Algorithm Alley
by Tim Kientzle


Example 1: 

static const int _stepSizeTable[89] = {
   7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 21, 23, 25, 28, 31, 34,
   37, 41, 45, 50, 55, 60, 66, 73, 80, 88, 97, 107, 118, 130, 143,
   157, 173, 190, 209, 230, 253, 279, 307, 337, 371, 408, 449, 494,
   544, 598, 658, 724, 796, 876, 963, 1060, 1166, 1282, 1411, 1552,
   1707, 1878, 2066, 2272, 2499, 2749, 3024, 3327, 3660, 4026,
   4428, 4871, 5358, 5894, 6484, 7132, 7845, 8630, 9493, 10442,
   11487, 12635, 13899, 15289, 16818, 18500, 20350, 22385, 24623,
   27086, 29794, 32767
};


Example 2: 
static const int indexAdjustTable[16] = {
   -1, -1, -1, -1,  // +0 - +3, decrease the step size
    2, 4, 6, 8,     // +4 - +7, increase the step size
   -1, -1, -1, -1,  // -0 - -3, decrease the step size
    2, 4, 6, 8,     // -4 - -7, increase the step size
};

Listing One
short ImaAdpcmDecode(unsigned char deltaCode, ImaState &state) {
   // Get the current step size
   int step = _stepSizeTable[state.index];
   // Construct the difference by scaling the current step size
   // This is approximately: difference = (deltaCode+.5)*step/4
   int difference = step>>3;
   if ( deltaCode & 1 ) difference += step>>2;
   if ( deltaCode & 2 ) difference += step>>1;
   if ( deltaCode & 4 ) difference += step;
   if ( deltaCode & 8 ) difference = -difference;
   // Build the new sample
   state.previousValue += difference;
   if (state.previousValue > 32767) state.previousValue = 32767;
   else if (state.previousValue < -32768) state.previousValue = -32768;

   // Update the step for the next sample
   state.index += indexAdjustTable[deltaCode];
   if (state.index < 0) state.index = 0;
   else if (state.index > 88) state.index = 88;

   return state.previousValue;
}


Listing Two 
unsigned char ImaAdpcmEncode(short sample, ImaState &state) {
   int diff = sample - state.previousValue;
   int step = _stepSizeTable[state.index];
   int deltaCode = 0;

   // Set sign bit
   if (diff < 0) { deltaCode = 8; diff = -diff; }

   // This is essentially deltaCode = (diff<<2)/step,
   // except the roundoff is handled differently.
   if ( diff >= step ) {  deltaCode |= 4;  diff -= step;  }
   step >>= 1;
   if ( diff >= step ) {  deltaCode |= 2;  diff -= step;  }
   step >>= 1;
   if ( diff >= step ) {  deltaCode |= 1;  diff -= step;  }

   ImaAdpcmDecode(deltaCode,state);  // update state
   return deltaCode;
}

#ifndef IMAADPCM_H_INCLUDED
#define IMAADPCM_H_INCLUDED

struct ImaState {
   int index;    // Index into step size table
   int previousValue; // Most recent sample value
};
// Decode/Encode a single sample and update state
short ImaAdpcmDecode(unsigned char deltaCode, ImaState &);
unsigned char ImaAdpcmEncode(short sample, ImaState &);
// Microsoft-compatible decoder
class DecompressImaAdpcmMs {
private:
   int  _channels;
   short *_samples[2];  // Left and right sample buffers
   short *_samplePtr[2]; // Pointers to current samples
   size_t   _samplesRemaining; // Samples remaining in each channel
   size_t   _samplesPerPacket; // Total samples per packet
public:
   DecompressImaAdpcmMs(int packetLength, int channels);
   ~DecompressImaAdpcmMs();
   size_t GetSamples(short *outBuff, size_t len);
private:
   unsigned char *_packet;   // Temporary buffer for packets
   size_t   _bytesPerPacket; // Size of a packet
   size_t  NextPacket();
   size_t ReadBytes(void *buffer, size_t request);
};
// Apple-compatible decoder
class DecompressImaAdpcmApple {
private:
   int _channels;
   ImaState _state[2];
   short _samples[2][64];
   short *_samplePtr[2];
   size_t   _samplesRemaining;
   size_t  NextPacket(short *sampleBuffer, ImaState &state);
public:
   DecompressImaAdpcmApple(int channels);
   size_t GetSamples(short *outBuff, size_t len);
   size_t ReadBytes(void *buffer, size_t request);
};
#endif

Listing Four
size_t  DecompressImaAdpcmApple::NextPacket(short *sampleBuffer,
                                           ImaState &state) {
   unsigned char _packet[34];
   // Pull in the packet and check the header
   size_t bytesRead = ReadBytes(_packet,34);
   if (bytesRead < 34) return 0;

   // Check the decompressor state
   state.index = _packet[1] & 0x7f;
   if (state.index > 88) {
      cerr << "Synchronization error.\n";
      exit(1);
   }
   // Recover upper nine bits of last sample
   short lastSample = 
      (static_cast<signed char>(_packet[0])*0x100 + 
       static_cast<signed char>(_packet[1])) & 0xff80;
   // If ours doesn't match, reset to the value in the file
   if ((state.previousValue & 0xff80) != lastSample)
      state.previousValue = lastSample;
   // Decompress nybbles
   for(int i=0; i<32; i++) {
      *sampleBuffer++ = ImaAdpcmDecode(_packet[i+2] & 0xf, state);
      *sampleBuffer++ = ImaAdpcmDecode((_packet[i+2]>>4) & 0xf, state);
   }
   return 64;
};

1