
**********************************************************************
files: Compression.TXT
       http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzdemo1.bas
       http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzgraphic.gif
       wip-lz77.zip (last draft version, bugged)
       wip-lz77-a.zip (reverted to earlier version, not bugged)
       lzdemo-0.zip (final working version)
**********************************************************************


This file contains two sections: draft & final. A small but significant change was made to the encoding procedure in the final version which simplified both the program code and the data encoding, and also made the program quicker, smaller and more efficient. Methods of increasing complexity were employed to improve the compression in the draft versions; these were mostly discarded for the final version.


** Lempel-Ziv compression routine (draft)
   ==============================

I've written an LZ77 en/decoding routine as I couldn't find one around for the Spectrum. Initially I'm just doing it in BASIC to get the logic right. It works, in that it encodes the file and the decoder restores it, but the output is bigger than the input so it's currently not much use for its intended purpose of data compression. There's an exhaustively commented listing [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzdemo1.bas]here[/url] (it's not very long).

   ==============================

I chose LZ77 by accident, really. It was the first one for which I found a comprehensive set of source code files (MegaLZ), but that only had a Z80 assembler version for the unpacker, the packer being in C, so I decided to write a Z80 version. After giving up on converting the C code, and after more searching, I found an excellent description of the LZ77 process on an orphaned page of a redundant site (see [url=https://sites.google.com/site/datacompressionguide/lz77]Data Compression Guide (LZ77/LZSS)[/url]), from which I was able to construct the BASIC version fairly easily. I've now done a straight Z80 conversion of that without any optimisation for size or speed, which I'll work on to get an efficient version, which will have to be more bit-based than byte-based.

   ==============================

Making progress; by using a 2kb window and half-byte counters (limiting matches to 15 characters) I've got a reduction of -43% on the test file.

   ==============================

I decided that there was too much repetition in the test file and replaced it with one with very little repetition, thereby reducing the reduction to -10%, so there's still some substantial improvement needed there.

   ==============================

I thought that there might be a problem with unpacking, in that, because of its self-referential nature, it's not possible to just select a piece of an LZ77 file to unpack; it always has to be unpacked from the start, as it needs to refer to what has gone before. Whereas, if it's holding location descriptions & graphics, I'd only want to unpack the segment for a particular location at any one time. However, as the unpacking is very quick, it will probably be practical to unpack from the start each time and just discard everything up to the required entry (or group of adjacent entries, to reduce the unpacking overhead).

It's not quite that simple because, as the unpack procedure refers back to what it's unpacked to retrieve repeated segments, some of it would have to be kept temporarily for reference, the maximum size needed being the size of the sliding window. To give some potential for reducing that workspace a value could be recorded at the start of the packed file giving the maximum "look behind" needed to unpack it.

So the whole of the packed file has to be held in main RAM at least temporarily (on the 48k; on the 128k a larger file than would fit could be loaded in window-size chunks and copied to RAMdisk, I suppose) but only a fraction of its total unpacked size is needed to unpack any particular segment within it; ie. window size + segment size + unpack code (short).

Apparently the LZ77 packing process can be substantially speeded up by using a circular rather than linear sliding window, but I don't really understand the explanation for that just at the moment. As the packing is done "extra ludum" its speed isn't quite so important. Given the way it works I'd expect LZ77 to be better at packing graphics rather than text, so I'll have to do comparisons with separate & mixed files.

   ==============================

Nope, I still don't understand this (this is from a different page to the one which I mentioned before).

[quote]A common technique to speed up LZ77 or LZSS compression is to write the symbols in the sliding window using a [i]modular addition[/i] operation. Instead of shifting the window LEN characters when a match is found (which is too slow), we just insert to the window position [b]mod[/b] [i]N[/i] whenever we need to write the new characters, where [i]N[/i] is the size of the window. This way, the window acts as a [i]circular array[/i], without ever shifting the characters. ( [i]The Data Compression Guide[/i] )[/quote]

I don't see how "shifting the window LEN characters when a match is found" is "too slow". I have two pointers, for the left- and right-hand edges, and add 'L+1' to each after a matching string has been copied to the output, where 'L' is the matched length (might be zero) plus one for the first unmatched character; it couldn't be much shorter.

Initially the window is zero size and only the right-hand edge extends as characters are read until it reaches the specified width, after which both edges move in step. I don't "write the symbols in the sliding window", I only read them and write to the output file. I'm not clear as to what "insert to the window position [b]mod[/b] [i]N[/i]" means either.

The slow bit is searching for extended matches, not moving the window, as it has to be checked for all matches to the character at the coding position 'cp', then each of those matches checked for a subsequent match on (cp+1), then each of those checked against (cp+2), and so on, until no further match is found, after which the string matching (cp+n-1), plus the unmatched character at (cp+n), are copied to the output, the window and coding position shifted right by the length output, and repeat to EOF.

-----

I tried the routine with a SCREEN$ from Forest of Doom and the compression was -53%, which is pretty good for a first attempt; so it's getting efficient text compression which is more of a problem.

   ==============================

This paragraph from the MegaLZ README would indicate that its packed file format is specific to itself.

[quote]While  the  original  Speccy  MegaLZ  (old  MegaLZ)  was  quite straightforward in selection of LZ codes, this new MegaLZ does a nice  thing:  it selects the best LZ codes chain through all the file,  using  smart  algorithm,  which  is close to the Dijkstra algorithm  for  searching  a shortest path.  As a result, packed file  sizes  decrease  up  to  5%,  which  is equivalent to size decrease  about 1000 bytes on 20kB packed file.  Some comparison of packing ratio with other packers available on Speccy was also done.[/quote]

   ==============================

I changed the lookback pointer to be a relative address from the coding position (it should have been that from the start anyway, but never mind) so it only needs to be as big as the window. This saved me 4 bits per entry for matches of two characters or more.

In addition I realised that, as the window is only 2048 bytes, that just needs 11 bits for offsets, so I used the spare bit as a scale indicator:
offsets . 0- 127 held as 0 000 0000 .... to 0 111 1111
offsets 128-2047 held as 1 000 1000 0000 to 1 111 1111 1111
which saved me another 4 bits for offsets less than 128.

I also changed the match selection to work backwards from the coding position rather than forwards from the left-hand window edge, making it more likely to find a match offset <128 and use the shorter pointer entry. These changes increased the compression for text from -10% to -24%, and for graphics from -53% to -59%. The unpacking is very quick, but the packing is still rather slow, so more work needs to be done on that in particular.

   ==============================

Here's some stats for the WIP-LZ77 routine; a SCREEN$ on the left and text on the right. Sorted by match length; 0-match 1st row; 1-match 2nd row, and so on. (There's a slight glitch in the unpacking; the SCREEN$ should be 6912 of course, and the text 2512.)

The SCREEN$ result is pretty good and could easily be made even better, as can be seen by the cluster on the last row, by allowing match lengths >15; just adding one bit to the match length and taking one bit off the pointer would be easiest.

Improving the text compression is more of a problem, due to the high incidence of short matches. I'm a bit short of ideas on that one - although bits will undoubtedly be instrumental in a solution.
[code]
Entries   Packed    Unpacked      Entries   Packed    Unpacked
 128       192        128           37        55.5       37
 310       775        620          183       457.5      366
  96       269.5      288          232       631        696
  50       135.5      200          138       397        552
  30        83.5      150           55       152.5      275
  70       192        420           30        85        180
  49       136        343           15        41.5      105
  50       142.5      400           12        35         96
  40       115        360            7        21         63
  36       100.5      360            6        17         60
  24        66.5      264            4        10         44
  25        71.5      300            0         0          0
  19        55        247            3         9         39
  18        52.5      252            0         0          0
  10        29        150            0         0          0
 152       454.5     2432            0         0          0

1107      2870.5     6914          722      1912       2513
Compression: -59%                 Compression: -24%
[/code]

   ==============================

Mentioning capitals reminded me that the text I was using wasn't particularly realistic, as half was all lower case and half upper case. So I made a new test file from the text of my postings on this topic and got much better results (-40%).

I can demark the output into "type" blocks, prefixed by a byte (or just a bit, really) to indicate to the unpack routine that the next "type" bytes it outputs have been encoded as either a 7-bit or 8-bit block. Although the encoded blocks will vary in size, as the packer is counting its input and the unpacker its output they will keep in step.

I've also managed to speed up the packer by about 400% (although it was [b]very[/b] slow before, so it could still do with being faster). Here's some new stats for text, on a larger file than before.
[code]
Entries   Packed    Unpacked
  40        60         40
 210       525        420
 361       997.5     1083
 278       797       1112
 163       475.5      815
 101       295        606
  68       198        476
  45       130.5      360
  36       106.5      324
  16        47        160
   9        27         99
  10        29.5      120
  11        32.5      143
   7        20.5       98
   3         9         45
  30        89        480

1388      3839.5     6381
Compression: -40%
[/code]

   ==============================

Here's an illustration of the procedure involved in the matching phase of the routine.

[center][img]http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzgraphic.gif[/img][/center]

1. Search the input segment delimited by the window WA<->WZ for all matches on (CP), the character at the Coding Position.
2. Mark each match pointer PB in the window.
3. Extend the lookahead pointer CN by incremental step 'n' from CP.
4. Mark each match pointer PB which both matched the previous character and where the character (PB+n)=(CN).
5. Repeat 3-4 until 4 finds no further matches.
6. Encode the rightmost match string at position PB length PL (zero if no matches) plus the unmatched character (CN).
7. Update the window coordinates WA,WZ and Coding Position CP by PL+1.
8. Repeat 1-7 until EOF.

At present all the parameters WA,WZ,PL,PB,CP,CN (and some more) are held as effectively variables in RAM, so if I want to update any I do; eg:
LD HL,(WA) : LD DE,(PL) : ADD HL,DE : LD (WA),HL
I have 20 variables altogether positioned from 65368 upwards.

One possible improvement is with regard to the PB list of pointers to initial matches created at step 2. Step 4 checks all the entries in the initial match list each time, either to compare the next character if the last one matched or to skip that entry if it didn't match. If I discarded redundant entries on each pass by compressing the list then subsequent steps 4 would be quicker, but compressing the list in itself would take extra time, so it would depend on which occurred most often as to whether it was worth changing or not.

---

That change did make a big improvement, reducing the run time by 25% - although it still takes 2 minutes to compress a SCREEN$ (but less than a minute for a similar sized text file), so it's not finished yet.

   ==============================

After a sudden inspiration I totally rewrote the packing routine (although still based on the LZ77 algorithm) and now I've got the pack times down to 1 minute for a SCREEN$ (-59% compression) and 28 seconds for a similar size text file (-40% compression); unpacking just takes less than a second. In general, the bigger the file is the better the compression.

   ==============================

It was changing it to use CPDR from the leading window edge instead of CPIR from the trailing edge, together with discarding the pointers table I was using before, which took 10% off the size of the routine and 25% off the run time. On the other hand, making a change to the encoding section which saved about 10% in that part made no visible difference to the run time even though there's a lot more lines of code in that section.

As the packing routine basically just has those two parts - searching & encoding - there's nowhere else where any significant savings can be made; and as the searching section is now just 45 lines of code it's very difficult to find room for improvement. (Einar's timings spreadsheet is coming in very handy, though.)

   ==============================

I've speeded it up a bit more; a SCREEN$ now takes 52secs and a same size text file takes 30secs. I was doing several out of bounds checks before doing the character check, then I realised I didn't need to do the out of bounds checks if the characters didn't match, as all those error conditions jumped to the same place anyway, so I put the character check first which saved about 10secs from the previous version. I could save another 5secs by taking out the progress counter, but I like to see something happening when it's running.

I'll try that history table idea next, as I've got loads of space. I've allowed 30k for the input/ encoded/ decoded files, plus there's 9k unused below that which used to hold that table which I mentioned discarding. The program itself is 1k; that's both packer & unpacker; plus there's a little BASIC program.

   ==============================

The BASIC program to which I referred in my previous post is just a couple of lines which prints some debug info and runs the test program.
[code]
  10 CLEAR VAL "25099": LET s=VAL "6": DIM m(s):
     LET p=VAL "64000": LET l=FN p(p):
     PRINT AT VAL "2",NOT PI;l'':
     FOR a=SGN PI TO s:
       LET ad=VAL "p+l-(7-a)*2-1":
       LET m(a)=FN p(ad): PRINT m(a):
     NEXT a:
     PAUSE NOT PI: LET t1=FN t(): RANDOMIZE USR m(2):
     LET t2=FN t(): PRINT 't2-t1:
     DEF FN p(a)=VAL "PEEK a+256*PEEK (a+1)"
  20 DEF FN m(x,y)=(x+y+ABS (x-y))/2:
     DEF FN u()=VAL "65536*PEEK  23674+256*PEEK 23673+PEEK 23672"/50:
     DEF FN t()=FN m(FN u(),FN u())
[/code]
There's another small BASIC program which prepares a table of statistics from packed data files, as seen in post #21, for example. I fixed that glitch with the unpacked files being slightly longer than the originals. The packer hadn't been checking for EOF at the right place and was encoding a few extra bytes past the end of the file.

   ==============================

I shaved off another 5 seconds and a few bytes by changing the out of bounds checks to compare via the A register rather than using SBC, changing the OOB checks to be handled in decreasing frequency of occurrence, and calculating some parameters during assembly rather than runtime. Here's the central matching loop, in case there's any more room for improvement.
[code]
        ;determine the extent of the match
MALOOP: push af           ;3>
        inc  hl              ;window pointer
        inc  de              ;lookahead pointer
        ld   a,(de)          ;compare lookahead character
        cp   (hl)            ;   with window character
        jr   nz,NEXTSW       ;no further match

        ld   bc,(CPOS)
        ld   a,h
        cp   b
        jr   nz,MANEXT1
        ld   a,l
        cp   c
        jr   z,NEXTSW        ;reached Coding Position

MANEXT1:ld   bc,ILAST
        ld   a,d
        cp   b
        jr   nz,MANEXT2
        ld   a,e
        cp   c
        jr   z,NEXTSW        ;reached end of input

MANEXT2:pop  af           ;3<
        cp   MAXLEN
        jr   z,NEXTSW+1      ;reached maximum match length
        inc  a
        jr   MALOOP
[/code]

   ==============================

... and here's the loop which encloses MALOOP. (Just saved another 3secs by saving H'L' just once, before entering any of the loops, as it's not needed until the RET from the USR call anyway; plus saving "match start" with one "ld (PTMP),hl" rather than repeated "push hl : pop hl".)
[code]
PA2PZ:  ld   de,(CPOS)
        ld   a,(de)          ;A =character at Coding Position
        cpdr                 ;search backwards for a match
        jr   z,MASTART
        ld   a,(PLEN)
        or   a
        jr   nz,LONGEST      ;use the last longest match found

        ;no match in window; output a zero entry
NOMATCH:call OUTPUT
        jr   z,ENLOOPZ
        jr   ENLOOP

MASTART:push hl           ;1>;preserve match start registers
        exx
        ex   de,hl
        pop  hl           ;1<
        inc  hl
        push de           ;1>;save H'L' (holds calculator RET address)
        ld   a,1             ;match length
        ld   de,(CPOS)
        push hl           ;2>;match start

;======================================
;MALOOP goes in here
;======================================

NEXTSW: pop  af           ;3<;A =current match length
        pop  hl           ;2<;HL=match start
        ld   bc,(PLEN)       ;C =longest match length so far
        cp   c
        jr   c,NOTLONG
        jr   z,NOTLONG
        ld   (CNXT),de
        ld   (PBEG),hl
        ld   (PLEN),a
NOTLONG:pop  hl           ;1<restore H'L'
        exx
        cp   MAXLEN
        jr   nc,LONGEST
        ld   a,b
        or   c
        jr   nz,PA2PZ

        ;(PBEG) & (PLEN) will identify the last longest match found
LONGEST:call OUTPUT
        jp   z,ENLOOPZ
        jp   ENLOOP
[/code]

   ==============================

The three lines "ld a,(PLEN) : or a : jr nz,LONGEST" just before NOMATCH can be deleted and the comment there should read "no further matches in window; output the last longest match" (which may be "no match"). Then the NOMATCH triplet can be relabeled LONGEST, the other one removed and the six lines at NOTLONG terminated with a "jr LONGEST".

-----

I've tried several SCREEN$ giving -50%-60% compression in 40-50secs. A very "bitty" screen (the loading screen from The Code) only did -30% in 50secs, whereas a blank screen did -85% in 6secs.

   ==============================

There's a problem with that last one, due to the "jr z,NEXTSW+1" a few lines earlier which jump, if taken, sends everything to pot, as "current match length" would be in A rather than B; so that MANEXT2 section would need to be changed as well to keep things in synch.

   ==============================

I've uploaded the current development version of [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/wip-lz77.zip]WIP-LZ77[/url] for reference. There's an assembler listing, a BASIC listing of the test runner, and a Z80 snapshot with the test runner, machine code and a test SCREEN$ already loaded. I had to change three parameters from assembled constants to variables, so at present it runs a couple of seconds slower than before.
[code]
Memory usage:
PROG  -> 27099 : BASIC
27100 -> 33999 : (6900 bytes spare)
34000 -> 63999 : input/encoding/output (max. input 10000 bytes)
64000 -> 65367 : machine code (about 500 bytes spare)
65368 -> 65535 : working storage (about 100 bytes spare)
[/code]

The demo does both packing & unpacking in turn. Just load a BIN at 34000 and RUN, enter length, text flag, print flag (defaults 2048,1,1). If text=1 and print=1 then the output will be printed to the screen; if text=0 and print=1 then the output will be copied to the display file; otherwise the output will just be stored in memory at the location & size displayed at the end (that's always done, regardless of the options selected). When it's done "GO TO 10" will print statistics, although this part is still in BASIC and is rather slow.

   ==============================

I tried including the character history idea and, once I'd tracked down a latent bug in the previous version which was causing the new version not to work, it reduced a typical SCREEN$ packing time from 43secs to 28secs! Unfortunately it also reduced the compression from -59% to -48%, so it still needs a bit of work.

I think that the problem is that the history is unconditionally recording the last occurrence of the initial character when writing an output record whereas it should be conditional on it being no further away (back down the file) than the previous entry, as otherwise it will miss out some possible matches when it next skips back to that history entry as a start point.

--

That's the way to go. Changing that reduced the running time even further to 25secs, although the compression just went up to -50%, so still some fine tuning needed.

   ==============================

The "historical" version got so much faster because it was only keeping history for matches at least 128bytes back, but because a history match took precedence it was also less efficient as it skipped over possible nearer matches. So now I do a 256byte scan backwards every 256bytes, recording the nearest occurrence of each character in the scanned segment, so I build up a 512byte history table (a 2-byte address for each of the 256 possible characters) in stages up to a maximum of 2kb back, this being the size of the window. Using an indexed lookup from the table for an initial match check rather than sequential searching gave this 20% time saving.

--

Got the SCREEN$ compression down to 15secs @ -56% just by using a much smaller window (256bytes rather than 2kb); but this wasn't good for text, which needs the larger window size for better results.

--

I've now uploaded the latest version of [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/wip-lz77.zip]WIP-LZ77[/url]. I've added window size to the list of enterable parameters. I seem to have lost some time in the meantime, as it's now running at 18secs @ -52%; I must have undone something somewhere while tinkering.

   ==============================

At present I've been reorganising the encoding to see if I can improve the compression significantly. I reduced the match length prefix to 2 bits and put all the prefixes separate from the encoded data to avoid having to deal with the constantly changing byte alignments that would otherwise cause. Although that saved six bits per entry on the 0/1 length matches it wasted 2 bits on all the others, so I didn't save much.

I also used the spare bit on the fourth prefix (there are only three entry types: 00,01,10; so 11 is spare) to hold a fifth bit for the match length, so I could increase it from 15 to 31 (using %10 for 2-15 and %11 for 16-31, the other four bits being held in the encoded data).

The problem I'm having with LZ is that the entries for 0/1 length matches always waste space. Even if it's only two bits per entry, that's all got to be made up by savings on the longer entries before any actual compression takes effect.

--

Fixed a bug in the preview scanner (formerly the history scanner, but it now scans 256 bytes ahead of the Coding Position, hence the name change) whereby it wasn't keeping ahead of the window, so compression ratios are now around -62%/-41% for pict/text respectively.

   ==============================

After another week of tinkering I came up with a way to avoid wasting any space with 0/1/2 match entries in text-only files, so they all give 0% compression with an average for the whole file of -38% (-59% for pict) with respective times of 24secs/37secs (6912 bytes). This is slightly worse than an earlier version, which was giving -41%/-62% compression, although that's probably due to my having removed any significant repetitions in the text of the test files, which would reduce the incidence of long matches.

   ==============================

I've uploaded the current development version of [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/wip-lz77.zip]WIP-LZ77[/url] for reference. Compression ratios are -45%...-75% for text and -30%...-60% for graphics. I had to add some features to get the extra compression (doubling the window size from 2k-4k for text, including a stepped comparative search, a separate "bit index" for distinguishing entry lengths, conditional discarding of length indicators, different encoding rules for text & graphics) which more than doubled the running time, unfortunately, so it takes a minute or so to pack a 7kb file; unpacking is just as quick as before, a fraction of a second. I'll have a look at speeding it up again later on; just now I was more interested in improving the compression.

By "stepped comparative search" I mean that for each matching iteration it  compares the match result starting at the next character and uses the longer of the two results; eg. encoding the right-hand segment below ('o'=offset):
CBAXBAABBBBBB.....CBAABBBBBBX
would normally encode: 3oA 6oX; whereas stepped encodes: C 9oX
It typically saves a couple of percent over 7kb, but at the expense of doubling the search time. Packing larger files gives better results.

The demo version allows files up to 10kb, but that's including both pack & unpack routines, plus the original, packed & unpacked versions of the file altogether in memory at the same time. In practice they would be kept separate, so files several kb larger than that could be handled. In due course I'll do a modified, minimalist version which allows selective unpacking, so that it can be given a record key as a parameter and only unpacks up to that record, discarding the data it unpacks to get to it.


**********************************************************************


** Lempel-Ziv compression routine (final)
   ==============================

I ran that sample data in post #11 through LZdemoA (which is three versions back from the one currently available). I could only use a 256-byte buffer as the file is only 410 bytes; compression was 51%. Making the file four times the size and using a 768-byte buffer compression was 73% and it took 3 seconds.

   ==============================

I'm doing a simpler version which doesn't need that extra 6900 bytes work area set aside, with a demo as before which allows experimenting with different files & window sizes (when I said "buffer" before I meant "window") but discarding the statistical calculations (apart from in/out/diff/%); plus separate pack/unpack routines which can be run independently by just passing a start address & length.

   ==============================

This new version is called [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzdemo-0.zip]LZdemo-0[/url] as I basically re-wrote it; it's half the size, twice as fast, but the compression ratio's not so good as it only allows a 256-byte window (it does 51% on that sample file mentioned above, although it got between 50%-90% on the several SCREEN$ which I tried).

I've tried it with various different SCREEN$ & text files (as it's easy to check if they've decoded OK) and they all unpacked correctly. The program's a lot easier to follow now and there's loads of comments in it.

In the demo it does the pack & unpack together; the two binary options mean:
Text : 1=text, 0=data
Print: 1=yes , 0=no
Text=0 + Print=1 assumes that the file is a SCREEN$ and dumps it to the display file while unpacking. Press ENTER whenever the border changes colour. Use the emulator's "load binary" option to load a test file when the border's red (or before) at address 34000. The demo program is 619 bytes + 60 + maximum match length (currently 63).

   ==============================

Bug fix! After the DEC BC at line 397 it needs this (I've updated the ZIP).
[code]        or   a
        jr   z,ENDRUN[/code]
If the number of packed segments was an exact multiple of 4 then the unpack would fall over at the end, as it would read a trailing empty flag byte after the last segment and copy 256 bytes of garbage at the end.

--

The BASIC program which runs the demo has an extra bit in the Z80 snapshot which isn't in the BAS listing file. Lines 100-800, which conveniently fit on one screen, have the unpack routine in BASIC. GO TO 100 after packing a text file will unpack it back onto the screen - rather slowly - but those few lines of BASIC does the same as 100-odd lines of assembler, so it should be easier to follow the logic.

Each four packed entries are preceded by a byte specifying their lengths - 1, 2 or 3 bytes in 4*2 bits. 1 & 2-byte entries just hold the plain bytes; 3-byte entries hold a length & reverse offset indicating from where to retrieve the next piece of the file.

   ==============================

Just out of curiosity I tried running that sample file above through LZdemo twice, which 2nd generation gave a 29% reduction on the 1st generation packed version. Combined with the first reduction of 51% that gives a net reduction of 66% without any coding changes. (Doing it a third time made the file bigger.) Of course, what that's showing is that the routine could be made substantially more efficient, to get that same compression in one pass. Now how to do that without making it too complicated and slow?

   ==============================

I've updated [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzdemo-0.zip]LZdemo-0[/url] again. I increased the speed & efficiency by a few % by simplifying the encoding so that I could use single bits as length markers, so I can now record eight entries in a byte instead of four.
[code]
;ENCODING
; Coding flag byte specifies length of next 8 entries.
; Coding entries may be:
; 0 matches: 1 byte  : cccccccc           : cchar
; 1 match:   1 byte  : mmmmmmmm           : mchar
;2+ matches: 2 bytes : llllllll oooooooo  : length+offset
[/code]
So you get a flag byte with eight length indicator bits followed by eight one- or two-byte entries with the packed data.

The demo code & workspace takes 736 bytes; the actual program is much the same size as before - about 600 bytes, but I've now assigned space for the workspace in the listing rather than appropriating it ad hoc, so the total requirement is made clear. I'll be able to get that under 700 bytes in due course, and the independent pack/unpack routines will be smaller still as there's some bits in the demo which they don't need at all. A SCREEN$ takes about 15 seconds to pack, and the blink of an eye to unpack.

   ==============================

I've updated [url=http://www.users.globalnet.co.uk/~jg27paw4/pourri/lzdemo-0.zip]LZdemo-0[/url] again; it now includes the independent pack/unpack routines, which total 567 + 131 = 698 bytes. There's a text file which explains everything.I'll come back to it in a few days to see if I can make the pack routine any smaller or more efficient.


**********************************************************************


** Lempel-Ziv compression concepts
   ===============================

The LZdpacku.TXT file explains all the options for each program. The input & output can be put wherever they will fit, as can the programs if reassembled to a new ORG. The demo has a fixed load point, but that was just for convenience to save having to type it in every time while testing; it can be put somewhere else.

Lempel-Ziv compression works by searching through what it's processed so far to find the longest match from where it's at now (the Coding Position) through what it has yet to process (the Lookahead). When it no longer finds a match it encodes a pointer & length in the output and sets the Coding Position forward to the end of the Lookahead and repeats. The Window is the length of the output back from the Coding Position which will be searched for a match. The bigger the Window the more likely it is that a match will be found and the longer that match is likely to be, making the compression more efficient; but the bigger the window the longer it will take to search through it and the slower the compression will be.

The optimum window size depends on the type of data being compressed and how quick you want it to be. The demo lets you experiment with different settings.


**********************************************************************
