Subversion Repositories Games.Carmageddon

Rev

Blame | Last modification | View Log | Download | RSS feed

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