Linked by Thom Holwerda on Thu 16th Jul 2009 21:44 UTC
Google One of the more controversial features of Google's Chrome/Chromium web browser is the way it handles updates. Contrary to other browsers, updates on Chrome are installed silently and automatically, without asking for the user's consent. While convenient and effective, it was also a security risk and sometimes it slowed people's machines down. Google now proposes a fix called Courgette.
Order by: Score:
Layman explanation attempt
by kragil on Thu 16th Jul 2009 22:05 UTC
kragil
Member since:
2006-01-04

It basically looks at the machine code of the new and the old executable. Adjusts/aligns the matching parts and then does a diff.(Not 100% correct, but you get the idea)
Simple but really genius .. just like their page rank algorithm... I am still pissed that I didn't come up with something that obvious .. damn .. I could really use all that money.(I would spent most of it on cars, women and drugs. The rest I would squander.)

Edited 2009-07-16 22:06 UTC

Reply Score: 6

RE: Layman explanation attempt
by kaiwai on Thu 16th Jul 2009 22:17 UTC in reply to "Layman explanation attempt "
kaiwai Member since:
2005-07-06

It basically looks at the machine code of the new and the old executable. Adjusts/aligns the matching parts and then does a diff.(Not 100% correct, but you get the idea)

Simple but really genius .. just like their page rank algorithm... I am still pissed that I didn't come up with something that obvious .. damn .. I could really use all that money.(I would spent most of it on cars, women and drugs. The rest I would squander.)


From what I understand, this isn't particularly new - Linux and Windows have delta updates which are binary diffs; I remember Microsoft before Microsoft developed a technology to reduce the size of updates; where a 1MB update might have a 500K file which is only around 30K difference between the old and new file.

Reply Score: 2

galvanash Member since:
2006-01-25

This is quite a bit beyond a simple binary diff. The approach currently taken (afaik) is just generating a simple diff and compressing it using zip/bzip/whatever.

This is doing what amounts to a full disassembly, complete with a symbol table, prior to compression.

In spirit, this is the same approach that the png format uses to get such high compression rates. Png uses a loss-less filtering pass that converts image data into a format that is more compressible by zlib. The filtering algorithms themselves are not compressing anything - they often make the data bigger, but they create a representation of the data that zlib can compress much more than the original data, resulting in a net gain. What Google has done is essentially the same thing, the disassembly step is used as a filtering pass to make the data more compressible.

Reply Score: 2

StephenBeDoper Member since:
2005-07-06

Exactly - isn't that the way that that rsync has worked for years now?

Reply Score: 2

galvanash Member since:
2006-01-25

Read the article again. Rsync does nothing even remotely like this.

Reply Score: 1

StephenBeDoper Member since:
2005-07-06

Read the article again. Rsync does nothing even remotely like this.


Or, perhaps, you could provide some (any) reference to, or citation of, the portion of the article which makes that detail clear? Just a thought.

Reply Score: 2

galvanash Member since:
2006-01-25

How do we use this to generate a better diff? With bsdiff we would compute the new file, 'update' from the 'original' like this:

server:
diff = bsdiff(original, update)
transmit diff


client:
receive diff
update = bspatch(original, diff)


(The server would pre-compute diff so that it could be transmitted immediately)

Courgette transforms the program into the primitive assembly language and does the diffing at the assembly level:

server:
asm_old = disassemble(original)
asm_new = disassemble(update)
asm_new_adjusted = adjust(asm_new, asm_old)
asm_diff = bsdiff(asm_old, asm_new_adjusted)
transmit asm_diff


client:
receive asm_diff
asm_old = disassemble(original)
asm_new_adjusted = bspatch(asm_old, asm_diff)
update = assemble(asm_new_adjusted)




rsync does essentially the same thing as bsdiff.

Reply Score: 2

flynn Member since:
2009-03-19

rsync just compares chunks by their checksums and sends over the chunks that don't match. When it comes to binary executables the number of differences is gigantic and spread all over the file, which will effectively make rsync transmit the whole file.

Reply Score: 1

RE[2]: Layman explanation attempt
by n4cer on Fri 17th Jul 2009 03:39 UTC in reply to "RE: Layman explanation attempt "
n4cer Member since:
2005-07-06

From what I understand, this isn't particularly new - Linux and Windows have delta updates which are binary diffs; I remember Microsoft before Microsoft developed a technology to reduce the size of updates; where a 1MB update might have a 500K file which is only around 30K difference between the old and new file.


Here's the relevant info from MS' Binary Delta Compression reference:

The Delta Compression API offers special handling for certain types of executable files (PE files, such as EXE or DLL files.) In particular, executables designed to run on the 32-bit Intel i386 family get special treatment. When the basis and target files are similar executables, this feature can reduce the size of the delta significantly—typically 50-70% further.

To get the maximum benefit from this feature, symbol files from the LINK process can be supplied during delta creation. This will help the creation process recognize the nature of the changes between the files. Richer symbol info, such as private symbols, will help make smaller deltas. Figure 3 illustrates this process.

Figure 3. Delta compression using symbol files

None of the symbol data is passed in the delta, and the symbol files are not needed during the delta apply process.

See Optional Data for Delta Create for more information on how symbols can be provided.

http://msdn.microsoft.com/en-us/library/ms811406.aspx

Reply Score: 3

galvanash Member since:
2006-01-25

Interesting. What they are doing sounds very similar, but they require the user to supply the symbol tables manually. Google's approach doesn't require anyone to supply the symbol tables, it creates them itself directly from the machine code (at least it creates something _like_ a symbol table and uses it for the same purpose).

I don't know which approach is more effective, but if they are close then Google's approach would be far more convenient.

Reply Score: 2

galvanash Member since:
2006-01-25

Also, from my understanding of the MS documentation: the Delta Compression API when used without the user supplied symbol table is probably roughly equivalent to bsdiff. It may be slightly more effective because it understands PE format, but that is just a guess.I don't see any other magic going on.

Reply Score: 3

RE: Layman explanation attempt
by flynn on Thu 16th Jul 2009 22:37 UTC in reply to "Layman explanation attempt "
flynn Member since:
2009-03-19

It basically looks at the machine code of the new and the old executable. Adjusts/aligns the matching parts and then does a diff.(Not 100% correct, but you get the idea)
Simple but really genius .. just like their page rank algorithm... I am still pissed that I didn't come up with something that obvious .. damn .. I could really use all that money.(I would spent most of it on cars, women and drugs. The rest I would squander.)

No, what you described is what they were doing up until now. The problem is that diffs on compiled binaries end up being ineffective because the binary undergoes many more changes between versions then the corresponding source. Remember that programming languages are very often one-to-many mappings for machine instructions. Even if only one line of code changes in the source, many machine instructions will change in the corresponding binary. When you add optimization in to the mix it gets even more messy. As the code changes the available optimizations the compiler can do also change. Some optimizations are no longer possible, while others become available. This has a drastic effect on the resulting binary.

What Google has done is developed a reversible transformation from a regular binary to one that is more condusive to diff'ing. This was they diff the transformed form, send it over the network and then reverse the transformation.

Edited 2009-07-16 22:42 UTC

Reply Score: 1

RE[2]: Layman explanation attempt
by kragil on Thu 16th Jul 2009 22:59 UTC in reply to "RE: Layman explanation attempt "
kragil Member since:
2006-01-04

No, they didn't do the disassemble/adjust part before. That is new.

Reply Score: 2

flynn Member since:
2009-03-19

This is new, but what you described in the initial post wasn't. What you described is just a regular diff. Diff (binary or regular) already works by finding long common subsequences and 'aligning' them. But a regular diff doesn't work on compiled binaries all that well because there are very few such long common subsequences.

Reply Score: 2

kragil Member since:
2006-01-04

I maybe didn't do a good job, but a regular diff has absolutly no understanding what machine code is and how to align machine code. I just left out stuff laymen wouldn't understand and I said it wasn't 100% correct.

So stop telling me what I said, I know.

Reply Score: 1

flynn Member since:
2009-03-19

I maybe didn't do a good job, but a regular diff has absolutly no understanding what machine code is and how to align machine code. I just left out stuff laymen wouldn't understand and I said it wasn't 100% correct.

So stop telling me what I said, I know.

Diff doesn't need to understand machine code to do it's job. It looks for long common subsequences and notes the differences of the rest. The fact that the sequence of 1's and 0's it is comparing corresponds to an add instruction or a mul instruction or a jmp or a call or whatever is absolutely inconsequential. It has no bearing on the algorithm. Just like a text file diff doesn't care about the meaning of the words it's compairing so does binary diff not care about which instructions it's operating on. It just cares about finding the long common sequences of 1's and 0's, no matter what they represent.

The reason binary diff doesn't work all that well isn't because it doesn't 'understant' machine code, it's because changes between two compiled binaries are often so drastic the resulting diff ends ups being almost as large as the file itself, making it almost useless as a space saver.

Reply Score: 1

kragil Member since:
2006-01-04

???????

That is what I am saying all along, that the new way analyses and adjusts (understands) machine code, but you obviously don't understand a single word I am saying so I will stop this insanity now.

Bye

Edited 2009-07-17 09:12 UTC

Reply Score: 1

Great work!
by obsidian on Thu 16th Jul 2009 22:07 UTC
obsidian
Member since:
2007-05-12

I'd love to see the detailed algorithm for this (which will hopefully be in the paper that they're working on). That should be well worth waiting for!

Really good to see work like this being done - looks like a very clever and elegant solution to the "diffing problem".

It'll be interesting to see which license the Courgette code is releaed under (if it is released).
I'd love to see it as "public domain" as (say) the LZMA algorithm is (with the LZMA SDK).

Edited 2009-07-16 22:20 UTC

Reply Score: 2

No change to the process though...
by Ventajou on Thu 16th Jul 2009 22:24 UTC
Ventajou
Member since:
2006-10-31

They would also save bandwidth if they only updated when the browser is actually running. Right now if you install Chrome and don't use it for 6 months, you still have that Google service running in the background and downloading updates whenever it feels like it.

Also they might want to start installing Chrome in the right location on disk instead of in the user's folder. It almost looks like an attempt to help enterprise users circumvent IT policies. Why can't they just install in the Program Files folder like everyone else? Between that and the lack of standalone installer, I don't see Chrome making much progress in the enterprise world.

Reply Score: 2

3rdalbum Member since:
2008-05-26

If Chrome is inside Program Files, then it can only update when it is running as Administrator. That's why it's done that way.

Reply Score: 2

Neato
by galvanash on Thu 16th Jul 2009 22:25 UTC
galvanash
Member since:
2006-01-25

Wow. Whoever thought that up is pretty clever. I mean its not like this is something that will change the world or anything - just a very neat optimization.

I wonder how expensive this operation is at runtime. If it was fast enough, this might be a useful approach to building self-extracting compressed executables for languages that produce large, monolithic, statically linked executables (Delphi comes to mind as a prime example of this)... Probably not worth the trouble for Delphi since it isn't very heavily used anymore, but it might be applicable for the output of some other languages.

Reply Score: 2

RE: Neato
by flynn on Thu 16th Jul 2009 22:40 UTC in reply to "Neato"
flynn Member since:
2009-03-19

If it was fast enough, this might be a useful approach to building self-extracting compressed executables for languages that produce large, monolithic, statically linked executables (Delphi comes to mind as a prime example of this)... Probably not worth the trouble for Delphi since it isn't very heavily used anymore, but it might be applicable for the output of some other languages.

*cough*Haskell*cough*

Reply Score: 1

RE[2]: Neato
by galvanash on Thu 16th Jul 2009 22:52 UTC in reply to "RE: Neato"
galvanash Member since:
2006-01-25

Didn't think of Haskell... Thats a VERY good example - the runtime is rather large and is pretty much always statically linked from what I understand (I'm not a user, but I'm somewhat familiar with it).

Of course the really big gains Google's approach achieves are only apparent on diffs, for the reason that a small code change often creates a rather large change in the resulting binary. But I wouldn't be surprised if a net gain is achievable even for the entire binary image - the disassembly is likely much more compressible than the binary image.

Reply Score: 2

RE[3]: Neato
by Elv13 on Fri 17th Jul 2009 04:17 UTC in reply to "RE[2]: Neato"
Elv13 Member since:
2006-06-12

Not really, you cant make miracles

mov ax,bx (72 bits)
add bx,0xF4D4 (104 bits)

(sorry, I never actually wrote assembly before so I know it is wrong) is bigger than the binary counterpart, let say

F4 D3 9A 73 (64 bits)
F5 D4 9B 74 (64 bits)

so for the complete binary, the assembly code may be more compressible, but it is also slightly bigger. So in my opinion, you make no gain, it is worst.

-I did not test-

Edited 2009-07-17 04:18 UTC

Reply Score: 1

RE[4]: Neato
by galvanash on Fri 17th Jul 2009 06:33 UTC in reply to "RE[3]: Neato"
galvanash Member since:
2006-01-25

Of course it is bigger. It is pretty much always going to be bigger. But the point is that it is dramatically more compressible.

Executable binaries give something like zlib very little to work with. Zlib (and almost any other compression algorithm) does its magic by finding patterns in the data. Binaries have very little in the way of patterns. The assembly code of said binary, however, is chock block full of patterns.

I'm not saying that it would definitely make exe files smaller, in fact I doubt it would be worth the trouble - but it isn't outside the realm of possibility. The odds of it being a net gain increase with executable size - hence why I qualified that it would only be appropriate (possibly) for very large binaries.

Reply Score: 2

RE[5]: Neato
by galvanash on Fri 17th Jul 2009 07:51 UTC in reply to "RE[4]: Neato"
galvanash Member since:
2006-01-25

Well, I just went take a look at the source code:

http://src.chromium.org/viewvc/chrome/trunk/src/courgette/

Frankly, my idea that this might be good as a generic exe packer are probably not valid. I only briefly glanced over the code, and frankly alot of it is WAY over my head, but the secret sauce appears to be what Google calls the "adjustment" step, and that step is only of any consequence for production of a delta - which is of no real consequence for a packer.

The disassembler is designed to produce a representation of the data in a format that is optimal for their adjustment step. It isn't _really_ a disassembler - its much more primitive than that, but it does in effect generate something akin to an instruction stream and a symbol table.

There is some pretty cool comments in there though that help explain things a bit. Neat stuff.

Reply Score: 2

RE[4]: Neato
by kjmph on Fri 17th Jul 2009 07:04 UTC in reply to "RE[3]: Neato"
kjmph Member since:
2009-07-17

Close, but no cigar. A major problem is not patterns in the code, but rather function addresses. If you add even one byte to the beginning of a file, all addresses beyond that point are now shifted by one byte. Think of all the functions statically linked which are called by address. Every single call now has a new address. That's a lot of cruft to send over a wire. If you replace function addresses with function symbols, most of them are not going to change. Less info to send that way.

Reply Score: 1

Firefox already has it
by vijayd81 on Thu 16th Jul 2009 22:53 UTC
vijayd81
Member since:
2008-07-18

It may not be exact same technology but firefox has incremental updates. They are called "mar" files. I believe their auto-updates use that. Also, you can download them from their ftp site (in update folder) and install them manually (filenames end with partial.mar)

Mozilla has not advertised it like Google. I am surprised that people are saying Google invented this cool feature.

Reply Score: 1

RE: Firefox already has it
by sbergman27 on Thu 16th Jul 2009 23:24 UTC in reply to "Firefox already has it"
sbergman27 Member since:
2005-07-24

It may not be exact same technology but firefox has incremental updates. They are called "mar" files.

No. Actually, MAR files use a variation on the same "bsdiff" algorithm that Google has been using, and has found to be unsatisfactory. Google's new approach looks to be 10x more effective. So no, Firefox doesn't have anything even remotely like it.

I've been saying for ages that we needed competition in the OSS browser area, and that the Firefox monopoly was bad, bad bad. (Konqueror? Oh, please...) And I'm beginning to feel vindicated, thanks to Google and the Webkit guys.

Edited 2009-07-16 23:25 UTC

Reply Score: 4

RE[2]: Firefox already has it
by Blomma on Fri 17th Jul 2009 11:30 UTC in reply to "RE: Firefox already has it"
Blomma Member since:
2005-07-06

Right, i think i can keel over and die now. Firefox being called a monopoly was the last thing on my list of things i thought i'd never hear.

Reply Score: 1

Nothing new
by Nagilum on Fri 17th Jul 2009 08:45 UTC
Nagilum
Member since:
2009-07-01

Back in the DOS days there was a compressor (I think just called ABC, advanced binary coder or something) that allowed you to save the dictionary that is generated when compressing a file. You could then re-use that to compress another file. So if you wanted to do a patch you would save the dictionary from compressing the original then use it to compress the updated version. The resulting file would be very small. Then you transfer the patch, use the compressor to temporary compress the original on the client side. That gives you the dictionary which you can then use to decompress the patch.
To get an idea how much you save by this compress a file with something like lzma (or something else with a big dictionary), then make a small change to a copy of the file, concatenate the two files and compress the result. Then compare filesize between the compressed original file and the compressed concatenated file. That difference is the approximate size of such a patch. (it will in fact be a bit larger as the dictionary cannot be modified by the patch without increasing the patch size)
Personally I would prefer this approach be implemented with something like lzma. Specialized data handling modules like courgette could then supplement that approach.

Reply Score: 1

RE: Nothing new
by Nagilum on Fri 17th Jul 2009 09:03 UTC in reply to "Nothing new"
Nagilum Member since:
2009-07-01

Just did a small test, looks like this doesn't work with lzma, However I did find the compressor:
ftp://ftp.elf.stuba.sk/pub/pc/pack/acb_200c.zip

Reply Score: 2

first read that as "Cougar-ette"
by rockwell on Fri 17th Jul 2009 16:04 UTC
rockwell
Member since:
2005-09-13

need more sleep .. or beer.

Reply Score: 2