Archived

This topic is now archived and is closed to further replies.

Automatic Patching Utility

This topic is 5110 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Many games nowadays have some sort of automatic patching utility, especially online games. I haven''t put much thought into this yet, but I have looked around online to try to see how it is commonly done, but I came up empty handed. It seems like it can be done by utilizing a diff-like program on the server side, and on the client side making the bit by bit edits/additions/deletions specified by the server diff output, but I would like the advice of someone who has actually done this. Thanks in advance, Kevin

Share this post


Link to post
Share on other sites
It would be just as easy or easier to keep the version information in a config file that the program reads on start up. Then when it connects to the internet master server the server can tell the client what version it is. If the server version > client version it can notify the client it needs to download a patch.

Sounds like the easiest way to me.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I think he was wondering on how to apply a patch and/or store the patch information.

Share this post


Link to post
Share on other sites
yea, the AP got the point, knowing when to apply the patches is pretty easy, I was more interested in how to write a program to apply a patch, or perhaps more generally, how to write a "diff" program and how to take the output from the diff program to patch a file.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by kevmo
yea, the AP got the point, knowing when to apply the patches is pretty easy, I was more interested in how to write a program to apply a patch, or perhaps more generally, how to write a "diff" program and how to take the output from the diff program to patch a file.


find the longest common substring between the two inputs. anything not in the longest common substring is the difference. google for the algorithm <i''m not really familiar with >

alternatively, you could just use the GNU diff tool



Share this post


Link to post
Share on other sites
Isn''t it more along the lines of finding the smallest set of common substrings spanning as much of the strings as possible? Because just one substring seems like it would only allow for 1 modification - its possible that the rest of the string does actually contain smaller common substrings in it that aren''t part of the difference. This is a harder problem than just the longest common substring problem.

Share this post


Link to post
Share on other sites
Really you don''t need a Diff program.

Step 1: A download and paste program,
downloads the files from the server and replaces
the old files. These files would be specified in
some filelist that the server sends. This
is a simple delete and then binary write operation for
stuff like the game .exe. ( slightly more complex if you have
an archive ie. .zip that is holding all your game data.. )

Step 2: A version checking rutine in your client game, and a
spawn new process/exit game process. This will start step 1,
then close the game.... sorry but someone else should fill in
the details on this.

Share this post


Link to post
Share on other sites
quote:
Really you don't need a Diff program.


I disagree with that. What if I was writing Warcraft, lets say, and there was a patch to one of the 100+MB files. Are you going to require your user to download the whole file over again as a "patch"?

The reason I was asking for a patch and not a delete and replace program is because of just that: it is far more efficient in terms of bandwidth to send just the part of the data that has changed.

[edited by - kevmo on December 17, 2003 8:49:07 PM]

Share this post


Link to post
Share on other sites
"Diff" algorithm would suck for anything but text (iirc)

rsync implements a very nice data-syncronization algorithm. Tuned to allow it to work well with both text AND raw data.

Share this post


Link to post
Share on other sites
I don't see how a diff-like algorithm would be bad on any kind of data - it is simply storing additions,modifications, and deletions. It doesn't make any sort of specification on what kind of data you are going to be delta compressing (i think that is the correct term: storing only data that has changed).

EDIT:

On the rsync algorithm (http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html):
"It's an algorithm meant for: when you didn't have the forethought to, at one end or the other, have a copy of the old file so you could run a diff".

This isn't the case in a patching utility, as the patch is generated from the old file and new file, and then sent to the client, who then just applies the patch.

According to http://samba.anu.edu.au/rsync/tech_report/, one advantage that rsync gives over running diff on the files is that it uses less CPU time. However, you have to consider the fact that you would only need to run this diff once to make the patch, after that you just distribute the patch. It is less data to store just the diff information in a smart manner rather than all the checksums and modified data.

In short, I disagree that rsync is a viable method for a standalone patch.

[edited by - kevmo on December 17, 2003 10:58:46 PM]

Share this post


Link to post
Share on other sites
I haven''t done this but I''m interested in this topic as well. I think what Anon user suggested seems like a viable solution.

You find the longest string of matching data. Save the offset and length of it in both programs. Then go through the data before and after the longest matching data only changing the data that is different and adding the data if it is non-existant.
The patcher program would be a list of patchable data. e.g.

class Patch
{
long lOffset;
virtual PatchIt();
....
};

class PatchByte : public Patch
{
.....
unsigned char ucPatchValue;
PatchIt(){.....}

};

class PatchArray : public Patch
{
unsigned char* pData;
long length;
....etc.
}


list patches;

...for all patches
patch it....

I might as well write a patch utility one of these days

Seems like a good challenge...

-Viktor

Share this post


Link to post
Share on other sites
As a follow-up, I'll briefly described the final design that I think I am going to take.

The situation is this: the user has file A, and the producer of the game wishes to update this file to file B.

To create the patch:
- Use a graph-based approach specified by http://www.justinalia.com/cs/algorithms/diff02.html
- Consider the size of file A in bytes to be n, and the size of file B to be m.
- Create a n X m grid of vertices, with a vertex labeled (x,y), x is in the set of [0,n] and y is in the set of [0,m].
- Add an edge from each vertex to the vertex on its left and on its right, and above it and below it.
- Add a diagonal edge from (x-1,y-1) to (x,y) if the x-th byte in A is equal to the y-th byte in B.
- Perform a weighted shortest path search from (0,0) to (m,n), with the horizontal and vertical edges weighted 1 and the diagonal edges weighted 0.
- What this search represents is the following: A horizontal edge is an addition to the file and a vertical edge is a deletion from the file (think about this for a bit). A change is simply a deletion then addition or vice versa. A diagonal edge means the data isnt stored.
- This means if we store each horizontal and verticle edge in the path along with the coordinates, we know exactly where to change the bytes. Note you also have to store the byte from the new file with a horizontal edge.
- This storage can be improved by storing sequences of edges together, thereby only storing the start of the sequence, and the number of additions/deletions in the sequence, and if the sequence is the addition, the bytes to add.

To apply the patch:
I haven't thought much about it, but it should be trivial given the byte-level diff patch.

For an automatic update service:
Keep a sort of revision control system on the server, storing hashes of all previous versions of the file, and the diff-patch to the next version of the file. To update a given file, look up its hash in the database (if it is not there, it means the file got corrupted, might as well either a) send the whole file over or b) do a rsync-like operation on the bad file). If the hash is there, send all the patches up to the latest version to the client, and apply them sequentially.

Comments/suggestions welcome.

[edited by - kevmo on December 17, 2003 11:41:18 PM]

Share this post


Link to post
Share on other sites