tools/fastlz.c

   1
   2 #include <stdlib.h>
   3 #include <stdio.h>
   4 #include <string.h>
   5 #include <assert.h>
   6 #include <time.h>
   7
   8 #define BLOCK_SIZE 65536
   9
  10 /*
  11    The format is tailored for fast decompression (i.e. only byte based),
  12    and skewed to ASCII content (highest bit often not set):
  13
  14    a 0LLLLLLL
  15         - self-describing ASCII character hex L
  16    b 100lllll <l+1 bytes>
  17         - literal run of length l+1
  18    c 101oolll <8o>
  19         - back ref of length l+2, at offset -(o+1) (o < 1 << 10)
  20    d 110lllll <8o>
  21         - back ref of length l+2+8, at offset -(o+1) (o < 1 << 8)
  22    e 1110llll <8o> <8o>
  23         - back ref of length l+2, at offset -(o+1) (o < 1 << 16)
  24    f 1111llll <8o> <8o> <8l>
  25         - back ref, length l+18 (l < 1<<12), offset -(o+1) (o < 1<<16)
  26
  27    Generally for a literal of length L we need L+1 bytes, hence it is
  28    better to encode also very short backrefs (2 chars) as backrefs if
  29    their offset is small, as that only needs two bytes.  Except if we
  30    already have a literal run, in that case it's better to append there,
  31    instead of breaking it for a backref.  So given a potential backref
  32    at offset O, length L the strategy is as follows:
  33
  34    L < 2 : encode as 1-literal
  35    L == 2, O > 1024 : encode as 1-literal
  36    L == 2, have already literals: encode as 1-literal
  37    O = O - 1
  38    L >= 2, L <= 9, O < 1024                            : encode as c
  39    L >= 10, L <= 41, O < 256                           : encode as d
  40    else we have either O >= 1024, or L >= 42:
  41    L >= 2, L <= 17, O < 65536                          : encode as e
  42    L >= 18, L <= 4095+18, O < 65536                    : encode as f
  43    else we have either L >= 4096+18 or O >= 65536.
  44    O >= 65536: encode as 1-literal, too bad
  45      (with the current block size this can't happen)
  46    L >= 4096+18, so reduce to 4095+18                  : encode as f
  47 */
  48
  49
  50 static unsigned int
  51 compress_buf (const unsigned char *in, unsigned int in_len,
  52               unsigned char *out, unsigned int out_len)
  53 {
  54   unsigned int oo = 0;          //out-offset
  55   unsigned int io = 0;          //in-offset
  56 #define HS (65536)
  57   unsigned short htab[HS];
  58   unsigned short hnext[BLOCK_SIZE];
  59   memset (htab, 0, sizeof (htab));
  60   memset (hnext, 0, sizeof (hnext));
  61   unsigned int litofs = 0;
  62   while (io + 2 < in_len)
  63     {
  64       /* Search for a match of the string starting at IN, we have at
  65          least three characters.  */
  66       unsigned int hval = in[io] | in[io + 1] << 8 | in[io + 2] << 16;
  67       unsigned int try, mlen, mofs, tries;
  68       hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
  69       hval = hval & (HS - 1);
  70       try = htab[hval];
  71       hnext[io] = htab[hval];
  72       htab[hval] = io;
  73       mlen = 0;
  74       mofs = 0;
  75       for (tries = 0; tries < 4; tries++)
  76         {
  77           unsigned int this_len, this_ofs;
  78           this_len = 0;
  79           this_ofs = 0;
  80           if (try < io)
  81             {
  82               for (;
  83                    io + this_len < in_len
  84                    && in[try + this_len] == in[io + this_len]; this_len++)
  85                 ;
  86               this_ofs = (io - try) - 1;
  87               if (this_len < 2)
  88                 this_len = 0;
  89               else if (this_len == 2 && (litofs || ((io - try) - 1) >= 1024))
  90                 this_len = 0;
  91               else if (this_len >= 4096 + 18)
  92                 this_len = 4095 + 18;
  93               else if (this_ofs >= 65536)
  94                 this_len = 0;
  95               if (this_len > mlen || (this_len == mlen && this_ofs < mofs))
  96                 mlen = this_len, mofs = this_ofs;
  97             }
  98           try = hnext[try];
  99         }
 100       if (!mlen)
 101         {
 102           if (!litofs)
 103             litofs = io + 1;
 104           io++;
 105         }
 106       else
 107         {
 108           if (litofs)
 109             {
 110               litofs--;
 111               unsigned litlen = io - litofs;
 112               //fprintf (stderr, "lit: %d\n", litlen);
 113               while (litlen)
 114                 {
 115                   if (litlen == 1 && in[litofs] < 0x80)
 116                     {
 117                       if (oo + 1 >= out_len)
 118                         return 0;
 119                       out[oo++] = in[litofs++];
 120                       break;
 121                     }
 122                   else if (litlen == 2 && in[litofs] < 0x80
 123                            && in[litofs + 1] < 0x80)
 124                     {
 125                       if (oo + 2 >= out_len)
 126                         return 0;
 127                       out[oo++] = in[litofs++];
 128                       out[oo++] = in[litofs++];
 129                       break;
 130                     }
 131                   else if (litlen <= 32)
 132                     {
 133                       if (oo + 1 + litlen >= out_len)
 134                         return 0;
 135                       out[oo++] = 0x80 | (litlen - 1);
 136                       while (litlen--)
 137                         out[oo++] = in[litofs++];
 138                       break;
 139                     }
 140                   else
 141                     {
 142                       /* Literal length > 32, so chunk it.  */
 143                       if (oo + 1 + 32 >= out_len)
 144                         return 0;
 145                       out[oo++] = 0x80 | 31;
 146                       memcpy (out + oo, in + litofs, 32);
 147                       oo += 32;
 148                       litofs += 32;
 149                       litlen -= 32;
 150                     }
 151                 }
 152               litofs = 0;
 153             }
 154
 155           //fprintf (stderr, "ref: %d @ %d\n", mlen, mofs);
 156
 157           if (mlen >= 2 && mlen <= 9 && mofs < 1024)
 158             {
 159               if (oo + 2 >= out_len)
 160                 return 0;
 161               out[oo++] = 0xa0 | ((mofs & 0x300) >> 5) | (mlen - 2);
 162               out[oo++] = mofs & 0xff;
 163             }
 164           else if (mlen >= 10 && mlen <= 41 && mofs < 256)
 165             {
 166               if (oo + 2 >= out_len)
 167                 return 0;
 168               out[oo++] = 0xc0 | (mlen - 10);
 169               out[oo++] = mofs;
 170             }
 171           else if (mlen >= 2 && mlen <= 17)
 172             {
 173               assert (mofs < 65536);
 174               if (oo + 3 >= out_len)
 175                 return 0;
 176               out[oo++] = 0xe0 | (mlen - 2);
 177               out[oo++] = mofs >> 8;
 178               out[oo++] = mofs & 0xff;
 179             }
 180           else
 181             {
 182               assert (mlen >= 18 && mlen <= 4095 + 18 && mofs < 65536);
 183               if (oo + 4 >= out_len)
 184                 return 0;
 185               out[oo++] = 0xf0 | ((mlen - 18) >> 8);
 186               out[oo++] = mofs >> 8;
 187               out[oo++] = mofs & 0xff;
 188               out[oo++] = (mlen - 18) & 0xff;
 189             }
 190           /* Insert the hashes for the compressed run [io..io+mlen-1].
 191              For [io] we have it already done at the start of the loop.
 192              So it's from [io+1..io+mlen-1], and we need three chars per
 193              hash, so the accessed characters will be [io+1..io+mlen-1+2],
 194              ergo io+mlen+1 < in_len.  */
 195           mlen--;
 196           io++;
 197           while (mlen--)
 198             {
 199               if (io + 2 < in_len)
 200                 {
 201                   unsigned int hval =
 202                     in[io] | in[io + 1] << 8 | in[io + 2] << 16;
 203                   hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
 204                   hval = hval & (HS - 1);
 205                   hnext[io] = htab[hval];
 206                   htab[hval] = io;
 207                 }
 208               io++;
 209             };
 210         }
 211     }
 212   /* We might have some characters left.  */
 213   if (io < in_len && !litofs)
 214     litofs = io + 1;
 215   io = in_len;
 216   if (litofs)
 217     {
 218       litofs--;
 219       unsigned litlen = io - litofs;
 220       //fprintf (stderr, "lit: %d\n", litlen);
 221       while (litlen)
 222         {
 223           if (litlen == 1 && in[litofs] < 0x80)
 224             {
 225               if (oo + 1 >= out_len)
 226                 return 0;
 227               out[oo++] = in[litofs++];
 228               break;
 229             }
 230           else if (litlen == 2 && in[litofs] < 0x80 && in[litofs + 1] < 0x80)
 231             {
 232               if (oo + 2 >= out_len)
 233                 return 0;
 234               out[oo++] = in[litofs++];
 235               out[oo++] = in[litofs++];
 236               break;
 237             }
 238           else if (litlen <= 32)
 239             {
 240               if (oo + 1 + litlen >= out_len)
 241                 return 0;
 242               out[oo++] = 0x80 | (litlen - 1);
 243               while (litlen--)
 244                 out[oo++] = in[litofs++];
 245               break;
 246             }
 247           else
 248             {
 249               /* Literal length > 32, so chunk it.  */
 250               if (oo + 1 + 32 >= out_len)
 251                 return 0;
 252               out[oo++] = 0x80 | 31;
 253               memcpy (out + oo, in + litofs, 32);
 254               oo += 32;
 255               litofs += 32;
 256               litlen -= 32;
 257             }
 258         }
 259       litofs = 0;
 260     }
 261   return oo;
 262 }
 263
 264 static unsigned int
 265 unchecked_decompress_buf (const unsigned char *in, unsigned int in_len,
 266                           unsigned char *out,
 267                           unsigned int out_len __attribute__((unused)))
 268 {
 269   unsigned char *orig_out = out;
 270   const unsigned char *in_end = in + in_len;
 271   while (in < in_end)
 272     {
 273       unsigned int first = *in++;
 274       unsigned int o = o;
 275       switch (first >> 5)
 276         {
 277         case 0:
 278         case 1:
 279         case 2:
 280         case 3:
 281           //a 0LLLLLLL
 282           //fprintf (stderr, "lit: 1\n");
 283           *out++ = first;
 284           continue;
 285         case 4:
 286           //b 100lllll <l+1 bytes>
 287           {
 288             unsigned int l = (first & 31) + 1;
 289             //fprintf (stderr, "lit: %d\n", l);
 290             while (l--)
 291               *out++ = *in++;
 292             continue;
 293           }
 294         case 5:
 295           //c 101oolll <8o>
 296           {
 297             o = first & (3 << 3);
 298             o = (o << 5) | *in++;
 299             first = (first & 7) + 2;
 300             break;
 301           }
 302         case 6:
 303           //d 110lllll <8o>
 304           {
 305             o = *in++;
 306             first = (first & 31) + 10;
 307             break;
 308           }
 309         case 7:
 310           //e 1110llll <8o> <8o>
 311           //f 1111llll <8o> <8o> <8l>
 312           {
 313             o = *in++ << 8;
 314             o |= *in++;
 315             first = first & 31;
 316             if (first >= 16)
 317               first = (((first - 16) << 8) | *in++) + 18;
 318             else
 319               first += 2;
 320             break;
 321           }
 322         }
 323       //fprintf (stderr, "ref: %d @ %d\n", first, o);
 324       o++;
 325       /* We know that first will not be zero, and this loop structure is
 326          better optimizable.  */
 327       do
 328         {
 329           *out = out[-o];
 330           out++;
 331         }
 332       while (--first);
 333     }
 334   return out - orig_out;
 335 }
 336
 337 #ifdef STANDALONE
 338
 339 static void
 340 transfer_file (FILE * from, FILE * to, int compress)
 341 {
 342   unsigned char inb[BLOCK_SIZE];
 343   unsigned char outb[BLOCK_SIZE];
 344   while (!feof (from) && !ferror (from))
 345     {
 346       unsigned int in_len, out_len;
 347       if (compress)
 348         {
 349           in_len = fread (inb, 1, BLOCK_SIZE, from);
 350           if (in_len)
 351             {
 352               unsigned char *b = outb;
 353               out_len = compress_buf (inb, in_len, outb, sizeof (outb));
 354               if (!out_len)
 355                 b = inb, out_len = in_len;
 356               if (fwrite (&out_len, sizeof (out_len), 1, to) != 1)
 357                 {
 358                   perror ("write size");
 359                   exit (1);
 360                 }
 361               if (fwrite (b, out_len, 1, to) != 1)
 362                 {
 363                   perror ("write data");
 364                   exit (1);
 365                 }
 366             }
 367         }
 368       else
 369         {
 370           if (fread (&in_len, sizeof (in_len), 1, from) != 1)
 371             {
 372               if (feof (from))
 373                 return;
 374               perror ("can't read size");
 375               exit (1);
 376             }
 377           if (fread (inb, in_len, 1, from) != 1)
 378             {
 379               perror ("can't read data");
 380               exit (1);
 381             }
 382           out_len =
 383             unchecked_decompress_buf (inb, in_len, outb, sizeof (outb));
 384           if (fwrite (outb, out_len, 1, to) != 1)
 385             {
 386               perror ("can't write output");
 387               exit (1);
 388             }
 389         }
 390     }
 391 }
 392
 393 /* Just for benchmarking purposes.  */
 394 static void
 395 dumb_memcpy (void *dest, const void *src, unsigned int len)
 396 {
 397   char *d = dest;
 398   const char *s = src;
 399   while (len--)
 400     *d++ = *s++;
 401 }
 402
 403 static void
 404 benchmark (FILE * from)
 405 {
 406   unsigned char inb[BLOCK_SIZE];
 407   unsigned char outb[BLOCK_SIZE];
 408   unsigned int in_len = fread (inb, 1, BLOCK_SIZE, from);
 409   unsigned int out_len;
 410   if (!in_len)
 411     {
 412       perror ("can't read from input");
 413       exit (1);
 414     }
 415
 416   unsigned int calib_loop;
 417   unsigned int per_loop;
 418   unsigned int i, j;
 419   clock_t start, end;
 420
 421   calib_loop = 1;
 422   per_loop = 0;
 423   start = clock ();
 424   while ((clock () - start) < CLOCKS_PER_SEC / 4)
 425     {
 426       calib_loop *= 2;
 427       for (i = 0; i < calib_loop; i++)
 428         dumb_memcpy (outb, inb, in_len);
 429       per_loop += calib_loop;
 430     }
 431
 432   fprintf (stderr, "memcpy:\nCalibrated to %d iterations per loop\n",
 433            per_loop);
 434
 435   start = clock ();
 436   for (i = 0; i < 10; i++)
 437     for (j = 0; j < per_loop; j++)
 438       dumb_memcpy (outb, inb, in_len);
 439   end = clock ();
 440   float seconds = (end - start) / (float) CLOCKS_PER_SEC;
 441   fprintf (stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 442            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 443
 444   calib_loop = 1;
 445   per_loop = 0;
 446   start = clock ();
 447   while ((clock () - start) < CLOCKS_PER_SEC / 4)
 448     {
 449       calib_loop *= 2;
 450       for (i = 0; i < calib_loop; i++)
 451         compress_buf (inb, in_len, outb, sizeof (outb));
 452       per_loop += calib_loop;
 453     }
 454
 455   fprintf (stderr, "compression:\nCalibrated to %d iterations per loop\n",
 456            per_loop);
 457
 458   start = clock ();
 459   for (i = 0; i < 10; i++)
 460     for (j = 0; j < per_loop; j++)
 461       compress_buf (inb, in_len, outb, sizeof (outb));
 462   end = clock ();
 463   seconds = (end - start) / (float) CLOCKS_PER_SEC;
 464   fprintf (stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 465            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 466
 467   out_len = compress_buf (inb, in_len, outb, sizeof (outb));
 468
 469   calib_loop = 1;
 470   per_loop = 0;
 471   start = clock ();
 472   while ((clock () - start) < CLOCKS_PER_SEC / 4)
 473     {
 474       calib_loop *= 2;
 475       for (i = 0; i < calib_loop; i++)
 476         unchecked_decompress_buf (outb, out_len, inb, sizeof (inb));
 477       per_loop += calib_loop;
 478     }
 479
 480   fprintf (stderr, "decompression:\nCalibrated to %d iterations per loop\n",
 481            per_loop);
 482
 483   start = clock ();
 484   for (i = 0; i < 10; i++)
 485     for (j = 0; j < per_loop; j++)
 486       unchecked_decompress_buf (outb, out_len, inb, sizeof (inb));
 487   end = clock ();
 488   seconds = (end - start) / (float) CLOCKS_PER_SEC;
 489   fprintf (stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 490            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 491 }
 492
 493 int
 494 main (int argc, char *argv[])
 495 {
 496   int compress = 1;
 497   if (argc > 1 && !strcmp (argv[1], "-d"))
 498     compress = 0;
 499   if (argc > 1 && !strcmp (argv[1], "-b"))
 500     benchmark (stdin);
 501   else
 502     transfer_file (stdin, stdout, compress);
 503   return 0;
 504 }
 505
 506 #endif