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
   8 void reliable_read(raw_input_func_t* input_func, void* userdata, uint8_t* buf, size_t len)
   9 {
  10         while (len > 0) {
  11                 ssize_t bytes_read = input_func(userdata, buf, len);
  12                 assert(bytes_read <= len);
  13
  14                 // TODO: We need better error handling here. setjmp()/longjmp()
  15                 // should hopefully do the trick, but we need to take care for
  16                 // suspension.
  17                 if (bytes_read == (ssize_t)-1) {
  18                         fprintf(stderr, "Input function returned error\n");
  19                         exit(1);
  20                 }
  21                 if (bytes_read == 0) {
  22                         fprintf(stderr, "Premature EOF\n");
  23                         exit(1);
  24                 }
  25
  26                 buf += bytes_read;
  27                 len -= bytes_read;
  28         }
  29 }
  30
  31 uint16_t read_length(raw_input_func_t* input_func, void* userdata)
  32 {
  33         uint8_t buf[2];
  34         reliable_read(input_func, userdata, buf, 2);
  35         return (buf[0] << 8) | buf[1];
  36 }
  37
  38 void read_huffman_tables(huffman_tables_t* dst, raw_input_func_t* input_func, void* userdata)
  39 {
  40         size_t len = read_length(input_func, userdata);
  41         assert(len > 2);
  42         len -= 2;
  43
  44         // TODO: check for NULL return
  45         uint8_t* buf = (uint8_t*)malloc(len);
  46         uint8_t* inptr = buf;
  47         reliable_read(input_func, userdata, buf, len);
  48
  49         while (len > 0) {
  50                 unsigned char tc_th = *inptr++;
  51                 --len;
  52                 unsigned table_class = tc_th >> 4;
  53                 unsigned table_dest = tc_th & 0x0f;
  54
  55                 if (table_class != 0 && table_class != 1) {
  56                         fprintf(stderr, "Error: Unknown table class %u\n", table_class);
  57                         exit(1);
  58                 }
  59                 if (table_dest >= 4) {
  60                         fprintf(stderr, "Error: Unknown table destination %u\n", table_dest);
  61                         exit(1);
  62                 }
  63
  64                 struct huffman_table* tbl = dst[table_class][table_dest];
  65                 if (len < 16) {
  66                         fprintf(stderr, "Short read for num_codes\n");
  67                         exit(1);
  68                 }
  69                 for (unsigned i = 0; i < 16; ++i) {
  70                         tbl->num_codes[i] = *inptr++;
  71                         --len;
  72                 }
  73                 for (unsigned i = 0, k = 0; i < 16; ++i) {
  74                         if (len < tbl->num_codes[i]) {
  75                                 fprintf(stderr, "Short read for codes\n");
  76                                 exit(1);
  77                         }
  78                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
  79                                 tbl->codes[k] = *inptr++;
  80                                 --len;
  81                         }
  82                 }
  83
  84                 // Generate derived tables
  85
  86                 // generate_size_table (figure C.1)
  87                 {
  88                         unsigned k = 0;
  89                         for (unsigned i = 0; i < 16; ++i) {
  90                                 for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
  91                                         tbl->huffsize[k] = i + 1;
  92                                 }
  93                         }
  94                         tbl->huffsize[k] = 0;
  95                 }
  96
  97                 // generate_code_table (figure C.2)
  98                 unsigned si = tbl->huffsize[0];
  99                 for (unsigned i = 0, j = 0;; ) {
 100                         tbl->huffcode[i++] = j++;
 101                         if (tbl->huffsize[i] == si) {
 102                                 continue;
 103                         }
 104                         if (tbl->huffsize[i] == 0) {
 105                                 break;
 106                         }
 107
 108                         do {
 109                                 j <<= 1;
 110                         } while (++si != tbl->huffsize[i]);
 111                 }
 112
 113                 // decoder_tables (figure F.15)
 114                 for (unsigned i = 0, j = 0; i < 16; ++i) {
 115                         if (tbl->num_codes[i] == 0) {
 116                                 tbl->maxcode[i] = -1;
 117                                 continue;
 118                         }
 119
 120                         tbl->valptr[i] = j;
 121                         tbl->mincode[i] = tbl->huffcode[j];
 122                         j += tbl->num_codes[i];
 123                         tbl->maxcode[i] = tbl->huffcode[j - 1];
 124                 }
 125
 126                 // Generate the lookup tables
 127                 for (unsigned i = 0; i < DEHUF_TABLE_SIZE; ++i) {
 128                         tbl->lookup_table_codes[i] = DEHUF_SLOW_PATH;
 129                         tbl->lookup_table_length[i] = DEHUF_SLOW_PATH;
 130                 }
 131
 132                 unsigned k = 0;
 133                 for (unsigned i = 0; i < 16; ++i) {
 134                         for (unsigned j = 0; j < tbl->num_codes[i]; ++j, ++k) {
 135                                 const unsigned code = tbl->huffcode[k];
 136                                 const unsigned length = tbl->huffsize[k];
 137                                 if (length > DEHUF_TABLE_BITS) {
 138                                         continue;
 139                                 }
 140                                 const unsigned prefix_min = code << (DEHUF_TABLE_BITS - length);
 141                                 const unsigned prefix_max = ((code + 1) << (DEHUF_TABLE_BITS - length));
 142
 143                                 for (unsigned elem = prefix_min; elem < prefix_max; ++elem) {
 144                                         assert(tbl->lookup_table_codes[elem] == DEHUF_SLOW_PATH);
 145                                         assert(tbl->lookup_table_length[elem] == DEHUF_SLOW_PATH);
 146                                         tbl->lookup_table_codes[elem] = k;
 147                                         tbl->lookup_table_length[elem] = length;
 148                                 }
 149                         }
 150                 }
 151         }
 152
 153         free(buf);
 154 }
 155
 156 unsigned read_huffman_symbol_slow_path(const struct huffman_table* table,
 157                                        struct bit_source* source) {
 158         possibly_refill(source, 1);
 159         unsigned code = read_bits(source, 1);
 160         int i = 0;
 161
 162         while (code > table->maxcode[i] || table->maxcode[i] == -1) {
 163                 possibly_refill(source, 1);
 164                 code = (code << 1) | read_bits(source, 1);
 165                 ++i;
 166
 167                 if (i > 15) {
 168                         fprintf(stderr, "Error in Huffman decoding: Too long code (%x)\n", code);
 169                         exit(1);
 170                 }
 171         }
 172
 173         return table->codes[table->valptr[i] + code - table->mincode[i]];
 174 }