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