Skip to content

Instantly share code, notes, and snippets.

@skeeto
Created November 1, 2024 16:41
Show Gist options
  • Save skeeto/e8e094a2ca4dce49dee1097826b67417 to your computer and use it in GitHub Desktop.
Save skeeto/e8e094a2ca4dce49dee1097826b67417 to your computer and use it in GitHub Desktop.
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define new(a, n, t) (t *)alloc(a, n, sizeof(t), _Alignof(t))
#define S(s) (Str){(uint8_t *)s, sizeof(s)-1}
typedef struct {
char *beg;
char *end;
} Arena;
static void *alloc(Arena *a, ptrdiff_t count, ptrdiff_t size, ptrdiff_t align)
{
ptrdiff_t pad = -(uintptr_t)a->beg & (align - 1);
assert(count < (a->end - a->beg - pad)/size);
void *r = a->beg + pad;
a->beg += pad + count*size;
return memset(r, 0, count*size);
}
typedef struct {
uint8_t *data;
ptrdiff_t len;
} Str;
static Str clone(Arena *a, Str s)
{
Str r = s;
r.data = new(a, r.len, uint8_t);
memcpy(r.data, s.data, r.len);
return r;
}
static Str concat(Arena *a, Str head, Str tail)
{
if (!head.data || a->beg != (char *)(head.data+head.len)) {
head = clone(a, head);
}
head.len += clone(a, tail).len;
return head;
}
static void reverse(Str s)
{
ptrdiff_t len = s.len;
for (ptrdiff_t i = 0; i < len/2; i++) {
uint8_t swap = s.data[i ];
s.data[i ] = s.data[len-i-1];
s.data[len-i-1] = swap;
}
}
static Str big_add(Str s1, Str s2, Arena *a)
{
if (s1.len < s2.len) {
return big_add(s2, s1, a);
}
uint8_t carry = 0;
Str result = {0};
for (ptrdiff_t i = s1.len - 1, j = s2.len - 1; i >= 0 || j >= 0; i--, j--) {
uint8_t digit1 = (i >= 0) ? s1.data[i] - '0' : 0;
uint8_t digit2 = (j >= 0) ? s2.data[j] - '0' : 0;
uint8_t sum = digit1 + digit2 + carry;
uint8_t addend = (sum % 10) + '0';
result = concat(a, result, (Str){&addend, 1});
carry = sum / 10;
}
if (carry) {
uint8_t addend = carry + '0';
result = concat(a, result, (Str){&addend, 1});
}
reverse(result);
return result;
}
int main(void)
{
ptrdiff_t cap = (ptrdiff_t)1<<21;
char *mem = malloc(cap);
Arena a = {mem, mem+cap};
{
Arena scratch = a; // auto-free on scope exit
Str result = big_add(
S("263693074296026866666830282074"),
S("269988572666773536645581659724"), &scratch
);
printf("WANT 533681646962800403312411941798\n");
printf("GOT %.*s\n", (int)result.len, result.data);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment