Partially working first draft of bigints

12 files changed, 485 insertions, 61 deletions

diff --git a/builtins/array.c b/builtins/array.c
index c5d52380..96a218f5 100644
--- a/builtins/array.c
+++ b/builtins/array.c
@@ -48,8 +48,9 @@ public void Array$compact(array_t *arr, int64_t padded_item_size)
     };
 }
 
-public void Array$insert(array_t *arr, const void *item, int64_t index, int64_t padded_item_size)
+public void Array$insert(array_t *arr, const void *item, Int_t int_index, int64_t padded_item_size)
 {
+    int64_t index = Int$as_i64(int_index);
     if (index <= 0) index = arr->length + index + 1;
 
     if (index < 1) index = 1;
@@ -79,8 +80,9 @@ public void Array$insert(array_t *arr, const void *item, int64_t index, int64_t
     memcpy((void*)arr->data + (index-1)*padded_item_size, item, padded_item_size);
 }
 
-public void Array$insert_all(array_t *arr, array_t to_insert, int64_t index, int64_t padded_item_size)
+public void Array$insert_all(array_t *arr, array_t to_insert, Int_t int_index, int64_t padded_item_size)
 {
+    int64_t index = Int$as_i64(int_index);
     if (to_insert.length == 0)
         return;
 
@@ -150,10 +152,12 @@ public void Array$insert_all(array_t *arr, array_t to_insert, int64_t index, int
     }
 }
 
-public void Array$remove(array_t *arr, int64_t index, int64_t count, int64_t padded_item_size)
+public void Array$remove(array_t *arr, Int_t int_index, Int_t int_count, int64_t padded_item_size)
 {
+    int64_t index = Int$as_i64(int_index);
     if (index < 1) index = arr->length + index + 1;
 
+    int64_t count = Int$as_i64(int_count);
     if (index < 1 || index > (int64_t)arr->length || count < 1) return;
 
     if (count > arr->length - index + 1)
@@ -205,7 +209,7 @@ public void Array$shuffle(array_t *arr, int64_t padded_item_size)
 
     char tmp[padded_item_size];
     for (int64_t i = arr->length-1; i > 1; i--) {
-        int64_t j = Int$random(0, i);
+        int64_t j = arc4random_uniform(i+1);
         memcpy(tmp, arr->data + i*padded_item_size, padded_item_size);
         memcpy((void*)arr->data + i*padded_item_size, arr->data + j*padded_item_size, padded_item_size);
         memcpy((void*)arr->data + j*padded_item_size, tmp, padded_item_size);
@@ -216,7 +220,7 @@ public void *Array$random(array_t arr)
 {
     if (arr.length == 0)
         return NULL; // fail("Cannot get a random item from an empty array!");
-    int64_t index = Int$random(0, arr.length-1);
+    int64_t index = arc4random_uniform(arr.length);
     return arr.data + arr.stride*index;
 }
 
@@ -234,8 +238,9 @@ public table_t Array$counts(array_t arr, const TypeInfo *type)
     return counts;
 }
 
-public array_t Array$sample(array_t arr, int64_t n, array_t weights, int64_t padded_item_size)
+public array_t Array$sample(array_t arr, Int_t int_n, array_t weights, int64_t padded_item_size)
 {
+    int64_t n = Int$as_i64(int_n);
     if (arr.length == 0 || n <= 0)
         return (array_t){};
 
@@ -262,7 +267,7 @@ public array_t Array$sample(array_t arr, int64_t n, array_t weights, int64_t pad
 
     if (total == 0.0) {
         for (int64_t i = 0; i < n; i++) {
-            int64_t index = Int$random(0, arr.length-1);
+            int64_t index = arc4random_uniform(arr.length);
             memcpy(selected.data + i*padded_item_size, arr.data + arr.stride*index, padded_item_size);
         }
     } else {
@@ -312,8 +317,9 @@ public array_t Array$sample(array_t arr, int64_t n, array_t weights, int64_t pad
     return selected;
 }
 
-public array_t Array$from(array_t array, int64_t first)
+public array_t Array$from(array_t array, Int_t int_first)
 {
+    int64_t first = Int$as_i64(int_first);
     if (first < 0)
         first = array.length + first + 1;
 
@@ -329,8 +335,9 @@ public array_t Array$from(array_t array, int64_t first)
     };
 }
 
-public array_t Array$to(array_t array, int64_t last)
+public array_t Array$to(array_t array, Int_t int_last)
 {
+    int64_t last = Int$as_i64(int_last);
     if (last < 0)
         last = array.length + last + 1;
 
@@ -349,8 +356,9 @@ public array_t Array$to(array_t array, int64_t last)
     };
 }
 
-public array_t Array$by(array_t array, int64_t stride, int64_t padded_item_size)
+public array_t Array$by(array_t array, Int_t int_stride, int64_t padded_item_size)
 {
+    int64_t stride = Int$as_i64(int_stride);
     // In the unlikely event that the stride value would be too large to fit in
     // a 15-bit integer, fall back to creating a copy of the array:
     if (__builtin_expect(array.stride*stride < ARRAY_MIN_STRIDE || array.stride*stride > ARRAY_MAX_STRIDE, 0)) {
@@ -389,7 +397,7 @@ public array_t Array$reversed(array_t array, int64_t padded_item_size)
     // the array. This should only happen if array.stride is MIN_STRIDE to
     // begin with (very unlikely).
     if (__builtin_expect(-array.stride < ARRAY_MIN_STRIDE || -array.stride > ARRAY_MAX_STRIDE, 0))
-        return Array$by(array, -1, padded_item_size);
+        return Array$by(array, I(-1), padded_item_size);
 
     array_t reversed = array;
     reversed.stride = -array.stride;
@@ -584,7 +592,7 @@ static void siftup(array_t *heap, int64_t pos, closure_t comparison, int64_t pad
 
 public void Array$heap_push(array_t *heap, const void *item, closure_t comparison, int64_t padded_item_size)
 {
-    Array$insert(heap, item, 0, padded_item_size);
+    Array$insert(heap, item, I(0), padded_item_size);
 
     if (heap->length > 1) {
         if (heap->data_refcount != 0)
diff --git a/builtins/array.h b/builtins/array.h
index 9a5307a2..6da84afd 100644
--- a/builtins/array.h
+++ b/builtins/array.h
@@ -7,27 +7,28 @@
 
 #include "datatypes.h"
 #include "functions.h"
+#include "integers.h"
 #include "types.h"
 #include "util.h"
 
 // Convert negative indices to back-indexed without branching: index0 = index + (index < 0)*(len+1)) - 1
 #define Array_get(item_type, arr_expr, index_expr, filename, start, end) *({ \
-    const array_t arr = arr_expr; int64_t index = (int64_t)(index_expr); \
+    const array_t arr = arr_expr; int64_t index = Int$as_i64(index_expr); \
     int64_t off = index + (index < 0) * (arr.length + 1) - 1; \
     if (__builtin_expect(off < 0 || off >= arr.length, 0)) \
-        fail_source(filename, start, end, "Invalid array index: %r (array has length %ld)\n", Int$as_text(&index, no, NULL), arr.length); \
+        fail_source(filename, start, end, "Invalid array index: %r (array has length %ld)\n", Int64$as_text(&index, no, NULL), arr.length); \
     (item_type*)(arr.data + arr.stride * off);})
 #define Array_lvalue(item_type, arr_expr, index_expr, padded_item_size, filename, start, end) *({ \
-    array_t *arr = arr_expr; int64_t index = (int64_t)(index_expr); \
+    array_t *arr = arr_expr; int64_t index = Int$as_i64(index_expr); \
     int64_t off = index + (index < 0) * (arr->length + 1) - 1; \
     if (__builtin_expect(off < 0 || off >= arr->length, 0)) \
-        fail_source(filename, start, end, "Invalid array index: %r (array has length %ld)\n", Int$as_text(&index, no, NULL), arr->length); \
+        fail_source(filename, start, end, "Invalid array index: %r (array has length %ld)\n", Int64$as_text(&index, no, NULL), arr->length); \
     if (arr->data_refcount > 0) \
         Array$compact(arr, padded_item_size); \
     (item_type*)(arr->data + arr->stride * off); })
 #define Array_set(item_type, arr, index, value, padded_item_size, filename, start, end) \
     Array_lvalue(item_type, arr_expr, index, padded_item_size, filename, start, end) = value
-#define Array_get_unchecked(type, x, i) *({ const array_t arr = x; int64_t index = (int64_t)(i); \
+#define Array_get_unchecked(type, x, i) *({ const array_t arr = x; int64_t index = I(i); \
                                           int64_t off = index + (index < 0) * (arr.length + 1) - 1; \
                                           (type*)(arr.data + arr.stride * off);})
 #define is_atomic(x) _Generic(x, bool: true, int8_t: true, int16_t: true, int32_t: true, int64_t: true, float: true, double: true, default: false)
@@ -55,22 +56,22 @@
 #define ARRAY_COPY(arr) ({ ARRAY_INCREF(arr); arr; })
 
 #define Array$insert_value(arr, item_expr, index, padded_item_size) ({ __typeof(item_expr) item = item_expr; Array$insert(arr, &item, index, padded_item_size); })
-void Array$insert(array_t *arr, const void *item, int64_t index, int64_t padded_item_size);
-void Array$insert_all(array_t *arr, array_t to_insert, int64_t index, int64_t padded_item_size);
-void Array$remove(array_t *arr, int64_t index, int64_t count, int64_t padded_item_size);
+void Array$insert(array_t *arr, const void *item, Int_t index, int64_t padded_item_size);
+void Array$insert_all(array_t *arr, array_t to_insert, Int_t index, int64_t padded_item_size);
+void Array$remove(array_t *arr, Int_t index, Int_t count, int64_t padded_item_size);
 void Array$sort(array_t *arr, closure_t comparison, int64_t padded_item_size);
 array_t Array$sorted(array_t arr, closure_t comparison, int64_t padded_item_size);
 void Array$shuffle(array_t *arr, int64_t padded_item_size);
 void *Array$random(array_t arr);
 #define Array$random_value(arr, t) ({ array_t _arr = arr; if (_arr.length == 0) fail("Cannot get a random value from an empty array!"); *(t*)Array$random(_arr); })
-array_t Array$sample(array_t arr, int64_t n, array_t weights, int64_t padded_item_size);
+array_t Array$sample(array_t arr, Int_t n, array_t weights, int64_t padded_item_size);
 table_t Array$counts(array_t arr, const TypeInfo *type);
 void Array$clear(array_t *array);
 void Array$compact(array_t *arr, int64_t padded_item_size);
 bool Array$contains(array_t array, void *item, const TypeInfo *type);
-array_t Array$from(array_t array, int64_t first);
-array_t Array$to(array_t array, int64_t last);
-array_t Array$by(array_t array, int64_t stride, int64_t padded_item_size);
+array_t Array$from(array_t array, Int_t first);
+array_t Array$to(array_t array, Int_t last);
+array_t Array$by(array_t array, Int_t stride, int64_t padded_item_size);
 array_t Array$reversed(array_t array, int64_t padded_item_size);
 array_t Array$concat(array_t x, array_t y, int64_t padded_item_size);
 uint32_t Array$hash(const array_t *arr, const TypeInfo *type);
diff --git a/builtins/channel.c b/builtins/channel.c
index cfb398b0..e4683aa3 100644
--- a/builtins/channel.c
+++ b/builtins/channel.c
@@ -34,7 +34,7 @@ public void Channel$push(channel_t *channel, const void *item, int64_t padded_it
     (void)pthread_mutex_lock(&channel->mutex);
     while (channel->items.length >= channel->max_size)
         pthread_cond_wait(&channel->cond, &channel->mutex);
-    Array$insert(&channel->items, item, 0, padded_item_size);
+    Array$insert(&channel->items, item, I(0), padded_item_size);
     (void)pthread_mutex_unlock(&channel->mutex);
     (void)pthread_cond_signal(&channel->cond);
 }
@@ -47,10 +47,10 @@ public void Channel$push_all(channel_t *channel, array_t to_push, int64_t padded
         for (int64_t i = 0; i < to_push.length; i++) {
             while (channel->items.length >= channel->max_size)
                 pthread_cond_wait(&channel->cond, &channel->mutex);
-            Array$insert(&channel->items, to_push.data + i*to_push.stride, 0, padded_item_size);
+            Array$insert(&channel->items, to_push.data + i*to_push.stride, I(0), padded_item_size);
         }
     } else {
-        Array$insert_all(&channel->items, to_push, 0, padded_item_size);
+        Array$insert_all(&channel->items, to_push, I(0), padded_item_size);
     }
     (void)pthread_mutex_unlock(&channel->mutex);
     (void)pthread_cond_signal(&channel->cond);
@@ -62,7 +62,7 @@ public void Channel$pop(channel_t *channel, void *out, int64_t item_size, int64_
     while (channel->items.length == 0)
         pthread_cond_wait(&channel->cond, &channel->mutex);
     memcpy(out, channel->items.data, item_size);
-    Array$remove(&channel->items, 1, 1, padded_item_size);
+    Array$remove(&channel->items, I(1), I(1), padded_item_size);
     (void)pthread_mutex_unlock(&channel->mutex);
     (void)pthread_cond_signal(&channel->cond);
 }
diff --git a/builtins/datatypes.h b/builtins/datatypes.h
index a9f28dc1..699c40e0 100644
--- a/builtins/datatypes.h
+++ b/builtins/datatypes.h
@@ -2,6 +2,7 @@
 
 // Common datastructures (arrays, tables, closures)
 
+#include <gmp.h>
 #include <stdint.h>
 #include <stdbool.h>
 #include <pthread.h>
@@ -17,6 +18,11 @@
 #define ARRAY_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(ARRAY_REFCOUNT_BITS)
 #define ARRAY_MAX_FREE_ENTRIES MAX_FOR_N_BITS(ARRAY_FREE_BITS)
 
+typedef union {
+    int64_t small;
+    mpz_t *big;
+} Int_t;
+
 typedef struct {
     void *data;
     // All of the following fields add up to 64 bits, which means that array
@@ -55,7 +61,7 @@ typedef struct {
 } closure_t;
 
 typedef struct Range_s {
-    int64_t first, last, step;
+    Int_t first, last, step;
 } Range_t;
 
 typedef struct {
diff --git a/builtins/functions.c b/builtins/functions.c
index 4e7d25ac..cb75442d 100644
--- a/builtins/functions.c
+++ b/builtins/functions.c
@@ -17,6 +17,7 @@
 #include "files.h"
 #include "functions.h"
 #include "halfsiphash.h"
+#include "integers.h"
 #include "pointer.h"
 #include "string.h"
 #include "table.h"
@@ -35,6 +36,7 @@ public void tomo_init(void)
    getrandom(&seed, sizeof(seed), 0);
    srand(seed);
    srand48(seed);
+   Int$init_random(seed);
 }
 
 static void print_stack_trace(FILE *out)
diff --git a/builtins/integers.c b/builtins/integers.c
index db1a73e2..8bc66172 100644
--- a/builtins/integers.c
+++ b/builtins/integers.c
@@ -1,6 +1,7 @@
 // Integer type infos and methods
 #include <gc.h>
 #include <gc/cord.h>
+#include <gmp.h>
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdlib.h>
@@ -8,11 +9,300 @@
 #include "array.h"
 #include "datatypes.h"
 #include "integers.h"
-#include "string.h"
+#include "text.h"
 #include "types.h"
+#include "SipHash/halfsiphash.h"
+
+static gmp_randstate_t Int_rng = {};
+
+public void Int$init_random(long seed)
+{
+    gmp_randinit_default(Int_rng);
+    gmp_randseed_ui(Int_rng, (unsigned long)seed);
+}
+
+public Int_t Int$from_i64(int64_t i)
+{
+    if (i == (int32_t)i) return (Int_t){.small=(i*4)+1};
+    mpz_t result;
+    mpz_init_set_si(result, i);
+    return Int$from_mpz(result);
+}
+
+public CORD Int$as_text(const Int_t *i, bool colorize, const TypeInfo *type) {
+    (void)type;
+    if (!i) return "Int";
+
+    if (__builtin_expect(i->small & 1, 1)) {
+        return CORD_asprintf(colorize ? "\x1b[35m%ld\x1b[33;2m\x1b[m" : "%ld", (i->small)>>2);
+    } else {
+        char *str = mpz_get_str(NULL, 10, *i->big);
+        return CORD_asprintf(colorize ? "\x1b[35m%s\x1b[33;2m\x1b[m" : "%s", str);
+    }
+}
+
+public int32_t Int$compare(const Int_t *x, const Int_t *y, const TypeInfo *type) {
+    (void)type;
+    if (__builtin_expect(((x->small & y->small) & 1) == 0, 0))
+        return mpz_cmp(*x->big, *y->big);
+    return (x->small > y->small) - (x->small < y->small);
+}
+
+public int32_t Int$compare_value(const Int_t x, const Int_t y) {
+    if (__builtin_expect(((x.small & y.small) & 1) == 0, 0))
+        return mpz_cmp(*x.big, *y.big);
+    return (x.small > y.small) - (x.small < y.small);
+}
+
+public bool Int$equal(const Int_t *x, const Int_t *y, const TypeInfo *type) {
+    (void)type;
+    return x->small == y->small || (__builtin_expect(((x->small & y->small) & 1) == 0, 0) && mpz_cmp(*x->big, *y->big) == 0);
+}
+
+public bool Int$equal_value(const Int_t x, const Int_t y) {
+    return x.small == y.small || (__builtin_expect(((x.small & y.small) & 1) == 0, 0) && mpz_cmp(*x.big, *y.big) == 0);
+}
+
+public bool Int$hash(const Int_t *x, const TypeInfo *type) {
+    (void)type;
+    uint32_t hash;
+    if (__builtin_expect(x->small & 1, 1)) {
+        halfsiphash(&x->small, sizeof(x->small), TOMO_HASH_KEY, (uint8_t*)&hash, sizeof(hash));
+    } else {
+        char *str = mpz_get_str(NULL, 16, *x->big);
+        halfsiphash(str, strlen(str), TOMO_HASH_KEY, (uint8_t*)&hash, sizeof(hash));
+    }
+    return hash;
+}
+
+public CORD Int$hex(Int_t i, int64_t digits, bool uppercase, bool prefix) {
+    const char *hex_fmt = uppercase ? (prefix ? "0x%0.*lX" : "%0.*lX") : (prefix ? "0x%0.*lx" : "%0.*lx");
+    if (__builtin_expect(i.small & 1, 1)) {
+        return CORD_asprintf(hex_fmt, (i.small)>>2);
+    } else {
+        CORD str = mpz_get_str(NULL, 16, *i.big);
+        if (uppercase) str = Text$upper(str);
+        if (digits > (int64_t)CORD_len(str))
+            str = CORD_cat(str, CORD_chars('0', digits - CORD_len(str)));
+        if (prefix) str = CORD_cat("0x", str);
+        return str;
+    }
+}
+
+public CORD Int$octal(Int_t i, int64_t digits, bool prefix) {
+    const char *octal_fmt = prefix ? "0o%0.*lo" : "%0.*lo";
+    if (__builtin_expect(i.small & 1, 1)) {
+        return CORD_asprintf(octal_fmt, (int)digits, (uint64_t)(i.small >> 2));
+    } else {
+        CORD str = mpz_get_str(NULL, 8, *i.big);
+        if (digits > (int64_t)CORD_len(str))
+            str = CORD_cat(str, CORD_chars('0', digits - CORD_len(str)));
+        if (prefix) str = CORD_cat("0o", str);
+        return str;
+    }
+}
+
+public Int_t Int$slow_plus(Int_t x, Int_t y) {
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    if (y.small & 1) {
+        mpz_t y_mpz;
+        mpz_init_set_int(y_mpz, y);
+        mpz_add(result, result, y_mpz);
+    } else {
+        mpz_add(result, result, *y.big);
+    }
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_minus(Int_t x, Int_t y) {
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    if (y.small & 1) {
+        mpz_t y_mpz;
+        mpz_init_set_int(y_mpz, y);
+        mpz_sub(result, result, y_mpz);
+    } else {
+        mpz_sub(result, result, *y.big);
+    }
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_times(Int_t x, Int_t y) {
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    if (y.small & 1) {
+        mpz_t y_mpz;
+        mpz_init_set_int(y_mpz, y);
+        mpz_mul(result, result, y_mpz);
+    } else {
+        mpz_mul(result, result, *y.big);
+    }
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_divided_by(Int_t x, Int_t y) {
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    if (y.small & 1) {
+        mpz_t y_mpz;
+        mpz_init_set_int(y_mpz, y);
+        mpz_cdiv_q(result, result, y_mpz);
+    } else {
+        mpz_cdiv_q(result, result, *y.big);
+    }
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_modulo(Int_t x, Int_t modulus)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_t divisor;
+    mpz_init_set_int(divisor, modulus);
+    mpz_mod(result, result, divisor);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_modulo1(Int_t x, Int_t modulus)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_sub_ui(result, result, 1);
+    mpz_t divisor;
+    mpz_init_set_int(divisor, modulus);
+    mpz_mod(result, result, divisor);
+    mpz_add_ui(result, result, 1);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_left_shifted(Int_t x, Int_t y)
+{
+    mp_bitcnt_t bits = (mp_bitcnt_t)Int$as_i64(y);
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_mul_2exp(result, result, bits);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_right_shifted(Int_t x, Int_t y)
+{
+    mp_bitcnt_t bits = (mp_bitcnt_t)Int$as_i64(y);
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_tdiv_q_2exp(result, result, bits);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_bit_and(Int_t x, Int_t y)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_t y_mpz;
+    mpz_init_set_int(y_mpz, y);
+    mpz_and(result, result, y_mpz);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_bit_or(Int_t x, Int_t y)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_t y_mpz;
+    mpz_init_set_int(y_mpz, y);
+    mpz_ior(result, result, y_mpz);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_bit_xor(Int_t x, Int_t y)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_t y_mpz;
+    mpz_init_set_int(y_mpz, y);
+    mpz_xor(result, result, y_mpz);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_negated(Int_t x)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_neg(result, result);
+    mpz_sub_ui(result, result, 1);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_negative(Int_t x)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_neg(result, result);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$slow_abs(Int_t x)
+{
+    mpz_t result;
+    mpz_init_set_int(result, x);
+    mpz_abs(result, result);
+    return Int$from_mpz(result);
+}
+
+public Int_t Int$random(Int_t min, Int_t max) {
+    int32_t cmp = Int$compare(&min, &max, &$Int);
+    if (cmp > 0)
+        fail("Random minimum value (%r) is larger than the maximum value (%r)",
+             Int$as_text(&min, false, &$Int), Int$as_text(&max, false, &$Int));
+    if (cmp == 0) return min;
+
+    mpz_t range_size;
+    mpz_init_set_int(range_size, max);
+    if (min.small & 1) {
+        mpz_t min_mpz;
+        mpz_init_set_si(min_mpz, min.small >> 2);
+        mpz_sub(range_size, range_size, min_mpz);
+    } else {
+        mpz_sub(range_size, range_size, *min.big);
+    }
+
+    mpz_t r;
+    mpz_init(r);
+    mpz_urandomm(r, Int_rng, range_size);
+    return Int$plus(min, Int$from_mpz(r));
+}
+
+public Range_t Int$to(Int_t from, Int_t to) {
+    return (Range_t){from, to, Int$compare(&to, &from, &$Int) >= 0 ? (Int_t){.small=(1<<2)|1} : (Int_t){.small=(-1/4)|1}};
+}
+
+public Int_t Int$from_text(CORD text) {
+    const char *str = CORD_to_const_char_star(text);
+    mpz_t i;
+    if (strncmp(str, "0x", 2) == 0) {
+        mpz_init_set_str(i, str + 2, 16);
+    } else if (strncmp(str, "0o", 2) == 0) {
+        mpz_init_set_str(i, str + 2, 8);
+    } else if (strncmp(str, "0b", 2) == 0) {
+        mpz_init_set_str(i, str + 2, 2);
+    } else {
+        mpz_init_set_str(i, str, 10);
+    }
+    return Int$from_mpz(i);
+}
+
+public const TypeInfo $Int = {
+    .size=sizeof(Int_t),
+    .align=__alignof__(Int_t),
+    .tag=CustomInfo,
+    .CustomInfo={
+        .compare=(void*)Int$compare,
+        .equal=(void*)Int$equal,
+        .hash=(void*)Int$equal,
+        .as_text=(void*)Int$as_text,
+    },
+};
 
-#define xstr(a) str(a)
-#define str(a) #a
 
 #define DEFINE_INT_TYPE(c_type, KindOfInt, fmt, min_val, max_val)\
     public CORD KindOfInt ## $as_text(const c_type *i, bool colorize, const TypeInfo *type) { \
@@ -69,7 +359,7 @@
         return (c_type)((uint64_t)min + (r % range)); \
     } \
     public Range_t KindOfInt ## $to(c_type from, c_type to) { \
-        return (Range_t){from, to, to >= from ? 1 : -1}; \
+        return (Range_t){Int$from_i64(from), Int$from_i64(to), to >= from ? (Int_t){.small=(1<<2)&1} : (Int_t){.small=(1<<2)&1}}; \
     } \
     public c_type KindOfInt ## $from_text(CORD text, CORD *the_rest) { \
         const char *str = CORD_to_const_char_star(text); \
@@ -98,7 +388,7 @@
         .CustomInfo={.compare=(void*)KindOfInt##$compare, .as_text=(void*)KindOfInt##$as_text}, \
     };
 
-DEFINE_INT_TYPE(int64_t,  Int,    "ld",     INT64_MIN, INT64_MAX);
+DEFINE_INT_TYPE(int64_t,  Int64,  "ld",     INT64_MIN, INT64_MAX);
 DEFINE_INT_TYPE(int32_t,  Int32,  "d_i32",  INT32_MIN, INT32_MAX);
 DEFINE_INT_TYPE(int16_t,  Int16,  "d_i16",  INT16_MIN, INT16_MAX);
 DEFINE_INT_TYPE(int8_t,   Int8,   "d_i8",   INT8_MIN,  INT8_MAX);
diff --git a/builtins/integers.h b/builtins/integers.h
index 4ab30490..cf2e7e25 100644
--- a/builtins/integers.h
+++ b/builtins/integers.h
@@ -6,11 +6,12 @@
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdlib.h>
+#include <gmp.h>
 
 #include "datatypes.h"
 #include "types.h"
 
-#define Int_t int64_t
+#define Int64_t int64_t
 #define Int32_t int32_t
 #define Int16_t int16_t
 #define Int8_t int8_t
@@ -33,15 +34,121 @@
     extern const c_type type_name ## $min, type_name##$max; \
     extern const TypeInfo $ ## type_name;
 
-DEFINE_INT_TYPE(int64_t, Int);
+DEFINE_INT_TYPE(int64_t, Int64);
 DEFINE_INT_TYPE(int32_t, Int32);
 DEFINE_INT_TYPE(int16_t, Int16);
 DEFINE_INT_TYPE(int8_t,  Int8);
 #undef DEFINE_INT_TYPE
 
-#define Int$abs(...) I64(labs(__VA_ARGS__))
+#define Int64$abs(...) I64(labs(__VA_ARGS__))
 #define Int32$abs(...) I32(abs(__VA_ARGS__))
 #define Int16$abs(...) I16(abs(__VA_ARGS__))
 #define Int8$abs(...) I8(abs(__VA_ARGS__))
 
+CORD Int$as_text(const Int_t *i, bool colorize, const TypeInfo *type);
+int32_t Int$compare(const Int_t *x, const Int_t *y, const TypeInfo *type);
+int32_t Int$compare_value(const Int_t x, const Int_t y);
+bool Int$equal(const Int_t *x, const Int_t *y, const TypeInfo *type);
+bool Int$equal_value(const Int_t x, const Int_t y);
+CORD Int$format(Int_t i, int64_t digits);
+CORD Int$hex(Int_t i, int64_t digits, bool uppercase, bool prefix);
+CORD Int$octal(Int_t i, int64_t digits, bool prefix);
+void Int$init_random(long seed);
+Int_t Int$random(Int_t min, Int_t max);
+Range_t Int$to(Int_t from, Int_t to);
+Int_t Int$from_text(CORD text);
+Int_t Int$abs(Int_t x);
+
+#define BIGGEST_SMALL_INT ((1<<30)-1)
+
+#define Int$from_mpz(mpz) (\
+    mpz_cmpabs_ui(mpz, BIGGEST_SMALL_INT) <= 0 ? ({ \
+        (Int_t){.small=(mpz_get_si(mpz)<<2)|1}; \
+    }) : ({ \
+        mpz_t *result_obj = new(mpz_t); \
+        memcpy(result_obj, &mpz, sizeof(mpz_t)); \
+        (Int_t){.big=result_obj}; \
+    }))
+
+#define mpz_init_set_int(mpz, i) do { \
+    if ((i).small & 1) mpz_init_set_si(mpz, (i).small >> 2); \
+    else mpz_init_set(mpz, *(i).big); \
+} while (0)
+
+#define Int$as_i64(i) (((i).small & 1) ? (int64_t)((i).small >> 2) : mpz_get_si(*(i).big))
+Int_t Int$from_i64(int64_t i);
+#define I(i) ((int64_t)(i) == (int32_t)(i) ? ((Int_t){.small=((uint64_t)(i)<<2)|1}) : Int$from_i64(i))
+
+Int_t Int$slow_plus(Int_t x, Int_t y);
+Int_t Int$slow_minus(Int_t x, Int_t y);
+Int_t Int$slow_times(Int_t x, Int_t y);
+Int_t Int$slow_divided_by(Int_t x, Int_t y);
+Int_t Int$slow_modulo(Int_t x, Int_t y);
+Int_t Int$slow_modulo1(Int_t x, Int_t y);
+Int_t Int$slow_left_shifted(Int_t x, Int_t y);
+Int_t Int$slow_right_shifted(Int_t x, Int_t y);
+Int_t Int$slow_bit_and(Int_t x, Int_t y);
+Int_t Int$slow_bit_or(Int_t x, Int_t y);
+Int_t Int$slow_bit_xor(Int_t x, Int_t y);
+Int_t Int$slow_negative(Int_t x);
+Int_t Int$slow_negated(Int_t x);
+Int_t Int$slow_abs(Int_t x);
+#define Int$plus(_x, _y) ({ \
+                          Int_t x = _x, y = _y; \
+                          const int64_t z = (int64_t)((uint64_t)x.small + (uint64_t)y.small); \
+                          __builtin_expect(((z|2) != (int32_t)z), 0) ? Int$slow_plus(x, y) : (Int_t){.small=(z-1)}; })
+
+#define Int$minus(_x, _y) ({ \
+                          Int_t x = _x, y = _y; \
+                          const int64_t z = (int64_t)(((uint64_t)x.small ^ 3) - (uint64_t)y.small); \
+                          __builtin_expect(((z & ~2) != (int32_t)z), 0) ? Int$slow_minus(x, y) : (Int_t){.small=(z-1)}; })
+
+#define Int$times(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           __builtin_expect(((x.small & y.small) & 1) == 0, 0) ? Int$slow_times(x, y) : ({ \
+                               const int64_t z = (x.small>>1) * (y.small>>1); \
+                               __builtin_expect(z != (int32_t)z, 0) ? Int$slow_times(x, y) : (Int_t){.small=z+1}; }); })
+
+#define Int$divided_by(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           __builtin_expect(((x.small & y.small) & 1) == 0, 0) ? Int$slow_divided_by(x, y) : ({ \
+                               const int64_t z = 4*(x.small>>1) / (y.small>>1); \
+                               __builtin_expect(z != (int32_t)z, 0) ? Int$slow_divided_by(x, y) : (Int_t){.small=z+1}; }); })
+#define Int$left_shifted(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           __builtin_expect(((x.small & y.small) & 1) == 0, 0) ? Int$slow_left_shifted(x, y) : ({ \
+                               const int64_t z = 4*((x.small>>2) << (y.small>>2)); \
+                               __builtin_expect(z != (int32_t)z, 0) ? Int$slow_left_shifted(x, y) : (Int_t){.small=z+1}; }); })
+#define Int$right_shifted(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           __builtin_expect(((x.small & y.small) & 1) == 0, 0) ? Int$slow_right_shifted(x, y) : ({ \
+                               const int64_t z = 4*((x.small>>2) >> (y.small>>2)); \
+                               __builtin_expect(z != (int32_t)z, 0) ? Int$slow_right_shifted(x, y) : (Int_t){.small=z+1}; }); })
+#define Int$bit_and(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           const int64_t z = x.small & y.small; \
+                           __builtin_expect((z & 1) == 1, 1) ? (Int_t){.small=z} : Int$slow_bit_and(x, y); })
+#define Int$bit_or(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           __builtin_expect(((x.small & y.small) & 1) == 1, 1) ? (Int_t){.small=(x.small | y.small)} : Int$slow_bit_or(x, y); })
+#define Int$bit_xor(_x, _y) ({ \
+                           Int_t x = _x, y = _y; \
+                           __builtin_expect(((x.small & y.small) & 1) == 1, 1) ? (Int_t){.small=(x.small ^ y.small) | 1} : Int$slow_bit_xor(x, y); })
+
+#define Int$modulo(x, y) Int$slow_modulo(x, y)
+#define Int$modulo1(x, y) Int$slow_modulo1(x, y)
+
+#define Int$negative(_x) ({ \
+                          Int_t x = _x; \
+                          __builtin_expect((x.small & 1), 1) ? (Int_t){.small=4*-((x.small)/4) + 1} : Int$slow_negative(x); })
+#define Int$negated(_x) ({ \
+                          Int_t x = _x; \
+                          __builtin_expect((x.small & 1), 1) ? (Int_t){.small=(~x.small) ^ 3} : Int$slow_negated(x); })
+#define Int$abs(_x) ({ \
+                     Int_t x = _x; \
+                     __builtin_expect((x.small & 1), 1) ? (Int_t){.small=4*labs((x.small)/4) + 1} : Int$slow_abs(x); })
+
+extern const TypeInfo $Int;
+
+
 // vim: ts=4 sw=0 et cino=L2,l1,(0,W4,m1,\:0
diff --git a/builtins/range.c b/builtins/range.c
index ced2a26f..840397b9 100644
--- a/builtins/range.c
+++ b/builtins/range.c
@@ -2,6 +2,7 @@
 
 #include <ctype.h>
 #include <err.h>
+#include <gmp.h>
 #include <gc.h>
 #include <gc/cord.h>
 #include <math.h>
@@ -11,23 +12,24 @@
 #include <sys/param.h>
 
 #include "types.h"
+#include "integers.h"
 #include "util.h"
 
 
 static int32_t Range$compare(const Range_t *x, const Range_t *y, const TypeInfo *type)
 {
     (void)type;
-    int32_t diff = (x->first > y->first) - (x->first < y->first);
+    int32_t diff = Int$compare(&x->first, &y->first, &$Int);
     if (diff != 0) return diff;
-    diff = (x->last > y->last) - (x->last < y->last);
+    diff = Int$compare(&x->last, &y->last, &$Int);
     if (diff != 0) return diff;
-    return (x->step > y->step) - (x->step < y->step);
+    return Int$compare(&x->step, &y->step, &$Int);
 }
 
 static bool Range$equal(const Range_t *x, const Range_t *y, const TypeInfo *type)
 {
     (void)type;
-    return (x->first == y->first) && (x->last == y->last) && (x->step == y->step);
+    return Int$equal(&x->first, &y->first, &$Int) && Int$equal(&x->last, &y->last, &$Int) && Int$equal(&x->step, &y->step, &$Int);
 }
 
 static CORD Range$as_text(const Range_t *r, bool use_color, const TypeInfo *type)
@@ -35,18 +37,20 @@ static CORD Range$as_text(const Range_t *r, bool use_color, const TypeInfo *type
     (void)type;
     if (!r) return "Range";
 
-    return CORD_asprintf(use_color ? "\x1b[0;1mRange\x1b[m(first=\x1b[35m%ld\x1b[m, last=\x1b[35m%ld\x1b[m, step=\x1b[35m%ld\x1b[m)"
-                         : "Range(first=%ld, last=%ld, step=%ld)", r->first, r->last, r->step);
+    return CORD_asprintf(use_color ? "\x1b[0;1mRange\x1b[m(first=%r, last=%r, step=%r)"
+                         : "Range(first=%r, last=%r, step=%r)",
+                         Int$as_text(&r->first, use_color, &$Int), Int$as_text(&r->last, use_color, &$Int),
+                         Int$as_text(&r->step, use_color, &$Int));
 }
 
 public Range_t Range$reversed(Range_t r)
 {
-    return (Range_t){r.last, r.first, -r.step};
+    return (Range_t){r.last, r.first, Int$negative(r.step)};
 }
 
-public Range_t Range$by(Range_t r, int64_t step)
+public Range_t Range$by(Range_t r, Int_t step)
 {
-    return (Range_t){r.first, r.last, step*r.step};
+    return (Range_t){r.first, r.last, Int$times(step, r.step)};
 }
 
 public const TypeInfo Range = {sizeof(Range_t), __alignof(Range_t), {.tag=CustomInfo, .CustomInfo={
diff --git a/builtins/table.c b/builtins/table.c
index e2044a2d..f99ffc86 100644
--- a/builtins/table.c
+++ b/builtins/table.c
@@ -267,7 +267,7 @@ public void *Table$reserve(table_t *t, const void *key, const void *value, const
         memcpy(buf + value_offset(type), value, value_size);
     else
         memset(buf + value_offset(type), 0, value_size);
-    Array$insert(&t->entries, buf, 0, entry_size(type));
+    Array$insert(&t->entries, buf, I(0), entry_size(type));
 
     int64_t entry_index = t->entries.length-1;
     void *entry = GET_ENTRY(*t, entry_index);
@@ -350,7 +350,7 @@ public void Table$remove(table_t *t, const void *key, const TypeInfo *type)
     // Last entry is being removed, so clear it out to be safe:
     memset(GET_ENTRY(*t, last_entry), 0, entry_size(type));
 
-    Array$remove(&t->entries, t->entries.length, 1, entry_size(type));
+    Array$remove(&t->entries, I(t->entries.length), I(1), entry_size(type));
 
     int64_t bucket_to_clear;
     if (prev) { // Middle (or end) of a chain
diff --git a/builtins/text.c b/builtins/text.c
index 2c72654a..754eef91 100644
--- a/builtins/text.c
+++ b/builtins/text.c
@@ -5,6 +5,7 @@
 #include <err.h>
 #include <gc.h>
 #include <gc/cord.h>
+#include <gmp.h>
 #include <limits.h>
 #include <stdbool.h>
 #include <stdint.h>
@@ -19,6 +20,7 @@
 #include "array.h"
 #include "functions.h"
 #include "halfsiphash.h"
+#include "integers.h"
 #include "text.h"
 #include "types.h"
 
@@ -248,11 +250,12 @@ public find_result_t Text$find(CORD str, CORD pat)
     return (pos == CORD_NOT_FOUND) ? (find_result_t){.status=FIND_FAILURE} : (find_result_t){.status=FIND_SUCCESS, .index=(int32_t)pos};
 }
 
-public CORD Text$replace(CORD text, CORD pat, CORD replacement, int64_t limit)
+public CORD Text$replace(CORD text, CORD pat, CORD replacement, Int_t int_limit)
 {
     if (!text || !pat) return text;
     CORD ret = CORD_EMPTY;
     size_t pos = 0, pat_len = CORD_len(pat);
+    int64_t limit = Int$as_i64(int_limit);
     for (size_t found; limit != 0 && (found=CORD_str(text, pos, pat)) != CORD_NOT_FOUND; --limit) {
         ret = CORD_all(ret, CORD_substr(text, pos, found - pos), replacement);
         pos = found + pat_len;
@@ -271,7 +274,7 @@ public array_t Text$split(CORD str, CORD split)
     for (int64_t i = 0; ; ) {
         size_t non_split = u8_strcspn(ustr + i, usplit);
         CORD chunk = CORD_substr((CORD)ustr, i, non_split);
-        Array$insert(&strings, &chunk, 0, sizeof(CORD));
+        Array$insert(&strings, &chunk, I(0), sizeof(CORD));
 
         i += non_split;
 
@@ -306,7 +309,7 @@ public array_t Text$clusters(CORD text)
         char cluster_buf[len+1];
         strlcpy(cluster_buf, (char*)pos, len+1);
         CORD cluster = CORD_from_char_star(cluster_buf);
-        Array$insert(&clusters, &cluster, 0, sizeof(CORD));
+        Array$insert(&clusters, &cluster, I(0), sizeof(CORD));
         pos = next;
     }
 
@@ -351,7 +354,7 @@ public array_t Text$bytes(CORD text)
     return ret;
 }
 
-public int64_t Text$num_clusters(CORD text)
+public Int_t Text$num_clusters(CORD text)
 {
     const uint8_t *ustr = (const uint8_t*)CORD_to_const_char_star(text);
     int64_t num_clusters = 0;
@@ -361,26 +364,26 @@ public int64_t Text$num_clusters(CORD text)
         ++num_clusters;
         pos = next;
     }
-    return num_clusters;
+    return I(num_clusters);
 }
 
-public int64_t Text$num_codepoints(CORD text)
+public Int_t Text$num_codepoints(CORD text)
 {
     uint8_t buf[128] = {0}; size_t norm_len = sizeof(buf);
     uint8_t *normalized = _normalize(text, buf, &norm_len);
     int64_t num_codepoints = u8_mbsnlen(normalized, norm_len-1);
     if (normalized != buf) free(normalized);
-    return num_codepoints;
+    return I(num_codepoints);
 }
 
-public int64_t Text$num_bytes(CORD text)
+public Int_t Text$num_bytes(CORD text)
 {
     uint8_t norm_buf[128] = {0}; size_t norm_len = sizeof(norm_buf);
     uint8_t *normalized = _normalize(text, norm_buf, &norm_len);
     --norm_len; // NUL byte
     if (!normalized) errx(1, "Unicode normalization error!");
     if (normalized != norm_buf) free(normalized);
-    return norm_len;
+    return I(norm_len);
 }
 
 public array_t Text$character_names(CORD text)
diff --git a/builtins/text.h b/builtins/text.h
index d738125f..798b559e 100644
--- a/builtins/text.h
+++ b/builtins/text.h
@@ -7,6 +7,8 @@
 #include <stdbool.h>
 #include <stdint.h>
 
+#include "datatypes.h"
+#include "integers.h"
 #include "types.h"
 #include "where.h"
 
@@ -29,15 +31,15 @@ bool Text$has(CORD str, CORD target, Where_t where);
 CORD Text$without(CORD str, CORD target, Where_t where);
 CORD Text$trimmed(CORD str, CORD skip, Where_t where);
 find_result_t Text$find(CORD str, CORD pat);
-CORD Text$replace(CORD text, CORD pat, CORD replacement, int64_t limit);
+CORD Text$replace(CORD text, CORD pat, CORD replacement, Int_t limit);
 array_t Text$split(CORD str, CORD split);
 CORD Text$join(CORD glue, array_t pieces);
 array_t Text$clusters(CORD text);
 array_t Text$codepoints(CORD text);
 array_t Text$bytes(CORD text);
-int64_t Text$num_clusters(CORD text);
-int64_t Text$num_codepoints(CORD text);
-int64_t Text$num_bytes(CORD text);
+Int_t Text$num_clusters(CORD text);
+Int_t Text$num_codepoints(CORD text);
+Int_t Text$num_bytes(CORD text);
 array_t Text$character_names(CORD text);
 
 extern const TypeInfo $Text;
diff --git a/builtins/tomo.h b/builtins/tomo.h
index bbf48e2a..637975f4 100644
--- a/builtins/tomo.h
+++ b/builtins/tomo.h
@@ -5,6 +5,7 @@
 
 #include <gc.h>
 #include <gc/cord.h>
+#include <gmp.h>
 #include <stdbool.h>
 #include <stdint.h>
 #include <sys/param.h>