1 /* count-leading-zeros.h -- counts the number of leading 0 bits in a word. 2 Copyright (C) 2012-2021 Free Software Foundation, Inc. 3 4 This file is free software: you can redistribute it and/or modify 5 it under the terms of the GNU Lesser General Public License as 6 published by the Free Software Foundation; either version 2.1 of the 7 License, or (at your option) any later version. 8 9 This file 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 Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public License 15 along with this program. If not, see <https://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 25 #ifndef _GL_INLINE_HEADER_BEGIN 26 #error "Please include config.h first." 27 #endif 28 _GL_INLINE_HEADER_BEGIN 29 #ifndef COUNT_LEADING_ZEROS_INLINE 30 # define COUNT_LEADING_ZEROS_INLINE _GL_INLINE 31 #endif 32 33 #ifdef __cplusplus 34 extern "C" { 35 #endif 36 37 /* Assuming the GCC builtin is BUILTIN and the MSC builtin is MSC_BUILTIN, 38 expand to code that computes the number of leading zeros of the local 39 variable 'x' of type TYPE (an unsigned integer type) and return it 40 from the current function. */ 41 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) \ 42 || (__clang_major__ >= 4) 43 # define COUNT_LEADING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \ 44 return x ? BUILTIN (x) : CHAR_BIT * sizeof x; 45 #elif _MSC_VER 46 # pragma intrinsic _BitScanReverse 47 # pragma intrinsic _BitScanReverse64 48 # define COUNT_LEADING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \ 49 do \ 50 { \ 51 unsigned long result; \ 52 return MSC_BUILTIN (&result, x) ? result : CHAR_BIT * sizeof x; \ 53 } \ 54 while (0) 55 #else 56 # define COUNT_LEADING_ZEROS(BUILTIN, MSC_BUILTIN, TYPE) \ 57 do \ 58 { \ 59 int count; \ 60 unsigned int leading_32; \ 61 if (! x) \ 62 return CHAR_BIT * sizeof x; \ 63 for (count = 0; \ 64 (leading_32 = ((x >> (sizeof (TYPE) * CHAR_BIT - 32)) \ 65 & 0xffffffffU), \ 66 count < CHAR_BIT * sizeof x - 32 && !leading_32); \ 67 count += 32) \ 68 x = x << 31 << 1; \ 69 return count + count_leading_zeros_32 (leading_32); \ 70 } \ 71 while (0) 72 73 /* Compute and return the number of leading zeros in X, 74 where 0 < X < 2**32. */ 75 COUNT_LEADING_ZEROS_INLINE int 76 count_leading_zeros_32 (unsigned int x) 77 { 78 /* <https://github.com/gibsjose/BitHacks> 79 <https://www.fit.vutbr.cz/~ibarina/pub/bithacks.pdf> */ 80 static const char de_Bruijn_lookup[32] = { 81 31, 22, 30, 21, 18, 10, 29, 2, 20, 17, 15, 13, 9, 6, 28, 1, 82 23, 19, 11, 3, 16, 14, 7, 24, 12, 4, 8, 25, 5, 26, 27, 0 83 }; 84 85 x |= x >> 1; 86 x |= x >> 2; 87 x |= x >> 4; 88 x |= x >> 8; 89 x |= x >> 16; 90 return de_Bruijn_lookup[((x * 0x07c4acddU) & 0xffffffffU) >> 27]; 91 } 92 #endif 93 94 /* Compute and return the number of leading zeros in X. */ 95 COUNT_LEADING_ZEROS_INLINE int 96 count_leading_zeros (unsigned int x) 97 { 98 COUNT_LEADING_ZEROS (__builtin_clz, _BitScanReverse, unsigned int); 99 } 100 101 /* Compute and return the number of leading zeros in X. */ 102 COUNT_LEADING_ZEROS_INLINE int 103 count_leading_zeros_l (unsigned long int x) 104 { 105 COUNT_LEADING_ZEROS (__builtin_clzl, _BitScanReverse, unsigned long int); 106 } 107 108 /* Compute and return the number of leading zeros in X. */ 109 COUNT_LEADING_ZEROS_INLINE int 110 count_leading_zeros_ll (unsigned long long int x) 111 { 112 COUNT_LEADING_ZEROS (__builtin_clzll, _BitScanReverse64, 113 unsigned long long int); 114 } 115 116 #ifdef __cplusplus 117 } 118 #endif 119 120 _GL_INLINE_HEADER_END 121 122 #endif /* COUNT_LEADING_ZEROS_H */ 123