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