Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0-only
       2                 :            : /*
       3                 :            :  *  LZO1X Decompressor from LZO
       4                 :            :  *
       5                 :            :  *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
       6                 :            :  *
       7                 :            :  *  The full LZO package can be found at:
       8                 :            :  *  http://www.oberhumer.com/opensource/lzo/
       9                 :            :  *
      10                 :            :  *  Changed for Linux kernel use by:
      11                 :            :  *  Nitin Gupta <nitingupta910@gmail.com>
      12                 :            :  *  Richard Purdie <rpurdie@openedhand.com>
      13                 :            :  */
      14                 :            : 
      15                 :            : #ifndef STATIC
      16                 :            : #include <linux/module.h>
      17                 :            : #include <linux/kernel.h>
      18                 :            : #endif
      19                 :            : #include <asm/unaligned.h>
      20                 :            : #include <linux/lzo.h>
      21                 :            : #include "lzodefs.h"
      22                 :            : 
      23                 :            : #define HAVE_IP(x)      ((size_t)(ip_end - ip) >= (size_t)(x))
      24                 :            : #define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
      25                 :            : #define NEED_IP(x)      if (!HAVE_IP(x)) goto input_overrun
      26                 :            : #define NEED_OP(x)      if (!HAVE_OP(x)) goto output_overrun
      27                 :            : #define TEST_LB(m_pos)  if ((m_pos) < out) goto lookbehind_overrun
      28                 :            : 
      29                 :            : /* This MAX_255_COUNT is the maximum number of times we can add 255 to a base
      30                 :            :  * count without overflowing an integer. The multiply will overflow when
      31                 :            :  * multiplying 255 by more than MAXINT/255. The sum will overflow earlier
      32                 :            :  * depending on the base count. Since the base count is taken from a u8
      33                 :            :  * and a few bits, it is safe to assume that it will always be lower than
      34                 :            :  * or equal to 2*255, thus we can always prevent any overflow by accepting
      35                 :            :  * two less 255 steps. See Documentation/lzo.txt for more information.
      36                 :            :  */
      37                 :            : #define MAX_255_COUNT      ((((size_t)~0) / 255) - 2)
      38                 :            : 
      39                 :          0 : int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
      40                 :            :                           unsigned char *out, size_t *out_len)
      41                 :            : {
      42                 :          0 :         unsigned char *op;
      43                 :          0 :         const unsigned char *ip;
      44                 :          0 :         size_t t, next;
      45                 :          0 :         size_t state = 0;
      46                 :          0 :         const unsigned char *m_pos;
      47                 :          0 :         const unsigned char * const ip_end = in + in_len;
      48                 :          0 :         unsigned char * const op_end = out + *out_len;
      49                 :            : 
      50                 :          0 :         unsigned char bitstream_version;
      51                 :            : 
      52                 :          0 :         op = out;
      53                 :          0 :         ip = in;
      54                 :            : 
      55         [ #  # ]:          0 :         if (unlikely(in_len < 3))
      56                 :          0 :                 goto input_overrun;
      57                 :            : 
      58   [ #  #  #  # ]:          0 :         if (likely(in_len >= 5) && likely(*ip == 17)) {
      59                 :          0 :                 bitstream_version = ip[1];
      60                 :          0 :                 ip += 2;
      61                 :            :         } else {
      62                 :            :                 bitstream_version = 0;
      63                 :            :         }
      64                 :            : 
      65         [ #  # ]:          0 :         if (*ip > 17) {
      66                 :          0 :                 t = *ip++ - 17;
      67         [ #  # ]:          0 :                 if (t < 4) {
      68                 :          0 :                         next = t;
      69                 :          0 :                         goto match_next;
      70                 :            :                 }
      71                 :          0 :                 goto copy_literal_run;
      72                 :            :         }
      73                 :            : 
      74                 :          0 :         for (;;) {
      75                 :          0 :                 t = *ip++;
      76         [ #  # ]:          0 :                 if (t < 16) {
      77         [ #  # ]:          0 :                         if (likely(state == 0)) {
      78         [ #  # ]:          0 :                                 if (unlikely(t == 0)) {
      79                 :            :                                         size_t offset;
      80                 :            :                                         const unsigned char *ip_last = ip;
      81                 :            : 
      82         [ #  # ]:          0 :                                         while (unlikely(*ip == 0)) {
      83                 :          0 :                                                 ip++;
      84         [ #  # ]:          0 :                                                 NEED_IP(1);
      85                 :            :                                         }
      86                 :          0 :                                         offset = ip - ip_last;
      87         [ #  # ]:          0 :                                         if (unlikely(offset > MAX_255_COUNT))
      88                 :            :                                                 return LZO_E_ERROR;
      89                 :            : 
      90                 :          0 :                                         offset = (offset << 8) - offset;
      91                 :          0 :                                         t += offset + 15 + *ip++;
      92                 :            :                                 }
      93                 :          0 :                                 t += 3;
      94                 :          0 : copy_literal_run:
      95                 :            : #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
      96   [ #  #  #  # ]:          0 :                                 if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
      97                 :          0 :                                         const unsigned char *ie = ip + t;
      98                 :          0 :                                         unsigned char *oe = op + t;
      99                 :          0 :                                         do {
     100         [ #  # ]:          0 :                                                 COPY8(op, ip);
     101                 :          0 :                                                 op += 8;
     102                 :          0 :                                                 ip += 8;
     103                 :          0 :                                                 COPY8(op, ip);
     104                 :          0 :                                                 op += 8;
     105                 :          0 :                                                 ip += 8;
     106         [ #  # ]:          0 :                                         } while (ip < ie);
     107                 :            :                                         ip = ie;
     108                 :            :                                         op = oe;
     109                 :            :                                 } else
     110                 :            : #endif
     111                 :            :                                 {
     112         [ #  # ]:          0 :                                         NEED_OP(t);
     113         [ #  # ]:          0 :                                         NEED_IP(t + 3);
     114                 :          0 :                                         do {
     115                 :          0 :                                                 *op++ = *ip++;
     116         [ #  # ]:          0 :                                         } while (--t > 0);
     117                 :            :                                 }
     118                 :          0 :                                 state = 4;
     119                 :          0 :                                 continue;
     120         [ #  # ]:          0 :                         } else if (state != 4) {
     121                 :          0 :                                 next = t & 3;
     122                 :          0 :                                 m_pos = op - 1;
     123                 :          0 :                                 m_pos -= t >> 2;
     124                 :          0 :                                 m_pos -= *ip++ << 2;
     125         [ #  # ]:          0 :                                 TEST_LB(m_pos);
     126         [ #  # ]:          0 :                                 NEED_OP(2);
     127                 :          0 :                                 op[0] = m_pos[0];
     128                 :          0 :                                 op[1] = m_pos[1];
     129                 :          0 :                                 op += 2;
     130                 :          0 :                                 goto match_next;
     131                 :            :                         } else {
     132                 :          0 :                                 next = t & 3;
     133                 :          0 :                                 m_pos = op - (1 + M2_MAX_OFFSET);
     134                 :          0 :                                 m_pos -= t >> 2;
     135                 :          0 :                                 m_pos -= *ip++ << 2;
     136                 :          0 :                                 t = 3;
     137                 :            :                         }
     138         [ #  # ]:          0 :                 } else if (t >= 64) {
     139                 :          0 :                         next = t & 3;
     140                 :          0 :                         m_pos = op - 1;
     141                 :          0 :                         m_pos -= (t >> 2) & 7;
     142                 :          0 :                         m_pos -= *ip++ << 3;
     143                 :          0 :                         t = (t >> 5) - 1 + (3 - 1);
     144         [ #  # ]:          0 :                 } else if (t >= 32) {
     145                 :          0 :                         t = (t & 31) + (3 - 1);
     146         [ #  # ]:          0 :                         if (unlikely(t == 2)) {
     147                 :            :                                 size_t offset;
     148                 :            :                                 const unsigned char *ip_last = ip;
     149                 :            : 
     150         [ #  # ]:          0 :                                 while (unlikely(*ip == 0)) {
     151                 :          0 :                                         ip++;
     152         [ #  # ]:          0 :                                         NEED_IP(1);
     153                 :            :                                 }
     154                 :          0 :                                 offset = ip - ip_last;
     155         [ #  # ]:          0 :                                 if (unlikely(offset > MAX_255_COUNT))
     156                 :            :                                         return LZO_E_ERROR;
     157                 :            : 
     158                 :          0 :                                 offset = (offset << 8) - offset;
     159                 :          0 :                                 t += offset + 31 + *ip++;
     160         [ #  # ]:          0 :                                 NEED_IP(2);
     161                 :            :                         }
     162                 :          0 :                         m_pos = op - 1;
     163                 :          0 :                         next = get_unaligned_le16(ip);
     164                 :          0 :                         ip += 2;
     165                 :          0 :                         m_pos -= next >> 2;
     166                 :          0 :                         next &= 3;
     167                 :            :                 } else {
     168         [ #  # ]:          0 :                         NEED_IP(2);
     169         [ #  # ]:          0 :                         next = get_unaligned_le16(ip);
     170   [ #  #  #  # ]:          0 :                         if (((next & 0xfffc) == 0xfffc) &&
     171                 :          0 :                             ((t & 0xf8) == 0x18) &&
     172         [ #  # ]:          0 :                             likely(bitstream_version)) {
     173         [ #  # ]:          0 :                                 NEED_IP(3);
     174                 :          0 :                                 t &= 7;
     175                 :          0 :                                 t |= ip[2] << 3;
     176                 :          0 :                                 t += MIN_ZERO_RUN_LENGTH;
     177         [ #  # ]:          0 :                                 NEED_OP(t);
     178                 :          0 :                                 memset(op, 0, t);
     179                 :          0 :                                 op += t;
     180                 :          0 :                                 next &= 3;
     181                 :          0 :                                 ip += 3;
     182                 :          0 :                                 goto match_next;
     183                 :            :                         } else {
     184                 :          0 :                                 m_pos = op;
     185                 :          0 :                                 m_pos -= (t & 8) << 11;
     186                 :          0 :                                 t = (t & 7) + (3 - 1);
     187         [ #  # ]:          0 :                                 if (unlikely(t == 2)) {
     188                 :            :                                         size_t offset;
     189                 :            :                                         const unsigned char *ip_last = ip;
     190                 :            : 
     191         [ #  # ]:          0 :                                         while (unlikely(*ip == 0)) {
     192                 :          0 :                                                 ip++;
     193         [ #  # ]:          0 :                                                 NEED_IP(1);
     194                 :            :                                         }
     195                 :          0 :                                         offset = ip - ip_last;
     196         [ #  # ]:          0 :                                         if (unlikely(offset > MAX_255_COUNT))
     197                 :            :                                                 return LZO_E_ERROR;
     198                 :            : 
     199                 :          0 :                                         offset = (offset << 8) - offset;
     200                 :          0 :                                         t += offset + 7 + *ip++;
     201         [ #  # ]:          0 :                                         NEED_IP(2);
     202                 :          0 :                                         next = get_unaligned_le16(ip);
     203                 :            :                                 }
     204                 :          0 :                                 ip += 2;
     205                 :          0 :                                 m_pos -= next >> 2;
     206                 :          0 :                                 next &= 3;
     207         [ #  # ]:          0 :                                 if (m_pos == op)
     208                 :          0 :                                         goto eof_found;
     209                 :          0 :                                 m_pos -= 0x4000;
     210                 :            :                         }
     211                 :            :                 }
     212         [ #  # ]:          0 :                 TEST_LB(m_pos);
     213                 :            : #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
     214         [ #  # ]:          0 :                 if (op - m_pos >= 8) {
     215                 :          0 :                         unsigned char *oe = op + t;
     216         [ #  # ]:          0 :                         if (likely(HAVE_OP(t + 15))) {
     217                 :          0 :                                 do {
     218         [ #  # ]:          0 :                                         COPY8(op, m_pos);
     219                 :          0 :                                         op += 8;
     220                 :          0 :                                         m_pos += 8;
     221                 :          0 :                                         COPY8(op, m_pos);
     222                 :          0 :                                         op += 8;
     223                 :          0 :                                         m_pos += 8;
     224         [ #  # ]:          0 :                                 } while (op < oe);
     225                 :          0 :                                 op = oe;
     226         [ #  # ]:          0 :                                 if (HAVE_IP(6)) {
     227                 :          0 :                                         state = next;
     228                 :          0 :                                         COPY4(op, ip);
     229                 :          0 :                                         op += next;
     230                 :          0 :                                         ip += next;
     231                 :          0 :                                         continue;
     232                 :            :                                 }
     233                 :            :                         } else {
     234         [ #  # ]:          0 :                                 NEED_OP(t);
     235                 :          0 :                                 do {
     236                 :          0 :                                         *op++ = *m_pos++;
     237         [ #  # ]:          0 :                                 } while (op < oe);
     238                 :            :                         }
     239                 :            :                 } else
     240                 :            : #endif
     241                 :            :                 {
     242                 :          0 :                         unsigned char *oe = op + t;
     243         [ #  # ]:          0 :                         NEED_OP(t);
     244                 :          0 :                         op[0] = m_pos[0];
     245                 :          0 :                         op[1] = m_pos[1];
     246                 :          0 :                         op += 2;
     247                 :          0 :                         m_pos += 2;
     248                 :          0 :                         do {
     249                 :          0 :                                 *op++ = *m_pos++;
     250         [ #  # ]:          0 :                         } while (op < oe);
     251                 :            :                 }
     252                 :          0 : match_next:
     253                 :          0 :                 state = next;
     254                 :          0 :                 t = next;
     255                 :            : #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
     256   [ #  #  #  # ]:          0 :                 if (likely(HAVE_IP(6) && HAVE_OP(4))) {
     257                 :          0 :                         COPY4(op, ip);
     258                 :          0 :                         op += t;
     259                 :          0 :                         ip += t;
     260                 :            :                 } else
     261                 :            : #endif
     262                 :            :                 {
     263         [ #  # ]:          0 :                         NEED_IP(t + 3);
     264         [ #  # ]:          0 :                         NEED_OP(t);
     265         [ #  # ]:          0 :                         while (t > 0) {
     266                 :          0 :                                 *op++ = *ip++;
     267                 :          0 :                                 t--;
     268                 :            :                         }
     269                 :            :                 }
     270                 :            :         }
     271                 :            : 
     272                 :            : eof_found:
     273                 :          0 :         *out_len = op - out;
     274         [ #  # ]:          0 :         return (t != 3       ? LZO_E_ERROR :
     275         [ #  # ]:          0 :                 ip == ip_end ? LZO_E_OK :
     276         [ #  # ]:          0 :                 ip <  ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN);
     277                 :            : 
     278                 :          0 : input_overrun:
     279                 :          0 :         *out_len = op - out;
     280                 :          0 :         return LZO_E_INPUT_OVERRUN;
     281                 :            : 
     282                 :          0 : output_overrun:
     283                 :          0 :         *out_len = op - out;
     284                 :          0 :         return LZO_E_OUTPUT_OVERRUN;
     285                 :            : 
     286                 :          0 : lookbehind_overrun:
     287                 :          0 :         *out_len = op - out;
     288                 :          0 :         return LZO_E_LOOKBEHIND_OVERRUN;
     289                 :            : }
     290                 :            : #ifndef STATIC
     291                 :            : EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
     292                 :            : 
     293                 :            : MODULE_LICENSE("GPL");
     294                 :            : MODULE_DESCRIPTION("LZO1X Decompressor");
     295                 :            : 
     296                 :            : #endif