update!
new cruncher variant LZ49, crunch better (average 10%) when used with more data
bugfix both crunchers when match/literal length equal to 270+255*n
bugfix Z80 cruncher: wrong size displayed when using more than one bank
bugfix Z80 cruncher: almost infinite loop when last key end in the last 3 bytes, or end the data
-----------
Hi!
I wrote a new compression format, freely inspired by LZ4 format (thanks to Yann Collet again)
The few modifications suits well to the Z80
The format was designed and modified to fit the decompression routine
Now it's optimised for size and speed
The decompression routine fit in 83 bytes and there is an ultra-short version (you lose some Nops)
Crunching routine is a little slow as matchkey may have an unlimited length
I will release in a few weeks max a C source code if people want to cross-crunch
Here is the format
(http://reho.st/self/7960e49dea09140879501b735524571f96b27606.png)
Token definition: contains both literal and match length information
4 high-bits: literal length 0-15
if length=15 then read one Literal length extended byte (value 0-255) and add to current literal length
if literal length extended byte=255 then read another one, etc.
4 low-bits: match length 0-15
if length=15 then read one Match length extended byte (value 0-255) and add to current match length
if match length extended byte=255 then read another one, etc.
THEN add 3 to the final match length, because it is the minimal length
Offset definition: absolute distance to match value -1
if you want to copy from previous byte, then offset value is 0
if you want to copy 5 bytes far, then offset value is 4
if you want to copy 255 bytes far, then offset value is 254
if you want to END the file, then offset value is 255
I will release soon (don't know when) a C source file with an brutforce key search, design to run in a computer with moar memory ;)
You may play with crunching/decrunching routine
The crunching routine read data to compress from central memory and put compressed data in extension C4/C5/C6/C7
---------------------
(http://reho.st/self/b7b4a3d2fb09a85c81a451e593aecdadd90b7032.png)
Changes:
1st high-bit of token is an extra offset range (set when offset>255)
Now this will be cool - a x86 cruncher (to work with sdcc etc.) and and small and fast decruncher on CPC.
Quote from: SRS on 22:27, 18 September 16
Now this will be cool - a x86 cruncher (to work with sdcc etc.) and and small and fast decruncher on CPC.
Here is the C source file, i tested it a little, should work (hope so)
I noticed a bug when literal or match length is 270+255*n with crunchers. Will fix this.
Quote from: roudoudou on 10:31, 20 September 16
I noticed a bug when literal or match length is 270+255*n with crunchers. Will fix this.
First post updated with fixed versions of Z80 & C cruncher
I also found a bug with displayed output size (Z80 cruncher) when output size uses more than one BANK. Fixed too.
Happy crunching!
This works with dev-cpp and win64:
/* LZ48 simple C source file / crappy version by roudoudou - Flower Corp. 2016 */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
int LZ48_encode_extended_length(unsigned char *odata, int length) {
int ioutput=0;
while (length>=255) {
odata[ioutput++]=0xFF;
length-=255;
}
/* if the last value is 255 we must encode 0 to end extended length */
odata[ioutput++]=length;
return ioutput;
}
int LZ48_encode_block(unsigned char *odata,unsigned char *data, int literaloffset,int literalcpt,int offset,int maxlength) {
int ioutput=1;
int token=0;
int i;
if (offset<0 || offset>255) {
fprintf(stderr,"internal offset error!");
exit(-2);
}
if (literalcpt<15) {
token=literalcpt<<4;
} else {
token=0xF0;
ioutput+=LZ48_encode_extended_length(odata+ioutput,literalcpt-15);
}
for (i=0; i<literalcpt; i++) odata[ioutput++]=data[literaloffset++];
if (maxlength<18) {
if (maxlength>2) {
token|=(maxlength-3);
} else {
/* endoffset has no length */
}
} else {
token|=0xF;
ioutput+=LZ48_encode_extended_length(odata+ioutput,maxlength-18);
}
odata[ioutput++]=offset-1;
odata[0]=token;
return ioutput;
}
unsigned char *LZ48_encode(unsigned char *data, int length, int *retlength) {
int i,startscan,current=1,token,ioutput=1,curscan;
int maxoffset,maxlength,matchlength,literal=0,literaloffset=1;
unsigned char *odata=NULL;
if (!length) return NULL;
odata=(unsigned char*) malloc(length*1.1);
if (!odata) {
fprintf(stderr,"memory full");
exit(-1);
}
/* first byte always literal */
odata[0]=data[0];
/* force short data encoding */
if (length<5) {
token=(length-1)<<4;
odata[ioutput++]=token;
for (i=1; i<length; i++) odata[ioutput++]=data[current++];
odata[ioutput++]=0xFF;
*retlength=ioutput;
return odata;
}
while (current<length) {
maxlength=0;
startscan=current-255;
if (startscan<0) startscan=0;
while (startscan<current) {
matchlength=0;
curscan=current;
for (i=startscan; curscan<length; i++) {
if (data[i]==data[curscan++]) matchlength++;
else break;
}
if (matchlength>=3 && matchlength>maxlength) {
maxoffset=startscan;
maxlength=matchlength;
}
startscan++;
}
if (maxlength) {
ioutput+=LZ48_encode_block(odata+ioutput,data,literaloffset,literal,current-maxoffset,maxlength);
current+=maxlength;
literaloffset=current;
literal=0;
} else {
literal++;
current++;
}
}
ioutput+=LZ48_encode_block(odata+ioutput,data,literaloffset,literal,0,0);
*retlength=ioutput;
return odata;
}
void LZ48_decode(unsigned char *data, unsigned char *odata) {
int HL=0,DE=0;
int literallength,matchlength,HLmatch;
odata[DE++]=data[HL++];
while (1) {
literallength=(data[HL] & 0xF0)>>4;
matchlength=(data[HL++] & 0xF);
if (literallength==15) {
while (data[HL]==255) {
literallength+=255;
HL++;
}
literallength+=data[HL++];
}
while (literallength>0) {
odata[DE++]=data[HL++];
literallength--;
}
/* matchkey */
if (matchlength==15) {
while (data[HL]==255) {
matchlength+=255;
HL++;
}
matchlength+=data[HL++];
}
matchlength+=3;
if (data[HL]==0xFF) return;
else HLmatch=DE-(data[HL++]+1);
while (matchlength) {
odata[DE++]=odata[HLmatch++];
matchlength--;
}
}
}
unsigned char * LZ48_decrunch(unsigned char *data, int *osize) {
int literallength,matchlength;
int HL=1,DE=1;
unsigned char *odata=NULL;
while (1) {
literallength=(data[HL] & 0xF0)>>4;
matchlength=(data[HL++] & 0xF);
if (literallength==15) {
while (data[HL]==255) {
literallength+=255;
HL++;
}
literallength+=data[HL++];
}
DE+=literallength;
HL+=literallength;
/* matchkey */
if (matchlength==15) {
while (data[HL]==255) {
matchlength+=255;
HL++;
}
matchlength+=data[HL++];
}
matchlength+=3;
if (data[HL]==0xFF) break;
else HL++;
DE+=matchlength;
}
*osize=DE;
odata=(unsigned char*)malloc(*osize);
if (!odata) {
fprintf(stderr,"memory full\n");
exit(-1);
}
LZ48_decode(data,odata);
return odata;
}
void Usage() {
printf("usage: lz48 <options>\n");
printf("options are:\n");
printf("-i <inputfile>\n");
printf("-o <outputfile>\n");
printf("-b hexatext output (enable if you forget outputfile)\n");
printf("-d decrunch\n");
printf("\n");
exit(0);
}
int ParseOptions(char **argv,int argc, char **inputfilename, char **outputfilename, int *hexoutput, int *crunch) {
int i=0;
if (argv[i][0]=='-') {
switch(argv[i][1]) {
case 'O':
case 'o':
if (i+1<argc) *outputfilename=argv[i+1];
i++;
break;
case 'I':
case 'i':
if (i+1<argc) *inputfilename=argv[i+1];
i++;
break;
case 'D':
case 'd':
*crunch=0;
break;
case 'B':
case 'b':
*hexoutput=1;
break;
default:
Usage();
}
} else
Usage();
return i;
}
/*
* GetParametersFromCommandLine
* retrieve parameters from command line and fill pointers to file names
* */
void GetParametersFromCommandLine(int argc, char **argv, char **inputfilename, char **outputfilename, int *hexoutput, int *crunch) {
#undef FUNC
#define FUNC "GetParametersFromCommandLine"
int i;
for (i=1; i<argc; i++)
i+=ParseOptions(&argv[i],argc-i,inputfilename,outputfilename,hexoutput,crunch);
if (!*inputfilename) Usage();
if (!*outputfilename) *hexoutput=1;
}
int main(int argc, char **argv) {
unsigned char *data=NULL,*newdata=NULL;
char *inputfilename=NULL,*outputfilename=NULL;
int hexoutput=0,isize,crunch=1;
int newsize,i,cr;
FILE *fin=NULL,*fout=stdout;
fprintf(stderr,"LZ48 cruncher / roudoudou - Flower Corp. 2016\n");
GetParametersFromCommandLine(argc,argv,&inputfilename,&outputfilename,&hexoutput,&crunch);
fin=fopen(inputfilename,"rb");
if (!fin) Usage();
fseek(fin,0,SEEK_END);
isize=ftell(fin);
fseek(fin,0,SEEK_SET);
data=(unsigned char*) malloc(isize);
if (!data) {
fprintf(stderr,"memory full\n");
exit(-1);
}
if (fread(data,1,isize,fin)!=isize) {
fprintf(stderr,"read error\n");
exit(-1);
}
fclose(fin);
switch (crunch) {
case 0:
newdata=LZ48_decrunch(data,&newsize);
break;
case 1:
newdata=LZ48_encode(data,isize,&newsize);
break;
}
printf("input: %d output: %d\n",isize,newsize);
if (hexoutput) {
for (i=cr=0; i<newsize; i++) {
if (!cr) {
printf("DEFB %02X",newdata[i]);
cr=1;
} else {
if (cr==15) {
printf(",%02X\n",newdata[i]);
cr=0;
} else {
printf(",%02X",newdata[i]);
cr++;
}
}
}
if (cr) printf("\n");
} else {
fout=fopen(outputfilename,"wb");
if (!fout) Usage;
if (fwrite(newdata,1,newsize,fout)!=newsize) {
fprintf(stderr,"write error\n");
exit(-1);
}
fclose(fout);
}
return 0;
}
bugfix Z80 cruncher: almost infinite loop when last key end in the last 3 bytes, or end the data
new release in the first post v017
first post updated
here is a variant of LZ48 -> LZ49 with 9bits offset
decrunch is a very little nops slower and there is an average 10% compression gain
two new sources: lz49crunch & lz49decrunch in Z80 assembly
C version will follow
I'm currently working on evolutions for LZ48 & LZ49 (it's alread programmed, i have to test it first!)
This is:
- constant time execution for partial decrunching (nop precise)
- maximum time execution for partial decrunching (maximum in nops)
- constant time execution for stream decrunching
- maximum time execution for stream decrunching
- constant data size for stream decrunching
- constant crunched size for stream decrunching
Have fun!
Here a version compatible with SDCC / CPCTelera :
[attach=2]
And exe Compressor / Decompressor for Windows :
[attach=3]
@roudoudou (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1714) : Can i adapt for WinCPCTelera the C decruncher version of your LZ248 (under GitHub) ?
@Arnaud (http://www.cpcwiki.eu/forum/index.php?action=profile;u=1424) it will be a pleasure!
Just did a quick test on this! it looks excellent! it compressed the 17k loading screen of my game down to 9k! Thanks for making such a great project!
Very nice! Will use it soon and report how it works :-)
Hi I compressed a file with:
- Exomizer: 16,1 KB
- CPCT......: 21 KB
- BitBuster: 21 KB
- LZ49 .....: 22,7 KB
Well, I just need some cruncher to get under 16 KB. Hmpf!
Hi GUNHED,
This is from a long time ago but once or twice I used a CPM utility called "DU" or "Crunch" (?) to compress files, don't know how efficient it was/is, like I say it was a long long time ago.
Cheers,
Peter
Quote from: GUNHED on 14:28, 09 August 18
Hi I compressed a file
Well, I just need some cruncher to get under 16 KB. Hmpf!
What kind of file?
If you want to beat a generic cruncher you must use dedicated features. Or use the best cruncher which is very slow to decrunch sadly...
Well, I just need to get this file inside 16 KB... So I tried what it probably the best four choices for the CPC. However it's different for any file (I guess). :)
It's also good to see that some CPC crunchers, still beat some PC programs ;D
I'll attach the file I did use, if there is interest...
Quote from: GUNHED on 15:00, 10 August 18
Well, I just need to get this file inside 16 KB... So I tried what it probably the best four choices for the CPC. However it's different for any file (I guess). :)
It's also good to see that some CPC crunchers, still beat some PC programs ;D
I'll attach the file I did use, if there is interest...
If you haven't checked it, look at Einar's zx7. It has the best compression on that family and it has very efficient decompressors supporting Z80.
Well, it just gets down to 20 KB. So Exomzer with 16,1 KB ist still the best, but only WinRAN can get it under 16 KB. Well, I'm afraid there is no WinRAR decompressor for the CPC.
Quote from: GUNHED on 15:37, 12 August 18
Well, it just gets down to 20 KB. So Exomzer with 16,1 KB ist still the best, but only WinRAN can get it under 16 KB. Well, I'm afraid there is no WinRAR decompressor for the CPC.
15240 bytes with Shrinkler but you should consider the very slow decrunching time
Quote from: roudoudou on 16:37, 12 August 18
15240 bytes with Shrinkler but you should consider the very slow decrunching time
Oh, thanks for the information - I will try immediately. Yes decrunching is slow, also very slow for Exomizer. LZ49 is far better (also CPCT is a well tool). :) :) :)
EDIT: Sorry for getting offtopic here, anybody got a link for Shrinkler newest version?
http://www.cpcwiki.eu/forum/programming/shrinkler-z80-decrunch-routine/
Hi folks.
I'm having a weird problem with a fairly large .bin file.
I crunch it with lz48, but when I decrunch it (either in my CPC program, or with lz48.exe itself), it doesn't reproduce the original .bin file.
It starts to become different around 9% through.
The original .bin file is 13,121 bytes.
The decrunched .bin file is 12,836 bytes.
Has anyone experienced this sort of thing?
The attached zip file contains the following:
- the .asm file that the .bin is produced from (compiled using RASM)
- the .bin file (correct version)
- the .lz file
i crunch the .bin with rasm directive incl48 and the crunched file is 295 bytes long instead of 294 in your archiveanyway the crunched files are quite different!!!so i guess your exe is wrong?
Ah, that's interesting.
I'll give it a try!
Thanks.
I had downloaded lz48.exe from this page:
https://www.octoate.de/wp/2016/12/31/lz48lz49-decompressor-for-the-amstrad-cpc/ (https://www.octoate.de/wp/2016/12/31/lz48lz49-decompressor-for-the-amstrad-cpc/)
Perhaps that executable was based on an older version of the compressor source code?
[EDIT] INCL48 worked! Thanks so much. 8)
Binary of LZ49 Windows compressor & fixed LZ48 Windows compressor.
lz48_bin.zip and lz48_c_source.zip
int LZ48_encode_extended_length(unsigned char *odata, int length)
{
int ioutput=0;
while (length>255) {
lz48_v002.zip
while (length>=255) {
Quote from: uniabis on 07:56, 02 April 19
Binary of LZ49 Windows compressor & fixed LZ48 Windows compressor.
lz48_bin.zip and lz48_c_source.zip
int LZ48_encode_extended_length(unsigned char *odata, int length)
{
int ioutput=0;
while (length>255) {
lz48_v002.zip
while (length>=255) {
Hi there.
Ah, your first post to the forums.
:)
Thanks for the new versions.
Is the greater-than check the only thing that has changed?
I realise i did not released the constant time version...
Frames with max nops for decrunching
But also...
Frames with exact configurable nop count for decrunching
I'm really interested in a version with constant data size for stream decrunching...
Because it hang at 27% ? :-\
Thank you Roudoudou for this work and for sharing! I am very interested in the LZ48/LZ49 variant you made from LZ4. I may use it in my software cause I need relatively fast compression time and very fast decompression time.
So, here is a little contribution.
First remark, you finally put offset byte at the end of the block (after match length), which is not what the diagrams of your first post show. Anyway.
Then, I propose some small optimizations to the decrunching routine (see attachment). In short:
- gain 6 nop when no literal, loose 2 otherwise (code around cp #10 when decoding token)
- optimize literal and match size calculation speed (8 bit add and simply inc b if carry was set)
- small size optimization on offset calculation (instead of src=dst-oft with 8 bit subtract, perform src=-oft+dst with one 16 bit add) (hint: neg might be avoided here)
- small size and speed optimization by moving ld c,a around
I am also looking at the crunching routine but it is too soon to share my findings. For now, I could gain >30% time when crunching my reference file (the one that has worse compression ratio).
First simple optimization is to move the ld bc,3 some lines away in LZ48_get_match_rescan...
Hello,
I am having trouble getting the cruncher/decruncher working.
I am using lz48decrunch_v006.asm posted in this thread for decrunching on CPC, assembled with RASM, translated with DisArk in order to use with SDCC.
I don't think the C glue code is the source of the issue (C source code found on this forum..).
I am using lz48.c cruncher I compiled on Linux (not sure which version I picked... command line stated it's from 2016).
Crunching / Decrunching in command line on Linux works, not on CPC.
I think I might have a version mismatch here.
Which files should I get ?
Thanks for your help !
[EDIT] : Please disregard, I finally got it working thanks to Arnaud6128 SDCC glue code. source and and target were reversed in my code....
last versions are all in this threadi can't help you more without the dataif this is not a secret, send me a mail with thoses datasregards
Hi Roudoudou,
I'm studying your LZ49 cruncher. And I dont fully understand this part, could you give me more comments about it, line 107. I think there is one useless JR, and
I dont understand why you just raise curadr when there is 1 or 2 bytes left.
Thanks.
; we are in the last 3 bytes, and maybe there is no more byte to crunch!
encode_block21
endadrcpy3:ld de,#1234
ld hl,(curadr)
encode_block21_loop
sbc hl,de
jr z,encode_block
ld hl,(curadr)
inc hl
ld (curadr),hl
jr encode_block21_loop
jr encode_block21
encode_block3
ld hl,(literal)
inc hl
inc hl
inc hl
ld (literal),hl
Quote from: elpekos on 08:33, 14 December 20
Hi Roudoudou,
I'm studying your LZ49 cruncher. And I dont fully understand this part, could you give me more comments about it, line 107. I think there is one useless JR, and
I dont understand why you just raise curadr when there is 1 or 2 bytes left.
the cruncher may not be fully optimised (i do not use anymore Z80 version to crunch since i use Rasm for this)
as far as i remember when we are in the last 3 bytes, it's useless to search for a key match, then i raise curadr AND literal in order to make a "literal block" and end with this block the crunched file
ok, if I'm not wrong, the code seems to just raise literal if 3 bytes left and just raise curadr if 2 or 1 byte(s) left.
And what about this strange 'jr encode_block21' ?
Is it just a cut and paste remnant ?
Quote from: elpekos on 08:53, 14 December 20
ok, if I'm not wrong, the code seems to just raise literal if 3 bytes left and just raise curadr if 2 or 1 byte(s) left.
And what about this strange 'jr encode_block21' ?
Is it just a cut and paste remnant ?
i hope this is only some useless dead code ;D
Hi,
I adapted your code for the Z88 OS. It works great... I compared results to the files produced by the C version. Thanks. I'll now focus on some optimisations and using a small buffer instead a large memory area.
Here is my optimized version of the LZ48 cruncher. People usually focus on decompression time only, but for the Soundtracker DMA (released last year (https://www.cpcwiki.eu/forum/applications/soundtracker-dma-v2-0-released/)) I needed also fast compression and LZ4x algorithms are great at this. With those optimizations on my reference data, compression time goes from 1.65s down to 585ms.
I focused on the match scan routine and took advantage of cpir and cpi assembly instructions. The loop itself is now faster but loop setup is longer. So, actual gain will depend on how your data look like.