adler32_simd_amd64.go

     1  // Copyright 2026 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  //go:build goexperiment.simd
     6  
     7  package adler32
     8  
     9  import "simd/archsimd"
    10  
    11  // haveSIMD reports whether the CPU supports the AVX2 instructions
    12  // used by updateSIMD.
    13  var haveSIMD = archsimd.X86.AVX2()
    14  
    15  const (
    16  	// minSIMD is the smallest input length for which updateSIMD
    17  	// outperforms updateGeneric.
    18  	minSIMD = 64
    19  
    20  	// blockSize is the number of bytes processed per iteration of
    21  	// the vector loop.
    22  	blockSize = 32
    23  
    24  	// nmaxSIMD is nmax rounded down to a multiple of blockSize. The
    25  	// vector loop processes at most this many bytes between modular
    26  	// reductions.
    27  	nmaxSIMD = nmax - nmax%blockSize
    28  )
    29  
    30  // taps[i] is the number of times the i'th byte of a block is counted
    31  // in the second sum: blockSize times for the first byte down to once
    32  // for the last. Cross-block contributions are accounted for by vps
    33  // in updateSIMD.
    34  var taps = [blockSize]int8{
    35  	32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17,
    36  	16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    37  }
    38  
    39  // updateSIMD computes the checksum using AVX2 vector instructions,
    40  // processing blockSize bytes per iteration. It accumulates, in
    41  // uint32 lanes:
    42  //
    43  //	vs1: the plain sum of all bytes, via VPSADBW against zero,
    44  //	vs2: the taps-weighted sum of the bytes of each block, via
    45  //	     VPMADDUBSW with the taps and VPMADDWD with 1,
    46  //	vps: the sum, over all blocks, of vs1 as it stood before that block,
    47  //
    48  // so that after an n-byte run starting from state (s1, s2),
    49  // s1' = s1 + sum(vs1) and
    50  // s2' = s2 + n*s1 + blockSize*sum(vps) + sum(vs2).
    51  //
    52  // The VPMADDUBSW pair sums are at most 255*(32+31) < 2^15-1, so they
    53  // cannot saturate. Modular reduction is deferred to the end of each
    54  // run. A run is at most nmaxSIMD <= nmax bytes, so by nmax's
    55  // defining property the total contribution to s2', and hence every
    56  // uint32 lane, stays below 2^32.
    57  func updateSIMD(d digest, p []byte) digest {
    58  	s1, s2 := uint32(d&0xffff), uint32(d>>16)
    59  
    60  	w := archsimd.LoadInt8x32Array(&taps)
    61  	ones := archsimd.BroadcastInt16x16(1)
    62  	var zero archsimd.Uint8x32
    63  
    64  	for len(p) >= blockSize {
    65  		n := nmaxSIMD
    66  		if n > len(p) {
    67  			n = len(p) - len(p)%blockSize
    68  		}
    69  		q := p[:n]
    70  		var vs1, vs2, vps archsimd.Uint32x8
    71  		for len(q) >= blockSize {
    72  			b := archsimd.LoadUint8x32(q)
    73  			vps = vps.Add(vs1)
    74  			vs1 = vs1.Add(b.SumOf8AbsDiff(zero).AsUint32x8())
    75  			vs2 = vs2.Add(b.DotProductPairsSaturated(w).DotProductPairs(ones).AsUint32x8())
    76  			q = q[blockSize:]
    77  		}
    78  		vs2 = vs2.Add(vps.ShiftAllLeft(5)) // 32 = blockSize bytes per block
    79  		r1 := vs1.GetLo().Add(vs1.GetHi())
    80  		r2 := vs2.GetLo().Add(vs2.GetHi())
    81  		s2 += uint32(n)*s1 + r2.GetElem(0) + r2.GetElem(1) + r2.GetElem(2) + r2.GetElem(3)
    82  		s1 += r1.GetElem(0) + r1.GetElem(1) + r1.GetElem(2) + r1.GetElem(3)
    83  		s1 %= mod
    84  		s2 %= mod
    85  		p = p[n:]
    86  	}
    87  	if len(p) > 0 {
    88  		return updateGeneric(digest(s2<<16|s1), p)
    89  	}
    90  	return digest(s2<<16 | s1)
    91  }
    92
View as plain text