JHHM

dedit

a tool for Teeworlds demo file shenanigens
git clone https://jhhm.no/repos/dedit.git

dedit/src/huffman.c

get raw file: huffman.c

1/* This file is part of dedit - a tool for editing Teeworlds/DDNet demo files
2   Copyright (C) 2024 JHHM
3
4   Dedit is free software: you can redistribute it and/or modify
5   it under the terms of the GNU General Public License as published by
6   the Free Software Foundation, either version 3 of the License, or
7   (at your option) any later version.
8
9   Dedit is distributed in the hope that it will be useful,
10   but WITHOUT ANY WARRANTY; without even the implied warranty of
11   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12   GNU General Public License for more details.
13
14   You should have received a copy of the GNU General Public License
15   along with dedit.  If not, see <https://www.gnu.org/licenses/>. */
16
17/*
18  This file is derived from Teeworlds code (Teeworlds License).
19  See NOTICES file for full license details.
20
21  https://github.com/teeworlds/teeworlds/blob/master/src/engine/shared/huffman.cpp
22*/
23
24#define _POSIX_C_SOURCE 200112L
25
26#include "huffman.h"
27
28#define HUFF_MAX_NODES (HUFF_MAX_SYMBOLS) * 2 - 1
29#define HUFF_MAX_SYMBOLS HUFF_EOF_SYMBOL + 1
30#define HUFF_EOF_SYMBOL 256
31
32typedef struct
33{
34    unsigned short symbol;
35    unsigned int bits;
36    unsigned int numbits;
37    unsigned short left, right;
38} huffnode;
39
40typedef struct
41{
42    unsigned short symbol;
43    int freq;
44} constructnode;
45
46const unsigned int freqtable[HUFF_MAX_SYMBOLS] = {
47    1 << 30, 4545, 2657, 431, 1950, 919, 444, 482, 2244, 617, 838, 542, 715, 1814, 304, 240, 754, 212, 647, 186,
48    283,     131,  146,  166, 543,  164, 167, 136, 179,  859, 363, 113, 157, 154,  204, 108, 137, 180, 202, 176,
49    872,     404,  168,  134, 151,  111, 113, 109, 120,  126, 129, 100, 41,  20,   16,  22,  18,  18,  17,  19,
50    16,      37,   13,   21,  362,  166, 99,  78,  95,   88,  81,  70,  83,  284,  91,  187, 77,  68,  52,  68,
51    59,      66,   61,   638, 71,   157, 50,  46,  69,   43,  11,  24,  13,  19,   10,  12,  12,  20,  14,  9,
52    20,      20,   10,   10,  15,   15,  12,  12,  7,    19,  15,  14,  13,  18,   35,  19,  17,  14,  8,   5,
53    15,      17,   9,    15,  14,   18,  8,   10,  2173, 134, 157, 68,  188, 60,   170, 60,  194, 62,  175, 71,
54    148,     67,   167,  78,  211,  67,  156, 69,  1674, 90,  174, 53,  147, 89,   181, 51,  174, 63,  163, 80,
55    167,     94,   128,  122, 223,  153, 218, 77,  200,  110, 190, 73,  174, 69,   145, 66,  277, 143, 141, 60,
56    136,     53,   180,  57,  142,  57,  158, 61,  166,  112, 152, 92,  26,  22,   21,  28,  20,  26,  30,  21,
57    32,      27,   20,   17,  23,   21,  30,  22,  22,   21,  27,  25,  17,  27,   23,  18,  39,  26,  15,  21,
58    12,      18,   18,   27,  20,   18,  15,  19,  11,   17,  33,  12,  18,  15,   19,  18,  16,  26,  17,  18,
59    9,       10,   25,   22,  22,   17,  20,  16,  6,    16,  15,  20,  14,  18,   24,  335, 1517};
60
61huffnode *rootnode;
62huffnode nodes[HUFF_MAX_NODES];
63int numnodes;
64
65void merge(constructnode **arr, int left, int middle, int right)
66{
67    int i, j, k;
68    int larrlen = middle - left + 1;
69    int rarrlen = right - middle;
70
71    constructnode *larr[larrlen], *rarr[rarrlen];
72
73    for (i = 0; i < larrlen; i++)
74        larr[i] = arr[left + i];
75    for (j = 0; j < rarrlen; j++)
76        rarr[j] = arr[middle + 1 + j];
77
78    i = j = 0;
79    k = left;
80
81    while (i < larrlen && j < rarrlen)
82    {
83        if (larr[i]->freq >= rarr[j]->freq)
84        {
85            arr[k] = larr[i];
86            i++;
87        }
88        else
89        {
90            arr[k] = rarr[j];
91            j++;
92        }
93        k++;
94    }
95    while (i < larrlen)
96    {
97        arr[k] = larr[i];
98        i++;
99        k++;
100    }
101    while (j < rarrlen)
102    {
103        arr[k] = rarr[j];
104        j++;
105        k++;
106    }
107}
108
109void mergesort(constructnode **arr, int left, int right)
110{
111    if (left < right)
112    {
113        int middle = left + (right - left) / 2;
114        mergesort(arr, left, middle);
115        mergesort(arr, middle + 1, right);
116        merge(arr, left, middle, right);
117    }
118}
119
120void setbits(huffnode *node, int bits, unsigned int depth)
121{
122    if (node->right != 0xffff)
123        setbits(&nodes[node->right], bits | (1 << depth), depth + 1);
124    if (node->left != 0xffff)
125        setbits(&nodes[node->left], bits, depth + 1);
126
127    if (node->numbits)
128    {
129        node->bits = bits;
130        node->numbits = depth;
131    }
132}
133
134void constructhufftree(const unsigned int *frequencies)
135{
136    constructnode nodesdata[HUFF_MAX_SYMBOLS];
137    constructnode *sortednodes[HUFF_MAX_SYMBOLS];
138
139    for (int i = 0; i < HUFF_MAX_SYMBOLS; i++)
140    {
141        nodes[i].numbits = 0xffffffff;
142        nodes[i].symbol = i;
143        nodes[i].left = 0xffff;
144        nodes[i].right = 0xffff;
145
146        if (i == HUFF_EOF_SYMBOL)
147            nodesdata[i].freq = 1;
148        else
149            nodesdata[i].freq = frequencies[i];
150        nodesdata[i].symbol = i;
151        sortednodes[i] = &nodesdata[i];
152    }
153
154    numnodes = HUFF_MAX_SYMBOLS;
155
156    for (int numnodesleft = HUFF_MAX_SYMBOLS; numnodesleft > 1; numnodesleft--)
157    {
158        mergesort(sortednodes, 0, numnodesleft - 1);
159        nodes[numnodes].numbits = 0;
160        nodes[numnodes].left = sortednodes[numnodesleft - 1]->symbol;
161        nodes[numnodes].right = sortednodes[numnodesleft - 2]->symbol;
162        sortednodes[numnodesleft - 2]->symbol = numnodes;
163        sortednodes[numnodesleft - 2]->freq = sortednodes[numnodesleft - 1]->freq + sortednodes[numnodesleft - 2]->freq;
164        numnodes++;
165    }
166    rootnode = &nodes[numnodes - 1];
167    setbits(rootnode, 0, 0);
168}
169
170void inithuff(const unsigned int *frequencies)
171{
172    if (!frequencies)
173        constructhufftree(freqtable);
174    else
175        constructhufftree(frequencies);
176}
177
178int compresshuff(const char *inputbuff, int inputsize, char *outputbuff, int outputsize)
179{
180    int outputlen = 0;
181    char bits = 0;
182    char numbits = 0;
183    unsigned short symbol = 0;
184
185    for (int y = 0; y < inputsize; y++)
186    {
187        symbol = (unsigned char)*(inputbuff + y);
188    appendeof:
189        for (unsigned int i = 0; i < nodes[symbol].numbits; i++)
190        {
191            char bit = (nodes[symbol].bits >> i) & 1;
192            bits |= (bit << numbits);
193            numbits++;
194            if (numbits == 8)
195            {
196                if (outputlen >= outputsize - 1)
197                    return -1;
198                outputbuff[outputlen] = bits;
199                outputlen++;
200                numbits = 0;
201                bits = 0;
202            }
203        }
204    }
205    if (symbol != HUFF_EOF_SYMBOL)
206    {
207        symbol = HUFF_EOF_SYMBOL;
208        goto appendeof;
209    }
210    outputbuff[outputlen] = bits;
211    outputlen++;
212    return outputlen;
213}
214
215int decompresshuff(const char *inputbuff, int inputsize, char *outputbuff, int outputsize)
216{
217    int inputoff = 0;
218    int outputlen = 0;
219    int bits = 0;
220    int numbits = 0;
221
222    huffnode *node;
223    while (1)
224    {
225        while (numbits < 24 && inputoff != inputsize)
226        {
227            bits |= (unsigned char)inputbuff[inputoff++] << numbits;
228            numbits += 8;
229        }
230
231        node = rootnode;
232        while (1)
233        {
234            if (bits & 1)
235                node = &nodes[node->right];
236            else
237                node = &nodes[node->left];
238
239            bits >>= 1;
240            numbits--;
241
242            if (node->numbits)
243                break;
244
245            if (numbits == 0)
246                return -1;
247        }
248
249        if (node->symbol == HUFF_EOF_SYMBOL)
250            return outputlen;
251
252        if (outputlen == outputsize)
253            return -1;
254
255        outputbuff[outputlen++] = node->symbol;
256    }
257}