Banner
Views: 729,190,369
Time:
12 users online: agostino1991, BTD6_maker, chillyfox, Darolac, GbreezeSunset, Golden Yoshi, kellykelster, Kusrry, MarioFanGamer, Sixcorby, ThalesMangaka, Wind Fish - Guests: 43 - Bots: 142Users: 38,385 (2,177 active)
Latest: Braniel
Tip: Read Lunar Magic's help file and SMW Central's FAQ, as they cover most of the basics of SMW hacking.Not logged in.
Floating IPS v1.31
Forum Index - Sunken Ghost Ship - C3 Museum - Summer 2015 - Floating IPS v1.31
Pages: « 1 »
Floating IPS v1.30 makes delta BPS creation quite a lot faster. It also adds a few other uninteresting changes. I suspect our SM64 hackers should like this, I've seen them complain about the old one being slow.

  • Figured out how to use suffix sorting to create patches, and implemented that. The delta BPS creator is now a LOT faster; about 50 times faster on SM64 Star Road on my Linux box (though Windows sees smaller speedups, due to lack of OpenMP). The resulting patch is 9% smaller, too.
  • Since the new delta BPS creator now combines the advantages of both with the drawbacks of neither, I removed the other ones. You can use the linear BPS creator from the command line, but I don't recommend it.
  • This also fixes a bug with zero-size input files. (Okay, that doesn't really have anything to do with suffix sorting, but it's fixed anyways.)
  • Added --ignore-checksum flag, to allow BPS checksums to be wrong. (It still prints a warning, and rejects mis-sized input ROMs.) I still believe it's a stupid idea, but if byuu says it's allowed, then I guess it is...
  • Flips now detects if you apply a BPS to its intended output and gives a more specific error message than "wrong ROM".
  • Flips now refuses to create IPSes from files larger than 16MB. IPS has never worked above 16MB, but it previously changed things up to the 16MB limit (Lunar IPS did the same). But no more.
  • Flips now rejects some more invalid command line arguments.


I'm considering making BPS the only output format, and starting patch creation while asking for the output filename; this would make it a few seconds faster. If you like IPS, this would be a good time to speak up.

Comparison of various patchers:

Patch sizes (bytes):
Input filebeat v03Floating IPS v1.30Flips v1.30 morememFlips v1.21xdelta3xdelta3 -9xdeltaxdelta -9bsdiff
Der Langrisser (J) -> (U)823,917817,190817,190819,461817,743816,452819,654819,564832,029
Mystic Ark (J) -> (U)252,938234,942234,942245,413225,837219,237198,567198,517157,116
bsnes v078 -> v079234,315209,601209,601208,662215,407195,846252,153251,91072,175
FEoEZ (J) -> 48mbit484848486363418418201
SM64 -> Star Road8,243,6106,805,4426,805,4427,833,0136,888,1696,475,1825,810,7285,787,9185,713,005
empty -> Linux 4.0.4 .xz84,240,12982,310,64282,310,64282,318,97782,312,23482,312,23482,335,84382,335,84382,674,709
Linux 3.18.14 -> 4.0.4 .xz79,044,60882,069,09382,069,09382,092,06182,070,60682,070,60582,094,38082,094,38082,427,979
Linux 3.18.14 -> 4.0.4 (256M)---3,326,1113,326,1113,544,7034,023,1213,432,7125,553,9885,535,3723,554,618
Linux 4.0.3 -> 4.0.4 (256M)---572,117572,117567,479904,301616,4121,082,5961,070,17040,747
Linux 3.18.14 -> 4.0.4---6,488,067---6,857,5417,916,5746,777,42112,707,63712,676,355---
Linux 4.0.3 -> 4.0.4---1,002,377---994,7361,528,2461,039,7153,626,5453,605,393---

Time (seconds):
Input filebeat v03Floating IPS v1.30Flips v1.30 morememFlips v1.21xdelta3xdelta3 -9xdeltaxdelta -9bsdiff
Der Langrisser (J) -> (U)3.960.390.311.250.070.080.080.061.07
Mystic Ark (J) -> (U)5.160.480.443.910.040.090.040.050.97
bsnes v078 -> v0794.110.190.141.410.040.130.040.070.28
FEoEZ (J) -> 48mbit0.240.770.750.230.020.040.040.040.91
SM64 -> Star Road584.414.333.81207.561.092.611.212.0617.14
empty -> Linux 4.0.4 .xz4523.5037.4617.06809.735.364.922.402.3010.93
Linux 3.18.14 -> 4.0.4 .xz16730.0053.7224.362479.2211.2911.386.386.19204.35
Linux 3.18.14 -> 4.0.4 (256M)---31.9539.629040.004.405.122.382.59117.28
Linux 4.0.3 -> 4.0.4 (256M)---30.2542.80336.261.922.271.621.81115.90
Linux 3.18.14 -> 4.0.4---85.90---33662.009.6710.075.295.62---
Linux 4.0.3 -> 4.0.4---88.72---1155.863.814.493.623.95---

Memory usage (megabytes):
Input filebeat v03Floating IPS v1.30Flips v1.30 morememFlips v1.21xdelta3xdelta3 -9xdeltaxdelta -9bsdiff
Der Langrisser (J) -> (U)95325254501455534
Mystic Ark (J) -> (U)141467875601558868
bsnes v078 -> v07947182840421384421
FEoEZ (J) -> 48mbit1736110510262157101085
SM64 -> Star Road406292514211861811818176
empty -> Linux 4.0.4 .xz2,5244777921,2288217822164
Linux 3.18.14 -> 4.0.4 .xz4,7348631,4862,3781472421221221,313
Linux 3.18.14 -> 4.0.4 (256M)---2,5704,6172,7501392353943944,352
Linux 4.0.3 -> 4.0.4 (256M)---2,5674,6152,6751392343833834,352
Linux 3.18.14 -> 4.0.4---5,594---5,899139235785786---
Linux 4.0.3 -> 4.0.4---5,634---5,691139234775775---

The Far East ROM adds 1MB zeroes at the 1MB mark.
The 256M Linuxes are the first 256MB of the Linux source code tarballs; some patchers would use more RAM than I have to process that.
The xz Linux is the official .xz, to see how well they handle (mostly) random data.
The null file is a file containing a single 00 (Flips 1.21 bugs up on zero-size inputs). xdelta doesn't like it either.

beat is about twice as slow as Flips 1.21, and uses twice as much memory, despite us using mostly the same (bad) algorithm; I'm not sure why, we're both using 64-bit offsets. Its patches are also slightly bigger; mostly due to 1.21 picking a closer match if there are multiple equivalent, possibly also due to changed heuristics.

Flips 1.30 gets rid of beat's algorithm, switching to one that's O(n log n); see libbps-suf.cpp in its source code for more details. As such, it handles big files a LOT better. It also narrowly beats 1.21 for most inputs; its changed algorithm allows it to find better matches much of the time (beat/1.21 don't allow picking matches across the entire target file), though it loses the pick-a-closer-match optimization from 1.21, so it loses on the Linux .xz.

bsdiff completely crushes everything on the bsnes executables; it's designed for minor updates to binary programs, and it does indeed do a good job with them. It also does a good job on the Linux tarballs too, I guess .tar looks like an executable? For the others, it's roughly the same as the three BPS creators.

e: updated the analysis a bit, it was done on an older beta of Flips 1.30

--------------------
<blm> zsnes users are the flatearthers of emulation
Always hype for performance.

Originally posted by Alcaro
I'm considering making BPS the only output format, and starting patch creation while asking for the output filename; this would make it a few seconds faster. If you like IPS, this would be a good time to speak up.

There's no reason to prefer IPS since Flips can handle softpatching files instead of the emu. BPS is the way forward for hacking.
Great work, delta BPS creation works like a charm. It previously went on way too long to be viable.
Awesome work!

For those not in the know, I spent a stupid amount of time trying to figure out a non-O(n^2) algorithm for finding differences between two files. As did many others. Alcaro solved a really difficult problem here.

Quote
I'm considering making BPS the only output format, and starting patch creation while asking for the output filename; this would make it a few seconds faster.


Be sure to rename your tool to Flbps when you do xD

Quote
bsdiff completely crushes everything on the bsnes executables; it's designed for minor updates to binary programs, and it does indeed do a good job with them


Yep, its algorithm is built around the idea of detecting the usual changes that happen when you've made small changes and recompiled your binary applications. Especially around x86/amd64. bsdiff is obviously going to win in the same way PNG will beat ZIP on images, FLAC will beat ZIP on audio, etc.
Originally posted by byuu
Be sure to rename your tool to Flbps when you do xD

I've considered it ever since I switched it to default to BPS-linear, but I'd rather keep the name pronounceable. Flbps sounds like blowing a raspberry, or something.


And apparently this release is bugged up; it requires a few files it's not supposed to require. I'll fix it when I get home tomorrow, I used wrong compiler flags.


e: Dear various SM64 guys: Would it be of any help if I teach Flips to apply PPF patches? It won't create them, and you'll still need to expand the ROM, but it should still be able to replace your PPF-o-Matic.

--------------------
<blm> zsnes users are the flatearthers of emulation
Originally posted by Doopliss_
Originally posted by byuu
Be sure to rename your tool to Flbps when you do xD

I've considered it ever since I switched it to default to BPS-linear, but I'd rather keep the name pronounceable. Flbps sounds like blowing a raspberry, or something.


And apparently this release is bugged up; it requires a few files it's not supposed to require. I'll fix it when I get home tomorrow, I used wrong compiler flags.


e: Dear various SM64 guys: Would it be of any help if I teach Flips to apply PPF patches? It won't create them, and you'll still need to expand the ROM, but it should still be able to replace your PPF-o-Matic.


Actually that would be a big help. Using PPF-o-Matic for files other then ISO's can be a bit of a inconvenience.
Originally posted by byuu
For those not in the know, I spent a stupid amount of time trying to figure out a non-O(n^2) algorithm for finding differences between two files. As did many others. Alcaro solved a really difficult problem here.

well I could easily make you an O(n^3) one
Is the algorithm at all conveyable to mortals? This sounds interesting.

Quote
If you like IPS, this would be a good time to speak up.

I do like it because it's familiar, but there's literally no rational reason to not prefer BPS, so might as well future it up yo.

--------------------


 
Originally posted by Vinnyboiler
Actually that would be a big help. Using PPF-o-Matic for files other then ISO's can be a bit of a inconvenience.

Convince the SM64 guys to switch to BPS (it'll get rid of the expander, and BPSes are smaller than PPF) and I'll teach Flips to apply PPF. Deal?

Won't be ready until after C3, though; I've got a bunch of other stuff to do first. For example getting rid of those DLLs.

Originally posted by WhiteYoshiEgg
well I could easily make you an O(n^3) one

oh yeah? I raise to you O(∞), it's eight bytes long and also cures cancer

Quote
Is the algorithm at all conveyable to mortals? This sounds interesting.

I tried to describe it in the source code; libbps-suf.cpp, near the top, below some random shell commands I forgot to remove. Not sure how mortal-compatible it is, though...

Some of your questions may be answered in byuuland, I cross-posted it. Several of them have been looking for a faster BPSer for quite a while.

--------------------
<blm> zsnes users are the flatearthers of emulation
Quote
Is the algorithm at all conveyable to mortals?


No. The basic idea of building a suffix array is easy enough; but doing so in O(n) time is pure voodoo.

Thankfully, the complexity won't matter for patch appliers =)

Quote
Some of your questions may be answered in byuuland Super byuu World Central
I supported .bps from the start. I say it's a-go.
Originally posted by byuu
byuuland Super byuu World Central

byuu's Message Board of Wonders and Other Miracles.

1.30B is up. Zero functional changes, it just gets rid of the MinGW DLLs. (I think the binary is a little smaller, too.)

--------------------
<blm> zsnes users are the flatearthers of emulation
double post because I sux.

Lui37 found a kinda serious bug that makes applying a BPS to a headered ROM emit a broken file. Also cleaned up some internal things, and wiped out a bug that made the GTK+ GUI get confused about which patch format it's using. Please redownload.

--------------------
<blm> zsnes users are the flatearthers of emulation
I think keeping IPS output support would be good for compatibility's sake (e.g. making patches for people who are using older IPS patchers like LIPS or IPSHARP that don't support BPS). But really it probably isn't a big deal as long as it continues to support IPS input for the sake of old patches. On the other hand though, correct me if I'm wrong, but isn't IPS still the only official standard here on the site? It would be silly to switch if BPS patches aren't even being accepted. could totally be wrong though
Originally posted by eXcavator
On the other hand though, correct me if I'm wrong, but isn't IPS still the only official standard here on the site? It would be silly to switch if BPS patches aren't even being accepted. could totally be wrong though

You are, they are.

Originally posted by submission rules when attempting to submit a hack
Submitting Content
Create an IPS/BPS patch - Download Floating IPS and follow its instructions.


Pre-Edit: That sounds derisive and rude. I don't know how to make it not. Know that it is not meant to be derisive or rude, just information.
Pages: « 1 »
Forum Index - Sunken Ghost Ship - C3 Museum - Summer 2015 - Floating IPS v1.31

The purpose of this site is not to distribute copyrighted material, but to honor one of our favourite games.

Copyright © 2005 - 2019 - SMW Central
Legal Information - Privacy Policy - Link To Us


Total queries: 23

Menu

Follow Us On

  • Facebook
  • Twitter
  • YouTube

Affiliates

  • Talkhaus
  • SMBX Community
  • GTx0
  • Super Luigi Bros
  • ROMhacking.net
  • MFGG
  • Gaming Reinvented