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 10:55:25 -0400 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> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: blaine.gmane.org 1506783376 12463 195.159.176.226 (30 Sep 2017 14:56:16 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 30 Sep 2017 14:56:16 +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 16:56: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 1dyJBX-0002MM-Fh for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Sep 2017 16:56:07 +0200 Original-Received: from localhost ([::1]:39540 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyJBa-0005LT-Rx for geb-bug-gnu-emacs@m.gmane.org; Sat, 30 Sep 2017 10:56:10 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35925) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dyJBV-0005LL-0B for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 10:56:06 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dyJBS-000671-8z for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 10:56:05 -0400 Original-Received: from debbugs.gnu.org ([208.118.235.43]:60846) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dyJBS-00065p-4T for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 10:56:02 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1dyJBR-0005fC-NH for bug-gnu-emacs@gnu.org; Sat, 30 Sep 2017 10:56:01 -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 14:56: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.150678333921736 (code B ref 22689); Sat, 30 Sep 2017 14:56:01 +0000 Original-Received: (at 22689) by debbugs.gnu.org; 30 Sep 2017 14:55:39 +0000 Original-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 Original-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 Original-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) 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 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) Content-Disposition: inline In-Reply-To: <83a81c478s.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:137689 Archived-At: 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.