home *** CD-ROM | disk | FTP | other *** search
/ CP/M / CPM_CDROM.iso / cpm / cpm68k / arc68k.arc / ARCUSQ.C < prev    next >
Text File  |  1987-11-27  |  3KB  |  108 lines
  1.  
  2. /*
  3.  *      arcusq.c        1.1
  4.  *
  5.  *      Author: Thom Henderson
  6.  *      Original System V port: Mike Stump
  7.  *      Enhancements, Bug fixes, and cleanup: Chris Seaman
  8.  *      Date: Fri Mar 20 09:57:02 1987
  9.  *      Last Mod.       3/21/87
  10.  *
  11.  */
  12.  
  13. /*
  14.  * ARC - Archive utility - ARCUSQ
  15.  * 
  16.  * Version 3.13, created on 01/30/86 at 20:11:42
  17.  * 
  18.  * (C) COPYRIGHT 1985 by System Enhancement Associates; ALL RIGHTS RESERVED
  19.  * 
  20.  *     Description:
  21.  *          This file contains the routines used to expand a file
  22.  *          which was packed using Huffman squeezing.
  23.  * 
  24.  *          Most of this code is taken from an USQ program by Richard
  25.  *          Greenlaw, which was adapted to CI-C86 by Robert J. Beilstein.
  26.  */
  27.  
  28. #include "arc.h"
  29.  
  30. /* stuff for Huffman unsqueezing */
  31.  
  32. #define ERROR (-1)
  33. #define SPEOF 256                      /* special endfile token */
  34. #define NUMVALS 257                    /* 256 data values plus SPEOF */
  35.  
  36. struct u_nd {                          /* decoding tree */
  37.   INT child[2];                        /* left, right */
  38. } u_node[NUMVALS];                     /* use large buffer */
  39.  
  40. static INT bpos;                       /* last bit position read */
  41. static INT curin;                      /* last byte value read */
  42. static INT numnodes;                   /* number of nodes in decode tree */
  43.  
  44. static INT get_int(f)                  /* get an integer */
  45. FILE *f;                               /* file to get it from */
  46. {
  47.     INT i;
  48.  
  49.     i = getc_unp(f);
  50.     return((short)(i | (getc_unp(f)<<8)));
  51. }
  52.  
  53. INT init_usq(f)                        /* initialize Huffman unsqueezing */
  54. FILE *f;                               /* file containing squeezed data */
  55. {
  56.     INT i;                             /* node index */
  57.  
  58.     bpos = 99;                         /* force initial read */
  59.  
  60.     numnodes = get_int(f);
  61.  
  62.     if (numnodes<0 || numnodes>=NUMVALS)
  63.         abort("File has an invalid decode tree");
  64.  
  65.     /* initialize for possible empty tree (SPEOF only) */
  66.  
  67.     u_node[0].child[0] = -(SPEOF + 1);
  68.     u_node[0].child[1] = -(SPEOF + 1);
  69.  
  70.     for (i=0; i<numnodes; ++i)         /* get decoding tree from file */
  71.     {
  72.         u_node[i].child[0] = get_int(f);
  73.         u_node[i].child[1] = get_int(f);
  74.     }
  75. }
  76.  
  77. INT getc_usq(f)                        /* get byte from squeezed file */
  78. FILE *f;                               /* file containing squeezed data */
  79. {
  80.     INT i;                             /* tree index */
  81.  
  82.     /* follow bit stream in tree to a leaf */
  83.  
  84.     for (i=0; i>=0; )                  /* work down(up?) from root */
  85.     {
  86.         if (++bpos>7)
  87.         {
  88.             if ((curin=getc_unp(f)) == ERROR)
  89.                 return(ERROR);
  90.             bpos = 0;
  91.  
  92.             /* move a level deeper in tree */
  93.             i = u_node[i].child[1&curin];
  94.         }
  95.         else
  96.             i = u_node[i].child[1 & (curin >>= 1)];
  97.     }
  98.  
  99.     /* decode fake node index to original data value */
  100.  
  101.     i = -(i + 1);
  102.  
  103.     /* decode special endfile token to normal EOF */
  104.  
  105.     i = (i==SPEOF) ? EOF : i;
  106.     return(i);
  107. }
  108.