backend/dvi/mdvi-lib/bitmap.c

   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         Uchar   *end;
 135         int     bytes;
 136
 137         DEBUG((DBG_BITMAP_OPS, "convert LSB %dx%d@8 -> bitmap\n", w, h));
 138
 139         bm = bitmap_alloc_raw(w, h);
 140
 141         /* this is the number of bytes in the original bitmap */
 142         bytes = ROUND(w, 8);
 143         unit  = (Uchar *)bm->data;
 144         end   = unit + bm->stride;
 145         curr = bits;
 146         /* we try to do this as fast as we can */
 147         for(i = 0; i < h; i++) {
 148 #ifdef WORD_LITTLE_ENDIAN
 149                 memcpy(unit, curr, bytes);
 150                 curr += stride;
 151 #else
 152                 int     j;
 153
 154                 for(j = 0; j < bytes; curr++, j++)
 155                         unit[j] = bit_swap[*curr];
 156                 cur += stride - bytes;
 157 #endif
 158                 memzero(unit + bytes, bm->stride - bytes);
 159                 unit  += bm->stride;
 160         }
 161         if(SHOW_OP_DATA)
 162                 bitmap_print(stderr, bm);
 163         return bm;
 164 }
 165
 166 BITMAP  *bitmap_convert_msb8(Uchar *data, int w, int h, int stride)
 167 {
 168         BITMAP  *bm;
 169         Uchar   *unit;
 170         Uchar   *curr;
 171         int     i;
 172         int     bytes;
 173
 174         bm = bitmap_alloc(w, h);
 175         bytes = ROUND(w, 8);
 176         unit = (Uchar *)bm->data;
 177         curr = data;
 178         for(i = 0; i < h; i++) {
 179 #ifdef WORD_LITTLE_ENDIAN
 180                 int     j;
 181
 182                 for(j = 0; j < bytes; curr++, j++)
 183                         unit[j] = bit_swap[*curr];
 184                 curr += stride - bytes;
 185 #else
 186                 memcpy(unit, curr, bytes);
 187                 curr += stride;
 188 #endif
 189                 memzero(unit + bytes, bm->stride - bytes);
 190                 unit += bm->stride;
 191         }
 192         if(SHOW_OP_DATA)
 193                 bitmap_print(stderr, bm);
 194         return bm;
 195 }
 196
 197
 198 BITMAP  *bitmap_copy(BITMAP *bm)
 199 {
 200         BITMAP  *nb = bitmap_alloc(bm->width, bm->height);
 201
 202         DEBUG((DBG_BITMAP_OPS, "copy %dx%d\n", bm->width, bm->height));
 203         memcpy(nb->data, bm->data, bm->height * bm->stride);
 204         return nb;
 205 }
 206
 207 BITMAP  *bitmap_alloc(int w, int h)
 208 {
 209         BITMAP  *bm;
 210
 211         bm = xalloc(BITMAP);
 212         bm->width = w;
 213         bm->height = h;
 214         bm->stride = BM_BYTES_PER_LINE(bm);
 215         if(h && bm->stride)
 216                 bm->data = (BmUnit *)mdvi_calloc(h, bm->stride);
 217         else
 218                 bm->data = NULL;
 219
 220         return bm;
 221 }
 222
 223 BITMAP  *bitmap_alloc_raw(int w, int h)
 224 {
 225         BITMAP  *bm;
 226
 227         bm = xalloc(BITMAP);
 228         bm->width = w;
 229         bm->height = h;
 230         bm->stride = BM_BYTES_PER_LINE(bm);
 231         if(h && bm->stride)
 232                 bm->data = (BmUnit *)mdvi_malloc(h * bm->stride);
 233         else
 234                 bm->data = NULL;
 235
 236         return bm;
 237 }
 238
 239 void    bitmap_destroy(BITMAP *bm)
 240 {
 241         if(bm->data)
 242                 free(bm->data);
 243         free(bm);
 244 }
 245
 246 void    bitmap_print(FILE *out, BITMAP *bm)
 247 {
 248         int     i, j;
 249         BmUnit  *a, mask;
 250         static const char labels[] = {
 251                 '1', '2', '3', '4', '5', '6', '7', '8', '9', '0'
 252         };
 253         int     sub;
 254
 255         a = bm->data;
 256         fprintf(out, "    ");
 257         if(bm->width > 10) {
 258                 putchar('0');
 259                 sub = 0;
 260                 for(j = 2; j <= bm->width; j++)
 261                         if((j %10) == 0) {
 262                                 if((j % 100) == 0) {
 263                                         fprintf(out, "*");
 264                                         sub += 100;
 265                                 } else
 266                                         fprintf(out, "%d", (j - sub)/10);
 267                         } else
 268                                 putc(' ', out);
 269                 fprintf(out, "\n    ");
 270         }
 271         for(j = 0; j < bm->width; j++)
 272                 putc(labels[j % 10], out);
 273         putchar('\n');
 274         for(i = 0; i < bm->height; i++) {
 275                 mask = FIRSTMASK;
 276                 a = (BmUnit *)((char *)bm->data + i * bm->stride);
 277                 fprintf(out, "%3d ", i+1);
 278                 for(j = 0; j < bm->width; j++) {
 279                         if(*a & mask)
 280                                 putc('#', out);
 281                         else
 282                                 putc('.', out);
 283                         if(mask == LASTMASK) {
 284                                 a++;
 285                                 mask = FIRSTMASK;
 286                         } else
 287                                 NEXTMASK(mask);
 288                 }
 289                 putchar('\n');
 290         }
 291 }
 292
 293 void bitmap_set_col(BITMAP *bm, int row, int col, int count, int state)
 294 {
 295         BmUnit  *ptr;
 296         BmUnit  mask;
 297
 298         ptr = __bm_unit_ptr(bm, col, row);
 299         mask = FIRSTMASKAT(col);
 300
 301         while(count-- > 0) {
 302                 if(state)
 303                         *ptr |= mask;
 304                 else
 305                         *ptr &= ~mask;
 306                 /* move to next row */
 307                 ptr = bm_offset(ptr, bm->stride);
 308         }
 309 }
 310
 311 /*
 312  * to use this function you should first make sure that
 313  * there is room for `count' bits in the scanline
 314  *
 315  * A general-purpose (but not very efficient) function to paint `n' pixels
 316  * on a bitmap, starting at position (x, y) would be:
 317  *
 318  *    bitmap_paint_bits(__bm_unit_ptr(bitmap, x, y), x % BITMAP_BITS, n)
 319  *
 320  */
 321 void    bitmap_paint_bits(BmUnit *ptr, int n, int count)
 322 {
 323         /* paint the head */
 324         if(n + count > BITMAP_BITS) {
 325                 *ptr |= SEGMENT(BITMAP_BITS - n, n);
 326                 count -= BITMAP_BITS - n;
 327                 ptr++;
 328         } else {
 329                 *ptr |= SEGMENT(count, n);
 330                 return;
 331         }
 332
 333         /* paint the middle */
 334         for(; count >= BITMAP_BITS; count -= BITMAP_BITS)
 335                 *ptr++ = bit_masks[BITMAP_BITS];
 336
 337         /* paint the tail */
 338         if(count > 0)
 339                 *ptr |= SEGMENT(count, 0);
 340 }
 341
 342 /*
 343  * same as paint_bits but clears pixels instead of painting them. Written
 344  * as a separate function for efficiency reasons.
 345  */
 346 void bitmap_clear_bits(BmUnit *ptr, int n, int count)
 347 {
 348         if(n + count > BITMAP_BITS) {
 349                 *ptr &= ~SEGMENT(BITMAP_BITS - n, n);
 350                 count -= BITMAP_BITS;
 351                 ptr++;
 352         } else {
 353                 *ptr &= ~SEGMENT(count, n);
 354                 return;
 355         }
 356
 357         for(; count >= BITMAP_BITS; count -= BITMAP_BITS)
 358                 *ptr++ = 0;
 359
 360         if(count > 0)
 361                 *ptr &= ~SEGMENT(count, 0);
 362 }
 363
 364 /* the general function to paint rows. Still used by the PK reader, but that
 365  * will change soon (The GF reader already uses bitmap_paint_bits()).
 366  */
 367 void    bitmap_set_row(BITMAP *bm, int row, int col, int count, int state)
 368 {
 369         BmUnit  *ptr;
 370
 371         ptr = __bm_unit_ptr(bm, col, row);
 372         if(state)
 373                 bitmap_paint_bits(ptr, col & (BITMAP_BITS-1), count);
 374         else
 375                 bitmap_clear_bits(ptr, col & (BITMAP_BITS-1), count);
 376 }
 377
 378 /*
 379  * Now several `flipping' operations
 380  */
 381
 382 void bitmap_flip_horizontally(BITMAP *bm)
 383 {
 384         BITMAP  nb;
 385         BmUnit  *fptr, *tptr;
 386         BmUnit  fmask, tmask;
 387         int     w, h;
 388
 389         nb.width = bm->width;
 390         nb.height = bm->height;
 391         nb.stride = bm->stride;
 392         nb.data = mdvi_calloc(bm->height, bm->stride);
 393
 394         fptr = bm->data;
 395         tptr = __bm_unit_ptr(&nb, nb.width-1, 0);
 396         for(h = 0; h < bm->height; h++) {
 397                 BmUnit  *fline, *tline;
 398
 399                 fline = fptr;
 400                 tline = tptr;
 401                 fmask = FIRSTMASK;
 402                 tmask = FIRSTMASKAT(nb.width-1);
 403                 for(w = 0; w < bm->width; w++) {
 404                         if(*fline & fmask)
 405                                 *tline |= tmask;
 406                         if(fmask == LASTMASK) {
 407                                 fmask = FIRSTMASK;
 408                                 fline++;
 409                         } else
 410                                 NEXTMASK(fmask);
 411                         if(tmask == FIRSTMASK) {
 412                                 tmask = LASTMASK;
 413                                 tline--;
 414                         } else
 415                                 PREVMASK(tmask);
 416                 }
 417                 fptr = bm_offset(fptr, bm->stride);
 418                 tptr = bm_offset(tptr, bm->stride);
 419         }
 420         DEBUG((DBG_BITMAP_OPS, "flip_horizontally (%d,%d) -> (%d,%d)\n",
 421                 bm->width, bm->height, nb.width, nb.height));
 422         mdvi_free(bm->data);
 423         bm->data = nb.data;
 424         if(SHOW_OP_DATA)
 425                 bitmap_print(stderr, bm);
 426 }
 427
 428 void    bitmap_flip_vertically(BITMAP *bm)
 429 {
 430         BITMAP  nb;
 431         BmUnit  *fptr, *tptr;
 432         BmUnit  fmask;
 433         int     w, h;
 434
 435         nb.width = bm->width;
 436         nb.height = bm->height;
 437         nb.stride = bm->stride;
 438         nb.data = mdvi_calloc(bm->height, bm->stride);
 439
 440         fptr = bm->data;
 441         tptr = __bm_unit_ptr(&nb, 0, nb.height-1);
 442         for(h = 0; h < bm->height; h++) {
 443                 BmUnit  *fline, *tline;
 444
 445                 fline = fptr;
 446                 tline = tptr;
 447                 fmask = FIRSTMASK;
 448                 for(w = 0; w < bm->width; w++) {
 449                         if(*fline & fmask)
 450                                 *tline |= fmask;
 451                         if(fmask == LASTMASK) {
 452                                 fmask = FIRSTMASK;
 453                                 fline++;
 454                                 tline++;
 455                         } else
 456                                 NEXTMASK(fmask);
 457                 }
 458                 fptr = bm_offset(fptr, bm->stride);
 459                 tptr = (BmUnit *)((char *)tptr - bm->stride);
 460         }
 461         DEBUG((DBG_BITMAP_OPS, "flip_vertically (%d,%d) -> (%d,%d)\n",
 462                 bm->width, bm->height, nb.width, nb.height));
 463         mdvi_free(bm->data);
 464         bm->data = nb.data;
 465         if(SHOW_OP_DATA)
 466                 bitmap_print(stderr, bm);
 467 }
 468
 469 void    bitmap_flip_diagonally(BITMAP *bm)
 470 {
 471         BITMAP  nb;
 472         BmUnit  *fptr, *tptr;
 473         BmUnit  fmask, tmask;
 474         int     w, h;
 475
 476         nb.width = bm->width;
 477         nb.height = bm->height;
 478         nb.stride = bm->stride;
 479         nb.data = mdvi_calloc(bm->height, bm->stride);
 480
 481         fptr = bm->data;
 482         tptr = __bm_unit_ptr(&nb, nb.width-1, nb.height-1);
 483         for(h = 0; h < bm->height; h++) {
 484                 BmUnit  *fline, *tline;
 485
 486                 fline = fptr;
 487                 tline = tptr;
 488                 fmask = FIRSTMASK;
 489                 tmask = FIRSTMASKAT(nb.width-1);
 490                 for(w = 0; w < bm->width; w++) {
 491                         if(*fline & fmask)
 492                                 *tline |= tmask;
 493                         if(fmask == LASTMASK) {
 494                                 fmask = FIRSTMASK;
 495                                 fline++;
 496                         } else
 497                                 NEXTMASK(fmask);
 498                         if(tmask == FIRSTMASK) {
 499                                 tmask = LASTMASK;
 500                                 tline--;
 501                         } else
 502                                 PREVMASK(tmask);
 503                 }
 504                 fptr = bm_offset(fptr, bm->stride);
 505                 tptr = bm_offset(tptr, -nb.stride);
 506         }
 507         DEBUG((DBG_BITMAP_OPS, "flip_diagonally (%d,%d) -> (%d,%d)\n",
 508                 bm->width, bm->height, nb.width, nb.height));
 509         mdvi_free(bm->data);
 510         bm->data = nb.data;
 511         if(SHOW_OP_DATA)
 512                 bitmap_print(stderr, bm);
 513 }
 514
 515 void    bitmap_rotate_clockwise(BITMAP *bm)
 516 {
 517         BITMAP  nb;
 518         BmUnit  *fptr, *tptr;
 519         BmUnit  fmask, tmask;
 520         int     w, h;
 521
 522         nb.width = bm->height;
 523         nb.height = bm->width;
 524         nb.stride = BM_BYTES_PER_LINE(&nb);
 525         nb.data = mdvi_calloc(nb.height, nb.stride);
 526
 527         fptr = bm->data;
 528         tptr = __bm_unit_ptr(&nb, nb.width - 1, 0);
 529
 530         tmask = FIRSTMASKAT(nb.width-1);
 531         for(h = 0; h < bm->height; h++) {
 532                 BmUnit  *fline, *tline;
 533
 534                 fmask = FIRSTMASK;
 535                 fline = fptr;
 536                 tline = tptr;
 537                 for(w = 0; w < bm->width; w++) {
 538                         if(*fline & fmask)
 539                                 *tline |= tmask;
 540                         if(fmask == LASTMASK) {
 541                                 fmask = FIRSTMASK;
 542                                 fline++;
 543                         } else
 544                                 NEXTMASK(fmask);
 545                         /* go to next row */
 546                         tline = bm_offset(tline, nb.stride);
 547                 }
 548                 fptr = bm_offset(fptr, bm->stride);
 549                 if(tmask == FIRSTMASK) {
 550                         tmask = LASTMASK;
 551                         tptr--;
 552                 } else
 553                         PREVMASK(tmask);
 554         }
 555
 556         DEBUG((DBG_BITMAP_OPS, "rotate_clockwise (%d,%d) -> (%d,%d)\n",
 557                 bm->width, bm->height, nb.width, nb.height));
 558         mdvi_free(bm->data);
 559         bm->data = nb.data;
 560         bm->width = nb.width;
 561         bm->height = nb.height;
 562         bm->stride = nb.stride;
 563         if(SHOW_OP_DATA)
 564                 bitmap_print(stderr, bm);
 565 }
 566
 567 void    bitmap_rotate_counter_clockwise(BITMAP *bm)
 568 {
 569         BITMAP  nb;
 570         BmUnit  *fptr, *tptr;
 571         BmUnit  fmask, tmask;
 572         int     w, h;
 573
 574         nb.width = bm->height;
 575         nb.height = bm->width;
 576         nb.stride = BM_BYTES_PER_LINE(&nb);
 577         nb.data = mdvi_calloc(nb.height, nb.stride);
 578
 579         fptr = bm->data;
 580         tptr = __bm_unit_ptr(&nb, 0, nb.height - 1);
 581
 582         tmask = FIRSTMASK;
 583         for(h = 0; h < bm->height; h++) {
 584                 BmUnit  *fline, *tline;
 585
 586                 fmask = FIRSTMASK;
 587                 fline = fptr;
 588                 tline = tptr;
 589                 for(w = 0; w < bm->width; w++) {
 590                         if(*fline & fmask)
 591                                 *tline |= tmask;
 592                         if(fmask == LASTMASK) {
 593                                 fmask = FIRSTMASK;
 594                                 fline++;
 595                         } else
 596                                 NEXTMASK(fmask);
 597                         /* go to previous row */
 598                         tline = bm_offset(tline, -nb.stride);
 599                 }
 600                 fptr = bm_offset(fptr, bm->stride);
 601                 if(tmask == LASTMASK) {
 602                         tmask = FIRSTMASK;
 603                         tptr++;
 604                 } else
 605                         NEXTMASK(tmask);
 606         }
 607
 608         DEBUG((DBG_BITMAP_OPS, "rotate_counter_clockwise (%d,%d) -> (%d,%d)\n",
 609                 bm->width, bm->height, nb.width, nb.height));
 610         mdvi_free(bm->data);
 611         bm->data = nb.data;
 612         bm->width = nb.width;
 613         bm->height = nb.height;
 614         bm->stride = nb.stride;
 615         if(SHOW_OP_DATA)
 616                 bitmap_print(stderr, bm);
 617 }
 618
 619 void    bitmap_flip_rotate_clockwise(BITMAP *bm)
 620 {
 621         BITMAP  nb;
 622         BmUnit  *fptr, *tptr;
 623         BmUnit  fmask, tmask;
 624         int     w, h;
 625
 626         nb.width = bm->height;
 627         nb.height = bm->width;
 628         nb.stride = BM_BYTES_PER_LINE(&nb);
 629         nb.data = mdvi_calloc(nb.height, nb.stride);
 630
 631         fptr = bm->data;
 632         tptr = __bm_unit_ptr(&nb, nb.width-1, nb.height-1);
 633
 634         tmask = FIRSTMASKAT(nb.width-1);
 635         for(h = 0; h < bm->height; h++) {
 636                 BmUnit  *fline, *tline;
 637
 638                 fmask = FIRSTMASK;
 639                 fline = fptr;
 640                 tline = tptr;
 641                 for(w = 0; w < bm->width; w++) {
 642                         if(*fline & fmask)
 643                                 *tline |= tmask;
 644                         if(fmask == LASTMASK) {
 645                                 fmask = FIRSTMASK;
 646                                 fline++;
 647                         } else
 648                                 NEXTMASK(fmask);
 649                         /* go to previous line */
 650                         tline = bm_offset(tline, -nb.stride);
 651                 }
 652                 fptr = bm_offset(fptr, bm->stride);
 653                 if(tmask == FIRSTMASK) {
 654                         tmask = LASTMASK;
 655                         tptr--;
 656                 } else
 657                         PREVMASK(tmask);
 658         }
 659         DEBUG((DBG_BITMAP_OPS, "flip_rotate_clockwise (%d,%d) -> (%d,%d)\n",
 660                 bm->width, bm->height, nb.width, nb.height));
 661         mdvi_free(bm->data);
 662         bm->data = nb.data;
 663         bm->width = nb.width;
 664         bm->height = nb.height;
 665         bm->stride = nb.stride;
 666         if(SHOW_OP_DATA)
 667                 bitmap_print(stderr, bm);
 668 }
 669
 670 void    bitmap_flip_rotate_counter_clockwise(BITMAP *bm)
 671 {
 672         BITMAP  nb;
 673         BmUnit  *fptr, *tptr;
 674         BmUnit  fmask, tmask;
 675         int     w, h;
 676
 677         nb.width = bm->height;
 678         nb.height = bm->width;
 679         nb.stride = BM_BYTES_PER_LINE(&nb);
 680         nb.data = mdvi_calloc(nb.height, nb.stride);
 681
 682         fptr = bm->data;
 683         tptr = nb.data;
 684         tmask = FIRSTMASK;
 685
 686         for(h = 0; h < bm->height; h++) {
 687                 BmUnit  *fline, *tline;
 688
 689                 fmask = FIRSTMASK;
 690                 fline = fptr;
 691                 tline = tptr;
 692                 for(w = 0; w < bm->width; w++) {
 693                         if(*fline & fmask)
 694                                 *tline |= tmask;
 695                         if(fmask == LASTMASK) {
 696                                 fmask = FIRSTMASK;
 697                                 fline++;
 698                         } else
 699                                 NEXTMASK(fmask);
 700                         /* go to next line */
 701                         tline = bm_offset(tline, nb.stride);
 702                 }
 703                 fptr = bm_offset(fptr, bm->stride);
 704                 if(tmask == LASTMASK) {
 705                         tmask = FIRSTMASK;
 706                         tptr++;
 707                 } else
 708                         NEXTMASK(tmask);
 709         }
 710
 711         DEBUG((DBG_BITMAP_OPS, "flip_rotate_counter_clockwise (%d,%d) -> (%d,%d)\n",
 712                 bm->width, bm->height, nb.width, nb.height));
 713         mdvi_free(bm->data);
 714         bm->data = nb.data;
 715         bm->width = nb.width;
 716         bm->height = nb.height;
 717         bm->stride = nb.stride;
 718         if(SHOW_OP_DATA)
 719                 bitmap_print(stderr, bm);
 720 }
 721
 722 #if 0
 723 void    bitmap_transform(BITMAP *map, DviOrientation orient)
 724 {
 725         switch(orient) {
 726                 case MDVI_ORIENT_TBLR:
 727                         break;
 728                 case MDVI_ORIENT_TBRL:
 729                         bitmap_flip_horizontally(map);
 730                         break;
 731                 case MDVI_ORIENT_BTLR:
 732                         bitmap_flip_vertically(map);
 733                         break;
 734                 case MDVI_ORIENT_BTRL:
 735                         bitmap_flip_diagonally(map);
 736                         break;
 737                 case MDVI_ORIENT_RP90:
 738                         bitmap_rotate_counter_clockwise(map);
 739                         break;
 740                 case MDVI_ORIENT_RM90:
 741                         bitmap_rotate_clockwise(map);
 742                         break;
 743                 case MDVI_ORIENT_IRP90:
 744                         bitmap_flip_rotate_counter_clockwise(map);
 745                         break;
 746                 case MDVI_ORIENT_IRM90:
 747                         bitmap_flip_rotate_clockwise(map);
 748                         break;
 749         }
 750 }
 751 #endif
 752
 753 /*
 754  * Count the number of non-zero bits in a box of dimensions w x h, starting
 755  * at column `step' in row `data'.
 756  *
 757  * Shamelessly stolen from xdvi.
 758  */
 759 static int do_sample(BmUnit *data, int stride, int step, int w, int h)
 760 {
 761         BmUnit  *ptr, *end, *cp;
 762         int     shift, n;
 763         int     bits_left;
 764         int     wid;
 765
 766         ptr = data + step / BITMAP_BITS;
 767         end = bm_offset(data, h * stride);
 768         shift = FIRSTSHIFTAT(step);
 769         bits_left = w;
 770         n = 0;
 771         while(bits_left) {
 772 #ifndef WORD_BIG_ENDIAN
 773                 wid = BITMAP_BITS - shift;
 774 #else
 775                 wid = shift;
 776 #endif
 777                 if(wid > bits_left)
 778                         wid = bits_left;
 779                 if(wid > 8)
 780                         wid = 8;
 781 #ifdef WORD_BIG_ENDIAN
 782                 shift -= wid;
 783 #endif
 784                 for(cp = ptr; cp < end; cp = bm_offset(cp, stride))
 785                         n += sample_count[(*cp >> shift) & bit_masks[wid]];
 786 #ifndef WORD_BIG_ENDIAN
 787                 shift += wid;
 788 #endif
 789 #ifdef WORD_BIG_ENDIAN
 790                 if(shift == 0) {
 791                         shift = BITMAP_BITS;
 792                         ptr++;
 793                 }
 794 #else
 795                 if(shift == BITMAP_BITS) {
 796                         shift = 0;
 797                         ptr++;
 798                 }
 799 #endif
 800                 bits_left -= wid;
 801         }
 802         return n;
 803 }
 804
 805 void    mdvi_shrink_box(DviContext *dvi, DviFont *font,
 806         DviFontChar *pk, DviGlyph *dest)
 807 {
 808         int     x, y, z;
 809         DviGlyph *glyph;
 810         int     hs, vs;
 811
 812         hs = dvi->params.hshrink;
 813         vs = dvi->params.vshrink;
 814         glyph = &pk->glyph;
 815
 816         x = (int)glyph->x / hs;
 817         if((int)glyph->x - x * hs > 0)
 818                 x++;
 819         dest->w = x + ROUND((int)glyph->w - glyph->x, hs);
 820
 821         z = (int)glyph->y + 1;
 822         y = z / vs;
 823         if(z - y * vs <= 0)
 824                 y--;
 825         dest->h = y + ROUND((int)glyph->h - z, vs) + 1;
 826         dest->x = x;
 827         dest->y = glyph->y / vs;
 828         dest->data = MDVI_GLYPH_EMPTY;
 829         DEBUG((DBG_BITMAPS, "shrink_box: (%dw,%dh,%dx,%dy) -> (%dw,%dh,%dx,%dy)\n",
 830                 glyph->w, glyph->h, glyph->x, glyph->y,
 831                 dest->w, dest->h, dest->x, dest->y));
 832 }
 833
 834 void    mdvi_shrink_glyph(DviContext *dvi, DviFont *font,
 835         DviFontChar *pk, DviGlyph *dest)
 836 {
 837         int     rows_left, rows, init_cols;
 838         int     cols_left, cols;
 839         BmUnit  *old_ptr, *new_ptr;
 840         BITMAP  *oldmap, *newmap;
 841         BmUnit  m, *cp;
 842         DviGlyph *glyph;
 843         int     sample, min_sample;
 844         int     old_stride;
 845         int     new_stride;
 846         int     x, y;
 847         int     w, h;
 848         int     hs, vs;
 849
 850         hs = dvi->params.hshrink;
 851         vs = dvi->params.vshrink;
 852
 853         min_sample = vs * hs * dvi->params.density / 100;
 854
 855         glyph = &pk->glyph;
 856         oldmap = (BITMAP *)glyph->data;
 857
 858         x = (int)glyph->x / hs;
 859         init_cols = (int)glyph->x - x * hs;
 860         if(init_cols <= 0)
 861                 init_cols += hs;
 862         else
 863                 x++;
 864         w = x + ROUND((int)glyph->w - glyph->x, hs);
 865
 866         cols = (int)glyph->y + 1;
 867         y = cols / vs;
 868         rows = cols - y * vs;
 869         if(rows <= 0) {
 870                 rows += vs;
 871                 y--;
 872         }
 873         h = y + ROUND((int)glyph->h - cols, vs) + 1;
 874
 875         /* create the new glyph */
 876         newmap = bitmap_alloc(w, h);
 877         dest->data = newmap;
 878         dest->x = x;
 879         dest->y = glyph->y / vs;
 880         dest->w = w;
 881         dest->h = h;
 882
 883         old_ptr = oldmap->data;
 884         old_stride = oldmap->stride;
 885         new_ptr = newmap->data;
 886         new_stride = newmap->stride;
 887         rows_left = glyph->h;
 888
 889         while(rows_left) {
 890                 if(rows > rows_left)
 891                         rows = rows_left;
 892                 cols_left = glyph->w;
 893                 m = FIRSTMASK;
 894                 cp = new_ptr;
 895                 cols = init_cols;
 896                 while(cols_left > 0) {
 897                         if(cols > cols_left)
 898                                 cols = cols_left;
 899                         sample = do_sample(old_ptr, old_stride,
 900                                 glyph->w - cols_left, cols, rows);
 901                         if(sample >= min_sample)
 902                                 *cp |= m;
 903                         if(m == LASTMASK) {
 904                                 m = FIRSTMASK;
 905                                 cp++;
 906                         } else
 907                                 NEXTMASK(m);
 908                         cols_left -= cols;
 909                         cols = hs;
 910                 }
 911                 new_ptr = bm_offset(new_ptr, new_stride);
 912                 old_ptr = bm_offset(old_ptr, rows * old_stride);
 913                 rows_left -= rows;
 914                 rows = vs;
 915         }
 916         DEBUG((DBG_BITMAPS, "shrink_glyph: (%dw,%dh,%dx,%dy) -> (%dw,%dh,%dx,%dy)\n",
 917                 glyph->w, glyph->h, glyph->x, glyph->y,
 918                 dest->w, dest->h, dest->x, dest->y));
 919         if(DEBUGGING(BITMAP_DATA))
 920                 bitmap_print(stderr, newmap);
 921 }
 922
 923 void    mdvi_shrink_glyph_grey(DviContext *dvi, DviFont *font,
 924         DviFontChar *pk, DviGlyph *dest)
 925 {
 926         int     rows_left, rows;
 927         int     cols_left, cols, init_cols;
 928         long    sampleval, samplemax;
 929         BmUnit  *old_ptr;
 930         void    *image;
 931         int     w, h;
 932         int     x, y;
 933         DviGlyph *glyph;
 934         BITMAP  *map;
 935         Ulong   *pixels;
 936         int     npixels;
 937         Ulong   colortab[2];
 938         int     hs, vs;
 939         DviDevice *dev;
 940
 941         hs = dvi->params.hshrink;
 942         vs = dvi->params.vshrink;
 943         dev = &dvi->device;
 944
 945         glyph = &pk->glyph;
 946         map = (BITMAP *)glyph->data;
 947
 948         x = (int)glyph->x / hs;
 949         init_cols = (int)glyph->x - x * hs;
 950         if(init_cols <= 0)
 951                 init_cols += hs;
 952         else
 953                 x++;
 954         w = x + ROUND((int)glyph->w - glyph->x, hs);
 955
 956         cols = (int)glyph->y + 1;
 957         y = cols / vs;
 958         rows = cols - y * vs;
 959         if(rows <= 0) {
 960                 rows += vs;
 961                 y--;
 962         }
 963         h = y + ROUND((int)glyph->h - cols, vs) + 1;
 964         ASSERT(w && h);
 965
 966         /* before touching anything, do this */
 967         image = dev->create_image(dev->device_data, w, h, BITMAP_BITS);
 968         if(image == NULL) {
 969                 mdvi_shrink_glyph(dvi, font, pk, dest);
 970                 return;
 971         }
 972
 973         /* save these colors */
 974         pk->fg = MDVI_CURRFG(dvi);
 975         pk->bg = MDVI_CURRBG(dvi);
 976
 977         samplemax = vs * hs;
 978         npixels = samplemax + 1;
 979         pixels = get_color_table(&dvi->device, npixels, pk->fg, pk->bg,
 980                         dvi->params.gamma, dvi->params.density);
 981         if(pixels == NULL) {
 982                 npixels = 2;
 983                 colortab[0] = pk->fg;
 984                 colortab[1] = pk->bg;
 985                 pixels = &colortab[0];
 986         }
 987
 988         /* setup the new glyph */
 989         dest->data = image;
 990         dest->x = x;
 991         dest->y = glyph->y / vs;
 992         dest->w = w;
 993         dest->h = h;
 994
 995         y = 0;
 996         old_ptr = map->data;
 997         rows_left = glyph->h;
 998
 999         while(rows_left && y < h) {
1000                 x = 0;
1001                 if(rows > rows_left)
1002                         rows = rows_left;
1003                 cols_left = glyph->w;
1004                 cols = init_cols;
1005                 while(cols_left && x < w) {
1006                         if(cols > cols_left)
1007                                 cols = cols_left;
1008                         sampleval = do_sample(old_ptr, map->stride,
1009                                 glyph->w - cols_left, cols, rows);
1010                         /* scale the sample value by the number of grey levels */
1011                         if(npixels - 1 != samplemax)
1012                                 sampleval = ((npixels-1) * sampleval) / samplemax;
1013                         ASSERT(sampleval < npixels);
1014                         dev->put_pixel(image, x, y, pixels[sampleval]);
1015                         cols_left -= cols;
1016                         cols = hs;
1017                         x++;
1018                 }
1019                 for(; x < w; x++)
1020                         dev->put_pixel(image, x, y, pixels[0]);
1021                 old_ptr = bm_offset(old_ptr, rows * map->stride);
1022                 rows_left -= rows;
1023                 rows = vs;
1024                 y++;
1025         }
1026
1027         for(; y < h; y++) {
1028                 for(x = 0; x < w; x++)
1029                         dev->put_pixel(image, x, y, pixels[0]);
1030         }
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