Home | History | Annotate | Download | only in crc64 
      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 "hash"
     11 
     12 // The size of a CRC-64 checksum in bytes.
     13 const Size = 8
     14 
     15 // Predefined polynomials.
     16 const (
     17 	// The ISO polynomial, defined in ISO 3309 and used in HDLC.
     18 	ISO = 0xD800000000000000
     19 
     20 	// The ECMA polynomial, defined in ECMA 182.
     21 	ECMA = 0xC96C5795D7870F42
     22 )
     23 
     24 // Table is a 256-word table representing the polynomial for efficient processing.
     25 type Table [256]uint64
     26 
     27 var (
     28 	slicing8TableISO  = makeSlicingBy8Table(makeTable(ISO))
     29 	slicing8TableECMA = makeSlicingBy8Table(makeTable(ECMA))
     30 )
     31 
     32 // MakeTable returns a Table constructed from the specified polynomial.
     33 // The contents of this Table must not be modified.
     34 func MakeTable(poly uint64) *Table {
     35 	switch poly {
     36 	case ISO:
     37 		return &slicing8TableISO[0]
     38 	case ECMA:
     39 		return &slicing8TableECMA[0]
     40 	default:
     41 		return makeTable(poly)
     42 	}
     43 }
     44 
     45 func makeTable(poly uint64) *Table {
     46 	t := new(Table)
     47 	for i := 0; i < 256; i++ {
     48 		crc := uint64(i)
     49 		for j := 0; j < 8; j++ {
     50 			if crc&1 == 1 {
     51 				crc = (crc >> 1) ^ poly
     52 			} else {
     53 				crc >>= 1
     54 			}
     55 		}
     56 		t[i] = crc
     57 	}
     58 	return t
     59 }
     60 
     61 func makeSlicingBy8Table(t *Table) *[8]Table {
     62 	var helperTable [8]Table
     63 	helperTable[0] = *t
     64 	for i := 0; i < 256; i++ {
     65 		crc := t[i]
     66 		for j := 1; j < 8; j++ {
     67 			crc = t[crc&0xff] ^ (crc >> 8)
     68 			helperTable[j][i] = crc
     69 		}
     70 	}
     71 	return &helperTable
     72 }
     73 
     74 // digest represents the partial evaluation of a checksum.
     75 type digest struct {
     76 	crc uint64
     77 	tab *Table
     78 }
     79 
     80 // New creates a new hash.Hash64 computing the CRC-64 checksum
     81 // using the polynomial represented by the Table.
     82 // Its Sum method will lay the value out in big-endian byte order.
     83 func New(tab *Table) hash.Hash64 { return &digest{0, tab} }
     84 
     85 func (d *digest) Size() int { return Size }
     86 
     87 func (d *digest) BlockSize() int { return 1 }
     88 
     89 func (d *digest) Reset() { d.crc = 0 }
     90 
     91 func update(crc uint64, tab *Table, p []byte) uint64 {
     92 	crc = ^crc
     93 	// Table comparison is somewhat expensive, so avoid it for small sizes
     94 	for len(p) >= 64 {
     95 		var helperTable *[8]Table
     96 		if *tab == slicing8TableECMA[0] {
     97 			helperTable = slicing8TableECMA
     98 		} else if *tab == slicing8TableISO[0] {
     99 			helperTable = slicing8TableISO
    100 			// For smaller sizes creating extended table takes too much time
    101 		} else if len(p) > 16384 {
    102 			helperTable = makeSlicingBy8Table(tab)
    103 		} else {
    104 			break
    105 		}
    106 		// Update using slicing-by-8
    107 		for len(p) > 8 {
    108 			crc ^= uint64(p[0]) | uint64(p[1])<<8 | uint64(p[2])<<16 | uint64(p[3])<<24 |
    109 				uint64(p[4])<<32 | uint64(p[5])<<40 | uint64(p[6])<<48 | uint64(p[7])<<56
    110 			crc = helperTable[7][crc&0xff] ^
    111 				helperTable[6][(crc>>8)&0xff] ^
    112 				helperTable[5][(crc>>16)&0xff] ^
    113 				helperTable[4][(crc>>24)&0xff] ^
    114 				helperTable[3][(crc>>32)&0xff] ^
    115 				helperTable[2][(crc>>40)&0xff] ^
    116 				helperTable[1][(crc>>48)&0xff] ^
    117 				helperTable[0][crc>>56]
    118 			p = p[8:]
    119 		}
    120 	}
    121 	// For reminders or small sizes
    122 	for _, v := range p {
    123 		crc = tab[byte(crc)^v] ^ (crc >> 8)
    124 	}
    125 	return ^crc
    126 }
    127 
    128 // Update returns the result of adding the bytes in p to the crc.
    129 func Update(crc uint64, tab *Table, p []byte) uint64 {
    130 	return update(crc, tab, p)
    131 }
    132 
    133 func (d *digest) Write(p []byte) (n int, err error) {
    134 	d.crc = update(d.crc, d.tab, p)
    135 	return len(p), nil
    136 }
    137 
    138 func (d *digest) Sum64() uint64 { return d.crc }
    139 
    140 func (d *digest) Sum(in []byte) []byte {
    141 	s := d.Sum64()
    142 	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))
    143 }
    144 
    145 // Checksum returns the CRC-64 checksum of data
    146 // using the polynomial represented by the Table.
    147 func Checksum(data []byte, tab *Table) uint64 { return update(0, tab, data) }
    148