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 9package crc32 10 11import ( 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 23func 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 29func 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 39func ieeeCLMUL(crc uint32, p []byte) uint32 40 41const castagnoliK1 = 168 42const castagnoliK2 = 1344 43 44type sse42Table [4]Table 45 46var castagnoliSSE42TableK1 *sse42Table 47var castagnoliSSE42TableK2 *sse42Table 48 49func archAvailableCastagnoli() bool { 50 return cpu.X86.HasSSE42 51} 52 53func 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. 78func 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 85func 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 196func archAvailableIEEE() bool { 197 return cpu.X86.HasPCLMULQDQ && cpu.X86.HasSSE41 198} 199 200var archIeeeTable8 *slicing8Table 201 202func 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 210func 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