Let flatecut accept a degenerate Huffman tree
diff --git a/lib/flatecut/flatecut.go b/lib/flatecut/flatecut.go
index 714dcc6..07919bb 100644
--- a/lib/flatecut/flatecut.go
+++ b/lib/flatecut/flatecut.go
@@ -253,7 +253,7 @@
for _, x := range lengths {
h.counts[x]++
}
- if h.counts[0] == uint32(len(lengths)) {
+ if h.counts[0] >= uint32(len(lengths)) {
return 0, 0, errInvalidBadHuffmanTree
}
@@ -284,7 +284,12 @@
}
}
if remaining != 0 {
- return 0, 0, errInvalidBadHuffmanTree
+ if ((h.counts[0] + 1) == uint32(len(lengths))) && (h.counts[1] == 1) {
+ // No-op. We allow a degenerate Huffman tree with only one code (of
+ // length 1 bit).
+ } else {
+ return 0, 0, errInvalidBadHuffmanTree
+ }
}
offsets := [maxCodeBits + 1]uint32{}
diff --git a/lib/flatecut/flatecut_test.go b/lib/flatecut/flatecut_test.go
index 95d94e7..5ba070e 100644
--- a/lib/flatecut/flatecut_test.go
+++ b/lib/flatecut/flatecut_test.go
@@ -15,8 +15,10 @@
package flatecut
import (
+ "bytes"
"compress/flate"
"io"
+ "io/ioutil"
"testing"
"github.com/google/wuffs/internal/testcut"
@@ -109,3 +111,39 @@
t.Fatalf("got %q, want %q", got, want)
}
}
+
+func TestDegenerateHuffmanUnused(t *testing.T) {
+ decode := func(src []byte) string {
+ dst, err := ioutil.ReadAll(
+ flate.NewReader(bytes.NewReader(src)))
+ if err != nil {
+ return err.Error()
+ }
+ return string(dst)
+ }
+
+ full, err := ioutil.ReadFile("../../test/data/artificial/deflate-degenerate-huffman-unused.deflate")
+ if err != nil {
+ t.Fatalf("ReadFile: %v", err)
+ }
+ if len(full) != 15 {
+ t.Fatalf("len(full): got %d, want %d", len(full), 15)
+ }
+
+ if got, want := decode(full), "foo"; got != want {
+ t.Fatalf("before Cut: got %q, want %q", got, want)
+ }
+
+ if encLen, decLen, err := Cut(nil, full, 14); err != nil {
+ t.Fatalf("Cut: %v", err)
+ } else if encLen != 14 {
+ t.Fatalf("encLen: got %d, want %d", encLen, 14)
+ } else if decLen != 2 {
+ t.Fatalf("decLen: got %d, want %d", decLen, 2)
+ }
+
+ if got, want := decode(full[:14]), "fo"; got != want {
+ t.Fatalf("after Cut: got %q, want %q", got, want)
+ }
+
+}
diff --git a/script/make-artificial.go b/script/make-artificial.go
index a8c74c6..4b9c5f6 100644
--- a/script/make-artificial.go
+++ b/script/make-artificial.go
@@ -232,6 +232,7 @@
func stateDeflate(line string) (stateFunc, error) {
g := &deflateGlobals
const (
+ cmdB = "bytes "
cmdBNC = "blockNoCompression "
cmdBFH = "blockFixedHuffman "
)
@@ -240,6 +241,18 @@
retState := stateFunc(nil)
switch {
+ case strings.HasPrefix(line, cmdB):
+ s := line[len(cmdB):]
+ for s != "" {
+ x, ok := uint32(0), false
+ x, s, ok = parseHex(s)
+ if !ok {
+ return nil, fmt.Errorf("bad stateDeflate command: %q", line)
+ }
+ out = append(out, uint8(x))
+ }
+ return stateDeflate, nil
+
case strings.HasPrefix(line, cmdBNC):
s = line[len(cmdBNC):]
retState = stateDeflateNoCompression
diff --git a/test/data/artificial/deflate-degenerate-huffman-unused.deflate b/test/data/artificial/deflate-degenerate-huffman-unused.deflate
new file mode 100644
index 0000000..4751683
--- /dev/null
+++ 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
new file mode 100644
index 0000000..52698b3
--- /dev/null
+++ b/test/data/artificial/deflate-degenerate-huffman-unused.deflate.commentary.txt
@@ -0,0 +1,66 @@
+Running deflate-degenerate-huffman-unused.deflate through script/print-bits.go
+and adding commentary:
+
+ offset xoffset ASCII hex binary
+ 000000 0x0000 . 0x05 0b_...._.101 Dynamic Huffman block, 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
+
+Decode the H-CL Huffman table (NumCLCodeLengths = 18). Recall the peculiar
+code_order: 16, 17, 18, 0, 8, ..., 2, 14, 1, 15:
+
+ 000002 0x0002 ! 0x21 0b_0010_000. CLCodeLengths: 18 x 3 bits
+ 000003 0x0003 . 0x01 0b_0000_0001 CLCLs[ 1] is 2
+ 000004 0x0004 . 0x00 0b_0000_0000 CLCLs[ 2] is 2
+ 000005 0x0005 . 0x00 0b_0000_0000 CLCLs[17] is 2
+ 000006 0x0006 . 0x00 0b_0000_0000 CLCLs[18] is 2
+ 000007 0x0007 . 0x80 0b_1000_0000
+ 000008 0x0008 . 0xA0 0b_.010_0000
+
+The H-CL Huffman table is:
+"00" -> CodeLength=1
+"01" -> CodeLength=2
+"10" -> CodeLength=17 which means a block of ( 3 + 3_extra_bits) zeroes
+"11" -> CodeLength=18 which means a block of (11 + 7_extra_bits) zeroes
+
+Decode the H-L Huffman table (NumLCodes = 257):
+
+ 000008 0x0008 . 0xA0 0b_1..._.... "11" is CL=18: 11+7extra
+ 000009 0x0009 . 0xB7 0b_...._...1
+ 000009 0x0009 . 0xB7 0b_1011_011. 7extra=91: 102 zeroes
+ 000010 0x000A V 0x56 0b_...._..10 "01" is CL= 2 (102='f')
+ 000010 0x000A V 0x56 0b_...._01.. "10" is CL=17: 3+3extra
+ 000010 0x000A V 0x56 0b_.101_.... 3extra=5: 8 zeroes
+ 000010 0x000A V 0x56 0b_0..._.... "00" is CL= 1 (111='o')
+ 000011 0x000B . 0xFE 0b_...._...0
+ 000011 0x000B . 0xFE 0b_...._.11. "11" is CL=18: 11+7extra
+ 000011 0x000B . 0xFE 0b_1111_1... 7extra=127: 138 zeroes
+ 000012 0x000C 7 0x37 0b_...._..11
+ 000012 0x000C 7 0x37 0b_...._01.. "10" is CL=17: 3+3extra
+ 000012 0x000C 7 0x37 0b_.011_.... 3extra=3: 6 zeroes
+ 000012 0x000C 7 0x37 0b_0..._.... "01" is CL=2 (256=EOB)
+ 000013 0x000D . 0x89 0b_...._...1
+
+The H-L Huffman table is:
+"0" -> 'o'
+"10" -> 'f'
+"11" -> EOB
+
+Decode the H-D Huffman table (NumDCodes = 1):
+
+ 000013 0x000D . 0x89 0b_...._.00. "00" is CL= 1 (DCode 0)
+
+The H-D Huffman table is:
+"0" -> 0
+This table is incomplete: there is no entry starting with a "1" bit. It is
+therefore degenerate, but not used below.
+
+Apply H-L and H-D.
+
+ 000013 0x000D . 0x89 0b_...0_1... lcode: 102 literal 'f'
+ 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
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
new file mode 100644
index 0000000..ffd4ded
--- /dev/null
+++ b/test/data/artificial/deflate-degenerate-huffman-unused.deflate.make-artificial.txt
@@ -0,0 +1,7 @@
+# Feed this file to script/make-artificial.go
+
+make deflate
+
+# TODO: blockDynamicHuffman
+# See deflate-degenerate-huffman.deflate.commentary.txt for details.
+bytes 0x05 0xC0 0x21 0x01 0x00 0x00 0x00 0x80 0xA0 0xB7 0x56 0xFE 0x37 0x89 0x01
diff --git a/test/data/artificial/deflate-distance-32768.deflate.commentary.txt b/test/data/artificial/deflate-distance-32768.deflate.commentary.txt
index 84a30b2..fb5d94e 100644
--- a/test/data/artificial/deflate-distance-32768.deflate.commentary.txt
+++ b/test/data/artificial/deflate-distance-32768.deflate.commentary.txt
@@ -18,7 +18,7 @@
000019 0x0013 . 0xE9 0b_...._...1
000019 0x0013 . 0xE9 0b_..10_100. dcode: 5 base: 7
000019 0x0013 . 0xE9 0b_.1.._.... extra: 1 distance: 8
- etc
+ etc
000236 0x00EC . 0xE9 0b_1..._.... lcode: 284 base: 227
000237 0x00ED . 0x91 0b_.001_0001
000237 0x00ED . 0x91 0b_1..._.... extra: 17 length: 244
