summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPaul Eggert <eggert@cs.ucla.edu>2013-10-07 14:37:19 -0700
committerPaul Eggert <eggert@cs.ucla.edu>2013-10-07 14:37:19 -0700
commit595e113b15e2ce80b95d39d1851ce78f25ffa1f4 (patch)
tree42c02de46a13e0af39fcc83de9d57c29e309f99e
parentddb317ba828f05eb48e98fda530443955485e75d (diff)
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 <count-one-bits.h>, <count-trailing-zeros.h>. (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
-rw-r--r--ChangeLog12
-rw-r--r--admin/ChangeLog6
-rwxr-xr-xadmin/merge-gnulib3
-rw-r--r--lib/count-one-bits.c7
-rw-r--r--lib/count-one-bits.h136
-rw-r--r--lib/count-trailing-zeros.c3
-rw-r--r--lib/count-trailing-zeros.h106
-rw-r--r--lib/gnulib.mk18
-rw-r--r--m4/count-one-bits.m412
-rw-r--r--m4/count-trailing-zeros.m412
-rw-r--r--m4/gnulib-comp.m410
-rw-r--r--nt/ChangeLog5
-rw-r--r--nt/gnulib.mk18
-rw-r--r--src/ChangeLog19
-rw-r--r--src/data.c179
-rw-r--r--src/lisp.h7
16 files changed, 409 insertions, 144 deletions
diff --git a/ChangeLog b/ChangeLog
index 4769f5d575..f1eec73689 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,15 @@
+2013-10-07 Paul Eggert <eggert@cs.ucla.edu>
+
+ 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 <eggert@cs.ucla.edu>
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 <eggert@cs.ucla.edu>
+
+ 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 <eggert@cs.ucla.edu>
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 <config.h>
+#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 <http://www.gnu.org/licenses/>. */
+
+/* Written by Ben Pfaff. */
+
+#ifndef COUNT_ONE_BITS_H
+#define COUNT_ONE_BITS_H 1
+
+#include <limits.h>
+#include <stdlib.h>
+
+#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 <config.h>
+#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 <http://www.gnu.org/licenses/>. */
+
+/* Written by Paul Eggert. */
+
+#ifndef COUNT_TRAILING_ZEROS_H
+#define COUNT_TRAILING_ZEROS_H 1
+
+#include <limits.h>
+#include <stdlib.h>
+
+#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 <eggert@cs.ucla.edu>
+
+ Improve support for popcount and counting trailing zeros (Bug#15550).
+ * gnulib.mk: Merge changes from ../lib/gnulib.mk.
+
2013-10-04 Paul Eggert <eggert@cs.ucla.edu>
* gnulib.mk: Create <byteswap.h> from <byteswap.in.h>.
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 <eggert@cs.ucla.edu>
+
+ Improve support for popcount and counting trailing zeros (Bug#15550).
+ * data.c: Include <count-one-bits.h>, <count-trailing-zeros.h>.
+ (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 <jan.h.d@swipnet.se>
* 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 <http://www.gnu.org/licenses/>. */
#include <stdio.h>
#include <byteswap.h>
+#include <count-one-bits.h>
+#include <count-trailing-zeros.h>
#include <intprops.h>
#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)))