bitops: rename bit scan functions
[wimlib] / include / wimlib / bitops.h
1 /*
2  * bitops.h - inline functions for bit manipulation
3  *
4  * The following copying information applies to this specific source code file:
5  *
6  * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
7  *
8  * To the extent possible under law, the author(s) have dedicated all copyright
9  * and related and neighboring rights to this software to the public domain
10  * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
11  * Dedication (the "CC0").
12  *
13  * This software is distributed in the hope that it will be useful, but WITHOUT
14  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15  * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
16  *
17  * You should have received a copy of the CC0 along with this software; if not
18  * see <http://creativecommons.org/publicdomain/zero/1.0/>.
19  */
20
21 #ifndef _WIMLIB_BITOPS_H
22 #define _WIMLIB_BITOPS_H
23
24 #include "wimlib/compiler.h"
25 #include "wimlib/types.h"
26
27 /*
28  * Bit Scan Reverse (BSR) - find the 0-based index (relative to the least
29  * significant bit) of the *most* significant 1 bit in the input value.  The
30  * input value must be nonzero!
31  */
32
33 static inline unsigned
34 bsr32(u32 v)
35 {
36 #ifdef compiler_bsr32
37         return compiler_bsr32(v);
38 #else
39         unsigned bit = 0;
40         while ((v >>= 1) != 0)
41                 bit++;
42         return bit;
43 #endif
44 }
45
46 static inline unsigned
47 bsr64(u64 v)
48 {
49 #ifdef compiler_bsr64
50         return compiler_bsr64(v);
51 #else
52         unsigned bit = 0;
53         while ((v >>= 1) != 0)
54                 bit++;
55         return bit;
56 #endif
57 }
58
59 static inline unsigned
60 bsrw(machine_word_t v)
61 {
62         STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
63         if (WORDBITS == 32)
64                 return bsr32(v);
65         else
66                 return bsr64(v);
67 }
68
69 /*
70  * Bit Scan Forward (BSF) - find the 0-based index (relative to the least
71  * significant bit) of the *least* significant 1 bit in the input value.  The
72  * input value must be nonzero!
73  */
74
75 static inline unsigned
76 bsf32(u32 v)
77 {
78 #ifdef compiler_bsf32
79         return compiler_bsf32(v);
80 #else
81         unsigned bit;
82         for (bit = 0; !(v & 1); bit++, v >>= 1)
83                 ;
84         return bit;
85 #endif
86 }
87
88 static inline unsigned
89 bsf64(u64 v)
90 {
91 #ifdef compiler_bsf64
92         return compiler_bsf64(v);
93 #else
94         unsigned bit;
95         for (bit = 0; !(v & 1); bit++, v >>= 1)
96                 ;
97         return bit;
98 #endif
99 }
100
101 static inline unsigned
102 bsfw(machine_word_t v)
103 {
104         STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
105         if (WORDBITS == 32)
106                 return bsf32(v);
107         else
108                 return bsf64(v);
109 }
110
111 /* Return the log base 2 of 'n', rounded up to the nearest integer. */
112 static inline unsigned
113 ilog2_ceil(size_t n)
114 {
115         if (n <= 1)
116                 return 0;
117         return 1 + bsrw(n - 1);
118 }
119
120 /* Round 'n' up to the nearest power of 2 */
121 static inline size_t
122 roundup_pow_of_2(size_t n)
123 {
124         return (size_t)1 << ilog2_ceil(n);
125 }
126
127 #endif /* _WIMLIB_BITOPS_H */