Fix std/deflate degenerate H-D Huffman table
RFC 1951 section 3.2.7. "Compression with dynamic Huffman codes
(BTYPE=10)" says, "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."
I had previously mis-read that excerpt to also require that the sole
distance code was the shortest distance (code 0, a distance of 1).
Fixes #66
diff --git a/release/c/wuffs-unsupported-snapshot.c b/release/c/wuffs-unsupported-snapshot.c
index 9ce5434..0875822 100644
--- a/release/c/wuffs-unsupported-snapshot.c
+++ b/release/c/wuffs-unsupported-snapshot.c
@@ -27008,14 +27008,17 @@
v_i += 1;
}
if (v_remaining != 0) {
- if ((a_which == 1) &&
- (v_counts[1] == 1) &&
- (self->private_data.f_code_lengths[a_n_codes0] == 1) &&
- ((((uint32_t)(v_counts[0])) + a_n_codes0 + 1) == a_n_codes1)) {
- self->private_impl.f_n_huffs_bits[1] = 1;
- self->private_data.f_huffs[1][0] = (WUFFS_DEFLATE__DCODE_MAGIC_NUMBERS[0] | 1);
- self->private_data.f_huffs[1][1] = (WUFFS_DEFLATE__DCODE_MAGIC_NUMBERS[31] | 1);
- return wuffs_base__make_status(NULL);
+ if ((a_which == 1) && (v_counts[1] == 1) && ((((uint32_t)(v_counts[0])) + a_n_codes0 + 1) == a_n_codes1)) {
+ v_i = 0;
+ while (v_i <= 29) {
+ if (self->private_data.f_code_lengths[(a_n_codes0 + v_i)] == 1) {
+ self->private_impl.f_n_huffs_bits[1] = 1;
+ self->private_data.f_huffs[1][0] = (WUFFS_DEFLATE__DCODE_MAGIC_NUMBERS[v_i] | 1);
+ self->private_data.f_huffs[1][1] = (WUFFS_DEFLATE__DCODE_MAGIC_NUMBERS[31] | 1);
+ return wuffs_base__make_status(NULL);
+ }
+ v_i += 1;
+ }
}
return wuffs_base__make_status(wuffs_deflate__error__bad_huffman_code_under_subscribed);
}
diff --git a/script/make-artificial.go b/script/make-artificial.go
index 575d0c0..e0d2337 100644
--- a/script/make-artificial.go
+++ b/script/make-artificial.go
@@ -587,20 +587,20 @@
return stateDeflateDynamicHuffman, nil
} else if l, d, ok := deflateParseLenDist(line); ok {
- if (l != 3) || (d != 2) {
- return nil, fmt.Errorf("TODO: support len/dist pairs for dynamic Huffman blocks")
+ if (l > 10) || (d > 4) {
+ return nil, fmt.Errorf("TODO: support len/dist ExtraBits > 0 for dynamic Huffman blocks")
}
- // len 3 is code 257, with no extra bits.
- if s := g.huffmans[2][257]; s != "" {
+ // len 3 is code 257, len 4 is code 258, etc. All with no ExtraBits.
+ if s := g.huffmans[2][l+254]; s != "" {
deflateGlobalsWriteDynamicHuffmanBits(s)
} else {
- return nil, fmt.Errorf("no code for literal/length symbol 257")
+ return nil, fmt.Errorf("no code for literal/length symbol %d", l+254)
}
- // dist 2 is code 1, with no extra bits.
- if s := g.huffmans[3][1]; s != "" {
+ // dist 1 is code 0, dist 2 is code 1, etc. All with no ExtraBits.
+ if s := g.huffmans[3][d-1]; s != "" {
deflateGlobalsWriteDynamicHuffmanBits(s)
} else {
- return nil, fmt.Errorf("no code for distance symbol 2")
+ return nil, fmt.Errorf("no code for distance symbol %d", d-1)
}
return stateDeflateDynamicHuffman, nil
diff --git a/std/deflate/decode_deflate.wuffs b/std/deflate/decode_deflate.wuffs
index c24a4d5..947f4f2 100644
--- a/std/deflate/decode_deflate.wuffs
+++ b/std/deflate/decode_deflate.wuffs
@@ -628,17 +628,21 @@
} endwhile
if remaining <> 0 {
// As a special case, allow a degenerate H-D Huffman table, with only
- // one 1-bit code, for the smallest possible distance.
+ // one 1-bit code.
if (args.which == 1) and (counts[1] == 1) and
- (this.code_lengths[args.n_codes0] == 1) and
(((counts[0] as base.u32) + args.n_codes0 + 1) == args.n_codes1) {
- this.n_huffs_bits[1] = 1
- this.huffs[1][0] = DCODE_MAGIC_NUMBERS[0] | 1
- this.huffs[1][1] = DCODE_MAGIC_NUMBERS[31] | 1
- return ok
+ i = 0
+ while i <= 29 {
+ if this.code_lengths[args.n_codes0 + i] == 1 {
+ this.n_huffs_bits[1] = 1
+ this.huffs[1][0] = DCODE_MAGIC_NUMBERS[i] | 1
+ this.huffs[1][1] = DCODE_MAGIC_NUMBERS[31] | 1
+ return ok
+ }
+ i += 1
+ } endwhile
}
-
return "#bad Huffman code (under-subscribed)"
}
diff --git a/test/data/artificial-deflate/degenerate-huffman-unused.deflate b/test/data/artificial-deflate/degenerate-huffman-unused.deflate
index 4751683..d899dd5 100644
--- a/test/data/artificial-deflate/degenerate-huffman-unused.deflate
+++ b/test/data/artificial-deflate/degenerate-huffman-unused.deflate
Binary files differ
diff --git a/test/data/artificial-deflate/degenerate-huffman-unused.deflate.commentary.txt b/test/data/artificial-deflate/degenerate-huffman-unused.deflate.commentary.txt
index 5804323..1da1926 100644
--- a/test/data/artificial-deflate/degenerate-huffman-unused.deflate.commentary.txt
+++ b/test/data/artificial-deflate/degenerate-huffman-unused.deflate.commentary.txt
@@ -2,8 +2,8 @@
adding commentary:
offset xoffset ASCII hex binary
- 000000 0x0000 . 0x05 0b_...._.101 Dynamic Huffman block, final
- 000000 0x0000 . 0x05 0b_0000_0... NumLCodes: 257
+ 000000 0x0000 . 0x04 0b_...._.100 Dynamic Huffman block, non-final
+ 000000 0x0000 . 0x04 0b_0000_0... NumLCodes: 257
000001 0x0001 . 0xC0 0b_...0_0000 NumDCodes: 1
000001 0x0001 . 0xC0 0b_110._.... NumCLCodeLengths: 18
000002 0x0002 ! 0x21 0b_...._...1
@@ -63,4 +63,7 @@
000013 0x000D . 0x89 0b_..0._.... lcode: 111 literal 'o'
000013 0x000D . 0x89 0b_.0.._.... lcode: 111 literal 'o'
000013 0x000D . 0x89 0b_1..._.... lcode: 256 end of block
- 000014 0x000E . 0x01 0b_...._...1
+ 000014 0x000E . 0x1B 0b_...._...1
+
+The second Dynamic Huffman block (the final one) continues after that, but this
+commentary stops here.
diff --git a/test/data/artificial-deflate/degenerate-huffman-unused.deflate.decompressed b/test/data/artificial-deflate/degenerate-huffman-unused.deflate.decompressed
index 1910281..c1eb7d9 100644
--- a/test/data/artificial-deflate/degenerate-huffman-unused.deflate.decompressed
+++ b/test/data/artificial-deflate/degenerate-huffman-unused.deflate.decompressed
@@ -1 +1 @@
-foo
\ No newline at end of file
+fooABCDABC
\ No newline at end of file
diff --git a/test/data/artificial-deflate/degenerate-huffman-unused.deflate.make-artificial.txt b/test/data/artificial-deflate/degenerate-huffman-unused.deflate.make-artificial.txt
index 063f90c..f7598cd 100644
--- a/test/data/artificial-deflate/degenerate-huffman-unused.deflate.make-artificial.txt
+++ b/test/data/artificial-deflate/degenerate-huffman-unused.deflate.make-artificial.txt
@@ -2,7 +2,7 @@
make deflate
-blockDynamicHuffman (final) {
+blockDynamicHuffman (nonFinal) {
huffman CodeLength {
1 00
2 01
@@ -19,9 +19,46 @@
huffman Distance {
# Incomplete. There is no key/value pair whose value starts with "1".
+ #
+ # The sole key/value pair is also unused. (The one below is used.)
0 0
}
literal "foo"
endOfBlock
}
+
+blockDynamicHuffman (final) {
+ huffman CodeLength {
+ 0 00
+ 1 01
+ 2 100
+ 3 101
+ 17 110
+ 18 111
+ }
+
+ huffman Literal/Length {
+ # 65='A', 66='B', 67='C', 68='D', 256=EOB, 257=Length3
+ 65 100
+ 66 101
+ 67 110
+ 68 111
+ 256 00
+ 257 01
+ }
+
+ huffman Distance {
+ # Incomplete. There is no key/value pair whose value starts with "1".
+ #
+ # The sole key/value pair is also used. (The one above is unused.)
+ #
+ # Per the second table in RFC 1951 section 3.2.5. "Compressed blocks
+ # (length and distance codes)", code 3 means a distance of 4.
+ 3 0
+ }
+
+ literal "ABCD"
+ len 3 dist 4
+ endOfBlock
+}
