[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
bug#15550: Improve support for popcount and counting trailing zeros.
|
From: |
Paul Eggert |
|
Subject: |
bug#15550: Improve support for popcount and counting trailing zeros. |
|
Date: |
Mon, 07 Oct 2013 00:46:32 -0700 |
|
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 |
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.
=== 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 <eggert@cs.ucla.edu>
+
+ 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 <eggert@cs.ucla.edu>
Use hardware insns for byteswapping on glibc hosts that support it.
=== 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 <eggert@cs.ucla.edu>
+
+ 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 <eggert@cs.ucla.edu>
Use hardware support for byteswapping on glibc x86 etc.
=== 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 @@
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
=== 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 <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
=== 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 <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 */
=== 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 <config.h>
+#define COUNT_TRAILING_ZEROS_INLINE _GL_EXTERN_INLINE
+#include "count-trailing-zeros.h"
=== 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 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
=== 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=. --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 symlin
k sys_sta
t 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 @@
## 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
=== 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])
+])
=== 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])
+])
=== 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
=== 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 <eggert@cs.ucla.edu>
+
+ Improve support for popcount and counting trailing zeros.
+ * 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-06 Jan Djärv <jan.h.d@swipnet.se>
* nsterm.m (ns_update_begin): If native fullscreen and no toolbar,
=== 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 <stdio.h>
#include <byteswap.h>
+#include <count-one-bits.h>
+#include <count-trailing-zeros.h>
#include <intprops.h>
#include "lisp.h"
@@ -2971,107 +2973,15 @@
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
-#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;
-}
-#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
-}
+#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
+# error "size_t wider than long long? Please file a bug report."
+#endif
enum bool_vector_op { bool_vector_exclusive_or,
bool_vector_union,
@@ -3143,55 +3053,54 @@
/* 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
- {
- /* 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;
- }
-#endif
+ 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
+ verify (SIZE_MAX <= ULLONG_MAX);
+ return count_trailing_zeros_ll (val);
+# else
+ verify (SIZE_MAX <= ULONG_MAX);
+# endif
+ }
}
static size_t
size_t_to_host_endian (size_t val)
{
-#ifdef WORDS_BIGENDIAN
-# if BITS_PER_SIZE_T == 64
+#ifndef WORDS_BIGENDIAN
+ return val;
+#elif SIZE_MAX >> 31 == 1
+ return bswap_32 (val);
+#elif SIZE_MAX >> 31 >> 31 >> 1 == 1
return bswap_64 (val);
-# else
- return bswap_32 (val);
-# endif
#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
}
=== 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 = 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 @@
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)))
- bug#15550: Improve support for popcount and counting trailing zeros.,
Paul Eggert <=