Easy Analog Data Compression

Listing 1: Partial listing of the encoder/compressor encoder.c

static iBitWidthOfCode = 6; 
static INT16 iXcode = 0; 
static int iXbitsTaken = 0; /* that many bits of iXcode are valid */

static const INT16 piABSCODE[17] = 
{
    +0x0000, +0x0001, +0x0003, +0x0007, +0x000F, +0x001F, +0x003F, +0x007F,
    +0x00FF, +0x01FF, +0x03FF, +0x07FF, +0x0FFF, +0x1FFF, +0x3FFF, +0x7FFF,
    (INT16) +0xFFFF
};

static const INT16 piOVFLCODE[16] = 
{
    +0x0000, +0x0000, +0x0002, +0x0006, +0x000E, +0x001E, +0x003E, +0x007E,
    +0x00FE, +0x01FE, +0x03FE, +0x07FE, +0x0FFE, +0x1FFE, +0x3FFE, +0x7FFE
};

static const INT16 piALIGNCODE[16] = 
{
    -0x0001, -0x0002, -0x0004, -0x0008, -0x0010, -0x0020, -0x0040, -0x0080,
    -0x0100, -0x0200, -0x0400, -0x0800, -0x1000, -0x2000, -0x4000, -0x8000
};

static INT32 piLastSamplesDiv3[3] = {0, 0, 0};


void writeCode(int iSample)
{
    flash_write((WORD) iSample);
}


void storeX(INT16 iCode)
{
    int iEmpty = 16 - iXbitsTaken;  /* available bits in the word      */

    /* storeX() expects a iBitWidthOfCode-bit value; 
     * however, negative numbers are sign extended up to the 16-bit MSB;
     * this sign extension must thus be removed */
    iCode &= piABSCODE[iBitWidthOfCode];

    if (iEmpty > iBitWidthOfCode)  /* more bits available than needed? */
    {                              /* yes: write entire bit pattern    */
        iCode <<= iXbitsTaken;     /* position new sub-word correctly  */
        iXcode |= iCode;           /* keep it to -or- w. next pattern  */
        iXbitsTaken += iBitWidthOfCode;
    } 
    else if (iEmpty == iBitWidthOfCode) /* if exactly as much bits are */
    {                                   /* available as needed, then   */
        iCode <<= iXbitsTaken;          /* position new sub-word,      */
        iCode |= iXcode;                /* -or- new sample to kept val */
        iXcode = 0x0000;                /* reset the kept values       */ 
        iXbitsTaken = 0;
        writeCode(iCode);               /* store new sample + kept val.*/
    }
    else
    {   
        /* we have to split the bit pattern into two words */
        register WORD wTemp = iCode;     /* make a copy                */
        iCode <<= iXbitsTaken;           /* position new sub-word      */
        iCode |= iXcode;                 /* create the 1st part        */
        wTemp >>= iEmpty;                /* position part two          */
        iXcode = wTemp;                  /* and keep it for next write */
        iXbitsTaken = iBitWidthOfCode - iEmpty;
        writeCode(iCode);                /* store 1st part             */ 
    }
}


void flushX()
{
    /* Check if the buffer of storeX() is not empty. */ 
    if (iXbitsTaken != 0) 
    {
        /* record that the next sample that follows will be aligned at 
         * WORD boundaries */
        storeX(piALIGNCODE[iBitWidthOfCode - 1]);  

        /* check if the ALIGNCODE already managed the alignment */
        if (iXbitsTaken != 0) 
        {
            /* if not, then flush the buffer and enforce the alignment */
            writeCode(iXcode);
        }
        iXcode = 0;
        iXbitsTaken = 0;
    }
} /* flushX() */


void encoder_flush()
{
    flushX();
}


void storeDelta16(INT16 iDeltaCode)
{
    static iSamples2MSBidentical = 0;

    if ((iDeltaCode >= piOVFLCODE[iBitWidthOfCode - 1]) ||
        (iDeltaCode <= piALIGNCODE[iBitWidthOfCode - 1]))
    {
        /* overflow/underflow: store OVFLCODE and increase bit width */
        storeX(piOVFLCODE[iBitWidthOfCode - 1]); 
        ++iBitWidthOfCode;
        assert(iBitWidthOfCode < 17);
        iSamples2MSBidentical = 0;
        storeDelta16(iDeltaCode);  /* retry with incr. width */
    }
    else
    {
        int iMaxBitMask = 3 << (iBitWidthOfCode - 2);
        int iDeltaBitWidthAfterStoring = 0;

        if ((iDeltaCode & iMaxBitMask) == 0x0000 || 
            (iDeltaCode & iMaxBitMask) == iMaxBitMask)
        {
            /* the two MSBits of iSample are identical */
            iSamples2MSBidentical++;
            if ((iSamples2MSBidentical == BIT_REDUCTION_LENGTH) &&
                (iBitWidthOfCode > MIN_BIT_WIDTH))  
            {
                /* already the BIT_REDUCTION_LENGTH-th sample where
                 * MSBit is not in use --> reduce the code width */
                iDeltaBitWidthAfterStoring = -1; 
                iSamples2MSBidentical = 0;
            }
        }
        else
        {
            iSamples2MSBidentical = 0;
        }
        storeX(iDeltaCode);
        iBitWidthOfCode += iDeltaBitWidthAfterStoring;
    }
} /* storeDelta16() */


void encoder_storeADEPT(INT16 iSample)
{  
    static BOOL bFirstValue = TRUE; /* start-up needed */
    INT32 iCodedSample;             /* the delta code  */

    /* estimate the value x'(t) for iSample out of the last 
     * iSamples x(t-1), x(t-2), x(t-3) with the formula 
     * x'(t) = -2/3*x(t-3) + 1/3*x(t-2) + 4/3*x(t-1).
     * This value x'(t) is taken as basis for the delta encoding */
    INT32 iPrediction;                   /* linear extrapolation */

    iPrediction = 4 * piLastSamplesDiv3[2] + 
                  piLastSamplesDiv3[1] - 
                  2 * piLastSamplesDiv3[0];

    iCodedSample = iSample - iPrediction;            /* delta encoding */
    piLastSamplesDiv3[0] = piLastSamplesDiv3[1];
    piLastSamplesDiv3[1] = piLastSamplesDiv3[2];
    piLastSamplesDiv3[2] = iSample/3;  /* div here to prevent overflow */

    if ((iCodedSample >= piOVFLCODE[15]) ||
        (iCodedSample <= piALIGNCODE[15]) ||
        (bFirstValue))
    {
        /* signal that a 32-bit absolute value follows */
        storeX(piABSCODE[iBitWidthOfCode - 1]); 

        /* check alignment; if not aligned, 
         * flush the remaining bits of the buffer */
        if (iXbitsTaken != 0) 
        {
            writeCode(iXcode);
            iXbitsTaken = 0;
            iXcode = 0x0000;
        }

        /* reset delta encoding and store the absolute value */
        piLastSamplesDiv3[0] = iSample/3; 
        piLastSamplesDiv3[1] = iSample/3; 
        piLastSamplesDiv3[2] = iSample/3; 
        writeCode(iSample);
        bFirstValue = FALSE;
    }
    else
    {
        storeDelta16((INT16) iCodedSample);
    }
}