Debian Codegraph @

src/jb2/proto.c

raw
1 /*
2 * proto.c - searching for prototypes
3 */
4
5 #include "../base/mdjvucfg.h"
6 #include <minidjvu/minidjvu.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 #define THRESHOLD 21
11
12 static const int32 bigint = INT32_MAX / 100 - 1;
13
14 /* THIS THING IS THE PRIMARY BOTTLENECK FOR LOSSLESS COMPRESSION
15 * TODO: OPTIMIZE IT!
16 * ceiling is an optimization - if we have more, quit
17 */
18 static int diff(mdjvu_bitmap_t image,
19 mdjvu_bitmap_t prototype,
20 unsigned char **image_uncompressed,
21 unsigned char **proto_uncompressed,
22 int32 ceiling)
23 {
24 int32 pw = mdjvu_bitmap_get_width (prototype);
25 int32 ph = mdjvu_bitmap_get_height(prototype);
26 int32 iw = mdjvu_bitmap_get_width (image);
27 int32 ih = mdjvu_bitmap_get_height(image);
28 int32 shift_x, shift_y;
29 int32 s = 0, i, n = pw + 2;
30 unsigned char *ir;
31 unsigned char *pr;
32
33 if (abs(iw - pw) > 2) return INT32_MAX;
34 if (abs(ih - ph) > 2) return INT32_MAX;
35
36 ir = (unsigned char *) malloc(n);
37 pr = (unsigned char *) malloc(n);
38
39 /* (shift_x, shift_y) is a shift of image with respect to prototype */
40 shift_x = (pw - pw/2) - (iw - iw/2); /* center favors right */
41 shift_y = ph/2 - ih/2; /* center favors top */
42
43 memset(pr, 0, n);
44 memset(ir, 0, n);
45
46 for (i = -1; i <= ph; i++)
47 {
48 int32 y = i - shift_y;
49
50 if (y >= 0 && y < ih)
51 memcpy(ir + shift_x + 1, image_uncompressed[y], iw);
52 else
53 memset(ir, 0, n); /* SUB-OPTIMAL? */
54
55 if (i >= 0 && i < ph)
56 memcpy(pr + 1, proto_uncompressed[i], pw);
57 else
58 memset(pr, 0, n);
59
60 /* reusing y */
61 for (y = 0; y < n; y++) if (ir[y] != pr[y]) s++;
62 if (s > ceiling)
63 {
64 free(ir);
65 free(pr);
66 return s;
67 }
68 }
69
70 free(ir);
71 free(pr);
72
73 return s;
74 }
75
76 static void find_prototypes
77 (mdjvu_image_t dict, unsigned char ***uncompressed_dict, mdjvu_image_t img)
78 {
79 int32 d = dict ? mdjvu_image_get_bitmap_count(dict) : 0;
80 int32 i, n = mdjvu_image_get_bitmap_count(img);
81 unsigned char ***uncompressed_bitmaps = (unsigned char ***)
82 malloc(n * sizeof(unsigned char **));
83
84 for (i = 0; i < n; i++)
85 {
86 mdjvu_bitmap_t current = mdjvu_image_get_bitmap(img, i);
87 int32 w = mdjvu_bitmap_get_width(current);
88 int32 h = mdjvu_bitmap_get_height(current);
89 uncompressed_bitmaps[i] = mdjvu_create_2d_array(w, h);
90 mdjvu_bitmap_unpack_all_0_or_1(current, uncompressed_bitmaps[i]);
91 }
92
93 if (!mdjvu_image_has_prototypes(img))
94 mdjvu_image_enable_prototypes(img);
95 if (!mdjvu_image_has_substitutions(img))
96 mdjvu_image_enable_substitutions(img);
97 if (!mdjvu_image_has_masses(img))
98 mdjvu_image_enable_masses(img); /* calculates them, not just enables */
99 for (i = 0; i < n; i++)
100 {
101 mdjvu_bitmap_t current = mdjvu_image_get_bitmap(img, i);
102 int32 mass = mdjvu_image_get_mass(img, current);
103 int32 w = mdjvu_bitmap_get_width(current);
104 int32 h = mdjvu_bitmap_get_height(current);
105 int32 max_score = w * h * THRESHOLD / 100;
106 int32 j;
107 mdjvu_bitmap_t best_match = NULL;
108 int32 best_score = max_score;
109
110 for (j = 0; j < d; j++)
111 {
112 int32 score;
113 mdjvu_bitmap_t candidate = mdjvu_image_get_bitmap(dict, j);
114 int32 c_mass = mdjvu_image_get_mass(dict, candidate);
115 if (abs(mass - c_mass) > best_score) continue;
116 score = diff(current,
117 candidate,
118 uncompressed_bitmaps[i],
119 uncompressed_dict[j],
120 best_score);
121 if (score < best_score)
122 {
123 best_score = score;
124 best_match = candidate;
125 if (!score)
126 break; /* a perfect match is found */
127 }
128 }
129
130 if (best_score) for (j = 0; j < i; j++)
131 {
132 int32 score;
133 mdjvu_bitmap_t candidate = mdjvu_image_get_bitmap(img, j);
134 int32 c_mass = mdjvu_image_get_mass(img, candidate);
135 if (abs(mass - c_mass) > best_score) continue;
136 score = diff(current,
137 candidate,
138 uncompressed_bitmaps[i],
139 uncompressed_bitmaps[j],
140 best_score);
141 if (score < best_score)
142 {
143 best_score = score;
144 best_match = candidate;
145 if (!score)
146 break; /* a perfect match is found */
147 }
148 }
149
150 if (best_score)
151 mdjvu_image_set_prototype(img, current, best_match);
152 else
153 mdjvu_image_set_substitution(img, current, best_match);
154 }
155
156 /* destroy uncompressed bitmaps */
157 for (i = 0; i < n; i++)
158 {
159 mdjvu_destroy_2d_array(uncompressed_bitmaps[i]);
160 }
161 free(uncompressed_bitmaps);
162 }
163
164 MDJVU_IMPLEMENT void mdjvu_find_prototypes(mdjvu_image_t img)
165 {
166 find_prototypes(NULL, NULL, img);
167 }
168
169 MDJVU_IMPLEMENT void mdjvu_multipage_find_prototypes(mdjvu_image_t dict,
170 int32 npages,
171 mdjvu_image_t *pages,
172 void (*report)(void *, int ),
173 void *param)
174 {
175 int i;
176 int32 n = mdjvu_image_get_bitmap_count(dict);
177 unsigned char ***uncompressed_dict_bitmaps = (unsigned char ***)
178 malloc(n * sizeof(unsigned char **));
179
180 for (i = 0; i < n; i++)
181 {
182 mdjvu_bitmap_t current = mdjvu_image_get_bitmap(dict, i);
183 int32 w = mdjvu_bitmap_get_width(current);
184 int32 h = mdjvu_bitmap_get_height(current);
185 uncompressed_dict_bitmaps[i] = mdjvu_create_2d_array(w, h);
186 mdjvu_bitmap_unpack_all_0_or_1(current, uncompressed_dict_bitmaps[i]);
187 }
188
189 if (!mdjvu_image_has_masses(dict))
190 mdjvu_image_enable_masses(dict); /* calculates them, not just enables */
191
192 for (i = 0; i < npages; i++)
193 {
194 find_prototypes(dict, uncompressed_dict_bitmaps, pages[i]);
195 report(param, i);
196 }
197
198 /* destroy uncompressed bitmaps */
199 for (i = 0; i < n; i++)
200 {
201 mdjvu_destroy_2d_array(uncompressed_dict_bitmaps[i]);
202 }
203 free(uncompressed_dict_bitmaps);
204 }