1#include <base/mem.h>
2
3#include <engine/shared/huffman.h>
4
5#include <gtest/gtest.h>
6
7TEST(Huffman, CompressionInputSizeZero)
8{
9 CHuffman Huffman;
10 Huffman.Init();
11
12 unsigned char aInput[64];
13 unsigned char aCompressed[2048];
14 unsigned char aDecompressed[2048];
15
16 const int CompressedSize = Huffman.Compress(pInput: aInput, InputSize: 0, pOutput: aCompressed, OutputSize: sizeof(aCompressed));
17 const unsigned char aExpected[] = {0x8A, 0x1B};
18
19 ASSERT_EQ(CompressedSize, (int)sizeof(aExpected));
20 EXPECT_EQ(mem_comp(aCompressed, aExpected, CompressedSize), 0);
21
22 const int UncompressedSize = Huffman.Decompress(pInput: aCompressed, InputSize: CompressedSize, pOutput: aDecompressed, OutputSize: sizeof(aDecompressed));
23 ASSERT_EQ(UncompressedSize, 0);
24}
25
26TEST(Huffman, CompressionShouldNotChangeData)
27{
28 CHuffman Huffman;
29 Huffman.Init();
30
31 unsigned char aInput[64];
32 unsigned char aCompressed[2048];
33 unsigned char aDecompressed[2048];
34
35 for(int InputMod = 0x00; InputMod <= 0xFFFF; ++InputMod)
36 {
37 mem_zero(block: aInput, size: sizeof(aInput));
38 mem_zero(block: aCompressed, size: sizeof(aCompressed));
39 mem_zero(block: aDecompressed, size: sizeof(aDecompressed));
40 aInput[0] = InputMod & 0xFF;
41 aInput[1] = (InputMod >> 8) & 0xFF;
42
43 const int CompressedSize = Huffman.Compress(pInput: aInput, InputSize: sizeof(aInput), pOutput: aCompressed, OutputSize: sizeof(aCompressed));
44 const int MaxSize = InputMod <= 0xFF ? 12 : 14;
45 ASSERT_GE(CompressedSize, 10);
46 ASSERT_LE(CompressedSize, MaxSize);
47
48 const int UncompressedSize = Huffman.Decompress(pInput: aCompressed, InputSize: CompressedSize, pOutput: aDecompressed, OutputSize: sizeof(aDecompressed));
49 ASSERT_EQ(UncompressedSize, (int)sizeof(aInput));
50 EXPECT_EQ(mem_comp(aInput, aDecompressed, UncompressedSize), 0);
51 }
52}
53
54TEST(Huffman, CompressionCompatible)
55{
56 CHuffman Huffman;
57 Huffman.Init();
58
59 unsigned char aInput[64];
60 unsigned char aCompressed[2048];
61
62 mem_zero(block: aInput, size: sizeof(aInput));
63 mem_zero(block: aCompressed, size: sizeof(aCompressed));
64
65 // compress 1-7 followed by a bunch of nullbytes
66 for(int i = 0; i < 8; i++)
67 aInput[i] = i;
68
69 const int Size = Huffman.Compress(pInput: aInput, InputSize: sizeof(aInput), pOutput: aCompressed, OutputSize: sizeof(aCompressed));
70
71 const unsigned char aExpected[] = {0x51, 0x58, 0x78, 0x76, 0x1B, 0xB7, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F, 0xc5, 0x0D};
72
73 ASSERT_EQ(Size, (int)sizeof(aExpected)) << "The compression is not compatible with older/other implementations anymore";
74 EXPECT_EQ(mem_comp(aCompressed, aExpected, Size), 0) << "The compression is not compatible with older/other implementations anymore";
75}
76
77TEST(Huffman, CompressionNoTrailingNull)
78{
79 CHuffman Huffman;
80 Huffman.Init();
81
82 unsigned char aInput[64];
83 unsigned char aCompressed[2048];
84 unsigned char aDecompressed[2048];
85
86 mem_zero(block: aInput, size: sizeof(aInput));
87 mem_zero(block: aCompressed, size: sizeof(aCompressed));
88 mem_zero(block: aDecompressed, size: sizeof(aDecompressed));
89 aInput[0] = 0x15;
90
91 const int CompressedSize = Huffman.Compress(pInput: aInput, InputSize: sizeof(aInput), pOutput: aCompressed, OutputSize: sizeof(aCompressed));
92
93 const unsigned char aExpected[] = {0xBE, 0xFD, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x15, 0x37};
94
95 ASSERT_EQ(CompressedSize, (int)sizeof(aExpected));
96 EXPECT_EQ(mem_comp(aCompressed, aExpected, CompressedSize), 0);
97
98 const int UncompressedSize = Huffman.Decompress(pInput: aCompressed, InputSize: CompressedSize, pOutput: aDecompressed, OutputSize: sizeof(aDecompressed));
99 ASSERT_EQ(UncompressedSize, (int)sizeof(aInput));
100 EXPECT_EQ(mem_comp(aInput, aDecompressed, UncompressedSize), 0);
101}
102
103TEST(Huffman, CompressionTruncated)
104{
105 CHuffman Huffman;
106 Huffman.Init();
107
108 unsigned char aInput[64];
109 unsigned char aCompressed[2048];
110
111 mem_zero(block: aInput, size: sizeof(aInput));
112 mem_zero(block: aCompressed, size: sizeof(aCompressed));
113
114 // compress 1-7 followed by a bunch of nullbytes
115 for(int i = 0; i < 8; i++)
116 aInput[i] = i;
117
118 for(size_t CompressedSize = 1; CompressedSize <= 14; ++CompressedSize)
119 {
120 EXPECT_EQ(Huffman.Compress(aInput, sizeof(aInput), aCompressed, CompressedSize), -1) << "Compression expected to fail with size " << CompressedSize;
121 }
122 for(size_t CompressedSize = 15; CompressedSize <= 20; ++CompressedSize)
123 {
124 EXPECT_EQ(Huffman.Compress(aInput, sizeof(aInput), aCompressed, CompressedSize), 15) << "Compression expected to succeed with size " << CompressedSize;
125 }
126}
127
128TEST(Huffman, DecompressionTableLookupIntegerOverflow)
129{
130 CHuffman Huffman;
131 Huffman.Init();
132
133 // Test data found by fuzzing
134 const unsigned char aInput1[] = {0x1A};
135 const unsigned char aInput2[] = {0x62, 0x91, 0x62, 0xA9};
136 const unsigned char aInput3[] = {0x4C, 0x04, 0xFE, 0x00, 0x68};
137 unsigned char aUncompressed[2048];
138
139 EXPECT_EQ(Huffman.Decompress(aInput1, sizeof(aInput1), aUncompressed, sizeof(aUncompressed)), -1);
140 EXPECT_EQ(Huffman.Decompress(aInput2, sizeof(aInput2), aUncompressed, sizeof(aUncompressed)), -1);
141 EXPECT_EQ(Huffman.Decompress(aInput3, sizeof(aInput3), aUncompressed, sizeof(aUncompressed)), -1);
142}
143