bitwise.gno
5.30 Kb ยท 302 lines
1// bitwise contains bitwise operations for Uint instances.
2// This file includes functions to perform bitwise AND, OR, XOR, and NOT operations, as well as bit shifting.
3// These operations are crucial for manipulating individual bits within a 256-bit unsigned integer.
4package uint256
5
6import (
7 "math/bits"
8)
9
10// Or sets z to the bitwise OR of x and y and returns z.
11func (z *Uint) Or(x, y *Uint) *Uint {
12 z[0] = x[0] | y[0]
13 z[1] = x[1] | y[1]
14 z[2] = x[2] | y[2]
15 z[3] = x[3] | y[3]
16 return z
17}
18
19// And sets z to the bitwise AND of x and y and returns z.
20func (z *Uint) And(x, y *Uint) *Uint {
21 z[0] = x[0] & y[0]
22 z[1] = x[1] & y[1]
23 z[2] = x[2] & y[2]
24 z[3] = x[3] & y[3]
25 return z
26}
27
28// Not sets z to the bitwise NOT of x and returns z.
29func (z *Uint) Not(x *Uint) *Uint {
30 z[3], z[2], z[1], z[0] = ^x[3], ^x[2], ^x[1], ^x[0]
31 return z
32}
33
34// AndNot sets z to x AND NOT y and returns z.
35func (z *Uint) AndNot(x, y *Uint) *Uint {
36 z[0] = x[0] &^ y[0]
37 z[1] = x[1] &^ y[1]
38 z[2] = x[2] &^ y[2]
39 z[3] = x[3] &^ y[3]
40 return z
41}
42
43// Xor sets z to the bitwise XOR of x and y and returns z.
44func (z *Uint) Xor(x, y *Uint) *Uint {
45 z[0] = x[0] ^ y[0]
46 z[1] = x[1] ^ y[1]
47 z[2] = x[2] ^ y[2]
48 z[3] = x[3] ^ y[3]
49 return z
50}
51
52// Lsh sets z to x left-shifted by n bits and returns z.
53// Panics if the shift would cause non-zero bits to overflow.
54func (z *Uint) Lsh(x *Uint, n uint) *Uint {
55 if x.IsZero() {
56 return z.Clear()
57 }
58
59 if n == 0 {
60 return z.Set(x)
61 }
62
63 // overflow check
64 if n >= 256 {
65 panic("Lsh: overflow")
66 }
67
68 // headroom check
69 top := -1
70 for i := 3; i >= 0; i-- {
71 if x[i] != 0 {
72 top = i
73 break
74 }
75 }
76
77 usedBits := bits.Len64(x[top]) // 1..64
78 msbIndex := top*64 + (usedBits - 1) // 0..255
79 headroom := 255 - msbIndex // 0..255
80 if n > uint(headroom) {
81 panic("Lsh: overflow")
82 }
83
84 // Perform the shift
85 return z.lsh(x, n)
86}
87
88// lsh performs left shift without overflow checking
89func (z *Uint) lsh(x *Uint, n uint) *Uint {
90 // n % 64 == 0
91 if n&0x3f == 0 {
92 switch n {
93 case 0:
94 return z.Set(x)
95 case 64:
96 return z.lsh64(x)
97 case 128:
98 return z.lsh128(x)
99 case 192:
100 return z.lsh192(x)
101 default:
102 return z.Clear()
103 }
104 }
105 var a, b uint64
106 // Big swaps first
107 switch {
108 case n > 192:
109 z.lsh192(x)
110 n -= 192
111 goto sh192
112 case n > 128:
113 z.lsh128(x)
114 n -= 128
115 goto sh128
116 case n > 64:
117 z.lsh64(x)
118 n -= 64
119 goto sh64
120 default:
121 z.Set(x)
122 }
123
124 // remaining shifts
125 a = z[0] >> (64 - n)
126 z[0] = z[0] << n
127
128sh64:
129 b = z[1] >> (64 - n)
130 z[1] = (z[1] << n) | a
131
132sh128:
133 a = z[2] >> (64 - n)
134 z[2] = (z[2] << n) | b
135
136sh192:
137 z[3] = (z[3] << n) | a
138
139 return z
140}
141
142// Rsh sets z to x right-shifted by n bits and returns z.
143// If n >= 256, z is set to 0.
144func (z *Uint) Rsh(x *Uint, n uint) *Uint {
145 // n % 64 == 0
146 if n&0x3f == 0 {
147 switch n {
148 case 0:
149 return z.Set(x)
150 case 64:
151 return z.rsh64(x)
152 case 128:
153 return z.rsh128(x)
154 case 192:
155 return z.rsh192(x)
156 default:
157 return z.Clear()
158 }
159 }
160 var a, b uint64
161 // Big swaps first
162 switch {
163 case n > 192:
164 if n > 256 {
165 return z.Clear()
166 }
167 z.rsh192(x)
168 n -= 192
169 goto sh192
170 case n > 128:
171 z.rsh128(x)
172 n -= 128
173 goto sh128
174 case n > 64:
175 z.rsh64(x)
176 n -= 64
177 goto sh64
178 default:
179 z.Set(x)
180 }
181
182 // remaining shifts
183 a = z[3] << (64 - n)
184 z[3] = z[3] >> n
185
186sh64:
187 b = z[2] << (64 - n)
188 z[2] = (z[2] >> n) | a
189
190sh128:
191 a = z[1] << (64 - n)
192 z[1] = (z[1] >> n) | b
193
194sh192:
195 z[0] = (z[0] >> n) | a
196
197 return z
198}
199
200// SRsh sets z to x arithmetically right-shifted by n bits and returns z.
201// It treats x as a signed two's complement integer. For negative values,
202// high-order bits are filled with 1s instead of 0s. If n >= 256 and x is negative, z is set to all 1s.
203func (z *Uint) SRsh(x *Uint, n uint) *Uint {
204 // If the MSB is 0, SRsh is same as Rsh.
205 if !x.isBitSet(255) {
206 return z.Rsh(x, n)
207 }
208 if n%64 == 0 {
209 switch n {
210 case 0:
211 return z.Set(x)
212 case 64:
213 return z.srsh64(x)
214 case 128:
215 return z.srsh128(x)
216 case 192:
217 return z.srsh192(x)
218 default:
219 return z.SetAllOne()
220 }
221 }
222 var a uint64 = MAX_UINT64 << (64 - n%64)
223 // Big swaps first
224 switch {
225 case n > 192:
226 if n > 256 {
227 return z.SetAllOne()
228 }
229 z.srsh192(x)
230 n -= 192
231 goto sh192
232 case n > 128:
233 z.srsh128(x)
234 n -= 128
235 goto sh128
236 case n > 64:
237 z.srsh64(x)
238 n -= 64
239 goto sh64
240 default:
241 z.Set(x)
242 }
243
244 // remaining shifts
245 z[3], a = (z[3]>>n)|a, z[3]<<(64-n)
246
247sh64:
248 z[2], a = (z[2]>>n)|a, z[2]<<(64-n)
249
250sh128:
251 z[1], a = (z[1]>>n)|a, z[1]<<(64-n)
252
253sh192:
254 z[0] = (z[0] >> n) | a
255
256 return z
257}
258
259func (z *Uint) lsh64(x *Uint) *Uint {
260 z[3], z[2], z[1], z[0] = x[2], x[1], x[0], 0
261 return z
262}
263
264func (z *Uint) lsh128(x *Uint) *Uint {
265 z[3], z[2], z[1], z[0] = x[1], x[0], 0, 0
266 return z
267}
268
269func (z *Uint) lsh192(x *Uint) *Uint {
270 z[3], z[2], z[1], z[0] = x[0], 0, 0, 0
271 return z
272}
273
274func (z *Uint) rsh64(x *Uint) *Uint {
275 z[3], z[2], z[1], z[0] = 0, x[3], x[2], x[1]
276 return z
277}
278
279func (z *Uint) rsh128(x *Uint) *Uint {
280 z[3], z[2], z[1], z[0] = 0, 0, x[3], x[2]
281 return z
282}
283
284func (z *Uint) rsh192(x *Uint) *Uint {
285 z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]
286 return z
287}
288
289func (z *Uint) srsh64(x *Uint) *Uint {
290 z[3], z[2], z[1], z[0] = MAX_UINT64, x[3], x[2], x[1]
291 return z
292}
293
294func (z *Uint) srsh128(x *Uint) *Uint {
295 z[3], z[2], z[1], z[0] = MAX_UINT64, MAX_UINT64, x[3], x[2]
296 return z
297}
298
299func (z *Uint) srsh192(x *Uint) *Uint {
300 z[3], z[2], z[1], z[0] = MAX_UINT64, MAX_UINT64, MAX_UINT64, x[3]
301 return z
302}
