From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.bugs Subject: bug#22689: [PATCH] Add logcount Date: Sat, 30 Sep 2017 15:48:50 -0700 Organization: UCLA Computer Science Department Message-ID: <484ef24a-8fbe-6e9c-cdb4-ef7c4467ada9@cs.ucla.edu> References: <87h9h9pnof.fsf@udel.edu> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------87573260DE112072A9A056BE" X-Trace: blaine.gmane.org 1506811818 32231 195.159.176.226 (30 Sep 2017 22:50:18 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 30 Sep 2017 22:50:18 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.3.0 Cc: 22689@debbugs.gnu.org To: Mark Oteiza Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sun Oct 01 00:50:10 2017 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dyQaH-0007W2-O3 for geb-bug-gnu-emacs@m.gmane.org; Sun, 01 Oct 2017 00:50:10 +0200 Original-Received: from localhost ([::1]:40575 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyQaP-0000Ti-2R for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Sep 2017 18:50:17 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:52841) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyQaC-0000SG-V4 for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 18:50:06 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyQaA-0002Ol-BL for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 18:50:05 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:32902) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dyQaA-0002ON-6G for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 18:50:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1dyQa9-0004yP-Ld for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 18:50:01 -0400 X-Loop: help-debbugs@gnu.org In-Reply-To: <87h9h9pnof.fsf@udel.edu> Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Sep 2017 22:50:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 22689 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 22689-submit@debbugs.gnu.org id=B22689.150681174719023 (code B ref 22689); Sat, 30 Sep 2017 22:50:01 +0000 Original-Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 22:49:07 +0000 Original-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 Original-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 Original-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) Original-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) Original-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 Original-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) Original-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) Content-Language: en-US X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.org gmane.emacs.bugs:137719 Archived-At: 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--