| View previous topic :: View next topic |
| Author |
Message |
jjw
n00b
Joined: 20 Mar 2003
Posts: 59
Location: Austin, TX, US
|
 Posted: Sun Sep 21, 2003 5:08 am Post subject: gnome patches |
 |
|
| Slobo wrote: | Hello John, Brian and all other supporters (like me:))
Just want to ask are there any plans to put gnome fdtus when gnome 2.4.1 arrive in next month or two. (2.4.0-->2.4.1).
What happend with announce of establishing one test gentoo diff repository with ssh access? Any good news ? Any plans?
Thank you for your work and answer.
Ssl |
Thanks for your interest and your question. We probably will be able to make the patches for the next minor gnome update. We only have ftp access to sunsite.dk at the moment, so we're doing the best job we can with our limited time. We now have a IRC channel: #gdev-deltup.
---JJW |
|
| Back to top |
|
 |
dmcdonne
n00b
Joined: 01 Oct 2003
Posts: 1
Location: Wagga Wagga, NSW, Australia
|
| Posted: Wed Oct 01, 2003 11:30 pm Post subject: Patch requests |
|
|
I've just installed deltup and its great. Saved ages moving from KDE 3.1.3 to 3.1.4 (56k modems are so slow!).
Is there a way we can request a patch to be put on the sunsite FTP? Or can we somehow submit our own patch (to save others having to download the files)?
I'm running vanilla-sources at home and the latest version is 2.4.22. There is no patch for 2.4.21 -> 2.4.22 on the sunsite ftp, anyone care to make a patch and save me the download?
Cheers,
Dave |
|
| Back to top |
|
|
ferringb
Retired Dev
Joined: 03 Apr 2003
Posts: 357
|
| Posted: Thu Oct 02, 2003 12:01 am Post subject: |
|
|
Best bet would probably to be pop into irc, and join channel #gdev-deltup .
Those who can post files usually hang out there... |
|
| Back to top |
|
|
ssvb
Tux's lil' helper
Joined: 06 Nov 2003
Posts: 96
|
| Posted: Sat Nov 08, 2003 8:12 pm Post subject: |
|
|
By the way, looks like the best compression ratio for bdelta patches can be provided by PPMD compressor: http://packages.qa.debian.org/p/ppmd.html
It beats both GZIP and BZIP2 in my tests.
As deltup is still in development, can you consider using optional PPMD compression for it? |
|
| Back to top |
|
|
ferringb
Retired Dev
Joined: 03 Apr 2003
Posts: 357
|
| Posted: Mon Nov 10, 2003 3:45 am Post subject: |
|
|
Worth taking a look at also is http://sourceforge.net/projects/diffball , ebuild at https://bugs.gentoo.org/show_bug.cgi?id=29731 . In terms of uncompressed performance, it usually beats bdelta's patch size, usually by a significant margin. Mind you that's uncompressed, compression levels the playing field though, leaving diffball and bdelta at the very least equivalent.
Either way, PPMd is quite nifty, very low memory usage, good speed, good performance- I submitted an ebuild for it last night at https://bugs.gentoo.org/show_bug.cgi?id=33066 .
| ssvb wrote: | | Is deltup is still in development, can you consider using optional PPMD compression for it? |
No clue on it's status, jjw hasn't popped on irc in 5+ weeks- someone appears to be maintaining the patches on ftp.sunsite.dk though... |
|
| Back to top |
|
|
ssvb
Tux's lil' helper
Joined: 06 Nov 2003
Posts: 96
|
| Posted: Tue Nov 11, 2003 5:27 pm Post subject: |
|
|
Downloaded and tried it. It really produces smaller patches than bdelta. But I a bit surprised when got compressed bdelta patch smaller than the compressed diffball patch. I got this result on a package that has a lot of differences between tarballs. When the differences are minor, diffball is always better.
I tried to investigate this problem and make diffball patch in bdelta format. As expected, it was much smaller in uncompressed form. But the index table (the first part of patch file) was much bigger in diffball patch and maybe because of this diffball lost.
Here are my further thoughts, consider two files:
1: AAAAABBCCC
2: ABBBBBBBBBBBBBB
An optimal encoding seems obvious:
{ref AB}{ref BB}{ref BB}...{ref BB}
But this does not take into account compression applied later. In some cases it is possible that the following encoding will be better:
{ref AB}BBBBBBBBBBBBB
In fact, "{ref BB}{ref BB}..." part of the first encoding is just a simple implementation of LZSS algorithm. Specialized compressor can do this work better.
One of the differences between bdelta and diffball patch files when you look inside of them is that bdelta patch has many embedded areas filled with zero bytes, diffball seems to replace all of them by the references to the original file in the index table. But looks like the compressor can handle that zero areas better.
| Quote: |
Either way, PPMd is quite nifty, very low memory usage, good speed, good performance- I submitted an ebuild for it last night at https://bugs.gentoo.org/show_bug.cgi?id=33066 . [/qoute]
Good. I like this compressor. But there are bugreports on debian page that it is not 64-bit clean. I do not have access to 64-bit computer and can't investigate this. I looked at the sources and looks like it just needs some typedefs replaced. Can anybody try to fix it on 64-bit platform?
By the way, using -m switch you can give more memory to it (it uses 10MB by default). It will generally result in a better compression, but when used improperly (200MB for example), the archives will just be not extractable on the computers that do not have enough memory.
The -o switch also affects compression ratio (it selects PPM model order, 4 by default, usually good on average files). Trying different values in the interval 3 - 10, you can tune compression ratio for any particular file if you can wait for multilpe passes to complete.
| Quote: | | [quote="ssvb"]Is deltup is still in development, can you consider using optional PPMD compression for it? |
No clue on it's status, jjw hasn't popped on irc in 5+ weeks- someone appears to be maintaining the patches on ftp.sunsite.dk though... |
That's strange, bdelta looks like a very small program and not very difficult to debug and release a final version, delta patches would be a very good addition to Gentoo portage system.
In addition, it would be better to replace MD5 for the full tarball with MD5 of the decompressed data (tar file). It will not break compatibility with the existing system, but it will be easier to make delta patches.
What I mean is the following: when doing emerge, MD5 of the compressedl tarball is checked first. If it does not match, the check for decompressed tar file MD5 is performed. Only when both MD5 are different, the file will be considered corrupted. So MD5 values in the portage tree for the older packages will apply to the compressed file, MD5 values of the newer packages and avare of delta patches will apply to the decompressed file content and everyone will be happy. |
|
| Back to top |
|
|
ferringb
Retired Dev
Joined: 03 Apr 2003
Posts: 357
|
| Posted: Tue Nov 11, 2003 10:29 pm Post subject: |
|
|
| ssvb wrote: | | Downloaded and tried it. It really produces smaller patches than bdelta. But I was a bit surprised when got compressed bdelta patch smaller than the compressed diffball patch. |
You have no idea how much that has bugged the crap out of me... 
| ssvb wrote: | I got this result on a package that has a lot of differences between tarballs. When the differences are minor, diffball is always better.
I tried to investigate this problem and make diffball patch in bdelta format. As expected, it was much smaller in uncompressed form. But the index table (the first part of patch file) was much bigger in diffball patch and maybe because of this diffball lost. |
I've been doing some testing of it, but basically diffball and differ are too good at finding matches- the delta commands (index) ends up being a significantly larger portion of the patch in diffball generated patches vs bdelta generated patches.
Normally you would want as little add data included in the patch as possible, but when using compression, the desired ratio changes- the delta command compress rather poorly (pretty much regardless of any format I've dealt with), so the ratio for achieving the smallest patch changes.
Added, the current release doesn't have any of my format optimization code- it'll make a difference, although I'm not expecting a massive difference.
Basically it's a set of functions to decide whether it's cheaper to write out a copy command, or add data- as an example, you have ACC, with the middle copy being a copy of say 2 bytes (diffball and differ are capable of this)- it's much more efficient to convert the copy to an add, and write out one add and a copy rather then having the control overhead for an add, 2 byte copy, then another copy.
| ssvb wrote: | | One of the differences between bdelta and diffball patch files when you look inside of them is that bdelta patch has many embedded areas filled with zero bytes, diffball seems to replace all of them by the references to the original file in the index table. But looks like the compressor can handle that zero areas better. |
My default format, switching, was designed to be both simple and space efficient- bdelta format definition specifies int as being x byes, and all ints from that point on are stored using x bytes- the reason bdelta's patches are mostly zero's, is that A) jjw never fixed his code so that it choose a correct intsize (diffball's implementation can do this, but doesn't to maintain compatability), B) if a number could be stored in 1 byte but the intsize is 4 bytes, it's still written using 4 bytes.
Basically every format but bdelta's uses a variable 'intsize' w/ their commands. This produces smaller uncompressed patches, but diminishes the possible compression gain...
That's actually the reason I added the convert_delta binary- conversion to bdelta format for a patch that is going to be compressed saves usually a few kb.
| ssvb wrote: | | Good. I like this compressor. But there are bugreports on debian page that it is not 64-bit clean. I do not have access to 64-bit computer and can't investigate this. I looked at the sources and looks like it just needs some typedefs replaced. Can anybody try to fix it on 64-bit platform? |
I'd noticed that on the debian qa page- at the moment, the ebuild is set to just arch x86, although I'm intending on digging through the code to try and fix whatever issue there may be. Assuming it's not just typedef issues, I was thinking about coopting a g5 at work to test it...
| ssvb wrote: | | That's strange, bdelta looks like a very small program and not very difficult to debug and release a final version, delta patches would be a very good addition to Gentoo portage system. |
Bdelta is a nifty extension of the rsync algorithm, although the code is rough, and the lib interface needs work. JJW had said he was working on further improvements, but that was 2 months back...
As for deltup, I'd much rather see that implemented as scripts; deltup doesn't really do anything that requires it being written in C++...
I'd thought about adding support for fdtu (xdelta format w/ a deltup header), although I'm not sure how many people would actually need fdtu support...
| ssvb wrote: | In addition, it would be better to replace MD5 for the full tarball with MD5 of the decompressed data (tar file). It will not break compatibility with the existing system, but it will be easier to make delta patches.
What I mean is the following: when doing emerge, MD5 of the compressedl tarball is checked first. If it does not match, the check for decompressed tar file MD5 is performed. Only when both MD5 are different, the file will be considered corrupted. So MD5 values in the portage tree for the older packages will apply to the compressed file, MD5 values of the newer packages and avare of delta patches will apply to the decompressed file content and everyone will be happy. |
Heh, I'd actually proposed that back around june on the dev-ml and in the forums at https://forums.gentoo.org/viewtopic.php?t=59991 . Added benefit of having 2 md5's in a digest is that a user could store the file in whatever format they choose, say converting all gzip to bzip2 for that 5-10% space saving.
I've been working on an addition to portage for distfile diff'ing, along w/ the uncompressed md5 support... if you're curious, you can either track me down through the forums (I watch this, and a few other distfile diff'ing threads), or much better, through irc. I'm usually on #gentoo as ferringb...
Side note, another nifty little delta compression prog is bsdiff- http://daemonlogy.net/bsdiff, and I've added an ebuild for it available at https://bugs.gentoo.org/show_bug.cgi?id=33100 .
It uses a suffix tree to represent the source file, which in terms of delta size, should beat the crap out of diffball- downside is the memory usage for the suffix tree is quite insane... Worth taking a look, although I'd avoid trying it w/ files above 50mb if you don't have 512mb of ram... |
|
| Back to top |
|
|
Slammer
Bodhisattva
Joined: 28 Mar 2003
Posts: 270
Location: Greece
|
| Posted: Sun Nov 30, 2003 2:51 pm Post subject: |
|
|
As a edelta user, I want to thank jjw for this utility.
It is saving hours of downloading from my dialup time.
One suggestion only, please try to provide fdtu's for the large sources first, lets say above 2M. Dont spend your capacity for small diffs.
Keep on you great work! Thanks!
_________________
Keep Slamming... |
|
| Back to top |
|
|
Ssl
Apprentice
Joined: 21 Feb 2003
Posts: 178
Location: Serbia
|
| Posted: Mon Dec 15, 2003 1:52 am Post subject: |
|
|
Hello all,
Just uploaded some new diffs to ftp://sunsite.dk/projects/deltup/patchfiles/ . Those are:
| Code: | sys-kernel/vanilla-sources-2.4.23
dev-libs/libxml2-2.6.3
dev-libs/libxslt-1.1.1
app-office/gnumeric-1.2.2
net-print/cups-1.1.20
gnome-base/ORBit2-2.8.3
net-ftp/gftp-2.0.16-r1
|
and not yet in portage | Code: | | sys-devel/gettext-0.13 |
Cheers, Ssl |
|
| Back to top |
|
|
Ssl
Apprentice
Joined: 21 Feb 2003
Posts: 178
Location: Serbia
|
| Posted: Thu Mar 04, 2004 11:23 am Post subject: |
|
|
Hi,
I updated some bigger apps found in my distfiles dir. and made several diffs.
Those are: | Code: | | vanilla-sources, development-sources, gcc, mozilla, libxml2, libxslt |
and some unstable gnome stuff from breakmygentoo.net as
PS. ferringb can you post me a link to development release of diffball or send it privately - I completely lost our irc log and obviously hadn't much time recently.
Cheers,
Ssl |
|
| Back to top |
|
|
[UK]Superdude
Tux's lil' helper
Joined: 22 Jul 2002
Posts: 149
Location: Adelaide, Australia
|
|
| Back to top |
|
|
ferringb
Retired Dev
Joined: 03 Apr 2003
Posts: 357
|
| Posted: Mon Apr 05, 2004 12:22 am Post subject: |
|
|
| [UK]Superdude wrote: | | Code: |
*
* Please note that deltup will be removed from portage
* in the near future. Development on deltup has stopped, although
* patches are being generated in the interim until another distfile
* patching system is ready for testing.
*
* further info will be available at
* http://www.gentoo.org/proj/en/glep/glep-0009.html
|
|
Actually, that was my doing .
Well, deltup (in my books) is developmentally dead- it's taken far longer then I had liked, but I've been nailing down my own differencer implementation that natively supports multiple formats- bsdiff, xdelta (also, deltup's fdtu format that is wrapped xdelta output), gdiff4, and bdelta.
I'm *finally* getting to the point where I've got all of the features I want pretty much finished- applying multiple patches in a single run (without creating temp files), reconstructing from compressed srcs (eg, no need to decompress the patches/reference file), and a flexible setup for dropping new formats/differencers in.
I'm finishing off diffball, but in the meantime I've also got a glep up for integration patching functionality into portage-> glep 25, Distfile Patching Support.
I've also fired off an email to gentoo-dev's mailing list regarding it- any feedback would be greatly appreciated |
|
| Back to top |
|
|
scientica
n00b
Joined: 22 Apr 2005
Posts: 2
Location: Sweden
|
| Posted: Fri Apr 22, 2005 2:38 pm Post subject: |
|
|
Maybe this isn't the correct place, but I trust someone will slap me right with a herring if so 
In this GELP I read
| Quote: | | Further, the ability to reverse a unified patch is due to the fact the diff includes both the original line, and the modified line. The author isn't aware of any binary differencer that is able to create patches the can be reversed- basically they're unidirectional, the patch that is generated can only be used to upgrade or downgrade the version, not both. The plus side of this limitation is a significantly decreased patch size. |
I just thought, wouldn't it be possible to have the difference beeing an xor of the "old" and "new" byte? ie:
OLD xor NEW = DIFF
and then simply when patching the "diff places" are xor'd, it should work both ways (I assume you know how the xor works), I'm not sure how to solve sections where "sizeof(OLD)!=sizeof(NEW)", but I guess some nifty header magic or such (if the diff sections are small structs like "[ secton_number | value_of_X | sum_of_x_minus_y | position/offset_in_old_file | position/offset_in_new_file | data[size] ]") could solve it via eg "saying" section N is X bytes/bits long and Y bytes/bits shorter [making the first (X-Y) bytes/bits xor bits, the remaining is the added (or removed it the sum is <0 - if the remaining bytes could be those to be removed (if the patch is reversed they'd be added -- unless I'm thinking wrong on reversed all needed is to change the sign of (X-Y) ))].
NB: I've not made any deeper analyze of this idea flash, or checked if someone has tried it. Or for that matter taken any look on how binary diff works.
wonder if any of the above made any sence... |
|
| Back to top |
|
|
ferringb
Retired Dev
Joined: 03 Apr 2003
Posts: 357
|
| Posted: Tue Apr 26, 2005 9:30 pm Post subject: |
|
|
Not easily doable. Part of the problem is that of orientation of the delta (this is going to be a fun explanation I can tell already . gnudiff deltas segments are around the 'adds' and deletes. So for them, doing an xor might make the patch more compressable (harder to read however, nuking the main benefit of unidiff). Bindiffer's work a bit differently, basically they treat the reference version as the soure for a dictionary, and do something akin to dict. compression of the versioned file. What I'm getting at is that the output isn't 'orientated' around just the change, like gnudiff (lcs alg moreso). Remember gnudiff doesn't even have a copy command, just add/delete.
bindiffers can, and do copy in a non linear fashion from the ref file. The copies from the reference file may be all over the place, while with gnudiff, it's linear, always increasing. So... with gnudiff, you could pull it off, because it's something of a linear transformation of the ref file into the ver file.
Actual bindiffers only reference *portions* of the ref file for copies. Their is the potential for large gaps in the ref file, which would require bundling the data of those gaps so you could go in reverse. If you did that, you'd drastically increase the size of the generated delta though.
So really the issue for going in reverse is that you would have to bundle a lot of extra data for the ref file, that isn't needed. Regarding using xor, there is actually a differencer/format that uses something akin; it specifies a copy, then an add mask/overlay (add each byte of the 'overlay' to the copy data, writing the resultant byte mod 256 to disk)- bsdiff does this. Most implementations for command syntax have just copy, and add. Bsdiff has copy, add, and add overlay (iirc). Does make it a bit more compressable, although writing an alg that can identify the best segment of a file to use for an overlay source is rather hard... |
|
| Back to top |
|
|
scientica
n00b
Joined: 22 Apr 2005
Posts: 2
Location: Sweden
|
| Posted: Wed Apr 27, 2005 8:31 pm Post subject: |
|
|
I see, interesting, I thought bindiffer's worked like "plain text" ones (but using bytes rather than chars/strings (even if they're the same data types in the low lever (bits in a byte/group ) - maybe that part about bytes!=chars!=string made somekind of sense to people locked up in High Level TypeCast Coding - honeslty one those words left my brain they sounded off  )).
I think unidiffs are nice, I like the part about them beeing "human readable" - but for binaries I think that's a bit of luxury one must give up.
Just another of my half/fully crazy ideas follows below, if you're worried about your mental health or got a weak heart I'd raise a warning that bellow might not be a good idea to read
| Code: | Imagine a file which is composed of 2 struct types in the following manner:
[diff_file [ diff ]+ ]+ (in "human": one or more diff _file structs followed by one or more diff structs)
the struct could look something like these
struct diff_file {
header_size interger_data_type; // size of this diff_file struct
old_file_date date_data_type;
new_file_date date_data_type;
old_file_name zero_terminated_string;
new_file_name zero_terminated_string;
old_minus_new_file_size interger_data_type; // the change in file size
diff_count interger_data_type; // numver of diff sturcts that follows this diff_file header.
diff_size interger_data_type; // the size of the diff structs that follows - so we can simply add this value with header_size to get to next diff_file struct (or EOF).
}
struct diff {
size_of_this_difference_block interge_data_type; // size of this struct
old_file_offset interger_data_type;
new_file_offset interger_data_type;
delta_size interge_data_type; // if >0 remainder_part is added, else it's the subtracted bytes (if we reverse we'd add them).
xor_data_part raw_byte_data_type;
remainder_data_part raw_byte_data_type;
}
where a "diff file" could look like this: (I hope you can interprent this scientica-is-a-nut-case-pseudo-code, "[]" denotes a 'struct member', and "{}" a struct, 'this' refers to the {struct} it's in, \0 is the null terminator - it's all a series of bytes, with no "\n" newlines - they're just there to limit the line length below. oh, and "(X xor Y)" is a single byte (the result of 'X xor Y') )
-------------
{[the size of this header][old files epoch date]
[new files epoch date][old_file.ext\0][new_file.ext\0][1][1]
[the size of the following diff blocks]}
{[size of this block][0][0][1]
[(A xor D)(B xor E)(C xor F)][G]}
-------------
here's a semi-fake "hexdump" of above:
size of data types: 32-bit = 1 dword = 4 hex numbers
(with the exception of strings which are 8-bit = byte)
0000 | 00 00 01 4e 12 34 56 78 ab cd ef 00 | ............
000C | 6f 6c 64 5f 66 69 6c 65 2e 65 78 74 | old_file.ext
0018 | 00 6e 65 77 5f 66 69 6c 65 2e 65 78 | .new_file.ex
0024 | 74 00 00 00 00 01 00 00 00 01 00 00 | t...........
0030 | 00 1a 00 00 00 1a 00 00 00 00 00 00 | ............
003C | 00 00 00 00 00 01 05 07 05 47 | .........G
-------------
old_file.ext is just the string: "ABC"
and new_file.ext is the string "DEFG"
then if we make the diff be compressed with some nice compression algo I think it's possible to shrink the diff "a few bits". The char set of the file names should be unicode really, but, for the sake of laziness and "simplicity" (you may laught) 8-bit ASCII will do for now.
Also, it might be nice to add some md5/sha1 field for the new and old files - so the intergity of the patched file can be checked (as well as checking so that the input file is ok).
As I said above, this is just a(nother) wild idea, ie, I haven't got a clue on how to handle the new_file_offset - ie should it be the offset at the time we "get to that part" (ie, the earlier adds and subs is counted). |
Any comments/questions about the madness above? or is it so mad that I just should silently crawl back to the stone I came from and return the air I got from somewhere?
[edit]yet a thought, maybe the data_part could be "divided" into something like /[(dq)qd]?words/ in stead of bytes for optimizations, even if it's possible to do some SIMD magic with 1-16 bytes I'm not sure if there's a xor SIMD for 16 bytes...[/edit] |
|
| Back to top |
|
|
ferringb
Retired Dev
Joined: 03 Apr 2003
Posts: 357
|
| Posted: Wed Apr 27, 2005 10:51 pm Post subject: |
|
|
Unicode (the glyph representation) doesn't matter at all. The reconstruction must be a perfect copy, as such it works at the byte level (or N bytes, or bits, however you write the differencer).
Regarding storing date, it's uneeded. If you're after verification that the reference file is what the patch applies against, a chksum + size is the route to go. Verification your differencer/reconstructor isn't whacked, have a versioned chksum+size field also. Personally I drop 'em, cause you should know what you're patching
Regarding rest of the post, guessing you're talking of an alternative format for gnudiff... otherwise, my point about dumping a buttload of extra data from the ref file into the patch and bloating up the deltas size stands |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
Portage & Programming
