And the inventive step is?
Fed up of seeing rather obvious solutions patented.
The clever bit is the algorithm. Applying it to the problem of software updates is rather obvious.
Mobilephoneware maker Red Bend Software has sued Google for patent infringement, claiming that the web giant's Chrome browser steps on an algorithmic patent it secured in 2003. In tandem with its Israeli parent company - Red Bend Ltd. - the Massachusetts-based Red Bend Software filed its suit in federal court on Monday, …
Using a diff file to update software is nothing new, we had that back in the Amiga days. I don't see how applying compression to the diff file infringes on patents. It just shouldn't be allowed to infringe. Unless Google is using exactly the same compression algorithm that was patented by the other company, but what are the chances of independently coming up with exactly the same one?
Maybe the world should drop this patent rubbish, it puts a major handbrake on progress and lines the pockets of lawyers. I say that as someone who was told by the patent office that my invention cannot be patented, so if I can live with it I'm sure other companies will find a way to. (Yes, I realise this will never happen in a million years)
It’s not the first time that this sort of issue has come up. This sort of patent should not be allowed to exist. If two different people/companies/entities independently solve very similar problems in very similar ways, then each should be entitled to use their own solution for their own respective gains.
MS can't sue Apple for using rectangular windows as part of their OS, Mercedes-Benz can't sue Ford for making cars with four round wheels and Red Bend should go get bent for try to pull this shit on Google.
The problem Google and Red Bend (among countless others) both solved independently is too principally simple to have hundreds of solutions. There are only so many ways to skin this cat and they should both be allowed to use their algorithm.
The patent mentions Unix diff - and says its output is excessively large. Small changes in the source code (e.g., checking that a parameter is within a valid range) will change the target addresses of many jumps/branches, function calls, and data references. (Example: I took a 30-line C program, changed "if (argc < 3)" to "if (argc < 3 || argc > 4)"; cmp found 858 differing bytes in the executables. Disassembly showed that only three instructions were added.) What they've patented is apparently a way to send only the significant changes, and have the patching program recalculate all the new addresses. They also apply it to data tables such as spreadsheets with cells referencing and performing calculations on other cells. An algorithm for doing that is not at all obvious and is a valid thing to patent.
Whether or not Google's algorithm is similar enough to infringe on that patent is a different matter, and there isn't enough information in the article to say anything about that.
The patent appears to be about a delta compression algorithm targeted at machine code.
If you insert a byte into an existing program, it will offset the addresses of all the following instructions. Any jumps to that code will now need to use a different address so the initially simple change has a large knock on effect.
A compression algorithm that doesn't know about these properties would likely end up patching every affected jump instruction. A machine code aware algorithm might simply record that "all jumps to this address range must be offset".
While it is an interesting technique, I find it hard to believe that no one thought of it before 1998 (one year before the application date).
I remember working on the exact same algorithm a few years ago. The patent in question was based upon a research paper 'Compressing differences in executable code'. One of the co-authors of this paper Udi Manber now works for Google I think. So the original author has helped write Courgette, but a different company holds a patent ... interesting to see how this will pan out given the pathetic US patent system
To sink a patent case it's only necessary to point out that someone else was doing the same thing before the plaintiff claims to have invented it. That makes it not their patent, therefore there's no case.
I'm sure there's a few people in Google who've been around the industry long enough to point this out.
Personally, I just think it's a pity the IT industry isn't run by geeks any more. It's run by businessmen, who think in terms of commercial advantage, intellectual property and legal action instead of "Hey that's cool! Can I use that too? I'll credit you in the comments at the top of the source code!"
I raise my glass to the late lamented IT industry.
Same as usual basically.
This is just clearly demonstrating HOW screwed up the patent system for code is.
This is a smaller company going after a bigger Company, but it also makes clear how bigger Companies can go after smaller ones and screw innovation. I get scared to write new stuff these days in case someone does me for 'nicking' their code.
Innovation is really dead it seems.
I few years back, I was tasked with developing a solution for exactly this problem so that we could patch binaries in the field.
I spent some time working on this, and from quickly reading the Google notes on Courgette, it seems that my solution was very similar - pull the binary apart, analyse the jump tables, etc etc. The thing is, once you start looking at this problem, the solution IS obvious. It's not easy (but it's not that hard either). But it IS obvious.
As it turned out, another guy on the team was also working on the same problem and his solution generated slightly better (smaller) patches than mine, so we ran with his idea instead. But it still used the same techniques.
After we'd worked on this, we also heard about some outfit in Isreal that had a solution - wouldn't be surprised if it was the same people - there can't be that many about. We talked to them and they wouldn't tell us how it worked but it was pretty clear that they also used a similar technique. I think they were very expensive though which is why we stuck with our own solution. And I'm sure many people have used similar techniques before and since - because it's obvious!
So anyway, depending on the date of the patent, I think there could be a prior art issue here.
Il Midga di Macaroni wrote: "Personally, I just think it's a pity the IT industry isn't run by geeks any more. It's run by businessmen, who think in terms of commercial advantage, intellectual property and legal action instead of Hey that's cool! Can I use that too? I'll credit you in the comments at the top of the source code!"
And that is also the reason /why/ the IT industry is run by businessmen instead of geeks.
Not so sure IT is run by true Businessmen.. Those are the kind that actively try and build businesses, strike deals between each other and who actually have a shred of honour. Pretty much a dying breed.
These days, businessman seems to refer to the MBA type who've sat in rooms, and read the latest methods for screwing over your staff and your competitor to get an improved payout for your shareholders for the next 3 years (the length of the business plan) after which time, the company folds due to having been gutted to make it short term profitable. But hey, it makes money, and you can always move onto the next company and do exactly the same.
IT seems to be run by accountants (the bad type who don't actually have the imagination to work out what something will actually create in the long term, and are too busy working out how many pennies can be shaved off next year's spend by not paying for infrastructure, resilience or skills) and Lawyers (who delight in running round trying to find more ways to sue everyone, thus raking in shed loads of money for themselves; either that, or in advising people how not to fall foul of those other lawyers, thus making shed loads of money for themselves).
I'm so glad The Reg. has the "Badgers" icon.
I go back far enough to days when we used to produce patches like this manually. In those days we wrote assembler code (IBM 370 or ICL Systrem 4 - almost identical at the non-privileged level) and the only way we had to apply patches was through binary deltas. It had many of the hallmarks of this sort of patent - look at the code change required to fix the bug, patch in branches and other overlays to the corrected code (if it couldn't be done in the space available) and put the extra bits of binary somewhere in some unused space at the end of the module.
The patches could be applied on-the-fly (this was for online OLTP), apart from a few core parts of the system that had to remain resident.
In effect, the binary was a manually created delta file that differentially patched part of the code, and that had been done long before I was involved (it dated back to the very early 1970s). Of course an automated system to work this out would have been nice, and given the regularity of IBM 370 machine code, not too difficult, but in those days it was easier to use people as code was hand-crafted and compact. (Also humans are rather better at working out the lease number of changes as they can code the patch to suit not do a comparison of two separate binaries of finished programs.
However, as usual, there are rarely really new breakthroughs in coding like this - just some logical extentions. Software patents are an abomination.
Are any other humans just seeing this whole conversation as ridiculous? Just to save our PROFIT. Save our PROFIT please. Goodness. Even the capitalist can't work it out amongst themselves. The good thing is that as humans, when we decide to ditch this madness and go PRO human, we're laughing. The tech already exists. It's ours :)
"bsdiff and bspatch are tools for building and applying patches to binary files. By using suffix sorting (specifically, Larsson and Sadakane's qsufsort) and taking advantage of how executable files change, bsdiff routinely produces binary patches 50-80% smaller than those produced by Xdelta, and 15% smaller than those produced by .RTPatch (a $2750/seat commercial patch tool)."
Colin Percival, Naive differences of executable code, http://www.daemonology.net/papers/bsdiff.pdf
To those who bitch about software patents and small troll companies without engaging the brain: some of us work for long hours, only to have our ideas taken without compensation. Patents are a legitimate form of protection for the innovation we create. But it has to be an invention that advances the art at a particular point in time.
Binary diff with compression is inventive, in the 1960's, not 1990's.
Remember, patents for software are something relatively new (1990's). They should protect those innovating in the field. But shame on real trolls that take a previously known software concept and try to say they came up with it. It makes it very difficult for us trying to make a real living in this industry.
Biting the hand that feeds IT © 1998–2019