ruby-changes:59517
From: =E5=8D=9C=E9=83=A8=E6=98=8C=E5=B9=B3 <ko1@a...>
Date: Fri, 27 Dec 2019 09:43:31 +0900 (JST)
Subject: [ruby-changes:59517] 64ec438b5b (master): internal/bits.h rework
https://git.ruby-lang.org/ruby.git/commit/?id=64ec438b5b From 64ec438b5bbeb6b29dd0393df01cc6ae3f5564da Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?=E5=8D=9C=E9=83=A8=E6=98=8C=E5=B9=B3?= <shyouhei@r...> Date: Mon, 2 Dec 2019 15:50:11 +0900 Subject: internal/bits.h rework Improving readability by converting some macros into inline functions. Also improved support for recent x86_64 processors, which have better instructions for the purposes. diff --git a/internal/bits.h b/internal/bits.h index 1551d50..2530bd8 100644 --- a/internal/bits.h +++ b/internal/bits.h @@ -8,7 +8,44 @@ https://github.com/ruby/ruby/blob/trunk/internal/bits.h#L8 * Permission is hereby granted, to either redistribute and/or * modify this file, provided that the conditions mentioned in the * file COPYING are met. Consult the file for details. + * @see Henry S. Warren Jr., "Hacker's Delight" (2nd ed.), 2013. + * @see SEI CERT C Coding Standard INT32-C. "Ensure that operations on + * signed integers do not result in overflow" + * @see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html + * @see https://clang.llvm.org/docs/LanguageExtensions.html#builtin-rotateleft + * @see https://clang.llvm.org/docs/LanguageExtensions.html#builtin-rotateright + * @see https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/byteswap-uint64-byteswap-ulong-byteswap-ushort + * @see https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64 + * @see https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64 + * @see https://docs.microsoft.com/en-us/cpp/intrinsics/lzcnt16-lzcnt-lzcnt64 + * @see https://docs.microsoft.com/en-us/cpp/intrinsics/popcnt16-popcnt-popcnt64 + * @see https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_lzcnt_u32 + * @see https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_tzcnt_u32 */ +#include "ruby/config.h" +#include <limits.h> /* for CHAR_BITS */ +#include <stdint.h> /* for uintptr_t */ + +#ifdef _MSC_VER +# include <stdlib.h> /* for _byteswap_uint64 */ +#endif + +#if defined(__x86_64__) && defined(__LZCNT__) && ! defined(MJIT_HEADER) +# /* Rule out MJIT_HEADER, which does not interface well with <immintrin.h> */ +# include <immintrin.h> /* for _lzcnt_u64 */ +#endif + +#if defined(_MSC_VER) && defined(_WIN64) +# include <intrin.h> /* for the following intrinsics */ +# pragma intrinsic(_BitScanForward) +# pragma intrinsic(_BitScanForward64) +# pragma intrinsic(_BitScanReverse) +# pragma intrinsic(_BitScanReverse64) +#endif + +#include "ruby/ruby.h" /* for VALUE */ +#include "internal/compilers.h" /* for __has_builtin */ +#include "internal/static_assert.h" /* for STATIC_ASSERT */ /* The most significant bit of the lower part of half-long integer. * If sizeof(long) == 4, this is 0x8000. @@ -16,19 +53,25 @@ https://github.com/ruby/ruby/blob/trunk/internal/bits.h#L53 */ #define HALF_LONG_MSB ((SIGNED_VALUE)1<<((SIZEOF_LONG*CHAR_BIT-1)/2)) -#define SIGNED_INTEGER_TYPE_P(int_type) (0 > ((int_type)0)-1) -#define SIGNED_INTEGER_MAX(sint_type) \ - (sint_type) \ - ((((sint_type)1) << (sizeof(sint_type) * CHAR_BIT - 2)) | \ - ((((sint_type)1) << (sizeof(sint_type) * CHAR_BIT - 2)) - 1)) -#define SIGNED_INTEGER_MIN(sint_type) (-SIGNED_INTEGER_MAX(sint_type)-1) -#define UNSIGNED_INTEGER_MAX(uint_type) (~(uint_type)0) -#ifdef HAVE_BUILTIN___BUILTIN_MUL_OVERFLOW_P -#define MUL_OVERFLOW_P(a, b) \ +#define SIGNED_INTEGER_TYPE_P(T) (0 > ((T)0)-1) + +#define SIGNED_INTEGER_MIN(T) \ + ((sizeof(T) == sizeof(int8_t)) ? ((T)INT8_MIN) : \ + ((sizeof(T) == sizeof(int16_t)) ? ((T)INT16_MIN) : \ + ((sizeof(T) == sizeof(int32_t)) ? ((T)INT32_MIN) : \ + ((sizeof(T) == sizeof(int64_t)) ? ((T)INT64_MIN) : \ + 0)))) + +#define SIGNED_INTEGER_MAX(T) ((T)(SIGNED_INTEGER_MIN(T) ^ ((T)~(T)0))) + +#define UNSIGNED_INTEGER_MAX(T) ((T)~(T)0) + +#if __has_builtin(__builtin_mul_overflow_p) +# define MUL_OVERFLOW_P(a, b) \ __builtin_mul_overflow_p((a), (b), (__typeof__(a * b))0) -#elif defined HAVE_BUILTIN___BUILTIN_MUL_OVERFLOW -#define MUL_OVERFLOW_P(a, b) \ - RB_GNUC_EXTENSION_BLOCK(__typeof__(a) c; __builtin_mul_overflow((a), (b), &c)) +#elif __has_builtin(__builtin_mul_overflow) +# define MUL_OVERFLOW_P(a, b) \ + __extension__ ({ __typeof__(a) c; __builtin_mul_overflow((a), (b), &c); }) #endif #define MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, min, max) ( \ @@ -38,121 +81,137 @@ https://github.com/ruby/ruby/blob/trunk/internal/bits.h#L81 ((b) > 0 ? (max) / (a) < (b) : (min) / (a) > (b)) : \ ((b) > 0 ? (min) / (a) < (b) : (max) / (a) > (b))) -#ifdef HAVE_BUILTIN___BUILTIN_MUL_OVERFLOW_P +#if __has_builtin(__builtin_mul_overflow_p) /* __builtin_mul_overflow_p can take bitfield */ /* and GCC permits bitfields for integers other than int */ -#define MUL_OVERFLOW_FIXNUM_P(a, b) RB_GNUC_EXTENSION_BLOCK( \ - struct { long fixnum : SIZEOF_LONG * CHAR_BIT - 1; } c; \ - __builtin_mul_overflow_p((a), (b), c.fixnum); \ -) +# define MUL_OVERFLOW_FIXNUM_P(a, b) \ + __extension__ ({ \ + struct { long fixnum : sizeof(long) * CHAR_BIT - 1; } c; \ + __builtin_mul_overflow_p((a), (b), c.fixnum); \ + }) #else -#define MUL_OVERFLOW_FIXNUM_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, FIXNUM_MIN, FIXNUM_MAX) +# define MUL_OVERFLOW_FIXNUM_P(a, b) \ + MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, FIXNUM_MIN, FIXNUM_MAX) #endif #ifdef MUL_OVERFLOW_P -#define MUL_OVERFLOW_LONG_LONG_P(a, b) MUL_OVERFLOW_P(a, b) -#define MUL_OVERFLOW_LONG_P(a, b) MUL_OVERFLOW_P(a, b) -#define MUL_OVERFLOW_INT_P(a, b) MUL_OVERFLOW_P(a, b) +# define MUL_OVERFLOW_LONG_LONG_P(a, b) MUL_OVERFLOW_P(a, b) +# define MUL_OVERFLOW_LONG_P(a, b) MUL_OVERFLOW_P(a, b) +# define MUL_OVERFLOW_INT_P(a, b) MUL_OVERFLOW_P(a, b) #else -#define MUL_OVERFLOW_LONG_LONG_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, LLONG_MIN, LLONG_MAX) -#define MUL_OVERFLOW_LONG_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, LONG_MIN, LONG_MAX) -#define MUL_OVERFLOW_INT_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, INT_MIN, INT_MAX) +# define MUL_OVERFLOW_LONG_LONG_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, LLONG_MIN, LLONG_MAX) +# define MUL_OVERFLOW_LONG_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, LONG_MIN, LONG_MAX) +# define MUL_OVERFLOW_INT_P(a, b) MUL_OVERFLOW_SIGNED_INTEGER_P(a, b, INT_MIN, INT_MAX) #endif -#ifndef swap16 -# ifdef HAVE_BUILTIN___BUILTIN_BSWAP16 -# define swap16(x) __builtin_bswap16(x) -# endif +#ifdef HAVE_UINT128_T +# define bit_length(x) \ + (unsigned int) \ + (sizeof(x) <= sizeof(int32_t) ? 32 - nlz_int32((uint32_t)(x)) : \ + sizeof(x) <= sizeof(int64_t) ? 64 - nlz_int64((uint64_t)(x)) : \ + 128 - nlz_int128((uint128_t)(x))) +#else +# define bit_length(x) \ + (unsigned int) \ + (sizeof(x) <= sizeof(int32_t) ? 32 - nlz_int32((uint32_t)(x)) : \ + 64 - nlz_int64((uint64_t)(x))) #endif -#ifndef swap16 -# define swap16(x) ((uint16_t)((((x)&0xFF)<<8) | (((x)>>8)&0xFF))) +static inline uint16_t swap16(uint16_t); +static inline uint32_t swap32(uint32_t); +static inline uint64_t swap64(uint64_t); +static inline unsigned nlz_int(unsigned x); +static inline unsigned nlz_long(unsigned long x); +static inline unsigned nlz_long_long(unsigned long long x); +static inline unsigned nlz_intptr(uintptr_t x); +static inline unsigned nlz_int32(uint32_t x); +static inline unsigned nlz_int64(uint64_t x); +#ifdef HAVE_UINT128_T +static inline unsigned nlz_int128(uint128_t x); #endif +static inline unsigned rb_popcount32(uint32_t x); +static inline unsigned rb_popcount64(uint64_t x); +static inline unsigned rb_popcount_intptr(uintptr_t x); +static inline int ntz_int32(uint32_t x); +static inline int ntz_int64(uint64_t x); +static inline int ntz_intptr(uintptr_t x); +static inline VALUE RUBY_BIT_ROTL(VALUE, int); +static inline VALUE RUBY_BIT_ROTR(VALUE, int); -#ifndef swap32 -# ifdef HAVE_BUILTIN___BUILTIN_BSWAP32 -# define swap32(x) __builtin_bswap32(x) -# endif -#endif +static inline uint16_t +swap16(uint16_t x) +{ +#if __has_builtin(__builtin_bswap16) + return __builtin_bswap16(x); -#ifndef swap32 -# define swap32(x) ((uint32_t)((((x)&0xFF)<<24) \ - |(((x)>>24)&0xFF) \ - |(((x)&0x0000FF00)<<8) \ - |(((x)&0x00FF0000)>>8) )) -#endif +#elif defined(_MSC_VER) + return _byteswap_ushort(x); + +#else + return (x << 8) | (x >> 8); -#ifndef swap64 -# ifdef HAVE_BUILTIN___BUILTIN_BSWAP64 -# define swap64(x) __builtin_bswap64(x) -# endif #endif +} + +static inline uint32_t +swap32(uint32_t x) +{ +#if __has_builtin(__builtin_bswap32) + return __builtin_bswap32(x); + +#elif defined(_MSC_VER) + return _byteswap_ulong(x); + +#else + x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16); + x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8); + return x; -#ifndef swap64 -# ifdef HAVE_INT64_T -# define byte_in_64bit(n) ((uint64_t)0xff << (n)) -# define swap64(x) ((uint64_t)((((x)&byte_in_64bit(0))<<56) \ - |(((x)>>56)&0xFF) \ - |(((x)&byte_in_64bit(8))<<40) \ - |(((x)&byte_in_64bit(48))>>40) \ - |(((x)&byte_in_64bit(16))<<24) \ - |(((x)&byte_in_64bit(40))>>24) \ - |(((x)&byte_in_64bit(24))<<8) \ - |(((x)&byte_in_64bit(32))>>8))) -# endif #endif +} -static inline unsigned int -nlz_int(unsigned int x) +static inline uint64_t +swap64(uint64_t x) { -#if defined(HAVE_BUILTIN___BUILTIN_CLZ) - if (x == 0) retur (... truncated) -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/