Superb!

One little thing: I don’t mean to throw wrenches or anything, but the binary name upx is already used by the UPX utility. This will create unpleasant name collisions for some poor sap somewhere.

Way better.

(Didn’t verify; mac user. Perhaps I should take one from Reagan’s book more often, eh?)

Fuck yes! We(Being the hacking/translation scene)'ve been needing this for years!

Yay!
Glad to see you guys like it. Thank you so much for the support!! It's absolutely critical to make this work (and replace IPS once and for all), of course.

I'll go over the format here in more technical detail, for those interested.

Okay, so we already know the format is:


So let's go over why things are the way they are ...

The signature, I wanted a dword-alignment, so I added "1" at the end. This isn't so that the format can change in the future to "UPS2", although perhaps in the far future, "UPS2" will be a different type of patch, such as an xdelta-like patching algorithm. They won't compete against each other. They would be combined in a container such as NINJA3 or whatever. But suffice to say for now, it's just a signature.

Next, the file sizes. The reason they are at the top and not the bottom of the file, is because it's easy to get a file size without reading the whole thing, and because if it were at the bottom, you couldn't automatically tell where the footer began, as it would not be constant. And the file sizes are variable-length encoded so as to support up to infinitely sized files.

So why put the CRC32's at the bottom? Simple, they can be computed during patch creation. As you make the patch, compute the CRC32, and you only need a single pass over each file to make the patch. Likewise, the patch CRC32 will be known at this point if you keep track of each write. The patch CRC32 comes last because it contains even the file CRC32s (eg if you modify the file CRC32's, the patch CRC32 needs to be modified as well. This is a good thing.)

And because of this exact ordering, it means the two input files can be read, start to finish, one time. The patch can be written, start to finish, one time. There's no need for special back-seeking, or read+write file permissions as would be required with any other ordering.

---

Okay, now what's this [V] stuff about? This is basically:
http://www.codecodex.com/wiki/index.php?title=Variable-Length_Integers

... but with a twist. We toggle the meaning of bit 7, 0 = continue, 1 = end. This cuts out two math operations during patching, which makes the algorithm faster with no speed penalty.

Here is a C implementation of the encoding / decoding of pointers. It's the same for file sizes and for patch relative offsets.


A bit of magic, but 100% optimal. There are no two pointers that decode to the same value. You'll see why this trick is needed soon.

Lastly, we have the actual patch blocks. All blocks contain XOR data of the two input files, followed by block 0x00 terminators when differences end.

XOR has an interesting property: X^Y=Z.
And now, both X^Z=Y and Y^X=Z.

This property means that the same exact patch file is bi-directional. That means you can make a patch against your original Japanese file and the English translation. When someone applies the patch once, it turns into the English game. Apply it again, and it turns back into the Japanese game! You don't have to keep both files around anymore!

The upside is that decompressed, it takes the same exact number of bytes as an IPS patch. The downside is you lose a bit of compression power, as XORed data contains two streams of data, rather than one. It's less likely a compressor will find patterns. We think it's worth it.

Now, the actual offset pointers are relative, not absolute. This combined with the pointer encoding trick means that ~95% of pointers are only one byte long, compared to a fixed 3 for IPS. And better yet, it supports infinitely sized files.

Because the pointers are always relative, we avoid the semi-tricky case with IPS patches that store out-of-order patch offsets. This is impossible with relative pointers, so we need not even worry about this case.

By relative, I mean the decoded pointer says "seek N bytes forward to find the next difference", rather than 'seek to offset N to find the next difference."

This has an economy of scale that works to our advantage, too. When data has lots of changes close together, you have to keep making new change blocks. This is the densest, worst case scenario for both UPS and IPS.

IPS' worst case is a file that changes every other byte. In that case, an IPS patch will be 8+filesize/2*(3+2+1) bytes. Eg 1MB becomes a ~3MB patch. For UPS, this will be: 20+filesize/2+(3) bytes, or ~1.5MB. Still bad, of course, but not awful. I will note that uCON64 has some black magic that writes out unchanged bytes as an optimization, we give that up to avoid encoding the lengths.

That is ... each block ends with 0x00. This is actually another special property. If X==Y, then X^Y==0x00. Convenient. As soon as two bytes are identical, that marks the end of a block. So long as we write out the first identical byte (as 0x00), this counts as our terminator. Think of it like C-style strings. Null-terminated, rather than Pasal-style strings, with the length at the beginning.

Another advantage is that we don't ever have to stop a diff block because the length exceeded our length size (eg a match >= 65536 bytes in IPS.) It simplifies patching a bit more.

Next up, we omit RLE. Why? I've done tests against IPS with and without RLE. My findings were that IPS+RLE was smaller than IPS, but IPS+RLE+ZIP was larger than IPS+ZIP. So you add extra complexity to shrink down a patch, and for what? Your bandwidth bill ends up larger, and the part that really doesn't matter (the user's ~200GB hard drive) shaves off a bit of size. Lame.

I've decided it's better to leave compression to compression algorithms. They continue to improve with time. Store the UPS file in a ZIP, or 7-Zip, or whatever archive type is popular in the future. Patch appliers can even do this automatically, stick the ups file inside a ZIP and call it .upz. Most emus support IPS patches inside ZIPs already ... this is a logical extension of that.

By omitting RLE, we also make the patching algorithm a lot simpler. Both for creating and for applying patches.

When reading past the end of the file, you have to have a value to XOR against. Unlike libc, I return 0x00 here, rather than 0xff. Why? 0x00 is more common, and it also results in clear-visible data at the end of the file. Let's be real here for a minute, using 0xff to invert the data doesn't do us any good at all. In fact it may hinder some compression algorithms (eg ones with explicit ASCII text detection,) and the data there, if copyrighted, is no less illegal when XORed against 0xff as it is against 0x00.

The downside here is that if you expand a ROM from 2MB to 4MB, and you expand with 0xff, expect the UPS file to end up at ~2MB or so, because it will see that 0x00 != 0xff. Again, the compression eliminates this. It will compact that entire expanded block to ~3 bytes or whatever.

Lastly, all blocks, even the last one, write out the 0x00 terminator, even though the last one isn't technically needed. That simplifies the patch application process a bit, and makes the patch format completely consistent.

And that's it! That's the whole spec. One of the neatest things is that any compatible patcher can only make a patch exactly one way. There's zero room for variation, there's zero "holes" where some odd behavior can occur between different patchers (eg IPS with an offset of "EOF", or length of 0, etc.) It's easy to tell if your patcher is correct -- just compare a patch made against the reference library. If it's bit perfect, you got it right.

And again, the format is 110% finalized and sealed off. This is so that we don't end up with all the extension shit added onto IPS. Eg Lunar IPS patches add a clip command that SNESTool won't parse. They also added RLE after release, and such. If anyone does this with UPS, it will be a license violation. It is absolutely not permitted. This means that the current UPS patcher will support every UPS patch ever made, which is very important. UPS doesn't need a clip command, because unlike IPS, it stores file sizes for each file, which makes clipping / growing trivial.

Probably the most controversial feature is the lack of RLE. Again, I really feel that simplicity is more important. The patch applier can pull the UPS right out of a ZIP if need be. I can see some people stressing when the UPS patch is much larger than UPS before compression.

And that's all. That covers every possible input case and edge case. Feel free to ask if you need more clarification on any specifics of the format.

I'm lazy, anyone want to help out?

Here's something to make it more interesting:

http://projects.elsallia.com/
http://projects.elsallia.com/der-langrisser/downloads

Der Langrisser v1.02 was released today in UPS format. It's a six-year anniversary, April Fool's release. Don't worry, it's a real release :)

Also, Nach's patcher should be out soon enough. So you won't be limited to just mine for long.

Well, my patcher requires Windows or Linux. I'm not going to pay Apple $600 for $200 worth of hardware just to run their crippled OS with two configuration options in the entire OS (color of buttons = blue or teal, minimize effect = genie or scale.)
If they don't want me to run their OS on affordable hardware, then their users suffer by my work not being available there.

Mine at least doesn't require anything else to run. No .NET, no MFC DLLs ... none of that.

Anyway, if you've ever used Nach's NSRT or NSFE programs written in Qt ... that's what his patcher should be like. His stuff, being Qt, runs on Windows, Linux and OS X. And he usually provides binaries for them all, along with auto-translation stuff for other languages and such. In other words, it should be a lot nicer than mine.

As for D and the community ... I don't see why that matters, really. D wasn't involved in UPS, it's basically Nach's NPS format ideas with me setting up the file layout and adding that pointer encoding thing and making a package out of it. Nach agreed that the encoded pointers work good, so we're merging that to UPS.

D will be creating the NINJA3 spec. Both specs are basically public domain, but like Firefox, if you want to change it, you need to rename it. Thus, it shouldn't matter who dislikes who.

But if you guys want to stick to pure UPS to spite D, that's fine by me. Or use NINJA3 and get all the benefits the container format adds. Just please, let's kill IPS once and for all. Please :)

NINJA3 will basically store UPS files inside of it for each individual patch, and will encode things such as authorship, system information, header information, etc on top of it. It will also handle multi-patch setups for eg PC games. But as the core uses UPS anyway, you can use one or the other. It's up to you. We aren't pushing either one over the other.

If either get accepted, the UPS spec will succeed. But NINJA3 will only succeed if people take to that over the simplicity of raw UPS files. It's really up to you guys to decide on that one. The main advantage of NINJA3 (header detection and such) can be abstracted out of the patch format to the patcher for most systems (SNES, Genesis, etc), thanks to storing file sizes and CRCs.

Hopefully myself and Nach have good standing in the community, at least :)