| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Release id #117852 : Doynax LZ
Has anyone else discovered further misbehaviour than that i described in the goofs? I'd add a bunch of features then and release it in a fixed and improved version. |
|
| |
chatGPZ
Registered: Dec 2001
Posts: 11386 |
\o/ |
| |
tlr
Registered: Sep 2003
Posts: 1790 |
I noticed it broke on some of my test data. Thumbs up for debugging it! |
| |
HCL
Registered: Feb 2003
Posts: 728 |
Why not let Doynax himself release a new version of his cruncher? He was around here just a few days ago, and probably still is.. |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
The source is there and open? So why not developing further on it, even more as it is rendered unusable on certain files this way? Doynax did not respond to Axis's mail so far, so i was just fixing it on my own in the meantime. It is not that we coders couldn't help ourselves :-) |
| |
HCL
Registered: Feb 2003
Posts: 728 |
Well, of course you can.. and if it's just a bugfix you want to release, then sure go ahead.. but more improvemets.. (?). Best would of course be if Doynax could tell his opinion himself..
When Doynax first started to develop his cruncher, he based it on the source code from ByteBoozer. It was also free/open, but i appreciated that he asked me about it first.. |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
Didn't spot any serious bugs so far, but i noticed that you can only decrunch to an address with the same lo-byte as the original file's loading address, meaning the destination address is not arbitrary. This may be a bug, but it may also be the result of an optimization. |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
So far it works okay when the depackaddress % 256 == 0. However it should handle other address lowbytes, but the compressed files then will be different, as it takes care that on every page (output) crossing the type bit is read again. |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
So you confirm that it is not a bug but the result of an optimization.
As any compressed or literal runs must not cross a page boundary in the output buffer (if i understood you correctly), the same data will compress differently depending on its offset to the page boundaries.
With all 256 possiblities for a given data file, the maximum difference in pack ratio should not be so much now, should it? Just wondering.. :) |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Well, this page wrapping thingy is the result of the "feature" to be able to always just render a new page of output per call of lz_decrunch. As it is just a single entry point one has to fetch a type_bit there. If you change the depacker to depack all on a single call, that problem can be solved easily. It even can be solved with keeping the feature (but making the depacker even bigger), by remembering if we exit from a literal run or a match.
|
| |
HCL
Registered: Feb 2003
Posts: 728 |
Personally i would not see this a s feature :P. Probably that's because of my lack of intelligence. |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Well, you could depack partially by this feature until a certain barrier that you release when the memory is free to depack to. Also i think this depacker was used in a game doynax did, so it has a different focus on depacking than when using it with a demo?
I just removed this feature quickly to proof my assumptions. Result: same filesize, and i can depack to any address now \o/
|
| |
Krill
Registered: Apr 2002
Posts: 2980 |
It's certainly a feature for a streaming decompressor to only decompress a chunk of data with each call. You can implement ring buffers, decompression on demand etc. on top of it easily. |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
someone could write a little summary on what this can do above/below Byteboozer, LZWVl, and the likes please? |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
I've been away for the last week, putting out some fires and putting in 15-hour working days so I just noticed this thread. Well, that and I'm useless at keeping up with private e-mail.
Anyway, I'm quite impressed with Bitbreaker's work so far in finding and fixing the bugs in the packer. I think it should painfully obvious by now that I've only tested it on my own data (and the Calgary corpus IIRC.)
Unfortunately I can't see any way of handling the 256-byte destination address wrapping without wasting two cycles/bytes, e.g. decreasing the length by one before storing it and raising carry before ADC.
Quoting BitbreakerThe source is there and open? So why not developing further on it, even more as it is rendered unusable on certain files this way? Doynax did not respond to Axis's mail so far, so i was just fixing it on my own in the meantime. It is not that we coders couldn't help ourselves :-) Go ahead, it's a public domain utility. There's is nothing quite as pointless as a development tool which you can't understand and fix/modify to your liking.
Still, I'd prefer to maintain and publish the thing in an "official" release if possible. The world is littered with enough branched versions of various utilities as it is so I'd prefer to stick to a single main line as long as is feasible.
Quoting BitbreakerWell, you could depack partially by this feature until a certain barrier that you release when the memory is free to depack to. Also i think this depacker was used in a game doynax did, so it has a different focus on depacking than when using it with a demo? Yeah, that's the general idea. It was created for a shoot'em'up which was supposed to play as a single contiuous level (think SWIV on the Amiga). The loader is responsible for continually streaming in fresh data during spare cycles (e.g. tilemaps, attack sequences, charsets, sprites, music) into a circular buffer which the game consumes at leisure.
Normally the cruncher looks at the target address if you feed it a *.prg file to handle this for you and I assumed that no one would need to decrunch to multiple target addresses. Still, for a wider release an #ifdef to get a more traditional interface and a separate streaming mode in the cruncher sounds like an excellent idea. |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quoting Oswaldsomeone could write a little summary on what this can do above/below Byteboozer, LZWVl, and the likes please? What it can do? Streaming decrunching, basically. What it can't do is native crunching.
Beyond that it's just another possible trade-off between compression rate, decrunching performance, and decruncher size. The actual encoding is virtually the same as ByteBoozer, which it was based on, but with the bits rearrange somewhat for faster decoding.
Plus better parsing and tweaked match offsets to try to squeeze a few extra bytes out of it. |
| |
enthusi
Registered: May 2004
Posts: 677 |
A bit unrelated,but are there any depackers with minmum of RAM usage?
Stream-decrunch byte-by-byte without large tables in RAM or ZP.
I.e. exomizer hast that nice get_decrunched_byte but uses that 156 Byte table (=large in my context *g*).
Any ideas?
|
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quoting enthusiA bit unrelated,but are there any depackers with minmum of RAM usage?
Stream-decrunch byte-by-byte without large tables in RAM or ZP.
I.e. exomizer hast that nice get_decrunched_byte but uses that 156 Byte table (=large in my context *g*).
Any ideas?
RLE perhaps?
If you've got ROM to spare but no RAM then you can't go wrong with static entropy coding, e.g. Huffman/arithmetic. For static dictionary compression from ROM you might try "Off-Line Dictionary-Based Compression" (Larsson & Moffat.) |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
@doynax: i put the stuff to our svn, but would be happy to have the most recent version from you to be sure i based my fixes on that version. Of course things can be switched on and off by ifdefs, but also a command-line option would do. As for the 256 byte literals i found a nice way to branch out Actually i won't get an overrun in the lowbyte, but thereofre i can directly fork out with a bew after the lda lz_scratch before the adding starts. Here it doesn't hurt much it and works well :-) Also started to save some bytes on the decruncher, but it is a hard work :-)
@enthusi: there's decrunchers with smaller size, but usually speed is the tradeoff, as you then have to do a lot of jsrs to common code. So also the doynax decruncher could be smaller, but then slower, i could try a slow but small version though. |
| |
doynax
Account closed
Registered: Oct 2004
Posts: 212 |
Quoting Bitbreakeri put the stuff to our svn, but would be happy to have the most recent version from you to be sure i based my fixes on that version. Certainly, though I don't think I've changed much since aside from translating it to CA65. IIRC I fixed a bug where the cruncher would crash on zero-byte files.
Quoting BitbreakerOf course things can be switched on and off by ifdefs, but also a command-line option would do. I was thinking more along the lines of the decruncher actually, though I suppose the users would prefer separate files.
Quoting BitbreakerAs for the 256 byte literals i found a nice way to branch out Actually i won't get an overrun in the lowbyte, but therefore i can directly fork out with a beq after the lda lz_scratch before the adding starts. Here it doesn't hurt much it and works well :-) Nice :)
Giving it some more thought I think I can do you one better: lda lz_scratch
lda lz_dst+0
; sec
sta lz_dst+0
bcs .upper_rts
.
.
.
.lrun_gotten:
tay
; sec
sbc #$01
sta lz_scratch Basically adding the length minus one with carry ensures overflow. Carry is always set before the SBC (due to the preceding branches), and it will also always be set after the literal copying loop as well except for the 256-byte case. However a sector refill must then also have occured, and part of the contract for that function is to raise carry on exit.
Net cost: zero cycles and one byte.
Quoting BitbreakerAlso started to save some bytes on the decruncher, but it is a hard work :-) Yeah, as you've probably noticed it was optimized for speed rather than size.
Quoting BitbreakerThere's decrunchers with smaller size, but usually speed is the tradeoff, as you then have to do a lot of jsrs to common code. You'll still need a decompression window if some sort though, which would be the main memory hog. I wonder how LZ coders perform with really small windows, many references are rather short after all.
As an aside, has anyone experimented with feeding a "don't care" mask to a compressor? I find myself having plenty of holes in my data, along with plenty of alignment and SMC bytes my code which might benefit. |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Quoting doynaxI was thinking more along the lines of the decruncher actually, though I suppose the users would prefer separate files.
Well, of the user just wants to depack a crucnhed file as a whole, the window stuff and per page rendering is not needed and thus a type bit can be always omitted after a literal run, except when it is of maximum size. In that case we loose the one feature, but gain teh possibility to depack to an arbitrary address, what more often is of good use in a trackmo. In that case, also your proposal with the forced page crossing does not work anymore of course. But well, it is two ways one can go, and the user has to decide which to use. Both can be configured, depending on ones needs. In case it just needs a bit of an ifdef-hell within the .asm part :-)
Quoting doynaxYeah, as you've probably noticed it was optimized for speed rather than size.
Well, compared to other depacker routines it is still of decent size, and you did a good job in saving bytes while making it fecking fast. I did a diversion of the bongo-cruncher from Mr. Wegi recently + decruncher. It is shorter in size, but your depacker is still 25% faster, though it is way faster than the other well known depackers, and despite shifting in the bits from the stream the usual way. However i did the copy loops faster, by fixing up the get_pointers index beforehand.
Also it would be pretty possible to let the cruncher spit out sfx files as well. Though it was not directly designed for that it is easy to adopt. |
| |
Krill
Registered: Apr 2002
Posts: 2980 |
I have just finished adding Doynax LZ to my loader. (Yes, it's FAST! And it seems to be between Exomizer and Pucrunch in pack ratio. New gold standard default demo packer hands down.) I'd like to release it with all packer fixes. When can i expect to see an official Doynax-approved patch? :) |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
It turns out, that doynax performs well on small files, and could even perform better per file when tweaking the offsettables. Also the encoding used performs worse on huge files with huge offsets and huge lengths. I made tests with otehr encodings that squeeze out way more bytes on huge files. But well, good that there's furtehr challenges to fight our boredome with :-P |
| |
chatGPZ
Registered: Dec 2001
Posts: 11386 |
go go go ! =) |
| |
Fungus
Registered: Sep 2002
Posts: 690 |
Yes Yes, bugfixed version puhleeeeeeeeeeeeze =] |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
Doynax has all the changes i made and is doing a proper release from that hopefully soon, so i ask for patience :) |
| |
Bitbreaker
Registered: Oct 2002
Posts: 508 |
here you go:
Doynamite 1.0 |
