From 3285a0fda37207ca1b79ac28e2c12c6f5efff89b Mon Sep 17 00:00:00 2001 From: Martin Holst Swende Date: Sun, 28 May 2017 23:39:33 +0200 Subject: core/vm, common/math: Add fast getByte for bigints, improve opByte --- common/math/big.go | 28 +++++++++++++++ common/math/big_test.go | 93 ++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 120 insertions(+), 1 deletion(-) (limited to 'common/math') diff --git a/common/math/big.go b/common/math/big.go index fd0174b36..48ad90216 100644 --- a/common/math/big.go +++ b/common/math/big.go @@ -130,6 +130,34 @@ func PaddedBigBytes(bigint *big.Int, n int) []byte { return ret } +// LittleEndianByteAt returns the byte at position n, +// if bigint is considered little-endian. +// So n==0 gives the least significant byte +func LittleEndianByteAt(bigint *big.Int, n int) byte { + words := bigint.Bits() + // Check word-bucket the byte will reside in + i := n / wordBytes + if i >= len(words) { + return byte(0) + } + word := words[i] + // Offset of the byte + shift := 8 * uint(n%wordBytes) + + return byte(word >> shift) +} + +// BigEndian32ByteAt returns the byte at position n, +// if bigint is considered big-endian. +// So n==0 gives the most significant byte +// WARNING: Only works for bigints in 32-byte range +func BigEndian32ByteAt(bigint *big.Int, n int) byte { + if n > 31 { + return byte(0) + } + return LittleEndianByteAt(bigint, 31-n) +} + // ReadBits encodes the absolute value of bigint as big-endian bytes. Callers must ensure // that buf has enough space. If buf is too short the result will be incomplete. func ReadBits(bigint *big.Int, buf []byte) { diff --git a/common/math/big_test.go b/common/math/big_test.go index e789bd18e..d4de7b8c3 100644 --- a/common/math/big_test.go +++ b/common/math/big_test.go @@ -21,6 +21,8 @@ import ( "encoding/hex" "math/big" "testing" + + "github.com/ethereum/go-ethereum/common" ) func TestHexOrDecimal256(t *testing.T) { @@ -133,8 +135,40 @@ func TestPaddedBigBytes(t *testing.T) { } } -func BenchmarkPaddedBigBytes(b *testing.B) { +func BenchmarkPaddedBigBytesLargePadding(b *testing.B) { bigint := MustParseBig256("123456789123456789123456789123456789") + for i := 0; i < b.N; i++ { + PaddedBigBytes(bigint, 200) + } +} +func BenchmarkPaddedBigBytesSmallPadding(b *testing.B) { + bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") + for i := 0; i < b.N; i++ { + PaddedBigBytes(bigint, 5) + } +} + +func BenchmarkPaddedBigBytesSmallOnePadding(b *testing.B) { + bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") + for i := 0; i < b.N; i++ { + PaddedBigBytes(bigint, 32) + } +} +func BenchmarkByteAtBrandNew(b *testing.B) { + bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") + for i := 0; i < b.N; i++ { + BigEndian32ByteAt(bigint, 15) + } +} +func BenchmarkByteAt(b *testing.B) { + bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") + for i := 0; i < b.N; i++ { + BigEndian32ByteAt(bigint, 15) + } +} +func BenchmarkByteAtOld(b *testing.B) { + + bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") for i := 0; i < b.N; i++ { PaddedBigBytes(bigint, 32) } @@ -173,7 +207,64 @@ func TestU256(t *testing.T) { } } } +func TestLittleEndianByteAt(t *testing.T) { + + tests := []struct { + x string + y int + exp byte + }{ + {"0", 0, 0x00}, + {"1", 1, 0x00}, + {"0", 1, 0x00}, + //{"1", 0, 0x01}, + {"0000000000000000000000000000000000000000000000000000000000102030", 0, 0x30}, + {"0000000000000000000000000000000000000000000000000000000000102030", 1, 0x20}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 31, 0xAB}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 32, 0x00}, + } + for _, test := range tests { + v := new(big.Int).SetBytes(common.Hex2Bytes(test.x)) + actual := LittleEndianByteAt(v, test.y) + if actual != test.exp { + t.Fatalf("Expected [%v] %v:th byte to be %v, was %v.", test.x, test.y, test.exp, actual) + } + + } +} +func TestBigEndianByteAt(t *testing.T) { + tests := []struct { + x string + y int + exp byte + }{ + {"0", 0, 0x00}, + {"1", 1, 0x00}, + {"0", 1, 0x00}, + {"1", 0, 0x00}, + {"0000000000000000000000000000000000000000000000000000000000102030", 0, 0x00}, + {"0000000000000000000000000000000000000000000000000000000000102030", 1, 0x00}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 31, 0x00}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 32, 0x00}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 0, 0xAB}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 1, 0xCD}, + {"00CDEF090807060504030201ffffffffffffffffffffffffffffffffffffffff", 0, 0x00}, + {"00CDEF090807060504030201ffffffffffffffffffffffffffffffffffffffff", 1, 0xCD}, + {"0000000000000000000000000000000000000000000000000000000000102030", 31, 0x30}, + {"0000000000000000000000000000000000000000000000000000000000102030", 30, 0x20}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 32, 0x0}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 0xFFFFFFFF, 0x0}, + } + for _, test := range tests { + v := new(big.Int).SetBytes(common.Hex2Bytes(test.x)) + actual := BigEndian32ByteAt(v, test.y) + if actual != test.exp { + t.Fatalf("Expected [%v] %v:th byte to be %v, was %v.", test.x, test.y, test.exp, actual) + } + + } +} func TestS256(t *testing.T) { tests := []struct{ x, y *big.Int }{ {x: big.NewInt(0), y: big.NewInt(0)}, -- cgit v1.2.3 From 1496b3aff6a537a1c5597ec55b8d3b25afded26c Mon Sep 17 00:00:00 2001 From: Martin Holst Swende Date: Tue, 6 Jun 2017 18:38:38 +0200 Subject: common/math, core/vm: Un-expose bigEndianByteAt, use correct terms for endianness --- common/math/big.go | 22 +++++++++++----------- common/math/big_test.go | 11 ++++++----- 2 files changed, 17 insertions(+), 16 deletions(-) (limited to 'common/math') diff --git a/common/math/big.go b/common/math/big.go index 48ad90216..c49d751fa 100644 --- a/common/math/big.go +++ b/common/math/big.go @@ -130,10 +130,10 @@ func PaddedBigBytes(bigint *big.Int, n int) []byte { return ret } -// LittleEndianByteAt returns the byte at position n, -// if bigint is considered little-endian. -// So n==0 gives the least significant byte -func LittleEndianByteAt(bigint *big.Int, n int) byte { +// bigEndianByteAt returns the byte at position n, +// if bigint is considered big-endian. +// So n==0 returns the least significant byte +func bigEndianByteAt(bigint *big.Int, n int) byte { words := bigint.Bits() // Check word-bucket the byte will reside in i := n / wordBytes @@ -147,15 +147,15 @@ func LittleEndianByteAt(bigint *big.Int, n int) byte { return byte(word >> shift) } -// BigEndian32ByteAt returns the byte at position n, -// if bigint is considered big-endian. -// So n==0 gives the most significant byte -// WARNING: Only works for bigints in 32-byte range -func BigEndian32ByteAt(bigint *big.Int, n int) byte { - if n > 31 { +// Byte returns the byte at position n, +// if bigint is considered little-endian with the supplied padlength. +// n==0 returns the most significant byte +// bigint '5', padlength 32, n=31 => 5 +func Byte(bigint *big.Int, padlength, n int) byte { + if n >= padlength { return byte(0) } - return LittleEndianByteAt(bigint, 31-n) + return bigEndianByteAt(bigint, padlength-1-n) } // ReadBits encodes the absolute value of bigint as big-endian bytes. Callers must ensure diff --git a/common/math/big_test.go b/common/math/big_test.go index d4de7b8c3..7cce7c212 100644 --- a/common/math/big_test.go +++ b/common/math/big_test.go @@ -157,13 +157,13 @@ func BenchmarkPaddedBigBytesSmallOnePadding(b *testing.B) { func BenchmarkByteAtBrandNew(b *testing.B) { bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") for i := 0; i < b.N; i++ { - BigEndian32ByteAt(bigint, 15) + bigEndianByteAt(bigint, 15) } } func BenchmarkByteAt(b *testing.B) { bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") for i := 0; i < b.N; i++ { - BigEndian32ByteAt(bigint, 15) + bigEndianByteAt(bigint, 15) } } func BenchmarkByteAtOld(b *testing.B) { @@ -225,7 +225,7 @@ func TestLittleEndianByteAt(t *testing.T) { } for _, test := range tests { v := new(big.Int).SetBytes(common.Hex2Bytes(test.x)) - actual := LittleEndianByteAt(v, test.y) + actual := bigEndianByteAt(v, test.y) if actual != test.exp { t.Fatalf("Expected [%v] %v:th byte to be %v, was %v.", test.x, test.y, test.exp, actual) } @@ -254,11 +254,12 @@ func TestBigEndianByteAt(t *testing.T) { {"0000000000000000000000000000000000000000000000000000000000102030", 31, 0x30}, {"0000000000000000000000000000000000000000000000000000000000102030", 30, 0x20}, {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 32, 0x0}, - {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 0xFFFFFFFF, 0x0}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 31, 0xFF}, + {"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", 0xFFFF, 0x0}, } for _, test := range tests { v := new(big.Int).SetBytes(common.Hex2Bytes(test.x)) - actual := BigEndian32ByteAt(v, test.y) + actual := Byte(v, 32, test.y) if actual != test.exp { t.Fatalf("Expected [%v] %v:th byte to be %v, was %v.", test.x, test.y, test.exp, actual) } -- cgit v1.2.3 From ac9865791a691094293e08702623c3a1374eeb5f Mon Sep 17 00:00:00 2001 From: Martin Holst Swende Date: Thu, 8 Jun 2017 23:16:05 +0200 Subject: core/vm, common/math: Add doc about Byte, fix format --- common/math/big.go | 8 ++++---- common/math/big_test.go | 27 ++++++++++++++++----------- 2 files changed, 20 insertions(+), 15 deletions(-) (limited to 'common/math') diff --git a/common/math/big.go b/common/math/big.go index c49d751fa..787278650 100644 --- a/common/math/big.go +++ b/common/math/big.go @@ -131,7 +131,7 @@ func PaddedBigBytes(bigint *big.Int, n int) []byte { } // bigEndianByteAt returns the byte at position n, -// if bigint is considered big-endian. +// in Big-Endian encoding // So n==0 returns the least significant byte func bigEndianByteAt(bigint *big.Int, n int) byte { words := bigint.Bits() @@ -148,9 +148,9 @@ func bigEndianByteAt(bigint *big.Int, n int) byte { } // Byte returns the byte at position n, -// if bigint is considered little-endian with the supplied padlength. -// n==0 returns the most significant byte -// bigint '5', padlength 32, n=31 => 5 +// with the supplied padlength in Little-Endian encoding. +// n==0 returns the MSB +// Example: bigint '5', padlength 32, n=31 => 5 func Byte(bigint *big.Int, padlength, n int) byte { if n >= padlength { return byte(0) diff --git a/common/math/big_test.go b/common/math/big_test.go index 7cce7c212..be9810dc8 100644 --- a/common/math/big_test.go +++ b/common/math/big_test.go @@ -141,6 +141,7 @@ func BenchmarkPaddedBigBytesLargePadding(b *testing.B) { PaddedBigBytes(bigint, 200) } } + func BenchmarkPaddedBigBytesSmallPadding(b *testing.B) { bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") for i := 0; i < b.N; i++ { @@ -154,18 +155,21 @@ func BenchmarkPaddedBigBytesSmallOnePadding(b *testing.B) { PaddedBigBytes(bigint, 32) } } + func BenchmarkByteAtBrandNew(b *testing.B) { bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") for i := 0; i < b.N; i++ { bigEndianByteAt(bigint, 15) } } + func BenchmarkByteAt(b *testing.B) { bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") for i := 0; i < b.N; i++ { bigEndianByteAt(bigint, 15) } } + func BenchmarkByteAtOld(b *testing.B) { bigint := MustParseBig256("0x18F8F8F1000111000110011100222004330052300000000000000000FEFCF3CC") @@ -207,21 +211,22 @@ func TestU256(t *testing.T) { } } } -func TestLittleEndianByteAt(t *testing.T) { +func TestBigEndianByteAt(t *testing.T) { tests := []struct { x string y int exp byte }{ - {"0", 0, 0x00}, - {"1", 1, 0x00}, - {"0", 1, 0x00}, - //{"1", 0, 0x01}, + {"00", 0, 0x00}, + {"01", 1, 0x00}, + {"00", 1, 0x00}, + {"01", 0, 0x01}, {"0000000000000000000000000000000000000000000000000000000000102030", 0, 0x30}, {"0000000000000000000000000000000000000000000000000000000000102030", 1, 0x20}, {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 31, 0xAB}, {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 32, 0x00}, + {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 500, 0x00}, } for _, test := range tests { v := new(big.Int).SetBytes(common.Hex2Bytes(test.x)) @@ -232,17 +237,16 @@ func TestLittleEndianByteAt(t *testing.T) { } } -func TestBigEndianByteAt(t *testing.T) { - +func TestLittleEndianByteAt(t *testing.T) { tests := []struct { x string y int exp byte }{ - {"0", 0, 0x00}, - {"1", 1, 0x00}, - {"0", 1, 0x00}, - {"1", 0, 0x00}, + {"00", 0, 0x00}, + {"01", 1, 0x00}, + {"00", 1, 0x00}, + {"01", 0, 0x00}, {"0000000000000000000000000000000000000000000000000000000000102030", 0, 0x00}, {"0000000000000000000000000000000000000000000000000000000000102030", 1, 0x00}, {"ABCDEF0908070605040302010000000000000000000000000000000000000000", 31, 0x00}, @@ -266,6 +270,7 @@ func TestBigEndianByteAt(t *testing.T) { } } + func TestS256(t *testing.T) { tests := []struct{ x, y *big.Int }{ {x: big.NewInt(0), y: big.NewInt(0)}, -- cgit v1.2.3