uint128.go raw
1 //go:build !amd64
2
3 package avx
4
5 import "math/bits"
6
7 // Pure Go fallback implementation for non-amd64 platforms
8
9 // Add adds two Uint128 values, returning the result and carry.
10 func (a Uint128) Add(b Uint128) (result Uint128, carry uint64) {
11 result.Lo, carry = bits.Add64(a.Lo, b.Lo, 0)
12 result.Hi, carry = bits.Add64(a.Hi, b.Hi, carry)
13 return
14 }
15
16 // AddCarry adds two Uint128 values with an input carry.
17 func (a Uint128) AddCarry(b Uint128, carryIn uint64) (result Uint128, carryOut uint64) {
18 result.Lo, carryOut = bits.Add64(a.Lo, b.Lo, carryIn)
19 result.Hi, carryOut = bits.Add64(a.Hi, b.Hi, carryOut)
20 return
21 }
22
23 // Sub subtracts b from a, returning the result and borrow.
24 func (a Uint128) Sub(b Uint128) (result Uint128, borrow uint64) {
25 result.Lo, borrow = bits.Sub64(a.Lo, b.Lo, 0)
26 result.Hi, borrow = bits.Sub64(a.Hi, b.Hi, borrow)
27 return
28 }
29
30 // SubBorrow subtracts b from a with an input borrow.
31 func (a Uint128) SubBorrow(b Uint128, borrowIn uint64) (result Uint128, borrowOut uint64) {
32 result.Lo, borrowOut = bits.Sub64(a.Lo, b.Lo, borrowIn)
33 result.Hi, borrowOut = bits.Sub64(a.Hi, b.Hi, borrowOut)
34 return
35 }
36
37 // Mul64 multiplies two 64-bit values and returns a 128-bit result.
38 func Mul64(a, b uint64) Uint128 {
39 hi, lo := bits.Mul64(a, b)
40 return Uint128{Lo: lo, Hi: hi}
41 }
42
43 // Mul multiplies two Uint128 values and returns a 256-bit result as [4]uint64.
44 // Result is [lo0, lo1, hi0, hi1] where value = lo0 + lo1<<64 + hi0<<128 + hi1<<192
45 func (a Uint128) Mul(b Uint128) [4]uint64 {
46 // (a.Hi*2^64 + a.Lo) * (b.Hi*2^64 + b.Lo)
47 // = a.Hi*b.Hi*2^128 + (a.Hi*b.Lo + a.Lo*b.Hi)*2^64 + a.Lo*b.Lo
48
49 // a.Lo * b.Lo -> r[0:1]
50 r0Hi, r0Lo := bits.Mul64(a.Lo, b.Lo)
51
52 // a.Lo * b.Hi -> r[1:2]
53 r1Hi, r1Lo := bits.Mul64(a.Lo, b.Hi)
54
55 // a.Hi * b.Lo -> r[1:2]
56 r2Hi, r2Lo := bits.Mul64(a.Hi, b.Lo)
57
58 // a.Hi * b.Hi -> r[2:3]
59 r3Hi, r3Lo := bits.Mul64(a.Hi, b.Hi)
60
61 var result [4]uint64
62 var carry uint64
63
64 result[0] = r0Lo
65
66 // result[1] = r0Hi + r1Lo + r2Lo
67 result[1], carry = bits.Add64(r0Hi, r1Lo, 0)
68 result[1], carry = bits.Add64(result[1], r2Lo, carry)
69
70 // result[2] = r1Hi + r2Hi + r3Lo + carry
71 result[2], carry = bits.Add64(r1Hi, r2Hi, carry)
72 result[2], carry = bits.Add64(result[2], r3Lo, carry)
73
74 // result[3] = r3Hi + carry
75 result[3] = r3Hi + carry
76
77 return result
78 }
79
80 // IsZero returns true if the Uint128 is zero.
81 func (a Uint128) IsZero() bool {
82 return a.Lo == 0 && a.Hi == 0
83 }
84
85 // Cmp compares two Uint128 values.
86 // Returns -1 if a < b, 0 if a == b, 1 if a > b.
87 func (a Uint128) Cmp(b Uint128) int {
88 if a.Hi < b.Hi {
89 return -1
90 }
91 if a.Hi > b.Hi {
92 return 1
93 }
94 if a.Lo < b.Lo {
95 return -1
96 }
97 if a.Lo > b.Lo {
98 return 1
99 }
100 return 0
101 }
102
103 // Lsh shifts a Uint128 left by n bits (n < 128).
104 func (a Uint128) Lsh(n uint) Uint128 {
105 if n >= 64 {
106 return Uint128{Lo: 0, Hi: a.Lo << (n - 64)}
107 }
108 if n == 0 {
109 return a
110 }
111 return Uint128{
112 Lo: a.Lo << n,
113 Hi: (a.Hi << n) | (a.Lo >> (64 - n)),
114 }
115 }
116
117 // Rsh shifts a Uint128 right by n bits (n < 128).
118 func (a Uint128) Rsh(n uint) Uint128 {
119 if n >= 64 {
120 return Uint128{Lo: a.Hi >> (n - 64), Hi: 0}
121 }
122 if n == 0 {
123 return a
124 }
125 return Uint128{
126 Lo: (a.Lo >> n) | (a.Hi << (64 - n)),
127 Hi: a.Hi >> n,
128 }
129 }
130
131 // Or returns the bitwise OR of two Uint128 values.
132 func (a Uint128) Or(b Uint128) Uint128 {
133 return Uint128{Lo: a.Lo | b.Lo, Hi: a.Hi | b.Hi}
134 }
135
136 // And returns the bitwise AND of two Uint128 values.
137 func (a Uint128) And(b Uint128) Uint128 {
138 return Uint128{Lo: a.Lo & b.Lo, Hi: a.Hi & b.Hi}
139 }
140
141 // Xor returns the bitwise XOR of two Uint128 values.
142 func (a Uint128) Xor(b Uint128) Uint128 {
143 return Uint128{Lo: a.Lo ^ b.Lo, Hi: a.Hi ^ b.Hi}
144 }
145
146 // Not returns the bitwise NOT of a Uint128.
147 func (a Uint128) Not() Uint128 {
148 return Uint128{Lo: ^a.Lo, Hi: ^a.Hi}
149 }
150