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