[xca] Handle blocks which cross 64kB boundaries

The XCA compression scheme as used in bootmgr was found to split the output into 64kB chunks, with a new Huffman symbol length table for each chunk. This behaviour is not documented in the XCA specification, but was discovered empirically. We currently make the assumption that the compression algorithm first splits the output into 64kB chunks, then compresses each chunk separately (while retaining the ability to refer back to previous chunks via LZ77 match symbols). However, some examples have been found in which a single LZ77 match symbol crosses a 64kB boundary within the output stream. This suggests the the compression algorithm starts a new chunk after it has compressed at least 64kB (rather than using a fixed 64kB chunk length). Experiments indicate that changing the decompressor to start a new chunk whenever at least 64kB have been decompressed produces the correct output. Reported-by: Brian Rak <brak@gameservers.com> Reported-by: Anton D. Kachalov <mouse@yandex-team.ru> Reported-by: Sven Dreyer <sven@dreyer-net.de> Signed-off-by: Michael Brown <mbrown@fensystems.co.uk>
ipxe · Mar 19, 2014 · 9bc2119 · 9bc2119
1 parent 4256fcf
commit 9bc2119
Showing 1 changed file with 5 additions and 1 deletion.
diff --git a/src/xca.c b/src/xca.c
@@ -191,6 +191,7 @@ ssize_t xca_decompress ( const void *data, size_t len, void *buf ) {
 	const void *end = ( src + len );
 	uint8_t *out = buf;
 	size_t out_len = 0;
+	size_t out_len_threshold = 0;
 	const struct xca_huf_len *lengths;
 	struct xca_symbols sym;
 	uint32_t accum = 0;
@@ -208,7 +209,7 @@ ssize_t xca_decompress ( const void *data, size_t len, void *buf ) {
 	while ( src < end ) {
 
 		/* (Re)initialise decompressor if applicable */
-		if ( ( out_len % XCA_BLOCK_SIZE ) == 0 ) {
+		if ( out_len >= out_len_threshold ) {
 
 			/* Construct symbol table */
 			lengths = src;
@@ -227,6 +228,9 @@ ssize_t xca_decompress ( const void *data, size_t len, void *buf ) {
 			accum <<= 16;
 			accum |= XCA_GET16 ( src );
 			extra_bits = 16;
+
+			/* Determine next threshold */
+			out_len_threshold = ( out_len + XCA_BLOCK_SIZE );
 		}
 
 		/* Determine symbol */