home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 496.lha / Backup_v2.06 / compress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-07  |  11.4 KB  |  531 lines
  1.  
  2. /*
  3.  *  COMPRESS.C
  4.  *
  5.  */
  6.  
  7. #include "defs.h"
  8.  
  9. #define ngetchar()  oreadchar()
  10. #define nputchar(n) mputc(n)
  11.  
  12. #ifndef min
  13. #define min(a,b)        ((a>b) ? b : a)
  14. #endif
  15.  
  16. #define BITS        13
  17.  
  18. #ifdef _DCC
  19. #define HSIZE  9001
  20. #else
  21.  
  22. #if BITS == 16
  23. #define HSIZE  69001           /* 95% occupancy */
  24. #endif
  25. #if BITS == 15
  26. #define HSIZE  35023           /* 94% occupancy */
  27. #endif
  28. #if BITS == 14
  29. #define HSIZE  18013           /* 91% occupancy */
  30. #endif
  31. #if BITS == 13
  32. #define HSIZE  9001           /* 91% occupancy */
  33. #endif
  34. #if BITS <= 12
  35. #define HSIZE  5003           /* 80% occupancy */
  36. #endif
  37.  
  38. #endif
  39.  
  40. typedef long        code_int;
  41. typedef long        count_int;
  42. typedef unsigned char    char_type;
  43.  
  44. #define MAXCODE(n_bits)  ((1 << (n_bits)) - 1)
  45. #define INIT_BITS 9            /* initial number of bits/code */
  46.  
  47. int n_bits;                /* number of bits/code            */
  48. int maxbits;                /* user settable max # bits/code    */
  49. code_int maxcode;            /* maximum code, given n_bits        */
  50. code_int maxmaxcode;            /* should NEVER generate this code  */
  51.  
  52. __far count_int   htab[HSIZE];
  53. __far uword      codetab[HSIZE];
  54.  
  55. #define htabof(i)       htab[i]
  56. #define codetabof(i)    codetab[i]
  57.  
  58. code_int hsize = HSIZE;         /* for dynamic table sizing */
  59.  
  60. #define tab_prefixof(i)     codetabof(i)
  61. #define tab_suffixof(i)     ((char_type *)(htab))[i]
  62. #define de_stack        ((char_type *)&tab_suffixof(1<<BITS))
  63.  
  64. code_int free_ent;            /* first unused entry */
  65. code_int getcode();
  66. void output (code_int);
  67. void cl_block(void);
  68. void cl_hash(count_int);
  69.  
  70. #define CHECK_GAP 10000 /* ratio check interval */
  71.  
  72. int    block_compress = 1;
  73. int    clear_flg;
  74. long    ratio;
  75. count_int checkpoint;
  76.  
  77. /*
  78.  * the next two codes should not be changed lightly, as they must not
  79.  * lie within the contiguous general code space.
  80.  */
  81.  
  82. #define FIRST    257    /* first free entry */
  83. #define CLEAR    256    /* table clear output code */
  84.  
  85. static int offset;
  86. long int in_count = 1;            /* length of input */
  87.  
  88. /*
  89.  *  Compress a file to memory-buffers and return TRUE if the compressed
  90.  *  size is smaller than the actual size.
  91.  */
  92.  
  93. long
  94. CompressFile(name, fsize)
  95. char *name;
  96. long fsize;
  97. {
  98.     long fcode;
  99.     code_int i = 0;
  100.     int c;
  101.     code_int ent;
  102.     int disp;
  103.     code_int hsize_reg;
  104.     int hshift;
  105.  
  106.     {
  107.     register NODE *node;
  108.     for (node = (NODE *)CSList.mlh_Head; node->ln_Succ; node = node->ln_Succ) {
  109.         if (WildCmp(node->ln_Name, name)) {
  110.         if (Verbose)
  111.             printf("  Will not compress %s\n", name);
  112.         return(0);
  113.         }
  114.     }
  115.     }
  116.  
  117.     if (WildCmp("*.Z", name) || WildCmp("*.ARC", name) || WildCmp("*.ZOO", name)) {
  118.     if (Verbose)
  119.         printf("  Will not compress %s\n", name);
  120.     return(0);
  121.     }
  122.  
  123.     CLen = 0;
  124.     CWrite = GetHead(&CList);
  125.     if (CWrite == NULL)
  126.     CWrite = NewSComp();
  127.     CWrite->N = 0;
  128.  
  129.     setmem(htab, sizeof(htab), 0);
  130.     setmem(codetab, sizeof(codetab), 0);
  131.  
  132.     hsize = HSIZE;
  133.     if ( fsize < (1 << 12) )
  134.     hsize = min ( 5003, HSIZE );
  135.     else if ( fsize < (1 << 13) )
  136.     hsize = min ( 9001, HSIZE );
  137.     else if ( fsize < (1 << 14) )
  138.     hsize = min ( 18013, HSIZE );
  139.     else if ( fsize < (1 << 15) )
  140.     hsize = min ( 35023, HSIZE );
  141.     else if ( fsize < 47000 )
  142.     hsize = min ( 50021, HSIZE );
  143.  
  144.     offset = clear_flg = ratio = 0;
  145.     in_count = 1;
  146.     checkpoint = CHECK_GAP;
  147.     n_bits  = INIT_BITS;        /* number of bits/code            */
  148.     maxbits = BITS;            /* user settable max # bits/code    */
  149.     maxcode = MAXCODE(INIT_BITS);       /* maximum code, given n_bits       */
  150.     maxmaxcode = 1 << BITS;        /* should NEVER generate this code  */
  151.     free_ent = ((block_compress) ? FIRST : 256 );
  152.  
  153.     ent = ngetchar();
  154.  
  155.     hshift = 0;
  156.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  157.     hshift++;
  158.     hshift = 8 - hshift;        /* set hash code range bound */
  159.  
  160.     hsize_reg = hsize;
  161.     cl_hash((count_int)hsize_reg);      /* clear hash table */
  162.  
  163.     /*printf("hshift %d hsr %d,%d\n", hshift, hsize_reg, hsize);*/
  164.  
  165.     while ((c = ngetchar()) != EOF) {
  166.     in_count++;
  167.     fcode = (long) (((long) c << maxbits) + ent);
  168.     i = ((c << hshift) ^ ent);      /* xor hashing */
  169.  
  170.     /*printf("c %02x fcode %08lx i %d ent %08lx\n", c, fcode, i, ent);*/
  171.  
  172.     if (i >= hsize_reg) {
  173.         /*printf("compress error A1 : %d on $%02x ent %lx\n", i, c, ent);*/
  174.         if (i >= HSIZE) {
  175.         puts("XXX1");
  176.         continue;
  177.         }
  178.     }
  179.  
  180.     if (htabof (i) == fcode) {
  181.         ent = codetabof(i);
  182.         continue;
  183.     } else if ((long)htabof (i) < 0)    /* empty slot */
  184.         goto nomatch;
  185.     disp = hsize_reg - i;        /* secondary hash (after G. Knott) */
  186.     if (i == 0)
  187.         disp = 1;
  188. probe:
  189.     if ((i -= disp) < 0)
  190.         i += hsize_reg;
  191.  
  192.     if (i >= hsize_reg || i < 0) {
  193.         /*printf("compress error A2 : %d on $%02x\n", i, c);*/
  194.         if (i >= HSIZE) {
  195.         puts("XXX2");
  196.         continue;
  197.         }
  198.     }
  199.  
  200.  
  201.     if (htabof (i) == fcode) {
  202.         ent = codetabof(i);
  203.         continue;
  204.     }
  205.     if ((long)htabof (i) > 0)
  206.         goto probe;
  207. nomatch:
  208.     output ((code_int) ent);
  209.     ent = c;
  210.     if (free_ent < maxmaxcode) {
  211.         codetabof(i) = free_ent++; /* code -> hashtable */
  212.         htabof(i) = fcode;
  213.     }
  214.     else if ((count_int)in_count >= checkpoint && block_compress)
  215.         cl_block ();
  216.     }
  217.  
  218.     /*
  219.      * Put out the final code.
  220.      */
  221.  
  222.     output((code_int)ent);
  223.     output((code_int)-1);
  224.  
  225.     return(CLen < fsize);
  226. }
  227.  
  228. static char buf[BITS];
  229.  
  230. char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  231. char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  232.  
  233. void
  234. output( code )
  235. code_int  code;
  236. {
  237.     register int r_off = offset, bits= n_bits;
  238.     register char * bp = buf;
  239.  
  240.     if ( code >= 0 ) {
  241.     /*
  242.      * Get to the first byte.
  243.      */
  244.     bp += (r_off >> 3);
  245.     r_off &= 7;
  246.     /*
  247.      * Since code is always >= 8 bits, only need to mask the first
  248.      * hunk on the left.
  249.      */
  250.     *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  251.     bp++;
  252.     bits -= (8 - r_off);
  253.     code >>= 8 - r_off;
  254.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  255.     if ( bits >= 8 ) {
  256.         *bp++ = code;
  257.         code >>= 8;
  258.         bits -= 8;
  259.     }
  260.     /* Last bits. */
  261.     if(bits)
  262.         *bp = code;
  263.  
  264.     offset += n_bits;
  265.     if (offset == (n_bits << 3)) {
  266.         bp = buf;
  267.         bits = n_bits;
  268.         mwrite(bp, bits);
  269.         bp += bits;
  270.         bits = 0;
  271.         offset = 0;
  272.     }
  273.  
  274.     /*
  275.      * If the next entry is going to be too big for the code size,
  276.      * then increase it, if possible.
  277.      */
  278.  
  279.     if (free_ent > maxcode || (clear_flg > 0)) {
  280.         /*
  281.          * Write the whole buffer, because the input side won't
  282.          * discover the size increase until after it has read it.
  283.          */
  284.         if (offset > 0)
  285.         mwrite(buf, n_bits);
  286.         offset = 0;
  287.  
  288.         if (clear_flg) {
  289.         n_bits = INIT_BITS;
  290.         maxcode = MAXCODE(INIT_BITS);
  291.         clear_flg = 0;
  292.         } else {
  293.         n_bits++;
  294.         if (n_bits == maxbits)
  295.             maxcode = maxmaxcode;
  296.         else
  297.             maxcode = MAXCODE(n_bits);
  298.         }
  299.     }
  300.     } else {
  301.     /*
  302.      * At EOF, write the rest of the buffer.
  303.      */
  304.     if (offset > 0)
  305.         mwrite(buf, (offset + 7) / 8);
  306.     offset = 0;
  307.     }
  308. }
  309.  
  310.  
  311. char *
  312. xrindex(s, c)            /* For those who don't have it in libc.a */
  313. register char *s, c;
  314. {
  315.     char *p;
  316.     for (p = NULL; *s; s++) {
  317.     if (*s == c)
  318.         p = s;
  319.     }
  320.     return(p);
  321. }
  322.  
  323. void
  324. cl_block()             /* table clear for block compress */
  325. {
  326.     register long int rat;
  327.  
  328.     checkpoint = in_count + CHECK_GAP;
  329.  
  330.     if (in_count > 0x007fffff) { /* shift will overflow */
  331.     rat = CLen >> 8;
  332.     if (rat == 0) {          /* Don't divide by zero */
  333.         rat = 0x7fffffff;
  334.     } else {
  335.         rat = in_count / rat;
  336.     }
  337.     } else {
  338.     rat = (in_count << 8) / CLen;      /* 8 fractional bits */
  339.     }
  340.     if (rat > ratio) {
  341.     ratio = rat;
  342.     } else {
  343.     ratio = 0;
  344.     cl_hash ( (count_int) hsize );
  345.     free_ent = FIRST;
  346.     clear_flg = 1;
  347.     output ( (code_int) CLEAR );
  348.     }
  349. }
  350.  
  351. void
  352. cl_hash(hsize)          /* reset code table */
  353.     register count_int hsize;
  354. {
  355.     register count_int *htab_p = htab+hsize;
  356.     register long i;
  357.     register long m1 = -1;
  358.  
  359.     i = hsize - 16;
  360.     do {                /* might use Sys V memset(3) here */
  361.         *(htab_p-16) = m1;
  362.         *(htab_p-15) = m1;
  363.         *(htab_p-14) = m1;
  364.         *(htab_p-13) = m1;
  365.         *(htab_p-12) = m1;
  366.         *(htab_p-11) = m1;
  367.         *(htab_p-10) = m1;
  368.         *(htab_p-9) = m1;
  369.         *(htab_p-8) = m1;
  370.         *(htab_p-7) = m1;
  371.         *(htab_p-6) = m1;
  372.         *(htab_p-5) = m1;
  373.         *(htab_p-4) = m1;
  374.         *(htab_p-3) = m1;
  375.         *(htab_p-2) = m1;
  376.         *(htab_p-1) = m1;
  377.         htab_p -= 16;
  378.     } while ((i -= 16) >= 0);
  379.     for ( i += 16; i > 0; i-- )
  380.         *--htab_p = m1;
  381. }
  382.  
  383. void
  384. UnCompressFile(insize)
  385. long insize;
  386. {
  387.     register char_type *stackp;
  388.     register int finchar;
  389.     register code_int code, oldcode, incode;
  390.  
  391.     /*
  392.      * As above, initialize the first 256 entries in the table.
  393.      */
  394.  
  395.     setmem(htab, sizeof(htab), 0);
  396.     setmem(codetab, sizeof(codetab), 0);
  397.  
  398.     offset = clear_flg = ratio = 0;
  399.     in_count = 1;
  400.     checkpoint = CHECK_GAP;
  401.     n_bits  = INIT_BITS;        /* number of bits/code            */
  402.     maxbits = BITS;            /* user settable max # bits/code    */
  403.     maxcode = MAXCODE(INIT_BITS);       /* maximum code, given n_bits       */
  404.     maxmaxcode = 1 << BITS;        /* should NEVER generate this code  */
  405.  
  406.     for ( code = 255; code >= 0; code-- ) {
  407.     tab_prefixof(code) = 0;
  408.     tab_suffixof(code) = (char_type)code;
  409.     }
  410.     free_ent = ((block_compress) ? FIRST : 256 );
  411.  
  412.     finchar = oldcode = getcode();
  413.     if (oldcode == -1)          /* EOF already? */
  414.     return;         /* Get out of here */
  415.     oputc((char)finchar);       /* first code must be 8 bits = char */
  416.     stackp = de_stack;
  417.  
  418.     while ((code = getcode()) > -1) {
  419.     if ((code == CLEAR) && block_compress) {
  420.         for (code = 255; code >= 0; code--)
  421.         tab_prefixof(code) = 0;
  422.         clear_flg = 1;
  423.         free_ent = FIRST - 1;
  424.         if ((code = getcode()) == -1)   /* O, untimely death! */
  425.         break;
  426.     }
  427.     incode = code;
  428.     /*
  429.      * Special case for KwKwK string.
  430.      */
  431.     if (code >= free_ent) {
  432.         *stackp++ = finchar;
  433.         code = oldcode;
  434.     }
  435.  
  436.     /*
  437.      * Generate output characters in reverse order
  438.      */
  439.     while ( code >= 256 ) {
  440.         *stackp++ = tab_suffixof(code);
  441.         code = tab_prefixof(code);
  442.     }
  443.     *stackp++ = finchar = tab_suffixof(code);
  444.  
  445.     /*
  446.      * And put them out in forward order
  447.      */
  448.     do
  449.         oputc (*--stackp);
  450.     while (stackp > de_stack);
  451.  
  452.     /*
  453.      * Generate the new entry.
  454.      */
  455.     if ((code=free_ent) < maxmaxcode) {
  456.         tab_prefixof(code) = (unsigned short)oldcode;
  457.         tab_suffixof(code) = finchar;
  458.         free_ent = code+1;
  459.     }
  460.     /*
  461.      * Remember previous code.
  462.      */
  463.     oldcode = incode;
  464.     }
  465. }
  466.  
  467. code_int
  468. getcode()
  469. {
  470.     /*
  471.      * On the VAX, it is important to have the register declarations
  472.      * in exactly the order given, or the asm will break.
  473.      */
  474.  
  475.     register code_int code;
  476.     static int offset = 0, size = 0;
  477.     static char_type buf[BITS];
  478.     register int r_off, bits;
  479.     register char_type *bp = buf;
  480.  
  481.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  482.     /*
  483.      * If the next entry will be too big for the current code
  484.      * size, then we must increase the size.  This implies reading
  485.      * a new buffer full, too.
  486.      */
  487.     if ( free_ent > maxcode ) {
  488.         n_bits++;
  489.         if ( n_bits == maxbits )
  490.         maxcode = maxmaxcode;    /* won't get any bigger now */
  491.         else
  492.         maxcode = MAXCODE(n_bits);
  493.     }
  494.     if ( clear_flg > 0) {
  495.         maxcode = MAXCODE (n_bits = INIT_BITS);
  496.         clear_flg = 0;
  497.     }
  498.     size = oread(buf, n_bits);
  499.     if (size <= 0)
  500.         return -1;            /* end of file */
  501.     offset = 0;
  502.     size = (size << 3) - (n_bits - 1);
  503.     }
  504.     r_off = offset;
  505.     bits = n_bits;
  506.  
  507.     /*
  508.      * Get to the first byte.
  509.      */
  510.     bp += (r_off >> 3);
  511.     r_off &= 7;
  512.     /* Get first part (low order bits) */
  513.  
  514.     code = (*bp++ >> r_off);
  515.  
  516.     bits -= (8 - r_off);
  517.     r_off = 8 - r_off;        /* now, offset into code word */
  518.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  519.     if ( bits >= 8 ) {
  520.         code |= *bp++ << r_off;
  521.         r_off += 8;
  522.         bits -= 8;
  523.     }
  524.     /* high order bits. */
  525.     code |= (*bp & rmask[bits]) << r_off;
  526.  
  527.     offset += n_bits;
  528.  
  529.     return code;
  530. }
  531.