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