(Apologies for the tl;dr, but I'm trying to explain an entire process and chain of logic here, to answer the inevitable questions of "Why not just do this?")
So zero padding the end was the first thing I tried, but it caused the game to crash. Just tried it again and it worked though, so I guess the bug was something else that I've since fixed.
Regardless, I still have a reason to do things the way that I am, and that's mod compatibility. Obviously, the compressor I wrote can deal with entire files at once, but dealing with them in segments improves mod compatibility. If I patch the entire file, then only the one patch is viable. But if I patch individual segments only, then any future mods that use that file will be compatible so long as they don't target any overlapping blocks.
Additionally, the way I handle segments, I write the start and end offset of the segment to a metadata file when I decompress. That way, when I compress it again, I can just copy the data before and after the segment I'm actually compressing, which is a lot faster than always decompressing and compressing every block (especially in one case where I'm targeting 6 blocks out of about 450). But of course, if I am doing multiple segments in a batch, if I compress one and it alters the file size, suddenly the metadata for the other segments is incorrect. I realize this could be resolved by using a looping workflow of decompress/extract single segment/file -> insert script -> compress/insert segment/file, but that's a lot less convenient for working on mods than a workflow of decompress/extract all segments/files -> insert all scripts -> compress/insert all segments/files. Plus, these tools are intended for more general use beyond text insertion as well, where this might be even less convenient. Basically what I'm saying is that somewhere I have to sacrifice some degree of convenience, and workflow isn't where I want to do it. So I'm trying to do something that's computationally more difficult, but simpler for the person trying to mod the game.
I have at least solved the issue of the end user of the mod having to wait on a randomized process, though. When the compressor hits on a successful sequence of sort orders for the blocks, it appends that sequence to the metadata file. During patch creation, this sequence is attached to the xdelta file, then stripped off during patch application and attached to the metadata again at the user's end, guaranteeing it will succeed first time, every time.
That still leaves me looking for a less naïve implementation of the compressor to speed up the process of finding a successful sort order sequence, if anyone has any ideas.
EDIT: I just had a couple thoughts on a compromise solution. What if, when I do a batch compression of multiple segments within the same file, I just do it in reverse order from the highest-numbered set of blocks to the lowest? That way, if one results in a smaller file, it won't impact the location of the next segment to be compressed?
Attacking from the other end, would it be worthwhile, instead of using start and end offsets from a static metadata file to copy the data on either side of the segment, to run the decompressor from within the compression process to generate the correct offsets at runtime? It would cause the compressor to take a performance hit, but the compressed size of a segment would no longer matter beyond sometimes needing to be no larger than the original.
I can see advantages and drawbacks to both. Anyone have thoughts?