Yer LZMA is a nightmare, I didnt do all the work on it, its from a project I worked on with others. But its a LZ77 style as you say that has differing ways of encoding the length and offset, this increases compression by not always having to use the same number of bits for the length and offset storage.
Everything is bit range coded using markov chains but its all interleaved. Basically everything is sent to a bit encoder which works out a probability of it being a 1 or a 0 based on arithmetic encoding style of subdividing a global range. Everything has its own probability which is updated following each bit. So decoding it starts by checking whether its a literal or lz77 by decoding a single bit from a bitdecoder. Reading that bit updates the literal/not bit decoder probability ready for next time. If its a literal then it decodes and updates the literal bit probabilities in turn. It doesnt have to transmit probability tables as they are calculated on the fly working on the theory that as long as the encoder and decoder agree on how to update the probability based on the bit (i.e. the encoder updates the probability based on the 1/0 after it encodes it, then the decoder can do the same as it will have decoded the bit so it knows if its a 1/0 to alter its probability). As i say, i know the theory and how the code works, but i didnt write most of it. Im looking to update it so that it works on nibbles and has smaller ranges more suited to Sam. Also I looked at redoing the decoder but most of its is hardcoded to 32bit maths, even though its mostly shifts and multiplies, 32 bit is not nice in z80. So ill rework it into mainly 16bit. Adrian -----Original Message----- From: owner-sam-us...@nvg.ntnu.no [mailto:owner-sam-us...@nvg.ntnu.no] On Behalf Of Thomas Harte Sent: 07 August 2010 20:16 To: sam-users@nvg.ntnu.no Subject: Re: Dizzy (was:Porting spectrum games...) LZMA doesn't seem to be terribly well documented, but I'm curious so do you mind if I ask a few questions? The LZ77-style stuff is quite well documented on Wikipedia, with variable packet sizes but otherwise unremarkable. Though it looks like length of repetitions is limited to 273 at most and the maximum distance isn't particularly clear. I guess for Sam screen purposes, 273 is more than enough and 15 bits for distance is always more than enough, with fewer bits being an option? Then there's the range coding aspect. It looks like the individual LZ77 packets are range coded and the fixed values encoded in literal packets are range coded separately? So you end up with two streams and you follow the LZ77 stream, grabbing a decoded digit from the data stream whenever you hit a literal packet? There are vague references to context and Markov chains without much exposition - I've taken this to mean that you've not just one table of symbol probabilities, but you divide them into groups and each group uses a separate table of probabilities recording what may come next. Those probabilities are then used for the range coding. And it's implied that group membership is indicated by the value of a certain number of the most significant bits in the normal LZMA course of things, presumably to make the probability tables cheap to transmit. Is that all correct? Or even close? It's all much more clever than anything I was trying. On Tue, Aug 3, 2010 at 9:11 PM, Adrian Brown <adr...@apbcomputerservices.co.uk> wrote: > Im using an LZMA approach similar to that in 7-zip - ive nearly finished > moving the code out of my project stuff so i can send it over. > > Adrian > > -----Original Message----- > From: owner-sam-us...@nvg.ntnu.no [mailto:owner-sam-us...@nvg.ntnu.no] On > Behalf Of Thomas Harte > Sent: 03 August 2010 18:16 > To: sam-users@nvg.ntnu.no > Subject: Re: Dizzy (was:Porting spectrum games...) > > I've just been reading about range/arithmetic coding, which feels like > it should do better than Huffman but seems to require some modulo > arithmetic per input or output token so may not be time effective on a > Sam. Have you been using anything like that? > > On Mon, Aug 2, 2010 at 12:43 PM, Thomas Harte <tomh.retros...@gmail.com> > wrote: >> It'll be interesting to see how you've done it. If code overhead is an >> issue then you've obviously taken quite a different approach to me. >> >> I had a quick poke around on Amazon for textbooks on this sort of >> thing but ended up preordering a Kindle. So that's my book budget gone >> for the next couple of months... >> >> On Sun, Aug 1, 2010 at 1:46 PM, Adrian Brown >> <adr...@apbcomputerservices.co.uk> wrote: >>> Ill extract it from the code that I cant send and put it in its own project >>> is C first >>> >>> Adrian >>> >>> -----Original Message----- >>> From: owner-sam-us...@nvg.ntnu.no [mailto:owner-sam-us...@nvg.ntnu.no] On >>> Behalf Of Stefan Drissen >>> Sent: 01 August 2010 13:31 >>> To: sam-users@nvg.ntnu.no >>> Subject: RE: Dizzy (was:Porting spectrum games...) >>> >>> Not a C person, but would http://sdcc.sourceforge.net/ help? >>> >>> -----Original Message----- >>> From: owner-sam-us...@nvg.ntnu.no [mailto:owner-sam-us...@nvg.ntnu.no] On >>> Behalf Of Adrian Brown >>> Sent: zondag 1 augustus 2010 14:04 >>> To: sam-users@nvg.ntnu.no >>> Subject: RE: Dizzy (was:Porting spectrum games...) >>> >>> This will be a nightmare to get into z80 ;) that is the downside. (unless >>> you build it using Sam C - it might compile under that) but i think a z80 >>> version would be required. >>> >>> -----Original Message----- >>> From: owner-sam-us...@nvg.ntnu.no [mailto:owner-sam-us...@nvg.ntnu.no] On >>> Behalf Of Thomas Harte >>> Sent: 01 August 2010 12:16 >>> To: sam-users@nvg.ntnu.no >>> Subject: Re: Dizzy (was:Porting spectrum games...) >>> >>> As a quick mea culpa, there was a bug in my code that means the second >>> set of figures I had were wrong. I'm back to an average 10% and up to >>> 15% worse than Adrian. >>> >>> On Sun, Aug 1, 2010 at 9:37 AM, Frode Tennebø <fr...@tennebo.com> wrote: >>>> On Sun, 01 Aug 2010 10:18:55 +0200, Andrew Park <alp...@ntlworld.com> >>> wrote: >>>> >>>>> Back in the days of the Sam there was a screen compressing utility which >>>>> was ok, anyone know where i can find it? >>>> >>>> Lord Insanity's Screen Cruncher >>>> >>> (ftp://ftp.nvg.ntnu.no/pub/sam-coupe/disks/utils/LordInsanityScreenCruncher. >>> zip)? >>>> >>>> -Frode >>>> >>>> -- >>>> ^ Frode Tennebø | email: fr...@tennebo.com | fr...@irc ^ >>>> | with Standard.Disclaimer; use Standard.Disclaimer; | >>>> >>> >>> >>> >>> >>> No virus found in this incoming message. >>> Checked by AVG - www.avg.com >>> Version: 9.0.851 / Virus Database: 271.1.1/3042 - Release Date: 07/31/10 >>> 20:34:00 >>> >>> >>> >>> >>> >> > > > >
