diff options
author | Felix Lange <fjl@users.noreply.github.com> | 2017-02-27 05:21:51 +0800 |
---|---|---|
committer | Jeffrey Wilcke <jeffrey@ethereum.org> | 2017-02-27 05:21:51 +0800 |
commit | 5c8fe28b725bd9b128edceae3215132ea741641b (patch) | |
tree | 4bcbfeb1a21536edbba06d1715752999faa7f085 /common | |
parent | 50ee279f2585e9e2eee30f0e1d4a3bf5f781bd72 (diff) | |
download | go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.tar go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.tar.gz go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.tar.bz2 go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.tar.lz go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.tar.xz go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.tar.zst go-tangerine-5c8fe28b725bd9b128edceae3215132ea741641b.zip |
common: move big integer math to common/math (#3699)
* common: remove CurrencyToString
Move denomination values to params instead.
* common: delete dead code
* common: move big integer operations to common/math
This commit consolidates all big integer operations into common/math and
adds tests and documentation.
There should be no change in semantics for BigPow, BigMin, BigMax, S256,
U256, Exp and their behaviour is now locked in by tests.
The BigD, BytesToBig and Bytes2Big functions don't provide additional
value, all uses are replaced by new(big.Int).SetBytes().
BigToBytes is now called PaddedBigBytes, its minimum output size
parameter is now specified as the number of bytes instead of bits. The
single use of this function is in the EVM's MSTORE instruction.
Big and String2Big are replaced by ParseBig, which is slightly stricter.
It previously accepted leading zeros for hexadecimal inputs but treated
decimal inputs as octal if a leading zero digit was present.
ParseUint64 is used in places where String2Big was used to decode a
uint64.
The new functions MustParseBig and MustParseUint64 are now used in many
places where parsing errors were previously ignored.
* common: delete unused big integer variables
* accounts/abi: replace uses of BytesToBig with use of encoding/binary
* common: remove BytesToBig
* common: remove Bytes2Big
* common: remove BigTrue
* cmd/utils: add BigFlag and use it for error-checked integer flags
While here, remove environment variable processing for DirectoryFlag
because we don't use it.
* core: add missing error checks in genesis block parser
* common: remove String2Big
* cmd/evm: use utils.BigFlag
* common/math: check for 256 bit overflow in ParseBig
This is supposed to prevent silent overflow/truncation of values in the
genesis block JSON. Without this check, a genesis block that set a
balance larger than 256 bits would lead to weird behaviour in the VM.
* cmd/utils: fixup import
Diffstat (limited to 'common')
-rw-r--r-- | common/.gitignore | 12 | ||||
-rw-r--r-- | common/.travis.yml | 3 | ||||
-rw-r--r-- | common/README.md | 140 | ||||
-rw-r--r-- | common/big.go | 140 | ||||
-rw-r--r-- | common/big_test.go | 89 | ||||
-rw-r--r-- | common/bytes.go | 155 | ||||
-rw-r--r-- | common/bytes_test.go | 108 | ||||
-rw-r--r-- | common/icap.go | 190 | ||||
-rw-r--r-- | common/icap_test.go | 91 | ||||
-rw-r--r-- | common/list.go | 97 | ||||
-rw-r--r-- | common/math/big.go | 143 | ||||
-rw-r--r-- | common/math/big_test.go | 196 | ||||
-rw-r--r-- | common/math/dist.go | 96 | ||||
-rw-r--r-- | common/math/dist_test.go | 82 | ||||
-rw-r--r-- | common/math/exp.go | 47 | ||||
-rw-r--r-- | common/math/integer.go | 65 | ||||
-rw-r--r-- | common/math/integer_test.go | 75 | ||||
-rw-r--r-- | common/size.go | 52 | ||||
-rw-r--r-- | common/size_test.go | 53 | ||||
-rw-r--r-- | common/types.go | 4 | ||||
-rw-r--r-- | common/types_template.go | 2 |
21 files changed, 494 insertions, 1346 deletions
diff --git a/common/.gitignore b/common/.gitignore deleted file mode 100644 index f725d58d1..000000000 --- a/common/.gitignore +++ /dev/null @@ -1,12 +0,0 @@ -# See http://help.github.com/ignore-files/ for more about ignoring files. -# -# If you find yourself ignoring temporary files generated by your text editor -# or operating system, you probably want to add a global ignore instead: -# git config --global core.excludesfile ~/.gitignore_global - -/tmp -*/**/*un~ -*un~ -.DS_Store -*/**/.DS_Store - diff --git a/common/.travis.yml b/common/.travis.yml deleted file mode 100644 index 69359072d..000000000 --- a/common/.travis.yml +++ /dev/null @@ -1,3 +0,0 @@ -language: go -go: - - 1.2 diff --git a/common/README.md b/common/README.md deleted file mode 100644 index adea022b7..000000000 --- a/common/README.md +++ /dev/null @@ -1,140 +0,0 @@ -# common - -[![Build -Status](https://travis-ci.org/ethereum/go-ethereum.png?branch=master)](https://travis-ci.org/ethereum/go-ethereum) - -The common package contains the ethereum utility library. - -# Installation - -As a subdirectory the main go-ethereum repository, you get it with -`go get github.com/ethereum/go-ethereum`. - -# Usage - -## RLP (Recursive Linear Prefix) Encoding - -RLP Encoding is an encoding scheme used by the Ethereum project. It -encodes any native value or list to a string. - -More in depth information about the encoding scheme see the -[Wiki](http://wiki.ethereum.org/index.php/RLP) article. - -```go -rlp := common.Encode("doge") -fmt.Printf("%q\n", rlp) // => "\0x83dog" - -rlp = common.Encode([]interface{}{"dog", "cat"}) -fmt.Printf("%q\n", rlp) // => "\0xc8\0x83dog\0x83cat" -decoded := common.Decode(rlp) -fmt.Println(decoded) // => ["dog" "cat"] -``` - -## Patricia Trie - -Patricie Tree is a merkle trie used by the Ethereum project. - -More in depth information about the (modified) Patricia Trie can be -found on the [Wiki](http://wiki.ethereum.org/index.php/Patricia_Tree). - -The patricia trie uses a db as backend and could be anything as long as -it satisfies the Database interface found in `common/db.go`. - -```go -db := NewDatabase() - -// db, root -trie := common.NewTrie(db, "") - -trie.Put("puppy", "dog") -trie.Put("horse", "stallion") -trie.Put("do", "verb") -trie.Put("doge", "coin") - -// Look up the key "do" in the trie -out := trie.Get("do") -fmt.Println(out) // => verb - -trie.Delete("puppy") -``` - -The patricia trie, in combination with RLP, provides a robust, -cryptographically authenticated data structure that can be used to store -all (key, value) bindings. - -```go -// ... Create db/trie - -// Note that RLP uses interface slices as list -value := common.Encode([]interface{}{"one", 2, "three", []interface{}{42}}) -// Store the RLP encoded value of the list -trie.Put("mykey", value) -``` - -## Value - -Value is a Generic Value which is used in combination with RLP data or -`([])interface{}` structures. It may serve as a bridge between RLP data -and actual real values and takes care of all the type checking and -casting. Unlike Go's `reflect.Value` it does not panic if it's unable to -cast to the requested value. It simple returns the base value of that -type (e.g. `Slice()` returns []interface{}, `Uint()` return 0, etc). - -### Creating a new Value - -`NewEmptyValue()` returns a new \*Value with it's initial value set to a -`[]interface{}` - -`AppendList()` appends a list to the current value. - -`Append(v)` appends the value (v) to the current value/list. - -```go -val := common.NewEmptyValue().Append(1).Append("2") -val.AppendList().Append(3) -``` - -### Retrieving values - -`Get(i)` returns the `i` item in the list. - -`Uint()` returns the value as an unsigned int64. - -`Slice()` returns the value as a interface slice. - -`Str()` returns the value as a string. - -`Bytes()` returns the value as a byte slice. - -`Len()` assumes current to be a slice and returns its length. - -`Byte()` returns the value as a single byte. - -```go -val := common.NewValue([]interface{}{1,"2",[]interface{}{3}}) -val.Get(0).Uint() // => 1 -val.Get(1).Str() // => "2" -s := val.Get(2) // => Value([]interface{}{3}) -s.Get(0).Uint() // => 3 -``` - -## Decoding - -Decoding streams of RLP data is simplified - -```go -val := common.NewValueFromBytes(rlpData) -val.Get(0).Uint() -``` - -## Encoding - -Encoding from Value to RLP is done with the `Encode` method. The -underlying value can be anything RLP can encode (int, str, lists, bytes) - -```go -val := common.NewValue([]interface{}{1,"2",[]interface{}{3}}) -rlp := val.Encode() -// Store the rlp data -Store(rlp) -``` diff --git a/common/big.go b/common/big.go index 4ce87ee0c..b552608bc 100644 --- a/common/big.go +++ b/common/big.go @@ -20,137 +20,11 @@ import "math/big" // Common big integers often used var ( - Big1 = big.NewInt(1) - Big2 = big.NewInt(2) - Big3 = big.NewInt(3) - Big0 = big.NewInt(0) - BigTrue = Big1 - BigFalse = Big0 - Big32 = big.NewInt(32) - Big36 = big.NewInt(36) - Big97 = big.NewInt(97) - Big98 = big.NewInt(98) - Big256 = big.NewInt(0xff) - Big257 = big.NewInt(257) - MaxBig = String2Big("0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff") + Big1 = big.NewInt(1) + Big2 = big.NewInt(2) + Big3 = big.NewInt(3) + Big0 = big.NewInt(0) + Big32 = big.NewInt(32) + Big256 = big.NewInt(0xff) + Big257 = big.NewInt(257) ) - -// Big pow -// -// Returns the power of two big integers -func BigPow(a, b int) *big.Int { - c := new(big.Int) - c.Exp(big.NewInt(int64(a)), big.NewInt(int64(b)), big.NewInt(0)) - - return c -} - -// Big -// -// Shortcut for new(big.Int).SetString(..., 0) -func Big(num string) *big.Int { - n := new(big.Int) - n.SetString(num, 0) - - return n -} - -// Bytes2Big -// -func BytesToBig(data []byte) *big.Int { - n := new(big.Int) - n.SetBytes(data) - - return n -} -func Bytes2Big(data []byte) *big.Int { return BytesToBig(data) } -func BigD(data []byte) *big.Int { return BytesToBig(data) } - -func String2Big(num string) *big.Int { - n := new(big.Int) - n.SetString(num, 0) - return n -} - -func BitTest(num *big.Int, i int) bool { - return num.Bit(i) > 0 -} - -// To256 -// -// "cast" the big int to a 256 big int (i.e., limit to) -var tt256 = new(big.Int).Lsh(big.NewInt(1), 256) -var tt256m1 = new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 256), big.NewInt(1)) -var tt255 = new(big.Int).Lsh(big.NewInt(1), 255) - -func U256(x *big.Int) *big.Int { - //if x.Cmp(Big0) < 0 { - // return new(big.Int).Add(tt256, x) - // } - - x.And(x, tt256m1) - - return x -} - -func S256(x *big.Int) *big.Int { - if x.Cmp(tt255) < 0 { - return x - } else { - // We don't want to modify x, ever - return new(big.Int).Sub(x, tt256) - } -} - -func FirstBitSet(v *big.Int) int { - for i := 0; i < v.BitLen(); i++ { - if v.Bit(i) > 0 { - return i - } - } - - return v.BitLen() -} - -// Big to bytes -// -// Returns the bytes of a big integer with the size specified by **base** -// Attempts to pad the byte array with zeros. -func BigToBytes(num *big.Int, base int) []byte { - ret := make([]byte, base/8) - - if len(num.Bytes()) > base/8 { - return num.Bytes() - } - - return append(ret[:len(ret)-len(num.Bytes())], num.Bytes()...) -} - -// Big copy -// -// Creates a copy of the given big integer -func BigCopy(src *big.Int) *big.Int { - return new(big.Int).Set(src) -} - -// Big max -// -// Returns the maximum size big integer -func BigMax(x, y *big.Int) *big.Int { - if x.Cmp(y) < 0 { - return y - } - - return x -} - -// Big min -// -// Returns the minimum size big integer -func BigMin(x, y *big.Int) *big.Int { - if x.Cmp(y) > 0 { - return y - } - - return x -} diff --git a/common/big_test.go b/common/big_test.go deleted file mode 100644 index 4d04a8db3..000000000 --- a/common/big_test.go +++ /dev/null @@ -1,89 +0,0 @@ -// Copyright 2014 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -package common - -import ( - "bytes" - "testing" -) - -func TestMisc(t *testing.T) { - a := Big("10") - b := Big("57896044618658097711785492504343953926634992332820282019728792003956564819968") - c := []byte{1, 2, 3, 4} - z := BitTest(a, 1) - - if !z { - t.Error("Expected true got", z) - } - - U256(a) - S256(a) - - U256(b) - S256(b) - - BigD(c) -} - -func TestBigMax(t *testing.T) { - a := Big("10") - b := Big("5") - - max1 := BigMax(a, b) - if max1 != a { - t.Errorf("Expected %d got %d", a, max1) - } - - max2 := BigMax(b, a) - if max2 != a { - t.Errorf("Expected %d got %d", a, max2) - } -} - -func TestBigMin(t *testing.T) { - a := Big("10") - b := Big("5") - - min1 := BigMin(a, b) - if min1 != b { - t.Errorf("Expected %d got %d", b, min1) - } - - min2 := BigMin(b, a) - if min2 != b { - t.Errorf("Expected %d got %d", b, min2) - } -} - -func TestBigCopy(t *testing.T) { - a := Big("10") - b := BigCopy(a) - c := Big("1000000000000") - y := BigToBytes(b, 16) - ybytes := []byte{0, 10} - z := BigToBytes(c, 16) - zbytes := []byte{232, 212, 165, 16, 0} - - if !bytes.Equal(y, ybytes) { - t.Error("Got", ybytes) - } - - if !bytes.Equal(z, zbytes) { - t.Error("Got", zbytes) - } -} diff --git a/common/bytes.go b/common/bytes.go index cbceea8b5..0342083a1 100644 --- a/common/bytes.go +++ b/common/bytes.go @@ -18,12 +18,7 @@ package common import ( - "bytes" - "encoding/binary" "encoding/hex" - "fmt" - "math/big" - "strings" ) func ToHex(b []byte) string { @@ -48,65 +43,6 @@ func FromHex(s string) []byte { return nil } -// Number to bytes -// -// Returns the number in bytes with the specified base -func NumberToBytes(num interface{}, bits int) []byte { - buf := new(bytes.Buffer) - err := binary.Write(buf, binary.BigEndian, num) - if err != nil { - fmt.Println("NumberToBytes failed:", err) - } - - return buf.Bytes()[buf.Len()-(bits/8):] -} - -// Bytes to number -// -// Attempts to cast a byte slice to a unsigned integer -func BytesToNumber(b []byte) uint64 { - var number uint64 - - // Make sure the buffer is 64bits - data := make([]byte, 8) - data = append(data[:len(b)], b...) - - buf := bytes.NewReader(data) - err := binary.Read(buf, binary.BigEndian, &number) - if err != nil { - fmt.Println("BytesToNumber failed:", err) - } - - return number -} - -// Read variable int -// -// Read a variable length number in big endian byte order -func ReadVarInt(buff []byte) (ret uint64) { - switch l := len(buff); { - case l > 4: - d := LeftPadBytes(buff, 8) - binary.Read(bytes.NewReader(d), binary.BigEndian, &ret) - case l > 2: - var num uint32 - d := LeftPadBytes(buff, 4) - binary.Read(bytes.NewReader(d), binary.BigEndian, &num) - ret = uint64(num) - case l > 1: - var num uint16 - d := LeftPadBytes(buff, 2) - binary.Read(bytes.NewReader(d), binary.BigEndian, &num) - ret = uint64(num) - default: - var num uint8 - binary.Read(bytes.NewReader(buff), binary.BigEndian, &num) - ret = uint64(num) - } - - return -} - // Copy bytes // // Returns an exact copy of the provided bytes @@ -152,53 +88,6 @@ func Hex2BytesFixed(str string, flen int) []byte { } } -func StringToByteFunc(str string, cb func(str string) []byte) (ret []byte) { - if len(str) > 1 && str[0:2] == "0x" && !strings.Contains(str, "\n") { - ret = Hex2Bytes(str[2:]) - } else { - ret = cb(str) - } - - return -} - -func FormatData(data string) []byte { - if len(data) == 0 { - return nil - } - // Simple stupid - d := new(big.Int) - if data[0:1] == "\"" && data[len(data)-1:] == "\"" { - return RightPadBytes([]byte(data[1:len(data)-1]), 32) - } else if len(data) > 1 && data[:2] == "0x" { - d.SetBytes(Hex2Bytes(data[2:])) - } else { - d.SetString(data, 0) - } - - return BigToBytes(d, 256) -} - -func ParseData(data ...interface{}) (ret []byte) { - for _, item := range data { - switch t := item.(type) { - case string: - var str []byte - if IsHex(t) { - str = Hex2Bytes(t[2:]) - } else { - str = []byte(t) - } - - ret = append(ret, RightPadBytes(str, 32)...) - case []byte: - ret = append(ret, LeftPadBytes(t, 32)...) - } - } - - return -} - func RightPadBytes(slice []byte, l int) []byte { if l < len(slice) { return slice @@ -220,47 +109,3 @@ func LeftPadBytes(slice []byte, l int) []byte { return padded } - -func LeftPadString(str string, l int) string { - if l < len(str) { - return str - } - - zeros := Bytes2Hex(make([]byte, (l-len(str))/2)) - - return zeros + str - -} - -func RightPadString(str string, l int) string { - if l < len(str) { - return str - } - - zeros := Bytes2Hex(make([]byte, (l-len(str))/2)) - - return str + zeros - -} - -func ToAddress(slice []byte) (addr []byte) { - if len(slice) < 20 { - addr = LeftPadBytes(slice, 20) - } else if len(slice) > 20 { - addr = slice[len(slice)-20:] - } else { - addr = slice - } - - addr = CopyBytes(addr) - - return -} - -func ByteSliceToInterface(slice [][]byte) (ret []interface{}) { - for _, i := range slice { - ret = append(ret, i) - } - - return -} diff --git a/common/bytes_test.go b/common/bytes_test.go index 98d402c48..fc164b13d 100644 --- a/common/bytes_test.go +++ b/common/bytes_test.go @@ -27,54 +27,6 @@ type BytesSuite struct{} var _ = checker.Suite(&BytesSuite{}) -func (s *BytesSuite) TestNumberToBytes(c *checker.C) { - // data1 := int(1) - // res1 := NumberToBytes(data1, 16) - // c.Check(res1, checker.Panics) - - var data2 float64 = 3.141592653 - exp2 := []byte{0xe9, 0x38} - res2 := NumberToBytes(data2, 16) - c.Assert(res2, checker.DeepEquals, exp2) -} - -func (s *BytesSuite) TestBytesToNumber(c *checker.C) { - datasmall := []byte{0xe9, 0x38, 0xe9, 0x38} - datalarge := []byte{0xe9, 0x38, 0xe9, 0x38, 0xe9, 0x38, 0xe9, 0x38} - - var expsmall uint64 = 0xe938e938 - var explarge uint64 = 0x0 - - ressmall := BytesToNumber(datasmall) - reslarge := BytesToNumber(datalarge) - - c.Assert(ressmall, checker.Equals, expsmall) - c.Assert(reslarge, checker.Equals, explarge) - -} - -func (s *BytesSuite) TestReadVarInt(c *checker.C) { - data8 := []byte{1, 2, 3, 4, 5, 6, 7, 8} - data4 := []byte{1, 2, 3, 4} - data2 := []byte{1, 2} - data1 := []byte{1} - - exp8 := uint64(72623859790382856) - exp4 := uint64(16909060) - exp2 := uint64(258) - exp1 := uint64(1) - - res8 := ReadVarInt(data8) - res4 := ReadVarInt(data4) - res2 := ReadVarInt(data2) - res1 := ReadVarInt(data1) - - c.Assert(res8, checker.Equals, exp8) - c.Assert(res4, checker.Equals, exp4) - c.Assert(res2, checker.Equals, exp2) - c.Assert(res1, checker.Equals, exp1) -} - func (s *BytesSuite) TestCopyBytes(c *checker.C) { data1 := []byte{1, 2, 3, 4} exp1 := []byte{1, 2, 3, 4} @@ -95,22 +47,6 @@ func (s *BytesSuite) TestIsHex(c *checker.C) { } -func (s *BytesSuite) TestParseDataString(c *checker.C) { - res1 := ParseData("hello", "world", "0x0106") - data := "68656c6c6f000000000000000000000000000000000000000000000000000000776f726c640000000000000000000000000000000000000000000000000000000106000000000000000000000000000000000000000000000000000000000000" - exp1 := Hex2Bytes(data) - c.Assert(res1, checker.DeepEquals, exp1) -} - -func (s *BytesSuite) TestParseDataBytes(c *checker.C) { - data1 := []byte{232, 212, 165, 16, 0} - exp1 := []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 232, 212, 165, 16, 0} - - res1 := ParseData(data1) - c.Assert(res1, checker.DeepEquals, exp1) - -} - func (s *BytesSuite) TestLeftPadBytes(c *checker.C) { val1 := []byte{1, 2, 3, 4} exp1 := []byte{0, 0, 0, 0, 1, 2, 3, 4} @@ -122,28 +58,6 @@ func (s *BytesSuite) TestLeftPadBytes(c *checker.C) { c.Assert(res2, checker.DeepEquals, val1) } -func (s *BytesSuite) TestFormatData(c *checker.C) { - data1 := "" - data2 := "0xa9e67e00" - data3 := "a9e67e" - data4 := "\"a9e67e00\"" - - // exp1 := []byte{} - exp2 := []byte{00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 0xa9, 0xe6, 0x7e, 00} - exp3 := []byte{00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00} - exp4 := []byte{0x61, 0x39, 0x65, 0x36, 0x37, 0x65, 0x30, 0x30, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00, 00} - - res1 := FormatData(data1) - res2 := FormatData(data2) - res3 := FormatData(data3) - res4 := FormatData(data4) - - c.Assert(res1, checker.IsNil) - c.Assert(res2, checker.DeepEquals, exp2) - c.Assert(res3, checker.DeepEquals, exp3) - c.Assert(res4, checker.DeepEquals, exp4) -} - func (s *BytesSuite) TestRightPadBytes(c *checker.C) { val := []byte{1, 2, 3, 4} exp := []byte{1, 2, 3, 4, 0, 0, 0, 0} @@ -155,28 +69,6 @@ func (s *BytesSuite) TestRightPadBytes(c *checker.C) { c.Assert(resshrt, checker.DeepEquals, val) } -func (s *BytesSuite) TestLeftPadString(c *checker.C) { - val := "test" - exp := "\x30\x30\x30\x30" + val - - resstd := LeftPadString(val, 8) - resshrt := LeftPadString(val, 2) - - c.Assert(resstd, checker.Equals, exp) - c.Assert(resshrt, checker.Equals, val) -} - -func (s *BytesSuite) TestRightPadString(c *checker.C) { - val := "test" - exp := val + "\x30\x30\x30\x30" - - resstd := RightPadString(val, 8) - resshrt := RightPadString(val, 2) - - c.Assert(resstd, checker.Equals, exp) - c.Assert(resshrt, checker.Equals, val) -} - func TestFromHex(t *testing.T) { input := "0x01" expected := []byte{1} diff --git a/common/icap.go b/common/icap.go deleted file mode 100644 index a36e669b3..000000000 --- a/common/icap.go +++ /dev/null @@ -1,190 +0,0 @@ -// Copyright 2015 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -// Spec at https://github.com/ethereum/wiki/wiki/ICAP:-Inter-exchange-Client-Address-Protocol - -package common - -import ( - "errors" - "math/big" - "strconv" - "strings" -) - -var ( - Base36Chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" - ICAPLengthError = errors.New("Invalid ICAP length") - ICAPEncodingError = errors.New("Invalid ICAP encoding") - ICAPChecksumError = errors.New("Invalid ICAP checksum") - ICAPCountryCodeError = errors.New("Invalid ICAP country code") - ICAPAssetIdentError = errors.New("Invalid ICAP asset identifier") - ICAPInstCodeError = errors.New("Invalid ICAP institution code") - ICAPClientIdentError = errors.New("Invalid ICAP client identifier") -) - -func ICAPToAddress(s string) (Address, error) { - switch len(s) { - case 35: // "XE" + 2 digit checksum + 31 base-36 chars of address - return parseICAP(s) - case 34: // "XE" + 2 digit checksum + 30 base-36 chars of address - return parseICAP(s) - case 20: // "XE" + 2 digit checksum + 3-char asset identifier + - // 4-char institution identifier + 9-char institution client identifier - return parseIndirectICAP(s) - default: - return Address{}, ICAPLengthError - } -} - -func parseICAP(s string) (Address, error) { - if !strings.HasPrefix(s, "XE") { - return Address{}, ICAPCountryCodeError - } - if err := validCheckSum(s); err != nil { - return Address{}, err - } - // checksum is ISO13616, Ethereum address is base-36 - bigAddr, _ := new(big.Int).SetString(s[4:], 36) - return BigToAddress(bigAddr), nil -} - -func parseIndirectICAP(s string) (Address, error) { - if !strings.HasPrefix(s, "XE") { - return Address{}, ICAPCountryCodeError - } - if s[4:7] != "ETH" { - return Address{}, ICAPAssetIdentError - } - if err := validCheckSum(s); err != nil { - return Address{}, err - } - // TODO: integrate with ICAP namereg - return Address{}, errors.New("not implemented") -} - -func AddressToICAP(a Address) (string, error) { - enc := base36Encode(a.Big()) - // zero padd encoded address to Direct ICAP length if needed - if len(enc) < 30 { - enc = join(strings.Repeat("0", 30-len(enc)), enc) - } - icap := join("XE", checkDigits(enc), enc) - return icap, nil -} - -// TODO: integrate with ICAP namereg when it's available -func AddressToIndirectICAP(a Address, instCode string) (string, error) { - // return addressToIndirectICAP(a, instCode) - return "", errors.New("not implemented") -} - -func addressToIndirectICAP(a Address, instCode string) (string, error) { - // TODO: add addressToClientIdent which grabs client ident from ICAP namereg - //clientIdent := addressToClientIdent(a) - clientIdent := "todo" - return clientIdentToIndirectICAP(instCode, clientIdent) -} - -func clientIdentToIndirectICAP(instCode, clientIdent string) (string, error) { - if len(instCode) != 4 || !validBase36(instCode) { - return "", ICAPInstCodeError - } - if len(clientIdent) != 9 || !validBase36(instCode) { - return "", ICAPClientIdentError - } - - // currently ETH is only valid asset identifier - s := join("ETH", instCode, clientIdent) - return join("XE", checkDigits(s), s), nil -} - -// https://en.wikipedia.org/wiki/International_Bank_Account_Number#Validating_the_IBAN -func validCheckSum(s string) error { - s = join(s[4:], s[:4]) - expanded, err := iso13616Expand(s) - if err != nil { - return err - } - checkSumNum, _ := new(big.Int).SetString(expanded, 10) - if checkSumNum.Mod(checkSumNum, Big97).Cmp(Big1) != 0 { - return ICAPChecksumError - } - return nil -} - -func checkDigits(s string) string { - expanded, _ := iso13616Expand(strings.Join([]string{s, "XE00"}, "")) - num, _ := new(big.Int).SetString(expanded, 10) - num.Sub(Big98, num.Mod(num, Big97)) - - checkDigits := num.String() - // zero padd checksum - if len(checkDigits) == 1 { - checkDigits = join("0", checkDigits) - } - return checkDigits -} - -// not base-36, but expansion to decimal literal: A = 10, B = 11, ... Z = 35 -func iso13616Expand(s string) (string, error) { - var parts []string - if !validBase36(s) { - return "", ICAPEncodingError - } - for _, c := range s { - i := uint64(c) - if i >= 65 { - parts = append(parts, strconv.FormatUint(uint64(c)-55, 10)) - } else { - parts = append(parts, string(c)) - } - } - return join(parts...), nil -} - -func base36Encode(i *big.Int) string { - var chars []rune - x := new(big.Int) - for { - x.Mod(i, Big36) - chars = append(chars, rune(Base36Chars[x.Uint64()])) - i.Div(i, Big36) - if i.Cmp(Big0) == 0 { - break - } - } - // reverse slice - for i, j := 0, len(chars)-1; i < j; i, j = i+1, j-1 { - chars[i], chars[j] = chars[j], chars[i] - } - return string(chars) -} - -func validBase36(s string) bool { - for _, c := range s { - i := uint64(c) - // 0-9 or A-Z - if i < 48 || (i > 57 && i < 65) || i > 90 { - return false - } - } - return true -} - -func join(s ...string) string { - return strings.Join(s, "") -} diff --git a/common/icap_test.go b/common/icap_test.go deleted file mode 100644 index 6306686d1..000000000 --- a/common/icap_test.go +++ /dev/null @@ -1,91 +0,0 @@ -// Copyright 2015 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -package common - -import "testing" - -/* More test vectors: -https://github.com/ethereum/web3.js/blob/master/test/iban.fromAddress.js -https://github.com/ethereum/web3.js/blob/master/test/iban.toAddress.js -https://github.com/ethereum/web3.js/blob/master/test/iban.isValid.js -https://github.com/ethereum/libethereum/blob/develop/test/libethcore/icap.cpp -*/ - -type icapTest struct { - name string - addr string - icap string -} - -var icapOKTests = []icapTest{ - {"Direct1", "0x52dc504a422f0e2a9e7632a34a50f1a82f8224c7", "XE499OG1EH8ZZI0KXC6N83EKGT1BM97P2O7"}, - {"Direct2", "0x11c5496aee77c1ba1f0854206a26dda82a81d6d8", "XE1222Q908LN1QBBU6XUQSO1OHWJIOS46OO"}, - {"DirectZeroPrefix", "0x00c5496aee77c1ba1f0854206a26dda82a81d6d8", "XE7338O073KYGTWWZN0F2WZ0R8PX5ZPPZS"}, - {"DirectDoubleZeroPrefix", "0x0000a5327eab78357cbf2ae8f3d49fd9d90c7d22", "XE0600DQK33XDTYUCRI0KYM5ELAKXDWWF6"}, -} - -var icapInvalidTests = []icapTest{ - {"DirectInvalidCheckSum", "", "XE7438O073KYGTWWZN0F2WZ0R8PX5ZPPZS"}, - {"DirectInvalidCountryCode", "", "XD7338O073KYGTWWZN0F2WZ0R8PX5ZPPZS"}, - {"DirectInvalidLength36", "", "XE499OG1EH8ZZI0KXC6N83EKGT1BM97P2O77"}, - {"DirectInvalidLength33", "", "XE499OG1EH8ZZI0KXC6N83EKGT1BM97P2"}, - - {"IndirectInvalidCheckSum", "", "XE35ETHXREGGOPHERSSS"}, - {"IndirectInvalidAssetIdentifier", "", "XE34ETHXREGGOPHERSSS"}, - {"IndirectInvalidLength19", "", "XE34ETHXREGGOPHERSS"}, - {"IndirectInvalidLength21", "", "XE34ETHXREGGOPHERSSSS"}, -} - -func TestICAPOK(t *testing.T) { - for _, test := range icapOKTests { - decodeEncodeTest(HexToAddress(test.addr), test.icap, t) - } -} - -func TestICAPInvalid(t *testing.T) { - for _, test := range icapInvalidTests { - failedDecodingTest(test.icap, t) - } -} - -func decodeEncodeTest(addr0 Address, icap0 string, t *testing.T) { - icap1, err := AddressToICAP(addr0) - if err != nil { - t.Errorf("ICAP encoding failed: %s", err) - } - if icap1 != icap0 { - t.Errorf("ICAP mismatch: have: %s want: %s", icap1, icap0) - } - - addr1, err := ICAPToAddress(icap0) - if err != nil { - t.Errorf("ICAP decoding failed: %s", err) - } - if addr1 != addr0 { - t.Errorf("Address mismatch: have: %x want: %x", addr1, addr0) - } -} - -func failedDecodingTest(icap string, t *testing.T) { - addr, err := ICAPToAddress(icap) - if err == nil { - t.Errorf("Expected ICAP decoding to fail.") - } - if addr != (Address{}) { - t.Errorf("Expected empty Address on failed ICAP decoding.") - } -} diff --git a/common/list.go b/common/list.go deleted file mode 100644 index 07b2f17f5..000000000 --- a/common/list.go +++ /dev/null @@ -1,97 +0,0 @@ -// Copyright 2014 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -package common - -import ( - "encoding/json" - "reflect" - "sync" -) - -// The list type is an anonymous slice handler which can be used -// for containing any slice type to use in an environment which -// does not support slice types (e.g., JavaScript, QML) -type List struct { - mut sync.Mutex - val interface{} - list reflect.Value - Length int -} - -// Initialise a new list. Panics if non-slice type is given. -func NewList(t interface{}) *List { - list := reflect.ValueOf(t) - if list.Kind() != reflect.Slice { - panic("list container initialized with a non-slice type") - } - - return &List{sync.Mutex{}, t, list, list.Len()} -} - -func EmptyList() *List { - return NewList([]interface{}{}) -} - -// Get N element from the embedded slice. Returns nil if OOB. -func (self *List) Get(i int) interface{} { - if self.list.Len() > i { - self.mut.Lock() - defer self.mut.Unlock() - - i := self.list.Index(i).Interface() - - return i - } - - return nil -} - -func (self *List) GetAsJson(i int) interface{} { - e := self.Get(i) - - r, _ := json.Marshal(e) - - return string(r) -} - -// Appends value at the end of the slice. Panics when incompatible value -// is given. -func (self *List) Append(v interface{}) { - self.mut.Lock() - defer self.mut.Unlock() - - self.list = reflect.Append(self.list, reflect.ValueOf(v)) - self.Length = self.list.Len() -} - -// Returns the underlying slice as interface. -func (self *List) Interface() interface{} { - return self.list.Interface() -} - -// For JavaScript <3 -func (self *List) ToJSON() string { - // make(T, 0) != nil - list := make([]interface{}, 0) - for i := 0; i < self.Length; i++ { - list = append(list, self.Get(i)) - } - - data, _ := json.Marshal(list) - - return string(data) -} diff --git a/common/math/big.go b/common/math/big.go new file mode 100644 index 000000000..c0508c102 --- /dev/null +++ b/common/math/big.go @@ -0,0 +1,143 @@ +// Copyright 2017 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +// Package math provides integer math utilities. +package math + +import ( + "math/big" +) + +var ( + tt255 = BigPow(2, 255) + tt256 = BigPow(2, 256) + tt256m1 = new(big.Int).Sub(tt256, big.NewInt(1)) + MaxBig256 = new(big.Int).Set(tt256m1) +) + +// ParseBig256 parses s as a 256 bit integer in decimal or hexadecimal syntax. +// Leading zeros are accepted. The empty string parses as zero. +func ParseBig256(s string) (*big.Int, bool) { + if s == "" { + return new(big.Int), true + } + var bigint *big.Int + var ok bool + if len(s) >= 2 && (s[:2] == "0x" || s[:2] == "0X") { + bigint, ok = new(big.Int).SetString(s[2:], 16) + } else { + bigint, ok = new(big.Int).SetString(s, 10) + } + if ok && bigint.BitLen() > 256 { + bigint, ok = nil, false + } + return bigint, ok +} + +// MustParseBig parses s as a 256 bit big integer and panics if the string is invalid. +func MustParseBig256(s string) *big.Int { + v, ok := ParseBig256(s) + if !ok { + panic("invalid 256 bit integer: " + s) + } + return v +} + +// BigPow returns a ** b as a big integer. +func BigPow(a, b int64) *big.Int { + r := big.NewInt(a) + return r.Exp(r, big.NewInt(b), nil) +} + +// BigMax returns the larger of x or y. +func BigMax(x, y *big.Int) *big.Int { + if x.Cmp(y) < 0 { + return y + } + return x +} + +// BigMin returns the smaller of x or y. +func BigMin(x, y *big.Int) *big.Int { + if x.Cmp(y) > 0 { + return y + } + return x +} + +// FirstBitSet returns the index of the first 1 bit in v, counting from LSB. +func FirstBitSet(v *big.Int) int { + for i := 0; i < v.BitLen(); i++ { + if v.Bit(i) > 0 { + return i + } + } + return v.BitLen() +} + +// PaddedBigBytes encodes a big integer as a big-endian byte slice. The length +// of the slice is at least n bytes. +func PaddedBigBytes(bigint *big.Int, n int) []byte { + bytes := bigint.Bytes() + if len(bytes) >= n { + return bytes + } + ret := make([]byte, n) + return append(ret[:len(ret)-len(bytes)], bytes...) +} + +// U256 encodes as a 256 bit two's complement number. This operation is destructive. +func U256(x *big.Int) *big.Int { + return x.And(x, tt256m1) +} + +// S256 interprets x as a two's complement number. +// x must not exceed 256 bits (the result is undefined if it does) and is not modified. +// +// S256(0) = 0 +// S256(1) = 1 +// S256(2**255) = -2**255 +// S256(2**256-1) = -1 +func S256(x *big.Int) *big.Int { + if x.Cmp(tt255) < 0 { + return x + } else { + return new(big.Int).Sub(x, tt256) + } +} + +// wordSize is the size number of bits in a big.Word. +const wordSize = 32 << (uint64(^big.Word(0)) >> 63) + +// Exp implements exponentiation by squaring. +// Exp returns a newly-allocated big integer and does not change +// base or exponent. The result is truncated to 256 bits. +// +// Courtesy @karalabe and @chfast +func Exp(base, exponent *big.Int) *big.Int { + result := big.NewInt(1) + + for _, word := range exponent.Bits() { + for i := 0; i < wordSize; i++ { + if word&1 == 1 { + U256(result.Mul(result, base)) + } + U256(base.Mul(base, base)) + word >>= 1 + } + } + return result +} diff --git a/common/math/big_test.go b/common/math/big_test.go new file mode 100644 index 000000000..a0f48a8eb --- /dev/null +++ b/common/math/big_test.go @@ -0,0 +1,196 @@ +// Copyright 2014 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + +package math + +import ( + "bytes" + "math/big" + "testing" +) + +func TestParseBig256(t *testing.T) { + tests := []struct { + input string + num *big.Int + ok bool + }{ + {"", big.NewInt(0), true}, + {"0", big.NewInt(0), true}, + {"0x0", big.NewInt(0), true}, + {"12345678", big.NewInt(12345678), true}, + {"0x12345678", big.NewInt(0x12345678), true}, + {"0X12345678", big.NewInt(0x12345678), true}, + // Tests for leading zero behaviour: + {"0123456789", big.NewInt(123456789), true}, // note: not octal + {"00", big.NewInt(0), true}, + {"0x00", big.NewInt(0), true}, + {"0x012345678abc", big.NewInt(0x12345678abc), true}, + // Invalid syntax: + {"abcdef", nil, false}, + {"0xgg", nil, false}, + // Larger than 256 bits: + {"115792089237316195423570985008687907853269984665640564039457584007913129639936", nil, false}, + } + for _, test := range tests { + num, ok := ParseBig256(test.input) + if ok != test.ok { + t.Errorf("ParseBig(%q) -> ok = %t, want %t", test.input, ok, test.ok) + continue + } + if num != nil && test.num != nil && num.Cmp(test.num) != 0 { + t.Errorf("ParseBig(%q) -> %d, want %d", test.input, num, test.num) + } + } +} + +func TestMustParseBig256(t *testing.T) { + defer func() { + if recover() == nil { + t.Error("MustParseBig should've panicked") + } + }() + MustParseBig256("ggg") +} + +func TestBigMax(t *testing.T) { + a := big.NewInt(10) + b := big.NewInt(5) + + max1 := BigMax(a, b) + if max1 != a { + t.Errorf("Expected %d got %d", a, max1) + } + + max2 := BigMax(b, a) + if max2 != a { + t.Errorf("Expected %d got %d", a, max2) + } +} + +func TestBigMin(t *testing.T) { + a := big.NewInt(10) + b := big.NewInt(5) + + min1 := BigMin(a, b) + if min1 != b { + t.Errorf("Expected %d got %d", b, min1) + } + + min2 := BigMin(b, a) + if min2 != b { + t.Errorf("Expected %d got %d", b, min2) + } +} + +func TestFirstBigSet(t *testing.T) { + tests := []struct { + num *big.Int + ix int + }{ + {big.NewInt(0), 0}, + {big.NewInt(1), 0}, + {big.NewInt(2), 1}, + {big.NewInt(0x100), 8}, + } + for _, test := range tests { + if ix := FirstBitSet(test.num); ix != test.ix { + t.Errorf("FirstBitSet(b%b) = %d, want %d", test.num, ix, test.ix) + } + } +} + +func TestPaddedBigBytes(t *testing.T) { + tests := []struct { + num *big.Int + n int + result []byte + }{ + {num: big.NewInt(0), n: 4, result: []byte{0, 0, 0, 0}}, + {num: big.NewInt(1), n: 4, result: []byte{0, 0, 0, 1}}, + {num: big.NewInt(512), n: 4, result: []byte{0, 0, 2, 0}}, + {num: BigPow(2, 32), n: 4, result: []byte{1, 0, 0, 0, 0}}, + } + for _, test := range tests { + if result := PaddedBigBytes(test.num, test.n); !bytes.Equal(result, test.result) { + t.Errorf("PaddedBigBytes(%d, %d) = %v, want %v", test.num, test.n, result, test.result) + } + } +} + +func TestU256(t *testing.T) { + tests := []struct{ x, y *big.Int }{ + {x: big.NewInt(0), y: big.NewInt(0)}, + {x: big.NewInt(1), y: big.NewInt(1)}, + {x: BigPow(2, 255), y: BigPow(2, 255)}, + {x: BigPow(2, 256), y: big.NewInt(0)}, + {x: new(big.Int).Add(BigPow(2, 256), big.NewInt(1)), y: big.NewInt(1)}, + // negative values + {x: big.NewInt(-1), y: new(big.Int).Sub(BigPow(2, 256), big.NewInt(1))}, + {x: big.NewInt(-2), y: new(big.Int).Sub(BigPow(2, 256), big.NewInt(2))}, + {x: BigPow(2, -255), y: big.NewInt(1)}, + } + for _, test := range tests { + if y := U256(new(big.Int).Set(test.x)); y.Cmp(test.y) != 0 { + t.Errorf("U256(%x) = %x, want %x", test.x, y, test.y) + } + } +} + +func TestS256(t *testing.T) { + tests := []struct{ x, y *big.Int }{ + {x: big.NewInt(0), y: big.NewInt(0)}, + {x: big.NewInt(1), y: big.NewInt(1)}, + {x: big.NewInt(2), y: big.NewInt(2)}, + { + x: new(big.Int).Sub(BigPow(2, 255), big.NewInt(1)), + y: new(big.Int).Sub(BigPow(2, 255), big.NewInt(1)), + }, + { + x: BigPow(2, 255), + y: new(big.Int).Neg(BigPow(2, 255)), + }, + { + x: new(big.Int).Sub(BigPow(2, 256), big.NewInt(1)), + y: big.NewInt(-1), + }, + { + x: new(big.Int).Sub(BigPow(2, 256), big.NewInt(2)), + y: big.NewInt(-2), + }, + } + for _, test := range tests { + if y := S256(test.x); y.Cmp(test.y) != 0 { + t.Errorf("S256(%x) = %x, want %x", test.x, y, test.y) + } + } +} + +func TestExp(t *testing.T) { + tests := []struct{ base, exponent, result *big.Int }{ + {base: big.NewInt(0), exponent: big.NewInt(0), result: big.NewInt(1)}, + {base: big.NewInt(1), exponent: big.NewInt(0), result: big.NewInt(1)}, + {base: big.NewInt(1), exponent: big.NewInt(1), result: big.NewInt(1)}, + {base: big.NewInt(1), exponent: big.NewInt(2), result: big.NewInt(1)}, + {base: big.NewInt(3), exponent: big.NewInt(144), result: MustParseBig256("507528786056415600719754159741696356908742250191663887263627442114881")}, + {base: big.NewInt(2), exponent: big.NewInt(255), result: MustParseBig256("57896044618658097711785492504343953926634992332820282019728792003956564819968")}, + } + for _, test := range tests { + if result := Exp(test.base, test.exponent); result.Cmp(test.result) != 0 { + t.Errorf("Exp(%d, %d) = %d, want %d", test.base, test.exponent, result, test.result) + } + } +} diff --git a/common/math/dist.go b/common/math/dist.go deleted file mode 100644 index 913fbfbd4..000000000 --- a/common/math/dist.go +++ /dev/null @@ -1,96 +0,0 @@ -// Copyright 2015 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -package math - -import ( - "math/big" - "sort" - - "github.com/ethereum/go-ethereum/common" -) - -type Summer interface { - Sum(i int) *big.Int - Len() int -} - -func Sum(slice Summer) (sum *big.Int) { - sum = new(big.Int) - - for i := 0; i < slice.Len(); i++ { - sum.Add(sum, slice.Sum(i)) - } - return -} - -type Vector struct { - Gas, Price *big.Int -} - -type VectorsBy func(v1, v2 Vector) bool - -func (self VectorsBy) Sort(vectors []Vector) { - bs := vectorSorter{ - vectors: vectors, - by: self, - } - sort.Sort(bs) -} - -type vectorSorter struct { - vectors []Vector - by func(v1, v2 Vector) bool -} - -func (v vectorSorter) Len() int { return len(v.vectors) } -func (v vectorSorter) Less(i, j int) bool { return v.by(v.vectors[i], v.vectors[j]) } -func (v vectorSorter) Swap(i, j int) { v.vectors[i], v.vectors[j] = v.vectors[j], v.vectors[i] } - -func PriceSort(v1, v2 Vector) bool { return v1.Price.Cmp(v2.Price) < 0 } -func GasSort(v1, v2 Vector) bool { return v1.Gas.Cmp(v2.Gas) < 0 } - -type vectorSummer struct { - vectors []Vector - by func(v Vector) *big.Int -} - -type VectorSum func(v Vector) *big.Int - -func (v VectorSum) Sum(vectors []Vector) *big.Int { - vs := vectorSummer{ - vectors: vectors, - by: v, - } - return Sum(vs) -} - -func (v vectorSummer) Len() int { return len(v.vectors) } -func (v vectorSummer) Sum(i int) *big.Int { return v.by(v.vectors[i]) } - -func GasSum(v Vector) *big.Int { return v.Gas } - -var etherInWei = new(big.Rat).SetInt(common.String2Big("1000000000000000000")) - -func GasPrice(bp, gl, ep *big.Int) *big.Int { - BP := new(big.Rat).SetInt(bp) - GL := new(big.Rat).SetInt(gl) - EP := new(big.Rat).SetInt(ep) - GP := new(big.Rat).Quo(BP, GL) - GP = GP.Quo(GP, EP) - - return GP.Mul(GP, etherInWei).Num() -} diff --git a/common/math/dist_test.go b/common/math/dist_test.go deleted file mode 100644 index f5857b6f8..000000000 --- a/common/math/dist_test.go +++ /dev/null @@ -1,82 +0,0 @@ -// Copyright 2015 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -package math - -import ( - "fmt" - "math/big" - "testing" -) - -type summer struct { - numbers []*big.Int -} - -func (s summer) Len() int { return len(s.numbers) } -func (s summer) Sum(i int) *big.Int { - return s.numbers[i] -} - -func TestSum(t *testing.T) { - summer := summer{numbers: []*big.Int{big.NewInt(1), big.NewInt(2), big.NewInt(3)}} - sum := Sum(summer) - if sum.Cmp(big.NewInt(6)) != 0 { - t.Errorf("got sum = %d, want 6", sum) - } -} - -func TestDist(t *testing.T) { - var vectors = []Vector{ - {big.NewInt(1000), big.NewInt(1234)}, - {big.NewInt(500), big.NewInt(10023)}, - {big.NewInt(1034), big.NewInt(1987)}, - {big.NewInt(1034), big.NewInt(1987)}, - {big.NewInt(8983), big.NewInt(1977)}, - {big.NewInt(98382), big.NewInt(1887)}, - {big.NewInt(12398), big.NewInt(1287)}, - {big.NewInt(12398), big.NewInt(1487)}, - {big.NewInt(12398), big.NewInt(1987)}, - {big.NewInt(12398), big.NewInt(128)}, - {big.NewInt(12398), big.NewInt(1987)}, - {big.NewInt(1398), big.NewInt(187)}, - {big.NewInt(12328), big.NewInt(1927)}, - {big.NewInt(12398), big.NewInt(1987)}, - {big.NewInt(22398), big.NewInt(1287)}, - {big.NewInt(1370), big.NewInt(1981)}, - {big.NewInt(12398), big.NewInt(1957)}, - {big.NewInt(42198), big.NewInt(1987)}, - } - - VectorsBy(GasSort).Sort(vectors) - fmt.Println(vectors) - - BP := big.NewInt(15) - GL := big.NewInt(1000000) - EP := big.NewInt(100) - fmt.Println("BP", BP, "GL", GL, "EP", EP) - GP := GasPrice(BP, GL, EP) - fmt.Println("GP =", GP, "Wei per GU") - - S := len(vectors) / 4 - fmt.Println("L", len(vectors), "S", S) - for i := 1; i <= S*4; i += S { - fmt.Printf("T%d = %v\n", i, vectors[i]) - } - - g := VectorSum(GasSum).Sum(vectors) - fmt.Printf("G = ∑g* (%v)\n", g) -} diff --git a/common/math/exp.go b/common/math/exp.go deleted file mode 100644 index 113b76b39..000000000 --- a/common/math/exp.go +++ /dev/null @@ -1,47 +0,0 @@ -// Copyright 2016 The go-ethereum Authors -// This file is part of the go-ethereum library. -// -// The go-ethereum library is free software: you can redistribute it and/or modify -// it under the terms of the GNU Lesser General Public License as published by -// the Free Software Foundation, either version 3 of the License, or -// (at your option) any later version. -// -// The go-ethereum library is distributed in the hope that it will be useful, -// but WITHOUT ANY WARRANTY; without even the implied warranty of -// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -// GNU Lesser General Public License for more details. -// -// You should have received a copy of the GNU Lesser General Public License -// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. - -package math - -import ( - "math/big" - - "github.com/ethereum/go-ethereum/common" -) - -// wordSize is the size number of bits in a big.Int Word. -const wordSize = 32 << (uint64(^big.Word(0)) >> 63) - -// Exp implement exponentiation by squaring algorithm. -// -// Exp return a new variable; base and exponent must -// not be changed under any circumstance. -// -// Courtesy @karalabe and @chfast -func Exp(base, exponent *big.Int) *big.Int { - result := big.NewInt(1) - - for _, word := range exponent.Bits() { - for i := 0; i < wordSize; i++ { - if word&1 == 1 { - common.U256(result.Mul(result, base)) - } - common.U256(base.Mul(base, base)) - word >>= 1 - } - } - return result -} diff --git a/common/math/integer.go b/common/math/integer.go index 1689b6586..a3eeee27e 100644 --- a/common/math/integer.go +++ b/common/math/integer.go @@ -1,10 +1,63 @@ +// Copyright 2017 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + package math -import gmath "math" +import "strconv" + +const ( + // Integer limit values. + MaxInt8 = 1<<7 - 1 + MinInt8 = -1 << 7 + MaxInt16 = 1<<15 - 1 + MinInt16 = -1 << 15 + MaxInt32 = 1<<31 - 1 + MinInt32 = -1 << 31 + MaxInt64 = 1<<63 - 1 + MinInt64 = -1 << 63 + MaxUint8 = 1<<8 - 1 + MaxUint16 = 1<<16 - 1 + MaxUint32 = 1<<32 - 1 + MaxUint64 = 1<<64 - 1 +) + +// ParseUint64 parses s as an integer in decimal or hexadecimal syntax. +// Leading zeros are accepted. The empty string parses as zero. +func ParseUint64(s string) (uint64, bool) { + if s == "" { + return 0, true + } + if len(s) >= 2 && (s[:2] == "0x" || s[:2] == "0X") { + v, err := strconv.ParseUint(s[2:], 16, 64) + return v, err == nil + } + v, err := strconv.ParseUint(s, 10, 64) + return v, err == nil +} + +// MustParseUint64 parses s as an integer and panics if the string is invalid. +func MustParseUint64(s string) uint64 { + v, ok := ParseUint64(s) + if !ok { + panic("invalid unsigned 64 bit integer: " + s) + } + return v +} -/* - * NOTE: The following methods need to be optimised using either bit checking or asm - */ +// NOTE: The following methods need to be optimised using either bit checking or asm // SafeSub returns subtraction result and whether overflow occurred. func SafeSub(x, y uint64) (uint64, bool) { @@ -13,7 +66,7 @@ func SafeSub(x, y uint64) (uint64, bool) { // SafeAdd returns the result and whether overflow occurred. func SafeAdd(x, y uint64) (uint64, bool) { - return x + y, y > gmath.MaxUint64-x + return x + y, y > MaxUint64-x } // SafeMul returns multiplication result and whether overflow occurred. @@ -21,5 +74,5 @@ func SafeMul(x, y uint64) (uint64, bool) { if x == 0 || y == 0 { return 0, false } - return x * y, y > gmath.MaxUint64/x + return x * y, y > MaxUint64/x } diff --git a/common/math/integer_test.go b/common/math/integer_test.go index 198114e5e..05bba221f 100644 --- a/common/math/integer_test.go +++ b/common/math/integer_test.go @@ -1,7 +1,22 @@ +// Copyright 2017 The go-ethereum Authors +// This file is part of the go-ethereum library. +// +// The go-ethereum library is free software: you can redistribute it and/or modify +// it under the terms of the GNU Lesser General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. +// +// The go-ethereum library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU Lesser General Public License for more details. +// +// You should have received a copy of the GNU Lesser General Public License +// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. + package math import ( - gmath "math" "testing" ) @@ -21,17 +36,18 @@ func TestOverflow(t *testing.T) { op operation }{ // add operations - {gmath.MaxUint64, 1, true, add}, - {gmath.MaxUint64 - 1, 1, false, add}, + {MaxUint64, 1, true, add}, + {MaxUint64 - 1, 1, false, add}, // sub operations {0, 1, true, sub}, {0, 0, false, sub}, // mul operations + {0, 0, false, mul}, {10, 10, false, mul}, - {gmath.MaxUint64, 2, true, mul}, - {gmath.MaxUint64, 1, false, mul}, + {MaxUint64, 2, true, mul}, + {MaxUint64, 1, false, mul}, } { var overflows bool switch test.op { @@ -48,3 +64,52 @@ func TestOverflow(t *testing.T) { } } } + +func TestParseUint64(t *testing.T) { + tests := []struct { + input string + num uint64 + ok bool + }{ + {"", 0, true}, + {"0", 0, true}, + {"0x0", 0, true}, + {"12345678", 12345678, true}, + {"0x12345678", 0x12345678, true}, + {"0X12345678", 0x12345678, true}, + // Tests for leading zero behaviour: + {"0123456789", 123456789, true}, // note: not octal + {"0x00", 0, true}, + {"0x012345678abc", 0x12345678abc, true}, + // Invalid syntax: + {"abcdef", 0, false}, + {"0xgg", 0, false}, + // Doesn't fit into 64 bits: + {"18446744073709551617", 0, false}, + } + for _, test := range tests { + num, ok := ParseUint64(test.input) + if ok != test.ok { + t.Errorf("ParseUint64(%q) -> ok = %t, want %t", test.input, ok, test.ok) + continue + } + if ok && num != test.num { + t.Errorf("ParseUint64(%q) -> %d, want %d", test.input, num, test.num) + } + } +} + +func TestMustParseUint64(t *testing.T) { + if v := MustParseUint64("12345"); v != 12345 { + t.Errorf(`MustParseUint64("12345") = %d, want 12345`, v) + } +} + +func TestMustParseUint64Panic(t *testing.T) { + defer func() { + if recover() == nil { + t.Error("MustParseBig should've panicked") + } + }() + MustParseUint64("ggg") +} diff --git a/common/size.go b/common/size.go index 9653b3629..c5a0cb0f2 100644 --- a/common/size.go +++ b/common/size.go @@ -18,7 +18,6 @@ package common import ( "fmt" - "math/big" ) type StorageSize float64 @@ -36,54 +35,3 @@ func (self StorageSize) String() string { func (self StorageSize) Int64() int64 { return int64(self) } - -// The different number of units -var ( - Douglas = BigPow(10, 42) - Einstein = BigPow(10, 21) - Ether = BigPow(10, 18) - Finney = BigPow(10, 15) - Szabo = BigPow(10, 12) - Shannon = BigPow(10, 9) - Babbage = BigPow(10, 6) - Ada = BigPow(10, 3) - Wei = big.NewInt(1) -) - -// -// Currency to string -// Returns a string representing a human readable format -func CurrencyToString(num *big.Int) string { - var ( - fin *big.Int = num - denom string = "Wei" - ) - - switch { - case num.Cmp(Ether) >= 0: - fin = new(big.Int).Div(num, Ether) - denom = "Ether" - case num.Cmp(Finney) >= 0: - fin = new(big.Int).Div(num, Finney) - denom = "Finney" - case num.Cmp(Szabo) >= 0: - fin = new(big.Int).Div(num, Szabo) - denom = "Szabo" - case num.Cmp(Shannon) >= 0: - fin = new(big.Int).Div(num, Shannon) - denom = "Shannon" - case num.Cmp(Babbage) >= 0: - fin = new(big.Int).Div(num, Babbage) - denom = "Babbage" - case num.Cmp(Ada) >= 0: - fin = new(big.Int).Div(num, Ada) - denom = "Ada" - } - - // TODO add comment clarifying expected behavior - if len(fin.String()) > 5 { - return fmt.Sprintf("%sE%d %s", fin.String()[0:5], len(fin.String())-5, denom) - } - - return fmt.Sprintf("%v %s", fin, denom) -} diff --git a/common/size_test.go b/common/size_test.go index ce19cab69..f5b6c725e 100644 --- a/common/size_test.go +++ b/common/size_test.go @@ -17,43 +17,22 @@ package common import ( - "math/big" - - checker "gopkg.in/check.v1" + "testing" ) -type SizeSuite struct{} - -var _ = checker.Suite(&SizeSuite{}) - -func (s *SizeSuite) TestStorageSizeString(c *checker.C) { - data1 := 2381273 - data2 := 2192 - data3 := 12 - - exp1 := "2.38 mB" - exp2 := "2.19 kB" - exp3 := "12.00 B" - - c.Assert(StorageSize(data1).String(), checker.Equals, exp1) - c.Assert(StorageSize(data2).String(), checker.Equals, exp2) - c.Assert(StorageSize(data3).String(), checker.Equals, exp3) -} - -func (s *SizeSuite) TestCommon(c *checker.C) { - ether := CurrencyToString(BigPow(10, 19)) - finney := CurrencyToString(BigPow(10, 16)) - szabo := CurrencyToString(BigPow(10, 13)) - shannon := CurrencyToString(BigPow(10, 10)) - babbage := CurrencyToString(BigPow(10, 7)) - ada := CurrencyToString(BigPow(10, 4)) - wei := CurrencyToString(big.NewInt(10)) - - c.Assert(ether, checker.Equals, "10 Ether") - c.Assert(finney, checker.Equals, "10 Finney") - c.Assert(szabo, checker.Equals, "10 Szabo") - c.Assert(shannon, checker.Equals, "10 Shannon") - c.Assert(babbage, checker.Equals, "10 Babbage") - c.Assert(ada, checker.Equals, "10 Ada") - c.Assert(wei, checker.Equals, "10 Wei") +func TestStorageSizeString(t *testing.T) { + tests := []struct { + size StorageSize + str string + }{ + {2381273, "2.38 mB"}, + {2192, "2.19 kB"}, + {12, "12.00 B"}, + } + + for _, test := range tests { + if test.size.String() != test.str { + t.Errorf("%f: got %q, want %q", float64(test.size), test.size.String(), test.str) + } + } } diff --git a/common/types.go b/common/types.go index 8a456e965..d38ea7306 100644 --- a/common/types.go +++ b/common/types.go @@ -52,7 +52,7 @@ func HexToHash(s string) Hash { return BytesToHash(FromHex(s)) } // Get the string representation of the underlying hash func (h Hash) Str() string { return string(h[:]) } func (h Hash) Bytes() []byte { return h[:] } -func (h Hash) Big() *big.Int { return Bytes2Big(h[:]) } +func (h Hash) Big() *big.Int { return new(big.Int).SetBytes(h[:]) } func (h Hash) Hex() string { return hexutil.Encode(h[:]) } // UnmarshalJSON parses a hash in its hex from to a hash. @@ -122,7 +122,7 @@ func IsHexAddress(s string) bool { // Get the string representation of the underlying address func (a Address) Str() string { return string(a[:]) } func (a Address) Bytes() []byte { return a[:] } -func (a Address) Big() *big.Int { return Bytes2Big(a[:]) } +func (a Address) Big() *big.Int { return new(big.Int).SetBytes(a[:]) } func (a Address) Hash() Hash { return BytesToHash(a[:]) } func (a Address) Hex() string { return hexutil.Encode(a[:]) } diff --git a/common/types_template.go b/common/types_template.go index 8048f9cc3..9a8f29977 100644 --- a/common/types_template.go +++ b/common/types_template.go @@ -37,7 +37,7 @@ func HexTo_N_(s string) _N_ { return BytesTo_N_(FromHex(s)) } // Get the string representation of the underlying hash func (h _N_) Str() string { return string(h[:]) } func (h _N_) Bytes() []byte { return h[:] } -func (h _N_) Big() *big.Int { return Bytes2Big(h[:]) } +func (h _N_) Big() *big.Int { return new(big.Int).SetBytes(h[:]) } func (h _N_) Hex() string { return "0x" + Bytes2Hex(h[:]) } // Sets the hash to the value of b. If b is larger than len(h) it will panic |