Reverse Engineered old Compression Algorithm for Frogger

An example why I love the internet. There are people still exploring the 1997 game Frogger! In this video we will look at an old compression algorithm to learn how a compression works in general.

I've been wanting to get into understanding save game checksums, but I have no clue where to start as far as reversing. I am very adapt to reversing in-game memory functions but algorithms still confuse me

Sounds fairly similar to Shining Force 2's character pattern compression. A 0 bit means copy the next word into the buffer. A 1 bit is followed by 11 bits of backward offset and 5 bits of repeat count. It starts that far back and copies forward from that location.

The longer patterns such as the fonts are compressed in a much more complex manner involving building words a nibble at a time using a rotating stack palette and varying numbers of bits to indicate the rotation index. Map data is compressed with yet another algorithm.

mwd mapworld?

LOL, NOT the game i was thinking of.

In a childhood i would be realy excited if i was able to create my own maps for games like Mario or Frogger, but now it's not that interesting.

Okay, so you find an ID which is PP20, now since I'm older than you and been coding longer, I remember a list of file ids. I haven't watched enough into the video, but my guess is that it's a PowerPacker compressed file. Which was actually an Amiga compressor that wasn't as good as Crunchmania. Let's see how good my guess is.

Dear god.
Why+

The compression as implemented is not using the PP20 format as well as it could. It was likely programmed to conform to the reverse-engineered decoder in a too simple way. There are a couple of ways to encode the input to conform to the decoder and achieve much better compression. The original PowerPacker had settings for offset/length limits to tune the speed/effectiveness of its compression. (I do not think original PP would compress AAAAA... as repeating of A. Instead it would take more of the AAAA and produce a shorter sequence.

One thing that people seem to be confused about is why it is doing the decompression in a reverse order and had some of other quirks like the "header" and offset at the end. It is designed to be *in-place* decoder, you allocate memory for the uncompressed file, load the file into the buffer and unpack in the same buffer and have assurance that you do not overwrite the source before it is processed. That is also why you can have non-compressible file encoded using the original data, so unpacking in-place is a no-op. Also if the uncompress loop output catches up to the source data, it knows that it is done, saving some cycles for hard to compress files.

I got this video recommendation and thought "Hey, I used to reverse engineer, weird compression codes!".
When watching, I kept getting weird deja-vu. I went to my repo where I had the painstakingly reverse engineered PP20 decoder from ~12years ago and the code was almost identical.
So went to the Frogger repo and saw my name in the decoder file as the original author :D. Nice nostalgia attack :D. I already forgot that I was already asked to allow using the code.

A note on the origin of this code. I had some Amiga mod music files (mostly game music) and working on a mod player. Some were compressed. Many using PowerPacker.
The only thing I could get my hands on was the .library binary file with 68000 machine code, which I had to disassemble and convert to Java a couple lines of Java and catch all bugs testing on real files. Quite fun.

Thanks for the video and a reminder of the past hobbies.

1989 -> 1997... this isn't a lot. I'm not surprised to see this algo being used only 8 years later. Usually, developpers learn their tools then reuse them during their career, especially, LZxx algorithms are pretty versatile.

I grew up playing this game. I didn't realize the fan base for it was big enough that a reverse engineering of the game happened. I would love to see that with Hot Wheels Stunt Track Driver.

Iz id pozzible to pord diz game to NES? 🐱

When I saw the pp20 I already knew. I think the author of power packer was nico Francois

Omg, I know PowerPacker!! I also wrote a decompressor for it once 😆

pp20 is power packer the game may have been on amiga too because i have seen the power packer used for making the music files mod be compressed and yet playable or even used as an archiver.

I was just about to post that pp20 is an Amiga power packer header when you mentioned it.

There's a plugin for total Commander to unpack Amiga powerpacker files.

I love your enthusiasm. Instant subscribe.. Thank you for this video!

wow thanks bro

The audio tracks on the disk have some serious bass!

Wow, i played this as a kid, crazy to see there's still an active community for it!

The Amiga was around for quite a ways into the Windows 95/PS1 era and it was a real devs workhorse: Psygnosis for example was making the leap to PS1 and you can see the fingerprints of Amiga dev tools like Dpaint all over some of their games, in Alundra for example.

haha I really enjoyed this as an old Amiga scene person because as soon as I saw PP20 i thought of PowerPacker.. i didn't skip ahead and got a nice surprise when it actually turned out to be that :D Memories.. thank you, i still remember... I think there's possibly a PP13B as well but its been a long time and I could be wrong.

I had this game for the PS1 way back in the day I never beat it though it was tough as nails.

Files can have any extension, whatever you want, if your file does not follow a known format why would you use a known extension?

I'd be nervous making videos about modding/reverse-engineering Nintendo games, aren't they known for throwing copyright strikes left and right in these situations?

Interesting that all these 500 As could be compressed much more efficiently with a modified RLE I call RLUE (run-length unary encoding, where the length itself is packed in a manner similar to UTF-8 codepoints), and the compression output would be 3 bytes. At least for graphics, I'd always suggest to use any RLE variant as the first step before applying any other compression.

Best ps1 game right here and the soundtrack is great for working out

God this game always kicked my ass. But it was really fun anyways.

There are people who care about such a recent newschool game? I thought it was going to be about the original Frogger from 1981.

Reminds me of the formula that made Doom run so fast

PP was very popular tool back than. I already knew what "PP20" stands for.

funny, i also had a similar compression algorithm to look at a while back, when i wanted to look at what data was transmitted by a particular game to the game server. if anyone is interested, here is the story:

at first i noticed that the json it sent was starting out as readable text, but was more and more garbled up the longer the string got. so i reverse engineered the relevant part of the game. turned out the game dev implemented their own adapted version of LZSS, so i wrote a decoder for it. to be more precise, i copied the reverse-engineered logic from the game into my code without understanding it and wrote tests for it to make sure i copied it correctly and it still behaved like the original. then i refactored my code step by step, verifying via the tests that my code still behaves exactly like the original decoder, and after a while i had some very human-readable and understandable code that was doing the exact same thing as the game and i could analyze it properly and understand what it does. in hindsight, knowing LZSS before trying to do this would have been really helpful, but i guess thats almost always the case, right? ^^

but i wasnt done yet, because for the game to still work while im reading what it sends, i had to also encode it again and send it to the server, as well as doing everythin for the server response as well. i chose the lazy approach and only encoded literal chunks. this made the "compressed" payload larger than the uncompressed json strings, since there were now all of these additional "the next block is a literal block" headers in there. but it worked and neither the game nor the server noticed that i was decompressing, reading and "compressing" their communication data in real time. it was really funny to see that i could get away with that xD

this all took way too much time, but it was a really fun project to do. i often compare these kinds of project to dark souls bosses: it is a lot of work up front, but when you finally get it done and it works, you feel like a total badass, even when you cheese the second stage :D

I wonder at which point is it more efficient to reimplement the game rather than reverse engineer binaries 🤔

I like the original frogger better

WAD = Where's All the Data?

Cool

This is the weird shit why I subbed to you

2 years late but cool

Hi, my name is Rifqi and I'm from Indonesia, help me sir, currently in my country everyone is playing Higgss domino island, can you make a cheat / mod apkk / trick trick that is not detected and can be used in the game? please help sir, so that our family life can change,,. I hope there is a way or trick / application that you gave...

54 dislikes? sheeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeesh

Atari punk rock