1 /* ffsl.h -- find the first set bit in a word. 2 Copyright (C) 2011-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 /* This file is meant to be included by ffsl.c and ffsll.c, after 20 they have defined FUNC and TYPE. */ 21 22 #include <config.h> 23 24 /* Specification. */ 25 #include <string.h> 26 27 #include <limits.h> 28 #include <strings.h> 29 30 #if defined _MSC_VER && !(__clang_major__ >= 4) 31 # include <intrin.h> 32 /* Copied from ffs.c. */ 33 static inline int 34 ffs (int i) /* */ 35 { 36 /* _BitScanForward 37 <https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64> */ 38 unsigned long bit; 39 if (_BitScanForward (&bit, i)) 40 return bit + 1; 41 else 42 return 0; 43 } 44 #endif 45 46 #if !defined FUNC || !defined TYPE 47 # error 48 #endif 49 50 int 51 FUNC (TYPE i) /* */ 52 { 53 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) \ 54 || (__clang_major__ >= 4) 55 return GCC_BUILTIN (i); 56 #elif defined _MSC_VER && defined MSVC_BUILTIN 57 /* _BitScanForward, _BitScanForward64 58 <https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64> */ 59 unsigned long bit; 60 if (MSVC_BUILTIN (&bit, i)) 61 return bit + 1; 62 else 63 return 0; 64 #else 65 unsigned TYPE j = i; 66 /* Split j into chunks, and look at one chunk after the other. */ 67 enum { chunk_bits = CHAR_BIT * sizeof (unsigned int) }; 68 /* The number of chunks is ceil (sizeof (TYPE) / sizeof (unsigned int)) 69 = (sizeof (TYPE) - 1) / sizeof (unsigned int) + 1. */ 70 enum { chunk_count = (sizeof (TYPE) - 1) / sizeof (unsigned int) + 1 }; 71 72 if (chunk_count > 1) 73 { 74 size_t k; 75 76 /* It is tempting to write if (!j) here, but if we do this, 77 Solaris 10/x86 "cc -O" miscompiles the code. */ 78 if (!i) 79 return 0; 80 /* Unroll the first loop round. k = 0. */ 81 if ((unsigned int) j) 82 return ffs ((unsigned int) j); 83 /* Generic loop. */ 84 for (k = 1; k < chunk_count - 1; k++) 85 if ((unsigned int) (j >> (k * chunk_bits)) != 0) 86 return k * chunk_bits + ffs ((unsigned int) (j >> (k * chunk_bits))); 87 } 88 /* Last loop round. k = chunk_count - 1. */ 89 return (chunk_count - 1) * chunk_bits 90 + ffs ((unsigned int) (j >> ((chunk_count - 1) * chunk_bits))); 91 #endif 92 }