From 595e113b15e2ce80b95d39d1851ce78f25ffa1f4 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 7 Oct 2013 14:37:19 -0700 Subject: 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 --- 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 +++++- 5 files changed, 269 insertions(+), 1 deletion(-) 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 (limited to 'lib') diff --git a/lib/count-one-bits.c b/lib/count-one-bits.c new file mode 100644 index 00000000000..66341d77cda --- /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 00000000000..2a7e93c3f40 --- /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 00000000000..f3da8867428 --- /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 00000000000..1dab45dc11d --- /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 73381f2bdce..69fc06bbe06 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 -- cgit v1.2.1