From bc17dba8fba0f3007398f231f07916a95ed963ac Mon Sep 17 00:00:00 2001 From: Felix Lange Date: Wed, 1 Jul 2015 02:09:02 +0200 Subject: rlp: add Split functions These functions allow destructuring of raw rlp-encoded bytes without the overhead of reflection or copying. --- rlp/decode_test.go | 3 +- rlp/raw.go | 140 ++++++++++++++++++++++++++++++++++++++ rlp/raw_test.go | 195 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 337 insertions(+), 1 deletion(-) create mode 100644 rlp/raw.go create mode 100644 rlp/raw_test.go (limited to 'rlp') diff --git a/rlp/decode_test.go b/rlp/decode_test.go index d6b0611dd..ce4f9ecc8 100644 --- a/rlp/decode_test.go +++ b/rlp/decode_test.go @@ -24,6 +24,7 @@ import ( "io" "math/big" "reflect" + "strings" "testing" ) @@ -725,7 +726,7 @@ func encodeTestSlice(n uint) []byte { } func unhex(str string) []byte { - b, err := hex.DecodeString(str) + b, err := hex.DecodeString(strings.Replace(str, " ", "", -1)) if err != nil { panic(fmt.Sprintf("invalid hex string: %q", str)) } diff --git a/rlp/raw.go b/rlp/raw.go new file mode 100644 index 000000000..e93c4df40 --- /dev/null +++ b/rlp/raw.go @@ -0,0 +1,140 @@ +// 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 . + +package rlp + +import "io" + +// Split returns the content of first RLP value and any +// bytes after the value as subslices of b. +func Split(b []byte) (k Kind, content, rest []byte, err error) { + k, ts, cs, err := readKind(b) + if err != nil { + return 0, nil, b, err + } + return k, b[ts : ts+cs], b[ts+cs:], nil +} + +// SplitString splits b into the content of an RLP string +// and any remaining bytes after the string. +func SplitString(b []byte) (content, rest []byte, err error) { + k, content, rest, err := Split(b) + if err != nil { + return nil, b, err + } + if k == List { + return nil, b, ErrExpectedString + } + return content, rest, nil +} + +// SplitList splits b into the content of a list and any remaining +// bytes after the list. +func SplitList(b []byte) (content, rest []byte, err error) { + k, content, rest, err := Split(b) + if err != nil { + return nil, b, err + } + if k != List { + return nil, b, ErrExpectedList + } + return content, rest, nil +} + +// CountValues counts the number of encoded values in b. +func CountValues(b []byte) (int, error) { + i := 0 + for ; len(b) > 0; i++ { + _, tagsize, size, err := readKind(b) + if err != nil { + return 0, err + } + b = b[tagsize+size:] + } + return i, nil +} + +func readKind(buf []byte) (k Kind, tagsize, contentsize uint64, err error) { + if len(buf) == 0 { + return 0, 0, 0, io.ErrUnexpectedEOF + } + b := buf[0] + switch { + case b < 0x80: + k = Byte + tagsize = 0 + contentsize = 1 + case b < 0xB8: + k = String + tagsize = 1 + contentsize = uint64(b - 0x80) + // Reject strings that should've been single bytes. + if contentsize == 1 && buf[1] < 128 { + return 0, 0, 0, ErrCanonSize + } + case b < 0xC0: + k = String + tagsize = uint64(b-0xB7) + 1 + contentsize, err = readSize(buf[1:], b-0xB7) + case b < 0xF8: + k = List + tagsize = 1 + contentsize = uint64(b - 0xC0) + default: + k = List + tagsize = uint64(b-0xF7) + 1 + contentsize, err = readSize(buf[1:], b-0xF7) + } + if err != nil { + return 0, 0, 0, err + } + // Reject values larger than the input slice. + if contentsize > uint64(len(buf))-tagsize { + return 0, 0, 0, ErrValueTooLarge + } + return k, tagsize, contentsize, err +} + +func readSize(b []byte, slen byte) (uint64, error) { + if int(slen) > len(b) { + return 0, io.ErrUnexpectedEOF + } + var s uint64 + switch slen { + case 1: + s = uint64(b[0]) + case 2: + s = uint64(b[0])<<8 | uint64(b[1]) + case 3: + s = uint64(b[0])<<16 | uint64(b[1])<<8 | uint64(b[2]) + case 4: + s = uint64(b[0])<<24 | uint64(b[1])<<16 | uint64(b[2])<<8 | uint64(b[3]) + case 5: + s = uint64(b[0])<<32 | uint64(b[1])<<24 | uint64(b[2])<<16 | uint64(b[3])<<8 | uint64(b[4]) + case 6: + s = uint64(b[0])<<40 | uint64(b[1])<<32 | uint64(b[2])<<24 | uint64(b[3])<<16 | uint64(b[4])<<8 | uint64(b[5]) + case 7: + s = uint64(b[0])<<48 | uint64(b[1])<<40 | uint64(b[2])<<32 | uint64(b[3])<<24 | uint64(b[4])<<16 | uint64(b[5])<<8 | uint64(b[6]) + case 8: + s = uint64(b[0])<<56 | uint64(b[1])<<48 | uint64(b[2])<<40 | uint64(b[3])<<32 | uint64(b[4])<<24 | uint64(b[5])<<16 | uint64(b[6])<<8 | uint64(b[7]) + } + // Reject sizes < 56 (shouldn't have separate size) and sizes with + // leading zero bytes. + if s < 56 || b[0] == 0 { + return 0, ErrCanonSize + } + return s, nil +} diff --git a/rlp/raw_test.go b/rlp/raw_test.go new file mode 100644 index 000000000..7d3ca13af --- /dev/null +++ b/rlp/raw_test.go @@ -0,0 +1,195 @@ +// 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 . + +package rlp + +import ( + "bytes" + "io" + "reflect" + "testing" +) + +func TestCountValues(t *testing.T) { + tests := []struct { + input string // note: spaces in input are stripped by unhex + count int + err error + }{ + // simple cases + {"", 0, nil}, + {"00", 1, nil}, + {"80", 1, nil}, + {"C0", 1, nil}, + {"01 02 03", 3, nil}, + {"01 C406070809 02", 3, nil}, + {"820101 820202 8403030303 04", 4, nil}, + + // size errors + {"8142", 0, ErrCanonSize}, + {"01 01 8142", 0, ErrCanonSize}, + {"02 84020202", 0, ErrValueTooLarge}, + + { + input: "A12000BF49F440A1CD0527E4D06E2765654C0F56452257516D793A9B8D604DCFDF2AB853F851808D10000000000000000000000000A056E81F171BCC55A6FF8345E692C0F86E5B48E01B996CADC001622FB5E363B421A0C5D2460186F7233C927E7DB2DCC703C0E500B653CA82273B7BFAD8045D85A470", + count: 2, + }, + } + for i, test := range tests { + count, err := CountValues(unhex(test.input)) + if count != test.count { + t.Errorf("test %d: count mismatch, got %d want %d\ninput: %s", i, count, test.count, test.input) + } + if !reflect.DeepEqual(err, test.err) { + t.Errorf("test %d: err mismatch, got %q want %q\ninput: %s", i, err, test.err, test.input) + } + } +} + +func TestSplitTypes(t *testing.T) { + if _, _, err := SplitString(unhex("C100")); err != ErrExpectedString { + t.Error("SplitString returned %q, want %q", err, ErrExpectedString) + } + if _, _, err := SplitList(unhex("01")); err != ErrExpectedList { + t.Error("SplitString returned %q, want %q", err, ErrExpectedList) + } + if _, _, err := SplitList(unhex("81FF")); err != ErrExpectedList { + t.Error("SplitString returned %q, want %q", err, ErrExpectedList) + } +} + +func TestSplit(t *testing.T) { + tests := []struct { + input string + kind Kind + val, rest string + err error + }{ + {input: "01FFFF", kind: Byte, val: "01", rest: "FFFF"}, + {input: "80FFFF", kind: String, val: "", rest: "FFFF"}, + {input: "C3010203", kind: List, val: "010203"}, + + // errors + {input: "", err: io.ErrUnexpectedEOF}, + + {input: "8141", err: ErrCanonSize, rest: "8141"}, + {input: "B800", err: ErrCanonSize, rest: "B800"}, + {input: "B802FFFF", err: ErrCanonSize, rest: "B802FFFF"}, + {input: "B90000", err: ErrCanonSize, rest: "B90000"}, + {input: "B90055", err: ErrCanonSize, rest: "B90055"}, + {input: "BA0002FFFF", err: ErrCanonSize, rest: "BA0002FFFF"}, + {input: "F800", err: ErrCanonSize, rest: "F800"}, + {input: "F90000", err: ErrCanonSize, rest: "F90000"}, + {input: "F90055", err: ErrCanonSize, rest: "F90055"}, + {input: "FA0002FFFF", err: ErrCanonSize, rest: "FA0002FFFF"}, + + {input: "8501010101", err: ErrValueTooLarge, rest: "8501010101"}, + {input: "C60607080902", err: ErrValueTooLarge, rest: "C60607080902"}, + + // size check overflow + {input: "BFFFFFFFFFFFFFFFFF", err: ErrValueTooLarge, rest: "BFFFFFFFFFFFFFFFFF"}, + {input: "FFFFFFFFFFFFFFFFFF", err: ErrValueTooLarge, rest: "FFFFFFFFFFFFFFFFFF"}, + + { + input: "B838FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + err: ErrValueTooLarge, + rest: "B838FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + }, + { + input: "F838FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + err: ErrValueTooLarge, + rest: "F838FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + }, + + // a few bigger values, just for kicks + { + input: "F839FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + kind: List, + val: "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + rest: "", + }, + { + input: "F90211A060EF29F20CC1007AE6E9530AEE16F4B31F8F1769A2D1264EC995C6D1241868D6A07C62AB8AC9838F5F5877B20BB37B387BC2106E97A3D52172CBEDB5EE17C36008A00EAB6B7324AADC0F6047C6AFC8229F09F7CF451B51D67C8DFB08D49BA8C3C626A04453343B2F3A6E42FCF87948F88AF7C8FC16D0C2735CBA7F026836239AB2C15FA024635C7291C882CE4C0763760C1A362DFC3FFCD802A55722236DE058D74202ACA0A220C808DE10F55E40AB25255201CFF009EA181D3906638E944EE2BF34049984A08D325AB26796F1CCB470F69C0F842501DC35D368A0C2575B2D243CFD1E8AB0FDA0B5298FF60DA5069463D610513C9F04F24051348391A143AFFAB7197DFACDEA72A02D2A7058A4463F8FB69378369E11EF33AE3252E2DB86CB545B36D3C26DDECE5AA0888F97BCA8E0BD83DC5B3B91CFF5FAF2F66F9501010682D67EF4A3B4E66115FBA0E8175A60C93BE9ED02921958F0EA55DA0FB5E4802AF5846147BAD92BC2D8AF26A08B3376FF433F3A4250FA64B7F804004CAC5807877D91C4427BD1CD05CF912ED8A09B32EF0F03BD13C37FF950C0CCCEFCCDD6669F2E7F2AA5CB859928E84E29763EA09BBA5E46610C8C8B1F8E921E5691BF8C7E40D75825D5EA3217AA9C3A8A355F39A0EEB95BC78251CCCEC54A97F19755C4A59A293544EEE6119AFA50531211E53C4FA00B6E86FE150BF4A9E0FEEE9C90F5465E617A861BB5E357F942881EE762212E2580", + kind: List, + val: "A060EF29F20CC1007AE6E9530AEE16F4B31F8F1769A2D1264EC995C6D1241868D6A07C62AB8AC9838F5F5877B20BB37B387BC2106E97A3D52172CBEDB5EE17C36008A00EAB6B7324AADC0F6047C6AFC8229F09F7CF451B51D67C8DFB08D49BA8C3C626A04453343B2F3A6E42FCF87948F88AF7C8FC16D0C2735CBA7F026836239AB2C15FA024635C7291C882CE4C0763760C1A362DFC3FFCD802A55722236DE058D74202ACA0A220C808DE10F55E40AB25255201CFF009EA181D3906638E944EE2BF34049984A08D325AB26796F1CCB470F69C0F842501DC35D368A0C2575B2D243CFD1E8AB0FDA0B5298FF60DA5069463D610513C9F04F24051348391A143AFFAB7197DFACDEA72A02D2A7058A4463F8FB69378369E11EF33AE3252E2DB86CB545B36D3C26DDECE5AA0888F97BCA8E0BD83DC5B3B91CFF5FAF2F66F9501010682D67EF4A3B4E66115FBA0E8175A60C93BE9ED02921958F0EA55DA0FB5E4802AF5846147BAD92BC2D8AF26A08B3376FF433F3A4250FA64B7F804004CAC5807877D91C4427BD1CD05CF912ED8A09B32EF0F03BD13C37FF950C0CCCEFCCDD6669F2E7F2AA5CB859928E84E29763EA09BBA5E46610C8C8B1F8E921E5691BF8C7E40D75825D5EA3217AA9C3A8A355F39A0EEB95BC78251CCCEC54A97F19755C4A59A293544EEE6119AFA50531211E53C4FA00B6E86FE150BF4A9E0FEEE9C90F5465E617A861BB5E357F942881EE762212E2580", + rest: "", + }, + { + input: "F877A12000BF49F440A1CD0527E4D06E2765654C0F56452257516D793A9B8D604DCFDF2AB853F851808D10000000000000000000000000A056E81F171BCC55A6FF8345E692C0F86E5B48E01B996CADC001622FB5E363B421A0C5D2460186F7233C927E7DB2DCC703C0E500B653CA82273B7BFAD8045D85A470", + kind: List, + val: "A12000BF49F440A1CD0527E4D06E2765654C0F56452257516D793A9B8D604DCFDF2AB853F851808D10000000000000000000000000A056E81F171BCC55A6FF8345E692C0F86E5B48E01B996CADC001622FB5E363B421A0C5D2460186F7233C927E7DB2DCC703C0E500B653CA82273B7BFAD8045D85A470", + rest: "", + }, + } + + for i, test := range tests { + kind, val, rest, err := Split(unhex(test.input)) + if kind != test.kind { + t.Errorf("test %d: kind mismatch: got %v, want %v", i, kind, test.kind) + } + if !bytes.Equal(val, unhex(test.val)) { + t.Errorf("test %d: val mismatch: got %x, want %s", i, val, test.val) + } + if !bytes.Equal(rest, unhex(test.rest)) { + t.Errorf("test %d: rest mismatch: got %x, want %s", i, rest, test.rest) + } + if err != test.err { + t.Errorf("test %d: error mismatch: got %q, want %q", i, err, test.err) + } + } +} + +func TestReadSize(t *testing.T) { + tests := []struct { + input string + slen byte + size uint64 + err error + }{ + {input: "", slen: 1, err: io.ErrUnexpectedEOF}, + {input: "FF", slen: 2, err: io.ErrUnexpectedEOF}, + {input: "00", slen: 1, err: ErrCanonSize}, + {input: "36", slen: 1, err: ErrCanonSize}, + {input: "37", slen: 1, err: ErrCanonSize}, + {input: "38", slen: 1, size: 0x38}, + {input: "FF", slen: 1, size: 0xFF}, + {input: "FFFF", slen: 2, size: 0xFFFF}, + {input: "FFFFFF", slen: 3, size: 0xFFFFFF}, + {input: "FFFFFFFF", slen: 4, size: 0xFFFFFFFF}, + {input: "FFFFFFFFFF", slen: 5, size: 0xFFFFFFFFFF}, + {input: "FFFFFFFFFFFF", slen: 6, size: 0xFFFFFFFFFFFF}, + {input: "FFFFFFFFFFFFFF", slen: 7, size: 0xFFFFFFFFFFFFFF}, + {input: "FFFFFFFFFFFFFFFF", slen: 8, size: 0xFFFFFFFFFFFFFFFF}, + {input: "0102", slen: 2, size: 0x0102}, + {input: "010203", slen: 3, size: 0x010203}, + {input: "01020304", slen: 4, size: 0x01020304}, + {input: "0102030405", slen: 5, size: 0x0102030405}, + {input: "010203040506", slen: 6, size: 0x010203040506}, + {input: "01020304050607", slen: 7, size: 0x01020304050607}, + {input: "0102030405060708", slen: 8, size: 0x0102030405060708}, + } + + for _, test := range tests { + size, err := readSize(unhex(test.input), test.slen) + if err != test.err { + t.Errorf("readSize(%s, %d): error mismatch: got %q, want %q", test.input, test.slen, err, test.err) + continue + } + if size != test.size { + t.Errorf("readSize(%s, %d): size mismatch: got %#x, want %#x", test.input, test.slen, size, test.size) + } + } +} -- cgit v1.2.3