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