ZX-COMPANDER for Sinclair ZX-81
by I.F. Boulton
from Your Computer, March 1984

ZX-Compander, a text compression routine for the ZX-81,
is explained by I.F. Boulton


Even with a 16K RAMpack the memory space of a ZX-81 is rapidly used up
by programs containing large amounts of text. Adventure games and
programs with Help messages or long instructions can often not be
squeezed in at all. What is needed is a way of compressing text before
storage so that it occupies much less memory space and then expanding
just those sections required at a particular time, back to their
original form.

Information can be compressed insofar as it is predictable; that is if
we can find, for instance, sequences of letters that frequently occur
in the text, we can code the whole sequence as one character each time
it occurs. ZX-Compander works by storing certain pairs of characters
in the message as single bytes. This method allows a maximum
compression of 50 percent if all the message is composed of those
pairs of letters which are being coded.

Each character recognised by the ZX-81 is stored as a single byte in
memory. The non- inverted letters, numbers and most of the punctuation
and arithmetic symbols have codes in the range 0 to 63. Thus of the
256 possible character codes 192 arc not used in normal English, these
codes are thus available for defining the pairs of letters we wish to
encode.

ZX-Compander operates by searching through the text for any of the 18
characters stored in locations 16514 to 16529; when one is found the
next character is checked to see if it matches any of the 12
characters stored in locations 16514 to 16525.

If such a match is found the first character of the pair is replaced
by a character whose code - in the range 64 to 255 - is calculated
from the codes of the letters in the pair. The other member of the
pair is then overwritten by the rest of the text being moved one
character down in memory. This movement does not actually shorten the
whole text string, it leaves the compressed text followed by a number
of identical characters.

The character repeated at the end is the last character of the
original text - this will in fact always be "$" - the number of
repeats being equal to the number of times the message has been coded
and moved down in the memory. Thus the text will be shortened by one
character for every pair found, while the string remains the same
length in memory. The actual compression occurs when the machine-code
routine returns to Basic.

The BC register pair - whose contents is returned as the argument of
the USR function - contains the length of the compressed text. The
original string is thus shortened by a line of the form:
	LET A$=A$( TO USR 16621)
The reason why 16 characters are sought out initially and only a
subset of 12 of these is accepted for the second member of the pair is
that with only 192 (192=16*12) codes free we cannot uniquely represent
256 (256=16*l6) pairs.

The expansion section of the program reverses the above procedure
except that the decode result is printed directly onto the screen.
This allows the whole memory to be filled with program and data
without having to leave an indefinite amount of space available for
holding decompressed text.

The compression which can be achieved using the program depends on the
careful matching of the first 12 of the 16 characters to the text
being coded - the last four have much less impact but are worth
considering. The letters used in the listed program are the 12 most
common letters in English - ETAOINSHRDLU - plus the space character
and three other common letters - GCY. The space character is placed at
the start of the list to speed the search as it is frequently the most
common character in a text.

As your text may contain many numbers or symbols the program has been
designed so that the only alteration needed to allow different sets of
characters to be recognised is for the relevant character codes to be
POKEd into locations 16514 to 16529.

Another feature is that the character table and decoding routine are
held in the first REM while the encoding routine is held in the
second. This allows you to delete the encoding routine once all the
text has been compressed, freeing another 89 bytes of precious memory.

Beyond the restriction that your initial text cannot contain
characters with codes over 63, there is one further problem; because
the variables in the ZX-81 are moved about in memory by the machine's
operating system it is necessary to flag the beginning and end of the
text string so that the routines can recognise their data. This is
done by starting the string with $$$, separating units within the text
that need to be separately retrieved - up to a maximum of 256 items -
with $ and terminating the data with $$. For this reason the $ sign
may not he used casually in the text, and the $$$ sequence must not
occur in other strings in the memory.

Start entering the program by typing a line 1 REM followed by a single
space and then l00 zeros and a line 2 REM followed by 84 zeros. The
machine-code loader in Listing 1 can then be typed in and RUN.
Carefully enter all the decimal codes in Listing 2; addresses are
given for every fifth byte to help you check your input.

Then edit line 10 to read
	FOR I=16621 TO 16704
[... and change the checksum from 10191 to 7612. JimG] and RUN the
program again, this time entering the codes in Listing 3. This should
give you two REMs identical to those shown in Listing 4 .If all is
well delete the loading program and enter the Basic lines from Listing
4. It is wise to save the program now before running it, as any
mistakes in the machine code will crash the machine.

If there are any mistakes in the routines, corrections can be POKEd
into the REMs; any attempt to Edit them will probably corrupt the
code.

The program can now be RUN. When prompted enter any string you choose
which obeys the rules on allowable characters. If you wish you can
separate sections within the text with $ signs. After you hit Newline
the text will be encoded. You will then be asked for the item number
you require. This will normally be 1 unless you have put $ separators
in the text. If you enter an item number which does not exist the
program will crash.

The item you have requested will now be printed starting at the first
free print position on the screen. If the original text is not
recovered or the program crashes the routine must be carefully checked
using Peek. Once everything is working smoothly you can proceed to use
the routines in application programs.

As the routine adds five bytes of $ to the message, plus one byte for
each separator, the greatest compression will only be achieved on
relatively long sections of text. The routines typically achieve
compressions of 30 to 40 percent on a wide range of input; from this,
and the amount of memory occupied by the decoding routine - 104 bytes
- it can be seen that savings in overall memory usage begin to appear
when the text is over about 300 characters long. Although the
compressed string actually appears longer this is due to certain codes
appearing as keywords.

In general your final application program should be developed by first
loading the ZX Compander routines from tape, adding in Basic whatever
editing facilities you need to aid the input of your text, entering
the text, and then compressing it using a line like line 30 in Listing
4. Once this has been done the editing section and line 2 can be
deleted. When you need to print an item all that is required is that
the item number be Poked into 16507, the print position be specified
using PRINT AT and the routine called using RAND USR 16566.

The routines are not relocatable due to the numerous subroutine calls
using absolute addresses.

