Ruby 4.1.0dev (2026-11-09 revision 05e951b61434561a845b0888e5c61ac1735498f7)
bits.h
1#ifndef INTERNAL_BITS_H /*-*-C-*-vi:se ft=c:*/
2#define INTERNAL_BITS_H
28#include "ruby/internal/config.h"
29#include <limits.h> /* for CHAR_BITS */
30#include <stdint.h> /* for uintptr_t */
31#include "internal/compilers.h" /* for __has_builtin */
32
33#ifdef _MSC_VER
34# include <stdlib.h> /* for _byteswap_uint64 */
35#endif
36
37#if defined(HAVE_X86INTRIN_H)
38# include <x86intrin.h> /* for _lzcnt_u64 */
39#elif defined(_MSC_VER)
40# include <intrin.h> /* for the following intrinsics */
41#endif
42
43#if defined(_MSC_VER) && defined(__AVX__)
44# pragma intrinsic(__popcnt)
45# pragma intrinsic(__popcnt64)
46#endif
47
48#if defined(_MSC_VER) && defined(__AVX2__)
49# pragma intrinsic(__lzcnt)
50# pragma intrinsic(__lzcnt64)
51#endif
52
53#if defined(_MSC_VER)
54# pragma intrinsic(_rotl)
55# pragma intrinsic(_rotr)
56# ifdef _WIN64
57# pragma intrinsic(_rotl64)
58# pragma intrinsic(_rotr64)
59# endif
60# pragma intrinsic(_BitScanForward)
61# pragma intrinsic(_BitScanReverse)
62# ifdef _WIN64
63# pragma intrinsic(_BitScanForward64)
64# pragma intrinsic(_BitScanReverse64)
65# endif
66#endif
67
68#include "ruby/ruby.h" /* for VALUE */
69#include "internal/static_assert.h" /* for STATIC_ASSERT */
70
71/* The most significant bit of the lower part of half-long integer.
72 * If sizeof(long) == 4, this is 0x8000.
73 * If sizeof(long) == 8, this is 0x80000000.
74 */
75#define HALF_LONG_MSB ((SIGNED_VALUE)1<<((SIZEOF_LONG*CHAR_BIT-1)/2))
76
77#define SIGNED_INTEGER_TYPE_P(T) (0 > ((T)0)-1)
78
79#define SIGNED_INTEGER_MIN(T) \
80 ((sizeof(T) == sizeof(int8_t)) ? ((T)INT8_MIN) : \
81 ((sizeof(T) == sizeof(int16_t)) ? ((T)INT16_MIN) : \
82 ((sizeof(T) == sizeof(int32_t)) ? ((T)INT32_MIN) : \
83 ((sizeof(T) == sizeof(int64_t)) ? ((T)INT64_MIN) : \
84 0))))
85
86#define SIGNED_INTEGER_MAX(T) ((T)(SIGNED_INTEGER_MIN(T) ^ ((T)~(T)0)))
87
88#define UNSIGNED_INTEGER_MAX(T) ((T)~(T)0)
89
90#ifndef MUL_OVERFLOW_SIGNED_INTEGER_P
91#if __has_builtin(__builtin_mul_overflow_p)
92# define MUL_OVERFLOW_P(a, b) \
93 __builtin_mul_overflow_p((a), (b), (__typeof__(a * b))0)
94#elif __has_builtin(__builtin_mul_overflow)
95# define MUL_OVERFLOW_P(a, b) \
96 __extension__ ({ __typeof__(a) c; __builtin_mul_overflow((a), (b), &c); })
97#endif
98
99#define MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, min, max) ( \
100 (a) == 0 ? 0 : \
101 (a) == -1 ? (b) < -(max) : \
102 (a) > 0 ? \
103 ((b) > 0 ? (max) / (a) < (b) : (min) / (a) > (b)) : \
104 ((b) > 0 ? (min) / (a) < (b) : (max) / (a) > (b)))
105
106#define MUL_OVERFLOW_UNSIGNED_INTEGER_P(a, b, max) ((a) > 0 && ((b) > (max) / (a)))
107
108#if __has_builtin(__builtin_mul_overflow_p)
109/* __builtin_mul_overflow_p can take bitfield */
110/* and GCC permits bitfields for integers other than int */
111# define MUL_OVERFLOW_FIXNUM_P(a, b) \
112 __extension__ ({ \
113 struct { long fixnum : sizeof(long) * CHAR_BIT - 1; } c = { 0 }; \
114 __builtin_mul_overflow_p((a), (b), c.fixnum); \
115 })
116#else
117# define MUL_OVERFLOW_FIXNUM_P(a, b) \
118 MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, FIXNUM_MIN, FIXNUM_MAX)
119#endif
120
121#if defined(MUL_OVERFLOW_P) && defined(USE___BUILTIN_MUL_OVERFLOW_LONG_LONG)
122# define MUL_OVERFLOW_LONG_LONG_P(a, b) MUL_OVERFLOW_P(a, b)
123#else
124# define MUL_OVERFLOW_LONG_LONG_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, LLONG_MIN, LLONG_MAX)
125#endif
126
127#ifdef MUL_OVERFLOW_P
128# define MUL_OVERFLOW_LONG_P(a, b) MUL_OVERFLOW_P(a, b)
129# define MUL_OVERFLOW_INT_P(a, b) MUL_OVERFLOW_P(a, b)
130#else
131# define MUL_OVERFLOW_LONG_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, LONG_MIN, LONG_MAX)
132# define MUL_OVERFLOW_INT_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, INT_MIN, INT_MAX)
133#endif
134
135#if SIZEOF_RB_LEN_T > SIZEOF_LONG
136# define MUL_OVERFLOW_LEN_P(a, b) MUL_OVERFLOW_LONG_LONG_P(a, b)
137#elif SIZEOF_RB_LEN_T > SIZEOF_INT
138# define MUL_OVERFLOW_LEN_P(a, b) MUL_OVERFLOW_LONG_P(a, b)
139#else
140# define MUL_OVERFLOW_LEN_P(a, b) MUL_OVERFLOW_INT_P(a, b)
141#endif
142
143#define MUL_OVERFLOW_SIZE_P(a, b) MUL_OVERFLOW_UNSIGNED_INTEGER_P(a, b, SIZE_MAX)
144#endif
145
146#ifndef ADD_OVERFLOW_SIGNED_INTEGER_P
147#if __has_builtin(__builtin_add_overflow_p)
148# define ADD_OVERFLOW_P(a, b) \
149 __builtin_add_overflow_p((a), (b), (__typeof__(a * b))0)
150#elif __has_builtin(__builtin_add_overflow)
151# define ADD_OVERFLOW_P(a, b) \
152 __extension__ ({ __typeof__(a) c; __builtin_add_overflow((a), (b), &c); })
153#endif
154
155#define ADD_OVERFLOW_SIGNED_INTEGER_P(a, b, min, max) ( \
156 (a) > 0 ? (b) > (max) - (a) : (b) < (min) - (a))
157
158#define ADD_OVERFLOW_UNSIGNED_INTEGER_P(a, b, max) ((b) > (max) - (a))
159
160#if __has_builtin(__builtin_add_overflow_p)
161/* __builtin_add_overflow_p can take bitfield */
162/* and GCC permits bitfields for integers other than int */
163# define ADD_OVERFLOW_FIXNUM_P(a, b) \
164 __extension__ ({ \
165 struct { long fixnum : sizeof(long) * CHAR_BIT - 1; } c = { 0 }; \
166 __builtin_add_overflow_p((a), (b), c.fixnum); \
167 })
168#else
169# define ADD_OVERFLOW_FIXNUM_P(a, b) \
170 ADD_OVERFLOW_SIGNED_INTEGER_P(a, b, FIXNUM_MIN, FIXNUM_MAX)
171#endif
172
173#if defined(ADD_OVERFLOW_P) && defined(USE___BUILTIN_ADD_OVERFLOW_LONG_LONG)
174# define ADD_OVERFLOW_LONG_LONG_P(a, b) ADD_OVERFLOW_P(a, b)
175#else
176# define ADD_OVERFLOW_LONG_LONG_P(a, b) ADD_OVERFLOW_SIGNED_INTEGER_P(a, b, LLONG_MIN, LLONG_MAX)
177#endif
178
179#ifdef ADD_OVERFLOW_P
180# define ADD_OVERFLOW_LONG_P(a, b) ADD_OVERFLOW_P(a, b)
181# define ADD_OVERFLOW_INT_P(a, b) ADD_OVERFLOW_P(a, b)
182#else
183# define ADD_OVERFLOW_LONG_P(a, b) ADD_OVERFLOW_SIGNED_INTEGER_P(a, b, LONG_MIN, LONG_MAX)
184# define ADD_OVERFLOW_INT_P(a, b) ADD_OVERFLOW_SIGNED_INTEGER_P(a, b, INT_MIN, INT_MAX)
185#endif
186
187#if SIZEOF_RB_LEN_T > SIZEOF_LONG
188# define ADD_OVERFLOW_LEN_P(a, b) ADD_OVERFLOW_LONG_LONG_P(a, b)
189#elif SIZEOF_RB_LEN_T > SIZEOF_INT
190# define ADD_OVERFLOW_LEN_P(a, b) ADD_OVERFLOW_LONG_P(a, b)
191#else
192# define ADD_OVERFLOW_LEN_P(a, b) ADD_OVERFLOW_INT_P(a, b)
193#endif
194
195#define ADD_OVERFLOW_SIZE_P(a, b) ADD_OVERFLOW_UNSIGNED_INTEGER_P(a, b SIZE_MAX)
196#endif
197
198#ifndef SUB_OVERFLOW_SIGNED_INTEGER_P
199#if __has_builtin(__builtin_sub_overflow_p)
200# define SUB_OVERFLOW_P(a, b) \
201 __builtin_sub_overflow_p((a), (b), (__typeof__(a * b))0)
202#elif __has_builtin(__builtin_sub_overflow)
203# define SUB_OVERFLOW_P(a, b) \
204 __extension__ ({ __typeof__(a) c; __builtin_sub_overflow((a), (b), &c); })
205#endif
206
207#define SUB_OVERFLOW_SIGNED_INTEGER_P(a, b, min, max) ( \
208 (b) > 0 ? (a) < (min) + (b) : (a) > (max) + (b))
209
210#define SUB_OVERFLOW_UNSIGNED_INTEGER_P(a, b) ((a) < (b))
211
212#if __has_builtin(__builtin_sub_overflow_p)
213/* __builtin_sub_overflow_p can take bitfield */
214/* and GCC permits bitfields for integers other than int */
215# define SUB_OVERFLOW_FIXNUM_P(a, b) \
216 __extension__ ({ \
217 struct { long fixnum : sizeof(long) * CHAR_BIT - 1; } c = { 0 }; \
218 __builtin_sub_overflow_p((a), (b), c.fixnum); \
219 })
220#else
221# define SUB_OVERFLOW_FIXNUM_P(a, b) \
222 SUB_OVERFLOW_SIGNED_INTEGER_P(a, b, FIXNUM_MIN, FIXNUM_MAX)
223#endif
224
225#if defined(SUB_OVERFLOW_P) && defined(USE___BUILTIN_SUB_OVERFLOW_LONG_LONG)
226# define SUB_OVERFLOW_LONG_LONG_P(a, b) SUB_OVERFLOW_P(a, b)
227#else
228# define SUB_OVERFLOW_LONG_LONG_P(a, b) SUB_OVERFLOW_SIGNED_INTEGER_P(a, b, LLONG_MIN, LLONG_MAX)
229#endif
230
231#ifdef SUB_OVERFLOW_P
232# define SUB_OVERFLOW_LONG_P(a, b) SUB_OVERFLOW_P(a, b)
233# define SUB_OVERFLOW_INT_P(a, b) SUB_OVERFLOW_P(a, b)
234#else
235# define SUB_OVERFLOW_LONG_P(a, b) SUB_OVERFLOW_SIGNED_INTEGER_P(a, b, LONG_MIN, LONG_MAX)
236# define SUB_OVERFLOW_INT_P(a, b) SUB_OVERFLOW_SIGNED_INTEGER_P(a, b, INT_MIN, INT_MAX)
237#endif
238
239#if SIZEOF_RB_LEN_T > SIZEOF_LONG
240# define SUB_OVERFLOW_LEN_P(a, b) SUB_OVERFLOW_LONG_LONG_P(a, b)
241#elif SIZEOF_RB_LEN_T > SIZEOF_INT
242# define SUB_OVERFLOW_LEN_P(a, b) SUB_OVERFLOW_LONG_P(a, b)
243#else
244# define SUB_OVERFLOW_LEN_P(a, b) SUB_OVERFLOW_INT_P(a, b)
245#endif
246
247#define SUB_OVERFLOW_SIZE_P(a, b) SUB_OVERFLOW_UNSIGNED_INTEGER_P(a, b SIZE_MAX)
248#endif
249
250#ifdef HAVE_UINT128_T
251# define bit_length(x) \
252 (unsigned int) \
253 (sizeof(x) <= sizeof(int32_t) ? 32 - nlz_int32((uint32_t)(x)) : \
254 sizeof(x) <= sizeof(int64_t) ? 64 - nlz_int64((uint64_t)(x)) : \
255 128 - nlz_int128((uint128_t)(x)))
256#else
257# define bit_length(x) \
258 (unsigned int) \
259 (sizeof(x) <= sizeof(int32_t) ? 32 - nlz_int32((uint32_t)(x)) : \
260 64 - nlz_int64((uint64_t)(x)))
261#endif
262
263#ifndef swap16
264# define swap16 ruby_swap16
265#endif
266
267#ifndef swap32
268# define swap32 ruby_swap32
269#endif
270
271#ifndef swap64
272# define swap64 ruby_swap64
273#endif
274
275static inline uint16_t ruby_swap16(uint16_t);
276static inline uint32_t ruby_swap32(uint32_t);
277static inline uint64_t ruby_swap64(uint64_t);
278static inline unsigned nlz_int(unsigned x);
279static inline unsigned nlz_long(unsigned long x);
280static inline unsigned nlz_long_long(unsigned long long x);
281static inline unsigned nlz_intptr(uintptr_t x);
282static inline unsigned nlz_int32(uint32_t x);
283static inline unsigned nlz_int64(uint64_t x);
284#ifdef HAVE_UINT128_T
285static inline unsigned nlz_int128(uint128_t x);
286#endif
287static inline unsigned rb_popcount32(uint32_t x);
288static inline unsigned rb_popcount64(uint64_t x);
289static inline unsigned rb_popcount_intptr(uintptr_t x);
290static inline int ntz_int32(uint32_t x);
291static inline int ntz_int64(uint64_t x);
292static inline int ntz_intptr(uintptr_t x);
293static inline VALUE RUBY_BIT_ROTL(VALUE, int);
294static inline VALUE RUBY_BIT_ROTR(VALUE, int);
295
296static inline uint16_t
297ruby_swap16(uint16_t x)
298{
299#if __has_builtin(__builtin_bswap16)
300 return __builtin_bswap16(x);
301
302#elif defined(_MSC_VER)
303 return _byteswap_ushort(x);
304
305#else
306 return (x << 8) | (x >> 8);
307
308#endif
309}
310
311static inline uint32_t
312ruby_swap32(uint32_t x)
313{
314#if __has_builtin(__builtin_bswap32)
315 return __builtin_bswap32(x);
316
317#elif defined(_MSC_VER)
318 return _byteswap_ulong(x);
319
320#else
321 x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
322 x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
323 return x;
324
325#endif
326}
327
328static inline uint64_t
329ruby_swap64(uint64_t x)
330{
331#if __has_builtin(__builtin_bswap64)
332 return __builtin_bswap64(x);
333
334#elif defined(_MSC_VER)
335 return _byteswap_uint64(x);
336
337#else
338 x = ((x & 0x00000000FFFFFFFFULL) << 32) | ((x & 0xFFFFFFFF00000000ULL) >> 32);
339 x = ((x & 0x0000FFFF0000FFFFULL) << 16) | ((x & 0xFFFF0000FFFF0000ULL) >> 16);
340 x = ((x & 0x00FF00FF00FF00FFULL) << 8) | ((x & 0xFF00FF00FF00FF00ULL) >> 8);
341 return x;
342
343#endif
344}
345
346static inline unsigned int
347nlz_int32(uint32_t x)
348{
349#if defined(_MSC_VER) && defined(__AVX2__)
350 /* Note: It seems there is no such thing like __LZCNT__ predefined in MSVC.
351 * AMD CPUs have had this instruction for decades (since K10) but for
352 * Intel, Haswell is the oldest one. We need to use __AVX2__ for maximum
353 * safety. */
354 return (unsigned int)__lzcnt(x);
355
356#elif defined(__x86_64__) && defined(__LZCNT__)
357 return (unsigned int)_lzcnt_u32(x);
358
359#elif defined(_MSC_VER) /* &&! defined(__AVX2__) */
360 unsigned long r;
361 return _BitScanReverse(&r, x) ? (31 - (int)r) : 32;
362
363#elif __has_builtin(__builtin_clz)
364 STATIC_ASSERT(sizeof_int, sizeof(int) * CHAR_BIT == 32);
365 return x ? (unsigned int)__builtin_clz(x) : 32;
366
367#else
368 uint32_t y;
369 unsigned n = 32;
370 y = x >> 16; if (y) {n -= 16; x = y;}
371 y = x >> 8; if (y) {n -= 8; x = y;}
372 y = x >> 4; if (y) {n -= 4; x = y;}
373 y = x >> 2; if (y) {n -= 2; x = y;}
374 y = x >> 1; if (y) {return n - 2;}
375 return (unsigned int)(n - x);
376#endif
377}
378
379static inline unsigned int
380nlz_int64(uint64_t x)
381{
382#if defined(_MSC_VER) && defined(__AVX2__)
383 return (unsigned int)__lzcnt64(x);
384
385#elif defined(__x86_64__) && defined(__LZCNT__)
386 return (unsigned int)_lzcnt_u64(x);
387
388#elif defined(_WIN64) && defined(_MSC_VER) /* &&! defined(__AVX2__) */
389 unsigned long r;
390 return _BitScanReverse64(&r, x) ? (63u - (unsigned int)r) : 64;
391
392#elif __has_builtin(__builtin_clzl)
393 if (x == 0) {
394 return 64;
395 }
396 else if (sizeof(long) * CHAR_BIT == 64) {
397 return (unsigned int)__builtin_clzl((unsigned long)x);
398 }
399 else if (sizeof(long long) * CHAR_BIT == 64) {
400 return (unsigned int)__builtin_clzll((unsigned long long)x);
401 }
402 else {
403 /* :FIXME: Is there a way to make this branch a compile-time error? */
404 UNREACHABLE_RETURN(~0);
405 }
406
407#else
408 uint64_t y;
409 unsigned int n = 64;
410 y = x >> 32; if (y) {n -= 32; x = y;}
411 y = x >> 16; if (y) {n -= 16; x = y;}
412 y = x >> 8; if (y) {n -= 8; x = y;}
413 y = x >> 4; if (y) {n -= 4; x = y;}
414 y = x >> 2; if (y) {n -= 2; x = y;}
415 y = x >> 1; if (y) {return n - 2;}
416 return (unsigned int)(n - x);
417
418#endif
419}
420
421#ifdef HAVE_UINT128_T
422static inline unsigned int
423nlz_int128(uint128_t x)
424{
425 uint64_t y = (uint64_t)(x >> 64);
426
427 if (x == 0) {
428 return 128;
429 }
430 else if (y == 0) {
431 return (unsigned int)nlz_int64(x) + 64;
432 }
433 else {
434 return (unsigned int)nlz_int64(y);
435 }
436}
437#endif
438
439static inline unsigned int
440nlz_int(unsigned int x)
441{
442 if (sizeof(unsigned int) * CHAR_BIT == 32) {
443 return nlz_int32((uint32_t)x);
444 }
445 else if (sizeof(unsigned int) * CHAR_BIT == 64) {
446 return nlz_int64((uint64_t)x);
447 }
448 else {
449 UNREACHABLE_RETURN(~0);
450 }
451}
452
453static inline unsigned int
454nlz_long(unsigned long x)
455{
456 if (sizeof(unsigned long) * CHAR_BIT == 32) {
457 return nlz_int32((uint32_t)x);
458 }
459 else if (sizeof(unsigned long) * CHAR_BIT == 64) {
460 return nlz_int64((uint64_t)x);
461 }
462 else {
463 UNREACHABLE_RETURN(~0);
464 }
465}
466
467static inline unsigned int
468nlz_long_long(unsigned long long x)
469{
470 if (sizeof(unsigned long long) * CHAR_BIT == 64) {
471 return nlz_int64((uint64_t)x);
472 }
473#ifdef HAVE_UINT128_T
474 else if (sizeof(unsigned long long) * CHAR_BIT == 128) {
475 return nlz_int128((uint128_t)x);
476 }
477#endif
478 else {
479 UNREACHABLE_RETURN(~0);
480 }
481}
482
483static inline unsigned int
484nlz_intptr(uintptr_t x)
485{
486 if (sizeof(uintptr_t) == sizeof(unsigned int)) {
487 return nlz_int((unsigned int)x);
488 }
489 if (sizeof(uintptr_t) == sizeof(unsigned long)) {
490 return nlz_long((unsigned long)x);
491 }
492 if (sizeof(uintptr_t) == sizeof(unsigned long long)) {
493 return nlz_long_long((unsigned long long)x);
494 }
495 else {
496 UNREACHABLE_RETURN(~0);
497 }
498}
499
500static inline unsigned int
501rb_popcount32(uint32_t x)
502{
503#if defined(_MSC_VER) && defined(__AVX__)
504 /* Note: CPUs since Nehalem and Barcelona have had this instruction so SSE
505 * 4.2 should suffice, but it seems there is no such thing like __SSE_4_2__
506 * predefined macro in MSVC. They do have __AVX__ so use it instead. */
507 return (unsigned int)__popcnt(x);
508
509#elif __has_builtin(__builtin_popcount)
510 STATIC_ASSERT(sizeof_int, sizeof(int) * CHAR_BIT >= 32);
511 return (unsigned int)__builtin_popcount(x);
512
513#else
514 x = (x & 0x55555555) + (x >> 1 & 0x55555555);
515 x = (x & 0x33333333) + (x >> 2 & 0x33333333);
516 x = (x & 0x07070707) + (x >> 4 & 0x07070707);
517 x = (x & 0x000f000f) + (x >> 8 & 0x000f000f);
518 x = (x & 0x0000001f) + (x >>16 & 0x0000001f);
519 return (unsigned int)x;
520
521#endif
522}
523
524static inline unsigned int
525rb_popcount64(uint64_t x)
526{
527#if defined(_MSC_VER) && defined(__AVX__)
528 return (unsigned int)__popcnt64(x);
529
530#elif __has_builtin(__builtin_popcount)
531 if (sizeof(long) * CHAR_BIT == 64) {
532 return (unsigned int)__builtin_popcountl((unsigned long)x);
533 }
534 else if (sizeof(long long) * CHAR_BIT == 64) {
535 return (unsigned int)__builtin_popcountll((unsigned long long)x);
536 }
537 else {
538 /* :FIXME: Is there a way to make this branch a compile-time error? */
539 UNREACHABLE_RETURN(~0);
540 }
541
542#else
543 x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555);
544 x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);
545 x = (x & 0x0707070707070707) + (x >> 4 & 0x0707070707070707);
546 x = (x & 0x000f000f000f000f) + (x >> 8 & 0x000f000f000f000f);
547 x = (x & 0x0000001f0000001f) + (x >>16 & 0x0000001f0000001f);
548 x = (x & 0x000000000000003f) + (x >>32 & 0x000000000000003f);
549 return (unsigned int)x;
550
551#endif
552}
553
554static inline unsigned int
555rb_popcount_intptr(uintptr_t x)
556{
557 if (sizeof(uintptr_t) * CHAR_BIT == 64) {
558 return rb_popcount64((uint64_t)x);
559 }
560 else if (sizeof(uintptr_t) * CHAR_BIT == 32) {
561 return rb_popcount32((uint32_t)x);
562 }
563 else {
564 UNREACHABLE_RETURN(~0);
565 }
566}
567
568static inline int
569ntz_int32(uint32_t x)
570{
571#if defined(__x86_64__) && defined(__BMI__)
572 return (unsigned)_tzcnt_u32(x);
573
574#elif defined(_MSC_VER)
575 /* :FIXME: Is there any way to issue TZCNT instead of BSF, apart from using
576 * assembly? Because issuing LZCNT seems possible (see nlz.h). */
577 unsigned long r;
578 return _BitScanForward(&r, x) ? (int)r : 32;
579
580#elif __has_builtin(__builtin_ctz)
581 STATIC_ASSERT(sizeof_int, sizeof(int) * CHAR_BIT == 32);
582 return x ? (unsigned)__builtin_ctz(x) : 32;
583
584#else
585 return rb_popcount32((~x) & (x-1));
586
587#endif
588}
589
590static inline int
591ntz_int64(uint64_t x)
592{
593#if defined(__x86_64__) && defined(__BMI__)
594 return (unsigned)_tzcnt_u64(x);
595
596#elif defined(_WIN64) && defined(_MSC_VER)
597 unsigned long r;
598 return _BitScanForward64(&r, x) ? (int)r : 64;
599
600#elif __has_builtin(__builtin_ctzl)
601 if (x == 0) {
602 return 64;
603 }
604 else if (sizeof(long) * CHAR_BIT == 64) {
605 return (unsigned)__builtin_ctzl((unsigned long)x);
606 }
607 else if (sizeof(long long) * CHAR_BIT == 64) {
608 return (unsigned)__builtin_ctzll((unsigned long long)x);
609 }
610 else {
611 /* :FIXME: Is there a way to make this branch a compile-time error? */
612 UNREACHABLE_RETURN(~0);
613 }
614
615#else
616 return rb_popcount64((~x) & (x-1));
617
618#endif
619}
620
621static inline int
622ntz_intptr(uintptr_t x)
623{
624 if (sizeof(uintptr_t) * CHAR_BIT == 64) {
625 return ntz_int64((uint64_t)x);
626 }
627 else if (sizeof(uintptr_t) * CHAR_BIT == 32) {
628 return ntz_int32((uint32_t)x);
629 }
630 else {
631 UNREACHABLE_RETURN(~0);
632 }
633}
634
635static inline VALUE
636RUBY_BIT_ROTL(VALUE v, int n)
637{
638#if __has_builtin(__builtin_rotateleft32) && (SIZEOF_VALUE * CHAR_BIT == 32)
639 return __builtin_rotateleft32(v, n);
640
641#elif __has_builtin(__builtin_rotateleft64) && (SIZEOF_VALUE * CHAR_BIT == 64)
642 return __builtin_rotateleft64(v, n);
643
644#elif defined(_MSC_VER) && (SIZEOF_VALUE * CHAR_BIT == 32)
645 return _rotl(v, n);
646
647#elif defined(_MSC_VER) && (SIZEOF_VALUE * CHAR_BIT == 64)
648 return _rotl64(v, n);
649
650#elif defined(_lrotl) && (SIZEOF_VALUE == SIZEOF_LONG)
651 return _lrotl(v, n);
652
653#else
654 const int m = (sizeof(VALUE) * CHAR_BIT) - 1;
655 return (v << (n & m)) | (v >> (-n & m));
656#endif
657}
658
659static inline VALUE
660RUBY_BIT_ROTR(VALUE v, int n)
661{
662#if __has_builtin(__builtin_rotateright32) && (SIZEOF_VALUE * CHAR_BIT == 32)
663 return __builtin_rotateright32(v, n);
664
665#elif __has_builtin(__builtin_rotateright64) && (SIZEOF_VALUE * CHAR_BIT == 64)
666 return __builtin_rotateright64(v, n);
667
668#elif defined(_MSC_VER) && (SIZEOF_VALUE * CHAR_BIT == 32)
669 return _rotr(v, n);
670
671#elif defined(_MSC_VER) && (SIZEOF_VALUE * CHAR_BIT == 64)
672 return _rotr64(v, n);
673
674#elif defined(_lrotr) && (SIZEOF_VALUE == SIZEOF_LONG)
675 return _lrotr(v, n);
676
677#else
678 const int m = (sizeof(VALUE) * CHAR_BIT) - 1;
679 return (v << (-n & m)) | (v >> (n & m));
680#endif
681}
682
683#endif /* INTERNAL_BITS_H */
UNREACHABLE_RETURN
#define UNREACHABLE_RETURN
Old name of RBIMPL_UNREACHABLE_RETURN.
Definition assume.h:29
VALUE
uintptr_t VALUE
Type that represents a Ruby object.
Definition value.h:40
Generated by doxygen 1.9.8