home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / xloadimg.zip / xloadimage.4.1 / pdsuncomp.c < prev    next >
C/C++ Source or Header  |  1993-10-28  |  16KB  |  453 lines
  1. /* jimf@saber.com, 05.06.91
  2.  *
  3.  * fairly major modifications to get this to work well in the xloadimage
  4.  * view of the world.  rather than a standalone program, this is now designed
  5.  * to be run as a subroutine.  a lot of comments on how to build and use
  6.  * this on different kinds of hosts have been removed.  removed or rewrote
  7.  * all the host-portability stuff.  lobotomized its ability to dump any but
  8.  * VICAR format.
  9.  */
  10. /* datri@convex.com, 4-14-91
  11.    This file is taken almost unchanged from the NASA CD-ROMS of the Voyager
  12.    images.  I can find no copyright anywhere near this code.
  13.    All I've done is added - as a special case for the output
  14.    filename to go to stdout, and made informational messages go to stderr
  15.    instead of stdout, removing some of the silly ones.  I've also corrected
  16.    some of the places where fools assume that VAX and VMS are synonymous */
  17.  
  18. /********************************************************************/
  19. /*  Voyager Image Decompression Program - C Version for PC, VAX,    */
  20. /*  UNIX and Macintosh systems.                                     */
  21. /*                                                                  */
  22. /*  Decompresses images using Kris Becker's subroutine DECOMP.C     */
  23. /*  which is included in this program in a shortened version.       */
  24. /*                                                                  */
  25. /*  Reads a variable length compressed VOYAGER image and outputs a  */
  26. /*  fixed length uncompressed image file in PDS format with         */
  27. /*  labels, image histogram, engineering table and 800 lines of     */
  28. /*  836 bytes (800 samples, 36 engineering bytes); or an 800 by     */
  29. /*  800 array with FITS, VICAR or no labels.  If used on a non-     */
  30. /*  byte-swapped machine the image histogram is un-swapped.         */
  31. /*                                                                  */
  32. /********************************************************************/
  33. /* HIST                                                             */
  34. /*  AUG89 Added code to get command line arguments for filenames    */
  35. /*  and output format; routines to free memory used by the Huffman  */
  36. /*  tree); fixed the SFDU label output length; and modified the     */
  37. /*  I/O routines so that the open for Host type 2 uses binary I/O.  */
  38. /*  JUN89 Fixed READVAR, to get length on 16-bit unswapped hosts.   */
  39. /*  JUL88 C driver to decompress standard Voyager Compressed images */
  40. /*  by Mike Martin 1989/06/10                                       */
  41. /*                                                                  */
  42. /*  Inputs   - Input file to be decompressed.                       */
  43. /*                                                                  */
  44. /*  Outputs  - Output file containing decompressed image.           */
  45. /*                                                                  */
  46. /********************************************************************/
  47.  
  48. #include "image.h"
  49. #include "pds.h"
  50.  
  51. #define RECORD_BYTES        836
  52.  
  53. typedef struct leaf {
  54.   struct leaf *right;
  55.   short int dn;
  56.   struct leaf *left;
  57. } NODE;
  58.  
  59. NODE        *tree;             /* huffman tree pointer */
  60. static long  hist[511];        /* histogram for huffman code */
  61. static int   Decompressing= 0; /* flag for pdsRead() */
  62.  
  63. static NODE *new_node();
  64. static long int free_node();
  65.  
  66. NODE *huff_tree(hist)
  67. /****************************************************************************
  68. *_TITLE huff_tree - constructs the Huffman tree; returns pointer to root    *
  69. *_ARGS  TYPE          NAME        I/O   DESCRIPTION                         */
  70.         long int     *hist;     /* I    First difference histogram          */
  71.  
  72. {
  73.   /*  Local variables used */
  74.   long int freq_list[512];      /* Histogram frequency list */
  75.   NODE **node_list;             /* DN pointer array list */
  76.  
  77.   register long int *fp;        /* Frequency list pointer */
  78.   register NODE **np;           /* Node list pointer */
  79.  
  80.   register long int num_freq;   /* Number non-zero frequencies in histogram */
  81.   long int sum;                 /* Sum of all frequencies */
  82.  
  83.   register short int num_nodes; /* Counter for DN initialization */
  84.   register short int cnt;       /* Miscellaneous counter */
  85.  
  86.   short int znull = -1;         /* Null node value */
  87.  
  88.   register NODE *temp;          /* Temporary node pointer */
  89.  
  90.   /* Functions called */
  91.   void sort_freq();
  92.  
  93.   /***************************************************************************
  94.     Allocate the array of nodes from memory and initialize these with numbers
  95.     corresponding with the frequency list.  There are only 511 possible
  96.     permutations of first difference histograms.  There are 512 allocated
  97.     here to adhere to the FORTRAN version.
  98.    ****************************************************************************/
  99.  
  100.   fp = freq_list;
  101.   node_list = (NODE **) lmalloc(sizeof(temp)*512);
  102.   if (node_list == NULL) {
  103.     fprintf(stderr,"\nOut of memory in huff_tree!\n");
  104.     exit(1);
  105.   }
  106.   np = node_list;
  107.  
  108.   for (num_nodes=1, cnt=512 ; cnt-- ; num_nodes++) {
  109. /**************************************************************************
  110.     The following code has been added to standardize the VAX byte order
  111.     for the "long int" type.  This code is intended to make the routine
  112.     as machine independant as possible.
  113. ***************************************************************************/
  114.     unsigned char *cp = (unsigned char *) hist++;
  115.     unsigned long int j;
  116.     short int i;
  117.     for (i=4 ; --i >= 0 ; j = (j << 8) | *(cp+i))
  118.       ;
  119.  
  120.     /* Now make the assignment */
  121.     *fp++ = j;
  122.     temp = new_node(num_nodes);
  123.     *np++ = temp;
  124.   }
  125.  
  126.   (*--fp) = 0;         /* Ensure the last element is zeroed out.  */
  127.  
  128. /***************************************************************************
  129.   Now, sort the frequency list and eliminate all frequencies of zero.
  130. ****************************************************************************/
  131.  
  132.   num_freq = 512;
  133.   sort_freq(freq_list,node_list,num_freq);
  134.  
  135.   fp = freq_list;
  136.   np = node_list;
  137.  
  138.   for (num_freq=512 ; (*fp) == 0 && (num_freq) ; fp++, np++, num_freq--)
  139.     /* EMPTY */
  140.     ;
  141.  
  142. /***************************************************************************
  143.   Now create the tree.  Note that if there is only one difference value,
  144.   it is returned as the root.  On each interation, a new node is created
  145.   and the least frequently occurring difference is assigned to the right
  146.   pointer and the next least frequency to the left pointer.  The node
  147.   assigned to the left pointer now becomes the combination of the two
  148.   nodes and it's frequency is the sum of the two combining nodes.
  149. ****************************************************************************/
  150.  
  151.   for (temp=(*np) ; (num_freq--) > 1 ; ) {
  152.     temp = new_node(znull);
  153.     temp->right = (*np++);
  154.     temp->left = (*np);
  155.     *np = temp;
  156.     *(fp+1) = *(fp+1) + *fp;
  157.     *fp++ = 0;
  158.     sort_freq(fp,np,num_freq);
  159.   }
  160.  
  161.   return temp;
  162. }
  163.  
  164. static NODE *new_node(value)
  165. /****************************************************************************
  166. *_TITLE new_node - allocates a NODE structure and returns a pointer to it   *
  167. *_ARGS  TYPE        NAME        I/O     DESCRIPTION                         */
  168.         short int   value;    /* I      Value to assign to DN field         */
  169.  
  170. {
  171.   NODE *temp;         /* Pointer to the memory block */
  172.  
  173. /***************************************************************************
  174.   Allocate the memory and intialize the fields.
  175. ****************************************************************************/
  176.  
  177.   temp = (NODE *) lmalloc(sizeof(NODE));
  178.   temp->right = NULL;
  179.   temp->dn = value;
  180.   temp->left = NULL;
  181.   return temp;
  182. }
  183.  
  184. void sort_freq(freq_list,node_list,num_freq)
  185. /****************************************************************************
  186. *_TITLE sort_freq - sorts frequency and node lists in increasing freq. order*
  187. *_ARGS  TYPE       NAME            I/O  DESCRIPTION                         */
  188.      long int   *freq_list;   /* I   Pointer to frequency list           */
  189.      NODE       **node_list;  /* I   Pointer to array of node pointers   */
  190.      long int   num_freq;     /* I   Number of values in freq list       */
  191.  
  192. {
  193.   /* Local Variables */
  194.   register long int *i;       /* primary pointer into freq_list */
  195.   register long int *j;       /* secondary pointer into freq_list */
  196.  
  197.   register NODE **k;          /* primary pointer to node_list */
  198.   register NODE **l;          /* secondary pointer into node_list */
  199.  
  200.   long int temp1;             /* temporary storage for freq_list */
  201.   NODE *temp2;                /* temporary storage for node_list */
  202.  
  203.   register long int cnt;      /* count of list elements */
  204.  
  205.  
  206. /************************************************************************
  207.   Save the current element - starting with the second - in temporary
  208.   storage.  Compare with all elements in first part of list moving
  209.   each up one element until the element is larger.  Insert current
  210.   element at this point in list.
  211. *************************************************************************/
  212.  
  213.   if (num_freq <= 0)
  214.     return;      /* If no elements or invalid, return */
  215.  
  216.   for (i=freq_list, k=node_list, cnt=num_freq ; --cnt ; *j=temp1, *l=temp2) {
  217.     temp1 = *(++i);
  218.     temp2 = *(++k);
  219.  
  220.     for (j = i, l = k ;  *(j-1) > temp1 ; ) {
  221.       *j = *(j-1);
  222.       *l = *(l-1);
  223.       j--;
  224.       l--;
  225.       if ( j <= freq_list)
  226.     break;
  227.     }
  228.   }
  229.   return;
  230. }
  231.  
  232. /* free_tree - free memory of all allocated nodes
  233.  *
  234.  * This routine is supplied to the programmer to free up all the
  235.  * allocated memory required to build the huffman tree.  The count
  236.  * of the nodes freed is returned in the parameter 'nfreed'.  The
  237.  * purpose of the routine is so if the user wishes to decompress more
  238.  * than one file per run, the program will not keep allocating new
  239.  * memory without first deallocating all previous nodes associated
  240.  * with the previous file decompression.
  241.  *
  242.  * 16-AUG-89 Kris Becker   USGS, Flagstaff Original Version
  243.  */
  244.  
  245. static void free_tree(nfreed)
  246.      long int   *nfreed;  /* Return of total count of nodes freed. */
  247. {
  248.   long int total_free = 0;
  249.  
  250.   /* Simply call the free_node routine and return the result.
  251.    */
  252.  
  253.   *nfreed = free_node(tree,total_free);
  254.   return;
  255. }
  256.  
  257. /* free_node - deallocates an allocated NODE pointer
  258.  *
  259.  * free_node will check both right and left pointers of a node
  260.  * and then free the current node using the free() C utility.
  261.  * Note that all nodes attached to the node via right or left
  262.  * pointers area also freed, so be sure that this is the desired
  263.  * result when calling this routine.
  264.  *
  265.  * This routine is supplied to allow successive calls to the
  266.  * decmpinit routine.  It will free up the memory allocated
  267.  * by previous calls to the decmpinit routine.  The call to free
  268.  * a previous huffman tree is:  total = free_node(tree,(long) 0);
  269.  * This call must be done by the programmer application routine
  270.  * and is not done by any of these routines.
  271.  *
  272.  * 16-AUG-89  Kris Becker U.S.G.S  Flagstaff Original Version
  273.  */
  274.  
  275. static long int free_node(pnode,total_free)
  276.         NODE     *pnode;       /* I  Pointer to node to free               */
  277.         long int total_free;   /* I  Total number of freed nodes           */
  278. {
  279.   if (pnode == (NODE *) NULL)
  280.     return(total_free);
  281.     
  282.   if (pnode->right != (NODE *) NULL)
  283.     total_free = free_node(pnode->right,total_free);
  284.   if (pnode->left != (NODE *) NULL)
  285.     total_free = free_node(pnode->left,total_free);
  286.  
  287.   lfree((byte *) pnode);
  288.   return(total_free + 1);
  289. }
  290.  
  291. /* pdsDecompress - decompresses Huffman coded compressed image lines
  292.  */
  293. static int decompress(ibuf,obuf,nin,nout)
  294.      char       *ibuf;   /* I        Compressed data buffer              */
  295.      char       *obuf;   /* O        Decompressed image line             */
  296.      long int   *nin;    /* I        Number of bytes on input buffer     */
  297.      long int   *nout;   /* I        Number of bytes in output buffer    */
  298.  
  299. {
  300.   /* Local Variables */
  301.   register NODE *ptr = tree;        /* pointer to position in tree */
  302.   register unsigned char test;      /* test byte for bit set */
  303.   register unsigned char idn;       /* input compressed byte */
  304.  
  305.   register char odn;                /* last dn value decompressed */
  306.  
  307.   char *ilim = ibuf + *nin;         /* end of compressed bytes */
  308.   char *olim = obuf + *nout;        /* end of output buffer */
  309.   char *obuf_start= obuf;
  310.  
  311.   /* Check for valid input values for nin, nout and make initial assignments.
  312.    */
  313.  
  314.   if (ilim > ibuf && olim > obuf)
  315.     odn = *obuf++ = *ibuf++;
  316.   else {
  317.     fprintf(stderr,"\nInvalid byte count in dcmprs!\n");
  318.     return(-1);
  319.   }
  320.  
  321.   /* Decompress the input buffer.  Assign the first byte to the working
  322.    * variable, idn.  An arithmatic and (&) is performed using the variable
  323.    * 'test' that is bit shifted to the right.  If the result is 0, then
  324.    * go to right else go to left.
  325.    */
  326.  
  327.   for (idn=(*ibuf) ; ibuf < ilim  ; idn =(*++ibuf)) {
  328.     for (test=0x80 ; test ; test >>= 1) {
  329.       ptr = (test & idn) ? ptr->left : ptr->right;
  330.  
  331.       if (ptr->dn != -1) {
  332.     if (obuf >= olim)
  333.       return(obuf - obuf_start);
  334.     odn -= ptr->dn + 256;
  335.     *obuf++ = odn;
  336.     ptr = tree;
  337.       }
  338.     }
  339.   }
  340.   return(obuf - obuf_start);
  341. }
  342.  
  343. /*********************************************************************/
  344. /*                                                                   */
  345. /* subroutine read_var - read variable length records from input file*/
  346. /*                                                                   */
  347. /*********************************************************************/
  348.  
  349. static int read_var(zf, ibuf)
  350.      ZFILE *zf;
  351.      char  *ibuf;
  352. {
  353.   int   length,result,nlen;
  354.   unsigned int value;
  355.   unsigned char buf[2];
  356.  
  357.   length = 0;
  358.   result = zread(zf,buf,2);
  359.   length= memToValLSB(buf, 2);
  360.   nlen = zread(zf,(byte *)ibuf,length+(length%2));
  361.   return(length);
  362. }
  363.  
  364. skip_record(zf)
  365.      ZFILE *zf;
  366. {
  367.   unsigned int value;
  368.   unsigned char buf[2];
  369.   char *dummy;
  370.  
  371.   zread(zf, buf, 2);
  372.   value= memToValLSB(buf, 2);
  373.   dummy= (char *)lmalloc(value);
  374.   zread(zf, (byte *)dummy, value);
  375.   lfree((byte *)dummy);
  376. }
  377.  
  378. /* initialize pdsRead() stuff.  if this is a huffman-encoded file, this
  379.  * reads the histogram table and initializes the huffman tree.
  380.  */
  381.  
  382. void pdsInit(zf, type)
  383.      ZFILE *zf;
  384.      int type;
  385. {
  386.   if (type == PDSVARIABLE) {
  387.     char buf[2];
  388.     int len;
  389.     char *dummy;
  390.  
  391.     Decompressing= 1; /* flag pdsRead() to do decompressions */
  392.  
  393.     /* skip label and image histogram
  394.      */
  395.     skip_record(zf);
  396.     skip_record(zf);
  397.  
  398.     /* read in huffman encoding histogram
  399.      */
  400.  
  401.     read_var(zf, (char *)hist);
  402.     read_var(zf, (char *)hist+836);
  403.     read_var(zf, (char *)hist+1672);
  404.  
  405.     tree = huff_tree(hist);
  406.   }
  407.   else
  408.     Decompressing= 0;
  409. }
  410.  
  411. /* function which will read pds data and do decompression if necessary.
  412.  */
  413.  
  414. int pdsRead(zf, buf, size)
  415.      ZFILE *zf;
  416.      char *buf;
  417.      int size;
  418. {
  419.   static char obuf[2048];
  420.   char ibuf[2048];
  421.   int left;
  422.   int in_length;
  423.   static int out_length= 2048, out_ptr= 0;
  424.  
  425.   if (Decompressing) {
  426.     left= size;
  427.     while (left) {
  428.       if (out_ptr == out_length) {
  429.     in_length= read_var(zf, ibuf);
  430.     if (in_length < 0)
  431.       return(-1);
  432.     out_length= decompress(ibuf, obuf, &in_length, &out_length);
  433.     if (out_length < 0)
  434.       return(-1);
  435.     out_ptr= 0;
  436.       }
  437.       if (left <= (out_length - out_ptr)) {
  438.     bcopy(obuf + out_ptr, buf, size);
  439.     out_ptr += left;
  440.     return(size);
  441.       }
  442.       else {
  443.     bcopy(obuf + out_ptr, buf, out_length - out_ptr);
  444.     left= left - (out_length - out_ptr);
  445.     out_ptr= out_length;
  446.       }
  447.     }
  448.     return(size);
  449.   }
  450.   else
  451.     return(zread(zf, (byte *)buf, size));
  452. }
  453.