1 /**
2  * Huffman Tests
3  * 
4  * Copyright:
5  * (C) 2012-2015 Tatsuhiro Tsujikawa
6  * (C) 2014-2015 Etienne Cimon
7  *
8  * License: 
9  * Distributed under the terms of the MIT license with an additional section 1.2 of the curl/libcurl project. 
10  * Consult the provided LICENSE.md file for details
11  */
12 module libhttp2.huffman_tests;
13 
14 import libhttp2.constants;
15 static if (TEST_ALL):
16 
17 import libhttp2.buffers;
18 import libhttp2.huffman;
19 import libhttp2.deflater;
20 import libhttp2.inflater;
21 import libhttp2.types;
22 import libhttp2.frame;
23 import libhttp2.helpers;
24 import libhttp2.tests;
25 import core.stdc.string : memcmp, memset, memcpy;
26 import std.conv : to;
27 
28 void test_hd_deflate() {
29 	Deflater deflater = Deflater(DEFAULT_MAX_DEFLATE_BUFFER_SIZE);
30 	Inflater inflater = Inflater(true);
31 	HeaderField[] hfa1 = [HeaderField(":path", "/my-example/index.html"), HeaderField(":scheme", "https"), HeaderField("hello", "world")];
32 	HeaderField[] hfa2 = [HeaderField(":path", "/script.js"), HeaderField(":scheme", "https")];
33 	HeaderField[] hfa3 = [HeaderField("cookie", "k1=v1"), HeaderField("cookie", "k2=v2"), HeaderField("via", "proxy")];
34 	HeaderField[] hfa4 = [HeaderField(":path", "/style.css"), HeaderField("cookie", "k1=v1"), HeaderField("cookie", "k1=v1")];
35 	HeaderField[] hfa5 = [HeaderField(":path", "/style.css"), HeaderField("x-nghttp2", "")];
36 	Buffers bufs = framePackBuffers();
37 	size_t blocklen;
38 	HeaderFields output;
39 	ErrorCode rv;
40 
41 	rv = deflater.deflate(bufs, hfa1);
42 	blocklen = bufs.length;
43 	assert(0 == rv);
44 	assert(blocklen > 0);
45 	assert(blocklen == output.inflate(inflater, bufs, 0));
46 	
47 	assert(3 == output.length);
48 	assert(hfa1.equals(output[0 .. 3]));
49 	
50 	output.reset();
51 	bufs.reset();
52 	
53 	/* Second headers */
54 	rv = deflater.deflate(bufs, hfa2);
55 	blocklen = bufs.length;
56 	
57 	assert(0 == rv);
58 	assert(blocklen > 0);
59 	assert(blocklen == output.inflate(inflater, bufs, 0));
60 	
61 	assert(2 == output.length);
62 	assert(hfa2.equals(output[0 .. 2]));
63 	
64 	output.reset();
65 	bufs.reset();
66 	
67 	/* Third headers, including same header field name, but value is not
68      the same. */
69 	rv = deflater.deflate(bufs, hfa3);
70 	blocklen = bufs.length;
71 	
72 	assert(0 == rv);
73 	assert(blocklen > 0);
74 	assert(blocklen == output.inflate(inflater, bufs, 0));
75 	
76 	assert(3 == output.length);
77 	assert(hfa3.equals(output[0 .. 3]));
78 	
79 	output.reset();
80 	bufs.reset();
81 	
82 	/* Fourth headers, including duplicate header fields. */
83 	rv = deflater.deflate(bufs, hfa4);
84 	blocklen = bufs.length;
85 	
86 	assert(0 == rv);
87 	assert(blocklen > 0);
88 	assert(blocklen == output.inflate(inflater, bufs, 0));
89 	
90 	assert(3 == output.length);
91 	assert(hfa4.equals(output[0 .. 3]));
92 	
93 	output.reset();
94 	bufs.reset();
95 	
96 	/* Fifth headers includes empty value */
97 	rv = deflater.deflate(bufs, hfa5);
98 	blocklen = bufs.length;
99 	
100 	assert(0 == rv);
101 	assert(blocklen > 0);
102 	assert(blocklen == output.inflate(inflater, bufs, 0));
103 	
104 	assert(2 == output.length);
105 	assert(hfa5.equals(output[0 .. 2]));
106 	
107 	output.reset();
108 	bufs.reset();
109 	
110 	/* Cleanup */
111 	bufs.free();
112 	inflater.free();
113 	deflater.free();
114 }
115 
116 void test_hd_deflate_same_indexed_repr() {
117 	Deflater deflater = Deflater(DEFAULT_MAX_DEFLATE_BUFFER_SIZE);
118 	Inflater inflater = Inflater(true);
119 	HeaderField[] hfa1 = [HeaderField("cookie", "alpha"), HeaderField("cookie", "alpha")];
120 	HeaderField[] hfa2 = [HeaderField("cookie", "alpha"), HeaderField("cookie", "alpha"), HeaderField("cookie", "alpha")];
121 	Buffers bufs = framePackBuffers();
122 	size_t blocklen;
123 	HeaderFields output;
124 	ErrorCode rv;
125 
126 	/* Encode 2 same headers.  Emit 1 literal reprs and 1 index repr. */
127 	rv = deflater.deflate(bufs, hfa1);
128 	blocklen = bufs.length;
129 	
130 	assert(0 == rv);
131 	assert(blocklen > 0);
132 	assert(blocklen == output.inflate(inflater, bufs, 0));
133 	
134 	assert(2 == output.length);
135 	assert(hfa1.equals(output[]));
136 	
137 	output.reset();
138 	bufs.reset();
139 	
140 	/* Encode 3 same headers.  This time, emits 3 index reprs. */
141 	rv = deflater.deflate(bufs, hfa2);
142 	blocklen = bufs.length;
143 	
144 	assert(0 == rv);
145 	assert(blocklen == 3);
146 	assert(blocklen == output.inflate(inflater, bufs, 0));
147 	
148 	assert(3 == output.length);
149 	assert(hfa2.equals(output[0 .. 3]));
150 	
151 	output.reset();
152 	bufs.reset();
153 	
154 	/* Cleanup */
155 	bufs.free();
156 	inflater.free();
157 	deflater.free();
158 }
159 
160 void test_hd_inflate_indexed() {
161 	Inflater inflater = Inflater(true);
162 	Buffers bufs = framePackBuffers();
163 	size_t blocklen;
164 	HeaderField hf = HeaderField(":path", "/");
165 	HeaderFields output;
166 
167 	bufs.add((1 << 7) | 4);
168 	
169 	blocklen = bufs.length;
170 	
171 	assert(1 == blocklen);
172 	assert(blocklen == output.inflate(inflater, bufs, 0));
173 	
174 	assert(1 == output.length);
175 	
176 	assert(hf == output.hfa_raw[0]);
177 	
178 	output.reset();
179 	bufs.reset();
180 	
181 	/* index = 0 is error */
182 	bufs.add(1 << 7);
183 	
184 	blocklen = bufs.length;
185 	
186 	assert(1 == blocklen);
187 	assert(ErrorCode.HEADER_COMP == output.inflate(inflater, bufs, 0));
188 	
189 	bufs.free();
190 	inflater.free();
191 }
192 
193 void test_hd_inflate_indname_noinc() {
194 	Inflater inflater = Inflater(true);
195 	Buffers bufs = framePackBuffers();
196 	size_t blocklen;
197 	HeaderField[] hfa = [
198 		/* Huffman */
199 		HeaderField("user-agent", "nghttp2"),
200 		/* Expecting no huffman */
201 		HeaderField("user-agent", "x")
202 	];
203 	size_t i;
204 	HeaderFields output;
205 
206 	foreach (ref hf; hfa) {
207 		assert(0 == bufs.emitIndexedNameBlock(57, hf, false));
208 		blocklen = bufs.length;
209 		
210 		assert(blocklen > 0);
211 		assert(blocklen == output.inflate(inflater, bufs, 0));
212 		assert(1 == output.length);
213 		assert(hf == output.hfa_raw[0]);
214 		assert(0 == inflater.ctx.hd_table.length);
215 		
216 		output.reset();
217 		bufs.reset();
218 	}
219 	
220 	bufs.free();
221 	inflater.free();
222 }
223 
224 void test_hd_inflate_indname_inc() {
225 	Inflater inflater = Inflater(true);
226 	Buffers bufs = framePackBuffers();
227 	size_t blocklen;
228 	HeaderField hf = HeaderField("user-agent", "nghttp2");
229 	HeaderFields output;
230 	assert(0 == bufs.emitIndexedNameBlock(57, hf, 1));
231 	blocklen = bufs.length;
232 	
233 	assert(blocklen > 0);
234 	assert(blocklen == output.inflate(inflater, bufs, 0));
235 	assert(1 == output.length);
236 	assert(hf == output.hfa_raw[0]);
237 	assert(1 == inflater.ctx.hd_table.length);
238 	assert(hf == inflater.ctx.get(static_table.length + inflater.ctx.hd_table.length - 1).hf);
239 	
240 	output.reset();
241 	bufs.free();
242 	inflater.free();
243 }
244 
245 void test_hd_inflate_indname_inc_eviction() {
246 	Inflater inflater = Inflater(true);
247 	Buffers bufs = framePackBuffers();
248 	size_t blocklen;
249 	ubyte[1024] value;
250 	memset(value.ptr, '0', value.length);
251 	HeaderFields output;
252 	HeaderField hf;
253 
254 	hf.value = cast(string)value;
255 	hf.flag = HeaderFlag.NONE;
256 
257 	assert(0 == bufs.emitIndexedNameBlock(14, hf, true));
258 	assert(0 == bufs.emitIndexedNameBlock(15, hf, true));
259 	assert(0 == bufs.emitIndexedNameBlock(16, hf, true));
260 	assert(0 == bufs.emitIndexedNameBlock(17, hf, true));
261 	
262 	blocklen = bufs.length;
263 
264 	assert(blocklen > 0);
265 	
266 	assert(blocklen == output.inflate(inflater, bufs, 0));
267 	
268 	assert(4 == output.length);
269 	assert(14 == output.hfa_raw[0].name.length);
270 	assert("accept-charset" == output.hfa_raw[0].name);
271 	assert(value.length == output.hfa_raw[0].value.length);
272 	
273 	output.reset();
274 	bufs.reset();
275 	
276 	assert(3 == inflater.ctx.hd_table.length);
277 	
278 	bufs.free();
279 	inflater.free();
280 }
281 
282 void test_hd_inflate_newname_noinc() {
283 	Inflater inflater = Inflater(true);
284 	Buffers bufs = framePackBuffers();
285 	size_t blocklen;
286 	HeaderField[] hfa = [/* Expecting huffman for both */
287 		HeaderField("my-long-content-length", "nghttp2"),
288 		/* Expecting no huffman for both */
289 		HeaderField("x", "y"),
290 		/* Huffman for key only */
291 		HeaderField("my-long-content-length", "y"),
292 		/* Huffman for value only */
293 		HeaderField("x", "nghttp2")];
294 	size_t i;
295 	HeaderFields output;
296 	
297 	foreach (ref hf; hfa) {
298 		assert(0 == bufs.emitNewNameBlock(hf, false));
299 		
300 		blocklen = bufs.length;
301 		
302 		assert(blocklen > 0);
303 		assert(blocklen == output.inflate(inflater, bufs, 0));
304 		
305 		assert(1 == output.length);
306 		assert(hf == output.hfa_raw[0]);
307 		assert(0 == inflater.ctx.hd_table.length);
308 		
309 		output.reset();
310 		bufs.reset();
311 	}
312 	
313 	bufs.free();
314 	inflater.free();
315 }
316 
317 void test_hd_inflate_newname_inc() {
318 	Inflater inflater = Inflater(true);
319 	Buffers bufs = framePackBuffers();
320 	size_t blocklen;
321 	HeaderField hf = HeaderField("x-rel", "nghttp2");
322 	HeaderFields output;
323 
324 	assert(0 == bufs.emitNewNameBlock(hf, true));
325 	
326 	blocklen = bufs.length;
327 	
328 	assert(blocklen > 0);
329 	assert(blocklen == output.inflate(inflater, bufs, 0));
330 	
331 	assert(1 == output.length);
332 	assert(hf == output.hfa_raw[0]);
333 	assert(1 == inflater.ctx.hd_table.length);
334 	assert(hf == inflater.ctx.get(static_table.length + inflater.ctx.hd_table.length - 1).hf);
335 	
336 	output.reset();
337 	bufs.free();
338 	inflater.free();
339 }
340 
341 void test_hd_inflate_clearall_inc() {
342 	Inflater inflater = Inflater(true);
343 	Buffers bufs = largeBuffers(8192);
344 	size_t blocklen;
345 	HeaderField hf;
346 	ubyte[4060] value;
347 	memset(value.ptr, '0', value.length);
348 	HeaderFields output;
349 
350 	/* Total 4097 bytes space required to hold this entry */
351 	hf.name = "alpha";
352 	hf.value = cast(string)value;
353 	hf.flag = HeaderFlag.NONE;
354 		
355 	assert(0 == bufs.emitNewNameBlock(hf, true));
356 	
357 	blocklen = bufs.length;
358 	
359 	assert(blocklen > 0);
360 	assert(blocklen == output.inflate(inflater, bufs, 0));
361 	
362 	assert(1 == output.length);
363 	assert(hf == output.hfa_raw[0]);
364 	assert(0 == inflater.ctx.hd_table.length);
365 	
366 	output.reset();
367 	
368 	/* Do it again */
369 	assert(blocklen == output.inflate(inflater, bufs, 0));
370 	
371 	assert(1 == output.length);
372 	assert(hf == output.hfa_raw[0]);
373 	assert(0 == inflater.ctx.hd_table.length);
374 	
375 	output.reset();
376 	bufs.reset();
377 	
378 	/* This time, 4096 bytes space required, which is just fits in the header table */	
379 	hf.value = hf.value[0 .. 4059];
380 	assert(0 == bufs.emitNewNameBlock(hf, true));
381 	
382 	blocklen = bufs.length;
383 	
384 	assert(blocklen > 0);
385 	assert(blocklen == output.inflate(inflater, bufs, 0));
386 	
387 	assert(1 == output.length);
388 	assert(hf == output.hfa_raw[0]);
389 	assert(1 == inflater.ctx.hd_table.length);
390 	
391 	output.reset();
392 	bufs.reset();
393 	
394 	bufs.free();
395 	inflater.free();
396 }
397 
398 void test_hd_inflate_zero_length_huffman() {
399 	Inflater inflater = Inflater(true);
400 	Buffers bufs = framePackBuffers();
401 	/* Literal header without indexing - new name */
402 	ubyte[] data = [0x40, 0x01, 0x78 /* 'x' */, 0x80];
403 	HeaderFields output;
404 
405 	bufs.add(cast(string)data);
406 	
407 	/* /\* Literal header without indexing - new name *\/ */
408 	/* ptr[0] = 0x40; */
409 	/* ptr[1] = 1; */
410 	/* ptr[2] = 'x'; */
411 	/* ptr[3] = 0x80; */
412 	
413 	
414 	assert(4 == output.inflate(inflater, bufs, 0));
415 	
416 	assert(1 == output.length);
417 	assert(1 == output.hfa_raw[0].name.length);
418 	assert('x' == output.hfa_raw[0].name[0]);
419 	assert(null == output.hfa_raw[0].value);
420 	assert(0 == output.hfa_raw[0].value.length);
421 	
422 	output.reset();
423 	bufs.free();
424 	inflater.free();
425 }
426 
427 void test_hd_ringbuf_reserve() {
428 	Deflater deflater;
429 	Inflater inflater = Inflater(true);
430 	HeaderField hf;
431 	Buffers bufs = framePackBuffers();
432 	HeaderFields output;
433 	int i;
434 	size_t rv;
435 	size_t blocklen;
436 		
437 	hf.flag = HeaderFlag.NONE;
438 	hf.name = "a";
439 	char[] value = Mem.alloc!(char[])(4);
440 	memset(value.ptr, 0, value.length);
441 	hf.value = cast(string) value;
442 	deflater = Deflater(8000);
443 	
444 	
445 	inflater.changeTableSize(8000);
446 	deflater.changeTableSize(8000);
447 	
448 	for (i = 0; i < 150; ++i) {
449 		memcpy(value.ptr, &i, i.sizeof);
450 		rv = deflater.deflate(bufs, hf);
451 		blocklen = bufs.length;
452 		
453 		assert(0 == rv);
454 		assert(blocklen > 0);
455 		
456 		assert(blocklen == output.inflate(inflater, bufs, 0));
457 		
458 		assert(1 == output.length);
459 		assert(hf == output.hfa_raw[0]);
460 		
461 		output.reset();
462 		bufs.reset();
463 	}
464 	
465 	bufs.free();
466 	inflater.free();
467 	deflater.free();
468 	
469 	Mem.free(hf.value);
470 }
471 
472 void test_hd_change_table_size() {
473 	Deflater deflater = Deflater(DEFAULT_MAX_DEFLATE_BUFFER_SIZE);
474 	Inflater inflater = Inflater(true);
475 	HeaderField[] hfa = [HeaderField("alpha", "bravo"), HeaderField("charlie", "delta")];
476 	HeaderField[] hfa2 = [HeaderField(":path", "/")];
477 	Buffers bufs = framePackBuffers();
478 	size_t rv;
479 	HeaderFields output;
480 	size_t blocklen;
481 		
482 	/* inflater changes notifies 8000 max header table size */
483 	inflater.changeTableSize(8000);
484 	deflater.changeTableSize(8000);
485 	
486 	assert(4096 == deflater.ctx.hd_table_bufsize_max);
487 	
488 	assert(8000 == inflater.ctx.hd_table_bufsize_max);
489 	assert(8000 == inflater.settings_hd_table_bufsize_max);
490 	
491 	/* This will emit encoding context update with header table size 4096 */
492 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
493 	blocklen = bufs.length;
494 	
495 	assert(0 == rv);
496 	assert(blocklen > 0);
497 	assert(2 == deflater.ctx.hd_table.length);
498 	assert(4096 == deflater.ctx.hd_table_bufsize_max);
499 	
500 	assert(blocklen == output.inflate(inflater, bufs, 0));
501 	assert(2 == inflater.ctx.hd_table.length);
502 	assert(4096 == inflater.ctx.hd_table_bufsize_max);
503 	assert(8000 == inflater.settings_hd_table_bufsize_max);
504 	
505 	output.reset();
506 	bufs.reset();
507 	
508 	/* inflater changes header table size to 1024 */
509 	inflater.changeTableSize(1024);
510 	deflater.changeTableSize(1024);
511 	
512 	assert(1024 == deflater.ctx.hd_table_bufsize_max);
513 	
514 	assert(1024 == inflater.ctx.hd_table_bufsize_max);
515 	assert(1024 == inflater.settings_hd_table_bufsize_max);
516 	
517 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
518 	blocklen = bufs.length;
519 	
520 	assert(0 == rv);
521 	assert(blocklen > 0);
522 	assert(2 == deflater.ctx.hd_table.length);
523 	assert(1024 == deflater.ctx.hd_table_bufsize_max);
524 	
525 	assert(blocklen == output.inflate(inflater, bufs, 0));
526 	assert(2 == inflater.ctx.hd_table.length);
527 	assert(1024 == inflater.ctx.hd_table_bufsize_max);
528 	assert(1024 == inflater.settings_hd_table_bufsize_max);
529 	
530 	output.reset();
531 	bufs.reset();
532 	
533 	/* inflater changes header table size to 0 */
534 	inflater.changeTableSize(0);
535 	deflater.changeTableSize(0);
536 	
537 	assert(0 == deflater.ctx.hd_table.length);
538 	assert(0 == deflater.ctx.hd_table_bufsize_max);
539 	
540 	assert(0 == inflater.ctx.hd_table.length);
541 	assert(0 == inflater.ctx.hd_table_bufsize_max);
542 	assert(0 == inflater.settings_hd_table_bufsize_max);
543 	
544 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
545 	blocklen = bufs.length;
546 	
547 	assert(0 == rv);
548 	assert(blocklen > 0);
549 	assert(0 == deflater.ctx.hd_table.length);
550 	assert(0 == deflater.ctx.hd_table_bufsize_max);
551 	
552 	assert(blocklen == output.inflate(inflater, bufs, 0));
553 	assert(0 == inflater.ctx.hd_table.length);
554 	assert(0 == inflater.ctx.hd_table_bufsize_max);
555 	assert(0 == inflater.settings_hd_table_bufsize_max);
556 	
557 	output.reset();
558 	bufs.reset();
559 	
560 	bufs.free();
561 	inflater.free();
562 	deflater.free();
563 	
564 	/* Check table buffer is expanded */
565 	bufs = framePackBuffers();
566 	
567 	deflater = Deflater(8192);
568 	inflater = Inflater(true);
569 	
570 	/* First inflater changes header table size to 8000 */
571 	inflater.changeTableSize(8000);
572 	deflater.changeTableSize(8000);
573 	
574 	assert(8000 == deflater.ctx.hd_table_bufsize_max);
575 	
576 	assert(8000 == inflater.ctx.hd_table_bufsize_max);
577 	assert(8000 == inflater.settings_hd_table_bufsize_max);
578 	
579 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
580 	blocklen = bufs.length;
581 	
582 	assert(0 == rv);
583 	assert(blocklen > 0);
584 	assert(2 == deflater.ctx.hd_table.length);
585 	assert(8000 == deflater.ctx.hd_table_bufsize_max);
586 	
587 	assert(blocklen == output.inflate(inflater, bufs, 0));
588 	assert(2 == inflater.ctx.hd_table.length);
589 	assert(8000 == inflater.ctx.hd_table_bufsize_max);
590 	assert(8000 == inflater.settings_hd_table_bufsize_max);
591 	
592 	output.reset();
593 	bufs.reset();
594 	
595 	inflater.changeTableSize(16383);
596 	deflater.changeTableSize(16383);
597 	
598 	assert(8192 == deflater.ctx.hd_table_bufsize_max);
599 	
600 	assert(16383 == inflater.ctx.hd_table_bufsize_max);
601 	assert(16383 == inflater.settings_hd_table_bufsize_max);
602 	
603 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
604 	blocklen = bufs.length;
605 	
606 	assert(0 == rv);
607 	assert(blocklen > 0);
608 	assert(2 == deflater.ctx.hd_table.length);
609 	assert(8192 == deflater.ctx.hd_table_bufsize_max);
610 	
611 	assert(blocklen == output.inflate(inflater, bufs, 0));
612 	assert(2 == inflater.ctx.hd_table.length);
613 	assert(8192 == inflater.ctx.hd_table_bufsize_max);
614 	assert(16383 == inflater.settings_hd_table_bufsize_max);
615 	
616 	output.reset();
617 	bufs.reset();
618 	
619 	/* Lastly, check the error condition */
620 	
621 	rv = bufs.emitTableSize(25600);
622 	assert(rv == 0);
623 	assert(ErrorCode.HEADER_COMP == output.inflate(inflater, bufs, 0));
624 	
625 	output.reset();
626 	bufs.reset();
627 	
628 	inflater.free();
629 	deflater.free();
630 	
631 	/* Check that encoder can handle the case where its allowable buffer
632      size is less than default size, 4096 */
633 	deflater = Deflater(1024);
634 	inflater = Inflater(true);
635 	
636 	assert(1024 == deflater.ctx.hd_table_bufsize_max);
637 	
638 	/* This emits context update with buffer size 1024 */
639 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
640 	blocklen = bufs.length;
641 	
642 	assert(0 == rv);
643 	assert(blocklen > 0);
644 	assert(2 == deflater.ctx.hd_table.length);
645 	assert(1024 == deflater.ctx.hd_table_bufsize_max);
646 	
647 	assert(blocklen == output.inflate(inflater, bufs, 0));
648 	assert(2 == inflater.ctx.hd_table.length);
649 	assert(1024 == inflater.ctx.hd_table_bufsize_max);
650 	assert(4096 == inflater.settings_hd_table_bufsize_max);
651 	
652 	output.reset();
653 	bufs.reset();
654 	
655 	inflater.free();
656 	deflater.free();
657 	
658 	/* Check that table size uint.max can be received */
659 	deflater = Deflater(uint.max);
660 	inflater = Inflater(true);
661 	
662 	inflater.changeTableSize(uint.max);
663 	deflater.changeTableSize(uint.max);
664 	
665 	rv = deflater.deflate(bufs, hfa[0 .. 2]);
666 	blocklen = bufs.length;
667 	
668 	assert(0 == rv);
669 	assert(uint.max == deflater.ctx.hd_table_bufsize_max);
670 	
671 	assert(blocklen == output.inflate(inflater, bufs, 0));
672 	assert(uint.max == inflater.ctx.hd_table_bufsize_max);
673 	assert(uint.max == inflater.settings_hd_table_bufsize_max);
674 	
675 	output.reset();
676 	bufs.reset();
677 	
678 	inflater.free();
679 	deflater.free();
680 	
681 	/* Check that context update emitted twice
682 	 */
683 	deflater = Deflater(4096);
684 	inflater = Inflater(true);
685 	
686 	inflater.changeTableSize(0);
687 	inflater.changeTableSize(3000);
688 	deflater.changeTableSize(0);
689 	deflater.changeTableSize(3000);
690 	
691 	assert(0 == deflater.min_hd_table_bufsize_max);
692 	assert(3000 == deflater.ctx.hd_table_bufsize_max);
693 	
694 	rv = deflater.deflate(bufs, hfa2[0 .. 1]);
695 	blocklen = bufs.length;
696 	
697 	assert(0 == rv);
698 	assert(3 < blocklen);
699 	assert(3000 == deflater.ctx.hd_table_bufsize_max);
700 	assert(uint.max == deflater.min_hd_table_bufsize_max);
701 	
702 	assert(blocklen == output.inflate(inflater, bufs, 0));
703 	assert(3000 == inflater.ctx.hd_table_bufsize_max);
704 	assert(3000 == inflater.settings_hd_table_bufsize_max);
705 	
706 	output.reset();
707 	
708 	inflater.free();
709 	deflater.free();
710 	
711 	bufs.free();
712 }
713 
714 void check_deflate_inflate(ref Deflater deflater, ref Inflater inflater, HeaderField[] hfa) 
715 {
716 	Buffers bufs = framePackBuffers();
717 	size_t blocklen;
718 	HeaderFields output;
719 	ErrorCode rv;
720 
721 	rv = deflater.deflate(bufs, hfa);
722 	blocklen = bufs.length;
723 	
724 	assert(0 == rv);
725 	assert(blocklen >= 0);
726 	assert(blocklen == output.inflate(inflater, bufs, 0));
727 	assert(hfa.length == output.length);
728 	assert(hfa.equals(output[]));
729 	output.reset();
730 	bufs.free();
731 }
732 
733 void test_hd_deflate_inflate() {
734 	Deflater deflater = Deflater(DEFAULT_MAX_DEFLATE_BUFFER_SIZE);
735 	Inflater inflater = Inflater(true);
736 	HeaderField[] hfa1 = [
737 		HeaderField(":status", "200 OK"),
738 		HeaderField("access-control-allow-origin", "*"),
739 		HeaderField("cache-control", "private, max-age=0, must-revalidate"),
740 		HeaderField("content-length", "76073"),
741 		HeaderField("content-type", "text/html"),
742 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
743 		HeaderField("expires", "Sat, 27 Jul 2013 06:22:12 GMT"),
744 		HeaderField("server", "Apache"),
745 		HeaderField("vary", "foobar"),
746 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
747 		HeaderField("x-cache", "MISS from alphabravo"),
748 		HeaderField("x-cache-action", "MISS"),
749 		HeaderField("x-cache-age", "0"),
750 		HeaderField("x-cache-lookup", "MISS from alphabravo:3128"),
751 		HeaderField("x-lb-nocache", "true")
752 	];
753 	HeaderField[] hfa2 = [
754 		HeaderField(":status", "304 Not Modified"),
755 		HeaderField("age", "0"),
756 		HeaderField("cache-control", "max-age=56682045"),
757 		HeaderField("content-type", "text/css"),
758 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
759 		HeaderField("expires", "Thu, 14 May 2015 07:22:57 GMT"),
760 		HeaderField("last-modified", "Tue, 14 May 2013 07:22:15 GMT"),
761 		HeaderField("vary", "Accept-Encoding"),
762 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
763 		HeaderField("x-cache", "HIT from alphabravo"),
764 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")];
765 
766 	HeaderField[] hfa3 = [
767 		HeaderField(":status", "304 Not Modified"),
768 		HeaderField("age", "0"),
769 		HeaderField("cache-control", "max-age=56682072"),
770 		HeaderField("content-type", "text/css"),
771 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
772 		HeaderField("expires", "Thu, 14 May 2015 07:23:24 GMT"),
773 		HeaderField("last-modified", "Tue, 14 May 2013 07:22:13 GMT"),
774 		HeaderField("vary", "Accept-Encoding"),
775 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
776 		HeaderField("x-cache", "HIT from alphabravo"),
777 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
778 	];
779 
780 	HeaderField[] hfa4 = [
781 		HeaderField(":status", "304 Not Modified"),
782 		HeaderField("age", "0"),
783 		HeaderField("cache-control", "max-age=56682022"),
784 		HeaderField("content-type", "text/css"),
785 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
786 		HeaderField("expires", "Thu, 14 May 2015 07:22:34 GMT"),
787 		HeaderField("last-modified", "Tue, 14 May 2013 07:22:14 GMT"),
788 		HeaderField("vary", "Accept-Encoding"),
789 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
790 		HeaderField("x-cache", "HIT from alphabravo"),
791 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
792 	];
793 	HeaderField[] hfa5 = [
794 		HeaderField(":status", "304 Not Modified"),
795 		HeaderField("age", "0"),
796 		HeaderField("cache-control", "max-age=4461139"),
797 		HeaderField("content-type", "application/x-javascript"),
798 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
799 		HeaderField("expires", "Mon, 16 Sep 2013 21:34:31 GMT"),
800 		HeaderField("last-modified", "Thu, 05 May 2011 09:15:59 GMT"),
801 		HeaderField("vary", "Accept-Encoding"),
802 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
803 		HeaderField("x-cache", "HIT from alphabravo"),
804 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
805 	];
806 
807 	HeaderField[] hfa6 = [
808 		HeaderField(":status", "304 Not Modified"),
809 		HeaderField("age", "0"),
810 		HeaderField("cache-control", "max-age=18645951"),
811 		HeaderField("content-type", "application/x-javascript"),
812 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
813 		HeaderField("expires", "Fri, 28 Feb 2014 01:48:03 GMT"),
814 		HeaderField("last-modified", "Tue, 12 Jul 2011 16:02:59 GMT"),
815 		HeaderField("vary", "Accept-Encoding"),
816 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
817 		HeaderField("x-cache", "HIT from alphabravo"),
818 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128"),
819 	];
820 	HeaderField[] hfa7 = [
821 		HeaderField(":status", "304 Not Modified"),
822 		HeaderField("age", "0"),
823 		HeaderField("cache-control", "max-age=31536000"),
824 		HeaderField("content-type", "application/javascript"),
825 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
826 		HeaderField("etag", "\"6807-4dc5b54e0dcc0\""),
827 		HeaderField("expires", "Wed, 21 May 2014 08:32:17 GMT"),
828 		HeaderField("last-modified", "Fri, 10 May 2013 11:18:51 GMT"),
829 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
830 		HeaderField("x-cache", "HIT from alphabravo"),
831 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
832 	];
833 	HeaderField[] hfa8 = [
834 		HeaderField(":status", "304 Not Modified"),
835 		HeaderField("age", "0"),
836 		HeaderField("cache-control", "max-age=31536000"),
837 		HeaderField("content-type", "application/javascript"),
838 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
839 		HeaderField("etag", "\"41c6-4de7d28585b00\""),
840 		HeaderField("expires", "Thu, 12 Jun 2014 10:00:58 GMT"),
841 		HeaderField("last-modified", "Thu, 06 Jun 2013 14:30:36 GMT"),
842 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
843 		HeaderField("x-cache", "HIT from alphabravo"),
844 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
845 	];
846 
847 	HeaderField[] hfa9 = [
848 		HeaderField(":status", "304 Not Modified"),
849 		HeaderField("age", "0"),
850 		HeaderField("cache-control", "max-age=31536000"),
851 		HeaderField("content-type", "application/javascript"),
852 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
853 		HeaderField("etag", "\"19d6e-4dc5b35a541c0\""),
854 		HeaderField("expires", "Wed, 21 May 2014 08:32:18 GMT"),
855 		HeaderField("last-modified", "Fri, 10 May 2013 11:10:07 GMT"),
856 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
857 		HeaderField("x-cache", "HIT from alphabravo"),
858 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
859 	];
860 	HeaderField[] hfa10 = [
861 		HeaderField(":status", "304 Not Modified"),
862 		HeaderField("age", "0"),
863 		HeaderField("cache-control", "max-age=56682045"),
864 		HeaderField("content-type", "text/css"),
865 		HeaderField("date", "Sat, 27 Jul 2013 06:22:12 GMT"),
866 		HeaderField("expires", "Thu, 14 May 2015 07:22:57 GMT"),
867 		HeaderField("last-modified", "Tue, 14 May 2013 07:21:53 GMT"),
868 		HeaderField("vary", "Accept-Encoding"),
869 		HeaderField("via", "1.1 alphabravo (squid/3.x.x), 1.1 nghttpx"),
870 		HeaderField("x-cache", "HIT from alphabravo"),
871 		HeaderField("x-cache-lookup", "HIT from alphabravo:3128")
872 	];
873 
874 	check_deflate_inflate(deflater, inflater, hfa1);
875 	check_deflate_inflate(deflater, inflater, hfa2);
876 	check_deflate_inflate(deflater, inflater, hfa3);
877 	check_deflate_inflate(deflater, inflater, hfa4);
878 	check_deflate_inflate(deflater, inflater, hfa5);
879 	check_deflate_inflate(deflater, inflater, hfa6);
880 	check_deflate_inflate(deflater, inflater, hfa7);
881 	check_deflate_inflate(deflater, inflater, hfa8);
882 	check_deflate_inflate(deflater, inflater, hfa9);
883 	check_deflate_inflate(deflater, inflater, hfa10);
884 	
885 	inflater.free();
886 	deflater.free();
887 }
888 
889 void test_hd_no_index() {
890 	Deflater deflater = Deflater(DEFAULT_MAX_DEFLATE_BUFFER_SIZE);
891 	Inflater inflater = Inflater(true);
892 	Buffers bufs = framePackBuffers();
893 	size_t blocklen;
894 	HeaderField[] hfa = [
895 		HeaderField(":method", "GET"), HeaderField(":method", "POST"),
896 		HeaderField(":path", "/foo"),  HeaderField("version", "HTTP/1.1"),
897 		HeaderField(":method", "GET")
898 	];
899 	size_t i;
900 	HeaderFields output;
901 	ErrorCode rv;
902 	
903 	/* 1st :method: GET can be indexable, last one is not */
904 	foreach (ref hf; hfa[1 .. $]) {
905 		hf.flag = HeaderFlag.NO_INDEX;
906 	}
907 
908 	rv = deflater.deflate(bufs, hfa);
909 	blocklen = bufs.length;
910 	
911 	assert(0 == rv);
912 	assert(blocklen > 0);
913 	assert(blocklen == output.inflate(inflater, bufs, 0));
914 	
915 	assert(hfa.length == output.length);
916 	assert(hfa.equals(output[]));
917 	
918 	assert(output.hfa_raw[0].flag == HeaderFlag.NONE);
919 
920 	foreach (ref hf; output[][1 .. $])
921 		assert(hf.flag == HeaderFlag.NO_INDEX);
922 	
923 	output.reset();
924 	
925 	bufs.free();
926 	inflater.free();
927 	deflater.free();
928 }
929 
930 void test_hd_deflate_bound() {
931 	Deflater deflater = Deflater(DEFAULT_MAX_DEFLATE_BUFFER_SIZE);
932 	HeaderField[] hfa = [HeaderField(":method", "GET"), HeaderField("alpha", "bravo")];
933 	Buffers bufs = framePackBuffers();
934 	size_t bound, bound2;
935 	
936 	bound = deflater.upperBound(hfa);
937 	
938 	assert(12 + 6 * 2 * 2 + hfa[0].name.length + hfa[0].value.length + hfa[1].name.length + hfa[1].value.length == bound);
939 	
940 	deflater.deflate(bufs, hfa);
941 	
942 	assert(bound > cast(size_t)bufs.length);
943 	
944 	bound2 = deflater.upperBound(hfa);
945 	
946 	assert(bound == bound2);
947 	
948 	bufs.free();
949 	deflater.free();
950 }
951 
952 void test_hd_public_api() {
953 	Deflater deflater = Deflater(4096);
954 	Inflater inflater = Inflater(true);
955 	HeaderField[] hfa = [HeaderField("alpha", "bravo"), HeaderField("charlie", "delta")];
956 	ubyte[4096] buf;
957 	size_t buflen;
958 	size_t blocklen;
959 	Buffers bufs = framePackBuffers();
960 
961 	buflen = deflater.upperBound(hfa);
962 	
963 	blocklen = deflater.deflate(buf[0 .. buflen], hfa);
964 	
965 	assert(blocklen > 0);
966 	bufs.free();
967 	bufs = new Buffers(buf[0 .. blocklen]);
968 	bufs.head.buf.last += blocklen;
969 	HeaderFields dummy;
970 	assert(blocklen == dummy.inflate(inflater, bufs, 0));
971 	dummy.reset();
972 	bufs.free();
973 	
974 	inflater.free();
975 	deflater.free();
976 
977 	/* See ErrorCode.INSUFF_BUFSIZE */
978 	deflater = Deflater(4096);
979 
980 	blocklen = deflater.deflate(buf[0 .. blocklen - 1], hfa);
981 	
982 	assert(ErrorCode.INSUFF_BUFSIZE == blocklen);
983 	deflater.free();
984 }
985 
986 private size_t encodeLength(ubyte *buf, ulong n, size_t prefix) {
987 	size_t k = (1 << prefix) - 1;
988 	size_t len;
989 	*buf &= ~cast(int)(cast(ubyte)k);
990 	if (n >= k) {
991 		*buf++ |= cast(ubyte) k;
992 		n -= k;
993 		++len;
994 	} else {
995 		*buf++ |= cast(ubyte) n;
996 		return 1;
997 	}
998 	do {
999 		++len;
1000 		if (n >= 128) {
1001 			*buf++ = cast(ubyte)((1 << 7) | ((cast(ubyte)n) & 0x7f));
1002 			n >>= 7;
1003 		} else {
1004 			*buf++ = cast(ubyte)n;
1005 			break;
1006 		}
1007 	} while (n);
1008 	return len;
1009 }
1010 
1011 void test_hd_decode_length() {
1012 	uint output;
1013 	size_t shift;
1014 	bool is_final;
1015 	ubyte[16] buf;
1016 	ubyte* bufp;
1017 	size_t len;
1018 	size_t rv;
1019 	size_t i;
1020 
1021 	len = encodeLength(buf.ptr, uint.max, 7);
1022 
1023 	rv = output.decodeLength(shift, is_final, 0, 0, buf.ptr, buf.ptr + cast(size_t)len, 7);
1024 	
1025 	assert(cast(int)len == rv, len.to!string ~ " != " ~ rv.to!string);
1026 	assert(false != is_final);
1027 	assert(uint.max == output);
1028 	
1029 	/* Make sure that we can decode integer if we feed 1 byte at a time */
1030 	output = 0;
1031 	shift = 0;
1032 	is_final = false;
1033 	bufp = buf.ptr;
1034 	
1035 	for (i = 0; i < len; ++i, ++bufp) {
1036 		rv = output.decodeLength(shift, is_final, output, shift, bufp, bufp + 1, 7);
1037 		assert(rv == 1);
1038 		
1039 		if (is_final) {
1040 			break;
1041 		}
1042 	}
1043 	
1044 	assert(i == len - 1);
1045 	assert(0 != is_final);
1046 	assert(uint.max == output);
1047 	
1048 	/* Check overflow case */
1049 	memset(buf.ptr, 0, buf.length);
1050 	len = encodeLength(buf.ptr, 1L << 32, 7);
1051 	
1052 	rv = output.decodeLength(shift, is_final, 0, 0, buf.ptr, buf.ptr + len, 7);
1053 	
1054 	assert(-1 == rv);
1055 }
1056 
1057 void test_hd_huff_encode() {
1058 	ErrorCode rv;
1059 	size_t len;
1060 	Buffers bufs, outbufs;
1061 	Decoder ctx;
1062 	const ubyte[] t1 = [22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9,  8,  7,  6,  5,  4,  3,  2,  1,  0];
1063 	
1064 	bufs = framePackBuffers();
1065 	outbufs = framePackBuffers();
1066 
1067 	rv = bufs.encodeHuffman(cast(string)t1);
1068 	
1069 	assert(rv == 0);
1070 		
1071 	len = ctx.decode(outbufs, bufs.cur.buf[], true);
1072 	
1073 	assert(bufs.length == len);
1074 	assert(cast(size_t)t1.length == outbufs.length);
1075 	
1076 	assert(t1[0 .. $] == outbufs.cur.buf.pos[0 .. t1.length]);
1077 	
1078 	bufs.free();
1079 	outbufs.free();
1080 }
1081 
1082 unittest {
1083 	import memutils.allocators;
1084 	enum Debugger = 0x02;
1085 	assert(0 == getAllocator!Debugger().bytesAllocated());
1086 	test_hd_deflate();
1087 	test_hd_deflate_same_indexed_repr();
1088 	test_hd_inflate_indexed();
1089 	test_hd_inflate_indname_noinc();
1090 	test_hd_inflate_indname_inc();
1091 	test_hd_inflate_indname_inc_eviction();
1092 	test_hd_inflate_newname_noinc();
1093 	test_hd_inflate_newname_inc();
1094 	test_hd_inflate_clearall_inc();
1095 	test_hd_inflate_zero_length_huffman();
1096 	test_hd_ringbuf_reserve();
1097 	test_hd_change_table_size();
1098 	test_hd_deflate_inflate();
1099 	test_hd_no_index();
1100 	test_hd_deflate_bound();
1101 	test_hd_public_api();
1102 	test_hd_decode_length();
1103 	test_hd_huff_encode();
1104 	assert(0 == getAllocator!Debugger().bytesAllocated());
1105 }