1// Copyright 2011 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// This file contains CRC32 algorithms that are not specific to any architecture
6// and don't use hardware acceleration.
7//
8// The simple (and slow) CRC32 implementation only uses a 256*4 bytes table.
9//
10// The slicing-by-8 algorithm is a faster implementation that uses a bigger
11// table (8*256*4 bytes).
12
13package crc32
14
15import "internal/byteorder"
16
17// simpleMakeTable allocates and constructs a Table for the specified
18// polynomial. The table is suitable for use with the simple algorithm
19// (simpleUpdate).
20func simpleMakeTable(poly uint32) *Table {
21	t := new(Table)
22	simplePopulateTable(poly, t)
23	return t
24}
25
26// simplePopulateTable constructs a Table for the specified polynomial, suitable
27// for use with simpleUpdate.
28func simplePopulateTable(poly uint32, t *Table) {
29	for i := 0; i < 256; i++ {
30		crc := uint32(i)
31		for j := 0; j < 8; j++ {
32			if crc&1 == 1 {
33				crc = (crc >> 1) ^ poly
34			} else {
35				crc >>= 1
36			}
37		}
38		t[i] = crc
39	}
40}
41
42// simpleUpdate uses the simple algorithm to update the CRC, given a table that
43// was previously computed using simpleMakeTable.
44func simpleUpdate(crc uint32, tab *Table, p []byte) uint32 {
45	crc = ^crc
46	for _, v := range p {
47		crc = tab[byte(crc)^v] ^ (crc >> 8)
48	}
49	return ^crc
50}
51
52// Use slicing-by-8 when payload >= this value.
53const slicing8Cutoff = 16
54
55// slicing8Table is array of 8 Tables, used by the slicing-by-8 algorithm.
56type slicing8Table [8]Table
57
58// slicingMakeTable constructs a slicing8Table for the specified polynomial. The
59// table is suitable for use with the slicing-by-8 algorithm (slicingUpdate).
60func slicingMakeTable(poly uint32) *slicing8Table {
61	t := new(slicing8Table)
62	simplePopulateTable(poly, &t[0])
63	for i := 0; i < 256; i++ {
64		crc := t[0][i]
65		for j := 1; j < 8; j++ {
66			crc = t[0][crc&0xFF] ^ (crc >> 8)
67			t[j][i] = crc
68		}
69	}
70	return t
71}
72
73// slicingUpdate uses the slicing-by-8 algorithm to update the CRC, given a
74// table that was previously computed using slicingMakeTable.
75func slicingUpdate(crc uint32, tab *slicing8Table, p []byte) uint32 {
76	if len(p) >= slicing8Cutoff {
77		crc = ^crc
78		for len(p) > 8 {
79			crc ^= byteorder.LeUint32(p)
80			crc = tab[0][p[7]] ^ tab[1][p[6]] ^ tab[2][p[5]] ^ tab[3][p[4]] ^
81				tab[4][crc>>24] ^ tab[5][(crc>>16)&0xFF] ^
82				tab[6][(crc>>8)&0xFF] ^ tab[7][crc&0xFF]
83			p = p[8:]
84		}
85		crc = ^crc
86	}
87	if len(p) == 0 {
88		return crc
89	}
90	return simpleUpdate(crc, &tab[0], p)
91}
92