
                                           Compress64K

Hermit's simple RLE, pattern-matching/dictionary based and arithmetic-coding compressor and decompressor
(See ChangeLog farther below...)


I created this tool to include compressed versions of SID-Wizard/FlexSID/etc. native C64 codes in my
PC-tools written in C, and the tool aim for easy decompression from C source-code.

Use 'compress64k' and 'decompress64k' from commandline or from Makefile/build-scripts.
In v1.1 in-place/self-extraction (SFX) mode is introduced, use 'compress64kSFX' and 'decompress64kSFX' accordingly.
If your OS or filesystem doesn't support symlinks, simply rename the executables to 'compress64kSFX' and
'decompress64kSFX' and they'll behave as SFX-compressor/decompressor that way, with the app detecting its own name.
(The shorter 'cmp64'/'cmp64sfx' and 'dec64'/'dec64sfx' symlinks/filenames can also be used for compression/decompression.)
The maximum end-address of SFX decompressed data is $FFFF, as a last 1 byte is kept for compressed data end-signal.
(Input-data with bigger size will have the last byte meant for address $FFFF shaved off.)
(An RLE-SFX might have some more limit on the size of the input-file because short RLE-sequences might be bigger sometimes than their sources.)

With v1.2 there's also a 'mem' format, which is essentially the SFX deprived of its starter-code
but the C64-decompression target-baseaddress is prepended in place of it to know where it prefers to be decompressed to.
Invoking this mode is done similarly, execute the 'compress64kMEM' or 'cmp64mem' executable-names/symlinks.

In v1.3 the RLE-SFX (and RLE-MEM) mode was added (based on Oswald's request at CSDb): use 'compress64kRLESFX' or 'cmp64rlesfx'
and 'decompress64kRLESFX' or 'dec64rlesfx' symlinks or decompress64k executable renamed to these names.
(And now '.exe' variants of these names are also checked for based on Ian Coog's latest addition.)
It uses only the fastest RLE method to compress and decompress and is useful for even faster
compress-transfer-decompress cycles for big C64 program files during a development.
(Typical decompression time is almost twice as fast as with pattern matching method, around 1..2 seconds max.)

Version 1.4 is all about making the commandline interface a bit user-friendlier on different systems.
All the compression/decompression modes can now be activated by '-SFX', '-MEM', '-RLESFX' and '-RLEMEM' arguments,
not just through symlinks or renamed main executables.
For compression, the SFX and RLESFX execution-startaddress can also be specified (forced) by '-exec <XXXX>' argument.
(The execution address can be given as decimal number, or if 'h' prefix is prepended, as a hexadecimal number.)

Both executables use the 'decompressor.c' and/or 'compressor.c' source-files which can also be
standalone-included (with compression.h) in your application to decompress data compressed with 'compress'
or to compress data from your application. It's your responsibility to allocate output-buffer (or 2 working buffers)
of enough size, there's no built-in bounds-checking. (And keep in mind, compression output can
actually be bigger than input sometimes, and decompressed output can be many times bigger
than compressed input. To be safe, compress64k.c and decompress64k.c uses 1MB buffers for example.)
However since v1.2, the convenience-functions Compression_decompressReadOnlyData() and the like make the allocations
and freeup of interum-buffers for you, and since v1.3, even for the decompression-target if it's NULL beforehand.

Building the tool from source requires C compiler and 'make' tool. 'make' makes it, 'make install' installs it.
(And to assemble selfextract.asm, 64tass v1.59.3120 was used (with '.namespace' support), other versions should mostly work too.)

The intended use is for files below/around 64kByte size, because there's no sliding lookback-window, and as the
filesize grows, by checking the whole file for matches, the compression-time gets exponentially longer.
But this allows to reuse all available patterns that are already unpacked. On the other hand, compression format
is very simple and the decompression is very fast. (And the precision of arithmetic coding 16bit probability
table is 100% adequate only for files below 65536 bytes, that is another limit-promoting factor for filesize.)

Generally the compression-ratio is close to Exomizer's and gzip's, and on par bzip2, if all the 3 methods
are enabled and used. (A 64kByte SIDwizard .prg file is compressed in 2..5 seconds even on a Raspberry Pi Zero
resulting in 28kByte, but a 175kByte  Robocop3 .d64 file took about 45 seconds on the Zero and resulted in a
90kByte compressed file. (Compressing a 400kByte html file took 85 seconds on the Zero, resulting in 72kBytes.)
On an i5 CPU all this happens in a blink of an eye...
SFX compression only uses pattern-matching with some limitations for shorter/faster C64-side self-extraction
code, so compression ratio suffers a bit, with near 64kbyte files exomizer reduces size about 3..4kbytes more.
In general, compress64k currently produces about 1.1 times bigger compressed output than exomizer.
(This might improve in the future, doing better on finding best pattern-matches, giving better compression ratio.)
But the good news: on the C64 the self-decompression with compress64k is at least twice as fast as with exomizer.
And the compression is about at least 2..3 times faster too, grinding less on fanatically reducing the size.
(Interesting fact: 'c64sfx' can reduce big 30..40kB exomizer-packed .prg files by ~1..2kB to an even smaller size...)

Compression works best as is, with carefully selected settings based on the statistics below but the code
can be fine-tuned in 'app_common.c' and 'decompressor.h' files. Most settings will affect both compression and
decompression (i.e. the compression-format) so both should be recompiled (and files repacked) upon change.
(The compression-methods can be turned off but that generally produces considerably worse compression ratio.
But they are adaptive: turned off when compressed size is bigger than original, not to increase size of small files.)
The very first byte of the compressed file is the header which tells the format/type, whether RLE/Dictionary
and Arithmetic codings were used for compression, to lead decompressor on which of the methods to use or not.


Detailed ChangeLog:
v1.4: -Commandline interface improvements: '-SFX', '-MEM', '-RLESFX', '-RLEMEM' and '-exec <XXXX>' arguments
v1.3: -Added '.exe' variant argv[0] checks everywhere according to Ian Coog's latest modification at CSDb release page
      -If readonly-data decompression target is NULL, it gets allocated automatically (API-change: now targetpointer's pointer is the last parameter)
      -Added RLE-SFX (and RLE-MEM) compression/decompression mode according to Oswald's request at CSDb (to compress, transfer and self-decompress C64 executables fast during development)
      -Fix (changes RLE compression format): Avoiding counting compressed RLE stream's first bytes at current 'CheckBase' position as a repeat
      -Added VERBOSE_BUILD, not showing warning with assembly-code size now if this is 0
      -Fixed some typos in selfextract assembly codes ('COMRESSION' to 'COMPRESSION', 'VRAMwritePr' to 'VRAMwritePtr', 'StartYset' to 'StartXset')
      -Created 'Compression_Extraction' namespace for the extractor so if used in non-SFX custom code, extractor's internal symbols won't clash
v1.2: -Added 'mem' variant of compressor and separated the C64-side decompressor code that can extract its output
      -Added new API functions for compressing/decompressing immutable/read-only data (automatic intermediate buffer)
      -Some last format changes detailed below! So recompress your files with this version to be able to decompress them.
      -Added RLE sequence compression/decompression to the pattern-matching method (long empty spaces compress better)
       (For SFX-mode it's not compressing repeated values, but repeated pattern-match prefixes.)
       -To fit new code better in $100..$1E0 range, the initial data-mover code is excluded from the copied zeropage code
      -Improved check whether the compressed input-data needs to be moved for SFX in-place decompression
      -Corrected SFX BASIC SYS-target jump-address detection (searching in yet-uncompressed data, search skipping BASIC row-number)
      (-REVERTED: Removed CLI at the end of self-extractor code as BASIC 'RUN' is not supported yet, but e.g. usermanual.prg needs it)
v1.1: -Now 'cmp64'/'cmp64sfx' and 'dec64'/'dec64sfx' short filenames can be used for C64 related SFX-compression/decompression
      -Some format changes detailed below! So recompress your files with this version to be able to decompress them.
      -Exchanged prefix $0F & $00: $00 is now literal with length in next bytes, $01..$0F is literal with length 1..15
      -Exchanged prefix $1E and $1F to $10 and $11  ($10 is now long patternmatch with 0 distance, $11 with nonzero)
      -Made compression much faster by skipping loop-based patternmatch comparison if 1st byte doesn't match
       and using backwards pattern-match search-loop with early exit on SFX-mode maximum sequence/match-length ('RLE').
      -Added SFX (in-place self-extraction) support (and for that, created a base-infrastructure of compressio-modes)
       (It's not worth using all methods for SFX, pattern-match is enough for roundabout the same compression ratio.)
       (To make C64-side self-extraction code smaller, added 'END' prefix, and some length/distance-limits are reduced.)
       (Maximum SFX sequence/patternmatch-length is reduced to a single-byte range and handled as such, not var.length.)
      -Improved non-SFX matchlength3+distance ($C0..$FF) case's distance compression ratio by having distance 63 as base.
      -Improved matchlength3 distance range: not worth storing as 2byte variable-length number, so using bit7, doubling range
       -Improved matchlength4 distance range too: SFX-code got simplified and length4 distance range bacame doubled 0..8192
        These range-enhancements produce generally smaller outputs even though these match-lookbacks are less than 64k range
       -Also improved matchlength5..18 to matchlength5..19 by moving the big matchlength plus big distance case's value
       (It's also easier to detect this way with a single 'BNE'/'BEQ' in the C64-side SFX-code.)
      -Adding 5 to big (above 19) matchlength and distance case for simpler C64 code (enhances the length0..247 length to 5..252)
      -REVERTED: Modified variable-length number format: 'nextbyte' flag is in LSB of byte, so C64 SFX-code is shorter (no masking needed)
      -Made octet and octet-counter surely being initialized for every decompression (initialization not just on EOF)
      -Added in-memory self-verification of compressed data with debugging possibilities to find out any compression-problems


2026 Hermit Software Hungary,  Use the code in any way you like, but I'd like to remain mentioned in verbatim copies.



Some introduction to, and some info about arithmetic coding:

The best article I found back in 2022 when I first played with arithmetic coding for FlexSID statistics,
is a 2014 document written by Mark Nelson. I based the mehtodology on that but created this completely rewritten
variant in C with many compile-time customization possibilities.

The essence of arithmetic coding is 'ranges'. You have a big range/scale of numbers and on this whole range you
assing bands/regions for the different values to compress. The bigger the frequency of occurrence of a given
value the bigger band/range it gets on the scale. When we advance to the next byte to encode we 'zoom' into
the band already selected by the previous byte, and from that point we trait it as the whole scale to place the
current byte into. Until the input stream of bytes ends we successively do this step until we get a very big
number whose exact value is determined by the last byte. The scheme is similar to the real life example of an
address of a person. We have to give the country, the city, the street and the house and the name of the
person in that house. If we imagine these finer-and-finer coordinates on a scale each address (and the person
pointed by it) can be analogous to a number on a scale. (The example is not perfect because the same number
can appear more than once in an input data to be compressed. Wikipedia has better explicit examples of the theory.)
 The total scale sums up to '1.0' in float but in reality that's very small of a resolution only capable of
storing several bytes. We use scaled 'fixed point' integer calculations on arbitrarily long numbers.
This is made by shifting out MSB of the current value of the bitstream and loading new bits into the LSB
when necessary. A picture is worth more than 1000 words, so I made some verbose debugging in the source that
can be enabled by enum value 'COMPRESSION_SHOW' being set to '1' in compression.h.
The state-display/logs of the arithmetic-coding-example binary file during compression and decompression
can be seen below.
 During encoding you can see that we read in an octet (byte) from the input-datastream, and we assign a new
smaller range to it based on its 'low' and 'high' boundary-values from the calculated value-probabiliy-based
'valueband'-table. These 'high' and 'low' values are getting scaled (shifted left) if they are completely above or
below the middle of the full range (value of the calculation range's MSB, $80000000 in case of 32bit calculation.
(There's a workaround too for near-convergence case when the range is in the middle of the full range.)
The entropy-compression is based on the mechanism that values smaller on the whole scale, which appear less
frequently, take more shifts until the next input is read and therefore take more bits in the compressed output
bitstream. But the frequent input-values with bigger ranges take less shifts and less bits.
 The encoding is very similar in many of the code to the encoder, it's main difference is that we close the
current input-value read from the bitstream more closely and scale it up to the full range, find its
high and low values and take actions based on them. (Essentially this whole decoding process is the reverse of
the compression process where the value is scaled down instead.)

This was an explanation in a nutshell but checking the source code and these diagrams below might lead to
better understanding of the concept and its real-world implementation (the header increases the size of this
small example file so the adaptive automatic on/off nature of the arithmetic coding was turned off temporarily
by setting COMPRESSION_ADAPTIVE_ARITHMETIC_CODING to 0 in compression.h to generate the diagrams):


./compress64k  testfiles/test_for_arithmetic_coding.bin
File-size before compressing "testfiles/test_for_arithmetic_coding.bin": 8 bytes  (Entropy: 1.75 bits/byte)
10:0000..[20]  20:1C71..[30]  30:8E38..[64]  64:C71C..[100]  100:E38E..[101]  101:FFFF..[00]
000000 -------------------------------------------------########------- 64(C71C..E38D): 0000..C71B..E38D..FFFF
000000 |...............|...............|..++++++++++++++=-------.......   (8E36..C71A): 1:0001
000000 |......++++++++++++++++++++++++++++=--------------..............   (1C6C..8E34): 1:0003
000001 |......---#############-------------............|............... 20(1C71..8E37): 1C6C..2910..5BA2..8E34
000001 |.........----------===+++++++++++++++++++++++..|...............   (5221..B744): 0:0006
000001 |........+++++++++++==========================++++++++++++++....   (2443..EE88) PendingBitCount:1
000002 |........----------------------------############-----------.... 30(8E38..C71B): 2443..94A2..C195..EE88
000002 |.........+++++++++++++++++++++++....------------...............   (2944..832A): 1:000D 0:001A
000003 |.........--###########----------...............|............... 20(1C71..8E37): 2944..3340..5B35..832A
000003 |...........-----------..+++++++++++++++++++++..|...............   (6681..B66A): 0:0034
000003 |...............|..++++++=====================++++++++++++++....   (4D03..ECD5) PendingBitCount:1
000004 |...............|..----###################------------------.... 20(1C71..8E37): 4D03..5EC4..A5CC..ECD5
000004 |..............++++++++===================+++++++++.............   (3D89..CB98) PendingBitCount:2
000005 |..............--------------------#########-------............. 30(8E38..C71B): 3D89..8C74..AC06..CB98
000005 |.....+++++++++++++++++.........|..---------....|...............   (18E9..580C): 1:0069 $D2 0:00D2 0:01A4
000005 |.....------===========++++++++++++++++++++++...|...............   (31D3..B019): 0:0348
000006 |...........---###############---------------...|............... 20(1C71..8E37): 31D3..3FDA..77F9..B019
000006 |..............---------------.+++++++++++++++++++++++++++++....   (7FB4..EFF3): 0:0690
000007 |...............|..............#####------------------------.... 10(0000..1C70): 7FB4..7FB4..8C2D..EFF3
000007 |...............|..............=====+++.........|...............   (7F69..985A) PendingBitCount:1
000007 |...............|..............========++++++...|...............   (7ED3..B0B5) PendingBitCount:2
000007 |...............|..............==============++++++++++++.......   (7DA7..E16A) PendingBitCount:3
000008 |...............|..............----------------------####....... 100(E38E..FFFE): 7DA7..D653..E169..E16A
000008 |...............|...............|..........++++++....----.......   (ACA7..C2D2): 1:0D21 0:1A42 0:3484 0:6908
000008 |...............|.....++++++++++++.........------...............   (594F..85A4): $11 1:D211
000008 |...........++++++++++============+.............|...............   (329F..8B49) PendingBitCount:1
 0:A422 1:4845 1:908B
Last Output Octet: $60
Compressed file "testfiles/test_for_arithmetic_coding.cmp" size: 210 bytes (2625%)  (Entropy: 0.64 bits/byte)
./decompress64k  testfiles/test_for_arithmetic_coding.cmp
File-size before decompressing "testfiles/test_for_arithmetic_coding.cmp": 210 bytes  (Entropy: 0.64 bits/byte)
10:0000..[20]  20:1C71..[30]  30:8E38..[64]  64:C71C..[100]  100:E38E..[101]  101:FFFF..[00]
Reading first InputValue bits
Octet:D2 Bit:1   InputValue:$0001
Bit:1   InputValue:$0003
Bit:0   InputValue:$0006
Bit:1   InputValue:$000D
Bit:0   InputValue:$001A
Bit:0   InputValue:$0034
Bit:1   InputValue:$0069
Bit:0   InputValue:$00D2
Octet:11 Bit:0   InputValue:$01A4
Bit:0   InputValue:$0348
Bit:0   InputValue:$0690
Bit:1   InputValue:$0D21
Bit:0   InputValue:$1A42
Bit:0   InputValue:$3484
Bit:0   InputValue:$6908
Bit:1   InputValue:$D211
Octet:60 Bit:0   InputValue:$1A422
Bit:1   InputValue:$34845
Bit:1   InputValue:$6908B
Bit:0   InputValue:$D2116
Bit:0   InputValue:$1A422C
Bit:0   InputValue:$348458
Bit:0   InputValue:$6908B0
Bit:0   InputValue:$D21160
EOF   InputValue:$1A422C1
EOF   InputValue:$3484583
EOF   InputValue:$6908B07
EOF   InputValue:$D21160F
EOF   InputValue:$1A422C1F
EOF   InputValue:$3484583F
EOF   InputValue:$6908B07F
EOF   InputValue:$D21160FF
000001 +++++++++++++++++++++++++++++++++++++++++++++++++###@####+++++++ D212:$64 C71C..E38D 0000..C71B..E38D..FFFF
000001 |...............|...............|..++++++++++++++=-------.......   8E36..C71A In: EOF -> A422C1FF
000001 |......++++++++++++++++++++++++++++=--------------..............   1C6C..8E34 In: EOF -> 484583FF
000002 |......+++########?####+@+++++++++++............|............... 62A7:$20 1C71..8E37 1C6C..2910..5BA2..8E34
000002 |.........----------===+++++++++++++++++++++++..|...............   5221..B744 In: EOF -> 908B07FF
000002 |........+++++++++++==========================++++++++++++++....   2443..EE88 In: EOF -> A1160FFF
000003 |........++++++++++++++++++++++++++++##@?########+++++++++++.... 9DFA:$30 8E38..C71B 2443..94A2..C195..EE88
000003 |.........+++++++++++++++++++++++....------------...............   2944..832A In: EOF -> 422C1FFF
000004 |.........++####?@#####++++++++++...............|............... 46EC:$20 1C71..8E37 2944..3340..5B35..832A
000004 |...........-----------..+++++++++++++++++++++..|...............   6681..B66A In: EOF -> 84583FFF
000004 |...............|..++++++=====================++++++++++++++....   4D03..ECD5 In: EOF -> 88B07FFF
000005 |...............|..++++@##########?#######++++++++++++++++++.... 5F97:$20 1C71..8E37 4D03..5EC4..A5CC..ECD5
000005 |..............++++++++===================+++++++++.............   3D89..CB98 In: EOF -> 9160FFFF
000006 |..............++++++++++++++++++++#?@######+++++++............. 9717:$30 8E38..C71B 3D89..8C74..AC06..CB98
000006 |.....+++++++++++++++++.........|..---------....|...............   18E9..580C In: EOF -> 22C1FFFF
000006 |.....------===========++++++++++++++++++++++...|...............   31D3..B019 In: EOF -> 4583FFFF
000007 |........@..+++##?############+++++++++++++++...|............... 27EB:$20 1C71..8E37 31D3..3FDA..77F9..B019
000007 |..............---------------.+++++++++++++++++++++++++++++....   7FB4..EFF3 In: EOF -> 8B07FFFF
000008 |.....@.........|..............###?#++++++++++++++++++++++++.... 19D4:$10 0000..1C70 7FB4..7FB4..8C2D..EFF3
000008 |...............|..............=====+++.........|...............   7F69..985A In: EOF -> 960FFFFF
000008 |...............|..............========++++++...|...............   7ED3..B0B5 In: EOF -> AC1FFFFF
000008 |...............|..............==============++++++++++++.......   7DA7..E16A In: EOF -> D83FFFFF
Decompressed file "testfiles/test_for_arithmetic_coding.dec" size: 8 bytes (3%)  (Entropy: 1.75 bits/byte)
diff  testfiles/test_for_arithmetic_coding.bin  testfiles/test_for_arithmetic_coding.dec



The statistics and brainstorming regarding my pattern-matching method:


Pattern-matching and literal-sequence prefixing format: a lot depends on the prefix's 1st byte (how much really short sequences are worth compressing), fitting as much info to it as possible
1st byte info:  Payload is Literal or Pattern?  Short or long payload/sequence: Numberlength of Length/Offset (Next byte coming?)
 1st byte payload: first bits of Literal/Pattern Sequence-Length,  maybe first bits of Offset (if length fits in very few bytes)
 Consider the result of statistics:
  -Most matchlengths (sequences) (>80..90%) are less than 4..9 bytes (more so for patterns). (The shorter 2..4 byte patterns are much more frequent(~70%), more than 100 byte long patterns are very rare (<1%).)
   Match-length Square-law distribution statistics: 2bytes:25..54%, 3bytes:18..28%, 4bytes:10..15%, 5bytes:5%, 6bytes:3%, 7bytes:2%, 8bytes:1.5%
   Match-length can't be 0, and even 1 is unwelcome (would give prefix overhead), so value can start from 2 (~40% of cases) to save bits/valueranges.
  -Most offsets (>90%) are bigger than 7 (and 60% are smaller than 256), but literal-sequence has no offset. //  -There are likely to be more patterns than literal seqeunces (60..66% vs 34..40%) as compression is getting better
   Luckily offset to beginning of pattern-source are never smaller than MatchLength, so it's enough to give MatchLength-BeginningOffset as offset (the end of the pattern-source)
   50..60% of distances (endoffsets) are in the range 0..127 or 8..255, 75% in 0..1023, 38% in 0..64, 25% in 0..31, 15% in 0..15, only 8% in 0..7
  -Small Distance+Length combination probabilities: offset<32 & length<9: 21..26%, offset<64 & length<5: 22..32%
 Lowest-bits: sequence/patetrn-length: huffman/arithmetic coding with prefixing/postfixing of field-length
  Huffman-coding length?: postfix: 1bit(value0/2: length=2..3): X0  2bits(value1/3/5/7: length=4..7): XX1  (alternative:  prefix: 1bit(value$0x/$4x: length=1..2): 0Xxxxxxx  2bits(value$8x/$Ax/$Cx/$Ex: length=3..6): 1XXxxxxx)
 Arithmetic-coding byte1?: value0..7:length2..9 literal, value8..15:length10..xx literal (next byte coming)
                           value16..23:length2..9 pattern with offset -1, 23..31:-||- with offset -2, 32..39:-||- with offset -3, etc.
  Anticipated value-ranges for 1st prefix-byte:
   -3.1%: Value0..6: 2..8 bytes long (80..90% of cases) Literal-sequence, Value7: Literal-sequence length9..136 info (value0..127) follows in a 2nd byte (bit7 is sign for next length137..16393 high-byte, and so on, as a variable-length number)
   -34%: Value0..6: 2..8 bytes long (90% of cases) Pattern, Value7: long pattern: prefix-byte1 other bits contain further 9..41 length-info (with bit7 as continuation-bit for length high-byte)
    -62%: If length was 2..8, 256/(range0..7)-(range0..7) -> Value0..30: Distance0..30 (~25%)
   or?: (with Huffman-prefixing technique?)
   -22%: Value0..2: 2..4 bytes long (75% of cases) Pattern, Value3: long pattern: prefix-byte1 other bits contain further 5..69 length-info (with bit7 as continuation-bit for length high-byte)
    -75%: If length was 2..4, 256/(range0..3)-(range0..3) -> Value0..62: Distance0..62 (~30%)
  OR: as the Distance is the critical part of prefix and it has Gaussian ditribution, use the middle of the curve?, with most frequent offset-values in 1st byte, and only add less critical and shorter 'length' info where it fits
   Top of Distance-curve: <8:7.7..10%, 8..15:6.8..8% + 16..31:10% + 32..63:13% + 64..127:12% + 128..255:7.2% -> 8..255/0..127:51%, *0..63:41%(less relative prefix-overead), *8..127:41%, *16..255:42%, *16..127:35%, *8..63:31%, 0..31:28%, 32..127:25%
    -Selecting Distance-range for prefix byte1: *0..63:41%(less relative prefix-overead) (and 0..31:28%, 0..127:50% ?)
 Huffman/Rice/binary-weight coding length-vs-offset: Value0..127(%0..):offset0..127+length2, Value128..191(%1..):offset0..63+length3, Value192..223(%11..):offset0..32+length4, Value224..239(%111..):offset0..16+length5, Value240..247(%1111..):offset0..7+length6, Value248..255(%11111..):literal-length/nextbyte
  Value0..7(%00000..):literal-length(85%)/nextbyte, Value8..15(%00001..):offset0..7(10%)+length6(5%),  //length-probability percentage seems to follow the binary-weighted nature (coincidence?)
  Value16..31(%0001..):offset0..16(15%)+length5(8%), Value32..63(%001..):offset0..32(25%)+length4(15%),
  Value64..127(%01..):offset0..63(40%)+length3(28%), Value128..255(%1..):offset0..127(50%)+length2(25%)  //good bitfield-fitting, but tendency is opposite of theoretical offset-length correlation! (shorter match might be found closer), but on the other hand, less frequent matchlengths punish us less times and doesn't feel overhead that much
 Arithmetic-coding length-vs-offset?: incorporate probabilistic distribution of lengths (& offsets?) into value-ranges more fine-tunedly, and consider the possible correlation (offset median growing with length?) and consider penalties of prefix-overhead
  length2-range:256*25%=64, length3-range:72, length4-range:38, length5-range:20, length6-range:14, length7-range:9, length8-range:7
  hand-correction to easy-to-handle powers of 2 (Huffmanizing): 2:64, 3:64, 4:32, 5:16, 6:16, 7:8, 8:8
  hand-correction for theoretical correlation (bigger length bigger offset): 2:64, 3:64, 4:40, 5:24, 6:16, 7:8, 8:8
   and for notfitting combination low-bits (for high-bits in nextbyte): offset-lowbits:32
  value-ranges: value0..7(%00000xxx): value0..6: literal-length 2..8, value7: next byte with bigger literal length (and bi7 for high-byte if needed),
   value8..15(%00001xxx):length8+Distance0..7, value16..31(%0001..):length7+offset0..15,
   value32..63(%001..):length6+offset0..31, value64..96(%010..):length5+offset0..31, value96..127(%011..):length4+offset0..31,
   value128..191(%10..):length3+offset0..63, value192..255(%11..):length2+offset0..63
 Rethinking the whole concept:
 -Should concentrate better on efficiency of next bytes with high-databits, it might worth sacrificing 1 bit for 'next byte coming' instead of losing low-databits of offset-value
  -Length2: only 1byte prefix is worth considering, so it doesn't need to have 'next byte' bit
 -Length5..8 with small offsets are rare (and long) enough (<3%) not to consider them as candidates for offset+length in a single byte, but as much as possible lengths above 6 should be stored in the 1st byte
 FINAL value-ranges: length2(25%)*64offsets(41%)=10%, length3(28%)*64offsets(41%)=11%, 4(15%)*32(29%)=4.3% -> Sum: 25% lucky 1byte-prefix cases expected   ( 5(8%)*32(29%)=2.3%, 6(5%)*16(18%)=1% )
  length3 with 64 offset-lowbits with nextbyte(offset-highbits) awaited, literal-length2..16/nextbyte, length4..18 awaiting offset in nextbyte or value15 for bigger length first, then offset
  Positioned ranges, Values:
   $00     : literal sequence, next variable-length number is coming with bigger length-values 16..143..whatever (0..247 in case of SFX-mode)
   $01..$0F: literal-sequence of length 1..15,
   $10     : following byte is variable-length number of big pattern-matchlength (SFX-mode:single-byte 0..247), Distance is implied 0 (prefix 1byte less in this special case, when e.g. pattern-match previous sequence is without any gaps, like with long repeats of non-RLE sources)
   $11..$1F: pattern-matchlength 5..19, followed by variable-length number of Distance-value
   $20..$3F: pattern-matchlength 4 with distance low-bits (0..31) in byte1, followed by distance high-bits in next byte (appears more often (~8%) than single-byte prefix in 4.3% of cases)
   $40     : following bytes are variable-length number of big pattern-matchlength (SFX-mode:single-byte 0..247), followed by variable-length Distance value
   $41..$7E: pattern-matchlength 3 with Distance-value 0..62 (a single-byte prefix, expected in 11% of cases)
   $7F     : RLE-sequence with length (repeat-count) in 2nd byte (& 3rd byte), followed by repeated byte-value in 4th byte
             (For SFX it's the repeat-count of the whole patternmatch-prefix following it, in case it would be repeated)
   $80     : 'END of data' prefix for SFX-mode (C64 self-extraction format)
   $81..$BF: pattern-matchlength 2 with Distance-value 0..62 (a single-byte prefix, expected in 10% of cases)
   $C0..$FF: pattern-matchlength 3 with Distance-value lowbits (0..63) followed by Distance-value high-bits in a byte (not var-length number, as it's not worth' compressing)
 1st test results (output:was 24kbyte with simple variable length offset+length, now 21kbyte, 4148 pattern-prefixes):
  length2 matches with 1byte prefix: 900(21%) (-900 bytes), Suspected correlation seems manifesting? (smaller matches are closer too with small distances)
  length3 matches with 1byte prefix: 339(8,2%) (-678 bytes), length3 matches with 2byte prefix: 859(21%) (-859 bytes),
  length4 matches with 1byte prefix: 146(3.5%) (-430 bytes), length4 matches with 2byte prefix: 121(2.9%) (-242 bytes),
  length4 matches with 3byte prefix: 401(9.7%) (-401 bytes) - too much, maybe consider changing to prefer length4 'nextbyte' compression (with about 300 bytes more total saving)
  length5 matches with 2byte prefix: 126(3%) (-504 bytes),   length5 matches with 3byte prefix: 205(5%) (-410 bytes),  length5 matches with 4byte prefix: 14(0.3%) (-14 bytes),
  length6 matches with 2byte prefix: 93(2.2%) (-372 bytes),  length6 matches with 3byte prefix: 146(3.5%) (-438 bytes), length6 matches with 4byte prefix: 7(0.15%) (-14 bytes),
  length7 matches with 2byte prefix: 62(1.5%) (-310 bytes),  length7 matches with 3byte prefix: 91(2.1%) (-364 bytes), length7 matches with 4byte prefix: 2(0.05%) (-6 bytes),
  length8 matches with 2byte prefix: 40(1%) (-240 bytes),    length8 matches with 3byte prefix: 81(2%) (-405 bytes),  length8 matches with 4byte prefix: 2(0.05%) (-8 bytes)
  Literal prefixes:2263, 1byte prefixes: 2189(96.8%) (+2189 bytes), 2byte prefixes: 72(3.2%) (+144 bytes), 3byte prefixes: 2(0.1%) (+6 bytes)
  length2 literals (1byte prefix): 1033(45.6%) (+1033 bytes), length3 literals (1byte prefix): 369(16%) (+369 bytes),
  length4 literals (1byte prefix): 257(11%) (+257 bytes), length5 literals (1byte prefix): 155(6.8%) (+155 bytes),
  length6 literals (1byte prefix): 102(4.5%) (+102 bytes), length7 literals (1byte prefix): 63(2.8%) (+63 bytes)
  Improved compression ratio a bit by enabling prefixing length1 literals (seems paradoxical but gives more pattern-matching opportunities it seems)
  Improved even further by having length4 with nextbyte (with offset high-bits): -300bytes


Stats (50kByte FlexSID-medium): PrefixCount:12512,  SmallOffsetCount:1333(10.6%), SmallLengthCount:12016(96%, 1:5279(42%)),  SmallSumCount:1862, SmallPrefixCount:1333
With MatchLength>=2: PrefixCount:7233,  SmallOffsetCount:376(5.2%), SmallLengthCount:6737(93% 2:3893(54%),3:1335,4:700,5:334,6:230,7:136,8:109),  SmallSumCount:571, SmallPrefixCount:376
Patterns only: PrefixCount:2681(60%),  SmallOffsetCount:124(4.5%), SmallLengthCount:2157(80%: 3:498(18.5%),4:750(28%),5:359(13%),6:261(10%),7:168(6.2%),8:120(4.4%)),  SmallSumCount:192, (SmallPrefixCount:124, same as SmallOfsetCount because it's a sum of length+Distance already)
 Small Lengths if allowed to substitute pattern with equal-length prefix (2 bytes at least): more pronounced small lengths, 2 is very frequent
  PrefixCount:4439(66%), SmallLengthCount:3930(89%: 2:1134(25.5%) 3:1257(28.3%),4:674(15%),5:342(7.7%),6:243(5.4%),7:154(3.4%),8:126(2.8%)
 Distance-count (Offset-Length) Gaussian distribution:  Verdict: 50..60% is in the range 0..127 or 0/8..255, 75% in 8..2048 or 0..1023, 38% in 0..64, 25% in 0..31, 15% in 0..15, only 8% in 0..7
  smaller than 2:47(1.7%), <3:89(3.3%), <4:117(4.3%) (2..3:70(2.6%), 4..7:91(3.3%)),
   <8:208(7.7%) (8..15:183(6.8%)), <9:235(8.7%), <10:254(9.5%), <11:275(10%), <12:299(11%),
   <16:391(15%) (16..31:274(10%)), <24:542(20%), <32:665(25%) (32..63:345(13%)), <48:855(32%),
   <64:1010(38%) (64..127:333(12%)), <96:1229(46%), <128:1343(50%) (128..255:220(8.2%)), <192:1463(55%), <256:1563(58%) (256..511:229(8.5%)), (512..1023:217(8%)), 1024..2048:203(7.5%), 2048..4095:149(5.5%), 4096..8191:184(6.8%), 8192..16383:98(3.6%)
   <512:1792(67%), <1024:2009(75%), <2048:2212(83%), <4096:2361(88%), <8192:2545(95%), <16384:2643(99%)
  with equal-length prefix substitution allowed (4439 prefixes): <4:251(5.6%), <8:458(10%), <16:806(18%),
   <32:1267(28.5%) (32..63:563(13%)), <64:1830(41%) (64..127:561(13%)), <128:2391(54%) <256:2712(61%) (128..255:321(7.2%)), <512:3066(69%), <1024:3370(76%)
 Distance and Length combinations that could fit into a single prefix-byte: Verdict: offset<32 & length<9:20..25%
  offset<8 & length<9:178(6.6%), offset<16 & length<9:330(12%), offset<32 & length<9:557(21%), offset<64 & length<5:586(22%)
  with equal-length prefix substitution allowed (4439 prefixes): <8&<9:429(9.6%), <16&<9:746(17%), <32&<9:1161(26%), <64&<5:1423(32%)
 Correlation between matchlength and Distance?: total or below length9: minoffset:0,averageoffset:1550,maxoffset:30676, small correlation:
                       length3:0..42..124,     length4:0..1823..16265, length5:0..2580..26824, length6:1..1919..30676, length7:1..2012..24156, length8:0..1724..24602, length9:3..2471..20756, length10:0..1673..19931, length11:3..1554..14072, , length12:0..1522..23077, length13:average1862, length14:2986, 15:1199, 16:8..866.4308(only 19 prefixes), 17:average1901, 18:552, 19:256, 20:218, 21:129, 22:833(only 8 prefixes), 23:270 ... 30:3006
  with equal-length prefix substitution allowed (4439 prefixes):  small correlation, but in theory average offset should increase with longer matches
   length2:0..36..125, length3:0..1925..16309, length4:0..2370..26240, length5:0..2554..26824, length6:1..1957..30676, length7:1..1750..20356, length8:0..2084..24602
Literal-sequences only: PrefixCount:1828(40%),  SmallLengthCount:1397 (70%) (length2:632(35%), length3:203(11%), length4:177(9.6%), length5:152(8.3%), length6:109(6%), length7:67(3.6%), length8:57(3.1%), length9:60, length10:40)
 with equal-length prefix substitution allowed: 2269 (34%) prefixes with more pronounced 2080 (91%) small-length literal sequences in this case (2byte:1094(48%), 3byte:378(17%), 4byte:257(11%), 5byte:140(6.1%), 6byte:101(4.4%), 7byte:57(2.5%), 8byte:53(2.3%)!

Conclusions: Length is usually small, offset is mostly larger, small sum of them appears more times than both being small.
             Pattern-Prefix format would benefit from using high-nybble of 'length' as offset-bits when length is small
             Literal-Prefix format wvould benefit from putting small length into offset0-byte (having literal sign and offset in a single byte)


Matches and Pattern-matchlength distribution example (subjuct: testfile, RLE-compressed internally, then pattern-match tests)
match-position: 0001,0024, length: 3, tbindex:0, data: 00 00 20
match-position: 0002,002A, length: 3, tbindex:0, data: 00 20 20
match-position: 0002,002E, length: 4, tbindex:0, data: 00 20 20 20
match-position: 0003,0017, length: 3, tbindex:0, data: 20 20 20
match-position: 0003,002F, length: 3, tbindex:0, data: 20 20 20
match-position: 000E,001D, length: 4, tbindex:0, data: 11 CC 22 24
match-position: 000F,001E, length: 3, tbindex:0, data: CC 22 24
match-position: 0017,002F, length: 3, tbindex:0, data: 20 20 20
match-position: 0023,0026, length: 3, tbindex:0, data: 20 00 00
match-position: 0027,0028, length: 3, tbindex:0, data: 00 00 00
match-position: 002A,002E, length: 3, tbindex:0, data: 00 20 20
match-position: 002C,0031, length: 3, tbindex:0, data: 20 02 00
//matchlength-distribution:
000: 1077
001: 107
002: 030
003: 010
004: 002
005: 000
...


Matches and Pattern-matchlength distribution example (subjuct: random.bin, RLE-compressed internally, then pattern-match tests)
match-position: 0019,01C2, length: 2, tbindex:0, data: 6C D6
match-position: 007F,009D, length: 2, tbindex:0, data: 83 1C
match-position: 00F7,0264, length: 2, tbindex:0, data: C0 B6
match-position: 010A,02F3, length: 2, tbindex:0, data: A3 F7
match-position: 0118,0197, length: 2, tbindex:0, data: C5 DA
match-position: 013E,03CD, length: 2, tbindex:0, data: 5D 40
match-position: 01B1,01CA, length: 2, tbindex:0, data: 59 3F
match-position: 0223,022A, length: 2, tbindex:0, data: 8B E3
match-position: 024A,02E4, length: 2, tbindex:0, data: 55 81
match-position: 0291,03FB, length: 2, tbindex:0, data: AC E6
match-position: 02E3,038F, length: 2, tbindex:0, data: B6 55
000: 518770
001: 1977
002: 011
003: 000
...


Pattern-matchlength distribution example (subjuct: uncompressed 50kbyte FlexSID-medium RLE-compressed internally to 34kbyte, then pattern-match tests, note strong decrease step at 011)
000: 554444464
001: 6913145
002: 540983
003: 140031 - the 3byte patterns are the least that are worth compressing (with lookup offset+length overhead)
004: 56013
005: 25415
006: 18310
007: 10470
008: 6201
009: 4777
010: 4083
011: 2526
012: 2103
013: 1826
014: 1683
015: 1433
016: 1226
017: 1024
018: 897
019: 800
020: 664
021: 605
022: 544
023: 472
024: 404
025: 367
026: 342
027: 330
028: 283
029: 250
030: 244
031: 234
032: 208
033: 208
034: 196
035: 180
036: 156
037: 137
038: 133
039: 107
040: 093
041: 080
042: 074
043: 069
044: 068
045: 064
046: 054
047: 050
048: 043
049: 041
050: 037
051: 034
052: 034
053: 033
054: 033
055: 033
056: 031
057: 028
058: 025
059: 026
060: 025
061: 024
062: 024
063: 023
064: 024
065: 023
066: 024
067: 024
068: 023
069: 024
070: 023
071: 024
072: 024
073: 022
074: 023
075: 022
076: 023
077: 023
078: 022
079: 019
080: 017
081: 017
082: 017
083: 014
084: 015
085: 014
086: 014
087: 014
088: 013
089: 013
090: 012
091: 013
092: 013
093: 012
094: 013
095: 012
096: 010
097: 013
098: 012
099: 013
100: 007
101: 009
102: 010
103: 009
104: 008
105: 006
106: 007
107: 006
108: 005
109: 006
110: 005
111: 006
112: 006
113: 005
114: 006
115: 005
116: 005
117: 005
118: 004
119: 005
120: 004
121: 005
122: 005
123: 004
124: 005
125: 004
126: 005
127: 004
128: 004
129: 003
130: 001
131: 002
132: 002
133: 001
134: 002
135: 001
136: 002
137: 002
138: 001
139: 002
140: 001
141: 002
142: 002
143: 001
144: 002
145: 001
146: 002
147: 001
148: 000
149: 001


