Home | History | Annotate | Line # | Download | only in dist 
      1 /*
      2  * Copyright (c) 2000-2007 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 #if defined(_KERNEL) || defined (_STANDALONE)
     38 #include <lib/libkern/libkern.h>
     39 #include <sys/systm.h>
     40 #include "lzfP.h"
     41 #else
     42 #include "lzf.h"
     43 #endif
     44 
     45 #ifdef _KERNEL
     46 # define SET_ERRNO(n) panic("lzf decompression failure: %s", #n)
     47 #else
     48 # ifdef AVOID_ERRNO
     49 #  define SET_ERRNO(n)
     50 # else
     51 #  include <errno.h>
     52 #  define SET_ERRNO(n) errno = (n)
     53 # endif
     54 #endif
     55 
     56 #if (__i386 || __amd64) && __GNUC__ >= 3
     57 # define lzf_movsb(dst, src, len)                \
     58    asm ("rep movsb"                              \
     59         : "=D" (dst), "=S" (src), "=c" (len)     \
     60         :  "0" (dst),  "1" (src),  "2" (len));
     61 #endif
     62 
     63 unsigned int
     64 lzf_decompress (const void *const in_data,  unsigned int in_len,
     65                 void             *out_data, unsigned int out_len)
     66 {
     67   u8 const *ip = (const u8 *)in_data;
     68   u8       *op = (u8 *)out_data;
     69   u8 const *const in_end  = ip + in_len;
     70   u8       *const out_end = op + out_len;
     71 
     72   do
     73     {
     74       unsigned int ctrl = *ip++;
     75 
     76       if (ctrl < (1 << 5)) /* literal run */
     77         {
     78           ctrl++;
     79 
     80           if (op + ctrl > out_end)
     81             {
     82               SET_ERRNO (E2BIG);
     83               return 0;
     84             }
     85 
     86 #if CHECK_INPUT
     87           if (ip + ctrl > in_end)
     88             {
     89               SET_ERRNO (EINVAL);
     90               return 0;
     91             }
     92 #endif
     93 
     94 #ifdef lzf_movsb
     95           lzf_movsb (op, ip, ctrl);
     96 #else
     97           do
     98             *op++ = *ip++;
     99           while (--ctrl);
    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           *op++ = *ref++;
    146           *op++ = *ref++;
    147 
    148           do
    149             *op++ = *ref++;
    150           while (--len);
    151 #endif
    152         }
    153     }
    154   while (ip < in_end);
    155 
    156   return (unsigned)(op - (u8 *)out_data);
    157 }
    158 
    159