home *** CD-ROM | disk | FTP | other *** search
/ PC Online 1997 March / PCO3_97.ISO / filesbbs / os2 / lzo026.arj / LZO026.ZIP / lzo-0.26 / src / lzo1f_9x.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-14  |  7.6 KB  |  338 lines
  1. /* lzo1f_9x.c -- implementation of the LZO1F-999 compression algorithm
  2.  
  3.    This file is part of the LZO real-time data compression library.
  4.  
  5.    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  6.    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  7.  
  8.    The LZO library is free software; you can redistribute it and/or
  9.    modify it under the terms of the GNU General Public License as
  10.    published by the Free Software Foundation; either version 2 of
  11.    the License, or (at your option) any later version.
  12.  
  13.    The LZO library is distributed in the hope that it will be useful,
  14.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16.    GNU General Public License for more details.
  17.  
  18.    You should have received a copy of the GNU General Public License
  19.    along with the LZO library; see the file COPYING.
  20.    If not, write to the Free Software Foundation, Inc.,
  21.    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  22.  
  23.    Markus F.X.J. Oberhumer
  24.    markus.oberhumer@jk.uni-linz.ac.at
  25.  */
  26.  
  27.  
  28.  
  29. #include <lzoconf.h>
  30. #if !defined(LZO_999_UNSUPPORTED)
  31.  
  32. #include <stdio.h>
  33. #include "config1f.h"
  34.  
  35. #if 0
  36. #undef NDEBUG
  37. #include <assert.h>
  38. #endif
  39.  
  40.  
  41. /***********************************************************************
  42. //
  43. ************************************************************************/
  44.  
  45. #define N            16383            /* size of ring buffer */
  46. #define THRESHOLD        2            /* lower limit for match length */
  47. #define F             2048            /* upper limit for match length */
  48.  
  49.  
  50. #define LZO1F
  51. #define LZO_COMPRESS_T    lzo1f_999_t
  52. #define lzo_swd_t        lzo1f_999_swd_t
  53. #include "lzo_mchw.ch"
  54.  
  55.  
  56.  
  57. /***********************************************************************
  58. //
  59. ************************************************************************/
  60.  
  61. static lzo_byte *
  62. code_match ( LZO_COMPRESS_T *c, lzo_byte *op, lzo_uint m_len, lzo_uint m_off )
  63. {
  64.     if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
  65.     {
  66.         m_off -= 1;
  67.         *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
  68.         *op++ = LZO_BYTE(m_off >> 3);
  69.         c->m2_m++;
  70.     }
  71.     else if (m_len == M2_MIN_LEN && m_off <= 2 * M2_MAX_OFFSET &&
  72.              c->r1_lit > 0)
  73.     {
  74.         assert(m_off > M2_MAX_OFFSET);
  75.         m_off -= 1 + M2_MAX_OFFSET;
  76.         *op++ = LZO_BYTE(((m_off & 7) << 2));
  77.         *op++ = LZO_BYTE(m_off >> 3);
  78.         c->r1_r++;
  79.     }
  80.     else
  81.     {
  82.         if (m_len <= M3_MAX_LEN)
  83.             *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
  84.         else
  85.         {
  86.             m_len -= M3_MAX_LEN;
  87.             *op++ = M3_MARKER | 0;
  88.             while (m_len > 255)
  89.             {
  90.                 m_len -= 255;
  91.                 *op++ = 0;
  92.             }
  93.             assert(m_len > 0);
  94.             *op++ = LZO_BYTE(m_len);
  95.         }
  96.         *op++ = LZO_BYTE((m_off & 63) << 2);
  97.         *op++ = LZO_BYTE(m_off >> 6);
  98.         c->m3_m++;
  99.     }
  100.  
  101.     return op;
  102. }
  103.  
  104.  
  105. static lzo_byte *
  106. STORE_RUN ( lzo_byte *op, const lzo_byte *ii, lzo_uint t, lzo_byte *out )
  107. {
  108.     if (t < 4 && op > out)
  109.         op[-2] |= LZO_BYTE(t);
  110.     else if (t <= 31)
  111.         *op++ = LZO_BYTE(t);
  112.     else
  113.     {
  114.         lzo_uint tt = t - 31;
  115.  
  116.         *op++ = 0;
  117.         while (tt > 255)
  118.         {
  119.             tt -= 255;
  120.             *op++ = 0;
  121.         }
  122.         assert(tt > 0);
  123.         *op++ = LZO_BYTE(tt);
  124.     }
  125.     do *op++ = *ii++; while (--t > 0);
  126.  
  127.     return op;
  128. }
  129.  
  130.  
  131. /***********************************************************************
  132. // this is a public function, but there is no prototype in a header file
  133. ************************************************************************/
  134.  
  135. LZO_EXTERN(int)
  136. lzo1f_999_compress_callback ( const lzo_byte *in , lzo_uint  in_len,
  137.                                     lzo_byte *out, lzo_uint *out_len,
  138.                                     lzo_voidp wrkmem,
  139.                                     lzo_progress_callback_t cb );
  140.  
  141. LZO_PUBLIC(int)
  142. lzo1f_999_compress_callback ( const lzo_byte *in , lzo_uint  in_len,
  143.                                     lzo_byte *out, lzo_uint *out_len,
  144.                                     lzo_voidp wrkmem,
  145.                                     lzo_progress_callback_t cb )
  146. {
  147.     lzo_byte *op;
  148.     const lzo_byte *ii;
  149.     lzo_uint lit;
  150.     lzo_uint m_len, m_off;
  151.     LZO_COMPRESS_T cc;
  152.     LZO_COMPRESS_T * const c = &cc;
  153.     lzo_swd_t * const swd = (lzo_swd_t *) wrkmem;
  154.     int r;
  155.  
  156.     /* sanity check */
  157.     if (!lzo_assert(LZO1F_999_MEM_COMPRESS >= lzo_sizeof(lzo_swd_t)))
  158.         return LZO_E_ERROR;
  159.  
  160.     c->init = 0;
  161.     c->ip = c->in = in;
  162.     c->in_end = in + in_len;
  163.     c->cb = cb;
  164.     c->r1_r = c->m2_m = c->m3_m = 0;
  165.  
  166.     op = out;
  167.     ii = c->ip;                /* point to start of literal run */
  168.     lit = 0;
  169.     c->r1_lit = c->r1_m_len = 0;
  170.  
  171.     r = find_match(c,swd,0,0);
  172.     if (r != 0)
  173.         return r;
  174.     while (c->look > 0)
  175.     {
  176.         int lazy_match_min_gain = -1;
  177.         lzo_uint ahead = 0;
  178.  
  179.         m_len = c->m_len;
  180.         m_off = c->m_off;
  181.  
  182.         assert(c->ip - c->look >= in);
  183.         if (lit == 0)
  184.             ii = c->ip - c->look;
  185.         assert(ii + lit == c->ip - c->look);
  186.         assert(swd->swd_char == *(c->ip - c->look));
  187.  
  188.         if ((m_len < M2_MIN_LEN) ||
  189.             (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
  190.         {
  191.             m_len = 0;
  192.         }
  193.         else 
  194.         {
  195.             assert(c->ip - c->look - m_off >= in);
  196.             assert(c->ip - c->look - m_off + m_len < c->ip);
  197.             assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
  198.                               m_len) == 0);
  199.  
  200.             if (lit < 3)
  201.                 lazy_match_min_gain = 1;
  202.             else if (lit == 3)
  203.                 lazy_match_min_gain = 3;
  204.             else if (lit == 31)
  205.                 lazy_match_min_gain = 3;
  206.             else
  207.                 lazy_match_min_gain = 1;
  208.         }
  209.  
  210.         /* try a lazy match */
  211.         if (m_len > 0 && lazy_match_min_gain >= 0 && c->look > m_len)
  212.         {
  213.             r = find_match(c,swd,1,0);
  214.             assert(r == 0);
  215.             assert(c->look > 0);
  216.  
  217.             if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
  218.                 c->m_off > M2_MAX_OFFSET)
  219.             {
  220.                 lazy_match_min_gain += 1;
  221.             }
  222.             else if (c->m_len <= M2_MAX_LEN &&
  223.                      c->m_off <= M2_MAX_OFFSET &&
  224.                      m_off > M2_MAX_OFFSET)
  225.             {
  226.                 if (lazy_match_min_gain > 0)
  227.                     lazy_match_min_gain -= 1;
  228.             }
  229.             else if (m_len == M2_MIN_LEN && c->m_len == M2_MIN_LEN &&
  230.                      c->m_off <= 2 * M2_MAX_OFFSET &&
  231.                      m_off > M2_MAX_OFFSET)
  232.             {
  233.                 if (lazy_match_min_gain > 0)
  234.                     lazy_match_min_gain -= 1;
  235.             }
  236.  
  237.             if (c->m_len >= m_len + lazy_match_min_gain)
  238.             {
  239.                 c->lazy++;
  240. #if !defined(NDEBUG)
  241.                 m_len = c->m_len;
  242.                 m_off = c->m_off;
  243.                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
  244.                                   m_len) == 0);
  245. #endif
  246.                 lit++;
  247.                 assert(ii + lit == c->ip - c->look);
  248.                 continue;
  249.             }
  250.             else
  251.             {
  252.                 ahead = 1;
  253.                 assert(ii + lit + 1 == c->ip - c->look);
  254.             }
  255.             assert(m_len > 0);
  256.         }
  257.         assert(ii + lit + ahead == c->ip - c->look);
  258.  
  259.  
  260.         if (m_len == 0)
  261.         {
  262.             /* a literal */
  263.             lit++;
  264.             r = find_match(c,swd,1,0);
  265.             assert(r == 0);
  266.         }
  267.         else
  268.         {
  269.             /* 1 - store run */
  270.             if (lit > 0)
  271.             {
  272.                 op = STORE_RUN(op,ii,lit,out);
  273.                 c->r1_m_len = m_len;
  274.                 c->r1_lit = lit;
  275.                 lit = 0;
  276.             }
  277.             else
  278.                 c->r1_lit = c->r1_m_len = 0;
  279.  
  280.             /* 2 - code match */
  281.             op = code_match(c,op,m_len,m_off);
  282.             r = find_match(c,swd,m_len,1+ahead);
  283.             assert(r == 0);
  284.         }
  285.  
  286.         c->codesize = op - out;
  287.     } 
  288.  
  289.  
  290.     /* store final run */
  291.     if (lit > 0)
  292.         op = STORE_RUN(op,ii,lit,out);
  293.  
  294. #if defined(LZO_EOF_CODE)
  295.     *op++ = M3_MARKER | 1;
  296.     *op++ = 0;
  297.     *op++ = 0;
  298. #endif
  299.  
  300.     c->codesize = op - out;
  301.     assert(c->textsize == in_len);
  302.  
  303.     *out_len = op - out;
  304.  
  305.     if (c->cb)
  306.         (*c->cb)(c->textsize,c->codesize);
  307.  
  308. #if 0
  309.     printf("%ld %ld -> %ld: %ld %ld %ld %ld\n",
  310.         (long) c->textsize, (long)in_len, (long) c->codesize,
  311.         c->r1_r, c->m2_m, c->m3_m, c->lazy);
  312. #endif
  313.     return LZO_E_OK;
  314. }
  315.  
  316.  
  317.  
  318. /***********************************************************************
  319. //
  320. ************************************************************************/
  321.  
  322. LZO_PUBLIC(int)
  323. lzo1f_999_compress  ( const lzo_byte *in , lzo_uint  in_len,
  324.                             lzo_byte *out, lzo_uint *out_len,
  325.                             lzo_voidp wrkmem )
  326. {
  327.     return lzo1f_999_compress_callback(in,in_len,out,out_len,wrkmem,
  328.                                        (lzo_progress_callback_t) 0);
  329. }
  330.  
  331.  
  332. #endif /* !defined(LZO_999_UNSUPPORTED) */
  333.  
  334. /*
  335. vi:ts=4
  336. */
  337.  
  338.