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