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