Does anyone know of any decent audio codec that has an efficient and fast encoder. I'd like to compress 8 bit PCM maybe to 25% or whatever is doable without too much loss of quality.

fast encoder or fast decoder?

Differential (or Delta) pulse-code modulation (DPCM) encodes the PCM values as differences between the current and the previous value. For audio this type of encoding reduces the number of bits required per sample by about 25% compared to PCM.
Adaptive DPCM (ADPCM) is a variant of DPCM that varies the size of the quantization step, to allow further reduction of the required bandwidth for a given signal-to-noise ratio.

[edit]
Actually, instead of coding the difference between the current and the previous sample
we can do the difference between the current and the prediction of the currect sample
based on some past samples. This can be more accurate but needs more CPU

DPCM is exactly what the polyscc is doing, each channel is
the difference between the sample to be played at time T
and the value being played at time T-1
the only missing part is the bit reduction of the differences
Maybe, we could exploit this somehow, but expect more noise

I mean fast decoder of course. A little typo I beleive It would indeed be quite nice to compress the audio a bit. It doesn't need to be lossless compression either but it can't be too lossy either since its only 8 bit PCM.

I once wrote a sample crunch algo for my old Digitrakker (MS-DOS).
IIRC it crunched 8bit samples down to about 66% (average).
Both the crunch and decrunch algorythm were quite simple. It was based on the delta values (of course) and a bit stream, containing only a few bits for small delta values (which should appear more often) and more bits for bigger delta values. So it was a little bit like the huffman stuff, but the "tree" was the same for every sample.
If you are interested, I can post it here. Do you need to decode in realtime (while playing the sample)?

Thanks Prodatron. I actually did some experiments yesterday with huffman like encoding of deltas too. I didn't find any good tree though (I got around 80% of original size) so if you want to post your algorithm it would be great.

You can find a ADPCM encoder and decoder in following archive:
http://www.msxarchive.nl/pub/msx/programming/c/sources/xadpcm.tgz

It is written in C, but should be straightforward to port back to assembler (I ported it from assembler)

Thanks alex

Hm, I reviewed it again, and now I am not sure, if it would really reach something like 66%.
Anyway here it is:

A packed byte is stored in the following form (inside the bitstream, read bits from left to right):

smX..X
s = sign; if s=1 the decoded byte will be XORed with 255 at the end.
m = mode;
- if m=1: three bits are following, containing the value for the byte (s1XXX, where XXX is the value)
- if m=0: the byte is encoded in the following form: s0..1XXXX => byte = <xxxx> + (number of <0>-bits between s and 1) * 16 - 8

Here is a pseudo code for the decoding:

function decodeOneDeltaByte
{
    sign = readBits(1);
    mode = readBits(1);
    
    if (mode == 1)
        byte = readBits(3);
    else
    {
        byte = -8;
        while (mode == 0)
        {
            byte += 16;
            mode = readBits(1);
        }
        byte += readBits(4);
    }
    
    if (sign == 1)
        byte = byte ^ 255;

    return byte;
}

The algo assumes, that most delta values fit in 3 bits + one sign bit (-> -8 - +7). This should be ok for samples with a high resolution (44KHz or so), but maybe not for samples used for the MSX?
In any case, today I think that a specialised implementation of the ADPCM algo could be much better and still easy to implement (will have a look at Alex source code).

Looks similar to the one I did. I also had a sign bit (except I did neg instead of xor FF) but then I did a deeper tree, something like:

S0XXXX
S100XX
S101XXX
S110XXXXX
S111XXXXXXXX

I'll take a look at alex ADPCM code and see if that one is better.

I guess a special ADPCM encoder could be done in an effective and simple way like this:
In front of each stream of values with the same bit depth:
- Bit depth of the following delta values (3 bit)
- Number of delta values stored with this bit depth (5 bits or so)
Then you don't have this overhead for each value inside the bitstream.
But it all depends on the practice :-)

One possibility is to store the LOG of the difference between samples, using a fixed bitrate. I wrote a program on the Amiga that plays back files encoded with 5-bits per sample (with the original and the output PCM being 16-bit) and it could work at 22KHz stereo on the plain 7MHz 68000. With an 8-bit input you could encode it with 4-bits which is only 50% compression ratio of course but at least it would be fast to decode.

for example if you have the following signed 8-bit PCM samples
0,15,68,9,-40,-45,-26,4
the encoding is based on a 16-element table
0,1,2,4,8,16,32,64,-1,-2,-4,-8,-16,-32,-64,-128
so those 8-bit samples would be encoded with 4-bit values like this
5,7,14,14,3,5,6
when decoded the waveform follows the original approximately (good enough for audio, just with a slight addition of noise)
0,16,80,16,-48,-44,-28,4

I didn't do NEG but CPL, because NEG would give you the same result for 0, so you loose one possible value.
Btw, I don't understand the sense of S100XX and S101XXX, if you already have S0XXXX (less or the same amount of bits)?
S111XXXXXXXX also doesn't make sense, as you need only 7bits, if you have an additional sign
But it could be a good idea to limit the maximum amount of bits like in your methode.

My ADPCM encoder/decoder is compatible with the ADPCM of the MSX Audio. It reduces the data size to 4 bits per sample. I originally wrote it for SME3. I'll dig up the Z80 assembly version of the routines if you are interested.

That would be great Alex. Btw, do you have the format description of the MSX Audio ADPCM?