summaryrefslogtreecommitdiff
path: root/obsolete/systems/knuth/unsupported/mfware/pxtopk.web
diff options
context:
space:
mode:
Diffstat (limited to 'obsolete/systems/knuth/unsupported/mfware/pxtopk.web')
-rw-r--r--obsolete/systems/knuth/unsupported/mfware/pxtopk.web1648
1 files changed, 1648 insertions, 0 deletions
diff --git a/obsolete/systems/knuth/unsupported/mfware/pxtopk.web b/obsolete/systems/knuth/unsupported/mfware/pxtopk.web
new file mode 100644
index 0000000000..0da0c4fc44
--- /dev/null
+++ b/obsolete/systems/knuth/unsupported/mfware/pxtopk.web
@@ -0,0 +1,1648 @@
+% PXtoPK.web
+%
+% PXtoPK creates a packed pixel file from a regular pixel file.
+%
+% Preliminary 0.0 version: May, 1985
+% First release 0.9 version: 8 May 1985
+% Updated to new PK standards (2.0) : 25 July 1985
+% Updated again to new PK format (2.1) : 15 August 1985
+% One_fourth bug fixed (2.2) : 23 January 1985
+% Use of i after for i := loop fixed (2.3) 14 November 1987
+\def\versiondate{30 November 1987}
+%
+\font\ninerm=cmr9
+\let\mc=\ninerm % medium caps for names like PASCAL
+\font\logo=logo10 % font used for the METAFONT logo
+\def\MF{{\logo META}\-{\logo FONT}}
+\def\PASCAL{{\mc Pascal}}
+\def\tamu{Texas A\char38 M}
+\def\(#1){} % this is used to make section names sort themselves better
+\def\9#1{} % this is used for sort keys in the index
+\def\title{PXtoPK}
+\def\contentspagenumber{0}
+\def\topofcontents{\null
+ \def\titlepage{F} % include headline on the contents page
+ \def\rheader{\mainfont\hfil \contentspagenumber}
+ \vfill
+ \centerline{\titlefont The {\ttitlefont PXtoPK} processor}
+ \vskip 15pt
+ \centerline{(Version 2.3, \versiondate)}
+ \vfill}
+\def\botofcontents{\vfill
+ \centerline{\hsize 5in\baselineskip9pt
+ \vbox{\ninerm\noindent
+ 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.}}}
+\pageno=\contentspagenumber \advance\pageno by 1
+
+@* Introduction.
+The standard format for the distribution of font raster information for \TeX\
+has been \.{PXL} 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 \.{PK}, 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 \.{pktopx}, no information will be lost by
+leaving the files in one format or another.
+
+@ The |banner| string defined here should be changed whenever \.{PXtoPK}
+gets modified.
+
+@d banner=='This is PXtoPK, Version 2.3'
+ {printed when the program starts}
+
+@ This program is written in standard \PASCAL, except where it is necessary
+to use extensions; for example, \.{PXtoPK} must read files whose names
+are dynamically specified, and that would be impossible in pure \PASCAL.
+
+@d othercases == others: {default for cases not listed explicitly}
+@d endcases == @+end {follows the default case in an extended |case| statement}
+@f othercases == else
+@f endcases == end
+
+@ Both the input and output come from binary files. On line interaction
+is handled through \PASCAL's standard |input| and |output| files.
+
+@d print_ln(#)==write_ln(output,#)
+@d print(#)==write(output,#)
+
+@p program PXtoPK(input, output);
+label @<Labels in the outer block@>@/
+const @<Constants in the outer block@>@/
+type @<Types in the outer block@>@/
+var @<Globals in the outer block@>@/
+procedure initialize; {this procedure gets things started properly}
+ var i:integer; {loop index for initializations}
+ begin print_ln(banner);@/
+ @<Set initial values@>@/
+ end;
+
+@ If the program has to stop prematurely, it goes to the
+`|final_end|'.
+
+@d final_end=9999 {label for the end of it all}
+
+@<Labels...@>=final_end;
+
+@ 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.
+@^system dependancies@>
+
+@<Constants...@>=
+@!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}
+
+@ Here are some macros for common programming idioms.
+
+@d incr(#) == #:=#+1 {increase a variable by unity}
+@d decr(#) == #:=#-1 {decrease a variable by unity}
+@d do_nothing == {empty statement}
+
+@ 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.
+
+@d abort(#)==begin print_ln(' ',#); jump_out; end
+
+@p procedure jump_out;
+begin goto final_end;
+end;
+
+@* The character set.
+Like all programs written with the \.{WEB} system, \.{PXtoPK} 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 \.{PXtoPK} have therefore been copied from the
+analogous ones in the \.{WEB} system routines. They have been considerably
+simplified, since \.{PXtoPK} need not deal with the controversial
+ASCII codes less than @'40.
+
+@<Types...@>=
+@!ASCII_code=" ".."~"; {a subrange of the integers}
+
+@ 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 \.{PXtoPK}.
+So we shall assume that the \PASCAL\ system being used for \.{PXtoPK}
+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 \PASCAL s
+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.
+@^system dependencies@>
+
+@d text_char == char {the data type of characters in text files}
+@d first_text_char=0 {ordinal number of the smallest element of |text_char|}
+@d last_text_char=127 {ordinal number of the largest element of |text_char|}
+
+@<Types...@>=
+@!text_file=packed file of text_char;
+
+@ The \.{PXtoPK} 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...@>=
+@!xord: array [text_char] of ASCII_code;
+ {specifies conversion of input characters}
+@!xchr: array [0..255] of text_char;
+ {specifies conversion of output characters}
+
+@ 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 init...@>=
+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]:='0';
+xchr[@'61]:='1';
+xchr[@'62]:='2';
+xchr[@'63]:='3';
+xchr[@'64]:='4';
+xchr[@'65]:='5';
+xchr[@'66]:='6';
+xchr[@'67]:='7';@/
+xchr[@'70]:='8';
+xchr[@'71]:='9';
+xchr[@'72]:=':';
+xchr[@'73]:=';';
+xchr[@'74]:='<';
+xchr[@'75]:='=';
+xchr[@'76]:='>';
+xchr[@'77]:='?';@/
+xchr[@'100]:='@@';
+xchr[@'101]:='A';
+xchr[@'102]:='B';
+xchr[@'103]:='C';
+xchr[@'104]:='D';
+xchr[@'105]:='E';
+xchr[@'106]:='F';
+xchr[@'107]:='G';@/
+xchr[@'110]:='H';
+xchr[@'111]:='I';
+xchr[@'112]:='J';
+xchr[@'113]:='K';
+xchr[@'114]:='L';
+xchr[@'115]:='M';
+xchr[@'116]:='N';
+xchr[@'117]:='O';@/
+xchr[@'120]:='P';
+xchr[@'121]:='Q';
+xchr[@'122]:='R';
+xchr[@'123]:='S';
+xchr[@'124]:='T';
+xchr[@'125]:='U';
+xchr[@'126]:='V';
+xchr[@'127]:='W';@/
+xchr[@'130]:='X';
+xchr[@'131]:='Y';
+xchr[@'132]:='Z';
+xchr[@'133]:='[';
+xchr[@'134]:='\';
+xchr[@'135]:=']';
+xchr[@'136]:='^';
+xchr[@'137]:='_';@/
+xchr[@'140]:='`';
+xchr[@'141]:='a';
+xchr[@'142]:='b';
+xchr[@'143]:='c';
+xchr[@'144]:='d';
+xchr[@'145]:='e';
+xchr[@'146]:='f';
+xchr[@'147]:='g';@/
+xchr[@'150]:='h';
+xchr[@'151]:='i';
+xchr[@'152]:='j';
+xchr[@'153]:='k';
+xchr[@'154]:='l';
+xchr[@'155]:='m';
+xchr[@'156]:='n';
+xchr[@'157]:='o';@/
+xchr[@'160]:='p';
+xchr[@'161]:='q';
+xchr[@'162]:='r';
+xchr[@'163]:='s';
+xchr[@'164]:='t';
+xchr[@'165]:='u';
+xchr[@'166]:='v';
+xchr[@'167]:='w';@/
+xchr[@'170]:='x';
+xchr[@'171]:='y';
+xchr[@'172]:='z';
+xchr[@'173]:='{';
+xchr[@'174]:='|';
+xchr[@'175]:='}';
+xchr[@'176]:='~';
+for i:=@'177 to 255 do xchr[i]:='?';
+
+@ The following system-independent code makes the |xord| array contain a
+suitable inverse to the information in |xchr|.
+
+@<Set init...@>=
+for i:=first_text_char to last_text_char do xord[chr(i)]:=@'40;
+for i:=" " to "~" do xord[xchr[i]]:=i;
+
+@* Pixel file format.
+A \.{PXL} file is an expanded raster description of a single font at a
+particular resolution. \.{PXL} files are used by many existing
+device-driver programs for dot matrix devices.
+All words in of \.{PXL} 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 \.{PXL} file and the last word contain the \.{PXL
+ID} 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
+\.{TFM} file. The \.{TFM} width, measured in \.{FIXes}, where 1 \.{FIX}
+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 \.{PXL} 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 \.{TFM} width.
+
+The final five words in the \.{PXL} 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 \.{TFM} 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 \.{FIXes}
+($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
+\.{PXL} ID as contained in the first word of the file.
+
+@d pxl_id=1001 {current version of \.{PXL} format}
+
+@* Packed file format.
+The packed file format is a compact representation of the data contained in a
+\.{GF} file. The information content is the same, but packed (\.{PK}) files
+are almost always less than half the size of their \.{GF} 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 \.{PK} 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 \.{GF} 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 \.{PK} 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 \.{PK} 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.
+
+@ 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.
+
+@ 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.)
+
+\yskip\hang|pk_xxx1| 240 |k[1]| |x[k]|. This command is undefined in general;
+it functions as a $(k+2)$-byte \\{no\_op} unless special \.{PK}-reading
+programs are being used. \MF\ 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.
+
+\yskip\hang\\{pk\_xxx2} 241 |k[2]| |x[k]|. Like |pk_xxx1|, but |0<=k<65536|.
+
+\yskip\hang\\{pk\_xxx3} 242 |k[3]| |x[k]|. Like |pk_xxx1|, but
+|0<=k<@t$2^{24}$@>|. \MF\ uses this when sending a \&{special} string whose
+length exceeds~255.
+
+\yskip\hang\\{pk\_xxx4} 243 |k[4]| |x[k]|. Like |pk_xxx1|, but |k| can be
+ridiculously large; |k| musn't be negative.
+
+\yskip\hang|pk_yyy| 244 |y[4]|. This command is undefined in general; it
+functions as a five-byte \\{no\_op} unless special \.{PK} reading programs
+are being used. \MF\ 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.
+
+\yskip\hang|pk_post| 245. Beginning of the postamble. This command is
+followed by enough |pk_no_op| commands to make the file a multiple
+of four bytes long. Zero through three are usual, but any number is
+allowed.
+This should make the file easy to read on machines which pack four bytes to
+a word.
+
+\yskip\hang|pk_no_op| 246. No operation, do nothing. Any number of
+|pk_no_op|'s may appear between \.{PK} commands, but a |pk_no_op| cannot be
+inserted between a command and its parameters, between two parameters, or
+inside a character definition.
+
+\yskip\hang|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 \.{PK} file. The parameters |ds| and |cs| are
+the design size of the file in $1/2^{20}$ points, and the checksum of the
+file, respectively. The checksum should match the \.{TFM} file and the
+\.{GF} 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 \.{PK} 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 \.{PK}. 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.
+
+@ We put a few of the above opcodes into definitions for symbolic use by
+this program.
+
+@d pk_id = 89 {the version of \.{PK} file described}
+@d pk_xxx1 = 240 {\&{special} commands}
+@d pk_yyy = 244 {\&{numspecial} commands}
+@d pk_post = 245 {postamble}
+@d pk_no_op = 246 {no operation}
+@d pk_pre = 247 {preamble}
+
+@ The \.{PK} 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 \.{GF} 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 \.{PK} file format are based on the four-bit nybble.
+
+@ The analysis of the pixel files yielded another interesting statistic: fully
+37\char`\%\
+of the raster rows were duplicates of the previous row. Thus, the \.{PK}
+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.
+
+@ 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.
+
+@ 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).
+
+@ Our only remaining task in the coding of packed numbers is the large run
+counts. We use a scheme suggested by D.~E.~Knuth
+@^Knuth, D.~E.@>
+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.
+
+@ 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.
+
+@p@{ 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 ; @}
+
+@ 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 \.{PK} 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.
+
+@ 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.
+
+\yskip\hang 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 \.{aminch}.
+
+\yskip\hang 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.
+
+\yskip\hang 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 \.{GF} file format, including vertical escapement.
+\vskip\baselineskip
+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 \.{PK} 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 \MF; the
+\MF\ reference point is the lower left hand corner of this pixel. (See the
+example below.)
+
+@ \TeX\ requires that all characters which have the same character codes
+modulo 256 also have the same |tfm| widths, and escapement values. The \.{PK}
+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.
+
+@ As an illustration of the \.{PK} format, the character \char4\ 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 \MF's row numbers.)
+
+\vskip\baselineskip
+\centerline{\vbox{\baselineskip=10pt
+\halign{\hfil#\quad&&\hfil#\hfil\cr
+0& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+1& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+2& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+3& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+4& & &M&M& & & & & & & & & & & & & & & & &M&M\cr
+5& & &M&M& & & & & & & & & & & & & & & & &M&M\cr
+6& & &M&M& & & & & & & & & & & & & & & & &M&M\cr
+7\cr
+8\cr
+9& & & & &M&M& & & & & & & & & & & & &M&M& & \cr
+10& & & & &M&M& & & & & & & & & & & & &M&M& & \cr
+11& & & & &M&M& & & & & & & & & & & & &M&M& & \cr
+12& & & & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M& & \cr
+13& & & & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M& & \cr
+14& & & & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M& & \cr
+15& & & & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M& & \cr
+16& & & & &M&M& & & & & & & & & & & & &M&M& & \cr
+17& & & & &M&M& & & & & & & & & & & & &M&M& & \cr
+18& & & & &M&M& & & & & & & & & & & & &M&M& & \cr
+19\cr
+20\cr
+21\cr
+22& & &M&M& & & & & & & & & & & & & & & & &M&M\cr
+23& & &M&M& & & & & & & & & & & & & & & & &M&M\cr
+24& & &M&M& & & & & & & & & & & & & & & & &M&M\cr
+25& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+26& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+27& & &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+28&*& &M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M&M\cr
+&\hphantom{M}&\hphantom{M}\cr
+}}}
+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:
+\vskip\baselineskip
+\centerline{82 [2] (16) 2 (42) [2] 2 (12) 2 (4) [3]}
+\centerline{16 (4) [2] 2 (12) 2 (62) [2] 2 (16) 82}
+\vskip\baselineskip
+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.
+
+@ 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):
+\vskip\baselineskip
+\centerline{\tt D9 E2 97 2 B1 E2 2 93 2 4 E3}
+\centerline{\tt 97 4 E2 2 93 2 C5 E2 2 97 D9}
+\vskip\baselineskip\noindent
+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.
+
+@ 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 {\tt 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:
+\vskip\baselineskip
+$$\vbox{\halign{\hfil #\quad&&{\tt #\ }\cr
+Flag byte&88\cr
+Packet length&1A\cr
+Character code&04\cr
+|tfm| width&09&C7&1C\cr
+Horizontal escapement (pixels)&19\cr
+Width of bit map&14\cr
+Height of bit map&1D\cr
+Horizontal offset (signed)&FE\cr
+Vertical offset&1C\cr
+Raster data&D9&E2&97\cr
+&2B&1E&22\cr
+&93&24&E3\cr
+&97&4E&22\cr
+&93&2C&5E\cr
+&22&97&D9\cr}}$$
+
+@ This format was written by Tomas Rokicki in August, 1985.
+
+@* 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...@>=
+@!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}
+@^system dependancies@>
+
+@ @<Glob...@>=
+@!pxl_file:word_file; {where the input comes from}
+@!pk_file:byte_file; {where the final output goes}
+@^system dependencies@>
+
+@ 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.
+@^system dependencies@>
+
+@p 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;
+
+@ 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.
+
+@<Glob...@>=
+@!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?}
+
+@ @<Set init...@>=
+pk_loc := 0 ;
+
+@ We need a function that will read in a word from the \.{PXL} file. If
+the particular system
+@^system dependencies@>
+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.
+
+@p function pixel_integer : integer ;
+var i:integer;
+begin i := pxl_file^ ;
+get(pxl_file) ;
+eof_pixel:=eof(pxl_file);
+pixel_integer:=i;
+end;
+
+@ @<Glob...@>=
+@!eof_pixel:boolean; {true when end of pixel file is reached.}
+
+@ We also need a few routines to write data to the \.{PK} 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.
+
+@<Const...@>=
+@!one_fourth=1073741824 ; {two to the thirtieth}
+
+@ @p 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 ;
+
+@ We need the globals |bit_weight| and |output_byte| for buffering.
+
+@<Glob...@>=
+@!bit_weight : integer ; {output bit weight}
+@!output_byte : integer ; {output byte for pk file}
+
+@ Here is a procedure that reads the \.{PXL} 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|.
+
+@p 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 not eof_pixel do begin
+ mem[k] := pixel_integer ;
+ k := k + 1 ;
+ if k > max_mem_size then
+ abort('PXtoPK memory size exceeded on load of pixel file!') ;
+ end ;
+ print_ln((4*k):1, ' bytes read from pixel file.') ;
+ if k + 10000 > max_mem_size then
+ abort('I don''t think that there will be enough memory.') ;
+ next_mem_free := k ;
+ k := k - 1 ;
+ if (mem[k] <> pxl_id) or (mem[0]<>pxl_id) then goto 9997 ;
+ goto 9999 ;
+9997: abort('PXL file is bad');
+@.PXL file is bad@>
+9999: dir_ptr := mem[k-1] ;
+end;
+
+@ We need to declare the |mem| array and a few other variables.
+
+@<Glob...@>=
+@!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}
+
+@* Writing the packed file.
+Next we have some bit manipulation routines we need.
+
+@p 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 ;
+
+@ We now need a few definitions to make access of the pixel file simpler.
+
+@d x_size == hi(mem[dir_ptr]) {sizes}
+@d y_size == lo(mem[dir_ptr])
+@d x_offset == his(mem[dir_ptr+1]) {offsets}
+@d y_offset == los(mem[dir_ptr+1])
+@d raster_pointer == mem[dir_ptr+2] {raster pointer}
+@d tfm_width == mem[dir_ptr+3] {tfm width}
+@d checksum == mem[dir_ptr+512] {checksum at end of directory}
+@d magnification == mem[dir_ptr+513]
+@d design_size == mem[dir_ptr+514]
+
+@ 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.
+
+@d preamble_comment == 'PXTOPK 2.3 output'
+@d comm_length = 17
+
+@p 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 ;
+
+@ We define a few globals to maintain some of this data.
+
+@<Glob...@>=
+@!car : integer ; {a global character pointer}
+@!hppp : integer ; {horizontal pixels per point}
+@!comment : packed array [1..comm_length] of char ;
+
+@ We initialize the comment array:
+
+@<Set init...@>=
+comment := preamble_comment ;
+
+@ 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.
+
+@p procedure write_postamble ;
+begin
+ pk_byte(pk_post) ;
+ while (pk_loc mod 4 <> 0) do pk_byte(pk_no_op) ;
+ print_ln(pk_loc:1, ' bytes written to packed file.') ;
+end ;
+
+@* 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.
+
+@ First, we need a routine to compare two raster rows and tell us if they
+are the same.
+
+@p function equal(row1, row2: integer) : boolean ;
+var i : integer ; {index}
+temp : boolean ;
+begin
+ i := width ;
+ temp := true ;
+ while (i > 0) and temp do begin
+ if mem[row1] <> mem[row2] then
+ temp := false ;
+ incr(row1) ; incr(row2) ;
+ i := i - 32 ;
+ end ;
+ equal := temp ;
+end ;
+
+@ We now declare a few variables to contain the character width,
+height, offsets, and raster pointer.
+
+@<Glob...@>=
+@!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}
+
+@ 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 \.{TFM} width.
+
+@p 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|@>
+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@> ;
+ @<Create bit counts@> ;
+ @<Calculate |dyn_f| and packed size and write character@> ;
+end ;
+
+@ The |pxl_conv| variable should be a global.
+
+@<Glob...@>=
+@!pxl_conv : real ; {converts TFM widths to pixels}
+
+@ 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@>=
+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
+
+@ Of course, we declare some of these locals.
+
+@<Locals...@>=
+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}
+
+@ We also need the |power| array, which contains powers of two.
+
+@<Glob...@>=
+@!power : array [0..31] of integer ;
+
+@ @<Set init...@>=
+power[0] := 1 ;
+for i := 1 to 30 do
+ power[i] := power[i-1] * 2 ;
+power[31] := - power[30] - power[30] ;
+
+@ 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.
+
+@d black = 1
+@d white = 0
+@d end_of_glyph = 2
+
+@ And now the actual routine.
+
+@<Create bit counts@>=
+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@> ;
+ if bit = test then
+ incr(count)
+ else begin
+ mem[cur_ptr] := count ;
+ incr(cur_ptr) ;
+ if cur_ptr + 3 > max_mem_size then
+ abort('Out of memory while saving character counts!') ;
+ 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
+
+@ 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@>=
+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
+
+@ Now for all of those many locals used but not defined:
+
+@<Locals...@>=
+@!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}
+
+@ 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@>=
+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@> ;
+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) or (height * width = 0) then begin
+ comp_size := (height * width + 7) div 8 ;
+ dyn_f := 14 ;
+end ;
+@<Write character preamble@> ;
+if dyn_f <> 14 then
+ @<Send compressed format@>
+else
+ @<Send bit map@> ;
+if pred_pk_loc <> pk_loc then
+ abort('Bad predicted character length: character ',car:1)
+
+@ 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@>=
+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
+
+@ We need a handful of locals:
+
+@<Locals to |ship_character|@>=
+@!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?}
+
+@ Now we write the character preamble information. First we need to determine
+which of the three formats we should use.
+
+@<Write character preamble@>=
+flag_byte := dyn_f * 16 ;
+if first_on then flag_byte := flag_byte + 8 ;
+if (tfm_width > 16777215) or (tfm_width < 0) or
+ (hor_esc < 0) or (comp_size > 196579) or (width > 65535) or
+ (height > 65535) or (c_x_off > 32767) or (c_y_off > 32767) or
+ (c_x_off < -32768) or (c_y_off < -32768) then
+ @<Write long character preamble@>
+else if (hor_esc > 255) or (width > 255) or (height > 255) or
+ (c_x_off > 127) or (c_y_off > 127) or (c_x_off < -128) or
+ (c_y_off < -128) or (comp_size > 1016) then
+ @<Write two-byte short character preamble@>
+else
+ @<Write one-byte short character preamble@>
+
+@ 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@>=
+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
+
+@ Here we write a short short character preamble, with one-byte size
+parameters.
+
+@<Write one-byte short character preamble@>=
+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
+
+@ Here we write a long short character preamble, with two-byte size parameters.
+
+@<Write two-byte short character preamble@>=
+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
+
+@ 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@>=
+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 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@>=
+begin
+ buff := 0 ;
+ p_bit := 8 ;
+ i := bit_counts ;
+ h_bit := width ;
+ on := not first_on ;
+ state := false ;
+ count := 0 ;
+ repeat_flag := 0 ;
+ while ( mem[i] <> 0 ) or state or ( 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@> ;
+ if state and ( repeat_flag = 0 ) then begin
+ count := s_count ; i := s_i ; on := s_on ;
+ state := false ;
+ end else if not state and ( 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
+
+@ All of the remaining locals:
+
+@<Locals to |ship_character|@>=
+@!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}
+
+@ 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@>=
+repeat
+ if count = 0 then begin
+ if mem[i] < 0 then begin
+ if not state then repeat_flag := - mem[i] ;
+ incr(i) ;
+ end ;
+ count := mem[i] ;
+ incr(i) ;
+ on := not on ;
+ end ;
+ if ( count >= p_bit ) and ( 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 ) and ( 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
+
+@* 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.
+
+@d flush_buffer == begin end
+@d get_line(#) == if eoln(input) then read_ln(input) ;
+ i := 1 ;
+ while not (eoln(input) or eof(input)) do begin
+ #[i] := input^ ;
+ incr(i) ;
+ get(input) ;
+ end ;
+ #[i] := ' '
+
+@ @p 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('Input file name: ') ;
+ flush_buffer ;
+ get_line(pxl_name) ;
+ print('Output file name: ') ;
+ flush_buffer ;
+ get_line(pk_name) ;
+ print_ln(' ') ;
+end ;
+
+@* The main program.
+Now that we have all the pieces written, let us put them together.
+
+@p 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 .
+
+@* System-dependent changes.
+This section should be replaced, if necessary, by changes to the program
+that are necessary to make \.{PXtoPK} work at a particular installation.
+Any additional routines should be inserted here.
+@^system dependencies@>
+
+@* Index.
+Pointers to error messages appear here together with the section numbers
+where each ident\-i\-fier is used.