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