source: bootcd/isolinux/syslinux-6.03/lzo/src/lzo1x_c.ch

Last change on this file was e16e8f2, checked in by Edwin Eefting <edwin@datux.nl>, 3 years ago

bootstuff
  • Property mode set to 100644
File size: 11.7 KB
RevLine 
[e16e8f2]1/* lzo1x_c.ch -- implementation of the LZO1[XY]-1 compression algorithm
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#if 1 && defined(DO_COMPRESS) && !defined(do_compress)
31   /* choose a unique name to better help PGO optimizations */
32#  define do_compress       LZO_PP_ECONCAT2(DO_COMPRESS,_core)
33#endif
34
35
36/***********************************************************************
37// compress a block of data.
38************************************************************************/
39
40static __lzo_noinline lzo_uint
41do_compress ( const lzo_bytep in , lzo_uint  in_len,
42                    lzo_bytep out, lzo_uintp out_len,
43                    lzo_uint  ti,  lzo_voidp wrkmem)
44{
45    const lzo_bytep ip;
46    lzo_bytep op;
47    const lzo_bytep const in_end = in + in_len;
48    const lzo_bytep const ip_end = in + in_len - 20;
49    const lzo_bytep ii;
50    lzo_dict_p const dict = (lzo_dict_p) wrkmem;
51
52    op = out;
53    ip = in;
54    ii = ip;
55
56    ip += ti < 4 ? 4 - ti : 0;
57    for (;;)
58    {
59        const lzo_bytep m_pos;
60#if !(LZO_DETERMINISTIC)
61        LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
62        lzo_uint m_len;
63        lzo_uint dindex;
64next:
65        if __lzo_unlikely(ip >= ip_end)
66            break;
67        DINDEX1(dindex,ip);
68        GINDEX(m_pos,m_off,dict,dindex,in);
69        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
70            goto literal;
71#if 1
72        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
73            goto try_match;
74        DINDEX2(dindex,ip);
75#endif
76        GINDEX(m_pos,m_off,dict,dindex,in);
77        if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
78            goto literal;
79        if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
80            goto try_match;
81        goto literal;
82
83try_match:
84#if (LZO_OPT_UNALIGNED32)
85        if (UA_GET_NE32(m_pos) != UA_GET_NE32(ip))
86#else
87        if (m_pos[0] != ip[0] || m_pos[1] != ip[1] || m_pos[2] != ip[2] || m_pos[3] != ip[3])
88#endif
89        {
90            /* a literal */
91literal:
92            UPDATE_I(dict,0,dindex,ip,in);
93            ip += 1 + ((ip - ii) >> 5);
94            continue;
95        }
96/*match:*/
97        UPDATE_I(dict,0,dindex,ip,in);
98#else
99        lzo_uint m_off;
100        lzo_uint m_len;
101        {
102        lzo_uint32_t dv;
103        lzo_uint dindex;
104literal:
105        ip += 1 + ((ip - ii) >> 5);
106next:
107        if __lzo_unlikely(ip >= ip_end)
108            break;
109        dv = UA_GET_LE32(ip);
110        dindex = DINDEX(dv,ip);
111        GINDEX(m_off,m_pos,in+dict,dindex,in);
112        UPDATE_I(dict,0,dindex,ip,in);
113        if __lzo_unlikely(dv != UA_GET_LE32(m_pos))
114            goto literal;
115        }
116#endif
117
118    /* a match */
119
120        ii -= ti; ti = 0;
121        {
122        lzo_uint t = pd(ip,ii);
123        if (t != 0)
124        {
125            if (t <= 3)
126            {
127                op[-2] = LZO_BYTE(op[-2] | t);
128#if (LZO_OPT_UNALIGNED32)
129                UA_COPY4(op, ii);
130                op += t;
131#else
132                { do *op++ = *ii++; while (--t > 0); }
133#endif
134            }
135#if (LZO_OPT_UNALIGNED32) || (LZO_OPT_UNALIGNED64)
136            else if (t <= 16)
137            {
138                *op++ = LZO_BYTE(t - 3);
139                UA_COPY8(op, ii);
140                UA_COPY8(op+8, ii+8);
141                op += t;
142            }
143#endif
144            else
145            {
146                if (t <= 18)
147                    *op++ = LZO_BYTE(t - 3);
148                else
149                {
150                    lzo_uint tt = t - 18;
151                    *op++ = 0;
152                    while __lzo_unlikely(tt > 255)
153                    {
154                        tt -= 255;
155                        UA_SET1(op, 0);
156                        op++;
157                    }
158                    assert(tt > 0);
159                    *op++ = LZO_BYTE(tt);
160                }
161#if (LZO_OPT_UNALIGNED32) || (LZO_OPT_UNALIGNED64)
162                do {
163                    UA_COPY8(op, ii);
164                    UA_COPY8(op+8, ii+8);
165                    op += 16; ii += 16; t -= 16;
166                } while (t >= 16); if (t > 0)
167#endif
168                { do *op++ = *ii++; while (--t > 0); }
169            }
170        }
171        }
172        m_len = 4;
173        {
174#if (LZO_OPT_UNALIGNED64)
175        lzo_uint64_t v;
176        v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len);
177        if __lzo_unlikely(v == 0) {
178            do {
179                m_len += 8;
180                v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len);
181                if __lzo_unlikely(ip + m_len >= ip_end)
182                    goto m_len_done;
183            } while (v == 0);
184        }
185#if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz64)
186        m_len += lzo_bitops_ctlz64(v) / CHAR_BIT;
187#elif (LZO_ABI_BIG_ENDIAN)
188        if ((v >> (64 - CHAR_BIT)) == 0) do {
189            v <<= CHAR_BIT;
190            m_len += 1;
191        } while ((v >> (64 - CHAR_BIT)) == 0);
192#elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz64)
193        m_len += lzo_bitops_cttz64(v) / CHAR_BIT;
194#elif (LZO_ABI_LITTLE_ENDIAN)
195        if ((v & UCHAR_MAX) == 0) do {
196            v >>= CHAR_BIT;
197            m_len += 1;
198        } while ((v & UCHAR_MAX) == 0);
199#else
200        if (ip[m_len] == m_pos[m_len]) do {
201            m_len += 1;
202        } while (ip[m_len] == m_pos[m_len]);
203#endif
204#elif (LZO_OPT_UNALIGNED32)
205        lzo_uint32_t v;
206        v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);
207        if __lzo_unlikely(v == 0) {
208            do {
209                m_len += 4;
210                v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);
211                if (v != 0)
212                    break;
213                m_len += 4;
214                v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len);
215                if __lzo_unlikely(ip + m_len >= ip_end)
216                    goto m_len_done;
217            } while (v == 0);
218        }
219#if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz32)
220        m_len += lzo_bitops_ctlz32(v) / CHAR_BIT;
221#elif (LZO_ABI_BIG_ENDIAN)
222        if ((v >> (32 - CHAR_BIT)) == 0) do {
223            v <<= CHAR_BIT;
224            m_len += 1;
225        } while ((v >> (32 - CHAR_BIT)) == 0);
226#elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz32)
227        m_len += lzo_bitops_cttz32(v) / CHAR_BIT;
228#elif (LZO_ABI_LITTLE_ENDIAN)
229        if ((v & UCHAR_MAX) == 0) do {
230            v >>= CHAR_BIT;
231            m_len += 1;
232        } while ((v & UCHAR_MAX) == 0);
233#else
234        if (ip[m_len] == m_pos[m_len]) do {
235            m_len += 1;
236        } while (ip[m_len] == m_pos[m_len]);
237#endif
238#else
239        if __lzo_unlikely(ip[m_len] == m_pos[m_len]) {
240            do {
241                m_len += 1;
242                if (ip[m_len] != m_pos[m_len])
243                    break;
244                m_len += 1;
245                if (ip[m_len] != m_pos[m_len])
246                    break;
247                m_len += 1;
248                if (ip[m_len] != m_pos[m_len])
249                    break;
250                m_len += 1;
251                if (ip[m_len] != m_pos[m_len])
252                    break;
253                m_len += 1;
254                if (ip[m_len] != m_pos[m_len])
255                    break;
256                m_len += 1;
257                if (ip[m_len] != m_pos[m_len])
258                    break;
259                m_len += 1;
260                if (ip[m_len] != m_pos[m_len])
261                    break;
262                m_len += 1;
263                if __lzo_unlikely(ip + m_len >= ip_end)
264                    goto m_len_done;
265            } while (ip[m_len] == m_pos[m_len]);
266        }
267#endif
268        }
269m_len_done:
270        m_off = pd(ip,m_pos);
271        ip += m_len;
272        ii = ip;
273        if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
274        {
275            m_off -= 1;
276#if defined(LZO1X)
277            *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
278            *op++ = LZO_BYTE(m_off >> 3);
279#elif defined(LZO1Y)
280            *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
281            *op++ = LZO_BYTE(m_off >> 2);
282#endif
283        }
284        else if (m_off <= M3_MAX_OFFSET)
285        {
286            m_off -= 1;
287            if (m_len <= M3_MAX_LEN)
288                *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
289            else
290            {
291                m_len -= M3_MAX_LEN;
292                *op++ = M3_MARKER | 0;
293                while __lzo_unlikely(m_len > 255)
294                {
295                    m_len -= 255;
296                    UA_SET1(op, 0);
297                    op++;
298                }
299                *op++ = LZO_BYTE(m_len);
300            }
301            *op++ = LZO_BYTE(m_off << 2);
302            *op++ = LZO_BYTE(m_off >> 6);
303        }
304        else
305        {
306            m_off -= 0x4000;
307            if (m_len <= M4_MAX_LEN)
308                *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8) | (m_len - 2));
309            else
310            {
311                m_len -= M4_MAX_LEN;
312                *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8));
313                while __lzo_unlikely(m_len > 255)
314                {
315                    m_len -= 255;
316                    UA_SET1(op, 0);
317                    op++;
318                }
319                *op++ = LZO_BYTE(m_len);
320            }
321            *op++ = LZO_BYTE(m_off << 2);
322            *op++ = LZO_BYTE(m_off >> 6);
323        }
324        goto next;
325    }
326
327    *out_len = pd(op, out);
328    return pd(in_end,ii-ti);
329}
330
331
332/***********************************************************************
333// public entry point
334************************************************************************/
335
336LZO_PUBLIC(int)
337DO_COMPRESS      ( const lzo_bytep in , lzo_uint  in_len,
338                         lzo_bytep out, lzo_uintp out_len,
339                         lzo_voidp wrkmem )
340{
341    const lzo_bytep ip = in;
342    lzo_bytep op = out;
343    lzo_uint l = in_len;
344    lzo_uint t = 0;
345
346    while (l > 20)
347    {
348        lzo_uint ll = l;
349        lzo_uintptr_t ll_end;
350#if 0 || (LZO_DETERMINISTIC)
351        ll = LZO_MIN(ll, 49152);
352#endif
353        ll_end = (lzo_uintptr_t)ip + ll;
354        if ((ll_end + ((t + ll) >> 5)) <= ll_end || (const lzo_bytep)(ll_end + ((t + ll) >> 5)) <= ip + ll)
355            break;
356#if (LZO_DETERMINISTIC)
357        lzo_memset(wrkmem, 0, ((lzo_uint)1 << D_BITS) * sizeof(lzo_dict_t));
358#endif
359        t = do_compress(ip,ll,op,out_len,t,wrkmem);
360        ip += ll;
361        op += *out_len;
362        l  -= ll;
363    }
364    t += l;
365
366    if (t > 0)
367    {
368        const lzo_bytep ii = in + in_len - t;
369
370        if (op == out && t <= 238)
371            *op++ = LZO_BYTE(17 + t);
372        else if (t <= 3)
373            op[-2] = LZO_BYTE(op[-2] | t);
374        else if (t <= 18)
375            *op++ = LZO_BYTE(t - 3);
376        else
377        {
378            lzo_uint tt = t - 18;
379
380            *op++ = 0;
381            while (tt > 255)
382            {
383                tt -= 255;
384                UA_SET1(op, 0);
385                op++;
386            }
387            assert(tt > 0);
388            *op++ = LZO_BYTE(tt);
389        }
390        UA_COPYN(op, ii, t);
391        op += t;
392    }
393
394    *op++ = M4_MARKER | 1;
395    *op++ = 0;
396    *op++ = 0;
397
398    *out_len = pd(op, out);
399    return LZO_E_OK;
400}
401
402
403/*
404vi:ts=4:et
405*/
Note: See TracBrowser for help on using the repository browser.