Source file src/pkg/hash/crc32/crc32.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 crc32 implements the 32-bit cyclic redundancy check, or CRC-32,
     6	// checksum. See http://en.wikipedia.org/wiki/Cyclic_redundancy_check for
     7	// information.
     8	package crc32
     9	
    10	import (
    11		"hash"
    12		"sync"
    13	)
    14	
    15	// The size of a CRC-32 checksum in bytes.
    16	const Size = 4
    17	
    18	// Predefined polynomials.
    19	const (
    20		// Far and away the most common CRC-32 polynomial.
    21		// Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, mpeg-2, ...
    22		IEEE = 0xedb88320
    23	
    24		// Castagnoli's polynomial, used in iSCSI.
    25		// Has better error detection characteristics than IEEE.
    26		// http://dx.doi.org/10.1109/26.231911
    27		Castagnoli = 0x82f63b78
    28	
    29		// Koopman's polynomial.
    30		// Also has better error detection characteristics than IEEE.
    31		// http://dx.doi.org/10.1109/DSN.2002.1028931
    32		Koopman = 0xeb31d82e
    33	)
    34	
    35	// Table is a 256-word table representing the polynomial for efficient processing.
    36	type Table [256]uint32
    37	
    38	// castagnoliTable points to a lazily initialized Table for the Castagnoli
    39	// polynomial. MakeTable will always return this value when asked to make a
    40	// Castagnoli table so we can compare against it to find when the caller is
    41	// using this polynomial.
    42	var castagnoliTable *Table
    43	var castagnoliOnce sync.Once
    44	
    45	func castagnoliInit() {
    46		castagnoliTable = makeTable(Castagnoli)
    47	}
    48	
    49	// IEEETable is the table for the IEEE polynomial.
    50	var IEEETable = makeTable(IEEE)
    51	
    52	// MakeTable returns the Table constructed from the specified polynomial.
    53	func MakeTable(poly uint32) *Table {
    54		switch poly {
    55		case IEEE:
    56			return IEEETable
    57		case Castagnoli:
    58			castagnoliOnce.Do(castagnoliInit)
    59			return castagnoliTable
    60		}
    61		return makeTable(poly)
    62	}
    63	
    64	// makeTable returns the Table constructed from the specified polynomial.
    65	func makeTable(poly uint32) *Table {
    66		t := new(Table)
    67		for i := 0; i < 256; i++ {
    68			crc := uint32(i)
    69			for j := 0; j < 8; j++ {
    70				if crc&1 == 1 {
    71					crc = (crc >> 1) ^ poly
    72				} else {
    73					crc >>= 1
    74				}
    75			}
    76			t[i] = crc
    77		}
    78		return t
    79	}
    80	
    81	// digest represents the partial evaluation of a checksum.
    82	type digest struct {
    83		crc uint32
    84		tab *Table
    85	}
    86	
    87	// New creates a new hash.Hash32 computing the CRC-32 checksum
    88	// using the polynomial represented by the Table.
    89	func New(tab *Table) hash.Hash32 { return &digest{0, tab} }
    90	
    91	// NewIEEE creates a new hash.Hash32 computing the CRC-32 checksum
    92	// using the IEEE polynomial.
    93	func NewIEEE() hash.Hash32 { return New(IEEETable) }
    94	
    95	func (d *digest) Size() int { return Size }
    96	
    97	func (d *digest) BlockSize() int { return 1 }
    98	
    99	func (d *digest) Reset() { d.crc = 0 }
   100	
   101	func update(crc uint32, tab *Table, p []byte) uint32 {
   102		crc = ^crc
   103		for _, v := range p {
   104			crc = tab[byte(crc)^v] ^ (crc >> 8)
   105		}
   106		return ^crc
   107	}
   108	
   109	// Update returns the result of adding the bytes in p to the crc.
   110	func Update(crc uint32, tab *Table, p []byte) uint32 {
   111		if tab == castagnoliTable {
   112			return updateCastagnoli(crc, p)
   113		}
   114		return update(crc, tab, p)
   115	}
   116	
   117	func (d *digest) Write(p []byte) (n int, err error) {
   118		d.crc = Update(d.crc, d.tab, p)
   119		return len(p), nil
   120	}
   121	
   122	func (d *digest) Sum32() uint32 { return d.crc }
   123	
   124	func (d *digest) Sum(in []byte) []byte {
   125		s := d.Sum32()
   126		in = append(in, byte(s>>24))
   127		in = append(in, byte(s>>16))
   128		in = append(in, byte(s>>8))
   129		in = append(in, byte(s))
   130		return in
   131	}
   132	
   133	// Checksum returns the CRC-32 checksum of data
   134	// using the polynomial represented by the Table.
   135	func Checksum(data []byte, tab *Table) uint32 { return Update(0, tab, data) }
   136	
   137	// ChecksumIEEE returns the CRC-32 checksum of data
   138	// using the IEEE polynomial.
   139	func ChecksumIEEE(data []byte) uint32 { return update(0, IEEETable, data) }