[xiph-cvs] cvs commit: w3d/docs entropycoder.tex
Holger Waechtler
holger at xiph.org
Tue Nov 20 03:15:03 PST 2001
holger 01/11/20 03:15:03
Modified: . Makefile TODO WHAT_THE_HECK_IS_THIS_CODE_DOING
_test_rle.c bitcoder.h rle.h tarkin.c wavelet.c
wavelet_coeff.c wavelet_xform.c
docs entropycoder.tex
Added: . golomb.h
Removed: . _test_huffman.c huffman.c huffman.h
Log:
- we have an adaptive golomb coder now, this works as well as the
adaptive huffman...
- removed some debug code in the runlength encoder
Revision Changes Path
1.20 +8 -11 w3d/Makefile
Index: Makefile
===================================================================
RCS file: /usr/local/cvsroot/w3d/Makefile,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -r1.19 -r1.20
--- Makefile 2001/11/13 16:29:07 1.19
+++ Makefile 2001/11/20 11:15:00 1.20
@@ -1,7 +1,7 @@
CC = gcc
RM = rm -rf
-CFLAGS = -g -O2 -Wall
+CFLAGS = -pg -O2 -Wall -I../ogg/ogg/include
# use 16 bit signed integers as wavelet coefficients
CFLAGS+= -DTYPE=int16_t
@@ -13,23 +13,23 @@
CFLAGS+= -DRLECODER
# simple malloc debugging
-CFLAGS+= -DDBG_MEMLEAKS
+#CFLAGS+= -DDBG_MEMLEAKS
# dump a lot debug images
-CFLAGS+= -DDBG_XFORM
+#CFLAGS+= -DDBG_XFORM
# dump ogg packet infos
-CFLAGS+= -DDBG_OGG
+#CFLAGS+= -DDBG_OGG
# disable assertions
#CFLAGS+= -DNDEBUG
-LFLAGS = -g -lefence -logg
+LFLAGS = -pg -lefence -logg -L../ogg/ogg/src/.libs
-OBJS = mem.o pnm.o huffman.o wavelet.o wavelet_xform.o wavelet_coeff.o \
+OBJS = mem.o pnm.o wavelet.o wavelet_xform.o wavelet_coeff.o \
yuv.o tarkin.o info.o
-TEST_TARGETS = _test_bitcoder _test_rle _test_huffman
+TEST_TARGETS = _test_bitcoder _test_rle
SRCS = $(OBJS:.o=.c)
TEST_OBJS = $(TEST_TARGETS:=.o)
@@ -51,15 +51,12 @@
$(RM) $(OBJS) $(TARGET) gmon.out core .depend .depend.bak rle.histogram
$(RM) $(TEST_TARGETS) $(TEST_OBJS)
$(RM) tarkin_enc tarkin_dec tarkin_enc.o tarkin_dec.o
- $(RM) *.ppm *.pgm
$(RM) stream.ogg
-
+ $(RM) *.ppm *.pgm
test: .depend $(TEST_TARGETS)
./_test_bitcoder
- ./_test_huffman
./_test_rle
-
.depend: $(SRCS) $(TEST_SRCS)
$(RM) .depend
1.10 +1 -0 w3d/TODO
Index: TODO
===================================================================
RCS file: /usr/local/cvsroot/w3d/TODO,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- TODO 2001/11/13 16:29:07 1.9
+++ TODO 2001/11/20 11:15:00 1.10
@@ -1,4 +1,5 @@
+
Most important things:
- the entropy coder, replace static huffman
1.3 +2 -1 w3d/WHAT_THE_HECK_IS_THIS_CODE_DOING
Index: WHAT_THE_HECK_IS_THIS_CODE_DOING
===================================================================
RCS file: /usr/local/cvsroot/w3d/WHAT_THE_HECK_IS_THIS_CODE_DOING,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- WHAT_THE_HECK_IS_THIS_CODE_DOING 2001/06/25 07:56:07 1.2
+++ WHAT_THE_HECK_IS_THIS_CODE_DOING 2001/11/20 11:15:00 1.3
@@ -4,7 +4,8 @@
The command line semantics are changed. You have to call the test program
now like this:
-./main ../clips/venuscubes-ppm/AnimSpace00%03d.ppm 1000 400 400 4 4
+./tarkin_enc ../clips/venuscubes-ppm/AnimSpace00%03d.ppm 5000 4 4
+./tarkin_dec
------------------------------------------------------------------------------
1.6 +3 -3 w3d/_test_rle.c
Index: _test_rle.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/_test_rle.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- _test_rle.c 2001/09/13 16:27:33 1.5
+++ _test_rle.c 2001/11/20 11:15:00 1.6
@@ -4,7 +4,7 @@
#define TEST(x) \
if(!(x)) { \
- fprintf(stderr, "Test ("#x") FAILED !!!\n"); \
+ fprintf(stderr, "Test ("#x") FAILED (i == %i) !!!\n", i); \
exit (-1); \
}
@@ -56,7 +56,7 @@
ENTROPY_ENCODER_INIT(&encoder, limit);
for (i=0; i<limit; i++) {
- bit[i] = (rand() > RAND_MAX/100) ? 0 : 1; /* avg. runlength 100 */
+ bit[i] = (rand() > RAND_MAX/1000) ? 0 : 1; /* avg. runlength 1000 */
OUTPUT_BIT(&encoder, bit[i]);
}
@@ -85,7 +85,7 @@
TEST(bit[i] == b);
skip = ENTROPY_CODER_RUNLENGTH(&decoder);
- if (skip > 0 && ENTROPY_CODER_MPS(&decoder) == 0) {
+ if (skip > 0 && ENTROPY_CODER_SYMBOL(&decoder) == 0) {
int j;
for (j=0; j<skip; j++)
TEST(bit[i+j] == 0);
1.10 +3 -3 w3d/bitcoder.h
Index: bitcoder.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/bitcoder.h,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -r1.9 -r1.10
--- bitcoder.h 2001/09/13 16:27:33 1.9
+++ bitcoder.h 2001/11/20 11:15:00 1.10
@@ -10,7 +10,7 @@
#define OUTPUT_BIT_DIRECT(coder,bit) bitcoder_write_bit(coder,bit)
#define INPUT_BIT_DIRECT(coder) bitcoder_read_bit(coder)
#define ENTROPY_CODER BitCoderState
-#define ENTROPY_ENCODER_INIT(coder,limit) bitcoder_encoder_init(coder,limit)
+#define ENTROPY_ENCODER_init(coder,limit) bitcoder_coder_init(coder,limit)
#define ENTROPY_ENCODER_DONE(coder) bitcoder_encoder_done(coder)
#define ENTROPY_ENCODER_FLUSH(coder) bitcoder_flush(coder)
#define ENTROPY_DECODER_INIT(coder,bitstream,limit) \
@@ -18,7 +18,7 @@
#define ENTROPY_DECODER_DONE(coder) /* nothing to do ... */
#define ENTROPY_CODER_BITSTREAM(coder) (coder)->bitstream
-#define ENTROPY_CODER_MPS(coder) 1
+#define ENTROPY_CODER_SYMBOL(coder) 1
#define ENTROPY_CODER_RUNLENGTH(coder) 0
#define ENTROPY_CODER_SKIP(coder,skip)
@@ -124,7 +124,7 @@
s->byte <<= 1;
s->bit_count--;
- return ret;
+ return ret & 1;
}
1.11 +46 -196 w3d/rle.h
Index: rle.h
===================================================================
RCS file: /usr/local/cvsroot/w3d/rle.h,v
retrieving revision 1.10
retrieving revision 1.11
diff -u -r1.10 -r1.11
--- rle.h 2001/09/13 16:27:33 1.10
+++ rle.h 2001/11/20 11:15:00 1.11
@@ -5,6 +5,7 @@
#include <assert.h>
#include "mem.h"
#include "bitcoder.h"
+#include "golomb.h"
#if defined(RLECODER)
@@ -22,230 +23,79 @@
#define ENTROPY_CODER_BITSTREAM(coder) ((coder)->bitcoder.bitstream)
#define ENTROPY_CODER_EOS(coder) ((coder)->bitcoder.eos)
-#define ENTROPY_CODER_MPS(coder) ((coder)->mps)
+#define ENTROPY_CODER_SYMBOL(coder) ((coder)->symbol)
#define ENTROPY_CODER_RUNLENGTH(coder) ((coder)->count)
#define ENTROPY_CODER_SKIP(coder,skip) do { (coder)->count -= skip; } while (0)
#endif
-#define RLE_HISTOGRAM 1
-
-/*
- * Ugly.
- */
-static inline
-uint32_t huffmancoder_read (BitCoderState *s)
-{
- if (bitcoder_read_bit (s) == 0)
- return 0;
-
- if (bitcoder_read_bit (s) == 0)
- return 1;
-
- if (bitcoder_read_bit (s) == 0) {
- if (bitcoder_read_bit (s) == 0)
- return 2;
- else
- return 3;
- }
-
- if (bitcoder_read_bit (s) == 0) {
- if (bitcoder_read_bit (s) == 0)
- return 4;
- else
- return 5;
- }
-
- if (bitcoder_read_bit (s) == 0) { /* read 8 bit number */
- uint32_t x = 0;
- int i;
- for (i=7; i>=0; i--)
- if (bitcoder_read_bit (s))
- x |= 1 << i;
-
- return (x + 5);
- } else { /* read 32 bit number */
- uint32_t x = 0;
- int i;
- for (i=31; i>=0; i--)
- if (bitcoder_read_bit (s))
- x |= 1 << i;
-
- return (x + 0xff + 5);
- }
-}
-
-
-/*
- * special handling if (x > 2^32 - 2) ???
- */
-static inline
-void huffmancoder_write (BitCoderState *s, uint32_t x)
-{
- if (x == 0) {
- bitcoder_write_bit (s, 0);
- return;
- }
-
- bitcoder_write_bit (s, 1);
- if (x == 1) {
- bitcoder_write_bit (s, 0);
- return;
- }
-
- bitcoder_write_bit (s, 1);
- if (x <= 3) {
- bitcoder_write_bit (s, 0);
- if (x == 2) bitcoder_write_bit (s, 0);
- else bitcoder_write_bit (s, 1);
- return;
- }
-
- bitcoder_write_bit (s, 1);
- if (x <= 5) {
- bitcoder_write_bit (s, 0);
- if (x == 4) bitcoder_write_bit (s, 0);
- else bitcoder_write_bit (s, 1);
- return;
- }
-
- x -= 5;
- bitcoder_write_bit (s, 1);
- if (x <= 0xff) {
- int i;
- bitcoder_write_bit (s, 0);
- for (i=7; i>=0; i--)
- bitcoder_write_bit (s, (x >> i) & 1);
- } else {
- int i;
- x -= 0xff;
- bitcoder_write_bit (s, 1);
- for (i=31; i>=0; i--)
- bitcoder_write_bit (s, (x >> i) & 1);
- }
-}
-
-
-
-static inline
-int required_bits (uint32_t x)
-{
- int bits = 32;
-
- assert (x >= 0);
-
- while (--bits >= 0 && ((x >> bits) & 1) == 0)
- ;
-
- return bits;
-}
-
-
-static inline
-void write_unsigned_number (BitCoderState *s, uint32_t x)
-{
- int bits;
-
- assert (x >= 0);
-
- bits = required_bits (x);
-
- huffmancoder_write (s, bits);
-
- while (--bits >= 0)
- bitcoder_write_bit (s, (x >> bits) & 1);
-}
-
-static inline
-uint32_t read_unsigned_number (BitCoderState *s)
-{
- int bits = huffmancoder_read (s);
- uint32_t x = 1 << bits;
-
- if (s->eos)
- return ~0;
-
- while (--bits >= 0) {
- x |= bitcoder_read_bit (s) << bits;
- if (s->eos)
- return ~0;
- }
-
- return x;
-}
-
-
typedef struct {
- int mps; /* more probable symbol */
- uint32_t count; /* have seen count mps's */
+ int symbol;
+ uint32_t count; /* have seen count symbol's */
BitCoderState bitcoder;
+ GolombAdaptiveCoderState golomb_state [2]; /* 2 states for 2 symbols... */
+ int have_seen_1;
} RLECoderState;
-#ifdef RLE_HISTOGRAM
-uint32_t histogram [512];
-uint32_t max_runlength;
-#endif
-
-
/*
* bit should be 0 or 1 !!!
*/
static inline
void rlecoder_write_bit (RLECoderState *s, int bit)
{
- if (s->mps == -1) {
-#ifdef RLE_HISTOGRAM
- memset (histogram, 0, 512*sizeof(uint32_t));
- max_runlength = 0;
-#endif
- s->mps = bit & 1;
- s->count = 0;
+ assert (bit == 0 || bit == 1);
+
+ if (s->symbol == -1) {
+ s->symbol = bit & 1;
+ s->count = 1;
+ s->have_seen_1 = bit;
bitcoder_write_bit (&s->bitcoder, bit);
}
- if (s->mps == bit) {
- s->count++;
- } else {
-#ifdef RLE_HISTOGRAM
- if (s->count < 511)
- histogram [s->count-1]++;
- else
- histogram [511]++;
- if (max_runlength < s->count)
- max_runlength = s->count-1;
-#endif
- write_unsigned_number (&s->bitcoder, s->count);
- s->mps = ~s->mps & 1;
+ if (s->symbol != bit) {
+ golombcoder_encode_number (&s->golomb_state[s->symbol],
+ &s->bitcoder, s->count);
+ s->symbol = ~s->symbol & 1;
+ s->have_seen_1 = 1;
s->count = 1;
- }
+ } else
+ s->count++;
}
static inline
int rlecoder_read_bit (RLECoderState *s)
{
if (s->count == 0) {
- s->count = read_unsigned_number (&s->bitcoder);
- s->mps = ~s->mps & 1;
+ s->symbol = ~s->symbol & 1;
+ s->count = golombcoder_decode_number (&s->golomb_state[s->symbol],
+ &s->bitcoder);
if (s->bitcoder.eos) {
- s->mps = 0;
+ s->symbol = 0;
s->count = ~0;
}
}
s->count--;
- return (s->mps);
+ return (s->symbol);
}
+int coder_id = 0;
+FILE *file = NULL;
+
static inline
void rlecoder_encoder_init (RLECoderState *s, uint32_t limit)
{
bitcoder_encoder_init (&s->bitcoder, limit);
- s->mps = -1;
- s->count = 0;
+ s->symbol = -1;
+ s->have_seen_1 = 0;
+ s->golomb_state[0].count = 0;
+ s->golomb_state[1].count = 0;
+ s->golomb_state[0].bits = 5 << 3;
+ s->golomb_state[1].bits = 5 << 3;
}
@@ -255,7 +105,11 @@
static inline
uint32_t rlecoder_encoder_flush (RLECoderState *s)
{
- write_unsigned_number (&s->bitcoder, s->count);
+ if (s->symbol == -1 || !s->have_seen_1)
+ return 0;
+
+ golombcoder_encode_number (&s->golomb_state[s->symbol],
+ &s->bitcoder, s->count);
return bitcoder_flush (&s->bitcoder);
}
@@ -264,10 +118,15 @@
void rlecoder_decoder_init (RLECoderState *s, uint8_t *bitstream, uint32_t limit)
{
bitcoder_decoder_init (&s->bitcoder, bitstream, limit);
- s->mps = bitcoder_read_bit (&s->bitcoder);
- s->count = read_unsigned_number (&s->bitcoder);
+ s->golomb_state[0].count = 0;
+ s->golomb_state[1].count = 0;
+ s->golomb_state[0].bits = 5 << 3;
+ s->golomb_state[1].bits = 5 << 3;
+ s->symbol = bitcoder_read_bit (&s->bitcoder);
+ s->count = golombcoder_decode_number (&s->golomb_state[s->symbol],
+ &s->bitcoder) - 1;
if (s->bitcoder.eos) {
- s->mps = 0;
+ s->symbol = 0;
s->count = ~0;
}
}
@@ -276,15 +135,6 @@
static inline
void rlecoder_encoder_done (RLECoderState *s)
{
-#ifdef RLE_HISTOGRAM
- FILE *f = fopen ("rle.histogram", "w");
- int i;
-
- fprintf (f, "# max. runlength: %u\n", max_runlength);
- for (i=0; i<512; i++)
- fprintf (f, "%i %u\n", i, histogram[i]);
- fclose (f);
-#endif
bitcoder_encoder_done (&s->bitcoder);
}
1.14 +1 -0 w3d/tarkin.c
Index: tarkin.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/tarkin.c,v
retrieving revision 1.13
retrieving revision 1.14
diff -u -r1.13 -r1.14
--- tarkin.c 2001/11/10 04:12:52 1.13
+++ tarkin.c 2001/11/20 11:15:00 1.14
@@ -381,6 +381,7 @@
layer->color_inv_xform (layer->waveletbuf, *frame,
s->current_frame_in_buf);
s->current_frame_in_buf++;
+ s->current_frame++;
if (s->current_frame_in_buf == s->frames_per_buf)
s->current_frame_in_buf=0;
1.13 +0 -1 w3d/wavelet.c
Index: wavelet.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet.c,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -r1.12 -r1.13
--- wavelet.c 2001/09/07 10:56:30 1.12
+++ wavelet.c 2001/11/20 11:15:00 1.13
@@ -1,6 +1,5 @@
#include "mem.h"
#include "wavelet.h"
-#include "rle.h"
/**
* (The transform code is in wavelet_xform.c)
1.6 +10 -9 w3d/wavelet_coeff.c
Index: wavelet_coeff.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet_coeff.c,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- wavelet_coeff.c 2001/09/13 16:27:33 1.5
+++ wavelet_coeff.c 2001/11/20 11:15:00 1.6
@@ -64,7 +64,7 @@
uint32_t skip = limit;
for (i=0; i<TYPE_BITS; i++) {
- if (ENTROPY_CODER_MPS(&s_stream[i]) != 0) {
+ if (ENTROPY_CODER_SYMBOL(&s_stream[i]) != 0) {
return 0;
} else {
uint32_t runlength = ENTROPY_CODER_RUNLENGTH(&s_stream[i]);
@@ -270,9 +270,10 @@
limit -= byte_count;
printf ("%s: rem. limit == %u\n", __FUNCTION__, limit);
- significand_limit = limit * 4 / 8;
+ significand_limit = limit * 7 / 8;
insignificand_limit = limit - significand_limit;
+ printf ("%s: limit == %u\n", __FUNCTION__, limit);
printf ("significand limit == %u\n", significand_limit);
printf ("insignificand limit == %u\n", insignificand_limit);
@@ -283,8 +284,8 @@
significand_limittab[i] = (significand_limit + 1) / 2;
insignificand_limittab[i] = (insignificand_limit + 1) / 2;
} else {
- significand_limittab[i] = significand_limit;
- insignificand_limittab[i] = insignificand_limit;
+ significand_limittab[0] = significand_limit;
+ insignificand_limittab[0] = insignificand_limit;
}
s_bytes = ENTROPY_ENCODER_FLUSH(&significand_bitstream[i]);
@@ -296,9 +297,6 @@
if (i_bytes < insignificand_limittab[i])
insignificand_limittab[i] = i_bytes;
- significand_limit -= significand_limittab[i];
- insignificand_limit -= insignificand_limittab[i];
-
byte_count += significand_limittab[i];
byte_count += insignificand_limittab[i];
@@ -306,6 +304,9 @@
i, insignificand_limittab[i], i_bytes);
printf (" significand_limittab[%i] == %u / %u\n",
i, significand_limittab[i], s_bytes);
+
+ significand_limit -= significand_limittab[i];
+ insignificand_limit -= insignificand_limittab[i];
}
printf ("byte_count == %u\n", byte_count);
@@ -426,10 +427,10 @@
uint32_t byte_count;
int i;
- for (i=0; i<TYPE_BITS; i++) {
+ for (i=0; i<TYPE_BITS; i++)
ENTROPY_ENCODER_INIT(&significand_bitstream[i], limit);
+ for (i=0; i<TYPE_BITS; i++)
ENTROPY_ENCODER_INIT(&insignificand_bitstream[i], limit);
- }
encode_coefficients (buf, significand_bitstream, insignificand_bitstream);
1.5 +2 -2 w3d/wavelet_xform.c
Index: wavelet_xform.c
===================================================================
RCS file: /usr/local/cvsroot/w3d/wavelet_xform.c,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- wavelet_xform.c 2001/09/13 16:27:33 1.4
+++ wavelet_xform.c 2001/11/20 11:15:00 1.5
@@ -261,7 +261,7 @@
assert (a_moments == 1 || a_moments == 2 || a_moments == 4);
assert (s_moments == 1 || s_moments == 2 || s_moments == 4);
- /* XXX FIXME: Ugly hack to workaround */
+ /* XXX FIXME: Ugly hack to work around */
/* the short-row bug in high */
/* order xform functions */
if (n < 9)
@@ -287,7 +287,7 @@
assert (a_moments == 1 || a_moments == 2 || a_moments == 4);
assert (s_moments == 1 || s_moments == 2 || s_moments == 4);
- /* XXX FIXME: Ugly hack to workaround */
+ /* XXX FIXME: Ugly hack to work around */
/* the short-row bug in high */
/* order xform functions */
if (n < 9)
1.1 w3d/golomb.h
Index: golomb.h
===================================================================
#ifndef __GOLOMB_H
#define __GOLOMB_H
#include "bitcoder.h"
static inline
void write_number_unary (BitCoderState *b, unsigned int x)
{
while (x--)
bitcoder_write_bit (b, 1);
bitcoder_write_bit (b, 0);
}
static inline
unsigned int read_number_unary (BitCoderState *b)
{
unsigned int x = 0;
while (bitcoder_read_bit (b))
x++;
return x;
}
static inline
void write_number_binary (BitCoderState *b, unsigned int x, int bits)
{
while (bits) {
bits--;
bitcoder_write_bit (b, (x >> bits) & 1);
}
}
static inline
unsigned int read_number_binary (BitCoderState *b, int bits)
{
unsigned int x = 0;
while (bits) {
bits--;
x |= bitcoder_read_bit (b) << bits;
}
return x;
}
static inline
unsigned int required_bits (unsigned int x)
{
int bits = 31;
while ((x & (1 << bits)) == 0 && bits)
bits--;
return bits;
}
static inline
void golomb_write_number (BitCoderState *b, unsigned int x, int bits)
{
unsigned int q, r;
assert (x > 0);
q = (x - 1) >> bits;
r = x - 1 - (q << bits);
if (q >= 15) {
if (x > 0xffff) {
write_number_unary (b, 16);
write_number_binary (b, x, 32);
} else {
write_number_unary (b, 15);
write_number_binary (b, x, 16);
}
} else {
write_number_unary (b, q);
write_number_binary (b, r, bits);
}
}
static inline
unsigned int golomb_read_number (BitCoderState *b, int bits)
{
unsigned int q, r, x;
q = read_number_unary (b);
if (q == 15)
x = read_number_binary (b, 16);
else if (q == 16)
x = read_number_binary (b, 32);
else {
r = read_number_binary (b, bits);
x = (q << bits) + r + 1;
}
return x;
}
typedef struct {
uint8_t count;
uint8_t bits; /* a 5.3 fixed point integer */
} GolombAdaptiveCoderState;
#define GOLOMB_ADAPTIVE_CODER_STATE_INITIALIZER { 8<<3, 0 }
static const int golomb_w_tab [] = { 256, 128, 64 };
static inline
void golombcoder_encode_number (GolombAdaptiveCoderState *g,
BitCoderState *b,
unsigned int x)
{
golomb_write_number (b, x, g->bits >> 3);
g->bits = ((256 - golomb_w_tab[g->count]) * (int) g->bits +
golomb_w_tab[g->count] * ((required_bits(x)<<3) + 4)) / 256;
g->count++;
if (g->count > 2)
g->count = 2;
}
static inline
unsigned int golombcoder_decode_number (GolombAdaptiveCoderState *g,
BitCoderState *b)
{
unsigned int x;
x = golomb_read_number (b, g->bits >> 3);
g->bits = ((256 - golomb_w_tab[g->count]) * g->bits +
golomb_w_tab[g->count] * ((required_bits(x)<<3) + 4)) / 256;
g->count++;
if (g->count > 2)
g->count = 2;
return x;
}
#endif
1.3 +34 -8 w3d/docs/entropycoder.tex
Index: entropycoder.tex
===================================================================
RCS file: /usr/local/cvsroot/w3d/docs/entropycoder.tex,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- entropycoder.tex 2001/09/13 16:27:35 1.2
+++ entropycoder.tex 2001/11/20 11:15:02 1.3
@@ -10,17 +10,43 @@
the first significand bits of smaller coefficients have similiar properties
but a bit shorter runs.
-Runlengths are the written as pair of two codes into the new compressed stream:
-\verb|number of required bits| and
-\verb|binary written runlength|. The first bit of runlength can be omitted;
-it's always $1$. The number of bits required to code the runlength are huffman
-coded. This is currently done with an ugly and pretty inefficient static
-huffman coder, it should better done with an adaptive huffman coder or a
-range coder. (Any Volunteers?)
+Runlengths are the written using the Golomb Coder to the compressed stream:
Insignificand bits (the bits of a coefficient after the first significand bit)
are almost random, it doesn't makes sense to spend much energy on trying
to compress them. But some of them -- especially for low frequency
coefficients -- need to be transmitted in order to prevent a DC offset or low
-frequency color floating.
+frequency color floating. So we write these bits directly into the stream.
+
+
+\subsection{ The Golomb Coder }
+
+Golomb published in the 70's a coding method to encode runlengths with a
+combination of near optimal huffman codes without going through the huffman
+algorithm. This was the base for some arithmetic entropy coders, namely the
+Z- and ZP-Coder which generalize and extend the Golomb coder to improve adaption.
+Because of patent issues of Mitsubishi and AT&T we can't use those derivates.
+
+Instead we use a slightly modified version of the original algorithm. If we
+have a good guess of the range of a number $x$ given by the number of required bits
+both on the transmitter and receiver side we encode a number by splitting it in
+two parameters $q$ and $r$:
+
+\begin{eqnarray}
+q &=& (x - 1) >> bits \nonumber\\
+r &=& x - 1 - (q << bits) \nonumber
+\end{eqnarray}
+
+Now the unary representation of $q$ holds a huffman code for the real number of
+required bits to transmit $r$ binary. And that's exactly what we transmit: the
+unary code of $q$ and the binary code of $r$.
+
+Every time a runlength is encoded we update the average number of bits required
+to encode runlengths of this symbol.
+
+The Golomb Coder performs well if use it to encode runlengths of 0-runs when the
+lengths of the runs don't differ much or if we have to transmit parameters with
+a known order of magnitude (width/heights/subbitstream lengths/...).
+
+
--- >8 ----
List archives: http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'cvs-request at xiph.org'
containing only the word 'unsubscribe' in the body. No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.
More information about the commits
mailing list