archival/libarchive/lzo1x_d.c

   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 */
  33 int lzo1x_decompress_safe(const uint8_t* in, unsigned in_len,
  34                 uint8_t* out, unsigned* out_len,
  35                 void* wrkmem UNUSED_PARAM)
  36 {
  37         register uint8_t* op;
  38         register const uint8_t* ip;
  39         register unsigned t;
  40 #if defined(COPY_DICT)
  41         unsigned m_off;
  42         const uint8_t* dict_end;
  43 #else
  44         register const uint8_t* m_pos = NULL; /* possibly not needed */
  45 #endif
  46         const uint8_t* const ip_end = in + in_len;
  47 #if defined(HAVE_ANY_OP)
  48         uint8_t* const op_end = out + *out_len;
  49 #endif
  50 #if defined(LZO1Z)
  51         unsigned last_m_off = 0;
  52 #endif
  53
  54 //      LZO_UNUSED(wrkmem);
  55
  56 #if defined(COPY_DICT)
  57         if (dict) {
  58                 if (dict_len > M4_MAX_OFFSET) {
  59                         dict += dict_len - M4_MAX_OFFSET;
  60                         dict_len = M4_MAX_OFFSET;
  61                 }
  62                 dict_end = dict + dict_len;
  63         } else {
  64                 dict_len = 0;
  65                 dict_end = NULL;
  66         }
  67 #endif /* COPY_DICT */
  68
  69         *out_len = 0;
  70
  71         op = out;
  72         ip = in;
  73
  74         if (*ip > 17) {
  75                 t = *ip++ - 17;
  76                 if (t < 4)
  77                         goto match_next;
  78                 assert(t > 0); NEED_OP(t); NEED_IP(t+1);
  79                 do *op++ = *ip++; while (--t > 0);
  80                 goto first_literal_run;
  81         }
  82
  83         while (TEST_IP && TEST_OP) {
  84                 t = *ip++;
  85                 if (t >= 16)
  86                         goto match;
  87                 /* a literal run */
  88                 if (t == 0) {
  89                         NEED_IP(1);
  90                         while (*ip == 0) {
  91                                 t += 255;
  92                                 ip++;
  93                                 NEED_IP(1);
  94                         }
  95                         TEST_IV(t);
  96                         t += 15 + *ip++;
  97                 }
  98                 /* copy literals */
  99                 assert(t > 0);
 100                 NEED_OP(t+3);
 101                 NEED_IP(t+4);
 102 #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
 103 # if !defined(LZO_UNALIGNED_OK_4)
 104                 if (PTR_ALIGNED2_4(op, ip))
 105 # endif
 106                 {
 107                         COPY4(op, ip);
 108                         op += 4;
 109                         ip += 4;
 110                         if (--t > 0) {
 111                                 if (t >= 4) {
 112                                         do {
 113                                                 COPY4(op, ip);
 114                                                 op += 4;
 115                                                 ip += 4;
 116                                                 t -= 4;
 117                                         } while (t >= 4);
 118                                         if (t > 0)
 119                                                 do *op++ = *ip++; while (--t > 0);
 120                                 } else {
 121                                         do *op++ = *ip++; while (--t > 0);
 122                                 }
 123                         }
 124                 }
 125 # if !defined(LZO_UNALIGNED_OK_4)
 126                 else
 127 # endif
 128 #endif
 129 #if !defined(LZO_UNALIGNED_OK_4)
 130                 {
 131                         *op++ = *ip++;
 132                         *op++ = *ip++;
 133                         *op++ = *ip++;
 134                         do *op++ = *ip++; while (--t > 0);
 135                 }
 136 #endif
 137
 138  first_literal_run:
 139                 t = *ip++;
 140                 if (t >= 16)
 141                         goto match;
 142 #if defined(COPY_DICT)
 143 #if defined(LZO1Z)
 144                 m_off = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
 145                 last_m_off = m_off;
 146 #else
 147                 m_off = (1 + M2_MAX_OFFSET) + (t >> 2) + (*ip++ << 2);
 148 #endif
 149                 NEED_OP(3);
 150                 t = 3; COPY_DICT(t,m_off)
 151 #else /* !COPY_DICT */
 152 #if defined(LZO1Z)
 153                 t = (1 + M2_MAX_OFFSET) + (t << 6) + (*ip++ >> 2);
 154                 m_pos = op - t;
 155                 last_m_off = t;
 156 #else
 157                 m_pos = op - (1 + M2_MAX_OFFSET);
 158                 m_pos -= t >> 2;
 159                 m_pos -= *ip++ << 2;
 160 #endif
 161                 TEST_LB(m_pos); NEED_OP(3);
 162                 *op++ = *m_pos++;
 163                 *op++ = *m_pos++;
 164                 *op++ = *m_pos;
 165 #endif /* COPY_DICT */
 166                 goto match_done;
 167
 168                 /* handle matches */
 169                 do {
 170  match:
 171                         if (t >= 64) {          /* a M2 match */
 172 #if defined(COPY_DICT)
 173 #if defined(LZO1X)
 174                                 m_off = 1 + ((t >> 2) & 7) + (*ip++ << 3);
 175                                 t = (t >> 5) - 1;
 176 #elif defined(LZO1Y)
 177                                 m_off = 1 + ((t >> 2) & 3) + (*ip++ << 2);
 178                                 t = (t >> 4) - 3;
 179 #elif defined(LZO1Z)
 180                                 m_off = t & 0x1f;
 181                                 if (m_off >= 0x1c)
 182                                         m_off = last_m_off;
 183                                 else {
 184                                         m_off = 1 + (m_off << 6) + (*ip++ >> 2);
 185                                         last_m_off = m_off;
 186                                 }
 187                                 t = (t >> 5) - 1;
 188 #endif
 189 #else /* !COPY_DICT */
 190 #if defined(LZO1X)
 191                                 m_pos = op - 1;
 192                                 m_pos -= (t >> 2) & 7;
 193                                 m_pos -= *ip++ << 3;
 194                                 t = (t >> 5) - 1;
 195 #elif defined(LZO1Y)
 196                                 m_pos = op - 1;
 197                                 m_pos -= (t >> 2) & 3;
 198                                 m_pos -= *ip++ << 2;
 199                                 t = (t >> 4) - 3;
 200 #elif defined(LZO1Z)
 201                                 {
 202                                         unsigned off = t & 0x1f;
 203                                         m_pos = op;
 204                                         if (off >= 0x1c) {
 205                                                 assert(last_m_off > 0);
 206                                                 m_pos -= last_m_off;
 207                                         } else {
 208                                                 off = 1 + (off << 6) + (*ip++ >> 2);
 209                                                 m_pos -= off;
 210                                                 last_m_off = off;
 211                                         }
 212                                 }
 213                                 t = (t >> 5) - 1;
 214 #endif
 215                                 TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 216                                 goto copy_match;
 217 #endif /* COPY_DICT */
 218                         }
 219                         else if (t >= 32) {                     /* a M3 match */
 220                                 t &= 31;
 221                                 if (t == 0) {
 222                                         NEED_IP(1);
 223                                         while (*ip == 0) {
 224                                                 t += 255;
 225                                                 ip++;
 226                                                 NEED_IP(1);
 227                                         }
 228                                         TEST_IV(t);
 229                                         t += 31 + *ip++;
 230                                 }
 231 #if defined(COPY_DICT)
 232 #if defined(LZO1Z)
 233                                 m_off = 1 + (ip[0] << 6) + (ip[1] >> 2);
 234                                 last_m_off = m_off;
 235 #else
 236                                 m_off = 1 + (ip[0] >> 2) + (ip[1] << 6);
 237 #endif
 238 #else /* !COPY_DICT */
 239 #if defined(LZO1Z)
 240                                 {
 241                                         unsigned off = 1 + (ip[0] << 6) + (ip[1] >> 2);
 242                                         m_pos = op - off;
 243                                         last_m_off = off;
 244                                 }
 245 #elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 246                                 m_pos = op - 1;
 247                                 m_pos -= (* (const lzo_ushortp) ip) >> 2;
 248 #else
 249                                 m_pos = op - 1;
 250                                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
 251 #endif
 252 #endif /* COPY_DICT */
 253                                 ip += 2;
 254                         }
 255                         else if (t >= 16) {                     /* a M4 match */
 256 #if defined(COPY_DICT)
 257                                 m_off = (t & 8) << 11;
 258 #else /* !COPY_DICT */
 259                                 m_pos = op;
 260                                 m_pos -= (t & 8) << 11;
 261 #endif /* COPY_DICT */
 262                                 t &= 7;
 263                                 if (t == 0) {
 264                                         NEED_IP(1);
 265                                         while (*ip == 0) {
 266                                                 t += 255;
 267                                                 ip++;
 268                                                 NEED_IP(1);
 269                                         }
 270                                         TEST_IV(t);
 271                                         t += 7 + *ip++;
 272                                 }
 273 #if defined(COPY_DICT)
 274 #if defined(LZO1Z)
 275                                 m_off += (ip[0] << 6) + (ip[1] >> 2);
 276 #else
 277                                 m_off += (ip[0] >> 2) + (ip[1] << 6);
 278 #endif
 279                                 ip += 2;
 280                                 if (m_off == 0)
 281                                         goto eof_found;
 282                                 m_off += 0x4000;
 283 #if defined(LZO1Z)
 284                                 last_m_off = m_off;
 285 #endif
 286 #else /* !COPY_DICT */
 287 #if defined(LZO1Z)
 288                                 m_pos -= (ip[0] << 6) + (ip[1] >> 2);
 289 #elif defined(LZO_UNALIGNED_OK_2) && defined(LZO_ABI_LITTLE_ENDIAN)
 290                                 m_pos -= (* (const lzo_ushortp) ip) >> 2;
 291 #else
 292                                 m_pos -= (ip[0] >> 2) + (ip[1] << 6);
 293 #endif
 294                                 ip += 2;
 295                                 if (m_pos == op)
 296                                         goto eof_found;
 297                                 m_pos -= 0x4000;
 298 #if defined(LZO1Z)
 299                                 last_m_off = pd((const uint8_t*)op, m_pos);
 300 #endif
 301 #endif /* COPY_DICT */
 302                         }
 303                         else {                          /* a M1 match */
 304 #if defined(COPY_DICT)
 305 #if defined(LZO1Z)
 306                                 m_off = 1 + (t << 6) + (*ip++ >> 2);
 307                                 last_m_off = m_off;
 308 #else
 309                                 m_off = 1 + (t >> 2) + (*ip++ << 2);
 310 #endif
 311                                 NEED_OP(2);
 312                                 t = 2; COPY_DICT(t,m_off)
 313 #else /* !COPY_DICT */
 314 #if defined(LZO1Z)
 315                                 t = 1 + (t << 6) + (*ip++ >> 2);
 316                                 m_pos = op - t;
 317                                 last_m_off = t;
 318 #else
 319                                 m_pos = op - 1;
 320                                 m_pos -= t >> 2;
 321                                 m_pos -= *ip++ << 2;
 322 #endif
 323                                 TEST_LB(m_pos); NEED_OP(2);
 324                                 *op++ = *m_pos++;
 325                                 *op++ = *m_pos;
 326 #endif /* COPY_DICT */
 327                                 goto match_done;
 328                         }
 329
 330                         /* copy match */
 331 #if defined(COPY_DICT)
 332
 333                         NEED_OP(t+3-1);
 334                         t += 3-1; COPY_DICT(t,m_off)
 335
 336 #else /* !COPY_DICT */
 337
 338                         TEST_LB(m_pos); assert(t > 0); NEED_OP(t+3-1);
 339 #if defined(LZO_UNALIGNED_OK_4) || defined(LZO_ALIGNED_OK_4)
 340 # if !defined(LZO_UNALIGNED_OK_4)
 341                         if (t >= 2 * 4 - (3 - 1) && PTR_ALIGNED2_4(op,m_pos)) {
 342                                 assert((op - m_pos) >= 4);      /* both pointers are aligned */
 343 # else
 344                         if (t >= 2 * 4 - (3 - 1) && (op - m_pos) >= 4) {
 345 # endif
 346                                 COPY4(op,m_pos);
 347                                 op += 4; m_pos += 4; t -= 4 - (3 - 1);
 348                                 do {
 349                                         COPY4(op,m_pos);
 350                                         op += 4; m_pos += 4; t -= 4;
 351                                 } while (t >= 4);
 352                                 if (t > 0)
 353                                         do *op++ = *m_pos++; while (--t > 0);
 354                         }
 355                         else
 356 #endif
 357                         {
 358  copy_match:
 359                                 *op++ = *m_pos++; *op++ = *m_pos++;
 360                                 do *op++ = *m_pos++; while (--t > 0);
 361                         }
 362
 363 #endif /* COPY_DICT */
 364
 365  match_done:
 366 #if defined(LZO1Z)
 367                         t = ip[-1] & 3;
 368 #else
 369                         t = ip[-2] & 3;
 370 #endif
 371                         if (t == 0)
 372                                 break;
 373
 374                         /* copy literals */
 375  match_next:
 376                         assert(t > 0);
 377                         assert(t < 4);
 378                         NEED_OP(t);
 379                         NEED_IP(t+1);
 380 #if 0
 381                         do *op++ = *ip++; while (--t > 0);
 382 #else
 383                         *op++ = *ip++;
 384                         if (t > 1) {
 385                                 *op++ = *ip++;
 386                                 if (t > 2)
 387                                         *op++ = *ip++;
 388                         }
 389 #endif
 390                         t = *ip++;
 391                 } while (TEST_IP && TEST_OP);
 392         }
 393
 394 //#if defined(HAVE_TEST_IP) || defined(HAVE_TEST_OP)
 395         /* no EOF code was found */
 396         *out_len = pd(op, out);
 397         return LZO_E_EOF_NOT_FOUND;
 398 //#endif
 399
 400  eof_found:
 401         assert(t == 1);
 402         *out_len = pd(op, out);
 403         return (ip == ip_end ? LZO_E_OK :
 404                    (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 405
 406 //#if defined(HAVE_NEED_IP)
 407  input_overrun:
 408         *out_len = pd(op, out);
 409         return LZO_E_INPUT_OVERRUN;
 410 //#endif
 411
 412 //#if defined(HAVE_NEED_OP)
 413  output_overrun:
 414         *out_len = pd(op, out);
 415         return LZO_E_OUTPUT_OVERRUN;
 416 //#endif
 417
 418 //#if defined(LZO_TEST_OVERRUN_LOOKBEHIND)
 419  lookbehind_overrun:
 420         *out_len = pd(op, out);
 421         return LZO_E_LOOKBEHIND_OVERRUN;
 422 //#endif
 423 }