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
|
<HTML
><HEAD
><TITLE
>Compression algorithm, 1 July 1997</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
REL="HOME"
HREF="t1.html"><LINK
REL="PREVIOUS"
TITLE="References"
HREF="x525.html"><LINK
REL="NEXT"
TITLE="Copying conditions of the compression code, 1 July 1997"
HREF="a537.html"></HEAD
><BODY
CLASS="appendix"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
></TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="x525.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="a537.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="appendix"
><H1
CLASS="appendix"
><A
NAME="compressor"
></A
>B. Compression algorithm, 1 July 1997</H1
><P
> Markus Gutschke, gutschk AT math PERIOD uni-muenster PERIOD de
</P
><P
> The compressor achieves an average compression rate of 60% of the
original size which is on par with "gzip". It seems that you cannot do
much better for compressing compiled binaries. This means that the
break even point for using compressed images is reached, once the
uncompressed size approaches 1.5kB. We can stuff more than 12kB into
an 8kB EPROM and more than 25kB into an 16kB EPROM. As there is only
32kB of RAM for both the uncompressed image and its BSS area, this
means that 32kB EPROMs will hardly ever be required.
</P
><P
> The compression algorithm uses a 4kB ring buffer for buffering the
uncompressed data. Before compression starts, the ring buffer is
filled with spaces (ASCII character 0x20). The algorithm tries to
find repeated input sequences of a maximum length of 60 bytes. All
256 different input bytes plus the 58 (60 minus a threshold of 2)
possible repeat lengths form a set of 314 symbols. These symbols are
adaptively Huffman encoded. The algorithm starts out with a Huffmann
tree that assigns equal code lengths to each of the 314 symbols
(slightly favoring the repeat symbols over symbols for regular input
characters), but it will be changed whenever the frequency of any of
the symbols changes. Frequency counts are kept in 16bit words until
the total number of compressed codes totals 2^15. Then, all frequency
counts will be halfed (rounding to the bigger number). For unrepeated
characters (symbols 0..255) the Huffman code is written to the output
stream. For repeated characters the Huffmann code, which denotes the
length of the repeated character sequence, is written out and then the
index in the ring buffer is computed. From this index, the algorithm
computes the offset relative to the current index into the ring
buffer. Thus, for typical input data, one would expect that short to
medium range offsets are more frequent than extremely short or medium
range to long range offsets. Thus the 12bit (for a 4kB buffer) offset
value is statically Huffman encoded using a precomputed Huffman tree
that favors those offset values that are deemed to be more
frequent. The Huffman encoded offset is written to the output data
stream, directly following the code that determines the length of
repeated characters.
</P
><P
> This algorithm, as implemented in the C example code, looks very good
and its operating parameters are already well optimized. This also
explains why it achieves compression ratios comparable with
"gzip". Depending on the input data, it sometimes excells considerably
beyond what "gzip -9" does, but this phenomenon does not appear to be
typical. There are some flaws with the algorithm, such as the limited
buffer sizes, the adaptive Huffman tree which takes very long to
change, if the input characters experience a sudden change in
distribution, and the static Huffman tree for encoding offsets into
the buffer. The slow changes of the adaptive Huffman tree are
partially counteracted by artifically keeping a 16bit precision for
the frequency counts, but this does not come into play until 32kB of
compressed data is output, so it does not have any impact on our use
for "etherboot", because the BOOT Prom does not support uncompressed
data of more then 32kB (c.f. doc/spec.doc).
</P
><P
> Nonetheless, these problems do not seem to affect compression of
compiled programs very much. Mixing object code with English text,
would not work too well though, and the algorithm should be reset in
between. Actually, we might gain a little improvement, if text and
data segments were compressed individually, but I have not
experimented with this option, yet.
</P
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="x525.html"
ACCESSKEY="P"
>Prev</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="t1.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="a537.html"
ACCESSKEY="N"
>Next</A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>References</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
> </TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Copying conditions of the compression code, 1 July 1997</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
|
