summaryrefslogtreecommitdiff
path: root/dviware/driv-standard/level-0/pk.tex
blob: 2577a49a65ac6d1453a4cab134d0ffc44bb9a1fe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
% $Id: pk.tex,v 2.3.1.1 1991/08/08 16:21:26 schrod Released schrod $
%------------------------------------------------------------
% taken from PKtype 2.3

%
% definition of PK format
% LaTeX markup
%


% $Log: pk.tex,v $
% Revision 2.3.1.1  1991/08/08  16:21:26  schrod
% CHANGES BY DON HOSEK:
%  -- Inserted \subsection's.
%  -- Deleted WEB defines.
%  -- `e.g.' now in italics, to be consistent with the rest of the
%     standard.
%
% CHANGES BY JOACHIM SCHROD:
%  -- Changed \bigbreak between WEB sections to \medbreak.
%  -- Added + signs to length specifications in \cmd tags, to show that
%     the param is signed.
%  -- Make formulas look more `math-like' and less `Pascal-like.'
%  -- Example and `packed number decoding algorithm' as figures.
%  -- Exchange this crude example picture with the explicite halign with
%     an environment for drawing letter examples.
%
% Revision 2.3  1990/11/15  19:03:50  schrod
% integrated changes of 18 Nov 89 by Don: The weight of bits were specified
% wrong and a few phrases were changed.
%    Please note that these changes make version 2.3, even if this is not
% noted in the version history of PKtype. But the version change was made
% both on the title page and in the banner message.
%
% Revision 2.2.1.2  90/07/17  00:00:00  schrod
% two \& were forgotten.
% 
% Revision 2.2.1.1  90/07/16  00:00:00  schrod
% adapted to PKtype change of Don (Hosek? Knuth? -- 21 Oct 89).
% changed \& to \res in documentation parts.
% appended \endinput.
% 
% Revision 2.2  90/07/04  00:00:00  schrod
% extracted from PKtype 2.2
% 



\section{Packed File Format}
\label{pk-format}

\subsection{Introduction}

The packed file format is a compact representation of the data
contained in a \str{GF} file. The information content is the same,
but packed (\str{PK}) files are almost always less than half the size
of their \str{GF} counterparts. They are also easier to convert into
a raster representation because they do not have a profusion of
\id{paint}, \id{skip}, and \id{new\_row} commands to be separately
interpreted. In addition, the \str{PK} format expressedly forbids
\res{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 \str{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 \str{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 is separated into two sets,
those that introduce a character definition, and those that do not.
The values that introduce a character definition range from 0 to 239;
byte values above 239 are interpreted as commands. Bytes that
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 \str{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.

\medbreak

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



\subsection{Summary of {\tt PK} commands}

First, the command bytes will 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 ({\it e.g.},
\id{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.)

\cmd \id{pk\_xxx1} 240, k[1] x[k].
 This command is undefined in general; it functions as a $(k+2)$-byte
\id{no\_op} unless special \str{PK}-reading programs are being used.
\MF\ generates \id{xxx} commands when encountering a \res{special}
string. It is recommended that $x$ be a string having the form of a
keyword followed by possible parameters relevant to that keyword.

\cmd \id{pk\_xxx2} 241, k[2] x[k].
 Like \id{pk\_xxx1}, but $0\le k<65536$.

\cmd \id{pk\_xxx3} 242, k[3] x[k].
 Like \id{pk\_xxx1}, but $0\le k<2^{24}$. \MF\ uses this when sending
a \res{special} string whose length exceeds~255.

\cmd \id{pk\_xxx4} 243, k[4] x[k].
 Like \id{pk\_xxx1}, but $k$ can be ridiculously large; $k$ musn't be
negative.

\cmd \id{pk\_yyy} 244, y[4].
 This command is undefined in general; it functions as a five-byte
\id{no\_op} unless special \str{PK} reading programs are being used.
\MF\ puts \id{scaled} numbers into \id{yyy}'s, as a result of
\res{numspecial} commands; the intent is to provide numeric
parameters to \id{xxx} commands that immediately precede.

\cmd \id{pk\_post} 245,.
 Beginning of the postamble. This command is followed by enough
\id{pk\_no\_op} commands to make the file a multiple of four bytes
long. Zero through three bytes are usual, but any number is allowed.
This should make the file easy to read on machines that pack four
bytes to a word.

\cmd \id{pk\_no\_op} 246,.
 No operation, do nothing. Any number of \id{pk\_no\_op}'s may appear
between \str{PK} commands, but a \id{pk\_no\_op} cannot be inserted
between a command and its parameters, between two parameters, or
inside a character definition.

\cmd \id{pk\_pre} 247, i[1] k[1] x[k] \id{ds}[4] \id{cs}[4] \id{hppp}[4] %
\id{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 \str{PK} file. The parameters \id{ds}
and \id{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
\str{TFM} file and the \str{GF} files for this font. Parameters
\id{hppp} and \id{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.''



\subsection{Packing algorithms}

The \str{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 left to right, traversing rows from the
top to bottom. This is essentially the way the \str{GF} format works.
Instead of presenting each row individually, however, we 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 easily be reconstructed. In addition, we
do not need special commands to mark the end of one row and the
beginning of the next.

Next, we place 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 that encloses all `black' pixels of a
character. We 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 seem 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 \str{PK} file format are
based on the four-bit nybble.

\medbreak

An analysis of typical pixel files yielded another interesting
statistic: Fully 37\,\% of the raster rows were duplicates of the
previous row. Thus, the \str{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.

\medbreak

Now we 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. 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.

\medbreak

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

We can analyze our several dozen pixel files and determine an optimal
value of \id{dyn\_f}, and use this value for all of the characters.
Unfortunately, values of \id{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 \id{dyn\_f} on a character basis, picking the
value that will pack each individual character in the smallest number
of nybbles. Legal values of \id{dyn\_f} run from 0 (with no
one-nybble run counts) to 13 (with no two-nybble run counts).

\medbreak

Our only remaining task in the coding of packed numbers is the large
run counts. We use a scheme suggested by {\sc D.\,E.~Knuth} that
simply and elegantly represents 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-\id{dyn\_f})\ast16+\id{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-\id{dyn\_f})\ast16+\id{dyn\_f}+1$ and adding 16,
and then we represent the result according to the scheme above.



\subsection{Decoding {\tt PK} files}

The final algorithm for decoding the run counts based on the above
scheme might look like the Pascal routine in
figure~\ref{fig:pk_packed_num}, assuming that a procedure called
\id{pk\_nyb} is available to get the next nybble from the file, and
assuming that the global \id{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.

\begin{figure*}
\begin{webprog}
\P\4\&{function}\1\  \37\\{pk\_packed\_num}: \37\\{integer};\6
\4\&{var} \37$\|i,\39\|j$: \37\\{integer};\2\6
\&{begin}\5
$\|i\K\\{get\_nyb}$;\6
\&{if} $\|i=0$ \1\&{then}\6
\&{begin}\6
\1\&{repeat}\5
$\|j\K\\{get\_nyb}$;\5
$\\{incr}(\|i)$;\6
\4\&{until}\5
$\|j\I0$;\2\6
\&{while} $\|i>0$ \1\&{do}\6
\&{begin}\5
$\|j\K\|j\ast16+\\{get\_nyb}$;\5
$\\{decr}(\|i)$;\6
\&{end};\2\6
$\\{pk\_packed\_num}\K\|j-15+(13-\\{dyn\_f})\ast16+\\{dyn\_f}$;\6
\&{end}\6
\4\&{else} \&{if} $\|i\L\\{dyn\_f}$ \1\&{then}\5
$\\{pk\_packed\_num}\K\|i$\6
\4\&{else} \&{if} $\|i<14$ \1\&{then}\5
$\\{pk\_packed\_num}\K(\|i-\\{dyn\_f}-1)\ast16+\\{get\_nyb}+\\{dyn\_f}+1$\6
\4\&{else} \&{begin}\6
\&{if} $\\{repeat\_count}\I0$ \1\&{then}\5
$\\{abort}(\.{\'Second\ repeat\ count\ for\ this\ row!\'})$;\2\6
$\\{repeat\_count}\K1$;\C{prevent recursion more than one level}\6
\&{if} $\|i=14$ \1\&{then}\5
! $\\{repeat\_count}\K\\{pk\_packed\_num}$;\2\6
$\\{send\_out}(\\{true},\39\\{repeat\_count})$;\5
$\\{pk\_packed\_num}\K\\{pk\_packed\_num}$;\6
\&{end};\2\2\2\6
\&{end};\par
\end{webprog}
\caption{Algorithm for decoding run counts in a \protect\str{PK} file}
\label{fig:pk_packed_num}
\end{figure*}

\medbreak

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 \str{PK} format allows bit-mapping of the characters.
This is indicated by a \id{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 $\lfloor
(\id{width}\ast\id{height}+7) / 8 \rfloor$. 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.

\medbreak

At this point, we are ready to introduce the format for a character
descriptor. It consists of three parts: a flag byte, a character
preamble, and the raster data. The most significant four bits of the
flag byte yield the \id{dyn\_f} value for that character. (Notice
that only values of 0 through 14 are legal for \id{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 8) 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 4) 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 packet-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; the
one that 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.

\begin{description}
\let\sp=\ %				% save meaning of `\ ' in this env
\everymath{\def\ {\allowbreak\sp}}	% allow line break within math list

\item[Short form]
 $\id{flag}[1]\ \id{pl}[1]\ \id{cc}[1]\ \id{tfm}[3]\
	\id{dm}[1]\ w[1]\ h[1]\ \id{hoff}[+1]\ \id{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 \str{cminch}.

\item[Extended short form]
 $\id{flag}[1]\ \id{pl}[2]\ \id{cc}[1]\ \id{tfm}[3]\ \id{dm}[2]\ w[2]\ h[2]\ 
	\id{hoff}[+2]\ \id{voff}[+2]$.\\
 Larger characters use this extended format.

\item[Long form]
 $\id{flag}[1]\ \id{pl}[4]\ \id{cc}[4]\ \id{tfm}[4]\ \id{dx}[4]\ \id{dy}[4]\
	w[4]\ h[4]\ \id{hoff}[4]\ \id{voff}[4]$.\\
 This is the general format which allows all of the parameters of the
\str{GF} file format, including vertical escapement.

\end{description}
%
 The \id{flag} parameter is the flag byte. The parameter \id{pl}
(packet length) contains the offset of the byte following this
character descriptor, with respect to the beginning of the \id{tfm}
width parameter. This is given so a \str{PK} reading program can,
once it has read the flag byte, packet length, and character code
(\id{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
$(\id{flag} \bmod 4)\cdot 256+\id{pl}$; for the short
extended format, it might be calculated as
$(\id{flag} \bmod 4)\cdot 65536+\id{pl}$.

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

\medbreak

\TeX\ requires all characters that have the same character codes
modulo 256 to have also the same \id{tfm} widths and escapement
values. The \str{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 standard version of \TeX\
cannot output character codes greater than 255, but extended versions
do exist.)

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.



\subsection{An example character}

As an illustration of the \str{PK} format, the character \char4\ from
the font {\tt 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 is shown in
figure~\ref{fig:pk-char-pic}.
%
 \begin{figure*}[tb]
\begin{paintletter}
&  ********************
&  ********************
&  ********************
&  ********************
&  **                **
&  **                **
&  **                **
& 
& 
&    **            **  
&    **            **  
&    **            **  
&    ****************  
&    ****************  
&    ****************  
&    ****************  
&    **            **  
&    **            **  
&    **            **  
&
&
&
&  **                **
&  **                **
&  **                **
&  ********************
&  ********************
&  ********************
&+ ********************
\end{paintletter}
\caption{Character \char4{} of {\tt amr10} (the row numbers are
         chosen for convenience, and are not \protect\MF's row numbers.)}
\label{fig:pk-char-pic}
\end{figure*}
%
 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 \id{hoff} value is $-2$,
and the \id{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:
%
 \begin{center}
 82 [2] (16) 2 (42) [2] 2 (12) 2 (4) [3]\\
 16 (4) [2] 2 (12) 2 (62) [2] 2 (16) 82\\
 \end{center}
%
 Note that any duplicated rows that are not all white or all black
are removed before the run counts are calculated. The rows thus
removed are rows 5, 6, 10, 11, 13, 14, 15, 17, 18, 23, and 24.

\medbreak

The next step in the encoding of this character is to calculate the
optimal value of \id{dyn\_f}. The details of how this calculation is
done are not important here; suffice it to say that there is a simple
algorithm that can determine the best value of \id{dyn\_f} in one
pass over the count list. 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):
%
 \begin{center}
 \tt
 D9 E2 97 2 B1 E2 2 93 2 4 E3\\
 97 4 E2 2 93 2 C5 E2 2 97 D9\\
 \end{center}
%
 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.

\medbreak

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 \id{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
\id{dyn\_f} value of 8. The final total character packet, in
hexadecimal, is given in figure~\ref{fig:pk-char-xd}.

\begin{figure}
\begin{center}
\begin{tabular}{r@{\qquad}lll}
   Flag byte& \tt 88\\
   Packet length& \tt 1A\\
   Character code& \tt 04\\
   \id{tfm} width& \tt 09& \tt C7& \tt 1C\\
   Horizontal escapement (pixels)& \tt 19\\
   Width of bit map& \tt 14\\
   Height of bit map& \tt 1D\\
   Horizontal offset (signed)& \tt FE\\
   Vertical offset& \tt 1C\\
   Raster data& \tt D9& \tt E2& \tt 97\\
   & \tt 2B& \tt 1E& \tt 22\\
   & \tt 93& \tt 24& \tt E3\\
   & \tt 97& \tt 4E& \tt 22\\
   & \tt 93& \tt 2C& \tt 5E\\
   & \tt 22& \tt 97& \tt D9\\
\end{tabular}
\end{center}
\caption{\protect\str{PK} character packet for \char4{} of {\tt amr10}}
\label{fig:pk-char-xd}
\end{figure}




\endinput