Optimizing the game's Huffman (de)compression code

[Caball009]

What does this PR do?

1. This pr adds a more optimized version of the game's huffman functions for (de)compression of data, particularly the compression. The game mainly uses huffman coding to compress game data on the server side and to decompress it on the client side.
2. If so desired, but not currently implemented, this may be a better way to fix the exploit issues related to huffman decompression. It's certainly a more efficient way than using a static buffer and copying the data if there are no buffer overruns as is currently done in the 'Security' namespace. https://github.com/iw4x/iw4x-client/blob/develop/src/Components/Modules/Security.cpp#L6-L30

How does this PR change IW4x's behaviour? This pr should not change existing behavior in any way.

Anything else we should know?

1. There's currently a potential for OOB read for decompression in the game's huffman code. The maximum number of OOB bytes is 2 bytes. The main reason to fix this would probably be correctness and to be compliant with sanitizers, not necessarily security. This is currently not fixed in this pr, but can be if so desired.
2. The game's functions 'MSG_ReadBitsCompress' and 'MSG_WriteBitsCompress' are currently not hooked and replaced with the functions in this pr. I'd like to get some feedback before proceeding to do so. That would also mean the game's huffman initialization can be skipped, although this only costs a couple of ms in my experience.
3. If the 'IterateTree' function is not inlined by the compiler, it'd probably be better to make it a part of the 'Decompress' function if optimization is the goal.

Did you check all the boxes?

• [x] Focus on a single fix or feature; remove any unrelated formatting or code changes
• [x] Mention any related issues (put closes #XXXX in comment to auto-close issue when PR is merged)
• [x] Follow our coding conventions
• [x] Minimize the number of commits

[Caball009]

@Rackover (you told me to ping you).

[Rackover]

Thanks for pinging me, I'm not good enough with Huffman to assert of the quality of this implementation, however I see that you did similar work before and I trust that you know what you're doing.

I think I would like to "test" the function by side-by-side executing Game::MSG_ReadBitsCompress and yours (and same for write) and asserting that the outputs are 100% identical. This way even if I don't fully understand it I can at least ensure this will have no undesirable side effects. Maybe you could include a test function in there that does something like that when iw4x is launched with a -test-huffman flag.

Here are some project specific notes:

• Utils::Huffman::detail should probably be its own file, maybe a header file, so that it doesn't cramp up the Utils::Huffman source file (currently you have to scroll to infinity before you can access any code).
• And then to implement the huffman into the game you would probablby want to create a Component called Huffman or something similar, that does the hooking work of plugging it into MSG_ReadbitsCompress/MSG_WriteBittsCompress. If you need directions or offsets I can look into it and provide them for you :)
• This will also allow the patch to be turned on or off easily from Loader.cpp, should there be any issue.

[Caball009]

I've set up a couple of (unfinished) unit tests as part of the new huffman component. Would you still like to have a test flag as well, or is it enough to have a unit test?

I'd like to use unit test 2 to compare the output from the old and new huffman code side by side for compression and decompression. I could use some help with the function stubs, though. I'm not sure if we need them, though currently the new huffman code functions expect a size for the output buffer as well, and the game doesn't provide this so that'll need to be sorted out.

I would also need a way to call the original huffman functions, but I'm not sure if that's possible after installing the hooks.

[Rackover]

Looks better! We have not ran any unit tests on IW4x for a while so I don't know if they even pass, but it's indeed a better idea to add this one to the tests - rather than having a single test flag - if they do. I'm gonna look into your hookings and stuff whenever I can, possibly this weekend. thanks again :)

[Caball009]

Sounds good, thank you. Feel free to reach out on Discord if you need anything quickly, though I'll try to keep an eye on this draft.

[Caball009]

@Rackover Is there any chance you can have a look at it this weekend? I'd like to write the other unit tests and finish this draft.

[Rackover]

Hello, sorry I was not sure this was up for review yet. This week end is a bit complicated for me, I can try looking at it monday night if I don't forget :)
Don't worry about pinging me if you feel like I'm not answering in reasonabble delays

[Caball009]

@Rackover Could you check the new changes, and check if the code works as intended?

https://github.com/iw4x/iw4x-client/pull/111/commits/8efe997cea458cc9488518b0eccd14c7426740b0 removes the huffman exploit fixes, but maybe that's a bit premature, so I'm just making sure that's not overlooked. It might be nice if it were enabled as a fallback option when the huffman component isn't active, so that there isn't a scenario where the exploits are unpatched.

[Caball009]

I have verified that the new huffman implementation is internally consistent; that is, uncompressed -> compressed -> decompressed yields the same data. The two parts that I haven't verified are the game hooks and the part of unit test 1 that compares the results from the two different huffman implementations.

[Caball009]

Updated with the requested changes.

4c0933f currently triggers a linker error that I haven't been able to figure out yet. Is it possible that the Utils::Huffman and Components::Huffman files / namespaces are clashing?

[Rackover]

Yes maybe, in that case you can just explicitely specify Components::Huffman when adding it to the loader if you want :)

[Caball009]

I already tried that, but it makes no difference.

[Caball009]

The linker error can be avoided by renaming either the Huffman utility files or the component files btw. If that's the way to solve this, which one should have a different name and what name would that be?

@Rackover Could you check the comments? I don't really like the explicit buffer checks up front, so imo I should get rid of the std::spans and just use the buffers and buffer sizes directly.

[Rackover]

So the good thing is that apparently github CI has no problem with your code currently cause it builds & links correctly. I have not tested it myself yet though, and I have not checked the comment yet. Next week I plan to work a little bit on IW4x and catch up on stuff, so I will be looking at your PR, testing it, and hopefully merging it, and releasing :)

Regarding the discussion of span vs ptr+size_t, I'm not a c++ expert and have never used spans, so I don't know. My opinion is that if a size check is to occur it should occur on debug AND release, so assertions is not protection enough for it 🙂

[Caball009]

Even though Github managed to get it working, I cannot get the MSVC linker to do the same thing. So just a heads up, if you ran into the same problem, renaming one set of files (module components or utils) should do the trick.

As for the 'std::span' comments, https://github.com/iw4x/iw4x-client/pull/111/commits/45e8f5489e8a5863c05a290d022427a5c6f33506 is how that could look like (the size checks are now part of the for loop conditions, so they're always checked). As far as I can tell (without having tested the game specific parts), the pr is good to go as-is.

[Rackover]

^2Huffman decompression out-of-bounds read detected!
^2Huffman decompression out-of-bounds read detected!
0% config string match, 0% config string coverage.

Cannot join a single server with your modification! (I tried three different servers) It is currently not functional, I tested it in debug only but it does not seem to work with existing servers. Could you please install IW4x and test your code too? This way you can probably find out what's wrong more easily than with my descriptions 🙂

Regarding your linker error: maybe you forgot to run Generate.bat after adding a new file! You need to do it to regenerate the solution. I did it on my end and it worked, and this is what Github CI does too.

[Caball009]

You're right, I didn't think to re-generate; that fixes it on my end as well. Thank you for that and thanks for testing.

The OOB detection messages are probably expected in debug mode. Just for reference, the game performs 'limited' OOB reads for many, if not most, decompression operations.

What's the meaning of the 3rd logged line, and did you check whether the unit tests and hooks were successful? I'm going to check what's required for me test IW4X live btw.

[Rackover]

Hello! I'm available on discord if you need help getting IW4x live. I'm back to work (somewhat) actively on IW4x so I should be able to help you out within reasonable delays if you need anything.

[Caball009]

Sounds good. I'll probably contact you at some point on Discord.

FWIW, I haven't given up on this pr, but it'll take me some additional time before I get around to installing IW4X and do live testing.

[Caball009]

It's been a while since my last commit, so has there been any progress?

[Rackover]

Hello! I'm still there, have you managed to set up IW4x to test your pull request on your end? :) I'm here on discord too if you need help with that. The setup for IW4x is pretty painless so if you can do that and test your PR on live servers to make sure everything works, it's very helpful. If everything runs as it should I will happily merge this in master and draft a new release! 😃

[Caball009]

Hello! I'm still there, have you managed to set up IW4x to test your pull request on your end? :) I'm here on discord too if you need help with that. The setup for IW4x is pretty painless so if you can do that and test your PR on live servers to make sure everything works, it's very helpful. If everything runs as it should I will happily merge this in master and draft a new release! 😃

I already did that about two months ago after I fixed some issues with the (de)compression. It worked then and it still works now on my end. So it's ready for you to test.

[mxve]

I can't comment on code quality and usefulness of this PR, but I did some quick testing. The game seems to run absolutely fine, I was able to:

• Connect to public servers
• Host a server without and with a mod loaded (botwarfare) & connect to it
• Play private match

[Rackover]

The game had no issue in Release but testing in debug mode, on a custom map, reveals this issue. Investigating

[Caball009]

We already discussed this privately, but I'll put it here as well for posterity.

The game doesn't have these early break checks for its (de)compression functions, so every time you see these debug prints, it's simply showing that the game would've accessed data beyond the size of the buffer. In other words, the print statements are a reflection of the game's implementation and not of this code, and can be removed if so desired.

If you run unit test 3 and step through it, you should be able to see precisely what's going on here.