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