From 595e113b15e2ce80b95d39d1851ce78f25ffa1f4 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 7 Oct 2013 14:37:19 -0700 Subject: [PATCH] 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. * admin/merge-gnulib (GNULIB_MODULES): Add count-one-bits and count-trailing-zeros. * 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. * nt/gnulib.mk: Merge changes from lib/gnulib.mk. * src/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. * src/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. Fixes: debbugs:15550 --- ChangeLog | 12 +++ admin/ChangeLog | 6 ++ admin/merge-gnulib | 3 +- lib/count-one-bits.c | 7 ++ lib/count-one-bits.h | 136 ++++++++++++++++++++++++++++ lib/count-trailing-zeros.c | 3 + lib/count-trailing-zeros.h | 106 ++++++++++++++++++++++ lib/gnulib.mk | 18 +++- m4/count-one-bits.m4 | 12 +++ m4/count-trailing-zeros.m4 | 12 +++ m4/gnulib-comp.m4 | 10 +++ nt/ChangeLog | 5 ++ nt/gnulib.mk | 18 +++- src/ChangeLog | 19 ++++ src/data.c | 179 +++++++++---------------------------- src/lisp.h | 7 +- 16 files changed, 409 insertions(+), 144 deletions(-) create mode 100644 lib/count-one-bits.c create mode 100644 lib/count-one-bits.h create mode 100644 lib/count-trailing-zeros.c create mode 100644 lib/count-trailing-zeros.h create mode 100644 m4/count-one-bits.m4 create mode 100644 m4/count-trailing-zeros.m4 diff --git a/ChangeLog b/ChangeLog index 4769f5d575..f1eec73689 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,15 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros (Bug#15550). + 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 Use hardware insns for byteswapping on glibc hosts that support it. diff --git a/admin/ChangeLog b/admin/ChangeLog index 837a0a2e6d..31247765a2 100644 --- a/admin/ChangeLog +++ b/admin/ChangeLog @@ -1,3 +1,9 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros (Bug#15550). + * merge-gnulib (GNULIB_MODULES): Add count-one-bits + and count-trailing-zeros. + 2013-10-04 Paul Eggert Use hardware support for byteswapping on glibc x86 etc. diff --git a/admin/merge-gnulib b/admin/merge-gnulib index aba0fa67a1..a5bd622f4c 100755 --- a/admin/merge-gnulib +++ b/admin/merge-gnulib @@ -27,7 +27,8 @@ GNULIB_URL=git://git.savannah.gnu.org/gnulib.git GNULIB_MODULES=' 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 diff --git a/lib/count-one-bits.c b/lib/count-one-bits.c new file mode 100644 index 0000000000..66341d77cd --- /dev/null +++ b/lib/count-one-bits.c @@ -0,0 +1,7 @@ +#include +#define COUNT_ONE_BITS_INLINE _GL_EXTERN_INLINE +#include "count-one-bits.h" + +#if 1500 <= _MSC_VER && (defined _M_IX86 || defined _M_X64) +int popcount_support = -1; +#endif diff --git a/lib/count-one-bits.h b/lib/count-one-bits.h new file mode 100644 index 0000000000..2a7e93c3f4 --- /dev/null +++ b/lib/count-one-bits.h @@ -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 = 0; \ + int bits; \ + for (bits = 0; bits < sizeof (TYPE) * CHAR_BIT; bits += 32) \ + { \ + count += count_one_bits_32 (x); \ + x = x >> 31 >> 1; \ + } \ + return count; \ + } \ + while (0) + +/* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTIN, + 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__ == 3 && __GNUC_MINOR__ >= 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 = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U); + x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U); + x = (x >> 16) + (x & 0xffff); + x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f); + return (x >> 8) + (x & 0x00ff); +} + +# if 1500 <= _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 = (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 int); +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* COUNT_ONE_BITS_H */ diff --git a/lib/count-trailing-zeros.c b/lib/count-trailing-zeros.c new file mode 100644 index 0000000000..f3da886742 --- /dev/null +++ b/lib/count-trailing-zeros.c @@ -0,0 +1,3 @@ +#include +#define COUNT_TRAILING_ZEROS_INLINE _GL_EXTERN_INLINE +#include "count-trailing-zeros.h" diff --git a/lib/count-trailing-zeros.h b/lib/count-trailing-zeros.h new file mode 100644 index 0000000000..1dab45dc11 --- /dev/null +++ b/lib/count-trailing-zeros.h @@ -0,0 +1,106 @@ +/* count-trailing-zeros.h -- counts the number of trailing 0 bits in a word. + 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_BUILTIN, + expand to code that computes the number of trailing zeros of the local + variable 'x' of type TYPE (an unsigned integer type) and return it + from the current function. */ +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 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 = 0; \ + if (! x) \ + return CHAR_BIT * sizeof x; \ + for (count = 0; \ + (count < CHAR_BIT * sizeof x - 32 \ + && ! (x & 0xffffffffU)); \ + count += 32) \ + x = 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] = { + 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 int); +} + +#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 diff --git a/lib/gnulib.mk b/lib/gnulib.mk index 73381f2bdc..69fc06bbe0 100644 --- a/lib/gnulib.mk +++ b/lib/gnulib.mk @@ -21,7 +21,7 @@ # the same distribution terms as the rest of that program. # # Generated by gnulib-tool. -# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=build-aux --avoid=close --avoid=dup --avoid=fchdir --avoid=fstat --avoid=malloc-posix --avoid=msvc-inval --avoid=msvc-nothrow --avoid=open --avoid=openat-die --avoid=opendir --avoid=raise --avoid=save-cwd --avoid=select --avoid=sigprocmask --avoid=sys_types --avoid=threadlib --makefile-name=gnulib.mk --conditional-dependencies --no-libtool --macro-prefix=gl --no-vc-files alloca-opt byteswap c-ctype c-strcase careadlinkat close-stream 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 intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 pselect pthread_sigmask putenv qacl readlink readlinkat sig2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub unsetenv utimens warnings +# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=build-aux --avoid=close --avoid=dup --avoid=fchdir --avoid=fstat --avoid=malloc-posix --avoid=msvc-inval --avoid=msvc-nothrow --avoid=open --avoid=openat-die --avoid=opendir --avoid=raise --avoid=save-cwd --avoid=select --avoid=sigprocmask --avoid=sys_types --avoid=threadlib --makefile-name=gnulib.mk --conditional-dependencies --no-libtool --macro-prefix=gl --no-vc-files alloca-opt byteswap c-ctype c-strcase 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 intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 pselect pthread_sigmask putenv qacl readlink readlinkat sig2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub unsetenv utimens warnings MOSTLYCLEANFILES += core *.stackdump @@ -132,6 +132,22 @@ EXTRA_DIST += close-stream.h ## end gnulib module close-stream +## begin gnulib module count-one-bits + +libgnu_a_SOURCES += count-one-bits.c + +EXTRA_DIST += count-one-bits.h + +## end gnulib module count-one-bits + +## begin gnulib module count-trailing-zeros + +libgnu_a_SOURCES += count-trailing-zeros.c + +EXTRA_DIST += count-trailing-zeros.h + +## end gnulib module count-trailing-zeros + ## begin gnulib module crypto/md5 libgnu_a_SOURCES += md5.c diff --git a/m4/count-one-bits.m4 b/m4/count-one-bits.m4 new file mode 100644 index 0000000000..07289641d4 --- /dev/null +++ b/m4/count-one-bits.m4 @@ -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]) +]) diff --git a/m4/count-trailing-zeros.m4 b/m4/count-trailing-zeros.m4 new file mode 100644 index 0000000000..b4a13c1439 --- /dev/null +++ b/m4/count-trailing-zeros.m4 @@ -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]) +]) diff --git a/m4/gnulib-comp.m4 b/m4/gnulib-comp.m4 index ff36981c8d..534d56f5ba 100644 --- a/m4/gnulib-comp.m4 +++ b/m4/gnulib-comp.m4 @@ -48,6 +48,8 @@ AC_DEFUN([gl_EARLY], # 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 @@ AC_DEFUN([gl_INIT], 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 @@ AC_DEFUN([gl_FILE_LIST], [ 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 @@ AC_DEFUN([gl_FILE_LIST], [ 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 diff --git a/nt/ChangeLog b/nt/ChangeLog index 94bd71d28f..390a8eb022 100644 --- a/nt/ChangeLog +++ b/nt/ChangeLog @@ -1,3 +1,8 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros (Bug#15550). + * gnulib.mk: Merge changes from ../lib/gnulib.mk. + 2013-10-04 Paul Eggert * gnulib.mk: Create from . diff --git a/nt/gnulib.mk b/nt/gnulib.mk index ff46e9f09a..f6a3401365 100644 --- a/nt/gnulib.mk +++ b/nt/gnulib.mk @@ -43,7 +43,7 @@ # the same distribution terms as the rest of that program. # # Generated by gnulib-tool. -# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=build-aux --avoid=dup --avoid=fchdir --avoid=fcntl --avoid=fstat --avoid=malloc-posix --avoid=msvc-inval --avoid=msvc-nothrow --avoid=open --avoid=openat-die --avoid=opendir --avoid=raise --avoid=save-cwd --avoid=select --avoid=sigprocmask --avoid=sys_types --avoid=threadlib --makefile-name=gnulib.mk --conditional-dependencies --no-libtool --macro-prefix=gl --no-vc-files alloca-opt c-ctype c-strcase careadlinkat close-stream crypto/md5 crypto/sha1 crypto/sha256 crypto/sha512 dtoastr dtotimespec dup2 environ execinfo faccessat fcntl-h fdatasync fdopendir filemode fstatat fsync getloadavg getopt-gnu gettime gettimeofday ignore-value intprops largefile lstat manywarnings memrchr mktime pselect pthread_sigmask putenv qacl readlink readlinkat sig2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub unsetenv utimens warnings +# Reproduce by: gnulib-tool --import --dir=. --lib=libgnu --source-base=lib --m4-base=m4 --doc-base=doc --tests-base=tests --aux-dir=build-aux --avoid=close --avoid=dup --avoid=fchdir --avoid=fstat --avoid=malloc-posix --avoid=msvc-inval --avoid=msvc-nothrow --avoid=open --avoid=openat-die --avoid=opendir --avoid=raise --avoid=save-cwd --avoid=select --avoid=sigprocmask --avoid=sys_types --avoid=threadlib --makefile-name=gnulib.mk --conditional-dependencies --no-libtool --macro-prefix=gl --no-vc-files alloca-opt byteswap c-ctype c-strcase 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 intprops largefile lstat manywarnings memrchr mkostemp mktime pipe2 pselect pthread_sigmask putenv qacl readlink readlinkat sig2str socklen stat-time stdalign stdarg stdbool stdio strftime strtoimax strtoumax symlink sys_stat sys_time time timer-time timespec-add timespec-sub unsetenv utimens warnings MOSTLYCLEANFILES += core *.stackdump @@ -121,6 +121,22 @@ EXTRA_DIST += close-stream.h ## end gnulib module close-stream +## begin gnulib module count-one-bits + +libgnu_a_SOURCES += count-one-bits.c + +EXTRA_DIST += count-one-bits.h + +## end gnulib module count-one-bits + +## begin gnulib module count-trailing-zeros + +libgnu_a_SOURCES += count-trailing-zeros.c + +EXTRA_DIST += count-trailing-zeros.h + +## end gnulib module count-trailing-zeros + ## begin gnulib module crypto/md5 libgnu_a_SOURCES += md5.c diff --git a/src/ChangeLog b/src/ChangeLog index 8e22e4f7cf..753e123378 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,22 @@ +2013-10-07 Paul Eggert + + Improve support for popcount and counting trailing zeros (Bug#15550). + * 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-07 Jan Djärv * nsterm.m (windowDidEnterFullScreen:): setPresentationOptions only diff --git a/src/data.c b/src/data.c index a6bfe50a3b..4ef326e4cf 100644 --- a/src/data.c +++ b/src/data.c @@ -22,6 +22,8 @@ along with GNU Emacs. If not, see . */ #include #include +#include +#include #include #include "lisp.h" @@ -2971,108 +2973,16 @@ bool_vector_spare_mask (ptrdiff_t nr_bits) return (((size_t) 1) << (nr_bits % BITS_PER_SIZE_T)) - 1; } -#if _MSC_VER >= 1500 && (defined _M_IX86 || defined _M_X64) -# define USE_MSC_POPCOUNT -# define POPCOUNT_STATIC_INLINE static inline -#elif __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) -# define USE_GCC_POPCOUNT -# if 199901L <= __STDC_VERSION__ || !__STRICT_ANSI__ -# define POPCOUNT_STATIC_INLINE static inline -# endif +#if SIZE_MAX <= UINT_MAX +# define popcount_size_t count_one_bits +#elif SIZE_MAX <= ULONG_MAX +# define popcount_size_t count_one_bits_l +#elif SIZE_MAX <= ULLONG_MAX +# define popcount_size_t count_one_bits_ll #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 = 0; - - for (j = 0; j < BITS_PER_SIZE_T; ++j) - count += !!((((size_t) 1) << j) & val); - - return count; -} +# error "size_t wider than long long? Please file a bug report." #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 == popcount_unknown_support) - { - int cpu_info[4]; - __cpuid (cpu_info, 1); - if (cpu_info[2] & (1<<23)) /* See MSDN. */ - popcount_state = popcount_use_intrinsic; - else - popcount_state = popcount_use_generic; - } - - if (popcount_state == popcount_use_intrinsic) - { -# if BITS_PER_SIZE_T == 64 -# pragma intrinsic __popcnt64 - count = __popcnt64 (val); -# else -# pragma intrinsic __popcnt - count = __popcnt (val); -# endif - } - else - count = 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 == 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 -} - enum bool_vector_op { bool_vector_exclusive_or, bool_vector_union, bool_vector_intersection, @@ -3143,55 +3053,54 @@ bool_vector_binop_driver (Lisp_Object op1, /* 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 == UINT_MAX) + return count_trailing_zeros (val); + if (SIZE_MAX == ULONG_MAX) + return count_trailing_zeros_l (val); +# if HAVE_UNSIGNED_LONG_LONG_INT + if (SIZE_MAX == ULLONG_MAX) + return count_trailing_zeros_ll (val); +# endif + + /* The rest of this code is for the unlikely platform where size_t differs + in width from unsigned int, unsigned long, and unsigned long long. */ if (val == 0) return CHAR_BIT * sizeof (val); - -#if defined USE_GCC_POPCOUNT && BITS_PER_SIZE_T == 64 - return __builtin_ctzll (val); -#elif defined USE_GCC_POPCOUNT && BITS_PER_SIZE_T == 32 - return __builtin_ctz (val); -#elif _MSC_VER && BITS_PER_SIZE_T == 64 -# pragma intrinsic _BitScanForward64 + if (SIZE_MAX <= UINT_MAX) + return count_trailing_zeros (val); + if (SIZE_MAX <= ULONG_MAX) + return count_trailing_zeros_l (val); { - /* No support test needed: support since 386. */ - unsigned long result; - _BitScanForward64 (&result, val); - return (unsigned int) result; - } -#elif _MSC_VER && BITS_PER_SIZE_T == 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 = 0; - for (val = ~val; val & 1; val >>= 1) - ++count; - - return count; +# if HAVE_UNSIGNED_LONG_LONG_INT + verify (SIZE_MAX <= ULLONG_MAX); + return count_trailing_zeros_ll (val); +# else + verify (SIZE_MAX <= ULONG_MAX); +# endif } -#endif } static size_t size_t_to_host_endian (size_t val) { -#ifdef WORDS_BIGENDIAN -# if BITS_PER_SIZE_T == 64 - return bswap_64 (val); -# else +#ifndef WORDS_BIGENDIAN + return val; +#elif SIZE_MAX >> 31 == 1 return bswap_32 (val); -# endif +#elif SIZE_MAX >> 31 >> 31 >> 1 == 1 + return bswap_64 (val); #else - return val; + int i; + size_t r = 0; + for (i = 0; i < sizeof val; i++) + { + r = (r << CHAR_BIT) | (val & ((1u << CHAR_BIT) - 1)); + val >>= CHAR_BIT; + } + return r; #endif } diff --git a/src/lisp.h b/src/lisp.h index c7f13e21e5..b8863d6821 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -71,6 +71,7 @@ enum BITS_PER_SHORT = CHAR_BIT * sizeof (short), BITS_PER_INT = CHAR_BIT * sizeof (int), BITS_PER_LONG = CHAR_BIT * sizeof (long int), + BITS_PER_SIZE_T = CHAR_BIT * sizeof (size_t), BITS_PER_EMACS_INT = CHAR_BIT * sizeof (EMACS_INT) }; @@ -4366,12 +4367,6 @@ functionp (Lisp_Object object) return 0; } -#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)!=0))) -- 2.20.1