QI and MQ Coder: First real-life experiences
- From: Thomas Richter <thor@xxxxxxxxxxxxxxxxx>
- Date: Sat, 28 Jan 2006 23:30:20 +0100
Hi group,
concerning the ongoing discussion of the QI coder vs. the arithmetic coding, I played now a bit with a real life example, namely audio compression.
The test application is a mildly drilled-up QI coder source from 1st Works, as found on their web-page, ported for Unix (thanks Jasen Betts!) and equipped with a very simplistic audio codec front-end, consisting of a linear predictor and a bitplane context modelling. QI was used in the largest possible block size (16K bits), MQ coding with its default context update tables. The code for QI/MQ is found below for anyone who feels like reproducing my results; *NOTE THAT I CANNOT GRANT YOU THE RIGHTS TO USE THESE CODES FOR ANYTHING BUT DEMONSTRATION/RESEARCH*.
Both codes were compiled with gcc-3.4.4, -O2 optimization for QI, default options for MQ (nothing but default optimization with -O). Codes read from stdin, create data on stdout. I didn't try to speedup the IO by blocking or other nice tricks on either code. Test data was the first movement of Brahms 1st Symphony, conducted by Leonard Bernstein, Wiener Phillharmoniker, Deutsche Gramophon recording. It is an approximately 15MB large audio track, encoded as a 16bpp wav file. That was the topmost on the stack of CDs here, no special reason to pick it. The system is a 1.4Ghz Athlon XP machine running Debian 3.1 "Sarge" with 512MB main memory. Thus, coding results are possibly not representative, I just had to make a test.
Some results:
1) It is pretty hard to get the data into the right shape for QI. This also implies that it is nearly impossible - or at least, for me, right now, pretty hard - to get it into a really decent/usable context modelling. Thus, something very simple had to be set up. Creating a simple context model for MQ was a "piece of cake" on the other hand. See also below.
2) Running time:
thor@skywise:~/src/qic> time QI cc </tmp/track1.wav >/tmp/track1.qi
real 4m12.484s user 4m3.640s sys 0m4.340s
thor@skywise:~/src/audiocompress> time arthdeco_wide </tmp/track1.wav >/tmp/track1.qm
real 2m25.064s user 2m4.880s sys 0m1.860s
Thus, MQ shows a clear advantage here (about a factor of two). The reason is possibly to a major degree due to the difficulty to get the data into the right shape for QI, thus a good deal of time is spend in just juggling bits. This is overall running time.
3) Memory footprint:
The MQ coder requires almost no memory except its tables, the code doesn't allocate memory at all. QI eats with 16K blocks about half of my system's main memory (something along 300MB estimated).
4) Coding efficiency:
-rw-r--r-- 1 thor thor 148708208 2006-01-28 21:35 track1.mq -rw-r--r-- 1 thor thor 159764576 2006-01-28 22:49 track1.qi
Topmost is the MQ coder output, bottommost the QI coder output. MQ shows a clear advantage here, though the comparison is not quite fair. I added a simpler, slightly more sophisticated context model to the MQ coder. I haven't been able to add a similar context model to the QI coder. Thus, I removed the more advanced context model from the MQ coder and played the game again, the result is as such for the MQ coder:
rw-r--r-- 1 thor thor 154397815 2006-01-28 23:11 track1.qm
This above is the MQ coder with the *identical* context model to the QI, thus even here it encodes better. Wierd?
Node that all these tests are pretty much preliminary, thus anyone is invited to try his/hers luck to improve the code and play with it.
5) Efficiency analysis: I think the current optimality analysis might have missed a term: The QI coder requires the side-information of how many LPS-bits have been encoded, and whether the LPS is 1 or 0. In the above coding analysis, this is makes up about 200K, thus even removing this side-information (thus making the stream non-decodable) does not yet make QI better than MQ. Node also that I had byte-padding at block-boundaries. This is included in the 200K estimated: I wrote an additional 2 bytes per block, and came out with 200K more.
6) If anyone feels like reproducing, please add the following code to QI, and drill up the main program apropriately to use 16K block sizes, and bypass the random-bit-test here:
/* snip */
/*
** Push the indicated bit buffer to stdout.
** Arguments are the bit buffer, the total number of bits
** in this buffer and the number of one-bits, as required for
** QI. This is not yet fully optimal as the encoder gets
** flushed to byte-boundaries for simplicity reasons.
*/
void push_buffer(unsigned char *bits,int totalbits,int onebits)
{
int exchange = 0;
int code = 0;
unsigned char outbuffer[2048+4];
/*
** Encode the number of bits. Two bytes suffer. Also encode
** whether we have the exchange case with more one-bits than
** zero bits
*/
if (onebits > (totalbits >> 1)) {
int j;
exchange = 1; /* conditional exchange */
for(j = 0;j < ((totalbits + 7) >> 3);j++) {
bits[j] ^= 0xff;
}
onebits = totalbits - onebits;
}
if (totalbits < (2048 << 3)) {
putchar((totalbits >> 8) | (exchange << 7));
putchar(totalbits & 0xff);
putchar((exchange << 7) | (onebits >> 8));
putchar(onebits & 0xff);
} else {
/* full buffer case. Avoid the overhead */
putchar((exchange << 7) | (1<<6) | (onebits >> 8));
putchar(onebits & 0xff);
}
memset(outbuffer,0,sizeof(outbuffer));
/* Get the number of output bits.
** Need not to be encoded, the decoder can reconstruct
** this from the number of one-bits. This is the number
** of bytes to write. Could be made better by not enforcing
** byte-padding here.
** Unfortunately, QI doesn't seem to be able to handle an
** all-zero buffer. Since this is encoded in the above with
** the number of one-bits, bypass in that case.
*/
code = (bt.len[onebits] + 7) >> 3;
/*
** Run now the encoder
*/
if (onebits) {
qiEnc(bits,0,onebits,outbuffer,0);
fwrite(outbuffer,1,code,stdout);
}
}/*
** Simple and stupid encoding for audio compression
*/
void compress(void)
{
unsigned char bitbuffer[16][2048];
unsigned int bitpos[16];
unsigned int bitcnt[16];
unsigned int last = 0,lastlast = 0;
int pred,j;memset(bitpos,0,sizeof(bitpos)); memset(bitcnt,0,sizeof(bitcnt));
do {
int c1,c2;
// Try to fill the input buffer by continuously reading from the input stream.
c1 = getchar();
c2 = getchar();
if (c2 >= 0) {
unsigned int c = ((c1 << 8) | c2);
unsigned int code;
/*
** Make unsigned, level shift
*/
c = (c + (1<<15)) & 0xffff;
/*
** Simple linear prediction,
** Form code, grey - coding for
** bitplane decorrelation.
*/
pred = (last << 1) - lastlast;
code = (c - pred) & 0xffff;
code ^= (code >> 1);
/*
** Sort into the contexts.
*/
for(j = 0;j < 16;j++) {
int pos = bitpos[j];
if (code & (1 << j)) {
/* The bit is one */
bitbuffer[j][pos >> 3] |= 1UL << (pos & 0x07);
bitcnt[j]++;
} else {
bitbuffer[j][pos >> 3] &= ~(1UL << (pos & 07));
}
bitpos[j]++;
//
// Check whether the bit position is out of range. If
// so, empty the buffer by writing it out via QI.
if (bitpos[j] >= (2048<<3)) {
push_buffer(bitbuffer[j],bitpos[j],bitcnt[j]);
bitcnt[j] = 0;
bitpos[j] = 0;
}
}
/*
** Update the predictor.
*/
lastlast = last;
last = c;
} else break;
} while(1);
/*
** flush the remaining parts of the buffer
*/
for(j=0;j < 16;j++) {
push_buffer(bitbuffer[j],bitpos[j],bitcnt[j]);
bitcnt[j] = 0;
}
}
/* snip */
Thus, if anyone finds a bug in the above that might have had negative impact on the coding effiency, please let me know. Also, if anyone feels like integrating this better into the program, let me know. I rather hacked it in.
Finally, here's the similar MQ coder code. Note that the MQ coder is covered by patents (IBM and Mitsubishi and maybe others), thus you cannot use it "as is" in products, and I do not give any guarantee concerning the usability, reliablity and similar of the code. Please use this only for research purposes. The context modelling is commented out here, and the MQ coder is *not* implemented optimally (one can do better than this!)
/* snip */
/* ** Simple predictive arithmetic audio coding, (c) 2004 Thomas Richter, ** THOR Software. ** $Id: arthdeco_wide.c,v 1.5 2004/10/10 20:06:33 thor Exp $ ** */
#include <stdio.h> #include <string.h>
/*
** context of the arithmetic coder: index into the probability table,
** most probable symbol
*/
struct MQContext {
unsigned char index;
unsigned char mp;
};/*
** Arithmetic coder structure.
** The MQ coder is patented software, IBM/Mitsubishi.
*/
struct MQCoder {
unsigned long a; /* the inverval */
unsigned long c; /* computation register */
int ct; /* bit counter */
int flag;
unsigned char b; /* b output register */
};/*
** MQ coder lookup tables
*/
const unsigned short Qe_Value[] = {
0x5601,0x3401,0x1801,0x0ac1,0x0521,0x0221,0x5601,0x5401,0x4801,0x3801,
0x3001,0x2401,0x1c01,0x1601,0x5601,0x54ff,0x5401,0x527d,0x5101,0x4c5f,
0x4801,0x3f80,0x3801,0x35f7,0x3401,0x31f6,0x3001,0x2801,0x2401,0x2201,
0x1c01,0x1801,0x1601,0x1401,0x1201,0x1101,0x0ac1,0x09c1,0x08a1,0x0521,
0x0441,0x02a1,0x0221,0x0141,0x0111,0x0085,0x0049,0x0025,0x0015,0x0009,
0x0005,0x0001,0x5601
};/*
** MSB/LSB switch flags
*/
const unsigned char Qe_Switch[] = {
1,0,0,0,0,0,1,0,0,0,
0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0
};/*
** Next state on MPS coding
*/
const unsigned char Qe_NMPS[] = {
1,2,3,4,5,44,7,8,9,10,
11,12,13,35,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,37,38,39,40,
41,42,43,44,45,45,47,48,49,50,
51,51,52
};/*
** Next state on LPS coding
*/
const unsigned char Qe_NLPS[] = {
1,6,9,12,35,39,6,14,14,14,
20,22,25,27,14,14,14,15,16,17,
18,19,20,21,22,23,24,25,26,27,
28,29,30,31,32,33,34,35,36,37,
38,39,40,41,42,43,44,45,46,47,
48,49,52
};static unsigned int getwchar(void)
{
int c1,c2;c1 = getchar(); c2 = getchar();
/* This is big-endian */
return ((c1 << 8) | c2); }
static void putwchar(unsigned int c)
{
putchar(c >> 8);
putchar(c & 0xff);
}/*
** Open the MQ coder for writing
*/
static void OpenForWrite(struct MQCoder *self)
{
self->a = 0x8000;
self->c = 0;
self->ct = 12;
self->b = 0;
self->flag = 0;
}static void OpenForRead(struct MQCoder *self)
{
unsigned char t; self->b = getchar();
self->c = self->b << 16;
t = getchar();
self->ct = 8;
if (self->b == 0xff) {
if (t < 0x90) {
self->c += t << 8;
self->ct--;
}
}
self->c += t << 8;
self->b = t;
self->c <<= 7;
self->ct -= 7;
self->a = 0x8000;
}static int GetBit(struct MQCoder *self,struct MQContext *ctx)
{
unsigned long q = Qe_Value[ctx->index];
unsigned char t;
int d; self->a -= q;
if ((self->c >> 16) >= q) {
/* MPS case */
self->c -= q << 16;
if (self->a & 0x8000) {
/* short MPS case, return immediately. */
return ctx->mp;
}
/* MPS exchange here */
d = (self->a < q); /* d == 1 on LPS */
} else {
/* LPS exchange here */
d = (self->a >= q); /* d == 1 on LPS */
self->a = q;
}
if (d) {
/* LPS decoding. Check for MPS/LPS exchange, adjust index */
d ^= ctx->mp;
if (Qe_Switch[ctx->index])
ctx->mp = d;
ctx->index = Qe_NLPS[ctx->index];
} else {
/* MPS decoding */
d = ctx->mp;
ctx->index = Qe_NMPS[ctx->index];
}
/* Now renormalize */
do {
if (self->ct == 0) {
t = getchar();
self->ct = 8;
if (self->b == 0xff) {
if (t < 0x90) {
self->c += t << 8;
self->ct--;
}
}
self->c += t << 8;
self->b = t;
}
self->a <<= 1;
self->c <<= 1;
self->ct--;
} while((self->a & 0x8000) == 0);return d; }
/*
** Put out a bit thru the MQ coder.
*/
static void PutBit(struct MQCoder *self,struct MQContext *ctx,char bit)
{
unsigned long q = Qe_Value[ctx->index]; self->a -= q;
/*
** Check for MPS/LPS coding
*/
if (bit == ctx->mp) {
/*
** MPS coding
*/
if (self->a & 0x8000) {
/* Short MPS case, no renormalization */
self->c += q;
return;
} else {
/* context change */
if (self->a < q) {
/* MPS/LPS exchange case */
self->a = q;
} else {
self->c += q;
}
ctx->index = Qe_NMPS[ctx->index];
}
} else {
/* LPS coding here */
if (self->a < q) {
self->c += q;
} else {
self->a = q;
}
ctx->mp ^= Qe_Switch[ctx->index];
ctx->index = Qe_NLPS[ctx->index];
}
/*
** Renormalize now.
*/
do {
self->a <<= 1;
self->c <<= 1;
if (--self->ct == 0) {
if (self->b < 0xff) {
if (self->c & 0x8000000) {
/* Overflow into the b register, remove
** carry bit and go on */
self->b++;
self->c &= 0x7ffffff;
}
}
if (self->b == 0xff) {
/* We either have an 0xff here, or generated one due to carry.
** in either case, must have buffered something or the overflow
** could not have happened.
*/
putchar(0xff);
self->b = self->c >> 20;
self->c &= 0xfffff;
self->ct = 7;
} else {
if (self->flag)
putchar(self->b);
self->b = self->c >> 19;
self->c &= 0x7ffff;
self->ct = 8;
}
self->flag = 1;
}
} while((self->a & 0x8000) == 0);
}/*
** Flush out the remaining bits
*/
static void Flush(struct MQCoder *self)
{
int k;
/*
** Number of bits to push out is then in k.
*/
self->c <<= self->ct;
for(k = 12 - self->ct;k > 0;k -= self->ct,self->c <<= self->ct) {
if (self->b < 0xff) {
if (self->c & 0x8000000) {
self->b++;
self->c &= 0x7ffffff;
}
}
if (self->b == 0xff) {
putchar(0xff);
self->b = self->c >> 20;
self->c &= 0xfffff;
self->ct = 7;
} else {
if (self->flag)
putchar(self->b);
self->b = self->c >> 19;
self->c &= 0x7ffff;
self->ct = 8;
}
self->flag = 1;
}
if (self->b < 0xff) {
if (self->c & 0x8000000) {
self->b++;
}
}
if (self->b != 0xff && self->flag)
putchar(self->b);
}int compress(void)
{
struct MQContext ctxt[4096*16];
struct MQContext *cx;
struct MQCoder coder;
unsigned int c,code,i;
unsigned int last = 0,lastlast = 0;
int pred;
unsigned int lb = 0;
unsigned int ci;/* reset all contexts */ memset(&ctxt,0,sizeof(ctxt)); OpenForWrite(&coder);
do {
/* Get input data, level shift to make unsigned
** to avoid overflows which would destroy the
** statistics
*/
c = (getwchar() + (1<<15)) & 0xffff;
if (feof(stdin))
break;
/*
** Form the context. This is here simply
** the last code and thus depends on the
** last three encoded words.
*/
ci = lb >> 4;
/*
** Make a prediction. This is just a linear
** predictor, i.e. a linear slope would be
** predicted to zero.
*/
pred = (last << 1) - lastlast;
/*
** Get the prediction error, possibly including
** wrap-arounds.
*/
code = (c - pred) & 0xffff;
/*
** Build up the context. This context is formed
** by the bit position (16 contexts) and the
** selected context above.
*/
cx = ctxt /*+ (ci << 4)*/;
/*
** keep the last code for the context
*/
lb = code;
/*
** bitplane decorrelation by grey-coding
*/
code ^= (code >> 1);
/*
** Now encode all bitplanes
*/
for(i = 0;i < 16;i++) {
PutBit(&coder,cx,(code & (1 << i))?1:0);
cx++;
}
/*
** keep history for prediction
*/
lastlast = last;
last = c;
} while(1);Flush(&coder);
return 0; }
/* snip */
Greetings, Thomas
.
- Follow-Ups:
- Re: QI and MQ Coder: First real-life experiences
- From: nightlight
- Re: QI and MQ Coder: First real-life experiences
- From: nightlight
- Re: QI and MQ Coder: First real-life experiences
- From: David A. Scott
- Re: QI and MQ Coder: First real-life experiences
- Prev by Date: Re: AVID NDxHD
- Next by Date: Re: QI and MQ Coder: First real-life experiences
- Previous by thread: Re: Compressing log files and CPU load
- Next by thread: Re: QI and MQ Coder: First real-life experiences
- Index(es):
Relevant Pages
|
