uint256.gno
6.25 Kb · 243 lines
1package uint256
2
3import (
4 "errors"
5 "math/bits"
6 "strconv"
7)
8
9const ErrBig256Range = "decimal number > 256 bits"
10
11// Uint represents a 256-bit unsigned integer.
12// It is stored as an array of 4 uint64 in little-endian order,
13// where arr[0] is the least significant and arr[3] is the most significant.
14type Uint [4]uint64
15
16// NewUint returns a new Uint initialized with the given uint64 value.
17func NewUint(val uint64) *Uint {
18 return &Uint{val, 0, 0, 0}
19}
20
21// NewUintFromInt64 returns a new Uint initialized with the given int64 value.
22// Panics if val is negative.
23func NewUintFromInt64(val int64) *Uint {
24 if val < 0 {
25 panic("val is negative")
26 }
27 return &Uint{uint64(val), 0, 0, 0}
28}
29
30// Zero returns a new Uint with value 0.
31func Zero() *Uint {
32 return &Uint{0, 0, 0, 0}
33}
34
35// One returns a new Uint with value 1.
36func One() *Uint {
37 return &Uint{1, 0, 0, 0}
38}
39
40func MaxUint256() *Uint {
41 return &Uint{18446744073709551615, 18446744073709551615, 18446744073709551615, 18446744073709551615}
42}
43
44// SetAllOne sets z to the maximum 256-bit value (all bits set to 1) and returns z.
45func (z *Uint) SetAllOne() *Uint {
46 z[3], z[2], z[1], z[0] = 18446744073709551615, 18446744073709551615, 18446744073709551615, 18446744073709551615
47 return z
48}
49
50// Set sets z to x and returns z.
51func (z *Uint) Set(x *Uint) *Uint {
52 *z = *x
53 return z
54}
55
56// SetOne sets z to 1 and returns z.
57func (z *Uint) SetOne() *Uint {
58 z[3], z[2], z[1], z[0] = 0, 0, 0, 1
59 return z
60}
61
62// SetFromDecimal sets z from a decimal string and returns an error if invalid.
63// Accepts an optional leading "+" sign but rejects underscores and negative values.
64// Returns ErrBig256Range if the number exceeds 256 bits.
65func (z *Uint) SetFromDecimal(s string) (err error) {
66 sLen := len(s)
67 // Remove max one leading +
68 if sLen > 0 && s[0] == '+' {
69 s = s[1:]
70 sLen--
71 }
72 // Remove any number of leading zeroes
73 if sLen > 0 && s[0] == '0' {
74 var i int
75 var c rune
76 for i, c = range s {
77 if c != '0' {
78 break
79 }
80 }
81 s = s[i:]
82 sLen = len(s)
83 }
84
85 // maxUint256Str is the string representation of the maximum uint256 value.
86 maxUint256Str := "115792089237316195423570985008687907853269984665640564039457584007913129639935"
87
88 maxLen := len(maxUint256Str)
89 if sLen < maxLen {
90 return z.fromDecimal(s)
91 }
92 if sLen == maxLen {
93 if s > maxUint256Str {
94 return errors.New(ErrBig256Range)
95 }
96 return z.fromDecimal(s)
97 }
98 return errors.New(ErrBig256Range)
99}
100
101// FromDecimal creates a new Uint from a decimal string.
102// Returns an error if the number exceeds 256 bits or is invalid.
103func FromDecimal(decimal string) (*Uint, error) {
104 var z Uint
105 if err := z.SetFromDecimal(decimal); err != nil {
106 return nil, err
107 }
108 return &z, nil
109}
110
111// MustFromDecimal creates a new Uint from a decimal string.
112// Panics if the string is invalid or the number exceeds 256 bits.
113func MustFromDecimal(decimal string) *Uint {
114 var z Uint
115 if err := z.SetFromDecimal(decimal); err != nil {
116 panic(err)
117 }
118 return &z
119}
120
121// multipliers holds the values that are needed for fromDecimal
122var multipliers = [5]Uint{
123 {0, 0, 0, 0}, // 1 (no multiplication needed in the first round)
124 {10000000000000000000, 0, 0, 0}, // 10 ^ 19
125 {687399551400673280, 5421010862427522170, 0, 0}, // 10 ^ 38
126 {5332261958806667264, 17004971331911604867, 2938735877055718769, 0}, // 10 ^ 57
127 {0, 8607968719199866880, 532749306367912313, 1593091911132452277}, // 10 ^ 76
128}
129
130// fromDecimal parses a decimal string by processing it in 19-character chunks.
131// Each chunk is multiplied by the appropriate power of 10 and accumulated.
132func (z *Uint) fromDecimal(bs string) error {
133 // first clear the input
134 z.Clear()
135 // the maximum value of uint64 is 18446744073709551615, which is 20 characters
136 // one less means that a string of 19 9's is always within the uint64 limit
137 var (
138 num uint64
139 err error
140 remaining = len(bs)
141 )
142 if remaining == 0 {
143 return errors.New("EOF")
144 }
145
146 // We proceed in steps of 19 characters (nibbles), from least significant to most significant.
147 // This means that the first (up to) 19 characters do not need to be multiplied.
148 // In the second iteration, our slice of 19 characters needs to be multiplied
149 // by a factor of 10^19. Et cetera.
150 for i := range multipliers {
151 if remaining <= 0 {
152 return nil // Done
153 }
154 if remaining > 19 {
155 num, err = strconv.ParseUint(bs[remaining-19:remaining], 10, 64)
156 } else {
157 // Final round
158 num, err = strconv.ParseUint(bs, 10, 64)
159 }
160 if err != nil {
161 return err
162 }
163 // add that number to our running total
164 if i == 0 {
165 z.SetUint64(num)
166 } else {
167 base := &Uint{uint64(num), 0, 0, 0}
168 // Check for overflow in multiplication
169 base, overflow := base.MulOverflow(base, &multipliers[i])
170 if overflow {
171 return errors.New(ErrBig256Range)
172 }
173 // Check for overflow in addition
174 base, overflow = base.AddOverflow(base, z)
175 if overflow {
176 return errors.New(ErrBig256Range)
177 }
178 z.Set(base)
179 }
180 // Chop off another 19 characters
181 if remaining > 19 {
182 bs = bs[0 : remaining-19]
183 }
184 remaining -= 19
185 }
186 return nil
187}
188
189// Byte returns the value of the byte at position n as a Uint.
190// Position n is counted from the right (0 = least significant byte).
191// Returns 0 if n >= 32.
192func (z *Uint) Byte(n *Uint) *Uint {
193 // in z, z[0] is the least significant
194 if number, overflow := n.Uint64WithOverflow(); !overflow {
195 if number < 32 {
196 number := z[4-1-number/8]
197 offset := (n[0] & 0x7) << 3 // 8*(n.d % 8)
198 z[0] = (number & (0xff00000000000000 >> offset)) >> (56 - offset)
199 z[3], z[2], z[1] = 0, 0, 0
200 return z
201 }
202 }
203
204 return z.Clear()
205}
206
207// BitLen returns the number of bits required to represent z.
208// BitLen(0) returns 0.
209func (z *Uint) BitLen() int {
210 switch {
211 case z[3] != 0:
212 return 192 + bits.Len64(z[3])
213 case z[2] != 0:
214 return 128 + bits.Len64(z[2])
215 case z[1] != 0:
216 return 64 + bits.Len64(z[1])
217 default:
218 return bits.Len64(z[0])
219 }
220}
221
222// ByteLen returns the number of bytes required to represent z.
223// ByteLen(0) returns 0.
224func (z *Uint) ByteLen() int {
225 return (z.BitLen() + 7) / 8
226}
227
228// Clear sets z to 0 and returns z.
229func (z *Uint) Clear() *Uint {
230 z[3], z[2], z[1], z[0] = 0, 0, 0, 0
231 return z
232}
233
234// Clone returns a new Uint with the same value as z.
235func (z *Uint) Clone() *Uint {
236 var x Uint
237 x[0] = z[0]
238 x[1] = z[1]
239 x[2] = z[2]
240 x[3] = z[3]
241
242 return &x
243}
