Lossless audio compression.

[Thorham]

Hi,

I'm looking for a reasonably good, lossless way to compress 16 bit stereo (28Khz) audio. I know there are things like FLAC, but I need something that will allow decompression without a high cpu load on a 50Mhz '030. Anyone know of anything useful? If it's not possible, then just forget it, but if there is any chance it's doable, then I'd like to hear some ideas.

Any suggestions are appreciated

[Genju]

FLAC is the lossless codec with the least complexity (and hence CPU usage) out there. Unless you want to create your own (which is probably bound to fail, considering that coding an efficient lossless audio codec is everything but trivial), you should either try FLAC or forget about the idea.

[Photon]

Hm, why say that Genju? I haven't seen any proofs that there is no better compression algorithm for lossless audio than FLAC. Certainly it's easy to make alternatives yourself that have a lighter CPU load.

If it's for Amiga I would try something inside the sampleplayer interrupt itself, to replace the 'fetching from buffer', a replacement for the buffer handler. If the algorithm is simple enough, you'd only have to be a sample ahead instead of temporarily buffering it in memory.

Delta conversion and RLE is the simplest I can think of that has any effect.

[Genju]

Originally Posted by Photon

Hm, why say that Genju? I haven't seen any proofs that there is no better compression algorithm for lossless audio than FLAC. Certainly it's easy to make alternatives yourself that have a lighter CPU load.

FLAC is already the best trade-off between compression ratio and complexity. Sure, you can try simple huffman compression, but you won't save more than 15-20% of the original size then. FLAC uses stuff like joint-stereo and inter-channel correlations and you can't go any lower with the complexity unless you want to end up with something that doesn't compress audio better than zip would.

[Thorham]

Originally Posted by Genju

FLAC is the lossless codec with the least complexity (and hence CPU usage) out there. Unless you want to create your own (which is probably bound to fail, considering that coding an efficient lossless audio codec is everything but trivial)

Sorry, but FLAC is too heavy (which is unfortunate because it's good) Meynaf is already doing a FLAC decoder on his 50Mhz '030, and I think it uses around 90% cpu time, and his decoder is well optimized. That's the last thing I've heard from him if I'm remembering it correct (which may not be the case ). I'm looking for something that's effective (doesn't have to be as effective as FLAC), and relatively fast.

Originally Posted by Genju

you should either try FLAC or forget about the idea.

I don't think it's a good idea to forget about it so soon

Originally Posted by Photon

Certainly it's easy to make alternatives yourself that have a lighter CPU load.

Have to agree with that

Originally Posted by Genju

If it's for Amiga I would try something inside the sampleplayer interrupt itself, to replace the 'fetching from buffer', a replacement for the buffer handler. If the algorithm is simple enough, you'd only have to be a sample ahead instead of temporarily buffering it in memory.

It's just for music replaying, isn't a simple buffer easier?

Originally Posted by Genju

Delta conversion and RLE is the simplest I can think of that has any effect.

Yep, sounds good. With deltas the number of bits drop, and you can easily RLE the sign for each delta (tested on the peecee). Seems promising

Any more suggestions?

[Zetr0]

@Thornam

whats your target CPU for this project?

If you are looking at something 020'ish or lower - then huffman/delta RLE with a resizable buffer (pending on target) might be the only choice.

What are you hoping to achieve in terms of running CPU load / audio quality (bits) and compression ratio?

As a thought you could use a a parser that removes/clips non-audible sounds from the audio file first and then encodes / compresses the audio file... although this is a lossy approach it will likey prove a better compressor with only nominal non-audible loss.

[StingRay]

Originally Posted by Zetr0

@Thornam

what your target CPU for this project?

Originally Posted by Thorham

but I need something that will allow decompression without a high cpu load on a 50Mhz '030.

[Zetr0]

LOL, thanks StingRay!


But I rekon you just hacked that in there didin't you... come on admit it.... It wasnt there before you l33t coder you!!!!


/Zetr0 nips out to check the google cache

"i'l catch you one of these days y'know...!!" lol!!


okay, so the target machine has a maximum of 9MIPS processing, so say we use only half of that 4.5MIPS...

for a Delta/RLE compressed 16 bit stereo audio file?

[Thorham]

Originally Posted by Zetr0

whats your target CPU for this project?

In the end a 28Mhz '020 (Blizzard?) should be able to handle it, although I'm using a '030 at 50Mhz. Basically as low as possible.

Originally Posted by Zetr0

If you are looking at something 020'ish or lower - then huffman/delta RLE with a resizable buffer (pending on target) might be the only choice.

Something like that might already be good enough anyway.

Originally Posted by Zetr0

What are you hoping to achieve in terms of running CPU load / audio quality (bits) and compression ratio?

Audio: 14bit 28Khz stereo (current wavs are still 16bit, though).
Cpu load: As low as possible

For the compression ratio I want to fit 1.67 Giga bytes onto one CD. The music is looped (game music) and the rips I have actually include the looping as repeating data, this can be cut off, and looped in the software. This will get rid of quite some data, so the compression ratio doesn't have to be the best possible.

Originally Posted by Zetr0

As a thought you could use a a parser that removes/clips non-audible sounds from the audio file first and then encodes / compresses the audio file... although this is a lossy approach it will likey prove a better compressor with only nominal non-audible loss.

Although you're right, the rips are lossless and the downsampling (done with Sox) is already lossy. If it's not possible to fit all the music on one CD, then this will be an interesting alternative

[Zetr0]

@Thornham,

It sounds like a fun project, I enjoyed playing with delta's and some shuffle key techniques at Uni, ahh fun times =)

So, lets see a standard CD being 700MB, storing 1.67GB might be a little on the hard side to achive, (thats 60%+ compression rate)

Although I suspect that that these looped tracks a half the problem, how much data have you got without the loops?

[Thorham]

Originally Posted by Zetr0

Although I suspect that that these looped tracks a half the problem, how much data have you got without the loops?

I don't know, and I would have to listen to most of the 93 tracks to get the loop times, although the original wavs are from a tracked source (PSF) so the loops might be detectable with a simple freebasic program.

[absence]

Originally Posted by Thorham

For the compression ratio I want to fit 1.67 Giga bytes onto one CD. The music is looped (game music) and the rips I have actually include the looping as repeating data, this can be cut off, and looped in the software. This will get rid of quite some data, so the compression ratio doesn't have to be the best possible.

Good thing, as fitting 1.67 GB of data on a cd can be a tall order even for FLAC. How large is the uncompressed data when looping in software? If the repeating data is large enough, compression may not even be necessary. (Edit: Sorry, I was too quick and didn't notice you had already answered this question.)

If audio quality isn't a top priority, you can also improve the compression ratio of lossless algorithms by avoiding dithering and noise shaping when converting from 16 to 14 bits. The result is "uglier" quantisation noise (distortion instead of hissing), but it may not be noticable.

Also, does it really have to be lossless? I don't know if simpler frequency based codecs like MP2 or Musepack (both sound good at high bitrates) are too heavy for the target CPU, but there's also stuff like ADPCM, which was used extensively as a streaming music format on the previous generation of game consoles.

[Kalms]

ADPCM sounds reasonably well, is cheap to decompress, and gives you 4:1 compression ratio for 16bit samples. You should be able to replay 28khz stereo for 10-20% CPU on a 28mhz 030.

I've published a decompressor here: http://code.google.com/p/unitedstatesofamiga/

[Thorham]

Originally Posted by absence

Good thing, as fitting 1.67 GB of data on a cd can be a tall order even for FLAC. How large is the uncompressed data when looping in software? If the repeating data is large enough, compression may not even be necessary. (Edit: Sorry, I was too quick and didn't notice you had already answered this question.)

It's probably less than half of data.

Originally Posted by absence

If audio quality isn't a top priority, you can also improve the compression ratio of lossless algorithms by avoiding dithering and noise shaping when converting from 16 to 14 bits. The result is "uglier" quantisation noise (distortion instead of hissing), but it may not be noticable.

Sound quality has maximum priority

The data is still all 16 bit, because Sox, which I used for the high quality down sampling from 48Khz, doesn't seem to like dithering from 16 bit to 14 bit. I tried to do this, because it might have increased the sound quality.

Getting rid of the two unneeded bits will reduce the data to 1.47 Gigs, whis is better than 1.67 Gigs, and it shouldn't even be audible (or even improve the audio somehat!), because when replaying on the Amiga, I think bits 6 and 7 will overlap with bits 8 and 9.

Originally Posted by absence

Also, does it really have to be lossless? I don't know if simpler frequency based codecs like MP2 or Musepack (both sound good at high bitrates) are too heavy for the target CPU, but there's also stuff like ADPCM, which was used extensively as a streaming music format on the previous generation of game consoles.

Lossyness is only acceptable if there's truely no other way. Lossy encoding is therefore a last resort.

Originally Posted by Kalms

ADPCM sounds reasonably well, is cheap to decompress, and gives you 4:1 compression ratio for 16bit samples. You should be able to replay 28khz stereo for 10-20% CPU on a 28mhz 030.

I've published a decompressor here: http://code.google.com/p/unitedstatesofamiga/

Thanks for the code However, from 'reasonably well' and the 4:1 compression I take it that ADPCM is lossy. Lossy is certainly interesting, but only if there's no other way.

[Thorham]

I've been playing around with this for a while and I'm able to compress to about 75%, without any Huffman or RLE encoding (those will be added if necessary). Anyone know how to improve it? Here's what I'm doing now:

1. Calculate mid/side: mid=(left+right)/2 side=mid-left (may look strange, but these steps can be reversed without any loss)
2. Calculate difference between previous sample and current.
3. Store difference sign separately and convert difference to distance.
4. Store the distances with a very simple variable length code (add two extra bits to let the decoder know a distance value is 4, 8, 12 or 16 bits large).

This is of course a very simple method that can easily be expanded. Any ideas?

Do you really need lossless? If so, have you considered applying a haar wavelet to the audio. It may sound complex, but it is not. it is merely the average of each byte pair followed by the difference which recreates the byte pair. This is iterated until you have an average followed by the fluctuations. Then pack via the Huffman, lz methods.

Near lossless can be achieved at guaranteed 2:1 ratio with barely any audial loss via VQ encoding byte pairs. Read up on vector quantization. 256 "optimum" byte pairs are created (512 byte table) and each byte lookup converts to a byte pair. Very fast decode.

[Nekoniaow]

Originally Posted by Thorham

I've been playing around with this for a while and I'm able to compress to about 75%, without any Huffman or RLE encoding (those will be added if necessary). Anyone know how to improve it? Here's what I'm doing now:

1. Calculate mid/side: mid=(left+right)/2 side=mid-left (may look strange, but these steps can be reversed without any loss)
2. Calculate difference between previous sample and current.
3. Store difference sign separately and convert difference to distance.
4. Store the distances with a very simple variable length code (add two extra bits to let the decoder know a distance value is 4, 8, 12 or 16 bits large).

This is of course a very simple method that can easily be expanded. Any ideas?

By 75% do you mean a 4:1 compression ratio or 4:3? I understood 4:3 but I'd rather be sure.
(The best codecs barely reach 50% so 4:3 it is. )

Also why do you store the sign bit separately? If you Huffman encode the values then it does not matter that they contain a sign bit and on the contrary it seems very unlikely that you will be able to separately compress the series of sign bits efficiently given their likely random nature.

[Mrs Beanbag]

this is interesting...

what i have done recently is to use a Lanczos filter to interpolate between the even bytes, then take the difference between the interpolated odd bytes and the real data. Store the even bytes and odd byte error separately, the odd bytes will be relatively small for "nice" sample data and will compress easily with any off-the-shelf packing algorithm or a custom LZ variant.

[Photon]

Heh, thread necromancing Since 2010 I did Nibbler, which is good at sample data and it can uniquely do 28kHz 4 channels in real time... bit of work to convert it to 4x interleaved streaming but if mono is ok it should be doable to just pop bytes out to a buffer, with time to spare. (This on 68000 now. Forever and for always. )

In lossless 8-bit audio, you're looking at 25-50% for sample data, unless you do something special. Delta+pure Huffman seems promising, why not, if you can stream it fast enough.

Lossy is where size gets interesting, basically though I think on 68000, considering you might lose the DMA advantage and 8-bit sounds bad enough as it is it's a bit wasting resources unless you can do something interesting with it like modulation, speech synth or whatever cos you get parameters to play with.

[NorthWay]

Can someone humour me with something I have been wondering for a while:
If you compress a sample with a lossy algorithm, what kind of compression could you get out of a delta between the original and the decompressed lossy data?

I.e. lossy compressed data plus compressed delta data - is it possible to get some better compression?