release/src/router/lzo/src/lzo1x_c.ch

   1 /* lzo1x_c.ch -- implementation of the LZO1[XY]-1 compression algorithm
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 2011 Markus Franz Xaver Johannes Oberhumer
   6    Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer
   7    Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer
   8    Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   9    Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
  10    Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
  11    Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
  12    Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  13    Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  14    Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  15    Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  16    Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  17    Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  18    Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  19    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  20    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  21    All Rights Reserved.
  22
  23    The LZO library is free software; you can redistribute it and/or
  24    modify it under the terms of the GNU General Public License as
  25    published by the Free Software Foundation; either version 2 of
  26    the License, or (at your option) any later version.
  27
  28    The LZO library is distributed in the hope that it will be useful,
  29    but WITHOUT ANY WARRANTY; without even the implied warranty of
  30    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31    GNU General Public License for more details.
  32
  33    You should have received a copy of the GNU General Public License
  34    along with the LZO library; see the file COPYING.
  35    If not, write to the Free Software Foundation, Inc.,
  36    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  37
  38    Markus F.X.J. Oberhumer
  39    <markus@oberhumer.com>
  40    http://www.oberhumer.com/opensource/lzo/
  41  */
  42
  43
  44
  45 #if 1 && defined(DO_COMPRESS) && !defined(do_compress)
  46    /* choose a unique name to better help PGO optimizations */
  47 #  define do_compress       LZO_CPP_ECONCAT2(DO_COMPRESS,_core)
  48 #endif
  49
  50 #if defined(UA_GET64) && (LZO_ABI_BIG_ENDIAN)
  51 #  define WANT_lzo_bitops_clz64 1
  52 #elif defined(UA_GET64) && (LZO_ABI_LITTLE_ENDIAN)
  53 #  define WANT_lzo_bitops_ctz64 1
  54 #elif defined(UA_GET32) && (LZO_ABI_BIG_ENDIAN)
  55 #  define WANT_lzo_bitops_clz32 1
  56 #elif defined(UA_GET32) && (LZO_ABI_LITTLE_ENDIAN)
  57 #  define WANT_lzo_bitops_ctz32 1
  58 #endif
  59 #include "lzo_func.ch"
  60
  61
  62 /***********************************************************************
  63 // compress a block of data.
  64 ************************************************************************/
  65
  66 static __lzo_noinline lzo_uint
  67 do_compress ( const lzo_bytep in , lzo_uint  in_len,
  68                     lzo_bytep out, lzo_uintp out_len,
  69                     lzo_uint  ti,  lzo_voidp wrkmem)
  70 {
  71     register const lzo_bytep ip;
  72     lzo_bytep op;
  73     const lzo_bytep const in_end = in + in_len;
  74     const lzo_bytep const ip_end = in + in_len - 20;
  75     const lzo_bytep ii;
  76     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
  77
  78     op = out;
  79     ip = in;
  80     ii = ip;
  81
  82     ip += ti < 4 ? 4 - ti : 0;
  83     for (;;)
  84     {
  85         const lzo_bytep m_pos;
  86 #if !(LZO_DETERMINISTIC)
  87         LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
  88         lzo_uint m_len;
  89         lzo_uint dindex;
  90 next:
  91         if __lzo_unlikely(ip >= ip_end)
  92             break;
  93         DINDEX1(dindex,ip);
  94         GINDEX(m_pos,m_off,dict,dindex,in);
  95         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
  96             goto literal;
  97 #if 1
  98         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  99             goto try_match;
 100         DINDEX2(dindex,ip);
 101 #endif
 102         GINDEX(m_pos,m_off,dict,dindex,in);
 103         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
 104             goto literal;
 105         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
 106             goto try_match;
 107         goto literal;
 108
 109 try_match:
 110 #if defined(UA_GET32)
 111         if (UA_GET32(m_pos) != UA_GET32(ip))
 112 #else
 113         if (m_pos[0] != ip[0] || m_pos[1] != ip[1] || m_pos[2] != ip[2] || m_pos[3] != ip[3])
 114 #endif
 115         {
 116             /* a literal */
 117 literal:
 118             UPDATE_I(dict,0,dindex,ip,in);
 119             ip += 1 + ((ip - ii) >> 5);
 120             continue;
 121         }
 122 /*match:*/
 123         UPDATE_I(dict,0,dindex,ip,in);
 124 #else
 125         lzo_uint m_off;
 126         lzo_uint m_len;
 127         {
 128         lzo_uint32 dv;
 129         lzo_uint dindex;
 130 literal:
 131         ip += 1 + ((ip - ii) >> 5);
 132 next:
 133         if __lzo_unlikely(ip >= ip_end)
 134             break;
 135         dv = UA_GET32(ip);
 136         dindex = DINDEX(dv,ip);
 137         GINDEX(m_off,m_pos,in+dict,dindex,in);
 138         UPDATE_I(dict,0,dindex,ip,in);
 139         if __lzo_unlikely(dv != UA_GET32(m_pos))
 140             goto literal;
 141         }
 142 #endif
 143
 144     /* a match */
 145
 146         ii -= ti; ti = 0;
 147         {
 148         register lzo_uint t = pd(ip,ii);
 149         if (t != 0)
 150         {
 151             if (t <= 3)
 152             {
 153                 op[-2] |= LZO_BYTE(t);
 154 #if defined(UA_COPY32)
 155                 UA_COPY32(op, ii);
 156                 op += t;
 157 #else
 158                 { do *op++ = *ii++; while (--t > 0); }
 159 #endif
 160             }
 161 #if defined(UA_COPY32) || defined(UA_COPY64)
 162             else if (t <= 16)
 163             {
 164                 *op++ = LZO_BYTE(t - 3);
 165 #if defined(UA_COPY64)
 166                 UA_COPY64(op, ii);
 167                 UA_COPY64(op+8, ii+8);
 168 #else
 169                 UA_COPY32(op, ii);
 170                 UA_COPY32(op+4, ii+4);
 171                 UA_COPY32(op+8, ii+8);
 172                 UA_COPY32(op+12, ii+12);
 173 #endif
 174                 op += t;
 175             }
 176 #endif
 177             else
 178             {
 179                 if (t <= 18)
 180                     *op++ = LZO_BYTE(t - 3);
 181                 else
 182                 {
 183                     register lzo_uint tt = t - 18;
 184                     *op++ = 0;
 185                     while __lzo_unlikely(tt > 255)
 186                     {
 187                         tt -= 255;
 188 #if 1 && (LZO_CC_MSC && (_MSC_VER >= 1400))
 189                         * (volatile unsigned char *) op++ = 0;
 190 #else
 191                         *op++ = 0;
 192 #endif
 193                     }
 194                     assert(tt > 0);
 195                     *op++ = LZO_BYTE(tt);
 196                 }
 197 #if defined(UA_COPY32) || defined(UA_COPY64)
 198                 do {
 199 #if defined(UA_COPY64)
 200                     UA_COPY64(op, ii);
 201                     UA_COPY64(op+8, ii+8);
 202 #else
 203                     UA_COPY32(op, ii);
 204                     UA_COPY32(op+4, ii+4);
 205                     UA_COPY32(op+8, ii+8);
 206                     UA_COPY32(op+12, ii+12);
 207 #endif
 208                     op += 16; ii += 16; t -= 16;
 209                 } while (t >= 16); if (t > 0)
 210 #endif
 211                 { do *op++ = *ii++; while (--t > 0); }
 212             }
 213         }
 214         }
 215         m_len = 4;
 216         {
 217 #if defined(UA_GET64)
 218         lzo_uint64 v;
 219         v = UA_GET64(ip + m_len) ^ UA_GET64(m_pos + m_len);
 220         if __lzo_unlikely(v == 0) {
 221             do {
 222                 m_len += 8;
 223                 v = UA_GET64(ip + m_len) ^ UA_GET64(m_pos + m_len);
 224                 if __lzo_unlikely(ip + m_len >= ip_end)
 225                     goto m_len_done;
 226             } while (v == 0);
 227         }
 228 #if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_clz64)
 229         m_len += lzo_bitops_clz64(v) / CHAR_BIT;
 230 #elif (LZO_ABI_BIG_ENDIAN)
 231         if ((v >> (64 - CHAR_BIT)) == 0) do {
 232             v <<= CHAR_BIT;
 233             m_len += 1;
 234         } while ((v >> (64 - CHAR_BIT)) == 0);
 235 #elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_ctz64)
 236         m_len += lzo_bitops_ctz64(v) / CHAR_BIT;
 237 #elif (LZO_ABI_LITTLE_ENDIAN)
 238         if ((v & UCHAR_MAX) == 0) do {
 239             v >>= CHAR_BIT;
 240             m_len += 1;
 241         } while ((v & UCHAR_MAX) == 0);
 242 #else
 243         if (ip[m_len] == m_pos[m_len]) do {
 244             m_len += 1;
 245         } while (ip[m_len] == m_pos[m_len]);
 246 #endif
 247 #elif defined(UA_GET32)
 248         lzo_uint32 v;
 249         v = UA_GET32(ip + m_len) ^ UA_GET32(m_pos + m_len);
 250         if __lzo_unlikely(v == 0) {
 251             do {
 252                 m_len += 4;
 253                 v = UA_GET32(ip + m_len) ^ UA_GET32(m_pos + m_len);
 254                 if __lzo_unlikely(ip + m_len >= ip_end)
 255                     goto m_len_done;
 256             } while (v == 0);
 257         }
 258 #if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_clz32)
 259         m_len += lzo_bitops_clz32(v) / CHAR_BIT;
 260 #elif (LZO_ABI_BIG_ENDIAN)
 261         if ((v >> (32 - CHAR_BIT)) == 0) do {
 262             v <<= CHAR_BIT;
 263             m_len += 1;
 264         } while ((v >> (32 - CHAR_BIT)) == 0);
 265 #elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_ctz32)
 266         m_len += lzo_bitops_ctz32(v) / CHAR_BIT;
 267 #elif (LZO_ABI_LITTLE_ENDIAN)
 268         if ((v & UCHAR_MAX) == 0) do {
 269             v >>= CHAR_BIT;
 270             m_len += 1;
 271         } while ((v & UCHAR_MAX) == 0);
 272 #else
 273         if (ip[m_len] == m_pos[m_len]) do {
 274             m_len += 1;
 275         } while (ip[m_len] == m_pos[m_len]);
 276 #endif
 277 #else
 278         if __lzo_unlikely(ip[m_len] == m_pos[m_len]) {
 279             do {
 280                 m_len += 1;
 281                 if __lzo_unlikely(ip + m_len >= ip_end)
 282                     goto m_len_done;
 283             } while (ip[m_len] == m_pos[m_len]);
 284         }
 285 #endif
 286         }
 287 m_len_done:
 288         m_off = pd(ip,m_pos);
 289         ip += m_len;
 290         ii = ip;
 291         if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
 292         {
 293             m_off -= 1;
 294 #if defined(LZO1X)
 295             *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
 296             *op++ = LZO_BYTE(m_off >> 3);
 297 #elif defined(LZO1Y)
 298             *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
 299             *op++ = LZO_BYTE(m_off >> 2);
 300 #endif
 301         }
 302         else if (m_off <= M3_MAX_OFFSET)
 303         {
 304             m_off -= 1;
 305             if (m_len <= M3_MAX_LEN)
 306                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 307             else
 308             {
 309                 m_len -= M3_MAX_LEN;
 310                 *op++ = M3_MARKER | 0;
 311                 while __lzo_unlikely(m_len > 255)
 312                 {
 313                     m_len -= 255;
 314 #if 1 && (LZO_CC_MSC && (_MSC_VER >= 1400))
 315                     * (volatile unsigned char *) op++ = 0;
 316 #else
 317                     *op++ = 0;
 318 #endif
 319                 }
 320                 *op++ = LZO_BYTE(m_len);
 321             }
 322             *op++ = LZO_BYTE(m_off << 2);
 323             *op++ = LZO_BYTE(m_off >> 6);
 324         }
 325         else
 326         {
 327             m_off -= 0x4000;
 328             if (m_len <= M4_MAX_LEN)
 329                 *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8) | (m_len - 2));
 330             else
 331             {
 332                 m_len -= M4_MAX_LEN;
 333                 *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8));
 334                 while __lzo_unlikely(m_len > 255)
 335                 {
 336                     m_len -= 255;
 337 #if 1 && (LZO_CC_MSC && (_MSC_VER >= 1400))
 338                     * (volatile unsigned char *) op++ = 0;
 339 #else
 340                     *op++ = 0;
 341 #endif
 342                 }
 343                 *op++ = LZO_BYTE(m_len);
 344             }
 345             *op++ = LZO_BYTE(m_off << 2);
 346             *op++ = LZO_BYTE(m_off >> 6);
 347         }
 348         goto next;
 349     }
 350
 351     *out_len = pd(op, out);
 352     return pd(in_end,ii-ti);
 353 }
 354
 355
 356 /***********************************************************************
 357 // public entry point
 358 ************************************************************************/
 359
 360 LZO_PUBLIC(int)
 361 DO_COMPRESS      ( const lzo_bytep in , lzo_uint  in_len,
 362                          lzo_bytep out, lzo_uintp out_len,
 363                          lzo_voidp wrkmem )
 364 {
 365     const lzo_bytep ip = in;
 366     lzo_bytep op = out;
 367     lzo_uint l = in_len;
 368     lzo_uint t = 0;
 369
 370     while (l > 20)
 371     {
 372         lzo_uint ll = l;
 373         lzo_uintptr_t ll_end;
 374 #if 0 || (LZO_DETERMINISTIC)
 375         ll = LZO_MIN(ll, 49152);
 376 #endif
 377         ll_end = (lzo_uintptr_t)ip + ll;
 378         if ((ll_end + ((t + ll) >> 5)) <= ll_end || (const lzo_bytep)(ll_end + ((t + ll) >> 5)) <= ip + ll)
 379             break;
 380 #if (LZO_DETERMINISTIC)
 381         lzo_memset(wrkmem, 0, ((lzo_uint)1 << D_BITS) * sizeof(lzo_dict_t));
 382 #endif
 383         t = do_compress(ip,ll,op,out_len,t,wrkmem);
 384         ip += ll;
 385         op += *out_len;
 386         l  -= ll;
 387     }
 388     t += l;
 389
 390     if (t > 0)
 391     {
 392         const lzo_bytep ii = in + in_len - t;
 393
 394         if (op == out && t <= 238)
 395             *op++ = LZO_BYTE(17 + t);
 396         else if (t <= 3)
 397             op[-2] |= LZO_BYTE(t);
 398         else if (t <= 18)
 399             *op++ = LZO_BYTE(t - 3);
 400         else
 401         {
 402             lzo_uint tt = t - 18;
 403
 404             *op++ = 0;
 405             while (tt > 255)
 406             {
 407                 tt -= 255;
 408 #if 1 && (LZO_CC_MSC && (_MSC_VER >= 1400))
 409                 /* prevent the compiler from transforming this loop
 410                  * into a memset() call */
 411                 * (volatile unsigned char *) op++ = 0;
 412 #else
 413                 *op++ = 0;
 414 #endif
 415             }
 416             assert(tt > 0);
 417             *op++ = LZO_BYTE(tt);
 418         }
 419         do *op++ = *ii++; while (--t > 0);
 420     }
 421
 422     *op++ = M4_MARKER | 1;
 423     *op++ = 0;
 424     *op++ = 0;
 425
 426     *out_len = pd(op, out);
 427     return LZO_E_OK;
 428 }
 429
 430
 431 /*
 432 vi:ts=4:et
 433 */