-
Notifications
You must be signed in to change notification settings - Fork 3.1k
/
page.go
126 lines (112 loc) · 2.7 KB
/
page.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
package mipsevm
import (
"bytes"
"compress/zlib"
"encoding/base64"
"encoding/hex"
"encoding/json"
"fmt"
"io"
"sync"
"github.com/ethereum/go-ethereum/crypto"
)
var zlibWriterPool = sync.Pool{
New: func() any {
var buf bytes.Buffer
return zlib.NewWriter(&buf)
},
}
type Page [PageSize]byte
func (p *Page) MarshalJSON() ([]byte, error) { // nosemgrep
var out bytes.Buffer
w := zlibWriterPool.Get().(*zlib.Writer)
defer zlibWriterPool.Put(w)
w.Reset(&out)
if _, err := w.Write(p[:]); err != nil {
return nil, err
}
if err := w.Close(); err != nil {
return nil, err
}
return json.Marshal(out.Bytes())
}
func (p *Page) UnmarshalJSON(dat []byte) error {
// Strip off the `"` characters at the start & end.
dat = dat[1 : len(dat)-1]
// Decode b64 then decompress
r, err := zlib.NewReader(base64.NewDecoder(base64.StdEncoding, bytes.NewReader(dat)))
if err != nil {
return err
}
defer r.Close()
if n, err := r.Read(p[:]); n != PageSize {
return fmt.Errorf("epxeted %d bytes, but got %d", PageSize, n)
} else if err == io.EOF {
return nil
} else {
return err
}
}
func (p *Page) UnmarshalText(dat []byte) error {
if len(dat) != PageSize*2 {
return fmt.Errorf("expected %d hex chars, but got %d", PageSize*2, len(dat))
}
_, err := hex.Decode(p[:], dat)
return err
}
type CachedPage struct {
Data *Page
// intermediate nodes only
Cache [PageSize / 32][32]byte
// true if the intermediate node is valid
Ok [PageSize / 32]bool
}
func (p *CachedPage) Invalidate(pageAddr uint32) {
if pageAddr >= PageSize {
panic("invalid page addr")
}
k := (1 << PageAddrSize) | pageAddr
// first cache layer caches nodes that has two 32 byte leaf nodes.
k >>= 5 + 1
for k > 0 {
p.Ok[k] = false
k >>= 1
}
}
func (p *CachedPage) InvalidateFull() {
p.Ok = [PageSize / 32]bool{} // reset everything to false
}
func (p *CachedPage) MerkleRoot() [32]byte {
// hash the bottom layer
for i := uint64(0); i < PageSize; i += 64 {
j := PageSize/32/2 + i/64
if p.Ok[j] {
continue
}
p.Cache[j] = crypto.Keccak256Hash(p.Data[i : i+64])
//fmt.Printf("0x%x 0x%x -> 0x%x\n", p.Data[i:i+32], p.Data[i+32:i+64], p.Cache[j])
p.Ok[j] = true
}
// hash the cache layers
for i := PageSize/32 - 2; i > 0; i -= 2 {
j := i >> 1
if p.Ok[j] {
continue
}
p.Cache[j] = HashPair(p.Cache[i], p.Cache[i+1])
p.Ok[j] = true
}
return p.Cache[1]
}
func (p *CachedPage) MerkleizeSubtree(gindex uint64) [32]byte {
_ = p.MerkleRoot() // fill cache
if gindex >= PageSize/32 {
if gindex >= PageSize/32*2 {
panic("gindex too deep")
}
// it's pointing to a bottom node
nodeIndex := gindex & (PageAddrMask >> 5)
return *(*[32]byte)(p.Data[nodeIndex*32 : nodeIndex*32+32])
}
return p.Cache[gindex]
}