home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1999 mARCH / PCWK3A99.iso / Linux / DDD331 / DDD-3_1_.000 / DDD-3_1_ / ddd-3.1.1 / ddd / huffencode.C < prev    next >
C/C++ Source or Header  |  1998-06-29  |  7KB  |  320 lines
  1. // $Id: huffencode.C,v 1.12 1998/06/29 09:08:20 zeller Exp $ -*- C++ -*-
  2. // Huffman-encode standard input
  3.  
  4. // Copyright (C) 1996-1998 Technische Universitaet Braunschweig, Germany.
  5. // Written by Andreas Zeller <zeller@ips.cs.tu-bs.de>.
  6. // 
  7. // This file is part of DDD.
  8. // 
  9. // DDD is free software; you can redistribute it and/or
  10. // modify it under the terms of the GNU General Public
  11. // License as published by the Free Software Foundation; either
  12. // version 2 of the License, or (at your option) any later version.
  13. // 
  14. // DDD is distributed in the hope that it will be useful,
  15. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. // See the GNU General Public License for more details.
  18. // 
  19. // You should have received a copy of the GNU General Public
  20. // License along with DDD -- see the file COPYING.
  21. // If not, write to the Free Software Foundation, Inc.,
  22. // 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  23. // 
  24. // DDD is the data display debugger.
  25. // For details, see the DDD World-Wide-Web page, 
  26. // `http://www.cs.tu-bs.de/softech/ddd/',
  27. // or send a mail to the DDD developers <ddd@ips.cs.tu-bs.de>.
  28.  
  29. char huffencode_rcsid[] = 
  30.     "$Id: huffencode.C,v 1.12 1998/06/29 09:08:20 zeller Exp $";
  31.  
  32. #include <limits.h>
  33. #include <iostream.h>
  34. #include <strstream.h>
  35. #include <iomanip.h>
  36. #include <stdlib.h>
  37.  
  38. #include "assert.h"
  39. #include "strclass.h"
  40. #include "cook.h"
  41. #include "DynArray.h"
  42. #include "bool.h"
  43.  
  44. #ifndef EXIT_SUCCESS
  45. #define EXIT_SUCCESS 0
  46. #endif
  47.  
  48. #ifndef EXIT_FAILURE
  49. #define EXIT_FAILURE 1
  50. #endif
  51.  
  52. // A node of the Huffman tree
  53. struct HuffNode {
  54.     bool isleaf;
  55.     union {
  56.     struct {        // Internal node:
  57.         HuffNode *left;    // Left child   (0)
  58.         HuffNode *right;    // Right child  (1)
  59.     } i;
  60.     struct {        // Leaf node:
  61.         char c;        // Character
  62.     } l;
  63.     };
  64.     int sum;            // Sum of the weights in the leaves
  65.     HuffNode *next;        // For queue usage
  66.     int number;            // For print usage
  67.  
  68.     // Constructor - internal node
  69.     HuffNode(HuffNode *l, HuffNode *r)
  70.     : isleaf(false), sum(l->sum + r->sum), next(0)
  71.     {
  72.     i.left  = l;
  73.     i.right = r;
  74.     }
  75.  
  76.     // Constructor - leaf node
  77.     HuffNode(char c, int s)
  78.     : isleaf(true), sum(s), next(0)
  79.     {
  80.     l.c = c;
  81.     }
  82. };
  83.  
  84. // Insert NODE into QUEUE such that the node with maximum sum comes first
  85. static void insert(HuffNode*& queue, HuffNode *node)
  86. {
  87.     if (queue == 0)
  88.     {
  89.     queue = node;
  90.     }
  91.     else if (queue->sum > node->sum)
  92.     {
  93.     node->next = queue;
  94.     queue = node;
  95.     }
  96.     else
  97.     {
  98.     insert(queue->next, node);
  99.     }
  100. }
  101.  
  102. // Extract the node with minimum sum from QUEUE (i.e. the last)
  103. static HuffNode *extract_min(HuffNode*& queue)
  104. {
  105.     HuffNode *node = queue;
  106.     if (queue != 0)
  107.     queue = queue->next;
  108.     return node;
  109. }
  110.  
  111. // Create a queue sorted according to occurrences of charatcer in S
  112. static HuffNode *initial_queue(const string& s)
  113. {
  114.     int occurrences[UCHAR_MAX + 1];
  115.  
  116.     unsigned int c;
  117.     for (c = 0; c < UCHAR_MAX + 1; c++)
  118.     occurrences[c] = 0;
  119.     for (int i = 0; i < int(s.length()); i++)
  120.     occurrences[(unsigned char)s[i]]++;
  121.  
  122.     HuffNode *queue = 0;
  123.     for (c = 0; c < UCHAR_MAX + 1; c++)
  124.     if (occurrences[c] > 0)
  125.         insert(queue, new HuffNode(c, occurrences[c]));
  126.  
  127.     return queue;
  128. }
  129.  
  130. // Return the length of QUEUE
  131. static int length(HuffNode *queue)
  132. {
  133.     int len = 0;
  134.     while (queue != 0)
  135.     {
  136.     len++;
  137.     queue = queue->next;
  138.     }
  139.  
  140.     return len;
  141. }
  142.  
  143. // Create a Huffman tree from S
  144. static HuffNode *huffman(const string& s)
  145. {
  146.     HuffNode *queue = initial_queue(s);
  147.     int n = length(queue);
  148.  
  149.     for (int i = 0; i < n - 1; i++)
  150.     {
  151.     HuffNode *x = extract_min(queue);
  152.     HuffNode *y = extract_min(queue);
  153.     insert(queue, new HuffNode(x, y));
  154.     }
  155.  
  156.     return extract_min(queue);
  157. }
  158.  
  159. // Write Huffman tree TREE on standard output
  160. static void write_huffman(HuffNode *tree)
  161. {
  162.     static int tics = 0;
  163.  
  164.     if (tree == 0)
  165.     return;
  166.  
  167.     if (tree->isleaf)
  168.     {
  169.     tree->number = tics++;
  170.     cout << "static const HuffCode _huff" << tree->number 
  171.          << " = {0, (HuffCode *)'" << cook(tree->l.c) << "'};\n";
  172.     }
  173.     else
  174.     {
  175.     write_huffman(tree->i.left);
  176.     write_huffman(tree->i.right);
  177.  
  178.     tree->number = tics++;
  179.     cout << "static const HuffCode _huff" << tree->number 
  180.          << " = {&_huff" << tree->i.left->number 
  181.          << ", &_huff" << tree->i.right->number << "};\n";
  182.     }
  183. }
  184.  
  185. // Fill CODES[C] with a [01]+ string denoting the encoding of C in TREE
  186. static void init_codes(string codes[UCHAR_MAX + 1], HuffNode *tree, 
  187.                string prefix = "")
  188. {
  189.     if (tree == 0)
  190.     return;
  191.  
  192.     if (tree->isleaf)
  193.     {
  194.     codes[(unsigned char)tree->l.c] = prefix;
  195.     }
  196.     else
  197.     {
  198.     init_codes(codes, tree->i.left,  prefix + "0");
  199.     init_codes(codes, tree->i.right, prefix + "1");
  200.     }
  201. }
  202.  
  203. // Convert a [01]+ string to a byte
  204. static char bits_to_byte(const string& bits)
  205. {
  206.     unsigned char c = 0;
  207.  
  208.     for (int i = 0; i < int(bits.length()); i++)
  209.     c = (c << 1) | (bits[i] == '0' ? 0 : 1);
  210.  
  211.     // clog << "bits_to_byte(" << cook(bits) << ") = " << int(c) << "\n";
  212.  
  213.     return (char)c;
  214. }
  215.  
  216. // Number of bits per character
  217. const int BITS_PER_CHAR = 8;
  218.  
  219. // Encode TEXT using the Huffman tree TREE
  220. static string encode(const string& text, HuffNode *tree)
  221. {
  222.     string codes[UCHAR_MAX + 1];
  223.  
  224.     init_codes(codes, tree);
  225.  
  226.     if (tree != 0)
  227.     {
  228.     unsigned int c;
  229.     cout << "// Encoding:\n";
  230.     for (c = 0; c < UCHAR_MAX + 1; c++)
  231.     {
  232.         if (codes[c] != "")
  233.         cout << "// '" << cook((char)(unsigned char)c)
  234.              << "'\t" << codes[c] << "\n";
  235.     }
  236.     }
  237.  
  238.     ostrstream bit_encoding_os;
  239.     int i;
  240.     for (i = 0; i < int(text.length()); i++)
  241.     bit_encoding_os << codes[(unsigned char)text[i]];
  242.     string bit_encoding(bit_encoding_os);
  243.  
  244.     // cout << "\n// " << bit_encoding << "\n";
  245.  
  246.     ostrstream byte_encoding;
  247.     for (i = 0; i < int(bit_encoding.length()) - BITS_PER_CHAR; 
  248.      i += BITS_PER_CHAR)
  249.     {
  250.     byte_encoding << bits_to_byte(bit_encoding.at(i, BITS_PER_CHAR));
  251.     }
  252.     byte_encoding << bits_to_byte(bit_encoding.from(i));
  253.  
  254.     return byte_encoding;
  255. }
  256.  
  257. // Write encoded text BYTE_ENCODING on standard output
  258. static void write_encoding(const string& byte_encoding)
  259. {
  260.     cout << "static const char hufftext[" 
  261.      << byte_encoding.length() + 1 << "] = \n\"";
  262.  
  263.     int p = 0;
  264.  
  265.     while (p < int(byte_encoding.length()))
  266.     {
  267.     if (p > 0 && p % 16 == 0)
  268.         cout << "\"\n\"";
  269.  
  270.     cout << "\\" << oct << setw(3) 
  271.          << setfill('0') << int((unsigned char)byte_encoding[p]);
  272.  
  273.     p++;
  274.     }
  275.  
  276.     cout << "\";\n";
  277. }    
  278.  
  279. // Read the string S from standard input
  280. static void read_input(string& s)
  281. {
  282.     ostrstream os;
  283.     char c;
  284.  
  285.     while (cin.get(c))
  286.     os << c;
  287.  
  288.     s = os;
  289. }
  290.  
  291. // Main program.  Read a text from standard input, write huffman tree
  292. // and encoded text on standard output.
  293. int main()
  294. {
  295.     string text;
  296.  
  297.     read_input(text);
  298.     HuffNode *tree = huffman(text);
  299.     string encoding = encode(text, tree);
  300.  
  301.     if (tree != 0)
  302.     {
  303.     cout << "\n";
  304.     write_huffman(tree);
  305.     cout << "\n";
  306.     cout << "static const HuffCode *const huffcode = &_huff" 
  307.          << tree->number << ";\n";
  308.     }
  309.     else
  310.     {
  311.     cout << "static const HuffCode *const huffcode = 0;\n";
  312.     }
  313.  
  314.     cout << "static const int hufflength = " << text.length() << ";\n";
  315.  
  316.     write_encoding(encoding);
  317.  
  318.     return EXIT_SUCCESS;
  319. }
  320.