Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!usc!cs.utexas.edu!texbell!sugar!karl
From: karl@sugar.hackercorp.com (Karl Lehenbauer)
Newsgroups: comp.sys.amiga.tech
Subject: Re: Fibonacci Compression???
Summary: Here's how it works, plus where to go for more info
Message-ID: <5541@sugar.hackercorp.com>
Date: 8 Apr 90 14:46:52 GMT
References: <9004071643.AA01559@jade.berkeley.edu>
Reply-To: karl@sugar.hackercorp.com (Karl Lehenbauer)
Organization: Sugar Land Unix - Houston
Lines: 33

Fibonacci delta compression is described in the IFF 8SVX documentation, which
is available in Amiga manuals and on fishdisks.

How it works is that the delta (difference) between successive samples is
determined, then a 4-bit values are used to represent the differences.
The 4-bit value is an index into a list of fibonacci numbers...
{-34, -21, -13, -8, -5, -3, -2, -1, 0, 1, 2, 3, 5, 8, 13, 21}

Those may not be the right numbers, but they're close.  They're documented.

This method introduces distortion anytime the next value isn't a representable
fibonacci number apart from the current one.  Encoding is a bit tricky because
you should shift numbers forwards and backwards in time to minimize the delta
between the number you're putting out and the value the sample's supposed to
actually be.

The docs say this is best for text, but it does work sort-of-OK for music,
witness the Newtek demo reel 1 as mentioned in another followup.

chatterbox, a program I posted a while back, although it has problems burning
too much CPU time on systems with no fast RAM, includes source code to do
fibonacci delta decompression.  

It is quite clever, if I may say so myself, in that it allocates a buffer the
size of the decompressed buffer, then loads the fibonacci compressed sample
into the back half of the buffer, then decompresses into the same buffer.
Halfway through the decompression, it starts clobbering the compressed data,
but it's data that's already been decompressed.  The last byte of uncompressed
data stored clobbers the last two compressed values, but they of course have
already been decompressed to generate those last two uncompressed data bytes.
-- 
-- uunet!sugar!karl   "I hate quotations.  Tell me what you know." -- Emerson
-- Usenet access: (713) 438-5018