# Litematica编码格式详解

此格式中最复杂的地方在于BlockStates的编码方式。BlockStates是一个LongArray类型的nbt tag，它用于储存一个region的三维矩阵信息。

每个region都有若干种方块，所有方块的种类记录于BlockStatePalette中，三维矩阵的元素均为无符号整数，每个元素的值代表这个位置的方块在palette中的索引。因此litematica以索引矩阵方式存储每个region。

为了减少空间占用，三维矩阵中每个元素的大小不是固定的，而是根据palette大小确定的。每个元素的位数是能够表示palette size-1所需的最少位数。比如2种方块需要1位，128种方块需要7位，257种方块需要9位。特别的，1种方块也需要1位。

NBT格式规定了所有基本数据类型都应当以大端序储存，解码时应当把它还原到本机所用的端序。虽然大多数电脑和服务器都是小端序，但本文将介绍一种端序无关的编解码方式，一切仅基于u64的位操作。（虽然long array是i64的数组，这里应当把它当作u64数组，方便位操作）。下文将不再使用字节的描述，仅通过位和位的索引来描述每个元素被编码的位置。

将整个u64数组想象成一个很长的bitset，若u64数组有N个元素，对应的bitset就有64N个元素。因此在整个bitset中，第i个位是第 $\lfloor i/64 \rfloor$个u64的第$i \ mod\ 64$位。


为了方便，定义“逻辑位索引”（logical bit index），它从63开始递减，取值范围为$(-\infty,63]$。由于会延伸到负数范围，因此需要用isize表示。

若每个元素需要用b个位表示，则第i个元素占据的第一个逻辑位
$$L_f=63-(b(i+1)-1)$$
它占据的最后一个逻辑位
$$L_l=63-bi$$

逻辑位索引和正常的位索引之间可以换算。为了方便讨论，将整个bitset上的索引称之为全局位索引，取值范围为非负整数；每个u64内部的位索引称为局部位索引，范围为$[0,63]$。因此从逻辑位索引换算为全局位索引的方法为
$$g=L+128\cdot\lceil\frac{-L}{64}\rceil$$

可见，在$[0,63]$范围内，逻辑位索引和全局位索引相等，$L=g$。

通过以上公式，可以计算出第i个元素占据的第一个和最后一个全局位索引$g_f$和$g_l$。若$g_f<g_l$，则这个元素占据的第一位和最后一位在同一个u64上，否则它被分成两段，存储在两个相邻的u64上。