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

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