/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.
Copyright (C) 2000-2013 Darklegion Development
Copyright (C) 2015-2019 GrangerHub

This file is part of Tremulous.

Tremulous is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 3 of the License,
or (at your option) any later version.

Tremulous is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Tremulous; if not, see <https://www.gnu.org/licenses/>

===========================================================================
*/

/* This is based on the Adaptive Huffman algorithm described in Sayood's Data
 * Compression book.  The ranks are not actually stored, but implicitly defined
 * by the location of a node within a doubly-linked list */

#include "huffman.h"

#include "alternatePlayerstate.h"
#include "cvar.h"
#include "msg.h"
#include "q_shared.h"
#include "qcommon.h"

static int bloc = 0;

void Huff_putBit(int bit, uint8_t *fout, int *offset)
{
    bloc = *offset;
    if ((bloc & 7) == 0)
    {
        fout[(bloc >> 3)] = 0;
    }
    fout[(bloc >> 3)] |= bit << (bloc & 7);
    bloc++;
    *offset = bloc;
}

int Huff_getBloc(void) { return bloc; }
void Huff_setBloc(int _bloc) { bloc = _bloc; }
int Huff_getBit(uint8_t *fin, int *offset)
{
    int t;
    bloc = *offset;
    t = (fin[(bloc >> 3)] >> (bloc & 7)) & 0x1;
    bloc++;
    *offset = bloc;
    return t;
}

/* Add a bit to the output file (buffered) */
static void add_bit(char bit, uint8_t *fout)
{
    if ((bloc & 7) == 0)
    {
        fout[(bloc >> 3)] = 0;
    }
    fout[(bloc >> 3)] |= bit << (bloc & 7);
    bloc++;
}

/* Receive one bit from the input file (buffered) */
static int get_bit(uint8_t *fin)
{
    int t;
    t = (fin[(bloc >> 3)] >> (bloc & 7)) & 0x1;
    bloc++;
    return t;
}

static node_t **get_ppnode(huff_t *huff)
{
    node_t **tppnode;
    if (!huff->freelist)
    {
        return &(huff->nodePtrs[huff->blocPtrs++]);
    }
    else
    {
        tppnode = huff->freelist;
        huff->freelist = (node_t **)*tppnode;
        return tppnode;
    }
}

static void free_ppnode(huff_t *huff, node_t **ppnode)
{
    *ppnode = (node_t *)huff->freelist;
    huff->freelist = ppnode;
}

/* Swap the location of these two nodes in the tree */
static void swap(huff_t *huff, node_t *node1, node_t *node2)
{
    node_t *par1, *par2;

    par1 = node1->parent;
    par2 = node2->parent;

    if (par1)
    {
        if (par1->left == node1)
        {
            par1->left = node2;
        }
        else
        {
            par1->right = node2;
        }
    }
    else
    {
        huff->tree = node2;
    }

    if (par2)
    {
        if (par2->left == node2)
        {
            par2->left = node1;
        }
        else
        {
            par2->right = node1;
        }
    }
    else
    {
        huff->tree = node1;
    }

    node1->parent = par2;
    node2->parent = par1;
}

/* Swap these two nodes in the linked list (update ranks) */
static void swaplist(node_t *node1, node_t *node2)
{
    node_t *par1;

    par1 = node1->next;
    node1->next = node2->next;
    node2->next = par1;

    par1 = node1->prev;
    node1->prev = node2->prev;
    node2->prev = par1;

    if (node1->next == node1)
    {
        node1->next = node2;
    }
    if (node2->next == node2)
    {
        node2->next = node1;
    }
    if (node1->next)
    {
        node1->next->prev = node1;
    }
    if (node2->next)
    {
        node2->next->prev = node2;
    }
    if (node1->prev)
    {
        node1->prev->next = node1;
    }
    if (node2->prev)
    {
        node2->prev->next = node2;
    }
}

/* Do the increments */
static void increment(huff_t *huff, node_t *node)
{
    node_t *lnode;

    if (!node)
    {
        return;
    }

    if (node->next != NULL && node->next->weight == node->weight)
    {
        lnode = *node->head;
        if (lnode != node->parent)
        {
            swap(huff, lnode, node);
        }
        swaplist(lnode, node);
    }
    if (node->prev && node->prev->weight == node->weight)
    {
        *node->head = node->prev;
    }
    else
    {
        *node->head = NULL;
        free_ppnode(huff, node->head);
    }
    node->weight++;
    if (node->next && node->next->weight == node->weight)
    {
        node->head = node->next->head;
    }
    else
    {
        node->head = get_ppnode(huff);
        *node->head = node;
    }
    if (node->parent)
    {
        increment(huff, node->parent);
        if (node->prev == node->parent)
        {
            swaplist(node, node->parent);
            if (*node->head == node)
            {
                *node->head = node->parent;
            }
        }
    }
}

void Huff_addRef(huff_t *huff, uint8_t ch)
{
    node_t *tnode, *tnode2;
    if (huff->loc[ch] == NULL)
    { /* if this is the first transmission of this node */
        tnode = &(huff->nodeList[huff->blocNode++]);
        tnode2 = &(huff->nodeList[huff->blocNode++]);

        tnode2->symbol = INTERNAL_NODE;
        tnode2->weight = 1;
        tnode2->next = huff->lhead->next;
        if (huff->lhead->next)
        {
            huff->lhead->next->prev = tnode2;
            if (huff->lhead->next->weight == 1)
            {
                tnode2->head = huff->lhead->next->head;
            }
            else
            {
                tnode2->head = get_ppnode(huff);
                *tnode2->head = tnode2;
            }
        }
        else
        {
            tnode2->head = get_ppnode(huff);
            *tnode2->head = tnode2;
        }
        huff->lhead->next = tnode2;
        tnode2->prev = huff->lhead;

        tnode->symbol = ch;
        tnode->weight = 1;
        tnode->next = huff->lhead->next;
        if (huff->lhead->next)
        {
            huff->lhead->next->prev = tnode;
            if (huff->lhead->next->weight == 1)
            {
                tnode->head = huff->lhead->next->head;
            }
            else
            {
                /* this should never happen */
                tnode->head = get_ppnode(huff);
                *tnode->head = tnode2;
            }
        }
        else
        {
            /* this should never happen */
            tnode->head = get_ppnode(huff);
            *tnode->head = tnode;
        }
        huff->lhead->next = tnode;
        tnode->prev = huff->lhead;
        tnode->left = tnode->right = NULL;

        if (huff->lhead->parent)
        {
            if (huff->lhead->parent->left == huff->lhead)
            { /* lhead is guaranteed to by the NYT */
                huff->lhead->parent->left = tnode2;
            }
            else
            {
                huff->lhead->parent->right = tnode2;
            }
        }
        else
        {
            huff->tree = tnode2;
        }

        tnode2->right = tnode;
        tnode2->left = huff->lhead;

        tnode2->parent = huff->lhead->parent;
        huff->lhead->parent = tnode->parent = tnode2;

        huff->loc[ch] = tnode;

        increment(huff, tnode2->parent);
    }
    else
    {
        increment(huff, huff->loc[ch]);
    }
}

/* Get a symbol */
int Huff_Receive(node_t *node, int *ch, uint8_t *fin)
{
    while (node && node->symbol == INTERNAL_NODE)
    {
        if (get_bit(fin))
        {
            node = node->right;
        }
        else
        {
            node = node->left;
        }
    }
    if (!node)
    {
        return 0;
        //		Com_Error(ERR_DROP, "Illegal tree!");
    }
    return (*ch = node->symbol);
}

/* Get a symbol */
void Huff_offsetReceive(node_t *node, int *ch, uint8_t *fin, int *offset, int maxoffset)
{
    bloc = *offset;
    while (node && node->symbol == INTERNAL_NODE)
    {
        if ( bloc >= maxoffset )
        {
            *ch = 0;
            *offset = maxoffset + 1;
            return;
        }

        if (get_bit(fin))
        {
            node = node->right;
        }
        else
        {
            node = node->left;
        }
    }
    if (!node)
    {
        *ch = 0;
        return;
        //		Com_Error(ERR_DROP, "Illegal tree!");
    }
    *ch = node->symbol;
    *offset = bloc;
}

/* Send the prefix code for this node */
static void send(node_t *node, node_t *child, uint8_t *fout, int maxoffset)
{
    if (node->parent)
    {
        send(node->parent, node, fout, maxoffset);
    }
    if (child)
    {
        if (bloc >= maxoffset)
        {
            bloc = maxoffset + 1;
            return;
        }

        if (node->right == child)
        {
            add_bit(1, fout);
        }
        else
        {
            add_bit(0, fout);
        }
    }
}

/* Send a symbol */
void Huff_transmit(huff_t *huff, int ch, uint8_t *fout, int maxoffset)
{
    int i;
    if (huff->loc[ch] == NULL)
    {
        /* node_t hasn't been transmitted, send a NYT, then the symbol */
        Huff_transmit(huff, NYT, fout, maxoffset);
        for (i = 7; i >= 0; i--)
        {
            add_bit((char)((ch >> i) & 0x1), fout);
        }
    }
    else
    {
        send(huff->loc[ch], NULL, fout, maxoffset);
    }
}

void Huff_offsetTransmit(huff_t *huff, int ch, uint8_t *fout, int *offset, int maxoffset)
{
    bloc = *offset;
    send(huff->loc[ch], NULL, fout, maxoffset);
    *offset = bloc;
}

void Huff_Decompress(struct msg_t *mbuf, int offset)
{
    int ch, cch, i, j, size;
    uint8_t seq[65536];
    uint8_t *buffer;
    huff_t huff;

    size = mbuf->cursize - offset;
    buffer = mbuf->data + offset;

    if (size <= 0)
    {
        return;
    }

    memset(&huff, 0, sizeof(huff_t));
    // Initialize the tree & list with the NYT node
    huff.tree = huff.lhead = huff.ltail = huff.loc[NYT] = &(huff.nodeList[huff.blocNode++]);
    huff.tree->symbol = NYT;
    huff.tree->weight = 0;
    huff.lhead->next = huff.lhead->prev = NULL;
    huff.tree->parent = huff.tree->left = huff.tree->right = NULL;

    cch = buffer[0] * 256 + buffer[1];
    // don't overflow with bad messages
    if (cch > mbuf->maxsize - offset)
    {
        cch = mbuf->maxsize - offset;
    }
    bloc = 16;

    for (j = 0; j < cch; j++)
    {
        ch = 0;
        // don't overflow reading from the messages
        // FIXME: would it be better to have an overflow check in get_bit ?
        if ((bloc >> 3) > size)
        {
            seq[j] = 0;
            break;
        }
        Huff_Receive(huff.tree, &ch, buffer); /* Get a character */
        if (ch == NYT)
        { /* We got a NYT, get the symbol associated with it */
            ch = 0;
            for (i = 0; i < 8; i++)
            {
                ch = (ch << 1) + get_bit(buffer);
            }
        }

        seq[j] = ch; /* Write symbol */

        Huff_addRef(&huff, (uint8_t)ch); /* Increment node */
    }
    mbuf->cursize = cch + offset;
    memcpy(mbuf->data + offset, seq, cch);
}

extern int oldsize;

void Huff_Compress(struct msg_t *mbuf, int offset)
{
    int i, ch, size;
    uint8_t seq[65536];
    uint8_t *buffer;
    huff_t huff;

    size = mbuf->cursize - offset;
    buffer = mbuf->data + +offset;

    if (size <= 0)
    {
        return;
    }

    memset(&huff, 0, sizeof(huff_t));
    // Add the NYT (not yet transmitted) node into the tree/list */
    huff.tree = huff.lhead = huff.loc[NYT] = &(huff.nodeList[huff.blocNode++]);
    huff.tree->symbol = NYT;
    huff.tree->weight = 0;
    huff.lhead->next = huff.lhead->prev = NULL;
    huff.tree->parent = huff.tree->left = huff.tree->right = NULL;

    seq[0] = (size >> 8);
    seq[1] = size & 0xff;

    bloc = 16;

    for (i = 0; i < size; i++)
    {
        ch = buffer[i];
        Huff_transmit(&huff, ch, seq, size << 3); /* Transmit symbol */
        Huff_addRef(&huff, (uint8_t)ch); /* Do update */
    }

    bloc += 8;  // next uint8_t

    mbuf->cursize = (bloc >> 3) + offset;
    memcpy(mbuf->data + offset, seq, (bloc >> 3));
}

void Huff_Init(huffman_t *huff)
{
    memset(&huff->compressor, 0, sizeof(huff_t));
    memset(&huff->decompressor, 0, sizeof(huff_t));

    // Initialize the tree & list with the NYT node
    huff->decompressor.tree = huff->decompressor.lhead = huff->decompressor.ltail = huff->decompressor.loc[NYT] =
        &(huff->decompressor.nodeList[huff->decompressor.blocNode++]);
    huff->decompressor.tree->symbol = NYT;
    huff->decompressor.tree->weight = 0;
    huff->decompressor.lhead->next = huff->decompressor.lhead->prev = NULL;
    huff->decompressor.tree->parent = huff->decompressor.tree->left = huff->decompressor.tree->right = NULL;

    // Add the NYT (not yet transmitted) node into the tree/list */
    huff->compressor.tree = huff->compressor.lhead = huff->compressor.loc[NYT] =
        &(huff->compressor.nodeList[huff->compressor.blocNode++]);
    huff->compressor.tree->symbol = NYT;
    huff->compressor.tree->weight = 0;
    huff->compressor.lhead->next = huff->compressor.lhead->prev = NULL;
    huff->compressor.tree->parent = huff->compressor.tree->left = huff->compressor.tree->right = NULL;
}