diff options
Diffstat (limited to 'obsolete/systems/knuth/unsupported/mfware/pxtopk.web')
-rw-r--r-- | obsolete/systems/knuth/unsupported/mfware/pxtopk.web | 1648 |
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. |