[comp.sys.amiga.tech] Fibonacci Compression???

C503719@UMCVMB.BITNET ("Baird McIntosh") (04/07/90)

>>original question from Sam Isaac <isaac@tahoe.unr.edu> on Apr 6, 1990

Well, first let me say that Amiga IFF sound doesn't seem to be a topic people
know about-- or is it a conspiracy and they're just not talking? :-)

Ok... from Perfect Sound 3.0 manual:
"COMP saves the file in IFF format using Fibonacci Delta Compression, a
 technique that stores each sample as a four bit offset from the previous
 sample.  This will cut your file size in half, but may reduce the sound
 quality considerably."

For any more technical information, like what value each bit of the 4-bit
offset represents, you'll need to refer to the amiga.tech gurus...  I would
add that the file is 1/2 size on disk, but is obviously expanded to full size
when loaded into memory (for edit or play).  Also, for more .fib sounds to
look at, get a copy of Newtek's Demo Reel One and peruse the various
directories on the first disk.  Several of the samples of 'Paranoimia' are
compressed using Fibonacci Delta Compression, and they still sound good.

To uncompress .fib files, you can use Perfect Sound (any version); there are
a few versions of the old Perfect Sound that are PD.  Version 3.0, however,
is *commercial*.  Just load the compressed sound into the editor, and then
save it using normal IFF or DUMP format.  Note that the sound quality will
still be the same.  The file's been compressed already; saving it in a
non-compressed format won't improve sound quality.  The PD sound program can
play compressed sounds, too.

I do hope someone reading this group knows more than me about this.

| Baird McIntosh | c503719@umcvmb.missouri.edu <-or-> c503719@umcvmb.bitnet |
"What will we do when [the UFOs] come?" -- Hobbes
"See if we can sell Mom and Dad into slavery for a Star Cruiser." -- Calvin

karl@sugar.hackercorp.com (Karl Lehenbauer) (04/08/90)

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

riley@batcomputer.tn.cornell.edu (Daniel S. Riley) (04/08/90)

In article <9004071643.AA01559@jade.berkeley.edu> C503719@UMCVMB.BITNET ("Baird McIntosh") writes:
>Ok... from Perfect Sound 3.0 manual:
>"COMP saves the file in IFF format using Fibonacci Delta Compression, a
> technique that stores each sample as a four bit offset from the previous
> sample.  This will cut your file size in half, but may reduce the sound
> quality considerably."
>
>For any more technical information, like what value each bit of the 4-bit
>offset represents, you'll need to refer to the amiga.tech gurus...

Fibonacci delta compression uses the first few numbers of the Fibonacci
series (x(n) = x(n-1) + x(n-2), x(0) = x(1) = 1) as deltas.  The actual
nubmers used are

BYTE codeToDelta[16] = {-34,-21,-13,-8,-5,-3,-2,-1,0,1,2,3,5,8,13,21};

The individual bits don't represent anything--you just take 4 bits,
look that number up in the table, and that's your offset.

This represents small changes fairly accurately, but is miserable
representing large changes, so there is potential for a lot of 
distortion.  In practice, it's ok for sound effects and such, but
questionable for anything that will be listened to critically.

This is, btw, all documented in the IFF specs, available on disk
from CATS and on paper in the RKMs.

-Dan Riley (riley@tcgould.tn.cornell.edu, cornell!batcomputer!riley)
-Wilson Lab, Cornell University

jdutka@wpi.wpi.edu (John Dutka) (04/09/90)

In article <5541@sugar.hackercorp.com> karl@sugar.hackercorp.com (Karl Lehenbauer) writes:
>chatterbox, a program I posted a while back, although it has problems burning

On an almost totally unrelated topic:
Is that, by chance, the program that allows you to assign sampled sounds to
events like a disk being inserted/ejected, and the system beep?  If so, I keep
getting an error using the program - every time I insert a disk with the
program active, I am told that the disk is corrupt/invalid, but when the
program isn't running, the disk is fine...
Can anyone help me?

-- 
| husc6!m2c!wpi!jdutka | "Hey, baby - wanna do some HEAT TRANSFER?           |
| jdutka@wpi.wpi.edu   |  Heh, heh, heh!"                                    |
| jdutka@wpi.bitnet    |     -Mechanical Engineers On The Prowl              |
| John Dutka  _________|_____________________________________________________|