1
/* Copyright (C) 2001-2006 Artifex Software, Inc.
4
This software is provided AS-IS with no warranty, either express or
7
This software is distributed under license and may not be copied, modified
8
or distributed except as expressly authorized under the terms of that
9
license. Refer to licensing information at http://www.artifex.com/
10
or contact Artifex Software, Inc., 7 Mt. Lassen Drive - Suite A-134,
11
San Rafael, CA 94903, U.S.A., +1(415)492-9861, for further information.
13
/*$Id: gxwts.c 8632 2008-04-10 05:43:43Z leonardo $ */
14
/* Rendering using Well Tempered Screening. */
16
#include "memory_.h" /* for memcmp */
28
#define GXWTS_USE_DOUBLE
31
/* device color type for wts. */
33
/* todo: trace and relocate pointers */
34
gs_private_st_simple(st_dc_wts, gx_device_color, "dc_wts");
35
static dev_color_proc_save_dc(gx_dc_wts_save_dc);
36
static dev_color_proc_get_dev_halftone(gx_dc_wts_get_dev_halftone);
37
static dev_color_proc_load(gx_dc_wts_load);
38
static dev_color_proc_fill_rectangle(gx_dc_wts_fill_rectangle);
39
static dev_color_proc_equal(gx_dc_wts_equal);
40
static dev_color_proc_write(gx_dc_wts_write);
41
static dev_color_proc_read(gx_dc_wts_read);
42
static dev_color_proc_get_nonzero_comps(gx_dc_wts_get_nonzero_comps);
43
const gx_device_color_type_t gx_dc_type_data_wts = {
45
gx_dc_wts_save_dc, gx_dc_wts_get_dev_halftone,
47
gx_dc_wts_load, gx_dc_wts_fill_rectangle,
48
gx_dc_default_fill_masked, gx_dc_wts_equal,
49
gx_dc_wts_write, gx_dc_wts_read,
50
gx_dc_wts_get_nonzero_comps
53
const gx_device_color_type_t *const gx_dc_type_wts =
57
/* Low-level implementation follows. */
60
* mul_shr_16: Multiply and shift right 16.
61
* @a: 32-bit signed number.
62
* @b: 32-bit signed number.
64
* Multiply @a and @b, then shift right 16 bits. Allow intermediate value
65
* to overflow 32 bits.
67
* Return value: result.
69
#ifdef GXWTS_USE_DOUBLE
71
mul_shr_16 (int a, int b)
73
return (int)floor(((double) a) * ((double) b) * (1.0 / (1 << 16)));
76
#error todo: supply mul_shr_16 based on 64 bit integer type
79
/* Implementation of wts_get_samples for rational cells. */
82
wts_get_samples_rat(const wts_screen_t *ws, int x, int y,
83
int *pcellx, int *pcelly, int *p_nsamples)
85
int d = y / ws->cell_height;
86
int r = y % ws->cell_height;
87
int x_ix = ((d * ws->cell_shift) + x) % ws->cell_width;
88
*p_nsamples = ws->cell_width - x_ix;
95
#define MOD_IS_SLOWER_THAN_BRANCH
97
#ifdef WTS_CACHE_SIZE_X
98
/* Implementation of wts_get_samples for Screen J, with cache. */
100
wts_get_samples_j(wts_screen_t *ws, int x, int y,
101
int *pcellx, int *pcelly, int *p_nsamples)
105
wts_screen_j_t *wsj = (wts_screen_j_t *)ws;
106
wts_j_cache_el *xcache = &wsj->xcache[(x >> 3) & (WTS_CACHE_SIZE_X - 1)];
107
wts_j_cache_el *ycache = &wsj->ycache[y & (WTS_CACHE_SIZE_Y - 1)];
109
if (xcache->tag != x || (x & 7)) {
110
double pad = (wsj->pa) * (1.0 / (1 << 16));
111
double pbd = (wsj->pb) * (1.0 / (1 << 16));
112
double afrac = x * pad;
113
double bfrac = x * pbd;
114
int acount = (int)floor(afrac);
115
int bcount = (int)floor(bfrac);
116
int nsa = (int)ceil((acount + 1 - afrac) / pad);
117
int nsb = (int)ceil((acount + 1 - afrac) / pad);
119
xcache->x = x + acount * wsj->XA + bcount * wsj->XB;
120
xcache->y = acount * wsj->YA + bcount * wsj->YB;
121
#ifdef MOD_IS_SLOWER_THAN_BRANCH
122
xcache->x += (xcache->y / ws->cell_height) * ws->cell_shift;
123
xcache->y %= ws->cell_height;
125
xcache->nsamples = min(nsa, nsb);
130
nsamples = xcache->nsamples;
132
if (ycache->tag != y) {
133
int ccount = mul_shr_16(y, wsj->pc);
134
int dcount = mul_shr_16(y, wsj->pd);
136
ycache->x = ccount * wsj->XC + dcount * wsj->XD;
137
ycache->y = y + ccount * wsj->YC + dcount * wsj->YD;
138
#ifdef MOD_IS_SLOWER_THAN_BRANCH
139
ycache->x += (ycache->y / ws->cell_height) * ws->cell_shift;
140
ycache->y %= ws->cell_height;
147
#ifdef MOD_IS_SLOWER_THAN_BRANCH
148
if (y_ix >= ws->cell_height) {
149
x_ix += ws->cell_shift;
150
y_ix -= ws->cell_height;
153
x_ix += (y_ix / ws->cell_height) * ws->cell_shift;
154
y_ix %= ws->cell_height;
156
x_ix %= ws->cell_width;
158
nsamples = min(nsamples, ws->cell_width - x_ix);
159
*p_nsamples = nsamples;
165
/* Implementation of wts_get_samples for Screen J. */
167
wts_get_samples_j(wts_screen_t *ws, int x, int y,
168
int *pcellx, int *pcelly, int *p_nsamples)
170
const wts_screen_j_t *wsj = (const wts_screen_j_t *)ws;
171
/* int d = y / ws->cell_height; */
174
double pad = (wsj->pa) * (1.0 / (1 << 16));
175
double pbd = (wsj->pb) * (1.0 / (1 << 16));
176
double afrac = x * pad;
177
double bfrac = x * pbd;
178
int acount = (int)floor(afrac);
179
int bcount = (int)floor(bfrac);
180
int ccount = mul_shr_16(y, wsj->pc);
181
int dcount = mul_shr_16(y, wsj->pd);
184
x_ix += acount * wsj->XA + bcount * wsj->XB +
185
ccount * wsj->XC + dcount * wsj->XD;
186
y_ix += acount * wsj->YA + bcount * wsj->YB +
187
ccount * wsj->YC + dcount * wsj->YD;
189
x_ix += (y_ix / ws->cell_height) * ws->cell_shift;
190
x_ix %= ws->cell_width;
191
y_ix %= ws->cell_height;
193
nsamples = ws->cell_width - x_ix;
194
if (floor (afrac + (nsamples - 1) * pad) > acount)
195
nsamples = (int)ceil((acount + 1 - afrac) / pad);
197
if (floor (bfrac + (nsamples - 1) * pbd) > bcount)
198
nsamples = (int)ceil((bcount + 1 - bfrac) / pbd);
200
printf("get_samples: (%d, %d) -> (%d, %d) %d (cc=%d)\n",
201
x, y, x_ix, y_ix, nsamples, ccount);
203
*p_nsamples = nsamples;
211
wts_screen_h_offset(int x, double p1, int m1, int m2)
213
/* todo: this is a linear search; constant time should be feasible */
214
double running_p = 0;
218
for (width_so_far = 0;; width_so_far += this_width) {
220
if (running_p >= 0.5) {
226
if (width_so_far + this_width > x)
229
return x - width_so_far + (this_width == m1 ? 0 : m1);
232
/* Implementation of wts_get_samples for Screen H. */
234
wts_get_samples_h(const wts_screen_t *ws, int x, int y,
235
int *pcellx, int *pcelly, int *p_nsamples)
237
const wts_screen_h_t *wsh = (const wts_screen_h_t *)ws;
238
int x_ix = wts_screen_h_offset(x, wsh->px,
239
wsh->x1, ws->cell_width - wsh->x1);
240
int y_ix = wts_screen_h_offset(y, wsh->py,
241
wsh->y1, ws->cell_height - wsh->y1);
242
*p_nsamples = (x_ix >= wsh->x1 ? ws->cell_width : wsh->x1) - x_ix;
249
* wts_get_samples: Get samples from Well Tempered Screening cell.
250
* @ws: Well Tempered Screening cell.
251
* @x: X coordinate of starting point.
252
* @y: Y coordinate of starting point.
253
* @samples: Where to store pointer to samples.
254
* @p_nsamples: Where to store number of valid samples.
256
* Finds samples from the cell for use in halftoning. On success,
257
* @p_nsamples is set to the number of valid samples, ie for 0 <= i <
258
* nsamples, samples[i] is a valid sample for coordinate (x + i, y).
259
* p_nsamples is guaranteed to at least 1. The samples in @samples
260
* are valid for the lifetime of the cell, or until the next garbage
261
* collection, whichever comes first.
263
* Todo: describe meaning of wts_screen_sample_t (particularly edge
266
* Note: may want to add a "cursor" to the api as an optimization. It
269
* Return value: 0 on success.
272
wts_get_samples(wts_screen_t *ws, int x, int y,
273
int *pcellx, int *pcelly, int *p_nsamples)
275
if (ws->type == WTS_SCREEN_J)
276
return wts_get_samples_j(ws, x, y, pcellx, pcelly, p_nsamples);
277
if (ws->type == WTS_SCREEN_H)
278
return wts_get_samples_h(ws, x, y, pcellx, pcelly, p_nsamples);
283
/* Device color methods follow. */
286
gx_dc_wts_save_dc(const gx_device_color * pdevc, gx_device_color_saved * psdc)
288
psdc->type = pdevc->type;
289
memcpy( psdc->colors.wts.levels,
290
pdevc->colors.wts.levels,
291
sizeof(psdc->colors.wts.levels) );
292
psdc->phase = pdevc->phase;
295
static const gx_device_halftone *
296
gx_dc_wts_get_dev_halftone(const gx_device_color * pdevc)
298
return pdevc->colors.wts.w_ht;
302
gx_dc_wts_load(gx_device_color *pdevc, const gs_imager_state * pis,
303
gx_device *ignore_dev, gs_color_select_t select)
309
* wts_draw: Draw a halftoned shade into a 1 bit deep buffer.
311
* @shade: Gray shade to draw.
312
* @data: Destination buffer.
313
* @data_raster: Rowstride for destination buffer.
314
* @x, @y, @w, @h: coordinates of rectangle to draw.
316
* This is close to an implementation of the "draw" method for the
317
* gx_ht_order class. Currently, only WTS screens implement this
318
* method, and only WTS device colors invoke it. However, implementing
319
* this for legacy order objects is probably a good idea, to improve
320
* halftoning performance as the cell size scales up.
322
* However, it's not exactly an implementation of the "draw" method
323
* for the gx_ht_order class because the "self" type would need to be
324
* gx_ht_order. Currently, however, device colors don't hold a pointer
325
* to the order object. Some amount of refactoring seems to be in
328
* Return value: 0 on success.
331
wts_draw(wts_screen_t *ws, wts_screen_sample_t shade,
332
byte *data, int data_raster,
333
int x, int y, int w, int h)
336
unsigned char *line_start = data;
338
for (yo = 0; yo < h; yo++) {
339
unsigned char *line_ptr = line_start;
344
for (xo = 0; xo < w; xo += imax) {
345
wts_screen_sample_t *samples;
349
wts_get_samples(ws, x + xo, y + yo, &cx, &cy, &n_samples);
350
samples = ws->samples + cy * ws->cell_width + cx;
351
imax = min(w - xo, n_samples);
352
for (i = 0; i < imax; i++) {
353
if (shade > samples[i])
365
line_start += data_raster;
371
* Special case implementation for one component. When we do plane_mask,
372
* we'll want to generalize this to handle any single-bit plane_mask.
375
gx_dc_wts_fill_rectangle_1(const gx_device_color *pdevc,
376
int x, int y, int w, int h,
377
gx_device *dev, gs_logical_operation_t lop,
378
const gx_rop_source_t *source)
380
/* gx_rop_source_t no_source; */
381
int tile_raster = ((w + 31) & -32) >> 3;
382
int tile_size = tile_raster * h;
383
unsigned char *tile_data;
385
gx_ht_order_component *components = pdevc->colors.wts.w_ht->components;
386
wts_screen_t *ws = components[0].corder.wts;
387
wts_screen_sample_t shade = pdevc->colors.wts.levels[0];
388
gx_color_index color0, color1;
389
int xph = pdevc->phase.x;
390
int yph = pdevc->phase.y;
392
color0 = dev->color_info.separable_and_linear == GX_CINFO_SEP_LIN ? 0 :
393
pdevc->colors.wts.plane_vector[1];
394
color1 = pdevc->colors.wts.plane_vector[0];
396
tile_data = malloc(tile_size);
398
wts_draw(ws, shade, tile_data, tile_raster, x - xph, y - yph, w, h);
400
/* See gx_dc_ht_binary_fill_rectangle() for explanation. */
401
if (dev->color_info.depth > 1)
402
lop &= ~lop_T_transparent;
404
/* Interesting question: should data_x be (x & 7), rather than 0,
405
to improve alignment? */
406
if (source == NULL && lop_no_S_is_T(lop))
407
code = (*dev_proc(dev, copy_mono))
408
(dev, tile_data, 0, tile_raster, gx_no_bitmap_id,
409
x, y, w, h, color0, color1);
417
const gx_device_color * pdevc,
418
const gx_device_color_saved * psdc,
419
const gx_device * dev,
424
/* not yet implemented */
425
return_error(gs_error_unknownerror);
430
gx_device_color * pdevc,
431
const gs_imager_state * pis,
432
const gx_device_color * prior_devc,
433
const gx_device * dev,
439
/* not yet implemented */
440
return_error(gs_error_unknownerror);
445
* wts_repack_tile_4: Repack four 1-bit tiles into chunky nibbles.
446
* Note: argument list will change. plane_mask and base_color will
447
* probably get added as an optimization.
449
* Note: we round w up to an even value. We're counting on the
450
* subsequent copy_color to ignore any extra bits.
453
wts_repack_tile_4(unsigned char *ctile_data, int ctile_raster,
454
const unsigned char **tile_data, int tile_raster,
455
const gx_color_index *plane_vector, bool invert,
459
int tile_idx_start = 0;
460
unsigned char *ctile_start = ctile_data;
461
byte inv_byte = invert ? 0xff : 0;
463
for (y = 0; y < h; y++) {
465
int tile_idx = tile_idx_start;
467
for (x = 0; x < w; x += 2) {
469
byte m0 = 0x80 >> (x & 6);
473
td = tile_data[0][tile_idx] ^ inv_byte;
474
if (td & m0) b |= plane_vector[0] << 4;
475
if (td & m1) b |= plane_vector[0];
477
td = tile_data[1][tile_idx] ^ inv_byte;
478
if (td & m0) b |= plane_vector[1] << 4;
479
if (td & m1) b |= plane_vector[1];
481
td = tile_data[2][tile_idx] ^ inv_byte;
482
if (td & m0) b |= plane_vector[2] << 4;
483
if (td & m1) b |= plane_vector[2];
485
td = tile_data[3][tile_idx] ^ inv_byte;
486
if (td & m0) b |= plane_vector[3] << 4;
487
if (td & m1) b |= plane_vector[3];
491
ctile_start[x >> 1] = b;
493
tile_idx_start += tile_raster;
494
ctile_start += ctile_raster;
498
/* Special case implementation for four components. Intermediate color
499
* to the order objecttile (for copy_color) is packed 2 to a byte.
501
* Looking at this code, it should generalize to more than four
502
* components. Probably the repack code should get factored out.
505
gx_dc_wts_fill_rectangle_4(const gx_device_color *pdevc,
506
int x, int y, int w, int h,
507
gx_device *dev, gs_logical_operation_t lop,
508
const gx_rop_source_t *source)
510
int num_comp = pdevc->colors.wts.num_components;
511
/* gx_rop_source_t no_source; */
513
int tile_raster = ((w + 31) & -32) >> 3;
514
int tile_size = tile_raster * h;
515
unsigned char *tile_data[4];
517
int ctile_raster = ((w + 7) & -8) >> 1;
518
int ctile_size = ctile_raster * h;
519
unsigned char *ctile_data;
522
bool invert = 0 && dev->color_info.polarity == GX_CINFO_POLARITY_SUBTRACTIVE;
524
int xph = pdevc->phase.x;
525
int yph = pdevc->phase.y;
527
for (i = 0; i < num_comp; i++) {
528
wts_screen_sample_t shade = pdevc->colors.wts.levels[i];
529
gx_ht_order_component *components = pdevc->colors.wts.w_ht->components;
530
wts_screen_t *ws = components[i].corder.wts;
532
tile_data[i] = malloc(tile_size);
533
wts_draw(ws, shade, tile_data[i], tile_raster, x - xph, y - yph, w, h);
536
ctile_data = malloc(ctile_size);
537
wts_repack_tile_4(ctile_data, ctile_raster,
538
(const unsigned char **)tile_data, tile_raster,
539
pdevc->colors.wts.plane_vector, invert, w, h);
541
/* See gx_dc_ht_binary_fill_rectangle() for explanation. */
542
if (dev->color_info.depth > 1)
543
lop &= ~lop_T_transparent;
545
if (source == NULL && lop_no_S_is_T(lop))
546
code = (*dev_proc(dev, copy_color))
547
(dev, ctile_data, 0, ctile_raster, gx_no_bitmap_id,
551
for (i = 0; i < num_comp; i++) {
559
gx_dc_wts_fill_rectangle(const gx_device_color *pdevc,
560
int x, int y, int w, int h,
561
gx_device *dev, gs_logical_operation_t lop,
562
const gx_rop_source_t *source)
564
int num_comp = pdevc->colors.wts.num_components;
567
return gx_dc_wts_fill_rectangle_1(pdevc, x, y, w, h, dev, lop, source);
568
else if (num_comp <= 4)
569
return gx_dc_wts_fill_rectangle_4(pdevc, x, y, w, h, dev, lop, source);
574
/* Compare two wts colors for equality. */
576
gx_dc_wts_equal(const gx_device_color *pdevc1,
577
const gx_device_color *pdevc2)
579
uint num_comp = pdevc1->colors.wts.num_components;
581
if (pdevc2->type != pdevc1->type ||
582
pdevc1->phase.x != pdevc2->phase.x ||
583
pdevc1->phase.y != pdevc2->phase.y ||
584
num_comp != pdevc2->colors.wts.num_components
588
!memcmp(pdevc1->colors.wts.levels,
589
pdevc2->colors.wts.levels,
590
num_comp * sizeof(pdevc1->colors.wts.levels[0]));
594
* Get the nonzero components of a wts halftone. This is used to
595
* distinguish components that are given zero intensity due to halftoning
596
* from those for which the original color intensity was in fact zero.
599
gx_dc_wts_get_nonzero_comps(
600
const gx_device_color * pdevc,
601
const gx_device * dev_ignored,
602
gx_color_index * pcomp_bits )
604
int i, ncomps = pdevc->colors.wts.num_components;
605
gx_color_index comp_bits = 0; /* todo: plane_mask */
607
for (i = 0; i < ncomps; i++) {
608
if (pdevc->colors.wts.levels[i] != 0)
609
comp_bits |= ((gx_color_index)1) << i;
611
*pcomp_bits = comp_bits;