home *** CD-ROM | disk | FTP | other *** search
/ High Voltage Shareware / high1.zip / high1 / DIR3 / KA9Q212.ZIP / LZW.C < prev    next >
C/C++ Source or Header  |  1993-07-16  |  15KB  |  559 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV. Permission granted for
  6.  * non-commercial distribution only.
  7.  */
  8.  
  9. /****************************************************************************
  10. *    $Id: lzw.c 1.2 93/07/16 11:46:21 ROOT_DOS Exp $
  11. *    13 Jul 93    1.2        GT    Conditional on LZW.                                *
  12. ****************************************************************************/
  13.  
  14. #include    "config.h"
  15. #if    LZW
  16. #include "global.h"
  17. #include "mbuf.h"
  18. #include "proc.h"
  19. #include "lzw.h"
  20. #include "usock.h"
  21.  
  22. static void fastencode __ARGS((struct usock *up,char data));
  23. static int16 zhash __ARGS((int32 code,char data));
  24. static void morebits __ARGS((struct lzw *lzw));
  25. static void cleartbl __ARGS((struct lzw *lzw));
  26. static void addtobuffer __ARGS((struct usock *up,int32 code));
  27. static void addchar __ARGS((char data,struct lzw *lzw));
  28. static void getstring __ARGS((int32 code,struct lzw *lzw));
  29. static char firstchar __ARGS((int32 code,struct lzw *lzw));
  30. static void decodetbl __ARGS((int32 code,struct lzw *lzw));
  31. static int32 nextcode __ARGS((struct usock *up));
  32.  
  33. /* Initialize a socket for compression. Bits specifies the maximum number
  34.  * of bits per codeword. The input and output code tables might grow to
  35.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  36.  * recommendation for the decoding, the actual number of bits may be
  37.  * larger, but not never more than 16.
  38.  */
  39. void
  40. lzwinit(s,bits,mode)
  41. int s;        /* socket to operate on */
  42. int bits;    /* maximum number of bits per codeword */
  43. int mode;    /* compression mode, LZWCOMPACT or LZWFAST */
  44. {
  45.     struct usock *up;
  46.     if((up = itop(s)) == NULLUSOCK)
  47.         return;
  48.     up->zout = (struct lzw *) callocw(1,sizeof(struct lzw));
  49.     up->zin = (struct lzw *) callocw(1,sizeof(struct lzw));
  50.     up->zout->codebits = LZWBITS;
  51.     if(bits < LZWBITS)
  52.         up->zout->maxbits = LZWBITS;
  53.     if(bits > 16 || bits == 0)
  54.         up->zout->maxbits = 16;
  55.     if(bits >= LZWBITS && bits <= 16)
  56.         up->zout->maxbits = bits;
  57.     up->zout->nextbit = 0;
  58.     up->zout->prefix = -1;
  59.     up->zout->version = -1;
  60.     up->zout->code = -1;
  61.     up->zout->mode = mode;
  62.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  63.     up->zin->codebits = LZWBITS;
  64.     up->zin->maxbits = -1;
  65.     up->zin->nextbit = 0;
  66.     up->zin->prefix = -1;
  67.     up->zin->version = -1;
  68.     up->zin->code = -1;
  69.     up->zin->next = ZFLUSH + 1;
  70.     up->zin->mode = LZWCOMPACT;
  71.     up->zin->buf = NULLBUF;
  72. }
  73.  
  74. void
  75. lzwfree(up)
  76. struct usock *up;
  77. {
  78.     if(up->zout != NULLLZW) {
  79.         cleartbl(up->zout);
  80.         free((char *)up->zout);
  81.         up->zout = NULLLZW;
  82.     }
  83.     up->zout = NULLLZW;
  84.     if(up->zin != NULLLZW) {
  85.         cleartbl(up->zin);
  86.         free_q(&up->zin->buf);
  87.         free((char *)up->zin);
  88.         up->zin = NULLLZW;
  89.     }
  90. }
  91. /* LZW encoding routine.
  92.  * See if the string specified by code + data is in the string table. If so,
  93.  * set prefix equal to the code of that string. Otherwise insert code + data
  94.  * in the string and set prefix equal to data.
  95.  */
  96. void
  97. lzwencode(s,data)
  98. int s;
  99. char data;
  100. {
  101.     struct usock *up;
  102.     register struct lzw *lzw;
  103.     int32 code, pagelim;
  104.     register unsigned int i,j;
  105.  
  106.     if((up = itop(s)) == NULLUSOCK)
  107.         return;
  108.     lzw = up->zout;
  109.     code = up->zout->prefix;
  110.     /* the first byte sent will be the version number */
  111.     if(lzw->version == -1) {
  112.         lzw->version = ZVERSION;
  113.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  114.         /* then send our recommended maximum number of codebits */
  115.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  116.     }
  117.     lzw->cnt++;
  118.     if(code == -1) {
  119.         lzw->prefix = (int32) uchar(data);
  120.         return;
  121.     }
  122.     if(lzw->mode == LZWFAST) {
  123.         fastencode(up,data);
  124.         return;
  125.     }
  126.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  127.     if(code <= ZFLUSH)
  128.         i = j = 0;
  129.     else {
  130.         i = (code - ZFLUSH) / LZWBLK;
  131.         j = (code - ZFLUSH) % LZWBLK;
  132.     }
  133.     if(lzw->tu.tbl == (struct zentry **)0)
  134.         lzw->tu.tbl = (struct zentry **) callocw(1,
  135.             sizeof(struct zentry *) * pagelim);
  136.     for(;;) {
  137.         if(itop(s) == NULLUSOCK) /* the connection has been closed */
  138.             return;
  139.         if(up->zout == NULLLZW) /* ...or is about to be closed */
  140.             return;
  141.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  142.             lzw->tu.tbl[i] = (struct zentry *)
  143.                 mallocw(LZWBLK * sizeof(struct zentry));
  144.             memset((char *)lzw->tu.tbl[i], 0xff,
  145.                 LZWBLK * sizeof(struct zentry));
  146.         }
  147.         while(j < LZWBLK) {
  148.             if(lzw->tu.tbl[i][j].data == data &&
  149.                 lzw->tu.tbl[i][j].code == (int16) code) {
  150.                 lzw->prefix = (int32)(i * LZWBLK + j +
  151.                               ZFLUSH + 1);
  152.                 return;
  153.             }
  154.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  155.                 lzw->tu.tbl[i][j].code = (int16) code;
  156.                 lzw->tu.tbl[i][j].data = data;
  157.                 addtobuffer(up,code);
  158.                 lzw->prefix = (int32) uchar(data);
  159.                 lzw->next++;
  160.                 if(lzw->next ==    (int32) 1 << lzw->codebits)
  161.                     /* the current table is now full */
  162.                     morebits(lzw);
  163.                 if(lzw->next + 1 == (int32)
  164.                         1 << lzw->maxbits) {
  165.                 /* The last codeword has been reached.
  166.                  * (Or last - 1.) Signal this and start all
  167.                  * over again.
  168.                  */
  169.                     addtobuffer(up,lzw->prefix);
  170.                        if(lzw->next + 1 == (int32)
  171.                             1 << lzw->codebits)
  172.                         morebits(lzw);
  173.                     addtobuffer(up,ZCC);
  174.                     cleartbl(lzw);
  175.                 }
  176.                 return;
  177.             }
  178.             ++j;
  179.         }
  180.         pwait(NULL);
  181.         ++i;
  182.         j = 0;
  183.     }
  184. }
  185.  
  186. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  187.  * bytes.
  188.  */
  189. static void
  190. fastencode(up,data)
  191. struct usock *up;
  192. char data;
  193. {
  194.     register struct zfast *z;
  195.     register struct mbuf *bp;
  196.     register struct lzw *lzw = up->zout;
  197.     int32 code = up->zout->prefix;
  198.     register int16 cnt, h;
  199.  
  200.     if(lzw->tu.bpp == NULLBUFP)
  201.         lzw->tu.bpp = (struct mbuf **) callocw(1,
  202.             sizeof(struct mbuf *) * ZHASH);
  203.     h = zhash(code,data);
  204.     if(lzw->tu.bpp[h] == NULLBUF)
  205.         lzw->tu.bpp[h] = ambufw(LZWBLK);
  206.     bp = lzw->tu.bpp[h];
  207.     cnt = bp->cnt / sizeof(struct zfast);
  208.     z = (struct zfast *) bp->data;
  209.     while(cnt > 0) {
  210.         if(z->data == data && z->code == (int16) code) {
  211.             lzw->prefix = (int32) z->owncode;
  212.             return;
  213.         }
  214.         z++;
  215.         if(--cnt == 0) {
  216.             if(bp->next == NULLBUF)
  217.                 break;
  218.             bp = bp->next;
  219.             cnt = bp->cnt / sizeof(struct zfast);
  220.             z = (struct zfast *) bp->data;
  221.         }
  222.     }
  223.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  224.         z = (struct zfast *) &bp->data[bp->cnt];
  225.         bp->cnt += sizeof(struct zfast);
  226.     }
  227.     else {
  228.         bp->next = ambufw(LZWBLK);
  229.         z = (struct zfast *) bp->next->data;
  230.         bp->next->cnt = sizeof(struct zfast);
  231.     }
  232.     z->code = (int16) code;
  233.     z->data = data;
  234.     z->owncode = (int16) lzw->next++;
  235.     addtobuffer(up,code);
  236.     lzw->prefix = (int32) uchar(data);
  237.     if(lzw->next == (int32) 1 << lzw->codebits) {
  238.         /* Increase the number of bits per codeword */
  239.         morebits(lzw);
  240.     }
  241.     if(lzw->next + 1 == (int32) 1 << lzw->maxbits) {
  242.         /* The last codeword has been reached. (Or last - 1.)
  243.          * Signal this and start all over again.
  244.          */
  245.         addtobuffer(up,lzw->prefix);
  246.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  247.             morebits(lzw);
  248.         addtobuffer(up,ZCC);
  249.         cleartbl(lzw);
  250.     }
  251.     pwait(NULL);
  252. }
  253.  
  254. static int16
  255. zhash(code,data)
  256. int32 code;
  257. char data;
  258. {
  259.     register int16 h;
  260.     h = lobyte(code);
  261.     h ^= hibyte(code);
  262.     h ^= data;
  263.     return h % ZHASH;
  264. }
  265.  
  266. /* increase the number of significant bits in the codewords, and increase
  267.  * the size of the string table accordingly.
  268.  */
  269. static void
  270. morebits(lzw)
  271. struct lzw *lzw;
  272. {
  273.     struct zentry **newt;
  274.     int32 pagelim, oldp;
  275.     oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  276.     lzw->codebits++;
  277.     if(lzw->mode == LZWFAST)
  278.         return;
  279.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  280.     newt = (struct zentry **) callocw(1,sizeof(struct zentry *)*pagelim);
  281.     memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * oldp);
  282.     free((char *)lzw->tu.tbl);
  283.     lzw->tu.tbl = newt;
  284. }
  285.  
  286. static void
  287. cleartbl(lzw)
  288. struct lzw *lzw;
  289. {
  290.     int32 pagelim,i;
  291.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  292.     lzw->codebits = LZWBITS;
  293.     lzw->prefix = -1;
  294.     lzw->next = ZFLUSH + 1;
  295.     if(lzw->tu.p == NULL)
  296.         return;
  297.     if(lzw->mode == LZWCOMPACT)
  298.         for(i=0; i < pagelim; ++i)
  299.             free((char *)lzw->tu.tbl[i]);
  300.     else
  301.         for(i=0; i < ZHASH; ++i)
  302.             free_p(lzw->tu.bpp[i]);
  303.     free((char *)lzw->tu.p);
  304.     lzw->tu.p = NULL;
  305. }
  306. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  307.  * code stream should be written first. The codeword ZFLUSH is used to
  308.  * pad the buffer to a byte boundary when the buffer will be flushed.
  309.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  310.  */
  311. static void
  312. addtobuffer(up,code)
  313. struct usock *up;
  314. int32 code;
  315. {
  316.     if(up->zout->code != -1) {
  317.         /* Insert remaining bits of ZFLUSH codeword */
  318.         up->obuf->data[up->obuf->cnt] =
  319.              up->zout->code >> up->zout->flushbit;
  320.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  321.             up->zout->nextbit = (up->zout->codebits -
  322.                         up->zout->flushbit) % 8;
  323.             if(up->zout->nextbit == 0)
  324.                 ++up->obuf->cnt;
  325.             up->zout->code = -1;
  326.         }
  327.         else {
  328.             /* not done yet */
  329.             ++up->obuf->cnt;
  330.             up->zout->flushbit += 8;
  331.             addtobuffer(up,code);
  332.             return;
  333.         }
  334.     }
  335.     /* normal codewords are treated here */
  336.     if(up->zout->nextbit == 0) {
  337.         /* we are at a byte boundary */
  338.         if(code == ZFLUSH) {
  339.             up->zout->flushbit = 0;
  340.             up->zout->code = ZFLUSH;
  341.             return;
  342.         }
  343.         up->obuf->data[up->obuf->cnt++] = (char) code;
  344.     }
  345.     else
  346.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  347.     if(code == ZFLUSH) {
  348.         /* interrupt here and save the rest of the ZFLUSH
  349.          * codeword for later.
  350.          */
  351.         up->zout->flushbit = 8 - up->zout->nextbit;
  352.         up->zout->code = ZFLUSH;
  353.         return;
  354.     }
  355.     up->obuf->data[up->obuf->cnt] = code >> 8 - up->zout->nextbit;
  356.     /* start on a third byte if necessary */
  357.     if(16 - up->zout->nextbit < up->zout->codebits)
  358.         up->obuf->data[++up->obuf->cnt] =
  359.                     code >> 16 - up->zout->nextbit;
  360.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  361.     if(up->zout->nextbit == 0)
  362.         ++up->obuf->cnt;
  363. }
  364.  
  365. void
  366. lzwflush(up)
  367. struct usock *up;
  368. {
  369.     /* interrupt the encoding process and send the prefix codeword */
  370.     if(up->zout->prefix != -1) {
  371.         addtobuffer(up,up->zout->prefix);
  372.            if(up->zout->next + 1 == (int32) 1 << up->zout->codebits)
  373.             morebits(up->zout);
  374.         up->zout->prefix = -1;
  375.     }
  376.     /* signal this by sending the ZFLUSH codeword */
  377.     addtobuffer(up,ZFLUSH);
  378. }
  379.  
  380. int
  381. lzwdecode(up)
  382. struct usock *up;
  383. {
  384.     int32 code,data;
  385.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf))
  386.        == -1)
  387.         return -1;
  388.     if(up->zin->maxbits == -1) {
  389.         /* receive a recommended value for the maximum no of bits */
  390.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1)
  391.             return -1;
  392.         if(up->zout->maxbits > up->zin->maxbits) {
  393.             if(up->zout->codebits > up->zin->maxbits) {
  394.                 /* We are already using more bits than our
  395.                  * peer want us to, so clear the encoding
  396.                  * table immediately.
  397.                  */
  398.                 addtobuffer(up,up->zout->prefix);
  399.                 if(up->zout->next + 1 == (int32)
  400.                    1 << up->zout->codebits)
  401.                     morebits(up->zout);
  402.                 addtobuffer(up,ZCC);
  403.                 cleartbl(up->zout);
  404.             }
  405.             up->zout->maxbits = up->zin->maxbits;
  406.         }
  407.     }
  408.     for(;;) {
  409.         if((data = PULLCHAR(&up->zin->buf)) != -1)
  410.             return (int) data;
  411.         if((code = nextcode(up)) == -1)
  412.             return -1;
  413.         decodetbl(code,up->zin);
  414.         up->zin->cnt += len_p(up->zin->buf);
  415.     }
  416. }
  417.  
  418. static void
  419. addchar(data,lzw)
  420. char data;
  421. struct lzw *lzw;
  422. {
  423.     lzw->buf = pushdown(lzw->buf,1);
  424.     *lzw->buf->data = data;
  425. }
  426. static void
  427. getstring(code,lzw)
  428. int32 code;
  429. struct lzw *lzw;
  430. {
  431.     int i,j;
  432.     for(;;) {
  433.         if(code < ZFLUSH) {
  434.             addchar(uchar(code),lzw);
  435.             return;
  436.         }
  437.         i = (code - ZFLUSH - 1) / LZWBLK;
  438.         j = (code - ZFLUSH - 1) % LZWBLK;
  439.         addchar(lzw->tu.tbl[i][j].data,lzw);
  440.         code = (int32) lzw->tu.tbl[i][j].code;
  441.     }
  442. }
  443. static char
  444. firstchar(code,lzw)
  445. int32 code;
  446. struct lzw *lzw;
  447. {
  448.     int i,j;
  449.     for(;;) {
  450.         if(code < ZFLUSH)
  451.             return uchar(code);
  452.         i = (code - ZFLUSH - 1) / LZWBLK;
  453.         j = (code - ZFLUSH - 1) % LZWBLK;
  454.         code = (int32) lzw->tu.tbl[i][j].code;
  455.     }
  456. }
  457. static void
  458. decodetbl(code,lzw)
  459. int32 code;
  460. struct lzw *lzw;
  461. {
  462.     register unsigned int i,j;
  463.     int32 pagelim;
  464.  
  465.     if(code > lzw->next) {
  466.         printf("LZW protocol error, process %s\n",Curproc->name);
  467.         return;
  468.     }
  469.     if(lzw->buf == NULLBUF) {
  470.         lzw->buf = ambufw(512);
  471.         /* allow us to use pushdown() later */
  472.         lzw->buf->data += lzw->buf->size;
  473.     }
  474.     if(lzw->prefix == -1) {
  475.         getstring(code,lzw);
  476.         lzw->prefix = code;
  477.         return;
  478.     }
  479.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  480.     if(lzw->tu.tbl == (struct zentry **)0)
  481.         lzw->tu.tbl = (struct zentry **) callocw(1,
  482.                 sizeof(struct zentry *) * pagelim);
  483.     if(code < ZFLUSH)
  484.         goto intable;
  485.     i = (code - ZFLUSH - 1) / LZWBLK;
  486.     j = (code - ZFLUSH - 1) % LZWBLK;
  487.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  488.         lzw->tu.tbl[i] = (struct zentry *)
  489.                 mallocw(LZWBLK * sizeof(struct zentry));
  490.         memset((char *)lzw->tu.tbl[i], 0xff,
  491.                 LZWBLK * sizeof(struct zentry));
  492.     }
  493.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  494.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  495.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  496.         getstring(code,lzw);
  497.         lzw->next = code + 1;
  498.         lzw->prefix = code;
  499.         if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  500.             morebits(lzw);
  501.         return;
  502.     }
  503. intable:
  504.     getstring(code,lzw);
  505.     i = (lzw->next - ZFLUSH - 1) / LZWBLK;
  506.     j = (lzw->next - ZFLUSH - 1) % LZWBLK;
  507.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  508.         lzw->tu.tbl[i] = (struct zentry *)
  509.                 mallocw(LZWBLK * sizeof(struct zentry));
  510.         memset((char *)lzw->tu.tbl[i], 0xff,
  511.                 LZWBLK * sizeof(struct zentry));
  512.     }
  513.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  514.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  515.     lzw->next++;
  516.     lzw->prefix = code;
  517.     if(lzw->next + 1 == (int32) 1 << lzw->codebits)
  518.         morebits(lzw);
  519. }
  520.  
  521. /* extract the next codeword from the input stream */
  522. static int32
  523. nextcode(up)
  524. struct usock *up;
  525. {
  526.     int32 code;
  527.     if(up->zin->code == -1) {    /* read the first character */
  528.         if((code = PULLCHAR(&up->ibuf)) == -1)
  529.             return -1;
  530.         up->zin->code = code >> up->zin->nextbit;
  531.     }
  532.     if(up->ibuf == NULLBUF)        /* next byte is not available yet */
  533.         return -1;
  534.     /* continue assembling the codeword */
  535.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  536.             8 - up->zin->nextbit) & (((int32) 1 <<
  537.             up->zin->codebits) - 1);
  538.     if(16 - up->zin->nextbit < up->zin->codebits) {
  539.         (void) PULLCHAR(&up->ibuf);
  540.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  541.         return nextcode(up);
  542.     }
  543.     code = up->zin->code;
  544.     up->zin->code = -1;
  545.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  546.     if(up->zin->nextbit == 0)
  547.         (void) PULLCHAR(&up->ibuf);
  548.     if(code == ZCC) {
  549.         cleartbl(up->zin);
  550.         return nextcode(up);
  551.     }
  552.     if(code == ZFLUSH) {
  553.         up->zin->prefix = -1;
  554.         return nextcode(up);
  555.     }
  556.     return code;
  557. }
  558. #endif    /* LZW */
  559.