...

Source file src/hash/crc32/crc32_amd64.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  // AMD64-specific hardware-assisted CRC32 algorithms. See crc32.go for a
     6  // description of the interface that each architecture-specific file
     7  // implements.
     8  
     9  package crc32
    10  
    11  import (
    12  	"internal/cpu"
    13  	"unsafe"
    14  )
    15  
    16  // This file contains the code to call the SSE 4.2 version of the Castagnoli
    17  // and IEEE CRC.
    18  
    19  // castagnoliSSE42 is defined in crc32_amd64.s and uses the SSE 4.2 CRC32
    20  // instruction.
    21  //
    22  //go:noescape
    23  func castagnoliSSE42(crc uint32, p []byte) uint32
    24  
    25  // castagnoliSSE42Triple is defined in crc32_amd64.s and uses the SSE 4.2 CRC32
    26  // instruction.
    27  //
    28  //go:noescape
    29  func castagnoliSSE42Triple(
    30  	crcA, crcB, crcC uint32,
    31  	a, b, c []byte,
    32  	rounds uint32,
    33  ) (retA uint32, retB uint32, retC uint32)
    34  
    35  // ieeeCLMUL is defined in crc_amd64.s and uses the PCLMULQDQ
    36  // instruction as well as SSE 4.1.
    37  //
    38  //go:noescape
    39  func ieeeCLMUL(crc uint32, p []byte) uint32
    40  
    41  const castagnoliK1 = 168
    42  const castagnoliK2 = 1344
    43  
    44  type sse42Table [4]Table
    45  
    46  var castagnoliSSE42TableK1 *sse42Table
    47  var castagnoliSSE42TableK2 *sse42Table
    48  
    49  func archAvailableCastagnoli() bool {
    50  	return cpu.X86.HasSSE42
    51  }
    52  
    53  func archInitCastagnoli() {
    54  	if !cpu.X86.HasSSE42 {
    55  		panic("arch-specific Castagnoli not available")
    56  	}
    57  	castagnoliSSE42TableK1 = new(sse42Table)
    58  	castagnoliSSE42TableK2 = new(sse42Table)
    59  	// See description in updateCastagnoli.
    60  	//    t[0][i] = CRC(i000, O)
    61  	//    t[1][i] = CRC(0i00, O)
    62  	//    t[2][i] = CRC(00i0, O)
    63  	//    t[3][i] = CRC(000i, O)
    64  	// where O is a sequence of K zeros.
    65  	var tmp [castagnoliK2]byte
    66  	for b := 0; b < 4; b++ {
    67  		for i := 0; i < 256; i++ {
    68  			val := uint32(i) << uint32(b*8)
    69  			castagnoliSSE42TableK1[b][i] = castagnoliSSE42(val, tmp[:castagnoliK1])
    70  			castagnoliSSE42TableK2[b][i] = castagnoliSSE42(val, tmp[:])
    71  		}
    72  	}
    73  }
    74  
    75  // castagnoliShift computes the CRC32-C of K1 or K2 zeroes (depending on the
    76  // table given) with the given initial crc value. This corresponds to
    77  // CRC(crc, O) in the description in updateCastagnoli.
    78  func castagnoliShift(table *sse42Table, crc uint32) uint32 {
    79  	return table[3][crc>>24] ^
    80  		table[2][(crc>>16)&0xFF] ^
    81  		table[1][(crc>>8)&0xFF] ^
    82  		table[0][crc&0xFF]
    83  }
    84  
    85  func archUpdateCastagnoli(crc uint32, p []byte) uint32 {
    86  	if !cpu.X86.HasSSE42 {
    87  		panic("not available")
    88  	}
    89  
    90  	// This method is inspired from the algorithm in Intel's white paper:
    91  	//    "Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction"
    92  	// The same strategy of splitting the buffer in three is used but the
    93  	// combining calculation is different; the complete derivation is explained
    94  	// below.
    95  	//
    96  	// -- The basic idea --
    97  	//
    98  	// The CRC32 instruction (available in SSE4.2) can process 8 bytes at a
    99  	// time. In recent Intel architectures the instruction takes 3 cycles;
   100  	// however the processor can pipeline up to three instructions if they
   101  	// don't depend on each other.
   102  	//
   103  	// Roughly this means that we can process three buffers in about the same
   104  	// time we can process one buffer.
   105  	//
   106  	// The idea is then to split the buffer in three, CRC the three pieces
   107  	// separately and then combine the results.
   108  	//
   109  	// Combining the results requires precomputed tables, so we must choose a
   110  	// fixed buffer length to optimize. The longer the length, the faster; but
   111  	// only buffers longer than this length will use the optimization. We choose
   112  	// two cutoffs and compute tables for both:
   113  	//  - one around 512: 168*3=504
   114  	//  - one around 4KB: 1344*3=4032
   115  	//
   116  	// -- The nitty gritty --
   117  	//
   118  	// Let CRC(I, X) be the non-inverted CRC32-C of the sequence X (with
   119  	// initial non-inverted CRC I). This function has the following properties:
   120  	//   (a) CRC(I, AB) = CRC(CRC(I, A), B)
   121  	//   (b) CRC(I, A xor B) = CRC(I, A) xor CRC(0, B)
   122  	//
   123  	// Say we want to compute CRC(I, ABC) where A, B, C are three sequences of
   124  	// K bytes each, where K is a fixed constant. Let O be the sequence of K zero
   125  	// bytes.
   126  	//
   127  	// CRC(I, ABC) = CRC(I, ABO xor C)
   128  	//             = CRC(I, ABO) xor CRC(0, C)
   129  	//             = CRC(CRC(I, AB), O) xor CRC(0, C)
   130  	//             = CRC(CRC(I, AO xor B), O) xor CRC(0, C)
   131  	//             = CRC(CRC(I, AO) xor CRC(0, B), O) xor CRC(0, C)
   132  	//             = CRC(CRC(CRC(I, A), O) xor CRC(0, B), O) xor CRC(0, C)
   133  	//
   134  	// The castagnoliSSE42Triple function can compute CRC(I, A), CRC(0, B),
   135  	// and CRC(0, C) efficiently.  We just need to find a way to quickly compute
   136  	// CRC(uvwx, O) given a 4-byte initial value uvwx. We can precompute these
   137  	// values; since we can't have a 32-bit table, we break it up into four
   138  	// 8-bit tables:
   139  	//
   140  	//    CRC(uvwx, O) = CRC(u000, O) xor
   141  	//                   CRC(0v00, O) xor
   142  	//                   CRC(00w0, O) xor
   143  	//                   CRC(000x, O)
   144  	//
   145  	// We can compute tables corresponding to the four terms for all 8-bit
   146  	// values.
   147  
   148  	crc = ^crc
   149  
   150  	// If a buffer is long enough to use the optimization, process the first few
   151  	// bytes to align the buffer to an 8 byte boundary (if necessary).
   152  	if len(p) >= castagnoliK1*3 {
   153  		delta := int(uintptr(unsafe.Pointer(&p[0])) & 7)
   154  		if delta != 0 {
   155  			delta = 8 - delta
   156  			crc = castagnoliSSE42(crc, p[:delta])
   157  			p = p[delta:]
   158  		}
   159  	}
   160  
   161  	// Process 3*K2 at a time.
   162  	for len(p) >= castagnoliK2*3 {
   163  		// Compute CRC(I, A), CRC(0, B), and CRC(0, C).
   164  		crcA, crcB, crcC := castagnoliSSE42Triple(
   165  			crc, 0, 0,
   166  			p, p[castagnoliK2:], p[castagnoliK2*2:],
   167  			castagnoliK2/24)
   168  
   169  		// CRC(I, AB) = CRC(CRC(I, A), O) xor CRC(0, B)
   170  		crcAB := castagnoliShift(castagnoliSSE42TableK2, crcA) ^ crcB
   171  		// CRC(I, ABC) = CRC(CRC(I, AB), O) xor CRC(0, C)
   172  		crc = castagnoliShift(castagnoliSSE42TableK2, crcAB) ^ crcC
   173  		p = p[castagnoliK2*3:]
   174  	}
   175  
   176  	// Process 3*K1 at a time.
   177  	for len(p) >= castagnoliK1*3 {
   178  		// Compute CRC(I, A), CRC(0, B), and CRC(0, C).
   179  		crcA, crcB, crcC := castagnoliSSE42Triple(
   180  			crc, 0, 0,
   181  			p, p[castagnoliK1:], p[castagnoliK1*2:],
   182  			castagnoliK1/24)
   183  
   184  		// CRC(I, AB) = CRC(CRC(I, A), O) xor CRC(0, B)
   185  		crcAB := castagnoliShift(castagnoliSSE42TableK1, crcA) ^ crcB
   186  		// CRC(I, ABC) = CRC(CRC(I, AB), O) xor CRC(0, C)
   187  		crc = castagnoliShift(castagnoliSSE42TableK1, crcAB) ^ crcC
   188  		p = p[castagnoliK1*3:]
   189  	}
   190  
   191  	// Use the simple implementation for what's left.
   192  	crc = castagnoliSSE42(crc, p)
   193  	return ^crc
   194  }
   195  
   196  func archAvailableIEEE() bool {
   197  	return cpu.X86.HasPCLMULQDQ && cpu.X86.HasSSE41
   198  }
   199  
   200  var archIeeeTable8 *slicing8Table
   201  
   202  func archInitIEEE() {
   203  	if !cpu.X86.HasPCLMULQDQ || !cpu.X86.HasSSE41 {
   204  		panic("not available")
   205  	}
   206  	// We still use slicing-by-8 for small buffers.
   207  	archIeeeTable8 = slicingMakeTable(IEEE)
   208  }
   209  
   210  func archUpdateIEEE(crc uint32, p []byte) uint32 {
   211  	if !cpu.X86.HasPCLMULQDQ || !cpu.X86.HasSSE41 {
   212  		panic("not available")
   213  	}
   214  
   215  	if len(p) >= 64 {
   216  		left := len(p) & 15
   217  		do := len(p) - left
   218  		crc = ^ieeeCLMUL(^crc, p[:do])
   219  		p = p[do:]
   220  	}
   221  	if len(p) == 0 {
   222  		return crc
   223  	}
   224  	return slicingUpdate(crc, archIeeeTable8, p)
   225  }
   226  

View as plain text