-
Notifications
You must be signed in to change notification settings - Fork 57
/
RLPReader.sol
354 lines (295 loc) · 10.4 KB
/
RLPReader.sol
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
// SPDX-License-Identifier: Apache-2.0
/*
* @author Hamdi Allam hamdi.allam97@gmail.com
* Please reach out with any questions or concerns
*/
pragma solidity >=0.5.10 <0.9.0;
library RLPReader {
uint8 constant STRING_SHORT_START = 0x80;
uint8 constant STRING_LONG_START = 0xb8;
uint8 constant LIST_SHORT_START = 0xc0;
uint8 constant LIST_LONG_START = 0xf8;
uint8 constant WORD_SIZE = 32;
struct RLPItem {
uint256 len;
uint256 memPtr;
}
struct Iterator {
RLPItem item; // Item that's being iterated over.
uint256 nextPtr; // Position of the next item in the list.
}
/*
* @dev Returns the next element in the iteration. Reverts if it has not next element.
* @param self The iterator.
* @return The next element in the iteration.
*/
function next(Iterator memory self) internal pure returns (RLPItem memory) {
require(hasNext(self));
uint256 ptr = self.nextPtr;
uint256 itemLength = _itemLength(ptr);
self.nextPtr = ptr + itemLength;
return RLPItem(itemLength, ptr);
}
/*
* @dev Returns true if the iteration has more elements.
* @param self The iterator.
* @return true if the iteration has more elements.
*/
function hasNext(Iterator memory self) internal pure returns (bool) {
RLPItem memory item = self.item;
return self.nextPtr < item.memPtr + item.len;
}
/*
* @param item RLP encoded bytes
*/
function toRlpItem(bytes memory item) internal pure returns (RLPItem memory) {
uint256 memPtr;
assembly {
memPtr := add(item, 0x20)
}
return RLPItem(item.length, memPtr);
}
/*
* @dev Create an iterator. Reverts if item is not a list.
* @param self The RLP item.
* @return An 'Iterator' over the item.
*/
function iterator(RLPItem memory self) internal pure returns (Iterator memory) {
require(isList(self));
uint256 ptr = self.memPtr + _payloadOffset(self.memPtr);
return Iterator(self, ptr);
}
/*
* @param the RLP item.
*/
function rlpLen(RLPItem memory item) internal pure returns (uint256) {
return item.len;
}
/*
* @param the RLP item.
* @return (memPtr, len) pair: location of the item's payload in memory.
*/
function payloadLocation(RLPItem memory item) internal pure returns (uint256, uint256) {
uint256 offset = _payloadOffset(item.memPtr);
uint256 memPtr = item.memPtr + offset;
uint256 len = item.len - offset; // data length
return (memPtr, len);
}
/*
* @param the RLP item.
*/
function payloadLen(RLPItem memory item) internal pure returns (uint256) {
(, uint256 len) = payloadLocation(item);
return len;
}
/*
* @param the RLP item containing the encoded list.
*/
function toList(RLPItem memory item) internal pure returns (RLPItem[] memory) {
require(isList(item));
uint256 items = numItems(item);
RLPItem[] memory result = new RLPItem[](items);
uint256 memPtr = item.memPtr + _payloadOffset(item.memPtr);
uint256 dataLen;
for (uint256 i = 0; i < items; i++) {
dataLen = _itemLength(memPtr);
result[i] = RLPItem(dataLen, memPtr);
memPtr = memPtr + dataLen;
}
return result;
}
// @return indicator whether encoded payload is a list. negate this function call for isData.
function isList(RLPItem memory item) internal pure returns (bool) {
if (item.len == 0) return false;
uint8 byte0;
uint256 memPtr = item.memPtr;
assembly {
byte0 := byte(0, mload(memPtr))
}
if (byte0 < LIST_SHORT_START) return false;
return true;
}
/*
* @dev A cheaper version of keccak256(toRlpBytes(item)) that avoids copying memory.
* @return keccak256 hash of RLP encoded bytes.
*/
function rlpBytesKeccak256(RLPItem memory item) internal pure returns (bytes32) {
uint256 ptr = item.memPtr;
uint256 len = item.len;
bytes32 result;
assembly {
result := keccak256(ptr, len)
}
return result;
}
/*
* @dev A cheaper version of keccak256(toBytes(item)) that avoids copying memory.
* @return keccak256 hash of the item payload.
*/
function payloadKeccak256(RLPItem memory item) internal pure returns (bytes32) {
(uint256 memPtr, uint256 len) = payloadLocation(item);
bytes32 result;
assembly {
result := keccak256(memPtr, len)
}
return result;
}
/** RLPItem conversions into data types **/
// @returns raw rlp encoding in bytes
function toRlpBytes(RLPItem memory item) internal pure returns (bytes memory) {
bytes memory result = new bytes(item.len);
if (result.length == 0) return result;
uint256 ptr;
assembly {
ptr := add(0x20, result)
}
copy(item.memPtr, ptr, item.len);
return result;
}
// any non-zero byte except "0x80" is considered true
function toBoolean(RLPItem memory item) internal pure returns (bool) {
require(item.len == 1);
uint256 result;
uint256 memPtr = item.memPtr;
assembly {
result := byte(0, mload(memPtr))
}
// SEE Github Issue #5.
// Summary: Most commonly used RLP libraries (i.e Geth) will encode
// "0" as "0x80" instead of as "0". We handle this edge case explicitly
// here.
if (result == 0 || result == STRING_SHORT_START) {
return false;
} else {
return true;
}
}
function toAddress(RLPItem memory item) internal pure returns (address) {
// 1 byte for the length prefix
require(item.len == 21);
return address(uint160(toUint(item)));
}
function toUint(RLPItem memory item) internal pure returns (uint256) {
require(item.len > 0 && item.len <= 33);
(uint256 memPtr, uint256 len) = payloadLocation(item);
uint256 result;
assembly {
result := mload(memPtr)
// shift to the correct location if neccesary
if lt(len, 32) {
result := div(result, exp(256, sub(32, len)))
}
}
return result;
}
// enforces 32 byte length
function toUintStrict(RLPItem memory item) internal pure returns (uint256) {
// one byte prefix
require(item.len == 33);
uint256 result;
uint256 memPtr = item.memPtr + 1;
assembly {
result := mload(memPtr)
}
return result;
}
function toBytes(RLPItem memory item) internal pure returns (bytes memory) {
require(item.len > 0);
(uint256 memPtr, uint256 len) = payloadLocation(item);
bytes memory result = new bytes(len);
uint256 destPtr;
assembly {
destPtr := add(0x20, result)
}
copy(memPtr, destPtr, len);
return result;
}
/*
* Private Helpers
*/
// @return number of payload items inside an encoded list.
function numItems(RLPItem memory item) private pure returns (uint256) {
if (item.len == 0) return 0;
uint256 count = 0;
uint256 currPtr = item.memPtr + _payloadOffset(item.memPtr);
uint256 endPtr = item.memPtr + item.len;
while (currPtr < endPtr) {
currPtr = currPtr + _itemLength(currPtr); // skip over an item
count++;
}
return count;
}
// @return entire rlp item byte length
function _itemLength(uint256 memPtr) private pure returns (uint256) {
uint256 itemLen;
uint256 byte0;
assembly {
byte0 := byte(0, mload(memPtr))
}
if (byte0 < STRING_SHORT_START) {
itemLen = 1;
} else if (byte0 < STRING_LONG_START) {
itemLen = byte0 - STRING_SHORT_START + 1;
} else if (byte0 < LIST_SHORT_START) {
assembly {
let byteLen := sub(byte0, 0xb7) // # of bytes the actual length is
memPtr := add(memPtr, 1) // skip over the first byte
/* 32 byte word size */
let dataLen := div(mload(memPtr), exp(256, sub(32, byteLen))) // right shifting to get the len
itemLen := add(dataLen, add(byteLen, 1))
}
} else if (byte0 < LIST_LONG_START) {
itemLen = byte0 - LIST_SHORT_START + 1;
} else {
assembly {
let byteLen := sub(byte0, 0xf7)
memPtr := add(memPtr, 1)
let dataLen := div(mload(memPtr), exp(256, sub(32, byteLen))) // right shifting to the correct length
itemLen := add(dataLen, add(byteLen, 1))
}
}
return itemLen;
}
// @return number of bytes until the data
function _payloadOffset(uint256 memPtr) private pure returns (uint256) {
uint256 byte0;
assembly {
byte0 := byte(0, mload(memPtr))
}
if (byte0 < STRING_SHORT_START) {
return 0;
} else if (byte0 < STRING_LONG_START || (byte0 >= LIST_SHORT_START && byte0 < LIST_LONG_START)) {
return 1;
} else if (byte0 < LIST_SHORT_START) {
// being explicit
return byte0 - (STRING_LONG_START - 1) + 1;
} else {
return byte0 - (LIST_LONG_START - 1) + 1;
}
}
/*
* @param src Pointer to source
* @param dest Pointer to destination
* @param len Amount of memory to copy from the source
*/
function copy(uint256 src, uint256 dest, uint256 len) private pure {
if (len == 0) return;
// copy as many word sizes as possible
for (; len >= WORD_SIZE; len -= WORD_SIZE) {
assembly {
mstore(dest, mload(src))
}
src += WORD_SIZE;
dest += WORD_SIZE;
}
if (len > 0) {
// left over bytes. Mask is used to remove unwanted bytes from the word
uint256 mask = 256**(WORD_SIZE - len) - 1;
assembly {
let srcpart := and(mload(src), not(mask)) // zero out src
let destpart := and(mload(dest), mask) // retrieve the bytes
mstore(dest, or(destpart, srcpart))
}
}
}
}