src/repopage.c

   1 /*
   2  * Copyright (c) 2007-2008, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * repopage.c
  10  *
  11  * Pageing and compression functions for the vertical repository data
  12  *
  13  */
  14
  15 #define _XOPEN_SOURCE 500
  16
  17 #include <sys/types.h>
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <unistd.h>
  22 #include <assert.h>
  23 #include <time.h>
  24
  25 #include "repo.h"
  26 #include "repopage.h"
  27
  28
  29
  30 #define BLOCK_SIZE (65536*1)
  31 #if BLOCK_SIZE <= 65536
  32 typedef __uint16_t Ref;
  33 #else
  34 typedef __uint32_t Ref;
  35 #endif
  36
  37 /*
  38    The format is tailored for fast decompression (i.e. only byte based),
  39    and skewed to ASCII content (highest bit often not set):
  40
  41    a 0LLLLLLL
  42         - self-describing ASCII character hex L
  43    b 100lllll <l+1 bytes>
  44         - literal run of length l+1
  45    c 101oolll <8o>
  46         - back ref of length l+2, at offset -(o+1) (o < 1 << 10)
  47    d 110lllll <8o>
  48         - back ref of length l+2+8, at offset -(o+1) (o < 1 << 8)
  49    e 1110llll <8o> <8o>
  50         - back ref of length l+3, at offset -(o+1) (o < 1 << 16)
  51   f1 1111llll <8l> <8o> <8o>
  52         - back ref, length l+19 (l < 1<<12), offset -(o+1) (o < 1<<16)
  53   f2 11110lll <8l> <8o> <8o>
  54         - back ref, length l+19 (l < 1<<11), offset -(o+1) (o < 1<<16)
  55    g 11111lll <8l> <8o> <8o> <8o>
  56         - back ref, length l+5 (l < 1<<11), offset -(o+1) (o < 1<<24)
  57
  58    Generally for a literal of length L we need L+1 bytes, hence it is
  59    better to encode also very short backrefs (2 chars) as backrefs if
  60    their offset is small, as that only needs two bytes.  Except if we
  61    already have a literal run, in that case it's better to append there,
  62    instead of breaking it for a backref.  So given a potential backref
  63    at offset O, length L the strategy is as follows:
  64
  65    L < 2 : encode as 1-literal
  66    L == 2, O > 1024 : encode as 1-literal
  67    L == 2, have already literals: encode as 1-literal
  68    O = O - 1
  69    L >= 2, L <= 9, O < 1024                            : encode as c
  70    L >= 10, L <= 41, O < 256                           : encode as d
  71    else we have either O >= 1024, or L >= 42:
  72    L < 3 : encode as 1-literal
  73    L >= 3, L <= 18, O < 65536                          : encode as e
  74    L >= 19, L <= 4095+18, O < 65536                    : encode as f
  75    else we have either L >= 4096+18 or O >= 65536.
  76    O >= 65536: encode as 1-literal, too bad
  77      (with the current block size this can't happen)
  78    L >= 4096+18, so reduce to 4095+18                  : encode as f
  79 */
  80
  81
  82 static unsigned int
  83 compress_buf(const unsigned char *in, unsigned int in_len,
  84               unsigned char *out, unsigned int out_len)
  85 {
  86   unsigned int oo = 0;          //out-offset
  87   unsigned int io = 0;          //in-offset
  88 #define HS (65536)
  89   Ref htab[HS];
  90   Ref hnext[BLOCK_SIZE];
  91   memset (htab, -1, sizeof (htab));
  92   memset (hnext, -1, sizeof (hnext));
  93   unsigned int litofs = 0;
  94   while (io + 2 < in_len)
  95     {
  96       /* Search for a match of the string starting at IN, we have at
  97          least three characters.  */
  98       unsigned int hval = in[io] | in[io + 1] << 8 | in[io + 2] << 16;
  99       unsigned int try, mlen, mofs, tries;
 100       hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
 101       hval = hval & (HS - 1);
 102       try = htab[hval];
 103       hnext[io] = htab[hval];
 104       htab[hval] = io;
 105       mlen = 0;
 106       mofs = 0;
 107
 108       for (tries = 0; try != -1 && tries < 12; tries++)
 109         {
 110           if (try < io
 111               && in[try] == in[io] && in[try + 1] == in[io + 1])
 112             {
 113               mlen = 2;
 114               mofs = (io - try) - 1;
 115               break;
 116             }
 117           try = hnext[try];
 118         }
 119       for (; try != -1 && tries < 12; tries++)
 120         {
 121           //assert (mlen >= 2);
 122           //assert (io + mlen < in_len);
 123           /* Try a match starting from [io] with the strings at [try].
 124              That's only sensible if TRY actually is before IO (can happen
 125              with uninit hash table).  If we have a previous match already
 126              we're only going to take the new one if it's longer, hence
 127              check the potentially last character.  */
 128           if (try < io && in[try + mlen] == in[io + mlen])
 129             {
 130               unsigned int this_len, this_ofs;
 131               if (memcmp (in + try, in + io, mlen))
 132                 goto no_match;
 133               this_len = mlen + 1;
 134               /* Now try extending the match by more characters.  */
 135               for (;
 136                    io + this_len < in_len
 137                    && in[try + this_len] == in[io + this_len]; this_len++)
 138                 ;
 139 #if 0
 140               unsigned int testi;
 141               for (testi = 0; testi < this_len; testi++)
 142                 assert (in[try + testi] == in[io + testi]);
 143 #endif
 144               this_ofs = (io - try) - 1;
 145               /*if (this_ofs > 65535)
 146                  goto no_match; */
 147 #if 0
 148               assert (this_len >= 2);
 149               assert (this_len >= mlen);
 150               assert (this_len > mlen || (this_len == mlen && this_ofs > mofs));
 151 #endif
 152               mlen = this_len, mofs = this_ofs;
 153               /* If our match extends up to the end of input, no next
 154                  match can become better.  This is not just an
 155                  optimization, it establishes a loop invariant
 156                  (io + mlen < in_len).  */
 157               if (io + mlen >= in_len)
 158                 goto match_done;
 159             }
 160         no_match:
 161           try = hnext[try];
 162           /*if (io - try - 1 >= 65536)
 163             break;*/
 164         }
 165
 166 match_done:
 167       if (mlen)
 168         {
 169           //fprintf (stderr, "%d %d\n", mlen, mofs);
 170           if (mlen == 2 && (litofs || mofs >= 1024))
 171             mlen = 0;
 172           /*else if (mofs >= 65536)
 173             mlen = 0;*/
 174           else if (mofs >= 65536)
 175             {
 176               if (mlen >= 2048 + 5)
 177                 mlen = 2047 + 5;
 178               else if (mlen < 5)
 179                 mlen = 0;
 180             }
 181           else if (mlen < 3)
 182             mlen = 0;
 183           /*else if (mlen >= 4096 + 19)
 184             mlen = 4095 + 19;*/
 185           else if (mlen >= 2048 + 19)
 186             mlen = 2047 + 19;
 187           /* Skip this match if the next character would deliver a better one,
 188              but only do this if we have the chance to really extend the
 189              length (i.e. our current length isn't yet the (conservative)
 190              maximum).  */
 191           if (mlen && mlen < (2048 + 5) && io + 3 < in_len)
 192             {
 193               unsigned int hval =
 194                 in[io + 1] | in[io + 2] << 8 | in[io + 3] << 16;
 195               unsigned int try;
 196               hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
 197               hval = hval & (HS - 1);
 198               try = htab[hval];
 199               if (try < io + 1
 200                   && in[try] == in[io + 1] && in[try + 1] == in[io + 2])
 201                 {
 202                   unsigned int this_len;
 203                   this_len = 2;
 204                   for (;
 205                        io + 1 + this_len < in_len
 206                        && in[try + this_len] == in[io + 1 + this_len];
 207                        this_len++)
 208                     ;
 209                   if (this_len >= mlen)
 210                     mlen = 0;
 211                 }
 212             }
 213         }
 214       if (!mlen)
 215         {
 216           if (!litofs)
 217             litofs = io + 1;
 218           io++;
 219         }
 220       else
 221         {
 222           if (litofs)
 223             {
 224               litofs--;
 225               unsigned litlen = io - litofs;
 226               //fprintf (stderr, "lit: %d\n", litlen);
 227               while (litlen)
 228                 {
 229                   unsigned int easy_sz;
 230                   /* Emit everything we can as self-describers.  As soon as
 231                      we hit a byte we can't emit as such we're going to emit
 232                      a length descriptor anyway, so we can as well include
 233                      bytes < 0x80 which might follow afterwards in that run.  */
 234                   for (easy_sz = 0;
 235                        easy_sz < litlen && in[litofs + easy_sz] < 0x80;
 236                        easy_sz++)
 237                     ;
 238                   if (easy_sz)
 239                     {
 240                       if (oo + easy_sz >= out_len)
 241                         return 0;
 242                       memcpy (out + oo, in + litofs, easy_sz);
 243                       litofs += easy_sz;
 244                       oo += easy_sz;
 245                       litlen -= easy_sz;
 246                       if (!litlen)
 247                         break;
 248                     }
 249                   if (litlen <= 32)
 250                     {
 251                       if (oo + 1 + litlen >= out_len)
 252                         return 0;
 253                       out[oo++] = 0x80 | (litlen - 1);
 254                       while (litlen--)
 255                         out[oo++] = in[litofs++];
 256                       break;
 257                     }
 258                   else
 259                     {
 260                       /* Literal length > 32, so chunk it.  */
 261                       if (oo + 1 + 32 >= out_len)
 262                         return 0;
 263                       out[oo++] = 0x80 | 31;
 264                       memcpy (out + oo, in + litofs, 32);
 265                       oo += 32;
 266                       litofs += 32;
 267                       litlen -= 32;
 268                     }
 269                 }
 270               litofs = 0;
 271             }
 272
 273           //fprintf (stderr, "ref: %d @ %d\n", mlen, mofs);
 274
 275           if (mlen >= 2 && mlen <= 9 && mofs < 1024)
 276             {
 277               if (oo + 2 >= out_len)
 278                 return 0;
 279               out[oo++] = 0xa0 | ((mofs & 0x300) >> 5) | (mlen - 2);
 280               out[oo++] = mofs & 0xff;
 281             }
 282           else if (mlen >= 10 && mlen <= 41 && mofs < 256)
 283             {
 284               if (oo + 2 >= out_len)
 285                 return 0;
 286               out[oo++] = 0xc0 | (mlen - 10);
 287               out[oo++] = mofs;
 288             }
 289           else if (mofs >= 65536)
 290             {
 291               assert (mlen >= 5 && mlen < 2048 + 5);
 292               if (oo + 5 >= out_len)
 293                 return 0;
 294               out[oo++] = 0xf8 | ((mlen - 5) >> 8);
 295               out[oo++] = (mlen - 5) & 0xff;
 296               out[oo++] = mofs & 0xff;
 297               out[oo++] = (mofs >> 8) & 0xff;
 298               out[oo++] = mofs >> 16;
 299             }
 300           else if (mlen >= 3 && mlen <= 18)
 301             {
 302               assert (mofs < 65536);
 303               if (oo + 3 >= out_len)
 304                 return 0;
 305               out[oo++] = 0xe0 | (mlen - 3);
 306               out[oo++] = mofs & 0xff;
 307               out[oo++] = mofs >> 8;
 308             }
 309           else
 310             {
 311               assert (mlen >= 19 && mlen <= 4095 + 19 && mofs < 65536);
 312               if (oo + 4 >= out_len)
 313                 return 0;
 314               out[oo++] = 0xf0 | ((mlen - 19) >> 8);
 315               out[oo++] = (mlen - 19) & 0xff;
 316               out[oo++] = mofs & 0xff;
 317               out[oo++] = mofs >> 8;
 318             }
 319           /* Insert the hashes for the compressed run [io..io+mlen-1].
 320              For [io] we have it already done at the start of the loop.
 321              So it's from [io+1..io+mlen-1], and we need three chars per
 322              hash, so the accessed characters will be [io+1..io+mlen-1+2],
 323              ergo io+mlen+1 < in_len.  */
 324           mlen--;
 325           io++;
 326           while (mlen--)
 327             {
 328               if (io + 2 < in_len)
 329                 {
 330                   unsigned int hval =
 331                     in[io] | in[io + 1] << 8 | in[io + 2] << 16;
 332                   hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
 333                   hval = hval & (HS - 1);
 334                   hnext[io] = htab[hval];
 335                   htab[hval] = io;
 336                 }
 337               io++;
 338             };
 339         }
 340     }
 341   /* We might have some characters left.  */
 342   if (io < in_len && !litofs)
 343     litofs = io + 1;
 344   io = in_len;
 345   if (litofs)
 346     {
 347       litofs--;
 348       unsigned litlen = io - litofs;
 349       //fprintf (stderr, "lit: %d\n", litlen);
 350       while (litlen)
 351         {
 352           unsigned int easy_sz;
 353           /* Emit everything we can as self-describers.  As soon as we hit a
 354              byte we can't emit as such we're going to emit a length
 355              descriptor anyway, so we can as well include bytes < 0x80 which
 356              might follow afterwards in that run.  */
 357           for (easy_sz = 0; easy_sz < litlen && in[litofs + easy_sz] < 0x80;
 358                easy_sz++)
 359             ;
 360           if (easy_sz)
 361             {
 362               if (oo + easy_sz >= out_len)
 363                 return 0;
 364               memcpy (out + oo, in + litofs, easy_sz);
 365               litofs += easy_sz;
 366               oo += easy_sz;
 367               litlen -= easy_sz;
 368               if (!litlen)
 369                 break;
 370             }
 371           if (litlen <= 32)
 372             {
 373               if (oo + 1 + litlen >= out_len)
 374                 return 0;
 375               out[oo++] = 0x80 | (litlen - 1);
 376               while (litlen--)
 377                 out[oo++] = in[litofs++];
 378               break;
 379             }
 380           else
 381             {
 382               /* Literal length > 32, so chunk it.  */
 383               if (oo + 1 + 32 >= out_len)
 384                 return 0;
 385               out[oo++] = 0x80 | 31;
 386               memcpy (out + oo, in + litofs, 32);
 387               oo += 32;
 388               litofs += 32;
 389               litlen -= 32;
 390             }
 391         }
 392       litofs = 0;
 393     }
 394   return oo;
 395 }
 396
 397 static unsigned int
 398 unchecked_decompress_buf(const unsigned char *in, unsigned int in_len,
 399                           unsigned char *out,
 400                           unsigned int out_len __attribute__((unused)))
 401 {
 402   unsigned char *orig_out = out;
 403   const unsigned char *in_end = in + in_len;
 404   while (in < in_end)
 405     {
 406       unsigned int first = *in++;
 407       int o;
 408       switch (first >> 4)
 409         {
 410         default:
 411           /* This default case can't happen, but GCCs VRP is not strong
 412              enough to see this, so make this explicitely not fall to
 413              the end of the switch, so that we don't have to initialize
 414              o above.  */
 415           continue;
 416         case 0: case 1:
 417         case 2: case 3:
 418         case 4: case 5:
 419         case 6: case 7:
 420           //a 0LLLLLLL
 421           //fprintf (stderr, "lit: 1\n");
 422           *out++ = first;
 423           continue;
 424         case 8: case 9:
 425           //b 100lllll <l+1 bytes>
 426           {
 427             unsigned int l = first & 31;
 428             //fprintf (stderr, "lit: %d\n", l);
 429             do
 430               *out++ = *in++;
 431             while (l--);
 432             continue;
 433           }
 434         case 10: case 11:
 435           //c 101oolll <8o>
 436           {
 437             o = first & (3 << 3);
 438             o = (o << 5) | *in++;
 439             first = (first & 7) + 2;
 440             break;
 441           }
 442         case 12: case 13:
 443           //d 110lllll <8o>
 444           {
 445             o = *in++;
 446             first = (first & 31) + 10;
 447             break;
 448           }
 449         case 14:
 450           // e 1110llll <8o> <8o>
 451           {
 452             o = in[0] | (in[1] << 8);
 453             in += 2;
 454             first = first & 31;
 455             first += 3;
 456             break;
 457           }
 458         case 15:
 459           //f1 1111llll <8o> <8o> <8l>
 460           //f2 11110lll <8o> <8o> <8l>
 461           // g 11111lll <8o> <8o> <8o> <8l>
 462           {
 463             first = first & 15;
 464             if (first >= 8)
 465               {
 466                 first = (((first - 8) << 8) | in[0]) + 5;
 467                 o = in[1] | (in[2] << 8) | (in[3] << 16);
 468                 in += 4;
 469               }
 470             else
 471               {
 472                 first = ((first << 8) | in[0]) + 19;
 473                 o = in[1] | (in[2] << 8);
 474                 in += 3;
 475               }
 476             break;
 477           }
 478         }
 479       //fprintf (stderr, "ref: %d @ %d\n", first, o);
 480       o++;
 481       o = -o;
 482 #if 0
 483       /* We know that first will not be zero, and this loop structure is
 484          better optimizable.  */
 485       do
 486         {
 487           *out = *(out - o);
 488           out++;
 489         }
 490       while (--first);
 491 #else
 492       switch (first)
 493         {
 494           case 18: *out = *(out + o); out++;
 495           case 17: *out = *(out + o); out++;
 496           case 16: *out = *(out + o); out++;
 497           case 15: *out = *(out + o); out++;
 498           case 14: *out = *(out + o); out++;
 499           case 13: *out = *(out + o); out++;
 500           case 12: *out = *(out + o); out++;
 501           case 11: *out = *(out + o); out++;
 502           case 10: *out = *(out + o); out++;
 503           case  9: *out = *(out + o); out++;
 504           case  8: *out = *(out + o); out++;
 505           case  7: *out = *(out + o); out++;
 506           case  6: *out = *(out + o); out++;
 507           case  5: *out = *(out + o); out++;
 508           case  4: *out = *(out + o); out++;
 509           case  3: *out = *(out + o); out++;
 510           case  2: *out = *(out + o); out++;
 511           case  1: *out = *(out + o); out++;
 512           case  0: break;
 513           default:
 514             /* Duff duff :-) */
 515             switch (first & 15)
 516               {
 517                 do
 518                   {
 519                     case  0: *out = *(out + o); out++;
 520                     case 15: *out = *(out + o); out++;
 521                     case 14: *out = *(out + o); out++;
 522                     case 13: *out = *(out + o); out++;
 523                     case 12: *out = *(out + o); out++;
 524                     case 11: *out = *(out + o); out++;
 525                     case 10: *out = *(out + o); out++;
 526                     case  9: *out = *(out + o); out++;
 527                     case  8: *out = *(out + o); out++;
 528                     case  7: *out = *(out + o); out++;
 529                     case  6: *out = *(out + o); out++;
 530                     case  5: *out = *(out + o); out++;
 531                     case  4: *out = *(out + o); out++;
 532                     case  3: *out = *(out + o); out++;
 533                     case  2: *out = *(out + o); out++;
 534                     case  1: *out = *(out + o); out++;
 535                   }
 536                 while ((int)(first -= 16) > 0);
 537               }
 538             break;
 539         }
 540 #endif
 541     }
 542   return out - orig_out;
 543 }
 544
 545 /**********************************************************************/
 546
 547 unsigned char *
 548 repodata_load_page_range(Repodata *data, unsigned int pstart, unsigned int pend)
 549 {
 550 /* Make sure all pages from PSTART to PEND (inclusive) are loaded,
 551    and are consecutive.  Return a pointer to the mapping of PSTART.  */
 552   unsigned char buf[BLOB_PAGESIZE];
 553   unsigned int i;
 554
 555   /* Quick check in case all pages are there already and consecutive.  */
 556   for (i = pstart; i <= pend; i++)
 557     if (data->pages[i].mapped_at == -1
 558         || (i > pstart
 559             && data->pages[i].mapped_at
 560                != data->pages[i-1].mapped_at + BLOB_PAGESIZE))
 561       break;
 562   if (i > pend)
 563     return data->blob_store + data->pages[pstart].mapped_at;
 564
 565   if (data->pagefd == -1)
 566     return 0;
 567
 568   /* Ensure that we can map the numbers of pages we need at all.  */
 569   if (pend - pstart + 1 > data->ncanmap)
 570     {
 571       unsigned int oldcan = data->ncanmap;
 572       data->ncanmap = pend - pstart + 1;
 573       if (data->ncanmap < 4)
 574         data->ncanmap = 4;
 575       data->mapped = sat_realloc2(data->mapped, data->ncanmap, sizeof(data->mapped[0]));
 576       memset (data->mapped + oldcan, 0, (data->ncanmap - oldcan) * sizeof (data->mapped[0]));
 577       data->blob_store = sat_realloc2(data->blob_store, data->ncanmap, BLOB_PAGESIZE);
 578 #ifdef DEBUG_PAGING
 579       fprintf (stderr, "PAGE: can map %d pages\n", data->ncanmap);
 580 #endif
 581     }
 582
 583   /* Now search for "cheap" space in our store.  Space is cheap if it's either
 584      free (very cheap) or contains pages we search for anyway.  */
 585
 586   /* Setup cost array.  */
 587   unsigned int cost[data->ncanmap];
 588   for (i = 0; i < data->ncanmap; i++)
 589     {
 590       unsigned int pnum = data->mapped[i];
 591       if (pnum == 0)
 592         cost[i] = 0;
 593       else
 594         {
 595           pnum--;
 596           Attrblobpage *p = data->pages + pnum;
 597           assert (p->mapped_at != -1);
 598           if (pnum >= pstart && pnum <= pend)
 599             cost[i] = 1;
 600           else
 601             cost[i] = 3;
 602         }
 603     }
 604
 605   /* And search for cheapest space.  */
 606   unsigned int best_cost = -1;
 607   unsigned int best = 0;
 608   unsigned int same_cost = 0;
 609   for (i = 0; i + pend - pstart < data->ncanmap; i++)
 610     {
 611       unsigned int c = cost[i];
 612       unsigned int j;
 613       for (j = 0; j < pend - pstart + 1; j++)
 614         c += cost[i+j];
 615       if (c < best_cost)
 616         best_cost = c, best = i;
 617       else if (c == best_cost)
 618         same_cost++;
 619       /* A null cost won't become better.  */
 620       if (c == 0)
 621         break;
 622     }
 623   /* If all places have the same cost we would thrash on slot 0.  Avoid
 624      this by doing a round-robin strategy in this case.  */
 625   if (same_cost == data->ncanmap - pend + pstart - 1)
 626     best = data->rr_counter++ % (data->ncanmap - pend + pstart);
 627
 628   /* So we want to map our pages from [best] to [best+pend-pstart].
 629      Use a very simple strategy, which doesn't make the best use of
 630      our resources, but works.  Throw away all pages in that range
 631      (even ours) then copy around ours (in case they were outside the
 632      range) or read them in.  */
 633   for (i = best; i < best + pend - pstart + 1; i++)
 634     {
 635       unsigned int pnum = data->mapped[i];
 636       if (pnum--
 637           /* If this page is exactly at the right place already,
 638              no need to evict it.  */
 639           && pnum != pstart + i - best)
 640         {
 641           /* Evict this page.  */
 642 #ifdef DEBUG_PAGING
 643           fprintf (stderr, "PAGE: evict page %d from %d\n", pnum, i);
 644 #endif
 645           cost[i] = 0;
 646           data->mapped[i] = 0;
 647           data->pages[pnum].mapped_at = -1;
 648         }
 649     }
 650
 651   /* Everything is free now.  Read in the pages we want.  */
 652   for (i = pstart; i <= pend; i++)
 653     {
 654       Attrblobpage *p = data->pages + i;
 655       unsigned int pnum = i - pstart + best;
 656       void *dest = data->blob_store + pnum * BLOB_PAGESIZE;
 657       if (p->mapped_at != -1)
 658         {
 659           if (p->mapped_at != pnum * BLOB_PAGESIZE)
 660             {
 661 #ifdef DEBUG_PAGING
 662               fprintf (stderr, "PAGECOPY: %d to %d\n", i, pnum);
 663 #endif
 664               /* Still mapped somewhere else, so just copy it from there.  */
 665               memcpy (dest, data->blob_store + p->mapped_at, BLOB_PAGESIZE);
 666               data->mapped[p->mapped_at / BLOB_PAGESIZE] = 0;
 667             }
 668         }
 669       else
 670         {
 671           unsigned int in_len = p->file_size;
 672           unsigned int compressed = in_len & 1;
 673           in_len >>= 1;
 674 #ifdef DEBUG_PAGING
 675           fprintf (stderr, "PAGEIN: %d to %d", i, pnum);
 676 #endif
 677           if (pread(data->pagefd, compressed ? buf : dest, in_len, p->file_offset) != in_len)
 678             {
 679               perror ("mapping pread");
 680               return 0;
 681             }
 682           if (compressed)
 683             {
 684               unsigned int out_len;
 685               out_len = unchecked_decompress_buf(buf, in_len,
 686                                                   dest, BLOB_PAGESIZE);
 687               if (out_len != BLOB_PAGESIZE && i < data->num_pages - 1)
 688                 {
 689                   fprintf(stderr, "can't decompress\n");
 690                   return 0;
 691                 }
 692 #ifdef DEBUG_PAGING
 693               fprintf (stderr, " (expand %d to %d)", in_len, out_len);
 694 #endif
 695             }
 696 #ifdef DEBUG_PAGING
 697           fprintf (stderr, "\n");
 698 #endif
 699         }
 700       p->mapped_at = pnum * BLOB_PAGESIZE;
 701       data->mapped[pnum] = i + 1;
 702     }
 703   return data->blob_store + best * BLOB_PAGESIZE;
 704 }
 705
 706 unsigned char *
 707 repodata_fetch_vertical(Repodata *data, Repokey *key, Id off, Id len)
 708 {
 709   unsigned char *dp;
 710   if (!len)
 711     return 0;
 712   if (off >= data->lastverticaloffset)
 713     {
 714       off -= data->lastverticaloffset;
 715       if (off + len > data->vincorelen)
 716         return 0;
 717       return data->vincore + off;
 718     }
 719   if (off + len > key->size)
 720     return 0;
 721   /* we now have the offset, go into vertical */
 722   off += data->verticaloffset[key - data->keys];
 723   /* fprintf(stderr, "key %d page %d\n", key->name, off / BLOB_PAGESIZE); */
 724   dp = repodata_load_page_range(data, off / BLOB_PAGESIZE, (off + len - 1) / BLOB_PAGESIZE);
 725   if (dp)
 726     dp += off % BLOB_PAGESIZE;
 727   return dp;
 728 }
 729
 730 unsigned int
 731 repodata_compress_page(unsigned char *page, unsigned int len, unsigned char *cpage, unsigned int max)
 732 {
 733   return compress_buf(page, len, cpage, max);
 734 }
 735
 736 #define SOLV_ERROR_EOF          3
 737 #define SOLV_ERROR_CORRUPT      6
 738
 739 static inline unsigned int
 740 read_u32(FILE *fp)
 741 {
 742   int c, i;
 743   unsigned int x = 0;
 744
 745   for (i = 0; i < 4; i++)
 746     {
 747       c = getc(fp);
 748       if (c == EOF)
 749         return 0;
 750       x = (x << 8) | c;
 751     }
 752   return x;
 753 }
 754
 755 /* Try to either setup on-demand paging (using FP as backing
 756    file), or in case that doesn't work (FP not seekable) slurps in
 757    all pages and deactivates paging.  */
 758 void
 759 repodata_read_or_setup_pages(Repodata *data, unsigned int pagesz, unsigned int blobsz)
 760 {
 761   FILE *fp = data->fp;
 762   unsigned int npages;
 763   unsigned int i;
 764   unsigned int can_seek;
 765   long cur_file_ofs;
 766   unsigned char buf[BLOB_PAGESIZE];
 767
 768   if (pagesz != BLOB_PAGESIZE)
 769     {
 770       /* We could handle this by slurping in everything.  */
 771       data->error = SOLV_ERROR_CORRUPT;
 772       return;
 773     }
 774   can_seek = 1;
 775   if ((cur_file_ofs = ftell(fp)) < 0)
 776     can_seek = 0;
 777   clearerr(fp);
 778   if (can_seek)
 779     data->pagefd = dup(fileno(fp));
 780   if (data->pagefd == -1)
 781     can_seek = 0;
 782
 783 #ifdef DEBUG_PAGING
 784   fprintf (stderr, "can %sseek\n", can_seek ? "" : "NOT ");
 785 #endif
 786   npages = (blobsz + BLOB_PAGESIZE - 1) / BLOB_PAGESIZE;
 787
 788   data->num_pages = npages;
 789   data->pages = sat_malloc2(npages, sizeof(data->pages[0]));
 790
 791   /* If we can't seek on our input we have to slurp in everything.  */
 792   if (!can_seek)
 793     data->blob_store = sat_malloc(npages * BLOB_PAGESIZE);
 794   for (i = 0; i < npages; i++)
 795     {
 796       unsigned int in_len = read_u32(fp);
 797       unsigned int compressed = in_len & 1;
 798       Attrblobpage *p = data->pages + i;
 799       in_len >>= 1;
 800 #ifdef DEBUG_PAGING
 801       fprintf (stderr, "page %d: len %d (%scompressed)\n",
 802                i, in_len, compressed ? "" : "not ");
 803 #endif
 804       if (can_seek)
 805         {
 806           cur_file_ofs += 4;
 807           p->mapped_at = -1;
 808           p->file_offset = cur_file_ofs;
 809           p->file_size = in_len * 2 + compressed;
 810           if (fseek(fp, in_len, SEEK_CUR) < 0)
 811             {
 812               perror ("fseek");
 813               fprintf (stderr, "can't seek after we thought we can\n");
 814               /* We can't fall back to non-seeking behaviour as we already
 815                  read over some data pages without storing them away.  */
 816               data->error = SOLV_ERROR_EOF;
 817               close(data->pagefd);
 818               data->pagefd = -1;
 819               return;
 820             }
 821           cur_file_ofs += in_len;
 822         }
 823       else
 824         {
 825           unsigned int out_len;
 826           void *dest = data->blob_store + i * BLOB_PAGESIZE;
 827           p->mapped_at = i * BLOB_PAGESIZE;
 828           p->file_offset = 0;
 829           p->file_size = 0;
 830           /* We can't seek, so suck everything in.  */
 831           if (fread(compressed ? buf : dest, in_len, 1, fp) != 1)
 832             {
 833               perror("fread");
 834               data->error = SOLV_ERROR_EOF;
 835               return;
 836             }
 837           if (compressed)
 838             {
 839               out_len = unchecked_decompress_buf(buf, in_len, dest, BLOB_PAGESIZE);
 840               if (out_len != BLOB_PAGESIZE && i < npages - 1)
 841                 {
 842                   data->error = SOLV_ERROR_CORRUPT;
 843                   return;
 844                 }
 845             }
 846         }
 847     }
 848 }
 849
 850
 851 #ifdef STANDALONE
 852
 853 static void
 854 transfer_file (FILE * from, FILE * to, int compress)
 855 {
 856   unsigned char inb[BLOCK_SIZE];
 857   unsigned char outb[BLOCK_SIZE];
 858   while (!feof (from) && !ferror (from))
 859     {
 860       unsigned int in_len, out_len;
 861       if (compress)
 862         {
 863           in_len = fread (inb, 1, BLOCK_SIZE, from);
 864           if (in_len)
 865             {
 866               unsigned char *b = outb;
 867               out_len = compress_buf (inb, in_len, outb, sizeof (outb));
 868               if (!out_len)
 869                 b = inb, out_len = in_len;
 870               if (fwrite (&out_len, sizeof (out_len), 1, to) != 1)
 871                 {
 872                   perror ("write size");
 873                   exit (1);
 874                 }
 875               if (fwrite (b, out_len, 1, to) != 1)
 876                 {
 877                   perror ("write data");
 878                   exit (1);
 879                 }
 880             }
 881         }
 882       else
 883         {
 884           if (fread (&in_len, sizeof (in_len), 1, from) != 1)
 885             {
 886               if (feof (from))
 887                 return;
 888               perror ("can't read size");
 889               exit (1);
 890             }
 891           if (fread (inb, in_len, 1, from) != 1)
 892             {
 893               perror ("can't read data");
 894               exit (1);
 895             }
 896           out_len =
 897             unchecked_decompress_buf (inb, in_len, outb, sizeof (outb));
 898           if (fwrite (outb, out_len, 1, to) != 1)
 899             {
 900               perror ("can't write output");
 901               exit (1);
 902             }
 903         }
 904     }
 905 }
 906
 907 /* Just for benchmarking purposes.  */
 908 static void
 909 dumb_memcpy (void *dest, const void *src, unsigned int len)
 910 {
 911   char *d = dest;
 912   const char *s = src;
 913   while (len--)
 914     *d++ = *s++;
 915 }
 916
 917 static void
 918 benchmark (FILE * from)
 919 {
 920   unsigned char inb[BLOCK_SIZE];
 921   unsigned char outb[BLOCK_SIZE];
 922   unsigned int in_len = fread (inb, 1, BLOCK_SIZE, from);
 923   unsigned int out_len;
 924   if (!in_len)
 925     {
 926       perror ("can't read from input");
 927       exit (1);
 928     }
 929
 930   unsigned int calib_loop;
 931   unsigned int per_loop;
 932   unsigned int i, j;
 933   clock_t start, end;
 934   float seconds;
 935
 936 #if 0
 937   calib_loop = 1;
 938   per_loop = 0;
 939   start = clock ();
 940   while ((clock () - start) < CLOCKS_PER_SEC / 4)
 941     {
 942       calib_loop *= 2;
 943       for (i = 0; i < calib_loop; i++)
 944         dumb_memcpy (outb, inb, in_len);
 945       per_loop += calib_loop;
 946     }
 947
 948   fprintf (stderr, "memcpy:\nCalibrated to %d iterations per loop\n",
 949            per_loop);
 950
 951   start = clock ();
 952   for (i = 0; i < 10; i++)
 953     for (j = 0; j < per_loop; j++)
 954       dumb_memcpy (outb, inb, in_len);
 955   end = clock ();
 956   seconds = (end - start) / (float) CLOCKS_PER_SEC;
 957   fprintf (stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 958            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 959 #endif
 960
 961   calib_loop = 1;
 962   per_loop = 0;
 963   start = clock ();
 964   while ((clock () - start) < CLOCKS_PER_SEC / 4)
 965     {
 966       calib_loop *= 2;
 967       for (i = 0; i < calib_loop; i++)
 968         compress_buf(inb, in_len, outb, sizeof (outb));
 969       per_loop += calib_loop;
 970     }
 971
 972   fprintf(stderr, "compression:\nCalibrated to %d iterations per loop\n",
 973            per_loop);
 974
 975   start = clock ();
 976   for (i = 0; i < 10; i++)
 977     for (j = 0; j < per_loop; j++)
 978       compress_buf (inb, in_len, outb, sizeof (outb));
 979   end = clock ();
 980   seconds = (end - start) / (float) CLOCKS_PER_SEC;
 981   fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
 982            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
 983
 984   out_len = compress_buf(inb, in_len, outb, sizeof (outb));
 985
 986   calib_loop = 1;
 987   per_loop = 0;
 988   start = clock ();
 989   while ((clock () - start) < CLOCKS_PER_SEC / 4)
 990     {
 991       calib_loop *= 2;
 992       for (i = 0; i < calib_loop; i++)
 993         unchecked_decompress_buf(outb, out_len, inb, sizeof (inb));
 994       per_loop += calib_loop;
 995     }
 996
 997   fprintf(stderr, "decompression:\nCalibrated to %d iterations per loop\n",
 998            per_loop);
 999
1000   start = clock ();
1001   for (i = 0; i < 10; i++)
1002     for (j = 0; j < per_loop; j++)
1003       unchecked_decompress_buf(outb, out_len, inb, sizeof (inb));
1004   end = clock();
1005   seconds = (end - start) / (float) CLOCKS_PER_SEC;
1006   fprintf(stderr, "%.2f seconds == %.2f MB/s\n", seconds,
1007            ((long long) in_len * per_loop * 10) / (1024 * 1024 * seconds));
1008 }
1009
1010 int
1011 main (int argc, char *argv[])
1012 {
1013   int compress = 1;
1014   if (argc > 1 && !strcmp (argv[1], "-d"))
1015     compress = 0;
1016   if (argc > 1 && !strcmp (argv[1], "-b"))
1017     benchmark (stdin);
1018   else
1019     transfer_file (stdin, stdout, compress);
1020   return 0;
1021 }
1022
1023 #endif
1024