Source file src/hash/crc32/crc32_test.go

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

View as plain text