1 /**
2 libsmacker - A C library for decoding .smk Smacker Video files
3 Copyright (C) 2012-2017 Greg Kennedy
4
5 See smacker.h for more information.
6
7 smk_hufftree.c
8 Implementation of Smacker Huffman coding trees.
9 */
10
11 #include "smk_hufftree.h"
12
13 /* malloc and friends */
14 #include "smk_malloc.h"
15
16 /**
17 8-bit Tree node structure.
18 If b0 is non-null, this is a branch, and b1 from the union should be used.
19 If b0 is null, this is a leaf, and val / escape code from union should be used.
20 */
21 struct smk_huff8_t
22 {
23 struct smk_huff8_t* b0;
24 union
25 {
26 struct smk_huff8_t* b1;
27 struct
28 {
29 unsigned short value;
30 unsigned char escapecode;
31 } leaf;
32 } u;
33 };
34
35 /**
36 16-bit Tree root struct: holds a huff8_t structure,
37 as well as a cache of three 16-bit values.
38 */
39 struct smk_huff16_t
40 {
41 struct smk_huff8_t* t;
42 unsigned short cache[3];
43 };
44
45 /*********************** 8-BIT HUFF-TREE FUNCTIONS ***********************/
46 /** safe build with built-in error jump */
47 #define smk_huff8_build_rec(bs,p) \
48 { \
49 p = _smk_huff8_build_rec(bs); \
50 if (!p) \
51 { \
52 fprintf(stderr, "libsmacker::smk_huff8_build_rec(" #bs ", " #p ") - ERROR (file: %s, line: %lu)\n", __FILE__, (unsigned long)__LINE__); \
53 goto error; \
54 } \
55 }
56 /** Recursive tree-building function. */
_smk_huff8_build_rec(struct smk_bit_t * bs)57 static struct smk_huff8_t* _smk_huff8_build_rec(struct smk_bit_t* bs)
58 {
59 struct smk_huff8_t* ret = NULL;
60 char bit;
61
62 /* sanity check - removed: bs cannot be null, because it was checked at smk_huff8_build below */
63 /* smk_assert(bs); */
64
65 /* Read the bit */
66 smk_bs_read_1(bs, bit);
67
68 /* Malloc a structure. */
69 smk_malloc(ret, sizeof(struct smk_huff8_t));
70
71 if (bit)
72 {
73 /* Bit set: this forms a Branch node. */
74 /* Recursively attempt to build the Left branch. */
75 smk_huff8_build_rec(bs, ret->b0);
76
77 /* Everything is still OK: attempt to build the Right branch. */
78 smk_huff8_build_rec(bs, ret->u.b1);
79
80 /* return branch pointer here */
81 return ret;
82 }
83
84 /* Bit unset signifies a Leaf node. */
85 /* Attempt to read value */
86 smk_bs_read_8(bs, ret->u.leaf.value);
87
88 /* smk_malloc sets entries to 0 by default */
89 /* ret->b0 = NULL; */
90 ret->u.leaf.escapecode = 0xFF;
91
92 return ret;
93
94 error:
95 /* In case of error, undo the subtree we were building, and return NULL. */
96 smk_huff8_free(ret);
97 return NULL;
98 }
99
100 /* Look up an 8-bit value from a basic huff tree.
101 Return -1 on error. */
_smk_huff8_lookup(struct smk_bit_t * bs,const struct smk_huff8_t * t)102 short _smk_huff8_lookup(struct smk_bit_t* bs, const struct smk_huff8_t* t)
103 {
104 char bit;
105
106 /* sanity check */
107 smk_assert(bs);
108 smk_assert(t);
109
110 if (!t->b0)
111 {
112 /* Reached a Leaf node. Return its value. */
113 return t->u.leaf.value;
114 }
115
116 /* Read the next bit from bitstream to determine path */
117 smk_bs_read_1(bs, bit);
118
119 if (bit)
120 {
121 /* get_bit returned Set, follow Right branch. */
122 return _smk_huff8_lookup(bs, t->u.b1);
123 }
124
125 /* follow Left branch */
126 return _smk_huff8_lookup(bs, t->b0);
127
128 error:
129 return -1;
130 }
131
132 /**
133 Entry point for huff8 build. Basically just checks the start/end tags
134 and calls smk_huff8_build_rec recursive function.
135 */
_smk_huff8_build(struct smk_bit_t * bs)136 struct smk_huff8_t* _smk_huff8_build(struct smk_bit_t* bs)
137 {
138 struct smk_huff8_t* ret = NULL;
139 char bit;
140
141 /* sanity check */
142 smk_assert(bs);
143
144 /* Smacker huff trees begin with a set-bit. */
145 smk_bs_read_1(bs, bit);
146
147 if (!bit)
148 {
149 /* Got a bit, but it was not 1. In theory, there could be a smk file
150 without this particular tree. */
151 fputs("libsmacker::_smk_huff8_build(bs) - Warning: initial get_bit returned 0\n", stderr);
152 goto error;
153 }
154
155 /* Begin parsing the tree data. */
156 smk_huff8_build_rec(bs, ret);
157
158 /* huff trees end with an unset-bit */
159 smk_bs_read_1(bs, bit);
160
161 if (bit)
162 {
163 fputs("libsmacker::_smk_huff8_build(bs) - ERROR: final get_bit returned 1\n", stderr);
164 goto error;
165 }
166
167 return ret;
168
169 error:
170 smk_huff8_free(ret);
171 return NULL;
172 }
173
174 /* function to recursively delete a huffman tree */
smk_huff8_free(struct smk_huff8_t * t)175 void smk_huff8_free(struct smk_huff8_t* t)
176 {
177 /* Sanity check: do not double-free */
178 smk_assert(t);
179
180 /* If this is not a leaf node, free child trees first */
181 if (t->b0)
182 {
183 smk_huff8_free(t->b0);
184 smk_huff8_free(t->u.b1);
185 }
186
187 /* Safe-delete tree node. */
188 smk_free(t);
189
190 error: ;
191 }
192
193 /*********************** 16-BIT HUFF-TREE FUNCTIONS ***********************/
194 /* safe bigtree build with built-in error jump */
195 #define smk_huff16_build_rec(bs,cache,low8,hi8,p) \
196 { \
197 p = _smk_huff16_build_rec(bs, cache, low8, hi8); \
198 if (!p) \
199 { \
200 fprintf(stderr, "libsmacker::smk_huff16_build_rec(" #bs ", " #cache ", " #low8 ", " #hi8 ", " #p ") - ERROR (file: %s, line: %lu)\n", __FILE__, (unsigned long)__LINE__); \
201 goto error; \
202 } \
203 }
204 /* Recursively builds a Big tree. */
_smk_huff16_build_rec(struct smk_bit_t * bs,const unsigned short cache[3],const struct smk_huff8_t * low8,const struct smk_huff8_t * hi8)205 static struct smk_huff8_t* _smk_huff16_build_rec(struct smk_bit_t* bs, const unsigned short cache[3], const struct smk_huff8_t* low8, const struct smk_huff8_t* hi8)
206 {
207 struct smk_huff8_t* ret = NULL;
208
209 char bit;
210 short lowval;
211
212 /* sanity check - removed: these cannot be null, because they were checked at smk_huff16_build below */
213 /* smk_assert(bs);
214 smk_assert(cache);
215 smk_assert(low8);
216 smk_assert(hi8); */
217
218 /* Get the first bit */
219 smk_bs_read_1(bs, bit);
220
221 /* Malloc a structure. */
222 smk_malloc(ret, sizeof(struct smk_huff8_t));
223
224 if (bit)
225 {
226 /* Recursively attempt to build the Left branch. */
227 smk_huff16_build_rec(bs, cache, low8, hi8, ret->b0);
228
229 /* Recursively attempt to build the Left branch. */
230 smk_huff16_build_rec(bs, cache, low8, hi8, ret->u.b1);
231
232 /* return branch pointer here */
233 return ret;
234 }
235
236 /* Bit unset signifies a Leaf node. */
237 smk_huff8_lookup(bs, low8, lowval);
238 smk_huff8_lookup(bs, hi8, ret->u.leaf.value);
239
240 /* Looks OK: we got low and hi values. Return a new LEAF */
241 /* ret->b0 = NULL; */
242 ret->u.leaf.value = lowval | (ret->u.leaf.value << 8);
243
244 /* Last: when building the tree, some Values may correspond to cache positions.
245 Identify these values and set the Escape code byte accordingly. */
246 if (ret->u.leaf.value == cache[0])
247 {
248 ret->u.leaf.escapecode = 0;
249 }
250 else if (ret->u.leaf.value == cache[1])
251 {
252 ret->u.leaf.escapecode = 1;
253 }
254 else if (ret->u.leaf.value == cache[2])
255 {
256 ret->u.leaf.escapecode = 2;
257 }
258 else
259 {
260 ret->u.leaf.escapecode = 0xFF;
261 }
262
263 return ret;
264
265 error:
266 smk_huff8_free(ret);
267 return NULL;
268 }
269
270 /* Entry point for building a big 16-bit tree. */
_smk_huff16_build(struct smk_bit_t * bs)271 struct smk_huff16_t* _smk_huff16_build(struct smk_bit_t* bs)
272 {
273 struct smk_huff16_t* big = NULL;
274
275 struct smk_huff8_t* low8 = NULL;
276 struct smk_huff8_t* hi8 = NULL;
277
278 short lowval;
279
280 char bit;
281 unsigned char i;
282
283 /* sanity check */
284 smk_assert(bs);
285
286 /* Smacker huff trees begin with a set-bit. */
287 smk_bs_read_1(bs, bit);
288
289 if (!bit)
290 {
291 smk_malloc(big, sizeof(struct smk_huff16_t));
292 big->t = NULL;
293 return big;
294 }
295
296 /* build low-8-bits tree */
297 smk_huff8_build(bs, low8);
298 /* build hi-8-bits tree */
299 smk_huff8_build(bs, hi8);
300
301 /* Everything looks OK so far. Time to malloc structure. */
302 smk_malloc(big, sizeof(struct smk_huff16_t));
303
304 /* Init the escape code cache. */
305 for (i = 0; i < 3; i ++)
306 {
307 smk_bs_read_8(bs, lowval);
308 smk_bs_read_8(bs, big->cache[i]);
309 big->cache[i] = lowval | (big->cache[i] << 8);
310 }
311
312 /* Finally, call recursive function to retrieve the Bigtree. */
313 smk_huff16_build_rec(bs, big->cache, low8, hi8, big->t);
314
315 /* Check final end tag. */
316 smk_bs_read_1(bs, bit);
317
318 /* Done with 8-bit hufftrees, free them. */
319 smk_huff8_free(hi8);
320 smk_huff8_free(low8);
321
322 if (bit)
323 {
324 fputs("libsmacker::smk_huff16_build(bs) - ERROR: final get_bit returned 1\n", stderr);
325 smk_huff16_free(big);
326 return NULL;
327 }
328
329 return big;
330
331 error:
332 smk_huff16_free(big);
333 smk_huff8_free(hi8);
334 smk_huff8_free(low8);
335 return NULL;
336 }
337
_smk_huff16_lookup_rec(struct smk_bit_t * bs,unsigned short cache[3],const struct smk_huff8_t * t)338 static int _smk_huff16_lookup_rec(struct smk_bit_t* bs, unsigned short cache[3], const struct smk_huff8_t* t)
339 {
340 unsigned short val;
341 char bit;
342
343 /* sanity check */
344 /* smk_assert(bs);
345 smk_assert(cache);
346 smk_assert(t); */
347
348 /* Reached a Leaf node */
349 if (!t->b0)
350 {
351 if (t->u.leaf.escapecode != 0xFF)
352 {
353 /* Found escape code. Retrieve value from Cache. */
354 val = cache[t->u.leaf.escapecode];
355 }
356 else
357 {
358 /* Use value directly. */
359 val = t->u.leaf.value;
360 }
361
362 if (cache[0] != val)
363 {
364 /* Update the cache, by moving val to the front of the queue,
365 if it isn't already there. */
366 cache[2] = cache[1];
367 cache[1] = cache[0];
368 cache[0] = val;
369 }
370
371 return val;
372 }
373
374 /* Read the next bit from bitstream to determine path */
375 smk_bs_read_1(bs, bit);
376
377 if (bit)
378 {
379 /* get_bit returned Set, follow Right branch. */
380 return _smk_huff16_lookup_rec(bs, cache, t->u.b1);
381 }
382
383 return _smk_huff16_lookup_rec(bs, cache, t->b0);
384
385 error:
386 return -1;
387 }
388
389 /* Convenience call-out for recursive bigtree lookup function */
_smk_huff16_lookup(struct smk_bit_t * bs,struct smk_huff16_t * big)390 long _smk_huff16_lookup(struct smk_bit_t* bs, struct smk_huff16_t* big)
391 {
392 /* sanity check */
393 smk_assert(bs);
394 smk_assert(big);
395
396 return _smk_huff16_lookup_rec(bs, big->cache, big->t);
397
398 error:
399 return -1;
400 }
401
402 /* Resets a Big hufftree cache */
smk_huff16_reset(struct smk_huff16_t * big)403 void smk_huff16_reset(struct smk_huff16_t* big)
404 {
405 /* sanity check */
406 smk_assert(big);
407
408 big->cache[0] = 0;
409 big->cache[1] = 0;
410 big->cache[2] = 0;
411
412 error: ;
413 }
414
415 /* delete a (big) huffman tree */
smk_huff16_free(struct smk_huff16_t * big)416 void smk_huff16_free(struct smk_huff16_t* big)
417 {
418 /* Sanity check: do not double-free */
419 smk_assert(big);
420
421 /* free the subtree */
422 if (big->t)
423 smk_huff8_free(big->t);
424
425 /* free the bigtree */
426 smk_free(big);
427
428 error: ;
429 }
430