2
FastLZ - lightning-fast lossless compression library
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)
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:
15
The above copyright notice and this permission notice shall be included in
16
all copies or substantial portions of the Software.
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
27
#if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
30
* Always check for bound when decompressing.
31
* Generally it is best to leave it defined.
36
* Give hints to the compiler for branch prediction optimization.
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))
42
#define FASTLZ_EXPECT_CONDITIONAL(c) (c)
43
#define FASTLZ_UNEXPECT_CONDITIONAL(c) (c)
47
* Use inlined functions for supported systems.
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
58
* Prevent accessing more than 8-bit at once, except on x86 architectures.
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
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
78
* FIXME: use preprocessor magic to set this on different platforms!
80
typedef unsigned char flzuint8;
81
typedef unsigned short flzuint16;
82
typedef unsigned int flzuint32;
85
int fastlz_compress(const void* input, int length, void* output);
86
int fastlz_compress_level(int level, const void* input, int length, void* output);
87
int fastlz_decompress(const void* input, int length, void* output, int maxout);
90
#define MAX_LEN 264 /* 256 + 8 */
91
#define MAX_DISTANCE 8192
93
#if !defined(FASTLZ_STRICT_ALIGN)
94
#define FASTLZ_READU16(p) *((const flzuint16*)(p))
96
#define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
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; }
105
#define FASTLZ_LEVEL 1
107
#undef FASTLZ_COMPRESSOR
108
#undef FASTLZ_DECOMPRESSOR
109
#define FASTLZ_COMPRESSOR fastlz1_compress
110
#define FASTLZ_DECOMPRESSOR fastlz1_decompress
111
static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
112
static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
116
#define FASTLZ_LEVEL 2
119
#define MAX_DISTANCE 8191
120
#define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
122
#undef FASTLZ_COMPRESSOR
123
#undef FASTLZ_DECOMPRESSOR
124
#define FASTLZ_COMPRESSOR fastlz2_compress
125
#define FASTLZ_DECOMPRESSOR fastlz2_decompress
126
static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
127
static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
130
int fastlz_compress(const void* input, int length, void* output)
132
/* for short block, choose fastlz1 */
134
return fastlz1_compress(input, length, output);
137
return fastlz2_compress(input, length, output);
140
int fastlz_decompress(const void* input, int length, void* output, int maxout)
142
/* magic identifier for compression level */
143
int level = ((*(const flzuint8*)input) >> 5) + 1;
146
return fastlz1_decompress(input, length, output, maxout);
148
return fastlz2_decompress(input, length, output, maxout);
150
/* unknown level, trigger error */
154
int fastlz_compress_level(int level, const void* input, int length, void* output)
157
return fastlz1_compress(input, length, output);
159
return fastlz2_compress(input, length, output);
164
#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
166
static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
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;
173
const flzuint8* htab[HASH_SIZE];
174
const flzuint8** hslot;
180
if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
184
/* create literal copy only */
187
while(ip <= ip_bound)
195
/* initializes hash table */
196
for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
199
/* we start with literal copy */
206
while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
211
/* minimum match length */
214
/* comparison starting-point */
215
const flzuint8* anchor = ip;
217
/* check for a run */
219
if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
223
ref = anchor - 1 + 3;
228
/* find potential match */
229
HASH_FUNCTION(hval,ip);
233
/* calculate distance to the match */
234
distance = anchor - ref;
236
/* update hash table */
239
/* is this a match? check the first 3 bytes */
242
(distance >= MAX_DISTANCE) ||
244
(distance >= MAX_FARDISTANCE) ||
246
*ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
250
/* far, needs at least 5-byte match */
251
if(distance >= MAX_DISTANCE)
253
if(*ip++ != *ref++ || *ip++!= *ref++)
261
/* last matched byte */
264
/* distance is biased */
269
/* zero distance means a run */
272
if(*ref++ != x) break; else ip++;
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;
287
if(*ref++ != *ip++) break;
291
/* if we have copied something, adjust the copy count */
293
/* copy is biased, '0' means 1 byte copy */
294
*(op-copy-1) = copy-1;
296
/* back, to overwrite the copy count */
299
/* reset literal counter */
302
/* length is biased, '1' means a match of 3 bytes */
306
/* encode the match */
308
if(distance < MAX_DISTANCE)
312
*op++ = (len << 5) + (distance >> 8);
313
*op++ = (distance & 255);
317
*op++ = (7 << 5) + (distance >> 8);
318
for(len-=7; len >= 255; len-= 255)
321
*op++ = (distance & 255);
326
/* far away, but not yet in the another galaxy... */
329
distance -= MAX_DISTANCE;
330
*op++ = (len << 5) + 31;
332
*op++ = distance >> 8;
333
*op++ = distance & 255;
337
distance -= MAX_DISTANCE;
338
*op++ = (7 << 5) + 31;
339
for(len-=7; len >= 255; len-= 255)
343
*op++ = distance >> 8;
344
*op++ = distance & 255;
349
if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
350
while(len > MAX_LEN-2)
352
*op++ = (7 << 5) + (distance >> 8);
353
*op++ = MAX_LEN - 2 - 7 -2;
354
*op++ = (distance & 255);
360
*op++ = (len << 5) + (distance >> 8);
361
*op++ = (distance & 255);
365
*op++ = (7 << 5) + (distance >> 8);
367
*op++ = (distance & 255);
371
/* update the hash at match boundary */
372
HASH_FUNCTION(hval,ip);
374
HASH_FUNCTION(hval,ip);
377
/* assuming literal copy */
386
if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
393
/* left-over as literal copy */
395
while(ip <= ip_bound)
406
/* if we have copied something, adjust the copy length */
408
*(op-copy-1) = copy-1;
413
/* marker for fastlz2 */
414
*(flzuint8*)output |= (1 << 5);
417
return op - (flzuint8*)output;
420
static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
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;
431
const flzuint8* ref = op;
432
flzuint32 len = ctrl >> 5;
433
flzuint32 ofs = (ctrl & 31) << 8;
455
/* match from 16-bit distance */
456
if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
457
if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
461
ref = op - ofs - MAX_DISTANCE;
466
if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
469
if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
473
if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
480
/* optimize copy for a run */
481
flzuint8 b = ref[-1];
490
#if !defined(FASTLZ_STRICT_ALIGN)
494
/* copy from reference */
500
#if !defined(FASTLZ_STRICT_ALIGN)
501
/* copy a byte, so that now it's word aligned */
508
/* copy 16-bit at once */
511
p = (const flzuint16*) ref;
512
for(len>>=1; len > 4; len-=4)
531
if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
533
if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
538
for(--ctrl; ctrl; ctrl--)
541
loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
546
while(FASTLZ_EXPECT_CONDITIONAL(loop));
548
return op - (flzuint8*)output;
551
#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
added
removed
lib/ts/fastlz.c
