home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / GXCCMAN.C < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-31  |  22.7 KB  |  718 lines
  1. /* Copyright (C) 1989, 1992, 1993, 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxccman.c */
  20. /* Character cache management routines for Ghostscript library */
  21. #include "gx.h"
  22. #include "memory_.h"
  23. #include "gpcheck.h"
  24. #include "gserrors.h"
  25. #include "gsstruct.h"
  26. #include "gsutil.h"            /* for gs_next_ids */
  27. #include "gxfixed.h"
  28. #include "gxmatrix.h"
  29. #include "gzstate.h"
  30. #include "gzpath.h"
  31. #include "gxdevmem.h"
  32. #include "gxchar.h"
  33. #include "gxfont.h"
  34. #include "gxfcache.h"
  35. #include "gxxfont.h"
  36.  
  37. /* Define the descriptors for the cache structures. */
  38. private_st_cached_fm_pair();
  39. private_st_cached_fm_pair_elt();
  40. /*private_st_cached_char();*/        /* unused */
  41. private_st_cached_char_ptr();
  42. private_st_cached_char_ptr_elt();
  43. /* GC procedures */
  44. #define cptr ((cached_char *)vptr)
  45. private ENUM_PTRS_BEGIN(cached_char_enum_ptrs) return 0;
  46.     case 0:
  47.       *pep = (cc_is_free(cptr) ? NULL :
  48.           (void *)(cptr->head.pair - cptr->head.pair->index));
  49.       break;
  50. ENUM_PTRS_END
  51. private RELOC_PTRS_BEGIN(cached_char_reloc_ptrs) {
  52.     uint offset;
  53.     if ( cc_is_free(cptr) )
  54.       return;
  55.     offset = cptr->head.pair->index * sizeof(cached_fm_pair);
  56.     RELOC_OFFSET_PTR(cached_char, head.pair, offset);
  57. } RELOC_PTRS_END
  58. #undef cptr
  59. private ENUM_PTRS_BEGIN_PROC(cc_ptr_enum_ptrs) {
  60.     cached_char *cptr = *(cached_char **)vptr;
  61.     if ( cptr == 0 )
  62.       return 0;
  63.     return cached_char_enum_ptrs(cptr, cptr->head.size, index, pep);
  64. } ENUM_PTRS_END_PROC
  65. private RELOC_PTRS_BEGIN(cc_ptr_reloc_ptrs) {
  66.     cached_char *cptr = *(cached_char **)vptr;
  67.     if ( cptr != 0 )
  68.       cached_char_reloc_ptrs(cptr, cptr->head.size, gcst);
  69. } RELOC_PTRS_END
  70.  
  71. /* Forward references */
  72. private gx_xfont *lookup_xfont_by_name(P6(gx_device *, gx_xfont_procs *, gs_font_name *, int, const cached_fm_pair *, const gs_matrix *));
  73. private cached_char *alloc_char_in_chunk(P4(gs_font_dir *, ulong, char_cache_chunk *, uint));
  74. private void shorten_cached_char(P3(gs_font_dir *, cached_char *, uint));
  75. private void image_bbox(P4(const byte *, uint, uint, gs_int_rect *));
  76. private uint compress_scaled_bits(P4(byte *, uint, uint, const gs_log2_scale_point *));
  77.  
  78. /* ====== Initialization ====== */
  79.  
  80. /* Allocate and initialize the character cache elements of a font directory. */
  81. int
  82. gx_char_cache_alloc(gs_memory_t *mem, register gs_font_dir *pdir,
  83.   uint bmax, uint mmax, uint cmax, uint upper)
  84. {    uint chsize = (cmax / 5) | 31;        /* a guess */
  85.     cached_fm_pair *mdata;
  86.     cached_char **chars;
  87.     /* Round up chsize to a power of 2. */
  88.     while ( chsize & (chsize + 1) )
  89.       chsize |= chsize >> 1;
  90.     chsize++;
  91.     mdata = gs_alloc_struct_array(mem, mmax, cached_fm_pair,
  92.                       &st_cached_fm_pair_element,
  93.                       "font_dir_alloc(mdata)");
  94.     chars = gs_alloc_struct_array(mem, chsize, cached_char *,
  95.                       &st_cached_char_ptr_element,
  96.                       "font_dir_alloc(chars)");
  97.     if ( mdata == 0 || chars == 0 )
  98.     {    gs_free_object(mem, chars, "font_dir_alloc(chars)");
  99.         gs_free_object(mem, mdata, "font_dir_alloc(mdata)");
  100.         return_error(gs_error_VMerror);
  101.     }
  102.     pdir->fmcache.mmax = mmax;
  103.     pdir->fmcache.mdata = mdata;
  104.     pdir->ccache.memory = mem;
  105.     pdir->ccache.bmax = bmax;
  106.     pdir->ccache.cmax = cmax;
  107.     pdir->ccache.lower = upper / 10;
  108.     pdir->ccache.upper = upper;
  109.     pdir->ccache.chars = chars;
  110.     pdir->ccache.chars_mask = chsize - 1;
  111.     gx_char_cache_init(pdir);
  112.     return 0;
  113. }
  114.  
  115. /* Initialize the character cache. */
  116. void
  117. gx_char_cache_init(register gs_font_dir *dir)
  118. {    int i;
  119.     cached_fm_pair *pair;
  120.     dir->fmcache.msize = 0;
  121.     dir->fmcache.mnext = 0;
  122.     dir->ccache.bsize = 0;
  123.     dir->ccache.csize = 0;
  124.     dir->ccache.bspace = 0;
  125.     dir->ccache.initial_chunk =
  126.         (char_cache_chunk *)gs_malloc(1, sizeof(char_cache_chunk),
  127.                            "initial_chunk");
  128.     dir->ccache.chunks = dir->ccache.initial_chunk->next =
  129.         dir->ccache.initial_chunk;
  130.     dir->ccache.initial_chunk->size = 0;
  131.     dir->ccache.cnext = 0;
  132.     memset((char *)dir->ccache.chars, 0,
  133.            (dir->ccache.chars_mask + 1) * sizeof(cached_char *));
  134.     for ( i = 0, pair = dir->fmcache.mdata;
  135.           i < dir->fmcache.mmax; i++, pair++
  136.         )
  137.     {    pair->index = i;
  138.         fm_pair_init(pair);
  139.     }
  140. }
  141.  
  142. /* ====== Purging ====== */
  143.  
  144. /* Purge from the character cache all entries selected by */
  145. /* a client-supplied procedure. */
  146. void
  147. gx_purge_selected_cached_chars(gs_font_dir *dir,
  148.   bool (*proc)(P2(cached_char *, void *)), void *proc_data)
  149. {    int chi;
  150.     for ( chi = dir->ccache.chars_mask; chi >= 0; )
  151.     {    cached_char **pcc = dir->ccache.chars + chi--;
  152.         while ( *pcc != 0 )
  153.         {    cached_char *cc = *pcc;
  154.             if ( (*proc)(cc, proc_data) )
  155.             {    cached_char *ccnext = cc->next;
  156.                 gx_free_cached_char(dir, cc);
  157.                 *pcc = ccnext;
  158.             }
  159.             else
  160.                 pcc = &cc->next;
  161.         }
  162.     }
  163. }
  164.  
  165. /* ====== Font-level routines ====== */
  166.  
  167. /* Add a font/matrix pair to the cache. */
  168. /* (This is only exported for gxccache.c.) */
  169. cached_fm_pair *
  170. gx_add_fm_pair(register gs_font_dir *dir, gs_font *font, const gs_uid *puid,
  171.   const gs_state *pgs)
  172. {    register cached_fm_pair *pair =
  173.         dir->fmcache.mdata + dir->fmcache.mnext;
  174.     cached_fm_pair *mend =
  175.         dir->fmcache.mdata + dir->fmcache.mmax;
  176.     if ( dir->fmcache.msize == dir->fmcache.mmax ) /* cache is full */
  177.     {    /* Prefer an entry with num_chars == 0, if any. */
  178.         int count;
  179.         for ( count = dir->fmcache.mmax;
  180.               --count >= 0 && pair->num_chars != 0;
  181.             )
  182.             if ( ++pair == mend ) pair = dir->fmcache.mdata;
  183.         gs_purge_fm_pair(dir, pair, 0);
  184.     }
  185.     else
  186.     {    /* Look for an empty entry.  (We know there is one.) */
  187.         while ( !fm_pair_is_free(pair) )
  188.             if ( ++pair == mend ) pair = dir->fmcache.mdata;
  189.     }
  190.     dir->fmcache.msize++;
  191.     dir->fmcache.mnext = pair + 1 - dir->fmcache.mdata;
  192.     if ( dir->fmcache.mnext == dir->fmcache.mmax )
  193.         dir->fmcache.mnext = 0;
  194.     pair->font = font;
  195.     pair->UID = *puid;
  196.     pair->mxx = pgs->char_tm.xx, pair->mxy = pgs->char_tm.xy;
  197.     pair->myx = pgs->char_tm.yx, pair->myy = pgs->char_tm.yy;
  198.     pair->num_chars = 0;
  199.     pair->xfont_tried = false;
  200.     pair->xfont = 0;
  201.     if_debug8('k', "[k]adding pair 0x%lx: font=0x%lx [%g %g %g %g] UID %ld, 0x%lx\n",
  202.           (ulong)pair, (ulong)font,
  203.           pair->mxx, pair->mxy, pair->myx, pair->myy,
  204.           (long)pair->UID.id, (ulong)pair->UID.xvalues);
  205.     return pair;
  206. }
  207.  
  208. /* Look up the xfont for a font/matrix pair. */
  209. /* (This is only exported for gxccache.c.) */
  210. void
  211. gx_lookup_xfont(const gs_state *pgs, cached_fm_pair *pair, int encoding_index)
  212. {    gx_device *dev = gs_currentdevice(pgs);
  213.     gx_device *fdev = (*dev_proc(dev, get_xfont_device))(dev);
  214.     gs_font *font = pair->font;
  215.     gx_xfont_procs *procs = (*dev_proc(fdev, get_xfont_procs))(fdev);
  216.     gx_xfont *xf = 0;
  217.     if ( procs != 0 )
  218.     {    gs_matrix mat;
  219.         mat.xx = pair->mxx, mat.xy = pair->mxy;
  220.         mat.yx = pair->myx, mat.yy = pair->myy;
  221.         /* xfonts can outlive their invocations, */
  222.         /* but restore purges them properly. */
  223.         pair->memory = pgs->memory;
  224.         if ( font->key_name.size != 0 )
  225.             xf = lookup_xfont_by_name(fdev, procs,
  226.                 &font->key_name, encoding_index,
  227.                 pair, &mat);
  228. #define font_name_eq(pfn1,pfn2)\
  229.   ((pfn1)->size == (pfn2)->size &&\
  230.    !memcmp((char *)(pfn1)->chars, (char *)(pfn2)->chars, (pfn1)->size))
  231.         if ( xf == 0 && font->font_name.size != 0 &&
  232.                  /* Avoid redundant lookup */
  233.              !font_name_eq(&font->font_name, &font->key_name)
  234.            )
  235.             xf = lookup_xfont_by_name(fdev, procs,
  236.                 &font->font_name, encoding_index,
  237.                 pair, &mat);
  238.         if ( xf == 0 & font->FontType != ft_composite &&
  239.              uid_is_valid(&((gs_font_base *)font)->UID)
  240.            )
  241.         {    /* Look for an original font with the same UID. */
  242.             gs_font_dir *pdir = font->dir;
  243.             gs_font *pfont;
  244.             for ( pfont = pdir->orig_fonts; pfont != 0;
  245.                   pfont = pfont->next
  246.                 )
  247.             {    if ( pfont->FontType != ft_composite &&
  248.                      uid_equal(&((gs_font_base *)pfont)->UID,
  249.                            &((gs_font_base *)font)->UID) &&
  250.                      pfont->key_name.size != 0 &&
  251.                      !font_name_eq(&font->key_name,
  252.                                &pfont->key_name)
  253.                    )
  254.                 {    xf = lookup_xfont_by_name(fdev, procs,
  255.                         &pfont->key_name,
  256.                         encoding_index, pair, &mat);
  257.                     if ( xf != 0 )
  258.                         break;
  259.                 }
  260.             }
  261.         }
  262.     }
  263.     pair->xfont = xf;
  264. }
  265.  
  266. /* ------ Internal routines ------ */
  267.  
  268. /* Purge from the caches all references to a given font/matrix pair, */
  269. /* or just characters that depend on its xfont. */
  270. #define cpair ((cached_fm_pair *)vpair)
  271. private bool
  272. purge_fm_pair_char(cached_char *cc, void *vpair)
  273. {    return cc->head.pair == cpair;
  274. }
  275. private bool
  276. purge_fm_pair_char_xfont(cached_char *cc, void *vpair)
  277. {    return cc->head.pair == cpair && cpair->xfont == 0 && !cc_has_bits(cc);
  278. }
  279. #undef cpair
  280. void
  281. gs_purge_fm_pair(gs_font_dir *dir, cached_fm_pair *pair, int xfont_only)
  282. {    if_debug2('k', "[k]purging pair 0x%lx%s\n",
  283.           (ulong)pair, (xfont_only ? " (xfont only)" : ""));
  284.     if ( pair->xfont != 0 )
  285.     {    (*pair->xfont->common.procs->release)(pair->xfont,
  286.             pair->memory);
  287.         pair->xfont_tried = false;
  288.         pair->xfont = 0;
  289.     }
  290.     gx_purge_selected_cached_chars(dir,
  291.                        (xfont_only ? purge_fm_pair_char_xfont :
  292.                     purge_fm_pair_char),
  293.                        pair);
  294.     if ( !xfont_only )
  295.     {
  296. #ifdef DEBUG
  297.         if ( pair->num_chars != 0 )
  298.         {    lprintf1("Error in gs_purge_fm_pair: num_chars =%d\n",
  299.                  pair->num_chars);
  300.         }
  301. #endif
  302.         fm_pair_set_free(pair);
  303.         dir->fmcache.msize--;
  304.     }
  305. }
  306.  
  307. /* Look up an xfont by name. */
  308. /* The caller must already have done get_xfont_device to get the proper */
  309. /* device to pass as the first argument to lookup_font. */
  310. private gx_xfont *
  311. lookup_xfont_by_name(gx_device *fdev, gx_xfont_procs *procs,
  312.   gs_font_name *pfstr, int encoding_index, const cached_fm_pair *pair,
  313.   const gs_matrix *pmat)
  314. {    gx_xfont *xf;
  315.     if_debug5('k', "[k]lookup xfont %s [%g %g %g %g]\n",
  316.           pfstr->chars, pmat->xx, pmat->xy, pmat->yx, pmat->yy);
  317.     xf = (*procs->lookup_font)(fdev,
  318.         &pfstr->chars[0], pfstr->size,
  319.         encoding_index, &pair->UID,
  320.         pmat, pair->memory);
  321.     if_debug1('k', "[k]... xfont=0x%lx\n", (ulong)xf);
  322.     return xf;
  323. }
  324.  
  325. /* ====== Character-level routines ====== */
  326.  
  327. /* Allocate storage for caching a rendered character. */
  328. /* If dev != NULL set up the memory device; */
  329. /* if dev == NULL, this is an xfont-only entry. */
  330. /* Return the cached_char if OK, 0 if too big. */
  331. cached_char *
  332. gx_alloc_char_bits(gs_font_dir *dir, gx_device_memory *dev,
  333.   ushort iwidth, ushort iheight)
  334. {    ulong isize, icdsize;
  335.     uint iraster;
  336.     char_cache_chunk *cck;
  337.     cached_char *cc;
  338.     gx_device_memory mdev;
  339.     gx_device_memory *pdev = dev;
  340.     if ( dev == NULL )
  341.     {    gs_make_mem_mono_device(&mdev, 0);
  342.         pdev = &mdev;
  343.     }
  344.     pdev->width = iwidth;
  345.     pdev->height = iheight;
  346.     iraster = gdev_mem_raster(pdev);
  347.     if ( iraster != 0 && iheight > dir->ccache.upper / iraster )
  348.         return 0;        /* too big */
  349.     isize = gdev_mem_bitmap_size(pdev);
  350.     icdsize = isize + sizeof_cached_char;
  351.     /* Try allocating at the current position first. */
  352.     cck = dir->ccache.chunks;
  353.     cc = alloc_char_in_chunk(dir, icdsize, cck, dir->ccache.cnext);
  354.     if ( cc == 0 )
  355.     {    if ( dir->ccache.bspace < dir->ccache.bmax )
  356.         {    /* Allocate another chunk. */
  357.             char_cache_chunk *cck_prev = cck;
  358.             uint cksize = dir->ccache.bmax / 5 + 1;
  359.             uint tsize = dir->ccache.bmax - dir->ccache.bspace;
  360.             byte *cdata;
  361.             if ( cksize > tsize )
  362.                 cksize = tsize;
  363.             if ( icdsize + sizeof(cached_char_head) > cksize )
  364.                 return 0;        /* wouldn't fit */
  365.             cck = (char_cache_chunk *)gs_malloc(1, sizeof(*cck),
  366.                             "char cache chunk");
  367.             if ( cck == 0 )
  368.                 return 0;
  369.             cdata = (byte *)gs_malloc(cksize, 1,
  370.                           "char cache chunk");
  371.             if ( cdata == 0 )
  372.             {    gs_free((char *)cck, 1, sizeof(*cck),
  373.                     "char cache chunk");
  374.                 return 0;
  375.             }
  376.             cck->data = cdata;
  377.             cck->size = cksize;
  378.             cck->next = cck_prev->next;
  379.             cck_prev->next = cck;
  380.             dir->ccache.bspace += cksize;
  381.             ((cached_char_head *)cdata)->size = cksize;
  382.             ((cached_char_head *)cdata)->pair = 0;
  383.             cc = alloc_char_in_chunk(dir, icdsize, cck, 0);
  384.         }
  385.         else
  386.         {    /* Cycle through chunks. */
  387.             char_cache_chunk *cck_init = cck;
  388.             while ( (cck = cck->next) != cck_init )
  389.             {    cc = alloc_char_in_chunk(dir, icdsize, cck, 0);
  390.                 if ( cc != 0 ) break;
  391.             }
  392.             if ( cc == 0 )
  393.                 cc = alloc_char_in_chunk(dir, icdsize, cck, 0);
  394.         }
  395.         if ( cc == 0 )
  396.             return 0;
  397.         dir->ccache.chunks = cck;    /* update roving pointer */
  398.     }
  399.     if_debug4('k', "[k]adding char 0x%lx:%u(%u,%u)\n",
  400.           (ulong)cc, (uint)icdsize, iwidth, iheight);
  401.     cc->xglyph = gx_no_xglyph;
  402.     cc->width = iwidth;
  403.     cc->height = iheight;
  404.     cc->raster = iraster;
  405.     cc->head.pair = 0;    /* not linked in yet */
  406.     cc->id = gx_no_bitmap_id;
  407.     if ( dev != NULL )
  408.         gx_open_cache_device(dev, cc);
  409.     return cc;
  410. }
  411.  
  412. /* Open the cache device. */
  413. void
  414. gx_open_cache_device(gx_device_memory *dev, cached_char *cc)
  415. {    byte *bits = cc_bits(cc);
  416.     dev->width = cc->width;
  417.     dev->height = cc->height;
  418.     memset((char *)bits, 0, (uint)gdev_mem_bitmap_size(dev));
  419.     dev->base = bits;
  420.     (*dev_proc(dev, open_device))((gx_device *)dev);    /* initialize */
  421. }
  422.  
  423. /* Remove a character from the cache. */
  424. void
  425. gx_free_cached_char(gs_font_dir *dir, cached_char *cc)
  426. {    char_cache_chunk *cck = cc->chunk;
  427.     dir->ccache.chunks = cck;
  428.     dir->ccache.cnext = (byte *)cc - cck->data;
  429.     dir->ccache.csize--;
  430.     dir->ccache.bsize -= cc->head.size;
  431.     if ( cc->head.pair != 0 )
  432.        {    /* might be allocated but not added to table yet */
  433.         cc->head.pair->num_chars--;
  434.        }
  435.     if_debug2('k', "[k]freeing char 0x%lx, pair=0x%lx\n",
  436.           (ulong)cc, (ulong)cc->head.pair);
  437.     cc_set_free(cc);
  438. }
  439.  
  440. /* Add a character to the cache */
  441. void
  442. gx_add_cached_char(gs_font_dir *dir, gx_device_memory *dev,
  443.   cached_char *cc, cached_fm_pair *pair, const gs_log2_scale_point *pscale)
  444. {    if_debug5('k', "[k]chaining char 0x%lx: pair=0x%lx, glyph=0x%lx, wmode=%d, depth=%d\n",
  445.           (ulong)cc, (ulong)pair, (ulong)cc->code,
  446.           cc->wmode, cc->depth);
  447.     if ( dev != NULL )
  448.         gx_add_char_bits(dir, dev, cc, pscale);
  449.     /* Add the new character at the tail of its chain. */
  450.     {    register cached_char **head =
  451.           chars_head(dir, cc->code, pair);
  452.         while ( *head != 0 ) head = &(*head)->next;
  453.         *head = cc;
  454.         cc->next = 0;
  455.         cc->head.pair = pair;
  456.         pair->num_chars++;
  457.     }
  458. }
  459.  
  460. /* Adjust the bits of a newly-rendered character, by unscaling */
  461. /* and/or compressing. */
  462. void
  463. gx_add_char_bits(gs_font_dir *dir, gx_device_memory *dev,
  464.   cached_char *cc, const gs_log2_scale_point *plog2_scale)
  465. {    uint raster, bsize, nraster;
  466.     byte *bits = cc_bits(cc);
  467.     gs_int_rect bbox;
  468.     /* If the character was oversampled, compress it now. */
  469.     if ( plog2_scale->x != 0 || plog2_scale->y != 0 )
  470.     {    if_debug4('k', "[k]compressing %dx%d by %dx%d\n",
  471.               cc->width, cc->height,
  472.               1 << plog2_scale->x, 1 << plog2_scale->y);
  473.         cc->raster = compress_scaled_bits(bits, cc->width,
  474.                           cc->height, plog2_scale);
  475.         cc->width >>= plog2_scale->x;
  476.         cc->height >>= plog2_scale->y;
  477.     }
  478.     raster = cc->raster;
  479.     /* Compress the character further by removing */
  480.     /* white space around the edges. */
  481.     image_bbox(bits, cc->height, raster, &bbox);
  482.     cc->height = bbox.q.y - bbox.p.y;
  483.     bsize = raster * cc->height;
  484.     if ( bbox.p.y != 0 )
  485.       {    /* Move the bits down. */
  486.         memmove(bits, bits + bbox.p.y * raster, bsize);
  487.         cc->offset.y -= int2fixed(bbox.p.y);
  488.       }
  489.     /* We'd like to trim off left and right blank space too, */
  490.     /* but currently we're only willing to move bytes, not bits. */
  491.     bbox.p.x &= ~7;
  492.     nraster = bitmap_raster(bbox.q.x - bbox.p.x);
  493.     if ( nraster < raster )
  494.       {    /* Move the bits over. */
  495.         register byte *to = bits;
  496.         register const byte *from = bits + (bbox.p.x >> 3);
  497.         uint n = cc->height;
  498.         for ( ; n--; from += raster, to += nraster )
  499.           memmove(to, from, nraster);
  500.         cc->raster = raster = nraster;
  501.         bsize = raster * cc->height;
  502.         cc->offset.x -= int2fixed(bbox.p.x);
  503.         cc->width = bbox.q.x - bbox.p.x;
  504.       }
  505.     /* Discard the memory device overhead that follows the bits, */
  506.     /* and any space reclaimed from unscaling or compression. */
  507.     {    uint diff = round_down(gdev_mem_bitmap_size(dev) - bsize,
  508.                     align_cached_char_mod);
  509.         if ( diff >= sizeof(cached_char_head) )
  510.         {    shorten_cached_char(dir, cc, diff);
  511.             dir->ccache.bsize -= diff;
  512.             if_debug2('K', "[K]shortening char 0x%lx by %u (mdev overhead)\n",
  513.                   (ulong)cc, diff);
  514.         }
  515.     }
  516.     /* Assign a bitmap id. */
  517.     cc->id = gs_next_ids(1);
  518. }
  519.  
  520. /* Purge from the caches all references to a given font. */
  521. void
  522. gs_purge_font_from_char_caches(gs_font_dir *dir, const gs_font *font)
  523. {    cached_fm_pair *pair = dir->fmcache.mdata;
  524.     int count = dir->fmcache.mmax;
  525.     if_debug1('k', "[k]purging font 0x%lx\n",
  526.           (ulong)font);
  527.     while ( count-- )
  528.     {    if ( pair->font == font )
  529.         {    if ( uid_is_valid(&pair->UID) )
  530.             {    /* Keep the entry. */
  531.                 pair->font = 0;
  532.             }
  533.             else
  534.                 gs_purge_fm_pair(dir, pair, 0);
  535.         }
  536.         pair++;
  537.     }
  538. }
  539.  
  540. /* ------ Internal routines ------ */
  541.  
  542. /* Allocate a character in a given chunk, which the caller will make */
  543. /* (or ensure) current. */
  544. private cached_char *
  545. alloc_char_in_chunk(gs_font_dir *dir, ulong icdsize,
  546.   char_cache_chunk *cck, uint cnext)
  547. {    uint cdsize;
  548.     cached_char_head *cch;
  549. #define hcc ((cached_char *)cch)
  550.     cached_char *cc;
  551.     uint fsize = 0;
  552.     if ( icdsize + sizeof(cached_char_head) > cck->size - cnext )
  553.     {    /* Not enough room to allocate here. */
  554.         return 0;
  555.     }
  556.     cdsize = (uint)icdsize;
  557.     /* Look for and/or free enough space. */
  558.     cch = (cached_char_head *)(cck->data + cnext);
  559.     cc = hcc;
  560.     while ( !(fsize == cdsize ||
  561.           fsize >= cdsize + sizeof(cached_char_head))
  562.           )
  563.     {    if ( !cc_head_is_free(cch) )
  564.         {    /* Free the character */
  565.             cached_char **pcc =
  566.                 chars_head(dir, hcc->code, cch->pair);
  567.             while ( *pcc != hcc )
  568.                 pcc = &(*pcc)->next;
  569.             *pcc = hcc->next; /* remove from chain */
  570.             gx_free_cached_char(dir, hcc);
  571.         }
  572.         fsize += cch->size;
  573.         if_debug2('K', "[K]merging free char 0x%lx(%u)\n",
  574.               (ulong)cch, cch->size);
  575.         cc->head.size = fsize;
  576.         cch = (cached_char_head *)((byte *)cc + fsize);
  577.     }
  578. #undef hcc
  579.     cc->chunk = cck;
  580.     cc->loc = (byte *)cc - cck->data;
  581.     if ( fsize > cdsize )
  582.       { shorten_cached_char(dir, cc, fsize - cdsize);
  583.         if_debug2('K', "[K]shortening char 0x%lx by %u (initial)\n",
  584.               (ulong)cc, fsize - cdsize);
  585.       }
  586.     dir->ccache.csize++;
  587.     dir->ccache.bsize += cdsize;
  588.     dir->ccache.cnext = cc->loc + cdsize;
  589.     return cc;
  590. }
  591.  
  592. /* Shorten a cached character. */
  593. /* diff >= sizeof(cached_char_head). */
  594. private void
  595. shorten_cached_char(gs_font_dir *dir, cached_char *cc, uint diff)
  596. {    char_cache_chunk *cck = cc->chunk;
  597.     cached_char_head *next;
  598.     if ( (byte *)cc + cc->head.size == cck->data + dir->ccache.cnext &&
  599.          cck == dir->ccache.chunks
  600.        )
  601.         dir->ccache.cnext -= diff;
  602.     cc->head.size -= diff;
  603.     next = (cached_char_head *)((byte *)cc + cc->head.size);
  604.     if_debug2('K', "[K]shortening creates free block 0x%lx(%u)\n",
  605.           (ulong)next, diff);
  606.     cc_head_set_free(next);
  607.     next->size = diff;
  608. }
  609.  
  610. /* ------ Image manipulation ------ */
  611.  
  612. /* Find the bounding box of a bitmap. */
  613. /* Assume bits beyond the width are zero. */
  614. private void
  615. image_bbox(const byte *data, uint height, uint raster, gs_int_rect *pbox)
  616. {    register const byte *p;
  617.     register uint n;
  618.     uint bsize = raster * height;
  619.     /* Count trailing blank rows. */
  620.     for ( p = data + bsize, n = bsize; n && !p[-1]; ) --n, --p;
  621.     if ( n == 0 )
  622.       {    pbox->p.x = pbox->q.x = pbox->p.y = pbox->q.y = 0;
  623.         return;
  624.       }
  625.     pbox->q.y = height = (n + raster - 1) / raster;
  626.     bsize = raster * height;
  627.     /* Count leading blank rows. */
  628.     {    uint count;
  629.         for ( p = data; !*p; ) ++p;
  630.         pbox->p.y = count = (p - data) / raster;
  631.         if ( count )
  632.           height -= count,
  633.           count *= raster, data += count, bsize -= count;
  634.     }
  635.     /* Find the left and right edges. */
  636.     /* We know that the first and last rows are non-blank. */
  637.     {    uint left = raster - 1, right = 0;
  638.         uint lbyte = 0, rbyte = 0;
  639.         const byte *q;
  640.         uint h;
  641.         for ( q = data, h = height; h-- > 0; q += raster )
  642.           {    for ( p = q, n = 0; n < left && !*p; p++, n++ ) ;
  643.             if ( n < left ) left = n, lbyte = *p;
  644.             else lbyte |= *p;
  645.             for ( p = q + raster - 1, n = raster - 1;
  646.                   n > right && !*p; p--, n--
  647.                 )
  648.               ;
  649.             if ( n > right ) right = n, rbyte = *p;
  650.             else rbyte |= *p;
  651.           }
  652.         left <<= 3;
  653.         while ( !(lbyte & 0x80) ) left++, lbyte <<= 1;
  654.         right = (right + 1) << 3;
  655.         while ( !(rbyte & 1) ) right--, rbyte >>= 1;
  656.         pbox->p.x = left;
  657.         pbox->q.x = right;
  658.     }
  659. }    
  660.  
  661. /* Count the number of 1-bits in a half-byte. */
  662. static const byte half_byte_1s[16] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
  663.  
  664. /* Compress a 4x4- or 2x2-oversampled bitmap to 1x1 by counting 1-bits. */
  665. /* The X and Y oversampling factors are 1, 2, or 4, but may be different. */
  666. /* Width and height reflect the oversampling; both are multiples of */
  667. /* the relevant scale factor. */
  668. /* Return the raster of the compressed bitmap. */
  669. private uint
  670. compress_scaled_bits(byte *data, uint width, uint height,
  671.   const gs_log2_scale_point *plog2_scale)
  672. {    int xscale = 1 << plog2_scale->x;
  673.     int yscale = 1 << plog2_scale->y;
  674.     uint threshold = xscale * yscale / 2;
  675.     uint sraster = bitmap_raster(width);
  676.     uint sskip = sraster * yscale;
  677.     uint dwidth = width / xscale;
  678.     uint draster = bitmap_raster(dwidth);
  679.     uint dskip = draster - ((dwidth + 7) >> 3);
  680.     uint mask = (1 << xscale) - 1;
  681.     byte *srow = data;
  682.     byte *d = data;
  683.     uint h;
  684. #ifdef DEBUG
  685.     if ( width % xscale != 0 || height % yscale != 0 )
  686.     {    lprintf4("size %d,%d not multiple of scale %d,%d!\n",
  687.              width, height, xscale, yscale);
  688.         width -= width % xscale;
  689.         height -= height % yscale;
  690.     }
  691. #endif
  692.     for ( h = height; h; h -= yscale )
  693.     {    byte *s = srow;
  694.         byte out_bit = 0x80;
  695.         byte out = 0;
  696.         int in_shift = 8 - xscale;
  697.         uint w;
  698.         for ( w = width; w; w -= xscale )
  699.         {    uint count = 0;
  700.             uint index;
  701.             for ( index = 0; index != sskip; index += sraster )
  702.                 count += half_byte_1s[(s[index] >> in_shift) & mask];
  703.             if ( count >= threshold )
  704.                 out += out_bit;
  705.             if ( (in_shift -= xscale) < 0 )
  706.                 s++, in_shift += 8;
  707.             if ( !(out_bit >>= 1) )
  708.                 *d++ = out, out_bit = 0x80, out = 0;
  709.         }
  710.         if ( out_bit != 0x80 )
  711.             *d++ = out;
  712.         for ( w = dskip; w != 0; w-- )
  713.             *d++ = 0;
  714.         srow += sskip;
  715.     }
  716.     return draster;
  717. }
  718.