home *** CD-ROM | disk | FTP | other *** search
/ Piper's Pit BBS/FTP: ibm 0040 - 0049 / ibm0040-0049 / ibm0040.tar / ibm0040 / IMGPROC.ZIP / C6TIFF.ZIP / LZW.C < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-30  |  16.0 KB  |  589 lines
  1. /*
  2. Copyright (c) 1988 by Sam Leffler.
  3. All rights reserved.
  4. Substantially modified by Craig A. Lindley Dec. 1989.
  5.  
  6. This file is provided for unrestricted use provided that this
  7. legend is included on all tape media and as a part of the
  8. software program in whole or part.  Users may copy, modify or
  9. distribute this file at will.
  10.  
  11. TIFF Library.
  12. Rev 5.0 Lempel-Ziv & Welch Compression Support
  13.  
  14. This code is derived from the compress program whose code is
  15. derived from software contributed to Berkeley by James A. Woods,
  16. derived from original work by Spencer Thomas and Joseph Orost.
  17.  
  18. The original Berkeley copyright notice appears below in its entirety.
  19. */
  20.  
  21. #include <alloc.h>
  22. #include <mem.h>
  23. #include "tiffio.h"
  24.  
  25.  
  26. #define MAXCODE(n)      ((1 << (n)) - 1)
  27. /*
  28.  * The TIFF spec specifies that encoded bit strings range
  29.  * from 9 to 12 bits.  This is somewhat unfortunate in that
  30.  * experience indicates full color RGB pictures often need
  31.  * ~14 bits for reasonable compression.
  32.  */
  33. #define BITS_MIN        9               /* start with 9 bits */
  34. #define BITS_MAX        12              /* max of 12 bit strings */
  35.  
  36. /* predefined codes */
  37. #define CODE_CLEAR      256             /* code to clear string table */
  38. #define CODE_EOI        257             /* end-of-information code */
  39. #define CODE_FIRST      258             /* first free code entry */
  40. #define CODE_MAX        MAXCODE(BITS_MAX)
  41.  
  42. #define HSIZE           5003            /* 80% occupancy */
  43. #define HSHIFT          (8-(16-12))
  44.  
  45. /*
  46. Decoding-specific state.
  47. */
  48. struct decode
  49. {
  50.    unsigned prefixtab[HSIZE];       /* prefix(code) */
  51.    char  suffixtab[CODE_MAX+1];     /* suffix(code) */
  52.    char  stack[HSIZE-(CODE_MAX+1)];
  53.    char  *stackp;                   /* stack pointer */
  54.    short firstchar;                 /* of string associated w/ last code */
  55. };
  56.  
  57. #define CHECK_GAP       10000       /* enc_ratio check interval */
  58.  
  59. /*
  60. Encoding-specific state.
  61. */
  62. struct encode
  63. {
  64.    long  checkpoint;             /* point at which to clear table */
  65.    long  ratio;                  /* current compression ratio */
  66.    unsigned long incount;        /* (input) data bytes encoded */
  67.    unsigned long outcount;       /* encoded (output) bytes */
  68.    long  htab[HSIZE];            /* hash table */
  69.    short codetab[HSIZE];         /* code table */
  70. };
  71.  
  72. /*
  73. State block for each open TIFF
  74. file using LZW compression.
  75. */
  76.  
  77. #define FLAG_CODEDELTA  0x1             /* increase code string size */
  78. #define FLAG_RESTART    0x2             /* restart interrupted decode */
  79.  
  80. typedef struct
  81. {
  82.    short    lzw_oldcode;            /* last code encountered */
  83.    unsigned lzw_flags;
  84.    unsigned lzw_nbits;              /* number of bits/code */
  85.    unsigned lzw_maxcode;            /* maximum code for lzw_nbits */
  86.    long     lzw_bitoff;             /* bit offset into data */
  87.    long     lzw_bitsize;            /* size of strip in bits */
  88.    unsigned lzw_free_ent;           /* next free entry in hash table */
  89.    union
  90.    {
  91.       struct  decode dec;
  92.       struct  encode enc;
  93.    } u;
  94. } LZWState;
  95.  
  96. #define dec_prefix      u.dec.prefixtab
  97. #define dec_suffix      u.dec.suffixtab
  98. #define dec_stack       u.dec.stack
  99. #define dec_stackp      u.dec.stackp
  100. #define dec_firstchar   u.dec.firstchar
  101.  
  102. #define enc_checkpoint  u.enc.checkpoint
  103. #define enc_ratio       u.enc.ratio
  104. #define enc_incount     u.enc.incount
  105. #define enc_outcount    u.enc.outcount
  106. #define enc_htab        u.enc.htab
  107. #define enc_codetab     u.enc.codetab
  108.  
  109. static unsigned BitCount;
  110. static unsigned ByteOffset;
  111. static unsigned long BitBuffer;
  112. static unsigned FinalByte;
  113. /*
  114. LZW Decoder.
  115. */
  116.  
  117. /*
  118. Setup state for decoding a strip.
  119. */
  120. static
  121. CompletionCode LZWPreDecode(TIFF *tif)
  122. {
  123.    register LZWState *sp = (LZWState *)tif->tif_data;
  124.    register short code;
  125.  
  126.    if (sp == NULL)
  127.    {
  128.       tif->tif_data = malloc((unsigned) sizeof (LZWState));
  129.       if (tif->tif_data == NULL)
  130.       {
  131.      TIFFError("LZWPreDecode","No space for LZW state block");
  132.      return (FALSE);
  133.       }
  134.       sp = (LZWState *)tif->tif_data;
  135.    }
  136.    sp->lzw_flags = 0;
  137.    sp->lzw_nbits = BITS_MIN;
  138.    sp->lzw_maxcode = MAXCODE(BITS_MIN);
  139.  
  140.    /* Pre-load the table */
  141.    for (code = 255; code >= 0; code--)
  142.       sp->dec_suffix[code] = (char)code;
  143.    sp->lzw_free_ent = CODE_FIRST;
  144.    sp->lzw_bitoff = 0L;
  145.    /* calculate data size in bits */
  146.    sp->lzw_bitsize = tif->tif_rawdatasize;
  147.    sp->lzw_bitsize = (sp->lzw_bitsize << 3L) - (BITS_MAX-1);
  148.    sp->dec_stackp = sp->dec_stack;
  149.    sp->lzw_oldcode = -1;
  150.    sp->dec_firstchar = -1;
  151.    BitCount = 0;    /* modified for GetNextCode CAL 12/28/89 */
  152.    BitBuffer = 0L;
  153.    ByteOffset = 0;
  154.    return (TRUE);
  155. }
  156.  
  157. /*
  158. Get the next code from the raw data buffer.
  159. */
  160. static
  161. unsigned GetNextCode(TIFF *tif)
  162. {
  163.    LZWState *sp = (LZWState *)tif->tif_data;
  164.    register unsigned code;
  165.    char *bp;
  166.  
  167.    /*
  168.    This check shouldn't be necessary because each
  169.    strip is suppose to be terminated with CODE_EOI.
  170.    At worst it's a substitute for the CODE_EOI that's
  171.    supposed to be there (see calculation of lzw_bitsize
  172.    in LZWPreDecode()).
  173.    */
  174.    if (sp->lzw_bitoff > sp->lzw_bitsize)
  175.       return (CODE_EOI);
  176.    /*
  177.    If the next entry is too big for the
  178.    current code size, then increase the
  179.    size up to the maximum possible.
  180.    */
  181.    if (sp->lzw_free_ent >= sp->lzw_maxcode) /* bug fixed CAL 12/28/89 */
  182.    {
  183.       sp->lzw_nbits++;
  184.       if (sp->lzw_nbits > BITS_MAX)
  185.      sp->lzw_nbits = BITS_MAX;
  186.       sp->lzw_maxcode = MAXCODE(sp->lzw_nbits);
  187.    }
  188.    if (sp->lzw_flags & FLAG_CODEDELTA)
  189.    {
  190.       sp->lzw_maxcode = MAXCODE(sp->lzw_nbits = BITS_MIN);
  191.       sp->lzw_flags &= ~FLAG_CODEDELTA;
  192.    }
  193.  
  194.    /* Code simplified CAL 12/28/89 */
  195.    /* Get to the first byte */
  196.    bp = (char *) (tif->tif_rawdata + ByteOffset);
  197.    while (BitCount <= 24)
  198.    {
  199.       BitBuffer |= ((unsigned long) *bp++) << (24 - BitCount);
  200.       BitCount += 8;
  201.       ByteOffset += 1;
  202.    }
  203.    code = (unsigned)(BitBuffer >> (32L - sp->lzw_nbits));
  204.    BitBuffer <<= ((unsigned long) sp->lzw_nbits);
  205.    BitCount -= sp->lzw_nbits;
  206.    sp->lzw_bitoff += sp->lzw_nbits;
  207.    return (code);
  208. }
  209.  
  210. /*
  211. Decode the next scanline.
  212. */
  213. static
  214. CompletionCode LZWDecode(TIFF *tif, char *op, long occ)
  215. {
  216.    register LZWState *sp = (LZWState *)tif->tif_data;
  217.    register unsigned code;
  218.    register char *stackp;
  219.    unsigned firstchar, oldcode, incode;
  220.  
  221.    stackp = sp->dec_stackp;
  222.    /* Restart interrupted unstacking operations */
  223.    if (sp->lzw_flags & FLAG_RESTART)
  224.    {
  225.       do
  226.       {
  227.      if (--occ < 0)
  228.      {
  229.         /* end of scanline */
  230.         sp->dec_stackp = stackp;
  231.         return (TRUE);
  232.      }
  233.      *op++ = *--stackp;
  234.       } while (stackp > sp->dec_stack);
  235.       sp->lzw_flags &= ~FLAG_RESTART;
  236.    }
  237.    oldcode = sp->lzw_oldcode;
  238.    firstchar = sp->dec_firstchar;
  239.    while (occ > 0 && (code = GetNextCode(tif)) != CODE_EOI)
  240.    {
  241.       if (code == CODE_CLEAR)
  242.       {
  243.      memset(sp->dec_prefix,0,sizeof (sp->dec_prefix));
  244.      sp->lzw_flags |= FLAG_CODEDELTA;
  245.      sp->lzw_free_ent = CODE_FIRST;
  246.      if ((code = GetNextCode(tif)) == CODE_EOI)
  247.         break;
  248.      *op++ = code, occ--;
  249.      oldcode = firstchar = code;
  250.      continue;
  251.       }
  252.       incode = code;
  253.       /*
  254.       When a code is not in the table we use (as spec'd):
  255.       StringFromCode(oldcode) +
  256.       FirstChar(StringFromCode(oldcode))
  257.       */
  258.       if (code >= sp->lzw_free_ent)
  259.       {
  260.      /* code not in table */
  261.      *stackp++ = firstchar;
  262.      code = oldcode;
  263.       }
  264.       /* Generate output string (first in reverse) */
  265.       for (; code >= 256; code = sp->dec_prefix[code])
  266.      *stackp++ = sp->dec_suffix[code];
  267.       *stackp++ = firstchar = sp->dec_suffix[code];
  268.       do
  269.       {
  270.      if (--occ < 0)
  271.      {
  272.         /* end of scanline */
  273.         sp->lzw_flags |= FLAG_RESTART;
  274.         break;
  275.      }
  276.      *op++ = *--stackp;
  277.       } while (stackp > sp->dec_stack);
  278.       /* Add the new entry to the code table */
  279.       if ((code = sp->lzw_free_ent) < CODE_MAX)
  280.       {
  281.      sp->dec_prefix[code] = oldcode;
  282.      sp->dec_suffix[code] = firstchar;
  283.      sp->lzw_free_ent++;
  284.       }
  285.       oldcode = incode;
  286.    }
  287.    sp->dec_stackp = stackp;
  288.    sp->lzw_oldcode = oldcode;
  289.    sp->dec_firstchar = firstchar;
  290.    if (occ > 0)
  291.    {
  292.       TIFFError(tif->tif_name,
  293.            "LZWDecode: Not enough data for scanline %d", tif->tif_row);
  294.       return (FALSE);
  295.    }
  296.    return (TRUE);
  297. }
  298.  
  299. /*
  300. LZW Encoding.
  301. */
  302. /*
  303. Reset code table.
  304. */
  305. static
  306. void cl_hash(LZWState *sp)
  307. {
  308.    register long *htab_p = sp->enc_htab+HSIZE;
  309.    register long i, m1 = -1;
  310.  
  311.    i = HSIZE - 16;
  312.    do
  313.    {
  314.       *(htab_p-16) = m1;
  315.       *(htab_p-15) = m1;
  316.       *(htab_p-14) = m1;
  317.       *(htab_p-13) = m1;
  318.       *(htab_p-12) = m1;
  319.       *(htab_p-11) = m1;
  320.       *(htab_p-10) = m1;
  321.       *(htab_p-9) = m1;
  322.       *(htab_p-8) = m1;
  323.       *(htab_p-7) = m1;
  324.       *(htab_p-6) = m1;
  325.       *(htab_p-5) = m1;
  326.       *(htab_p-4) = m1;
  327.       *(htab_p-3) = m1;
  328.       *(htab_p-2) = m1;
  329.       *(htab_p-1) = m1;
  330.       htab_p -= 16;
  331.    } while ((i -= 16) >= 0);
  332.    for (i += 16; i > 0; i--)
  333.       *--htab_p = m1;
  334. }
  335.  
  336. /*
  337. Reset encoding state at the start of a strip.
  338. */
  339. static
  340. CompletionCode LZWPreEncode(TIFF *tif)
  341. {
  342.    register LZWState *sp = (LZWState *)tif->tif_data;
  343.  
  344.    if (sp == NULL)
  345.    {
  346.       tif->tif_data = malloc(sizeof (LZWState));
  347.       if (tif->tif_data == NULL)
  348.       {
  349.      TIFFError("LZWPreEncode","No space for LZW state block");
  350.      return (FALSE);
  351.       }
  352.       sp = (LZWState *)tif->tif_data;
  353.    }
  354.    sp->lzw_flags = 0;
  355.    sp->enc_ratio = 0;
  356.    sp->enc_checkpoint = CHECK_GAP;
  357.    sp->lzw_maxcode = MAXCODE(sp->lzw_nbits = BITS_MIN);
  358.    sp->lzw_free_ent = CODE_FIRST;
  359.    sp->lzw_bitoff = 0;
  360.    sp->lzw_bitsize = (tif->tif_rawdatasize << 3) - (BITS_MAX-1);
  361.    cl_hash(sp);            /* clear hash table */
  362.    sp->lzw_oldcode = -1;   /* generates CODE_CLEAR in LZWEncode */
  363.    BitCount = 0;           /* modified for PutNextCode CAL 12/28/89 */
  364.    BitBuffer = 0L;
  365.    ByteOffset = 0;
  366.    FinalByte = FALSE;
  367.    return (TRUE);
  368. }
  369.  
  370. static
  371. void PutNextCode(TIFF *tif, unsigned code)
  372. {
  373.    register LZWState *sp = (LZWState *)tif->tif_data;
  374.    register char *bp;
  375.  
  376.    bp = (char *)(tif->tif_rawdata + ByteOffset);
  377.  
  378.    BitBuffer |= (unsigned long) code << (32L-sp->lzw_nbits-BitCount);
  379.    BitCount += sp->lzw_nbits;
  380.    while (BitCount >= 8)
  381.    {
  382.       *bp++ = BitBuffer >> 24;
  383.       BitBuffer <<= 8;
  384.       BitCount -= 8;
  385.       ByteOffset += 1;
  386.    }
  387.    /* if last byte of strip force last byte to be written */
  388.    if (FinalByte)
  389.       *bp++ = BitBuffer >> 24;
  390.  
  391.  
  392.    /*
  393.    enc_outcount is used by the compression analysis machinery
  394.    which resets the compression tables when the compression
  395.    ratio goes up.  lzw_bitoff is used here (in PutNextCode) for
  396.    inserting codes into the output buffer.  tif_rawcc must
  397.    be updated for the mainline write code in TIFFWriteScanline()
  398.    so that data is flushed when the end of a strip is reached.
  399.    Note that the latter is rounded up to ensure that a non-zero
  400.    byte count is present.
  401.    */
  402.    sp->enc_outcount += sp->lzw_nbits;
  403.    sp->lzw_bitoff += sp->lzw_nbits;
  404.    tif->tif_rawcc = (sp->lzw_bitoff + 7) >> 3;
  405.    /*
  406.    If the next entry is going to be too big for
  407.    the code size, then increase it, if possible.
  408.    */
  409.    if (sp->lzw_flags & FLAG_CODEDELTA)
  410.    {
  411.       sp->lzw_maxcode = MAXCODE(sp->lzw_nbits = BITS_MIN);
  412.       sp->lzw_flags &= ~FLAG_CODEDELTA;
  413.    }
  414.    else if (sp->lzw_free_ent >= sp->lzw_maxcode)
  415.    {
  416.       sp->lzw_nbits++;
  417.       if (sp->lzw_nbits > BITS_MAX)
  418.      sp->lzw_nbits = BITS_MAX;
  419.       sp->lzw_maxcode = MAXCODE(sp->lzw_nbits);
  420.    }
  421. }
  422.  
  423.  
  424. /*
  425. Check compression ratio and, if things seem to
  426. be slipping, clear the hash table and reset state.
  427. */
  428. static
  429. void cl_block(TIFF *tif)
  430. {
  431.    register LZWState *sp = (LZWState *)tif->tif_data;
  432.    register unsigned long rat;
  433.  
  434.    sp->enc_checkpoint = sp->enc_incount + CHECK_GAP;
  435.    if (sp->enc_incount > 0x007fffffL)
  436.    {
  437.       /* shift will overflow */
  438.       rat = sp->enc_outcount >> 8;
  439.       rat = (rat == 0 ? 0x7fffffffL : sp->enc_incount / rat);
  440.    }
  441.    else
  442.       rat = (sp->enc_incount << 8) / sp->enc_outcount; /* 8 fract bits */
  443.    if (rat <= sp->enc_ratio)
  444.    {
  445.       sp->enc_ratio = 0;
  446.       cl_hash(sp);
  447.       sp->lzw_free_ent = CODE_FIRST;
  448.       sp->lzw_flags |= FLAG_CODEDELTA;
  449.       PutNextCode(tif, CODE_CLEAR);
  450.    }
  451.    else
  452.       sp->enc_ratio = rat;
  453. }
  454.  
  455. /*
  456. Encode a scanline of pixels.
  457.  
  458. Uses an open addressing double hashing (no chaining) on the
  459. prefix code/next character combination.  We do a variant of
  460. Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
  461. relatively-prime secondary probe.  Here, the modular division
  462. first probe is gives way to a faster exclusive-or manipulation.
  463. Also do block compression with an adaptive reset, whereby the
  464. code table is cleared when the compression ratio decreases,
  465. but after the table fills.  The variable-length output codes
  466. are re-sized at this point, and a CODE_CLEAR is generated
  467. for the decoder.
  468. */
  469. static
  470. CompletionCode LZWEncode(TIFF *tif, char *bp, long cc)
  471. {
  472.    register LZWState *sp;
  473.    register long fcode;
  474.    register unsigned c, ent, disp;
  475.    register short h;
  476.  
  477.    if ((sp = (LZWState *)tif->tif_data) == NULL)
  478.       return (FALSE);
  479.    ent = sp->lzw_oldcode;
  480.    if (ent == (unsigned) -1 && cc > 0)
  481.    {
  482.       PutNextCode(tif, CODE_CLEAR);
  483.       ent = *bp++;
  484.       cc--;
  485.       sp->enc_incount++;
  486.    }
  487.    while (cc > 0)
  488.    {
  489.       c = *bp++;
  490.       cc--;
  491.       sp->enc_incount++;
  492.       fcode = (c << BITS_MAX) + ent;
  493.       h = (c << HSHIFT) ^ ent;        /* xor hashing */
  494.       if (sp->enc_htab[h] == fcode)
  495.       {
  496.      ent = sp->enc_codetab[h];
  497.      continue;
  498.       }
  499.       if (sp->enc_htab[h] >= 0)
  500.       {
  501.      /* Primary hash failed, check secondary hash */
  502.      disp = HSIZE - h;
  503.      if (h == 0)
  504.         disp = 1;
  505.      do
  506.      {
  507.         if ((h -= disp) < 0)
  508.            h += HSIZE;
  509.         if (sp->enc_htab[h] == fcode)
  510.         {
  511.            ent = sp->enc_codetab[h];
  512.            goto hit;
  513.         }
  514.      } while (sp->enc_htab[h] >= 0);
  515.       }
  516.       /* New entry, add to table */
  517.       PutNextCode(tif, ent);
  518.       ent = c;
  519.       if (sp->lzw_free_ent < CODE_MAX)
  520.       {
  521.      sp->enc_codetab[h] = sp->lzw_free_ent++;
  522.      sp->enc_htab[h] = fcode;
  523.       }
  524.       else if (sp->enc_incount >= sp->enc_checkpoint)
  525.      cl_block(tif);
  526. hit:  ;
  527.    }
  528.    sp->lzw_oldcode = ent;
  529.    return (TRUE);
  530. }
  531.  
  532. /*
  533. Finish off an encoded strip by flushing the last
  534. string and tacking on an End Of Information code.
  535. */
  536. static
  537. CompletionCode LZWPostEncode(TIFF *tif)
  538. {
  539.    LZWState *sp = (LZWState *)tif->tif_data;
  540.  
  541.    if (sp->lzw_oldcode != -1)
  542.       PutNextCode(tif, sp->lzw_oldcode);
  543.    FinalByte = TRUE;
  544.    PutNextCode(tif, CODE_EOI);
  545.    return (TRUE);
  546. }
  547.  
  548. static
  549. void LZWCleanup(TIFF *tif)
  550. {
  551.    if (tif->tif_data)
  552.    {
  553.       free(tif->tif_data);
  554.       tif->tif_data = NULL;
  555.    }
  556. }
  557.  
  558. void TIFFInitLZW(TIFF *tif)
  559. {
  560.    tif->tif_stripdecode = LZWPreDecode;
  561.    tif->tif_decoderow   = LZWDecode;
  562.    tif->tif_stripencode = LZWPreEncode;
  563.    tif->tif_encoderow   = LZWEncode;
  564.    tif->tif_encodestrip = LZWPostEncode;
  565.    tif->tif_cleanup     = LZWCleanup;
  566. }
  567.  
  568.  
  569. /*
  570. Copyright (c) 1985, 1986 The Regents of the University of California.
  571. All rights reserved.
  572.  
  573. This code is derived from software contributed to Berkeley by
  574. James A. Woods, derived from original work by Spencer Thomas
  575. and Joseph Orost.
  576.  
  577. Redistribution and use in source and binary forms are permitted
  578. provided that the above copyright notice and this paragraph are
  579. duplicated in all such forms and that any documentation,
  580. advertising materials, and other materials related to such
  581. distribution and use acknowledge that the software was developed
  582. by the University of California, Berkeley.  The name of the
  583. University may not be used to endorse or promote products derived
  584. from this software without specific prior written permission.
  585. THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  586. IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  587. WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  588. */
  589.