195d72d

commit: 195d72d
comment: Implemented decoding rlp
file:
func Decode(data []byte, pos int) (interface{}, int) {
    char := int(data[pos])
    slice := make([]interface{}, 0) // slice 一開始為空
    
    switch {
    case char < 24:
        return append(slice, data[pos]), pos + 1 //加入slice
    case char < 56:
        b := int(data[pos]) - 23
        return FromBin(data[pos+1 : pos+1+b]), pos + 1 + b // 透過FromBin將data[pos+1 : pos+1+b]從binary轉成int64。
    case char < 64:
        b := int(data[pos]) - 55
        b2 := int(FromBin(data[pos+1 : pos+1+b])) // 透過FromBin將data[pos+1 : pos+1+b]從binary轉成int64。
        return FromBin(data[pos+1+b : pos+1+b+b2]), pos+1+b+b2 // 透過FromBin將data[pos+b : pos+1+b+b2]從binary轉成int64。
    case char < 120:
        b := int(data[pos]) - 64
        return data[pos+1:pos+1+b], pos+1+b
    case char < 128:
        b := int(data[pos]) - 119
        b2 := int(FromBin(data[pos+1 : pos+1+b]))
        return data[pos+1+b : pos+1+b+b2], pos+1+b+b2
    case char < 184:
        b := int(data[pos]) - 128
        pos++
        for i := 0; i < b; i++ {
            var obj interface{}

            obj, pos = Decode(data, pos)
            slice = append(slice, obj)
        }
        return slice, pos
    case char < 192:
        b := int(data[pos]) - 183
        //b2 := int(FromBin(data[pos+1 : pos+1+b])) (ref imprementation has an unused variable)
        pos = pos+1+b
        for i := 0; i < b; i++ {
            var obj interface{}

            obj, pos = Decode(data, pos)
            slice = append(slice, obj)
        }
        return slice, pos

    default:
        panic(fmt.Sprintf("byte not supported: %q", char))
    }

    return slice, 0
}

分析:

RLP 編碼定義如下:

型別 | 首位元組範圍 | 編碼內容 ———— | ————- [0x00, 0x7f]的單個位元組 | [0x00, 0x7f] | 位元組內容本身 0-55 位元組長的字串 | [0x80, 0xb7] | 0x80加上字串長度,後跟字串二進位制內容 超過55個位元組的字串 | [0xb8, 0xbf] | 0xb7加上字串長度的長度,後跟字串二進位制內容 0-55個位元組長的列表(所有項的組合長度) | [0xc0, 0xf7] | 0xc0加上所有的項的RLP編碼串聯起來的長度得到的單個位元組,後跟所有的項的RLP編碼的串聯組成。 列表的內容超過55位元組 | [0xf8, 0xff] | 0xC0加上所有的項的RLP編碼串聯起來的長度的長度得到的單個位元組,後跟所有的項的RLP編碼串聯起來的長度的長度,再後跟所有的項的RLP編碼的串聯組成

例子 字串 “pig” = [ 0x83, ‘p’, ‘i’, ‘g’ ] 列表 [ “pig”, “dog” ] = [ 0xc8, 0x83, ‘p’, ‘i’, ‘g’, 0x83, ’d’, ‘o’, ‘g’ ] 空字串 (‘null’) = [ 0x80 ] 空列表 = [ 0xc0 ] 數字12 (‘x0c’) = [ 0x0c ] 數字 1024 (‘x04x00’) = [ 0x82, 0x04, 0x00 ] 巢狀列表 [ [], [[]], [ [], [[]] ] ] = [ 0xc7, 0xc0, 0xc1, 0xc0, 0xc3, 0xc0, 0xc1, 0xc0 ] 字串 “Lorem ipsum dolor sit amet, consectetur adipisicing elit” = [ 0xb8, 0x38, ‘L’, ‘o’, ‘r’, ‘e’, ’m’, ‘ ‘, … , ‘e’, ‘l’, ‘i’, ’t’ ]

RLP分析 以上我們可以看出RLP編碼的設計思想,就是通過首位元組快速判斷一串編碼的型別,充分利用了一個位元組的儲存空間,將0x7f以後的值賦予了新的含義,RLP最大的優點是在充分利用位元組的情況下,同時支援列表結構,也就是說可以很輕易的利用RLP儲存一個樹狀結構。

程序處理RLP編碼時也非常容易,根據首位元組就可以判斷出這段編碼的型別,同時呼叫不同的方法進行解碼,和JSON編碼類似,支援巢狀的結構,通過遞迴呼叫可以將整個RLP快速還原成一顆樹,或者轉譯成一個JSON結構,便於其他程序使用。

Encode:

WriteSliceHeader := func(length int) {
    if length < 56 {
        // buff.WriteString(string(length + 128))
        buff.WriteByte(byte(length + 128)) // Change from use WriteString to use WriteByte 
    } else {
        b2 := ToBin(uint64(length), 0)
        // buff.WriteString(string(len(b2) + 183) + b2)
        buff.WriteByte(byte(len(b2) + 183)) // Change from use WriteString to use WriteByte 
        buff.WriteString(b2)
    }
}

// FIXME How can I do this "better"?
if interSlice, ok := t.([]interface{}); ok {
    WriteSliceHeader(len(interSlice))
    for _, val := range interSlice {
        buff.Write(Encode(val))
    }
} else if stringSlice, ok := t.([]string); ok {
    WriteSliceHeader(len(stringSlice))
    for _, val := range stringSlice {
        buff.Write(Encode(val))
    }
}

用來處理兩種類型切片[]interface{}[]string,基本上是做一樣的事,程式碼需要優化。用迴圈處理切片內的元素,再次呼叫Encode函式處理,形成類似遞迴的概念。

rlp_test.go

func TestEncode(t *testing.T) {
strRes := "Cdog"
bytes := Encode("dog")
str := string(bytes)
if str != strRes {
t.Error(fmt.Sprintf("Expected %q, got %q", strRes, str))
}
dec,_ := Decode(bytes, 0)
fmt.Printf("raw: %v encoded: %q == %v\n", dec, str, "dog")


sliceRes := "\x83CdogCgodCcat"
strs := []string{"dog", "god", "cat"}
bytes = Encode(strs)
slice := string(bytes)
if slice != sliceRes {
t.Error(fmt.Sprintf("Expected %q, got %q", sliceRes, slice))
}

dec,_ = Decode(bytes, 0)
fmt.Printf("raw: %v encoded: %q == %v\n", dec, slice, strs)
} 

result:

init Ethereum VM
stack size = 256

# processing Tx (8fee28c5311d91212d92cbf14548e9e96ab39a)
# fee = 0.000000, ops = 12, sender = 1234567890, value = 20

# processing Tx (3ab78afb9e495acc6eabd8982730dbb679db2f)
# fee = 0.000000, ops = 2, sender = 1234567890, value = 20
0   67 [10 6 0 0 0 0]
0   67 [10 6 0 0 0 0]
# finished processing Tx

2   66 [10 10 0 0 0 0]
3   67 [255 7 0 0 0 0]
4   81 [20 255 0 0 0 0]
... JMP 7 ...
7   66 [30 31 0 0 0 0]
8   67 [255 22 0 0 0 0]
9   81 [31 255 0 0 0 0]
... JMP 22 ...
# finished processing Tx

rlp encoded Tx "\x01\x00\x010\x00\n1234567890\x00\x010\x00\x0220\x00\x010\x01\x00\x06395843\x00\x06657986\x00\t335612448\x00\x06524099\x00\b16716881\x00\x010\x00\b13114947\x00\a2039362\x00\a1507139\x00\b16719697\x00\a1048387\x00\x0565360"
block enc "\x01\x00\x010\x00\x00\x00\x00\x00 mi\u007f\xb0\b\x91A\xd0P\x1f\xb7\xf9\x1cd\xb1ӑ{\xc2ѕ&X\xa4\u007f\xad\xea\x95\v\xed\xc8="
block hash "39e507d0bc23032af0fc1ad2d979c27d31968fc9ed69c4e3000fed172305e24d"

Process finished with exit code 0

test result:

=== RUN   TestEncode
raw: [100 111 103] encoded: "Cdog" == dog
raw: [[100 111 103] [103 111 100] [99 97 116]] encoded: "\x83CdogCgodCcat" == [dog god cat]
--- PASS: TestEncode (0.00s)
=== RUN   TestRlpEncode
--- PASS: TestRlpEncode (0.00s)
PASS

Process finished with exit code 0