home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / GSHT1.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  12KB  |  341 lines
  1. /* Copyright (C) 1993 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. /* gsht1.c */
  20. /* Screen (Type 1) halftone processing for Ghostscript library */
  21. #include "math_.h"
  22. #include "gx.h"
  23. #include "gserrors.h"
  24. #include "gsstruct.h"
  25. #include "gzstate.h"
  26. #include "gxdevice.h"            /* for gzht.h */
  27. #include "gzht.h"
  28.  
  29. private_st_gs_screen_enum();
  30.  
  31. /* GC procedures */
  32.  
  33. #define eptr ((gs_screen_enum *)vptr)
  34.  
  35. private ENUM_PTRS_BEGIN(screen_enum_enum_ptrs) {
  36.     if ( index < 2 + st_ht_order_max_ptrs )
  37.       { gs_ptr_type_t ret = (*st_ht_order.enum_ptrs)(&eptr->order, sizeof(eptr->order), index-2, pep);
  38.         if ( ret == 0 )    /* don't stop early */
  39.           ret = ptr_struct_type, *pep = 0;
  40.         return ret;
  41.       }
  42.     return (*st_halftone.enum_ptrs)(&eptr->halftone, sizeof(eptr->halftone), index-(2+st_ht_order_max_ptrs), pep);
  43.     }
  44.     ENUM_PTR(0, gs_screen_enum, pgs);
  45.     ENUM_PTR(1, gs_screen_enum, dev_ht);
  46. ENUM_PTRS_END
  47.  
  48. private RELOC_PTRS_BEGIN(screen_enum_reloc_ptrs) {
  49.     RELOC_PTR(gs_screen_enum, pgs);
  50.     RELOC_PTR(gs_screen_enum, dev_ht);
  51.     (*st_halftone.reloc_ptrs)(&eptr->halftone, sizeof(gs_halftone), gcst);
  52.     (*st_ht_order.reloc_ptrs)(&eptr->order, sizeof(gx_ht_order), gcst);
  53. } RELOC_PTRS_END
  54.  
  55. #undef eptr
  56.  
  57. /*
  58.  * We construct a halftone tile as a "super-cell" consisting of
  59.  * multiple copies of a basic cell.  We characterize the basic cell
  60.  * by two integers U and V, at least one of which is non-zero,
  61.  * which define the vertices of the basic cell at device space coordinates
  62.  * (0,0), (U,V), (U-V,U+V), and (-V,U).  If the coefficients of the
  63.  * default device transformation matrix are xx, xy, yx, and yy, then
  64.  * U and V are related to the frequency F and the angle A by:
  65.  *    P = 72 / F;
  66.  *    U = P * (xx * cos(A) + yx * sin(A));
  67.  *    V = P * (xy * cos(A) + yy * sin(A)).
  68.  * If we then define:
  69.  *    D = gcd(abs(U), abs(V));
  70.  *    W = (U * U + V * V) / D;
  71.  * then the super-cell consists of W basic cells occupying W x W pixels.
  72.  * The trick in all this is to find values of F and A that aren't too far
  73.  * from the requested ones, and that yield a manageably small value for W.
  74.  *
  75.  * Note that the super-cell only has to be so large because we want to
  76.  * use it directly to tile the plane.  In fact, it is composed of W / D
  77.  * horizontal strips of size W x D, shifted horizontally with respect
  78.  * to each other by S * D pixels, where S = (K * U / D) mod (W / D) for
  79.  * the smallest non-negative integer K such that K * V / D = 1 mod (W / D).
  80.  * The routines here only generate a single strip of samples, and let
  81.  * gx_ht_construct_spot_order construct the rest.  We could save a lot of
  82.  * space by storing only one strip, and letting the tile_rectangle routines
  83.  * do the shifting at rendering time; however, we will leave this
  84.  * added complexity for the future.
  85.  */
  86.  
  87. /* Forward references */
  88. private void pick_cell_size(P5(gs_screen_halftone *ph,
  89.   const gs_matrix *pmat, long max_w,
  90.   gs_int_point *pcell, gs_int_point *ptile));
  91. private int igcd(P2(int, int));
  92.  
  93. /* Allocate a screen enumerator. */
  94. gs_screen_enum *
  95. gs_screen_enum_alloc(gs_memory_t *mem, client_name_t cname)
  96. {    return gs_alloc_struct(mem, gs_screen_enum, &st_gs_screen_enum, cname);
  97. }
  98.  
  99. /* Set up for halftone sampling. */
  100. int
  101. gs_screen_init(gs_screen_enum *penum, gs_state *pgs,
  102.   gs_screen_halftone *phsp)
  103. {    gs_matrix imat;
  104.     gs_int_point cell, tile;
  105.     int code;
  106.     int d;
  107.     penum->pgs = pgs;        /* ensure clean for GC */
  108.     penum->dev_ht = 0;        /* ditto */
  109.     if ( phsp->frequency < 0.1 )
  110.         return_error(gs_error_rangecheck);
  111.     gs_deviceinitialmatrix(gs_currentdevice(pgs), &imat);
  112.     pick_cell_size(phsp, &imat, max_ushort, &cell, &tile);
  113. #define u cell.x
  114. #define v cell.y
  115. #define w tile.x
  116.     d = igcd(u, v);
  117.     code = gx_ht_init_order(&penum->order, tile.x, tile.y,
  118.                 w * d, pgs->memory);
  119.     if ( code < 0 )
  120.         return code;
  121.     penum->halftone.type = ht_type_screen;
  122.     penum->halftone.params.screen = *phsp;
  123.     penum->x = penum->y = 0;
  124.     {    /* Unfortunately, we don't know any closed formula for */
  125.         /* computing the shift, so we do it by enumeration. */
  126.         uint k;
  127.         uint wd = w / d;
  128.         uint vk = (v < 0 ? v + w : v) / d;
  129.         for ( k = 0; k < wd; k++ )
  130.         {    if ( (k * vk) % wd == 1 )
  131.                 break;
  132.         }
  133.         penum->strip = d;
  134.         penum->shift = ((((u < 0 ? u + w : u) / d) * k) % wd) * d;
  135.         if_debug2('h', "[h]strip=%d shift=%d\n", d, penum->shift);
  136.     }
  137.     /* The transformation matrix must include normalization to the */
  138.     /* interval (-1..1), and rotation by the negative of the angle. */
  139.     /****** WRONG IF NON-SQUARE PIXELS ******/
  140.     {    float xscale = 2.0 / hypot((double)cell.x, (double)cell.y);
  141.         float yscale = xscale;
  142.         gs_make_rotation(-phsp->actual_angle, &penum->mat);
  143.         penum->mat.xx *= xscale, penum->mat.xy *= xscale;
  144.         penum->mat.yx *= yscale, penum->mat.yy *= yscale;
  145.         penum->mat.tx = -1.0;
  146.         penum->mat.ty = -1.0;
  147.         if_debug6('h', "[h]Screen: %dx%d [%f %f %f %f]\n",
  148.               tile.x, tile.y,
  149.               penum->mat.xx, penum->mat.xy,
  150.               penum->mat.yx, penum->mat.yy);
  151.     }
  152. #undef u
  153. #undef v
  154. #undef w
  155.     return 0;
  156. }
  157.  
  158. /*
  159.  * The following routine looks for "good" values of U and V
  160.  * in a simple-minded way, according to the following algorithm:
  161.  * We compute trial values u and v from the original values of F and A.
  162.  * Normally these will not be integers.  We then examine the 4 pairs of
  163.  * integers obtained by rounding each of u and v independently up or down,
  164.  * and pick the pair U, V that yields the smallest value of W. If no pair
  165.  * yields an acceptably small W, we divide both u and v by 2 and try again.
  166.  * Then we run the equations backward to obtain the actual F and A.
  167.  * This is fairly easy given that we require either xx = yy = 0 or
  168.  * xy = yx = 0.  In the former case, we have
  169.  *    U = (72 / F * xx) * cos(A);
  170.  *    V = (72 / F * yy) * sin(A);
  171.  * from which immediately
  172.  *    A = arctan((V / yy) / (U / xx)),
  173.  * or equivalently
  174.  *    A = arctan((V * xx) / (U * yy)).
  175.  * We can then obtain F as
  176.  *    F = (72 * xx / U) * cos(A),
  177.  * or equivalently
  178.  *    F = (72 * yy / V) * sin(A).
  179.  * For landscape devices, we replace xx by yx, yy by xy, and interchange
  180.  * sin and cos, resulting in
  181.  *    A = arctan((U * xy) / (V * yx))
  182.  * and
  183.  *    F = (72 * yx / U) * sin(A)
  184.  * or
  185.  *    F = (72 * xy / V) * cos(A).
  186.  */
  187. /* ph->frequency and ph->angle are input parameters; */
  188. /* the routine sets ph->actual_frequency and ph->actual_angle. */
  189. private void
  190. pick_cell_size(gs_screen_halftone *ph, const gs_matrix *pmat, long max_w,
  191.   gs_int_point *pcell, gs_int_point *ptile)
  192. {    bool landscape = (pmat->xy != 0.0 || pmat->yx != 0.0);
  193.     /* Account for a possibly reflected coordinate system. */
  194.     /* See gxstroke.c for the algorithm. */
  195.     bool reflected =
  196.         (landscape ? pmat->xy * pmat->yx > pmat->xx * pmat->yy :
  197.          (pmat->xx < 0) != (pmat->yy < 0));
  198.     int reflection = (reflected ? -1 : 1);
  199.     int rotation =
  200.         (landscape ? (pmat->yx < 0 ? 90 : -90) :
  201.                  pmat->xx < 0 ? 180 : 0);
  202.     double a = ph->angle;
  203.     gs_matrix rmat;
  204.     gs_point t;
  205.     int u0, v0, ut, vt, u, v;
  206.     long w;
  207.     double rf, ra;
  208.  
  209.     /*
  210.      * We need to find a vector in device space whose length is
  211.      * 1 inch / ph->frequency and whose angle is ph->angle.
  212.      * Because device pixels may not be square, we can't simply
  213.      * map the length to device space and then rotate it;
  214.      * instead, since we know that user space is uniform in X and Y,
  215.      * we calculate the correct angle in user space before rotation.
  216.      */
  217.  
  218.     a = a * reflection + rotation;
  219.  
  220.     /* Compute trial values of u and v. */
  221.  
  222.     gs_make_rotation(a, &rmat);
  223.     gs_distance_transform(72.0 / ph->frequency, 0.0, &rmat, &t);
  224.     gs_distance_transform(t.x, t.y, pmat, &t);
  225.     if_debug8('h', "[h]Requested: f=%g a=%g mat=[%g %g %g %g] => u=%g v=%g\n",
  226.           ph->frequency, ph->angle,
  227.           pmat->xx, pmat->xy, pmat->yx, pmat->yy, t.x, t.y);
  228.  
  229.     /* Choose the "best" U and V. */
  230.  
  231.     u0 = (int)floor(t.x + 0.0001);
  232.     v0 = (int)floor(t.y + 0.0001);
  233.     /* Force a halfway reasonable cell size. */
  234.     if ( u0 == 0 && v0 == 0 )
  235.         u0 = v0 = 1;
  236.     while ( abs(u0) + abs(v0) < 4 )
  237.         u0 <<= 1, v0 <<= 1;
  238. try:    w = max_w;
  239.     for ( ut = u0 + 1; ut >= u0; ut-- )
  240.       for ( vt = v0 + 1; vt >= v0; vt-- )
  241.     {    int d = igcd(ut, vt);
  242.         long wt = abs(ut / d * (long)ut) + abs(vt / d * (long)vt);
  243.         if ( wt < w )
  244.             u = ut, v = vt, w = wt;
  245.     }
  246.     if ( w == max_w )
  247.     {    /* We couldn't find an acceptable U and V. */
  248.         /* Shrink the cell and try again. */
  249.         u0 >>= 1;
  250.         v0 >>= 1;
  251.         goto try;
  252.     }
  253.  
  254.     /* Compute the actual values of F and A. */
  255.  
  256.     if ( landscape )
  257.         ra = atan2(u * pmat->xy, v * pmat->yx),
  258.         rf = 72.0 * (u == 0 ? pmat->xy / v * cos(ra) : pmat->yx / u * sin(ra));
  259.     else
  260.         ra = atan2(v * pmat->xx, u * pmat->yy),
  261.         rf = 72.0 * (u == 0 ? pmat->yy / v * sin(ra) : pmat->xx / u * cos(ra));
  262.  
  263.     /* Deliver the results. */
  264.     /****** WRONG IF NON-SQUARE PIXELS ******/
  265.  
  266.     pcell->x = u, pcell->y = v;
  267.     ptile->x = w, ptile->y = w;
  268.     ph->actual_frequency = fabs(rf);
  269.     ph->actual_angle = (ra * radians_to_degrees - rotation) * reflection;
  270.     if_debug5('h', "[h]Chosen: f=%g a=%g u=%d v=%d w=%d\n",
  271.           ph->actual_frequency, ph->actual_angle, u, v, (int)w);
  272. }
  273.  
  274. /* Compute the GCD of two integers. */
  275. private int
  276. igcd(int x, int y)
  277. {    int c = abs(x), d = abs(y);
  278.     while ( c != 0 && d != 0 )
  279.         if ( c > d ) c %= d;
  280.         else d %= c;
  281.     return d + c;        /* at most one is non-zero */
  282. }
  283.  
  284. /* Report current point for sampling */
  285. int
  286. gs_screen_currentpoint(gs_screen_enum *penum, gs_point *ppt)
  287. {    gs_point pt;
  288.     int code;
  289.     if ( penum->y >= penum->strip )        /* all done */
  290.     {    gx_ht_construct_spot_order(&penum->order,
  291.                        penum->strip, penum->shift);
  292.         return 1;
  293.     }
  294.     if ( (code = gs_point_transform(penum->x + 0.5, penum->y + 0.5, &penum->mat, &pt)) < 0 )
  295.         return code;
  296.     if ( pt.x < -1.0 )
  297.         pt.x += ((int)(-ceil(pt.x)) + 1) & ~1;
  298.     else if ( pt.x >= 1.0 )
  299.         pt.x -= ((int)pt.x + 1) & ~1;
  300.     if ( pt.y < -1.0 )
  301.         pt.y += ((int)(-ceil(pt.y)) + 1) & ~1;
  302.     else if ( pt.y >= 1.0 )
  303.         pt.y -= ((int)pt.y + 1) & ~1;
  304.     *ppt = pt;
  305.     return 0;
  306. }
  307.  
  308. /* Record next halftone sample */
  309. int
  310. gs_screen_next(gs_screen_enum *penum, floatp value)
  311. {    ushort sample;
  312.     int width = penum->order.width;
  313.     if ( value < -1.0 || value > 1.0 )
  314.         return_error(gs_error_rangecheck);
  315.     /* The following statement was split into two */
  316.     /* to work around a bug in the Siemens C compiler. */
  317.     sample = (ushort)(value * (float)(int)(max_ushort >> 1));
  318.     sample += (max_ushort >> 1);    /* convert from signed to biased */
  319. #ifdef DEBUG
  320. if ( gs_debug_c('h') )
  321.    {    gs_point pt;
  322.     gs_screen_currentpoint(penum, &pt);
  323.     dprintf6("[h]sample x=%d y=%d (%f,%f): %f -> %u\n",
  324.          penum->x, penum->y, pt.x, pt.y, value, sample);
  325.    }
  326. #endif
  327.     penum->order.bits[penum->y * width + penum->x].mask = sample;
  328.     if ( ++(penum->x) >= width )
  329.         penum->x = 0, ++(penum->y);
  330.     return 0;
  331. }
  332.  
  333. /* Install a fully constructed screen in the gstate. */
  334. int
  335. gs_screen_install(gs_screen_enum *penum)
  336. {    gx_device_halftone dev_ht;
  337.     dev_ht.order = penum->order;
  338.     dev_ht.components = 0;
  339.     return gx_ht_install(penum->pgs, &penum->halftone, &dev_ht);
  340. }
  341.