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