§1  PXtoPK  INTRODUCTION 1

1. Introduction. The standard format for the distribution of font raster information for TEX has been files. These files are loosely packed, based on a 32-bit word, and use no forms of compression. TEX requires dozens of fonts in many different sizes, with typical installations having hundreds of pixel files using many megabytes of disk storage. Distribution of the unwieldy pixel files is also a difficult problem for microcomputer systems, on which TEX is only just becoming available. Many boxes of diskettes would be required just to store a basic set of fonts in three sizes for a three-hundred dot per inch device. A better format is called for.

This program compresses a pixel file into a packed, or , file. This new format is primarily intended for distribution. Drivers can be adapted to read these files, and since pixel files can be converted back and forth with this program and its companion , no information will be lost by leaving the files in one format or another.

2. The banner string defined here should be changed whenever gets modified.

define banner ≡ ´ ␣ ␣ ␣ ␣ ´ { printed when the program starts }

3. This program is written in standard Pascal, except where it is necessary to use extensions; for example, must read files whose names are dynamically specified, and that would be impossible in pure Pascal.

define othercases ≡ others : { default for cases not listed explicitly }

define endcases ≡ end { follows the default case in an extended case statement }

format othercases ≡ else

format endcases ≡ end

4. Both the input and output come from binary files. On line interaction is handled through Pascal’s standard input and output files.

define print ln(#) ≡ write ln(output , #)

define print (#) ≡ write(output , #) program PXtoPK (input , output );

label ⟨ Labels in the outer block 5 ⟩

const ⟨ Constants in the outer block 6 ⟩

type ⟨ Types in the outer block 9 ⟩

var ⟨ Globals in the outer block 11 ⟩

procedure initialize; { this procedure gets things started properly } var i: integer ; { loop index for initializations } begin print ln(banner ); ⟨ Set initial values 12 ⟩ end;

5. If the program has to stop prematurely, it goes to the ‘final end ’.

define final end = 9999 { label for the end of it all } ⟨ Labels in the outer block 5 ⟩ ≡

final end ;

This code is used in section 4.

2  INTRODUCTION  PXtoPK §6

6. The variable max mem size should be set to the size of the largest font that will be downloaded, with a few thousand extra for safety. 100,000 should be sufficient. ⟨ Constants in the outer block 6 ⟩ ≡

max mem size = 200000; { the major array used for almost everything. } name length = 80; { maximum length of a file name } terminal line length = 132; { maximum length of an input line }

See also section 39. This code is used in section 4.

7. Here are some macros for common programming idioms.

define incr (#) ≡ # ← # + 1 { increase a variable by unity } define decr (#) ≡ # ← # − 1 { decrease a variable by unity } define do nothing ≡ { empty statement }

8. It is possible that a malformed pixel file (heaven forbid!) or some other error might be detected by this program. Such errors might occur in a deeply nested procedure, so the procedure called jump out has been added to transfer to the very end of the program with an error message.

define abort (#) ≡ begin print ln(´ ␣´ , #); jump out ; end

procedure jump out ; begin goto final end ; end;

§9  PXtoPK  THE CHARACTER SET 3
9. The character set. Like all programs written with the  system,  can be used with any

character set. But it uses ASCII code internally, because the programming for portable input-output is easier when a fixed internal code is used.

The next few sections of have therefore been copied from the analogous ones in the system routines. They have been considerably simplified, since need not deal with the controversial ASCII codes less than ´ 40 . ⟨ Types in the outer block 9 ⟩ ≡

ASCII code = ␣ . . ; { a subrange of the integers }

See also sections 10 and 32. This code is used in section 4.

10. The original Pascal compiler was designed in the late 60s, when six-bit character sets were common, so it did not make provision for lower case letters. Nowadays, of course, we need to deal with both upper and lower case alphabets in a convenient way, especially in a program like . So we shall assume that the Pascal system being used for has a character set containing at least the standard visible characters of ASCII code ( through ).

Some Pascal compilers use the original name char for the data type associated with the characters in text files, while other Pascals consider char to be a 64-element subrange of a larger data type that has some other name. In order to accommodate this difference, we shall use the name text char to stand for the data type of the characters in the output file. We shall also assume that text char consists of the elements chr (first text char ) through chr (last text char ), inclusive. The following definitions should be adjusted if necessary.

define text char ≡ char { the data type of characters in text files }

define first text char = 0 { ordinal number of the smallest element of text char }

define last text char = 127 { ordinal number of the largest element of text char } ⟨ Types in the outer block 9 ⟩ +≡

text file = packed file of text char ;

11. The processor converts between ASCII code and the user’s external character set by means of arrays xord and xchr that are analogous to Pascal’s ord and chr functions. ⟨ Globals in the outer block 11 ⟩ ≡ xord : array [text char ] of ASCII code; { specifies conversion of input characters } xchr : array [0 . . 255] of text char ; { specifies conversion of output characters }

See also sections 33, 35, 38, 41, 43, 47, 52, 54, and 57. This code is used in section 4.

4  THE CHARACTER SET  PXtoPK §12

12. Under our assumption that the visible characters of standard ASCII are all present, the following assignment statements initialize the xchr array properly, without needing any system-dependent changes. ⟨ Set initial values 12 ⟩ ≡

for i ← 0 to ´ 37 do xchr [i] ← ´ ´ ; xchr [´ 40 ] ← ´ ␣´ ; xchr [´ 41 ] ← ´ ´ ; xchr [´ 42 ] ← ´ ´ ; xchr [´ 43 ] ← ´ #´ ; xchr [´ 44 ] ← ´ $´ ; xchr [´ 45 ] ← ´ %´ ; xchr [´ 46 ] ← ´ ´ ; xchr [´ 47 ] ← ´ ´ ´ ´ ; xchr [´ 50 ] ← ´ ´ ; xchr [´ 51 ] ← ´ ´ ; xchr [´ 52 ] ← ´ ´ ; xchr [´ 53 ] ← ´ ´ ; xchr [´ 54 ] ← ´ ´ ; xchr [´ 55 ] ← ´ ´ ; xchr [´ 56 ] ← ´ ´ ; xchr [´ 57 ] ← ´ ´ ; xchr [´ 60 ] ← ´ ´ ; xchr [´ 61 ] ← ´ ´ ; xchr [´ 62 ] ← ´ ´ ; xchr [´ 63 ] ← ´ ´ ; xchr [´ 64 ] ← ´ ´ ; xchr [´ 65 ] ← ´ ´ ; xchr [´ 66 ] ← ´ ´ ; xchr [´ 67 ] ← ´ ´ ; xchr [´ 70 ] ← ´ ´ ; xchr [´ 71 ] ← ´ ´ ; xchr [´ 72 ] ← ´ ´ ; xchr [´ 73 ] ← ´ ´ ; xchr [´ 74 ] ← ´ ´ ; xchr [´ 75 ] ← ´ ´ ; xchr [´ 76 ] ← ´ ´ ; xchr [´ 77 ] ← ´ ´ ; xchr [´ 100 ] ← ´ ´ ; xchr [´ 101 ] ← ´ ´ ; xchr [´ 102 ] ← ´ ´ ; xchr [´ 103 ] ← ´ ´ ; xchr [´ 104 ] ← ´ ´ ; xchr [´ 105 ] ← ´ ´ ; xchr [´ 106 ] ← ´ ´ ; xchr [´ 107 ] ← ´ ´ ; xchr [´ 110 ] ← ´ ´ ; xchr [´ 111 ] ← ´ ´ ; xchr [´ 112 ] ← ´ ´ ; xchr [´ 113 ] ← ´ ´ ; xchr [´ 114 ] ← ´ ´ ; xchr [´ 115 ] ← ´ ´ ; xchr [´ 116 ] ← ´ ´ ; xchr [´ 117 ] ← ´ ´ ; xchr [´ 120 ] ← ´ ´ ; xchr [´ 121 ] ← ´ ´ ; xchr [´ 122 ] ← ´ ´ ; xchr [´ 123 ] ← ´ ´ ; xchr [´ 124 ] ← ´ ´ ; xchr [´ 125 ] ← ´ ´ ; xchr [´ 126 ] ← ´ ´ ; xchr [´ 127 ] ← ´ ´ ; xchr [´ 130 ] ← ´ ´ ; xchr [´ 131 ] ← ´ ´ ; xchr [´ 132 ] ← ´ ´ ; xchr [´ 133 ] ← ´ ´ ; xchr [´ 134 ] ← ´ ´ ; xchr [´ 135 ] ← ´ ´ ; xchr [´ 136 ] ← ´ ´ ; xchr [´ 137 ] ← ´ ´ ; xchr [´ 140 ] ← ´ ` ´ ; xchr [´ 141 ] ← ´ ´ ; xchr [´ 142 ] ← ´ ´ ; xchr [´ 143 ] ← ´ ´ ; xchr [´ 144 ] ← ´ ´ ; xchr [´ 145 ] ← ´ ´ ; xchr [´ 146 ] ← ´ ´ ; xchr [´ 147 ] ← ´ ´ ; xchr [´ 150 ] ← ´ ´ ; xchr [´ 151 ] ← ´ ´ ; xchr [´ 152 ] ← ´ ´ ; xchr [´ 153 ] ← ´ ´ ; xchr [´ 154 ] ← ´ ´ ; xchr [´ 155 ] ← ´ ´ ; xchr [´ 156 ] ← ´ ´ ; xchr [´ 157 ] ← ´ ´ ; xchr [´ 160 ] ← ´ ´ ; xchr [´ 161 ] ← ´ ´ ; xchr [´ 162 ] ← ´ ´ ; xchr [´ 163 ] ← ´ ´ ; xchr [´ 164 ] ← ´ ´ ; xchr [´ 165 ] ← ´ ´ ; xchr [´ 166 ] ← ´ ´ ; xchr [´ 167 ] ← ´ ´ ; xchr [´ 170 ] ← ´ ´ ; xchr [´ 171 ] ← ´ ´ ; xchr [´ 172 ] ← ´ ´ ; xchr [´ 173 ] ← ´ ´ ; xchr [´ 174 ] ← ´ ´ ; xchr [´ 175 ] ← ´ ´ ; xchr [´ 176 ] ← ´ ´ ; for i ← ´ 177 to 255 do xchr [i] ← ´ ´ ;

See also sections 13, 36, 48, and 58. This code is used in section 4.

13. The following system-independent code makes the xord array contain a suitable inverse to the information in xchr . ⟨ Set initial values 12 ⟩ +≡

for i ← first text char to last text char do xord [chr (i)] ← ´ 40 ; for i ← ␣ to do xord [xchr [i]] ← i;

§14  PXtoPK  PIXEL FILE FORMAT 5

14. Pixel file format. A file is an expanded raster description of a single font at a particular resolution. files are used by many existing device-driver programs for dot matrix devices. All words in of files are in 32-bit format, with the four lower bits zero on 36-bit machines. The raster information is contained in a sequence of binary words which record white pixels as zeros and black pixels as ones.

The first word of the file and the last word contain the which is currently equal to 1001 (decimal). This first word is followed by a sequence of raster information words where each line of pixels in the glyphs is represented by one or more words of binary information. The number of words used to represent each row of pixels for any particular glyph is fixed and it is set by the value of max m − min m + 1 for that particular glyph. Each white pixel is represented by a zero and each black pixel is represented by a one in the corresponding bit positions (the first 32 only of each word on 36-bit machines). The unused bit positions toward the end of each set of words for each row of pixels are filled with zeros.

The font directory follows, occupying a fixed position with respect to the end of the file (in words 517 through 6 from this end), and assigns 4 words for each of the potential 128 different glyphs that could be contained in this particular font in the order of their assending ascii values (not in the order that the glyphs appear in the raster section, which may be entirely arbitrary). This means that the first four words are for the ascii zero glyph. All four words reserved for any missing glyphs are set to zero.

The first word of each glyph’s directory information contains the pixel width in the left half-word (the leftmost 16 bits) and the pixel height in the right half-word (the next 16 bits). These dimensions are those of the smallest bounding-box, measured in pixels, and they have nothing necessarily to do with the width and height figures that appear in the file. The width, measured in , where 1 is 1/2^{20} times the design size, is listed in the fourth word of the glyph’s directory information.

The second word of the glyph’s directory information contains the offset of the glyph’s reference point from its upper-left-hand corner of the bounding box, measured in pixels, with the x-offset in the left half-word and the y-offset in the right half-word. These numbers may be negative, and two’s complement representation is used. Remember that the positive x direction means ‘rightward’ and positive y is ‘downward’ on the page.

The third word of a glyph’s directory information contains the number of the word in this file where the raster description for this particular glyph begins, measured from the first word which is numbered zero. As mentioned earlier, the fourth word of directory information for each glyph contains the width.

The final five words in the file contain information relation to the entire file. The first of these five words is a checksum which should match the checksum contained in the file that TEX used in reference to this font, although, if this checksum is zero, no validity checking will be done. The second of these five words is an integer that is 1000 times the magnification factor at which this font was produced. The third word contains the design sige of the font measured in (2^{−20} unmagnified points). The fourth word contains a pointer to the first word of the font directory. The fifth and last word of the entire file contains a duplicate of the ID as contained in the first word of the file.

6  PACKED FILE FORMAT  PXtoPK §15

define pxl id = 1001 { current version of format } 15. Packed file format. The packed file format is a compact representation of the data contained in a file. The information content is the same, but packed ( ) files are almost always less than half the size of their counterparts. They are also easier to convert into a raster representation because they do not have a profusion of paint , skip, and new row commands to be separately interpreted. In addition, the format expressedly forbids special commands within a character. The minimum bounding box for each character is explicit in the format, and does not need to be scanned for as in the format. Finally, the width and escapement values are combined with the raster information into character “packets”, making it simpler in many cases to process a character.

A file is organized as a stream of 8-bit bytes. At times, these bytes might be split into 4-bit nybbles or single bits, or combined into multiple byte parameters. When bytes are split into smaller pieces, the ‘first’ piece is always the most significant of the byte. For instance, the first bit of a byte is the bit with value 128; the first nybble can be found by dividing a byte by 16. Similarly, when bytes are combined into multiple byte parameters, the first byte is the most significant of the parameter. If the parameter is signed, it is represented by two’s-complement notation.

The set of possible eight-bit values are separated into two sets, those that introduce a character definition, and those that do not. The values that introduce a character definition comprise the range from 0 to 239; byte values above 239 are interpreted commands. Bytes which introduce character definitions are called flag bytes, and various fields within the byte indicate various things about how the character definition is encoded. Command bytes have zero or more parameters, and can never appear within a character definition or between parameters of another command, where they would be interpeted as data.

A file consists of a preamble, followed by a sequence of one or more character definitions, followed by a postamble. The preamble command must be the first byte in the file, followed immediately by its parameters. Any number of character definitions may follow, and any command but the preamble command and the postamble command may occur between character definitions. The very last command in the file must be the postamble.

16. The packed file format is intended to be easy to read and interpret by device drivers. The small size of the file reduces the input/output overhead each time a font is defined. For those drivers that load and save each font file into memory, the small size also helps reduce the memory requirements. The length of each character packet is specified, allowing the character raster data to be loaded into memory by simply counting bytes, rather than interpreting each command; then, each character can be interpreted on a demand basis. This also makes it possible for a driver to skip a particular character quickly if it knows that the character is unused.

§17  PXtoPK  PACKED FILE FORMAT 7

17. First, the command bytes shall be presented; then the format of the Character definitions will be defined. Eight of the possible sixteen commands (values 240 through 255) are currently defined; the others are reserved for future extensions. The commands are listed below. Each command is specified by its symbolic name (e.g., pk no op), its opcode byte, and any parameters. The parameters are followed by a bracketed number telling how many bytes they occupy, with the number preceded by a plus sign if it is a signed quantity. (Four byte quantities are always signed, however.) pk xxx1

240 k[1] x[k]. This command is undefined in general; it functions as a (k + 2)-byte no op unless special -reading programs are being used. generates xxx commands when encountering a special string. It is recommended that x be a string having the form of a keyword followed by possible parameters relevant to that keyword.

pk xxx2

241 k[2] x[k]. Like pk xxx1 , but 0 ≤ k < 65536. pk xxx3

242 k[3] x[k]. Like pk xxx1 , but 0 ≤ k < 2^{24}. uses this when sending a special string whose length exceeds 255.

pk xxx4

243 k[4] x[k]. Like pk xxx1 , but k can be ridiculously large; k musn’t be negative. pk yyy

244 y[4]. This command is undefined in general; it functions as a five-byte no op unless special reading programs are being used. puts scaled numbers into yyy ’s, as a result of numspecial commands; the intent is to provide numeric parameters to xxx commands that immediately precede.

pk post 245. Beginning of the postamble. This command is followed by just enough pk no op commands to make the file a multiple of four bytes long; zero through three are usual, but four are also allowed. This should make the file easy to read on machines which pack four bytes to a word.

pk no op 246. No operation, do nothing. Any number of pk no op’s may appear between commands, but a pk no op cannot be inserted between a command and its parameters, between two parameters, or inside a character definition.

pk pre 247 i[1] k[1] x[k] ds [4] cs [4] hppp[4] vppp[4]. Preamble command. Here, i is the identification byte of the file, currently equal to 89. The string x is merely a comment, usually indicating the source of the file. The parameters ds and cs are the design size of the file in 1/2^{16} points, and the checksum of the file, respectively. The checksum should match the file and the files for this font. Parameters hppp and vppp are the ratios of pixels per point, horizontally and vertically, multiplied by 2^{16}; they can be used to correlate the font with specific device resolutions, magnifications, and “at sizes”. Usually, the name of the file is formed by concatenating the font name (e.g., amr10) with the resolution at which the font is prepared in pixels per inch multiplied by the magnification factor, and the letters . For instance, amr10 at 300 dots per inch should be named AMR10.300PK; at one thousand dots per inch and magstephalf, it should be named AMR10.1095PK.

18. We put a few of the above opcodes into definitions for symbolic use by this program.

define pk id = 89 { the version of file described } define pk xxx1 = 240 { special commands } define pk yyy = 244 { numspecial commands } define pk post = 245 { postamble } define pk no op = 246 { no operation } define pk pre = 247 { preamble } 19. The format has two conflicting goals; to pack character raster and size information as compactly as possible, while retaining ease of translation into raster and other forms. A suitable compromise was found in the use of run-encoding of the raster information. Instead of packing the individual bits of the character, we instead count the number of consecutive ‘black’ or ‘white’ pixels in a horizontal raster row, and then encode this number. Run counts are found for each row, from the top of the character to the bottom. This is essentially the way the format works. Instead of presenting each row individually, however, let us concatenate all of the horizontal raster rows into one long string of pixels, and encode this row. With knowledge of the width of the bit-map, the original character glyph can be easily reconstructed. In addition, we do not need special commands to mark the end of one row and the beginning of the next.

Next, let us put the burden of finding the minimum bounding box on the part of the font generator, since the characters will usually be used much more often than they are generated. The minimum bounding box is the smallest rectangle which encloses all ‘black’ pixels of a character. Let us also eliminate the need for a special end of character marker, by supplying exactly as many bits as are required to fill the minimum bounding box, from which the end of the character is implicit.

Let us next consider the distribution of the run counts. Analysis of several dozen pixel files at 300 dots per inch yields a distribution peaking at four, falling off slowly until ten, then a bit more steeply until twenty, and then asymptotically approaching the horizontal. Thus, the great majority of our run counts will fit in a four-bit nybble. The eight-bit byte is attractive for our run-counts, as it is the standard on many systems; however, the wasted four bits in the majority of cases seems a high price to pay. Another possibility is to use a Huffman-type encoding scheme with a variable number of bits for each run-count; this was rejected because of the overhead in fetching and examining individual bits in the file. Thus, the character raster definitions in the file format are based on the four-bit nybble.

20. The analysis of the pixel files yielded another interesting statistic: fully 37% of the raster rows were duplicates of the previous row. Thus, the format allows the specification of repeat counts, which indicate how many times a horizontal raster row is to be repeated. These repeated rows are taken out of the character glyph before individual rows are concatenated into the long string of pixels.

For elegance, we disallow a run count of zero. The case of a null raster description should be gleaned from the character width and height being equal to zero, and no raster data should be read. No other zero counts are ever necessary. Also, in the absence of repeat counts, the repeat value is set to be zero (only the original row is sent.) If a repeat count is seen, it takes effect on the current row. The current row is defined as the row on which the first pixel of the next run count will lie. The repeat count is set back to zero when the last pixel in the current row is seen, and the row is sent out.

This poses a problem for entirely black and entirely white rows, however. Let us say that the current row ends with four white pixels, and then we have five entirely empty rows, followed by a black pixel at the beginning of the next row, and the character width is ten pixels. We would like to use a repeat count, but there is no legal place to put it. If we put it before the white run count, it will apply to the current row. If we put it after, it applies to the row with the black pixel at the beginning. Thus, entirely white or entirely black repeated rows are always packed as large run counts (in this case, a white run count of 54) rather than repeat counts.

21. Now let us turn our attention to the actual packing of the run counts and repeat counts into nybbles. There are only sixteen possible nybble values. We need to indicate run counts and repeat counts. Since the run counts are much more common, we will devote the majority of the nybble values to them. We therefore indicate a repeat count by a nybble of 14 followed by a packed number, where a packed number will be explained later. Since the repeat count value of one is so common, we indicate a repeat one command by a single nybble of 15. A 14 followed by the packed number 1 is still legal for a repeat one count, however. The run counts are coded directly as packed numbers.

For packed numbers, therefore, we have the nybble values 0 through 13. We need to represent the positive integers up to, say, 2^{31} − 1. We would like the more common smaller numbers to take only one or two nybbles, and the infrequent large numbers to take three or more. We could therefore allocate one nybble value to indicate a large run count taking three or more nybbles. We do this with the value 0.

22. We are left with the values 1 through 13. We can allocate some of these, say dyn f , to be one-nybble run counts. These will work for the run counts 1 . . dyn f . For subsequent run counts, we will use a nybble greater than dyn f , followed by a second nybble, whose value can run from 0 through 15. Thus, the two-byte nybble values will run from dyn f + 1 . . (13 − dyn f ) ∗ 16 + dyn f . We have our definition of large run count values now, being all counts greater than (13 − dyn f ) ∗ 16 + dyn f .

We can analyze our several dozen pixel files and determine an optimal value of dyn f , and use this value for all of the characters. Unfortunately, values of dyn f that pack small characters well tend to pack the large characters poorly, and values that pack large characters well are not efficient for the smaller characters. Thus, we choose the optimal dyn f on a character basis, picking the value which will pack each individual character in the smallest number of nybbles. Legal values of dyn f run from 0 (with no one-byte run counts) to 13 (with no two-byte run counts).

23. Our only remaining task in the coding of packed numbers is the large run counts. We use a scheme suggested by D. E. Knuth which will simply and elegantly represent arbitrarily large values. The general scheme to represent an integer i is to write its hexadecimal representation, with leading zeros removed. Then we count the number of digits, and prepend one less than that many zeros before the hexadecimal representation. Thus, the values from one to fifteen occupy one nybble; the values sixteen through 255 occupy three, the values 256 through 4095 require five, etc.

For our purposes, however, we have already represented the numbers one through (13−dyn f )∗16+dyn f . In addition, the one-nybble values have already been taken by our other commands, which means that only the values from sixteen up are available to us for long run counts. Thus, we simply normalize our long run counts, by subtracting (13−dyn f )∗16+dyn f +1 and adding 16, and then representing the result according to the scheme above.

24. The final algorithm for decoding the run counts based on the above scheme might look like this, assuming a procedure called pk nyb is available to get the next nybble from the file, and assuming that the global repeat count indicates whether a row needs to be repeated. Note that this routine is recursive, but since a repeat count can never directly follow another repeat count, it can only be recursive to one level.

function pk packed num: integer ; var i, j, k: integer ; begin i ← get nyb; if i = 0 then

begin repeat j ← get nyb; incr (i);

until j ≠ 0; while i > 0 do

begin j ← j ∗ 16 + get nyb; decr (i);

end; pk packed num ← j − 15 + (13 − dyn f ) ∗ 16 + dyn f ; end

else if i ≤ dyn f then pk packed num ← i

else if i < 14 then pk packed num ← (i − dyn f − 1) ∗ 16 + get nyb + dyn f + 1

else begin if i = 14 then repeat count ← pk packed num else repeat count ← 1; pk packed num ← pk packed num; end;

end; 25. For low resolution fonts, or characters with ‘gray’ areas, run encoding can often make the character many times larger. Therefore, for those characters that cannot be encoded efficiently with run counts, the format allows bit-mapping of the characters. This is indicated by a dyn f value of 14. The bits are packed tightly, by concatenating all of the horizontal raster rows into one long string, and then packing this string eight bits to a byte. The number of bytes required can be calculated by (width ∗ height + 7) div 8. This format should only be used when packing the character by run counts takes more bytes than this, although, of course, it is legal for any character. Any extra bits in the last byte should be set to zero.

26. At this point, we are ready to introduce the format for a character descripter. It consists of three parts: a flag byte, a character preamble, and the raster data. The most significant four nybbles of the flag byte yield the dyn f value for that character. (Notice that only values of 0 through 14 are legal for dyn f , with 14 indicating a bit mapped character; thus, the flag bytes do not conflict with the command bytes, whose upper nybble is always 15.) The next bit (with weight 16) indicates whether the first run count is a black count or a white count, with a one indicating a black count. For bit-mapped characters, this bit should be set to a zero. The next bit (with weight 8) indicates whether certain later parameters (referred to as size parameters) are given in one-byte or two-byte quantities, with a one indicating that they are in two-byte quantities. The last two bits are concatenated on to the beginning of the length parameter in the character preamble, which will be explained below.

However, if the last three bits of the flag byte are all set (normally indicating that the size parameters are two-byte values and that a 3 should be prepended to the length parameter), then a long format of the character preamble should be used instead of one of the short forms.

Therefore, there are three formats for the character preamble, and which one is used depends on the least significant three bits of the flag byte. If the least significant three bits are in the range zero through three, the short format is used. If they are in the range four through six, the extended short format is used. Otherwise, if the least significant bits are all set, then the long form of the character preamble is used. The preamble formats are explained below.

Short form: flag [1] pl [1] cc[1] tfm[3] dm[1] w[1] h[1] hoff [+1] voff [+1]. If this format of the character preamble is used, the above parameters must all fit in the indicated number of bytes, signed or unsigned as indicated. Almost all of the standard TEX font characters fit; the few exceptions are fonts such as . Extended short form: flag [1] pl [2] cc[1] tfm[3] dm[2] w[2] h[2] hoff [+2] voff [+2]. Larger characters use this extended format. Long form: flag [1] pl [4] cc[4] tfm[4] dx [4] dy [4] w[4] h[4] hoff [4] voff [4]. This is the general format which allows all of the parameters of the file format, including vertical escapement.

The flag parameter is the flag byte. The parameter pl (packet length) contains the offset of the byte following this character descripter, with respect to the beginning of the tfm width parameter. This is given so a reading program can, once it has read the flag byte, packet length, and character code (cc), skip over the character by simply reading this many more bytes. For the two short forms of the character preamble, the last two bits of the flag byte should be considered the two most-significant bits of the packet length. For the short format, the true packet length might be calculated as (flag mod 4) ∗ 256 + pl ; for the extended format, it might be calculated as (flag mod 4) ∗ 65536 + pl .

The w parameter is the width and the h parameter is the height in pixels of the minimum bounding box. The dx and dy parameters are the horizontal and vertical escapements, respectively. In the short formats, dy is assumed to be zero and dm is dy but in pixels; in the long format, dx and dy are both in pixels multiplied by 2^{16}. The hoff is the horizontal offset from the upper left pixel to the reference pixel; the voff is the vertical offset. They are both given in pixels, with right and down being positive. The reference pixel is the pixel which occupies the unit square in ; the reference point is the lower left hand corner of this pixel. (See the example below.)

27. TEX requires that all characters which have the same character codes modulo 256 also have the same tfm widths, and escapement values. The format does not itself make this a requirement, but in order for the font to work correctly with the TEX software, this constraint should be observed. The current version of TEX (1.5) cannot output character codes greater than 255 anyway.

Following the character preamble is the raster information for the character, packed by run counts or by bits, as indicated by the flag byte. If the character is packed by run counts and the required number of nybbles is odd, then the last byte of the raster description should have a zero for its least significant nybble.

28. As an illustration of the format, the character Ξ from the font amr10 at 300 dots per inch will be encoded. This character was chosen because it illustrates some of the borderline cases. The raster for the character looks like this (the row numbers are chosen for convenience, and are not ’s row numbers.)

0  MMMMMMMMMMMMMMMMMMMM
1  MMMMMMMMMMMMMMMMMMMM
2  MMMMMMMMMMMMMMMMMMMM
3  MMMMMMMMMMMMMMMMMMMM
4  MM  MM
5  MM  MM
6  MM  MM

7 8

9  MM  MM
10  MM  MM
11  MM  MM
12  MMMMMMMMMMMMMMMM
13  MMMMMMMMMMMMMMMM
14  MMMMMMMMMMMMMMMM
15  MMMMMMMMMMMMMMMM
16  MM  MM
17  MM  MM
18  MM  MM

19 20 21

22  MM  MM
23  MM  MM
24  MM  MM
25  MMMMMMMMMMMMMMMMMMMM
26  MMMMMMMMMMMMMMMMMMMM
27  MMMMMMMMMMMMMMMMMMMM
28 * MMMMMMMMMMMMMMMMMMMM

The width of the minimum bounding box for this character is 20; its height is 29. The ‘*’ represents the reference pixel; notice how it lies outside the minimum bounding box. The hoff value is −2, and the voff is 28.

The first task is to calculate the run counts and repeat counts. The repeat counts are placed at the first transition (black to white or white to black) in a row, and are enclosed in brackets. White counts are enclosed in parentheses. It is relatively easy to generate the counts list:

82 [2] (16) 2 (42) [2] 2 (12) 2 (4) [3] 16 (4) [2] 2 (12) 2 (62) [2] 2 (16) 82

Note that any duplicated rows that are not all white or all black are removed before the repeat counts are calculated. The rows thus removed are rows 5, 6, 10, 11, 13, 14, 15, 17, 18, 23, and 24.

29. The next step in the encoding of this character is to calculate the optimal value of dyn f . The details of how this calculation is done are not important here; suffice it to say that there is a simple algorithm which in one pass over the count list can determine the best value of dyn f . For this character, the optimal value turns out to be 8 (atypically low). Thus, all count values less than or equal to 8 are packed in one nybble; those from nine to (13 − 8) ∗ 16 + 8 or 88 are packed in two nybbles. The run encoded values now become (in hex, separated according to the above list):

                               D9 E2 97 2 B1 E2 2 93 2 4 E3
                               97 4 E2 2 93 2 C5 E2 2 97 D9

which comes to 36 nybbles, or 18 bytes. This is shorter than the 73 bytes required for the bit map, so we use the run count packing.

30. The short form of the character preamble is used because all of the parameters fit in their respective lengths. The packet length is therefore 18 bytes for the raster, plus eight bytes for the character preamble parameters following the character code, or 26. The tfm width for this character is 640796, or 9C71C in hexadecimal. The horizontal escapement is 25 pixels. The flag byte is 88 hex, indicating the short preamble, the black first count, and the dyn f value of 8. The final total character packet, in hexadecimal, is:

Flag byte 88
Packet length 1A
Character code 04
tfm width 09 C7 1C
Horizontal escapement (pixels) 19
Width of bit map 14
Height of bit map 1D
Horizontal offset (signed) FE
Vertical offset 1C
Raster data D9 E2 97

                                                      2B 1E 22
                                                      93 24 E3
                                                      97 4E 22
                                                      93 2C 5E
                                                      22 97 D9

31. This format was written by Tomas Rokicki in August, 1985.

§32  PXtoPK  INPUT AND OUTPUT 13

32. Input and output. There are three types of files that this program must deal with—standard text files, files of integers (pixel files), and files of bytes (packed files.) For our purposes, we shall consider an eight-bit byte to consist of the values 0 . . 255. If your system does not pack these values to a byte, it is no major difficulty; you must only insure that the output routine pk byte converts the value to the appropriate type before sending it to the file. ⟨ Types in the outer block 9 ⟩ +≡

eight bits = 0 . . 255; { packed file byte }

word file = packed file of integer ; { for pixel file words }

byte file = packed file of eight bits ; { for packed file words }

33. ⟨ Globals in the outer block 11 ⟩ +≡ pxl file: word file; { where the input comes from } pk file: byte file; { where the final output goes }

34. To prepare these files for input, we reset them. An extension of Pascal is needed in the case of pxl file, since we want to associate it with external files whose names are specified dynamically (i.e., not known at compile time). The following code assumes that ‘reset (f, s)’ does this, when f is a file variable and s is a string variable that specifies the file name. If eof (f) is true immediately after reset (f, s) has acted, we assume that no file named s is accessible. procedure open pxl file; { prepares to read packed bytes in a pxl file }

begin reset (pxl file, pxl name); eof pixel ← eof (pxl file);

end; procedure open pk file; { prepares the output for writing }

begin rewrite(pk file, pk name);

end;

35. We need a place to store the names of the input and output file, as well as a character counter for the output file and a line position variable. ⟨ Globals in the outer block 11 ⟩ +≡ pxl name, pk name: packed array [1 . . name length] of char ; { name of input and output files } pk loc: integer ; { how many bytes have we sent? }

36. ⟨ Set initial values 12 ⟩ +≡ pk loc ← 0;

37. We need a function that will read in a word from the file. If the particular system requires buffering, here is the place to do it. It also sets a global flag eof pixel when it reaches the end of the file. If this flag is set on entrance to load pxl file, it is assumed that the file is bad. function pixel integer : integer ;

var i: integer ;

begin i ← pxl file↑; get (pxl file); eof pixel ← eof (pxl file); pixel integer ← i; end;

38. ⟨ Globals in the outer block 11 ⟩ +≡ eof pixel : boolean; { true when end of pixel file is reached. }

14  INPUT AND OUTPUT  PXtoPK §39

39. We also need a few routines to write data to the file. We write data in 4-, 8-, 16-, 24-, and 32-bit chunks, so we define the appropriate routines. We must be careful not to let the sign bit mess us up, as some Pascal’s implement division of a negative integer differently. We define a constant to help us with the sign manipulations. ⟨ Constants in the outer block 6 ⟩ +≡

one fourth = 1073741824; { two to the thirtieth }

40. procedure pk byte(b : integer );

begin if b < 0 then b ← b + 256; pk file↑ ← b; put (pk file); incr (pk loc); end;

procedure pk halfword (a : integer ); begin if a < 0 then a ← a + 65536; pk byte(a div 256); pk byte(a mod 256); end;

procedure pk three bytes (a : integer ); begin pk byte(a div 65536 mod 256); pk byte(a div 256 mod 256); pk byte(a mod 256); end;

procedure pk word (a : integer ); var b: integer ; begin if a < 0 then

begin a ← a + one fourth + one fourth; b ← 128 + a div 16777216; end

else b ← a div 16777216; pk byte(b); pk byte(a div 65536 mod 256); pk byte(a div 256 mod 256); pk byte(a mod 256); end;

procedure pk nyb(a : integer );

begin if bit weight = 16 then begin output byte ← a ∗ 16; bit weight ← 1; end

else begin pk byte(output byte + a); bit weight ← 16;

end; end;

41. We need the globals bit weight and output byte for buffering. ⟨ Globals in the outer block 11 ⟩ +≡ bit weight : integer ; { output bit weight } output byte: integer ; { output byte for pk file } 42. Here is a procedure that reads the file into memory, and sets the dir ptr to the proper place. It only checks that the first and last bytes of the file contain pxl id . procedure load pxl file; { read in the pixel data }

label 9997, { used for a bad format }

9999; { used for normal completion } var k: integer ; { index for word moves } begin open pxl file; k ← 0; if eof pixel then goto 9997; while ¬eof pixel do

begin mem[k] ← pixel integer ; k ← k + 1;

if k > max mem size then abort (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); end;

print ln((4 ∗ k) : 1, ´ ␣ ␣ ␣ ␣ ␣ ´ ); if k + 10000 > max mem size then abort (´ ␣ ´ ´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); next mem free ← k; k ← k − 1; if (mem[k] ≠ pxl id ) ∨ (mem[0] ≠ pxl id ) then goto 9997; goto 9999;

9997: abort (´ ␣ ␣ ␣ ´ ); 9999: dir ptr ← mem[k − 1];

end;

43. We need to declare the mem array and a few other variables. ⟨ Globals in the outer block 11 ⟩ +≡ mem: array [0 . . max mem size] of integer ; { memory array } next mem free: integer ; { next memory location available } dir ptr : integer ; { points to the directory of the pixel file }

16  WRITING THE PACKED FILE  PXtoPK §44

44. Writing the packed file. Next we have some bit manipulation routines we need. function hi (a : integer ): integer ;

begin hi ← a div 65536; end;

function lo(a : integer ): integer ; begin lo ← a mod 65536; end;

function his (a : integer ): integer ; begin if a < 0 then his ← (a + one fourth + one fourth) div 65536 − 32768 else his ← a div 65536; end;

function hip(a : integer ): integer ; begin if a < 0 then hip ← (a + one fourth + one fourth) div 65536 + 32768 else hip ← a div 65536; end;

function lop(a : integer ): integer ; begin lop ← a − 65536 ∗ his (a); end;

function los (a : integer ): integer ; var b: integer ; begin b ← lop(a); if b > 32767 then los ← b − 65536 else los ← b; end;

45. We now need a few definitions to make access of the pixel file simpler.

define x size ≡ hi (mem[dir ptr ]) { sizes } define y size ≡ lo(mem[dir ptr ]) define x offset ≡ his (mem[dir ptr + 1]) { offsets } define y offset ≡ los (mem[dir ptr + 1]) define raster pointer ≡ mem[dir ptr + 2] { raster pointer } define tfm width ≡ mem[dir ptr + 3] { tfm width } define checksum ≡ mem[dir ptr + 512] { checksum at end of directory } define magnification ≡ mem[dir ptr + 513] define design size ≡ mem[dir ptr + 514]

46. Now we write the preamble. First, we must determine if we can use eight bit sizes and offsets, or if we need sixteen bits. Then, we simply copy some data from the pixel file to the packed file. Since pixel files are assumed to be square, we simply write the horizontal magnification factor out as the vertical magnification factor.

define preamble comment ≡ ´ ␣ ␣ ´ define comm length = 17

procedure write preamble; var i: integer ; { general purpose index } begin open pk file; pk byte(pk pre); pk byte(pk id ); pk byte(comm length); for i ← 1 to comm length do pk byte(xord [comment [i]]); pk word (design size); pk word (checksum); pk word (hppp); pk word (hppp); end;

§47  PXtoPK  WRITING THE PACKED FILE 17

47. We define a few globals to maintain some of this data. ⟨ Globals in the outer block 11 ⟩ +≡ car : integer ; { a global character pointer } hppp: integer ; { horizontal pixels per point } comment : packed array [1 . . comm length] of char ;

48. We initialize the comment array: ⟨ Set initial values 12 ⟩ +≡

comment ← preamble comment ;

49. The write postamble procedure is very simple, having just to write the pk post command, followed by enough pk no op’s to make the file a multiple of four bytes long.Σ procedure write postamble;

begin pk byte(pk post );

while (pk loc mod 4 ≠ 0) do pk byte(pk no op);

18  PACKING AND SHIPPING CHARACTER DATA  PXtoPK §50

print ln(pk loc : 1, ´ ␣ ␣ ␣ ␣ ␣ ´ ); end; 50. Packing and shipping character data. Now we have the meat of the program—where we actually pack and send a character to the pk file. First, we determine if we can use repeat commands by looking for repeated raster rows that are not all zeros or all ones. Next, we create a list of bit counts in the mem array, starting with white bits (if any) and continuing until the end of the character. We determine the length of the character in the packed form, and compare it with the length in a bit-packed form, and send out the smaller of the two.

51. First, we need a routine to compare two raster rows and tell us if they are the same. function equal (row1 , row2 : integer ): boolean;

var i: integer ; { index }

temp: boolean; begin i ← width; temp ← true; while (i > 0) ∧ temp do

begin if mem[row1 ] ≠ mem[row2 ] then temp ← false;

incr (row1 ); incr (row2 ); i ← i − 32;

end; equal ← temp; end;

52. We now declare a few variables to contain the character width, height, offsets, and raster pointer. ⟨ Globals in the outer block 11 ⟩ +≡ width: integer ; { width of current character } height : integer ; { height of current character } c x off : integer ; { x offset of current character } c y off : integer ; { y offset of current character }

53. Now we supply the actual routine that compresses and ships the character. We also calculate the horizontal escapement in pixels for the character here. Since the pixel file format does not supply this information, we approximate it like pixel-file reading drivers have to be rounding the width. procedure ship character ;

var c raster : integer ; { pointer to raster data of character } word width: integer ; { width of character in 32-bit words } comp size: integer ; { size of compressed representation } hor esc: integer ; { horizontal escapement value } ⟨ Locals to ship character 56 ⟩ begin hor esc ← round (pxl conv ∗ tfm width); width ← x size; height ← y size; c x off ← x offset ; c y off ← y offset ; c raster ← raster pointer ; word width ← (width + 31) div 32; ⟨ Create repeat list 55 ⟩; ⟨ Create bit counts 60 ⟩; ⟨ Calculate dyn f and packed size and write character 63 ⟩; end;

§55  PXtoPK  PACKING AND SHIPPING CHARACTER DATA 19

54. The pxl conv variable should be a global. ⟨ Globals in the outer block 11 ⟩ +≡ pxl conv : real ; { converts TFM widths to pixels } 55. Our first task is to create the list of repeated raster rows. To do this, we first create a row of all zeros and a row of all ones to insure that we do not flag on these. Next, we simply walk through the raster representation, looking for duplicates, and flag them as equal. Finally, we walk through this preliminary repeat list and add up all successive equal rows. ⟨ Create repeat list 55 ⟩ ≡

zero row ← next mem free; ones row ← next mem free + word width;

repeat pointer ← ones row + word width; bit counts ← repeat pointer + height + 1; for i ← zero row to ones row − 1 do mem[i] ← 0; for i ← ones row to repeat pointer − 2 do mem[i] ← −1; i ← width mod 32; if i = 0 then mem[repeat pointer − 1] ← −1 else if i = 1 then mem[repeat pointer − 1] ← −one fourth − one fourth

else mem[repeat pointer − 1] ← −power [32 − i]; i ← 0; j ← height ; while i < j do

begin if equal (i ∗ word width + c raster , zero row ) then mem[repeat pointer + i] ← 0 else if equal (i ∗ word width + c raster , ones row ) then mem[repeat pointer + i] ← 0

else if i + 1 = j then mem[repeat pointer + i] ← 0

else if equal (i ∗ word width + c raster , (i + 1) ∗ word width + c raster ) then

mem[repeat pointer + i] ← 1 else mem[repeat pointer + i] ← 0;

incr (i); end;

i ← 0;

while i < j do begin k ← i; while mem[repeat pointer + k] = 1 do incr (k); mem[repeat pointer + i] ← k − i; i ← k + 1; end;

mem[repeat pointer + i] ← 0

This code is used in section 53.

56. Of course, we declare some of these locals. ⟨ Locals to ship character 56 ⟩ ≡ i, j, k: integer ; { index variables } zero row : integer ; { points to the row of zeros } ones row : integer ; { points to the row of ones } repeat pointer : integer ; { points to the repeat list } bit counts : integer ; { points to the bit count list } bits smaller : boolean; { indicates that bit mapping is shorter } final size: integer ; { final total size of character }

See also sections 62, 65, and 72. This code is used in section 53.

57. We also need the power array, which contains powers of two. ⟨ Globals in the outer block 11 ⟩ +≡ power : array [0 . . 31] of integer ; 58. ⟨ Set initial values 12 ⟩ +≡

power [0] ← 1; for i ← 1 to 30 do power [i] ← power [i − 1] ∗ 2; power [31] ← −power [i − 1] − power [i − 1];

59. Now we scan the raster representation, skipping any rows which are repeated from previous rows, and put this information in the mem array starting after bit counts . A 0 terminates the list. The basic approach is quite simple, but first we need a few definitions to make the type of bit returned more readable.

define black = 1 define white = 0 define end of glyph = 2

60. And now the actual routine. ⟨ Create bit counts 60 ⟩ ≡

repeat flag ← 0; bit ptr ← width − 1; cur repeat ← repeat pointer ; end raster ← c raster + height ∗ word width; cur ptr ← bit counts ; count ← 0; test ← white; repeat ⟨ Get bit, skipping repeated rows 61 ⟩;

if bit = test then incr (count )

else begin mem[cur ptr ] ← count ; incr (cur ptr ); if cur ptr + 3 > max mem size then abort (´ ␣ ␣ ␣ ␣ ␣ ␣ ´ ); count ← 1; test ← bit ; if repeat flag > 0 then

begin mem[cur ptr ] ← −repeat flag ; repeat flag ← 0; incr (cur ptr ); end; end;

until test = end of glyph; mem[cur ptr ] ← 0; mem[cur ptr + 1] ← 0

This code is used in section 53.

61. Of course, there is still that get bit macro that needs to be defined. We simply pull the bits off one by one, checking the repeat flag and end of glyph. ⟨ Get bit, skipping repeated rows 61 ⟩ ≡

incr (bit ptr );

if bit ptr = width then begin bit mod 32 ← 0; bit ptr ← 0; if mem[cur repeat ] > 0 then

begin repeat flag ← mem[cur repeat ]; cur repeat ← cur repeat + repeat flag ; c raster ← c raster + word width ∗ repeat flag ; end;

incr (cur repeat );

end; decr (bit mod 32 ); if bit mod 32 = −1 then

begin bit mod 32 ← 31; word ← mem[c raster ]; incr (c raster ); end;

if c raster > end raster then bit ← end of glyph else if bit mod 32 = 31 then

begin if word < 0 then begin bit ← black ; word ← word + one fourth + one fourth; end

else bit ← white;

end else begin if word ≥ power [bit mod 32 ] then

begin word ← word − power [bit mod 32 ]; bit ← black ; end

else bit ← white;

end

This code is used in section 60.

62. Now for all of those many locals used but not defined: ⟨ Locals to ship character 56 ⟩ +≡ count : integer ; { counts the number of bits } test : integer ; { what bits we are counting } cur ptr : integer ; { where to put the counts } bit : integer ; { a variable to return the type of bit } repeat flag : integer ; { indicates this row is to be repeated. } word : integer ; { current word to extract bits from } bit ptr : integer ; { a bit counter in horizontal bits } bit mod 32 : integer ; { the power of two to look for } cur repeat : integer ; { index into repeat array } end raster : integer ; { the end of the character raster representation } 63. Here is another piece of rather intricate code. Here we determine the smallest size in which we can pack the data, calculating dyn f in the process. To do this, we calculate the size required if dyn f is 0, and put this in comp size. Then, we calculate the changes in the size for each increment of dyn f , and stick these values in the deriv array. Finally, we scan through this array, and find the final minimum value, which we then use to send the character data. ⟨ Calculate dyn f and packed size and write character 63 ⟩ ≡

for i ← 1 to 13 do deriv [i] ← 0; first on ← mem[bit counts ] = 0; if first on then incr (bit counts ); i ← bit counts ; comp size ← 0; while mem[i] ≠ 0 do ⟨ Process count for best dyn f value 64 ⟩; b comp size ← comp size; dyn f ← 0; for i ← 1 to 13 do

begin comp size ← comp size + deriv [i];

if comp size ≤ b comp size then begin b comp size ← comp size; dyn f ← i; end;

end; comp size ← (b comp size + 1) div 2; if (comp size > (height ∗ width + 7) div 8) ∨ (height ∗ width = 0) then

begin comp size ← (height ∗ width + 7) div 8; dyn f ← 14; end;

⟨ Write character preamble 66 ⟩; if dyn f ≠ 14 then ⟨ Send compressed format 70 ⟩ else ⟨ Send bit map 71 ⟩; if pred pk loc ≠ pk loc then abort (´ ␣ ␣ ␣ ␣ ␣´ , car : 1)

This code is used in section 53.

64. When we enter this module, we have a count, at mem[i]. First, we add to the comp size the number of nybbles that this count would require, assuming dyn f to be zero. Since when dyn f is zero, there are no one nybble counts, we simply check the two-nybble counts, and then the extensible counts.

Next, we take the count value and determine the value of dyn f (if any) that would cause this count to take either more or less nybbles. If a valid value for dyn f exists in this range, we accumulate this change in the deriv array.

We know that a repeat count of one will not change the length of the raster representation, no matter what dyn f is, because it is always represented by the nybble 15, so we do that as a special case. ⟨ Process count for best dyn f value 64 ⟩ ≡

begin j ← mem[i];

if j = −1 then incr (comp size)

else begin if j < 0 then begin incr (comp size); j ← −j; end;

if j < 209 then comp size ← comp size + 2 else begin k ← j − 193; while k ≥ 16 do

begin k ← k div 16; comp size ← comp size + 2;

end; comp size ← comp size + 1; end;

if j < 14 then decr (deriv [j])

else if j < 209 then incr (deriv [(223 − j) div 15])

else begin k ← 16; while (k ∗ 16 < j + 3) do k ← k ∗ 16; if j − k ≤ 192 then deriv [(207 − j + k) div 15] ← deriv [(207 − j + k) div 15] + 2; end;

end; incr (i); end

This code is used in section 63.

65. We need a handful of locals: ⟨ Locals to ship character 56 ⟩ +≡ dyn f : integer ; { packing value } deriv : array [1 . . 13] of integer ; { derivative } b comp size: integer ; { best size } first on: boolean; { indicates that the first bit is on } flag byte: integer ; { flag byte for character } state: boolean; { state variable } on: boolean; { white or black? } 66. Now we write the character preamble information. First we need to determine which of the three formats we should use. ⟨ Write character preamble 66 ⟩ ≡

flag byte ← dyn f ∗ 16; if first on then flag byte ← flag byte + 8; if (tfm width > 16777215) ∨ (tfm width < 0) ∨ (hor esc < 0) ∨ (comp size > 196579) ∨ (width > 65535) ∨

(height > 65535) ∨ (c x off > 32767) ∨ (c y off > 32767) ∨ (c x off < −32768) ∨ (c y off < −32768) then ⟨ Write long character preamble 67 ⟩

else if (hor esc > 255) ∨ (width > 255) ∨ (height > 255) ∨ (c x off > 127) ∨ (c y off > 127) ∨ (c x off <

−128) ∨ (c y off < −128) ∨ (comp size > 1016) then ⟨ Write two-byte short character preamble 69 ⟩

else ⟨ Write one-byte short character preamble 68 ⟩

This code is used in section 63.

67. Here we have determined that we must write a long character preamble. We adjust a few parameters, and then must write the data. ⟨ Write long character preamble 67 ⟩ ≡

begin flag byte ← flag byte + 7; pk byte(flag byte); comp size ← comp size + 28; pk word (comp size); pk word (car ); pred pk loc ← pk loc + comp size; pk word (tfm width); pk word (hor esc ∗ 65536); pk word (0); pk word (width); pk word (height ); pk word (c x off ); pk word (c y off ); end

This code is used in section 66.

68. Here we write a short short character preamble, with one-byte size parameters. ⟨ Write one-byte short character preamble 68 ⟩ ≡

begin comp size ← comp size + 8; flag byte ← flag byte + comp size div 256; pk byte(flag byte); pk byte(comp size mod 256); pk byte(car ); pred pk loc ← pk loc + comp size; pk three bytes (tfm width); pk byte(hor esc); pk byte(width); pk byte(height ); pk byte(c x off ); pk byte(c y off ); end

This code is used in section 66.

69. Here we write a long short character preamble, with two-byte size parameters. ⟨ Write two-byte short character preamble 69 ⟩ ≡

begin comp size ← comp size + 13; flag byte ← flag byte + comp size div 65536 + 4; pk byte(flag byte); pk halfword (comp size mod 65536); pk byte(car ); pred pk loc ← pk loc + comp size; pk three bytes (tfm width); pk halfword (hor esc); pk halfword (width); pk halfword (height ); pk halfword (c x off ); pk halfword (c y off ); end

This code is used in section 66.

70. At this point, we have decided that the run-encoded format is smaller. (This is almost always the case.) We send out the data, a nybble at a time. ⟨ Send compressed format 70 ⟩ ≡

begin bit weight ← 16; max 2 ← 208 − 15 ∗ dyn f ; i ← bit counts ; while mem[i] ≠ 0 do

begin j ← mem[i]; if j = −1 then pk nyb(15) else begin if j < 0 then

begin pk nyb(14); j ← −j;

end; if j ≤ dyn f then pk nyb(j) else if j ≤ max 2 then

begin j ← j − dyn f − 1; pk nyb(j div 16 + dyn f + 1); pk nyb(j mod 16); end

else begin j ← j − max 2 + 15; k ← 16;

while k ≤ j do begin k ← k ∗ 16; pk nyb(0); end;

while k > 1 do begin k ← k div 16; pk nyb(j div k); j ← j mod k; end; end;

end; incr (i); end;

if bit weight ≠ 16 then pk byte(output byte); end

This code is used in section 63.

71. This macro is for the case where we have decided to send the character raster packed bit-wise. It uses the bit counts as well, sending eight at a time. Here we have a miniature packed format interpreter, as we must repeat any rows that are repeated. The algorithm to do this was a lot of fun to generate. Can you figure out how it works? ⟨ Send bit map 71 ⟩ ≡

begin buff ← 0; p bit ← 8; i ← bit counts ; h bit ← width; on ← ¬first on; state ← false; count ← 0; repeat flag ← 0; while (mem[i] ≠ 0) ∨ state ∨ (count > 0) do

begin if state then

begin count ← r count ; i ← r i ; on ← r on; decr (repeat flag ); end

else begin r count ← count ; r i ← i; r on ← on;

end; ⟨ Send one row by bits 73 ⟩; if state ∧ (repeat flag = 0) then

begin count ← s count ; i ← s i ; on ← s on; state ← false; end

else if ¬state ∧ (repeat flag > 0) then begin s count ← count ; s i ← i; s on ← on; state ← true; end;

end; if p bit ≠ 8 then pk byte(buff ); end

This code is used in section 63.

72. All of the remaining locals: ⟨ Locals to ship character 56 ⟩ +≡ h bit : integer ; { what bit in the character are we on? } p bit : integer ; { what bit are we about to send out? } r on, s on: boolean; { state saving variables } r count , s count : integer ; { ditto } r i , s i : integer ; { and again. } max 2 : integer ; { the highest count that fits in two bytes } pred pk loc: integer ; { where we think the character will end } buff : integer ; { buffer for byte output } 73. We are at the beginning of a row; we simply output the next width bits. We break the possibilities up into three cases; we finish a byte but not the row, we finish a row, and we finish neither a row nor a byte. But, first, we insure that we have a count value. ⟨ Send one row by bits 73 ⟩ ≡

repeat if count = 0 then

begin if mem[i] < 0 then begin if ¬state then repeat flag ← −mem[i]; incr (i); end;

count ← mem[i]; incr (i); on ← ¬on; end;

if (count ≥ p bit ) ∧ (p bit < h bit ) then begin { we end a byte, we don’t end the row } if on then buff ← buff + power [p bit ] − 1; pk byte(buff ); buff ← 0; h bit ← h bit − p bit ; count ← count − p bit ; p bit ← 8; end

else if (count < p bit ) ∧ (count < h bit ) then begin { we end neither the row nor the byte } if on then buff ← buff + power [p bit ] − power [p bit − count ]; p bit ← p bit − count ; h bit ← h bit − count ; count ← 0; end

else begin { we end a row and maybe a byte } if on then buff ← buff + power [p bit ] − power [p bit − h bit ]; count ← count − h bit ; p bit ← p bit − h bit ; h bit ← width; if p bit = 0 then

begin pk byte(buff ); buff ← 0; p bit ← 8; end;

end; until h bit = width

This code is used in section 71.

28  TERMINAL COMMUNICATION  PXtoPK §74

74. Terminal communication. We must get the file names and determine whether output is to be in hexadecimal or binary. To do this, we use the standard input path name. We need a procedure to flush the input buffer. For most systems, this will be an empty statement. For other systems, a print ln will provide a quick fix. We also need a routine to get a line of input from the terminal. On some systems, a simple read ln will do. Finally, a macro to print a string to the first blank is required.

define flush buffer ≡

begin end

define get line(#) ≡

if eoln(input ) then read ln(input ); i ← 1; while ¬(eoln(input ) ∨ eof (input )) do

begin #[i] ← input ↑; incr (i); get (input ); end;

        #[i] ← ´ ␣´

75. procedure dialog ;

var i: integer ; { index variable }

buffer : packed array [1 . . name length] of char ; { input buffer } begin for i ← 1 to name length do

begin pxl name[i] ← ´ ␣´ ; pk name[i] ← ´ ␣´ ;

end; print (´ ␣ ␣ ␣␣´ ); flush buffer ; get line(pxl name); print (´ ␣ ␣ ␣␣´ ); flush buffer ; get line(pk name); print ln(´ ␣´ ); end;

§76  PXtoPK  THE MAIN PROGRAM 29

76. The main program. Now that we have all the pieces written, let us put them together. begin initialize; dialog ; load pxl file; pxl conv ← (design size div 16)/65536.0 ∗ magnification/72.27/5242880.0; hppp ← round (magnification ∗ 65536/72.27/5); write preamble; for car ← 0 to 127 do

begin if raster pointer ≠ 0 then ship character ; dir ptr ← dir ptr + 4; end;

write postamble; final end : end.

30  SYSTEM-DEPENDENT CHANGES  PXtoPK §77

77. System-dependent changes. This section should be replaced, if necessary, by changes to the program that are necessary to make work at a particular installation. Any additional routines should be inserted here.

§78  PXtoPK  INDEX 31

78. Index. Pointers to error messages appear here together with the section numbers where each identifier is used.

abort : \underline{8}, 42, 60, 63. ASCII code: \underline{9}, 11. b: \underline{40}, \underline{44}. b comp size: 63, \underline{65}. banner : \underline{2}, 4. bit : 60, 61, \underline{62}. bit counts : 55, \underline{56}, 59, 60, 63, 70, 71. bit mod 32 : 61, \underline{62}. bit ptr : 60, 61, \underline{62}. bit weight : 40, \underline{41}, 70. bits smaller : \underline{56}. black : \underline{59}, 61. boolean: 38, 51, 56, 65, 72. buff : 71, \underline{72}, 73. buffer : 75. byte file: \underline{32}, 33. c raster : \underline{53}, 55, 60, 61. c x off : \underline{52}, 53, 66, 67, 68, 69. c y off : \underline{52}, 53, 66, 67, 68, 69. car : \underline{47}, 63, 67, 68, 69, 76. cc: 26. char : 10, 35, 47, 75. checksum: \underline{45}, 46. chr : 10, 11, 13. comm length: \underline{46}, 47. comment : 46, \underline{47}, 48. comp size: \underline{53}, 63, 64, 66, 67, 68, 69. count : 60, \underline{62}, 71, 73. cs : 17. cur ptr : 60, \underline{62}. cur repeat : 60, 61, \underline{62}. decr : \underline{7}, 24, 61, 64, 71. deriv : 63, 64, \underline{65}. design size: \underline{45}, 46, 76. dialog : \underline{75}, 76. dir ptr : 42, \underline{43}, 45, 76. dm: 26. do nothing : \underline{7}. ds : 17. dx : 26. dy : 26. dyn f : 22, 23, 24, 25, 26, 29, 30, 63, 64, \underline{65}, 66, 70. eight bits : \underline{32}. else: 3. end: 3. end of glyph: \underline{59}, 60, 61. end raster : 60, 61, \underline{62}. endcases: \underline{3}. eof : 34, 37, 74. eof pixel : 34, 37, \underline{38}, 42. eoln: 74. equal : \underline{51}, 55. false: 51, 71. final end : \underline{5}, 8, 76. final size: \underline{56}. first on: 63, \underline{65}, 66, 71. first text char : \underline{10}, 13. flag : 26. flag byte: \underline{65}, 66, 67, 68, 69. flush buffer : \underline{74}, 75. get : 37, 74. get line: \underline{74}, 75. get nyb: 24. h bit : 71, \underline{72}, 73. height : 25, \underline{52}, 53, 55, 60, 63, 66, 67, 68, 69. hi : \underline{44}, 45. hip: \underline{44}. his : \underline{44}, 45. hoff : 26, 28. hor esc: \underline{53}, 66, 67, 68, 69. hppp: 17, 46, \underline{47}, 76. i: \underline{4}, \underline{24}, \underline{37}, \underline{46}, \underline{51}, \underline{75}. incr : \underline{7}, 24, 40, 51, 55, 60, 61, 63, 64, 70, 73, 74. initialize: \underline{4}, 76. input : 4, 74. integer : 4, 24, 32, 35, 37, 40, 41, 42, 43, 44, 46, 47, 51, 52, 53, 56, 57, 62, 65, 72, 75.

jump out : \underline{8}.

k: \underline{42}.

Knuth, D. E.: 23. last text char : \underline{10}, 13. lo: \underline{44}, 45. load pxl file: 37, \underline{42}, 76. lop: \underline{44}. los : \underline{44}, 45. magnification: \underline{45}, 76. max m: 14. max mem size: \underline{6}, 42, 43, 60. max 2 : 70, \underline{72}. mem: 42, \underline{43}, 45, 50, 51, 55, 59, 60, 61, 63,

64, 70, 71, 73. min m: 14. name length: \underline{6}, 35, 75. next mem free: 42, \underline{43}, 55. on: \underline{65}, 71, 73. one fourth: \underline{39}, 40, 44, 55, 61. ones row : 55, \underline{56}. open pk file: \underline{34}, 46. open pxl file: \underline{34}, 42. ord : 11.

32  INDEX  PXtoPK §78

othercases: \underline{3}. others : 3. output : 4. output byte: 40, \underline{41}, 70. p bit : 71, \underline{72}, 73. pixel integer : \underline{37}, 42. pk byte: 32, \underline{40}, 46, 49, 67, 68, 69, 70, 71, 73. pk file: \underline{33}, 34, 40, 50. pk halfword : \underline{40}, 69. pk id : \underline{18}, 46. pk loc: \underline{35}, 36, 40, 49, 63, 67, 68, 69. pk name: 34, \underline{35}, 75. pk no op: 17, \underline{18}, 49. pk nyb: \underline{40}, 70. pk packed num: \underline{24}. pk post : 17, \underline{18}, 49. pk pre: 17, \underline{18}, 46. pk three bytes : \underline{40}, 68, 69. pk word : \underline{40}, 46, 67. pk xxx1 : 17, \underline{18}. pk yyy : 17, \underline{18}. pl : 26. power : 55, \underline{57}, 58, 61, 73. preamble comment : \underline{46}, 48. pred pk loc: 63, 67, 68, 69, \underline{72}. print : \underline{4}, 75. print ln: \underline{4}, 8, 42, 49, 74, 75. put : 40. : 42. pxl conv : 53, \underline{54}, 76. pxl file: \underline{33}, 34, 37. pxl id : \underline{14}, 42. pxl name: 34, \underline{35}, 75. PXtoPK : \underline{4}. r count : 71, \underline{72}. r i : 71, \underline{72}. r on: 71, \underline{72}. raster pointer : \underline{45}, 53, 76. read ln: 74. real : 54. repeat count : 24. repeat flag : 60, 61, \underline{62}, 71, 73. repeat pointer : 55, \underline{56}, 60. reset : 34. rewrite: 34. round : 53, 76. row1 : 51. row2 : 51. s count : 71, \underline{72}. s i : 71, \underline{72}. s on: 71, \underline{72}. scaled : 17. ship character : \underline{53}, 76. state: \underline{65}, 71, 73. system dependancies: 6, 32. system dependencies: 10, 33, 34, 37, 77. temp: 51. terminal line length: \underline{6}. test : 60, \underline{62}. text char : \underline{10}, 11. text file: \underline{10}. tfm: 26, 27, 30. tfm width: \underline{45}, 53, 66, 67, 68, 69. true: 51, 71. voff : 26, 28. vppp: 17. white: \underline{59}, 60, 61. width: 25, 51, \underline{52}, 53, 55, 60, 61, 63, 66, 67,

68, 69, 71, 73. word : 61, \underline{62}. word file: \underline{32}, 33. word width: \underline{53}, 55, 60, 61. write: 4. write ln: 4. write postamble: \underline{49}, 76. write preamble: \underline{46}, 76. x offset : \underline{45}, 53. x size: \underline{45}, 53. xchr : \underline{11}, 12, 13. xord : \underline{11}, 13, 46. y offset : \underline{45}, 53. y size: \underline{45}, 53. yyy : 17. zero row : 55, \underline{56}.

§78  PXtoPK  NAMES OF THE SECTIONS 33

⟨ Calculate dyn f and packed size and write character 63 ⟩ Used in section 53. ⟨ Constants in the outer block 6, 39 ⟩ Used in section 4.

⟨ Create bit counts 60 ⟩ Used in section 53.

⟨ Create repeat list 55 ⟩ Used in section 53. ⟨ Get bit, skipping repeated rows 61 ⟩ Used in section 60.

⟨ Globals in the outer block 11, 33, 35, 38, 41, 43, 47, 52, 54, 57 ⟩ Used in section 4.

⟨ Labels in the outer block 5 ⟩ Used in section 4.

⟨ Locals to ship character 56, 62, 65, 72 ⟩ Used in section 53.

⟨ Process count for best dyn f value 64 ⟩ Used in section 63.

⟨ Send bit map 71 ⟩ Used in section 63.

⟨ Send compressed format 70 ⟩ Used in section 63. ⟨ Send one row by bits 73 ⟩ Used in section 71.

⟨ Set initial values 12, 13, 36, 48, 58 ⟩ Used in section 4.

⟨ Types in the outer block 9, 10, 32 ⟩ Used in section 4. ⟨ Write character preamble 66 ⟩ Used in section 63. ⟨ Write long character preamble 67 ⟩ Used in section 66. ⟨ Write one-byte short character preamble 68 ⟩ Used in section 66. ⟨ Write two-byte short character preamble 69 ⟩ Used in section 66.

The PXtoPK processor

(Version 2.2, 15 August 1985)

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 The character set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3 Pixel file format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5 Packed file format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 6 Input and output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 13 Writing the packed file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 16 Packing and shipping character data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 18 Terminal communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 28 The main program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 29 System-dependent changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 30 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 31

The preparation of this report was supported in part by the National Science Foundation under grants IST-8201926 and MCS-8300984, and by the System Development Foundation. ‘TEX’ is a trademark of the American Mathematical Society.