1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
// Copyright 2016, Joe Tsai. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE.md file.
package internal
import (
"encoding/hex"
"testing"
)
func TestMoveToFront(t *testing.T) {
vectors := []struct {
input, output string
}{{
input: "",
output: "",
}, {
input: "ff00ff00ff00ff00",
output: "ff01010101010101",
}, {
input: "" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000010000000001",
output: "" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000010100000001",
}, {
input: "" +
"0000000000000000000000010101010101010101010101010101010101010101" +
"0101010101010101010101010101010101010101000000000000000203030004",
output: "" +
"0000000000000000000000010000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000010000000000000203000204",
}, {
input: "00000001",
output: "" +
"00000001",
}, {
input: "" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000100000000",
output: "" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000101000000",
}, {
input: "" +
"0000000000000000010101010101010101010101010101010101010101010101" +
"0101010101010101010101010101010101010101010101010101010101010101" +
"0101010101010101010200000000000000020203030303030304040505050505" +
"0505050505050505050505050505050505050505050505050505050505050505",
output: "" +
"0000000000000000010000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000202000000000000010003000000000004000500000000" +
"0000000000000000000000000000000000000000000000000000000000000000",
}, {
input: "000000010101000202020003030300040404000505050006",
output: "" +
"000000010000010200000103000001040000010500000106",
}, {
input: "" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000001010102020202030202020202" +
"0202020202020202020202020202020202020202020202020202020202020202",
output: "" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000001000002000000030100000000" +
"0000000000000000000000000000000000000000000000000000000000000000",
}, {
input: "" +
"0000000000000000000102020202020202020000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000302020202020202010103030303030304040505050505" +
"0505050505050505050505050505050505050505050505050505050505050505",
output: "" +
"0000000000000000000102000000000000000200000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000302000000000000030002000000000004000500000000" +
"0000000000000000000000000000000000000000000000000000000000000000",
}, {
input: "0000010000000102020201030303010404020105",
output: "" +
"0000010100000102000001030000010400030205",
}, {
input: "" +
"0000000000000000010202010101010101010202020202020202020202020202" +
"0202020202020202020202020202020202020202020202020202020202020202" +
"0202020202020202020201010101010101020202020202020203040000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000201010101010101020205050505050503030606060606" +
"0606060606060606060606060606060606060606060606060606060606060606" +
"0606060606060606060202020202020202000702020202020202040404040404" +
"0404040404040404040404040404040404040404040404040404040404040404",
output: "" +
"0000000000000000010200010000000000000100000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000001000000000000010000000000000003040400000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000304000000000000010005000000000005000600000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000300000000000000050702000000000000070000000000" +
"0000000000000000000000000000000000000000000000000000000000000000",
}, {
input: "" +
"0000000000000001010100020202000303030004040400050505000606060007" +
"070700080808000909090a0a",
output: "" +
"0000000000000001000001020000010300000104000001050000010600000107" +
"000001080000010900000a00",
}, {
input: "" +
"0000010203030303040000050600070507050201070206060804000400020002" +
"06000200000006000905020000080805050a0202000808080808080105080808" +
"0400050205020505050505050b0205040b0505050505050b0605050505050505" +
"0505050505050505050505050505050502050505050505050505050202050505" +
"040502020b0b0b0b020b0b0b0b0b0b02020b0b0b0b0b0b02020b0b0b0b0b0b0b" +
"0b0b0b0b0b0b0b02020b0b0b0b0b0b0b0b0b0b0b0b0b0b0204020b0b0b050b0a" +
"0c0c02010d0d0d0d0d00060b0d0d0d0d020201020d0d0d0d0c0b02020d0d0d07" +
"04040404070606020b050402060602000e020202060205040404060606040202" +
"040404040404040404040404000000000f0f00090f0f0f0f0f0f0f0b09030d0d" +
"0909060909090101010100000909090909090909010101010101010101010101" +
"0101010101010101010101010d0d0d0d0d0d0d10090c0909090909100f0f0f0f" +
"0f0f07070f0f0f0f0f0f0e0e0f0f0f0f0f0f0f0f0c0c0c0c0c0c0c0c0c0c0c0c" +
"0c0c00080d0d0d0d0d0d020b0d0d0d0d030200010d0d0d0d0d0b02040d0d0d07" +
"0202020207060b020202020206060b0e0e040006060208080808080806060606" +
"00000000000000000000000009090909111111110d0d0d0d1212120900000000" +
"000107060a0a0505050500001212121212121212090909090909090909090909" +
"050511040d0d0d0d0d02040b0d070d0d0a0200010d0d0d0d050b02020d0d0d0d" +
"07020202060b0b0b0402050b02050b07010b00050202020202020c0002020202" +
"02020202020202020202020202020202020202020d0d0d0d0d0d0d0d09090909" +
"09090f0912121212121212121210101010101010090909090909090909090909" +
"0909090909090909090909090909090909090909090909090909090909090909" +
"090909090e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e" +
"0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e" +
"0e0e020211111111111111111111080808080808111111111111111111111111" +
"1111111111111111111111111111111111111111111111111111111111111111" +
"111111110e0e0e0e0e0e0e0e0e030303030303030e0e0e0e0e0e0e0e0e0e0e0e" +
"0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e0e" +
"0e0e0e0e03030303030303030303030303030303030303030303030303030303",
output: "" +
"0000010203000000040400050602070301010607030205000807070101040101" +
"04020201000002010908040300060003000a0400040400000000000905020000" +
"0804030501010100000000000b02020403020000000000010902000000000000" +
"0000000000000000000000000000000004010000000000000000000100010000" +
"0401020004000000010100000000000100010000000000010001000000000000" +
"0000000000000001000100000000000000000000000000010301020000030108" +
"0c0004090d00000000090907030000000500050102000000060403000300000c" +
"0a00000001070004050a0503040001090e020000030105050000030000010300" +
"010000000000000000000000050000000f00010e0200000000000008020f0b00" +
"0200080100000d00000007000200000000000000020000000000000000000000" +
"0000000000000000000000000400000000000010030e01000000000209000000" +
"00000e000100000000000e000100000000000000050000000000000000000000" +
"000008100800000000000e0d020000000d03050c040000000005040e0300000b" +
"03000000010e0503000000000200020c0006080400050a000000000002000000" +
"0300000000000000000000000e000000110000000a0000001200000304000000" +
"000c0c0712001200000005000700000000000000070000000000000000000000" +
"0300090c0a000000000c020e030b01000a050a0c040000000907050003000000" +
"070200000c040000090306030202020507020804050000000000100302000000" +
"000000000000000000000000000000000000000009000000000000000c000000" +
"000011010e000000000000000012000000000000020000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000011000000000000000000000000000000000000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000060010000000000000000000110000000000010000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000003000000000000000012000000000000010000000000000000000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000001000000000000000000000000000000000000000000000000000000",
}, {
input: "" +
"0000000000010101010102020202030303030404040405050505050606060707" +
"07070808",
output: "" +
"0000000000010000000002000000030000000400000005000000000600000700" +
"00000800",
}, {
input: "" +
"0000000000000000010001010101010101000000000000000002020303030303" +
"0303030303030303030303030303030303030303030303030303030303030303" +
"0303030303030303030401010101010101040005050505050502020303030303" +
"0303030303030303030303030303030303030303030303030303030303030303",
output: "" +
"0000000000000000010101000000000000010000000000000002000300000000" +
"0000000000000000000000000000000000000000000000000000000000000000" +
"0000000000000000000404000000000000010405000000000005000500000000" +
"0000000000000000000000000000000000000000000000000000000000000000",
}, {
input: "" +
"0000010000000102020101030303010404040105050501060606010707010108" +
"08010109",
output: "" +
"0000010100000102000100030000010400000105000001060000010700010008" +
"00010009",
}}
var mtf MoveToFront
for i, v := range vectors {
input, _ := hex.DecodeString(v.input)
mtf.Encode(input)
output := append([]uint8(nil), input...)
mtf.Decode(input)
if input := hex.EncodeToString(input); input != v.input {
t.Errorf("test %d, input differs:\ngot %v\nwant %v", i, input, v.input)
}
if output := hex.EncodeToString(output); output != v.output {
t.Errorf("test %d, output differs:\ngot %v\nwant %v", i, output, v.output)
}
}
}
|
