Debian Codegraph @

src/base/4bitmap.c

raw
1 /*
2 * 4bitmap.c - routines for handling packed bitmaps
3 */
4
5 #include "../base/mdjvucfg.h"
6 #include <minidjvu/minidjvu.h>
7 #include <stdlib.h>
8 #include <string.h>
9 #include <assert.h>
10
11 typedef struct
12 {
13 unsigned char **data;
14 int32 width, height;
15 int32 index;
16 } Bitmap;
17
18
19 #ifndef NDEBUG
20 int32 alive_bitmap_counter = 0;
21 #endif
22
23 #define BYTES_PER_ROW(WIDTH) (((WIDTH) + 7) >> 3)
24
25 /* __________________________ create/destroy ___________________________ */
26
27 MDJVU_IMPLEMENT mdjvu_bitmap_t mdjvu_bitmap_create(int32 width, int32 height)
28 {
29 Bitmap *b = (Bitmap *) malloc(sizeof(Bitmap));
30 mdjvu_init();
31 #ifndef NDEBUG
32 alive_bitmap_counter++;
33 #endif
34 b->width = width;
35 b->height = height;
36 b->index = -1;
37 b->data = mdjvu_create_2d_array(BYTES_PER_ROW(width), height);
38 return (mdjvu_bitmap_t) b;
39 }
40
41 MDJVU_IMPLEMENT void mdjvu_bitmap_destroy(mdjvu_bitmap_t bmp)
42 {
43 Bitmap *b = (Bitmap *) bmp;
44 #ifndef NDEBUG
45 alive_bitmap_counter--;
46 #endif
47 mdjvu_destroy_2d_array(b->data);
48 free(b);
49 }
50
51 /* __________________________ clone & assign ___________________________ */
52
53 #define BMP ((Bitmap *) b)
54 #define ROW_SIZE BYTES_PER_ROW(BMP->width)
55
56 MDJVU_IMPLEMENT mdjvu_bitmap_t mdjvu_bitmap_clone(mdjvu_bitmap_t b)
57 {
58 mdjvu_bitmap_t result = mdjvu_bitmap_create(BMP->width, BMP->height);
59
60 /* Using the fact that the 2d arrays by 2d_array() are really 1d ones */
61 memcpy(((Bitmap *) result)->data[0], BMP->data[0], ROW_SIZE * BMP->height);
62 return result;
63 }
64
65 MDJVU_IMPLEMENT void mdjvu_bitmap_assign(mdjvu_bitmap_t dst, mdjvu_bitmap_t b)
66 {
67 mdjvu_destroy_2d_array(((Bitmap *)dst)->data);
68 ((Bitmap *)dst)->data =
69 mdjvu_create_2d_array(BYTES_PER_ROW(BMP->width), BMP->height);
70 ((Bitmap *)dst)->width = BMP->width;
71 ((Bitmap *)dst)->height = BMP->height;
72 memcpy(((Bitmap *) dst)->data[0], BMP->data[0], ROW_SIZE * BMP->height);
73 }
74
75 MDJVU_IMPLEMENT void mdjvu_bitmap_exchange(mdjvu_bitmap_t d, mdjvu_bitmap_t src)
76 {
77 int32 d_index_backup = ((Bitmap *) d)->index;
78 int32 s_index_backup = ((Bitmap *) src)->index;
79 Bitmap tmp = * (Bitmap *) d;
80 * (Bitmap *) d = * (Bitmap *) src;
81 * (Bitmap *) src = tmp;
82 ((Bitmap *) d)->index = d_index_backup;
83 ((Bitmap *) src)->index = s_index_backup;
84 }
85
86
87 /* __________________________ getters/setters __________________________ */
88
89
90 MDJVU_IMPLEMENT int32 mdjvu_bitmap_get_width(mdjvu_bitmap_t b)
91 {
92 return BMP->width;
93 }
94
95 MDJVU_IMPLEMENT int32 mdjvu_bitmap_get_height(mdjvu_bitmap_t b)
96 {
97 return BMP->height;
98 }
99
100 MDJVU_IMPLEMENT int32 mdjvu_bitmap_get_index(mdjvu_bitmap_t b)
101 {
102 if (b)
103 return BMP->index;
104 else
105 return -1;
106 }
107
108 MDJVU_IMPLEMENT void mdjvu_bitmap_set_index(mdjvu_bitmap_t b, int32 v)
109 {
110 BMP->index = v;
111 }
112
113 MDJVU_IMPLEMENT int32 mdjvu_bitmap_get_packed_row_size(mdjvu_bitmap_t b)
114 {
115 return ROW_SIZE;
116 }
117
118 MDJVU_IMPLEMENT unsigned char *
119 mdjvu_bitmap_access_packed_row(mdjvu_bitmap_t b, int32 i)
120 {
121 return BMP->data[i];
122 }
123
124 MDJVU_IMPLEMENT void mdjvu_bitmap_clear(mdjvu_bitmap_t b)
125 {
126 memset(BMP->data[0], 0, BMP->height * ROW_SIZE);
127 }
128
129 /* __________________________ packing/unpacking ________________________ */
130
131 /* All the functions in this part are, well, suboptimized. */
132
133 MDJVU_IMPLEMENT void mdjvu_bitmap_pack_row
134 (mdjvu_bitmap_t b, unsigned char *bytes, int32 y)
135 {
136 unsigned char *bits = BMP->data[y];
137 int coef = 0x80;
138 int a = 0; /* accumulates bits */
139 int32 i = BMP->width;
140 while (i--)
141 {
142 if (*bytes++) a |= coef;
143
144 coef >>= 1;
145 if (!coef)
146 {
147 coef = 0x80;
148 *bits++ = a;
149 a = 0;
150 }
151 }
152
153 if (BMP->width & 7) *bits = a;
154 }
155
156 MDJVU_IMPLEMENT void mdjvu_bitmap_unpack_row
157 (mdjvu_bitmap_t b, unsigned char *bytes, int32 y)
158 {
159 unsigned char *bits = BMP->data[y];
160 int coef = 0x80;
161 int a = *bits;
162 int32 i = BMP->width;
163 while (i--)
164 {
165 *bytes++ = a & coef;
166
167 coef >>= 1;
168 if (!coef)
169 {
170 coef = 0x80;
171 if (!i) break; /* FIXME: this is not necessary, only to valgrind */
172 a = *++bits;
173 }
174 }
175 }
176
177 /* FIXME: this is almost a copy of the previous function */
178 MDJVU_IMPLEMENT void mdjvu_bitmap_unpack_row_0_or_1
179 (mdjvu_bitmap_t b, unsigned char *bytes, int32 y)
180 {
181 unsigned char *bits = BMP->data[y];
182 int coef = 0x80;
183 int a = *bits;
184 int32 i = BMP->width;
185 while (i--)
186 {
187 *bytes++ = a & coef ? 1 : 0;
188
189 coef >>= 1;
190 if (!coef)
191 {
192 coef = 0x80;
193 if (!i) break; /* FIXME: this is not necessary, only to valgrind */
194 a = *++bits;
195 }
196 }
197 }
198
199 MDJVU_IMPLEMENT void mdjvu_bitmap_pack_all
200 (mdjvu_bitmap_t b, unsigned char **data)
201 {
202 int32 i = 0, h = BMP->height;
203 for (i = 0; i < h; i++)
204 {
205 mdjvu_bitmap_pack_row(b, data[i], i);
206 }
207 }
208
209 MDJVU_IMPLEMENT void mdjvu_bitmap_unpack_all
210 (mdjvu_bitmap_t b, unsigned char **data)
211 {
212 int32 i = 0, h = BMP->height;
213 for (i = 0; i < h; i++)
214 {
215 mdjvu_bitmap_unpack_row(b, data[i], i);
216 }
217 }
218
219 MDJVU_IMPLEMENT void mdjvu_bitmap_unpack_all_0_or_1
220 (mdjvu_bitmap_t b, unsigned char **data)
221 {
222 int32 i = 0, h = BMP->height;
223 for (i = 0; i < h; i++)
224 {
225 mdjvu_bitmap_unpack_row_0_or_1(b, data[i], i);
226 }
227 }
228
229 /* _______________________________ crop ________________________________ */
230
231 MDJVU_IMPLEMENT mdjvu_bitmap_t mdjvu_bitmap_crop
232 (mdjvu_bitmap_t b, int32 left, int32 top, int32 w, int32 h)
233 {
234 if (left == 0 && top == 0 && w == BMP->width && h == BMP->height)
235 {
236 return mdjvu_bitmap_clone(b);
237 }
238 else
239 {
240 mdjvu_bitmap_t result;
241 int32 i = top, count = h;
242 unsigned char *buf;
243
244 assert(left >= 0);
245 assert(left + w <= BMP->width);
246 assert(top >= 0);
247 assert(top + h <= BMP->height);
248
249 result = mdjvu_bitmap_create(w, h);
250 buf = (unsigned char *) malloc(BMP->width);
251 while (count--)
252 {
253 mdjvu_bitmap_unpack_row(b, buf, i);
254 mdjvu_bitmap_pack_row(result, buf + left, i - top);
255 i++;
256 }
257 free(buf);
258 return result;
259 }
260 }
261
262 /* _______________________________ bbox ________________________________ */
263
264 static int row_is_empty(Bitmap *bmp, int32 y)
265 {
266 unsigned char *row = bmp->data[y];
267 int32 bytes_to_check = BYTES_PER_ROW(bmp->width) - 1;
268 int32 bits_to_check = bmp->width - (bytes_to_check << 3);
269 int32 mask = 0xFF << (8 - bits_to_check);
270 int32 i;
271
272 for (i = 0; i < bytes_to_check; i++)
273 if (row[i]) return 0;
274
275 if (row[bytes_to_check] & mask) return 0;
276 return 1;
277 }
278
279 static int column_is_empty(Bitmap *bmp, int32 x)
280 {
281 int32 byte_offset = x >> 3;
282 int mask = 1 << (7 - (x & 7));
283 int32 bytes_per_row = BYTES_PER_ROW(bmp->width);
284 unsigned char *p = bmp->data[0] + byte_offset;
285 int32 i = bmp->height;
286
287 while(i--)
288 {
289 if (*p & mask) return 0;
290 p += bytes_per_row;
291 }
292
293 return 1;
294 }
295
296 MDJVU_IMPLEMENT void mdjvu_bitmap_get_bounding_box(mdjvu_bitmap_t b,
297 int32 *pl, int32 *pt, int32 *pw, int32 *ph)
298 {
299 int32 right = BMP->width - 1;
300 int32 left = 0;
301 int32 bottom = BMP->height - 1;
302 int32 top = 0;
303
304 while (column_is_empty(BMP, right) && right) right--;
305 while (column_is_empty(BMP, left) && left < right) left++;
306
307 *pl = left;
308 *pw = right - left + 1;
309
310 while (row_is_empty(BMP, bottom) && bottom) bottom--;
311 while (row_is_empty(BMP, top) && top < bottom) top++;
312
313 *pt = top;
314 *ph = bottom - top + 1;
315 }
316
317 MDJVU_IMPLEMENT void mdjvu_bitmap_remove_margins
318 (mdjvu_bitmap_t b, int32 *px, int32 *py)
319 {
320 int32 w, h;
321 mdjvu_bitmap_t cropped;
322 mdjvu_bitmap_get_bounding_box(b, px, py, &w, &h);
323 if (!*px && !*py && w == BMP->width && h == BMP->height)
324 return;
325 cropped = mdjvu_bitmap_crop(b, *px, *py, w, h);
326 mdjvu_bitmap_exchange(b, cropped);
327 mdjvu_bitmap_destroy(cropped);
328 }
329
330 /* _______________________________ misc ________________________________ */
331
332 /* This is a sub-optimal way to count mass.
333 * Run "fortune -m BITCOUNT" to see a better way...
334 */
335 MDJVU_IMPLEMENT int32 mdjvu_bitmap_get_mass(mdjvu_bitmap_t b)
336 {
337 int32 m = 0;
338 int32 w = BMP->width;
339 int32 h = BMP->height;
340 unsigned char *buf = (unsigned char *) malloc(w);
341 int32 y;
342 for (y = 0; y < h; y++)
343 {
344 int x;
345 mdjvu_bitmap_unpack_row_0_or_1(b, buf, y);
346 for (x = 0; x < w; x++)
347 m += buf[x];
348 }
349 free(buf);
350 return m;
351 }
352