After the two header pages the file is an array of pages, all of the page size in the file header. Page n is at byte (n + 1) × page size. A page has a header, then values that grow up from the header, free space, and a table of four-byte tags that grows down from the end of the page. Each tag gives the size and place of one value, so values can be added, removed and moved without changing the tags of the others.
Page header
The first 40 bytes. Pages of 16 and 32 KiB continue the header to 80 bytes (below). Values are counted from the end of the header.
| Offset | Size | Name | Description |
|---|---|---|---|
| 0 | 4 | XOR checksum | See checksums. |
| 4 | 4 | ECC checksum | From revision 0x0b. Before it, the page number. |
| 8 | 8 | Last modified | The database time of the last change. |
| 16 | 4 | Previous page | The left sibling on the same level of the tree, 0 for none. |
| 20 | 4 | Next page | The right sibling, 0 for none. |
| 24 | 4 | Father data page object | The object identifier of the tree the page belongs to: a table, an index or a long value tree (see the catalog). |
| 28 | 2 | Available data size | Free bytes on the page. |
| 30 | 2 | Available uncommitted data size | Free bytes that entries deleted in a transaction not yet committed still hold. |
| 32 | 2 | First available data offset | Where the free space after the values starts. |
| 34 | 2 | Available page tag | The number of tags in use (the upper four bits are reserved from revision 0x122). |
| 36 | 4 | Flags | Below. |
Flags
| Bit | Name | Meaning |
|---|---|---|
| 0x1 | Root | The first page of a tree. |
| 0x2 | Leaf | Holds the data (or index) entries. A page that is not a leaf is a branch. |
| 0x4 | Parent | A branch directly above the leaves. |
| 0x8 | Empty | A page with no entries. |
| 0x10 | Pre-initialised | Not documented by libesedb. |
| 0x20 | Space tree | An extent list: see space trees. |
| 0x40 | Index | A page of an index. |
| 0x80 | Long value | A page of a long value tree. |
| 0x100, 0x200 | SLV | Streaming large value space (obsolete). |
| 0x400 | Non-unique keys | Probably: keys on the page may repeat. Listed as unknown by libesedb. |
| 0x800 | New record format | Set on every page of the files described. |
| 0x2000 | New checksum format | The page has an ECC checksum. |
| 0x4000 | Scrubbed | Probably: unused data was overwritten with a fill pattern. |
| 0x1000, 0x8000, 0x10000 | Unknown | Not documented. 0x8000 and 0x10000 occur on pages of the Windows files described. |
Pages of 16 and 32 KiB
The header is 80 bytes. After the common 40 bytes come three more checksum pairs, the page number and eight bytes that are not documented:
| Offset | Size | Name |
|---|---|---|
| 40 | 8 | XOR and ECC checksum of block 1 |
| 48 | 8 | XOR and ECC checksum of block 2 |
| 56 | 8 | XOR and ECC checksum of block 3 |
| 64 | 8 | Page number |
| 72 | 8 | Unknown (zeros) |
Checksums
Every page is protected by an XOR checksum and, from revision 0x0b, an ECC checksum. The rules below were worked out on real files and reproduce every checksum of every page of six of them (pages of 4, 8, 16 and 32 KiB).
Before revision 0x0b
The XOR of all 32-bit words of the page from offset 4, starting from 0x89abcdef, is the first word. The second word is the page number.
From revision 0x0b
The page is cut into blocks: the whole page up to 8 KiB, otherwise four blocks of a quarter of the page (4 KiB for a 16 KiB page, 8 KiB for a 32 KiB page). For each block, take its 32-bit words (the first block starts at word 2, after the two checksums):
- XOR checksum = the XOR of the words, XORed with the page number.
- ECC checksum = a 32-bit value built from the position of every set bit in the block, counted in bits from the start of the block (from word 2 in the first block). Let S be the XOR of those positions and P the parity of the number of set bits. The low 16 bits are S (its low 16 bits); the high 16 bits are S again, with every bit of the block's bit-position range inverted when P is 1 (S XOR 0x7fff for a 4 KiB block, 0xffff for 8 KiB and larger).
Block 0's pair is in the first two words; blocks 1 to 3 have theirs in the extended header (offsets 40, 48 and 56), and block 0's XOR covers those words, so they are written first. A page that is all zeros was never written and has no checksum. Because the ECC is a one-error-correcting code, it can in principle repair a single flipped bit of a page; the explorer only reports a mismatch.
function pageChecksums(page, n, blockSize):
for each block k:
words = 32-bit words of the block (the first block from word 2)
x = xor of words
s = 0; p = 0
for each set bit at position b (counted from the block's start):
s = s xor b; p = p xor 1
lo = s and 0xffff
hi = lo xor (p ? blockSize * 8 - 1 : 0) and 0xffff
xorChecksum[k] = x xor n
eccChecksum[k] = (hi << 16) or lo
Links
Reference
- Extensible Storage Engine (ESE) Database File (EDB) format – the page header, flags and tags