home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / packer / zip4c / shrink.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-10-03  |  10.2 KB  |  392 lines
  1. /*
  2.  
  3.  Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
  4.  Permission is granted to any individual or institution to use, copy, or
  5.  redistribute this software so long as all of the original files are included
  6.  unmodified, that it is not sold for profit, and that this copyright notice
  7.  is retained.
  8.  
  9. */
  10.  
  11. /*
  12.  *  shrink.c by Mark Adler.
  13.  */
  14.  
  15. #include "zip.h"
  16. #include "tempf.h"
  17.  
  18.  
  19. /*
  20.    Shrink.Pas version 1.2 by R. P. Byrne, 1989 (in Pascal and assembler).
  21.    We here heartily acknowledge R. P. Byrne's contribution to this project.
  22.    The existence of this program really triggered our efforts to write a
  23.    portable Unix zip.  What little remains of Byrne's program lies in this
  24.    source file, and those remnants are mostly in the variable and routine
  25.    names, since it has been translated and extensively modified and rewritten.
  26.  
  27.    Stolen, translated into C, and modified by Mark Adler, 11 October 1990.
  28.    Severely modified again by Mark Adler, 11 July 1991, to remove the
  29.    unnecessary FreeList and ClearTable arrays, and to replace the recursive
  30.    Prune() routine with a non-recursive method.
  31.    As Stravinsky once said: "Mediocre composers plagiarize.
  32.                              Great composers steal."
  33. */
  34.  
  35. /*   Compress a set of input files into a Zip file using Lempel-Ziv-Welch */
  36. /*   (LZW) compression techniques (the "shrink" method). */
  37.  
  38.  
  39. #define MINBITS         9       /* Starting code size of 9 bits */
  40. #define MAXBITS         13      /* Maximum code size of 13 bits */
  41. #define TABLESIZE       8191    /* We'll need 4K entries in table */
  42. #define SPECIAL         256     /* Special function code */
  43. #define INCSIZE         1       /* Code for a jump in code size */
  44. #define CLEARCODE       2       /* Code for code table has been cleared */
  45. #define FIRSTENTRY      257     /* First available table entry */
  46.  
  47.  
  48. /* Define data types needed to implement a code table for LZW compression */
  49.  
  50. typedef struct CodeRec {
  51.   /* Code Table record format... */
  52.   short Child;          /* Addr of 1st suffix for this prefix */
  53.   short Sibling;        /* Addr of next suffix in chain */
  54.   uch Suffix;           /* Suffix character */
  55. } CodeRec;
  56.  
  57. typedef CodeRec CodeArray[TABLESIZE + 1];       /* Define the code table */
  58.  
  59.  
  60.  
  61. /* Private globals */
  62. local CodeRec far *CodeTable;   /* Points to code table for LZW compression */
  63.  
  64. local int NextFree;     /* Next free table entry */
  65.  
  66. local int CodeSize;     /* Size of codes (in bits) currently being written */
  67. local int MaxCode;      /* Largest code that can be written in CodeSize bits */
  68.  
  69. local int FirstCh;      /* Flag indicating the START of a shrink operation */
  70.  
  71. local tFILE *tempf = NULL;      /* Temporary file */
  72. local ulg count;                /* Count of bytes written */
  73.  
  74.  
  75. /* Local functions */
  76. #ifdef PROTO
  77.    local void PutCode(int);
  78.    local int Build_Data_Structures(void);
  79.    local void Destroy_Data_Structures(void);
  80.    local void Initialize_Data_Structures(void);
  81.    local void Clear_Table(void);
  82.    local void Table_Add(int, int);
  83. #endif /* PROTO */
  84.  
  85.  
  86. /* Macro for PutCode() that writes to tempf and counts bytes in count */
  87. #define PUT(c) {tputc(c, tempf); count++;}
  88.  
  89. local void PutCode(c)
  90. int c;                  /* code to send */
  91. /* Write out the low CodeSize bits of c using the PUT macro.  If c is -1,
  92.    then flush the bit buffer.  Assumes CodeSize < 16.  By Mark Adler. */
  93. {
  94.   static int b = 0;     /* current bits waiting to go out */
  95.   static int n = 0;     /* number of bits in b */
  96.   /* masks for all bit values */
  97.   static int x[] = {0, 1, 3, 7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff,
  98.                 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff};
  99.  
  100.   if (c == -1)
  101.   {
  102.     if (n)
  103.     {
  104.       if (n > 8)
  105.       {
  106.         PUT((char)b)
  107.         PUT((char)((b >> 8) & x[n - 8]))
  108.       }
  109.       else
  110.         PUT((char)(b & x[n]))
  111.       b = n = 0;
  112.     }
  113.   }
  114.   else
  115.   {
  116.     b |= (c & x[CodeSize]) << n;
  117.     n += CodeSize;
  118.     if (n >= 16)
  119.     {
  120.       PUT((char)b)
  121.       PUT((char)(b >> 8))
  122.       if (n == 16)
  123.         b = n = 0;
  124.       else
  125.       {
  126.         n -= 16;
  127.         b = (c >> (CodeSize - n)) & x[n];
  128.       }
  129.     }
  130.   }
  131. }
  132.  
  133.  
  134.  
  135. local int Build_Data_Structures()
  136. /* Allocate tables for shrinking.  Return true on failure. */
  137. {
  138.   return (CodeTable = (CodeRec far *)farmalloc(sizeof(CodeArray))) == NULL;
  139. }
  140.  
  141.  
  142.  
  143. local void Destroy_Data_Structures()
  144. /* Deallocate tables for shrinking. */
  145. {
  146.   if (CodeTable != NULL)
  147.   {
  148.     farfree((voidp far *)CodeTable);
  149.     CodeTable = NULL;
  150.   }
  151. }
  152.  
  153.  
  154.  
  155. local void Initialize_Data_Structures()
  156. /* Clear tables for shrinking. */
  157. {
  158.   int i;                /* counter for table entries */
  159.   CodeRec far *t;       /* pointer to current table entry */
  160.  
  161.   /* Initialize parent symbols */
  162.   for (i = 0, t = CodeTable; i <= 255; i++, t++)
  163.   {
  164.     t->Child = -1;
  165.     t->Suffix = (uch)i;
  166.   }
  167.  
  168.   /* Build free list */
  169.   NextFree = FIRSTENTRY;
  170.   for (i = FIRSTENTRY, t = CodeTable + FIRSTENTRY; i < TABLESIZE; i++, t++)
  171.     t->Child = i + 1;
  172.   t->Child = -1;
  173. }
  174.  
  175.  
  176.  
  177. local void Clear_Table()
  178. /* Clear the leaves of the tree--assume all entries used (NextFree == -1) */
  179. {
  180.   int n;                /* node counter */
  181.   CodeRec far *p;       /* pointer to next node to look at */
  182.   short far *q;         /* pointer to node child or sibling entry */
  183.  
  184.   /* Mark leaf nodes */
  185.   p = CodeTable + TABLESIZE;
  186.   n = TABLESIZE + 1 - FIRSTENTRY;
  187.   do {
  188.     if (p->Child == -1)
  189.       p->Child = -2;
  190.     p--;
  191.   } while (--n);
  192.  
  193.   /* Shake leaves from tree */
  194.   p = CodeTable;
  195.   n = 256;
  196.   do {
  197.     q = &p->Child;
  198.     while (*q != -1 && CodeTable[*q].Child == -2)
  199.       *q = CodeTable[*q].Sibling;
  200.     p++;
  201.   } while (--n);
  202.   p = CodeTable + FIRSTENTRY;
  203.   n = TABLESIZE + 1 - FIRSTENTRY;
  204.   do {
  205.     if (p->Child != -2)
  206.     {
  207.       q = &p->Child;
  208.       while (*q != -1 && CodeTable[*q].Child == -2)
  209.         *q = CodeTable[*q].Sibling;
  210.       q = &p->Sibling;
  211.       while (*q != -1 && CodeTable[*q].Child == -2)
  212.         *q = CodeTable[*q].Sibling;
  213.     }
  214.     p++;
  215.   } while (--n);
  216.  
  217.   /* Build the list of free table entries */
  218.   NextFree = -1;
  219.   p = CodeTable + TABLESIZE;
  220.   n = TABLESIZE + 1 - FIRSTENTRY;
  221.   do {
  222.     if (p->Child == -2)
  223.     {
  224.       p->Child = NextFree;
  225.       NextFree = n + FIRSTENTRY - 1;
  226.     }
  227.     p--;
  228.   } while (--n);
  229. }
  230.  
  231.  
  232.  
  233. local void Table_Add(p, s)
  234. int p;                  /* prefix to add to */
  235. int s;                  /* suffix to add to it */
  236. /* Add an entry to the table. */
  237. {
  238.   int f;                /* next free node */
  239.  
  240.   if ((f = NextFree) != -1)
  241.   {
  242.     NextFree = CodeTable[f].Child;
  243.     CodeTable[f].Child = -1;
  244.     CodeTable[f].Sibling = -1;
  245.     CodeTable[f].Suffix = (uch)s;
  246.     if (CodeTable[p].Child == -1)
  247.       CodeTable[p].Child = f;
  248.     else
  249.     {
  250.       p = CodeTable[p].Child;
  251.       while (CodeTable[p].Sibling != -1)
  252.         p = CodeTable[p].Sibling;
  253.       CodeTable[p].Sibling = f;
  254.     }
  255.   }
  256. }
  257.  
  258.  
  259. local int lastcode;
  260.  
  261. int shr_setup()
  262. /* Initialize shrink() routines.  Return an error code in the ZE_ class. */
  263. {
  264.   if (Build_Data_Structures())
  265.     return ZE_MEM;
  266.   Initialize_Data_Structures();
  267.   FirstCh = 1;
  268.   lastcode = -1;
  269.   if ((tempf = topen('S')) == NULL)
  270.     return ZE_MEM;
  271.   count = 0;
  272.   return ZE_OK;
  273. }
  274.  
  275.  
  276. int shr_p1(b, n)
  277. uch *b;                 /* buffer with bytes to shrink */
  278. extent n;               /* number of bytes in buffer */
  279. /* Shrink n bytes at *b.  Return an error code in the ZE_ class. */
  280. {
  281.   int f;                /* result of Table_Lookup */
  282.   int s;                /* byte to shrink */
  283.  
  284.   if (FirstCh && n)
  285.   {                             /* If just getting started ... */
  286.     CodeSize = MINBITS;         /*   Initialize code size to minimum */
  287.     MaxCode = (1 << CodeSize) - 1;
  288.     lastcode = *b++;  n--;      /*   get first character from input, */
  289.     FirstCh = 0;                /*   and reset the first char flag. */
  290.   }
  291.   while (NextFree == -1 && n)
  292.   {
  293.     /* Ok, lets clear the code table (adaptive reset) */
  294.     PutCode(lastcode);
  295.     PutCode(SPECIAL);
  296.     PutCode(CLEARCODE);
  297.     Clear_Table();
  298.     Table_Add(lastcode, s = *b++);  n--;
  299.     lastcode = s;
  300.   }
  301.   while (n)
  302.   {
  303.     s = *b++;  n--;
  304.     f = CodeTable[lastcode].Child;
  305.     while (f != -1 && CodeTable[f].Suffix != (uch)s)
  306.       f = CodeTable[f].Sibling;
  307.     if (f != -1)
  308.       /* If lastcode:s pair is found in the code table, then ... */
  309.       /* ... set lastcode to the entry where the pair is located */
  310.       lastcode = f;
  311.     else
  312.     {
  313.       /* Not in table */
  314.       PutCode(lastcode);        /* Write current lastcode */
  315.       Table_Add(lastcode, s);   /* Attempt to add to code table */
  316.       lastcode = s;             /* Reset lastcode for new char */
  317.       if (NextFree > MaxCode && CodeSize < MAXBITS)
  318.       {
  319.         /* Time to increase the code size and change the max. code */
  320.         PutCode(SPECIAL);
  321.         PutCode(INCSIZE);
  322.         CodeSize++;
  323.         MaxCode = (1 << CodeSize) - 1;
  324.       }
  325.       while (NextFree == -1 && n)
  326.       {
  327.         /* Ok, lets clear the code table (adaptive reset) */
  328.         PutCode(lastcode);
  329.         PutCode(SPECIAL);
  330.         PutCode(CLEARCODE);
  331.         Clear_Table();
  332.         Table_Add(lastcode, s = *b++);  n--;
  333.         lastcode = s;
  334.       }
  335.     }
  336.   }
  337.   return ZE_OK;
  338. }
  339.  
  340.  
  341. int shr_size(s)
  342. ulg *s;                 /* return value: size of shrunk data */
  343. /* End shrink and return size of shrunk data in *s.  Return an error code in
  344.    the ZE_ class. */
  345. {
  346.   PutCode(lastcode);            /* Write last prefix code */
  347.   PutCode(-1);                  /* Tell putcode to flush remaining bits */
  348.   Destroy_Data_Structures();
  349.   *s = count;
  350.   return tflush(tempf) || terror(tempf) ? ZE_TEMP : ZE_OK;
  351. }
  352.  
  353.  
  354. int shr_p2(f)
  355. FILE *f;                /* file to write shrunk data to */
  356. /* Copy shrunk data from temporary file to zip file *f.  Return an error
  357.    code in the ZE_ class. */
  358. {
  359.   char *b;              /* malloc'ed buffer for copying */
  360.   extent k;             /* holds result of fread */
  361.  
  362.   if ((b = malloc(BSZ)) == NULL)
  363.     return ZE_MEM;
  364.   trewind(tempf);
  365.   while ((k = tread(b, 1, BSZ, tempf)) > 0)
  366.     if (zfwrite(b, 1, k, f) != k)
  367.     {
  368.       free((voidp *)b);
  369.       return ZE_TEMP;
  370.     }
  371.   free((voidp *)b);
  372.   if (terror(tempf))
  373.     return ZE_TEMP;
  374.   tclose(tempf);
  375.   tempf = NULL;
  376.   return ZE_OK;
  377. }
  378.  
  379.  
  380. int shr_clear()
  381. /* Terminate shrink procedure (at any time).  Return an error code in
  382.    the ZE_ class (always ZE_OK). */
  383. {
  384.   Destroy_Data_Structures();
  385.   if (tempf != NULL)
  386.   {
  387.     tclose(tempf);
  388.     tempf =  NULL;
  389.   }
  390.   return ZE_OK;
  391. }
  392.