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