News: 11 March 2016 - Forum Rules
Current Moderators - DarkSol, KingMike, MathOnNapkins, Azkadellia, Danke

Author Topic: Dual patcher: Bug Tracker  (Read 2679 times)

HatZen08

  • Jr. Member
  • **
  • Posts: 20
    • View Profile
Dual patcher: Bug Tracker
« on: April 28, 2014, 10:14:23 am »
Greetings.

I am developing a new patcher called dual. The patcher objective is the management of multiple patches in the same target file without the target file corruption.

A patch in dual format register the difference between two files with identical size. When the bytes differ in value for the same position, the bytes value of the two files is stored. A dual patch is effectively the merging of a conventional patch with his anti-patch (undo patch).

The main concept is to use the original bytes and the modified bytes stored in the patches to perform smart operations in the target file. As example, when a new patch is applied to the target file, the target file is checked against the original bytes. The modified bytes will only be applied to the target file if the bytes of the target file correspond to the original bytes in the patch. Otherwise, the patch isn't applied.

Dual can also verify if the patches are already applied to the target file and check the compatibilities between different patches. It allows the user to safely apply or undo the patches without the target file corruption.

I compiled the patcher in my system. It is a ubuntu linux 32-bit. To be honest, I don't have experience about distributable binaries and I don't know how compatible the executable file is with others linux systems. The source files are included with the patcher. They only use the standard c library and should be easily compiled with gcc or other c compilers. It is the theory, anyway. :-)

I am releasing a beta version for this patcher here . I did my own tests and it is working correctly in my system. However, many thing can happen between different systems and architectures. If someone has the interest, please give it a try and post any errors found.

I included a documentation in the file. You can also have a summary of dual commands with 'dual -h'

FAST6191

  • Hero Member
  • *****
  • Posts: 2894
    • View Profile
Re: Dual patcher: Bug Tracker
« Reply #1 on: April 28, 2014, 05:38:18 pm »
Afraid I am going to be the first to ask the tough questions, however coding a patching setup will probably teach you a bit so carry on if that is your goal. The patching format scene is pretty well stocked (ips, ups, xdelta, bsdiff, ppf, ninja and beat to name but a few already in somewhat heavy rotation and what form your immediate competition) and pretty fractured as far as general patching formats. You seem to be heading in the more modern direction (checks, undo, patch stacking) which is good. Likewise you will also face the "IPS is good enough" issue in a lot of cases.

What is the max file size? ISOs for some of the new consoles are up in the 50 gig range. Your competition is theoretically infinite and if not then in the well into the terabytes/more than many will see in the next few years.
What sort of memory am I looking at when patching, when patch making and is there compression involved?
What is the relocation window? I am looking at similar windows to iso size really, however that is very much the extreme case and probably will not go beyond say 2 gigs for normal use (though a switch to change it would not hurt).
You seem to be heading for generic, is there any chance of it being adapted for something console/format specific? If I am already building a batch file with a filesystem unpacker then I might not be so inclined to use your format. Likewise something that can handle SNES headers, interleaved ROMs and more could find itself with a place at the table. More and more systems are also using encryption.
A hash to confirm is nice, if there is none. Are you considering any form of parity/recovery data in there? I have sent out par2 files before though and I was not the first to do it.
How well would this format take to an embedded platform? Soft patching is great and well known in PC emulators, andrios and the rest are starting to see the light and I have met a few people that have their computing needs largely sorted by it.

Branching and stacking is interesting. However I can usually quite easily force things to stack if I want to and aim for that goal, especially on a filesystem using platform like most modern ones.

How set in stone, or alternatively how flexible, is your patching spec? As it stands I have several IPS patches that want certain patchers, PPF has been somewhat fractured for years, Xdelta has at least two lines, bsdiff is not great on windows and all have their failings otherwise.

HatZen08

  • Jr. Member
  • **
  • Posts: 20
    • View Profile
Re: Dual patcher: Bug Tracker
« Reply #2 on: April 29, 2014, 08:14:04 am »
Perhaps, I should give a practical example to help understand the patcher objective.

I am a hacker of Final Fantasy 6 (snes version). I have already two digits of patches for this game. For now, forget it and think you are a hacker who wants to do improvements for this game. You searched RHDN and another sites for patches. In the end, you could get nearly 40 small patches. All of them add small improvements for this game and it should be nice if all of them could work together.

Suppose that your patcher doesn't check for applying patches in wrong positions of the rom and that the patches are all from different people. Some of them don't have any documentation.

The first factor for corruption is if the patch is aimed for a rom with or without a header. If the patch is aimed for a rom without the header and the rom has a header, it will apply the modified bytes in the wrong location. Similarly, the patch also need to be aimed to a rom with the correct version. If only one of them mismatch the rom version and the header/no header issue, the game will be corrupted and will be left unplayable.

The most dangerous factor for corruption is address collision. When you apply a patch, if the patch overwrite the bytes already written by other patches, the game will be corrupted. The second patch must no overwrite the first patch. The third must not overwrite the first and the second. The fourth must not overwrite the first, the second and the third. If the patcher doesn't give you support to check or avoid the address collision between the patches, you can only pray that the rom will not be corrupted after the 40 patches.

Also, patches aren't static by nature. They should be upgraded for better versions. Let's suppose you have successfully applied 40 patches without corrupting the rom and want to upgrade only one patch. If you don't have an anti-patch, your only option is to start from a clean rom and apply all your 39 patches again. Of course, the new updated patch will change their addresses and it may or may not be compatible with your 39 patches.

The dual patcher is aimed to avoid the mentioned issues. It avoids the address collision between the patches and the appliance of patches that are not designed for the rom. It can also safely apply and remove the patches from the rom.

Quote
What is the max file size?
Internally dual uses a four bytes unsigned integer (32 bits). It can store the max value of 2^32. For my final fantasy 6 rom with 3MB, it is more than enough. For target files in the giga byte range, the patcher won't work correctly.

Quote
What sort of memory am I looking at when patching, when patch making and is there compression involved?
Dual follows a different direction from standard patchers. Instead of focus in the creation of small files with high compression for distribution, dual focus in the patches management.

Traditional patchers only need to store the difference between the files bytes. Dual needs to store the original and the modified bytes of the files. It is the double of the size of the bytes a traditional patcher should store.

Dual doesn't have internal compression and it is unfit for the creation of smaller files with high compression for distribution. It follows a different direction.

Quote
You seem to be heading for generic, is there any chance of it being adapted for something console/format specific?
Internally, dual perspective is to work with file bytes. It doesn't recognize any specific format for consoles. The actual direction is to follow the generic approach and to avoid any specialization for a specific console format.

FAST6191

  • Hero Member
  • *****
  • Posts: 2894
    • View Profile
Re: Dual patcher: Bug Tracker
« Reply #3 on: April 29, 2014, 09:01:40 am »
I am not sure how well it work in the wild, at least not without some of kind of pointer awareness. That was not a joke either as FF6 is probably one of the titles that has been disassembled to the level where you could do that, likewise I have seen some things approaching that in the pokemon, fire emblem and especially the golden sun world (see some of Atrius' tools). By all means have a generic aspect too though. The other alternative is you reengineer the (or most popular) patches to be compatible, if the are not already of course (more than a few patches I have seen are designed to play well).

"Free space" collisions are almost certainly the main killer but the slightly more subtle effects (I change how the text engine works and it troubles things expecting a stock one, worse is when things expect more VRAM than now exists thanks to another hack) are not exactly orders of magnitude less common.
How much free space is there in FF6? I have not tangled with FF6 SNES (the GBA being my main poison there) but the SNES is not noted for being practically unlimited in terms of space, to that end space fights may be less not considering how things will play out and more "this is the only space I have".

On undo/anti patches they are typically not hard to make for non relocating/filesystem based systems -- you swap the source and destination ROM where the new source is the stock with the single patch you need to undo patch and make a patch from that. Granted that may not be immediately obvious to an end user. Also "take a backup" solves a few problems there, many patchers even doing just that (or generating a new file).

Thinking about it though for stacking patches I would like to see a source, functionally infinite patch options (add one and a new selection dialog/option appears, make a poll on a forum for a similar idea) and a checkbox to turn things on and off, maybe also patch order selection.

If you are looking at the SNES does that mean you are not looking at any kind of data relocation support?

I forgot to ask last time but will your patcher support expanding the file in general (3 megs to 4 megs for example), not all formats do it and it may not be default functionality in the file handling library you are using.

HatZen08

  • Jr. Member
  • **
  • Posts: 20
    • View Profile
Re: Dual patcher: Bug Tracker
« Reply #4 on: April 30, 2014, 06:29:45 am »
Dual works with the concept of the undo and applied bytes. It works for binaries files but I will use text files to facilitate the explanation.

As example, considerate that you have three text files called orig.txt, mod1.txt and mod2.txt. The orig.txt correspond to the clean and unmodified file. Mod1.txt and mod2.txt are copies of orig1.txt which were modified to add a new code.

Code: [Select]
orig.txt  0123456789
mod1.txt  0ABCDE6789
mod2.txt  0123VWXYZ9

Let's make a dual patch between orig.txt and mod1.txt called patch1.dua. They have 5 different bytes between them and it begins in the position 1. The undo bytes will be “12345” and the applied bytes will be “ABCDE”. If we create a new patch called patch2.dua between orig.txt and mod2.txt, the difference between them is 5 bytes and they start in the position 4. The undo bytes are “45678” and the applied bytes are “VWXYZ”.

Code: [Select]
patch1.dua position 1, 5 bytes, undo = “12345”, applied = “ABCDE”
patch2.dua position 4, 5 bytes, undo = “45678”, applied = “VWXYZ”


If you get a clean copy of orig.txt its bytes will be “0123456789”. When you try to apply patch1.dua, its undo bytes will be verified against the target file. In this case, “12345” match the target file for the position 1 to 5. The applied bytes will be written in the file and the file bytes will now be “0ABCDE6789”.

If you try to apply patch2.dua, it will check his undo bytes against the target file. In this case, for the position 4-8 in the target file, its bytes will be “DE678” but the undo bytes in the patch will be “45678”. They don't match and the patch won't be applied to avoid a collision. To apply the patch, patch1.dua must be removed first.

If you have another patch in a different format (like IPS), you only need the clean rom and a copy to create a dual patch. Apply the IPS patch in the copy and create a new patch between the clean rom and the copy where the IPS patch was applied.

Dual is aimed to manage multiple dual patches in the same target file. When the setup of the patches is finalized in the target file, another patcher can be used for distribution. You only need the clean target file and the target file which was modified by dual patches. Patchers with high compression or more advanced features can be used.

There is too many issues related to this area and a unique tool can't solve everything. Dual is aimed to avoid collisions between dual patches and to facilitate their management. It may not be perfect but it surely helps. You know, it is my first patcher. I still am learning. :-)

I don't plan to include any kind of relocation support. Also, dual don't support file expansion. You can use specific tools for this purpose.