1/*
2 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23package jdk.incubator.http.internal.hpack;
24
25import org.testng.annotations.Test;
26
27import java.nio.ByteBuffer;
28import java.util.Stack;
29import java.util.regex.Matcher;
30import java.util.regex.Pattern;
31
32import static java.lang.Integer.parseInt;
33import static org.testng.Assert.*;
34
35public final class HuffmanTest {
36
37    //
38    // https://tools.ietf.org/html/rfc7541#appendix-B
39    //
40    private static final String SPEC =
41            // @formatter:off
42     "                          code as bits                 as hex   len\n" +
43     "        sym              aligned to MSB                aligned   in\n" +
44     "                                                       to LSB   bits\n" +
45     "       (  0)  |11111111|11000                             1ff8  [13]\n" +
46     "       (  1)  |11111111|11111111|1011000                7fffd8  [23]\n" +
47     "       (  2)  |11111111|11111111|11111110|0010         fffffe2  [28]\n" +
48     "       (  3)  |11111111|11111111|11111110|0011         fffffe3  [28]\n" +
49     "       (  4)  |11111111|11111111|11111110|0100         fffffe4  [28]\n" +
50     "       (  5)  |11111111|11111111|11111110|0101         fffffe5  [28]\n" +
51     "       (  6)  |11111111|11111111|11111110|0110         fffffe6  [28]\n" +
52     "       (  7)  |11111111|11111111|11111110|0111         fffffe7  [28]\n" +
53     "       (  8)  |11111111|11111111|11111110|1000         fffffe8  [28]\n" +
54     "       (  9)  |11111111|11111111|11101010               ffffea  [24]\n" +
55     "       ( 10)  |11111111|11111111|11111111|111100      3ffffffc  [30]\n" +
56     "       ( 11)  |11111111|11111111|11111110|1001         fffffe9  [28]\n" +
57     "       ( 12)  |11111111|11111111|11111110|1010         fffffea  [28]\n" +
58     "       ( 13)  |11111111|11111111|11111111|111101      3ffffffd  [30]\n" +
59     "       ( 14)  |11111111|11111111|11111110|1011         fffffeb  [28]\n" +
60     "       ( 15)  |11111111|11111111|11111110|1100         fffffec  [28]\n" +
61     "       ( 16)  |11111111|11111111|11111110|1101         fffffed  [28]\n" +
62     "       ( 17)  |11111111|11111111|11111110|1110         fffffee  [28]\n" +
63     "       ( 18)  |11111111|11111111|11111110|1111         fffffef  [28]\n" +
64     "       ( 19)  |11111111|11111111|11111111|0000         ffffff0  [28]\n" +
65     "       ( 20)  |11111111|11111111|11111111|0001         ffffff1  [28]\n" +
66     "       ( 21)  |11111111|11111111|11111111|0010         ffffff2  [28]\n" +
67     "       ( 22)  |11111111|11111111|11111111|111110      3ffffffe  [30]\n" +
68     "       ( 23)  |11111111|11111111|11111111|0011         ffffff3  [28]\n" +
69     "       ( 24)  |11111111|11111111|11111111|0100         ffffff4  [28]\n" +
70     "       ( 25)  |11111111|11111111|11111111|0101         ffffff5  [28]\n" +
71     "       ( 26)  |11111111|11111111|11111111|0110         ffffff6  [28]\n" +
72     "       ( 27)  |11111111|11111111|11111111|0111         ffffff7  [28]\n" +
73     "       ( 28)  |11111111|11111111|11111111|1000         ffffff8  [28]\n" +
74     "       ( 29)  |11111111|11111111|11111111|1001         ffffff9  [28]\n" +
75     "       ( 30)  |11111111|11111111|11111111|1010         ffffffa  [28]\n" +
76     "       ( 31)  |11111111|11111111|11111111|1011         ffffffb  [28]\n" +
77     "   ' ' ( 32)  |010100                                       14  [ 6]\n" +
78     "   '!' ( 33)  |11111110|00                                 3f8  [10]\n" +
79     "  '\"' ( 34)  |11111110|01                                 3f9  [10]\n" +
80     "   '#' ( 35)  |11111111|1010                               ffa  [12]\n" +
81     "   '$' ( 36)  |11111111|11001                             1ff9  [13]\n" +
82     "   '%' ( 37)  |010101                                       15  [ 6]\n" +
83     "   '&' ( 38)  |11111000                                     f8  [ 8]\n" +
84     "   ''' ( 39)  |11111111|010                                7fa  [11]\n" +
85     "   '(' ( 40)  |11111110|10                                 3fa  [10]\n" +
86     "   ')' ( 41)  |11111110|11                                 3fb  [10]\n" +
87     "   '*' ( 42)  |11111001                                     f9  [ 8]\n" +
88     "   '+' ( 43)  |11111111|011                                7fb  [11]\n" +
89     "   ',' ( 44)  |11111010                                     fa  [ 8]\n" +
90     "   '-' ( 45)  |010110                                       16  [ 6]\n" +
91     "   '.' ( 46)  |010111                                       17  [ 6]\n" +
92     "   '/' ( 47)  |011000                                       18  [ 6]\n" +
93     "   '0' ( 48)  |00000                                         0  [ 5]\n" +
94     "   '1' ( 49)  |00001                                         1  [ 5]\n" +
95     "   '2' ( 50)  |00010                                         2  [ 5]\n" +
96     "   '3' ( 51)  |011001                                       19  [ 6]\n" +
97     "   '4' ( 52)  |011010                                       1a  [ 6]\n" +
98     "   '5' ( 53)  |011011                                       1b  [ 6]\n" +
99     "   '6' ( 54)  |011100                                       1c  [ 6]\n" +
100     "   '7' ( 55)  |011101                                       1d  [ 6]\n" +
101     "   '8' ( 56)  |011110                                       1e  [ 6]\n" +
102     "   '9' ( 57)  |011111                                       1f  [ 6]\n" +
103     "   ':' ( 58)  |1011100                                      5c  [ 7]\n" +
104     "   ';' ( 59)  |11111011                                     fb  [ 8]\n" +
105     "   '<' ( 60)  |11111111|1111100                           7ffc  [15]\n" +
106     "   '=' ( 61)  |100000                                       20  [ 6]\n" +
107     "   '>' ( 62)  |11111111|1011                               ffb  [12]\n" +
108     "   '?' ( 63)  |11111111|00                                 3fc  [10]\n" +
109     "   '@' ( 64)  |11111111|11010                             1ffa  [13]\n" +
110     "   'A' ( 65)  |100001                                       21  [ 6]\n" +
111     "   'B' ( 66)  |1011101                                      5d  [ 7]\n" +
112     "   'C' ( 67)  |1011110                                      5e  [ 7]\n" +
113     "   'D' ( 68)  |1011111                                      5f  [ 7]\n" +
114     "   'E' ( 69)  |1100000                                      60  [ 7]\n" +
115     "   'F' ( 70)  |1100001                                      61  [ 7]\n" +
116     "   'G' ( 71)  |1100010                                      62  [ 7]\n" +
117     "   'H' ( 72)  |1100011                                      63  [ 7]\n" +
118     "   'I' ( 73)  |1100100                                      64  [ 7]\n" +
119     "   'J' ( 74)  |1100101                                      65  [ 7]\n" +
120     "   'K' ( 75)  |1100110                                      66  [ 7]\n" +
121     "   'L' ( 76)  |1100111                                      67  [ 7]\n" +
122     "   'M' ( 77)  |1101000                                      68  [ 7]\n" +
123     "   'N' ( 78)  |1101001                                      69  [ 7]\n" +
124     "   'O' ( 79)  |1101010                                      6a  [ 7]\n" +
125     "   'P' ( 80)  |1101011                                      6b  [ 7]\n" +
126     "   'Q' ( 81)  |1101100                                      6c  [ 7]\n" +
127     "   'R' ( 82)  |1101101                                      6d  [ 7]\n" +
128     "   'S' ( 83)  |1101110                                      6e  [ 7]\n" +
129     "   'T' ( 84)  |1101111                                      6f  [ 7]\n" +
130     "   'U' ( 85)  |1110000                                      70  [ 7]\n" +
131     "   'V' ( 86)  |1110001                                      71  [ 7]\n" +
132     "   'W' ( 87)  |1110010                                      72  [ 7]\n" +
133     "   'X' ( 88)  |11111100                                     fc  [ 8]\n" +
134     "   'Y' ( 89)  |1110011                                      73  [ 7]\n" +
135     "   'Z' ( 90)  |11111101                                     fd  [ 8]\n" +
136     "   '[' ( 91)  |11111111|11011                             1ffb  [13]\n" +
137     "  '\\' ( 92)  |11111111|11111110|000                     7fff0  [19]\n" +
138     "   ']' ( 93)  |11111111|11100                             1ffc  [13]\n" +
139     "   '^' ( 94)  |11111111|111100                            3ffc  [14]\n" +
140     "   '_' ( 95)  |100010                                       22  [ 6]\n" +
141     "   '`' ( 96)  |11111111|1111101                           7ffd  [15]\n" +
142     "   'a' ( 97)  |00011                                         3  [ 5]\n" +
143     "   'b' ( 98)  |100011                                       23  [ 6]\n" +
144     "   'c' ( 99)  |00100                                         4  [ 5]\n" +
145     "   'd' (100)  |100100                                       24  [ 6]\n" +
146     "   'e' (101)  |00101                                         5  [ 5]\n" +
147     "   'f' (102)  |100101                                       25  [ 6]\n" +
148     "   'g' (103)  |100110                                       26  [ 6]\n" +
149     "   'h' (104)  |100111                                       27  [ 6]\n" +
150     "   'i' (105)  |00110                                         6  [ 5]\n" +
151     "   'j' (106)  |1110100                                      74  [ 7]\n" +
152     "   'k' (107)  |1110101                                      75  [ 7]\n" +
153     "   'l' (108)  |101000                                       28  [ 6]\n" +
154     "   'm' (109)  |101001                                       29  [ 6]\n" +
155     "   'n' (110)  |101010                                       2a  [ 6]\n" +
156     "   'o' (111)  |00111                                         7  [ 5]\n" +
157     "   'p' (112)  |101011                                       2b  [ 6]\n" +
158     "   'q' (113)  |1110110                                      76  [ 7]\n" +
159     "   'r' (114)  |101100                                       2c  [ 6]\n" +
160     "   's' (115)  |01000                                         8  [ 5]\n" +
161     "   't' (116)  |01001                                         9  [ 5]\n" +
162     "   'u' (117)  |101101                                       2d  [ 6]\n" +
163     "   'v' (118)  |1110111                                      77  [ 7]\n" +
164     "   'w' (119)  |1111000                                      78  [ 7]\n" +
165     "   'x' (120)  |1111001                                      79  [ 7]\n" +
166     "   'y' (121)  |1111010                                      7a  [ 7]\n" +
167     "   'z' (122)  |1111011                                      7b  [ 7]\n" +
168     "   '{' (123)  |11111111|1111110                           7ffe  [15]\n" +
169     "   '|' (124)  |11111111|100                                7fc  [11]\n" +
170     "   '}' (125)  |11111111|111101                            3ffd  [14]\n" +
171     "   '~' (126)  |11111111|11101                             1ffd  [13]\n" +
172     "       (127)  |11111111|11111111|11111111|1100         ffffffc  [28]\n" +
173     "       (128)  |11111111|11111110|0110                    fffe6  [20]\n" +
174     "       (129)  |11111111|11111111|010010                 3fffd2  [22]\n" +
175     "       (130)  |11111111|11111110|0111                    fffe7  [20]\n" +
176     "       (131)  |11111111|11111110|1000                    fffe8  [20]\n" +
177     "       (132)  |11111111|11111111|010011                 3fffd3  [22]\n" +
178     "       (133)  |11111111|11111111|010100                 3fffd4  [22]\n" +
179     "       (134)  |11111111|11111111|010101                 3fffd5  [22]\n" +
180     "       (135)  |11111111|11111111|1011001                7fffd9  [23]\n" +
181     "       (136)  |11111111|11111111|010110                 3fffd6  [22]\n" +
182     "       (137)  |11111111|11111111|1011010                7fffda  [23]\n" +
183     "       (138)  |11111111|11111111|1011011                7fffdb  [23]\n" +
184     "       (139)  |11111111|11111111|1011100                7fffdc  [23]\n" +
185     "       (140)  |11111111|11111111|1011101                7fffdd  [23]\n" +
186     "       (141)  |11111111|11111111|1011110                7fffde  [23]\n" +
187     "       (142)  |11111111|11111111|11101011               ffffeb  [24]\n" +
188     "       (143)  |11111111|11111111|1011111                7fffdf  [23]\n" +
189     "       (144)  |11111111|11111111|11101100               ffffec  [24]\n" +
190     "       (145)  |11111111|11111111|11101101               ffffed  [24]\n" +
191     "       (146)  |11111111|11111111|010111                 3fffd7  [22]\n" +
192     "       (147)  |11111111|11111111|1100000                7fffe0  [23]\n" +
193     "       (148)  |11111111|11111111|11101110               ffffee  [24]\n" +
194     "       (149)  |11111111|11111111|1100001                7fffe1  [23]\n" +
195     "       (150)  |11111111|11111111|1100010                7fffe2  [23]\n" +
196     "       (151)  |11111111|11111111|1100011                7fffe3  [23]\n" +
197     "       (152)  |11111111|11111111|1100100                7fffe4  [23]\n" +
198     "       (153)  |11111111|11111110|11100                  1fffdc  [21]\n" +
199     "       (154)  |11111111|11111111|011000                 3fffd8  [22]\n" +
200     "       (155)  |11111111|11111111|1100101                7fffe5  [23]\n" +
201     "       (156)  |11111111|11111111|011001                 3fffd9  [22]\n" +
202     "       (157)  |11111111|11111111|1100110                7fffe6  [23]\n" +
203     "       (158)  |11111111|11111111|1100111                7fffe7  [23]\n" +
204     "       (159)  |11111111|11111111|11101111               ffffef  [24]\n" +
205     "       (160)  |11111111|11111111|011010                 3fffda  [22]\n" +
206     "       (161)  |11111111|11111110|11101                  1fffdd  [21]\n" +
207     "       (162)  |11111111|11111110|1001                    fffe9  [20]\n" +
208     "       (163)  |11111111|11111111|011011                 3fffdb  [22]\n" +
209     "       (164)  |11111111|11111111|011100                 3fffdc  [22]\n" +
210     "       (165)  |11111111|11111111|1101000                7fffe8  [23]\n" +
211     "       (166)  |11111111|11111111|1101001                7fffe9  [23]\n" +
212     "       (167)  |11111111|11111110|11110                  1fffde  [21]\n" +
213     "       (168)  |11111111|11111111|1101010                7fffea  [23]\n" +
214     "       (169)  |11111111|11111111|011101                 3fffdd  [22]\n" +
215     "       (170)  |11111111|11111111|011110                 3fffde  [22]\n" +
216     "       (171)  |11111111|11111111|11110000               fffff0  [24]\n" +
217     "       (172)  |11111111|11111110|11111                  1fffdf  [21]\n" +
218     "       (173)  |11111111|11111111|011111                 3fffdf  [22]\n" +
219     "       (174)  |11111111|11111111|1101011                7fffeb  [23]\n" +
220     "       (175)  |11111111|11111111|1101100                7fffec  [23]\n" +
221     "       (176)  |11111111|11111111|00000                  1fffe0  [21]\n" +
222     "       (177)  |11111111|11111111|00001                  1fffe1  [21]\n" +
223     "       (178)  |11111111|11111111|100000                 3fffe0  [22]\n" +
224     "       (179)  |11111111|11111111|00010                  1fffe2  [21]\n" +
225     "       (180)  |11111111|11111111|1101101                7fffed  [23]\n" +
226     "       (181)  |11111111|11111111|100001                 3fffe1  [22]\n" +
227     "       (182)  |11111111|11111111|1101110                7fffee  [23]\n" +
228     "       (183)  |11111111|11111111|1101111                7fffef  [23]\n" +
229     "       (184)  |11111111|11111110|1010                    fffea  [20]\n" +
230     "       (185)  |11111111|11111111|100010                 3fffe2  [22]\n" +
231     "       (186)  |11111111|11111111|100011                 3fffe3  [22]\n" +
232     "       (187)  |11111111|11111111|100100                 3fffe4  [22]\n" +
233     "       (188)  |11111111|11111111|1110000                7ffff0  [23]\n" +
234     "       (189)  |11111111|11111111|100101                 3fffe5  [22]\n" +
235     "       (190)  |11111111|11111111|100110                 3fffe6  [22]\n" +
236     "       (191)  |11111111|11111111|1110001                7ffff1  [23]\n" +
237     "       (192)  |11111111|11111111|11111000|00           3ffffe0  [26]\n" +
238     "       (193)  |11111111|11111111|11111000|01           3ffffe1  [26]\n" +
239     "       (194)  |11111111|11111110|1011                    fffeb  [20]\n" +
240     "       (195)  |11111111|11111110|001                     7fff1  [19]\n" +
241     "       (196)  |11111111|11111111|100111                 3fffe7  [22]\n" +
242     "       (197)  |11111111|11111111|1110010                7ffff2  [23]\n" +
243     "       (198)  |11111111|11111111|101000                 3fffe8  [22]\n" +
244     "       (199)  |11111111|11111111|11110110|0            1ffffec  [25]\n" +
245     "       (200)  |11111111|11111111|11111000|10           3ffffe2  [26]\n" +
246     "       (201)  |11111111|11111111|11111000|11           3ffffe3  [26]\n" +
247     "       (202)  |11111111|11111111|11111001|00           3ffffe4  [26]\n" +
248     "       (203)  |11111111|11111111|11111011|110          7ffffde  [27]\n" +
249     "       (204)  |11111111|11111111|11111011|111          7ffffdf  [27]\n" +
250     "       (205)  |11111111|11111111|11111001|01           3ffffe5  [26]\n" +
251     "       (206)  |11111111|11111111|11110001               fffff1  [24]\n" +
252     "       (207)  |11111111|11111111|11110110|1            1ffffed  [25]\n" +
253     "       (208)  |11111111|11111110|010                     7fff2  [19]\n" +
254     "       (209)  |11111111|11111111|00011                  1fffe3  [21]\n" +
255     "       (210)  |11111111|11111111|11111001|10           3ffffe6  [26]\n" +
256     "       (211)  |11111111|11111111|11111100|000          7ffffe0  [27]\n" +
257     "       (212)  |11111111|11111111|11111100|001          7ffffe1  [27]\n" +
258     "       (213)  |11111111|11111111|11111001|11           3ffffe7  [26]\n" +
259     "       (214)  |11111111|11111111|11111100|010          7ffffe2  [27]\n" +
260     "       (215)  |11111111|11111111|11110010               fffff2  [24]\n" +
261     "       (216)  |11111111|11111111|00100                  1fffe4  [21]\n" +
262     "       (217)  |11111111|11111111|00101                  1fffe5  [21]\n" +
263     "       (218)  |11111111|11111111|11111010|00           3ffffe8  [26]\n" +
264     "       (219)  |11111111|11111111|11111010|01           3ffffe9  [26]\n" +
265     "       (220)  |11111111|11111111|11111111|1101         ffffffd  [28]\n" +
266     "       (221)  |11111111|11111111|11111100|011          7ffffe3  [27]\n" +
267     "       (222)  |11111111|11111111|11111100|100          7ffffe4  [27]\n" +
268     "       (223)  |11111111|11111111|11111100|101          7ffffe5  [27]\n" +
269     "       (224)  |11111111|11111110|1100                    fffec  [20]\n" +
270     "       (225)  |11111111|11111111|11110011               fffff3  [24]\n" +
271     "       (226)  |11111111|11111110|1101                    fffed  [20]\n" +
272     "       (227)  |11111111|11111111|00110                  1fffe6  [21]\n" +
273     "       (228)  |11111111|11111111|101001                 3fffe9  [22]\n" +
274     "       (229)  |11111111|11111111|00111                  1fffe7  [21]\n" +
275     "       (230)  |11111111|11111111|01000                  1fffe8  [21]\n" +
276     "       (231)  |11111111|11111111|1110011                7ffff3  [23]\n" +
277     "       (232)  |11111111|11111111|101010                 3fffea  [22]\n" +
278     "       (233)  |11111111|11111111|101011                 3fffeb  [22]\n" +
279     "       (234)  |11111111|11111111|11110111|0            1ffffee  [25]\n" +
280     "       (235)  |11111111|11111111|11110111|1            1ffffef  [25]\n" +
281     "       (236)  |11111111|11111111|11110100               fffff4  [24]\n" +
282     "       (237)  |11111111|11111111|11110101               fffff5  [24]\n" +
283     "       (238)  |11111111|11111111|11111010|10           3ffffea  [26]\n" +
284     "       (239)  |11111111|11111111|1110100                7ffff4  [23]\n" +
285     "       (240)  |11111111|11111111|11111010|11           3ffffeb  [26]\n" +
286     "       (241)  |11111111|11111111|11111100|110          7ffffe6  [27]\n" +
287     "       (242)  |11111111|11111111|11111011|00           3ffffec  [26]\n" +
288     "       (243)  |11111111|11111111|11111011|01           3ffffed  [26]\n" +
289     "       (244)  |11111111|11111111|11111100|111          7ffffe7  [27]\n" +
290     "       (245)  |11111111|11111111|11111101|000          7ffffe8  [27]\n" +
291     "       (246)  |11111111|11111111|11111101|001          7ffffe9  [27]\n" +
292     "       (247)  |11111111|11111111|11111101|010          7ffffea  [27]\n" +
293     "       (248)  |11111111|11111111|11111101|011          7ffffeb  [27]\n" +
294     "       (249)  |11111111|11111111|11111111|1110         ffffffe  [28]\n" +
295     "       (250)  |11111111|11111111|11111101|100          7ffffec  [27]\n" +
296     "       (251)  |11111111|11111111|11111101|101          7ffffed  [27]\n" +
297     "       (252)  |11111111|11111111|11111101|110          7ffffee  [27]\n" +
298     "       (253)  |11111111|11111111|11111101|111          7ffffef  [27]\n" +
299     "       (254)  |11111111|11111111|11111110|000          7fffff0  [27]\n" +
300     "       (255)  |11111111|11111111|11111011|10           3ffffee  [26]\n" +
301     "   EOS (256)  |11111111|11111111|11111111|111111      3fffffff  [30]";
302    // @formatter:on
303
304    @Test
305    public void read_table() {
306        Pattern line = Pattern.compile(
307                "\\(\\s*(?<ascii>\\d+)\\s*\\)\\s*(?<binary>(\\|(0|1)+)+)\\s*" +
308                        "(?<hex>[0-9a-zA-Z]+)\\s*\\[\\s*(?<len>\\d+)\\s*\\]");
309        Matcher m = line.matcher(SPEC);
310        int i = 0;
311        while (m.find()) {
312            String ascii = m.group("ascii");
313            String binary = m.group("binary").replaceAll("\\|", "");
314            String hex = m.group("hex");
315            String len = m.group("len");
316
317            // Several sanity checks for the data read from the table, just to
318            // make sure what we read makes sense
319            assertEquals(parseInt(len), binary.length());
320            assertEquals(parseInt(binary, 2), parseInt(hex, 16));
321
322            int expected = parseInt(ascii);
323
324            // TODO: find actual eos, do not hardcode it!
325            byte[] bytes = intToBytes(0x3fffffff, 30,
326                    parseInt(hex, 16), parseInt(len));
327
328            StringBuilder actual = new StringBuilder();
329            Huffman.Reader t = new Huffman.Reader();
330            t.read(ByteBuffer.wrap(bytes), actual, false, true);
331
332            // What has been read MUST represent a single symbol
333            assertEquals(actual.length(), 1, "ascii: " + ascii);
334
335            // It's a lot more visual to compare char as codes rather than
336            // characters (as some of them might not be visible)
337            assertEquals(actual.charAt(0), expected);
338            i++;
339        }
340        assertEquals(i, 257); // 256 + EOS
341    }
342
343    //
344    // https://tools.ietf.org/html/rfc7541#appendix-C.4.1
345    //
346    @Test
347    public void read_1() {
348        read("f1e3 c2e5 f23a 6ba0 ab90 f4ff", "www.example.com");
349    }
350
351    @Test
352    public void write_1() {
353        write("www.example.com", "f1e3 c2e5 f23a 6ba0 ab90 f4ff");
354    }
355
356    //
357    // https://tools.ietf.org/html/rfc7541#appendix-C.4.2
358    //
359    @Test
360    public void read_2() {
361        read("a8eb 1064 9cbf", "no-cache");
362    }
363
364    @Test
365    public void write_2() {
366        write("no-cache", "a8eb 1064 9cbf");
367    }
368
369    //
370    // https://tools.ietf.org/html/rfc7541#appendix-C.4.3
371    //
372    @Test
373    public void read_3() {
374        read("25a8 49e9 5ba9 7d7f", "custom-key");
375    }
376
377    @Test
378    public void write_3() {
379        write("custom-key", "25a8 49e9 5ba9 7d7f");
380    }
381
382    //
383    // https://tools.ietf.org/html/rfc7541#appendix-C.4.3
384    //
385    @Test
386    public void read_4() {
387        read("25a8 49e9 5bb8 e8b4 bf", "custom-value");
388    }
389
390    @Test
391    public void write_4() {
392        write("custom-value", "25a8 49e9 5bb8 e8b4 bf");
393    }
394
395    //
396    // https://tools.ietf.org/html/rfc7541#appendix-C.6.1
397    //
398    @Test
399    public void read_5() {
400        read("6402", "302");
401    }
402
403    @Test
404    public void write_5() {
405        write("302", "6402");
406    }
407
408    //
409    // https://tools.ietf.org/html/rfc7541#appendix-C.6.1
410    //
411    @Test
412    public void read_6() {
413        read("aec3 771a 4b", "private");
414    }
415
416    @Test
417    public void write_6() {
418        write("private", "aec3 771a 4b");
419    }
420
421    //
422    // https://tools.ietf.org/html/rfc7541#appendix-C.6.1
423    //
424    @Test
425    public void read_7() {
426        read("d07a be94 1054 d444 a820 0595 040b 8166 e082 a62d 1bff",
427                "Mon, 21 Oct 2013 20:13:21 GMT");
428    }
429
430    @Test
431    public void write_7() {
432        write("Mon, 21 Oct 2013 20:13:21 GMT",
433                "d07a be94 1054 d444 a820 0595 040b 8166 e082 a62d 1bff");
434    }
435
436    //
437    // https://tools.ietf.org/html/rfc7541#appendix-C.6.1
438    //
439    @Test
440    public void read_8() {
441        read("9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 d3",
442                "https://www.example.com");
443    }
444
445    @Test
446    public void write_8() {
447        write("https://www.example.com",
448                "9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 d3");
449    }
450
451    //
452    // https://tools.ietf.org/html/rfc7541#appendix-C.6.2
453    //
454    @Test
455    public void read_9() {
456        read("640e ff", "307");
457    }
458
459    @Test
460    public void write_9() {
461        write("307", "640e ff");
462    }
463
464    //
465    // https://tools.ietf.org/html/rfc7541#appendix-C.6.3
466    //
467    @Test
468    public void read_10() {
469        read("d07a be94 1054 d444 a820 0595 040b 8166 e084 a62d 1bff",
470                "Mon, 21 Oct 2013 20:13:22 GMT");
471    }
472
473    @Test
474    public void write_10() {
475        write("Mon, 21 Oct 2013 20:13:22 GMT",
476                "d07a be94 1054 d444 a820 0595 040b 8166 e084 a62d 1bff");
477    }
478
479    //
480    // https://tools.ietf.org/html/rfc7541#appendix-C.6.3
481    //
482    @Test
483    public void read_11() {
484        read("9bd9 ab", "gzip");
485    }
486
487    @Test
488    public void write_11() {
489        write("gzip", "9bd9 ab");
490    }
491
492    //
493    // https://tools.ietf.org/html/rfc7541#appendix-C.6.3
494    //
495    @Test
496    public void read_12() {
497        read("94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 " +
498             "d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 " +
499             "3160 65c0 03ed 4ee5 b106 3d50 07",
500             "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1");
501    }
502
503    @Test
504    public void test_trie_has_no_empty_nodes() {
505        Huffman.Node root = Huffman.INSTANCE.getRoot();
506        Stack<Huffman.Node> backlog = new Stack<>();
507        backlog.push(root);
508        while (!backlog.isEmpty()) {
509            Huffman.Node n = backlog.pop();
510            // The only type of nodes we couldn't possibly catch during
511            // construction is an empty node: no children and no char
512            if (n.left != null) {
513                backlog.push(n.left);
514            }
515            if (n.right != null) {
516                backlog.push(n.right);
517            }
518            assertFalse(!n.charIsSet && n.left == null && n.right == null,
519                    "Empty node in the trie");
520        }
521    }
522
523    @Test
524    public void test_trie_has_257_nodes() {
525        int count = 0;
526        Huffman.Node root = Huffman.INSTANCE.getRoot();
527        Stack<Huffman.Node> backlog = new Stack<>();
528        backlog.push(root);
529        while (!backlog.isEmpty()) {
530            Huffman.Node n = backlog.pop();
531            if (n.left != null) {
532                backlog.push(n.left);
533            }
534            if (n.right != null) {
535                backlog.push(n.right);
536            }
537            if (n.isLeaf()) {
538                count++;
539            }
540        }
541        assertEquals(count, 257);
542    }
543
544    @Test
545    public void cant_encode_outside_byte() {
546        TestHelper.Block<Object> coding =
547                () -> new Huffman.Writer()
548                        .from(((char) 256) + "", 0, 1)
549                        .write(ByteBuffer.allocate(1));
550        RuntimeException e =
551                TestHelper.assertVoidThrows(RuntimeException.class, coding);
552        TestHelper.assertExceptionMessageContains(e, "char");
553    }
554
555    private static void read(String hexdump, String decoded) {
556        ByteBuffer source = SpecHelper.toBytes(hexdump);
557        Appendable actual = new StringBuilder();
558        new Huffman.Reader().read(source, actual, true);
559        assertEquals(actual.toString(), decoded);
560    }
561
562    private static void write(String decoded, String hexdump) {
563        int n = Huffman.INSTANCE.lengthOf(decoded);
564        ByteBuffer destination = ByteBuffer.allocate(n); // Extra margin (1) to test having more bytes in the destination than needed is ok
565        Huffman.Writer writer = new Huffman.Writer();
566        BuffersTestingKit.forEachSplit(destination, byteBuffers -> {
567            writer.from(decoded, 0, decoded.length());
568            boolean written = false;
569            for (ByteBuffer b : byteBuffers) {
570                int pos = b.position();
571                written = writer.write(b);
572                b.position(pos);
573            }
574            assertTrue(written);
575            ByteBuffer concated = BuffersTestingKit.concat(byteBuffers);
576            String actual = SpecHelper.toHexdump(concated);
577            assertEquals(actual, hexdump);
578            writer.reset();
579        });
580    }
581
582    //
583    // It's not very pretty, yes I know that
584    //
585    //      hex:
586    //
587    //      |31|30|...|N-1|...|01|00|
588    //                  \        /
589    //                  codeLength
590    //
591    //      hex <<= 32 - codeLength; (align to MSB):
592    //
593    //      |31|30|...|32-N|...|01|00|
594    //        \        /
595    //        codeLength
596    //
597    //      EOS:
598    //
599    //      |31|30|...|M-1|...|01|00|
600    //                   \        /
601    //                   eosLength
602    //
603    //      eos <<= 32 - eosLength; (align to MSB):
604    //
605    //      pad with MSBs of EOS:
606    //
607    //      |31|30|...|32-N|32-N-1|...|01|00|
608    //                     |    32|...|
609    //
610    //      Finally, split into byte[]
611    //
612    private byte[] intToBytes(int eos, int eosLength, int hex, int codeLength) {
613        hex <<= 32 - codeLength;
614        eos >>= codeLength - (32 - eosLength);
615        hex |= eos;
616        int n = (int) Math.ceil(codeLength / 8.0);
617        byte[] result = new byte[n];
618        for (int i = 0; i < n; i++) {
619            result[i] = (byte) (hex >> (32 - 8 * (i + 1)));
620        }
621        return result;
622    }
623}
624