bigint.h - tomo

(220 lines)
   1 // Big integer type (`Int` in Tomo)
   2 
   3 #include <gmp.h>
   4 #include <stdbool.h>
   5 #include <stdint.h>
   6 
   7 #include "datatypes.h"
   8 #include "stdlib.h"
   9 #include "types.h"
  10 #include "util.h"
  11 
  12 Text_t Int$as_text(const void *i, bool colorize, const TypeInfo_t *type);
  13 Text_t Int$value_as_text(Int_t i);
  14 PUREFUNC uint64_t Int$hash(const void *x, const TypeInfo_t *type);
  15 PUREFUNC int32_t Int$compare(const void *x, const void *y, const TypeInfo_t *type);
  16 PUREFUNC int32_t Int$compare_value(const Int_t x, const Int_t y);
  17 CONSTFUNC bool Int$is_between(const Int_t x, const Int_t low, const Int_t high);
  18 CONSTFUNC Int_t Int$clamped(Int_t x, Int_t low, Int_t high);
  19 PUREFUNC bool Int$equal(const void *x, const void *y, const TypeInfo_t *type);
  20 PUREFUNC bool Int$equal_value(const Int_t x, const Int_t y);
  21 Text_t Int$hex(Int_t i, Int_t digits, bool uppercase, bool prefix);
  22 Text_t Int$octal(Int_t i, Int_t digits, bool prefix);
  23 PUREFUNC Closure_t Int$to(Int_t first, Int_t last, OptionalInt_t step);
  24 PUREFUNC Closure_t Int$onward(Int_t first, Int_t step);
  25 OptionalInt_t Int$from_str(const char *str);
  26 OptionalInt_t Int$parse(Text_t text, OptionalInt_t base, Text_t *remainder);
  27 Int_t Int$abs(Int_t x);
  28 Int_t Int$power(Int_t base, Int_t exponent);
  29 Int_t Int$gcd(Int_t x, Int_t y);
  30 OptionalInt_t Int$sqrt(Int_t i);
  31 bool Int$get_bit(Int_t x, Int_t bit_index);
  32 
  33 #define BIGGEST_SMALL_INT 0x3fffffff
  34 #define SMALLEST_SMALL_INT -0x40000000
  35 
  36 #define Int$from_mpz(mpz)                                                                                              \
  37     (mpz_cmpabs_ui(mpz, BIGGEST_SMALL_INT) <= 0                                                                        \
  38          ? ((Int_t){.small = (mpz_get_si(mpz) << 2L) | 1L})                                                            \
  39          : ((Int_t){.big = memcpy(new (__mpz_struct), mpz, sizeof(__mpz_struct))}))
  40 
  41 #define mpz_init_set_int(mpz, i)                                                                                       \
  42     do {                                                                                                               \
  43         if likely ((i).small & 1L) mpz_init_set_si(mpz, (i).small >> 2L);                                              \
  44         else mpz_init_set(mpz, (i).big);                                                                               \
  45     } while (0)
  46 
  47 #define I_small(i) ((Int_t){.small = (int64_t)((uint64_t)(i) << 2L) | 1L})
  48 #define I(i) _Generic(i, int8_t: I_small(i), int16_t: I_small(i), default: Int$from_int64(i))
  49 #define I_is_zero(i) ((i).small == 1L)
  50 
  51 Int_t Int$slow_plus(Int_t x, Int_t y);
  52 Int_t Int$slow_minus(Int_t x, Int_t y);
  53 Int_t Int$slow_times(Int_t x, Int_t y);
  54 Int_t Int$slow_divided_by(Int_t x, Int_t y);
  55 Int_t Int$slow_modulo(Int_t x, Int_t y);
  56 Int_t Int$slow_modulo1(Int_t x, Int_t y);
  57 Int_t Int$slow_left_shifted(Int_t x, Int_t y);
  58 Int_t Int$slow_right_shifted(Int_t x, Int_t y);
  59 Int_t Int$slow_bit_and(Int_t x, Int_t y);
  60 Int_t Int$slow_bit_or(Int_t x, Int_t y);
  61 Int_t Int$slow_bit_xor(Int_t x, Int_t y);
  62 Int_t Int$slow_negative(Int_t x);
  63 Int_t Int$slow_negated(Int_t x);
  64 bool Int$is_prime(Int_t x, Int_t reps);
  65 Int_t Int$next_prime(Int_t x);
  66 Int_t Int$choose(Int_t n, Int_t k);
  67 Int_t Int$factorial(Int_t n);
  68 
  69 extern const TypeInfo_t Int$info;
  70 
  71 // Fast-path inline versions for the common case where integer arithmetic is
  72 // between two small ints.
  73 
  74 MACROLIKE Int_t Int$plus(Int_t x, Int_t y) {
  75     const int64_t z = (int64_t)((uint64_t)x.small + (uint64_t)y.small);
  76     if likely ((z | 2L) == (int32_t)z) return (Int_t){.small = (z - 1L)};
  77     return Int$slow_plus(x, y);
  78 }
  79 
  80 MACROLIKE Int_t Int$minus(Int_t x, Int_t y) {
  81     const int64_t z = (int64_t)(((uint64_t)x.small ^ 3L) - (uint64_t)y.small);
  82     if likely ((z & ~2L) == (int32_t)z) return (Int_t){.small = z};
  83     return Int$slow_minus(x, y);
  84 }
  85 
  86 MACROLIKE Int_t Int$times(Int_t x, Int_t y) {
  87     if likely ((x.small & y.small) & 1L) {
  88         const int64_t z = (x.small >> 1L) * (y.small >> 1L);
  89         if likely (z == (int32_t)z) return (Int_t){.small = z + 1L};
  90     }
  91     return Int$slow_times(x, y);
  92 }
  93 
  94 MACROLIKE Int_t Int$divided_by(Int_t x, Int_t y) {
  95     if likely (x.small & y.small & 1L) {
  96         // Euclidean division, see:
  97         // https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/divmodnote-letter.pdf
  98         const int64_t D = (x.small >> 2L);
  99         const int64_t d = (y.small >> 2L);
 100         int64_t q = D / d, r = D % d;
 101         q -= (r < 0L) * (2L * (d > 0L) - 1L);
 102         if likely (q == (int32_t)q) return (Int_t){.small = (q << 2L) | 1L};
 103     }
 104     return Int$slow_divided_by(x, y);
 105 }
 106 
 107 MACROLIKE Int_t Int$modulo(Int_t x, Int_t y) {
 108     if likely (x.small & y.small & 1L) {
 109         // Euclidean modulus, see:
 110         // https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/divmodnote-letter.pdf
 111         const int64_t D = (x.small >> 2L);
 112         const int64_t d = (y.small >> 2L);
 113         int64_t r = D % d;
 114         r -= (r < 0L) * (2L * (d < 0L) - 1L) * d;
 115         return (Int_t){.small = (r << 2L) | 1L};
 116     }
 117     return Int$slow_modulo(x, y);
 118 }
 119 
 120 MACROLIKE Int_t Int$modulo1(Int_t x, Int_t y) {
 121     if likely (x.small & y.small & 1L) {
 122         // Euclidean modulus, see:
 123         // https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/divmodnote-letter.pdf
 124         const int64_t D = (x.small >> 2L) - 1L;
 125         const int64_t d = (y.small >> 2L);
 126         int64_t r = D % d;
 127         r -= (r < 0L) * (2L * (d < 0L) - 1L) * d;
 128         return (Int_t){.small = ((r + 1L) << 2L) | 1L};
 129     }
 130     return Int$slow_modulo1(x, y);
 131 }
 132 
 133 MACROLIKE Int_t Int$left_shifted(Int_t x, Int_t y) {
 134     if likely (x.small & y.small & 1L) {
 135         const int64_t z = ((x.small >> 2L) << (y.small >> 2L)) << 2L;
 136         if likely (z == (int32_t)z) return (Int_t){.small = z + 1L};
 137     }
 138     return Int$slow_left_shifted(x, y);
 139 }
 140 
 141 MACROLIKE Int_t Int$right_shifted(Int_t x, Int_t y) {
 142     if likely (x.small & y.small & 1L) {
 143         const int64_t z = ((x.small >> 2L) >> (y.small >> 2L)) << 2L;
 144         if likely (z == (int32_t)z) return (Int_t){.small = z + 1L};
 145     }
 146     return Int$slow_right_shifted(x, y);
 147 }
 148 
 149 MACROLIKE Int_t Int$bit_and(Int_t x, Int_t y) {
 150     const int64_t z = x.small & y.small;
 151     if likely (z & 1L) return (Int_t){.small = z};
 152     return Int$slow_bit_and(x, y);
 153 }
 154 
 155 MACROLIKE Int_t Int$bit_or(Int_t x, Int_t y) {
 156     if likely (x.small & y.small & 1L) return (Int_t){.small = (x.small | y.small)};
 157     return Int$slow_bit_or(x, y);
 158 }
 159 
 160 MACROLIKE Int_t Int$bit_xor(Int_t x, Int_t y) {
 161     if likely (x.small & y.small & 1L) return (Int_t){.small = (x.small ^ y.small) | 1L};
 162     return Int$slow_bit_xor(x, y);
 163 }
 164 
 165 MACROLIKE Int_t Int$negated(Int_t x) {
 166     if likely (x.small & 1L) return (Int_t){.small = (~x.small) ^ 3L};
 167     return Int$slow_negated(x);
 168 }
 169 
 170 MACROLIKE Int_t Int$negative(Int_t x) {
 171     if likely (x.small & 1L) return (Int_t){.small = ((-((x.small) >> 2L)) << 2L) | 1L};
 172     return Int$slow_negative(x);
 173 }
 174 
 175 MACROLIKE PUREFUNC bool Int$is_negative(Int_t x) {
 176     if likely (x.small & 1L) return x.small < 0L;
 177     return Int$compare_value(x, I_small(0)) < 0L;
 178 }
 179 
 180 // Constructors/conversion functions:
 181 
 182 // Int constructors:
 183 #ifdef __GNUC__
 184 #pragma GCC diagnostic push
 185 #pragma GCC diagnostic ignored "-Wfloat-equal"
 186 #endif
 187 MACROLIKE PUREFUNC Int_t Int$from_num64(double n, bool truncate) {
 188     mpz_t result;
 189     mpz_init_set_d(result, n);
 190     if (!truncate && unlikely(mpz_get_d(result) != n)) fail("Could not convert to an integer without truncation: ", n);
 191     return Int$from_mpz(result);
 192 }
 193 MACROLIKE PUREFUNC Int_t Int$from_num32(float n, bool truncate) {
 194     return Int$from_num64((double)n, truncate);
 195 }
 196 MACROLIKE Int_t Int$from_int64(int64_t i) {
 197     if likely (i >= SMALLEST_SMALL_INT && i <= BIGGEST_SMALL_INT) return (Int_t){.small = (i << 2L) | 1L};
 198     mpz_t result;
 199     mpz_init_set_si(result, i);
 200     return Int$from_mpz(result);
 201 }
 202 MACROLIKE CONSTFUNC Int_t Int$from_int32(Int32_t i) {
 203     return Int$from_int64((Int32_t)i);
 204 }
 205 MACROLIKE CONSTFUNC Int_t Int$from_int16(Int16_t i) {
 206     return I_small(i);
 207 }
 208 MACROLIKE CONSTFUNC Int_t Int$from_int8(Int8_t i) {
 209     return I_small(i);
 210 }
 211 MACROLIKE CONSTFUNC Int_t Int$from_byte(Byte_t b) {
 212     return I_small(b);
 213 }
 214 MACROLIKE CONSTFUNC Int_t Int$from_bool(Bool_t b) {
 215     return I_small(b);
 216 }
 217 
 218 #ifdef __GNUC__
 219 #pragma GCC diagnostic pop
 220 #endif