From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.bugs Subject: bug#15550: Improve support for popcount and counting trailing zeros. Date: Mon, 07 Oct 2013 00:46:32 -0700 Organization: UCLA Computer Science Department Message-ID: <525266D8.2040102@cs.ucla.edu> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1381132035 22439 80.91.229.3 (7 Oct 2013 07:47:15 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 7 Oct 2013 07:47:15 +0000 (UTC) To: 15550@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Mon Oct 07 09:47:18 2013 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VT5XA-0003Ya-R6 for geb-bug-gnu-emacs@m.gmane.org; Mon, 07 Oct 2013 09:47:17 +0200 Original-Received: from localhost ([::1]:57933 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VT5XA-0007eW-Cl for geb-bug-gnu-emacs@m.gmane.org; Mon, 07 Oct 2013 03:47:16 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:50067) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VT5X2-0007dH-6I for bug-gnu-emacs@gnu.org; Mon, 07 Oct 2013 03:47:12 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VT5Wx-0002UT-Hu for bug-gnu-emacs@gnu.org; Mon, 07 Oct 2013 03:47:08 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:50934) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VT5Wx-0002UM-Du for bug-gnu-emacs@gnu.org; Mon, 07 Oct 2013 03:47:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1VT5Ww-0007no-Kp for bug-gnu-emacs@gnu.org; Mon, 07 Oct 2013 03:47:03 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Paul Eggert Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 07 Oct 2013 07:47:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 15550 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-gnu-emacs Original-Received: via spool by submit@debbugs.gnu.org id=B.138113201729979 (code B ref -1); Mon, 07 Oct 2013 07:47:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 7 Oct 2013 07:46:57 +0000 Original-Received: from localhost ([127.0.0.1]:59227 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VT5Wo-0007nQ-M0 for submit@debbugs.gnu.org; Mon, 07 Oct 2013 03:46:56 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:48274) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1VT5Wk-0007nG-6W for submit@debbugs.gnu.org; Mon, 07 Oct 2013 03:46:52 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VT5Wf-0002Se-Bs for submit@debbugs.gnu.org; Mon, 07 Oct 2013 03:46:50 -0400 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:57663) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VT5Wf-0002Sa-81 for submit@debbugs.gnu.org; Mon, 07 Oct 2013 03:46:45 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49966) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VT5Wa-0007bm-Of for bug-gnu-emacs@gnu.org; Mon, 07 Oct 2013 03:46:45 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VT5WW-0002Rd-96 for bug-gnu-emacs@gnu.org; Mon, 07 Oct 2013 03:46:40 -0400 Original-Received: from smtp.cs.ucla.edu ([131.179.128.62]:43297) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VT5WV-0002RP-KZ; Mon, 07 Oct 2013 03:46:36 -0400 Original-Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id EF960A60007; Mon, 7 Oct 2013 00:46:34 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Original-Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id qC1WqX-2MhP0; Mon, 7 Oct 2013 00:46:33 -0700 (PDT) Original-Received: from [192.168.1.9] (pool-108-0-233-62.lsanca.fios.verizon.net [108.0.233.62]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id D1BB0A60008; Mon, 7 Oct 2013 00:46:32 -0700 (PDT) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 X-Enigmail-Version: 1.5.2 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.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-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:78979 Archived-At: I'd like to install this patch soon. Most of it is generated automatically from admin/merge-gnulib. I'm CC'ing this to Eli to give him a heads-up about the Microsoft-related side of this. I assume that nt/gnulib.mk needs to be edited at some point, but that's better done by someone with Windows expertise. =3D=3D=3D modified file 'ChangeLog' --- ChangeLog 2013-10-04 07:36:22 +0000 +++ ChangeLog 2013-10-07 07:36:08 +0000 @@ -1,3 +1,15 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros. + Do this by using the Gnulib modules for this. + This should generate faster code on non-GCC, non-MSC platforms, + and make the code a bit more portable, at least in theory. + * lib/count-one-bits.c, lib/count-one-bits.h: + * lib/count-trailing-zeros.c, lib/count-trailing-zeros.h: + * m4/count-one-bits.m4, m4/count-trailing-zeros.m4: + New files, copied from gnulib. + * lib/gnulib.mk, m4/gnulib-comp.m4: Regenerate. + 2013-10-04 Paul Eggert =20 Use hardware insns for byteswapping on glibc hosts that support it. =3D=3D=3D modified file 'admin/ChangeLog' --- admin/ChangeLog 2013-10-04 07:36:22 +0000 +++ admin/ChangeLog 2013-10-07 07:36:08 +0000 @@ -1,3 +1,9 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros. + * merge-gnulib (GNULIB_MODULES): Add count-one-bits + and count-trailing-zeros. + 2013-10-04 Paul Eggert =20 Use hardware support for byteswapping on glibc x86 etc. =3D=3D=3D modified file 'admin/merge-gnulib' --- admin/merge-gnulib 2013-10-04 07:36:22 +0000 +++ admin/merge-gnulib 2013-10-07 07:36:08 +0000 @@ -27,7 +27,8 @@ =20 GNULIB_MODULES=3D' alloca-opt byteswap c-ctype c-strcase - careadlinkat close-stream crypto/md5 crypto/sha1 crypto/sha256 crypto/= sha512 + careadlinkat close-stream count-one-bits count-trailing-zeros + crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 dtoastr dtotimespec dup2 environ execinfo faccessat fcntl fcntl-h fdatasync fdopendir filemode fstatat fsync getloadavg getopt-gnu gettime gettimeofday =3D=3D=3D added file 'lib/count-one-bits.c' --- lib/count-one-bits.c 1970-01-01 00:00:00 +0000 +++ lib/count-one-bits.c 2013-10-07 07:36:08 +0000 @@ -0,0 +1,7 @@ +#include +#define COUNT_ONE_BITS_INLINE _GL_EXTERN_INLINE +#include "count-one-bits.h" + +#if 1500 <=3D _MSC_VER && (defined _M_IX86 || defined _M_X64) +int popcount_support =3D -1; +#endif =3D=3D=3D added file 'lib/count-one-bits.h' --- lib/count-one-bits.h 1970-01-01 00:00:00 +0000 +++ lib/count-one-bits.h 2013-10-07 07:36:08 +0000 @@ -0,0 +1,136 @@ +/* count-one-bits.h -- counts the number of 1-bits in a word. + Copyright (C) 2007-2013 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see .= */ + +/* Written by Ben Pfaff. */ + +#ifndef COUNT_ONE_BITS_H +#define COUNT_ONE_BITS_H 1 + +#include +#include + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef COUNT_ONE_BITS_INLINE +# define COUNT_ONE_BITS_INLINE _GL_INLINE +#endif + +/* Expand to code that computes the number of 1-bits of the local + variable 'x' of type TYPE (an unsigned integer type) and return it + from the current function. */ +#define COUNT_ONE_BITS_GENERIC(TYPE) \ + do = \ + { = \ + int count =3D 0; = \ + int bits; = \ + for (bits =3D 0; bits < sizeof (TYPE) * CHAR_BIT; bits +=3D 32) = \ + { = \ + count +=3D count_one_bits_32 (x); = \ + x =3D x >> 31 >> 1; = \ + } = \ + return count; = \ + } = \ + while (0) + +/* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTI= N, + expand to code that computes the number of 1-bits of the local + variable 'x' of type TYPE (an unsigned integer type) and return it + from the current function. */ +#if __GNUC__ > 3 || (__GNUC__ =3D=3D 3 && __GNUC_MINOR__ >=3D 4) +# define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) return BUILTIN (x) +#else + +/* Compute and return the number of 1-bits set in the least + significant 32 bits of X. */ +COUNT_ONE_BITS_INLINE int +count_one_bits_32 (unsigned int x) +{ + x =3D ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U); + x =3D ((x & 0xccccccccU) >> 2) + (x & 0x33333333U); + x =3D (x >> 16) + (x & 0xffff); + x =3D ((x & 0xf0f0) >> 4) + (x & 0x0f0f); + return (x >> 8) + (x & 0x00ff); +} + +# if 1500 <=3D _MSC_VER && (defined _M_IX86 || defined _M_X64) + +/* While gcc falls back to its own generic code if the machine + on which it's running doesn't support popcount, with Microsoft's + compiler we need to detect and fallback ourselves. */ +# pragma intrinsic __cpuid +# pragma intrinsic __popcnt +# pragma intrinsic __popcnt64 + +/* Return nonzero if popcount is supported. */ + +/* 1 if supported, 0 if not supported, -1 if unknown. */ +extern int popcount_support; + +COUNT_ONE_BITS_INLINE int +popcount_supported (void) +{ + if (popcount_support < 0) + { + int cpu_info[4]; + __cpuid (cpu_info, 1); + popcount_support =3D (cpu_info[2] >> 23) & 1; /* See MSDN. */ + } + return popcount_support; +} + +# define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) \ + do \ + { \ + if (popcount_supported ()) \ + return MSC_BUILTIN (x); \ + else \ + COUNT_ONE_BITS_GENERIC (TYPE); \ + } \ + while (0) +# else +# define COUNT_ONE_BITS(BUILTIN, MSC_BUILTIN, TYPE) \ + COUNT_ONE_BITS_GENERIC (TYPE) +# endif +#endif + +/* Compute and return the number of 1-bits set in X. */ +COUNT_ONE_BITS_INLINE int +count_one_bits (unsigned int x) +{ + COUNT_ONE_BITS (__builtin_popcount, __popcnt, unsigned int); +} + +/* Compute and return the number of 1-bits set in X. */ +COUNT_ONE_BITS_INLINE int +count_one_bits_l (unsigned long int x) +{ + COUNT_ONE_BITS (__builtin_popcountl, __popcnt, unsigned long int); +} + +#if HAVE_UNSIGNED_LONG_LONG_INT +/* Compute and return the number of 1-bits set in X. */ +COUNT_ONE_BITS_INLINE int +count_one_bits_ll (unsigned long long int x) +{ + COUNT_ONE_BITS (__builtin_popcountll, __popcnt64, unsigned long long i= nt); +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* COUNT_ONE_BITS_H */ =3D=3D=3D added file 'lib/count-trailing-zeros.c' --- lib/count-trailing-zeros.c 1970-01-01 00:00:00 +0000 +++ lib/count-trailing-zeros.c 2013-10-07 07:36:08 +0000 @@ -0,0 +1,3 @@ +#include +#define COUNT_TRAILING_ZEROS_INLINE _GL_EXTERN_INLINE +#include "count-trailing-zeros.h" =3D=3D=3D added file 'lib/count-trailing-zeros.h' --- lib/count-trailing-zeros.h 1970-01-01 00:00:00 +0000 +++ lib/count-trailing-zeros.h 2013-10-07 07:36:08 +0000 @@ -0,0 +1,106 @@ +/* count-trailing-zeros.h -- counts the number of trailing 0 bits in a w= ord. + Copyright 2013 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see .= */ + +/* Written by Paul Eggert. */ + +#ifndef COUNT_TRAILING_ZEROS_H +#define COUNT_TRAILING_ZEROS_H 1 + +#include +#include + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef COUNT_TRAILING_ZEROS_INLINE +# define COUNT_TRAILING_ZEROS_INLINE _GL_INLINE +#endif + +/* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTI= N, + expand to code that computes the number of trailing zeros of the loca= l + variable 'x' of type TYPE (an unsigned integer type) and return it + from the current function. */ +#if __GNUC__ > 3 || (__GNUC__ =3D=3D 3 && __GNUC_MINOR__ >=3D 4) +# define COUNT_TRAILING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) = \ + return x ? BUILTIN (x) : CHAR_BIT * sizeof x; +#elif _MSC_VER +# pragma intrinsic _BitScanForward +# pragma intrinsic _BitScanForward64 +# define COUNT_TRAILING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) = \ + do = \ + { = \ + unsigned long result; = \ + return MSC_BUILTIN (&result, x) ? result : CHAR_BIT * sizeof x; = \ + } = \ + while (0) +#else +# define COUNT_TRAILING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) = \ + do = \ + { = \ + int count =3D 0; = \ + if (! x) = \ + return CHAR_BIT * sizeof x; = \ + for (count =3D 0; = \ + (count < CHAR_BIT * sizeof x - 32 = \ + && ! (x & 0xffffffffU)); = \ + count +=3D 32) = \ + x =3D x >> 31 >> 1; = \ + return count + count_trailing_zeros_32 (x); = \ + } = \ + while (0) + +/* Compute and return the number of trailing zeros in the least + significant 32 bits of X. One of these bits must be nonzero. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros_32 (unsigned int x) +{ + /* http://graphics.stanford.edu/~seander/bithacks.html */ + static const char de_Bruijn_lookup[32] =3D { + 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, + 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 + }; + return de_Bruijn_lookup[(((x & -x) * 0x077cb531U) & 0xffffffffU) >> 27= ]; +} +#endif + +/* Compute and return the number of trailing zeros in X. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros (unsigned int x) +{ + COUNT_TRAILING_ZEROS (__builtin_ctz, _BitScanForward, unsigned int); +} + +/* Compute and return the number of trailing zeros in X. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros_l (unsigned long int x) +{ + COUNT_TRAILING_ZEROS (__builtin_ctzl, _BitScanForward, unsigned long i= nt); +} + +#if HAVE_UNSIGNED_LONG_LONG_INT +/* Compute and return the number of trailing zeros in X. */ +COUNT_TRAILING_ZEROS_INLINE int +count_trailing_zeros_ll (unsigned long long int x) +{ + COUNT_TRAILING_ZEROS (__builtin_ctzll, _BitScanForward64, + unsigned long long int); +} +#endif + +_GL_INLINE_HEADER_END + +#endif =3D=3D=3D modified file 'lib/gnulib.mk' --- lib/gnulib.mk 2013-10-04 07:36:22 +0000 +++ lib/gnulib.mk 2013-10-07 07:36:08 +0000 @@ -21,7 +21,7 @@ # the same distribution terms as the rest of that program. # # Generated by gnulib-tool. -# Reproduce by: gnulib-tool --import --dir=3D. --lib=3Dlibgnu --source-b= ase=3Dlib --m4-base=3Dm4 --doc-base=3Ddoc --tests-base=3Dtests --aux-dir=3D= build-aux --avoid=3Dclose --avoid=3Ddup --avoid=3Dfchdir --avoid=3Dfstat = --avoid=3Dmalloc-posix --avoid=3Dmsvc-inval --avoid=3Dmsvc-nothrow --avoi= d=3Dopen --avoid=3Dopenat-die --avoid=3Dopendir --avoid=3Draise --avoid=3D= save-cwd --avoid=3Dselect --avoid=3Dsigprocmask --avoid=3Dsys_types --avo= id=3Dthreadlib --makefile-name=3Dgnulib.mk --conditional-dependencies --n= o-libtool --macro-prefix=3Dgl --no-vc-files alloca-opt byteswap c-ctype c= -strcase careadlinkat close-stream crypto/md5 crypto/sha1 crypto/sha256 c= rypto/sha512 dtoastr dtotimespec dup2 environ execinfo faccessat fcntl fc= ntl-h fdatasync fdopendir filemode fstatat fsync getloadavg getopt-gnu ge= ttime gettimeofday intprops largefile lstat manywarnings memrchr mkostemp= mktime pipe2 pselect pthread_sigmask putenv qacl readlink readlinkat sig= 2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax s= trtoumax symlin k sys_sta t sys_time time timer-time timespec-add timespec-sub unsetenv utimens war= nings +# Reproduce by: gnulib-tool --import --dir=3D. --lib=3Dlibgnu --source-b= ase=3Dlib --m4-base=3Dm4 --doc-base=3Ddoc --tests-base=3Dtests --aux-dir=3D= build-aux --avoid=3Dclose --avoid=3Ddup --avoid=3Dfchdir --avoid=3Dfstat = --avoid=3Dmalloc-posix --avoid=3Dmsvc-inval --avoid=3Dmsvc-nothrow --avoi= d=3Dopen --avoid=3Dopenat-die --avoid=3Dopendir --avoid=3Draise --avoid=3D= save-cwd --avoid=3Dselect --avoid=3Dsigprocmask --avoid=3Dsys_types --avo= id=3Dthreadlib --makefile-name=3Dgnulib.mk --conditional-dependencies --n= o-libtool --macro-prefix=3Dgl --no-vc-files alloca-opt byteswap c-ctype c= -strcase careadlinkat close-stream count-one-bits count-trailing-zeros cr= ypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 dtoastr dtotimespec dup2= environ execinfo faccessat fcntl fcntl-h fdatasync fdopendir filemode fs= tatat fsync getloadavg getopt-gnu gettime gettimeofday intprops largefile= lstat manywarnings memrchr mkostemp mktime pipe2 pselect pthread_sigmask= putenv qacl readlink readlinkat sig2str socklen stat-time stdalign stdar= g stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-a= dd timespec-sub unsetenv utimens warnings =20 =20 MOSTLYCLEANFILES +=3D core *.stackdump @@ -132,6 +132,22 @@ =20 ## end gnulib module close-stream =20 +## begin gnulib module count-one-bits + +libgnu_a_SOURCES +=3D count-one-bits.c + +EXTRA_DIST +=3D count-one-bits.h + +## end gnulib module count-one-bits + +## begin gnulib module count-trailing-zeros + +libgnu_a_SOURCES +=3D count-trailing-zeros.c + +EXTRA_DIST +=3D count-trailing-zeros.h + +## end gnulib module count-trailing-zeros + ## begin gnulib module crypto/md5 =20 libgnu_a_SOURCES +=3D md5.c =3D=3D=3D added file 'm4/count-one-bits.m4' --- m4/count-one-bits.m4 1970-01-01 00:00:00 +0000 +++ m4/count-one-bits.m4 2013-10-07 07:36:08 +0000 @@ -0,0 +1,12 @@ +# count-one-bits.m4 serial 3 +dnl Copyright (C) 2007, 2009-2013 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +AC_DEFUN([gl_COUNT_ONE_BITS], +[ + dnl We don't need (and can't compile) count_one_bits_ll + dnl unless the type 'unsigned long long int' exists. + AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) +]) =3D=3D=3D added file 'm4/count-trailing-zeros.m4' --- m4/count-trailing-zeros.m4 1970-01-01 00:00:00 +0000 +++ m4/count-trailing-zeros.m4 2013-10-07 07:36:08 +0000 @@ -0,0 +1,12 @@ +# count-trailing-zeros.m4 +dnl Copyright (C) 2013 Free Software Foundation, Inc. +dnl This file is free software; the Free Software Foundation +dnl gives unlimited permission to copy and/or distribute it, +dnl with or without modifications, as long as this notice is preserved. + +AC_DEFUN([gl_COUNT_TRAILING_ZEROS], +[ + dnl We don't need (and can't compile) count_trailing_zeros_ll + dnl unless the type 'unsigned long long int' exists. + AC_REQUIRE([AC_TYPE_UNSIGNED_LONG_LONG_INT]) +]) =3D=3D=3D modified file 'm4/gnulib-comp.m4' --- m4/gnulib-comp.m4 2013-10-04 07:36:22 +0000 +++ m4/gnulib-comp.m4 2013-10-07 07:36:08 +0000 @@ -48,6 +48,8 @@ # Code from module careadlinkat: # Code from module clock-time: # Code from module close-stream: + # Code from module count-one-bits: + # Code from module count-trailing-zeros: # Code from module crypto/md5: # Code from module crypto/sha1: # Code from module crypto/sha256: @@ -175,6 +177,8 @@ gl_CLOCK_TIME gl_CLOSE_STREAM gl_MODULE_INDICATOR([close-stream]) + gl_COUNT_ONE_BITS + gl_COUNT_TRAILING_ZEROS gl_MD5 gl_SHA1 gl_SHA256 @@ -806,6 +810,10 @@ lib/careadlinkat.h lib/close-stream.c lib/close-stream.h + lib/count-one-bits.c + lib/count-one-bits.h + lib/count-trailing-zeros.c + lib/count-trailing-zeros.h lib/dirent.in.h lib/dosname.h lib/dtoastr.c @@ -919,6 +927,8 @@ m4/c-strtod.m4 m4/clock_time.m4 m4/close-stream.m4 + m4/count-one-bits.m4 + m4/count-trailing-zeros.m4 m4/dirent_h.m4 m4/dup2.m4 m4/environ.m4 =3D=3D=3D modified file 'src/ChangeLog' --- src/ChangeLog 2013-10-06 15:59:11 +0000 +++ src/ChangeLog 2013-10-07 07:36:08 +0000 @@ -1,3 +1,22 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros. + * data.c: Include , . + (USE_MSC_POPCOUNT, POPCOUNT_STATIC_INLINE) + (NEED_GENERIC_POPCOUNT, popcount_size_t_generic) + (popcount_size_t_msc, popcount_size_t_gcc): + Remove; now done by Gnulib. + (popcount_size_t): Now a macro that defers to Gnulib. + (count_trailing_zero_bits): Return int, for consistency with + Gnulib and because Emacs prefers signed to unsigned int. + Don't assume that size_t is either unsigned int or unsigned long + or unsigned long long. + (size_t_to_host_endian): Do not assume that size_t is either + exactly 32 or exactly 64 bits wide. + * lisp.h (BITS_PER_SIZE_T): Define consistently with BITS_PER_LONG + etc., so that it's now an enum constant, not a macro. + No need to assume that it's either 32 or 64. + 2013-10-06 Jan Dj=C3=A4rv =20 * nsterm.m (ns_update_begin): If native fullscreen and no toolbar, =3D=3D=3D modified file 'src/data.c' --- src/data.c 2013-10-04 07:36:22 +0000 +++ src/data.c 2013-10-07 07:36:08 +0000 @@ -22,6 +22,8 @@ #include =20 #include +#include +#include #include =20 #include "lisp.h" @@ -2971,107 +2973,15 @@ return (((size_t) 1) << (nr_bits % BITS_PER_SIZE_T)) - 1; } =20 -#if _MSC_VER >=3D 1500 && (defined _M_IX86 || defined _M_X64) -# define USE_MSC_POPCOUNT -# define POPCOUNT_STATIC_INLINE static inline -#elif __GNUC__ > 3 || (__GNUC__ =3D=3D 3 && __GNUC_MINOR__ >=3D 4) -# define USE_GCC_POPCOUNT -# if 199901L <=3D __STDC_VERSION__ || !__STRICT_ANSI__ -# define POPCOUNT_STATIC_INLINE static inline -# endif -#else -# define NEED_GENERIC_POPCOUNT -#endif -#ifndef POPCOUNT_STATIC_INLINE -# define POPCOUNT_STATIC_INLINE static -#endif - -#ifdef USE_MSC_POPCOUNT -# define NEED_GENERIC_POPCOUNT -#endif - -#ifdef NEED_GENERIC_POPCOUNT -POPCOUNT_STATIC_INLINE unsigned int -popcount_size_t_generic (size_t val) -{ - unsigned short j; - unsigned int count =3D 0; - - for (j =3D 0; j < BITS_PER_SIZE_T; ++j) - count +=3D !!((((size_t) 1) << j) & val); - - return count; -} -#endif - -#ifdef USE_MSC_POPCOUNT -POPCOUNT_STATIC_INLINE unsigned int -popcount_size_t_msc (size_t val) -{ - unsigned int count; - -#pragma intrinsic __cpuid - /* While gcc falls back to its own generic code if the machine on - which it's running doesn't support popcount, we need to perform the - detection and fallback ourselves when compiling with Microsoft's - compiler. */ - - static enum { - popcount_unknown_support, - popcount_use_generic, - popcount_use_intrinsic - } popcount_state; - - if (popcount_state =3D=3D popcount_unknown_support) - { - int cpu_info[4]; - __cpuid (cpu_info, 1); - if (cpu_info[2] & (1<<23)) /* See MSDN. */ - popcount_state =3D popcount_use_intrinsic; - else - popcount_state =3D popcount_use_generic; - } - - if (popcount_state =3D=3D popcount_use_intrinsic) - { -# if BITS_PER_SIZE_T =3D=3D 64 -# pragma intrinsic __popcnt64 - count =3D __popcnt64 (val); -# else -# pragma intrinsic __popcnt - count =3D __popcnt (val); -# endif - } - else - count =3D popcount_size_t_generic (val); - - return count; -} -#endif /* USE_MSC_POPCOUNT */ - -#ifdef USE_GCC_POPCOUNT -POPCOUNT_STATIC_INLINE unsigned int -popcount_size_t_gcc (size_t val) -{ -# if BITS_PER_SIZE_T =3D=3D 64 - return __builtin_popcountll (val); -# else - return __builtin_popcount (val); -# endif -} -#endif /* USE_GCC_POPCOUNT */ - -POPCOUNT_STATIC_INLINE unsigned int -popcount_size_t (size_t val) -{ -#if defined USE_MSC_POPCOUNT - return popcount_size_t_msc (val); -#elif defined USE_GCC_POPCOUNT - return popcount_size_t_gcc (val); -#else - return popcount_size_t_generic (val); -#endif -} +#if SIZE_MAX <=3D UINT_MAX +# define popcount_size_t count_one_bits +#elif SIZE_MAX <=3D ULONG_MAX +# define popcount_size_t count_one_bits_l +#elif SIZE_MAX <=3D ULLONG_MAX +# define popcount_size_t count_one_bits_ll +#else +# error "size_t wider than long long? Please file a bug report." +#endif =20 enum bool_vector_op { bool_vector_exclusive_or, bool_vector_union, @@ -3143,55 +3053,54 @@ =20 /* Compute the number of trailing zero bits in val. If val is zero, return the number of bits in val. */ -static unsigned int +static int count_trailing_zero_bits (size_t val) { + if (SIZE_MAX =3D=3D UINT_MAX) + return count_trailing_zeros (val); + if (SIZE_MAX =3D=3D ULONG_MAX) + return count_trailing_zeros_l (val); +# if HAVE_UNSIGNED_LONG_LONG_INT + if (SIZE_MAX =3D=3D ULLONG_MAX) + return count_trailing_zeros_ll (val); +# endif + + /* The rest of this code is for the unlikely platform where size_t dif= fers + in width from unsigned int, unsigned long, and unsigned long long. = */ if (val =3D=3D 0) return CHAR_BIT * sizeof (val); - -#if defined USE_GCC_POPCOUNT && BITS_PER_SIZE_T =3D=3D 64 - return __builtin_ctzll (val); -#elif defined USE_GCC_POPCOUNT && BITS_PER_SIZE_T =3D=3D 32 - return __builtin_ctz (val); -#elif _MSC_VER && BITS_PER_SIZE_T =3D=3D 64 -# pragma intrinsic _BitScanForward64 - { - /* No support test needed: support since 386. */ - unsigned long result; - _BitScanForward64 (&result, val); - return (unsigned int) result; - } -#elif _MSC_VER && BITS_PER_SIZE_T =3D=3D 32 -# pragma intrinsic _BitScanForward - { - /* No support test needed: support since 386. */ - unsigned long result; - _BitScanForward (&result, val); - return (unsigned int) result; - } -#else - { - unsigned int count; - count =3D 0; - for (val =3D ~val; val & 1; val >>=3D 1) - ++count; - - return count; - } -#endif + if (SIZE_MAX <=3D UINT_MAX) + return count_trailing_zeros (val); + if (SIZE_MAX <=3D ULONG_MAX) + return count_trailing_zeros_l (val); + { +# if HAVE_UNSIGNED_LONG_LONG_INT + verify (SIZE_MAX <=3D ULLONG_MAX); + return count_trailing_zeros_ll (val); +# else + verify (SIZE_MAX <=3D ULONG_MAX); +# endif + } } =20 static size_t size_t_to_host_endian (size_t val) { -#ifdef WORDS_BIGENDIAN -# if BITS_PER_SIZE_T =3D=3D 64 +#ifndef WORDS_BIGENDIAN + return val; +#elif SIZE_MAX >> 31 =3D=3D 1 + return bswap_32 (val); +#elif SIZE_MAX >> 31 >> 31 >> 1 =3D=3D 1 return bswap_64 (val); -# else - return bswap_32 (val); -# endif #else - return val; + int i; + size_t r =3D 0; + for (i =3D 0; i < sizeof val; i++) + { + r =3D (r << CHAR_BIT) | (val & ((1u << CHAR_BIT) - 1)); + val >>=3D CHAR_BIT; + } + return r; #endif } =20 =3D=3D=3D modified file 'src/lisp.h' --- src/lisp.h 2013-10-04 07:36:22 +0000 +++ src/lisp.h 2013-10-07 07:36:08 +0000 @@ -71,6 +71,7 @@ BITS_PER_SHORT =3D CHAR_BIT * sizeof (short), BITS_PER_INT =3D CHAR_BIT * sizeof (int), BITS_PER_LONG =3D CHAR_BIT * sizeof (long int), + BITS_PER_SIZE_T =3D CHAR_BIT * sizeof (size_t), BITS_PER_EMACS_INT =3D CHAR_BIT * sizeof (EMACS_INT) }; =20 @@ -4366,12 +4367,6 @@ return 0; } =20 -#if ((SIZE_MAX >> 31) >> 1) & 1 -# define BITS_PER_SIZE_T 64 -#else -# define BITS_PER_SIZE_T 32 -#endif - /* Round x to the next multiple of y. Does not overflow. Evaluates arguments repeatedly. */ #define ROUNDUP(x,y) ((y)*((x)/(y) + ((x)%(y)!=3D0)))