git.sesse.net Git - fjl/blob - dehuff.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <assert.h>
   4
   5 #include "bytesource.h"
   6 #include "dehuff.h"
   7 #include "input.h"
   8
   9 void read_huffman_tables(huffman_tables_t* dst, input_func_t* input_func, void* userdata)
  10 {
  11         size_t len = read_uint16(input_func, userdata);
  12         assert(len > 2);
  13         len -= 2;
  14
  15         // TODO: check for NULL return
  16         uint8_t* buf = (uint8_t*)malloc(len);
  17         uint8_t* inptr = buf;
  18         reliable_read(input_func, userdata, buf, len);
  19
  20         while (len > 0) {
  21                 unsigned char tc_th = *inptr++;
  22                 --len;
  23                 unsigned table_class = tc_th >> 4;
  24                 unsigned table_dest = tc_th & 0x0f;
  25
  26                 if (table_class != 0 && table_class != 1) {
  27                         fprintf(stderr, "Error: Unknown table class %u\n", table_class);
  28                         exit(1);
  29                 }
  30                 if (table_dest >= 4) {
  31                         fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
  32                         exit(1);
  33                 }
  34
  35                 struct huffman_table* tbl = &((*dst)[table_class][table_dest]);
  36                 if (len < 16) {
  37                         fprintf(stderr, "Short read for num_codes\n");
  38                         exit(1);
  39                 }
  40                 for (unsigned i = 0; i < 16; ++i) {
  41                         tbl->num_codes[i] = *inptr++;
  42                         --len;
  43                 }
  44                 for (unsigned i = 0, k = 0; i < 16; ++i) {
  45                         if (len < tbl->num_codes[i]) {
  46                                 fprintf(stderr, "Short read for codes\n");
  47                                 exit(1);
  48                         }
  49                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
  50                                 tbl->codes[k] = *inptr++;
  51                                 --len;
  52                         }
  53                 }
  54
  55                 // Generate derived tables
  56
  57                 // generate_size_table (figure C.1)
  58                 {
  59                         unsigned k = 0;
  60                         for (unsigned i = 0; i < 16; ++i) {
  61                                 for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
  62                                         tbl->huffsize[k] = i + 1;
  63                                 }
  64                         }
  65                         tbl->huffsize[k] = 0;
  66                 }
  67
  68                 // generate_code_table (figure C.2)
  69                 unsigned si = tbl->huffsize[0];
  70                 for (unsigned i = 0, j = 0;; ) {
  71                         tbl->huffcode[i++] = j++;
  72                         if (tbl->huffsize[i] == si) {
  73                                 continue;
  74                         }
  75                         if (tbl->huffsize[i] == 0) {
  76                                 break;
  77                         }
  78
  79                         do {
  80                                 j <<= 1;
  81                         } while (++si != tbl->huffsize[i]);
  82                 }
  83
  84                 // decoder_tables (figure F.15)
  85                 for (unsigned i = 0, j = 0; i < 16; ++i) {
  86                         if (tbl->num_codes[i] == 0) {
  87                                 tbl->maxcode[i] = -1;
  88                                 continue;
  89                         }
  90
  91                         tbl->valptr[i] = j;
  92                         tbl->mincode[i] = tbl->huffcode[j];
  93                         j += tbl->num_codes[i];
  94                         tbl->maxcode[i] = tbl->huffcode[j - 1];
  95                 }
  96
  97                 // Generate the lookup tables
  98                 for (unsigned i = 0; i < DEHUF_TABLE_SIZE; ++i) {
  99                         tbl->lookup_table_codes[i] = DEHUF_SLOW_PATH;
 100                         tbl->lookup_table_length[i] = DEHUF_SLOW_PATH;
 101                 }
 102
 103                 unsigned k = 0;
 104                 for (unsigned i = 0; i < 16; ++i) {
 105                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
 106                                 const unsigned code = tbl->huffcode[k];
 107                                 const unsigned length = tbl->huffsize[k];
 108                                 if (length > DEHUF_TABLE_BITS) {
 109                                         continue;
 110                                 }
 111                                 const unsigned prefix_min = code << (DEHUF_TABLE_BITS - length);
 112                                 const unsigned prefix_max = ((code + 1) << (DEHUF_TABLE_BITS - length));
 113
 114                                 for (unsigned elem = prefix_min; elem < prefix_max; ++elem) {
 115                                         assert(tbl->lookup_table_codes[elem] == DEHUF_SLOW_PATH);
 116                                         assert(tbl->lookup_table_length[elem] == DEHUF_SLOW_PATH);
 117                                         tbl->lookup_table_codes[elem] = tbl->codes[k];
 118                                         tbl->lookup_table_length[elem] = length;
 119                                 }
 120                         }
 121                 }
 122         }
 123
 124         free(buf);
 125 }
 126
 127 unsigned read_huffman_symbol_slow_path(const struct huffman_table* table,
 128                                        struct bit_source* source) {
 129         possibly_refill(source, 1);
 130         unsigned code = read_bits(source, 1);
 131         int i = 0;
 132
 133         while (table->maxcode[i] == -1 || code > (unsigned)table->maxcode[i]) {
 134                 possibly_refill(source, 1);
 135                 code = (code << 1) | read_bits(source, 1);
 136                 ++i;
 137
 138                 if (i > 15) {
 139                         fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
 140                         exit(1);
 141                 }
 142         }
 143
 144         return table->codes[table->valptr[i] + code - table->mincode[i]];
 145 }