From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Mark Oteiza Newsgroups: gmane.emacs.bugs Subject: bug#22689: [PATCH] Add logcount Date: Sat, 30 Sep 2017 13:07:58 -0400 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> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: blaine.gmane.org 1506791353 21567 195.159.176.226 (30 Sep 2017 17:09:13 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 30 Sep 2017 17:09:13 +0000 (UTC) User-Agent: NeoMutt/20170912-48-0df7d3-dirty Cc: 22689@debbugs.gnu.org To: Eli Zaretskii Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Sat Sep 30 19:09:07 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 1dyLGD-0004pq-Fq for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Sep 2017 19:09:05 +0200 Original-Received: from localhost ([::1]:39885 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyLGK-0007Gu-Ka for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Sep 2017 13:09:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45805) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyLGD-0007Gn-NK for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 13:09:07 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyLGA-0003oR-D0 for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 13:09:05 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:60927) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dyLGA-0003oD-9S for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 13:09:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1dyLGA-0000YY-0N for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 13:09:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Mark Oteiza Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sat, 30 Sep 2017 17:09: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.15067912882073 (code B ref 22689); Sat, 30 Sep 2017 17:09:01 +0000 Original-Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 17:08:08 +0000 Original-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 Original-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 Original-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) Original-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) Content-Disposition: inline In-Reply-To: <8360c040up.fsf@gnu.org> 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:137696 Archived-At: 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.