Branch data Line data Source code
1 : : /**
2 : : * @file decoder.c
3 : : * @brief Dictionary lifecycle: open compiled .trp buffer, lookup keys.
4 : : *
5 : : * Copyright (c) 2026 M. A. Chatterjee <deftio at deftio dot com>
6 : : * BSD-2-Clause — see LICENSE.txt
7 : : */
8 : :
9 : : #include "core_internal.h"
10 : :
11 : : /* ── Internal: parse trie config and symbol table ───────────────────── */
12 : :
13 : 551 : static tp_result parse_trie_config(tp_bitstream_reader *r, tp_dict *dict)
14 : : {
15 : : uint64_t val;
16 : : tp_result rc;
17 : :
18 : : /* bits_per_symbol (4 bits) */
19 : 551 : rc = tp_bs_read_bits(r, 4, &val);
20 [ + + ]: 551 : if (rc != TP_OK)
21 : 2 : return rc;
22 : 549 : dict->sym.bits_per_symbol = (uint8_t)val;
23 : 549 : dict->info.bits_per_symbol = (uint8_t)val;
24 : :
25 : : /* symbol_count (8 bits) */
26 : 549 : rc = tp_bs_read_bits(r, 8, &val);
27 [ + + ]: 549 : if (rc != TP_OK)
28 : 2 : return rc;
29 : 547 : dict->sym.symbol_count = (uint16_t)val;
30 : :
31 : : /* special_symbol_map: 6 control codes */
32 : 547 : memset(dict->sym.code_is_ctrl, 0, sizeof(dict->sym.code_is_ctrl));
33 [ + + ]: 3804 : for (int c = 0; c < TP_NUM_CONTROL_CODES; c++) {
34 : 3265 : rc = tp_bs_read_bits(r, dict->sym.bits_per_symbol, &val);
35 [ + + ]: 3265 : if (rc != TP_OK)
36 : 8 : return rc;
37 : 3257 : dict->sym.ctrl_codes[c] = (uint32_t)val;
38 [ + - ]: 3257 : if (val < 256)
39 : 3257 : dict->sym.code_is_ctrl[val] = true;
40 : : }
41 : :
42 : : /* Read symbol table */
43 : 539 : memset(dict->sym.reverse_map, 0, sizeof(dict->sym.reverse_map));
44 : 539 : memset(dict->sym.symbol_map, 0, sizeof(dict->sym.symbol_map));
45 : 539 : uint32_t max_code = dict->sym.symbol_count;
46 [ + + ]: 5393 : for (uint32_t code = TP_NUM_CONTROL_CODES; code < max_code; code++) {
47 : : uint64_t cp;
48 : 4941 : rc = tp_bs_read_varint_u(r, &cp);
49 [ + + ]: 4941 : if (rc != TP_OK)
50 : 87 : return rc;
51 [ + - + + ]: 4854 : if (code < 256 && cp < 256) {
52 : 4814 : dict->sym.reverse_map[code] = (uint8_t)cp;
53 : 4814 : dict->sym.symbol_map[cp] = code;
54 : : }
55 : : }
56 : :
57 : 452 : return TP_OK;
58 : : }
59 : :
60 : : /* ── Open / Close ────────────────────────────────────────────────────── */
61 : :
62 : 633 : static tp_result dict_open_impl(tp_dict **out, const uint8_t *buf, size_t len, bool check_crc)
63 : : {
64 [ + + + + ]: 633 : if (!out || !buf)
65 : 2 : return TP_ERR_INVALID_PARAM;
66 [ + + ]: 631 : if (len < TP_HEADER_SIZE)
67 : 6 : return TP_ERR_TRUNCATED;
68 : :
69 : : /* Parse header */
70 : : /* Allocation failure paths are excluded from coverage (LCOV_EXCL). */
71 : 625 : tp_bitstream_reader *r = NULL;
72 : 625 : tp_result rc = tp_bs_reader_create(&r, buf, (uint64_t)len * 8);
73 [ - + ]: 625 : if (rc != TP_OK)
74 : : return rc; /* LCOV_EXCL_LINE */
75 : :
76 : : tp_header hdr;
77 : 625 : rc = tp_header_read(r, &hdr);
78 [ + + ]: 625 : if (rc != TP_OK) {
79 : 4 : tp_bs_reader_destroy(&r);
80 : 4 : return rc;
81 : : }
82 : :
83 : : /* CRC verification */
84 [ + + + - ]: 621 : if (check_crc && len >= 4) {
85 : 528 : size_t crc_data_len = len - 4;
86 : 528 : uint32_t expected_crc =
87 : 528 : ((uint32_t)buf[crc_data_len] << 24) | ((uint32_t)buf[crc_data_len + 1] << 16) |
88 : 528 : ((uint32_t)buf[crc_data_len + 2] << 8) | ((uint32_t)buf[crc_data_len + 3]);
89 : 528 : uint32_t actual_crc = tp_crc32(buf, crc_data_len);
90 [ + + ]: 528 : if (actual_crc != expected_crc) {
91 : 69 : tp_bs_reader_destroy(&r);
92 : 69 : return TP_ERR_CORRUPT;
93 : : }
94 : : }
95 : :
96 : : /* Check for unsupported features */
97 [ + + ]: 552 : if (hdr.flags & TP_FLAG_HAS_SUFFIX_TABLE) {
98 : 1 : tp_bs_reader_destroy(&r);
99 : 1 : return TP_ERR_VERSION;
100 : : }
101 : :
102 : : /* Allocate dict */
103 : 551 : tp_dict *dict = calloc(1, sizeof(*dict));
104 [ - + ]: 551 : if (!dict) {
105 : : /* LCOV_EXCL_START */
106 : : tp_bs_reader_destroy(&r);
107 : : return TP_ERR_ALLOC;
108 : : /* LCOV_EXCL_STOP */
109 : : }
110 : :
111 : 551 : dict->buf = buf;
112 : 551 : dict->len = len;
113 : 551 : dict->hdr = hdr;
114 : :
115 : : /* Populate info */
116 : 551 : dict->info.format_version_major = hdr.version_major;
117 : 551 : dict->info.format_version_minor = hdr.version_minor;
118 : 551 : dict->info.num_keys = hdr.num_keys;
119 : 551 : dict->info.has_values = (hdr.flags & TP_FLAG_HAS_VALUES) != 0;
120 : 551 : dict->info.has_suffix_table = false;
121 : 551 : dict->info.compact_mode = (hdr.flags & TP_FLAG_COMPACT_MODE) != 0;
122 : 551 : dict->info.total_bytes = len;
123 : 551 : dict->info.checksum_type = TP_CHECKSUM_CRC32;
124 : 551 : dict->info.trie_mode = TP_ADDR_BIT;
125 : 551 : dict->info.value_mode = TP_ADDR_BYTE;
126 : :
127 : : /* Parse trie config and symbol table */
128 : : /* Reader is at bit 256 (byte 32, start of data stream) */
129 : 551 : rc = parse_trie_config(r, dict);
130 [ + + ]: 551 : if (rc != TP_OK) {
131 : 99 : tp_bs_reader_destroy(&r);
132 : 99 : free(dict);
133 : 99 : return rc;
134 : : }
135 : :
136 : 452 : uint64_t data_start = (uint64_t)TP_HEADER_SIZE * 8;
137 : 452 : dict->trie_start = data_start + hdr.trie_data_offset;
138 : 452 : dict->value_start = data_start + hdr.value_store_offset;
139 : :
140 : 452 : tp_bs_reader_destroy(&r);
141 : 452 : *out = dict;
142 : 452 : return TP_OK;
143 : : }
144 : :
145 : 539 : tp_result tp_dict_open(tp_dict **out, const uint8_t *buf, size_t len)
146 : : {
147 : 539 : return dict_open_impl(out, buf, len, true);
148 : : }
149 : :
150 : 94 : tp_result tp_dict_open_unchecked(tp_dict **out, const uint8_t *buf, size_t len)
151 : : {
152 : 94 : return dict_open_impl(out, buf, len, false);
153 : : }
154 : :
155 : 457 : tp_result tp_dict_close(tp_dict **dict)
156 : : {
157 [ + + ]: 457 : if (!dict)
158 : 1 : return TP_ERR_INVALID_PARAM;
159 : 456 : free(*dict);
160 : 456 : *dict = NULL;
161 : 456 : return TP_OK;
162 : : }
163 : :
164 : : /* ── Query ───────────────────────────────────────────────────────────── */
165 : :
166 : 299 : uint32_t tp_dict_count(const tp_dict *dict)
167 : : {
168 [ + + ]: 299 : if (!dict)
169 : 1 : return 0;
170 : 298 : return dict->info.num_keys;
171 : : }
172 : :
173 : : /* ── Lookup ──────────────────────────────────────────────────────────── */
174 : :
175 : 20615 : tp_result tp_dict_lookup(const tp_dict *dict, const char *key, tp_value *val)
176 : : {
177 [ + + - + ]: 20615 : if (!dict || !key)
178 : 1 : return TP_ERR_INVALID_PARAM;
179 : 20614 : return tp_dict_lookup_n(dict, key, strlen(key), val);
180 : : }
181 : :
182 : 21851 : tp_result tp_dict_lookup_n(const tp_dict *dict, const char *key, size_t key_len, tp_value *val)
183 : : {
184 [ + + - + ]: 21851 : if (!dict || !key)
185 : 1 : return TP_ERR_INVALID_PARAM;
186 : :
187 : : /* Empty dictionary: nothing to find */
188 [ + + ]: 21850 : if (dict->info.num_keys == 0)
189 : 2 : return TP_ERR_NOT_FOUND;
190 : :
191 : 21848 : tp_bitstream_reader *r = NULL;
192 : 21848 : tp_result rc = tp_bs_reader_create(&r, dict->buf, (uint64_t)dict->len * 8);
193 [ - + ]: 21848 : if (rc != TP_OK)
194 : : return rc; /* LCOV_EXCL_LINE */
195 : :
196 : 21848 : rc = tp_bs_reader_seek(r, dict->trie_start);
197 [ + + ]: 21848 : if (rc != TP_OK) {
198 : 1 : tp_bs_reader_destroy(&r);
199 : : return rc; /* LCOV_EXCL_LINE */
200 : : }
201 : :
202 : 21847 : uint8_t bps = dict->sym.bits_per_symbol;
203 : 21847 : size_t key_idx = 0;
204 : 21847 : uint32_t value_index = 0;
205 : 21847 : bool found_value = false;
206 : 21847 : bool expect_branch = false; /* set after END/END_VAL when key not consumed */
207 : :
208 : 263005 : while (true) {
209 : : uint64_t sym_raw;
210 : 284852 : rc = tp_bs_read_bits(r, bps, &sym_raw);
211 [ + + ]: 284852 : if (rc != TP_OK) {
212 : 10 : tp_bs_reader_destroy(&r);
213 : : /* If we were expecting a BRANCH after a terminal but hit
214 : : EOF, the key doesn't exist. */
215 [ + + ]: 10 : if (expect_branch)
216 : 10609 : return TP_ERR_NOT_FOUND;
217 : 9 : return rc;
218 : : }
219 : 284842 : uint32_t sym = (uint32_t)sym_raw;
220 : :
221 [ + + ]: 284842 : if (sym == dict->sym.ctrl_codes[TP_CTRL_END]) {
222 [ + + ]: 19535 : if (key_idx == key_len) {
223 : 10067 : tp_bs_reader_destroy(&r);
224 [ + + ]: 10067 : if (val)
225 : 10066 : *val = tp_value_null();
226 : 10067 : return TP_OK;
227 : : }
228 : : /* Key not fully consumed: a BRANCH may follow this terminal
229 : : for children sharing this prefix. */
230 : 9468 : expect_branch = true;
231 : 263005 : continue;
232 : : }
233 : :
234 [ + + ]: 265307 : if (sym == dict->sym.ctrl_codes[TP_CTRL_END_VAL]) {
235 : : uint64_t vi;
236 : 20659 : rc = tp_bs_read_varint_u(r, &vi);
237 [ + + ]: 20659 : if (rc != TP_OK) {
238 : 5 : tp_bs_reader_destroy(&r);
239 : 5 : return rc;
240 : : }
241 [ + + ]: 20654 : if (key_idx == key_len) {
242 : 11238 : value_index = (uint32_t)vi;
243 : 11238 : found_value = true;
244 : 11238 : break;
245 : : }
246 : : /* Key not fully consumed: a BRANCH may follow. */
247 : 9416 : expect_branch = true;
248 : 9416 : continue;
249 : : }
250 : :
251 [ + + ]: 244648 : if (sym == dict->sym.ctrl_codes[TP_CTRL_BRANCH]) {
252 : 121594 : expect_branch = false;
253 : : uint64_t child_count;
254 : 121594 : rc = tp_bs_read_varint_u(r, &child_count);
255 [ + + ]: 121594 : if (rc != TP_OK) {
256 : 4 : tp_bs_reader_destroy(&r);
257 : 222 : return rc;
258 : : }
259 : :
260 [ + + ]: 121590 : if (key_idx >= key_len) {
261 : 47 : tp_bs_reader_destroy(&r);
262 : 47 : return TP_ERR_NOT_FOUND;
263 : : }
264 : :
265 : 121543 : uint8_t target = (uint8_t)key[key_idx];
266 : 121543 : bool found_child = false;
267 : :
268 [ + + ]: 472084 : for (uint64_t ci = 0; ci < child_count; ci++) {
269 : 471966 : bool has_skip = (ci < child_count - 1);
270 : 471966 : uint64_t skip_dist = 0;
271 : :
272 [ + + ]: 471966 : if (has_skip) {
273 : : /* Read SKIP control code */
274 : : uint64_t skip_sym;
275 : 451504 : rc = tp_bs_read_bits(r, bps, &skip_sym);
276 [ + + ]: 451504 : if (rc != TP_OK) {
277 : 3 : tp_bs_reader_destroy(&r);
278 : 9 : return rc;
279 : : }
280 : : /* Read skip distance */
281 : 451501 : rc = tp_bs_read_varint_u(r, &skip_dist);
282 [ + + ]: 451501 : if (rc != TP_OK) {
283 : 6 : tp_bs_reader_destroy(&r);
284 : 6 : return rc;
285 : : }
286 : : }
287 : :
288 : : /* Peek at first symbol of this child */
289 : : uint64_t child_first_sym;
290 : 471957 : rc = tp_bs_peek_bits(r, bps, &child_first_sym);
291 [ + + ]: 471957 : if (rc != TP_OK) {
292 : 4 : tp_bs_reader_destroy(&r);
293 : 4 : return rc;
294 : : }
295 : :
296 : : /* Determine if this is a regular symbol */
297 : 471953 : uint32_t csym = (uint32_t)child_first_sym;
298 [ + - + + ]: 471953 : bool is_ctrl = (csym < 256) && dict->sym.code_is_ctrl[csym];
299 : :
300 [ + + ]: 471953 : if (!is_ctrl) {
301 : : /* It's a regular symbol; check if it matches */
302 : 471844 : uint32_t expected_code = dict->sym.symbol_map[target];
303 [ + + ]: 471844 : if (csym == expected_code) {
304 : : /* Match! Consume this symbol and continue */
305 : 121372 : tp_bs_reader_advance(r, bps);
306 : 121372 : key_idx++;
307 : 121372 : found_child = true;
308 : 121372 : break;
309 : : }
310 : : }
311 : :
312 : : /* Check if it's an END/END_VAL (terminal with no more key
313 : : chars). These can only match if target matches nothing,
314 : : so skip to next sibling. */
315 : :
316 [ + + ]: 350581 : if (has_skip) {
317 : : /* Skip to next sibling */
318 : 350463 : rc = tp_bs_reader_advance(r, skip_dist);
319 [ + + ]: 350463 : if (rc != TP_OK) {
320 : 40 : tp_bs_reader_destroy(&r);
321 : 40 : return rc;
322 : : }
323 : : }
324 : : }
325 : :
326 [ + + ]: 121490 : if (!found_child) {
327 : 118 : tp_bs_reader_destroy(&r);
328 : 118 : return TP_ERR_NOT_FOUND;
329 : : }
330 : 121372 : continue;
331 : : }
332 : :
333 : : /* If we expected a BRANCH after a terminal but got something
334 : : else, the key extends beyond a leaf node — not found. */
335 [ + + ]: 123054 : if (expect_branch) {
336 : 121 : tp_bs_reader_destroy(&r);
337 : 121 : return TP_ERR_NOT_FOUND;
338 : : }
339 : :
340 : : /* Regular symbol */
341 [ + - + + ]: 122933 : if (!dict->sym.code_is_ctrl[sym < 256 ? sym : 0]) {
342 [ + + ]: 122918 : if (key_idx >= key_len) {
343 : 7 : tp_bs_reader_destroy(&r);
344 : 7 : return TP_ERR_NOT_FOUND;
345 : : }
346 : 122911 : uint32_t expected_code = dict->sym.symbol_map[(uint8_t)key[key_idx]];
347 [ + + ]: 122911 : if (sym != expected_code) {
348 : 162 : tp_bs_reader_destroy(&r);
349 : 162 : return TP_ERR_NOT_FOUND;
350 : : }
351 : 122749 : key_idx++;
352 : 122749 : continue;
353 : : }
354 : :
355 : : /* Unknown control code */
356 : 15 : tp_bs_reader_destroy(&r);
357 : 15 : return TP_ERR_INVALID_PARAM;
358 : : }
359 : :
360 : : /* Decode value if found */
361 [ + - + + : 11238 : if (found_value && val && dict->info.has_values) {
+ - ]
362 : : /* Seek to value store and skip to the right value */
363 : 11237 : rc = tp_bs_reader_seek(r, dict->value_start);
364 [ + + ]: 11237 : if (rc != TP_OK) {
365 : 15 : tp_bs_reader_destroy(&r);
366 : 15 : return rc;
367 : : }
368 : :
369 : : /* Skip value_index values */
370 [ + + ]: 50009521 : for (uint32_t i = 0; i < value_index; i++) {
371 : : tp_value tmp;
372 : 49998374 : rc = tp_value_decode(r, &tmp, dict->buf);
373 [ + + ]: 49998374 : if (rc != TP_OK) {
374 : 75 : tp_bs_reader_destroy(&r);
375 : 75 : return rc;
376 : : }
377 : : }
378 : :
379 : 11147 : rc = tp_value_decode(r, val, dict->buf);
380 : 11147 : tp_bs_reader_destroy(&r);
381 : 11147 : return rc;
382 : : }
383 : :
384 : : /* LCOV_EXCL_START — found_value is only set via CTRL_END_VAL which
385 : : implies has_values, so the condition above always takes priority. */
386 : : if (found_value && val) {
387 : : *val = tp_value_null();
388 : : }
389 : : /* LCOV_EXCL_STOP */
390 : :
391 : 1 : tp_bs_reader_destroy(&r);
392 : 1 : return TP_OK;
393 : : }
394 : :
395 : 10037 : tp_result tp_dict_contains(const tp_dict *dict, const char *key, bool *out)
396 : : {
397 [ + + + - : 10037 : if (!dict || !key || !out)
- + ]
398 : 4 : return TP_ERR_INVALID_PARAM;
399 : :
400 : : tp_value val;
401 : 10033 : tp_result rc = tp_dict_lookup(dict, key, &val);
402 [ + + ]: 10033 : if (rc == TP_OK) {
403 : 10021 : *out = true;
404 : 10021 : return TP_OK;
405 : : }
406 [ + + ]: 12 : if (rc == TP_ERR_NOT_FOUND) {
407 : 7 : *out = false;
408 : 7 : return TP_OK;
409 : : }
410 : 5 : return rc;
411 : : }
412 : :
413 : : /* ── Info ────────────────────────────────────────────────────────────── */
414 : :
415 : 8 : tp_result tp_dict_get_info(const tp_dict *dict, tp_dict_info *info)
416 : : {
417 [ + + - + ]: 8 : if (!dict || !info)
418 : 3 : return TP_ERR_INVALID_PARAM;
419 : 5 : *info = dict->info;
420 : 5 : return TP_OK;
421 : : }
422 : :
423 : : /* ── Iteration ──────────────────────────────────────────────────────── */
424 : :
425 : 15 : tp_result tp_dict_iterate(const tp_dict *dict, tp_iterator **out)
426 : : {
427 [ + + - + ]: 15 : if (!dict || !out)
428 : 1 : return TP_ERR_INVALID_PARAM;
429 : :
430 : 14 : tp_iterator *it = calloc(1, sizeof(*it));
431 [ - + ]: 14 : if (!it)
432 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
433 : :
434 : 14 : it->dict = dict;
435 : 14 : it->pos = dict->trie_start;
436 : 14 : it->done = false;
437 : 14 : it->key_buf = malloc(256);
438 [ - + ]: 14 : if (!it->key_buf) {
439 : : /* LCOV_EXCL_START */
440 : : free(it);
441 : : return TP_ERR_ALLOC;
442 : : /* LCOV_EXCL_STOP */
443 : : }
444 : 14 : it->key_buf_cap = 256;
445 : 14 : it->key_len = 0;
446 : 14 : it->stack_top = -1;
447 : 14 : it->started = false;
448 : 14 : *out = it;
449 : 14 : return TP_OK;
450 : : }
451 : :
452 : 8 : tp_result tp_iter_next(tp_iterator *it, const char **key, size_t *key_len, tp_value *val)
453 : : {
454 [ + + ]: 8 : if (!it)
455 : 1 : return TP_ERR_INVALID_PARAM;
456 : :
457 [ + + ]: 7 : if (it->done)
458 : 1 : return TP_ERR_EOF;
459 : :
460 : : /* Simple iteration: scan through all keys using sequential lookup */
461 : : /* For v0.1, we just do a linear scan of sorted entries from the encoder.
462 : : A proper implementation would walk the trie directly. Since we don't
463 : : store the sorted entry list in the dict, we return EOF for now. */
464 : 6 : it->done = true;
465 : : (void)key;
466 : : (void)key_len;
467 : : (void)val;
468 : 6 : return TP_ERR_EOF;
469 : : }
470 : :
471 : 3 : tp_result tp_iter_reset(tp_iterator *it)
472 : : {
473 [ + + ]: 3 : if (!it)
474 : 1 : return TP_ERR_INVALID_PARAM;
475 : 2 : it->pos = it->dict->trie_start;
476 : 2 : it->done = false;
477 : 2 : it->key_len = 0;
478 : 2 : it->stack_top = -1;
479 : 2 : it->started = false;
480 : 2 : return TP_OK;
481 : : }
482 : :
483 : 17 : tp_result tp_iter_destroy(tp_iterator **it)
484 : : {
485 [ + + ]: 17 : if (!it)
486 : 1 : return TP_ERR_INVALID_PARAM;
487 [ + + ]: 16 : if (*it) {
488 : 14 : free((*it)->key_buf);
489 : 14 : free(*it);
490 : 14 : *it = NULL;
491 : : }
492 : 16 : return TP_OK;
493 : : }
494 : :
495 : : /* ── Search ─────────────────────────────────────────────────────────── */
496 : :
497 : 2 : tp_result tp_dict_find_prefix(const tp_dict *dict, const char *prefix, tp_iterator **out)
498 : : {
499 [ + + + - : 2 : if (!dict || !prefix || !out)
- + ]
500 : 1 : return TP_ERR_INVALID_PARAM;
501 : 1 : return tp_dict_iterate(dict, out);
502 : : }
503 : :
504 : 2 : tp_result tp_dict_find_fuzzy(const tp_dict *dict, const char *query, uint8_t max_dist,
505 : : tp_iterator **out)
506 : : {
507 [ + + + - : 2 : if (!dict || !query || !out)
- + ]
508 : 1 : return TP_ERR_INVALID_PARAM;
509 : : (void)max_dist;
510 : 1 : return tp_dict_iterate(dict, out);
511 : : }
512 : :
513 : 3 : tp_result tp_iter_get_distance(const tp_iterator *it, uint8_t *dist)
514 : : {
515 [ + + - + ]: 3 : if (!it || !dist)
516 : 2 : return TP_ERR_INVALID_PARAM;
517 : 1 : *dist = it->distance;
518 : 1 : return TP_OK;
519 : : }
|
