crc32_generic.go

Documentation: hash/crc32

		 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