Debian Codegraph @

src/alg/compress.c

raw
1 /*
2 * compress.c - recommended sequences of algorithms invocations to compress
3 */
4
5
6 #include "../base/mdjvucfg.h"
7 #include <minidjvu/minidjvu.h>
8 #include <stdlib.h>
9 #include <stdio.h>
10 #include <assert.h>
11
12 struct MinidjvuCompressionOptions
13 {
14 int clean;
15 int verbose;
16 int no_prototypes;
17 int averaging;
18 int report;
19 int report_start_page;
20 int report_total_pages;
21 mdjvu_matcher_options_t matcher_options;
22 };
23
24 MDJVU_IMPLEMENT mdjvu_compression_options_t mdjvu_compression_options_create()
25 {
26 mdjvu_compression_options_t opt = (mdjvu_compression_options_t)
27 malloc(sizeof(struct MinidjvuCompressionOptions));
28 mdjvu_init();
29 opt->clean = 0;
30 opt->verbose = 0;
31 opt->report = 0;
32 opt->averaging = 0;
33 opt->no_prototypes = 0;
34 opt->matcher_options = NULL;
35 return opt;
36 }
37
38 MDJVU_IMPLEMENT void mdjvu_compression_options_destroy(mdjvu_compression_options_t opt)
39 {
40 if (opt->matcher_options)
41 mdjvu_matcher_options_destroy(opt->matcher_options);
42 free(opt);
43 }
44
45 MDJVU_IMPLEMENT void mdjvu_set_matcher_options(mdjvu_compression_options_t opt, mdjvu_matcher_options_t v)
46 {
47 if (opt->matcher_options)
48 mdjvu_matcher_options_destroy(opt->matcher_options);
49 opt->matcher_options = v;
50 }
51 MDJVU_IMPLEMENT void mdjvu_set_clean(mdjvu_compression_options_t opt, int v)
52 {opt->clean = v;}
53 MDJVU_IMPLEMENT void mdjvu_set_verbose(mdjvu_compression_options_t opt, int v)
54 {opt->verbose = v;}
55 MDJVU_IMPLEMENT void mdjvu_set_averaging(mdjvu_compression_options_t opt, int v)
56 {opt->averaging = v;}
57 MDJVU_IMPLEMENT void mdjvu_set_no_prototypes(mdjvu_compression_options_t opt, int v)
58 {opt->no_prototypes = v;}
59 MDJVU_IMPLEMENT void mdjvu_set_report(mdjvu_compression_options_t opt, int v)
60 {opt->report = v;}
61 MDJVU_IMPLEMENT void mdjvu_set_report_start_page(mdjvu_compression_options_t opt, int v)
62 {opt->report_start_page = v;}
63 MDJVU_IMPLEMENT void mdjvu_set_report_total_pages(mdjvu_compression_options_t opt, int v)
64 {opt->report_total_pages = v;}
65
66 static void find_substitutions(mdjvu_image_t image,
67 struct MinidjvuCompressionOptions *opt)
68 {
69 mdjvu_matcher_options_t m_opt = opt->matcher_options;
70 int32 i, n = mdjvu_image_get_bitmap_count(image);
71 int32 *tags = (int32 *) malloc(n * sizeof(int32));
72 int32 max_tag = mdjvu_classify_bitmaps(image, tags, m_opt, /* centers_needed: */ opt->averaging);
73 mdjvu_bitmap_t *representatives = (mdjvu_bitmap_t *)
74 calloc(max_tag + 1 /* cause starts with 1 */, sizeof(mdjvu_bitmap_t));
75 int32 *cx = (int32 *) malloc(n * sizeof(int32));
76 int32 *cy = (int32 *) malloc(n * sizeof(int32));
77
78 if (!mdjvu_image_has_substitutions(image))
79 mdjvu_image_enable_substitutions(image);
80 if (!opt->averaging)
81 {
82 for (i = 0; i < n; i++)
83 {
84 if (!representatives[tags[i]])
85 representatives[tags[i]] = mdjvu_image_get_bitmap(image, i);
86 }
87 }
88 else
89 {
90 /* Average */
91 mdjvu_bitmap_t *sources = (mdjvu_bitmap_t *) calloc(n, sizeof(mdjvu_bitmap_t));
92 for (i = 1; i < max_tag; i++)
93 {
94 int j, sources_found = 0;
95 mdjvu_bitmap_t rep;
96
97 for (j = 0; j < n; j++)
98 {
99 if (tags[j] == i)
100 sources[sources_found++] = mdjvu_image_get_bitmap(image, j);
101 }
102
103 for (j = 0; j < sources_found; j++)
104 mdjvu_image_get_center(image, sources[j], &cx[j], &cy[j]);
105
106 rep = mdjvu_average(sources, sources_found, cx, cy);
107 mdjvu_image_add_bitmap(image, rep);
108 mdjvu_image_set_substitution(image, rep, rep);
109 representatives[i] = rep;
110 }
111
112 mdjvu_image_disable_centers(image);
113 free(sources);
114 }
115 assert(mdjvu_image_check_indices(image));
116 free(cx);
117 free(cy);
118
119
120 for (i = 0; i < n; i++)
121 {
122 if (!tags[i]) continue; /* that's for images with no-subst flag */
123 mdjvu_image_set_substitution(image,
124 mdjvu_image_get_bitmap(image, i),
125 representatives[tags[i]]);
126 }
127
128 free(representatives);
129 free(tags);
130 }
131
132
133 static int32 count_prototypes(mdjvu_image_t image)
134 {
135 int32 i, s = 0, n = mdjvu_image_get_bitmap_count(image);
136 for (i = 0; i < n; i++)
137 {
138 mdjvu_bitmap_t bmp = mdjvu_image_get_bitmap(image, i);
139 if (mdjvu_image_get_prototype(image, bmp))
140 s++;
141 }
142 return s;
143 }
144
145
146 MDJVU_IMPLEMENT void mdjvu_compress_image(mdjvu_image_t image, mdjvu_compression_options_t opt)
147 {
148 mdjvu_compression_options_t options;
149 if (opt)
150 options = opt;
151 else
152 options = mdjvu_compression_options_create();
153
154 if (options->verbose) puts(_("deciding what pieces are letters"));
155 mdjvu_calculate_not_a_letter_flags(image);
156
157 if (options->verbose) puts(_("sorting blits"));
158 mdjvu_sort_blits(image);
159 if (options->verbose) puts(_("sorting bitmaps"));
160 mdjvu_image_sort_bitmaps(image);
161
162 if (options->matcher_options)
163 {
164 if (options->verbose) puts(_("matching patterns"));
165 find_substitutions(image, options);
166
167 if (options->verbose) puts(_("adjusting substitution coordinates"));
168 mdjvu_adjust(image);
169
170 if (options->verbose) puts(_("removing unused bitmaps"));
171 mdjvu_image_remove_unused_bitmaps(image);
172
173 if (options->verbose)
174 {
175 printf(_("the image now has %d bitmaps\n"),
176 mdjvu_image_get_bitmap_count(image));
177 }
178
179 if (options->averaging)
180 {
181 if (options->verbose) puts(_("sorting bitmaps (again)"));
182 mdjvu_image_sort_bitmaps(image);
183 }
184 }
185
186 if (options->no_prototypes)
187 {
188 mdjvu_image_enable_prototypes(image);
189 }
190 else
191 {
192 if (options->verbose) puts(_("finding prototypes"));
193 mdjvu_find_prototypes(image);
194 if (options->verbose)
195 {
196 printf(_("%d bitmaps have prototypes\n"),
197 count_prototypes(image));
198 }
199 }
200
201 if (!opt)
202 mdjvu_compression_options_destroy(options);
203 }
204
205
206 /* ----------------------- MULTIPAGE STUFF ------------------------------ */
207
208
209 /* Fill the dictionary with the bitmaps chosen with dictionary_flags.
210 * The `representatives' array is filled with new dictionary letters as needed.
211 *
212 * Arguments:
213 * max_tag - obviously, the maximal tag; tag 0 is unused
214 * representatives - [0..max_tag] array of letters; tag 0 is unused
215 * dictionary_flags - [0..max_tag] array of 1/0 flags; tag 0 is unused
216 *
217 * Returns:
218 * the newly created dictionary (a 0 x 0 image to be destroyed later)
219 *
220 * FIXME: cloning bitmaps is a waste of memory - better to detach them instead.
221 */
222
223 static mdjvu_image_t get_dictionary(int32 max_tag,
224 mdjvu_bitmap_t *representatives,
225 unsigned char *dictionary_flags)
226 {
227 mdjvu_image_t dictionary = mdjvu_image_create(0,0); /* 0 x 0 image */
228 int32 tag;
229 for (tag = 1; tag <= max_tag; tag++)
230 {
231 mdjvu_bitmap_t clone;
232 if (!dictionary_flags[tag]) continue;
233 clone = mdjvu_bitmap_clone(representatives[tag]);
234 representatives[tag] = clone;
235 mdjvu_image_add_bitmap(dictionary, clone);
236 }
237 return dictionary;
238 }
239
240
241 /* -------------------------------------------------------------------------- */
242
243 /* Set `substitution' pointers in each page to representatives.
244 *
245 * Arguments:
246 * n - number of pages
247 * pages
248 * total_bitmaps_count - sum of all bitmap counts on each page
249 * tags - an array of tags (to index `representatives')
250 * representatives - [0..max_tag] array of bitmaps (tag 0 unused)
251 */
252
253 static void set_substitutions(int n,
254 mdjvu_image_t *pages,
255 int32 total_bitmaps_count,
256 int32 *tags,
257 mdjvu_bitmap_t *representatives)
258 {
259 int page_number;
260 int32 total_bitmaps_passed = 0;
261 for (page_number = 0; page_number < n; page_number++)
262 {
263 mdjvu_image_t page = pages[page_number];
264 int32 bitmap_count = mdjvu_image_get_bitmap_count(page);
265 int32 i; /* index of bitmap in a page */
266
267 if (!mdjvu_image_has_substitutions(page))
268 mdjvu_image_enable_substitutions(page);
269
270 for (i = 0; i < bitmap_count; i++)
271 {
272 int32 tag = tags[total_bitmaps_passed++];
273 if (!tag) continue; /* skip non-substitutable bitmaps */
274 mdjvu_image_set_substitution(page,
275 mdjvu_image_get_bitmap(page, i),
276 representatives[tag]);
277 }
278 }
279 }
280
281 /* -------------------------------------------------------------------------- */
282
283 static void report_classify(void *param, int page_completed)
284 {
285 mdjvu_compression_options_t r = (mdjvu_compression_options_t) param;
286 if (r->report)
287 {
288 printf(_("Classification: %d of %d completed\n"), r->report_start_page + page_completed,
289 r->report_total_pages);
290 }
291 }
292
293 static void report_prototypes(void *param, int page_completed)
294 {
295 mdjvu_compression_options_t r = (mdjvu_compression_options_t) param;
296 if (r->report)
297 {
298 printf(_("Prototype search: %d of %d completed\n"), r->report_start_page + page_completed,
299 r->report_total_pages);
300 }
301 }
302
303
304 MDJVU_FUNCTION mdjvu_image_t mdjvu_compress_multipage(int n, mdjvu_image_t *pages, mdjvu_compression_options_t options)
305 {
306 mdjvu_image_t dictionary = NULL;
307 int i;
308 int32 total_bitmaps_count, max_tag;
309 mdjvu_bitmap_t *representatives;
310 int32 *tags;
311 int32 *npatterns;
312 unsigned char *dictionary_flags;
313
314 total_bitmaps_count = 0;
315 for (i = 0; i < n; i++)
316 {
317 total_bitmaps_count += mdjvu_image_get_bitmap_count(pages[i]);
318
319 if (options->verbose) printf(_("deciding what pieces are letters in page #%d\n"), i);
320 mdjvu_calculate_not_a_letter_flags(pages[i]);
321
322 if (options->verbose) printf(_("sorting letters in page #%d\n"), i);
323 mdjvu_sort_blits(pages[i]);
324 mdjvu_image_sort_bitmaps(pages[i]);
325
326 if (!mdjvu_image_has_substitutions(pages[i]))
327 mdjvu_image_enable_substitutions(pages[i]);
328 }
329
330 tags = MDJVU_MALLOCV(int32, total_bitmaps_count);
331 if (options->report) printf(_("started classification\n"));
332 max_tag = mdjvu_multipage_classify_bitmaps
333 (n, total_bitmaps_count, pages, tags,
334 ((struct MinidjvuCompressionOptions *) options)->matcher_options,
335 report_classify, options, options->averaging);
336 if (options->report) printf(_("finished classification\n"));
337
338 dictionary_flags = (unsigned char *) malloc((max_tag + 1));
339 representatives = (mdjvu_bitmap_t *)
340 malloc((max_tag + 1) * sizeof(mdjvu_bitmap_t));
341
342 npatterns = MDJVU_MALLOCV(int32, n);
343 for (i = 0; i < n; i++)
344 {
345 npatterns[i] = mdjvu_image_get_bitmap_count(pages[i]);
346 }
347 mdjvu_multipage_get_dictionary_flags(n, npatterns,
348 max_tag, tags, dictionary_flags);
349 MDJVU_FREEV(npatterns);
350
351 if (!options->averaging)
352 {
353 mdjvu_multipage_choose_representatives(n, pages, max_tag, tags, representatives);
354 dictionary = get_dictionary(max_tag, representatives, dictionary_flags);
355
356 }
357 else
358 dictionary = mdjvu_multipage_choose_average_representatives(
359 n, pages, total_bitmaps_count, max_tag, tags, representatives, dictionary_flags);
360
361 for (i = 0; i < n; i++)
362 mdjvu_image_set_dictionary(pages[i], dictionary);
363
364 set_substitutions(n, pages, total_bitmaps_count, tags, representatives);
365
366 mdjvu_multipage_adjust(dictionary, n, pages);
367 for (i = 0; i < n; i++)
368 mdjvu_image_remove_unused_bitmaps(pages[i]);
369 if (options->report) printf(_("started prototype search\n"));
370 mdjvu_multipage_find_prototypes(dictionary, n, pages,
371 report_prototypes, options);
372 if (options->report) printf(_("finished prototype search\n"));
373 free(dictionary_flags);
374 free(representatives);
375 MDJVU_FREEV(tags);
376
377 return dictionary;
378 }