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 13 package crc32
14 15 import "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).
20 func simpleMakeTable(poly uint32) *Table {
21 t := &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.
28 func 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.
44 func 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.
53 const slicing8Cutoff = 16
54 55 // slicing8Table is array of 8 Tables, used by the slicing-by-8 algorithm.
56 type 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).
60 func slicingMakeTable(poly uint32) *slicing8Table {
61 t := &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.
75 func 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