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