crc64.mx raw
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 crc64 implements the 64-bit cyclic redundancy check, or CRC-64,
6 // checksum. See https://en.wikipedia.org/wiki/Cyclic_redundancy_check for
7 // information.
8 package crc64
9
10 import (
11 "errors"
12 "hash"
13 "internal/byteorder"
14 "sync"
15 )
16
17 // The size of a CRC-64 checksum in bytes.
18 const Size = 8
19
20 // Predefined polynomials.
21 const (
22 // The ISO polynomial, defined in ISO 3309 and used in HDLC.
23 ISO = 0xD800000000000000
24
25 // The ECMA polynomial, defined in ECMA 182.
26 ECMA = 0xC96C5795D7870F42
27 )
28
29 // Table is a 256-word table representing the polynomial for efficient processing.
30 type Table [256]uint64
31
32 var (
33 slicing8TableISO *[8]Table
34 slicing8TableECMA *[8]Table
35 )
36
37 var buildSlicing8TablesOnce = sync.OnceFunc(buildSlicing8Tables)
38
39 func buildSlicing8Tables() {
40 slicing8TableISO = makeSlicingBy8Table(makeTable(ISO))
41 slicing8TableECMA = makeSlicingBy8Table(makeTable(ECMA))
42 }
43
44 // MakeTable returns a [Table] constructed from the specified polynomial.
45 // The contents of this [Table] must not be modified.
46 func MakeTable(poly uint64) *Table {
47 buildSlicing8TablesOnce()
48 switch poly {
49 case ISO:
50 return &slicing8TableISO[0]
51 case ECMA:
52 return &slicing8TableECMA[0]
53 default:
54 return makeTable(poly)
55 }
56 }
57
58 func makeTable(poly uint64) *Table {
59 t := &Table{}
60 for i := 0; i < 256; i++ {
61 crc := uint64(i)
62 for j := 0; j < 8; j++ {
63 if crc&1 == 1 {
64 crc = (crc >> 1) ^ poly
65 } else {
66 crc >>= 1
67 }
68 }
69 t[i] = crc
70 }
71 return t
72 }
73
74 func makeSlicingBy8Table(t *Table) *[8]Table {
75 var helperTable [8]Table
76 helperTable[0] = *t
77 for i := 0; i < 256; i++ {
78 crc := t[i]
79 for j := 1; j < 8; j++ {
80 crc = t[crc&0xff] ^ (crc >> 8)
81 helperTable[j][i] = crc
82 }
83 }
84 return &helperTable
85 }
86
87 // digest represents the partial evaluation of a checksum.
88 type digest struct {
89 crc uint64
90 tab *Table
91 }
92
93 // New creates a new hash.Hash64 computing the CRC-64 checksum using the
94 // polynomial represented by the [Table]. Its Sum method will lay the
95 // value out in big-endian byte order. The returned Hash64 also
96 // implements [encoding.BinaryMarshaler] and [encoding.BinaryUnmarshaler] to
97 // marshal and unmarshal the internal state of the hash.
98 func New(tab *Table) hash.Hash64 { return &digest{0, tab} }
99
100 func (d *digest) Size() int { return Size }
101
102 func (d *digest) BlockSize() int { return 1 }
103
104 func (d *digest) Reset() { d.crc = 0 }
105
106 const (
107 magic = "crc\x02"
108 marshaledSize = len(magic) + 8 + 8
109 )
110
111 func (d *digest) AppendBinary(b []byte) ([]byte, error) {
112 b = append(b, magic...)
113 b = byteorder.BEAppendUint64(b, tableSum(d.tab))
114 b = byteorder.BEAppendUint64(b, d.crc)
115 return b, nil
116 }
117
118 func (d *digest) MarshalBinary() ([]byte, error) {
119 return d.AppendBinary([]byte{:0:marshaledSize})
120 }
121
122 func (d *digest) UnmarshalBinary(b []byte) error {
123 if len(b) < len(magic) || b[:len(magic)] != magic {
124 return errors.New("hash/crc64: invalid hash state identifier")
125 }
126 if len(b) != marshaledSize {
127 return errors.New("hash/crc64: invalid hash state size")
128 }
129 if tableSum(d.tab) != byteorder.BEUint64(b[4:]) {
130 return errors.New("hash/crc64: tables do not match")
131 }
132 d.crc = byteorder.BEUint64(b[12:])
133 return nil
134 }
135
136 func (d *digest) Clone() (hash.Cloner, error) {
137 r := *d
138 return &r, nil
139 }
140
141 func update(crc uint64, tab *Table, p []byte) uint64 {
142 buildSlicing8TablesOnce()
143 crc = ^crc
144 // Table comparison is somewhat expensive, so avoid it for small sizes
145 for len(p) >= 64 {
146 var helperTable *[8]Table
147 if *tab == slicing8TableECMA[0] {
148 helperTable = slicing8TableECMA
149 } else if *tab == slicing8TableISO[0] {
150 helperTable = slicing8TableISO
151 // For smaller sizes creating extended table takes too much time
152 } else if len(p) >= 2048 {
153 // According to the tests between various x86 and arm CPUs, 2k is a reasonable
154 // threshold for now. This may change in the future.
155 helperTable = makeSlicingBy8Table(tab)
156 } else {
157 break
158 }
159 // Update using slicing-by-8
160 for len(p) > 8 {
161 crc ^= byteorder.LEUint64(p)
162 crc = helperTable[7][crc&0xff] ^
163 helperTable[6][(crc>>8)&0xff] ^
164 helperTable[5][(crc>>16)&0xff] ^
165 helperTable[4][(crc>>24)&0xff] ^
166 helperTable[3][(crc>>32)&0xff] ^
167 helperTable[2][(crc>>40)&0xff] ^
168 helperTable[1][(crc>>48)&0xff] ^
169 helperTable[0][crc>>56]
170 p = p[8:]
171 }
172 }
173 // For reminders or small sizes
174 for _, v := range p {
175 crc = tab[byte(crc)^v] ^ (crc >> 8)
176 }
177 return ^crc
178 }
179
180 // Update returns the result of adding the bytes in p to the crc.
181 func Update(crc uint64, tab *Table, p []byte) uint64 {
182 return update(crc, tab, p)
183 }
184
185 func (d *digest) Write(p []byte) (n int, err error) {
186 d.crc = update(d.crc, d.tab, p)
187 return len(p), nil
188 }
189
190 func (d *digest) Sum64() uint64 { return d.crc }
191
192 func (d *digest) Sum(in []byte) []byte {
193 s := d.Sum64()
194 return append(in, byte(s>>56), byte(s>>48), byte(s>>40), byte(s>>32), byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
195 }
196
197 // Checksum returns the CRC-64 checksum of data
198 // using the polynomial represented by the [Table].
199 func Checksum(data []byte, tab *Table) uint64 { return update(0, tab, data) }
200
201 // tableSum returns the ISO checksum of table t.
202 func tableSum(t *Table) uint64 {
203 var a [2048]byte
204 b := a[:0]
205 if t != nil {
206 for _, x := range t {
207 b = byteorder.BEAppendUint64(b, x)
208 }
209 }
210 return Checksum(b, MakeTable(ISO))
211 }
212