1// Copyright 2015, Joe Tsai. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE.md file.
4
5package brotli
6
7import (
8	"bytes"
9	"strings"
10	"testing"
11)
12
13func TestDictDecoder(t *testing.T) {
14	const abc = "ABC\n"
15	const fox = "The quick brown fox jumped over the lazy dog!\n"
16	const poem = "The Road Not Taken\nRobert Frost\n" +
17		"\n" +
18		"Two roads diverged in a yellow wood,\n" +
19		"And sorry I could not travel both\n" +
20		"And be one traveler, long I stood\n" +
21		"And looked down one as far as I could\n" +
22		"To where it bent in the undergrowth;\n" +
23		"\n" +
24		"Then took the other, as just as fair,\n" +
25		"And having perhaps the better claim,\n" +
26		"Because it was grassy and wanted wear;\n" +
27		"Though as for that the passing there\n" +
28		"Had worn them really about the same,\n" +
29		"\n" +
30		"And both that morning equally lay\n" +
31		"In leaves no step had trodden black.\n" +
32		"Oh, I kept the first for another day!\n" +
33		"Yet knowing how way leads on to way,\n" +
34		"I doubted if I should ever come back.\n" +
35		"\n" +
36		"I shall be telling this with a sigh\n" +
37		"Somewhere ages and ages hence:\n" +
38		"Two roads diverged in a wood, and I-\n" +
39		"I took the one less traveled by,\n" +
40		"And that has made all the difference.\n"
41	var refs = []struct {
42		dist   int // Backward distance (0 if this is an insertion)
43		length int // Length of copy or insertion
44	}{
45		{0, 38}, {33, 3}, {0, 48}, {79, 3}, {0, 11}, {34, 5}, {0, 6}, {23, 7},
46		{0, 8}, {50, 3}, {0, 2}, {69, 3}, {34, 5}, {0, 4}, {97, 3}, {0, 4},
47		{43, 5}, {0, 6}, {7, 4}, {88, 7}, {0, 12}, {80, 3}, {0, 2}, {141, 4},
48		{0, 1}, {196, 3}, {0, 3}, {157, 3}, {0, 6}, {181, 3}, {0, 2}, {23, 3},
49		{77, 3}, {28, 5}, {128, 3}, {110, 4}, {70, 3}, {0, 4}, {85, 6}, {0, 2},
50		{182, 6}, {0, 4}, {133, 3}, {0, 7}, {47, 5}, {0, 20}, {112, 5}, {0, 1},
51		{58, 3}, {0, 8}, {59, 3}, {0, 4}, {173, 3}, {0, 5}, {114, 3}, {0, 4},
52		{92, 5}, {0, 2}, {71, 3}, {0, 2}, {76, 5}, {0, 1}, {46, 3}, {96, 4},
53		{130, 4}, {0, 3}, {360, 3}, {0, 3}, {178, 5}, {0, 7}, {75, 3}, {0, 3},
54		{45, 6}, {0, 6}, {299, 6}, {180, 3}, {70, 6}, {0, 1}, {48, 3}, {66, 4},
55		{0, 3}, {47, 5}, {0, 9}, {325, 3}, {0, 1}, {359, 3}, {318, 3}, {0, 2},
56		{199, 3}, {0, 1}, {344, 3}, {0, 3}, {248, 3}, {0, 10}, {310, 3}, {0, 3},
57		{93, 6}, {0, 3}, {252, 3}, {157, 4}, {0, 2}, {273, 5}, {0, 14}, {99, 4},
58		{0, 1}, {464, 4}, {0, 2}, {92, 4}, {495, 3}, {0, 1}, {322, 4}, {16, 4},
59		{0, 3}, {402, 3}, {0, 2}, {237, 4}, {0, 2}, {432, 4}, {0, 1}, {483, 5},
60		{0, 2}, {294, 4}, {0, 2}, {306, 3}, {113, 5}, {0, 1}, {26, 4}, {164, 3},
61		{488, 4}, {0, 1}, {542, 3}, {248, 6}, {0, 5}, {205, 3}, {0, 8}, {48, 3},
62		{449, 6}, {0, 2}, {192, 3}, {328, 4}, {9, 5}, {433, 3}, {0, 3}, {622, 25},
63		{615, 5}, {46, 5}, {0, 2}, {104, 3}, {475, 10}, {549, 3}, {0, 4}, {597, 8},
64		{314, 3}, {0, 1}, {473, 6}, {317, 5}, {0, 1}, {400, 3}, {0, 3}, {109, 3},
65		{151, 3}, {48, 4}, {0, 4}, {125, 3}, {108, 3}, {0, 2},
66	}
67
68	var want string
69	var buf bytes.Buffer
70	var dd dictDecoder
71	dd.Init(1 << 11)
72
73	checkLastBytes := func(str string) {
74		if len(str) < 2 {
75			str = "\x00\x00" + str
76		}
77		str = str[len(str)-2:]
78		p1, p2 := dd.LastBytes()
79		got := string([]byte{p2, p1})
80		if got != str {
81			t.Errorf("last bytes mismatch: got %q, want %q", got, str)
82		}
83	}
84	writeCopy := func(dist, length int) {
85		if dist < length {
86			cnt := (dist + length - 1) / dist
87			want += strings.Repeat(want[len(want)-dist:], cnt)[:length]
88		} else {
89			want += want[len(want)-dist:][:length]
90		}
91
92		for length > 0 {
93			length -= dd.WriteCopy(dist, length)
94			if dd.AvailSize() == 0 {
95				buf.Write(dd.ReadFlush())
96			}
97		}
98
99		checkLastBytes(want)
100	}
101	writeString := func(str string) {
102		want += str
103
104		for len(str) > 0 {
105			cnt := copy(dd.WriteSlice(), str)
106			str = str[cnt:]
107			dd.WriteMark(cnt)
108			if dd.AvailSize() == 0 {
109				buf.Write(dd.ReadFlush())
110			}
111		}
112
113		checkLastBytes(want)
114	}
115
116	writeString("")
117	writeString(".")
118	str := poem
119	for _, ref := range refs {
120		if ref.dist == 0 {
121			writeString(str[:ref.length])
122		} else {
123			writeCopy(ref.dist, ref.length)
124		}
125		str = str[ref.length:]
126	}
127	writeCopy(dd.HistSize(), 33)
128	writeString(abc)
129	writeCopy(len(abc), 59*len(abc))
130	writeString(fox)
131	writeCopy(len(fox), 9*len(fox))
132	writeString(".")
133	writeCopy(1, 9)
134	writeString(strings.ToUpper(poem))
135	writeCopy(len(poem), 7*len(poem))
136	writeCopy(dd.HistSize(), 10)
137
138	buf.Write(dd.ReadFlush())
139	if buf.String() != want {
140		t.Errorf("final string mismatch:\ngot  %q\nwant %q", buf.String(), want)
141	}
142}
143
144func BenchmarkDictDecoderCopy(b *testing.B) {
145	nb := 1 << 24
146	b.SetBytes(int64(nb))
147
148	for i := 0; i < b.N; i++ {
149		var dd dictDecoder
150		dd.Init(1 << 16)
151
152		copy(dd.WriteSlice(), "abc")
153		dd.WriteMark(3)
154
155		dist, length := 3, nb
156		for length > 0 {
157			length -= dd.WriteCopy(dist, length)
158			if dd.AvailSize() == 0 {
159				dd.ReadFlush()
160			}
161		}
162	}
163}
164