libzypp  17.14.0
MediaBlockList.cc
Go to the documentation of this file.
1 /*---------------------------------------------------------------------\
2 | ____ _ __ __ ___ |
3 | |__ / \ / / . \ . \ |
4 | / / \ V /| _/ _/ |
5 | / /__ | | | | | | |
6 | /_____||_| |_| |_| |
7 | |
8 \---------------------------------------------------------------------*/
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 
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
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 
std::string asString(const DefaultIntegral< Tp, TInitial > &obj)
Compute Message Digests (MD5, SHA1 etc)
Definition: Digest.h:45
Definition: Arch.h:344
std::string form(const char *format,...) __attribute__((format(printf
Printf style construction of std::string.
Definition: String.cc:36
std::vector< unsigned char > digestVector()
get vector of unsigned char representation of the digest
Definition: Digest.cc:212
static size_t fetchnext(FILE *fp, unsigned char *bp, size_t blksize, size_t pushback, unsigned char *pushbackp)
a single block from the blocklist, consisting of an offset and a size
bool create(const std::string &name)
initialize creation of a new message digest
Definition: Digest.cc:156
Easy-to use interface to the ZYPP dependency resolver.
Definition: CodePitfalls.doc:1
bool update(const char *bytes, size_t len)
feed data into digest computation algorithm
Definition: Digest.cc:230