source: rtems-tools/rtemstoolkit/fastlz.c @ 0c0b2d4

4.10
Last change on this file since 0c0b2d4 was 87e0e76, checked in by Chris Johns <chrisj@…>, on Sep 13, 2014 at 2:09:16 AM

Refactor code into the RTEMS Toolkit.

  • Property mode set to 100644
File size: 13.3 KB
Line 
1/* 
2  FastLZ - lightning-fast lossless compression library
3
4  Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
5  Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
6  Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
7
8  Permission is hereby granted, free of charge, to any person obtaining a copy
9  of this software and associated documentation files (the "Software"), to deal
10  in the Software without restriction, including without limitation the rights
11  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12  copies of the Software, and to permit persons to whom the Software is
13  furnished to do so, subject to the following conditions:
14
15  The above copyright notice and this permission notice shall be included in
16  all copies or substantial portions of the Software.
17
18  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24  THE SOFTWARE.
25*/
26
27#if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
28
29/*
30 * Always check for bound when decompressing.
31 * Generally it is best to leave it defined.
32 */
33#define FASTLZ_SAFE
34
35/*
36 * Give hints to the compiler for branch prediction optimization.
37 */
38#if defined(__GNUC__) && (__GNUC__ > 2)
39#define FASTLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
40#define FASTLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
41#else
42#define FASTLZ_EXPECT_CONDITIONAL(c)    (c)
43#define FASTLZ_UNEXPECT_CONDITIONAL(c)  (c)
44#endif
45
46/*
47 * Use inlined functions for supported systems.
48 */
49#if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
50#define FASTLZ_INLINE inline
51#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
52#define FASTLZ_INLINE __inline
53#else
54#define FASTLZ_INLINE
55#endif
56
57/*
58 * Prevent accessing more than 8-bit at once, except on x86 architectures.
59 */
60#if !defined(FASTLZ_STRICT_ALIGN)
61#define FASTLZ_STRICT_ALIGN
62#if defined(__i386__) || defined(__386)  /* GNU C, Sun Studio */
63#undef FASTLZ_STRICT_ALIGN
64#elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
65#undef FASTLZ_STRICT_ALIGN
66#elif defined(_M_IX86) /* Intel, MSVC */
67#undef FASTLZ_STRICT_ALIGN
68#elif defined(__386)
69#undef FASTLZ_STRICT_ALIGN
70#elif defined(_X86_) /* MinGW */
71#undef FASTLZ_STRICT_ALIGN
72#elif defined(__I86__) /* Digital Mars */
73#undef FASTLZ_STRICT_ALIGN
74#endif
75#endif
76
77/*
78 * FIXME: use preprocessor magic to set this on different platforms!
79 */
80typedef unsigned char  flzuint8;
81typedef unsigned short flzuint16;
82typedef unsigned int   flzuint32;
83
84/* prototypes */
85int fastlz_compress(const void* input, int length, void* output);
86int fastlz_compress_level(int level, const void* input, int length, void* output);
87int fastlz_decompress(const void* input, int length, void* output, int maxout);
88
89#define MAX_COPY       32
90#define MAX_LEN       264  /* 256 + 8 */
91#define MAX_DISTANCE 8192
92
93#if !defined(FASTLZ_STRICT_ALIGN)
94#define FASTLZ_READU16(p) *((const flzuint16*)(p))
95#else
96#define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
97#endif
98
99#define HASH_LOG  13
100#define HASH_SIZE (1<< HASH_LOG)
101#define HASH_MASK  (HASH_SIZE-1)
102#define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
103
104#undef FASTLZ_LEVEL
105#define FASTLZ_LEVEL 1
106
107#undef FASTLZ_COMPRESSOR
108#undef FASTLZ_DECOMPRESSOR
109#define FASTLZ_COMPRESSOR fastlz1_compress
110#define FASTLZ_DECOMPRESSOR fastlz1_decompress
111static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
112static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
113#include "fastlz.c"
114
115#undef FASTLZ_LEVEL
116#define FASTLZ_LEVEL 2
117
118#undef MAX_DISTANCE
119#define MAX_DISTANCE 8191
120#define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
121
122#undef FASTLZ_COMPRESSOR
123#undef FASTLZ_DECOMPRESSOR
124#define FASTLZ_COMPRESSOR fastlz2_compress
125#define FASTLZ_DECOMPRESSOR fastlz2_decompress
126static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
127static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
128#include "fastlz.c"
129
130int fastlz_compress(const void* input, int length, void* output)
131{
132  /* for short block, choose fastlz1 */
133  if(length < 65536)
134    return fastlz1_compress(input, length, output);
135
136  /* else... */
137  return fastlz2_compress(input, length, output);
138}
139
140int fastlz_decompress(const void* input, int length, void* output, int maxout)
141{
142  /* magic identifier for compression level */
143  int level = ((*(const flzuint8*)input) >> 5) + 1;
144
145  if(level == 1)
146    return fastlz1_decompress(input, length, output, maxout);
147  if(level == 2)
148    return fastlz2_decompress(input, length, output, maxout);
149
150  /* unknown level, trigger error */
151  return 0;
152}
153
154int fastlz_compress_level(int level, const void* input, int length, void* output)
155{
156  if(level == 1)
157    return fastlz1_compress(input, length, output);
158  if(level == 2)
159    return fastlz2_compress(input, length, output);
160
161  return 0;
162}
163
164#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
165
166static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
167{
168  const flzuint8* ip = (const flzuint8*) input;
169  const flzuint8* ip_bound = ip + length - 2;
170  const flzuint8* ip_limit = ip + length - 12;
171  flzuint8* op = (flzuint8*) output;
172
173  const flzuint8* htab[HASH_SIZE];
174  const flzuint8** hslot;
175  flzuint32 hval;
176
177  flzuint32 copy;
178
179  /* sanity check */
180  if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
181  {
182    if(length)
183    {
184      /* create literal copy only */
185      *op++ = length-1;
186      ip_bound++;
187      while(ip <= ip_bound)
188        *op++ = *ip++;
189      return length+1;
190    }
191    else
192      return 0;
193  }
194
195  /* initializes hash table */
196  for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
197    *hslot = ip;
198
199  /* we start with literal copy */
200  copy = 2;
201  *op++ = MAX_COPY-1;
202  *op++ = *ip++;
203  *op++ = *ip++;
204
205  /* main loop */
206  while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
207  {
208    const flzuint8* ref;
209    flzuint32 distance;
210
211    /* minimum match length */
212    flzuint32 len = 3;
213
214    /* comparison starting-point */
215    const flzuint8* anchor = ip;
216
217    /* check for a run */
218#if FASTLZ_LEVEL==2
219    if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
220    {
221      distance = 1;
222      ip += 3;
223      ref = anchor - 1 + 3;
224      goto match;
225    }
226#endif
227
228    /* find potential match */
229    HASH_FUNCTION(hval,ip);
230    hslot = htab + hval;
231    ref = htab[hval];
232
233    /* calculate distance to the match */
234    distance = anchor - ref;
235
236    /* update hash table */
237    *hslot = anchor;
238
239    /* is this a match? check the first 3 bytes */
240    if(distance==0 || 
241#if FASTLZ_LEVEL==1
242    (distance >= MAX_DISTANCE) ||
243#else
244    (distance >= MAX_FARDISTANCE) ||
245#endif
246    *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
247      goto literal;
248
249#if FASTLZ_LEVEL==2
250    /* far, needs at least 5-byte match */
251    if(distance >= MAX_DISTANCE)
252    {
253      if(*ip++ != *ref++ || *ip++!= *ref++) 
254        goto literal;
255      len += 2;
256    }
257   
258    match:
259#endif
260
261    /* last matched byte */
262    ip = anchor + len;
263
264    /* distance is biased */
265    distance--;
266
267    if(!distance)
268    {
269      /* zero distance means a run */
270      flzuint8 x = ip[-1];
271      while(ip < ip_bound)
272        if(*ref++ != x) break; else ip++;
273    }
274    else
275    for(;;)
276    {
277      /* safe because the outer check against ip limit */
278      if(*ref++ != *ip++) break;
279      if(*ref++ != *ip++) break;
280      if(*ref++ != *ip++) break;
281      if(*ref++ != *ip++) break;
282      if(*ref++ != *ip++) break;
283      if(*ref++ != *ip++) break;
284      if(*ref++ != *ip++) break;
285      if(*ref++ != *ip++) break;
286      while(ip < ip_bound)
287        if(*ref++ != *ip++) break;
288      break;
289    }
290
291    /* if we have copied something, adjust the copy count */
292    if(copy)
293      /* copy is biased, '0' means 1 byte copy */
294      *(op-copy-1) = copy-1;
295    else
296      /* back, to overwrite the copy count */
297      op--;
298
299    /* reset literal counter */
300    copy = 0;
301
302    /* length is biased, '1' means a match of 3 bytes */
303    ip -= 3;
304    len = ip - anchor;
305
306    /* encode the match */
307#if FASTLZ_LEVEL==2
308    if(distance < MAX_DISTANCE)
309    {
310      if(len < 7)
311      {
312        *op++ = (len << 5) + (distance >> 8);
313        *op++ = (distance & 255);
314      }
315      else
316      {
317        *op++ = (7 << 5) + (distance >> 8);
318        for(len-=7; len >= 255; len-= 255)
319          *op++ = 255;
320        *op++ = len;
321        *op++ = (distance & 255);
322      }
323    }
324    else
325    {
326      /* far away, but not yet in the another galaxy... */
327      if(len < 7)
328      {
329        distance -= MAX_DISTANCE;
330        *op++ = (len << 5) + 31;
331        *op++ = 255;
332        *op++ = distance >> 8;
333        *op++ = distance & 255;
334      }
335      else
336      {
337        distance -= MAX_DISTANCE;
338        *op++ = (7 << 5) + 31;
339        for(len-=7; len >= 255; len-= 255)
340          *op++ = 255;
341        *op++ = len;
342        *op++ = 255;
343        *op++ = distance >> 8;
344        *op++ = distance & 255;
345      }
346    }
347#else
348
349    if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
350      while(len > MAX_LEN-2)
351      {
352        *op++ = (7 << 5) + (distance >> 8);
353        *op++ = MAX_LEN - 2 - 7 -2; 
354        *op++ = (distance & 255);
355        len -= MAX_LEN-2;
356      }
357
358    if(len < 7)
359    {
360      *op++ = (len << 5) + (distance >> 8);
361      *op++ = (distance & 255);
362    }
363    else
364    {
365      *op++ = (7 << 5) + (distance >> 8);
366      *op++ = len - 7;
367      *op++ = (distance & 255);
368    }
369#endif
370
371    /* update the hash at match boundary */
372    HASH_FUNCTION(hval,ip);
373    htab[hval] = ip++;
374    HASH_FUNCTION(hval,ip);
375    htab[hval] = ip++;
376
377    /* assuming literal copy */
378    *op++ = MAX_COPY-1;
379
380    continue;
381
382    literal:
383      *op++ = *anchor++;
384      ip = anchor;
385      copy++;
386      if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
387      {
388        copy = 0;
389        *op++ = MAX_COPY-1;
390      }
391  }
392
393  /* left-over as literal copy */
394  ip_bound++;
395  while(ip <= ip_bound)
396  {
397    *op++ = *ip++;
398    copy++;
399    if(copy == MAX_COPY)
400    {
401      copy = 0;
402      *op++ = MAX_COPY-1;
403    }
404  }
405
406  /* if we have copied something, adjust the copy length */
407  if(copy)
408    *(op-copy-1) = copy-1;
409  else
410    op--;
411
412#if FASTLZ_LEVEL==2
413  /* marker for fastlz2 */
414  *(flzuint8*)output |= (1 << 5);
415#endif
416
417  return op - (flzuint8*)output;
418}
419
420static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
421{
422  const flzuint8* ip = (const flzuint8*) input;
423  const flzuint8* ip_limit  = ip + length;
424  flzuint8* op = (flzuint8*) output;
425  flzuint8* op_limit = op + maxout;
426  flzuint32 ctrl = (*ip++) & 31;
427  int loop = 1;
428
429  do
430  {
431    const flzuint8* ref = op;
432    flzuint32 len = ctrl >> 5;
433    flzuint32 ofs = (ctrl & 31) << 8;
434
435    if(ctrl >= 32)
436    {
437#if FASTLZ_LEVEL==2
438      flzuint8 code;
439#endif
440      len--;
441      ref -= ofs;
442      if (len == 7-1)
443#if FASTLZ_LEVEL==1
444        len += *ip++;
445      ref -= *ip++;
446#else
447        do
448        {
449          code = *ip++;
450          len += code;
451        } while (code==255);
452      code = *ip++;
453      ref -= code;
454
455      /* match from 16-bit distance */
456      if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
457      if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
458      {
459        ofs = (*ip++) << 8;
460        ofs += *ip++;
461        ref = op - ofs - MAX_DISTANCE;
462      }
463#endif
464     
465#ifdef FASTLZ_SAFE
466      if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
467        return 0;
468
469      if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
470        return 0;
471#endif
472
473      if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
474        ctrl = *ip++;
475      else
476        loop = 0;
477
478      if(ref == op)
479      {
480        /* optimize copy for a run */
481        flzuint8 b = ref[-1];
482        *op++ = b;
483        *op++ = b;
484        *op++ = b;
485        for(; len; --len)
486          *op++ = b;
487      }
488      else
489      {
490#if !defined(FASTLZ_STRICT_ALIGN)
491        const flzuint16* p;
492        flzuint16* q;
493#endif
494        /* copy from reference */
495        ref--;
496        *op++ = *ref++;
497        *op++ = *ref++;
498        *op++ = *ref++;
499
500#if !defined(FASTLZ_STRICT_ALIGN)
501        /* copy a byte, so that now it's word aligned */
502        if(len & 1)
503        {
504          *op++ = *ref++;
505          len--;
506        }
507
508        /* copy 16-bit at once */
509        q = (flzuint16*) op;
510        op += len;
511        p = (const flzuint16*) ref;
512        for(len>>=1; len > 4; len-=4)
513        {
514          *q++ = *p++;
515          *q++ = *p++;
516          *q++ = *p++;
517          *q++ = *p++;
518        }
519        for(; len; --len)
520          *q++ = *p++;
521#else
522        for(; len; --len)
523          *op++ = *ref++;
524#endif
525      }
526    }
527    else
528    {
529      ctrl++;
530#ifdef FASTLZ_SAFE
531      if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
532        return 0;
533      if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
534        return 0;
535#endif
536
537      *op++ = *ip++; 
538      for(--ctrl; ctrl; ctrl--)
539        *op++ = *ip++;
540
541      loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
542      if(loop)
543        ctrl = *ip++;
544    }
545  }
546  while(FASTLZ_EXPECT_CONDITIONAL(loop));
547
548  return op - (flzuint8*)output;
549}
550
551#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
Note: See TracBrowser for help on using the repository browser.