ad2hcaf.c

静态Huffman的小程序

/* Adaptive Huffman encoding program */
/* Hal Burch */
/* Sept 16, 1996 */

/*
 * This is based on the Adaptive Huffman algorithm described in Sayood's Data
 * Compression book.  The ranks are not actually stored, but implicitly
 * defined by the location of a node within a doubly-linked list
 */


/*******************************************************************************
*NOTICE:                                                                       *
*This code is believed by the author to be bug free.  You are free to use and  *
*modify this code with the understanding that any use, either direct or        *
*derivative, must contain acknowledgement of its author and source.  The author*
*makes no warranty of any kind, expressed or implied, of merchantability or    *
*fitness for a particular purpose.  The author shall not be held liable for any*
*incidental or consequential damages in connection with or arising out of the  *
*furnishing, performance, or use of this software.  This software is not       *
*authorized for use in life support devices or systems.                        *
********************************************************************************/
/* Modified by David A. Scott so could be better used for cryptograpic uses */
/* #define ASSERT 1 /* */
#define MAX 255			/* Maximum symbol */
#define N 8			/* number of bits */

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include <string.h>
#include "ad2hcaf.h"

extern Node    *tree;
extern Node    *lhead;
extern Node    *loc[MAX + 1];
static Node   **freelist = NULL;

Node          **
get_ppnode(void)
{
   Node          **tppnode;
   if (!freelist)
      return (Node **) malloc(sizeof(Node *));
   else {
      tppnode = freelist;
      freelist = (Node **) * tppnode;
      return tppnode;
   }
}

static void 
free_ppnode(Node ** ppnode)
{
   *ppnode = (Node *) freelist;
   freelist = ppnode;
}

void 
checkranks(Node * node)
{
   Node           *lnode;
   for (lnode = node; lnode; lnode = lnode->next) {
      assert(!lnode->next || lnode->next->weight >= lnode->weight);
      assert(lnode->head && *(lnode->head) && (*lnode->head)->weight == lnode->weight);
      if (lnode->next)
	 if (lnode->weight == lnode->next->weight)
	    assert(lnode->next->head == lnode->head);
	 else
	    assert(lnode->next->head != lnode->head);
   }
}
static int      KOUNT;
void 
dave(Node * node)
{
   if (!node->parent)
      return;
   KOUNT = 0;
   dave(node->parent);
   KOUNT++;
   if (node->parent->left == node)
      printf("l");
   else if (node->parent->right == node)
      printf("r");
   else {
      printf(" TREE ERROR \n");
      exit(0);
   }
}
void 
scott(Node * node)
{
   Node           *das;
   int             i, j;
   if (node->right && node->left) {
      for (i = 0, das = node->right; das = das->right;)
	 i++;
      for (j = 0, das = node->left; das = das->left;)
	 j++;
      if (i > j || (i = j && node->right < node->left)) {
	 das = node->right;
	 node->right = node->left;
	 node->left = das;
      }
   }
}

/* */
#if OLDEND == 1
void 
Zcott(void)
{
   Node           *das;
   Node           *node;
   int             i, j;
   /*
    printf(" here in Zcott \n");
    dump_tree(tree); */
   for (das = lhead; das; das = das->parent) {
      if (das->parent->right == das) {
	 das->parent->right = das->parent->left;
	 das->parent->left = das;
      }
   }
   /*
    printf(" here in Zcott top \n");
    dump_tree(tree);
    printf(" here in Zcott bottom \n");
   */
}
#endif
/**/
void 
dumptree(Node * node)
{				/* Debugging routine...dump the tree in
				 * prefix notation */
   if (!node)
      return;
   if (node->symbol == INTERNAL_NODE)
      printf("ww%8.8xww \n", node->weight);
   /* printf ("."); */
   else {
      printf("z%2.2xz", node->symbol);
      printf("W%8.8xW ", node->weight);
      dave(node);
      printf(" bits= %d\n", KOUNT);
   }
   if (node->left)
      assert(node->left->parent == node);
   if (node->right)
      assert(node->right->parent == node);
   dumptree(node->left);
   dumptree(node->right);
   if (node == tree)
      printf("\n");
}
/* */
void 
dump_tree(Node * node)
{				/* Debugging routine...dump the tree in
				 * prefix notation */
   if (!node)
      return;
   if (node->symbol == INTERNAL_NODE)
      printf("ww%8.8xww \n", node->weight);
   /* printf ("."); */
   else {
      printf("z%2.2xz", node->symbol);
      printf("W%8.8xW ", node->weight);
      dave(node);
      printf(" bits= %d\n", KOUNT);
   }
   if (node->prev)
      dump_tree(node->prev);
}
/* */
void 
dumplist(Node * node)
{				/* Debugging routine...dump the link list */
   while (node) {
      if (!node)
	 return;
      if (node->symbol == INTERNAL_NODE)
	 printf(".");
      else
	 printf("s%xs", node->symbol);
      printf("(%i)", node->weight);
      node = node->next;
   }
   printf("\n");
}

void 
usage(char **argv)
{
   fprintf(stderr, "Usage: %s inputfile outputfile conditiionfile \n", argv[0]);
}

void 
swap(Node * node1, Node * node2)
{				/* Swap the location of these two nodes in
				 * the tree */
   Node           *par1, *par2;


   par1 = node1->parent;
   par2 = node2->parent;

   if (par1) {
      if (par1->left == node1)
	 par1->left = node2;
      else {
#ifdef ASSERT
	 assert(par1->right == node1);
#endif
	 par1->right = node2;
      }
   } else
      tree = node2;

   if (par2) {
      if (par2->left == node2)
	 par2->left = node1;
      else {
#ifdef ASSERT
	 assert(par2->right == node2);
#endif
	 par2->right = node1;
      }
   } else
      tree = node1;

   node1->parent = par2;
   node2->parent = par1;
   scott(par1);
   scott(par2);
}

void 
swaplist(Node * node1, Node * node2)
{				/* Swap these two nodes in the linked list
				 * (update ranks) */
   Node           *par1;

   par1 = node1->next;
   node1->next = node2->next;
   node2->next = par1;

   par1 = node1->prev;
   node1->prev = node2->prev;
   node2->prev = par1;

   if (node1->next == node1)
      node1->next = node2;
   if (node2->next == node2)
      node2->next = node1;

   if (node1->next)
      node1->next->prev = node1;
   if (node2->next)
      node2->next->prev = node2;
   if (node1->prev)
      node1->prev->next = node1;
   if (node2->prev)
      node2->prev->next = node2;
#ifdef ASSERT
   assert(node1->next != node1);
   assert(node2->next != node2);
#endif
}

void 
increment(Node * node, int DAS)
{				/* Do the increments */
   Node           *lnode;

   if (!node)
      return;


   if (node->next != NULL && node->next->weight == node->weight) {
      lnode = *node->head;
#ifdef ASSERT
      assert(lnode != node);
      assert(lnode->parent != node);
      assert(lnode->weight == node->weight);
#endif
      if (lnode != node->parent)
	 swap(lnode, node);
      swaplist(lnode, node);
   }
   if (node->prev && node->prev->weight == node->weight)
      *node->head = node->prev;
   else {
      *node->head = NULL;
      free_ppnode(node->head);
   }

   node->weight = DAS + node->weight;
   /* scott(node); */



   if (node->next && node->next->weight < node->weight) {
      printf(" *** errir \n %x %x %x\n", (int) node->next->weight, (int) node->weight, DAS);
      exit(8);
   }
   if (node->next && node->next->weight == node->weight)
      node->head = node->next->head;
   else {
      node->head = get_ppnode();
      *node->head = node;
   }
   if (node->parent) {
      increment(node->parent, DAS);
      if (node->prev == node->parent) {
	 swaplist(node, node->parent);
	 if (*node->head == node)
	    *node->head = node->parent;
      }
   }
}
static int      XXX[MAX + 1] = {0, 0};
int             ZZZ[MAX + 1] = {0, 0};
static int      YYY = MAX + 1;

static Node    *Sstart = NULL;
static Node    *Ssend = NULL;
/* */

#if OLDEND == 1

void 
undo_tree(void)
{
   /* start with pointer to chain of modifed sites */
   Node           *node;
   node = Sstart;
   while (node != NULL) {
      node->parent = node->sparent;
      node->left = node->sleft;
      node->right = node->sright;
      node = node->snext;
      Sstart->snext = NULL;
      Sstart = node;
   }
   Sstart = NULL;
   Ssend = NULL;
}
/* */
void 
do_tree(Node * node)
{
   if (Sstart == NULL) {	/* adds new node if necessary to s chain */
      Sstart = node;
   }
   if (node->snext == NULL && Ssend != node) {
      node->sparent = node->parent;
      node->sleft = node->left;
      node->sright = node->right;
      if (Ssend != NULL)
	 Ssend->snext = node;
      Ssend = node;
   }
}
/* */

void 
do_stretch(Node * node)
{
   /*
    * node is such that parent and alternate child of node is an internal
    * node. Restructure codes such that  node is brought into the chain thus
    * making longest path longer by one. use do_tree for any node affected
    */
   Node           *t, *ta, *tal, *tar;
   t = node->parent;
   ta = t->right == node ? t->left : t->right;
   if (ta->right->weight >= ta->right->weight) {
      tar = ta->right;
      tal = ta->left;
   } else {
      tar = ta->left;
      tal = ta->right;
   }
   do_tree(node);
   do_tree(t);
   do_tree(ta);
   do_tree(tar);
   do_tree(tal);
   node->parent = ta;
   tar->parent = t;
   t->right = tar;
   t->left = ta;
   ta->right = tal;
   ta->left = node;
}
void 
dodo_tree(void)
{
   /* converts tree to one for low symbol complete use */
   int             i;
   Node           *t;
   Zcott();
   for (i = -1, t = lhead; t != NULL; t = t->parent)
      i++;			/* number of bits  in path */
   /* printf(" number of bits before %u \n",i); */
   while (i++ < 8) {		/* make sure eight in path */
      t = lhead;
      while ((t->parent->left != t && t->parent->left->symbol != INTERNAL_NODE) ||
       (t->parent->right != t && t->parent->right->symbol != INTERNAL_NODE))
	 t = t->parent;
      do_stretch(t);
   }
   for (i = -1, t = tree; t != NULL; t = t->left)
      i++;			/* number of bits  in path */
   if (i < 8) {
      printf(" length of zero token %u should be 8 or more\n", i);
      exit(3);
   }
}
#endif
/************ build tree from table********/



void 
add_ref(int ch)
{
   int             i;
   Node           *tnode, *tnode2;
   if (!YYY)
      increment(loc[ch], 4 * (MAX + 1));
   else if (!XXX[ch]) {
      /*
           if (YYY <= 201)printf("here f \n");
           printf(" topV baby %x weight is %x \n",ch,(int)loc[ch]->weight);
           printf(" topV parent %x weight is %x \n",ch,(int)loc[ch]->parent->weight);
           printf(" topV lhead %x weight is %x \n",ch,(int)lhead->weight);
      */
      while (loc[ch]->weight < 2 * (MAX + 1))
	 increment(loc[ch], 1);
      /*
           printf(" topW baby %x weight is %x \n",ch,(int)loc[ch]->weight);
           printf(" topW parent %x weight is %x \n",ch,(int)loc[ch]->parent->weight);
           printf(" topW lhead %x weight is %x \n",ch,(int)lhead->weight);
      */


      while (loc[ch]->parent->weight < 4 * (MAX + 1)) {
	 while (lhead->prev)
	    lhead = lhead->prev;
	 if (lhead == loc[ch])
	    break;
	 increment(lhead, 1);
      }
      while (lhead->prev)
	 lhead = lhead->prev;	/* get head */

      /*
           printf(" topX baby %x weight is %x \n",ch,(int)loc[ch]->weight);
           printf(" topX parent %x weight is %x \n",ch,(int)loc[ch]->parent->weight);
           printf(" topX lhead %x weight is %x \n",ch,(int)lhead->weight);
      */

      /* parant weight is 2*(MAX+1) */
      /* printf(" synbol %x  symbols left = %d \n",loc[ch]->symbol,--YYY); */
      --YYY;
      /*
           printf(" did new for %x weight is %x \n",ch,(int)loc[ch]->weight);
           printf(" did parant  weight is %x \n",(int)loc[ch]->parent->weight);
      */
      if ((loc[ch]->weight < 2 * (MAX + 1) || loc[ch]->parent->weight != 4 * (MAX + 1)) && YYY) {
	 printf(" magor error \n");
	 exit(1);
      }
      XXX[ch] = 1;
      increment(loc[ch], 2 * (MAX + 1));

   } else {

      increment(loc[ch], 2 * (MAX + 1));
      increment(loc[ch], 2 * (MAX + 1));
   }
}

/* */
static int      ZOLD = 300;
void 
add_refx1(int ch)
{
   if (ZOLD == 300)
      ZOLD = ch;
   if (!ZZZ[ch] && ZOLD != ch) {
      add_ref(ch);
   }
   ZZZ[ch]++;
}

/* */

void 
tree_fin(void)
{
   int             i, j, k;
   Node           *t;
   for (i = 0, j = 0; i < 256; i++)
      if (ZZZ[i])
	 j++;			/* j is number of unique charcters */
#if OLDEND == 1

   if (j < 9) {
      printf(" you have %u variables you need at least nine \n", j);
      exit(3);
   }
#else
   if (j < 2) {
      printf(" you have %u variables you need at least two \n", j);
      exit(3);
   }
#endif
   /* printf(" here x %u \n",j);k=0; */
   for (t = tree; t; t = t->prev) {
      if (t->weight == (long long) 2 * (MAX + 1)) {
	 lhead = t;
	 t->prev = NULL;
	 t->right = NULL;
	 t->left = NULL;
	 t->symbol = ZOLD;
	 loc[ZOLD] = t;
	 break;
      }
      k++;
   }
   /*
    * printf(" here y %u \n",k); dump_tree(tree); printf(" first tree done
    * \n");
    */
   YYY = 1;
   add_ref(ZOLD);
   /*
    dump_tree(tree);
   printf(" here z \n"); */
   YYY = j;			/* reset to number of symbols */
   for (t = tree; t != NULL; t = t->prev)
      t->weight >>= 10;
   /* dump_tree(tree); */
   /* no load for ratio of occurring */
   for (i = 0; i < 256; i++)
      XXX[i] = 0;
   for (i = 0; i < 256; i++) {
      while (ZZZ[i] > 1) {
	 add_ref(i);
	 --ZZZ[i];
      }
      if (!ZZZ[i])
	 XXX[i] = 1;
   }
   /*
    printf(" dump end \n");
    dump_tree(tree); */
}