iPXE
deflate.c
Go to the documentation of this file.
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  */
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  */
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  */
72 
73 /** Code length map */
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 */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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 ) );
322  ( byte << deflate->bits ) );
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  */
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 ) );
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  */
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  */
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  */
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  */
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  */
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  */
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 */
513  if ( header < 0 ) {
514  deflate->resume = &&zlib_header;
515  return 0;
516  }
517 
518  /* Parse header */
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 */
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 ) {
555  goto literal_block;
557  goto static_block;
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 */
571  }
572 
573  literal_len: {
574  int len;
575 
576  /* Extract LEN field */
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",
587  }
588 
589  literal_nlen: {
590  int nlen;
591 
592  /* Extract NLEN field */
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 */
661  if ( header < 0 ) {
662  deflate->resume = &&dynamic_header;
663  return 0;
664  }
665 
666  /* Parse header */
667  hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
669  hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
671  hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
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,
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 */
697  if ( len < 0 ) {
698  deflate->resume = &&dynamic_codelen;
699  return 0;
700  }
701 
702  /* Store code length */
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,
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;
721  deflate->length = 0;
722  }
723 
724  dynamic_litlen_distance: {
725  int len;
726  int index;
727 
728  /* Decode literal/length/distance code length */
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 */
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-- ) {
767  deflate->length );
768  }
769 
770  /* Process next literal/length or distance code
771  * length, if more are required.
772  */
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,
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 */
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--;
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 */
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 */
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--;
909  }
910 
911  lzhuf_distance_extra: {
912  int extra;
913  size_t dup_len;
914  size_t dup_distance;
915 
916  /* Extract 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 */
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  */
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  */
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--;
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--;
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 }
int deflate_inflate(struct deflate *deflate, struct deflate_chunk *in, struct deflate_chunk *out)
Inflate compressed data.
Definition: deflate.c:492
#define EINVAL
Invalid argument.
Definition: errno.h:428
static void deflate_set_length(struct deflate *deflate, unsigned int index, unsigned int bits)
Set Huffman symbol length.
Definition: deflate.c:120
struct arbelprm_rc_send_wqe rc
Definition: arbel.h:14
unsigned short uint16_t
Definition: stdint.h:11
unsigned int length_index
Current length index within a set of code lengths.
Definition: deflate.h:181
#define DEFLATE_DYNAMIC_HLIT_LSB
Dynamic header HLIT field LSB.
Definition: deflate.h:52
static uint16_t deflate_distance_base[32]
Distance base values.
Definition: deflate.c:71
__be32 in[4]
Definition: CIB_PRM.h:35
static void deflate_copy(struct deflate_chunk *out, userptr_t start, size_t offset, size_t len)
Copy data to output buffer (if available)
Definition: deflate.c:456
static unsigned int unsigned int bit
Definition: bigint.h:205
#define DEFLATE_CODELEN_BITS
Dynamic header code length length (in bits)
Definition: deflate.h:70
struct deflate_alphabet distance_codelen
Distance and code length Huffman alphabet.
Definition: deflate.h:212
Error codes.
unsigned int length_target
Target length index within a set of code lengths.
Definition: deflate.h:183
#define DEFLATE_DYNAMIC_HCLEN_MASK
Dynamic header HCLEN field mask.
Definition: deflate.h:67
#define DEFLATE_HUFFMAN_QL_SHIFT
Quick lookup shift.
Definition: deflate.h:82
unsigned int extra_bits
Number of extra bits required.
Definition: deflate.h:187
#define DEFLATE_HUFFMAN_BITS
Maximum length of a Huffman symbol (in bits)
Definition: deflate.h:73
static __always_inline void copy_from_user(void *dest, userptr_t src, off_t src_off, size_t len)
Copy data from user buffer.
Definition: uaccess.h:337
size_t dup_distance
Distance of a duplicated string.
Definition: deflate.h:191
#define DEFLATE_HEADER_BTYPE_STATIC
Block header type: static Huffman alphabet.
Definition: deflate.h:40
unsigned int header
Current block header.
Definition: deflate.h:177
#define DBGC(...)
Definition: compiler.h:505
uint16_t raw[0]
Raw symbols.
Definition: deflate.h:144
enum deflate_format format
Format.
Definition: deflate.h:164
unsigned int length
Current length within a set of code lengths.
Definition: deflate.h:185
A Huffman-coded set of symbols of a given length.
Definition: deflate.h:115
char prefix[4]
Definition: vmconsole.c:53
#define ZLIB_ADLER32_BITS
ZLIB ADLER32 length (in bits)
Definition: deflate.h:112
uint32_t start
First symbol of this length (normalised to 16 bits)
Definition: deflate.h:128
A Huffman-coded alphabet.
Definition: deflate.h:134
#define DEFLATE_LITLEN_END
Literal/length end of block code.
Definition: deflate.h:85
static unsigned int deflate_length(struct deflate *deflate, unsigned int index)
Get Huffman symbol length.
Definition: deflate.c:133
Character types.
static int deflate_alphabet(struct deflate *deflate, struct deflate_alphabet *alphabet, unsigned int count, unsigned int offset)
Construct Huffman alphabet.
Definition: deflate.c:213
#define DEFLATE_DYNAMIC_HDIST_MASK
Dynamic header HDIST field mask.
Definition: deflate.h:61
uint8_t count
Repetition count.
Definition: deflate.h:152
Access to external ("user") memory.
unsigned int bits
Number of bits within the accumulator.
Definition: deflate.h:174
static const char * deflate_bin(unsigned long value, unsigned int bits)
Transcribe binary value (for debugging)
Definition: deflate.c:98
struct ib_mad_cm cm
Definition: ib_mad.h:14
#define ENOTSUP
Operation not supported.
Definition: errno.h:589
static int isprint(int character)
Check if character is printable.
Definition: ctype.h:86
#define DEFLATE_DYNAMIC_HCLEN_LSB
Dynamic header HCLEN field LSB.
Definition: deflate.h:64
uint32_t start
Starting offset.
Definition: netvsc.h:12
static void deflate_dump_alphabet(struct deflate *deflate, struct deflate_alphabet *alphabet)
Dump Huffman alphabet (for debugging)
Definition: deflate.c:165
#define DEFLATE_HEADER_BTYPE_LSB
Block header type LSB.
Definition: deflate.h:31
#define ZLIB_HEADER_BITS
ZLIB header length (in bits)
Definition: deflate.h:97
A chunk of data.
Definition: deflate.h:241
void deflate_init(struct deflate *deflate, enum deflate_format format)
Initialise decompressor.
Definition: deflate.c:999
#define DEFLATE_LITERAL_LEN_BITS
Literal header LEN/NLEN field length (in bits)
Definition: deflate.h:46
uint32_t accumulator
Accumulator.
Definition: deflate.h:167
size_t dup_len
Length of a duplicated string.
Definition: deflate.h:189
#define ZLIB_HEADER_CM_DEFLATE
ZLIB header compression method: DEFLATE.
Definition: deflate.h:106
Assertions.
assert((readw(&hdr->flags) &(GTF_reading|GTF_writing))==0)
void * resume
Resume point.
Definition: deflate.h:162
#define DEFLATE_HUFFMAN_QL_BITS
Quick lookup length for a Huffman symbol (in bits)
Definition: deflate.h:79
uint8_t lookup[1<< DEFLATE_HUFFMAN_QL_BITS]
Quick lookup table.
Definition: deflate.h:138
static userptr_t size_t offset
Offset of the first segment within the content.
Definition: deflate.h:259
__be32 out[4]
Definition: CIB_PRM.h:36
struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS]
Huffman-coded symbol set for each length.
Definition: deflate.h:136
FILE_LICENCE(GPL2_OR_LATER_OR_UBDL)
uint16_t freq
Number of Huffman-coded symbols having this length.
Definition: deflate.h:121
ZLIB header and footer.
Definition: deflate.h:21
pseudo_bit_t value[0x00020]
Definition: arbel.h:13
#define DEFLATE_DYNAMIC_HLIT_MASK
Dynamic header HLIT field mask.
Definition: deflate.h:55
uint8_t fill
Length pair.
Definition: deflate.h:150
deflate_format
Compression formats.
Definition: deflate.h:17
#define DEFLATE_CODELEN_MAX_CODE
Maximum value of a code length code.
Definition: deflate.h:94
static const char * deflate_alphabet_name(struct deflate *deflate, struct deflate_alphabet *alphabet)
Determine Huffman alphabet name (for debugging)
Definition: deflate.c:147
uint32_t rotalumucca
Bit-reversed accumulator.
Definition: deflate.h:172
unsigned char uint8_t
Definition: stdint.h:10
unsigned int distance_count
Number of symbols in the distance Huffman alphabet.
Definition: deflate.h:220
static uint8_t deflate_litlen_base[28]
Literal/length base values.
Definition: deflate.c:62
static int deflate_consume(struct deflate *deflate, unsigned int count)
Consume accumulated bits from the input stream.
Definition: deflate.c:343
unsigned char byte
Definition: smc9000.h:38
uint16_t base
Base address.
Definition: edd.h:14
struct deflate_alphabet litlen
Literal/length Huffman alphabet.
Definition: deflate.h:194
uint16_t * raw
Raw symbols having this length.
Definition: deflate.h:130
static int deflate_accumulate(struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
Attempt to accumulate bits from input stream.
Definition: deflate.c:307
static uint8_t deflate_codelen_map[19]
Code length map.
Definition: deflate.c:74
#define DEFLATE_DYNAMIC_BITS
Dynamic header length (in bits)
Definition: deflate.h:49
Raw DEFLATE data (no header or footer)
Definition: deflate.h:19
uint8_t code
Response code.
Definition: scsi.h:16
static volatile void * bits
Definition: bitops.h:27
uint32_t len
Length.
Definition: ena.h:14
#define DBGC2(...)
Definition: compiler.h:522
A static Huffman alphabet length pattern.
Definition: deflate.h:148
uint16_t count
Number of entries.
Definition: ena.h:22
#define DEFLATE_HEADER_BTYPE_LITERAL
Block header type: literal data.
Definition: deflate.h:37
struct ena_aq_header header
Header.
Definition: ena.h:12
userptr_t virt_to_user(volatile const void *addr)
Convert virtual address to user pointer.
#define DEFLATE_HEADER_BITS
Block header length (in bits)
Definition: deflate.h:25
#define ZLIB_HEADER_CM_MASK
ZLIB header compression method mask.
Definition: deflate.h:103
static struct deflate_static_length_pattern deflate_static_length_patterns[]
Static Huffman alphabet length patterns.
Definition: deflate.c:79
#define DBGCP(...)
Definition: compiler.h:539
__be32 raw[7]
Definition: CIB_PRM.h:28
unsigned int litlen_count
Number of symbols in the literal/length Huffman alphabet.
Definition: deflate.h:201
#define ZLIB_HEADER_CM_LSB
ZLIB header compression method LSB.
Definition: deflate.h:100
#define DBG_EXTRA
Definition: compiler.h:319
#define DEFLATE_HEADER_BFINAL_BIT
Block header final block flags bit.
Definition: deflate.h:28
uint8_t lengths[((DEFLATE_LITLEN_MAX_CODE+1)+(DEFLATE_DISTANCE_MAX_CODE+1)+1)/2]
Huffman code lengths.
Definition: deflate.h:237
struct arbelprm_port_state_change_st data
Message.
Definition: arbel.h:12
static void deflate_discard_to_byte(struct deflate *deflate)
Discard bits up to the next byte boundary.
Definition: deflate.c:443
DEFLATE decompression algorithm.
uint8_t shift
Shift to normalise symbols of this length to 16 bits.
Definition: deflate.h:119
static int deflate_extract(struct deflate *deflate, struct deflate_chunk *in, unsigned int target)
Attempt to extract a fixed number of bits from input stream.
Definition: deflate.c:366
uint64_t index
Index of the first segment within the content.
Definition: pccrc.h:21
static int deflate_decode(struct deflate *deflate, struct deflate_chunk *in, struct deflate_alphabet *alphabet)
Attempt to decode a Huffman-coded symbol from input stream.
Definition: deflate.c:396
int const char * format
Definition: xfer.h:104
#define ZLIB_HEADER_FDICT_BIT
ZLIB header preset dictionary flag bit.
Definition: deflate.h:109
#define NULL
NULL pointer (VOID *)
Definition: Base.h:362
String functions.
#define DEFLATE_DYNAMIC_HDIST_LSB
Dynamic header HDIST field LSB.
Definition: deflate.h:58
uint8_t bits
Length of Huffman-coded symbols.
Definition: deflate.h:117
void memcpy_user(userptr_t dest, off_t dest_off, userptr_t src, off_t src_off, size_t len)
Copy data between user buffers.
static uint8_t deflate_reverse[256]
Byte reversal table.
Definition: deflate.c:51
size_t remaining
Remaining length of data (e.g.
Definition: deflate.h:179
unsigned long userptr_t
A pointer to a user buffer.
Definition: uaccess.h:33
String functions.
void * memset(void *dest, int character, size_t len) __nonnull
#define DEFLATE_HEADER_BTYPE_DYNAMIC
Block header type: dynamic Huffman alphabet.
Definition: deflate.h:43
Decompressor.
Definition: deflate.h:156