One of the features that we would love to add into Assembly is model script injection. However, in order to do this, we need to be able to add extra entries into a "scripts" reflexive in scnr. There aren't any "stub" script entries that we can just replace (well, technically there can be, but they don't appear in retail maps), and there also isn't any free space after the reflexive because tags are packed pretty tightly. This means that we need to move the reflexive to a different place that has room for the extra entries.
Traditionally, modders have "resized" reflexives by simply finding one large enough in an "unused" tag and overwriting that by copying the offset over. It works pretty well, and it's really simple to do...manually. The problem is that we're making a map editor here, and Assembly has no way of knowing what tags you don't plan on using (unless we ask you to mark them in some sort of dialog, but that's just plain stupid), so we actually need to find space in the file which isn't used by anything. And that's a problem in itself, because doing so normally would require us to scan every single tag's metadata and build a map of the file's memory usage. That just isn't feasible.
We finally decided that we have no other choice but to actually inject extra space into the file. It is really the only reliable method of expanding a chunk infinitely, because it allows us to know for certain where a large-enough space in the file is. After doing lots of research on the subject, we were able to figure out how this works, and today I'm going to be sharing that.
Injecting extra space into the file involves taking the following steps:
- Figuring out where to inject the data
- Figuring out how much data to inject
- Actually injecting the data
- Adjusting the file so that it loads the new data
Without any further ado, let's get started.
Step 1: Finding the location to inject data to
Obviously, we can't inject any data if we don't know where to put it. Sure, we need to expand the area of the file where tag meta is stored, but how do we know where that is? Let's take a little look into the .map format.
First of all, .map files have the following general layout (not drawn to scale):
Now, the two main blocks that we need to focus on are the file header and the tag metadata. The "tag metadata" block is the section of the file where tags and reflexives are stored, and that's the section that we're interested in expanding. In order to know where it is, though, we need to look at the file header. Obviously, that's at the very beginning of the file, and it's the first thing that you will see when you open the .map in a hex editor.
I currently have the following header values mapped out (these offsets are for Reach, but they're very similar in the other games):
0000 int32 magic = 'head'
0004 int32 game version
0008 int32 file size
0010 uint32 tag table header address
0014 uint32 index offset of the end of the file (file size - locale address mask)
0018 uint32 virtual size (sizes of all partitions added together, see below)
013C int16 type
0158 int32 number of stringIDs
015C int32 size of stringID data
0160 int32 pointer to the stringID offset table (not a memory address, but irrelevant here)
0164 int32 pointer to the stringID data
018C asciiz internal name
01B0 asciiz scenario name
02B4 int32 number of tag names
02B8 int32 pointer to tag name data
02BC int32 size of tag name data
02C0 int32 pointer to tag name offset table
02E8 uint32 virtual base (memory address of partition 0, see below)
02EC int32 xdk version
02F0 uint32 partition 0 address
02F4 int32 partition 0 size
02F8 uint32 partition 1 address
02FC int32 partition 1 size
0300 uint32 partition 2 address
0304 int32 partition 2 size
0308 uint32 partition 3 address
030C int32 partition 3 size
0310 uint32 partition 4 address
0314 int32 partition 4 size
0318 uint32 partition 5 address
031C int32 partition 5 size
0470 int32 file offset of asset data
0478 int32 locale address mask (aka "index offset magic," controls where the locale tables are located)
047C int32 stringID/tagname table address mask (minus the header size)
0480 int32 offset of asset data, relative to the end of the file header
0488 int32 asset data size
048C int32 index offset of the end of the file
0490 int32 virtual size (size of the tag metadata, or all partition sizes added together)
0494 int32 pointer to the first locale table (file offset of the first locale table - locale address mask)
0498 int32 size of the locale data
As you might have noticed, however, there isn't a direct pointer to where the metadata is - we'll need to do a bit of math. But it's pretty simple. If you look back at the .map layout diagram above, you'll see that the tag metadata immediately follows the asset table. And guess what: the header stores the file offset and the size of the asset data! This means that all we have to do is add the two values together:
offset of tag metadata = file offset of asset data + asset data size
(note: subtract the virtual base from that result and you have the map magic!)
All right, so we have the file offset of the metadata block. We just need to determine where to put the injected data inside of that block. Ideally, we would want to insert the data in a way that doesn't throw off any memory addresses in the file, because going back and adjusting everything would be a huge pain and would be very error-prone. My first thought was to put the injected data at the end of the metadata, because logically that would be pretty easy, right?
Wrong. It turns out that doing so makes the game completely reject the .map file even if you adjust the header correctly. It doesn't even bother trying to RSA check it; loading will simply stop at 0%. See, all of the .map files vary in size, and Bungie decided to play things safe. Rather than putting every .map file at a fixed base address in memory and setting a size limit on them so that they don't overflow into other data, they build the files to always end at a certain address (in Reach, this is 0xBFC00000). This means that injecting our extra data at the end of the file will cause the file to surpass that memory address and fail to load.
Taking this into consideration, our only choice is to inject data at the very beginning of the metadata. And at a first glance, this might seem like a radical thing to do: wouldn't that push back every single memory address in the file? Let's take a closer look at the .map format.
Something that you might have noticed in my map of the file header is that there are a bunch of "partition X address" and "partition X size" values. This is because .map files are split into what are known as "partitions" (this presentation made by Bungie briefly explains this). Tag metadata is actually divided into blocks based upon purpose (and probably for debugging reasons), and those partition values control how large each block is and what the block's memory address should be. This means that we can actually inject data at the beginning of the meta without changing any memory addresses - we just decrease the memory address of the first partition.
After all of this, we finally know exactly where we want to inject our extra data: at the very beginning of the meta partition (see my "offset of tag metadata" calculation above). I know that I talked a lot there even though the calculation of this offset is very simple, but I wanted to share information on how .map files work because understanding that is key to understanding how injection works and why using that offset is the best choice.
Step 2: How much?
Okay, so this is a bit of a trivial question. But the answer actually isn't as obvious as we initially thought it was. Just because we might only need 0x200 or so bytes for our new chunk doesn't actually mean that we only need to expand the file by that much. In fact, doing so actually makes the game freeze up.
The reason behind this is because the game (and the Xbox?) expects the meta partitions to be aligned to a multiple of a certain "page size." If you've ever looked at the meta section of a .map file in a hex editor, you might have noticed that there are a lot of zero bytes in that section of the file. The purpose behind those is to pad the partition out so that its size is properly aligned.
But what is the alignment? Let's whip out our handy-dandy hex editor and take a look at the partition table:
Now, if you take a close look at that diagram, you might notice something: every single address and size always has two zero bytes at the end, making everything a multiple of 0x10000. This is our alignment! Given this, we need to adjust the size of the data we want to inject so that it is a multiple of 0x10000 and satisfies the game's alignment requirements. This formula does that for us:
size of data to inject = (size actually needed + 0xFFFF) & 0xFFFF0000
(where & is bitwise and)
And sure, this can result in a lot of wasted space because needing 0x10010 bytes means that we would actually need to inject 0x20000 bytes, but we can set up a memory allocation system to fix that problem. Now, let's inject our data!
Step 3: Bangarang
Actually injecting the space into the file is pretty easy. All we have to do is start at the end of the file and move everything back in blocks (we settled on copying 1MB at a time for now) until enough space has been made available at the beginning of the metadata.
const long BufferSize = 0x100000; // 1 MB
uint8_t* buffer = new uint8_t[BufferSize];
// Push everything back in blocks
long moved = 0;
long moveSize = header.fileSize - injectOffset;
while (moved < moveSize)
long readSize = std::min(moveSize - moved, BufferSize);
reader.seekTo(header.fileSize - moved - readSize);
long read = reader.readBlock(readSize, buffer);
writer.seekTo(header.fileSize + injectSize - moved - readSize);
moved += read;
It's also important to zero out the injected pages so that they don't cause problems when read by a meta editor, but I'm not going to show that here.
Step 4: Loading... Done
We're almost there! All we need to do now is adjust the file header so that the newly-injected pages will actually load into memory. Remember that we injected extra pages into the beginning of the meta partition. Looking back at the header layout I posted above, this means that we need to do the following:
- Increase the file size value
- Increase the virtual size value (to resize the metadata)
- Decrease the virtual base and the memory address of partition 0 (so that no memory addresses change)
- Increase the size of the first meta partition (since we injected our data there)
- Finally, increase the locale address mask since the locale tables got pushed back (see the diagram showing the general .map layout)
This code accomplishes all of that:
header.fileSize += injectSize;
header.virtualSize += injectSize;
header.virtualBase -= injectSize;
header.localeAddressMask += injectSize;
header.partitions.address -= injectSize;
header.partitions.size += injectSize;
After all of this, we've finally managed to inject empty space into the .map file that we can use for anything meta-related (injecting new tags, resizing reflexives, etc.). It's up to you how you want to use the new data.
Since this involved a fair amount of work, I have created a program called "mapexpand" (link below) which can do all of this for you. It's a command-line program because I like C++ and I was too lazy to make a GUI for it, but that shouldn't be a problem since this program is targeted at advanced modders anyway. You use it like this:
mapexpand <path to .map file> <number of 0x10000-byte pages to inject>
The program will then print the memory address and file offset of the injected data. Don't close the console window, because you'll probably need that. Just sayin.
So, for example, to add 0x20000 bytes into forge_halo.map, you can just run
mapexpand "forge_halo.map" 2
There are a few things that you need to be careful of though:
- This only adds extra meta to the .map. You can't use this program to add models or textures - that's an entirely different process.
- This program only works with the retail version of Reach for now. However, the method described in this blog post should work for Halo 3 as well, aside from differing header offsets.
- You must patch your .xex with Zedd's blue flames patches. Using a .xex patched with Reachunlock or a similar program makes the game reject the map file for a currently-unknown reason.
- Don't inject anything while Ascension or another editor is open. Injecting changes the map magic because it involves decreasing the virtual base address of the metadata.
- Ascension can't handle patching between maps of different sizes. To create a patch which requires an expanded map file, you need to set an expanded .map as the original map and instruct users to use this program (perhaps through a .bat file or a similar script) before patching.
- Finally, only inject the number of pages that you actually need. You can always add more later. Adding 50 MB to the file just because you think you might need it is stupid and will probably slow your Xbox down or make the game just crash.
Download mapexpand (includes C++ source code)
So, let's see what people can do with this.
Love you guys.