release/src/router/lzo/src/lzo1.c

   1 /* lzo1.c -- implementation of the LZO1 algorithm
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 1996-2015 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 #include "lzo_conf.h"
  30 #include <lzo/lzo1.h>
  31
  32
  33 /***********************************************************************
  34 // The next two defines can be changed to customize LZO1.
  35 // The default version is LZO1-5/1.
  36 ************************************************************************/
  37
  38 /* run bits (3 - 5) - the compressor and the decompressor
  39  * must use the same value. */
  40 #if !defined(RBITS)
  41 #  define RBITS     5
  42 #endif
  43
  44 /* compression level (1 - 9) - this only affects the compressor.
  45  * 1 is fastest, 9 is best compression ratio */
  46 #if !defined(CLEVEL)
  47 #  define CLEVEL    1           /* fastest by default */
  48 #endif
  49
  50
  51 /* check configuration */
  52 #if (RBITS < 3 || RBITS > 5)
  53 #  error "invalid RBITS"
  54 #endif
  55 #if (CLEVEL < 1 || CLEVEL > 9)
  56 #  error "invalid CLEVEL"
  57 #endif
  58
  59
  60 /***********************************************************************
  61 // You should not have to change anything below this line.
  62 ************************************************************************/
  63
  64 /*
  65      Format of the marker byte
  66
  67
  68      76543210
  69      --------
  70      00000000   a long run (a 'R0' run) - there are short and long R0 runs
  71      000rrrrr   a short run with len r
  72      mmmooooo   a short match (len = 2+m, o = offset low bits)
  73      111ooooo   a long match (o = offset low bits)
  74 */
  75
  76
  77 #define RSIZE   (1 << RBITS)
  78 #define RMASK   (RSIZE - 1)
  79
  80 #define OBITS   RBITS               /* offset and run-length use same bits */
  81 #define OSIZE   (1 << OBITS)
  82 #define OMASK   (OSIZE - 1)
  83
  84 #define MBITS   (8 - OBITS)
  85 #define MSIZE   (1 << MBITS)
  86 #define MMASK   (MSIZE - 1)
  87
  88
  89 /* sanity checks */
  90 #if (OBITS < 3 || OBITS > 5)
  91 #  error "invalid OBITS"
  92 #endif
  93 #if (MBITS < 3 || MBITS > 5)
  94 #  error "invalid MBITS"
  95 #endif
  96
  97
  98 /***********************************************************************
  99 // some macros to improve readability
 100 ************************************************************************/
 101
 102 /* Minimum len of a match */
 103 #define MIN_MATCH           3
 104 #define THRESHOLD           (MIN_MATCH - 1)
 105
 106 /* Minimum len of match coded in 2 bytes */
 107 #define MIN_MATCH_SHORT     MIN_MATCH
 108
 109 /* Maximum len of match coded in 2 bytes */
 110 #define MAX_MATCH_SHORT     (THRESHOLD + (MSIZE - 2))
 111 /* MSIZE - 2: 0 is used to indicate runs,
 112  *            MSIZE-1 is used to indicate a long match */
 113
 114 /* Minimum len of match coded in 3 bytes */
 115 #define MIN_MATCH_LONG      (MAX_MATCH_SHORT + 1)
 116
 117 /* Maximum len of match coded in 3 bytes */
 118 #define MAX_MATCH_LONG      (MIN_MATCH_LONG + 255)
 119
 120 /* Maximum offset of a match */
 121 #define MAX_OFFSET          (1 << (8 + OBITS))
 122
 123
 124 /*
 125
 126 RBITS | MBITS  MIN  THR.  MSIZE  MAXS  MINL  MAXL   MAXO  R0MAX R0FAST
 127 ======+===============================================================
 128   3   |   5      3    2     32    32    33    288   2048    263   256
 129   4   |   4      3    2     16    16    17    272   4096    271   264
 130   5   |   3      3    2      8     8     9    264   8192    287   280
 131
 132  */
 133
 134
 135 /***********************************************************************
 136 // internal configuration
 137 // all of these affect compression only
 138 ************************************************************************/
 139
 140 /* choose the hashing strategy */
 141 #ifndef LZO_HASH
 142 #define LZO_HASH    LZO_HASH_LZO_INCREMENTAL_A
 143 #endif
 144 #define D_INDEX1(d,p)       d = DM(DMUL(0x21,DX2(p,5,5)) >> 5)
 145 #define D_INDEX2(d,p)       d = d ^ D_MASK
 146
 147 #define DBITS       (8 + RBITS)
 148 #include "lzo_dict.h"
 149 #define DVAL_LEN    DVAL_LOOKAHEAD
 150
 151
 152 /***********************************************************************
 153 // get algorithm info, return memory required for compression
 154 ************************************************************************/
 155
 156 LZO_EXTERN(lzo_uint) lzo1_info ( int *rbits, int *clevel );
 157
 158 LZO_PUBLIC(lzo_uint)
 159 lzo1_info ( int *rbits, int *clevel )
 160 {
 161     if (rbits)
 162         *rbits = RBITS;
 163     if (clevel)
 164         *clevel = CLEVEL;
 165     return D_SIZE * lzo_sizeof(lzo_bytep);
 166 }
 167
 168
 169 /***********************************************************************
 170 // decode a R0 literal run (a long run)
 171 ************************************************************************/
 172
 173 #define R0MIN   (RSIZE)             /* Minimum len of R0 run of literals */
 174 #define R0MAX   (R0MIN + 255)       /* Maximum len of R0 run of literals */
 175 #define R0FAST  (R0MAX & ~7u)       /* R0MAX aligned to 8 byte boundary */
 176
 177 #if (R0MAX - R0FAST != 7) || ((R0FAST & 7) != 0)
 178 #  error "something went wrong"
 179 #endif
 180
 181 /* 7 special codes from R0FAST+1 .. R0MAX
 182  * these codes mean long R0 runs with lengths
 183  * 512, 1024, 2048, 4096, 8192, 16384, 32768 */
 184
 185
 186 /***********************************************************************
 187 // LZO1 decompress a block of data.
 188 //
 189 // Could be easily translated into assembly code.
 190 ************************************************************************/
 191
 192 LZO_PUBLIC(int)
 193 lzo1_decompress  ( const lzo_bytep in , lzo_uint  in_len,
 194                          lzo_bytep out, lzo_uintp out_len,
 195                          lzo_voidp wrkmem )
 196 {
 197     lzo_bytep op;
 198     const lzo_bytep ip;
 199     const lzo_bytep const ip_end = in + in_len;
 200     lzo_uint t;
 201
 202     LZO_UNUSED(wrkmem);
 203
 204     op = out;
 205     ip = in;
 206     while (ip < ip_end)
 207     {
 208         t = *ip++;  /* get marker */
 209
 210         if (t < R0MIN)          /* a literal run */
 211         {
 212             if (t == 0)             /* a R0 literal run */
 213             {
 214                 t = *ip++;
 215                 if (t >= R0FAST - R0MIN)            /* a long R0 run */
 216                 {
 217                     t -= R0FAST - R0MIN;
 218                     if (t == 0)
 219                         t = R0FAST;
 220                     else
 221                     {
 222 #if 0
 223                         t = 256u << ((unsigned) t);
 224 #else
 225                         /* help the optimizer */
 226                         lzo_uint tt = 256;
 227                         do tt <<= 1; while (--t > 0);
 228                         t = tt;
 229 #endif
 230                     }
 231                     MEMCPY8_DS(op,ip,t);
 232                     continue;
 233                 }
 234                 t += R0MIN;
 235             }
 236             MEMCPY_DS(op,ip,t);
 237         }
 238         else                    /* a match */
 239         {
 240             lzo_uint tt;
 241             /* get match offset */
 242             const lzo_bytep m_pos = op - 1;
 243             m_pos -= (lzo_uint)(t & OMASK) | (((lzo_uint) *ip++) << OBITS);
 244
 245             /* get match len */
 246             if (t >= ((MSIZE - 1) << OBITS))                /* all m-bits set */
 247                 tt = (MIN_MATCH_LONG - THRESHOLD) + *ip++;  /* a long match */
 248             else
 249                 tt = t >> OBITS;                            /* a short match */
 250
 251             assert(m_pos >= out);
 252             assert(m_pos <  op);
 253             /* a half unrolled loop */
 254             *op++ = *m_pos++;
 255             *op++ = *m_pos++;
 256             MEMCPY_DS(op,m_pos,tt);
 257         }
 258     }
 259
 260     *out_len = pd(op, out);
 261
 262     /* the next line is the only check in the decompressor ! */
 263     return (ip == ip_end ? LZO_E_OK :
 264            (ip < ip_end  ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN));
 265 }
 266
 267
 268 /***********************************************************************
 269 // code a literal run
 270 ************************************************************************/
 271
 272 static
 273 #if LZO_ARCH_AVR
 274 __lzo_noinline
 275 #endif
 276 lzo_bytep
 277 store_run(lzo_bytep op, const lzo_bytep ii, lzo_uint r_len)
 278 {
 279     assert(r_len > 0);
 280
 281     /* code a long R0 run */
 282     if (r_len >= 512)
 283     {
 284         unsigned r_bits = 7;        /* 256 << 7 == 32768 */
 285         do {
 286             while (r_len >= (256u << r_bits))
 287             {
 288                 r_len -= (256u << r_bits);
 289                 *op++ = 0; *op++ = LZO_BYTE((R0FAST - R0MIN) + r_bits);
 290                 MEMCPY8_DS(op, ii, (256u << r_bits));
 291             }
 292         } while (--r_bits > 0);
 293     }
 294     while (r_len >= R0FAST)
 295     {
 296         r_len -= R0FAST;
 297         *op++ = 0; *op++ = R0FAST - R0MIN;
 298         MEMCPY8_DS(op, ii, R0FAST);
 299     }
 300
 301     if (r_len >= R0MIN)
 302     {
 303         /* code a short R0 run */
 304         *op++ = 0; *op++ = LZO_BYTE(r_len - R0MIN);
 305         MEMCPY_DS(op, ii, r_len);
 306     }
 307     else if (r_len > 0)
 308     {
 309         /* code a 'normal' run */
 310         *op++ = LZO_BYTE(r_len);
 311         MEMCPY_DS(op, ii, r_len);
 312     }
 313
 314     assert(r_len == 0);
 315     return op;
 316 }
 317
 318
 319
 320 /***********************************************************************
 321 // LZO1 compress a block of data.
 322 //
 323 // Could be translated into assembly code without too much effort.
 324 //
 325 // I apologize for the spaghetti code, but it really helps the optimizer.
 326 ************************************************************************/
 327
 328 static int
 329 do_compress    ( const lzo_bytep in , lzo_uint  in_len,
 330                        lzo_bytep out, lzo_uintp out_len,
 331                        lzo_voidp wrkmem )
 332 {
 333     const lzo_bytep ip;
 334 #if defined(__LZO_HASH_INCREMENTAL)
 335     lzo_xint dv;
 336 #endif
 337     lzo_bytep op;
 338     const lzo_bytep m_pos;
 339     const lzo_bytep const ip_end = in+in_len - DVAL_LEN - MIN_MATCH_LONG;
 340     const lzo_bytep const in_end = in+in_len - DVAL_LEN;
 341     const lzo_bytep ii;
 342     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
 343
 344 #if !defined(NDEBUG)
 345     const lzo_bytep m_pos_sav;
 346 #endif
 347
 348     op = out;
 349     ip = in;
 350     ii = ip;                /* point to start of literal run */
 351     if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1)
 352         goto the_end;
 353
 354     /* init dictionary */
 355 #if (LZO_DETERMINISTIC)
 356     BZERO8_PTR(wrkmem,sizeof(lzo_dict_t),D_SIZE);
 357 #endif
 358
 359     DVAL_FIRST(dv,ip);
 360     UPDATE_D(dict,0,dv,ip,in);
 361     ip++;
 362     DVAL_NEXT(dv,ip);
 363
 364     do {
 365         LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
 366         lzo_uint dindex;
 367
 368         DINDEX1(dindex,ip);
 369         GINDEX(m_pos,m_off,dict,dindex,in);
 370         if (LZO_CHECK_MPOS(m_pos,m_off,in,ip,MAX_OFFSET))
 371             goto literal;
 372         if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2])
 373             goto match;
 374         DINDEX2(dindex,ip);
 375         GINDEX(m_pos,m_off,dict,dindex,in);
 376         if (LZO_CHECK_MPOS(m_pos,m_off,in,ip,MAX_OFFSET))
 377             goto literal;
 378         if (m_pos[0] == ip[0] && m_pos[1] == ip[1] && m_pos[2] == ip[2])
 379             goto match;
 380         goto literal;
 381
 382
 383 literal:
 384         UPDATE_I(dict,0,dindex,ip,in);
 385         if (++ip >= ip_end)
 386             break;
 387         continue;
 388
 389 match:
 390         UPDATE_I(dict,0,dindex,ip,in);
 391 #if !defined(NDEBUG) && (LZO_DICT_USE_PTR)
 392         m_pos_sav = m_pos;
 393 #endif
 394         m_pos += 3;
 395         {
 396     /* we have found a match (of at least length 3) */
 397 #if !defined(NDEBUG) && !(LZO_DICT_USE_PTR)
 398             assert((m_pos_sav = ip - m_off) == (m_pos - 3));
 399 #endif
 400             /* 1) store the current literal run */
 401             if (pd(ip,ii) > 0)
 402             {
 403                 lzo_uint t = pd(ip,ii);
 404 #if 1
 405                 /* OPTIMIZED: inline the copying of a short run */
 406                 if (t < R0MIN)
 407                 {
 408                     *op++ = LZO_BYTE(t);
 409                     MEMCPY_DS(op, ii, t);
 410                 }
 411                 else
 412 #endif
 413                     op = store_run(op,ii,t);
 414             }
 415
 416             /* 2a) compute match len */
 417             ii = ip;        /* point to start of current match */
 418
 419             /* we already matched MIN_MATCH bytes,
 420              * m_pos also already advanced MIN_MATCH bytes */
 421             ip += MIN_MATCH;
 422             assert(m_pos < ip);
 423
 424             /* try to match another MIN_MATCH_LONG - MIN_MATCH bytes
 425              * to see if we get a long match */
 426
 427 #define PS  *m_pos++ != *ip++
 428
 429 #if (MIN_MATCH_LONG - MIN_MATCH == 2)                   /* MBITS == 2 */
 430             if (PS || PS)
 431 #elif (MIN_MATCH_LONG - MIN_MATCH == 6)                 /* MBITS == 3 */
 432             if (PS || PS || PS || PS || PS || PS)
 433 #elif (MIN_MATCH_LONG - MIN_MATCH == 14)                /* MBITS == 4 */
 434             if (PS || PS || PS || PS || PS || PS || PS ||
 435                 PS || PS || PS || PS || PS || PS || PS)
 436 #elif (MIN_MATCH_LONG - MIN_MATCH == 30)                /* MBITS == 5 */
 437             if (PS || PS || PS || PS || PS || PS || PS || PS ||
 438                 PS || PS || PS || PS || PS || PS || PS || PS ||
 439                 PS || PS || PS || PS || PS || PS || PS || PS ||
 440                 PS || PS || PS || PS || PS || PS)
 441 #else
 442 #  error "MBITS not yet implemented"
 443 #endif
 444             {
 445                 lzo_uint m_len;
 446
 447             /* 2b) code a short match */
 448                     assert(pd(ip,m_pos) == m_off);
 449                 --ip;   /* ran one too far, point back to non-match */
 450                 m_len = pd(ip, ii);
 451                     assert(m_len >= MIN_MATCH_SHORT);
 452                     assert(m_len <= MAX_MATCH_SHORT);
 453                     assert(m_off > 0);
 454                     assert(m_off <= MAX_OFFSET);
 455                     assert(ii-m_off == m_pos_sav);
 456                     assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
 457                 --m_off;
 458                 /* code short match len + low offset bits */
 459                 *op++ = LZO_BYTE(((m_len - THRESHOLD) << OBITS) |
 460                                  (m_off & OMASK));
 461                 /* code high offset bits */
 462                 *op++ = LZO_BYTE(m_off >> OBITS);
 463
 464
 465             /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
 466
 467 #define SI      /* nothing */
 468 #define DI      ++ii; DVAL_NEXT(dv,ii); UPDATE_D(dict,0,dv,ii,in);
 469 #define XI      assert(ii < ip); ii = ip; DVAL_FIRST(dv,(ip));
 470
 471 #if (CLEVEL == 9) || (CLEVEL >= 7 && MBITS <= 4) || (CLEVEL >= 5 && MBITS <= 3)
 472             /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
 473                 ++ii;
 474                 do {
 475                     DVAL_NEXT(dv,ii);
 476                     UPDATE_D(dict,0,dv,ii,in);
 477                 } while (++ii < ip);
 478                 DVAL_NEXT(dv,ii);
 479                 assert(ii == ip);
 480                 DVAL_ASSERT(dv,ip);
 481 #elif (CLEVEL >= 3)
 482                 SI   DI DI   XI
 483 #elif (CLEVEL >= 2)
 484                 SI   DI      XI
 485 #else
 486                              XI
 487 #endif
 488
 489             }
 490             else
 491             {
 492             /* we've found a long match - see how far we can still go */
 493                 const lzo_bytep end;
 494                 lzo_uint m_len;
 495
 496                 assert(ip <= in_end);
 497                 assert(ii == ip - MIN_MATCH_LONG);
 498
 499                 if (pd(in_end,ip) <= (MAX_MATCH_LONG - MIN_MATCH_LONG))
 500                     end = in_end;
 501                 else
 502                 {
 503                     end = ip + (MAX_MATCH_LONG - MIN_MATCH_LONG);
 504                     assert(end < in_end);
 505                 }
 506
 507                 while (ip < end  &&  *m_pos == *ip)
 508                     m_pos++, ip++;
 509                 assert(ip <= in_end);
 510
 511             /* 2b) code the long match */
 512                 m_len = pd(ip, ii);
 513                     assert(m_len >= MIN_MATCH_LONG);
 514                     assert(m_len <= MAX_MATCH_LONG);
 515                     assert(m_off > 0);
 516                     assert(m_off <= MAX_OFFSET);
 517                     assert(ii-m_off == m_pos_sav);
 518                     assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
 519                     assert(pd(ip,m_pos) == m_off);
 520                 --m_off;
 521                 /* code long match flag + low offset bits */
 522                 *op++ = LZO_BYTE(((MSIZE - 1) << OBITS) | (m_off & OMASK));
 523                 /* code high offset bits */
 524                 *op++ = LZO_BYTE(m_off >> OBITS);
 525                 /* code match len */
 526                 *op++ = LZO_BYTE(m_len - MIN_MATCH_LONG);
 527
 528
 529             /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
 530 #if (CLEVEL == 9)
 531             /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
 532             /* This is not recommended because it is slow. */
 533                 ++ii;
 534                 do {
 535                     DVAL_NEXT(dv,ii);
 536                     UPDATE_D(dict,0,dv,ii,in);
 537                 } while (++ii < ip);
 538                 DVAL_NEXT(dv,ii);
 539                 assert(ii == ip);
 540                 DVAL_ASSERT(dv,ip);
 541 #elif (CLEVEL >= 8)
 542                 SI   DI DI DI DI DI DI DI DI   XI
 543 #elif (CLEVEL >= 7)
 544                 SI   DI DI DI DI DI DI DI      XI
 545 #elif (CLEVEL >= 6)
 546                 SI   DI DI DI DI DI DI         XI
 547 #elif (CLEVEL >= 5)
 548                 SI   DI DI DI DI               XI
 549 #elif (CLEVEL >= 4)
 550                 SI   DI DI DI                  XI
 551 #elif (CLEVEL >= 3)
 552                 SI   DI DI                     XI
 553 #elif (CLEVEL >= 2)
 554                 SI   DI                        XI
 555 #else
 556                                                XI
 557 #endif
 558             }
 559
 560             /* ii now points to the start of next literal run */
 561             assert(ii == ip);
 562         }
 563     } while (ip < ip_end);
 564
 565
 566
 567 the_end:
 568     assert(ip <= in_end);
 569
 570
 571 #if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
 572     /* return -1 if op == out to indicate that we
 573      * couldn't compress and didn't copy anything.
 574      */
 575     if (op == out)
 576     {
 577         *out_len = 0;
 578         return LZO_E_NOT_COMPRESSIBLE;
 579     }
 580 #endif
 581
 582
 583     /* store the final literal run */
 584     if (pd(in_end+DVAL_LEN,ii) > 0)
 585         op = store_run(op,ii,pd(in_end+DVAL_LEN,ii));
 586
 587     *out_len = pd(op, out);
 588     return 0;               /* compression went ok */
 589 }
 590
 591
 592 /***********************************************************************
 593 // compress public entry point.
 594 ************************************************************************/
 595
 596 LZO_PUBLIC(int)
 597 lzo1_compress ( const lzo_bytep in , lzo_uint  in_len,
 598                       lzo_bytep out, lzo_uintp out_len,
 599                       lzo_voidp wrkmem )
 600 {
 601     int r = LZO_E_OK;
 602
 603     /* don't try to compress a block that's too short */
 604     if (in_len == 0)
 605         *out_len = 0;
 606     else if (in_len <= MIN_MATCH_LONG + DVAL_LEN + 1)
 607     {
 608 #if defined(LZO_RETURN_IF_NOT_COMPRESSIBLE)
 609         r = LZO_E_NOT_COMPRESSIBLE;
 610 #else
 611         *out_len = pd(store_run(out,in,in_len), out);
 612 #endif
 613     }
 614     else
 615         r = do_compress(in,in_len,out,out_len,wrkmem);
 616
 617     return r;
 618 }
 619
 620
 621 /* vim:set ts=4 sw=4 et: */