Section 110: Packed data

In order to make efficient use of storage space, $\text{TEX}$ bases its major data structures on a memory_word, which contains either a (signed) integer, possibly scaled, or a (signed) glue_ratio, or a small number of fields that are one half or one quarter of the size used for storing integers.

If x is a variable of type memory_word, it contains up to four fields that can be referred to as follows:

This is somewhat cumbersome to write, and not very readable either, but macros will be used to make the notation shorter and more transparent. The Pascal code below gives a formal definition of memory_word and its subsidiary types, using packed variant records. $\text{TEX}$ makes no assumptions about the relative positions of the fields within a word.

Since we are assuming 32-bit integers, a halfword must contain at least 16 bits, and a quarterword must contain at least 8 bits. But it doesn’t hurt to have more bits; for example, with enough 36-bit words you might be able to have MEM_MAX as large as 262142, which is eight times as much memory as anybody had during the first four years of $\text{TEX}$’s existence.

N.B.: Valuable memory space will be dreadfully wasted unless $\text{TEX}$ is compiled by a Pascal that packs all of the memory_word variants into the space of a single integer. This means, for example, that glue_ratio words should be short_real instead of double on some computers. Some Pascal compilers will pack an integer whose subrange is ‘0 .. 255’ into an eight-bit field, but others insist on allocating space for an additional sign bit; on such systems you can get 256 values into a quarterword only if the subrange is ‘−128 .. 127’.

The present implementation tries to accommodate as many variations as possible, so it makes few assumptions. If integers having the subrange ‘MIN_QUARTERWORD .. MAX_QUARTERWORD’ can be packed into a quarterword, and if integers having the subrange ‘MIN_HALFWORD .. MAX_HALFWORD’ can be packed into a halfword, everything should work satisfactorily.

It is usually most efficient to have MIN_QUARTERWORD = MIN_HALFWORD = 0, so one should try to achieve this unless it causes a severe problem. The values defined here are recommended for most 32-bit computers.

#define MIN_QUARTERWORD 0           // smallest allowable value in a |quarterword|
#define MAX_QUARTERWORD 65535       // largest allowable value in a |quarterword|
#define MIN_HALFWORD    -0x3fffffff // smallest allowable value in a |halfword|
#define MAX_HALFWORD    0x3fffffff  // largest allowable value in a |halfword|

Section 111

Here are the inequalities that the quarterword and halfword values must satisfy (or rather, the inequalities that they mustn’t satisfy):

#ifdef INIT
if (MEM_MIN != MEM_BOT || MEM_MAX != MEM_TOP) {
    bad = 10;
}
#endif
if (MEM_MIN > MEM_BOT || MEM_MAX < MEM_TOP) {
    bad = 10;
}
if (MIN_QUARTERWORD > 0 || MAX_QUARTERWORD < 127) {
    bad = 11;
}
if (MIN_HALFWORD > 0 || MAX_HALFWORD < 32767) {
    bad = 12;
}
if (MIN_QUARTERWORD < MIN_HALFWORD || MAX_QUARTERWORD > MAX_HALFWORD) {
    bad = 13;
}
if (MEM_MIN < MIN_HALFWORD
    || MEM_MAX >= MAX_HALFWORD
    || MEM_BOT - MEM_MIN > MAX_HALFWORD + 1)
{
    bad = 14;
}
if (FONT_BASE < MIN_QUARTERWORD || FONT_MAX > MAX_QUARTERWORD) {
    bad = 15;
}
if (FONT_MAX > FONT_BASE + 256) {
    bad = 16;
}
if (SAVE_SIZE > MAX_HALFWORD || MAX_STRINGS > MAX_HALFWORD) {
    bad = 17;
}
if (BUF_SIZE > MAX_HALFWORD) {
    bad = 18;
}
if (MAX_QUARTERWORD - MIN_QUARTERWORD < 255) {
    bad = 19;
}

Section 112

The operation of adding or subtracting MIN_QUARTERWORD occurs quite frequently in $\text{TEX}$, so it is convenient to abbreviate this operation by using the macros qi and qo for input and output to and from quarterword format.

The inner loop of $\text{TEX}$ will run faster with respect to compilers that don’t optimize expressions like ‘x + 0’ and ‘x − 0’, if these macros are simplified in the obvious way when MIN_QUARTERWORD = 0.

#define hi(X) ((X) + MIN_HALFWORD) // to put a sixteen-bit item into a halfword
#define ho(X) ((X) - MIN_HALFWORD) // to take a sixteen-bit item from a halfword

Section 113

The reader should study the following definitions closely:

typedef uint16_t quarterword; // 1/4 of a word
typedef int32_t halfword;     // 1/2 of a word

typedef union {
    int         integer;
    scaled      sc;
    glue_ratio  gr;
    halfword    hh[2];
    quarterword qqqq[4];
} memory_word;

typedef FILE* word_file;

// << Start file |datastructures.h|, 1381 >>

#define qqqq_b0(W) (W).qqqq[0]
#define qqqq_b1(W) (W).qqqq[1]
#define qqqq_b2(W) (W).qqqq[2]
#define qqqq_b3(W) (W).qqqq[3]
#define hh_b0(W)   qqqq_b0((W))
#define hh_b1(W)   qqqq_b1((W))
#define hh_lh(W)   (W).hh[0]
#define hh_rh(W)   (W).hh[1]

Section 114

When debugging, we may want to print a memory_word without knowing what type it is; so we print it in all modes.

#ifdef DEBUG
// prints |w| in all ways
void print_word(memory_word w) {
    print_int(w.integer);
    print_char(' ');
    print_scaled(w.sc);
    print_char(' ');
    print_scaled((scaled)round(w.gr * UNITY));
    print_ln();
    print_int(hh_lh(w));
    print_char('=');
    print_int(hh_b0(w));
    print_char(':');
    print_int(hh_b1(w));
    print_char(';');
    print_int(hh_rh(w));
    print_char(' ');
    print_int(qqqq_b0(w));
    print_char(':');
    print_int(qqqq_b1(w));
    print_char(':');
    print_int(qqqq_b2(w));
    print_char(':');
    print_int(qqqq_b3(w));
}
#endif