uint256.gno
8.64 Kb ยท 292 lines
1// Ported from https://github.com/holiman/uint256
2// This package provides a 256-bit unsigned integer type, Uint256, and associated functions.
3package uint256
4
5import (
6 "errors"
7 "math/bits"
8 "strconv"
9)
10
11const (
12 MaxUint64 = 1<<64 - 1
13 uintSize = 32 << (^uint(0) >> 63)
14)
15
16// Uint is represented as an array of 4 uint64, in little-endian order,
17// so that Uint[3] is the most significant, and Uint[0] is the least significant
18type Uint struct {
19 arr [4]uint64
20}
21
22// NewUint returns a new initialized Uint.
23func NewUint(val uint64) *Uint {
24 z := &Uint{arr: [4]uint64{val, 0, 0, 0}}
25 return z
26}
27
28// Zero returns a new Uint initialized to zero.
29func Zero() *Uint {
30 return NewUint(0)
31}
32
33// One returns a new Uint initialized to one.
34func One() *Uint {
35 return NewUint(1)
36}
37
38// SetAllOne sets all the bits of z to 1
39func (z *Uint) SetAllOne() *Uint {
40 z.arr[3], z.arr[2], z.arr[1], z.arr[0] = MaxUint64, MaxUint64, MaxUint64, MaxUint64
41 return z
42}
43
44// Set sets z to x and returns z.
45func (z *Uint) Set(x *Uint) *Uint {
46 *z = *x
47
48 return z
49}
50
51// SetOne sets z to 1
52func (z *Uint) SetOne() *Uint {
53 z.arr[3], z.arr[2], z.arr[1], z.arr[0] = 0, 0, 0, 1
54 return z
55}
56
57const twoPow256Sub1 = "115792089237316195423570985008687907853269984665640564039457584007913129639935"
58
59// SetFromDecimal sets z from the given string, interpreted as a decimal number.
60// OBS! This method is _not_ strictly identical to the (*big.Uint).SetString(..., 10) method.
61// Notable differences:
62// - This method does not accept underscore input, e.g. "100_000",
63// - This method does not accept negative zero as valid, e.g "-0",
64// - (this method does not accept any negative input as valid))
65func (z *Uint) SetFromDecimal(s string) (err error) {
66 // Remove max one leading +
67 if len(s) > 0 && s[0] == '+' {
68 s = s[1:]
69 }
70 // Remove any number of leading zeroes
71 if len(s) > 0 && s[0] == '0' {
72 var i int
73 var c rune
74 for i, c = range s {
75 if c != '0' {
76 break
77 }
78 }
79 s = s[i:]
80 }
81 if len(s) < len(twoPow256Sub1) {
82 return z.fromDecimal(s)
83 }
84 if len(s) == len(twoPow256Sub1) {
85 if s > twoPow256Sub1 {
86 return ErrBig256Range
87 }
88 return z.fromDecimal(s)
89 }
90 return ErrBig256Range
91}
92
93// FromDecimal is a convenience-constructor to create an Uint from a
94// decimal (base 10) string. Numbers larger than 256 bits are not accepted.
95func FromDecimal(decimal string) (*Uint, error) {
96 var z Uint
97 if err := z.SetFromDecimal(decimal); err != nil {
98 return nil, err
99 }
100 return &z, nil
101}
102
103// MustFromDecimal is a convenience-constructor to create an Uint from a
104// decimal (base 10) string.
105// Returns a new Uint and panics if any error occurred.
106func MustFromDecimal(decimal string) *Uint {
107 var z Uint
108 if err := z.SetFromDecimal(decimal); err != nil {
109 panic(err)
110 }
111 return &z
112}
113
114// multipliers holds the values that are needed for fromDecimal
115var multipliers = [5]*Uint{
116 nil, // represents first round, no multiplication needed
117 {[4]uint64{10000000000000000000, 0, 0, 0}}, // 10 ^ 19
118 {[4]uint64{687399551400673280, 5421010862427522170, 0, 0}}, // 10 ^ 38
119 {[4]uint64{5332261958806667264, 17004971331911604867, 2938735877055718769, 0}}, // 10 ^ 57
120 {[4]uint64{0, 8607968719199866880, 532749306367912313, 1593091911132452277}}, // 10 ^ 76
121}
122
123// fromDecimal is a helper function to only ever be called via SetFromDecimal
124// this function takes a string and chunks it up, calling ParseUint on it up to 5 times
125// these chunks are then multiplied by the proper power of 10, then added together.
126func (z *Uint) fromDecimal(bs string) error {
127 // first clear the input
128 z.Clear()
129 // the maximum value of uint64 is 18446744073709551615, which is 20 characters
130 // one less means that a string of 19 9's is always within the uint64 limit
131 var (
132 num uint64
133 err error
134 remaining = len(bs)
135 )
136 if remaining == 0 {
137 return errors.New("EOF")
138 }
139 // We proceed in steps of 19 characters (nibbles), from least significant to most significant.
140 // This means that the first (up to) 19 characters do not need to be multiplied.
141 // In the second iteration, our slice of 19 characters needs to be multipleied
142 // by a factor of 10^19. Et cetera.
143 for i, mult := range multipliers {
144 if remaining <= 0 {
145 return nil // Done
146 } else if remaining > 19 {
147 num, err = strconv.ParseUint(bs[remaining-19:remaining], 10, 64)
148 } else {
149 // Final round
150 num, err = strconv.ParseUint(bs, 10, 64)
151 }
152 if err != nil {
153 return err
154 }
155 // add that number to our running total
156 if i == 0 {
157 z.SetUint64(num)
158 } else {
159 base := NewUint(num)
160 z.Add(z, base.Mul(base, mult))
161 }
162 // Chop off another 19 characters
163 if remaining > 19 {
164 bs = bs[0 : remaining-19]
165 }
166 remaining -= 19
167 }
168 return nil
169}
170
171// Byte sets z to the value of the byte at position n,
172// with 'z' considered as a big-endian 32-byte integer
173// if 'n' > 32, f is set to 0
174// Example: f = '5', n=31 => 5
175func (z *Uint) Byte(n *Uint) *Uint {
176 // in z, z.arr[0] is the least significant
177 if number, overflow := n.Uint64WithOverflow(); !overflow {
178 if number < 32 {
179 number := z.arr[4-1-number/8]
180 offset := (n.arr[0] & 0x7) << 3 // 8*(n.d % 8)
181 z.arr[0] = (number & (0xff00000000000000 >> offset)) >> (56 - offset)
182 z.arr[3], z.arr[2], z.arr[1] = 0, 0, 0
183 return z
184 }
185 }
186
187 return z.Clear()
188}
189
190// BitLen returns the number of bits required to represent z
191func (z *Uint) BitLen() int {
192 switch {
193 case z.arr[3] != 0:
194 return 192 + bits.Len64(z.arr[3])
195 case z.arr[2] != 0:
196 return 128 + bits.Len64(z.arr[2])
197 case z.arr[1] != 0:
198 return 64 + bits.Len64(z.arr[1])
199 default:
200 return bits.Len64(z.arr[0])
201 }
202}
203
204// ByteLen returns the number of bytes required to represent z
205func (z *Uint) ByteLen() int {
206 return (z.BitLen() + 7) / 8
207}
208
209// Clear sets z to 0
210func (z *Uint) Clear() *Uint {
211 z.arr[3], z.arr[2], z.arr[1], z.arr[0] = 0, 0, 0, 0
212 return z
213}
214
215const (
216 // hextable = "0123456789abcdef"
217 bintable = "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\x00\x01\x02\x03\x04\x05\x06\a\b\t\xff\xff\xff\xff\xff\xff\xff\n\v\f\r\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\n\v\f\r\x0e\x0f\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff"
218 badNibble = 0xff
219)
220
221// SetFromHex sets z from the given string, interpreted as a hexadecimal number.
222// OBS! This method is _not_ strictly identical to the (*big.Int).SetString(..., 16) method.
223// Notable differences:
224// - This method _require_ "0x" or "0X" prefix.
225// - This method does not accept zero-prefixed hex, e.g. "0x0001"
226// - This method does not accept underscore input, e.g. "100_000",
227// - This method does not accept negative zero as valid, e.g "-0x0",
228// - (this method does not accept any negative input as valid)
229func (z *Uint) SetFromHex(hex string) error {
230 return z.fromHex(hex)
231}
232
233// fromHex is the internal implementation of parsing a hex-string.
234func (z *Uint) fromHex(hex string) error {
235 if err := checkNumberS(hex); err != nil {
236 return err
237 }
238 if len(hex) > 66 {
239 return ErrBig256Range
240 }
241 z.Clear()
242 end := len(hex)
243 for i := 0; i < 4; i++ {
244 start := end - 16
245 if start < 2 {
246 start = 2
247 }
248 for ri := start; ri < end; ri++ {
249 nib := bintable[hex[ri]]
250 if nib == badNibble {
251 return ErrSyntax
252 }
253 z.arr[i] = z.arr[i] << 4
254 z.arr[i] += uint64(nib)
255 }
256 end = start
257 }
258 return nil
259}
260
261// FromHex is a convenience-constructor to create an Uint from
262// a hexadecimal string. The string is required to be '0x'-prefixed
263// Numbers larger than 256 bits are not accepted.
264func FromHex(hex string) (*Uint, error) {
265 var z Uint
266 if err := z.fromHex(hex); err != nil {
267 return nil, err
268 }
269 return &z, nil
270}
271
272// MustFromHex is a convenience-constructor to create an Uint from
273// a hexadecimal string.
274// Returns a new Uint and panics if any error occurred.
275func MustFromHex(hex string) *Uint {
276 var z Uint
277 if err := z.fromHex(hex); err != nil {
278 panic(err)
279 }
280 return &z
281}
282
283// Clone creates a new Uint identical to z
284func (z *Uint) Clone() *Uint {
285 var x Uint
286 x.arr[0] = z.arr[0]
287 x.arr[1] = z.arr[1]
288 x.arr[2] = z.arr[2]
289 x.arr[3] = z.arr[3]
290
291 return &x
292}
