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 = &sse42Table{}
58 castagnoliSSE42TableK2 = &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