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