I've recently become interested in investigating and documenting Suikoden II's sprite assembly, event code, dialogue, etc; basically all its file formats. However, I'm not sure what's been investigated already; I can't find a whole lot of technical discussion on this game anywhere, and given its rarity I fear there may not have been very much technical investigation at all up to this point.

Assuming that's the case, I guess the graphics compression algorithm would be as good a place to start as any. Does anyone here who's worked with PSX-era Konami games feel that there's a particular compression routine or at least a general species of compression routine Konami typically used for its sprite-based graphics? For example, some basic knowledge of LZSS sliding window compression gets you surprisingly far in Square Enix PSX-era games. It'd be awesome if Konami used LZSS too, but I'm assuming there's other efficient techniques out there so I'm not holding out too much hope for that.

Er, I still need to actually run Suikoden II through a graphics viewer to see if the graphics even *are* compressed, but I'm assuming that they are until I get some time to investigate. If they aren't and the sprites and tilesets are literally just hanging out right in the open, I'll laugh at myself with you all.  

EDIT -- NOTE TO SELF: Graphics most likely compressed. Next step, compare uncompressed sprites and portraits in VRAM to files in the 120_Play folder and see if any data in game memory dump can be matched to suspected compressed files in that directory.

EDIT -- NOTE TO SELF: Fantastic! Experiment proved that the character sprites (as well as portraits!) are contained in the 120_Play folder! Sprite assembly and animation appears to be self-contained, otherwise replacing Nanami with Ada in that folder would have produced a screwed-up Ada. Also note -- Suikoden II keeps its sprite data in VRAM a deceptively long time; I had to manually switch Nanami out of the party to refresh her sprite data. Otherwise it was kept unchanged in the savestate until that point, despite going in and out of battle, in and out of towns, etc.

Only things that apparently got messed up during the simple switcharoo experiment:

#1. When the swapped character sprite dodges, the game seems to freeze consistently. Ouch. Something's up there, maybe a quirk in the animation or sprite assembly data.

#2. While sprite palettes are contained in the character's graphics pack, it would appear that the portrait palette is not.

#3. Furthermore, the swapped character's portrait appears at the end of battle (when experience, etc., is tallied) but seems garbled in the party formation menu. Oddly enough, when the swapped character trades places with an arbitrary normal character, the swapped character copies the normal character's portrait. Quite odd.

Now on to VRAM examination and comparison with the source file, and then victory! :crazy:

If anyone else wants to take a look at the Suikoden II sprite graphics pack format (again, palettes definitely and sprite assembly most likely included), Nanami's at 0xB1DC000 in a 2048 byte/sector ISO. Ada (arbitrary pick since I wouldn't have to repointer if I used a smaller graphics pack, and I don't know for sure how pointers in Suikoden II work yet) is at 0xB0C2800 in a 2048 byte/sector ISO. I strongly suspect compression still, because Nanami's graphics pack looked like a palette followed by compressed gobbledegook in tilemolester.

I am so freaking glad that I know what "LBA" means after chatting with more experienced modders some time ago. IsoBuster tells which sector the files start on as long as it can sense a proper table of contents.

EDIT: Okay, I've finally got (hopefully) the Rosetta Stone of Suikoden II graphics compression.
http://www.sendspace.com/file/yjrg02

Inside the zip are the following files:

Nan 120 Play: Nanami's graphics pack straight from a 2048 byte/sector ISO. Contains (probably uncompressed) palettes and most definitely compressed sprite and portrait data. Looks like it starts with a header table -- I'm most interested in the data starting at 0x31E4; 0x3D74/0x3D94 because judging from the dumped RAM, the sprites were decompressed from data around one of these addresses.

NanamiSpriteRAW PERFECT: Uncompressed spritesheet strung together from VRAM data; Microsoft Excel is the most underrated hacking tool evar. :thumbsup:  There's probably a bit of extraneous data hanging around either at the beginning of this file or the end, but I wanted to make sure that I caught the whole sprite sheet I saw in VRAM. Format is 4bpp-reversed, 2D. 16-color palette.

NanamiPal.zst: The sprite sheet's native palette in a format that Tilemolester can understand. Creaothceann's PVV3 is the second-most underrated hacking tool evar.  :beer:  

RAM Dump: I might be using the term "RAM" wrong here; it's whatever leaps out of pSX when you tell it to "dump memory." It contains large pieces of the compressed Nanami graphics pack, as well as several of the graphics pack's uncompressed palettes. Compare 0x3204~0x3B30 of Nan 120 Play to 0x1428E4~0x143210 of this file; same with 0x3DA0~4950 of Nan 120 Play and 0x143478ish~0x144030 of this file.

VRAM Dump: Not a huge deal now that I've teased the uncompressed sprite sheet out of it, but you can throw it into PVV3 and take a look at the state of the game's visuals when I made the RAM/Memory dump.

The goal now is to see if there's some recognizable compression method at work in the Nan 120 Play file by comparing sections of it to NanamiSpriteRAW PERFECT. I won't be able to get back to this for a couple weeks to take a good look, so I wanted to dump what I've observed and what I've got here in the meantime in case others are interested.

EDIT: Actually, now I'm more interested in the earlier part of Nan 120 Play, from around 0x690 on. While this portion of the file doesn't seem to appear in RAM, it's always possible I didn't dump enough RAM, and there's some short byte strings common to both the compressed file and the uncompressed file here. Going to the uncompressed NanamiSpriteRAW PERFECT and zeroing in on some nonzero byte strings should give you search results in the 120 Nan Play file.

---

Earlier in the day...

My goal is to document as much of Suikoden II's file format as possible, and hopefully someone with programming knowledge will take interest in writing an editor. I just fired up the game again after getting inspired to embark on a possible Suikoden fan project down the road myself, and I was just blown away by the technical quality of the game (far superior to the original Suikoden). It'd be great if there were an entire community devoted to Suikoden modding, but alas, I think it's going to be a long, winding road indeed.

Lacking uber capabilities, I succeeded in brute force location of Nanami's uncompressed sprite sheet in VRAM. Problem is, VRAM is viewed two-dimensionally and the bytes would have to be presented in a width that TileMolester just can't reach for them to align correctly -- agh! I got around that by doing some crazy ninja stuff like transferring a section of VRAM to a new image and switching between 8bpp and 4bpp encoding, then widening, to gradually separate Nanami's data from the other VRAM data interleaved with it, and got the uncompressed sprite sheet. Now the problem is, I just realized Tilemolester corrupted the raw data slightly, possibly due to Tilemolester's penchant for assigning the same color to different slots in its default sample palette. Arrrgh!

When the sprite sheet distilled from VRAM is compared to the original VRAM data, there's a couple places where 0x00s have been converted into 0x20s, for example. That'll play hell with figuring out the decompression algorithm, because I'm trying to do it by brute force comparison of the compressed and uncompressed data.

Since I don't want to piece together the sprite sheet by plucking its disaligned segments straight from VRAM (it seems putting Humpty Dumpty together again would be easier), I'm going to have another go at distilling the sprite sheet via Tilemolester and try making sure there aren't duplicate colors on Tilemolester's default sample palette when I copy the image from one window to another this time around.

This would all be so much easier if Tilemolester could just widen images to the width that PSX VRAM uses. Anyone know why Tilemolester is so limited? Is there any other raw image viewer that can exceed Tilemolester's max image width?

Again, the current goal is to figure out the graphics decompression routine used in Suikoden II by comparing an uncompressed spritesheet with its compressed counterpart, Nanami being the arbitrary example. I know this is extremely frowned upon by experienced modders (I should learn how to read PSX ASM sometime and just find the decompression routine), but so far I'm one-for-one using this method. Things are looking up because there's only one section of Nanami's sprite file stored in RAM, or whatever the output is when you tell pSX to dump "Memory." My hope is I'll be able to compare that section of RAM with the uncompressed sprite sheet and figure out how the decompression transformed the compressed file into the uncompressed version.

If I can get an accurate uncompressed sprite sheet, I'll post that and the part of the compressed graphics file stored in RAM so others more familiar with various compression algorithms might be able to provide some insight.

EDIT: Crap, just wasted an entire morning to realize that Tilemolester just isn't cut out for this -- there's too much data corruption when transferring data from one image to another; things like 0x00s turning into 0x0Cs or 0x00s turning into 0x20s. I'll have to use the Humpty Dumpty method after all. Maybe it won't be so bad...now I wish I had a hex editor that could display greater than 256 columns at a time though. Then I'd be able to dump it into a spreadsheet and copy the properly aligned image data into a new hex file. It's so frustrating capturing raw data from VRAM in PSX games!

Tauwasser, this is what I'm getting for NanamiSpriteRAW PERFECT, 4bpp-reversed, 2D and importing NanamiPal.zst for the palette in TileMolester:


That should be absolutely correct. If that's not what you got with a 4bpp-reversed 2D codec, I might have included the wrong file in the zip or something. Let me know if that's not what you get with those settings and I'll have to reupload.

In any case, thanks for the bump! Now I can do this without my post above becoming obscenely cluttered:

EDIT: I made some time to compare unique runs between Nan 120 Play and NanamiSpriteRAW PERFECT. During random investigation, I found unique byte runs shared between the two files at the following addresses: 0x67D9~0x67E2 (Uncompressed) & 0xED3~0xEDC (Compressed); and 0x68A5~0x68AC (Uncompressed) & 0xEE1~0xEE8 (Compressed). The files pass my ad hoc "test for sliding window compression," so it's possible we're dealing with LZ-family compression.

However, I haven't been able to conclusively determine that Suikoden II uses sliding window/LZ compression for its graphics; I just haven't been able to disprove it. And now I'm interested in the fact that David's found library-based compression in the Suikogaidens. Care to share any info about that algorithm you saw in the Suikogaiden text files, David Holmes?

I'm really, totally, a noobie at modding still, so I'm kind of feeling my way around. Nanami's sprite sheet is written to either address 0x440 in VRAM or address 0xC40 if she's in the top-left party formation slot if I remember correctly, so if someone wants to convert that into a RAM address and run a breakpoint to find the decompression routine, I sure won't complain. My main hangup right now is that I know nothing about PSX ASM, so I haven't bothered to try finding and interpreting the actual decompression code.

EDIT: Oooh, just saw all your advice Tauwasser! Thanks! I'll have to ponder on this.

EDIT: And just to be clear, I've switched my own investigation from the later addresses in the compressed file like 0x3D74 and 0x3D94 in favor of earlier addresses in the 0x690~0x2C90 range, because only in the earlier portion of the compressed file am I finding any data shared between it and the uncompressed file. Nanami's got a ton of sprites overall, so the data in VRAM covers only a small portion of that (in battle, about 1/2 of her whole battle sheet is in VRAM at any one time). If the game decompresses the entire sprite collection and then plucks a portion of that for VRAM at any one time, that's probably a further roadblock in this effort.

Sorry for the misinfo with the codec, you're right. I was just ignorant that stuff would be significantly wider than 30ish, so I concluded that the codec had to be a power of 2bpp higher. You're right tho. Still, 62 x 16 tiles is pretty bad.

I took a look at your data offsets (good job finding it, I looked into it too, but couldn't find stuff that quickly). So basically you have to check out the "header" type thing which will point to pointers to compressed data. The first 5 byte seem to be the size, though it could be first four = size and after that = type or something. The compression method is a mystery. It might actually be some some hybrid thing that can use lzxx and some other method. I found that most stuff that happens to be identical is preceded by binary 11000XXX where X + 8 is the number of bytes that follow uncompressed. However, it will jump/reuse really big stuff in between by seemingly only having 5 bytes or so in its stream - yet it will sometimes only reuse only 3 bytes with the same amount of bytes (in compressed stream) that it can use for hundreds of bytes...

This is rather intriguing, keep at it

cYa,

Tauwasser

Sorry for not adding anything to the discussion, but this is one of the awesomest, most interesting and informing threads I've seen in awhile. Watching someone figuring things out and how they did it and the help of other people is encouraging. Thanks guys. :beer:

</AfternoonTVSpecialMode>

Well, I went on and made some compares. I compare the very first data header's files and the output starting at the first sprite. You'll get the idea what I mean with funny jumps. I made pdf files from datafile1.hex (the first compressed datastream referenced) and the whole spritestuff you provided (in *PERFECT data file).

Also, you could check out if any of the other three data files (which get all referenced by header the first pointer @ 0x000C -> header @0x31E4 -> pointer list @ 0x2C6C-0x2C7B -> 4 * datafileN.hex). Contain any unique stuff that is between stuff currently marked... I doubt it though. I think this would be the whole first "animation frameset" for whatever Nanami is doing in the first 4 animations (like...umm... jumping? Maybe?).

I actually got the feeling that the whole compression is related to the tuple pairs that get referenced right before the pointers get referenced or something. Maybe it's some sort of dictionary stuff. Like, get repetitions that are used very often so you don't have to waste 2..5 bytes on sliding windows, but rather have one-byte opcodes for those... or something. This is really strange. It might be unfeasible to try to decode it by hand (which I've done for a few algorithms by now, but none as strange as this one seemingly).

Also, I actually had the idea that the opcodes might also reference other parts of the compressed stream (like, read next x instructions from cur_pos + NNNN). However, that seemed not to be a consistent case. I also thought about bit streaming compression stuff, but it seemed nonsensical when you can find whole strings of literals encoded in the stream which could also be encoded shorter using bitstreaming (there are some 00 encoded literally as well as some stuff that could be accessed through a sliding window setup much shorter).

Anyway, here are the extracted/marked files, so grab 'em while they're hot.

cYa,

Tauwasser

Ok, i tinkered with the header and that's what came to pass:


That's the main header.
I haven't found out what the 210000 would be, but whatever. Maybe it's some kind of code which parts of the header are to be used as it seems kind of extensible to me.

Pointer1 and Pointer2 are either pointers to pointer lists and therefore point to 0x00000000 (as in list is empty), or they are set to 00 by the bytes after [21] or something... Either way, no way to know what they do until we see an example.

Pointer GFX is a pointer to a list of pointers which holds number of GFX pointers. Pointer to pal seems to be limited to point to one palette. Or maybe it's the [21] or something.

Struct1 and Struct2 are somewhat weird.

Struct1: It's 14 bytes per entry: [Unknown (4B)][Some counter (4B)][Pointer1 (4B)][Unknown (4B)][Pointer2 (4B)] Pointer1 seems to always point to 4 bytes, whereas pointer2 points to an extensible structure (or maybe one of the values determines its length).

Struct2: It's 8 byter per entry: [Number of entries (4B)][Pointer to entries (4B)]. Each entry is 8 byte, all unknown in function.

That's all for Nan 120 Play. If you got more examples, do upload them.

cYa,

Tauwasser

Wow, I actually think I finally understood how it all works

That is, the concept, not the encoding format. Basically, all four first frames can be derived from datafile1.hex alone. The other data pointed to seem to be some vectors telling it exactly how to do the vram wrapping or something (guess based upon adressing involved, goes in jumps from 0x00, 0x20, 0x40 etc... seems to me like it's actually wrapping 20 tiles per frame around and anding absolute with 0x3FFF... just look at the data that struct1 pointer2 is referencing).

Please take a look at this.

Basically, it's a comparison over all frames for an animation (in any animation, nothing is going to change much, right?). So it takes the bits that correspond most in all the frames and encodes these literally. Anything else is encoded in some scheme before the data it seems. It now must know which bits to set and reset based on which frame is being produced. With this scheme all "animated" pixels can be compressed as difference matchings to any "base" frame (which does not correspond to any frame actually produced!).

I hope this info sheds some light. And yes, it's mindfuck. However, with that knowledge, it seems straightforward to reverse the algorithm now... I actually have some stuff worked out, but I'm not sure about that yet, so I won't post it now. That, and I'm tired....

cYa,

Tauwasser