~jderose/filestore/v1-on

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <string.h>

#define DMEDIA_LEAF_SIZE 8388608
#define DMEDIA_DIGEST_BITS 280
#define DMEDIA_DIGEST_BYTES 35
#define DMEDIA_DIGEST_B32LEN 56
#define DMEDIA_DIGEST_B32LEN_T 57

/* For now so we don't have any issues round-tripping values through JavaScript,
we're setting a "soft" file-size limit at 2**53 bytes (the max integer that
fully works in JavaScript).  But this is quite big, approximately 9.01 PB for
a single file: */
const uint64_t DMEDIA_MAX_FILE_SIZE = 9007199254740992ul;

/* With our current 8 MiB leaf-size and the above 2**53 "soft" max-file-size,
that means will have at most 2**30 leaves: */
const uint32_t DMEDIA_MAX_LEAF_COUNT = 1073741824u;


/*******************************************************************************
    Convert the leaf-index and file-size to their UTF-8 encoded decimal forms.

These byte-array values are used for the Skein `key` parameter in order to
cryptographically tie the leaf-hash to the leaf-index, and the root-hash to the
file-size.

By hashing these integers according to their decimal string representation (as
opposed to say their unsigned 64-bit little-endian representation), the hashing
protocol can support arbitrarily large files, and in an endian-neutral fashion
(just like UTF-8).

We hope the V1 protocol will have at least a 10-year useful lifetime, but it
could be even longer, perhaps 20 years.  And with confidence we can say that
media files 20 years into the future... will be bigger.  So support for
arbitrarily large files (at the protocol level) is critical.

Our Python reference implementation can already support arbitrarily large files
thanks to the arbitrary precision `int` type in Python3.  But in practice, it's
not worth the effort for every implementation to support arbitrarily large files
*today*... it's only important that the protocol design itself support
arbitrarily large files.

Our guidance for C implementations is to use an unsigned 64-bit int for the
file-size, and an unsigned 32-bit int for the leaf-index.  Out of respect for
the differently-abled JavaScript, we recommend implementations set a "soft"
file-size limit of 2**53 bytes (approximately 9.01 PB), which with our 8 MiB
leaf-size gives us a "soft" leaf-count limit of 2**30, thus we can use an
unsigned 32-bit int for the leaf-index.

Note that in C implementations (or any other), the string-terminating '\0'
should *not* be included in the key.
*/

// Length of max 32 and 64-bit decimal strings, including the terminating '\0':
#define DMEDIA_KEY32_LEN 11
#define DMEDIA_KEY64_LEN 21

typedef struct {
    size_t len;
    uint8_t data[DMEDIA_KEY32_LEN];
} DmediaKey32;

typedef struct {
    size_t len;
    uint8_t data[DMEDIA_KEY64_LEN];
} DmediaKey64;

DmediaKey32
dmedia_uint32_to_key(uint32_t value)
{
    DmediaKey32 key;
    key.len = snprintf(&key.data[0], DMEDIA_KEY32_LEN, "%u", value);
    assert(key.len > 0);
    assert(key.len < DMEDIA_KEY32_LEN);
    return key;
}

DmediaKey64
dmedia_uint64_to_key(uint64_t value)
{
    DmediaKey64 key;
    key.len = snprintf(&key.data[0], DMEDIA_KEY64_LEN, "%lu", value);
    assert(key.len > 0);
    assert(key.len < DMEDIA_KEY64_LEN);
    return key;
}


/*******************************************************************************
    Base32-encode the root-hash (or leaf-hash for testing).
*/

static const uint8_t base32[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";

void
dmedia_digest_to_base32(const uint8_t *src, uint8_t *dst)
{
    size_t i, j;
    uint16_t taxi = 0;
    uint8_t bits = 0;

    // `bits` take the `taxi` from `src` to `dst`, experience change:
    for (i=j=0; i<DMEDIA_DIGEST_BYTES; i++) {
        taxi = (taxi << 8) | src[i];
        bits += 8;
        while (bits >= 5) {
            bits -= 5;
            dst[j] = base32[(taxi >> bits) & 0x1f];
            j++;
        }
    }
    dst[j] = '\0';  // Terminate the array  

    // Okay, now check our maths:
    assert(bits == 0);
    assert(i == DMEDIA_DIGEST_BYTES);
    assert(j == DMEDIA_DIGEST_B32LEN);
}


/*******************************************************************************
    Simple binary buffers with length and a data pointer.
*/

typedef struct {
    size_t len;
    uint8_t *data;
} DmediaBuffer;

DmediaBuffer
dmedia_buffer_new()
{
    DmediaBuffer buf;
    buf.len = 0;
    buf.data = NULL;
    return buf;
}

DmediaBuffer
dmedia_buffer_create(size_t len)
{
    DmediaBuffer buf;
    assert(len > 0);
    assert(len <= DMEDIA_LEAF_SIZE);
    buf.len = len;
    buf.data = malloc(len);
    assert(buf.data != NULL);
    return buf;
}

// Allocate (len + 1) bytes, terminate with a '\0'
DmediaBuffer
dmedia_buffer_create_and_terminate(size_t len)
{
    DmediaBuffer buf;
    uint8_t *data;
    assert(len > 0);
    assert(len <= DMEDIA_LEAF_SIZE);
    buf.len = len;
    buf.data = malloc(len + 1);
    assert(buf.data != NULL);

    // Terminate
    data = (buf.data + len);
    *data = '\0';
    return buf;
}

uint8_t
dmedia_buffer_free(DmediaBuffer *buf)
{
    buf->len = 0;
    if (buf->data != NULL) {
        free(buf->data);
        buf->data = NULL;
        return 1;
    }
    return 0;
}


/*******************************************************************************
    Protocol building blocks: hash_leaf() and hash_root()
*/

uint8_t
dmedia_hash_leaf(uint32_t leaf_index, DmediaBuffer leaf_data, uint8_t *digest)
{
    DmediaKey32 key;

    // Similar value checking as Protocol.hash_leaf():
    if (leaf_index >= DMEDIA_MAX_LEAF_COUNT) {
        return 1;
    }
    if (leaf_data.len < 1) {
        return 2;
    }
    if (leaf_data.len > DMEDIA_LEAF_SIZE) {
        return 3;
    }
    if (leaf_data.data == NULL) {
        return 4;
    }

    key = dmedia_uint32_to_key(leaf_index);

    // Dummy implementation for now:
    size_t i;
    for (i=0; i<35; i++) {
        digest[i] = '+';
    }

    return 0;
}

uint8_t
dmedia_hash_root(uint64_t file_size, DmediaBuffer leaf_hashes, uint8_t *digest)
{
    DmediaKey64 key;
    size_t leaf_count;
    uint64_t low, high;

    // Similar value checking as Protocol.hash_root():
    if (file_size < 1) {
        return 1;
    }
    if (file_size > DMEDIA_MAX_FILE_SIZE) {
        return 2;
    }
    if (leaf_hashes.len < DMEDIA_DIGEST_BYTES) {
        return 3;
    }
    if (leaf_hashes.len % DMEDIA_DIGEST_BYTES != 0) {
        return 4;
    }
    if (leaf_hashes.data == NULL) {
        return 5;
    }

    // Check file_size bounds:
    leaf_count = leaf_hashes.len / DMEDIA_DIGEST_BYTES;
    low = (leaf_count - 1) * DMEDIA_LEAF_SIZE + 1;
    high = leaf_count * DMEDIA_LEAF_SIZE;
    if (file_size < low) {
        return 6;
    }
    if (file_size > high) {
        return 7;
    }

    key = dmedia_uint64_to_key(file_size);

    // Dummy implementation for now:
    size_t i;
    for (i=0; i<35; i++) {
        digest[i] = '+';
    }

    return 0;
}


/*******************************************************************************
    Simple linked-list that DmediaHasher uses to accumulate leaf-hashes
*/

typedef struct _DmediaNode {
    uint32_t index;
    uint8_t digest[DMEDIA_DIGEST_BYTES];
    struct _DmediaNode *next;
} DmediaNode;

DmediaNode *
dmedia_node_new(uint32_t index)
{
    DmediaNode *self;
    self = (DmediaNode *) malloc(sizeof(DmediaNode));
    self->index = index;
    self->next = NULL;
    return self;
}

typedef struct {
    uint32_t count;
    DmediaNode *head;
    DmediaNode *tail;
} DmediaList;

DmediaList
dmedia_list_new()
{
    DmediaList self;
    self.count = 0;
    self.head = NULL;
    self.tail = NULL;
    return self;
}

DmediaNode *
dmedia_list_extend(DmediaList *self)
{
    DmediaNode *node;
    node = dmedia_node_new(self->count);
    self->count++;
    if (NULL == self->head) {
        self->head = node;
    }
    if (NULL != self->tail) {
        self->tail->next = node;
    }
    self->tail = node;
    return node;
}

DmediaBuffer
dmedia_list_to_buffer(DmediaList *self)
{
    DmediaBuffer buf;
    DmediaNode *node, *next;
    uint8_t *dst;
    uint32_t count = 0;

    assert(self->count > 0);
    assert(self->head != NULL);
    assert(self->tail != NULL);
    assert(self->tail->index + 1 == self->count);

    buf = dmedia_buffer_create(self->count * DMEDIA_DIGEST_BYTES);
    dst = buf.data;
    node = self->head;
    while (NULL != node) {
        assert(count < self->count);
        count++;
        next = node->next;
        if (NULL == next) {
            assert(self->tail == node);
        }
        memcpy(dst, node->digest, DMEDIA_DIGEST_BYTES);
        dst += DMEDIA_DIGEST_BYTES; 
        node = next;
    }
    assert(count == self->count); 
    return buf;
}

uint32_t
dmedia_list_free(DmediaList *self)
{
    uint32_t count = 0;
    DmediaNode *node, *next;
    node = self->head;
    while (NULL != node) {
        count++;
        next = node->next;
        free(node);
        if (NULL == next) {
            assert(self->tail == node);
        }
        node = next;
    }
    assert(self->count == count);
    self->count = 0;
    self->head = NULL;
    self->tail = NULL;
    return count;
}


/*******************************************************************************
    Port of the Python Hasher class... high level API most apps will use.
*/

typedef struct {
    uint32_t index;
    DmediaBuffer buf;
} DmediaLeaf;

typedef struct {
    uint8_t digest[DMEDIA_DIGEST_BYTES];
    uint8_t id[DMEDIA_DIGEST_B32LEN_T];
    uint64_t file_size;
    DmediaBuffer leaf_hashes;
} DmediaRootHash;

typedef struct {
    uint8_t closed;
    uint64_t file_size;
    DmediaList list;
} DmediaHasher;

DmediaHasher
dmedia_hasher_new()
{
    DmediaHasher self;
    self.closed = 0;
    self.file_size = 0;
    self.list = dmedia_list_new();
    return self;
}

int
dmedia_hasher_free(DmediaHasher *self)
{

}

int
dmedia_hasher_update(DmediaHasher *self, DmediaLeaf *leaf)
{
    
}

DmediaRootHash
dmedia_hasher_finish(DmediaHasher *self)
{
    
}


////////////////////////////////////////////////////////////////////////////////
// Some crude WIP tests

void test_constants()
{
    assert(DMEDIA_LEAF_SIZE == 8 * 1024 * 1024);
    assert(DMEDIA_DIGEST_BYTES == DMEDIA_DIGEST_BITS / 8);
    assert(DMEDIA_DIGEST_B32LEN == DMEDIA_DIGEST_BITS / 5);
    assert(DMEDIA_DIGEST_B32LEN_T == DMEDIA_DIGEST_B32LEN + 1);
    assert(DMEDIA_MAX_LEAF_COUNT == DMEDIA_MAX_FILE_SIZE / DMEDIA_LEAF_SIZE);
}

void test_dmedia_uint32_to_key()
{
    DmediaKey32 key;

    // Largest
    key = dmedia_uint32_to_key(4294967295u);
    assert(key.len == 10);
    assert(strcmp(key.data, "4294967295") == 0);

    // In the middle
    key = dmedia_uint32_to_key(1776 * 6);
    assert(key.len == 5);
    assert(strcmp(key.data, "10656") == 0);

    // Smallest
    key = dmedia_uint32_to_key(0);
    assert(key.len == 1);
    assert(strcmp(key.data, "0") == 0);
}

void test_dmedia_uint64_to_key()
{
    DmediaKey64 key;

    // Largest
    key = dmedia_uint64_to_key(18446744073709551615ul);
    assert(key.len == 20);
    assert(strcmp(key.data, "18446744073709551615") == 0);

    // In the middle
    key = dmedia_uint64_to_key(1776 * 6);
    assert(key.len == 5);
    assert(strcmp(key.data, "10656") == 0);

    // Smallest
    key = dmedia_uint64_to_key(0);
    assert(key.len == 1);
    assert(strcmp(key.data, "0") == 0);
}

void test_dmedia_digest_to_base32()
{
    size_t i;
    uint8_t src[35];
    uint8_t dst[57];

    for (i=0; i<35; i++) {
        src[i] = 0;
    }
    dmedia_digest_to_base32(src, dst);
    assert(strcmp(dst, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA") == 0);

    for (i=0; i<35; i++) {
        src[i] = 255;
    }
    dmedia_digest_to_base32(src, dst);
    assert(strcmp(dst, "77777777777777777777777777777777777777777777777777777777") == 0);

    for (i=0; i<35; i++) {
        src[i] = i;
    }
    dmedia_digest_to_base32(src, dst);
    assert(strcmp(dst, "AAAQEAYEAUDAOCAJBIFQYDIOB4IBCEQTCQKRMFYYDENBWHA5DYPSAIJC") == 0);

    for (i=0; i<35; i++) {
        src[i] = 255 - i;
    }
    dmedia_digest_to_base32(src, dst);
    assert(strcmp(dst, "777P37H37L47R57W6X2PH4XR6DX653PM5PVOT2HH43S6JY7C4HQN7XW5") == 0);

    for (i=0; i<35; i++) {
        src[i] = 255 * (i % 2);
    }
    dmedia_digest_to_base32(src, dst);
    assert(strcmp(dst, "AD7QB7YA74AP6AH7AD7QB7YA74AP6AH7AD7QB7YA74AP6AH7AD7QB7YA") == 0);
}

void test_dmedia_buffer_create()
{
    DmediaBuffer buf;

    buf = dmedia_buffer_create(1048576);
    assert(buf.len == 1048576);
    assert(buf.data != NULL);
    dmedia_buffer_free(&buf);
    assert(buf.len == 0);
    assert(buf.data == NULL);

    buf = dmedia_buffer_create(1776);
    assert(buf.len == 1776);
    assert(buf.data != NULL);
    dmedia_buffer_free(&buf);
    assert(buf.len == 0);
    assert(buf.data == NULL);
}

void test_dmedia_hash_leaf()
{
    uint8_t digest[] = "-----------------------------------";
    assert(sizeof digest == 36);
    DmediaBuffer buf = dmedia_buffer_new();

    // leaf_index >= DMEDIA_MAX_LEAF_COUNT
    assert(dmedia_hash_leaf(DMEDIA_MAX_LEAF_COUNT, buf, digest) == 1);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // leaf_data.len < 1
    assert(dmedia_hash_leaf(0, buf, digest) == 2);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // leaf_data.len > DMEDIA_LEAF_SIZE
    buf.len = DMEDIA_LEAF_SIZE + 1;
    assert(dmedia_hash_leaf(0, buf, digest) == 3);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // leaf_data.data == NULL
    buf.len = 18;
    assert(dmedia_hash_leaf(0, buf, digest) == 4);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // One good one:
    DmediaBuffer one = dmedia_buffer_create(1776);
    assert(dmedia_hash_leaf(0, one, digest) == 0);
    assert(strcmp(digest, "+++++++++++++++++++++++++++++++++++") == 0);
    assert(dmedia_buffer_free(&one) == 1);
}

void test_dmedia_hash_root()
{
    uint8_t digest[] = "-----------------------------------";
    assert(sizeof digest == 36);
    DmediaBuffer buf = dmedia_buffer_new();

    // file_size < 1
    assert(dmedia_hash_root(0, buf, digest) == 1);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // file_size > DMEDIA_MAX_FILE_SIZE
    assert(dmedia_hash_root(DMEDIA_MAX_FILE_SIZE + 1, buf, digest) == 2);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // leaf_hashes.len < DMEDIA_DIGEST_BYTES
    assert(dmedia_hash_root(1776, buf, digest) == 3);
    assert(strcmp(digest, "-----------------------------------") == 0);
    buf.len = 34;
    assert(dmedia_hash_root(1776, buf, digest) == 3);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // leaf_hashes.len % DMEDIA_DIGEST_BYTES != 0
    buf.len = 60;
    assert(dmedia_hash_root(1776, buf, digest) == 4);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // leaf_hashes.data == NULL
    buf.len = 35;
    assert(dmedia_hash_root(1776, buf, digest) == 5);
    assert(strcmp(digest, "-----------------------------------") == 0);

    DmediaBuffer one = dmedia_buffer_create(35);
    DmediaBuffer two = dmedia_buffer_create(70);

    // file_size < low
    assert(dmedia_hash_root(DMEDIA_LEAF_SIZE, two, digest) == 6);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // file_size > high
    assert(dmedia_hash_root(2 * DMEDIA_LEAF_SIZE + 1, two, digest) == 7);
    assert(strcmp(digest, "-----------------------------------") == 0);
    assert(dmedia_hash_root(DMEDIA_LEAF_SIZE + 1, one, digest) == 7);
    assert(strcmp(digest, "-----------------------------------") == 0);

    // One good one:
    assert(dmedia_hash_root(1776, one, digest) == 0);
    assert(strcmp(digest, "+++++++++++++++++++++++++++++++++++") == 0);

    assert(dmedia_buffer_free(&one) == 1);
    assert(dmedia_buffer_free(&two) == 1);
}

void test_dmedia_node_new()
{
    DmediaNode *node;
    node = dmedia_node_new(17);
    assert(node != NULL);
    assert(node->index == 17);
    assert(node->next == NULL);
    free(node);
}

void test_dmedia_list_new()
{
    DmediaList list;
    list = dmedia_list_new();
    assert(list.count == 0);
    assert(list.head == NULL);
    assert(list.tail == NULL);
}

void test_dmedia_list_extend()
{
    DmediaList list;
    DmediaNode *node1, *node2;
    list = dmedia_list_new();

    node1 = dmedia_list_extend(&list);
    assert(list.count == 1);
    assert(list.head == node1);
    assert(list.tail == node1);
    assert(node1->index == 0);
    assert(node1->next == NULL);

    node2 = dmedia_list_extend(&list);
    assert(list.count == 2);
    assert(list.head == node1);
    assert(list.tail == node2);
    assert(node2->index == 1);
    assert(node2->next == NULL);
    assert(node1->next == node2);

    free(node1);
    free(node2);
}

void test_dmedia_list_to_buffer()
{
    DmediaList list;
    DmediaNode *node;
    DmediaBuffer buf;
    uint8_t count = 17;
    uint8_t i, j;
    size_t base;

    list = dmedia_list_new();
    for (i=0; i<count; i++) {
        assert(list.count == i);
        node = dmedia_list_extend(&list);
        assert(list.tail == node);
        assert(list.count == i + 1);

        for (j=0; j<DMEDIA_DIGEST_BYTES; j++) {
            node->digest[j] = i;   
        }
    }

    buf = dmedia_list_to_buffer(&list);
    assert(buf.len == 595);
    for (i=0; i<count; i++) {
        base = i * DMEDIA_DIGEST_BYTES;
        for (j=0; j<DMEDIA_DIGEST_BYTES; j++) {
            assert(buf.data[base + j] == i); 
        }
    }

    assert(dmedia_buffer_free(&buf) == 1);
    assert(dmedia_list_free(&list) == count);
}

void test_dmedia_list_free()
{
    DmediaList list;
    DmediaNode *node;
    uint8_t count = 21;
    uint8_t i;

    list = dmedia_list_new();
    for (i=0; i<count; i++) {
        assert(list.count == i);
        node = dmedia_list_extend(&list);
        assert(list.tail == node);
        assert(list.count == i + 1);
    }
    assert(list.count == count);
    assert(dmedia_list_free(&list) == count);
    assert(list.count == 0);
    assert(list.head == NULL);
    assert(list.tail == NULL);
}

void test_dmedia_hasher_new()
{
    DmediaHasher hasher;
    hasher = dmedia_hasher_new();
    assert(hasher.file_size == 0);
    assert(hasher.closed == 0);
    assert(hasher.list.count == 0);
    assert(hasher.list.head == NULL);
    assert(hasher.list.tail == NULL);
}


// For now, just run the tests:
main ()
{
    test_constants();
    test_dmedia_buffer_create();

    test_dmedia_uint32_to_key();
    test_dmedia_uint64_to_key();
    test_dmedia_digest_to_base32();

    test_dmedia_hash_leaf();
    test_dmedia_hash_root();

    test_dmedia_node_new();
    test_dmedia_list_new();
    test_dmedia_list_extend();
    test_dmedia_list_to_buffer();
    test_dmedia_list_free();
}