39 lines
844 B
Go
39 lines
844 B
Go
|
// uint256: Fixed size 256-bit math library
|
||
|
|
// Copyright 2020 uint256 Authors
|
||
|
|
// SPDX-License-Identifier: BSD-3-Clause
|
||
|
|
|
||
|
|
package uint256
|
||
|
|
|
||
|
|
import "math/bits"
|
||
|
|
|
||
|
|
// reciprocal2by1 computes <^d, ^0> / d.
|
||
|
|
func reciprocal2by1(d uint64) uint64 {
|
||
|
|
reciprocal, _ := bits.Div64(^d, ^uint64(0), d)
|
||
|
|
return reciprocal
|
||
|
|
}
|
||
|
|
|
||
|
|
// udivrem2by1 divides <uh, ul> / d and produces both quotient and remainder.
|
||
|
|
// It uses the provided d's reciprocal.
|
||
|
|
// Implementation ported from https://github.com/chfast/intx and is based on
|
||
|
|
// "Improved division by invariant integers", Algorithm 4.
|
||
|
|
func udivrem2by1(uh, ul, d, reciprocal uint64) (quot, rem uint64) {
|
||
|
|
qh, ql := bits.Mul64(reciprocal, uh)
|
||
|
|
ql, carry := bits.Add64(ql, ul, 0)
|
||
|
|
qh, _ = bits.Add64(qh, uh, carry)
|
||
|
|
qh++
|
||
|
|
|
||
|
|
r := ul - qh*d
|
||
|
|
|
||
|
|
if r > ql {
|
||
|
|
qh--
|
||
|
|
r += d
|
||
|
|
}
|
||
|
|
|
||
|
|
if r >= d {
|
||
|
|
qh++
|
||
|
|
r -= d
|
||
|
|
}
|
||
|
|
|
||
|
|
return qh, r
|
||
|
|
}
|