home *** CD-ROM | disk | FTP | other *** search
/ Black Box 4 / BlackBox.cdr / progc / gs24src.arj / GXHT.C < prev    next >
C/C++ Source or Header  |  1992-02-27  |  12KB  |  334 lines
  1. /* Copyright (C) 1989, 1990, 1991 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* gxht.c */
  21. /* Halftone rendering routines for Ghostscript imaging library */
  22. #include "memory_.h"
  23. #include "gx.h"
  24. #include "gserrors.h"
  25. #include "gxfixed.h"
  26. #include "gxmatrix.h"            /* for gxdevice.h */
  27. #include "gzstate.h"
  28. #include "gzdevice.h"
  29. #include "gzcolor.h"            /* requires gxdevice.h */
  30. #include "gzht.h"
  31.  
  32. extern ulong gs_next_ids(P1(uint));
  33.  
  34. /*
  35.  * We don't want to remember all the values of the halftone screen,
  36.  * because they would take up space proportional to P^3, where P is
  37.  * the number of pixels in a cell.  Instead, we pick some number N of
  38.  * patterns to cache.  Each cache slot covers a range of (P+1)/N
  39.  * different gray levels: we "slide" the contents of the slot back and
  40.  * forth within this range by incrementally adding and dropping 1-bits.
  41.  * N>=0 (obviously); N<=P+1 (likewise); also, so that we can simplify things
  42.  * by preallocating the bookkeeping information for the cache, we define
  43.  * a constant max_cached_tiles which is an a priori maximum value for N.
  44.  *
  45.  * Note that the raster for each tile must be a multiple of 32 bits,
  46.  * to satisfy the copy_mono device routine, even though a multiple of
  47.  * 16 bits would otherwise be sufficient.
  48.  */
  49.  
  50. /*** Big memory machines ***/
  51. #define max_cached_tiles_LARGE 256
  52. #define max_ht_bits_LARGE 35000
  53. /*** Small memory machines ***/
  54. #define max_cached_tiles_SMALL 25
  55. #define max_ht_bits_SMALL 1000
  56.  
  57. #if arch_ints_are_short
  58. #  define max_cached_tiles max_cached_tiles_SMALL
  59. #  define max_ht_bits max_ht_bits_SMALL
  60. #else
  61. #  define max_cached_tiles max_cached_tiles_LARGE
  62. #  define max_ht_bits max_ht_bits_LARGE
  63. #endif
  64.  
  65. typedef struct bit_tile_s {
  66.     int level;            /* the cached gray level, i.e. */
  67.                     /* the number of spots whitened, */
  68.                     /* or -1 if the cache is empty */
  69.     gx_bitmap tile;            /* the currently rendered tile */
  70. } bit_tile;
  71. typedef struct gx_ht_cache_s {
  72.     /* The following are set when the cache is created. */
  73.     byte *bits;            /* the base of the bits */
  74.     uint bits_size;            /* the space available for bits */
  75.     /* The following are reset each time the cache is initialized */
  76.     /* for a new screen. */
  77.     ht_bit *order;            /* the cached order vector */
  78.     int num_cached;            /* actual # of cached tiles */
  79.     int levels_per_tile;        /* # of levels per cached tile */
  80.     bit_tile tiles[max_cached_tiles];    /* the cached tiles */
  81.     gx_bitmap_id base_id;        /* the base id, to which */
  82.                     /* we add the halftone level */
  83. } ht_cache;
  84. private ht_cache cache;
  85. private byte cache_bits[max_ht_bits];
  86. /* Bit masks for whitening vector.  The high-order byte always comes */
  87. /* first.  We have to define the masks as bit16 to ensure that */
  88. /* they will be properly aligned in memory on machines that care. */
  89. typedef unsigned short bit16;
  90. #if arch_is_big_endian
  91. #  define b2(hi,lo) (hi<<8)+lo
  92. #else
  93. #  define b2(hi,lo) (lo<<8)+hi
  94. #endif
  95. private bit16 single_bits[16] =
  96.    {    b2(0x80,0), b2(0x40,0), b2(0x20,0), b2(0x10,0),
  97.     b2(8,0), b2(4,0), b2(2,0), b2(1,0),
  98.     b2(0,0x80), b2(0,0x40), b2(0,0x20), b2(0,0x10),
  99.     b2(0,8), b2(0,4), b2(0,2), b2(0,1)
  100.    };
  101. private bit16 mb1[1] =
  102.    {    b2(0xff,0xff) };
  103. private bit16 mb2[2] =
  104.    {    b2(0xaa,0xaa), b2(0x55,0x55) };
  105. private bit16 mb3[3] =
  106.    {    b2(0x92,0x49), b2(0x49,0x24), b2(0x24,0x92) };
  107. private bit16 mb4[4] =
  108.    {    b2(0x88,0x88), b2(0x44,0x44), b2(0x22,0x22), b2(0x11,0x11) };
  109. private bit16 mb5[5] =
  110.    {    b2(0x84,0x21), b2(0x42,0x10), b2(0x21,0x08), b2(0x10,0x84),
  111.     b2(0x08,0x42)
  112.    };
  113. private bit16 mb6[6] =
  114.    {    b2(0x82,0x08), b2(0x41,0x04), b2(0x20,0x82), b2(0x10,0x41),
  115.     b2(0x08,0x20), b2(0x04,0x10)
  116.    };
  117. private bit16 mb7[7] =
  118.    {    b2(0x81,0x02), b2(0x40,0x81), b2(0x20,0x40), b2(0x10,0x20),
  119.     b2(0x08,0x10), b2(0x04,0x08), b2(0x02,0x04)
  120.    };
  121. private bit16 mb8[8] =
  122.    {    b2(0x80,0x80), b2(0x40,0x40), b2(0x20,0x20), b2(0x10,0x10),
  123.     b2(0x08,0x08), b2(0x04,0x04), b2(0x02,0x02), b2(0x01,0x01)
  124.    };
  125. #undef b2
  126. private bit16 *multi_bits[9] =
  127.    {    0, mb1, mb2, mb3, mb4, mb5, mb6, mb7, mb8
  128.    };
  129.  
  130. /* Construct the order vector.  order is an array of ht_bits: */
  131. /* order[i].offset contains the index of the bit position */
  132. /* that is i'th in the whitening order. */
  133. int
  134. gx_ht_construct_order(ht_bit *order, int width, int height)
  135. {    uint i;
  136.     uint size = (uint)(width * height);
  137.     int padding = (-width) & 31;
  138.     if ( (width + padding) / 8 * height > max_ht_bits )
  139.         return_error(gs_error_limitcheck);    /* can't cache the rendering */
  140.     /* Clear the cache, to avoid confusion in case */
  141.     /* the address of a new order vector matches that of a */
  142.     /* (deallocated) old one. */
  143.     cache.order = NULL;
  144.     cache.bits = cache_bits;
  145.     cache.bits_size = max_ht_bits;
  146.     /* Convert sequential indices to */
  147.     /* byte indices and mask values. */
  148.     for ( i = 0; i < size; i++ )
  149.        {    int pix = order[i].offset;
  150.         pix += pix / width * padding;
  151.         order[i].offset = (pix >> 4) << 1;
  152.         order[i].mask =
  153.             (width <= 8 ?
  154.              multi_bits[width][pix & 15] :
  155.              single_bits[pix & 15]);
  156.        }
  157. #ifdef DEBUG
  158. if ( gs_debug['h'] )
  159.        {    dprintf1("[h]Halftone order %lx:\n", (ulong)order);
  160.         for ( i = 0; i < size; i++ )
  161.             dprintf3("%4d: %u:%x\n", i, order[i].offset,
  162.                  order[i].mask);
  163.        }
  164. #endif
  165.     return 0;
  166. }
  167.  
  168. /* Make the cache order current, and return whether */
  169. /* there is room for all possible tiles in the cache. */
  170. private void init_ht(P2(ht_cache *, halftone_params *));
  171. int
  172. gx_check_tile_cache(gs_state *pgs)
  173. {    halftone_params *pht = pgs->halftone;
  174.     if ( cache.order != pht->order )
  175.       init_ht(&cache, pht);
  176.     return cache.levels_per_tile == 1;
  177. }
  178.  
  179. /* Determine whether a given (width, y, height) might fit into a */
  180. /* single tile. If so, return the byte offset of the appropriate row */
  181. /* from the beginning of the tile; if not, return -1. */
  182. int
  183. gx_check_tile_size(gs_state *pgs, int w, int y, int h)
  184. {    int tsy;
  185. #define tile0 cache.tiles[0].tile    /* a typical tile */
  186.     if ( h > tile0.rep_height || w > tile0.rep_width )
  187.       return -1;
  188.     tsy = (y + pgs->phase_mod.y) % tile0.rep_height;
  189.     if ( tsy + h > tile0.size.y )
  190.       return -1;
  191.     /* Tile fits in Y, might fit in X. */
  192.     return tsy * tile0.raster;
  193. #undef tile0
  194. }
  195.  
  196. /* Load the device color into the halftone cache if needed. */
  197. private void render_ht(P4(bit_tile *, int, halftone_params *, gx_bitmap_id));
  198. void
  199. gx_color_load(gx_device_color *pdevc, gs_state *pgs)
  200. {    int level = pdevc->halftone_level;
  201.     halftone_params *pht;
  202.     bit_tile *bt;
  203.     if ( level == 0 ) return;    /* no halftone */
  204.     pht = pgs->halftone;
  205.     if ( cache.order != pht->order )
  206.       init_ht(&cache, pht);
  207.     bt = &cache.tiles[level / cache.levels_per_tile];
  208.     if ( bt->level != level )
  209.         render_ht(bt, level, pht, cache.base_id);
  210.     pdevc->tile = &bt->tile;
  211. }
  212.  
  213. /* Initialize the tile cache for a given screen. */
  214. /* Cache as many different levels as will fit. */
  215. private void
  216. init_ht(ht_cache *pcache, halftone_params *pht)
  217. {    int width = pht->width;
  218.     int height = pht->height;
  219.     int size = width * height;
  220.     static int up_to_16[] =
  221.         /* up_to_16[i] = 16 / i * i */
  222.         { 0, 16, 16, 15, 16, 15, 12, 14, 16 };
  223.     int width_unit = (width <= 8 ? up_to_16[width] : width);
  224.     int height_unit = height;
  225.     uint raster = ((width + 31) >> 5) << 2;
  226.     uint tile_bytes = raster * height;
  227.     int num_cached;
  228.     int i;
  229.     byte *tbits = pcache->bits;
  230.     /* Make sure num_cached is within bounds */
  231.     num_cached = max_ht_bits / tile_bytes;
  232.     if ( num_cached > size ) num_cached = size;
  233.     if ( num_cached > max_cached_tiles ) num_cached = max_cached_tiles;
  234.     if ( num_cached <= max_cached_tiles / 2 )
  235.       height_unit <<= 1, tile_bytes <<= 1;
  236.     pcache->base_id = gs_next_ids(size);
  237.     for ( i = 0; i < num_cached; i++ )
  238.        {    register bit_tile *bt = &pcache->tiles[i];
  239.         bt->level = -1;
  240.         bt->tile.data = tbits;
  241.         bt->tile.raster = raster;
  242.         bt->tile.size.x = width_unit;
  243.         bt->tile.size.y = height_unit;
  244.         bt->tile.rep_width = width;
  245.         bt->tile.rep_height = height;
  246.         tbits += tile_bytes;
  247.        }
  248.     pcache->order = pht->order;
  249.     pcache->num_cached = num_cached;
  250.     pcache->levels_per_tile = (size + num_cached - 1) / num_cached;
  251. }
  252.  
  253. /*
  254.  * Compute and save the rendering of a given gray level
  255.  * with the current halftone.  The cache holds multiple tiles,
  256.  * where each tile covers a range of possible levels.
  257.  * If the tile whose range includes the desired level is already loaded,
  258.  * we adjust it incrementally: this saves a lot of time for
  259.  * the average image, where gray levels don't change abruptly.
  260.  * Note that we will never be asked to cache levels 0 or order_size,
  261.  * which correspond to black or white respectively.
  262.  */
  263. private void
  264. render_ht(bit_tile *pbt, int level /* [1..order_size-1] */,
  265.   halftone_params *pht, gx_bitmap_id base_id)
  266. {    ht_bit *order = pht->order;
  267.     register ht_bit *p;
  268.     register ht_bit *endp;
  269.     register byte *bits = pbt->tile.data;
  270.     int old_level = pbt->level;
  271.     if ( old_level < 0 )
  272.        {    /* The cache is empty.  Preload it with */
  273.         /* whichever of all-0s and all-1s will be faster. */
  274.         uint tile_bytes = pbt->tile.raster * pbt->tile.size.y;
  275.         if ( level >= pht->order_size >> 1 )
  276.            {    old_level = pht->order_size;
  277.             memset(bits, 0xff, tile_bytes);
  278.            }
  279.         else
  280.            {    old_level = 0;
  281.             memset(bits, 0, tile_bytes);
  282.            }
  283.        }
  284. #ifdef DEBUG
  285.     if ( level < 0 || level > pht->order_size || level == old_level )
  286.        {    lprintf3("Error in render_ht: level=%d, old_level=%d, order_size=%d=n", level, old_level, pht->order_size);
  287.         gs_exit(1);
  288.        }
  289. #endif
  290.     /* Note that we can use the same loop to turn bits either */
  291.     /* on or off, using xor.  We use < to compare pointers, */
  292.     /* rather than ==, because Turbo C only compares the */
  293.     /* low 16 bits for < and > but compares all 32 bits for ==. */
  294.     if ( level > old_level )
  295.         p = &order[old_level], endp = &order[level];
  296.     else
  297.         p = &order[level], endp = &order[old_level];
  298.     /* Invert bits between the two pointers */
  299.     do
  300.        {    *(bit16 *)&bits[p->offset] ^= p->mask;
  301.        }
  302.     while ( ++p < endp );
  303. #ifdef DEBUG
  304. if ( gs_debug['h'] )
  305.        {    byte *p = bits;
  306.         int wb = pbt->tile.raster;
  307.         byte *ptr = bits + wb * pbt->tile.size.y;
  308.         dprintf7("[h]Halftone cache %lx: old=%d, new=%d, w=%d(%d), h=%d(%d):\n",
  309.              (ulong)bits, old_level, level, pbt->tile.size.x,
  310.                  pht->width, pbt->tile.size.y, pht->height);
  311.         while ( p < ptr )
  312.            {    dprintf1(" %02x", *p++);
  313.             if ( (p - bits) % wb == 0 ) dputc('\n');
  314.            }
  315.        }
  316. #endif
  317.     pbt->level = level;
  318.     pbt->tile.id = base_id + level;
  319.     if ( pbt->tile.size.y > pbt->tile.rep_height )
  320.       { /* Replicate the tile in Y.  We only do this when */
  321.         /* all the renderings will fit in the cache, */
  322.         /* so we only do it once per level, and it doesn't */
  323.         /* have to be very efficient. */
  324.         uint rh = pbt->tile.rep_height;
  325.         uint h = pbt->tile.size.y;
  326.         uint tsize = pbt->tile.raster * rh;
  327.         do
  328.           { memcpy(bits + tsize, bits, tsize);
  329.         bits += tsize;
  330.           }
  331.         while ( (h -= rh) != 0 );
  332.       }
  333. }
  334.