#include "arch.h"

#include <assert.h></assert.h>

#include <stdlib.h></stdlib.h>

#include <string.h></string.h>

//#include <stdio.h></stdio.h>

enum {

    NO_CODE   = 0xffff,

    DICT_SIZE = 0xffff };

int arch_init(Arch *a) {

    memset(a, 0, sizeof(*a));

    a->entries = (Entry*)calloc(sizeof(Entry), DICT_SIZE);

    if (!a->entries) return RES_FAIL;

    for(int i = 0; i < 256; ++i) {

        Entry *e = a->entries + i;

        memset(e->children, 0xff, sizeof(e->children));

        e->value = i;

        a->root.children[i] = i;

    }

    a->nextcode = 0x100;

    a->codebits = 9;

    return RES_DONE;

}

void arch_deinit(Arch *a) {

    free(a->entries);

    memset(a, 0, sizeof(*a));

}

static void arch_entry_use(Arch *a, Entry *e) {

    if (!e->parent) return;

    if (e->next) {

        if (e->prev) e->prev->next = e->next;

                     else a->first = e->next;

        e->next->prev = e->prev;

        e->prev = a->last;

        e->next = NULL;

        a->last = a->last->next = e;

    }

    arch_entry_use(a, e->parent);

}

static Entry* arch_entry_add(Arch *a, Entry *parent, Byte value) {

    Entry *e;

    Code nextcode = a->nextcode;

    if (nextcode < DICT_SIZE) {

        ++a->nextcode;

        if (!(nextcode & a->nextcode)) ++a->codebits;

        assert(a->codebits <= 16);

        assert(nextcode < DICT_SIZE);

        e = a->entries + nextcode;

        memset(e->children, 0xff, sizeof(e->children));

        e->prev = a->last; e->next = NULL;

        if (a->last) a->last->next = e;

                     else a->first = e;

        a->last = e;

    } else {

        arch_entry_use(a, parent);

        e = a->first;

        assert(e);

        assert(e != parent);

        assert(e->parent);

        assert(e->parent->children[e->value] == e - a->entries);

        e->parent->children[e->value] = NO_CODE;

        //assert(!e->prev);

        //assert(e->next);

        //a->first = e->next; e->prev = a->last;

        //e->next = e->next->prev = NULL;

        //a->last = a->last->next = e;

    }

    assert(parent);

    assert(parent->children[value] == NO_CODE);

    e->value = value;

    e->parent = parent;

    parent->children[value] = e - a->entries;

    //printf("add code: %d\n", (int)(e - a->entries));

    //for(int i = 0; i < 256; ++i) assert(e->children[i] == NO_CODE);

    arch_entry_use(a, e);

    return e;

}

int arch_deflate(Arch *a, int final) {

    if (a->rb.bits) return RES_FAIL;

    while(1) {

        if (a->wb.end - a->wb.cur < 5) return RES_RETRY;

        Entry *e = &a->root;

        Byte *bp = a->rb.cur;

        Bits codebits = a->codebits;

        while(1) {

            Byte b;

            if (!buf_read_byte(&a->rb, &b)) {

                if (final) { arch_entry_use(a, e); break; }

                a->rb.cur = bp;

                break;

            }

            if (e->children[b] == NO_CODE) { e = arch_entry_add(a, e, b); break; }

            e = a->entries + e->children[b];

        }

        if (bp == a->rb.cur) break;

        assert(e);

        assert(e != &a->root);

        Code code; Byte b = e->value;

        if (e->parent) { code = e->parent - a->entries; }

                  else { code = a->nextcode; assert(final); }

        //printf("pos: %d/%d, code %d/%d, byte %d (%c)\n", (int)(a->rb.cur - a->rb.begin), (int)(a->rb.end - a->rb.begin), (int)code, (int)a->nextcode, (int)b, (char)b);

        if ( !buf_write_bits(&a->wb, (((Word)code) << 8) | b, codebits + 8) ) return RES_FAIL;

    }

    if (final && a->rb.cur >= a->rb.end) { buf_write_pad(&a->wb); return RES_DONE; }

    return RES_RETRY;

}

static int arch_entry_write(Arch *a, Entry *e, TinySize count) {

    if (!e->parent) {

        if (a->wb.end - a->wb.cur < count) return 0;

    } else {

        if (!arch_entry_write(a, e->parent, count+1)) return 0;

    }

    //fputc(e->value, stdout);

    buf_write_byte(&a->wb, e->value);

    return 1;

}

int arch_inflate(Arch *a, int final) {

    if (a->wb.bits) return RES_FAIL;

    while(1) {

        Byte *bp = a->rb.cur;

        Bits bb = a->rb.bits;

        Word w;

        if (!buf_read_bits(&a->rb, &w, a->codebits + 8)) break;

        Code code = w >> 8;

        Byte b = w;

        //printf("pos: %d/%d + %d, code %d/%d, byte %d (%c)\n", (int)(a->rb.cur - a->rb.begin), (int)(a->rb.end - a->rb.begin), (int)a->rb.bits, (int)code, (int)a->nextcode, (int)b, (char)b);

        if (code < a->nextcode) {

            Entry *e = &a->entries[code];

            if (!arch_entry_write(a, e, 1)) {

                a->rb.cur = bp;

                a->rb.bits = bb;

                return RES_RETRY;

            }

            //fputc(b, stdout); fputc('\n', stdout);

            if (e->children[b] == NO_CODE) e = arch_entry_add(a, e, b); else arch_entry_use(a, e);

        } else

        if (code != a->nextcode) {

            return RES_FAIL;

        } else {

            //printf("pos: %d/%d + %d, code %d/%d, byte %d (%c)\n", (int)(a->rb.cur - a->rb.begin), (int)(a->rb.end - a->rb.begin), (int)a->rb.bits, (int)code, (int)a->nextcode, (int)b, (char)b);

        }

        if (!buf_write_byte(&a->wb, b)) return RES_FAIL;

    }

    if (final) { buf_read_pad(&a->rb); return RES_DONE; }

    return RES_RETRY;

}