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 http://en.wikipedia.org/wiki/Cyclic_redundancy_check for 7 // information. 8 package crc64 9 10 import ( 11 "errors" 12 "hash" 13 ) 14 15 // The size of a CRC-64 checksum in bytes. 16 const Size = 8 17 18 // Predefined polynomials. 19 const ( 20 // The ISO polynomial, defined in ISO 3309 and used in HDLC. 21 ISO = 0xD800000000000000 22 23 // The ECMA polynomial, defined in ECMA 182. 24 ECMA = 0xC96C5795D7870F42 25 ) 26 27 // Table is a 256-word table representing the polynomial for efficient processing. 28 type Table [256]uint64 29 30 var ( 31 slicing8TableISO = makeSlicingBy8Table(makeTable(ISO)) 32 slicing8TableECMA = makeSlicingBy8Table(makeTable(ECMA)) 33 ) 34 35 // MakeTable returns a Table constructed from the specified polynomial. 36 // The contents of this Table must not be modified. 37 func MakeTable(poly uint64) *Table { 38 switch poly { 39 case ISO: 40 return &slicing8TableISO[0] 41 case ECMA: 42 return &slicing8TableECMA[0] 43 default: 44 return makeTable(poly) 45 } 46 } 47 48 func makeTable(poly uint64) *Table { 49 t := new(Table) 50 for i := 0; i < 256; i++ { 51 crc := uint64(i) 52 for j := 0; j < 8; j++ { 53 if crc&1 == 1 { 54 crc = (crc >> 1) ^ poly 55 } else { 56 crc >>= 1 57 } 58 } 59 t[i] = crc 60 } 61 return t 62 } 63 64 func makeSlicingBy8Table(t *Table) *[8]Table { 65 var helperTable [8]Table 66 helperTable[0] = *t 67 for i := 0; i < 256; i++ { 68 crc := t[i] 69 for j := 1; j < 8; j++ { 70 crc = t[crc&0xff] ^ (crc >> 8) 71 helperTable[j][i] = crc 72 } 73 } 74 return &helperTable 75 } 76 77 // digest represents the partial evaluation of a checksum. 78 type digest struct { 79 crc uint64 80 tab *Table 81 } 82 83 // New creates a new hash.Hash64 computing the CRC-64 checksum using the 84 // polynomial represented by the Table. Its Sum method will lay the 85 // value out in big-endian byte order. The returned Hash64 also 86 // implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler to 87 // marshal and unmarshal the internal state of the hash. 88 func New(tab *Table) hash.Hash64 { return &digest{0, tab} } 89 90 func (d *digest) Size() int { return Size } 91 92 func (d *digest) BlockSize() int { return 1 } 93 94 func (d *digest) Reset() { d.crc = 0 } 95 96 const ( 97 magic = "crc\x02" 98 marshaledSize = len(magic) + 8 + 8 99 ) 100 101 func (d *digest) MarshalBinary() ([]byte, error) { 102 b := make([]byte, 0, marshaledSize) 103 b = append(b, magic...) 104 b = appendUint64(b, tableSum(d.tab)) 105 b = appendUint64(b, d.crc) 106 return b, nil 107 } 108 109 func (d *digest) UnmarshalBinary(b []byte) error { 110 if len(b) < len(magic) || string(b[:len(magic)]) != magic { 111 return errors.New("hash/crc64: invalid hash state identifier") 112 } 113 if len(b) != marshaledSize { 114 return errors.New("hash/crc64: invalid hash state size") 115 } 116 if tableSum(d.tab) != readUint64(b[4:]) { 117 return errors.New("hash/crc64: tables do not match") 118 } 119 d.crc = readUint64(b[12:]) 120 return nil 121 } 122 123 func appendUint64(b []byte, x uint64) []byte { 124 a := [8]byte{ 125 byte(x >> 56), 126 byte(x >> 48), 127 byte(x >> 40), 128 byte(x >> 32), 129 byte(x >> 24), 130 byte(x >> 16), 131 byte(x >> 8), 132 byte(x), 133 } 134 return append(b, a[:]...) 135 } 136 137 func readUint64(b []byte) uint64 { 138 _ = b[7] 139 return uint64(b[7]) | uint64(b[6])<<8 | uint64(b[5])<<16 | uint64(b[4])<<24 | 140 uint64(b[3])<<32 | uint64(b[2])<<40 | uint64(b[1])<<48 | uint64(b[0])<<56 141 } 142 143 func update(crc uint64, tab *Table, p []byte) uint64 { 144 crc = ^crc 145 // Table comparison is somewhat expensive, so avoid it for small sizes 146 for len(p) >= 64 { 147 var helperTable *[8]Table 148 if *tab == slicing8TableECMA[0] { 149 helperTable = slicing8TableECMA 150 } else if *tab == slicing8TableISO[0] { 151 helperTable = slicing8TableISO 152 // For smaller sizes creating extended table takes too much time 153 } else if len(p) > 16384 { 154 helperTable = makeSlicingBy8Table(tab) 155 } else { 156 break 157 } 158 // Update using slicing-by-8 159 for len(p) > 8 { 160 crc ^= uint64(p[0]) | uint64(p[1])<<8 | uint64(p[2])<<16 | uint64(p[3])<<24 | 161 uint64(p[4])<<32 | uint64(p[5])<<40 | uint64(p[6])<<48 | uint64(p[7])<<56 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 = appendUint64(b, x) 208 } 209 } 210 return Checksum(b, MakeTable(ISO)) 211 } 212
