Commit | Line | Data |
---|---|---|
ad0cc502 WJ |
1 | /* Copyright (C) 1989, 1992 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 | /* gxdraw.c */ | |
21 | /* Primitive drawing routines for Ghostscript imaging library */ | |
22 | #include "gx.h" | |
23 | #include "math_.h" | |
24 | #include "gxfixed.h" | |
25 | #include "gxmatrix.h" | |
26 | #include "gzstate.h" | |
27 | #include "gzdevice.h" /* requires gsstate.h */ | |
28 | #include "gzcolor.h" /* requires gxdevice.h */ | |
29 | ||
30 | /* Fill a rectangle. */ | |
31 | int | |
32 | gz_fill_rectangle(int x, int y, int w, int h, gx_device_color *pdevc, | |
33 | gs_state *pgs) | |
34 | { gx_device *dev = pgs->device->info; | |
35 | #ifdef DEBUG | |
36 | if ( gs_debug['v'] ) | |
37 | dprintf7("[v]x=%d y=%d w=%d h=%d c1=%ld c2=%ld htl=%d\n", | |
38 | x, y, w, h, (long)pdevc->color1, (long)pdevc->color2, | |
39 | (long)pdevc->halftone_level); | |
40 | #endif | |
41 | return gz_fill_rectangle_open(dev, x, y, w, h, dev->procs->fill_rectangle, dev->procs->tile_rectangle, pdevc, pgs); | |
42 | } | |
43 | ||
44 | /* | |
45 | * Auxiliary procedures for computing a * b / c and a * b % c | |
46 | * when a, b, and c are all non-negative, | |
47 | * b < c, and a * b exceeds (or might exceed) the capacity of a long. | |
48 | * It's really annoying that C doesn't provide any way to get at | |
49 | * the double-length multiply/divide instructions that | |
50 | * the machine undoubtedly provides.... | |
51 | * | |
52 | * Note that these routines are exported for the benefit of gxfill.c. | |
53 | */ | |
54 | ||
55 | fixed | |
56 | fixed_mult_quo(fixed a, fixed b, fixed c) | |
57 | { return (fixed)floor((double)a * b / c); | |
58 | } | |
59 | fixed | |
60 | fixed_mult_rem(fixed a, fixed b, fixed c) | |
61 | { double prod = (double)a * b; | |
62 | return (fixed)(prod - floor(prod / c) * c); | |
63 | } | |
64 | ||
65 | /* Fill a trapezoid. Requires: wt >= 0, wb >= 0, h >= 0. */ | |
66 | /* Note that the arguments are fixeds, not ints! */ | |
67 | /* This is derived from Paul Haeberli's floating point algorithm. */ | |
68 | typedef struct trap_line_s { | |
69 | int di; fixed df; /* dx/dy ratio */ | |
70 | fixed ldi, ldf; /* increment per scan line */ | |
71 | fixed x, xf; /* current value */ | |
72 | } trap_line; | |
73 | int | |
74 | gz_fill_trapezoid_fixed(fixed fx0, fixed fw0, fixed fy0, | |
75 | fixed fx1, fixed fw1, fixed fh, int swap_axes, | |
76 | gx_device_color *pdevc, gs_state *pgs) | |
77 | { const fixed ymin = fixed_rounded(fy0) + float2fixed(0.5); | |
78 | const fixed ymax = fixed_rounded(fy0 + fh); | |
79 | int iy = fixed2int_var(ymin); | |
80 | const int iy1 = fixed2int_var(ymax); | |
81 | if ( iy >= iy1 ) return 0; /* no scan lines to sample */ | |
82 | { trap_line l, r; | |
83 | int rxl, rxr, ry; | |
84 | const fixed dxl = fx1 - fx0; | |
85 | const fixed dxr = dxl + fw1 - fw0; | |
86 | const fixed yline = ymin - fy0; /* partial pixel offset to */ | |
87 | /* first line to sample */ | |
88 | int fill_direct = color_is_pure(pdevc); | |
89 | gx_color_index cindex; | |
90 | gx_device *dev; | |
91 | dev_proc_fill_rectangle((*fill_rect)); | |
92 | int code; | |
93 | ||
94 | r.x = (l.x = fx0 + float2fixed(0.5)) + fw0; | |
95 | if ( fill_direct ) | |
96 | cindex = pdevc->color1, | |
97 | dev = pgs->device->info, | |
98 | fill_rect = dev->procs->fill_rectangle; | |
99 | #define fill_trap_rect(x,y,w,h)\ | |
100 | (fill_direct ?\ | |
101 | (swap_axes ? (*fill_rect)(dev, y, x, h, w, cindex) :\ | |
102 | (*fill_rect)(dev, x, y, w, h, cindex)) :\ | |
103 | swap_axes ? gz_fill_rectangle(y, x, h, w, pdevc, pgs) :\ | |
104 | gz_fill_rectangle(x, y, w, h, pdevc, pgs)) | |
105 | ||
106 | /* Compute the dx/dy ratios. */ | |
107 | /* dx# = dx#i + (dx#f / fh). */ | |
108 | #define compute_dx(tl, d)\ | |
109 | if ( d >= 0 )\ | |
110 | { if ( d < fh ) tl.di = 0, tl.df = d;\ | |
111 | else tl.di = (int)(d / fh), tl.df = d - tl.di * fh, tl.x += yline * tl.di;\ | |
112 | }\ | |
113 | else\ | |
114 | { if ( (tl.df = d + fh) >= 0 /* d >= -fh */ ) tl.di = -1, tl.x -= yline;\ | |
115 | else tl.di = (int)-((fh - 1 - d) / fh), tl.df = d - tl.di * fh, tl.x += yline * tl.di;\ | |
116 | } | |
117 | ||
118 | /* Compute the x offsets at the first scan line to sample. */ | |
119 | /* We need to be careful in computing yline * dx#f {/,%} fh */ | |
120 | /* because the multiplication may overflow. We know that */ | |
121 | /* all the quantities involved are non-negative, and that */ | |
122 | /* yline is less than 1 (as a fixed, of course); this gives us */ | |
123 | /* a cheap conservative check for overflow in the multiplication. */ | |
124 | #define ymult_limit (max_fixed / fixed_1) | |
125 | #define ymult_quo(yl, dxxf)\ | |
126 | (dxxf < ymult_limit ? yl * dxxf / fh : fixed_mult_quo(yl, dxxf, fh)) | |
127 | #define ymult_rem(yl, dxxf)\ | |
128 | (dxxf < ymult_limit ? yl * dxxf % fh : fixed_mult_rem(yl, dxxf, fh)) | |
129 | ||
130 | /* It's worth checking for dxl == dxr, since this is the case */ | |
131 | /* for parallelograms (including stroked lines). */ | |
132 | compute_dx(l, dxl); | |
133 | if ( dxr == dxl ) | |
134 | { fixed fx = ymult_quo(yline, l.df); | |
135 | l.x += fx; | |
136 | if ( l.di == 0 ) | |
137 | r.di = 0, r.df = l.df; | |
138 | else /* too hard to do adjustments right */ | |
139 | compute_dx(r, dxr); | |
140 | r.x += fx; | |
141 | } | |
142 | else | |
143 | { l.x += ymult_quo(yline, l.df); | |
144 | compute_dx(r, dxr); | |
145 | r.x += ymult_quo(yline, r.df); | |
146 | } | |
147 | rxl = fixed2int_var(l.x); | |
148 | rxr = fixed2int_var(r.x); | |
149 | ry = iy; | |
150 | ||
151 | /* Compute one line's worth of dx/dy. */ | |
152 | /* dx# * fixed_1 = ld#i + (ld#f / fh). */ | |
153 | /* We don't have to bother with this if */ | |
154 | /* we're only sampling a single scan line. */ | |
155 | if ( iy1 - iy == 1 ) | |
156 | { iy++; | |
157 | goto last; | |
158 | } | |
159 | #define compute_ldx(tl)\ | |
160 | if ( tl.df < ymult_limit )\ | |
161 | tl.ldi = int2fixed(tl.di) + int2fixed(tl.df) / fh,\ | |
162 | tl.ldf = int2fixed(tl.df) % fh,\ | |
163 | tl.xf = yline * tl.df % fh - fh;\ | |
164 | else\ | |
165 | tl.ldi = int2fixed(tl.di) + fixed_mult_quo(fixed_1, tl.df, fh),\ | |
166 | tl.ldf = fixed_mult_rem(fixed_1, tl.df, fh),\ | |
167 | tl.xf = fixed_mult_rem(yline, tl.df, fh) - fh | |
168 | compute_ldx(l); | |
169 | if ( dxr == dxl ) | |
170 | r.ldi = l.ldi, r.ldf = l.ldf, r.xf = l.xf; | |
171 | else | |
172 | { compute_ldx(r); | |
173 | } | |
174 | #undef compute_ldx | |
175 | ||
176 | while ( ++iy != iy1 ) | |
177 | { int ixl, ixr; | |
178 | #define step_line(tl)\ | |
179 | tl.x += tl.ldi;\ | |
180 | if ( (tl.xf += tl.ldf) >= 0 ) tl.xf -= fh, tl.x++; | |
181 | step_line(l); | |
182 | step_line(r); | |
183 | #undef step_line | |
184 | ixl = fixed2int_var(l.x); | |
185 | ixr = fixed2int_var(r.x); | |
186 | if ( ixl != rxl || ixr != rxr ) | |
187 | { code = fill_trap_rect(rxl, ry, rxr - rxl, iy - ry); | |
188 | if ( code < 0 ) goto xit; | |
189 | rxl = ixl, rxr = ixr, ry = iy; | |
190 | } | |
191 | } | |
192 | last: code = fill_trap_rect(rxl, ry, rxr - rxl, iy - ry); | |
193 | xit: if ( code < 0 && fill_direct ) return_error(code); | |
194 | return code; | |
195 | } | |
196 | } | |
197 | ||
198 | /* Fill a parallelogram whose points are p, p+a, p+b, and p+a+b. */ | |
199 | /* We should swap axes to get best accuracy, but we don't. */ | |
200 | int | |
201 | gz_fill_pgram_fixed(fixed px, fixed py, fixed ax, fixed ay, | |
202 | fixed bx, fixed by, gx_device_color *pdevc, gs_state *pgs) | |
203 | { fixed t; | |
204 | fixed qx, dx, wx, pax, qax; | |
205 | int code; | |
206 | #define swap(r, s) (t = r, r = s, s = t) | |
207 | /* Reorder the points so that 0 <= ay <= by. */ | |
208 | if ( ay < 0 ) px += ax, py += ay, ax = -ax, ay = -ay; | |
209 | if ( by < 0 ) px += bx, py += by, bx = -bx, by = -by; | |
210 | if ( ay > by ) swap(ax, bx), swap(ay, by); | |
211 | if ( by == 0 ) return 0; /* degenerate (line) */ | |
212 | qx = px + ax + bx; | |
213 | /* Compute the distance from p to the point on the line (p, p+b) */ | |
214 | /* whose Y coordinate is equal to ay. */ | |
215 | dx = (fixed)((double)bx * ay / by); | |
216 | if ( dx < ax ) pax = px + dx, qax = qx - ax, wx = ax - dx; | |
217 | else pax = px + ax, qax = qx - dx, wx = dx - ax; | |
218 | if ( ay >= fixed_1 || | |
219 | fixed_rounded(py) != fixed_rounded(py + ay) | |
220 | ) | |
221 | { code = gz_fill_trapezoid_fixed(px, fixed_0, py, pax, wx, ay, | |
222 | 0, pdevc, pgs); | |
223 | if ( code < 0 ) return code; | |
224 | } | |
225 | code = gz_fill_trapezoid_fixed(pax, wx, py + ay, qax, wx, by - ay, | |
226 | 0, pdevc, pgs); | |
227 | if ( code < 0 ) return code; | |
228 | py += by; | |
229 | if ( ay >= fixed_1 || | |
230 | fixed_rounded(py) != fixed_rounded(py + ay) | |
231 | ) | |
232 | return gz_fill_trapezoid_fixed(qax, wx, py, qx, fixed_0, ay, | |
233 | 0, pdevc, pgs); | |
234 | #undef swap | |
235 | return 0; | |
236 | } | |
237 | ||
238 | /* Default implementation of tile_rectangle */ | |
239 | int | |
240 | gx_default_tile_rectangle(gx_device *dev, register gx_bitmap *tile, | |
241 | int x, int y, int w, int h, gx_color_index color0, gx_color_index color1, | |
242 | int px, int py) | |
243 | { /* Fill the rectangle in chunks */ | |
244 | int width = tile->size.x; | |
245 | int height = tile->size.y; | |
246 | int raster = tile->raster; | |
247 | int rwidth = tile->rep_width; | |
248 | int irx = ((rwidth & (rwidth - 1)) == 0 ? /* power of 2 */ | |
249 | (x + px) & (rwidth - 1) : | |
250 | (x + px) % rwidth); | |
251 | int ry = (y + py) % tile->rep_height; | |
252 | int icw = width - irx; | |
253 | int ch = height - ry; | |
254 | byte *row = tile->data + ry * raster; | |
255 | #define d_proc_mono (dev->procs->copy_mono) | |
256 | dev_proc_copy_mono((*proc_mono)); | |
257 | #define d_proc_color (dev->procs->copy_color) | |
258 | dev_proc_copy_color((*proc_color)); | |
259 | #define d_color_halftone\ | |
260 | (color0 == gx_no_color_index && color1 == gx_no_color_index) | |
261 | int color_halftone; | |
262 | #define get_color_info()\ | |
263 | if ( (color_halftone = d_color_halftone) ) proc_color = d_proc_color;\ | |
264 | else proc_mono = d_proc_mono | |
265 | int code; | |
266 | #ifdef DEBUG | |
267 | if ( gs_debug['t'] ) | |
268 | { int ptx, pty; | |
269 | byte *ptp = tile->data; | |
270 | dprintf3("[t]tile %dx%d raster=%d;", | |
271 | tile->size.x, tile->size.y, tile->raster); | |
272 | dprintf6(" x,y=%d,%d w,h=%d,%d p=%d,%d\n", | |
273 | x, y, w, h, px, py); | |
274 | for ( pty = 0; pty < tile->size.y; pty++ ) | |
275 | { dprintf(" "); | |
276 | for ( ptx = 0; ptx < tile->raster; ptx++ ) | |
277 | dprintf1("%3x", *ptp++); | |
278 | } | |
279 | dputc('\n'); | |
280 | } | |
281 | #endif | |
282 | #define real_copy_tile(srcx, tx, ty, tw, th)\ | |
283 | code =\ | |
284 | (color_halftone ?\ | |
285 | (*proc_color)(dev, row, srcx, raster, gx_no_bitmap_id, tx, ty, tw, th) :\ | |
286 | (*proc_mono)(dev, row, srcx, raster, gx_no_bitmap_id, tx, ty, tw, th, color0, color1));\ | |
287 | if ( code < 0 ) return_error(code) | |
288 | #ifdef DEBUG | |
289 | #define copy_tile(sx, tx, ty, tw, th)\ | |
290 | if ( gs_debug['t'] )\ | |
291 | dprintf5(" copy sx=%d x=%d y=%d w=%d h=%d\n",\ | |
292 | sx, tx, ty, tw, th);\ | |
293 | real_copy_tile(sx, tx, ty, tw, th) | |
294 | #else | |
295 | #define copy_tile(sx, tx, ty, tw, th)\ | |
296 | real_copy_tile(sx, tx, ty, tw, th) | |
297 | #endif | |
298 | if ( icw >= w ) | |
299 | { /* Narrow operation */ | |
300 | int ey, fey, cy; | |
301 | if ( ch >= h ) | |
302 | { /* Just one (partial) tile to transfer. */ | |
303 | #define color_halftone d_color_halftone | |
304 | #define proc_color d_proc_color | |
305 | #define proc_mono d_proc_mono | |
306 | copy_tile(irx, x, y, w, h); | |
307 | #undef proc_mono | |
308 | #undef proc_color | |
309 | #undef color_halftone | |
310 | return 0; | |
311 | } | |
312 | get_color_info(); | |
313 | ey = y + h; | |
314 | fey = ey - height; | |
315 | copy_tile(irx, x, y, w, ch); | |
316 | cy = y + ch; | |
317 | row = tile->data; | |
318 | do | |
319 | { ch = (cy > fey ? ey - cy : height); | |
320 | copy_tile(irx, x, cy, w, ch); | |
321 | } | |
322 | while ( (cy += ch) < ey ); | |
323 | return 0; | |
324 | } | |
325 | get_color_info(); | |
326 | if ( ch >= h ) | |
327 | { /* Shallow operation */ | |
328 | int ex = x + w; | |
329 | int fex = ex - width; | |
330 | int cx = x + icw; | |
331 | copy_tile(irx, x, y, icw, h); | |
332 | while ( cx <= fex ) | |
333 | { copy_tile(0, cx, y, width, h); | |
334 | cx += width; | |
335 | } | |
336 | if ( cx < ex ) | |
337 | { copy_tile(0, cx, y, ex - cx, h); | |
338 | } | |
339 | } | |
340 | else | |
341 | { /* Full operation */ | |
342 | int ex = x + w, ey = y + h; | |
343 | int fex = ex - width, fey = ey - height; | |
344 | int cx, cy; | |
345 | for ( cy = y; ; ) | |
346 | { copy_tile(irx, x, cy, icw, ch); | |
347 | cx = x + icw; | |
348 | while ( cx <= fex ) | |
349 | { copy_tile(0, cx, cy, width, ch); | |
350 | cx += width; | |
351 | } | |
352 | if ( cx < ex ) | |
353 | { copy_tile(0, cx, cy, ex - cx, ch); | |
354 | } | |
355 | if ( (cy += ch) >= ey ) break; | |
356 | ch = (cy > fey ? ey - cy : height); | |
357 | row = tile->data; | |
358 | } | |
359 | } | |
360 | #undef copy_tile | |
361 | #undef real_copy_tile | |
362 | return 0; | |
363 | } | |
364 | ||
365 | /* Draw a one-pixel-wide line. */ | |
366 | int | |
367 | gz_draw_line_fixed(fixed ixf, fixed iyf, fixed itoxf, fixed itoyf, | |
368 | gx_device_color *pdevc, gs_state *pgs) | |
369 | { int ix = fixed2int_var(ixf); | |
370 | int iy = fixed2int_var(iyf); | |
371 | int itox = fixed2int_var(itoxf); | |
372 | int itoy = fixed2int_var(itoyf); | |
373 | gx_device *dev; | |
374 | if ( itoy == iy ) /* horizontal line */ | |
375 | { return (ix <= itox ? | |
376 | gz_fill_rectangle(ix, iy, itox - ix + 1, 1, pdevc, pgs) : | |
377 | gz_fill_rectangle(itox, iy, ix - itox + 1, 1, pdevc, pgs) | |
378 | ); | |
379 | } | |
380 | if ( itox == ix ) /* vertical line */ | |
381 | { return (iy <= itoy ? | |
382 | gz_fill_rectangle(ix, iy, 1, itoy - iy + 1, pdevc, pgs) : | |
383 | gz_fill_rectangle(ix, itoy, 1, iy - itoy + 1, pdevc, pgs) | |
384 | ); | |
385 | } | |
386 | if ( color_is_pure(pdevc) && | |
387 | (dev = pgs->device->info, | |
388 | (*dev->procs->draw_line)(dev, ix, iy, itox, itoy, | |
389 | pdevc->color1)) >= 0 ) | |
390 | return 0; | |
391 | { fixed h = itoyf - iyf; | |
392 | fixed w = itoxf - ixf; | |
393 | fixed tf; | |
394 | #define fswap(a, b) tf = a, a = b, b = tf | |
395 | #define half float2fixed(0.5) | |
396 | if ( (w < 0 ? -w : w) <= (h < 0 ? -h : h) ) | |
397 | { if ( h < 0 ) | |
398 | fswap(ixf, itoxf), fswap(iyf, itoyf), | |
399 | h = -h; | |
400 | return gz_fill_trapezoid_fixed(ixf - half, fixed_1, iyf, | |
401 | itoxf - half, fixed_1, h, | |
402 | 0, pdevc, pgs); | |
403 | } | |
404 | else | |
405 | { if ( w < 0 ) | |
406 | fswap(ixf, itoxf), fswap(iyf, itoyf), | |
407 | w = -w; | |
408 | return gz_fill_trapezoid_fixed(iyf - half, fixed_1, ixf, | |
409 | itoyf - half, fixed_1, w, | |
410 | 1, pdevc, pgs); | |
411 | } | |
412 | #undef half | |
413 | #undef fswap | |
414 | } | |
415 | } | |
416 | ||
417 | /* A stub to force use of the standard procedure. */ | |
418 | int | |
419 | gx_default_draw_line(gx_device *dev, | |
420 | int x0, int y0, int x1, int y1, gx_color_index color) | |
421 | { return -1; | |
422 | } |