bitwise.gno
6.47 Kb · 332 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
6// Or sets z to the bitwise OR of x and y and returns z.
7//
8// Parameters:
9// - x: First 256-bit operand.
10// - y: Second 256-bit operand.
11//
12// Returns:
13// - z: The 256-bit bitwise OR x | y, stored in the receiver.
14func (z *Uint) Or(x, y *Uint) *Uint {
15 z[0] = x[0] | y[0]
16 z[1] = x[1] | y[1]
17 z[2] = x[2] | y[2]
18 z[3] = x[3] | y[3]
19 return z
20}
21
22// And sets z to the bitwise AND of x and y and returns z.
23//
24// Parameters:
25// - x: First 256-bit operand.
26// - y: Second 256-bit operand.
27//
28// Returns:
29// - z: The 256-bit bitwise AND x & y, stored in the receiver.
30func (z *Uint) And(x, y *Uint) *Uint {
31 z[0] = x[0] & y[0]
32 z[1] = x[1] & y[1]
33 z[2] = x[2] & y[2]
34 z[3] = x[3] & y[3]
35 return z
36}
37
38// Not sets z to the bitwise complement of x and returns z.
39//
40// Parameters:
41// - x: 256-bit operand whose bits are complemented.
42//
43// Returns:
44// - z: The 256-bit bitwise complement ^x, stored in the receiver.
45func (z *Uint) Not(x *Uint) *Uint {
46 z[3], z[2], z[1], z[0] = ^x[3], ^x[2], ^x[1], ^x[0]
47 return z
48}
49
50// AndNot sets z to x AND NOT y and returns z.
51//
52// Parameters:
53// - x: First 256-bit operand.
54// - y: Operand whose bits are cleared from x.
55//
56// Returns:
57// - z: The 256-bit bit pattern x &^ y, stored in the receiver.
58func (z *Uint) AndNot(x, y *Uint) *Uint {
59 z[0] = x[0] &^ y[0]
60 z[1] = x[1] &^ y[1]
61 z[2] = x[2] &^ y[2]
62 z[3] = x[3] &^ y[3]
63 return z
64}
65
66// Xor sets z to the bitwise exclusive OR of x and y and returns z.
67//
68// Parameters:
69// - x: First 256-bit operand.
70// - y: Second 256-bit operand.
71//
72// Returns:
73// - z: The 256-bit bitwise exclusive OR x ^ y, stored in the receiver.
74func (z *Uint) Xor(x, y *Uint) *Uint {
75 z[0] = x[0] ^ y[0]
76 z[1] = x[1] ^ y[1]
77 z[2] = x[2] ^ y[2]
78 z[3] = x[3] ^ y[3]
79 return z
80}
81
82// Lsh sets z to x left-shifted by n bits and returns z.
83// Bits shifted beyond the 256-bit width are discarded; n >= 256 produces zero.
84//
85// Parameters:
86// - x: 256-bit operand to shift.
87// - n: Number of bit positions to shift left.
88//
89// Returns:
90// - z: The low 256 bits of x << n, stored in the receiver.
91func (z *Uint) Lsh(x *Uint, n uint) *Uint {
92 if x.IsZero() {
93 return z.Clear()
94 }
95
96 if n == 0 {
97 return z.Set(x)
98 }
99
100 return z.lsh(x, n)
101}
102
103// lsh performs left shift without overflow checking
104func (z *Uint) lsh(x *Uint, n uint) *Uint {
105 // n % 64 == 0
106 if n&0x3f == 0 {
107 switch n {
108 case 0:
109 return z.Set(x)
110 case 64:
111 return z.lsh64(x)
112 case 128:
113 return z.lsh128(x)
114 case 192:
115 return z.lsh192(x)
116 default:
117 return z.Clear()
118 }
119 }
120 var a, b uint64
121 // Big swaps first
122 switch {
123 case n > 192:
124 z.lsh192(x)
125 n -= 192
126 goto sh192
127 case n > 128:
128 z.lsh128(x)
129 n -= 128
130 goto sh128
131 case n > 64:
132 z.lsh64(x)
133 n -= 64
134 goto sh64
135 default:
136 z.Set(x)
137 }
138
139 // remaining shifts
140 a = z[0] >> (64 - n)
141 z[0] = z[0] << n
142
143sh64:
144 b = z[1] >> (64 - n)
145 z[1] = (z[1] << n) | a
146
147sh128:
148 a = z[2] >> (64 - n)
149 z[2] = (z[2] << n) | b
150
151sh192:
152 z[3] = (z[3] << n) | a
153
154 return z
155}
156
157// Rsh sets z to x logically right-shifted by n bits and returns z.
158// Zero bits are shifted in from the left, and n >= 256 produces zero.
159//
160// Parameters:
161// - x: 256-bit operand to shift.
162// - n: Number of bit positions to shift right.
163//
164// Returns:
165// - z: The 256-bit logical right shift x >> n, stored in the receiver.
166func (z *Uint) Rsh(x *Uint, n uint) *Uint {
167 // n % 64 == 0
168 if n&0x3f == 0 {
169 switch n {
170 case 0:
171 return z.Set(x)
172 case 64:
173 return z.rsh64(x)
174 case 128:
175 return z.rsh128(x)
176 case 192:
177 return z.rsh192(x)
178 default:
179 return z.Clear()
180 }
181 }
182 var a, b uint64
183 // Big swaps first
184 switch {
185 case n > 192:
186 if n > 256 {
187 return z.Clear()
188 }
189 z.rsh192(x)
190 n -= 192
191 goto sh192
192 case n > 128:
193 z.rsh128(x)
194 n -= 128
195 goto sh128
196 case n > 64:
197 z.rsh64(x)
198 n -= 64
199 goto sh64
200 default:
201 z.Set(x)
202 }
203
204 // remaining shifts
205 a = z[3] << (64 - n)
206 z[3] = z[3] >> n
207
208sh64:
209 b = z[2] << (64 - n)
210 z[2] = (z[2] >> n) | a
211
212sh128:
213 a = z[1] << (64 - n)
214 z[1] = (z[1] >> n) | b
215
216sh192:
217 z[0] = (z[0] >> n) | a
218
219 return z
220}
221
222// SRsh sets z to x arithmetically right-shifted by n bits and returns z.
223// The top bit is treated as a sign bit: negative patterns receive one-fill,
224// while non-negative patterns use the logical right shift.
225//
226// Parameters:
227// - x: 256-bit two's-complement bit pattern to shift.
228// - n: Number of bit positions to shift right.
229//
230// Returns:
231// - z: The arithmetic right shift of x, stored in the receiver; n >= 256
232// yields all ones for a negative x and zero otherwise.
233func (z *Uint) SRsh(x *Uint, n uint) *Uint {
234 // If the MSB is 0, SRsh is same as Rsh.
235 if !x.isBitSet(255) {
236 return z.Rsh(x, n)
237 }
238 if n%64 == 0 {
239 switch n {
240 case 0:
241 return z.Set(x)
242 case 64:
243 return z.srsh64(x)
244 case 128:
245 return z.srsh128(x)
246 case 192:
247 return z.srsh192(x)
248 default:
249 return z.SetAllOne()
250 }
251 }
252 var a uint64 = 18446744073709551615 << (64 - n%64)
253 // Big swaps first
254 switch {
255 case n > 192:
256 if n > 256 {
257 return z.SetAllOne()
258 }
259 z.srsh192(x)
260 n -= 192
261 goto sh192
262 case n > 128:
263 z.srsh128(x)
264 n -= 128
265 goto sh128
266 case n > 64:
267 z.srsh64(x)
268 n -= 64
269 goto sh64
270 default:
271 z.Set(x)
272 }
273
274 // remaining shifts
275 z[3], a = (z[3]>>n)|a, z[3]<<(64-n)
276
277sh64:
278 z[2], a = (z[2]>>n)|a, z[2]<<(64-n)
279
280sh128:
281 z[1], a = (z[1]>>n)|a, z[1]<<(64-n)
282
283sh192:
284 z[0] = (z[0] >> n) | a
285
286 return z
287}
288
289func (z *Uint) lsh64(x *Uint) *Uint {
290 z[3], z[2], z[1], z[0] = x[2], x[1], x[0], 0
291 return z
292}
293
294func (z *Uint) lsh128(x *Uint) *Uint {
295 z[3], z[2], z[1], z[0] = x[1], x[0], 0, 0
296 return z
297}
298
299func (z *Uint) lsh192(x *Uint) *Uint {
300 z[3], z[2], z[1], z[0] = x[0], 0, 0, 0
301 return z
302}
303
304func (z *Uint) rsh64(x *Uint) *Uint {
305 z[3], z[2], z[1], z[0] = 0, x[3], x[2], x[1]
306 return z
307}
308
309func (z *Uint) rsh128(x *Uint) *Uint {
310 z[3], z[2], z[1], z[0] = 0, 0, x[3], x[2]
311 return z
312}
313
314func (z *Uint) rsh192(x *Uint) *Uint {
315 z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]
316 return z
317}
318
319func (z *Uint) srsh64(x *Uint) *Uint {
320 z[3], z[2], z[1], z[0] = 18446744073709551615, x[3], x[2], x[1]
321 return z
322}
323
324func (z *Uint) srsh128(x *Uint) *Uint {
325 z[3], z[2], z[1], z[0] = 18446744073709551615, 18446744073709551615, x[3], x[2]
326 return z
327}
328
329func (z *Uint) srsh192(x *Uint) *Uint {
330 z[3], z[2], z[1], z[0] = 18446744073709551615, 18446744073709551615, 18446744073709551615, x[3]
331 return z
332}
