1 /*
2 * huffman.c
3 * huffman encoding/decoding for use in hexenworld networking
4 *
5 * $Id: huffman.c,v 1.21 2010-01-11 18:48:19 sezero Exp $
6 *
7 * Copyright (C) 1997-1998 Raven Software Corp.
8 *
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or (at
12 * your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
17 *
18 * See the GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License along
21 * with this program; if not, write to the Free Software Foundation, Inc.,
22 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25 #include <stdlib.h>
26 #include <sys/types.h>
27 #include <stdio.h>
28 #include <string.h>
29 #include <stdarg.h>
30 #include "compiler.h"
31 #include "huffman.h"
32
33 #if defined(__GNUC__) && !(defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L)
34 #define HuffPrintf(fmt, args...) fprintf(stderr, fmt, ##args)
35 #else /* require c99 variadic macros. */
36 #define HuffPrintf(...) fprintf(stderr, __VA_ARGS__)
37 #endif /* HuffPrintf */
38
39 FUNC_NORETURN extern void Sys_Error (const char *error, ...) FUNC_PRINTF(1,2);
40 #ifdef __WATCOMC__
41 #pragma aux Sys_Error aborts;
42 #endif
43
44
45 //
46 // huffman types and vars
47 //
48
49 typedef struct huffnode_s
50 {
51 struct huffnode_s *zero;
52 struct huffnode_s *one;
53 float freq;
54 unsigned char val;
55 unsigned char pad[3];
56 } huffnode_t;
57
58 typedef struct
59 {
60 unsigned int bits;
61 int len;
62 } hufftab_t;
63
64 static void *HuffMemBase = NULL;
65 static huffnode_t *HuffTree = NULL;
66 static hufftab_t HuffLookup[256];
67
68 #ifdef _MSC_VER
69 #pragma warning(disable:4305)
70 /* double to float truncation */
71 #endif
72 static const float HuffFreq[256] =
73 {
74 # include "hufffreq.h"
75 };
76
77
78 //=============================================================================
79
80 //
81 // huffman debugging
82 //
83 #if _DEBUG_HUFFMAN
84
85 static int HuffIn = 0;
86 static int HuffOut= 0;
87 static int freqs[256];
88
ZeroFreq(void)89 static void ZeroFreq (void)
90 {
91 memset(freqs, 0, 256 * sizeof(int));
92 }
93
CalcFreq(const unsigned char * packet,int packetlen)94 static void CalcFreq (const unsigned char *packet, int packetlen)
95 {
96 int ix;
97
98 for (ix = 0; ix < packetlen; ix++)
99 {
100 freqs[packet[ix]]++;
101 }
102 }
103
PrintFreqs(void)104 void PrintFreqs (void)
105 {
106 int ix;
107 float total = 0;
108
109 for (ix = 0; ix < 256; ix++)
110 {
111 total += freqs[ix];
112 }
113
114 if (total > .01)
115 {
116 for (ix = 0; ix < 256; ix++)
117 {
118 HuffPrintf("\t%.8f,\n", ((float)freqs[ix])/total);
119 }
120 }
121
122 ZeroFreq();
123 }
124 #endif /* _DEBUG_HUFFMAN */
125
126
127 //=============================================================================
128
129 //
130 // huffman functions
131 //
132
FindTab(huffnode_t * tmp,int len,unsigned int bits)133 static void FindTab (huffnode_t *tmp, int len, unsigned int bits)
134 {
135 if (!tmp)
136 Sys_Error("no huff node");
137
138 if (tmp->zero)
139 {
140 if (!tmp->one)
141 Sys_Error("no one in node");
142 if (len >= 32)
143 Sys_Error("compression screwd");
144 FindTab (tmp->zero, len+1, bits<<1);
145 FindTab (tmp->one, len+1, (bits<<1)|1);
146 return;
147 }
148
149 HuffLookup[tmp->val].len = len;
150 HuffLookup[tmp->val].bits = bits;
151 return;
152 }
153
154 static unsigned char const Masks[8] =
155 {
156 0x1,
157 0x2,
158 0x4,
159 0x8,
160 0x10,
161 0x20,
162 0x40,
163 0x80
164 };
165
PutBit(unsigned char * buf,int pos,int bit)166 static void PutBit (unsigned char *buf, int pos, int bit)
167 {
168 if (bit)
169 buf[pos/8] |= Masks[pos%8];
170 else
171 buf[pos/8] &=~Masks[pos%8];
172 }
173
GetBit(const unsigned char * buf,int pos)174 static int GetBit (const unsigned char *buf, int pos)
175 {
176 if (buf[pos/8] & Masks[pos%8])
177 return 1;
178 else
179 return 0;
180 }
181
BuildTree(const float * freq)182 static void BuildTree (const float *freq)
183 {
184 float min1, min2;
185 int i, j, minat1, minat2;
186 huffnode_t *work[256];
187 huffnode_t *tmp;
188
189 HuffMemBase = malloc(512 * sizeof(huffnode_t));
190 if (!HuffMemBase)
191 Sys_Error("Failed allocating memory for HuffTree");
192 memset(HuffMemBase, 0, 512 * sizeof(huffnode_t));
193 tmp = (huffnode_t *) HuffMemBase;
194
195 for (i = 0; i < 256; tmp++, i++)
196 {
197 tmp->val = (unsigned char)i;
198 tmp->freq = freq[i];
199 tmp->zero = NULL;
200 tmp->one = NULL;
201 HuffLookup[i].len = 0;
202 work[i] = tmp;
203 }
204
205 for (i = 0; i < 255; tmp++, i++)
206 {
207 minat1 = -1;
208 minat2 = -1;
209 min1 = 1E30;
210 min2 = 1E30;
211
212 for (j = 0; j < 256; j++)
213 {
214 if (!work[j])
215 continue;
216 if (work[j]->freq < min1)
217 {
218 minat2 = minat1;
219 min2 = min1;
220 minat1 = j;
221 min1 = work[j]->freq;
222 }
223 else if (work[j]->freq < min2)
224 {
225 minat2 = j;
226 min2 = work[j]->freq;
227 }
228 }
229 if (minat1 < 0)
230 Sys_Error("minat1: %d", minat1);
231 if (minat2 < 0)
232 Sys_Error("minat2: %d", minat2);
233 tmp->zero = work[minat2];
234 tmp->one = work[minat1];
235 tmp->freq = work[minat2]->freq + work[minat1]->freq;
236 tmp->val = 0xff;
237 work[minat1] = tmp;
238 work[minat2] = NULL;
239 }
240
241 HuffTree = --tmp; // last incrementation in the loop above wasn't used
242 FindTab (HuffTree, 0, 0);
243
244 #if _DEBUG_HUFFMAN
245 for (i = 0; i < 256; i++)
246 {
247 if (!HuffLookup[i].len && HuffLookup[i].len <= 32)
248 {
249 // HuffPrintf("%d %d %2X\n", HuffLookup[i].len, HuffLookup[i].bits, i);
250 Sys_Error("bad frequency table");
251 }
252 }
253 #endif /* _DEBUG_HUFFMAN */
254 }
255
HuffDecode(const unsigned char * in,unsigned char * out,int inlen,int * outlen,const int maxlen)256 void HuffDecode (const unsigned char *in, unsigned char *out, int inlen, int *outlen, const int maxlen)
257 {
258 int bits, tbits;
259 huffnode_t *tmp;
260
261 --inlen;
262 if (inlen < 0)
263 {
264 *outlen = 0;
265 return;
266 }
267 if (*in == 0xff)
268 {
269 if (inlen > maxlen)
270 memcpy (out, in+1, maxlen);
271 else if (inlen)
272 memcpy (out, in+1, inlen);
273 *outlen = inlen;
274 return;
275 }
276
277 tbits = inlen*8 - *in;
278 bits = 0;
279 *outlen = 0;
280
281 while (bits < tbits)
282 {
283 tmp = HuffTree;
284 do
285 {
286 if ( GetBit(in+1, bits) )
287 tmp = tmp->one;
288 else
289 tmp = tmp->zero;
290 bits++;
291 } while (tmp->zero);
292
293 if ( ++(*outlen) > maxlen )
294 return; // out[maxlen - 1] is written already
295 *out++ = tmp->val;
296 }
297 }
298
HuffEncode(const unsigned char * in,unsigned char * out,int inlen,int * outlen)299 void HuffEncode (const unsigned char *in, unsigned char *out, int inlen, int *outlen)
300 {
301 int i, j, bitat;
302 unsigned int t;
303 #if _DEBUG_HUFFMAN
304 unsigned char *buf;
305 int tlen;
306 #endif /* _DEBUG_HUFFMAN */
307
308 bitat = 0;
309
310 for (i = 0; i < inlen; i++)
311 {
312 t = HuffLookup[in[i]].bits;
313 for (j = 0; j < HuffLookup[in[i]].len; j++)
314 {
315 PutBit (out+1, bitat + HuffLookup[in[i]].len-j-1, t&1);
316 t >>= 1;
317 }
318 bitat += HuffLookup[in[i]].len;
319 }
320
321 *outlen = 1 + (bitat + 7)/8;
322 *out = 8 * ((*outlen)-1) - bitat;
323
324 if (*outlen >= inlen+1)
325 {
326 *out = 0xff;
327 memcpy (out+1, in, inlen);
328 *outlen = inlen+1;
329 }
330
331 #if _DEBUG_HUFFMAN
332 HuffIn += inlen;
333 HuffOut += *outlen;
334 HuffPrintf("in: %d out: %d ratio: %f\n", HuffIn, HuffOut, 1-(float)HuffOut/(float)HuffIn);
335 CalcFreq(in, inlen);
336
337 buf = (unsigned char *) malloc (inlen);
338 HuffDecode (out, buf, *outlen, &tlen, inlen);
339 if (tlen != inlen)
340 Sys_Error("bogus compression");
341 for (i = 0; i < inlen; i++)
342 {
343 if (in[i] != buf[i])
344 Sys_Error("bogus compression");
345 }
346 free (buf);
347 #endif /* _DEBUG_HUFFMAN */
348 }
349
HuffInit(void)350 void HuffInit (void)
351 {
352 #if _DEBUG_HUFFMAN
353 ZeroFreq ();
354 #endif /* _DEBUG_HUFFMAN */
355 BuildTree(HuffFreq);
356 }
357
358