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                 // Generate the AC lookup tables.
 124                 for (unsigned i = 0; i < DEHUF_AC_TABLE_SIZE; ++i) {
 125                         tbl->ac_table_codes[i] = AC_DEHUF_SLOW_PATH;
 126                         tbl->ac_table_length[i] = AC_DEHUF_SLOW_PATH;
 127                         tbl->ac_table_skip[i] = AC_DEHUF_SLOW_PATH;
 128
 129                         int lookup = i >> (DEHUF_AC_TABLE_BITS - DEHUF_TABLE_BITS);
 130                         int rs = tbl->lookup_table_codes[lookup];
 131                         unsigned length = tbl->lookup_table_length[lookup];
 132                         if (rs == DEHUF_SLOW_PATH) {
 133                                 // Not enough bits to decode even the length.
 134                                 continue;
 135                         }
 136                         if (rs == 0x00) {
 137                                 // End of block.
 138                                 tbl->ac_table_codes[i] = AC_END_OF_BLOCK;
 139                                 tbl->ac_table_length[i] = length;
 140                                 tbl->ac_table_skip[i] = 0;
 141                                 continue;
 142                         }
 143                         if (rs == 0xf0) {
 144                                 // 16 zero coefficients.
 145                                 tbl->ac_table_codes[i] = AC_SIXTEEN_ZEROS;
 146                                 tbl->ac_table_length[i] = length;
 147                                 tbl->ac_table_skip[i] = 15;
 148                                 continue;
 149                         }
 150
 151                         unsigned r = rs >> 4;
 152                         unsigned s = rs & 0xf;
 153                         if (s > DEHUF_AC_TABLE_BITS - length) {
 154                                 // Not enough bits to decode this coefficient.
 155                                 continue;
 156                         }
 157
 158                         unsigned bits = (i >> (DEHUF_AC_TABLE_BITS - length - s)) & ((1 << s) - 1);
 159
 160                         tbl->ac_table_codes[i] = extend(bits, s);
 161                         tbl->ac_table_length[i] = length + s;
 162                         tbl->ac_table_skip[i] = r;
 163
 164                         assert(tbl->ac_table_length[i] <= DEHUF_AC_TABLE_BITS);
 165                 }
 166         }
 167
 168         free(buf);
 169 }
 170
 171 unsigned read_huffman_symbol_slow_path(const struct huffman_table* table,
 172                                        struct bit_source* source) {
 173         possibly_refill(source, 1);
 174         unsigned code = read_bits(source, 1);
 175         int i = 0;
 176
 177         while (table->maxcode[i] == -1 || code > (unsigned)table->maxcode[i]) {
 178                 possibly_refill(source, 1);
 179                 code = (code << 1) | read_bits(source, 1);
 180                 ++i;
 181
 182                 if (i > 15) {
 183                         fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
 184                         exit(1);
 185                 }
 186         }
 187
 188         return table->codes[table->valptr[i] + code - table->mincode[i]];
 189 }