In-Place Packers/Unpackers

[mcgeezer]

Hi All,

For my project I'm currently using the Rob Northen packer/depacker because mainly it was the first one I found and it did a job. The problem with it is that it doesn't support inplace depack and some of the file I pack take a while to pack using WinUAE even with warp mode.

Could anyone suggest a better packer to use that is pretty straight forward to use for packing data files only? It needs to support in place depack as I can get back 160Kb of ram if I do. I'll need the assembler unpack routine as well to swap out.

Cheers,
Geezer

[Galahad/FLT]

Originally Posted by mcgeezer

Hi All,

For my project I'm currently using the Rob Northen packer/depacker because mainly it was the first one I found and it did a job. The problem with it is that it doesn't support inplace depack and some of the file I pack take a while to pack using WinUAE even with warp mode.

Could anyone suggest a better packer to use that is pretty straight forward to use for packing data files only? It needs to support in place depack as I can get back 160Kb of ram if I do. I'll need the assembler unpack routine as well to swap out.

Cheers,
Geezer

If what you mean by "in place" I.e. if you load to address $40000, you need to also depack to the same address, RNC Propack most certainly does support that.

It uses quite a large ish stack space though, $180+ bytes to achieve it.

There are 2 types of Propack, look at the header, it will say RNC and then after that a value of $01 or $02.

[mcgeezer]

Originally Posted by Galahad/FLT

If what you mean by "in place" I.e. if you load to address $40000, you need to also depack to the same address, RNC Propack most certainly does support that.

It uses quite a large ish stack space though, $180+ bytes to achieve it.

There are 2 types of Propack, look at the header, it will say RNC and then after that a value of $01 or $02.

In the version I have the header in the source says this:

*------------------------------------------------------------------------------ 
* PRO-PACK Unpack Routine (Compact Version) - MC68000, Method 1 
* 
* on entry, 
*	a0.l = start address of packed file 
*	a1.l = start address to unpack file 
*	(note: a1 cannot be equal to a0) 
*	stack space required: $1DC bytes 
* 
*	all other registers are preserved 
*------------------------------------------------------------------------------

So i guess I need Method 2 right?

[FSizzle]

It is quite common for packers which can decompress in-place to require the source to be aligned to the end of the buffer rather than the start.

i.e. if input size = $400 and output size = $1000 then the input data should start at $600 bytes in the buffer.

Is that possibly a requirement of propacker?

[alpine9000]

As Galahad said, use method 2 and then you can de-pack in place.

As for packing speed, if you're cross building you can use this on your host machine:

https://github.com/lab313ru/rnc_propack_source

Creates 100% identical files to the RNC version run on the Amiga.

[Galahad/FLT]

I've figured it out, you're using the COMPACT version of RNC 1 to unpack.

You can use RNC 2 or RNC 1 so long as its the non COMPACT version, check out the zone, i've put what I use there

[phx]

Another option besides unpacking in place would be to do it while loading. So you only need a small additional buffer, let's say 512 bytes, for the next block.

There are some disadvantages though: It is not as fast, because you have to fill the buffer from time to time, and it only works with packers which use a single data stream. Don't know if Propack falls into this category, but the LZ-packer, which I used for my last games, did not.

Simple packers, like Bytekiller, are usually fine for this method.

[mcgeezer]

Originally Posted by Galahad/FLT

I've figured it out, you're using the COMPACT version of RNC 1 to unpack.

You can use RNC 2 or RNC 1 so long as its the non COMPACT version, check out the zone, i've put what I use there

Nice one Galahad, will take a look!

[mcgeezer]

Originally Posted by phx

Another option besides unpacking in place would be to do it while loading. So you only need a small additional buffer, let's say 512 bytes, for the next block.

There are some disadvantages though: It is not as fast, because you have to fill the buffer from time to time, and it only works with packers which use a single data stream. Don't know if Propack falls into this category, but the LZ-packer, which I used for my last games, did not.

Simple packers, like Bytekiller, are usually fine for this method.

I did have a look on Aminet and seen something called cranker... but it looked a bit over the top for my needs.

[ross]

Damn! I would have so much to say on the subject that I can't find the time to do it...

[dodke]

For very fast on the fly data decompression I've used lz77 a lot.
There are sources here for decompression on 68k and also a C program for compression and decompression which works on any platform:
http://privat.bahnhof.se/wb800787/da...h/lz77_v13.zip

Recently I've started using lz48 though which is pretty much as fast and still simple but slightly better:
http://www.cpcwiki.eu/forum/programm...herdecruncher/

[SyX]

Originally Posted by ross

Damn! I would have so much to say on the subject that I can't find the time to do it...

I would love to see your super optimized aplib decruncher variant, @ross... maybe in a few months you will get enough free time

Those days i use ZX7, although the compressor is slower for big files and doesn't crunch so well than aplib (but never more that a few dozens of bytes); the zx7 decruncher is faster and smaller than aplib; support forward and backward decrunch, of course; and everything is open source, while we will never get the aplib cruncher sources.

Another great feature is that the delta (extra bytes for decrunching in place) is guaranteed that is never bigger than 4 bytes; because that for decrunching in place, you only need to reserve in memory the decrunched file size + an extra long, load the crunched file at the end of this zone and decrunch

And this extra long can be used as a flag for signaling that data was loaded or another thing that you like.

... and i forget, a nice feature is that it is super easy to modify the decruncher for adding a function that changes the calculation of the destination address. That is useful for making funny FX effects while you are decrunching data directly on the screen or if you want to sort your data in other way for getting a better compression rate (for example, storing screen as tiles or interleaved screens as independent planes, ...)

[modrobert]

I'm assuming this is available in some shape or form on Amiga?

https://en.wikipedia.org/wiki/LZ77_and_LZ78

A personal favourite is the V.42bis variant of this compression modems used back in the day, where data which was already compressed passed through without performance loss, also relatively easy to implement in hardware.

EDIT: Great, found it two posts above mine. Thanks dodke.

[Photon]

Galahad and phx have given help, so all that is left is a timid logical reaction: In-place decompression so completely goes against the grain of what data compression is.

Load-to-top-of-dest or even just a few bytes to spare for a load offset (instead of having to copying to/from the stack to slow things down, spending more bytes) allows maximum decompression speed, making your program appear 'zippier' to the user!

[mcgeezer]

Originally Posted by Photon

Galahad and phx have given help, so all that is left is a timid logical reaction: In-place decompression so completely goes against the grain of what data compression is.

Load-to-top-of-dest or even just a few bytes to spare for a load offset (instead of having to copying to/from the stack to slow things down, spending more bytes) allows maximum decompression speed, making your program appear 'zippier' to the user!

The lesser complexity benefit out ways the speed benefit for my needs.

[ross]

It's all about costs/benefits.
The simplest thing would be that the compressed data were at the beginning of the buffer containing the final destination.
In this way the user should not worry about anything except to allocate the buffer, load the compressed data at start address and call the unpacker.
But in this case, even neglecting a securyty zone and doing a pure LZ compression, it's a necessity to arrange the bitcoding for backward references access,
which is certainly slightly slower than a forward access.
For the forward case you can think of copying the data to the end of buffer (loss of speed in the unpacker)
or load compressed data directly at the top (slightly complicating the logic of the loader).

I have to quantify the loss of speed for a backward fetch bitcoding.

[ross]

Originally Posted by SyX

Another great feature is that the delta (extra bytes for decrunching in place) is guaranteed that is never bigger than 4 bytes; because that for decrunching in place, you only need to reserve in memory the decrunched file size + an extra long, load the crunched file at the end of this zone and decrunch

This is interesting.
So if you use the 'bitchoice' token as a longword you can make a real in place decompressor (with backward fetch).
The problem is that it would be rather slow in a bare 68k (no problem for 020+).
But I can't think of any possibility to guarantee a safety margin of 4 bytes except by cutting off the compression at some point for pathological cases.
In any case, for normal graphics and code data, it is rare to find yourself in such negative situations, especially if your compressor uses 'literal sequences' and therefore pure encoding cannot expand the stream much.

[SyX]

Originally Posted by ross

In any case, for normal graphics and code data, it is rare to find yourself in such negative situations, especially if your compressor uses 'literal sequences' and therefore pure encoding cannot expand the stream much.

Exactly! And in the days before the new improved winuae debugger, I used the vamos project for testing that the normal case worked well and the same happened with data prepared specially for trying to exploit those pathological cases.

Usually we try to consider every possibility, but sometimes the probability of happening every one of those are very low... not impossible, but well, we have tests for that reason.

[Photon]

Originally Posted by mcgeezer

The lesser complexity benefit out ways the speed benefit for my needs.

There's a meme for such a statement



There's absolutely zero complexity from adding an offset.

Rather, someone who made the cruncher for you to use, would facepalm and ask, "What the hell were you thinking, decompressing to the same place?? Don't you even understand the basics of coding? Like, source/destination overwrite, ring a bell?"

Anyway. Understand the tools you use. Load to an appropriate address. Decompress to destination. Simple & lets you select the best compression tool from all the compression tools there are, for your needs.

Aahh..! Now I can go back to my timid self again.

[mcgeezer]

Originally Posted by Photon

There's a meme for such a statement



There's absolutely zero complexity from adding an offset.

Rather, someone who made the cruncher for you to use, would facepalm and ask, "What the hell were you thinking, decompressing to the same place?? Don't you even understand the basics of coding? Like, source/destination overwrite, ring a bell?"

Anyway. Understand the tools you use. Load to an appropriate address. Decompress to destination. Simple & lets you select the best compression tool from all the compression tools there are, for your needs.

Aahh..! Now I can go back to my timid self again.

There's no need for this response, you're a moderator but more importantly have some respect for a fellow coder, I suspect you should owe me an apology.

Do I understand the basics of coding? yes I fucking well do! You should try going upward of 20,000 lines of assembler into a game under a time limit and things tend to get a bit complex.

All I asked for was a bit of help with de-packing in place, the speed of which isn't important at this time, the reason was to save on memory (which I have thanks to Galahad). I have used the in place de-pack routine he put into the zone because as it stands I allocate ram, load the file to the start of that allocation and then de-pack using the same address, fair enough I could have loaded the file to an extra offset - but that adds some complexity.

Go back to being your normal self for all I care, but keep things respectful and we'll get along just peachy.