[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