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