1 /* vim: set expandtab ts=4 sw=4: */
2 /*
3 * You may redistribute this program and/or modify it under the terms of
4 * the GNU General Public License as published by the Free Software Foundation,
5 * either version 3 of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <https://www.gnu.org/licenses/>.
14 */
15 #ifndef Bits_H
16 #define Bits_H
17
18 #include "util/Assert.h"
19 #include "util/Gcc.h"
20 #include "util/Linker.h"
21 Linker_require("util/Bits.c")
22
23 #include <stdint.h>
24 #include <stddef.h>
25
26 /**
27 * Find first set bit in a 64 bit integer.
28 */
Bits_ffs64(uint64_t number)29 static inline int Bits_ffs64(uint64_t number)
30 {
31 if (!number) {
32 return 0;
33 }
34 int out = 1;
35 while (!(number & 1)) {
36 number >>= 1;
37 out++;
38 }
39 return out;
40 }
41
Bits_popCountx64(uint64_t number)42 static inline int Bits_popCountx64(uint64_t number)
43 {
44 return __builtin_popcountll(number);
45 }
46
Bits_popCountx32(uint32_t number)47 static inline int Bits_popCountx32(uint32_t number)
48 {
49 int out = 0;
50 for (int i = 0; i < 32; i++) {
51 out += ((number >> i) & 1);
52 }
53 return out;
54 }
55
Bits_log2x64(uint64_t number)56 static inline int Bits_log2x64(uint64_t number)
57 {
58 if (!number) { return 0; }
59 return 63 - __builtin_clzll(number);
60 }
61 int Bits_log2x64_stupid(uint64_t number);
62
63 /** Largest possible number whose log2 is bitCount. */
Bits_maxBits64(uint32_t bitCount)64 static inline uint64_t Bits_maxBits64(uint32_t bitCount)
65 {
66 Assert_ifParanoid(bitCount < 64);
67 return (((uint64_t)1) << bitCount) - 1;
68 }
69
Bits_log2x32(uint32_t number)70 static inline int Bits_log2x32(uint32_t number)
71 {
72 int out = 0;
73 while (number >>= 1) {
74 out++;
75 }
76 return out;
77 }
78
79 /**
80 * Bitwise reversal of the a number.
81 * This is endian safe.
82 */
Bits_bitReverse64(uint64_t toReverse)83 static inline uint64_t Bits_bitReverse64(uint64_t toReverse)
84 {
85 #define Bits_rotateAndMask(mask, rotateBits) \
86 toReverse = ((toReverse >> rotateBits) & mask) | ((toReverse & mask) << rotateBits)
87
88 Bits_rotateAndMask(0x5555555555555555ull, 1);
89 Bits_rotateAndMask(0x3333333333333333ull, 2);
90 Bits_rotateAndMask(0x0F0F0F0F0F0F0F0Full, 4);
91 return __builtin_bswap64(toReverse);
92
93 #undef Bits_rotateAndMask
94 }
95
96 /**
97 * @param buffer the space of check if it's zero.
98 * @length the nuber of bytes to check for zero'd-ness.
99 * @return true if all bytes checked are zero.
100 */
Bits_isZero(void * buffer,size_t length)101 static inline int Bits_isZero(void* buffer, size_t length)
102 {
103 uint8_t* buff = (uint8_t*) buffer;
104 for (size_t i = 0; i < length; i++) {
105 if (buff[i]) {
106 return 0;
107 }
108 }
109 return 1;
110 }
111
112 #define Bits_memmove(a,b,c) __builtin_memmove(a,b,c)
113 #define Bits_memset(a,b,c) __builtin_memset(a,b,c)
114 #define Bits_memcmp(a,b,c) __builtin_memcmp(a,b,c)
115
116 /**
117 * Bits_memcpy()
118 * Alias to POSIX memcpy(), allows for extra debugging checks.
119 *
120 * @param out buffer to write to.
121 * @param in buffer to read from.
122 * @param length number of bytes to copy.
123 * @param file name of the file calling this, for logging.
124 * @param line the line number of the calling file, for logging.
125 * @param constant true if the length should be checked for being constant.
126 * @return out
127 */
128 #define Bits_memcpy(a,b,c) Bits__memcpy(a,b,c,Gcc_SHORT_FILE,Gcc_LINE)
Bits__memcpy(void * out,const void * in,size_t length,char * file,int line)129 static inline void* Bits__memcpy(void* out,
130 const void* in,
131 size_t length,
132 char* file,
133 int line)
134 {
135 const char* inc = in;
136 const char* outc = out;
137 // Check that pointers don't alias.
138 if (outc >= inc && outc < inc + length) {
139 Assert_failure(file, line, "memcpy() pointers alias each other");
140 }
141 return __builtin_memcpy(out, in, length);
142 }
143
144 void* Bits_memmem(const void* haystack, size_t haystackLen, const void* needle, size_t needleLen);
145
Bits_get16(uint8_t * bytes)146 static inline uint16_t Bits_get16(uint8_t* bytes)
147 {
148 uint16_t x = 0;
149 Bits_memcpy(&x, bytes, 2);
150 return x;
151 }
152
Bits_put16(uint8_t * bytes,uint16_t num)153 static inline void Bits_put16(uint8_t* bytes, uint16_t num)
154 {
155 Bits_memcpy(bytes, &num, 2);
156 }
157
158 #endif
159