hfs_btree.hpp

Go to the documentation of this file.

// hfs_btree.hpp -- HFS+ B-tree node parsing (header level only, session 1).
//
// Reference: TN1150 § "B-Trees".
//
// Every B-tree node starts with a 14-byte BTNodeDescriptor:
//   __be32 fLink         forward sibling node number
//   __be32 bLink         backward sibling node number
//   __u8   kind           -1=leaf, 0=index, 1=header, 2=map
//                          (stored as two's-complement signed byte)
//   __u8   height         distance from leaves (leaves = 1, root = depth)
//   __be16 numRecords     number of records in this node
//   __be16 reserved       always 0
//
// The HEADER node (kind=1, always node 0 of the B-tree) is special:
// after the descriptor, its first record holds a 106-byte BTHeaderRec
// describing the tree (root node, depth, node size, etc.).
//
// In session 1 we only parse these two structures. The full B-tree
// walker (descend index nodes, iterate leaf records) lands in session
// 2 alongside the catalog/extents file readers.
 
#pragma once
 
#include <cstdint>
#include <functional>
#include <string>
#include <vector>
 
namespace hfs {
 
// Node kinds
constexpr int8_t  kBTLeafNode   = -1;
constexpr int8_t  kBTIndexNode  =  0;
constexpr int8_t  kBTHeaderNode =  1;
constexpr int8_t  kBTMapNode    =  2;
 
// HFSX key-compare types (stored in BTHeaderRec.keyCompareType)
constexpr uint8_t kHFSCaseFolding = 0xCF;  // case-INsensitive (default)
constexpr uint8_t kHFSBinaryCompare = 0xBC; // case-SENSITIVE (HFSX)
 
// HFS+ btreeType values (stored in BTHeaderRec.btreeType)
constexpr uint8_t kHFSBTreeType = 0xFF;
constexpr uint8_t kUserBTreeType = 0x80;
constexpr uint8_t kReservedBTreeType = 0x00;
 
// 14-byte node descriptor at the start of every node.
struct NodeDescriptor {
    uint32_t fLink      {0};   // next-sibling node number, 0 if none
    uint32_t bLink      {0};   // prev-sibling node number, 0 if none
    int8_t   kind       {0};
    uint8_t  height     {0};
    uint16_t numRecords {0};
};
 
// Parse a 14-byte BTNodeDescriptor. Returns false if reserved fields
// look broken (we don't enforce reserved == 0 strictly because some
// damaged nodes still have valid records).
bool parse_node_descriptor(const unsigned char* buf, NodeDescriptor& out);
 
// 106-byte BTHeaderRec, found in the first record of node 0 of every
// HFS+ B-tree (catalog, extents, attributes, allocation has its own
// special layout).
struct HeaderRec {
    uint16_t treeDepth      {0};   // height of the tree (1 = single leaf)
    uint32_t rootNode       {0};   // node number of the root
    uint32_t leafRecords    {0};   // total leaf-level records in the tree
    uint32_t firstLeafNode  {0};   // first leaf in left-to-right order
    uint32_t lastLeafNode   {0};
    uint16_t nodeSize       {0};   // node size in bytes (typ. 4096 / 8192)
    uint16_t maxKeyLength   {0};
    uint32_t totalNodes     {0};
    uint32_t freeNodes      {0};
    uint32_t clumpSize      {0};
    uint8_t  btreeType      {0};
    uint8_t  keyCompareType {0};   // HFSX only; 0 on HFS+ classic
    uint32_t attributes     {0};
};
 
// Parse a 106-byte BTHeaderRec at the given pointer.
// The caller is responsible for locating the first record of the
// header node (typically at offset 14 = sizeof(NodeDescriptor) within
// the node buffer).
bool parse_header_rec(const unsigned char* buf, HeaderRec& out);
 
// Returns the byte offset, within a node of size `nodeSize`, of the
// `i`-th record. The record offsets are stored as 16-bit big-endian
// values at the END of the node, in REVERSE order: the last 2 bytes
// are the offset of record 0, the 2 bytes before that are record 1's
// offset, and so on. (TN1150 § "Record Offsets".)
//
// Returns 0 if `i >= numRecords` or if the offset table would land
// outside the node.
uint16_t node_record_offset(const unsigned char* node_buf,
                            uint16_t nodeSize,
                            uint16_t numRecords,
                            uint16_t i);
 
// Convenience wrapper: returns the byte length of record `i`,
// computed as offset[i+1] - offset[i] (or end-of-records-area - offset
// for the last record).
uint16_t node_record_length(const unsigned char* node_buf,
                            uint16_t nodeSize,
                            uint16_t numRecords,
                            uint16_t i);
 
// =============================================================================
//  Catalog record types (HFS+ kCatalogRecordType*)
// =============================================================================
//
// Each leaf record in the catalog B-tree starts with a 2-byte big-endian
// recordType discriminator immediately after the key. We expose the four
// values; their bodies are decoded in session 3.
 
constexpr int16_t kHFSPlusFolderRecord       = 0x0001;
constexpr int16_t kHFSPlusFileRecord         = 0x0002;
constexpr int16_t kHFSPlusFolderThreadRecord = 0x0003;
constexpr int16_t kHFSPlusFileThreadRecord   = 0x0004;
 
// =============================================================================
//  Catalog key
// =============================================================================
//
// HFSPlusCatalogKey layout:
//   __be16 keyLength       (length of the rest of the key, NOT including
//                            this 2-byte length field itself)
//   __be32 parentID        (parent folder CNID)
//   __be16 nameLength      (number of UTF-16 code units, NOT bytes)
//   UniChar name[nameLength]  (UTF-16-BE, NFD)
//
// Total key size = 2 + keyLength bytes. The name length in bytes is
// nameLength * 2.
 
struct CatalogKey {
    uint32_t parentID    {0};
    uint16_t nameLength  {0};   // UTF-16 code units
    const unsigned char* name_utf16be {nullptr};  // points INTO the buffer
    uint16_t total_key_bytes {0};   // 2 (keyLength) + keyLength
};
 
// Parse a catalog key starting at `key_buf`. Returns false if the key
// length would overflow `max_bytes`.
bool parse_catalog_key(const unsigned char* key_buf,
                        uint32_t max_bytes,
                        CatalogKey& out);
 
// Compute the byte offset (within a record buffer) where the record body
// starts, i.e. immediately after the catalog key. Index nodes use this
// same layout (key + 4-byte child node pointer).
//
// Returns 0 on bad key.
uint32_t catalog_record_body_offset(const unsigned char* record_buf,
                                     uint32_t record_len);
 
// =============================================================================
//  Generic B-tree walker
// =============================================================================
//
// We walk a B-tree rooted at `header.rootNode` recursively. For every
// leaf record found, the callback is invoked with the raw record buffer.
// The callback can return false to stop traversal early.
//
// `read_node(node_index, out_buf)` is a user-supplied function that reads
// `header.nodeSize` bytes for the given node index. This indirection lets
// us drive the walker against:
//   - a real on-disk catalog file (via fork reader)
//   - an in-memory mock (for tests)
//
// The walker DOES NOT itself decode catalog records; callers do that.
// We only know how to parse the node descriptor + record offsets.
 
using NodeReader =
    std::function<bool(uint32_t node_index, std::vector<unsigned char>& out)>;
 
using LeafRecordCallback =
    std::function<bool(const unsigned char* record_buf, uint16_t record_len)>;
 
bool walk_btree(const HeaderRec& header,
                const NodeReader& read_node,
                const LeafRecordCallback& on_leaf,
                std::vector<std::string>& logs,
                std::string& error);
 
} // namespace hfs