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 "strings"
15 "testing"
16 )
17
18
19 func TestCastagnoliRace(t *testing.T) {
20
21
22
23 ieee := NewIEEE()
24 go MakeTable(Castagnoli)
25 ieee.Write([]byte("hello"))
26 }
27
28 func TestHashInterface(t *testing.T) {
29 testhash.TestHash(t, func() hash.Hash { return NewIEEE() })
30 }
31
32 type test struct {
33 ieee, castagnoli uint32
34 in string
35 halfStateIEEE string
36 halfStateCastagnoli string
37 }
38
39 var golden = []test{
40 {0x0, 0x0, "", "crc\x01ʇ\x91M\x00\x00\x00\x00", "crc\x01wB\x84\x81\x00\x00\x00\x00"},
41 {0xe8b7be43, 0xc1d04330, "a", "crc\x01ʇ\x91M\x00\x00\x00\x00", "crc\x01wB\x84\x81\x00\x00\x00\x00"},
42 {0x9e83486d, 0xe2a22936, "ab", "crc\x01ʇ\x91M跾C", "crc\x01wB\x84\x81\xc1\xd0C0"},
43 {0x352441c2, 0x364b3fb7, "abc", "crc\x01ʇ\x91M跾C", "crc\x01wB\x84\x81\xc1\xd0C0"},
44 {0xed82cd11, 0x92c80a31, "abcd", "crc\x01ʇ\x91M\x9e\x83Hm", "crc\x01wB\x84\x81\xe2\xa2)6"},
45 {0x8587d865, 0xc450d697, "abcde", "crc\x01ʇ\x91M\x9e\x83Hm", "crc\x01wB\x84\x81\xe2\xa2)6"},
46 {0x4b8e39ef, 0x53bceff1, "abcdef", "crc\x01ʇ\x91M5$A\xc2", "crc\x01wB\x84\x816K?\xb7"},
47 {0x312a6aa6, 0xe627f441, "abcdefg", "crc\x01ʇ\x91M5$A\xc2", "crc\x01wB\x84\x816K?\xb7"},
48 {0xaeef2a50, 0xa9421b7, "abcdefgh", "crc\x01ʇ\x91M\xed\x82\xcd\x11", "crc\x01wB\x84\x81\x92\xc8\n1"},
49 {0x8da988af, 0x2ddc99fc, "abcdefghi", "crc\x01ʇ\x91M\xed\x82\xcd\x11", "crc\x01wB\x84\x81\x92\xc8\n1"},
50 {0x3981703a, 0xe6599437, "abcdefghij", "crc\x01ʇ\x91M\x85\x87\xd8e", "crc\x01wB\x84\x81\xc4P֗"},
51 {0x6b9cdfe7, 0xb2cc01fe, "Discard medicine more than two years old.", "crc\x01ʇ\x91M\xfd\xe5\xc2J", "crc\x01wB\x84\x81S\"(\xe0"},
52 {0xc90ef73f, 0xe28207f, "He who has a shady past knows that nice guys finish last.", "crc\x01ʇ\x91M\x01Nj+", "crc\x01wB\x84\x81'\xdaR\x15"},
53 {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"},
54 {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"},
55 {0x154c6d11, 0xf505ef04, "The days of the digital watch are numbered. -Tom Stoppard", "crc\x01ʇ\x91MOa\xa5\r", "crc\x01wB\x84\x81\xd3s\x9dP"},
56 {0x4c418325, 0x85d3dc82, "Nepal premier won't resign.", "crc\x01ʇ\x91M\xa8S9\x85", "crc\x01wB\x84\x81{\x90\x8a\x14"},
57 {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"},
58 {0x26216a4b, 0x75eb77dd, "His money is twice tainted: 'taint yours and 'taint mine.", "crc\x01ʇ\x91M\\\x1an\x88", "crc\x01wB\x84\x81W\a8Z"},
59 {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"},
60 {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"},
61 {0xab3abe14, 0x572b74e2, "size: a.out: bad magic", "crc\x01ʇ\x91M\x8a\x0f\xad\b", "crc\x01wB\x84\x81\x80\xc9n\xd8"},
62 {0xbab102b6, 0x8a58a6d5, "The major problem is with sendmail. -Mark Horton", "crc\x01ʇ\x91M\a\xf0\xb3\x15", "crc\x01wB\x84\x81liS\xcc"},
63 {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"},
64 {0x6d52a33c, 0x735400a4, "If the enemy is within range, then so are you.", "crc\x01ʇ\x91My\x1b\x99\xf8", "crc\x01wB\x84\x81\xaaB\x037"},
65 {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"},
66 {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"},
67 {0x7d0a377f, 0xde2e65c5, "C is as portable as Stonehedge!!", "crc\x01ʇ\x91M\xf7\xd6\x00\xd5", "crc\x01wB\x84\x81de\\\xf8"},
68 {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"},
69 {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"},
70 {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"},
71 {0x1010dab0, 0x8a11661f, strings.Repeat("01234567", 1024), "crc\x01ʇ\x91M\x92\xe5\xba\xf3", "crc\x01wB\x84\x81\x1a\x02\x88Y"},
72 {0x772d04d7, 0x5a6f5c45, strings.Repeat("a", 1024+65), "crc\x01ʇ\x91M\xe7Љ\xd1", "crc\x01wB\x84\x81\x95B\xa9("},
73 }
74
75
76
77 func testGoldenIEEE(t *testing.T, crcFunc func(b []byte) uint32) {
78 for _, g := range golden {
79 if crc := crcFunc([]byte(g.in)); crc != g.ieee {
80 t.Errorf("IEEE(%s) = 0x%x want 0x%x", g.in, crc, g.ieee)
81 }
82 }
83 }
84
85
86
87 func testGoldenCastagnoli(t *testing.T, crcFunc func(b []byte) uint32) {
88 for _, g := range golden {
89 if crc := crcFunc([]byte(g.in)); crc != g.castagnoli {
90 t.Errorf("Castagnoli(%s) = 0x%x want 0x%x", g.in, crc, g.castagnoli)
91 }
92 }
93 }
94
95
96
97 func testCrossCheck(t *testing.T, crcFunc1, crcFunc2 func(crc uint32, b []byte) uint32) {
98
99
100
101 lengths := []int{0, 1, 2, 3, 4, 5, 10, 16, 50, 63, 64, 65, 100,
102 127, 128, 129, 255, 256, 257, 300, 312, 384, 416, 448, 480,
103 500, 501, 502, 503, 504, 505, 512, 513, 1000, 1024, 2000,
104 4030, 4031, 4032, 4033, 4036, 4040, 4048, 4096, 5000, 10000}
105 for _, length := range lengths {
106 p := make([]byte, length)
107 _, _ = rand.Read(p)
108 crcInit := uint32(rand.Int63())
109 crc1 := crcFunc1(crcInit, p)
110 crc2 := crcFunc2(crcInit, p)
111 if crc1 != crc2 {
112 t.Errorf("mismatch: 0x%x vs 0x%x (buffer length %d)", crc1, crc2, length)
113 }
114 }
115 }
116
117
118 func TestSimple(t *testing.T) {
119 tab := simpleMakeTable(IEEE)
120 testGoldenIEEE(t, func(b []byte) uint32 {
121 return simpleUpdate(0, tab, b)
122 })
123
124 tab = simpleMakeTable(Castagnoli)
125 testGoldenCastagnoli(t, func(b []byte) uint32 {
126 return simpleUpdate(0, tab, b)
127 })
128 }
129
130 func TestGoldenMarshal(t *testing.T) {
131 t.Run("IEEE", func(t *testing.T) {
132 for _, g := range golden {
133 h := New(IEEETable)
134 h2 := New(IEEETable)
135
136 io.WriteString(h, g.in[:len(g.in)/2])
137
138 state, err := h.(encoding.BinaryMarshaler).MarshalBinary()
139 if err != nil {
140 t.Errorf("could not marshal: %v", err)
141 continue
142 }
143
144 stateAppend, err := h.(encoding.BinaryAppender).AppendBinary(make([]byte, 4, 32))
145 if err != nil {
146 t.Errorf("could not marshal: %v", err)
147 continue
148 }
149 stateAppend = stateAppend[4:]
150
151 if string(state) != g.halfStateIEEE {
152 t.Errorf("IEEE(%q) state = %q, want %q", g.in, state, g.halfStateIEEE)
153 continue
154 }
155
156 if string(stateAppend) != g.halfStateIEEE {
157 t.Errorf("IEEE(%q) state = %q, want %q", g.in, stateAppend, g.halfStateIEEE)
158 continue
159 }
160
161 if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state); err != nil {
162 t.Errorf("could not unmarshal: %v", err)
163 continue
164 }
165
166 io.WriteString(h, g.in[len(g.in)/2:])
167 io.WriteString(h2, g.in[len(g.in)/2:])
168
169 if h.Sum32() != h2.Sum32() {
170 t.Errorf("IEEE(%s) = 0x%x != marshaled 0x%x", g.in, h.Sum32(), h2.Sum32())
171 }
172 }
173 })
174 t.Run("Castagnoli", func(t *testing.T) {
175 table := MakeTable(Castagnoli)
176 for _, g := range golden {
177 h := New(table)
178 h2 := New(table)
179
180 io.WriteString(h, g.in[:len(g.in)/2])
181
182 state, err := h.(encoding.BinaryMarshaler).MarshalBinary()
183 if err != nil {
184 t.Errorf("could not marshal: %v", err)
185 continue
186 }
187
188 stateAppend, err := h.(encoding.BinaryAppender).AppendBinary(make([]byte, 4, 32))
189 if err != nil {
190 t.Errorf("could not marshal: %v", err)
191 continue
192 }
193 stateAppend = stateAppend[4:]
194
195 if string(state) != g.halfStateCastagnoli {
196 t.Errorf("Castagnoli(%q) state = %q, want %q", g.in, state, g.halfStateCastagnoli)
197 continue
198 }
199
200 if string(stateAppend) != g.halfStateCastagnoli {
201 t.Errorf("Castagnoli(%q) state = %q, want %q", g.in, stateAppend, g.halfStateCastagnoli)
202 continue
203 }
204
205 if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state); err != nil {
206 t.Errorf("could not unmarshal: %v", err)
207 continue
208 }
209
210 io.WriteString(h, g.in[len(g.in)/2:])
211 io.WriteString(h2, g.in[len(g.in)/2:])
212
213 if h.Sum32() != h2.Sum32() {
214 t.Errorf("Castagnoli(%s) = 0x%x != marshaled 0x%x", g.in, h.Sum32(), h2.Sum32())
215 }
216 }
217 })
218 }
219
220 func TestMarshalTableMismatch(t *testing.T) {
221 h1 := New(IEEETable)
222 h2 := New(MakeTable(Castagnoli))
223
224 state1, err := h1.(encoding.BinaryMarshaler).MarshalBinary()
225 if err != nil {
226 t.Errorf("could not marshal: %v", err)
227 }
228
229 if err := h2.(encoding.BinaryUnmarshaler).UnmarshalBinary(state1); err == nil {
230 t.Errorf("no error when one was expected")
231 }
232 }
233
234
235 func TestSlicing(t *testing.T) {
236 tab := slicingMakeTable(IEEE)
237 testGoldenIEEE(t, func(b []byte) uint32 {
238 return slicingUpdate(0, tab, b)
239 })
240
241 tab = slicingMakeTable(Castagnoli)
242 testGoldenCastagnoli(t, func(b []byte) uint32 {
243 return slicingUpdate(0, tab, b)
244 })
245
246
247 for _, poly := range []uint32{IEEE, Castagnoli, Koopman, 0xD5828281} {
248 t1 := simpleMakeTable(poly)
249 f1 := func(crc uint32, b []byte) uint32 {
250 return simpleUpdate(crc, t1, b)
251 }
252 t2 := slicingMakeTable(poly)
253 f2 := func(crc uint32, b []byte) uint32 {
254 return slicingUpdate(crc, t2, b)
255 }
256 testCrossCheck(t, f1, f2)
257 }
258 }
259
260 func TestArchIEEE(t *testing.T) {
261 if !archAvailableIEEE() {
262 t.Skip("Arch-specific IEEE not available.")
263 }
264 archInitIEEE()
265 slicingTable := slicingMakeTable(IEEE)
266 testCrossCheck(t, archUpdateIEEE, func(crc uint32, b []byte) uint32 {
267 return slicingUpdate(crc, slicingTable, b)
268 })
269 }
270
271 func TestArchCastagnoli(t *testing.T) {
272 if !archAvailableCastagnoli() {
273 t.Skip("Arch-specific Castagnoli not available.")
274 }
275 archInitCastagnoli()
276 slicingTable := slicingMakeTable(Castagnoli)
277 testCrossCheck(t, archUpdateCastagnoli, func(crc uint32, b []byte) uint32 {
278 return slicingUpdate(crc, slicingTable, b)
279 })
280 }
281
282 func TestGolden(t *testing.T) {
283 testGoldenIEEE(t, ChecksumIEEE)
284
285
286
287 for delta := 1; delta <= 7; delta++ {
288 testGoldenIEEE(t, func(b []byte) uint32 {
289 ieee := NewIEEE()
290 d := delta
291 if d >= len(b) {
292 d = len(b)
293 }
294 ieee.Write(b[:d])
295 ieee.Write(b[d:])
296 return ieee.Sum32()
297 })
298 }
299
300 castagnoliTab := MakeTable(Castagnoli)
301 if castagnoliTab == nil {
302 t.Errorf("nil Castagnoli Table")
303 }
304
305 testGoldenCastagnoli(t, func(b []byte) uint32 {
306 castagnoli := New(castagnoliTab)
307 castagnoli.Write(b)
308 return castagnoli.Sum32()
309 })
310
311
312
313 for delta := 1; delta <= 7; delta++ {
314 testGoldenCastagnoli(t, func(b []byte) uint32 {
315 castagnoli := New(castagnoliTab)
316 d := delta
317 if d >= len(b) {
318 d = len(b)
319 }
320 castagnoli.Write(b[:d])
321 castagnoli.Write(b[d:])
322 return castagnoli.Sum32()
323 })
324 }
325 }
326
327 func BenchmarkCRC32(b *testing.B) {
328 b.Run("poly=IEEE", benchmarkAll(NewIEEE()))
329 b.Run("poly=Castagnoli", benchmarkAll(New(MakeTable(Castagnoli))))
330 b.Run("poly=Koopman", benchmarkAll(New(MakeTable(Koopman))))
331 }
332
333 func benchmarkAll(h hash.Hash32) func(b *testing.B) {
334 return func(b *testing.B) {
335 for _, size := range []int{15, 40, 512, 1 << 10, 4 << 10, 32 << 10} {
336 name := fmt.Sprint(size)
337 if size >= 1024 {
338 name = fmt.Sprintf("%dkB", size/1024)
339 }
340 b.Run("size="+name, func(b *testing.B) {
341 for align := 0; align <= 1; align++ {
342 b.Run(fmt.Sprintf("align=%d", align), func(b *testing.B) {
343 benchmark(b, h, int64(size), int64(align))
344 })
345 }
346 })
347 }
348 }
349 }
350
351 func benchmark(b *testing.B, h hash.Hash32, n, alignment int64) {
352 b.SetBytes(n)
353 data := make([]byte, n+alignment)
354 data = data[alignment:]
355 for i := range data {
356 data[i] = byte(i)
357 }
358 in := make([]byte, 0, h.Size())
359
360
361 h.Reset()
362 h.Write(data)
363 h.Sum(in)
364
365 in = in[:0]
366
367 b.ResetTimer()
368 for i := 0; i < b.N; i++ {
369 h.Reset()
370 h.Write(data)
371 h.Sum(in)
372 in = in[:0]
373 }
374 }
375
View as plain text