1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <gtest/gtest.h>
#include <inflate.h>
/* Test that we read the bits in the correct order */
TEST (BufferTests, GetNextBitTest) {
reset_pos();
/* The 4-byte buffer in memory */
unsigned char buf[4] = {175, /* = 10101111 */
240, /* = 11110000 */
15, /* = 00001111 */
204}; /* = 11001100 */
/*
* The real stream order.
* If the bytes are laid out in memory as
* [b0b1..b7] [b8...b15] ...
* Then the correct stream order is:
* [b7...b0] [b15...b8] ...
*/
int stream_order[32] = {1, 1, 1, 1, 0, 1, 0, 1,
0, 0, 0, 0, 1, 1, 1, 1,
1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 1, 1, 0, 0, 1, 1};
for (int i = 0; i < 32; i++) {
// TODO this cast should probably not be necessary
// change type signature to unsigned char in inflate
ASSERT_EQ (get_next_bit((char *) buf), stream_order[i]);
}
}
/*
* Test that we get the correct numerical value when
* reading from a buffer.
* In this test, all integers are interpreted in
* STREAM ORDER. That is, if the bitstream
* is (b0, b1, b2, ..., bn), we interpret
* b0 as the MSB and bn as the LSB. Note that the order
* of the bitstream is not necessarily the order that
* the bits are laid out in memory; see get_next_bit().
*/
TEST (BufferTests, StreamOrderTest) {
reset_pos();
unsigned char buf[2] = {220, /* = 11011100 */
145}; /* = 10010001 */
/* First 3 bits are 001 */
ASSERT_EQ (get_n_bits((char *) buf, 3, false), 1);
/* Next 5 are 11011 */
ASSERT_EQ (get_n_bits((char *) buf, 5, false), 27);
/* Next 2 are 10 */
ASSERT_EQ (get_n_bits((char *) buf, 2, false), 2);
/* Next 6 are 001001 */
ASSERT_EQ (get_n_bits((char *) buf, 6, false), 9);
}
/*
* Like the test above, but interprets integers in REVERSE STREAM ORDER.
* That is, if we read in the bitstream (b0, b1, ..., bn),
* b0 is the LSB and bn is the MSB.
*/
TEST (BufferTests, RevStreamOrderTest) {
reset_pos();
unsigned char buf[2] = {220, /* = 11011100 */
145}; /* = 10010001 */
/* First 3 bits are 001 */
ASSERT_EQ (get_n_bits((char *) buf, 3, true), 4);
/* Next 5 are 11011 */
ASSERT_EQ (get_n_bits((char *) buf, 5, true), 27);
/* Next 2 are 10 */
ASSERT_EQ (get_n_bits((char *) buf, 2, true), 1);
/* Next 6 are 001001 */
ASSERT_EQ (get_n_bits((char *) buf, 6, true), 36);
}
/* Test making a huffman tree from a sequence of lengths */
TEST (HuffmanTests, TestMakeHuffman) {
int n_symbols = 8;
int lens[8] = {3, 3, 3, 3, 3, 2, 4, 4};
huffman_t *hf = make_huffman(lens, n_symbols);
int bl_counts[MAX_LENGTH + 1] = {0, 0, 1, 5, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
/* Check bl_counts */
for (int i = 0; i < MAX_LENGTH + 1; i++) {
ASSERT_EQ (hf->bl_counts[i], bl_counts[i]);
}
/*
* Check min_codes for entries with non-zero bl_count
* It doesn't really matter what the other entries are.
*/
ASSERT_EQ (hf->min_codes[2], 0);
ASSERT_EQ (hf->min_codes[3], 2);
ASSERT_EQ (hf->min_codes[4], 14);
/* Check that the alphabet arrays were populated correctly. */
ASSERT_EQ (hf->alphabet[2][0], 5);
for (int i = 0; i < 5; i++) ASSERT_EQ (hf->alphabet[3][i], i);
ASSERT_EQ (hf->alphabet[4][0], 6);
ASSERT_EQ (hf->alphabet[4][1], 7);
destroy_huffman(hf);
}
/*
* Test that make_huffman does not assign a code to symbols with
* a length of 0.
*/
TEST (HuffmanTests, TestMakeHuffmanZeroLens) {
int n_symbols = 8;
int lens[8] = {1, 0, 2, 3, 3, 0, 4, 3};
huffman_t *hf = make_huffman(lens, n_symbols);
int bl_counts[MAX_LENGTH + 1] = {0, 1, 1, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
/* Check bl_counts */
for (int i = 0; i < MAX_LENGTH + 1; i++) {
ASSERT_EQ (hf->bl_counts[i], bl_counts[i]);
}
/* Check min_codes */
ASSERT_EQ (hf->min_codes[1], 0);
ASSERT_EQ (hf->min_codes[2], 2);
ASSERT_EQ (hf->min_codes[3], 6);
ASSERT_EQ (hf->min_codes[4], 18);
/* Check alphabet. */
ASSERT_EQ (hf->alphabet[1][0], 0);
/* 1 and 5 are not used! (length = 0) */
ASSERT_EQ (hf->alphabet[2][0], 2);
ASSERT_EQ (hf->alphabet[3][0], 3);
ASSERT_EQ (hf->alphabet[3][1], 4);
ASSERT_EQ (hf->alphabet[3][2], 7);
ASSERT_EQ (hf->alphabet[4][0], 6);
destroy_huffman(hf);
}
// TODO
TEST (HuffmanTests, TestReadChunk) {
}
TEST (HuffmanTests, TestReadLens) {}
int main(int argc, char **argv) {
::testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}