cpukit/libdl/fastlz.c

0001 /*
0002   FastLZ - lightning-fast lossless compression library
0003
0004   Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
0005   Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
0006   Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
0007
0008   Permission is hereby granted, free of charge, to any person obtaining a copy
0009   of this software and associated documentation files (the "Software"), to deal
0010   in the Software without restriction, including without limitation the rights
0011   to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
0012   copies of the Software, and to permit persons to whom the Software is
0013   furnished to do so, subject to the following conditions:
0014
0015   The above copyright notice and this permission notice shall be included in
0016   all copies or substantial portions of the Software.
0017
0018   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
0019   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
0020   FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
0021   AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
0022   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
0023   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
0024   THE SOFTWARE.
0025 */
0026
0027 #if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
0028
0029 /*
0030  * Always check for bound when decompressing.
0031  * Generally it is best to leave it defined.
0032  */
0033 #define FASTLZ_SAFE
0034
0035 /*
0036  * Give hints to the compiler for branch prediction optimization.
0037  */
0038 #if defined(__GNUC__) && (__GNUC__ > 2)
0039 #define FASTLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
0040 #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
0041 #else
0042 #define FASTLZ_EXPECT_CONDITIONAL(c)    (c)
0043 #define FASTLZ_UNEXPECT_CONDITIONAL(c)  (c)
0044 #endif
0045
0046 /*
0047  * Use inlined functions for supported systems.
0048  */
0049 #if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
0050 #define FASTLZ_INLINE inline
0051 #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
0052 #define FASTLZ_INLINE __inline
0053 #else
0054 #define FASTLZ_INLINE
0055 #endif
0056
0057 /*
0058  * Prevent accessing more than 8-bit at once, except on x86 architectures.
0059  */
0060 #if !defined(FASTLZ_STRICT_ALIGN)
0061 #define FASTLZ_STRICT_ALIGN
0062 #if defined(__i386__) || defined(__386)  /* GNU C, Sun Studio */
0063 #undef FASTLZ_STRICT_ALIGN
0064 #elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
0065 #undef FASTLZ_STRICT_ALIGN
0066 #elif defined(_M_IX86) /* Intel, MSVC */
0067 #undef FASTLZ_STRICT_ALIGN
0068 #elif defined(__386)
0069 #undef FASTLZ_STRICT_ALIGN
0070 #elif defined(_X86_) /* MinGW */
0071 #undef FASTLZ_STRICT_ALIGN
0072 #elif defined(__I86__) /* Digital Mars */
0073 #undef FASTLZ_STRICT_ALIGN
0074 #endif
0075 #endif
0076
0077 /*
0078  * FIXME: use preprocessor magic to set this on different platforms!
0079  */
0080 typedef unsigned char  flzuint8;
0081 typedef unsigned short flzuint16;
0082 typedef unsigned int   flzuint32;
0083
0084 /* prototypes */
0085 int fastlz_compress(const void* input, int length, void* output);
0086 int fastlz_compress_level(int level, const void* input, int length, void* output);
0087 int fastlz_decompress(const void* input, int length, void* output, int maxout);
0088
0089 #define MAX_COPY       32
0090 #define MAX_LEN       264  /* 256 + 8 */
0091 #define MAX_DISTANCE 8192
0092
0093 #if !defined(FASTLZ_STRICT_ALIGN)
0094 #define FASTLZ_READU16(p) *((const flzuint16*)(p))
0095 #else
0096 #define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
0097 #endif
0098
0099 #define HASH_LOG  13
0100 #define HASH_SIZE (1<< HASH_LOG)
0101 #define HASH_MASK  (HASH_SIZE-1)
0102 #define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
0103
0104 #undef FASTLZ_LEVEL
0105 #define FASTLZ_LEVEL 1
0106
0107 #undef FASTLZ_COMPRESSOR
0108 #undef FASTLZ_DECOMPRESSOR
0109 #define FASTLZ_COMPRESSOR fastlz1_compress
0110 #define FASTLZ_DECOMPRESSOR fastlz1_decompress
0111 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
0112 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
0113 #include "fastlz.c"
0114
0115 #undef FASTLZ_LEVEL
0116 #define FASTLZ_LEVEL 2
0117
0118 #undef MAX_DISTANCE
0119 #define MAX_DISTANCE 8191
0120 #define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
0121
0122 #undef FASTLZ_COMPRESSOR
0123 #undef FASTLZ_DECOMPRESSOR
0124 #define FASTLZ_COMPRESSOR fastlz2_compress
0125 #define FASTLZ_DECOMPRESSOR fastlz2_decompress
0126 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
0127 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
0128 #include "fastlz.c"
0129
0130 int fastlz_compress(const void* input, int length, void* output)
0131 {
0132   /* for short block, choose fastlz1 */
0133   if(length < 65536)
0134     return fastlz1_compress(input, length, output);
0135
0136   /* else... */
0137   return fastlz2_compress(input, length, output);
0138 }
0139
0140 int fastlz_decompress(const void* input, int length, void* output, int maxout)
0141 {
0142   /* magic identifier for compression level */
0143   int level = ((*(const flzuint8*)input) >> 5) + 1;
0144
0145   if(level == 1)
0146     return fastlz1_decompress(input, length, output, maxout);
0147   if(level == 2)
0148     return fastlz2_decompress(input, length, output, maxout);
0149
0150   /* unknown level, trigger error */
0151   return 0;
0152 }
0153
0154 int fastlz_compress_level(int level, const void* input, int length, void* output)
0155 {
0156   if(level == 1)
0157     return fastlz1_compress(input, length, output);
0158   if(level == 2)
0159     return fastlz2_compress(input, length, output);
0160
0161   return 0;
0162 }
0163
0164 #else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
0165
0166 static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
0167 {
0168   const flzuint8* ip = (const flzuint8*) input;
0169   const flzuint8* ip_bound = ip + length - 2;
0170   const flzuint8* ip_limit = ip + length - 12;
0171   flzuint8* op = (flzuint8*) output;
0172
0173   const flzuint8* htab[HASH_SIZE];
0174   const flzuint8** hslot;
0175   flzuint32 hval;
0176
0177   flzuint32 copy;
0178
0179   /* sanity check */
0180   if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
0181   {
0182     if(length)
0183     {
0184       /* create literal copy only */
0185       *op++ = length-1;
0186       ip_bound++;
0187       while(ip <= ip_bound)
0188         *op++ = *ip++;
0189       return length+1;
0190     }
0191     else
0192       return 0;
0193   }
0194
0195   /* initializes hash table */
0196   for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
0197     *hslot = ip;
0198
0199   /* we start with literal copy */
0200   copy = 2;
0201   *op++ = MAX_COPY-1;
0202   *op++ = *ip++;
0203   *op++ = *ip++;
0204
0205   /* main loop */
0206   while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
0207   {
0208     const flzuint8* ref;
0209     flzuint32 distance;
0210
0211     /* minimum match length */
0212     flzuint32 len = 3;
0213
0214     /* comparison starting-point */
0215     const flzuint8* anchor = ip;
0216
0217     /* check for a run */
0218 #if FASTLZ_LEVEL==2
0219     if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
0220     {
0221       distance = 1;
0222       #ifndef __rtems__
0223         /*
0224          * ip is assigned a value here, but is immediately assigned another
0225          * value when it goes to match (line 269). The value that was initially
0226          * assigned is not used, and this results in a Coverity issue. See CID
0227          * 1399751
0228          */
0229         ip += 3;
0230       #endif
0231       ref = anchor - 1 + 3;
0232       goto match;
0233     }
0234 #endif
0235
0236     /* find potential match */
0237     HASH_FUNCTION(hval,ip);
0238     hslot = htab + hval;
0239     ref = htab[hval];
0240
0241     /* calculate distance to the match */
0242     distance = anchor - ref;
0243
0244     /* update hash table */
0245     *hslot = anchor;
0246
0247     /* is this a match? check the first 3 bytes */
0248     if(distance==0 ||
0249 #if FASTLZ_LEVEL==1
0250     (distance >= MAX_DISTANCE) ||
0251 #else
0252     (distance >= MAX_FARDISTANCE) ||
0253 #endif
0254     *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
0255       goto literal;
0256
0257 #if FASTLZ_LEVEL==2
0258     /* far, needs at least 5-byte match */
0259     if(distance >= MAX_DISTANCE)
0260     {
0261       if(*ip++ != *ref++ || *ip++!= *ref++)
0262         goto literal;
0263       len += 2;
0264     }
0265
0266     match:
0267 #endif
0268
0269     /* last matched byte */
0270     ip = anchor + len;
0271
0272     /* distance is biased */
0273     distance--;
0274
0275     if(!distance)
0276     {
0277       /* zero distance means a run */
0278       flzuint8 x = ip[-1];
0279       while(ip < ip_bound)
0280         if(*ref++ != x) break; else ip++;
0281     }
0282     else
0283     for(;;)
0284     {
0285       /* safe because the outer check against ip limit */
0286       if(*ref++ != *ip++) break;
0287       if(*ref++ != *ip++) break;
0288       if(*ref++ != *ip++) break;
0289       if(*ref++ != *ip++) break;
0290       if(*ref++ != *ip++) break;
0291       if(*ref++ != *ip++) break;
0292       if(*ref++ != *ip++) break;
0293       if(*ref++ != *ip++) break;
0294       while(ip < ip_bound)
0295         if(*ref++ != *ip++) break;
0296       break;
0297     }
0298
0299     /* if we have copied something, adjust the copy count */
0300     if(copy)
0301       /* copy is biased, '0' means 1 byte copy */
0302       *(op-copy-1) = copy-1;
0303     else
0304       /* back, to overwrite the copy count */
0305       op--;
0306
0307     /* reset literal counter */
0308     copy = 0;
0309
0310     /* length is biased, '1' means a match of 3 bytes */
0311     ip -= 3;
0312     len = ip - anchor;
0313
0314     /* encode the match */
0315 #if FASTLZ_LEVEL==2
0316     if(distance < MAX_DISTANCE)
0317     {
0318       if(len < 7)
0319       {
0320         *op++ = (len << 5) + (distance >> 8);
0321         *op++ = (distance & 255);
0322       }
0323       else
0324       {
0325         *op++ = (7 << 5) + (distance >> 8);
0326         for(len-=7; len >= 255; len-= 255)
0327           *op++ = 255;
0328         *op++ = len;
0329         *op++ = (distance & 255);
0330       }
0331     }
0332     else
0333     {
0334       /* far away, but not yet in the another galaxy... */
0335       if(len < 7)
0336       {
0337         distance -= MAX_DISTANCE;
0338         *op++ = (len << 5) + 31;
0339         *op++ = 255;
0340         *op++ = distance >> 8;
0341         *op++ = distance & 255;
0342       }
0343       else
0344       {
0345         distance -= MAX_DISTANCE;
0346         *op++ = (7 << 5) + 31;
0347         for(len-=7; len >= 255; len-= 255)
0348           *op++ = 255;
0349         *op++ = len;
0350         *op++ = 255;
0351         *op++ = distance >> 8;
0352         *op++ = distance & 255;
0353       }
0354     }
0355 #else
0356
0357     if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
0358       while(len > MAX_LEN-2)
0359       {
0360         *op++ = (7 << 5) + (distance >> 8);
0361         *op++ = MAX_LEN - 2 - 7 -2;
0362         *op++ = (distance & 255);
0363         len -= MAX_LEN-2;
0364       }
0365
0366     if(len < 7)
0367     {
0368       *op++ = (len << 5) + (distance >> 8);
0369       *op++ = (distance & 255);
0370     }
0371     else
0372     {
0373       *op++ = (7 << 5) + (distance >> 8);
0374       *op++ = len - 7;
0375       *op++ = (distance & 255);
0376     }
0377 #endif
0378
0379     /* update the hash at match boundary */
0380     HASH_FUNCTION(hval,ip);
0381     htab[hval] = ip++;
0382     HASH_FUNCTION(hval,ip);
0383     htab[hval] = ip++;
0384
0385     /* assuming literal copy */
0386     *op++ = MAX_COPY-1;
0387
0388     continue;
0389
0390     literal:
0391       *op++ = *anchor++;
0392       ip = anchor;
0393       copy++;
0394       if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
0395       {
0396         copy = 0;
0397         *op++ = MAX_COPY-1;
0398       }
0399   }
0400
0401   /* left-over as literal copy */
0402   ip_bound++;
0403   while(ip <= ip_bound)
0404   {
0405     *op++ = *ip++;
0406     copy++;
0407     if(copy == MAX_COPY)
0408     {
0409       copy = 0;
0410       *op++ = MAX_COPY-1;
0411     }
0412   }
0413
0414   /* if we have copied something, adjust the copy length */
0415   if(copy)
0416     *(op-copy-1) = copy-1;
0417   else
0418     op--;
0419
0420 #if FASTLZ_LEVEL==2
0421   /* marker for fastlz2 */
0422   *(flzuint8*)output |= (1 << 5);
0423 #endif
0424
0425   return op - (flzuint8*)output;
0426 }
0427
0428 static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
0429 {
0430   const flzuint8* ip = (const flzuint8*) input;
0431   const flzuint8* ip_limit  = ip + length;
0432   flzuint8* op = (flzuint8*) output;
0433   flzuint8* op_limit = op + maxout;
0434   flzuint32 ctrl = (*ip++) & 31;
0435   int loop = 1;
0436
0437   do
0438   {
0439     const flzuint8* ref = op;
0440     flzuint32 len = ctrl >> 5;
0441     flzuint32 ofs = (ctrl & 31) << 8;
0442
0443     if(ctrl >= 32)
0444     {
0445 #if FASTLZ_LEVEL==2
0446       flzuint8 code;
0447 #endif
0448       len--;
0449       ref -= ofs;
0450       if (len == 7-1)
0451 #if FASTLZ_LEVEL==1
0452         len += *ip++;
0453       ref -= *ip++;
0454 #else
0455         do
0456         {
0457           code = *ip++;
0458           len += code;
0459         } while (code==255);
0460       code = *ip++;
0461       ref -= code;
0462
0463       /* match from 16-bit distance */
0464       if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
0465       if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
0466       {
0467         ofs = (*ip++) << 8;
0468         ofs += *ip++;
0469         ref = op - ofs - MAX_DISTANCE;
0470       }
0471 #endif
0472
0473 #ifdef FASTLZ_SAFE
0474       if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
0475         return 0;
0476
0477       if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
0478         return 0;
0479 #endif
0480
0481       if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
0482         ctrl = *ip++;
0483       else
0484         loop = 0;
0485
0486       if(ref == op)
0487       {
0488         /* optimize copy for a run */
0489         flzuint8 b = ref[-1];
0490         *op++ = b;
0491         *op++ = b;
0492         *op++ = b;
0493         for(; len; --len)
0494           *op++ = b;
0495       }
0496       else
0497       {
0498 #if !defined(FASTLZ_STRICT_ALIGN)
0499         const flzuint16* p;
0500         flzuint16* q;
0501 #endif
0502         /* copy from reference */
0503         ref--;
0504         *op++ = *ref++;
0505         *op++ = *ref++;
0506         *op++ = *ref++;
0507
0508 #if !defined(FASTLZ_STRICT_ALIGN)
0509         /* copy a byte, so that now it's word aligned */
0510         if(len & 1)
0511         {
0512           *op++ = *ref++;
0513           len--;
0514         }
0515
0516         /* copy 16-bit at once */
0517         q = (flzuint16*) op;
0518         op += len;
0519         p = (const flzuint16*) ref;
0520         for(len>>=1; len > 4; len-=4)
0521         {
0522           *q++ = *p++;
0523           *q++ = *p++;
0524           *q++ = *p++;
0525           *q++ = *p++;
0526         }
0527         for(; len; --len)
0528           *q++ = *p++;
0529 #else
0530         for(; len; --len)
0531           *op++ = *ref++;
0532 #endif
0533       }
0534     }
0535     else
0536     {
0537       ctrl++;
0538 #ifdef FASTLZ_SAFE
0539       if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
0540         return 0;
0541       if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
0542         return 0;
0543 #endif
0544
0545       *op++ = *ip++;
0546       for(--ctrl; ctrl; ctrl--)
0547         *op++ = *ip++;
0548
0549       loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
0550       if(loop)
0551         ctrl = *ip++;
0552     }
0553   }
0554   while(FASTLZ_EXPECT_CONDITIONAL(loop));
0555
0556   return op - (flzuint8*)output;
0557 }
0558
0559 #endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */