Waveform Compressor

It is possible to compress 16-bit waveform data by 25% using Delta Compression. When the waveform changes gracefully, each 16-bits can be represented by 4-bits of metadata plus 8-bits of data.

What is Delta Comp

Delta Compression is a simple technique that saves a byte of meta data and zero or more data bytes for each pair of 16-bit words in the source.

Why Delta Comp

Lossless algorithms can be found by google:wiki rle which highlights run-length encoding and others. Some are good for text, some are special for fascimile and video, but all increase complexity. Delta Comp is specific to single-channel waveform data.

What is Delta Comp Metadata

Delta Comp packs the meta information for two 16-bit words into one byte. The first nibble is for word1, the second is for word 2. Here is an enumeration:-

// metadata status to track word deltas
typedef enum {
 eMetaEqual,			///< 00000000
 eMetaPlusOne,		///< 00000001
 eMetaPlusTwo,		///< 00000010
 eMetaPlusThree,		///< 00000011 NA
 eMetaMinusOne,		///< 00000100
 eMetaMinusTwo,		///< 00000101
 eMetaMinusThree,		///< 00000110 NA
 eMetaError			///< 00000110 ?NA

}META_CODES_E;

Three meta bits are allocated, but not every combination is needed. The fourth bit might be used in future to add other routines such as RLE.

Delta Comp In A Nutshell

Delta Comp is most effective when each word of data differs from the previous by less than 256. If the sensor saturates or is flat, it is even better since only meta bytes are stored. A dirty sensor would store the original data plus meta bytes. Random data would certainly be expanded.

Here is the programming sequence..

  • Copy the first Word as is without change
  • Start looping through the remaining pairs of words.
  • store meta1 and meta2 in the same byte.
  • store delta of first word ( 0, 1, or 2 bytes )
  • store delta of second word ( 0, 1, or 2 bytes )
  • repeat until the data is consummed and packed

Here is some sample data:-

hello world; size short= 2 bytes
[SRC-I:  0 D: 245]
[SRC-I:  1 D: 250]
[SRC-I:  2 D: 255]
[SRC-I:  3 D: 260]
[SRC-I:  4 D: 265]
[SRC-I:  5 D: 260]
[SRC-I:  6 D: 255]
[SRC-I:  7 D: 250]
[SRC-I:  8 D: 245]
[I:000 D:000 H:00]
[I:001 D:245 H:f5]
[I:002 D:017 H:11]
[I:003 D:005 H:05]
[I:004 D:005 H:05]
[I:005 D:017 H:11]
[I:006 D:005 H:05]
[I:007 D:005 H:05]
[I:008 D:068 H:44]
[I:009 D:005 H:05]
[I:010 D:005 H:05]
[I:011 D:068 H:44]
[I:012 D:005 H:05]
[I:013 D:005 H:05]
[TEST-I:  0 H:245]
[TEST-I:  1 H:250]
[TEST-I:  2 H:255]
[TEST-I:  3 H:260]
[TEST-I:  4 H:265]
[TEST-I:  5 H:260]
[TEST-I:  6 H:255]
[TEST-I:  7 H:250]
[TEST-I:  8 H:245]
Number words = 9
Number output bytes = 14

What Is The Source Code

#include <stdlib.h>
#include <stdio.h>
// metadata status to track word deltas
typedef enum {
 eMetaEqual,			///< 00000000
 eMetaPlusOne,		///< 00000001
 eMetaPlusTwo,		///< 00000010
 eMetaPlusThree,		///< 00000011 NA
 eMetaMinusOne,		///< 00000100
 eMetaMinusTwo,		///< 00000101
 eMetaMinusThree,		///< 00000110 NA
 eMetaError			///< 00000110 ?NA
}META_CODES_E;
enum { 
 eNUM_WORDS = 9
};
typedef unsigned short ushort;
typedef unsigned char  uchar;
/// data shared between routines
typedef struct{
 int stepRaw;
 int stepComp; 
 int stepCompSave;
 ushort prev;			///< previous word
 ushort meta[2];		///< word status
}META_T;
static ushort rawData[eNUM_WORDS];	///< raw
static uchar comp[eNUM_WORDS*4];	///< encoded
static ushort testData[eNUM_WORDS];	///< from decode
static META_T meta_t;		///< program info
void encode( META_T *pgm );
void decode( META_T *pgm );
ushort getCompByte( META_T *pgm);
ushort getCompWord( META_T *pgm );
void setOutByte( META_T *pgm, uchar b );
void packDelta( META_T *pgm, ushort word, int wi);
ushort unpackDelta( META_T *pgm, int wi );
/// 1. setup some static text data
/// 2. encode
/// 3. decode
/// 4. check space saved and that decode result = initial data
/// 
int main( int argc, char *argv[] )
{
 META_T *pgm = &meta_t;
 const int bottom=245;
 int i, dir=1,step;
 printf("hello world; size short= %d bytes\n", sizeof(short));
 for( i=0; i < eNUM_WORDS; i++){
    if( i == 0 ){
 step=bottom;
    }
    rawData[i] = step;
    printf("[SRC-I:%3d D: %d]\n",i,rawData[i]);
    if( i >= eNUM_WORDS / 2) dir = -1;
    if( dir == 1 ){
 step += 5;
    }
    else{
 step -= 5;
    }
 }
 encode(pgm);
 pgm->stepCompSave = pgm->stepComp;
 decode(pgm);
 printf("\nNumber words = %d\n", eNUM_WORDS);
 printf("Number output bytes = %d\n", pgm->stepComp);
 return 0;
}
ushort getCompByte( META_T *pgm)
{
 ushort w = comp[pgm->stepComp++] & 0xff;
 return w;
}
ushort getCompWord( META_T *pgm )
{
  ushort b1 = comp[pgm->stepComp++] & 0xff;
  ushort b2 = comp[pgm->stepComp++] & 0xff;
 ushort w = (b1 << 8) | b2;
 return w;
}
void setOutByte( META_T *pgm, uchar b )
{
 comp[pgm->stepComp++] = b & 0xff;
 if( pgm->stepComp >= (eNUM_WORDS*4) ){
    puts("too many out bytes");
 }
} 
void setOutWord( META_T *pgm, ushort w )
{
 comp[pgm->stepComp++] = (w & 0xf0)>>8;
 if( pgm->stepComp >= (eNUM_WORDS*4) ){
    puts("too many out bytes");
 }
 comp[pgm->stepComp++] = (w & 0xff);
 if( pgm->stepComp >= (eNUM_WORDS*4) ){
    puts("too many out bytes");
 }
}
void packDelta( META_T *pgm, ushort word, int wi)
{
 ushort diff,prev = pgm->prev;
 pgm->prev = word;
 if( word == prev ){
    pgm->meta[wi] = eMetaEqual;
    return;
 }
 if( word > prev ){
    diff = word - prev;
    if( diff < 0x100 ){
 pgm->meta[wi] = eMetaPlusOne;
 setOutByte(pgm, diff );
    }
    else{
 pgm->meta[wi] = eMetaPlusTwo;
 //setOutByte( pgm, ((diff >> 8) & 0xff)); 
 //setOutByte( pgm, (diff & 0xff)); 
 setOutWord( pgm, diff); 
    }
    return;
 }
 // word must be < previous
 diff = prev - word;
 if( diff < 0x100 ){
    pgm->meta[wi] = eMetaMinusOne;
    setOutByte( pgm, diff );
 }
 else{
    pgm->meta[wi] = eMetaMinusTwo;
    //setOutByte( pgm, ((diff >> 8) & 0xff)); 
    //setOutByte( pgm, (diff & 0xff)); 
    setOutWord( pgm, diff); 
 }
 return;
}
void encode( META_T *pgm )
{
 ushort w1,w2;
 uchar uc;
 int metaIndex;
 // copy the first word to the output as is. use it as a seed for
 // finding the deltas in the following loop.
 w1 = pgm->prev = rawData[pgm->stepRaw++];
 setOutWord( pgm, w1); 
 while( pgm->stepRaw < eNUM_WORDS ){
    w1 = rawData[pgm->stepRaw++];
    if( pgm->stepRaw >= eNUM_WORDS ) {
 puts("adjust array size by 1");
 break;
    }
    // allow deltas to be set first. save space for the metadata
    // which will precede a variable number of delta data bytes.
    metaIndex = pgm->stepComp++;
    packDelta(pgm, w1, 0);
    w2 = rawData[pgm->stepRaw++];
    packDelta(pgm,w2,1);
    uc = pgm->meta[0]<<4 | pgm->meta[1];
    comp[metaIndex] = uc;	// fill in metadata      
 }
}
ushort unpackDelta( META_T *pgm, int wi )
{
 ushort w1=0;
 switch(pgm->meta[wi]){
 case eMetaPlusOne:
    w1 =  pgm->prev + getCompByte(pgm); 
    break;
 case eMetaPlusTwo:
    w1 =  pgm->prev + getCompWord(pgm);
    break;
 case eMetaMinusOne:
    w1 =  pgm->prev - getCompByte(pgm); 
    break;
 case eMetaMinusTwo:
    w1 =  pgm->prev - getCompWord(pgm);
    break;
 case eMetaEqual:
    w1 = pgm->prev;
    break;
 default:
    puts("unpackDelta: invalid meta");
    break;
 }
 return w1;
}
void decode( META_T *pgm )
{
 int i,stepTest;
 ushort w,m;
 pgm->stepCompSave = pgm->stepComp;
 pgm->stepComp=0;
 w = getCompWord(pgm);   // take first word as is
 stepTest=0;
 testData[stepTest++] = w;
 pgm->prev = w;
 for( i=0; i < pgm->stepCompSave; i++ ){
    m = comp[i] & 0xff;
    printf("[I:%03d D:%03d H:%02x]\n",i, m, m);
 }
 while( pgm->stepComp < pgm->stepCompSave ){
    m = getCompByte(pgm);	// metadata
    pgm->meta[0] = (m & 0xf0)>>4;
    pgm->meta[1] = (m & 0xf);
    w = unpackDelta(pgm,0);
    testData[stepTest++] = w;
    pgm->prev = w;
    w = unpackDelta(pgm,1);
    testData[stepTest++] = w;
    pgm->prev = w;
 }
 for( i=0; i < stepTest; i++ ){
    printf("[TEST-I:%3d H:%d]\n",i, testData[i]);
 }
}
// main.c

Navigation
Personal Tools