uint256.gno
8.14 Kb · 314 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.
17//
18// Parameters:
19// - val: the initial uint64 value
20//
21// Returns:
22// - result: a new Uint initialized to val
23func NewUint(val uint64) *Uint {
24 return &Uint{val, 0, 0, 0}
25}
26
27// NewUintFromInt64 returns a new Uint initialized with the given int64 value.
28// Panics if val is negative.
29//
30// Parameters:
31// - val: the initial non-negative int64 value; a negative value panics
32//
33// Returns:
34// - result: a new Uint initialized to val
35func NewUintFromInt64(val int64) *Uint {
36 if val < 0 {
37 panic("val is negative")
38 }
39 return &Uint{uint64(val), 0, 0, 0}
40}
41
42// Zero returns a new Uint with value 0.
43//
44// Returns:
45// - result: a new zero-valued Uint
46func Zero() *Uint {
47 return &Uint{0, 0, 0, 0}
48}
49
50// One returns a new Uint with value 1.
51//
52// Returns:
53// - result: a new Uint containing one
54func One() *Uint {
55 return &Uint{1, 0, 0, 0}
56}
57
58// MaxUint256 returns the maximum 256-bit unsigned integer (2^256-1).
59//
60// Returns:
61// - result: a new Uint containing 2^256-1
62func MaxUint256() *Uint {
63 return &Uint{18446744073709551615, 18446744073709551615, 18446744073709551615, 18446744073709551615}
64}
65
66// SetAllOne sets z to the maximum 256-bit value (all bits set to 1) and returns z.
67//
68// Returns:
69// - result: z after setting every bit to one
70func (z *Uint) SetAllOne() *Uint {
71 z[3], z[2], z[1], z[0] = 18446744073709551615, 18446744073709551615, 18446744073709551615, 18446744073709551615
72 return z
73}
74
75// Set sets z to x and returns z.
76//
77// Parameters:
78// - x: the Uint value copied into z
79//
80// Returns:
81// - result: z after copying x
82func (z *Uint) Set(x *Uint) *Uint {
83 *z = *x
84 return z
85}
86
87// SetOne sets z to 1 and returns z.
88//
89// Returns:
90// - result: z after setting it to one
91func (z *Uint) SetOne() *Uint {
92 z[3], z[2], z[1], z[0] = 0, 0, 0, 1
93 return z
94}
95
96// SetFromDecimal sets z from a decimal string and returns an error if invalid.
97// Accepts an optional leading "+" sign but rejects underscores and negative values.
98// Returns ErrBig256Range if the number exceeds 256 bits.
99//
100// Parameters:
101// - s: the decimal text to parse; a leading + is accepted, while negatives and underscores are rejected
102//
103// Returns:
104// - err: nil on success; otherwise the parse or range error
105func (z *Uint) SetFromDecimal(s string) (err error) {
106 sLen := len(s)
107 // Remove max one leading +
108 if sLen > 0 && s[0] == '+' {
109 s = s[1:]
110 sLen--
111 }
112 // Remove any number of leading zeroes
113 if sLen > 0 && s[0] == '0' {
114 var i int
115 var c rune
116 for i, c = range s {
117 if c != '0' {
118 break
119 }
120 }
121 s = s[i:]
122 sLen = len(s)
123 }
124
125 // maxUint256Str is the string representation of the maximum uint256 value.
126 maxUint256Str := "115792089237316195423570985008687907853269984665640564039457584007913129639935"
127
128 maxLen := len(maxUint256Str)
129 if sLen < maxLen {
130 return z.fromDecimal(s)
131 }
132 if sLen == maxLen {
133 if s > maxUint256Str {
134 return errors.New(ErrBig256Range)
135 }
136 return z.fromDecimal(s)
137 }
138 return errors.New(ErrBig256Range)
139}
140
141// FromDecimal creates a new Uint from a decimal string.
142// Returns an error if the number exceeds 256 bits or is invalid.
143//
144// Parameters:
145// - decimal: the decimal text representing a non-negative value within 256 bits
146//
147// Returns:
148// - value: a new parsed Uint, or nil on error
149// - err: nil on success; otherwise an invalid-format or 256-bit-range error
150func FromDecimal(decimal string) (*Uint, error) {
151 var z Uint
152 if err := z.SetFromDecimal(decimal); err != nil {
153 return nil, err
154 }
155 return &z, nil
156}
157
158// MustFromDecimal creates a new Uint from a decimal string.
159// Panics if the string is invalid or the number exceeds 256 bits.
160//
161// Parameters:
162// - decimal: the decimal text representing a non-negative value within 256 bits
163//
164// Returns:
165// - result: a new parsed Uint; invalid or out-of-range input panics
166func MustFromDecimal(decimal string) *Uint {
167 var z Uint
168 if err := z.SetFromDecimal(decimal); err != nil {
169 panic(err)
170 }
171 return &z
172}
173
174// multipliers holds the values that are needed for fromDecimal
175var multipliers = [5]Uint{
176 {0, 0, 0, 0}, // 1 (no multiplication needed in the first round)
177 {10000000000000000000, 0, 0, 0}, // 10 ^ 19
178 {687399551400673280, 5421010862427522170, 0, 0}, // 10 ^ 38
179 {5332261958806667264, 17004971331911604867, 2938735877055718769, 0}, // 10 ^ 57
180 {0, 8607968719199866880, 532749306367912313, 1593091911132452277}, // 10 ^ 76
181}
182
183// fromDecimal parses a decimal string by processing it in 19-character chunks.
184// Each chunk is multiplied by the appropriate power of 10 and accumulated.
185func (z *Uint) fromDecimal(bs string) error {
186 // first clear the input
187 z.Clear()
188 // the maximum value of uint64 is 18446744073709551615, which is 20 characters
189 // one less means that a string of 19 9's is always within the uint64 limit
190 var (
191 num uint64
192 err error
193 remaining = len(bs)
194 )
195 if remaining == 0 {
196 return errors.New("EOF")
197 }
198
199 // We proceed in steps of 19 characters (nibbles), from least significant to most significant.
200 // This means that the first (up to) 19 characters do not need to be multiplied.
201 // In the second iteration, our slice of 19 characters needs to be multiplied
202 // by a factor of 10^19. Et cetera.
203 for i := range multipliers {
204 if remaining <= 0 {
205 return nil // Done
206 }
207 if remaining > 19 {
208 num, err = strconv.ParseUint(bs[remaining-19:remaining], 10, 64)
209 } else {
210 // Final round
211 num, err = strconv.ParseUint(bs, 10, 64)
212 }
213 if err != nil {
214 return err
215 }
216 // add that number to our running total
217 if i == 0 {
218 z.SetUint64(num)
219 } else {
220 base := &Uint{uint64(num), 0, 0, 0}
221 // Check for overflow in multiplication
222 base, overflow := base.MulOverflow(base, &multipliers[i])
223 if overflow {
224 return errors.New(ErrBig256Range)
225 }
226 // Check for overflow in addition
227 base, overflow = base.AddOverflow(base, z)
228 if overflow {
229 return errors.New(ErrBig256Range)
230 }
231 z.Set(base)
232 }
233 // Chop off another 19 characters
234 if remaining > 19 {
235 bs = bs[0 : remaining-19]
236 }
237 remaining -= 19
238 }
239 return nil
240}
241
242// Byte returns the value of the byte at position n as a Uint.
243// Position n is counted from the left (0 = most significant byte).
244// Returns 0 if n >= 32.
245//
246// Parameters:
247// - n: the zero-based byte position counted from the most-significant byte; positions 32 and above yield zero
248//
249// Returns:
250// - result: z containing the selected byte as a Uint, or zero when n is outside the 32-byte value
251func (z *Uint) Byte(n *Uint) *Uint {
252 // in z, z[0] is the least significant
253 if number, overflow := n.Uint64WithOverflow(); !overflow {
254 if number < 32 {
255 number := z[4-1-number/8]
256 offset := (n[0] & 0x7) << 3 // 8*(n.d % 8)
257 z[0] = (number & (0xff00000000000000 >> offset)) >> (56 - offset)
258 z[3], z[2], z[1] = 0, 0, 0
259 return z
260 }
261 }
262
263 return z.Clear()
264}
265
266// BitLen returns the number of bits required to represent z.
267// BitLen(0) returns 0.
268//
269// Returns:
270// - bits: the number of significant bits in z, with zero represented by 0
271func (z *Uint) BitLen() int {
272 switch {
273 case z[3] != 0:
274 return 192 + bits.Len64(z[3])
275 case z[2] != 0:
276 return 128 + bits.Len64(z[2])
277 case z[1] != 0:
278 return 64 + bits.Len64(z[1])
279 default:
280 return bits.Len64(z[0])
281 }
282}
283
284// ByteLen returns the number of bytes required to represent z.
285// ByteLen(0) returns 0.
286//
287// Returns:
288// - bytes: the number of bytes needed to represent z, with zero represented by 0
289func (z *Uint) ByteLen() int {
290 return (z.BitLen() + 7) / 8
291}
292
293// Clear sets z to 0 and returns z.
294//
295// Returns:
296// - result: z after setting it to zero
297func (z *Uint) Clear() *Uint {
298 z[3], z[2], z[1], z[0] = 0, 0, 0, 0
299 return z
300}
301
302// Clone returns a new Uint with the same value as z.
303//
304// Returns:
305// - result: a newly allocated Uint with the same value as z
306func (z *Uint) Clone() *Uint {
307 var x Uint
308 x[0] = z[0]
309 x[1] = z[1]
310 x[2] = z[2]
311 x[3] = z[3]
312
313 return &x
314}