lib/lzo/lzo1x_decompress_safe.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  *  LZO1X Decompressor from LZO
0004  *
0005  *  Copyright (C) 1996-2012 Markus F.X.J. Oberhumer <markus@oberhumer.com>
0006  *
0007  *  The full LZO package can be found at:
0008  *  http://www.oberhumer.com/opensource/lzo/
0009  *
0010  *  Changed for Linux kernel use by:
0011  *  Nitin Gupta <nitingupta910@gmail.com>
0012  *  Richard Purdie <rpurdie@openedhand.com>
0013  */
0014
0015 #ifndef STATIC
0016 #include <linux/module.h>
0017 #include <linux/kernel.h>
0018 #endif
0019 #include <asm/unaligned.h>
0020 #include <linux/lzo.h>
0021 #include "lzodefs.h"
0022
0023 #define HAVE_IP(x)      ((size_t)(ip_end - ip) >= (size_t)(x))
0024 #define HAVE_OP(x)      ((size_t)(op_end - op) >= (size_t)(x))
0025 #define NEED_IP(x)      if (!HAVE_IP(x)) goto input_overrun
0026 #define NEED_OP(x)      if (!HAVE_OP(x)) goto output_overrun
0027 #define TEST_LB(m_pos)  if ((m_pos) < out) goto lookbehind_overrun
0028
0029 /* This MAX_255_COUNT is the maximum number of times we can add 255 to a base
0030  * count without overflowing an integer. The multiply will overflow when
0031  * multiplying 255 by more than MAXINT/255. The sum will overflow earlier
0032  * depending on the base count. Since the base count is taken from a u8
0033  * and a few bits, it is safe to assume that it will always be lower than
0034  * or equal to 2*255, thus we can always prevent any overflow by accepting
0035  * two less 255 steps. See Documentation/staging/lzo.rst for more information.
0036  */
0037 #define MAX_255_COUNT      ((((size_t)~0) / 255) - 2)
0038
0039 int lzo1x_decompress_safe(const unsigned char *in, size_t in_len,
0040               unsigned char *out, size_t *out_len)
0041 {
0042     unsigned char *op;
0043     const unsigned char *ip;
0044     size_t t, next;
0045     size_t state = 0;
0046     const unsigned char *m_pos;
0047     const unsigned char * const ip_end = in + in_len;
0048     unsigned char * const op_end = out + *out_len;
0049
0050     unsigned char bitstream_version;
0051
0052     op = out;
0053     ip = in;
0054
0055     if (unlikely(in_len < 3))
0056         goto input_overrun;
0057
0058     if (likely(in_len >= 5) && likely(*ip == 17)) {
0059         bitstream_version = ip[1];
0060         ip += 2;
0061     } else {
0062         bitstream_version = 0;
0063     }
0064
0065     if (*ip > 17) {
0066         t = *ip++ - 17;
0067         if (t < 4) {
0068             next = t;
0069             goto match_next;
0070         }
0071         goto copy_literal_run;
0072     }
0073
0074     for (;;) {
0075         t = *ip++;
0076         if (t < 16) {
0077             if (likely(state == 0)) {
0078                 if (unlikely(t == 0)) {
0079                     size_t offset;
0080                     const unsigned char *ip_last = ip;
0081
0082                     while (unlikely(*ip == 0)) {
0083                         ip++;
0084                         NEED_IP(1);
0085                     }
0086                     offset = ip - ip_last;
0087                     if (unlikely(offset > MAX_255_COUNT))
0088                         return LZO_E_ERROR;
0089
0090                     offset = (offset << 8) - offset;
0091                     t += offset + 15 + *ip++;
0092                 }
0093                 t += 3;
0094 copy_literal_run:
0095 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
0096                 if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
0097                     const unsigned char *ie = ip + t;
0098                     unsigned char *oe = op + t;
0099                     do {
0100                         COPY8(op, ip);
0101                         op += 8;
0102                         ip += 8;
0103                         COPY8(op, ip);
0104                         op += 8;
0105                         ip += 8;
0106                     } while (ip < ie);
0107                     ip = ie;
0108                     op = oe;
0109                 } else
0110 #endif
0111                 {
0112                     NEED_OP(t);
0113                     NEED_IP(t + 3);
0114                     do {
0115                         *op++ = *ip++;
0116                     } while (--t > 0);
0117                 }
0118                 state = 4;
0119                 continue;
0120             } else if (state != 4) {
0121                 next = t & 3;
0122                 m_pos = op - 1;
0123                 m_pos -= t >> 2;
0124                 m_pos -= *ip++ << 2;
0125                 TEST_LB(m_pos);
0126                 NEED_OP(2);
0127                 op[0] = m_pos[0];
0128                 op[1] = m_pos[1];
0129                 op += 2;
0130                 goto match_next;
0131             } else {
0132                 next = t & 3;
0133                 m_pos = op - (1 + M2_MAX_OFFSET);
0134                 m_pos -= t >> 2;
0135                 m_pos -= *ip++ << 2;
0136                 t = 3;
0137             }
0138         } else if (t >= 64) {
0139             next = t & 3;
0140             m_pos = op - 1;
0141             m_pos -= (t >> 2) & 7;
0142             m_pos -= *ip++ << 3;
0143             t = (t >> 5) - 1 + (3 - 1);
0144         } else if (t >= 32) {
0145             t = (t & 31) + (3 - 1);
0146             if (unlikely(t == 2)) {
0147                 size_t offset;
0148                 const unsigned char *ip_last = ip;
0149
0150                 while (unlikely(*ip == 0)) {
0151                     ip++;
0152                     NEED_IP(1);
0153                 }
0154                 offset = ip - ip_last;
0155                 if (unlikely(offset > MAX_255_COUNT))
0156                     return LZO_E_ERROR;
0157
0158                 offset = (offset << 8) - offset;
0159                 t += offset + 31 + *ip++;
0160                 NEED_IP(2);
0161             }
0162             m_pos = op - 1;
0163             next = get_unaligned_le16(ip);
0164             ip += 2;
0165             m_pos -= next >> 2;
0166             next &= 3;
0167         } else {
0168             NEED_IP(2);
0169             next = get_unaligned_le16(ip);
0170             if (((next & 0xfffc) == 0xfffc) &&
0171                 ((t & 0xf8) == 0x18) &&
0172                 likely(bitstream_version)) {
0173                 NEED_IP(3);
0174                 t &= 7;
0175                 t |= ip[2] << 3;
0176                 t += MIN_ZERO_RUN_LENGTH;
0177                 NEED_OP(t);
0178                 memset(op, 0, t);
0179                 op += t;
0180                 next &= 3;
0181                 ip += 3;
0182                 goto match_next;
0183             } else {
0184                 m_pos = op;
0185                 m_pos -= (t & 8) << 11;
0186                 t = (t & 7) + (3 - 1);
0187                 if (unlikely(t == 2)) {
0188                     size_t offset;
0189                     const unsigned char *ip_last = ip;
0190
0191                     while (unlikely(*ip == 0)) {
0192                         ip++;
0193                         NEED_IP(1);
0194                     }
0195                     offset = ip - ip_last;
0196                     if (unlikely(offset > MAX_255_COUNT))
0197                         return LZO_E_ERROR;
0198
0199                     offset = (offset << 8) - offset;
0200                     t += offset + 7 + *ip++;
0201                     NEED_IP(2);
0202                     next = get_unaligned_le16(ip);
0203                 }
0204                 ip += 2;
0205                 m_pos -= next >> 2;
0206                 next &= 3;
0207                 if (m_pos == op)
0208                     goto eof_found;
0209                 m_pos -= 0x4000;
0210             }
0211         }
0212         TEST_LB(m_pos);
0213 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
0214         if (op - m_pos >= 8) {
0215             unsigned char *oe = op + t;
0216             if (likely(HAVE_OP(t + 15))) {
0217                 do {
0218                     COPY8(op, m_pos);
0219                     op += 8;
0220                     m_pos += 8;
0221                     COPY8(op, m_pos);
0222                     op += 8;
0223                     m_pos += 8;
0224                 } while (op < oe);
0225                 op = oe;
0226                 if (HAVE_IP(6)) {
0227                     state = next;
0228                     COPY4(op, ip);
0229                     op += next;
0230                     ip += next;
0231                     continue;
0232                 }
0233             } else {
0234                 NEED_OP(t);
0235                 do {
0236                     *op++ = *m_pos++;
0237                 } while (op < oe);
0238             }
0239         } else
0240 #endif
0241         {
0242             unsigned char *oe = op + t;
0243             NEED_OP(t);
0244             op[0] = m_pos[0];
0245             op[1] = m_pos[1];
0246             op += 2;
0247             m_pos += 2;
0248             do {
0249                 *op++ = *m_pos++;
0250             } while (op < oe);
0251         }
0252 match_next:
0253         state = next;
0254         t = next;
0255 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
0256         if (likely(HAVE_IP(6) && HAVE_OP(4))) {
0257             COPY4(op, ip);
0258             op += t;
0259             ip += t;
0260         } else
0261 #endif
0262         {
0263             NEED_IP(t + 3);
0264             NEED_OP(t);
0265             while (t > 0) {
0266                 *op++ = *ip++;
0267                 t--;
0268             }
0269         }
0270     }
0271
0272 eof_found:
0273     *out_len = op - out;
0274     return (t != 3       ? LZO_E_ERROR :
0275         ip == ip_end ? LZO_E_OK :
0276         ip <  ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN);
0277
0278 input_overrun:
0279     *out_len = op - out;
0280     return LZO_E_INPUT_OVERRUN;
0281
0282 output_overrun:
0283     *out_len = op - out;
0284     return LZO_E_OUTPUT_OVERRUN;
0285
0286 lookbehind_overrun:
0287     *out_len = op - out;
0288     return LZO_E_LOOKBEHIND_OVERRUN;
0289 }
0290 #ifndef STATIC
0291 EXPORT_SYMBOL_GPL(lzo1x_decompress_safe);
0292
0293 MODULE_LICENSE("GPL");
0294 MODULE_DESCRIPTION("LZO1X Decompressor");
0295
0296 #endif