* Wolfenstein: Enemy Territory GPL Source Code
* Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company.
* This file is part of the Wolfenstein: Enemy Territory GPL Source Code
* If you have questions concerning this license or the applicable additional terms, you may contact
* in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
*/
#include "huffenstein.h"
static huffman_t msgHuff;
int Huff_GetBit(unsigned char *fin, int *offset, int *bloc) {
int t;
*bloc = *offset;
t = fin[*bloc >> 3] >> (*bloc & 7) & 0x1;
*bloc = *bloc + 1;
*offset = *bloc;
return t;
}
static int get_bit(unsigned char *fin, int *bloc) {
int t;
t = fin[*bloc >> 3] >> (*bloc & 7) & 0x1;
*bloc = *bloc + 1;
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;
}
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;
}
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;
}
}
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;
}
}
}
}
static void Huff_addRef(huff_t *huff, unsigned char ch) {
node_t *tnode, *tnode2;
if (huff->loc[ch] == NULL) {
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 {
tnode->head = get_ppnode(huff);
*tnode->head = tnode2;
}
} else {
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) {
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]);
}
}
int msg_hData[256] = {
250315, 41193, 6292, 7106, 3730, 3750, 6110, 23283, 33317, 6950, 7838, 9714, 9257, 17259, 3949, 1778,
8288, 1604, 1590, 1663, 1100, 1213, 1238, 1134, 1749, 1059, 1246, 1149, 1273, 4486, 2805, 3472,
21819, 1159, 1670, 1066, 1043, 1012, 1053, 1070, 1726, 888, 1180, 850, 960, 780, 1752, 3296,
10630, 4514, 5881, 2685, 4650, 3837, 2093, 1867, 2584, 1949, 1972, 940, 1134, 1788, 1670, 1206,
5719, 6128, 7222, 6654, 3710, 3795, 1492, 1524, 2215, 1140, 1355, 971, 2180, 1248, 1328, 1195,
1770, 1078, 1264, 1266, 1168, 965, 1155, 1186, 1347, 1228, 1529, 1600, 2617, 2048, 2546, 3275,
2410, 3585, 2504, 2800, 2675, 6146, 3663, 2840, 14253, 3164, 2221, 1687, 3208, 2739, 3512, 4796,
4091, 3515, 5288, 4016, 7937, 6031, 5360, 3924, 4892, 3743, 4566, 4807, 5852, 6400, 6225, 8291,
23243, 7838, 7073, 8935, 5437, 4483, 3641, 5256, 5312, 5328, 5370, 3492, 2458, 1694, 1821, 2121,
1916, 1149, 1516, 1367, 1236, 1029, 1258, 1104, 1245, 1006, 1149, 1025, 1241, 952, 1287, 997,
1713, 1009, 1187, 879, 1099, 929, 1078, 951, 1656, 930, 1153, 1030, 1262, 1062, 1214, 1060,
1621, 930, 1106, 912, 1034, 892, 1158, 990, 1175, 850, 1121, 903, 1087, 920, 1144, 1056,
3462, 2240, 4397, 12136, 7758, 1345, 1307, 3278, 1950, 886, 1023, 1112, 1077, 1042, 1061, 1071,
1484, 1001, 1096, 915, 1052, 995, 1070, 876, 1111, 851, 1059, 805, 1112, 923, 1103, 817,
1899, 1872, 976, 841, 1127, 956, 1159, 950, 7791, 954, 1289, 933, 1127, 3207, 1020, 927,
1355, 768, 1040, 745, 952, 805, 1073, 740, 1013, 805, 1008, 796, 996, 1057, 11457, 13504,
};
void Huff_Init() {
int i, j;
huffman_t *huff = &msgHuff;
memset(&huff->decompressor, 0, sizeof(huff_t));
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;
for (i = 0; i < 256; i++) {
for (j = 0; j < msg_hData[i]; j++) {
Huff_addRef(&msgHuff.decompressor, (unsigned char) i);
}
}
}
void Huff_OffsetReceive(int *ch, unsigned char *fin, int *offset, int *bloc) {
node_t *node = msgHuff.decompressor.tree;
*bloc = *offset;
while (node && node->symbol == INTERNAL_NODE) {
if (get_bit(fin, bloc)) {
node = node->right;
} else {
node = node->left;
}
}
if (!node) {
*ch = 0;
return;
}
*ch = node->symbol;
*offset = *bloc;
}