• Advertisement

Archived

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

Patches

This topic is 5711 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

Basically, how do they work? For example, when you log on to Battle.net and it downloads the newest update. What''s a way I could essentially make a game I write patchable? ---- "Caw, caw, BANG f**k I''m dead!" --The Crow

Share this post


Link to post
Share on other sites
Advertisement
Make a program that can read and execute the patch-files.

They can be designed like this:

CHUNK 1: HEADER DEFINITIONS
* number of files to be updated / added

CHUNK 2: LIST OF PATCH ITEMS
they store the actual data that has to be added or is used to exchange older files. The list contains exactly the number of items you declared in the header definitions (chunk 1).

* bool: replaces whole file?

if yes, just skip the following passage...

* position in file (where do you have to start copying / inserting)

* bool: just copy or do you have to replace

* if replace: datasize you have to DELETE from original file.

and then (-finally-) the data (image, sound, ...)

FINISHED!

With such a simple system you can keep your game patch-able...

Hope it helped...

Yours,

Indeterminatus

--si tacuisses, philosophus mansisses--

Share this post


Link to post
Share on other sites
Some patches are just self extracting archives containing the newest versions of changed files. This is much easier than actually patching the executable.

Share this post


Link to post
Share on other sites
of course, you''re right...i didn''t mean to patch the executable, but to WRITE an executable that can read your patchfile (just like an archive, but cut to the needs of a patch...)

i got the idea of an own patching system when i thought of a huge game project...if you have a huge file (around 60 megs, for example) it would be useless to download the complete file again, if only one megabyte has changed in the new version...do you get the idea?
If you tell the patch executable to copy the following data in file at position you would only need to provide the changed bytes + some xtra bytes with informations on what to do with the embedded data (in the patchfile)...

Hope it''s clearer now...

Yours,

Indeterminatus

--si tacuisses, philosophus mansisses--

Share this post


Link to post
Share on other sites
Look up each of "longest common subsequence" and "diff algorithm" on the web to get you started. I've never done it myself, so I can't offer much help, but it's worth a look.

[edited by - chronos on May 30, 2002 9:45:07 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
That is a good idea Indeterminatus, but how would you know where to tell your patch file to put the updated section of code. What I mean is, say you have an executable that needs to be patched, how do you know where in the file the patch is suppose to go?

Share this post


Link to post
Share on other sites
By the way, for a bit of fun you can do this under Linux:
od -tx1 -w1 -v old_file | awk '{print ($2)}' > old_file.hex
od -tx1 -w1 -v new_file | awk '{print ($2)}' > new_file.hex
diff old_file.hex new_file.hex
The first two commands convert binary files to hexadecimal, one byte per line. The last command outputs a list of differences between the two files. Because each line represents a byte, what you get is list of bytes which are either new or different.

[edited by - chronos on May 30, 2002 6:36:52 PM]

Share this post


Link to post
Share on other sites
You don''t need to do anything special to be able to write patachable programs.

For example:

The file "enemy.dat" contain all the possible words the enemy can say at you. Then, later, you want to add some more words. So, you create the new file and plug it into an installer. You hand out the ''patch'' that will allow the enemy to say more stuff. It''s a patch because it not a complet upgrade from the prior version.

Sometimes, you might need to upgrade the executable, if it can be done without the need to re-install the whole thing, you call it a patch.

So, basically a patch is the new file that will over write the old file. A small updrade.


It''s all you need

Share this post


Link to post
Share on other sites
Not always.

If you have small files, sure, overwrite them. But if you have a big data file, you need to update just what was changed.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Anonymous Poster
That is a good idea Indeterminatus, but how would you know where to tell your patch file to put the updated section of code. What I mean is, say you have an executable that needs to be patched, how do you know where in the file the patch is suppose to go?


compiliers can ouput what is called a map file.
map files contain locations of everything that youve
declared in your code..be it variables, functions,
everything.

with such information, it is trivial to write a tool that
patches a chunk of code into the desired location and then
fixes up the subsequent addresses..this is not necessary if
the new piece of code is the _exact_ size as the original.

ive never actually patched an executable, but the above
would be my first attempt to do so..ive used a similar
method for generating loadable code segments for the n64
games ive worked on..so im sure it would work..

however, there are probably better ways to do it that i
am not aware of..

Share this post


Link to post
Share on other sites
I've been working on some "patching code" myself. Here's what I do:

Open the OLD file and the NEW file in binary mode.
Read the OLD file filling a dynamically created buffer to hold it.
Compare the size of OLD file and NEW file
You need to know this because if the NEW file is shorter or longer this will have an impact on the "patched" file (especially if it is an .exe)
Open a new DATA file in binary mode
Read in a buffer from the NEW file
Compare byte for byte NEW to OLD

ok here's where we need some code... After some trial and error (doesn't everyone code like that) I created a struct to hold my offset and the bytes that were different, here's the struct:


    
static int BLOCKSIZE = 18;

typedef struct tagPatchBlock
{
DWORD offset; // how far into the file to write new data.

WORD count; // the number of values that are to be written @ offset.

BYTE values[BLOCKSIZE]; // the values to write.

} sPatchBlock



ok now:

When a difference is detected store the offset in the sPatchBlock struct
If you fill up the values (18 in this case) you save that block to your DATA file like so:
fwrite(&fileblock,sizeof(sPatchBlock),1,PatchFile);
Also if the delta of the next offset is more than one you will save off that fileblock and create a new one.


At first glance it may look like your wasting space in the DATA file... and you would be correct. The solution is to compress the DATA file using zlib or another compression alogo.

The only thing left is a header in the DATA file and creating a new file is easy...

If you have any questions feel free to email me - I'll gladly send you some of my test code.








Dave "Dak Lozar" Loeser †

[edited the fixed text]

[edited by - Dak Lozar on June 2, 2002 11:38:37 AM]

Share this post


Link to post
Share on other sites
Dark Lozar,

The problem with your code is that doesn't work all that well for something like the following:

offset: 0000000000111111111122222222223
0123456789012345678901234567890
file 1: {ABCDEFGHIJKLMNOPQRSTUVWXYZ$$$}
file 2: {ABCDEFGHI**JKLMNOPRSTUVWXYZ}
There's a better way to do it than what you propose. You've probably noticed that the two strings above have three substrings and the start and end of file markers (represented here as "{" and "}") in common:

{ ABCDEFGHI JKLMNOP RSTUVWXYZ }
The offsets for each of these items in each of the two original files are:

file 1: 00, 01 - 09, 10 - 16, 18 - 26, 30
file 2: 00, 01 - 09, 12 - 18, 19 - 27, 28
You'll notice some gaps between the offsets given:

file 1 gaps: 17, 27 - 29
file 2 gaps: 10 - 11
File 1 gaps indicate those characters belonging to file 1 which have been removed from it. File 2 gaps indicate those charcters belonging to file 2 which have been added to file 1.

You use this information to define ranges of offsets where bytes should be removed from the original file (you use the contents of this file as input) and offset/data pairs where bytes should be added to the final file.

[edited by - chronos on June 2, 2002 2:27:49 AM]

Share this post


Link to post
Share on other sites
hi chronos,

In all my testing (that''s all I''ve done with this code so far), I''ve successfully recreated all data files and executables using this technique.

using your data and assuming that file 1 is OLD file and file2 is NEW file, here''s what I would end up with.


offset: 0000000000111111111122222222223
0123456789012345678901234567890
file 1: {ABCDEFGHIJKLMNOPQRSTUVWXYZ$$$}
file 2: {ABCDEFGHI**JKLMNOPRSTUVWXYZ}

OFFSET: 10
COUNT : 18
VALUES: **JKLMNOPRSTUVWXYZ}


One of the items that I did leave out was the in the header of the data file there is a checksum of the file being patched (OLD) and of course the data file that it is being patched from along with the file size of the resulting NEW file and checksum.

I''m not sure where you''re thinking this technique is lacking - care to elaborate?









Dave "Dak Lozar" Loeser †

Share this post


Link to post
Share on other sites
Dark Lozar,

What I was trying to suggest is that while your code works okay for files where the changes between the two files share the same offsets in each file...

file 1: {ABBA...}
file 2: {ACCA...}
^^
... it doesn't work very well when the changes cause the offsets to change ...

file 1: {ABABAB...AB}
file 2: {IABABAB...AB}
^^^^^^^^^^^^
You'll notice in this second example that the only difference is an "I" inserted at the start of the second file. Your algorithm would produce as many chunks as (filesize-1) / 18 + 1, while the algorithm I gave would simply do this:

file 1: {ABABAB...AB}
file 2: {IABABAB...AB}
Both have in common:

{ ABABAB...AB }
If N is the offset of EOF for file 1 and K is the offset of EOF for file 2:

file 1 offsets: 0, 1 - (N-1), N
file 2 offsets: 0, 2 - (K-1), K
We get the following gaps:

file 1 gaps: none
file 2 gaps: 1
Instead of so many chunks what you get is:

Remove nothing from file 1.
Add "I" at offset 1 to file 2.
Because offsets will change whenever you insert or remove something from a file (except at the end of it), you'll want to use an algorithm that handles these cases well.

[edited by - chronos on June 2, 2002 4:59:45 PM]

Share this post


Link to post
Share on other sites
There's something I should clarify about the algorithm I explained above. When looking for characters in common between the two files we must preserve the order in which these characters appear. In other words, we're looking for the "longest common subsequence", as I suggested before.

This means that for a pair of files like these,
{AABBBBAA}
{BBAAAABB}
you don't want to pick common substrings out of order:

{ AA BB BB AA } <-- WRONG
What you want to do is look for the longest common subsequence. In this particular case we have several such sequences:

{ AA AA }
{ AA BB }
{ BB AA }
{ BB BB }
Any one of these will work, although some will work better than others (the two in the middle will yield a smaller set of changes in this case).

[edited by - chronos on June 4, 2002 4:36:35 PM]

Share this post


Link to post
Share on other sites
chronos,
Yup, I see what your saying... and do agree that this is a better technique...

I''ve been relying on compression as a method of keeping the data file (for the patch) small... and so far things are working out.

I am intriqued by the method that you have described and will probably spend some time to see if there are benefits in reducing the size the resulting data file...

Take care,

Dave "Dak Lozar" Loeser †

Share this post


Link to post
Share on other sites

  • Advertisement