1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package crc32
6
7import (
8	crand "crypto/rand"
9	"hash"
10	mrand "math/rand"
11	"testing"
12)
13
14type test struct {
15	ieee, castagnoli uint32
16	in               string
17}
18
19var golden = []test{
20	{0x0, 0x0, ""},
21	{0xe8b7be43, 0xc1d04330, "a"},
22	{0x9e83486d, 0xe2a22936, "ab"},
23	{0x352441c2, 0x364b3fb7, "abc"},
24	{0xed82cd11, 0x92c80a31, "abcd"},
25	{0x8587d865, 0xc450d697, "abcde"},
26	{0x4b8e39ef, 0x53bceff1, "abcdef"},
27	{0x312a6aa6, 0xe627f441, "abcdefg"},
28	{0xaeef2a50, 0xa9421b7, "abcdefgh"},
29	{0x8da988af, 0x2ddc99fc, "abcdefghi"},
30	{0x3981703a, 0xe6599437, "abcdefghij"},
31	{0x6b9cdfe7, 0xb2cc01fe, "Discard medicine more than two years old."},
32	{0xc90ef73f, 0xe28207f, "He who has a shady past knows that nice guys finish last."},
33	{0xb902341f, 0xbe93f964, "I wouldn't marry him with a ten foot pole."},
34	{0x42080e8, 0x9e3be0c3, "Free! Free!/A trip/to Mars/for 900/empty jars/Burma Shave"},
35	{0x154c6d11, 0xf505ef04, "The days of the digital watch are numbered.  -Tom Stoppard"},
36	{0x4c418325, 0x85d3dc82, "Nepal premier won't resign."},
37	{0x33955150, 0xc5142380, "For every action there is an equal and opposite government program."},
38	{0x26216a4b, 0x75eb77dd, "His money is twice tainted: 'taint yours and 'taint mine."},
39	{0x1abbe45e, 0x91ebe9f7, "There is no reason for any individual to have a computer in their home. -Ken Olsen, 1977"},
40	{0xc89a94f7, 0xf0b1168e, "It's a tiny change to the code and not completely disgusting. - Bob Manchek"},
41	{0xab3abe14, 0x572b74e2, "size:  a.out:  bad magic"},
42	{0xbab102b6, 0x8a58a6d5, "The major problem is with sendmail.  -Mark Horton"},
43	{0x999149d7, 0x9c426c50, "Give me a rock, paper and scissors and I will move the world.  CCFestoon"},
44	{0x6d52a33c, 0x735400a4, "If the enemy is within range, then so are you."},
45	{0x90631e8d, 0xbec49c95, "It's well we cannot hear the screams/That we create in others' dreams."},
46	{0x78309130, 0xa95a2079, "You remind me of a TV show, but that's all right: I watch it anyway."},
47	{0x7d0a377f, 0xde2e65c5, "C is as portable as Stonehedge!!"},
48	{0x8c79fd79, 0x297a88ed, "Even if I could be Shakespeare, I think I should still choose to be Faraday. - A. Huxley"},
49	{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"},
50	{0x8e0bb443, 0xdcded527, "How can you write a big system without C++?  -Paul Glick"},
51}
52
53// testGoldenIEEE verifies that the given function returns
54// correct IEEE checksums.
55func testGoldenIEEE(t *testing.T, crcFunc func(b []byte) uint32) {
56	for _, g := range golden {
57		if crc := crcFunc([]byte(g.in)); crc != g.ieee {
58			t.Errorf("IEEE(%s) = 0x%x want 0x%x", g.in, crc, g.ieee)
59		}
60	}
61}
62
63// testGoldenCastagnoli verifies that the given function returns
64// correct IEEE checksums.
65func testGoldenCastagnoli(t *testing.T, crcFunc func(b []byte) uint32) {
66	for _, g := range golden {
67		if crc := crcFunc([]byte(g.in)); crc != g.castagnoli {
68			t.Errorf("Castagnoli(%s) = 0x%x want 0x%x", g.in, crc, g.castagnoli)
69		}
70	}
71}
72
73// testCrossCheck generates random buffers of various lengths and verifies that
74// the two "update" functions return the same result.
75func testCrossCheck(t *testing.T, crcFunc1, crcFunc2 func(crc uint32, b []byte) uint32) {
76	// The AMD64 implementation has some cutoffs at lengths 168*3=504 and
77	// 1344*3=4032. We should make sure lengths around these values are in the
78	// list.
79	lengths := []int{0, 1, 2, 3, 4, 5, 10, 16, 50, 100, 128,
80		500, 501, 502, 503, 504, 505, 512, 1000, 1024, 2000,
81		4030, 4031, 4032, 4033, 4036, 4040, 4048, 4096, 5000, 10000}
82	for _, length := range lengths {
83		p := make([]byte, length)
84		_, _ = crand.Read(p)
85		crcInit := uint32(mrand.Int63())
86		crc1 := crcFunc1(crcInit, p)
87		crc2 := crcFunc2(crcInit, p)
88		if crc1 != crc2 {
89			t.Errorf("mismatch: 0x%x vs 0x%x (buffer length %d)", crc1, crc2, length)
90		}
91	}
92}
93
94// TestSimple tests the simple generic algorithm.
95func TestSimple(t *testing.T) {
96	tab := simpleMakeTable(IEEE)
97	testGoldenIEEE(t, func(b []byte) uint32 {
98		return simpleUpdate(0, tab, b)
99	})
100
101	tab = simpleMakeTable(Castagnoli)
102	testGoldenCastagnoli(t, func(b []byte) uint32 {
103		return simpleUpdate(0, tab, b)
104	})
105}
106
107// TestSimple tests the slicing-by-8 algorithm.
108func TestSlicing(t *testing.T) {
109	tab := slicingMakeTable(IEEE)
110	testGoldenIEEE(t, func(b []byte) uint32 {
111		return slicingUpdate(0, tab, b)
112	})
113
114	tab = slicingMakeTable(Castagnoli)
115	testGoldenCastagnoli(t, func(b []byte) uint32 {
116		return slicingUpdate(0, tab, b)
117	})
118
119	// Cross-check various polys against the simple algorithm.
120	for _, poly := range []uint32{IEEE, Castagnoli, Koopman, 0xD5828281} {
121		t1 := simpleMakeTable(poly)
122		f1 := func(crc uint32, b []byte) uint32 {
123			return simpleUpdate(crc, t1, b)
124		}
125		t2 := slicingMakeTable(poly)
126		f2 := func(crc uint32, b []byte) uint32 {
127			return slicingUpdate(crc, t2, b)
128		}
129		testCrossCheck(t, f1, f2)
130	}
131}
132
133func TestArchIEEE(t *testing.T) {
134	if !archAvailableIEEE() {
135		t.Skip("Arch-specific IEEE not available.")
136	}
137	archInitIEEE()
138	slicingTable := slicingMakeTable(IEEE)
139	testCrossCheck(t, archUpdateIEEE, func(crc uint32, b []byte) uint32 {
140		return slicingUpdate(crc, slicingTable, b)
141	})
142}
143
144func TestArchCastagnoli(t *testing.T) {
145	if !archAvailableCastagnoli() {
146		t.Skip("Arch-specific Castagnoli not available.")
147	}
148	archInitCastagnoli()
149	slicingTable := slicingMakeTable(Castagnoli)
150	testCrossCheck(t, archUpdateCastagnoli, func(crc uint32, b []byte) uint32 {
151		return slicingUpdate(crc, slicingTable, b)
152	})
153}
154
155func TestGolden(t *testing.T) {
156	testGoldenIEEE(t, ChecksumIEEE)
157
158	// Some implementations have special code to deal with misaligned
159	// data; test that as well.
160	for delta := 1; delta <= 7; delta++ {
161		testGoldenIEEE(t, func(b []byte) uint32 {
162			ieee := NewIEEE()
163			d := delta
164			if d >= len(b) {
165				d = len(b)
166			}
167			ieee.Write(b[:d])
168			ieee.Write(b[d:])
169			return ieee.Sum32()
170		})
171	}
172
173	castagnoliTab := MakeTable(Castagnoli)
174	if castagnoliTab == nil {
175		t.Errorf("nil Castagnoli Table")
176	}
177
178	testGoldenCastagnoli(t, func(b []byte) uint32 {
179		castagnoli := New(castagnoliTab)
180		castagnoli.Write(b)
181		return castagnoli.Sum32()
182	})
183
184	// Some implementations have special code to deal with misaligned
185	// data; test that as well.
186	for delta := 1; delta <= 7; delta++ {
187		testGoldenCastagnoli(t, func(b []byte) uint32 {
188			castagnoli := New(castagnoliTab)
189			d := delta
190			if d >= len(b) {
191				d = len(b)
192			}
193			castagnoli.Write(b[:d])
194			castagnoli.Write(b[d:])
195			return castagnoli.Sum32()
196		})
197	}
198}
199
200func BenchmarkIEEECrc40B(b *testing.B) {
201	benchmark(b, NewIEEE(), 40, 0)
202}
203
204func BenchmarkIEEECrc1KB(b *testing.B) {
205	benchmark(b, NewIEEE(), 1<<10, 0)
206}
207
208func BenchmarkIEEECrc4KB(b *testing.B) {
209	benchmark(b, NewIEEE(), 4<<10, 0)
210}
211
212func BenchmarkIEEECrc32KB(b *testing.B) {
213	benchmark(b, NewIEEE(), 32<<10, 0)
214}
215
216func BenchmarkCastagnoliCrc15B(b *testing.B) {
217	benchmark(b, New(MakeTable(Castagnoli)), 15, 0)
218}
219
220func BenchmarkCastagnoliCrc15BMisaligned(b *testing.B) {
221	benchmark(b, New(MakeTable(Castagnoli)), 15, 1)
222}
223
224func BenchmarkCastagnoliCrc40B(b *testing.B) {
225	benchmark(b, New(MakeTable(Castagnoli)), 40, 0)
226}
227
228func BenchmarkCastagnoliCrc40BMisaligned(b *testing.B) {
229	benchmark(b, New(MakeTable(Castagnoli)), 40, 1)
230}
231
232func BenchmarkCastagnoliCrc512(b *testing.B) {
233	benchmark(b, New(MakeTable(Castagnoli)), 512, 0)
234}
235
236func BenchmarkCastagnoliCrc512Misaligned(b *testing.B) {
237	benchmark(b, New(MakeTable(Castagnoli)), 512, 1)
238}
239
240func BenchmarkCastagnoliCrc1KB(b *testing.B) {
241	benchmark(b, New(MakeTable(Castagnoli)), 1<<10, 0)
242}
243
244func BenchmarkCastagnoliCrc1KBMisaligned(b *testing.B) {
245	benchmark(b, New(MakeTable(Castagnoli)), 1<<10, 1)
246}
247
248func BenchmarkCastagnoliCrc4KB(b *testing.B) {
249	benchmark(b, New(MakeTable(Castagnoli)), 4<<10, 0)
250}
251
252func BenchmarkCastagnoliCrc4KBMisaligned(b *testing.B) {
253	benchmark(b, New(MakeTable(Castagnoli)), 4<<10, 1)
254}
255
256func BenchmarkCastagnoliCrc32KB(b *testing.B) {
257	benchmark(b, New(MakeTable(Castagnoli)), 32<<10, 0)
258}
259
260func BenchmarkCastagnoliCrc32KBMisaligned(b *testing.B) {
261	benchmark(b, New(MakeTable(Castagnoli)), 32<<10, 1)
262}
263
264func benchmark(b *testing.B, h hash.Hash32, n, alignment int64) {
265	b.SetBytes(n)
266	data := make([]byte, n+alignment)
267	data = data[alignment:]
268	for i := range data {
269		data[i] = byte(i)
270	}
271	in := make([]byte, 0, h.Size())
272
273	// Warm up
274	h.Reset()
275	h.Write(data)
276	h.Sum(in)
277
278	b.ResetTimer()
279	for i := 0; i < b.N; i++ {
280		h.Reset()
281		h.Write(data)
282		h.Sum(in)
283	}
284}
285