adler32_simd_arm64.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  const (
    12  	haveSIMD = true
    13  
    14  	// minSIMD is the smallest input length for which updateSIMD
    15  	// outperforms updateGeneric.
    16  	minSIMD = 64
    17  
    18  	// blockSize is the number of bytes processed per iteration of
    19  	// the vector loop.
    20  	blockSize = 32
    21  
    22  	// nmaxSIMD is nmax rounded down to a multiple of blockSize. The
    23  	// vector loop processes at most this many bytes between modular
    24  	// reductions.
    25  	nmaxSIMD = nmax - nmax%blockSize
    26  )
    27  
    28  // taps[i] is the number of times the i'th byte of a block is counted
    29  // in the second sum: blockSize times for the first byte down to once
    30  // for the last. Cross-block contributions are accounted for by vps
    31  // in updateSIMD.
    32  var taps = [blockSize]uint16{
    33  	32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17,
    34  	16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    35  }
    36  
    37  // updateSIMD computes the checksum using NEON vector instructions,
    38  // processing blockSize bytes per iteration. It accumulates, in
    39  // uint32 lanes:
    40  //
    41  //	vs1: the plain sum of all bytes,
    42  //	vs2: the taps-weighted sum of the bytes of each block,
    43  //	vps: the sum, over all blocks, of vs1 as it stood before that block,
    44  //
    45  // so that after an n-byte run starting from state (s1, s2),
    46  // s1' = s1 + sum(vs1) and
    47  // s2' = s2 + n*s1 + blockSize*sum(vps) + sum(vs2).
    48  //
    49  // Modular reduction is deferred to the end of each run. A run is at
    50  // most nmaxSIMD <= nmax bytes, so by nmax's defining property the
    51  // total contribution to s2', and hence every uint32 lane, stays
    52  // below 2^32.
    53  func updateSIMD(d digest, p []byte) digest {
    54  	s1, s2 := uint32(d&0xffff), uint32(d>>16)
    55  
    56  	w0 := archsimd.LoadUint16x8(taps[0:])
    57  	w1 := archsimd.LoadUint16x8(taps[8:])
    58  	w2 := archsimd.LoadUint16x8(taps[16:])
    59  	w3 := archsimd.LoadUint16x8(taps[24:])
    60  
    61  	for len(p) >= blockSize {
    62  		n := nmaxSIMD
    63  		if n > len(p) {
    64  			n = len(p) - len(p)%blockSize
    65  		}
    66  		q := p[:n]
    67  		var vs1, vs2, vps archsimd.Uint32x4
    68  		for len(q) >= blockSize {
    69  			a := archsimd.LoadUint8x16(q)
    70  			b := archsimd.LoadUint8x16(q[16:])
    71  			vps = vps.Add(vs1)
    72  
    73  			// Widen the bytes to uint16 lanes.
    74  			alo := a.ExtendLo8ToUint16()
    75  			ahi := a.HiToLo().ExtendLo8ToUint16()
    76  			blo := b.ExtendLo8ToUint16()
    77  			bhi := b.HiToLo().ExtendLo8ToUint16()
    78  
    79  			// Byte sums for vs1: each lane of t sums 4 bytes
    80  			// (<= 1020) and of t2 8 bytes (<= 2040), so uint16
    81  			// cannot overflow. The low half of t2 covers all of t.
    82  			t := alo.Add(ahi).Add(blo.Add(bhi))
    83  			t2 := t.ConcatAddPairs(t)
    84  			vs1 = vs1.Add(t2.ExtendLo4ToUint32())
    85  
    86  			// Weighted sums for vs2: each product is at most 255*32
    87  			// = 8160, each lane of r sums 4 products (<= 32640) and
    88  			// of r2 8 (<= 65280), so uint16 cannot overflow. The
    89  			// low half of r2 covers all 32 products.
    90  			pa := alo.Mul(w0)
    91  			pb := ahi.Mul(w1)
    92  			pc := blo.Mul(w2)
    93  			pd := bhi.Mul(w3)
    94  			r := pa.ConcatAddPairs(pb).ConcatAddPairs(pc.ConcatAddPairs(pd))
    95  			r2 := r.ConcatAddPairs(r)
    96  			vs2 = vs2.Add(r2.ExtendLo4ToUint32())
    97  
    98  			q = q[blockSize:]
    99  		}
   100  		vs2 = vs2.Add(vps.ShiftAllLeft(5)) // 32 = blockSize bytes per block
   101  		s2 += uint32(n)*s1 + vs2.ReduceSum()
   102  		s1 += vs1.ReduceSum()
   103  		s1 %= mod
   104  		s2 %= mod
   105  		p = p[n:]
   106  	}
   107  	if len(p) > 0 {
   108  		return updateGeneric(digest(s2<<16|s1), p)
   109  	}
   110  	return digest(s2<<16 | s1)
   111  }
   112
View as plain text