1 // Copyright (c) 2014 Anthony Towns
3 // This program is free software; you can redistribute it and/or modify
4 // it under the terms of the GNU General Public License as published by
5 // the Free Software Foundation; either version 2 of the License, or
6 // (at your option) any later version.
10 #include <apt-pkg/init.h>
11 #include <apt-pkg/fileutl.h>
12 #include <apt-pkg/error.h>
13 #include <apt-pkg/acquire-method.h>
14 #include <apt-pkg/strutl.h>
15 #include <apt-pkg/hashes.h>
16 #include <apt-pkg/configuration.h>
17 #include "aptmethod.h"
35 #define BLOCK_SIZE (512*1024)
43 explicit MemBlock(size_t size
) : size(size
), next(NULL
)
45 free
= start
= new char[size
];
48 size_t avail(void) { return size
- (free
- start
); }
53 free
= start
= new char[BLOCK_SIZE
];
69 char *add_easy(char *src
, size_t len
, char *last
)
72 for (MemBlock
*k
= this; k
; k
= k
->next
) {
73 if (k
->free
== last
) {
74 if (len
<= k
->avail()) {
75 char *n
= k
->add(src
, len
);
83 } else if (last
>= start
&& last
< free
) {
91 char *add(char *src
, size_t len
) {
94 if (len
> BLOCK_SIZE
) {
95 next
= new MemBlock(len
);
100 return next
->add(src
, len
);
104 memcpy(dst
, src
, len
);
112 * 1. write out <offset> lines unchanged
113 * 2. skip <del_cnt> lines from source
114 * 3. write out <add_cnt> lines (<add>/<add_len>)
118 size_t add_cnt
; /* lines */
119 size_t add_len
; /* bytes */
122 explicit Change(size_t off
)
125 del_cnt
= add_cnt
= add_len
= 0;
129 /* actually, don't write <lines> lines from <add> */
130 void skip_lines(size_t lines
)
133 char *s
= (char*) memchr(add
, '\n', add_len
);
136 add_len
-= (s
- add
);
141 assert(add_cnt
== 0);
152 std::list
<struct Change
> changes
;
153 std::list
<struct Change
>::iterator where
;
154 size_t pos
; // line number is as far left of iterator as possible
156 bool pos_is_okay(void) const
160 std::list
<struct Change
>::const_iterator x
;
161 for (x
= changes
.begin(); x
!= where
; ++x
) {
162 assert(x
!= changes
.end());
163 cpos
+= x
->offset
+ x
->add_cnt
;
173 where
= changes
.end();
177 std::list
<struct Change
>::iterator
begin(void) { return changes
.begin(); }
178 std::list
<struct Change
>::iterator
end(void) { return changes
.end(); }
180 std::list
<struct Change
>::reverse_iterator
rbegin(void) { return changes
.rbegin(); }
181 std::list
<struct Change
>::reverse_iterator
rend(void) { return changes
.rend(); }
183 void add_change(Change c
) {
184 assert(pos_is_okay());
185 go_to_change_for(c
.offset
);
186 assert(pos
+ where
->offset
== c
.offset
);
188 delete_lines(c
.del_cnt
);
189 assert(pos
+ where
->offset
== c
.offset
);
191 assert(pos_is_okay());
192 if (where
->add_len
> 0)
194 assert(where
->add_len
== 0 && where
->add_cnt
== 0);
196 where
->add_len
= c
.add_len
;
197 where
->add_cnt
= c
.add_cnt
;
200 assert(pos_is_okay());
202 assert(pos_is_okay());
208 while (where
->offset
== 0 && where
!= changes
.begin()) {
211 std::list
<struct Change
>::iterator next
= where
;
214 while (next
!= changes
.end() && next
->offset
== 0) {
215 where
->del_cnt
+= next
->del_cnt
;
217 if (next
->add
== NULL
) {
218 next
= changes
.erase(next
);
219 } else if (where
->add
== NULL
) {
220 where
->add
= next
->add
;
221 where
->add_len
= next
->add_len
;
222 where
->add_cnt
= next
->add_cnt
;
223 next
= changes
.erase(next
);
230 void go_to_change_for(size_t line
)
232 while(where
!= changes
.end()) {
237 if (pos
+ where
->offset
+ where
->add_cnt
<= line
) {
241 // line is somewhere in this slot
242 if (line
< pos
+ where
->offset
) {
244 } else if (line
== pos
+ where
->offset
) {
252 /* it goes before this patch */
256 void new_change(void) { insert(where
->offset
); }
258 void insert(size_t offset
)
260 assert(pos_is_okay());
261 assert(where
== changes
.end() || offset
<= where
->offset
);
262 if (where
!= changes
.end())
263 where
->offset
-= offset
;
264 changes
.insert(where
, Change(offset
));
266 assert(pos_is_okay());
269 void split(size_t offset
)
271 assert(pos_is_okay());
273 assert(where
->offset
< offset
);
274 assert(offset
< where
->offset
+ where
->add_cnt
);
276 size_t keep_lines
= offset
- where
->offset
;
278 Change
before(*where
);
282 where
->skip_lines(keep_lines
);
284 before
.add_cnt
= keep_lines
;
285 before
.add_len
-= where
->add_len
;
287 changes
.insert(where
, before
);
289 assert(pos_is_okay());
292 void delete_lines(size_t cnt
)
294 std::list
<struct Change
>::iterator x
= where
;
295 assert(pos_is_okay());
306 if (x
== changes
.end()) {
314 where
->del_cnt
+= del
;
317 assert(pos_is_okay());
321 assert(pos_is_okay());
323 pos
-= where
->offset
+ where
->add_cnt
;
324 assert(pos_is_okay());
328 assert(pos_is_okay());
329 pos
+= where
->offset
+ where
->add_cnt
;
331 assert(pos_is_okay());
336 FileChanges filechanges
;
339 static bool retry_fwrite(char *b
, size_t l
, FileFd
&f
, Hashes
*hash
)
341 if (f
.Write(b
, l
) == false)
344 hash
->Add((unsigned char*)b
, l
);
348 static void dump_rest(FileFd
&o
, FileFd
&i
, Hashes
*hash
)
350 char buffer
[BLOCK_SIZE
];
351 unsigned long long l
= 0;
352 while (i
.Read(buffer
, sizeof(buffer
), &l
)) {
353 if (l
==0 || !retry_fwrite(buffer
, l
, o
, hash
))
358 static void dump_lines(FileFd
&o
, FileFd
&i
, size_t n
, Hashes
*hash
)
360 char buffer
[BLOCK_SIZE
];
362 if (i
.ReadLine(buffer
, sizeof(buffer
)) == NULL
)
364 size_t const l
= strlen(buffer
);
365 if (l
== 0 || buffer
[l
-1] == '\n')
367 retry_fwrite(buffer
, l
, o
, hash
);
371 static void skip_lines(FileFd
&i
, int n
)
373 char buffer
[BLOCK_SIZE
];
375 if (i
.ReadLine(buffer
, sizeof(buffer
)) == NULL
)
377 size_t const l
= strlen(buffer
);
378 if (l
== 0 || buffer
[l
-1] == '\n')
383 static void dump_mem(FileFd
&o
, char *p
, size_t s
, Hashes
*hash
) {
384 retry_fwrite(p
, s
, o
, hash
);
389 bool read_diff(FileFd
&f
, Hashes
* const h
)
391 char buffer
[BLOCK_SIZE
];
392 bool cmdwanted
= true;
394 Change
ch(std::numeric_limits
<size_t>::max());
395 if (f
.ReadLine(buffer
, sizeof(buffer
)) == NULL
)
396 return _error
->Error("Reading first line of patchfile %s failed", f
.Name().c_str());
404 s
= strtoul(buffer
, &m
, 10);
405 if (unlikely(m
== buffer
|| s
== std::numeric_limits
<unsigned long>::max() || errno
!= 0))
406 return _error
->Error("Parsing patchfile %s failed: Expected an effected line start", f
.Name().c_str());
407 else if (*m
== ',') {
409 e
= strtol(m
, &c
, 10);
410 if (unlikely(m
== c
|| e
== std::numeric_limits
<unsigned long>::max() || errno
!= 0))
411 return _error
->Error("Parsing patchfile %s failed: Expected an effected line end", f
.Name().c_str());
413 return _error
->Error("Parsing patchfile %s failed: Effected lines end %lu is before start %lu", f
.Name().c_str(), e
, s
);
419 return _error
->Error("Parsing patchfile %s failed: Effected line is after previous effected line", f
.Name().c_str());
430 if (unlikely(s
== 0))
431 return _error
->Error("Parsing patchfile %s failed: Change command can't effect line zero", f
.Name().c_str());
437 ch
.del_cnt
= e
- s
+ 1;
440 if (unlikely(s
== 0))
441 return _error
->Error("Parsing patchfile %s failed: Delete command can't effect line zero", f
.Name().c_str());
443 ch
.del_cnt
= e
- s
+ 1;
447 filechanges
.add_change(ch
);
450 return _error
->Error("Parsing patchfile %s failed: Unknown command", f
.Name().c_str());
452 } else { /* !cmdwanted */
453 if (strcmp(buffer
, ".\n") == 0) {
455 filechanges
.add_change(ch
);
461 last
= ch
.add
+ ch
.add_len
;
463 add
= add_text
.add_easy(buffer
, l
, last
);
469 filechanges
.add_change(ch
);
472 ch
.offset
+= ch
.add_cnt
;
479 } while(f
.ReadLine(buffer
, sizeof(buffer
)));
483 void write_diff(FileFd
&f
)
485 unsigned long long line
= 0;
486 std::list
<struct Change
>::reverse_iterator ch
;
487 for (ch
= filechanges
.rbegin(); ch
!= filechanges
.rend(); ++ch
) {
488 line
+= ch
->offset
+ ch
->del_cnt
;
491 for (ch
= filechanges
.rbegin(); ch
!= filechanges
.rend(); ++ch
) {
492 std::list
<struct Change
>::reverse_iterator mg_i
, mg_e
= ch
;
493 while (ch
->del_cnt
== 0 && ch
->offset
== 0)
497 if (ch
->add_cnt
> 0) {
498 if (ch
->del_cnt
== 0) {
499 strprintf(buf
, "%llua\n", line
);
500 } else if (ch
->del_cnt
== 1) {
501 strprintf(buf
, "%lluc\n", line
+1);
503 strprintf(buf
, "%llu,%lluc\n", line
+1, line
+ch
->del_cnt
);
505 f
.Write(buf
.c_str(), buf
.length());
509 dump_mem(f
, mg_i
->add
, mg_i
->add_len
, NULL
);
510 } while (mg_i
-- != mg_e
);
513 f
.Write(buf
.c_str(), buf
.length());
514 } else if (ch
->del_cnt
== 1) {
515 strprintf(buf
, "%llud\n", line
+1);
516 f
.Write(buf
.c_str(), buf
.length());
517 } else if (ch
->del_cnt
> 1) {
518 strprintf(buf
, "%llu,%llud\n", line
+1, line
+ch
->del_cnt
);
519 f
.Write(buf
.c_str(), buf
.length());
525 void apply_against_file(FileFd
&out
, FileFd
&in
, Hashes
*hash
= NULL
)
527 std::list
<struct Change
>::iterator ch
;
528 for (ch
= filechanges
.begin(); ch
!= filechanges
.end(); ++ch
) {
529 dump_lines(out
, in
, ch
->offset
, hash
);
530 skip_lines(in
, ch
->del_cnt
);
531 dump_mem(out
, ch
->add
, ch
->add_len
, hash
);
533 dump_rest(out
, in
, hash
);
538 class RredMethod
: public aptMethod
{
543 std::string FileName
;
544 HashStringList ExpectedHashes
;
545 PDiffFile(std::string
const &FileName
, HashStringList
const &ExpectedHashes
) :
546 FileName(FileName
), ExpectedHashes(ExpectedHashes
) {}
549 HashStringList
ReadExpectedHashesForPatch(unsigned int const patch
, std::string
const &Message
)
551 HashStringList ExpectedHashes
;
552 for (char const * const * type
= HashString::SupportedHashes(); *type
!= NULL
; ++type
)
555 strprintf(tagname
, "Patch-%d-%s-Hash", patch
, *type
);
556 std::string
const hashsum
= LookupTag(Message
, tagname
.c_str());
557 if (hashsum
.empty() == false)
558 ExpectedHashes
.push_back(HashString(*type
, hashsum
));
560 return ExpectedHashes
;
564 virtual bool URIAcquire(std::string
const &Message
, FetchItem
*Itm
) APT_OVERRIDE
{
565 Debug
= _config
->FindB("Debug::pkgAcquire::RRed", false);
567 std::string Path
= Get
.Host
+ Get
.Path
; // rred:/path - no host
570 Res
.Filename
= Itm
->DestFile
;
571 if (Itm
->Uri
.empty())
573 Path
= Itm
->DestFile
;
574 Itm
->DestFile
.append(".result");
578 std::vector
<PDiffFile
> patchfiles
;
581 if (FileExists(Path
+ ".ed") == true)
583 HashStringList
const ExpectedHashes
= ReadExpectedHashesForPatch(0, Message
);
584 std::string
const FileName
= Path
+ ".ed";
585 if (ExpectedHashes
.usable() == false)
586 return _error
->Error("No hashes found for uncompressed patch: %s", FileName
.c_str());
587 patchfiles
.push_back(PDiffFile(FileName
, ExpectedHashes
));
591 _error
->PushToStack();
592 std::vector
<std::string
> patches
= GetListOfFilesInDir(flNotFile(Path
), "gz", true, false);
593 _error
->RevertToStack();
595 std::string
const baseName
= Path
+ ".ed.";
596 unsigned int seen_patches
= 0;
597 for (std::vector
<std::string
>::const_iterator p
= patches
.begin();
598 p
!= patches
.end(); ++p
)
600 if (p
->compare(0, baseName
.length(), baseName
) == 0)
602 HashStringList
const ExpectedHashes
= ReadExpectedHashesForPatch(seen_patches
, Message
);
603 if (ExpectedHashes
.usable() == false)
604 return _error
->Error("No hashes found for uncompressed patch %d: %s", seen_patches
, p
->c_str());
605 patchfiles
.push_back(PDiffFile(*p
, ExpectedHashes
));
611 std::string patch_name
;
612 for (std::vector
<PDiffFile
>::iterator I
= patchfiles
.begin();
613 I
!= patchfiles
.end();
616 patch_name
= I
->FileName
;
618 std::clog
<< "Patching " << Path
<< " with " << patch_name
622 Hashes
patch_hash(I
->ExpectedHashes
);
623 // all patches are compressed, even if the name doesn't reflect it
624 if (p
.Open(patch_name
, FileFd::ReadOnly
, FileFd::Gzip
) == false ||
625 patch
.read_diff(p
, &patch_hash
) == false)
627 _error
->DumpErrors(std::cerr
, GlobalError::DEBUG
, false);
631 HashStringList
const hsl
= patch_hash
.GetHashStringList();
632 if (hsl
!= I
->ExpectedHashes
)
633 return _error
->Error("Hash Sum mismatch for uncompressed patch %s", patch_name
.c_str());
637 std::clog
<< "Applying patches against " << Path
638 << " and writing results to " << Itm
->DestFile
642 if (inp
.Open(Path
, FileFd::ReadOnly
, FileFd::Extension
) == false)
644 std::cerr
<< "FAILED to open inp " << Path
<< std::endl
;
645 return _error
->Error("Failed to open inp %s", Path
.c_str());
647 if (out
.Open(Itm
->DestFile
, FileFd::WriteOnly
| FileFd::Create
| FileFd::BufferedWrite
, FileFd::Extension
) == false)
649 std::cerr
<< "FAILED to open out " << Itm
->DestFile
<< std::endl
;
650 return _error
->Error("Failed to open out %s", Itm
->DestFile
.c_str());
653 Hashes
hash(Itm
->ExpectedHashes
);
654 patch
.apply_against_file(out
, inp
, &hash
);
660 std::clog
<< "rred: finished file patching of " << Path
<< "." << std::endl
;
663 struct stat bufbase
, bufpatch
;
664 if (stat(Path
.c_str(), &bufbase
) != 0 ||
665 stat(patch_name
.c_str(), &bufpatch
) != 0)
666 return _error
->Errno("stat", _("Failed to stat"));
668 struct timeval times
[2];
669 times
[0].tv_sec
= bufbase
.st_atime
;
670 times
[1].tv_sec
= bufpatch
.st_mtime
;
671 times
[0].tv_usec
= times
[1].tv_usec
= 0;
672 if (utimes(Itm
->DestFile
.c_str(), times
) != 0)
673 return _error
->Errno("utimes",_("Failed to set modification time"));
675 if (stat(Itm
->DestFile
.c_str(), &bufbase
) != 0)
676 return _error
->Errno("stat", _("Failed to stat"));
678 Res
.LastModified
= bufbase
.st_mtime
;
679 Res
.Size
= bufbase
.st_size
;
680 Res
.TakeHashes(hash
);
687 RredMethod() : aptMethod("rred", "2.0",SingleInstance
| SendConfig
), Debug(false) {}
690 int main(int argc
, char **argv
)
693 bool just_diff
= true;
702 // Usage: rred -t input output diff ...
703 if (argc
> 1 && strcmp(argv
[1], "-t") == 0) {
704 // Read config files so we see compressors.
705 pkgInitConfig(*_config
);
709 } else if (argc
> 1 && strcmp(argv
[1], "-f") == 0) {
716 for (; i
< argc
; i
++) {
718 if (p
.Open(argv
[i
], FileFd::ReadOnly
) == false) {
719 _error
->DumpErrors(std::cerr
);
722 if (patch
.read_diff(p
, NULL
) == false)
724 _error
->DumpErrors(std::cerr
);
731 std::cerr
<< "Patching " << argv
[2] << " into " << argv
[3] << "\n";
732 inp
.Open(argv
[2], FileFd::ReadOnly
,FileFd::Extension
);
733 out
.Open(argv
[3], FileFd::WriteOnly
| FileFd::Create
| FileFd::BufferedWrite
, FileFd::Extension
);
734 patch
.apply_against_file(out
, inp
);
736 } else if (just_diff
) {
738 out
.OpenDescriptor(STDOUT_FILENO
, FileFd::WriteOnly
| FileFd::Create
);
739 patch
.write_diff(out
);
743 out
.OpenDescriptor(STDOUT_FILENO
, FileFd::WriteOnly
| FileFd::Create
| FileFd::BufferedWrite
);
744 inp
.OpenDescriptor(STDIN_FILENO
, FileFd::ReadOnly
);
745 patch
.apply_against_file(out
, inp
);