[deflate] Add support for DEFLATE decompression

Signed-off-by: Michael Brown <mcb30@ipxe.org>

1 files changed, 1045 insertions, 0 deletions

diff --git a/src/crypto/deflate.c b/src/crypto/deflate.c
new file mode 100644
index 00000000..1854eff4
--- /dev/null
+++ b/src/crypto/deflate.c
@@ -0,0 +1,1045 @@
+/*
+ * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <string.h>
+#include <strings.h>
+#include <errno.h>
+#include <assert.h>
+#include <ctype.h>
+#include <ipxe/uaccess.h>
+#include <ipxe/deflate.h>
+
+/** @file
+ *
+ * DEFLATE decompression algorithm
+ *
+ * This file implements the decompression half of the DEFLATE
+ * algorithm specified in RFC 1951.
+ *
+ * Portions of this code are derived from wimboot's xca.c.
+ *
+ */
+
+/**
+ * Byte reversal table
+ *
+ * For some insane reason, the DEFLATE format stores some values in
+ * bit-reversed order.
+ */
+static uint8_t deflate_reverse[256];
+
+/** Literal/length base values
+ *
+ * We include entries only for literal/length codes 257-284.  Code 285
+ * does not fit the pattern (it represents a length of 258; following
+ * the pattern from the earlier codes would give a length of 259), and
+ * has no extra bits.  Codes 286-287 are invalid, but can occur.  We
+ * treat any code greater than 284 as meaning "length 285, no extra
+ * bits".
+ */
+static uint8_t deflate_litlen_base[28];
+
+/** Distance base values
+ *
+ * We include entries for all possible codes 0-31, avoiding the need
+ * to check for undefined codes 30 and 31 before performing the
+ * lookup.  Codes 30 and 31 are never initialised, and will therefore
+ * be treated as meaning "14 extra bits, base distance 0".
+ */
+static uint16_t deflate_distance_base[32];
+
+/** Code length map */
+static uint8_t deflate_codelen_map[19] = {
+	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
+};
+
+/** Static Huffman alphabet length patterns */
+static struct deflate_static_length_pattern deflate_static_length_patterns[] = {
+	/* Literal/length code lengths */
+	{ 0x88, ( ( ( 143 -   0 ) + 1 ) / 2 ) },
+	{ 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) },
+	{ 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) },
+	{ 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) },
+	/* Distance code lengths */
+	{ 0x55, ( ( (  31 -   0 ) + 1 ) / 2 ) },
+	/* End marker */
+	{ 0, 0 }
+};
+
+/**
+ * Transcribe binary value (for debugging)
+ *
+ * @v value		Value
+ * @v bits		Length of value (in bits)
+ * @ret string		Transcribed value
+ */
+static const char * deflate_bin ( unsigned long value, unsigned int bits ) {
+	static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
+	char *out = buf;
+
+	/* Sanity check */
+	assert ( bits < sizeof ( buf ) );
+
+	/* Transcribe value */
+	while ( bits-- )
+		*(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
+	*out = '\0';
+
+	return buf;
+}
+
+/**
+ * Set Huffman symbol length
+ *
+ * @v deflate		Decompressor
+ * @v index		Index within lengths
+ * @v bits		Symbol length (in bits)
+ */
+static void deflate_set_length ( struct deflate *deflate, unsigned int index,
+				 unsigned int bits ) {
+
+	deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
+}
+
+/**
+ * Get Huffman symbol length
+ *
+ * @v deflate		Decompressor
+ * @v index		Index within lengths
+ * @ret bits		Symbol length (in bits)
+ */
+static unsigned int deflate_length ( struct deflate *deflate,
+				     unsigned int index ) {
+
+	return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
+		 & 0x0f );
+}
+
+/**
+ * Determine Huffman alphabet name (for debugging)
+ *
+ * @v deflate		Decompressor
+ * @v alphabet		Huffman alphabet
+ * @ret name		Alphabet name
+ */
+static const char * deflate_alphabet_name ( struct deflate *deflate,
+					    struct deflate_alphabet *alphabet ){
+
+	if ( alphabet == &deflate->litlen ) {
+		return "litlen";
+	} else if ( alphabet == &deflate->distance_codelen ) {
+		return "distance/codelen";
+	} else {
+		return "<UNKNOWN>";
+	}
+}
+
+/**
+ * Dump Huffman alphabet (for debugging)
+ *
+ * @v deflate		Decompressor
+ * @v alphabet		Huffman alphabet
+ */
+static void deflate_dump_alphabet ( struct deflate *deflate,
+				    struct deflate_alphabet *alphabet ) {
+	struct deflate_huf_symbols *huf_sym;
+	unsigned int bits;
+	unsigned int huf;
+	unsigned int i;
+
+	/* Do nothing unless debugging is enabled */
+	if ( ! DBG_EXTRA )
+		return;
+
+	/* Dump symbol table for each utilised length */
+	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
+				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
+		huf_sym = &alphabet->huf[ bits - 1 ];
+		if ( huf_sym->freq == 0 )
+			continue;
+		huf = ( huf_sym->start >> huf_sym->shift );
+		DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" "
+			"freq %d:", deflate,
+			deflate_alphabet_name ( deflate, alphabet ), bits,
+			deflate_bin ( huf, huf_sym->bits ), huf_sym->freq );
+		for ( i = 0 ; i < huf_sym->freq ; i++ ) {
+			DBGC2 ( alphabet, " %03x",
+				huf_sym->raw[ huf + i ] );
+		}
+		DBGC2 ( alphabet, "\n" );
+	}
+
+	/* Dump quick lookup table */
+	DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate,
+		deflate_alphabet_name ( deflate, alphabet ) );
+	for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
+			    sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
+		DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) );
+	}
+	DBGC2 ( alphabet, "\n" );
+}
+
+/**
+ * Construct Huffman alphabet
+ *
+ * @v deflate		Decompressor
+ * @v alphabet		Huffman alphabet
+ * @v count		Number of symbols
+ * @v offset		Starting offset within length table
+ * @ret rc		Return status code
+ */
+static int deflate_alphabet ( struct deflate *deflate,
+			      struct deflate_alphabet *alphabet,
+			      unsigned int count, unsigned int offset ) {
+	struct deflate_huf_symbols *huf_sym;
+	unsigned int huf;
+	unsigned int cum_freq;
+	unsigned int bits;
+	unsigned int raw;
+	unsigned int adjustment;
+	unsigned int prefix;
+	int complete;
+
+	/* Clear symbol table */
+	memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
+
+	/* Count number of symbols with each Huffman-coded length */
+	for ( raw = 0 ; raw < count ; raw++ ) {
+		bits = deflate_length ( deflate, ( raw + offset ) );
+		if ( bits )
+			alphabet->huf[ bits - 1 ].freq++;
+	}
+
+	/* Populate Huffman-coded symbol table */
+	huf = 0;
+	cum_freq = 0;
+	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
+				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
+		huf_sym = &alphabet->huf[ bits - 1 ];
+		huf_sym->bits = bits;
+		huf_sym->shift = ( 16 - bits );
+		huf_sym->start = ( huf << huf_sym->shift );
+		huf_sym->raw = &alphabet->raw[cum_freq];
+		huf += huf_sym->freq;
+		if ( huf > ( 1U << bits ) ) {
+			DBGC ( alphabet, "DEFLATE %p \"%s\" has too many "
+			       "symbols with lengths <=%d\n", deflate,
+			       deflate_alphabet_name ( deflate, alphabet ),
+			       bits );
+			return -EINVAL;
+		}
+		huf <<= 1;
+		cum_freq += huf_sym->freq;
+	}
+	complete = ( huf == ( 1U << bits ) );
+
+	/* Populate raw symbol table */
+	for ( raw = 0 ; raw < count ; raw++ ) {
+		bits = deflate_length ( deflate, ( raw + offset ) );
+		if ( bits ) {
+			huf_sym = &alphabet->huf[ bits - 1 ];
+			*(huf_sym->raw++) = raw;
+		}
+	}
+
+	/* Adjust Huffman-coded symbol table raw pointers and populate
+	 * quick lookup table.
+	 */
+	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
+				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
+		huf_sym = &alphabet->huf[ bits - 1 ];
+
+		/* Adjust raw pointer */
+		huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */
+		adjustment = ( huf_sym->start >> huf_sym->shift );
+		huf_sym->raw -= adjustment; /* Adjust for quick indexing */
+
+		/* Populate quick lookup table */
+		for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ;
+		      prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) {
+			alphabet->lookup[prefix] = ( bits - 1 );
+		}
+	}
+
+	/* Dump alphabet (for debugging) */
+	deflate_dump_alphabet ( deflate, alphabet );
+
+	/* Check that there are no invalid codes */
+	if ( ! complete ) {
+		DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate,
+		       deflate_alphabet_name ( deflate, alphabet ) );
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+/**
+ * Attempt to accumulate bits from input stream
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v target		Number of bits to accumulate
+ * @ret excess		Number of excess bits accumulated (may be negative)
+ */
+static int deflate_accumulate ( struct deflate *deflate,
+				struct deflate_chunk *in,
+				unsigned int target ) {
+	uint8_t byte;
+
+	while ( deflate->bits < target ) {
+
+		/* Check for end of input */
+		if ( in->offset >= in->len )
+			break;
+
+		/* Acquire byte from input */
+		copy_from_user ( &byte, in->data, in->offset++,
+				 sizeof ( byte ) );
+		deflate->accumulator = ( deflate->accumulator |
+					 ( byte << deflate->bits ) );
+		deflate->rotalumucca = ( deflate->rotalumucca |
+					 ( deflate_reverse[byte] <<
+					   ( 24 - deflate->bits ) ) );
+		deflate->bits += 8;
+
+		/* Sanity check */
+		assert ( deflate->bits <=
+			 ( 8 * sizeof ( deflate->accumulator ) ) );
+	}
+
+	return ( deflate->bits - target );
+}
+
+/**
+ * Consume accumulated bits from the input stream
+ *
+ * @v deflate		Decompressor
+ * @v count		Number of accumulated bits to consume
+ * @ret data		Consumed bits
+ */
+static int deflate_consume ( struct deflate *deflate, unsigned int count ) {
+	int data;
+
+	/* Sanity check */
+	assert ( count <= deflate->bits );
+
+	/* Extract data and consume bits */
+	data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) );
+	deflate->accumulator >>= count;
+	deflate->rotalumucca <<= count;
+	deflate->bits -= count;
+
+	return data;
+}
+
+/**
+ * Attempt to extract a fixed number of bits from input stream
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v target		Number of bits to extract
+ * @ret data		Extracted bits (or negative if not yet accumulated)
+ */
+static int deflate_extract ( struct deflate *deflate, struct deflate_chunk *in,
+			     unsigned int target ) {
+	int excess;
+	int data;
+
+	/* Return immediately if we are attempting to extract zero bits */
+	if ( target == 0 )
+		return 0;
+
+	/* Attempt to accumulate bits */
+	excess = deflate_accumulate ( deflate, in, target );
+	if ( excess < 0 )
+		return excess;
+
+	/* Extract data and consume bits */
+	data = deflate_consume ( deflate, target );
+	DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate,
+		deflate_bin ( data, target ), data, data );
+
+	return data;
+}
+
+/**
+ * Attempt to decode a Huffman-coded symbol from input stream
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v alphabet		Huffman alphabet
+ * @ret code		Raw code (or negative if not yet accumulated)
+ */
+static int deflate_decode ( struct deflate *deflate,
+			    struct deflate_chunk *in,
+			    struct deflate_alphabet *alphabet ) {
+	struct deflate_huf_symbols *huf_sym;
+	uint16_t huf;
+	unsigned int lookup_index;
+	int excess;
+	unsigned int raw;
+
+	/* Attempt to accumulate maximum required number of bits.
+	 * There may be fewer bits than this remaining in the stream,
+	 * even if the stream still contains some complete
+	 * Huffman-coded symbols.
+	 */
+	deflate_accumulate ( deflate, in, DEFLATE_HUFFMAN_BITS );
+
+	/* Normalise the bit-reversed accumulated value to 16 bits */
+	huf = ( deflate->rotalumucca >> 16 );
+
+	/* Find symbol set for this length */
+	lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT );
+	huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
+	while ( huf < huf_sym->start )
+		huf_sym--;
+
+	/* Calculate number of excess bits, and return if not yet complete */
+	excess = ( deflate->bits - huf_sym->bits );
+	if ( excess < 0 )
+		return excess;
+
+	/* Consume bits */
+	deflate_consume ( deflate, huf_sym->bits );
+
+	/* Look up raw symbol */
+	raw = huf_sym->raw[ huf >> huf_sym->shift ];
+	DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate,
+		deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ),
+		raw, raw );
+
+	return raw;
+}
+
+/**
+ * Discard bits up to the next byte boundary
+ *
+ * @v deflate		Decompressor
+ */
+static void deflate_discard_to_byte ( struct deflate *deflate ) {
+
+	deflate_consume ( deflate, ( deflate->bits & 7 ) );
+}
+
+/**
+ * Copy data to output buffer (if available)
+ *
+ * @v out		Output data buffer
+ * @v start		Source data
+ * @v offset		Starting offset within source data
+ * @v len		Length to copy
+ */
+static void deflate_copy ( struct deflate_chunk *out,
+			   userptr_t start, size_t offset, size_t len ) {
+	size_t out_offset = out->offset;
+	size_t copy_len;
+
+	/* Copy data one byte at a time, to allow for overlap */
+	if ( out_offset < out->len ) {
+		copy_len = ( out->len - out_offset );
+		if ( copy_len > len )
+			copy_len = len;
+		while ( copy_len-- ) {
+			memcpy_user ( out->data, out_offset++,
+				      start, offset++, 1 );
+		}
+	}
+	out->offset += len;
+}
+
+/**
+ * Inflate compressed data
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v out		Output data buffer
+ * @ret rc		Return status code
+ *
+ * The caller can use deflate_finished() to determine whether a
+ * successful return indicates that the decompressor is merely waiting
+ * for more input.
+ *
+ * Data will not be written beyond the specified end of the output
+ * data buffer, but the offset within the output data buffer will be
+ * updated to reflect the amount that should have been written.  The
+ * caller can use this to find the length of the decompressed data
+ * before allocating the output data buffer.
+ */
+int deflate_inflate ( struct deflate *deflate,
+		      struct deflate_chunk *in,
+		      struct deflate_chunk *out ) {
+
+	/* This could be implemented more neatly if gcc offered a
+	 * means for enforcing tail recursion.
+	 */
+	if ( deflate->resume ) {
+		goto *(deflate->resume);
+	} else switch ( deflate->format ) {
+		case DEFLATE_RAW:	goto block_header;
+		case DEFLATE_ZLIB:	goto zlib_header;
+		default:		assert ( 0 );
+	}
+
+ zlib_header: {
+		int header;
+		int cm;
+
+		/* Extract header */
+		header = deflate_extract ( deflate, in, ZLIB_HEADER_BITS );
+		if ( header < 0 ) {
+			deflate->resume = &&zlib_header;
+			return 0;
+		}
+
+		/* Parse header */
+		cm = ( ( header >> ZLIB_HEADER_CM_LSB ) & ZLIB_HEADER_CM_MASK );
+		if ( cm != ZLIB_HEADER_CM_DEFLATE ) {
+			DBGC ( deflate, "DEFLATE %p unsupported ZLIB "
+			       "compression method %d\n", deflate, cm );
+			return -ENOTSUP;
+		}
+		if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) {
+			DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset "
+			       "dictionary\n", deflate );
+			return -ENOTSUP;
+		}
+
+		/* Process first block header */
+		goto block_header;
+	}
+
+ block_header: {
+		int header;
+		int bfinal;
+		int btype;
+
+		/* Extract block header */
+		header = deflate_extract ( deflate, in, DEFLATE_HEADER_BITS );
+		if ( header < 0 ) {
+			deflate->resume = &&block_header;
+			return 0;
+		}
+
+		/* Parse header */
+		deflate->header = header;
+		bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) );
+		btype = ( header >> DEFLATE_HEADER_BTYPE_LSB );
+		DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n",
+		       deflate, ( bfinal ? "final " : "" ), btype );
+		switch ( btype ) {
+		case DEFLATE_HEADER_BTYPE_LITERAL:
+			goto literal_block;
+		case DEFLATE_HEADER_BTYPE_STATIC:
+			goto static_block;
+		case DEFLATE_HEADER_BTYPE_DYNAMIC:
+			goto dynamic_block;
+		default:
+			DBGC ( deflate, "DEFLATE %p unsupported block type "
+			       "%#x\n", deflate, btype );
+			return -ENOTSUP;
+		}
+	}
+
+ literal_block: {
+
+		/* Discard any bits up to the next byte boundary */
+		deflate_discard_to_byte ( deflate );
+	}
+
+ literal_len: {
+		int len;
+
+		/* Extract LEN field */
+		len = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS );
+		if ( len < 0 ) {
+			deflate->resume = &&literal_len;
+			return 0;
+		}
+
+		/* Record length of literal data */
+		deflate->remaining = len;
+		DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
+			deflate, deflate->remaining );
+	}
+
+ literal_nlen: {
+		int nlen;
+
+		/* Extract NLEN field */
+		nlen = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS);
+		if ( nlen < 0 ) {
+			deflate->resume = &&literal_nlen;
+			return 0;
+		}
+
+		/* Verify NLEN */
+		if ( ( ( deflate->remaining ^ ~nlen ) &
+		       ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) {
+			DBGC ( deflate, "DEFLATE %p invalid len/nlen "
+			       "%#04zx/%#04x\n", deflate,
+			       deflate->remaining, nlen );
+			return -EINVAL;
+		}
+	}
+
+ literal_data: {
+		size_t in_remaining;
+		size_t len;
+
+		/* Calculate available amount of literal data */
+		in_remaining = ( in->len - in->offset );
+		len = deflate->remaining;
+		if ( len < in_remaining )
+			len = in_remaining;
+
+		/* Copy data to output buffer */
+		deflate_copy ( out, in->data, in->offset, len );
+
+		/* Consume data from input buffer */
+		in->offset += len;
+		deflate->remaining -= len;
+
+		/* Finish processing if we are blocked */
+		if ( deflate->remaining ) {
+			deflate->resume = &&literal_data;
+			return 0;
+		}
+
+		/* Otherwise, finish block */
+		goto block_done;
+	}
+
+ static_block: {
+		struct deflate_static_length_pattern *pattern;
+		uint8_t *lengths = deflate->lengths;
+
+		/* Construct static Huffman lengths as per RFC 1950 */
+		for ( pattern = deflate_static_length_patterns ;
+		      pattern->count ; pattern++ ) {
+			memset ( lengths, pattern->fill, pattern->count );
+			lengths += pattern->count;
+		}
+		deflate->litlen_count = 288;
+		deflate->distance_count = 32;
+		goto construct_alphabets;
+	}
+
+ dynamic_block:
+
+ dynamic_header: {
+		int header;
+		unsigned int hlit;
+		unsigned int hdist;
+		unsigned int hclen;
+
+		/* Extract block header */
+		header = deflate_extract ( deflate, in, DEFLATE_DYNAMIC_BITS );
+		if ( header < 0 ) {
+			deflate->resume = &&dynamic_header;
+			return 0;
+		}
+
+		/* Parse header */
+		hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
+			 DEFLATE_DYNAMIC_HLIT_MASK );
+		hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
+			  DEFLATE_DYNAMIC_HDIST_MASK );
+		hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
+			  DEFLATE_DYNAMIC_HCLEN_MASK );
+		deflate->litlen_count = ( hlit + 257 );
+		deflate->distance_count = ( hdist + 1 );
+		deflate->length_index = 0;
+		deflate->length_target = ( hclen + 4 );
+		DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d "
+			"litlen, %d distance\n", deflate,
+			deflate->length_target, deflate->litlen_count,
+			deflate->distance_count );
+
+		/* Prepare for decoding code length code lengths */
+		memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
+	}
+
+ dynamic_codelen: {
+		int len;
+		unsigned int index;
+		int rc;
+
+		/* Extract all code lengths */
+		while ( deflate->length_index < deflate->length_target ) {
+
+			/* Extract code length length */
+			len = deflate_extract ( deflate, in,
+						DEFLATE_CODELEN_BITS );
+			if ( len < 0 ) {
+				deflate->resume = &&dynamic_codelen;
+				return 0;
+			}
+
+			/* Store code length */
+			index = deflate_codelen_map[deflate->length_index++];
+			deflate_set_length ( deflate, index, len );
+			DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
+				deflate, index, len );
+		}
+
+		/* Generate code length alphabet */
+		if ( ( rc = deflate_alphabet ( deflate,
+					       &deflate->distance_codelen,
+					       ( DEFLATE_CODELEN_MAX_CODE + 1 ),
+					       0 ) ) != 0 )
+			return rc;
+
+		/* Prepare for decoding literal/length/distance code lengths */
+		memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
+		deflate->length_index = 0;
+		deflate->length_target = ( deflate->litlen_count +
+					   deflate->distance_count );
+		deflate->length = 0;
+	}
+
+ dynamic_litlen_distance: {
+		int len;
+		int index;
+
+		/* Decode literal/length/distance code length */
+		len = deflate_decode ( deflate, in, &deflate->distance_codelen);
+		if ( len < 0 ) {
+			deflate->resume = &&dynamic_litlen_distance;
+			return 0;
+		}
+
+		/* Prepare for extra bits */
+		if ( len < 16 ) {
+			deflate->length = len;
+			deflate->extra_bits = 0;
+			deflate->dup_len = 1;
+		} else {
+			static const uint8_t dup_len[3] = { 3, 3, 11 };
+			static const uint8_t extra_bits[3] = { 2, 3, 7 };
+			index = ( len - 16 );
+			deflate->dup_len = dup_len[index];
+			deflate->extra_bits = extra_bits[index];
+			if ( index )
+				deflate->length = 0;
+		}
+	}
+
+ dynamic_litlen_distance_extra: {
+		int extra;
+		unsigned int dup_len;
+
+		/* Extract extra bits */
+		extra = deflate_extract ( deflate, in, deflate->extra_bits );
+		if ( extra < 0 ) {
+			deflate->resume = &&dynamic_litlen_distance_extra;
+			return 0;
+		}
+
+		/* Store code lengths */
+		dup_len = ( deflate->dup_len + extra );
+		while ( ( deflate->length_index < deflate->length_target ) &&
+			dup_len-- ) {
+			deflate_set_length ( deflate, deflate->length_index++,
+					     deflate->length );
+		}
+
+		/* Process next literal/length or distance code
+		 * length, if more are required.
+		 */
+		if ( deflate->length_index < deflate->length_target )
+			goto dynamic_litlen_distance;
+
+		/* Construct alphabets */
+		goto construct_alphabets;
+	}
+
+ construct_alphabets: {
+		unsigned int distance_offset = deflate->litlen_count;
+		unsigned int distance_count = deflate->distance_count;
+		int rc;
+
+		/* Generate literal/length alphabet */
+		if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen,
+					       deflate->litlen_count, 0 ) ) !=0)
+			return rc;
+
+		/* Handle degenerate case of a single distance code
+		 * (for which it is impossible to construct a valid,
+		 * complete Huffman alphabet).  RFC 1951 states:
+		 *
+		 *   If only one distance code is used, it is encoded
+		 *   using one bit, not zero bits; in this case there
+		 *   is a single code length of one, with one unused
+		 *   code.  One distance code of zero bits means that
+		 *   there are no distance codes used at all (the data
+		 *   is all literals).
+		 *
+		 * If we have only a single distance code, then we
+		 * instead use two distance codes both with length 1.
+		 * This results in a valid Huffman alphabet.  The code
+		 * "0" will mean distance code 0 (which is either
+		 * correct or irrelevant), and the code "1" will mean
+		 * distance code 1 (which is always irrelevant).
+		 */
+		if ( deflate->distance_count == 1 ) {
+
+			deflate->lengths[0] = 0x11;
+			distance_offset = 0;
+			distance_count = 2;
+		}
+
+		/* Generate distance alphabet */
+		if ( ( rc = deflate_alphabet ( deflate,
+					       &deflate->distance_codelen,
+					       distance_count,
+					       distance_offset ) ) != 0 )
+			return rc;
+	}
+
+ lzhuf_litlen: {
+		int code;
+		uint8_t byte;
+		unsigned int extra;
+		unsigned int bits;
+
+		/* Decode Huffman codes */
+		while ( 1 ) {
+
+			/* Decode Huffman code */
+			code = deflate_decode ( deflate, in, &deflate->litlen );
+			if ( code < 0 ) {
+				deflate->resume = &&lzhuf_litlen;
+				return 0;
+			}
+
+			/* Handle according to code type */
+			if ( code < DEFLATE_LITLEN_END ) {
+
+				/* Literal value: copy to output buffer */
+				byte = code;
+				DBGCP ( deflate, "DEFLATE %p literal %#02x "
+					"('%c')\n", deflate, byte,
+					( isprint ( byte ) ? byte : '.' ) );
+				deflate_copy ( out, virt_to_user ( &byte ), 0,
+					       sizeof ( byte ) );
+
+			} else if ( code == DEFLATE_LITLEN_END ) {
+
+				/* End of block */
+				goto block_done;
+
+			} else {
+
+				/* Length code: process extra bits */
+				extra = ( code - DEFLATE_LITLEN_END - 1 );
+				if ( extra < 28 ) {
+					bits = ( extra / 4 );
+					if ( bits )
+						bits--;
+					deflate->extra_bits = bits;
+					deflate->dup_len =
+						deflate_litlen_base[extra];
+				} else {
+					deflate->extra_bits = 0;
+					deflate->dup_len = 258;
+				}
+				goto lzhuf_litlen_extra;
+			}
+		}
+	}
+
+ lzhuf_litlen_extra: {
+		int extra;
+
+		/* Extract extra bits */
+		extra = deflate_extract ( deflate, in, deflate->extra_bits );
+		if ( extra < 0 ) {
+			deflate->resume = &&lzhuf_litlen_extra;
+			return 0;
+		}
+
+		/* Update duplicate length */
+		deflate->dup_len += extra;
+	}
+
+ lzhuf_distance: {
+		int code;
+		unsigned int extra;
+		unsigned int bits;
+
+		/* Decode Huffman code */
+		code = deflate_decode ( deflate, in,
+					&deflate->distance_codelen );
+		if ( code < 0 ) {
+			deflate->resume = &&lzhuf_distance;
+			return 0;
+		}
+
+		/* Process extra bits */
+		extra = code;
+		bits = ( extra / 2 );
+		if ( bits )
+			bits--;
+		deflate->extra_bits = bits;
+		deflate->dup_distance = deflate_distance_base[extra];
+	}
+
+ lzhuf_distance_extra: {
+		int extra;
+		size_t dup_len;
+		size_t dup_distance;
+
+		/* Extract extra bits */
+		extra = deflate_extract ( deflate, in, deflate->extra_bits );
+		if ( extra < 0 ) {
+			deflate->resume = &&lzhuf_distance_extra;
+			return 0;
+		}
+
+		/* Update duplicate distance */
+		dup_distance = ( deflate->dup_distance + extra );
+		dup_len = deflate->dup_len;
+		DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance "
+			"%zd\n", deflate, dup_len, dup_distance );
+
+		/* Sanity check */
+		if ( dup_distance > out->offset ) {
+			DBGC ( deflate, "DEFLATE %p bad distance %zd (max "
+			       "%zd)\n", deflate, dup_distance, out->offset );
+			return -EINVAL;
+		}
+
+		/* Copy data, allowing for overlap */
+		deflate_copy ( out, out->data, ( out->offset - dup_distance ),
+			       dup_len );
+
+		/* Process next literal/length symbol */
+		goto lzhuf_litlen;
+	}
+
+ block_done: {
+
+		DBGCP ( deflate, "DEFLATE %p end of block\n", deflate );
+
+		/* If this was not the final block, process next block header */
+		if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ))
+			goto block_header;
+
+		/* Otherwise, process footer (if any) */
+		switch ( deflate->format ) {
+		case DEFLATE_RAW:	goto finished;
+		case DEFLATE_ZLIB:	goto zlib_footer;
+		default:		assert ( 0 );
+		}
+	}
+
+ zlib_footer: {
+
+		/* Discard any bits up to the next byte boundary */
+		deflate_discard_to_byte ( deflate );
+	}
+
+ zlib_adler32: {
+		int excess;
+
+		/* Accumulate the 32 bits of checksum.  We don't check
+		 * the value, stop processing immediately afterwards,
+		 * and so don't have to worry about the nasty corner
+		 * cases involved in calling deflate_extract() to
+		 * obtain a full 32 bits.
+		 */
+		excess = deflate_accumulate ( deflate, in, ZLIB_ADLER32_BITS );
+		if ( excess < 0 ) {
+			deflate->resume = &&zlib_adler32;
+			return 0;
+		}
+
+		/* Finish processing */
+		goto finished;
+	}
+
+ finished: {
+		/* Mark as finished and terminate */
+		DBGCP ( deflate, "DEFLATE %p finished\n", deflate );
+		deflate->resume = NULL;
+		return 0;
+	}
+}
+
+/**
+ * Initialise decompressor
+ *
+ * @v deflate		Decompressor
+ * @v format		Compression format code
+ */
+void deflate_init ( struct deflate *deflate, enum deflate_format format ) {
+	static int global_init_done;
+	uint8_t i;
+	uint8_t bit;
+	uint8_t byte;
+	unsigned int base;
+	unsigned int bits;
+
+	/* Perform global initialisation if required */
+	if ( ! global_init_done ) {
+
+		/* Initialise byte reversal table */
+		for ( i = 255 ; i ; i-- ) {
+			for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) {
+				byte <<= 1;
+				if ( i & bit )
+					byte |= 1;
+			}
+			deflate_reverse[i] = byte;
+		}
+
+		/* Initialise literal/length extra bits table */
+		base = 3;
+		for ( i = 0 ; i < 28 ; i++ ) {
+			bits = ( i / 4 );
+			if ( bits )
+				bits--;
+			deflate_litlen_base[i] = base;
+			base += ( 1 << bits );
+		}
+		assert ( base == 259 ); /* sic */
+
+		/* Initialise distance extra bits table */
+		base = 1;
+		for ( i = 0 ; i < 30 ; i++ ) {
+			bits = ( i / 2 );
+			if ( bits )
+				bits--;
+			deflate_distance_base[i] = base;
+			base += ( 1 << bits );
+		}
+		assert ( base == 32769 );
+
+		/* Record global initialisation as complete */
+		global_init_done = 1;
+	}
+
+	/* Initialise structure */
+	memset ( deflate, 0, sizeof ( *deflate ) );
+	deflate->format = format;
+}