bitmath.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  //specgen:category Bit math
     6  
     7  package spec
     8  
     9  import "math/bits"
    10  
    11  // OnesCount counts the number of one bits ("population count") in
    12  // each element.
    13  //
    14  //	z[i] = bits.OnesCount(x[i])
    15  func OnesCount[E Ints | Uints, W Width](x Vec[E, W]) (z Vec[E, W]) {
    16  	return map1[E, W, E, W](x, func(x E) E {
    17  		switch any(x).(type) {
    18  		case int8, uint8:
    19  			return E(bits.OnesCount8(uint8(x)))
    20  		case int16, uint16:
    21  			return E(bits.OnesCount16(uint16(x)))
    22  		case int32, uint32:
    23  			return E(bits.OnesCount32(uint32(x)))
    24  		case int64, uint64:
    25  			return E(bits.OnesCount64(uint64(x)))
    26  		}
    27  		panic("unreachable")
    28  	})
    29  }
    30  
    31  // TODO: Should LeadingZeros be defined on signed types?
    32  
    33  // LeadingZeros counts the leading zero bits of each element in x,
    34  // starting from the most significant bit.
    35  // If an element is 0, the result is {{.xN}}.
    36  //
    37  //	z[i] = bits.LeadingZeros(x[i])
    38  func LeadingZeros[E Ints | Uints, W Width](x Vec[E, W]) (z Vec[E, W]) {
    39  	return map1[E, W, E, W](x, func(x E) E {
    40  		switch any(x).(type) {
    41  		case int8, uint8:
    42  			return E(bits.LeadingZeros8(uint8(x)))
    43  		case int16, uint16:
    44  			return E(bits.LeadingZeros16(uint16(x)))
    45  		case int32, uint32:
    46  			return E(bits.LeadingZeros32(uint32(x)))
    47  		case int64, uint64:
    48  			return E(bits.LeadingZeros64(uint64(x)))
    49  		}
    50  		panic("unreachable")
    51  	})
    52  }
    53  
    54  // TODO: Right now, nothing supports TrailingZeros.
    55  
    56  // TrailingZeros counts the trailing zero bits of each element in x,
    57  // starting from the least significant bit.
    58  // If an element is 0, the result is {{.xN}}.
    59  //
    60  //	z[i] = bits.TrailingZeros(x[i])
    61  func TrailingZeros[E Uints, W Width](x Vec[E, W]) (z Vec[E, W]) {
    62  	return map1[E, W, E, W](x, func(x E) E {
    63  		switch x := any(x).(type) {
    64  		case uint8:
    65  			return E(bits.TrailingZeros8(x))
    66  		case uint16:
    67  			return E(bits.TrailingZeros16(x))
    68  		case uint32:
    69  			return E(bits.TrailingZeros32(x))
    70  		case uint64:
    71  			return E(bits.TrailingZeros64(x))
    72  		}
    73  		panic("unreachable")
    74  	})
    75  }
    76  
    77  // TODO: Calling this "Trailing zeros" for masks breaks the abstraction boundary
    78  // around the exact mask representation. E.g., what does it mean for a wide mask
    79  // or a byte mask?
    80  
    81  // TrailingZeros returns the number of low-order false (zero) elements in mask
    82  // x. If the mask is entirely false, it returns {{lanes .x "x"}}.
    83  //
    84  //specgen:name TrailingZeros
    85  func TrailingZerosMask[E MaskElt, W Width](x Vec[E, W]) int {
    86  	i := 0
    87  	for ; i < len(x); i++ {
    88  		if x[i] != 0 {
    89  			break
    90  		}
    91  	}
    92  	return i
    93  }
    94  
    95  // CarrylessMultiplyEven computes the elementwise carryless multiplication of
    96  // even-indexed elements of x and y. The result of each carryless multiply is
    97  // twice the width of the input elements. The high bits are stored in elements
    98  // z[2*i+1] and the low bits are stored in elements z[2*i].
    99  //
   100  //	concat(z[2*i+1], z[2*i]) = clmul(x[2*i], y[2*i])
   101  //
   102  // A carryless multiplication uses bitwise XOR instead of add-with-carry.
   103  // For example, to compute the carryless multiply of 0b1110 and 0b1011:
   104  //
   105  //	     1110
   106  //	   ⊗ 1011
   107  //	  ───────
   108  //	     1110
   109  //	    1110
   110  //	   0000
   111  //	⊕ 1110
   112  //	  ───────
   113  //	  1100010
   114  //
   115  // Carryless multiply can also be viewed as multiplying polynomials with
   116  // coefficients from GF(2). For example, the above example can be represented as
   117  //
   118  //	  (x^3 + x^2 + x^1) * (x^3 + x^1 + x^0)
   119  //	= (x^6 + x^5 + (1^1)x^4 + (1^1)x^3 + (1^1)x^2 + x^1)
   120  //	= (x^6 + x^5 + x^1)
   121  //
   122  //specgen:commutative
   123  func CarrylessMultiplyEven[E Uints, W Width](x, y Vec[E, W]) (z Vec[E, W]) {
   124  	return carrylessMultiplyPair(x, y, false, false)
   125  }
   126  
   127  // CarrylessMultiplyEvenOdd computes the elementwise carryless multiplication of
   128  // even-indexed elements of x and odd-indexed elements of y. The result of each
   129  // carryless multiply is twice the width of the input elements. The high bits
   130  // are stored in elements z[2*i+1] and the low bits are stored in elements
   131  // z[2*i].
   132  //
   133  //	concat(z[2*i+1], z[2*i]) = clmul(x[2*i], y[2*i+1])
   134  //
   135  // See [CarrylessMultiplyEven] for details about carryless multiply.
   136  //
   137  //specgen:commutative
   138  func CarrylessMultiplyEvenOdd[E Uints, W Width](x, y Vec[E, W]) (z Vec[E, W]) {
   139  	return carrylessMultiplyPair(x, y, false, true)
   140  }
   141  
   142  // CarrylessMultiplyOdd computes the elementwise carryless multiplication of
   143  // odd-indexed elements of x and y. The result of each carryless multiply is
   144  // twice the width of the input elements. The high bits are stored in elements
   145  // z[2*i+1] and the low bits are stored in elements z[2*i].
   146  //
   147  //	concat(z[2*i+1], z[2*i]) = clmul(x[2*i+1], y[2*i+1])
   148  //
   149  // See [CarrylessMultiplyEven] for details about carryless multiply.
   150  //
   151  //specgen:commutative
   152  func CarrylessMultiplyOdd[E Uints, W Width](x, y Vec[E, W]) (z Vec[E, W]) {
   153  	return carrylessMultiplyPair(x, y, true, true)
   154  }
   155  
   156  // CarrylessMultiplyOddEven computes the elementwise carryless multiplication of
   157  // odd-indexed elements of x and even-indexed elements of y. The result of each
   158  // carryless multiply is twice the width of the input elements. The high bits
   159  // are stored in elements z[2*i+1] and the low bits are stored in elements
   160  // z[2*i].
   161  //
   162  //	concat(z[2*i+1], z[2*i]) = clmul(x[2*i+1], y[2*i])
   163  //
   164  // See [CarrylessMultiplyEven] for details about carryless multiply.
   165  //
   166  //specgen:commutative
   167  func CarrylessMultiplyOddEven[E Uints, W Width](x, y Vec[E, W]) (z Vec[E, W]) {
   168  	return carrylessMultiplyPair(x, y, true, false)
   169  }
   170  
   171  func carrylessMultiplyPair[E Uints, W Width](x, y Vec[E, W], xOdd, yOdd bool) (z Vec[E, W]) {
   172  	z = makeVec[E, W]()
   173  	pairs := z.len() / 2
   174  	for i := 0; i < pairs; i++ {
   175  		xi := x[2*i]
   176  		if xOdd {
   177  			xi = x[2*i+1]
   178  		}
   179  		yi := y[2*i]
   180  		if yOdd {
   181  			yi = y[2*i+1]
   182  		}
   183  		z[2*i+1], z[2*i] = clmul(xi, yi)
   184  	}
   185  	return z
   186  }
   187
View as plain text