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