crc64window

Documentation

Overview

Package crc64window provides CRCs over fixed-sized, rolling windows of bytes.

It uses the same polynomial representation and CRC conditioning as hash/crc64, so the results are the same as computing hash/crc64 over the window of the last sz bytes added, where sz is the window size. Thus, in this code, rolling and nonRolling will receive the same value.

w := crc64window.New(crc64window.ECMA, 3)  // Window size is 3 bytes.
w.Advance(0x17)
w.Advance(0x92)
w.Advance(0x04)
rolling := w.Advance(0x28)   // Rolls 0x17 out, and 0x28 in.

nonRolling := crc64.Update(0, crc64.MakeTable(crc64.ECMA), []byte{0x92, 0x04, 0x28})

Strangely, hash/crc64's specification does not mention which of the many possible bit representations and conditioning choices it uses. We assume it will not change from the following, which was gleaned from the hash/crc64 source code:

• All messages to be processed, CRC values, and CRC polynomials are polynomials in x whose coefficients are in Z(2).
• CRC values are represented by uint64 values in which bit i of the integer represents the coefficient of x**(63-i) in the polynomial.
• CRC polynomials are represented like CRC values, except that the x**64 coefficient of the CRC polynomial is implicitly 1, and not stored.
• Messages to be processed are represented by byte vectors in which the lowest-order bit of the first byte is the highest-degree polynomial coefficient.
• For a CRC polynomial p and a message m, the CRC value: CRC(p, m) = c + ((c * (x**len(m)) + (m * x**64)) mod p) where the conditioning constant c = x**63 + x**62 + x**61 + ... + x + 1, and len(m) is the number of bits in m.

Index

• Constants
• type Window
  • func New(poly uint64, size int) *Window
  • func (w *Window) Advance(b byte) uint64

Constants

const ECMA = 0xc96c5795d7870f42

The ECMA-64 polynomial, defined in ECMA 182. This polynomial is recommended for use with this package, though other polynomials found in hash/crc64 will also work.

Types

type Window

type Window struct {
	// contains filtered or unexported fields
}

A Window contains the state needed to compute a CRC over a fixed-sized, rolling window of data.

func New

func New(poly uint64, size int) *Window

New() returns a Window with the given size and CRC polynomial. Initially, all the bytes in the window are zero. Requires size > 0.

func (*Window) Advance

func (w *Window) Advance(b byte) uint64

Advance() removes the first byte from window *w, adds b as the new last byte, and returns the CRC of the window.