diff options
| author | Junio C Hamano <gitster@pobox.com> | 2022-07-11 16:08:34 -0700 |
|---|---|---|
| committer | Junio C Hamano <gitster@pobox.com> | 2022-07-11 16:08:34 -0700 |
| commit | 7bc735932830b9840daeff68819d626c3b0cd07b (patch) | |
| tree | 6c36713b44abd490cd78976f7ad2839a9268abd3 | |
| parent | ebdf143ff06ab8a67139c290755d6c6ecfe3126b (diff) | |
| download | git-htmldocs-7bc735932830b9840daeff68819d626c3b0cd07b.tar.gz | |
Autogenerated HTML docs for v2.37.0-38-g55ece
30 files changed, 1330 insertions, 158 deletions
diff --git a/RelNotes/2.38.0.txt b/RelNotes/2.38.0.txt index a96fcabd8..f3e36b12f 100644 --- a/RelNotes/2.38.0.txt +++ b/RelNotes/2.38.0.txt @@ -1,9 +1,40 @@ Git v2.38 Release Notes ======================= +Performance, Internal Implementation, Development Support etc. + + * Collection of what is referenced by objects in promisor packs have + been optimized to inspect these objects in the in-pack order. + (merge 18c08abc82 jk/optim-promisor-object-enumeration later to maint). + + * Introduce a helper to see if a branch is already being worked on + (hence should not be newly checked out in a working tree), which + performs much better than the existing find_shared_symref() to + replace many uses of the latter. + + * Teach "git archive" to (optionally and then by default) avoid + spawning an external "gzip" process when creating ".tar.gz" (and + ".tgz") archives. + (merge 4f4be00d30 rs/archive-with-internal-gzip later to maint). + + Fixes since v2.37 ----------------- * Rewrite of "git add -i" in C that appeared in Git 2.25 didn't correctly record a removed file to the index, which was fixed. (merge 4788e8b256 js/add-i-delete later to maint). + + * Certain diff options are currently ignored when combined-diff is + shown; mark them as incompatible with the feature. + (merge cfb19ae05f rs/combine-diff-with-incompatible-options later to maint). + + * Adjust technical/bitmap-format to be formatted by AsciiDoc, and + add some missing information to the documentation. + (merge ac7667bd44 ac/bitmap-format-doc later to maint). + + * Other code cleanup, docfix, build fix, etc. + (merge 5fd9d1738e jk/revisions-doc-markup-fix later to maint). + (merge 1971510c35 pb/diff-doc-raw-format later to maint). + (merge a3ba4fa715 cr/setup-bug-typo later to maint). + (merge 85845580d9 ds/vscode-settings later to maint). diff --git a/diff-format.txt b/diff-format.txt index 7a9c3b6ff..a3ae8747a 100644 --- a/diff-format.txt +++ b/diff-format.txt @@ -43,7 +43,7 @@ That is, from the left to the right: . a space. . sha1 for "src"; 0\{40\} if creation or unmerged. . a space. -. sha1 for "dst"; 0\{40\} if creation, unmerged or "look at work tree". +. sha1 for "dst"; 0\{40\} if deletion, unmerged or "work tree out of sync with the index". . a space. . status, followed by optional "score" number. . a tab or a NUL when `-z` option is used. @@ -69,8 +69,8 @@ percentage of similarity between the source and target of the move or copy). Status letter M may be followed by a score (denoting the percentage of dissimilarity) for file rewrites. -<sha1> is shown as all 0's if a file is new on the filesystem -and it is out of sync with the index. +The sha1 for "dst" is shown as all 0's if a file on the filesystem +is out of sync with the index. Example: diff --git a/git-archive.html b/git-archive.html index 15e99f70e..1a209e40b 100644 --- a/git-archive.html +++ b/git-archive.html @@ -783,10 +783,12 @@ comment.</p></div> </dt>
<dd>
<p>
- Format of the resulting archive: <em>tar</em> or <em>zip</em>. If this option
+ Format of the resulting archive. Possible values are <code>tar</code>,
+ <code>zip</code>, <code>tar.gz</code>, <code>tgz</code>, and any format defined using the
+ configuration option <code>tar.<format>.command</code>. If <code>--format</code>
is not given, and the output file is specified, the format is
- inferred from the filename if possible (e.g. writing to "foo.zip"
- makes the output to be in the zip format). Otherwise the output
+ inferred from the filename if possible (e.g. writing to <code>foo.zip</code>
+ makes the output to be in the <code>zip</code> format). Otherwise the output
format is <code>tar</code>.
</p>
</dd>
@@ -988,21 +990,20 @@ tar.<format>.command is executed using the shell with the generated tar file on its
standard input, and should produce the final output on its
standard output. Any compression-level options will be passed
- to the command (e.g., "-9"). An output file with the same
- extension as <code><format></code> will be use this format if no other
- format is given.
+ to the command (e.g., <code>-9</code>).
</p>
-<div class="paragraph"><p>The "tar.gz" and "tgz" formats are defined automatically and default to
-<code>gzip -cn</code>. You may override them with custom commands.</p></div>
+<div class="paragraph"><p>The <code>tar.gz</code> and <code>tgz</code> formats are defined automatically and use the
+magic command <code>git archive gzip</code> by default, which invokes an internal
+implementation of gzip.</p></div>
</dd>
<dt class="hdlist1">
tar.<format>.remote
</dt>
<dd>
<p>
- If true, enable <code><format></code> for use by remote clients via
+ If true, enable the format for use by remote clients via
<a href="git-upload-archive.html">git-upload-archive(1)</a>. Defaults to false for
- user-defined formats, but true for the "tar.gz" and "tgz"
+ user-defined formats, but true for the <code>tar.gz</code> and <code>tgz</code>
formats.
</p>
</dd>
@@ -1148,7 +1149,7 @@ while archiving any tree in your <code>$GIT_DIR/info/attributes</code> file.</p> <div id="footer">
<div id="footer-text">
Last updated
- 2022-06-07 14:51:19 PDT
+ 2022-07-11 16:06:18 PDT
</div>
</div>
</body>
diff --git a/git-archive.txt b/git-archive.txt index 56989a2f3..60c040988 100644 --- a/git-archive.txt +++ b/git-archive.txt @@ -34,10 +34,12 @@ OPTIONS ------- --format=<fmt>:: - Format of the resulting archive: 'tar' or 'zip'. If this option + Format of the resulting archive. Possible values are `tar`, + `zip`, `tar.gz`, `tgz`, and any format defined using the + configuration option `tar.<format>.command`. If `--format` is not given, and the output file is specified, the format is - inferred from the filename if possible (e.g. writing to "foo.zip" - makes the output to be in the zip format). Otherwise the output + inferred from the filename if possible (e.g. writing to `foo.zip` + makes the output to be in the `zip` format). Otherwise the output format is `tar`. -l:: @@ -143,17 +145,16 @@ tar.<format>.command:: is executed using the shell with the generated tar file on its standard input, and should produce the final output on its standard output. Any compression-level options will be passed - to the command (e.g., "-9"). An output file with the same - extension as `<format>` will be use this format if no other - format is given. + to the command (e.g., `-9`). + -The "tar.gz" and "tgz" formats are defined automatically and default to -`gzip -cn`. You may override them with custom commands. +The `tar.gz` and `tgz` formats are defined automatically and use the +magic command `git archive gzip` by default, which invokes an internal +implementation of gzip. tar.<format>.remote:: - If true, enable `<format>` for use by remote clients via + If true, enable the format for use by remote clients via linkgit:git-upload-archive[1]. Defaults to false for - user-defined formats, but true for the "tar.gz" and "tgz" + user-defined formats, but true for the `tar.gz` and `tgz` formats. [[ATTRIBUTES]] diff --git a/git-diff-files.html b/git-diff-files.html index 55f61bae3..5479b206f 100644 --- a/git-diff-files.html +++ b/git-diff-files.html @@ -2180,7 +2180,7 @@ a space. </li>
<li>
<p>
-sha1 for "dst"; 0{40} if creation, unmerged or "look at work tree".
+sha1 for "dst"; 0{40} if deletion, unmerged or "work tree out of sync with the index".
</p>
</li>
<li>
@@ -2267,8 +2267,8 @@ X: "unknown" change type (most probably a bug, please report it) percentage of similarity between the source and target of the move or
copy). Status letter M may be followed by a score (denoting the
percentage of dissimilarity) for file rewrites.</p></div>
-<div class="paragraph"><p><sha1> is shown as all 0’s if a file is new on the filesystem
-and it is out of sync with the index.</p></div>
+<div class="paragraph"><p>The sha1 for "dst" is shown as all 0’s if a file on the filesystem
+is out of sync with the index.</p></div>
<div class="paragraph"><p>Example:</p></div>
<div class="listingblock">
<div class="content">
diff --git a/git-diff-index.html b/git-diff-index.html index f727d2958..90a88f5a3 100644 --- a/git-diff-index.html +++ b/git-diff-index.html @@ -2174,7 +2174,7 @@ a space. </li>
<li>
<p>
-sha1 for "dst"; 0{40} if creation, unmerged or "look at work tree".
+sha1 for "dst"; 0{40} if deletion, unmerged or "work tree out of sync with the index".
</p>
</li>
<li>
@@ -2261,8 +2261,8 @@ X: "unknown" change type (most probably a bug, please report it) percentage of similarity between the source and target of the move or
copy). Status letter M may be followed by a score (denoting the
percentage of dissimilarity) for file rewrites.</p></div>
-<div class="paragraph"><p><sha1> is shown as all 0’s if a file is new on the filesystem
-and it is out of sync with the index.</p></div>
+<div class="paragraph"><p>The sha1 for "dst" is shown as all 0’s if a file on the filesystem
+is out of sync with the index.</p></div>
<div class="paragraph"><p>Example:</p></div>
<div class="listingblock">
<div class="content">
@@ -2719,8 +2719,8 @@ matches my working directory. But doing a <em>git diff-index</em> does:</p></div <div class="literalblock">
<div class="content">
<pre><code>torvalds@ppc970:~/git> git diff-index --cached HEAD
--100644 blob 4161aecc6700a2eb579e842af0b7f22b98443f74 commit.c
-+100644 blob 4161aecc6700a2eb579e842af0b7f22b98443f74 git-commit.c</code></pre>
+:100644 000000 4161aecc6700a2eb579e842af0b7f22b98443f74 0000000000000000000000000000000000000000 D commit.c
+:000000 100644 0000000000000000000000000000000000000000 4161aecc6700a2eb579e842af0b7f22b98443f74 A git-commit.c</code></pre>
</div></div>
<div class="paragraph"><p>You can see easily that the above is a rename.</p></div>
<div class="paragraph"><p>In fact, <code>git diff-index --cached</code> <strong>should</strong> always be entirely equivalent to
@@ -2754,7 +2754,7 @@ have not actually done a <em>git update-index</em> on it yet - there is no <div class="literalblock">
<div class="content">
<pre><code>torvalds@ppc970:~/v2.6/linux> git diff-index --abbrev HEAD
-:100644 100664 7476bb... 000000... kernel/sched.c</code></pre>
+:100644 100644 7476bb5ba 000000000 M kernel/sched.c</code></pre>
</div></div>
<div class="paragraph"><p>i.e., it shows that the tree has changed, and that <code>kernel/sched.c</code> is
not up to date and may contain new stuff. The all-zero sha1 means that to
@@ -2797,7 +2797,7 @@ always have the special all-zero sha1.</td> <div id="footer">
<div id="footer-text">
Last updated
- 2021-12-10 14:52:02 PST
+ 2022-07-11 16:06:18 PDT
</div>
</div>
</body>
diff --git a/git-diff-index.txt b/git-diff-index.txt index 679cae27d..c30d8f0da 100644 --- a/git-diff-index.txt +++ b/git-diff-index.txt @@ -69,8 +69,8 @@ done an `update-index` to make that effective in the index file. matches my working directory. But doing a 'git diff-index' does: torvalds@ppc970:~/git> git diff-index --cached HEAD - -100644 blob 4161aecc6700a2eb579e842af0b7f22b98443f74 commit.c - +100644 blob 4161aecc6700a2eb579e842af0b7f22b98443f74 git-commit.c + :100644 000000 4161aecc6700a2eb579e842af0b7f22b98443f74 0000000000000000000000000000000000000000 D commit.c + :000000 100644 0000000000000000000000000000000000000000 4161aecc6700a2eb579e842af0b7f22b98443f74 A git-commit.c You can see easily that the above is a rename. @@ -103,7 +103,7 @@ have not actually done a 'git update-index' on it yet - there is no "object" associated with the new state, and you get: torvalds@ppc970:~/v2.6/linux> git diff-index --abbrev HEAD - :100644 100664 7476bb... 000000... kernel/sched.c + :100644 100644 7476bb5ba 000000000 M kernel/sched.c i.e., it shows that the tree has changed, and that `kernel/sched.c` is not up to date and may contain new stuff. The all-zero sha1 means that to diff --git a/git-diff-tree.html b/git-diff-tree.html index 3fa4d027c..56dcd3cae 100644 --- a/git-diff-tree.html +++ b/git-diff-tree.html @@ -3451,7 +3451,7 @@ a space. </li>
<li>
<p>
-sha1 for "dst"; 0{40} if creation, unmerged or "look at work tree".
+sha1 for "dst"; 0{40} if deletion, unmerged or "work tree out of sync with the index".
</p>
</li>
<li>
@@ -3538,8 +3538,8 @@ X: "unknown" change type (most probably a bug, please report it) percentage of similarity between the source and target of the move or
copy). Status letter M may be followed by a score (denoting the
percentage of dissimilarity) for file rewrites.</p></div>
-<div class="paragraph"><p><sha1> is shown as all 0’s if a file is new on the filesystem
-and it is out of sync with the index.</p></div>
+<div class="paragraph"><p>The sha1 for "dst" is shown as all 0’s if a file on the filesystem
+is out of sync with the index.</p></div>
<div class="paragraph"><p>Example:</p></div>
<div class="listingblock">
<div class="content">
diff --git a/git-diff.html b/git-diff.html index b1790d3fe..2f97ca6c2 100644 --- a/git-diff.html +++ b/git-diff.html @@ -2312,7 +2312,7 @@ a space. </li>
<li>
<p>
-sha1 for "dst"; 0{40} if creation, unmerged or "look at work tree".
+sha1 for "dst"; 0{40} if deletion, unmerged or "work tree out of sync with the index".
</p>
</li>
<li>
@@ -2399,8 +2399,8 @@ X: "unknown" change type (most probably a bug, please report it) percentage of similarity between the source and target of the move or
copy). Status letter M may be followed by a score (denoting the
percentage of dissimilarity) for file rewrites.</p></div>
-<div class="paragraph"><p><sha1> is shown as all 0’s if a file is new on the filesystem
-and it is out of sync with the index.</p></div>
+<div class="paragraph"><p>The sha1 for "dst" is shown as all 0’s if a file on the filesystem
+is out of sync with the index.</p></div>
<div class="paragraph"><p>Example:</p></div>
<div class="listingblock">
<div class="content">
diff --git a/git-rev-parse.html b/git-rev-parse.html index 38fcbb3e8..3a0b9ee85 100644 --- a/git-rev-parse.html +++ b/git-rev-parse.html @@ -1702,7 +1702,7 @@ The <em>..</em> (two-dot) Range Notation </p>
</dd>
<dt class="hdlist1">
-The <em>…</em> (three-dot) Symmetric Difference Notation
+The <em>...</em> (three-dot) Symmetric Difference Notation
</dt>
<dd>
<p>
diff --git a/gitrevisions.html b/gitrevisions.html index 6336cea62..fcbfa3430 100644 --- a/gitrevisions.html +++ b/gitrevisions.html @@ -1169,7 +1169,7 @@ The <em>..</em> (two-dot) Range Notation </p>
</dd>
<dt class="hdlist1">
-The <em>…</em> (three-dot) Symmetric Difference Notation
+The <em>...</em> (three-dot) Symmetric Difference Notation
</dt>
<dd>
<p>
diff --git a/howto/coordinate-embargoed-releases.html b/howto/coordinate-embargoed-releases.html index b01582840..66a95c0b1 100644 --- a/howto/coordinate-embargoed-releases.html +++ b/howto/coordinate-embargoed-releases.html @@ -873,7 +873,7 @@ Thanks, <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:24 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/keep-canonical-history-correct.html b/howto/keep-canonical-history-correct.html index d121d4a81..afad95fe6 100644 --- a/howto/keep-canonical-history-correct.html +++ b/howto/keep-canonical-history-correct.html @@ -938,7 +938,7 @@ tip of your <em>master</em> again and redo the two merges:</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:24 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/maintain-git.html b/howto/maintain-git.html index ae2316fa1..f598039c6 100644 --- a/howto/maintain-git.html +++ b/howto/maintain-git.html @@ -1469,7 +1469,7 @@ $ git update-ref -d $mf/ai/topic</code></pre> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:24 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/new-command.html b/howto/new-command.html index d8637e99e..141c5c6f0 100644 --- a/howto/new-command.html +++ b/howto/new-command.html @@ -863,7 +863,7 @@ letter [PATCH 0/n]. <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:21 PDT
+ 2022-07-11 16:06:55 PDT
</div>
</div>
</body>
diff --git a/howto/rebase-from-internal-branch.html b/howto/rebase-from-internal-branch.html index a6373ecf4..6e7d1b4cf 100644 --- a/howto/rebase-from-internal-branch.html +++ b/howto/rebase-from-internal-branch.html @@ -895,7 +895,7 @@ the #1' commit.</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:24 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/rebuild-from-update-hook.html b/howto/rebuild-from-update-hook.html index 532a64ce0..e7874057a 100644 --- a/howto/rebuild-from-update-hook.html +++ b/howto/rebuild-from-update-hook.html @@ -847,7 +847,7 @@ This is still crude and does not protect against simultaneous <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:23 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/recover-corrupted-blob-object.html b/howto/recover-corrupted-blob-object.html index 38d7b9067..6e3d760c6 100644 --- a/howto/recover-corrupted-blob-object.html +++ b/howto/recover-corrupted-blob-object.html @@ -880,7 +880,7 @@ thing.</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:23 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/recover-corrupted-object-harder.html b/howto/recover-corrupted-object-harder.html index 469a93922..e174a376c 100644 --- a/howto/recover-corrupted-object-harder.html +++ b/howto/recover-corrupted-object-harder.html @@ -1189,7 +1189,7 @@ int main(int argc, char **argv) <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:23 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/revert-a-faulty-merge.html b/howto/revert-a-faulty-merge.html index d02055b6e..40c1f1c3d 100644 --- a/howto/revert-a-faulty-merge.html +++ b/howto/revert-a-faulty-merge.html @@ -1025,7 +1025,7 @@ P---o---o---M---x---x---W---x---M2 <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:23 PDT
+ 2022-07-11 16:06:57 PDT
</div>
</div>
</body>
diff --git a/howto/revert-branch-rebase.html b/howto/revert-branch-rebase.html index e8b4dc424..34626b97d 100644 --- a/howto/revert-branch-rebase.html +++ b/howto/revert-branch-rebase.html @@ -907,7 +907,7 @@ Committed merge 7fb9b7262a1d1e0a47bbfdcbbcf50ce0635d3f8f <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:21 PDT
+ 2022-07-11 16:06:55 PDT
</div>
</div>
</body>
diff --git a/howto/separating-topic-branches.html b/howto/separating-topic-branches.html index cd96734a9..b4a54d91f 100644 --- a/howto/separating-topic-branches.html +++ b/howto/separating-topic-branches.html @@ -841,7 +841,7 @@ o---o"master"</code></pre> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:23 PDT
+ 2022-07-11 16:06:56 PDT
</div>
</div>
</body>
diff --git a/howto/setup-git-server-over-http.html b/howto/setup-git-server-over-http.html index ef4651d88..2ec5b066d 100644 --- a/howto/setup-git-server-over-http.html +++ b/howto/setup-git-server-over-http.html @@ -1071,7 +1071,7 @@ help diagnosing the problem, but removes security checks.</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:23 PDT
+ 2022-07-11 16:06:56 PDT
</div>
</div>
</body>
diff --git a/howto/update-hook-example.html b/howto/update-hook-example.html index 72043a322..7c352259a 100644 --- a/howto/update-hook-example.html +++ b/howto/update-hook-example.html @@ -930,7 +930,7 @@ that JC can make non-fast-forward pushes on it.</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:22 PDT
+ 2022-07-11 16:06:56 PDT
</div>
</div>
</body>
diff --git a/howto/use-git-daemon.html b/howto/use-git-daemon.html index 967e66743..ecb0f8a5f 100644 --- a/howto/use-git-daemon.html +++ b/howto/use-git-daemon.html @@ -791,7 +791,7 @@ a good practice to put the paths after a "--" separator.</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:22 PDT
+ 2022-07-11 16:06:56 PDT
</div>
</div>
</body>
diff --git a/howto/using-merge-subtree.html b/howto/using-merge-subtree.html index b88f5f916..176f39445 100644 --- a/howto/using-merge-subtree.html +++ b/howto/using-merge-subtree.html @@ -848,7 +848,7 @@ Please note that if the other project merges from you, then it will <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:22 PDT
+ 2022-07-11 16:06:55 PDT
</div>
</div>
</body>
diff --git a/howto/using-signed-tag-in-pull-request.html b/howto/using-signed-tag-in-pull-request.html index ccd02a4e5..2511a60cc 100644 --- a/howto/using-signed-tag-in-pull-request.html +++ b/howto/using-signed-tag-in-pull-request.html @@ -952,7 +952,7 @@ as part of the merge commit.</p></div> <div id="footer">
<div id="footer-text">
Last updated
- 2022-07-02 22:18:22 PDT
+ 2022-07-11 16:06:55 PDT
</div>
</div>
</body>
diff --git a/revisions.txt b/revisions.txt index f5f17b65a..cef8c3c66 100644 --- a/revisions.txt +++ b/revisions.txt @@ -283,7 +283,7 @@ The '..' (two-dot) Range Notation:: for commits that are reachable from r2 excluding those that are reachable from r1 by '{caret}r1 r2' and it can be written as 'r1..r2'. -The '...' (three-dot) Symmetric Difference Notation:: +The '\...' (three-dot) Symmetric Difference Notation:: A similar notation 'r1\...r2' is called symmetric difference of 'r1' and 'r2' and is defined as 'r1 r2 --not $(git merge-base --all r1 r2)'. diff --git a/technical/bitmap-format.html b/technical/bitmap-format.html new file mode 100644 index 000000000..7af67d8f5 --- /dev/null +++ b/technical/bitmap-format.html @@ -0,0 +1,1128 @@ +<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
+ "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
+<head>
+<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
+<meta name="generator" content="AsciiDoc 10.1.4" />
+<title>GIT bitmap v1 format</title>
+<style type="text/css">
+/* Shared CSS for AsciiDoc xhtml11 and html5 backends */
+
+/* Default font. */
+body {
+ font-family: Georgia,serif;
+}
+
+/* Title font. */
+h1, h2, h3, h4, h5, h6,
+div.title, caption.title,
+thead, p.table.header,
+#toctitle,
+#author, #revnumber, #revdate, #revremark,
+#footer {
+ font-family: Arial,Helvetica,sans-serif;
+}
+
+body {
+ margin: 1em 5% 1em 5%;
+}
+
+a {
+ color: blue;
+ text-decoration: underline;
+}
+a:visited {
+ color: fuchsia;
+}
+
+em {
+ font-style: italic;
+ color: navy;
+}
+
+strong {
+ font-weight: bold;
+ color: #083194;
+}
+
+h1, h2, h3, h4, h5, h6 {
+ color: #527bbd;
+ margin-top: 1.2em;
+ margin-bottom: 0.5em;
+ line-height: 1.3;
+}
+
+h1, h2, h3 {
+ border-bottom: 2px solid silver;
+}
+h2 {
+ padding-top: 0.5em;
+}
+h3 {
+ float: left;
+}
+h3 + * {
+ clear: left;
+}
+h5 {
+ font-size: 1.0em;
+}
+
+div.sectionbody {
+ margin-left: 0;
+}
+
+hr {
+ border: 1px solid silver;
+}
+
+p {
+ margin-top: 0.5em;
+ margin-bottom: 0.5em;
+}
+
+ul, ol, li > p {
+ margin-top: 0;
+}
+ul > li { color: #aaa; }
+ul > li > * { color: black; }
+
+.monospaced, code, pre {
+ font-family: "Courier New", Courier, monospace;
+ font-size: inherit;
+ color: navy;
+ padding: 0;
+ margin: 0;
+}
+pre {
+ white-space: pre-wrap;
+}
+
+#author {
+ color: #527bbd;
+ font-weight: bold;
+ font-size: 1.1em;
+}
+#email {
+}
+#revnumber, #revdate, #revremark {
+}
+
+#footer {
+ font-size: small;
+ border-top: 2px solid silver;
+ padding-top: 0.5em;
+ margin-top: 4.0em;
+}
+#footer-text {
+ float: left;
+ padding-bottom: 0.5em;
+}
+#footer-badges {
+ float: right;
+ padding-bottom: 0.5em;
+}
+
+#preamble {
+ margin-top: 1.5em;
+ margin-bottom: 1.5em;
+}
+div.imageblock, div.exampleblock, div.verseblock,
+div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
+div.admonitionblock {
+ margin-top: 1.0em;
+ margin-bottom: 1.5em;
+}
+div.admonitionblock {
+ margin-top: 2.0em;
+ margin-bottom: 2.0em;
+ margin-right: 10%;
+ color: #606060;
+}
+
+div.content { /* Block element content. */
+ padding: 0;
+}
+
+/* Block element titles. */
+div.title, caption.title {
+ color: #527bbd;
+ font-weight: bold;
+ text-align: left;
+ margin-top: 1.0em;
+ margin-bottom: 0.5em;
+}
+div.title + * {
+ margin-top: 0;
+}
+
+td div.title:first-child {
+ margin-top: 0.0em;
+}
+div.content div.title:first-child {
+ margin-top: 0.0em;
+}
+div.content + div.title {
+ margin-top: 0.0em;
+}
+
+div.sidebarblock > div.content {
+ background: #ffffee;
+ border: 1px solid #dddddd;
+ border-left: 4px solid #f0f0f0;
+ padding: 0.5em;
+}
+
+div.listingblock > div.content {
+ border: 1px solid #dddddd;
+ border-left: 5px solid #f0f0f0;
+ background: #f8f8f8;
+ padding: 0.5em;
+}
+
+div.quoteblock, div.verseblock {
+ padding-left: 1.0em;
+ margin-left: 1.0em;
+ margin-right: 10%;
+ border-left: 5px solid #f0f0f0;
+ color: #888;
+}
+
+div.quoteblock > div.attribution {
+ padding-top: 0.5em;
+ text-align: right;
+}
+
+div.verseblock > pre.content {
+ font-family: inherit;
+ font-size: inherit;
+}
+div.verseblock > div.attribution {
+ padding-top: 0.75em;
+ text-align: left;
+}
+/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
+div.verseblock + div.attribution {
+ text-align: left;
+}
+
+div.admonitionblock .icon {
+ vertical-align: top;
+ font-size: 1.1em;
+ font-weight: bold;
+ text-decoration: underline;
+ color: #527bbd;
+ padding-right: 0.5em;
+}
+div.admonitionblock td.content {
+ padding-left: 0.5em;
+ border-left: 3px solid #dddddd;
+}
+
+div.exampleblock > div.content {
+ border-left: 3px solid #dddddd;
+ padding-left: 0.5em;
+}
+
+div.imageblock div.content { padding-left: 0; }
+span.image img { border-style: none; vertical-align: text-bottom; }
+a.image:visited { color: white; }
+
+dl {
+ margin-top: 0.8em;
+ margin-bottom: 0.8em;
+}
+dt {
+ margin-top: 0.5em;
+ margin-bottom: 0;
+ font-style: normal;
+ color: navy;
+}
+dd > *:first-child {
+ margin-top: 0.1em;
+}
+
+ul, ol {
+ list-style-position: outside;
+}
+ol.arabic {
+ list-style-type: decimal;
+}
+ol.loweralpha {
+ list-style-type: lower-alpha;
+}
+ol.upperalpha {
+ list-style-type: upper-alpha;
+}
+ol.lowerroman {
+ list-style-type: lower-roman;
+}
+ol.upperroman {
+ list-style-type: upper-roman;
+}
+
+div.compact ul, div.compact ol,
+div.compact p, div.compact p,
+div.compact div, div.compact div {
+ margin-top: 0.1em;
+ margin-bottom: 0.1em;
+}
+
+tfoot {
+ font-weight: bold;
+}
+td > div.verse {
+ white-space: pre;
+}
+
+div.hdlist {
+ margin-top: 0.8em;
+ margin-bottom: 0.8em;
+}
+div.hdlist tr {
+ padding-bottom: 15px;
+}
+dt.hdlist1.strong, td.hdlist1.strong {
+ font-weight: bold;
+}
+td.hdlist1 {
+ vertical-align: top;
+ font-style: normal;
+ padding-right: 0.8em;
+ color: navy;
+}
+td.hdlist2 {
+ vertical-align: top;
+}
+div.hdlist.compact tr {
+ margin: 0;
+ padding-bottom: 0;
+}
+
+.comment {
+ background: yellow;
+}
+
+.footnote, .footnoteref {
+ font-size: 0.8em;
+}
+
+span.footnote, span.footnoteref {
+ vertical-align: super;
+}
+
+#footnotes {
+ margin: 20px 0 20px 0;
+ padding: 7px 0 0 0;
+}
+
+#footnotes div.footnote {
+ margin: 0 0 5px 0;
+}
+
+#footnotes hr {
+ border: none;
+ border-top: 1px solid silver;
+ height: 1px;
+ text-align: left;
+ margin-left: 0;
+ width: 20%;
+ min-width: 100px;
+}
+
+div.colist td {
+ padding-right: 0.5em;
+ padding-bottom: 0.3em;
+ vertical-align: top;
+}
+div.colist td img {
+ margin-top: 0.3em;
+}
+
+@media print {
+ #footer-badges { display: none; }
+}
+
+#toc {
+ margin-bottom: 2.5em;
+}
+
+#toctitle {
+ color: #527bbd;
+ font-size: 1.1em;
+ font-weight: bold;
+ margin-top: 1.0em;
+ margin-bottom: 0.1em;
+}
+
+div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
+ margin-top: 0;
+ margin-bottom: 0;
+}
+div.toclevel2 {
+ margin-left: 2em;
+ font-size: 0.9em;
+}
+div.toclevel3 {
+ margin-left: 4em;
+ font-size: 0.9em;
+}
+div.toclevel4 {
+ margin-left: 6em;
+ font-size: 0.9em;
+}
+
+span.aqua { color: aqua; }
+span.black { color: black; }
+span.blue { color: blue; }
+span.fuchsia { color: fuchsia; }
+span.gray { color: gray; }
+span.green { color: green; }
+span.lime { color: lime; }
+span.maroon { color: maroon; }
+span.navy { color: navy; }
+span.olive { color: olive; }
+span.purple { color: purple; }
+span.red { color: red; }
+span.silver { color: silver; }
+span.teal { color: teal; }
+span.white { color: white; }
+span.yellow { color: yellow; }
+
+span.aqua-background { background: aqua; }
+span.black-background { background: black; }
+span.blue-background { background: blue; }
+span.fuchsia-background { background: fuchsia; }
+span.gray-background { background: gray; }
+span.green-background { background: green; }
+span.lime-background { background: lime; }
+span.maroon-background { background: maroon; }
+span.navy-background { background: navy; }
+span.olive-background { background: olive; }
+span.purple-background { background: purple; }
+span.red-background { background: red; }
+span.silver-background { background: silver; }
+span.teal-background { background: teal; }
+span.white-background { background: white; }
+span.yellow-background { background: yellow; }
+
+span.big { font-size: 2em; }
+span.small { font-size: 0.6em; }
+
+span.underline { text-decoration: underline; }
+span.overline { text-decoration: overline; }
+span.line-through { text-decoration: line-through; }
+
+div.unbreakable { page-break-inside: avoid; }
+
+
+/*
+ * xhtml11 specific
+ *
+ * */
+
+div.tableblock {
+ margin-top: 1.0em;
+ margin-bottom: 1.5em;
+}
+div.tableblock > table {
+ border: 3px solid #527bbd;
+}
+thead, p.table.header {
+ font-weight: bold;
+ color: #527bbd;
+}
+p.table {
+ margin-top: 0;
+}
+/* Because the table frame attribute is overridden by CSS in most browsers. */
+div.tableblock > table[frame="void"] {
+ border-style: none;
+}
+div.tableblock > table[frame="hsides"] {
+ border-left-style: none;
+ border-right-style: none;
+}
+div.tableblock > table[frame="vsides"] {
+ border-top-style: none;
+ border-bottom-style: none;
+}
+
+
+/*
+ * html5 specific
+ *
+ * */
+
+table.tableblock {
+ margin-top: 1.0em;
+ margin-bottom: 1.5em;
+}
+thead, p.tableblock.header {
+ font-weight: bold;
+ color: #527bbd;
+}
+p.tableblock {
+ margin-top: 0;
+}
+table.tableblock {
+ border-width: 3px;
+ border-spacing: 0px;
+ border-style: solid;
+ border-color: #527bbd;
+ border-collapse: collapse;
+}
+th.tableblock, td.tableblock {
+ border-width: 1px;
+ padding: 4px;
+ border-style: solid;
+ border-color: #527bbd;
+}
+
+table.tableblock.frame-topbot {
+ border-left-style: hidden;
+ border-right-style: hidden;
+}
+table.tableblock.frame-sides {
+ border-top-style: hidden;
+ border-bottom-style: hidden;
+}
+table.tableblock.frame-none {
+ border-style: hidden;
+}
+
+th.tableblock.halign-left, td.tableblock.halign-left {
+ text-align: left;
+}
+th.tableblock.halign-center, td.tableblock.halign-center {
+ text-align: center;
+}
+th.tableblock.halign-right, td.tableblock.halign-right {
+ text-align: right;
+}
+
+th.tableblock.valign-top, td.tableblock.valign-top {
+ vertical-align: top;
+}
+th.tableblock.valign-middle, td.tableblock.valign-middle {
+ vertical-align: middle;
+}
+th.tableblock.valign-bottom, td.tableblock.valign-bottom {
+ vertical-align: bottom;
+}
+
+
+/*
+ * manpage specific
+ *
+ * */
+
+body.manpage h1 {
+ padding-top: 0.5em;
+ padding-bottom: 0.5em;
+ border-top: 2px solid silver;
+ border-bottom: 2px solid silver;
+}
+body.manpage h2 {
+ border-style: none;
+}
+body.manpage div.sectionbody {
+ margin-left: 3em;
+}
+
+@media print {
+ body.manpage div#toc { display: none; }
+}
+
+
+</style>
+<script type="text/javascript">
+/*<+'])');
+ // Function that scans the DOM tree for header elements (the DOM2
+ // nodeIterator API would be a better technique but not supported by all
+ // browsers).
+ var iterate = function (el) {
+ for (var i = el.firstChild; i != null; i = i.nextSibling) {
+ if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
+ var mo = re.exec(i.tagName);
+ if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
+ result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
+ }
+ iterate(i);
+ }
+ }
+ }
+ iterate(el);
+ return result;
+ }
+
+ var toc = document.getElementById("toc");
+ if (!toc) {
+ return;
+ }
+
+ // Delete existing TOC entries in case we're reloading the TOC.
+ var tocEntriesToRemove = [];
+ var i;
+ for (i = 0; i < toc.childNodes.length; i++) {
+ var entry = toc.childNodes[i];
+ if (entry.nodeName.toLowerCase() == 'div'
+ && entry.getAttribute("class")
+ && entry.getAttribute("class").match(/^toclevel/))
+ tocEntriesToRemove.push(entry);
+ }
+ for (i = 0; i < tocEntriesToRemove.length; i++) {
+ toc.removeChild(tocEntriesToRemove[i]);
+ }
+
+ // Rebuild TOC entries.
+ var entries = tocEntries(document.getElementById("content"), toclevels);
+ for (var i = 0; i < entries.length; ++i) {
+ var entry = entries[i];
+ if (entry.element.id == "")
+ entry.element.id = "_toc_" + i;
+ var a = document.createElement("a");
+ a.href = "#" + entry.element.id;
+ a.appendChild(document.createTextNode(entry.text));
+ var div = document.createElement("div");
+ div.appendChild(a);
+ div.className = "toclevel" + entry.toclevel;
+ toc.appendChild(div);
+ }
+ if (entries.length == 0)
+ toc.parentNode.removeChild(toc);
+},
+
+
+/////////////////////////////////////////////////////////////////////
+// Footnotes generator
+/////////////////////////////////////////////////////////////////////
+
+/* Based on footnote generation code from:
+ * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
+ */
+
+footnotes: function () {
+ // Delete existing footnote entries in case we're reloading the footnodes.
+ var i;
+ var noteholder = document.getElementById("footnotes");
+ if (!noteholder) {
+ return;
+ }
+ var entriesToRemove = [];
+ for (i = 0; i < noteholder.childNodes.length; i++) {
+ var entry = noteholder.childNodes[i];
+ if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
+ entriesToRemove.push(entry);
+ }
+ for (i = 0; i < entriesToRemove.length; i++) {
+ noteholder.removeChild(entriesToRemove[i]);
+ }
+
+ // Rebuild footnote entries.
+ var cont = document.getElementById("content");
+ var spans = cont.getElementsByTagName("span");
+ var refs = {};
+ var n = 0;
+ for (i=0; i<spans.length; i++) {
+ if (spans[i].className == "footnote") {
+ n++;
+ var note = spans[i].getAttribute("data-note");
+ if (!note) {
+ // Use [\s\S] in place of . so multi-line matches work.
+ // Because JavaScript has no s (dotall) regex flag.
+ note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
+ spans[i].innerHTML =
+ "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
+ "' title='View footnote' class='footnote'>" + n + "</a>]";
+ spans[i].setAttribute("data-note", note);
+ }
+ noteholder.innerHTML +=
+ "<div class='footnote' id='_footnote_" + n + "'>" +
+ "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
+ n + "</a>. " + note + "</div>";
+ var id =spans[i].getAttribute("id");
+ if (id != null) refs["#"+id] = n;
+ }
+ }
+ if (n == 0)
+ noteholder.parentNode.removeChild(noteholder);
+ else {
+ // Process footnoterefs.
+ for (i=0; i<spans.length; i++) {
+ if (spans[i].className == "footnoteref") {
+ var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
+ href = href.match(/#.*/)[0]; // Because IE return full URL.
+ n = refs[href];
+ spans[i].innerHTML =
+ "[<a href='#_footnote_" + n +
+ "' title='View footnote' class='footnote'>" + n + "</a>]";
+ }
+ }
+ }
+},
+
+install: function(toclevels) {
+ var timerId;
+
+ function reinstall() {
+ asciidoc.footnotes();
+ if (toclevels) {
+ asciidoc.toc(toclevels);
+ }
+ }
+
+ function reinstallAndRemoveTimer() {
+ clearInterval(timerId);
+ reinstall();
+ }
+
+ timerId = setInterval(reinstall, 500);
+ if (document.addEventListener)
+ document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
+ else
+ window.onload = reinstallAndRemoveTimer;
+}
+
+}
+asciidoc.install();
+/*]]>*/
+</script>
+</head>
+<body class="article">
+<div id="header">
+<h1>GIT bitmap v1 format</h1>
+</div>
+<div id="content">
+<div class="sect1">
+<h2 id="_pack_and_multi_pack_bitmaps">Pack and multi-pack bitmaps</h2>
+<div class="sectionbody">
+<div class="paragraph"><p>Bitmaps store reachability information about the set of objects in a packfile,
+or a multi-pack index (MIDX). The former is defined obviously, and the latter is
+defined as the union of objects in packs contained in the MIDX.</p></div>
+<div class="paragraph"><p>A bitmap may belong to either one pack, or the repository’s multi-pack index (if
+it exists). A repository may have at most one bitmap.</p></div>
+<div class="paragraph"><p>An object is uniquely described by its bit position within a bitmap:</p></div>
+<div class="ulist"><ul>
+<li>
+<p>
+If the bitmap belongs to a packfile, the <em>n</em>th bit corresponds to
+ the <em>n</em>th object in pack order. For a function <code>offset</code> which maps
+ objects to their byte offset within a pack, pack order is defined as
+ follows:
+</p>
+<div class="literalblock">
+<div class="content">
+<pre><code>o1 <= o2 <==> offset(o1) <= offset(o2)</code></pre>
+</div></div>
+</li>
+<li>
+<p>
+If the bitmap belongs to a MIDX, the <em>n</em>th bit corresponds to the
+ <em>n</em>th object in MIDX order. With an additional function <code>pack</code> which
+ maps objects to the pack they were selected from by the MIDX, MIDX order
+ is defined as follows:
+</p>
+<div class="literalblock">
+<div class="content">
+<pre><code>o1 <= o2 <==> pack(o1) <= pack(o2) /\ offset(o1) <= offset(o2)</code></pre>
+</div></div>
+<div class="paragraph"><p>The ordering between packs is done according to the MIDX’s .rev file.
+Notably, the preferred pack sorts ahead of all other packs.</p></div>
+</li>
+</ul></div>
+<div class="paragraph"><p>The on-disk representation (described below) of a bitmap is the same regardless
+of whether or not that bitmap belongs to a packfile or a MIDX. The only
+difference is the interpretation of the bits, which is described above.</p></div>
+<div class="paragraph"><p>Certain bitmap extensions are supported (see: Appendix B). No extensions are
+required for bitmaps corresponding to packfiles. For bitmaps that correspond to
+MIDXs, both the bit-cache and rev-cache extensions are required.</p></div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_on_disk_format">On-disk format</h2>
+<div class="sectionbody">
+<div class="ulist"><ul>
+<li>
+<p>
+A header appears at the beginning:
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+4-byte signature:
+</dt>
+<dd>
+<p>
+{<em>B</em>, <em>I</em>, <em>T</em>, <em>M</em>}
+</p>
+</dd>
+<dt class="hdlist1">
+2-byte version number (network byte order):
+</dt>
+<dd>
+<p>
+ The current implementation only supports version 1
+ of the bitmap index (the same one as JGit).
+</p>
+</dd>
+<dt class="hdlist1">
+2-byte flags (network byte order):
+</dt>
+<dd>
+<p>
+ The following flags are supported:
+</p>
+<div class="ulist"><ul>
+<li>
+<p>
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+BITMAP_OPT_FULL_DAG (0x1) REQUIRED:
+</dt>
+<dd>
+<p>
+ This flag must always be present. It implies that the
+ bitmap index has been generated for a packfile or
+ multi-pack index (MIDX) with full closure (i.e. where
+ every single object in the packfile/MIDX can find its
+ parent links inside the same packfile/MIDX). This is a
+ requirement for the bitmap index format, also present in
+ JGit, that greatly reduces the complexity of the
+ implementation.
+</p>
+</dd>
+</dl></div>
+</li>
+<li>
+<p>
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+BITMAP_OPT_HASH_CACHE (0x4):
+</dt>
+<dd>
+<p>
+ If present, the end of the bitmap file contains
+ <code>N</code> 32-bit name-hash values, one per object in the
+ pack/MIDX. The format and meaning of the name-hash is
+ described below.
+</p>
+</dd>
+</dl></div>
+</li>
+</ul></div>
+</dd>
+<dt class="hdlist1">
+4-byte entry count (network byte order):
+</dt>
+<dd>
+<p>
+ The total count of entries (bitmapped commits) in this bitmap index.
+</p>
+</dd>
+<dt class="hdlist1">
+20-byte checksum:
+</dt>
+<dd>
+<p>
+ The SHA1 checksum of the pack/MIDX this bitmap index
+ belongs to.
+</p>
+</dd>
+</dl></div>
+</li>
+<li>
+<p>
+4 EWAH bitmaps that act as type indexes
+</p>
+<div class="paragraph"><p>Type indexes are serialized after the hash cache in the shape
+of four EWAH bitmaps stored consecutively (see Appendix A for
+the serialization format of an EWAH bitmap).</p></div>
+<div class="paragraph"><p>There is a bitmap for each Git object type, stored in the following
+order:</p></div>
+<div class="ulist"><ul>
+<li>
+<p>
+Commits
+</p>
+</li>
+<li>
+<p>
+Trees
+</p>
+</li>
+<li>
+<p>
+Blobs
+</p>
+</li>
+<li>
+<p>
+Tags
+</p>
+</li>
+</ul></div>
+<div class="paragraph"><p>In each bitmap, the `n`th bit is set to true if the `n`th object
+in the packfile or multi-pack index is of that type.</p></div>
+<div class="paragraph"><p>The obvious consequence is that the OR of all 4 bitmaps will result
+in a full set (all bits set), and the AND of all 4 bitmaps will
+result in an empty bitmap (no bits set).</p></div>
+</li>
+<li>
+<p>
+N entries with compressed bitmaps, one for each indexed commit
+</p>
+<div class="paragraph"><p>Where <code>N</code> is the total amount of entries in this bitmap index.
+Each entry contains the following:</p></div>
+<div class="ulist"><ul>
+<li>
+<p>
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+4-byte object position (network byte order):
+</dt>
+<dd>
+<p>
+ The position <strong>in the index for the packfile or
+ multi-pack index</strong> where the bitmap for this commit is
+ found.
+</p>
+</dd>
+</dl></div>
+</li>
+<li>
+<p>
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+1-byte XOR-offset:
+</dt>
+<dd>
+<p>
+ The xor offset used to compress this bitmap. For an entry
+ in position <code>x</code>, a XOR offset of <code>y</code> means that the actual
+ bitmap representing this commit is composed by XORing the
+ bitmap for this entry with the bitmap in entry <code>x-y</code> (i.e.
+ the bitmap <code>y</code> entries before this one).
+</p>
+<div class="admonitionblock">
+<table><tr>
+<td class="icon">
+<div class="title">Note</div>
+</td>
+<td class="content">This compression can be recursive. In order to
+XOR this entry with a previous one, the previous entry needs
+to be decompressed first, and so on.</td>
+</tr></table>
+</div>
+<div class="paragraph"><p>The hard-limit for this offset is 160 (an entry can only be
+xor’ed against one of the 160 entries preceding it). This
+number is always positive, and hence entries are always xor’ed
+with <strong>previous</strong> bitmaps, not bitmaps that will come afterwards
+in the index.</p></div>
+</dd>
+</dl></div>
+</li>
+<li>
+<p>
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+1-byte flags for this bitmap:
+</dt>
+<dd>
+<p>
+ At the moment the only available flag is <code>0x1</code>, which hints
+ that this bitmap can be re-used when rebuilding bitmap indexes
+ for the repository.
+</p>
+</dd>
+</dl></div>
+</li>
+<li>
+<p>
+The compressed bitmap itself, see Appendix A.
+</p>
+</li>
+</ul></div>
+</li>
+<li>
+<p>
+</p>
+<div class="dlist"><dl>
+<dt class="hdlist1">
+TRAILER:
+</dt>
+<dd>
+<p>
+ Trailing checksum of the preceding contents.
+</p>
+</dd>
+</dl></div>
+</li>
+</ul></div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_appendix_a_serialization_format_for_an_ewah_bitmap">Appendix A: Serialization format for an EWAH bitmap</h2>
+<div class="sectionbody">
+<div class="paragraph"><p>Ewah bitmaps are serialized in the same protocol as the JAVAEWAH
+library, making them backwards compatible with the JGit
+implementation:</p></div>
+<div class="ulist"><ul>
+<li>
+<p>
+4-byte number of bits of the resulting UNCOMPRESSED bitmap
+</p>
+</li>
+<li>
+<p>
+4-byte number of words of the COMPRESSED bitmap, when stored
+</p>
+</li>
+<li>
+<p>
+N x 8-byte words, as specified by the previous field
+</p>
+<div class="paragraph"><p>This is the actual content of the compressed bitmap.</p></div>
+</li>
+<li>
+<p>
+4-byte position of the current RLW for the compressed
+ bitmap
+</p>
+</li>
+</ul></div>
+<div class="paragraph"><p>All words are stored in network byte order for their corresponding
+sizes.</p></div>
+<div class="paragraph"><p>The compressed bitmap is stored in a form of run-length encoding, as
+follows. It consists of a concatenation of an arbitrary number of
+chunks. Each chunk consists of one or more 64-bit words</p></div>
+<div class="literalblock">
+<div class="content">
+<pre><code>H L_1 L_2 L_3 .... L_M</code></pre>
+</div></div>
+<div class="paragraph"><p>H is called RLW (run length word). It consists of (from lower to higher
+order bits):</p></div>
+<div class="ulist"><ul>
+<li>
+<p>
+1 bit: the repeated bit B
+</p>
+</li>
+<li>
+<p>
+32 bits: repetition count K (unsigned)
+</p>
+</li>
+<li>
+<p>
+31 bits: literal word count M (unsigned)
+</p>
+</li>
+</ul></div>
+<div class="paragraph"><p>The bitstream represented by the above chunk is then:</p></div>
+<div class="ulist"><ul>
+<li>
+<p>
+K repetitions of B
+</p>
+</li>
+<li>
+<p>
+The bits stored in <code>L_1</code> through <code>L_M</code>. Within a word, bits at
+ lower order come earlier in the stream than those at higher
+ order.
+</p>
+</li>
+</ul></div>
+<div class="paragraph"><p>The next word after <code>L_M</code> (if any) must again be a RLW, for the next
+chunk. For efficient appending to the bitstream, the EWAH stores a
+pointer to the last RLW in the stream.</p></div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_appendix_b_optional_bitmap_sections">Appendix B: Optional Bitmap Sections</h2>
+<div class="sectionbody">
+<div class="paragraph"><p>These sections may or may not be present in the <code>.bitmap</code> file; their
+presence is indicated by the header flags section described above.</p></div>
+</div>
+</div>
+<div class="sect1">
+<h2 id="_name_hash_cache">Name-hash cache</h2>
+<div class="sectionbody">
+<div class="paragraph"><p>If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains
+a cache of 32-bit values, one per object in the pack/MIDX. The value at
+position <code>i</code> is the hash of the pathname at which the `i`th object
+(counting in index or multi-pack index order) in the pack/MIDX can be found.
+This can be fed into the delta heuristics to compare objects with similar
+pathnames.</p></div>
+<div class="paragraph"><p>The hash algorithm used is:</p></div>
+<div class="literalblock">
+<div class="content">
+<pre><code>hash = 0;
+while ((c = *name++))
+ if (!isspace(c))
+ hash = (hash >> 2) + (c << 24);</code></pre>
+</div></div>
+<div class="paragraph"><p>Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
+If implementations want to choose a different hashing scheme, they are
+free to do so, but MUST allocate a new header flag (because comparing
+hashes made under two different schemes would be pointless).</p></div>
+</div>
+</div>
+</div>
+<div id="footnotes"><hr /></div>
+<div id="footer">
+<div id="footer-text">
+Last updated
+ 2022-07-11 16:06:18 PDT
+</div>
+</div>
+</body>
+</html>
diff --git a/technical/bitmap-format.txt b/technical/bitmap-format.txt index 04b3ec217..a85f58f51 100644 --- a/technical/bitmap-format.txt +++ b/technical/bitmap-format.txt @@ -25,9 +25,9 @@ An object is uniquely described by its bit position within a bitmap: is defined as follows: o1 <= o2 <==> pack(o1) <= pack(o2) /\ offset(o1) <= offset(o2) - - The ordering between packs is done according to the MIDX's .rev file. - Notably, the preferred pack sorts ahead of all other packs. ++ +The ordering between packs is done according to the MIDX's .rev file. +Notably, the preferred pack sorts ahead of all other packs. The on-disk representation (described below) of a bitmap is the same regardless of whether or not that bitmap belongs to a packfile or a MIDX. The only @@ -39,97 +39,108 @@ MIDXs, both the bit-cache and rev-cache extensions are required. == On-disk format - - A header appears at the beginning: - - 4-byte signature: {'B', 'I', 'T', 'M'} - - 2-byte version number (network byte order) - The current implementation only supports version 1 - of the bitmap index (the same one as JGit). - - 2-byte flags (network byte order) - - The following flags are supported: - - - BITMAP_OPT_FULL_DAG (0x1) REQUIRED - This flag must always be present. It implies that the - bitmap index has been generated for a packfile or - multi-pack index (MIDX) with full closure (i.e. where - every single object in the packfile/MIDX can find its - parent links inside the same packfile/MIDX). This is a - requirement for the bitmap index format, also present in - JGit, that greatly reduces the complexity of the - implementation. - - - BITMAP_OPT_HASH_CACHE (0x4) - If present, the end of the bitmap file contains - `N` 32-bit name-hash values, one per object in the - pack/MIDX. The format and meaning of the name-hash is - described below. - - 4-byte entry count (network byte order) - - The total count of entries (bitmapped commits) in this bitmap index. - - 20-byte checksum - - The SHA1 checksum of the pack/MIDX this bitmap index - belongs to. - - - 4 EWAH bitmaps that act as type indexes - - Type indexes are serialized after the hash cache in the shape - of four EWAH bitmaps stored consecutively (see Appendix A for - the serialization format of an EWAH bitmap). - - There is a bitmap for each Git object type, stored in the following - order: - - - Commits - - Trees - - Blobs - - Tags - - In each bitmap, the `n`th bit is set to true if the `n`th object - in the packfile or multi-pack index is of that type. - - The obvious consequence is that the OR of all 4 bitmaps will result - in a full set (all bits set), and the AND of all 4 bitmaps will - result in an empty bitmap (no bits set). - - - N entries with compressed bitmaps, one for each indexed commit - - Where `N` is the total amount of entries in this bitmap index. - Each entry contains the following: - - - 4-byte object position (network byte order) - The position **in the index for the packfile or - multi-pack index** where the bitmap for this commit is - found. - - - 1-byte XOR-offset - The xor offset used to compress this bitmap. For an entry - in position `x`, a XOR offset of `y` means that the actual - bitmap representing this commit is composed by XORing the - bitmap for this entry with the bitmap in entry `x-y` (i.e. - the bitmap `y` entries before this one). - - Note that this compression can be recursive. In order to - XOR this entry with a previous one, the previous entry needs - to be decompressed first, and so on. - - The hard-limit for this offset is 160 (an entry can only be - xor'ed against one of the 160 entries preceding it). This - number is always positive, and hence entries are always xor'ed - with **previous** bitmaps, not bitmaps that will come afterwards - in the index. - - - 1-byte flags for this bitmap - At the moment the only available flag is `0x1`, which hints - that this bitmap can be re-used when rebuilding bitmap indexes - for the repository. - - - The compressed bitmap itself, see Appendix A. + * A header appears at the beginning: + + 4-byte signature: :: {'B', 'I', 'T', 'M'} + + 2-byte version number (network byte order): :: + + The current implementation only supports version 1 + of the bitmap index (the same one as JGit). + + 2-byte flags (network byte order): :: + + The following flags are supported: + + ** {empty} + BITMAP_OPT_FULL_DAG (0x1) REQUIRED: ::: + + This flag must always be present. It implies that the + bitmap index has been generated for a packfile or + multi-pack index (MIDX) with full closure (i.e. where + every single object in the packfile/MIDX can find its + parent links inside the same packfile/MIDX). This is a + requirement for the bitmap index format, also present in + JGit, that greatly reduces the complexity of the + implementation. + + ** {empty} + BITMAP_OPT_HASH_CACHE (0x4): ::: + + If present, the end of the bitmap file contains + `N` 32-bit name-hash values, one per object in the + pack/MIDX. The format and meaning of the name-hash is + described below. + + 4-byte entry count (network byte order): :: + The total count of entries (bitmapped commits) in this bitmap index. + + 20-byte checksum: :: + The SHA1 checksum of the pack/MIDX this bitmap index + belongs to. + + * 4 EWAH bitmaps that act as type indexes ++ +Type indexes are serialized after the hash cache in the shape +of four EWAH bitmaps stored consecutively (see Appendix A for +the serialization format of an EWAH bitmap). ++ +There is a bitmap for each Git object type, stored in the following +order: ++ + - Commits + - Trees + - Blobs + - Tags + ++ +In each bitmap, the `n`th bit is set to true if the `n`th object +in the packfile or multi-pack index is of that type. ++ +The obvious consequence is that the OR of all 4 bitmaps will result +in a full set (all bits set), and the AND of all 4 bitmaps will +result in an empty bitmap (no bits set). + + * N entries with compressed bitmaps, one for each indexed commit ++ +Where `N` is the total amount of entries in this bitmap index. +Each entry contains the following: + + ** {empty} + 4-byte object position (network byte order): :: + The position **in the index for the packfile or + multi-pack index** where the bitmap for this commit is + found. + + ** {empty} + 1-byte XOR-offset: :: + The xor offset used to compress this bitmap. For an entry + in position `x`, a XOR offset of `y` means that the actual + bitmap representing this commit is composed by XORing the + bitmap for this entry with the bitmap in entry `x-y` (i.e. + the bitmap `y` entries before this one). ++ +NOTE: This compression can be recursive. In order to +XOR this entry with a previous one, the previous entry needs +to be decompressed first, and so on. ++ +The hard-limit for this offset is 160 (an entry can only be +xor'ed against one of the 160 entries preceding it). This +number is always positive, and hence entries are always xor'ed +with **previous** bitmaps, not bitmaps that will come afterwards +in the index. + + ** {empty} + 1-byte flags for this bitmap: :: + At the moment the only available flag is `0x1`, which hints + that this bitmap can be re-used when rebuilding bitmap indexes + for the repository. + + ** The compressed bitmap itself, see Appendix A. + + * {empty} + TRAILER: :: + Trailing checksum of the preceding contents. == Appendix A: Serialization format for an EWAH bitmap @@ -142,8 +153,8 @@ implementation: - 4-byte number of words of the COMPRESSED bitmap, when stored - N x 8-byte words, as specified by the previous field - - This is the actual content of the compressed bitmap. ++ +This is the actual content of the compressed bitmap. - 4-byte position of the current RLW for the compressed bitmap |