{"thread":{"id":"65836","subject":"[PATCH] doc: detail LMAP binary format specification","startedAt":"2026-06-18T17:06:18Z","lastAt":"2026-06-18T17:06:18Z","messageCount":1,"participants":["irsalshydiq"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"545871","messageId":"20260619000000.3286-1-ichalprov@gmail.com","threadId":"65836","inReplyTo":null,"subject":"[PATCH] doc: detail LMAP binary format specification","fromName":"irsalshydiq","fromEmail":"ichalprov@gmail.com","sentAt":"2026-04-16T05:55:42Z","receivedAt":"2026-06-18T17:06:18Z","isPatch":true,"body":"The experimental Rust implementation in 'loose.rs' introduces a new\nbinary format called 'LMAP' for mapping between different object ID\nformats (e.g., SHA-1 and SHA-256).\n\nHowever, the technical documentation for this format was missing from\nthe 'Documentation/technical/' directory, making it difficult for\nC developers to understand the format's layout and logic.\n\nAdd 'Documentation/technical/loose-object-map.adoc' to provide a bit-by-bit\nspecification of the 'LMAP' format and register it in the build systems.\n\nSigned-off-by: irsalshydiq <ichalprov@gmail.com>\n---\n Documentation/Makefile                        |  1 +\n Documentation/technical/loose-object-map.adoc | 72 +++++++++++++++++++\n Documentation/technical/meson.build           |  1 +\n 3 files changed, 74 insertions(+)\n create mode 100644 Documentation/technical/loose-object-map.adoc\n\ndiff --git a/Documentation/Makefile b/Documentation/Makefile\nindex 2699f0b24a..8ad908d62c 100644\n--- a/Documentation/Makefile\n+++ b/Documentation/Makefile\n@@ -126,6 +126,7 @@ TECH_DOCS += technical/directory-rename-detection\n TECH_DOCS += technical/hash-function-transition\n TECH_DOCS += technical/large-object-promisors\n TECH_DOCS += technical/long-running-process-protocol\n+TECH_DOCS += technical/loose-object-map\n TECH_DOCS += technical/multi-pack-index\n TECH_DOCS += technical/packfile-uri\n TECH_DOCS += technical/pack-heuristics\ndiff --git a/Documentation/technical/loose-object-map.adoc b/Documentation/technical/loose-object-map.adoc\nnew file mode 100644\nindex 0000000000..6e8dbd6c6f\n--- /dev/null\n+++ b/Documentation/technical/loose-object-map.adoc\n@@ -0,0 +1,72 @@\n+Loose Object Map (LMAP) format\n+============================\n+\n+The loose object map file (LMAP) provides a way to map between different object\n+ID formats (e.g., SHA-1 and SHA-256) for loose objects. It is designed for\n+efficient lookup and storage of these mappings.\n+\n+All multi-byte integers are in network byte order (big-endian).\n+\n+== File Layout\n+\n+- A header (20 bytes)\n+- An Object Format Table (16 bytes per format)\n+- A Trailer Offset (8 bytes)\n+- Data Sections (variable length, 4-byte aligned)\n+- A Trailer (variable length, defined by hash algorithm)\n+\n+=== Header\n+\n+- 4-byte signature: `LMAP`\n+- 4-byte version number: The current version is 1.\n+- 4-byte header size: The total size of the header, including the Object Format Table and Trailer Offset.\n+- 4-byte number of items: The number of object IDs mapped in this file.\n+- 4-byte number of object formats: The number of different hash algorithms supported in this file (minimum 2).\n+\n+=== Object Format Table\n+\n+For each object format (as specified in the header), there is a 16-byte entry:\n+\n+- 4-byte Format ID: The identifier for the hash algorithm (e.g., `0x73686131` for SHA-1, `0x73323536` for SHA-256).\n+- 4-byte Shortened Length: The minimum number of bytes needed to unambiguously identify an object ID in this format within this file.\n+- 8-byte Data Offset: The absolute offset from the beginning of the file to the start of the data section for this format.\n+\n+=== Trailer Offset\n+\n+- 8-byte Trailer Offset: The absolute offset from the beginning of the file to the start of the Trailer.\n+\n+=== Data Sections\n+\n+Each object format has a corresponding data section starting at the offset provided in the Object Format Table. Each data section is aligned to a 4-byte boundary.\n+\n+==== Format 1 (Storage Format) Data Section\n+\n+The first format listed is considered the \"storage\" or \"main\" format. Its data section contains:\n+\n+1. **Shortened Index**: `(number of items) * (shortened length)` bytes.\n+   This table contains the first `shortened length` bytes of each object ID, sorted lexicographically. This allows for binary search lookup.\n+\n+2. **Full OID Table**: `(number of items) * (hash length)` bytes.\n+   The full object IDs for the storage format, in the same order as the Shortened Index.\n+\n+3. **Metadata Table**: `(number of items) * 4` bytes.\n+   A table of 32-bit integers representing the type of each object:\n+   - 0: Reserved (e.g., null OID, empty tree/blob)\n+   - 1: Loose Object\n+   - 2: Shallow Commit\n+   - 3: Submodule Commit\n+\n+==== Subsequent Format (Compatibility) Data Section\n+\n+For each subsequent format, the data section contains:\n+\n+1. **Shortened Index**: Similar to the storage format, but for the compatibility algorithm's OIDs.\n+\n+2. **Full OID Table**: The full object IDs in the compatibility algorithm.\n+\n+3. **Mapping Table**: `(number of items) * 4` bytes.\n+   A table of 32-bit integers. Each entry at index `i` provides the index in the **storage format's** tables that corresponds to this compatibility object ID.\n+\n+=== Trailer\n+\n+- Variable length: The hash of all preceding bytes in the file, calculated using the main hash algorithm.\ndiff --git a/Documentation/technical/meson.build b/Documentation/technical/meson.build\nindex ec07088c57..dc1249f9aa 100644\n--- a/Documentation/technical/meson.build\n+++ b/Documentation/technical/meson.build\n@@ -16,6 +16,7 @@ articles = [\n   'large-object-promisors.adoc',\n   'long-running-process-protocol.adoc',\n   'multi-pack-index.adoc',\n+  'loose-object-map.adoc',\n   'packfile-uri.adoc',\n   'pack-heuristics.adoc',\n   'parallel-checkout.adoc',\n-- \n2.50.1 (Apple Git-155)\n\n"}]}