1 #ifndef lint
2 static char sccsid[] = "@(#)nvsort.c 1.4 (CWI) 87/03/05";
3 #endif
4 /*
5 * from (Berkeley):
6 * vsort.c 1.11 84/05/29
7 *
8 * Sorts and shuffles ditroff output for versatec wide printer. It
9 * puts pages side-by-side on the output, and fits as many as it can
10 * on one horizontal span. The versatec driver sees only pages of
11 * full width, not the individual pages. Output is sorted vertically
12 * and bands are created NLINES pixels high. Any object that has
13 * ANY part of it in a band is put on that band.
14 *
15 * Jaap Akkerhuis
16 * de-Berkletized by #ifdef BERK
17 */
18
19
20 #include <stdio.h>
21 #include <ctype.h>
22 #include <math.h>
23
24
25 /* #define DEBUGABLE /* compile-time flag for debugging */
26 #define FATAL 1
27 #define NVLIST 3000 /* size of list of vertical spans */
28 #define OBUFSIZ 250000 /* size of character buffer before sorting */
29 #define SLOP 1000 /* extra bit of buffer to allow for passing OBUFSIZ */
30 #define MAXVECT 200 /* maximum number of points (vectors) in a polygon */
31
32 #ifndef FONTDIR
33 #define FONTDIR "/usr/lib/font"
34 #endif FONTDIR
35
36 #define POINT 72 /* number of points per inch */
37
38 #ifndef VER80
39 #define WIDTH 7040 /* number of pixels across the page */
40 #else
41 #define WIDTH 2112 /* number of pixels across the page */
42 /*
43 * Note that this does not work unless the input really is
44 * designed for the versatec, i.e., res = 200. But that's
45 * OK, because it is only used for side-by-side pages, which
46 * we don't do anyway.
47 * DD
48 */
49 #endif VER80
50
51 #define BAND 2.2 /* length of each band in inches */
52 #define NLINES (int)(BAND * inch) /* number of pixels in each band */
53 #define HALF (inch/2)
54
55 #define hgoto(n) if((hpos = leftmarg + n) > maxh) maxh = hpos
56 #define hmot(n) if((hpos += n) > maxh) maxh = hpos
57 #define vmot(n) vpos += (n)
58 #define vgoto(n) vpos = (n)
59
60
61 int dbg = 0; /* debug flag != 0 means do debug output */
62
63 int size = 10; /* current size (points) */
64 int up = 0; /* number of pixels that the current size pushes up */
65 int down = 0; /* # of pixels that the current size will hang down */
66 int font = 1; /* current font */
67 char * fontdir = FONTDIR; /* place to find DESC.out file */
68 int inch = 200; /* resolution of the device, in inches */
69 int thick = 3; /* line thickness */
70
71 #ifdef BERK
72 int stip = 1; /* current stipple */
73 int style = -1; /* line style bit-mask */
74 #endif BERK
75
76
77 int hpos = 0; /* horizontal position to be at next (left = 0) */
78 int vpos = 0; /* current vertical position (down positive) */
79
80 int maxh = 0; /* farthest right we've gone on the current span */
81 int leftmarg= 0; /* current page offset */
82 int spanno = 0; /* current span number for driver in 'p#' commands */
83 int pageno = 0; /* number of pages spread across a physical page */
84
85
86 struct vlist {
87 unsigned short v; /* vertical position of this spread */
88 unsigned short h; /* horizontal position */
89 unsigned short t; /* line thickness */
90 #ifdef BERK
91 short st; /* style mask */
92 unsigned char l; /* stipple number */
93 #endif BERK
94 unsigned short u; /* upper extent of height */
95 unsigned short d; /* depth of height */
96 unsigned short s; /* point size */
97 unsigned char f; /* font number */
98 unsigned short x; /* set if this span starts with `x' command */
99 char *p; /* text pointer to this spread */
100 };
101
102 struct vlist vlist[NVLIST + 1];
103 struct vlist *vlp; /* current spread being added to */
104 int nvlist = 1; /* number of spreads in list */
105 int obufsiz = OBUFSIZ;
106 char obuf[OBUFSIZ + SLOP];
107 char *op = obuf; /* pointer to current spot in buffer */
108
109
110
main(argc,argv)111 main(argc, argv)
112 int argc;
113 char *argv[];
114 {
115 FILE *fp;
116 double atof();
117
118
119 vlp = &vlist[0]; /* initialize spread pointer */
120 vlp->p = op;
121 vlp->v = vlp->d = vlp->u = vlp->h = 0;
122 vlp->s = size;
123 vlp->f = font;
124 #ifdef BERK
125 vlp->l = stip;
126 vlp->st = style;
127 #endif BERK
128 vlp->t = thick;
129 /* we don't need added HxxVxxfxsxx for first span */
130 vlp->x++;
131
132 while (argc > 1 && **++argv == '-') {
133 switch ((*argv)[1]) {
134 case 'f':
135 fontdir = &(*argv)[2];
136 break;
137 #ifdef DEBUGABLE
138 case 'd':
139 dbg = atoi(&(*argv)[2]);
140 if (!dbg) dbg = 1;
141 break;
142 case 's':
143 if((obufsiz = atoi(&(*argv)[2])) > OBUFSIZ)
144 obufsiz = OBUFSIZ;
145 break;
146 #endif DEBUGABLE
147 }
148 argc--;
149 }
150
151 if (argc <= 1)
152 conv(stdin);
153 else
154 while (--argc > 0) {
155 if ((fp = fopen(*argv, "r")) == NULL)
156 error(FATAL, "can't open %s", *argv);
157 conv(fp);
158 fclose(fp);
159 }
160 done();
161 }
162
163 /* read number from input: copy to output */
164 int
getnumber(fp)165 getnumber (fp)
166 register FILE *fp;
167 {
168 register int k;
169 register char c;
170
171 while (isspace(c = getc(fp)))
172 ;
173 k = 0;
174 if (c == '-') {
175 #ifndef BERK
176 *op++ = c; /* should be output as well!!! */
177 #endif BERK
178 c = getc(fp);
179 do {
180 k = 10 * k - ((*op++ = c) - '0');
181 } while (isdigit(c = getc(fp)));
182 } else {
183 do {
184 k = 10 * k + (*op++ = c) - '0';
185 } while (isdigit(c = getc(fp)));
186 }
187 ungetc(c, fp);
188 return (k);
189 }
190
191 /* read number from input: do _N_O_T copy to output */
192 int
ngetnumber(fp)193 ngetnumber (fp)
194 register FILE *fp;
195 {
196 register int k;
197 register char c;
198
199 while (isspace(c = getc(fp)))
200 ;
201 k = 0;
202 if (c == '-') {
203 c = getc(fp);
204 do {
205 k = 10 * k - (c - '0');
206 } while (isdigit(c = getc(fp)));
207 } else {
208 do {
209 k = 10 * k + c - '0';
210 } while (isdigit(c = getc(fp)));
211 }
212 ungetc(c, fp);
213 return (k);
214 }
215
216
conv(fp)217 conv(fp)
218 register FILE *fp;
219 {
220 register int c;
221 int m, n, m1, n1;
222
223 while ((c = getc(fp)) != EOF) {
224 #ifdef DEBUGABLE
225 if (dbg > 2) fprintf(stderr, "conv: got:<%c>, op-obuf=%d V=%d\n", c, op-obuf, vpos);
226 #endif DEBUGABLE
227 if (op > obuf + obufsiz) {
228 error(!FATAL, "buffer overflow %d.", op - (obuf + obufsiz));
229 oflush();
230 }
231 switch (c) {
232 case '\0': /* filter out noise */
233 break;
234 case '\n': /* let text input through */
235 case '\t':
236 case ' ':
237 *op++ = c;
238 break;
239 case '{': /* push down current environment */
240 *op++ = c;
241 t_push();
242 break;
243 case '}': /* pop up last environment */
244 *op++ = c;
245 t_pop();
246 break;
247 case '0': case '1': case '2': case '3': case '4':
248 case '5': case '6': case '7': case '8': case '9':
249 /* two motion digits plus a character */
250 setlimit(vpos - up, vpos + down);
251 /*
252 *op++ = c;
253 hmot((c-'0') * 10 + (*op++ = getc(fp)) - '0');
254 *op++ = getc(fp);
255 */
256 n = ((c - '0') * 10 + ( m = getc(fp)) - '0');
257 hmot(n);
258 sprintf(op, "%02d", n);
259 op += strlen(op);
260 *op++ = getc(fp);
261 break;
262 case 'c': /* single ascii character */
263 setlimit(vpos - up, vpos + down);
264 *op++ = c;
265 *op++ = getc(fp);
266 break;
267 case 'C': /* white-space terminated funny character */
268 setlimit(vpos - up, vpos + down);
269 *op++ = c;
270 do
271 *op++ = c = getc(fp);
272 while (c != EOF && !isspace(c));
273 break;
274 case 't': /* straight text */
275 setlimit(vpos - up, vpos + down);
276 *op++ = c;
277 fgets(op, SLOP, fp);
278 op += strlen(op);
279 break;
280 case 'D': /* draw function */
281 switch (c = getc(fp)) {
282 int skip;
283 #ifdef BERK
284 case 's': /* "style" */
285 sprintf(op, "Ds ");
286 op += 3;
287 style = getnumber(fp);
288 break;
289
290 case 't': /* thickness */
291 sprintf(op, "Dt ");
292 op += 3;
293 thick = getnumber(fp);
294 break;
295 #endif BERK
296
297 case 'l': /* draw a line */
298 n1 = ngetnumber(fp);
299 m1 = ngetnumber(fp);
300 n = n1;
301 m = m1;
302 if (m < 0) {
303 setlimit(vpos+m-thick/2, vpos+thick/2);
304 } else {
305 setlimit(vpos-(1+thick/2),vpos+1+m+thick/2);
306 }
307 sprintf(op, "Dl %d %d", n, m);
308 op += strlen(op);
309 hmot(n1);
310 vmot(m1);
311 #ifndef BERK
312 /*
313 * note that this function is actually
314 * Dl n m .
315 * so we have to skip over the ".".
316 *
317 * Rhetoric question: Why doensn't Berkeley
318 * maintain compatability?
319 */
320 do{
321 skip = getc(fp);
322 if( skip == EOF)
323 error(FATAL,
324 "Cannot find . in Dl\n");
325 }while( skip != '.');
326 #endif BERK
327 break;
328
329 case 'e': /* ellipse */
330 n = ngetnumber(fp);
331 m = ngetnumber(fp);
332 setlimit(vpos-(m+thick)/2, vpos+(m+thick)/2);
333 sprintf(op, "De %d %d", n, m);
334 op += strlen(op);
335 hmot(n);
336 break;
337
338 case 'c': /* circle */
339 n = ngetnumber(fp);
340 setlimit(vpos-(n+thick)/2, vpos+(n+thick)/2);
341 sprintf(op, "Dc %d", n);
342 op += strlen(op);
343 hmot(n);
344 break;
345
346 case 'a': /* arc */
347 #ifdef BERK
348 n = getnumber(fp);
349 m = getnumber(fp);
350 n1 = getnumber(fp);
351 m1 = getnumber(fp);
352 #else
353 n = ngetnumber(fp);
354 m = ngetnumber(fp);
355 n1 = ngetnumber(fp);
356 m1 = ngetnumber(fp);
357 #endif BERK
358 arcbounds(n, m, n1, m1);
359 sprintf(op, "Da %d %d %d %d", n, m, n1, m1);
360 op += strlen(op);
361 hmot(n + n1);
362 vmot(m + m1);
363 break;
364
365 #ifdef BERK
366 case 'P':
367 case 'p':
368 {
369 register int nvect;
370 int member;
371 int border;
372 int x[MAXVECT];
373 int y[MAXVECT];
374
375
376 border = (c == 'p'); /* type of polygon */
377 member = ngetnumber(fp);/* and member number */
378
379 nvect = 1; /* starting point for */
380 x[1] = hpos; /* points on polygon */
381 y[1] = vpos;
382 m = n = vpos; /* = max/min vertical */
383 /* position for curve */
384 {
385 register int h;
386 register int v;
387
388
389 h = hpos; /* calculate max and minimum */
390 v = vpos; /* vertical position */
391 /* and get points */
392 do {
393 h += ngetnumber(fp);
394 v += ngetnumber(fp);
395
396 if (v < n) n = v;
397 else if (v > m) m = v;
398
399 if (nvect < (MAXVECT-1))/* keep the */
400 nvect++; /* points in */
401 x[nvect] = h; /* bounds */
402 y[nvect] = v; /* of arrays */
403 c = getc(fp);
404 } while (c != '\n' && c != EOF);
405 }
406 if (border) { /* output border as a */
407 register int *x1; /* bunch of lines */
408 register int *x2; /* instead of having */
409 register int *y1; /* the filter do it */
410 register int *y2;
411 register int extra = thick/2;
412
413 x1 = &(x[0]); /* x1, y1, x2, y2 are */
414 x2 = &(x[1]); /* for indexing along */
415 y1 = &(y[0]); /* coordinate arrays */
416 y2 = &(y[1]);
417 for (border = 0; ++border < nvect; ) {
418 if (*++y1 > *++y2) {
419 setlimit(*y2-extra, vpos+extra);
420 } else {
421 setlimit(vpos-(1+extra),*y2+1+extra);
422 /* the extra 1's are to force */
423 /* setlimit to know this is a */
424 /* real entry (making sure it */
425 /* doesn't get vpos as limit */
426 }
427 sprintf(op, "Dl %d %d\n",
428 c = *++x2 - *++x1, *y2 - *y1);
429 op += strlen(op);
430 hmot(c); /* update vpos for */
431 vgoto(*y2); /* the setlimit call */
432 }
433 } else {
434 register int *x1; /* x1, x2, are for */
435 register int *x2; /* indexing points */
436 register int i; /* random int */
437
438 x1 = &(x[0]);
439 x2 = &(x[1]);
440 for (i = 0; ++i < nvect; ) {
441 hmot(*++x2 - *++x1);
442 }
443 vgoto(y[nvect]);
444 sprintf(op, "H%dV%d", hpos, vpos);
445 op += strlen(op);
446 }
447 if (member) {
448 polygon(member, nvect, x, y, m, n);
449 }
450 }
451 break;
452 #endif BERK
453
454 case '~': /* wiggly line */
455 #ifdef BERK
456 case 'g': /* gremlin curve */
457 #endif BERK
458 startspan(vpos); /* always put curve */
459 sprintf(op, "D%c ", c); /* on its own span */
460 op += 3;
461
462 m = n = vpos; /* = max/min vertical */
463 do { /* position for curve */
464 /*
465 hpos += getnumber(fp);
466 *op++ = ' ';
467 vpos += getnumber(fp);
468 *op++ = ' ';
469 */
470 n1 = ngetnumber(fp);
471 m1 = ngetnumber(fp);
472
473 hmot(n1);
474 vmot(m1);
475 sprintf(op, "%d %d ", n1, m1);
476 op += strlen(op);
477
478 if (vpos < n) n = vpos;
479 else if (vpos > m) m = vpos;
480 c = getc(fp);
481 } while (c != '\n' && c != EOF);
482
483 vlp->u = n < 0 ? 0 : n;
484 vlp->d = m;
485 *op++ = '\n';
486 startspan(vpos);
487 break;
488
489 default:
490 error(FATAL,"unknown drawing command %c", c);
491 break;
492 }
493 break;
494 case 's':
495 *op++ = c;
496 size = getnumber(fp);
497 up = ((size + 1)*inch) / POINT; /* ROUGH estimate */
498 down = up / 3; /* of max up/down */
499 break;
500 case 'f':
501 *op++ = c;
502 font = getnumber(fp);
503 break;
504 #ifdef BERK
505 case 'i':
506 *op++ = c;
507 stip = getnumber(fp);
508 break;
509 #endif BERK
510 case 'H': /* absolute horizontal motion */
511 hgoto(ngetnumber(fp));
512 sprintf(op, "H%d", hpos);
513 op += strlen(op); /* reposition by page offset */
514 break;
515 case 'h': /* relative horizontal motion */
516 /*
517 *op++ = c;
518 hmot(getnumber(fp));
519 */
520 n = ngetnumber(fp);
521 hmot(n);
522 sprintf(op, "h%d", n);
523 op += strlen(op);
524 break;
525 case 'w': /* useless */
526 *op++ = c; /* But put it out anyway */
527 break;
528 case 'V': /* absolute vertical motion */
529 /*
530 *op++ = c;
531 vgoto(getnumber(fp));
532 */
533 vgoto(ngetnumber(fp));
534 sprintf(op, "V%d", vpos);
535 op += strlen(op);
536 break;
537 case 'v':
538 /*
539 *op++ = c;
540 vmot(getnumber(fp));
541 */
542 n = ngetnumber(fp);
543 vmot(n);
544 sprintf(op, "v%d", n);
545 op += strlen(op);
546 break;
547 case 'p': /* new page */
548 startspan(vpos);
549 t_page(ngetnumber(fp));
550 vpos = 0;
551 break;
552 case 'n': /* end of line */
553 hpos = leftmarg;
554 /*
555 *op++ = c;
556 do
557 *op++ = c = getc(fp);
558 while (c != '\n' && c != EOF);
559 */
560 *op++ = c;
561 n = ngetnumber(fp);
562 m = ngetnumber(fp);
563 sprintf(op, "%d %d", n, m);
564 op += strlen(op);
565 break;
566 case '#': /* comment */
567 do
568 c = getc(fp);
569 while (c != '\n' && c != EOF);
570 break;
571 case 'x': /* device control */
572 devcntrl(fp);
573 break;
574 default:
575 error(!FATAL, "unknown input character %o %c", c, c);
576 done();
577 }
578 }
579 }
580
devcntrl(fp)581 devcntrl(fp) /* interpret device control functions */
582 FILE *fp; /* returns -1 apon recieving "stop" command */
583 {
584 char str[20], str1[50], buf[50];
585 char *p;
586 int c, n, t1, t2;
587
588 fscanf(fp, "%s", str);
589 switch (str[0]) {
590 case 'r': /* resolution assumed when prepared */
591 fscanf(fp, "%d %d %d", &inch, &t1, &t2);
592 sprintf(str1, "x res %d %d %d", inch, t1, t2);
593 break;
594 default: /* reconstruct the string */
595 fgets(buf, sizeof buf, fp);
596 sprintf(str1, "x %s%s", str, buf);
597 }
598
599 startspan(vpos);
600 vlp->x++; /* yes, this is an x command */
601 p = str1;
602 while (*p)
603 *op++ = *p++;
604 }
605
606 /*----------------------------------------------------------------------------*
607 | Routine: setlimit
608 |
609 | Results: using "newup" and "newdown" decide when to start a new span.
610 | maximum rise and/or fall of a vertical extent are saved.
611 |
612 | Side Efct: may start new span.
613 *----------------------------------------------------------------------------*/
614
615 #define diffspan(x,y) ((x)/NLINES != (y)/NLINES)
616
setlimit(newup,newdown)617 setlimit(newup, newdown)
618 register int newup;
619 register int newdown;
620 {
621 register int currup = vlp->u;
622 register int currdown = vlp->d;
623
624 if (newup < 0) newup = 0; /* don't go back beyond start of page */
625 if (newdown < 0) newdown = 0;
626
627 if (diffspan(currup, currdown)) { /* now spans > one band */
628 if (diffspan(newup, currup) || diffspan(newdown, currdown)) {
629 startspan (vpos);
630 vlp->u = newup;
631 vlp->d = newdown;
632 } else {
633 if (newup < currup) vlp->u = newup;
634 if (newdown > currdown) vlp->d = newdown;
635 }
636 } else {
637 if (newup < currup) { /* goes farther up than before */
638 if (currup == vlp->v) { /* is new span, just set "up" */
639 vlp->u = newup;
640 } else {
641 if (diffspan(newup, currup)) { /* goes up farther */
642 startspan(vpos); /* than previously */
643 vlp->u = newup; /* AND to a higher */
644 vlp->d = newdown; /* band. */
645 return;
646 } else {
647 vlp->u = newup;
648 }
649 }
650 }
651 if (newdown > currdown) {
652 if (currdown == vlp->v) {
653 vlp->d = newdown;
654 return;
655 } else {
656 if (diffspan(newdown, currdown)) {
657 startspan(vpos);
658 vlp->u = newup;
659 vlp->d = newdown;
660 return;
661 } else {
662 vlp->d = newdown;
663 }
664 }
665 }
666 }
667 }
668
669
670 /*----------------------------------------------------------------------------*
671 | Routine: arcbounds (h, v, h1, v1)
672 |
673 | Results: using the horizontal positions of the starting and ending
674 | points relative to the center and vertically relative to
675 | each other, arcbounds calculates the upper and lower extent
676 | of the arc which is one of: starting point, ending point
677 | or center + rad for bottom, and center - rad for top.
678 |
679 | Side Efct: calls setlimit(up, down) to save the extent information.
680 *----------------------------------------------------------------------------*/
681
arcbounds(h,v,h1,v1)682 arcbounds(h, v, h1, v1)
683 int h, v, h1, v1;
684 {
685 register unsigned rad = (int)(sqrt((double)(h*h + v*v)) + 0.5);
686 register int i = ((h >= 0) << 2) | ((h1 < 0) << 1) | ((v + v1) < 0);
687
688 /* i is a set of flags for the points being on the */
689 /* left of the center point, and which is higher */
690
691 v1 += vpos + v; /* v1 is vertical position of ending point */
692 /* test relative positions for maximums */
693 setlimit( /* and set the up/down of the arc */
694 ((((i&3)==1) ? v1 : (((i&5)==4) ? vpos : vpos+v-rad)) - thick/2),
695 ((((i&3)==2) ? v1 : (((i&5)==1) ? vpos : vpos+v+rad)) + thick/2));
696 }
697
698
oflush()699 oflush() /* sort, then dump out contents of obuf */
700 {
701 register struct vlist *vp;
702 register int notdone;
703 register int topv;
704 register int botv;
705 register int i;
706 register char *p;
707
708 #ifdef DEBUGABLE
709 if (dbg) fprintf(stderr, "GAG me with an into oflush, V=%d\n", vpos);
710 #endif DEBUGABLE
711 if (op == obuf)
712 return;
713 *op = 0;
714
715 topv = 0;
716 botv = NLINES - 1;
717 do {
718 notdone = 0;
719 vp = vlist;
720 for (i = 0; i < nvlist; i++, vp++) {
721 #ifdef DEBUGABLE
722 if(dbg>1)fprintf(stderr,"oflush: u=%d, d=%d,%.60s\n",vp->u,vp->d,vp->p);
723 #endif DEBUGABLE
724 if (vp->u <= botv && vp->d >= topv) {
725 if(vp->x) /* doesn't need font or size */
726 printf("H%dV%d\n%s", vp->h,vp->v,vp->p);
727 else
728 printf("H%dV%ds%df%d\n%s",
729 vp->h,vp->v,vp->s,vp->f,vp->p);
730 }
731 notdone |= vp->d > botv; /* not done if there's still */
732 } /* something to put lower */
733 if (notdone) putchar('P'); /* mark the end of the spread */
734 topv += NLINES; /* unless it's the last one */
735 botv += NLINES;
736 } while (notdone);
737
738 fflush(stdout);
739 vlp = vlist;
740 vlp->p = op = obuf;
741 vlp->h = hpos;
742 vlp->v = vpos;
743 vlp->u = vpos;
744 vlp->d = vpos;
745 vlp->s = size;
746 vlp->f = font;
747 #ifdef BERK
748 vlp->l = stip;
749 vlp->st = style;
750 #endif BERK
751 vlp->t = thick;
752 vlp->x = 0;
753 *op = 0;
754 nvlist = 1;
755 }
756
757
done()758 done()
759 {
760 oflush();
761 exit(0);
762 }
763
error(f,s,a1,a2,a3,a4,a5,a6,a7)764 error(f, s, a1, a2, a3, a4, a5, a6, a7) {
765 fprintf(stderr, "vsort: ");
766 fprintf(stderr, s, a1, a2, a3, a4, a5, a6, a7);
767 fprintf(stderr, "\n");
768 if (f)
769 done();
770 }
771
772 #define MAXSTATE 5
773
774 struct state {
775 int ssize;
776 int sfont;
777 int shpos;
778 int svpos;
779 };
780 struct state state[MAXSTATE];
781 struct state *statep = state;
782
t_push()783 t_push() /* begin a new block */
784 {
785 statep->ssize = size;
786 statep->sfont = font;
787 statep->shpos = hpos;
788 statep->svpos = vpos;
789 hpos = vpos = 0;
790 if (statep++ >= state+MAXSTATE)
791 error(FATAL, "{ nested too deep");
792 hpos = vpos = 0;
793 }
794
t_pop()795 t_pop() /* pop to previous state */
796 {
797 if (--statep < state)
798 error(FATAL, "extra }");
799 size = statep->ssize;
800 font = statep->sfont;
801 hpos = statep->shpos;
802 vpos = statep->svpos;
803 }
804
805
806 /*----------------------------------------------------------------------------*
807 | Routine: t_page
808 |
809 | Results: new Margins are calculated for putting pages side-by-side.
810 | If no more pages can fit across the paper (WIDTH wide)
811 | a real page end is done and the currrent page is output.
812 |
813 | Side Efct: oflush is called on a REAL page boundary.
814 *----------------------------------------------------------------------------*/
815
t_page(n)816 t_page(n)
817 int n;
818 {
819 #ifndef VER80
820 static int first = 1; /* flag to catch the 1st time through */
821
822 /*
823 * if we're near the edge, or this is the first page
824 * we'll go over on this page.
825 */
826 if (leftmarg + 2*(pageno ? leftmarg/pageno : 0) > WIDTH
827 || maxh > WIDTH - inch || first) {
828 oflush();
829 printf("p%d\n", spanno++); /* make it a REAL page-break */
830 first = pageno = leftmarg = maxh = 0;
831
832 } else {
833 /* x = last page's width (in half-inches) */
834 register int x = (maxh - leftmarg + (HALF - 1)) / HALF;
835
836 if (x > 11 && x <= 17)
837 leftmarg += (8 * inch) + HALF; /* if close to 8.5" */
838 else /* then make it so */
839 leftmarg = ((maxh + HALF) / HALF) * HALF; /* else set it to the */
840 pageno++; /* nearest half-inch */
841 }
842 #else
843 oflush();
844 printf("p%d\n", n);
845 pageno = leftmarg = maxh = 0;
846 #endif VER80
847 }
848
849
startspan(n)850 startspan(n)
851 register int n;
852 {
853 *op++ = 0;
854 if (nvlist >= NVLIST) {
855 #ifdef DEBUGABLE
856 error(!FATAL, "(startspan) ran out of vlist");
857 #endif DEBUGABLE
858 oflush();
859 }
860 vlp++;
861 vlp->p = op;
862 vlp->v = n;
863 vlp->d = n;
864 vlp->u = n;
865 vlp->h = hpos;
866 vlp->s = size;
867 vlp->f = font;
868 #ifdef BERK
869 vlp->l = stip;
870 vlp->st = style;
871 #endif BERK
872 vlp->t = thick;
873 vlp->x = 0;
874 nvlist++;
875 }
876
877 #ifdef BERK
878
879 #define MAXX 0x7fff
880 #define MINX 0x8000
881
882 typedef struct poly {
883 struct poly *next; /* doublely-linked lists of vectors */
884 struct poly *prev;
885 int param; /* bressenham line algorithm parameter */
886 short dx; /* delta-x for calculating line */
887 short dy; /* delta-y for calculating line */
888 short currx; /* current x in this vector */
889 short endy; /* where vector ends */
890 } polyvector;
891
892
893 /*----------------------------------------------------------------------------*
894 | Routine: polygon ( member, num_vectors, x_coor, y_coor, maxy, miny )
895 |
896 | Results: outputs commands to draw a polygon starting at (x[1], y[1])
897 | going through each of (x_coordinates, y_coordinates), and
898 | filled with "member" stipple pattern.
899 |
900 | A scan-line algorithm is simulated and pieces of the
901 | polygon are put out that fit on bands of the versatec
902 | output filter.
903 |
904 | The format of the polygons put out are:
905 | 'Dp member num miny maxy [p dx dy curx endy]'
906 | where "num" is the number of [..] entries in that
907 | section of the polygon.
908 *----------------------------------------------------------------------------*/
909
polygon(member,nvect,x,y,maxy,miny)910 polygon(member, nvect, x, y, maxy, miny)
911 int member;
912 int nvect;
913 int x[];
914 int y[];
915 int maxy;
916 int miny;
917 {
918 int nexty; /* at what x value the next vector starts */
919 register int active; /* number of vectors in active list */
920 int firsttime; /* force out a polgon the first time through */
921 polyvector *activehead; /* doing fill, is active edge list */
922 polyvector *waitinghead; /* edges waiting to be active */
923 register polyvector *vectptr; /* random vector */
924 register int i; /* random register */
925
926
927 /* allocate space for raster-fill algorithm*/
928 vectptr = (polyvector *) malloc(sizeof(polyvector) * (nvect + 4));
929 if (vectptr == (polyvector *) NULL) {
930 error(!FATAL, "unable to allocate space for polygon");
931 return;
932 }
933
934 waitinghead = vectptr;
935 vectptr->param = miny - 1;
936 (vectptr++)->prev = NULL; /* put dummy entry at start */
937 waitinghead->next = vectptr;
938 vectptr->prev = waitinghead;
939 i = 1; /* starting point of coords */
940 if (y[1] != y[nvect] || x[1] != x[nvect]) {
941 y[0] = y[nvect]; /* close polygon if it's not */
942 x[0] = x[nvect];
943 i = 0;
944 }
945 active = 0;
946 while (i < nvect) { /* set up the vectors */
947 register int j; /* indexes to work off of */
948 register int k;
949
950 j = i; /* j "points" to the higher (lesser) point */
951 k = ++i;
952 if (y[j] == y[k]) /* ignore horizontal lines */
953 continue;
954
955 if (y[j] > y[k]) {
956 j++;
957 k--;
958 }
959 active++;
960 vectptr->next = vectptr + 1;
961 vectptr->param = y[j]; /* starting point of vector */
962 vectptr->dx = x[k] - x[j]; /* line-calculating parameters */
963 vectptr->dy = y[k] - y[j];
964 vectptr->currx = x[j]; /* starting point */
965 (vectptr++)->endy = y[k]; /* ending point */
966 vectptr->prev = vectptr - 1;
967 }
968 /* if no useable vectors, quit */
969 if (active < 2)
970 goto leavepoly;
971
972 vectptr->param = maxy + 1; /* dummy entry at end, too */
973 vectptr->next = NULL;
974
975 activehead = ++vectptr; /* two dummy entries for active list */
976 vectptr->currx = MINX; /* head */
977 vectptr->endy = maxy + 1;
978 vectptr->param = vectptr->dx = vectptr->dy = 0;
979 activehead->next = ++vectptr;
980 activehead->prev = vectptr;
981 vectptr->prev = activehead; /* tail */
982 vectptr->next = activehead;
983 vectptr->currx = MAXX;
984 vectptr->endy = maxy + 1;
985 vectptr->param = vectptr->dx = vectptr->dy = 0;
986
987 /* if there's no need to break the */
988 /* polygon into pieces, don't bother */
989 if (diffspan(miny, maxy)) {
990 active = 0; /* will keep track of # of vectors */
991 firsttime = 1;
992 } else { /* in the active list */
993 startspan(miny);
994 sprintf(op, "Dq %d %d %d %d", member, active, miny, maxy);
995 op += strlen(op);
996 for (vectptr = waitinghead->next; active--; vectptr++) {
997 sprintf(op, " %d %d %d %d %d",
998 vectptr->param, vectptr->dx, vectptr->dy,
999 vectptr->currx, vectptr->endy);
1000 op += strlen(op);
1001 }
1002 *(op++) = '\n';
1003 goto leavepoly;
1004 }
1005 /* main loop -- gets vectors off the waiting list, */
1006 /* then displays spans while updating the vectors in */
1007 /* the active list */
1008 while (miny <= maxy) {
1009 i = maxy + 1; /* this is the NEXT time to get a new vector */
1010 for (vectptr = waitinghead->next; vectptr != NULL; ) {
1011 if (miny == vectptr->param) {
1012 /* the entry in waiting list (vectptr) is */
1013 /* ready to go into active list. Need to */
1014 /* convert some vector stuff and sort the */
1015 /* entry into the list. */
1016 register polyvector *p; /* random vector pointers */
1017 register polyvector *v;
1018
1019 /* convert this */
1020 if (vectptr->dx < 0) /* entry to active */
1021 vectptr->param = -((vectptr->dx >> 1) + (vectptr->dy >> 1));
1022 else
1023 vectptr->param = (vectptr->dx >> 1) - (vectptr->dy >> 1);
1024
1025 p = vectptr; /* remove from the */
1026 vectptr = vectptr->next; /* waiting list */
1027 vectptr->prev = p->prev;
1028 p->prev->next = vectptr;
1029 /* find where it goes */
1030 /* in the active list */
1031 /* (sorted smallest first) */
1032 for (v = activehead->next; v->currx < p->currx; v = v->next)
1033 ;
1034 p->next = v; /* insert into active list */
1035 p->prev = v->prev; /* before the one it stopped on */
1036 v->prev = p;
1037 p->prev->next = p;
1038 active++;
1039 } else {
1040 if (i > vectptr->param) {
1041 i = vectptr->param;
1042 }
1043 vectptr = vectptr->next;
1044 }
1045 }
1046 nexty = i;
1047
1048 /* print the polygon while there */
1049 /* are no more vectors to add */
1050 while (miny < nexty) {
1051 /* remove any finished vectors */
1052 vectptr = activehead->next;
1053 do {
1054 if (vectptr->endy <= miny) {
1055 vectptr->prev->next = vectptr->next;
1056 vectptr->next->prev = vectptr->prev;
1057 active--;
1058 }
1059 } while ((vectptr = vectptr->next) != activehead);
1060
1061 /* output a polygon for this band */
1062 if (firsttime || !(miny % NLINES)) {
1063 register int numwait; /* number in the waiting list */
1064 register int newmaxy; /* max for this band (bottom or maxy)*/
1065
1066
1067 startspan(miny);
1068 if ((newmaxy = (miny / NLINES) * NLINES + (NLINES - 1)) > maxy)
1069 newmaxy = maxy;
1070
1071 /* count up those vectors that WILL */
1072 /* become active in this band */
1073 for (numwait = 0, vectptr = waitinghead->next;
1074 vectptr != NULL; vectptr = vectptr->next) {
1075 if (vectptr->param <= newmaxy)
1076 numwait++;
1077 }
1078
1079 sprintf(op,"Dq %d %d %d %d",member,active+numwait,miny,newmaxy);
1080 op += strlen(op);
1081 for (i = active, vectptr = activehead->next; i--;
1082 vectptr = vectptr->next) {
1083 sprintf(op, " %d %d %d %d %d",
1084 vectptr->param, vectptr->dx, -vectptr->dy,
1085 vectptr->currx, vectptr->endy);
1086 op += strlen(op);
1087 }
1088 for (vectptr = waitinghead->next; vectptr != NULL;
1089 vectptr = vectptr->next) {
1090 if (vectptr->param <= newmaxy) {
1091 sprintf(op, " %d %d %d %d %d",
1092 vectptr->param, vectptr->dx, vectptr->dy,
1093 vectptr->currx, vectptr->endy);
1094 op += strlen(op);
1095 }
1096 }
1097 *(op++) = '\n';
1098 firsttime = 0;
1099 }
1100
1101 /* update the vectors */
1102 vectptr = activehead->next;
1103 do {
1104 if (vectptr->dx > 0) {
1105 while (vectptr->param >= 0) {
1106 vectptr->param -= vectptr->dy;
1107 vectptr->currx++;
1108 }
1109 vectptr->param += vectptr->dx;
1110 } else if (vectptr->dx < 0) {
1111 while (vectptr->param >= 0) {
1112 vectptr->param -= vectptr->dy;
1113 vectptr->currx--;
1114 }
1115 vectptr->param -= vectptr->dx;
1116 }
1117 /* must sort the vectors if updates */
1118 /* caused them to cross */
1119 /* also move to next vector here */
1120 if (vectptr->currx < vectptr->prev->currx) {
1121 register polyvector *v; /* vector to move */
1122 register polyvector *p; /* vector to put it after */
1123
1124 v = vectptr;
1125 p = v->prev;
1126 while (v->currx < p->currx) /* find the */
1127 p = p->prev; /* right vector */
1128
1129 vectptr = vectptr->next; /* remove from spot */
1130 vectptr->prev = v->prev;
1131 v->prev->next = vectptr;
1132
1133 v->prev = p; /* put in new spot */
1134 v->next = p->next;
1135 p->next = v;
1136 v->next->prev = v;
1137 } else {
1138 vectptr = vectptr->next;
1139 }
1140 } while (vectptr != activehead);
1141
1142 ++miny;
1143 } /* while (miny < nexty) */
1144 } /* while (miny <= maxy) */
1145
1146 leavepoly:
1147 startspan(vpos); /* make sure stuff after polygon is at correct vpos */
1148 free(waitinghead);
1149 } /* polygon function */
1150 #endif BERK
1151