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}