nat_wasm.go

     1  // Copyright 2024 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  package bigmod
     6  
     7  // The generic implementation relies on 64x64->128 bit multiplication and
     8  // 64-bit add-with-carry, which are compiler intrinsics on many architectures.
     9  // Wasm doesn't support those. Here we implement it with 32x32->64 bit
    10  // operations, which is more efficient on Wasm.
    11  
    12  // addMulVVW multiplies the multi-word value x by the single-word value y,
    13  // adding the result to the multi-word value z and returning the final carry.
    14  // It can be thought of as one row of a pen-and-paper column multiplication.
    15  func addMulVVW(z, x []uint, y uint) (carry uint) {
    16  	const mask32 = 1<<32 - 1
    17  	y0 := y & mask32
    18  	y1 := y >> 32
    19  	_ = x[len(z)-1] // bounds check elimination hint
    20  	for i, zi := range z {
    21  		xi := x[i]
    22  		x0 := xi & mask32
    23  		x1 := xi >> 32
    24  		z0 := zi & mask32
    25  		z1 := zi >> 32
    26  		c0 := carry & mask32
    27  		c1 := carry >> 32
    28  
    29  		w00 := x0*y0 + z0 + c0
    30  		l00 := w00 & mask32
    31  		h00 := w00 >> 32
    32  
    33  		w01 := x0*y1 + z1 + h00
    34  		l01 := w01 & mask32
    35  		h01 := w01 >> 32
    36  
    37  		w10 := x1*y0 + c1 + l01
    38  		h10 := w10 >> 32
    39  
    40  		carry = x1*y1 + h10 + h01
    41  		z[i] = w10<<32 + l00
    42  	}
    43  	return carry
    44  }
    45
View as plain text