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

View as plain text