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