1 /*
2 * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License as
6 * published by the Free Software Foundation; either version 2 of the
7 * License, or any later version.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA.
18 *
19 * You can also choose to distribute this program under the terms of
20 * the Unmodified Binary Distribution Licence (as given in the file
21 * COPYING.UBDL), provided that you have satisfied its requirements.
22 */
23
24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
25
26 #include <string.h>
27 #include <strings.h>
28 #include <errno.h>
29 #include <assert.h>
30 #include <ctype.h>
31 #include <ipxe/uaccess.h>
32 #include <ipxe/deflate.h>
33
34 /** @file
35 *
36 * DEFLATE decompression algorithm
37 *
38 * This file implements the decompression half of the DEFLATE
39 * algorithm specified in RFC 1951.
40 *
41 * Portions of this code are derived from wimboot's xca.c.
42 *
43 */
44
45 /**
46 * Byte reversal table
47 *
48 * For some insane reason, the DEFLATE format stores some values in
49 * bit-reversed order.
50 */
51 static uint8_t deflate_reverse[256];
52
53 /** Literal/length base values
54 *
55 * We include entries only for literal/length codes 257-284. Code 285
56 * does not fit the pattern (it represents a length of 258; following
57 * the pattern from the earlier codes would give a length of 259), and
58 * has no extra bits. Codes 286-287 are invalid, but can occur. We
59 * treat any code greater than 284 as meaning "length 285, no extra
60 * bits".
61 */
62 static uint8_t deflate_litlen_base[28];
63
64 /** Distance base values
65 *
66 * We include entries for all possible codes 0-31, avoiding the need
67 * to check for undefined codes 30 and 31 before performing the
68 * lookup. Codes 30 and 31 are never initialised, and will therefore
69 * be treated as meaning "14 extra bits, base distance 0".
70 */
71 static uint16_t deflate_distance_base[32];
72
73 /** Code length map */
74 static uint8_t deflate_codelen_map[19] = {
75 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
76 };
77
78 /** Static Huffman alphabet length patterns */
79 static struct deflate_static_length_pattern deflate_static_length_patterns[] = {
80 /* Literal/length code lengths */
81 { 0x88, ( ( ( 143 - 0 ) + 1 ) / 2 ) },
82 { 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) },
83 { 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) },
84 { 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) },
85 /* Distance code lengths */
86 { 0x55, ( ( ( 31 - 0 ) + 1 ) / 2 ) },
87 /* End marker */
88 { 0, 0 }
89 };
90
91 /**
92 * Transcribe binary value (for debugging)
93 *
94 * @v value Value
95 * @v bits Length of value (in bits)
96 * @ret string Transcribed value
97 */
deflate_bin(unsigned long value,unsigned int bits)98 static const char * deflate_bin ( unsigned long value, unsigned int bits ) {
99 static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
100 char *out = buf;
101
102 /* Sanity check */
103 assert ( bits < sizeof ( buf ) );
104
105 /* Transcribe value */
106 while ( bits-- )
107 *(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
108 *out = '\0';
109
110 return buf;
111 }
112
113 /**
114 * Set Huffman symbol length
115 *
116 * @v deflate Decompressor
117 * @v index Index within lengths
118 * @v bits Symbol length (in bits)
119 */
deflate_set_length(struct deflate * deflate,unsigned int index,unsigned int bits)120 static void deflate_set_length ( struct deflate *deflate, unsigned int index,
121 unsigned int bits ) {
122
123 deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
124 }
125
126 /**
127 * Get Huffman symbol length
128 *
129 * @v deflate Decompressor
130 * @v index Index within lengths
131 * @ret bits Symbol length (in bits)
132 */
deflate_length(struct deflate * deflate,unsigned int index)133 static unsigned int deflate_length ( struct deflate *deflate,
134 unsigned int index ) {
135
136 return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
137 & 0x0f );
138 }
139
140 /**
141 * Determine Huffman alphabet name (for debugging)
142 *
143 * @v deflate Decompressor
144 * @v alphabet Huffman alphabet
145 * @ret name Alphabet name
146 */
deflate_alphabet_name(struct deflate * deflate,struct deflate_alphabet * alphabet)147 static const char * deflate_alphabet_name ( struct deflate *deflate,
148 struct deflate_alphabet *alphabet ){
149
150 if ( alphabet == &deflate->litlen ) {
151 return "litlen";
152 } else if ( alphabet == &deflate->distance_codelen ) {
153 return "distance/codelen";
154 } else {
155 return "<UNKNOWN>";
156 }
157 }
158
159 /**
160 * Dump Huffman alphabet (for debugging)
161 *
162 * @v deflate Decompressor
163 * @v alphabet Huffman alphabet
164 */
deflate_dump_alphabet(struct deflate * deflate,struct deflate_alphabet * alphabet)165 static void deflate_dump_alphabet ( struct deflate *deflate,
166 struct deflate_alphabet *alphabet ) {
167 struct deflate_huf_symbols *huf_sym;
168 unsigned int bits;
169 unsigned int huf;
170 unsigned int i;
171
172 /* Do nothing unless debugging is enabled */
173 if ( ! DBG_EXTRA )
174 return;
175
176 /* Dump symbol table for each utilised length */
177 for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
178 sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
179 huf_sym = &alphabet->huf[ bits - 1 ];
180 if ( huf_sym->freq == 0 )
181 continue;
182 huf = ( huf_sym->start >> huf_sym->shift );
183 DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" "
184 "freq %d:", deflate,
185 deflate_alphabet_name ( deflate, alphabet ), bits,
186 deflate_bin ( huf, huf_sym->bits ), huf_sym->freq );
187 for ( i = 0 ; i < huf_sym->freq ; i++ ) {
188 DBGC2 ( alphabet, " %03x",
189 huf_sym->raw[ huf + i ] );
190 }
191 DBGC2 ( alphabet, "\n" );
192 }
193
194 /* Dump quick lookup table */
195 DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate,
196 deflate_alphabet_name ( deflate, alphabet ) );
197 for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
198 sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
199 DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) );
200 }
201 DBGC2 ( alphabet, "\n" );
202 }
203
204 /**
205 * Construct Huffman alphabet
206 *
207 * @v deflate Decompressor
208 * @v alphabet Huffman alphabet
209 * @v count Number of symbols
210 * @v offset Starting offset within length table
211 * @ret rc Return status code
212 */
deflate_alphabet(struct deflate * deflate,struct deflate_alphabet * alphabet,unsigned int count,unsigned int offset)213 static int deflate_alphabet ( struct deflate *deflate,
214 struct deflate_alphabet *alphabet,
215 unsigned int count, unsigned int offset ) {
216 struct deflate_huf_symbols *huf_sym;
217 unsigned int huf;
218 unsigned int cum_freq;
219 unsigned int bits;
220 unsigned int raw;
221 unsigned int adjustment;
222 unsigned int prefix;
223 int complete;
224
225 /* Clear symbol table */
226 memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
227
228 /* Count number of symbols with each Huffman-coded length */
229 for ( raw = 0 ; raw < count ; raw++ ) {
230 bits = deflate_length ( deflate, ( raw + offset ) );
231 if ( bits )
232 alphabet->huf[ bits - 1 ].freq++;
233 }
234
235 /* Populate Huffman-coded symbol table */
236 huf = 0;
237 cum_freq = 0;
238 for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
239 sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
240 huf_sym = &alphabet->huf[ bits - 1 ];
241 huf_sym->bits = bits;
242 huf_sym->shift = ( 16 - bits );
243 huf_sym->start = ( huf << huf_sym->shift );
244 huf_sym->raw = &alphabet->raw[cum_freq];
245 huf += huf_sym->freq;
246 if ( huf > ( 1U << bits ) ) {
247 DBGC ( alphabet, "DEFLATE %p \"%s\" has too many "
248 "symbols with lengths <=%d\n", deflate,
249 deflate_alphabet_name ( deflate, alphabet ),
250 bits );
251 return -EINVAL;
252 }
253 huf <<= 1;
254 cum_freq += huf_sym->freq;
255 }
256 complete = ( huf == ( 1U << bits ) );
257
258 /* Populate raw symbol table */
259 for ( raw = 0 ; raw < count ; raw++ ) {
260 bits = deflate_length ( deflate, ( raw + offset ) );
261 if ( bits ) {
262 huf_sym = &alphabet->huf[ bits - 1 ];
263 *(huf_sym->raw++) = raw;
264 }
265 }
266
267 /* Adjust Huffman-coded symbol table raw pointers and populate
268 * quick lookup table.
269 */
270 for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
271 sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
272 huf_sym = &alphabet->huf[ bits - 1 ];
273
274 /* Adjust raw pointer */
275 huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */
276 adjustment = ( huf_sym->start >> huf_sym->shift );
277 huf_sym->raw -= adjustment; /* Adjust for quick indexing */
278
279 /* Populate quick lookup table */
280 for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ;
281 prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) {
282 alphabet->lookup[prefix] = ( bits - 1 );
283 }
284 }
285
286 /* Dump alphabet (for debugging) */
287 deflate_dump_alphabet ( deflate, alphabet );
288
289 /* Check that there are no invalid codes */
290 if ( ! complete ) {
291 DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate,
292 deflate_alphabet_name ( deflate, alphabet ) );
293 return -EINVAL;
294 }
295
296 return 0;
297 }
298
299 /**
300 * Attempt to accumulate bits from input stream
301 *
302 * @v deflate Decompressor
303 * @v in Compressed input data
304 * @v target Number of bits to accumulate
305 * @ret excess Number of excess bits accumulated (may be negative)
306 */
deflate_accumulate(struct deflate * deflate,struct deflate_chunk * in,unsigned int target)307 static int deflate_accumulate ( struct deflate *deflate,
308 struct deflate_chunk *in,
309 unsigned int target ) {
310 uint8_t byte;
311
312 while ( deflate->bits < target ) {
313
314 /* Check for end of input */
315 if ( in->offset >= in->len )
316 break;
317
318 /* Acquire byte from input */
319 copy_from_user ( &byte, in->data, in->offset++,
320 sizeof ( byte ) );
321 deflate->accumulator = ( deflate->accumulator |
322 ( byte << deflate->bits ) );
323 deflate->rotalumucca = ( deflate->rotalumucca |
324 ( deflate_reverse[byte] <<
325 ( 24 - deflate->bits ) ) );
326 deflate->bits += 8;
327
328 /* Sanity check */
329 assert ( deflate->bits <=
330 ( 8 * sizeof ( deflate->accumulator ) ) );
331 }
332
333 return ( deflate->bits - target );
334 }
335
336 /**
337 * Consume accumulated bits from the input stream
338 *
339 * @v deflate Decompressor
340 * @v count Number of accumulated bits to consume
341 * @ret data Consumed bits
342 */
deflate_consume(struct deflate * deflate,unsigned int count)343 static int deflate_consume ( struct deflate *deflate, unsigned int count ) {
344 int data;
345
346 /* Sanity check */
347 assert ( count <= deflate->bits );
348
349 /* Extract data and consume bits */
350 data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) );
351 deflate->accumulator >>= count;
352 deflate->rotalumucca <<= count;
353 deflate->bits -= count;
354
355 return data;
356 }
357
358 /**
359 * Attempt to extract a fixed number of bits from input stream
360 *
361 * @v deflate Decompressor
362 * @v in Compressed input data
363 * @v target Number of bits to extract
364 * @ret data Extracted bits (or negative if not yet accumulated)
365 */
deflate_extract(struct deflate * deflate,struct deflate_chunk * in,unsigned int target)366 static int deflate_extract ( struct deflate *deflate, struct deflate_chunk *in,
367 unsigned int target ) {
368 int excess;
369 int data;
370
371 /* Return immediately if we are attempting to extract zero bits */
372 if ( target == 0 )
373 return 0;
374
375 /* Attempt to accumulate bits */
376 excess = deflate_accumulate ( deflate, in, target );
377 if ( excess < 0 )
378 return excess;
379
380 /* Extract data and consume bits */
381 data = deflate_consume ( deflate, target );
382 DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate,
383 deflate_bin ( data, target ), data, data );
384
385 return data;
386 }
387
388 /**
389 * Attempt to decode a Huffman-coded symbol from input stream
390 *
391 * @v deflate Decompressor
392 * @v in Compressed input data
393 * @v alphabet Huffman alphabet
394 * @ret code Raw code (or negative if not yet accumulated)
395 */
deflate_decode(struct deflate * deflate,struct deflate_chunk * in,struct deflate_alphabet * alphabet)396 static int deflate_decode ( struct deflate *deflate,
397 struct deflate_chunk *in,
398 struct deflate_alphabet *alphabet ) {
399 struct deflate_huf_symbols *huf_sym;
400 uint16_t huf;
401 unsigned int lookup_index;
402 int excess;
403 unsigned int raw;
404
405 /* Attempt to accumulate maximum required number of bits.
406 * There may be fewer bits than this remaining in the stream,
407 * even if the stream still contains some complete
408 * Huffman-coded symbols.
409 */
410 deflate_accumulate ( deflate, in, DEFLATE_HUFFMAN_BITS );
411
412 /* Normalise the bit-reversed accumulated value to 16 bits */
413 huf = ( deflate->rotalumucca >> 16 );
414
415 /* Find symbol set for this length */
416 lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT );
417 huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
418 while ( huf < huf_sym->start )
419 huf_sym--;
420
421 /* Calculate number of excess bits, and return if not yet complete */
422 excess = ( deflate->bits - huf_sym->bits );
423 if ( excess < 0 )
424 return excess;
425
426 /* Consume bits */
427 deflate_consume ( deflate, huf_sym->bits );
428
429 /* Look up raw symbol */
430 raw = huf_sym->raw[ huf >> huf_sym->shift ];
431 DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate,
432 deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ),
433 raw, raw );
434
435 return raw;
436 }
437
438 /**
439 * Discard bits up to the next byte boundary
440 *
441 * @v deflate Decompressor
442 */
deflate_discard_to_byte(struct deflate * deflate)443 static void deflate_discard_to_byte ( struct deflate *deflate ) {
444
445 deflate_consume ( deflate, ( deflate->bits & 7 ) );
446 }
447
448 /**
449 * Copy data to output buffer (if available)
450 *
451 * @v out Output data buffer
452 * @v start Source data
453 * @v offset Starting offset within source data
454 * @v len Length to copy
455 */
deflate_copy(struct deflate_chunk * out,userptr_t start,size_t offset,size_t len)456 static void deflate_copy ( struct deflate_chunk *out,
457 userptr_t start, size_t offset, size_t len ) {
458 size_t out_offset = out->offset;
459 size_t copy_len;
460
461 /* Copy data one byte at a time, to allow for overlap */
462 if ( out_offset < out->len ) {
463 copy_len = ( out->len - out_offset );
464 if ( copy_len > len )
465 copy_len = len;
466 while ( copy_len-- ) {
467 memcpy_user ( out->data, out_offset++,
468 start, offset++, 1 );
469 }
470 }
471 out->offset += len;
472 }
473
474 /**
475 * Inflate compressed data
476 *
477 * @v deflate Decompressor
478 * @v in Compressed input data
479 * @v out Output data buffer
480 * @ret rc Return status code
481 *
482 * The caller can use deflate_finished() to determine whether a
483 * successful return indicates that the decompressor is merely waiting
484 * for more input.
485 *
486 * Data will not be written beyond the specified end of the output
487 * data buffer, but the offset within the output data buffer will be
488 * updated to reflect the amount that should have been written. The
489 * caller can use this to find the length of the decompressed data
490 * before allocating the output data buffer.
491 */
deflate_inflate(struct deflate * deflate,struct deflate_chunk * in,struct deflate_chunk * out)492 int deflate_inflate ( struct deflate *deflate,
493 struct deflate_chunk *in,
494 struct deflate_chunk *out ) {
495
496 /* This could be implemented more neatly if gcc offered a
497 * means for enforcing tail recursion.
498 */
499 if ( deflate->resume ) {
500 goto *(deflate->resume);
501 } else switch ( deflate->format ) {
502 case DEFLATE_RAW: goto block_header;
503 case DEFLATE_ZLIB: goto zlib_header;
504 default: assert ( 0 );
505 }
506
507 zlib_header: {
508 int header;
509 int cm;
510
511 /* Extract header */
512 header = deflate_extract ( deflate, in, ZLIB_HEADER_BITS );
513 if ( header < 0 ) {
514 deflate->resume = &&zlib_header;
515 return 0;
516 }
517
518 /* Parse header */
519 cm = ( ( header >> ZLIB_HEADER_CM_LSB ) & ZLIB_HEADER_CM_MASK );
520 if ( cm != ZLIB_HEADER_CM_DEFLATE ) {
521 DBGC ( deflate, "DEFLATE %p unsupported ZLIB "
522 "compression method %d\n", deflate, cm );
523 return -ENOTSUP;
524 }
525 if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) {
526 DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset "
527 "dictionary\n", deflate );
528 return -ENOTSUP;
529 }
530
531 /* Process first block header */
532 goto block_header;
533 }
534
535 block_header: {
536 int header;
537 int bfinal;
538 int btype;
539
540 /* Extract block header */
541 header = deflate_extract ( deflate, in, DEFLATE_HEADER_BITS );
542 if ( header < 0 ) {
543 deflate->resume = &&block_header;
544 return 0;
545 }
546
547 /* Parse header */
548 deflate->header = header;
549 bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) );
550 btype = ( header >> DEFLATE_HEADER_BTYPE_LSB );
551 DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n",
552 deflate, ( bfinal ? "final " : "" ), btype );
553 switch ( btype ) {
554 case DEFLATE_HEADER_BTYPE_LITERAL:
555 goto literal_block;
556 case DEFLATE_HEADER_BTYPE_STATIC:
557 goto static_block;
558 case DEFLATE_HEADER_BTYPE_DYNAMIC:
559 goto dynamic_block;
560 default:
561 DBGC ( deflate, "DEFLATE %p unsupported block type "
562 "%#x\n", deflate, btype );
563 return -ENOTSUP;
564 }
565 }
566
567 literal_block: {
568
569 /* Discard any bits up to the next byte boundary */
570 deflate_discard_to_byte ( deflate );
571 }
572
573 literal_len: {
574 int len;
575
576 /* Extract LEN field */
577 len = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS );
578 if ( len < 0 ) {
579 deflate->resume = &&literal_len;
580 return 0;
581 }
582
583 /* Record length of literal data */
584 deflate->remaining = len;
585 DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
586 deflate, deflate->remaining );
587 }
588
589 literal_nlen: {
590 int nlen;
591
592 /* Extract NLEN field */
593 nlen = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS);
594 if ( nlen < 0 ) {
595 deflate->resume = &&literal_nlen;
596 return 0;
597 }
598
599 /* Verify NLEN */
600 if ( ( ( deflate->remaining ^ ~nlen ) &
601 ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) {
602 DBGC ( deflate, "DEFLATE %p invalid len/nlen "
603 "%#04zx/%#04x\n", deflate,
604 deflate->remaining, nlen );
605 return -EINVAL;
606 }
607 }
608
609 literal_data: {
610 size_t in_remaining;
611 size_t len;
612
613 /* Calculate available amount of literal data */
614 in_remaining = ( in->len - in->offset );
615 len = deflate->remaining;
616 if ( len > in_remaining )
617 len = in_remaining;
618
619 /* Copy data to output buffer */
620 deflate_copy ( out, in->data, in->offset, len );
621
622 /* Consume data from input buffer */
623 in->offset += len;
624 deflate->remaining -= len;
625
626 /* Finish processing if we are blocked */
627 if ( deflate->remaining ) {
628 deflate->resume = &&literal_data;
629 return 0;
630 }
631
632 /* Otherwise, finish block */
633 goto block_done;
634 }
635
636 static_block: {
637 struct deflate_static_length_pattern *pattern;
638 uint8_t *lengths = deflate->lengths;
639
640 /* Construct static Huffman lengths as per RFC 1950 */
641 for ( pattern = deflate_static_length_patterns ;
642 pattern->count ; pattern++ ) {
643 memset ( lengths, pattern->fill, pattern->count );
644 lengths += pattern->count;
645 }
646 deflate->litlen_count = 288;
647 deflate->distance_count = 32;
648 goto construct_alphabets;
649 }
650
651 dynamic_block:
652
653 dynamic_header: {
654 int header;
655 unsigned int hlit;
656 unsigned int hdist;
657 unsigned int hclen;
658
659 /* Extract block header */
660 header = deflate_extract ( deflate, in, DEFLATE_DYNAMIC_BITS );
661 if ( header < 0 ) {
662 deflate->resume = &&dynamic_header;
663 return 0;
664 }
665
666 /* Parse header */
667 hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
668 DEFLATE_DYNAMIC_HLIT_MASK );
669 hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
670 DEFLATE_DYNAMIC_HDIST_MASK );
671 hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
672 DEFLATE_DYNAMIC_HCLEN_MASK );
673 deflate->litlen_count = ( hlit + 257 );
674 deflate->distance_count = ( hdist + 1 );
675 deflate->length_index = 0;
676 deflate->length_target = ( hclen + 4 );
677 DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d "
678 "litlen, %d distance\n", deflate,
679 deflate->length_target, deflate->litlen_count,
680 deflate->distance_count );
681
682 /* Prepare for decoding code length code lengths */
683 memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
684 }
685
686 dynamic_codelen: {
687 int len;
688 unsigned int index;
689 int rc;
690
691 /* Extract all code lengths */
692 while ( deflate->length_index < deflate->length_target ) {
693
694 /* Extract code length length */
695 len = deflate_extract ( deflate, in,
696 DEFLATE_CODELEN_BITS );
697 if ( len < 0 ) {
698 deflate->resume = &&dynamic_codelen;
699 return 0;
700 }
701
702 /* Store code length */
703 index = deflate_codelen_map[deflate->length_index++];
704 deflate_set_length ( deflate, index, len );
705 DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
706 deflate, index, len );
707 }
708
709 /* Generate code length alphabet */
710 if ( ( rc = deflate_alphabet ( deflate,
711 &deflate->distance_codelen,
712 ( DEFLATE_CODELEN_MAX_CODE + 1 ),
713 0 ) ) != 0 )
714 return rc;
715
716 /* Prepare for decoding literal/length/distance code lengths */
717 memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
718 deflate->length_index = 0;
719 deflate->length_target = ( deflate->litlen_count +
720 deflate->distance_count );
721 deflate->length = 0;
722 }
723
724 dynamic_litlen_distance: {
725 int len;
726 int index;
727
728 /* Decode literal/length/distance code length */
729 len = deflate_decode ( deflate, in, &deflate->distance_codelen);
730 if ( len < 0 ) {
731 deflate->resume = &&dynamic_litlen_distance;
732 return 0;
733 }
734
735 /* Prepare for extra bits */
736 if ( len < 16 ) {
737 deflate->length = len;
738 deflate->extra_bits = 0;
739 deflate->dup_len = 1;
740 } else {
741 static const uint8_t dup_len[3] = { 3, 3, 11 };
742 static const uint8_t extra_bits[3] = { 2, 3, 7 };
743 index = ( len - 16 );
744 deflate->dup_len = dup_len[index];
745 deflate->extra_bits = extra_bits[index];
746 if ( index )
747 deflate->length = 0;
748 }
749 }
750
751 dynamic_litlen_distance_extra: {
752 int extra;
753 unsigned int dup_len;
754
755 /* Extract extra bits */
756 extra = deflate_extract ( deflate, in, deflate->extra_bits );
757 if ( extra < 0 ) {
758 deflate->resume = &&dynamic_litlen_distance_extra;
759 return 0;
760 }
761
762 /* Store code lengths */
763 dup_len = ( deflate->dup_len + extra );
764 while ( ( deflate->length_index < deflate->length_target ) &&
765 dup_len-- ) {
766 deflate_set_length ( deflate, deflate->length_index++,
767 deflate->length );
768 }
769
770 /* Process next literal/length or distance code
771 * length, if more are required.
772 */
773 if ( deflate->length_index < deflate->length_target )
774 goto dynamic_litlen_distance;
775
776 /* Construct alphabets */
777 goto construct_alphabets;
778 }
779
780 construct_alphabets: {
781 unsigned int distance_offset = deflate->litlen_count;
782 unsigned int distance_count = deflate->distance_count;
783 int rc;
784
785 /* Generate literal/length alphabet */
786 if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen,
787 deflate->litlen_count, 0 ) ) !=0)
788 return rc;
789
790 /* Handle degenerate case of a single distance code
791 * (for which it is impossible to construct a valid,
792 * complete Huffman alphabet). RFC 1951 states:
793 *
794 * If only one distance code is used, it is encoded
795 * using one bit, not zero bits; in this case there
796 * is a single code length of one, with one unused
797 * code. One distance code of zero bits means that
798 * there are no distance codes used at all (the data
799 * is all literals).
800 *
801 * If we have only a single distance code, then we
802 * instead use two distance codes both with length 1.
803 * This results in a valid Huffman alphabet. The code
804 * "0" will mean distance code 0 (which is either
805 * correct or irrelevant), and the code "1" will mean
806 * distance code 1 (which is always irrelevant).
807 */
808 if ( deflate->distance_count == 1 ) {
809
810 deflate->lengths[0] = 0x11;
811 distance_offset = 0;
812 distance_count = 2;
813 }
814
815 /* Generate distance alphabet */
816 if ( ( rc = deflate_alphabet ( deflate,
817 &deflate->distance_codelen,
818 distance_count,
819 distance_offset ) ) != 0 )
820 return rc;
821 }
822
823 lzhuf_litlen: {
824 int code;
825 uint8_t byte;
826 unsigned int extra;
827 unsigned int bits;
828
829 /* Decode Huffman codes */
830 while ( 1 ) {
831
832 /* Decode Huffman code */
833 code = deflate_decode ( deflate, in, &deflate->litlen );
834 if ( code < 0 ) {
835 deflate->resume = &&lzhuf_litlen;
836 return 0;
837 }
838
839 /* Handle according to code type */
840 if ( code < DEFLATE_LITLEN_END ) {
841
842 /* Literal value: copy to output buffer */
843 byte = code;
844 DBGCP ( deflate, "DEFLATE %p literal %#02x "
845 "('%c')\n", deflate, byte,
846 ( isprint ( byte ) ? byte : '.' ) );
847 deflate_copy ( out, virt_to_user ( &byte ), 0,
848 sizeof ( byte ) );
849
850 } else if ( code == DEFLATE_LITLEN_END ) {
851
852 /* End of block */
853 goto block_done;
854
855 } else {
856
857 /* Length code: process extra bits */
858 extra = ( code - DEFLATE_LITLEN_END - 1 );
859 if ( extra < 28 ) {
860 bits = ( extra / 4 );
861 if ( bits )
862 bits--;
863 deflate->extra_bits = bits;
864 deflate->dup_len =
865 deflate_litlen_base[extra];
866 } else {
867 deflate->extra_bits = 0;
868 deflate->dup_len = 258;
869 }
870 goto lzhuf_litlen_extra;
871 }
872 }
873 }
874
875 lzhuf_litlen_extra: {
876 int extra;
877
878 /* Extract extra bits */
879 extra = deflate_extract ( deflate, in, deflate->extra_bits );
880 if ( extra < 0 ) {
881 deflate->resume = &&lzhuf_litlen_extra;
882 return 0;
883 }
884
885 /* Update duplicate length */
886 deflate->dup_len += extra;
887 }
888
889 lzhuf_distance: {
890 int code;
891 unsigned int extra;
892 unsigned int bits;
893
894 /* Decode Huffman code */
895 code = deflate_decode ( deflate, in,
896 &deflate->distance_codelen );
897 if ( code < 0 ) {
898 deflate->resume = &&lzhuf_distance;
899 return 0;
900 }
901
902 /* Process extra bits */
903 extra = code;
904 bits = ( extra / 2 );
905 if ( bits )
906 bits--;
907 deflate->extra_bits = bits;
908 deflate->dup_distance = deflate_distance_base[extra];
909 }
910
911 lzhuf_distance_extra: {
912 int extra;
913 size_t dup_len;
914 size_t dup_distance;
915
916 /* Extract extra bits */
917 extra = deflate_extract ( deflate, in, deflate->extra_bits );
918 if ( extra < 0 ) {
919 deflate->resume = &&lzhuf_distance_extra;
920 return 0;
921 }
922
923 /* Update duplicate distance */
924 dup_distance = ( deflate->dup_distance + extra );
925 dup_len = deflate->dup_len;
926 DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance "
927 "%zd\n", deflate, dup_len, dup_distance );
928
929 /* Sanity check */
930 if ( dup_distance > out->offset ) {
931 DBGC ( deflate, "DEFLATE %p bad distance %zd (max "
932 "%zd)\n", deflate, dup_distance, out->offset );
933 return -EINVAL;
934 }
935
936 /* Copy data, allowing for overlap */
937 deflate_copy ( out, out->data, ( out->offset - dup_distance ),
938 dup_len );
939
940 /* Process next literal/length symbol */
941 goto lzhuf_litlen;
942 }
943
944 block_done: {
945
946 DBGCP ( deflate, "DEFLATE %p end of block\n", deflate );
947
948 /* If this was not the final block, process next block header */
949 if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ))
950 goto block_header;
951
952 /* Otherwise, process footer (if any) */
953 switch ( deflate->format ) {
954 case DEFLATE_RAW: goto finished;
955 case DEFLATE_ZLIB: goto zlib_footer;
956 default: assert ( 0 );
957 }
958 }
959
960 zlib_footer: {
961
962 /* Discard any bits up to the next byte boundary */
963 deflate_discard_to_byte ( deflate );
964 }
965
966 zlib_adler32: {
967 int excess;
968
969 /* Accumulate the 32 bits of checksum. We don't check
970 * the value, stop processing immediately afterwards,
971 * and so don't have to worry about the nasty corner
972 * cases involved in calling deflate_extract() to
973 * obtain a full 32 bits.
974 */
975 excess = deflate_accumulate ( deflate, in, ZLIB_ADLER32_BITS );
976 if ( excess < 0 ) {
977 deflate->resume = &&zlib_adler32;
978 return 0;
979 }
980
981 /* Finish processing */
982 goto finished;
983 }
984
985 finished: {
986 /* Mark as finished and terminate */
987 DBGCP ( deflate, "DEFLATE %p finished\n", deflate );
988 deflate->resume = NULL;
989 return 0;
990 }
991 }
992
993 /**
994 * Initialise decompressor
995 *
996 * @v deflate Decompressor
997 * @v format Compression format code
998 */
deflate_init(struct deflate * deflate,enum deflate_format format)999 void deflate_init ( struct deflate *deflate, enum deflate_format format ) {
1000 static int global_init_done;
1001 uint8_t i;
1002 uint8_t bit;
1003 uint8_t byte;
1004 unsigned int base;
1005 unsigned int bits;
1006
1007 /* Perform global initialisation if required */
1008 if ( ! global_init_done ) {
1009
1010 /* Initialise byte reversal table */
1011 for ( i = 255 ; i ; i-- ) {
1012 for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) {
1013 byte <<= 1;
1014 if ( i & bit )
1015 byte |= 1;
1016 }
1017 deflate_reverse[i] = byte;
1018 }
1019
1020 /* Initialise literal/length extra bits table */
1021 base = 3;
1022 for ( i = 0 ; i < 28 ; i++ ) {
1023 bits = ( i / 4 );
1024 if ( bits )
1025 bits--;
1026 deflate_litlen_base[i] = base;
1027 base += ( 1 << bits );
1028 }
1029 assert ( base == 259 ); /* sic */
1030
1031 /* Initialise distance extra bits table */
1032 base = 1;
1033 for ( i = 0 ; i < 30 ; i++ ) {
1034 bits = ( i / 2 );
1035 if ( bits )
1036 bits--;
1037 deflate_distance_base[i] = base;
1038 base += ( 1 << bits );
1039 }
1040 assert ( base == 32769 );
1041
1042 /* Record global initialisation as complete */
1043 global_init_done = 1;
1044 }
1045
1046 /* Initialise structure */
1047 memset ( deflate, 0, sizeof ( *deflate ) );
1048 deflate->format = format;
1049 }
1050