Line data Source code
1 : /**
2 : * The MIT License (MIT)
3 : *
4 : * Copyright (c) 2021 RSK Labs Ltd
5 : *
6 : * Permission is hereby granted, free of charge, to any person obtaining a copy
7 : * of this software and associated documentation files (the "Software"), to
8 : * deal in the Software without restriction, including without limitation the
9 : * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 : * sell copies of the Software, and to permit persons to whom the Software is
11 : * furnished to do so, subject to the following conditions:
12 : *
13 : * The above copyright notice and this permission notice shall be included in
14 : * all copies or substantial portions of the Software.
15 : *
16 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 : * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 : * IN THE SOFTWARE.
23 : */
24 :
25 : #include <stddef.h>
26 : #include <stdint.h>
27 : #include <string.h>
28 :
29 : #include "srlp.h"
30 :
31 : #include "os.h"
32 :
33 : #include "dbg.h"
34 :
35 : // This code tinkers with function pointers referenced from
36 : // const data structures, so we need to use the PIC macro.
37 : // See:
38 : // https://ledger.readthedocs.io/en/latest/userspace/memory.html?highlight=PIC#pic-and-model-implications
39 :
40 : // Parser state is modeled as a stack of context items of the form:
41 : //
42 : // { state, size, cursor }, where:
43 : //
44 : // - state: signals what the parser is currently parsing
45 : // - size: size in bytes of the structure being parsed
46 : // - cursor: number of bytes consumed for the structure being parsed
47 : //
48 : // At the bottom of the stack there's always a mark used to prevent a
49 : // stack underflow. The stack size is limited to MAX_RLP_CTX_DEPTH
50 : // items (see srlp.h).
51 :
52 : // Context item stack and stack pointer
53 : static uint8_t rlp_ctx_ptr;
54 : static rlp_ctx_t rlp_ctx[MAX_RLP_CTX_DEPTH + 1];
55 :
56 : // Pointer to the beginning of the next chunk to report
57 : static uint8_t* rlp_frame_start;
58 :
59 : // User callbacks
60 : static const rlp_callbacks_t* rlp_callbacks;
61 :
62 : /*
63 : * Initialize the parser.
64 : *
65 : * @arg[in] cbs struct holding callbacks to be called by the parser
66 : */
67 15 : void rlp_start(const rlp_callbacks_t* cbs) {
68 15 : rlp_callbacks = cbs;
69 15 : rlp_ctx_ptr = 0;
70 15 : explicit_bzero(rlp_ctx, sizeof(rlp_ctx));
71 15 : rlp_ctx[rlp_ctx_ptr].state = RLP_BOTTOM;
72 15 : }
73 :
74 : // Notify the user about a trivial bytearray (length = 0 or 1).
75 : // Defined as a macro to save stack space.
76 : #define TRIVIAL_BYTEARRAY(bytearray, len) \
77 : { \
78 : ((rlp_start_cb_t)PIC(rlp_callbacks->bytearray_start))(len); \
79 : ((rlp_chunk_cb_t)PIC(rlp_callbacks->bytearray_chunk))(bytearray, len); \
80 : ((rlp_end_cb_t)PIC(rlp_callbacks->bytearray_end))(); \
81 : }
82 :
83 : // Push a context item to the stack. Defined as a macro to save stack.
84 : // NOTE: Returns if stack overflow.
85 : //
86 : // @arg st state of context item to push
87 : // @arg sz size in bytes of the item top parse
88 : //
89 : #define RLP_PUSH_CTX(st, sz) \
90 : { \
91 : if (rlp_ctx_ptr == MAX_RLP_CTX_DEPTH) { \
92 : return RLP_STACK_OVERFLOW; \
93 : } \
94 : ++rlp_ctx_ptr; \
95 : rlp_ctx[rlp_ctx_ptr].state = (st); \
96 : rlp_ctx[rlp_ctx_ptr].size = (sz); \
97 : rlp_ctx[rlp_ctx_ptr].cursor = 0; \
98 : }
99 :
100 : // Pop current context. Defined as a macro to save stack space.
101 : // NOTE: Returns if stack underflow.
102 : //
103 : #define RLP_POP_CTX() \
104 : { \
105 : if (rlp_ctx_ptr == 0) { \
106 : return RLP_STACK_UNDERFLOW; \
107 : } \
108 : rlp_state_t state = rlp_ctx[rlp_ctx_ptr].state; \
109 : if (state == RLP_LIST) { \
110 : ((rlp_end_cb_t)PIC(rlp_callbacks->list_end))(); \
111 : } else if (state == RLP_STR) { \
112 : ((rlp_end_cb_t)PIC(rlp_callbacks->bytearray_end))(); \
113 : } \
114 : --rlp_ctx_ptr; \
115 : }
116 :
117 : // Called for every consumed byte of the input buffer. Traverse stack from
118 : // top to bottom, incrementing the number of consumed bytes for each list
119 : // context.
120 : // If consumed bytes reaches list size on the top context, pop it.
121 : // If consumed bytes reaches list size on a non-top context, fail due to
122 : // inconsistency.
123 : //
124 : // Defined as a macro to save stack.
125 : // NOTE: Returns if stack underflow
126 : //
127 : #define RLP_UPDATE_LISTS() \
128 : { \
129 : int __ix; \
130 : for (__ix = rlp_ctx_ptr; __ix >= 0; --__ix) { \
131 : if (rlp_ctx[__ix].state != RLP_LIST) { \
132 : continue; \
133 : } \
134 : ++rlp_ctx[__ix].cursor; \
135 : if (rlp_ctx[__ix].cursor == rlp_ctx[__ix].size) { \
136 : if (__ix == rlp_ctx_ptr) { \
137 : RLP_POP_CTX(); \
138 : } else { \
139 : return RLP_MALFORMED; \
140 : } \
141 : } \
142 : } \
143 : }
144 :
145 : // Handle beginning of list. Defined as a macro to save stack space.
146 : #define HANDLE_RLP_LIST(b) \
147 : { \
148 : if (*b <= 0x7F) { \
149 : TRIVIAL_BYTEARRAY(rlp_frame_start, 1); \
150 : } else if (*b == 0x80) { \
151 : TRIVIAL_BYTEARRAY(rlp_frame_start, 0); \
152 : } else if (*b <= 0xB7) { \
153 : RLP_PUSH_CTX(RLP_STR, *b - 0x80); \
154 : ((rlp_start_cb_t)PIC(rlp_callbacks->bytearray_start))(*b - 0x80); \
155 : } else if (*b <= 0xBF) { \
156 : if (*b - 0xB7 > sizeof(uint16_t)) { \
157 : return RLP_TOO_LONG; \
158 : } \
159 : RLP_PUSH_CTX(RLP_STR_LEN, *b - 0xB7); \
160 : } else if (*b <= 0xF7) { \
161 : RLP_PUSH_CTX(RLP_LIST, *b - 0xC0 + 1); \
162 : ((rlp_start_cb_t)PIC(rlp_callbacks->list_start))(*b - 0xC0); \
163 : } else { \
164 : if (*b - 0xF7 > sizeof(uint16_t)) { \
165 : return RLP_TOO_LONG; \
166 : } \
167 : RLP_PUSH_CTX(RLP_LIST_LEN, *b - 0xF7); \
168 : } \
169 : rlp_frame_start = b + 1; \
170 : }
171 :
172 : // Handle beginning of byte array. Defined as a macero to save space.
173 : #define HANDLE_RLP_STR(b) \
174 : { \
175 : ++rlp_ctx[rlp_ctx_ptr].cursor; \
176 : if (rlp_ctx[rlp_ctx_ptr].size == rlp_ctx[rlp_ctx_ptr].cursor) { \
177 : ((rlp_chunk_cb_t)PIC(rlp_callbacks->bytearray_chunk))( \
178 : rlp_frame_start, b - rlp_frame_start + 1); \
179 : RLP_POP_CTX(); \
180 : rlp_frame_start = b + 1; \
181 : } \
182 : }
183 :
184 : /*
185 : * Consume a chunk of bytes.
186 : *
187 : * @arg[in] buf: buffer holdoing bytes to be consumed
188 : * @arg[in] len: number of bytes to consume in buffer
189 : *
190 : * @return
191 : * RLP_OK if bytes were consumed successfully
192 : * RLP_TOO_LONG if len greater than RLP_BUFFER_SIZE
193 : * RLP_STACK_OVERFLOW if list nesting level is greater than MAX_RLP_CTX_DEPTH
194 : * RLP_STACK_UNDERFLOW if RLP to parse is ill-formed (e.g., [[a])
195 : * RLP_MALFORMED if RLP to parse is ill-formed wrt reported sizes
196 : */
197 735 : int rlp_consume(uint8_t* buf, const uint8_t len) {
198 735 : if (len > RLP_BUFFER_SIZE) {
199 0 : return RLP_TOO_LONG;
200 : }
201 :
202 735 : rlp_frame_start = buf;
203 7995 : for (uint8_t i = 0; i < len; ++i) {
204 7261 : uint8_t* b = buf + i;
205 :
206 : LOG_SRLP_CTX(*b, rlp_ctx, rlp_ctx_ptr);
207 :
208 7261 : switch (rlp_ctx[rlp_ctx_ptr].state) {
209 159 : case RLP_BOTTOM:
210 : case RLP_LIST:
211 159 : HANDLE_RLP_LIST(b);
212 159 : break;
213 25 : case RLP_LIST_LEN:
214 25 : if (rlp_ctx[rlp_ctx_ptr].size == 0) {
215 9 : rlp_ctx[rlp_ctx_ptr].state = RLP_LIST;
216 9 : rlp_ctx[rlp_ctx_ptr].size = rlp_ctx[rlp_ctx_ptr].cursor;
217 9 : rlp_ctx[rlp_ctx_ptr].cursor = 0;
218 9 : rlp_frame_start = b;
219 9 : ((rlp_start_cb_t)PIC(rlp_callbacks->list_start))(
220 9 : rlp_ctx[rlp_ctx_ptr].size);
221 9 : HANDLE_RLP_LIST(b);
222 : } else {
223 16 : rlp_ctx[rlp_ctx_ptr].size -= 1;
224 16 : rlp_ctx[rlp_ctx_ptr].cursor =
225 16 : (rlp_ctx[rlp_ctx_ptr].cursor << 8) | *b;
226 : }
227 25 : break;
228 7006 : case RLP_STR:
229 7006 : HANDLE_RLP_STR(b);
230 7006 : break;
231 71 : case RLP_STR_LEN:
232 71 : if (rlp_ctx[rlp_ctx_ptr].size == 0) {
233 29 : rlp_ctx[rlp_ctx_ptr].state = RLP_STR;
234 29 : rlp_ctx[rlp_ctx_ptr].size = rlp_ctx[rlp_ctx_ptr].cursor;
235 29 : rlp_ctx[rlp_ctx_ptr].cursor = 0;
236 29 : rlp_frame_start = b;
237 29 : ((rlp_start_cb_t)PIC(rlp_callbacks->bytearray_start))(
238 29 : rlp_ctx[rlp_ctx_ptr].size);
239 29 : HANDLE_RLP_STR(b);
240 : } else {
241 42 : rlp_ctx[rlp_ctx_ptr].size -= 1;
242 42 : rlp_ctx[rlp_ctx_ptr].cursor =
243 42 : (rlp_ctx[rlp_ctx_ptr].cursor << 8) | *b;
244 : }
245 71 : break;
246 : }
247 :
248 : // Increment consumed bytes for all lists in the context
249 28790 : RLP_UPDATE_LISTS();
250 : }
251 :
252 : // If the item being parsed is a byte array, notify about the seen chunk.
253 734 : if (rlp_ctx[rlp_ctx_ptr].state == RLP_STR) {
254 692 : ((rlp_chunk_cb_t)PIC(rlp_callbacks->bytearray_chunk))(
255 692 : rlp_frame_start, buf + len - rlp_frame_start);
256 : }
257 :
258 734 : return RLP_OK;
259 : }
260 :
261 : /*
262 : * Guess the length in bytes of the RLP prefix for str of the given size.
263 : *
264 : * NOTE: This guessing because for single byte strings we need the str
265 : * value to determine accurately. For single byte strings, this method
266 : * always return one. It's up to the caller to take this into account.
267 : *
268 : * @arg[in] str_size string size
269 : */
270 0 : uint8_t guess_rlp_str_prefix_size(uint16_t str_size) {
271 0 : if (str_size == 0)
272 0 : return 1;
273 0 : else if (str_size == 1)
274 : // Guessing happens here: we should return zero if
275 : // the string's single byte is less or equals 0x7F.
276 0 : return 1;
277 0 : else if (str_size <= 55)
278 0 : return 1;
279 : else {
280 : uint8_t n;
281 0 : for (n = 0; str_size != 0; str_size >>= 8, ++n)
282 : ;
283 0 : return n + 1;
284 : }
285 : }
286 :
287 : /*
288 : * Get the length in bytes of the (minimal) RLP prefix for a list of the
289 : * given size (max size for any given list is 2^16-1 in this
290 : * implementation)
291 : *
292 : * @arg[in] list_size list size
293 : */
294 0 : uint8_t rlp_list_prefix_size(uint16_t list_size) {
295 0 : if (list_size <= 55)
296 0 : return 1;
297 :
298 : uint8_t n;
299 0 : for (n = 0; list_size != 0; list_size >>= 8, ++n)
300 : ;
301 0 : return n + 1;
302 : }
|
