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 : 214894 : static tp_result value_deep_copy(tp_value *v)
18 : : {
19 [ + + + + ]: 214894 : if (v->type == TP_STRING && v->data.string_val.str) {
20 : 70 : size_t len = v->data.string_val.str_len;
21 : 70 : char *copy = malloc(len + 1);
22 : 70 : if (!copy) /* LCOV_EXCL_BR_LINE */
23 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
24 : 70 : memcpy(copy, v->data.string_val.str, len);
25 : 70 : copy[len] = '\0';
26 : 70 : v->data.string_val.str = copy;
27 [ + + + + ]: 214824 : } else if (v->type == TP_BLOB && v->data.blob_val.data) {
28 : : /* Copy zero-length blobs too: value_free_copy() frees any non-NULL
29 : : blob pointer, so leaving the caller's pointer in place would make
30 : : the encoder free memory it does not own. */
31 : 16 : size_t len = v->data.blob_val.len;
32 [ + + ]: 16 : uint8_t *copy = malloc(len > 0 ? len : 1);
33 : 16 : if (!copy) /* LCOV_EXCL_BR_LINE */
34 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
35 [ + + ]: 16 : if (len > 0)
36 : 14 : memcpy(copy, v->data.blob_val.data, len);
37 : 16 : v->data.blob_val.data = copy;
38 : : }
39 : 214894 : return TP_OK;
40 : : }
41 : :
42 : : /** Free deep-copied data inside a tp_value. */
43 : 214894 : static void value_free_copy(tp_value *v)
44 : : {
45 [ + + + + ]: 214894 : if (v->type == TP_STRING && v->data.string_val.str) {
46 : 70 : free((void *)v->data.string_val.str);
47 : 70 : v->data.string_val.str = NULL;
48 [ + + + + ]: 214824 : } else if (v->type == TP_BLOB && v->data.blob_val.data) {
49 : 16 : free((void *)v->data.blob_val.data);
50 : 16 : v->data.blob_val.data = NULL;
51 : : }
52 : 214894 : }
53 : :
54 : : /* ── Defaults ────────────────────────────────────────────────────────── */
55 : :
56 : 316 : tp_encoder_options tp_encoder_defaults(void)
57 : : {
58 : : tp_encoder_options opts;
59 : 316 : memset(&opts, 0, sizeof(opts));
60 : 316 : opts.trie_mode = TP_ADDR_BIT;
61 : 316 : opts.value_mode = TP_ADDR_BYTE;
62 : 316 : opts.checksum = TP_CHECKSUM_CRC32;
63 : 316 : opts.enable_suffix = false; /* not implemented yet */
64 : 316 : opts.compact_mode = false;
65 : 316 : opts.bits_per_symbol = 0; /* auto */
66 : 316 : return opts;
67 : : }
68 : :
69 : : /* ── Create / Destroy ────────────────────────────────────────────────── */
70 : :
71 : 308 : tp_result tp_encoder_create(tp_encoder **out)
72 : : {
73 [ + + ]: 308 : if (!out)
74 : 1 : return TP_ERR_INVALID_PARAM;
75 : :
76 : 307 : tp_encoder_options opts = tp_encoder_defaults();
77 : 307 : return tp_encoder_create_ex(out, &opts);
78 : : }
79 : :
80 : 318 : tp_result tp_encoder_create_ex(tp_encoder **out, const tp_encoder_options *opts)
81 : : {
82 [ + + + + ]: 318 : if (!out || !opts)
83 : 3 : return TP_ERR_INVALID_PARAM;
84 : :
85 : : /* tp_encoder_options offers six knobs; this encoder implements one
86 : : (bits_per_symbol). The rest were accepted and silently ignored, so a
87 : : caller asking for SHA-256 got CRC-32 and a caller enabling the suffix
88 : : table got a plain trie, with no way to tell. Say so instead.
89 : :
90 : : These are not permanent limits -- see docs/internals/format-spec-v2.md
91 : : -- but until they are real, asking for them is an error, not a
92 : : no-op. */
93 [ + + ]: 315 : if (opts->trie_mode != TP_ADDR_BIT)
94 : 1 : return TP_ERR_UNSUPPORTED;
95 [ + + ]: 314 : if (opts->value_mode != TP_ADDR_BYTE)
96 : 1 : return TP_ERR_UNSUPPORTED;
97 [ + + ]: 313 : if (opts->checksum != TP_CHECKSUM_CRC32)
98 : 1 : return TP_ERR_UNSUPPORTED;
99 [ + + ]: 312 : if (opts->enable_suffix)
100 : 1 : return TP_ERR_UNSUPPORTED;
101 [ + + ]: 311 : if (opts->compact_mode)
102 : 1 : return TP_ERR_UNSUPPORTED;
103 [ + + ]: 310 : if (opts->bits_per_symbol > 15)
104 : 1 : return TP_ERR_INVALID_PARAM;
105 : :
106 : : /* Allocation failure paths are excluded from coverage (LCOV_EXCL). */
107 : 309 : tp_encoder *enc = calloc(1, sizeof(*enc));
108 : 309 : if (!enc) /* LCOV_EXCL_BR_LINE */
109 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
110 : :
111 : 309 : enc->opts = *opts;
112 : 309 : enc->count = 0;
113 : 309 : enc->entries = NULL;
114 : 309 : enc->entries_cap = 0;
115 : 309 : enc->sorted = false;
116 : 309 : *out = enc;
117 : 309 : return TP_OK;
118 : : }
119 : :
120 : 314 : tp_result tp_encoder_destroy(tp_encoder **enc)
121 : : {
122 [ + + ]: 314 : if (!enc)
123 : 1 : return TP_ERR_INVALID_PARAM;
124 [ + + ]: 313 : if (*enc) {
125 [ + + ]: 215156 : for (uint32_t i = 0; i < (*enc)->count; i++) {
126 : 214847 : value_free_copy(&(*enc)->entries[i].val);
127 : 214847 : free((*enc)->entries[i].key);
128 : : }
129 : 309 : free((*enc)->entries);
130 : 309 : free(*enc);
131 : 309 : *enc = NULL;
132 : : }
133 : 313 : return TP_OK;
134 : : }
135 : :
136 : : /* ── Add entries ─────────────────────────────────────────────────────── */
137 : :
138 : 211671 : tp_result tp_encoder_add(tp_encoder *enc, const char *key, const tp_value *val)
139 : : {
140 [ + + + + ]: 211671 : if (!enc || !key)
141 : 2 : return TP_ERR_INVALID_PARAM;
142 : 211669 : return tp_encoder_add_n(enc, key, strlen(key), val);
143 : : }
144 : :
145 : 214896 : tp_result tp_encoder_add_n(tp_encoder *enc, const char *key, size_t key_len, const tp_value *val)
146 : : {
147 [ + + + + ]: 214896 : if (!enc || !key)
148 : 2 : return TP_ERR_INVALID_PARAM;
149 : :
150 : : /* Grow entries array if needed */
151 [ + + ]: 214894 : if (enc->count >= enc->entries_cap) {
152 [ + + ]: 386 : size_t new_cap = enc->entries_cap == 0 ? 16 : enc->entries_cap * 2;
153 : 386 : tp_entry *new_entries = realloc(enc->entries, new_cap * sizeof(tp_entry));
154 : 386 : if (!new_entries) /* LCOV_EXCL_BR_LINE */
155 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
156 : 386 : enc->entries = new_entries;
157 : 386 : enc->entries_cap = new_cap;
158 : : }
159 : :
160 : : /* Copy key */
161 : 214894 : char *key_copy = malloc(key_len + 1);
162 : 214894 : if (!key_copy) /* LCOV_EXCL_BR_LINE */
163 : : return TP_ERR_ALLOC; /* LCOV_EXCL_LINE */
164 : 214894 : memcpy(key_copy, key, key_len);
165 : 214894 : key_copy[key_len] = '\0';
166 : :
167 : 214894 : tp_entry *e = &enc->entries[enc->count];
168 : 214894 : e->key = key_copy;
169 : 214894 : e->key_len = key_len;
170 [ + + ]: 214894 : if (val)
171 : 204862 : e->val = *val;
172 : : else
173 : 10032 : e->val = tp_value_null();
174 : :
175 : : /* Deep-copy string/blob data so the encoder owns it */
176 : 214894 : tp_result vrc = value_deep_copy(&e->val);
177 : 214894 : if (vrc != TP_OK) { /* LCOV_EXCL_BR_LINE */
178 : : /* LCOV_EXCL_START */
179 : : free(key_copy);
180 : : return vrc;
181 : : /* LCOV_EXCL_STOP */
182 : : }
183 : :
184 : 214894 : enc->count++;
185 : 214894 : enc->sorted = false;
186 : 214894 : return TP_OK;
187 : : }
188 : :
189 : : /* ── Query ───────────────────────────────────────────────────────────── */
190 : :
191 : 15 : uint32_t tp_encoder_count(const tp_encoder *enc)
192 : : {
193 [ + + ]: 15 : if (!enc)
194 : 1 : return 0;
195 : 14 : return enc->count;
196 : : }
197 : :
198 : : /* ── Sort entries ────────────────────────────────────────────────────── */
199 : :
200 : 1792972 : static int entry_cmp(const void *a, const void *b)
201 : : {
202 : 1792972 : const tp_entry *ea = (const tp_entry *)a;
203 : 1792972 : const tp_entry *eb = (const tp_entry *)b;
204 : 1792972 : size_t min_len = ea->key_len < eb->key_len ? ea->key_len : eb->key_len;
205 : 1792972 : int cmp = memcmp(ea->key, eb->key, min_len);
206 [ + + ]: 1792972 : if (cmp != 0)
207 : 1790706 : return cmp;
208 [ + + ]: 2266 : if (ea->key_len < eb->key_len)
209 : 2262 : return -1;
210 [ - + ]: 4 : if (ea->key_len > eb->key_len)
211 : 0 : return 1;
212 : 4 : return 0;
213 : : }
214 : :
215 : 278 : static void sort_entries(tp_encoder *enc)
216 : : {
217 [ + + ]: 278 : if (enc->count > 1)
218 : 187 : qsort(enc->entries, enc->count, sizeof(tp_entry), entry_cmp);
219 : 278 : enc->sorted = true;
220 : 278 : }
221 : :
222 : : /* Remove duplicate keys (keep last added) */
223 : 278 : static void dedup_entries(tp_encoder *enc)
224 : : {
225 [ + + ]: 278 : if (enc->count <= 1)
226 : 91 : return;
227 : 187 : uint32_t write = 0;
228 [ + + ]: 214988 : for (uint32_t i = 0; i < enc->count; i++) {
229 [ + + + + ]: 214801 : if (i + 1 < enc->count && enc->entries[i].key_len == enc->entries[i + 1].key_len &&
230 [ + + ]: 202480 : memcmp(enc->entries[i].key, enc->entries[i + 1].key, enc->entries[i].key_len) == 0) {
231 : 4 : value_free_copy(&enc->entries[i].val);
232 : 4 : free(enc->entries[i].key);
233 : 4 : continue;
234 : : }
235 [ + + ]: 214797 : if (write != i)
236 : 3 : enc->entries[write] = enc->entries[i];
237 : 214797 : write++;
238 : : }
239 : 187 : enc->count = write;
240 : : }
241 : :
242 : : /* ── Symbol analysis ─────────────────────────────────────────────────── */
243 : :
244 : 278 : static void analyze_symbols(tp_encoder *enc)
245 : : {
246 : 278 : tp_symbol_info *sym = &enc->sym;
247 : 278 : memset(sym, 0, sizeof(*sym));
248 : :
249 : 278 : bool used[256] = {false};
250 : :
251 : : /* Scan all keys to find used byte values */
252 [ + + ]: 215160 : for (uint32_t i = 0; i < enc->count; i++) {
253 [ + + ]: 5103407 : for (size_t j = 0; j < enc->entries[i].key_len; j++) {
254 : 4888525 : used[(uint8_t)enc->entries[i].key[j]] = true;
255 : : }
256 : : }
257 : :
258 : : /* Count alphabet size */
259 : 278 : sym->alphabet_size = 0;
260 [ + + ]: 71446 : for (int i = 0; i < 256; i++) {
261 [ + + ]: 71168 : if (used[i])
262 : 3726 : sym->alphabet_size++;
263 : : }
264 : :
265 : : /* Determine bits_per_symbol */
266 : 278 : uint16_t total_symbols = sym->alphabet_size + TP_NUM_CONTROL_CODES;
267 : 278 : uint8_t bps = enc->opts.bits_per_symbol;
268 [ + - ]: 278 : if (bps == 0) {
269 : : /* Auto: find minimum bits to cover all symbols */
270 : 278 : bps = 1;
271 [ + + ]: 1156 : while (((uint16_t)1 << bps) < total_symbols)
272 : 878 : bps++;
273 : : }
274 : 278 : sym->bits_per_symbol = bps;
275 : 278 : sym->symbol_count = total_symbols;
276 : :
277 : : /* Assign control codes to the first slots */
278 [ + + ]: 1946 : for (int c = 0; c < TP_NUM_CONTROL_CODES; c++) {
279 : 1668 : sym->ctrl_codes[c] = (uint32_t)c;
280 : 1668 : sym->code_is_ctrl[c] = true;
281 : : }
282 : :
283 : : /* Assign alphabet symbols starting after control codes */
284 : 278 : uint32_t code = TP_NUM_CONTROL_CODES;
285 [ + + ]: 71446 : for (int i = 0; i < 256; i++) {
286 [ + + ]: 71168 : if (used[i]) {
287 : 3726 : sym->symbol_map[i] = code;
288 [ + + ]: 3726 : if (code < 256)
289 : 3712 : sym->reverse_map[code] = (uint8_t)i;
290 : 3726 : code++;
291 : : }
292 : : }
293 : 278 : }
294 : :
295 : : /* ── Trie encoding ───────────────────────────────────────────────────── */
296 : :
297 : : /* Helper: compute VarInt encoded size in bits */
298 : 1702305 : static uint64_t varint_bits(uint64_t val)
299 : : {
300 : 1702305 : uint64_t bits = 0;
301 : : do {
302 : 3341925 : bits += 8;
303 : 3341925 : val >>= 7;
304 [ + + ]: 3341925 : } while (val > 0);
305 : 1702305 : return bits;
306 : : }
307 : :
308 : : /**
309 : : * Compute the number of bits needed to encode the trie subtree for
310 : : * entries[start..end) given that common_prefix characters have already been
311 : : * consumed. This is the "dry run" pass used to compute SKIP distances.
312 : : * value_idx is tracked so VarInt sizes for value indices are exact.
313 : : */
314 : : static uint64_t trie_subtree_size(const tp_encoder *enc, uint32_t start, uint32_t end,
315 : : size_t prefix_len, bool has_values, uint32_t *value_idx);
316 : :
317 : : /**
318 : : * Write the trie subtree for entries[start..end).
319 : : */
320 : : static tp_result trie_write(const tp_encoder *enc, tp_bitstream_writer *w, uint32_t start,
321 : : uint32_t end, size_t prefix_len, bool has_values, uint32_t *value_idx);
322 : :
323 : 1016296 : static uint64_t trie_subtree_size(const tp_encoder *enc, uint32_t start, uint32_t end,
324 : : size_t prefix_len, bool has_values, uint32_t *value_idx)
325 : : {
326 : 1016296 : uint8_t bps = enc->sym.bits_per_symbol;
327 : 1016296 : uint64_t bits = 0;
328 : :
329 : : /* Find common prefix beyond prefix_len */
330 : 1016296 : size_t common = prefix_len;
331 : 12966983 : while (true) {
332 : 13983279 : bool all_have = true;
333 : 13983279 : uint8_t ch = 0;
334 [ + + ]: 29139665 : for (uint32_t i = start; i < end; i++) {
335 [ + + ]: 16172682 : if (enc->entries[i].key_len <= common) {
336 : 948486 : all_have = false;
337 : 948486 : break;
338 : : }
339 [ + + ]: 15224196 : if (i == start)
340 : 13034793 : ch = (uint8_t)enc->entries[i].key[common];
341 [ + + ]: 2189403 : else if ((uint8_t)enc->entries[i].key[common] != ch) {
342 : 67810 : all_have = false;
343 : 67810 : break;
344 : : }
345 : : }
346 [ + + ]: 13983279 : if (!all_have)
347 : 1016296 : break;
348 : 12966983 : common++;
349 : : }
350 : :
351 : : /* Emit symbols for the common prefix part */
352 : 1016296 : bits += (uint64_t)(common - prefix_len) * bps;
353 : :
354 : : /* Check if any entry terminates exactly at 'common' */
355 : 1016296 : bool has_terminal = false;
356 : 1016296 : uint32_t terminal_idx = start;
357 [ + + ]: 1016296 : if (enc->entries[start].key_len == common) {
358 : 948486 : has_terminal = true;
359 : 948486 : terminal_idx = start;
360 : : }
361 : :
362 : : /* Count children (entries whose keys continue past 'common') */
363 : 1016296 : uint32_t child_count = 0;
364 [ + + ]: 1016296 : uint32_t prev_start = has_terminal ? start + 1 : start;
365 : : {
366 : 1016296 : uint32_t cs = prev_start;
367 [ + + ]: 1820313 : while (cs < end) {
368 : 804017 : child_count++;
369 : 804017 : uint8_t ch = (uint8_t)enc->entries[cs].key[common];
370 : 804017 : uint32_t ce = cs + 1;
371 [ + + + + ]: 1865957 : while (ce < end && (uint8_t)enc->entries[ce].key[common] == ch)
372 : 1061940 : ce++;
373 : 804017 : cs = ce;
374 : : }
375 : : }
376 : :
377 [ + + + + ]: 1016296 : if (has_terminal && child_count == 0) {
378 [ + + + + ]: 945108 : if (has_values && enc->entries[terminal_idx].val.type != TP_NULL) {
379 : 896583 : bits += bps; /* END_VAL */
380 : 896583 : bits += varint_bits(*value_idx);
381 : : } else {
382 : 48525 : bits += bps; /* END */
383 : : }
384 : 945108 : (*value_idx)++;
385 [ + + + - ]: 74566 : } else if (has_terminal && child_count > 0) {
386 [ + + + - ]: 3378 : if (has_values && enc->entries[terminal_idx].val.type != TP_NULL) {
387 : 1705 : bits += bps; /* END_VAL */
388 : 1705 : bits += varint_bits(*value_idx);
389 : : } else {
390 : 1673 : bits += bps; /* END */
391 : : }
392 : 3378 : (*value_idx)++;
393 : 3378 : bits += bps; /* BRANCH */
394 : 3378 : bits += varint_bits(child_count);
395 : 3378 : uint32_t cs = prev_start;
396 : 3378 : uint32_t child_i = 0;
397 [ + + ]: 36822 : while (cs < end) {
398 : 33444 : uint32_t ce = cs + 1;
399 [ + + ]: 66850 : while (ce < end &&
400 [ + + ]: 63472 : (uint8_t)enc->entries[ce].key[common] == (uint8_t)enc->entries[cs].key[common])
401 : 33406 : ce++;
402 : :
403 [ + + ]: 33444 : if (child_i < child_count - 1) {
404 : : /* Need to compute child size first to know skip distance */
405 : 30066 : uint32_t saved_vi = *value_idx;
406 : 30066 : uint64_t child_sz = trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
407 : 30066 : bits += bps; /* SKIP */
408 : 30066 : bits += varint_bits(child_sz);
409 : 30066 : bits += child_sz;
410 : : (void)saved_vi;
411 : : } else {
412 : 3378 : bits += trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
413 : : }
414 : 33444 : child_i++;
415 : 33444 : cs = ce;
416 : : }
417 : : } else { /* !has_terminal, child_count > 1 */
418 : 67810 : bits += bps; /* BRANCH */
419 : 67810 : bits += varint_bits(child_count);
420 : 67810 : uint32_t cs = prev_start;
421 : 67810 : uint32_t child_i = 0;
422 [ + + ]: 838383 : while (cs < end) {
423 : 770573 : uint32_t ce = cs + 1;
424 [ + + ]: 1799107 : while (ce < end &&
425 [ + + ]: 1731297 : (uint8_t)enc->entries[ce].key[common] == (uint8_t)enc->entries[cs].key[common])
426 : 1028534 : ce++;
427 : :
428 [ + + ]: 770573 : if (child_i < child_count - 1) {
429 : 702763 : uint32_t saved_vi = *value_idx;
430 : 702763 : uint64_t child_sz = trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
431 : 702763 : bits += bps; /* SKIP */
432 : 702763 : bits += varint_bits(child_sz);
433 : 702763 : bits += child_sz;
434 : : (void)saved_vi;
435 : : } else {
436 : 67810 : bits += trie_subtree_size(enc, cs, ce, common, has_values, value_idx);
437 : : }
438 : 770573 : child_i++;
439 : 770573 : cs = ce;
440 : : }
441 : : }
442 : :
443 : 1016296 : return bits;
444 : : }
445 : :
446 : 232220 : static tp_result trie_write(const tp_encoder *enc, tp_bitstream_writer *w, uint32_t start,
447 : : uint32_t end, size_t prefix_len, bool has_values, uint32_t *value_idx)
448 : : {
449 : 232220 : uint8_t bps = enc->sym.bits_per_symbol;
450 : : tp_result rc;
451 : :
452 : : /* Find common prefix beyond prefix_len */
453 : 232220 : size_t common = prefix_len;
454 : 2939158 : while (true) {
455 : 3171378 : bool all_have = true;
456 : 3171378 : uint8_t ch = 0;
457 [ + + ]: 8199046 : for (uint32_t i = start; i < end; i++) {
458 [ + + ]: 5259888 : if (enc->entries[i].key_len <= common) {
459 : 213868 : all_have = false;
460 : 213868 : break;
461 : : }
462 [ + + ]: 5046020 : if (i == start)
463 : 2957510 : ch = (uint8_t)enc->entries[i].key[common];
464 [ + + ]: 2088510 : else if ((uint8_t)enc->entries[i].key[common] != ch) {
465 : 18352 : all_have = false;
466 : 18352 : break;
467 : : }
468 : : }
469 [ + + ]: 3171378 : if (!all_have)
470 : 232220 : break;
471 : 2939158 : common++;
472 : : }
473 : :
474 : : /* Write common prefix symbols */
475 [ + + ]: 3171378 : for (size_t i = prefix_len; i < common; i++) {
476 : 2939158 : uint8_t ch = (uint8_t)enc->entries[start].key[i];
477 : 2939158 : uint32_t code = enc->sym.symbol_map[ch];
478 : 2939158 : rc = tp_bs_write_bits(w, code, bps);
479 : 2939158 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
480 : : return rc; /* LCOV_EXCL_LINE */
481 : : }
482 : :
483 : : /* Check if any entry terminates exactly at 'common' */
484 : 232220 : bool has_terminal = false;
485 : 232220 : uint32_t terminal_entry = start;
486 [ + + ]: 232220 : if (enc->entries[start].key_len == common) {
487 : 213868 : has_terminal = true;
488 : 213868 : terminal_entry = start;
489 : : }
490 : :
491 : : /* Count and locate children */
492 : 232220 : uint32_t child_count = 0;
493 [ + + ]: 232220 : uint32_t children_start = has_terminal ? start + 1 : start;
494 : : {
495 : 232220 : uint32_t cs = children_start;
496 [ + + ]: 464172 : while (cs < end) {
497 : 231952 : child_count++;
498 : 231952 : uint8_t ch = (uint8_t)enc->entries[cs].key[common];
499 : 231952 : uint32_t ce = cs + 1;
500 [ + + + + ]: 1108421 : while (ce < end && (uint8_t)enc->entries[ce].key[common] == ch)
501 : 876469 : ce++;
502 : 231952 : cs = ce;
503 : : }
504 : : }
505 : :
506 : : /* Write terminal if present */
507 [ + + ]: 232220 : if (has_terminal) {
508 [ + + + + ]: 213868 : if (has_values && enc->entries[terminal_entry].val.type != TP_NULL) {
509 : 203527 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_END_VAL], bps);
510 : 203527 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
511 : : return rc; /* LCOV_EXCL_LINE */
512 : 203527 : rc = tp_bs_write_varint_u(w, *value_idx);
513 : 203527 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
514 : : return rc; /* LCOV_EXCL_LINE */
515 : : } else {
516 : 10341 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_END], bps);
517 : 10341 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
518 : : return rc; /* LCOV_EXCL_LINE */
519 : : }
520 : 213868 : (*value_idx)++;
521 : : }
522 : :
523 [ + + ]: 232220 : if (child_count == 0) {
524 : 212547 : return TP_OK;
525 : : }
526 : :
527 : : /* Branch */
528 : 19673 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_BRANCH], bps);
529 : 19673 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
530 : : return rc; /* LCOV_EXCL_LINE */
531 : 19673 : rc = tp_bs_write_varint_u(w, child_count);
532 : 19673 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
533 : : return rc; /* LCOV_EXCL_LINE */
534 : :
535 : : /* For each child: optionally write SKIP, then recurse.
536 : : Pass 'common' (not common+1) so each child writes its own
537 : : distinguishing character as the first symbol — the decoder
538 : : peeks at this symbol to decide which branch to follow. */
539 : 19673 : uint32_t cs = children_start;
540 : 19673 : uint32_t child_i = 0;
541 [ + + ]: 251625 : while (cs < end) {
542 : 231952 : uint32_t ce = cs + 1;
543 [ + + ]: 1108421 : while (ce < end &&
544 [ + + ]: 1088748 : (uint8_t)enc->entries[ce].key[common] == (uint8_t)enc->entries[cs].key[common])
545 : 876469 : ce++;
546 : :
547 [ + + ]: 231952 : if (child_i < child_count - 1) {
548 : 212279 : uint32_t vi_copy = *value_idx;
549 : 212279 : uint64_t child_sz = trie_subtree_size(enc, cs, ce, common, has_values, &vi_copy);
550 : 212279 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[TP_CTRL_SKIP], bps);
551 : 212279 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
552 : : return rc; /* LCOV_EXCL_LINE */
553 : 212279 : rc = tp_bs_write_varint_u(w, child_sz);
554 : 212279 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
555 : : return rc; /* LCOV_EXCL_LINE */
556 : : }
557 : :
558 : 231952 : rc = trie_write(enc, w, cs, ce, common, has_values, value_idx);
559 : 231952 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
560 : : return rc; /* LCOV_EXCL_LINE */
561 : :
562 : 231952 : child_i++;
563 : 231952 : cs = ce;
564 : : }
565 : :
566 : 19673 : return TP_OK;
567 : : }
568 : :
569 : : /* ── Build ───────────────────────────────────────────────────────────── */
570 : :
571 : 281 : tp_result tp_encoder_build(tp_encoder *enc, uint8_t **buf, size_t *len)
572 : : {
573 [ + + + + : 281 : if (!enc || !buf || !len)
+ + ]
574 : 3 : return TP_ERR_INVALID_PARAM;
575 : :
576 : : /* Sort and deduplicate */
577 : 278 : sort_entries(enc);
578 : 278 : dedup_entries(enc);
579 : :
580 : : /* Determine if any entries have non-null values */
581 : 278 : bool has_values = false;
582 [ + + ]: 11623 : for (uint32_t i = 0; i < enc->count; i++) {
583 [ + + ]: 11581 : if (enc->entries[i].val.type != TP_NULL) {
584 : 236 : has_values = true;
585 : 236 : break;
586 : : }
587 : : }
588 : :
589 : : /* Analyze symbols and build maps */
590 : 278 : analyze_symbols(enc);
591 : :
592 : : /* The trie config packs symbol_count into 8 header bits. An alphabet
593 : : wider than TP_MAX_ALPHABET_SIZE overflows that field, which used to
594 : : produce a buffer with a valid CRC whose every lookup silently failed.
595 : : Refuse to build it instead. */
596 [ + + ]: 278 : if (enc->sym.symbol_count > 255)
597 : 4 : return TP_ERR_ALPHABET;
598 : :
599 : : /* Create writer */
600 : 274 : tp_bitstream_writer *w = NULL;
601 : 274 : tp_result rc = tp_bs_writer_create(&w, 256, 0);
602 : 274 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
603 : : return rc; /* LCOV_EXCL_LINE */
604 : :
605 : : /* Write placeholder header (32 bytes) */
606 : : tp_header hdr;
607 : 274 : memset(&hdr, 0, sizeof(hdr));
608 : 274 : hdr.magic[0] = TP_MAGIC_0;
609 : 274 : hdr.magic[1] = TP_MAGIC_1;
610 : 274 : hdr.magic[2] = TP_MAGIC_2;
611 : 274 : hdr.magic[3] = TP_MAGIC_3;
612 : 274 : hdr.version_major = TP_FORMAT_VERSION_MAJOR;
613 : 274 : hdr.version_minor = TP_FORMAT_VERSION_MINOR;
614 : 274 : hdr.num_keys = enc->count;
615 [ + + ]: 274 : if (has_values)
616 : 236 : hdr.flags |= TP_FLAG_HAS_VALUES;
617 : :
618 : 274 : rc = tp_header_write(w, &hdr);
619 : 274 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
620 : : /* LCOV_EXCL_START */
621 : : tp_bs_writer_destroy(&w);
622 : : return rc;
623 : : /* LCOV_EXCL_STOP */
624 : : }
625 : :
626 : : /* Data stream starts at bit 256 (byte 32) */
627 : 274 : uint64_t data_start = tp_bs_writer_position(w);
628 : :
629 : : /* Write trie config: bits_per_symbol (4 bits) + symbol_count (8 bits) */
630 : 274 : rc = tp_bs_write_bits(w, enc->sym.bits_per_symbol, 4);
631 : 274 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
632 : : /* LCOV_EXCL_START */
633 : : tp_bs_writer_destroy(&w);
634 : : return rc;
635 : : /* LCOV_EXCL_STOP */
636 : : }
637 : 274 : rc = tp_bs_write_bits(w, enc->sym.symbol_count, 8);
638 : 274 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
639 : : /* LCOV_EXCL_START */
640 : : tp_bs_writer_destroy(&w);
641 : : return rc;
642 : : /* LCOV_EXCL_STOP */
643 : : }
644 : :
645 : : /* Write special symbol map (6 * bps bits) */
646 [ + + ]: 1918 : for (int c = 0; c < TP_NUM_CONTROL_CODES; c++) {
647 : 1644 : rc = tp_bs_write_bits(w, enc->sym.ctrl_codes[c], enc->sym.bits_per_symbol);
648 : 1644 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
649 : : /* LCOV_EXCL_START */
650 : : tp_bs_writer_destroy(&w);
651 : : return rc;
652 : : /* LCOV_EXCL_STOP */
653 : : }
654 : : }
655 : :
656 : : /* Write symbol table (VarInt codepoints for non-control symbols) */
657 [ + + ]: 70418 : for (int i = 0; i < 256; i++) {
658 : : /* Find byte values that are in the alphabet, in code order */
659 : : }
660 : : /* Actually: write in code order, skipping control codes */
661 : : {
662 : 274 : uint32_t max_code = enc->sym.symbol_count;
663 [ + + ]: 2986 : for (uint32_t code = TP_NUM_CONTROL_CODES; code < max_code; code++) {
664 : 2712 : uint8_t byte_val = 0;
665 [ + - ]: 2712 : if (code < 256)
666 : 2712 : byte_val = enc->sym.reverse_map[code];
667 : 2712 : rc = tp_bs_write_varint_u(w, byte_val);
668 : 2712 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
669 : : /* LCOV_EXCL_START */
670 : : tp_bs_writer_destroy(&w);
671 : : return rc;
672 : : /* LCOV_EXCL_STOP */
673 : : }
674 : : }
675 : : }
676 : :
677 : : /* Record trie data offset (relative to data stream start) */
678 : 274 : uint64_t trie_data_offset = tp_bs_writer_position(w) - data_start;
679 : :
680 : : /* Write prefix trie */
681 : 274 : uint32_t value_idx = 0;
682 [ + + ]: 274 : if (enc->count > 0) {
683 : 268 : rc = trie_write(enc, w, 0, enc->count, 0, has_values, &value_idx);
684 : 268 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
685 : : /* LCOV_EXCL_START */
686 : : tp_bs_writer_destroy(&w);
687 : : return rc;
688 : : /* LCOV_EXCL_STOP */
689 : : }
690 : : }
691 : :
692 : : /* Record value store offset */
693 : 274 : uint64_t value_store_offset = tp_bs_writer_position(w) - data_start;
694 : :
695 : : /* Write value store */
696 [ + + ]: 274 : if (has_values) {
697 [ + + ]: 203776 : for (uint32_t i = 0; i < enc->count; i++) {
698 : 203540 : rc = tp_value_encode(w, &enc->entries[i].val);
699 : 203540 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
700 : : /* LCOV_EXCL_START */
701 : : tp_bs_writer_destroy(&w);
702 : : return rc;
703 : : /* LCOV_EXCL_STOP */
704 : : }
705 : : }
706 : : }
707 : :
708 : : /* Total data bits */
709 : 274 : uint64_t total_data_bits = tp_bs_writer_position(w) - data_start;
710 : :
711 : : /* The header stores these three as 32-bit *bit* counts, so the data
712 : : stream cannot exceed 2^32 bits (512 MB). Truncating them silently
713 : : would produce a file with a valid CRC over wrong offsets that decodes
714 : : to garbage -- the same failure the alphabet check exists to prevent.
715 : : Refuse to build it instead. Lifting this ceiling needs the wider
716 : : header of format v2. */
717 [ + - + - : 274 : if (total_data_bits > UINT32_MAX || trie_data_offset > UINT32_MAX ||
- + ]
718 : : value_store_offset > UINT32_MAX) {
719 : 0 : tp_bs_writer_destroy(&w);
720 : 0 : return TP_ERR_OVERFLOW;
721 : : }
722 : :
723 : : /* Align to byte boundary before CRC */
724 : 274 : rc = tp_bs_writer_align_to_byte(w);
725 : 274 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
726 : : /* LCOV_EXCL_START */
727 : : tp_bs_writer_destroy(&w);
728 : : return rc;
729 : : /* LCOV_EXCL_STOP */
730 : : }
731 : :
732 : : /* Now patch the header with final offsets */
733 : : /* We need to overwrite bytes 12-27 with the correct offsets */
734 : : const uint8_t *wbuf;
735 : : uint64_t wbit_len;
736 : 274 : tp_bs_writer_get_buffer(w, &wbuf, &wbit_len);
737 : :
738 : : /* Build the final buffer: first get current data */
739 : 274 : size_t pre_crc_bytes = (size_t)(tp_bs_writer_position(w) / 8);
740 : :
741 : : /* Compute CRC-32 over everything so far */
742 : 274 : uint32_t crc = tp_crc32(wbuf, pre_crc_bytes);
743 : :
744 : : /* Write CRC-32 as 4 bytes at the end */
745 : 274 : rc = tp_bs_write_u32(w, crc);
746 : 274 : if (rc != TP_OK) { /* LCOV_EXCL_BR_LINE */
747 : : /* LCOV_EXCL_START */
748 : : tp_bs_writer_destroy(&w);
749 : : return rc;
750 : : /* LCOV_EXCL_STOP */
751 : : }
752 : :
753 : : /* Detach buffer */
754 : : uint8_t *out_buf;
755 : : size_t out_byte_len;
756 : : uint64_t out_bit_len;
757 : 274 : rc = tp_bs_writer_detach_buffer(w, &out_buf, &out_byte_len, &out_bit_len);
758 : 274 : tp_bs_writer_destroy(&w);
759 : 274 : if (rc != TP_OK) /* LCOV_EXCL_BR_LINE */
760 : : return rc; /* LCOV_EXCL_LINE */
761 : :
762 : : /* Patch header fields in the output buffer */
763 : : /* trie_data_offset at byte 12 (big-endian) */
764 : 274 : out_buf[12] = (uint8_t)(trie_data_offset >> 24);
765 : 274 : out_buf[13] = (uint8_t)(trie_data_offset >> 16);
766 : 274 : out_buf[14] = (uint8_t)(trie_data_offset >> 8);
767 : 274 : out_buf[15] = (uint8_t)(trie_data_offset);
768 : : /* value_store_offset at byte 16 */
769 : 274 : out_buf[16] = (uint8_t)(value_store_offset >> 24);
770 : 274 : out_buf[17] = (uint8_t)(value_store_offset >> 16);
771 : 274 : out_buf[18] = (uint8_t)(value_store_offset >> 8);
772 : 274 : out_buf[19] = (uint8_t)(value_store_offset);
773 : : /* suffix_table_offset at byte 20 = 0 (no suffix table) */
774 : 274 : out_buf[20] = 0;
775 : 274 : out_buf[21] = 0;
776 : 274 : out_buf[22] = 0;
777 : 274 : out_buf[23] = 0;
778 : : /* total_data_bits at byte 24 */
779 : 274 : out_buf[24] = (uint8_t)(total_data_bits >> 24);
780 : 274 : out_buf[25] = (uint8_t)(total_data_bits >> 16);
781 : 274 : out_buf[26] = (uint8_t)(total_data_bits >> 8);
782 : 274 : out_buf[27] = (uint8_t)(total_data_bits);
783 : :
784 : : /* Recompute CRC over the patched data (everything except last 4 bytes) */
785 : 274 : size_t crc_data_len = out_byte_len - 4;
786 : 274 : crc = tp_crc32(out_buf, crc_data_len);
787 : 274 : out_buf[crc_data_len] = (uint8_t)(crc >> 24);
788 : 274 : out_buf[crc_data_len + 1] = (uint8_t)(crc >> 16);
789 : 274 : out_buf[crc_data_len + 2] = (uint8_t)(crc >> 8);
790 : 274 : out_buf[crc_data_len + 3] = (uint8_t)(crc);
791 : :
792 : 274 : *buf = out_buf;
793 : 274 : *len = out_byte_len;
794 : 274 : return TP_OK;
795 : : }
796 : :
797 : : /* ── Reset ───────────────────────────────────────────────────────────── */
798 : :
799 : 9 : tp_result tp_encoder_reset(tp_encoder *enc)
800 : : {
801 [ + + ]: 9 : if (!enc)
802 : 1 : return TP_ERR_INVALID_PARAM;
803 [ + + ]: 51 : for (uint32_t i = 0; i < enc->count; i++) {
804 : 43 : value_free_copy(&enc->entries[i].val);
805 : 43 : free(enc->entries[i].key);
806 : : }
807 : 8 : free(enc->entries);
808 : 8 : enc->entries = NULL;
809 : 8 : enc->entries_cap = 0;
810 : 8 : enc->count = 0;
811 : 8 : enc->sorted = false;
812 : 8 : return TP_OK;
813 : : }
|
