Branch data Line data Source code
1 : : /**
2 : : * @file v2_tails.c
3 : : * @brief Suffix-merged tail pool — format v2 §8.1.
4 : : *
5 : : * Copyright (c) 2026 M. A. Chatterjee <deftio at deftio dot com>
6 : : * BSD-2-Clause — see LICENSE.txt
7 : : */
8 : :
9 : : #include "triepack/v2_tails.h"
10 : :
11 : : #include <stdlib.h>
12 : : #include <string.h>
13 : :
14 : : typedef struct {
15 : : const uint8_t *bytes;
16 : : uint32_t len;
17 : : uint64_t offset; /* assigned during emit */
18 : : uint64_t seq; /* index in the caller's array, to map refs back */
19 : : uint64_t distinct_of; /* index into the distinct table */
20 : : } entry;
21 : :
22 : : struct tp2_tailpool {
23 : : uint8_t *pool;
24 : : uint64_t pool_len;
25 : : uint64_t distinct;
26 : : tp2_tail_ref *refs; /* one per input tail, in input order */
27 : : uint64_t count;
28 : : };
29 : :
30 : : /* §8.1 step 2: order by reversed byte sequence, ascending — compare the last
31 : : byte first. Bytes compare as *unsigned*; a signed char here would sort 0x80
32 : : below 0x01 and silently reorder the pool for any non-ASCII data. */
33 : 8858 : static int cmp_reversed(const void *a, const void *b)
34 : : {
35 : 8858 : const entry *x = a, *y = b;
36 : 8858 : uint32_t i = 0;
37 [ + + + + ]: 40723 : while (i < x->len && i < y->len) {
38 : 40356 : uint8_t xb = x->bytes[x->len - 1 - i];
39 : 40356 : uint8_t yb = y->bytes[y->len - 1 - i];
40 [ + + ]: 40356 : if (xb != yb)
41 [ + + ]: 8491 : return xb < yb ? -1 : 1;
42 : 31865 : i++;
43 : : }
44 [ + + ]: 367 : if (x->len != y->len)
45 [ + + ]: 365 : return x->len < y->len ? -1 : 1;
46 : : /* Equal content: order by input position so the sort is total and the
47 : : result cannot depend on the sort implementation's stability. */
48 [ - + ]: 2 : return (x->seq < y->seq) ? -1 : (x->seq > y->seq);
49 : : }
50 : :
51 : 1026 : static int same_tail(const entry *a, const entry *b)
52 : : {
53 [ + + + + ]: 1026 : return a->len == b->len && memcmp(a->bytes, b->bytes, a->len) == 0;
54 : : }
55 : :
56 : : /* Is `s` a proper suffix of `big`? */
57 : 1024 : static int is_proper_suffix(const entry *s, const entry *big)
58 : : {
59 [ + + + + ]: 1024 : return s->len < big->len && memcmp(big->bytes + big->len - s->len, s->bytes, s->len) == 0;
60 : : }
61 : :
62 : 14 : tp2_tailpool *tp2_tailpool_build(const uint8_t *const *tails, const uint32_t *lens, uint64_t count)
63 : : {
64 : 14 : tp2_tailpool *tp = calloc(1, sizeof(*tp));
65 [ - + ]: 14 : if (!tp)
66 : 0 : return NULL;
67 : 14 : tp->count = count;
68 [ + + ]: 14 : if (count == 0) {
69 : 1 : tp->pool = calloc(1, 1);
70 [ - + ]: 1 : return tp->pool ? tp : (free(tp), NULL);
71 : : }
72 : :
73 : 13 : tp->refs = calloc((size_t)count, sizeof(*tp->refs));
74 : 13 : entry *sorted = calloc((size_t)count, sizeof(*sorted));
75 [ + - - + ]: 13 : if (!tp->refs || !sorted) {
76 : 0 : free(sorted);
77 : 0 : tp2_tailpool_destroy(&tp);
78 : 0 : return NULL;
79 : : }
80 : :
81 [ + + ]: 1052 : for (uint64_t i = 0; i < count; i++) {
82 : 1039 : sorted[i].bytes = tails[i];
83 : 1039 : sorted[i].len = lens[i];
84 : 1039 : sorted[i].seq = i;
85 : : }
86 : :
87 : : /* Step 2: sort by reversed bytes. */
88 : 13 : qsort(sorted, (size_t)count, sizeof(*sorted), cmp_reversed);
89 : :
90 : : /* Step 1 (completed): collapse to the *distinct* tails. Equal tails are
91 : : adjacent after the sort, so this is a single pass. */
92 : 13 : uint64_t ndistinct = 0;
93 [ + + ]: 1052 : for (uint64_t i = 0; i < count; i++) {
94 [ + + + + ]: 1039 : if (i > 0 && same_tail(&sorted[i], &sorted[i - 1]))
95 : 2 : sorted[i].distinct_of = ndistinct - 1;
96 : : else
97 : 1037 : sorted[i].distinct_of = ndistinct++;
98 : : }
99 : :
100 : 13 : entry *distinct = calloc((size_t)ndistinct, sizeof(*distinct));
101 [ - + ]: 13 : if (!distinct) {
102 : 0 : free(sorted);
103 : 0 : tp2_tailpool_destroy(&tp);
104 : 0 : return NULL;
105 : : }
106 [ + + ]: 1052 : for (uint64_t i = 0; i < count; i++)
107 : 1039 : distinct[sorted[i].distinct_of] = sorted[i];
108 : :
109 : : /* Worst case the pool is every distinct tail concatenated. */
110 : 13 : uint64_t cap = 0;
111 [ + + ]: 1050 : for (uint64_t i = 0; i < ndistinct; i++)
112 : 1037 : cap += distinct[i].len;
113 [ + - ]: 13 : tp->pool = calloc((size_t)(cap ? cap : 1), 1);
114 [ - + ]: 13 : if (!tp->pool) {
115 : 0 : free(sorted);
116 : 0 : free(distinct);
117 : 0 : tp2_tailpool_destroy(&tp);
118 : 0 : return NULL;
119 : : }
120 : :
121 : : /* Step 3: walk from last to first, tracking the most recently emitted
122 : : tail. A tail that is a proper suffix of it costs no bytes. */
123 : 13 : int64_t prev = -1;
124 [ + + ]: 1050 : for (int64_t i = (int64_t)ndistinct - 1; i >= 0; i--) {
125 [ + + + + ]: 1037 : if (prev >= 0 && is_proper_suffix(&distinct[i], &distinct[prev])) {
126 : 114 : distinct[i].offset = distinct[prev].offset + distinct[prev].len - distinct[i].len;
127 : 114 : continue;
128 : : }
129 : 923 : distinct[i].offset = tp->pool_len;
130 : 923 : memcpy(tp->pool + tp->pool_len, distinct[i].bytes, distinct[i].len);
131 : 923 : tp->pool_len += distinct[i].len;
132 : 923 : prev = i;
133 : : }
134 : :
135 : : /* Map every input tail back to its distinct entry's placement. */
136 [ + + ]: 1052 : for (uint64_t i = 0; i < count; i++) {
137 : 1039 : const entry *d = &distinct[sorted[i].distinct_of];
138 : 1039 : tp->refs[sorted[i].seq].offset = d->offset;
139 : 1039 : tp->refs[sorted[i].seq].length = d->len;
140 : : }
141 : :
142 : 13 : tp->distinct = ndistinct;
143 : 13 : free(sorted);
144 : 13 : free(distinct);
145 : 13 : return tp;
146 : : }
147 : :
148 : 16 : void tp2_tailpool_destroy(tp2_tailpool **tp)
149 : : {
150 [ + + + + ]: 16 : if (!tp || !*tp)
151 : 2 : return;
152 : 14 : free((*tp)->pool);
153 : 14 : free((*tp)->refs);
154 : 14 : free(*tp);
155 : 14 : *tp = NULL;
156 : : }
157 : :
158 : 21 : const uint8_t *tp2_tailpool_bytes(const tp2_tailpool *tp)
159 : : {
160 [ + - ]: 21 : return tp ? tp->pool : NULL;
161 : : }
162 : :
163 : 1046 : uint64_t tp2_tailpool_size(const tp2_tailpool *tp)
164 : : {
165 [ + - ]: 1046 : return tp ? tp->pool_len : 0;
166 : : }
167 : :
168 : 4 : uint64_t tp2_tailpool_distinct(const tp2_tailpool *tp)
169 : : {
170 [ + - ]: 4 : return tp ? tp->distinct : 0;
171 : : }
172 : :
173 : 1045 : tp2_tail_ref tp2_tailpool_ref(const tp2_tailpool *tp, uint64_t i)
174 : : {
175 : 1045 : tp2_tail_ref none = {0, 0};
176 [ + - + - : 1045 : if (!tp || !tp->refs || i >= tp->count)
- + ]
177 : 0 : return none;
178 : 1045 : return tp->refs[i];
179 : : }
|
