libgo/go/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 // +build ignore
  10
  11 package crc32
  12
  13 import (
  14         "internal/cpu"
  15         "unsafe"
  16 )
  17
  18 // This file contains the code to call the SSE 4.2 version of the Castagnoli
  19 // and IEEE CRC.
  20
  21 // castagnoliSSE42 is defined in crc32_amd64.s and uses the SSE 4.2 CRC32
  22 // instruction.
  23 //go:noescape
  24 func castagnoliSSE42(crc uint32, p []byte) uint32
  25
  26 // castagnoliSSE42Triple is defined in crc32_amd64.s and uses the SSE 4.2 CRC32
  27 // instruction.
  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 //go:noescape
  38 func ieeeCLMUL(crc uint32, p []byte) uint32
  39
  40 const castagnoliK1 = 168
  41 const castagnoliK2 = 1344
  42
  43 type sse42Table [4]Table
  44
  45 var castagnoliSSE42TableK1 *sse42Table
  46 var castagnoliSSE42TableK2 *sse42Table
  47
  48 func archAvailableCastagnoli() bool {
  49         return cpu.X86.HasSSE42
  50 }
  51
  52 func archInitCastagnoli() {
  53         if !cpu.X86.HasSSE42 {
  54                 panic("arch-specific Castagnoli not available")
  55         }
  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[:])
  70                 }
  71         }
  72 }
  73
  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] ^
  81                 table[0][crc&0xFF]
  82 }
  83
  84 func archUpdateCastagnoli(crc uint32, p []byte) uint32 {
  85         if !cpu.X86.HasSSE42 {
  86                 panic("not available")
  87         }
  88
  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
  93         // below.
  94         //
  95         // -- The basic idea --
  96         //
  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.
 101         //
 102         // Roughly this means that we can process three buffers in about the same
 103         // time we can process one buffer.
 104         //
 105         // The idea is then to split the buffer in three, CRC the three pieces
 106         // separately and then combine the results.
 107         //
 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
 114         //
 115         // -- The nitty gritty --
 116         //
 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)
 121         //
 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
 124         // bytes.
 125         //
 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)
 132         //
 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
 137         // 8-bit tables:
 138         //
 139         //    CRC(uvwx, O) = CRC(u000, O) xor
 140         //                   CRC(0v00, O) xor
 141         //                   CRC(00w0, O) xor
 142         //                   CRC(000x, O)
 143         //
 144         // We can compute tables corresponding to the four terms for all 8-bit
 145         // values.
 146
 147         crc = ^crc
 148
 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)
 153                 if delta != 0 {
 154                         delta = 8 - delta
 155                         crc = castagnoliSSE42(crc, p[:delta])
 156                         p = p[delta:]
 157                 }
 158         }
 159
 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(
 164                         crc, 0, 0,
 165                         p, p[castagnoliK2:], p[castagnoliK2*2:],
 166                         castagnoliK2/24)
 167
 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:]
 173         }
 174
 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(
 179                         crc, 0, 0,
 180                         p, p[castagnoliK1:], p[castagnoliK1*2:],
 181                         castagnoliK1/24)
 182
 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:]
 188         }
 189
 190         // Use the simple implementation for what's left.
 191         crc = castagnoliSSE42(crc, p)
 192         return ^crc
 193 }
 194
 195 func archAvailableIEEE() bool {
 196         return cpu.X86.HasPCLMULQDQ && cpu.X86.HasSSE41
 197 }
 198
 199 var archIeeeTable8 *slicing8Table
 200
 201 func archInitIEEE() {
 202         if !cpu.X86.HasPCLMULQDQ || !cpu.X86.HasSSE41 {
 203                 panic("not available")
 204         }
 205         // We still use slicing-by-8 for small buffers.
 206         archIeeeTable8 = slicingMakeTable(IEEE)
 207 }
 208
 209 func archUpdateIEEE(crc uint32, p []byte) uint32 {
 210         if !cpu.X86.HasPCLMULQDQ || !cpu.X86.HasSSE41 {
 211                 panic("not available")
 212         }
 213
 214         if len(p) >= 64 {
 215                 left := len(p) & 15
 216                 do := len(p) - left
 217                 crc = ^ieeeCLMUL(^crc, p[:do])
 218                 p = p[do:]
 219         }
 220         if len(p) == 0 {
 221                 return crc
 222         }
 223         return slicingUpdate(crc, archIeeeTable8, p)
 224 }