#include M/****************************************************************************M*_TITLE node_def - definition of NODE type *M*_ARGS NONE *M*_DESCR node_def defines the basic element of a node used to build the *M* Huffman tree for data decompression. The code declares a user *M* defined type that consists of an integer field and a left and right *M* pointer field. The *right and *left pointers point to another *M* NODE structure, a recursive reference of itself. The dn field will *M* contain a -1 if the node is not a leaf (or end node) otherwise it *M* will contain the pixel difference value. This value is then *M* subtracted from the preceding pixel and 256 is added to normalize *M* the actual first difference value. The left and right pointers are *M* undefined (NULL) if the node is a leaf, otherwise they will point *M* to the next adjacent node in the tree. *M*_LIMS This definition has been tested on VAX 750 (VMS 4.7), DEC MicroVAX *M* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *M* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *M* systems, check for portability conflicts. *M*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original Version *M*_END *N*****************************************************************************/ typedef struct leaf {# struct leaf *right; short int dn;" struct leaf *left; } NODE;J/*************************************************************************F Declare the tree pointer. This pointer will hold the root of the tree@ once the tree is created by the accompanying routine huff_tree.K**************************************************************************/ NODE *tree;$ void decompress(ibuf,obuf,nin,nout)M/****************************************************************************M*_TITLE decompress - decompresses image lines stored in compressed format *N*_ARGS TYPE NAME I/O DESCRIPTION */N char *ibuf; /* I Compressed data buffer */N char *obuf; /* O Decompressed image line */N long int *nin; /* I Number of bytes on input buffer */N long int *nout; /* I Number of bytes in output buffer *//*M*_DESCR This routine decompresses Huffman encoded compressed data. Huffman *M* coding uses a variable number of bits to encode different values of *M* the original data. The compression results because the most *M* frequently occurring data value is represented in the smallest *M* number of bits. This routine is called by a main program to *M* decompress an image line contained in ibuf. The first byte of *M* ibuf contains the actual first pixel value of the line. All *M* other bytes in the input line contain the compressed data. The *M* output buffer, obuf, will contain the decompressed image line *M* after the call to the "dcmprs" routine. *M*_LIMS This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX *M* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *M* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *M* systems, check for portability conflicts. *M* Please note that the calling convention used for this routine *M* follow VAX/VMS FORTRAN pass-by-reference standards to allow linking *M* to FORTRAN calling routines. C programmers must be aware of this *M* when coding calling routines. *M*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original C Version *M*_END *N*****************************************************************************/ {( /* The external root pointer to tree */ extern NODE *tree;1 /* Declare functions called from this routine */ void dcmprs();J/*************************************************************************E This routine is fairly simple as it's only function is to call the routine dcmprs. K**************************************************************************/$ dcmprs(ibuf,obuf,nin,nout,tree); return; }void decmpinit(hist)L/***************************************************************************L*_TITLE decmpinit - initializes the Huffman tree *M*_ARGS TYPE NAME I/O DESCRIPTION */L long int *hist; /* I First-difference histogram. This *L* array MUST be dimensioned to at *L* least 511 elements. There are a *L* total of 511 first-differerence *L* values. The least first- *L* difference value is 0-255 or -255, *L* while the largest first-difference *L* is 255-0 or 255. The first- *L* difference values are normalized *L* for table use to the range 1 to *L* 511 by adding 256 to each *M* difference. *//*L*_DESCR This routine is relatively simple; it is responsible for creating *L* the Huffman tree from the first difference histogram of the image. *L* In a first difference histogram, the first byte in each image line *L* is the actual pixel value. All other pixels are obtained by *L* subtracting the first difference value at the current pixel from *L* the actual value of the preceding pixel and adding 256 to provide *L* a positive number. The I-th element of the array "hist" should be *L* the frequency of occurances for the value I. Note the declaration *L* of the pointer tree. This external variable is defined by this *L* routine. It returns the pointer to the root of the Huffman tree *L* created by "huff_tree". The huff_tree routine will automatically *L* swap the low and high order bytes of the 32-bit elements in the *L* of the first difference histogram for the computer systems which *L* store integers in "most significant byte first" order. For computer*L* systems which store 32-bit words in "least significant byte first */* order, no swapping of the bytes occurs.L*_LIMS This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX *L* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *L* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *L* systems, check for portability conflicts. *L*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original C Version *L*_END *M****************************************************************************/{= extern NODE *tree; /* Huffman tree root pointer */; /* Specify the calling function to initialize the tree */ NODE *huff_tree();M/****************************************************************************/ Simply call the huff_tree routine and return.N*****************************************************************************/ tree = huff_tree(hist); return; }NODE *huff_tree(hist)M/****************************************************************************M*_TITLE huff_tree - constructs the Huffman tree; returns pointer to root *N*_ARGS TYPE NAME I/O DESCRIPTION */N long int *hist; /* I First difference histogram *//*M*_DESC huff_tree constructs a binary Huffman tree and returns the pointer *M* to the root of the tree. The implementation here may not be the *M* most efficient, but conditions of the algorithm used to compress *M* the data governed the design of this algorithm. Other *M* implementations are available in FORTRAN and VAX MACRO Assembler. *M* This routine allocates memory as needed to construct the tree. *M* The tree is implemented as a user defined structure described *M* above. The algorithm uses an array of node pointers allocated *M* for all possible values. This array is then initialized by *M* assigning all leafs to the array. Each leaf has a cooresponding *M* frequency assigned to it and the frequencies are sorted in ascending*M* order. All zero frequencies are ignored and tree construction *M* begins. The tree is built by combining the two least occuring *M* frequencies into one node. This new node is treated as one by *M* adding together the two frequencies forming a cummulative frequency *M* of the combining nodes. The second smallest node now contains the *M* newly combined node and the smallest node is deleted from the list. *M* The frequency list is then resorted to determine the next two node *M* combinations until one node is left. This node will be the root of *M* the tree. This pointer is then returned to the calling routine. *M*_LIMS This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX *M* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *M* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *M* systems, check for portability conflicts. *M* This routine uses the memory allocation routine "malloc". Check *M* for call specifications and casting portability of these features *M* for the compiler in used. *M*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original C Version *M*_END *N*****************************************************************************/ { /* Local variables used */@ long int freq_list[512]; /* Histogram frequency list */= NODE **node_list; /* DN pointer array list */ > register long int *fp; /* Frequency list pointer */9 register NODE **np; /* Node list pointer */P register long int num_freq; /* Number non-zero frequencies in histogram */> long int sum; /* Sum of all frequencies */E register short int num_nodes; /* Counter for DN initialization */= register short int cnt; /* Miscellaneous counter */7 short int znull = -1; /* Null node value */ > register NODE *temp; /* Temporary node pointer */ /* Functions called */ void sort_freq(); NODE *new_node(); char *malloc();L/***************************************************************************K Allocate the array of nodes from memory and initialize these with numbersF corresponding with the frequency list. There are only 511 possible H permutations of first difference histograms. There are 512 allocated ( here to adhere to the FORTRAN version.M****************************************************************************/ fp = freq_list;2 node_list = (NODE **) malloc(sizeof(temp)*512); if (node_list == NULL) {0 printf("\nOut of memory in huff_tree!\n"); exit(1); } np = node_list;3 for (num_nodes=1, cnt=512 ; cnt-- ; num_nodes++) {K/**************************************************************************G The following code has been added to standardize the VAX byte orderG for the "long int" type. This code is intended to make the routine' as machine independant as possible.L***************************************************************************/5 unsigned char *cp = (unsigned char *) hist++; unsigned long int j; short int i;6 for (i=4 ; --i >= 0 ; j = (j << 8) | *(cp+i));/* Now make the assignment */ *fp++ = j;# temp = new_node(num_nodes); *np++ = temp; }G (*--fp) = 0; /* Ensure the last element is zeroed out. */L/***************************************************************************E Now, sort the frequency list and eliminate all frequencies of zero.M****************************************************************************/ num_freq = 512;* sort_freq(freq_list,node_list,num_freq); fp = freq_list; np = node_list;I for (num_freq=512 ; (*fp) == 0 && (num_freq) ; fp++, np++, num_freq--);L/***************************************************************************H Now create the tree. Note that if there is only one difference value,H it is returned as the root. On each interation, a new node is createdH and the least frequently occurring difference is assigned to the rightF pointer and the next least frequency to the left pointer. The node E assigned to the left pointer now becomes the combination of the twoA nodes and it's frequency is the sum of the two combining nodes.M****************************************************************************/( for (temp=(*np) ; (num_freq--) > 1 ; ) { temp = new_node(znull); temp->right = (*np++); temp->left = (*np); *np = temp; *(fp+1) = *(fp+1) + *fp; *fp++ = 0;" sort_freq(fp,np,num_freq); } return temp; }NODE *new_node(value)M/****************************************************************************M*_TITLE new_node - allocates a NODE structure and returns a pointer to it *N*_ARGS TYPE NAME I/O DESCRIPTION */N short int value; /* I Value to assign to DN field *//*M*_DESC new_node allocates virtual memory for a new NODE structure. It *M* initializes the right and left pointers to NULL and the dn field *M* is initialized to the passed parameter 'value'. *M*_LIMS This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX *M* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *M* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *M* systems, check for portability conflicts. *M* This routine uses the malloc routine that requests virtual memory *M* from the system. Most C libraries have some version of this *M* function. Check the reference manuals for compatibility. *M*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original Version *M*_END *N*****************************************************************************/ {9 NODE *temp; /* Pointer to the memory block */8 char *malloc(); /* Memory allocation function */L/***************************************************************************/ Allocate the memory and intialize the fields.M****************************************************************************/' temp = (NODE *) malloc(sizeof(NODE)); if (temp != NULL) { temp->right = NULL; temp->dn = value; temp->left = NULL; } else {0 printf("\nOut of memory in new_node!\n"); exit(1); } return temp; }- void sort_freq(freq_list,node_list,num_freq)M/****************************************************************************M*_TITLE sort_freq - sorts frequency and node lists in increasing freq. order*N*_ARGS TYPE NAME I/O DESCRIPTION */N long int *freq_list; /* I Pointer to frequency list */N NODE **node_list; /* I Pointer to array of node pointers */N long int num_freq; /* I Number of values in freq list *//*M*_DESCR This routine uses an insertion sort to reorder a frequency list *M* in order of increasing frequency. The corresponding elements *M* of the node list are reordered to maintain correspondence. The *M* node list is actually a pointer to an array of pointers to tree ** nodes.M*_LIMS This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX *M* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *M* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *M* systems, check for portability conflicts. *M*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original C Version *M*_END *N*****************************************************************************/ { /* Local Variables */D register long int *i; /* primary pointer into freq_list */F register long int *j; /* secondary pointer into freq_list */ B register NODE **k; /* primary pointer to node_list */F register NODE **l; /* secondary pointer into node_list */E long int temp1; /* temporary storage for freq_list */E NODE *temp2; /* temporary storage for node_list */< register long int cnt; /* count of list elements */I/************************************************************************D Save the current element - starting with the second - in temporaryC storage. Compare with all elements in first part of list moving C each up one element until the element is larger. Insert current element at this point in list.J*************************************************************************/J if (num_freq <= 0) return; /* If no elements or invalid, return */L for (i=freq_list, k=node_list, cnt=num_freq ; --cnt ; *j=temp1, *l=temp2) { temp1 = *(++i); temp2 = *(++k);/ for (j = i, l = k ; *(j-1) > temp1 ; ) { *j = *(j-1); *l = *(l-1); j--; l--;' if ( j <= freq_list) break; } } return; }% void dcmprs(ibuf,obuf,nin,nout,root)M/****************************************************************************M*_TITLE dcmprs - decompresses Huffman coded compressed image lines *N*_ARGS TYPE NAME I/O DESCRIPTION */N char *ibuf; /* I Compressed data buffer */N char *obuf; /* O Decompressed image line */N long int *nin; /* I Number of bytes on input buffer */N long int *nout; /* I Number of bytes in output buffer */N NODE *root; /* I Huffman coded tree *//*M*_DESCR This routine follows a path from the root of the Huffman tree to *M* one of it's leaves. The choice at each branch is decided by the *M* successive bits of the compressed input stream. Left for 1, right *M* for 0. Only leaf nodes have a value other than -1. The routine *M* traces a path through the tree until it finds a node with a value *M* not equal to -1 (a leaf node). The value at the leaf node is *M* subtracted from the preceeding pixel value plus 256 to restore *M* the uncompressed pixel. This algorithm is then repeated until the *M* entire line has been processed. *M*_LIMS This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX *M* (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an *M* IBM PC (MICROSOFT 4.0, 3.0 compilers). When converting to other *M* systems, check for portability conflicts. *M* Please note that the calling convention used for these routines *M* follow VAX/VMS FORTRAN pass-by-reference standards to allow *M* linking to FORTRAN calling routines. C programmers must be aware *M* of this when coding calling routines. *M*_HIST 17-FEB-88 Kris Becker USGS, Flagstaff Original C Version *M*_END *N*****************************************************************************/ { /* Local Variables */G register NODE *ptr = root; /* pointer to position in tree */A register unsigned char test; /* test byte for bit set */A register unsigned char idn; /* input compressed byte */F register char odn; /* last dn value decompressed */C char *ilim = ibuf + *nin; /* end of compressed bytes */@ char *olim = obuf + *nout; /* end of output buffer */K/**************************************************************************J Check for valid input values for nin, nout and make initial assignments.L***************************************************************************/# if (ilim > ibuf && olim > obuf) odn = *obuf++ = *ibuf++; else {7 printf("\nInvalid byte count in dcmprs!\n"); exit(1); }K/**************************************************************************E Decompress the input buffer. Assign the first byte to the working G variable, idn. An arithmatic and (&) is performed using the variableD 'test' that is bit shifted to the right. If the result is 0, then go to right else go to left.L***************************************************************************/5 for (idn=(*ibuf) ; ibuf < ilim ; idn =(*++ibuf)) {+ for (test=0x80 ; test ; test >>= 1) {8 ptr = (test & idn) ? ptr->left : ptr->right; if (ptr->dn != -1) {) if (obuf >= olim) return;% odn -= ptr->dn + 256; *obuf++ = odn; ptr = root; } } } return; }void free_tree(nfreed)M/****************************************************************************M*_TITLE free_tree - free memory of all allocated nodes *N*_ARGS TYPE NAME I/O DESCRIPTION */M long int *nfreed; /* O Return of total count of nodes *N* freed. *//*M*_DESCR This routine is supplied to the programmer to free up all the *M* allocated memory required to build the huffman tree. The count *M* of the nodes freed is returned in the parameter 'nfreed'. The *M* purpose of the routine is so if the user wishes to decompress more *M* than one file per run, the program will not keep allocating new *M* memory without first deallocating all previous nodes associated *M* with the previous file decompression. *M*_HIST 16-AUG-89 Kris Becker USGS, Flagstaff Original Version *M*_END *M****************************************************************************/{ long int total_free = 0;8 extern NODE *tree; /* Huffman tree root pointer */+/* Specify the function to free the tree */ long int free_node();M/****************************************************************************: Simply call the free_node routine and return the result.N*****************************************************************************/& *nfreed = free_node(tree,total_free); return;}$long int free_node(pnode,total_free)L/***************************************************************************9*_TITLE free_node - deallocates an allocated NODE pointerM*_ARGS TYPE NAME I/O DESCRIPTION */M NODE *pnode; /* I Pointer to node to free */M long int total_free; /* I Total number of freed nodes *//*L*_DESCR free_node will check both right and left pointers of a node *L* and then free the current node using the free() C utility. *L* Note that all nodes attached to the node via right or left *L* pointers area also freed, so be sure that this is the desired *L* result when calling this routine. *L* This routine is supplied to allow successive calls to the *L* decmpinit routine. It will free up the memory allocated *L* by previous calls to the decmpinit routine. The call to free *L* a previous huffman tree is: total = free_node(tree,(long) 0); *L* This call must be done by the programmer application routine *L* and is not done by any of these routines. *M*_HIST 16-AUG-89 Kris Becker U.S.G.S Flagstaff Original Version */{0 if (pnode == (NODE *) NULL) return(total_free); # if (pnode->right != (NODE *) NULL)2 total_free = free_node(pnode->right,total_free);" if (pnode->left != (NODE *) NULL)1 total_free = free_node(pnode->left,total_free); free((char *) pnode); return(total_free + 1);}