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