lib/builtin.c

   1 /* uses alias to allow building with gcc/clang */
   2 #ifdef __TINYC__
   3 #define BUILTIN(x)      __builtin_##x
   4 #define BUILTINN(x)     "__builtin_" # x
   5 #else
   6 #define BUILTIN(x)      __tcc_builtin_##x
   7 #define BUILTINN(x)     "__tcc_builtin_" # x
   8 #endif
   9
  10 /* ---------------------------------------------- */
  11 /* This file implements:
  12  * __builtin_ffs
  13  * __builtin_clz
  14  * __builtin_ctz
  15  * __builtin_clrsb
  16  * __builtin_popcount
  17  * __builtin_parity
  18  * for int, long and long long
  19  */
  20
  21 static const unsigned char table_1_32[] = {
  22      0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,
  23     31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
  24 };
  25 static const unsigned char table_2_32[32] = {
  26     31, 22, 30, 21, 18, 10, 29,  2, 20, 17, 15, 13,  9,  6, 28,  1,
  27     23, 19, 11,  3, 16, 14,  7, 24, 12,  4,  8, 25,  5, 26, 27,  0
  28 };
  29 static const unsigned char table_1_64[] = {
  30      0,  1,  2, 53,  3,  7, 54, 27,  4, 38, 41,  8, 34, 55, 48, 28,
  31     62,  5, 39, 46, 44, 42, 22,  9, 24, 35, 59, 56, 49, 18, 29, 11,
  32     63, 52,  6, 26, 37, 40, 33, 47, 61, 45, 43, 21, 23, 58, 17, 10,
  33     51, 25, 36, 32, 60, 20, 57, 16, 50, 31, 19, 15, 30, 14, 13, 12
  34 };
  35 static const unsigned char table_2_64[] = {
  36     63, 16, 62,  7, 15, 36, 61,  3,  6, 14, 22, 26, 35, 47, 60,  2,
  37      9,  5, 28, 11, 13, 21, 42, 19, 25, 31, 34, 40, 46, 52, 59,  1,
  38     17,  8, 37,  4, 23, 27, 48, 10, 29, 12, 43, 20, 32, 41, 53, 18,
  39     38, 24, 49, 30, 44, 33, 54, 39, 50, 45, 55, 51, 56, 57, 58,  0
  40 };
  41
  42 #define FFSI(x) \
  43     return table_1_32[((x & -x) * 0x077cb531u) >> 27] + (x != 0);
  44 #define FFSL(x) \
  45     return table_1_64[((x & -x) * 0x022fdd63cc95386dull) >> 58] + (x != 0);
  46 #define CTZI(x) \
  47     return table_1_32[((x & -x) * 0x077cb531u) >> 27];
  48 #define CTZL(x) \
  49     return table_1_64[((x & -x) * 0x022fdd63cc95386dull) >> 58];
  50 #define CLZI(x)   \
  51     x |= x >> 1;  \
  52     x |= x >> 2;  \
  53     x |= x >> 4;  \
  54     x |= x >> 8;  \
  55     x |= x >> 16; \
  56     return table_2_32[(x * 0x07c4acddu) >> 27];
  57 #define CLZL(x)   \
  58     x |= x >> 1;  \
  59     x |= x >> 2;  \
  60     x |= x >> 4;  \
  61     x |= x >> 8;  \
  62     x |= x >> 16; \
  63     x |= x >> 32; \
  64     return table_2_64[x * 0x03f79d71b4cb0a89ull >> 58];
  65 #define POPCOUNTI(x, m)                                                   \
  66     x = x - ((x >> 1) & 0x55555555);                                      \
  67     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);                       \
  68     x = (x + (x >> 4)) & 0xf0f0f0f;                                       \
  69     return ((x * 0x01010101) >> 24) & m;
  70 #define POPCOUNTL(x, m)                                                   \
  71     x = x - ((x >> 1) & 0x5555555555555555ull);                           \
  72     x = (x & 0x3333333333333333ull) + ((x >> 2) & 0x3333333333333333ull); \
  73     x = (x + (x >> 4)) & 0xf0f0f0f0f0f0f0full;                            \
  74     return ((x * 0x0101010101010101ull) >> 56) & m;
  75
  76 /* Returns one plus the index of the least significant 1-bit of x,
  77    or if x is zero, returns zero. */
  78 int BUILTIN(ffs) (int x) { FFSI(x) }
  79 int BUILTIN(ffsll) (long long x) { FFSL(x) }
  80 #if __SIZEOF_LONG__ == 4
  81 int BUILTIN(ffsl) (long x) __attribute__((alias(BUILTINN(ffs))));
  82 #else
  83 int BUILTIN(ffsl) (long x) __attribute__((alias(BUILTINN(ffsll))));
  84 #endif
  85
  86 /* Returns the number of leading 0-bits in x, starting at the most significant
  87    bit position. If x is 0, the result is undefined.  */
  88 int BUILTIN(clz) (unsigned int x) { CLZI(x) }
  89 int BUILTIN(clzll) (unsigned long long x) { CLZL(x) }
  90 #if __SIZEOF_LONG__ == 4
  91 int BUILTIN(clzl) (unsigned long x) __attribute__((alias(BUILTINN(clz))));
  92 #else
  93 int BUILTIN(clzl) (unsigned long x) __attribute__((alias(BUILTINN(clzll))));
  94 #endif
  95
  96 /* Returns the number of trailing 0-bits in x, starting at the least
  97    significant bit position. If x is 0, the result is undefined. */
  98 int BUILTIN(ctz) (unsigned int x) { CTZI(x) }
  99 int BUILTIN(ctzll) (unsigned long long x) { CTZL(x) }
 100 #if __SIZEOF_LONG__ == 4
 101 int BUILTIN(ctzl) (unsigned long x) __attribute__((alias(BUILTINN(ctz))));
 102 #else
 103 int BUILTIN(ctzl) (unsigned long x) __attribute__((alias(BUILTINN(ctzll))));
 104 #endif
 105
 106 /* Returns the number of leading redundant sign bits in x, i.e. the number
 107    of bits following the most significant bit that are identical to it.
 108    There are no special cases for 0 or other values. */
 109 int BUILTIN(clrsb) (int x) { if (x < 0) x = ~x; x <<= 1; CLZI(x) }
 110 int BUILTIN(clrsbll) (long long x) { if (x < 0) x = ~x; x <<= 1; CLZL(x) }
 111 #if __SIZEOF_LONG__ == 4
 112 int BUILTIN(clrsbl) (long x) __attribute__((alias(BUILTINN(clrsb))));
 113 #else
 114 int BUILTIN(clrsbl) (long x) __attribute__((alias(BUILTINN(clrsbll))));
 115 #endif
 116
 117 /* Returns the number of 1-bits in x.*/
 118 int BUILTIN(popcount) (unsigned int x) { POPCOUNTI(x, 0x3f) }
 119 int BUILTIN(popcountll) (unsigned long long x) { POPCOUNTL(x, 0x7f) }
 120 #if __SIZEOF_LONG__ == 4
 121 int BUILTIN(popcountl) (unsigned long x) __attribute__((alias(BUILTINN(popcount))));
 122 #else
 123 int BUILTIN(popcountl ) (unsigned long x) __attribute__((alias(BUILTINN(popcountll))));
 124 #endif
 125
 126 /* Returns the parity of x, i.e. the number of 1-bits in x modulo 2. */
 127 int BUILTIN(parity) (unsigned int x) { POPCOUNTI(x, 0x01) }
 128 int BUILTIN(parityll) (unsigned long long x) { POPCOUNTL(x, 0x01) }
 129 #if __SIZEOF_LONG__ == 4
 130 int BUILTIN(parityl) (unsigned long x) __attribute__((alias(BUILTINN(parity))));
 131 #else
 132 int BUILTIN(parityl) (unsigned long x) __attribute__((alias(BUILTINN(parityll))));
 133 #endif
 134
 135 #ifndef __TINYC__
 136 #if defined(__GNUC__) && (__GNUC__ >= 6)
 137 /* gcc overrides alias from __builtin_ffs... to ffs.. so use assembly code */
 138 __asm__(".globl  __builtin_ffs");
 139 __asm__(".set __builtin_ffs,__tcc_builtin_ffs");
 140 __asm__(".globl  __builtin_ffsl");
 141 __asm__(".set __builtin_ffsl,__tcc_builtin_ffsl");
 142 __asm__(".globl  __builtin_ffsll");
 143 __asm__(".set __builtin_ffsll,__tcc_builtin_ffsll");
 144 #else
 145 int __builtin_ffs(int x) __attribute__((alias("__tcc_builtin_ffs")));
 146 int __builtin_ffsl(long x) __attribute__((alias("__tcc_builtin_ffsl")));
 147 int __builtin_ffsll(long long x) __attribute__((alias("__tcc_builtin_ffsll")));
 148 #endif
 149 int __builtin_clz(unsigned int x) __attribute__((alias("__tcc_builtin_clz")));
 150 int __builtin_clzl(unsigned long x) __attribute__((alias("__tcc_builtin_clzl")));
 151 int __builtin_clzll(unsigned long long x) __attribute__((alias("__tcc_builtin_clzll")));
 152 int __builtin_ctz(unsigned int x) __attribute__((alias("__tcc_builtin_ctz")));
 153 int __builtin_ctzl(unsigned long x) __attribute__((alias("__tcc_builtin_ctzl")));
 154 int __builtin_ctzll(unsigned long long x) __attribute__((alias("__tcc_builtin_ctzll")));
 155 int __builtin_clrsb(int x) __attribute__((alias("__tcc_builtin_clrsb")));
 156 int __builtin_clrsbl(long x) __attribute__((alias("__tcc_builtin_clrsbl")));
 157 int __builtin_clrsbll(long long x) __attribute__((alias("__tcc_builtin_clrsbll")));
 158 int __builtin_popcount(unsigned int x) __attribute__((alias("__tcc_builtin_popcount")));
 159 int __builtin_popcountl(unsigned long x) __attribute__((alias("__tcc_builtin_popcountl")));
 160 int __builtin_popcountll(unsigned long long x) __attribute__((alias("__tcc_builtin_popcountll")));
 161 int __builtin_parity(unsigned int x) __attribute__((alias("__tcc_builtin_parity")));
 162 int __builtin_parityl(unsigned long x) __attribute__((alias("__tcc_builtin_parityl")));
 163 int __builtin_parityll(unsigned long long x) __attribute__((alias("__tcc_builtin_parityll")));
 164 #endif