bdfgrid.c

   1 /*
   2  * Copyright 2008 Department of Mathematical Sciences, New Mexico State University
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  17  * DEPARTMENT OF MATHEMATICAL SCIENCES OR NEW MEXICO STATE UNIVERSITY BE
  18  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
  19  * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  20  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #include "bdfP.h"
  24
  25 #ifndef MYABS
  26 #define MYABS(n) ((n) < 0 ? -(n) : (n))
  27 #endif
  28
  29 #undef MAX
  30 #define MAX(h, i) ((h) > (i) ? (h) : (i))
  31
  32 #undef MIN
  33 #define MIN(l, o) ((l) < (o) ? (l) : (o))
  34
  35 double _bdf_cos_tbl[360] = {
  36     0.000000, 0.999848, 0.999391, 0.998630, 0.997564, 0.996195,
  37     0.994522, 0.992546, 0.990268, 0.987688, 0.984808, 0.981627,
  38     0.978148, 0.974370, 0.970296, 0.965926, 0.961262, 0.956305,
  39     0.951057, 0.945519, 0.939693, 0.933580, 0.927184, 0.920505,
  40     0.913545, 0.906308, 0.898794, 0.891007, 0.882948, 0.874620,
  41     0.866025, 0.857167, 0.848048, 0.838671, 0.829038, 0.819152,
  42     0.809017, 0.798636, 0.788011, 0.777146, 0.766044, 0.754710,
  43     0.743145, 0.731354, 0.719340, 0.707107, 0.694658, 0.681998,
  44     0.669131, 0.656059, 0.642788, 0.629320, 0.615661, 0.601815,
  45     0.587785, 0.573576, 0.559193, 0.544639, 0.529919, 0.515038,
  46     0.500000, 0.484810, 0.469472, 0.453990, 0.438371, 0.422618,
  47     0.406737, 0.390731, 0.374607, 0.358368, 0.342020, 0.325568,
  48     0.309017, 0.292372, 0.275637, 0.258819, 0.241922, 0.224951,
  49     0.207912, 0.190809, 0.173648, 0.156434, 0.139173, 0.121869,
  50     0.104528, 0.087156, 0.069756, 0.052336, 0.034899, 0.017452,
  51     0.000000, -0.017452, -0.034899, -0.052336, -0.069756, -0.087156,
  52     -0.104528, -0.121869, -0.139173, -0.156434, -0.173648, -0.190809,
  53     -0.207912, -0.224951, -0.241922, -0.258819, -0.275637, -0.292372,
  54     -0.309017, -0.325568, -0.342020, -0.358368, -0.374607, -0.390731,
  55     -0.406737, -0.422618, -0.438371, -0.453990, -0.469472, -0.484810,
  56     -0.500000, -0.515038, -0.529919, -0.544639, -0.559193, -0.573576,
  57     -0.587785, -0.601815, -0.615661, -0.629320, -0.642788, -0.656059,
  58     -0.669131, -0.681998, -0.694658, -0.707107, -0.719340, -0.731354,
  59     -0.743145, -0.754710, -0.766044, -0.777146, -0.788011, -0.798636,
  60     -0.809017, -0.819152, -0.829038, -0.838671, -0.848048, -0.857167,
  61     -0.866025, -0.874620, -0.882948, -0.891007, -0.898794, -0.906308,
  62     -0.913545, -0.920505, -0.927184, -0.933580, -0.939693, -0.945519,
  63     -0.951057, -0.956305, -0.961262, -0.965926, -0.970296, -0.974370,
  64     -0.978148, -0.981627, -0.984808, -0.987688, -0.990268, -0.992546,
  65     -0.994522, -0.996195, -0.997564, -0.998630, -0.999391, -0.999848,
  66     -1.000000, -0.999848, -0.999391, -0.998630, -0.997564, -0.996195,
  67     -0.994522, -0.992546, -0.990268, -0.987688, -0.984808, -0.981627,
  68     -0.978148, -0.974370, -0.970296, -0.965926, -0.961262, -0.956305,
  69     -0.951057, -0.945519, -0.939693, -0.933580, -0.927184, -0.920505,
  70     -0.913545, -0.906308, -0.898794, -0.891007, -0.882948, -0.874620,
  71     -0.866025, -0.857167, -0.848048, -0.838671, -0.829038, -0.819152,
  72     -0.809017, -0.798636, -0.788011, -0.777146, -0.766044, -0.754710,
  73     -0.743145, -0.731354, -0.719340, -0.707107, -0.694658, -0.681998,
  74     -0.669131, -0.656059, -0.642788, -0.629320, -0.615661, -0.601815,
  75     -0.587785, -0.573576, -0.559193, -0.544639, -0.529919, -0.515038,
  76     -0.500000, -0.484810, -0.469472, -0.453990, -0.438371, -0.422618,
  77     -0.406737, -0.390731, -0.374607, -0.358368, -0.342020, -0.325568,
  78     -0.309017, -0.292372, -0.275637, -0.258819, -0.241922, -0.224951,
  79     -0.207912, -0.190809, -0.173648, -0.156434, -0.139173, -0.121869,
  80     -0.104528, -0.087156, -0.069756, -0.052336, -0.034899, -0.017452,
  81     -0.000000, 0.017452, 0.034899, 0.052336, 0.069756, 0.087156,
  82     0.104528, 0.121869, 0.139173, 0.156434, 0.173648, 0.190809,
  83     0.207912, 0.224951, 0.241922, 0.258819, 0.275637, 0.292372,
  84     0.309017, 0.325568, 0.342020, 0.358368, 0.374607, 0.390731,
  85     0.406737, 0.422618, 0.438371, 0.453990, 0.469472, 0.484810,
  86     0.500000, 0.515038, 0.529919, 0.544639, 0.559193, 0.573576,
  87     0.587785, 0.601815, 0.615661, 0.629320, 0.642788, 0.656059,
  88     0.669131, 0.681998, 0.694658, 0.707107, 0.719340, 0.731354,
  89     0.743145, 0.754710, 0.766044, 0.777146, 0.788011, 0.798636,
  90     0.809017, 0.819152, 0.829038, 0.838671, 0.848048, 0.857167,
  91     0.866025, 0.874620, 0.882948, 0.891007, 0.898794, 0.906308,
  92     0.913545, 0.920505, 0.927184, 0.933580, 0.939693, 0.945519,
  93     0.951057, 0.956305, 0.961262, 0.965926, 0.970296, 0.974370,
  94     0.978148, 0.981627, 0.984808, 0.987688, 0.990268, 0.992546,
  95     0.994522, 0.996195, 0.997564, 0.998630, 0.999391, 0.999848,
  96 };
  97
  98 double _bdf_sin_tbl[360] = {
  99     0.000000, 0.017452, 0.034899, 0.052336, 0.069756, 0.087156,
 100     0.104528, 0.121869, 0.139173, 0.156434, 0.173648, 0.190809,
 101     0.207912, 0.224951, 0.241922, 0.258819, 0.275637, 0.292372,
 102     0.309017, 0.325568, 0.342020, 0.358368, 0.374607, 0.390731,
 103     0.406737, 0.422618, 0.438371, 0.453990, 0.469472, 0.484810,
 104     0.500000, 0.515038, 0.529919, 0.544639, 0.559193, 0.573576,
 105     0.587785, 0.601815, 0.615661, 0.629320, 0.642788, 0.656059,
 106     0.669131, 0.681998, 0.694658, 0.707107, 0.719340, 0.731354,
 107     0.743145, 0.754710, 0.766044, 0.777146, 0.788011, 0.798636,
 108     0.809017, 0.819152, 0.829038, 0.838671, 0.848048, 0.857167,
 109     0.866025, 0.874620, 0.882948, 0.891007, 0.898794, 0.906308,
 110     0.913545, 0.920505, 0.927184, 0.933580, 0.939693, 0.945519,
 111     0.951057, 0.956305, 0.961262, 0.965926, 0.970296, 0.974370,
 112     0.978148, 0.981627, 0.984808, 0.987688, 0.990268, 0.992546,
 113     0.994522, 0.996195, 0.997564, 0.998630, 0.999391, 0.999848,
 114     1.000000, 0.999848, 0.999391, 0.998630, 0.997564, 0.996195,
 115     0.994522, 0.992546, 0.990268, 0.987688, 0.984808, 0.981627,
 116     0.978148, 0.974370, 0.970296, 0.965926, 0.961262, 0.956305,
 117     0.951057, 0.945519, 0.939693, 0.933580, 0.927184, 0.920505,
 118     0.913545, 0.906308, 0.898794, 0.891007, 0.882948, 0.874620,
 119     0.866025, 0.857167, 0.848048, 0.838671, 0.829038, 0.819152,
 120     0.809017, 0.798636, 0.788011, 0.777146, 0.766044, 0.754710,
 121     0.743145, 0.731354, 0.719340, 0.707107, 0.694658, 0.681998,
 122     0.669131, 0.656059, 0.642788, 0.629320, 0.615661, 0.601815,
 123     0.587785, 0.573576, 0.559193, 0.544639, 0.529919, 0.515038,
 124     0.500000, 0.484810, 0.469472, 0.453990, 0.438371, 0.422618,
 125     0.406737, 0.390731, 0.374607, 0.358368, 0.342020, 0.325568,
 126     0.309017, 0.292372, 0.275637, 0.258819, 0.241922, 0.224951,
 127     0.207912, 0.190809, 0.173648, 0.156434, 0.139173, 0.121869,
 128     0.104528, 0.087156, 0.069756, 0.052336, 0.034899, 0.017452,
 129     0.000000, -0.017452, -0.034899, -0.052336, -0.069756, -0.087156,
 130     -0.104528, -0.121869, -0.139173, -0.156434, -0.173648, -0.190809,
 131     -0.207912, -0.224951, -0.241922, -0.258819, -0.275637, -0.292372,
 132     -0.309017, -0.325568, -0.342020, -0.358368, -0.374607, -0.390731,
 133     -0.406737, -0.422618, -0.438371, -0.453990, -0.469472, -0.484810,
 134     -0.500000, -0.515038, -0.529919, -0.544639, -0.559193, -0.573576,
 135     -0.587785, -0.601815, -0.615661, -0.629320, -0.642788, -0.656059,
 136     -0.669131, -0.681998, -0.694658, -0.707107, -0.719340, -0.731354,
 137     -0.743145, -0.754710, -0.766044, -0.777146, -0.788011, -0.798636,
 138     -0.809017, -0.819152, -0.829038, -0.838671, -0.848048, -0.857167,
 139     -0.866025, -0.874620, -0.882948, -0.891007, -0.898794, -0.906308,
 140     -0.913545, -0.920505, -0.927184, -0.933580, -0.939693, -0.945519,
 141     -0.951057, -0.956305, -0.961262, -0.965926, -0.970296, -0.974370,
 142     -0.978148, -0.981627, -0.984808, -0.987688, -0.990268, -0.992546,
 143     -0.994522, -0.996195, -0.997564, -0.998630, -0.999391, -0.999848,
 144     -1.000000, -0.999848, -0.999391, -0.998630, -0.997564, -0.996195,
 145     -0.994522, -0.992546, -0.990268, -0.987688, -0.984808, -0.981627,
 146     -0.978148, -0.974370, -0.970296, -0.965926, -0.961262, -0.956305,
 147     -0.951057, -0.945519, -0.939693, -0.933580, -0.927184, -0.920505,
 148     -0.913545, -0.906308, -0.898794, -0.891007, -0.882948, -0.874620,
 149     -0.866025, -0.857167, -0.848048, -0.838671, -0.829038, -0.819152,
 150     -0.809017, -0.798636, -0.788011, -0.777146, -0.766044, -0.754710,
 151     -0.743145, -0.731354, -0.719340, -0.707107, -0.694658, -0.681998,
 152     -0.669131, -0.656059, -0.642788, -0.629320, -0.615661, -0.601815,
 153     -0.587785, -0.573576, -0.559193, -0.544639, -0.529919, -0.515038,
 154     -0.500000, -0.484810, -0.469472, -0.453990, -0.438371, -0.422618,
 155     -0.406737, -0.390731, -0.374607, -0.358368, -0.342020, -0.325568,
 156     -0.309017, -0.292372, -0.275637, -0.258819, -0.241922, -0.224951,
 157     -0.207912, -0.190809, -0.173648, -0.156434, -0.139173, -0.121869,
 158     -0.104528, -0.087156, -0.069756, -0.052336, -0.034899, -0.017452,
 159 };
 160
 161 double _bdf_tan_tbl[90] = {
 162     0.000000, 0.017455, 0.034921, 0.052408, 0.069927, 0.087489,
 163     0.105104, 0.122785, 0.140541, 0.158384, 0.176327, 0.194380,
 164     0.212557, 0.230868, 0.249328, 0.267949, 0.286745, 0.305731,
 165     0.324920, 0.344328, 0.363970, 0.383864, 0.404026, 0.424475,
 166     0.445229, 0.466308, 0.487733, 0.509525, 0.531709, 0.554309,
 167     0.577350, 0.600861, 0.624869, 0.649408, 0.674509, 0.700208,
 168     0.726543, 0.753554, 0.781286, 0.809784, 0.839100, 0.869287,
 169     0.900404, 0.932515, 0.965689, 1.000000, 1.035530, 1.072369,
 170     1.110613, 1.150368, 1.191754, 1.234897, 1.279942, 1.327045,
 171     1.376382, 1.428148, 1.482561, 1.539865, 1.600335, 1.664279,
 172     1.732051, 1.804048, 1.880726, 1.962611, 2.050304, 2.144507,
 173     2.246037, 2.355852, 2.475087, 2.605089, 2.747477, 2.904211,
 174     3.077684, 3.270853, 3.487414, 3.732051, 4.010781, 4.331476,
 175     4.704630, 5.144554, 5.671282, 6.313752, 7.115370, 8.144346,
 176     9.514364, 11.430052, 14.300666, 19.081137, 28.636253, 57.289962,
 177 };
 178
 179 /*
 180  * Determine the actual ink bounds.
 181  */
 182 static int
 183 _bdf_grid_ink_bounds(bdf_glyph_grid_t *grid, short *x, short *y,
 184                      short *width, short *height)
 185 {
 186     short bx, by, bwd, bht, minx, maxx, miny, maxy, dx, dy;
 187     unsigned short bpr, ink, sel, col;
 188     unsigned char *bmap, *masks;
 189
 190     masks = 0;
 191     switch (grid->bpp) {
 192       case 1: masks = bdf_onebpp; break;
 193       case 2: masks = bdf_twobpp; break;
 194       case 4: masks = bdf_fourbpp; break;
 195       case 8: masks = bdf_eightbpp; break;
 196     }
 197
 198     if (grid->sel.width != 0 && grid->sel.height != 0) {
 199         sel = 1;
 200         bx = by = 0;
 201         bwd = grid->sel.width;
 202         bht = grid->sel.height;
 203         bmap = grid->sel.bitmap;
 204     } else {
 205         sel = 0;
 206         bx = grid->glyph_x;
 207         by = grid->glyph_y;
 208         bwd = grid->glyph_bbx.width;
 209         bht = grid->glyph_bbx.height;
 210         bmap = grid->bitmap;
 211     }
 212     maxx = maxy = 0;
 213     minx = bx + bwd;
 214     miny = by + bht;
 215
 216     bpr = ((bwd * grid->bpp) + 7) >> 3;
 217     ink = 0;
 218
 219     bwd += bx;
 220     bht += by;
 221     for (dy = by; dy < bht; dy++) {
 222         for (col = bx * grid->bpp, dx = bx; dx < bwd; dx++, col += grid->bpp) {
 223             if (bmap[(dy * bpr) + (col >> 3)] & masks[(col & 7) / grid->bpp]) {
 224                 ink = 1;
 225                 minx = MIN(minx, dx);
 226                 miny = MIN(miny, dy);
 227                 maxx = MAX(maxx, dx);
 228                 maxy = MAX(maxy, dy);
 229             }
 230         }
 231     }
 232
 233     *x = minx + ((sel) ? grid->sel.x : 0);
 234     *y = miny + ((sel) ? grid->sel.y : 0);
 235     if (ink == 0)
 236       *width = *height = 0;
 237     else {
 238         *width = (maxx - minx) + 1;
 239         *height = (maxy - miny) + 1;
 240     }
 241     return ink;
 242 }
 243
 244 /**************************************************************************
 245  *
 246  * Glyph grid create and destroy functions.
 247  *
 248  **************************************************************************/
 249
 250 /*
 251  * Make a glyph grid with the glyph bitmap set in the bitmap.
 252  */
 253 bdf_glyph_grid_t *
 254 bdf_make_glyph_grid(bdf_font_t *font, int code, int unencoded)
 255 {
 256     unsigned short si, di, col, colx, byte;
 257     short ht, as, ds, gsize, bpr, x, y, nx, ny;
 258     long l, r, m;
 259     bdf_glyph_grid_t *gr;
 260     bdf_glyph_t *gl, *glp;
 261     bdf_property_t *p;
 262     unsigned char *masks;
 263     char name[24];
 264
 265 #if 0
 266     if (font == 0)
 267       return 0;
 268 #endif
 269
 270     /*
 271      * Allocate the grid and initialize it.
 272      */
 273     gr = (bdf_glyph_grid_t *) malloc(sizeof(bdf_glyph_grid_t));
 274     (void) memset((char *) gr, 0, sizeof(bdf_glyph_grid_t));
 275
 276     /*
 277      * Set the encoding and the unencoded flag.
 278      */
 279     gr->bpp = (font) ? font->bpp : 1;
 280     gr->encoding = code;
 281     gr->unencoded = unencoded;
 282
 283     /*
 284      * Set the glyph grid spacing.
 285      */
 286     gr->spacing = (font) ? font->spacing : BDF_CHARCELL;
 287
 288     /*
 289      * Set the point size and resolutions.
 290      */
 291     if (font) {
 292         gr->point_size = font->point_size;
 293         gr->resolution_x = font->resolution_x;
 294         gr->resolution_y = font->resolution_y;
 295     } else {
 296         gr->point_size = 12;
 297         gr->resolution_x = gr->resolution_y = 100;
 298     }
 299
 300     /*
 301      * Set the CAP_HEIGHT and X_HEIGHT if they exist in the font.
 302      */
 303     if (font) {
 304         if ((p = bdf_get_font_property(font, "CAP_HEIGHT")) != 0)
 305           gr->cap_height = (short) p->value.int32;
 306         if ((p = bdf_get_font_property(font, "X_HEIGHT")) != 0)
 307           gr->x_height = (short) p->value.int32;
 308     }
 309
 310     masks = 0;
 311     switch (gr->bpp) {
 312       case 1: masks = bdf_onebpp; break;
 313       case 2: masks = bdf_twobpp; break;
 314       case 4: masks = bdf_fourbpp; break;
 315       case 8: masks = bdf_eightbpp; break;
 316     }
 317
 318     /*
 319      * Copy the font bounding box into the grid.
 320      */
 321     if (font)
 322       (void) memcpy((char *) &gr->font_bbx, (char *) &font->bbx,
 323                     sizeof(bdf_bbx_t));
 324     else {
 325         gr->font_bbx.height = 17;
 326         gr->font_bbx.width = 8;
 327         gr->font_bbx.descent = 8;
 328         gr->font_bbx.ascent = 9;
 329         gr->font_bbx.y_offset = -8;
 330     }
 331
 332
 333     if (font) {
 334         if (unencoded) {
 335             gl = font->unencoded;
 336             r = font->unencoded_used;
 337         } else {
 338             gl = font->glyphs;
 339             r = font->glyphs_used;
 340         }
 341     } else {
 342         gl = 0;
 343         r = 0;
 344     }
 345
 346     /*
 347      * Locate the specified glyph using a simple binary search.
 348      */
 349     glp = 0;
 350     if (r > 0) {
 351         for (l = 0; r >= l; ) {
 352             m = (l + r) >> 1;
 353             glp = gl + m;
 354             if (glp->encoding == code)
 355               break;
 356             if (glp->encoding > code)
 357               r = m - 1;
 358             else if (glp->encoding < code)
 359               l = m + 1;
 360             glp = 0;
 361         }
 362     }
 363
 364     ht = gr->font_bbx.height;
 365     as = gr->font_bbx.ascent;
 366     ds = gr->font_bbx.descent;
 367
 368     /*
 369      * 1. Determine width and height needed from the largest of the
 370      *    width or height.
 371      */
 372     gr->grid_width = gr->grid_height =
 373         MAX(gr->font_bbx.width, gr->font_bbx.height);
 374
 375     /*
 376      * 2. Make sure the grid is at least a square of the largest of the width
 377      *    or height of the glyph itself to allow room for transformations.
 378      */
 379     if (glp != 0) {
 380         /*
 381          * Set the glyph name and other metrics.
 382          */
 383         if (glp->name) {
 384             gr->name = (char *) malloc(strlen(glp->name) + 1);
 385             (void) memcpy(gr->name, glp->name, strlen(glp->name) + 1);
 386         } else {
 387             sprintf(name, "char%d", code);
 388             gr->name = (char *) malloc(strlen(name) + 1);
 389             (void) memcpy(gr->name, name, strlen(name) + 1);
 390         }
 391         gr->dwidth = glp->dwidth;
 392
 393         /*
 394          * Copy the glyph bounding box into the grid.
 395          */
 396         (void) memcpy((char *) &gr->glyph_bbx, (char *) &glp->bbx,
 397                       sizeof(bdf_bbx_t));
 398
 399         if (glp->bbx.height < glp->bbx.ascent + glp->bbx.descent)
 400           gsize = glp->bbx.ascent + glp->bbx.descent;
 401         else
 402           gsize = glp->bbx.height;
 403
 404         /*
 405          * Figure the maximum of the glyph width and height.
 406          */
 407         gsize = MAX(gr->glyph_bbx.width, gsize);
 408
 409         /*
 410          * If either the grid width or grid height is less than the
 411          * grid size just determined, then adjust them to the new grid size.
 412          */
 413         gr->grid_width = MAX(gr->grid_width, gsize);
 414         gr->grid_height = MAX(gr->grid_height, gsize);
 415     } else {
 416         /*
 417          * The glyph doesn't exist, so make up a name for it.
 418          */
 419         if (unencoded)
 420           sprintf(name, "unencoded%d", code);
 421         else
 422           sprintf(name, "char%d", code);
 423         gr->name = (char *) malloc(strlen(name) + 1);
 424         (void) memcpy(gr->name, name, strlen(name) + 1);
 425     }
 426
 427     /*
 428      * If the font has character-cell or mono spacing, make sure the grid
 429      * device width is set to the width stored in the font.
 430      */
 431     if (gr->spacing != BDF_PROPORTIONAL)
 432       gr->dwidth = (font) ? font->monowidth : 8;
 433
 434     /*
 435      * Determine the vertical origin based on the font bounding box.
 436      */
 437     if (ht >= as + ds)
 438       gr->base_y = (((gr->grid_height >> 1) - (ht >> 1)) + ht) - ds;
 439     else
 440       gr->base_y = ((gr->grid_height >> 1) - ((as + ds) >> 1)) + as;
 441
 442     /*
 443      * The final adjust is to check to see if the glyph positioned relative to
 444      * the baseline would cause the grid to change size.  This sometimes
 445      * happens in fonts that have incorrect metrics.
 446      */
 447     if (gr->base_y + gr->glyph_bbx.descent > gr->grid_height) {
 448         gsize = gr->base_y + gr->glyph_bbx.descent;
 449         gr->grid_width = MAX(gsize, gr->grid_width);
 450         gr->grid_height = MAX(gsize, gr->grid_height);
 451     }
 452
 453     /*
 454      * Determine the horizontal origin based on the font bounding box and
 455      * centered within the grid.
 456      */
 457     gr->base_x = (gr->grid_width >> 1) - (gr->font_bbx.width >> 1);
 458     if (gr->font_bbx.x_offset < 0)
 459       gr->base_x += MYABS(gr->font_bbx.x_offset);
 460
 461     /*
 462      * Allocate double the storage needed for the grid bitmap.  The extra
 463      * storage will be used for transformations.
 464      */
 465     gr->bytes = ((((gr->grid_width * gr->bpp) + 7) >> 3) *
 466                  gr->grid_height) << 1;
 467     gr->bitmap = (unsigned char *) malloc(gr->bytes);
 468     (void) memset((char *) gr->bitmap, 0, gr->bytes);
 469
 470     /*
 471      * Initialize the top-left coordinates of the glyph to the baseline
 472      * coordinates.
 473      */
 474     gr->glyph_x = gr->base_x;
 475     gr->glyph_y = gr->base_y;
 476
 477     /*
 478      * If the glyph was not found, simply return the empty grid.
 479      */
 480     if (glp == 0)
 481       return gr;
 482
 483     /*
 484      * Determine the top-left coordinates of the glyph with respect to the
 485      * baseline coordinates.
 486      */
 487     gr->glyph_x = nx = gr->base_x + gr->glyph_bbx.x_offset;
 488     gr->glyph_y = ny = gr->base_y - gr->glyph_bbx.ascent;
 489
 490     /*
 491      * Now copy the glyph bitmap to the appropriate location in the grid.
 492      */
 493     bpr = ((gr->glyph_bbx.width * gr->bpp) + 7) >> 3;
 494     gsize = ((gr->grid_width * gr->bpp) + 7) >> 3;
 495     for (y = 0; y < gr->glyph_bbx.height; y++, ny++) {
 496         for (colx = nx * gr->bpp, col = x = 0; x < gr->glyph_bbx.width;
 497              x++, col += gr->bpp, colx += gr->bpp) {
 498             si = (col & 7) / gr->bpp;
 499             byte = glp->bitmap[(y * bpr) + (col >> 3)] & masks[si];
 500             if (byte) {
 501                 di = (colx & 7) / gr->bpp;
 502                 if (di < si)
 503                   byte <<= (si - di) * gr->bpp;
 504                 else if (di > si)
 505                   byte >>= (di - si) * gr->bpp;
 506                 gr->bitmap[(ny * gsize) + (colx >> 3)] |= byte;
 507             }
 508         }
 509     }
 510
 511     /*
 512      * Always crop the glyph to the ink bounds before editing.
 513      */
 514     bdf_grid_crop(gr, 0);
 515
 516     /*
 517      * Copy any Unicode mappings that might be present for this glyph, even if
 518      * it is a proportional font.  It might be changed to a character cell or
 519      * monowidth font later.
 520      */
 521     gr->unicode.map_size = glp->unicode.map_size;
 522     gr->unicode.map_used = glp->unicode.map_used;
 523     gr->unicode.map = (unsigned char *)
 524         malloc(sizeof(unsigned char) * gr->unicode.map_size);
 525     (void) memcpy((char *) gr->unicode.map, (char *) glp->unicode.map,
 526                   sizeof(unsigned char) * gr->unicode.map_used);
 527
 528     /*
 529      * Return the grid.
 530      */
 531     return gr;
 532 }
 533
 534 void
 535 bdf_free_glyph_grid(bdf_glyph_grid_t *grid)
 536 {
 537     if (grid == 0)
 538       return;
 539
 540     if (grid->name != 0)
 541       free(grid->name);
 542     if (grid->bytes > 0)
 543       free((char *) grid->bitmap);
 544     if (grid->sel.bytes > 0)
 545       free((char *) grid->sel.bitmap);
 546     if (grid->unicode.map_size > 0)
 547       free((char *) grid->unicode.map);
 548     free((char *) grid);
 549 }
 550
 551 /**************************************************************************
 552  *
 553  * Glyph grid resize functions.
 554  *
 555  **************************************************************************/
 556
 557 /*
 558  * Enlarge the grid without affecting the font or glyph metrics.
 559  */
 560 int
 561 bdf_grid_enlarge(bdf_glyph_grid_t *grid, unsigned short width,
 562                  unsigned short height)
 563 {
 564     unsigned short si, di, col, colx, byte;
 565     short ht, wd, as, ds, x, y, nx, ny;
 566     unsigned short gwd, ght, bytes, obpr, nbpr, gsize;
 567     unsigned char *bitmap, *masks;
 568
 569     if (grid == 0 || (width < grid->grid_width && height < grid->grid_height))
 570       return 0;
 571
 572     masks = 0;
 573     switch (grid->bpp) {
 574       case 1: masks = bdf_onebpp; break;
 575       case 2: masks = bdf_twobpp; break;
 576       case 4: masks = bdf_fourbpp; break;
 577       case 8: masks = bdf_eightbpp; break;
 578     }
 579
 580     ht = height;
 581     as = grid->font_bbx.ascent;
 582     ds = grid->font_bbx.descent;
 583
 584     gwd = MAX(width, grid->grid_width);
 585     ght = MAX(height, grid->grid_height);
 586     gsize = MAX(gwd, ght);
 587
 588     nbpr = ((gsize * grid->bpp) + 7) >> 3;
 589     bytes = (nbpr * ght) << 1;
 590     bitmap = (unsigned char *) malloc(bytes);
 591     (void) memset((char *) bitmap, 0, bytes);
 592
 593     /*
 594      * Determine the new baseline.
 595      */
 596     if (ht >= as + ds)
 597       grid->base_y = (((ght >> 1) - (ht >> 1)) + ht) - ds;
 598     else
 599       grid->base_y = ((ght >> 1) - ((as + ds) >> 1)) + as;
 600
 601     grid->base_x = (gwd >> 1) - (grid->font_bbx.width >> 1);
 602     if (grid->font_bbx.x_offset < 0)
 603       grid->base_x += MYABS(grid->font_bbx.x_offset);
 604
 605     nx = grid->base_x + grid->glyph_bbx.x_offset;
 606     ny = grid->base_y - grid->glyph_bbx.ascent;
 607
 608     /*
 609      * Now copy the bitmap into the new storage base on the new metrics
 610      * values.
 611      */
 612     obpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
 613     wd = grid->glyph_x + grid->glyph_bbx.width;
 614     ht = grid->glyph_y + grid->glyph_bbx.height;
 615     for (y = grid->glyph_y; y < ht; y++, ny++) {
 616         col = grid->glyph_x * grid->bpp;
 617         colx = nx * grid->bpp;
 618         for (x = grid->glyph_x; x < wd;
 619              x++, col += grid->bpp, colx += grid->bpp) {
 620             si = (col & 7) / grid->bpp;
 621             byte = grid->bitmap[(y * obpr) + (col >> 3)] & masks[si];
 622             if (byte) {
 623                 di = (colx & 7) / grid->bpp;
 624                 if (di < si)
 625                   byte <<= (si - di) * grid->bpp;
 626                 else if (di > si)
 627                   byte >>= (di - si) * grid->bpp;
 628                 bitmap[(ny * nbpr) + (colx >> 3)] |= byte;
 629             }
 630         }
 631     }
 632
 633     /*
 634      * Adjust the glyph coordinates.
 635      */
 636     grid->glyph_x = grid->base_x + grid->glyph_bbx.x_offset;
 637     grid->glyph_y = grid->base_y - grid->glyph_bbx.ascent;
 638
 639     /*
 640      * Get rid of the old grid bitmap and replace it with the new one.
 641      */
 642     free((char *) grid->bitmap);
 643     grid->bytes = bytes;
 644     grid->bitmap = bitmap;
 645
 646     /*
 647      * Update the new grid width and height.
 648      */
 649     grid->grid_width = grid->grid_height = gsize;
 650
 651     /*
 652      * Always mark the grid as being modified on a resize.
 653      */
 654     grid->modified = 1;
 655
 656     return 1;
 657 }
 658
 659 /*
 660  * Change the font bounding box values and resize the grid bitmap if
 661  * necessary.
 662  */
 663 int
 664 bdf_grid_resize(bdf_glyph_grid_t *grid, bdf_metrics_t *metrics)
 665 {
 666     int changed;
 667     unsigned short si, di, col, colx, byte;
 668     short ht, wd, as, ds, x, y, nx, ny;
 669     unsigned short gwd, ght, bytes, obpr, nbpr, gsize;
 670     unsigned char *bitmap, *masks;
 671
 672     changed = 0;
 673
 674     if (grid == 0 || metrics == 0)
 675       return changed;
 676
 677     masks = 0;
 678     switch (grid->bpp) {
 679       case 1: masks = bdf_onebpp; break;
 680       case 2: masks = bdf_twobpp; break;
 681       case 4: masks = bdf_fourbpp; break;
 682       case 8: masks = bdf_eightbpp; break;
 683     }
 684
 685     /*
 686      * Create new grid bitmaps in preparation for the various metrics changing.
 687      */
 688     if (metrics->width > grid->grid_width ||
 689         metrics->height > grid->grid_height) {
 690         changed = 1;
 691
 692         ht = metrics->height;
 693         as = metrics->ascent;
 694         ds = metrics->descent;
 695
 696         gwd = MAX(metrics->width, grid->grid_width);
 697         ght = MAX(metrics->height, grid->grid_height);
 698
 699         /*
 700          * Get the larger of the two dimensions.
 701          */
 702         gsize = MAX(gwd, ght);
 703
 704         nbpr = ((gsize * grid->bpp) + 7) >> 3;
 705         bytes = (nbpr * gsize) << 1;
 706         bitmap = (unsigned char *) malloc(bytes);
 707         (void) memset((char *) bitmap, 0, bytes);
 708
 709         /*
 710          * Determine the new baseline.
 711          */
 712         if (ht >= as + ds)
 713           grid->base_y = (((ght >> 1) - (ht >> 1)) + ht) - ds;
 714         else
 715           grid->base_y = ((ght >> 1) - ((as + ds) >> 1)) + as;
 716
 717         grid->base_x = (gwd >> 1) - (metrics->width >> 1);
 718         if (metrics->x_offset < 0)
 719           grid->base_x += MYABS(metrics->x_offset);
 720
 721         nx = grid->base_x + grid->glyph_bbx.x_offset;
 722         ny = grid->base_y - grid->glyph_bbx.ascent;
 723
 724         /*
 725          * Now copy the bitmap into the new storage base on the new metrics
 726          * values.
 727          */
 728         obpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
 729         wd = grid->glyph_x + grid->glyph_bbx.width;
 730         ht = grid->glyph_y + grid->glyph_bbx.height;
 731         for (y = grid->glyph_y; y < ht; y++, ny++) {
 732             col = grid->glyph_x * grid->bpp;
 733             colx = nx * grid->bpp;
 734             for (x = grid->glyph_x; x < wd;
 735                  x++, col += grid->bpp, colx += grid->bpp) {
 736                 si = (col & 7) / grid->bpp;
 737                 byte = grid->bitmap[(y * obpr) + (col >> 3)] & masks[si];
 738                 if (byte) {
 739                     di = (colx & 7) / grid->bpp;
 740                     if (di < si)
 741                       byte <<= (si - di) * grid->bpp;
 742                     else if (di > si)
 743                       byte >>= (di - si) * grid->bpp;
 744                     bitmap[(ny * nbpr) + (colx >> 3)] |= byte;
 745                 }
 746             }
 747         }
 748
 749         /*
 750          * Adjust the glyph coordinates.
 751          */
 752         grid->glyph_x = grid->base_x + grid->glyph_bbx.x_offset;
 753         grid->glyph_y = grid->base_y - grid->glyph_bbx.ascent;
 754
 755         /*
 756          * Get rid of the old grid bitmap and replace it with the new one.
 757          */
 758         free((char *) grid->bitmap);
 759         grid->bytes = bytes;
 760         grid->bitmap = bitmap;
 761
 762         /*
 763          * Update the new grid width and height.
 764          */
 765         grid->grid_width = grid->grid_height = gsize;
 766
 767         /*
 768          * Copy the metrics info into the font bounding box.
 769          */
 770         grid->font_bbx.width = metrics->width;
 771         grid->font_bbx.x_offset = metrics->x_offset;
 772         grid->font_bbx.height = metrics->height;
 773         grid->font_bbx.ascent = metrics->ascent;
 774         grid->font_bbx.descent = metrics->descent;
 775         grid->font_bbx.y_offset = metrics->y_offset;
 776     } else {
 777         /*
 778          * The grid does not need to resized, but the baseline must
 779          * be recalculated and the bitmap copied again.
 780          */
 781         bytes = grid->bytes >> 1;
 782         bitmap = grid->bitmap + bytes;
 783         (void) memset((char *) bitmap, 0, bytes);
 784
 785         ht = metrics->height;
 786         as = metrics->ascent;
 787         ds = metrics->descent;
 788
 789         gwd = grid->grid_width;
 790         ght = grid->grid_height;
 791
 792         /*
 793          * Determine the new baseline.
 794          */
 795         if (ht >= as + ds)
 796           grid->base_y = (((ght >> 1) - (ht >> 1)) + ht) - ds;
 797         else
 798           grid->base_y = ((ght >> 1) - ((as + ds) >> 1)) + as;
 799
 800         grid->base_x = (gwd >> 1) - (metrics->width >> 1);
 801         if (metrics->x_offset < 0)
 802           grid->base_x += MYABS(metrics->x_offset);
 803
 804         nx = grid->base_x + grid->glyph_bbx.x_offset;
 805         ny = grid->base_y - grid->glyph_bbx.ascent;
 806
 807         wd = grid->glyph_x + grid->glyph_bbx.width;
 808         ht = grid->glyph_y + grid->glyph_bbx.height;
 809
 810         obpr = nbpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
 811         for (y = grid->glyph_y; y < ht; y++, ny++) {
 812             col = grid->glyph_x * grid->bpp;
 813             colx = nx * grid->bpp;
 814             for (x = grid->glyph_x; x < wd;
 815                  x++, col += grid->bpp, colx += grid->bpp) {
 816                 si = (col & 7) / grid->bpp;
 817                 byte = grid->bitmap[(y * obpr) + (col >> 3)] & masks[si];
 818                 if (byte) {
 819                     di = (colx & 7) / grid->bpp;
 820                     if (di < si)
 821                       byte <<= (si - di) * grid->bpp;
 822                     else if (di > si)
 823                       byte >>= (di - si) * grid->bpp;
 824                     bitmap[(ny * nbpr) + (colx >> 3)] |= byte;
 825                 }
 826             }
 827         }
 828
 829         /*
 830          * Copy the adjusted bitmap back into the main area.
 831          */
 832         (void) memcpy((char *) grid->bitmap, (char *) bitmap, bytes);
 833
 834         /*
 835          * Adjust the glyph coordinates.
 836          */
 837         grid->glyph_x = grid->base_x + grid->glyph_bbx.x_offset;
 838         grid->glyph_y = grid->base_y - grid->glyph_bbx.ascent;
 839
 840         /*
 841          * Copy the metrics info into the font bounding box.
 842          */
 843         grid->font_bbx.width = metrics->width;
 844         grid->font_bbx.x_offset = metrics->x_offset;
 845         grid->font_bbx.height = metrics->height;
 846         grid->font_bbx.ascent = metrics->ascent;
 847         grid->font_bbx.descent = metrics->descent;
 848         grid->font_bbx.y_offset = metrics->y_offset;
 849     }
 850
 851     /*
 852      * If the font is not proportional, make sure the device width is adjusted
 853      * to meet the new font bounding box.
 854      */
 855     if (changed && grid->spacing != BDF_PROPORTIONAL)
 856       grid->dwidth = grid->font_bbx.width;
 857
 858     /*
 859      * Always mark the grid as being modified on a resize.
 860      */
 861     grid->modified = 1;
 862
 863     return changed;
 864 }
 865
 866 int
 867 bdf_grid_crop(bdf_glyph_grid_t *grid, int grid_modified)
 868 {
 869     int cropped;
 870     short x, y, delta, maxx, minx, maxy, miny, col;
 871     unsigned short bpr;
 872     unsigned char *masks;
 873
 874     cropped = 0;
 875     if (grid == 0)
 876       return cropped;
 877
 878     masks = 0;
 879     switch (grid->bpp) {
 880       case 1: masks = bdf_onebpp; break;
 881       case 2: masks = bdf_twobpp; break;
 882       case 4: masks = bdf_fourbpp; break;
 883       case 8: masks = bdf_eightbpp; break;
 884     }
 885
 886     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
 887
 888     maxx = maxy = -1;
 889     minx = miny = grid->grid_width;
 890     for (y = 0; y < grid->grid_height; y++) {
 891         for (col = x = 0; x < grid->grid_width; x++, col += grid->bpp) {
 892             if (grid->bitmap[(y * bpr) + (col >> 3)] &
 893                 masks[(col & 7) / grid->bpp]) {
 894                 minx = MIN(minx, x);
 895                 maxx = MAX(maxx, x);
 896                 miny = MIN(miny, y);
 897                 maxy = MAX(maxy, y);
 898             }
 899         }
 900     }
 901
 902     /*
 903      * Handle an empty bitmap as a special case.
 904      */
 905     if (maxx == -1) {
 906         /*
 907          * If the glyph bounding box indicated something was there originally,
 908          * then indicate that it was cropped.
 909          */
 910         if (grid->glyph_bbx.width != 0 || grid->glyph_bbx.height != 0)
 911           cropped = 1;
 912         (void) memset((char *) &grid->glyph_bbx, 0, sizeof(bdf_bbx_t));
 913         grid->glyph_x = grid->base_x;
 914         grid->glyph_y = grid->base_y;
 915         if (cropped && grid_modified)
 916           grid->modified = 1;
 917         return cropped;
 918     }
 919
 920     /*
 921      * Increment the max points so width and height calculations won't go
 922      * wrong.
 923      */
 924     maxx++;
 925     maxy++;
 926
 927     if (minx != grid->glyph_x) {
 928         cropped = 1;
 929         delta = minx - grid->glyph_x;
 930         grid->glyph_x += delta;
 931         grid->glyph_bbx.x_offset += delta;
 932     }
 933     if (maxx - minx != grid->glyph_bbx.width) {
 934         cropped = 1;
 935         delta = (maxx - minx) - grid->glyph_bbx.width;
 936         grid->glyph_bbx.width += delta;
 937     }
 938
 939     if (miny != grid->glyph_y) {
 940         cropped = 1;
 941         delta = miny - grid->glyph_y;
 942         grid->glyph_y += delta;
 943         grid->glyph_bbx.y_offset =
 944             grid->base_y - (grid->glyph_y + (maxy - miny));
 945     }
 946     if (maxy - miny != grid->glyph_bbx.height) {
 947         cropped = 1;
 948         delta = (maxy - miny) - grid->glyph_bbx.height;
 949         grid->glyph_bbx.height += delta;
 950         grid->glyph_bbx.y_offset =
 951             grid->base_y - (grid->glyph_y + (maxy - miny));
 952         grid->glyph_bbx.ascent =
 953             grid->glyph_bbx.height + grid->glyph_bbx.y_offset;
 954         grid->glyph_bbx.descent = -grid->glyph_bbx.y_offset;
 955     }
 956
 957     /*
 958      * Indicate that the grid was modified if the glyph had to be cropped.
 959      */
 960     if (cropped && grid_modified)
 961       grid->modified = 1;
 962
 963     return cropped;
 964 }
 965
 966 /**************************************************************************
 967  *
 968  * Glyph grid pixel functions.
 969  *
 970  **************************************************************************/
 971
 972 int
 973 bdf_grid_set_pixel(bdf_glyph_grid_t *grid, short x, short y, int val)
 974 {
 975     unsigned short si, di, dx;
 976     int set, bpr, delta;
 977     unsigned char *masks;
 978
 979     set = 0;
 980
 981     if (grid == 0 || x < 0 || x >= grid->grid_width ||
 982         y < 0 || y >= grid->grid_height)
 983       return set;
 984
 985     si = 0;
 986     masks = 0;
 987     switch (grid->bpp) {
 988       case 1: masks = bdf_onebpp; si = 7; break;
 989       case 2: masks = bdf_twobpp; si = 3; break;
 990       case 4: masks = bdf_fourbpp; si = 1; break;
 991       case 8: masks = bdf_eightbpp; si = 0; break;
 992     }
 993
 994     /*
 995      * Remove any unused bits from the value.
 996      */
 997     val &= masks[si];
 998
 999     dx = x * grid->bpp;
1000     di = (dx & 7) / grid->bpp;
1001
1002     /*
1003      * Shift up the value to the appropriate place if necessary.
1004      */
1005     if (di < si)
1006       val <<= (si - di) * grid->bpp;
1007
1008     /*
1009      * Determine the bytes-per-row.
1010      */
1011     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
1012
1013     /*
1014      * If the pixel is already set, simply return with an indication that
1015      * nothing changed.
1016      */
1017     if ((grid->bitmap[(y * bpr) + (dx >> 3)] & masks[di]) == val)
1018       return set;
1019
1020     /*
1021      * Set the bit.
1022      */
1023     set = 1;
1024
1025     /*
1026      * Clear the bits that will take the new value.
1027      */
1028     grid->bitmap[(y * bpr) + (dx >> 3)] &= ~masks[di];
1029     grid->bitmap[(y * bpr) + (dx >> 3)] |= val;
1030
1031     /*
1032      * Adjust the glyph bounding box.
1033      */
1034     if (x < grid->glyph_x) {
1035         delta = grid->glyph_x - x;
1036         grid->glyph_bbx.width += delta;
1037         grid->glyph_bbx.x_offset -= delta;
1038         if (grid->spacing == BDF_PROPORTIONAL)
1039           grid->dwidth = grid->glyph_bbx.width + grid->glyph_bbx.x_offset;
1040         grid->glyph_x -= delta;
1041     } else if (x >= grid->glyph_x + grid->glyph_bbx.width) {
1042         delta = x - (grid->glyph_x + grid->glyph_bbx.width) + 1;
1043         grid->glyph_bbx.width += delta;
1044         if (grid->spacing == BDF_PROPORTIONAL)
1045           grid->dwidth = grid->glyph_bbx.width + grid->glyph_bbx.x_offset;
1046     }
1047     if (y < grid->glyph_y) {
1048         delta = grid->glyph_y - y;
1049         grid->glyph_bbx.ascent += delta;
1050         grid->glyph_bbx.height += delta;
1051         grid->glyph_y -= delta;
1052     } else if (y >= grid->glyph_y + grid->glyph_bbx.height) {
1053         delta = y - (grid->glyph_y + grid->glyph_bbx.height) + 1;
1054         grid->glyph_bbx.descent += delta;
1055         grid->glyph_bbx.height += delta;
1056         grid->glyph_bbx.y_offset = -grid->glyph_bbx.descent;
1057     }
1058
1059     /*
1060      * Indicate that the glyph was modified.
1061      */
1062     grid->modified = 1;
1063
1064     return set;
1065 }
1066
1067 int
1068 bdf_grid_clear_pixel(bdf_glyph_grid_t *grid, short x, short y)
1069 {
1070     int cleared, bpr;
1071     short delta, maxx, minx, maxy, miny, wd, ht;
1072     unsigned short di, dx;
1073     unsigned char *masks;
1074
1075     cleared = 0;
1076
1077     if (grid == 0 || x < 0 || x >= grid->grid_width ||
1078         y < 0 || y >= grid->grid_height)
1079       return cleared;
1080
1081     masks = 0;
1082     switch (grid->bpp) {
1083       case 1: masks = bdf_onebpp; break;
1084       case 2: masks = bdf_twobpp; break;
1085       case 4: masks = bdf_fourbpp; break;
1086       case 8: masks = bdf_eightbpp; break;
1087     }
1088
1089     /*
1090      * Determine the bytes-per-row.
1091      */
1092     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
1093
1094     dx = x * grid->bpp;
1095     di = (dx & 7) / grid->bpp;
1096
1097     /*
1098      * If the bit is already clear, simply return with an indication that
1099      * nothing changed.
1100      */
1101     if (!(grid->bitmap[(y * bpr) + (dx >> 3)] & masks[di]))
1102       return cleared;
1103
1104     /*
1105      * Clear the bit.
1106      */
1107     cleared = 1;
1108     grid->bitmap[(y * bpr) + (dx >> 3)] &= ~masks[di];
1109
1110     /*
1111      * Determine the new min and max values.
1112      */
1113     maxx = maxy = 0;
1114     minx = miny = 32767;
1115
1116     wd = grid->glyph_x + grid->glyph_bbx.width;
1117     ht = grid->glyph_y + grid->glyph_bbx.height;
1118
1119     for (y = grid->glyph_y; y < ht; y++) {
1120         dx = grid->glyph_x * grid->bpp;
1121         for (x = grid->glyph_x; x < wd; x++, dx += grid->bpp) {
1122             di = (dx & 7) / grid->bpp;
1123             if (grid->bitmap[(y * bpr) + (dx >> 3)] & masks[di]) {
1124                 minx = MIN(minx, x);
1125                 maxx = MAX(maxx, x);
1126                 miny = MIN(miny, y);
1127                 maxy = MAX(maxy, y);
1128             }
1129         }
1130     }
1131
1132     /*
1133      * If this call clears the last bit in the image, set the glyph origin
1134      * to the base and return.
1135      */
1136     if (maxx == 0) {
1137         grid->glyph_x = grid->base_x;
1138         grid->glyph_y = grid->base_y;
1139         if (grid->spacing == BDF_PROPORTIONAL)
1140           grid->dwidth = 0;
1141         (void) memset((char *) &grid->glyph_bbx, 0, sizeof(grid->glyph_bbx));
1142         grid->modified = 1;
1143         return cleared;
1144     }
1145
1146     /*
1147      * Figure out the left and right bearing changes.
1148      */
1149     if (minx > grid->glyph_x) {
1150         delta = minx - grid->glyph_x;
1151         grid->glyph_bbx.width -= delta;
1152         grid->glyph_bbx.x_offset += delta;
1153         if (grid->spacing == BDF_PROPORTIONAL)
1154           grid->dwidth = grid->glyph_bbx.width + grid->glyph_bbx.x_offset;
1155         grid->glyph_x += delta;
1156     } else if (maxx < wd - 1) {
1157         delta = (wd - 1) - maxx;
1158         grid->glyph_bbx.width -= delta;
1159         if (grid->spacing == BDF_PROPORTIONAL)
1160           grid->dwidth = grid->glyph_bbx.width + grid->glyph_bbx.x_offset;
1161     }
1162
1163     if (miny > grid->glyph_y) {
1164         delta = miny - grid->glyph_y;
1165         grid->glyph_bbx.ascent -= delta;
1166         grid->glyph_bbx.height -= delta;
1167         grid->glyph_y += delta;
1168     } else if (maxy < ht - 1) {
1169         delta = (ht - 1) - maxy;
1170         grid->glyph_bbx.descent -= delta;
1171         grid->glyph_bbx.height -= delta;
1172         grid->glyph_bbx.y_offset = -grid->glyph_bbx.descent;
1173     }
1174
1175     /*
1176      * Indicate that the glyph was modified.
1177      */
1178     grid->modified = 1;
1179
1180     return cleared;
1181 }
1182
1183 int
1184 bdf_grid_invert_pixel(bdf_glyph_grid_t *grid, short x, short y, int val)
1185 {
1186     short bpr, di;
1187     unsigned char *masks;
1188
1189     if (grid == 0 || x < 0 || x >= grid->grid_width ||
1190         y < 0 || y >= grid->grid_height)
1191       return 0;
1192
1193     masks = 0;
1194     switch (grid->bpp) {
1195       case 1: masks = bdf_onebpp; break;
1196       case 2: masks = bdf_twobpp; break;
1197       case 4: masks = bdf_fourbpp; break;
1198       case 8: masks = bdf_eightbpp; break;
1199     }
1200
1201     /*
1202      * Determine the bytes-per-row and mask index.
1203      */
1204     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
1205     di = ((x * grid->bpp) & 7) / grid->bpp;
1206
1207     /*
1208      * If the bit is set, then clear it, otherwise, set it.
1209      */
1210     if (grid->bitmap[(y * bpr) + ((x * grid->bpp) >> 3)] & masks[di])
1211       return bdf_grid_clear_pixel(grid, x, y);
1212     else
1213       return bdf_grid_set_pixel(grid, x, y, val);
1214 }
1215
1216 /**************************************************************************
1217  *
1218  * Glyph grid bitmap transformation functions.
1219  *
1220  **************************************************************************/
1221
1222 short
1223 _bdf_ceiling(double v)
1224 {
1225     short val, neg;
1226
1227     val = neg = 0;
1228     if (v < 0) {
1229         neg = 1;
1230         while (v < -1.0) {
1231             val++;
1232             v += 1.0;
1233         }
1234     } else if (v > 0) {
1235         while (v > 1.0) {
1236             val++;
1237             v -= 1.0;
1238         }
1239         if (v > 0.0)
1240           val++;
1241     }
1242     return (!neg) ? val : -val;
1243 }
1244
1245 static int
1246 _bdf_rotate_selection(bdf_glyph_grid_t *grid, int mul90, short degrees)
1247 {
1248     int rotated, byte;
1249     short wd, ht, nx, ny, cx, cy, x, y, col;
1250     short ox, oy, shiftx, shifty, si, di;
1251     double dx, dy;
1252     unsigned short bytes, bpr;
1253     unsigned char *scratch, *masks;
1254
1255     rotated = 0;
1256
1257     /*
1258      * Check to see if the number of rotations would have no affect by
1259      * checking if the count is a multiple of 4 (mod 4 == 0).
1260      */
1261     if (grid == 0 || degrees == 0)
1262       return rotated;
1263
1264     masks = 0;
1265     switch (grid->bpp) {
1266       case 1: masks = bdf_onebpp; break;
1267       case 2: masks = bdf_twobpp; break;
1268       case 4: masks = bdf_fourbpp; break;
1269       case 8: masks = bdf_eightbpp; break;
1270     }
1271
1272     bytes = grid->sel.bytes >> 1;
1273     scratch = grid->sel.bitmap + bytes;
1274     (void) memset((char *) scratch, 0, bytes);
1275
1276     cx = grid->sel.width >> 1;
1277     cy = grid->sel.height >> 1;
1278
1279     wd = ht = MAX(grid->sel.width, grid->sel.height);
1280     cx = cy = wd >> 1;
1281
1282     bpr = ((wd * grid->bpp) + 7) >> 3;
1283
1284     for (shiftx = shifty = y = 0; y < ht; y++) {
1285         for (col = x = 0; x < wd; x++, col += grid->bpp) {
1286             dx = (double) (x - cx);
1287             dy = (double) (y - cy);
1288             if (mul90) {
1289                 nx = cx + (short) ((dx * _bdf_cos_tbl[degrees]) -
1290                                    (dy * _bdf_sin_tbl[degrees]));
1291                 ny = cy + (short) ((dx * _bdf_sin_tbl[degrees]) +
1292                                    (dy * _bdf_cos_tbl[degrees]));
1293             } else {
1294                 nx = cx + _bdf_ceiling((dx * _bdf_cos_tbl[degrees]) -
1295                                        (dy * _bdf_sin_tbl[degrees]));
1296                 ny = cy + _bdf_ceiling((dx * _bdf_sin_tbl[degrees]) +
1297                                        (dy * _bdf_cos_tbl[degrees]));
1298             }
1299
1300             /*
1301              * Wrap the coordinates around the edges if necessary.
1302              */
1303             if (nx < 0) {
1304                 shiftx = MIN(shiftx, nx);
1305                 nx += wd;
1306             } else if (nx >= wd) {
1307                 ox = (nx - wd) + 1;
1308                 shiftx = MAX(shiftx, ox);
1309                 nx -= wd;
1310             }
1311             if (ny < 0) {
1312                 shifty = MIN(shifty, ny);
1313                 ny += ht;
1314             } else if (ny >= ht) {
1315                 oy = (ny - ht) + 1;
1316                 shifty = MAX(shifty, oy);
1317                 ny -= ht;
1318             }
1319
1320             si = (col & 7) / grid->bpp;
1321             byte = grid->sel.bitmap[(y * bpr) + (col >> 3)] & masks[si];
1322             if (byte) {
1323                 rotated = 1;
1324                 nx *= grid->bpp;
1325                 di = (nx & 7) / grid->bpp;
1326                 if (di < si)
1327                   byte <<= (si - di) * grid->bpp;
1328                 else if (di > si)
1329                   byte >>= (di - si) * grid->bpp;
1330                 scratch[(ny * bpr) + (nx >> 3)] |= byte;
1331             }
1332         }
1333     }
1334
1335     if (rotated) {
1336         /*
1337          * If a shift is required, then shift the scratch area back into
1338          * the main bitmap.
1339          */
1340         if (shiftx || shifty) {
1341             (void) memset((char *) grid->sel.bitmap, 0, bytes);
1342             for (y = 0; y < ht; y++) {
1343                 for (col = x = 0; x < wd; x++, col += grid->bpp) {
1344                     si = (col & 7) / grid->bpp;
1345                     byte = scratch[(y * bpr) + (col >> 3)] & masks[si];
1346                     if (byte) {
1347                         nx = x - shiftx;
1348                         ny = y - shifty;
1349
1350                         if (nx < 0)
1351                           nx += wd;
1352                         else if (nx >= wd)
1353                           nx -= wd;
1354                         if (ny < 0)
1355                           ny += ht;
1356                         else if (ny >= ht)
1357                           ny -= ht;
1358
1359                         nx *= grid->bpp;
1360                         di = (nx & 7) / grid->bpp;
1361                         if (di < si)
1362                           byte <<= (si - di) * grid->bpp;
1363                         else if (di > si)
1364                           byte >>= (di - si) * grid->bpp;
1365                         grid->sel.bitmap[(ny * bpr) + (nx >> 3)] |= byte;
1366                     }
1367                 }
1368             }
1369         } else
1370           /*
1371            * Copy the scratch buffer back to the main buffer.
1372            */
1373           (void) memcpy((char *) grid->sel.bitmap, (char *) scratch, bytes);
1374
1375         /*
1376          * Determine the new selection width and height.
1377          */
1378         ox = oy = 0;
1379         nx = ny = 16384;
1380         for (y = 0; y < ht; y++) {
1381             for (col = x = 0; x < wd; x++, col += grid->bpp) {
1382                 si = (col & 7) / grid->bpp;
1383                 if (grid->sel.bitmap[(y * bpr) + (col >> 3)] & masks[si]) {
1384                     ox = MAX(ox, x);
1385                     nx = MIN(nx, x);
1386                     oy = MAX(oy, y);
1387                     ny = MIN(ny, y);
1388                 }
1389             }
1390         }
1391
1392         /*
1393          * Recalculate the center corrdinates so the selection will be
1394          * positioned nicely once it is shifted to the upper left corner.
1395          */
1396         cx = grid->sel.width >> 1;
1397         cy = grid->sel.height >> 1;
1398
1399         /*
1400          * Set the new width and height.
1401          */
1402         grid->sel.width = (ox - nx) + 1;
1403         grid->sel.height = (oy - ny) + 1;
1404
1405         /*
1406          * Shift again to force the selection to the upper left corner.
1407          */
1408         if (nx || ny) {
1409             (void) memset((char *) scratch, 0, bytes);
1410             for (y = 0; y < ht; y++) {
1411                 for (col = x = 0; x < wd; x++, col += grid->bpp) {
1412                     si = (col & 7) / grid->bpp;
1413                     byte = grid->sel.bitmap[(y * bpr) + (col >> 3)] &
1414                         masks[si];
1415                     if (byte) {
1416                         oy = y - ny;
1417                         ox = (x - nx) * grid->bpp;
1418                         di = (ox & 7) / grid->bpp;
1419                         if (di < si)
1420                           byte <<= (si - di) * grid->bpp;
1421                         else if (di > si)
1422                           byte >>= (di - si) * grid->bpp;
1423                         scratch[(oy * bpr) + (ox >> 3)] |= byte;
1424                     }
1425                 }
1426             }
1427             (void) memcpy((char *) grid->sel.bitmap, (char *) scratch, bytes);
1428         }
1429
1430         /*
1431          * Determine the new top left coordinates from the center coordinates.
1432          */
1433         grid->sel.x = (grid->sel.x + cx) - (grid->sel.width >> 1);
1434         grid->sel.y = (grid->sel.y + cy) - (grid->sel.height >> 1);
1435
1436         /*
1437          * If the rotation caused the selection rectangle to overlap the edges
1438          * of the grid, shift it so it is completely visible again.
1439          */
1440         if (grid->sel.x + grid->sel.width > grid->grid_width)
1441           grid->sel.x -= (grid->sel.x + grid->sel.width) - grid->grid_width;
1442         if (grid->sel.y + grid->sel.height > grid->grid_height)
1443           grid->sel.y -= (grid->sel.y + grid->sel.height) - grid->grid_height;
1444
1445         /*
1446          * Mark the grid as being modified.
1447          */
1448         grid->modified = 1;
1449     }
1450
1451     return rotated;
1452 }
1453
1454 static void
1455 _bdf_rotate_resize(bdf_glyph_grid_t *grid, int mul90, short degrees,
1456                   int *resize)
1457 {
1458     unsigned short wd, ht;
1459     short cx, cy, x1, y1, x2, y2;
1460     double dx1, dy1, dx2, dy2;
1461     bdf_metrics_t metrics;
1462
1463     *resize = 0;
1464     (void) memset((char *) &metrics, 0, sizeof(bdf_metrics_t));
1465
1466     metrics.x_offset = grid->font_bbx.x_offset;
1467     metrics.width = grid->font_bbx.width;
1468     metrics.ascent = grid->font_bbx.ascent;
1469     metrics.descent = grid->font_bbx.descent;
1470     metrics.height = grid->font_bbx.height;
1471     metrics.y_offset = grid->font_bbx.y_offset;
1472
1473     cx = grid->glyph_x + (grid->glyph_bbx.width >> 1);
1474     cy = grid->glyph_y + (grid->glyph_bbx.height >> 1);
1475
1476     /*
1477      * Rotate the lower left and upper right corners and check for a potential
1478      * resize.
1479      */
1480     x1 = grid->glyph_x;
1481     y1 = grid->glyph_y + grid->glyph_bbx.height;
1482     x2 = grid->glyph_x + grid->glyph_bbx.width;
1483     y2 = grid->glyph_y;
1484
1485     dx1 = (double) (x1 - cx);
1486     dy1 = (double) (y1 - cy);
1487     dx2 = (double) (x2 - cx);
1488     dy2 = (double) (y2 - cx);
1489
1490     if (mul90) {
1491         x1 = cx + (short) ((dx1 * _bdf_cos_tbl[degrees]) -
1492                            (dy1 * _bdf_sin_tbl[degrees]));
1493         y1 = cy + (short) ((dx1 * _bdf_sin_tbl[degrees]) +
1494                            (dy1 * _bdf_cos_tbl[degrees]));
1495         x2 = cx + (short) ((dx2 * _bdf_cos_tbl[degrees]) -
1496                            (dy2 * _bdf_sin_tbl[degrees]));
1497         y2 = cy + (short) ((dx2 * _bdf_sin_tbl[degrees]) +
1498                            (dy2 * _bdf_cos_tbl[degrees]));
1499     } else {
1500         x1 = cx + _bdf_ceiling((dx1 * _bdf_cos_tbl[degrees]) -
1501                                (dy1 * _bdf_sin_tbl[degrees]));
1502         y1 = cy + _bdf_ceiling((dx1 * _bdf_sin_tbl[degrees]) +
1503                                (dy1 * _bdf_cos_tbl[degrees]));
1504         x2 = cx + _bdf_ceiling((dx2 * _bdf_cos_tbl[degrees]) -
1505                                (dy2 * _bdf_sin_tbl[degrees]));
1506         y2 = cy + _bdf_ceiling((dx2 * _bdf_sin_tbl[degrees]) +
1507                                (dy2 * _bdf_cos_tbl[degrees]));
1508     }
1509
1510     wd = MYABS(x2 - x1);
1511     ht = MYABS(y2 - y1);
1512     if (wd > metrics.width) {
1513         metrics.width += wd - grid->font_bbx.width;
1514         *resize = 1;
1515     }
1516     if (ht > metrics.height) {
1517         metrics.ascent += ht - grid->font_bbx.height;
1518         metrics.height += ht - grid->font_bbx.height;
1519         *resize = 1;
1520     }
1521
1522     /*
1523      * Rotate the upper left and lower right corners and check for a potential
1524      * resize.
1525      */
1526     x1 = grid->glyph_x;
1527     y1 = grid->glyph_y;
1528     x2 = grid->glyph_x + grid->glyph_bbx.width;
1529     y2 = grid->glyph_y + grid->glyph_bbx.height;
1530
1531     dx1 = (double) (x1 - cx);
1532     dy1 = (double) (y1 - cy);
1533     dx2 = (double) (x2 - cx);
1534     dy2 = (double) (y2 - cx);
1535
1536     if (mul90) {
1537         x1 = cx + (short) ((dx1 * _bdf_cos_tbl[degrees]) -
1538                            (dy1 * _bdf_sin_tbl[degrees]));
1539         y1 = cy + (short) ((dx1 * _bdf_sin_tbl[degrees]) +
1540                            (dy1 * _bdf_cos_tbl[degrees]));
1541         x2 = cx + (short) ((dx2 * _bdf_cos_tbl[degrees]) -
1542                            (dy2 * _bdf_sin_tbl[degrees]));
1543         y2 = cy + (short) ((dx2 * _bdf_sin_tbl[degrees]) +
1544                            (dy2 * _bdf_cos_tbl[degrees]));
1545     } else {
1546         x1 = cx + _bdf_ceiling((dx1 * _bdf_cos_tbl[degrees]) -
1547                                (dy1 * _bdf_sin_tbl[degrees]));
1548         y1 = cy + _bdf_ceiling((dx1 * _bdf_sin_tbl[degrees]) +
1549                                (dy1 * _bdf_cos_tbl[degrees]));
1550         x2 = cx + _bdf_ceiling((dx2 * _bdf_cos_tbl[degrees]) -
1551                                (dy2 * _bdf_sin_tbl[degrees]));
1552         y2 = cy + _bdf_ceiling((dx2 * _bdf_sin_tbl[degrees]) +
1553                                (dy2 * _bdf_cos_tbl[degrees]));
1554     }
1555
1556     wd = MYABS(x2 - x1);
1557     ht = MYABS(y2 - y1);
1558     if (wd > metrics.width) {
1559         metrics.width += wd - grid->font_bbx.width;
1560         *resize = 1;
1561     }
1562     if (ht > metrics.height) {
1563         metrics.ascent += ht - grid->font_bbx.height;
1564         metrics.height += ht - grid->font_bbx.height;
1565         *resize = 1;
1566     }
1567
1568     if (*resize)
1569       (void) bdf_grid_resize(grid, &metrics);
1570 }
1571
1572 static void
1573 _bdf_shear_resize(bdf_glyph_grid_t *grid, short degrees, int neg, int *resize)
1574 {
1575     unsigned short wd;
1576     short x1, y1, x2, y2;
1577     bdf_metrics_t metrics;
1578
1579     *resize = 0;
1580     (void) memset((char *) &metrics, 0, sizeof(bdf_metrics_t));
1581
1582     metrics.x_offset = grid->font_bbx.x_offset;
1583     metrics.width = grid->font_bbx.width;
1584     metrics.ascent = grid->font_bbx.ascent;
1585     metrics.descent = grid->font_bbx.descent;
1586     metrics.height = grid->font_bbx.height;
1587     metrics.y_offset = grid->font_bbx.y_offset;
1588
1589     /*
1590      * Shear the lower left and upper right corners and check for a potential
1591      * resize.
1592      */
1593     x1 = 0;
1594     y1 = grid->glyph_bbx.height;
1595     x2 = grid->glyph_bbx.width;
1596     y2 = 0;
1597
1598     if (neg) {
1599         x1 += (short) ((double) y1 * _bdf_tan_tbl[degrees]);
1600         x2 += (short) ((double) y2 * _bdf_tan_tbl[degrees]);
1601     } else {
1602         x1 += (short) ((double) (grid->glyph_bbx.height - y1) *
1603                        _bdf_tan_tbl[degrees]);
1604         x2 += (short) ((double) (grid->glyph_bbx.height - y2) *
1605                        _bdf_tan_tbl[degrees]);
1606     }
1607
1608     wd = MYABS(x2 - x1);
1609     if (wd > metrics.width) {
1610         metrics.width += wd - grid->font_bbx.width;
1611         *resize = 1;
1612     }
1613
1614     /*
1615      * Shear the upper left and lower right corners and check for a potential
1616      * resize.
1617      */
1618     x1 = 0;
1619     y1 = 0;
1620     x2 = grid->glyph_bbx.width;
1621     y2 = grid->glyph_bbx.height;
1622
1623     if (neg) {
1624         x1 += (short) ((double) y1 * _bdf_tan_tbl[degrees]);
1625         x2 += (short) ((double) y2 * _bdf_tan_tbl[degrees]);
1626     } else {
1627         x1 += (short) ((double) (grid->glyph_bbx.height - y1) *
1628                        _bdf_tan_tbl[degrees]);
1629         x2 += (short) ((double) (grid->glyph_bbx.height - y2) *
1630                        _bdf_tan_tbl[degrees]);
1631     }
1632
1633     wd = MYABS(x2 - x1);
1634     if (wd > metrics.width) {
1635         metrics.width += wd - grid->font_bbx.width;
1636         *resize = 1;
1637     }
1638
1639     if (*resize)
1640       (void) bdf_grid_resize(grid, &metrics);
1641 }
1642
1643 /*
1644  * Rotate the bitmap in the grid by some number of degrees.
1645  */
1646 int
1647 bdf_grid_rotate(bdf_glyph_grid_t *grid, short degrees, int *resize)
1648 {
1649     int rotated, mul90;
1650     short nx, ny, cx, cy, x, y, wd, ht;
1651     short ox, oy, gx, gy, shiftx, shifty;
1652     unsigned short si, di, col, byte;
1653     double dx, dy;
1654     unsigned short bytes, bpr;
1655     unsigned char *scratch, *masks;
1656
1657     rotated = 0;
1658
1659     /*
1660      * Make sure the number of degrees is between 0 and 359 and adjusted to a
1661      * positive number of degrees if necessary.
1662      */
1663     while (degrees < 0)
1664       degrees += 360;
1665     while (degrees >= 360)
1666       degrees -= 360;
1667
1668     if (grid == 0 || degrees == 0 ||
1669         (grid->glyph_bbx.width == 0 && grid->glyph_bbx.height == 0))
1670       return rotated;
1671
1672     masks = 0;
1673     switch (grid->bpp) {
1674       case 1: masks = bdf_onebpp; break;
1675       case 2: masks = bdf_twobpp; break;
1676       case 4: masks = bdf_fourbpp; break;
1677       case 8: masks = bdf_eightbpp; break;
1678     }
1679
1680     mul90 = ((degrees % 90) == 0) ? 1 : 0;
1681
1682     /*
1683      * Force the grid to resize if the rotation requires it.
1684      */
1685     _bdf_rotate_resize(grid, mul90, degrees, resize);
1686
1687     if (grid->sel.width != 0 && grid->sel.height != 0)
1688       return _bdf_rotate_selection(grid, mul90, degrees);
1689
1690     /*
1691      * Halve the byte count in the grid for later use.
1692      */
1693     bytes = grid->bytes >> 1;
1694
1695     /*
1696      * Point at the scratch buffer area and initialize it.
1697      */
1698     scratch = grid->bitmap + bytes;
1699     (void) memset((char *) scratch, 0, bytes);
1700
1701     /*
1702      * Determine the bytes per row.
1703      */
1704     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
1705
1706     /*
1707      * Determine the center coordinates of the glyph bitmap rectangle.
1708      */
1709     cx = grid->glyph_x + (grid->glyph_bbx.width >> 1);
1710     cy = grid->glyph_y + (grid->glyph_bbx.height >> 1);
1711
1712     /*
1713      * Only run over the rectangle containing the glyph itself.
1714      */
1715     gx = grid->glyph_x;
1716     gy = grid->glyph_y;
1717
1718     wd = gx + grid->glyph_bbx.width;
1719     ht = gy + grid->glyph_bbx.height;
1720
1721     /*
1722      * Initialize the adjustment counts used if the bitmap
1723      * wraps around the edge.
1724      */
1725     shiftx = shifty = 0;
1726
1727     for (y = gy; y < ht; y++) {
1728         col = gx * grid->bpp;
1729         for (x = gx; x < wd; x++, col += grid->bpp) {
1730
1731             /*
1732              * Rotate the point.
1733              */
1734             dx = (double) (x - cx);
1735             dy = (double) (y - cy);
1736             if (mul90) {
1737                 nx = cx + (short) ((dx * _bdf_cos_tbl[degrees]) -
1738                                    (dy * _bdf_sin_tbl[degrees]));
1739                 ny = cy + (short) ((dx * _bdf_sin_tbl[degrees]) +
1740                                    (dy * _bdf_cos_tbl[degrees]));
1741             } else {
1742                 nx = cx + _bdf_ceiling((dx * _bdf_cos_tbl[degrees]) -
1743                                        (dy * _bdf_sin_tbl[degrees]));
1744                 ny = cy + _bdf_ceiling((dx * _bdf_sin_tbl[degrees]) +
1745                                        (dy * _bdf_cos_tbl[degrees]));
1746             }
1747
1748             /*
1749              * Wrap the coordinates around the edges if necessary.
1750              */
1751             if (nx < 0) {
1752                 shiftx = MIN(shiftx, nx);
1753                 nx += grid->grid_width;
1754             } else if (nx >= grid->grid_width) {
1755                 ox = (nx - grid->grid_width) + 1;
1756                 shiftx = MAX(shiftx, ox);
1757                 nx -= grid->grid_width;
1758             }
1759             if (ny < 0) {
1760                 shifty = MIN(shifty, ny);
1761                 ny += grid->grid_height;
1762             } else if (ny >= grid->grid_height) {
1763                 oy = (ny - grid->grid_height) + 1;
1764                 shifty = MAX(shifty, oy);
1765                 ny -= grid->grid_height;
1766             }
1767
1768             si = (col & 7) / grid->bpp;
1769             byte = grid->bitmap[(y * bpr) + (col >> 3)] & masks[si];
1770             if (byte) {
1771                 rotated = 1;
1772                 nx *= grid->bpp;
1773                 di = (nx & 7) / grid->bpp;
1774                 if (di < si)
1775                   byte <<= (si - di) * grid->bpp;
1776                 else if (di > si)
1777                   byte >>= (di - si) * grid->bpp;
1778                 scratch[(ny * bpr) + (nx >> 3)] |= byte;
1779             }
1780         }
1781     }
1782
1783     if (rotated) {
1784         /*
1785          * If a shift is required, then shift the scratch area back into
1786          * the main bitmap.
1787          */
1788         if (shiftx || shifty) {
1789             (void) memset((char *) grid->bitmap, 0, bytes);
1790             for (y = 0; y < grid->grid_height; y++) {
1791                 for (col = x = 0; x < grid->grid_width;
1792                      x++, col += grid->bpp) {
1793                     si = (col & 7) / grid->bpp;
1794                     byte = scratch[(y * bpr) + (col >> 3)] & masks[si];
1795                     if (byte) {
1796                         nx = x - shiftx;
1797                         ny = y - shifty;
1798
1799                         if (nx < 0)
1800                           nx += grid->grid_width;
1801                         else if (nx >= grid->grid_width)
1802                           nx -= grid->grid_width;
1803                         if (ny < 0)
1804                           ny += grid->grid_height;
1805                         else if (ny >= grid->grid_height)
1806                           ny -= grid->grid_height;
1807
1808                         nx *= grid->bpp;
1809                         di = (nx & 7) / grid->bpp;
1810                         if (di < si)
1811                           byte <<= (si - di) * grid->bpp;
1812                         else if (di > si)
1813                           byte >>= (di - si) * grid->bpp;
1814                         grid->bitmap[(ny * bpr) + (nx >> 3)] |= byte;
1815                     }
1816                 }
1817             }
1818         } else
1819           /*
1820            * Copy the scratch buffer back to the main buffer.
1821            */
1822           (void) memcpy((char *) grid->bitmap, (char *) scratch, bytes);
1823
1824         /*
1825          * Determine the new glyph bounding box and the top left coordinates.
1826          */
1827         ox = oy = 0;
1828         nx = ny = 16384;
1829         for (y = 0; y < grid->grid_height; y++) {
1830             for (col = x = 0; x < grid->grid_width; x++, col += grid->bpp) {
1831                 si = (col & 7) / grid->bpp;
1832                 if (grid->bitmap[(y * bpr) + (col >> 3)] & masks[si]) {
1833                     nx = MIN(nx, x);
1834                     ox = MAX(ox, x);
1835                     ny = MIN(ny, y);
1836                     oy = MAX(oy, y);
1837                 }
1838             }
1839         }
1840
1841         /*
1842          * Set the new top left corrdinates.
1843          */
1844         grid->glyph_x = nx;
1845         grid->glyph_y = ny;
1846
1847         /*
1848          * Set the new glyph bounding box.
1849          */
1850         grid->glyph_bbx.width = (ox - nx) + 1;
1851         grid->glyph_bbx.x_offset = nx - grid->base_x;
1852         grid->glyph_bbx.height = (oy - ny) + 1;
1853         grid->glyph_bbx.ascent = grid->base_y - ny;
1854         grid->glyph_bbx.descent = grid->glyph_bbx.height -
1855             grid->glyph_bbx.ascent;
1856         grid->glyph_bbx.y_offset = -grid->glyph_bbx.descent;
1857
1858         /*
1859          * Mark the grid as being modified.
1860          */
1861         grid->modified = 1;
1862     }
1863
1864     return rotated;
1865 }
1866
1867 int
1868 bdf_grid_shear(bdf_glyph_grid_t *grid, short degrees, int *resize)
1869 {
1870     int sheared, neg;
1871     short cx, cy, wd, ht, gx, gy, x, y;
1872     short nx, ox, ny, oy, shiftx, shifty;
1873     unsigned short bytes, bpr, si, di, col, byte;
1874     unsigned char *scratch, *masks;
1875
1876     sheared = 0;
1877
1878     if (degrees == 0 || degrees < -45 || degrees > 45 || grid == 0 ||
1879         (grid->glyph_bbx.width == 0 && grid->glyph_bbx.height == 0))
1880       return sheared;
1881
1882     if ((neg = (degrees < 0)))
1883       degrees = -degrees;
1884
1885     /*
1886      * Check to see if the grid needs to be resized to hold the sheared glyph.
1887      */
1888     _bdf_shear_resize(grid, degrees, neg, resize);
1889
1890     masks = 0;
1891     switch (grid->bpp) {
1892       case 1: masks = bdf_onebpp; break;
1893       case 2: masks = bdf_twobpp; break;
1894       case 4: masks = bdf_fourbpp; break;
1895       case 8: masks = bdf_eightbpp; break;
1896     }
1897
1898     /*
1899      * Halve the byte count in the grid for later use.
1900      */
1901     bytes = grid->bytes >> 1;
1902
1903     /*
1904      * Point at the scratch buffer area and initialize it.
1905      */
1906     scratch = grid->bitmap + bytes;
1907     (void) memset((char *) scratch, 0, bytes);
1908
1909     /*
1910      * Determine the bytes per row.
1911      */
1912     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
1913
1914     /*
1915      * Determine the center coordinates of the glyph bitmap rectangle.
1916      */
1917     gx = grid->glyph_x;
1918     gy = grid->glyph_y;
1919
1920     cx = gx + (grid->glyph_bbx.width >> 1);
1921     cy = gy + (grid->glyph_bbx.height >> 1);
1922
1923     wd = gx + grid->glyph_bbx.width;
1924     ht = gy + grid->glyph_bbx.height;
1925
1926     shiftx = shifty = 0;
1927     for (y = gy; y < ht; y++) {
1928         col = gx * grid->bpp;
1929         for (x = gx; x < wd; x++, col += grid->bpp) {
1930             ny = y;
1931             if (neg)
1932               nx = x + (short) ((double) y * _bdf_tan_tbl[degrees]);
1933             else
1934               nx = x + (short) ((double) (gy + (ht - y)) *
1935                                 _bdf_tan_tbl[degrees]);
1936
1937             if (nx < 0) {
1938                 shiftx = MIN(shiftx, nx);
1939                 nx += grid->grid_width;
1940             } else if (nx >= grid->grid_width) {
1941                 ox = (nx - grid->grid_width) + 1;
1942                 shiftx = MAX(shiftx, ox);
1943                 nx -= grid->grid_width;
1944             }
1945             if (ny < 0) {
1946                 shifty = MIN(shifty, ny);
1947                 ny += grid->grid_height;
1948             } else if (ny >= grid->grid_height) {
1949                 oy = (ny - grid->grid_height) + 1;
1950                 shifty = MAX(shifty, oy);
1951                 ny -= grid->grid_height;
1952             }
1953
1954             si = (col & 7) / grid->bpp;
1955             byte = grid->bitmap[(y * bpr) + (col >> 3)] & masks[si];
1956             if (byte) {
1957                 sheared = 1;
1958                 nx *= grid->bpp;
1959                 di = (nx & 7) / grid->bpp;
1960                 if (di < si)
1961                   byte <<= (si - di) * grid->bpp;
1962                 else if (di > si)
1963                   byte >>= (di - si) * grid->bpp;
1964                 scratch[(y * bpr) + (nx >> 3)] |= byte;
1965             }
1966         }
1967     }
1968
1969     if (sheared) {
1970         /*
1971          * If a shift is required, then shift the scratch area back into
1972          * the main bitmap.
1973          */
1974         if (shiftx || shifty) {
1975             (void) memset((char *) grid->bitmap, 0, bytes);
1976             for (y = 0; y < grid->grid_height; y++) {
1977                 for (col = x = 0; x < grid->grid_width;
1978                      x++, col += grid->bpp) {
1979                     si = (col & 7) / grid->bpp;
1980                     byte = scratch[(y * bpr) + (col >> 3)] & masks[si];
1981                     if (byte) {
1982                         nx = x - shiftx;
1983                         ny = y - shifty;
1984
1985                         if (nx < 0)
1986                           nx += grid->grid_width;
1987                         else if (nx >= grid->grid_width)
1988                           nx -= grid->grid_width;
1989                         if (ny < 0)
1990                           ny += grid->grid_height;
1991                         else if (ny >= grid->grid_height)
1992                           ny -= grid->grid_height;
1993
1994                         nx *= grid->bpp;
1995                         di = (nx & 7) / grid->bpp;
1996                         if (di < si)
1997                           byte <<= (si - di) * grid->bpp;
1998                         else if (di > si)
1999                           byte >>= (di - si) * grid->bpp;
2000                         grid->bitmap[(ny * bpr) + (nx >> 3)] |= byte;
2001                     }
2002                 }
2003             }
2004         } else
2005           /*
2006            * Copy the scratch buffer back to the main buffer.
2007            */
2008           (void) memcpy((char *) grid->bitmap, (char *) scratch, bytes);
2009
2010         ox = oy = 0;
2011         nx = ny = 16384;
2012         for (y = 0; y < grid->grid_height; y++) {
2013             for (col = x = 0; x < grid->grid_width; x++, col += grid->bpp) {
2014                 si = (col & 7) / grid->bpp;
2015                 if (grid->bitmap[(y * bpr) + (col >> 3)] & masks[si]) {
2016                     ox = MAX(ox, x);
2017                     nx = MIN(nx, x);
2018                     oy = MAX(oy, y);
2019                     ny = MIN(ny, y);
2020                 }
2021             }
2022         }
2023
2024         /*
2025          * Set the new top left corrdinates.
2026          */
2027         grid->glyph_x = nx;
2028         grid->glyph_y = ny;
2029
2030         /*
2031          * Set the new glyph bounding box.
2032          */
2033         grid->glyph_bbx.width = (ox - nx) + 1;
2034         grid->glyph_bbx.x_offset = nx - grid->base_x;
2035         grid->glyph_bbx.height = (oy - ny) + 1;
2036         grid->glyph_bbx.ascent = grid->base_y - ny;
2037         grid->glyph_bbx.descent = grid->glyph_bbx.height -
2038             grid->glyph_bbx.ascent;
2039         grid->glyph_bbx.y_offset = -grid->glyph_bbx.descent;
2040
2041         /*
2042          * Mark the grid as being modified.
2043          */
2044         grid->modified = 1;
2045     }
2046
2047     return sheared;
2048 }
2049
2050 int
2051 bdf_grid_embolden(bdf_glyph_grid_t *grid)
2052 {
2053     int done;
2054     short wd, ht, gx, gy, x, y;
2055     unsigned short b1, b2, bpr, si, di, col;
2056     unsigned char *masks;
2057
2058     done = 0;
2059
2060     if (grid == 0 ||
2061         (grid->glyph_bbx.width == 0 && grid->glyph_bbx.height == 0))
2062       return done;
2063
2064     masks = 0;
2065     switch (grid->bpp) {
2066       case 1: masks = bdf_onebpp; break;
2067       case 2: masks = bdf_twobpp; break;
2068       case 4: masks = bdf_fourbpp; break;
2069       case 8: masks = bdf_eightbpp; break;
2070     }
2071
2072     /*
2073      * Determine the bytes per row.
2074      */
2075     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2076
2077     gx = grid->glyph_x;
2078     gy = grid->glyph_y;
2079
2080     wd = gx + grid->glyph_bbx.width;
2081     ht = gy + grid->glyph_bbx.height;
2082
2083     if (grid->spacing == BDF_PROPORTIONAL ||
2084         (grid->spacing == BDF_MONOWIDTH &&
2085          grid->glyph_bbx.width < grid->font_bbx.width))
2086       /*
2087        * Only allow horizontal expansion in the cases that make sense.
2088        */
2089       wd++;
2090
2091     for (y = gy; y < ht; y++) {
2092         col = (wd - 1) * grid->bpp;
2093         for (x = wd - 1; x > gx; x--, col -= grid->bpp) {
2094             si = (col & 7) / grid->bpp;
2095             di = ((col - grid->bpp) & 7) / grid->bpp;
2096             b1 = grid->bitmap[(y * bpr) + (col >> 3)] & masks[si];
2097             b2 = grid->bitmap[(y * bpr) + ((col - grid->bpp) >> 3)] &
2098                 masks[di];
2099             if (!b1 && b2) {
2100                 if (di < si)
2101                   b2 >>= (si - di) * grid->bpp;
2102                 else if (di > si)
2103                   b2 <<= (di - si) * grid->bpp;
2104                 grid->bitmap[(y * bpr) + (col >> 3)] |= b2;
2105                 /*
2106                  * Mark the grid as being modified.
2107                  */
2108                 done = grid->modified = 1;
2109             }
2110         }
2111     }
2112
2113     /*
2114      * Adjust the glyph width so it will be reflected when the glyph is stored
2115      * back in the font.
2116      */
2117     grid->glyph_bbx.width = wd - gx;
2118
2119     return done;
2120 }
2121
2122 /**************************************************************************
2123  *
2124  * Glyph grid selection functions.
2125  *
2126  **************************************************************************/
2127
2128 int
2129 bdf_has_selection(bdf_glyph_grid_t *grid, short *x, short *y,
2130                   short *width, short *height)
2131 {
2132     if (grid == 0 || (grid->sel.width == 0 && grid->sel.height == 0))
2133       return 0;
2134
2135     if (x != 0)
2136       *x = grid->sel.x;
2137     if (y != 0)
2138       *y = grid->sel.y;
2139     if (width != 0)
2140       *width = grid->sel.width;
2141     if (height != 0)
2142       *height = grid->sel.height;
2143
2144     return 1;
2145 }
2146
2147 /*
2148  * Select a rectangle on the grid.
2149  */
2150 void
2151 bdf_set_selection(bdf_glyph_grid_t *grid, short x, short y,
2152                   short width, short height)
2153 {
2154     short nx, ny, wd, ht, ssize, dx, dy, col;
2155     unsigned short bytes, bpr, sbpr, si, di, byte;
2156     unsigned char *masks;
2157
2158     if (grid == 0)
2159       return;
2160
2161     /*
2162      * Make sure the specified rectangle is within reasonable bounds.
2163      */
2164     if (x < 0 || x >= grid->grid_width)
2165       x = 0;
2166     if (y < 0 || y >= grid->grid_height)
2167       y = 0;
2168
2169     if (x + width > grid->grid_width)
2170       width = (x + width) - grid->grid_width;
2171     if (y + height > grid->grid_height)
2172       height = (y + height) - grid->grid_height;
2173
2174     grid->sel.x = x;
2175     grid->sel.y = y;
2176     grid->sel.width = width;
2177     grid->sel.height = height;
2178
2179     /*
2180      * Allocate enough space to represent a square the size of the largest
2181      * of the width and height of the selection.  This allows rotation and
2182      * flipping of the selected bitmap.
2183      */
2184     ssize = MAX(width, height);
2185
2186     bytes = ((((ssize * grid->bpp) + 7) >> 3) * ssize) << 1;
2187
2188     /*
2189      * If the selection is being removed (width and height are 0), then simply
2190      * return.
2191      */
2192     if (bytes == 0)
2193       return;
2194
2195     masks = 0;
2196     switch (grid->bpp) {
2197       case 1: masks = bdf_onebpp; break;
2198       case 2: masks = bdf_twobpp; break;
2199       case 4: masks = bdf_fourbpp; break;
2200       case 8: masks = bdf_eightbpp; break;
2201     }
2202
2203     if (bytes > grid->sel.bytes) {
2204         if (grid->sel.bytes == 0)
2205           grid->sel.bitmap = (unsigned char *) malloc(bytes);
2206         else
2207           grid->sel.bitmap = (unsigned char *)
2208               realloc((char *) grid->sel.bitmap, bytes);
2209         grid->sel.bytes = bytes;
2210     } else
2211       bytes = grid->sel.bytes;
2212
2213     /*
2214      * Initialize the selection bitmap and copy the selected bits to it.
2215      */
2216     (void) memset((char *) grid->sel.bitmap, 0, bytes);
2217
2218     wd = x + width;
2219     ht = y + height;
2220
2221     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2222     sbpr = ((grid->sel.width * grid->bpp) + 7) >> 3;
2223
2224     for (ny = 0, dy = y; dy < ht; dy++, ny++) {
2225         col = x * grid->bpp;
2226         for (nx = 0, dx = x; dx < wd;
2227              dx++, nx += grid->bpp, col += grid->bpp) {
2228             si = (col & 7) / grid->bpp;
2229             byte = grid->bitmap[(dy * bpr) + (col >> 3)] & masks[si];
2230             if (byte) {
2231                 di = (nx & 7) / grid->bpp;
2232                 if (di < si)
2233                   byte <<= (si - di) * grid->bpp;
2234                 else if (di > si)
2235                   byte >>= (di - si) * grid->bpp;
2236                 grid->sel.bitmap[(ny * sbpr) + (nx >> 3)] |= byte;
2237             }
2238         }
2239     }
2240 }
2241
2242 /*
2243  * Detach a selection in preparation for moving it.  What it does is clear the
2244  * bits set in the selection from the main grid.  Again, this is only used for
2245  * move operations.
2246  */
2247 void
2248 bdf_detach_selection(bdf_glyph_grid_t *grid)
2249 {
2250     short sx, sy, x, y, wd, ht, dx;
2251     unsigned short bpr, sbpr, si, di, byte;
2252     unsigned char *masks;
2253
2254     if (grid == 0 || (grid->sel.width == 0 && grid->sel.height == 0))
2255       return;
2256
2257     masks = 0;
2258     switch (grid->bpp) {
2259       case 1: masks = bdf_onebpp; break;
2260       case 2: masks = bdf_twobpp; break;
2261       case 4: masks = bdf_fourbpp; break;
2262       case 8: masks = bdf_eightbpp; break;
2263     }
2264
2265     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2266     sbpr = ((grid->sel.width * grid->bpp) + 7) >> 3;
2267
2268     wd = grid->sel.x + grid->sel.width;
2269     ht = grid->sel.y + grid->sel.height;
2270
2271     for (sy = 0, y = grid->sel.y; y < ht; y++, sy++) {
2272         for (sx = 0, x = grid->sel.x; x < wd; x++, sx += grid->bpp) {
2273             si = (sx & 7) / grid->bpp;
2274             byte = grid->sel.bitmap[(sy * sbpr) + (sx >> 3)] & masks[si];
2275             if (byte) {
2276                 dx = x * grid->bpp;
2277                 di = (dx & 7) / grid->bpp;
2278                 grid->bitmap[(y * bpr) + (dx >> 3)] &= ~masks[di];
2279             }
2280         }
2281     }
2282
2283     /*
2284      * Crop the new image to determine the new bounds with the selection.
2285      */
2286     (void) bdf_grid_crop(grid, 1);
2287 }
2288
2289 void
2290 bdf_attach_selection(bdf_glyph_grid_t *grid)
2291 {
2292     short sx, sy, x, y, wd, ht;
2293     unsigned short bpr, sbpr, dx, di, si, byte;
2294     unsigned char *masks;
2295
2296     if (grid == 0 || (grid->sel.width == 0 && grid->sel.height == 0))
2297       return;
2298
2299     masks = 0;
2300     switch (grid->bpp) {
2301       case 1: masks = bdf_onebpp; break;
2302       case 2: masks = bdf_twobpp; break;
2303       case 4: masks = bdf_fourbpp; break;
2304       case 8: masks = bdf_eightbpp; break;
2305     }
2306
2307     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2308     sbpr = ((grid->sel.width * grid->bpp) + 7) >> 3;
2309
2310     wd = grid->sel.x + grid->sel.width;
2311     ht = grid->sel.y + grid->sel.height;
2312
2313     for (sy = 0, y = grid->sel.y; y < ht; y++, sy++) {
2314         for (sx = 0, x = grid->sel.x; x < wd; x++, sx += grid->bpp) {
2315             si = (sx & 7) / grid->bpp;
2316             byte = grid->sel.bitmap[(sy * sbpr) + (sx >> 3)] & masks[si];
2317             if (byte) {
2318                 dx = x * grid->bpp;
2319                 di = (dx & 7) / grid->bpp;
2320                 if (di < si)
2321                   byte <<= (si - di) * grid->bpp;
2322                 else if (di > si)
2323                   byte >>= (di - si) * grid->bpp;
2324                 grid->bitmap[(y * bpr) + (dx >> 3)] |= byte;
2325             }
2326         }
2327     }
2328
2329     /*
2330      * Crop the new image to determine the new bounds with the selection.
2331      */
2332     (void) bdf_grid_crop(grid, 1);
2333 }
2334
2335 /*
2336  * Indicate the selection no longer exists by setting the width and height to
2337  * 0.
2338  */
2339 void
2340 bdf_lose_selection(bdf_glyph_grid_t *grid)
2341 {
2342     if (grid == 0)
2343       return;
2344     grid->sel.width = grid->sel.height = 0;
2345 }
2346
2347 /*
2348  * Delete the selection by first detaching it which will erase the rectangle
2349  * on the grid and then losing the selection.
2350  */
2351 void
2352 bdf_delete_selection(bdf_glyph_grid_t *grid)
2353 {
2354     bdf_detach_selection(grid);
2355     bdf_lose_selection(grid);
2356 }
2357
2358 /*
2359  * Check to see if a coordinate pair is in the selected region.
2360  */
2361 int
2362 bdf_in_selection(bdf_glyph_grid_t *grid, short x, short y, short *set)
2363 {
2364     short wd, ht;
2365     unsigned short bpr, si, di, byte;
2366     unsigned char *masks;
2367
2368     if (grid == 0 || (grid->sel.width == 0 && grid->sel.height == 0))
2369       return 0;
2370
2371     di = 0;
2372     masks = 0;
2373     switch (grid->bpp) {
2374       case 1: masks = bdf_onebpp; di = 7; break;
2375       case 2: masks = bdf_twobpp; di = 3; break;
2376       case 4: masks = bdf_fourbpp; di = 1; break;
2377       case 8: masks = bdf_eightbpp; di = 0; break;
2378     }
2379
2380     bpr = ((grid->sel.width * grid->bpp) + 7) >> 3;
2381
2382     wd = grid->sel.x + grid->sel.width;
2383     ht = grid->sel.y + grid->sel.height;
2384
2385     if ((x >= grid->sel.x && x < wd) && (y >= grid->sel.y && y < ht)) {
2386         if (set) {
2387             /*
2388              * Adjust the byte back to an index value.
2389              */
2390             x *= grid->bpp;
2391             si = (x & 7) / grid->bpp;
2392             byte = grid->sel.bitmap[(y * bpr) + (x >> 3)] & masks[si];
2393             if (di > si)
2394               byte >>= (di - si) * grid->bpp;
2395             *set = byte;
2396         }
2397         return 1;
2398     }
2399
2400     return 0;
2401 }
2402
2403 int
2404 bdf_grid_shift(bdf_glyph_grid_t *grid, short xcount, short ycount)
2405 {
2406     int sel, delta;
2407     short xdir, ydir, x, y, wd, ht, dx, dy, nx, ny;
2408     unsigned short bytes, bpr, si, di, byte, col;
2409     unsigned char *scratch, *masks;
2410
2411     if (grid == 0)
2412       return 0;
2413
2414     xdir = ydir = 1;
2415     if (xcount < 0) {
2416         xdir = -1;
2417         xcount = -xcount;
2418     }
2419
2420     if (ycount < 0) {
2421         ydir = -1;
2422         ycount = -ycount;
2423     }
2424
2425     /*
2426      * Adjust the shift counts if they are larger than they should be.
2427      */
2428     if (xcount > grid->grid_width)
2429       xcount -= grid->grid_width;
2430     if (ycount > grid->grid_height)
2431       ycount -= grid->grid_height;
2432
2433     /*
2434      * Adjust the counts to limit the shift to the boundaries of the grid.
2435      */
2436     if (grid->sel.width != 0 && grid->sel.height != 0) {
2437         /*
2438          * The selection is being shifted.
2439          */
2440         x = grid->sel.x;
2441         y = grid->sel.y;
2442         wd = grid->sel.width;
2443         ht = grid->sel.height;
2444         sel = 1;
2445     } else {
2446         x = grid->glyph_x;
2447         y = grid->glyph_y;
2448         wd = grid->glyph_bbx.width;
2449         ht = grid->glyph_bbx.height;
2450         sel = 0;
2451     }
2452
2453     /*
2454      * If the width and height are 0, then simply return, because there
2455      * is nothing to shift.
2456      */
2457     if (wd == 0 && ht == 0)
2458       return 0;
2459
2460     if (xdir == 1 && x + wd + xcount > grid->grid_width)
2461       xcount = grid->grid_width - (x + wd);
2462     else if (xdir == -1 && xcount > x)
2463       xcount = x;
2464
2465     if (ydir == 1 && y + ht + ycount > grid->grid_height)
2466       ycount = grid->grid_height - (y + ht);
2467     else if (ydir == -1 && ycount > y)
2468       ycount = y;
2469
2470     if (xcount == 0 && ycount == 0)
2471       return 0;
2472
2473     /*
2474      * If the selection is the one being shifted, adjust the X and Y
2475      * coordinates and adjust the glyph metrics.
2476      */
2477     if (sel) {
2478         /*
2479          * Determine the actual ink bounds of the selection so the
2480          * glyph metrics can be adjusted if necessary.
2481          */
2482         if (_bdf_grid_ink_bounds(grid, &x, &y, &wd, &ht)) {
2483             /*
2484              * Have to adjust the glyph metrics.
2485              */
2486             x += xdir * xcount;
2487             y += ydir * ycount;
2488             if (x < grid->glyph_x) {
2489                 delta = grid->glyph_x - x;
2490                 grid->glyph_bbx.width += delta;
2491                 grid->glyph_bbx.x_offset -= delta;
2492                 if (grid->spacing == BDF_PROPORTIONAL)
2493                   grid->dwidth += delta;
2494                 grid->glyph_x -= delta;
2495             } else if (x >= grid->glyph_x + grid->glyph_bbx.width) {
2496                 delta = x - (grid->glyph_x + grid->glyph_bbx.width);
2497                 grid->glyph_bbx.width += delta;
2498                 if (grid->spacing == BDF_PROPORTIONAL)
2499                   grid->dwidth += delta;
2500             }
2501
2502             if (y < grid->glyph_y) {
2503                 delta = grid->glyph_y - y;
2504                 grid->glyph_bbx.height += delta;
2505                 grid->glyph_bbx.ascent += delta;
2506                 grid->glyph_y -= delta;
2507             } else if (y + ht >= grid->glyph_y + grid->glyph_bbx.height) {
2508                 delta = (y + ht) - (grid->glyph_y + grid->glyph_bbx.height);
2509                 grid->glyph_bbx.height += delta;
2510                 grid->glyph_bbx.y_offset -= delta;
2511                 grid->glyph_bbx.descent += delta;
2512             }
2513
2514             grid->modified = 1;
2515         }
2516
2517         /*
2518          * Adjust the top-left coordinate of the selection rectangle.
2519          */
2520         grid->sel.x += xdir * xcount;
2521         grid->sel.y += ydir * ycount;
2522
2523         return 1;
2524     }
2525
2526     masks = 0;
2527     switch (grid->bpp) {
2528       case 1: masks = bdf_onebpp; di = 7; break;
2529       case 2: masks = bdf_twobpp; di = 3; break;
2530       case 4: masks = bdf_fourbpp; di = 1; break;
2531       case 8: masks = bdf_eightbpp; di = 0; break;
2532     }
2533
2534     /*
2535      * The glyph itself is being shifted.
2536      */
2537     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2538     bytes = grid->bytes >> 1;
2539     scratch = grid->bitmap + bytes;
2540     (void) memset((char *) scratch, 0, bytes);
2541
2542     /*
2543      * Shift just the glyph rectangle to keep things fast.
2544      */
2545     wd += x;
2546     ht += y;
2547     for (dy = y; dy < ht; dy++) {
2548         col = x * grid->bpp;
2549         for (dx = x; dx < wd; dx++, col += grid->bpp) {
2550             si = (col & 7) / grid->bpp;
2551             byte = grid->bitmap[(dy * bpr) + (col >> 3)] & masks[si];
2552             if (byte) {
2553                 nx = dx + (xdir * xcount);
2554                 ny = dy + (ydir * ycount);
2555                 nx *= grid->bpp;
2556                 di = (nx & 7) / grid->bpp;
2557                 if (di < si)
2558                   byte <<= (si - di) * grid->bpp;
2559                 else if (di > si)
2560                   byte >>= (di - si) * grid->bpp;
2561                 scratch[(ny * bpr) + (nx >> 3)] |= byte;
2562             }
2563         }
2564     }
2565
2566     /*
2567      * Copy the scratch buffer back to the main buffer.
2568      */
2569     (void) memcpy((char *) grid->bitmap, (char *) scratch, bytes);
2570
2571     /*
2572      * Adjust the top-left coordinate of the glyph rectangle.
2573      */
2574     grid->glyph_x += xdir * xcount;
2575     grid->glyph_y += ydir * ycount;
2576
2577     /*
2578      * Adjust the glyph offsets relative to the baseline coordinates.
2579      */
2580     grid->glyph_bbx.x_offset = grid->glyph_x - grid->base_x;
2581     grid->glyph_bbx.y_offset = grid->base_y -
2582         (grid->glyph_y + grid->glyph_bbx.height);
2583
2584     /*
2585      * Adjust the glyph ascent and descent.
2586      */
2587     grid->glyph_bbx.ascent = grid->base_y - grid->glyph_y;
2588     grid->glyph_bbx.descent = (grid->glyph_y + grid->glyph_bbx.height) -
2589         grid->base_y;
2590
2591     /*
2592      * Mark the grid as being modified.
2593      */
2594     grid->modified = 1;
2595
2596     return 1;
2597 }
2598
2599
2600 int
2601 bdf_grid_flip(bdf_glyph_grid_t *grid, short dir)
2602 {
2603     int flipped, sel, delta;
2604     short dx, dy, x, y, nx, ny, wd, ht;
2605     unsigned short bytes, bpr, si, di, col, colx, byte;
2606     unsigned char *bmap, *scratch, *masks;
2607
2608     flipped = 0;
2609
2610     if (grid == 0)
2611       return flipped;
2612
2613     if (grid->sel.width != 0 && grid->sel.height != 0) {
2614         sel = 1;
2615         x = y = 0;
2616         wd = grid->sel.width;
2617         ht = grid->sel.height;
2618         bpr = ((wd * grid->bpp) + 7) >> 3;
2619         bytes = grid->sel.bytes >> 1;
2620         bmap = grid->sel.bitmap;
2621     } else {
2622         sel = 0;
2623         x = grid->glyph_x;
2624         y = grid->glyph_y;
2625         wd = grid->glyph_bbx.width;
2626         ht = grid->glyph_bbx.height;
2627         bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2628         bytes = grid->bytes >> 1;
2629         bmap = grid->bitmap;
2630     }
2631
2632     /*
2633      * If the width or height is 0, don't do anything.
2634      */
2635     if (wd == 0|| ht == 0)
2636       return flipped;
2637
2638     nx = 0;
2639     masks = 0;
2640     switch (grid->bpp) {
2641       case 1: masks = bdf_onebpp; di = 7; break;
2642       case 2: masks = bdf_twobpp; di = 3; break;
2643       case 4: masks = bdf_fourbpp; di = 1; break;
2644       case 8: masks = bdf_eightbpp; di = 0; break;
2645     }
2646
2647     /*
2648      * Set and initialize the scratch area.
2649      */
2650     scratch = bmap + bytes;
2651     (void) memset((char *) scratch, 0, bytes);
2652
2653     wd += x;
2654     ht += y;
2655
2656     if (dir < 0) {
2657         /*
2658          * Flip horizontally.
2659          */
2660         for (dy = y; dy < ht; dy++) {
2661             col = x * grid->bpp;
2662             for (nx = wd - 1, dx = x; dx < wd; dx++, nx--, col += grid->bpp) {
2663                 si = (col & 7) / grid->bpp;
2664                 byte = bmap[(dy * bpr) + (col >> 3)] & masks[si];
2665                 if (byte) {
2666                     flipped = 1;
2667                     colx = nx * grid->bpp;
2668                     di = (colx & 7) / grid->bpp;
2669                     if (di < si)
2670                       byte <<= (si - di) * grid->bpp;
2671                     else if (di > si)
2672                       byte >>= (di - si) * grid->bpp;
2673                     scratch[(dy * bpr) + (colx >> 3)] |= byte;
2674                 }
2675             }
2676         }
2677         if (flipped) {
2678             if (sel)
2679               grid->sel.x += nx + 1;
2680             else {
2681                 grid->glyph_x = nx + 1;
2682                 grid->glyph_bbx.x_offset = grid->glyph_x - grid->base_x;
2683             }
2684         }
2685     } else {
2686         /*
2687          * Flip vertically.
2688          */
2689         for (ny = ht - 1, dy = y; dy < ht; dy++, ny--) {
2690             col = x * grid->bpp;
2691             for (dx = x; dx < wd; dx++, col += grid->bpp) {
2692                 si = (col & 7) / grid->bpp;
2693                 byte = bmap[(dy * bpr) + (col >> 3)] & masks[si];
2694                 if (byte) {
2695                     flipped = 1;
2696                     scratch[(ny * bpr) + (col >> 3)] |= byte;
2697                 }
2698             }
2699         }
2700         if (flipped) {
2701             if (sel)
2702               grid->sel.y += ny + 1;
2703             else {
2704                 grid->glyph_y = ny + 1;
2705                 grid->glyph_bbx.y_offset = grid->base_y -
2706                     (grid->glyph_y + grid->glyph_bbx.height);
2707                 grid->glyph_bbx.ascent = grid->base_y - grid->glyph_y;
2708                 grid->glyph_bbx.descent =
2709                     (grid->glyph_y + grid->glyph_bbx.height) - grid->base_y;
2710             }
2711         }
2712     }
2713
2714     if (flipped) {
2715         /*
2716          * Copy the scratch area back to the working area.
2717          */
2718         if (sel)
2719           (void) memcpy((char *) grid->sel.bitmap, (char *) scratch, bytes);
2720         else
2721           (void) memcpy((char *) grid->bitmap, (char *) scratch, bytes);
2722
2723         if (sel) {
2724             /*
2725              * Check to see if flipping the selection caused the glyph metrics
2726              * to change.
2727              */
2728             if (_bdf_grid_ink_bounds(grid, &x, &y, &wd, &ht)) {
2729                 if (x < grid->glyph_x) {
2730                     delta = grid->glyph_x - x;
2731                     grid->glyph_bbx.width += delta;
2732                     grid->glyph_bbx.x_offset -= delta;
2733                     grid->glyph_x -= delta;
2734                     if (grid->spacing == BDF_PROPORTIONAL)
2735                       grid->dwidth += delta;
2736                 } else if (x >= grid->glyph_x + grid->glyph_bbx.width) {
2737                     delta = x - (grid->glyph_x + grid->glyph_bbx.width);
2738                     grid->glyph_bbx.width += delta;
2739                     if (grid->spacing == BDF_PROPORTIONAL)
2740                       grid->dwidth += delta;
2741                 }
2742
2743                 if (y < grid->glyph_y) {
2744                     delta = grid->glyph_y - y;
2745                     grid->glyph_bbx.height += delta;
2746                     grid->glyph_bbx.ascent += delta;
2747                     grid->glyph_y -= delta;
2748                 } else if (y >= grid->glyph_y + grid->glyph_bbx.height) {
2749                     delta = y - (grid->glyph_y + grid->glyph_bbx.height);
2750                     grid->glyph_bbx.height += delta;
2751                     grid->glyph_bbx.y_offset -= delta;
2752                     grid->glyph_bbx.descent += delta;
2753                 }
2754             }
2755         }
2756
2757         /*
2758          * Mark the grid as being modified.
2759          */
2760         grid->modified = 1;
2761     }
2762
2763     return flipped;
2764 }
2765
2766 void
2767 bdf_grid_origin(bdf_glyph_grid_t *grid, short *x, short *y)
2768 {
2769     if (grid == 0)
2770       return;
2771
2772     *x = grid->base_x;
2773     *y = grid->base_y;
2774 }
2775
2776 bdf_glyph_t *
2777 bdf_grid_glyph(bdf_glyph_grid_t *grid)
2778 {
2779     int len;
2780     short x, y, nx, ny, wd, ht, gx, gy;
2781     unsigned short bpr, nbpr, si, di, col, byte;
2782     bdf_glyph_t *glyph;
2783     unsigned char *masks;
2784     double ps, dw, rx;
2785
2786     if (grid == 0)
2787       return 0;
2788
2789     masks = 0;
2790     switch (grid->bpp) {
2791       case 1: masks = bdf_onebpp; di = 7; break;
2792       case 2: masks = bdf_twobpp; di = 3; break;
2793       case 4: masks = bdf_fourbpp; di = 1; break;
2794       case 8: masks = bdf_eightbpp; di = 0; break;
2795     }
2796
2797     /*
2798      * Create the new glyph.
2799      */
2800     glyph = (bdf_glyph_t *) malloc(sizeof(bdf_glyph_t));
2801     (void) memset((char *) glyph, 0, sizeof(bdf_glyph_t));
2802
2803     gx = grid->glyph_x;
2804     gy = grid->glyph_y;
2805
2806     /*
2807      * Copy the bounding box.
2808      */
2809     (void) memcpy((char *) &glyph->bbx, (char *) &grid->glyph_bbx,
2810                   sizeof(bdf_bbx_t));
2811
2812     /*
2813      * If the font has character-cell spacing, then make sure the bitmap is
2814      * cropped to fit within the bounds of the font bbx.
2815      */
2816     if (grid->spacing == BDF_CHARCELL) {
2817         if (gx < grid->base_x) {
2818             glyph->bbx.x_offset = 0;
2819             glyph->bbx.width -= grid->base_x - gx;
2820             gx += grid->base_x - gx;
2821         }
2822         if (glyph->bbx.width > grid->font_bbx.width)
2823           glyph->bbx.width -= glyph->bbx.width - grid->font_bbx.width;
2824     }
2825
2826     /*
2827      * Set up its bitmap.
2828      */
2829     nbpr = ((glyph->bbx.width * grid->bpp) + 7) >> 3;
2830     glyph->bytes = nbpr * glyph->bbx.height;
2831     glyph->bitmap = (unsigned char *) malloc(glyph->bytes);
2832     (void) memset((char *) glyph->bitmap, 0, glyph->bytes);
2833
2834     /*
2835      * Set the other values.
2836      */
2837     if (grid->name != 0) {
2838         len = strlen(grid->name) + 1;
2839         glyph->name = (char *) malloc(len);
2840         (void) memcpy(glyph->name, grid->name, len);
2841     }
2842     glyph->encoding = grid->encoding;
2843     glyph->dwidth = grid->dwidth;
2844
2845     /*
2846      * Reset the glyph SWIDTH value.
2847      */
2848     ps = (double) grid->point_size;
2849     rx = (double) grid->resolution_x;
2850     dw = (double) grid->dwidth;
2851     glyph->swidth = (unsigned short) ((dw * 72000.0) / (ps * rx));
2852
2853     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
2854     wd = gx + glyph->bbx.width;
2855     ht = gy + glyph->bbx.height;
2856
2857     /*
2858      * Copy the bitmap from the grid into the glyph.
2859      */
2860     for (ny = 0, y = gy; y < ht; y++, ny++) {
2861         col = gx * grid->bpp;
2862         for (nx = 0, x = gx; x < wd; x++, nx += grid->bpp, col += grid->bpp) {
2863             si = (col & 7) / grid->bpp;
2864             byte = grid->bitmap[(y * bpr) + (col >> 3)] & masks[si];
2865             if (byte) {
2866                 di = (nx & 7) / grid->bpp;
2867                 if (di < si)
2868                   byte <<= (si - di) * grid->bpp;
2869                 else if (di > si)
2870                   byte >>= (di - si) * grid->bpp;
2871                 glyph->bitmap[(ny * nbpr) + (nx >> 3)] |= byte;
2872             }
2873         }
2874     }
2875
2876     /*
2877      * Return the new glyph.
2878      */
2879     return glyph;
2880 }
2881
2882 /*
2883  * Create a bitmap with the glyph image as well as the selection.
2884  */
2885 void
2886 bdf_grid_image(bdf_glyph_grid_t *grid, bdf_bitmap_t *image)
2887 {
2888     short x, y, ix, iy;
2889     unsigned short bpr, ibpr, si, di, col, colx, byte;
2890     unsigned char *masks;
2891
2892     if (grid == 0 || image == 0)
2893       return;
2894
2895     masks = 0;
2896     switch (grid->bpp) {
2897       case 1: masks = bdf_onebpp; di = 7; break;
2898       case 2: masks = bdf_twobpp; di = 3; break;
2899       case 4: masks = bdf_fourbpp; di = 1; break;
2900       case 8: masks = bdf_eightbpp; di = 0; break;
2901     }
2902
2903     image->bpp = grid->bpp;
2904     image->x = image->y = 0;
2905     image->width = grid->grid_width;
2906     image->height = grid->grid_height;
2907     image->bytes = grid->bytes >> 1;
2908     image->bitmap = (unsigned char *) malloc(image->bytes);
2909     (void) memcpy((char *) image->bitmap, (char *) grid->bitmap, image->bytes);
2910
2911     /*
2912      * Add the selection to the bitmap if it exists.
2913      */
2914     if (grid->sel.width != 0 && grid->sel.height != 0) {
2915         ibpr = ((image->width * grid->bpp) + 7) >> 3;
2916         bpr = ((grid->sel.width * grid->bpp) + 7) >> 3;
2917         for (iy = grid->sel.y, y = 0; y < grid->sel.height; y++, iy++) {
2918             for (ix = grid->sel.x, col = x = 0; x < grid->sel.width;
2919                  x++, ix++, col += grid->bpp) {
2920                 si = (col & 7) / grid->bpp;
2921                 byte = grid->sel.bitmap[(y * bpr) + (col >> 3)] & masks[si];
2922                 if (byte) {
2923                     colx = ix * grid->bpp;
2924                     di = (colx & 7) / grid->bpp;
2925                     if (di < si)
2926                       byte <<= (si - di) * grid->bpp;
2927                     else if (di > si)
2928                       byte >>= (di - si) * grid->bpp;
2929                     image->bitmap[(iy * ibpr) + (colx >> 3)] |= byte;
2930                 }
2931             }
2932         }
2933     }
2934 }
2935
2936 /*
2937  * These values are intended to give pixels mapped from 1bpp to nbpp the
2938  * darkest available index, which is 1.
2939  */
2940 static unsigned char twobpp_ones[] = {0x40, 0x10, 0x04, 0x01};
2941 static unsigned char fourbpp_ones[] = {0x10, 0x01};
2942 static unsigned char eightbpp_ones[] = {0x01};
2943
2944 /*
2945  * Routines for quick and dirty dithering.
2946  */
2947 static void
2948 _bdf_one_to_n(bdf_bitmap_t *bmap, int n)
2949 {
2950     unsigned short bpr, sbpr, bytes, col, sx, sy;
2951     unsigned char *nbmap, *ones = 0;
2952
2953     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
2954       return;
2955
2956     switch (n) {
2957       case 1: ones = bdf_onebpp; break;
2958       case 2: ones = twobpp_ones; break;
2959       case 4: ones = fourbpp_ones; break;
2960       case 8: ones = eightbpp_ones; break;
2961     }
2962
2963     sbpr = (bmap->width + 7) >> 3;
2964     bpr = ((bmap->width * n) + 7) >> 3;
2965     bytes = bpr * bmap->height;
2966     nbmap = (unsigned char *) malloc(bytes);
2967     (void) memset((char *) nbmap, 0, bytes);
2968
2969     for (sy = 0; sy < bmap->height; sy++) {
2970         for (col = sx = 0; sx < bmap->width; sx++, col += n) {
2971             if (bmap->bitmap[(sy * sbpr) + (sx >> 3)] & (0x80 >> (sx & 7)))
2972               nbmap[(sy * bpr) + (col >> 3)] |= ones[(col & 7) / n];
2973         }
2974     }
2975     free((char *) bmap->bitmap);
2976     bmap->bpp = n;
2977     bmap->bytes = bytes;
2978     bmap->bitmap = nbmap;
2979 }
2980
2981 static void
2982 _bdf_n_to_one(bdf_bitmap_t *bmap)
2983 {
2984     unsigned short bpr, sbpr, bytes, col, sx, sy;
2985     unsigned char *nbmap, *masks;
2986
2987     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
2988       return;
2989
2990     masks = 0;
2991     switch (bmap->bpp) {
2992       case 1: masks = bdf_onebpp; break;
2993       case 2: masks = bdf_twobpp; break;
2994       case 4: masks = bdf_fourbpp; break;
2995       case 8: masks = bdf_eightbpp; break;
2996     }
2997
2998     sbpr = ((bmap->width * bmap->bpp) + 7) >> 3;
2999     bpr = (bmap->width + 7) >> 3;
3000     bytes = bpr * bmap->height;
3001     nbmap = (unsigned char *) malloc(bytes);
3002     (void) memset((char *) nbmap, 0, bytes);
3003
3004     for (sy = 0; sy < bmap->height; sy++) {
3005         for (col = sx = 0; sx < bmap->width; sx++, col += bmap->bpp) {
3006             if (bmap->bitmap[(sy * sbpr) + (col >> 3)] &
3007                 masks[(col & 7) / bmap->bpp])
3008               nbmap[(sy * bpr) + (sx >> 3)] |= (0x80 >> (sx & 7));
3009         }
3010     }
3011     free((char *) bmap->bitmap);
3012     bmap->bpp = 1;
3013     bmap->bytes = bytes;
3014     bmap->bitmap = nbmap;
3015 }
3016
3017 static void
3018 _bdf_two_to_four(bdf_bitmap_t *bmap)
3019 {
3020     unsigned short bpr, sbpr, bytes, col, si, byte, sx, sy;
3021     unsigned char *nbmap, *masks;
3022
3023     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
3024       return;
3025
3026     masks = bdf_twobpp;
3027
3028     sbpr = ((bmap->width << 1) + 7) >> 3;
3029     bpr = ((bmap->width << 2) + 7) >> 3;
3030     bytes = bpr * bmap->height;
3031     nbmap = (unsigned char *) malloc(bytes);
3032     (void) memset((char *) nbmap, 0, bytes);
3033
3034     for (sy = 0; sy < bmap->height; sy++) {
3035         for (col = sx = 0; sx < bmap->width; sx++, col += 2) {
3036             si = (col & 7) >> 1;
3037             byte = bmap->bitmap[(sy * sbpr) + (col >> 3)] & masks[si];
3038             if (byte) {
3039                 /*
3040                  * Shift the byte down to leave the index in the lowest 2
3041                  * bits.
3042                  */
3043                 if (si < 3)
3044                   byte >>= (3 - si) << 1;
3045
3046                 /*
3047                  * Break 16 into 4 groups of 4 and map the 2bpp index to one
3048                  * of those 4.
3049                  */
3050                 bytes <<= 2;
3051                 if ((sx & 1) == 0)
3052                   byte <<= 4;
3053                 nbmap[(sy * bpr) + ((sx << 2) >> 3)] |= byte;
3054             }
3055         }
3056     }
3057     free((char *) bmap->bitmap);
3058     bmap->bpp = 4;
3059     bmap->bytes = bytes;
3060     bmap->bitmap = nbmap;
3061 }
3062
3063 static void
3064 _bdf_four_to_two(bdf_bitmap_t *bmap)
3065 {
3066     unsigned short bpr, sbpr, bytes, col, si, byte, sx, sy;
3067     unsigned char *nbmap, *masks;
3068
3069     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
3070       return;
3071
3072     masks = bdf_fourbpp;
3073
3074     sbpr = ((bmap->width << 2) + 7) >> 3;
3075     bpr = ((bmap->width << 1) + 7) >> 3;
3076     bytes = bpr * bmap->height;
3077     nbmap = (unsigned char *) malloc(bytes);
3078     (void) memset((char *) nbmap, 0, bytes);
3079
3080     for (sy = 0; sy < bmap->height; sy++) {
3081         for (col = sx = 0; sx < bmap->width; sx++, col += 4) {
3082             si = (col & 7) >> 2;
3083             byte = bmap->bitmap[(sy * sbpr) + (col >> 3)] & masks[si];
3084             if (byte) {
3085                 /*
3086                  * Shift the byte down to make an index.
3087                  */
3088                 if (si == 0)
3089                   byte >>= 4;
3090
3091                 /*
3092                  * Scale the index to two bits per pixel and shift it into
3093                  * place if necessary.
3094                  */
3095                 byte >>= 2;
3096                 if (byte == 0)
3097                   byte = 1;
3098
3099                 si = ((sx << 1) & 7) >> 1;
3100                 if (si < 3)
3101                   byte <<= (3 - si) << 1;
3102
3103                 nbmap[(sy * bpr) + ((sx << 1) >> 3)] |= byte;
3104             }
3105         }
3106     }
3107     free((char *) bmap->bitmap);
3108     bmap->bpp = 2;
3109     bmap->bytes = bytes;
3110     bmap->bitmap = nbmap;
3111 }
3112
3113 static void
3114 _bdf_two_to_eight(bdf_bitmap_t *bmap)
3115 {
3116     unsigned short bpr, sbpr, bytes, col, si, byte, sx, sy;
3117     unsigned char *nbmap, *masks;
3118
3119     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
3120       return;
3121
3122     masks = bdf_twobpp;
3123
3124     sbpr = ((bmap->width << 1) + 7) >> 3;
3125     bpr = bmap->width;
3126     bytes = bpr * bmap->height;
3127     nbmap = (unsigned char *) malloc(bytes);
3128     (void) memset((char *) nbmap, 0, bytes);
3129
3130     for (sy = 0; sy < bmap->height; sy++) {
3131         for (col = sx = 0; sx < bmap->width; sx++, col += 2) {
3132             si = (col & 7) >> 1;
3133             byte = bmap->bitmap[(sy * sbpr) + (col >> 3)] & masks[si];
3134             if (byte) {
3135                 /*
3136                  * Shift the byte down to leave the index in the lowest 2
3137                  * bits.
3138                  */
3139                 if (si < 3)
3140                   byte >>= (3 - si) << 1;
3141
3142                 /*
3143                  * Break 256 into 4 groups of 64 and map the 2bpp index to one
3144                  * of those 4.
3145                  */
3146                 byte <<= 6;
3147                 nbmap[(sy * bpr) + sx] = byte;
3148             }
3149         }
3150     }
3151     free((char *) bmap->bitmap);
3152     bmap->bpp = 8;
3153     bmap->bytes = bytes;
3154     bmap->bitmap = nbmap;
3155 }
3156
3157 static void
3158 _bdf_eight_to_two(bdf_bitmap_t *bmap)
3159 {
3160     unsigned short bpr, sbpr, bytes, si, byte, sx, sy;
3161     unsigned char *nbmap;
3162
3163     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
3164       return;
3165
3166     sbpr = bmap->width;
3167     bpr = ((bmap->width << 1) + 7) >> 3;
3168     bytes = bpr * bmap->height;
3169     nbmap = (unsigned char *) malloc(bytes);
3170     (void) memset((char *) nbmap, 0, bytes);
3171
3172     for (sy = 0; sy < bmap->height; sy++) {
3173         for (sx = 0; sx < bmap->width; sx++) {
3174             byte = bmap->bitmap[(sy * sbpr) + sx];
3175             if (byte) {
3176                 /*
3177                  * Scale the index to two bits per pixel and shift it into
3178                  * place if necessary.
3179                  */
3180                 byte >>= 6;
3181                 if (byte == 0)
3182                   byte = 1;
3183
3184                 si = ((sx << 1) & 7) >> 1;
3185                 if (si < 3)
3186                   byte <<= (3 - si) << 1;
3187
3188                 nbmap[(sy * bpr) + ((sx << 1) >> 3)] |= byte;
3189             }
3190         }
3191     }
3192     free((char *) bmap->bitmap);
3193     bmap->bpp = 2;
3194     bmap->bytes = bytes;
3195     bmap->bitmap = nbmap;
3196 }
3197
3198 static void
3199 _bdf_four_to_eight(bdf_bitmap_t *bmap)
3200 {
3201     unsigned short bpr, sbpr, bytes, col, si, byte, sx, sy;
3202     unsigned char *nbmap, *masks;
3203
3204     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
3205       return;
3206
3207     masks = bdf_fourbpp;
3208
3209     sbpr = ((bmap->width << 2) + 7) >> 3;
3210     bpr = bmap->width;
3211     bytes = bpr * bmap->height;
3212     nbmap = (unsigned char *) malloc(bytes);
3213     (void) memset((char *) nbmap, 0, bytes);
3214
3215     for (sy = 0; sy < bmap->height; sy++) {
3216         for (col = sx = 0; sx < bmap->width; sx++, col += 4) {
3217             si = (col & 7) >> 2;
3218             byte = bmap->bitmap[(sy * sbpr) + (col >> 3)] & masks[si];
3219             if (byte) {
3220                 /*
3221                  * Shift the byte down to make an index.
3222                  */
3223                 if (si == 0)
3224                   byte >>= 4;
3225
3226                 /*
3227                  * Multiply by 16 to get the 8bpp index.
3228                  */
3229                 byte <<= 4;
3230
3231                 nbmap[(sy * bpr) + sx] = byte;
3232             }
3233         }
3234     }
3235     free((char *) bmap->bitmap);
3236     bmap->bpp = 8;
3237     bmap->bytes = bytes;
3238     bmap->bitmap = nbmap;
3239 }
3240
3241 static void
3242 _bdf_eight_to_four(bdf_bitmap_t *bmap)
3243 {
3244     unsigned short bpr, sbpr, bytes, col, si, byte, sx, sy;
3245     unsigned char *nbmap;
3246
3247     if (bmap == 0 || bmap->width == 0 || bmap->height == 0)
3248       return;
3249
3250     sbpr = bmap->width;
3251     bpr = ((bmap->width << 2) + 7) >> 3;
3252     bytes = bpr * bmap->height;
3253     nbmap = (unsigned char *) malloc(bytes);
3254     (void) memset((char *) nbmap, 0, bytes);
3255
3256     for (sy = 0; sy < bmap->height; sy++) {
3257         for (col = sx = 0; sx < bmap->width; sx++, col += 4) {
3258             byte = bmap->bitmap[(sy * sbpr) + sx];
3259             if (byte) {
3260                 /*
3261                  * Divide the index by 16 to determine which 4bpp index
3262                  * it will be.
3263                  */
3264                 byte >>= 4;
3265                 if (byte == 0)
3266                   byte = 1;
3267
3268                 /*
3269                  * Shift the bits up by 4 if the index is even.
3270                  */
3271                 si = (col & 7) >> 2;
3272                 if (si == 0)
3273                   byte <<= 4;
3274
3275                 nbmap[(sy * bpr) + ((sx << 2) >> 3)] |= byte;
3276             }
3277         }
3278     }
3279     free((char *) bmap->bitmap);
3280     bmap->bpp = 4;
3281     bmap->bytes = bytes;
3282     bmap->bitmap = nbmap;
3283 }
3284
3285 /*
3286  * Add a bitmap to a grid as a selection.
3287  */
3288 void
3289 bdf_add_selection(bdf_glyph_grid_t *grid, bdf_bitmap_t *sel)
3290 {
3291     unsigned short bytes, bpr;
3292
3293     if (grid == 0 || sel == 0 || sel->width == 0 || sel->height == 0 ||
3294         sel->bytes == 0)
3295       return;
3296
3297     if (sel->bpp != grid->bpp) {
3298         /*
3299          * Dither the incoming bitmap to match the same bits per pixel as the
3300          * grid it is being added to.
3301          */
3302         if (sel->bpp == 1)
3303           _bdf_one_to_n(sel, grid->bpp);
3304         else if (grid->bpp == 1)
3305           _bdf_n_to_one(sel);
3306         else if (sel->bpp == 2) {
3307             if (grid->bpp == 4)
3308               _bdf_two_to_four(sel);
3309             else
3310               _bdf_two_to_eight(sel);
3311         } else if (sel->bpp == 4) {
3312             if (grid->bpp == 2)
3313               _bdf_four_to_two(sel);
3314             else
3315               _bdf_four_to_eight(sel);
3316         } else if (sel->bpp == 8) {
3317             if (grid->bpp == 2)
3318               _bdf_eight_to_two(sel);
3319             else
3320               _bdf_eight_to_four(sel);
3321         }
3322     }
3323
3324     /*
3325      * If the bitmap is too big then trim the right and/or the bottom to fit
3326      * in the grid.
3327      */
3328     if (sel->width > grid->grid_width)
3329       sel->width = grid->grid_width;
3330     if (sel->height > grid->grid_height)
3331       sel->height = grid->grid_height;
3332
3333     /*
3334      * If the positioning puts the selection bitmap off one of the edges,
3335      * adjust it so it is completely on the grid.
3336      */
3337     if (sel->x + sel->width > grid->grid_width)
3338       sel->x -= (sel->x + sel->width) - grid->grid_width;
3339     if (sel->y + sel->height > grid->grid_height)
3340       sel->y -= (sel->y + sel->height) - grid->grid_height;
3341
3342     bpr = ((sel->width * grid->bpp) + 7) >> 3;
3343     bytes = (bpr * sel->height) << 1;
3344
3345     /*
3346      * Resize the storage for the selection bitmap if necessary.
3347      */
3348     if (bytes > grid->sel.bytes) {
3349         if (grid->sel.bytes == 0)
3350           grid->sel.bitmap = (unsigned char *) malloc(bytes);
3351         else
3352           grid->sel.bitmap = (unsigned char *)
3353               realloc((char *) grid->sel.bitmap, bytes);
3354         grid->sel.bytes = bytes;
3355     }
3356
3357     /*
3358      * Copy the width and height values.
3359      */
3360     grid->sel.x = sel->x;
3361     grid->sel.y = sel->y;
3362     grid->sel.width = sel->width;
3363     grid->sel.height = sel->height;
3364
3365     /*
3366      * Copy the incoming bitmap to the new selection bitmap.
3367      */
3368     (void) memcpy((char *) grid->sel.bitmap, (char *) sel->bitmap,
3369                   bytes >> 1);
3370
3371     /*
3372      * Crop the image to adjust the glyph bounding box.
3373      */
3374     (void) bdf_grid_crop(grid, 1);
3375 }
3376
3377 int
3378 bdf_grid_color_at(bdf_glyph_grid_t *grid, short x, short y)
3379 {
3380     unsigned short bpr, si, di, byte;
3381     unsigned char *masks = 0;
3382
3383     if (grid->bpp == 1)
3384       return -1;
3385
3386     di = 0;
3387     switch (grid->bpp) {
3388       case 2: masks = bdf_twobpp; di = 3; break;
3389       case 4: masks = bdf_fourbpp; di = 1; break;
3390       case 8: masks = bdf_eightbpp; di = 0; break;
3391     }
3392
3393     x *= grid->bpp;
3394
3395     bpr = ((grid->grid_width * grid->bpp) + 7) >> 3;
3396     si = (x & 7) / grid->bpp;
3397
3398     byte = grid->bitmap[(y * bpr) + (x >> 3)] & masks[si];
3399     if (di > si)
3400       byte >>= (di - si) * grid->bpp;
3401     return (int) byte;
3402 }