home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / standalone / compress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-03-29  |  12.4 KB  |  525 lines
  1. #if 0
  2. static char sccsid[]= "@(#)compress.c    @(#)compress.c    5.9 (Berkeley) 5/11/86";
  3. #endif
  4.  
  5. /*
  6.  * Compress - data compression program. This is an EXTREMELY HACKED version
  7.  * of the old compress program, solely to uncompress a -b12 stream. It runs
  8.  * in standalone mode on PDP-11s, and it is typically used to uncompress and
  9.  * fill a disk with an incoming compressed disk image.
  10.  *
  11.  * There's a whole lot of cruft I haven't bothered to take out, but it's
  12.  * mostly cpp stuff which doesn't make it into the binary.
  13.  *
  14.  * Warren Toomey    wkt@cs.adfa.oz.au    24th March 1998
  15.  */
  16.  
  17. #define    min(a,b)    ((a>b) ? b : a)
  18. #ifndef pdp11
  19. #define pdp11
  20. #endif
  21.  
  22. /*
  23.  * machine variants which require cc -Dmachine:  pdp11, z8000, pcxt
  24.  */
  25.  
  26. /*
  27.  * Set USERMEM to the maximum amount of physical user memory available
  28.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  29.  * for compression.
  30.  *
  31.  * SACREDMEM is the amount of physical memory saved for others; compress
  32.  * will hog the rest.
  33.  */
  34. #ifndef SACREDMEM
  35. #define SACREDMEM    0
  36. #endif
  37.  
  38. #ifndef USERMEM
  39. #define USERMEM     450000    /* default user memory */
  40. #endif
  41.  
  42. #ifdef interdata        /* (Perkin-Elmer) */
  43. #define SIGNED_COMPARE_SLOW    /* signed compare is slower than unsigned */
  44. #endif
  45.  
  46. #ifdef pdp11
  47. #define BITS     12        /* max bits/code for 16-bit machine */
  48. #define NO_UCHAR        /* also if "unsigned char" functions as signed
  49.                    char */
  50. #undef USERMEM
  51. #endif    /* pdp11 */        /* don't forget to compile with -i */
  52.  
  53. #ifdef z8000
  54. #define BITS     12
  55. #undef vax            /* weird preprocessor */
  56. #undef USERMEM
  57. #endif                /* z8000 */
  58.  
  59. #ifdef pcxt
  60. #define BITS   12
  61. #undef USERMEM
  62. #endif                /* pcxt */
  63.  
  64. #ifdef USERMEM
  65. #if USERMEM >= (433484+SACREDMEM)
  66. #define PBITS    16
  67. #else
  68. #if USERMEM >= (229600+SACREDMEM)
  69. #define PBITS    15
  70. #else
  71. #if USERMEM >= (127536+SACREDMEM)
  72. #define PBITS    14
  73. #else
  74. #if USERMEM >= (73464+SACREDMEM)
  75. #define PBITS    13
  76. #else
  77. #define PBITS    12
  78. #endif
  79. #endif
  80. #endif
  81. #endif
  82. #undef USERMEM
  83. #endif                /* USERMEM */
  84.  
  85. #ifdef PBITS            /* Preferred BITS for this memory size */
  86. #ifndef BITS
  87. #define BITS PBITS
  88. #endif    /* BITS */
  89. #endif                /* PBITS */
  90.  
  91. #if BITS == 16
  92. #define HSIZE    69001        /* 95% occupancy */
  93. #endif
  94. #if BITS == 15
  95. #define HSIZE    35023        /* 94% occupancy */
  96. #endif
  97. #if BITS == 14
  98. #define HSIZE    18013        /* 91% occupancy */
  99. #endif
  100. #if BITS == 13
  101. #define HSIZE    9001        /* 91% occupancy */
  102. #endif
  103. #if BITS <= 12
  104. #define HSIZE    5003        /* 80% occupancy */
  105. #endif
  106.  
  107. #ifdef M_XENIX            /* Stupid compiler can't handle arrays with */
  108. #if BITS == 16            /* more than 65535 bytes - so we fake it */
  109. #define XENIX_16
  110. #else
  111. #if BITS > 13            /* Code only handles BITS = 12, 13, or 16 */
  112. #define BITS    13
  113. #endif
  114. #endif
  115. #endif
  116.  
  117. /*
  118.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  119.  */
  120. #if BITS > 15
  121. typedef long int code_int;
  122. #else
  123. typedef int code_int;
  124. #endif
  125.  
  126. #ifdef SIGNED_COMPARE_SLOW
  127. typedef unsigned long int count_int;
  128. typedef unsigned short int count_short;
  129. #else
  130. typedef long int count_int;
  131. #endif
  132.  
  133. #ifdef NO_UCHAR
  134. typedef char char_type;
  135. #else
  136. typedef unsigned char char_type;
  137. #endif                    /* UCHAR */
  138.  
  139. char_type magic_header[] = {"\037\235"};    /* 1F 9D */
  140.  
  141. /* Defines for third byte of header */
  142. #define BIT_MASK    0x1f
  143. #define BLOCK_MASK    0x80
  144. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  145.  * a fourth header byte (for expansion).
  146.  */
  147. #define INIT_BITS 9        /* initial number of bits/code */
  148.  
  149. /*
  150.  * compress.c - File compression ala IEEE Computer, June 1984.
  151.  *
  152.  * Authors:    Spencer W. Thomas    (decvax!utah-cs!thomas)
  153.  *        Jim McKie        (decvax!mcvax!jim)
  154.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  155.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  156.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  157.  *        Joe Orost        (decvax!vax135!petsd!joe)
  158.  *
  159.  * Revision 4.0  85/07/30  12:50:00  joe
  160.  * Removed ferror() calls in output routine on every output except first.
  161.  * Prepared for release to the world.
  162.  *
  163.  */
  164.  
  165. #include <stdio.h>
  166. #include <ctype.h>
  167. #include <signal.h>
  168. #include <sys/types.h>
  169. #include <sys/stat.h>
  170.  
  171. int n_bits;            /* number of bits/code */
  172. int maxbits = BITS;        /* user settable max # bits/code */
  173. code_int maxcode;        /* maximum code, given n_bits */
  174. code_int maxmaxcode = 1 << BITS;/* should NEVER generate this code */
  175.  
  176. #ifdef COMPATIBLE        /* But wrong! */
  177. #define MAXCODE(n_bits)    (1 << (n_bits) - 1)
  178. #else
  179. #define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  180. #endif                /* COMPATIBLE */
  181.  
  182. #ifdef XENIX_16
  183. count_int htab0[8192];
  184. count_int htab1[8192];
  185. count_int htab2[8192];
  186. count_int htab3[8192];
  187. count_int htab4[8192];
  188. count_int htab5[8192];
  189. count_int htab6[8192];
  190. count_int htab7[8192];
  191. count_int htab8[HSIZE - 65536];
  192. count_int *htab[9] = {
  193. htab0, htab1, htab2, htab3, htab4, htab5, htab6, htab7, htab8};
  194.  
  195. #define htabof(i)    (htab[(i) >> 13][(i) & 0x1fff])
  196. unsigned short code0tab[16384];
  197. unsigned short code1tab[16384];
  198. unsigned short code2tab[16384];
  199. unsigned short code3tab[16384];
  200. unsigned short code4tab[16384];
  201. unsigned short *codetab[5] = {
  202. code0tab, code1tab, code2tab, code3tab, code4tab};
  203.  
  204. #define codetabof(i)    (codetab[(i) >> 14][(i) & 0x3fff])
  205.  
  206. #else                /* Normal machine */
  207.  
  208. #ifdef sel            /* gould base register braindamage */
  209. /*NOBASE*/
  210. count_int htab[HSIZE];
  211. unsigned short codetab[HSIZE];
  212.  
  213. /*NOBASE*/
  214. #else
  215. count_int htab[HSIZE];
  216. unsigned short codetab[HSIZE];
  217.  
  218. #endif    /* sel */
  219.  
  220. #define htabof(i)    htab[i]
  221. #define codetabof(i)    codetab[i]
  222. #endif                /* XENIX_16 */
  223. code_int hsize = HSIZE;        /* for dynamic table sizing */
  224. count_int fsize;
  225.  
  226. /*
  227.  * To save much memory, we overlay the table used by compress() with those
  228.  * used by decompress().  The tab_prefix table is the same size and type
  229.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  230.  * get this from the beginning of htab.  The output stack uses the rest
  231.  * of htab, and contains characters.  There is plenty of room for any
  232.  * possible stack (stack used to be 8000 characters).
  233.  */
  234.  
  235. #define tab_prefixof(i)    codetabof(i)
  236. #ifdef XENIX_16
  237. #define tab_suffixof(i)    ((char_type *)htab[(i)>>15])[(i) & 0x7fff]
  238. #define de_stack        ((char_type *)(htab2))
  239. #else                /* Normal machine */
  240. #define tab_suffixof(i)    ((char_type *)(htab))[i]
  241. #define de_stack        ((char_type *)&tab_suffixof(1<<BITS))
  242. #endif                /* XENIX_16 */
  243.  
  244. code_int free_ent = 0;        /* first unused entry */
  245. int exit_stat = 0;        /* per-file status */
  246. int perm_stat = 0;        /* permanent status */
  247.  
  248. code_int getcode();
  249. int decompress();
  250. int myread();
  251.  
  252. /*
  253.  * block compression parameters -- after all codes are used up,
  254.  * and compression rate changes, start over.
  255.  */
  256. int block_compress = BLOCK_MASK;
  257. int clear_flg = 0;
  258. long int ratio = 0;
  259.  
  260. #define CHECK_GAP 10000        /* ratio check interval */
  261. count_int checkpoint = CHECK_GAP;
  262.  
  263. /*
  264.  * the next two codes should not be changed lightly, as they must not
  265.  * lie within the contiguous general code space.
  266.  */
  267. #define FIRST    257        /* first free entry */
  268. #define    CLEAR    256        /* table clear output code */
  269.  
  270. int main()
  271. {
  272.   int i, j;
  273.   char buf[50];
  274.   char_type c, d;
  275.  
  276.   printf("zcat disk writer, known devices are ");
  277.   for (i=0; devsw[i].dv_name; i++) printf("%s ", devsw[i].dv_name);
  278.   printf("\n");
  279.   do {
  280.     printf("Enter file containing compressed data: ");
  281.     gets(buf);
  282.     i = open(buf, 0, 0);
  283.   } while (i<=0);
  284.   do {
  285.     printf("Enter device to write uncompressed data: ");
  286.     gets(buf);
  287.     j = open(buf, 1, 0777);
  288.   } while (j<=0);
  289.  
  290.   /* Check the magic number */
  291.   myread(i, &c, 1);
  292.   myread(i, &d, 1);
  293.  
  294.   if ((c != magic_header[0]) || (d != magic_header[1])) {
  295.     printf("input not in compressed format\n");
  296.     exit(1);
  297.   }
  298.   /* Get maxbits from file */
  299.   myread(i, &c, 1);
  300.   maxbits = c;
  301.   block_compress = maxbits & BLOCK_MASK;
  302.   maxbits &= BIT_MASK;
  303.   maxmaxcode = 1 << maxbits;
  304.   if (maxbits > BITS) {
  305.     printf("input compressed with %d bits, can only handle %d bits\n",
  306.        maxbits, BITS);
  307.     exit(1);
  308.   }
  309.   hsize = HSIZE;
  310.   decompress(i, j);
  311.   printf("Image written, looping indefintely\n");
  312.   while (1) ;
  313. }
  314.  
  315.  
  316. /*
  317.  * Decompress stdin to stdout.  This routine adapts to the codes in the
  318.  * file building the "string" table on-the-fly; requiring no table to
  319.  * be stored in the compressed file.  The tables used herein are shared
  320.  * with those of the compress() routine.  See the definitions above.
  321.  */
  322.  
  323. #define BSIZE 512
  324. char buf[BSIZE];
  325.  
  326. int decompress(in, out)
  327.   int in, out;
  328. {
  329.   register char_type *stackp;
  330.   register int finchar;
  331.   register code_int code, oldcode, incode;
  332.   int cnt = 0;
  333.  
  334.   /*
  335.    *  As above, initialize the first 256 entries in the table.
  336.    */
  337.   maxcode = MAXCODE(n_bits = INIT_BITS);
  338.   for (code = 255; code >= 0; code--) {
  339.     tab_prefixof(code) = 0;
  340.     tab_suffixof(code) = (char_type) code;
  341.   }
  342.   free_ent = ((block_compress) ? FIRST : 256);
  343.  
  344.   finchar = oldcode = getcode(in);
  345.   if (oldcode == -1)        /* EOF already? */
  346.     return (0);            /* Get out of here */
  347.   buf[cnt++] = (char) finchar;    /* first code must be 8 bits = char */
  348.   if (cnt == BSIZE) {
  349.     write(out, buf, BSIZE);
  350.     cnt = 0;
  351.   }
  352.   stackp = de_stack;
  353.  
  354.   while ((code = getcode(in)) > -1) {
  355.  
  356.     if ((code == CLEAR) && block_compress) {
  357.       for (code = 255; code >= 0; code--)
  358.     tab_prefixof(code) = 0;
  359.       clear_flg = 1;
  360.       free_ent = FIRST - 1;
  361.       if ((code = getcode(in)) == -1)    /* O, untimely death! */
  362.     break;
  363.     }
  364.     incode = code;
  365.     /*
  366.      *  Special case for KwKwK string.
  367.      */
  368.     if (code >= free_ent) {
  369.       *stackp++ = finchar;
  370.       code = oldcode;
  371.     }
  372.     /*
  373.      *  Generate output characters in reverse order
  374.      */
  375. #ifdef SIGNED_COMPARE_SLOW
  376.     while (((unsigned long) code) >= ((unsigned long) 256)) {
  377. #else
  378.     while (code >= 256) {
  379. #endif
  380.       *stackp++ = tab_suffixof(code);
  381.       code = tab_prefixof(code);
  382.     }
  383.     *stackp++ = finchar = tab_suffixof(code);
  384.  
  385.     /*
  386.      *  And put them out in forward order
  387.      */
  388.     do {
  389.       buf[cnt++] = *--stackp;
  390.       if (cnt == BSIZE) {
  391.     write(out, buf, BSIZE);
  392.     cnt = 0;
  393.       }
  394.     } while (stackp > de_stack);
  395.  
  396.     /*
  397.      *  Generate the new entry.
  398.      */
  399.     if ((code = free_ent) < maxmaxcode) {
  400.       tab_prefixof(code) = (unsigned short) oldcode;
  401.       tab_suffixof(code) = finchar;
  402.       free_ent = code + 1;
  403.     }
  404.     /*
  405.      *  Remember previous code.
  406.      */
  407.     oldcode = incode;
  408.   }
  409.   if (cnt)
  410.     write(out, buf, BSIZE);
  411.   return (0);
  412. }
  413.  
  414. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  415.  
  416. /*****************************************************************
  417.  * TAG( getcode )
  418.  *
  419.  * Read one code from the standard input.  If EOF, return -1.
  420.  * Inputs:
  421.  *     stdin
  422.  * Outputs:
  423.  *     code or -1 is returned.
  424.  */
  425.  
  426. code_int
  427. getcode(in)
  428.   int in;
  429. {
  430.   /*
  431.    * On the VAX, it is important to have the register declarations in exactly
  432.    * the order given, or the asm will break.
  433.    */
  434.   register code_int code;
  435.   static int offset = 0, size = 0;
  436.   static char_type buf[BITS];
  437.   register int r_off, bits;
  438.   register char_type *bp = buf;
  439.  
  440.   if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  441.     /*
  442.      * If the next entry will be too big for the current code size, then we
  443.      * must increase the size.  This implies reading a new buffer full, too.
  444.      */
  445.     if (free_ent > maxcode) {
  446.       n_bits++;
  447.       if (n_bits == maxbits)
  448.     maxcode = maxmaxcode;    /* won't get any bigger now */
  449.       else
  450.     maxcode = MAXCODE(n_bits);
  451.     }
  452.     if (clear_flg > 0) {
  453.       maxcode = MAXCODE(n_bits = INIT_BITS);
  454.       clear_flg = 0;
  455.     }
  456.     size = myread(in, buf, n_bits);
  457.     if (size <= 0)
  458.       return -1;        /* end of file */
  459.     offset = 0;
  460.     /* Round size down to integral number of codes */
  461.     size = (size << 3) - (n_bits - 1);
  462.   }
  463.   r_off = offset;
  464.   bits = n_bits;
  465. #ifdef vax
  466.   asm("extzv   r10,r9,(r8),r11");
  467. #else                /* not a vax */
  468.   /*
  469.    * Get to the first byte.
  470.    */
  471.   bp += (r_off >> 3);
  472.   r_off &= 7;
  473.   /* Get first part (low order bits) */
  474. #ifdef NO_UCHAR
  475.   code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  476. #else
  477.   code = (*bp++ >> r_off);
  478. #endif                /* NO_UCHAR */
  479.   bits -= (8 - r_off);
  480.   r_off = 8 - r_off;        /* now, offset into code word */
  481.   /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  482.   if (bits >= 8) {
  483. #ifdef NO_UCHAR
  484.     code |= (*bp++ & 0xff) << r_off;
  485. #else
  486.     code |= *bp++ << r_off;
  487. #endif                /* NO_UCHAR */
  488.     r_off += 8;
  489.     bits -= 8;
  490.   }
  491.   /* high order bits. */
  492.   code |= (*bp & rmask[bits]) << r_off;
  493. #endif                /* vax */
  494.   offset += n_bits;
  495.  
  496.   return code;
  497. }
  498.  
  499. static char mybuf[512];
  500. static int mycnt = 512;
  501.  
  502. /* Fudge a read of < 512 bytes */
  503.  
  504. myread(fdesc, buf, count)
  505.   int fdesc;
  506.   char *buf;
  507.   int count;
  508. {
  509.   int j, i = 0;
  510.  
  511.   while (count) {
  512.     if (mycnt == 512) {
  513.       j= read(fdesc, mybuf, 512);
  514.       if (j==0) return(-1);
  515.       mycnt = 0;
  516.     }
  517.     while (count && (mycnt != 512)) {
  518.       *buf++ = mybuf[mycnt++];
  519.       i++;
  520.       count--;
  521.     }
  522.   }
  523.   return (i);
  524. }
  525.