Mercurial > hg > octave-shane > gnulib-hg
annotate lib/count-leading-zeros.h @ 17255:d81be792518a
update from texinfo
| author | Karl Berry <karl@freefriends.org> |
|---|---|
| date | Tue, 01 Jan 2013 15:51:49 -0800 |
| parents | e542fd46ad6f |
| children | 1f9070ef79b0 |
| rev | line source |
|---|---|
| 17037 | 1 /* count-leading-zeros.h -- counts the number of leading 0 bits in a word. |
|
17249
e542fd46ad6f
maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents:
17166
diff
changeset
|
2 Copyright (C) 2012-2013 Free Software Foundation, Inc. |
| 17037 | 3 |
| 4 This program is free software: you can redistribute it and/or modify | |
| 5 it under the terms of the GNU General Public License as published by | |
| 6 the Free Software Foundation; either version 3 of the License, or | |
| 7 (at your option) any later version. | |
| 8 | |
| 9 This program is distributed in the hope that it will be useful, | |
| 10 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 12 GNU General Public License for more details. | |
| 13 | |
| 14 You should have received a copy of the GNU General Public License | |
| 15 along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
| 16 | |
| 17 /* Written by Eric Blake. */ | |
| 18 | |
| 19 #ifndef COUNT_LEADING_ZEROS_H | |
| 20 # define COUNT_LEADING_ZEROS_H 1 | |
| 21 | |
| 22 #include <limits.h> | |
| 23 #include <stdlib.h> | |
| 24 #include "verify.h" | |
| 25 | |
|
17166
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
26 _GL_INLINE_HEADER_BEGIN |
|
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
27 #ifndef COUNT_LEADING_ZEROS_INLINE |
|
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
28 # define COUNT_LEADING_ZEROS_INLINE _GL_INLINE |
|
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
29 #endif |
|
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
30 |
| 17037 | 31 /* Expand the code which computes the number of leading zeros of the local |
| 32 variable 'x' of type TYPE (an unsigned integer type) and returns it | |
| 33 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
|
34 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) |
| 17037 | 35 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \ |
| 36 return x ? BUILTIN (x) : CHAR_BIT * sizeof x; | |
| 37 #else | |
| 38 # define COUNT_LEADING_ZEROS(BUILTIN, TYPE) \ | |
| 39 /* This condition is written so as to avoid shifting by more than \ | |
| 40 31 bits at once, and also avoids a random HP-UX cc bug. */ \ | |
| 41 verify (((TYPE) -1 >> 31 >> 31 >> 2) == 0); /* TYPE has at most 64 bits */ \ | |
| 42 int count = 0; \ | |
| 43 if (1 < (TYPE) -1 >> 31) { /* TYPE has more than 32 bits? */ \ | |
| 44 count = count_leading_zeros_32 (x >> 31 >> 1); \ | |
| 45 if (count < 32) \ | |
| 46 return count; \ | |
| 47 } \ | |
| 48 return count + count_leading_zeros_32 (x); | |
| 49 | |
| 50 /* Compute and return the number of leading zeros in the least | |
| 51 significant 32 bits of X. */ | |
|
17166
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
52 COUNT_LEADING_ZEROS_INLINE int |
| 17037 | 53 count_leading_zeros_32 (unsigned int x) |
| 54 { | |
|
17038
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
55 /* http://graphics.stanford.edu/~seander/bithacks.html */ |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
56 static const char deBruijnLookup[32] = { |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
57 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
58 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
59 }; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
60 |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
61 x &= 0xffffffffU; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
62 if (!x) |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
63 return 32; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
64 x |= x >> 1; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
65 x |= x >> 2; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
66 x |= x >> 4; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
67 x |= x >> 8; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
68 x |= x >> 16; |
|
86928fc41efe
count-leading-zeros: use a lookup table on non-gcc compilers
Eric Blake <eblake@redhat.com>
parents:
17037
diff
changeset
|
69 return 31 - deBruijnLookup[(x * 0x07c4acddU) >> 27]; |
| 17037 | 70 } |
| 71 #endif | |
| 72 | |
| 73 /* 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
|
74 COUNT_LEADING_ZEROS_INLINE int |
| 17037 | 75 count_leading_zeros (unsigned int x) |
| 76 { | |
| 77 COUNT_LEADING_ZEROS (__builtin_clz, unsigned int); | |
| 78 } | |
| 79 | |
| 80 /* 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
|
81 COUNT_LEADING_ZEROS_INLINE int |
| 17037 | 82 count_leading_zeros_l (unsigned long int x) |
| 83 { | |
| 84 COUNT_LEADING_ZEROS (__builtin_clzl, unsigned long int); | |
| 85 } | |
| 86 | |
| 87 #if HAVE_UNSIGNED_LONG_LONG_INT | |
| 88 /* 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
|
89 COUNT_LEADING_ZEROS_INLINE int |
| 17037 | 90 count_leading_zeros_ll (unsigned long long int x) |
| 91 { | |
| 92 COUNT_LEADING_ZEROS (__builtin_clzll, unsigned long long int); | |
| 93 } | |
| 94 #endif | |
| 95 | |
|
17166
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
96 _GL_INLINE_HEADER_END |
|
22a948de1761
count-leading-zeros: better 'inline'
Paul Eggert <eggert@cs.ucla.edu>
parents:
17038
diff
changeset
|
97 |
| 17037 | 98 #endif /* COUNT_LEADING_ZEROS_H */ |