Add code for efficient (?) Huffman decoding.
[fjl] / dehuff_test.c
index e383a1d5d43911a2a9a2dd7faa9733fd63077032..0212244bdf4594be6cf4b54280a5eb80003d0a45 100644 (file)
@@ -19,23 +19,36 @@ ssize_t custom_read(void* userdata, uint8_t* buf, size_t count)
        return num_to_read;     
 }
 
-// Uses the example from section K.3.1 from the JPEG standard.
-void test_table_gen()
-{
-       uint8_t bytes[] = {
-               // Chunk length: Chunk length (2) + coefficient class (1) + 
-               // code lengths (16) + code words (12)
-               0, 31, 
+// The example from section K.3.1 from the JPEG standard.
+uint8_t example_table_bytes[] = {
+       // Chunk length: Chunk length (2) + coefficient class (1) + 
+       // code lengths (16) + code words (12)
+       0, 31, 
 
-               // DC coefficient, table 0
-               0x00,
+       // DC coefficient, table 0
+       0x00,
 
-               // List of code lengths
-               0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+       // List of code lengths
+       0x00, 0x01, 0x05, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 
-               // Code words
-               0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b,
-       };
+       // Code words
+       0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b,
+};
+
+void read_example_tables(huffman_tables_t* tables)
+{
+       struct custom_read_userdata ud;
+       ud.bytes = example_table_bytes;
+       ud.bytes_left = sizeof(example_table_bytes);
+
+       read_huffman_tables(tables, custom_read, &ud);
+}      
+
+// Test that the generated code tables are what we expect.
+void test_table_gen()
+{
+       huffman_tables_t tables;
+       read_example_tables(&tables);
 
        // Expected results (table K.3)
        struct {
@@ -55,19 +68,44 @@ void test_table_gen()
                { 8, 0xfe },
                { 9, 0x1fe },
        };
+       
+       struct huffman_table* tbl = &tables[DC_CLASS][0];       
+       for (unsigned i = 0; i < 12; ++i) {
+               assert(tbl->huffsize[i] == expected_table[i].code_length);
+               assert(tbl->huffcode[i] == expected_table[i].code_word);
+       }
+}
+
+// Test that we can decode a simple bit stream.
+// Note that since we end on a long code, we won't crash into
+// the end-of-stream problems we currently have.
+void test_decoding()
+{
+       huffman_tables_t tables;
+       read_example_tables(&tables);
+       
+       // Our stream looks like this:
+       //
+       //  0   1   2   3   4   5    6     7      8       9       10        11
+       // 00 010 011 100 101 110 1110 11110 111110 1111110 11111110 111111110
+       uint8_t bytes[] = {
+               0x13, 0x97, 0x77, 0xbe, 0xfd, 0xfd, 0xfe
+       };
 
        struct custom_read_userdata ud;
        ud.bytes = bytes;
        ud.bytes_left = sizeof(bytes);
 
-       huffman_tables_t tables;
-       read_huffman_tables(&tables, custom_read, &ud);
+       struct bit_source source;
+       init_bit_source(&source, custom_read, &ud);
                
        struct huffman_table* tbl = &tables[DC_CLASS][0];       
        for (unsigned i = 0; i < 12; ++i) {
-               assert(tbl->huffsize[i] == expected_table[i].code_length);
-               assert(tbl->huffcode[i] == expected_table[i].code_word);
+               unsigned symbol = read_huffman_symbol(tbl, &source);
+               assert(symbol == i);
        }
+
+       assert(source.bits_available == 0);
 }
 
 int main(void)
@@ -75,6 +113,9 @@ int main(void)
        printf("test_table_gen()\n");
        test_table_gen();
        
+       printf("test_decoding()\n");
+       test_decoding();
+       
        printf("All tests pass.\n");
        return 0;
 }