2  INTRODUCTION  PXtoCH §1

1. Introduction. The utility program converts TEX raster pixel (“ ”) files into character pixel (“ ”) files. A file output by this program can be edited with a normal text editor, and the result can be converted back to format using the companion program .

The first program was designed by Lynn Ruggles in the winter of 1983. The programs and had a significant effect on the evolution of the present code. Most of the documentation is from David Fuchs’ description of PXL files.

Currently, only 128 characters are allowed in a font. The banner string defined here should be changed whenever gets modified. define banner ≡ ´ ␣ ␣ ␣ ␣ ´ { printed when the program starts }

2. This program is written entirely in standard PASCAL, except that it occasionally has lower case letters in strings that are output. Such letters can be converted to upper case if necessary. The input is read from pxl file, and the output is written on chr file; error messages and other remarks are written on the error file, which the user may choose to assign to the terminal if the system permits it.

The term print is used instead of write when this program writes on the error file, so that all such output can be easily deflected.

define print (#) ≡ write(error file, #) define print ln(#) ≡ write ln(error file, #)

program PXtoCH (pxl file, chr file, error file); const ⟨ Constants 20 ⟩ type ⟨ Types 6 ⟩ var ⟨ Global Variables 7 ⟩ procedure initialize;

begin ⟨ Reset input file 8 ⟩ ⟨ Reset error file 10 ⟩ print ln(banner ); file ok ← true; end;

3. Here are some macros for common programming idioms.

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

§4  PXtoCH  FONT METRIC DATA 3

4. Font metric data. The idea behind files is that typesetting routines like TEX need a compact way to store the relevant information about several dozen fonts, and computer centers need a compact way to store the relevant information about several hundred fonts. files are compact, and most of the information they contain is highly relevant, so they provide a solution to the problem.

However, sometimes Metafont does not produce very good fonts at a low resolution and the characters need some editing to make them readable, so the files are also provided. The file can be edited with a text editor and then converted back into a file.

5. A file is considered to be a series of 32-bit words (on 36-bit machines, the four low-order bits of each word are always zero). In the discussion below, “left half word” means the highest order 16 bits in a word, and “right half word” means the 16 next-highest order bits in the word (which are exactly the lowest order 16 bits on 32 bit machines).

The information in a file appears in a sequence of 8-bit bytes. Since the number of bytes is always a multiple of 4, we could also regard the file as a sequence of 32-bit words; but TEX uses the byte interpretation, and so does . Note that the bytes are all nonnegative and less than 2^{15}.

A file may contain raster information for as many as 128 characters and as few as 0 characters. An exception to these rules is planned for oriental fonts; such fonts, however, are not allowed by this version of .

Incidentally, when two or more 8-bit bytes are combined to form an integer of 16 or more bits, the most significant bytes appear first in the file. This is called BigEndian order.

6. ⟨ Types 6 ⟩ ≡ byte = 0 . . 255; { unsigned eight-bit quantity }

See also sections 21, 30, and 36. This code is used in section 2.

7. ⟨ Global Variables 7 ⟩ ≡ pxl file: packed file of 0 . . 255;

See also sections 9, 11, 13, 22, 31, 37, 39, 48, 51, 55, and 58. This code is used in section 2.

8. On some systems you may have to do something special to read a packed file of bytes. For example, the following code didn’t work when it was first tried at Stanford, because packed files have to be opened with a special switch setting on the PASCAL that was used. ⟨ Reset input file 8 ⟩ ≡

reset (pxl file);

This code is used in sections 2 and 44.

9. Additionally, an error file is provided which contains all error messages for each character. This file can be specified to be the terminal, in which case all the error messages will be displayed when the program is run. ⟨ Global Variables 7 ⟩ +≡ error file: text ;

10. ⟨ Reset error file 10 ⟩ ≡ rewrite(error file);

This code is used in section 2.

4  THE INPUT FILE CONTAINS THE FOLLOWING FIELDS  PXtoCH §11

11. The input file contains the following fields.

(1 word) is currently equal to 1001 decimal. (many words) All of the file from word 1 up to the Font Directory contains raster

descriptions. The raster description of a character is contained in consecutive words. Bits containing a 1 correspond to black pixels. The leftmost pixel of the top row of a character’s pixel representation corresponds to the most significant bit in the first word of its raster description. The next most significant bit in the first word corresponds to the next to leftmost pixel in its top row, and so on. If the character’s pixel width is greater than 32, the 33^{rd} bit in the top row corresponds to the most significant bit in the second word of its raster description. Each new raster row begins in a new word, so the final word for each row probably will not be full (unless the pixel width of the character is evenly divisible by 32). The most significant bits are the ones that are valid, and the unused low order bits will be zero. From this information, it can be seen that a character with pixel width w and pixel height h requires exactly ⌈w/32⌉ × h words for its raster description. As an example of the case where the pixel width is greater than 32, consider a character whose pixel width is 40 and whose pixel height is 30. The first word of its raster description contains the the leftmost 32 pixels of the top row in the character. The next word of the Raster Description contains the remaining 8 pixels of the first row of the character in its most significant 8 bits, with all remaining bits zero. The third word contains the left 32 pixels of the second row of the character, etc. So, each row takes 2 words, and there are 30 rows, so the raster description of this character requires 60 words.

(512 words) contains the directory information for all of the 128 possible characters. The first four words of the font directory have Directory Information about the character with ascii value of zero, the next four words are for the character with ascii value of one, etc. Any character not present in the font will have all four of its Directory Information words set to zero, so the Directory Information for the character with ascii value x will always be in words 4 × x through 4 × x + 3 of the font directory . For example, if the second to last word in a file contained the value 12000, then words 12324 through 12327 of the file contain information about the ascii character “Q”, since ascii “Q” = ’121 octal = 81 decimal, and 4 × 81 = 324. The meanings of a character’s four Directory words are described later in this document.

(1 word) should match the checksum in any file that refers to this font (otherwise TEX prepared the file under the wrong assumptions–it got the checksum from a file that doesn’t match this file). However, if this word is zero, no validity check will be made. In general, this number will appear to contain 32 bits of nonsense.

(1 word) is an integer representing 1000 times the magnification factor at which this font was produced. If the magnification factor is , the extension to the name of this file should be .

(1 word) Just as in the file, it is in units of es (2^{−20}) unmagnified points; remember that there are 72.27 points in an inch. The design size should also be indicated by the last characters of the ’s file name. The design size is not affected by the magnification. For instance, if the example font is CMR5 at 1.5 times regular size, then the file would be called , word 12513 would contain 1500, and word 12514 would contain 5 × 2^{20}.

(1 word) is a pointer to the Directory Information. If the number of words in the file is p (i.e. word numbers zero through p − 1) then Directory Information Pointer should equal p − 512 − 5. Note that all pointers are relative to the first word in the file, which is word zero.

(1 word) is currently = 1001 decimal (just like pxl id1 ). ⟨ Global Variables 7 ⟩ +≡ pxl id1 , checksum, magnification, design size, directory ptr , pxl id2 : integer ;

§12  PXtoCH  THE FONT DIRECTORY 5

12. The Font Directory. The Font Directory contains four words of information per character. There are six fields packed into these four words as follows:

: pxl width (16 bits), plus pxl height (16 bits) The character’s pixel width is in the left half-word, and its pixel height is in the right half-word. These numbers have no connection with the height and width that TEX thinks the character has (from the file); rather, they are the size of the smallest bounding-box that fits around the black pixels that form the character’s raster representation, i.e. the number of pixels wide and high that the character is. The pixel width is just large enough to encompass the leftmost and rightmost black pixels in the character. Likewise, the pixel height is just large enough to encompass the topmost and bottommost black pixels. In our Q example, its pixel width is 15 and its pixel height is 16, so word 12324 in the example file contains 15 × 2^{16} + 16.

: x offset (16 bits), plus y offset (16 bits) This word contains the offset of the character’s reference point from the upper-left-hand corner of the bounding box: the x offset in the left half-word, 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 offsets are in units of pixels. For the Q, the x offset is 2 and the y offset is 12, so word 12325 of the example file contains 2 × 2^{16} + 12.

: raster address (32 bits) The third word contains the number of the word in this file where the raster description for this character begins. This number is relative to the beginning of the file, the first word of which is numbered zero. The layout of raster descriptions is explained below. The raster descriptions of consecutive characters need not be in order within a file–for instance the raster description for character “Q” might be followed by the raster description of the character “A”. Of course, a single character’s raster description is always contained in consecutive words.

f a character is totally white then the third word contains a zero. (The pxl width, pxl height , x offset and y offset of a totally white character must be zero too, although the Width may be non-zero. A non-zero Width would mean that the character is a fixed width space. TEX’s standard Computer Modern fonts do not contain any such characters.) For the “Q” example, word 12326 might contain any number from 0 thru 12000 − 16 (since Q’s raster description is 16 words long), let’s say it is 600.

: tfm width (32 bits) The fourth word contains the tfm width of the character. That is the width that TEX thinks the character is (exactly as in the file). The width is expressed in es, which are 1/(2^{20})^{th} of the design size. The tfm width does not take into account the magnification at which the file was prepared. Thus, if “Q” had a width of 7 points in a 12 point font, word 327 in the file would contain ⌊(7/12) × 2^{20}⌋. See the documentation for more information on es.

13. So that is what  files hold. The next question is, “What about  files?” A complete answer to

that question appears in the documentation of the companion program, , so it will not be repeated here. Suffice it to say that a file is an ordinary text file. The format is almost self-explanatory when you see an example or two. ⟨ Global Variables 7 ⟩ +≡ chr file: text ;

6  USEFUL SUBROUTINES  PXtoCH §14

14. Useful subroutines. Here we put some subroutines which will be used later in the program. First we define some functions to simplify reading in the pxl file one byte at a time and converting it to

words or halfwords. Read halfword reads in two bytes from pxl file. function read halfword : integer ;

var word1 , word2 : byte; begin read (pxl file, word1 ); read (pxl file, word2 ); read halfword ← word1 ∗ two 8 + word2 ; end;

15. Read word reads in four bytes from pxl file. function read word : integer ;

var i: integer ; word1 : byte; word2 : integer ; begin word2 ← 0; for i ← 1 to 4 do

begin read (pxl file, word1 );

word2 ← word2 ∗ two 8 + word1 ; end;

read word ← word2 ; end;

16. Read byte reads in one byte from pxl file. function read byte: integer ;

var word1 : integer ; begin read (pxl file, word1 ); read byte ← word1 ; end;

17. Here we also define two other procedures, max and min, which will be used later. As the name implies, max returns the larger of two integers. function max (m, n : integer ): integer ;

begin if m > n then max ← m else max ← n; end;

18. And min returns the smaller of two integers. function min(m, n : integer ): integer ;

begin if m > n then min ← n else min ← m; end;

19. One other useful routine returns the ceiling of (num/divisor). function ceiling (num : integer ; divisor : integer ): integer ;

§20  PXtoCH  THE FIRST PASS ON A PXL FILE 7

begin if num mod divisor > 0 then ceiling ← num div divisor + 1 else ceiling ← num div divisor ; end; 20. The first pass on a PXL file. This is the first of three sections. It reads in the pxl file and checks for errors and returns a flag, file ok , indicating whether anything is wrong with the file. If the file is ok, the font information is saved. Because the pxl file contains all of the size information needed by this program at the end of the file, the file must be read in twice; the first time, the raster information is ignored and the font information is saved.

define field size = 4 { number of fields per character } define num chrs = 128 { number of characters } define font fields = 512 { field size × num chrs } define pxl num = 1034 { (font fields + end num) ×2 } define init num = 1 { words of information at beginning of file } define end num = 5 { words of information at end of file } define save end num = 10 { end num ×2 }

⟨ Constants 20 ⟩ ≡ tbl size = font fields ; { size of table needed to hold font info } init size = init num; { words of info at beginning of file } end size = save end num; { halfwords of info at end of file } pxl size = pxl num; { size of pxl array } font size = num chrs ; { size of fnt info array } two 7 = ´ 200 ; two 8 = ´ 400 ; two 15 = ´ 100000 ; two 16 = ´ 200000 ; two 20 = ´ 4000000 ;

See also sections 29, 35, and 50. This code is used in section 2.

21. ⟨ Types 6 ⟩ +≡ halfword = 0 . . ´ 77777 ; { unsigned sixteen-bit quantity } pxl index = 1 . . pxl size; { address of a half word in pxl }

22. ⟨ Global Variables 7 ⟩ +≡ pxl : array [pxl index ] of integer ; { used to store the last 517 words of pxl file (in halfwords) } pxl ptr : integer ; { an index into pxl } file size, max width, max height : integer ; { save extreme values from pxl file } file ok : boolean; { was the file ok? } too short : boolean; { or was it too short? }

23. The input may, of course, be all screwed up and not a file at all. So we begin cautiously.

define abort (#) ≡ begin print ln(#);

        print ln(´ ␣   ␣ ␣   ´    ´ ␣  ␣   ␣   ␣   ␣    ␣    ␣  ␣ ␣   ␣  ´ );

file ok ← false;

end

define error (#) ≡ print ln(#)

24. Now, we read in the first word in the file which should be equal to 1001 decimal. If it isn’t, we could be reading the wrong type of file. The program will attempt to continue after printing out a warning message. ⟨ Read header info 24 ⟩ ≡

pxl id1 ← read word ; { read and check first word in file } if pxl id1 ≠ 1001 then error (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ );

This code is used in section 26.

8  THE FIRST PASS ON A PXL FILE  PXtoCH §25

25. Next, we read in 517 words (128 characters × 4 words + 5 words of font information) from the pxl file and save them in pxl . (For efficiency later on, we read and store them a halfword at a time.) There should be at least this many words in the file. If there aren’t, then there is something wrong with the file and the program terminates. If there are no raster descriptions in the file, then these will be not only the next 517 words, they will also be the last 517 words, which is what we want. If there are more than 517 words left in the file, we continue reading the file, circulating the pxl ptr through the array so that the 517^{th} from last word is the next word to be overwritten. When the end of file is reached, the pxl ptr will actually be pointing to the word which was 517^{th} from the end of the file. ⟨ Read to end of file 25 ⟩ ≡

pxl ptr ← 1;

file size ← 1;

too short ← true;

if eof (pxl file) then error (´ ␣ ␣ ␣ ␣ ␣ ␣ ␣ ´ )

else repeat pxl [pxl ptr ] ← read halfword ; incr (pxl ptr ); incr (file size); too short ← eof (pxl file);

until (pxl ptr > pxl size) ∨ too short ; if too short then abort (´ ␣ ␣ ␣ ␣ ´ ) { else continue reading until end of file } else repeat if pxl ptr > pxl size then pxl ptr ← 1;

pxl [pxl ptr ] ← read halfword ; incr (pxl ptr ); incr (file size); until eof (pxl file);

file size ← file size div 2;

This code is used in section 26.

26. Read in the file for the first pass. procedure check file(var pxl ptr : integer );

begin ⟨ Read header info 24 ⟩

⟨ Read to end of file 25 ⟩

end; 27. Here, the file information is saved. This information was the last info read in and so is stored in the 10 halfwords in pxl prior to pxl ptr . (Remember, we are using pxl as a circular list.) If this pointer is somewhere in the middle of the file, all we need to do is look at the previous ten halfwords. If the pointer is at the beginning or at the end of the file, however, the font information is split between the end of the array and the beginning, so we need to extract information from both places. procedure save font info(var pxl ptr : integer );

var i, j, index : integer ;

tbl : packed array [1 . . end size] of integer ; begin { save pointers to information in tbl } for i ← 1 to end size do

begin tbl [i] ← pxl ptr − i;

if tbl [i] < 1 then tbl [i] ← tbl [i] + pxl size; end;

{ then use tbl to index pxl } checksum ← pxl [tbl [10]] ∗ two 16 + pxl [tbl [9]]; magnification ← pxl [tbl [8]] ∗ two 16 + pxl [tbl [7]]; design size ← pxl [tbl [6]] ∗ two 16 + pxl [tbl [5]]; directory ptr ← pxl [tbl [4]] ∗ two 16 + pxl [tbl [3]]; pxl id2 ← pxl [tbl [2]] ∗ two 16 + pxl [tbl [1]]; end;

28. Here is the first pass on the pxl file. procedure first pass ;

10  SORTING THE ADDRESSES  PXtoCH §29

begin check file(pxl ptr ); if file ok then save font info(pxl ptr ); end; 29. Sorting the addresses. The second section of the program is simply a sort procedure which sorts the font information by the raster address saved for each character. ⟨ Constants 20 ⟩ +≡

raster offset = 8; { halfwords stored for each character }

raster begin = 4; { halfwords away from first that the raster address is stored }

30. ⟨ Types 6 ⟩ +≡ font type = packed array [1 . . font size] of integer ;

31. ⟨ Global Variables 7 ⟩ +≡ addr tbl : font type; { array for saving the raster addresses } rank tbl : font type; { array for saving the rank of each address } tbl ptr2 : integer ;

32. The raster images in the file are not stored in any particular order, but each character has stored in its font information, a pointer to its raster image. In order to process the raster information sequentially (the order in which it is stored in the file) we need to sort the font information by the raster addresses. In order to sort the addresses, we need to extract them from the rest of the font information. This should be (and is) easy: each raster address is a constant offset from the previous one. The addresses can be saved by simply cycling through the pxl array and scooping up every n^{th} word, where n is the number of words stored in the array for each character. Along with each address, a rank is stored. Initially, this rank is just the order in which the addresses are saved. In the sort procedure, it is the ranks that will be sorted; the addresses will not actually be shifted around. See details of the sort procedure for why the sort is done this way. ⟨ Extract raster address 32 ⟩ ≡

total ch ← 1;

tbl ptr ← pxl ptr + raster begin; { index of first address }

if tbl ptr > pxl size then tbl ptr ← tbl ptr − pxl size;

repeat tbl ptr2 ← tbl ptr + 1; if tbl ptr2 > pxl size then tbl ptr2 ← 1; rank tbl [total ch] ← total ch; addr tbl [total ch] ← pxl [tbl ptr ] ∗ two 16 + pxl [tbl ptr2 ]; incr (total ch); tbl ptr ← tbl ptr + raster offset ; if tbl ptr > pxl size then tbl ptr ← tbl ptr − pxl size;

until tbl ptr + end size − raster begin = pxl ptr ;

total ch ← total ch − 1;

This code is used in section 43.

33. Rather than sort the addresses themselves, a rank is sorted. (there is a reason for this, stay tuned). If the addresses are sorted, we then have no way of knowing which address matches which position in the Font Directory. If the addresses are not switched around within addr tbl , then they always stay in the same order in which they were loaded into addr tbl , and thus correspond to the order in the Font Directory. Instead, the ranks are switched around, and the sorted order of the addresses can be determined by the rank associated with the address after the sort is done. Contrariwise, the addresses could have been sorted and a pointer to which address it was could have been saved with the address, but the rank method will be used to good advantage later on, so bear with us.

Switch switches two integer values for the sort routine. procedure switch(var i, j : integer );

var temp: integer ;

begin temp ← i; i ← j; j ← temp;

§34  PXtoCH  SORTING THE ADDRESSES 11

end; 34. The sort procedure (a quick sort). Note that we are comparing addresses (addr tbl ), yet exchanging ranks (rank tbl ). procedure sort (m, n : integer );

var key : integer ; done: boolean; i, j: integer ; begin if m < n then

begin { initialize starting points } i ← m; j ← n + 1;

{ set key for comparison } key ← addr tbl [rank tbl [m]]; done ← false;

{ loop until start counter ¿ finish counter } repeat { increment start until value in array ¿= key or start = end of array }

repeat i ← i + 1

until (addr tbl [rank tbl [i]] ≥ key ) ∨ (i = n);

{ decrement finish counter until value in array ¡ key or finish = beginning of array } repeat j ← j − 1 until (addr tbl [rank tbl [j]] < key ) ∨ (j = m);

{ if start ¡ finish, switch ranks, otherwise loop is done } if i < j then switch(rank tbl [i], rank tbl [j]) else done ← true;

until done; switch(rank tbl [m], rank tbl [j]);

{ list now has all values less than key in one part, all values greater than key in the other. now sort

the two parts } if (j > 1) ∧ (m < (j − 1)) then sort (m, j − 1); if (j + 1) < n then sort (j + 1, n); end;

end;

35. Here is where we use those ranks. We can now go back to pxl and move the Font Directory information to a more useable structure. Each rank in the address file specifies where the font information should go in the array fnt info. For example, the information for the first character in pxl is placed into fnt info in the position specified by the rank of the first address in the sorted address file. If the rank is 10, then the first character in the font directory is the tenth character in the raster information. The font information for this character is saved in bucket 10 in the fnt info array. If the raster address is zero, no information is saved. ⟨ Constants 20 ⟩ +≡

two 17 = ´ 400000 ;

36. ⟨ Types 6 ⟩ +≡

fnt rec = record pxl height : integer ; pxl width: integer ; x offset : integer ; y offset : integer ; raster addr : integer ; tfm width: integer ; chr code: integer end;

fnt tbl type = packed array [1 . . font size] of fnt rec; 37. ⟨ Global Variables 7 ⟩ +≡ fnt info: fnt tbl type; { array for saving character information } total ch: integer ; { keep track of how many characters there are } index1 , index2 , index3 : integer ;

38. The character with the first raster image in pxl file will be put into the first position of fnt info, and so on for the entire table. ⟨ Save font info by rank 38 ⟩ ≡

max height ← 0; max width ← 0;

for rnk ← 1 to total ch do begin ⟨ Calculate indexes 40 ⟩ ⟨ Move font information 41 ⟩ end;

This code is used in section 43.

39. ⟨ Global Variables 7 ⟩ +≡ tbl : array [1 . . raster offset ] of integer ;

40. Calculate pointers to the information for this character. If we are in the middle of the table, we simply look at the next n number of fields, where n is the number of fields saved for each character. If we are at the end of the table, and there aren’t enough fields left at the end of the array to contain the information for this character, then we have to continue looking at the beginning of the array (treating the array as a circular list). This section determines where the information is in the table for this character, and saves the pointers to the fields in tbl , so that the first field appears in position tbl [1], the second in position tbl [2], etc. ⟨ Calculate indexes 40 ⟩ ≡

tbl [1] ← (rank tbl [rnk ] − 1) ∗ raster offset + pxl ptr ; if tbl [1] > pxl size then tbl [1] ← tbl [1] − pxl size; if tbl [1] < pxl size − raster offset + 1 then

for i ← 2 to raster offset do tbl [i] ← tbl [1] + i − 1 else for i ← 2 to raster offset do

begin tbl [i] ← tbl [1] + i − 1;

if tbl [i] > pxl size then tbl [i] ← tbl [i] − pxl size; end;

This code is used in section 38.

41. Here we actually move the information stored in pxl to the fnt info table. This transfer is straightforward for most of the fields, but for the x and y offset we have to check to see if the fields are negative, and if so, adjust them before we save them (what we actually do is check to see if the number is larger than 2^{15}, and if so, adjust it so that it is really the two’s complement of that number. We want the value to fall within the range of −2^{15} to +2^{15}). Note that the pxl width, pxl height , x offset and y offset are each contained in one halfword, and thus one bucket of pxl , but the tfm width and the raster addr are contained in two. We also convert the rank to octal and save it in the table as the chr code. ⟨ Move font information 41 ⟩ ≡

fnt info[rnk ].pxl width ← pxl [tbl [1]]; fnt info[rnk ].pxl height ← pxl [tbl [2]]; if pxl [tbl [3]] > two 15 then fnt info[rnk ].x offset ← pxl [tbl [3]] − two 16 else fnt info[rnk ].x offset ← pxl [tbl [3]]; if pxl [tbl [4]] > two 15 then fnt info[rnk ].y offset ← pxl [tbl [4]] − two 16 else fnt info[rnk ].y offset ← pxl [tbl [4]]; fnt info[rnk ].tfm width ← pxl [tbl [7]] ∗ two 16 + pxl [tbl [8]]; fnt info[rnk ].raster addr ← pxl [tbl [5]] ∗ two 16 + pxl [tbl [6]]; fnt info[rnk ].chr code ← convert chrcode(rank tbl [rnk ]); max height ← max (fnt info[rnk ].pxl height , max height ); max width ← max (fnt info[rnk ].pxl width, max width);

This code is used in section 38.

42. Convert rank to octal for chrcode. function convert chrcode(var num : integer ): integer ;

var i, j: integer ; begin j ← (num − 1) div 64; i ← ((num − 1) − j ∗ 64) div 8; convert chrcode ← j ∗ 100 + i ∗ 10 + ((num − 1) mod 8); end;

43. The second section of the program which does the sort. procedure sort addresses ;

14  SECOND PASS  PXtoCH §44

var tbl ptr : integer ; rnk : integer ; i: integer ; begin ⟨ Extract raster address 32 ⟩ sort (1, total ch); ⟨ Save font info by rank 38 ⟩ end; 44. Second pass. The pxl file is read a second time and the information at the beginning of the file (the raster images) is converted into a pictoral representation using periods and asterisks which is output along with information about the character including size information, kerning, and position within the raster. procedure second pass ;

var index , chrptr : integer ; i, j, h, w: integer ; begin ⟨ Reset input file 8 ⟩ ⟨ Set output file 45 ⟩ ⟨ Read first word 46 ⟩ ⟨ Output character file header 47 ⟩ ⟨ Convert raster info to format 49 ⟩ ⟨ Save final info 61 ⟩ end;

45. ⟨ Set output file 45 ⟩ ≡ rewrite(chr file);

This code is used in section 44.

46. Read first word of file for second pass. ⟨ Read first word 46 ⟩ ≡

pxl id1 ← read word ; byte count ← 0;

This code is used in section 44.

47. The first page of the output file contains information about the entire font. This information comes from the end of the pxl file and needs to be saved somewhere, so we’ll put it here. ⟨ Output character file header 47 ⟩ ≡

write ln(chr file, ´ ␣ ␣ ␣ ´ ); write ln(chr file, ´ ␣ ␣ ␣ ´ , total ch : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣ ´ , checksum : 1); write ln(chr file, ´ ␣␣ ´ , magnification : 1); write ln(chr file, ´ ␣ ␣␣␣␣ ´ , design size : 1); write ln(chr file, ´ ␣ ␣␣ ´ , directory ptr : 1); write ln(chr file, ´ ␣ ␣␣␣␣␣␣␣ ´ , pxl id1 : 1); write ln(chr file, ´ ␣ ␣␣␣␣␣ ´ , max height : 1); write ln(chr file, ´ ␣ ␣␣␣␣␣␣ ´ , max width : 1);

This code is used in section 44.

§49  PXtoCH  SECOND PASS 15

48. We will use these variables when we are converting the binary raster to the character raster, so we will declare them here. ⟨ Global Variables 7 ⟩ +≡ width, height , word width, next byte, top, bottom, left , right , offset , index , byte count : integer ; i, j, h, w: integer ; first one, top found : boolean; 49. If there is a raster image for this character (its raster addr is not 0), then we convert it to characters and write it out. While we are doing the conversion we will need to save information about the character such as its position in the raster, the boundaries of the character (its leftmost, rightmost, topmost and bottommost pixel), etc. ⟨ Convert raster info to format 49 ⟩ ≡

for index ← 1 to font size do begin { check for correct raster address } height ← fnt info[index ].pxl height ; if (height ≠ 0) ∧ (fnt info[index ].raster addr ≠ 0) then

begin width ← fnt info[index ].pxl width; word width ← ceiling (width, word size); right ← 0; left ← word size + 1; top found ← false; ⟨ Read raster info 52 ⟩ ⟨ Save character info 56 ⟩ ⟨ Output character info 57 ⟩ ⟨ Output raster 59 ⟩ end; end;

This code is used in section 44.

50. Here are the characters we will use to print out the character image. ⟨ Constants 20 ⟩ +≡

asterisk = ´ ´ ; { a black or ’on’ pixel } blank = ´ ␣´ ; { a position marker } period = ´ ´ ; { a white or ’off’ pixel } dash = ´ ´ ; { the x-offset } bar = ´ ´ ; { the y-offset } plus = ´ ´ ; { the origin } word size = 32; max pxl size = 10000;

{ big number large enough to accommodate height × width × resolution for one character }

51. More variables needed to save the raster image. ⟨ Global Variables 7 ⟩ +≡ chr : packed array [1 . . max pxl size] of char ; { this is where we save the raster until we print it out } bit on: boolean; { is this pixel black or white? } two power : integer ; { used to decriment the binary number representing the raster } b: integer ; { which byte of the word we are processing } bit : integer ; { location of the current pixel within the word } 52. For the height of the character, read word width words and process them. The value of word width is equal to the number of 32-bit words needed to store the width of the character. The words will actually be processed one byte at a time. ⟨ Read raster info 52 ⟩ ≡

for h ← 1 to height do begin first one ← true; for w ← 1 to word width do

begin for b ← 1 to 4 do begin next byte ← read byte; incr (byte count ); ⟨ Create star raster 53 ⟩ end

end; end;

This code is used in section 49.

53. To create the character raster, we will process each byte from left to right, or from its highest order digit to its lowest. After each digit is converted to either a period or a star, it is saved in chr , which is actually a very long one dimensional array. Since we don’t know in advance how high and wide a particular character is going to be, we can’t allocate a two dimensional array of the right size, so a one dimensional one will have to do. ⟨ Create star raster 53 ⟩ ≡

two power ← two 7 ; i ← 1; offset ← (word width ∗ (h − 1) + (w − 1)) ∗ word size; bit on ← false; if next byte ≠ 0 then bottom ← h; while next byte ≠ 0 do

begin bit on ← next byte div two power = 1; next byte ← next byte mod two power ; two power ← two power div 2; bit ← i + (b − 1) ∗ 8; ⟨ Save location of character extremes 54 ⟩ incr (i); end;

{ fill up rest of buffer with blanks } for j ← i to 8 do

begin chr [offset + j + (b − 1) ∗ 8] ← period ; end;

This code is used in section 52.

54. After we determine whether this bit is on or off, we first of all need to save it as either a period or an asterisk, then if it is an asterisk, we need to check and see whether the pixel we have just processed is at the extremes of the raster. If so, we want to update our raster information. ⟨ Save location of character extremes 54 ⟩ ≡

if bit on then

begin chr [offset + bit ] ← asterisk ;

if ¬top found then begin top found ← true; top ← h; end;

if next byte = 0 then right ← max (right , bit + (w − 1) ∗ word size);

if first one then

if (bit + (w − 1) ∗ word size) < left then begin left ← min(left , bit + (w − 1) ∗ word size); first one ← false; end;

end else chr [offset + bit ] ← period ;

This code is used in section 53.

55. Variables used to save character information. ⟨ Global Variables 7 ⟩ +≡ data end , data row count , rows from top, internal width, raster width, right kerning , depth: integer ; x limit , y limit , x, y: integer ;

56. Once we have finished reading in the binary raster, we can calculate some information about the character we have just processed. ⟨ Save character info 56 ⟩ ≡

data row count ← bottom − top + 1;

depth ← bottom − top − fnt info[index ].y offset + 1;

right kerning ← right − fnt info[index ].tfm width div two 20 ; raster width ← right − fnt info[index ].x offset ; internal width ← right − left + 1; rows from top ← top; data end ← bottom;

This code is used in section 49.

57. Each character will appear on a separate page in the output file. The first thing that we want to output are statistics for the character. ⟨ Output character info 57 ⟩ ≡

page(chr file); write ln(chr file, ´ ␣␣␣␣␣␣␣␣ ´ , fnt info[index ].chr code : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣ ´ , fnt info[index ].pxl height : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣␣ ´ , fnt info[index ].pxl width : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣␣ ´ , right : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣␣␣ ´ , left : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣␣ ´ , depth : 1); write ln(chr file, ´ ␣ ␣␣␣␣␣␣␣ ´ , fnt info[index ].x offset : 1); write ln(chr file, ´ ␣ ␣␣␣␣␣␣␣ ´ , fnt info[index ].y offset : 1); write ln(chr file, ´ ␣ ␣␣␣␣␣␣ ´ , fnt info[index ].tfm width : 1); write ln(chr file, ´ ␣ ␣␣␣ ´ , raster width : 1); write ln(chr file, ´ ␣ ␣ ´ , internal width : 1); write ln(chr file, ´ ␣ ␣␣ ´ , right kerning : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣␣␣␣ ´ , top : 1); write ln(chr file, ´ ␣␣␣␣␣␣␣␣␣ ´ , bottom : 1); write ln(chr file, ´ ␣ ␣ ␣ ´ , data row count : 1);

This code is used in section 49.

58. ⟨ Global Variables 7 ⟩ +≡ max raster , max diff : integer ;

59. Then we output the character itself. Blanks to the right of the character’s raster width will not be output (what you see is what you get). Using the information saved for this character, we will output a raster only large enough to hold the character. There is some additional information that appears to the top and left of the character raster, notably the x offset position, the y offset position, and the origin (the point where the x and y offsets cross). ⟨ Output raster 59 ⟩ ≡

⟨ Write out reference point 60 ⟩ max raster ← max (height , fnt info[index ].y offset ); max diff ← max (fnt info[index ].y offset − height + 1, 0); for h ← 1 to max diff do

begin for x ← x limit to (width − 1) do write(chr file, blank ); write ln(chr file); end;

for h ← 0 to height − 1 do begin offset ← h ∗ word width ∗ word size + 1; chrptr ← offset ; for x ← x limit to −1 do

if (fnt info[index ].y offset = (h + max diff )) ∧ (x = −1) then write(chr file, bar ) else write(chr file, blank );

while chrptr ≤ right + offset − 1 do begin write(chr file, chr [chrptr ]); incr (chrptr ); end;

write ln(chr file);

end; write ln(chr file);

This code is used in section 49.

60. It is a little tricky to figure out where the reference points are to be printed. Basically we want to print from the smaller of the y offset or -1 down the page, and from the smaller of the x offset or -1 across the page. If either one lies on the origin (-1), then we want to print the origin instead of the reference point. The y offset will always be printed in column -1 and the x offset will always be printed in row -1. The origin appears at the point where the two would intersect (−1, −1). ⟨ Write out reference point 60 ⟩ ≡

x limit ← min(fnt info[index ].x offset , −1); y limit ← min(fnt info[index ].y offset , −1); if y limit < −1 then

for y ← y limit to −2 do

begin for x ← x limit to width do if (x = −1) ∧ (y = y limit ) then write(chr file, bar ) else write(chr file, blank );

write ln(chr file);

end; for x ← x limit to width do

if (x = −1) then write(chr file, plus )

else if (x = fnt info[index ].x offset ) then write(chr file, dash)

else write(chr file, blank ); write ln(chr file);

This code is used in section 59.

61. Finally, we print out some statistics on the file, and we are done. ⟨ Save final info 61 ⟩ ≡

print ln(´ ␣ ␣´ , total ch : 1, ´ ␣ ´ ); print ln(´ ␣ ␣ ␣ ␣´ , max height : 1, ´ ´ ); print ln(´ ␣ ␣ ␣ ␣´ , max width : 1, ´ ´ ); print ln(´ ␣ ␣ ␣´ , magnification : 1, ´ ´ ); print ln(´ ␣ ␣ ␣ ␣´ , design size : 1, ´ ´ ); print ln(´ ␣ ␣ ␣ ␣´ , pxl id1 : 1, ´ ´ ); print ln(´ ␣ ´ );

This code is used in section 44.

20  THE MAIN PROGRAM  PXtoCH §62

62. The main program. Initialize the files, read the pxl file once to extract the file information and the font table, sort the font table, then read it again to extract the raster information.

Here is where begins and ends. begin initialize; first pass ; file ok ← pxl id1 = pxl id2 ;

if file ok then

begin sort addresses ; second pass ; end

else if pxl id1 ≠ pxl id2 then

    begin error (´ ␣  ␣  ␣         ␣  ␣    ␣    ␣   ␣     ␣   ␣  ␣  ␣   ␣  ␣  ´ );

error (´ ␣ ␣ ´ );

end; end.

§63  PXtoCH  SYSTEM-DEPENDENT CHANGES 21

63. System-dependent changes. This module should be replaced, if necessary, by changes to the program that are necessary to make work at a particular installation. It is usually best to design your change file so that all changes to previous modules preserve the module numbering; then everybody’s version will be consistent with the printed program. More extensive changes, which introduce new modules, can be inserted here; then only the index itself will get a new module number.

22  INDEX  PXtoCH §64

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

abort : \underline{23}, 25. addr tbl : \underline{31}, 32, 33, 34. asterisk : \underline{50}, 54. b: \underline{51}. banner : \underline{1}, 2. bar : \underline{50}, 59, 60. bit : \underline{51}, 53, 54. bit on: \underline{51}, 53, 54. blank : \underline{50}, 59, 60. boolean: 22, 34, 48, 51. bottom: \underline{48}, 53, 56, 57. byte: \underline{6}, 14, 15. byte count : 46, \underline{48}, 52. ceiling : \underline{19}, 49. char : 51. check file: \underline{26}, 28. checksum: \underline{11}, 27, 47. Chinese characters: 5. chr : \underline{51}, 53, 54, 59. chr code: \underline{36}, 41, 57. chr file: \underline{2}, \underline{13}, 45, 47, 57, 59, 60. chrptr : \underline{44}, 59. convert chrcode: 41, \underline{42}. dash: \underline{50}, 60. data end : \underline{55}, 56. data row count : \underline{55}, 56, 57. decr : \underline{3}. depth: \underline{55}, 56, 57. design size: \underline{11}, 27, 47, 61. directory ptr : \underline{11}, 27, 47. divisor : \underline{19}. done: \underline{34}. end num: \underline{20}. end size: \underline{20}, 27, 32. eof : 25. error : \underline{23}, 24, 25, 62. error file: 2, \underline{9}, 10. false: 23, 34, 49, 53, 54. field size: \underline{20}. file ok : 2, 20, \underline{22}, 23, 28, 62. file size: \underline{22}, 25. first one: \underline{48}, 52, 54. first pass : \underline{28}, 62. fnt info: 20, 35, \underline{37}, 38, 41, 49, 56, 57, 59, 60. fnt rec: \underline{36}. fnt tbl type: \underline{36}, 37. font directory : 11, 35. font fields : \underline{20}. font size: \underline{20}, 30, 36, 49. font type: \underline{30}, 31. halfword : \underline{21}. height : 12, \underline{48}, 49, 52, 59. i: \underline{15}, \underline{27}, \underline{33}, \underline{42}. incr : \underline{3}, 25, 32, 52, 53, 59. index : 27, \underline{44}, \underline{48}, 49, 56, 57, 59, 60. index1 : \underline{37}. index2 : \underline{37}. index3 : \underline{37}. init num: \underline{20}. init size: \underline{20}. initialize: \underline{2}, 62. integer : 11, 14, 15, 16, 17, 18, 19, 22, 26, 27, 30, 31, 33, 34, 36, 37, 39, 42, 43, 44, 48, 51, 55, 58.

internal width: \underline{55}, 56, 57.

j: \underline{42}.

Japanese characters: 5.

key : \underline{34}.

left : \underline{48}, 49, 54, 56, 57.

magnification: \underline{11}, 27, 47, 61.

max : \underline{17}, 41, 54, 59. max diff : 58, 59. max height : \underline{22}, 38, 41, 47, 61. max pxl size: \underline{50}, 51. max raster : 58, 59. max width: \underline{22}, 38, 41, 47, 61. min: 17, \underline{18}, 54, 60. next byte: \underline{48}, 52, 53, 54. num: \underline{19}, \underline{42}. num chrs : \underline{20}. offset : \underline{48}, 53, 54, 59. oriental characters: 5. page: 57. period : \underline{50}, 53, 54. plus : \underline{50}, 60. print : \underline{2}. print ln: \underline{2}, 23, 61. pxl : 20, 21, \underline{22}, 25, 27, 32, 35, 41. pxl file: \underline{2}, \underline{7}, 8, 14, 15, 16, 20, 22, 25, 28, 38,

44, 47, 62. pxl height : 12, \underline{36}, 41, 49, 57.

pxl id1 : \underline{11}, 24, 46, 47, 61, 62.
pxl id2 : \underline{11}, 27, 62.
pxl index : \underline{21}, 22.
pxl num: \underline{20}.
pxl ptr : \underline{22}, 25, \underline{26}, \underline{27}, 28, 32, 40.
pxl size: \underline{20}, 21, 25, 27, 32, 40.
pxl width: 12, \underline{36}, 41, 49, 57.
PXtoCH : \underline{2}.
rank tbl : \underline{31}, 32, 34, 40, 41.
raster addr : \underline{36}, 41, 49.

§64  PXtoCH  INDEX 23

raster address : 12. raster begin: \underline{29}, 32. raster offset : \underline{29}, 32, 39, 40. raster width: \underline{55}, 56, 57. read : 14, 15, 16. Read byte: 16. read byte: \underline{16}, 52. Read halfword : 14. read halfword : \underline{14}, 25. read word : \underline{15}, 24, 46. Read word : 15. reset : 8. rewrite: 10, 45. right : \underline{48}, 49, 54, 56, 57, 59. right kerning : \underline{55}, 56, 57. rnk : 38, 40, 41, \underline{43}. rows from top: \underline{55}, 56. save end num: \underline{20}. save font info: \underline{27}, 28. second pass : \underline{44}, 62. sort : \underline{34}, 43. sort addresses : \underline{43}, 62. switch: \underline{33}, 34. system dependencies: 2, 8, 63. tbl : 27, 39, 40, 41. tbl ptr : 32, \underline{43}. tbl ptr2 : \underline{31}, 32. tbl size: \underline{20}. temp: \underline{33}. text : 9, 13. tfm width: 12, \underline{36}, 41, 56, 57. too short : \underline{22}, 25. top: \underline{48}, 54, 56, 57. top found : \underline{48}, 49, 54. total ch: 32, \underline{37}, 38, 43, 47, 61. true: 2, 25, 34, 52, 54. two power : \underline{51}, 53. two 15 : \underline{20}, 41. two 16 : \underline{20}, 27, 32, 41. two 17 : \underline{35}. two 20 : \underline{20}, 56. two 7 : \underline{20}, 53. two 8 : 14, 15, \underline{20}. width: 12, \underline{48}, 49, 59, 60. word size: 49, \underline{50}, 53, 54, 59. word width: \underline{48}, 49, 52, 53, 59. word1 : \underline{14}, \underline{15}, \underline{16}. word2 : \underline{14}, \underline{15}. write: 2, 59, 60. write ln: 2, 47, 57, 59, 60. x : 41. x limit : \underline{55}, 59, 60.

x offset : 12, \underline{36}, 41, 56, 57, 59, 60.
y limit : \underline{55}, 60.
y offset : 12, \underline{36}, 41, 56, 57, 59, 60.

24  NAMES OF THE SECTIONS  PXtoCH §64

⟨ Calculate indexes 40 ⟩ Used in section 38.

⟨ Constants 20, 29, 35, 50 ⟩ Used in section 2.

⟨ Convert raster info to format 49 ⟩ Used in section 44. ⟨ Create star raster 53 ⟩ Used in section 52. ⟨ Extract raster address 32 ⟩ Used in section 43.

⟨ Global Variables 7, 9, 11, 13, 22, 31, 37, 39, 48, 51, 55, 58 ⟩ Used in section 2.

⟨ Move font information 41 ⟩ Used in section 38. ⟨ Output character file header 47 ⟩ Used in section 44. ⟨ Output character info 57 ⟩ Used in section 49.

⟨ Output raster 59 ⟩ Used in section 49. ⟨ Read first word 46 ⟩ Used in section 44. ⟨ Read header info 24 ⟩ Used in section 26. ⟨ Read raster info 52 ⟩ Used in section 49. ⟨ Read to end of file 25 ⟩ Used in section 26. ⟨ Reset error file 10 ⟩ Used in section 2. ⟨ Reset input file 8 ⟩ Used in sections 2 and 44.

⟨ Save character info 56 ⟩ Used in section 49.

⟨ Save final info 61 ⟩ Used in section 44.

⟨ Save font info by rank 38 ⟩ Used in section 43. ⟨ Save location of character extremes 54 ⟩ Used in section 53.

⟨ Set output file 45 ⟩ Used in section 44. ⟨ Types 6, 21, 30, 36 ⟩ Used in section 2.

⟨ Write out reference point 60 ⟩ Used in section 59.

The PXtoCH processor

(Version 1, October 1983)

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Font metric data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 The input file contains the following fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 The Font Directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5 Useful subroutines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 6 The first pass on a PXL file . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 7 Sorting the addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 10 Second pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 14 The main program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 20 System-dependent changes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 21 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 22

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