OP2Archive Application Development

[Vagabond]

I spent some time on OP2Archive recently.

Now when you attempt to upload a filename that contains a non ASCII character (above decimal 127), an error is thrown and displayed to the user. This is to protect Outpost 2's alphabetical sorting algorithm for archive files that does not include support for things like characters with accents.

I'm using the function below to check if a non ASCII character is present. I'm not thrilled with the solution. Since characters above 127 come back as a negative number, I'm checking both below 0 and above 127. I'm wondering if there are holes to approaching the problem this way. If anyone has any suggestions, I would be will to implement them instead. Since the sort is isolated in this function, it will be easy to change out in the future if bugs are discovered:

Code: [Select]

#include <algorithm>

bool StringHelper::ContainsNonAsciiChars(string str)
{
	return std::any_of(str.begin(), str.end(), [](char i) { return (i < 0 || i > 127); });
}

I also opened a new branch on OP2Utility. It separates each class inside Archive into a discrete file of source code. Previously, we had ArchiveUnpacker, ArchivePacker, MemoryMappedFile, and ArchvieFile all defined in the same .h/.cpp file. I found this pretty confusing. I opened the branch so that Hooman could review my changes to his code before affecting the master.

Plan going forward:

• Update the Archive function below to not take an internalNames variable. Instead, produce the internal names from the filesToPack variable organically.

Code: [Select]

virtual bool CreateVolume(const char *volumeFileName, int numFilesToPack, const char **filesToPack, const char **internalNames) = 0;

• Move code to alphabetically sort the list of files to pack into the Archive code. (Currently, anyone wanting to create an archive must manually sort their filenames).
• Move code to check for non-approved characters in filenames into the archive code. (Same reason as above)
• Push another release of OP2Archive.

I'm planning to implement these functions using modern C++ practices within the Archive code. I've already been sprinkling in things like std:unique_ptr into the Archive code. Hooman, if this bothers you, please let me know and I'll stop. I'll do all this work in a separate branch for merging once everyone is happy with it.

Thanks,
Brett

[leeor_net]

...

I'm using the function below to check if a non ASCII character is present. I'm not thrilled with the solution. Since characters above 127 come back as a negative number, I'm checking both below 0 and above 127. I'm wondering if there are holes to approaching the problem this way. If anyone has any suggestions, I would be will to implement them instead.

...

Use an unsigned char instead. Ascii characters aren't defined in negatives so it's odd to look at values less than zero.

Code: [Select]

/* Note explicit cast, quiets static code analyzers */
return std::any_of(str.begin(), str.end(), [](unsigned char i) { return (static_cast<unsigned short>(i) > 127); });

[Hooman]

Yeah, C++ standard doesn't specify if char is signed or unsigned. It's compiler dependent. If you want to ensure it's unsigned, then specify unsigned.


I'll try to take a look at the new branch over the next couple of days. Though I am generally in favor of the changes you're proposing.


One question though, are the high ASCII values actually causing demonstrable problems? I don't believe the game tries to treat high ASCII values in any kind of special way, so I would assume ignoring them would produce the most consistent results. Is this perhaps an encoding issue, where some method assumes an unexpected (non-ASCII) encoding?

[Vagabond]

Use an unsigned char instead. Ascii characters aren't defined in negatives so it's odd to look at values less than zero.

Thanks Leeor. I went ahead an updated my function as suggested. I used this opportunity to try out the git cherry-pick command to push it to both branches.

One question though, are the high ASCII values actually causing demonstrable problems? I don't believe the game tries to treat high ASCII values in any kind of special way, so I would assume ignoring them would produce the most consistent results. Is this perhaps an encoding issue, where some method assumes an unexpected (non-ASCII) encoding?

Hooman, to be more clear on what is going on:

1. The alphabetical sort command I created for the filenames is sorting ASCII characters above decimal 127 incorrectly. So Windows Explorer will sort them differently than my sort alogrithim.

2. Based on your comment below from the OP2Archive release thread, I feel like it would allow for undefined behavior in Outpost 2 if these characters are used in filenames. Especially since I am not verifying my sort algorithm exactly matches the one used by Outpost2.exe.

From my brief debugging session, it didn't look like Outpost 2 tried to do anything special with accented characters. The code path that was actually used only took special consideration for the 26 uppercase characters.

I don't want to expend effort testing Outpost 2's internal binary sort to see if it fails or not for the edge case of someone using a character like an accented e, so I figured blocking the behavior and providing the user an error message was a better idea than allowing possible undefined behavior.

I'm itching to get started on this, so soon I'd like to merge the branch that separated out the classes into discrete files and create the development branch for the actual changes.

-Brett

[Hooman]

1. The alphabetical sort command I created for the filenames is sorting ASCII characters above decimal 127 incorrectly. So Windows Explorer will sort them differently than my sort algorithm.

I wouldn't call that incorrect. There are many different types of sorts, with different purposes. Sort rules can get quite complex, but without a reason for extra rules, it just slows the sort down with no real gain. The purpose of the sort was to implement a binary search for efficiency purposes, not to sort in a nice order that would appeal to people. It's done purely for machine processing reasons, with no user visible display of the sort order.

2. Based on your comment below from the OP2Archive release thread, I feel like it would allow for undefined behavior in Outpost 2 if these characters are used in filenames. Especially since I am not verifying my sort algorithm exactly matches the one used by Outpost2.exe.

You may have a point here about undefined behaviour. However, by making it check for high ASCII characters, you're making the algorithm diverge from the Outpost 2 algorithm, which chose to ignore that aspect. As this is a machine processing step, it's probably wise to have it match as close as possible.

Since it is unusual to use high ASCII characters, and encoding considerations were likely not accounted for, it may make sense to warn the user of a potential problem, though I really feel this should be a warning rather than an error. Besides, how can someone test the behaviour of Outpost 2's algorithm if you program refuses to create the test data. 

[Hooman]

Ok, I've had a chance to look at your branch that splits classes into separate files. Looks fine. You basically did the obvious thing.

One suggestion I have is to squash the 3 main commits into 1 commit. The 2 minor commits look like bug fixes for the larger commit, and hence the larger commit seems to be broken. By squashing, you reduce the noise, and ensure all commits (the 1 remaining commit in this case) works.

You can look up "interactive rebase" in the Git documentation to figure out how to squash commits. This falls into the realm of rewriting history. Whenever possible, it's good to do this before pushing to the central repo.

Side note: This is also why pushing after every commit is considered an anti-pattern in Git, since you inevitably catch these mistakes sometime after making the commit. By delaying the push, you give yourself a chance to find and fix these errors before publishing the results.

At any rate, things are already pushed to a branch in the public repo. There are two choices at this point. You can squash, and then do a force push (very Darth Vader like), to update the branch on the central repo. This can be a nuisance for other people that have downloaded that branch. Don't worry, I'm sure I can deal with it. Plus the branch gets deleted after merging into master, so meh. The other option, is to do the squash, and merge into master locally, and push the changes on master. The branch can then be deleted without ever having been updated in the central repo, no force push required (sorry my young apprentice).


I noticed you added the sort update to this branch. Is that the part that was making you itch? 

The sort commit isn't really related. It would be better on a different branch. Though I do understand the temptation, as keeping work linear is easier, and you often have changes that depend on other pending changes. In this case, you could have created another branch off of master. If the changes were more dependent on the branch changes, you can create a branch off another branch.

At any rate, if all changes are merged into master using a fast-forward merge, you won't be able to tell where the branches were merged in, or how many, so it won't really matter. That's the case I expect here. If the merge requires a merge commit (a commit with more than 1 parent), then it's a little more obvious, and may stand out as strange to have both changes come from the same branch.


For code review, using a GitHub pull request may be a good option. It's fine to open a pull request from different branches in the same repository. That's a fairly standard way to start a code review. People can then review the changes right from the browser, with color coded diffs, and comments. They also have handy buttons for performing the merge should the code pass review, and to delete the branch after the merge is done.

If you want to give it a try, you can do so now, or after attempting the squash. Totally optional though.

[Vagabond]

Since it is unusual to use high ASCII characters, and encoding considerations were likely not accounted for, it may make sense to warn the user of a potential problem, though I really feel this should be a warning rather than an error. Besides, how can someone test the behaviour of Outpost 2's algorithm if you program refuses to create the test data.

Hooman, since you don't agree with aborting the operation in this case, I'll drop integrating this feature into OP2Utility's Archive library code. It will remain in the OP2Archive as it currently exists. Feel free to update OP2Archve to display a warning instead of aborting if you wish.

I researched and used TortoiseGit to perform both the interactive rebase and the force push. First time using --force, but it appears everything worked out right. Not sure how rewriting the public history will affect your copy of the repository. Thanks for the quick tutorial on how to accomplish it.

The sort commit isn't really related. It would be better on a different branch. Though I do understand the temptation, as keeping work linear is easier, and you often have changes that depend on other pending changes. In this case, you could have created another branch off of master. If the changes were more dependent on the branch changes, you can create a branch off another branch.

I think you are talking about the commit Fix function StringHelper::ContainsNonAsciiChars(std::string str) to use only unsigned chars. I made this commit to the master and then pushed it also to the branch in an effort to keep both branches as closely aligned as possbile.

However, now that I merged the branch, the commit Fix function StringHelper::ContainsNonAsciiChars(std::string str) to use only unsigned chars is listed twice which isn't desirable.


Hooman, how do you feel about changing this function:

Code: [Select]

virtual bool CreateVolume(const char *volumeFileName, int numFilesToPack, const char **filesToPack, const char **internalNames) = 0;

instead to read:

Code: [Select]

virtual bool CreateVolume(std::string volumeFileName, std::vector<std::string> filesToPack) = 0;

I think we both agree on removing const char** internalNames and generating these internal to the OP2Utility Archives code.

Changing filesToPack from const char** to std::vector<std::string> removes the need to pass the int numFilesToPack. I'm working with vectors on my side and it doesn't make sense to me to convert them into a char** if I don't have to. Perhaps I'm missing something though.

Thanks,
Brett

[Hooman]

However, now that I merged the branch, the commit Fix function StringHelper::ContainsNonAsciiChars(std::string str) to use only unsigned chars is listed twice which isn't desirable.

Yeah, it's probably not worthwhile to cherry pick a commit between branches that will be merged together. I think cherry pick is more for maintenance branches of old releases. You wouldn't merge new features into an old branch, but a bug fix might appear on both branches.


Side note, you have a static_cast<unsigned short>, which I don't think is needed. I assume that got added during bug hunting/fixing?


The API change is good. The newer C++ features should make it simpler and less error prone to use. Dropping the extra set of file names is a good simplification, especially for default API usage. Ideally, that's all people should have to deal with. There is some slight loss of functionality, in that files can't be renamed as they are packed, but honestly, why would that be done, and how on earth would a user interface support it? I'm fine with losing that ability. The simplification seems like a bigger win.

[leeor_net]

I'm seeing some pass by value's using std::string -- these should instead be pass by reference to const.

[Hooman]

I'm seeing some pass by value's using std::string -- these should instead be pass by reference to const.

Maybe. Maybe not.

Are the Days of Passing Const Std::String as a Parameter Over?

The answer may depend on the specifics of the function.

[Vagabond]

Leeor,

My intent is to provide the archive code with a copy of the string and vector to do with what they please without modifying the values kept by OP2Archive. So I think in C++11 or newer the best way to achieve this is as stated: I have no real idea what I'm trying to say here, it just seems to be the right way to do it based on some research online. The whole topic of how to pass arguments in C++ is really confusing to me. 

Code: [Select]

virtual bool CreateVolume(std::string volumeFileName, std::vector<std::string> filesToPack) = 0;

Hooman,

Check Leeor's 4 APR post in this thread. I added the static_cast based on his recommendation.

Plan to start working a new branch starting today to make these changes.

Thanks,
-Brett

[Vagabond]

Okay, I just created a new branch and pull request for OP2Utility.

I updated:

Code: [Select]

virtual bool CreateVolume(const char *volumeFileName, int numFilesToPack, const char **filesToPack, const char **internalNames) = 0;

to read:

Code: [Select]

virtual bool CreateVolume(std::string volumeFileName, std::vector<std::string> filesToPack, std::vector<std::string> internalNames) = 0;

I stopped here because this created a lot of changes in the source code and I didn't want the branch to become too big to review. Once this branch is merged, I'll create a new branch to remove internalNames from CreateVolume.

I tested the code in this branch by creating a new .vol and .clm file. Both packed successfully. I even tested the clm file in game and it worked.

Commit Message
* Update ArchivePacker::CreateVolume() to use std::string and std::vector in input arguments

 - Update VolFile.h/.cpp to use size_t to represent the number of files in archive instead of using int.
 - Store filesToPack and internalNames as std::vector<std::string> instead of char**.
 - Remove destruction subroutines where char** was replaced with std::vector<std::string>.

Pull Request URL: https://github.com/OutpostUniverse/OP2Utility/pull/9

I requested review from Hooman, but don't have any issues with others reviewing/commenting on it as well through GitHub.

Thanks,
Brett

[leeor_net]

To readress my statement of passing by reference to const, you _still_ should do that. What you're doing now is passing a std::string by value. This means that you're invoking a constructor and a destructor when you don't actually need to. By passing by reference to const (e.g., const std::string& volumeFileName), you avoid the cost of the construction and destruction of a copy of the object. Instead, you are passing by reference. Since the function doesn't appear to be changing the string at all and it appears it's used once in the function CreateFileA, passing by reference to const is the most efficient way to do this.

Likewise, the second and third arguments:

Code: [Select]

std::vector<std::string> filesToPack, std::vector<std::string> internalNames

should also be either references or references to const. E.g.:

Code: [Select]

const std::vector<std::string>& filesToPack, const std::vector<std::string>& internalNames

Basically, your function prototype should look like this:

Code: [Select]

bool ClmFile::CreateVolume(const std::string& volumeFileName, const std::vector<std::string>& filesToPack, const std::vector<std::string>& internalNames)

Again, the function appears to call const member functions of std::vector... that being the case, by passing by value as you are, you're creating copies of each std::vector which invokes a constructor for the vector and a constructor for each item in the vector. For small file counts this is trivial but if you are doing any processing on any less than trivial count of files and internal names, you're potentially copying hundreds to thousands of objects. As you can imagine this gets very slow very fast.

This is in direct opposition to languages like Visual Basic, Java and C# where passing by value is as fast or faster (basically it's handled internally as pointers but you as the user don't see that).

Pass by reference to const whenever and wherever possible. If you don't actually need a copy of an object, don't make said copy. By changing the arguments to reference to const, you won't need to make an changes to the function itself unless you're calling non-const member functions but from a quick skim of the function it doesn't look like you're doing that.


As a semi-related side note, some really good compilers can see these kinds of things and will probably optimize that sort of needless copying, allocation and deallocation on its own but you can't count on that.

As another semi-related side note mostly regarding your post about C, in the case of C you'd be passing arguments via pointers and const pointers... e.g., const char* _string, etc.

[Hooman]

Those changes were a bit extensive. They look fine though. Code appears much more modern. Looked a bit like more modernization could be done too.


After reviewing, there is one tangentially related note that I'd like to bring up for possible future review. It's not related to the code changes, or at least the code changes don't impact this aspect of the code:

The size of size_t (and the size of int) is dependent on the target platform. The use of size_t is appropriate here for in memory handling of data. It would not be appropriate for the structures serialized to disk, as the file format should remain platform independent. It may be worth revisiting this possible discrepancy in future edits. There may be corner cases for 64-bit builds, such as the in memory structures being too large to fit the structures saved to disk. This is extremely unlikely to be an issue in practice. The other side is, a 64-bit build might try to enlarge the disk structure sizes, making it unable to work with existing files.


The recommendation was to use unsigned char, however the cast is for unsigned short.


Leeor, with C++11 there are now move semantics, which complicate the issue. This already eliminates a lot of copying. I believe the const reference prevents use of the new move semantics. It may actually be less efficient in some cases to pass by const reference. Further, newer compilers mandate the use of move semantics in some circumstances, which seems to negate concerns over some compilers implementing or not implementing a certain optimization. It is actually a complicated muddy issue. I'm afraid I can't offer a recommendation here without doing further reading.

[Vagabond]

Looked a bit like more modernization could be done too.

Thanks for reviewing so quickly Hooman. I just merged the pull request back into the master. Now that the bulk of the changes were made to pass the filenames in via vector<string>, the other changes should be a lot smaller in scope. I am trying to move the code to C++11 standards that I touch making the changes.

The size of size_t (and the size of int) is dependent on the target platform. The use of size_t is appropriate here for in memory handling of data. It would not be appropriate for the structures serialized to disk, as the file format should remain platform independent. It may be worth revisiting this possible discrepancy in future edits. There may be corner cases for 64-bit builds, such as the in memory structures being too large to fit the structures saved to disk. This is extremely unlikely to be an issue in practice. The other side is, a 64-bit build might try to enlarge the disk structure sizes, making it unable to work with existing files.

I think I basically understand what you are saying, but it is beyond my scope of knowledge to try to fix.

I pushed a second commit to the repository cleaning StringHelper. I fixed the typo in the static_cast and deleted 2 helper functions I was using to transfer vector<string> into char** and vice versa as they are no longer needed. These functions are not needed anymore since we removed the char** calls.

It is actually a complicated muddy issue. I'm afraid I can't offer a recommendation here without doing further reading.

I agree with this. My thoughts are:

1. It is complicated to determine the exact most efficient way to pass arguments in C++ when you consider move semantics.
2. The code is cleaner not peppering it everywhere with const &.
3. The code base has not expressed any performance issues. Until performance issues are noted, it is better to go with the cleaner syntax and let the compiler figure the performance details out on its own.

I've basically finished the next branch, but will wait a bit to push as I need to test a couple of archive packs first.

-Brett

[leeor_net]

...
2. The code is cleaner not peppering it everywhere with const &.
...

I disagree. Partially because I'm used to it, but in a lot of ways because it makes way more sense to me. Move semantics in C++ are a relatively new thing and as stated, muddy's the waters. That muddiness is something I as a developer don't appreciate so I tend to stick with what I know... Plus I imagine even with said move semantics compiler developers wouldn't strip out optimizations regarding references.

But that's just my humble opinion.

[Vagabond]

I pushed another branch and associated merge request for removing the argument internalNames from ArchivePacker::CreateVolume. ArchivePacker now also checks if 2 filenames (not including paths) are the same in the provided fileToPack and throws an exception if found. I had implemented this in OP2Archive, but believe it belongs on the OP2Utility side.

The following tests were completed:

1. Packing a new CLM file and testing in game.
2. Packing a new vol file.
3. Attempting to pack a vol file with 2 files with the same name. Operation properly aborted by new code.


I also recommended merging the branch turning XFile into a namespace instead of a Utility class. After Hooman pushes this merge, I'll test against modified versions of OP2Archive and OP2MapImager.

Once we stabilize development of OP2Utility, I'll push versions of OP2Archive and OP2MapImager that use the newest version of OP2Utility.

Thanks,
Brett

[Hooman]

Plus I imagine even with said move semantics compiler developers wouldn't strip out optimizations regarding references.

Yes, you're right, there is of course no reason to remove old optimizations, but that's kind of missing the point. There are certain cases where the old way of doing things couldn't be optimized, which can be optimized with move semantics. Consider the case of copying and holding a string into an internal data buffer. You might still declare such a parameter as const &, as the original, doesn't need to be modified by the called function. It might however be modified or deallocated later by the caller, hence a copy is stored rather than a reference to the original. But if the input parameter was a temporary, you can avoid the copy by simply taking ownership of the string buffer. This is where move semantics help. The compiler knows to call either the copy operator or the move operator based on whether the source object is a variable (lvalue), or a temporary (rvalue). The optimization goes beyond just the point of the call, taking into account the lifetimes of the objects.

There are also some convenience and syntax benefits, such as passing literals that have no associate memory address. Declaring a parameter as const & requires the parameter to have a memory address. That doesn't work so well for literals, such as 5. If you've ever found yourself declaring a variable just to pass a constant into a function, you know how annoying this is.

That muddiness is something I as a developer don't appreciate

Heh, I tend to agree. I'm not a fan when languages have multiple syntax options for the same thing. I've noticed Ruby violated that principle a few times to ill effect. I'm also rather against aliases to account for different spellings in different regions, such as US versus UK spellings of function names. I would prefer there only being one correct way.


Vagabond, I've merged the branch.

I'm thinking about the workflow right now. In the future, it probably makes sense for you as the project owner to do the merge, and was probably silly of me to request your review after opening the pull request. I think requesting review is more suitable when there is no main project owner, or when the project owner wants code reviewed by someone else. For a lot of single author projects, opening a pull request is in a way requesting review and inclusion by the project owner.

I suppose I'm still figuring out GitHub and GitHub etiquette.

[Vagabond]

I went ahead and merged the Archive change that removed the internalName argument from the CreateVolume function.

A new branch and merge request were created for sorting filesToPack alphabetically inside the CreateVolume function.

This is the last change I currently had in mind for OP2Utility. If Leeor is looking to move is OP2-Landlord code to using OP2Utility, we could start looking at the differences between OP2Utility and his code base for merging. Otherwise, I'll look to release a new version of OP2Archive. Unless Hooman has something else he wants to review, change, fix, etc.

Vagabond, I've merged the branch.

I'm thinking about the workflow right now. In the future, it probably makes sense for you as the project owner to do the merge, and was probably silly of me to request your review after opening the pull request. I think requesting review is more suitable when there is no main project owner, or when the project owner wants code reviewed by someone else. For a lot of single author projects, opening a pull request is in a way requesting review and inclusion by the project owner.

I suppose I'm still figuring out GitHub and GitHub etiquette.

I figured you just tagged me for review since I wrote the original code as a courtesy. Which is why I keep tagging you in changes to the Archive code since you wrote it. I don't really consider myself the owner of the code. You wrote all of the archive code which is the largest piece. We co-wrote the code to load a map into memory, but we used all your notes that would have otherwise made it impossible for me to write.

Thanks,
-Brett

[leeor_net]

In reference to Hooman's comment about subfolders in VOL files:

We may want to consider the possibility of subfolders within VOL files, and how the path component interacts with the filename.

It got me thinking (especially with Brett's comments about OP2-Landlord), are the VOL files absolutely 100% required or is it possible to replace them with standard ZIP files? Is this something that our recent mods are capable of implementing or is this hard coded into the main executable?

[Vagabond]

We have been spending a fair amount of time working on OP2Utility and commenting on the progress. If you are wanting to follow the progress closely you can subrscribe to the repo on GitHub. I'd also be happy if others want to work alongside or add constructive comments, merge requests, bug reports, etc.

I have uncommitted code that saves about 2/3rds of an Outpost 2 map to file. I've been reviewing the process by loading the created file using HxD and comparing to the original file. The last portion I need to work on is adding the TileGroups at the end of the map file. I may need some help interpreting some items in the ollydbg notes section after the next time I work on it.

No one has commented negatively on the plan to use a MapReader and MapWriter as discussed above, so I will let go with that plan in addition to adding the terrain enums to OP2Utility as suggested by Leeor.

Leeor, I wouldn't mind switching to zip files but this is beyond my skills.

You could implement the mapper without involving vol files, but it would require using a separate tpool like OP2Archive to extract the tile sets and maps for use in the mapper. I would recommend considering allowing for reading of vol files to load tile sets and maps at least. It would probably be okay to force the user to repack Vols using a separate application as you only need to do this before redistributing a new version of the game. Just my opinion here though.

Thanks,
Brett

[leeor_net]

What I mean is, are the VOL files absolutely required by Outpost 2 or can we modify it to instead use a standard archive format like ZIP? ZIP is simple enough to implement via zlib or similar and I use archives like that in many of my games via PhysicsFS... so it popped into my mind that maybe we could just eliminate an archaic format and replace it with a well documented and well supported one.

[lordpalandus]

Well, as the game can load loose VOL files, I'd say it could also load zip files. Or renamed zip files.

[leeor_net]

VOL and ZIP are two totally different formats... if the main executable (outpost2.exe) is what loads the VOL files, changing it to load ZIP files instead would be non trivial. On the other hand, if the VOL files are loaded up by one of the various DLL's, adding ZIP support should be straight forward.

But I haven't followed along closely enough to know this (which is why I'm posing the question to Hooman/Vagabond   )

[Vagabond]

Leeor,

Unfortunately how Outpost 2 consumes vol and clm files internally is beyond my knowledge. I only know a fair amount about the actual file format due to Hooman's coaching and excellent documentation. He would probably be in a better spot to answer a question like this.

-Brett