1 //
2 // ========================================================================
3 // Copyright (c) 1995-2016 Mort Bay Consulting Pty. Ltd.
4 // ------------------------------------------------------------------------
5 // All rights reserved. This program and the accompanying materials
6 // are made available under the terms of the Eclipse Public License v1.0
7 // and Apache License v2.0 which accompanies this distribution.
8 //
9 // The Eclipse Public License is available at
10 // http://www.eclipse.org/legal/epl-v10.html
11 //
12 // The Apache License v2.0 is available at
13 // http://www.opensource.org/licenses/apache2.0.php
14 //
15 // You may elect to redistribute this code under either of these licenses.
16 // ========================================================================
17 //
18
19 package org.eclipse.jetty.http2.hpack;
20
21 import java.nio.ByteBuffer;
22
23 public class Huffman
24 {
25
26 // Appendix C: Huffman Codes
27 // http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-12#appendix-C
28 static final int[][] CODES =
29 {
30 /* ( 0) |11111111|11000 */ {0x1ff8,13},
31 /* ( 1) |11111111|11111111|1011000 */ {0x7fffd8,23},
32 /* ( 2) |11111111|11111111|11111110|0010 */ {0xfffffe2,28},
33 /* ( 3) |11111111|11111111|11111110|0011 */ {0xfffffe3,28},
34 /* ( 4) |11111111|11111111|11111110|0100 */ {0xfffffe4,28},
35 /* ( 5) |11111111|11111111|11111110|0101 */ {0xfffffe5,28},
36 /* ( 6) |11111111|11111111|11111110|0110 */ {0xfffffe6,28},
37 /* ( 7) |11111111|11111111|11111110|0111 */ {0xfffffe7,28},
38 /* ( 8) |11111111|11111111|11111110|1000 */ {0xfffffe8,28},
39 /* ( 9) |11111111|11111111|11101010 */ {0xffffea,24},
40 /* ( 10) |11111111|11111111|11111111|111100 */ {0x3ffffffc,30},
41 /* ( 11) |11111111|11111111|11111110|1001 */ {0xfffffe9,28},
42 /* ( 12) |11111111|11111111|11111110|1010 */ {0xfffffea,28},
43 /* ( 13) |11111111|11111111|11111111|111101 */ {0x3ffffffd,30},
44 /* ( 14) |11111111|11111111|11111110|1011 */ {0xfffffeb,28},
45 /* ( 15) |11111111|11111111|11111110|1100 */ {0xfffffec,28},
46 /* ( 16) |11111111|11111111|11111110|1101 */ {0xfffffed,28},
47 /* ( 17) |11111111|11111111|11111110|1110 */ {0xfffffee,28},
48 /* ( 18) |11111111|11111111|11111110|1111 */ {0xfffffef,28},
49 /* ( 19) |11111111|11111111|11111111|0000 */ {0xffffff0,28},
50 /* ( 20) |11111111|11111111|11111111|0001 */ {0xffffff1,28},
51 /* ( 21) |11111111|11111111|11111111|0010 */ {0xffffff2,28},
52 /* ( 22) |11111111|11111111|11111111|111110 */ {0x3ffffffe,30},
53 /* ( 23) |11111111|11111111|11111111|0011 */ {0xffffff3,28},
54 /* ( 24) |11111111|11111111|11111111|0100 */ {0xffffff4,28},
55 /* ( 25) |11111111|11111111|11111111|0101 */ {0xffffff5,28},
56 /* ( 26) |11111111|11111111|11111111|0110 */ {0xffffff6,28},
57 /* ( 27) |11111111|11111111|11111111|0111 */ {0xffffff7,28},
58 /* ( 28) |11111111|11111111|11111111|1000 */ {0xffffff8,28},
59 /* ( 29) |11111111|11111111|11111111|1001 */ {0xffffff9,28},
60 /* ( 30) |11111111|11111111|11111111|1010 */ {0xffffffa,28},
61 /* ( 31) |11111111|11111111|11111111|1011 */ {0xffffffb,28},
62 /*' ' ( 32) |010100 */ {0x14, 6},
63 /*'!' ( 33) |11111110|00 */ {0x3f8,10},
64 /*'"' ( 34) |11111110|01 */ {0x3f9,10},
65 /*'#' ( 35) |11111111|1010 */ {0xffa,12},
66 /*'$' ( 36) |11111111|11001 */ {0x1ff9,13},
67 /*'%' ( 37) |010101 */ {0x15, 6},
68 /*'&' ( 38) |11111000 */ {0xf8, 8},
69 /*''' ( 39) |11111111|010 */ {0x7fa,11},
70 /*'(' ( 40) |11111110|10 */ {0x3fa,10},
71 /*')' ( 41) |11111110|11 */ {0x3fb,10},
72 /*'*' ( 42) |11111001 */ {0xf9, 8},
73 /*'+' ( 43) |11111111|011 */ {0x7fb,11},
74 /*',' ( 44) |11111010 */ {0xfa, 8},
75 /*'-' ( 45) |010110 */ {0x16, 6},
76 /*'.' ( 46) |010111 */ {0x17, 6},
77 /*'/' ( 47) |011000 */ {0x18, 6},
78 /*'0' ( 48) |00000 */ {0x0, 5},
79 /*'1' ( 49) |00001 */ {0x1, 5},
80 /*'2' ( 50) |00010 */ {0x2, 5},
81 /*'3' ( 51) |011001 */ {0x19, 6},
82 /*'4' ( 52) |011010 */ {0x1a, 6},
83 /*'5' ( 53) |011011 */ {0x1b, 6},
84 /*'6' ( 54) |011100 */ {0x1c, 6},
85 /*'7' ( 55) |011101 */ {0x1d, 6},
86 /*'8' ( 56) |011110 */ {0x1e, 6},
87 /*'9' ( 57) |011111 */ {0x1f, 6},
88 /*':' ( 58) |1011100 */ {0x5c, 7},
89 /*';' ( 59) |11111011 */ {0xfb, 8},
90 /*'<' ( 60) |11111111|1111100 */ {0x7ffc,15},
91 /*'=' ( 61) |100000 */ {0x20, 6},
92 /*'>' ( 62) |11111111|1011 */ {0xffb,12},
93 /*'?' ( 63) |11111111|00 */ {0x3fc,10},
94 /*'@' ( 64) |11111111|11010 */ {0x1ffa,13},
95 /*'A' ( 65) |100001 */ {0x21, 6},
96 /*'B' ( 66) |1011101 */ {0x5d, 7},
97 /*'C' ( 67) |1011110 */ {0x5e, 7},
98 /*'D' ( 68) |1011111 */ {0x5f, 7},
99 /*'E' ( 69) |1100000 */ {0x60, 7},
100 /*'F' ( 70) |1100001 */ {0x61, 7},
101 /*'G' ( 71) |1100010 */ {0x62, 7},
102 /*'H' ( 72) |1100011 */ {0x63, 7},
103 /*'I' ( 73) |1100100 */ {0x64, 7},
104 /*'J' ( 74) |1100101 */ {0x65, 7},
105 /*'K' ( 75) |1100110 */ {0x66, 7},
106 /*'L' ( 76) |1100111 */ {0x67, 7},
107 /*'M' ( 77) |1101000 */ {0x68, 7},
108 /*'N' ( 78) |1101001 */ {0x69, 7},
109 /*'O' ( 79) |1101010 */ {0x6a, 7},
110 /*'P' ( 80) |1101011 */ {0x6b, 7},
111 /*'Q' ( 81) |1101100 */ {0x6c, 7},
112 /*'R' ( 82) |1101101 */ {0x6d, 7},
113 /*'S' ( 83) |1101110 */ {0x6e, 7},
114 /*'T' ( 84) |1101111 */ {0x6f, 7},
115 /*'U' ( 85) |1110000 */ {0x70, 7},
116 /*'V' ( 86) |1110001 */ {0x71, 7},
117 /*'W' ( 87) |1110010 */ {0x72, 7},
118 /*'X' ( 88) |11111100 */ {0xfc, 8},
119 /*'Y' ( 89) |1110011 */ {0x73, 7},
120 /*'Z' ( 90) |11111101 */ {0xfd, 8},
121 /*'[' ( 91) |11111111|11011 */ {0x1ffb,13},
122 /*'\' ( 92) |11111111|11111110|000 */ {0x7fff0,19},
123 /*']' ( 93) |11111111|11100 */ {0x1ffc,13},
124 /*'^' ( 94) |11111111|111100 */ {0x3ffc,14},
125 /*'_' ( 95) |100010 */ {0x22, 6},
126 /*'`' ( 96) |11111111|1111101 */ {0x7ffd,15},
127 /*'a' ( 97) |00011 */ {0x3, 5},
128 /*'b' ( 98) |100011 */ {0x23, 6},
129 /*'c' ( 99) |00100 */ {0x4, 5},
130 /*'d' (100) |100100 */ {0x24, 6},
131 /*'e' (101) |00101 */ {0x5, 5},
132 /*'f' (102) |100101 */ {0x25, 6},
133 /*'g' (103) |100110 */ {0x26, 6},
134 /*'h' (104) |100111 */ {0x27, 6},
135 /*'i' (105) |00110 */ {0x6, 5},
136 /*'j' (106) |1110100 */ {0x74, 7},
137 /*'k' (107) |1110101 */ {0x75, 7},
138 /*'l' (108) |101000 */ {0x28, 6},
139 /*'m' (109) |101001 */ {0x29, 6},
140 /*'n' (110) |101010 */ {0x2a, 6},
141 /*'o' (111) |00111 */ {0x7, 5},
142 /*'p' (112) |101011 */ {0x2b, 6},
143 /*'q' (113) |1110110 */ {0x76, 7},
144 /*'r' (114) |101100 */ {0x2c, 6},
145 /*'s' (115) |01000 */ {0x8, 5},
146 /*'t' (116) |01001 */ {0x9, 5},
147 /*'u' (117) |101101 */ {0x2d, 6},
148 /*'v' (118) |1110111 */ {0x77, 7},
149 /*'w' (119) |1111000 */ {0x78, 7},
150 /*'x' (120) |1111001 */ {0x79, 7},
151 /*'y' (121) |1111010 */ {0x7a, 7},
152 /*'z' (122) |1111011 */ {0x7b, 7},
153 /*'{' (123) |11111111|1111110 */ {0x7ffe,15},
154 /*'|' (124) |11111111|100 */ {0x7fc,11},
155 /*'}' (125) |11111111|111101 */ {0x3ffd,14},
156 /*'~' (126) |11111111|11101 */ {0x1ffd,13},
157 /* (127) |11111111|11111111|11111111|1100 */ {0xffffffc,28},
158 /* (128) |11111111|11111110|0110 */ {0xfffe6,20},
159 /* (129) |11111111|11111111|010010 */ {0x3fffd2,22},
160 /* (130) |11111111|11111110|0111 */ {0xfffe7,20},
161 /* (131) |11111111|11111110|1000 */ {0xfffe8,20},
162 /* (132) |11111111|11111111|010011 */ {0x3fffd3,22},
163 /* (133) |11111111|11111111|010100 */ {0x3fffd4,22},
164 /* (134) |11111111|11111111|010101 */ {0x3fffd5,22},
165 /* (135) |11111111|11111111|1011001 */ {0x7fffd9,23},
166 /* (136) |11111111|11111111|010110 */ {0x3fffd6,22},
167 /* (137) |11111111|11111111|1011010 */ {0x7fffda,23},
168 /* (138) |11111111|11111111|1011011 */ {0x7fffdb,23},
169 /* (139) |11111111|11111111|1011100 */ {0x7fffdc,23},
170 /* (140) |11111111|11111111|1011101 */ {0x7fffdd,23},
171 /* (141) |11111111|11111111|1011110 */ {0x7fffde,23},
172 /* (142) |11111111|11111111|11101011 */ {0xffffeb,24},
173 /* (143) |11111111|11111111|1011111 */ {0x7fffdf,23},
174 /* (144) |11111111|11111111|11101100 */ {0xffffec,24},
175 /* (145) |11111111|11111111|11101101 */ {0xffffed,24},
176 /* (146) |11111111|11111111|010111 */ {0x3fffd7,22},
177 /* (147) |11111111|11111111|1100000 */ {0x7fffe0,23},
178 /* (148) |11111111|11111111|11101110 */ {0xffffee,24},
179 /* (149) |11111111|11111111|1100001 */ {0x7fffe1,23},
180 /* (150) |11111111|11111111|1100010 */ {0x7fffe2,23},
181 /* (151) |11111111|11111111|1100011 */ {0x7fffe3,23},
182 /* (152) |11111111|11111111|1100100 */ {0x7fffe4,23},
183 /* (153) |11111111|11111110|11100 */ {0x1fffdc,21},
184 /* (154) |11111111|11111111|011000 */ {0x3fffd8,22},
185 /* (155) |11111111|11111111|1100101 */ {0x7fffe5,23},
186 /* (156) |11111111|11111111|011001 */ {0x3fffd9,22},
187 /* (157) |11111111|11111111|1100110 */ {0x7fffe6,23},
188 /* (158) |11111111|11111111|1100111 */ {0x7fffe7,23},
189 /* (159) |11111111|11111111|11101111 */ {0xffffef,24},
190 /* (160) |11111111|11111111|011010 */ {0x3fffda,22},
191 /* (161) |11111111|11111110|11101 */ {0x1fffdd,21},
192 /* (162) |11111111|11111110|1001 */ {0xfffe9,20},
193 /* (163) |11111111|11111111|011011 */ {0x3fffdb,22},
194 /* (164) |11111111|11111111|011100 */ {0x3fffdc,22},
195 /* (165) |11111111|11111111|1101000 */ {0x7fffe8,23},
196 /* (166) |11111111|11111111|1101001 */ {0x7fffe9,23},
197 /* (167) |11111111|11111110|11110 */ {0x1fffde,21},
198 /* (168) |11111111|11111111|1101010 */ {0x7fffea,23},
199 /* (169) |11111111|11111111|011101 */ {0x3fffdd,22},
200 /* (170) |11111111|11111111|011110 */ {0x3fffde,22},
201 /* (171) |11111111|11111111|11110000 */ {0xfffff0,24},
202 /* (172) |11111111|11111110|11111 */ {0x1fffdf,21},
203 /* (173) |11111111|11111111|011111 */ {0x3fffdf,22},
204 /* (174) |11111111|11111111|1101011 */ {0x7fffeb,23},
205 /* (175) |11111111|11111111|1101100 */ {0x7fffec,23},
206 /* (176) |11111111|11111111|00000 */ {0x1fffe0,21},
207 /* (177) |11111111|11111111|00001 */ {0x1fffe1,21},
208 /* (178) |11111111|11111111|100000 */ {0x3fffe0,22},
209 /* (179) |11111111|11111111|00010 */ {0x1fffe2,21},
210 /* (180) |11111111|11111111|1101101 */ {0x7fffed,23},
211 /* (181) |11111111|11111111|100001 */ {0x3fffe1,22},
212 /* (182) |11111111|11111111|1101110 */ {0x7fffee,23},
213 /* (183) |11111111|11111111|1101111 */ {0x7fffef,23},
214 /* (184) |11111111|11111110|1010 */ {0xfffea,20},
215 /* (185) |11111111|11111111|100010 */ {0x3fffe2,22},
216 /* (186) |11111111|11111111|100011 */ {0x3fffe3,22},
217 /* (187) |11111111|11111111|100100 */ {0x3fffe4,22},
218 /* (188) |11111111|11111111|1110000 */ {0x7ffff0,23},
219 /* (189) |11111111|11111111|100101 */ {0x3fffe5,22},
220 /* (190) |11111111|11111111|100110 */ {0x3fffe6,22},
221 /* (191) |11111111|11111111|1110001 */ {0x7ffff1,23},
222 /* (192) |11111111|11111111|11111000|00 */ {0x3ffffe0,26},
223 /* (193) |11111111|11111111|11111000|01 */ {0x3ffffe1,26},
224 /* (194) |11111111|11111110|1011 */ {0xfffeb,20},
225 /* (195) |11111111|11111110|001 */ {0x7fff1,19},
226 /* (196) |11111111|11111111|100111 */ {0x3fffe7,22},
227 /* (197) |11111111|11111111|1110010 */ {0x7ffff2,23},
228 /* (198) |11111111|11111111|101000 */ {0x3fffe8,22},
229 /* (199) |11111111|11111111|11110110|0 */ {0x1ffffec,25},
230 /* (200) |11111111|11111111|11111000|10 */ {0x3ffffe2,26},
231 /* (201) |11111111|11111111|11111000|11 */ {0x3ffffe3,26},
232 /* (202) |11111111|11111111|11111001|00 */ {0x3ffffe4,26},
233 /* (203) |11111111|11111111|11111011|110 */ {0x7ffffde,27},
234 /* (204) |11111111|11111111|11111011|111 */ {0x7ffffdf,27},
235 /* (205) |11111111|11111111|11111001|01 */ {0x3ffffe5,26},
236 /* (206) |11111111|11111111|11110001 */ {0xfffff1,24},
237 /* (207) |11111111|11111111|11110110|1 */ {0x1ffffed,25},
238 /* (208) |11111111|11111110|010 */ {0x7fff2,19},
239 /* (209) |11111111|11111111|00011 */ {0x1fffe3,21},
240 /* (210) |11111111|11111111|11111001|10 */ {0x3ffffe6,26},
241 /* (211) |11111111|11111111|11111100|000 */ {0x7ffffe0,27},
242 /* (212) |11111111|11111111|11111100|001 */ {0x7ffffe1,27},
243 /* (213) |11111111|11111111|11111001|11 */ {0x3ffffe7,26},
244 /* (214) |11111111|11111111|11111100|010 */ {0x7ffffe2,27},
245 /* (215) |11111111|11111111|11110010 */ {0xfffff2,24},
246 /* (216) |11111111|11111111|00100 */ {0x1fffe4,21},
247 /* (217) |11111111|11111111|00101 */ {0x1fffe5,21},
248 /* (218) |11111111|11111111|11111010|00 */ {0x3ffffe8,26},
249 /* (219) |11111111|11111111|11111010|01 */ {0x3ffffe9,26},
250 /* (220) |11111111|11111111|11111111|1101 */ {0xffffffd,28},
251 /* (221) |11111111|11111111|11111100|011 */ {0x7ffffe3,27},
252 /* (222) |11111111|11111111|11111100|100 */ {0x7ffffe4,27},
253 /* (223) |11111111|11111111|11111100|101 */ {0x7ffffe5,27},
254 /* (224) |11111111|11111110|1100 */ {0xfffec,20},
255 /* (225) |11111111|11111111|11110011 */ {0xfffff3,24},
256 /* (226) |11111111|11111110|1101 */ {0xfffed,20},
257 /* (227) |11111111|11111111|00110 */ {0x1fffe6,21},
258 /* (228) |11111111|11111111|101001 */ {0x3fffe9,22},
259 /* (229) |11111111|11111111|00111 */ {0x1fffe7,21},
260 /* (230) |11111111|11111111|01000 */ {0x1fffe8,21},
261 /* (231) |11111111|11111111|1110011 */ {0x7ffff3,23},
262 /* (232) |11111111|11111111|101010 */ {0x3fffea,22},
263 /* (233) |11111111|11111111|101011 */ {0x3fffeb,22},
264 /* (234) |11111111|11111111|11110111|0 */ {0x1ffffee,25},
265 /* (235) |11111111|11111111|11110111|1 */ {0x1ffffef,25},
266 /* (236) |11111111|11111111|11110100 */ {0xfffff4,24},
267 /* (237) |11111111|11111111|11110101 */ {0xfffff5,24},
268 /* (238) |11111111|11111111|11111010|10 */ {0x3ffffea,26},
269 /* (239) |11111111|11111111|1110100 */ {0x7ffff4,23},
270 /* (240) |11111111|11111111|11111010|11 */ {0x3ffffeb,26},
271 /* (241) |11111111|11111111|11111100|110 */ {0x7ffffe6,27},
272 /* (242) |11111111|11111111|11111011|00 */ {0x3ffffec,26},
273 /* (243) |11111111|11111111|11111011|01 */ {0x3ffffed,26},
274 /* (244) |11111111|11111111|11111100|111 */ {0x7ffffe7,27},
275 /* (245) |11111111|11111111|11111101|000 */ {0x7ffffe8,27},
276 /* (246) |11111111|11111111|11111101|001 */ {0x7ffffe9,27},
277 /* (247) |11111111|11111111|11111101|010 */ {0x7ffffea,27},
278 /* (248) |11111111|11111111|11111101|011 */ {0x7ffffeb,27},
279 /* (249) |11111111|11111111|11111111|1110 */ {0xffffffe,28},
280 /* (250) |11111111|11111111|11111101|100 */ {0x7ffffec,27},
281 /* (251) |11111111|11111111|11111101|101 */ {0x7ffffed,27},
282 /* (252) |11111111|11111111|11111101|110 */ {0x7ffffee,27},
283 /* (253) |11111111|11111111|11111101|111 */ {0x7ffffef,27},
284 /* (254) |11111111|11111111|11111110|000 */ {0x7fffff0,27},
285 /* (255) |11111111|11111111|11111011|10 */ {0x3ffffee,26},
286 /*EOS (256) |11111111|11111111|11111111|111111 */ {0x3fffffff,30},
287 };
288
289 static final int[][] LCCODES = new int[CODES.length][];
290
291 // Huffman decode tree stored in a flattened char array for good
292 // locality of reference.
293 static final char[] tree;
294 static final char[] rowsym;
295 static final byte[] rowbits;
296
297 // Build the Huffman lookup tree and LC TABLE
298 static
299 {
300 System.arraycopy(CODES,0,LCCODES,0,CODES.length);
301 for (int i='A';i<='Z';i++)
302 LCCODES[i]=LCCODES['a'+i-'A'];
303
304 int r=0;
305 for (int i=0;i<CODES.length;i++)
306 r+=(CODES[i][1]+7)/8;
307 tree=new char[r*256];
308 rowsym=new char[r];
309 rowbits=new byte[r];
310
311 r=0;
312 for (int sym = 0; sym < CODES.length; sym++)
313 {
314 int code = CODES[sym][0];
315 int len = CODES[sym][1];
316
317 int current = 0;
318
319 while (len > 8)
320 {
321 len -= 8;
322 int i = ((code >>> len) & 0xFF);
323
324 int t=current*256+i;
325 current = tree[t];
326 if (current == 0)
327 {
328 tree[t] = (char)++r;
329 current=r;
330 }
331 }
332
333 int terminal = ++r;
334 rowsym[r]=(char)sym;
335 int b = len & 0x07;
336 int terminalBits = b == 0?8:b;
337
338 rowbits[r]=(byte)terminalBits;
339 int shift = 8 - len;
340 int start = current*256 + ((code << shift) & 0xFF);
341 int end = start + (1<<shift);
342 for (int i = start; i < end; i++)
343 tree[i]=(char)terminal;
344 }
345 }
346
347 public static String decode(ByteBuffer buffer)
348 {
349 return decode(buffer,buffer.remaining());
350 }
351
352 public static String decode(ByteBuffer buffer,int length)
353 {
354 StringBuilder out = new StringBuilder(length*2);
355 int node = 0;
356 int current = 0;
357 int bits = 0;
358
359 byte[] array = buffer.array();
360 int position=buffer.position();
361 int start=buffer.arrayOffset()+position;
362 int end=start+length;
363 buffer.position(position+length);
364
365 for (int i=start; i<end; i++)
366 {
367 int b = array[i]&0xFF;
368 current = (current << 8) | b;
369 bits += 8;
370 while (bits >= 8)
371 {
372 int c = (current >>> (bits - 8)) & 0xFF;
373 node = tree[node*256+c];
374 if (rowbits[node]!=0)
375 {
376 // terminal node
377 out.append(rowsym[node]);
378 bits -= rowbits[node];
379 node = 0;
380 }
381 else
382 {
383 // non-terminal node
384 bits -= 8;
385 }
386 }
387 }
388
389 while (bits > 0)
390 {
391 int c = (current << (8 - bits)) & 0xFF;
392 node = tree[node*256+c];
393 if (rowbits[node]==0 || rowbits[node] > bits)
394 break;
395
396 if (rowbits[node]==0)
397 throw new IllegalStateException();
398
399 out.append(rowsym[node]);
400 bits -= rowbits[node];
401 node = 0;
402 }
403
404 return out.toString();
405 }
406
407 public static int octetsNeeded(String s)
408 {
409 return octetsNeeded(CODES,s);
410 }
411
412 public static void encode(ByteBuffer buffer,String s)
413 {
414 encode(CODES,buffer,s);
415 }
416
417 public static int octetsNeededLC(String s)
418 {
419 return octetsNeeded(LCCODES,s);
420 }
421
422 public static void encodeLC(ByteBuffer buffer, String s)
423 {
424 encode(LCCODES,buffer,s);
425 }
426
427 private static int octetsNeeded(final int[][] table,String s)
428 {
429 int needed=0;
430 int len = s.length();
431 for (int i=0;i<len;i++)
432 {
433 char c=s.charAt(i);
434 if (c>=128 || c<' ')
435 throw new IllegalArgumentException();
436 needed += table[c][1];
437 }
438
439 return (needed+7) / 8;
440 }
441
442 private static void encode(final int[][] table,ByteBuffer buffer,String s)
443 {
444 long current = 0;
445 int n = 0;
446
447 byte[] array = buffer.array();
448 int p=buffer.arrayOffset()+buffer.position();
449
450 int len = s.length();
451 for (int i=0;i<len;i++)
452 {
453 char c=s.charAt(i);
454 if (c>=128 || c<' ')
455 throw new IllegalArgumentException();
456 int code = table[c][0];
457 int bits = table[c][1];
458
459 current <<= bits;
460 current |= code;
461 n += bits;
462
463 while (n >= 8)
464 {
465 n -= 8;
466 array[p++]=(byte)(current >> n);
467 }
468 }
469
470 if (n > 0)
471 {
472 current <<= (8 - n);
473 current |= (0xFF >>> n);
474 array[p++]=(byte)current;
475 }
476
477 buffer.position(p-buffer.arrayOffset());
478 }
479
480 }