1// uint256: Fixed size 256-bit math library
2// Copyright 2020 uint256 Authors
3// SPDX-License-Identifier: BSD-3-Clause
4
5package uint256
6
7import (
8	"encoding/binary"
9	"errors"
10	"fmt"
11	"io"
12	"math/big"
13	"math/bits"
14)
15
16const (
17	maxWords = 256 / bits.UintSize // number of big.Words in 256-bit
18
19	// The constants below work as compile-time checks: in case evaluated to
20	// negative value it cannot be assigned to uint type and compilation fails.
21	// These particular expressions check if maxWords either 4 or 8 matching
22	// 32-bit and 64-bit architectures.
23	_ uint = -(maxWords & (maxWords - 1)) // maxWords is power of two.
24	_ uint = -(maxWords & ^(4 | 8))       // maxWords is 4 or 8.
25)
26
27// ToBig returns a big.Int version of z.
28func (z *Int) ToBig() *big.Int {
29	b := new(big.Int)
30	switch maxWords { // Compile-time check.
31	case 4: // 64-bit architectures.
32		words := [4]big.Word{big.Word(z[0]), big.Word(z[1]), big.Word(z[2]), big.Word(z[3])}
33		b.SetBits(words[:])
34	case 8: // 32-bit architectures.
35		words := [8]big.Word{
36			big.Word(z[0]), big.Word(z[0] >> 32),
37			big.Word(z[1]), big.Word(z[1] >> 32),
38			big.Word(z[2]), big.Word(z[2] >> 32),
39			big.Word(z[3]), big.Word(z[3] >> 32),
40		}
41		b.SetBits(words[:])
42	}
43	return b
44}
45
46// FromBig is a convenience-constructor from big.Int.
47// Returns a new Int and whether overflow occurred.
48func FromBig(b *big.Int) (*Int, bool) {
49	z := &Int{}
50	overflow := z.SetFromBig(b)
51	return z, overflow
52}
53
54// fromHex is the internal implementation of parsing a hex-string.
55func (z *Int) fromHex(hex string) error {
56	if err := checkNumberS(hex); err != nil {
57		return err
58	}
59
60	if len(hex) > 66 {
61		return ErrBig256Range
62	}
63	end := len(hex)
64	for i := 0; i < 4; i++ {
65		start := end - 16
66		if start < 2 {
67			start = 2
68		}
69		for ri := start; ri < end; ri++ {
70			nib := bintable[hex[ri]]
71			if nib == badNibble {
72				return ErrSyntax
73			}
74			z[i] = z[i] << 4
75			z[i] += uint64(nib)
76		}
77		end = start
78	}
79	return nil
80}
81
82// FromHex is a convenience-constructor to create an Int from
83// a hexadecimal string. The string is required to be '0x'-prefixed
84// Numbers larger than 256 bits are not accepted.
85func FromHex(hex string) (*Int, error) {
86	var z Int
87	if err := z.fromHex(hex); err != nil {
88		return nil, err
89	}
90	return &z, nil
91}
92
93// UnmarshalText implements encoding.TextUnmarshaler
94func (z *Int) UnmarshalText(input []byte) error {
95	return z.fromHex(string(input))
96}
97
98// SetFromBig converts a big.Int to Int and sets the value to z.
99// TODO: Ensure we have sufficient testing, esp for negative bigints.
100func (z *Int) SetFromBig(b *big.Int) bool {
101	z.Clear()
102	words := b.Bits()
103	overflow := len(words) > maxWords
104
105	switch maxWords { // Compile-time check.
106	case 4: // 64-bit architectures.
107		if len(words) > 0 {
108			z[0] = uint64(words[0])
109			if len(words) > 1 {
110				z[1] = uint64(words[1])
111				if len(words) > 2 {
112					z[2] = uint64(words[2])
113					if len(words) > 3 {
114						z[3] = uint64(words[3])
115					}
116				}
117			}
118		}
119	case 8: // 32-bit architectures.
120		numWords := len(words)
121		if overflow {
122			numWords = maxWords
123		}
124		for i := 0; i < numWords; i++ {
125			if i%2 == 0 {
126				z[i/2] = uint64(words[i])
127			} else {
128				z[i/2] |= uint64(words[i]) << 32
129			}
130		}
131	}
132
133	if b.Sign() == -1 {
134		z.Neg(z)
135	}
136	return overflow
137}
138
139// Format implements fmt.Formatter. It accepts the formats
140// 'b' (binary), 'o' (octal with 0 prefix), 'O' (octal with 0o prefix),
141// 'd' (decimal), 'x' (lowercase hexadecimal), and
142// 'X' (uppercase hexadecimal).
143// Also supported are the full suite of package fmt's format
144// flags for integral types, including '+' and ' ' for sign
145// control, '#' for leading zero in octal and for hexadecimal,
146// a leading "0x" or "0X" for "%#x" and "%#X" respectively,
147// specification of minimum digits precision, output field
148// width, space or zero padding, and '-' for left or right
149// justification.
150//
151func (z *Int) Format(s fmt.State, ch rune) {
152	z.ToBig().Format(s, ch)
153}
154
155// SetBytes8 is identical to SetBytes(in[:8]), but panics is input is too short
156func (z *Int) SetBytes8(in []byte) *Int {
157	_ = in[7] // bounds check hint to compiler; see golang.org/issue/14808
158	z[3], z[2], z[1] = 0, 0, 0
159	z[0] = binary.BigEndian.Uint64(in[0:8])
160	return z
161}
162
163// SetBytes16 is identical to SetBytes(in[:16]), but panics is input is too short
164func (z *Int) SetBytes16(in []byte) *Int {
165	_ = in[15] // bounds check hint to compiler; see golang.org/issue/14808
166	z[3], z[2] = 0, 0
167	z[1] = binary.BigEndian.Uint64(in[0:8])
168	z[0] = binary.BigEndian.Uint64(in[8:16])
169	return z
170}
171
172// SetBytes16 is identical to SetBytes(in[:24]), but panics is input is too short
173func (z *Int) SetBytes24(in []byte) *Int {
174	_ = in[23] // bounds check hint to compiler; see golang.org/issue/14808
175	z[3] = 0
176	z[2] = binary.BigEndian.Uint64(in[0:8])
177	z[1] = binary.BigEndian.Uint64(in[8:16])
178	z[0] = binary.BigEndian.Uint64(in[16:24])
179	return z
180}
181
182func (z *Int) SetBytes32(in []byte) *Int {
183	_ = in[31] // bounds check hint to compiler; see golang.org/issue/14808
184	z[3] = binary.BigEndian.Uint64(in[0:8])
185	z[2] = binary.BigEndian.Uint64(in[8:16])
186	z[1] = binary.BigEndian.Uint64(in[16:24])
187	z[0] = binary.BigEndian.Uint64(in[24:32])
188	return z
189}
190
191func (z *Int) SetBytes1(in []byte) *Int {
192	z[3], z[2], z[1] = 0, 0, 0
193	z[0] = uint64(in[0])
194	return z
195}
196
197func (z *Int) SetBytes9(in []byte) *Int {
198	_ = in[8] // bounds check hint to compiler; see golang.org/issue/14808
199	z[3], z[2] = 0, 0
200	z[1] = uint64(in[0])
201	z[0] = binary.BigEndian.Uint64(in[1:9])
202	return z
203}
204
205func (z *Int) SetBytes17(in []byte) *Int {
206	_ = in[16] // bounds check hint to compiler; see golang.org/issue/14808
207	z[3] = 0
208	z[2] = uint64(in[0])
209	z[1] = binary.BigEndian.Uint64(in[1:9])
210	z[0] = binary.BigEndian.Uint64(in[9:17])
211	return z
212}
213
214func (z *Int) SetBytes25(in []byte) *Int {
215	_ = in[24] // bounds check hint to compiler; see golang.org/issue/14808
216	z[3] = uint64(in[0])
217	z[2] = binary.BigEndian.Uint64(in[1:9])
218	z[1] = binary.BigEndian.Uint64(in[9:17])
219	z[0] = binary.BigEndian.Uint64(in[17:25])
220	return z
221}
222
223func (z *Int) SetBytes2(in []byte) *Int {
224	_ = in[1] // bounds check hint to compiler; see golang.org/issue/14808
225	z[3], z[2], z[1] = 0, 0, 0
226	z[0] = uint64(binary.BigEndian.Uint16(in[0:2]))
227	return z
228}
229
230func (z *Int) SetBytes10(in []byte) *Int {
231	_ = in[9] // bounds check hint to compiler; see golang.org/issue/14808
232	z[3], z[2] = 0, 0
233	z[1] = uint64(binary.BigEndian.Uint16(in[0:2]))
234	z[0] = binary.BigEndian.Uint64(in[2:10])
235	return z
236}
237
238func (z *Int) SetBytes18(in []byte) *Int {
239	_ = in[17] // bounds check hint to compiler; see golang.org/issue/14808
240	z[3] = 0
241	z[2] = uint64(binary.BigEndian.Uint16(in[0:2]))
242	z[1] = binary.BigEndian.Uint64(in[2:10])
243	z[0] = binary.BigEndian.Uint64(in[10:18])
244	return z
245}
246
247func (z *Int) SetBytes26(in []byte) *Int {
248	_ = in[25] // bounds check hint to compiler; see golang.org/issue/14808
249	z[3] = uint64(binary.BigEndian.Uint16(in[0:2]))
250	z[2] = binary.BigEndian.Uint64(in[2:10])
251	z[1] = binary.BigEndian.Uint64(in[10:18])
252	z[0] = binary.BigEndian.Uint64(in[18:26])
253	return z
254}
255
256func (z *Int) SetBytes3(in []byte) *Int {
257	_ = in[2] // bounds check hint to compiler; see golang.org/issue/14808
258	z[3], z[2], z[1] = 0, 0, 0
259	z[0] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
260	return z
261}
262
263func (z *Int) SetBytes11(in []byte) *Int {
264	_ = in[10] // bounds check hint to compiler; see golang.org/issue/14808
265	z[3], z[2] = 0, 0
266	z[1] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
267	z[0] = binary.BigEndian.Uint64(in[3:11])
268	return z
269}
270
271func (z *Int) SetBytes19(in []byte) *Int {
272	_ = in[18] // bounds check hint to compiler; see golang.org/issue/14808
273	z[3] = 0
274	z[2] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
275	z[1] = binary.BigEndian.Uint64(in[3:11])
276	z[0] = binary.BigEndian.Uint64(in[11:19])
277	return z
278}
279
280func (z *Int) SetBytes27(in []byte) *Int {
281	_ = in[26] // bounds check hint to compiler; see golang.org/issue/14808
282	z[3] = uint64(binary.BigEndian.Uint16(in[1:3])) | uint64(in[0])<<16
283	z[2] = binary.BigEndian.Uint64(in[3:11])
284	z[1] = binary.BigEndian.Uint64(in[11:19])
285	z[0] = binary.BigEndian.Uint64(in[19:27])
286	return z
287}
288
289func (z *Int) SetBytes4(in []byte) *Int {
290	_ = in[3] // bounds check hint to compiler; see golang.org/issue/14808
291	z[3], z[2], z[1] = 0, 0, 0
292	z[0] = uint64(binary.BigEndian.Uint32(in[0:4]))
293	return z
294}
295
296func (z *Int) SetBytes12(in []byte) *Int {
297	_ = in[11] // bounds check hint to compiler; see golang.org/issue/14808
298	z[3], z[2] = 0, 0
299	z[1] = uint64(binary.BigEndian.Uint32(in[0:4]))
300	z[0] = binary.BigEndian.Uint64(in[4:12])
301	return z
302}
303
304func (z *Int) SetBytes20(in []byte) *Int {
305	_ = in[19] // bounds check hint to compiler; see golang.org/issue/14808
306	z[3] = 0
307	z[2] = uint64(binary.BigEndian.Uint32(in[0:4]))
308	z[1] = binary.BigEndian.Uint64(in[4:12])
309	z[0] = binary.BigEndian.Uint64(in[12:20])
310	return z
311}
312
313func (z *Int) SetBytes28(in []byte) *Int {
314	_ = in[27] // bounds check hint to compiler; see golang.org/issue/14808
315	z[3] = uint64(binary.BigEndian.Uint32(in[0:4]))
316	z[2] = binary.BigEndian.Uint64(in[4:12])
317	z[1] = binary.BigEndian.Uint64(in[12:20])
318	z[0] = binary.BigEndian.Uint64(in[20:28])
319	return z
320}
321
322func (z *Int) SetBytes5(in []byte) *Int {
323	_ = in[4] // bounds check hint to compiler; see golang.org/issue/14808
324	z[3], z[2], z[1] = 0, 0, 0
325	z[0] = bigEndianUint40(in[0:5])
326	return z
327}
328
329func (z *Int) SetBytes13(in []byte) *Int {
330	_ = in[12] // bounds check hint to compiler; see golang.org/issue/14808
331	z[3], z[2] = 0, 0
332	z[1] = bigEndianUint40(in[0:5])
333	z[0] = binary.BigEndian.Uint64(in[5:13])
334	return z
335}
336
337func (z *Int) SetBytes21(in []byte) *Int {
338	_ = in[20] // bounds check hint to compiler; see golang.org/issue/14808
339	z[3] = 0
340	z[2] = bigEndianUint40(in[0:5])
341	z[1] = binary.BigEndian.Uint64(in[5:13])
342	z[0] = binary.BigEndian.Uint64(in[13:21])
343	return z
344}
345
346func (z *Int) SetBytes29(in []byte) *Int {
347	_ = in[23] // bounds check hint to compiler; see golang.org/issue/14808
348	z[3] = bigEndianUint40(in[0:5])
349	z[2] = binary.BigEndian.Uint64(in[5:13])
350	z[1] = binary.BigEndian.Uint64(in[13:21])
351	z[0] = binary.BigEndian.Uint64(in[21:29])
352	return z
353}
354
355func (z *Int) SetBytes6(in []byte) *Int {
356	_ = in[5] // bounds check hint to compiler; see golang.org/issue/14808
357	z[3], z[2], z[1] = 0, 0, 0
358	z[0] = bigEndianUint48(in[0:6])
359	return z
360}
361
362func (z *Int) SetBytes14(in []byte) *Int {
363	_ = in[13] // bounds check hint to compiler; see golang.org/issue/14808
364	z[3], z[2] = 0, 0
365	z[1] = bigEndianUint48(in[0:6])
366	z[0] = binary.BigEndian.Uint64(in[6:14])
367	return z
368}
369
370func (z *Int) SetBytes22(in []byte) *Int {
371	_ = in[21] // bounds check hint to compiler; see golang.org/issue/14808
372	z[3] = 0
373	z[2] = bigEndianUint48(in[0:6])
374	z[1] = binary.BigEndian.Uint64(in[6:14])
375	z[0] = binary.BigEndian.Uint64(in[14:22])
376	return z
377}
378
379func (z *Int) SetBytes30(in []byte) *Int {
380	_ = in[29] // bounds check hint to compiler; see golang.org/issue/14808
381	z[3] = bigEndianUint48(in[0:6])
382	z[2] = binary.BigEndian.Uint64(in[6:14])
383	z[1] = binary.BigEndian.Uint64(in[14:22])
384	z[0] = binary.BigEndian.Uint64(in[22:30])
385	return z
386}
387
388func (z *Int) SetBytes7(in []byte) *Int {
389	_ = in[6] // bounds check hint to compiler; see golang.org/issue/14808
390	z[3], z[2], z[1] = 0, 0, 0
391	z[0] = bigEndianUint56(in[0:7])
392	return z
393}
394
395func (z *Int) SetBytes15(in []byte) *Int {
396	_ = in[14] // bounds check hint to compiler; see golang.org/issue/14808
397	z[3], z[2] = 0, 0
398	z[1] = bigEndianUint56(in[0:7])
399	z[0] = binary.BigEndian.Uint64(in[7:15])
400	return z
401}
402
403func (z *Int) SetBytes23(in []byte) *Int {
404	_ = in[22] // bounds check hint to compiler; see golang.org/issue/14808
405	z[3] = 0
406	z[2] = bigEndianUint56(in[0:7])
407	z[1] = binary.BigEndian.Uint64(in[7:15])
408	z[0] = binary.BigEndian.Uint64(in[15:23])
409	return z
410}
411
412func (z *Int) SetBytes31(in []byte) *Int {
413	_ = in[30] // bounds check hint to compiler; see golang.org/issue/14808
414	z[3] = bigEndianUint56(in[0:7])
415	z[2] = binary.BigEndian.Uint64(in[7:15])
416	z[1] = binary.BigEndian.Uint64(in[15:23])
417	z[0] = binary.BigEndian.Uint64(in[23:31])
418	return z
419}
420
421// Utility methods that are "missing" among the bigEndian.UintXX methods.
422
423func bigEndianUint40(b []byte) uint64 {
424	_ = b[4] // bounds check hint to compiler; see golang.org/issue/14808
425	return uint64(b[4]) | uint64(b[3])<<8 | uint64(b[2])<<16 | uint64(b[1])<<24 |
426		uint64(b[0])<<32
427}
428
429func bigEndianUint48(b []byte) uint64 {
430	_ = b[5] // bounds check hint to compiler; see golang.org/issue/14808
431	return uint64(b[5]) | uint64(b[4])<<8 | uint64(b[3])<<16 | uint64(b[2])<<24 |
432		uint64(b[1])<<32 | uint64(b[0])<<40
433}
434
435func bigEndianUint56(b []byte) uint64 {
436	_ = b[6] // bounds check hint to compiler; see golang.org/issue/14808
437	return uint64(b[6]) | uint64(b[5])<<8 | uint64(b[4])<<16 | uint64(b[3])<<24 |
438		uint64(b[2])<<32 | uint64(b[1])<<40 | uint64(b[0])<<48
439}
440
441// EncodeRLP implements the rlp.Encoder interface from go-ethereum
442// and writes the RLP encoding of z to w.
443func (z *Int) EncodeRLP(w io.Writer) error {
444	if z == nil {
445		_, err := w.Write([]byte{0x80})
446		return err
447	}
448	nBits := z.BitLen()
449	if nBits == 0 {
450		_, err := w.Write([]byte{0x80})
451		return err
452	}
453	if nBits <= 7 {
454		_, err := w.Write([]byte{byte(z[0])})
455		return err
456	}
457	nBytes := byte((nBits + 7) / 8)
458	var b [33]byte
459	binary.BigEndian.PutUint64(b[1:9], z[3])
460	binary.BigEndian.PutUint64(b[9:17], z[2])
461	binary.BigEndian.PutUint64(b[17:25], z[1])
462	binary.BigEndian.PutUint64(b[25:33], z[0])
463	b[32-nBytes] = 0x80 + nBytes
464	_, err := w.Write(b[32-nBytes:])
465	return err
466}
467
468// MarshalText implements encoding.TextMarshaler
469func (z *Int) MarshalText() ([]byte, error) {
470	return []byte(z.Hex()), nil
471}
472
473// UnmarshalJSON implements json.Unmarshaler.
474func (z *Int) UnmarshalJSON(input []byte) error {
475	if len(input) < 2 || input[0] != '"' || input[len(input)-1] != '"' {
476		return ErrNonString
477	}
478	return z.UnmarshalText(input[1 : len(input)-1])
479}
480
481// String returns the hex encoding of b.
482func (z *Int) String() string {
483	return z.Hex()
484}
485
486const (
487	hextable  = "0123456789abcdef"
488	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"
489	badNibble = 0xff
490)
491
492// Hex encodes z in 0x-prefixed hexadecimal form.
493func (z *Int) Hex() string {
494	// This implementation is not optimal, it allocates a full
495	// 66-byte output buffer which it fills. It could instead allocate a smaller
496	// buffer, and omit the final crop-stage.
497	output := make([]byte, 66)
498	nibbles := (z.BitLen() + 3) / 4 // nibbles [0,64]
499	if nibbles == 0 {
500		nibbles = 1
501	}
502	// Start with the most significant
503	zWord := (nibbles - 1) / 16
504	for i := zWord; i >= 0; i-- {
505		off := (3 - i) * 16
506		output[off+2] = hextable[byte(z[i]>>60)&0xf]
507		output[off+3] = hextable[byte(z[i]>>56)&0xf]
508		output[off+4] = hextable[byte(z[i]>>52)&0xf]
509		output[off+5] = hextable[byte(z[i]>>48)&0xf]
510		output[off+6] = hextable[byte(z[i]>>44)&0xf]
511		output[off+7] = hextable[byte(z[i]>>40)&0xf]
512		output[off+8] = hextable[byte(z[i]>>36)&0xf]
513		output[off+9] = hextable[byte(z[i]>>32)&0xf]
514		output[off+10] = hextable[byte(z[i]>>28)&0xf]
515		output[off+11] = hextable[byte(z[i]>>24)&0xf]
516		output[off+12] = hextable[byte(z[i]>>20)&0xf]
517		output[off+13] = hextable[byte(z[i]>>16)&0xf]
518		output[off+14] = hextable[byte(z[i]>>12)&0xf]
519		output[off+15] = hextable[byte(z[i]>>8)&0xf]
520		output[off+16] = hextable[byte(z[i]>>4)&0xf]
521		output[off+17] = hextable[byte(z[i]&0xF)&0xf]
522	}
523	output[64-nibbles] = '0'
524	output[65-nibbles] = 'x'
525	return string(output[64-nibbles:])
526}
527
528var (
529	ErrEmptyString   = errors.New("empty hex string")
530	ErrSyntax        = errors.New("invalid hex string")
531	ErrMissingPrefix = errors.New("hex string without 0x prefix")
532	ErrEmptyNumber   = errors.New("hex string \"0x\"")
533	ErrLeadingZero   = errors.New("hex number with leading zero digits")
534	ErrBig256Range   = errors.New("hex number > 256 bits")
535	ErrNonString     = errors.New("non-string")
536)
537
538func checkNumberS(input string) error {
539	l := len(input)
540	if l == 0 {
541		return ErrEmptyString
542	}
543	if l < 2 || input[0] != '0' ||
544		(input[1] != 'x' && input[1] != 'X') {
545		return ErrMissingPrefix
546	}
547	if l == 2 {
548		return ErrEmptyNumber
549	}
550	if len(input) > 3 && input[2] == '0' {
551		return ErrLeadingZero
552	}
553	return nil
554}
555