| |
ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Decrunch direction
So I'm in the middle of updating nucrunch's self extracting file generator to change over to the two-segment no-copy forward decrunch method I pioneered in tinycrunch. The forward decruncher is slightly faster than the reverse, and the two segment method should also make it easer to add support for lowering the minimum start address to 0x0200.
I was just wondering if there was any point in maintaining the reverse decruncher at all - if I drop it, then I can simplify the code somewhat, and maintenance will be saner moving forward. I pretty much only implemented it for SFX purposes, and that requirement is gone now.
Any thoughts?
Definitions:
A forward decrunch reads the input data from the start to the end, and also outputs in the same direction. A reverse decrunch starts from the end of the input data and works backward, and does the same with the output. It's handy for traditional single-segment self extracting files as you don't have to copy the input to high memory before you start decrunching.
Two segment method: two segment SFXes contain two chunks of data - the first decompresses to the area of RAM starting at the end of the loaded data, and the rest is an in-place compressed copy of the rest.
eg
before decrunch: ........daaaaaaaabbbbbb......................
after decrunch: ..d...BBBBBBBBBBBBBBBBBAAAAAAAAAAAAAAAAAAA...
where
- a is a compressed copy of the data at A
- b is a compressed copy of the data at B
- d is the decruncher (which copies itself to low memory before executing.) |
|
... 10 posts hidden. Click here to view all posts....
|
| |
Mixer
Registered: Apr 2008
Posts: 452 |
So, with forward decrunch the crunched file must be loaded to the (end of allocated space - sizeof decrunch file)?
Or does the decruncher do the transfer to the end of space?
If then, one needs to know the size of compressed file to be able to set the load address to the right location.
Isn't this just transfering some operations off of the decruncher to whatever code uses the packed file? |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
Quoting MixerSo, with forward decrunch the crunched file must be loaded to the (end of allocated space - sizeof decrunch file)? Yes. If you mean (end of allocated space - sizeof crunched file).
Quoting MixerOr does the decruncher do the transfer to the end of space? No. That copy is to be avoided (as it isn't done for classic backward decrunching, which has been used to avoid that copy).
Quoting MixerIf then, one needs to know the size of compressed file to be able to set the load address to the right location. That's what the cruncher would do, assign the right loading address for the crunched data file.
Quoting MixerIsn't this just transfering some operations off of the decruncher to whatever code uses the packed file? Not really, the idea is to avoid copying packed data while still getting that bit of extra speed forward decrunching provides over backward decrunching. In the scenario of loading packed files (rather than running an SFX), the load address is good for forward decrunching, which the loader would then proceed to do while loading. |
| |
bubis
Account closed
Registered: Apr 2002
Posts: 19 |
Wow, this two segment method is a brilliant idea! You should patent it! :D |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Thanks Bubis! Re. patents, haha probably.
Some diagrams to illustrate my comments above:
I've elided the decrunch code space allocation and copying time, (they're pretty minimal), and assumed
- a destination area that starts from ~$0800
- an initial data load to $0801 (as is required for anything with a sysline)
- decrunch doesn't start until after loading (no other option for onefilers)
- a three block interleave fastload (just so I don't swamp the graphs with load time)
- a 60% compression ratio
I've also assumed identical decompression speed for forward and reverse decrunch. Going back over my old benchmarks the two nucrunch decoders turn out to be much of a muchness; sometimes one is 1-2% faster, sometimes the other. I'm still dropping the reverse codec mind; as much as anything else I need to switch to either copy+decrunch or multisegment just to support destinations below $0800. |
| |
Mixer
Registered: Apr 2008
Posts: 452 |
Awesome space-time graphs. |
| |
Copyfault
Registered: Dec 2001
Posts: 478 |
Cool idea doing a split up of the data sequence! However, this should arise some questions, e.g. how to find the best "split point" of the complete (unpacked) data sequence, wether it makes sense to have even more segments, etc...
Quoting ChristopherJam [...]
Two segment method: two segment SFXes contain two chunks of data - the first decompresses to the area of RAM starting at the end of the loaded data, and the rest is an in-place compressed copy of the rest.
eg
before decrunch: ........daaaaaaaabbbbbb......................
after decrunch: ..d...BBBBBBBBBBBBBBBBBAAAAAAAAAAAAAAAAAAA...
where
- a is a compressed copy of the data at A
- b is a compressed copy of the data at B
- d is the decruncher (which copies itself to low memory before executing.)
Just a thought about the decruncher code: you could avoid copying this if the decruncher is placed at the end of the crunched data chunk, i.e.
before decrunch: ........aaaaaaaabbbbbbd......................
which should allow to decrunch to the lower mem locations without hassle, like
after decrunch: ..BBBBBBBBBBBBBBBBBBBBdAAAAAAAAAAAAAAAAAAA...
Depending on the inner workings of the decruncher it might even be possible to "overwrite" it in the 2nd decrunch phase as I can imagine that having the decruncher code in the middle of the decrunched data is not wanted in most cases.
Should speed up the overall decrunch speed a little and widen the memory location for the decrunched data. Just some thought that came to my mind reading about this !!brilliant!! two segment decrunch method... |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1409 |
Thanks for feedback all.
As for split point determination, tinycrunch currently does a first pass where it compresses the entire input file to get an estimate of the end-of-load address, then does a few trial iterations until the intersegment gap is reasonably small (cf TinyCrunch V1.1.1 source for details; run in verbose mode to see the iterations in action).
I am indeed considering placing the default ("medium") nucrunch decoder at the splitpoint for the next release, probably with a tinycrunch decoder copied to the stack for decrunching the medium decrunch routine at start of decrunch, then infilling the gap once the bulk of data has been decrunched.
But yes, ideally I'd place the primary decompressor somewhere where the final file just has a run of zeros or some other easy to reproduce data. A feature for another day, when I get around to putting the final cleanup code in the sprite position registers like that other all memory decruncher whose name currently escapes me. |
| |
Radiant
Registered: Sep 2004
Posts: 639 |
Simple. Smart. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
first time I just skimmed through the first post, but if bubis says something is brilliant, I must check, and it is ;) |
| Previous - 1 | 2 - Next |
