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.
5 // Package crc32 implements the 32-bit cyclic redundancy check, or CRC-32,
6 // checksum. See https://en.wikipedia.org/wiki/Cyclic_redundancy_check for
9 // Polynomials are represented in LSB-first form also known as reversed representation.
11 // See https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Reversed_representations_and_reciprocal_polynomials
22 // The size of a CRC-32 checksum in bytes.
25 // Predefined polynomials.
27 // IEEE is by far and away the most common CRC-32 polynomial.
28 // Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, ...
31 // Castagnoli's polynomial, used in iSCSI.
32 // Has better error detection characteristics than IEEE.
33 // https://dx.doi.org/10.1109/26.231911
34 Castagnoli
= 0x82f63b78
36 // Koopman's polynomial.
37 // Also has better error detection characteristics than IEEE.
38 // https://dx.doi.org/10.1109/DSN.2002.1028931
42 // Table is a 256-word table representing the polynomial for efficient processing.
43 type Table
[256]uint32
45 // This file makes use of functions implemented in architecture-specific files.
46 // The interface that they implement is as follows:
48 // // archAvailableIEEE reports whether an architecture-specific CRC32-IEEE
49 // // algorithm is available.
50 // archAvailableIEEE() bool
52 // // archInitIEEE initializes the architecture-specific CRC3-IEEE algorithm.
53 // // It can only be called if archAvailableIEEE() returns true.
56 // // archUpdateIEEE updates the given CRC32-IEEE. It can only be called if
57 // // archInitIEEE() was previously called.
58 // archUpdateIEEE(crc uint32, p []byte) uint32
60 // // archAvailableCastagnoli reports whether an architecture-specific
61 // // CRC32-C algorithm is available.
62 // archAvailableCastagnoli() bool
64 // // archInitCastagnoli initializes the architecture-specific CRC32-C
65 // // algorithm. It can only be called if archAvailableCastagnoli() returns
67 // archInitCastagnoli()
69 // // archUpdateCastagnoli updates the given CRC32-C. It can only be called
70 // // if archInitCastagnoli() was previously called.
71 // archUpdateCastagnoli(crc uint32, p []byte) uint32
73 // castagnoliTable points to a lazily initialized Table for the Castagnoli
74 // polynomial. MakeTable will always return this value when asked to make a
75 // Castagnoli table so we can compare against it to find when the caller is
76 // using this polynomial.
77 var castagnoliTable
*Table
78 var castagnoliTable8
*slicing8Table
79 var castagnoliArchImpl
bool
80 var updateCastagnoli
func(crc
uint32, p
[]byte) uint32
81 var castagnoliOnce sync
.Once
82 var haveCastagnoli
uint32
84 func castagnoliInit() {
85 castagnoliTable
= simpleMakeTable(Castagnoli
)
86 castagnoliArchImpl
= archAvailableCastagnoli()
88 if castagnoliArchImpl
{
90 updateCastagnoli
= archUpdateCastagnoli
92 // Initialize the slicing-by-8 table.
93 castagnoliTable8
= slicingMakeTable(Castagnoli
)
94 updateCastagnoli
= func(crc
uint32, p
[]byte) uint32 {
95 return slicingUpdate(crc
, castagnoliTable8
, p
)
99 atomic
.StoreUint32(&haveCastagnoli
, 1)
102 // IEEETable is the table for the IEEE polynomial.
103 var IEEETable
= simpleMakeTable(IEEE
)
105 // ieeeTable8 is the slicing8Table for IEEE
106 var ieeeTable8
*slicing8Table
107 var ieeeArchImpl
bool
108 var updateIEEE
func(crc
uint32, p
[]byte) uint32
109 var ieeeOnce sync
.Once
112 ieeeArchImpl
= archAvailableIEEE()
116 updateIEEE
= archUpdateIEEE
118 // Initialize the slicing-by-8 table.
119 ieeeTable8
= slicingMakeTable(IEEE
)
120 updateIEEE
= func(crc
uint32, p
[]byte) uint32 {
121 return slicingUpdate(crc
, ieeeTable8
, p
)
126 // MakeTable returns a Table constructed from the specified polynomial.
127 // The contents of this Table must not be modified.
128 func MakeTable(poly
uint32) *Table
{
131 ieeeOnce
.Do(ieeeInit
)
134 castagnoliOnce
.Do(castagnoliInit
)
135 return castagnoliTable
137 return simpleMakeTable(poly
)
140 // digest represents the partial evaluation of a checksum.
146 // New creates a new hash.Hash32 computing the CRC-32 checksum using the
147 // polynomial represented by the Table. Its Sum method will lay the
148 // value out in big-endian byte order. The returned Hash32 also
149 // implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to
150 // marshal and unmarshal the internal state of the hash.
151 func New(tab
*Table
) hash
.Hash32
{
152 if tab
== IEEETable
{
153 ieeeOnce
.Do(ieeeInit
)
155 return &digest
{0, tab
}
158 // NewIEEE creates a new hash.Hash32 computing the CRC-32 checksum using
159 // the IEEE polynomial. Its Sum method will lay the value out in
160 // big-endian byte order. The returned Hash32 also implements
161 // encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to marshal
162 // and unmarshal the internal state of the hash.
163 func NewIEEE() hash
.Hash32
{ return New(IEEETable
) }
165 func (d
*digest
) Size() int { return Size
}
167 func (d
*digest
) BlockSize() int { return 1 }
169 func (d
*digest
) Reset() { d
.crc
= 0 }
173 marshaledSize
= len(magic
) + 4 + 4
176 func (d
*digest
) MarshalBinary() ([]byte, error
) {
177 b
:= make([]byte, 0, marshaledSize
)
178 b
= append(b
, magic
...)
179 b
= appendUint32(b
, tableSum(d
.tab
))
180 b
= appendUint32(b
, d
.crc
)
184 func (d
*digest
) UnmarshalBinary(b
[]byte) error
{
185 if len(b
) < len(magic
) ||
string(b
[:len(magic
)]) != magic
{
186 return errors
.New("hash/crc32: invalid hash state identifier")
188 if len(b
) != marshaledSize
{
189 return errors
.New("hash/crc32: invalid hash state size")
191 if tableSum(d
.tab
) != readUint32(b
[4:]) {
192 return errors
.New("hash/crc32: tables do not match")
194 d
.crc
= readUint32(b
[8:])
198 func appendUint32(b
[]byte, x
uint32) []byte {
205 return append(b
, a
[:]...)
208 func readUint32(b
[]byte) uint32 {
210 return uint32(b
[3]) |
uint32(b
[2])<<8 |
uint32(b
[1])<<16 |
uint32(b
[0])<<24
213 // Update returns the result of adding the bytes in p to the crc.
214 func Update(crc
uint32, tab
*Table
, p
[]byte) uint32 {
216 case atomic
.LoadUint32(&haveCastagnoli
) != 0 && tab
== castagnoliTable
:
217 return updateCastagnoli(crc
, p
)
218 case tab
== IEEETable
:
219 // Unfortunately, because IEEETable is exported, IEEE may be used without a
220 // call to MakeTable. We have to make sure it gets initialized in that case.
221 ieeeOnce
.Do(ieeeInit
)
222 return updateIEEE(crc
, p
)
224 return simpleUpdate(crc
, tab
, p
)
228 func (d
*digest
) Write(p
[]byte) (n
int, err error
) {
230 case atomic
.LoadUint32(&haveCastagnoli
) != 0 && d
.tab
== castagnoliTable
:
231 d
.crc
= updateCastagnoli(d
.crc
, p
)
232 case d
.tab
== IEEETable
:
233 // We only create digest objects through New() which takes care of
234 // initialization in this case.
235 d
.crc
= updateIEEE(d
.crc
, p
)
237 d
.crc
= simpleUpdate(d
.crc
, d
.tab
, p
)
242 func (d
*digest
) Sum32() uint32 { return d
.crc
}
244 func (d
*digest
) Sum(in
[]byte) []byte {
246 return append(in
, byte(s
>>24), byte(s
>>16), byte(s
>>8), byte(s
))
249 // Checksum returns the CRC-32 checksum of data
250 // using the polynomial represented by the Table.
251 func Checksum(data
[]byte, tab
*Table
) uint32 { return Update(0, tab
, data
) }
253 // ChecksumIEEE returns the CRC-32 checksum of data
254 // using the IEEE polynomial.
255 func ChecksumIEEE(data
[]byte) uint32 {
256 ieeeOnce
.Do(ieeeInit
)
257 return updateIEEE(0, data
)
260 // tableSum returns the IEEE checksum of table t.
261 func tableSum(t
*Table
) uint32 {
265 for _
, x
:= range t
{
266 b
= appendUint32(b
, x
)
269 return ChecksumIEEE(b
)