Branch data Line data Source code
1 : : /**
2 : : * @file encoder.c
3 : : * @brief Encoder lifecycle: accumulate key/value pairs, build compressed trie.
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 : : /* ── Value deep copy / free helpers ───────────────────────────────────── */
12 : :
13 : : /**
14 : : * Deep-copy heap-referencing data (string/blob) inside a tp_value so
15 : : * the encoder owns it. Must be paired with value_free_copy().
16 : : */
17 : 20785 : static tp_result value_deep_copy(tp_value *v)
18 : : {
19 [ + + + + ]: 20785 : if (v->type == TP_STRING && v->data.string_val.str) {
20 : 56 : size_t len = v->data.string_val.str_len;
21 : 56 : char *copy = malloc(len + 1);
22 [ - + ]: 56 : if (!copy)
23 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
24 : 56 : memcpy(copy, v->data.string_val.str, len);
25 : 56 : copy[len] = '\0';
26 : 56 : v->data.string_val.str = copy;
27 [ + + + + : 20729 : } else if (v->type == TP_BLOB && v->data.blob_val.data && v->data.blob_val.len > 0) {
+ - ]
28 : 6 : size_t len = v->data.blob_val.len;
29 : 6 : uint8_t *copy = malloc(len);
30 [ - + ]: 6 : if (!copy)
31 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
32 : 6 : memcpy(copy, v->data.blob_val.data, len);
33 : 6 : v->data.blob_val.data = copy;
34 : : }
35 : 20785 : return TP_OK;
36 : : }
37 : :
38 : : /** Free deep-copied data inside a tp_value. */
39 : 20785 : static void value_free_copy(tp_value *v)
40 : : {
41 [ + + + + ]: 20785 : if (v->type == TP_STRING && v->data.string_val.str) {
42 : 56 : free((void *)v->data.string_val.str);
43 : 56 : v->data.string_val.str = NULL;
44 [ + + + + ]: 20729 : } else if (v->type == TP_BLOB && v->data.blob_val.data) {
45 : 6 : free((void *)v->data.blob_val.data);
46 : 6 : v->data.blob_val.data = NULL;
47 : : }
48 : 20785 : }
49 : :
50 : : /* ── Defaults ────────────────────────────────────────────────────────── */
51 : :
52 : 235 : tp_encoder_options tp_encoder_defaults(void)
53 : : {
54 : : tp_encoder_options opts;
55 : 235 : memset(&opts, 0, sizeof(opts));
56 : 235 : opts.trie_mode = TP_ADDR_BIT;
57 : 235 : opts.value_mode = TP_ADDR_BYTE;
58 : 235 : opts.checksum = TP_CHECKSUM_CRC32;
59 : 235 : opts.enable_suffix = false; /* not implemented yet */
60 : 235 : opts.compact_mode = false;
61 : 235 : opts.bits_per_symbol = 0; /* auto */
62 : 235 : return opts;
63 : : }
64 : :
65 : : /* ── Create / Destroy ────────────────────────────────────────────────── */
66 : :
67 : 234 : tp_result tp_encoder_create(tp_encoder **out)
68 : : {
69 [ + + ]: 234 : if (!out)
70 : 1 : return TP_ERR_INVALID_PARAM;
71 : :
72 : 233 : tp_encoder_options opts = tp_encoder_defaults();
73 : 233 : return tp_encoder_create_ex(out, &opts);
74 : : }
75 : :
76 : 237 : tp_result tp_encoder_create_ex(tp_encoder **out, const tp_encoder_options *opts)
77 : : {
78 [ + + + + ]: 237 : if (!out || !opts)
79 : 3 : return TP_ERR_INVALID_PARAM;
80 : :
81 : : /* Allocation failure paths are excluded from coverage (LCOV_EXCL). */
82 : 234 : tp_encoder *enc = calloc(1, sizeof(*enc));
83 [ - + ]: 234 : if (!enc)
84 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
85 : :
86 : 234 : enc->opts = *opts;
87 : 234 : enc->count = 0;
88 : 234 : enc->entries = NULL;
89 : 234 : enc->entries_cap = 0;
90 : 234 : enc->sorted = false;
91 : 234 : *out = enc;
92 : 234 : return TP_OK;
93 : : }
94 : :
95 : 238 : tp_result tp_encoder_destroy(tp_encoder **enc)
96 : : {
97 [ + + ]: 238 : if (!enc)
98 : 1 : return TP_ERR_INVALID_PARAM;
99 [ + + ]: 237 : if (*enc) {
100 [ + + ]: 20973 : for (uint32_t i = 0; i < (*enc)->count; i++) {
101 : 20739 : value_free_copy(&(*enc)->entries[i].val);
102 : 20739 : free((*enc)->entries[i].key);
103 : : }
104 : 234 : free((*enc)->entries);
105 : 234 : free(*enc);
106 : 234 : *enc = NULL;
107 : : }
108 : 237 : return TP_OK;
109 : : }
110 : :
111 : : /* ── Add entries ─────────────────────────────────────────────────────── */
112 : :
113 : 20601 : tp_result tp_encoder_add(tp_encoder *enc, const char *key, const tp_value *val)
114 : : {
115 [ + + + + ]: 20601 : if (!enc || !key)
116 : 2 : return TP_ERR_INVALID_PARAM;
117 : 20599 : return tp_encoder_add_n(enc, key, strlen(key), val);
118 : : }
119 : :
120 : 20787 : tp_result tp_encoder_add_n(tp_encoder *enc, const char *key, size_t key_len, const tp_value *val)
121 : : {
122 [ + + + + ]: 20787 : if (!enc || !key)
123 : 2 : return TP_ERR_INVALID_PARAM;
124 : :
125 : : /* Grow entries array if needed */
126 [ + + ]: 20785 : if (enc->count >= enc->entries_cap) {
127 [ + + ]: 235 : size_t new_cap = enc->entries_cap == 0 ? 16 : enc->entries_cap * 2;
128 : 235 : tp_entry *new_entries = realloc(enc->entries, new_cap * sizeof(tp_entry));
129 [ - + ]: 235 : if (!new_entries)
130 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
131 : 235 : enc->entries = new_entries;
132 : 235 : enc->entries_cap = new_cap;
133 : : }
134 : :
135 : : /* Copy key */
136 : 20785 : char *key_copy = malloc(key_len + 1);
137 [ - + ]: 20785 : if (!key_copy)
138 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
139 : 20785 : memcpy(key_copy, key, key_len);
140 : 20785 : key_copy[key_len] = '\0';
141 : :
142 : 20785 : tp_entry *e = &enc->entries[enc->count];
143 : 20785 : e->key = key_copy;
144 : 20785 : e->key_len = key_len;
145 [ + + ]: 20785 : if (val)
146 : 10756 : e->val = *val;
147 : : else
148 : 10029 : e->val = tp_value_null();
149 : :
150 : : /* Deep-copy string/blob data so the encoder owns it */
151 : 20785 : tp_result vrc = value_deep_copy(&e->val);
152 [ - + ]: 20785 : if (vrc != TP_OK) {
153 : : /* LCOV_EXCL_START */
154 : : free(key_copy);
155 : : return vrc;
156 : : /* LCOV_EXCL_STOP */
157 : : }
158 : :
159 : 20785 : enc->count++;
160 : 20785 : enc->sorted = false;
161 : 20785 : return TP_OK;
162 : : }
163 : :
164 : : /* ── Query ───────────────────────────────────────────────────────────── */
165 : :
166 : 7 : uint32_t tp_encoder_count(const tp_encoder *enc)
167 : : {
168 [ + + ]: 7 : if (!enc)
169 : 1 : return 0;
170 : 6 : return enc->count;
171 : : }
172 : :
173 : : /* ── Sort entries ────────────────────────────────────────────────────── */
174 : :
175 : 184360 : static int entry_cmp(const void *a, const void *b)
176 : : {
177 : 184360 : const tp_entry *ea = (const tp_entry *)a;
178 : 184360 : const tp_entry *eb = (const tp_entry *)b;
179 : 184360 : size_t min_len = ea->key_len < eb->key_len ? ea->key_len : eb->key_len;
180 : 184360 : int cmp = memcmp(ea->key, eb->key, min_len);
181 [ + + ]: 184360 : if (cmp != 0)
182 : 183337 : return cmp;
183 [ + + ]: 1023 : if (ea->key_len < eb->key_len)
184 : 1019 : return -1;
185 [ - + ]: 4 : if (ea->key_len > eb->key_len)
186 : 0 : return 1;
187 : 4 : return 0;
188 : : }
189 : :
190 : 208 : static void sort_entries(tp_encoder *enc)
191 : : {
192 [ + + ]: 208 : if (enc->count > 1)
193 : 116 : qsort(enc->entries, enc->count, sizeof(tp_entry), entry_cmp);
194 : 208 : enc->sorted = true;
195 : 208 : }
196 : :
197 : : /* Remove duplicate keys (keep last added) */
198 : 208 : static void dedup_entries(tp_encoder *enc)
199 : : {
200 [ + + ]: 208 : if (enc->count <= 1)
201 : 92 : return;
202 : 116 : uint32_t write = 0;
203 [ + + ]: 20808 : for (uint32_t i = 0; i < enc->count; i++) {
204 [ + + + + ]: 20692 : if (i + 1 < enc->count && enc->entries[i].key_len == enc->entries[i + 1].key_len &&
205 [ + + ]: 8915 : memcmp(enc->entries[i].key, enc->entries[i + 1].key, enc->entries[i].key_len) == 0) {
206 : 4 : value_free_copy(&enc->entries[i].val);
207 : 4 : free(enc->entries[i].key);
208 : 4 : continue;
209 : : }
210 [ + + ]: 20688 : if (write != i)
211 : 3 : enc->entries[write] = enc->entries[i];
212 : 20688 : write++;
213 : : }
214 : 116 : enc->count = write;
215 : : }
216 : :
217 : : /* ── Symbol analysis ─────────────────────────────────────────────────── */
218 : :
219 : 208 : static void analyze_symbols(tp_encoder *enc)
220 : : {
221 : 208 : tp_symbol_info *sym = &enc->sym;
222 : 208 : memset(sym, 0, sizeof(*sym));
223 : :
224 : 208 : bool used[256] = {false};
225 : :
226 : : /* Scan all keys to find used byte values */
227 [ + + ]: 20984 : for (uint32_t i = 0; i < enc->count; i++) {
228 [ + + ]: 261231 : for (size_t j = 0; j < enc->entries[i].key_len; j++) {
229 : 240455 : used[(uint8_t)enc->entries[i].key[j]] = true;
230 : : }
231 : : }
232 : :
233 : : /* Count alphabet size */
234 : 208 : sym->alphabet_size = 0;
235 [ + + ]: 53456 : for (int i = 0; i < 256; i++) {
236 [ + + ]: 53248 : if (used[i])
237 : 1217 : sym->alphabet_size++;
238 : : }
239 : :
240 : : /* Determine bits_per_symbol */
241 : 208 : uint16_t total_symbols = sym->alphabet_size + TP_NUM_CONTROL_CODES;
242 : 208 : uint8_t bps = enc->opts.bits_per_symbol;
243 [ + - ]: 208 : if (bps == 0) {
244 : : /* Auto: find minimum bits to cover all symbols */
245 : 208 : bps = 1;
246 [ + + ]: 813 : while (((uint16_t)1 << bps) < total_symbols)
247 : 605 : bps++;
248 : : }
249 : 208 : sym->bits_per_symbol = bps;
250 : 208 : sym->symbol_count = total_symbols;
251 : :
252 : : /* Assign control codes to the first slots */
253 [ + + ]: 1456 : for (int c = 0; c < TP_NUM_CONTROL_CODES; c++) {
254 : 1248 : sym->ctrl_codes[c] = (uint32_t)c;
255 : 1248 : sym->code_is_ctrl[c] = true;
256 : : }
257 : :
258 : : /* Assign alphabet symbols starting after control codes */
259 : 208 : uint32_t code = TP_NUM_CONTROL_CODES;
260 [ + + ]: 53456 : for (int i = 0; i < 256; i++) {
261 [ + + ]: 53248 : if (used[i]) {
262 : 1217 : sym->symbol_map[i] = code;
263 [ + - ]: 1217 : if (code < 256)
264 : 1217 : sym->reverse_map[code] = (uint8_t)i;
265 : 1217 : code++;
266 : : }
267 : : }
268 : 208 : }
269 : :
270 : : /* ── Trie encoding ───────────────────────────────────────────────────── */
271 : :
272 : : /* Helper: compute VarInt encoded size in bits */
273 : 155835 : static uint64_t varint_bits(uint64_t val)
274 : : {
275 : 155835 : uint64_t bits = 0;
276 : : do {
277 : 212929 : bits += 8;
278 : 212929 : val >>= 7;
279 [ + + ]: 212929 : } while (val > 0);
280 : 155835 : return bits;
281 : : }
282 : :
283 : : /**
284 : : * Compute the number of bits needed to encode the trie subtree for
285 : : * entries[start..end) given that common_prefix characters have already been
286 : : * consumed. This is the "dry run" pass used to compute SKIP distances.
287 : : * value_idx is tracked so VarInt sizes for value indices are exact.
288 : : */
289 : : static uint64_t trie_subtree_size(const tp_encoder *enc, uint32_t start, uint32_t end,
290 : : size_t prefix_len, bool has_values, uint32_t *value_idx);
291 : :
292 : : /**
293 : : * Write the trie subtree for entries[start..end).
294 : : */
295 : : static tp_result trie_write(const tp_encoder *enc, tp_bitstream_writer *w, uint32_t start,
296 : : uint32_t end, size_t prefix_len, bool has_values, uint32_t *value_idx);
297 : :
298 : 124675 : static uint64_t trie_subtree_size(const tp_encoder *enc, uint32_t start, uint32_t end,
299 : : size_t prefix_len, bool has_values, uint32_t *value_idx)
300 : : {
301 : 124675 : uint8_t bps = enc->sym.bits_per_symbol;
302 : 124675 : uint64_t bits = 0;
303 : :
304 : : /* Find common prefix beyond prefix_len */
305 : 124675 : size_t common = prefix_len;
306 : 256857 : while (true) {
307 : 381532 : bool all_have = true;
308 : 381532 : uint8_t ch = 0;
309 [ + + ]: 1178669 : for (uint32_t i = start; i < end; i++) {
310 [ + + ]: 921812 : if (enc->entries[i].key_len <= common) {
311 : 100663 : all_have = false;
312 : 100663 : break;
313 : : }
314 [ + + ]: 821149 : if (i == start)
315 : 280869 : ch = (uint8_t)enc->entries[i].key[common];
316 [ + + ]: 540280 : else if ((uint8_t)enc->entries[i].key[common] != ch) {
317 : 24012 : all_have = false;
318 : 24012 : break;
319 : : }
320 : : }
321 [ + + ]: 381532 : if (!all_have)
322 : 124675 : break;
323 : 256857 : common++;
324 : : }
325 : :
326 : : /* Emit symbols for the common prefix part */
327 : 124675 : bits += (uint64_t)(common - prefix_len) * bps;
328 : :
329 : : /* Check if any entry terminates exactly at 'common' */
330 : 124675 : bool has_terminal = false;
331 : 124675 : uint32_t terminal_idx = start;
332 [ + + ]: 124675 : if (enc->entries[start].key_len == common) {
333 : 100663 : has_terminal = true;
334 : 100663 : terminal_idx = start;
335 : : }
336 : :
337 : : /* Count children (entries whose keys continue past 'common') */
338 : 124675 : uint32_t child_count = 0;
339 [ + + ]: 124675 : uint32_t prev_start = has_terminal ? start + 1 : start;
340 : : {
341 : 124675 : uint32_t cs = prev_start;
342 [ + + ]: 229759 : while (cs < end) {
343 : 105084 : child_count++;
344 : 105084 : uint8_t ch = (uint8_t)enc->entries[cs].key[common];
345 : 105084 : uint32_t ce = cs + 1;
346 [ + + + + ]: 273409 : while (ce < end && (uint8_t)enc->entries[ce].key[common] == ch)
347 : 168325 : ce++;
348 : 105084 : cs = ce;
349 : : }
350 : : }
351 : :
352 [ + + + + ]: 124675 : if (has_terminal && child_count == 0) {
353 [ + + + + ]: 97298 : if (has_values && enc->entries[terminal_idx].val.type != TP_NULL) {
354 : 49057 : bits += bps; /* END_VAL */
355 : 49057 : bits += varint_bits(*value_idx);
356 : : } else {
357 : 48241 : bits += bps; /* END */
358 : : }
359 : 97298 : (*value_idx)++;
360 [ + + + - ]: 30742 : } else if (has_terminal && child_count > 0) {
361 [ + + + - ]: 3365 : if (has_values && enc->entries[terminal_idx].val.type != TP_NULL) {
362 : 1694 : bits += bps; /* END_VAL */
363 : 1694 : bits += varint_bits(*value_idx);
364 : : } else {
365 : 1671 : bits += bps; /* END */
366 : : }
367 : 3365 : (*value_idx)++;
368 : 3365 : bits += bps; /* BRANCH */
369 : 3365 : bits += varint_bits(child_count);
370 : 3365 : uint32_t cs = prev_start;
371 : 3365 : uint32_t child_i = 0;
372 [ + + ]: 36796 : while (cs < end) {
373 : 33431 : uint32_t ce = cs + 1;
374 [ + + ]: 66837 : while (ce < end &&
375 [ + + ]: 63472 : (uint8_t)enc->entries[ce].key[common] == (uint8_t)enc->entries[cs].key[common])
376 : 33406 : ce++;
377 : :
378 [ + + ]: 33431 : if (child_i < child_count - 1) {
379 : : /* Need to compute child size first to know skip distance */
380 : 30066 : uint32_t saved_vi = *value_idx;
381 : 30066 : uint64_t child_sz = trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
382 : 30066 : bits += bps; /* SKIP */
383 : 30066 : bits += varint_bits(child_sz);
384 : 30066 : bits += child_sz;
385 : : (void)saved_vi;
386 : : } else {
387 : 3365 : bits += trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
388 : : }
389 : 33431 : child_i++;
390 : 33431 : cs = ce;
391 : : }
392 : : } else { /* !has_terminal, child_count > 1 */
393 : 24012 : bits += bps; /* BRANCH */
394 : 24012 : bits += varint_bits(child_count);
395 : 24012 : uint32_t cs = prev_start;
396 : 24012 : uint32_t child_i = 0;
397 [ + + ]: 95665 : while (cs < end) {
398 : 71653 : uint32_t ce = cs + 1;
399 [ + + ]: 206572 : while (ce < end &&
400 [ + + ]: 182560 : (uint8_t)enc->entries[ce].key[common] == (uint8_t)enc->entries[cs].key[common])
401 : 134919 : ce++;
402 : :
403 [ + + ]: 71653 : if (child_i < child_count - 1) {
404 : 47641 : uint32_t saved_vi = *value_idx;
405 : 47641 : uint64_t child_sz = trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
406 : 47641 : bits += bps; /* SKIP */
407 : 47641 : bits += varint_bits(child_sz);
408 : 47641 : bits += child_sz;
409 : : (void)saved_vi;
410 : : } else {
411 : 24012 : bits += trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
412 : : }
413 : 71653 : child_i++;
414 : 71653 : cs = ce;
415 : : }
416 : : }
417 : :
418 : 124675 : return bits;
419 : : }
420 : :
421 : 26147 : static tp_result trie_write(const tp_encoder *enc, tp_bitstream_writer *w, uint32_t start,
422 : : uint32_t end, size_t prefix_len, bool has_values, uint32_t *value_idx)
423 : : {
424 : 26147 : uint8_t bps = enc->sym.bits_per_symbol;
425 : : tp_result rc;
426 : :
427 : : /* Find common prefix beyond prefix_len */
428 : 26147 : size_t common = prefix_len;
429 : 56786 : while (true) {
430 : 82933 : bool all_have = true;
431 : 82933 : uint8_t ch = 0;
432 [ + + ]: 345566 : for (uint32_t i = start; i < end; i++) {
433 [ + + ]: 288780 : if (enc->entries[i].key_len <= common) {
434 : 20776 : all_have = false;
435 : 20776 : break;
436 : : }
437 [ + + ]: 268004 : if (i == start)
438 : 62157 : ch = (uint8_t)enc->entries[i].key[common];
439 [ + + ]: 205847 : else if ((uint8_t)enc->entries[i].key[common] != ch) {
440 : 5371 : all_have = false;
441 : 5371 : break;
442 : : }
443 : : }
444 [ + + ]: 82933 : if (!all_have)
445 : 26147 : break;
446 : 56786 : common++;
447 : : }
448 : :
449 : : /* Write common prefix symbols */
450 [ + + ]: 82933 : for (size_t i = prefix_len; i < common; i++) {
451 : 56786 : uint8_t ch = (uint8_t)enc->entries[start].key[i];
452 : 56786 : uint32_t code = enc->sym.symbol_map[ch];
453 : 56786 : rc = tp_bs_write_bits(w, code, bps);
454 [ - + ]: 56786 : if (rc != TP_OK)
455 : : return rc; /* LCOV_EXCL_LINE */
456 : : }
457 : :
458 : : /* Check if any entry terminates exactly at 'common' */
459 : 26147 : bool has_terminal = false;
460 : 26147 : uint32_t terminal_entry = start;
461 [ + + ]: 26147 : if (enc->entries[start].key_len == common) {
462 : 20776 : has_terminal = true;
463 : 20776 : terminal_entry = start;
464 : : }
465 : :
466 : : /* Count and locate children */
467 : 26147 : uint32_t child_count = 0;
468 [ + + ]: 26147 : uint32_t children_start = has_terminal ? start + 1 : start;
469 : : {
470 : 26147 : uint32_t cs = children_start;
471 [ + + ]: 52090 : while (cs < end) {
472 : 25943 : child_count++;
473 : 25943 : uint8_t ch = (uint8_t)enc->entries[cs].key[common];
474 : 25943 : uint32_t ce = cs + 1;
475 [ + + + + ]: 120813 : while (ce < end && (uint8_t)enc->entries[ce].key[common] == ch)
476 : 94870 : ce++;
477 : 25943 : cs = ce;
478 : : }
479 : : }
480 : :
481 : : /* Write terminal if present */
482 [ + + ]: 26147 : if (has_terminal) {
483 [ + + + + ]: 20776 : if (has_values && enc->entries[terminal_entry].val.type != TP_NULL) {
484 : 10738 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_END_VAL], bps);
485 [ - + ]: 10738 : if (rc != TP_OK)
486 : : return rc; /* LCOV_EXCL_LINE */
487 : 10738 : rc = tp_bs_write_varint_u(w, *value_idx);
488 [ - + ]: 10738 : if (rc != TP_OK)
489 : : return rc; /* LCOV_EXCL_LINE */
490 : : } else {
491 : 10038 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_END], bps);
492 [ - + ]: 10038 : if (rc != TP_OK)
493 : : return rc; /* LCOV_EXCL_LINE */
494 : : }
495 : 20776 : (*value_idx)++;
496 : : }
497 : :
498 [ + + ]: 26147 : if (child_count == 0) {
499 : 19795 : return TP_OK;
500 : : }
501 : :
502 : : /* Branch */
503 : 6352 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_BRANCH], bps);
504 [ - + ]: 6352 : if (rc != TP_OK)
505 : : return rc; /* LCOV_EXCL_LINE */
506 : 6352 : rc = tp_bs_write_varint_u(w, child_count);
507 [ - + ]: 6352 : if (rc != TP_OK)
508 : : return rc; /* LCOV_EXCL_LINE */
509 : :
510 : : /* For each child: optionally write SKIP, then recurse.
511 : : Pass 'common' (not common+1) so each child writes its own
512 : : distinguishing character as the first symbol — the decoder
513 : : peeks at this symbol to decide which branch to follow. */
514 : 6352 : uint32_t cs = children_start;
515 : 6352 : uint32_t child_i = 0;
516 [ + + ]: 32295 : while (cs < end) {
517 : 25943 : uint32_t ce = cs + 1;
518 [ + + ]: 120813 : while (ce < end &&
519 [ + + ]: 114461 : (uint8_t)enc->entries[ce].key[common] == (uint8_t)enc->entries[cs].key[common])
520 : 94870 : ce++;
521 : :
522 [ + + ]: 25943 : if (child_i < child_count - 1) {
523 : 19591 : uint32_t vi_copy = *value_idx;
524 : 19591 : uint64_t child_sz = trie_subtree_size(enc, cs, ce, common, has_values, &vi_copy);
525 : 19591 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_SKIP], bps);
526 [ - + ]: 19591 : if (rc != TP_OK)
527 : : return rc; /* LCOV_EXCL_LINE */
528 : 19591 : rc = tp_bs_write_varint_u(w, child_sz);
529 [ - + ]: 19591 : if (rc != TP_OK)
530 : : return rc; /* LCOV_EXCL_LINE */
531 : : }
532 : :
533 : 25943 : rc = trie_write(enc, w, cs, ce, common, has_values, value_idx);
534 [ - + ]: 25943 : if (rc != TP_OK)
535 : : return rc; /* LCOV_EXCL_LINE */
536 : :
537 : 25943 : child_i++;
538 : 25943 : cs = ce;
539 : : }
540 : :
541 : 6352 : return TP_OK;
542 : : }
543 : :
544 : : /* ── Build ───────────────────────────────────────────────────────────── */
545 : :
546 : 211 : tp_result tp_encoder_build(tp_encoder *enc, uint8_t **buf, size_t *len)
547 : : {
548 [ + + + + : 211 : if (!enc || !buf || !len)
+ + ]
549 : 3 : return TP_ERR_INVALID_PARAM;
550 : :
551 : : /* Sort and deduplicate */
552 : 208 : sort_entries(enc);
553 : 208 : dedup_entries(enc);
554 : :
555 : : /* Determine if any entries have non-null values */
556 : 208 : bool has_values = false;
557 [ + + ]: 10238 : for (uint32_t i = 0; i < enc->count; i++) {
558 [ + + ]: 10218 : if (enc->entries[i].val.type != TP_NULL) {
559 : 188 : has_values = true;
560 : 188 : break;
561 : : }
562 : : }
563 : :
564 : : /* Analyze symbols and build maps */
565 : 208 : analyze_symbols(enc);
566 : :
567 : : /* Create writer */
568 : 208 : tp_bitstream_writer *w = NULL;
569 : 208 : tp_result rc = tp_bs_writer_create(&w, 256, 0);
570 [ - + ]: 208 : if (rc != TP_OK)
571 : : return rc; /* LCOV_EXCL_LINE */
572 : :
573 : : /* Write placeholder header (32 bytes) */
574 : : tp_header hdr;
575 : 208 : memset(&hdr, 0, sizeof(hdr));
576 : 208 : hdr.magic[0] = TP_MAGIC_0;
577 : 208 : hdr.magic[1] = TP_MAGIC_1;
578 : 208 : hdr.magic[2] = TP_MAGIC_2;
579 : 208 : hdr.magic[3] = TP_MAGIC_3;
580 : 208 : hdr.version_major = TP_FORMAT_VERSION_MAJOR;
581 : 208 : hdr.version_minor = TP_FORMAT_VERSION_MINOR;
582 : 208 : hdr.num_keys = enc->count;
583 [ + + ]: 208 : if (has_values)
584 : 188 : hdr.flags |= TP_FLAG_HAS_VALUES;
585 : :
586 : 208 : rc = tp_header_write(w, &hdr);
587 [ - + ]: 208 : if (rc != TP_OK) {
588 : : /* LCOV_EXCL_START */
589 : : tp_bs_writer_destroy(&w);
590 : : return rc;
591 : : /* LCOV_EXCL_STOP */
592 : : }
593 : :
594 : : /* Data stream starts at bit 256 (byte 32) */
595 : 208 : uint64_t data_start = tp_bs_writer_position(w);
596 : :
597 : : /* Write trie config: bits_per_symbol (4 bits) + symbol_count (8 bits) */
598 : 208 : rc = tp_bs_write_bits(w, enc->sym.bits_per_symbol, 4);
599 [ - + ]: 208 : if (rc != TP_OK) {
600 : : /* LCOV_EXCL_START */
601 : : tp_bs_writer_destroy(&w);
602 : : return rc;
603 : : /* LCOV_EXCL_STOP */
604 : : }
605 : 208 : rc = tp_bs_write_bits(w, enc->sym.symbol_count, 8);
606 [ - + ]: 208 : if (rc != TP_OK) {
607 : : /* LCOV_EXCL_START */
608 : : tp_bs_writer_destroy(&w);
609 : : return rc;
610 : : /* LCOV_EXCL_STOP */
611 : : }
612 : :
613 : : /* Write special symbol map (6 * bps bits) */
614 [ + + ]: 1456 : for (int c = 0; c < TP_NUM_CONTROL_CODES; c++) {
615 : 1248 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[c], enc->sym.bits_per_symbol);
616 [ - + ]: 1248 : if (rc != TP_OK) {
617 : : /* LCOV_EXCL_START */
618 : : tp_bs_writer_destroy(&w);
619 : : return rc;
620 : : /* LCOV_EXCL_STOP */
621 : : }
622 : : }
623 : :
624 : : /* Write symbol table (VarInt codepoints for non-control symbols) */
625 [ + + ]: 53456 : for (int i = 0; i < 256; i++) {
626 : : /* Find byte values that are in the alphabet, in code order */
627 : : }
628 : : /* Actually: write in code order, skipping control codes */
629 : : {
630 : 208 : uint32_t max_code = enc->sym.symbol_count;
631 [ + + ]: 1425 : for (uint32_t code = TP_NUM_CONTROL_CODES; code < max_code; code++) {
632 : 1217 : uint8_t byte_val = 0;
633 [ + - ]: 1217 : if (code < 256)
634 : 1217 : byte_val = enc->sym.reverse_map[code];
635 : 1217 : rc = tp_bs_write_varint_u(w, byte_val);
636 [ - + ]: 1217 : if (rc != TP_OK) {
637 : : /* LCOV_EXCL_START */
638 : : tp_bs_writer_destroy(&w);
639 : : return rc;
640 : : /* LCOV_EXCL_STOP */
641 : : }
642 : : }
643 : : }
644 : :
645 : : /* Record trie data offset (relative to data stream start) */
646 : 208 : uint64_t trie_data_offset = tp_bs_writer_position(w) - data_start;
647 : :
648 : : /* Write prefix trie */
649 : 208 : uint32_t value_idx = 0;
650 [ + + ]: 208 : if (enc->count > 0) {
651 : 204 : rc = trie_write(enc, w, 0, enc->count, 0, has_values, &value_idx);
652 [ - + ]: 204 : if (rc != TP_OK) {
653 : : /* LCOV_EXCL_START */
654 : : tp_bs_writer_destroy(&w);
655 : : return rc;
656 : : /* LCOV_EXCL_STOP */
657 : : }
658 : : }
659 : :
660 : : /* Record value store offset */
661 : 208 : uint64_t value_store_offset = tp_bs_writer_position(w) - data_start;
662 : :
663 : : /* Write value store */
664 [ + + ]: 208 : if (has_values) {
665 [ + + ]: 10935 : for (uint32_t i = 0; i < enc->count; i++) {
666 : 10747 : rc = tp_value_encode(w, &enc->entries[i].val);
667 [ - + ]: 10747 : if (rc != TP_OK) {
668 : : /* LCOV_EXCL_START */
669 : : tp_bs_writer_destroy(&w);
670 : : return rc;
671 : : /* LCOV_EXCL_STOP */
672 : : }
673 : : }
674 : : }
675 : :
676 : : /* Total data bits */
677 : 208 : uint64_t total_data_bits = tp_bs_writer_position(w) - data_start;
678 : :
679 : : /* Align to byte boundary before CRC */
680 : 208 : rc = tp_bs_writer_align_to_byte(w);
681 [ - + ]: 208 : if (rc != TP_OK) {
682 : : /* LCOV_EXCL_START */
683 : : tp_bs_writer_destroy(&w);
684 : : return rc;
685 : : /* LCOV_EXCL_STOP */
686 : : }
687 : :
688 : : /* Now patch the header with final offsets */
689 : : /* We need to overwrite bytes 12-27 with the correct offsets */
690 : : const uint8_t *wbuf;
691 : : uint64_t wbit_len;
692 : 208 : tp_bs_writer_get_buffer(w, &wbuf, &wbit_len);
693 : :
694 : : /* Build the final buffer: first get current data */
695 : 208 : size_t pre_crc_bytes = (size_t)(tp_bs_writer_position(w) / 8);
696 : :
697 : : /* Compute CRC-32 over everything so far */
698 : 208 : uint32_t crc = tp_crc32(wbuf, pre_crc_bytes);
699 : :
700 : : /* Write CRC-32 as 4 bytes at the end */
701 : 208 : rc = tp_bs_write_u32(w, crc);
702 [ - + ]: 208 : if (rc != TP_OK) {
703 : : /* LCOV_EXCL_START */
704 : : tp_bs_writer_destroy(&w);
705 : : return rc;
706 : : /* LCOV_EXCL_STOP */
707 : : }
708 : :
709 : : /* Detach buffer */
710 : : uint8_t *out_buf;
711 : : size_t out_byte_len;
712 : : uint64_t out_bit_len;
713 : 208 : rc = tp_bs_writer_detach_buffer(w, &out_buf, &out_byte_len, &out_bit_len);
714 : 208 : tp_bs_writer_destroy(&w);
715 [ - + ]: 208 : if (rc != TP_OK)
716 : : return rc; /* LCOV_EXCL_LINE */
717 : :
718 : : /* Patch header fields in the output buffer */
719 : : /* trie_data_offset at byte 12 (big-endian) */
720 : 208 : out_buf[12] = (uint8_t)(trie_data_offset >> 24);
721 : 208 : out_buf[13] = (uint8_t)(trie_data_offset >> 16);
722 : 208 : out_buf[14] = (uint8_t)(trie_data_offset >> 8);
723 : 208 : out_buf[15] = (uint8_t)(trie_data_offset);
724 : : /* value_store_offset at byte 16 */
725 : 208 : out_buf[16] = (uint8_t)(value_store_offset >> 24);
726 : 208 : out_buf[17] = (uint8_t)(value_store_offset >> 16);
727 : 208 : out_buf[18] = (uint8_t)(value_store_offset >> 8);
728 : 208 : out_buf[19] = (uint8_t)(value_store_offset);
729 : : /* suffix_table_offset at byte 20 = 0 (no suffix table) */
730 : 208 : out_buf[20] = 0;
731 : 208 : out_buf[21] = 0;
732 : 208 : out_buf[22] = 0;
733 : 208 : out_buf[23] = 0;
734 : : /* total_data_bits at byte 24 */
735 : 208 : out_buf[24] = (uint8_t)(total_data_bits >> 24);
736 : 208 : out_buf[25] = (uint8_t)(total_data_bits >> 16);
737 : 208 : out_buf[26] = (uint8_t)(total_data_bits >> 8);
738 : 208 : out_buf[27] = (uint8_t)(total_data_bits);
739 : :
740 : : /* Recompute CRC over the patched data (everything except last 4 bytes) */
741 : 208 : size_t crc_data_len = out_byte_len - 4;
742 : 208 : crc = tp_crc32(out_buf, crc_data_len);
743 : 208 : out_buf[crc_data_len] = (uint8_t)(crc >> 24);
744 : 208 : out_buf[crc_data_len + 1] = (uint8_t)(crc >> 16);
745 : 208 : out_buf[crc_data_len + 2] = (uint8_t)(crc >> 8);
746 : 208 : out_buf[crc_data_len + 3] = (uint8_t)(crc);
747 : :
748 : 208 : *buf = out_buf;
749 : 208 : *len = out_byte_len;
750 : 208 : return TP_OK;
751 : : }
752 : :
753 : : /* ── Reset ───────────────────────────────────────────────────────────── */
754 : :
755 : 8 : tp_result tp_encoder_reset(tp_encoder *enc)
756 : : {
757 [ + + ]: 8 : if (!enc)
758 : 1 : return TP_ERR_INVALID_PARAM;
759 [ + + ]: 49 : for (uint32_t i = 0; i < enc->count; i++) {
760 : 42 : value_free_copy(&enc->entries[i].val);
761 : 42 : free(enc->entries[i].key);
762 : : }
763 : 7 : free(enc->entries);
764 : 7 : enc->entries = NULL;
765 : 7 : enc->entries_cap = 0;
766 : 7 : enc->count = 0;
767 : 7 : enc->sorted = false;
768 : 7 : return TP_OK;
769 : : }
|
