13 ms·

Reminds me of when Apple started providing "smaller size updates" to OS X. I was curious about the details since my doctorate had touched on the topic, so I wo

Reminds me of when Apple started providing "smaller size updates" to OS X. I was curious about the details since my doctorate had touched on the topic, so I worked my contacts (I had a few in Apple engineering from the FreeBSD / OS X relationship) and after a few months I got back as answer: "We're using a tool called bsdiff, are you familiar with it?" I was indeed, since I was the author of said tool. (Just to be clear, there was no license violation involved in this case; just a lack of awareness of the provenance of the open source software they were using.)

eska 5y ago
I sent an email to a corporate Steam email address, asking whether I’d be allowed to post a screenshot from half-life in a computer graphics shading thesis. Ended up with a response from Gabe Newell, CEO, shortly after, and another engineer who invented skeletal animation, all excited to talk about it with some random kid
rubicon33 5y ago
I don't understand what bsdiff does, or is. I am a software developer and I frankly have no clue what I would ever use bsdiff for! I've read what it does (libraries for building and applying patches to binary files) and still don't really have a sense for what the purpose of this tool is. What are some real life use cases for it? When does a developer need such a tool?
- deleted 5y ago
  [deleted]
- faeyanpiraat 5y ago
  If you have a game, where you have large packs of files (like a 2GB sized textures.pak), and in a patch you want to add 2 small things, you can just ship the differencd between the old anc new pack file, and skip transferring the rest.
  - OldTimeCoffee 5y ago
    They do this, but not as a binary diff. The new files are just shipped as an override of the old files that are loaded after the old files. It's substainally faster than applying a binary diff and file sizes really aren't a concern for the most part. The game industry really hasn't used binary diffs and patching since the 90s when they used RTPatch.
    - mcguire 5y ago
      I've noticed. Flight Simulator downloads tens of GB every time I start it. :-/
- throwaway3699 5y ago
  Implementing software updates where you don't want to ship entire binaries again (and only the diff) would be one. In some video games the assets are also packed into massive binaries, so you don't want to ship gigabytes of data because you replaced one icon. Sadly many games do this anyway nowadays.
  - maccard 5y ago
    One of the reasons games do this is the data is compressed, so a "patch" might be indistinguishable from a real update. Also, as a dev, you have no idea what version your users are updating _from_. You either need to generate some number of patches for every version you could be updating from, and figure out if you should just download the whole thing again in any of those cases anyway.
    - oblio 5y ago
      > One of the reasons games do this is the data is compressed, so a "patch" might be indistinguishable from a real update. Does this happen with more advanced compression algorithms? I've rsynced zip files of different versions of internal software and the diff was always much, much smaller than the entire package.
      - whelming_wave 5y ago
        Kind of an aside from your question, but binary patches not being much smaller than the full thing might happen more with modern games? Heresay, but from what I've heard modern games may ship multiple copies of some assets with different levels or features so they can be loaded as a sequential read off the disk. While a block-oriented compression algorithm might sync up more reliably, if you're packing 200MB of assets for a level and they're all compressed to take advantage of the fact they'll be read sequentially could mean a change 25MB in would still ship ~175MB of changes.
        uuidgen 5y ago
        So far in in most of the world even platter disks (which have really poor performance with modern Windows) are faster than network. Which means you can download description of the difference and reorder the file locally much faster than downloading it. Yes it needs the file to made in a way that is update friendly - most current compression algorithms can be configured like that. Yes, compression will be slightly lower, but you will save on both download size AND disk space, because right now most patches require you to download patch and then apply it, requiring twice the space. If you have 5% larger asset file but can patch it with a few memcpy on a mapped file it is a win in every way imaginable. It is just really poor programming, nothing more. And it's everywhere. If find source >/dev/null takes 6 seconds there is no reason for gradle to take 2 minutes on a rebuild. If the dev is used to that, why would they even think about patch optimisation?
- cperciva 5y ago
  Does it help if I tell you that bsdiff has saved end users somewhere over 10,000 years of waiting for software updates to download?
  - throw14082020 5y ago
    yea well thats not enough! Xcode should be using it too. They make us download 12GB for every update. /s end open source entitlement section Thanks for your great work
- nix23 5y ago
  Chrome and Chromium used bsdiff for updates: https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...
  - codeulike 5y ago
    The page says they use something called Courgette which is similar to bsdiff
    - nix23 5y ago
      They used bsdiff before and now Courgette.
- codeulike 5y ago
  Its old now but here's a description from Chromium about something they use called Courgette which is similar/related to bsdiff https://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html https://blog.chromium.org/2009/07/smaller-is-faster-and-safe... The explanation here is pretty fascinating https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...
  - kevincox 5y ago
    The really cool TL;DR here is that courgette "disassembles" the binary before diffing. Basically turning internal references into symbolic references. This way adding an extra instruction to a function won't affect all of the relative addresses in surrounding code.
- masklinn 5y ago
  > I don't understand what bsdiff does, or is. It‘s a binary diff/patch utility. > What are some real life use cases for it? When does a developer need such a tool? Incrementally update binary files e.g. assets or runnable binaries instead if having to re-send the entire thing on every update so e.g. games, browsers, package managers, … The standard diff/patch utilities are text-based and even when they do extend to binary data their algorithms and heuristics tend to be biased towards textual contents. Bsdiff was built specifically with an eye towards executables.
YakBizzarro 5y ago
I used and hacked bsdiff in the past. A very neat concept and tool, many many thanks for making and publishing it!
vanderZwan 5y ago
While I'm not the author of anything, I did on one occasion share Russ Cox' articles on regexes with a fellow developer, only for that developer to reply "that guy is making a mountain out of a molehill, just use re2".
- jffry 5y ago
  For anybody who's lost: Russ Cox is the original author of re2, a fast C++ library implementing regular expressions that are guaranteed to run in linear-time. There's a collection of articles they wrote talking about regexes and various pitfalls: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/
  - deathanatos 5y ago
    This is still relevant today, too. The last several JavaScript vulns. that people at my company have had to upgrade around were because of accidentally quadratic regex in JavaScript. One poor library[1] was attempting to match a header whose grammar was a whoppingly complex, 1#token (this is in the HTTP spec's notation: it means 1 or more `token`s, comma separated with optional whitespace around the comma) and hit this, by trying to split the incoming values with, / *, */ I was shocked that this wasn't compiled to a DFA. (I checked, too: my JS exhibited the behavior in the bug report.) This is, I also think, another reason why "simple" text protocols are not really so simple. The grammar above is "trivial", and yet, this is the end result. I don't feel like the library is particularly at fault: I doubt I would have caught this in code review. [1]: https://www.npmjs.com/advisories/1748 https://www.npmjs.com/advisories/1748
- phkahler 5y ago
  >> "that guy is making a mountain out of a molehill, just use re2" That's an odd thing about the tech world, it's accessible. As you get better in different areas you are actually more and more likely to make contact with important people (big names? people who did important stuff?). This can creep up on you if you're not aware what level you're operating at. It can be a small world.
  - 5y ago
grupthink 5y ago
Yeah, but did you win the Putnam?
- mishraprince 5y ago
  That one reply in that flame war is still hilarious so many years later. To anyone who didn't get the reference of Putnam https://news.ycombinator.com/item?id=35079 https://news.ycombinator.com/item?id=35079
  - bredren 5y ago
    tldr; In 2007, an academic argues with PG and others. After long exchange, academic defensively states their own achievements. Another user challenges academic with GP question, to which academic provides unexpected affirmative response.
    - pjerem 5y ago
      I think you missed the point. Scroll up, it's the same guy :)
      - bredren 5y ago
        Haha. I did. That’s wonderful.
    - yuppiemephisto 5y ago
      I don't agree with that phrasing. A lot of people on that thread seemed sure cperciva was some arrogant dickhead bound for failure, but tarsnap is going a lot stronger than many of them are. Also people in the thread were amazingly rude to him, while he seemed pretty polite to me.
      - cperciva 5y ago
        I think you're giving cperciva too much credit. He was just as arrogant as people thought, and he was definitely defensive.
gowld 5y ago
Nowadays, Apple ships the whole 4GB OS, even when they have to ship 3 point updates in one month for small bugs.
- warrenm 5y ago
  You obviously haven't done macOS updates in many years
scrollaway 5y ago
I first encountered bsdiff when working on reverse engineering Blizzard MPQs (their proprietary packaging format, long abandoned now in favour of other stuff). They started using it for mpq patches some time in … 2007 I want to say? I was 16, had just started to code. 10-ish years later, I'm doing other stuff but still working with Blizzard-related tooling sometimes. I was talking to a Battle.net engineer about their latest-and-greatest game update protocols. He tells me they're thinking of adopting this great thing called bsdiff for the next version. I giggled a bit. Anyway, hi! I implemented a version of your algorithm when I still barely knew wtf I was doing. https://github.com/jleclanche/python-ptch https://github.com/jleclanche/python-ptch

eska 5y ago

I sent an email to a corporate Steam email address, asking whether I’d be allowed to post a screenshot from half-life in a computer graphics shading thesis. Ended up with a response from Gabe Newell, CEO, shortly after, and another engineer who invented skeletal animation, all excited to talk about it with some random kid

rubicon33 5y ago

I don't understand what bsdiff does, or is. I am a software developer and I frankly have no clue what I would ever use bsdiff for! I've read what it does (libraries for building and applying patches to binary files) and still don't really have a sense for what the purpose of this tool is. What are some real life use cases for it? When does a developer need such a tool?

deleted 5y ago
[deleted]
faeyanpiraat 5y ago
If you have a game, where you have large packs of files (like a 2GB sized textures.pak), and in a patch you want to add 2 small things, you can just ship the differencd between the old anc new pack file, and skip transferring the rest.
- OldTimeCoffee 5y ago
  They do this, but not as a binary diff. The new files are just shipped as an override of the old files that are loaded after the old files. It's substainally faster than applying a binary diff and file sizes really aren't a concern for the most part. The game industry really hasn't used binary diffs and patching since the 90s when they used RTPatch.
  - mcguire 5y ago
    I've noticed. Flight Simulator downloads tens of GB every time I start it. :-/
throwaway3699 5y ago
Implementing software updates where you don't want to ship entire binaries again (and only the diff) would be one. In some video games the assets are also packed into massive binaries, so you don't want to ship gigabytes of data because you replaced one icon. Sadly many games do this anyway nowadays.
- maccard 5y ago
  One of the reasons games do this is the data is compressed, so a "patch" might be indistinguishable from a real update. Also, as a dev, you have no idea what version your users are updating _from_. You either need to generate some number of patches for every version you could be updating from, and figure out if you should just download the whole thing again in any of those cases anyway.
  - oblio 5y ago
    > One of the reasons games do this is the data is compressed, so a "patch" might be indistinguishable from a real update. Does this happen with more advanced compression algorithms? I've rsynced zip files of different versions of internal software and the diff was always much, much smaller than the entire package.
    - whelming_wave 5y ago
      Kind of an aside from your question, but binary patches not being much smaller than the full thing might happen more with modern games? Heresay, but from what I've heard modern games may ship multiple copies of some assets with different levels or features so they can be loaded as a sequential read off the disk. While a block-oriented compression algorithm might sync up more reliably, if you're packing 200MB of assets for a level and they're all compressed to take advantage of the fact they'll be read sequentially could mean a change 25MB in would still ship ~175MB of changes.
      - uuidgen 5y ago
        So far in in most of the world even platter disks (which have really poor performance with modern Windows) are faster than network. Which means you can download description of the difference and reorder the file locally much faster than downloading it. Yes it needs the file to made in a way that is update friendly - most current compression algorithms can be configured like that. Yes, compression will be slightly lower, but you will save on both download size AND disk space, because right now most patches require you to download patch and then apply it, requiring twice the space. If you have 5% larger asset file but can patch it with a few memcpy on a mapped file it is a win in every way imaginable. It is just really poor programming, nothing more. And it's everywhere. If find source >/dev/null takes 6 seconds there is no reason for gradle to take 2 minutes on a rebuild. If the dev is used to that, why would they even think about patch optimisation?
cperciva 5y ago
Does it help if I tell you that bsdiff has saved end users somewhere over 10,000 years of waiting for software updates to download?
- throw14082020 5y ago
  yea well thats not enough! Xcode should be using it too. They make us download 12GB for every update. /s end open source entitlement section Thanks for your great work
nix23 5y ago
Chrome and Chromium used bsdiff for updates: https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...
- codeulike 5y ago
  The page says they use something called Courgette which is similar to bsdiff
  - nix23 5y ago
    They used bsdiff before and now Courgette.
codeulike 5y ago
Its old now but here's a description from Chromium about something they use called Courgette which is similar/related to bsdiff https://blog.chromium.org/2009/07/smaller-is-faster-and-safer-too.html https://blog.chromium.org/2009/07/smaller-is-faster-and-safe... The explanation here is pretty fascinating https://www.chromium.org/developers/design-documents/software-updates-courgette https://www.chromium.org/developers/design-documents/softwar...
- kevincox 5y ago
  The really cool TL;DR here is that courgette "disassembles" the binary before diffing. Basically turning internal references into symbolic references. This way adding an extra instruction to a function won't affect all of the relative addresses in surrounding code.
masklinn 5y ago
> I don't understand what bsdiff does, or is. It‘s a binary diff/patch utility. > What are some real life use cases for it? When does a developer need such a tool? Incrementally update binary files e.g. assets or runnable binaries instead if having to re-send the entire thing on every update so e.g. games, browsers, package managers, … The standard diff/patch utilities are text-based and even when they do extend to binary data their algorithms and heuristics tend to be biased towards textual contents. Bsdiff was built specifically with an eye towards executables.

YakBizzarro 5y ago

I used and hacked bsdiff in the past. A very neat concept and tool, many many thanks for making and publishing it!

vanderZwan 5y ago

While I'm not the author of anything, I did on one occasion share Russ Cox' articles on regexes with a fellow developer, only for that developer to reply "that guy is making a mountain out of a molehill, just use re2".

jffry 5y ago
For anybody who's lost: Russ Cox is the original author of re2, a fast C++ library implementing regular expressions that are guaranteed to run in linear-time. There's a collection of articles they wrote talking about regexes and various pitfalls: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/
- deathanatos 5y ago
  This is still relevant today, too. The last several JavaScript vulns. that people at my company have had to upgrade around were because of accidentally quadratic regex in JavaScript. One poor library[1] was attempting to match a header whose grammar was a whoppingly complex, 1#token (this is in the HTTP spec's notation: it means 1 or more `token`s, comma separated with optional whitespace around the comma) and hit this, by trying to split the incoming values with, / *, */ I was shocked that this wasn't compiled to a DFA. (I checked, too: my JS exhibited the behavior in the bug report.) This is, I also think, another reason why "simple" text protocols are not really so simple. The grammar above is "trivial", and yet, this is the end result. I don't feel like the library is particularly at fault: I doubt I would have caught this in code review. [1]: https://www.npmjs.com/advisories/1748 https://www.npmjs.com/advisories/1748
phkahler 5y ago
>> "that guy is making a mountain out of a molehill, just use re2" That's an odd thing about the tech world, it's accessible. As you get better in different areas you are actually more and more likely to make contact with important people (big names? people who did important stuff?). This can creep up on you if you're not aware what level you're operating at. It can be a small world.
- 5y ago

grupthink 5y ago

Yeah, but did you win the Putnam?

mishraprince 5y ago
That one reply in that flame war is still hilarious so many years later. To anyone who didn't get the reference of Putnam https://news.ycombinator.com/item?id=35079 https://news.ycombinator.com/item?id=35079
- bredren 5y ago
  tldr; In 2007, an academic argues with PG and others. After long exchange, academic defensively states their own achievements. Another user challenges academic with GP question, to which academic provides unexpected affirmative response.
  - pjerem 5y ago
    I think you missed the point. Scroll up, it's the same guy :)
    - bredren 5y ago
      Haha. I did. That’s wonderful.
  - yuppiemephisto 5y ago
    I don't agree with that phrasing. A lot of people on that thread seemed sure cperciva was some arrogant dickhead bound for failure, but tarsnap is going a lot stronger than many of them are. Also people in the thread were amazingly rude to him, while he seemed pretty polite to me.
    - cperciva 5y ago
      I think you're giving cperciva too much credit. He was just as arrogant as people thought, and he was definitely defensive.

gowld 5y ago

Nowadays, Apple ships the whole 4GB OS, even when they have to ship 3 point updates in one month for small bugs.

warrenm 5y ago
You obviously haven't done macOS updates in many years

scrollaway 5y ago

I first encountered bsdiff when working on reverse engineering Blizzard MPQs (their proprietary packaging format, long abandoned now in favour of other stuff). They started using it for mpq patches some time in … 2007 I want to say? I was 16, had just started to code. 10-ish years later, I'm doing other stuff but still working with Blizzard-related tooling sometimes. I was talking to a Battle.net engineer about their latest-and-greatest game update protocols. He tells me they're thinking of adopting this great thing called bsdiff for the next version. I giggled a bit. Anyway, hi! I implemented a version of your algorithm when I still barely knew wtf I was doing. https://github.com/jleclanche/python-ptch https://github.com/jleclanche/python-ptch