libgo/go/hash/crc64/crc64.go

   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 }