VOL compression of .txt files

[Hooman]

Well, I just spent countless hours trying to figure out how the compression works for the .txt files in the .vol files. I think I've got almost all of it figured out. I've started on a decompression program. It's not done yet, but the code I have so far properly decompresses at least the first 12 bytes. (Woohoo.... really....)

So, it uses an adaptive variable bit length compression scheme that seems to be a mix between Huffman encoding and LZW encoding.

Basically, it treats the file like a bit stream with the most significant bit of each byte being used first. I guess, if you were to view the file as a bunch of hex bytes and then write it all out in binary, then extracting the next bit is like shifting the whole file left.

Anyways, here's what I've figured so far about about how the bitstream is interpreted. First, a Huffman tree is generated with 314 terminal nodes (I'm pretty sure anyways). The data values in the terminal nodes of the initial tree are a numerically increasing sequence of numbers starting at 0 and going to 313 as you move accross the bottom of the tree. (How this is all implemented is actually REALLY COOL! Anyways, more on that at a later time I guess)

Now, a search then starts at the root of the tree. The bits control which branch of the tree to follow. (i.e. 0 go left, 1 go right). When a terminal node is reached, the value in the node is used to determine what is output. As soon as the value is found, the Huffman tree is updated. I believe the tree is updated according to the standard algorithm for adaptive Huffman encoding, except that the tree is already fully generated from the start, and not generated as the values are read. I'm still checking into this but I'm sure it's at least VERY close.

Now, if the value read from the terminal node of the tree is <= 255 then it is taken as is (as an ASCII code) and output. If the value is >= 256 then it outputs a run of bytes that has previously been output. The length of the run is (value - 253). Note that this implies a run must be at least 3 bytes long. The starting location of the run (in a buffer of previously output bytes) is taken relative to the current location of output to the buffer. The next sequence of bits waiting to be read is used to determine how far back the match occured. Note that when a code >= 256 is read, at least 8 bits are then extracted from the bitstream for the offset to the starting location of the match. More than 8 bits can be read and as far as I've seen it always reads 9 bits (but this likely changes). After this, the algorithm goes back to searching the Huffman tree.

Note: As of this moment, I'm not exactly sure how the algorithm determines how many bits to extract to find the starting location of a match.

Note: My tree update I coded isn't yet fully functional so that's why I only get correct results to about 12 bytes. But before the tree update coded was added, this was only 6 bytes.

From what I've seen (using morale.txt):

When the algorithm starts, the first few characters output correspond to 9 bits of input. The second time a character is output, it corresponds to 8 bits of input(adaptive compression).

If you want to verify this on the first few bytes of the file, the update to the tree can be ignored for about the first 6 bytes output without messing things up. The tree lookup can then be approximated by subtracting. (Basically, read in a 9 bit integer and subtract 396.)

I traced through the decompression of about the first 650 bits and the output matched the .txt files from the demo, so I'm pretty sure this works. (Yes, it took a while). This was till about the end of "UTOPIA(tab)90". At this point, I got bored, decided it worked and stopped.

Hopefully in a few days I'll have some working code to decompress the files. (I sure hope nobody has figured this out already!  :blink:  )
 

[alice]

oh, wow... I've been trying to figure that out for a long time. (so have many other members)

When I get home, I'm gonna try this...

(I don't think anyone figured this out yet.  From what I know, we used a hex editor to figure out what does what....)

[Cynex]

Didn't know somebody else was about to figure it out.

I've found all this long ago and decrypted all the sheets (this is where I got the researches-list from).
However I just decided to not give it away since it could be used for cheating.

As I was informed by op2hacker, the game doesn't check for modified sheets, so if anybody cheats you probably won't be able to find out...

I'm also of the opinion that a part of the game goes lost, when one has the possibility to look at sheets just to figure out the fastest way to get a specific technology.

This is how I think about it.

Let me know your opinion.

[Hooman]

I had a feeling you had already figured it out. Did you actually get the whole decompression algorithm or did you just let the game do it and then dump the memory? (It would have been much easier but not as fun.) If you did figure it out, then I'm wondering what your thoughts are on the tree update algorithm. It appears to be a slight variant to me right now.

Anyways, I was planning on testing the possible consequences to multiplayer before releasing anything like the file contents or the code I was working on. I figured it would have been checksummed but I guess not. I was worried that an uncompressed version that matched exactly a compressed version would not allow people to play against each other. I never really thought you could get away with two different versions of the files.

Well, I find it a bit hard to just quit working on it now, but yeah I see your point about the tech tree. Chances are, I won't bother paying much attention to the specifics details of the file contents. I'm sure I'll lose interest shortly after figuring it out. I never play the game anymore and I've only ever played multiplayer like 2 or 3 times. I don't really expect to play anymore and if I did, it would probably be colony games. I find it more fun to figure out how the game works than to actually play it now. It seems to be that way with all games for me. I fear my game playing days are over, and yet I guess I'm kinda glad since it's really starting to strike me as a waste of time.    Mnid you, figuring them out still strikes me as educational.  (thumbsup)

And cheating in multiplayer is very wrong!

Doh! I just found a page cached in google. It seems op2hacker did the same sort of thing about a year ago to find what's going on in memory. Man, I feel like I'm always so behind! lol.  
 

[BlackBox]

Yeah, I tried to decode the routine but gave up after about 10 hrs of work because I couldn't find the part where the splitting up of the VOL contents (ie. finding a certain file in the VOL) and where it actually performs the decoding. I just remember I kept single stepping thru the code and noticed it was copying bytes into a buffer in OP2, holding the uncompressed/decoded sheets content.

However, very good work so far! Keep it up!

Btw, for everyone else that may be reading:
This does NOT mean we can add new units by simply changing the sheets. There are many variables that go into what makes a "unit":
1) the properties of the unit, stored in sheets.vol\VEHICLES.txt, sheets.vol\*TEK.txt (for the research to make the unit possible), etc.
2) the bitmaps for it, stored in OP2_ART.bmp, and information about these are in Maps.vol\OP2_ART.prt.
3) internal constants for it, hardcoded into Outpost2.exe.
4) symbolic ID for it (a member of the map_id enum) that is given by the .dll for the mission to make the game create an instance of the unit.

To add units, it would require tweaking of the entire game.

[Cynex]

Well, I was trying to understand the routine for a long time and figured out much.
However I was just too lazy to put more afford in it, so I stopped after the first try to create the initial tree-structure.

At the end I actually know nearly as much as you, but without the Huffman/LZW stuff.
(I know LZW, but never heard of special tree-structures.)

So I just worked out another way to let the game do the work for me
It's quite suitable, but I sense you prefer the hard way.

My view about gaming is actually that I don't play that much, too.
Finding out stuff is a better use of time
Nevertheless I don't want to distract anybody from playing, so this is why I'm that careful with things.

Consider that it is entirely possible to replace the old sheets with uncompressed new ones.

And you should really think about it.
Mysteries always keep things at life. Once they are gone, it could mean the end of the game.

[Hooman]

Well, thanks for the replies. They're certainly something to think about.

I think I've finally got my tree updating properly. I've figured out how to determine how many bits to read to find the start of a run but I haven't coded it yet. I can decompress about 5 lines before that becomes a problem.


As for what stuff in the .exe does, I can break it down (at least the major parts) by the starting address of the routine. (For the few who can understand this  (thumbsup) ). Actually, I better not. Op2hacker, if you want them, PM me.

00XXXXXX    Determines what to do with the codes read from the tree
00XXXXXX    Returns the next bit of input in EAX
00XXXXXX    Returns the next 8 bits of input encoded in a byte in EAX (used for reading the block starting addresses)
00XXXXXX    Returns the next encoded byte. The above two use CALL [EBP+1C]
00XXXXXX    Updates the Huffman Tree
00XXXXXX     Returns the next code decoded using the tree

This last routine is really cool. It uses a table to represent the tree. The siblings are always next to each other in the table. So by adding 0 or 1 to the index of the left child, you get either the left or right child. The first CALL (in the loop) gets the next bit which controls which branch to follow. You just add this bit to the index and reindex. So if EDI is the index of the current node then

Code: [Select]

ADD EAX, EDI
MOVSX EDI, WORD PTR DS:[ECX+EAX*2]

is used to traverse a branch of the tree. (ECX is of course the base of the table and EAX gets the value of the next bit.)

It's also interesting to note that a leaf node is determined by the value stored in the data/link part. So a value above 0x273 represents data and values below represent a link to another node. Hence the terminating condition for the loop. To get the data back, it then subtracts 0x273.

I just had to share that little bit. The coolness of it all was killing me B) . Extracting the bits from the stream is also somewhat interesting. Updating the tree is a small nightmare. Especially the parent indexes. It took me awhile to see what I was missing there.

Oh, and the number is bits used for the starting address of a block I believe is always at least 9 and can be up to 14 bits. It also has default values for certain bits once the length of a block gets long enough.

Anyways, back to work for me. Hmm, I probably wouldn't have gotten this done today if it wasn't for that freak snowstorm.  <_<

Edit: I've now got it properly working (mostly) for a few of the files. (mines, morale, space, vehicles) The only problem with those files is that the decompressor doesn't know how to detect the end of the files and so it spits out a bunch of garbage at the end. The *tek files I get almost nothing out of yet (except the leading comments and part of the first tech in multitek). I'll have to recheck my code for decompressing runs. The numbers are much too large and are causing problems. Meh. Time to take a break and go watch a movie.

Edit:
Looks like I've got them all decompressed properly now (except the garbage at the end, but that can just be deleted with notepad or something). I was forgetting to wrap my read pointer at 4096. Also, the buffer has to be initialized to spaces so that large values (or negative values that wrap around to large values) point to spaces and not just junk.

Hmm, it's kinda tempting to try writting a compression program sometime. Sometime being the key word here. I don't care to do it anytime soon.

Anyways, has anyone figured out how to put the decompressed files back into the .vol files. I've been using that ReVOLver program but the game just quits while loading up. I've tried editing the .vol file to change the 0x103 in the index record to 0x100 but that didn't work either. (I assume that's how it knows the files are compressed.)

[Hooman]

Well, I put my decompression program to the test. I've decompressed all the .txt files and rebuilt SHEETS.VOL from the uncompressed files. It looks like it's finally all working.

Using the newly built sheets.vol, you can freely extract and rebuild sheets.vol using the ReVOLver program. The .txt files are then just plain text are you are free to edit them.

Note: I am not currently releasing the new sheets.vol for the reasons mentioned in the above posts. I will look into the above reasons and see how much of a problem it might really be for potential cheaters.

Note: In the event that I do release the new sheets.vol (or that I forget this detail myself), you must rebuild with the new sheets.vol in the Outpost2 directory since the ReVOLver program does not modify the compression tag (it just seems to replace the end of the file and patches up the offsets). Obviously the compression tag must not be set for uncompressed files.


Say, anyone want to notify Allen McPheeters of changes?  :heh:  (thumbsup)
 

[Arklon]

If one player had a different sheets.vol, I assume (98% positive, the other 2% is milkfat-- er, uncertainty) the game would get out of sync between players with different sheets.vol files. Much like if one player edited the memory and turned a light tower kit (or any other kit, for that matter) into a basic lab kit (again, or any other kit), when built, it would be a basic lab to the player who built it, but a light tower to everyone else. (I've tested the basic lab thing.)

OP2 sends actions each player does through the multiplayer session. For construction, it begins with creating the kit. That kit will end up being the final structure, if and when built. If the kit is abruptly changed, OP2 will not send changed data to other players. Which is why if you changed a kit into another kit, it would appear as what it was before changed to other players, but what you changed it to to you.


Allen McPheeters... co-head of the OP2 project, I believe. I've seen that notice in the demo sheets.

[Hooman]

Well, I just tried mucking about with the sheets.vol file. It seems it IS checksummed. Also, if someone has an uncompressed version of sheets.vol they can't play against someone with the original sheets.vol due to the checksum. So never mind games going out of sync, you just can't start the game with a different sheets.vol file.

However, that still leaves the issue of having the tech tree plainly visible. It might ruin the game if people know exactly what techs to research. Hmm, maybe we should start a debate/poll on this.

I'm gong to check on that checksum thing a little more just to make sure I'm not wrong. Also, if it is possible to cheat or get around the checksum, there are likely more subtle and effective ways to cheat than suddenly changing a structure. Like changing the cost of a structure. It would still be the same building but the money might go out of sync (which you would probably never notice). Also, it might not work quite the same as changing a memory value since if you were then able to build a basic lab, it would always have been a basic lab and thus it might actually build properly.

Well, I'll go see what I can find out.
 

[BlackBox]

It's very easy to cheat the checksum. I did it in my no cd crack.

I would explain it here, but I'm not going to because of the chances that someone could use it to cheat.

(Hooman: if you want what I did, PM me. Also, is is possible that I could have a look at your code / the uncompressed sheets? I'm wondering how you did it.)

Arklon: There is no way in the sheets that you can change the actual definition of the structure, for example from a light tower to a basic lab. The stuff that controls the graphics for the structure, and how the structure functions, is contained in the EXE. The sheets only contain costs, hit points, production amounts, armor, research topics, etc.

[Arklon]

op2hacker: I didn't say change light tower to basic lab in the sheets. I meant in OP2's memory (changing a stored light tower kit into a basic lab kit with a memory editor).

[Hooman]

Yes.... I was purposefully neglecting to talk about cheating the checksum so as not to give people any ideas. I was planning to try to break that just to see how easy it would be. (My initial over simplified attemp failed.  :whistle: )

I would like to see the details of how you get around that sort of thing. As for my code, I'll send it to you but I'd like to clean it up first. It's a real mess right now. It was kinda going OO since I was using C++ but I was also trying to follow the assembly closely so as not to miss anything. You can probably guess what the results were like.  (thumbsdown)

I guess I can send you the uncompressed sheets for now. (In the VOL files to make it easy, particularily for rebuilding.)

 

[Hooman]

OK, when starting a multiplayer game, I saw the following files being checksummed:
the .txt files in sheets.vol (compressed/uncompressed will change the checksum)
Outpost2.exe
OP2Shell.dll
the .dll file for the level
the .map file for the level

Bad news: The checksum is really easy to get around. I found the routine (which was really easy), it's only about half a page of assembly and it was really straight forward to understand. Ever worse, it's really easy to modify different files to have the same checksum.

I tried an example where I changed the price of an agridome to 100 common ore instread of 600. Multiplayer connect fine and the game was none the wiser. I built a few agridomes and I tried scouting how much ore the other players had. They both calculated the money based on what they thought the agridomes should cost so the amount of money each player had was out of sync. After a while, when I placed buildings which I normally wouldn't have had the money for, they would only appear in the game with the cheaper agridomes. Same with the units I built, only I actually managed to build a scout in the other game that the game with the cheaper agridomes couldn't detect. I was able to scout the other base without my scout being seen. Self destructing the scout also caused out of sync damage.

Anyways, it appears the game just sends the commands accross and each computer handles the commands according to it's own set of rules. In a sense, this sorta defeats the purpose of cheating since the other person won't be seeing or playing the same game as you. Thus even if it looks like you're beating them, they might still think they are beating you. It also caused the game to crash eventually.

I guess this could still be used for some sort of cheating without throwing the games out of sync, but not in any way I can think of that involves the vol files. The only thing I can think of that would work is cheating to get information. Anyone else have any thoughts on this?

Oh, and I'm currently working on a reVOLver like program that can handle the compressed files and possibly even extract the files in OP2.clm to .wav files instead of .raw files. (Incase anyone else was thinking of doing it, it's already being done.) I also suspect that the wave format in the .clm file can be changed (but must be the same for all files in it). Just don't expect it for a little while since I go back to school tomorrow and I'll be a little busy.

Hey, and op2hacker, about that vol file I sent you.... I'm thinking I should try modifying the internal files so their checksums match the original. Think it's a good idea? Then you can play multi with the uncompressed files and since the data is really the same, the game shouldn't go out of sync. I'm not sure exactly how cleanly this can be done right now, but at the very worst, there would be a few bytes of garbage at the end.
 

[BlackBox]

I could show you my checksum modify code. (Btw.. could I see what solution you had to hack the checksum?)

It's not even a half page of assembly to change the checksum, it's 3 lines of assembly. Mine is about the simplest you can get.

Btw: Converting the raw files to wave files should be very very straightforward. They're already in PCM format so all you have to do is slap a RIFF WAVE header on with the correct bytes set and you're done.

 

[Hooman]

I know converting the RAW files to WAV files is easy.  B) That's why I was thinking of doing it.  B)  It just seemed like an added convienence if I was going to bother with a VOL unpacker/repacker. Besides, if I ever release a program to decompress the vol files, I figured it might as well be a complete replacement for the ReVOLver program so people don't have to keep two programs floating around and switch between them.

Oh, and I didn't change the checksum code. I changed the files so that their checksum matched any value I wanted. I didn't need to modify the exe. Besides, the same code is used to calculate the checksum for all the files above so I didn't see a simple 3 line solution that would return the right checksum for all the files. (Oh, and I think you only need 2 lines of assembly to cheat the exe checksum you mentioned earlier. One of the lines wasn't needed.) As for calculating how to modify a file to match a given checksum, it's also 2 lines of assembly, provided you already know the checksum.
 

[Hooman]

Well, I continue to have no time to work on my program, but I took some time today to repack a sheets.vol file with uncompressed data so that the checksum matches the original compressed file.

This means:
1) The new sheets.vol can be used to replace the old one and there should be no trouble connecting in multiplayer. (At least no problems in my test).
2) The new sheets.vol file can be unpacked with the usual ReVOLver utility. So...
3) People can edit the files in sheets.vol and play with the new rules. (Either repack the sheets.vol files or copy the .txt files into the outpost2 directory)
4) If someone modifies the new vol file, or the .txt files, the difference in the checksum will prevent them from connecting to a multiplayer game (unless the other person is using the same modified files).
5) If someone finds a way to defeat the checksum algorithm, (like how I packed the file) then any differences with the original will cause multiplayer games to go out of sync. So modifying the .txt files should not allow anyone to gain an unfair advantage (just screw up the game so noone really knows what the other person is doing).
6) People will be able to see how the game works (and adjust their playing strategy). Of course things like the tech tree are already listed in the .doc files that get installed when the game does. However, units stats like speed and weapon range will now be revealed.

I'm gonig to hold off on releasing the file since some people have expressed certain concerns about it. I would however like an idea as to what people think about releasing the new file.

[RedXIII]

I really do not see the problem, its already easy to cheat in multi games without going through such pains as to modify the files. Plus, as you said, if the files are different it will just desync and crash eventually.

[Kramy]

I don't see a problem either. On a somewhat related note, you've never bothered to measure weapon fire ranges or fire times!?

[Hooman]

On a somewhat related note, you've never bothered to measure weapon fire ranges or fire times!?

Err, umm, no.

Actually I don't often play the game anymore. Most of the time I spend on it, I spend programming stuff for it.

Anyways, its looking like I'll release the stuff but I just want to make sure there's nothing I've overlooked. Once it's released, there's nothing I can do to "unrelease" it.

Any last comments?
 

[Hooman]

The uncompressed sheets.vol is now posted in the file forums. Get it here:

http://forum.outpostuniverse.net/index.php?showtopic=993...indpost&p=21347

[Arklon]

I also messed around with the beta sheets and the full game. It's very odd... they seem to work correctly with the full game. Well, except for the wreakage gathering on the postrelease demo.

[Tellaris]

Measureing weapon ranges isn't really all that important.   All you need to know is that microwave=shortrange, RPG/Sticky are same range, and EMP may be 1 more then that, I'm not sure.
Thor outranges ESG by 1 square, thats good enough for me.

[Mez]

then you have the research upgrades to increase the distance.

[Eddy-B]

You guys are replying to a post, made almost a year ago, by a person that hasn't been on the forum for like 6 months ?
This forum is starting to die out.. :lol:  we need to live it up a little, guys!