From unknown Fri Aug 15 12:52:21 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#22689 <22689@debbugs.gnu.org> To: bug#22689 <22689@debbugs.gnu.org> Subject: Status: 25.1.50; implement logcount Reply-To: bug#22689 <22689@debbugs.gnu.org> Date: Fri, 15 Aug 2025 19:52:21 +0000 retitle 22689 25.1.50; implement logcount reassign 22689 emacs submitter 22689 Mark Oteiza severity 22689 wishlist thanks From debbugs-submit-bounces@debbugs.gnu.org Mon Feb 15 18:19:13 2016 Received: (at submit) by debbugs.gnu.org; 15 Feb 2016 23:19:13 +0000 Received: from localhost ([127.0.0.1]:40566 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84) (envelope-from ) id 1aVSQD-0008NS-HR for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:13 -0500 Received: from eggs.gnu.org ([208.118.235.92]:40779) by debbugs.gnu.org with esmtp (Exim 4.84) (envelope-from ) id 1aVSQB-0008NB-Sc for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:12 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aVSQ5-00064m-Or for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:06 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50,T_DKIM_INVALID autolearn=disabled version=3.3.2 Received: from lists.gnu.org ([2001:4830:134:3::11]:37116) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQ5-00064i-Ln for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:05 -0500 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59975) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQ4-0001g8-EV for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:19:05 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aVSQ1-000643-5r for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:19:04 -0500 Received: from mail-yw0-x235.google.com ([2607:f8b0:4002:c05::235]:36784) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQ1-00063u-0m for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:19:01 -0500 Received: by mail-yw0-x235.google.com with SMTP id e63so31303077ywc.3 for ; Mon, 15 Feb 2016 15:19:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:mime-version:content-type :content-transfer-encoding; bh=52gCL3e7IlJbAv1MYrZyoaeaF+irVjw73tKxYcTR9es=; b=OFjf/5BBgt7Sltmqdo1zJhMzqTA+HRUIktOly+Ceso5wLFXo0cdwnPXFAeJMIKSrzj vTB0cAq1qufv+Q/mZ4+wbab5PiPon2618gw5YK8cClma3Hi+4zQYuxKseTqcFM4sQD/D WQ/QDS8clxJtM2oZg5KsDZhh+LdB3dZGoaNNVEIQxKHbVyljTLN1XGxEU7TWg01tJw95 hfbEhQZgXM+JdSMoY4o0ogap2YBf4LHy1/+8ZzHJOEON2fZaQ2Jk+IL/+bk9rNpgCeoC 4snSY8oxnuZBE0YDKhzdmdywe08jDDOpCbD8RACiZK3jz1B10WBUC6G/Gub84l0yI8pr tXbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-type:content-transfer-encoding; bh=52gCL3e7IlJbAv1MYrZyoaeaF+irVjw73tKxYcTR9es=; b=J7I1zZUASw7O70XCu9tLNqUC0PKrNEE+D/w4F4Zb/WP2rxxWgYgesNk8DPo5/kL8EH cq+Dfo0hpMCFPHdwGrok7yxinEMKcVxdh7vj6kWTsGCoLXb4KK6ZpM95bWDgUmsLIol+ EVf2Ti7OvDcX+XzZRzPMId6aWQ8XVoIlb520/H+o520FxP0uDAemH+TVNhOIwyJkkYC9 aGTRQ//QA44C0+TRbEtW+tp0Gpa5fvccd6hweAkKTtoDvhbFLPiIAlNJWIrT/TrxM9KN WT1dTvyHuza0UT9J3xlUV0R42hzkgtleD9wQywKRes9ENh7cZaHG7Cr75H2s9D8YaUcE 0XCA== X-Gm-Message-State: AG10YORgbMHPCMbyCJsjW0yqSurmbpyFPOwmV13y79QoMkCXbPvB8SZGyhXGE5GlmqyP+NNk X-Received: by 10.13.250.196 with SMTP id k187mr11854036ywf.23.1455578340076; Mon, 15 Feb 2016 15:19:00 -0800 (PST) Received: from holos.localdomain (pool-96-227-83-242.phlapa.fios.verizon.net. [96.227.83.242]) by smtp.gmail.com with ESMTPSA id e4sm22369840ywb.0.2016.02.15.15.18.58 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 15 Feb 2016 15:18:58 -0800 (PST) Received: by holos.localdomain (Postfix, from userid 1000) id 3CF3F696ED; Mon, 15 Feb 2016 18:18:57 -0500 (EST) From: Mark Oteiza To: bug-gnu-emacs@gnu.org Subject: 25.1.50; implement logcount Date: Mon, 15 Feb 2016 18:18:56 -0500 Message-ID: <87h9h9pnof.fsf@udel.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 2001:4830:134:3::11 X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) Wishlist: Logcount, AKA popcount, Hamming weight, sideways sum. Basically, counting the number of 1s in a number's binary representation. The concept is similar to that in `bool-vector-count-population', except the argument would be a number, presumably a non-negative integer. There are a number of ways to go about it, and beyond that I'm not sure how to write it into data.c: - Some compilers have a __builtin_popcount (gcc since 2004 and llvm since 2005) - gmp has a popcount function - lots of algorithms implementing it Many are given here: https://en.wikipedia.org/wiki/Hamming_weight another resource: http://rosettacode.org/wiki/Population_count Guile's implementation uses table lookup: http://git.savannah.gnu.org/cgit/guile.git/tree/libguile/numbers.c#n5234 When I needed it, I just na=C3=AFvely ported an algorithm to elisp (in particular ignoring the case of negative numbers): (let ((m1 #x555555555555555) (m2 #x333333333333333) (m4 #x0f0f0f0f0f0f0f0f) (h01 #x0101010101010101)) (setq x (- x (logand (lsh x -1) m1))) (setq x (+ (logand x m2) (logand (lsh x -2) m2))) (setq x (logand (+ x (lsh x -4)) m4)) (lsh (* x h01) -56)) The table lookup isn't so different (defvar logtab [0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4]) (let ((count 0)) (while (not (zerop x)) (setq count (+ count (aref logtab (logand 15 x)))) (setq x (lsh x -4))) count) I couldn't find any implementation of this in calc either, but such a function/operation would fit in calc-bin. From debbugs-submit-bounces@debbugs.gnu.org Fri Sep 29 13:41:44 2017 Received: (at 22689) by debbugs.gnu.org; 29 Sep 2017 17:41:44 +0000 Received: from localhost ([127.0.0.1]:39539 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dxzIG-00064D-2G for submit@debbugs.gnu.org; Fri, 29 Sep 2017 13:41:44 -0400 Received: from mail-qt0-f193.google.com ([209.85.216.193]:52951) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dxzID-00063y-UG for 22689@debbugs.gnu.org; Fri, 29 Sep 2017 13:41:42 -0400 Received: by mail-qt0-f193.google.com with SMTP id o52so468834qtc.9 for <22689@debbugs.gnu.org>; Fri, 29 Sep 2017 10:41:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:subject:message-id:mime-version:content-disposition :user-agent; bh=zKeBM0eJgC9mpvD32rjMsB2CsoxuwqDOXpUlaBMKEzs=; b=zbl625T9gxzalKFB6Gs9kHJCp7+j6f1odNoD/150wlq54ahAxO3cs3T61GHuo0+CUr C68Nf3jy/dAqsUe9/ETLQXHvST6leWqQz6mi613MAtOCQd3bdpn35wTDmtX12fiTjqBP DhPXh0z0pZ1kYtLviqZmCBjdC6xFOAQw01M8WMN4ECrtbf9RJuI42gz+p2Ks7JugHZvu 6Nk05QQ+JQAkmWMgAosw3bLPGGe7Q9iWXrq7nvT0mBAnIs1wwe5LDpmSHdLg4MOoJ9DR oEYJecZdxIf5kAXvIAAob0iXznWIAgiS1lLfczskGJlVFmIOQZjJ/0w1FC9ipwFgJT4h f5Yw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:mime-version :content-disposition:user-agent; bh=zKeBM0eJgC9mpvD32rjMsB2CsoxuwqDOXpUlaBMKEzs=; b=ba3PUleU6OEbQz8UPEQCOv+c/vwPR3v4z7BSqs5YhjOP/aFOrhsS5NqPS/pZ9WrWZC Dz6Qpt7Q6SxBLdEYEhreNXaBlzkX60PGFLzqXOhuc12ZYYCY/MpB5XAUY0rohK9tWUyS VJx9f5cztDmWYsaYIi+MNnyNPmrVEphtud80b90tyztEHvMRF2oK5c1Gf10xzcWM0l4r XkqJsUHs7X7YOQFHy/AqGNS6XoOMw4jn2ji3jlHJifyiTl/HDJvplktlmzqi83h70nYI /nOfhqF9/5Efsu/lNgbT/K2Ef5ZMb2oLNdJxbZoaV+bK80nsa6/vqUEmD38vsAM7Qzod ngBA== X-Gm-Message-State: AMCzsaUgYWNmvNKDFARewKMS+QzEBX3cjbOyTW6jKdvq4gVVZlniKMci N2l9Py2jk753qm5qV/I9mpcbT85aeGY= X-Google-Smtp-Source: AOwi7QANEg6Teol5FVptBTDHJE5iWtwh8UNRPJ5kyyrSWmqsdxeEwjAUSqZtFF8r2wmRmOLHZswbOg== X-Received: by 10.200.46.216 with SMTP id i24mr7556176qta.257.1506706896084; Fri, 29 Sep 2017 10:41:36 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id z192sm2890850qka.91.2017.09.29.10.41.35 for <22689@debbugs.gnu.org> (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 29 Sep 2017 10:41:35 -0700 (PDT) Date: Fri, 29 Sep 2017 13:41:34 -0400 From: Mark Oteiza To: 22689@debbugs.gnu.org Subject: [PATCH] Add logcount Message-ID: <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: 0.5 (/) X-Debbugs-Envelope-To: 22689 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.5 (/) Hi, I made an attempt implementing this: diff --git a/src/data.c b/src/data.c index e070be6c20..1332173dcd 100644 --- a/src/data.c +++ b/src/data.c @@ -3069,6 +3069,57 @@ usage: (logxor &rest INTS-OR-MARKERS) */) return arith_driver (Alogxor, nargs, args); } +#if defined (__POPCNT__) && defined (__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1)) +#define HAVE_BUILTIN_POPCOUNTLL +#endif + +static uint32_t +bitcount32 (uint32_t b) +{ + b -= (b >> 1) & 0x55555555; + b = (b & 0x33333333) + ((b >> 2) & 0x33333333); + b = (b + (b >> 4)) & 0x0f0f0f0f; + return (b * 0x01010101) >> 24; +} + +static uint64_t +bitcount64 (uint64_t b) +{ + b -= (b >> 1) & 0x5555555555555555; + b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333); + b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f; + return (b * 0x0101010101010101) >> 56; +} + +DEFUN ("logcount", Flogcount, Slogcount, 1, 1, 0, + doc: /* Return population count of VALUE. */) + (register Lisp_Object value) +{ + Lisp_Object res; + + CHECK_NUMBER (value); + +#ifdef HAVE_BUILTIN_POPCOUNTLL + XSETINT (res, __builtin_popcount (XUINT (value))); +#else /* HAVE_BUILTIN_POPCOUNTLL */ + if (XINT (value) <= UINT_MAX) + XSETINT (res, bitcount32 (XUINT (value))); + else if (XINT (value) <= ULONG_MAX) + XSETINT (res, bitcount64 (XUINT (value))); + else + { + int count; + EMACS_UINT v = XUINT (value); + for (count = 0; v; count++) + { + v &= v - 1; + } + XSETINT (res, v); + } +#endif /* HAVE_BUILTIN_POPCOUNTLL */ + return res; +} + static Lisp_Object ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh) { @@ -3856,6 +3907,7 @@ syms_of_data (void) defsubr (&Slogand); defsubr (&Slogior); defsubr (&Slogxor); + defsubr (&Slogcount); defsubr (&Slsh); defsubr (&Sash); defsubr (&Sadd1); From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 07:43:08 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 11:43:08 +0000 Received: from localhost ([127.0.0.1]:40074 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyGAm-0000lv-By for submit@debbugs.gnu.org; Sat, 30 Sep 2017 07:43:08 -0400 Received: from eggs.gnu.org ([208.118.235.92]:57098) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyGAk-0000lV-JC for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 07:43:06 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyGAc-0003Zz-68 for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 07:43:01 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=disabled version=3.3.2 Received: from fencepost.gnu.org ([2001:4830:134:3::e]:47023) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyGAc-0003Zu-2P; Sat, 30 Sep 2017 07:42:58 -0400 Received: from 84.94.185.246.cable.012.net.il ([84.94.185.246]:3184 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1dyGAa-0008NJ-9G; Sat, 30 Sep 2017 07:42:57 -0400 Date: Sat, 30 Sep 2017 14:42:51 +0300 Message-Id: <83mv5c4dl0.fsf@gnu.org> From: Eli Zaretskii To: Mark Oteiza In-reply-to: <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> (message from Mark Oteiza on Fri, 29 Sep 2017 13:41:34 -0400) Subject: Re: bug#22689: [PATCH] Add logcount References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Eli Zaretskii Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) > Date: Fri, 29 Sep 2017 13:41:34 -0400 > From: Mark Oteiza > > I made an attempt implementing this: Thanks. I'm not an expert on these ops, but otherwise the code looks OK to me, modulo the minor comments below. This will eventually need a NEWS entry and some docs in the ELisp manual. > +#if defined (__POPCNT__) && defined (__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1)) > +#define HAVE_BUILTIN_POPCOUNTLL > +#endif Where does __POPCNT__ definition come from? I don't see it in my GCC's "gcc -dM" output. As for the rest of the condition, I think you should use GNUC_PREREQ, like this: #if GNUC_PREREQ (4, 1, 0) > +static uint64_t > +bitcount64 (uint64_t b) > +{ > + b -= (b >> 1) & 0x5555555555555555; > + b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333); > + b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f; > + return (b * 0x0101010101010101) >> 56; Shouldn't these constants have a ULL suffix, to make sure they are not truncated to a 32-bit int? > +#else /* HAVE_BUILTIN_POPCOUNTLL */ > + if (XINT (value) <= UINT_MAX) > + XSETINT (res, bitcount32 (XUINT (value))); > + else if (XINT (value) <= ULONG_MAX) > + XSETINT (res, bitcount64 (XUINT (value))); The comparisons against Uxxx_MAX seem to assume that VALUE is unsigned, but that's not guaranteed, right? From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 09:16:45 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 13:16:45 +0000 Received: from localhost ([127.0.0.1]:40144 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyHdN-0002yg-5s for submit@debbugs.gnu.org; Sat, 30 Sep 2017 09:16:45 -0400 Received: from mail-qk0-f171.google.com ([209.85.220.171]:49069) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyHdL-0002yS-MP for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 09:16:44 -0400 Received: by mail-qk0-f171.google.com with SMTP id a128so1877978qkc.5 for <22689@debbugs.gnu.org>; Sat, 30 Sep 2017 06:16:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=Y865DXghJthutX1oQmCnU2GlvsXA1+brF9SrvWrsTsI=; b=u46OtmU/hoEAyR0wAAuNkz2PWqFGeKEivHaeA45pg6BX9LYhMJu84P/tI82Ew9zdmz F7T6Oe56Vs8w6M28OtTdK+YX+lL9lo4Xow4B0UI68a+yatKgXMh6OzktiKzlORgMMMsO FcDRbizqqpZBAxIBl1l4w5iQsQTRSjVEweJreM94DZnSC0m5Ymp3YoqhArBKmxqyTNLL J+DkUGuU1MVSNLiVsnW+XbIhl+e+S26IOQK371m1QXM9qg9mwwWX5voV7BAvsK5JcQ8r ChPgHjnFoKAWgz+VLPnPxg5TvH0RDzMf6eXMCqJGOUPoHf5rSHOVBaxD1Z8RDhazuEBN j+AA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=Y865DXghJthutX1oQmCnU2GlvsXA1+brF9SrvWrsTsI=; b=ivNbeELa2+JQHs4ba91bDpAft86dirZVgXfHgTAAOUbt10mcB1VvOK6v6m4eo4h3Fc ipFBrEsSkZ85N+WIYIFgPN2ioFhGnhSYvWWBJWl3BbzYUIcpx4KM0Yq+pmTmrO/kdoP9 ynx5z62L6WuXeR9BbGlf4WgVm6KIt79MwzI0wILwyYVhtffO7wHxg79UAondEKuZnG4m jB72cRD+A0KuU3UEL6aWPqWO/PfMjZicmo/UA8YKTrFADYFlCHxuzo4ptnboSWzcUA6y lWWidFasvt18ilWMubmqzHDCJnRZXsFvC6ClFBhlulPRJ4bTT9oMXOHiDzpkGE9ApwW3 ZALg== X-Gm-Message-State: AMCzsaXho5yd9YC+OyM3Xc+5XHa1lmju/LBZTUqPfsAzbdqHQ9x1DDJ5 sHNQ30jj9snHebgAhp7X4TKMcg== X-Google-Smtp-Source: AOwi7QDEdfYeMNJ5hNnR5rVglaKMNs2IpCfhuWIajHN/eNL6F6roRhiUgjVMA22rI9Bk7//lRVuOKQ== X-Received: by 10.55.112.7 with SMTP id l7mr7596874qkc.38.1506777398137; Sat, 30 Sep 2017 06:16:38 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id d140sm4038117qkc.41.2017.09.30.06.16.36 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 06:16:37 -0700 (PDT) Date: Sat, 30 Sep 2017 09:16:36 -0400 From: Mark Oteiza To: Eli Zaretskii Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930131636.xe22lbwlea7yqelh@logos.localdomain> References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <83mv5c4dl0.fsf@gnu.org> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) On 30/09/17 at 02:42pm, Eli Zaretskii wrote: > > +#if defined (__POPCNT__) && defined (__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1)) > > +#define HAVE_BUILTIN_POPCOUNTLL > > +#endif > > Where does __POPCNT__ definition come from? I don't see it in my > GCC's "gcc -dM" output. > > As for the rest of the condition, I think you should use GNUC_PREREQ, > like this: > > #if GNUC_PREREQ (4, 1, 0) I guess it comes from nowhere, that condition and the two helper functions come from here https://rosettacode.org/wiki/Population_count#C > > +static uint64_t > > +bitcount64 (uint64_t b) > > +{ > > + b -= (b >> 1) & 0x5555555555555555; > > + b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333); > > + b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f; > > + return (b * 0x0101010101010101) >> 56; > > Shouldn't these constants have a ULL suffix, to make sure they are not > truncated to a 32-bit int? Probably, I don't know--I'm out of my comfort zone here. > > +#else /* HAVE_BUILTIN_POPCOUNTLL */ > > + if (XINT (value) <= UINT_MAX) > > + XSETINT (res, bitcount32 (XUINT (value))); > > + else if (XINT (value) <= ULONG_MAX) > > + XSETINT (res, bitcount64 (XUINT (value))); > > The comparisons against Uxxx_MAX seem to assume that VALUE is > unsigned, but that's not guaranteed, right? True. Should I instead be doing XINT (value) <= xxx_MAX && XINT (value) >= xxx_MIN or might there be a better check? For negative values popcount typically counts ones of the two's complement From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 10:00:03 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 14:00:03 +0000 Received: from localhost ([127.0.0.1]:41226 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyIJH-0004Gx-2v for submit@debbugs.gnu.org; Sat, 30 Sep 2017 10:00:03 -0400 Received: from eggs.gnu.org ([208.118.235.92]:52140) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyIJF-0004Fx-0Y for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 10:00:01 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyIJ6-0000a8-LM for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 09:59:55 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=disabled version=3.3.2 Received: from fencepost.gnu.org ([2001:4830:134:3::e]:34422) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyIJ6-0000Zt-Is; Sat, 30 Sep 2017 09:59:52 -0400 Received: from 84.94.185.246.cable.012.net.il ([84.94.185.246]:3326 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1dyIJ5-0005wq-PE; Sat, 30 Sep 2017 09:59:52 -0400 Date: Sat, 30 Sep 2017 16:59:47 +0300 Message-Id: <83a81c478s.fsf@gnu.org> From: Eli Zaretskii To: Mark Oteiza In-reply-to: <20170930131636.xe22lbwlea7yqelh@logos.localdomain> (message from Mark Oteiza on Sat, 30 Sep 2017 09:16:36 -0400) Subject: Re: bug#22689: [PATCH] Add logcount References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Eli Zaretskii Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) > Date: Sat, 30 Sep 2017 09:16:36 -0400 > From: Mark Oteiza > Cc: 22689@debbugs.gnu.org > > On 30/09/17 at 02:42pm, Eli Zaretskii wrote: > > > +#if defined (__POPCNT__) && defined (__GNUC__) && (__GNUC__> 4 || (__GNUC__== 4 && __GNUC_MINOR__> 1)) > > > +#define HAVE_BUILTIN_POPCOUNTLL > > > +#endif > > > > Where does __POPCNT__ definition come from? I don't see it in my > > GCC's "gcc -dM" output. > > > > As for the rest of the condition, I think you should use GNUC_PREREQ, > > like this: > > > > #if GNUC_PREREQ (4, 1, 0) > > I guess it comes from nowhere, that condition and the two helper > functions come from here > https://rosettacode.org/wiki/Population_count#C I only see that symbol in the GCC sources, which I don't think are relevant here. If you drop the __POPCNT__ part, does the code still work for you? > > > +static uint64_t > > > +bitcount64 (uint64_t b) > > > +{ > > > + b -= (b >> 1) & 0x5555555555555555; > > > + b = (b & 0x3333333333333333) + ((b >> 2) & 0x3333333333333333); > > > + b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0f; > > > + return (b * 0x0101010101010101) >> 56; > > > > Shouldn't these constants have a ULL suffix, to make sure they are not > > truncated to a 32-bit int? > > Probably, I don't know--I'm out of my comfort zone here. I'd use the suffixes. > > > +#else /* HAVE_BUILTIN_POPCOUNTLL */ > > > + if (XINT (value) <= UINT_MAX) > > > + XSETINT (res, bitcount32 (XUINT (value))); > > > + else if (XINT (value) <= ULONG_MAX) > > > + XSETINT (res, bitcount64 (XUINT (value))); > > > > The comparisons against Uxxx_MAX seem to assume that VALUE is > > unsigned, but that's not guaranteed, right? > > True. Should I instead be doing > > XINT (value) <= xxx_MAX && > XINT (value) >= xxx_MIN > > or might there be a better check? For negative values popcount > typically counts ones of the two's complement I'd just assign to an unsigned temporary, IIUC the semantics. Btw, on Windows, a long is a 32-bit type, so I think we need to check against ULONG_LONG_MAX as well. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 10:55:39 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 14:55:39 +0000 Received: from localhost ([127.0.0.1]:41294 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyJB4-0005eV-Iw for submit@debbugs.gnu.org; Sat, 30 Sep 2017 10:55:39 -0400 Received: from mail-qk0-f172.google.com ([209.85.220.172]:50509) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyJAz-0005eF-5u for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 10:55:37 -0400 Received: by mail-qk0-f172.google.com with SMTP id s132so1992529qke.7 for <22689@debbugs.gnu.org>; Sat, 30 Sep 2017 07:55:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=DjiRbLn5bwXSnPxOBsknOM0koSPMwfLlE7ZawUqkxNk=; b=1C7tEoAkNAvFs0Z3AhJyOLyUCbCbE10LstOOikMsXh7iK9r+oP6zVnqaZdLbMb87Gf mIYv7YG7cag2thzv9OxaajEfRZwk6I4Y6rXkcdQxkNvlVMc9CtfeV+ply9ZSCD4dNsC0 TVTgf/atFErk7iACMJx2q2w0w/7y9mRPuw12rlGAClkPk7T7gVzy54oVY325yPuas9YX /UTyaZZv1itQ0pyMwGPBzWkWsYnBYAZLO/M6FOE98HvauKIWBfotX1NVDsGk/EOmfWKx Tle6koBsCpth/mw0TuOtkbQ5JxYXtOXvFerFfUuBFqRC2OEgbKKR+MPr4C9qKdEPtsk8 gfrg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=DjiRbLn5bwXSnPxOBsknOM0koSPMwfLlE7ZawUqkxNk=; b=V8CDO9VKl4fbDqi9Weda3MbVktMtex8h8lYloLbB24vbjMbk/gm2RYgXtKodceZvM3 AZAu8rDIFbskuCHZspCHVkopJmmDNEd/dqniMY8dS9e/YyyRThBAAgiLUPvorjKKN37X se5mHgN+mX2+CB1fww37788L+2ZpThkqzRl6ULRzeXgx4ZHN/VkcJtxI4gAuFDK0bkFK cq3zStZqrXt4h2Y0H0HgF1rcUKaklaqmxgZqGsPNC0PpB/F15u8pd9en5QA9I+Vz3JIA KDisOoBs5n02Xs01vnpLXUZ7cs341Jm/KQMmG1NuEjAPwqIml+hqbHkpVVGvyZ6LpPVb gUXw== X-Gm-Message-State: AMCzsaWmmX9UoWSV8T6SMmC4HhCAWmf0874msWeIecMDsKoxYyC4Rpd8 z/Q6OF0Iqg6KemRS/pwrFstddg== X-Google-Smtp-Source: AOwi7QC+0jgQjtoA4oEgcrTFAlYMX/ClGxKWBaLXpu48CtLra495sCARNOrs1UGsjdyvbcJGqYvoaQ== X-Received: by 10.55.137.65 with SMTP id l62mr4963007qkd.257.1506783327437; Sat, 30 Sep 2017 07:55:27 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id h19sm4419301qta.26.2017.09.30.07.55.26 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 07:55:26 -0700 (PDT) Date: Sat, 30 Sep 2017 10:55:25 -0400 From: Mark Oteiza To: Eli Zaretskii Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <83a81c478s.fsf@gnu.org> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) On 30/09/17 at 04:59pm, Eli Zaretskii wrote: > I only see that symbol in the GCC sources, which I don't think are > relevant here. > > If you drop the __POPCNT__ part, does the code still work for you? Yes. > > > > +#else /* HAVE_BUILTIN_POPCOUNTLL */ > > > > + if (XINT (value) <= UINT_MAX) > > > > + XSETINT (res, bitcount32 (XUINT (value))); > > > > + else if (XINT (value) <= ULONG_MAX) > > > > + XSETINT (res, bitcount64 (XUINT (value))); > > > > > > The comparisons against Uxxx_MAX seem to assume that VALUE is > > > unsigned, but that's not guaranteed, right? > > > > True. Should I instead be doing > > > > XINT (value) <= xxx_MAX && > > XINT (value) >= xxx_MIN > > > > or might there be a better check? For negative values popcount > > typically counts ones of the two's complement > > I'd just assign to an unsigned temporary, IIUC the semantics. > > Btw, on Windows, a long is a 32-bit type, so I think we need > to check against ULONG_LONG_MAX as well. I tried implementing your comments (and added a test). I don't know what to do in the #else for ULONG_LONG_MAX. diff --git a/src/data.c b/src/data.c index e070be6c20..8b3866151d 100644 --- a/src/data.c +++ b/src/data.c @@ -3069,6 +3069,66 @@ usage: (logxor &rest INTS-OR-MARKERS) */) return arith_driver (Alogxor, nargs, args); } +#if GNUC_PREREQ (4, 1, 0) +#define HAVE_BUILTIN_POPCOUNTLL +#endif + +#ifndef HAVE_BUILTIN_POPCOUNTLL +static uint32_t +logcount32 (uint32_t b) +{ + b -= (b >> 1) & 0x55555555; + b = (b & 0x33333333) + ((b >> 2) & 0x33333333); + b = (b + (b >> 4)) & 0x0f0f0f0f; + return (b * 0x01010101) >> 24; +} + +static uint64_t +logcount64 (uint64_t b) +{ + b -= (b >> 1) & 0x5555555555555555ULL; + b = (b & 0x3333333333333333ULL) + ((b >> 2) & 0x3333333333333333ULL); + b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0fULL; + return (b * 0x0101010101010101ULL) >> 56; +} +#endif /* HAVE_BUILTIN_POPCOUNTLL */ + +DEFUN ("logcount", Flogcount, Slogcount, 1, 1, 0, + doc: /* Return population count of VALUE. +If VALUE is negative, the count is of its two's complement representation. */) + (register Lisp_Object value) +{ + Lisp_Object res; + EMACS_UINT v; + + CHECK_NUMBER (value); + + v = XUINT (value); +#ifdef HAVE_BUILTIN_POPCOUNTLL + if (v <= UINT_MAX) + XSETINT (res, __builtin_popcount (v)); + else if (v <= ULONG_MAX) + XSETINT (res, __builtin_popcountl (v)); + else if (v <= ULONG_LONG_MAX) + XSETINT (res, __builtin_popcountll (v)); +#else /* HAVE_BUILTIN_POPCOUNTLL */ + if (v <= UINT_MAX) + XSETINT (res, logcount32 (v)); + else if (v <= ULONG_MAX) + XSETINT (res, logcount64 (v)); +#endif /* HAVE_BUILTIN_POPCOUNTLL */ + else + { + unsigned int count; + for (count = 0; v; count++) + { + v &= v - 1; + } + XSETINT (res, v); + } + return res; +} + static Lisp_Object ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh) { @@ -3856,6 +3916,7 @@ syms_of_data (void) defsubr (&Slogand); defsubr (&Slogior); defsubr (&Slogxor); + defsubr (&Slogcount); defsubr (&Slsh); defsubr (&Sash); defsubr (&Sadd1); diff --git a/test/src/data-tests.el b/test/src/data-tests.el index 8de8c145d4..d1154cc5c4 100644 --- a/test/src/data-tests.el +++ b/test/src/data-tests.el @@ -107,6 +107,19 @@ (should (isnan (min 1.0 0.0e+NaN))) (should (isnan (min 1.0 0.0e+NaN 1.1)))) +(defun data-tests-popcnt (byte) + "Calculate the Hamming weight of BYTE." + (setq byte (- byte (logand (lsh byte -1) #x55555555))) + (setq byte (+ (logand byte #x33333333) (logand (lsh byte -2) #x33333333))) + (lsh (* (logand (+ byte (lsh byte -4)) #x0f0f0f0f) #x01010101) -24)) + +(ert-deftest data-tests-logcount () + (should (cl-loop for n in (number-sequence 0 255) + always (= (logcount n) (data-tests-popcnt n)))) + ;; https://oeis.org/A000120 + (should (= 11 (logcount 9727))) + (should (= 8 (logcount 9999)))) + ;; Bool vector tests. Compactly represent bool vectors as hex ;; strings. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 11:38:33 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 15:38:34 +0000 Received: from localhost ([127.0.0.1]:41327 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyJqb-0006mq-Mb for submit@debbugs.gnu.org; Sat, 30 Sep 2017 11:38:33 -0400 Received: from eggs.gnu.org ([208.118.235.92]:43298) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyJqa-0006md-Jt for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 11:38:32 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyJqS-00049D-8G for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 11:38:27 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=disabled version=3.3.2 Received: from fencepost.gnu.org ([2001:4830:134:3::e]:46050) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyJqS-000495-2P; Sat, 30 Sep 2017 11:38:24 -0400 Received: from 84.94.185.246.cable.012.net.il ([84.94.185.246]:4052 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1dyJqR-0005MS-Be; Sat, 30 Sep 2017 11:38:23 -0400 Date: Sat, 30 Sep 2017 18:38:18 +0300 Message-Id: <838tgw42ol.fsf@gnu.org> From: Eli Zaretskii To: Mark Oteiza In-reply-to: <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> (message from Mark Oteiza on Sat, 30 Sep 2017 10:55:25 -0400) Subject: Re: bug#22689: [PATCH] Add logcount References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Eli Zaretskii Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) > Date: Sat, 30 Sep 2017 10:55:25 -0400 > From: Mark Oteiza > Cc: 22689@debbugs.gnu.org > > > Btw, on Windows, a long is a 32-bit type, so I think we need > > to check against ULONG_LONG_MAX as well. > > I tried implementing your comments (and added a test). I don't know > what to do in the #else for ULONG_LONG_MAX. Same as you do for ULONG_MAX, I think. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 12:03:41 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 16:03:41 +0000 Received: from localhost ([127.0.0.1]:41331 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyKEu-0007QP-QT for submit@debbugs.gnu.org; Sat, 30 Sep 2017 12:03:41 -0400 Received: from mail-qk0-f175.google.com ([209.85.220.175]:51539) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyKEs-0007QC-UZ for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 12:03:39 -0400 Received: by mail-qk0-f175.google.com with SMTP id 17so2055517qkq.8 for <22689@debbugs.gnu.org>; Sat, 30 Sep 2017 09:03:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=6kbixxeCXss0Zx2vai/4kALdlMpboNYO2/AZV36YA+Y=; b=eQyknp30+ySmXYDmzs93TU/J7POb/wIJvNHymf+s3cN/NO9n/GHzHmKAMcJbJsrnrX CzLGXlN5pZ2whl1T8MJsO7CRWPNaFvX1MAPFml+hm1T9hCS4kTK5J6slI2IUeqh9prVN HsO2AjteMC6Us/gnDngd9iwONtJGICS0C+sPKS9z39fD78FMYCUbXgFHlAFSCgHHcuqL EowEZJsSO+f6AtqDaYCeeLaKGB9cytNy+lriVP49V8hCXpIza33qIts+lS/0mkyDW9YR FclXRZhndXgSz8uIHqep1z4oUmO+liNfMGax/5n2mBfYNJd26wpt3CO+ZlWPdvRfK/H3 K+uw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=6kbixxeCXss0Zx2vai/4kALdlMpboNYO2/AZV36YA+Y=; b=H2noj7PgxGJ312OGl8uUCk+20w9QRqN+2h7rPpA9JDklrnc8ztxHkn1St6EoP+BUNt jxskV2zb9F4INDnJzUMBmSscB0/1M8uTBNzAVn/KGHQBaoFe0izP/YmNNGr6JiBdUeLu ThE9oUJw+CyorZTO9tyuruwtSbGFt4r3X4gBL23p35y4IA0gXoV288bv+ZUuwQ3Va3q1 6K8Q4v3nP42MfiSi2Y4iyYl/l+Zm/HkBD+/V+vhVwx26pS/e8oEEEo9KGi3Wjn1iw9Pz xKdLzn3UmN37So483ma8bq2fL+J/+KpUziuBSeiIkZC/PZxFebzD2m9BNprosS+jQxKX U+og== X-Gm-Message-State: AMCzsaVa6Taqb1CuGrkEdrHZa8rPECNBQxFLY5L5RxJj6xJVdBTsafij /v3AFn8fL+HSb2/fiKaV3PHK6Xryh5g= X-Google-Smtp-Source: AOwi7QAELOJcc+SAH8xkaIoSDhyzGXv/2PRvKGyfLhvxVf9cmlZpUP+4HMtl9tjd/5/K93mlTwxB0A== X-Received: by 10.233.221.3 with SMTP id r3mr7937152qkf.219.1506787413316; Sat, 30 Sep 2017 09:03:33 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id t184sm4197263qkc.74.2017.09.30.09.03.32 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 09:03:32 -0700 (PDT) Date: Sat, 30 Sep 2017 12:03:31 -0400 From: Mark Oteiza To: Eli Zaretskii Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930160331.ibxxjh626jrlm4ef@logos.localdomain> References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> <838tgw42ol.fsf@gnu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <838tgw42ol.fsf@gnu.org> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) On 30/09/17 at 06:38pm, Eli Zaretskii wrote: > > Date: Sat, 30 Sep 2017 10:55:25 -0400 > > From: Mark Oteiza > > Cc: 22689@debbugs.gnu.org > > > > > Btw, on Windows, a long is a 32-bit type, so I think we need > > > to check against ULONG_LONG_MAX as well. > > > > I tried implementing your comments (and added a test). I don't know > > what to do in the #else for ULONG_LONG_MAX. > > Same as you do for ULONG_MAX, I think. so the following? else if (v <= ULONG_MAX || v <= ULONG_LONG_MAX) XSETINT (res, logcount64 (v)); From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 12:18:08 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 16:18:08 +0000 Received: from localhost ([127.0.0.1]:41342 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyKSu-0007mW-KT for submit@debbugs.gnu.org; Sat, 30 Sep 2017 12:18:08 -0400 Received: from eggs.gnu.org ([208.118.235.92]:35141) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyKSt-0007mH-6x for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 12:18:07 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyKSk-000839-Oy for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 12:18:01 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=disabled version=3.3.2 Received: from fencepost.gnu.org ([2001:4830:134:3::e]:51710) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyKSk-00082r-Lf; Sat, 30 Sep 2017 12:17:58 -0400 Received: from 84.94.185.246.cable.012.net.il ([84.94.185.246]:4150 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1dyKSj-0004TZ-Ie; Sat, 30 Sep 2017 12:17:58 -0400 Date: Sat, 30 Sep 2017 19:17:50 +0300 Message-Id: <8360c040up.fsf@gnu.org> From: Eli Zaretskii To: Mark Oteiza In-reply-to: <20170930160331.ibxxjh626jrlm4ef@logos.localdomain> (message from Mark Oteiza on Sat, 30 Sep 2017 12:03:31 -0400) Subject: Re: bug#22689: [PATCH] Add logcount References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> <838tgw42ol.fsf@gnu.org> <20170930160331.ibxxjh626jrlm4ef@logos.localdomain> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Eli Zaretskii Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) > Date: Sat, 30 Sep 2017 12:03:31 -0400 > From: Mark Oteiza > Cc: 22689@debbugs.gnu.org > > > > I tried implementing your comments (and added a test). I don't know > > > what to do in the #else for ULONG_LONG_MAX. > > > > Same as you do for ULONG_MAX, I think. > > so the following? > > else if (v <= ULONG_MAX || v <= ULONG_LONG_MAX) > XSETINT (res, logcount64 (v)); Yes. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 12:50:52 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 16:50:52 +0000 Received: from localhost ([127.0.0.1]:41367 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyKya-00007a-36 for submit@debbugs.gnu.org; Sat, 30 Sep 2017 12:50:52 -0400 Received: from odoacer.turtle-trading.net ([217.91.34.180]:45475) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyKyY-00007L-Da for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 12:50:50 -0400 Received: from justinian.turtle-trading.net ([192.168.2.118]) by odoacer.turtle-trading.net with esmtp (Exim 4.80) (envelope-from ) id 1dyKyQ-0006Dc-FY; Sat, 30 Sep 2017 18:50:42 +0200 Received: from benny by justinian.turtle-trading.net with local (Exim 4.84_2) (envelope-from ) id 1dyKyQ-0003Fe-CF; Sat, 30 Sep 2017 18:50:42 +0200 From: Benjamin Riefenstahl To: Mark Oteiza Subject: Re: bug#22689: [PATCH] Add logcount References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> Date: Sat, 30 Sep 2017 18:50:42 +0200 In-Reply-To: <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> (Mark Oteiza's message of "Sat, 30 Sep 2017 10:55:25 -0400") Message-ID: <87tvzk5dwd.fsf@blei.turtle-trading.net> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.60 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Score: -0.0 (/) X-Debbugs-Envelope-To: 22689 Cc: Eli Zaretskii , 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) Hi Mark, Just a drive-by note: Mark Oteiza writes: > + { > + unsigned int count; > + for (count = 0; v; count++) > + { > + v &= v - 1; > + } > + XSETINT (res, v); > + } Isn't this a fancy way of just saying "XSETINT (res, 0)"? The variable "count" is incremented but never used, so without it the loop degenerates to while (v) { v &= v - 1; } I other words, this just loops until "v == 0". Maybe that assignment should be "XSETINT (res, count)"? That would actually use the variable "count". benny From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 12:59:13 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 16:59:13 +0000 Received: from localhost ([127.0.0.1]:41371 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyL6e-0000JD-SG for submit@debbugs.gnu.org; Sat, 30 Sep 2017 12:59:13 -0400 Received: from mail-qk0-f180.google.com ([209.85.220.180]:49478) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyL6d-0000Iz-9q for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 12:59:11 -0400 Received: by mail-qk0-f180.google.com with SMTP id u67so2139431qkg.6 for <22689@debbugs.gnu.org>; Sat, 30 Sep 2017 09:59:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=jtFAHv9iNQmWgXIUFJloBnDYj876DqiKQGr9xPNtDbk=; b=vHcx+dIXgi0iuInlJa/m4U1jTlX6VYPY+8nStaXbZNh7A3tAVQKtazPrCxpLDtewck ew9maVH8SCl3/GtzC2z/J/Wm04Q720Z6G6UdQQdGmp1V0L6BZotb/b6tnuiOFSAvF9iv 0gRCAYB32ZY208SbimrELwWwaEVZA8TyKbbCmkKRQsTp7Zzd7sb2DlRSixOOCgBgL3JX 2typnY1bvx9LsR+UXLIXtXe3vjOZObXJEP3a4zjYC/eUsrf7CmiU7zs284PY8++cW17q LrzxWIpkacWuJNXCk/hnkZWd2+QY+O2S8tTZ3BwgbmC7K9BZzZzUHV3dN7iJuJYRjYpC Kz1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=jtFAHv9iNQmWgXIUFJloBnDYj876DqiKQGr9xPNtDbk=; b=AkoiF/rcKPVZm+NaF1K1ZfgX8gmwZUvzrxqd81NUz/QRJZJ+QCnVSXDuNCrszw1PQ1 obSqd7xuVKrvLEbpZiaMmfq1zu1o9UjdTvvA+EV7urSss6wLqF1S8iDHD+ljLulRmuds W4hLdXXJtpdt5slrBO8+uEyPuY8hhTEAg5BjkPK0/blD4RXKdCcuAyGvYau+6/SruwYZ N1vdzXicR3ssrmb8dIIae21hVrU5YXAiR1LHkjbPkMYbZud7R7k7pADhnpkT/h0J5k/O y6kSI5V6BFhV3LmFyEEClx+DZaI4kjt+eyRs5hIE/kVrPr9iFK7oFWKT1g2sMoB+Qp87 8neA== X-Gm-Message-State: AMCzsaXzvINENpEOmt+kPQVgGCMZd25tI/k4uSc0UngX0cHo6qYQOc++ bKFUeA3Q8J5Jv5vn/JQ1X0hRpA== X-Google-Smtp-Source: AOwi7QDMdl6wZXQXQQKLEIvgT0CddxHP1NAyfm3iopkTLRDLgJJ1htOKP5CjvNeYm485opNdVe1P2g== X-Received: by 10.55.99.144 with SMTP id x138mr8433918qkb.76.1506790745600; Sat, 30 Sep 2017 09:59:05 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id w14sm3305123qkg.82.2017.09.30.09.59.04 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 09:59:05 -0700 (PDT) Date: Sat, 30 Sep 2017 12:59:04 -0400 From: Mark Oteiza To: Benjamin Riefenstahl Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930165904.2mt53wuphermhs6q@logos.localdomain> References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> <87tvzk5dwd.fsf@blei.turtle-trading.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <87tvzk5dwd.fsf@blei.turtle-trading.net> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: 0.5 (/) X-Debbugs-Envelope-To: 22689 Cc: Eli Zaretskii , 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.5 (/) On 30/09/17 at 06:50pm, Benjamin Riefenstahl wrote: > Hi Mark, > > Just a drive-by note: > > Mark Oteiza writes: > > + { > > + unsigned int count; > > + for (count = 0; v; count++) > > + { > > + v &= v - 1; > > + } > > + XSETINT (res, v); > > + } > > Isn't this a fancy way of just saying "XSETINT (res, 0)"? The variable > "count" is incremented but never used, so without it the loop > degenerates to > > while (v) > { > v &= v - 1; > } > > I other words, this just loops until "v == 0". > > Maybe that assignment should be "XSETINT (res, count)"? That would > actually use the variable "count". I think you're right, thank you. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 13:08:08 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 17:08:08 +0000 Received: from localhost ([127.0.0.1]:41375 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyLFH-0000XM-NB for submit@debbugs.gnu.org; Sat, 30 Sep 2017 13:08:07 -0400 Received: from mail-qt0-f176.google.com ([209.85.216.176]:49177) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyLFF-0000Wt-Mu for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 13:08:06 -0400 Received: by mail-qt0-f176.google.com with SMTP id o3so3033271qte.6 for <22689@debbugs.gnu.org>; Sat, 30 Sep 2017 10:08:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=ErtSVcVlTE1adfknL5H/PrIuwAXVkeFGZsMEaINa5h4=; b=peag3PNFFp/8ZrgIqh8ga1oEOPKerS1NPUucHAER7SCzGM3HBhZEaGzwmbqQ0pdWBB HxCGmy/uMLC8x4ROGjBw9OQPG+WolU0LZgFNbxq/S2p2qdpKTuSDnUxHm1dezcoSNPXf K2u4BLOYtWUMybqX4uVyNhMxcpyA3z2SBUs96TglmM7hietOSDw1ecNrRUoMvN1K7VCW w4cr2Ox5yrS+i8djF9Agd7B0PNv5090cVYqw/CY9xjdQl5/2z83VgmVIrIU3Tc3dZogm HXQNXSts9ij293cwXVvOeoT5l2apA3upz6FrR6djddFUPKCyvpbDRGaomrlEEwnfbg2j h22g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=ErtSVcVlTE1adfknL5H/PrIuwAXVkeFGZsMEaINa5h4=; b=XdkrwCRxhodWVAtKBc1DVtCX2ov+rAi0jWUL0AVfZ81Rd+7NzGdJrbvHP3bS8Dt6WX P8r5p5u0SYZlPK4HZ4CH4gMzG8xwv33oqFn6JaBbZc8DdHU89pK0SyGi/qSSWT5+s67F /EkwS9wEKY7x1B/15SXpTVtUDNg8qa3bT0PwRM5Pv25i0x+QkvbQ4tumf8O6oXzI+e1L /uQzOSU40m7qwZRadosbFEAGtRa/jJ4bz8SUUB25WgyeOopqd8JDqB7/b6ANgG+JmWGA 3lNz21b+gDQ4IWqk8RkvBiXfuYkEUMr0KZ5monlILh+UtCMZkzm4OqP4IrM9P+KOzx1x 7LPw== X-Gm-Message-State: AMCzsaVZG3EmdvU2I3meYYw5e3TRIymLx4uNfGlo+5JdeaTU3cxYKOrO Iu/bEoP/sbQM5BPEx4gPqBPsNF0Nhds= X-Google-Smtp-Source: AOwi7QC2nK9jOUKey7yrNpxdjA3Yw9MVJNOdVdoiucjSE9JbvXyRhf+9ibfxblmHWApPpVsz3azVPg== X-Received: by 10.237.53.225 with SMTP id d30mr11811643qte.164.1506791280235; Sat, 30 Sep 2017 10:08:00 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id 8sm2623223qkj.59.2017.09.30.10.07.59 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 10:07:59 -0700 (PDT) Date: Sat, 30 Sep 2017 13:07:58 -0400 From: Mark Oteiza To: Eli Zaretskii Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930170758.zp2hdjw3il5fbier@logos.localdomain> References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> <838tgw42ol.fsf@gnu.org> <20170930160331.ibxxjh626jrlm4ef@logos.localdomain> <8360c040up.fsf@gnu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <8360c040up.fsf@gnu.org> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: 0.5 (/) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.5 (/) On 30/09/17 at 07:17pm, Eli Zaretskii wrote: > > Date: Sat, 30 Sep 2017 12:03:31 -0400 > > From: Mark Oteiza > > Cc: 22689@debbugs.gnu.org > > > > > > I tried implementing your comments (and added a test). I don't know > > > > what to do in the #else for ULONG_LONG_MAX. > > > > > > Same as you do for ULONG_MAX, I think. > > > > so the following? > > > > else if (v <= ULONG_MAX || v <= ULONG_LONG_MAX) > > XSETINT (res, logcount64 (v)); > > Yes. Ok. Patch including this, Benjamin's catch, and documentation. doc/lispref/numbers.texi | 10 ++++++++ etc/NEWS | 3 +++ src/data.c | 61 ++++++++++++++++++++++++++++++++++++++++++++++++ test/src/data-tests.el | 13 +++++++++++ 4 files changed, 87 insertions(+) diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi index 3fdc94169b..29c6429eda 100644 --- a/doc/lispref/numbers.texi +++ b/doc/lispref/numbers.texi @@ -1107,6 +1107,16 @@ Bitwise Operations @end example @end defun +@defun logcount integer +This function returns the population count of @var{integer}: the +number of ones in the binary representation of @var{integer}. + +@example +(logcount 42) ; 42 = #b101010 + @result{} 3 +@end example +@end defun + @node Math Functions @section Standard Mathematical Functions @cindex transcendental functions diff --git a/etc/NEWS b/etc/NEWS index 238c7b7ea4..8fbc354fc0 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -31,6 +31,9 @@ When you add a new item, use the appropriate mark if you are sure it applies, * Changes in Emacs 27.1 ++++ +** New function 'logcount' calculates an integer's Hamming weight. + * Editing Changes in Emacs 27.1 diff --git a/src/data.c b/src/data.c index e070be6c20..f470d6ffaa 100644 --- a/src/data.c +++ b/src/data.c @@ -3069,6 +3069,66 @@ usage: (logxor &rest INTS-OR-MARKERS) */) return arith_driver (Alogxor, nargs, args); } +#if GNUC_PREREQ (4, 1, 0) +#define HAVE_BUILTIN_POPCOUNTLL +#endif + +#ifndef HAVE_BUILTIN_POPCOUNTLL +static uint32_t +logcount32 (uint32_t b) +{ + b -= (b >> 1) & 0x55555555; + b = (b & 0x33333333) + ((b >> 2) & 0x33333333); + b = (b + (b >> 4)) & 0x0f0f0f0f; + return (b * 0x01010101) >> 24; +} + +static uint64_t +logcount64 (uint64_t b) +{ + b -= (b >> 1) & 0x5555555555555555ULL; + b = (b & 0x3333333333333333ULL) + ((b >> 2) & 0x3333333333333333ULL); + b = (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0fULL; + return (b * 0x0101010101010101ULL) >> 56; +} +#endif /* HAVE_BUILTIN_POPCOUNTLL */ + +DEFUN ("logcount", Flogcount, Slogcount, 1, 1, 0, + doc: /* Return population count of VALUE. +If VALUE is negative, the count is of its two's complement representation. */) + (register Lisp_Object value) +{ + Lisp_Object res; + EMACS_UINT v; + + CHECK_NUMBER (value); + + v = XUINT (value); +#ifdef HAVE_BUILTIN_POPCOUNTLL + if (v <= UINT_MAX) + XSETINT (res, __builtin_popcount (v)); + else if (v <= ULONG_MAX) + XSETINT (res, __builtin_popcountl (v)); + else if (v <= ULONG_LONG_MAX) + XSETINT (res, __builtin_popcountll (v)); +#else /* HAVE_BUILTIN_POPCOUNTLL */ + if (v <= UINT_MAX) + XSETINT (res, logcount32 (v)); + else if (v <= ULONG_MAX || v <= ULONG_LONG_MAX) + XSETINT (res, logcount64 (v)); +#endif /* HAVE_BUILTIN_POPCOUNTLL */ + else + { + unsigned int count; + for (count = 0; v; count++) + { + v &= v - 1; + } + XSETINT (res, count); + } + return res; +} + static Lisp_Object ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh) { @@ -3856,6 +3916,7 @@ syms_of_data (void) defsubr (&Slogand); defsubr (&Slogior); defsubr (&Slogxor); + defsubr (&Slogcount); defsubr (&Slsh); defsubr (&Sash); defsubr (&Sadd1); diff --git a/test/src/data-tests.el b/test/src/data-tests.el index 8de8c145d4..d1154cc5c4 100644 --- a/test/src/data-tests.el +++ b/test/src/data-tests.el @@ -107,6 +107,19 @@ (should (isnan (min 1.0 0.0e+NaN))) (should (isnan (min 1.0 0.0e+NaN 1.1)))) +(defun data-tests-popcnt (byte) + "Calculate the Hamming weight of BYTE." + (setq byte (- byte (logand (lsh byte -1) #x55555555))) + (setq byte (+ (logand byte #x33333333) (logand (lsh byte -2) #x33333333))) + (lsh (* (logand (+ byte (lsh byte -4)) #x0f0f0f0f) #x01010101) -24)) + +(ert-deftest data-tests-logcount () + (should (cl-loop for n in (number-sequence 0 255) + always (= (logcount n) (data-tests-popcnt n)))) + ;; https://oeis.org/A000120 + (should (= 11 (logcount 9727))) + (should (= 8 (logcount 9999)))) + ;; Bool vector tests. Compactly represent bool vectors as hex ;; strings. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 13:53:49 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 17:53:49 +0000 Received: from localhost ([127.0.0.1]:41402 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyLxV-0001ji-Ek for submit@debbugs.gnu.org; Sat, 30 Sep 2017 13:53:49 -0400 Received: from eggs.gnu.org ([208.118.235.92]:38376) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyLxT-0001jS-JW for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 13:53:47 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyLxK-0007tx-Mr for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 13:53:41 -0400 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,RP_MATCHES_RCVD autolearn=disabled version=3.3.2 Received: from fencepost.gnu.org ([2001:4830:134:3::e]:36536) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyLxK-0007ti-KN; Sat, 30 Sep 2017 13:53:38 -0400 Received: from 84.94.185.246.cable.012.net.il ([84.94.185.246]:4250 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1dyLxJ-00034b-0I; Sat, 30 Sep 2017 13:53:38 -0400 Date: Sat, 30 Sep 2017 20:53:26 +0300 Message-Id: <834lrk3wfd.fsf@gnu.org> From: Eli Zaretskii To: Mark Oteiza In-reply-to: <20170930170758.zp2hdjw3il5fbier@logos.localdomain> (message from Mark Oteiza on Sat, 30 Sep 2017 13:07:58 -0400) Subject: Re: bug#22689: [PATCH] Add logcount References: <87h9h9pnof.fsf@udel.edu> <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> <838tgw42ol.fsf@gnu.org> <20170930160331.ibxxjh626jrlm4ef@logos.localdomain> <8360c040up.fsf@gnu.org> <20170930170758.zp2hdjw3il5fbier@logos.localdomain> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4830:134:3::e X-Spam-Score: -5.0 (-----) X-Debbugs-Envelope-To: 22689 Cc: 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Eli Zaretskii Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -5.0 (-----) > Date: Sat, 30 Sep 2017 13:07:58 -0400 > From: Mark Oteiza > Cc: 22689@debbugs.gnu.org > > Ok. Patch including this, Benjamin's catch, and documentation. Thanks. A minor comment on the docs: > +@defun logcount integer > +This function returns the population count of @var{integer}: the > +number of ones in the binary representation of @var{integer}. I would mention here the "Hamming weight" term (in @dfn) that is referenced in NEWS, and I would also add a few index entries: @cindex popcount @cindex Hamming weight @cindex counting set bits From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 14:18:15 2017 Received: (at 22689-done) by debbugs.gnu.org; 30 Sep 2017 18:18:15 +0000 Received: from localhost ([127.0.0.1]:41423 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyML9-0004Dl-GE for submit@debbugs.gnu.org; Sat, 30 Sep 2017 14:18:15 -0400 Received: from mail-qk0-f171.google.com ([209.85.220.171]:54704) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyML7-0004DX-UW for 22689-done@debbugs.gnu.org; Sat, 30 Sep 2017 14:18:14 -0400 Received: by mail-qk0-f171.google.com with SMTP id d70so2209992qkc.11 for <22689-done@debbugs.gnu.org>; Sat, 30 Sep 2017 11:18:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=FxyPUA2R2VF7vIXdQJe1fSbZprBnpCVVDTYaszQaxAk=; b=mhrgsVeGyseZLmkb0oYn2Vt9sEko4cbPTQr5dDls4dNkVUtWyyypgnKZmN0lrJyG5D Q8Y/XKK5P8t8NWrVUN6soKFRx/w4aio8gGrD7YSphQRuoMI9pwff5LEO1GGnpTn+SwIU ZZ2NHlUmoi6Km/G9kK20yO6GmXAPFm27IfiPCSAW3Y8Pk3Z+OCgIQrkXFZuRe4ULafpN WkNSGs+gezlzCtTIAI4hSIV/q89LZGqIWSda0H9hSq3o8B1Op3oQsjRzd2RWx/+rC8RW Xak4GSlwlMM6WF1Rqu1u/u3KKA4rJpuL8NgX2NQX8GPRjuRlUVLGGgCL3yx4C43yrXVB 3rlw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=FxyPUA2R2VF7vIXdQJe1fSbZprBnpCVVDTYaszQaxAk=; b=smnjtfWFvciwCGBRWOD23B+sVW8WnHPPmY7M9k1mdtOvwu0ID0FuvY0wKYSPlCYOPv sanTf/Aght9XYN9ifpox02IoXVUWvBpvz/ormc/WRUMzXZcPnjbrfwIk5+EypD2APxLo j6JnfTO3FnoAuwrfahRt1H0mpaNwlqEsGwO88G2jawUT5J5Lq7fh7wmDUFhRAGaPF4Td 6ZjH+jiJidUuOW0S23Zq57yKirxlyhepmUWRg3HIm/3RjKMklqrgZLtm19o5JZl2tR/t Go0/f3O1OV470Y5wpGc+DbA5wkL/MytyyG8rFXsGtn7qJuOOCwMWWLmLkxReP0XtQhzG vUsg== X-Gm-Message-State: AMCzsaV6GtVR22KOjQXGpWvF3ybefvDAsQdGeP0rShwu216pCeBfmQoq QO9vpBSAToNMXazOvx17rmECsvxhw1I= X-Google-Smtp-Source: AOwi7QDGdnTY7NZD21d4/SsEwB500xryoCkWqpn1p57b9jcBjkG3OBIYuWA386DgDCq5zGibiWJE0g== X-Received: by 10.55.5.14 with SMTP id 14mr3299422qkf.37.1506795488385; Sat, 30 Sep 2017 11:18:08 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id n4sm4340641qkf.49.2017.09.30.11.18.07 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 11:18:07 -0700 (PDT) Date: Sat, 30 Sep 2017 14:18:07 -0400 From: Mark Oteiza To: Eli Zaretskii Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930181807.4eviiyvlxchp4oph@logos.localdomain> References: <20170929174134.e6uxcr63dtyvd6f4@logos.localdomain> <83mv5c4dl0.fsf@gnu.org> <20170930131636.xe22lbwlea7yqelh@logos.localdomain> <83a81c478s.fsf@gnu.org> <20170930145525.kg2zh3jf5odx6g3s@logos.localdomain> <838tgw42ol.fsf@gnu.org> <20170930160331.ibxxjh626jrlm4ef@logos.localdomain> <8360c040up.fsf@gnu.org> <20170930170758.zp2hdjw3il5fbier@logos.localdomain> <834lrk3wfd.fsf@gnu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <834lrk3wfd.fsf@gnu.org> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: -2.8 (--) X-Debbugs-Envelope-To: 22689-done Cc: 22689-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.8 (--) On 30/09/17 at 08:53pm, Eli Zaretskii wrote: > > Date: Sat, 30 Sep 2017 13:07:58 -0400 > > From: Mark Oteiza > > Cc: 22689@debbugs.gnu.org > > > > Ok. Patch including this, Benjamin's catch, and documentation. > > Thanks. A minor comment on the docs: > > > +@defun logcount integer > > +This function returns the population count of @var{integer}: the > > +number of ones in the binary representation of @var{integer}. > > I would mention here the "Hamming weight" term (in @dfn) that is > referenced in NEWS, and I would also add a few index entries: > > @cindex popcount > @cindex Hamming weight > @cindex counting set bits Done, pushed as 185f3334. Thank you. From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 18:49:07 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 22:49:07 +0000 Received: from localhost ([127.0.0.1]:41583 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyQZH-0004wl-6S for submit@debbugs.gnu.org; Sat, 30 Sep 2017 18:49:07 -0400 Received: from zimbra.cs.ucla.edu ([131.179.128.68]:39720) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyQZF-0004wI-MT for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 18:49:06 -0400 Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id E35D316008A; Sat, 30 Sep 2017 15:48:59 -0700 (PDT) Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id 4dDNrD8PC3Ub; Sat, 30 Sep 2017 15:48:58 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 744A3160AEB; Sat, 30 Sep 2017 15:48:58 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id wvMU2ZZ24V3J; Sat, 30 Sep 2017 15:48:58 -0700 (PDT) Received: from [192.168.1.9] (unknown [47.154.18.85]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 4D24516008A; Sat, 30 Sep 2017 15:48:58 -0700 (PDT) To: Mark Oteiza From: Paul Eggert Subject: Re: bug#22689: [PATCH] Add logcount Organization: UCLA Computer Science Department Message-ID: <484ef24a-8fbe-6e9c-cdb4-ef7c4467ada9@cs.ucla.edu> Date: Sat, 30 Sep 2017 15:48:50 -0700 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------87573260DE112072A9A056BE" Content-Language: en-US X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 22689 Cc: Eli Zaretskii , 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.3 (--) This is a multi-part message in MIME format. --------------87573260DE112072A9A056BE Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable I looked at this patch after it landed in 'master'. Thanks for contributi= ng it. A couple of minor improvements. First, the implementation of logcount can= use=20 the count_one_bits functions already used by Emacs, rather than reinventi= ng that=20 wheel; these functions should be just as fast as __builtin_popcount etc. = when=20 using GCC. Second, logcount should count zero bits in negative numbers, f= or=20 compatibility with Common Lisp. I installed the attached two patches to=20 implement these improvements. --------------87573260DE112072A9A056BE Content-Type: text/x-patch; name="0001-Simplify-logcount-implementation.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="0001-Simplify-logcount-implementation.patch" =46rom 6fe5f5db496f5962e1504991bf77e2b7d23a681f Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sat, 30 Sep 2017 13:12:33 -0700 Subject: [PATCH 1/2] Simplify logcount implementation * src/data.c (HAVE_BUILTIN_POPCOUNTLL, logcount32, logcount64): Remove. (Flogcount): Simplify by using count_one_bits. --- src/data.c | 60 +++++++-------------------------------------------------= ---- 1 file changed, 7 insertions(+), 53 deletions(-) diff --git a/src/data.c b/src/data.c index b595e3fb1a..fd8cdd19aa 100644 --- a/src/data.c +++ b/src/data.c @@ -3069,64 +3069,18 @@ usage: (logxor &rest INTS-OR-MARKERS) */) return arith_driver (Alogxor, nargs, args); } =20 -#if GNUC_PREREQ (4, 1, 0) -#define HAVE_BUILTIN_POPCOUNTLL -#endif - -#ifndef HAVE_BUILTIN_POPCOUNTLL -static uint32_t -logcount32 (uint32_t b) -{ - b -=3D (b >> 1) & 0x55555555; - b =3D (b & 0x33333333) + ((b >> 2) & 0x33333333); - b =3D (b + (b >> 4)) & 0x0f0f0f0f; - return (b * 0x01010101) >> 24; -} - -static uint64_t -logcount64 (uint64_t b) -{ - b -=3D (b >> 1) & 0x5555555555555555ULL; - b =3D (b & 0x3333333333333333ULL) + ((b >> 2) & 0x3333333333333333ULL)= ; - b =3D (b + (b >> 4)) & 0x0f0f0f0f0f0f0f0fULL; - return (b * 0x0101010101010101ULL) >> 56; -} -#endif /* HAVE_BUILTIN_POPCOUNTLL */ - DEFUN ("logcount", Flogcount, Slogcount, 1, 1, 0, doc: /* Return population count of VALUE. If VALUE is negative, the count is of its two's complement representatio= n. */) - (register Lisp_Object value) + (Lisp_Object value) { - Lisp_Object res; - EMACS_UINT v; - CHECK_NUMBER (value); - - v =3D XUINT (value); -#ifdef HAVE_BUILTIN_POPCOUNTLL - if (v <=3D UINT_MAX) - XSETINT (res, __builtin_popcount (v)); - else if (v <=3D ULONG_MAX) - XSETINT (res, __builtin_popcountl (v)); - else if (v <=3D ULONG_LONG_MAX) - XSETINT (res, __builtin_popcountll (v)); -#else /* HAVE_BUILTIN_POPCOUNTLL */ - if (v <=3D UINT_MAX) - XSETINT (res, logcount32 (v)); - else if (v <=3D ULONG_MAX || v <=3D ULONG_LONG_MAX) - XSETINT (res, logcount64 (v)); -#endif /* HAVE_BUILTIN_POPCOUNTLL */ - else - { - unsigned int count; - for (count =3D 0; v; count++) - { - v &=3D v - 1; - } - XSETINT (res, count); - } - return res; + EMACS_UINT v =3D XUINT (value); + return make_number (EMACS_UINT_WIDTH <=3D UINT_WIDTH + ? count_one_bits (v) + : EMACS_UINT_WIDTH <=3D ULONG_WIDTH + ? count_one_bits_l (v) + : count_one_bits_ll (v)); } =20 static Lisp_Object --=20 2.13.5 --------------87573260DE112072A9A056BE Content-Type: text/x-patch; name="0002-Make-logcount-act-like-CL-on-negative-arg.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="0002-Make-logcount-act-like-CL-on-negative-arg.patch" =46rom 3b6d6b03383ac413fd0f25c4ae4fed1c780a3c29 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sat, 30 Sep 2017 15:36:52 -0700 Subject: [PATCH 2/2] Make logcount act like CL on negative arg Behaving like Common Lisp is less likely to lead to surprises, as it yields the same answers on 32- vs 64-bit machines. * doc/lispref/numbers.texi (Bitwise Operations): Document behavior on negative integers. * src/data.c (Flogcount): Behave like Common Lisp for negative arguments. * test/src/data-tests.el (data-tests-popcnt) (data-tests-logcount): Test negative args too. --- doc/lispref/numbers.texi | 7 ++++++- src/data.c | 6 ++++-- test/src/data-tests.el | 4 +++- 3 files changed, 13 insertions(+), 4 deletions(-) diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi index 5058063af4..be74b0c611 100644 --- a/doc/lispref/numbers.texi +++ b/doc/lispref/numbers.texi @@ -1113,9 +1113,14 @@ Bitwise Operations @defun logcount integer This function returns the @dfn{Hamming weight} of @var{integer}: the number of ones in the binary representation of @var{integer}. +If @var{integer} is negative, it returns the number of zero bits in +its two's complement binary representation. The result is always +nonnegative. =20 @example -(logcount 42) ; 42 =3D #b101010 +(logcount 43) ; 43 =3D #b101011 + @result{} 4 +(logcount -43) ; -43 =3D #b111...1010101 @result{} 3 @end example @end defun diff --git a/src/data.c b/src/data.c index fd8cdd19aa..2e7f3e017b 100644 --- a/src/data.c +++ b/src/data.c @@ -3071,11 +3071,13 @@ usage: (logxor &rest INTS-OR-MARKERS) */) =20 DEFUN ("logcount", Flogcount, Slogcount, 1, 1, 0, doc: /* Return population count of VALUE. -If VALUE is negative, the count is of its two's complement representatio= n. */) +This is the number of one bits in the two's complement representation +of VALUE. If VALUE is negative, return the number of zero bits in the +representation. */) (Lisp_Object value) { CHECK_NUMBER (value); - EMACS_UINT v =3D XUINT (value); + EMACS_INT v =3D XINT (value) < 0 ? -1 - XINT (value) : XINT (value); return make_number (EMACS_UINT_WIDTH <=3D UINT_WIDTH ? count_one_bits (v) : EMACS_UINT_WIDTH <=3D ULONG_WIDTH diff --git a/test/src/data-tests.el b/test/src/data-tests.el index d1154cc5c4..374d1689b9 100644 --- a/test/src/data-tests.el +++ b/test/src/data-tests.el @@ -109,12 +109,14 @@ =20 (defun data-tests-popcnt (byte) "Calculate the Hamming weight of BYTE." + (if (< byte 0) + (setq byte (lognot byte))) (setq byte (- byte (logand (lsh byte -1) #x55555555))) (setq byte (+ (logand byte #x33333333) (logand (lsh byte -2) #x3333333= 3))) (lsh (* (logand (+ byte (lsh byte -4)) #x0f0f0f0f) #x01010101) -24)) =20 (ert-deftest data-tests-logcount () - (should (cl-loop for n in (number-sequence 0 255) + (should (cl-loop for n in (number-sequence -255 255) always (=3D (logcount n) (data-tests-popcnt n)))) ;; https://oeis.org/A000120 (should (=3D 11 (logcount 9727))) --=20 2.13.5 --------------87573260DE112072A9A056BE-- From debbugs-submit-bounces@debbugs.gnu.org Sat Sep 30 19:22:43 2017 Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 23:22:43 +0000 Received: from localhost ([127.0.0.1]:41594 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyR5n-0005uJ-7w for submit@debbugs.gnu.org; Sat, 30 Sep 2017 19:22:43 -0400 Received: from mail-qt0-f178.google.com ([209.85.216.178]:45157) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyR5l-0005u0-2I for 22689@debbugs.gnu.org; Sat, 30 Sep 2017 19:22:41 -0400 Received: by mail-qt0-f178.google.com with SMTP id t46so3567543qtj.2 for <22689@debbugs.gnu.org>; Sat, 30 Sep 2017 16:22:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=GxM+hFMl2LfrXWHVcagT44711vXCYlLQ1QMt8d0EZ10=; b=Rzzlk6toIsPjkzBiszV1vUPqHAXekaWCaQgOHb7hyNF26Y99+3B+JhD9O/25qSivN4 lNtiu+e/o+80V69tPekYc/0Elm5P9Ln1qzOcq43xvofInvf4eVUV3vO16Q/kZG9VZAL6 N+EGTvInOoALWUPXjiVJBA2YEST5hAfAH0FZus6O3qGhcmhcHXCwidzf2x8NnoHZWm6I DVoUi0XMXgju7fPVxxs30uGNUzdcpo1+EHr1asF9tOvL4xR/GN4wMTiFqGfxtlsJyae7 a20rcYszxzL3nzEZ6E99ri19TOoHh7KyY20jN3XUd1GLM18zKTnRpKi3FUNAdBktlaHn oLpg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=GxM+hFMl2LfrXWHVcagT44711vXCYlLQ1QMt8d0EZ10=; b=YBWtdfOXU/XuacWM2OsBKcP/PHeleKm8uZLEDXuCWEMOiaMCxq7duV1yKIk/Xp2smx SeFRveXA7ymFBpUV8cH5SXFGL7zaON3HfK+9lZPqF2agaWz33+khUcdTb67GGHzmPtHO GUBhbKlQwqv2oNJDSCYJqM7+mJWjpKRvYxA5sIYqP9vOOXSzi9zdibV71WTgwXNXG7IU sRP4ycDd6Yc6dYnyhjNGI9rZm1WYXUshSLuKKKpMeW7crbxUSE8GzYmhVD0sFCza2r+a ijivHFjomuB2FoLf32IXSnrKTyOiHVuweQKhQinR57fAVRJa1Qn7UCuJknsNYOq0SglM +jJQ== X-Gm-Message-State: AMCzsaUK9gVg3aF5UVVCVSPYMh9CKNOkGOo5MaG9JDKNcIKBIYdX3gmm WjPxtMEchOdh8uxGzHeLvwe55w== X-Google-Smtp-Source: AOwi7QBlwriKreu3LGaFVUu04te3sDZp7c89inhXb+9l0Kb+ZllW+fkObwOf4hno55fB3vzXklM27A== X-Received: by 10.200.27.28 with SMTP id y28mr13008472qtj.297.1506813755631; Sat, 30 Sep 2017 16:22:35 -0700 (PDT) Received: from logos.localdomain (pool-173-67-36-61.bltmmd.fios.verizon.net. [173.67.36.61]) by smtp.gmail.com with ESMTPSA id y68sm4630015qkd.87.2017.09.30.16.22.34 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 30 Sep 2017 16:22:34 -0700 (PDT) Date: Sat, 30 Sep 2017 19:22:33 -0400 From: Mark Oteiza To: Paul Eggert Subject: Re: bug#22689: [PATCH] Add logcount Message-ID: <20170930232233.3dtcrcijapknju45@logos.localdomain> References: <484ef24a-8fbe-6e9c-cdb4-ef7c4467ada9@cs.ucla.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <484ef24a-8fbe-6e9c-cdb4-ef7c4467ada9@cs.ucla.edu> User-Agent: NeoMutt/20170912-48-0df7d3-dirty X-Spam-Score: -0.2 (/) X-Debbugs-Envelope-To: 22689 Cc: Eli Zaretskii , 22689@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.2 (/) On 30/09/17 at 03:48pm, Paul Eggert wrote: > I looked at this patch after it landed in 'master'. Thanks for contributing it. > > A couple of minor improvements. First, the implementation of logcount can > use the count_one_bits functions already used by Emacs, rather than > reinventing that wheel; these functions should be just as fast as > __builtin_popcount etc. when using GCC. Second, logcount should count zero > bits in negative numbers, for compatibility with Common Lisp. I installed > the attached two patches to implement these improvements. Thank you for the improvements--I was not aware of count-one-bits.h but am pleasantly surprised. From unknown Fri Aug 15 12:52:21 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Sun, 29 Oct 2017 11:24:06 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator