BMF Files

Nature's Debris introduces a new file format which you can find in world saves under subfolders of the md folder. These .bmf files are called Binary Map Format files, and they store multiple NBT tags under 64-bits keys in one file. It's basically a region file, but with a different structure. This page gives a detailed description of BMF.

The BMF implementation can be found at src/main/java/net/rgsw/io/BMFFile.java.

The structure

The binary data that is stored in BMF is split up in sectors of a fixed size. Each sector has the same size, which may differentiate from context to context. This sector size is not indicated in the header and it should just match with the context. When a sector is partially filled with data, the trailing space can be filled with random bytes, usually 0s.
Sectors may be spread randomly across the format. In the first case this might seem inefficient, but it's definitely more efficient than ordering all the sectors so that all data can be read from left to right. After all the binary data, a footer indicates which sectors should be read in which order to reconstruct the data from the randomly ordered sectors.

The header

A BMF file starts with a 4-bytes header. This is a 32-bits integer indicating the amount of sectors that will follow. The first bit (sign) of this integer is not used, but is reserved and must be always 0. The amount of actual bytes that follow can be determined by multiplying the sector count with the sector size, which is dependent of the context.

The sectors

Right after the header, all the sectors follow. The amount of sectors that follow must exactly match the amount of sectors that was specified in the header. Again, these sectors can have any order, which must be completely independent from the data that was stored in each sector.
The data stored in the file can be compressed in GZip or DEFLATE format, or can be kept uncompressed. The compression level is the same for every binary in the file, and is, just like the sector size, dependent of the context. Additionally, contexts may stream manually compressed data into the file, of which the compression type can be different per binary. BMF files just treat the compressed binaries as a stream of uncompressed bytes, and they should be decompressed manually after reading them.

The footer

After the header and all the sectors follows the footer. This footer maps the references to a list of integers that indicate how the data saved under this reference can be reconstructed. This is the entry table. The entry table is placed in the footer because of its flexible size, basically the same reason as why sectors can be ordered randomly (this is descibed below). The header more or less indicates where the footer starts.
The entry table starts with 4 bytes indicating the amount of entries in the file. This is again a signed integer, of which the sign bit is reserved and must always be 0.
After the 4 bytes follows the indicated amount of index tables. Index tables map the 64-bits reference keys to tables indicating which sectors store which part of the data and in which order they should be read. These tables basically indicate how the data can be reconstructed from the random sector order. Each index table starts with a 64-bits integer that stores the key of the specific entry. This key is signed, but its sign does not matter: keys may be negative. The only reserved key is 0 (null). The key is followed by a 32-bits integer indicating the amount of sectors that the corresponding entry uses. This may be, but is not always the amount of integers that are left in the index list.
The index list is an ordered list of integers, specifying the indices of the sectors that contain the data of the corresponding entry in the correct order. These indices are signed 32-bits integers, where negative indices specify special operands. Currently, only -1 and -2 are used:

Index Number	Description
>= 0	Specifies a concrete index in the sector list, where 0 is the first sector.
-1	Specifies an unexisting, and thus completely empty sector. Each byte in this sector is 0.
-2	Specifies a range of consecutive indices. Another positive index should follow this index to indicate the amount of consecutive indices. The range starts at the index before this integer, plus one. For example: 15 -2 6 is the same as 15 16 17 18 19 20 21 and literally means 15 followed by 6 other consecutive indices.

The index list continues until the right amount of sectors is specified. Each item of the index list specifies a specific amount of sectors, and all the items together must match the amount of sectors specified before the index list.

Why are sectors randomly ordered?

Binaries stored in BMF files can have flexible sizes. This means that when the binary is rewritten, its size may change, and it may eventually take more or less bytes than it did before. If all sectors are arranged in the order of the binaries (so that you can read the binaries from left to right), you need to shift all sectors of the other binaries when a binary resizes, otherwise you would overwrite other sectors or you would create a large gap in the file. The shifting operation requires you to load (possibly very large) parts of the file into memory, just to rewrite them elsewhere in the file. In BMF, sectors are randomly ordered. When a binary grows in size, more sectors are appended at the end of the file. When a binary shrinks in size, sectors at the end of the file are moved into the created gap. This has a positive effect on the performance and memory usage of the implementation, as we don't need to move a lot of bytes (only a few when a gap is created).
For the same reason, the entry table is placed in a footer. If it would have been in the header, all sectors had to be shifted when it changes in size (e.g. when an entry is added or removed). In the footer, it can grow or shrink freely in size as there is no data that needs to be shifted.

An example, that uses strings and characters instead of binaries and bytes. Below you see two strings, "THISISTEXT" and "ABCDEFGHIJKLM" saved in sectors of 4 chars (0 is an unused byte).

HEADER  SECTORS
0007    THIS ISTE XT00 ABCD EFGH IJKL M000

If we would change "THISISTEXT" into "THIS_IS_LONGER_TEXT" (adding two sectors), and we don't order sectors randomly, the following operations happen in consecutive order:

HEADER  0    1    2    3    4    5    6    7    8
0007    THIS ISTE XT00 ABCD EFGH IJKL M000            ~ Before doing anything
0009    THIS ISTE XT00 ABCD EFGH IJKL M000 0000 0000  ~ Extend to 9 sectors (allocate 2)
0009    THIS ISTE XT00 ABCD EFGH IJKL M000 0000 M000  ~ Move 6 to 8
0009    THIS ISTE XT00 ABCD EFGH IJKL M000 IJKL M000  ~ Move 5 to 7
0009    THIS ISTE XT00 ABCD EFGH IJKL EFGH IJKL M000  ~ Move 4 to 6
0009    THIS ISTE XT00 ABCD EFGH ABCD EFGH IJKL M000  ~ Move 3 to 5
0009    THIS ISTE XT00 ABCD EFGH ABCD EFGH IJKL M000  ~ Rewrite sector 0: THIS
0009    THIS _IS_ XT00 ABCD EFGH ABCD EFGH IJKL M000  ~ Rewrite sector 1: _IS_
0009    THIS _IS_ LONG ABCD EFGH ABCD EFGH IJKL M000  ~ Rewrite sector 2: LONG
0009    THIS _IS_ LONG ER_T EFGH ABCD EFGH IJKL M000  ~ Rewrite sector 3: ER_T
0009    THIS _IS_ LONG ER_T EXTH ABCD EFGH IJKL M000  ~ Rewrite sector 4: EXT  (note that the last char is left unchanged)

In the second case, we use the same strings, and apply the same change. However, now we allow random ordering of the sectors:

HEADER  0    1    2    3    4    5    6    7    8
0007    THIS ISTE XT00 ABCD EFGH IJKL M000            ~ Before doing anything
0009    THIS ISTE XT00 ABCD EFGH IJKL M000 0000 0000  ~ Extend to 9 sectors (allocate 2)
0009    THIS ISTE XT00 ABCD EFGH IJKL M000 0000 0000  ~ Rewrite sector 0: THIS
0009    THIS _IS_ XT00 ABCD EFGH IJKL M000 0000 0000  ~ Rewrite sector 1: _IS_
0009    THIS _IS_ LONG ABCD EFGH IJKL M000 0000 0000  ~ Rewrite sector 2: LONG
0009    THIS _IS_ LONG ABCD EFGH IJKL M000 ER_T 0000  ~ Rewrite sector 7: ER_T
0009    THIS _IS_ LONG ABCD EFGH IJKL M000 ER_T EXT0  ~ Rewrite sector 8: EXT  (again, the last char is left unchanged)

As you can see, the second case uses only 6 I/O operations while the first case needed 10 operations. In large files, this technique can decrease the amount of I/O operations down to only 10% of what we would need when using the shifting technique.

Drawbacks

• A drawback of the random-order technique is that reading takes a little more performance as we need to seek back and forth throughout the file to read and write data. This is, however, only a fraction of the performance we've saved by using this technique.
• We need the ability to read back and forth throughout a BMF binary. This is possible for buffers and files (via java.io.RandomAccessFile) and some other streaming channels, but in other cases the binary needs to be buffered before it can be read as a BMF format.
• Currently, the sector size and compression type of a file are not stored in the BMF binary itself. BMF does not store a version number either. This does not allow full compatibility across all BMF files. The only version indicator that we have is the first bit of a binary, which is, and must always be 0 in the current version. This bit must indicate context independence and backward compatibility in the future.

Usages

BMF files are used as a replacement of Anvil region files (.mca files) in ND-related things. They were originally designed for the world area system as a random amount of NBT tags needed to be mapped to long keys in a specific region. Additionally, we now save the reference chunks in BMF format too, where the long keys actually hold 2 ints that specify the X and Z coords of all stored chunks.

Future of BMF

BMF is currently experimental, but I see a true future for this format in other applications than Nature's Debris. Therefore a separate library is coming for the BMF, standalone from Nature's Debris. This library will also bring backward compatibility, context independence and better performance to BMF.