home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / grafik / lzwsch / lzwsrch.ccc next >
Encoding:
Text File  |  1992-05-10  |  2.9 KB  |  98 lines
  1. /*    lzwsrch.c
  2.  *    fast search of LZW tables for encoding
  3.  *    author:            J.F.R. "Frank" Slinkman, 72411,650
  4.  *    last update:    10-May-92
  5.  *    compiler:        Pro-MC
  6.  *    released to the public domain
  7.  *=============================================================================
  8.  *    lzw_search() is invoked as follows:
  9.  *
  10.  *    lzw_search( &bgn_srch, &num_2_srch );
  11.  *
  12.  *    where:    bgn_srch is the number of the pfx_lsb[] element to search first;
  13.  *            num_2_srch is the number of elements to be searched.
  14.  *=============================================================================
  15.  *    initially, num_2_srch will be zero, and bgn_srch will be number of root
  16.  *        values + 2.
  17.  *
  18.  *    if prefix-suffix found in table, function returns slot number where found
  19.  *        and updates bgn_srch and num_2_srch for next invocation.
  20.  *
  21.  *    if prefix_suffix not found, function returns -1, and updates bgn_srch
  22.  *        and num_2_srch for next invocation.
  23.  *
  24.  *    if table full, function returns -2, and re-initializes bgn_srch and
  25.  *        num_2_srch to zero and the number of root values + 2, respectively.
  26.  *=============================================================================
  27.  * globals */
  28.  
  29. char    pfx_lsb[4096];        /* portion of LZW table holding prefix lsbs */
  30. char    pfx_msb[4096];        /*    "    "   "    "      "       "   msbs */
  31. char    sfx_lsb[4096];        /*    "    "   "    "      "    suffix lsbs */
  32. int        prefix, suffix;
  33. int        num_roots;            /* init this value to number of root values + 2 */
  34. /*===========================================================================*/
  35.  
  36. int lzw_search( bgn_srch, num_2_srch )
  37. int    *bgn_srch, *num_2_srch;
  38. {
  39.     int        next_slot, tst_slot, slot, count;
  40.     char    lsb, msb, sfx;
  41.     unsigned int    base = &pfx_lsb[0] - 1;
  42.  
  43.     slot = tst_slot = *bgn_srch;
  44.     count = *num_2_srch;
  45.     next_slot = *bgn_srch + *num_2_srch;
  46.  
  47.     lsb = prefix;
  48.     msb = prefix >> 8;
  49.     sfx = suffix;
  50.  
  51. /* Note:  some compilers may require the above three lines to be written:
  52.  *
  53.  *    lsb = prefix & 0xff;
  54.  *    msb = prefix & 0xff00 >> 8;
  55.  *    sfx = suffix & 0xff;
  56.  */
  57.  
  58.     if ( count > 0 )
  59.     {    do
  60.         {    slot = tst_slot = memchr( &pfx_lsb[tst_slot], lsb, count ) - base;
  61.             count = next_slot - slot;
  62.             --slot;
  63.         }
  64.         while ( ( slot >= 0 )
  65.                 && ( pfx_msb[slot] != msb )
  66.                 && ( sfx_lsb[slot] != sfx )
  67.                 && ( count > 0 ) );
  68.     }
  69.  
  70.     /* string was found if slot >= 0
  71.      * if found, update bgn_srch and num_2_srch and return slot number */
  72.  
  73.     if ( slot >= 0 )
  74.     {    *bgn_srch = tst_slot;
  75.         *num_2_srch = count;
  76.         return slot;
  77.     }
  78.  
  79.     /* if num_2_srch was 0 or if tst_slot < 0, see if table full
  80.      * if full, update bgn_srch and num_2_srch and return -2 */
  81.  
  82.     if ( *bgn_srch == 4096 )
  83.     {    *bgn_srch = num_roots;
  84.         *num_2_srch = 0;
  85.         return -2;
  86.     }
  87.  
  88.     /* if string not found and table not full, write string to table,
  89.      * update bgn_srch and num_2_srch, and return -1 */
  90.  
  91.     pfx_lsb[next_slot] = lsb;
  92.     pfx_msb[next_slot] = msb;
  93.     sfx_lsb[next_slot] = sfx;
  94.     *bgn_srch = num_roots;
  95.     *num_2_srch = next_slot - num_roots + 1;
  96.     return -1;
  97. }
  98.