home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / GXDITHER.C < prev    next >
C/C++ Source or Header  |  1994-07-30  |  16KB  |  448 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. /* gxdither.c */
  20. #include "gx.h"
  21. #include "gxfixed.h"
  22. #include "gxlum.h"
  23. #include "gxmatrix.h"
  24. #include "gzstate.h"
  25. #include "gxcmap.h"
  26. #include "gxdither.h"
  27. #include "gzht.h"
  28.  
  29. /*
  30.  * The procedures in this file use halftoning (if necessary)
  31.  * to implement a given device color that has already gone through
  32.  * the transfer function.  There are two major cases: gray and color.
  33.  * Gray halftoning always uses a binary screen.  Color halftoning
  34.  * uses either a fast algorithm with a binary screen that produces
  35.  * relatively poor approximations, or a very slow algorithm with a
  36.  * general colored screen (or screens) that faithfully implements
  37.  * the Adobe specifications.
  38.  */
  39.  
  40. /* Tables for fast computation of fractional color levels. */
  41. /* We have to put the table before any uses of it because of a bug */
  42. /* in the VAX C compiler. */
  43. /* We have to split up the definition of the table itself because of a bug */
  44. /*  in the IBM AIX 3.2 C compiler. */
  45. private const gx_color_value
  46.   q0[] = { 0 };
  47. private const gx_color_value
  48.   q1[] = { 0, frac_color_(1,1) };
  49. private const gx_color_value
  50.   q2[] = { 0, frac_color_(1,2), frac_color_(2,2) };
  51. private const gx_color_value
  52.   q3[] = { 0, frac_color_(1,3), frac_color_(2,3), frac_color_(3,3) };
  53. private const gx_color_value
  54.   q4[] = { 0, frac_color_(1,4), frac_color_(2,4), frac_color_(3,4), frac_color_(4,4) };
  55. private const gx_color_value
  56.   q5[] = { 0, frac_color_(1,5), frac_color_(2,5), frac_color_(3,5), frac_color_(4,5), frac_color_(5,5) };
  57. private const gx_color_value
  58.   q6[] = { 0, frac_color_(1,6), frac_color_(2,6), frac_color_(3,6), frac_color_(4,6), frac_color_(5,6), frac_color_(6,6) };
  59. private const gx_color_value
  60.   q7[] = { 0, frac_color_(1,7), frac_color_(2,7), frac_color_(3,7), frac_color_(4,7), frac_color_(5,7), frac_color_(6,7), frac_color_(7,7) };
  61. /* We export fc_color_quo for the fractional_color macro in gzht.h. */
  62. const gx_color_value _ds *fc_color_quo[8] =
  63.  { q0, q1, q2, q3, q4, q5, q6, q7 };
  64.  
  65. /* Render a gray, possibly by halftoning. */
  66. int
  67. gx_render_gray(frac gray, gx_device_color *pdevc, const gs_state *pgs)
  68. {    gx_device *dev = pgs->device;
  69.     gx_color_value alpha = pgs->alpha;
  70.  
  71. /* Make a special check for black and white. */
  72.     if ( alpha == gx_max_color_value )
  73.     {    if ( gray == frac_0 )
  74.         {    color_set_pure(pdevc, dev->cached.black);
  75.             return 0;
  76.         }
  77.         else if ( gray == frac_1 )
  78.         {    color_set_pure(pdevc, dev->cached.white);
  79.             return 0;
  80.         }
  81.     }
  82.  
  83. /* get a few handy values */
  84.     {    uint max_value = dev->color_info.dither_gray - 1;
  85.         unsigned long hsize =
  86.             (unsigned)pgs->dev_ht->order.num_levels;
  87.         unsigned long nshades = hsize * max_value + 1;
  88.         unsigned long lx = (nshades * gray) / (frac_1_long + 1);
  89.         uint v = lx / hsize;
  90.         gx_color_value lum = fractional_color(v, max_value);
  91.         gx_color_index color1;
  92.         int level = lx % hsize;
  93.         /* The following should be a conditional expression, */
  94.         /* but the DECStation 3100 Ultrix 4.3 compiler */
  95.         /* generates bad code for it. */
  96.         if ( alpha == gx_max_color_value )
  97.           {    color1 = gx_map_rgb_color(dev, lum, lum, lum);
  98.           }
  99.         else
  100.           {    color1 = gx_map_rgb_alpha_color(dev, lum, lum, lum, alpha);
  101.           }
  102.         if_debug5('c', "[c]gray=0x%x --> (%d+%d/%lu)/%d\n",
  103.               (unsigned)gray, v, level, hsize, max_value + 1);
  104.         if ( level == 0 )
  105.         {    /* Close enough to a pure color, */
  106.             /* no dithering needed. */
  107.             color_set_pure(pdevc, color1);
  108.         }
  109.         else
  110.         {    v++;
  111.             lum = fractional_color(v, max_value);
  112.             color_set_binary_halftone(pdevc, color1,
  113.                 (alpha == gx_max_color_value ?
  114.                  gx_map_rgb_color(dev, lum, lum, lum) :
  115.                  gx_map_rgb_alpha_color(dev, lum, lum, lum, alpha)),
  116.                 level);
  117.         }
  118.         return gx_color_load(pdevc, pgs);
  119.     }
  120. }
  121.  
  122. /* 
  123.  *    Color dithering for Ghostscript.  The underlying device imaging model
  124.  *    supports dithering between two colors to generate intermediate shades.
  125.  *    
  126.  *    If the device has high quality colors (at least 32 values
  127.  *    per axis), we ask it to map the color directly.
  128.  *
  129.  *    Otherwise, things are a bit more complicated.  If the device 
  130.  *     supports N shades of each R, G and B independently, there are a total 
  131.  *    of N*N*N colors.  These colors form a 3-D grid in a cubical color 
  132.  *    space.  The following dithering technique works by locating the 
  133.  *    color we want in this 3-D color grid and finding the eight colors 
  134.  *     that surround it.  In the case of dithering into 8 colors with 1 
  135.  *    bit for each red, green and blue, these eight colors will always 
  136.  *    be the same.
  137.  *
  138.  *    Now we consider all possible diagonal paths between the eight colors
  139.  *    and chose the path that runs closest to our desired color in 3-D
  140.  *    color space.  There are 28 such paths.  Then we find the position
  141.  *    on the path that is closest to our color.
  142.  *
  143.  *    The search is made faster by always reflecting our color into
  144.  *    the bottom octant of the cube and comparing it to 7 paths.
  145.  *    After the best path and the best position on that path are found,
  146.  *    the results are reflected back into the original color space.
  147.  *
  148.  *    NOTE: This code has been tested for B/W and Color imaging with
  149.  *    1, 2, 3 and 8 bits per component.
  150.  *
  151.  *    --- original code by Paul Haeberli @ Silicon Graphics - 1990
  152.  *    --- extensively revised by L. Peter Deutsch, Aladdin Enterprises
  153.  *
  154.  *    lpd 3/14/94: added support for CMYK.
  155.  */
  156.  
  157. /*
  158.  * The weights are arbitrary, as long as their ratios are correct
  159.  * and they will fit into the difference between a ulong and a frac
  160.  * with room to spare.  By making WEIGHT1 and WEIGHT4 powers of 2,
  161.  * we can turn some multiplies into shifts.
  162.  */
  163. #define WNUM 128000
  164. #define    WEIGHT1        (ulong)(WNUM/1000)    /* 1.0            */
  165. #define    WEIGHT2        (ulong)(WNUM/1414)    /* 1/sqrt(2.0)        */
  166. #define    WEIGHT3        (ulong)(WNUM/1732)    /* 1/sqrt(3.0)        */
  167. #define WEIGHT4        (ulong)(WNUM/2000)    /* 1/sqrt(4.0)        */
  168.  
  169. #define    DIAG_R        (0x1)
  170. #define    DIAG_G        (0x2)
  171. #define    DIAG_B        (0x4)
  172. #define DIAG_W        (0x8)
  173. #define    DIAG_RG        (0x3)
  174. #define    DIAG_GB        (0x6)
  175. #define    DIAG_BR        (0x5)
  176. #define    DIAG_RGB    (0x7)
  177. #define DIAG_RGBW    (0xf)
  178.  
  179. /* What should we do about the W/K component?  For the moment, */
  180. /* we ignore it in the luminance computation. */
  181. #define lum_white_weight 0
  182. private const unsigned short lum_w[16] = {
  183.     (0*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  184.     (0*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  185.     (0*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  186.     (0*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  187.     (1*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  188.     (1*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  189.     (1*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+0*lum_white_weight),
  190.     (1*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+0*lum_white_weight),
  191.     (0*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  192.     (0*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+1*lum_white_weight),
  193.     (0*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  194.     (0*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+1*lum_white_weight),
  195.     (1*lum_blue_weight+0*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  196.     (1*lum_blue_weight+0*lum_green_weight+1*lum_red_weight+1*lum_white_weight),
  197.     (1*lum_blue_weight+1*lum_green_weight+0*lum_red_weight+1*lum_white_weight),
  198.     (1*lum_blue_weight+1*lum_green_weight+1*lum_red_weight+1*lum_white_weight)
  199. };
  200.  
  201. /* Render RGB or CMYK, possibly by halftoning. */
  202. /* If we are rendering RGB, white is ignored. */
  203. /* If we are rendering CMYK, red/green/blue/white are actually */
  204. /* cyan/magenta/yellow/black. */
  205. int
  206. gx_render_color(frac red, frac green, frac blue, frac white, bool cmyk,
  207.   gx_device_color *pdevc, const gs_state *pgs)
  208. {    gx_device *dev = pgs->device;
  209.     uint max_value = dev->color_info.dither_rgb - 1;
  210.     uint num_levels = pgs->dev_ht->order.num_levels;
  211.     gx_color_value alpha = pgs->alpha;
  212.     frac rem_r, rem_g, rem_b, rem_w;
  213.     uint r, g, b, w;
  214.     gx_color_value vr, vg, vb, vw;
  215. #define map_color()\
  216.   (cmyk ? gx_map_cmyk_color(dev, vr, vg, vb, vw) :\
  217.    alpha == gx_max_color_value ?\
  218.    gx_map_rgb_color(dev, vr, vg, vb) :\
  219.    gx_map_rgb_alpha_color(dev, vr, vg, vb, alpha))
  220.  
  221.     /* Compute the quotient and remainder of each color component */
  222.     /* with the actual number of available colors. */
  223.     switch ( max_value )
  224.     {
  225.     case 1:            /* 8 or 16 colors */
  226.         if ( red == frac_1 ) rem_r = 0, r = 1;
  227.         else rem_r = red, r = 0;
  228.         if ( green == frac_1 ) rem_g = 0, g = 1;
  229.         else rem_g = green, g = 0;
  230.         if ( blue == frac_1 ) rem_b = 0, b = 1;
  231.         else rem_b = blue, b = 0;
  232.         if ( white == frac_1 ) rem_w = 0, w = 1;
  233.         else rem_w = white, w = 0;
  234.         break;
  235.     default:
  236.        {    ulong want_r, want_g, want_b, want_w;
  237.         want_r = (ulong)max_value * red;
  238.         r = frac_1_quo(want_r);
  239.         rem_r = frac_1_rem(want_r, r);
  240.         want_g = (ulong)max_value * green;
  241.         g = frac_1_quo(want_g);
  242.         rem_g = frac_1_rem(want_g, g);
  243.         want_b = (ulong)max_value * blue;
  244.         b = frac_1_quo(want_b);
  245.         rem_b = frac_1_rem(want_b, b);
  246.         want_w = (ulong)max_value * white;
  247.         w = frac_1_quo(want_w);
  248.         rem_w = frac_1_rem(want_w, w);
  249.        }
  250.     }
  251.  
  252.     /* Check for no dithering required */
  253.     if ( !(rem_r | rem_g | rem_b | rem_w) )
  254.     {    vr = fractional_color(r, max_value);
  255.         vg = fractional_color(g, max_value);
  256.         vb = fractional_color(b, max_value);
  257.         vw = fractional_color(w, max_value);
  258.         color_set_pure(pdevc, map_color());
  259.         return 0;
  260.     }
  261.  
  262.     if_debug12('c', "[c]rgbw=0x%x,0x%x,0x%x,0x%x -->\n   %x+0x%x,%x+0x%x,%x+0x%x,%x+0x%x -->\n",
  263.           (unsigned)red, (unsigned)green, (unsigned)blue, (unsigned)white,
  264.           (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g,
  265.           (unsigned)b, (unsigned)rem_b, (unsigned)w, (unsigned)rem_w);
  266.  
  267.     /* Dithering is required.  Choose between two algorithms. */
  268.       
  269.     if ( pgs->dev_ht->components != 0 )
  270.     {    /* Someone went to the trouble of setting different */
  271.         /* screens for the different components. */
  272.         /* Use the slow, general colored halftone algorithm. */
  273. #define rgb_rem(rem_v) (rem_v * (ulong)num_levels / frac_1)
  274.         uint lr = rgb_rem(rem_r), lg = rgb_rem(rem_g),
  275.           lb = rgb_rem(rem_b);
  276.         if ( cmyk )
  277.           color_set_cmyk_halftone(pdevc, r, lr, g, lg, b, lb,
  278.                       w, rgb_rem(rem_w));
  279.         else
  280.           color_set_rgb_halftone(pdevc, r, lr, g, lg, b, lb, alpha);
  281. #undef rgb_rem
  282.         return gx_color_load(pdevc, pgs);
  283.     }
  284.  
  285.     /* Fast, approximate binary halftone algorithm. */
  286.     
  287.   {    ulong hsize = num_levels;
  288.     int adjust_r, adjust_b, adjust_g, adjust_w;
  289.     gx_color_index color1;
  290.     frac amax, amin;
  291.     ulong fmax, cmax;
  292.     int axisc, facec, cubec, diagc;
  293.     unsigned short lum_invert;
  294.     ulong dot1, dot2, dot3, dot4;
  295.     int level;
  296.     int code;
  297.  
  298. /* Flip the remainder color into the 0, 0, 0 octant. */
  299.     lum_invert = 0;
  300. #define half (frac_1/2)
  301.     if ( rem_r > half )
  302.         rem_r = frac_1 - rem_r,
  303.           adjust_r = -1, r++, lum_invert += lum_red_weight * 2;
  304.     else
  305.         adjust_r = 1;
  306.     if ( rem_g > half )
  307.         rem_g = frac_1 - rem_g,
  308.           adjust_g = -1, g++, lum_invert += lum_green_weight * 2;
  309.     else
  310.         adjust_g = 1;
  311.     if ( rem_b > half )
  312.         rem_b = frac_1 - rem_b,
  313.           adjust_b = -1, b++, lum_invert += lum_blue_weight * 2;
  314.     else
  315.         adjust_b = 1;
  316.     if ( rem_w > half )
  317.         rem_w = frac_1 - rem_w,
  318.           adjust_w = -1, b++, lum_invert += lum_white_weight * 2;
  319.     else
  320.         adjust_w = 1;
  321.     vr = fractional_color(r, max_value);
  322.     vg = fractional_color(g, max_value);
  323.     vb = fractional_color(b, max_value);
  324.     vw = fractional_color(w, max_value);
  325.     color1 = map_color();
  326.  
  327. /* 
  328.  * Dot the color with each axis to find the best one of 15;
  329.  * find the color at the end of the axis chosen.
  330.  */
  331.     cmax = (ulong)rem_r+rem_g+rem_b;
  332.     dot4 = cmax + rem_w;
  333.     if ( rem_g > rem_r )
  334.       {    if ( rem_b > rem_g )
  335.           amax = rem_b, axisc = DIAG_B;
  336.         else
  337.           amax = rem_g, axisc = DIAG_G;
  338.         if ( rem_b > rem_r )
  339.           amin = rem_r, fmax = (ulong)rem_g+rem_b, facec = DIAG_GB;
  340.         else
  341.           amin = rem_b, fmax = (ulong)rem_r+rem_g, facec = DIAG_RG;
  342.       }
  343.     else
  344.       {    if ( rem_b > rem_r )
  345.           amax = rem_b, axisc = DIAG_B;
  346.         else
  347.           amax = rem_r, axisc = DIAG_R;
  348.         if ( rem_b > rem_g )
  349.           amin = rem_g, fmax = (ulong)rem_b+rem_r, facec = DIAG_BR;
  350.         else
  351.           amin = rem_b, fmax = (ulong)rem_r+rem_g, facec = DIAG_RG;
  352.       }
  353.     if ( rem_w > amin )
  354.       {    cmax = fmax + rem_w, cubec = facec + DIAG_W;
  355.         if ( rem_w > amax )
  356.           fmax = (ulong)amax + rem_w, facec = axisc + DIAG_W,
  357.           amax = rem_w, axisc = DIAG_W;
  358.         else if ( rem_w > fmax - amax )
  359.           fmax = (ulong)amax + rem_w, facec = axisc + DIAG_W;
  360.       }
  361.     else
  362.         cubec = DIAG_RGB;
  363.  
  364.     dot1 = amax*WEIGHT1;
  365.     dot2 = fmax*WEIGHT2;
  366.     dot3 = cmax*WEIGHT3;
  367.     /*dot4 see above*/
  368. #define use_axis()\
  369.   diagc = axisc, level = (hsize * amax + (frac_1_long / 2)) / frac_1_long
  370. #define use_face()\
  371.   diagc = facec, level = (hsize * fmax + frac_1_long) / (2 * frac_1_long)
  372. #define use_cube()\
  373.   diagc = cubec, level = (hsize * cmax + (3 * frac_1_long / 2)) / (3 * frac_1_long)
  374. #define use_tesseract()\
  375.   diagc = DIAG_RGBW, level = (hsize * dot4 + (2 * frac_1_long)) / (4 * frac_1_long)
  376.     if ( dot1 > dot2 )
  377.       {    if ( dot3 > dot1 )
  378.           {    if ( dot4*WEIGHT4 > dot3 )
  379.               use_tesseract();
  380.             else
  381.               use_cube();
  382.           }
  383.         else
  384.           {    if ( dot4*WEIGHT4 > dot1 )
  385.               use_tesseract();
  386.             else
  387.               use_axis();
  388.           }
  389.       }
  390.     else
  391.       {    if ( dot3 > dot2 )
  392.           {    if ( dot4*WEIGHT4 > dot3 )
  393.               use_tesseract();
  394.             else
  395.               use_cube();
  396.           }
  397.         else
  398.           {    if ( dot4*WEIGHT4 > dot2 )
  399.               use_tesseract();
  400.             else
  401.               use_face();
  402.           }
  403.       };
  404.  
  405.     if_debug12('c', "   %x+0x%x,%x+0x%x,%x+0x%x,%x+x0%x; adjust=%d,%d,%d,%d\n",
  406.           (unsigned)r, (unsigned)rem_r, (unsigned)g, (unsigned)rem_g,
  407.           (unsigned)b, (unsigned)rem_b, (unsigned)w, (unsigned)rem_w,
  408.           adjust_r, adjust_g, adjust_b, adjust_w);
  409.  
  410.     if ( level == 0 )
  411.     {    color_set_pure(pdevc, color1);
  412.         code = 0;
  413.     }
  414.     else
  415.     {    gx_color_index color2;
  416. /* construct the second color, inverting back to original space if needed */
  417.         if (diagc & DIAG_R) r += adjust_r;
  418.         if (diagc & DIAG_G) g += adjust_g;
  419.         if (diagc & DIAG_B) b += adjust_b;
  420.         if (diagc & DIAG_W) w += adjust_w;
  421. /* get the second device color, sorting by luminance */
  422.         vr = fractional_color(r, max_value);
  423.         vg = fractional_color(g, max_value);
  424.         vb = fractional_color(b, max_value);
  425.         vw = fractional_color(w, max_value);
  426.         color2 = map_color();
  427.         if ( level == num_levels )
  428.           {    /* This can only happen through rounding.... */
  429.             color_set_pure(pdevc, color2);
  430.             code = 0;
  431.           }
  432.         else
  433.           {    if ( lum_w[diagc] < lum_invert )
  434.               color_set_binary_halftone(pdevc, color2, color1, hsize - level);
  435.             else
  436.               color_set_binary_halftone(pdevc, color1, color2, level);
  437.             code = gx_color_load(pdevc, pgs);
  438.           }
  439.     }
  440.  
  441.     if_debug7('c', "[c]diagc=%d; colors=0x%lx,0x%lx; level=%d/%d; lum=%d,diag=%d\n",
  442.           diagc, (ulong)pdevc->colors.binary.color[0],
  443.           (ulong)pdevc->colors.binary.color[1],
  444.           level, (unsigned)hsize, lum_invert, lum_w[diagc]);
  445.     return code;
  446.   }
  447. }
  448.