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 implements the 32-bit cyclic redundancy check, or CRC-32, 6 // checksum. See http://en.wikipedia.org/wiki/Cyclic_redundancy_check for 7 // information. 8 // 9 // Polynomials are represented in LSB-first form also known as reversed representation. 10 // 11 // See http://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Reversed_representations_and_reciprocal_polynomials 12 // for information. 13 package crc32 14 15 import ( 16 "hash" 17 "sync" 18 ) 19 20 // The size of a CRC-32 checksum in bytes. 21 const Size = 4 22 23 // Predefined polynomials. 24 const ( 25 // IEEE is by far and away the most common CRC-32 polynomial. 26 // Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, ... 27 IEEE = 0xedb88320 28 29 // Castagnoli's polynomial, used in iSCSI. 30 // Has better error detection characteristics than IEEE. 31 // http://dx.doi.org/10.1109/26.231911 32 Castagnoli = 0x82f63b78 33 34 // Koopman's polynomial. 35 // Also has better error detection characteristics than IEEE. 36 // http://dx.doi.org/10.1109/DSN.2002.1028931 37 Koopman = 0xeb31d82e 38 ) 39 40 // Table is a 256-word table representing the polynomial for efficient processing. 41 type Table [256]uint32 42 43 // castagnoliTable points to a lazily initialized Table for the Castagnoli 44 // polynomial. MakeTable will always return this value when asked to make a 45 // Castagnoli table so we can compare against it to find when the caller is 46 // using this polynomial. 47 var castagnoliTable *Table 48 var castagnoliOnce sync.Once 49 50 func castagnoliInit() { 51 castagnoliTable = makeTable(Castagnoli) 52 } 53 54 // IEEETable is the table for the IEEE polynomial. 55 var IEEETable = makeTable(IEEE) 56 57 // slicing8Table is array of 8 Tables 58 type slicing8Table [8]Table 59 60 // iEEETable8 is the slicing8Table for IEEE 61 var iEEETable8 *slicing8Table 62 var iEEETable8Once sync.Once 63 64 // MakeTable returns the Table constructed from the specified polynomial. 65 func MakeTable(poly uint32) *Table { 66 switch poly { 67 case IEEE: 68 return IEEETable 69 case Castagnoli: 70 castagnoliOnce.Do(castagnoliInit) 71 return castagnoliTable 72 } 73 return makeTable(poly) 74 } 75 76 // makeTable returns the Table constructed from the specified polynomial. 77 func makeTable(poly uint32) *Table { 78 t := new(Table) 79 for i := 0; i < 256; i++ { 80 crc := uint32(i) 81 for j := 0; j < 8; j++ { 82 if crc&1 == 1 { 83 crc = (crc >> 1) ^ poly 84 } else { 85 crc >>= 1 86 } 87 } 88 t[i] = crc 89 } 90 return t 91 } 92 93 // makeTable8 returns slicing8Table constructed from the specified polynomial. 94 func makeTable8(poly uint32) *slicing8Table { 95 t := new(slicing8Table) 96 t[0] = *makeTable(poly) 97 for i := 0; i < 256; i++ { 98 crc := t[0][i] 99 for j := 1; j < 8; j++ { 100 crc = t[0][crc&0xFF] ^ (crc >> 8) 101 t[j][i] = crc 102 } 103 } 104 return t 105 } 106 107 // digest represents the partial evaluation of a checksum. 108 type digest struct { 109 crc uint32 110 tab *Table 111 } 112 113 // New creates a new hash.Hash32 computing the CRC-32 checksum 114 // using the polynomial represented by the Table. 115 func New(tab *Table) hash.Hash32 { return &digest{0, tab} } 116 117 // NewIEEE creates a new hash.Hash32 computing the CRC-32 checksum 118 // using the IEEE polynomial. 119 func NewIEEE() hash.Hash32 { return New(IEEETable) } 120 121 func (d *digest) Size() int { return Size } 122 123 func (d *digest) BlockSize() int { return 1 } 124 125 func (d *digest) Reset() { d.crc = 0 } 126 127 func update(crc uint32, tab *Table, p []byte) uint32 { 128 crc = ^crc 129 for _, v := range p { 130 crc = tab[byte(crc)^v] ^ (crc >> 8) 131 } 132 return ^crc 133 } 134 135 // updateSlicingBy8 updates CRC using Slicing-by-8 136 func updateSlicingBy8(crc uint32, tab *slicing8Table, p []byte) uint32 { 137 crc = ^crc 138 for len(p) > 8 { 139 crc ^= uint32(p[0]) | uint32(p[1])<<8 | uint32(p[2])<<16 | uint32(p[3])<<24 140 crc = tab[0][p[7]] ^ tab[1][p[6]] ^ tab[2][p[5]] ^ tab[3][p[4]] ^ 141 tab[4][crc>>24] ^ tab[5][(crc>>16)&0xFF] ^ 142 tab[6][(crc>>8)&0xFF] ^ tab[7][crc&0xFF] 143 p = p[8:] 144 } 145 crc = ^crc 146 return update(crc, &tab[0], p) 147 } 148 149 // Update returns the result of adding the bytes in p to the crc. 150 func Update(crc uint32, tab *Table, p []byte) uint32 { 151 if tab == castagnoliTable { 152 return updateCastagnoli(crc, p) 153 } 154 // only use slicing-by-8 when input is larger than 4KB 155 if tab == IEEETable && len(p) >= 4096 { 156 iEEETable8Once.Do(func() { 157 iEEETable8 = makeTable8(IEEE) 158 }) 159 return updateSlicingBy8(crc, iEEETable8, p) 160 } 161 return update(crc, tab, p) 162 } 163 164 func (d *digest) Write(p []byte) (n int, err error) { 165 d.crc = Update(d.crc, d.tab, p) 166 return len(p), nil 167 } 168 169 func (d *digest) Sum32() uint32 { return d.crc } 170 171 func (d *digest) Sum(in []byte) []byte { 172 s := d.Sum32() 173 return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s)) 174 } 175 176 // Checksum returns the CRC-32 checksum of data 177 // using the polynomial represented by the Table. 178 func Checksum(data []byte, tab *Table) uint32 { return Update(0, tab, data) } 179 180 // ChecksumIEEE returns the CRC-32 checksum of data 181 // using the IEEE polynomial. 182 func ChecksumIEEE(data []byte) uint32 { return Update(0, IEEETable, data) } 183
