* bug#15550: Improve support for popcount and counting trailing zeros.
@ 2013-10-07 7:46 Paul Eggert
2013-10-07 15:59 ` Eli Zaretskii
0 siblings, 1 reply; 3+ messages in thread
From: Paul Eggert @ 2013-10-07 7:46 UTC (permalink / raw)
To: 15550
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)))
^ permalink raw reply [flat|nested] 3+ messages in thread* bug#15550: Improve support for popcount and counting trailing zeros.
2013-10-07 7:46 bug#15550: Improve support for popcount and counting trailing zeros Paul Eggert
@ 2013-10-07 15:59 ` Eli Zaretskii
2013-10-07 21:38 ` Paul Eggert
0 siblings, 1 reply; 3+ messages in thread
From: Eli Zaretskii @ 2013-10-07 15:59 UTC (permalink / raw)
To: Paul Eggert; +Cc: 15550
> Date: Mon, 07 Oct 2013 00:46:32 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: Eli Zaretskii <eliz@gnu.org>
>
> 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.
Please just add the same fragment to nt/gnulib.mk as what you add to
lib/gnulib.mk. This code needs to be compiled into Emacs on Windows;
if there's some adverse effect to this change (I don't think there
will be), we can always fix that as followup.
Thanks.
^ permalink raw reply [flat|nested] 3+ messages in thread
* bug#15550: Improve support for popcount and counting trailing zeros.
2013-10-07 15:59 ` Eli Zaretskii
@ 2013-10-07 21:38 ` Paul Eggert
0 siblings, 0 replies; 3+ messages in thread
From: Paul Eggert @ 2013-10-07 21:38 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: 15550-done
On 10/07/13 08:59, Eli Zaretskii wrote:
> Please just add the same fragment to nt/gnulib.mk as what you add to lib/gnulib.mk. This code needs to be compiled into Emacs on Windows; if there's some adverse effect to this change (I don't think there will be), we can always fix that as followup. Thanks.
Thanks, done as trunk bzr 114564, and marking
this as done.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2013-10-07 21:38 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-10-07 7:46 bug#15550: Improve support for popcount and counting trailing zeros Paul Eggert
2013-10-07 15:59 ` Eli Zaretskii
2013-10-07 21:38 ` Paul Eggert
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).