zypp/media/MediaBlockList.cc

   1 /*---------------------------------------------------------------------\
   2 |                          ____ _   __ __ ___                          |
   3 |                         |__  / \ / / . \ . \                         |
   4 |                           / / \ V /|  _/  _/                         |
   5 |                          / /__ | | | | | |                           |
   6 |                         /_____||_| |_| |_|                           |
   7 |                                                                      |
   8 \---------------------------------------------------------------------*/
   9 /** \file zypp/media/MediaBlockList.cc
  10  *
  11  */
  12
  13 #include <sys/types.h>
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17
  18 #include <vector>
  19 #include <iostream>
  20 #include <fstream>
  21
  22 #include "zypp/media/MediaBlockList.h"
  23 #include "zypp/base/Logger.h"
  24 #include "zypp/base/String.h"
  25
  26 using namespace std;
  27 using namespace zypp::base;
  28
  29 namespace zypp {
  30   namespace media {
  31
  32 MediaBlockList::MediaBlockList(off_t size)
  33 {
  34   filesize = size;
  35   haveblocks = false;
  36   chksumlen = 0;
  37   chksumpad = 0;
  38   rsumlen = 0;
  39   rsumpad = 0;
  40 }
  41
  42 size_t
  43 MediaBlockList::addBlock(off_t off, size_t size)
  44 {
  45   haveblocks = true;
  46   blocks.push_back(MediaBlock( off, size ));
  47   return blocks.size() - 1;
  48 }
  49
  50 void
  51 MediaBlockList::setFileChecksum(std::string ctype, int cl, unsigned char *c)
  52 {
  53   if (!cl)
  54     return;
  55   fsumtype = ctype;
  56   fsum.resize(cl);
  57   memcpy(&fsum[0], c, cl);
  58 }
  59
  60 bool
  61 MediaBlockList::createFileDigest(Digest &digest) const
  62 {
  63   return digest.create(fsumtype);
  64 }
  65
  66 bool
  67 MediaBlockList::verifyFileDigest(Digest &digest) const
  68 {
  69   if (!haveFileChecksum())
  70     return true;
  71   vector<unsigned char>dig = digest.digestVector();
  72   if (dig.empty() || dig.size() < fsum.size())
  73     return false;
  74   return memcmp(&dig[0], &fsum[0], fsum.size()) ? false : true;
  75 }
  76
  77 void
  78 MediaBlockList::setChecksum(size_t blkno, std::string cstype, int csl, unsigned char *cs, size_t cspad)
  79 {
  80   if (!csl)
  81     return;
  82   if (!chksumlen)
  83     {
  84       if (blkno)
  85         return;
  86       chksumlen = csl;
  87       chksumtype = cstype;
  88       chksumpad = cspad;
  89     }
  90   if (csl != chksumlen || cstype != chksumtype || cspad != chksumpad || blkno != chksums.size() / chksumlen)
  91     return;
  92   chksums.resize(chksums.size() + csl);
  93   memcpy(&chksums[csl * blkno], cs, csl);
  94 }
  95
  96 void
  97 MediaBlockList::setRsum(size_t blkno, int rsl, unsigned int rs, size_t rspad)
  98 {
  99   if (!rsl)
 100     return;
 101   if (!rsumlen)
 102     {
 103       if (blkno)
 104         return;
 105       rsumlen = rsl;
 106       rsumpad = rspad;
 107     }
 108   if (rsl != rsumlen || rspad != rsumpad || blkno != rsums.size())
 109     return;
 110   rsums.push_back(rs);
 111 }
 112
 113 bool
 114 MediaBlockList::createDigest(Digest &digest) const
 115 {
 116   return digest.create(chksumtype);
 117 }
 118
 119 bool
 120 MediaBlockList::verifyDigest(size_t blkno, Digest &digest) const
 121 {
 122   if (!haveChecksum(blkno))
 123     return true;
 124   size_t size = blocks[blkno].size;
 125   if (!size)
 126     return true;
 127   if (chksumpad > size)
 128     {
 129       char pad[chksumpad - size];
 130       memset(pad, 0, chksumpad - size);
 131       digest.update(pad, chksumpad - size);
 132     }
 133   vector<unsigned char>dig = digest.digestVector();
 134   if (dig.empty() || dig.size() < size_t(chksumlen))
 135     return false;
 136   return memcmp(&dig[0], &chksums[chksumlen * blkno], chksumlen) ? false : true;
 137 }
 138
 139 unsigned int
 140 MediaBlockList::updateRsum(unsigned int rs, const char* bytes, size_t len) const
 141 {
 142   if (!len)
 143     return rs;
 144   unsigned short s, m;
 145   s = (rs >> 16) & 65535;
 146   m = rs & 65535;
 147   for (; len > 0 ; len--)
 148     {
 149       unsigned short c = (unsigned char)*bytes++;
 150       s += c;
 151       m += s;
 152     }
 153   return (s & 65535) << 16 | (m & 65535);
 154 }
 155
 156 bool
 157 MediaBlockList::verifyRsum(size_t blkno, unsigned int rs) const
 158 {
 159   if (!haveRsum(blkno))
 160     return true;
 161   size_t size = blocks[blkno].size;
 162   if (!size)
 163     return true;
 164   if (rsumpad > size)
 165     {
 166       unsigned short s, m;
 167       s = (rs >> 16) & 65535;
 168       m = rs & 65535;
 169       m += s * (rsumpad - size);
 170       rs = (s & 65535) << 16 | (m & 65535);
 171     }
 172   switch(rsumlen)
 173     {
 174     case 3:
 175       rs &= 0xffffff;
 176     case 2:
 177       rs &= 0xffff;
 178     case 1:
 179       rs &= 0xff;
 180     default:
 181       break;
 182     }
 183   return rs == rsums[blkno];
 184 }
 185
 186 bool
 187 MediaBlockList::checkRsum(size_t blkno, const unsigned char *buf, size_t bufl) const
 188 {
 189   if (blkno >= blocks.size() || bufl < blocks[blkno].size)
 190     return false;
 191   unsigned int rs = updateRsum(0, (const char *)buf, blocks[blkno].size);
 192   return verifyRsum(blkno, rs);
 193 }
 194
 195 bool
 196 MediaBlockList::checkChecksum(size_t blkno, const unsigned char *buf, size_t bufl) const
 197 {
 198   if (blkno >= blocks.size() || bufl < blocks[blkno].size)
 199     return false;
 200   Digest dig;
 201   if (!createDigest(dig))
 202     return false;
 203   dig.update((const char *)buf, blocks[blkno].size);
 204   return verifyDigest(blkno, dig);
 205 }
 206
 207 // specialized version of checkChecksum that can deal with a "rotated" buffer
 208 bool
 209 MediaBlockList::checkChecksumRotated(size_t blkno, const unsigned char *buf, size_t bufl, size_t start) const
 210 {
 211   if (blkno >= blocks.size() || bufl < blocks[blkno].size)
 212     return false;
 213   if (start == bufl)
 214     start = 0;
 215   Digest dig;
 216   if (!createDigest(dig))
 217     return false;
 218   size_t size = blocks[blkno].size;
 219   size_t len = bufl - start > size ? size : bufl - start;
 220   dig.update((const char *)buf + start, len);
 221   if (size > len)
 222     dig.update((const char *)buf, size - len);
 223   return verifyDigest(blkno, dig);
 224 }
 225
 226 // write block to the file. can also deal with "rotated" buffers
 227 void
 228 MediaBlockList::writeBlock(size_t blkno, FILE *fp, const unsigned char *buf, size_t bufl, size_t start, vector<bool> &found) const
 229 {
 230   if (blkno >= blocks.size() || bufl < blocks[blkno].size)
 231     return;
 232   off_t off = blocks[blkno].off;
 233   size_t size = blocks[blkno].size;
 234   if (fseeko(fp, off, SEEK_SET))
 235     return;
 236   if (start == bufl)
 237     start = 0;
 238   size_t len = bufl - start > size ? size : bufl - start;
 239   if (fwrite(buf + start, len, 1, fp) != 1)
 240     return;
 241   if (size > len && fwrite(buf, size - len, 1, fp) != 1)
 242     return;
 243   found[blkno] = true;
 244   found[blocks.size()] = true;
 245 }
 246
 247 static size_t
 248 fetchnext(FILE *fp, unsigned char *bp, size_t blksize, size_t pushback, unsigned char *pushbackp)
 249 {
 250   size_t l = blksize;
 251   int c;
 252
 253   if (pushback)
 254     {
 255       if (pushbackp != bp)
 256         memmove(bp, pushbackp, pushback);
 257       bp += pushback;
 258       l -= pushback;
 259     }
 260   while (l)
 261     {
 262       c = getc(fp);
 263       if (c == EOF)
 264         break;
 265       *bp++ = c;
 266       l--;
 267     }
 268   if (l)
 269     memset(bp, 0, l);
 270   return blksize - l;
 271 }
 272
 273
 274 void
 275 MediaBlockList::reuseBlocks(FILE *wfp, string filename)
 276 {
 277   FILE *fp;
 278
 279   if (!chksumlen || (fp = fopen(filename.c_str(), "r")) == 0)
 280     return;
 281   size_t nblks = blocks.size();
 282   vector<bool> found;
 283   found.resize(nblks + 1);
 284   if (rsumlen && !rsums.empty())
 285     {
 286       size_t blksize = blocks[0].size;
 287       if (nblks == 1 && rsumpad && rsumpad > blksize)
 288         blksize = rsumpad;
 289       // create hash of checksums
 290       unsigned int hm = rsums.size() * 2;
 291       while (hm & (hm - 1))
 292         hm &= hm - 1;
 293       hm = hm * 2 - 1;
 294       if (hm < 16383)
 295         hm = 16383;
 296       unsigned int *ht = new unsigned int[hm + 1];
 297       memset(ht, 0, (hm + 1) * sizeof(unsigned int));
 298       for (unsigned int i = 0; i < rsums.size(); i++)
 299         {
 300           if (blocks[i].size != blksize && (i != nblks - 1 || rsumpad != blksize))
 301             continue;
 302           unsigned int r = rsums[i];
 303           unsigned int h = r & hm;
 304           unsigned int hh = 7;
 305           while (ht[h])
 306             h = (h + hh++) & hm;
 307           ht[h] = i + 1;
 308         }
 309
 310       unsigned char *buf = new unsigned char[blksize];
 311       unsigned char *buf2 = new unsigned char[blksize];
 312       size_t pushback = 0;
 313       unsigned char *pushbackp = 0;
 314       int bshift = 0;
 315       if ((blksize & (blksize - 1)) == 0)
 316         for (bshift = 0; size_t(1 << bshift) != blksize; bshift++)
 317           ;
 318       unsigned short a, b;
 319       a = b = 0;
 320       memset(buf, 0, blksize);
 321       bool eof = 0;
 322       bool init = 1;
 323       int sql = nblks > 1 && chksumlen < 16 ? 2 : 1;
 324       while (!eof)
 325         {
 326           for (size_t i = 0; i < blksize; i++)
 327             {
 328               int c;
 329               if (eof)
 330                 c = 0;
 331               else
 332                 {
 333                    if (pushback)
 334                     {
 335                       c = *pushbackp++;
 336                       pushback--;
 337                     }
 338                   else
 339                     c = getc(fp);
 340                   if (c == EOF)
 341                     {
 342                       eof = true;
 343                       c = 0;
 344                       if (!i || sql == 2)
 345                         break;
 346                     }
 347                 }
 348               int oc = buf[i];
 349               buf[i] = c;
 350               a += c - oc;
 351               if (bshift)
 352                 b += a - (oc << bshift);
 353               else
 354                 b += a - oc * blksize;
 355               if (init)
 356                 {
 357                   if (size_t(i) != blksize - 1)
 358                     continue;
 359                   init = 0;
 360                 }
 361               unsigned int r;
 362               if (rsumlen == 1)
 363                 r = ((unsigned int)b & 255);
 364               else if (rsumlen == 2)
 365                 r = ((unsigned int)b & 65535);
 366               else if (rsumlen == 3)
 367                 r = ((unsigned int)a & 255) << 16 | ((unsigned int)b & 65535);
 368               else
 369                 r = ((unsigned int)a & 65535) << 16 | ((unsigned int)b & 65535);
 370               unsigned int h = r & hm;
 371               unsigned int hh = 7;
 372               for (; ht[h]; h = (h + hh++) & hm)
 373                 {
 374                   size_t blkno = ht[h] - 1;
 375                   if (rsums[blkno] != r)
 376                     continue;
 377                   if (found[blkno])
 378                     continue;
 379                   if (sql == 2)
 380                     {
 381                       if (eof || blkno + 1 >= nblks)
 382                         continue;
 383                       pushback = fetchnext(fp, buf2, blksize, pushback, pushbackp);
 384                       pushbackp = buf2;
 385                       if (!pushback)
 386                         continue;
 387                       if (!checkRsum(blkno + 1, buf2, blksize))
 388                         continue;
 389                     }
 390                   if (!checkChecksumRotated(blkno, buf, blksize, i + 1))
 391                     continue;
 392                   if (sql == 2 && !checkChecksum(blkno + 1, buf2, blksize))
 393                     continue;
 394                   writeBlock(blkno, wfp, buf, blksize, i + 1, found);
 395                   if (sql == 2)
 396                     {
 397                       writeBlock(blkno + 1, wfp, buf2, blksize, 0, found);
 398                       pushback = 0;
 399                       blkno++;
 400                     }
 401                   while (!eof)
 402                     {
 403                       blkno++;
 404                       pushback = fetchnext(fp, buf2, blksize, pushback, pushbackp);
 405                       pushbackp = buf2;
 406                       if (!pushback)
 407                         break;
 408                       if (!checkRsum(blkno, buf2, blksize))
 409                         break;
 410                       if (!checkChecksum(blkno, buf2, blksize))
 411                         break;
 412                       writeBlock(blkno, wfp, buf2, blksize, 0, found);
 413                       pushback = 0;
 414                     }
 415                   init = false;
 416                   memset(buf, 0, blksize);
 417                   a = b = 0;
 418                   i = size_t(-1);       // start with 0 on next iteration
 419                   break;
 420                 }
 421             }
 422         }
 423       delete[] buf2;
 424       delete[] buf;
 425       delete[] ht;
 426     }
 427   else if (chksumlen >= 16)
 428     {
 429       // dummy variant, just check the checksums
 430       size_t bufl = 4096;
 431       off_t off = 0;
 432       unsigned char *buf = new unsigned char[bufl];
 433       for (size_t blkno = 0; blkno < blocks.size(); ++blkno)
 434         {
 435           if (off > blocks[blkno].off)
 436             continue;
 437           size_t blksize = blocks[blkno].size;
 438           if (blksize > bufl)
 439             {
 440               delete[] buf;
 441               bufl = blksize;
 442               buf = new unsigned char[bufl];
 443             }
 444           size_t skip = blocks[blkno].off - off;
 445           while (skip)
 446             {
 447               size_t l = skip > bufl ? bufl : skip;
 448               if (fread(buf, l, 1, fp) != 1)
 449                 break;
 450               skip -= l;
 451               off += l;
 452             }
 453           if (fread(buf, blksize, 1, fp) != 1)
 454             break;
 455           if (checkChecksum(blkno, buf, blksize))
 456             writeBlock(blkno, wfp, buf, blksize, 0, found);
 457           off += blksize;
 458         }
 459     }
 460   if (!found[nblks])
 461     return;
 462   // now throw out all of the blocks we found
 463   std::vector<MediaBlock> nblocks;
 464   std::vector<unsigned char> nchksums;
 465   std::vector<unsigned int> nrsums;
 466
 467   for (size_t blkno = 0; blkno < blocks.size(); ++blkno)
 468     {
 469       if (!found[blkno])
 470         {
 471           // still need it
 472           nblocks.push_back(blocks[blkno]);
 473           if (chksumlen && (blkno + 1) * chksumlen <= chksums.size())
 474             {
 475               nchksums.resize(nblocks.size() * chksumlen);
 476               memcpy(&nchksums[(nblocks.size() - 1) * chksumlen], &chksums[blkno * chksumlen], chksumlen);
 477             }
 478           if (rsumlen && (blkno + 1) <= rsums.size())
 479             nrsums.push_back(rsums[blkno]);
 480         }
 481     }
 482   blocks = nblocks;
 483   chksums = nchksums;
 484   rsums = nrsums;
 485 }
 486
 487 std::string
 488 MediaBlockList::asString() const
 489 {
 490   std::string s;
 491   size_t i, j;
 492
 493   if (filesize != off_t(-1))
 494     {
 495       long long size = filesize;
 496       s = zypp::str::form("[ BlockList, file size %lld\n", size);
 497     }
 498   else
 499     s = "[ BlockList, filesize unknown\n";
 500   if (!haveblocks)
 501     s += "  No block information\n";
 502   if (chksumpad)
 503     s += zypp::str::form("  Checksum pad %zd\n", chksumpad);
 504   if (rsumpad)
 505     s += zypp::str::form("  Rsum pad %zd\n", rsumpad);
 506   for (i = 0; i < blocks.size(); ++i)
 507     {
 508       long long off=blocks[i].off;
 509       long long size=blocks[i].size;
 510       s += zypp::str::form("  (%8lld, %8lld)", off, size);
 511       if (chksumlen && chksums.size() >= (i + 1) * chksumlen)
 512         {
 513           s += "  " + chksumtype + ":";
 514           for (j = 0; j < size_t(chksumlen); j++)
 515             s += zypp::str::form("%02hhx", chksums[i * chksumlen + j]);
 516         }
 517       if (rsumlen && rsums.size() > i)
 518         {
 519           s += "  RSUM:";
 520           s += zypp::str::form("%0*x", 2 * rsumlen, rsums[i]);
 521         }
 522       s += "\n";
 523     }
 524   s += "]";
 525   return s;
 526 }
 527
 528   } // namespace media
 529 } // namespace zypp
 530