• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1/* lzo_mchw.ch -- matching functions using a window
2
3   This file is part of the LZO real-time data compression library.
4
5   Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
6   All Rights Reserved.
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   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22
23   Markus F.X.J. Oberhumer
24   <markus@oberhumer.com>
25   http://www.oberhumer.com/opensource/lzo/
26 */
27
28
29/***********************************************************************
30//
31************************************************************************/
32
33typedef struct
34{
35    unsigned init;
36
37    lzo_uint look;          /* bytes in lookahead buffer */
38
39    lzo_uint m_len;
40    lzo_uint m_off;
41
42    lzo_uint last_m_len;
43    lzo_uint last_m_off;
44
45    const lzo_bytep bp;
46    const lzo_bytep ip;
47    const lzo_bytep in;
48    const lzo_bytep in_end;
49    lzo_bytep out;
50
51    lzo_callback_p cb;
52
53    lzo_uint textsize;      /* text size counter */
54    lzo_uint codesize;      /* code size counter */
55    lzo_uint printcount;    /* counter for reporting progress every 1K bytes */
56
57    /* some stats */
58    unsigned long lit_bytes;
59    unsigned long match_bytes;
60    unsigned long rep_bytes;
61    unsigned long lazy;
62
63#if defined(LZO1B)
64    lzo_uint r1_m_len;
65
66    /* some stats */
67    unsigned long r1_r, m3_r, m2_m, m3_m;
68#endif
69
70#if defined(LZO1C)
71    lzo_uint r1_m_len;
72    lzo_bytep m3;
73
74    /* some stats */
75    unsigned long r1_r, m3_r, m2_m, m3_m;
76#endif
77
78#if defined(LZO1F)
79    lzo_uint r1_lit;
80    lzo_uint r1_m_len;
81
82    /* some stats */
83    unsigned long r1_r, m2_m, m3_m;
84#endif
85
86#if defined(LZO1X) || defined(LZO1Y) || defined(LZO1Z)
87    lzo_uint r1_lit;
88    lzo_uint r1_m_len;
89
90    /* some stats */
91    unsigned long m1a_m, m1b_m, m2_m, m3_m, m4_m;
92    unsigned long lit1_r, lit2_r, lit3_r;
93#endif
94
95#if defined(LZO2A)
96    /* some stats */
97    unsigned long m1, m2, m3, m4;
98#endif
99}
100LZO_COMPRESS_T;
101
102
103#define getbyte(c)  ((c).ip < (c).in_end ? *((c).ip)++ : (-1))
104
105#include "lzo_swd.ch"
106
107
108/***********************************************************************
109//
110************************************************************************/
111
112static int
113init_match ( LZO_COMPRESS_T *c, lzo_swd_p s,
114             const lzo_bytep dict, lzo_uint dict_len,
115             lzo_uint32_t flags )
116{
117    int r;
118
119    assert(!c->init);
120    c->init = 1;
121
122    s->c = c;
123
124    c->last_m_len = c->last_m_off = 0;
125
126    c->textsize = c->codesize = c->printcount = 0;
127    c->lit_bytes = c->match_bytes = c->rep_bytes = 0;
128    c->lazy = 0;
129
130    r = swd_init(s,dict,dict_len);
131    if (r != LZO_E_OK)
132    {
133        swd_exit(s);
134        return r;
135    }
136
137    s->use_best_off = (flags & 1) ? 1 : 0;
138    return LZO_E_OK;
139}
140
141
142/***********************************************************************
143//
144************************************************************************/
145
146static int
147find_match ( LZO_COMPRESS_T *c, lzo_swd_p s,
148             lzo_uint this_len, lzo_uint skip )
149{
150    assert(c->init);
151
152    if (skip > 0)
153    {
154        assert(this_len >= skip);
155        swd_accept(s, this_len - skip);
156        c->textsize += this_len - skip + 1;
157    }
158    else
159    {
160        assert(this_len <= 1);
161        c->textsize += this_len - skip;
162    }
163
164    s->m_len = SWD_THRESHOLD;
165    s->m_off = 0;
166#ifdef SWD_BEST_OFF
167    if (s->use_best_off)
168        lzo_memset(s->best_pos,0,sizeof(s->best_pos));
169#endif
170    swd_findbest(s);
171    c->m_len = s->m_len;
172    c->m_off = s->m_off;
173
174    swd_getbyte(s);
175
176    if (s->b_char < 0)
177    {
178        c->look = 0;
179        c->m_len = 0;
180        swd_exit(s);
181    }
182    else
183    {
184        c->look = s->look + 1;
185    }
186    c->bp = c->ip - c->look;
187
188#if 0
189    /* brute force match search */
190    if (c->m_len > SWD_THRESHOLD && c->m_len + 1 <= c->look)
191    {
192        const lzo_bytep ip = c->bp;
193        const lzo_bytep m  = c->bp - c->m_off;
194        const lzo_bytep in = c->in;
195
196        if (ip - in > s->swd_n)
197            in = ip - s->swd_n;
198        for (;;)
199        {
200            while (*in != *ip)
201                in++;
202            if (in == ip)
203                break;
204            if (in != m)
205                if (lzo_memcmp(in,ip,c->m_len+1) == 0)
206                    printf("%p %p %p %5d\n",in,ip,m,c->m_len);
207            in++;
208        }
209    }
210#endif
211
212    if (c->cb && c->cb->nprogress && c->textsize > c->printcount)
213    {
214        (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
215        c->printcount += 1024;
216    }
217
218    return LZO_E_OK;
219}
220
221
222/*
223vi:ts=4:et
224*/
225
226