Section 592: Shipping pages out

After considering $T E X$ ’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 DVI form, outputting a “page” to dvi_file. The DVI 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 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 ⟩+≡

int total_pages;    // the number of pages that have been shipped out
scaled max_v;       // maximum height-plus-depth of pages shipped so far
scaled max_h;       // maximum width of pages shipped so far
int max_push;       // deepest nesting of |PUSH| commands encountered so far
int last_bop;       // location of previous |BOP| in the `DVI` output
int dead_cycles;    // recent outputs that didn't ship anything out
bool doing_leaders; // are we inside a leader box?

quarterword c, f;                 // character and font in current |CHAR_NODE|
scaled rule_ht, rule_dp, rule_wd; // size of current rule being output
pointer g;                        // current glue specification
int lq, lr;                       // quantities used in calculations for leaders

Section 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;

Section 594

The DVI 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 DVI bytes is part of $T E X$ ’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 DVI 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 $\geq$ dvi_gone.

Section 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 ⟩+≡

eight_bits dvi_buf[DVI_BUF_SIZE + 1]; // buffer for `DVI` output
int half_buf;   // half of |DVI_BUF_SIZE|
int dvi_limit;  // end of the current half buffer
int dvi_ptr;    // the next available buffer address
int dvi_offset; // |DVI_BUF_SIZE| times the number of times the output buffer has been fully emptied
int dvi_gone;   // the number of bytes already output to |dvi_file|

Section 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 / 2;
dvi_limit = DVI_BUF_SIZE;
dvi_ptr = 0;
dvi_offset = 0;
dvi_gone = 0;

Section 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 is part of $T E X$ ’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.

dvi.c

// << Start file |dvi.c|, 1382 >>

void write_dvi(int a, int b) {
    int k;
    for(k = a; k <= b; k++) {
        write_byte(dvi_file, dvi_buf[k]);
    }
}

Section 598

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

dvi.h

#define dvi_out(X)                  \
    do {                            \
        dvi_buf[dvi_ptr] = (X);     \
        incr(dvi_ptr);              \
        if (dvi_ptr == dvi_limit) { \
            dvi_swap();             \
        }                           \
    } while (0)

dvi.c

// outputs half of the buffer
void dvi_swap() {
    if (dvi_limit == DVI_BUF_SIZE) {
        write_dvi(0, half_buf - 1);
        dvi_limit = half_buf;
        dvi_offset += DVI_BUF_SIZE;
        dvi_ptr = 0;
    }
    else {
        write_dvi(half_buf, DVI_BUF_SIZE - 1);
        dvi_limit = DVI_BUF_SIZE;
    }
    dvi_gone += half_buf;
}

Section 599

Here is how we clean out the buffer when $T E X$ 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) {
    write_dvi(half_buf, DVI_BUF_SIZE - 1);
}
if (dvi_ptr > 0) {
    write_dvi(0, dvi_ptr - 1);
}

Section 600

The dvi_four procedure outputs four bytes in two’s complement notation, without risking arithmetic overflow.

dvi.c

void dvi_four(int x) {
    if (x >= 0) {
        dvi_out(x / 0x1000000);
    }
    else {
        x += 0x40000000;
        x += 0x40000000;
        dvi_out(x / 0x1000000 + 128);
    }
    x %= 0x1000000;
    dvi_out(x / 0x10000);
    x %= 0x10000;
    dvi_out(x / 256);
    dvi_out(x % 256);
}

Section 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.

dvi.c

void dvi_pop(int l) {
    if (l == dvi_offset + dvi_ptr && dvi_ptr > 0) {
        decr(dvi_ptr);
    }
    else {
        dvi_out(POP);
    }
}

Section 602

Here’s a procedure that outputs a font definition. Since $T E X 82$ uses at most 256 different fonts per job, FNT_DEF1 is always used as the command code.

dvi.c

void dvi_font_def(internal_font_number f) {
    int k; // index into |str_pool|
    dvi_out(FNT_DEF1);
    dvi_out(f - FONT_BASE - 1);
    dvi_out(qqqq_b0(font_check[f]));
    dvi_out(qqqq_b1(font_check[f]));
    dvi_out(qqqq_b2(font_check[f]));
    dvi_out(qqqq_b3(font_check[f]));
    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 >>
}

Section 603

⟨ Output the font name whose internal number is f 603 ⟩≡

for(k = str_start[font_area[f]]; k < str_start[font_area[f] + 1]; k++) {
    dvi_out(str_pool[k]);
}
for(k = str_start[font_name[f]]; k < str_start[font_name[f] + 1]; k++) {
    dvi_out(str_pool[k]);
}

Section 604

Versions of $T E X$ 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 DVI 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 DVI 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 $3141592653589$ , 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} \dots 1_{y}$ and $5_{y} \dots 5_{y} \dots 5_{y})$ and one z-hit $(3_{z} \dots 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 DVI 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 DVI file.

$T E X$ ’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} \dots$ in the example above were, in fact, produced by this procedure, as the reader can verify. (Go ahead and try it.)

Section 605

In order to implement such an idea, $T E X$ 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 DVI 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 DVI command.

constants.h

#define MOVEMENT_NODE_SIZE 3 // number of words per entry in the down and right stacks

dvi.h

#define location(X) mem[(X) + 2].integer // `DVI` byte number for a movement command

⟨ Global variables 13 ⟩+≡

pointer down_ptr, right_ptr; // heads of the down and right stacks

Section 606

⟨ Set initial values of key variables 21 ⟩+≡

down_ptr = null;
right_ptr = null;

Section 607

Here is a subroutine that produces a DVI 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.

dvi.c

void movement(scaled w, eight_bits o) {
    small_number mstate; // have we seen a |y| or |z|?
    pointer p, q; // current and top nodes on the stack
    int k; // index into |dvi_buf|, modulo |DVI_BUF_SIZE|

    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) {
        link(q) = down_ptr;
        down_ptr = q;
    }
    else {
        link(q) = right_ptr;
        right_ptr = q;
    }
    
    // << Look at the other stack entries until deciding what sort of DVI 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 >>
}

Section 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 DVI command refers to y or z, respectively (or to W or X, in the case of horizontal motion); YZ_OK means that the DVI 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 $T E X$ ’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} \dots δ_{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} \dots 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.

constants.h

#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

Section 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) {
    dvi_out(o + Y0 - DOWN1); // |Y0| or |W0|
    while (link(q) != p) {
        q = link(q);
        switch (info(q)) {
        case YZ_OK:
            info(q) = Z_OK;
            break;
        
        case Y_OK:
            info(q) = D_FIXED;
            break;
        
        default:
            do_nothing;
        }
    }
}
else {
    dvi_out(o + Z0 - DOWN1); // |Z0| or |X0|
    while (link(q) != p) {
        q = link(q);
        switch (info(q)) {
        case YZ_OK:
            info(q) = Y_OK;
            break;
        
        case Z_OK:
            info(q) = D_FIXED;
            break;
        
        default:
            do_nothing;
        }
    }
}

Section 610

⟨ Generate a DOWN or RIGHT command for w and return 610 ⟩≡

info(q) = YZ_OK;
if (abs(w) >= 0x800000) {
    dvi_out(o + 3); // |DOWN4| or |RIGHT4|
    dvi_four(w);
    return;
}
if (abs(w) >= 0x8000 ) {
    dvi_out(o + 2); // |DOWN3| or |RIGHT3|
    if (w < 0) {
        w += 0x1000000;
    }
    dvi_out(w / 0x10000);
    w %= 0x10000;
    goto label_2;
}
if (abs(w) >= 128) {
    dvi_out(o + 1); // |DOWN2| or |RIGHT2|
    if (w < 0) {
        w += 0x10000;
    }
    goto label_2;
}
dvi_out(o); // |DOWN1| or |RIGHT1|
if (w < 0) {
    w += 256;
}
goto label_1;
label_2:
dvi_out(w / 256);
label_1:
dvi_out(w % 256);
return;

Section 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.

constants.h

#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 DVI command to generate; goto found if node p is a “hit” 611 ⟩≡

p = link(q);
mstate = NONE_SEEN;
while (p != null) {
    if (width(p) == w) {
        // << Consider a node with matching width; |goto found| if it's a hit, 612 >>
    }
    else {
        switch (mstate + info(p)) {
        case NONE_SEEN + Y_HERE:
            mstate = Y_SEEN;
            break;
        
        case NONE_SEEN + Z_HERE:
            mstate = Z_SEEN;
            break;
        
        case Y_SEEN + Z_HERE:
        case Z_SEEN + Y_HERE:
            goto not_found;
        
        default:
            do_nothing;
        }
    }
    p = link(p);
}
not_found:

Section 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, $\dots$ ”.

⟨ Consider a node with matching width; goto found if it’s a hit 612 ⟩≡

switch (mstate + info(p)) {
case NONE_SEEN + YZ_OK:
case NONE_SEEN + Y_OK:
case Z_SEEN + YZ_OK:
case Z_SEEN + Y_OK:
    if (location(p) < dvi_gone) {
        goto not_found;
    }
    else {
        // << Change buffered instruction to |y| or |w| and |goto found|, 613 >>
    }
    break;

case NONE_SEEN + Z_OK:
case Y_SEEN + YZ_OK:
case Y_SEEN + Z_OK:
    if (location(p) < dvi_gone) {
        goto not_found;
    }
    else {
        // << Change buffered instruction to |z| or |x| and |goto found|, 614 >>
    }
    break;

case NONE_SEEN + Y_HERE:
case NONE_SEEN + Z_HERE:
case Y_SEEN + Z_HERE:
case Z_SEEN + Y_HERE:
    goto found;

default:
    do_nothing;
}

Section 613

⟨ Change buffered instruction to y or w and goto found 613 ⟩≡

k = location(p) - dvi_offset;
if (k < 0) {
    k += DVI_BUF_SIZE;
}
dvi_buf[k] += Y1 - DOWN1;
info(p) = Y_HERE;
goto found;

Section 614

⟨ Change buffered instruction to z or x and goto found 614 ⟩≡

k = location(p) - dvi_offset;
if (k < 0) {
    k += DVI_BUF_SIZE;
}
dvi_buf[k] += Z1 - DOWN1;
info(p) = Z_HERE;
goto found;

Section 615

In case you are wondering when all the movement nodes are removed from $T E X$ ’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.

dvi.c

// delete movement nodes with |location >= l|
void prune_movements(int l) {
    pointer p; // node being deleted
    while (down_ptr != null) {
        if (location(down_ptr) < l) {
            break; // goto done
        }
        p = down_ptr;
        down_ptr = link(p);
        free_node(p, MOVEMENT_NODE_SIZE);
    }
    // done:
    while (right_ptr != null) {
        if (location(right_ptr) < l) {
            break; // return
        }
        p = right_ptr;
        right_ptr = link(p);
        free_node(p, MOVEMENT_NODE_SIZE);
    }
}

Section 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 DVI file to lump these three quantities together into a single motion.

Therefore, $T E X$ 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 DVI 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 DVI 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 DVI output.

dvi.h

#define synch_h                              \
    do {                                     \
        if (cur_h != dvi_h) {                \
            movement(cur_h - dvi_h, RIGHT1); \
            dvi_h = cur_h;                   \
        }                                    \
    } while (0)


#define synch_v                             \
    do {                                    \
        if (cur_v != dvi_v) {               \
            movement(cur_v - dvi_v, DOWN1); \
            dvi_v = cur_v;                  \
        }                                   \
    } while (0)

⟨ Global variables 13 ⟩+≡

scaled dvi_h, dvi_v;        // a `DVI` reader program thinks we are here
scaled cur_h, cur_v;        // TeX thinks we are here
internal_font_number dvi_f; // the current font
int cur_s;                  // current depth of output box nesting, initially -1

Section 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) {
    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(" TeX output ");
    print_int(year);
    print_char('.');
    print_two(month);
    print_char('.');
    print_two(day);
    print_char(':');
    print_two(time_ / 60);
    print_two(time_ % 60);
    selector = old_setting;
    dvi_out(cur_length);
    for(s = str_start[str_ptr]; s < pool_ptr; s++) {
        dvi_out(str_pool[s]);
    }
    pool_ptr = str_start[str_ptr]; // flush the current string
}

Section 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).

Section 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 $T E X$ ’s run-time stack correspond to the values of h and v that a DVI-reading program will push onto its coordinate stack.

dvi.c

// << Declare procedures needed in |hlist_out|, |vlist_out|, 1368 >>

// output an |HLIST_NODE| box
void hlist_out() {
    scaled base_line;         // the baseline coordinate for this box
    scaled left_edge;         // the left coordinate for this box
    scaled save_h, save_v;    // what |dvi_h| and |dvi_v| should pop to
    pointer this_box;         // pointer to containing box
    int g_order;              // applicable order of infinity for glue
    int g_sign;               // selects type of glue
    pointer p;                // current position in the hlist
    int save_loc;             // `DVI` byte location upon entry
    pointer leader_box;       // the leader box being replicated
    scaled leader_wd;         // width of leader box being replicated
    scaled lx;                // extra space between leader boxes
    bool outer_doing_leaders; // were we doing leaders?
    scaled edge;              // left edge of sub-box, or right edge of leader space
    double glue_temp;         // glue value before rounding
    double cur_glue;          // glue seen so far
    scaled cur_g;             // rounded equivalent of |cur_glue| times the glue ratio
    
    cur_g = 0;
    cur_glue = 0.0;
    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) {
        dvi_out(PUSH);
    }
    if (cur_s > max_push) {
        max_push = cur_s;
    }
    save_loc = dvi_offset + dvi_ptr;
    base_line = cur_v;
    left_edge = cur_h;
    while (p != null) {
        // << 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) {
        dvi_pop(save_loc);
    }
    decr(cur_s);
}

Section 620

We ought to give special care to the efficiency of one part of hlist_out, since it belongs to $T E X$ ’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)) {
    synch_h;
    synch_v;
    do {
        f = font(p);
        c = character(p);
        if (f != dvi_f) {
            // << Change font |dvi_f| to |f|, 621 >>
        }
        if (c >= 128) {
            dvi_out(SET1);
        }
        dvi_out(c);
        cur_h += char_width(f, char_info(f, c));
        p = link(p);
  } while (is_char_node(p));
  dvi_h = cur_h;
}
else {
    // << Output the non-|CHAR_NODE| |p| for |hlist_out| and move to the next node, 622 >>
}

Section 621

⟨ Change font dvi_f to f 621 ⟩≡

if (!font_used[f]) {
    dvi_font_def(f);
    font_used[f] = true;
}
if (f <= 64 + FONT_BASE) {
    dvi_out(f - FONT_BASE - 1 + FNT_NUM_0);
}
else {
    dvi_out(FNT1);
    dvi_out(f - FONT_BASE - 1);
}
dvi_f = f;

Section 622

⟨ Output the non-CHAR_NODE p for hlist_out and move to the next node 622 ⟩≡

switch (type(p)) {
case HLIST_NODE:
case VLIST_NODE:
    // << Output a box in an hlist, 623 >>
    break;

case RULE_NODE:
    rule_ht = height(p);
    rule_dp = depth(p);
    rule_wd = width(p);
    goto fin_rule;

case WHATSIT_NODE:
    // << Output the whatsit node |p| in an hlist, 1367 >>
    break;

case GLUE_NODE:
    // << Move right or output leaders, 625 >>

case KERN_NODE:
case MATH_NODE:
    cur_h += width(p);
    break;

case LIGATURE_NODE:
    // << Make node |p| look like a |CHAR_NODE| and |goto reswitch|, 652 >>

default:
    do_nothing;
}
goto next_p;

fin_rule:
// << Output a rule in an hlist, 624 >>

move_past:
cur_h += rule_wd;

next_p:
p = link(p);

Section 623

⟨ Output a box in an hlist 623 ⟩≡

if (list_ptr(p) == null) {
    cur_h += width(p);
}
else {
    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) {
        vlist_out();
    }
    else {
        hlist_out();
    }
    dvi_h = save_h;
    dvi_v = save_v;
    cur_h = edge + width(p);
    cur_v = base_line;
}

Section 624

⟨ Output a rule in an hlist 624 ⟩≡

if (is_running(rule_ht)) {
    rule_ht = height(this_box);
}
if (is_running(rule_dp)) {
    rule_dp = depth(this_box);
}
rule_ht += rule_dp; // this is the rule thickness
if (rule_ht > 0 && rule_wd > 0) {
    // we don't output empty rules
    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 += rule_wd;
}

Section 625

constants.h

#define BILLION 1000000000.0

dvi.h

#define vet_glue(X)                      \
    do {                                 \
        glue_temp = (X);                 \
        if (glue_temp > BILLION) {       \
            glue_temp = BILLION;         \
        }                                \
        else if (glue_temp < -BILLION) { \
            glue_temp = -BILLION;        \
        }                                \
    } while (0)

⟨ Move right or output leaders 625 ⟩≡

g = glue_ptr(p);
rule_wd = width(g) - cur_g;
if (g_sign != NORMAL) {
    if (g_sign == STRETCHING) {
        if (stretch_order(g) == g_order) {
            cur_glue += stretch(g);
            vet_glue(glue_set(this_box)*cur_glue);
            cur_g = (scaled)round(glue_temp);
        }
    }
    else if (shrink_order(g) == g_order) {
        cur_glue -= shrink(g);
        vet_glue(glue_set(this_box)*cur_glue);
        cur_g = (scaled)round(glue_temp);
    }
}
rule_wd += cur_g;
if (subtype(p) >= A_LEADERS) {
    // << Output leaders in an hlist, |goto fin_rule| if a rule or to |next_p| if done, 626 >>
}
goto move_past;

Section 626

⟨ Output leaders in an hlist, goto fin_rule if a rule or to next_p if done 626 ⟩≡

leader_box = leader_ptr(p);
if (type(leader_box) == RULE_NODE) {
    rule_ht = height(leader_box);
    rule_dp = depth(leader_box);
    goto fin_rule;
}
leader_wd = width(leader_box);
if (leader_wd > 0 && rule_wd > 0) {
    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) {
        // << Output a leader box at |cur_h|, then advance |cur_h| by |leader_wd + lx|, 628 >>
    }
    cur_h = edge - 10;
    goto next_p;
}

Section 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 $\times ⌈$ (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) {
    save_h = cur_h;
    cur_h = left_edge + leader_wd*((cur_h - left_edge) / leader_wd);
    if (cur_h < save_h) {
        cur_h += leader_wd;
    }
}
else {
    lq = rule_wd / leader_wd; // the number of box copies
    lr = rule_wd % leader_wd; // the remaining space
    if (subtype(p) == C_LEADERS) {
        cur_h += lr / 2;
    }
    else {
        lx = lr / (lq + 1);
        cur_h += (lr - (lq - 1) * lx) / 2;
    }
}

Section 628

The ‘synch’ operations here are intended to decrease the number of bytes needed to specify horizontal and vertical motion in the DVI output.

⟨ Output a leader box at cur_h, then advance cur_h by leader_wd + lx 628 ⟩≡

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) {
    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;

Section 629

The vlist_out routine is similar to hlist_out, but a bit simpler.

dvi.c

// output a |VLIST_NODE| box
void vlist_out() {
    scaled left_edge;         // the left coordinate for this box
    scaled top_edge;          // the top coordinate for this box
    scaled save_h, save_v;    // what |dvi_h| and |dvi_v| should pop to
    pointer this_box;         // pointer to containing box
    int g_order;              // applicable order of infinity for glue
    int g_sign;               // selects type of glue
    pointer p;                // current position in the vlist
    int save_loc;             // `DVI` byte location upon entry
    pointer leader_box;       // the leader box being replicated
    scaled leader_ht;         // height of leader box being replicated
    scaled lx;                // extra space between leader boxes
    bool outer_doing_leaders; // were we doing leaders?
    scaled edge;              // bottom boundary of leader space
    double glue_temp;         // glue value before rounding
    double cur_glue;          // glue seen so far
    scaled cur_g;             // rounded equivalent of |cur_glue| times the glue ratio
    
    cur_g = 0;
    cur_glue = 0.0;
    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) {
        dvi_out(PUSH);
    }
    if (cur_s > max_push) {
        max_push = cur_s;
    }
    save_loc = dvi_offset + dvi_ptr;
    left_edge = cur_h;
    cur_v -= height(this_box);
    top_edge = cur_v;
    while (p != null) {
        // << 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) {
        dvi_pop(save_loc);
    }
    decr(cur_s);
}

Section 630

⟨ Output node p for vlist_out and move to the next node, maintaining the condition cur_h = left_edge 630 ⟩≡

if (is_char_node(p)) {
    confusion("vlistout");
}
else {
    // << Output the non-|CHAR_NODE| |p| for |vlist_out|, 631 >>
}
next_p:
p = link(p);

Section 631

⟨ Output the non-CHAR_NODE p for vlist_out 631 ⟩≡

switch (type(p)) {
case HLIST_NODE:
case VLIST_NODE:
    // << Output a box in a vlist, 632 >>
    break;

case RULE_NODE:
    rule_ht = height(p);
    rule_dp = depth(p);
    rule_wd = width(p);
    goto fin_rule;

case WHATSIT_NODE:
    // << Output the whatsit node |p| in a vlist, 1366 >>
    break;

case GLUE_NODE:
    // << Move down or output leaders, 634 >>

case KERN_NODE:
    cur_v += width(p);
    break;

default:
    do_nothing;
}
goto next_p;

fin_rule:
// << Output a rule in a vlist, |goto next_p|, 633 >>

move_past:
cur_v += rule_ht;

Section 632

The synch_v here allows the DVI 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) {
    cur_v += height(p) + depth(p);
}
else {
    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) {
        vlist_out();
    }
    else {
        hlist_out();
    }
    dvi_h = save_h;
    dvi_v = save_v;
    cur_v = save_v + depth(p);
    cur_h = left_edge;
}

Section 633

⟨ Output a rule in a vlist, goto next_p 633 ⟩≡

if (is_running(rule_wd)) {
    rule_wd = width(this_box);
}
rule_ht += rule_dp; // this is the rule thickness
cur_v += rule_ht;
if (rule_ht > 0 && rule_wd > 0) {
    // we don't output empty rules
    synch_h;
    synch_v;
    dvi_out(PUT_RULE);
    dvi_four(rule_ht);
    dvi_four(rule_wd);
}
goto next_p;

Section 634

⟨ Move down or output leaders 634 ⟩≡

g = glue_ptr(p);
rule_ht = width(g) - cur_g;
if (g_sign != NORMAL) {
    if (g_sign == STRETCHING) {
        if (stretch_order(g) == g_order) {
            cur_glue += stretch(g);
            vet_glue(glue_set(this_box)*cur_glue);
            cur_g = (scaled)round(glue_temp);
        }
    }
    else if (shrink_order(g) == g_order) {
        cur_glue -= shrink(g);
        vet_glue(glue_set(this_box)*cur_glue);
        cur_g = (scaled)round(glue_temp);
    }
}
rule_ht += cur_g;
if (subtype(p) >= A_LEADERS) {
    // << Output leaders in a vlist, |goto fin_rule| if a rule or to |next_p| if done, 635 >>
}
goto move_past;

Section 635

⟨ Output leaders in a vlist, goto fin_rule if a rule or to next_p if done 635 ⟩≡

leader_box = leader_ptr(p);
if (type(leader_box) == RULE_NODE) {
    rule_wd = width(leader_box);
    rule_dp = 0;
    goto fin_rule;
}
leader_ht = height(leader_box) + depth(leader_box);
if (leader_ht > 0 && rule_ht > 0) {
    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) {
        // << Output a leader box at |cur_v|, then advance |cur_v| by |leader_ht + lx|, 637 >>
    }
    cur_v = edge - 10;
    goto next_p;
}

Section 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) {
    save_v = cur_v;
    cur_v = top_edge + leader_ht*((cur_v - top_edge) / leader_ht);
    if (cur_v < save_v) {
        cur_v += leader_ht;
    }
}
else {
    lq = rule_ht / leader_ht; // the number of box copies
    lr = rule_ht % leader_ht; // the remaining space
    if (subtype(p) == C_LEADERS) {
        cur_v += lr / 2;
    }
    else {
        lx = lr / (lq + 1);
        cur_v += (lr - (lq - 1) * lx)/2;
    }
}

Section 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 ⟩≡

cur_h = left_edge + shift_amount(leader_box);
synch_h;
save_h = dvi_h;
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) {
    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;

Section 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.

dvi.c

// output the box |p|
void ship_out(pointer p) {
    int page_loc;    // location of the current |BOP|
    int j, k;        // indices to first ten count registers
    pool_pointer s;  // index into |str_pool|
    int old_setting; // saved |selector| setting
    
    if (tracing_output > 0) {
        print_nl("");
        print_ln();
        print("Completed box being shipped out");
    }
    if (term_offset > MAX_PRINT_LINE - 9) {
        print_ln();
    }
    else if (term_offset > 0 || file_offset > 0) {
        print_char(' ');
    }
    print_char('[');
    j = 9;
    while (count(j) == 0 && j > 0) {
        decr(j);
    }
    for(k = 0; k <= j; k++) {
        print_int(count(k));
        if (k < j) {
            print_char('.');
        }
    }
    update_terminal;
    if (tracing_output > 0) {
        print_char(']');
        begin_diagnostic();
        show_box(p);
        end_diagnostic(true);
    }
    // << Ship box |p| out, 640 >>
    if (tracing_output <= 0) {
        print_char(']');
    }
    dead_cycles = 0;
    update_terminal; // progress report
    // << Flush the box from memory, showing statistics if requested, 639 >>
}

Section 639

⟨ Flush the box from memory, showing statistics if requested 639 ⟩≡

#ifdef STAT
if (tracing_stats > 1) {
    print_nl("Memory usage before: ");
    print_int(var_used);
    print_char('&');
    print_int(dyn_used);
    print_char(';');
}
#endif
flush_node_list(p);
#ifdef STAT
if (tracing_stats > 1) {
    print(" after: ");
    print_int(var_used);
    print_char('&');
    print_int(dyn_used);
    print("; still untouched: ");
    print_int(hi_mem_min - lo_mem_max - 1);
    print_ln();
}
#endif

Section 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; k <= 9; k++) {
    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) {
    vlist_out();
}
else {
    hlist_out();
}
dvi_out(EOP);
incr(total_pages);
cur_s = -1;
done:

Section 641

Sometimes the user will generate a huge page because other error messages are being ignored. Such pages are not output to the dvi 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)
{
    print_err("Huge page cannot be shipped out");
    help2("The page just created is more than 18 feet tall or")
        ("more than 18 feet wide, so I suspect something went wrong.");
    error();
    if (tracing_output <= 0) {
        begin_diagnostic();
        print_nl("The following box has been deleted:");
        show_box(p);
        end_diagnostic(true);
    }
    goto done;
}
if (height(p) + depth(p) + v_offset > max_v) {
    max_v = height(p) + depth(p) + v_offset;
}
if (width(p) + h_offset > max_h) {
    max_h = width(p) + h_offset;
}

Section 642

At the end of the program, we must finish things off by writing the postamble. If total_pages = 0, the DVI file was never opened. If total_pages $\geq$ 65536, the DVI file will lie. And if max_push $\geq$ 65536, the user deserves whatever chaos might ensue.

An integer variable k will be declared for use by this routine.

⟨ Finish the DVI file 642 ⟩≡

while (cur_s > -1) {
    if (cur_s > 0) {
        dvi_out(POP);
    }
    else {
        dvi_out(EOP);
        incr(total_pages);
    }
    decr(cur_s);
}
if (total_pages == 0) {
    print_nl("No pages of output.");
}
else {
    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 / 256);
    dvi_out(max_push % 256);
    dvi_out((total_pages / 256) % 256);
    dvi_out(total_pages % 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) % 4); // the number of 223's
    while (k > 0) {
        dvi_out(223);
        decr(k);
    }
    // << Empty the last bytes out of |dvi_buf|, 599 >>
    print_nl("Output written on ");
    slow_print(output_file_name);
    print(" (");
    print_int(total_pages);
    print(" page");
    if (total_pages != 1) {
        print_char('s');
    }
    print(", ");
    print_int(dvi_offset + dvi_ptr);
    print(" bytes).");
    b_close(dvi_file);
}

Section 643

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

while (font_ptr > FONT_BASE) {
    if (font_used[font_ptr]) {
        dvi_font_def(font_ptr);
    }
    decr(font_ptr);
}

TeX in C