Evince
Evince is a document viewer capable of displaying multiple and single page document formats like PDF and Postscript.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
bitmap.c
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2000, Matias Atria
3  *
4  * This program is free software; you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation; either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  */
18 
19 /* Bitmap manipulation routines */
20 
21 #include <config.h>
22 #include <stdlib.h>
23 
24 #include "mdvi.h"
25 #include "color.h"
26 
27 /* bit_masks[n] contains a BmUnit with `n' contiguous bits */
28 
29 static BmUnit bit_masks[] = {
30  0x0, 0x1, 0x3, 0x7,
31  0xf, 0x1f, 0x3f, 0x7f,
32  0xff,
33 #if BITMAP_BYTES > 1
34  0x1ff, 0x3ff, 0x7ff,
35  0xfff, 0x1fff, 0x3fff, 0x7fff,
36  0xffff,
37 #if BITMAP_BYTES > 2
38  0x1ffff, 0x3ffff, 0x7ffff,
39  0xfffff, 0x1fffff, 0x3fffff, 0x7fffff,
40  0xffffff, 0x1ffffff, 0x3ffffff, 0x7ffffff,
41  0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff,
42  0xffffffff
43 #endif /* BITMAP_BYTES > 2 */
44 #endif /* BITMAP_BYTES > 1 */
45 };
46 
47 #ifndef NODEBUG
48 #define SHOW_OP_DATA (DEBUGGING(BITMAP_OPS) && DEBUGGING(BITMAP_DATA))
49 #endif
50 
51 /*
52  * Some useful macros to manipulate bitmap data
53  * SEGMENT(m,n) = bit mask for a segment of `m' contiguous bits
54  * starting at column `n'. These macros assume that
55  * m + n <= BITMAP_BITS, 0 <= m, n.
56  */
57 #ifdef WORD_BIG_ENDIAN
58 #define SEGMENT(m,n) (bit_masks[m] << (BITMAP_BITS - (m) - (n)))
59 #else
60 #define SEGMENT(m,n) (bit_masks[m] << (n))
61 #endif
62 
63 /* sampling and shrinking routines shamelessly stolen from xdvi */
64 
65 static int sample_count[] = {
66  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
67  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
68  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
69  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
70  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
71  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
72  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
73  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
74  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
75  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
76  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
77  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
78  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
79  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
80  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
81  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
82 };
83 
84 /* bit_swap[j] = j with all bits inverted (i.e. msb -> lsb) */
85 static Uchar bit_swap[] = {
86  0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
87  0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
88  0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
89  0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
90  0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
91  0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
92  0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
93  0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
94  0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
95  0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
96  0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
97  0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
98  0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
99  0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
100  0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
101  0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
102  0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
103  0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
104  0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
105  0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
106  0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
107  0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
108  0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
109  0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
110  0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
111  0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
112  0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
113  0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
114  0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
115  0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
116  0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
117  0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
118 };
119 
120 
121 /*
122  * next we have three bitmap functions to convert bitmaps in LSB bit order
123  * with 8, 16 and 32 bits per unit, to our internal format. The differences
124  * are minimal, but writing a generic function to handle all unit sizes is
125  * hopelessly slow.
126  */
127 
128 BITMAP *bitmap_convert_lsb8(Uchar *bits, int w, int h, int stride)
129 {
130  BITMAP *bm;
131  int i;
132  Uchar *unit;
133  register Uchar *curr;
134  int bytes;
135 
136  DEBUG((DBG_BITMAP_OPS, "convert LSB %dx%d@8 -> bitmap\n", w, h));
137 
138  bm = bitmap_alloc_raw(w, h);
139 
140  /* this is the number of bytes in the original bitmap */
141  bytes = ROUND(w, 8);
142  unit = (Uchar *)bm->data;
143  curr = bits;
144  /* we try to do this as fast as we can */
145  for(i = 0; i < h; i++) {
146 #ifdef WORD_LITTLE_ENDIAN
147  memcpy(unit, curr, bytes);
148  curr += stride;
149 #else
150  int j;
151 
152  for(j = 0; j < bytes; curr++, j++)
153  unit[j] = bit_swap[*curr];
154  cur += stride - bytes;
155 #endif
156  memzero(unit + bytes, bm->stride - bytes);
157  unit += bm->stride;
158  }
159  if(SHOW_OP_DATA)
160  bitmap_print(stderr, bm);
161  return bm;
162 }
163 
164 BITMAP *bitmap_convert_msb8(Uchar *data, int w, int h, int stride)
165 {
166  BITMAP *bm;
167  Uchar *unit;
168  Uchar *curr;
169  int i;
170  int bytes;
171 
172  bm = bitmap_alloc(w, h);
173  bytes = ROUND(w, 8);
174  unit = (Uchar *)bm->data;
175  curr = data;
176  for(i = 0; i < h; i++) {
177 #ifdef WORD_LITTLE_ENDIAN
178  int j;
179 
180  for(j = 0; j < bytes; curr++, j++)
181  unit[j] = bit_swap[*curr];
182  curr += stride - bytes;
183 #else
184  memcpy(unit, curr, bytes);
185  curr += stride;
186 #endif
187  memzero(unit + bytes, bm->stride - bytes);
188  unit += bm->stride;
189  }
190  if(SHOW_OP_DATA)
191  bitmap_print(stderr, bm);
192  return bm;
193 }
194 
195 
196 BITMAP *bitmap_copy(BITMAP *bm)
197 {
198  BITMAP *nb = bitmap_alloc(bm->width, bm->height);
199 
200  DEBUG((DBG_BITMAP_OPS, "copy %dx%d\n", bm->width, bm->height));
201  memcpy(nb->data, bm->data, bm->height * bm->stride);
202  return nb;
203 }
204 
205 BITMAP *bitmap_alloc(int w, int h)
206 {
207  BITMAP *bm;
208 
209  bm = xalloc(BITMAP);
210  bm->width = w;
211  bm->height = h;
212  bm->stride = BM_BYTES_PER_LINE(bm);
213  if(h && bm->stride)
214  bm->data = (BmUnit *)mdvi_calloc(h, bm->stride);
215  else
216  bm->data = NULL;
217 
218  return bm;
219 }
220 
221 BITMAP *bitmap_alloc_raw(int w, int h)
222 {
223  BITMAP *bm;
224 
225  bm = xalloc(BITMAP);
226  bm->width = w;
227  bm->height = h;
228  bm->stride = BM_BYTES_PER_LINE(bm);
229  if(h && bm->stride)
230  bm->data = (BmUnit *)mdvi_malloc(h * bm->stride);
231  else
232  bm->data = NULL;
233 
234  return bm;
235 }
236 
237 void bitmap_destroy(BITMAP *bm)
238 {
239  if(bm->data)
240  free(bm->data);
241  free(bm);
242 }
243 
244 void bitmap_print(FILE *out, BITMAP *bm)
245 {
246  int i, j;
247  BmUnit *a, mask;
248  static const char labels[] = {
249  '1', '2', '3', '4', '5', '6', '7', '8', '9', '0'
250  };
251  int sub;
252 
253  a = bm->data;
254  fprintf(out, " ");
255  if(bm->width > 10) {
256  putchar('0');
257  sub = 0;
258  for(j = 2; j <= bm->width; j++)
259  if((j %10) == 0) {
260  if((j % 100) == 0) {
261  fprintf(out, "*");
262  sub += 100;
263  } else
264  fprintf(out, "%d", (j - sub)/10);
265  } else
266  putc(' ', out);
267  fprintf(out, "\n ");
268  }
269  for(j = 0; j < bm->width; j++)
270  putc(labels[j % 10], out);
271  putchar('\n');
272  for(i = 0; i < bm->height; i++) {
273  mask = FIRSTMASK;
274  a = (BmUnit *)((char *)bm->data + i * bm->stride);
275  fprintf(out, "%3d ", i+1);
276  for(j = 0; j < bm->width; j++) {
277  if(*a & mask)
278  putc('#', out);
279  else
280  putc('.', out);
281  if(mask == LASTMASK) {
282  a++;
283  mask = FIRSTMASK;
284  } else
285  NEXTMASK(mask);
286  }
287  putchar('\n');
288  }
289 }
290 
291 void bitmap_set_col(BITMAP *bm, int row, int col, int count, int state)
292 {
293  BmUnit *ptr;
294  BmUnit mask;
295 
296  ptr = __bm_unit_ptr(bm, col, row);
297  mask = FIRSTMASKAT(col);
298 
299  while(count-- > 0) {
300  if(state)
301  *ptr |= mask;
302  else
303  *ptr &= ~mask;
304  /* move to next row */
305  ptr = bm_offset(ptr, bm->stride);
306  }
307 }
308 
309 /*
310  * to use this function you should first make sure that
311  * there is room for `count' bits in the scanline
312  *
313  * A general-purpose (but not very efficient) function to paint `n' pixels
314  * on a bitmap, starting at position (x, y) would be:
315  *
316  * bitmap_paint_bits(__bm_unit_ptr(bitmap, x, y), x % BITMAP_BITS, n)
317  *
318  */
319 void bitmap_paint_bits(BmUnit *ptr, int n, int count)
320 {
321  /* paint the head */
322  if(n + count > BITMAP_BITS) {
323  *ptr |= SEGMENT(BITMAP_BITS - n, n);
324  count -= BITMAP_BITS - n;
325  ptr++;
326  } else {
327  *ptr |= SEGMENT(count, n);
328  return;
329  }
330 
331  /* paint the middle */
332  for(; count >= BITMAP_BITS; count -= BITMAP_BITS)
333  *ptr++ = bit_masks[BITMAP_BITS];
334 
335  /* paint the tail */
336  if(count > 0)
337  *ptr |= SEGMENT(count, 0);
338 }
339 
340 /*
341  * same as paint_bits but clears pixels instead of painting them. Written
342  * as a separate function for efficiency reasons.
343  */
344 void bitmap_clear_bits(BmUnit *ptr, int n, int count)
345 {
346  if(n + count > BITMAP_BITS) {
347  *ptr &= ~SEGMENT(BITMAP_BITS - n, n);
348  count -= BITMAP_BITS;
349  ptr++;
350  } else {
351  *ptr &= ~SEGMENT(count, n);
352  return;
353  }
354 
355  for(; count >= BITMAP_BITS; count -= BITMAP_BITS)
356  *ptr++ = 0;
357 
358  if(count > 0)
359  *ptr &= ~SEGMENT(count, 0);
360 }
361 
362 /* the general function to paint rows. Still used by the PK reader, but that
363  * will change soon (The GF reader already uses bitmap_paint_bits()).
364  */
365 void bitmap_set_row(BITMAP *bm, int row, int col, int count, int state)
366 {
367  BmUnit *ptr;
368 
369  ptr = __bm_unit_ptr(bm, col, row);
370  if(state)
371  bitmap_paint_bits(ptr, col & (BITMAP_BITS-1), count);
372  else
373  bitmap_clear_bits(ptr, col & (BITMAP_BITS-1), count);
374 }
375 
376 /*
377  * Now several `flipping' operations
378  */
379 
380 void bitmap_flip_horizontally(BITMAP *bm)
381 {
382  BITMAP nb;
383  BmUnit *fptr, *tptr;
384  BmUnit fmask, tmask;
385  int w, h;
386 
387  nb.width = bm->width;
388  nb.height = bm->height;
389  nb.stride = bm->stride;
390  nb.data = mdvi_calloc(bm->height, bm->stride);
391 
392  fptr = bm->data;
393  tptr = __bm_unit_ptr(&nb, nb.width-1, 0);
394  for(h = 0; h < bm->height; h++) {
395  BmUnit *fline, *tline;
396 
397  fline = fptr;
398  tline = tptr;
399  fmask = FIRSTMASK;
400  tmask = FIRSTMASKAT(nb.width-1);
401  for(w = 0; w < bm->width; w++) {
402  if(*fline & fmask)
403  *tline |= tmask;
404  if(fmask == LASTMASK) {
405  fmask = FIRSTMASK;
406  fline++;
407  } else
408  NEXTMASK(fmask);
409  if(tmask == FIRSTMASK) {
410  tmask = LASTMASK;
411  tline--;
412  } else
413  PREVMASK(tmask);
414  }
415  fptr = bm_offset(fptr, bm->stride);
416  tptr = bm_offset(tptr, bm->stride);
417  }
418  DEBUG((DBG_BITMAP_OPS, "flip_horizontally (%d,%d) -> (%d,%d)\n",
419  bm->width, bm->height, nb.width, nb.height));
420  mdvi_free(bm->data);
421  bm->data = nb.data;
422  if(SHOW_OP_DATA)
423  bitmap_print(stderr, bm);
424 }
425 
426 void bitmap_flip_vertically(BITMAP *bm)
427 {
428  BITMAP nb;
429  BmUnit *fptr, *tptr;
430  BmUnit fmask;
431  int w, h;
432 
433  nb.width = bm->width;
434  nb.height = bm->height;
435  nb.stride = bm->stride;
436  nb.data = mdvi_calloc(bm->height, bm->stride);
437 
438  fptr = bm->data;
439  tptr = __bm_unit_ptr(&nb, 0, nb.height-1);
440  for(h = 0; h < bm->height; h++) {
441  BmUnit *fline, *tline;
442 
443  fline = fptr;
444  tline = tptr;
445  fmask = FIRSTMASK;
446  for(w = 0; w < bm->width; w++) {
447  if(*fline & fmask)
448  *tline |= fmask;
449  if(fmask == LASTMASK) {
450  fmask = FIRSTMASK;
451  fline++;
452  tline++;
453  } else
454  NEXTMASK(fmask);
455  }
456  fptr = bm_offset(fptr, bm->stride);
457  tptr = (BmUnit *)((char *)tptr - bm->stride);
458  }
459  DEBUG((DBG_BITMAP_OPS, "flip_vertically (%d,%d) -> (%d,%d)\n",
460  bm->width, bm->height, nb.width, nb.height));
461  mdvi_free(bm->data);
462  bm->data = nb.data;
463  if(SHOW_OP_DATA)
464  bitmap_print(stderr, bm);
465 }
466 
467 void bitmap_flip_diagonally(BITMAP *bm)
468 {
469  BITMAP nb;
470  BmUnit *fptr, *tptr;
471  BmUnit fmask, tmask;
472  int w, h;
473 
474  nb.width = bm->width;
475  nb.height = bm->height;
476  nb.stride = bm->stride;
477  nb.data = mdvi_calloc(bm->height, bm->stride);
478 
479  fptr = bm->data;
480  tptr = __bm_unit_ptr(&nb, nb.width-1, nb.height-1);
481  for(h = 0; h < bm->height; h++) {
482  BmUnit *fline, *tline;
483 
484  fline = fptr;
485  tline = tptr;
486  fmask = FIRSTMASK;
487  tmask = FIRSTMASKAT(nb.width-1);
488  for(w = 0; w < bm->width; w++) {
489  if(*fline & fmask)
490  *tline |= tmask;
491  if(fmask == LASTMASK) {
492  fmask = FIRSTMASK;
493  fline++;
494  } else
495  NEXTMASK(fmask);
496  if(tmask == FIRSTMASK) {
497  tmask = LASTMASK;
498  tline--;
499  } else
500  PREVMASK(tmask);
501  }
502  fptr = bm_offset(fptr, bm->stride);
503  tptr = bm_offset(tptr, -nb.stride);
504  }
505  DEBUG((DBG_BITMAP_OPS, "flip_diagonally (%d,%d) -> (%d,%d)\n",
506  bm->width, bm->height, nb.width, nb.height));
507  mdvi_free(bm->data);
508  bm->data = nb.data;
509  if(SHOW_OP_DATA)
510  bitmap_print(stderr, bm);
511 }
512 
513 void bitmap_rotate_clockwise(BITMAP *bm)
514 {
515  BITMAP nb;
516  BmUnit *fptr, *tptr;
517  BmUnit fmask, tmask;
518  int w, h;
519 
520  nb.width = bm->height;
521  nb.height = bm->width;
522  nb.stride = BM_BYTES_PER_LINE(&nb);
523  nb.data = mdvi_calloc(nb.height, nb.stride);
524 
525  fptr = bm->data;
526  tptr = __bm_unit_ptr(&nb, nb.width - 1, 0);
527 
528  tmask = FIRSTMASKAT(nb.width-1);
529  for(h = 0; h < bm->height; h++) {
530  BmUnit *fline, *tline;
531 
532  fmask = FIRSTMASK;
533  fline = fptr;
534  tline = tptr;
535  for(w = 0; w < bm->width; w++) {
536  if(*fline & fmask)
537  *tline |= tmask;
538  if(fmask == LASTMASK) {
539  fmask = FIRSTMASK;
540  fline++;
541  } else
542  NEXTMASK(fmask);
543  /* go to next row */
544  tline = bm_offset(tline, nb.stride);
545  }
546  fptr = bm_offset(fptr, bm->stride);
547  if(tmask == FIRSTMASK) {
548  tmask = LASTMASK;
549  tptr--;
550  } else
551  PREVMASK(tmask);
552  }
553 
554  DEBUG((DBG_BITMAP_OPS, "rotate_clockwise (%d,%d) -> (%d,%d)\n",
555  bm->width, bm->height, nb.width, nb.height));
556  mdvi_free(bm->data);
557  bm->data = nb.data;
558  bm->width = nb.width;
559  bm->height = nb.height;
560  bm->stride = nb.stride;
561  if(SHOW_OP_DATA)
562  bitmap_print(stderr, bm);
563 }
564 
565 void bitmap_rotate_counter_clockwise(BITMAP *bm)
566 {
567  BITMAP nb;
568  BmUnit *fptr, *tptr;
569  BmUnit fmask, tmask;
570  int w, h;
571 
572  nb.width = bm->height;
573  nb.height = bm->width;
574  nb.stride = BM_BYTES_PER_LINE(&nb);
575  nb.data = mdvi_calloc(nb.height, nb.stride);
576 
577  fptr = bm->data;
578  tptr = __bm_unit_ptr(&nb, 0, nb.height - 1);
579 
580  tmask = FIRSTMASK;
581  for(h = 0; h < bm->height; h++) {
582  BmUnit *fline, *tline;
583 
584  fmask = FIRSTMASK;
585  fline = fptr;
586  tline = tptr;
587  for(w = 0; w < bm->width; w++) {
588  if(*fline & fmask)
589  *tline |= tmask;
590  if(fmask == LASTMASK) {
591  fmask = FIRSTMASK;
592  fline++;
593  } else
594  NEXTMASK(fmask);
595  /* go to previous row */
596  tline = bm_offset(tline, -nb.stride);
597  }
598  fptr = bm_offset(fptr, bm->stride);
599  if(tmask == LASTMASK) {
600  tmask = FIRSTMASK;
601  tptr++;
602  } else
603  NEXTMASK(tmask);
604  }
605 
606  DEBUG((DBG_BITMAP_OPS, "rotate_counter_clockwise (%d,%d) -> (%d,%d)\n",
607  bm->width, bm->height, nb.width, nb.height));
608  mdvi_free(bm->data);
609  bm->data = nb.data;
610  bm->width = nb.width;
611  bm->height = nb.height;
612  bm->stride = nb.stride;
613  if(SHOW_OP_DATA)
614  bitmap_print(stderr, bm);
615 }
616 
617 void bitmap_flip_rotate_clockwise(BITMAP *bm)
618 {
619  BITMAP nb;
620  BmUnit *fptr, *tptr;
621  BmUnit fmask, tmask;
622  int w, h;
623 
624  nb.width = bm->height;
625  nb.height = bm->width;
626  nb.stride = BM_BYTES_PER_LINE(&nb);
627  nb.data = mdvi_calloc(nb.height, nb.stride);
628 
629  fptr = bm->data;
630  tptr = __bm_unit_ptr(&nb, nb.width-1, nb.height-1);
631 
632  tmask = FIRSTMASKAT(nb.width-1);
633  for(h = 0; h < bm->height; h++) {
634  BmUnit *fline, *tline;
635 
636  fmask = FIRSTMASK;
637  fline = fptr;
638  tline = tptr;
639  for(w = 0; w < bm->width; w++) {
640  if(*fline & fmask)
641  *tline |= tmask;
642  if(fmask == LASTMASK) {
643  fmask = FIRSTMASK;
644  fline++;
645  } else
646  NEXTMASK(fmask);
647  /* go to previous line */
648  tline = bm_offset(tline, -nb.stride);
649  }
650  fptr = bm_offset(fptr, bm->stride);
651  if(tmask == FIRSTMASK) {
652  tmask = LASTMASK;
653  tptr--;
654  } else
655  PREVMASK(tmask);
656  }
657  DEBUG((DBG_BITMAP_OPS, "flip_rotate_clockwise (%d,%d) -> (%d,%d)\n",
658  bm->width, bm->height, nb.width, nb.height));
659  mdvi_free(bm->data);
660  bm->data = nb.data;
661  bm->width = nb.width;
662  bm->height = nb.height;
663  bm->stride = nb.stride;
664  if(SHOW_OP_DATA)
665  bitmap_print(stderr, bm);
666 }
667 
668 void bitmap_flip_rotate_counter_clockwise(BITMAP *bm)
669 {
670  BITMAP nb;
671  BmUnit *fptr, *tptr;
672  BmUnit fmask, tmask;
673  int w, h;
674 
675  nb.width = bm->height;
676  nb.height = bm->width;
677  nb.stride = BM_BYTES_PER_LINE(&nb);
678  nb.data = mdvi_calloc(nb.height, nb.stride);
679 
680  fptr = bm->data;
681  tptr = nb.data;
682  tmask = FIRSTMASK;
683 
684  for(h = 0; h < bm->height; h++) {
685  BmUnit *fline, *tline;
686 
687  fmask = FIRSTMASK;
688  fline = fptr;
689  tline = tptr;
690  for(w = 0; w < bm->width; w++) {
691  if(*fline & fmask)
692  *tline |= tmask;
693  if(fmask == LASTMASK) {
694  fmask = FIRSTMASK;
695  fline++;
696  } else
697  NEXTMASK(fmask);
698  /* go to next line */
699  tline = bm_offset(tline, nb.stride);
700  }
701  fptr = bm_offset(fptr, bm->stride);
702  if(tmask == LASTMASK) {
703  tmask = FIRSTMASK;
704  tptr++;
705  } else
706  NEXTMASK(tmask);
707  }
708 
709  DEBUG((DBG_BITMAP_OPS, "flip_rotate_counter_clockwise (%d,%d) -> (%d,%d)\n",
710  bm->width, bm->height, nb.width, nb.height));
711  mdvi_free(bm->data);
712  bm->data = nb.data;
713  bm->width = nb.width;
714  bm->height = nb.height;
715  bm->stride = nb.stride;
716  if(SHOW_OP_DATA)
717  bitmap_print(stderr, bm);
718 }
719 
720 #if 0
721 void bitmap_transform(BITMAP *map, DviOrientation orient)
722 {
723  switch(orient) {
724  case MDVI_ORIENT_TBLR:
725  break;
726  case MDVI_ORIENT_TBRL:
727  bitmap_flip_horizontally(map);
728  break;
729  case MDVI_ORIENT_BTLR:
730  bitmap_flip_vertically(map);
731  break;
732  case MDVI_ORIENT_BTRL:
733  bitmap_flip_diagonally(map);
734  break;
735  case MDVI_ORIENT_RP90:
736  bitmap_rotate_counter_clockwise(map);
737  break;
738  case MDVI_ORIENT_RM90:
739  bitmap_rotate_clockwise(map);
740  break;
741  case MDVI_ORIENT_IRP90:
742  bitmap_flip_rotate_counter_clockwise(map);
743  break;
744  case MDVI_ORIENT_IRM90:
745  bitmap_flip_rotate_clockwise(map);
746  break;
747  }
748 }
749 #endif
750 
751 /*
752  * Count the number of non-zero bits in a box of dimensions w x h, starting
753  * at column `step' in row `data'.
754  *
755  * Shamelessly stolen from xdvi.
756  */
757 static int do_sample(BmUnit *data, int stride, int step, int w, int h)
758 {
759  BmUnit *ptr, *end, *cp;
760  int shift, n;
761  int bits_left;
762  int wid;
763 
764  ptr = data + step / BITMAP_BITS;
765  end = bm_offset(data, h * stride);
766  shift = FIRSTSHIFTAT(step);
767  bits_left = w;
768  n = 0;
769  while(bits_left) {
770 #ifndef WORD_BIG_ENDIAN
771  wid = BITMAP_BITS - shift;
772 #else
773  wid = shift;
774 #endif
775  if(wid > bits_left)
776  wid = bits_left;
777  if(wid > 8)
778  wid = 8;
779 #ifdef WORD_BIG_ENDIAN
780  shift -= wid;
781 #endif
782  for(cp = ptr; cp < end; cp = bm_offset(cp, stride))
783  n += sample_count[(*cp >> shift) & bit_masks[wid]];
784 #ifndef WORD_BIG_ENDIAN
785  shift += wid;
786 #endif
787 #ifdef WORD_BIG_ENDIAN
788  if(shift == 0) {
789  shift = BITMAP_BITS;
790  ptr++;
791  }
792 #else
793  if(shift == BITMAP_BITS) {
794  shift = 0;
795  ptr++;
796  }
797 #endif
798  bits_left -= wid;
799  }
800  return n;
801 }
802 
803 void mdvi_shrink_box(DviContext *dvi, DviFont *font,
804  DviFontChar *pk, DviGlyph *dest)
805 {
806  int x, y, z;
807  DviGlyph *glyph;
808  int hs, vs;
809 
810  hs = dvi->params.hshrink;
811  vs = dvi->params.vshrink;
812  glyph = &pk->glyph;
813 
814  x = (int)glyph->x / hs;
815  if((int)glyph->x - x * hs > 0)
816  x++;
817  dest->w = x + ROUND((int)glyph->w - glyph->x, hs);
818 
819  z = (int)glyph->y + 1;
820  y = z / vs;
821  if(z - y * vs <= 0)
822  y--;
823  dest->h = y + ROUND((int)glyph->h - z, vs) + 1;
824  dest->x = x;
825  dest->y = glyph->y / vs;
826  dest->data = MDVI_GLYPH_EMPTY;
827  DEBUG((DBG_BITMAPS, "shrink_box: (%dw,%dh,%dx,%dy) -> (%dw,%dh,%dx,%dy)\n",
828  glyph->w, glyph->h, glyph->x, glyph->y,
829  dest->w, dest->h, dest->x, dest->y));
830 }
831 
832 void mdvi_shrink_glyph(DviContext *dvi, DviFont *font,
833  DviFontChar *pk, DviGlyph *dest)
834 {
835  int rows_left, rows, init_cols;
836  int cols_left, cols;
837  BmUnit *old_ptr, *new_ptr;
838  BITMAP *oldmap, *newmap;
839  BmUnit m, *cp;
840  DviGlyph *glyph;
841  int sample, min_sample;
842  int old_stride;
843  int new_stride;
844  int x, y;
845  int w, h;
846  int hs, vs;
847 
848  hs = dvi->params.hshrink;
849  vs = dvi->params.vshrink;
850 
851  min_sample = vs * hs * dvi->params.density / 100;
852 
853  glyph = &pk->glyph;
854  oldmap = (BITMAP *)glyph->data;
855 
856  x = (int)glyph->x / hs;
857  init_cols = (int)glyph->x - x * hs;
858  if(init_cols <= 0)
859  init_cols += hs;
860  else
861  x++;
862  w = x + ROUND((int)glyph->w - glyph->x, hs);
863 
864  cols = (int)glyph->y + 1;
865  y = cols / vs;
866  rows = cols - y * vs;
867  if(rows <= 0) {
868  rows += vs;
869  y--;
870  }
871  h = y + ROUND((int)glyph->h - cols, vs) + 1;
872 
873  /* create the new glyph */
874  newmap = bitmap_alloc(w, h);
875  dest->data = newmap;
876  dest->x = x;
877  dest->y = glyph->y / vs;
878  dest->w = w;
879  dest->h = h;
880 
881  old_ptr = oldmap->data;
882  old_stride = oldmap->stride;
883  new_ptr = newmap->data;
884  new_stride = newmap->stride;
885  rows_left = glyph->h;
886 
887  while(rows_left) {
888  if(rows > rows_left)
889  rows = rows_left;
890  cols_left = glyph->w;
891  m = FIRSTMASK;
892  cp = new_ptr;
893  cols = init_cols;
894  while(cols_left > 0) {
895  if(cols > cols_left)
896  cols = cols_left;
897  sample = do_sample(old_ptr, old_stride,
898  glyph->w - cols_left, cols, rows);
899  if(sample >= min_sample)
900  *cp |= m;
901  if(m == LASTMASK) {
902  m = FIRSTMASK;
903  cp++;
904  } else
905  NEXTMASK(m);
906  cols_left -= cols;
907  cols = hs;
908  }
909  new_ptr = bm_offset(new_ptr, new_stride);
910  old_ptr = bm_offset(old_ptr, rows * old_stride);
911  rows_left -= rows;
912  rows = vs;
913  }
914  DEBUG((DBG_BITMAPS, "shrink_glyph: (%dw,%dh,%dx,%dy) -> (%dw,%dh,%dx,%dy)\n",
915  glyph->w, glyph->h, glyph->x, glyph->y,
916  dest->w, dest->h, dest->x, dest->y));
917  if(DEBUGGING(BITMAP_DATA))
918  bitmap_print(stderr, newmap);
919 }
920 
921 void mdvi_shrink_glyph_grey(DviContext *dvi, DviFont *font,
922  DviFontChar *pk, DviGlyph *dest)
923 {
924  int rows_left, rows;
925  int cols_left, cols, init_cols;
926  long sampleval, samplemax;
927  BmUnit *old_ptr;
928  void *image;
929  int w, h;
930  int x, y;
931  DviGlyph *glyph;
932  BITMAP *map;
933  Ulong *pixels;
934  int npixels;
935  Ulong colortab[2];
936  int hs, vs;
937  DviDevice *dev;
938 
939  hs = dvi->params.hshrink;
940  vs = dvi->params.vshrink;
941  dev = &dvi->device;
942 
943  glyph = &pk->glyph;
944  map = (BITMAP *)glyph->data;
945 
946  x = (int)glyph->x / hs;
947  init_cols = (int)glyph->x - x * hs;
948  if(init_cols <= 0)
949  init_cols += hs;
950  else
951  x++;
952  w = x + ROUND((int)glyph->w - glyph->x, hs);
953 
954  cols = (int)glyph->y + 1;
955  y = cols / vs;
956  rows = cols - y * vs;
957  if(rows <= 0) {
958  rows += vs;
959  y--;
960  }
961  h = y + ROUND((int)glyph->h - cols, vs) + 1;
962  ASSERT(w && h);
963 
964  /* before touching anything, do this */
965  image = dev->create_image(dev->device_data, w, h, BITMAP_BITS);
966  if(image == NULL) {
967  mdvi_shrink_glyph(dvi, font, pk, dest);
968  return;
969  }
970 
971  /* save these colors */
972  pk->fg = MDVI_CURRFG(dvi);
973  pk->bg = MDVI_CURRBG(dvi);
974 
975  samplemax = vs * hs;
976  npixels = samplemax + 1;
977  pixels = get_color_table(&dvi->device, npixels, pk->fg, pk->bg,
978  dvi->params.gamma, dvi->params.density);
979  if(pixels == NULL) {
980  npixels = 2;
981  colortab[0] = pk->fg;
982  colortab[1] = pk->bg;
983  pixels = &colortab[0];
984  }
985 
986  /* setup the new glyph */
987  dest->data = image;
988  dest->x = x;
989  dest->y = glyph->y / vs;
990  dest->w = w;
991  dest->h = h;
992 
993  y = 0;
994  old_ptr = map->data;
995  rows_left = glyph->h;
996 
997  while(rows_left && y < h) {
998  x = 0;
999  if(rows > rows_left)
1000  rows = rows_left;
1001  cols_left = glyph->w;
1002  cols = init_cols;
1003  while(cols_left && x < w) {
1004  if(cols > cols_left)
1005  cols = cols_left;
1006  sampleval = do_sample(old_ptr, map->stride,
1007  glyph->w - cols_left, cols, rows);
1008  /* scale the sample value by the number of grey levels */
1009  if(npixels - 1 != samplemax)
1010  sampleval = ((npixels-1) * sampleval) / samplemax;
1011  ASSERT(sampleval < npixels);
1012  dev->put_pixel(image, x, y, pixels[sampleval]);
1013  cols_left -= cols;
1014  cols = hs;
1015  x++;
1016  }
1017  for(; x < w; x++)
1018  dev->put_pixel(image, x, y, pixels[0]);
1019  old_ptr = bm_offset(old_ptr, rows * map->stride);
1020  rows_left -= rows;
1021  rows = vs;
1022  y++;
1023  }
1024 
1025  for(; y < h; y++) {
1026  for(x = 0; x < w; x++)
1027  dev->put_pixel(image, x, y, pixels[0]);
1028  }
1029 
1030  dev->image_done(image);
1031  DEBUG((DBG_BITMAPS, "shrink_glyph_grey: (%dw,%dh,%dx,%dy) -> (%dw,%dh,%dx,%dy)\n",
1032  glyph->w, glyph->h, glyph->x, glyph->y,
1033  dest->w, dest->h, dest->x, dest->y));
1034 }
1035