220  PART 32: SHIPPING PAGES OUT  TEX82 §592

592. Shipping pages out. After considering TEX’s eyes and stomach, we come now to the bowels. The ship out procedure is given a pointer to a box; its mission is to describe that box in form,

outputting a “page” to dvi file. The coordinates (h, v) = (0, 0) should correspond to the upper left corner of the box being shipped.

Since boxes can be inside of boxes inside of boxes, the main work of ship out is done by two mutually recursive routines, hlist out and vlist out , which traverse the hlists and vlists inside of horizontal and vertical boxes.

As individual pages are being processed, we need to accumulate information about the entire set of pages, since such statistics must be reported in the postamble. The global variables total pages , max v , max h, max push, and last bop are used to record this information.

The variable doing leaders is true while leaders are being output. The variable dead cycles contains the number of times an output routine has been initiated since the last ship out .

A few additional global variables are also defined here for use in vlist out and hlist out . They could have been local variables, but that would waste stack space when boxes are deeply nested, since the values of these variables are not needed during recursive calls. ⟨ Global variables 13 ⟩ +≡ total pages : integer ; { the number of pages that have been shipped out } max v : scaled ; { maximum height-plus-depth of pages shipped so far } max h: scaled ; { maximum width of pages shipped so far } max push: integer ; { deepest nesting of push commands encountered so far } last bop: integer ; { location of previous bop in the output } dead cycles : integer ; { recent outputs that didn’t ship anything out } doing leaders : boolean; { are we inside a leader box? } c, f: quarterword ; { character and font in current char node } rule ht , rule dp, rule wd : scaled ; { size of current rule being output } g: pointer ; { current glue specification } lq , lr : integer ; { quantities used in calculations for leaders }

593. ⟨ Set initial values of key variables 21 ⟩ +≡ total pages ← 0; max v ← 0; max h ← 0; max push ← 0; last bop ← −1; doing leaders ← false; dead cycles ← 0; cur s ← −1;

594. The bytes are output to a buffer instead of being written directly to the output file. This makes it possible to reduce the overhead of subroutine calls, thereby measurably speeding up the computation, since output of bytes is part of TEX’s inner loop. And it has another advantage as well, since we can change instructions in the buffer in order to make the output more compact. For example, a ‘down2 ’ command can be changed to a ‘y2 ’, thereby making a subsequent ‘y0 ’ command possible, saving two bytes.

The output buffer is divided into two parts of equal size; the bytes found in dvi buf [0 . . half buf − 1] constitute the first half, and those in dvi buf [half buf . . dvi buf size − 1] constitute the second. The global variable dvi ptr points to the position that will receive the next output byte. When dvi ptr reaches dvi limit , which is always equal to one of the two values half buf or dvi buf size, the half buffer that is about to be invaded next is sent to the output and dvi limit is changed to its other value. Thus, there is always at least a half buffer’s worth of information present, except at the very beginning of the job.

Bytes of the file are numbered sequentially starting with 0; the next byte to be generated will be number dvi offset + dvi ptr . A byte is present in the buffer only if its number is ≥ dvi gone. ⟨ Types in the outer block 18 ⟩ +≡

§595  TEX82  PART 32: SHIPPING PAGES OUT 221

dvi index = 0 . . dvi buf size; { an index into the output buffer } 595. Some systems may find it more efficient to make dvi buf a packed array, since output of four bytes at once may be facilitated. ⟨ Global variables 13 ⟩ +≡ dvi buf : array [dvi index ] of eight bits ; { buffer for output } half buf : dvi index ; { half of dvi buf size } dvi limit : dvi index ; { end of the current half buffer } dvi ptr : dvi index ; { the next available buffer address } dvi offset : integer ; { dvi buf size times the number of times the output buffer has been fully emptied } dvi gone: integer ; { the number of bytes already output to dvi file }

596. Initially the buffer is all in one piece; we will output half of it only after it first fills up. ⟨ Set initial values of key variables 21 ⟩ +≡

half buf ← dvi buf size div 2; dvi limit ← dvi buf size; dvi ptr ← 0; dvi offset ← 0; dvi gone ← 0;

597. The actual output of dvi buf [a . . b] to dvi file is performed by calling write dvi (a, b). For best results, this procedure should be optimized to run as fast as possible on each particular system, since it is part of TEX’s inner loop. It is safe to assume that a and b + 1 will both be multiples of 4 when write dvi (a, b) is called; therefore it is possible on many machines to use efficient methods to pack four bytes per word and to output an array of words with one system call. procedure write dvi (a, b : dvi index );

var k: dvi index ;

begin for k ← a to b do write(dvi file, dvi buf [k]);

end;

598. To put a byte in the buffer without paying the cost of invoking a procedure each time, we use the macro dvi out .

define dvi out (#) ≡ begin dvi buf [dvi ptr ] ← #; incr (dvi ptr ); if dvi ptr = dvi limit then dvi swap; end

procedure dvi swap; { outputs half of the buffer }

begin if dvi limit = dvi buf size then begin write dvi (0, half buf − 1); dvi limit ← half buf ; dvi offset ← dvi offset + dvi buf size; dvi ptr ← 0; end

else begin write dvi (half buf , dvi buf size − 1); dvi limit ← dvi buf size;

end; dvi gone ← dvi gone + half buf ; end;

599. Here is how we clean out the buffer when TEX is all through; dvi ptr will be a multiple of 4. ⟨ Empty the last bytes out of dvi buf 599 ⟩ ≡

if dvi limit = half buf then write dvi (half buf , dvi buf size − 1);

if dvi ptr > 0 then write dvi (0, dvi ptr − 1)

This code is used in section 642.

600. The dvi four procedure outputs four bytes in two’s complement notation, without risking arithmetic overflow. procedure dvi four (x : integer );

begin if x ≥ 0 then dvi out (x div ´ 100000000 ) else begin x ← x + ´ 10000000000 ; x ← x + ´ 10000000000 ; dvi out ((x div ´ 100000000 ) + 128);

end; x ← x mod ´ 100000000 ; dvi out (x div ´ 200000 ); x ← x mod ´ 200000 ; dvi out (x div ´ 400 ); dvi out (x mod ´ 400 ); end;

601. A mild optimization of the output is performed by the dvi pop routine, which issues a pop unless it is possible to cancel a ‘push pop’ pair. The parameter to dvi pop is the byte address following the old push that matches the new pop. procedure dvi pop(l : integer );

begin if (l = dvi offset + dvi ptr ) ∧ (dvi ptr > 0) then decr (dvi ptr ) else dvi out (pop); end;

602. Here’s a procedure that outputs a font definition. Since TEX82 uses at most 256 different fonts per job, fnt def1 is always used as the command code. procedure dvi font def (f : internal font number );

var k: pool pointer ; { index into str pool } begin dvi out (fnt def1 ); dvi out (f − font base − 1); dvi out (qo(font check [f].b0 )); dvi out (qo(font check [f].b1 )); dvi out (qo(font check [f].b2 )); dvi out (qo(font check [f].b3 )); dvi four (font size[f]); dvi four (font dsize[f]); dvi out (length(font area[f])); dvi out (length(font name[f])); ⟨ Output the font name whose internal number is f 603 ⟩; end;

603. ⟨ Output the font name whose internal number is f 603 ⟩ ≡ for k ← str start [font area[f]] to str start [font area[f] + 1] − 1 do dvi out (so(str pool [k])); for k ← str start [font name[f]] to str start [font name[f] + 1] − 1 do dvi out (so(str pool [k]))

This code is used in section 602.

604. Versions of TEX intended for small computers might well choose to omit the ideas in the next few parts of this program, since it is not really necessary to optimize the code by making use of the w0 , x0 , y0 , and z0 commands. Furthermore, the algorithm that we are about to describe does not pretend to give an optimum reduction in the length of the code; after all, speed is more important than compactness. But the method is surprisingly effective, and it takes comparatively little time.

We can best understand the basic idea by first considering a simpler problem that has the same essential characteristics. Given a sequence of digits, say 3 1 4 1 5 9 2 6 5 3 5 8 9, we want to assign subscripts d, y, or z to each digit so as to maximize the number of “y-hits” and “z-hits”; a y-hit is an instance of two appearances of the same digit with the subscript y, where no y’s intervene between the two appearances, and a z-hit is defined similarly. For example, the sequence above could be decorated with subscripts as follows:

3_{z} 1_{y} 4_{d} 1_{y} 5_{y} 9_{d} 2_{d} 6_{d} 5_{y} 3_{z} 5_{y} 8_{d} 9_{d}.

There are three y-hits (1_{y} … 1_{y} and 5_{y} … 5_{y} … 5_{y}) and one z-hit (3_{z} … 3_{z}); there are no d-hits, since the two appearances of 9_{d} have d’s between them, but we don’t count d-hits so it doesn’t matter how many there are. These subscripts are analogous to the commands called down, y, and z, and the digits are analogous to different amounts of vertical motion; a y-hit or z-hit corresponds to the opportunity to use the one-byte commands y0 or z0 in a file.

TEX’s method of assigning subscripts works like this: Append a new digit, say δ, to the right of the sequence. Now look back through the sequence until one of the following things happens: (a) You see δ_{y} or δ_{z}, and this was the first time you encountered a y or z subscript, respectively. Then assign y or z to the new δ; you have scored a hit. (b) You see δ_{d}, and no y subscripts have been encountered so far during this search. Then change the previous δ_{d} to δ_{y} (this corresponds to changing a command in the output buffer), and assign y to the new δ; it’s another hit. (c) You see δ_{d}, and a y subscript has been seen but not a z. Change the previous δ_{d} to δ_{z} and assign z to the new δ. (d) You encounter both y and z subscripts before encountering a suitable δ, or you scan all the way to the front of the sequence. Assign d to the new δ; this assignment may be changed later.

The subscripts 3_{z} 1_{y} 4_{d} … in the example above were, in fact, produced by this procedure, as the reader can verify. (Go ahead and try it.)

605. In order to implement such an idea, TEX maintains a stack of pointers to the down, y, and z commands that have been generated for the current page. And there is a similar stack for right , w, and x commands. These stacks are called the down stack and right stack, and their top elements are maintained in the variables down ptr and right ptr .

Each entry in these stacks contains four fields: The width field is the amount of motion down or to the right; the location field is the byte number of the command in question (including the appropriate dvi offset ); the link field points to the next item below this one on the stack; and the info field encodes the options for possible change in the command.

define movement node size = 3 { number of words per entry in the down and right stacks } define location(#) ≡ mem[# + 2].int { byte number for a movement command }

⟨ Global variables 13 ⟩ +≡ down ptr , right ptr : pointer ; { heads of the down and right stacks }

606. ⟨ Set initial values of key variables 21 ⟩ +≡ down ptr ← null ; right ptr ← null ; 607. Here is a subroutine that produces a command for some specified downward or rightward motion. It has two parameters: w is the amount of motion, and o is either down1 or right1 . We use the fact that the command codes have convenient arithmetic properties: y1 − down1 = w1 − right1 and z1 − down1 = x1 − right1 . procedure movement (w : scaled ; o : eight bits );

label exit , found , not found , 2, 1;

var mstate: small number ; { have we seen a y or z? } p, q: pointer ; { current and top nodes on the stack } k: integer ; { index into dvi buf , modulo dvi buf size }

begin q ← get node(movement node size); { new node for the top of the stack }

width(q) ← w; location(q) ← dvi offset + dvi ptr ;

if o = down1 then begin link (q) ← down ptr ; down ptr ← q; end

else begin link (q) ← right ptr ; right ptr ← q;

end; ⟨ Look at the other stack entries until deciding what sort of command to generate; goto found if

node p is a “hit” 611 ⟩; ⟨ Generate a down or right command for w and return 610 ⟩;

found : ⟨ Generate a y0 or z0 command in order to reuse a previous appearance of w 609 ⟩; exit : end;

608. The info fields in the entries of the down stack or the right stack have six possible settings: y here or z here mean that the command refers to y or z, respectively (or to w or x, in the case of horizontal motion); yz OK means that the command is down (or right ) but can be changed to either y or z (or to either w or x); y OK means that it is down and can be changed to y but not z; z OK is similar; and d fixed means it must stay down.

The four settings yz OK , y OK , z OK , d fixed would not need to be distinguished from each other if we were simply solving the digit-subscripting problem mentioned above. But in TEX’s case there is a complication because of the nested structure of push and pop commands. Suppose we add parentheses to the digit-subscripting problem, redefining hits so that δ_{y} … δ_{y} is a hit if all y’s between the δ’s are enclosed in properly nested parentheses, and if the parenthesis level of the right-hand δ_{y} is deeper than or equal to that of the left-hand one. Thus, ‘(’ and ‘)’ correspond to ‘push’ and ‘pop’. Now if we want to assign a subscript to the final 1 in the sequence

2_{y} 7_{d} 1_{d} ( 8_{z} 2_{y} 8_{z}) 1

we cannot change the previous 1_{d} to 1_{y}, since that would invalidate the 2_{y} … 2_{y} hit. But we can change it to 1_{z}, scoring a hit since the intervening 8_{z}’s are enclosed in parentheses.

The program below removes movement nodes that are introduced after a push, before it outputs the corresponding pop.

define y here = 1 { info when the movement entry points to a y command }

define z here = 2 { info when the movement entry points to a z command }

define yz OK = 3 { info corresponding to an unconstrained down command }

define y OK = 4 { info corresponding to a down that can’t become a z }

define z OK = 5 { info corresponding to a down that can’t become a y }

define d fixed = 6 { info corresponding to a down that can’t change } 609. When the movement procedure gets to the label found , the value of info(p) will be either y here or z here. If it is, say, y here, the procedure generates a y0 command (or a w0 command), and marks all info fields between q and p so that y is not OK in that range. ⟨ Generate a y0 or z0 command in order to reuse a previous appearance of w 609 ⟩ ≡

info(q) ← info(p); if info(q) = y here then

begin dvi out (o + y0 − down1 ); { y0 or w0 } while link (q) ≠ p do

begin q ← link (q);

case info(q) of

yz OK : info(q) ← z OK ; y OK : info(q) ← d fixed ;

othercases do nothing

endcases;

end; end

else begin dvi out (o + z0 − down1 ); { z0 or x0 }

while link (q) ≠ p do begin q ← link (q); case info(q) of yz OK : info(q) ← y OK ; z OK : info(q) ← d fixed ;

othercases do nothing

endcases;

end; end

This code is used in section 607.

610. ⟨ Generate a down or right command for w and return 610 ⟩ ≡ info(q) ← yz OK ; if abs (w) ≥ ´ 40000000 then

begin dvi out (o + 3); { down4 or right4 } dvi four (w); return; end;

if abs (w) ≥ ´ 100000 then begin dvi out (o + 2); { down3 or right3 } if w < 0 then w ← w + ´ 100000000 ; dvi out (w div ´ 200000 ); w ← w mod ´ 200000 ; goto 2; end;

if abs (w) ≥ ´ 200 then begin dvi out (o + 1); { down2 or right2 } if w < 0 then w ← w + ´ 200000 ; goto 2; end;

dvi out (o); { down1 or right1 } if w < 0 then w ← w + ´ 400 ; goto 1;

2: dvi out (w div ´ 400 ); 1: dvi out (w mod ´ 400 ); return

This code is used in section 607.

611. As we search through the stack, we are in one of three states, y seen, z seen, or none seen, depending on whether we have encountered y here or z here nodes. These states are encoded as multiples of 6, so that they can be added to the info fields for quick decision-making.

define none seen = 0 { no y here or z here nodes have been encountered yet } define y seen = 6 { we have seen y here but not z here } define z seen = 12 { we have seen z here but not y here }

⟨ Look at the other stack entries until deciding what sort of command to generate; goto found if node

p is a “hit” 611 ⟩ ≡ p ← link (q); mstate ← none seen; while p ≠ null do

begin if width(p) = w then ⟨ Consider a node with matching width; goto found if it’s a hit 612 ⟩ else case mstate + info(p) of

none seen + y here: mstate ← y seen; none seen + z here: mstate ← z seen; y seen + z here, z seen + y here: goto not found ;

othercases do nothing

endcases; p ← link (p); end;

not found :

This code is used in section 607.

612. We might find a valid hit in a y or z byte that is already gone from the buffer. But we can’t change bytes that are gone forever; “the moving finger writes, ….” ⟨ Consider a node with matching width; goto found if it’s a hit 612 ⟩ ≡

case mstate + info(p) of none seen + yz OK , none seen + y OK , z seen + yz OK , z seen + y OK :

if location(p) < dvi gone then goto not found

else ⟨ Change buffered instruction to y or w and goto found 613 ⟩; none seen + z OK , y seen + yz OK , y seen + z OK :

if location(p) < dvi gone then goto not found

else ⟨ Change buffered instruction to z or x and goto found 614 ⟩; none seen + y here, none seen + z here, y seen + z here, z seen + y here: goto found ;

othercases do nothing

endcases

This code is used in section 611.

613. ⟨ Change buffered instruction to y or w and goto found 613 ⟩ ≡ begin k ← location(p) − dvi offset ; if k < 0 then k ← k + dvi buf size; dvi buf [k] ← dvi buf [k] + y1 − down1 ; info(p) ← y here; goto found ; end

This code is used in section 612.

614. ⟨ Change buffered instruction to z or x and goto found 614 ⟩ ≡ begin k ← location(p) − dvi offset ; if k < 0 then k ← k + dvi buf size; dvi buf [k] ← dvi buf [k] + z1 − down1 ; info(p) ← z here; goto found ; end

This code is used in section 612.

615. In case you are wondering when all the movement nodes are removed from TEX’s memory, the answer is that they are recycled just before hlist out and vlist out finish outputting a box. This restores the down and right stacks to the state they were in before the box was output, except that some info’s may have become more restrictive. procedure prune movements (l : integer ); { delete movement nodes with location ≥ l }

label done, exit ;

var p: pointer ; { node being deleted }

begin while down ptr ≠ null do begin if location(down ptr ) < l then goto done; p ← down ptr ; down ptr ← link (p); free node(p, movement node size); end;

done: while right ptr ≠ null do begin if location(right ptr ) < l then return; p ← right ptr ; right ptr ← link (p); free node(p, movement node size); end;

exit : end;

616. The actual distances by which we want to move might be computed as the sum of several separate movements. For example, there might be several glue nodes in succession, or we might want to move right by the width of some box plus some amount of glue. More importantly, the baselineskip distances are computed in terms of glue together with the depth and height of adjacent boxes, and we want the file to lump these three quantities together into a single motion.

Therefore, TEX maintains two pairs of global variables: dvi h and dvi v are the h and v coordinates corresponding to the commands actually output to the file, while cur h and cur v are the coordinates corresponding to the current state of the output routines. Coordinate changes will accumulate in cur h and cur v without being reflected in the output, until such a change becomes necessary or desirable; we can call the movement procedure whenever we want to make dvi h = cur h or dvi v = cur v .

The current font reflected in the output is called dvi f ; there is no need for a ‘cur f ’ variable.

The depth of nesting of hlist out and vlist out is called cur s ; this is essentially the depth of push commands in the output.

define synch h ≡

if cur h ≠ dvi h then begin movement (cur h − dvi h, right1 ); dvi h ← cur h; end

define synch v ≡

if cur v ≠ dvi v then begin movement (cur v − dvi v , down1 ); dvi v ← cur v ; end

⟨ Global variables 13 ⟩ +≡ dvi h, dvi v : scaled ; { a reader program thinks we are here } cur h, cur v : scaled ; { TEX thinks we are here } dvi f : internal font number ; { the current font } cur s : integer ; { current depth of output box nesting, initially −1 } 617. ⟨ Initialize variables as ship out begins 617 ⟩ ≡

dvi h ← 0; dvi v ← 0; cur h ← h offset ; dvi f ← null font ; ensure dvi open; if total pages = 0 then

begin dvi out (pre); dvi out (id byte); { output the preamble } dvi four (25400000); dvi four (473628672); { conversion ratio for sp } prepare mag ; dvi four (mag ); { magnification factor is frozen } old setting ← selector ; selector ← new string ; print ( ␣ ␣ ␣ ); print int (year ); print char ( ); print two(month); print char ( ); print two(day ); print char ( ); print two(time div 60); print two(time mod 60); selector ← old setting ; dvi out (cur length); for s ← str start [str ptr ] to pool ptr − 1 do dvi out (so(str pool [s])); pool ptr ← str start [str ptr ]; { flush the current string } end

This code is used in section 640.

618. When hlist out is called, its duty is to output the box represented by the hlist node pointed to by temp ptr . The reference point of that box has coordinates (cur h, cur v ).

Similarly, when vlist out is called, its duty is to output the box represented by the vlist node pointed to by temp ptr . The reference point of that box has coordinates (cur h, cur v ). procedure vlist out ; forward ; { hlist out and vlist out are mutually recursive } 619. The recursive procedures hlist out and vlist out each have local variables save h and save v to hold the values of dvi h and dvi v just before entering a new level of recursion. In effect, the values of save h and save v on TEX’s run-time stack correspond to the values of h and v that a -reading program will push onto its coordinate stack.

define move past = 13 { go to this label when advancing past glue or a rule } define fin rule = 14 { go to this label to finish processing a rule } define next p = 15 { go to this label when finished with node p }

⟨ Declare procedures needed in hlist out , vlist out 1368 ⟩ procedure hlist out ; { output an hlist node box }

label reswitch, move past , fin rule, next p; var base line: scaled ; { the baseline coordinate for this box }

left edge: scaled ; { the left coordinate for this box }

save h, save v : scaled ; { what dvi h and dvi v should pop to } this box : pointer ; { pointer to containing box } g order : glue ord ; { applicable order of infinity for glue } g sign: normal . . shrinking ; { selects type of glue } p: pointer ; { current position in the hlist } save loc: integer ; { byte location upon entry } leader box : pointer ; { the leader box being replicated } leader wd : scaled ; { width of leader box being replicated } lx : scaled ; { extra space between leader boxes } outer doing leaders : boolean; { were we doing leaders? } edge: scaled ; { left edge of sub-box, or right edge of leader space } glue temp: real ; { glue value before rounding }

begin this box ← temp ptr ; g order ← glue order (this box ); g sign ← glue sign(this box ); p ← list ptr (this box ); incr (cur s ); if cur s > 0 then dvi out (push); if cur s > max push then max push ← cur s ; save loc ← dvi offset + dvi ptr ; base line ← cur v ; left edge ← cur h; while p ≠ null do ⟨ Output node p for hlist out and move to the next node, maintaining the condition

cur v = base line 620 ⟩; prune movements (save loc); if cur s > 0 then dvi pop(save loc); decr (cur s ); end; 620. We ought to give special care to the efficiency of one part of hlist out , since it belongs to TEX’s inner loop. When a char node is encountered, we save a little time by processing several nodes in succession until reaching a non-char node. The program uses the fact that set char 0 = 0. ⟨ Output node p for hlist out and move to the next node, maintaining the condition cur v = base line 620 ⟩ ≡ reswitch: if is char node(p) then

begin synch h; synch v ;

repeat f ← font (p); c ← character (p); if f ≠ dvi f then ⟨ Change font dvi f to f 621 ⟩; if c ≥ qi (128) then dvi out (set1 ); dvi out (qo(c)); cur h ← cur h + char width(f)(char info(f)(c)); p ← link (p);

until ¬is char node(p);

dvi h ← cur h;

end else ⟨ Output the non-char node p for hlist out and move to the next node 622 ⟩

This code is used in section 619.

621. ⟨ Change font dvi f to f 621 ⟩ ≡

begin if ¬font used [f] then begin dvi font def (f); font used [f] ← true; end;

if f ≤ 64 + font base then dvi out (f − font base − 1 + fnt num 0 ) else begin dvi out (fnt1 ); dvi out (f − font base − 1);

end; dvi f ← f; end

This code is used in section 620.

622. ⟨ Output the non-char node p for hlist out and move to the next node 622 ⟩ ≡ begin case type(p) of hlist node, vlist node: ⟨ Output a box in an hlist 623 ⟩; rule node: begin rule ht ← height (p); rule dp ← depth(p); rule wd ← width(p); goto fin rule;

end; whatsit node: ⟨ Output the whatsit node p in an hlist 1367 ⟩; glue node: ⟨ Move right or output leaders 625 ⟩; kern node, math node: cur h ← cur h + width(p); ligature node: ⟨ Make node p look like a char node and goto reswitch 652 ⟩;

othercases do nothing

endcases; goto next p;

fin rule: ⟨ Output a rule in an hlist 624 ⟩; move past : cur h ← cur h + rule wd ; next p: p ← link (p);

end

This code is used in section 620.

623. ⟨ Output a box in an hlist 623 ⟩ ≡ if list ptr (p) = null then cur h ← cur h + width(p) else begin save h ← dvi h; save v ← dvi v ; cur v ← base line + shift amount (p);

{ shift the box down } temp ptr ← p; edge ← cur h; if type(p) = vlist node then vlist out else hlist out ; dvi h ← save h; dvi v ← save v ; cur h ← edge + width(p); cur v ← base line; end

This code is used in section 622.

624. ⟨ Output a rule in an hlist 624 ⟩ ≡ if is running (rule ht ) then rule ht ← height (this box ); if is running (rule dp) then rule dp ← depth(this box ); rule ht ← rule ht + rule dp; { this is the rule thickness } if (rule ht > 0) ∧ (rule wd > 0) then { we don’t output empty rules }

begin synch h; cur v ← base line + rule dp; synch v ; dvi out (set rule); dvi four (rule ht ); dvi four (rule wd ); cur v ← base line; dvi h ← dvi h + rule wd ; end

This code is used in section 622.

625. define vet glue(#) ≡ glue temp ← #; if glue temp > float constant (1000000000) then glue temp ← float constant (1000000000) else if glue temp < −float constant (1000000000) then glue temp ← −float constant (1000000000)

⟨ Move right or output leaders 625 ⟩ ≡ begin g ← glue ptr (p); rule wd ← width(g); if g sign ≠ normal then

begin if g sign = stretching then

begin if stretch order (g) = g order then begin vet glue(float (glue set (this box )) ∗ stretch(g)); rule wd ← rule wd + round (glue temp); end; end

else if shrink order (g) = g order then begin vet glue(float (glue set (this box )) ∗ shrink (g)); rule wd ← rule wd − round (glue temp); end;

end; if subtype(p) ≥ a leaders then

⟨ Output leaders in an hlist, goto fin rule if a rule or to next p if done 626 ⟩; goto move past ; end

This code is used in section 622.

626. ⟨ Output leaders in an hlist, goto fin rule if a rule or to next p if done 626 ⟩ ≡ begin leader box ← leader ptr (p); if type(leader box ) = rule node then

begin rule ht ← height (leader box ); rule dp ← depth(leader box ); goto fin rule; end;

leader wd ← width(leader box ); if (leader wd > 0) ∧ (rule wd > 0) then

begin rule wd ← rule wd + 10; { compensate for floating-point rounding } edge ← cur h + rule wd ; lx ← 0; ⟨ Let cur h be the position of the first box, and set leader wd + lx to

the spacing between corresponding parts of boxes 627 ⟩; while cur h + leader wd ≤ edge do

⟨ Output a leader box at cur h, then advance cur h by leader wd + lx 628 ⟩; cur h ← edge − 10; goto next p; end;

end

This code is used in section 625.

627. The calculations related to leaders require a bit of care. First, in the case of a leaders (aligned leaders), we want to move cur h to left edge plus the smallest multiple of leader wd for which the result is not less than the current value of cur h; i.e., cur h should become left edge + leader wd × ⌈(cur h − left edge)/leader wd ⌉. The program here should work in all cases even though some implementations of Pascal give nonstandard results for the div operation when cur h is less than left edge.

In the case of c leaders (centered leaders), we want to increase cur h by half of the excess space not occupied by the leaders; and in the case of x leaders (expanded leaders) we increase cur h by 1/(q + 1) of this excess space, where q is the number of times the leader box will be replicated. Slight inaccuracies in the division might accumulate; half of this rounding error is placed at each end of the leaders. ⟨ Let cur h be the position of the first box, and set leader wd + lx to the spacing between corresponding

parts of boxes 627 ⟩ ≡ if subtype(p) = a leaders then

begin save h ← cur h; cur h ← left edge + leader wd ∗ ((cur h − left edge) div leader wd ); if cur h < save h then cur h ← cur h + leader wd ; end

else begin lq ← rule wd div leader wd ; { the number of box copies } lr ← rule wd mod leader wd ; { the remaining space } if subtype(p) = c leaders then cur h ← cur h + (lr div 2) else begin lx ← (2 ∗ lr + lq + 1) div (2 ∗ lq + 2); { round(lr /(lq + 1)) }

cur h ← cur h + ((lr − (lq − 1) ∗ lx ) div 2);

end; end

This code is used in section 626.

628. The ‘synch’ operations here are intended to decrease the number of bytes needed to specify horizontal and vertical motion in the output. ⟨ Output a leader box at cur h, then advance cur h by leader wd + lx 628 ⟩ ≡

begin cur v ← base line + shift amount (leader box ); synch v ; save v ← dvi v ; synch h; save h ← dvi h; temp ptr ← leader box ; outer doing leaders ← doing leaders ; doing leaders ← true; if type(leader box ) = vlist node then vlist out else hlist out ; doing leaders ← outer doing leaders ; dvi v ← save v ; dvi h ← save h; cur v ← base line; cur h ← save h + leader wd + lx ; end

This code is used in section 626.

629. The vlist out routine is similar to hlist out , but a bit simpler. procedure vlist out ; { output a vlist node box }

label move past , fin rule, next p; var left edge: scaled ; { the left coordinate for this box }

top edge: scaled ; { the top coordinate for this box }

save h, save v : scaled ; { what dvi h and dvi v should pop to } this box : pointer ; { pointer to containing box } g order : glue ord ; { applicable order of infinity for glue } g sign: normal . . shrinking ; { selects type of glue } p: pointer ; { current position in the vlist } save loc: integer ; { byte location upon entry } leader box : pointer ; { the leader box being replicated } leader ht : scaled ; { height of leader box being replicated } lx : scaled ; { extra space between leader boxes } outer doing leaders : boolean; { were we doing leaders? } edge: scaled ; { bottom boundary of leader space } glue temp: real ; { glue value before rounding }

begin this box ← temp ptr ; g order ← glue order (this box ); g sign ← glue sign(this box ); p ← list ptr (this box ); incr (cur s ); if cur s > 0 then dvi out (push); if cur s > max push then max push ← cur s ; save loc ← dvi offset + dvi ptr ; left edge ← cur h; cur v ← cur v − height (this box ); top edge ← cur v ; while p ≠ null do ⟨ Output node p for vlist out and move to the next node, maintaining the condition

cur h = left edge 630 ⟩; prune movements (save loc); if cur s > 0 then dvi pop(save loc); decr (cur s ); end;

630. ⟨ Output node p for vlist out and move to the next node, maintaining the condition

cur h = left edge 630 ⟩ ≡ begin if is char node(p) then confusion( ) else ⟨ Output the non-char node p for vlist out 631 ⟩;

next p: p ← link (p);

end

This code is used in section 629.

631. ⟨ Output the non-char node p for vlist out 631 ⟩ ≡ begin case type(p) of hlist node, vlist node: ⟨ Output a box in a vlist 632 ⟩; rule node: begin rule ht ← height (p); rule dp ← depth(p); rule wd ← width(p); goto fin rule;

end; whatsit node: ⟨ Output the whatsit node p in a vlist 1366 ⟩; glue node: ⟨ Move down or output leaders 634 ⟩; kern node: cur v ← cur v + width(p);

othercases do nothing

endcases; goto next p;

fin rule: ⟨ Output a rule in a vlist, goto next p 633 ⟩; move past : cur v ← cur v + rule ht ;

end

This code is used in section 630.

632. The synch v here allows the output to use one-byte commands for adjusting v in most cases, since the baselineskip distance will usually be constant. ⟨ Output a box in a vlist 632 ⟩ ≡

if list ptr (p) = null then cur v ← cur v + height (p) + depth(p) else begin cur v ← cur v + height (p); synch v ; save h ← dvi h; save v ← dvi v ;

cur h ← left edge + shift amount (p); { shift the box right }

temp ptr ← p;

if type(p) = vlist node then vlist out else hlist out ;

dvi h ← save h; dvi v ← save v ; cur v ← save v + depth(p); cur h ← left edge; end

This code is used in section 631.

633. ⟨ Output a rule in a vlist, goto next p 633 ⟩ ≡ if is running (rule wd ) then rule wd ← width(this box ); rule ht ← rule ht + rule dp; { this is the rule thickness } cur v ← cur v + rule ht ; if (rule ht > 0) ∧ (rule wd > 0) then { we don’t output empty rules }

begin synch h; synch v ; dvi out (put rule); dvi four (rule ht ); dvi four (rule wd ); end;

goto next p

This code is used in section 631.

634. ⟨ Move down or output leaders 634 ⟩ ≡ begin g ← glue ptr (p); rule ht ← width(g); if g sign ≠ normal then

begin if g sign = stretching then

begin if stretch order (g) = g order then begin vet glue(float (glue set (this box )) ∗ stretch(g)); rule ht ← rule ht + round (glue temp); end;

end else if shrink order (g) = g order then

begin vet glue(float (glue set (this box )) ∗ shrink (g)); rule ht ← rule ht − round (glue temp); end;

end; if subtype(p) ≥ a leaders then

⟨ Output leaders in a vlist, goto fin rule if a rule or to next p if done 635 ⟩; goto move past ; end

This code is used in section 631.

635. ⟨ Output leaders in a vlist, goto fin rule if a rule or to next p if done 635 ⟩ ≡ begin leader box ← leader ptr (p); if type(leader box ) = rule node then

begin rule wd ← width(leader box ); rule dp ← 0; goto fin rule; end;

leader ht ← height (leader box ) + depth(leader box ); if (leader ht > 0) ∧ (rule ht > 0) then

begin rule ht ← rule ht + 10; { compensate for floating-point rounding } edge ← cur v + rule ht ; lx ← 0; ⟨ Let cur v be the position of the first box, and set leader ht + lx to

the spacing between corresponding parts of boxes 636 ⟩; while cur v + leader ht ≤ edge do

⟨ Output a leader box at cur v , then advance cur v by leader ht + lx 637 ⟩; cur v ← edge − 10; goto next p; end;

end

This code is used in section 634.

636. ⟨ Let cur v be the position of the first box, and set leader ht + lx to the spacing between

corresponding parts of boxes 636 ⟩ ≡ if subtype(p) = a leaders then

begin save v ← cur v ; cur v ← top edge + leader ht ∗ ((cur v − top edge) div leader ht ); if cur v < save v then cur v ← cur v + leader ht ; end

else begin lq ← rule ht div leader ht ; { the number of box copies } lr ← rule ht mod leader ht ; { the remaining space } if subtype(p) = c leaders then cur v ← cur v + (lr div 2) else begin lx ← (2 ∗ lr + lq + 1) div (2 ∗ lq + 2); { round(lr /(lq + 1)) }

cur v ← cur v + ((lr − (lq − 1) ∗ lx ) div 2);

end; end

This code is used in section 635.

637. When we reach this part of the program, cur v indicates the top of a leader box, not its baseline. ⟨ Output a leader box at cur v , then advance cur v by leader ht + lx 637 ⟩ ≡

begin cur h ← left edge + shift amount (leader box ); synch h; save h ← dvi h; cur v ← cur v + height (leader box ); synch v ; save v ← dvi v ; temp ptr ← leader box ; outer doing leaders ← doing leaders ; doing leaders ← true; if type(leader box ) = vlist node then vlist out else hlist out ; doing leaders ← outer doing leaders ; dvi v ← save v ; dvi h ← save h; cur h ← left edge; cur v ← save v − height (leader box ) + leader ht + lx ; end

This code is used in section 635.

638. The hlist out and vlist out procedures are now complete, so we are ready for the ship out routine that gets them started in the first place. procedure ship out (p : pointer ); { output the box p }

label done; var page loc: integer ; { location of the current bop }

j, k: 0 . . 9; { indices to first ten count registers }

s: pool pointer ; { index into str pool }

old setting : 0 . . max selector ; { saved selector setting } begin if tracing output > 0 then

begin print nl ( ); print ln; print ( ␣ ␣ ␣ ␣ ); end;

if term offset > max print line − 9 then print ln else if (term offset > 0) ∨ (file offset > 0) then print char ( ␣ ); print char ( ); j ← 9; while (count (j) = 0) ∧ (j > 0) do decr (j); for k ← 0 to j do

begin print int (count (k));

if k < j then print char ( );

end; update terminal ; if tracing output > 0 then

begin print char ( ); begin diagnostic; show box (p); end diagnostic(true); end;

⟨ Ship box p out 640 ⟩; if tracing output ≤ 0 then print char ( ); dead cycles ← 0; update terminal ; { progress report } ⟨ Flush the box from memory, showing statistics if requested 639 ⟩; end; 639. ⟨ Flush the box from memory, showing statistics if requested 639 ⟩ ≡

stat if tracing stats > 1 then begin print nl ( ␣ ␣ ␣ ); print int (var used ); print char ( ); print int (dyn used ); print char ( ); end;

tats flush node list (p); stat if tracing stats > 1 then

begin print ( ␣ ␣ ); print int (var used ); print char ( ); print int (dyn used ); print ( ␣ ␣ ␣ ); print int (hi mem min − lo mem max − 1); print ln; end;

tats

This code is used in section 638.

640. ⟨ Ship box p out 640 ⟩ ≡ ⟨ Update the values of max h and max v ; but if the page is too large, goto done 641 ⟩; ⟨ Initialize variables as ship out begins 617 ⟩; page loc ← dvi offset + dvi ptr ; dvi out (bop); for k ← 0 to 9 do dvi four (count (k)); dvi four (last bop); last bop ← page loc; cur v ← height (p) + v offset ; temp ptr ← p; if type(p) = vlist node then vlist out else hlist out ; dvi out (eop); incr (total pages ); cur s ← −1;

done:

This code is used in section 638.

641. Sometimes the user will generate a huge page because other error messages are being ignored. Such pages are not output to the file, since they may confuse the printing software. ⟨ Update the values of max h and max v ; but if the page is too large, goto done 641 ⟩ ≡

if (height (p) > max dimen) ∨ (depth(p) > max dimen) ∨

(height (p) + depth(p) + v offset > max dimen) ∨ (width(p) + h offset > max dimen) then

begin print err (  ␣    ␣      ␣  ␣       ␣  );

  help2 (  ␣    ␣    ␣       ␣  ␣    ␣    ␣  ␣    ␣    ␣  )
  (  ␣    ␣  ␣    ␣     ␣  ␣ ␣       ␣         ␣    ␣  ); error ;

if tracing output ≤ 0 then begin begin diagnostic; print nl ( ␣ ␣ ␣ ␣ ␣ ); show box (p); end diagnostic(true); end;

goto done;

end; if height (p) + depth(p) + v offset > max v then max v ← height (p) + depth(p) + v offset ; if width(p) + h offset > max h then max h ← width(p) + h offset

This code is used in section 640.

642. At the end of the program, we must finish things off by writing the postamble. If total pages = 0, the file was never opened. If total pages ≥ 65536, the file will lie.

An integer variable k will be declared for use by this routine. ⟨ Finish the file 642 ⟩ ≡

while cur s > −1 do begin if cur s > 0 then dvi out (pop) else begin dvi out (eop); incr (total pages );

end; decr (cur s ); end;

if total pages = 0 then print nl ( ␣ ␣ ␣ ) else begin dvi out (post ); { beginning of the postamble }

dvi four (last bop); last bop ← dvi offset + dvi ptr − 5; { post location } dvi four (25400000); dvi four (473628672); { conversion ratio for sp } prepare mag ; dvi four (mag ); { magnification factor } dvi four (max v ); dvi four (max h); dvi out (max push div 256); dvi out (max push mod 256); dvi out ((total pages div 256) mod 256); dvi out (total pages mod 256); ⟨ Output the font definitions for all fonts that were used 643 ⟩; dvi out (post post ); dvi four (last bop); dvi out (id byte); k ← 4 + ((dvi buf size − dvi ptr ) mod 4); { the number of 223’s } while k > 0 do

begin dvi out (223); decr (k); end;

⟨ Empty the last bytes out of dvi buf 599 ⟩; print nl ( ␣ ␣ ␣ ); slow print (output file name); print ( ␣ ); print int (total pages ); print ( ␣ ); if total pages ≠ 1 then print char ( ); print ( ␣ ); print int (dvi offset + dvi ptr ); print ( ␣ ); b close(dvi file); end

This code is used in section 1333.

643. ⟨ Output the font definitions for all fonts that were used 643 ⟩ ≡

while font ptr > font base do begin if font used [font ptr ] then dvi font def (font ptr ); decr (font ptr ); end

This code is used in section 642.