stdbit.h (15063B)
1 /* stdbit.h -- C23 7.18a -- Bit and byte utilities */ 2 #ifndef KIT_STDBIT_H 3 #define KIT_STDBIT_H 4 5 #include <stdbool.h> 6 #include <limits.h> 7 8 #define __STDC_VERSION_STDBIT_H__ 202311L 9 10 #define __STDC_ENDIAN_LITTLE__ 1234 11 #define __STDC_ENDIAN_BIG__ 4321 12 #if defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ 13 #define __STDC_ENDIAN_NATIVE__ __STDC_ENDIAN_BIG__ 14 #else 15 #define __STDC_ENDIAN_NATIVE__ __STDC_ENDIAN_LITTLE__ 16 #endif 17 18 #define __KIT_STDBIT_WIDTH(T) ((unsigned)(sizeof(T) * CHAR_BIT)) 19 20 static inline unsigned int stdc_leading_zeros_uc(unsigned char v) { 21 unsigned int w = __KIT_STDBIT_WIDTH(unsigned char); 22 if (v == 0) return w; 23 return (unsigned int)__builtin_clz((unsigned int)v) - 24 (__KIT_STDBIT_WIDTH(unsigned int) - w); 25 } 26 27 static inline unsigned int stdc_leading_zeros_us(unsigned short v) { 28 unsigned int w = __KIT_STDBIT_WIDTH(unsigned short); 29 if (v == 0) return w; 30 return (unsigned int)__builtin_clz((unsigned int)v) - 31 (__KIT_STDBIT_WIDTH(unsigned int) - w); 32 } 33 34 static inline unsigned int stdc_leading_zeros_ui(unsigned int v) { 35 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned int); 36 return (unsigned int)__builtin_clz(v); 37 } 38 39 static inline unsigned int stdc_leading_zeros_ul(unsigned long v) { 40 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned long); 41 #if __SIZEOF_LONG__ == 8 42 return (unsigned int)__builtin_clzll((unsigned long long)v); 43 #else 44 return (unsigned int)__builtin_clz((unsigned int)v); 45 #endif 46 } 47 48 static inline unsigned int stdc_leading_zeros_ull(unsigned long long v) { 49 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned long long); 50 return (unsigned int)__builtin_clzll(v); 51 } 52 53 static inline unsigned int stdc_trailing_zeros_uc(unsigned char v) { 54 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned char); 55 return (unsigned int)__builtin_ctz((unsigned int)v); 56 } 57 58 static inline unsigned int stdc_trailing_zeros_us(unsigned short v) { 59 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned short); 60 return (unsigned int)__builtin_ctz((unsigned int)v); 61 } 62 63 static inline unsigned int stdc_trailing_zeros_ui(unsigned int v) { 64 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned int); 65 return (unsigned int)__builtin_ctz(v); 66 } 67 68 static inline unsigned int stdc_trailing_zeros_ul(unsigned long v) { 69 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned long); 70 #if __SIZEOF_LONG__ == 8 71 return (unsigned int)__builtin_ctzll((unsigned long long)v); 72 #else 73 return (unsigned int)__builtin_ctz((unsigned int)v); 74 #endif 75 } 76 77 static inline unsigned int stdc_trailing_zeros_ull(unsigned long long v) { 78 if (v == 0) return __KIT_STDBIT_WIDTH(unsigned long long); 79 return (unsigned int)__builtin_ctzll(v); 80 } 81 82 static inline unsigned int stdc_count_ones_uc(unsigned char v) { 83 unsigned int n = 0; 84 while (v != 0) { 85 n += (unsigned int)(v & 1u); 86 v = (unsigned char)(v >> 1u); 87 } 88 return n; 89 } 90 91 static inline unsigned int stdc_count_ones_us(unsigned short v) { 92 unsigned int n = 0; 93 while (v != 0) { 94 n += (unsigned int)(v & 1u); 95 v = (unsigned short)(v >> 1u); 96 } 97 return n; 98 } 99 100 static inline unsigned int stdc_count_ones_ui(unsigned int v) { 101 unsigned int n = 0; 102 while (v != 0) { 103 n += v & 1u; 104 v >>= 1u; 105 } 106 return n; 107 } 108 109 static inline unsigned int stdc_count_ones_ul(unsigned long v) { 110 unsigned int n = 0; 111 while (v != 0) { 112 n += (unsigned int)(v & 1ul); 113 v >>= 1u; 114 } 115 return n; 116 } 117 118 static inline unsigned int stdc_count_ones_ull(unsigned long long v) { 119 unsigned int n = 0; 120 while (v != 0) { 121 n += (unsigned int)(v & 1ull); 122 v >>= 1u; 123 } 124 return n; 125 } 126 127 static inline unsigned int stdc_leading_ones_uc(unsigned char v) { 128 return stdc_leading_zeros_uc((unsigned char)~v); 129 } 130 static inline unsigned int stdc_leading_ones_us(unsigned short v) { 131 return stdc_leading_zeros_us((unsigned short)~v); 132 } 133 static inline unsigned int stdc_leading_ones_ui(unsigned int v) { 134 return stdc_leading_zeros_ui(~v); 135 } 136 static inline unsigned int stdc_leading_ones_ul(unsigned long v) { 137 return stdc_leading_zeros_ul(~v); 138 } 139 static inline unsigned int stdc_leading_ones_ull(unsigned long long v) { 140 return stdc_leading_zeros_ull(~v); 141 } 142 143 static inline unsigned int stdc_trailing_ones_uc(unsigned char v) { 144 return stdc_trailing_zeros_uc((unsigned char)~v); 145 } 146 static inline unsigned int stdc_trailing_ones_us(unsigned short v) { 147 return stdc_trailing_zeros_us((unsigned short)~v); 148 } 149 static inline unsigned int stdc_trailing_ones_ui(unsigned int v) { 150 return stdc_trailing_zeros_ui(~v); 151 } 152 static inline unsigned int stdc_trailing_ones_ul(unsigned long v) { 153 return stdc_trailing_zeros_ul(~v); 154 } 155 static inline unsigned int stdc_trailing_ones_ull(unsigned long long v) { 156 return stdc_trailing_zeros_ull(~v); 157 } 158 159 static inline unsigned int stdc_count_zeros_uc(unsigned char v) { 160 return __KIT_STDBIT_WIDTH(unsigned char) - stdc_count_ones_uc(v); 161 } 162 static inline unsigned int stdc_count_zeros_us(unsigned short v) { 163 return __KIT_STDBIT_WIDTH(unsigned short) - stdc_count_ones_us(v); 164 } 165 static inline unsigned int stdc_count_zeros_ui(unsigned int v) { 166 return __KIT_STDBIT_WIDTH(unsigned int) - stdc_count_ones_ui(v); 167 } 168 static inline unsigned int stdc_count_zeros_ul(unsigned long v) { 169 return __KIT_STDBIT_WIDTH(unsigned long) - stdc_count_ones_ul(v); 170 } 171 static inline unsigned int stdc_count_zeros_ull(unsigned long long v) { 172 return __KIT_STDBIT_WIDTH(unsigned long long) - stdc_count_ones_ull(v); 173 } 174 175 static inline bool stdc_has_single_bit_uc(unsigned char v) { 176 return v != 0 && (unsigned char)(v & (unsigned char)(v - 1u)) == 0; 177 } 178 static inline bool stdc_has_single_bit_us(unsigned short v) { 179 return v != 0 && (unsigned short)(v & (unsigned short)(v - 1u)) == 0; 180 } 181 static inline bool stdc_has_single_bit_ui(unsigned int v) { 182 return v != 0 && (v & (v - 1u)) == 0; 183 } 184 static inline bool stdc_has_single_bit_ul(unsigned long v) { 185 return v != 0 && (v & (v - 1ul)) == 0; 186 } 187 static inline bool stdc_has_single_bit_ull(unsigned long long v) { 188 return v != 0 && (v & (v - 1ull)) == 0; 189 } 190 191 static inline unsigned int stdc_bit_width_uc(unsigned char v) { 192 return __KIT_STDBIT_WIDTH(unsigned char) - stdc_leading_zeros_uc(v); 193 } 194 static inline unsigned int stdc_bit_width_us(unsigned short v) { 195 return __KIT_STDBIT_WIDTH(unsigned short) - stdc_leading_zeros_us(v); 196 } 197 static inline unsigned int stdc_bit_width_ui(unsigned int v) { 198 return __KIT_STDBIT_WIDTH(unsigned int) - stdc_leading_zeros_ui(v); 199 } 200 static inline unsigned int stdc_bit_width_ul(unsigned long v) { 201 return __KIT_STDBIT_WIDTH(unsigned long) - stdc_leading_zeros_ul(v); 202 } 203 static inline unsigned int stdc_bit_width_ull(unsigned long long v) { 204 return __KIT_STDBIT_WIDTH(unsigned long long) - stdc_leading_zeros_ull(v); 205 } 206 207 static inline unsigned char stdc_bit_floor_uc(unsigned char v) { 208 return v == 0 ? 0 : (unsigned char)(1u << (stdc_bit_width_uc(v) - 1u)); 209 } 210 static inline unsigned short stdc_bit_floor_us(unsigned short v) { 211 return v == 0 ? 0 : (unsigned short)(1u << (stdc_bit_width_us(v) - 1u)); 212 } 213 static inline unsigned int stdc_bit_floor_ui(unsigned int v) { 214 return v == 0 ? 0 : (1u << (stdc_bit_width_ui(v) - 1u)); 215 } 216 static inline unsigned long stdc_bit_floor_ul(unsigned long v) { 217 return v == 0 ? 0 : (1ul << (stdc_bit_width_ul(v) - 1u)); 218 } 219 static inline unsigned long long stdc_bit_floor_ull(unsigned long long v) { 220 return v == 0 ? 0 : (1ull << (stdc_bit_width_ull(v) - 1u)); 221 } 222 223 static inline unsigned char stdc_bit_ceil_uc(unsigned char v) { 224 unsigned int w; 225 if (v <= 1u) return 1u; 226 w = stdc_bit_width_uc((unsigned char)(v - 1u)); 227 return w >= __KIT_STDBIT_WIDTH(unsigned char) ? 0 : (unsigned char)(1u << w); 228 } 229 static inline unsigned short stdc_bit_ceil_us(unsigned short v) { 230 unsigned int w; 231 if (v <= 1u) return 1u; 232 w = stdc_bit_width_us((unsigned short)(v - 1u)); 233 return w >= __KIT_STDBIT_WIDTH(unsigned short) ? 0 234 : (unsigned short)(1u << w); 235 } 236 static inline unsigned int stdc_bit_ceil_ui(unsigned int v) { 237 unsigned int w; 238 if (v <= 1u) return 1u; 239 w = stdc_bit_width_ui(v - 1u); 240 return w >= __KIT_STDBIT_WIDTH(unsigned int) ? 0 : (1u << w); 241 } 242 static inline unsigned long stdc_bit_ceil_ul(unsigned long v) { 243 unsigned int w; 244 if (v <= 1ul) return 1ul; 245 w = stdc_bit_width_ul(v - 1ul); 246 return w >= __KIT_STDBIT_WIDTH(unsigned long) ? 0 : (1ul << w); 247 } 248 static inline unsigned long long stdc_bit_ceil_ull(unsigned long long v) { 249 unsigned int w; 250 if (v <= 1ull) return 1ull; 251 w = stdc_bit_width_ull(v - 1ull); 252 return w >= __KIT_STDBIT_WIDTH(unsigned long long) ? 0 : (1ull << w); 253 } 254 255 static inline unsigned int stdc_first_leading_zero_uc(unsigned char v) { 256 return v == (unsigned char)~0u ? 0 : stdc_leading_ones_uc(v) + 1u; 257 } 258 static inline unsigned int stdc_first_leading_zero_us(unsigned short v) { 259 return v == (unsigned short)~0u ? 0 : stdc_leading_ones_us(v) + 1u; 260 } 261 static inline unsigned int stdc_first_leading_zero_ui(unsigned int v) { 262 return v == ~0u ? 0 : stdc_leading_ones_ui(v) + 1u; 263 } 264 static inline unsigned int stdc_first_leading_zero_ul(unsigned long v) { 265 return v == ~0ul ? 0 : stdc_leading_ones_ul(v) + 1u; 266 } 267 static inline unsigned int stdc_first_leading_zero_ull(unsigned long long v) { 268 return v == ~0ull ? 0 : stdc_leading_ones_ull(v) + 1u; 269 } 270 271 static inline unsigned int stdc_first_leading_one_uc(unsigned char v) { 272 return v == 0 ? 0 : stdc_leading_zeros_uc(v) + 1u; 273 } 274 static inline unsigned int stdc_first_leading_one_us(unsigned short v) { 275 return v == 0 ? 0 : stdc_leading_zeros_us(v) + 1u; 276 } 277 static inline unsigned int stdc_first_leading_one_ui(unsigned int v) { 278 return v == 0 ? 0 : stdc_leading_zeros_ui(v) + 1u; 279 } 280 static inline unsigned int stdc_first_leading_one_ul(unsigned long v) { 281 return v == 0 ? 0 : stdc_leading_zeros_ul(v) + 1u; 282 } 283 static inline unsigned int stdc_first_leading_one_ull(unsigned long long v) { 284 return v == 0 ? 0 : stdc_leading_zeros_ull(v) + 1u; 285 } 286 287 static inline unsigned int stdc_first_trailing_zero_uc(unsigned char v) { 288 return v == (unsigned char)~0u ? 0 : stdc_trailing_ones_uc(v) + 1u; 289 } 290 static inline unsigned int stdc_first_trailing_zero_us(unsigned short v) { 291 return v == (unsigned short)~0u ? 0 : stdc_trailing_ones_us(v) + 1u; 292 } 293 static inline unsigned int stdc_first_trailing_zero_ui(unsigned int v) { 294 return v == ~0u ? 0 : stdc_trailing_ones_ui(v) + 1u; 295 } 296 static inline unsigned int stdc_first_trailing_zero_ul(unsigned long v) { 297 return v == ~0ul ? 0 : stdc_trailing_ones_ul(v) + 1u; 298 } 299 static inline unsigned int stdc_first_trailing_zero_ull(unsigned long long v) { 300 return v == ~0ull ? 0 : stdc_trailing_ones_ull(v) + 1u; 301 } 302 303 static inline unsigned int stdc_first_trailing_one_uc(unsigned char v) { 304 return v == 0 ? 0 : stdc_trailing_zeros_uc(v) + 1u; 305 } 306 static inline unsigned int stdc_first_trailing_one_us(unsigned short v) { 307 return v == 0 ? 0 : stdc_trailing_zeros_us(v) + 1u; 308 } 309 static inline unsigned int stdc_first_trailing_one_ui(unsigned int v) { 310 return v == 0 ? 0 : stdc_trailing_zeros_ui(v) + 1u; 311 } 312 static inline unsigned int stdc_first_trailing_one_ul(unsigned long v) { 313 return v == 0 ? 0 : stdc_trailing_zeros_ul(v) + 1u; 314 } 315 static inline unsigned int stdc_first_trailing_one_ull(unsigned long long v) { 316 return v == 0 ? 0 : stdc_trailing_zeros_ull(v) + 1u; 317 } 318 319 #define __KIT_STDBIT_WIDTH_EXPR(v) ((unsigned)(sizeof(v) * CHAR_BIT)) 320 321 static inline unsigned long long __kit_stdbit_mask(unsigned int width) { 322 return width >= __KIT_STDBIT_WIDTH(unsigned long long) 323 ? ~0ull 324 : ((1ull << width) - 1ull); 325 } 326 327 static inline unsigned int __kit_stdbit_lz(unsigned long long v, 328 unsigned int width) { 329 v &= __kit_stdbit_mask(width); 330 if (v == 0) return width; 331 return (unsigned int)__builtin_clzll(v) - 332 (__KIT_STDBIT_WIDTH(unsigned long long) - width); 333 } 334 335 static inline unsigned int __kit_stdbit_tz(unsigned long long v, 336 unsigned int width) { 337 v &= __kit_stdbit_mask(width); 338 if (v == 0) return width; 339 return (unsigned int)__builtin_ctzll(v); 340 } 341 342 static inline unsigned int __kit_stdbit_pop(unsigned long long v, 343 unsigned int width) { 344 unsigned int n = 0; 345 v &= __kit_stdbit_mask(width); 346 while (v != 0) { 347 n += (unsigned int)(v & 1ull); 348 v >>= 1u; 349 } 350 return n; 351 } 352 353 static inline unsigned long long __kit_stdbit_floor(unsigned long long v, 354 unsigned int width) { 355 unsigned int w; 356 v &= __kit_stdbit_mask(width); 357 if (v == 0) return 0; 358 w = width - __kit_stdbit_lz(v, width) - 1u; 359 return 1ull << w; 360 } 361 362 static inline unsigned long long __kit_stdbit_ceil(unsigned long long v, 363 unsigned int width) { 364 unsigned int w; 365 v &= __kit_stdbit_mask(width); 366 if (v <= 1ull) return 1ull; 367 w = width - __kit_stdbit_lz(v - 1ull, width); 368 return w >= width ? 0ull : (1ull << w); 369 } 370 371 static inline bool __kit_stdbit_single(unsigned long long v, 372 unsigned int width) { 373 v &= __kit_stdbit_mask(width); 374 return v != 0 && (v & (v - 1ull)) == 0; 375 } 376 377 static inline unsigned int __kit_stdbit_first_lz(unsigned long long v, 378 unsigned int width) { 379 unsigned int n = __kit_stdbit_lz(v, width); 380 return n == width ? 0u : n + 1u; 381 } 382 383 static inline unsigned int __kit_stdbit_first_tz(unsigned long long v, 384 unsigned int width) { 385 unsigned int n = __kit_stdbit_tz(v, width); 386 return n == width ? 0u : n + 1u; 387 } 388 389 #define stdc_leading_zeros(v) \ 390 __kit_stdbit_lz((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 391 #define stdc_leading_ones(v) \ 392 __kit_stdbit_lz(~(unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 393 #define stdc_trailing_zeros(v) \ 394 __kit_stdbit_tz((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 395 #define stdc_trailing_ones(v) \ 396 __kit_stdbit_tz(~(unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 397 #define stdc_first_leading_zero(v) \ 398 __kit_stdbit_first_lz(~(unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 399 #define stdc_first_leading_one(v) \ 400 __kit_stdbit_first_lz((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 401 #define stdc_first_trailing_zero(v) \ 402 __kit_stdbit_first_tz(~(unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 403 #define stdc_first_trailing_one(v) \ 404 __kit_stdbit_first_tz((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 405 #define stdc_count_ones(v) \ 406 __kit_stdbit_pop((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 407 #define stdc_count_zeros(v) (__KIT_STDBIT_WIDTH_EXPR(v) - stdc_count_ones(v)) 408 #define stdc_has_single_bit(v) \ 409 __kit_stdbit_single((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 410 #define stdc_bit_width(v) \ 411 (__KIT_STDBIT_WIDTH_EXPR(v) - stdc_leading_zeros(v)) 412 #define stdc_bit_floor(v) \ 413 __kit_stdbit_floor((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 414 #define stdc_bit_ceil(v) \ 415 __kit_stdbit_ceil((unsigned long long)(v), __KIT_STDBIT_WIDTH_EXPR(v)) 416 417 #endif