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 https://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 https://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Reversed_representations_and_reciprocal_polynomials
12 // for information.
13 package crc32
14 15 import (
16 "errors"
17 "hash"
18 "internal/byteorder"
19 "sync"
20 "sync/atomic"
21 )
22 23 // The size of a CRC-32 checksum in bytes.
24 const Size = 4
25 26 // Predefined polynomials.
27 const (
28 // IEEE is by far and away the most common CRC-32 polynomial.
29 // Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, ...
30 IEEE = 0xedb88320
31 32 // Castagnoli's polynomial, used in iSCSI.
33 // Has better error detection characteristics than IEEE.
34 // https://dx.doi.org/10.1109/26.231911
35 Castagnoli = 0x82f63b78
36 37 // Koopman's polynomial.
38 // Also has better error detection characteristics than IEEE.
39 // https://dx.doi.org/10.1109/DSN.2002.1028931
40 Koopman = 0xeb31d82e
41 )
42 43 // Table is a 256-word table representing the polynomial for efficient processing.
44 type Table [256]uint32
45 46 // This file makes use of functions implemented in architecture-specific files.
47 // The interface that they implement is as follows:
48 //
49 // // archAvailableIEEE reports whether an architecture-specific CRC32-IEEE
50 // // algorithm is available.
51 // archAvailableIEEE() bool
52 //
53 // // archInitIEEE initializes the architecture-specific CRC3-IEEE algorithm.
54 // // It can only be called if archAvailableIEEE() returns true.
55 // archInitIEEE()
56 //
57 // // archUpdateIEEE updates the given CRC32-IEEE. It can only be called if
58 // // archInitIEEE() was previously called.
59 // archUpdateIEEE(crc uint32, p []byte) uint32
60 //
61 // // archAvailableCastagnoli reports whether an architecture-specific
62 // // CRC32-C algorithm is available.
63 // archAvailableCastagnoli() bool
64 //
65 // // archInitCastagnoli initializes the architecture-specific CRC32-C
66 // // algorithm. It can only be called if archAvailableCastagnoli() returns
67 // // true.
68 // archInitCastagnoli()
69 //
70 // // archUpdateCastagnoli updates the given CRC32-C. It can only be called
71 // // if archInitCastagnoli() was previously called.
72 // archUpdateCastagnoli(crc uint32, p []byte) uint32
73 74 // castagnoliTable points to a lazily initialized Table for the Castagnoli
75 // polynomial. MakeTable will always return this value when asked to make a
76 // Castagnoli table so we can compare against it to find when the caller is
77 // using this polynomial.
78 var castagnoliTable *Table
79 var castagnoliTable8 *slicing8Table
80 var updateCastagnoli func(crc uint32, p []byte) uint32
81 var haveCastagnoli atomic.Bool
82 83 var castagnoliInitOnce = sync.OnceFunc(func() {
84 castagnoliTable = simpleMakeTable(Castagnoli)
85 86 if archAvailableCastagnoli() {
87 archInitCastagnoli()
88 updateCastagnoli = archUpdateCastagnoli
89 } else {
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)
94 }
95 }
96 97 haveCastagnoli.Store(true)
98 })
99 100 // IEEETable is the table for the [IEEE] polynomial.
101 var IEEETable = simpleMakeTable(IEEE)
102 103 // ieeeTable8 is the slicing8Table for IEEE
104 var ieeeTable8 *slicing8Table
105 var updateIEEE func(crc uint32, p []byte) uint32
106 107 var ieeeInitOnce = sync.OnceFunc(func() {
108 if archAvailableIEEE() {
109 archInitIEEE()
110 updateIEEE = archUpdateIEEE
111 } else {
112 // Initialize the slicing-by-8 table.
113 ieeeTable8 = slicingMakeTable(IEEE)
114 updateIEEE = func(crc uint32, p []byte) uint32 {
115 return slicingUpdate(crc, ieeeTable8, p)
116 }
117 }
118 })
119 120 // MakeTable returns a [Table] constructed from the specified polynomial.
121 // The contents of this [Table] must not be modified.
122 func MakeTable(poly uint32) *Table {
123 switch poly {
124 case IEEE:
125 ieeeInitOnce()
126 return IEEETable
127 case Castagnoli:
128 castagnoliInitOnce()
129 return castagnoliTable
130 default:
131 return simpleMakeTable(poly)
132 }
133 }
134 135 // digest represents the partial evaluation of a checksum.
136 type digest struct {
137 crc uint32
138 tab *Table
139 }
140 141 // New creates a new [hash.Hash32] computing the CRC-32 checksum using the
142 // polynomial represented by the [Table]. Its Sum method will lay the
143 // value out in big-endian byte order. The returned Hash32 also
144 // implements [encoding.BinaryMarshaler] and [encoding.BinaryUnmarshaler] to
145 // marshal and unmarshal the internal state of the hash.
146 func New(tab *Table) hash.Hash32 {
147 if tab == IEEETable {
148 ieeeInitOnce()
149 }
150 return &digest{0, tab}
151 }
152 153 // NewIEEE creates a new [hash.Hash32] computing the CRC-32 checksum using
154 // the [IEEE] polynomial. Its Sum method will lay the value out in
155 // big-endian byte order. The returned Hash32 also implements
156 // [encoding.BinaryMarshaler] and [encoding.BinaryUnmarshaler] to marshal
157 // and unmarshal the internal state of the hash.
158 func NewIEEE() hash.Hash32 { return New(IEEETable) }
159 160 func (d *digest) Size() int { return Size }
161 162 func (d *digest) BlockSize() int { return 1 }
163 164 func (d *digest) Reset() { d.crc = 0 }
165 166 const (
167 magic = "crc\x01"
168 marshaledSize = len(magic) + 4 + 4
169 )
170 171 func (d *digest) AppendBinary(b []byte) ([]byte, error) {
172 b = append(b, magic...)
173 b = byteorder.BEAppendUint32(b, tableSum(d.tab))
174 b = byteorder.BEAppendUint32(b, d.crc)
175 return b, nil
176 }
177 178 func (d *digest) MarshalBinary() ([]byte, error) {
179 return d.AppendBinary([]byte{:0:marshaledSize})
180 181 }
182 183 func (d *digest) UnmarshalBinary(b []byte) error {
184 if len(b) < len(magic) || b[:len(magic)] != magic {
185 return errors.New("hash/crc32: invalid hash state identifier")
186 }
187 if len(b) != marshaledSize {
188 return errors.New("hash/crc32: invalid hash state size")
189 }
190 if tableSum(d.tab) != byteorder.BEUint32(b[4:]) {
191 return errors.New("hash/crc32: tables do not match")
192 }
193 d.crc = byteorder.BEUint32(b[8:])
194 return nil
195 }
196 197 func (d *digest) Clone() (hash.Cloner, error) {
198 r := *d
199 return &r, nil
200 }
201 202 func update(crc uint32, tab *Table, p []byte, checkInitIEEE bool) uint32 {
203 switch {
204 case haveCastagnoli.Load() && tab == castagnoliTable:
205 return updateCastagnoli(crc, p)
206 case tab == IEEETable:
207 if checkInitIEEE {
208 ieeeInitOnce()
209 }
210 return updateIEEE(crc, p)
211 default:
212 return simpleUpdate(crc, tab, p)
213 }
214 }
215 216 // Update returns the result of adding the bytes in p to the crc.
217 func Update(crc uint32, tab *Table, p []byte) uint32 {
218 // Unfortunately, because IEEETable is exported, IEEE may be used without a
219 // call to MakeTable. We have to make sure it gets initialized in that case.
220 return update(crc, tab, p, true)
221 }
222 223 func (d *digest) Write(p []byte) (n int, err error) {
224 // We only create digest objects through New() which takes care of
225 // initialization in this case.
226 d.crc = update(d.crc, d.tab, p, false)
227 return len(p), nil
228 }
229 230 func (d *digest) Sum32() uint32 { return d.crc }
231 232 func (d *digest) Sum(in []byte) []byte {
233 s := d.Sum32()
234 return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
235 }
236 237 // Checksum returns the CRC-32 checksum of data
238 // using the polynomial represented by the [Table].
239 func Checksum(data []byte, tab *Table) uint32 { return Update(0, tab, data) }
240 241 // ChecksumIEEE returns the CRC-32 checksum of data
242 // using the [IEEE] polynomial.
243 func ChecksumIEEE(data []byte) uint32 {
244 ieeeInitOnce()
245 return updateIEEE(0, data)
246 }
247 248 // tableSum returns the IEEE checksum of table t.
249 func tableSum(t *Table) uint32 {
250 var a [1024]byte
251 b := a[:0]
252 if t != nil {
253 for _, x := range t {
254 b = byteorder.BEAppendUint32(b, x)
255 }
256 }
257 return ChecksumIEEE(b)
258 }
259