Source file
src/hash/crc32/crc32_test.go
1
2
3
4
5 package crc32
6
7 import (
8 "encoding"
9 "fmt"
10 "hash"
11 "internal/testhash"
12 "io"
13 "math/rand"
14 "testing"
15 )
16
17
18 func TestCastagnoliRace(t *testing.T) {
19
20
21
22 ieee := NewIEEE()
23 go MakeTable(Castagnoli)
24 ieee.Write([]byte("hello"))
25 }
26
27 func TestHashInterface(t *testing.T) {
28 testhash.TestHash(t, func() hash.Hash { return NewIEEE() })
29 }
30
31 type test struct {
32 ieee, castagnoli uint32
33 in string
34 halfStateIEEE string
35 halfStateCastagnoli string
36 }
37
38 var golden = []test{
39 {0x0, 0x0, "", "crc\x01ʇ\x91M\x00\x00\x00\x00", "crc\x01wB\x84\x81\x00\x00\x00\x00"},
40 {0xe8b7be43, 0xc1d04330, "a", "crc\x01ʇ\x91M\x00\x00\x00\x00", "crc\x01wB\x84\x81\x00\x00\x00\x00"},
41 {0x9e83486d, 0xe2a22936, "ab", "crc\x01ʇ\x91M跾C", "crc\x01wB\x84\x81\xc1\xd0C0"},
42 {0x352441c2, 0x364b3fb7, "abc", "crc\x01ʇ\x91M跾C", "crc\x01wB\x84\x81\xc1\xd0C0"},
43 {0xed82cd11, 0x92c80a31, "abcd", "crc\x01ʇ\x91M\x9e\x83Hm", "crc\x01wB\x84\x81\xe2\xa2)6"},
44 {0x8587d865, 0xc450d697, "abcde", "crc\x01ʇ\x91M\x9e\x83Hm", "crc\x01wB\x84\x81\xe2\xa2)6"},
45 {0x4b8e39ef, 0x53bceff1, "abcdef", "crc\x01ʇ\x91M5$A\xc2", "crc\x01wB\x84\x816K?\xb7"},
46 {0x312a6aa6, 0xe627f441, "abcdefg", "crc\x01ʇ\x91M5$A\xc2", "crc\x01wB\x84\x816K?\xb7"},
47 {0xaeef2a50, 0xa9421b7, "abcdefgh", "crc\x01ʇ\x91M\xed\x82\xcd\x11", "crc\x01wB\x84\x81\x92\xc8\n1"},
48 {0x8da988af, 0x2ddc99fc, "abcdefghi", "crc\x01ʇ\x91M\xed\x82\xcd\x11", "crc\x01wB\x84\x81\x92\xc8\n1"},
49 {0x3981703a, 0xe6599437, "abcdefghij", "crc\x01ʇ\x91M\x85\x87\xd8e", "crc\x01wB\x84\x81\xc4P֗"},
50 {0x6b9cdfe7, 0xb2cc01fe, "Discard medicine more than two years old.", "crc\x01ʇ\x91M\xfd\xe5\xc2J", "crc\x01wB\x84\x81S\"(\xe0"},
51 {0xc90ef73f, 0xe28207f, "He who has a shady past knows that nice guys finish last.", "crc\x01ʇ\x91M\x01Nj+", "crc\x01wB\x84\x81'\xdaR\x15"},
52 {0xb902341f, 0xbe93f964, "I wouldn't marry him with a ten foot pole.", "crc\x01ʇ\x91M\x9d\x13\xce\x10", "crc\x01wB\x84\x81\xc3\xed\xabG"},
53 {0x42080e8, 0x9e3be0c3, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave", "crc\x01ʇ\x91M-\xed\xf7\x94", "crc\x01wB\x84\x81\xce\xceb\x81"},
54 {0x154c6d11, 0xf505ef04, "The days of the digital watch are numbered. -Tom Stoppard", "crc\x01ʇ\x91MOa\xa5\r", "crc\x01wB\x84\x81\xd3s\x9dP"},
55 {0x4c418325, 0x85d3dc82, "Nepal premier won't resign.", "crc\x01ʇ\x91M\xa8S9\x85", "crc\x01wB\x84\x81{\x90\x8a\x14"},
56 {0x33955150, 0xc5142380, "For every action there is an equal and opposite government program.", "crc\x01ʇ\x91Ma\xe9>\x86", "crc\x01wB\x84\x81\xaa@\xc4\x1c"},
57 {0x26216a4b, 0x75eb77dd, "His money is twice tainted: 'taint yours and 'taint mine.", "crc\x01ʇ\x91M\\\x1an\x88", "crc\x01wB\x84\x81W\a8Z"},
58 {0x1abbe45e, 0x91ebe9f7, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977", "crc\x01ʇ\x91M\xb7\xf5\xf2\xca", "crc\x01wB\x84\x81\xc4o\x9d\x85"},
59 {0xc89a94f7, 0xf0b1168e, "It's a tiny change to the code and not completely disgusting. - Bob Manchek", "crc\x01ʇ\x91M\x84g1\xe8", "crc\x01wB\x84\x81#\x98\f\xab"},
60 {0xab3abe14, 0x572b74e2, "size: a.out: bad magic", "crc\x01ʇ\x91M\x8a\x0f\xad\b", "crc\x01wB\x84\x81\x80\xc9n\xd8"},
61 {0xbab102b6, 0x8a58a6d5, "The major problem is with sendmail. -Mark Horton", "crc\x01ʇ\x91M\a\xf0\xb3\x15", "crc\x01wB\x84\x81liS\xcc"},
62 {0x999149d7, 0x9c426c50, "Give me a rock, paper and scissors and I will move the world. CCFestoon", "crc\x01ʇ\x91M\x0fa\xbc.", "crc\x01wB\x84\x81\xdb͏C"},
63 {0x6d52a33c, 0x735400a4, "If the enemy is within range, then so are you.", "crc\x01ʇ\x91My\x1b\x99\xf8", "crc\x01wB\x84\x81\xaaB\x037"},
64 {0x90631e8d, 0xbec49c95, "It's well we cannot hear the screams/That we create in others' dreams.", "crc\x01ʇ\x91M\bqfY", "crc\x01wB\x84\x81\x16y\xa1\xd2"},
65 {0x78309130, 0xa95a2079, "You remind me of a TV show, but that's all right: I watch it anyway.", "crc\x01ʇ\x91M\xbdO,\xc2", "crc\x01wB\x84\x81f&\xc5\xe4"},
66 {0x7d0a377f, 0xde2e65c5, "C is as portable as Stonehedge!!", "crc\x01ʇ\x91M\xf7\xd6\x00\xd5", "crc\x01wB\x84\x81de\\\xf8"},
67 {0x8c79fd79, 0x297a88ed, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley", "crc\x01ʇ\x91Ml+\xb8\xa7", "crc\x01wB\x84\x81\xbf\xd6S\xdd"},
68 {0xa20b7167, 0x66ed1d8b, "The fugacity of a constituent in a mixture of gases at a given temperature is proportional to its mole fraction. Lewis-Randall Rule", "crc\x01ʇ\x91M<lR[", "crc\x01wB\x84\x81{\xaco\xb1"},
69 {0x8e0bb443, 0xdcded527, "How can you write a big system without C++? -Paul Glick", "crc\x01ʇ\x91M\x0e\x88\x89\xed", "crc\x01wB\x84\x813\xd7C\u007f"},
70 }
71
72
73
74 func testGoldenIEEE(t *testing.T, crcFunc func(b []byte) uint32) {
75 for _, g := range golden {
76 if crc := crcFunc([]byte(g.in)); crc != g.ieee {
77 t.Errorf("IEEE(%s) = 0x%x want 0x%x", g.in, crc, g.ieee)
78 }
79 }
80 }
81
82
83
84 func testGoldenCastagnoli(t *testing.T, crcFunc func(b []byte) uint32) {
85 for _, g := range golden {
86 if crc := crcFunc([]byte(g.in)); crc != g.castagnoli {
87 t.Errorf("Castagnoli(%s) = 0x%x want 0x%x", g.in, crc, g.castagnoli)
88 }
89 }
90 }
91
92
93
94 func testCrossCheck(t *testing.T, crcFunc1, crcFunc2 func(crc uint32, b []byte) uint32) {
95
96
97
98 lengths := []int{0, 1, 2, 3, 4, 5, 10, 16, 50, 63, 64, 65, 100,
99 127, 128, 129, 255, 256, 257, 300, 312, 384, 416, 448, 480,
100 500, 501, 502, 503, 504, 505, 512, 513, 1000, 1024, 2000,
101 4030, 4031, 4032, 4033, 4036, 4040, 4048, 4096, 5000, 10000}
102 for _, length := range lengths {
103 p := make([]byte, length)
104 _, _ = rand.Read(p)
105 crcInit := uint32(rand.Int63())
106 crc1 := crcFunc1(crcInit, p)
107 crc2 := crcFunc2(crcInit, p)
108 if crc1 != crc2 {
109 t.Errorf("mismatch: 0x%x vs 0x%x (buffer length %d)", crc1, crc2, length)
110 }
111 }
112 }
113
114
115 func TestSimple(t *testing.T) {
116 tab := simpleMakeTable(IEEE)
117 testGoldenIEEE(t, func(b []byte) uint32 {
118 return simpleUpdate(0, tab, b)
119 })
120
121 tab = simpleMakeTable(Castagnoli)
122 testGoldenCastagnoli(t, func(b []byte) uint32 {
123 return simpleUpdate(0, tab, b)
124 })
125 }
126
127 func TestGoldenMarshal(t *testing.T) {
128 t.Run("IEEE", func(t *testing.T) {
129 for _, g := range golden {
130 h := New(IEEETable)
131 h2 := New(IEEETable)
132
133 io.WriteString(h, g.in[:len(g.in)/2])
134
135 state, err := h.(encoding.BinaryMarshaler).MarshalBinary()
136 if err != nil {
137 t.Errorf("could not marshal: %v", err)
138 continue
139 }
140
141 stateAppend, err := h.(encoding.BinaryAppender).AppendBinary(make([]byte, 4, 32))
142 if err != nil {
143 t.Errorf("could not marshal: %v", err)
144 continue
145 }
146 stateAppend = stateAppend[4:]
147
148 if string(state) != g.halfStateIEEE {
149 t.Errorf("IEEE(%q) state = %q, want %q", g.in, state, g.halfStateIEEE)
150 continue
151 }
152
153 if string(stateAppend) != g.halfStateIEEE {
154 t.Errorf("IEEE(%q) state = %q, want %q", g.in, stateAppend, g.halfStateIEEE)
155 continue
156 }
157
158 if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state); err != nil {
159 t.Errorf("could not unmarshal: %v", err)
160 continue
161 }
162
163 io.WriteString(h, g.in[len(g.in)/2:])
164 io.WriteString(h2, g.in[len(g.in)/2:])
165
166 if h.Sum32() != h2.Sum32() {
167 t.Errorf("IEEE(%s) = 0x%x != marshaled 0x%x", g.in, h.Sum32(), h2.Sum32())
168 }
169 }
170 })
171 t.Run("Castagnoli", func(t *testing.T) {
172 table := MakeTable(Castagnoli)
173 for _, g := range golden {
174 h := New(table)
175 h2 := New(table)
176
177 io.WriteString(h, g.in[:len(g.in)/2])
178
179 state, err := h.(encoding.BinaryMarshaler).MarshalBinary()
180 if err != nil {
181 t.Errorf("could not marshal: %v", err)
182 continue
183 }
184
185 stateAppend, err := h.(encoding.BinaryAppender).AppendBinary(make([]byte, 4, 32))
186 if err != nil {
187 t.Errorf("could not marshal: %v", err)
188 continue
189 }
190 stateAppend = stateAppend[4:]
191
192 if string(state) != g.halfStateCastagnoli {
193 t.Errorf("Castagnoli(%q) state = %q, want %q", g.in, state, g.halfStateCastagnoli)
194 continue
195 }
196
197 if string(stateAppend) != g.halfStateCastagnoli {
198 t.Errorf("Castagnoli(%q) state = %q, want %q", g.in, stateAppend, g.halfStateCastagnoli)
199 continue
200 }
201
202 if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state); err != nil {
203 t.Errorf("could not unmarshal: %v", err)
204 continue
205 }
206
207 io.WriteString(h, g.in[len(g.in)/2:])
208 io.WriteString(h2, g.in[len(g.in)/2:])
209
210 if h.Sum32() != h2.Sum32() {
211 t.Errorf("Castagnoli(%s) = 0x%x != marshaled 0x%x", g.in, h.Sum32(), h2.Sum32())
212 }
213 }
214 })
215 }
216
217 func TestMarshalTableMismatch(t *testing.T) {
218 h1 := New(IEEETable)
219 h2 := New(MakeTable(Castagnoli))
220
221 state1, err := h1.(encoding.BinaryMarshaler).MarshalBinary()
222 if err != nil {
223 t.Errorf("could not marshal: %v", err)
224 }
225
226 if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state1); err == nil {
227 t.Errorf("no error when one was expected")
228 }
229 }
230
231
232 func TestSlicing(t *testing.T) {
233 tab := slicingMakeTable(IEEE)
234 testGoldenIEEE(t, func(b []byte) uint32 {
235 return slicingUpdate(0, tab, b)
236 })
237
238 tab = slicingMakeTable(Castagnoli)
239 testGoldenCastagnoli(t, func(b []byte) uint32 {
240 return slicingUpdate(0, tab, b)
241 })
242
243
244 for _, poly := range []uint32{IEEE, Castagnoli, Koopman, 0xD5828281} {
245 t1 := simpleMakeTable(poly)
246 f1 := func(crc uint32, b []byte) uint32 {
247 return simpleUpdate(crc, t1, b)
248 }
249 t2 := slicingMakeTable(poly)
250 f2 := func(crc uint32, b []byte) uint32 {
251 return slicingUpdate(crc, t2, b)
252 }
253 testCrossCheck(t, f1, f2)
254 }
255 }
256
257 func TestArchIEEE(t *testing.T) {
258 if !archAvailableIEEE() {
259 t.Skip("Arch-specific IEEE not available.")
260 }
261 archInitIEEE()
262 slicingTable := slicingMakeTable(IEEE)
263 testCrossCheck(t, archUpdateIEEE, func(crc uint32, b []byte) uint32 {
264 return slicingUpdate(crc, slicingTable, b)
265 })
266 }
267
268 func TestArchCastagnoli(t *testing.T) {
269 if !archAvailableCastagnoli() {
270 t.Skip("Arch-specific Castagnoli not available.")
271 }
272 archInitCastagnoli()
273 slicingTable := slicingMakeTable(Castagnoli)
274 testCrossCheck(t, archUpdateCastagnoli, func(crc uint32, b []byte) uint32 {
275 return slicingUpdate(crc, slicingTable, b)
276 })
277 }
278
279 func TestGolden(t *testing.T) {
280 testGoldenIEEE(t, ChecksumIEEE)
281
282
283
284 for delta := 1; delta <= 7; delta++ {
285 testGoldenIEEE(t, func(b []byte) uint32 {
286 ieee := NewIEEE()
287 d := delta
288 if d >= len(b) {
289 d = len(b)
290 }
291 ieee.Write(b[:d])
292 ieee.Write(b[d:])
293 return ieee.Sum32()
294 })
295 }
296
297 castagnoliTab := MakeTable(Castagnoli)
298 if castagnoliTab == nil {
299 t.Errorf("nil Castagnoli Table")
300 }
301
302 testGoldenCastagnoli(t, func(b []byte) uint32 {
303 castagnoli := New(castagnoliTab)
304 castagnoli.Write(b)
305 return castagnoli.Sum32()
306 })
307
308
309
310 for delta := 1; delta <= 7; delta++ {
311 testGoldenCastagnoli(t, func(b []byte) uint32 {
312 castagnoli := New(castagnoliTab)
313 d := delta
314 if d >= len(b) {
315 d = len(b)
316 }
317 castagnoli.Write(b[:d])
318 castagnoli.Write(b[d:])
319 return castagnoli.Sum32()
320 })
321 }
322 }
323
324 func BenchmarkCRC32(b *testing.B) {
325 b.Run("poly=IEEE", benchmarkAll(NewIEEE()))
326 b.Run("poly=Castagnoli", benchmarkAll(New(MakeTable(Castagnoli))))
327 b.Run("poly=Koopman", benchmarkAll(New(MakeTable(Koopman))))
328 }
329
330 func benchmarkAll(h hash.Hash32) func(b *testing.B) {
331 return func(b *testing.B) {
332 for _, size := range []int{15, 40, 512, 1 << 10, 4 << 10, 32 << 10} {
333 name := fmt.Sprint(size)
334 if size >= 1024 {
335 name = fmt.Sprintf("%dkB", size/1024)
336 }
337 b.Run("size="+name, func(b *testing.B) {
338 for align := 0; align <= 1; align++ {
339 b.Run(fmt.Sprintf("align=%d", align), func(b *testing.B) {
340 benchmark(b, h, int64(size), int64(align))
341 })
342 }
343 })
344 }
345 }
346 }
347
348 func benchmark(b *testing.B, h hash.Hash32, n, alignment int64) {
349 b.SetBytes(n)
350 data := make([]byte, n+alignment)
351 data = data[alignment:]
352 for i := range data {
353 data[i] = byte(i)
354 }
355 in := make([]byte, 0, h.Size())
356
357
358 h.Reset()
359 h.Write(data)
360 h.Sum(in)
361
362 in = in[:0]
363
364 b.ResetTimer()
365 for i := 0; i < b.N; i++ {
366 h.Reset()
367 h.Write(data)
368 h.Sum(in)
369 in = in[:0]
370 }
371 }
372
View as plain text