Source file src/hash/crc32/crc32_generic.go

     1	// Copyright 2011 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	// This file contains CRC32 algorithms that are not specific to any architecture
     6	// and don't use hardware acceleration.
     7	//
     8	// The simple (and slow) CRC32 implementation only uses a 256*4 bytes table.
     9	//
    10	// The slicing-by-8 algorithm is a faster implementation that uses a bigger
    11	// table (8*256*4 bytes).
    12	
    13	package crc32
    14	
    15	// simpleMakeTable allocates and constructs a Table for the specified
    16	// polynomial. The table is suitable for use with the simple algorithm
    17	// (simpleUpdate).
    18	func simpleMakeTable(poly uint32) *Table {
    19		t := new(Table)
    20		simplePopulateTable(poly, t)
    21		return t
    22	}
    23	
    24	// simplePopulateTable constructs a Table for the specified polynomial, suitable
    25	// for use with simpleUpdate.
    26	func simplePopulateTable(poly uint32, t *Table) {
    27		for i := 0; i < 256; i++ {
    28			crc := uint32(i)
    29			for j := 0; j < 8; j++ {
    30				if crc&1 == 1 {
    31					crc = (crc >> 1) ^ poly
    32				} else {
    33					crc >>= 1
    34				}
    35			}
    36			t[i] = crc
    37		}
    38	}
    39	
    40	// simpleUpdate uses the simple algorithm to update the CRC, given a table that
    41	// was previously computed using simpleMakeTable.
    42	func simpleUpdate(crc uint32, tab *Table, p []byte) uint32 {
    43		crc = ^crc
    44		for _, v := range p {
    45			crc = tab[byte(crc)^v] ^ (crc >> 8)
    46		}
    47		return ^crc
    48	}
    49	
    50	// Use slicing-by-8 when payload >= this value.
    51	const slicing8Cutoff = 16
    52	
    53	// slicing8Table is array of 8 Tables, used by the slicing-by-8 algorithm.
    54	type slicing8Table [8]Table
    55	
    56	// slicingMakeTable constructs a slicing8Table for the specified polynomial. The
    57	// table is suitable for use with the slicing-by-8 algorithm (slicingUpdate).
    58	func slicingMakeTable(poly uint32) *slicing8Table {
    59		t := new(slicing8Table)
    60		simplePopulateTable(poly, &t[0])
    61		for i := 0; i < 256; i++ {
    62			crc := t[0][i]
    63			for j := 1; j < 8; j++ {
    64				crc = t[0][crc&0xFF] ^ (crc >> 8)
    65				t[j][i] = crc
    66			}
    67		}
    68		return t
    69	}
    70	
    71	// slicingUpdate uses the slicing-by-8 algorithm to update the CRC, given a
    72	// table that was previously computed using slicingMakeTable.
    73	func slicingUpdate(crc uint32, tab *slicing8Table, p []byte) uint32 {
    74		if len(p) >= slicing8Cutoff {
    75			crc = ^crc
    76			for len(p) > 8 {
    77				crc ^= uint32(p[0]) | uint32(p[1])<<8 | uint32(p[2])<<16 | uint32(p[3])<<24
    78				crc = tab[0][p[7]] ^ tab[1][p[6]] ^ tab[2][p[5]] ^ tab[3][p[4]] ^
    79					tab[4][crc>>24] ^ tab[5][(crc>>16)&0xFF] ^
    80					tab[6][(crc>>8)&0xFF] ^ tab[7][crc&0xFF]
    81				p = p[8:]
    82			}
    83			crc = ^crc
    84		}
    85		if len(p) == 0 {
    86			return crc
    87		}
    88		return simpleUpdate(crc, &tab[0], p)
    89	}
    90	

View as plain text