Home | History | Annotate | Download | only in crc32 
      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 //
      9 // Polynomials are represented in LSB-first form also known as reversed representation.
     10 //
     11 // See http://en.wikipedia.org/wiki/Mathematics_of_cyclic_redundancy_checks#Reversed_representations_and_reciprocal_polynomials
     12 // for information.
     13 package crc32
     14 
     15 import (
     16 	"hash"
     17 	"sync"
     18 )
     19 
     20 // The size of a CRC-32 checksum in bytes.
     21 const Size = 4
     22 
     23 // Predefined polynomials.
     24 const (
     25 	// IEEE is by far and away the most common CRC-32 polynomial.
     26 	// Used by ethernet (IEEE 802.3), v.42, fddi, gzip, zip, png, ...
     27 	IEEE = 0xedb88320
     28 
     29 	// Castagnoli's polynomial, used in iSCSI.
     30 	// Has better error detection characteristics than IEEE.
     31 	// http://dx.doi.org/10.1109/26.231911
     32 	Castagnoli = 0x82f63b78
     33 
     34 	// Koopman's polynomial.
     35 	// Also has better error detection characteristics than IEEE.
     36 	// http://dx.doi.org/10.1109/DSN.2002.1028931
     37 	Koopman = 0xeb31d82e
     38 )
     39 
     40 // Table is a 256-word table representing the polynomial for efficient processing.
     41 type Table [256]uint32
     42 
     43 // This file makes use of functions implemented in architecture-specific files.
     44 // The interface that they implement is as follows:
     45 //
     46 //    // archAvailableIEEE reports whether an architecture-specific CRC32-IEEE
     47 //    // algorithm is available.
     48 //    archAvailableIEEE() bool
     49 //
     50 //    // archInitIEEE initializes the architecture-specific CRC3-IEEE algorithm.
     51 //    // It can only be called if archAvailableIEEE() returns true.
     52 //    archInitIEEE()
     53 //
     54 //    // archUpdateIEEE updates the given CRC32-IEEE. It can only be called if
     55 //    // archInitIEEE() was previously called.
     56 //    archUpdateIEEE(crc uint32, p []byte) uint32
     57 //
     58 //    // archAvailableCastagnoli reports whether an architecture-specific
     59 //    // CRC32-C algorithm is available.
     60 //    archAvailableCastagnoli() bool
     61 //
     62 //    // archInitCastagnoli initializes the architecture-specific CRC32-C
     63 //    // algorithm. It can only be called if archAvailableCastagnoli() returns
     64 //    // true.
     65 //    archInitCastagnoli()
     66 //
     67 //    // archUpdateCastagnoli updates the given CRC32-C. It can only be called
     68 //    // if archInitCastagnoli() was previously called.
     69 //    archUpdateCastagnoli(crc uint32, p []byte) uint32
     70 
     71 // castagnoliTable points to a lazily initialized Table for the Castagnoli
     72 // polynomial. MakeTable will always return this value when asked to make a
     73 // Castagnoli table so we can compare against it to find when the caller is
     74 // using this polynomial.
     75 var castagnoliTable *Table
     76 var castagnoliTable8 *slicing8Table
     77 var castagnoliArchImpl bool
     78 var updateCastagnoli func(crc uint32, p []byte) uint32
     79 var castagnoliOnce sync.Once
     80 
     81 func castagnoliInit() {
     82 	castagnoliTable = simpleMakeTable(Castagnoli)
     83 	castagnoliArchImpl = archAvailableCastagnoli()
     84 
     85 	if castagnoliArchImpl {
     86 		archInitCastagnoli()
     87 		updateCastagnoli = archUpdateCastagnoli
     88 	} else {
     89 		// Initialize the slicing-by-8 table.
     90 		castagnoliTable8 = slicingMakeTable(Castagnoli)
     91 		updateCastagnoli = func(crc uint32, p []byte) uint32 {
     92 			return slicingUpdate(crc, castagnoliTable8, p)
     93 		}
     94 	}
     95 }
     96 
     97 // IEEETable is the table for the IEEE polynomial.
     98 var IEEETable = simpleMakeTable(IEEE)
     99 
    100 // ieeeTable8 is the slicing8Table for IEEE
    101 var ieeeTable8 *slicing8Table
    102 var ieeeArchImpl bool
    103 var updateIEEE func(crc uint32, p []byte) uint32
    104 var ieeeOnce sync.Once
    105 
    106 func ieeeInit() {
    107 	ieeeArchImpl = archAvailableIEEE()
    108 
    109 	if ieeeArchImpl {
    110 		archInitIEEE()
    111 		updateIEEE = archUpdateIEEE
    112 	} else {
    113 		// Initialize the slicing-by-8 table.
    114 		ieeeTable8 = slicingMakeTable(IEEE)
    115 		updateIEEE = func(crc uint32, p []byte) uint32 {
    116 			return slicingUpdate(crc, ieeeTable8, p)
    117 		}
    118 	}
    119 }
    120 
    121 // MakeTable returns a Table constructed from the specified polynomial.
    122 // The contents of this Table must not be modified.
    123 func MakeTable(poly uint32) *Table {
    124 	switch poly {
    125 	case IEEE:
    126 		ieeeOnce.Do(ieeeInit)
    127 		return IEEETable
    128 	case Castagnoli:
    129 		castagnoliOnce.Do(castagnoliInit)
    130 		return castagnoliTable
    131 	}
    132 	return simpleMakeTable(poly)
    133 }
    134 
    135 // digest represents the partial evaluation of a checksum.
    136 type digest struct {
    137 	crc uint32
    138 	tab *Table
    139 }
    140 
    141 // New creates a new hash.Hash32 computing the CRC-32 checksum
    142 // using the polynomial represented by the Table.
    143 // Its Sum method will lay the value out in big-endian byte order.
    144 func New(tab *Table) hash.Hash32 {
    145 	if tab == IEEETable {
    146 		ieeeOnce.Do(ieeeInit)
    147 	}
    148 	return &digest{0, tab}
    149 }
    150 
    151 // NewIEEE creates a new hash.Hash32 computing the CRC-32 checksum
    152 // using the IEEE polynomial.
    153 // Its Sum method will lay the value out in big-endian byte order.
    154 func NewIEEE() hash.Hash32 { return New(IEEETable) }
    155 
    156 func (d *digest) Size() int { return Size }
    157 
    158 func (d *digest) BlockSize() int { return 1 }
    159 
    160 func (d *digest) Reset() { d.crc = 0 }
    161 
    162 // Update returns the result of adding the bytes in p to the crc.
    163 func Update(crc uint32, tab *Table, p []byte) uint32 {
    164 	switch tab {
    165 	case castagnoliTable:
    166 		return updateCastagnoli(crc, p)
    167 	case IEEETable:
    168 		// Unfortunately, because IEEETable is exported, IEEE may be used without a
    169 		// call to MakeTable. We have to make sure it gets initialized in that case.
    170 		ieeeOnce.Do(ieeeInit)
    171 		return updateIEEE(crc, p)
    172 	default:
    173 		return simpleUpdate(crc, tab, p)
    174 	}
    175 }
    176 
    177 func (d *digest) Write(p []byte) (n int, err error) {
    178 	switch d.tab {
    179 	case castagnoliTable:
    180 		d.crc = updateCastagnoli(d.crc, p)
    181 	case IEEETable:
    182 		// We only create digest objects through New() which takes care of
    183 		// initialization in this case.
    184 		d.crc = updateIEEE(d.crc, p)
    185 	default:
    186 		d.crc = simpleUpdate(d.crc, d.tab, p)
    187 	}
    188 	return len(p), nil
    189 }
    190 
    191 func (d *digest) Sum32() uint32 { return d.crc }
    192 
    193 func (d *digest) Sum(in []byte) []byte {
    194 	s := d.Sum32()
    195 	return append(in, byte(s>>24), byte(s>>16), byte(s>>8), byte(s))
    196 }
    197 
    198 // Checksum returns the CRC-32 checksum of data
    199 // using the polynomial represented by the Table.
    200 func Checksum(data []byte, tab *Table) uint32 { return Update(0, tab, data) }
    201 
    202 // ChecksumIEEE returns the CRC-32 checksum of data
    203 // using the IEEE polynomial.
    204 func ChecksumIEEE(data []byte) uint32 {
    205 	ieeeOnce.Do(ieeeInit)
    206 	return updateIEEE(0, data)
    207 }
    208