home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / altsrcs / 1 / 1774 < prev    next >
Encoding:
Internet Message Format  |  1990-12-28  |  11.0 KB
  1. From: gtoal@tharr.UUCP (Graham Toal)
  2. Newsgroups: alt.sources
  3. Subject: dynhuff.c - C source of dynamic huffman alg
  4. Message-ID: <951@tharr.UUCP>
  5. Date: 3 Sep 90 11:24:42 GMT
  6.  
  7. Archive-name: dynhuff.c
  8.  
  9. Well, after posting that last article, I felt a bit antisocial leaving
  10. the conversion to C to some luckless soul, so I had a quick hack at it
  11. myself.  This C version wraps up the previous code into an actual
  12. usable program, complete with error checking and magic numbers.
  13.  
  14. ----- cut here -----
  15. /*
  16.   ALGORITHM 673,
  17.  
  18.   ACM Transactions on Mathematical Software, Vol 15, No 2, Pages 158-167. 
  19.  
  20.   Jeffrey Scott Vitter
  21.   Brown University
  22.  
  23.   This file coded up from the paper above by Graham Toal <gtoal@ed.ac.uk>
  24.  
  25.   This is a one-pass dynamic Huffman code generator.  I supply a trivial
  26.   interface for testing.  Real-world use would require that you firstly
  27.   translate this into C (please post here when you do) and secondly
  28.   modify the IO to write binary files. (This writes a text file of
  29.   0's and 1's for demonstration purposes)
  30.  
  31.   Also it needs some logic for what happens on } of file.
  32.  
  33. */
  34.  
  35. #include <stdio.h>
  36. #include <string.h>
  37. #include <stdlib.h>
  38.  
  39. #define HUFF_MAGIC 240859L
  40.  
  41. FILE *input_file;
  42. FILE *output_file;
  43.  
  44. #ifndef TRUE
  45. #define TRUE (0==0)
  46. #define FALSE (0!=0)
  47. #endif
  48.  
  49. #define  n  256
  50. #define  bb  (n*2 + 1)
  51.  
  52. int alpha[n+1];
  53. int rep[n+1];
  54. int block[bb+1];
  55. int weight[bb+1];
  56. int parent[bb+1];
  57. int parity[bb+1];
  58. int rtChild[bb+1];
  59. int first[bb+1];
  60. int last[bb+1];
  61. int prevBlock[bb+1];
  62. int nextBlock[bb+1];
  63. int availBlock;
  64. int stack[n+1];
  65. int a;
  66. int M, E, R, Z;
  67.  
  68. void Initialize(void)
  69. {
  70. int i;
  71.  
  72.   M = 0; E = 0; R = -1; Z = 2*n - 1;
  73.   for (i = 1; i <=n; i++) {
  74.     M = M+1; R = R+1;
  75.     if (R*2 == M) { E = E+1; R = 0; }
  76.     alpha[i] = i; rep[i] = i;
  77.   }
  78.   /* Initialize node n as the 0-node */
  79.   block[n] = 1; prevBlock[1] = 1; nextBlock[1] = 1; weight[1] = 0;
  80.   first[1] = n; last[1] = n; parity[1] = 0;
  81.   /* Initialize available block list */
  82.   availBlock = 2;
  83.   for (i = availBlock; i <= Z-1; i++) nextBlock[i] = i+1;
  84.   nextBlock[Z] = 0;
  85. }
  86.  
  87. static int nextbitpos = 0;
  88. void Transmit(int i)
  89. {
  90. static int byte = 0;
  91.  
  92.   byte = (byte << 1) | (i&1); nextbitpos ++;
  93.   
  94.   if (nextbitpos == 8) {
  95.     if (fputc(byte, output_file) == EOF) {
  96.       fprintf(stderr, "Error writing output file - disk full?\n");
  97.       exit(0);
  98.     }
  99.     byte = 0; nextbitpos = 0;
  100.   }
  101. }
  102.  
  103. int Receive(void)
  104. {
  105. static int byte;
  106. static int bitsleft = 0;
  107. int bit;
  108.  
  109.   if (bitsleft == 0) {
  110.     for (;;) {
  111.       byte = fgetc(input_file);
  112.       if (byte == EOF) {
  113.         return(0);
  114.       }
  115.       break;
  116.     }
  117.     bitsleft = 8;
  118.   }
  119.   bit = (byte >> 7) & 1;
  120.   byte = (byte << 1);
  121.   bitsleft -= 1;
  122.   return(bit);
  123. }
  124.  
  125. void EncodeAndTransmit(int j)
  126. {
  127. int i, ii, q, t, root;
  128.  
  129.   q = rep[j]; i = 0;
  130.   if (q <= M) { /* Encode letter of zero weight */
  131.     q = q - 1;
  132.     if (q < R*2) {
  133.       t = E+1;
  134.     } else {
  135.       q = q - R; t = E;
  136.     }
  137.     for (ii = 1; ii <= t; ii++) {
  138.       i = i + 1; stack[i] = q % 2;
  139.       q = q / 2;
  140.     }
  141.     q = M;
  142.   }
  143.   if (M == n) root = n; else root = Z;
  144.   while (q != root) { /* Traverse up the tree */
  145.     i = i + 1; stack[i] = (first[block[q]] - q + parity[block[q]]) % 2;
  146.     q = parent[block[q]] - (first[block[q]] - q + 1 - parity[block[q]]) / 2;
  147.   }
  148.   for (ii = i; ii >= 1; --ii) {
  149.     Transmit(stack[ii]);
  150.   }
  151. }
  152.  
  153. int FindChild(int j, int parity)
  154. {
  155. int delta, right, gap;
  156.  
  157.   delta = 2*(first[block[j]]-j) + 1 - parity;
  158.   right = rtChild[block[j]]; gap = right - last[block[right]];
  159.   if (delta <= gap) return(right-delta);
  160.   else {
  161.     delta = delta - gap - 1;
  162.     right = first[prevBlock[block[right]]]; gap = right - last[block[right]];
  163.     if (delta <= gap) return(right-delta);
  164.     else return(first[prevBlock[block[right]]] - delta + gap + 1);
  165.   }
  166. }
  167.  
  168. int ReceiveAndDecode(void)
  169. {
  170. int i, q;
  171.  
  172.   if (M == n) q = n; else q = Z; /* Set q to the root node */
  173.   while (q > n) /* Traverse down the tree */
  174.     q = FindChild(q, Receive());
  175.   if (q == M) { /* Decode 0-node */
  176.     q = 0;
  177.     for (i = 1; i <= E; i++) q = q*2 + Receive();
  178.     if (q < R) q = q*2 + Receive(); else q = q + R;
  179.     q = q + 1;
  180.   }
  181.   return(alpha[q]);
  182. }
  183.  
  184. void InterchangeLeaves(int e1, int e2)
  185. {
  186. int temp;
  187.  
  188.   rep[alpha[e1]] = e2; rep[alpha[e2]] = e1;
  189.   temp = alpha[e1]; alpha[e1] = alpha[e2]; alpha[e2] = temp;
  190. }
  191.  
  192. /* These should be local to Update, but visible to FindNode & SlideAndInc */
  193. int q, leafToIncrement, bq, b, oldParent, oldParity, nbq, par, bpar;
  194. int slide;
  195.  
  196. void FindNode(int k)
  197. {
  198.   q = rep[k]; leafToIncrement = 0;
  199.   if (q <= M) { /* A zero weight becomes positive */
  200.     InterchangeLeaves(q, M);
  201.     if (R == 0) { R = M / 2; if (R > 0) E = E-1; }
  202.     M = M-1; R = R-1; q = M+1; bq = block[q];
  203.     if (M > 0) {
  204.       /* Split the 0-node into an internal node with two children.  The new
  205.         0-node is node M; the old 0-node is node M+1; the new parent of
  206.         nodes M and M+1 is node M+n */
  207.       block[M] = bq; last[bq] = M; oldParent = parent[bq];
  208.       parent[bq] = M+n; parity[bq] = 1;
  209.       /* Create a new internal block of zero weight for node M+n */
  210.       b = availBlock; availBlock = nextBlock[availBlock];
  211.       prevBlock[b] = bq; nextBlock[b] = nextBlock[bq];
  212.       prevBlock[nextBlock[bq]] = b; nextBlock[bq] = b;
  213.       parent[b] = oldParent; parity[b] = 0; rtChild[b] = q;
  214.       block[M+n] = b; weight[b] = 0;
  215.       first[b] = M+n; last[b] = M+n;
  216.       leafToIncrement = q; q = M+n;
  217.     }
  218.   } else { /* Interchange q with the first node in q's block */
  219.     InterchangeLeaves(q, first[block[q]]);
  220.     q = first[block[q]];
  221.     if ((q == M+1) && (M > 0)) {
  222.       leafToIncrement = q; q = parent[block[q]];
  223.     }
  224.   }
  225. }
  226.  
  227. void SlideAndIncrement(void)
  228. { /* q is currently the first node in its block */
  229.   bq = block[q]; nbq = nextBlock[bq];
  230.   par = parent[bq]; oldParent = par; oldParity = parity[bq];
  231.   if ((
  232.        (q <= n) && (first[nbq] > n) && (weight[nbq] == weight[bq]))
  233.      ||
  234.        ((q > n) && (first[nbq] <= n) && (weight[nbq] == weight[bq]+1)
  235.      )) {     /* Slide q over the next block */
  236.     slide = TRUE;
  237.     oldParent = parent[nbq]; oldParity = parity[nbq];
  238.     /* Adjust child pointers for next higher level in tree */
  239.     if (par > 0) {
  240.       bpar = block[par];
  241.       if (rtChild[bpar] == q) {
  242.         rtChild[bpar] = last[nbq];
  243.       } else if (rtChild[bpar] == first[nbq]) {
  244.         rtChild[bpar] = q;
  245.       } else rtChild[bpar] = rtChild[bpar]+1;
  246.       if (par != Z) {
  247.         if (block[par+1] != bpar) {
  248.           if (rtChild[block[par+1]] == first[nbq])
  249.             rtChild[block[par+1]] = q;
  250.           else if (block[rtChild[block[par+1]]] == nbq) {
  251.             rtChild[block[par+1]] = rtChild[block[par+1]]+1;
  252.           }
  253.         }
  254.       }
  255.     }
  256.     /* Adjust parent pointers for block nbq */
  257.     parent[nbq] = parent[nbq] - 1 + parity[nbq]; parity[nbq] = 1-parity[nbq];
  258.     nbq = nextBlock[nbq];
  259.   } else slide = FALSE;
  260.   if ((
  261.       ((q <= n) && (first[nbq] <= n))
  262.       ||
  263.       ((q > n) && (first[nbq] > n))
  264.      )
  265.      && (weight[nbq] == weight[bq]+1)) {
  266.     /* Merge q into the block of weight one higher */
  267.     block[q] = nbq; last[nbq] = q;
  268.     if (last[bq] == q) { /* q's old block disappears */
  269.       nextBlock[prevBlock[bq]] = nextBlock[bq];
  270.       prevBlock[nextBlock[bq]] = prevBlock[bq];
  271.       nextBlock[bq] = availBlock; availBlock = bq;
  272.     } else {
  273.       if (q > n) rtChild[bq] = FindChild(q-1, 1);
  274.       if (parity[bq] == 0) parent[bq] = parent[bq] - 1;
  275.       parity[bq] = 1-parity[bq];
  276.       first[bq] = q-1;
  277.     }
  278.   } else if (last[bq] == q) {
  279.     if (slide) { /* q's block is slid forward in the block list */
  280.       prevBlock[nextBlock[bq]] = prevBlock[bq];
  281.       nextBlock[prevBlock[bq]] = nextBlock[bq];
  282.       prevBlock[bq] = prevBlock[nbq]; nextBlock[bq] = nbq;
  283.       prevBlock[nbq] = bq; nextBlock[prevBlock[bq]] = bq;
  284.       parent[bq] = oldParent; parity[bq] = oldParity;
  285.     }
  286.     weight[bq] = weight[bq]+1;
  287.   } else {
  288.     /* A new block is created for q */
  289.     b = availBlock; availBlock = nextBlock[availBlock];
  290.     block[q] = b; first[b] = q; last[b] = q;
  291.     if (q > n) {
  292.       rtChild[b] = rtChild[bq];
  293.       rtChild[bq] = FindChild(q-1, 1);
  294.       if (rtChild[b] == q-1) parent[bq] = q;
  295.       else if (parity[bq] == 0) parent[bq] = parent[bq]-1;
  296.     } else if (parity[bq] == 0) parent[bq] = parent[bq]-1;
  297.     first[bq] = q-1; parity[bq] = 1-parity[bq];
  298.     /* Insert q's in block in its proper place in the block list */
  299.     prevBlock[b] = prevBlock[nbq]; nextBlock[b] = nbq;
  300.     prevBlock[nbq] = b; nextBlock[prevBlock[b]] = b;
  301.     weight[b] = weight[bq]+1;
  302.     parent[b] = oldParent; parity[b] = oldParity;
  303.   }
  304.   /* Move q one level higher in the tree */
  305.   if (q <= n) q = oldParent; else q = par;
  306. }
  307.  
  308. void Update(int k)
  309. {
  310.   /* Set q to the node whose weight should increase */
  311.   FindNode(k);
  312.   while (q > 0) {
  313.     /* At this point, q is the first node in its block.  Increment q's weight
  314.       by 1 and slide q if necessary over the next block to maintain the
  315.       invariant.  Then set q to the node one level higher that needs
  316.       incrementing next */
  317.     SlideAndIncrement();
  318.   }
  319.   /* Finish up some special cases involving the 0-node */
  320.   if (leafToIncrement != 0) {
  321.     q = leafToIncrement;
  322.     SlideAndIncrement();
  323.   }
  324. }
  325.  
  326. void hfputw(long w, FILE *f)
  327. {
  328.   fputc((int)((w>>24L)&255L), f);
  329.   fputc((int)((w>>16L)&255L), f);
  330.   fputc((int)((w>> 8L)&255L), f);
  331.   fputc((int)((w     )&255L), f);
  332. }
  333.  
  334. long hfgetw(FILE *f)
  335. {
  336. long w;
  337.   w = fgetc(f); w = w<<8L;
  338.   w |= fgetc(f); w = w<<8L;
  339.   w |= fgetc(f); w = w<<8L;
  340.   w |= fgetc(f);
  341.   return(w);
  342. }
  343.  
  344. int main(int argc, char **argv)
  345. {
  346. long fsize;
  347.  
  348.   if (argc != 4 || *argv[1] != '-') {
  349.     fprintf(stderr, "syntax: %s {-e,-d} input output\n", argv[0]);
  350.     exit(0);
  351.   }
  352.  
  353.   Initialize();
  354.  
  355.   input_file = fopen(argv[2], "rb");
  356.   if (input_file == NULL) {
  357.     fprintf(stderr, "%s: cannot open input file %s\n", argv[0], argv[2]);
  358.     exit(0);
  359.   }
  360.  
  361.   if (strcmp(argv[1], "-e") == 0) {
  362.     output_file = fopen(argv[3], "wb");
  363.     if (output_file == NULL) {
  364.       fprintf(stderr, "%s: cannot open output file %s\n", argv[0], argv[3]);
  365.       fclose(input_file);
  366.       exit(0);
  367.     }
  368.     fseek(input_file, 0L, SEEK_END);
  369.     fsize = ftell(input_file);
  370.     fclose(input_file);
  371.     input_file = fopen(argv[2], "rb");
  372.     hfputw(HUFF_MAGIC, output_file);
  373.     hfputw(fsize, output_file);
  374.     for (;;) {
  375.       a = fgetc(input_file);
  376.       if (a == EOF) break;
  377.       EncodeAndTransmit(a);
  378.       Update(a);
  379.     }
  380.     while (nextbitpos != 0) Transmit(1);
  381.     fclose(input_file);
  382.     fclose(output_file);
  383.   } else if (strcmp(argv[1], "-d") == 0) {
  384.     long check_magic;
  385.  
  386.     check_magic = hfgetw(input_file);
  387.     if (check_magic != HUFF_MAGIC) {
  388.       fprintf(stderr, "%s: input file %s not huffman encoded (%ld vs %ld)\n",
  389.         argv[0], argv[2], check_magic, HUFF_MAGIC);
  390.       exit(0);
  391.     }
  392.     output_file = fopen(argv[3], "wb");
  393.     fsize = hfgetw(input_file);
  394.     for (;;) {
  395.       a = ReceiveAndDecode();
  396.       if (fputc(a, output_file) == EOF) {
  397.         fprintf(stderr, "Error writing output file - disk full?\n");
  398.         exit(0);
  399.       }
  400.       if (--fsize == 0L) break;
  401.       Update(a);
  402.     }
  403.     fclose(input_file);
  404.     fclose(output_file);
  405.   } else {
  406.     fprintf(stderr, "syntax: %s {-e,-d} input output\n", argv[0]);
  407.   }
  408.   exit(0);
  409. }
  410.