lib/pdf: make startPage() upstream compatible
[swftools.git] / lib / gfxtools.c
1 /* gfxtools.c
2
3    Various utility functions for dealing with gfxdevices.
4
5    Part of the swftools package.
6
7    Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
8
9    This program is free software; you can redistribute it and/or modify
10    it under the terms of the GNU General Public License as published by
11    the Free Software Foundation; either version 2 of the License, or
12    (at your option) any later version.
13
14    This program is distributed in the hope that it will be useful,
15    but WITHOUT ANY WARRANTY; without even the implied warranty of
16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17    GNU General Public License for more details.
18
19    You should have received a copy of the GNU General Public License
20    along with this program; if not, write to the Free Software
21    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
22
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <memory.h>
26 #include <math.h>
27 #include <string.h>
28 #include <assert.h>
29 #include "gfxtools.h"
30 #include "gfxfont.h"
31 #include "jpeg.h"
32 #include "q.h"
33
34 typedef struct _linedraw_internal
35 {
36     gfxline_t*start;
37     gfxline_t*next;
38     gfxcoord_t x0,y0;
39     char has_moveto;
40 } linedraw_internal_t;
41
42 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
43 {
44     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
45     gfxline_t*l = (gfxline_t*)rfx_alloc(sizeof(gfxline_t));
46     l->type = gfx_moveTo;
47     i->has_moveto = 1;
48     i->x0 = x;
49     i->y0 = y;
50     l->sx = l->sy = 0;
51     d->x = l->x = x;
52     d->y = l->y = y;
53     l->next = 0;
54     if(i->next)
55         i->next->next = l;
56     i->next = l;
57     if(!i->start)
58         i->start = l;
59 }
60 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
61 {
62     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
63     if(!i->has_moveto) {
64         /* starts with a line, not with a moveto. As this is the first
65            entry in the list, this is probably *meant* to be a moveto */
66         linedraw_moveTo(d, x, y);
67         return;
68     }
69     
70     gfxline_t*l = (gfxline_t*)rfx_alloc(sizeof(gfxline_t));
71     l->type = gfx_lineTo;
72     d->x = l->x = x;
73     d->y = l->y = y;
74
75     l->next = 0;
76     if(i->next)
77         i->next->next = l;
78     i->next = l;
79     if(!i->start)
80         i->start = l;
81 }
82 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
83 {
84     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
85     if(!i->has_moveto) {
86         linedraw_moveTo(d, x, y);
87         return;
88     }
89
90     gfxline_t*l = (gfxline_t*)rfx_alloc(sizeof(gfxline_t));
91     l->type = gfx_splineTo;
92     d->x = l->x = x;
93     d->y = l->y = y;
94     l->sx = sx;
95     l->sy = sy;
96     l->next = 0;
97     if(i->next)
98         i->next->next = l;
99     i->next = l;
100     if(!i->start)
101         i->start = l;
102 }
103 static void linedraw_close(gfxdrawer_t*d)
104 {
105     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
106     if(!i->has_moveto) 
107         return;
108     linedraw_lineTo(d, i->x0, i->y0);
109     i->has_moveto = 0;
110     i->x0 = 0;
111     i->y0 = 0;
112 }
113 static void* linedraw_result(gfxdrawer_t*d)
114 {
115     linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
116     void*result = (void*)i->start;
117     rfx_free(i);
118     memset(d, 0, sizeof(gfxdrawer_t));
119     return result;
120 }
121
122 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
123 {
124     linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
125     d->x = 0x7fffffff;
126     d->y = 0x7fffffff;
127     d->internal = i;
128     d->moveTo = linedraw_moveTo;
129     d->lineTo = linedraw_lineTo;
130     d->splineTo = linedraw_splineTo;
131     d->close = linedraw_close;
132     d->result = linedraw_result;
133 }
134
135 typedef struct _qspline_abc
136 {
137     double ax,bx,cx;
138     double ay,by,cy;
139 } qspline_abc_t;
140
141 typedef struct qspline_t
142 {
143     gfxpoint_t start;
144     gfxpoint_t control;
145     gfxpoint_t end;
146 } qspline_t;
147
148 typedef struct cspline_t
149 {
150     gfxpoint_t start;
151     gfxpoint_t control1;
152     gfxpoint_t control2;
153     gfxpoint_t end;
154 } cspline_t;
155
156 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
157 {
158     /*
159        Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
160        Form 2: x = a*t*t + b*t + c
161     */
162     s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
163     s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
164 }
165
166 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
167 {
168     double dt = t2-t1;
169     double nax = q->ax*dt*dt;
170     double nay = q->ay*dt*dt;
171     double nbx = 2*q->ax*dt*t1 + q->bx*dt;
172     double nby = 2*q->ay*dt*t1 + q->by*dt;
173     double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
174     double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
175     *dx = ncx + nbx/2;
176     *dy = ncy + nby/2;
177 }
178
179 static double get_spline_len(qspline_abc_t*s)
180 {
181     int parts = (int)(sqrt(fabs(s->ax) + fabs(s->ay))*3);
182     int i;
183     double len = 0;
184     double r;
185     double r2;
186     if(parts < 3) parts = 3;
187     r = 1.0/parts;
188     r2 = 1.0/(parts*parts);
189     for(i=0;i<parts;i++)
190     {
191         double dx = s->ax*(2*i+1)*r2 + s->bx*r;
192         double dy = s->ay*(2*i+1)*r2 + s->by*r;
193         len += sqrt(dx*dx+dy*dy);
194     }
195     /*printf("Spline from %f,%f to %f,%f has len %f (%f)\n", s->cx, s->cy,
196             s->cx + s->bx + s->ax,
197             s->cy + s->by + s->ay, len,
198             sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay))
199             );
200     assert(len+0.5 >= sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay)));
201      */
202     return len;
203 }
204
205 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r, float phase)
206 {
207     double x=0,y=0;
208     double linepos,nextpos;
209     char on;
210     int apos=0;
211
212     if(line && line->type != gfx_moveTo) {
213         fprintf(stderr, "gfxtool: outline doesn't start with a moveTo");
214         return;
215     }
216     
217     int i;
218     double dashlen=0;
219     for(i=0;r[i]>=0;i++) {
220         dashlen+=r[i];
221     }
222     if(!r || (r[0]<=0 && r[0]>-0.01) || dashlen<0.001) {
223         // no dashing. just draw the thing
224         while(line) {
225             if(line->type == gfx_moveTo) {
226                 d->moveTo(d, line->x, line->y);
227             } else if(line->type == gfx_lineTo) {
228                 d->lineTo(d, line->x, line->y);
229             } else if(line->type == gfx_splineTo) {
230                 d->splineTo(d, line->sx, line->sy, line->x, line->y);
231             }
232             line = line->next;
233         }
234         return;
235     }
236     if(r[0]<0 || phase<0) {
237         fprintf(stderr, "gfxtool: invalid (negative) dashes: %f, phase=%f\n", r[0], phase);
238         return;
239     }
240
241     for(;line;line=line->next) {
242         if(line->type == gfx_moveTo) {
243             d->moveTo(d, line->x, line->y);
244             on = 1; nextpos = r[0]; apos = 0; linepos = 0;
245             x = line->x; y = line->y;
246             while(linepos < phase) {
247                 //printf("[+] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f\n", linepos, phase, on, apos, nextpos);
248                 linepos += r[apos];
249                 if(linepos < phase) {
250                     on ^= 1;
251                     if(r[++apos]<0)
252                         apos = 0;
253                     nextpos += r[apos];
254                 }
255             }
256             linepos = phase;
257             //printf("[k] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f \n", linepos, phase, on, apos, nextpos);
258         } else if(line->type == gfx_lineTo) {
259             double dx = line->x - x;
260             double dy = line->y - y;
261             double len = sqrt(dx*dx+dy*dy);
262             double vx;
263             double vy;
264             double lineend = linepos+len;
265             if(len==0)
266                 continue;
267             vx = dx/len;
268             vy = dy/len;
269             assert(nextpos>=linepos);
270             //printf("(line) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
271             while(nextpos<lineend) {
272                 double nx = x + vx*(nextpos-linepos);
273                 double ny = y + vy*(nextpos-linepos);
274                 if(on) {d->lineTo(d, nx,ny);/*printf("lineTo %f\n", nextpos);*/}
275                 else   {d->moveTo(d, nx,ny);/*printf("moveTo %f\n", nextpos);*/}
276                 on^=1;
277                 if(r[++apos]<0)
278                     apos = 0;
279                 nextpos+=r[apos];
280             }
281             linepos = lineend;
282             if(on) {
283                 //printf("lineTo %f\n", 1.0);
284                 d->lineTo(d, line->x,line->y);
285             }
286             x = line->x; y = line->y;
287         } else if(line->type == gfx_splineTo) {
288             qspline_abc_t q;
289             double len, lineend,lastt;
290             mkspline(&q, x, y, line);
291
292             len = get_spline_len(&q);
293             //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
294             if(len==0)
295                 continue;
296             lineend = linepos+len;
297             lastt = 0;
298             if(nextpos<linepos)
299                 printf("%f !< %f\n", nextpos, linepos);
300             assert(nextpos>=linepos);
301             //printf("(spline) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
302             while(nextpos<lineend) {
303                 double t = (nextpos-linepos)/len;
304                 //printf("%f (%f-%f) apos=%d r[apos]=%f\n", t, nextpos, linepos, apos, r[apos]);
305                 double nx = q.ax*t*t+q.bx*t+q.cx;
306                 double ny = q.ay*t*t+q.by*t+q.cy;
307                 if(on) {
308                     double sx,sy;
309                     spline_get_controlpoint(&q, lastt, t, &sx, &sy);
310                     d->splineTo(d, sx, sy, nx,ny);
311                     //printf("splineTo %f\n", nextpos);
312                 } else  {
313                     d->moveTo(d, nx,ny);
314                     //printf("moveTo %f\n", nextpos);
315                 }
316                 lastt =  t;
317                 on^=1;
318                 if(r[++apos]<0)
319                     apos = 0;
320                 nextpos+=r[apos];
321             }
322             linepos = lineend;
323             if(on) {
324                 double sx,sy;
325                 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
326                 d->splineTo(d, sx, sy, line->x,line->y);
327                 //printf("splineTo %f\n", 1.0);
328             }
329             x = line->x; y = line->y;
330         }
331     }
332 }
333
334 gfxline_t * gfxline_clone(gfxline_t*line)
335 {
336     gfxline_t*dest = 0;
337     gfxline_t*pos = 0;
338     while(line) {
339         gfxline_t*n = (gfxline_t*)rfx_calloc(sizeof(gfxline_t));
340         *n = *line;
341         n->next = 0;
342         if(!pos) {
343             dest = pos = n;
344         } else {
345             pos->next = n;
346             pos = n;
347         }
348         line = line->next;
349     }
350     return dest;
351 }
352
353 static char splineIsStraight(double x, double y, gfxline_t*l)
354 {
355     if(l->type == gfx_moveTo)
356         return 0;
357     if(l->type == gfx_lineTo)
358         return 1;
359     double dx = l->x-x;
360     double dy = l->y-y;
361     double sx = l->sx-x;
362     double sy = l->sy-y;
363     if(fabs(dx*sy - dy*sx) < 0.000001 && (dx*sx + dy*sy) >= 0) {
364         return 1;
365     }
366     return 0;
367 }
368
369 void gfxline_optimize(gfxline_t*line)
370 {
371     gfxline_t*l = line;
372     /* step 1: convert splines to lines, where possible */
373     double x=0,y=0;
374     while(l) {
375         if(l->type == gfx_splineTo && splineIsStraight(x,y,l)) {
376             l->type = gfx_lineTo;
377         }
378         x = l->x;
379         y = l->y;
380         l = l->next;
381     }
382     /* step 2: combine adjacent lines and splines, where possible */
383     l = line;
384     while(l && l->next) {
385         gfxline_t*next = l->next;
386         char combine = 0;
387         double sx=0,sy=0;
388         if(l->type == gfx_lineTo && next->type == gfx_lineTo) {
389             double dx = l->x-x;
390             double dy = l->y-y;
391             double nx = next->x-l->x;
392             double ny = next->y-l->y;
393             if(fabs(dx*ny - dy*nx) < 0.000001 && (dx*nx + dy*ny) >= 0) {
394                 combine = 1;
395             }
396         } else if(l->type == gfx_splineTo && next->type == gfx_splineTo) {
397             /* TODO */
398         }
399         if(combine) {
400             l->next = next->next;
401             next->next = 0;
402             l->x = next->x;
403             l->y = next->y;
404             l->sx = sx;
405             l->sy = sy;
406             rfx_free(next);
407         } else {
408             x = l->x;
409             y = l->y;
410             l = l->next;
411         }
412     }
413 }
414
415 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes, float phase)
416 {
417     gfxdrawer_t d;
418     gfxline_t*result;
419     gfxdrawer_target_gfxline(&d);
420     gfxtool_draw_dashed_line(&d, line, dashes, phase);
421     result= (gfxline_t*)d.result(&d);
422     return result;
423 }
424
425 void gfxline_show(gfxline_t*l, FILE*fi)
426 {
427     while(l) {
428         if(l->type == gfx_moveTo) {
429             fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
430         }
431         if(l->type == gfx_lineTo) {
432             fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
433         }
434         if(l->type == gfx_splineTo) {
435             fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
436         }
437         l = l->next;
438     }
439 }
440
441 void gfxline_free(gfxline_t*l)
442 {
443     if(l && (l+1) == l->next) {
444         /* flattened */
445         rfx_free(l);
446     } else {
447         gfxline_t*next;
448         while(l) {
449             next = l->next;
450             l->next = 0;
451             rfx_free(l);
452             l = next;
453         }
454     }
455 }
456
457 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
458 {
459     gfxpoint_t p;
460     double tt = t*t;
461     double ttt = tt*t;
462     double mt = (1-t);
463     double mtmt = mt*(1-t);
464     double mtmtmt = mtmt*(1-t);
465     p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
466             + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
467     p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
468             + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
469     return p;
470 }
471 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
472 {
473     gfxpoint_t p;
474     p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
475     p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
476     return p;
477 }
478
479 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
480 {
481     unsigned int gran = 0;
482     unsigned int istep = 0x80000000;
483     unsigned int istart = 0;
484     int num = 0;
485     int level = 0;
486
487     while(istart<0x80000000)
488     {
489         unsigned int iend = istart + istep;
490         double start = istart/(double)0x80000000;
491         double end = iend/(double)0x80000000;
492         qspline_t test;
493         double pos,qpos;
494         char left = 0,recurse=0;
495         int t;
496         int probes = 15;
497         double dx,dy;
498
499         /* create simple approximation: a qspline_t which run's through the
500            qspline_t point at 0.5 */
501         test.start = cspline_getpoint(s, start);
502         test.control = cspline_getpoint(s, (start+end)/2);
503         test.end = cspline_getpoint(s, end);
504         /* fix the control point:
505            move it so that the new spline does runs through it */
506         test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
507         test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
508
509         /* depending on where we are in the spline, we either try to match
510            the left or right tangent */
511         if(start<0.5)
512             left=1;
513         /* get derivative */
514         pos = left?start:end;
515         qpos = pos*pos;
516         test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
517                     3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
518         test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
519                     3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
520         if(left) {
521             test.control.x *= (end-start)/2;
522             test.control.y *= (end-start)/2;
523             test.control.x += test.start.x;
524             test.control.y += test.start.y;
525         } else {
526             test.control.x *= -(end-start)/2;
527             test.control.y *= -(end-start)/2;
528             test.control.x += test.end.x;
529             test.control.y += test.end.y;
530         }
531
532 //#define PROBES
533 #ifdef PROBES
534         /* measure the spline's accurancy, by taking a number of probes */
535         for(t=0;t<probes;t++) {
536             gfxpoint_t qr1,qr2,cr1,cr2;
537             double pos = 0.5/(probes*2)*(t*2+1);
538             double dx,dy;
539             double dist1,dist2;
540             qr1 = qspline_getpoint(&test, pos);
541             cr1 = cspline_getpoint(s, start+pos*(end-start));
542
543             dx = qr1.x - cr1.x;
544             dy = qr1.y - cr1.y;
545             dist1 = dx*dx+dy*dy;
546
547             if(dist1>quality2) {
548                 recurse=1;break;
549             }
550             qr2 = qspline_getpoint(&test, (1-pos));
551             cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
552
553             dx = qr2.x - cr2.x;
554             dy = qr2.y - cr2.y;
555             dist2 = dx*dx+dy*dy;
556
557             if(dist2>quality2) {
558                 recurse=1;break;
559             }
560         }
561 #else // quadratic error: *much* faster!
562
563         /* convert control point representation to
564            d*x^3 + c*x^2 + b*x + a */
565         dx= s->end.x  - s->control2.x*3 + s->control1.x*3 - s->start.x;
566         dy= s->end.y  - s->control2.y*3 + s->control1.y*3 - s->start.y;
567
568         /* we need to do this for the subspline between [start,end], not [0,1]
569            as a transformation of t->a*t+b does nothing to highest coefficient
570            of the spline except multiply it with a^3, we just need to modify
571            d here. */
572         {double m = end-start;
573          dx*=m*m*m;
574          dy*=m*m*m;
575         }
576
577         /* use the integral over (f(x)-g(x))^2 between 0 and 1
578            to measure the approximation quality.
579            (it boils down to const*d^2) */
580         recurse = (dx*dx + dy*dy > quality2);
581 #endif
582
583         if(recurse && istep>1 && size-level > num) {
584             istep >>= 1;
585             level++;
586         } else {
587             *q++ = test;
588             num++;
589             istart += istep;
590             while(!(istart & istep)) {
591                 level--;
592                 istep <<= 1;
593             }
594         }
595     }
596     return num;
597 }
598
599 void gfxdraw_conicTo(gfxdrawer_t*draw, double cx, double cy, double tox, double toy, double quality)
600 {
601     double c1x = (draw->x + 2 * cx) / 3;
602     double c1y = (draw->y + 2 * cy) / 3;
603     double c2x = (2 * cx + tox) / 3;
604     double c2y = (2 * cy + toy) / 3;
605     gfxdraw_cubicTo(draw, c1x, c1y, c2x, c2y, tox, toy, quality);
606 }
607
608
609 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y, double quality)
610 {
611     qspline_t q[128];
612     cspline_t c;
613     double maxerror = quality>0 ? quality : 1.0;
614     int t,num;
615
616     c.start.x = draw->x;
617     c.start.y = draw->y;
618     c.control1.x = c1x;
619     c.control1.y = c1y;
620     c.control2.x = c2x;
621     c.control2.y = c2y;
622     c.end.x = x;
623     c.end.y = y;
624
625     num = approximate3(&c, q, 128, maxerror);
626
627     for(t=0;t<num;t++) {
628         gfxpoint_t mid;
629         gfxpoint_t to;
630         mid.x = q[t].control.x;
631         mid.y = q[t].control.y;
632         to.x = q[t].end.x;
633         to.y = q[t].end.y;
634         draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
635     }
636 }
637
638 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
639 {
640     if(box.xmin==0 && box.ymin==0 && box.xmax==0 && box.ymax==0) {
641         box.xmin = x;
642         box.ymin = y;
643         box.xmax = x;
644         box.ymax = y;
645         if(x==0 && y==0) box.xmax = 0.0000001;
646         return box;
647     }
648     if(x < box.xmin)
649         box.xmin = x;
650     if(x > box.xmax)
651         box.xmax = x;
652     if(y < box.ymin)
653         box.ymin = y;
654     if(y > box.ymax)
655         box.ymax = y;
656     return box;
657 }
658
659 gfxbbox_t gfxbbox_expand_to_bbox(gfxbbox_t box, gfxbbox_t box2)
660 {
661     box = gfxbbox_expand_to_point(box, box2.xmin, box2.ymin);
662     box = gfxbbox_expand_to_point(box, box2.xmax, box2.ymax);
663     return box;
664 }
665
666 void gfxbbox_intersect(gfxbbox_t*box1, gfxbbox_t*box2)
667 {
668     if(box2->xmin > box1->xmin)
669         box1->xmin = box2->xmin;
670     if(box2->ymin > box1->ymin)
671         box1->ymin = box2->ymin;
672     if(box2->xmax < box1->xmax)
673         box1->xmax = box2->xmax;
674     if(box2->ymax > box1->ymax)
675         box1->ymax = box2->ymax;
676     if(box1->xmin > box1->xmax)
677         box1->xmax = box1->xmin;
678     if(box1->ymin > box1->ymax)
679         box1->ymax = box1->ymin;
680 }
681
682 gfxbbox_t gfxline_getbbox(gfxline_t*line)
683 {
684     gfxcoord_t x=0,y=0;
685     gfxbbox_t bbox = {0,0,0,0};
686     char last = 0;
687     while(line) {
688         if(line->type == gfx_moveTo) {
689             last = 1;
690         } else if(line->type == gfx_lineTo) {
691             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
692             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
693             last = 0;
694         } else if(line->type == gfx_splineTo) {
695             if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
696             bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
697             bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
698             last = 0;
699         }
700         x = line->x;
701         y = line->y;
702         line = line->next;
703     }
704     return bbox;
705 }
706
707 gfxline_t* gfxline_append(gfxline_t*line1, gfxline_t*line2)
708 {
709     gfxline_t*l = line1;;
710     if(!l)
711         return line2;
712     while(l->next) {
713         l = l->next;
714     }
715     l->next = line2;
716     return line1;
717 }
718
719 void gfxline_transform(gfxline_t*line, gfxmatrix_t*matrix)
720 {
721     while(line) {
722         double x = matrix->m00*line->x + matrix->m10*line->y + matrix->tx;
723         double y = matrix->m01*line->x + matrix->m11*line->y + matrix->ty;
724         line->x = x;
725         line->y = y;
726         if(line->type == gfx_splineTo) {
727             double sx = matrix->m00*line->sx + matrix->m10*line->sy + matrix->tx;
728             double sy = matrix->m01*line->sx + matrix->m11*line->sy + matrix->ty;
729             line->sx = sx;
730             line->sy = sy;
731         }
732         line = line->next;
733     }
734 }
735
736 void gfxmatrix_dump(gfxmatrix_t*m, FILE*fi, char*prefix)
737 {
738     fprintf(fi, "%s%f %f | %f\n", prefix, m->m00, m->m10, m->tx);
739     fprintf(fi, "%s%f %f | %f\n", prefix, m->m01, m->m11, m->ty);
740 }
741
742 void gfxmatrix_transform(gfxmatrix_t*m, double* v, double*dest)
743 {
744     dest[0] = m->m00*v[0] + m->m10*v[1] + m->tx;
745     dest[1] = m->m01*v[0] + m->m11*v[1] + m->ty;
746 }
747 void gfxmatrix_invert(gfxmatrix_t*m, gfxmatrix_t*dest)
748 {
749     double det = m->m00 * m->m11 - m->m10 * m->m01;
750     if(!det) {
751         memset(dest, 0, sizeof(gfxmatrix_t));
752         return;
753     }
754     det = 1/det;
755     dest->m00 = m->m11 * det;
756     dest->m01 = -m->m01 * det;
757     dest->m10 = -m->m10 * det;
758     dest->m11 = m->m00 * det;
759     dest->tx = -(dest->m00 * m->tx + dest->m10 * m->ty);
760     dest->ty = -(dest->m01 * m->tx + dest->m11 * m->ty);
761 }
762 void gfxmatrix_unit(gfxmatrix_t*m)
763 {
764     memset(m, 0, sizeof(gfxmatrix_t));
765     m->m00 = 1.0;
766     m->m11 = 1.0;
767 }
768 void gfxmatrix_multiply(gfxmatrix_t*m1, gfxmatrix_t*m2, gfxmatrix_t*dest)
769 {
770     dest->m00 = m1->m00*m2->m00 + m1->m10*m2->m01;
771     dest->m01 = m1->m01*m2->m00 + m1->m11*m2->m01;
772     dest->m10 = m1->m00*m2->m10 + m1->m10*m2->m11;
773     dest->m11 = m1->m01*m2->m10 + m1->m11*m2->m11;
774     dest->tx = m1->m00*m2->tx + m1->m10*m2->ty + m1->tx;
775     dest->ty = m1->m01*m2->tx + m1->m11*m2->ty + m1->ty;
776 }
777
778 gfxfontlist_t* gfxfontlist_create()
779 {
780     /* Initial list ist empty */
781     return 0;
782 }
783
784 gfxfont_t*gfxfontlist_findfont(gfxfontlist_t*list, char*id)
785 {
786     gfxfontlist_t*l = list;
787     while(l) {
788         if(!strcmp((char*)l->font->id, id)) {
789             return l->font;
790         }
791         l = l->next;
792     }
793     return 0;
794 }
795 char gfxfontlist_hasfont(gfxfontlist_t*list, gfxfont_t*font)
796 {
797     gfxfontlist_t*l = list;
798     while(l) {
799         if(!strcmp((char*)l->font->id, font->id)) {
800             return 1;
801         }
802         l = l->next;
803     }
804     return 0;
805 }
806 void*gfxfontlist_getuserdata(gfxfontlist_t*list, const char*id)
807 {
808     gfxfontlist_t*l = list;
809     while(l) {
810         if(!strcmp((char*)l->font->id, id)) {
811             return l->user;
812         }
813         l = l->next;
814     }
815     return 0;
816 }
817 gfxfontlist_t*gfxfontlist_addfont2(gfxfontlist_t*list, gfxfont_t*font, void*user)
818 {
819     gfxfontlist_t*last=0,*l = list;
820     while(l) {
821         last = l;
822         if(l->font == font) {
823             return list; // we already know this font
824         }
825         l = l->next;
826     }
827     if(!font) {
828         fprintf(stderr, "Tried to add zero font\n");
829     }
830     l = (gfxfontlist_t*)rfx_calloc(sizeof(gfxfontlist_t));
831     l->font = font;
832     l->user = user;
833     l->next = 0;
834     if(last) {
835         last->next = l;
836         return list;
837     } else {
838         return l;
839     }
840 }
841 gfxfontlist_t*gfxfontlist_addfont(gfxfontlist_t*list, gfxfont_t*font)
842 {
843     return gfxfontlist_addfont2(list, font, 0);
844 }
845 void gfxfontlist_free(gfxfontlist_t*list, char deletefonts)
846 {
847     gfxfontlist_t*l = list;
848     while(l) {
849         gfxfontlist_t*next = l->next;
850         if(deletefonts && l->font) {
851             gfxfont_free(l->font);l->font=0;
852         }
853         l->next = 0;
854         free(l);
855         l = next;
856     }
857 }
858
859 gfxline_t*gfxline_makerectangle(double x1,double y1,double x2, double y2)
860 {
861     gfxline_t* line = (gfxline_t*)rfx_calloc(sizeof(gfxline_t)*5);
862     line[0].x = x1;line[0].y = y1;line[0].type = gfx_moveTo;line[0].next = &line[1];
863     line[1].x = x2;line[1].y = y1;line[1].type = gfx_lineTo;line[1].next = &line[2];
864     line[2].x = x2;line[2].y = y2;line[2].type = gfx_lineTo;line[2].next = &line[3];
865     line[3].x = x1;line[3].y = y2;line[3].type = gfx_lineTo;line[3].next = &line[4];
866     line[4].x = x1;line[4].y = y1;line[4].type = gfx_lineTo;
867     return line;
868 }
869
870 gfxline_t*gfxline_makecircle(double x,double y,double rx, double ry)
871 {
872     double C1 = 0.2930;    
873     double C2 = 0.4140;   
874     double begin = 0.7070; 
875     gfxline_t** line = (gfxline_t**)rfx_calloc(sizeof(gfxline_t*)*9);
876     int t;
877     for(t=0;t<9;t++) {
878         line[t] = rfx_calloc(sizeof(gfxline_t));
879     }
880     line[0]->type = gfx_moveTo;
881     line[0]->x = x+begin*rx;
882     line[0]->y = y+begin*ry;
883     for(t=1;t<9;t++) {
884         line[t-1]->next = line[t];
885         line[t]->type = gfx_splineTo;
886     }
887     line[8]->next = 0;
888 #define R(nr,cx,cy,mx,my) \
889     line[nr]->sx = line[nr-1]->x + (cx); \
890     line[nr]->sy = line[nr-1]->y + (cy); \
891     line[nr]->x = line[nr]->sx + (mx); \
892     line[nr]->y = line[nr]->sy + (my);
893     R(1, -C1*rx,  C1*ry, -C2*rx,      0);
894     R(2, -C2*rx,      0, -C1*rx, -C1*ry);
895     R(3, -C1*rx, -C1*ry,      0, -C2*ry);
896     R(4,      0, -C2*ry,  C1*rx, -C1*ry);
897     R(5,  C1*rx, -C1*ry,  C2*rx,      0);
898     R(6,  C2*rx,      0,  C1*rx,  C1*ry);
899     R(7,  C1*rx,  C1*ry,      0,  C2*ry);
900     R(8,      0,  C2*ry, -C1*rx,  C1*ry);
901     gfxline_t*l = line[0];
902     free(line);
903     return l;
904 }
905
906 gfxbbox_t* gfxline_isrectangle(gfxline_t*_l)
907 {
908     if(!_l)
909         return 0;
910
911     gfxline_t*l = gfxline_clone(_l);
912     gfxline_optimize(l);
913
914     double x1,x2,y1,y2;
915     int xc=0,yc=0;
916     char corners=0;
917
918     char prev=0;
919     char fail=0;
920     for(;l; l=l->next) {
921         double x = l->x;
922         double y = l->y;
923
924         char top=0,left=0;
925
926         if(xc==2 && x!=x1 && x!=x2) {fail=1;break;}
927         else if(xc>=1 && x==x1) {left=0;}
928         else if(xc==2 && x==x2) {left=1;}
929         else if(xc==1 && x!=x1) {x2 = x; xc=2; left=1;}
930         else if(xc==0) {x1 = x; xc=1;left=0;}
931         else {fprintf(stderr, "Internal error in rectangle detection\n");}
932
933         if(yc==2 && y!=y1 && y!=y2) {fail=1;break;}
934         else if(yc>=1 && y==y1) {top=0;}
935         else if(yc==2 && y==y2) {top=1;}
936         else if(yc==1 && y!=y1) {y2 = y; yc=2; top=1;}
937         else if(yc==0) {y1 = y; yc=1;top=0;}
938         else {fprintf(stderr, "Internal error in rectangle detection\n");}
939
940         char pos=top<<1|left;
941
942         if((pos^prev)==3) {
943             /* diagonal lines not allowed */
944             fail=1;break;
945         }
946         prev = pos;
947
948         /* no corner except the first one may be touched twice */
949         if(pos && (corners & 1<<pos)) {
950             fail=1;break;
951         }
952         /* mark which corners have been touched so far */
953         corners |= 1<<pos;
954     }
955     if(fail) {
956         gfxline_free(l);
957         return 0;
958     }
959
960     if(corners!=0x0f) return 0; // not all 4 corners reached
961
962     if(x2<x1) {double x = x2;x2=x1;x1=x;}
963     if(y2<y1) {double y = y2;y2=y1;y1=y;}
964
965     gfxbbox_t*r = malloc(sizeof(gfxbbox_t));
966     r->xmin = x1; r->ymin = y1;
967     r->xmax = x2; r->ymax = y2;
968     return r;
969 }
970
971 void gfximage_transform(gfximage_t*img, gfxcxform_t*cxform)
972 {
973     int t;
974     int size = img->width*img->height;
975
976     int rr,rg,rb,ra, tr;
977     int gr,gg,gb,ga, tg;
978     int br,bg,bb,ba, tb;
979     int ar,ag,ab,aa, ta;
980     rr = (int)(cxform->rr*256);gr = (int)(cxform->gr*256);
981     rg = (int)(cxform->rg*256);gg = (int)(cxform->gg*256);
982     rb = (int)(cxform->rb*256);gb = (int)(cxform->gb*256);
983     ra = (int)(cxform->ra*256);ga = (int)(cxform->ga*256);
984     br = (int)(cxform->br*256);ar = (int)(cxform->ar*256);tr = (int)(cxform->tr*256);
985     bg = (int)(cxform->bg*256);ag = (int)(cxform->ag*256);tg = (int)(cxform->tg*256);
986     bb = (int)(cxform->bb*256);ab = (int)(cxform->ab*256);tb = (int)(cxform->tb*256);
987     ba = (int)(cxform->ba*256);aa = (int)(cxform->aa*256);ta = (int)(cxform->ta*256);
988
989     for(t=0;t<size;t++) {
990         gfxcolor_t*pixel = &img->data[t];
991         unsigned char r = (pixel->r * rr + pixel->g * rg + pixel->b * rb + pixel->a * ra + tr) / 256;
992         unsigned char g = (pixel->r * gr + pixel->g * gg + pixel->b * gb + pixel->a * ga + tg) / 256;
993         unsigned char b = (pixel->r * br + pixel->g * bg + pixel->b * bb + pixel->a * ba + tb) / 256;
994         unsigned char a = (pixel->r * ar + pixel->g * ag + pixel->b * ab + pixel->a * aa + ta) / 256;
995         pixel->r = r;
996         pixel->g = g;
997         pixel->b = b;
998         pixel->a = a;
999     }
1000 }
1001 void gfxline_dump(gfxline_t*line, FILE*fi, char*prefix)
1002 {
1003     while(line) {
1004         if(line->type == gfx_moveTo) {
1005             fprintf(fi, "%smoveTo %.2f %.2f\n", prefix, line->x, line->y);
1006         } else if(line->type == gfx_lineTo) {
1007             fprintf(fi, "%slineTo %.2f %.2f\n", prefix, line->x, line->y);
1008         } else if(line->type == gfx_splineTo) {
1009             fprintf(fi, "%ssplineTo (%.2f %.2f) %.2f %.2f\n", prefix, line->sx, line->sy, line->x, line->y);
1010         }
1011         line = line->next;
1012     }
1013 }
1014
1015 static char gfxpoint_equals(void*c1, void*c2)
1016 {
1017     return !memcmp(c1, c2, sizeof(gfxpoint_t));
1018 }
1019 static unsigned int gfxpoint_hash(void*c)
1020 {
1021     return string_hash3(c, sizeof(gfxpoint_t));
1022 }
1023 static void* gfxpoint_clone(void*c)
1024 {
1025     void*n = malloc(sizeof(gfxpoint_t));
1026     memcpy(n, c, sizeof(gfxpoint_t));
1027     return n;
1028 }
1029 static void gfxpoint_destroy(void*c)
1030 {
1031     free(c);
1032 }
1033 static type_t gfxpoint_type = {
1034     hash: (hash_func)gfxpoint_hash,
1035     equals: (equals_func)gfxpoint_equals,
1036     dup: (dup_func)gfxpoint_clone,
1037     free: (free_func)gfxpoint_destroy,
1038 };
1039
1040 gfxline_t* gfxline_restitch(gfxline_t*line)
1041 {
1042     dict_t*ff = dict_new2(&gfxpoint_type);
1043     dict_t*rev = dict_new2(&gfxpoint_type);
1044     
1045     gfxline_t*prev=0;
1046     while(line) {
1047         gfxline_t*next = line->next;
1048         if(line->type == gfx_moveTo && (line->next && line->next->type != gfx_moveTo)) {
1049             gfxpoint_t xy = {line->x, line->y};
1050             dict_put(ff, &xy, line);
1051             prev = line;
1052         } else if(!line->next || line->next->type == gfx_moveTo) {
1053             if(prev) {
1054                 gfxpoint_t xy = {line->x, line->y};
1055                 dict_put(rev, &xy, prev);
1056                 line->next = 0;
1057                 prev=0;
1058             }
1059         }
1060         line = next;
1061     }
1062    
1063     gfxpoint_t pos = {0,0};
1064
1065     gfxline_t*result = 0;
1066     gfxline_t*last = 0;
1067    
1068     char first = 1;
1069     while(dict_count(ff)) {
1070         char reverse = 0, stitch = 1;
1071         gfxline_t*l = dict_lookup(ff, &pos);
1072         if(l) {
1073             char d = dict_del2(ff,&pos,l);assert(d);
1074         } else {
1075             l = dict_lookup(rev, &pos);
1076             if(l) {
1077                 reverse = 1;
1078                 char d = dict_del2(rev,&pos,l);assert(d);
1079             }
1080         }
1081         if(!l) {
1082             /* try to find *any* entry. this is costly, but
1083                doesn't happen too often */
1084             stitch = 0;
1085             DICT_ITERATE_DATA(ff, gfxline_t*, l2) {
1086                 l = l2;
1087                 break;
1088             }
1089             assert(l);
1090             gfxpoint_t xy = {l->x,l->y};
1091             char d = dict_del2(ff,&xy,l);assert(d);
1092         }
1093         
1094         gfxline_t*end = l;
1095         if(!reverse) {
1096             while(end->next) end = end->next;
1097             pos.x = end->x;
1098             pos.y = end->y;
1099             char d = dict_del2(rev,&pos,l);assert(d);
1100         } else {
1101             l = gfxline_reverse(l);
1102             pos.x = end->x;
1103             pos.y = end->y;
1104             char d = dict_del2(ff,&pos,end);assert(d);
1105         }
1106
1107         assert(l->type == gfx_moveTo);
1108         if(stitch && !first) {
1109             /* cut away the moveTo */
1110             gfxline_t*next = l->next;
1111             free(l);
1112             l = next;
1113         }
1114
1115         if(!last) {
1116             result = l;
1117             last = end;
1118         } else {
1119             last->next = l;
1120             last = end;
1121         }
1122         first = 0;
1123     }
1124     dict_destroy(ff);
1125     dict_destroy(rev);
1126     return result;
1127 }
1128
1129 gfxline_t* gfxline_reverse(gfxline_t*line)
1130 {
1131     gfxline_t*b = 0;
1132     while(line) {
1133         gfxline_t*next = line->next;
1134         if(next && next->type != gfx_moveTo) {
1135             line->type = next->type;
1136             line->sx = next->sx;
1137             line->sy = next->sy;
1138         } else {
1139             line->type = gfx_moveTo;
1140         }
1141         line->next = b;
1142         b = line;
1143         line = next;
1144     }
1145     return b;
1146 }
1147
1148 void gfxgradient_destroy(gfxgradient_t*gradient)
1149 {
1150     while(gradient) {
1151         gfxgradient_t*next = gradient->next;
1152         free(gradient);
1153         gradient = next;
1154     }
1155 }
1156
1157 gfxparams_t* gfxparams_new()
1158 {
1159     return (gfxparams_t*)rfx_calloc(sizeof(gfxparams_t));
1160 }
1161
1162 void gfxparams_store(gfxparams_t*params, const char*key, const char*value)
1163 {
1164     gfxparam_t*o = params->params;
1165     while(o) {
1166         if(!strcmp(key, o->key)) {
1167             /* overwrite old value */
1168             free((void*)o->value);
1169             o->value = strdup(value);
1170             return;
1171         }
1172         o = o->next;
1173     }
1174     gfxparam_t*p = (gfxparam_t*)malloc(sizeof(gfxparam_t));
1175     p->key = strdup(key);
1176     p->value = strdup(value);
1177     p->next = 0;
1178
1179     if(params->last) {
1180         params->last->next = p;
1181         params->last = p;
1182     } else {
1183         params->params = p;
1184         params->last = p;
1185     }
1186 }
1187
1188 void gfxparams_free(gfxparams_t*params)
1189 {
1190     gfxparam_t*p = params->params;
1191     while(p) {
1192         gfxparam_t*next = p->next;
1193         free((void*)p->key);
1194         if(p->value) free((void*)p->value);
1195         free(p);
1196         p = next;
1197     }
1198     free(params);
1199 }
1200