1 /* Copyright (C) 1995, 1996, 1997, 1999, 2000 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: gxdht.h,v 1.9 2005/03/14 18:08:37 dan Exp $ */ 18 /* Definition of device halftones */ 19 20 #ifndef gxdht_INCLUDED 21 # define gxdht_INCLUDED 22 23 #include "gsrefct.h" 24 #include "gsmatrix.h" 25 #include "gxarith.h" /* for igcd */ 26 #include "gxhttype.h" 27 #include "gscspace.h" 28 #include "gxcindex.h" 29 #include "gxfrac.h" 30 31 /* 32 * We represent a halftone tile as a rectangular super-cell consisting of 33 * multiple copies of a multi-cell whose corners lie on integral 34 * coordinates, which in turn is a parallelogram (normally square) array of 35 * basic parallelogram (normally square) cells whose corners lie on rational 36 * coordinates. 37 * 38 * Let T be the aspect ratio (ratio of physical pixel height to physical 39 * pixel width), which is abs(xx/yy) for portrait devices and abs(yx/xy) for 40 * landscape devices. We characterize the basic cell by four rational 41 * numbers U(') = M(')/R(') and V(') = N(')/R(') where R(') is positive, at 42 * least one of U and V (and the corresponding one of U' and V') is 43 * non-zero, and U' is approximately U/T and V' is approximately V*T; these 44 * numbers define the vertices of the basic cell at device space coordinates 45 * (0,0), (U,V), (U-V',U'+V), and (-V',U'); then the multi-cell is defined 46 * similarly by M(') and N('). From these definitions, the basic cell has 47 * an area of B = U*U' + V*V' = (M*M' + N*N') / R*R' pixels, and the 48 * multi-cell has an area of C = B * R*R' = M*M' + N*N' pixels. 49 * 50 * If the coefficients of the default device transformation matrix are xx, 51 * xy, yx, and yy, then U and V are related to the frequency F and the angle 52 * A by: 53 * P = 72 / F; 54 * U = P * (xx * cos(A) + yx * sin(A)); 55 * V = P * (xy * cos(A) + yy * sin(A)). 56 * 57 * We can tile the plane with any rectangular super-cell that consists of 58 * repetitions of the multi-cell and whose corners coincide with multi-cell 59 * coordinates (0,0). We observe that for any integers i, j such that i*N - 60 * j*M' = 0, a multi-cell corner lies on the X axis at W = i*M + j*N'; 61 * similarly, if i'*M - j'*N' = 0, a corner lies on the Y axis at W' = i'*N 62 * + j'*M'. Then the super-cell occupies Z = W * W' pixels, consisting of Z 63 * / C multi-cells or Z / B basic cells. The trick in all this is to find 64 * values of F and A that aren't too far from the requested ones, and that 65 * yield a manageably small value for Z. 66 * 67 * Note that the super-cell only has to be so large because we want to use 68 * it directly to tile the plane. In fact, we can decompose it into W' / D 69 * horizontal strips of width W and height D, shifted horizontally with 70 * respect to each other by S pixels, where we compute S by finding h and k 71 * such that h*N - k*M' = D and then S = h*M + k*N'. The halftone setup 72 * routines only generate a single strip of samples, and let 73 * gx_ht_construct_spot_order construct the rest. If W' is large, we 74 * actually keep only one strip, and let the strip_tile_rectangle routines 75 * do the shifting at rendering time. 76 */ 77 typedef struct gx_ht_cell_params_s { 78 /* Defining values. M * M1 != 0 or N * N1 != 0; R > 0, R1 > 0. */ 79 /* R and D are short rather than ushort so that we don't get */ 80 /* unsigned results from arithmetic. */ 81 short M, N, R; 82 short M1, N1, R1; 83 /* Derived values. */ 84 ulong C; 85 short D, D1; 86 uint W, W1; 87 int S; 88 } gx_ht_cell_params_t; 89 90 /* Compute the derived values from the defining values. */ 91 void gx_compute_cell_values(gx_ht_cell_params_t *); 92 93 /* 94 * The whitening order is represented by a pair of arrays. 95 * The levels array contains an integer (an index into the bit_data array) 96 * for each distinct halftone level, indicating how many pixels should be 97 * whitened for that level; levels[0] = 0, levels[i] <= levels[i+1], and 98 * levels[num_levels-1] <= num_bits. The bit_data array contains data to 99 * specify which bits should be set for each level: it has several 100 * different representations depending on space/time tradeoffs. 101 * 102 * The default bit_data representation is an (offset,mask) pair for each 103 * pixel in the tile. bits[i].offset is the (properly aligned) byte index 104 * of a pixel in the tile; bits[i].mask is the mask to be or'ed into this 105 * byte and following ones. This is arranged so it will work properly on 106 * either big- or little-endian machines, and with different mask widths. 107 */ 108 /* 109 * The mask width must be at least as wide as uint, 110 * and must not be wider than the width implied by align_bitmap_mod. 111 */ 112 typedef uint ht_mask_t; 113 114 #define ht_mask_bits (sizeof(ht_mask_t) * 8) 115 typedef struct gx_ht_bit_s { 116 uint offset; 117 ht_mask_t mask; 118 } gx_ht_bit; 119 120 /* During sampling, bits[i].mask is used to hold a normalized sample value. */ 121 typedef ht_mask_t ht_sample_t; 122 123 /* The following awkward expression avoids integer overflow. */ 124 #define max_ht_sample (ht_sample_t)(((1 << (ht_mask_bits - 2)) - 1) * 2 + 1) 125 126 #ifndef wts_screen_t_DEFINED 127 # define wts_screen_t_DEFINED 128 typedef struct wts_screen_s wts_screen_t; 129 #endif 130 131 #ifndef gs_wts_screen_enum_t_DEFINED 132 # define gs_wts_screen_enum_t_DEFINED 133 typedef struct gs_wts_screen_enum_s gs_wts_screen_enum_t; 134 #endif 135 136 /* 137 * Define the internal representation of a halftone order. 138 * Note that it may include a cached transfer function. 139 * 140 * Halftone orders exist in two slightly different configurations, strip and 141 * complete. In a complete order, shift = 0 and full_height = height; in a 142 * strip order, shift != 0 and full_height is the height of a fully expanded 143 * halftone made up of enough shifted strip copies to get back to a zero 144 * shift. In other words, full_height is a cached value, but it is an 145 * important one, since it is the modulus used for computing the 146 * tile-relative phase. Requirements: 147 * width > 0, height > 0, multiple > 0 148 * raster >= bitmap_raster(width) 149 * 0 <= shift < width 150 * num_bits = width * height 151 * For complete orders: 152 * full_height = height 153 * For strip orders: 154 * full_height = height * width / gcd(width, shift) 155 * Note that during the sampling of a complete spot halftone, these 156 * invariants may be violated; in particular, it is possible that shift != 0 157 * and height < full_height, even though num_bits and num_levels reflect the 158 * full height. In this case, the invariant is restored (by resetting 159 * shift and height) when sampling is finished. However, we must save the 160 * original height and shift values used for sampling, since sometimes we 161 * run the "finishing" routines more than once. (This is ugly, but it's 162 * too hard to fix.) 163 * 164 * See gxbitmap.h for more details about strip halftones. 165 */ 166 typedef struct gx_ht_cache_s gx_ht_cache; 167 #ifndef gx_ht_order_DEFINED 168 # define gx_ht_order_DEFINED 169 typedef struct gx_ht_order_s gx_ht_order; 170 #endif 171 #ifndef gx_ht_tile_DEFINED 172 # define gx_ht_tile_DEFINED 173 typedef struct gx_ht_tile_s gx_ht_tile; 174 #endif 175 typedef struct gx_ht_order_procs_s { 176 177 /* Define the size of each element of bit_data. */ 178 179 uint bit_data_elt_size; 180 181 /* Construct the order from the threshold array. */ 182 /* Note that for 16-bit threshold values, */ 183 /* each value is 2 bytes in big-endian order (Adobe spec). */ 184 185 int (*construct_order)(gx_ht_order *order, const byte *thresholds); 186 187 /* Return the (x,y) coordinate of an element of bit_data. */ 188 189 int (*bit_index)(const gx_ht_order *order, uint index, 190 gs_int_point *ppt); 191 192 /* Update a halftone cache tile to match this order. */ 193 194 int (*render)(gx_ht_tile *tile, int new_bit_level, 195 const gx_ht_order *order); 196 197 /* Draw a halftone shade into a 1 bit deep buffer. */ 198 /* Note: this is a tentative design for a new method. I may not 199 keep it. */ 200 int (*draw)(gx_ht_order *order, frac shade, 201 byte *data, int data_raster, 202 int x, int y, int w, int h); 203 204 } gx_ht_order_procs_t; 205 /* 206 * Define the procedure vectors for the supported implementations 207 * (in gxhtbit.c). 208 */ 209 extern const gx_ht_order_procs_t ht_order_procs_table[2]; 210 #define ht_order_procs_default ht_order_procs_table[0] /* bit_data is gx_ht_bit[] */ 211 #define ht_order_procs_short ht_order_procs_table[1] /* bit_data is ushort[] */ 212 /* For screen/spot halftones, we must record additional parameters. */ 213 typedef struct gx_ht_order_screen_params_s { 214 gs_matrix matrix; /* CTM when the function was sampled */ 215 ulong max_size; /* max bitmap size */ 216 } gx_ht_order_screen_params_t; 217 struct gx_ht_order_s { 218 gx_ht_cell_params_t params; /* parameters defining the cells */ 219 gs_wts_screen_enum_t *wse; 220 wts_screen_t *wts; /* if non-NULL, then rest of the structure is irrelevant */ 221 ushort width; 222 ushort height; 223 ushort raster; 224 ushort shift; 225 ushort orig_height; 226 ushort orig_shift; 227 uint full_height; 228 uint num_levels; /* = levels size */ 229 uint num_bits; /* = countof(bit_data) = width * height */ 230 const gx_ht_order_procs_t *procs; 231 gs_memory_t *data_memory; /* for levels and bit_data, may be 0 */ 232 uint *levels; 233 void *bit_data; 234 gx_ht_cache *cache; /* cache to use */ 235 gx_transfer_map *transfer; /* TransferFunction or 0 */ 236 gx_ht_order_screen_params_t screen_params; 237 }; 238 239 #define ht_order_is_complete(porder)\ 240 ((porder)->shift == 0) 241 #define ht_order_full_height(porder)\ 242 ((porder)->shift == 0 ? (porder)->height :\ 243 (porder)->width / igcd((porder)->width, (porder)->shift) *\ 244 (porder)->height) 245 246 /* We only export st_ht_order for use in st_screen_enum. */ 247 extern_st(st_ht_order); 248 #define public_st_ht_order() /* in gsht.c */\ 249 gs_public_st_composite(st_ht_order, gx_ht_order, "gx_ht_order",\ 250 ht_order_enum_ptrs, ht_order_reloc_ptrs) 251 #define st_ht_order_max_ptrs 4 252 253 /* 254 * Define a device halftone. This consists of one or more orders. 255 * If components = 0, then order is the only current halftone screen 256 * (set by setscreen, Type 1 sethalftone, Type 3 sethalftone, or 257 * Type 5 sethalftone with only a Default). Otherwise, order is the 258 * gray or black screen (for gray/RGB or CMYK devices respectively), 259 * and components is an array of gx_ht_order_components parallel to 260 * the components of the client halftone (set by setcolorscreen or 261 * Type 5 sethalftone). 262 * 263 * Multi-component halftone orders may be required even in Level 1 systems, 264 * because they are needed for setcolorscreen. 265 * 266 * NOTE: it is assumed that all subsidiary structures of device halftones 267 * (the components array, and the bit_data, levels, cache, and transfer 268 * members of any gx_ht_orders, both the default order and any component 269 * orders) are allocated with the same allocator as the device halftone 270 * itself. 271 */ 272 typedef struct gx_ht_order_component_s { 273 gx_ht_order corder; 274 int comp_number; 275 int cname; 276 } gx_ht_order_component; 277 278 #define private_st_ht_order_component() /* in gsht.c */\ 279 gs_private_st_ptrs_add0(st_ht_order_component, gx_ht_order_component,\ 280 "gx_ht_order_component", ht_order_component_enum_ptrs,\ 281 ht_order_component_reloc_ptrs, st_ht_order, corder) 282 #define st_ht_order_component_max_ptrs st_ht_order_max_ptrs 283 /* We only export st_ht_order_component_element for use in banding. */ 284 extern_st(st_ht_order_component_element); 285 #define public_st_ht_order_comp_element() /* in gsht.c */\ 286 gs_public_st_element(st_ht_order_component_element, gx_ht_order_component,\ 287 "gx_ht_order_component[]", ht_order_element_enum_ptrs,\ 288 ht_order_element_reloc_ptrs, st_ht_order_component) 289 290 #ifndef gx_device_halftone_DEFINED 291 # define gx_device_halftone_DEFINED 292 typedef struct gx_device_halftone_s gx_device_halftone; 293 #endif 294 295 /* 296 * Device Halftone Structure definition. See comments before 297 * gx_imager_dev_ht_install() for more information on this structure and its 298 * fields. 299 */ 300 struct gx_device_halftone_s { 301 gx_ht_order order; /* must be first, for subclassing */ 302 rc_header rc; 303 gs_id id; /* the id changes whenever the data change */ 304 /* 305 * We have to keep the halftone type so that we can pass it 306 * through the band list for gx_imager_dev_ht_install. 307 */ 308 gs_halftone_type type; 309 gx_ht_order_component *components; 310 311 uint num_comp; /* Number of components in the halftone */ 312 uint num_dev_comp; /* Number of process color model components */ 313 /* The following are computed from the above. */ 314 int lcm_width, lcm_height; /* LCM of primary color tile sizes, */ 315 /* max_int if overflowed */ 316 }; 317 318 extern_st(st_device_halftone); 319 #define public_st_device_halftone() /* in gsht.c */\ 320 gs_public_st_ptrs_add1(st_device_halftone, gx_device_halftone,\ 321 "gx_device_halftone", device_halftone_enum_ptrs,\ 322 device_halftone_reloc_ptrs, st_ht_order, order, components) 323 #define st_device_halftone_max_ptrs (st_ht_order_max_ptrs + 1) 324 325 /* Complete a halftone order defined by a threshold array. */ 326 void gx_ht_complete_threshold_order(gx_ht_order *porder); 327 328 /* Release a gx_device_halftone by freeing its components. */ 329 /* (Don't free the gx_device_halftone itself.) */ 330 void gx_device_halftone_release(gx_device_halftone * pdht, gs_memory_t * mem); 331 332 #endif /* gxdht_INCLUDED */ 333