in progress mini 128bit unsigned integer; totally unoptimized

uint128.c

#include "uint128.h"
#include "assert.h"
#include <string.h>
#include <stdio.h>

static inline void uint128_set_bit(uint128_t a, uint8_t idx)
{
    assert(idx < 128);
    a[idx/8] |= 1 << (7 - idx%8);
}

static inline void uint128_clr_bit(uint128_t a, uint8_t idx)
{
    assert(idx < 128);
    a[idx/8] &= ~(1 << (7 - idx%8));
}
static inline void uint128_asgn_bit(uint128_t a, uint8_t idx, bool value)
{
    if(value)
        uint128_set_bit(a, idx);
    else
        uint128_clr_bit(a, idx);
}

static inline bool uint128_test_bit(uint128_t a, uint8_t idx)
{
    assert(idx < 128);
    return (a[idx/8] >> (7 - idx%8)) & 0x01;
}

static inline void uint128_cpy_bit(uint128_t a, uint8_t src_bit, uint8_t dst_bit)
{
    assert(src_bit < 128 && dst_bit < 128);
    uint128_asgn_bit(a, dst_bit, uint128_test_bit(a, src_bit));
}

void uint128_lshift(uint128_t a, uint8_t places)
{
    assert(places <= 128);
    for(uint8_t dst_bit = 0; dst_bit < 128; ++dst_bit) {
        if(dst_bit < 128-places)
            uint128_cpy_bit(a, dst_bit + places, dst_bit);
        else
            uint128_clr_bit(a, dst_bit);
    }
}

void uint128_clear(uint128_t a)
{
    memset(a, 0, sizeof(uint128_t));
}
void uint128_init(uint128_t a, uint16_t initial_value)
{
    uint128_clear(a);
    a[15] = initial_value & 0xff;
    a[14] = initial_value >> 8;
}

// out = a + b
void uint128_add(uint128_t out, uint128_t const a, uint128_t const b)
{
    uint8_t carry = 0;
    for(int i = 15; i >= 0; --i) {
        out[i] = a[i] + b[i] + carry;
        carry  = (a[i] > out[i]);
    }
}
void uint128_add_inplace(uint128_t a, uint128_t const b)
{
    uint8_t carry = 0, old;
    for(int i = 15; i >= 0; --i) {
        old   = a[i];
        a[i] += b[i] + carry;
        carry = (old > a[i]);
    }
}

// out = a * b
void uint128_mul(uint128_t out, uint128_t const a, uint128_t const b)
{
    uint8_t m = 16, n = 16;
    for(int i = 0; i < 16 && a[i] == 0x00; ++i, --m);
    for(int i = 0; i < 16 && b[i] == 0x00; ++i, --n);
    assert(m+n <= 16);
     
    uint128_clear(out);
    for(uint8_t j = 0; j < n; ++j) {
        uint16_t carry = 0;
        for(int i = 0; i < m; ++i) {
            uint16_t t = a[15-i]*b[15-j] + out[15-i-j] + carry;
            out[15-i-j] = t&0xff;
            carry = t >> 8;
        }
        out[15-j-m] = carry;
    }
}

// out = a / b
void uint128_div(uint128_t out, uint128_t const a, uint128_t const b)
{
    uint8_t m = 16, n = 16;
    for(int i = 0; i < 16 && a[i] == 0x00; ++i, --m);
    for(int i = 0; i < 16 && b[i] == 0x00; ++i, --n);
    assert(m+n <= 16 && m < n);
     
    uint128_clear(out);
    for(uint8_t j = 0; j < n; ++j) {
        uint16_t carry = 0;
        for(int i = 0; i < m; ++i) {
            uint16_t t = a[15-i]*b[15-j] + out[15-i-j] + carry;
            out[15-i-j] = t&0xff;
            carry = t >> 8;
        }
        out[15-j-m] = carry;
    }
}

void uint128_atoi(uint128_t out, const char *str, uint8_t len)
{
    assert(len <= 36 && len%4 == 0);

    uint128_clear(out);
    uint128_t tmp1, tmp2;
    // Shift by 1000 at a time
    static const uint128_t shift = {
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x27, 0x10
    };
    uint128_t mul = {
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01
    };
    for(int16_t i = len; i > 0; i -= 4) {
        uint16_t part = (str[i-1]-'0')     + (str[i-2]-'0')*10
                      + (str[i-3]-'0')*100 + (str[i-4]-'0')*1000;
        uint128_init(tmp1, part);
        uint128_mul(tmp2, tmp1, mul);
        
        uint128_add_inplace(out, tmp2);
        uint128_mul(tmp1, mul, shift);
        memcpy(mul, tmp1, sizeof(uint128_t));
    }
}

#ifdef __APPLE__
uint32_t uint128_itoa(uint128_t n, uint8_t *buf, uint32_t max_len)
{
    // vU128 is little endian
    vU128 bignum = {0};
    for(int i = 0; i < 16; ++i) {
        ((uint8_t*)&bignum)[i-1] = n[16-i];
    }
    vU128 zero = {0};
    vU128 ten = {0};
    vU128 rem;
    ten.s.LSW = 10;
        
    uint32_t len = 0;
    while(memcmp(&bignum, &zero, sizeof(vU128)) != 0 && len < max_len-1) {
        bignum.v = vU128Divide(bignum.v, ten.v, &rem.v);
        buf[len++] = rem.s.LSW + '0';
    }
    for(int i = 0, j = len-1; i < j; ++i, --j) {
        uint8_t tmp = buf[j];
        buf[j] = buf[i];
        buf[i] = tmp;
    }
    buf[len] = '\0';
    return len;
}
#endif

#ifdef DEBUG
void uint128_print_hex(uint128_t a)
{
    for(uint8_t i = 0; i < 16; ++i) {
        printf("%02x ", a[i]);
    }
}

void uint128_print_bin(uint128_t a)
{
    for(int i = 0; i < 128; ++i) {
        printf("%d", uint128_test_bit(a, i));
    }
}
#endif


//int main() {
//    uint128_t a = { 0x12, 0x34, 0x56, 0x78, 0x90, 0xab, 0xcd, 0xef, 0x12, 0x34, 0x56, 0x78, 0x90, 0xab, 0xcd, 0xff };
//    uint128_t b = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff };
//    uint128_t c = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
//
//    #define LINE() puts("-------------------------------------------------------------");
//    uint128_print_hex(a); puts("| orig");
//    LINE();
//
//    uint128_add(c, a, b);
//    uint128_print_hex(c); puts("| c = a + b");
//    LINE();
//
//    uint128_init(a, 300);
//    uint128_print_hex(a); puts("| a = 300");
//    LINE();
//
//    uint128_lshift(a, 7);
//    uint128_print_hex(a); puts("| a << 7");
//    LINE();
//
//    uint128_init(a, 300);
//    uint128_init(b, 65535);
//    uint128_print_hex(a); puts("| a = 300");
//    uint128_print_hex(b); puts("| b = 10000");
//    LINE();
//
//    uint128_mul(c, a, b);
//    uint128_print_hex(c); puts("| c = a * b");
//    LINE();
//
//    char * bignum = "123456789123456789123456789123456789";
//    uint128_atoi(c, bignum, strlen(bignum));
//    uint128_print_hex(c); printf("| c = atoi(%s)\n", bignum);
//    LINE();
//}

uint128.h

#ifndef UINT128_H
#define UINT128_H
#include <stdint.h>
#include <stdbool.h>

typedef uint8_t uint128_t[16]; // Big endian

void uint128_lshift(uint128_t a, uint8_t places);

void uint128_clear(uint128_t a);
void uint128_init(uint128_t a, uint16_t initial_value);

// out = a + b
void uint128_add(uint128_t out, uint128_t const a, uint128_t const b);
void uint128_add_inplace(uint128_t a, uint128_t const b);
// out = a * b
void uint128_mul(uint128_t out, uint128_t const a, uint128_t const b);

// String->uint128
// String must be of length divisible by 4 and no longer than 36 digits
void uint128_atoi(uint128_t out, const char *str, uint8_t len);

#ifdef DEBUG
void uint128_print_hex(uint128_t a);
void uint128_print_bin(uint128_t a);
#endif

#ifdef __APPLE__
// Uses Apple's vBigNum. Returns the length of the resulting string
uint32_t uint128_itoa(uint128_t n, uint8_t *buf, uint32_t max_len);
#endif

#endif