home *** CD-ROM | disk | FTP | other *** search
/ Voyagers to the Outer Planets 3: Uranus / VoyagestotheOuterPlanetsVol3.cdr / software / decomp.c < prev    next >
C/C++ Source or Header  |  1988-09-14  |  23KB  |  507 lines
  1. #include <stdio.h>
  2.  
  3. /****************************************************************************
  4. *_TITLE node_def - definition of NODE type                                  *
  5. *_ARGS NONE                                                                 *
  6.  
  7. *_DESCR node_def defines the basic element of a node used to build the      *
  8. *       Huffman tree for data decompression.  The code declares a user      *
  9. *       defined type that consists of an integer field and a left and right *
  10. *       pointer field.  The *right and *left pointers point to another      *
  11. *       NODE structure, a recursive reference of itself.  The dn field will *
  12. *       contain a -1 if the node is not a leaf (or end node) otherwise it   *
  13. *       will contain the pixel difference value.  This value is then        *
  14. *       subtracted from the preceding pixel and 256 is added to normalize   *
  15. *       the actual first difference value.  The left and right pointers are *
  16. *       undefined (NULL) if the node is a leaf, otherwise they will point   *
  17. *       to the next adjacent node in the tree.                              *
  18.  
  19. *_LIMS  This definition has been tested on VAX 750 (VMS 4.7), DEC MicroVAX  *
  20. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an       *
  21. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other    *
  22. *       systems, check for portability conflicts.                           *
  23.  
  24. *_HIST  17-FEB-88  Kris Becker  USGS, Flagstaff Original Version            *
  25. *_END                                                                       *
  26. *****************************************************************************/
  27.  
  28.   typedef struct leaf 
  29.               {
  30.                 struct leaf *right;
  31.                 short int dn;
  32.                 struct leaf *left;
  33.                } NODE;
  34.  
  35.  
  36. /*************************************************************************
  37.  Declare the tree pointer. This pointer will hold the root of the tree
  38.  once the tree is created by the accompanying routine huff_tree.
  39. **************************************************************************/
  40.   NODE *tree;
  41.  
  42.  
  43.  void decompress(ibuf,obuf,nin,nout)
  44. /****************************************************************************
  45. *_TITLE decompress - decompresses image lines stored in compressed format   *
  46. *_ARGS  TYPE       NAME      I/O        DESCRIPTION                         */
  47.         char       *ibuf;  /* I         Compressed data buffer              */
  48.         char       *obuf;  /* O         Decompressed image line             */
  49.         long int   *nin;   /* I         Number of bytes on input buffer     */
  50.         long int   *nout;  /* I         Number of bytes in output buffer    */
  51.  
  52. /*
  53. *_DESCR This routine decompresses Huffman encoded compressed data.  Huffman *
  54. *       coding uses a variable number of bits to encode different values of *
  55. *       the original data.  The compression results because the most        *
  56. *       frequently occurring data value is represented in the smallest      *
  57. *       number of bits.  This routine is called by a main program to        *
  58. *       decompress an image line contained in ibuf.  The first byte of      *
  59. *       ibuf contains the actual first pixel value of the line.  All        *
  60. *       other bytes in the input line contain the compressed data.  The     *
  61. *       output buffer, obuf, will contain the decompressed image line       *
  62. *       after the call to the "dcmprs" routine.                             *
  63.  
  64. *_LIMS  This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX     *
  65. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an       *
  66. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other    *
  67. *       systems, check for portability conflicts.                           *
  68.  
  69. *       Please note that the calling convention used for this routine       *
  70. *       follow VAX/VMS FORTRAN pass-by-reference standards to allow linking *
  71. *       to FORTRAN calling routines.  C programmers must be aware of this   *
  72. *       when coding calling routines.                                       *
  73.  
  74. *_HIST  17-FEB-88 Kris Becker USGS, Flagstaff Original C Version            *
  75. *_END                                                                       *
  76. *****************************************************************************/
  77.  
  78.  
  79.   {
  80.  /* The external root pointer to tree */
  81.     extern NODE *tree;
  82.  
  83.  /* Declare functions called from this routine */
  84.     void dcmprs();
  85.  
  86.  
  87. /*************************************************************************
  88.   This routine is fairly simple as it's only function is to call the 
  89.   routine dcmprs. 
  90. **************************************************************************/
  91.  
  92.     dcmprs(ibuf,obuf,nin,nout,tree);
  93.   
  94.     return;
  95.   }
  96.  
  97.  
  98.  
  99. void decmpinit(hist)
  100. /***************************************************************************
  101. *_TITLE decmpinit - initializes the Huffman tree                           *
  102. *_ARGS  TYPE       NAME      I/O        DESCRIPTION                        */
  103.         long int   *hist;  /* I         First-difference histogram.  This  *
  104. *                                       array MUST be dimensioned to at    *
  105. *                                       least 511 elements.  There are a   *
  106. *                                       total of 511 first-differerence    *
  107. *                                       values.  The least first-          *
  108. *                                       difference value is 0-255 or -255, *
  109. *                                       while the largest first-difference *
  110. *                                       is 255-0 or 255.  The first-       *
  111. *                                       difference values are normalized   *
  112. *                                       for table use to the range 1 to    *
  113. *                                       511 by adding 256 to each          *
  114. *                                       difference.                        */
  115.  
  116. /*
  117. *_DESCR This routine is relatively simple; it is responsible for creating  *
  118. *       the Huffman tree from the first difference histogram of the image. *
  119. *       In a first difference histogram, the first byte in each image line *
  120. *       is the actual pixel value.  All other pixels are obtained by       *
  121. *       subtracting the first difference value at the current pixel from   *
  122. *       the actual value of the preceding pixel and adding 256 to provide  *
  123. *       a positive number.  The I-th element of the array "hist" should be *
  124. *       the frequency of occurances for the value I.  Note the declaration *
  125. *       of the pointer tree.  This external variable is defined by this    *
  126. *       routine.  It returns the pointer to the root of the Huffman tree   *
  127. *       created by "huff_tree". The huff_tree routine will automatically   *
  128. *       swap the low and high order bytes of the 32-bit elements in the    *
  129. *       of the first difference histogram for the computer systems which   *
  130. *       store integers in "most significant byte first" order. For computer*
  131. *       systems which store 32-bit words in "least significant byte first  *
  132. *       order, no swapping of the bytes occurs.
  133.  
  134.  
  135. *_LIMS  This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX    *
  136. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an      *
  137. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other   *
  138. *       systems, check for portability conflicts.                          *
  139.  
  140. *_HIST  17-FEB-88  Kris Becker  USGS, Flagstaff Original C Version         *
  141. *_END                                                                      *
  142. ****************************************************************************/
  143.  
  144. {
  145.   extern NODE *tree;          /* Huffman tree root pointer */
  146.  
  147.   /* Specify the calling function to initialize the tree */
  148.   NODE *huff_tree();
  149.  
  150. /****************************************************************************
  151.   Simply call the huff_tree routine and return.
  152. *****************************************************************************/
  153.  
  154.   tree = huff_tree(hist);
  155.  
  156.   return;
  157.  }
  158.  
  159.  
  160.  
  161.  
  162.  
  163. NODE *huff_tree(hist)
  164. /****************************************************************************
  165. *_TITLE huff_tree - constructs the Huffman tree; returns pointer to root    *
  166. *_ARGS  TYPE          NAME        I/O   DESCRIPTION                         */
  167.         long int     *hist;     /* I    First difference histogram          */
  168. /*
  169. *_DESC  huff_tree constructs a binary Huffman tree and returns the pointer  *
  170. *       to the root of the tree.  The implementation here may not be the    *
  171. *       most efficient, but conditions of the algorithm used to compress    *
  172. *       the data governed the design of this algorithm.  Other              *
  173. *       implementations are available in FORTRAN and VAX MACRO Assembler.   *
  174. *       This routine allocates memory as needed to construct the tree.      *
  175. *       The tree is implemented as a user defined structure described       *
  176. *       above.  The algorithm uses an array of node pointers allocated      *
  177. *       for all possible values.  This array is then initialized by         *
  178. *       assigning all leafs to the array.  Each leaf has a cooresponding    *
  179. *       frequency assigned to it and the frequencies are sorted in ascending*
  180. *       order.  All zero frequencies are ignored and tree construction      *
  181. *       begins.  The tree is built by combining the two least occuring      *
  182. *       frequencies into one node.  This new node is treated as one by      *
  183. *       adding together the two frequencies forming a cummulative frequency *
  184. *       of the combining nodes.  The second smallest node now contains the  *
  185. *       newly combined node and the smallest node is deleted from the list. *
  186. *       The frequency list is then resorted to determine the next two node  *
  187. *       combinations until one node is left.  This node will be the root of *
  188. *       the tree.  This pointer is then returned to the calling routine.    *
  189.  
  190.  
  191. *_LIMS  This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX     *
  192. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an       *
  193. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other    *
  194. *       systems, check for portability conflicts.                           *
  195.  
  196. *       This routine uses the memory allocation routine "malloc".  Check    *
  197. *       for call specifications and casting portability of these features   *
  198. *       for the compiler in used.                                           *
  199.  
  200. *_HIST  17-FEB-88  Kris Becker  USGS, Flagstaff Original C Version          *
  201. *_END                                                                       *
  202. *****************************************************************************/
  203.  
  204.   {
  205.   /*  Local variables used */
  206.     long int freq_list[512];      /* Histogram frequency list */
  207.     NODE **node_list;             /* DN pointer array list */
  208.     
  209.     register long int *fp;        /* Frequency list pointer */
  210.     register NODE **np;           /* Node list pointer */
  211.  
  212.     register long int num_freq;   /* Number non-zero frequencies in histogram */
  213.     long int sum;                 /* Sum of all frequencies */
  214.  
  215.     register short int num_nodes; /* Counter for DN initialization */
  216.     register short int cnt;       /* Miscellaneous counter */
  217.  
  218.     short int znull = -1;         /* Null node value */
  219.     
  220.     register NODE *temp;          /* Temporary node pointer */
  221.  
  222.   /* Functions called */
  223.     void sort_freq();
  224.     NODE *new_node();
  225.     char *malloc();
  226.  
  227. /***************************************************************************
  228.   Allocate the array of nodes from memory and initialize these with numbers
  229.   corresponding with the frequency list.  There are only 511 possible 
  230.   permutations of first difference histograms.  There are 512 allocated 
  231.   here to adhere to the FORTRAN version.
  232. ****************************************************************************/
  233.  
  234.    fp = freq_list;
  235.    node_list = (NODE **) malloc(sizeof(temp)*512);
  236.    if (node_list == NULL)
  237.     {
  238.       printf("\nOut of memory in huff_tree!\n");
  239.       exit(1);
  240.     }
  241.    np = node_list;
  242.  
  243.    for (num_nodes=1, cnt=512 ; cnt-- ; num_nodes++)
  244.      {
  245. /**************************************************************************
  246.     The following code has been added to standardize the VAX byte order
  247.     for the "long int" type.  This code is intended to make the routine
  248.     as machine independant as possible.
  249. ***************************************************************************/
  250.         unsigned char *cp = (unsigned char *) hist++;
  251.         unsigned long int j;
  252.         short int i;
  253.         for (i=4 ; --i >= 0 ; j = (j << 8) | *(cp+i));
  254.  
  255. /* Now make the assignment */
  256.         *fp++ = j;
  257.         temp = new_node(num_nodes);
  258.         *np++ = temp;
  259.      }
  260.  
  261.      (*--fp) = 0;         /* Ensure the last element is zeroed out.  */
  262.  
  263. /***************************************************************************
  264.   Now, sort the frequency list and eliminate all frequencies of zero.
  265. ****************************************************************************/
  266.  
  267.   num_freq = 512;
  268.   sort_freq(freq_list,node_list,num_freq);
  269.  
  270.   fp = freq_list;
  271.   np = node_list;
  272.  
  273.   for (num_freq=512 ; (*fp) == 0 && (num_freq) ; fp++, np++, num_freq--);
  274.  
  275.  
  276. /***************************************************************************
  277.   Now create the tree.  Note that if there is only one difference value,
  278.   it is returned as the root.  On each interation, a new node is created
  279.   and the least frequently occurring difference is assigned to the right
  280.   pointer and the next least frequency to the left pointer.  The node 
  281.   assigned to the left pointer now becomes the combination of the two
  282.   nodes and it's frequency is the sum of the two combining nodes.
  283. ****************************************************************************/
  284.  
  285.   for (temp=(*np) ; (num_freq--) > 1 ; )
  286.     {
  287.         temp = new_node(znull);
  288.         temp->right = (*np++);
  289.         temp->left = (*np);
  290.         *np = temp;
  291.         *(fp+1) = *(fp+1) + *fp;
  292.         *fp++ = 0;
  293.         sort_freq(fp,np,num_freq);
  294.     }
  295.   
  296.   return temp;
  297.  }
  298.  
  299.  
  300.  
  301.  
  302. NODE *new_node(value)
  303. /****************************************************************************
  304. *_TITLE new_node - allocates a NODE structure and returns a pointer to it   *
  305. *_ARGS  TYPE        NAME        I/O     DESCRIPTION                         */
  306.         short int   value;    /* I      Value to assign to DN field         */
  307.  
  308. /*
  309. *_DESC  new_node allocates virtual memory for a new NODE structure.  It     *
  310. *       initializes the right and left pointers to NULL and the dn field    *
  311. *       is initialized to the passed parameter 'value'.                     *
  312.  
  313.  
  314. *_LIMS  This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX     *
  315. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an       *
  316. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other    *
  317. *       systems, check for portability conflicts.                           *
  318.  
  319. *       This routine uses the malloc routine that requests virtual memory   *
  320. *       from the system.  Most C libraries have some version of this        *
  321. *       function.  Check the reference manuals for compatibility.           *
  322.  
  323. *_HIST  17-FEB-88  Kris Becker  USGS, Flagstaff Original Version            *
  324. *_END                                                                       *
  325. *****************************************************************************/
  326.  
  327.   {
  328.     NODE *temp;         /* Pointer to the memory block */
  329.  
  330.     char *malloc();     /* Memory allocation function */
  331.  
  332.  
  333. /***************************************************************************
  334.   Allocate the memory and intialize the fields.
  335. ****************************************************************************/
  336.  
  337.   temp = (NODE *) malloc(sizeof(NODE));
  338.  
  339.   if (temp != NULL) 
  340.     {
  341.       temp->right = NULL;
  342.       temp->dn = value;
  343.       temp->left = NULL;
  344.     }
  345.   else
  346.     {
  347.        printf("\nOut of memory in new_node!\n");
  348.        exit(1);
  349.     }
  350.  
  351.    return temp;
  352.   }
  353.  
  354.  
  355.  
  356.  void sort_freq(freq_list,node_list,num_freq)
  357. /****************************************************************************
  358. *_TITLE sort_freq - sorts frequency and node lists in increasing freq. order*
  359. *_ARGS  TYPE       NAME            I/O  DESCRIPTION                         */
  360.         long int   *freq_list;   /* I   Pointer to frequency list           */
  361.         NODE       **node_list;  /* I   Pointer to array of node pointers   */
  362.         long int   num_freq;     /* I   Number of values in freq list       */
  363.  
  364. /*
  365. *_DESCR This routine uses an insertion sort to reorder a frequency list     *
  366. *       in order of increasing frequency.  The corresponding elements       *
  367. *       of the node list are reordered to maintain correspondence.  The     *
  368. *       node list is actually a pointer to an array of pointers to tree     *
  369. *       nodes.
  370.  
  371. *_LIMS  This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX     *
  372. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an       *
  373. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other    *
  374. *       systems, check for portability conflicts.                           *
  375.  
  376. *_HIST  17-FEB-88 Kris Becker USGS, Flagstaff Original C Version            *
  377. *_END                                                                       *
  378. *****************************************************************************/
  379.   {
  380.     /* Local Variables */
  381.     register long int *i;       /* primary pointer into freq_list */
  382.     register long int *j;       /* secondary pointer into freq_list */
  383.     
  384.     register NODE **k;          /* primary pointer to node_list */
  385.     register NODE **l;          /* secondary pointer into node_list */
  386.  
  387.     long int temp1;             /* temporary storage for freq_list */
  388.     NODE *temp2;                /* temporary storage for node_list */
  389.  
  390.     register long int cnt;      /* count of list elements */
  391.  
  392.  
  393. /************************************************************************
  394.   Save the current element - starting with the second - in temporary
  395.   storage.  Compare with all elements in first part of list moving 
  396.   each up one element until the element is larger.  Insert current 
  397.   element at this point in list.
  398. *************************************************************************/
  399.  
  400.    if (num_freq <= 0) return;      /* If no elements or invalid, return */
  401.  
  402.    for (i=freq_list, k=node_list, cnt=num_freq ; --cnt ; *j=temp1, *l=temp2)
  403.      {
  404.         temp1 = *(++i);
  405.         temp2 = *(++k);
  406.  
  407.         for (j = i, l = k ;  *(j-1) > temp1 ; )
  408.           {
  409.             *j = *(j-1);
  410.             *l = *(l-1);
  411.             j--;
  412.             l--;
  413.             if ( j <= freq_list) break;
  414.           }
  415.  
  416.      }
  417.   return;
  418.   }
  419.  
  420.  
  421.  
  422.  
  423.  void dcmprs(ibuf,obuf,nin,nout,root)
  424. /****************************************************************************
  425. *_TITLE dcmprs - decompresses Huffman coded compressed image lines          *
  426. *_ARGS  TYPE       NAME       I/O       DESCRIPTION                         */
  427.         char       *ibuf;   /* I        Compressed data buffer              */
  428.         char       *obuf;   /* O        Decompressed image line             */
  429.         long int   *nin;    /* I        Number of bytes on input buffer     */
  430.         long int   *nout;   /* I        Number of bytes in output buffer    */
  431.         NODE       *root;   /* I        Huffman coded tree                  */
  432.  
  433. /*
  434. *_DESCR This routine follows a path from the root of the Huffman tree to    *
  435. *       one of it's leaves.  The choice at each branch is decided by the    *
  436. *       successive bits of the compressed input stream.  Left for 1, right  *
  437. *       for 0.  Only leaf nodes have a value other than -1.  The routine    *
  438. *       traces a path through the tree until it finds a node with a value   *
  439. *       not equal to -1 (a leaf node).  The value at the leaf node is       *
  440. *       subtracted from the preceeding pixel value plus 256 to restore      *
  441. *       the uncompressed pixel.  This algorithm is then repeated until the  *
  442. *       entire line has been processed.                                     *
  443.  
  444.  
  445. *_LIMS  This routine has been tested on VAX 750 (VMS 4.6), DEC MicroVAX     *
  446. *       (ULTRIX 2.2), SUN Workstation (UNIX 4.2, release 3.4), and an       *
  447. *       IBM PC (MICROSOFT 4.0, 3.0 compilers).  When converting to other    *
  448. *       systems, check for portability conflicts.                           *
  449.  
  450. *       Please note that the calling convention used for these routines     *
  451. *       follow VAX/VMS FORTRAN pass-by-reference standards to allow         *
  452. *       linking to FORTRAN calling routines.  C programmers must be aware   *
  453. *       of this when coding calling routines.                               *
  454.  
  455. *_HIST  17-FEB-88 Kris Becker USGS, Flagstaff Original C Version            *
  456. *_END                                                                       *
  457. *****************************************************************************/
  458.   {
  459.     /* Local Variables */
  460.     register NODE *ptr = root;        /* pointer to position in tree */
  461.     register unsigned char test;      /* test byte for bit set */
  462.     register unsigned char idn;       /* input compressed byte */
  463.  
  464.     register char odn;                /* last dn value decompressed */
  465.  
  466.     char *ilim = ibuf + *nin;         /* end of compressed bytes */
  467.     char *olim = obuf + *nout;        /* end of output buffer */
  468.  
  469.  
  470.  
  471. /**************************************************************************
  472.   Check for valid input values for nin, nout and make initial assignments.
  473. ***************************************************************************/
  474.  
  475.     if (ilim > ibuf && olim > obuf)
  476.        odn = *obuf++ = *ibuf++;
  477.     else
  478.        {
  479.            printf("\nInvalid byte count in dcmprs!\n");
  480.            exit(1);
  481.        }
  482.  
  483. /**************************************************************************
  484.   Decompress the input buffer.  Assign the first byte to the working 
  485.   variable, idn.  An arithmatic and (&) is performed using the variable
  486.   'test' that is bit shifted to the right.  If the result is 0, then
  487.   go to right else go to left.
  488. ***************************************************************************/
  489.  
  490.     for (idn=(*ibuf) ; ibuf < ilim  ; idn =(*++ibuf))
  491.      {
  492.         for (test=0x80 ; test ; test >>= 1)
  493.            {
  494.             ptr = (test & idn) ? ptr->left : ptr->right;
  495.  
  496.             if (ptr->dn != -1) 
  497.               {
  498.                 if (obuf >= olim) return;
  499.                 odn -= ptr->dn + 256;
  500.                 *obuf++ = odn;
  501.                 ptr = root;
  502.               }
  503.           }
  504.      }
  505.    return;
  506.   }
  507.