Mercurial > gnulib

annotate lib/count-leading-zeros.h @ 40186:8964917f9574

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
autoupdate
author Karl Berry <karl@freefriends.org>
date Mon, 18 Feb 2019 08:02:49 -0800
parents b06060465f09
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
1 /* count-leading-zeros.h -- counts the number of leading 0 bits in a word.
40057
b06060465f09 maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents: 19484
diff changeset
2 Copyright (C) 2012-2019 Free Software Foundation, Inc.
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
3
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
4 This program is free software: you can redistribute it and/or modify
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
5 it under the terms of the GNU General Public License as published by
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
6 the Free Software Foundation; either version 3 of the License, or
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
7 (at your option) any later version.
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
8
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
9 This program is distributed in the hope that it will be useful,
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
12 GNU General Public License for more details.
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
13
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
14 You should have received a copy of the GNU General Public License
19190
9759915b2aca all: prefer https: URLs
Paul Eggert <eggert@cs.ucla.edu>
parents: 18626
diff changeset
15 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
16
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
17 /* Written by Eric Blake. */
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
18
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
19 #ifndef COUNT_LEADING_ZEROS_H
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
20 #define COUNT_LEADING_ZEROS_H 1
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
21
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
22 #include <limits.h>
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
23 #include <stdlib.h>
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
24
17473
1f9070ef79b0 headers: check that _GL_INLINE_HEADER_BEGIN is defined
Paul Eggert <eggert@cs.ucla.edu>
parents: 17249
diff changeset
25 #ifndef _GL_INLINE_HEADER_BEGIN
1f9070ef79b0 headers: check that _GL_INLINE_HEADER_BEGIN is defined
Paul Eggert <eggert@cs.ucla.edu>
parents: 17249
diff changeset
26 #error "Please include config.h first."
1f9070ef79b0 headers: check that _GL_INLINE_HEADER_BEGIN is defined
Paul Eggert <eggert@cs.ucla.edu>
parents: 17249
diff changeset
27 #endif
17166
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
28 _GL_INLINE_HEADER_BEGIN
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
29 #ifndef COUNT_LEADING_ZEROS_INLINE
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
30 # define COUNT_LEADING_ZEROS_INLINE _GL_INLINE
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
31 #endif
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
32
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
33 /* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTIN,
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
34 expand to code that computes the number of leading zeros of the local
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
35 variable 'x' of type TYPE (an unsigned integer type) and return it
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
36 from the current function. */
17038
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
37 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
38 # define COUNT_LEADING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
39 return x ? BUILTIN (x) : CHAR_BIT * sizeof x;
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
40 #elif _MSC_VER
17863
9ace8922f68f count-leading-zeros: fix pragma typos
Paul Eggert <eggert@cs.ucla.edu>
parents: 17861
diff changeset
41 # pragma intrinsic _BitScanReverse
9ace8922f68f count-leading-zeros: fix pragma typos
Paul Eggert <eggert@cs.ucla.edu>
parents: 17861
diff changeset
42 # pragma intrinsic _BitScanReverse64
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
43 # define COUNT_LEADING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
44 do \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
45 { \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
46 unsigned long result; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
47 return MSC_BUILTIN (&result, x) ? result : CHAR_BIT * sizeof x; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
48 } \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
49 while (0)
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
50 #else
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
51 # define COUNT_LEADING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
52 do \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
53 { \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
54 int count; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
55 unsigned int leading_32; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
56 if (! x) \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
57 return CHAR_BIT * sizeof x; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
58 for (count = 0; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
59 (leading_32 = ((x >> (sizeof (TYPE) * CHAR_BIT - 32)) \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
60 & 0xffffffffU), \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
61 count < CHAR_BIT * sizeof x - 32 && !leading_32); \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
62 count += 32) \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
63 x = x << 31 << 1; \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
64 return count + count_leading_zeros_32 (leading_32); \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
65 } \
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
66 while (0)
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
67
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
68 /* Compute and return the number of leading zeros in X,
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
69 where 0 < X < 2**32. */
17166
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
70 COUNT_LEADING_ZEROS_INLINE int
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
71 count_leading_zeros_32 (unsigned int x)
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
72 {
19192
d86e08b1f555 all: Replace many more http URLs by https URLs. Update stale URLs.
Bruno Haible <bruno@clisp.org>
parents: 19190
diff changeset
73 /* <https://github.com/gibsjose/BitHacks>
d86e08b1f555 all: Replace many more http URLs by https URLs. Update stale URLs.
Bruno Haible <bruno@clisp.org>
parents: 19190
diff changeset
74 <http://www.fit.vutbr.cz/~ibarina/pub/bithacks.pdf> */
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
75 static const char de_Bruijn_lookup[32] = {
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
76 31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1,
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
77 23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0
17038
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
78 };
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
79
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
80 x |= x >> 1;
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
81 x |= x >> 2;
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
82 x |= x >> 4;
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
83 x |= x >> 8;
86928fc41efe count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents: 17037
diff changeset
84 x |= x >> 16;
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
85 return de_Bruijn_lookup[((x * 0x07c4acddU) & 0xffffffffU) >> 27];
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
86 }
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
87 #endif
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
88
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
89 /* Compute and return the number of leading zeros in X. */
17166
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
90 COUNT_LEADING_ZEROS_INLINE int
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
91 count_leading_zeros (unsigned int x)
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
92 {
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
93 COUNT_LEADING_ZEROS (__builtin_clz, _BitScanReverse, unsigned int);
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
94 }
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
95
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
96 /* Compute and return the number of leading zeros in X. */
17166
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
97 COUNT_LEADING_ZEROS_INLINE int
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
98 count_leading_zeros_l (unsigned long int x)
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
99 {
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
100 COUNT_LEADING_ZEROS (__builtin_clzl, _BitScanReverse, unsigned long int);
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
101 }
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
102
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
103 #if HAVE_UNSIGNED_LONG_LONG_INT
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
104 /* Compute and return the number of leading zeros in X. */
17166
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
105 COUNT_LEADING_ZEROS_INLINE int
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
106 count_leading_zeros_ll (unsigned long long int x)
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
107 {
17504
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
108 COUNT_LEADING_ZEROS (__builtin_clzll, _BitScanReverse64,
0c3911457322 count-leading-zeros: port to MSC; support types wider than 64 bits
Paul Eggert <eggert@cs.ucla.edu>
parents: 17473
diff changeset
109 unsigned long long int);
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
110 }
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
111 #endif
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
112
17166
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
113 _GL_INLINE_HEADER_END
22a948de1761 count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents: 17038
diff changeset
114
17037
abd788a78228 count-leading-zeros: new module
Eric Blake <eblake@redhat.com>
parents:
diff changeset
115 #endif /* COUNT_LEADING_ZEROS_H */