deps/libchdr/huffman.c

   1 // license:BSD-3-Clause\r
   2 // copyright-holders:Aaron Giles\r
   3 /***************************************************************************\r
   4 \r
   5     huffman.c\r
   6 \r
   7     Static Huffman compression and decompression helpers.\r
   8 \r
   9 ****************************************************************************\r
  10 \r
  11     Maximum codelength is officially (alphabetsize - 1). This would be 255 bits\r
  12     (since we use 1 byte values). However, it is also dependent upon the number\r
  13     of samples used, as follows:\r
  14 \r
  15          2 bits -> 3..4 samples\r
  16          3 bits -> 5..7 samples\r
  17          4 bits -> 8..12 samples\r
  18          5 bits -> 13..20 samples\r
  19          6 bits -> 21..33 samples\r
  20          7 bits -> 34..54 samples\r
  21          8 bits -> 55..88 samples\r
  22          9 bits -> 89..143 samples\r
  23         10 bits -> 144..232 samples\r
  24         11 bits -> 233..376 samples\r
  25         12 bits -> 377..609 samples\r
  26         13 bits -> 610..986 samples\r
  27         14 bits -> 987..1596 samples\r
  28         15 bits -> 1597..2583 samples\r
  29         16 bits -> 2584..4180 samples   -> note that a 4k data size guarantees codelength <= 16 bits\r
  30         17 bits -> 4181..6764 samples\r
  31         18 bits -> 6765..10945 samples\r
  32         19 bits -> 10946..17710 samples\r
  33         20 bits -> 17711..28656 samples\r
  34         21 bits -> 28657..46367 samples\r
  35         22 bits -> 46368..75024 samples\r
  36         23 bits -> 75025..121392 samples\r
  37         24 bits -> 121393..196417 samples\r
  38         25 bits -> 196418..317810 samples\r
  39         26 bits -> 317811..514228 samples\r
  40         27 bits -> 514229..832039 samples\r
  41         28 bits -> 832040..1346268 samples\r
  42         29 bits -> 1346269..2178308 samples\r
  43         30 bits -> 2178309..3524577 samples\r
  44         31 bits -> 3524578..5702886 samples\r
  45         32 bits -> 5702887..9227464 samples\r
  46 \r
  47     Looking at it differently, here is where powers of 2 fall into these buckets:\r
  48 \r
  49           256 samples -> 11 bits max\r
  50           512 samples -> 12 bits max\r
  51            1k samples -> 14 bits max\r
  52            2k samples -> 15 bits max\r
  53            4k samples -> 16 bits max\r
  54            8k samples -> 18 bits max\r
  55           16k samples -> 19 bits max\r
  56           32k samples -> 21 bits max\r
  57           64k samples -> 22 bits max\r
  58          128k samples -> 24 bits max\r
  59          256k samples -> 25 bits max\r
  60          512k samples -> 27 bits max\r
  61            1M samples -> 28 bits max\r
  62            2M samples -> 29 bits max\r
  63            4M samples -> 31 bits max\r
  64            8M samples -> 32 bits max\r
  65 \r
  66 ****************************************************************************\r
  67 \r
  68     Delta-RLE encoding works as follows:\r
  69 \r
  70     Starting value is assumed to be 0. All data is encoded as a delta\r
  71     from the previous value, such that final[i] = final[i - 1] + delta.\r
  72     Long runs of 0s are RLE-encoded as follows:\r
  73 \r
  74         0x100 = repeat count of 8\r
  75         0x101 = repeat count of 9\r
  76         0x102 = repeat count of 10\r
  77         0x103 = repeat count of 11\r
  78         0x104 = repeat count of 12\r
  79         0x105 = repeat count of 13\r
  80         0x106 = repeat count of 14\r
  81         0x107 = repeat count of 15\r
  82         0x108 = repeat count of 16\r
  83         0x109 = repeat count of 32\r
  84         0x10a = repeat count of 64\r
  85         0x10b = repeat count of 128\r
  86         0x10c = repeat count of 256\r
  87         0x10d = repeat count of 512\r
  88         0x10e = repeat count of 1024\r
  89         0x10f = repeat count of 2048\r
  90 \r
  91     Note that repeat counts are reset at the end of a row, so if a 0 run\r
  92     extends to the end of a row, a large repeat count may be used.\r
  93 \r
  94     The reason for starting the run counts at 8 is that 0 is expected to\r
  95     be the most common symbol, and is typically encoded in 1 or 2 bits.\r
  96 \r
  97 ***************************************************************************/\r
  98 \r
  99 #include <stdlib.h>\r
 100 #include <assert.h>\r
 101 #include <stdio.h>\r
 102 #include <string.h>\r
 103 \r
 104 #include "huffman.h"\r
 105 \r
 106 #define MAX(x,y) ((x) > (y) ? (x) : (y))\r
 107 \r
 108 //**************************************************************************\r
 109 //  MACROS\r
 110 //**************************************************************************\r
 111 \r
 112 #define MAKE_LOOKUP(code,bits)  (((code) << 5) | ((bits) & 0x1f))\r
 113 \r
 114 \r
 115 //**************************************************************************\r
 116 //  IMPLEMENTATION\r
 117 //**************************************************************************\r
 118 \r
 119 //-------------------------------------------------\r
 120 //  huffman_context_base - create an encoding/\r
 121 //  decoding context\r
 122 //-------------------------------------------------\r
 123 \r
 124 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits)\r
 125 {\r
 126    struct huffman_decoder* decoder;\r
 127 \r
 128         /* limit to 24 bits */\r
 129         if (maxbits > 24)\r
 130                 return NULL;\r
 131 \r
 132         decoder = (struct huffman_decoder*)malloc(sizeof(struct huffman_decoder));\r
 133         decoder->numcodes = numcodes;\r
 134         decoder->maxbits = maxbits;\r
 135         decoder->lookup = (lookup_value*)malloc(sizeof(lookup_value) * (1 << maxbits));\r
 136         decoder->huffnode = (struct node_t*)malloc(sizeof(struct node_t) * numcodes);\r
 137         decoder->datahisto = NULL;\r
 138         decoder->prevdata = 0;\r
 139         decoder->rleremaining = 0;\r
 140         return decoder;\r
 141 }\r
 142 \r
 143 //-------------------------------------------------\r
 144 //  decode_one - decode a single code from the\r
 145 //  huffman stream\r
 146 //-------------------------------------------------\r
 147 \r
 148 uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
 149 {\r
 150         /* peek ahead to get maxbits worth of data */\r
 151         uint32_t bits = bitstream_peek(bitbuf, decoder->maxbits);\r
 152 \r
 153         /* look it up, then remove the actual number of bits for this code */\r
 154         lookup_value lookup = decoder->lookup[bits];\r
 155         bitstream_remove(bitbuf, lookup & 0x1f);\r
 156 \r
 157         /* return the value */\r
 158         return lookup >> 5;\r
 159 }\r
 160 \r
 161 //-------------------------------------------------\r
 162 //  import_tree_rle - import an RLE-encoded\r
 163 //  huffman tree from a source data stream\r
 164 //-------------------------------------------------\r
 165 \r
 166 enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
 167 {\r
 168    enum huffman_error error;\r
 169         int curnode;\r
 170         // bits per entry depends on the maxbits\r
 171         int numbits;\r
 172         if (decoder->maxbits >= 16)\r
 173                 numbits = 5;\r
 174         else if (decoder->maxbits >= 8)\r
 175                 numbits = 4;\r
 176         else\r
 177                 numbits = 3;\r
 178 \r
 179         // loop until we read all the nodes\r
 180         for (curnode = 0; curnode < decoder->numcodes; )\r
 181         {\r
 182                 // a non-one value is just raw\r
 183                 int nodebits = bitstream_read(bitbuf, numbits);\r
 184                 if (nodebits != 1)\r
 185                         decoder->huffnode[curnode++].numbits = nodebits;\r
 186 \r
 187                 // a one value is an escape code\r
 188                 else\r
 189                 {\r
 190                         // a double 1 is just a single 1\r
 191                         nodebits = bitstream_read(bitbuf, numbits);\r
 192                         if (nodebits == 1)\r
 193                                 decoder->huffnode[curnode++].numbits = nodebits;\r
 194 \r
 195                         // otherwise, we need one for value for the repeat count\r
 196                         else\r
 197                         {\r
 198                                 int repcount = bitstream_read(bitbuf, numbits) + 3;\r
 199                                 while (repcount--)\r
 200                                         decoder->huffnode[curnode++].numbits = nodebits;\r
 201                         }\r
 202                 }\r
 203         }\r
 204 \r
 205         // make sure we ended up with the right number\r
 206         if (curnode != decoder->numcodes)\r
 207                 return HUFFERR_INVALID_DATA;\r
 208 \r
 209         // assign canonical codes for all nodes based on their code lengths\r
 210         error = huffman_assign_canonical_codes(decoder);\r
 211         if (error != HUFFERR_NONE)\r
 212                 return error;\r
 213 \r
 214         // build the lookup table\r
 215         huffman_build_lookup_table(decoder);\r
 216 \r
 217         // determine final input length and report errors\r
 218         return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r
 219 }\r
 220 \r
 221 \r
 222 //-------------------------------------------------\r
 223 //  import_tree_huffman - import a huffman-encoded\r
 224 //  huffman tree from a source data stream\r
 225 //-------------------------------------------------\r
 226 \r
 227 enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf)\r
 228 {\r
 229    int index;\r
 230    int start;\r
 231         int count = 0;\r
 232         uint8_t rlefullbits = 0;\r
 233         int last = 0;\r
 234         int curcode;\r
 235    enum huffman_error error;\r
 236    uint32_t temp;\r
 237         // start by parsing the lengths for the small tree\r
 238         struct huffman_decoder* smallhuff = create_huffman_decoder(24, 6);\r
 239 \r
 240         smallhuff->huffnode[0].numbits = bitstream_read(bitbuf, 3);\r
 241         start = bitstream_read(bitbuf, 3) + 1;\r
 242 \r
 243         for (index = 1; index < 24; index++)\r
 244         {\r
 245                 if (index < start || count == 7)\r
 246                         smallhuff->huffnode[index].numbits = 0;\r
 247                 else\r
 248                 {\r
 249                         count = bitstream_read(bitbuf, 3);\r
 250                         smallhuff->huffnode[index].numbits = (count == 7) ? 0 : count;\r
 251                 }\r
 252         }\r
 253 \r
 254         // then regenerate the tree\r
 255         error = huffman_assign_canonical_codes(smallhuff);\r
 256         if (error != HUFFERR_NONE)\r
 257                 return error;\r
 258         huffman_build_lookup_table(smallhuff);\r
 259 \r
 260         // determine the maximum length of an RLE count\r
 261         temp = decoder->numcodes - 9;\r
 262         while (temp != 0)\r
 263                 temp >>= 1, rlefullbits++;\r
 264 \r
 265         // now process the rest of the data\r
 266         for (curcode = 0; curcode < decoder->numcodes; )\r
 267         {\r
 268                 int value = huffman_decode_one(smallhuff, bitbuf);\r
 269                 if (value != 0)\r
 270                         decoder->huffnode[curcode++].numbits = last = value - 1;\r
 271                 else\r
 272                 {\r
 273                         int count = bitstream_read(bitbuf, 3) + 2;\r
 274                         if (count == 7+2)\r
 275                                 count += bitstream_read(bitbuf, rlefullbits);\r
 276                         for ( ; count != 0 && curcode < decoder->numcodes; count--)\r
 277                                 decoder->huffnode[curcode++].numbits = last;\r
 278                 }\r
 279         }\r
 280 \r
 281         // make sure we ended up with the right number\r
 282         if (curcode != decoder->numcodes)\r
 283                 return HUFFERR_INVALID_DATA;\r
 284 \r
 285         // assign canonical codes for all nodes based on their code lengths\r
 286         error = huffman_assign_canonical_codes(decoder);\r
 287         if (error != HUFFERR_NONE)\r
 288                 return error;\r
 289 \r
 290         // build the lookup table\r
 291         huffman_build_lookup_table(decoder);\r
 292 \r
 293         // determine final input length and report errors\r
 294         return bitstream_overflow(bitbuf) ? HUFFERR_INPUT_BUFFER_TOO_SMALL : HUFFERR_NONE;\r
 295 }\r
 296 \r
 297 \r
 298 //-------------------------------------------------\r
 299 //  compute_tree_from_histo - common backend for\r
 300 //  computing a tree based on the data histogram\r
 301 //-------------------------------------------------\r
 302 \r
 303 enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder)\r
 304 {\r
 305    int i;\r
 306    uint32_t upperweight;\r
 307         uint32_t lowerweight = 0;\r
 308         // compute the number of data items in the histogram\r
 309         uint32_t sdatacount = 0;\r
 310         for (i = 0; i < decoder->numcodes; i++)\r
 311                 sdatacount += decoder->datahisto[i];\r
 312 \r
 313         // binary search to achieve the optimum encoding\r
 314         upperweight = sdatacount * 2;\r
 315         while (1)\r
 316         {\r
 317                 // build a tree using the current weight\r
 318                 uint32_t curweight = (upperweight + lowerweight) / 2;\r
 319                 int curmaxbits = huffman_build_tree(decoder, sdatacount, curweight);\r
 320 \r
 321                 // apply binary search here\r
 322                 if (curmaxbits <= decoder->maxbits)\r
 323                 {\r
 324                         lowerweight = curweight;\r
 325 \r
 326                         // early out if it worked with the raw weights, or if we're done searching\r
 327                         if (curweight == sdatacount || (upperweight - lowerweight) <= 1)\r
 328                                 break;\r
 329                 }\r
 330                 else\r
 331                         upperweight = curweight;\r
 332         }\r
 333 \r
 334         // assign canonical codes for all nodes based on their code lengths\r
 335         return huffman_assign_canonical_codes(decoder);\r
 336 }\r
 337 \r
 338 \r
 339 \r
 340 //**************************************************************************\r
 341 //  INTERNAL FUNCTIONS\r
 342 //**************************************************************************\r
 343 \r
 344 //-------------------------------------------------\r
 345 //  tree_node_compare - compare two tree nodes\r
 346 //  by weight\r
 347 //-------------------------------------------------\r
 348 \r
 349 static int huffman_tree_node_compare(const void *item1, const void *item2)\r
 350 {\r
 351         const struct node_t *node1 = *(const struct node_t **)item1;\r
 352         const struct node_t *node2 = *(const struct node_t **)item2;\r
 353         if (node2->weight != node1->weight)\r
 354                 return node2->weight - node1->weight;\r
 355         if (node2->bits - node1->bits == 0)\r
 356                 fprintf(stderr, "identical node sort keys, should not happen!\n");\r
 357         return (int)node1->bits - (int)node2->bits;\r
 358 }\r
 359 \r
 360 \r
 361 //-------------------------------------------------\r
 362 //  build_tree - build a huffman tree based on the\r
 363 //  data distribution\r
 364 //-------------------------------------------------\r
 365 \r
 366 int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight)\r
 367 {\r
 368    int curcode;\r
 369    int nextalloc;\r
 370         int maxbits = 0;\r
 371         // make a list of all non-zero nodes\r
 372         struct node_t** list = (struct node_t**)malloc(sizeof(struct node_t*) * decoder->numcodes * 2);\r
 373         int listitems = 0;\r
 374         memset(decoder->huffnode, 0, decoder->numcodes * sizeof(decoder->huffnode[0]));\r
 375         for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
 376                 if (decoder->datahisto[curcode] != 0)\r
 377                 {\r
 378                         list[listitems++] = &decoder->huffnode[curcode];\r
 379                         decoder->huffnode[curcode].count = decoder->datahisto[curcode];\r
 380                         decoder->huffnode[curcode].bits = curcode;\r
 381 \r
 382                         // scale the weight by the current effective length, ensuring we don't go to 0\r
 383                         decoder->huffnode[curcode].weight = ((uint64_t)decoder->datahisto[curcode]) * ((uint64_t)totalweight) / ((uint64_t)totaldata);\r
 384                         if (decoder->huffnode[curcode].weight == 0)\r
 385                                 decoder->huffnode[curcode].weight = 1;\r
 386                 }\r
 387 /*\r
 388         fprintf(stderr, "Pre-sort:\n");\r
 389         for (int i = 0; i < listitems; i++) {\r
 390             fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r
 391         }\r
 392 */\r
 393         // sort the list by weight, largest weight first\r
 394         qsort(&list[0], listitems, sizeof(list[0]), huffman_tree_node_compare);\r
 395 /*\r
 396         fprintf(stderr, "Post-sort:\n");\r
 397         for (int i = 0; i < listitems; i++) {\r
 398             fprintf(stderr, "weight: %d code: %d\n", list[i]->m_weight, list[i]->m_bits);\r
 399         }\r
 400         fprintf(stderr, "===================\n");\r
 401 */\r
 402         // now build the tree\r
 403         nextalloc = decoder->numcodes;\r
 404 \r
 405         while (listitems > 1)\r
 406         {\r
 407                 int curitem;\r
 408                 // remove lowest two items\r
 409                 struct node_t* node1 = &(*list[--listitems]);\r
 410                 struct node_t* node0 = &(*list[--listitems]);\r
 411 \r
 412                 // create new node\r
 413                 struct node_t* newnode = &decoder->huffnode[nextalloc++];\r
 414                 newnode->parent = NULL;\r
 415                 node0->parent = node1->parent = newnode;\r
 416                 newnode->weight = node0->weight + node1->weight;\r
 417 \r
 418                 // insert into list at appropriate location\r
 419                 for (curitem = 0; curitem < listitems; curitem++)\r
 420                         if (newnode->weight > list[curitem]->weight)\r
 421                         {\r
 422                                 memmove(&list[curitem+1], &list[curitem], (listitems - curitem) * sizeof(list[0]));\r
 423                                 break;\r
 424                         }\r
 425                 list[curitem] = newnode;\r
 426                 listitems++;\r
 427         }\r
 428 \r
 429         // compute the number of bits in each code, and fill in another histogram\r
 430         for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
 431         {\r
 432                 struct node_t* node = &decoder->huffnode[curcode];\r
 433                 node->numbits = 0;\r
 434                 node->bits = 0;\r
 435 \r
 436                 // if we have a non-zero weight, compute the number of bits\r
 437                 if (node->weight > 0)\r
 438                 {\r
 439          struct node_t *curnode;\r
 440                         // determine the number of bits for this node\r
 441                         for (curnode = node; curnode->parent != NULL; curnode = curnode->parent)\r
 442                                 node->numbits++;\r
 443                         if (node->numbits == 0)\r
 444                                 node->numbits = 1;\r
 445 \r
 446                         // keep track of the max\r
 447                         maxbits = MAX(maxbits, ((int)node->numbits));\r
 448                 }\r
 449         }\r
 450         return maxbits;\r
 451 }\r
 452 \r
 453 \r
 454 //-------------------------------------------------\r
 455 //  assign_canonical_codes - assign canonical codes\r
 456 //  to all the nodes based on the number of bits\r
 457 //  in each\r
 458 //-------------------------------------------------\r
 459 \r
 460 enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder)\r
 461 {\r
 462    int curcode, codelen;\r
 463         uint32_t curstart = 0;\r
 464 \r
 465         // build up a histogram of bit lengths\r
 466         uint32_t bithisto[33] = { 0 };\r
 467         for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
 468         {\r
 469                 struct node_t* node = &decoder->huffnode[curcode];\r
 470                 if (node->numbits > decoder->maxbits)\r
 471                         return HUFFERR_INTERNAL_INCONSISTENCY;\r
 472                 if (node->numbits <= 32)\r
 473                         bithisto[node->numbits]++;\r
 474         }\r
 475 \r
 476         // for each code length, determine the starting code number\r
 477         for (codelen = 32; codelen > 0; codelen--)\r
 478         {\r
 479                 uint32_t nextstart = (curstart + bithisto[codelen]) >> 1;\r
 480                 if (codelen != 1 && nextstart * 2 != (curstart + bithisto[codelen]))\r
 481                         return HUFFERR_INTERNAL_INCONSISTENCY;\r
 482                 bithisto[codelen] = curstart;\r
 483                 curstart = nextstart;\r
 484         }\r
 485 \r
 486         // now assign canonical codes\r
 487         for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
 488         {\r
 489                 struct node_t* node = &decoder->huffnode[curcode];\r
 490                 if (node->numbits > 0)\r
 491                         node->bits = bithisto[node->numbits]++;\r
 492         }\r
 493         return HUFFERR_NONE;\r
 494 }\r
 495 \r
 496 \r
 497 //-------------------------------------------------\r
 498 //  build_lookup_table - build a lookup table for\r
 499 //  fast decoding\r
 500 //-------------------------------------------------\r
 501 \r
 502 void huffman_build_lookup_table(struct huffman_decoder* decoder)\r
 503 {\r
 504    int curcode;\r
 505         // iterate over all codes\r
 506         for (curcode = 0; curcode < decoder->numcodes; curcode++)\r
 507         {\r
 508                 // process all nodes which have non-zero bits\r
 509                 struct node_t* node = &decoder->huffnode[curcode];\r
 510                 if (node->numbits > 0)\r
 511                 {\r
 512          int shift;\r
 513          lookup_value *dest;\r
 514          lookup_value *destend;\r
 515 \r
 516                         // set up the entry\r
 517                         lookup_value value = MAKE_LOOKUP(curcode, node->numbits);\r
 518 \r
 519                         // fill all matching entries\r
 520                         shift   = decoder->maxbits - node->numbits;\r
 521                         dest    = &decoder->lookup[node->bits << shift];\r
 522                         destend = &decoder->lookup[((node->bits + 1) << shift) - 1];\r
 523 \r
 524                         while (dest <= destend)\r
 525                                 *dest++ = value;\r
 526                 }\r
 527         }\r
 528 }\r