...
Run Format

Source file src/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	//
     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	

View as plain text