2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
24 * COMPONENT_NAME: austext
26 * FUNCTIONS: build_tree
39 * (C) COPYRIGHT International Business Machines Corp. 1990,1996
41 * Licensed Materials - Property of IBM
42 * US Government Users Restricted Rights - Use, duplication or
43 * disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
45 /************************** HUFFCODE.C ******************************
46 * $XConsortium: huffcode.c /main/9 1996/11/14 15:31:05 rcs $
48 * Counts frequency of occurrance of every possible byte value of input text.
49 * Creates Huffman Code Table based on byte frequencies and writes it
50 * in 2 formats to 2 different output files.
51 * The encode table (.huf) maintains the frequency counts and explicitly
52 * includes the huffman code strings. Generally speaking, the .huf file
53 * is intended for humans to read. The decode table (.c) is an array
54 * of integers meant to be compiled into an object module, then linked
55 * into the decode program. The .c format closely resembles the original
56 * huffman code tree in this program.
57 * By keeping the tree as an obscure array of integers,
58 * the huffman code can double as an encryption technique,
59 * and the decoding method kept somewhat proprietary.
61 * For a good discussion of Huffman codes and related algorithms,
62 * see "Data Compression Techniques and Applications Hardware and
63 * Software Considerations" by Gilbert Held and Thomas R. Marshall.
64 * The tree itself is balanced to minimize longest bitstring length
65 * per Eugene Schwartz, Information and Control 7, 37-44 (1964).
67 * At beginning of each new execution, the program tries to
68 * open the .huf table file and continue byte frequency counting
70 * If the .huf file doesn't exist, the table's counts are
71 * initialized to zeroes. The .c decode table is recomputed fresh
72 * each run, whether it existed before or not.
74 * If the input file is not specified then the frequencies in the table
75 * are not changed, and the huffman codes are recomputed with the
76 * existing frequencies.
78 * THIS PROGRAM DOES NOT CHECK .HUF FILE FORMAT!--it had better be correct.
80 * HUFFMAN ENCODE TABLE (.huf) FILE FORMAT:
81 * Each line represents each possible byte value (0 - 255),
82 * the huffman 'literal' character (#256), or comments.
83 * There are exactly 257 lines sorted by decreasing count.
84 * There are four fields, each separated by one or more tabs (\t).
86 * 1. CHARACTER. a number from 0 to 256.
88 * The 'character' represented by the number 256 is the literal.
89 * it represents all characters whose frequency is so low that
90 * there is no huffman code translation--this reduces the max
91 * length of the coded bit string when there are lots of zero
92 * or low frequency bytes in the input. For example,
93 * pure ascii text files only occasionally have byte values
94 * less than 32 (control chars) and rarely greater than 127
95 * (high order bit turned on).
97 * 2. HUFFMAN CODE. a string of binary digits (0's and 1's).
98 * Each string is unique to that character.
99 * This field will consist of a single blank, when the character
100 * will be coded by the huffman literal. If the code of
101 * the literal itself is blank, then literal coding is
102 * not used in this table--all characters are represented
103 * by complete huffman code strings.
105 * 3. COUNT. The number of times this character appeared in the text.
106 * The literal's count equals the sum of the counts of all the
107 * real characters which are represented by the literal.
108 * The literal's count may be 0 if all the characters it
109 * represents have zero frequencies.
111 * 4. COMMENTS. A label depicting the printable char or its description.
113 * HUFFMAN DECODE TABLE (.c) FILE FORMAT:
114 * A sequence of integers formatted as a C array of integer pairs
115 * and intended to be compiled and linked into the decode program.
116 * Each huffman tree node contains two integers.
117 * The root of the tree is the LAST integer pair.
118 * The first (left) integer contains the array index down the '0' branch,
119 * the right integer points down the '1' branch.
120 * However if an integer is negative, the decoding ceases and the
121 * resulting plaintext character is the negative integer + 257,
122 * and will always be in the range 0 - 255, or 256 for the literal code.
125 * Revision 2.3 1996/03/25 18:55:04 miker
126 * Changed FILENAME_MAX to _POSIX_PATH_MAX.
128 * Revision 2.2 1995/10/25 17:50:34 miker
131 * Revision 2.1 1995/09/22 20:46:28 miker
132 * Freeze DtSearch 0.1, AusText 2.1.8
134 * Revision 1.4 1995/09/19 22:04:11 miker
135 * Print out nonascii chars in .huf file comments.
137 * Revision 1.3 1995/09/05 18:08:00 miker
138 * Name changes for DtSearch.
145 #include <sys/stat.h>
148 #define MS_huff 30 /* message catalog set number */
149 #define DELIMITERS "\t\n" /* betw fields in .huf file */
151 #define MAX_BITLEN 24
152 #define MAX_NODES 514
154 * 256 chars + 'literal' char = max leaves, therefore max treesize
158 /*----------------------- HCTREE --------------------------*/
159 /* tree is also a table so tree ptrs are table indexes:
160 * 0 - 255 = characters themselves (leaves at base of tree).
161 * 256 = literal code (special char/leaf).
162 * > 256 = higher nodes.
163 * Global 'last_node' = highest actual node alloc so far.
164 * When tree completed, last_node = root of tree.
168 char bit; /* '0' or '1' (assoc with link to
170 long count; /* freq of occurrance of char */
171 int sort; /* specifies output sort order */
172 int father; /* index points UP toward root of
174 int son0; /* index of '0' (left) subnode */
175 int son1; /* index of '1' (right) subnode */
178 /*------------------------ GLOBALS ---------------------------*/
179 static int last_node = 256;
181 long literal_threshold = 0L;
182 int debug_switch = FALSE;
183 int literal_coding_on = TRUE;
184 int input_file_specified; /* TRUE if user enters
186 int no_huffcode_file; /* TRUE if table file not
188 HCTREE hctree1[MAX_NODES];
189 char filename_input[_POSIX_PATH_MAX];
190 char filename_huf[_POSIX_PATH_MAX];
191 char filename_huc[_POSIX_PATH_MAX];
193 #ifndef TURBO_COMPILER
194 /****************************************/
198 /****************************************/
199 static char *strrev (char *string)
205 for (i = 0, j = strlen (string) - 1; i < j; i++, j--) {
207 string[i] = string[j];
213 #endif /* !TURBO_COMPILER */
215 /****************************************/
219 /****************************************/
220 /* Each call joins the two nodes with smallest count
221 * into a single higher level node. If there are more than 2 nodes with
222 * similar 'smallest' counts, then within that group the 2 nodes with the
223 * shortest current bitstring length are joined.
224 * Returns TRUE for each successful lower level join.
225 * Returns FALSE when final join is made at highest level (root).
227 static int build_tree (void)
236 /* find 2 lowest counts */
237 for (i = 0; i < 257; i++) {
238 /* skip over real chars with counts <= 'literal' threshold */
239 if (literal_coding_on
241 && hctree1[i].count <= literal_threshold) {
242 hctree1[i].sort = MAX_BITLEN + 1;
246 /* skip over literal if literal coding turned off */
247 if (i == 256 && !literal_coding_on) {
248 hctree1[256].sort = MAX_BITLEN + 1;
253 * Ascend to highest tree level for current table entry,
254 * putting length of bitstring into sort field. Save
255 * highest tree level in curr.
258 for (j = i; j != -1; j = hctree1[j].father) {
264 * sanity checks after ascending tree: 1. if bit strings
265 * have grown too large, quit. 2. if curr points to top
268 if (hctree1[i].sort > MAX_BITLEN) {
269 fprintf (stderr, "%s", catgets(dtsearch_catd, MS_huff, 30,
270 "\n183 Bit strings have grown too large. You probably "
271 "have literals\n turned off with grossly unbalanced "
272 "character counts.\n\7"));
275 if (hctree1[curr].count >= total_count) {
276 fprintf (stderr, "%s", catgets(dtsearch_catd, MS_huff, 31,
277 "\n191 Programming Error: Still trying to build\n"
278 " Huffman Code Tree after root created.\n\7"));
283 * if curr ptr already joins low0 or low1, try the next
286 if (curr == low0 || curr == low1)
290 * If curr count is less than low0, or if curr count = low0
291 * but curr bitstring length is less, replace both low0 and
292 * low1. (that way, we keep low0 always <= low1)
294 if (low0 == -1 || hctree1[curr].count < hctree1[low0].count ||
295 (hctree1[curr].count == hctree1[low0].count && hctree1[i].sort < len0)) {
299 len0 = hctree1[i].sort;
304 * At this point curr count is 'greater' than low0. If curr
305 * count is less than low1, or if curr count = low1 but
306 * curr bitstring length is less, replace only low1
308 if (low1 == -1 || hctree1[curr].count < hctree1[low1].count ||
309 (hctree1[curr].count == hctree1[low1].count && hctree1[i].sort < len1)) {
311 len1 = hctree1[i].sort;
316 * default: curr count is greater than BOTH low0 and low1,
317 * try next table entry
319 } /* end loop to find two lowest counts */
321 /* low0 and low1 now point to two lowest count nodes.
322 * link in low0 and low1 to next available new node.
325 hctree1[low0].bit = '0';
326 hctree1[low0].father = last_node;
327 hctree1[low1].bit = '1';
328 hctree1[low1].father = last_node;
329 hctree1[last_node].bit = LAST_BIT;
330 hctree1[last_node].father = -1;
331 hctree1[last_node].count = hctree1[low0].count + hctree1[low1].count;
332 hctree1[last_node].son0 = low0;
333 hctree1[last_node].son1 = low1;
336 printf ("%3d: low0=%6ld\tlow1=%6ld\tsum=%6ld\t(%ld)\n",
337 last_node, hctree1[low0].count, hctree1[low1].count,
338 hctree1[last_node].count, total_count);
340 if (hctree1[last_node].count < total_count)
344 } /* end of function build_tree */
346 /****************************************/
350 /****************************************/
351 static char *char_label (int x)
359 return "\\b (backspace)";
363 return "\\n (linefeed)";
365 return "\\v (vert tab)";
367 return "\\f (form feed)";
369 return "\\r (carr retn)";
371 return "CTRL-Z (EOF)";
373 return "CTRL-[ (ESC)";
377 return "SPACE (blank)";
381 return "_ (underscore)";
385 return "*** LITERAL CODE ***";
390 sprintf (buf, "'CTRL-%c'", 0x40 | x);
394 strcpy (buf, catgets(dtsearch_catd, MS_huff, 32,
395 "(nonascii char, high bit set)"));
399 sprintf (buf, "'%c'", x);
403 } /* end of function char_label */
405 /****************************************/
407 /* Next Sorted Node */
409 /****************************************/
410 /* Called repeatedly, returns the next treebase node in sorted order.
411 * Sort order is by length of Huffman Code String.
412 * Caller must pass index of last node returned (neg at first call).
413 * Lasti should never be larger than treebase.
415 static int next_sorted_node (int lasti)
419 long nextsortval = MAX_BITLEN + 2;
421 /* permanently mark last returned node as unavailable */
423 hctree1[lasti].sort = MAX_BITLEN + 2;
425 /* find next shortest string length */
426 for (i = 0; i < 257; i++)
427 if (hctree1[i].sort < nextsortval) {
428 nextsortval = hctree1[i].sort;
432 } /* end of function next_sorted_node */
434 /****************************************/
436 /* Initialize Treebase */
438 /****************************************/
439 /* 'Treebase' is original 257 character nodes (including literal code).
440 * If huffcode table file exists, initializes treebase with its values,
441 * else initializes treebase with zero counts.
443 static void init_treebase (void)
451 /* .huf table file does not exist--zero all counts */
452 if ((instream_huf = fopen (filename_huf, "r")) == NULL) {
453 no_huffcode_file = TRUE;
454 for (i = 0; i < 257; i++) {
455 hctree1[i].bit = LAST_BIT;
456 hctree1[i].count = 0L;
457 hctree1[i].father = -1;
458 hctree1[i].son0 = -1;
459 hctree1[i].son1 = -1;
463 /* Table file exists--init treebase with values from file.
464 * We are only interested in the character itself (i),
465 * and its current count. All other fields will be recreated
466 * at output time. FILE FORMAT IS NOT CHECKED--IT HAD BETTER BE CORRECT!
469 no_huffcode_file = FALSE;
470 fgets (filebuf, sizeof (filebuf) - 1, instream_huf);
471 /* discard this first line (don't need id stamp) */
472 while (fgets (filebuf, sizeof (filebuf) - 1, instream_huf)
474 i = atoi (strtok (filebuf, DELIMITERS)); /* char */
475 if (i < 0 || i > 256) {
476 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 33,
477 "366 Invalid file format for %s.\n"),
481 strtok (NULL, DELIMITERS); /* skip over current huff
483 hctree1[i].count = (i == 256) ?
484 0L : atol (strtok (NULL, DELIMITERS));
485 hctree1[i].bit = LAST_BIT;
486 hctree1[i].father = -1;
487 hctree1[i].son0 = -1;
488 hctree1[i].son1 = -1;
490 total_count += hctree1[i].count;
491 } /* endwhile loop that reads each table line */
492 fclose (instream_huf);
495 } /* end of function init_treebase */
497 /****************************************/
501 /****************************************/
502 /* determines correct huffman code based on current counts in tree,
503 * writes out all to both files overlaying previous values if they existed.
505 static void huffman_code (time_t idstamp)
507 int i; /* current char */
509 int j; /* ascends tree from i to build bit_string */
510 char bit_string[MAX_BITLEN + 4];
516 /* establish the 'literal' node (char #256) count
517 * equal to sum of all chars whose counts are less than threshold.
519 if (literal_coding_on) {
520 hctree1[256].count = 0L;
521 for (i = 0; i < 256; i++)
522 if (hctree1[i].count <= literal_threshold)
523 hctree1[256].count += hctree1[i].count;
526 /* build the Huffman Code tree, and determine root (last_node) */
527 while (build_tree ());
529 /* now that we know the total number of tree nodes (last_node),
530 * we are ready to write.
531 * Open both output files and verify they are not write protected.
533 if ((outstream_huc = fopen (filename_huc, "w")) == NULL) {
534 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 34,
535 "424 File '%s' failed to open for write. Is it read-only?\n"),
539 if ((outstream_huf = fopen (filename_huf, "w")) == NULL) {
540 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 34,
541 "439 File '%s' failed to open for write. Is it read-only?\n"),
546 /* create the .c decode file (tree as integer array) */
547 fprintf (outstream_huc,
548 "#include <time.h>\n"
549 "char *hctree_name =\t\"%s\";\n"
550 "time_t hctree_id =\t%ldL;\n"
551 "int hctree_root =\t%d;\n"
552 "static int hctree_array[] = {\n",
553 filename_huc, idstamp, last_node - 257);
554 for (i = 257; i <= last_node; i++) {
555 fprintf (outstream_huc, "\t%4d,\t%4d%c\t/* %3d */\n",
556 hctree1[i].son0 - 257, hctree1[i].son1 - 257,
557 (i == last_node) ? ' ' : ',', /* no comma after last
559 i - 257); /* comment contains node number */
561 fprintf (outstream_huc, "\t};\nint *hctree =\thctree_array;\n");
562 fclose (outstream_huc);
564 /* write out the tree base (0-256) in sorted order to .huf file */
565 fprintf (outstream_huf, "%ld\tHCTREE_ID\n", idstamp);
566 for (lasti = -1; (i = next_sorted_node (lasti)) >= 0; lasti = i) {
568 * Create huffman code digit string. j ascends tree from i
569 * to build string in reverse order.
572 for (j = i; j != -1; j = hctree1[j].father)
573 *bitptr++ = hctree1[j].bit;
574 *bitptr = '\0'; /* terminate reversed string */
575 strrev (bit_string); /* reverse the string order */
576 if (bit_string[1] == 0)
577 strcpy (bit_string, " ");
578 if (strlen (bit_string) < 9)
579 strcat (bit_string, "\t");
581 /* write out the line for this char */
582 sprintf (sprintbuf, "%d\t%s\t%ld\t%s\n",
584 bit_string + 1, /* hop over LAST_BIT */
587 fprintf (outstream_huf, "%s", sprintbuf);
589 } /* end forloop printing out each tree base entry */
591 fclose (outstream_huf);
593 } /* end of function huffman_code */
595 /****************************************/
599 /****************************************/
600 static void print_usage (void)
602 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 35,
603 "USAGE: huffcode [-lN | -l-] [-o] <huffname> [<infile>]\n"
604 " -l<N> specifies the 'literal' threshold count. Any character occurring\n"
605 " <= <N> times will be coded with the Huffman literal. Default is -l0,\n"
606 " literal coding only for bytes with counts of zero.\n"
607 " -l- turns off literal coding. Turning off literal coding in unbalanced\n"
608 " trees leads to EXTREMELY LONG bit string codes--don't do it unless\n"
609 " the input is known to be a well balanced binary file.\n"
610 " -o preauthorizes overwriting any currently existing decode file.\n"
611 " <huffname> is the filename prefix for the Huffman Code files.\n"
612 " If the encode file (%s) already exists, byte counts from infile will\n"
613 " be added to it, otherwise it will be newly created.\n"
614 " The decode file (%s) is always newly created each run.\n"
615 " <infile> is an input file containing bytes to be counted.\n"
616 " It may be omitted if the encode file already exists.\n"),
617 EXT_HUFFCODE, EXT_HDECODE);
619 } /* end of function print_usage */
621 /********************************************************/
623 /* USER_ARGS_PROCESSOR */
625 /********************************************************/
626 /* handles command line arguments for 'main' */
627 static void user_args_processor (int argc, char **argv)
630 int OK_to_overwrite = FALSE;
633 if (argc <= 1) { /* user just wants to see usage msg */
638 /* each pass grabs new parm of "-xxx" format */
639 while (--argc > 0 && (*++argv)[0] == '-') {
641 argptr[1] = tolower (argptr[1]);
643 case 'l': /* literal threshold */
646 else if (argptr[2] == '-')
647 literal_coding_on = FALSE;
649 literal_threshold = atoi (argptr + 2);
652 case 'o': /* OK_to_overwrite .c file if it already
654 OK_to_overwrite = TRUE;
657 case 'v': /* verbose mode = debug switch */
663 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 36,
664 "'%s' is invalid argument.\n"), argptr);
666 exit (2); /* ABORT program */
669 } /* endwhile for cmd line '-'processing */
671 /* test for required tree file name */
673 fprintf (stderr, "%s", catgets(dtsearch_catd, MS_huff, 37,
674 "576 Missing Huffman Code file names prefix.\n"));
678 /* create 2 output file names from passed argument */
679 strncpy (filename_huf, argv[0], _POSIX_PATH_MAX);
680 filename_huf[_POSIX_PATH_MAX - 6] = 0;
681 strcat (filename_huf, EXT_HUFFCODE);
682 strncpy (filename_huc, argv[0], _POSIX_PATH_MAX);
683 filename_huc[_POSIX_PATH_MAX - 6] = 0;
684 strcat (filename_huc, EXT_HDECODE);
686 /* Since the decode file is a C source code file (.c extension),
687 * we want to be sure not to erase somebody's source program.
688 * So if the .c file already exists, and the user didn't specify
689 * overwrite in a command line argument, ask him now if it's OK to
690 * blow away the old file.
692 if (!OK_to_overwrite)
693 if ((stream = fopen (filename_huc, "r")) != NULL) {
695 printf (catgets(dtsearch_catd, MS_huff, 38,
696 "Decode file '%s' already exists. "
697 "Is it OK to overwrite it? [y/n] "),
699 if (toupper (getchar ()) != 'Y')
703 /* test for optional input file name */
705 input_file_specified = FALSE;
707 input_file_specified = TRUE;
708 strncpy (filename_input, argv[1], _POSIX_PATH_MAX);
709 filename_input[_POSIX_PATH_MAX - 1] = 0;
713 } /* end of function user_args_processor */
715 /****************************************/
719 /****************************************/
720 int main (int argc, char *argv[])
723 struct stat fstat_input;
726 time_t now, start_stamp;
728 setlocale (LC_ALL, "");
729 dtsearch_catd = catopen (FNAME_DTSRCAT, 0);
730 printf (catgets(dtsearch_catd, MS_huff, 40,
731 "HUFFCODE Version %s\n"), AUSAPI_VERSION);
733 /* validate user's command line arguments */
734 user_args_processor (argc, argv);
736 /* initialize tree table, using the table file if it exists */
738 if (total_count == 0L)
739 printf ("%s", catgets(dtsearch_catd, MS_huff, 41,
740 "Huffman Code Tables will be newly created.\n"));
742 printf (catgets(dtsearch_catd, MS_huff, 42,
743 "Table '%s' already contains %ld Kbytes from previous runs.\n"),
744 filename_huf, total_count / 1000L);
746 if (!input_file_specified && no_huffcode_file) {
747 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 43,
748 "645 Input file not specified and '%s' table file\n"
749 " doesn't exist--nothing to do!\n"),
755 /* read the input file and count its bytes */
756 if (input_file_specified) {
757 if ((instream = fopen (filename_input, "rb")) == NULL) {
759 fprintf (stderr, catgets(dtsearch_catd, MS_huff, 44,
760 "Could not open input file '%s' or access status: %s\n"),
761 filename_input, strerror (errno));
764 if (fstat (fileno (instream), &fstat_input) == -1)
766 printf (catgets(dtsearch_catd, MS_huff, 45,
767 "Input file '%s' contains about %ld Kbytes.\n"),
768 filename_input, fstat_input.st_size / 1000L);
771 while ((mychar = getc (instream)) != EOF) {
772 hctree1[mychar].count++;
775 /* echo progress to user every so often */
776 if (!(++bytes_in % 10000L))
777 printf (catgets(dtsearch_catd, MS_huff, 46,
778 "\r%ld%% done. %2ld Kbytes read. "
779 "Estimate %3ld seconds to completion. "),
780 (bytes_in * 100L) / fstat_input.st_size,
782 (fstat_input.st_size - bytes_in) *
783 (time (NULL) - start_stamp) / bytes_in);
784 } /* end read loop for each char in input file */
788 } /* endif that processes input file */
790 /* build huffman code tree, write out files */
791 time (&now); /* this will be the official tree id time
793 printf (catgets(dtsearch_catd, MS_huff, 47,
794 "Identifying timestamp will be '%ld'.\n"
795 "%s Huffman Code Tables in '%s' and '%s'..."),
798 catgets(dtsearch_catd, MS_huff, 48, "Creating") :
799 catgets(dtsearch_catd, MS_huff, 49, "Rebuilding"),
805 } /* end of function main */
807 /************************** HUFFCODE.C ******************************/