Google Git
Sign in
chromium / external / gitster / git-htmldocs / 472c81a0f3cf8038d39479da1e3840ac33fe6ef8 / . / technical / bitmap-format.html
blob: 064d14f25d5f69ff7db79d7e636fe5ceb23b4814 [file] [log] [blame]
Junio C Hamano7bc73592022-07-11 23:08:34[diff] [blame]1<?xml version="1.0" encoding="UTF-8"?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
3 "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
4<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
5<head>
6<meta http-equiv="Content-Type" content="application/xhtml+xml; charset=UTF-8" />
Junio C Hamanoa85030a2022-07-27 16:48:21[diff] [blame]7<meta name="generator" content="AsciiDoc 10.2.0" />
Junio C Hamano7bc73592022-07-11 23:08:34[diff] [blame]8<title>GIT bitmap v1 format</title>
9<style type="text/css">
10/* Shared CSS for AsciiDoc xhtml11 and html5 backends */
11
12/* Default font. */
13body {
14 font-family: Georgia,serif;
15}
16
17/* Title font. */
18h1, h2, h3, h4, h5, h6,
19div.title, caption.title,
20thead, p.table.header,
21#toctitle,
22#author, #revnumber, #revdate, #revremark,
23#footer {
24 font-family: Arial,Helvetica,sans-serif;
25}
26
27body {
28 margin: 1em 5% 1em 5%;
29}
30
31a {
32 color: blue;
33 text-decoration: underline;
34}
35a:visited {
36 color: fuchsia;
37}
38
39em {
40 font-style: italic;
41 color: navy;
42}
43
44strong {
45 font-weight: bold;
46 color: #083194;
47}
48
49h1, h2, h3, h4, h5, h6 {
50 color: #527bbd;
51 margin-top: 1.2em;
52 margin-bottom: 0.5em;
53 line-height: 1.3;
54}
55
56h1, h2, h3 {
57 border-bottom: 2px solid silver;
58}
59h2 {
60 padding-top: 0.5em;
61}
62h3 {
63 float: left;
64}
65h3 + * {
66 clear: left;
67}
68h5 {
69 font-size: 1.0em;
70}
71
72div.sectionbody {
73 margin-left: 0;
74}
75
76hr {
77 border: 1px solid silver;
78}
79
80p {
81 margin-top: 0.5em;
82 margin-bottom: 0.5em;
83}
84
85ul, ol, li > p {
86 margin-top: 0;
87}
88ul > li { color: #aaa; }
89ul > li > * { color: black; }
90
91.monospaced, code, pre {
92 font-family: "Courier New", Courier, monospace;
93 font-size: inherit;
94 color: navy;
95 padding: 0;
96 margin: 0;
97}
98pre {
99 white-space: pre-wrap;
100}
101
102#author {
103 color: #527bbd;
104 font-weight: bold;
105 font-size: 1.1em;
106}
107#email {
108}
109#revnumber, #revdate, #revremark {
110}
111
112#footer {
113 font-size: small;
114 border-top: 2px solid silver;
115 padding-top: 0.5em;
116 margin-top: 4.0em;
117}
118#footer-text {
119 float: left;
120 padding-bottom: 0.5em;
121}
122#footer-badges {
123 float: right;
124 padding-bottom: 0.5em;
125}
126
127#preamble {
128 margin-top: 1.5em;
129 margin-bottom: 1.5em;
130}
131div.imageblock, div.exampleblock, div.verseblock,
132div.quoteblock, div.literalblock, div.listingblock, div.sidebarblock,
133div.admonitionblock {
134 margin-top: 1.0em;
135 margin-bottom: 1.5em;
136}
137div.admonitionblock {
138 margin-top: 2.0em;
139 margin-bottom: 2.0em;
140 margin-right: 10%;
141 color: #606060;
142}
143
144div.content { /* Block element content. */
145 padding: 0;
146}
147
148/* Block element titles. */
149div.title, caption.title {
150 color: #527bbd;
151 font-weight: bold;
152 text-align: left;
153 margin-top: 1.0em;
154 margin-bottom: 0.5em;
155}
156div.title + * {
157 margin-top: 0;
158}
159
160td div.title:first-child {
161 margin-top: 0.0em;
162}
163div.content div.title:first-child {
164 margin-top: 0.0em;
165}
166div.content + div.title {
167 margin-top: 0.0em;
168}
169
170div.sidebarblock > div.content {
171 background: #ffffee;
172 border: 1px solid #dddddd;
173 border-left: 4px solid #f0f0f0;
174 padding: 0.5em;
175}
176
177div.listingblock > div.content {
178 border: 1px solid #dddddd;
179 border-left: 5px solid #f0f0f0;
180 background: #f8f8f8;
181 padding: 0.5em;
182}
183
184div.quoteblock, div.verseblock {
185 padding-left: 1.0em;
186 margin-left: 1.0em;
187 margin-right: 10%;
188 border-left: 5px solid #f0f0f0;
189 color: #888;
190}
191
192div.quoteblock > div.attribution {
193 padding-top: 0.5em;
194 text-align: right;
195}
196
197div.verseblock > pre.content {
198 font-family: inherit;
199 font-size: inherit;
200}
201div.verseblock > div.attribution {
202 padding-top: 0.75em;
203 text-align: left;
204}
205/* DEPRECATED: Pre version 8.2.7 verse style literal block. */
206div.verseblock + div.attribution {
207 text-align: left;
208}
209
210div.admonitionblock .icon {
211 vertical-align: top;
212 font-size: 1.1em;
213 font-weight: bold;
214 text-decoration: underline;
215 color: #527bbd;
216 padding-right: 0.5em;
217}
218div.admonitionblock td.content {
219 padding-left: 0.5em;
220 border-left: 3px solid #dddddd;
221}
222
223div.exampleblock > div.content {
224 border-left: 3px solid #dddddd;
225 padding-left: 0.5em;
226}
227
228div.imageblock div.content { padding-left: 0; }
229span.image img { border-style: none; vertical-align: text-bottom; }
230a.image:visited { color: white; }
231
232dl {
233 margin-top: 0.8em;
234 margin-bottom: 0.8em;
235}
236dt {
237 margin-top: 0.5em;
238 margin-bottom: 0;
239 font-style: normal;
240 color: navy;
241}
242dd > *:first-child {
243 margin-top: 0.1em;
244}
245
246ul, ol {
247 list-style-position: outside;
248}
249ol.arabic {
250 list-style-type: decimal;
251}
252ol.loweralpha {
253 list-style-type: lower-alpha;
254}
255ol.upperalpha {
256 list-style-type: upper-alpha;
257}
258ol.lowerroman {
259 list-style-type: lower-roman;
260}
261ol.upperroman {
262 list-style-type: upper-roman;
263}
264
265div.compact ul, div.compact ol,
266div.compact p, div.compact p,
267div.compact div, div.compact div {
268 margin-top: 0.1em;
269 margin-bottom: 0.1em;
270}
271
272tfoot {
273 font-weight: bold;
274}
275td > div.verse {
276 white-space: pre;
277}
278
279div.hdlist {
280 margin-top: 0.8em;
281 margin-bottom: 0.8em;
282}
283div.hdlist tr {
284 padding-bottom: 15px;
285}
286dt.hdlist1.strong, td.hdlist1.strong {
287 font-weight: bold;
288}
289td.hdlist1 {
290 vertical-align: top;
291 font-style: normal;
292 padding-right: 0.8em;
293 color: navy;
294}
295td.hdlist2 {
296 vertical-align: top;
297}
298div.hdlist.compact tr {
299 margin: 0;
300 padding-bottom: 0;
301}
302
303.comment {
304 background: yellow;
305}
306
307.footnote, .footnoteref {
308 font-size: 0.8em;
309}
310
311span.footnote, span.footnoteref {
312 vertical-align: super;
313}
314
315#footnotes {
316 margin: 20px 0 20px 0;
317 padding: 7px 0 0 0;
318}
319
320#footnotes div.footnote {
321 margin: 0 0 5px 0;
322}
323
324#footnotes hr {
325 border: none;
326 border-top: 1px solid silver;
327 height: 1px;
328 text-align: left;
329 margin-left: 0;
330 width: 20%;
331 min-width: 100px;
332}
333
334div.colist td {
335 padding-right: 0.5em;
336 padding-bottom: 0.3em;
337 vertical-align: top;
338}
339div.colist td img {
340 margin-top: 0.3em;
341}
342
343@media print {
344 #footer-badges { display: none; }
345}
346
347#toc {
348 margin-bottom: 2.5em;
349}
350
351#toctitle {
352 color: #527bbd;
353 font-size: 1.1em;
354 font-weight: bold;
355 margin-top: 1.0em;
356 margin-bottom: 0.1em;
357}
358
359div.toclevel0, div.toclevel1, div.toclevel2, div.toclevel3, div.toclevel4 {
360 margin-top: 0;
361 margin-bottom: 0;
362}
363div.toclevel2 {
364 margin-left: 2em;
365 font-size: 0.9em;
366}
367div.toclevel3 {
368 margin-left: 4em;
369 font-size: 0.9em;
370}
371div.toclevel4 {
372 margin-left: 6em;
373 font-size: 0.9em;
374}
375
376span.aqua { color: aqua; }
377span.black { color: black; }
378span.blue { color: blue; }
379span.fuchsia { color: fuchsia; }
380span.gray { color: gray; }
381span.green { color: green; }
382span.lime { color: lime; }
383span.maroon { color: maroon; }
384span.navy { color: navy; }
385span.olive { color: olive; }
386span.purple { color: purple; }
387span.red { color: red; }
388span.silver { color: silver; }
389span.teal { color: teal; }
390span.white { color: white; }
391span.yellow { color: yellow; }
392
393span.aqua-background { background: aqua; }
394span.black-background { background: black; }
395span.blue-background { background: blue; }
396span.fuchsia-background { background: fuchsia; }
397span.gray-background { background: gray; }
398span.green-background { background: green; }
399span.lime-background { background: lime; }
400span.maroon-background { background: maroon; }
401span.navy-background { background: navy; }
402span.olive-background { background: olive; }
403span.purple-background { background: purple; }
404span.red-background { background: red; }
405span.silver-background { background: silver; }
406span.teal-background { background: teal; }
407span.white-background { background: white; }
408span.yellow-background { background: yellow; }
409
410span.big { font-size: 2em; }
411span.small { font-size: 0.6em; }
412
413span.underline { text-decoration: underline; }
414span.overline { text-decoration: overline; }
415span.line-through { text-decoration: line-through; }
416
417div.unbreakable { page-break-inside: avoid; }
418
419
420/*
421 * xhtml11 specific
422 *
423 * */
424
425div.tableblock {
426 margin-top: 1.0em;
427 margin-bottom: 1.5em;
428}
429div.tableblock > table {
430 border: 3px solid #527bbd;
431}
432thead, p.table.header {
433 font-weight: bold;
434 color: #527bbd;
435}
436p.table {
437 margin-top: 0;
438}
439/* Because the table frame attribute is overridden by CSS in most browsers. */
440div.tableblock > table[frame="void"] {
441 border-style: none;
442}
443div.tableblock > table[frame="hsides"] {
444 border-left-style: none;
445 border-right-style: none;
446}
447div.tableblock > table[frame="vsides"] {
448 border-top-style: none;
449 border-bottom-style: none;
450}
451
452
453/*
454 * html5 specific
455 *
456 * */
457
458table.tableblock {
459 margin-top: 1.0em;
460 margin-bottom: 1.5em;
461}
462thead, p.tableblock.header {
463 font-weight: bold;
464 color: #527bbd;
465}
466p.tableblock {
467 margin-top: 0;
468}
469table.tableblock {
470 border-width: 3px;
471 border-spacing: 0px;
472 border-style: solid;
473 border-color: #527bbd;
474 border-collapse: collapse;
475}
476th.tableblock, td.tableblock {
477 border-width: 1px;
478 padding: 4px;
479 border-style: solid;
480 border-color: #527bbd;
481}
482
483table.tableblock.frame-topbot {
484 border-left-style: hidden;
485 border-right-style: hidden;
486}
487table.tableblock.frame-sides {
488 border-top-style: hidden;
489 border-bottom-style: hidden;
490}
491table.tableblock.frame-none {
492 border-style: hidden;
493}
494
495th.tableblock.halign-left, td.tableblock.halign-left {
496 text-align: left;
497}
498th.tableblock.halign-center, td.tableblock.halign-center {
499 text-align: center;
500}
501th.tableblock.halign-right, td.tableblock.halign-right {
502 text-align: right;
503}
504
505th.tableblock.valign-top, td.tableblock.valign-top {
506 vertical-align: top;
507}
508th.tableblock.valign-middle, td.tableblock.valign-middle {
509 vertical-align: middle;
510}
511th.tableblock.valign-bottom, td.tableblock.valign-bottom {
512 vertical-align: bottom;
513}
514
515
516/*
517 * manpage specific
518 *
519 * */
520
521body.manpage h1 {
522 padding-top: 0.5em;
523 padding-bottom: 0.5em;
524 border-top: 2px solid silver;
525 border-bottom: 2px solid silver;
526}
527body.manpage h2 {
528 border-style: none;
529}
530body.manpage div.sectionbody {
531 margin-left: 3em;
532}
533
534@media print {
535 body.manpage div#toc { display: none; }
536}
537
538
539</style>
540<script type="text/javascript">
541/*<![CDATA[*/
542var asciidoc = { // Namespace.
543
544/////////////////////////////////////////////////////////////////////
545// Table Of Contents generator
546/////////////////////////////////////////////////////////////////////
547
548/* Author: Mihai Bazon, September 2002
549 * http://students.infoiasi.ro/~mishoo
550 *
551 * Table Of Content generator
552 * Version: 0.4
553 *
554 * Feel free to use this script under the terms of the GNU General Public
555 * License, as long as you do not remove or alter this notice.
556 */
557
558 /* modified by Troy D. Hanson, September 2006. License: GPL */
559 /* modified by Stuart Rackham, 2006, 2009. License: GPL */
560
561// toclevels = 1..4.
562toc: function (toclevels) {
563
564 function getText(el) {
565 var text = "";
566 for (var i = el.firstChild; i != null; i = i.nextSibling) {
567 if (i.nodeType == 3 /* Node.TEXT_NODE */) // IE doesn't speak constants.
568 text += i.data;
569 else if (i.firstChild != null)
570 text += getText(i);
571 }
572 return text;
573 }
574
575 function TocEntry(el, text, toclevel) {
576 this.element = el;
577 this.text = text;
578 this.toclevel = toclevel;
579 }
580
581 function tocEntries(el, toclevels) {
582 var result = new Array;
583 var re = new RegExp('[hH]([1-'+(toclevels+1)+'])');
584 // Function that scans the DOM tree for header elements (the DOM2
585 // nodeIterator API would be a better technique but not supported by all
586 // browsers).
587 var iterate = function (el) {
588 for (var i = el.firstChild; i != null; i = i.nextSibling) {
589 if (i.nodeType == 1 /* Node.ELEMENT_NODE */) {
590 var mo = re.exec(i.tagName);
591 if (mo && (i.getAttribute("class") || i.getAttribute("className")) != "float") {
592 result[result.length] = new TocEntry(i, getText(i), mo[1]-1);
593 }
594 iterate(i);
595 }
596 }
597 }
598 iterate(el);
599 return result;
600 }
601
602 var toc = document.getElementById("toc");
603 if (!toc) {
604 return;
605 }
606
607 // Delete existing TOC entries in case we're reloading the TOC.
608 var tocEntriesToRemove = [];
609 var i;
610 for (i = 0; i < toc.childNodes.length; i++) {
611 var entry = toc.childNodes[i];
612 if (entry.nodeName.toLowerCase() == 'div'
613 && entry.getAttribute("class")
614 && entry.getAttribute("class").match(/^toclevel/))
615 tocEntriesToRemove.push(entry);
616 }
617 for (i = 0; i < tocEntriesToRemove.length; i++) {
618 toc.removeChild(tocEntriesToRemove[i]);
619 }
620
621 // Rebuild TOC entries.
622 var entries = tocEntries(document.getElementById("content"), toclevels);
623 for (var i = 0; i < entries.length; ++i) {
624 var entry = entries[i];
625 if (entry.element.id == "")
626 entry.element.id = "_toc_" + i;
627 var a = document.createElement("a");
628 a.href = "#" + entry.element.id;
629 a.appendChild(document.createTextNode(entry.text));
630 var div = document.createElement("div");
631 div.appendChild(a);
632 div.className = "toclevel" + entry.toclevel;
633 toc.appendChild(div);
634 }
635 if (entries.length == 0)
636 toc.parentNode.removeChild(toc);
637},
638
639
640/////////////////////////////////////////////////////////////////////
641// Footnotes generator
642/////////////////////////////////////////////////////////////////////
643
644/* Based on footnote generation code from:
645 * http://www.brandspankingnew.net/archive/2005/07/format_footnote.html
646 */
647
648footnotes: function () {
649 // Delete existing footnote entries in case we're reloading the footnodes.
650 var i;
651 var noteholder = document.getElementById("footnotes");
652 if (!noteholder) {
653 return;
654 }
655 var entriesToRemove = [];
656 for (i = 0; i < noteholder.childNodes.length; i++) {
657 var entry = noteholder.childNodes[i];
658 if (entry.nodeName.toLowerCase() == 'div' && entry.getAttribute("class") == "footnote")
659 entriesToRemove.push(entry);
660 }
661 for (i = 0; i < entriesToRemove.length; i++) {
662 noteholder.removeChild(entriesToRemove[i]);
663 }
664
665 // Rebuild footnote entries.
666 var cont = document.getElementById("content");
667 var spans = cont.getElementsByTagName("span");
668 var refs = {};
669 var n = 0;
670 for (i=0; i<spans.length; i++) {
671 if (spans[i].className == "footnote") {
672 n++;
673 var note = spans[i].getAttribute("data-note");
674 if (!note) {
675 // Use [\s\S] in place of . so multi-line matches work.
676 // Because JavaScript has no s (dotall) regex flag.
677 note = spans[i].innerHTML.match(/\s*\[([\s\S]*)]\s*/)[1];
678 spans[i].innerHTML =
679 "[<a id='_footnoteref_" + n + "' href='#_footnote_" + n +
680 "' title='View footnote' class='footnote'>" + n + "</a>]";
681 spans[i].setAttribute("data-note", note);
682 }
683 noteholder.innerHTML +=
684 "<div class='footnote' id='_footnote_" + n + "'>" +
685 "<a href='#_footnoteref_" + n + "' title='Return to text'>" +
686 n + "</a>. " + note + "</div>";
687 var id =spans[i].getAttribute("id");
688 if (id != null) refs["#"+id] = n;
689 }
690 }
691 if (n == 0)
692 noteholder.parentNode.removeChild(noteholder);
693 else {
694 // Process footnoterefs.
695 for (i=0; i<spans.length; i++) {
696 if (spans[i].className == "footnoteref") {
697 var href = spans[i].getElementsByTagName("a")[0].getAttribute("href");
698 href = href.match(/#.*/)[0]; // Because IE return full URL.
699 n = refs[href];
700 spans[i].innerHTML =
701 "[<a href='#_footnote_" + n +
702 "' title='View footnote' class='footnote'>" + n + "</a>]";
703 }
704 }
705 }
706},
707
708install: function(toclevels) {
709 var timerId;
710
711 function reinstall() {
712 asciidoc.footnotes();
713 if (toclevels) {
714 asciidoc.toc(toclevels);
715 }
716 }
717
718 function reinstallAndRemoveTimer() {
719 clearInterval(timerId);
720 reinstall();
721 }
722
723 timerId = setInterval(reinstall, 500);
724 if (document.addEventListener)
725 document.addEventListener("DOMContentLoaded", reinstallAndRemoveTimer, false);
726 else
727 window.onload = reinstallAndRemoveTimer;
728}
729
730}
731asciidoc.install();
732/*]]>*/
733</script>
734</head>
735<body class="article">
736<div id="header">
737<h1>GIT bitmap v1 format</h1>
738</div>
739<div id="content">
740<div class="sect1">
741<h2 id="_pack_and_multi_pack_bitmaps">Pack and multi-pack bitmaps</h2>
742<div class="sectionbody">
743<div class="paragraph"><p>Bitmaps store reachability information about the set of objects in a packfile,
744or a multi-pack index (MIDX). The former is defined obviously, and the latter is
745defined as the union of objects in packs contained in the MIDX.</p></div>
746<div class="paragraph"><p>A bitmap may belong to either one pack, or the repository&#8217;s multi-pack index (if
747it exists). A repository may have at most one bitmap.</p></div>
748<div class="paragraph"><p>An object is uniquely described by its bit position within a bitmap:</p></div>
749<div class="ulist"><ul>
750<li>
751<p>
752If the bitmap belongs to a packfile, the <em>n</em>th bit corresponds to
753 the <em>n</em>th object in pack order. For a function <code>offset</code> which maps
754 objects to their byte offset within a pack, pack order is defined as
755 follows:
756</p>
757<div class="literalblock">
758<div class="content">
759<pre><code>o1 &lt;= o2 &lt;==&gt; offset(o1) &lt;= offset(o2)</code></pre>
760</div></div>
761</li>
762<li>
763<p>
764If the bitmap belongs to a MIDX, the <em>n</em>th bit corresponds to the
765 <em>n</em>th object in MIDX order. With an additional function <code>pack</code> which
766 maps objects to the pack they were selected from by the MIDX, MIDX order
767 is defined as follows:
768</p>
769<div class="literalblock">
770<div class="content">
771<pre><code>o1 &lt;= o2 &lt;==&gt; pack(o1) &lt;= pack(o2) /\ offset(o1) &lt;= offset(o2)</code></pre>
772</div></div>
773<div class="paragraph"><p>The ordering between packs is done according to the MIDX&#8217;s .rev file.
774Notably, the preferred pack sorts ahead of all other packs.</p></div>
775</li>
776</ul></div>
777<div class="paragraph"><p>The on-disk representation (described below) of a bitmap is the same regardless
778of whether or not that bitmap belongs to a packfile or a MIDX. The only
779difference is the interpretation of the bits, which is described above.</p></div>
780<div class="paragraph"><p>Certain bitmap extensions are supported (see: Appendix B). No extensions are
781required for bitmaps corresponding to packfiles. For bitmaps that correspond to
782MIDXs, both the bit-cache and rev-cache extensions are required.</p></div>
783</div>
784</div>
785<div class="sect1">
786<h2 id="_on_disk_format">On-disk format</h2>
787<div class="sectionbody">
788<div class="ulist"><ul>
789<li>
790<p>
791A header appears at the beginning:
792</p>
793<div class="dlist"><dl>
794<dt class="hdlist1">
7954-byte signature:
796</dt>
797<dd>
798<p>
799{<em>B</em>, <em>I</em>, <em>T</em>, <em>M</em>}
800</p>
801</dd>
802<dt class="hdlist1">
8032-byte version number (network byte order):
804</dt>
805<dd>
806<p>
807 The current implementation only supports version 1
808 of the bitmap index (the same one as JGit).
809</p>
810</dd>
811<dt class="hdlist1">
8122-byte flags (network byte order):
813</dt>
814<dd>
815<p>
816 The following flags are supported:
817</p>
818<div class="ulist"><ul>
819<li>
820<p>
821</p>
822<div class="dlist"><dl>
823<dt class="hdlist1">
824BITMAP_OPT_FULL_DAG (0x1) REQUIRED:
825</dt>
826<dd>
827<p>
828 This flag must always be present. It implies that the
829 bitmap index has been generated for a packfile or
830 multi-pack index (MIDX) with full closure (i.e. where
831 every single object in the packfile/MIDX can find its
832 parent links inside the same packfile/MIDX). This is a
833 requirement for the bitmap index format, also present in
834 JGit, that greatly reduces the complexity of the
835 implementation.
836</p>
837</dd>
838</dl></div>
839</li>
840<li>
841<p>
842</p>
843<div class="dlist"><dl>
844<dt class="hdlist1">
845BITMAP_OPT_HASH_CACHE (0x4):
846</dt>
847<dd>
848<p>
849 If present, the end of the bitmap file contains
850 <code>N</code> 32-bit name-hash values, one per object in the
851 pack/MIDX. The format and meaning of the name-hash is
852 described below.
853</p>
854</dd>
855</dl></div>
856</li>
857</ul></div>
858</dd>
859<dt class="hdlist1">
8604-byte entry count (network byte order):
861</dt>
862<dd>
863<p>
864 The total count of entries (bitmapped commits) in this bitmap index.
865</p>
866</dd>
867<dt class="hdlist1">
86820-byte checksum:
869</dt>
870<dd>
871<p>
872 The SHA1 checksum of the pack/MIDX this bitmap index
873 belongs to.
874</p>
875</dd>
876</dl></div>
877</li>
878<li>
879<p>
8804 EWAH bitmaps that act as type indexes
881</p>
882<div class="paragraph"><p>Type indexes are serialized after the hash cache in the shape
883of four EWAH bitmaps stored consecutively (see Appendix A for
884the serialization format of an EWAH bitmap).</p></div>
885<div class="paragraph"><p>There is a bitmap for each Git object type, stored in the following
886order:</p></div>
887<div class="ulist"><ul>
888<li>
889<p>
890Commits
891</p>
892</li>
893<li>
894<p>
895Trees
896</p>
897</li>
898<li>
899<p>
900Blobs
901</p>
902</li>
903<li>
904<p>
905Tags
906</p>
907</li>
908</ul></div>
909<div class="paragraph"><p>In each bitmap, the `n`th bit is set to true if the `n`th object
910in the packfile or multi-pack index is of that type.</p></div>
911<div class="paragraph"><p>The obvious consequence is that the OR of all 4 bitmaps will result
912in a full set (all bits set), and the AND of all 4 bitmaps will
913result in an empty bitmap (no bits set).</p></div>
914</li>
915<li>
916<p>
917N entries with compressed bitmaps, one for each indexed commit
918</p>
919<div class="paragraph"><p>Where <code>N</code> is the total amount of entries in this bitmap index.
920Each entry contains the following:</p></div>
921<div class="ulist"><ul>
922<li>
923<p>
924</p>
925<div class="dlist"><dl>
926<dt class="hdlist1">
9274-byte object position (network byte order):
928</dt>
929<dd>
930<p>
931 The position <strong>in the index for the packfile or
932 multi-pack index</strong> where the bitmap for this commit is
933 found.
934</p>
935</dd>
936</dl></div>
937</li>
938<li>
939<p>
940</p>
941<div class="dlist"><dl>
942<dt class="hdlist1">
9431-byte XOR-offset:
944</dt>
945<dd>
946<p>
947 The xor offset used to compress this bitmap. For an entry
948 in position <code>x</code>, a XOR offset of <code>y</code> means that the actual
949 bitmap representing this commit is composed by XORing the
950 bitmap for this entry with the bitmap in entry <code>x-y</code> (i.e.
951 the bitmap <code>y</code> entries before this one).
952</p>
953<div class="admonitionblock">
954<table><tr>
955<td class="icon">
956<div class="title">Note</div>
957</td>
958<td class="content">This compression can be recursive. In order to
959XOR this entry with a previous one, the previous entry needs
960to be decompressed first, and so on.</td>
961</tr></table>
962</div>
963<div class="paragraph"><p>The hard-limit for this offset is 160 (an entry can only be
964xor&#8217;ed against one of the 160 entries preceding it). This
965number is always positive, and hence entries are always xor&#8217;ed
966with <strong>previous</strong> bitmaps, not bitmaps that will come afterwards
967in the index.</p></div>
968</dd>
969</dl></div>
970</li>
971<li>
972<p>
973</p>
974<div class="dlist"><dl>
975<dt class="hdlist1">
9761-byte flags for this bitmap:
977</dt>
978<dd>
979<p>
980 At the moment the only available flag is <code>0x1</code>, which hints
981 that this bitmap can be re-used when rebuilding bitmap indexes
982 for the repository.
983</p>
984</dd>
985</dl></div>
986</li>
987<li>
988<p>
989The compressed bitmap itself, see Appendix A.
990</p>
991</li>
992</ul></div>
993</li>
994<li>
995<p>
996</p>
997<div class="dlist"><dl>
998<dt class="hdlist1">
999TRAILER:
1000</dt>
1001<dd>
1002<p>
1003 Trailing checksum of the preceding contents.
1004</p>
1005</dd>
1006</dl></div>
1007</li>
1008</ul></div>
1009</div>
1010</div>
1011<div class="sect1">
1012<h2 id="_appendix_a_serialization_format_for_an_ewah_bitmap">Appendix A: Serialization format for an EWAH bitmap</h2>
1013<div class="sectionbody">
1014<div class="paragraph"><p>Ewah bitmaps are serialized in the same protocol as the JAVAEWAH
1015library, making them backwards compatible with the JGit
1016implementation:</p></div>
1017<div class="ulist"><ul>
1018<li>
1019<p>
10204-byte number of bits of the resulting UNCOMPRESSED bitmap
1021</p>
1022</li>
1023<li>
1024<p>
10254-byte number of words of the COMPRESSED bitmap, when stored
1026</p>
1027</li>
1028<li>
1029<p>
1030N x 8-byte words, as specified by the previous field
1031</p>
1032<div class="paragraph"><p>This is the actual content of the compressed bitmap.</p></div>
1033</li>
1034<li>
1035<p>
10364-byte position of the current RLW for the compressed
1037 bitmap
1038</p>
1039</li>
1040</ul></div>
1041<div class="paragraph"><p>All words are stored in network byte order for their corresponding
1042sizes.</p></div>
1043<div class="paragraph"><p>The compressed bitmap is stored in a form of run-length encoding, as
1044follows. It consists of a concatenation of an arbitrary number of
1045chunks. Each chunk consists of one or more 64-bit words</p></div>
1046<div class="literalblock">
1047<div class="content">
1048<pre><code>H L_1 L_2 L_3 .... L_M</code></pre>
1049</div></div>
1050<div class="paragraph"><p>H is called RLW (run length word). It consists of (from lower to higher
1051order bits):</p></div>
1052<div class="ulist"><ul>
1053<li>
1054<p>
10551 bit: the repeated bit B
1056</p>
1057</li>
1058<li>
1059<p>
106032 bits: repetition count K (unsigned)
1061</p>
1062</li>
1063<li>
1064<p>
106531 bits: literal word count M (unsigned)
1066</p>
1067</li>
1068</ul></div>
1069<div class="paragraph"><p>The bitstream represented by the above chunk is then:</p></div>
1070<div class="ulist"><ul>
1071<li>
1072<p>
1073K repetitions of B
1074</p>
1075</li>
1076<li>
1077<p>
1078The bits stored in <code>L_1</code> through <code>L_M</code>. Within a word, bits at
1079 lower order come earlier in the stream than those at higher
1080 order.
1081</p>
1082</li>
1083</ul></div>
1084<div class="paragraph"><p>The next word after <code>L_M</code> (if any) must again be a RLW, for the next
1085chunk. For efficient appending to the bitstream, the EWAH stores a
1086pointer to the last RLW in the stream.</p></div>
1087</div>
1088</div>
1089<div class="sect1">
1090<h2 id="_appendix_b_optional_bitmap_sections">Appendix B: Optional Bitmap Sections</h2>
1091<div class="sectionbody">
1092<div class="paragraph"><p>These sections may or may not be present in the <code>.bitmap</code> file; their
1093presence is indicated by the header flags section described above.</p></div>
1094</div>
1095</div>
1096<div class="sect1">
1097<h2 id="_name_hash_cache">Name-hash cache</h2>
1098<div class="sectionbody">
1099<div class="paragraph"><p>If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains
1100a cache of 32-bit values, one per object in the pack/MIDX. The value at
1101position <code>i</code> is the hash of the pathname at which the `i`th object
1102(counting in index or multi-pack index order) in the pack/MIDX can be found.
1103This can be fed into the delta heuristics to compare objects with similar
1104pathnames.</p></div>
1105<div class="paragraph"><p>The hash algorithm used is:</p></div>
1106<div class="literalblock">
1107<div class="content">
1108<pre><code>hash = 0;
1109while ((c = *name++))
1110 if (!isspace(c))
1111 hash = (hash &gt;&gt; 2) + (c &lt;&lt; 24);</code></pre>
1112</div></div>
1113<div class="paragraph"><p>Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
1114If implementations want to choose a different hashing scheme, they are
1115free to do so, but MUST allocate a new header flag (because comparing
1116hashes made under two different schemes would be pointless).</p></div>
1117</div>
1118</div>
1119</div>
1120<div id="footnotes"><hr /></div>
1121<div id="footer">
1122<div id="footer-text">
1123Last updated
1124 2022-07-11 16:06:18 PDT
1125</div>
1126</div>
1127</body>
1128</html>