Home | History | Annotate | Download | only in liblzf
      1 /*
      2  * Copyright (c) 2000-2010 Marc Alexander Lehmann <schmorp (at) schmorp.de>
      3  *
      4  * Redistribution and use in source and binary forms, with or without modifica-
      5  * tion, are permitted provided that the following conditions are met:
      6  *
      7  *   1.  Redistributions of source code must retain the above copyright notice,
      8  *       this list of conditions and the following disclaimer.
      9  *
     10  *   2.  Redistributions in binary form must reproduce the above copyright
     11  *       notice, this list of conditions and the following disclaimer in the
     12  *       documentation and/or other materials provided with the distribution.
     13  *
     14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
     15  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
     16  * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
     17  * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
     18  * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
     20  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
     21  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
     22  * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
     23  * OF THE POSSIBILITY OF SUCH DAMAGE.
     24  *
     25  * Alternatively, the contents of this file may be used under the terms of
     26  * the GNU General Public License ("GPL") version 2 or any later version,
     27  * in which case the provisions of the GPL are applicable instead of
     28  * the above. If you wish to allow the use of your version of this file
     29  * only under the terms of the GPL and not to allow others to use your
     30  * version of this file under the BSD license, indicate your decision
     31  * by deleting the provisions above and replace them with the notice
     32  * and other provisions required by the GPL. If you do not delete the
     33  * provisions above, a recipient may use your version of this file under
     34  * either the BSD or the GPL.
     35  */
     36 
     37 #include "lzfP.h"
     38 
     39 #if AVOID_ERRNO
     40 # define SET_ERRNO(n)
     41 #else
     42 # include <errno.h>
     43 # define SET_ERRNO(n) errno = (n)
     44 #endif
     45 
     46 #if USE_REP_MOVSB /* small win on amd, big loss on intel */
     47 #if (__i386 || __amd64) && __GNUC__ >= 3
     48 # define lzf_movsb(dst, src, len)                \
     49    asm ("rep movsb"                              \
     50         : "=D" (dst), "=S" (src), "=c" (len)     \
     51         :  "0" (dst),  "1" (src),  "2" (len));
     52 #endif
     53 #endif
     54 
     55 unsigned int
     56 lzf_decompress (const void *const in_data,  unsigned int in_len,
     57                 void             *out_data, unsigned int out_len)
     58 {
     59   u8 const *ip = (const u8 *)in_data;
     60   u8       *op = (u8 *)out_data;
     61   u8 const *const in_end  = ip + in_len;
     62   u8       *const out_end = op + out_len;
     63 
     64   do
     65     {
     66       unsigned int ctrl = *ip++;
     67 
     68       if (ctrl < (1 << 5)) /* literal run */
     69         {
     70           ctrl++;
     71 
     72           if (op + ctrl > out_end)
     73             {
     74               SET_ERRNO (E2BIG);
     75               return 0;
     76             }
     77 
     78 #if CHECK_INPUT
     79           if (ip + ctrl > in_end)
     80             {
     81               SET_ERRNO (EINVAL);
     82               return 0;
     83             }
     84 #endif
     85 
     86 #ifdef lzf_movsb
     87           lzf_movsb (op, ip, ctrl);
     88 #else
     89           switch (ctrl)
     90             {
     91               case 32: *op++ = *ip++; case 31: *op++ = *ip++; case 30: *op++ = *ip++; case 29: *op++ = *ip++;
     92               case 28: *op++ = *ip++; case 27: *op++ = *ip++; case 26: *op++ = *ip++; case 25: *op++ = *ip++;
     93               case 24: *op++ = *ip++; case 23: *op++ = *ip++; case 22: *op++ = *ip++; case 21: *op++ = *ip++;
     94               case 20: *op++ = *ip++; case 19: *op++ = *ip++; case 18: *op++ = *ip++; case 17: *op++ = *ip++;
     95               case 16: *op++ = *ip++; case 15: *op++ = *ip++; case 14: *op++ = *ip++; case 13: *op++ = *ip++;
     96               case 12: *op++ = *ip++; case 11: *op++ = *ip++; case 10: *op++ = *ip++; case  9: *op++ = *ip++;
     97               case  8: *op++ = *ip++; case  7: *op++ = *ip++; case  6: *op++ = *ip++; case  5: *op++ = *ip++;
     98               case  4: *op++ = *ip++; case  3: *op++ = *ip++; case  2: *op++ = *ip++; case  1: *op++ = *ip++;
     99             }
    100 #endif
    101         }
    102       else /* back reference */
    103         {
    104           unsigned int len = ctrl >> 5;
    105 
    106           u8 *ref = op - ((ctrl & 0x1f) << 8) - 1;
    107 
    108 #if CHECK_INPUT
    109           if (ip >= in_end)
    110             {
    111               SET_ERRNO (EINVAL);
    112               return 0;
    113             }
    114 #endif
    115           if (len == 7)
    116             {
    117               len += *ip++;
    118 #if CHECK_INPUT
    119               if (ip >= in_end)
    120                 {
    121                   SET_ERRNO (EINVAL);
    122                   return 0;
    123                 }
    124 #endif
    125             }
    126 
    127           ref -= *ip++;
    128 
    129           if (op + len + 2 > out_end)
    130             {
    131               SET_ERRNO (E2BIG);
    132               return 0;
    133             }
    134 
    135           if (ref < (u8 *)out_data)
    136             {
    137               SET_ERRNO (EINVAL);
    138               return 0;
    139             }
    140 
    141 #ifdef lzf_movsb
    142           len += 2;
    143           lzf_movsb (op, ref, len);
    144 #else
    145           switch (len)
    146             {
    147               default:
    148                 len += 2;
    149 
    150                 if (op >= ref + len)
    151                   {
    152                     /* disjunct areas */
    153                     memcpy (op, ref, len);
    154                     op += len;
    155                   }
    156                 else
    157                   {
    158                     /* overlapping, use octte by octte copying */
    159                     do
    160                       *op++ = *ref++;
    161                     while (--len);
    162                   }
    163 
    164                 break;
    165 
    166               case 9: *op++ = *ref++;
    167               case 8: *op++ = *ref++;
    168               case 7: *op++ = *ref++;
    169               case 6: *op++ = *ref++;
    170               case 5: *op++ = *ref++;
    171               case 4: *op++ = *ref++;
    172               case 3: *op++ = *ref++;
    173               case 2: *op++ = *ref++;
    174               case 1: *op++ = *ref++;
    175               case 0: *op++ = *ref++; /* two octets more */
    176                       *op++ = *ref++;
    177             }
    178 #endif
    179         }
    180     }
    181   while (ip < in_end);
    182 
    183   return op - (u8 *)out_data;
    184 }
    185 
    186