Compressed data format on the ZX Spectrum
As I could understand my articles enough dry exposition.
Because of this, I able to estimate, even being glued
together, they gather in very small book. Perhaps this is due to
that I omit unwittingly
details? If so, then what I write, without
My advice is not to read ...
Unfortunate.
Nevertheless, I ventured to create a
another lengthy opus, claiming the utility in terms of overall
development. It does not matter if nothing is written in it you
do not can remember (I do very little out
I remember, because and began recording). This is not
poem, which must learn to
lessons, and not the adventures of sword and blaster.
There simply gives some scattered information on the
possibility of expressing in words (we call this process
"verbalization") of certain structures that are difficult in a
sense "feel." At the same time after reading the reader will be
able to remotely imagine yourself method of analysis and, in
fact, the presentation of such structures, although I, as a
writer, especially not on a specified concentrated.
Note also that the material does not
exhaustively.
It should, inter alia, to avoid
looks like "a really ...", especially regarding terminology.
Used terminology, I will mention here, she is established in
the context of my personal thinking and may not correspond to
the intuitive reader, especially if it has a specific education
in this oblasti.Odnako, as far as my earlier experiences of
this kind of verbalization almost was not made, and as such
generally accepted terminology does not exist. Same source text
circulated for similar rights are not readable.
So, my terms:
disp (displacement - displacement) or dist
(Distance - distance) - characteristic
shift from the current position of the output stream (the file
being recovered) to the repeated fragment in the LZ77-based
methods. (What are the methods, in fact, consist in that from
time to time to copy snippets from behind somewhere ahead, and
namely "a cursor, that is, as the judges the current position.)
disp If before I put a minus This means that this
characteristic has has a negative sign for the receipt of
Address fragment adds not otni maetsya of current address.
dispH, dispL - senior and junior bytes
disp.
puts or len - the length of the repeated fragment. Fragment
can be replicated over themselves. The most typical case of
this kind occurs when disp = 1, and reduced to repetition
the same byte.
For instructions type disp4 len7 or hiding the number of
bits in this number.
tree (tree) - a structure used
to store information about how binary
codes of various lengths are of a certain set of characters
(literal). Considered Fano and Huffman. The method of
constructing the tree, proposed by Fano, in general, worse
Haffmanovskogo, since for the latter proved optimality.
According to Huffman tree is built consistent association of
two rare units with the summation of the frequency for use of
the sum frequency at subsequent associations. According to
Fano, if the reader is interested, the tree is constructed
successive division of the list sorted by frequency of literal
roughly equal to the left (zero), and right (single)
sub-branches. Trees, if go to practice, may be stored in many
ways - pointers, tiers or even implicitly.
% - A binary representation;
# - Hexadecimal representation.
bit stream - data that is retrieved by bit (like shift);
byte stream - the data retrieved byte (which is obviously
faster).
There are several ways of sharing both types of flows in
A file with sequential access.
(By this idea was first implemented, it is difficult to
assume.) This, for example, the simplest way:
1. File is retrieved from the byte buffer
bitstream, and the pointer moves;
2 and more. Byte of the address pointer.
Bits is extracted from the byte buffer, when it
running out of work similarly to step 1.
... And its variation, where instead of "byte-buffer bit
stream" appears "slovobufer" (16 bits).
In format, using both flow
mixed form, the order is important extraction
data from them. I do not specify this order in
text, just write code structure is
in order. Ie if it is written:
% Xxxx, dispH3 - a reference to something. dispL in
byte stream. puts = so much,
it should be understood that the first of the bit stream
read% xxxx, dispH3, and only then from a byte - dispL.
Typically, the bits are extracted from left to right (7,6,
..., or 15.14, ...). Except a compressor RIP 0.2x, where it
happens the other way. But this will be written separately.
A. Encoder
