int256.gno
22.03 Kb · 932 lines
1package int256
2
3import (
4 "encoding/binary"
5 "math"
6 "math/bits"
7
8 u256 "gno.land/p/gnoswap/uint256/v1"
9)
10
11type Int [4]uint64
12
13// Zero returns a fresh Int whose 256 bits are all zero.
14//
15// Returns:
16// - zero: A mutable *Int representing the signed value 0.
17func Zero() *Int {
18 return &Int{}
19}
20
21// One returns a fresh Int representing the signed value 1.
22//
23// Returns:
24// - one: A mutable *Int with only its least-significant bit set.
25func One() *Int {
26 return &Int{1, 0, 0, 0}
27}
28
29// MinInt256 returns the minimum signed 256-bit integer, -2^255.
30//
31// Returns:
32// - minimum: A fresh *Int containing the two's-complement minimum value.
33func MinInt256() *Int {
34 return &Int{0, 0, 0, 0x8000000000000000}
35}
36
37// MaxInt256 returns the maximum signed 256-bit integer, 2^255 - 1.
38//
39// Returns:
40// - maximum: A fresh *Int containing the largest positive int256 value.
41func MaxInt256() *Int {
42 return &Int{0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0x7fffffffffffffff}
43}
44
45// NewInt constructs a signed 256-bit integer from an int64.
46//
47// Parameters:
48// - val: Signed 64-bit value to sign-extend into 256 bits.
49//
50// Returns:
51// - value: A fresh *Int representing val.
52func NewInt(val int64) *Int {
53 z := &Int{}
54 z.SetInt64(val)
55 return z
56}
57
58// Set copies the complete 256-bit value from x into z.
59//
60// Parameters:
61// - x: Source Int whose four limbs are copied.
62//
63// Returns:
64// - z: The receiver after copying x.
65func (z *Int) Set(x *Int) *Int {
66 z[0], z[1], z[2], z[3] = x[0], x[1], x[2], x[3]
67 return z
68}
69
70// SetInt64 assigns x to z with two's-complement sign extension.
71//
72// Parameters:
73// - x: Signed 64-bit value to store.
74//
75// Returns:
76// - z: The receiver representing x as an Int.
77func (z *Int) SetInt64(x int64) *Int {
78 if x >= 0 {
79 z[3], z[2], z[1], z[0] = 0, 0, 0, uint64(x)
80 return z
81 }
82
83 z[3], z[2], z[1], z[0] = 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, uint64(x)
84 return z
85}
86
87// IsInt64 reports whether z can be represented exactly as a signed int64.
88//
89// Returns:
90// - fits: True when z is in [math.MinInt64, math.MaxInt64], false otherwise.
91func (z *Int) IsInt64() bool {
92 return ((z[1]|z[2]|z[3]) == 0 && z[0] <= 0x7fffffffffffffff) || // zero or positive int64
93 ((z[1]&z[2]&z[3]) == 0xffffffffffffffff && z[0] >= 0x8000000000000000) // negative int64
94}
95
96// Int64 converts z to int64 after checking its signed range.
97//
98// Returns:
99// - value: z's exact signed 64-bit value.
100//
101// Panics if z is outside the signed int64 range.
102func (z *Int) Int64() int64 {
103 if !z.IsInt64() {
104 panic("int256: int64 overflow")
105 }
106 s := z.Sign()
107 if s == 0 {
108 return 0
109 }
110 if s > 0 {
111 // overflow when z[0] > math.MaxInt64
112 return int64(z[0])
113 }
114 // -(2^64 - z[0])
115 return -int64(math.MaxUint64 - z[0] + 1)
116}
117
118// SetUint64 assigns the non-negative uint64 x to z, clearing its upper limbs.
119//
120// Parameters:
121// - x: Unsigned 64-bit value to store.
122//
123// Returns:
124// - z: The receiver representing x as a non-negative Int.
125func (z *Int) SetUint64(x uint64) *Int {
126 z[3], z[2], z[1], z[0] = 0, 0, 0, x
127 return z
128}
129
130// IsUint64 reports whether z fits in an unsigned 64-bit word.
131//
132// Returns:
133// - fits: True when all three upper 64-bit limbs of z are zero.
134func (z *Int) IsUint64() bool {
135 return (z[1] | z[2] | z[3]) == 0
136}
137
138// Uint64 converts z to uint64 when its upper 192 bits are zero.
139//
140// Returns:
141// - value: z's exact unsigned 64-bit value.
142//
143// Panics if any upper limb of z is non-zero.
144func (z *Int) Uint64() uint64 {
145 if !z.IsUint64() {
146 panic("int256: uint64 overflow")
147 }
148 return z[0]
149}
150
151// Abs returns the unsigned magnitude of z.
152//
153// Returns:
154// - magnitude: A *u256.Uint containing |z|; negative values are negated before conversion.
155//
156// Panics for MinInt256 because NegOverflow cannot represent its positive magnitude as Int.
157func (z *Int) Abs() *u256.Uint {
158 if z.IsNeg() {
159 neg := new(Int).NegOverflow(z)
160 return &u256.Uint{neg[0], neg[1], neg[2], neg[3]}
161 }
162 return &u256.Uint{z[0], z[1], z[2], z[3]}
163}
164
165// Sign reports the signed sign of z.
166//
167// Returns:
168// - sign: -1 for negative z, 0 for zero z, or 1 for positive z.
169func (z *Int) Sign() int {
170 if z.IsZero() {
171 return 0
172 }
173 if z[3]&0x8000000000000000 == 0 {
174 return 1
175 }
176 return -1
177}
178
179// IsZero reports whether every limb of z is zero.
180//
181// Returns:
182// - isZero: True exactly when z represents the signed value 0.
183func (z *Int) IsZero() bool {
184 return (z[0] | z[1] | z[2] | z[3]) == 0
185}
186
187// IsOne reports whether z represents the signed value 1.
188//
189// Returns:
190// - isOne: True exactly when the low limb is 1 and all upper limbs are zero.
191func (z *Int) IsOne() bool {
192 return (z[0] == 1) && (z[1]|z[2]|z[3]) == 0
193}
194
195// IsNeg reports whether z has its signed two's-complement sign bit set.
196//
197// Returns:
198// - isNegative: True when z is negative, including MinInt256.
199func (z *Int) IsNeg() bool {
200 return z[3]&0x8000000000000000 != 0
201}
202
203// IsPositive reports whether z is strictly greater than zero.
204//
205// Returns:
206// - isPositive: True when the sign bit is clear and at least one value bit is set.
207func (z *Int) IsPositive() bool {
208 return (z[3]&0x8000000000000000) == 0 && (z[3]|z[2]|z[1]|z[0]) != 0
209}
210
211// IsMinI256 reports whether z equals MinInt256.
212//
213// Returns:
214// - isMinimum: True only for the bit pattern 0x8000...0000.
215func (z *Int) IsMinI256() bool {
216 return (z[3] == 0x8000000000000000) && ((z[2] | z[1] | z[0]) == 0)
217}
218
219// NegOverflow computes the two's-complement negation of x and rejects the
220// one value whose positive magnitude is outside signed int256.
221//
222// Parameters:
223// - x: Signed 256-bit value to negate.
224//
225// Returns:
226// - z: The receiver containing -x.
227//
228// Panics when x is MinInt256.
229func (z *Int) NegOverflow(x *Int) *Int {
230 if x[3] == 0x8000000000000000 && x[2] == 0 && x[1] == 0 && x[0] == 0 {
231 panic("int256: overflow")
232 }
233
234 return z.Neg(x)
235}
236
237// Neg computes the two's-complement negation of x modulo 2^256.
238//
239// Parameters:
240// - x: 256-bit value whose bits are complemented and incremented.
241//
242// Returns:
243// - z: The receiver containing the wrapped negation of x.
244func (z *Int) Neg(x *Int) *Int {
245 var carry uint64
246 z[0], z[1], z[2], z[3] = ^x[0], ^x[1], ^x[2], ^x[3]
247 z[0], carry = bits.Add64(z[0], 1, 0)
248 z[1], carry = bits.Add64(z[1], 0, carry)
249 z[2], carry = bits.Add64(z[2], 0, carry)
250 z[3] += carry
251 return z
252}
253
254// Eq reports whether z and x have identical 256-bit representations.
255//
256// Parameters:
257// - x: Int to compare with z.
258//
259// Returns:
260// - equal: True when all four limbs match.
261func (z *Int) Eq(x *Int) bool {
262 return (z[0] == x[0]) && (z[1] == x[1]) && (z[2] == x[2]) && (z[3] == x[3])
263}
264
265// Neq reports whether z and x have different 256-bit representations.
266//
267// Parameters:
268// - x: Int to compare with z.
269//
270// Returns:
271// - different: True when at least one limb differs.
272func (z *Int) Neq(x *Int) bool {
273 return !z.Eq(x)
274}
275
276// Add adds x and y modulo 2^256.
277//
278// Parameters:
279// - x: First signed 256-bit addend.
280// - y: Second signed 256-bit addend.
281//
282// Returns:
283// - z: The receiver containing the low 256 bits of x + y.
284func (z *Int) Add(x, y *Int) *Int {
285 var carry uint64
286 z[0], carry = bits.Add64(x[0], y[0], 0)
287 z[1], carry = bits.Add64(x[1], y[1], carry)
288 z[2], carry = bits.Add64(x[2], y[2], carry)
289 z[3] = x[3] + y[3] + carry
290 return z
291}
292
293// AddOverflow adds x and y modulo 2^256 and reports signed overflow.
294//
295// Parameters:
296// - x: First signed 256-bit addend.
297// - y: Second signed 256-bit addend.
298//
299// Returns:
300// - z: The wrapped 256-bit sum.
301// - overflow: True when x and y have the same sign but the wrapped sum has the opposite sign.
302func (z *Int) AddOverflow(x, y *Int) (*Int, bool) {
303 var carry uint64
304 z[0], carry = bits.Add64(x[0], y[0], 0)
305 z[1], carry = bits.Add64(x[1], y[1], carry)
306 z[2], carry = bits.Add64(x[2], y[2], carry)
307 z[3] = x[3] + y[3] + carry
308 var overflow bool
309 signX, signY, signZ := x.Sign(), y.Sign(), z.Sign()
310 if (signX == signY) && (signX != signZ) {
311 overflow = true
312 }
313 return z, overflow
314}
315
316// Sub subtracts y from x modulo 2^256.
317//
318// Parameters:
319// - x: Signed 256-bit minuend.
320// - y: Signed 256-bit subtrahend.
321//
322// Returns:
323// - z: The receiver containing the low 256 bits of x - y.
324func (z *Int) Sub(x, y *Int) *Int {
325 var carry uint64
326 z[0], carry = bits.Sub64(x[0], y[0], 0)
327 z[1], carry = bits.Sub64(x[1], y[1], carry)
328 z[2], carry = bits.Sub64(x[2], y[2], carry)
329 z[3] = x[3] - y[3] - carry
330 return z
331}
332
333// SubOverflow subtracts y from x modulo 2^256 and reports signed overflow.
334//
335// Parameters:
336// - x: Signed 256-bit minuend.
337// - y: Signed 256-bit subtrahend.
338//
339// Returns:
340// - z: The wrapped 256-bit difference.
341// - overflow: True when the mathematical signed difference is outside the int256 range.
342func (z *Int) SubOverflow(x, y *Int) (*Int, bool) {
343 var carry uint64
344 z[0], carry = bits.Sub64(x[0], y[0], 0)
345 z[1], carry = bits.Sub64(x[1], y[1], carry)
346 z[2], carry = bits.Sub64(x[2], y[2], carry)
347 z[3] = x[3] - y[3] - carry
348 var overflow bool
349 signX, signY, signZ := x.Sign(), y.Sign(), z.Sign()
350 if (signX == 0 && y.IsMinI256()) || ((signX != 0) && (signX != signY) && (signX != signZ)) {
351 overflow = true
352 }
353 return z, overflow
354}
355
356// Mul multiplies x and y modulo 2^256.
357//
358// Parameters:
359// - x: First signed 256-bit factor.
360// - y: Second signed 256-bit factor.
361//
362// Returns:
363// - z: The receiver containing the low 256 bits of x * y.
364func (z *Int) Mul(x, y *Int) *Int {
365 var (
366 res Int
367 carry uint64
368 res1, res2, res3 uint64
369 )
370
371 carry, res[0] = bits.Mul64(x[0], y[0])
372 carry, res1 = umulHop(carry, x[1], y[0])
373 carry, res2 = umulHop(carry, x[2], y[0])
374 res3 = x[3]*y[0] + carry
375
376 carry, res[1] = umulHop(res1, x[0], y[1])
377 carry, res2 = umulStep(res2, x[1], y[1], carry)
378 res3 = res3 + x[2]*y[1] + carry
379
380 carry, res[2] = umulHop(res2, x[0], y[2])
381 res3 = res3 + x[1]*y[2] + carry
382
383 res[3] = res3 + x[0]*y[3]
384
385 return z.Set(&res)
386}
387
388// MulOverflow multiplies x and y and reports whether the signed product exceeds int256.
389// The returned value is still the wrapped low 256-bit product.
390//
391// Parameters:
392// - x: First signed 256-bit factor.
393// - y: Second signed 256-bit factor.
394//
395// Returns:
396// - z: The low 256 bits of the signed product, with its sign restored.
397// - overflow: True when the mathematical product is outside [-2^255, 2^255 - 1].
398func (z *Int) MulOverflow(x, y *Int) (*Int, bool) {
399 if (x.IsMinI256() && y.IsOne()) || (x.IsOne() && y.IsMinI256()) {
400 return z.Set(MinInt256()), false
401 }
402
403 var flipSign bool
404 xSign, ySign := x.Sign(), y.Sign()
405 if xSign*ySign == -1 {
406 flipSign = true
407 }
408
409 xCopy := x.Clone()
410 yCopy := y.Clone()
411
412 if xSign < 0 {
413 xCopy.Neg(xCopy)
414 }
415 if ySign < 0 {
416 yCopy.Neg(yCopy)
417 }
418
419 p := umul(xCopy, yCopy)
420 z[0], z[1], z[2], z[3] = p[0], p[1], p[2], p[3]
421
422 var overflow bool
423 if (p[4] | p[5] | p[6] | p[7]) != 0 {
424 overflow = true
425 } else if z.IsNeg() {
426 // The 256th bit is set, which means the absolute value is >= 2^255
427 // This is only valid if the result should be exactly -2^255
428 if !flipSign || !z.IsMinI256() {
429 overflow = true
430 }
431 }
432
433 if flipSign {
434 z.Neg(z)
435 }
436
437 return z, overflow
438}
439
440func umul(x, y *Int) [8]uint64 {
441 var (
442 res [8]uint64
443 carry, carry4, carry5, carry6 uint64
444 res1, res2, res3, res4, res5 uint64
445 )
446
447 carry, res[0] = bits.Mul64(x[0], y[0])
448 carry, res1 = umulHop(carry, x[1], y[0])
449 carry, res2 = umulHop(carry, x[2], y[0])
450 carry4, res3 = umulHop(carry, x[3], y[0])
451
452 carry, res[1] = umulHop(res1, x[0], y[1])
453 carry, res2 = umulStep(res2, x[1], y[1], carry)
454 carry, res3 = umulStep(res3, x[2], y[1], carry)
455 carry5, res4 = umulStep(carry4, x[3], y[1], carry)
456
457 carry, res[2] = umulHop(res2, x[0], y[2])
458 carry, res3 = umulStep(res3, x[1], y[2], carry)
459 carry, res4 = umulStep(res4, x[2], y[2], carry)
460 carry6, res5 = umulStep(carry5, x[3], y[2], carry)
461
462 carry, res[3] = umulHop(res3, x[0], y[3])
463 carry, res[4] = umulStep(res4, x[1], y[3], carry)
464 carry, res[5] = umulStep(res5, x[2], y[3], carry)
465 res[7], res[6] = umulStep(carry6, x[3], y[3], carry)
466
467 return res
468}
469
470func umulStep(z, x, y, carry uint64) (hi, lo uint64) {
471 hi, lo = bits.Mul64(x, y)
472 lo, carry = bits.Add64(lo, carry, 0)
473 hi += carry
474 lo, carry = bits.Add64(lo, z, 0)
475 hi += carry
476 return hi, lo
477}
478
479func umulHop(z, x, y uint64) (hi, lo uint64) {
480 hi, lo = bits.Mul64(x, y)
481 lo, carry := bits.Add64(lo, z, 0)
482 hi += carry
483 return hi, lo
484}
485
486// Clear sets every limb of z to zero.
487//
488// Returns:
489// - z: The receiver representing the signed value 0.
490func (z *Int) Clear() *Int {
491 z[0], z[1], z[2], z[3] = 0, 0, 0, 0
492 return z
493}
494
495// SetOne sets z to the signed value 1.
496//
497// Returns:
498// - z: The receiver with only its least-significant bit set.
499func (z *Int) SetOne() *Int {
500 z[3], z[2], z[1], z[0] = 0, 0, 0, 1
501 return z
502}
503
504// SetAllBitsOne sets every bit of z to one, the two's-complement representation of -1.
505//
506// Returns:
507// - z: The receiver containing the all-ones 256-bit pattern.
508func (z *Int) SetAllBitsOne() *Int {
509 z[0], z[1], z[2], z[3] = 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff
510 return z
511}
512
513// Div divides signed 256-bit x by y, truncating the quotient toward zero.
514//
515// Parameters:
516// - x: Signed 256-bit dividend.
517// - y: Signed 256-bit divisor.
518//
519// Returns:
520// - z: The receiver containing the signed quotient x / y.
521//
522// Panics if y is zero.
523func (z *Int) Div(x, y *Int) *Int {
524 if x.Sign() > 0 {
525 if y.Sign() > 0 {
526 return z.uquo(x, y)
527 }
528 z.uquo(x, new(Int).Neg(y))
529 return z.Neg(z)
530 }
531 if y.Sign() < 0 {
532 return z.uquo(new(Int).Neg(x), new(Int).Neg(y))
533 }
534 z.uquo(new(Int).Neg(x), y)
535 return z.Neg(z)
536}
537
538func (z *Int) uquo(x, y *Int) *Int {
539 if y.IsZero() {
540 panic("zero division")
541 }
542 if x.IsZero() {
543 return z.Clear()
544 }
545 if x.Eq(y) {
546 return z.SetOne()
547 }
548 if x.IsInt64() && y.IsInt64() {
549 return z.SetInt64(x.Int64() / y.Int64())
550 }
551 quot := Int{}
552 udivrem(quot[:], x[:], y)
553 return z.Set(")
554}
555
556// Rem computes the signed remainder of x divided by y, preserving x's sign.
557//
558// Parameters:
559// - x: Signed 256-bit dividend.
560// - y: Signed 256-bit divisor.
561//
562// Returns:
563// - z: The receiver containing x % y, with magnitude less than |y|.
564//
565// Panics if y is zero.
566func (z *Int) Rem(x, y *Int) *Int {
567 if x.Sign() > 0 {
568 if y.Sign() > 0 {
569 return z.urem(x, y)
570 }
571 return z.urem(x, new(Int).Neg(y))
572 }
573 if y.Sign() < 0 {
574 z.urem(new(Int).Neg(x), new(Int).Neg(y))
575 return z.Neg(z)
576 }
577 z.urem(new(Int).Neg(x), y)
578 return z.Neg(z)
579}
580
581func (z *Int) urem(x, y *Int) *Int {
582 if y.IsZero() {
583 panic("zero division")
584 }
585 if x.IsZero() {
586 return z.Clear()
587 }
588 if x.Eq(y) {
589 return z.Clear()
590 }
591 if x.IsInt64() && y.IsInt64() {
592 xInt64 := x.Int64()
593 yInt64 := y.Int64()
594 return z.SetInt64(xInt64 % yInt64)
595 }
596 quot := Int{}
597 rem := udivrem(quot[:], x[:], y)
598 return z.Set(&rem)
599}
600
601// Lt reports whether z is less than x as signed int256 values.
602//
603// Parameters:
604// - x: Signed 256-bit value to compare with z.
605//
606// Returns:
607// - less: True when z < x.
608func (z *Int) Lt(x *Int) bool {
609 return z.Cmp(x) < 0
610}
611
612// Lte reports whether z is less than or equal to x as signed int256 values.
613//
614// Parameters:
615// - x: Signed 256-bit value to compare with z.
616//
617// Returns:
618// - lessOrEqual: True when z <= x.
619func (z *Int) Lte(x *Int) bool {
620 return z.Cmp(x) <= 0
621}
622
623// Gt reports whether z is greater than x as signed int256 values.
624//
625// Parameters:
626// - x: Signed 256-bit value to compare with z.
627//
628// Returns:
629// - greater: True when z > x.
630func (z *Int) Gt(x *Int) bool {
631 return z.Cmp(x) > 0
632}
633
634// Gte reports whether z is greater than or equal to x as signed int256 values.
635//
636// Parameters:
637// - x: Signed 256-bit value to compare with z.
638//
639// Returns:
640// - greaterOrEqual: True when z >= x.
641func (z *Int) Gte(x *Int) bool {
642 return z.Cmp(x) >= 0
643}
644
645// Cmp compares z and x as signed two's-complement int256 values.
646//
647// Parameters:
648// - x: Signed 256-bit value to compare with z.
649//
650// Returns:
651// - comparison: -1 when z < x, 0 when z == x, and 1 when z > x.
652func (z *Int) Cmp(x *Int) int {
653 zneg := int8(z[3] >> 63)
654 xneg := int8(x[3] >> 63)
655 if zneg != xneg {
656 return int(xneg - zneg)
657 }
658 d0, carry := bits.Sub64(z[0], x[0], 0)
659 d1, carry := bits.Sub64(z[1], x[1], carry)
660 d2, carry := bits.Sub64(z[2], x[2], carry)
661 d3, carry := bits.Sub64(z[3], x[3], carry)
662 if carry == 1 {
663 return -1
664 }
665 if d0|d1|d2|d3 == 0 {
666 return 0
667 }
668 return 1
669}
670
671// Clone returns an independent copy of z.
672//
673// Returns:
674// - clone: A fresh *Int with the same four limbs as z.
675func (z *Int) Clone() *Int {
676 return &Int{z[0], z[1], z[2], z[3]}
677}
678
679// Or sets z to the bitwise OR of x and y.
680//
681// Parameters:
682// - x: First 256-bit operand.
683// - y: Second 256-bit operand.
684//
685// Returns:
686// - z: The receiver containing x | y.
687func (z *Int) Or(x, y *Int) *Int {
688 z[0] = x[0] | y[0]
689 z[1] = x[1] | y[1]
690 z[2] = x[2] | y[2]
691 z[3] = x[3] | y[3]
692 return z
693}
694
695// And sets z to the bitwise AND of x and y.
696//
697// Parameters:
698// - x: First 256-bit operand.
699// - y: Second 256-bit operand.
700//
701// Returns:
702// - z: The receiver containing x & y.
703func (z *Int) And(x, y *Int) *Int {
704 z[0] = x[0] & y[0]
705 z[1] = x[1] & y[1]
706 z[2] = x[2] & y[2]
707 z[3] = x[3] & y[3]
708 return z
709}
710
711// Xor sets z to the bitwise exclusive OR of x and y.
712//
713// Parameters:
714// - x: First 256-bit operand.
715// - y: Second 256-bit operand.
716//
717// Returns:
718// - z: The receiver containing x ^ y.
719func (z *Int) Xor(x, y *Int) *Int {
720 z[0] = x[0] ^ y[0]
721 z[1] = x[1] ^ y[1]
722 z[2] = x[2] ^ y[2]
723 z[3] = x[3] ^ y[3]
724 return z
725}
726
727// Not sets z to the bitwise complement of x.
728//
729// Parameters:
730// - x: 256-bit operand whose bits are complemented.
731//
732// Returns:
733// - z: The receiver containing ^x.
734func (z *Int) Not(x *Int) *Int {
735 z[0] = ^x[0]
736 z[1] = ^x[1]
737 z[2] = ^x[2]
738 z[3] = ^x[3]
739 return z
740}
741
742// Lsh sets z to x left-shifted by n bits, truncating to 256 bits.
743//
744// Parameters:
745// - x: 256-bit bit pattern to shift.
746// - n: Number of bit positions to shift left; n >= 256 yields zero.
747//
748// Returns:
749// - z: The receiver containing (x << n) modulo 2^256.
750func (z *Int) Lsh(x *Int, n uint) *Int {
751 if n == 0 {
752 return z.Set(x)
753 }
754 if n >= 256 {
755 return z.Clear()
756 }
757 // Handle exact multiples of 64 separately to avoid 64-bit shift issues
758 if n&0x3f == 0 {
759 switch n {
760 case 64:
761 z[3], z[2], z[1], z[0] = x[2], x[1], x[0], 0
762 case 128:
763 z[3], z[2], z[1], z[0] = x[1], x[0], 0, 0
764 case 192:
765 z[3], z[2], z[1], z[0] = x[0], 0, 0, 0
766 }
767 return z
768 }
769 switch {
770 case n > 192:
771 n -= 192
772 z[3], z[2], z[1], z[0] = x[0]<<n, 0, 0, 0
773 case n > 128:
774 n -= 128
775 z[3] = (x[1] << n) | (x[0] >> (64 - n))
776 z[2] = x[0] << n
777 z[1], z[0] = 0, 0
778 case n > 64:
779 n -= 64
780 z[3] = (x[2] << n) | (x[1] >> (64 - n))
781 z[2] = (x[1] << n) | (x[0] >> (64 - n))
782 z[1] = x[0] << n
783 z[0] = 0
784 default:
785 z[3] = (x[3] << n) | (x[2] >> (64 - n))
786 z[2] = (x[2] << n) | (x[1] >> (64 - n))
787 z[1] = (x[1] << n) | (x[0] >> (64 - n))
788 z[0] = x[0] << n
789 }
790 return z
791}
792
793// Rsh shifts x right by n bits using signed arithmetic semantics.
794// Non-negative values receive zero-fill; negative values receive sign extension.
795//
796// Parameters:
797// - x: Signed 256-bit value to shift.
798// - n: Number of bit positions to shift right.
799//
800// Returns:
801// - z: The receiver containing the arithmetic right shift of x.
802func (z *Int) Rsh(x *Int, n uint) *Int {
803 if n == 0 {
804 return z.Set(x)
805 }
806 if x.IsNeg() {
807 return z.negRsh(x, n)
808 }
809 return z.rsh(x, n)
810}
811
812func (z *Int) rsh(x *Int, n uint) *Int {
813 if n >= 256 {
814 return z.Clear()
815 }
816 // Handle exact multiples of 64 separately to avoid 64-bit shift issues
817 if n&0x3f == 0 {
818 switch n {
819 case 0:
820 return z.Set(x)
821 case 64:
822 z[3], z[2], z[1], z[0] = 0, x[3], x[2], x[1]
823 case 128:
824 z[3], z[2], z[1], z[0] = 0, 0, x[3], x[2]
825 case 192:
826 z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]
827 }
828 return z
829 }
830 switch {
831 case n > 192:
832 n -= 192
833 z[3], z[2], z[1], z[0] = 0, 0, 0, x[3]>>n
834 case n > 128:
835 n -= 128
836 z[3], z[2] = 0, 0
837 z[1] = x[3] >> n
838 z[0] = (x[3] << (64 - n)) | (x[2] >> n)
839 case n > 64:
840 n -= 64
841 z[3] = 0
842 z[2] = x[3] >> n
843 z[1] = (x[3] << (64 - n)) | (x[2] >> n)
844 z[0] = (x[2] << (64 - n)) | (x[1] >> n)
845 default:
846 z[3] = x[3] >> n
847 z[2] = (x[3] << (64 - n)) | (x[2] >> n)
848 z[1] = (x[2] << (64 - n)) | (x[1] >> n)
849 z[0] = (x[1] << (64 - n)) | (x[0] >> n)
850 }
851 return z
852}
853
854func (z *Int) negRsh(x *Int, n uint) *Int {
855 if n >= 256 {
856 return z.SetAllBitsOne()
857 }
858 var v uint64 = 0xffffffffffffffff
859 // Handle exact multiples of 64 separately to avoid 64-bit shift issues
860 if n&0x3f == 0 {
861 switch n {
862 case 0:
863 return z.Set(x)
864 case 64:
865 z[3], z[2], z[1], z[0] = v, x[3], x[2], x[1]
866 case 128:
867 z[3], z[2], z[1], z[0] = v, v, x[3], x[2]
868 case 192:
869 z[3], z[2], z[1], z[0] = v, v, v, x[3]
870 }
871 return z
872 }
873 switch {
874 case n > 192:
875 n -= 192
876 z[3], z[2], z[1], z[0] = v, v, v, (v<<(64-n))|(x[3]>>n)
877 case n > 128:
878 n -= 128
879 z[3], z[2] = v, v
880 z[1] = (v << (64 - n)) | (x[3] >> n)
881 z[0] = (x[3] << (64 - n)) | (x[2] >> n)
882 case n > 64:
883 n -= 64
884 z[3] = v
885 z[2] = (v << (64 - n)) | (x[3] >> n)
886 z[1] = (x[3] << (64 - n)) | (x[2] >> n)
887 z[0] = (x[2] << (64 - n)) | (x[1] >> n)
888 default:
889 z[3] = (v << (64 - n)) | (x[3] >> n)
890 z[2] = (x[3] << (64 - n)) | (x[2] >> n)
891 z[1] = (x[2] << (64 - n)) | (x[1] >> n)
892 z[0] = (x[1] << (64 - n)) | (x[0] >> n)
893 }
894 return z
895}
896
897// BitLen returns the number of bits needed to represent z's raw 256-bit pattern.
898//
899// Returns:
900// - length: Bit length of the four-limb representation; zero has length 0 and
901// a negative value may require all 256 bits.
902func (z *Int) BitLen() int {
903 switch {
904 case z[3] != 0:
905 return 192 + bits.Len64(z[3])
906 case z[2] != 0:
907 return 128 + bits.Len64(z[2])
908 case z[1] != 0:
909 return 64 + bits.Len64(z[1])
910 default:
911 return bits.Len64(z[0])
912 }
913}
914
915// SetBytes32 loads the first 32 bytes of in as a big-endian 256-bit value.
916//
917// Parameters:
918// - in: Byte slice containing at least 32 bytes, with the most-significant byte first.
919// Bytes beyond the first 32 are ignored.
920//
921// Returns:
922// - z: The receiver populated from the 32-byte big-endian representation.
923//
924// Panics if in contains fewer than 32 bytes.
925func (z *Int) SetBytes32(in []byte) *Int {
926 _ = in[31] // bounds check hint to compiler; see golang.org/issue/14808
927 z[3] = binary.BigEndian.Uint64(in[0:8])
928 z[2] = binary.BigEndian.Uint64(in[8:16])
929 z[1] = binary.BigEndian.Uint64(in[16:24])
930 z[0] = binary.BigEndian.Uint64(in[24:32])
931 return z
932}
