A.D.A. Amiga Demoscene Archive

I have tested (the Win32 version) of Shrinkler 4.4 and found one issue with the crunched files.

I get an error 80000004 (illegal instruction?) on 68000 CPU when running crunched file from workbench. It works fine straight from floppy disk at boot-up (before workbench is loaded).

I also retested Shrinkler 4.3 with the same files and that works from workbench or from floppy disk at boot-up without any issues.

Edit:It seems that after more testing Shrinkler 4.3 seems to have the same issue. I can't seem to put my finger on what is causing it, as sometimes the files will decompress from workbench without an error and sometimes they won't.
Any ideas Blueberry?

That doesn't sound good...

Does it have a .info file or are you running it via Show All Files?

Which Kickstart and Workbench versions are you running?

Are you running any non-standard programs that might interfere? If you rename WBStartup to something else (if you are on 2.0 or newer), then start with no startup sequence and simply run LoadWB and EndCLI, does the problem still occur?

I'm using my usual A600 setup (68000 CPU, 8MB chipRAM, 0MB fastRAM, ECS chipset) in WinUAE 2.0.1:

Kickstart=37.350
workbench=37.71

No other programs running in background (unless you count workbench itself!)


When the files don't have any icons, the files decompress and run without any issues.
When the files have icons (tool icon on my 3 test files), I get the error mentioned in my previous post.


I don't understand why having an icon would cause them to crash. The icon file (.info) is completely separate, right?

When a program is run from Workbench using a tool icon, the Workbench sends a message to the program containing information about tooltypes, icons selected and such. The program must receive that message, or it might crash. See for instance this explanation.

Do your programs work if they are not crunched? You might need to test both short-running and longer-running (at least a few seconds) programs to be sure.

Ok, I found some time to do some more testing today using Shrinkler 4.4 and WinUAE 2.0.1

The original 3 test files were created in Blitz Basic by someone else. The file used in the tests below, was created using DevPac 3.18 by me:

Compression - No Icon - works
Compression - Icon - Project - fails with 'no default tool' message from Workbench.
Compression - Icon - Tool - fails

No Compression - No Icon - works /
No Compression - Icon - Project - fails with 'no default tool' message from Workbench.
No Compression - Icon - Tool - works /




I dumped the files onto an emulated floppy (ADF) along with LoadWB and Dir in the "C" drawer (I forgot about EndCLI at the time). Created a "startup-sequence" file that runs LoadWB and dumped it in the "S" drawer. I then rebooted with the disk in df0: and once WB loaded, I simply typed DIR df0: and then typed the name of the file to load. The results are as follows:

Compression - Icon (Project) works
Compression - Icon (Tool) works
Compression - No Icon - works

No Compression - Icon (Project) works
No Compression - Icon (Tool) works
No Compression - No Icon - works


Now I went back to the original 3 files that caused issues, and did the same thing:

File 1 with Icon (Tool) - works
File 2 with Icon (Tool) - works
File 3 with Icon (Tool) - works


I looked at my startup-sequence.HD and user-startup files, but can't see anything that I think might cause issues. I can list both files (or upload to my website) if you want to take a look at them.



When I say they work, they can run for as long as I let them (e.g. minutes or for an hour).

I have a minor bug report. Running with WinUAE's builtin Aros kickstart, and running as an A4000-level machine, shrinkler-compressed executables hang after decompressing somehow (I see in the winuae debugger that the program counter is pointing to garbage). I've tried with multiple different kinds of executables, and they seem to all behave the same. The same executables run fine on Aros without compression.

An easy way to test this is to use my toolchain and use runaros.bat with for example Octorubber.

I don't know if you care enough to try to fix this, or figure out why aros doesn't behave the same as all other platforms, but I wanted to at least mention it to you.

I have not looked at the AROS executable launcher code, but my guess is it leaves registers in a different state than the AmigaOS launcher. Shrinkler assumes that A3 points to the loaded segment list (4 bytes before the entry point) which is true for all Amiga kickstarts but might not be for AROS.

If A3 points to garbage, it could give the behavior you describe for mini-compressed executables (such as Octorubber) but executables crunched using the normal or overlap modes would likely crash earlier on.

Toni has made a fix in the replacement rom so for future releases, a3 will match the behavior - problem solved :-)

1)
Is there a preferred file extension for a shrinkled data file?

2)
A request for the addition of an option to add an extra longword at the end of the crunched data file, and possibly also an option to pad the file size to the next multiple of 16.

Cheers

1) I haven't really thought about that. It's not like it was meant as an interchange format. But of course it is nice to tell the shrinkled files apart from other files easily. My first thought would be ".shr". Or maybe ".shrinkled" because this is Amiga and three-letter extensions are so MS-DOS. What do you think?

2) I am not sure I understand why you would want Shrinkler to do that, rather than just padding the file when you load it. Can you tell a bit more about your use case?

1) My thought exactly. I settled for .shr to keep it reasonably short. Strict filename conventions help when writing makefile recipes.

2) My idea was to concatenate several shrinkled files into one, and keep good data alignment. But then it struck me that I don't really benefit from having the shrinkled data aligned. It's the decrunched data I wan't to have aligned, and that's another story. So forget this request... I didn't think it through.


Another question:

Does the decompression routine support in-place operation? If I put the shrinkled data in the end of the buffer, and decompress to the the beginning?

I would vote for ".shrinkled" because it is more clear then ".shr" :-)

Sometimes it will work, but sometimes it will need a safety margin (shrinkled data extending a few bytes beyond the end of the decompressed data). This margin is actually computed for each hunk when crunching in overlap mode, so Shrinkler could also compute it and print it when compressing as data.

The margin will usually not be very big, unless you are trying to compress completely random data. A 16 byte margin should be safe. Remember that when decompressing on 68000, the shrinkled data must be word aligned. On 68020+ it doesn't matter.

cool, thanks!

I'm wondering about a specific behavior when using data compression (-d option). The compressed data grows in 4-byte steps, and sometimes I get an output file with four trailing zeroes. For Example:



And:



Is this some rounding error when writing out the data file (since "835.943 bytes" sound that it might fit into 836 bytes) and I can safely truncate those 00 bytes?

Hello, maybe too late for testing ?

I'm currently trying shrinkler from crinkler.net/shrinkler40.zip
2 problems to report:
The option "-h" for merging hunks: return
"Merging hunks ... EMT Trap"... with an exe where's there is nothing to merge, so ok.

My startup code that GetMsg the eventual Workbench message and return it seems to doesn't work when crinkled... the crunched executable is able to launch from dos, crash at start from WB icon.
Sad !

The decompressor reads the compressed data one longword at a time. This is why the compressed size is always divisible by 4. As the sole data block inside an executable, this doesn't matter, as executable sizes are rounded up to a multiple of 4 anyway.

It consumes bits from the longword one at a time from most significant to least significant. In your case, some of the (upper) bits in the last longword are significant, otherwise it would not be there. If those bytes matter to you, you can try truncating some of the last few bytes (that is, replace them by FF to trigger the worst case if you don't know which data will be in memory right after the compressed data) and see if you get the correct result. This is of course not a sustainable solution, as you would need to redo the experiment every time you re-crunch your data.

Can you say a bit more about your use case?

krabob: You should really be using version 4.4. Version 4.0 is both buggy and slow. :)

If the problems persist in 4.4, please send me (uncrunched) examples of executables that trigger the bugs. Then I will take a look at what happens.

Came up when I was coding this at a point when the header (DOS header and deshrinkler routine) was not divisible by 4, so the size of the compressed data wasn't either.

The "try if it still works" route worked. :) Is it possible to determine the number of significant bytes from the best "After xth pass" number? For example, "755.375" meaning 756 in bytes, "756.992" meaning 757 etc.?

Not quite. The fractional numbers are based on the theoretical entropy for the compressed data. The actual, range encoded data need a few more bits to ensure correct rounding at the end.

Happy New Year ADA!

Another year, another Shrinkler! (OK, it was 3 years since the last one, but anyway...)

Shrinkler 4.5 has now been released! It contains various fixes and enhancements, mostly based on discussions and suggestions here and in other places:

The decrunch header code no longer depends on A3 pointing to the loaded segment list. This makes shrinkled programs able to launch from a Workbench icon (provided the program correctly handles the Workbench message). It also makes it more straightforward to launch shrinkled programs from a custom loader.

For those who prefer not to delve into arcane compression options, there are now a set of numeric options to select an overall compression level, ranging from -1 (fastest) to -9 (slowest). These set all of the compression options to values proportional to the level. Since these options also set the number of iterations, the compression time is approximately quadratic in the compression level. The default compression level is -2.

Each of the compression options can be set in addition to the level, overriding the preset values. In particular, it can be useful to reduce the number of iterations to save some time on the highest levels.

The new --no-crunch option skips crunching and does only hunk processing, including hunk merging if enabled. Thanks to Todi for suggesting the feature.

Completely empty hunks would cause Shrinkler to report a verify error during crunching. These are now padded to 4 bytes.

When crunching a data file, Shrinkler now prints the minimum safety margin to use if the decompressed data overlaps the compressed data when decompressing. If the value is zero or negative, no margin is needed, which means that the compressed data can simply be placed at the end of the decompressed data. If the value is positive, the end of the compressed data must extend at least this many bytes beyond the end of the decompressed data. Note that even though the value may be odd, the compressed data must always be placed on an even address if it is to be decompressed on less than a 68020.

Wonderful, great work!

Excellent!! Will try it out soon.

Hi there
I'm trying to do a Z80 conversion of the decruncher
As i'm new to 68K assembly, i have a question about the algorithm
When computing proba adress in the stack, i guess the d6 register value is always a negative value when doing the LEA?
Another thing: d6 seems to be used as byte everywhere in the source so why the stack needs 1.5K instead of 512 bytes?
thanks
And btw, nice algo!

D6 is usually positive - it is only negative in the single case of reading the bit indicating whether a reference uses a repeated offset or not. This bit has a context separate from all the others. It happens where there is the "moveq.l #-1,d6" instruction.

The instructions calculating the address into the stack ("lea.l 4+SINGLE_BIT_CONTEXTS*2(a7,d6.l),a1" and then "add.l d6,a1") add 4 to get past the return address of the GetBit call, plus another 2 to make room for that single bit context mentioned earlier. This way, the address always ends up into the space allocated on the stack.

The upper byte of D6 is set separately from the lower byte. It happens both in the GetKind and GetNumber procedures, in both cases using the "lsl.w #8,d6" instruction. The upper byte groups the contexts, so they are ordered like this:

-1: Repeated offset (as described above)
$000: Literal/match select for even bytes
$0xx: Literal contexts for even bytes
$100: Literal/match select for odd bytes
$1xx: Literal contexts for odd bytes
$3xx: Number contexts for match offsets
$4xx: Number contexts for match lengths

The reason for skipping $2xx is that the number contexts are accessed through the GetNumber function, which means there will be one more return address on the stack once the execution reaches GetBit, so the effective base address of the context table will be 4 bytes earlier when accessing the number contexts. Thus, $2xx would overlap the $1xx contexts slightly. The easiest (i.e. smallest) way to compensate is simply to not use $2xx. Also the number contexts don't use the whole ranges (only up to 30 at max in the lower byte). So it should be possible to reduce the number of contexts used to less than 600, though that would make the computation of the context index more involved.

Won't a Z80 implementation be horribly slow, having to implement the per-decoded-bit multiplication using additions and shifts? :)

thanks for the explanations, that was what i missed with the negative value and the other positives...
i traced a little that value but sometimes it gets up to 0x6FF so i think i missed a motorola flag somewhere ^_^
the slowness won't be a problem for a 4K or even a 64K prod if the prod rocks!
right now the problem is the code size of 400 bytes as the Z80 has no complex instructions like 68K

I succeed to make a proper code tracing both 68K and Z80 side by side :)

I re-optimised the decruncher as 68K size optimis are very differents from Z80 optims

So the Z80 decruncher size is 350 bytes now and the speed is not that bad -> Less than 1s per kb

I will publish the code on cpcwiki but maybe you may add it to your package?

Again, thanks a lot for this nice algo!

Shrinkler 4.6 is released!

The features and fixes in this release are mainly relevant for people working with large files. This is what is new:

- The suffix array construction, which runs in the slight pause before each hunk is compressed, has been reimplemented using the very fast SA-IS algorithm, which means that these pauses are now almost gone.
- Shrinkler would give a verify error if a data file, or a single hunk, compressed to more than about 2MB (1953125 bytes to be exact - try to guess where that number comes from). This is now fixed. Thanks to Phibrizzo for reporting the bug.
- Increased max number of reference edges (-r option) to 100000000, which can come in handy when compressing very large files.
- The HUNK_RELOC32SHORT and HUNK_DREL32 relocation hunks are now supported. Thus, Shrinkler can be used together with tools which emit such hunks. Thanks to Todi for suggesting the feature.

Hi Blueberry, I'm building latest Shrinkler using VS 2019. The resulting Debug binaries don't work, they index arrays out of range in MatchFinder.extend_left and MatchFinder.extend_right. Oddly enough, Release binaries do work and produce the same output files as binaries I build with cygwin gcc. I thought you might be interested in this. Cheers. Btw is this just me or is it generally not possible to write messages that contain newlines or parentheses?

Thanks for the bug report, Moerder! I looked at the MatchFinder and spotted the errors (they were actually two different errors). The out of range accesses were also easy to reproduce. It does look like the accesses are harmless, but they of course should not be there. Fixed on GitHub.