[xiph-cvs] cvs commit: w3d huffman.c huffman.h Makefile TODO

Holger Waechtler holger at xiph.org
Tue Nov 13 08:29:09 PST 2001



holger      01/11/13 08:29:08

  Modified:    .        Makefile TODO
  Added:       .        huffman.c huffman.h
  Log:
  the adaptive huffman coder for 32 symbols, neither tested nor used these days

Revision  Changes    Path
1.19      +2 -1      w3d/Makefile

Index: Makefile
===================================================================
RCS file: /usr/local/cvsroot/w3d/Makefile,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -r1.18 -r1.19
--- Makefile	2001/11/07 21:19:02	1.18
+++ Makefile	2001/11/13 16:29:07	1.19
@@ -26,7 +26,7 @@
 
 LFLAGS = -g -lefence -logg
 
-OBJS = mem.o pnm.o wavelet.o wavelet_xform.o wavelet_coeff.o \
+OBJS = mem.o pnm.o huffman.o wavelet.o wavelet_xform.o wavelet_coeff.o \
         yuv.o tarkin.o info.o
 
 TEST_TARGETS = _test_bitcoder _test_rle _test_huffman
@@ -67,3 +67,4 @@
         sh tools/makedepend.sh -f.depend -- $(CFLAGS) -- $(SRCS) $(TEST_SRCS) tarkin_enc.c tarkin_dec.c
 
 -include .depend
+

1.9       +0 -1      w3d/TODO

Index: TODO
===================================================================
RCS file: /usr/local/cvsroot/w3d/TODO,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- TODO	2001/09/13 16:27:33	1.8
+++ TODO	2001/11/13 16:29:07	1.9
@@ -2,7 +2,6 @@
 Most important things:
 
  - the entropy coder, replace static huffman
- - oggetize the stream format (Jack? Help!)
  - clean up the pnsr tools
  - write docs and do some performance analysis, compare to other codecs
  - think about a multiresolution multidimensional motion flow detection scheme,

1.1                  w3d/huffman.c

Index: huffman.c
===================================================================

#include <stdlib.h>
#include <stdint.h>
#include <assert.h>

#include "huffman.h"

#define MAX_FREQ ((1 << 14) - 1)

#define LEAF(x) ((x) | (1 << 5))

HuffmanTree32 default_huffman_tree = {
   { {~0, 0, 1, 2 },
     { 0, 0, 3, 4 },
     { 0, 0, 5, 6 },
     { 1, 0, 7, 8 },
     { 1, 0, 9, 10 },
     { 2, 0, 11, 12 },
     { 2, 0, 13, 14 },
     { 3, 0, 15, 16 },
     { 3, 0, 17, 18 },
     { 4, 0, 19, 20 },
     { 4, 0, 21, 22 },
     { 5, 0, 23, 24 },
     { 5, 0, 25, 26 },
     { 6, 0, 27, 28 },
     { 6, 0, 29, 30 },
     { 7, 0, LEAF(0), LEAF(1) },
     { 7, 0, LEAF(2), LEAF(3) },
     { 8, 0, LEAF(4), LEAF(5) },
     { 8, 0, LEAF(6), LEAF(7) },
     { 9, 0, LEAF(8), LEAF(9) },
     { 9, 0, LEAF(10), LEAF(11) },
     { 10, 0, LEAF(12), LEAF(13) },
     { 10, 0, LEAF(14), LEAF(15) },
     { 11, 0, LEAF(16), LEAF(17) },
     { 11, 0, LEAF(18), LEAF(19) },
     { 12, 0, LEAF(20), LEAF(21) },
     { 12, 0, LEAF(22), LEAF(23) },
     { 13, 0, LEAF(24), LEAF(25) },
     { 13, 0, LEAF(26), LEAF(27) },
     { 14, 0, LEAF(28), LEAF(29) },
     { 14, 0, LEAF(30), LEAF(31) }
   },
   {
     { 15, 0 },
     { 15, 0 },
     { 16, 0 },
     { 16, 0 },
     { 17, 0 },
     { 17, 0 },
     { 18, 0 },
     { 18, 0 },
     { 19, 0 },
     { 19, 0 },
     { 20, 0 },
     { 20, 0 },
     { 21, 0 },
     { 21, 0 },
     { 22, 0 },
     { 22, 0 },
     { 23, 0 },
     { 23, 0 },
     { 24, 0 },
     { 24, 0 },
     { 25, 0 },
     { 25, 0 },
     { 26, 0 },
     { 26, 0 },
     { 27, 0 },
     { 27, 0 },
     { 28, 0 },
     { 28, 0 },
     { 29, 0 },
     { 29, 0 },
     { 30, 0 },
     { 30, 0 }
   }
};

static
void huffman_swap_nodes (HuffmanTree32 *t, unsigned int n1, unsigned int n2);

/**
 *   be careful, this will return leafs if the is_leaf bit is set!!
 */
static inline
HuffmanNode* _huffman_get_node (HuffmanTree32 *t, unsigned int node)
{
   if (node & (1 << 5))
      return (HuffmanNode*) &t->leaf[node & 0x1f];
   else
      return &t->node[node];
}

/**
 *  searches above for a node with lower frequency and returns this
 *  or the node left above. 
 */
static inline
unsigned int _huffman_get_usuccessor (HuffmanTree32 *t, unsigned int node,
                                      int freq_limit)
{
   HuffmanNode *root = _huffman_get_node (t, node);
   HuffmanNode *n;
   int level = 0;

   while (root->parent != ~0) {
      root = &t->node[root->parent];
      level++;
   }

   n = _huffman_get_node (t, root->child0);

   if (root->child0 & (1 << 5))
      return root->child0;

   while (level > 2 && n->freq > freq_limit) {
      int is_leaf = n->child0 & (1 << 5);
      if (is_leaf)
         break;
      n = _huffman_get_node (t, n->child0);
      level--;
   };

   return n->child0;
}

/**
 * search for the right successor. Can return NULL!
 */
static inline
unsigned int _huffman_get_rsuccessor (HuffmanTree32 *t, unsigned int node,
                                      int freq_limit)
{
   HuffmanNode *n, *parent;
   int level = 0;

   n = _huffman_get_node (t, node);

   while ((parent = &t->node[n->parent])->child1 == node) {
      node = n->parent;
      if (node == ~0)                   /*  no right successor */
         return ~0;
      n = _huffman_get_node (t, node);
      level++;
   }

   n = _huffman_get_node (t, parent->child1);

   if (parent->child1 & (1 << 5))
      return parent->child1;

   while (level > 1 && n->freq > freq_limit) {
      int is_leaf = n->child0 & (1 << 5);
      if (is_leaf)
         break;
      n = _huffman_get_node (t, n->child0);
      level--;
   }

   return n->child0;
}

static inline
void huffman_update (HuffmanTree32 *t, unsigned int node)
{
   HuffmanNode *n = _huffman_get_node (t, node);
   unsigned int r = node, u = node;

   do {
      r = _huffman_get_rsuccessor (t, r, n->freq);
   } while (r != ~0 && _huffman_get_node(t, r)->freq > n->freq);

   if (_huffman_get_node(t, r)->freq > n->freq)
      huffman_swap_nodes (t, node, r);

   do {
      u = _huffman_get_usuccessor (t, u, n->freq);
   } while (u != ~0 && _huffman_get_node(t, u)->freq > n->freq);

   if (_huffman_get_node(t, u)->freq > n->freq)
      huffman_swap_nodes (t, node, u);
}

static inline
void huffman_update_freq (HuffmanTree32 *t, unsigned int node)
{
   while (node != ~0) {
      HuffmanNode *n = _huffman_get_node (t, node);

      if (!(node & (1 << 5))) {
         HuffmanNode *c0 = _huffman_get_node (t, n->child0);
         HuffmanNode *c1 = _huffman_get_node (t, n->child1);
         n->freq = c0->freq + c1->freq;

         if (n->freq > MAX_FREQ) {
            int i;
            for (i=0; i<31; i++)
               t->node[i].freq /= 2;
            for (i=0; i<32; i++)
               t->leaf[i].freq /= 2;
         }
      }

      huffman_update (t, node);
      node = n->parent;
   };
}

#define ISWAP(a,b)  do { unsigned int tmp = a; a = b; b = tmp; } while (0)

static
void huffman_swap_nodes (HuffmanTree32 *t, unsigned int n1, unsigned int n2)
{
   HuffmanNode *node1 = _huffman_get_node (t, n1);
   HuffmanNode *node2 = _huffman_get_node (t, n2);

   if (node1->parent == node2->parent) {
      HuffmanNode *parent =  &t->node[node1->parent];
      ISWAP(parent->child0, parent->child1);
   } else {
      HuffmanNode *parent1 = &t->node[node1->parent];
      HuffmanNode *parent2 = &t->node[node2->parent];

      if (parent1->child0 == n1) parent1->child0 = n2;
      else if (parent1->child0 == n2) parent1->child0 = n1;

      if (parent1->child1 == n1) parent1->child1 = n2;
      else if (parent1->child1 == n2) parent1->child1 = n1;

      if (parent2->child0 == n1) parent2->child0 = n2;
      else if (parent2->child0 == n2) parent2->child0 = n1;

      if (parent2->child1 == n1) parent2->child1 = n2;
      else if (parent2->child1 == n2) parent2->child1 = n1;

      ISWAP(node1->parent, node2->parent);

      huffman_update_freq (t, node1->parent);
      huffman_update_freq (t, node2->parent);
   }
}

void huffman_init (HuffmanTree32 *tree)
{
   memcpy (tree, &default_huffman_tree, sizeof(HuffmanTree32));
}

void huffman_encode_symbol (BitCoderState *bitcoder, HuffmanTree32 *t, unsigned int symbol)
{
   HuffmanNode *node, *parent;
   unsigned int n = symbol;
   uint32_t code = 0;
   int bit = 0;

   assert (symbol < 32);

   node = (HuffmanNode*) &t->leaf[symbol];

   do {
      parent = _huffman_get_node (t, node->parent);
      code |= (parent->child1 == n) << bit++;
      n = node->parent;
      node = parent;
   } while (n != ~0);
   
   while (bit)
      bitcoder_write_bit (bitcoder, code >> --bit);

   t->leaf[symbol].freq++;
   huffman_update (t, symbol | (1 << 5));
}

unsigned int huffman_decode_symbol (BitCoderState *bitcoder, HuffmanTree32 *t)
{
   unsigned int n = ~0;

   do {
      HuffmanNode *node = _huffman_get_node (t, n);
      if (bitcoder_read_bit (bitcoder))
         n = node->child1;
      else
         n = node->child0;
   } while (!n & (1 << 5));

   t->leaf[n & 0x1f].freq++;
   huffman_update (t, n);

   return (n & 0x1f);
}

1.1                  w3d/huffman.h

Index: huffman.h
===================================================================

#include "bitcoder.h"

typedef struct {
   unsigned int parent : 5;
   unsigned int freq : 15;
   unsigned int child0 : 6;   /* MSB is the is_leaf bit! */
   unsigned int child1 : 6;   /* MSB is the is_leaf bit! */
} HuffmanNode;

typedef struct {
   unsigned int parent : 5;
   unsigned int freq : 15;
} HuffmanLeaf;

typedef struct {
   HuffmanNode node[31];
   HuffmanLeaf leaf[32];
} HuffmanTree32;

extern 
void huffman_init (HuffmanTree32 *tree);

extern 
void huffman_encode_symbol (BitCoderState *bitcoder, HuffmanTree32 *t,
                            unsigned int symbol);
extern 
unsigned int huffman_decode_symbol (BitCoderState *bitcoder, HuffmanTree32 *t);

--- >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