| 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 |
|