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