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 <stdint.h>
26 : #include <string.h>
27 : #include "memutil.h"
28 :
29 : #include "trie.h"
30 : #include "svarint.h"
31 : #include "util.h"
32 :
33 : // Context pointer
34 : static trie_ctx_t *ctx;
35 :
36 : /*
37 : * Initialize the parser.
38 : *
39 : * @arg[in] ctx the context to be used for this session
40 : * @arg[in] cb the callback to be used for this session
41 : * @arg[in] length the length of the node in bytes
42 : */
43 274 : void trie_init(trie_ctx_t *_ctx, trie_cb_t _cb, uint32_t length) {
44 274 : ctx = _ctx;
45 274 : memset(ctx, 0, sizeof(trie_ctx_t));
46 274 : ctx->state = TRIE_ST_FLAGS;
47 274 : ctx->callback = _cb;
48 274 : ctx->remaining_bytes = length;
49 274 : }
50 :
51 : /*
52 : * Tell whether parsing is finished, and
53 : * whether it triggered an error (and which one)
54 : * This should be checked after every call to trie_consume
55 : */
56 2543 : int8_t trie_result() {
57 2543 : if (ctx->state < 0 || ctx->state == TRIE_ST_DONE)
58 530 : return ctx->state;
59 2013 : return TRIE_ERR_NONE;
60 : }
61 :
62 : #define NEXT_STATE() \
63 : { \
64 : if (ctx->state < TRIE_ST_SHARED_PREFIX_LENGTH && \
65 : TRIE_FG_SHARED_PREFIX_PRESENT(ctx->flags)) { \
66 : ctx->state = TRIE_ST_SHARED_PREFIX_LENGTH; \
67 : } else if (ctx->state < TRIE_ST_LEFT_NODE && \
68 : TRIE_FG_NODE_PRESENT_LEFT(ctx->flags)) { \
69 : ctx->offset = 0; \
70 : if (TRIE_FG_NODE_IS_EMBEDDED_LEFT(ctx->flags)) \
71 : ctx->state = TRIE_ST_LEFT_NODE_EMBEDDED; \
72 : else \
73 : ctx->state = TRIE_ST_LEFT_NODE; \
74 : } else if (ctx->state < TRIE_ST_RIGHT_NODE && \
75 : TRIE_FG_NODE_PRESENT_RIGHT(ctx->flags)) { \
76 : ctx->offset = 0; \
77 : if (TRIE_FG_NODE_IS_EMBEDDED_RIGHT(ctx->flags)) \
78 : ctx->state = TRIE_ST_RIGHT_NODE_EMBEDDED; \
79 : else \
80 : ctx->state = TRIE_ST_RIGHT_NODE; \
81 : } else if (ctx->state < TRIE_ST_CHILDREN_SIZE && \
82 : (TRIE_FG_NODE_PRESENT_LEFT(ctx->flags) || \
83 : TRIE_FG_NODE_PRESENT_RIGHT(ctx->flags))) { \
84 : svarint_init(&ctx->varint); \
85 : ctx->state = TRIE_ST_CHILDREN_SIZE; \
86 : } else if (ctx->state < TRIE_ST_VALUE) { \
87 : ctx->offset = 0; \
88 : if (TRIE_FG_HAS_LONG_VALUE(ctx->flags)) \
89 : ctx->state = TRIE_ST_LONG_VALUE; \
90 : else if (ctx->remaining_bytes == 0) { \
91 : ctx->state = TRIE_ERR_INVALID; \
92 : return i + 1; \
93 : } else \
94 : ctx->state = TRIE_ST_VALUE; \
95 : } else { \
96 : ctx->state = TRIE_ERR_INVALID; \
97 : return i + 1; \
98 : } \
99 : }
100 :
101 : #define SHARED_PREFIX_TO_BYTES() \
102 : { ctx->length = (ctx->length - 1) / 8 + 1; }
103 :
104 : /*
105 : * Consume a chunk of bytes.
106 : *
107 : * @arg[in] buf: buffer holding bytes to be consumed
108 : * @arg[in] len: number of bytes to consume in buffer
109 : *
110 : * @return the number of bytes actually read and processed
111 : */
112 2246 : uint8_t trie_consume(uint8_t *buf, const uint8_t len) {
113 : uint8_t processed;
114 :
115 17119 : for (uint8_t i = 0; i < len; i++) {
116 15146 : switch (ctx->state) {
117 273 : case TRIE_ST_FLAGS:
118 273 : ctx->raw[0] = buf[i];
119 273 : ctx->raw_size = 1;
120 273 : --ctx->remaining_bytes;
121 273 : ctx->flags = buf[i];
122 273 : ctx->callback(TRIE_EV_FLAGS);
123 267 : NEXT_STATE();
124 266 : break;
125 112 : case TRIE_ST_SHARED_PREFIX_LENGTH:
126 112 : ctx->raw[0] = buf[i];
127 112 : ctx->raw_size = 1;
128 112 : --ctx->remaining_bytes;
129 112 : ctx->state = TRIE_ST_SHARED_PREFIX;
130 112 : if (/*buf[i] >= 0 &&*/ buf[i] <= 31) {
131 69 : ctx->length = buf[i] + 1;
132 69 : ctx->callback(TRIE_EV_SHARED_PREFIX_LENGTH);
133 69 : SHARED_PREFIX_TO_BYTES();
134 43 : } else if (buf[i] >= 32 && buf[i] <= 254) {
135 6 : ctx->length = buf[i] + 128;
136 6 : ctx->callback(TRIE_EV_SHARED_PREFIX_LENGTH);
137 6 : SHARED_PREFIX_TO_BYTES();
138 : } else {
139 37 : ctx->state = TRIE_ST_SHARED_PREFIX_LENGTH_VAR;
140 37 : svarint_init(&ctx->varint);
141 : }
142 112 : break;
143 58 : case TRIE_ST_SHARED_PREFIX_LENGTH_VAR:
144 58 : processed = svarint_consume(buf + i, len - i);
145 116 : SAFE_MEMMOVE(ctx->raw,
146 : sizeof(ctx->raw),
147 : ctx->raw_size,
148 : buf,
149 : len,
150 : i,
151 : processed,
152 : {
153 : ctx->state = TRIE_ERR_INVALID;
154 : return processed;
155 : });
156 58 : ctx->raw_size += processed;
157 58 : i += processed - 1;
158 58 : ctx->remaining_bytes -= processed;
159 :
160 58 : switch (svarint_result()) {
161 36 : case SVARINT_ST_DONE:
162 36 : ctx->length = ctx->varint.value;
163 36 : ctx->callback(TRIE_EV_SHARED_PREFIX_LENGTH);
164 36 : SHARED_PREFIX_TO_BYTES();
165 36 : ctx->state = TRIE_ST_SHARED_PREFIX;
166 36 : break;
167 1 : case SVARINT_ERR_UNSUPPORTED:
168 1 : ctx->state = TRIE_ERR_UNSUPPORTED;
169 1 : return i + 1;
170 0 : case SVARINT_ERR_INVALID:
171 0 : ctx->state = TRIE_ERR_INVALID;
172 0 : return i + 1;
173 : }
174 57 : break;
175 884 : case TRIE_ST_SHARED_PREFIX:
176 884 : ctx->raw_size = 1;
177 884 : ctx->raw[0] = buf[i];
178 884 : --ctx->remaining_bytes;
179 884 : ctx->callback(TRIE_EV_SHARED_PREFIX);
180 884 : if (--ctx->length == 0) {
181 111 : NEXT_STATE();
182 : }
183 884 : break;
184 2816 : case TRIE_ST_LEFT_NODE:
185 : case TRIE_ST_RIGHT_NODE:
186 2816 : if (ctx->offset == 0) {
187 88 : ctx->raw_size = 0;
188 88 : ctx->callback(ctx->state == TRIE_ST_LEFT_NODE
189 : ? TRIE_EV_LEFT_NODE_START
190 : : TRIE_EV_RIGHT_NODE_START);
191 : }
192 2816 : ctx->raw[0] = buf[i];
193 2816 : ctx->raw_size = 1;
194 2816 : --ctx->remaining_bytes;
195 2816 : ctx->callback(ctx->state == TRIE_ST_LEFT_NODE
196 : ? TRIE_EV_LEFT_NODE_DATA
197 : : TRIE_EV_RIGHT_NODE_DATA);
198 2816 : if (++ctx->offset == NON_EMBEDDED_NODE_SIZE) {
199 88 : ctx->raw_size = 0;
200 88 : ctx->callback(ctx->state == TRIE_ST_LEFT_NODE
201 : ? TRIE_EV_LEFT_NODE_END
202 : : TRIE_EV_RIGHT_NODE_END);
203 88 : NEXT_STATE();
204 : }
205 2816 : break;
206 6788 : case TRIE_ST_LEFT_NODE_EMBEDDED:
207 : case TRIE_ST_RIGHT_NODE_EMBEDDED:
208 6788 : ctx->raw[0] = buf[i];
209 6788 : ctx->raw_size = 1;
210 6788 : --ctx->remaining_bytes;
211 6788 : if (ctx->offset == 0) {
212 178 : ctx->offset = MIN(buf[i], MAX_EMBEDDED_SIZE);
213 178 : ctx->length = (uint32_t)ctx->offset;
214 178 : ctx->callback(ctx->state == TRIE_ST_LEFT_NODE_EMBEDDED
215 : ? TRIE_EV_LEFT_NODE_EMBEDDED_START
216 : : TRIE_EV_RIGHT_NODE_EMBEDDED_START);
217 : } else {
218 6610 : ctx->callback(ctx->state == TRIE_ST_LEFT_NODE_EMBEDDED
219 : ? TRIE_EV_LEFT_NODE_EMBEDDED_DATA
220 : : TRIE_EV_RIGHT_NODE_EMBEDDED_DATA);
221 6610 : if (--ctx->offset == 0) {
222 178 : ctx->raw_size = 0;
223 178 : ctx->callback(ctx->state == TRIE_ST_LEFT_NODE_EMBEDDED
224 : ? TRIE_EV_LEFT_NODE_EMBEDDED_END
225 : : TRIE_EV_RIGHT_NODE_EMBEDDED_END);
226 178 : NEXT_STATE();
227 : }
228 : }
229 6788 : break;
230 214 : case TRIE_ST_CHILDREN_SIZE:
231 214 : if (svarint_notstarted())
232 154 : ctx->raw_size = 0;
233 214 : processed = svarint_consume(buf + i, len - i);
234 428 : SAFE_MEMMOVE(ctx->raw,
235 : sizeof(ctx->raw),
236 : ctx->raw_size,
237 : buf,
238 : len,
239 : i,
240 : processed,
241 : {
242 : ctx->state = TRIE_ERR_INVALID;
243 : return processed;
244 : });
245 214 : ctx->raw_size += processed;
246 214 : i += processed - 1;
247 214 : ctx->remaining_bytes -= processed;
248 :
249 214 : switch (svarint_result()) {
250 142 : case SVARINT_ST_DONE:
251 142 : ctx->children_size = ctx->varint.value;
252 142 : ctx->callback(TRIE_EV_CHILDREN_SIZE);
253 142 : if (ctx->remaining_bytes == 0 &&
254 142 : !TRIE_FG_HAS_LONG_VALUE(ctx->flags)) {
255 142 : ctx->state = TRIE_ST_DONE;
256 142 : return i + 1;
257 : } else {
258 0 : NEXT_STATE();
259 : }
260 0 : break;
261 12 : case SVARINT_ERR_UNSUPPORTED:
262 12 : ctx->state = TRIE_ERR_UNSUPPORTED;
263 12 : return i + 1;
264 0 : case SVARINT_ERR_INVALID:
265 0 : ctx->state = TRIE_ERR_INVALID;
266 0 : return i + 1;
267 : }
268 60 : break;
269 431 : case TRIE_ST_VALUE:
270 431 : if (ctx->offset == 0)
271 9 : ctx->callback(TRIE_EV_VALUE_START);
272 431 : ctx->raw[0] = buf[i];
273 431 : ctx->raw_size = 1;
274 431 : --ctx->remaining_bytes;
275 431 : ++ctx->offset;
276 431 : ctx->callback(TRIE_EV_VALUE_DATA);
277 431 : if (ctx->remaining_bytes == 0) {
278 9 : ctx->callback(TRIE_EV_VALUE_END);
279 9 : ctx->state = TRIE_ST_DONE;
280 9 : return i + 1;
281 : }
282 422 : break;
283 3570 : case TRIE_ST_LONG_VALUE:
284 3570 : --ctx->remaining_bytes;
285 3570 : if (ctx->offset == 0) {
286 102 : ctx->raw_size = 0;
287 102 : ctx->callback(TRIE_EV_VALUE_HASH_START);
288 : }
289 3570 : if (ctx->offset < VALUE_HASH_SIZE) {
290 3264 : ctx->raw[0] = buf[i];
291 3264 : ctx->raw_size = 1;
292 3264 : ctx->callback(TRIE_EV_VALUE_HASH_DATA);
293 3264 : ++ctx->offset;
294 3264 : ctx->value_size = 0;
295 3264 : ctx->raw_size = 0;
296 : } else {
297 306 : ctx->value_size = (ctx->value_size << 8) + buf[i];
298 306 : ctx->raw[ctx->raw_size++] = buf[i];
299 306 : if (++ctx->offset == VALUE_HASH_SIZE + VALUE_LENGTH_SIZE) {
300 102 : ctx->callback(TRIE_EV_VALUE_HASH_END);
301 100 : ctx->state = ctx->remaining_bytes == 0 ? TRIE_ST_DONE
302 : : TRIE_ERR_INVALID;
303 100 : return i + 1;
304 : }
305 : }
306 3468 : break;
307 0 : default:
308 0 : return 0;
309 : }
310 : }
311 :
312 1973 : return len;
313 : }
|
