diff options
Diffstat (limited to 'mpm')
| -rw-r--r-- | mpm/Makefile.mk | 30 | ||||
| -rw-r--r-- | mpm/README | 191 | ||||
| -rw-r--r-- | mpm/misc.cc | 66 | ||||
| -rw-r--r-- | mpm/misc.h | 51 | ||||
| -rw-r--r-- | mpm/page.cc | 628 | ||||
| -rw-r--r-- | mpm/page.h | 132 | ||||
| -rw-r--r-- | mpm/queue.cc | 248 | ||||
| -rw-r--r-- | mpm/range.cc | 627 | ||||
| -rw-r--r-- | mpm/range.h | 348 | ||||
| -rw-r--r-- | mpm/slug.cc | 642 | ||||
| -rw-r--r-- | mpm/slug.h | 87 | ||||
| -rw-r--r-- | mpm/version.c | 20 |
12 files changed, 3070 insertions, 0 deletions
diff --git a/mpm/Makefile.mk b/mpm/Makefile.mk new file mode 100644 index 0000000000000..849a45041259c --- /dev/null +++ b/mpm/Makefile.mk @@ -0,0 +1,30 @@ +OBJ = misc.o page.o queue.o range.o slug.o version.o + +FLAGS = $(EUC) $(DEFINES) + +.c.o: + $(CC) $(CFLAGS) $(WARN) $(FLAGS) $(CPPFLAGS) -c $< + +.cc.o: + $(CXX) $(CFLAGS) $(WARN) $(FLAGS) $(CPPFLAGS) -c $< + +all: pm + +pm: $(OBJ) + $(CXX) $(CFLAGS) $(LDFLAGS) $(OBJ) $(LIBS) -lm -o pm + +install: all + test -d $(ROOT)$(LIBDIR) || mkdir -p $(ROOT)$(LIBDIR) + $(INSTALL) -c pm $(ROOT)$(LIBDIR)/pm + $(STRIP) $(ROOT)$(LIBDIR)/pm + +clean: + rm -f $(OBJ) pm core log *~ + +mrproper: clean + +misc.o: misc.cc misc.h +page.o: page.cc misc.h slug.h range.h page.h +queue.o: queue.cc misc.h slug.h range.h page.h +range.o: range.cc misc.h slug.h range.h +slug.o: slug.cc misc.h slug.h diff --git a/mpm/README b/mpm/README new file mode 100644 index 0000000000000..369b76bf64e60 --- /dev/null +++ b/mpm/README @@ -0,0 +1,191 @@ +from <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> +------------------------------------------------------------------------ + +An experiment in page makeup for troff output... + +-mpm is a version of standard -ms that causes extra +information for vertical justification and figure +placement to be included in troff output. Commands that +have been augmented to provide paddable space are + + .SH and .NH + .PP and .LP no space if \n(PD is 0; normally .nr PD 0.3v; leave at least 1u + .IP and .QP also + .EQ and .EN + .TS and .TE no space if \n(TS is 0; normally .nr TS 0.5v + .PS and .PE + .P1 and .P2 display programs in CW font + .DS and .DE + .QS and .QE + +Other commands, registers, strings, etc.: + + .SP n explicit paddable space, just like .sp n. + generally you should ALWAYS use .SP instead of .sp. + if you need exactly a given vertical space, you can say + .SP 3i exactly + this space won't be padded. + .Tm words prints "words" and the output page number on stderr + sorry about the spelling; -ms pre-empted .TM + .NE n like .ne. note: does not cause a break + + Others may be added as the need arises. + + .nr FO n Set the page length. This value is the bottom of + the text on the page; a bottom title may lie below. + default is 10i (== 10 inches). + %o, %e are strings containing odd and even page titles + %# is the current page number (often useless) + .PT is a macro invoked at the top of each "page"; + it will normally use %e, %o and %#. There is also + a .BT for page bottoms if desired. + .BP force a page break + .FL force all waiting figures out before any more running text + .1C, .2C multiple columns; number registers CW and GW set + the column and gutter width if you don't like the default. + absent a .FC command, all two-column contents collect + together on the page + .FC freeze current two-column contents and start afresh. + necessary if you want to switch between 1 and 2 column + text and keep the relative order among them. + +Usage is some variant of + + ... | troff -mpm + +/usr/lib/tmac/pm is the page-justifier itself; it is called automatically +by the -mpm macro package. If you are installing this yourself, you will +have to edit the 2nd line of tmac.pm to arrange that pm is called directly +from troff. + +There are several lines in tmac.pm that say + .so /n/coma/usr/bwk/... +You should delete these; they are placeholders for some experiments. + +If you use -mm, you are more or less out of luck, although we will be +happy to provide a crude and incomplete program that purports to convert +-mm to -ms. It may suggest what you need but it won't do the job. + +To compile pm, you need a C++ compiler, preferably release 2.0 or later. +Put the .c and .h files in a directory, and type + make +This process may well fail. The usual cause is that different systems +put function declarations in different header files, and C++ insists that +all functions be properly declared. You can almost always get through this +part by adding function declarations. The most likely offender is malloc; +a line like + extern char *malloc(int); +near the top of slug.c will solve this one. + + +Bugs, etc.: + + not all -ms commands have been decorated; in particular, + the rich variety of document types (TM, CSTR, etc.,) is not + really supported. + + there are problems with funny first pages and troff input + that moves back up the page. + + multiple columns: only .2C is available. The program does not check + whether something is wide or narrow: user has responsibility to mark + which with .1C or .2C. + + headings are a bit tricky if you want things like + running titles that include the current section title. + normally a two-pass procedure using .Tm is needed. + + It's a pain to force a blank vertical space of specified height. + Try this: + .de x + \v'\\$1'\0\h'-\w'\0'u'\c + .. + .x 2.5i + + +If you want to roll your own, the following components are +included in pm's "command language". They are inserted in +the troff output in the form of "x X ..." commands, which +are created either by \X'...' or by the .X macro in -mpm. +Look at how they are used in /usr/lib/tmac/tmac.pm for examples. + + +BS n breakable stream n = min # lines that must appear on page + use: PP, LP, IP, ... + +US unbreakable stream use: KS/KE, DS/DE, TS/TE, EQ/EN, PS/PE, etc. + +BF v breakable float v = preferred vertical location of box center + use: FS/FE + use two successive BF's to give two preferences + +UF v unbreakable float v = preferred vertical location of box center + use: KF/KE + use two successive UF's to give two preferences + +PT page title use: user has absolute control between PT and END + no SP's or other pm commands inside are processed + +BT bottom title use: user has absolute control between BT and END + +END end end a US, BF, UF, PT, or BT + all constructs nest, but a float within another float + or a US block will not float within or outside the block + +NE n need break page if a VBOX of height n would not fit on page + use: .NE n + +SP n space paddable space of n + use: .SP n + +PARM NP v top of pm text at v + new page + +PARM FO v bottom of pm text at v + footer length of text on page = FO-NP + +PARM PL v physical page ends at v + page length default = FO + NP + +PARM MF x tolerance to prevent padding + minimum fullness default = 0.9 + +PARM CT x tolerance for two-column operation + column tolerance default = 0.5 + +PARM DBG x debugging flag + +TM str message .Tm words prints <pageno> <tab> <words> on stderr + +MC n o multiple column n columns, offset o. + Only 1 and 2 columns will work. + +CMD BP break page force page break + +CMD FL flush force all queued figures out before any more + stream material is output + +CMD FC freeze columns force out current two-column contents; + start a fresh one + +Something like this will probably have to be added: + +NC new column HARD! + +Known botches in the existing implementation of pm: + +If a footnote is split across two pages, any associated separator line +will not be copied. If there are multiple footnotes on one page, there +will be multiple separators too. -mpm's .FS macro does not provide a +separator. If you want a separator line, put it in explicitly with +a call to the .FA macro. + +There are not enough settable parameters; in particular, the +way to control the height is a botch. + + +Historical note: There is a simpler version of pm and -mpm +called pj and -mpj that only does vertical justification of +pages that have already been laid out by conventional means. +This simpler version may be adequate, but it is no longer +supported and memory of how it works is growing dim. diff --git a/mpm/misc.cc b/mpm/misc.cc new file mode 100644 index 0000000000000..e83bf2531e4e4 --- /dev/null +++ b/mpm/misc.cc @@ -0,0 +1,66 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)misc.cc 1.3 (gritter) 10/30/05 */ +#include "misc.h" +#include <stdarg.h> + +char *progname; +int wantwarn = 0; + +int dbg = 0; +// dbg = 1 : dump slugs +// dbg = 2 : dump ranges +// dbg = 4 : report function entry +// dbg = 8 : follow queue progress +// dbg = 16: follow page fill progress + +static void +msg(void) +{ + fprintf(stdout, "\n#MESSAGE TO USER: "); +} + +void +FATAL(const char *fmt, ...) +{ + char buf[4096]; + va_list ap; + + msg(); + va_start(ap, fmt); + vsnprintf(buf, sizeof buf, fmt, ap); + va_end(ap); + fputs(buf, stdout); + fprintf(stderr, "%s: ", progname); + fputs(buf, stderr); + fflush(stdout); + exit(1); +} + +void +WARNING(const char *fmt, ...) +{ + char buf[4096]; + va_list ap; + + msg(); + va_start(ap, fmt); + vsnprintf(buf, sizeof buf, fmt, ap); + va_end(ap); + fputs(buf, stdout); + if (wantwarn) { + fprintf(stderr, "%s: ", progname); + fputs(buf, stderr); + } + fflush(stdout); +} diff --git a/mpm/misc.h b/mpm/misc.h new file mode 100644 index 0000000000000..d46efd75be4ca --- /dev/null +++ b/mpm/misc.h @@ -0,0 +1,51 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)misc.h 1.3 (gritter) 10/30/05 */ +#include <stdio.h> +#include <stdlib.h> +#include <math.h> +#include <ctype.h> +#include <string.h> + +#ifdef __GLIBC__ +#ifdef _IO_getc_unlocked +#undef getc +#define getc(f) _IO_getc_unlocked(f) +#endif +#ifdef _IO_putc_unlocked +#undef putc +#undef putchar +#define putc(c, f) _IO_putc_unlocked(c, f) +#define putchar(c) _IO_putc_unlocked(c, stdout) +#endif +#endif /* __GLIBC__ */ + +extern char *progname; +extern int linenum; +extern int wantwarn; + +extern void FATAL(const char *, ...); +extern void WARNING(const char *, ...); + +#define eq(s,t) (strcmp(s,t) == 0) + +inline int max(int x, int y) { return x > y ? x : y; } +inline int min(int x, int y) { return x > y ? y : x; } +// already defined in stdlib.h: +//inline int abs(int x) { return (x >= 0) ? x : -x; } + +extern int dbg; + +extern int pn, userpn; // actual and user-defined page numbers +extern int pagetop, pagebot; // printing margins +extern int physbot; // physical bottom of the page diff --git a/mpm/page.cc b/mpm/page.cc new file mode 100644 index 0000000000000..95efd405ff1a1 --- /dev/null +++ b/mpm/page.cc @@ -0,0 +1,628 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)page.cc 1.4 (gritter) 10/30/05 */ +#include <locale.h> +#include "misc.h" +#include "slug.h" +#include "range.h" +#include "page.h" + +const int MAXRANGES = 1000; +static range *ptemp[MAXRANGES]; // for movefloats() + +static void swapright(int n) // used by movefloats() +{ + range *t = ptemp[n]; + ptemp[n] = ptemp[n+1]; + ptemp[n+1] = t; + ptemp[n]->setaccum( ptemp[n+1]->accum() - + ptemp[n+1]->rawht() + ptemp[n]->rawht() ); + ptemp[n+1]->setaccum( ptemp[n]->accum() + ptemp[n+1]->rawht() ); +} + +// Figure out the goal position for each floating range on scratch, +// and move it past stream ranges until it's as close to its goal as possible. +static void movefloats(stream *scratch, double scale) +{ + const int Huge = 10000000; + int nranges; + for (nranges = 0; scratch->more(); scratch->advance()) + ptemp[nranges++] = scratch->current(); + scratch->freeall(); + ufrange rtemp; + ptemp[nranges] = &rtemp; + rtemp.setgoal(Huge); + int accumV = 0; // compute accum values and + int i; + for (i = 0; i < nranges; i++) { // pick closest goal for floats + ptemp[i]->pickgoal(accumV, scale); + ptemp[i]->setaccum(accumV += ptemp[i]->rawht()); + } + int j; // index for inner loop below: + for (i = nranges; --i >= 0; ) // stably sort floats to bottom + for (j = i; j < nranges; j++) + if (ptemp[j]->goal() > ptemp[j+1]->goal()) + swapright(j); + else + break; + if (dbg & 16) + printf("#movefloats: before floating, from bottom:\n"); + for (i = nranges; --i >= 0; ) { // find topmost float + if (ptemp[i]->goal() == NOGOAL) + break; + if (dbg & 16) + printf("# serialno %d goal %d height %d\n", + ptemp[i]->serialno(), ptemp[i]->goal(), + ptemp[i]->rawht()); + } // i+1 is topmost float + for (i++ ; i < nranges; i++) // move each float up the page + for (j = i; j > 0; j--) // as long as closer to its goal + if (ptemp[j]->goal() + <= ptemp[j-1]->accum() + ptemp[j]->rawht()/2 + && ptemp[j-1]->goal() == NOGOAL) + swapright(j-1); + else + break; + if (ptemp[nranges] != &rtemp) + FATAL("goal sentinel has disappeared from movefloats"); + for (i = 0; i < nranges; i++) // copy sorted list back + scratch->append(ptemp[i]); +} + +// Traverse the leaves of a tree of ranges, filtering out only SP and VBOX. +static range *filter(generator *g) +{ + range *r; + while ((r = g->next())) + if (r->isvbox() || r->issp()) + break; + return r; +} + +// Zero out leading and trailing spaces; coalesce adjacent SP's. +static void trimspace(stream *scratch) +{ + range *r, *prevr = 0; + generator g; + for (g = scratch; (r = filter(&g)) != 0 && r->issp(); prevr = r) + r->setheight(0); // zap leading SP + for ( ; (r = filter(&g)) != 0; prevr = r) + if (r->issp()) + { + if (prevr && prevr->issp()) { + // coalesce adjacent SPs + r->setheight(max(r->rawht(), prevr->height())); + prevr->setheight(0); + } else // a VBOX intervened + r->setheight(r->rawht()); + } + if (prevr && prevr->issp()) // zap *all* trailing space + prevr->setheight(0); // (since it all coalesced + // into the last one) +} + +// Pad the non-zero SP's in scratch so the total height is wantht. +// Note that the SP values in scratch are not the raw values, and +// indeed may already have been padded. +static void justify(stream *scratch, int wantht) +{ + range *r; + int nsp = 0, hsp = 0; + + int adjht = scratch->height(); + // Find all the spaces. + generator g; + for (g = scratch; (r = g.next()); ) + if (r->issp() && r->height() > 0) { + nsp++; + hsp += r->height(); + } + int excess = wantht - adjht; + if (excess < 0) + WARNING("something on page %d is oversize by %d\n", + userpn, -excess); + if (dbg & 16) + printf("# justify %d: excess %d nsp %d hsp %d adjht %d\n", + userpn, excess, nsp, hsp, adjht); + if (excess <= 0 || nsp == 0) + return; + // Redistribute the excess space. + for (g = scratch; (r = g.next()); ) + if (r->issp() && r->height() > 0) { + int delta = (int) ((float)(r->height()*excess)/hsp + 0.5); + if (dbg & 16) + printf("# pad space %d by %d: hsp %d excess %d\n", + r->height(), delta, hsp, excess); + r->setheight(r->height() + delta); + } +} + +// If r were added to s, would the height of the composed result be at most maxht? +int wouldfit(range *r, stream *s, int maxht) +{ + if (r->rawht() + s->rawht() <= maxht) + return 1; // the conservative test succeeded + stream scratch; // local playground for costly test + for (stream cd = *s; cd.more(); cd.advance()) + scratch.append(cd.current()); + scratch.append(r); + movefloats(&scratch, ((double) scratch.rawht())/maxht); + trimspace(&scratch); + int retval = scratch.height() <= maxht; + scratch.freeall(); + return retval; +} + +// If s1 were added to s, would the height of the composed result be at most maxht? +// The computational structure is similar to that above. +int wouldfit(stream *s1, stream *s, int maxht) +{ + if (s1->rawht() + s->rawht() <= maxht) + return 1; + stream scratch, cd; + for (cd = *s; cd.more(); cd.advance()) + scratch.append(cd.current()); + for (cd = *s1; cd.more(); cd.advance()) + scratch.append(cd.current()); + movefloats(&scratch, ((double) scratch.rawht())/maxht); + trimspace(&scratch); + int retval = scratch.height() <= maxht; + scratch.freeall(); + return retval; +} + +// All of stream *s is destined for one column or the other; which is it to be? +void multicol::choosecol(stream *s, int goalht) +{ + stream *dest; + if (!leftblocked && wouldfit(s, &(column[0]), goalht)) + dest = &(column[0]); + else { + dest = &(column[1]); + if (!s->current()->floatable()) + // a stream item is going into the right + // column, so no more can go into the left. + leftblocked = 1; + } + for (stream cd = *s; cd.more(); cd.advance()) + dest->append(cd.current()); +} + +double coltol = 0.5; + +// Try, very hard, to put everything in the multicol into two columns +// so that the total height is at most htavail. +void multicol::compose(int defonly) +{ + if (!nonempty()) { + setheight(0); + return; + } + scratch.freeall(); // fill scratch with everything destined + // for either column + stream cd; + for (cd = definite; cd.more(); cd.advance()) + scratch.append(cd.current()); + if (!defonly) + for (cd = *(currpage->stage); cd.more(); cd.advance()) + if (cd.current()->numcol() == 2) + scratch.append(cd.current()); + scratch.restoreall(); // in particular, floatables' goals + int rawht = scratch.rawht(); + int halfheight = (int)(coltol*rawht); + // choose a goal height + int maxht = defonly ? halfheight : htavail; +secondtry: + int i; + for (i = 0; i < 2; i++) + column[i].freeall(); + leftblocked = 0; + cd = scratch; + while (cd.more()) { + queue ministage; // for the minimally acceptable chunks + ministage.freeall(); // that are to be added to either column + while (cd.more() && !cd.current()->issentinel()) { + ministage.enqueue(cd.current()); + cd.advance(); + } + choosecol(&ministage, maxht); + if (cd.more() && cd.current()->issentinel()) + cd.advance(); // past sentinel + } + if (height() > htavail && maxht != htavail) { + // We tried to balance the columns, but + // the result was too tall. Go back + // and try again with the less ambitious + // goal of fitting the space available. + maxht = htavail; + goto secondtry; + } + for (i = 0; i < 2; i++) { + movefloats(&(column[i]), ((double) column[i].rawht())/currpage->pagesize); + trimspace(&(column[i])); + } + if (dbg & 32) { + printf("#multicol::compose: htavail %d maxht %d dv %d\n", + htavail, maxht, height()); + dump(); + } + if (defonly) + stretch(height()); +} + +// A sequence of two-column ranges waits on the stage. +// So long as the page's skeleton hasn't changed--that is, the maximum height +// available to the two-column chunk is the same--we just use the columns that +// have been built up so far, and choose a column into which to put the stage. +// If the skeleton has changed, however, then we may need to make entirely +// new decisions about which column gets what, so we recompose the whole page. +void multicol::tryout() +{ + if (htavail == prevhtavail) + choosecol(currpage->stage, htavail); + else + currpage->compose(DRAFT); + prevhtavail = htavail; +} + +// Make both columns the same height. +// (Maybe this should also be governed by minfull, +// to prevent padding very underfull columns.) +void multicol::stretch(int wantht) +{ + if (wantht < height()) + FATAL("page %d: two-column chunk cannot shrink\n", userpn); + for (int i = 0; i < 2; i++) + justify(&(column[i]), wantht); + if (dbg & 16) + printf("#col hts: left %d right %d\n", + column[0].height(), column[1].height()); +} + +// Report an upper bound on how tall the current two-column object is. +// The (possibly composed) heights of the two columns give a crude upper +// bound on the total height. If the result is more than the height +// available for the two-column object, then the columns are each +// composed to give a better estimate of their heights. +int multicol::height() +{ + int retval = max(column[0].height(), column[1].height()); + if (retval < htavail) + return retval; + for (int i = 0; i < 2; i++) { + movefloats(&(column[i]), ((double) column[i].height())/currpage->pagesize); + trimspace(&(column[i])); + } + return max(column[0].height(), column[1].height()); +} + +void multicol::dump() +{ + printf("####2COL dv %d\n", height()); + printf("# left column:\n"); + column[0].dump(); + printf("# right column:\n"); + column[1].dump(); +} + +// From the head of queue qp, peel off a piece whose raw height is at most space. +int peeloff(stream *qp, int space) +{ + stream *s1 = qp->current()->children(); + if (!(s1 && s1->more() && s1->current()->height() <= space)) + // in other words, either qp's head is + // not nested, or its first subrange + return 0; // is also too big, so we give up + qp->split(); + s1 = qp->current()->children(); + stream *s2 = qp->next()->children(); + while (s2->more() && s2->current()->rawht() <= space) { + s1->append(s2->current()); + space -= s2->current()->rawht(); + s2->advance(); + } + return 1; +} + +// There are four possibilities for consecutive calls to tryout(). +// If we're processing a sequence of single-column ranges, tryout() +// uses the original algorithm: (1) conservative test; (2) costly test; +// (3) split a breakable item. +// If we're processing a sequence of double-column ranges, tryout() +// defers to twocol->tryout(), which gradually builds up the contents +// of the two columns until they're as tall as they can be without +// exceeding twocol->htavail. +// If we're processing a sequence of single-column ranges and we +// get a double-column range, then we use compose() to build a +// skeleton page and set twocol->htavail, the maximum height that +// should be occupied by twocol. +// If we're processing a sequence of double-column ranges and we +// get a single-column range, then we should go back and squish +// the double-column chunk as short as possible before we see if +// we can fit the single-column range. +void page::tryout() +{ + if (!stage->more()) + FATAL("empty stage in page::tryout()\n"); + int curnumcol = stage->current()->numcol(); + if (dbg & 32) { + printf("#page::tryout(): ncol = %d, prevncol = %d; on stage:\n", + curnumcol, prevncol); + stage->dump(); + printf("#END of stage contents\n"); + } + switch(curnumcol) { + default: + FATAL("unexpected number of columns in tryout(): %d\n", + stage->current()->numcol()); + break; + case 1: + if (prevncol == 2) + compose(FINAL); + if (wouldfit(stage, &definite, pagesize - twocol->height())) + commit(); + else if (stage->current()->breakable() || (blank() + && peeloff(stage, + pagesize - (definite.height() + + twocol->height())))) { + // first add the peeled-off part that fits + adddef(stage->dequeue()); + // then send the rest back for later + stage->current()->setbreaking(); + welsh(); + } else if (blank()) { + stage->current()->rdump(); + FATAL("A %s is too big to continue.\n", + stage->current()->typname()); + } else + welsh(); + break; + case 2: + if (prevncol == 1) + compose(DRAFT); + else + twocol->tryout(); + if (scratch.height() <= pagesize) + commit(); + else + welsh(); + break; + } + prevncol = curnumcol; +} + +// To compose the page, we (1) fill scratch with the stuff that's meant to +// go on the page; (2) compose scratch as best we can; (3) set the maximum +// height available to the two-column part of the page; (4) have the two- +// column part compose itself. +// In the computation of twocol->htavail, it does not matter that +// twocol->height() is merely an upper bound, because it is merely being +// subtracted out to give the exact total height of the single-column stuff. +void page::compose(int final) +{ + makescratch(final); + int adjht = scratch.rawht(); + if (dbg & 16) + printf("# page %d measure %d\n", userpn, adjht); + movefloats(&scratch, ((double) adjht)/pagesize); + trimspace(&scratch); + twocol->htavail = pagesize - (scratch.height() - twocol->height()); + twocol->compose(final); + adjht = scratch.height(); + if (dbg & 16) + printf("# page %d measure %d after trim\n", userpn, adjht); +} + +// Fill the scratch area with ranges destined for the page. +// If defonly == 0, then add anything that's on stage--this is a trial run. +// If defonly != 0, use only what's definitely on the page. +void page::makescratch(int defonly) +{ + scratch.freeall(); + stream cd; + for (cd = definite; cd.more(); cd.advance()) + scratch.append(cd.current()); + if (!defonly) + for (cd = *stage; cd.more(); cd.advance()) + if (cd.current()->numcol() == 1) + scratch.append(cd.current()); + if (twocol->nonempty()) + scratch.append(twocol); +} + +// Accept the current contents of the stage. +// If the stage contains two-column ranges, add a sentinel to indicate the end +// of a chunk of stage contents. +void page::commit() +{ + if (dbg & 4) + printf("#entering page::commit()\n"); + int numcol = 0; + while (stage->more()) { + numcol = stage->current()->numcol(); + adddef(stage->dequeue()); + } + if (numcol == 2) + adddef(new sentrange); +} + +// Send the current contents of the stage back to its source. +void page::welsh() +{ + if (dbg & 4) + printf("#entering page::welsh()\n"); + while (stage->more()) { + range *r = stage->dequeue(); + r->enqueue(ANDBLOCK); + } +} + +enum { USonly = 1 }; + +// So long as anything is eligible to go onto the page, keep trying. +// Once nothing is eligible, compose and justify the page. +void page::fill() +{ + while (stage->prime()) + stage->pend(); + compose(FINAL); + if (dbg & 16) + scratch.dump(); + if (anymore()) { + int adjht = scratch.height(); + if (adjht > minfull*pagesize) { + justify(&scratch, pagesize); + adjht = scratch.height(); + int stretchamt = max(pagesize - adjht, 0); + twocol->stretch(twocol->height() + stretchamt); + // in case the page's stretchability lies + // entirely in its two-column part + } else + WARNING("page %d only %.0f%% full; will not be adjusted\n", + userpn, 100*(double) adjht/pagesize); + } +} + +void page::adddef(range *r) +{ + if (dbg & 4) + printf("#entering page::adddef()\n"); + switch (r->numcol()) { + case 1: definite.append(r); + break; + case 2: twocol->definite.append(r); + break; + default: FATAL("%d-column range unexpected\n", r->numcol()); + } +} + +int multicol::print(int cv, int col) +{ + if (col != 0) + FATAL("multicolumn output must start in left column\n"); + int curv = cv, maxv = cv; // print left column + for ( ; column[0].more(); column[0].advance()) { + curv = column[0].current()->print(curv, 0); + maxv = max(maxv, curv); + } + curv = cv; // print right column + for ( ; column[1].more(); column[1].advance()) { + curv = column[1].current()->print(curv, 1); + maxv = max(maxv, curv); + } + return maxv; +} + +void page::print() +{ + static int tops = 1, bots = 1; + if (!scratch.more()) { + WARNING("## Here's what's left on squeue:\n"); + squeue.dump(); + WARNING("## Here's what's left on bfqueue:\n"); + bfqueue.dump(); + WARNING("## Here's what's left on ufqueue:\n"); + ufqueue.dump(); + WARNING("page %d appears to be empty\n", userpn); + fflush(stderr), fflush(stdout), exit(0); + // something is very wrong if this happens + } + printf("p%d\n", userpn); // print troff output page number + if (ptlist.more()) { // print page header + ptlist.current()->print(0, 0); + ptlist.advance(); + } else if (tops) { + WARNING("ran out of page titles at %d\n", userpn); + tops = 0; + } + int curv = 0; + printf("V%d\n", curv = pagetop);// print page contents + for ( ; scratch.more(); scratch.advance()) { + curv = scratch.current()->print(curv, 0); + } + if (btlist.more()) { // print page footer + btlist.current()->print(0, 0); + btlist.advance(); + } else if (bots) { + WARNING("ran out of page bottoms at %d\n", userpn); + bots = 0; + } + printf("V%d\n", physbot); // finish troff output page +} + +int pagetop = 0; // top printing margin +int pagebot = 0; // bottom printing margin +int physbot = 0; // physical bottom of page + +double minfull = 0.9; // minimum fullness before padding + +int pn = 0; // cardinal page number +int userpn = 0; // page number derived from PT slugs + +static void makepage() +{ + page pg(pagebot - pagetop); + ++pn; + userpn = ptlist.more() ? ptlist.current()->pn() : pn; + pg.fill(); + pg.print(); +} + +static void conv(FILE *fp) +{ + startup(fp); // read slugs, etc. + while (anymore()) + makepage(); + lastrange->print(0, 0); // trailer + checkout(); // check that everything was printed +} + +int +main(int argc, char **argv) +{ + static FILE *fp = stdin; + setlocale(LC_CTYPE, ""); + progname = argv[0]; + while (argc > 1 && argv[1][0] == '-') { + switch (argv[1][1]) { + case 'd': + dbg = atoi(&argv[1][2]); + if (dbg == 0) + dbg = ~0; + break; + case 'm': + minfull = 0.01*atof(&argv[1][2]); + break; + case 'c': + coltol = 0.01*atof(&argv[1][2]); + break; + case 'w': + wantwarn = 1; + break; + } + argc--; + argv++; + } + if (argc <= 1) + conv(stdin); + else + while (--argc > 0) { + if (strcmp(*++argv, "-") == 0) + fp = stdin; + else if ((fp = fopen(*argv, "r")) == NULL) + FATAL("can't open %s\n", *argv); + conv(fp); + fclose(fp); + } + exit(0); +} diff --git a/mpm/page.h b/mpm/page.h new file mode 100644 index 0000000000000..21023e83b03d7 --- /dev/null +++ b/mpm/page.h @@ -0,0 +1,132 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)page.h 1.3 (gritter) 10/30/05 */ +extern queue squeue; // the three queues on which ranges reside +extern queue bfqueue; +extern queue ufqueue; + +extern double minfull; + +extern double coltol; + +int anymore(); + +// The following is used in some calls to range::enqueue(int = 0). +#define ANDBLOCK 1 + +class page; + +enum { DRAFT = 0, FINAL = 1 }; + +// The mergestream currpage->stage serves as a staging area for page makeup: +// when primed, it contains a minimal acceptable chunk of input ranges. +// The page must either take or leave everything that's on stage. +class mergestream : public queue { + page *currpage; // current page that's accepting stuff + public: + mergestream(page *cp) { currpage = cp; unblock(); } + void unblock(); + int prime(); // stage next legal chunk + void pend(); // process pending chunk on stage +}; + +// The multicol currpage->twocol is the two-column piece of the page to which +// two-column ranges are currently being added. +// The page sets htavail to indicate how tall it is allowed to become. +// All ranges on definite must be placed when the multicol is printed. +// Each of these definite ranges also resides on one of column[0] and [1], +// which represent the current best guess about how to divide definite +// between the two columns. +class multicol : public range { + page *currpage; // current page that's accepting stuff + stream definite; // definitely on page + stream scratch; // for trial compositions + stream column[2]; // left (0) and right (1) columns + int leftblocked; // OK to add to left column? + int htavail; // max possible ht, set by page::tryout() + int prevhtavail; // max 2-colht last time we added something + friend class page; +public: + multicol(page *cp) { currpage = cp; + leftblocked = 0; + htavail = 0; + prevhtavail = -1; + setgoal(NOGOAL); } + // the two-column piece behaves as part + // of the stream of single-column input. + int numcol() { return 1; } + int nonempty() { return definite.more(); } + void choosecol(range *, int);// add first arg to one or other column + void choosecol(stream*, int);// add *all ranges on first arg* + // to one or other column + // NOT the same as a mapcar of the + // preceding function over the ranges + // on the first argument! + void compose(int); // divide into two columns + void tryout(); // decide which column gets stage contents + void stretch(int); // justify both columns to given height + int print(int curv, int col); + int height(); // an upper bound on actual height + int rawht() { return max(column[0].rawht(), column[1].rawht()); } + void reheight(int *cv, int *mv) + { *cv += height(); *mv = max(*mv, *cv); } + void dump(); + int isvbox() { return nonempty(); } // during trimspace() +}; + +// These sentinel ranges are used to separate the ranges on twocol::definite +// into the chunks in which they came from the staging area. +// Thus, they preserve the results of the computation that was done to prime +// page::stage. +class sentrange : public range { + public: + sentrange() { } + int numcol() { return 2; } + int issentinel() { return 1; } +}; + +class page { + int pagesize; // allowed maximum height + int prevncol; // was last item tried 1- or 2-column? + int vsince; // how many vboxes from "current" BS + // (to avoid putting a single line on + // a page with a very large floatable) + stream definite; // definitely on page, in input order + stream scratch; // playground in which to alter page + void cmdproc(); // process any of several commands + void parmproc(); // process any of several parameters + void tryout(); // see whether current stage contents fit + void compose(int); // float and trim current page contents + void makescratch(int); // fill scratch area + void commit(); // accept the items on stage + void welsh(); // reject the items on stage + void adddef(range *r); // add to one of the definite queues + // (definite or twocol->definite) + public: + mergestream *stage; + friend class mergestream; + multicol *twocol; + friend class multicol; + page(int p) { pagesize = p; + prevncol = 1; + vsince = 0; + stage = new mergestream(this); + twocol = new multicol(this); } + ~page() { definite.freeall(); scratch.freeall(); } + void fill(); + int blank() { return !definite.more() && !twocol->definite.more();} + void print(); +}; + +// functions in page.c +extern int main(int, char **); diff --git a/mpm/queue.cc b/mpm/queue.cc new file mode 100644 index 0000000000000..b4287fff52cf5 --- /dev/null +++ b/mpm/queue.cc @@ -0,0 +1,248 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)queue.cc 1.3 (gritter) 10/30/05 */ +#include "misc.h" +#include "slug.h" +#include "range.h" +#include "page.h" + +queue squeue; +queue bfqueue; +queue ufqueue; + +// We use the stream function current() to access a queue's head. +// Thus, queue member curr should always point to its first range. +void queue::check(const char *whence) +{ + if (dbg & 8) { + const char *p; + if (this == &squeue) + p = "squeue"; + else if (this == &bfqueue) + p = "bfqueue"; + else if (this == &ufqueue) + p = "ufqueue"; + else + p = "weird queue"; + printf("#checking %s\n", p); + } + if (first != curr) + FATAL("check(%s): first != curr, line %d\n", whence, curr->rp->lineno()); +} + +// When ranges are told to enqueue themselves, they are being rejected from the +// stage back onto their original queues. +// They reset any parameters that may have been altered by staging or trial +// composition. + +void range::enqueue(int block) +{ + squeue.enqueue(this); + if (block) + squeue.block(); +} + +void ufrange::enqueue(int block) +{ + restore(); // both goal positions + ufqueue.enqueue(this); + if (block) + ufqueue.block(); +} + +void bfrange::enqueue(int block) +{ + restore(); // both goal positions + bfqueue.enqueue(this); + if (block) + bfqueue.block(); +} + +int anymore() +{ + return !(squeue.empty() && ufqueue.empty() && bfqueue.empty()); +} + +void mergestream::unblock() +{ + squeue.unblock(); + bfqueue.unblock(); + ufqueue.unblock(); +} + +// Fill the staging area with a minimal chunk of input ranges. +int mergestream::prime() +{ + if (dbg & 4) + printf("#entering mergestream::prime()\n"); + if (!empty()) + return 1; + int brkok = 1; // is it OK to break after the last + // VBOX that was added to the stage? + int needheight = -1; // minimum acceptable height of the + // chunk being constructed on stage + // If the range at the head of any queue is breaking, + // deal with it first. + if (squeue.more() && squeue.current()->breaking()) + enqueue(squeue.dequeue()); + else if (bfqueue.more() && (bfqueue.current()->breaking() || + (bfqueue.serialno() < squeue.serialno()))) + enqueue(bfqueue.dequeue()); + else if (ufqueue.more() && (ufqueue.current()->breaking() || + (ufqueue.serialno() < squeue.serialno()))) + enqueue(ufqueue.dequeue()); + else while (squeue.more()) { + // Fill the stage with enough ranges to be a valid chunk. + range *r = squeue.dequeue(); + if (r->isvbox()) { // VBOX + if (dbg & 16) + printf("#VBOX: !empty: %d; brkok: %d; vsince: %d\n", + !empty(), brkok, currpage->vsince); + if (!empty() // there's something there + && brkok + // it's OK to break here + && currpage->vsince >= 2 + // enough stream has gone onto this page + && rawht() >= needheight + // current need has been satisfied + ) { + // the stage already contains enough + // ranges, so this one can wait + r->enqueue(); + break; + } else { + if (r->rawht() > 0) { + ++currpage->vsince; + brkok = r->brkafter(); + } + enqueue(r); + } + } else if (r->isnested() || r->issp()) { // US, SP + if (!empty() && rawht() >= needheight) { + // enough already, wait + r->enqueue(); + break; + } + currpage->vsince = 0; + enqueue(r); + if (height() >= needheight) + break; + } else if (r->isneed()) { // NE + if (!empty() && rawht() >= needheight) { + // not currently working on an unsatisfied NEed + r->enqueue(); + break; + } + // deal with overlapping NEeds + needheight = rawht() + max(needheight - rawht(), r->needht()); + enqueue(r); + } else if (r->forceflush() == NO) { + enqueue(r); + } else if (r->forceflush() == YES) { + currpage->vsince = 0; + if (!empty()) { + // ready or not, r must wait + r->enqueue(); + break; + } + enqueue(r); + break; + } else + FATAL("unexpected %s[%s] in prime(), line %d\n", + r->typname(), r->headstr(), r->lineno()); + } + return more(); // 0 if nothing was staged +} + +void page::cmdproc() +{ + if (stage->next()) + FATAL("more than a single command on bsqueue\n"); + switch (stage->current()->cmdtype()) { + case FC: // freeze the current 2-column range and start a new one + adddef(stage->dequeue()); + twocol->compose(FINAL); + adddef(twocol); + twocol = new multicol(this); + break; + case BP: // force a page break + adddef(stage->dequeue()); + squeue.block(); + break; + case FL: // flush out all floatables that precede this range: + // no more stream input allowed until they're past + if (stage->serialno() > ufqueue.serialno() || + stage->serialno() > bfqueue.serialno()) { + range *r = stage->dequeue(); + r->enqueue(ANDBLOCK); + } else + adddef(stage->dequeue()); + break; + default: + stage->current()->dump(); + FATAL("unknown command\n"); + } +} + +void page::parmproc() +{ + if (stage->next()) + FATAL("more than a single parameter on bsqueue\n"); + switch (stage->current()->parmtype()) { + case NP: // page top margin + if (blank()) + pagetop = stage->current()->parm(); + pagesize = pagebot - pagetop; + break; + case FO: + if (blank()) + pagebot = stage->current()->parm(); + pagesize = pagebot - pagetop; + break; + case PL: + if (blank()) + physbot = stage->current()->parm(); + break; + case MF: + minfull = 0.01*stage->current()->parm(); + break; + case CT: + coltol = 0.01*stage->current()->parm(); + break; + case WARN: + wantwarn = stage->current()->parm(); + break; + case DBG: + dbg = stage->current()->parm(); + break; + default: + stage->current()->dump(); + FATAL("unknown parameter\n"); + } + adddef(stage->dequeue()); +} + +// Process the contents of the staging area; a relic that used to do more. +void mergestream::pend() +{ + if (dbg & 4) + printf("#entering mergestream::pend()\n"); + if (!more()) + return; + if (current()->iscmd()) + currpage->cmdproc(); + else if (current()->isparm()) + currpage->parmproc(); + else + currpage->tryout(); +} diff --git a/mpm/range.cc b/mpm/range.cc new file mode 100644 index 0000000000000..88e0e4d055d80 --- /dev/null +++ b/mpm/range.cc @@ -0,0 +1,627 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)range.cc 1.3 (gritter) 10/30/05 */ +#include <math.h> +#include "misc.h" +#include "slug.h" +#include "range.h" + +void sprange::reheight(int *cv, int *mv) +{ + if (*cv != *mv) + WARNING("slug %d: an imbedded SP, line %d\n", + first->serialno(), first->lineno()); + *cv += dv; + *mv = max(*mv, *cv); +} + +void sprange::rerawht(int *cv, int *mv) +{ + *cv += rawht(); + *mv = max(*mv, *cv); +} + +void nestrange::restore() +{ + subrange->restoreall(); +} + +void stream::freeall() // not a destructor; called explicitly +{ + strblk *p, *q; + for (p = first; p; p = q) { + q = p->next; + delete p; + } + first = last = curr = 0; +} + +void stream::dump() +{ + for (stream s = *this; s.more(); s.advance()) + s.current()->dump(); +} + +void stream::rdump() +{ + for (stream s = *this; s.more(); s.advance()) + s.current()->rdump(); +} + +int stream::restoreall() +{ + for (stream s = *this; s.more(); s.advance()) + s.current()->restore(); + return measure(this); +} + +range *stream::append(range *r) +{ + if (last == 0) + curr = first = last = new strblk; + else { + last->next = new strblk; + last = last->next; + if (curr == 0) + curr = last; + } + last->next = 0; + return last->rp = r; +} + +void stream::split() // duplicate current() range +{ + strblk *s2 = new strblk; + range *r2 = curr->rp->clone(); + s2->rp = r2; + s2->next = curr->next; + if (last == curr) + last = s2; + curr->next = s2; + curr->rp->killkids(); // children only in the 2nd one + // r2->crosslink(r1); +} + +int stream::height() +{ + stream s = *this; + int h; + for (h = 0; s.more(); s.advance()) + h += s.current()->height(); + return h; +} + +int stream::rawht() +{ + stream s = *this; + int h; + for (h = 0; s.more(); s.advance()) + h += s.current()->rawht(); + return h; +} + +int measure(stream *sp) // record high-water mark of stream +{ // sets nested stream heights + stream s = *sp; + int curv, maxv; + for (maxv = curv = 0; s.more(); s.advance()) + s.current()->reheight(&curv, &maxv); + return maxv; +} + +int rawmeasure(stream *sp) +{ + stream s = *sp; + int curv, maxv; + for (maxv = curv = 0; s.more(); s.advance()) + s.current()->rerawht(&curv, &maxv); + return maxv; +} + +void nestrange::rdump() +{ + dump(); + if (subrange) + subrange->rdump(); +} + +void nestrange::killkids() +{ + subrange = new stream; +} + +int nestrange::print(int curv, int col) +{ + int ocurv = curv; + first->slugout(col); + for (stream s = *subrange; s.more(); s.advance()) + curv = s.current()->print(curv, col); + return ocurv + height(); +} + +#define macroclone(rangetype) range *rangetype::clone() {\ + rangetype *t = new rangetype;\ + *t = *this;\ + return t; } + +macroclone(usrange); +macroclone(ufrange); +macroclone(bfrange); + +#undef macroclone + +#define macropickgoal(rangetype) void rangetype::pickgoal(int acv, double scale) {\ + if (scale > 1) {\ + goalV = (int)(scale*goalV);\ + goal2 = (int)(scale*goal2);\ + }\ + if (abs(acv - goalV) > abs(acv-goal2))\ + goalV = goal2; } + +macropickgoal(ufrange) +macropickgoal(bfrange) + +#undef macropickgoal + +range *generator::next() +{ + range *r; + if (child) { + if ((r = child->next())) + return r; + delete child; + child = 0; + } + if (!s.more()) + return 0; + r = s.current(); + if (r->isnested()) + child = new generator(r->children()); + s.advance(); + return r; +} + +range *queue::enqueue(range *r) +{ + if (dbg & 8) + printf("#entering queue::enqueue()\n"); + check("queue::enqueue"); + if (!last || last->rp->serialno() < r->serialno()) // common case + return append(r); + if (dbg & 8) + printf("#queue::enqueue() pushing back\n"); + newguy = new strblk; + newguy->rp = r; + if (r->serialno() < first->rp->serialno()) { + newguy->next = first; + curr = first = newguy; + return newguy->rp; + } + if (dbg & 8) + printf("#queue::enqueue() searching down queue\n"); + for (curr = first; + next() && next()->serialno() < r->serialno(); + curr = curr->next) + ; + newguy->next = curr->next; + curr->next = newguy; + curr = first; // restore important queue condition + return newguy->rp; +} + +range *queue::dequeue() +{ + if (dbg & 8) + printf("#entering queue::dequeue()\n"); + check("queue::dequeue"); + curr = first->next; + range *retval = first->rp; + delete first; + first = curr; + if (!curr) + last = 0; + return retval; +} + +// ================================================================================ + +// functions that munge the troff output stored in slugs[] + +// ================================================================================ + +static void doprefix(FILE *fp) // copy 1st "x" commands to output +{ + int c; + + while ((c = getc(fp)) != EOF) { + if (c != 'x') { + ungetc(c, fp); + break; + } + putchar(c); + do { + putchar(c = getc(fp)); + } while (c != '\n'); + linenum++; + } +// printf("x font 1 R\n"); // horrible kludge: ensure a font for first f1 command +} + +#define DELTASLUGS 15000 + +static slug *slugs = 0; +static int nslugs = 0; // slugs has nslugs slots +static slug *slugp = 0; // next free slug in slugs + +static void readslugs(FILE *fp) +{ + if ((slugs = (slug *) malloc((nslugs = DELTASLUGS)*sizeof(slug))) == NULL) + FATAL("no room for %d-slug array\n", nslugs); + slugp = slugs; + for (slugp = slugs; ; slugp++) { + if (slugp >= slugs+nslugs-2) { + int where = slugp - slugs; + if ((slugs = (slug *) realloc((char *) slugs, (nslugs += DELTASLUGS)*sizeof(slug))) == NULL) + FATAL("no room for %d slugs\n", nslugs); + WARNING("now slug array can hold %d slugs\n", nslugs); + slugp = slugs + where; + } + *slugp = getslug(fp); + if (slugp->type == EOF) + break; + } + *++slugp = eofslug(); + printf("# %d slugs\n", (int)(slugp-slugs)); +} + +static slug *findend(slug *sp) +{ + slug *p; + for (p = sp; p->type == sp->type; p++) // skip runs + ; // espec UF UF UF + for ( ; p < slugp; p++) + switch (p->type) { + case US: + case UF: + case BF: + case PT: + case BT: + p = findend(p); + break; + case END: + return p; + } + FATAL("walked past EOF in findend looking for %d (%s), line %d\n", + sp->type, sp->typname(), sp->lineno()); + return sp; +} + +static int markp(int i, int n, int parm) +{ // should VBOX i of n be marked to brevent breaking after it? + if (i >= n-1) + return 0; + return i <= parm-2 || i >= n-parm; +} + +static void markbreak(slug *p) +{ + // Mark impermissible breakpoints in BS's. + // The parm field of a VBOX is >0 if we shouldn't break after it. + int parm = 0; // how many lines must stay on page + int goahead = 1; // true until we see the next BS + int nowmark = 0; // true when we should be marking + int n = 0; + while (p->type == BS) + parm = p++->parm; // latest BS parm applies + slug *op = p; + while (goahead) { + switch (p->type) { + case VBOX: // count VBOXes so second pass knows + if (p->dv > 0) // knows how far to end of BS + n++; + break; + case US: // mark around EQ/EN, etc. + nowmark = 1; + p = findend(p); + break; + case UF: // but not around floats, PTs, and BTs + case BF: + case PT: + case BT: + p = findend(p); + break; + case SP: // naked SP: probable macro botch + nowmark = 1; // mark around it anyhow + break; + case BS: // beginning of next paragraph + case END: // probable macro botch + case EOF: + goahead = 0; // stop work after marking + nowmark = 1; + default: + break; + } + p++; + if (nowmark) { + int i = 0; // VBOX counter for second pass + while (op < p) { + switch (op->type) { + case VBOX: + if (op->dv > 0) + op->parm = markp(i, n, parm); + i++; + break; + case US: // caused second pass to begin + case SP: + case BS: + case END: + case EOF: + op = p; + break; + case UF: // skip on this pass too + case BF: + case PT: + case BT: + op = findend(op); + break; + default: + break; + } + op++; + } + if (i != n) + WARNING("markbreak failed : i %d n %d\n", i, n); + op = p; + nowmark = n = 0; + } + } +} + +static void fixslugs() // adjust bases and dv's, set parameters, etc. +{ + slug *prevV = 0, *p; + for (p = slugs; p < slugp; p++) { + if (p->type == VBOX) { + prevV = p; + continue; + } + if (p->base != 0) { + WARNING("%s slug (type %d) has base = %d, line %d\n", + p->typname(), p->type, p->base, p->lineno()); + } + if ((p->type == SP) || (p->type == NE)) + continue; + if (p->type == PAGE) + prevV = 0; + if (p->dv != 0) + { + if (prevV) { + prevV->base = max(prevV->base, p->dv); + p->dv = 0; + } else { + WARNING("s slug (type %d) has dv = %d, line %d\n", + p->typname(), p->type, p->dv, p->lineno()); + } + } + } + prevV = 0; + int firstNP = 0, firstFO = 0, firstPL = 0; + for (p = slugs; p < slugp; p++) { + switch (p->type) { + // adjust the dv in a sequence of VBOXes + // by subtracting from each the base of the preceding VBOX + case VBOX: + if (prevV) + p->dv -= prevV->base; + prevV = p; + break; + case SP: + p->dv = max(p->dv, 0); + break; + case PAGE: + p->neutralize(); + prevV = 0; + break; + // record only first "declarations" of Page Top and bottom (FO); + case PARM: + switch (p->parm) { + case NP: + if (firstNP++ == 0) + pagetop = p->parm2; + p->neutralize(); + break; + case FO: + if (firstFO++ == 0) + pagebot = p->parm2; + p->neutralize(); + break; + case PL: + if (firstPL++ == 0) + physbot = p->parm2; + p->neutralize(); + break; + } + break; + // things that begin groups; not US, which should nest properly + case UF: + case BF: + while ((p+1)->type == p->type) { + // join adjacent identical + (p+1)->parm2 = p->parm; // parm is latest + // parm2 is previous + p->neutralize(); // so it's not seen later + p++; + } + break; + // none of the above + case US: + case PT: + case BT: + case BS: + case END: + case TM: + case COORD: + case NE: + case MC: + case CMD: + case EOF: + break; + default: + WARNING("Unknown slug type %d in fixslugs, line %d\n", + p->type, p->lineno()); + break; + } + } + int pagesize = pagebot - pagetop; + if (pagesize == 0) + FATAL("Page dimensions not declared\n"); + if (physbot == 0) + physbot = pagebot + pagetop; + printf("# page top %d bot %d size %d physbot %d\n", + pagetop, pagebot, pagesize, physbot); + for (p = slugs; p < slugp; p++) { + switch (p->type) { + // normalize float parameters + case BF: + case UF: + // primary goal + p->parm = max(min(p->parm-pagetop, pagesize), 0); + // secondary goal + p->parm2 = max(min(p->parm2-pagetop, pagesize), 0); + break; + // normalize need parameters + case NE: + p->dv = max( min(p->dv, pagesize), 0); + break; + // mark permissible breaks + case BS: + markbreak(p); + break; + } + if (dbg & 1) + p->dump(); + } +} + +void checkout() +{ + for (slug *p = slugs; p < slugp; p++) + switch (p->type) { + case PT: + case BT: + p = findend(p); + break; + case SP: + case VBOX: + if (p->seen != 1) + WARNING("%s slug %d seen %d times\n", + p->typname(), p->serialno(), + p->seen); + break; + } +} + +eofrange *lastrange; +stream ptlist, btlist; + +static slug *makeranges(slug *p, stream *s, int level) +{ + stream *t; + + for ( ; p < slugp; p++) + switch (p->type) { + case VBOX: + s->append(new vboxrange(p)); + break; + case SP: + s->append(new sprange(p)); + break; + case BS: + s->append(new bsrange(p)); + break; + case US: + s->append(new usrange(p, t = new stream)); + p = makeranges(p+1, t, level+1); + break; + case BF: + s->append(new bfrange(p, t = new stream)); + p = makeranges(p+1, t, level+1); + break; + case UF: + s->append(new ufrange(p, t = new stream)); + p = makeranges(p+1, t, level+1); + break; + case PT: + ptlist.append(new ptrange(p, t = new stream)); + p = makeranges(p+1, t, level+1); + break; + case BT: + btlist.append(new btrange(p, t = new stream)); + p = makeranges(p+1, t, level+1); + break; + case END: + s->append(new endrange(p)); + return p; + case TM: + s->append(new tmrange(p)); + break; + case COORD: + s->append(new coordrange(p)); + break; + case NE: + if (level) { + WARNING("Nested NE commands are ignored, line %d\n", + p->lineno()); + p->dv = 0; + } + s->append(new nerange(p)); + break; + case MC: + s->append(new mcrange(p)); + break; + case CMD: + if (level) + WARNING("Nested command ignored, line %d\n", + p->lineno()); + s->append(new cmdrange(p)); + break; + case PARM: + if (level) + WARNING("Nested parameter ignored, line %d\n", + p->lineno()); + s->append(new parmrange(p)); + break; + case EOF: + lastrange = new eofrange(p); + return 0; + } + return p; +} + +static queue text; // unexamined input ranges; the real data + +void startup(FILE *fp) +{ + doprefix(fp); // peel off 'x' commands + readslugs(fp); // read everything into slugs[] + fixslugs(); // measure parameters and clean up + makeranges(slugs, &text, 0); // add range superstructure + measure(&text); // heights of nested things + rawmeasure(&text); + while (text.more()) { + range *r = text.dequeue(); + if (dbg & 2) + r->dump(); + r->enqueue(); + } +} diff --git a/mpm/range.h b/mpm/range.h new file mode 100644 index 0000000000000..c3f4cfac5fe9e --- /dev/null +++ b/mpm/range.h @@ -0,0 +1,348 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)range.h 1.3 (gritter) 10/30/05 */ +const int NOGOAL = -1; + +class stream; + +enum primeflush { NO, YES, EXPECTED, UNEXPECTED }; // mergestream::prime() + +// Ranges do two things. They interpose a layer between slugs and the rest +// of the program; this is important because of the grossness of the slug +// data structure (made necessary by its origins in troff output). Ranges also +// group together other ranges into meaningful chunks like unbreakable stream +// objects, floatable objects, and page headers and footers. +// Member function height() returns a range's height as of the latest composition. +// Member function rawht() returns the range's original height in the input. +class range { + protected: + slug *first; // earliest slug in range + int accumV; // accumulated V to this point + public: + range() { first = 0; accumV = 0; } + range(slug *p) { first = p; accumV = 0; } + char *headstr() { + return first ? first->headstr() : (char *)""; } + char *typname() { return first->typname(); } + int serialno() { return first->serialno(); } + int lineno() { return first->lineno(); } + virtual void dump() { first->dump(); } + virtual void rdump() { dump(); } + virtual int print(int cv, int col) { + first->slugout(col); return cv; } + virtual int floatable() { return 0; } + virtual int brkafter() { return 1; } + virtual int isnested() { return 0; } + virtual int issp() { return 0; } + virtual int isvbox() { return 0; } + virtual int isneed() { return 0; } + virtual int iscmd() { return 0; } + virtual int cmdtype() { return -1; } + virtual int isparm() { return 0; } + virtual int parmtype() { return -1; } + virtual int parm() { return -1; } + virtual int breakable() { return 0; } + virtual int forceflush() { return UNEXPECTED; } + virtual int pn() { return 0; } + virtual stream *children() { return 0; } // see page::peeloff() + virtual void killkids() { } + virtual void enqueue(int = 0); + virtual int height() { return 0; } + virtual int rawht() { return 0; } + virtual int needht() { return 0; } + virtual void reheight(int *, int *) { } + virtual void rerawht(int *, int *) { } + virtual void setheight(int) { } + virtual void restore() { } // goals of floatables + virtual int goal() { return NOGOAL; } + int accum() { return accumV; } + void setaccum(int n) { accumV = n; } + virtual void setgoal(int) { } + virtual void pickgoal(int, double) { } + virtual int numcol() { return first->numcol(); } + virtual int issentinel() { return 0; } + virtual range *clone() { return 0; } + virtual int breaking() { return 0; } + virtual void setbreaking() { } +}; + +class vboxrange : public range { + int dv; // inherited from slug + int base; // inherited from slug + int brk; // 0 => ok to break after, 1 => no break + public: + vboxrange(slug *p) : range(p) { dv = p->dv; base = p->base; brk = p->parm; } + void dump() { + printf("#### VBOX brk? %d dv %d ht %d\n", brk, dv, dv+base); } + int print(int cv, int col) { + printf("V%d\n", cv += dv); first->slugout(col); return cv+base; } + int brkafter() { return !brk; } + int isvbox() { return 1; } + int forceflush() { return NO; } + int height() { return dv + base; } + int rawht() { return first->dv + first->base; } + void reheight(int *cv, int *mv) { + *cv += dv+base; *mv = max(*mv, *cv); } + void rerawht(int *cv, int *mv) { + *cv += rawht(); *mv = max(*mv, *cv); } +}; + +class sprange : public range { + int dv; + public: + sprange(slug *p) : range(p) { dv = first->dv; } + void dump() { + printf("#### SP dv %d (originally %d)\n", dv, first->dv); } + int print(int cv, int col) { + first->slugout(col); return cv + dv; } + int issp() { return 1; } + int forceflush() { return YES; } + int height() { return dv; } + int rawht() { return first->dv; } + void reheight(int *, int *); + void rerawht(int *, int *); + void setheight(int n) { dv = n; } +}; + +class tmrange : public range { + public: + tmrange(slug *p) : range(p) { } + int forceflush() { return NO; } + int print(int cv, int col) { first->slugout(col); return cv; } +}; + +class coordrange : public range { + public: + coordrange(slug *p) : range(p) { } + int forceflush() { return NO; } + int print(int cv, int col) + { first->slugout(col); printf(" Y %d\n", cv); return cv; } +}; + +class nerange : public range { + public: + nerange(slug *p) : range(p) { } + int isneed() { return 1; } + int forceflush() { return YES; } + int needht() { return first->dv; } +}; + +class mcrange : public range { + public: + mcrange(slug *p) : range(p) { } + int forceflush() { return YES; } +}; + +class cmdrange : public range { + public: + cmdrange(slug *p) : range(p) { } + int iscmd() { return 1; } + int forceflush() { return YES; } + int cmdtype() { return first->parm; } +}; + +class parmrange : public range { + public: + parmrange(slug *p) : range(p) { } + int isparm() { return 1; } + int forceflush() { return YES; } + int parmtype() { return first->parm; } + int parm() { return first->parm2; } +}; + +class bsrange : public range { + public: + bsrange(slug *p) : range(p) { } + int forceflush() { return NO; } + int print(int cv, int col) { first->slugout(col); return cv; } +}; + +class endrange : public range { + public: + endrange(slug *p) : range(p) { } + int forceflush() { return UNEXPECTED; } +}; + +class eofrange : public range { + public: + eofrange(slug *p) : range(p) { } + int forceflush() { return UNEXPECTED; } +}; + +extern eofrange *lastrange; // the EOF block (trailer, etc.) goes here + +int measure(stream *); +int rawmeasure(stream *); + +// A nestrange packages together a sequence of ranges, its subrange. +// Other parts of the program reach in and alter the dimensions of +// some of these ranges, so when the height of a range is requested +// it is computed completely afresh. +// (Note: the alternative, of keeping around many copies of ranges +// with different dimensions, was abandoned because of the difficulty +// of ensuring that exactly one copy of each original range would be +// output.) +class nestrange : public range { + protected: + stream *subrange; + int isbreaking; + int rawdv; + public: + nestrange() : range() { subrange = 0; isbreaking = 0; rawdv = -1; } + nestrange(slug *p, stream *s) : range(p) + { subrange = s; isbreaking = 0; rawdv = -1; } + void rdump(); + virtual void restore(); + stream *children() { return subrange; } + void killkids(); + int height() { return measure(subrange); } + int rawht() { if (rawdv < 0 || isbreaking) rawdv = rawmeasure(subrange); + return rawdv; } + void reheight(int *cv, int *mv) { + *mv += measure(subrange); *cv = max(*mv, *cv); } + void rerawht(int *cv, int *mv) { + *mv += rawht(); *cv = max(*mv, *cv); } + int isnested() { return 1; } + int forceflush() { return EXPECTED; } + int print(int cv, int col); + int breaking() { return isbreaking; } + void setbreaking() { isbreaking++; } +}; + +class usrange : public nestrange { + public: + usrange() { } + usrange(slug *p, stream *s) : nestrange(p, s) {} + void dump() { printf("#### US dv %d\n", height()); } + range *clone(); +}; + +class ufrange : public nestrange { + int goalV, goal2; + public: + ufrange() { } + ufrange(slug *p, stream *s) : nestrange(p, s) { + goalV = p->parm; goal2 = p->parm2; } + void dump() { printf("#### UF dv %d goal %d goal2 %d\n", + height(), goalV, goal2); } + int floatable() { return 1; } + void enqueue(int = 0); + range *clone(); + int goal() { return goalV; } + void setgoal(int n) { goalV = goal2 = n; } + void pickgoal(int acv, double scale); + void restore() { goalV = first->parm; goal2 = first->ht; } +}; + +class bfrange : public nestrange { + int goalV, goal2; + public: + bfrange() { } + bfrange(slug *p, stream *s) : nestrange(p, s) { + goalV = p->parm; goal2 = p->parm2; } + void dump() { printf("#### BF dv %d goal %d goal2 %d\n", + height(), goalV, goal2); } + int floatable() { return 1; } + void enqueue(int = 0); + range *clone(); + int goal() { return goalV; } + void setgoal(int n) { goalV = goal2 = n; } + void pickgoal(int acv, double scale); + void restore() { goalV = first->parm; goal2 = first->parm2; } + int breakable() { return 1; } // can be broken +}; + +class ptrange : public nestrange { + int pgno; + public: + int pn() { return pgno; } + ptrange(slug *p, stream *s) : nestrange(p, s) { pgno = p->parm; } + void dump() { printf("#### PT pgno %d dv %d\n", pgno, height()); } +}; + +class btrange : public nestrange { + int pgno; + public: + btrange(slug *p, stream *s) : nestrange(p, s) { pgno = p->parm; } + void dump() { printf("#### BT pgno %d dv %d\n", pgno, height()); } +}; + +// A stream is a sequence of ranges; we use this data structure a lot +// to traverse various sequences that crop up in page-making. +class stream { + protected: +public: + struct strblk { // ranges are linked by these blocks + strblk *next; + range *rp; + }; + strblk *first; + strblk *last; + strblk *curr; + public: + stream() { curr = last = first = 0; } + stream(range *r) { curr = last = first = new strblk; + last->rp = r; last->next = 0; } + void freeall(); // note: not a destructor + void dump(); // top level + void rdump(); // recursive + int restoreall(); + range *current() { return curr->rp; } + range *next() { return curr && curr->next ? curr->next->rp : 0; } + void advance() { curr = curr->next; } + range *append(range *r); + void split(); + int more() { return curr && curr->rp; } + int height(); + int rawht(); +}; + +// A generator iterates through all the ranges of a stream +// (not just the root ranges of nestranges). +class generator { + stream s; + generator *child; + public: + generator() { child = 0; } + generator(stream *sp) { s = *sp; child = 0; } + range *next(); +}; + +extern stream ptlist, btlist; // page titles + +#undef INFINITY +#define INFINITY 1000001 + +// A queue is a distinguished kind of stream. +// It keeps its contents in order by the serial numbers of the ranges. +// A queue can be blocked from dequeuing something to indicate +// that it's not worth considering the queue again on a given page. +class queue : public stream { + strblk *newguy; + protected: + int blocked; + void check(const char *); + public: + queue() : blocked(0) { } + range *enqueue(range *r); + range *dequeue(); + void block() { blocked = 1; } + void unblock() { blocked = 0; } + int more() { return !blocked && stream::more(); } + int empty() { return !stream::more(); } + int serialno() { return empty() ? INFINITY : current()->serialno(); } +}; + +// functions in range.c +void checkout(); +void startup(FILE *); diff --git a/mpm/slug.cc b/mpm/slug.cc new file mode 100644 index 0000000000000..d5b56045bc880 --- /dev/null +++ b/mpm/slug.cc @@ -0,0 +1,642 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)slug.cc 1.7 (gritter) 7/29/06 */ +#include "misc.h" +#include "slug.h" +#include <math.h> + +static char *bufptr(int); + +void slug::coalesce() +{ + (this+1)->dp = dp; // pretty grimy, but meant to ensure + // that all output goes out. + // maybe it has to skip over PT's; + // some stuff is getting pushed inside PT..END +} + +void slug::neutralize() +{ + switch (type) { + case PAGE: + case UF: + case BF: + case PARM: + type = NEUTRAL; + coalesce(); + break; + default: + WARNING("neutralized %d (%s) with %s\n", + type, typname(), headstr()); + break; + } +} + +void slug::dump() // print contents of a slug +{ + printf("# %d %-4.4s parm %d dv %d base %d s%g f%d H%d\n#\t\t%s\n", + serialno(), typname(), parm, dv, base, + size, font, hpos, headstr()); +} + +char *slug::headstr() +{ + const int HEADLEN = 4096; + static char buf[2*HEADLEN]; + int j = 0; + char *s = bufptr(dp); + int n = (this+1)->dp - dp; + if (n >= HEADLEN) + n = HEADLEN; + for (int i = 0; i < n; i++) + switch (s[i]) { + case '\n': + case '\t': + case '\0': + case ' ': + break; + default: + buf[j++] = s[i]; + break; + } + buf[j] = 0; + return buf; +} + +static char *strindex(char s[], const char t[]) // index of earliest t[] in s[] +{ + for (int i = 0; s[i] != '\0'; i++) { + int j, k; + for (j = i, k = 0; t[k]!='\0' && s[j] == t[k]; j++, k++) + ; + if (k > 0 && t[k] == '\0') + return s+i; + } + return 0; +} + +void slug::slugout(int col) +{ + static int numout = 0; + if (seen++) + WARNING("%s slug #%d seen %d times [%s]\n", + typname(), serialno(), seen, headstr()); + if (type == TM) { + char *p; + if ((p = strindex(bufptr(dp), "x X TM "))) + p += strlen("x X TM "); // skip junk + else + FATAL("strange TM [%s]\n", headstr()); + fprintf(stderr, "%d\t", userpn); // page # as prefix + for ( ; p < bufptr((this+1)->dp); p++) + putc(*p, stderr); + } else if (type == COORD) { + for (char *p = bufptr(dp); p < bufptr((this+1)->dp) && *p != '\n'; p++) + putc(*p, stdout); + printf(" # P %d X %d", userpn, hpos + col*offset); + return; + } else if (type == VBOX) { + if (numout++ > 0) { // BUG??? might miss something + if (size == (int)size) + printf("s%d\n", (int)size); + else + printf("s-23 %g\n", size); + printf("f%d\n", font); + } + printf("H%d\n", hpos + col*offset); + } + fwrite(bufptr(dp), sizeof(char), (this+1)->dp - dp, stdout); +} + +char *slug::typname() +{ + static char buf[50]; + const char *p = buf; // return value + switch(type) { + case EOF: p = "EOF"; break; + case VBOX: p = "VBOX"; break; + case SP: p = "SP"; break; + case BS: p = "BS"; break; + case US: p = "US"; break; + case BF: p = "BF"; break; + case UF: p = "UF"; break; + case PT: p = "PT"; break; + case BT: p = "BT"; break; + case END: p = "END"; break; + case NEUTRAL: p = "NEUT"; break; + case PAGE: p = "PAGE"; break; + case TM: p = "TM"; break; + case COORD: p = "COORD"; break; + case NE: p = "NE"; break; + case CMD: p = "CMD"; break; + case PARM: p = "PARM"; break; + default: snprintf(buf, sizeof(buf), "weird type %d", type); + } + return (char *)p; +} + +// ================================================================================ + +// troff output-specific functions + +// ================================================================================ + +const int DELTABUF = 500000; // grow the input buffer in chunks + +static char *inbuf = 0; // raw text input collects here +static int ninbuf = 0; // byte count for inbuf +static char *inbp = 0; // next free slot in inbuf +int linenum = 0; // input line number + +static inline void addc(int c) { *inbp++ = c; } + +static void adds(char *s) +{ + for (char *p = s; *p; p++) + addc(*p); +} + +static char *getutf(FILE *fp) // get 1 utf-encoded char (might be multiple bytes) +{ + static char buf[100]; + char *p = buf; + + for (*p = 0; (*p++ = getc(fp)) != EOF; ) { + *p = 0; +#ifdef EUC + if (mblen(buf, sizeof buf) > 0) // found a valid character +#endif + break; + } + return buf; +} + +static char *bufptr(int n) { return inbuf + n; } // scope of inbuf is too local + +static inline int wherebuf() { return inbp - inbuf; } + +static char *getstr(char *p, char *temp) +{ // copy next non-blank string from p to temp, update p + while (*p == ' ' || *p == '\t' || *p == '\n') + p++; + if (*p == '\0') { + temp[0] = 0; + return(NULL); + } + while (*p != ' ' && *p != '\t' && *p != '\n' && *p != '\0') + *temp++ = *p++; + *temp = '\0'; + return(p); +} + +/*************************************************************************** + bounding box of a circular arc Eric Grosse 24 May 84 + +Conceptually, this routine generates a list consisting of the start, +end, and whichever north, east, south, and west points lie on the arc. +The bounding box is then the range of this list. + list = {start,end} + j = quadrant(start) + k = quadrant(end) + if( j==k && long way 'round ) append north,west,south,east + else + while( j != k ) + append center+radius*[j-th of north,west,south,east unit vectors] + j += 1 (mod 4) + return( bounding box of list ) +The following code implements this, with simple optimizations. +***********************************************************************/ + +static int quadrant(double x, double y) +{ + if ( x>=0.0 && y> 0.0) return(1); + else if( x< 0.0 && y>=0.0) return(2); + else if( x<=0.0 && y< 0.0) return(3); + else if( x> 0.0 && y<=0.0) return(4); + else return 0; /* shut up lint */ +} + +static double xmin, ymin, xmax, ymax; // used by getDy + +static void arc_extreme(double x0, double y0, double x1, double y1, double xc, double yc) + /* start, end, center */ +{ /* assumes center isn't too far out */ + double r; + int j, k; + printf("#start %g,%g, end %g,%g, ctr %g,%g\n", x0,y0, x1,y1, xc,yc); + y0 = -y0; y1 = -y1; yc = -yc; // troff's up is eric's down + x0 -= xc; y0 -= yc; /* move to center */ + x1 -= xc; y1 -= yc; + xmin = (x0<x1)?x0:x1; ymin = (y0<y1)?y0:y1; + xmax = (x0>x1)?x0:x1; ymax = (y0>y1)?y0:y1; + r = sqrt(x0*x0 + y0*y0); + if (r > 0.0) { + j = quadrant(x0,y0); + k = quadrant(x1,y1); + if (j == k && y1*x0 < x1*y0) { + /* viewed as complex numbers, if Im(z1/z0)<0, arc is big */ + if( xmin > -r) xmin = -r; if( ymin > -r) ymin = -r; + if( xmax < r) xmax = r; if( ymax < r) ymax = r; + } else { + while (j != k) { + switch (j) { + case 1: if( ymax < r) ymax = r; break; /* north */ + case 2: if( xmin > -r) xmin = -r; break; /* west */ + case 3: if( ymin > -r) ymin = -r; break; /* south */ + case 4: if( xmax < r) xmax = r; break; /* east */ + } + j = j%4 + 1; + } + } + } + xmin += xc; ymin += yc; ymin = -ymin; + xmax += xc; ymax += yc; ymax = -ymax; +} + + +static int getDy(char *p, int *dx, int *maxv) + // figure out where we are after a D'...' +{ + int x, y, x1, y1; // for input values + char temp[50]; + p++; // get to command letter + switch (*p++) { + case 'l': // line + sscanf(p, "%d %d", dx, &y); + return *maxv = y; + case 'a': // arc + sscanf(p, "%d %d %d %d", &x, &y, &x1, &y1); + *dx = x1 - x; + arc_extreme(0, 0, x+x1, y+y1, x, y); // sets [xy][max|min] + printf("#arc bounds x %g, %g; y %g, %g\n", + xmin, xmax, ymin, ymax); + *maxv = (int) (ymin+0.5); + return y + y1; + case '~': // spline + for (*dx = *maxv = y = 0; (p=getstr(p, temp)) != NULL; ) { + // above getstr() gets x value + *dx += atoi(temp); + p = getstr(p, temp); // this one gets y value + y += atoi(temp); + *maxv = max(*maxv, y); // ok??? + if (*p == '\n' || *p == 0) // input is a single line; + break; // don't walk off end if realloc + } + return y; + case 'c': // circle, ellipse + sscanf(p, "%d", dx); + *maxv = *dx/2; // high water mark is ht/2 + return 0; + case 'e': + sscanf(p, "%d %d", dx, &y); + *maxv = y/2; // high water mark is ht/2 + return 0; + default: // weird stuff + return 0; + } +} + +static int serialnum = 0; + +slug eofslug() +{ + slug ret; + ret.serialnum = serialnum; + ret.type = EOF; + ret.dp = wherebuf(); + return ret; +} + +slug getslug(FILE *fp) +{ + if (inbuf == NULL) { + if ((inbuf = (char *) malloc(ninbuf = DELTABUF)) == NULL) + FATAL("no room for %d character input buffer\n", ninbuf); + inbp = inbuf; + } + if (wherebuf() > ninbuf-5000) { + // this is still flaky -- lines can be very long + int where = wherebuf(); // where we were + if ((inbuf = (char *) realloc(inbuf, ninbuf += DELTABUF)) == NULL) + FATAL("no room for %d character input buffer\n", ninbuf); + WARNING("grew input buffer to %d characters\n", ninbuf); + inbp = inbuf + where; // same offset in new array + } + static int baseV = 0; // first V command of preceding slug + static int curV = 0, curH = 0; + static int font = 0; + static float size = 0; + static int baseadj = 0; + static int ncol = 1, offset = 0; // multi-column stuff + char str[4096], str2[4096], buf[4096], *p; + int firstV = 0, firstH = 0; + int maxV = curV; + int ocurV = curV, mxv = 0, dx = 0; + int sawD = 0; // > 0 if have seen D... + slug ret; + ret.serialnum = serialnum++; + ret.type = VBOX; // use the same as last by default + ret.dv = curV - baseV; + ret.hpos = curH; + ret.base = ret.parm = ret.parm2 = ret.seen = 0; + ret.font = font; + ret.size = size; + ret.dp = wherebuf(); + ret.ncol = ncol; + ret.offset = offset; + ret.linenum = linenum; // might be low + + for (;;) { + int c, m, n; // for input values + int sign; // hoisted from case 'h' below + switch (c = getc(fp)) { + case EOF: + ret.type = EOF; + ret.dv = 0; + if (baseadj) + printf("# adjusted %d bases\n", baseadj); + printf("# %d characters, %d lines\n", wherebuf(), linenum); + return ret; + case 'V': + fscanf(fp, "%d", &n); + if (firstV++ == 0) { + ret.dv = n - baseV; + baseV = n; + } else { + snprintf(buf, sizeof(buf), "v%d", n - curV); + adds(buf); + } + curV = n; + maxV = max(maxV, curV); + break; + case 'H': // absolute H motion + fscanf(fp, "%d", &n); + if (firstH++ == 0) { + ret.hpos = n; + } else { + snprintf(buf, sizeof(buf), "h%d", n - curH); + adds(buf); + } + curH = n; + break; + case 'h': // relative H motion + addc(c); + sign = 1; + if ((c = getc(fp)) == '-') { + addc(c); + sign = -1; + c = getc(fp); + } + for (n = 0; isdigit(c); c = getc(fp)) { + addc(c); + n = 10 * n + c - '0'; + } + curH += n * sign; + ungetc(c, fp); + break; + case 'x': // device control: x ... + addc(c); + fgets(buf, (int) sizeof(buf), fp); + linenum++; + adds(buf); + if (buf[0] == ' ' && buf[1] == 'X') { // x X ... + if (2 != sscanf(buf+2, "%s %d", str, &n)) + n = 0; + if (eq(str, "SP")) { // X SP n + ret.type = SP; // paddable SPace + ret.dv = n; // of height n + } else if (eq(str, "BS")) { + ret.type = BS; // Breakable Stream + ret.parm = n; // >=n VBOXES on a page + } else if (eq(str, "BF")) { + ret.type = BF; // Breakable Float + ret.parm = ret.parm2 = n; + // n = pref center (as UF) + } else if (eq(str, "US")) { + ret.type = US; // Unbreakable Stream + ret.parm = n; + } else if (eq(str, "UF")) { + ret.type = UF; // Unbreakable Float + ret.parm = ret.parm2 = n; + // n = preferred center + // to select several, + // use several UF lines + } else if (eq(str, "PT")) { + ret.type = PT; // Page Title + ret.parm = n; + } else if (eq(str, "BT")) { + ret.type = BT; // Bottom Title + ret.parm = n; + } else if (eq(str, "END")) { + ret.type = END; + ret.parm = n; + } else if (eq(str, "TM")) { + ret.type = TM; // Terminal Message + ret.dv = 0; + } else if (eq(str, "COORD")) { + ret.type = COORD;// page COORDinates + ret.dv = 0; + } else if (eq(str, "NE")) { + ret.type = NE; // NEed to break page + ret.dv = n; // if <n units left + } else if (eq(str, "MC")) { + ret.type = MC; // Multiple Columns + sscanf(buf+2, "%s %d %d", + str, &ncol, &offset); + ret.ncol = ncol; + ret.offset = offset; + } else if (eq(str, "CMD")) { + ret.type = CMD; // CoMmaNd + sscanf(buf+2, "%s %s", str2, str); + if (eq(str, "FC")) // Freeze 2-Col + ret.parm = FC; + else if (eq(str, "FL")) // FLush + ret.parm = FL; + else if (eq(str, "BP")) // Break Page + ret.parm = BP; + else WARNING("unknown command %s\n", + str); + } else if (eq(str, "PARM")) { + ret.type = PARM;// PARaMeter + sscanf(buf+2, "%s %s %d", str2, str, &ret.parm2); + if (eq(str, "NP")) // New Page + ret.parm = NP; + else if (eq(str, "FO")) // FOoter + ret.parm = FO; + else if (eq(str, "PL")) // Page Length + ret.parm = PL; + else if (eq(str, "MF")) // MinFull + ret.parm = MF; + else if (eq(str, "CT")) // ColTol + ret.parm = CT; + else if (eq(str, "WARN")) //WARNings? + ret.parm = WARN; + else if (eq(str, "DBG"))// DeBuG + ret.parm = DBG; + else WARNING("unknown parameter %s\n", + str); + } else + break; // out of switch + if (firstV > 0) + WARNING("weird x X %s in mid-VBOX\n", + str); + for (;;) { + c = getc(fp); + ungetc(c, fp); + if (c != '+') + break; + fgets(buf, (int) sizeof(buf), fp); + linenum++; + adds(buf); + } + return ret; + } + break; + case 'n': // end of line + fscanf(fp, "%d %d", &n, &m); + ret.ht = n; + ret.base = m; + getc(fp); // newline + linenum++; + snprintf(buf, sizeof(buf), "n%d %d\n", ret.ht, + ret.base); + adds(buf); + if (!firstV++) + baseV = curV; + // older incarnations of this program used ret.base + // in complicated and unreliable ways; + // example: if ret.ht + ret.base < ret.dv, ret.base = 0 + // this was meant to avoid double-counting the space + // around displayed equations; it didn't work + // Now, we believe ret.base = 0, otherwise we give it + // a value we have computed. + if (ret.base == 0 && sawD == 0) + return ret; // don't fiddle 0-bases + if (ret.base != maxV - baseV) { + ret.base = maxV - baseV; + baseadj++; + } + if (ret.type != VBOX) + WARNING("%s slug (type %d) has base = %d\n", + ret.typname(), ret.type, ret.base); + return ret; + case 'p': // new page + fscanf(fp, "%d", &n); + ret.type = PAGE; + curV = baseV = ret.dv = 0; + ret.parm = n; // just in case someone needs it + return ret; + case 's': { // size change snnn + int isize; + fscanf(fp, "%d", &isize); + if (isize == -23) { + fscanf(fp, "%f", &size); + snprintf(buf, sizeof(buf), + "s-23 %g\n", size); + } else { + size = isize; + snprintf(buf, sizeof(buf), + "s%d\n", isize); + } + adds(buf); + } + break; + case 'f': // font fnnn + fscanf(fp, "%d", &font); + snprintf(buf, sizeof(buf), "f%d\n", font); + adds(buf); + break; + case '\n': + linenum++; + /* fall through */ + case ' ': + addc(c); + break; + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + // two motion digits plus a character + addc(c); + n = c - '0'; + addc(c = getc(fp)); + curH += 10 * n + c - '0'; + adds(getutf(fp)); + if (!firstV++) + baseV = curV; + break; + case 'c': // single ascii character + addc(c); + adds(getutf(fp)); + if (!firstV++) + baseV = curV; + break; + case 'C': // Cxyz\n + case 'N': // Nnnn\n + addc(c); + while ((c = getc(fp)) != ' ' && c != '\n') + addc(c); + addc(c); + if (!firstV++) + baseV = curV; + linenum++; + break; + case 'D': // draw function: D.*\n + sawD++; + p = bufptr(wherebuf()); // where does the D start + addc(c); + while ((c = getc(fp)) != '\n') + addc(c); + addc(c); + if (!firstV++) + baseV = curV; + ocurV = curV, mxv = 0, dx = 0; + curV += getDy(p, &dx, &mxv); // figure out how big it is + maxV = max(max(maxV, curV), ocurV+mxv); + curH += dx; + linenum++; + break; + case 'v': // relative vertical vnnn + addc(c); + if (!firstV++) + baseV = curV; + sign = 1; + if ((c = getc(fp)) == '-') { + addc(c); + sign = -1; + c = getc(fp); + } + for (n = 0; isdigit(c); c = getc(fp)) { + addc(c); + n = 10 * n + c - '0'; + } + ungetc(c, fp); + curV += n * sign; + maxV = max(maxV, curV); + addc('\n'); + break; + case 'w': // word space + addc(c); + break; + case '#': // comment + addc(c); + while ((c = getc(fp)) != '\n') + addc(c); + addc('\n'); + linenum++; + break; + default: + WARNING("unknown input character %o %c (%50.50s)\n", + c, c, bufptr(wherebuf()-50)); + break; + } + } +} diff --git a/mpm/slug.h b/mpm/slug.h new file mode 100644 index 0000000000000..4dc5b76109ffd --- /dev/null +++ b/mpm/slug.h @@ -0,0 +1,87 @@ +/* + * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005. + * + * Derived from Plan 9 source code published at the 9fans list by Rob Pike, + * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html> + * + * Copyright (C) 2003, Lucent Technologies Inc. and others. + * All Rights Reserved. + * + * Distributed under the terms of the Lucent Public License Version 1.02. + */ + +/* Sccsid @(#)slug.h 1.5 (gritter) 10/31/05 */ +enum slugtypes { + NONE, // can't happen + VBOX, // Vertical Box -- printable stuff + SP, // paddable SPace + BS, // start Breakable Stream + US, // start Unbreakable Stream + BF, // start Breakable Float + UF, // start Unbreakable Float + PT, // start Page Top material (header) + BT, // start page BoTtom material (footer) + END, // ENDs of groups + NEUTRAL, // NEUTRALized slugs can do no harm (cf. CIA) + PAGE, // beginning of PAGE in troff input + TM, // Terminal Message to appear during output + COORD, // output page COORDinates + NE, // NEed command + MC, // Multiple-Column command + CMD, // misc CoMmanDs: FC, FL, BP + PARM, // misc PARaMeters: NP, FO + LASTTYPE // can't happen either +}; + +enum cmdtypes { + FC, // Freeze 2-Column material + FL, // FLush all floats before reading more stream + BP // Break Page +}; + +enum parmtypes { + NP, // distance of top margin from page top (New Page) + FO, // distance of bottom margin from page top (FOoter) + PL, // distance of physical page bottom from page top (Page Length) + MF, // minimum fullness required for padding + CT, // tolerance for division into two columns + WARN, // warnings to stderr? + DBG // debugging flag +}; + +class slug { + int serialnum; + int dp; // offset of data for this slug in inbuf + int linenum; // input line number (approx) for this slug + int font; // font in effect at slug beginning + float size; // size in effect at slug beginning + int seen; // 0 until output + int ncol; // number of columns (1 or 2) + int offset; // horizontal offset for 2 columns + public: + int type; // VBOX, PP, etc. + int parm; // parameter + int base; // "depth" of this slug (from n command) + int hpos; // abs horizontal position + int dv; // height of this slug above its input Vpos + union { + int ht; // "height" of this slug (from n command) + int parm2; // second parameter, since only VBOXes have ht + }; + friend slug getslug(FILE *); + friend void checkout(); + friend slug eofslug(); + void coalesce(); // with next slug in array slugs[] + void neutralize(); // render this one a no-op + void dump(); // dump its contents for debugging + char *headstr(); // string value of text + void slugout(int); // add the slug to the output + char *typname(); // printable slug type + int serialno() { return serialnum; } + int numcol() { return ncol; } + int lineno() { return linenum; } +}; + +// functions in slug.c +slug eofslug(); +slug getslug(FILE *); diff --git a/mpm/version.c b/mpm/version.c new file mode 100644 index 0000000000000..4ead6741e6dfb --- /dev/null +++ b/mpm/version.c @@ -0,0 +1,20 @@ +#if __GNUC__ >= 3 && __GNUC_MINOR__ >= 4 || __GNUC__ >= 4 +#define USED __attribute__ ((used)) +#elif defined __GNUC__ +#define USED __attribute__ ((unused)) +#else +#define USED +#endif +static const char sccsid[] USED = "@(#)/usr/ucblib/pm.sl 1.5 (gritter) 7/29/06"; +/* SLIST */ +/* +misc.h: Sccsid @(#)misc.h 1.3 (gritter) 10/30/05 +page.h: Sccsid @(#)page.h 1.3 (gritter) 10/30/05 +range.h: Sccsid @(#)range.h 1.3 (gritter) 10/30/05 +slug.h: Sccsid @(#)slug.h 1.5 (gritter) 10/31/05 +misc.cc: Sccsid @(#)misc.cc 1.3 (gritter) 10/30/05 +page.cc: Sccsid @(#)page.cc 1.4 (gritter) 10/30/05 +queue.cc: Sccsid @(#)queue.cc 1.3 (gritter) 10/30/05 +range.cc: Sccsid @(#)range.cc 1.3 (gritter) 10/30/05 +slug.cc: Sccsid @(#)slug.cc 1.7 (gritter) 7/29/06 +*/ |