lzo/src/lzo1x_oo.ch

   1 /* lzo1x_oo.ch -- LZO1X compressed data optimizer
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   6    Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
   7    Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
   8    Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
   9    Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  10    Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  11    Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  12    Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  13    Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  14    Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  15    Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  16    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  17    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  18    All Rights Reserved.
  19
  20    The LZO library is free software; you can redistribute it and/or
  21    modify it under the terms of the GNU General Public License as
  22    published by the Free Software Foundation; either version 2 of
  23    the License, or (at your option) any later version.
  24
  25    The LZO library is distributed in the hope that it will be useful,
  26    but WITHOUT ANY WARRANTY; without even the implied warranty of
  27    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  28    GNU General Public License for more details.
  29
  30    You should have received a copy of the GNU General Public License
  31    along with the LZO library; see the file COPYING.
  32    If not, write to the Free Software Foundation, Inc.,
  33    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  34
  35    Markus F.X.J. Oberhumer
  36    <markus@oberhumer.com>
  37    http://www.oberhumer.com/opensource/lzo/
  38  */
  39
  40
  41 #define TEST_IP     (ip < ip_end)
  42 #define TEST_OP     (op <= op_end)
  43
  44 #define NO_LIT      LZO_UINT_MAX
  45
  46
  47 /***********************************************************************
  48 //
  49 ************************************************************************/
  50
  51 static void copy2(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)
  52 {
  53     assert(off > 0);
  54     ip[0] = m_pos[0];
  55     if (off == 1)
  56         ip[1] = m_pos[0];
  57     else
  58         ip[1] = m_pos[1];
  59 }
  60
  61
  62 static void copy3(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off)
  63 {
  64     assert(off > 0);
  65     ip[0] = m_pos[0];
  66     if (off == 1)
  67     {
  68         ip[2] = ip[1] = m_pos[0];
  69     }
  70     else if (off == 2)
  71     {
  72         ip[1] = m_pos[1];
  73         ip[2] = m_pos[0];
  74     }
  75     else
  76     {
  77         ip[1] = m_pos[1];
  78         ip[2] = m_pos[2];
  79     }
  80 }
  81
  82
  83 /***********************************************************************
  84 // optimize a block of data.
  85 ************************************************************************/
  86
  87 LZO_PUBLIC(int)
  88 DO_OPTIMIZE          (       lzo_bytep in , lzo_uint  in_len,
  89                              lzo_bytep out, lzo_uintp out_len,
  90                              lzo_voidp wrkmem )
  91 {
  92     lzo_bytep op;
  93     lzo_bytep ip;
  94     lzo_uint t;
  95     lzo_bytep m_pos;
  96     lzo_bytep const ip_end = in + in_len;
  97     lzo_bytep const op_end = out + *out_len;
  98     lzo_bytep litp = NULL;
  99     lzo_uint lit = 0;
 100     lzo_uint next_lit = NO_LIT;
 101     lzo_uint nl;
 102     unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0;
 103
 104     LZO_UNUSED(wrkmem);
 105
 106     *out_len = 0;
 107
 108     op = out;
 109     ip = in;
 110
 111     assert(in_len >= 3);
 112     if (*ip > 17)
 113     {
 114         t = *ip++ - 17;
 115         if (t < 4)
 116             goto match_next;
 117         goto first_literal_run;
 118     }
 119     assert(*ip < 16 || (*ip == 17 && in_len == 3));
 120
 121     while (TEST_IP && TEST_OP)
 122     {
 123         t = *ip++;
 124         if (t >= 16)
 125             goto match;
 126         /* a literal run */
 127         litp = ip - 1;
 128         if (t == 0)
 129         {
 130             t = 15;
 131             while (*ip == 0)
 132                 t += 255, ip++;
 133             t += *ip++;
 134         }
 135         lit = t + 3;
 136         /* copy literals */
 137 copy_literal_run:
 138         *op++ = *ip++; *op++ = *ip++; *op++ = *ip++;
 139 first_literal_run:
 140         do *op++ = *ip++; while (--t > 0);
 141
 142
 143         t = *ip++;
 144
 145         if (t >= 16)
 146             goto match;
 147 #if defined(LZO1X)
 148         m_pos = op - 1 - 0x800;
 149 #elif defined(LZO1Y)
 150         m_pos = op - 1 - 0x400;
 151 #endif
 152         m_pos -= t >> 2;
 153         m_pos -= *ip++ << 2;
 154         *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
 155         lit = 0;
 156         goto match_done;
 157
 158
 159         /* handle matches */
 160         do {
 161             if (t < 16)                     /* a M1 match */
 162             {
 163                 m_pos = op - 1;
 164                 m_pos -= t >> 2;
 165                 m_pos -= *ip++ << 2;
 166
 167                 if (litp == NULL)
 168                     goto copy_m1;
 169
 170                 /* assert that there was a match just before */
 171                 assert(lit >= 1 && lit <= 3);
 172                 assert(litp == ip - 2 - lit - 2);
 173                 assert((lzo_uint)(*litp & 3) == lit);
 174                 nl = ip[-2] & 3;
 175                 /* test if a match follows */
 176                 if (nl == 0 && lit == 1 && ip[0] >= 16)
 177                 {
 178                     next_lit = nl;
 179                     /* adjust length of previous short run */
 180                     lit += 2;
 181                     *litp = LZO_BYTE((*litp & ~3) | lit);
 182                     /* copy over the 2 literals that replace the match */
 183                     copy2(ip-2,m_pos,pd(op,m_pos));
 184                     o_m1_a++;
 185                 }
 186                 /* test if a literal run follows */
 187                 else if (nl == 0 && ip[0] < 16 && ip[0] != 0 &&
 188                          (lit + 2 + ip[0] < 16))
 189                 {
 190                     t = *ip++;
 191                     /* remove short run */
 192                     *litp &= ~3;
 193                     /* copy over the 2 literals that replace the match */
 194                     copy2(ip-3+1,m_pos,pd(op,m_pos));
 195                     /* move literals 1 byte ahead */
 196                     litp += 2;
 197                     if (lit > 0)
 198                         lzo_memmove(litp+1,litp,lit);
 199                     /* insert new length of long literal run */
 200                     lit += 2 + t + 3; assert(lit <= 18);
 201                     *litp = LZO_BYTE(lit - 3);
 202
 203                     o_m1_b++;
 204                     *op++ = *m_pos++; *op++ = *m_pos++;
 205                     goto copy_literal_run;
 206                 }
 207 copy_m1:
 208                 *op++ = *m_pos++; *op++ = *m_pos++;
 209             }
 210             else
 211             {
 212 match:
 213                 if (t >= 64)                /* a M2 match */
 214                 {
 215                     m_pos = op - 1;
 216 #if defined(LZO1X)
 217                     m_pos -= (t >> 2) & 7;
 218                     m_pos -= *ip++ << 3;
 219                     t = (t >> 5) - 1;
 220 #elif defined(LZO1Y)
 221                     m_pos -= (t >> 2) & 3;
 222                     m_pos -= *ip++ << 2;
 223                     t = (t >> 4) - 3;
 224 #endif
 225                     if (litp == NULL)
 226                         goto copy_m;
 227
 228                     nl = ip[-2] & 3;
 229                     /* test if in beetween two long literal runs */
 230                     if (t == 1 && lit > 3 && nl == 0 &&
 231                         ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
 232                     {
 233                         assert(*litp == lit - 3);
 234                         t = *ip++;
 235                         /* copy over the 3 literals that replace the match */
 236                         copy3(ip-1-2,m_pos,pd(op,m_pos));
 237                         /* set new length of previous literal run */
 238                         lit += 3 + t + 3; assert(lit <= 18);
 239                         *litp = LZO_BYTE(lit - 3);
 240                         o_m2++;
 241                         *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
 242                         goto copy_literal_run;
 243                     }
 244                 }
 245                 else
 246                 {
 247                     if (t >= 32)            /* a M3 match */
 248                     {
 249                         t &= 31;
 250                         if (t == 0)
 251                         {
 252                             t = 31;
 253                             while (*ip == 0)
 254                                 t += 255, ip++;
 255                             t += *ip++;
 256                         }
 257                         m_pos = op - 1;
 258                         m_pos -= *ip++ >> 2;
 259                         m_pos -= *ip++ << 6;
 260                     }
 261                     else                    /* a M4 match */
 262                     {
 263                         m_pos = op;
 264                         m_pos -= (t & 8) << 11;
 265                         t &= 7;
 266                         if (t == 0)
 267                         {
 268                             t = 7;
 269                             while (*ip == 0)
 270                                 t += 255, ip++;
 271                             t += *ip++;
 272                         }
 273                         m_pos -= *ip++ >> 2;
 274                         m_pos -= *ip++ << 6;
 275                         if (m_pos == op)
 276                             goto eof_found;
 277                         m_pos -= 0x4000;
 278                     }
 279                     if (litp == NULL)
 280                         goto copy_m;
 281
 282                     nl = ip[-2] & 3;
 283                     /* test if in beetween two matches */
 284                     if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16)
 285                     {
 286                         assert(litp == ip - 3 - lit - 2);
 287                         assert((lzo_uint)(*litp & 3) == lit);
 288                         next_lit = nl;
 289                         /* make a previous short run */
 290                         lit += 3;
 291                         *litp = LZO_BYTE((*litp & ~3) | lit);
 292                         /* copy over the 3 literals that replace the match */
 293                         copy3(ip-3,m_pos,pd(op,m_pos));
 294                         o_m3_a++;
 295                     }
 296                     /* test if a literal run follows */
 297                     else if (t == 1 && lit <= 3 && nl == 0 &&
 298                              ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16))
 299                     {
 300                         assert(litp == ip - 3 - lit - 2);
 301                         assert((lzo_uint)(*litp & 3) == lit);
 302                         t = *ip++;
 303                         /* remove short run */
 304                         *litp &= ~3;
 305                         /* copy over the 3 literals that replace the match */
 306                         copy3(ip-4+1,m_pos,pd(op,m_pos));
 307                         /* move literals 1 byte ahead */
 308                         litp += 2;
 309                         if (lit > 0)
 310                             lzo_memmove(litp+1,litp,lit);
 311                         /* insert new length of long literal run */
 312                         lit += 3 + t + 3; assert(lit <= 18);
 313                         *litp = LZO_BYTE(lit - 3);
 314
 315                         o_m3_b++;
 316                         *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++;
 317                         goto copy_literal_run;
 318                     }
 319                 }
 320 copy_m:
 321                 *op++ = *m_pos++; *op++ = *m_pos++;
 322                 do *op++ = *m_pos++; while (--t > 0);
 323             }
 324
 325 match_done:
 326             if (next_lit == NO_LIT)
 327             {
 328                 t = ip[-2] & 3;
 329                 lit = t;
 330                 litp = ip - 2;
 331             }
 332             else
 333                 t = next_lit;
 334             assert(t <= 3);
 335             next_lit = NO_LIT;
 336             if (t == 0)
 337                 break;
 338             /* copy literals */
 339 match_next:
 340             do *op++ = *ip++; while (--t > 0);
 341             t = *ip++;
 342         } while (TEST_IP && TEST_OP);
 343     }
 344
 345     /* no EOF code was found */
 346     *out_len = pd(op, out);
 347     return LZO_E_EOF_NOT_FOUND;
 348
 349 eof_found:
 350     assert(t == 1);
 351 #if 0
 352     printf("optimize: %5lu %5lu   %5lu   %5lu %5lu\n",
 353            o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b);
 354 #endif
 355     LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2);
 356     LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b);
 357     *out_len = pd(op, out);
 358     return (ip == ip_end ? LZO_E_OK :
 359            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 360 }
 361
 362
 363 /*
 364 vi:ts=4:et
 365 */
 366