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 <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)
 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 += bytes;
 151 #else
 152                 int     j;
 153
 154                 for(j = 0; j < bytes; curr++, j++)
 155                         unit[j] = bit_swap[*curr];
 156 #endif
 157                 memzero(unit + bytes, bm->stride - bytes);
 158                 unit  += bm->stride;
 159         }
 160         if(SHOW_OP_DATA)
 161                 bitmap_print(stderr, bm);
 162         return bm;
 163 }
 164
 165 BITMAP  *bitmap_convert_msb8(Uchar *data, int w, int h)
 166 {
 167         BITMAP  *bm;
 168         Uchar   *unit;
 169         Uchar   *curr;
 170         int     i;
 171         int     bytes;
 172
 173         bm = bitmap_alloc(w, h);
 174         bytes = ROUND(w, 8);
 175         unit = (Uchar *)bm->data;
 176         curr = data;
 177         for(i = 0; i < h; i++) {
 178 #ifdef WORD_LITTLE_ENDIAN
 179                 int     j;
 180
 181                 for(j = 0; j < bytes; curr++, j++)
 182                         unit[j] = bit_swap[*curr];
 183 #else
 184                 memcpy(unit, curr, bytes);
 185                 curr += bytes;
 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         DEBUG((DBG_BITMAPS, "shrink_glyph_grey: (%dw,%dh,%dx,%dy) -> (%dw,%dh,%dx,%dy)\n",
1030                 glyph->w, glyph->h, glyph->x, glyph->y,
1031                 dest->w, dest->h, dest->x, dest->y));
1032 }
1033