int256.gno
12.66 Kb ยท 626 lines
1package int256
2
3import (
4 "encoding/binary"
5 "math"
6 "math/bits"
7
8 u256 "gno.land/p/gnoswap/uint256"
9)
10
11type Int [4]uint64
12
13var (
14 MAX_UINT64 = ^uint64(0)
15 MIN_I256 = &Int{0, 0, 0, 0x8000000000000000}
16)
17
18func Zero() *Int {
19 return &Int{}
20}
21
22func One() *Int {
23 return &Int{1, 0, 0, 0}
24}
25
26func MinInt256() *Int {
27 return &Int{0, 0, 0, 0x8000000000000000}
28}
29
30func MaxInt256() *Int {
31 return &Int{0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0x7fffffffffffffff}
32}
33
34func NewInt(val int64) *Int {
35 z := &Int{}
36 z.SetInt64(val)
37 return z
38}
39
40func (z *Int) Set(x *Int) *Int {
41 z[0], z[1], z[2], z[3] = x[0], x[1], x[2], x[3]
42 return z
43}
44
45func (z *Int) SetInt64(x int64) *Int {
46 if x >= 0 {
47 z[3], z[2], z[1], z[0] = 0, 0, 0, uint64(x)
48 return z
49 }
50
51 z[3], z[2], z[1], z[0] = 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, uint64(x)
52 return z
53}
54
55func (z *Int) IsInt64() bool {
56 return ((z[1]|z[2]|z[3]) == 0 && z[0] <= 0x7fffffffffffffff) || // zero or positive int64
57 ((z[1]&z[2]&z[3]) == 0xffffffffffffffff && z[0] >= 0x8000000000000000) // negative int64
58}
59
60func (z *Int) Int64() int64 {
61 if !z.IsInt64() {
62 panic("int256: int64 overflow")
63 }
64 s := z.Sign()
65 if s == 0 {
66 return 0
67 }
68 if s > 0 {
69 // overflow when z[0] > math.MaxInt64
70 return int64(z[0])
71 }
72 // -(2^64 - z[0])
73 return -int64(math.MaxUint64 - z[0] + 1)
74}
75
76func (z *Int) SetUint64(x uint64) *Int {
77 z[3], z[2], z[1], z[0] = 0, 0, 0, x
78 return z
79}
80
81func (z *Int) IsUint64() bool {
82 return (z[1] | z[2] | z[3]) == 0
83}
84
85func (z *Int) Uint64() uint64 {
86 if !z.IsUint64() {
87 panic("int256: uint64 overflow")
88 }
89 return z[0]
90}
91
92func (z *Int) Abs() *u256.Uint {
93 if z.IsNeg() {
94 neg := new(Int).NegOverflow(z)
95 return &u256.Uint{neg[0], neg[1], neg[2], neg[3]}
96 }
97 return &u256.Uint{z[0], z[1], z[2], z[3]}
98}
99
100func (z *Int) Sign() int {
101 if z.IsZero() {
102 return 0
103 }
104 if z[3]&0x8000000000000000 == 0 {
105 return 1
106 }
107 return -1
108}
109
110func (z *Int) IsZero() bool {
111 return (z[0] | z[1] | z[2] | z[3]) == 0
112}
113
114func (z *Int) IsOne() bool {
115 return (z[0] == 1) && (z[1]|z[2]|z[3]) == 0
116}
117
118func (z *Int) IsNeg() bool {
119 return z[3]&0x8000000000000000 != 0
120}
121
122func (z *Int) IsPositive() bool {
123 return (z[3]&0x8000000000000000) == 0 && (z[3]|z[2]|z[1]|z[0]) != 0
124}
125
126func (z *Int) IsMinI256() bool {
127 return (z[3] == 0x8000000000000000) && ((z[2] | z[1] | z[0]) == 0)
128}
129
130func (z *Int) NegOverflow(x *Int) *Int {
131 if x[3] == 0x8000000000000000 && x[2] == 0 && x[1] == 0 && x[0] == 0 {
132 panic("int256: overflow")
133 }
134
135 return z.Neg(x)
136}
137
138func (z *Int) Neg(x *Int) *Int {
139 var carry uint64
140 z[0], z[1], z[2], z[3] = ^x[0], ^x[1], ^x[2], ^x[3]
141 z[0], carry = bits.Add64(z[0], 1, 0)
142 z[1], carry = bits.Add64(z[1], 0, carry)
143 z[2], carry = bits.Add64(z[2], 0, carry)
144 z[3] += carry
145 return z
146}
147
148func (z *Int) Eq(x *Int) bool {
149 return (z[0] == x[0]) && (z[1] == x[1]) && (z[2] == x[2]) && (z[3] == x[3])
150}
151
152func (z *Int) Neq(x *Int) bool {
153 return !z.Eq(x)
154}
155
156func (z *Int) Add(x, y *Int) *Int {
157 var carry uint64
158 z[0], carry = bits.Add64(x[0], y[0], 0)
159 z[1], carry = bits.Add64(x[1], y[1], carry)
160 z[2], carry = bits.Add64(x[2], y[2], carry)
161 z[3] = x[3] + y[3] + carry
162 return z
163}
164
165func (z *Int) AddOverflow(x, y *Int) (*Int, bool) {
166 var carry uint64
167 z[0], carry = bits.Add64(x[0], y[0], 0)
168 z[1], carry = bits.Add64(x[1], y[1], carry)
169 z[2], carry = bits.Add64(x[2], y[2], carry)
170 z[3] = x[3] + y[3] + carry
171 var overflow bool
172 signX, signY, signZ := x.Sign(), y.Sign(), z.Sign()
173 if (signX == signY) && (signX != signZ) {
174 overflow = true
175 }
176 return z, overflow
177}
178
179func (z *Int) Sub(x, y *Int) *Int {
180 var carry uint64
181 z[0], carry = bits.Sub64(x[0], y[0], 0)
182 z[1], carry = bits.Sub64(x[1], y[1], carry)
183 z[2], carry = bits.Sub64(x[2], y[2], carry)
184 z[3] = x[3] - y[3] - carry
185 return z
186}
187
188func (z *Int) SubOverflow(x, y *Int) (*Int, bool) {
189 var carry uint64
190 z[0], carry = bits.Sub64(x[0], y[0], 0)
191 z[1], carry = bits.Sub64(x[1], y[1], carry)
192 z[2], carry = bits.Sub64(x[2], y[2], carry)
193 z[3] = x[3] - y[3] - carry
194 var overflow bool
195 signX, signY, signZ := x.Sign(), y.Sign(), z.Sign()
196 if (signX == 0 && y.IsMinI256()) || ((signX != 0) && (signX != signY) && (signX != signZ)) {
197 overflow = true
198 }
199 return z, overflow
200}
201
202func (z *Int) Mul(x, y *Int) *Int {
203 var (
204 res Int
205 carry uint64
206 res1, res2, res3 uint64
207 )
208
209 carry, res[0] = bits.Mul64(x[0], y[0])
210 carry, res1 = umulHop(carry, x[1], y[0])
211 carry, res2 = umulHop(carry, x[2], y[0])
212 res3 = x[3]*y[0] + carry
213
214 carry, res[1] = umulHop(res1, x[0], y[1])
215 carry, res2 = umulStep(res2, x[1], y[1], carry)
216 res3 = res3 + x[2]*y[1] + carry
217
218 carry, res[2] = umulHop(res2, x[0], y[2])
219 res3 = res3 + x[1]*y[2] + carry
220
221 res[3] = res3 + x[0]*y[3]
222
223 return z.Set(&res)
224}
225
226func (z *Int) MulOverflow(x, y *Int) (*Int, bool) {
227 if (x.IsMinI256() && y.IsOne()) || (x.IsOne() && y.IsMinI256()) {
228 return z.Set(MIN_I256), false
229 }
230
231 var flipSign bool
232 xSign, ySign := x.Sign(), y.Sign()
233 if xSign*ySign == -1 {
234 flipSign = true
235 }
236
237 xCopy := x.Clone()
238 yCopy := y.Clone()
239
240 if xSign < 0 {
241 xCopy.Neg(xCopy)
242 }
243 if ySign < 0 {
244 yCopy.Neg(yCopy)
245 }
246
247 p := umul(xCopy, yCopy)
248 z[0], z[1], z[2], z[3] = p[0], p[1], p[2], p[3]
249
250 var overflow bool
251 if (p[4] | p[5] | p[6] | p[7]) != 0 {
252 overflow = true
253 } else if z.IsNeg() {
254 // The 256th bit is set, which means the absolute value is >= 2^255
255 // This is only valid if the result should be exactly -2^255
256 if !flipSign || !z.IsMinI256() {
257 overflow = true
258 }
259 }
260
261 if flipSign {
262 z.Neg(z)
263 }
264
265 return z, overflow
266}
267
268func umul(x, y *Int) [8]uint64 {
269 var (
270 res [8]uint64
271 carry, carry4, carry5, carry6 uint64
272 res1, res2, res3, res4, res5 uint64
273 )
274
275 carry, res[0] = bits.Mul64(x[0], y[0])
276 carry, res1 = umulHop(carry, x[1], y[0])
277 carry, res2 = umulHop(carry, x[2], y[0])
278 carry4, res3 = umulHop(carry, x[3], y[0])
279
280 carry, res[1] = umulHop(res1, x[0], y[1])
281 carry, res2 = umulStep(res2, x[1], y[1], carry)
282 carry, res3 = umulStep(res3, x[2], y[1], carry)
283 carry5, res4 = umulStep(carry4, x[3], y[1], carry)
284
285 carry, res[2] = umulHop(res2, x[0], y[2])
286 carry, res3 = umulStep(res3, x[1], y[2], carry)
287 carry, res4 = umulStep(res4, x[2], y[2], carry)
288 carry6, res5 = umulStep(carry5, x[3], y[2], carry)
289
290 carry, res[3] = umulHop(res3, x[0], y[3])
291 carry, res[4] = umulStep(res4, x[1], y[3], carry)
292 carry, res[5] = umulStep(res5, x[2], y[3], carry)
293 res[7], res[6] = umulStep(carry6, x[3], y[3], carry)
294
295 return res
296}
297
298func umulStep(z, x, y, carry uint64) (hi, lo uint64) {
299 hi, lo = bits.Mul64(x, y)
300 lo, carry = bits.Add64(lo, carry, 0)
301 hi += carry
302 lo, carry = bits.Add64(lo, z, 0)
303 hi += carry
304 return hi, lo
305}
306
307func umulHop(z, x, y uint64) (hi, lo uint64) {
308 hi, lo = bits.Mul64(x, y)
309 lo, carry := bits.Add64(lo, z, 0)
310 hi += carry
311 return hi, lo
312}
313
314func (z *Int) Clear() *Int {
315 z[0], z[1], z[2], z[3] = 0, 0, 0, 0
316 return z
317}
318
319func (z *Int) SetOne() *Int {
320 z[3], z[2], z[1], z[0] = 0, 0, 0, 1
321 return z
322}
323
324func (z *Int) SetAllBitsOne() *Int {
325 z[0], z[1], z[2], z[3] = 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff
326 return z
327}
328
329func (z *Int) Div(x, y *Int) *Int {
330 if x.Sign() > 0 {
331 if y.Sign() > 0 {
332 return z.uquo(x, y)
333 }
334 z.uquo(x, new(Int).Neg(y))
335 return z.Neg(z)
336 }
337 if y.Sign() < 0 {
338 return z.uquo(new(Int).Neg(x), new(Int).Neg(y))
339 }
340 z.uquo(new(Int).Neg(x), y)
341 return z.Neg(z)
342}
343
344func (z *Int) uquo(x, y *Int) *Int {
345 if y.IsZero() {
346 panic("zero division")
347 }
348 if x.IsZero() {
349 return z.Clear()
350 }
351 if x.Eq(y) {
352 return z.SetOne()
353 }
354 if x.IsInt64() && y.IsInt64() {
355 return z.SetInt64(x.Int64() / y.Int64())
356 }
357 quot := Int{}
358 udivrem(quot[:], x[:], y)
359 return z.Set(")
360}
361
362func (z *Int) Rem(x, y *Int) *Int {
363 if x.Sign() > 0 {
364 if y.Sign() > 0 {
365 return z.urem(x, y)
366 }
367 return z.urem(x, new(Int).Neg(y))
368 }
369 if y.Sign() < 0 {
370 z.urem(new(Int).Neg(x), new(Int).Neg(y))
371 return z.Neg(z)
372 }
373 z.urem(new(Int).Neg(x), y)
374 return z.Neg(z)
375}
376
377func (z *Int) urem(x, y *Int) *Int {
378 if y.IsZero() {
379 panic("zero division")
380 }
381 if x.IsZero() {
382 return z.Clear()
383 }
384 if x.Eq(y) {
385 return z.Clear()
386 }
387 if x.IsInt64() && y.IsInt64() {
388 xInt64 := x.Int64()
389 yInt64 := y.Int64()
390 return z.SetInt64(xInt64 % yInt64)
391 }
392 quot := Int{}
393 rem := udivrem(quot[:], x[:], y)
394 return z.Set(&rem)
395}
396
397func (z *Int) Lt(x *Int) bool {
398 return z.Cmp(x) < 0
399}
400
401func (z *Int) Lte(x *Int) bool {
402 return z.Cmp(x) <= 0
403}
404
405func (z *Int) Gt(x *Int) bool {
406 return z.Cmp(x) > 0
407}
408
409func (z *Int) Gte(x *Int) bool {
410 return z.Cmp(x) >= 0
411}
412
413func (z *Int) Cmp(x *Int) int {
414 zneg := int8(z[3] >> 63)
415 xneg := int8(x[3] >> 63)
416 if zneg != xneg {
417 return int(xneg - zneg)
418 }
419 d0, carry := bits.Sub64(z[0], x[0], 0)
420 d1, carry := bits.Sub64(z[1], x[1], carry)
421 d2, carry := bits.Sub64(z[2], x[2], carry)
422 d3, carry := bits.Sub64(z[3], x[3], carry)
423 if carry == 1 {
424 return -1
425 }
426 if d0|d1|d2|d3 == 0 {
427 return 0
428 }
429 return 1
430}
431
432func (z *Int) Clone() *Int {
433 return &Int{z[0], z[1], z[2], z[3]}
434}
435
436func (z *Int) Or(x, y *Int) *Int {
437 z[0] = x[0] | y[0]
438 z[1] = x[1] | y[1]
439 z[2] = x[2] | y[2]
440 z[3] = x[3] | y[3]
441 return z
442}
443
444func (z *Int) And(x, y *Int) *Int {
445 z[0] = x[0] & y[0]
446 z[1] = x[1] & y[1]
447 z[2] = x[2] & y[2]
448 z[3] = x[3] & y[3]
449 return z
450}
451
452func (z *Int) Xor(x, y *Int) *Int {
453 z[0] = x[0] ^ y[0]
454 z[1] = x[1] ^ y[1]
455 z[2] = x[2] ^ y[2]
456 z[3] = x[3] ^ y[3]
457 return z
458}
459
460func (z *Int) Not(x *Int) *Int {
461 z[0] = ^x[0]
462 z[1] = ^x[1]
463 z[2] = ^x[2]
464 z[3] = ^x[3]
465 return z
466}
467
468func (z *Int) Lsh(x *Int, n uint) *Int {
469 if n == 0 {
470 return z.Set(x)
471 }
472 if n >= 256 {
473 return z.Clear()
474 }
475 // Handle exact multiples of 64 separately to avoid 64-bit shift issues
476 if n&0x3f == 0 {
477 switch n {
478 case 64:
479 z[3], z[2], z[1], z[0] = x[2], x[1], x[0], 0
480 case 128:
481 z[3], z[2], z[1], z[0] = x[1], x[0], 0, 0
482 case 192:
483 z[3], z[2], z[1], z[0] = x[0], 0, 0, 0
484 }
485 return z
486 }
487 switch {
488 case n > 192:
489 n -= 192
490 z[3], z[2], z[1], z[0] = x[0]<<n, 0, 0, 0
491 case n > 128:
492 n -= 128
493 z[3] = (x[1] << n) | (x[0] >> (64 - n))
494 z[2] = x[0] << n
495 z[1], z[0] = 0, 0
496 case n > 64:
497 n -= 64
498 z[3] = (x[2] << n) | (x[1] >> (64 - n))
499 z[2] = (x[1] << n) | (x[0] >> (64 - n))
500 z[1] = x[0] << n
501 z[0] = 0
502 default:
503 z[3] = (x[3] << n) | (x[2] >> (64 - n))
504 z[2] = (x[2] << n) | (x[1] >> (64 - n))
505 z[1] = (x[1] << n) | (x[0] >> (64 - n))
506 z[0] = x[0] << n
507 }
508 return z
509}
510
511func (z *Int) Rsh(x *Int, n uint) *Int {
512 if n == 0 {
513 return z.Set(x)
514 }
515 if x.IsNeg() {
516 return z.negRsh(x, n)
517 }
518 return z.rsh(x, n)
519}
520
521func (z *Int) rsh(x *Int, n uint) *Int {
522 if n >= 256 {
523 return z.Clear()
524 }
525 // Handle exact multiples of 64 separately to avoid 64-bit shift issues
526 if n&0x3f == 0 {
527 switch n {
528 case 0:
529 return z.Set(x)
530 case 64:
531 z[3], z[2], z[1], z[0] = 0, x[3], x[2], x[1]
532 case 128:
533 z[3], z[2], z[1], z[0] = 0, 0, x[3], x[2]
534 case 192:
535 z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]
536 }
537 return z
538 }
539 switch {
540 case n > 192:
541 n -= 192
542 z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]>>n
543 case n > 128:
544 n -= 128
545 z[3], z[2] = 0, 0
546 z[1] = x[3] >> n
547 z[0] = (x[3] << (64 - n)) | (x[2] >> n)
548 case n > 64:
549 n -= 64
550 z[3] = 0
551 z[2] = x[3] >> n
552 z[1] = (x[3] << (64 - n)) | (x[2] >> n)
553 z[0] = (x[2] << (64 - n)) | (x[1] >> n)
554 default:
555 z[3] = x[3] >> n
556 z[2] = (x[3] << (64 - n)) | (x[2] >> n)
557 z[1] = (x[2] << (64 - n)) | (x[1] >> n)
558 z[0] = (x[1] << (64 - n)) | (x[0] >> n)
559 }
560 return z
561}
562
563func (z *Int) negRsh(x *Int, n uint) *Int {
564 if n >= 256 {
565 return z.SetAllBitsOne()
566 }
567 var v uint64 = 0xffffffffffffffff
568 // Handle exact multiples of 64 separately to avoid 64-bit shift issues
569 if n&0x3f == 0 {
570 switch n {
571 case 0:
572 return z.Set(x)
573 case 64:
574 z[3], z[2], z[1], z[0] = v, x[3], x[2], x[1]
575 case 128:
576 z[3], z[2], z[1], z[0] = v, v, x[3], x[2]
577 case 192:
578 z[3], z[2], z[1], z[0] = v, v, v, x[3]
579 }
580 return z
581 }
582 switch {
583 case n > 192:
584 n -= 192
585 z[3], z[2], z[1], z[0] = v, v, v, (v<<(64-n))|(x[3]>>n)
586 case n > 128:
587 n -= 128
588 z[3], z[2] = v, v
589 z[1] = (v << (64 - n)) | (x[3] >> n)
590 z[0] = (x[3] << (64 - n)) | (x[2] >> n)
591 case n > 64:
592 n -= 64
593 z[3] = v
594 z[2] = (v << (64 - n)) | (x[3] >> n)
595 z[1] = (x[3] << (64 - n)) | (x[2] >> n)
596 z[0] = (x[2] << (64 - n)) | (x[1] >> n)
597 default:
598 z[3] = (v << (64 - n)) | (x[3] >> n)
599 z[2] = (x[3] << (64 - n)) | (x[2] >> n)
600 z[1] = (x[2] << (64 - n)) | (x[1] >> n)
601 z[0] = (x[1] << (64 - n)) | (x[0] >> n)
602 }
603 return z
604}
605
606func (z *Int) BitLen() int {
607 switch {
608 case z[3] != 0:
609 return 192 + bits.Len64(z[3])
610 case z[2] != 0:
611 return 128 + bits.Len64(z[2])
612 case z[1] != 0:
613 return 64 + bits.Len64(z[1])
614 default:
615 return bits.Len64(z[0])
616 }
617}
618
619func (z *Int) SetBytes32(in []byte) *Int {
620 _ = in[31] // bounds check hint to compiler; see golang.org/issue/14808
621 z[3] = binary.BigEndian.Uint64(in[0:8])
622 z[2] = binary.BigEndian.Uint64(in[8:16])
623 z[1] = binary.BigEndian.Uint64(in[16:24])
624 z[0] = binary.BigEndian.Uint64(in[24:32])
625 return z
626}
