LXR busybox/archival/libarchive/lzo1x

   1/* implementation of the LZO1X decompression algorithm
   2
   3   This file is part of the LZO real-time data compression library.
   4
   5   Copyright (C) 1996..2008 Markus Franz Xaver Johannes Oberhumer
   6   All Rights Reserved.
   7
   8   Markus F.X.J. Oberhumer <markus@oberhumer.com>
   9   http://www.oberhumer.com/opensource/lzo/
  10
  11   The LZO library is free software; you can redistribute it and/or
  12   modify it under the terms of the GNU General Public License as
  13   published by the Free Software Foundation; either version 2 of
  14   the License, or (at your option) any later version.
  15
  16   The LZO library is distributed in the hope that it will be useful,
  17   but WITHOUT ANY WARRANTY; without even the implied warranty of
  18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19   GNU General Public License for more details.
  20
  21   You should have received a copy of the GNU General Public License
  22   along with the LZO library; see the file COPYING.
  23   If not, write to the Free Software Foundation, Inc.,
  24   51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  25 */
  26#include "libbb.h"
  27#include "liblzo.h"
  28
  29/***********************************************************************
  30// decompress a block of data.
  31************************************************************************/
  32/* safe decompression with overrun testing */
  33int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len,
  34                uint8_t* out, unsigned* out_len /*, void* wrkmem */)
  35{
  36        register uint8_t* op;
  37        register const uint8_t* ip;
  38        register unsigned t;
  39#if defined(COPY_DICT)
  40        unsigned m_off;
  41        const uint8_t* dict_end;
  42#else
  43        register const uint8_t* m_pos = NULL; /* possibly not needed */
  44#endif
  45        const uint8_t* const ip_end = in + in_len;
  46#if defined(HAVE_ANY_OP)
  47        uint8_t* const op_end = out + *out_len;
  48#endif
  49#if defined(LZO1Z)
  50        unsigned last_m_off = 0;
  51#endif
  52
  53//      LZO_UNUSED(wrkmem);
  54
  55#if defined(COPY_DICT)
  56        if (dict) {
  57                if (dict_len > M4_MAX_OFFSET) {
  58                        dict += dict_len - M4_MAX_OFFSET;
  59                        dict_len = M4_MAX_OFFSET;
  60                }
  61                dict_end = dict + dict_len;
  62        } else {
  63                dict_len = 0;
  64                dict_end = NULL;
  65        }
  66#endif /* COPY_DICT */
  67
  68        *out_len = 0;
  69
  70        op = out;
  71        ip = in;
  72
  73        if (*ip > 17) {
  74                t = *ip++ - 17;
  75                if (t < 4)
  76                        goto match_next;
  77                assert(t > 0); NEED_OP(t); NEED_IP(t+1);
  78                do *op++ = *ip++; while (--t > 0);
  79                goto first_literal_run;
  80        }
  81
  82        while (TEST_IP && TEST_OP) {
  83                t = *ip++;
  84                if (t >= 16)
  85                        goto match;
  86                /* a literal run */
  87                if (t == 0) {
  88                        NEED_IP(1);
  89                        while (*ip == 0) {
  90                                t += 255;
  91                                ip++;
  92                                NEED_IP(1);
  93                        }
  94                        TEST_IV(t);
  95                        t += 15 + *ip++;
  96                }
  97                /* copy literals */
  98                assert(t > 0);
  99                NEED_OP(t+3);
 100                NEED_IP(t+4);
 101#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
 102# if !defined(LZO_UNALIGNED_OK_4)
 103                if (PTR_ALIGNED2_4(op, ip))
 104# endif
 105                {
 106                        COPY4(op, ip);
 107                        op += 4;
 108                        ip += 4;
 109                        if (--t > 0) {
 110                                if (t >= 4) {
 111                                        do {
 112                                                COPY4(op, ip);
 113                                                op += 4;
 114                                                ip += 4;
 115                                                t -= 4;
 116                                        } while (t >= 4);
 117                                        if (t > 0)
 118                                                do *op++ = *ip++; while (--t > 0);
 119                                } else {
 120                                        do *op++ = *ip++; while (--t > 0);
 121                                }
 122                        }
 123                }
 124# if !defined(LZO_UNALIGNED_OK_4)
 125                else
 126# endif
 127#endif
 128#if !defined(LZO_UNALIGNED_OK_4)
 129                {
 130                        *op++ = *ip++;
 131                        *op++ = *ip++;
 132                        *op++ = *ip++;
 133                        do *op++ = *ip++; while (--t > 0);
 134                }
 135#endif
 136
 137 first_literal_run:
 138                t = *ip++;
 139                if (t >= 16)
 140                        goto match;
 141#if defined(COPY_DICT)
 142#if defined(LZO1Z)
 143                m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
 144                last_m_off = m_off;
 145#else
 146                m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
 147#endif
 148                NEED_OP(3);
 149                t = 3; COPY_DICT(t,m_off)
 150#else /* !COPY_DICT */
 151#if defined(LZO1Z)
 152                t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
 153                m_pos = op - t;
 154                last_m_off = t;
 155#else
 156                m_pos = op - (1 + M2_MAX_OFFSET);
 157                m_pos -= t >> 2;
 158                m_pos -= *ip++ << 2;
 159#endif
 160                TEST_LB(m_pos); NEED_OP(3);
 161                *op++ = *m_pos++;
 162                *op++ = *m_pos++;
 163                *op++ = *m_pos;
 164#endif /* COPY_DICT */
 165                goto match_done;
 166
 167                /* handle matches */
 168                do {
 169 match:
 170                        if (t >= 64) {          /* a M2 match */
 171#if defined(COPY_DICT)
 172#if defined(LZO1X)
 173                                m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
 174                                t = (t >> 5) - 1;
 175#elif defined(LZO1Y)
 176                                m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
 177                                t = (t >> 4) - 3;
 178#elif defined(LZO1Z)
 179                                m_off = t & 0x1f;
 180                                if (m_off >= 0x1c)
 181                                        m_off = last_m_off;
 182                                else {
 183                                        m_off = 1 + (m_off << 6) + (*ip++ >> 2);
 184                                        last_m_off = m_off;
 185                                }
 186                                t = (t >> 5) - 1;
 187#endif
 188#else /* !COPY_DICT */
 189#if defined(LZO1X)
 190                                m_pos = op - 1;
 191                                m_pos -= (t >> 2) & 7;
 192                                m_pos -= *ip++ << 3;
 193                                t = (t >> 5) - 1;
 194#elif defined(LZO1Y)
 195                                m_pos = op - 1;
 196                                m_pos -= (t >> 2) & 3;
 197                                m_pos -= *ip++ << 2;
 198                                t = (t >> 4) - 3;
 199#elif defined(LZO1Z)
 200                                {
 201                                        unsigned off = t & 0x1f;
 202                                        m_pos = op;
 203                                        if (off >= 0x1c) {
 204                                                assert(last_m_off > 0);
 205                                                m_pos -= last_m_off;
 206                                        } else {
 207                                                off = 1 + (off << 6) + (*ip++ >> 2);
 208                                                m_pos -= off;
 209                                                last_m_off = off;
 210                                        }
 211                                }
 212                                t = (t >> 5) - 1;
 213#endif
 214                                TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 215                                goto copy_match;
 216#endif /* COPY_DICT */
 217                        }
 218                        else if (t >= 32) {                     /* a M3 match */
 219                                t &= 31;
 220                                if (t == 0) {
 221                                        NEED_IP(1);
 222                                        while (*ip == 0) {
 223                                                t += 255;
 224                                                ip++;
 225                                                NEED_IP(1);
 226                                        }
 227                                        TEST_IV(t);
 228                                        t += 31 + *ip++;
 229                                }
 230#if defined(COPY_DICT)
 231#if defined(LZO1Z)
 232                                m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
 233                                last_m_off = m_off;
 234#else
 235                                m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
 236#endif
 237#else /* !COPY_DICT */
 238#if defined(LZO1Z)
 239                                {
 240                                        unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2);
 241                                        m_pos = op - off;
 242                                        last_m_off = off;
 243                                }
 244#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 245                                m_pos = op - 1;
 246                                m_pos -= (* (const lzo_ushortp) ip) >> 2;
 247#else
 248                                m_pos = op - 1;
 249                                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
 250#endif
 251#endif /* COPY_DICT */
 252                                ip += 2;
 253                        }
 254                        else if (t >= 16) {                     /* a M4 match */
 255#if defined(COPY_DICT)
 256                                m_off = (t & 8) << 11;
 257#else /* !COPY_DICT */
 258                                m_pos = op;
 259                                m_pos -= (t & 8) << 11;
 260#endif /* COPY_DICT */
 261                                t &= 7;
 262                                if (t == 0) {
 263                                        NEED_IP(1);
 264                                        while (*ip == 0) {
 265                                                t += 255;
 266                                                ip++;
 267                                                NEED_IP(1);
 268                                        }
 269                                        TEST_IV(t);
 270                                        t += 7 + *ip++;
 271                                }
 272#if defined(COPY_DICT)
 273#if defined(LZO1Z)
 274                                m_off += (ip[0] << 6) + (ip[1] >> 2);
 275#else
 276                                m_off += (ip[0] >> 2) + (ip[1] << 6);
 277#endif
 278                                ip += 2;
 279                                if (m_off == 0)
 280                                        goto eof_found;
 281                                m_off += 0x4000;
 282#if defined(LZO1Z)
 283                                last_m_off = m_off;
 284#endif
 285#else /* !COPY_DICT */
 286#if defined(LZO1Z)
 287                                m_pos -= (ip[0] << 6) + (ip[1] >> 2);
 288#elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 289                                m_pos -= (* (const lzo_ushortp) ip) >> 2;
 290#else
 291                                m_pos -= (ip[0] >> 2) + (ip[1] << 6);
 292#endif
 293                                ip += 2;
 294                                if (m_pos == op)
 295                                        goto eof_found;
 296                                m_pos -= 0x4000;
 297#if defined(LZO1Z)
 298                                last_m_off = pd((const uint8_t*)op, m_pos);
 299#endif
 300#endif /* COPY_DICT */
 301                        }
 302                        else {                          /* a M1 match */
 303#if defined(COPY_DICT)
 304#if defined(LZO1Z)
 305                                m_off = 1 + (t << 6) + (*ip++ >> 2);
 306                                last_m_off = m_off;
 307#else
 308                                m_off = 1 + (t >> 2) + (*ip++ << 2);
 309#endif
 310                                NEED_OP(2);
 311                                t = 2; COPY_DICT(t,m_off)
 312#else /* !COPY_DICT */
 313#if defined(LZO1Z)
 314                                t = 1 + (t << 6) + (*ip++ >> 2);
 315                                m_pos = op - t;
 316                                last_m_off = t;
 317#else
 318                                m_pos = op - 1;
 319                                m_pos -= t >> 2;
 320                                m_pos -= *ip++ << 2;
 321#endif
 322                                TEST_LB(m_pos); NEED_OP(2);
 323                                *op++ = *m_pos++;
 324                                *op++ = *m_pos;
 325#endif /* COPY_DICT */
 326                                goto match_done;
 327                        }
 328
 329                        /* copy match */
 330#if defined(COPY_DICT)
 331
 332                        NEED_OP(t+3-1);
 333                        t += 3-1; COPY_DICT(t,m_off)
 334
 335#else /* !COPY_DICT */
 336
 337                        TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 338#if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
 339# if !defined(LZO_UNALIGNED_OK_4)
 340                        if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) {
 341                                assert((op - m_pos) >= 4);      /* both pointers are aligned */
 342# else
 343                        if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
 344# endif
 345                                COPY4(op,m_pos);
 346                                op += 4; m_pos += 4; t -= 4 - (3 - 1);
 347                                do {
 348                                        COPY4(op,m_pos);
 349                                        op += 4; m_pos += 4; t -= 4;
 350                                } while (t >= 4);
 351                                if (t > 0)
 352                                        do *op++ = *m_pos++; while (--t > 0);
 353                        }
 354                        else
 355#endif
 356                        {
 357 copy_match:
 358                                *op++ = *m_pos++; *op++ = *m_pos++;
 359                                do *op++ = *m_pos++; while (--t > 0);
 360                        }
 361
 362#endif /* COPY_DICT */
 363
 364 match_done:
 365#if defined(LZO1Z)
 366                        t = ip[-1] & 3;
 367#else
 368                        t = ip[-2] & 3;
 369#endif
 370                        if (t == 0)
 371                                break;
 372
 373                        /* copy literals */
 374 match_next:
 375                        assert(t > 0);
 376                        assert(t < 4);
 377                        NEED_OP(t);
 378                        NEED_IP(t+1);
 379#if 0
 380                        do *op++ = *ip++; while (--t > 0);
 381#else
 382                        *op++ = *ip++;
 383                        if (t > 1) {
 384                                *op++ = *ip++;
 385                                if (t > 2)
 386                                        *op++ = *ip++;
 387                        }
 388#endif
 389                        t = *ip++;
 390                } while (TEST_IP && TEST_OP);
 391        }
 392
 393//#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
 394        /* no EOF code was found */
 395        *out_len = pd(op, out);
 396        return LZO_E_EOF_NOT_FOUND;
 397//#endif
 398
 399 eof_found:
 400        assert(t == 1);
 401        *out_len = pd(op, out);
 402        return (ip == ip_end ? LZO_E_OK :
 403                   (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 404
 405//#if defined(HAVE_NEED_IP)
 406 input_overrun:
 407        *out_len = pd(op, out);
 408        return LZO_E_INPUT_OVERRUN;
 409//#endif
 410
 411//#if defined(HAVE_NEED_OP)
 412 output_overrun:
 413        *out_len = pd(op, out);
 414        return LZO_E_OUTPUT_OVERRUN;
 415//#endif
 416
 417//#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
 418 lookbehind_overrun:
 419        *out_len = pd(op, out);
 420        return LZO_E_LOOKBEHIND_OVERRUN;
 421//#endif
 422}
 423