1 #include "./deorummolae.h"
2
3 #include <array>
4 #include <cstdio>
5
6 #include "./esaxx/sais.hxx"
7
8 /* Used for quick SA-entry to file mapping. Each file is padded to size that
9 is a multiple of chunk size. */
10 #define CHUNK_SIZE 64
11 /* Length of substring that is considered to be covered by dictionary string. */
12 #define CUT_MATCH 6
13 /* Minimal dictionary entry size. */
14 #define MIN_MATCH 24
15
16 /* Non tunable definitions. */
17 #define CHUNK_MASK (CHUNK_SIZE - 1)
18 #define COVERAGE_SIZE (1 << (DM_LOG_MAX_FILES - 6))
19
20 /* File coverage: every bit set to 1 denotes a file covered by an isle. */
21 typedef std::array<uint64_t, COVERAGE_SIZE> Coverage;
22
23 /* Symbol of text alphabet. */
24 typedef int32_t TextChar;
25
26 /* Pointer to position in text. */
27 typedef uint32_t TextIdx;
28
29 /* SAIS sarray_type; unfortunately, must be a signed type. */
30 typedef int32_t TextSaIdx;
31
popcount(uint64_t u)32 static size_t popcount(uint64_t u) {
33 return static_cast<size_t>(__builtin_popcountll(u));
34 }
35
36 /* Condense terminators and pad file entries. */
rewriteText(std::vector<TextChar> * text)37 static void rewriteText(std::vector<TextChar>* text) {
38 TextChar terminator = text->back();
39 TextChar prev = terminator;
40 TextIdx to = 0;
41 for (TextIdx from = 0; from < text->size(); ++from) {
42 TextChar next = text->at(from);
43 if (next < 256 || prev < 256) {
44 text->at(to++) = next;
45 if (next >= 256) terminator = next;
46 }
47 prev = next;
48 }
49 text->resize(to);
50 if (text->empty()) text->push_back(terminator);
51 while (text->size() & CHUNK_MASK) text->push_back(terminator);
52 }
53
54 /* Reenumerate terminators for smaller alphabet. */
remapTerminators(std::vector<TextChar> * text,TextChar * next_terminator)55 static void remapTerminators(std::vector<TextChar>* text,
56 TextChar* next_terminator) {
57 TextChar prev = -1;
58 TextChar x = 256;
59 for (TextIdx i = 0; i < text->size(); ++i) {
60 TextChar next = text->at(i);
61 if (next < 256) { // Char.
62 // Do nothing.
63 } else if (prev < 256) { // Terminator after char.
64 next = x++;
65 } else { // Terminator after terminator.
66 next = prev;
67 }
68 text->at(i) = next;
69 prev = next;
70 }
71 *next_terminator = x;
72 }
73
74 /* Combine all file entries; create mapping position->file. */
buildFullText(std::vector<std::vector<TextChar>> * data,std::vector<TextChar> * full_text,std::vector<TextIdx> * file_map,std::vector<TextIdx> * file_offset,TextChar * next_terminator)75 static void buildFullText(std::vector<std::vector<TextChar>>* data,
76 std::vector<TextChar>* full_text, std::vector<TextIdx>* file_map,
77 std::vector<TextIdx>* file_offset, TextChar* next_terminator) {
78 file_map->resize(0);
79 file_offset->resize(0);
80 full_text->resize(0);
81 for (TextIdx i = 0; i < data->size(); ++i) {
82 file_offset->push_back(full_text->size());
83 std::vector<TextChar>& file = data->at(i);
84 rewriteText(&file);
85 full_text->insert(full_text->end(), file.begin(), file.end());
86 file_map->insert(file_map->end(), file.size() / CHUNK_SIZE, i);
87 }
88 if (false) remapTerminators(full_text, next_terminator);
89 }
90
91 /* Build longest-common-prefix based on suffix array and text.
92 TODO: borrowed -> unknown efficiency. */
buildLcp(std::vector<TextChar> * text,std::vector<TextIdx> * sa,std::vector<TextIdx> * lcp,std::vector<TextIdx> * invese_sa)93 static void buildLcp(std::vector<TextChar>* text, std::vector<TextIdx>* sa,
94 std::vector<TextIdx>* lcp, std::vector<TextIdx>* invese_sa) {
95 TextIdx size = static_cast<TextIdx>(text->size());
96 lcp->resize(size);
97 TextIdx k = 0;
98 lcp->at(size - 1) = 0;
99 for (TextIdx i = 0; i < size; ++i) {
100 if (invese_sa->at(i) == size - 1) {
101 k = 0;
102 continue;
103 }
104 // Suffix which follow i-th suffix.
105 TextIdx j = sa->at(invese_sa->at(i) + 1);
106 while (i + k < size && j + k < size && text->at(i + k) == text->at(j + k)) {
107 ++k;
108 }
109 lcp->at(invese_sa->at(i)) = k;
110 if (k > 0) --k;
111 }
112 }
113
114 /* Isle is a range in SA with LCP not less than some value.
115 When we raise the LCP requirement, the isle sunks and smaller isles appear
116 instead. */
117 typedef struct {
118 TextIdx lcp;
119 TextIdx l;
120 TextIdx r;
121 Coverage coverage;
122 } Isle;
123
124 /* Helper routine for `cutMatch`. */
poisonData(TextIdx pos,TextIdx length,std::vector<std::vector<TextChar>> * data,std::vector<TextIdx> * file_map,std::vector<TextIdx> * file_offset,TextChar * next_terminator)125 static void poisonData(TextIdx pos, TextIdx length,
126 std::vector<std::vector<TextChar>>* data, std::vector<TextIdx>* file_map,
127 std::vector<TextIdx>* file_offset, TextChar* next_terminator) {
128 TextIdx f = file_map->at(pos / CHUNK_SIZE);
129 pos -= file_offset->at(f);
130 std::vector<TextChar>& file = data->at(f);
131 TextIdx l = (length == CUT_MATCH) ? CUT_MATCH : 1;
132 for (TextIdx j = 0; j < l; j++, pos++) {
133 if (file[pos] >= 256) continue;
134 if (file[pos + 1] >= 256) {
135 file[pos] = file[pos + 1];
136 } else if (pos > 0 && file[pos - 1] >= 256) {
137 file[pos] = file[pos - 1];
138 } else {
139 file[pos] = (*next_terminator)++;
140 }
141 }
142 }
143
144 /* Remove substrings of a given match from files.
145 Substrings are replaced with unique terminators, so next iteration SA would
146 not allow to cross removed areas. */
cutMatch(std::vector<std::vector<TextChar>> * data,TextIdx index,TextIdx length,std::vector<TextIdx> * sa,std::vector<TextIdx> * lcp,std::vector<TextIdx> * invese_sa,TextChar * next_terminator,std::vector<TextIdx> * file_map,std::vector<TextIdx> * file_offset)147 static void cutMatch(std::vector<std::vector<TextChar>>* data, TextIdx index,
148 TextIdx length, std::vector<TextIdx>* sa, std::vector<TextIdx>* lcp,
149 std::vector<TextIdx>* invese_sa, TextChar* next_terminator,
150 std::vector<TextIdx>* file_map, std::vector<TextIdx>* file_offset) {
151 while (length >= CUT_MATCH) {
152 TextIdx i = index;
153 while (lcp->at(i) >= length) {
154 i++;
155 poisonData(
156 sa->at(i), length, data, file_map, file_offset, next_terminator);
157 }
158 while (true) {
159 poisonData(
160 sa->at(index), length, data, file_map, file_offset, next_terminator);
161 if (index == 0 || lcp->at(index - 1) < length) break;
162 index--;
163 }
164 length--;
165 index = invese_sa->at(sa->at(index) + 1);
166 }
167 }
168
DM_generate(size_t dictionary_size_limit,const std::vector<size_t> & sample_sizes,const uint8_t * sample_data)169 std::string DM_generate(size_t dictionary_size_limit,
170 const std::vector<size_t>& sample_sizes, const uint8_t* sample_data) {
171 {
172 TextIdx tmp = static_cast<TextIdx>(dictionary_size_limit);
173 if ((tmp != dictionary_size_limit) || (tmp > 1u << 30)) {
174 fprintf(stderr, "dictionary_size_limit is too large\n");
175 return "";
176 }
177 }
178
179 /* Could use 256 + '0' for easier debugging. */
180 TextChar next_terminator = 256;
181
182 std::string output;
183 std::vector<std::vector<TextChar>> data;
184
185 TextIdx offset = 0;
186 size_t num_samples = sample_sizes.size();
187 if (num_samples > DM_MAX_FILES) num_samples = DM_MAX_FILES;
188 for (size_t n = 0; n < num_samples; ++n) {
189 TextIdx delta = static_cast<TextIdx>(sample_sizes[n]);
190 if (delta != sample_sizes[n]) {
191 fprintf(stderr, "sample is too large\n");
192 return "";
193 }
194 if (delta == 0) {
195 fprintf(stderr, "0-length samples are prohibited\n");
196 return "";
197 }
198 TextIdx next_offset = offset + delta;
199 if (next_offset <= offset) {
200 fprintf(stderr, "corpus is too large\n");
201 return "";
202 }
203 data.push_back(
204 std::vector<TextChar>(sample_data + offset, sample_data + next_offset));
205 offset = next_offset;
206 data.back().push_back(next_terminator++);
207 }
208
209 /* Most arrays are allocated once, and then just resized to smaller and
210 smaller sizes. */
211 std::vector<TextChar> full_text;
212 std::vector<TextIdx> file_map;
213 std::vector<TextIdx> file_offset;
214 std::vector<TextIdx> sa;
215 std::vector<TextIdx> invese_sa;
216 std::vector<TextIdx> lcp;
217 std::vector<Isle> isles;
218 std::vector<char> output_data;
219 TextIdx total = 0;
220 TextIdx total_cost = 0;
221 TextIdx best_cost;
222 Isle best_isle;
223 size_t min_count = num_samples;
224
225 while (true) {
226 TextIdx max_match = static_cast<TextIdx>(dictionary_size_limit) - total;
227 buildFullText(&data, &full_text, &file_map, &file_offset, &next_terminator);
228 sa.resize(full_text.size());
229 /* Hopefully, non-negative TextSaIdx is the same sa TextIdx counterpart. */
230 saisxx(full_text.data(), reinterpret_cast<TextSaIdx*>(sa.data()),
231 static_cast<TextChar>(full_text.size()), next_terminator);
232 invese_sa.resize(full_text.size());
233 for (TextIdx i = 0; i < full_text.size(); ++i) {
234 invese_sa[sa[i]] = i;
235 }
236 buildLcp(&full_text, &sa, &lcp, &invese_sa);
237
238 /* Do not rebuild SA/LCP, just use different selection. */
239 retry:
240 best_cost = 0;
241 best_isle = {0, 0, 0, {{0}}};
242 isles.resize(0);
243 isles.push_back(best_isle);
244
245 for (TextIdx i = 0; i < lcp.size(); ++i) {
246 TextIdx l = i;
247 Coverage cov = {{0}};
248 size_t f = file_map[sa[i] / CHUNK_SIZE];
249 cov[f >> 6] = (static_cast<uint64_t>(1)) << (f & 63);
250 while (lcp[i] < isles.back().lcp) {
251 Isle& top = isles.back();
252 top.r = i;
253 l = top.l;
254 for (size_t x = 0; x < cov.size(); ++x) cov[x] |= top.coverage[x];
255 size_t count = 0;
256 for (size_t x = 0; x < cov.size(); ++x) count += popcount(cov[x]);
257 TextIdx effective_lcp = top.lcp;
258 /* Restrict (last) dictionary entry length. */
259 if (effective_lcp > max_match) effective_lcp = max_match;
260 TextIdx cost = count * effective_lcp;
261 if (cost > best_cost && count >= min_count &&
262 effective_lcp >= MIN_MATCH) {
263 best_cost = cost;
264 best_isle = top;
265 best_isle.lcp = effective_lcp;
266 }
267 isles.pop_back();
268 for (size_t x = 0; x < cov.size(); ++x) {
269 isles.back().coverage[x] |= cov[x];
270 }
271 }
272 if (lcp[i] > isles.back().lcp) isles.push_back({lcp[i], l, 0, {{0}}});
273 for (size_t x = 0; x < cov.size(); ++x) {
274 isles.back().coverage[x] |= cov[x];
275 }
276 }
277
278 /* When saturated matches do not match length restrictions, lower the
279 saturation requirements. */
280 if (best_cost == 0 || best_isle.lcp < MIN_MATCH) {
281 if (min_count >= 8) {
282 min_count = (min_count * 7) / 8;
283 fprintf(stderr, "Retry: min_count=%zu\n", min_count);
284 goto retry;
285 }
286 break;
287 }
288
289 /* Save the entry. */
290 fprintf(stderr, "Savings: %d+%d, dictionary: %d+%d\n",
291 total_cost, best_cost, total, best_isle.lcp);
292 int* piece = &full_text[sa[best_isle.l]];
293 output.insert(output.end(), piece, piece + best_isle.lcp);
294 total += best_isle.lcp;
295 total_cost += best_cost;
296 cutMatch(&data, best_isle.l, best_isle.lcp, &sa, &lcp, &invese_sa,
297 &next_terminator, &file_map, &file_offset);
298 if (total >= dictionary_size_limit) break;
299 }
300
301 return output;
302 }
303