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
21 // The size of a CRC-32 checksum in bytes.
24 // Predefined polynomials.
26 // IEEE is by far and away the most common CRC-32 polynomial.
27 // Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, ...
30 // Castagnoli's polynomial, used in iSCSI.
31 // Has better error detection characteristics than IEEE.
32 // https://dx.doi.org/10.1109/26.231911
33 Castagnoli
= 0x82f63b78
35 // Koopman's polynomial.
36 // Also has better error detection characteristics than IEEE.
37 // https://dx.doi.org/10.1109/DSN.2002.1028931
41 // Table is a 256-word table representing the polynomial for efficient processing.
42 type Table
[256]uint32
44 // This file makes use of functions implemented in architecture-specific files.
45 // The interface that they implement is as follows:
47 // // archAvailableIEEE reports whether an architecture-specific CRC32-IEEE
48 // // algorithm is available.
49 // archAvailableIEEE() bool
51 // // archInitIEEE initializes the architecture-specific CRC3-IEEE algorithm.
52 // // It can only be called if archAvailableIEEE() returns true.
55 // // archUpdateIEEE updates the given CRC32-IEEE. It can only be called if
56 // // archInitIEEE() was previously called.
57 // archUpdateIEEE(crc uint32, p []byte) uint32
59 // // archAvailableCastagnoli reports whether an architecture-specific
60 // // CRC32-C algorithm is available.
61 // archAvailableCastagnoli() bool
63 // // archInitCastagnoli initializes the architecture-specific CRC32-C
64 // // algorithm. It can only be called if archAvailableCastagnoli() returns
66 // archInitCastagnoli()
68 // // archUpdateCastagnoli updates the given CRC32-C. It can only be called
69 // // if archInitCastagnoli() was previously called.
70 // archUpdateCastagnoli(crc uint32, p []byte) uint32
72 // castagnoliTable points to a lazily initialized Table for the Castagnoli
73 // polynomial. MakeTable will always return this value when asked to make a
74 // Castagnoli table so we can compare against it to find when the caller is
75 // using this polynomial.
76 var castagnoliTable
*Table
77 var castagnoliTable8
*slicing8Table
78 var castagnoliArchImpl
bool
79 var updateCastagnoli
func(crc
uint32, p
[]byte) uint32
80 var castagnoliOnce sync
.Once
82 func castagnoliInit() {
83 castagnoliTable
= simpleMakeTable(Castagnoli
)
84 castagnoliArchImpl
= archAvailableCastagnoli()
86 if castagnoliArchImpl
{
88 updateCastagnoli
= archUpdateCastagnoli
90 // Initialize the slicing-by-8 table.
91 castagnoliTable8
= slicingMakeTable(Castagnoli
)
92 updateCastagnoli
= func(crc
uint32, p
[]byte) uint32 {
93 return slicingUpdate(crc
, castagnoliTable8
, p
)
98 // IEEETable is the table for the IEEE polynomial.
99 var IEEETable
= simpleMakeTable(IEEE
)
101 // ieeeTable8 is the slicing8Table for IEEE
102 var ieeeTable8
*slicing8Table
103 var ieeeArchImpl
bool
104 var updateIEEE
func(crc
uint32, p
[]byte) uint32
105 var ieeeOnce sync
.Once
108 ieeeArchImpl
= archAvailableIEEE()
112 updateIEEE
= archUpdateIEEE
114 // Initialize the slicing-by-8 table.
115 ieeeTable8
= slicingMakeTable(IEEE
)
116 updateIEEE
= func(crc
uint32, p
[]byte) uint32 {
117 return slicingUpdate(crc
, ieeeTable8
, p
)
122 // MakeTable returns a Table constructed from the specified polynomial.
123 // The contents of this Table must not be modified.
124 func MakeTable(poly
uint32) *Table
{
127 ieeeOnce
.Do(ieeeInit
)
130 castagnoliOnce
.Do(castagnoliInit
)
131 return castagnoliTable
133 return simpleMakeTable(poly
)
136 // digest represents the partial evaluation of a checksum.
142 // New creates a new hash.Hash32 computing the CRC-32 checksum using the
143 // polynomial represented by the Table. Its Sum method will lay the
144 // value out in big-endian byte order. The returned Hash32 also
145 // implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to
146 // marshal and unmarshal the internal state of the hash.
147 func New(tab
*Table
) hash
.Hash32
{
148 if tab
== IEEETable
{
149 ieeeOnce
.Do(ieeeInit
)
151 return &digest
{0, tab
}
154 // NewIEEE creates a new hash.Hash32 computing the CRC-32 checksum using
155 // the IEEE polynomial. Its Sum method will lay the value out in
156 // big-endian byte order. The returned Hash32 also implements
157 // encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to marshal
158 // and unmarshal the internal state of the hash.
159 func NewIEEE() hash
.Hash32
{ return New(IEEETable
) }
161 func (d
*digest
) Size() int { return Size
}
163 func (d
*digest
) BlockSize() int { return 1 }
165 func (d
*digest
) Reset() { d
.crc
= 0 }
169 marshaledSize
= len(magic
) + 4 + 4
172 func (d
*digest
) MarshalBinary() ([]byte, error
) {
173 b
:= make([]byte, 0, marshaledSize
)
174 b
= append(b
, magic
...)
175 b
= appendUint32(b
, tableSum(d
.tab
))
176 b
= appendUint32(b
, d
.crc
)
180 func (d
*digest
) UnmarshalBinary(b
[]byte) error
{
181 if len(b
) < len(magic
) ||
string(b
[:len(magic
)]) != magic
{
182 return errors
.New("hash/crc32: invalid hash state identifier")
184 if len(b
) != marshaledSize
{
185 return errors
.New("hash/crc32: invalid hash state size")
187 if tableSum(d
.tab
) != readUint32(b
[4:]) {
188 return errors
.New("hash/crc32: tables do not match")
190 d
.crc
= readUint32(b
[8:])
194 func appendUint32(b
[]byte, x
uint32) []byte {
201 return append(b
, a
[:]...)
204 func readUint32(b
[]byte) uint32 {
206 return uint32(b
[3]) |
uint32(b
[2])<<8 |
uint32(b
[1])<<16 |
uint32(b
[0])<<24
209 // Update returns the result of adding the bytes in p to the crc.
210 func Update(crc
uint32, tab
*Table
, p
[]byte) uint32 {
212 case castagnoliTable
:
213 return updateCastagnoli(crc
, p
)
215 // Unfortunately, because IEEETable is exported, IEEE may be used without a
216 // call to MakeTable. We have to make sure it gets initialized in that case.
217 ieeeOnce
.Do(ieeeInit
)
218 return updateIEEE(crc
, p
)
220 return simpleUpdate(crc
, tab
, p
)
224 func (d
*digest
) Write(p
[]byte) (n
int, err error
) {
226 case castagnoliTable
:
227 d
.crc
= updateCastagnoli(d
.crc
, p
)
229 // We only create digest objects through New() which takes care of
230 // initialization in this case.
231 d
.crc
= updateIEEE(d
.crc
, p
)
233 d
.crc
= simpleUpdate(d
.crc
, d
.tab
, p
)
238 func (d
*digest
) Sum32() uint32 { return d
.crc
}
240 func (d
*digest
) Sum(in
[]byte) []byte {
242 return append(in
, byte(s
>>24), byte(s
>>16), byte(s
>>8), byte(s
))
245 // Checksum returns the CRC-32 checksum of data
246 // using the polynomial represented by the Table.
247 func Checksum(data
[]byte, tab
*Table
) uint32 { return Update(0, tab
, data
) }
249 // ChecksumIEEE returns the CRC-32 checksum of data
250 // using the IEEE polynomial.
251 func ChecksumIEEE(data
[]byte) uint32 {
252 ieeeOnce
.Do(ieeeInit
)
253 return updateIEEE(0, data
)
256 // tableSum returns the IEEE checksum of table t.
257 func tableSum(t
*Table
) uint32 {
261 for _
, x
:= range t
{
262 b
= appendUint32(b
, x
)
265 return ChecksumIEEE(b
)