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