home *** CD-ROM | disk | FTP | other *** search
/ PC Online 1997 March / PCO3_97.ISO / filesbbs / os2 / lzo026.arj / LZO026.ZIP / lzo-0.26 / src / lzo1x_9x.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-14  |  9.5 KB  |  435 lines
  1. /* lzo1x_9x.c -- implementation of the LZO1X-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 "config1x.h"
  34.  
  35. #if 0
  36. #undef NDEBUG
  37. #include <assert.h>
  38. #endif
  39.  
  40.  
  41. /***********************************************************************
  42. //
  43. ************************************************************************/
  44.  
  45. #define N            0xbfff            /* size of ring buffer */
  46. #define THRESHOLD        1            /* lower limit for match length */
  47. #define F             2048            /* upper limit for match length */
  48.  
  49.  
  50. #define LZO1X
  51. #define LZO_COMPRESS_T    lzo1x_999_t
  52. #define lzo_swd_t        lzo1x_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.     c->match_bytes += m_len;
  65.  
  66.     if (m_len == 2)
  67.     {
  68.         assert(m_off <= M1_MAX_OFFSET);
  69.         assert(c->r1_lit > 0); assert(c->r1_lit < 4);
  70.         m_off -= 1;
  71.         *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
  72.         *op++ = LZO_BYTE(m_off >> 2);
  73.         c->m1a_m++;
  74.     }
  75.     else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
  76.     {
  77.         assert(m_len >= 3);
  78.         m_off -= 1;
  79.         *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
  80.         *op++ = LZO_BYTE(m_off >> 3);
  81.         c->m2_m++;
  82.     }
  83.     else if (m_len == M2_MIN_LEN && m_off <= MX_MAX_OFFSET && c->r1_lit >= 4)
  84.     {
  85.         assert(m_len == 3);
  86.         assert(m_off > M2_MAX_OFFSET);
  87.         m_off -= 1 + M2_MAX_OFFSET;
  88.         *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
  89.         *op++ = LZO_BYTE(m_off >> 2);
  90.         c->m1b_m++;
  91.     }
  92.     else if (m_off <= M3_MAX_OFFSET)
  93.     {
  94.         assert(m_len >= 3);
  95.         m_off -= 1;
  96.         if (m_len <= M3_MAX_LEN)
  97.             *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
  98.         else
  99.         {
  100.             m_len -= M3_MAX_LEN;
  101.             *op++ = M3_MARKER | 0;
  102.             while (m_len > 255)
  103.             {
  104.                 m_len -= 255;
  105.                 *op++ = 0;
  106.             }
  107.             assert(m_len > 0);
  108.             *op++ = LZO_BYTE(m_len);
  109.         }
  110.         *op++ = LZO_BYTE((m_off & 63) << 2);
  111.         *op++ = LZO_BYTE(m_off >> 6);
  112.         c->m3_m++;
  113.     }
  114.     else
  115.     {
  116.         lzo_uint k;
  117.  
  118.         assert(m_len >= 3);
  119.         assert(m_off > 0x4000); assert(m_off <= 0xbfff);
  120.         m_off -= 0x4000;
  121.         k = (m_off & 0x4000) >> 11;
  122.         if (m_len <= M4_MAX_LEN)
  123.             *op++ = LZO_BYTE(M4_MARKER | k | (m_len - 2));
  124.         else
  125.         {
  126.             m_len -= M4_MAX_LEN;
  127.             *op++ = LZO_BYTE(M4_MARKER | k | 0);
  128.             while (m_len > 255)
  129.             {
  130.                 m_len -= 255;
  131.                 *op++ = 0;
  132.             }
  133.             assert(m_len > 0);
  134.             *op++ = LZO_BYTE(m_len);
  135.         }
  136.         *op++ = LZO_BYTE((m_off & 63) << 2);
  137.         *op++ = LZO_BYTE(m_off >> 6);
  138.         c->m4_m++;
  139.     }
  140.  
  141.     return op;
  142. }
  143.  
  144.  
  145. static lzo_byte *
  146. STORE_RUN ( LZO_COMPRESS_T *c, lzo_byte *op, const lzo_byte *ii, lzo_uint t )
  147. {
  148.     c->lit_bytes += t;
  149.  
  150.     if (op == c->out && t <= 238)
  151.     {
  152.         *op++ = LZO_BYTE(17 + t);
  153.     }
  154.     else if (t <= 3)
  155.     {
  156.         op[-2] |= LZO_BYTE(t);
  157.         c->lit1_r++;
  158.     }
  159.     else if (t <= 18)
  160.     {
  161.         *op++ = LZO_BYTE(t - 3);
  162.         c->lit2_r++;
  163.     }
  164.     else
  165.     {
  166.         lzo_uint tt = t - 18;
  167.  
  168.         *op++ = 0;
  169.         while (tt > 255)
  170.         {
  171.             tt -= 255;
  172.             *op++ = 0;
  173.         }
  174.         assert(tt > 0);
  175.         *op++ = LZO_BYTE(tt);
  176.         c->lit3_r++;
  177.     }
  178.     do *op++ = *ii++; while (--t > 0);
  179.  
  180.     return op;
  181. }
  182.  
  183.  
  184. /***********************************************************************
  185. // this is a public function, but there is no prototype in a header file
  186. ************************************************************************/
  187.  
  188. LZO_EXTERN(int)
  189. lzo1x_999_compress_callback ( const lzo_byte *in , lzo_uint  in_len,
  190.                                     lzo_byte *out, lzo_uint *out_len,
  191.                                     lzo_voidp wrkmem,
  192.                                     lzo_progress_callback_t cb );
  193.  
  194. LZO_PUBLIC(int)
  195. lzo1x_999_compress_callback ( const lzo_byte *in , lzo_uint  in_len,
  196.                                     lzo_byte *out, lzo_uint *out_len,
  197.                                     lzo_voidp wrkmem,
  198.                                     lzo_progress_callback_t cb )
  199. {
  200.     lzo_byte *op;
  201.     const lzo_byte *ii;
  202.     lzo_uint lit;
  203.     lzo_uint m_len, m_off;
  204.     LZO_COMPRESS_T cc;
  205.     LZO_COMPRESS_T * const c = &cc;
  206.     lzo_swd_t * const swd = (lzo_swd_t *) wrkmem;
  207.     int r;
  208.  
  209.     /* sanity check */
  210.     if (!lzo_assert(LZO1X_999_MEM_COMPRESS >= lzo_sizeof(lzo_swd_t)))
  211.         return LZO_E_ERROR;
  212.  
  213.     c->init = 0;
  214.     c->ip = c->in = in;
  215.     c->in_end = in + in_len;
  216.     c->out = out;
  217.     c->cb = cb;
  218.     c->m1a_m = c->m1b_m = c->m2_m = c->m3_m = c->m4_m = 0;
  219.     c->lit1_r = c->lit2_r = c->lit3_r = 0;
  220.  
  221.     op = out;
  222.     ii = c->ip;                /* point to start of literal run */
  223.     lit = 0;
  224.     c->r1_lit = c->r1_m_len = 0;
  225.  
  226.     r = find_match(c,swd,0,0);
  227.     if (r != 0)
  228.         return r;
  229.     while (c->look > 0)
  230.     {
  231.         int lazy_match_min_gain = -1;
  232.         lzo_uint ahead = 0;
  233.  
  234.         m_len = c->m_len;
  235.         m_off = c->m_off;
  236.  
  237.         assert(c->ip - c->look >= in);
  238.         if (lit == 0)
  239.             ii = c->ip - c->look;
  240.         assert(ii + lit == c->ip - c->look);
  241.         assert(swd->swd_char == *(c->ip - c->look));
  242.  
  243.         if ((m_len < 2) ||
  244.             (m_len == 2 && (m_off > M1_MAX_OFFSET || lit == 0 || lit >= 4 || op == out)))
  245.         {
  246.             /* a literal */
  247.             m_len = 0;
  248.         }
  249.         else if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET)
  250.         {
  251.             /* compression ratio improves if we code a literal in some cases */
  252.             if (m_off <= MX_MAX_OFFSET && lit >= 4)
  253.                 ;
  254.             else if (lit >= 4)
  255.                 m_len = 0;
  256.         }
  257.  
  258.         if (m_len > 0)
  259.         {
  260.             assert(c->ip - c->look - m_off >= in);
  261.             assert(c->ip - c->look - m_off + m_len < c->ip);
  262.             assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
  263.                               m_len) == 0);
  264.  
  265.             if (lit < 3)
  266.                 lazy_match_min_gain = 1;
  267.             else if (lit == 3)
  268.                 lazy_match_min_gain = 3;
  269.             else if (lit == 18)
  270.                 lazy_match_min_gain = 3;
  271.             else
  272.                 lazy_match_min_gain = 1;
  273.         }
  274.  
  275.         /* try a lazy match */
  276.         if (m_len > 0 && c->look > m_len)
  277.         {
  278.             r = find_match(c,swd,1,0);
  279.             assert(r == 0);
  280.             assert(c->look > 0);
  281.  
  282.             if (m_len == M2_MIN_LEN)
  283.             {
  284.                 if (lit >= 4)
  285.                 {
  286.                     assert(m_off <= MX_MAX_OFFSET);
  287.                     if (c->m_off > MX_MAX_OFFSET)
  288.                         lazy_match_min_gain += 1;
  289.                 }
  290.                 else
  291.                 {
  292.                     if (m_off <= M2_MAX_OFFSET && c->m_off > M2_MAX_OFFSET)
  293.                         lazy_match_min_gain += 1;
  294.                 }
  295.             }
  296.             else if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
  297.                      c->m_off > M2_MAX_OFFSET)
  298.             {
  299.                 lazy_match_min_gain += 1;
  300.             }
  301. #if 0
  302.             else if (m_len <= M3_MAX_LEN && m_off <= M3_MAX_OFFSET &&
  303.                      c->m_off > M3_MAX_OFFSET)
  304.             {
  305.                 lazy_match_min_gain += 1;
  306.             }
  307. #endif
  308.  
  309.             if (c->m_len <= M2_MAX_LEN && c->m_off <= M2_MAX_OFFSET &&
  310.                 m_off > M2_MAX_OFFSET)
  311.             {
  312.                 if (lazy_match_min_gain > 0)
  313.                     lazy_match_min_gain -= 1;
  314.             }
  315. #if 0
  316.             else if (c->m_len <= M3_MAX_LEN && c->m_off <= M3_MAX_OFFSET &&
  317.                      m_off > M3_MAX_OFFSET)
  318.             {
  319.                 if (lazy_match_min_gain > 0)
  320.                     lazy_match_min_gain -= 1;
  321.             }
  322. #endif
  323.  
  324.             if (m_len == 2)
  325.                 if (lazy_match_min_gain == 0)
  326.                     lazy_match_min_gain = 1;
  327.  
  328.             if (c->m_len >= m_len + lazy_match_min_gain)
  329.             {
  330.                 c->lazy++;
  331. #if !defined(NDEBUG)
  332.                 m_len = c->m_len;
  333.                 m_off = c->m_off;
  334.                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
  335.                                   m_len) == 0);
  336. #endif
  337.                 lit++;
  338.                 assert(ii + lit == c->ip - c->look);
  339.                 continue;
  340.             }
  341.             else
  342.             {
  343.                 ahead = 1;
  344.                 assert(ii + lit + 1 == c->ip - c->look);
  345.             }
  346.             assert(m_len > 0);
  347.         }
  348.         assert(ii + lit + ahead == c->ip - c->look);
  349.  
  350.  
  351.         if (m_len == 0)
  352.         {
  353.             /* a literal */
  354.             lit++;
  355.             r = find_match(c,swd,1,0);
  356.         }
  357.         else
  358.         {
  359.             /* 1 - store run */
  360.             if (lit > 0)
  361.             {
  362.                 assert(m_len >= 2);
  363.                 op = STORE_RUN(c,op,ii,lit);
  364.                 c->r1_m_len = m_len;
  365.                 c->r1_lit = lit;
  366.                 lit = 0;
  367.             }
  368.             else
  369.             {
  370.                 assert(m_len >= 3);
  371.                 c->r1_lit = c->r1_m_len = 0;
  372.             }
  373.  
  374.             /* 2 - code match */
  375.             op = code_match(c,op,m_len,m_off);
  376.             r = find_match(c,swd,m_len,1+ahead);
  377.         }
  378.         assert(r == 0);
  379.  
  380.         c->codesize = op - out;
  381.     } 
  382.  
  383.  
  384.     /* store final run */
  385.     if (lit > 0)
  386.         op = STORE_RUN(c,op,ii,lit);
  387.  
  388. #if defined(LZO_EOF_CODE)
  389.     *op++ = M4_MARKER | 1;
  390.     *op++ = 0;
  391.     *op++ = 0;
  392. #endif
  393.  
  394.     c->codesize = op - out;
  395.     assert(c->textsize == in_len);
  396.  
  397.     *out_len = op - out;
  398.  
  399.     if (c->cb)
  400.         (*c->cb)(c->textsize,c->codesize);
  401.  
  402. #if 0
  403.     printf("%ld %ld -> %ld  %ld: %ld %ld %ld %ld %ld  %ld: %ld %ld %ld  %ld\n",
  404.         (long) c->textsize, (long) in_len, (long) c->codesize,
  405.         c->match_bytes, c->m1a_m, c->m1b_m, c->m2_m, c->m3_m, c->m4_m,
  406.         c->lit_bytes, c->lit1_r, c->lit2_r, c->lit3_r, c->lazy);
  407. #endif
  408.     assert(c->lit_bytes + c->match_bytes == in_len);
  409.  
  410.     return LZO_E_OK;
  411. }
  412.  
  413.  
  414.  
  415. /***********************************************************************
  416. //
  417. ************************************************************************/
  418.  
  419. LZO_PUBLIC(int)
  420. lzo1x_999_compress  ( const lzo_byte *in , lzo_uint  in_len,
  421.                             lzo_byte *out, lzo_uint *out_len,
  422.                             lzo_voidp wrkmem )
  423. {
  424.     return lzo1x_999_compress_callback(in,in_len,out,out_len,wrkmem,
  425.                                        (lzo_progress_callback_t) 0);
  426. }
  427.  
  428.  
  429. #endif /* !defined(LZO_999_UNSUPPORTED) */
  430.  
  431. /*
  432. vi:ts=4
  433. */
  434.  
  435.