technical/bitmap-format.html

   1 <!DOCTYPE html>
   2 <html xmlns="http://www.w3.org/1999/xhtml" lang="en">
   3 <head>
   4 <meta charset="UTF-8"/>
   5 <meta http-equiv="X-UA-Compatible" content="IE=edge"/>
   6 <meta name="viewport" content="width=device-width, initial-scale=1.0"/>
   7 <meta name="generator" content="Asciidoctor 2.0.20"/>
   8 <title>GIT bitmap v1 format</title>
   9 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"/>
  10 <style>
  11 /*! Asciidoctor default stylesheet | MIT License | https://asciidoctor.org */
  12 /* Uncomment the following line when using as a custom stylesheet */
  13 /* @import "https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700"; */
  14 html{font-family:sans-serif;-webkit-text-size-adjust:100%}
  15 a{background:none}
  16 a:focus{outline:thin dotted}
  17 a:active,a:hover{outline:0}
  18 h1{font-size:2em;margin:.67em 0}
  19 b,strong{font-weight:bold}
  20 abbr{font-size:.9em}
  21 abbr[title]{cursor:help;border-bottom:1px dotted #dddddf;text-decoration:none}
  22 dfn{font-style:italic}
  23 hr{height:0}
  24 mark{background:#ff0;color:#000}
  25 code,kbd,pre,samp{font-family:monospace;font-size:1em}
  26 pre{white-space:pre-wrap}
  27 q{quotes:"\201C" "\201D" "\2018" "\2019"}
  28 small{font-size:80%}
  29 sub,sup{font-size:75%;line-height:0;position:relative;vertical-align:baseline}
  30 sup{top:-.5em}
  31 sub{bottom:-.25em}
  32 img{border:0}
  33 svg:not(:root){overflow:hidden}
  34 figure{margin:0}
  35 audio,video{display:inline-block}
  36 audio:not([controls]){display:none;height:0}
  37 fieldset{border:1px solid silver;margin:0 2px;padding:.35em .625em .75em}
  38 legend{border:0;padding:0}
  39 button,input,select,textarea{font-family:inherit;font-size:100%;margin:0}
  40 button,input{line-height:normal}
  41 button,select{text-transform:none}
  42 button,html input[type=button],input[type=reset],input[type=submit]{-webkit-appearance:button;cursor:pointer}
  43 button[disabled],html input[disabled]{cursor:default}
  44 input[type=checkbox],input[type=radio]{padding:0}
  45 button::-moz-focus-inner,input::-moz-focus-inner{border:0;padding:0}
  46 textarea{overflow:auto;vertical-align:top}
  47 table{border-collapse:collapse;border-spacing:0}
  48 *,::before,::after{box-sizing:border-box}
  49 html,body{font-size:100%}
  50 body{background:#fff;color:rgba(0,0,0,.8);padding:0;margin:0;font-family:"Noto Serif","DejaVu Serif",serif;line-height:1;position:relative;cursor:auto;-moz-tab-size:4;-o-tab-size:4;tab-size:4;word-wrap:anywhere;-moz-osx-font-smoothing:grayscale;-webkit-font-smoothing:antialiased}
  51 a:hover{cursor:pointer}
  52 img,object,embed{max-width:100%;height:auto}
  53 object,embed{height:100%}
  54 img{-ms-interpolation-mode:bicubic}
  55 .left{float:left!important}
  56 .right{float:right!important}
  57 .text-left{text-align:left!important}
  58 .text-right{text-align:right!important}
  59 .text-center{text-align:center!important}
  60 .text-justify{text-align:justify!important}
  61 .hide{display:none}
  62 img,object,svg{display:inline-block;vertical-align:middle}
  63 textarea{height:auto;min-height:50px}
  64 select{width:100%}
  65 .subheader,.admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{line-height:1.45;color:#7a2518;font-weight:400;margin-top:0;margin-bottom:.25em}
  66 div,dl,dt,dd,ul,ol,li,h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6,pre,form,p,blockquote,th,td{margin:0;padding:0}
  67 a{color:#2156a5;text-decoration:underline;line-height:inherit}
  68 a:hover,a:focus{color:#1d4b8f}
  69 a img{border:0}
  70 p{line-height:1.6;margin-bottom:1.25em;text-rendering:optimizeLegibility}
  71 p aside{font-size:.875em;line-height:1.35;font-style:italic}
  72 h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{font-family:"Open Sans","DejaVu Sans",sans-serif;font-weight:300;font-style:normal;color:#ba3925;text-rendering:optimizeLegibility;margin-top:1em;margin-bottom:.5em;line-height:1.0125em}
  73 h1 small,h2 small,h3 small,#toctitle small,.sidebarblock>.content>.title small,h4 small,h5 small,h6 small{font-size:60%;color:#e99b8f;line-height:0}
  74 h1{font-size:2.125em}
  75 h2{font-size:1.6875em}
  76 h3,#toctitle,.sidebarblock>.content>.title{font-size:1.375em}
  77 h4,h5{font-size:1.125em}
  78 h6{font-size:1em}
  79 hr{border:solid #dddddf;border-width:1px 0 0;clear:both;margin:1.25em 0 1.1875em}
  80 em,i{font-style:italic;line-height:inherit}
  81 strong,b{font-weight:bold;line-height:inherit}
  82 small{font-size:60%;line-height:inherit}
  83 code{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;font-weight:400;color:rgba(0,0,0,.9)}
  84 ul,ol,dl{line-height:1.6;margin-bottom:1.25em;list-style-position:outside;font-family:inherit}
  85 ul,ol{margin-left:1.5em}
  86 ul li ul,ul li ol{margin-left:1.25em;margin-bottom:0}
  87 ul.circle{list-style-type:circle}
  88 ul.disc{list-style-type:disc}
  89 ul.square{list-style-type:square}
  90 ul.circle ul:not([class]),ul.disc ul:not([class]),ul.square ul:not([class]){list-style:inherit}
  91 ol li ul,ol li ol{margin-left:1.25em;margin-bottom:0}
  92 dl dt{margin-bottom:.3125em;font-weight:bold}
  93 dl dd{margin-bottom:1.25em}
  94 blockquote{margin:0 0 1.25em;padding:.5625em 1.25em 0 1.1875em;border-left:1px solid #ddd}
  95 blockquote,blockquote p{line-height:1.6;color:rgba(0,0,0,.85)}
  96 @media screen and (min-width:768px){h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2}
  97 h1{font-size:2.75em}
  98 h2{font-size:2.3125em}
  99 h3,#toctitle,.sidebarblock>.content>.title{font-size:1.6875em}
 100 h4{font-size:1.4375em}}
 101 table{background:#fff;margin-bottom:1.25em;border:1px solid #dedede;word-wrap:normal}
 102 table thead,table tfoot{background:#f7f8f7}
 103 table thead tr th,table thead tr td,table tfoot tr th,table tfoot tr td{padding:.5em .625em .625em;font-size:inherit;color:rgba(0,0,0,.8);text-align:left}
 104 table tr th,table tr td{padding:.5625em .625em;font-size:inherit;color:rgba(0,0,0,.8)}
 105 table tr.even,table tr.alt{background:#f8f8f7}
 106 table thead tr th,table tfoot tr th,table tbody tr td,table tr td,table tfoot tr td{line-height:1.6}
 107 h1,h2,h3,#toctitle,.sidebarblock>.content>.title,h4,h5,h6{line-height:1.2;word-spacing:-.05em}
 108 h1 strong,h2 strong,h3 strong,#toctitle strong,.sidebarblock>.content>.title strong,h4 strong,h5 strong,h6 strong{font-weight:400}
 109 .center{margin-left:auto;margin-right:auto}
 110 .stretch{width:100%}
 111 .clearfix::before,.clearfix::after,.float-group::before,.float-group::after{content:" ";display:table}
 112 .clearfix::after,.float-group::after{clear:both}
 113 :not(pre).nobreak{word-wrap:normal}
 114 :not(pre).nowrap{white-space:nowrap}
 115 :not(pre).pre-wrap{white-space:pre-wrap}
 116 :not(pre):not([class^=L])>code{font-size:.9375em;font-style:normal!important;letter-spacing:0;padding:.1em .5ex;word-spacing:-.15em;background:#f7f7f8;border-radius:4px;line-height:1.45;text-rendering:optimizeSpeed}
 117 pre{color:rgba(0,0,0,.9);font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;line-height:1.45;text-rendering:optimizeSpeed}
 118 pre code,pre pre{color:inherit;font-size:inherit;line-height:inherit}
 119 pre>code{display:block}
 120 pre.nowrap,pre.nowrap pre{white-space:pre;word-wrap:normal}
 121 em em{font-style:normal}
 122 strong strong{font-weight:400}
 123 .keyseq{color:rgba(51,51,51,.8)}
 124 kbd{font-family:"Droid Sans Mono","DejaVu Sans Mono",monospace;display:inline-block;color:rgba(0,0,0,.8);font-size:.65em;line-height:1.45;background:#f7f7f7;border:1px solid #ccc;border-radius:3px;box-shadow:0 1px 0 rgba(0,0,0,.2),inset 0 0 0 .1em #fff;margin:0 .15em;padding:.2em .5em;vertical-align:middle;position:relative;top:-.1em;white-space:nowrap}
 125 .keyseq kbd:first-child{margin-left:0}
 126 .keyseq kbd:last-child{margin-right:0}
 127 .menuseq,.menuref{color:#000}
 128 .menuseq b:not(.caret),.menuref{font-weight:inherit}
 129 .menuseq{word-spacing:-.02em}
 130 .menuseq b.caret{font-size:1.25em;line-height:.8}
 131 .menuseq i.caret{font-weight:bold;text-align:center;width:.45em}
 132 b.button::before,b.button::after{position:relative;top:-1px;font-weight:400}
 133 b.button::before{content:"[";padding:0 3px 0 2px}
 134 b.button::after{content:"]";padding:0 2px 0 3px}
 135 p a>code:hover{color:rgba(0,0,0,.9)}
 136 #header,#content,#footnotes,#footer{width:100%;margin:0 auto;max-width:62.5em;*zoom:1;position:relative;padding-left:.9375em;padding-right:.9375em}
 137 #header::before,#header::after,#content::before,#content::after,#footnotes::before,#footnotes::after,#footer::before,#footer::after{content:" ";display:table}
 138 #header::after,#content::after,#footnotes::after,#footer::after{clear:both}
 139 #content{margin-top:1.25em}
 140 #content::before{content:none}
 141 #header>h1:first-child{color:rgba(0,0,0,.85);margin-top:2.25rem;margin-bottom:0}
 142 #header>h1:first-child+#toc{margin-top:8px;border-top:1px solid #dddddf}
 143 #header>h1:only-child,body.toc2 #header>h1:nth-last-child(2){border-bottom:1px solid #dddddf;padding-bottom:8px}
 144 #header .details{border-bottom:1px solid #dddddf;line-height:1.45;padding-top:.25em;padding-bottom:.25em;padding-left:.25em;color:rgba(0,0,0,.6);display:flex;flex-flow:row wrap}
 145 #header .details span:first-child{margin-left:-.125em}
 146 #header .details span.email a{color:rgba(0,0,0,.85)}
 147 #header .details br{display:none}
 148 #header .details br+span::before{content:"\00a0\2013\00a0"}
 149 #header .details br+span.author::before{content:"\00a0\22c5\00a0";color:rgba(0,0,0,.85)}
 150 #header .details br+span#revremark::before{content:"\00a0|\00a0"}
 151 #header #revnumber{text-transform:capitalize}
 152 #header #revnumber::after{content:"\00a0"}
 153 #content>h1:first-child:not([class]){color:rgba(0,0,0,.85);border-bottom:1px solid #dddddf;padding-bottom:8px;margin-top:0;padding-top:1rem;margin-bottom:1.25rem}
 154 #toc{border-bottom:1px solid #e7e7e9;padding-bottom:.5em}
 155 #toc>ul{margin-left:.125em}
 156 #toc ul.sectlevel0>li>a{font-style:italic}
 157 #toc ul.sectlevel0 ul.sectlevel1{margin:.5em 0}
 158 #toc ul{font-family:"Open Sans","DejaVu Sans",sans-serif;list-style-type:none}
 159 #toc li{line-height:1.3334;margin-top:.3334em}
 160 #toc a{text-decoration:none}
 161 #toc a:active{text-decoration:underline}
 162 #toctitle{color:#7a2518;font-size:1.2em}
 163 @media screen and (min-width:768px){#toctitle{font-size:1.375em}
 164 body.toc2{padding-left:15em;padding-right:0}
 165 #toc.toc2{margin-top:0!important;background:#f8f8f7;position:fixed;width:15em;left:0;top:0;border-right:1px solid #e7e7e9;border-top-width:0!important;border-bottom-width:0!important;z-index:1000;padding:1.25em 1em;height:100%;overflow:auto}
 166 #toc.toc2 #toctitle{margin-top:0;margin-bottom:.8rem;font-size:1.2em}
 167 #toc.toc2>ul{font-size:.9em;margin-bottom:0}
 168 #toc.toc2 ul ul{margin-left:0;padding-left:1em}
 169 #toc.toc2 ul.sectlevel0 ul.sectlevel1{padding-left:0;margin-top:.5em;margin-bottom:.5em}
 170 body.toc2.toc-right{padding-left:0;padding-right:15em}
 171 body.toc2.toc-right #toc.toc2{border-right-width:0;border-left:1px solid #e7e7e9;left:auto;right:0}}
 172 @media screen and (min-width:1280px){body.toc2{padding-left:20em;padding-right:0}
 173 #toc.toc2{width:20em}
 174 #toc.toc2 #toctitle{font-size:1.375em}
 175 #toc.toc2>ul{font-size:.95em}
 176 #toc.toc2 ul ul{padding-left:1.25em}
 177 body.toc2.toc-right{padding-left:0;padding-right:20em}}
 178 #content #toc{border:1px solid #e0e0dc;margin-bottom:1.25em;padding:1.25em;background:#f8f8f7;border-radius:4px}
 179 #content #toc>:first-child{margin-top:0}
 180 #content #toc>:last-child{margin-bottom:0}
 181 #footer{max-width:none;background:rgba(0,0,0,.8);padding:1.25em}
 182 #footer-text{color:hsla(0,0%,100%,.8);line-height:1.44}
 183 #content{margin-bottom:.625em}
 184 .sect1{padding-bottom:.625em}
 185 @media screen and (min-width:768px){#content{margin-bottom:1.25em}
 186 .sect1{padding-bottom:1.25em}}
 187 .sect1:last-child{padding-bottom:0}
 188 .sect1+.sect1{border-top:1px solid #e7e7e9}
 189 #content h1>a.anchor,h2>a.anchor,h3>a.anchor,#toctitle>a.anchor,.sidebarblock>.content>.title>a.anchor,h4>a.anchor,h5>a.anchor,h6>a.anchor{position:absolute;z-index:1001;width:1.5ex;margin-left:-1.5ex;display:block;text-decoration:none!important;visibility:hidden;text-align:center;font-weight:400}
 190 #content h1>a.anchor::before,h2>a.anchor::before,h3>a.anchor::before,#toctitle>a.anchor::before,.sidebarblock>.content>.title>a.anchor::before,h4>a.anchor::before,h5>a.anchor::before,h6>a.anchor::before{content:"\00A7";font-size:.85em;display:block;padding-top:.1em}
 191 #content h1:hover>a.anchor,#content h1>a.anchor:hover,h2:hover>a.anchor,h2>a.anchor:hover,h3:hover>a.anchor,#toctitle:hover>a.anchor,.sidebarblock>.content>.title:hover>a.anchor,h3>a.anchor:hover,#toctitle>a.anchor:hover,.sidebarblock>.content>.title>a.anchor:hover,h4:hover>a.anchor,h4>a.anchor:hover,h5:hover>a.anchor,h5>a.anchor:hover,h6:hover>a.anchor,h6>a.anchor:hover{visibility:visible}
 192 #content h1>a.link,h2>a.link,h3>a.link,#toctitle>a.link,.sidebarblock>.content>.title>a.link,h4>a.link,h5>a.link,h6>a.link{color:#ba3925;text-decoration:none}
 193 #content h1>a.link:hover,h2>a.link:hover,h3>a.link:hover,#toctitle>a.link:hover,.sidebarblock>.content>.title>a.link:hover,h4>a.link:hover,h5>a.link:hover,h6>a.link:hover{color:#a53221}
 194 details,.audioblock,.imageblock,.literalblock,.listingblock,.stemblock,.videoblock{margin-bottom:1.25em}
 195 details{margin-left:1.25rem}
 196 details>summary{cursor:pointer;display:block;position:relative;line-height:1.6;margin-bottom:.625rem;outline:none;-webkit-tap-highlight-color:transparent}
 197 details>summary::-webkit-details-marker{display:none}
 198 details>summary::before{content:"";border:solid transparent;border-left:solid;border-width:.3em 0 .3em .5em;position:absolute;top:.5em;left:-1.25rem;transform:translateX(15%)}
 199 details[open]>summary::before{border:solid transparent;border-top:solid;border-width:.5em .3em 0;transform:translateY(15%)}
 200 details>summary::after{content:"";width:1.25rem;height:1em;position:absolute;top:.3em;left:-1.25rem}
 201 .admonitionblock td.content>.title,.audioblock>.title,.exampleblock>.title,.imageblock>.title,.listingblock>.title,.literalblock>.title,.stemblock>.title,.openblock>.title,.paragraph>.title,.quoteblock>.title,table.tableblock>.title,.verseblock>.title,.videoblock>.title,.dlist>.title,.olist>.title,.ulist>.title,.qlist>.title,.hdlist>.title{text-rendering:optimizeLegibility;text-align:left;font-family:"Noto Serif","DejaVu Serif",serif;font-size:1rem;font-style:italic}
 202 table.tableblock.fit-content>caption.title{white-space:nowrap;width:0}
 203 .paragraph.lead>p,#preamble>.sectionbody>[class=paragraph]:first-of-type p{font-size:1.21875em;line-height:1.6;color:rgba(0,0,0,.85)}
 204 .admonitionblock>table{border-collapse:separate;border:0;background:none;width:100%}
 205 .admonitionblock>table td.icon{text-align:center;width:80px}
 206 .admonitionblock>table td.icon img{max-width:none}
 207 .admonitionblock>table td.icon .title{font-weight:bold;font-family:"Open Sans","DejaVu Sans",sans-serif;text-transform:uppercase}
 208 .admonitionblock>table td.content{padding-left:1.125em;padding-right:1.25em;border-left:1px solid #dddddf;color:rgba(0,0,0,.6);word-wrap:anywhere}
 209 .admonitionblock>table td.content>:last-child>:last-child{margin-bottom:0}
 210 .exampleblock>.content{border:1px solid #e6e6e6;margin-bottom:1.25em;padding:1.25em;background:#fff;border-radius:4px}
 211 .sidebarblock{border:1px solid #dbdbd6;margin-bottom:1.25em;padding:1.25em;background:#f3f3f2;border-radius:4px}
 212 .sidebarblock>.content>.title{color:#7a2518;margin-top:0;text-align:center}
 213 .exampleblock>.content>:first-child,.sidebarblock>.content>:first-child{margin-top:0}
 214 .exampleblock>.content>:last-child,.exampleblock>.content>:last-child>:last-child,.exampleblock>.content .olist>ol>li:last-child>:last-child,.exampleblock>.content .ulist>ul>li:last-child>:last-child,.exampleblock>.content .qlist>ol>li:last-child>:last-child,.sidebarblock>.content>:last-child,.sidebarblock>.content>:last-child>:last-child,.sidebarblock>.content .olist>ol>li:last-child>:last-child,.sidebarblock>.content .ulist>ul>li:last-child>:last-child,.sidebarblock>.content .qlist>ol>li:last-child>:last-child{margin-bottom:0}
 215 .literalblock pre,.listingblock>.content>pre{border-radius:4px;overflow-x:auto;padding:1em;font-size:.8125em}
 216 @media screen and (min-width:768px){.literalblock pre,.listingblock>.content>pre{font-size:.90625em}}
 217 @media screen and (min-width:1280px){.literalblock pre,.listingblock>.content>pre{font-size:1em}}
 218 .literalblock pre,.listingblock>.content>pre:not(.highlight),.listingblock>.content>pre[class=highlight],.listingblock>.content>pre[class^="highlight "]{background:#f7f7f8}
 219 .literalblock.output pre{color:#f7f7f8;background:rgba(0,0,0,.9)}
 220 .listingblock>.content{position:relative}
 221 .listingblock code[data-lang]::before{display:none;content:attr(data-lang);position:absolute;font-size:.75em;top:.425rem;right:.5rem;line-height:1;text-transform:uppercase;color:inherit;opacity:.5}
 222 .listingblock:hover code[data-lang]::before{display:block}
 223 .listingblock.terminal pre .command::before{content:attr(data-prompt);padding-right:.5em;color:inherit;opacity:.5}
 224 .listingblock.terminal pre .command:not([data-prompt])::before{content:"$"}
 225 .listingblock pre.highlightjs{padding:0}
 226 .listingblock pre.highlightjs>code{padding:1em;border-radius:4px}
 227 .listingblock pre.prettyprint{border-width:0}
 228 .prettyprint{background:#f7f7f8}
 229 pre.prettyprint .linenums{line-height:1.45;margin-left:2em}
 230 pre.prettyprint li{background:none;list-style-type:inherit;padding-left:0}
 231 pre.prettyprint li code[data-lang]::before{opacity:1}
 232 pre.prettyprint li:not(:first-child) code[data-lang]::before{display:none}
 233 table.linenotable{border-collapse:separate;border:0;margin-bottom:0;background:none}
 234 table.linenotable td[class]{color:inherit;vertical-align:top;padding:0;line-height:inherit;white-space:normal}
 235 table.linenotable td.code{padding-left:.75em}
 236 table.linenotable td.linenos,pre.pygments .linenos{border-right:1px solid;opacity:.35;padding-right:.5em;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none}
 237 pre.pygments span.linenos{display:inline-block;margin-right:.75em}
 238 .quoteblock{margin:0 1em 1.25em 1.5em;display:table}
 239 .quoteblock:not(.excerpt)>.title{margin-left:-1.5em;margin-bottom:.75em}
 240 .quoteblock blockquote,.quoteblock p{color:rgba(0,0,0,.85);font-size:1.15rem;line-height:1.75;word-spacing:.1em;letter-spacing:0;font-style:italic;text-align:justify}
 241 .quoteblock blockquote{margin:0;padding:0;border:0}
 242 .quoteblock blockquote::before{content:"\201c";float:left;font-size:2.75em;font-weight:bold;line-height:.6em;margin-left:-.6em;color:#7a2518;text-shadow:0 1px 2px rgba(0,0,0,.1)}
 243 .quoteblock blockquote>.paragraph:last-child p{margin-bottom:0}
 244 .quoteblock .attribution{margin-top:.75em;margin-right:.5ex;text-align:right}
 245 .verseblock{margin:0 1em 1.25em}
 246 .verseblock pre{font-family:"Open Sans","DejaVu Sans",sans-serif;font-size:1.15rem;color:rgba(0,0,0,.85);font-weight:300;text-rendering:optimizeLegibility}
 247 .verseblock pre strong{font-weight:400}
 248 .verseblock .attribution{margin-top:1.25rem;margin-left:.5ex}
 249 .quoteblock .attribution,.verseblock .attribution{font-size:.9375em;line-height:1.45;font-style:italic}
 250 .quoteblock .attribution br,.verseblock .attribution br{display:none}
 251 .quoteblock .attribution cite,.verseblock .attribution cite{display:block;letter-spacing:-.025em;color:rgba(0,0,0,.6)}
 252 .quoteblock.abstract blockquote::before,.quoteblock.excerpt blockquote::before,.quoteblock .quoteblock blockquote::before{display:none}
 253 .quoteblock.abstract blockquote,.quoteblock.abstract p,.quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{line-height:1.6;word-spacing:0}
 254 .quoteblock.abstract{margin:0 1em 1.25em;display:block}
 255 .quoteblock.abstract>.title{margin:0 0 .375em;font-size:1.15em;text-align:center}
 256 .quoteblock.excerpt>blockquote,.quoteblock .quoteblock{padding:0 0 .25em 1em;border-left:.25em solid #dddddf}
 257 .quoteblock.excerpt,.quoteblock .quoteblock{margin-left:0}
 258 .quoteblock.excerpt blockquote,.quoteblock.excerpt p,.quoteblock .quoteblock blockquote,.quoteblock .quoteblock p{color:inherit;font-size:1.0625rem}
 259 .quoteblock.excerpt .attribution,.quoteblock .quoteblock .attribution{color:inherit;font-size:.85rem;text-align:left;margin-right:0}
 260 p.tableblock:last-child{margin-bottom:0}
 261 td.tableblock>.content{margin-bottom:1.25em;word-wrap:anywhere}
 262 td.tableblock>.content>:last-child{margin-bottom:-1.25em}
 263 table.tableblock,th.tableblock,td.tableblock{border:0 solid #dedede}
 264 table.grid-all>*>tr>*{border-width:1px}
 265 table.grid-cols>*>tr>*{border-width:0 1px}
 266 table.grid-rows>*>tr>*{border-width:1px 0}
 267 table.frame-all{border-width:1px}
 268 table.frame-ends{border-width:1px 0}
 269 table.frame-sides{border-width:0 1px}
 270 table.frame-none>colgroup+*>:first-child>*,table.frame-sides>colgroup+*>:first-child>*{border-top-width:0}
 271 table.frame-none>:last-child>:last-child>*,table.frame-sides>:last-child>:last-child>*{border-bottom-width:0}
 272 table.frame-none>*>tr>:first-child,table.frame-ends>*>tr>:first-child{border-left-width:0}
 273 table.frame-none>*>tr>:last-child,table.frame-ends>*>tr>:last-child{border-right-width:0}
 274 table.stripes-all>*>tr,table.stripes-odd>*>tr:nth-of-type(odd),table.stripes-even>*>tr:nth-of-type(even),table.stripes-hover>*>tr:hover{background:#f8f8f7}
 275 th.halign-left,td.halign-left{text-align:left}
 276 th.halign-right,td.halign-right{text-align:right}
 277 th.halign-center,td.halign-center{text-align:center}
 278 th.valign-top,td.valign-top{vertical-align:top}
 279 th.valign-bottom,td.valign-bottom{vertical-align:bottom}
 280 th.valign-middle,td.valign-middle{vertical-align:middle}
 281 table thead th,table tfoot th{font-weight:bold}
 282 tbody tr th{background:#f7f8f7}
 283 tbody tr th,tbody tr th p,tfoot tr th,tfoot tr th p{color:rgba(0,0,0,.8);font-weight:bold}
 284 p.tableblock>code:only-child{background:none;padding:0}
 285 p.tableblock{font-size:1em}
 286 ol{margin-left:1.75em}
 287 ul li ol{margin-left:1.5em}
 288 dl dd{margin-left:1.125em}
 289 dl dd:last-child,dl dd:last-child>:last-child{margin-bottom:0}
 290 li p,ul dd,ol dd,.olist .olist,.ulist .ulist,.ulist .olist,.olist .ulist{margin-bottom:.625em}
 291 ul.checklist,ul.none,ol.none,ul.no-bullet,ol.no-bullet,ol.unnumbered,ul.unstyled,ol.unstyled{list-style-type:none}
 292 ul.no-bullet,ol.no-bullet,ol.unnumbered{margin-left:.625em}
 293 ul.unstyled,ol.unstyled{margin-left:0}
 294 li>p:empty:only-child::before{content:"";display:inline-block}
 295 ul.checklist>li>p:first-child{margin-left:-1em}
 296 ul.checklist>li>p:first-child>.fa-square-o:first-child,ul.checklist>li>p:first-child>.fa-check-square-o:first-child{width:1.25em;font-size:.8em;position:relative;bottom:.125em}
 297 ul.checklist>li>p:first-child>input[type=checkbox]:first-child{margin-right:.25em}
 298 ul.inline{display:flex;flex-flow:row wrap;list-style:none;margin:0 0 .625em -1.25em}
 299 ul.inline>li{margin-left:1.25em}
 300 .unstyled dl dt{font-weight:400;font-style:normal}
 301 ol.arabic{list-style-type:decimal}
 302 ol.decimal{list-style-type:decimal-leading-zero}
 303 ol.loweralpha{list-style-type:lower-alpha}
 304 ol.upperalpha{list-style-type:upper-alpha}
 305 ol.lowerroman{list-style-type:lower-roman}
 306 ol.upperroman{list-style-type:upper-roman}
 307 ol.lowergreek{list-style-type:lower-greek}
 308 .hdlist>table,.colist>table{border:0;background:none}
 309 .hdlist>table>tbody>tr,.colist>table>tbody>tr{background:none}
 310 td.hdlist1,td.hdlist2{vertical-align:top;padding:0 .625em}
 311 td.hdlist1{font-weight:bold;padding-bottom:1.25em}
 312 td.hdlist2{word-wrap:anywhere}
 313 .literalblock+.colist,.listingblock+.colist{margin-top:-.5em}
 314 .colist td:not([class]):first-child{padding:.4em .75em 0;line-height:1;vertical-align:top}
 315 .colist td:not([class]):first-child img{max-width:none}
 316 .colist td:not([class]):last-child{padding:.25em 0}
 317 .thumb,.th{line-height:0;display:inline-block;border:4px solid #fff;box-shadow:0 0 0 1px #ddd}
 318 .imageblock.left{margin:.25em .625em 1.25em 0}
 319 .imageblock.right{margin:.25em 0 1.25em .625em}
 320 .imageblock>.title{margin-bottom:0}
 321 .imageblock.thumb,.imageblock.th{border-width:6px}
 322 .imageblock.thumb>.title,.imageblock.th>.title{padding:0 .125em}
 323 .image.left,.image.right{margin-top:.25em;margin-bottom:.25em;display:inline-block;line-height:0}
 324 .image.left{margin-right:.625em}
 325 .image.right{margin-left:.625em}
 326 a.image{text-decoration:none;display:inline-block}
 327 a.image object{pointer-events:none}
 328 sup.footnote,sup.footnoteref{font-size:.875em;position:static;vertical-align:super}
 329 sup.footnote a,sup.footnoteref a{text-decoration:none}
 330 sup.footnote a:active,sup.footnoteref a:active{text-decoration:underline}
 331 #footnotes{padding-top:.75em;padding-bottom:.75em;margin-bottom:.625em}
 332 #footnotes hr{width:20%;min-width:6.25em;margin:-.25em 0 .75em;border-width:1px 0 0}
 333 #footnotes .footnote{padding:0 .375em 0 .225em;line-height:1.3334;font-size:.875em;margin-left:1.2em;margin-bottom:.2em}
 334 #footnotes .footnote a:first-of-type{font-weight:bold;text-decoration:none;margin-left:-1.05em}
 335 #footnotes .footnote:last-of-type{margin-bottom:0}
 336 #content #footnotes{margin-top:-.625em;margin-bottom:0;padding:.75em 0}
 337 div.unbreakable{page-break-inside:avoid}
 338 .big{font-size:larger}
 339 .small{font-size:smaller}
 340 .underline{text-decoration:underline}
 341 .overline{text-decoration:overline}
 342 .line-through{text-decoration:line-through}
 343 .aqua{color:#00bfbf}
 344 .aqua-background{background:#00fafa}
 345 .black{color:#000}
 346 .black-background{background:#000}
 347 .blue{color:#0000bf}
 348 .blue-background{background:#0000fa}
 349 .fuchsia{color:#bf00bf}
 350 .fuchsia-background{background:#fa00fa}
 351 .gray{color:#606060}
 352 .gray-background{background:#7d7d7d}
 353 .green{color:#006000}
 354 .green-background{background:#007d00}
 355 .lime{color:#00bf00}
 356 .lime-background{background:#00fa00}
 357 .maroon{color:#600000}
 358 .maroon-background{background:#7d0000}
 359 .navy{color:#000060}
 360 .navy-background{background:#00007d}
 361 .olive{color:#606000}
 362 .olive-background{background:#7d7d00}
 363 .purple{color:#600060}
 364 .purple-background{background:#7d007d}
 365 .red{color:#bf0000}
 366 .red-background{background:#fa0000}
 367 .silver{color:#909090}
 368 .silver-background{background:#bcbcbc}
 369 .teal{color:#006060}
 370 .teal-background{background:#007d7d}
 371 .white{color:#bfbfbf}
 372 .white-background{background:#fafafa}
 373 .yellow{color:#bfbf00}
 374 .yellow-background{background:#fafa00}
 375 span.icon>.fa{cursor:default}
 376 a span.icon>.fa{cursor:inherit}
 377 .admonitionblock td.icon [class^="fa icon-"]{font-size:2.5em;text-shadow:1px 1px 2px rgba(0,0,0,.5);cursor:default}
 378 .admonitionblock td.icon .icon-note::before{content:"\f05a";color:#19407c}
 379 .admonitionblock td.icon .icon-tip::before{content:"\f0eb";text-shadow:1px 1px 2px rgba(155,155,0,.8);color:#111}
 380 .admonitionblock td.icon .icon-warning::before{content:"\f071";color:#bf6900}
 381 .admonitionblock td.icon .icon-caution::before{content:"\f06d";color:#bf3400}
 382 .admonitionblock td.icon .icon-important::before{content:"\f06a";color:#bf0000}
 383 .conum[data-value]{display:inline-block;color:#fff!important;background:rgba(0,0,0,.8);border-radius:50%;text-align:center;font-size:.75em;width:1.67em;height:1.67em;line-height:1.67em;font-family:"Open Sans","DejaVu Sans",sans-serif;font-style:normal;font-weight:bold}
 384 .conum[data-value] *{color:#fff!important}
 385 .conum[data-value]+b{display:none}
 386 .conum[data-value]::after{content:attr(data-value)}
 387 pre .conum[data-value]{position:relative;top:-.125em}
 388 b.conum *{color:inherit!important}
 389 .conum:not([data-value]):empty{display:none}
 390 dt,th.tableblock,td.content,div.footnote{text-rendering:optimizeLegibility}
 391 h1,h2,p,td.content,span.alt,summary{letter-spacing:-.01em}
 392 p strong,td.content strong,div.footnote strong{letter-spacing:-.005em}
 393 p,blockquote,dt,td.content,td.hdlist1,span.alt,summary{font-size:1.0625rem}
 394 p{margin-bottom:1.25rem}
 395 .sidebarblock p,.sidebarblock dt,.sidebarblock td.content,p.tableblock{font-size:1em}
 396 .exampleblock>.content{background:#fffef7;border-color:#e0e0dc;box-shadow:0 1px 4px #e0e0dc}
 397 .print-only{display:none!important}
 398 @page{margin:1.25cm .75cm}
 399 @media print{*{box-shadow:none!important;text-shadow:none!important}
 400 html{font-size:80%}
 401 a{color:inherit!important;text-decoration:underline!important}
 402 a.bare,a[href^="#"],a[href^="mailto:"]{text-decoration:none!important}
 403 a[href^="http:"]:not(.bare)::after,a[href^="https:"]:not(.bare)::after{content:"(" attr(href) ")";display:inline-block;font-size:.875em;padding-left:.25em}
 404 abbr[title]{border-bottom:1px dotted}
 405 abbr[title]::after{content:" (" attr(title) ")"}
 406 pre,blockquote,tr,img,object,svg{page-break-inside:avoid}
 407 thead{display:table-header-group}
 408 svg{max-width:100%}
 409 p,blockquote,dt,td.content{font-size:1em;orphans:3;widows:3}
 410 h2,h3,#toctitle,.sidebarblock>.content>.title{page-break-after:avoid}
 411 #header,#content,#footnotes,#footer{max-width:none}
 412 #toc,.sidebarblock,.exampleblock>.content{background:none!important}
 413 #toc{border-bottom:1px solid #dddddf!important;padding-bottom:0!important}
 414 body.book #header{text-align:center}
 415 body.book #header>h1:first-child{border:0!important;margin:2.5em 0 1em}
 416 body.book #header .details{border:0!important;display:block;padding:0!important}
 417 body.book #header .details span:first-child{margin-left:0!important}
 418 body.book #header .details br{display:block}
 419 body.book #header .details br+span::before{content:none!important}
 420 body.book #toc{border:0!important;text-align:left!important;padding:0!important;margin:0!important}
 421 body.book #toc,body.book #preamble,body.book h1.sect0,body.book .sect1>h2{page-break-before:always}
 422 .listingblock code[data-lang]::before{display:block}
 423 #footer{padding:0 .9375em}
 424 .hide-on-print{display:none!important}
 425 .print-only{display:block!important}
 426 .hide-for-print{display:none!important}
 427 .show-for-print{display:inherit!important}}
 428 @media amzn-kf8,print{#header>h1:first-child{margin-top:1.25rem}
 429 .sect1{padding:0!important}
 430 .sect1+.sect1{border:0}
 431 #footer{background:none}
 432 #footer-text{color:rgba(0,0,0,.6);font-size:.9em}}
 433 @media amzn-kf8{#header,#content,#footnotes,#footer{padding:0}}
 434 </style>
 435 </head>
 436 <body class="article">
 437 <div id="header">
 438 <h1>GIT bitmap v1 format</h1>
 439 <div class="details">
 440 <span id="revdate">2024-11-01</span>
 441 </div>
 442 </div>
 443 <div id="content">
 444 <div class="sect1">
 445 <h2 id="_pack_and_multi_pack_bitmaps">Pack and multi-pack bitmaps</h2>
 446 <div class="sectionbody">
 447 <div class="paragraph">
 448 <p>Bitmaps store reachability information about the set of objects in a packfile,
 449 or a multi-pack index (MIDX). The former is defined obviously, and the latter is
 450 defined as the union of objects in packs contained in the MIDX.</p>
 451 </div>
 452 <div class="paragraph">
 453 <p>A bitmap may belong to either one pack, or the repository&#8217;s multi-pack index (if
 454 it exists). A repository may have at most one bitmap.</p>
 455 </div>
 456 <div class="paragraph">
 457 <p>An object is uniquely described by its bit position within a bitmap:</p>
 458 </div>
 459 <div class="ulist">
 460 <ul>
 461 <li>
 462 <p>If the bitmap belongs to a packfile, the <em>n</em>th bit corresponds to
 463 the <em>n</em>th object in pack order. For a function <code>offset</code> which maps
 464 objects to their byte offset within a pack, pack order is defined as
 465 follows:</p>
 466 <div class="literalblock">
 467 <div class="content">
 468 <pre>o1 &lt;= o2 &lt;==&gt; offset(o1) &lt;= offset(o2)</pre>
 469 </div>
 470 </div>
 471 </li>
 472 <li>
 473 <p>If the bitmap belongs to a MIDX, the <em>n</em>th bit corresponds to the
 474 <em>n</em>th object in MIDX order. With an additional function <code>pack</code> which
 475 maps objects to the pack they were selected from by the MIDX, MIDX order
 476 is defined as follows:</p>
 477 <div class="literalblock">
 478 <div class="content">
 479 <pre>o1 &lt;= o2 &lt;==&gt; pack(o1) &lt;= pack(o2) /\ offset(o1) &lt;= offset(o2)</pre>
 480 </div>
 481 </div>
 482 <div class="paragraph">
 483 <p>The ordering between packs is done according to the MIDX&#8217;s .rev file.
 484 Notably, the preferred pack sorts ahead of all other packs.</p>
 485 </div>
 486 </li>
 487 </ul>
 488 </div>
 489 <div class="paragraph">
 490 <p>The on-disk representation (described below) of a bitmap is the same regardless
 491 of whether or not that bitmap belongs to a packfile or a MIDX. The only
 492 difference is the interpretation of the bits, which is described above.</p>
 493 </div>
 494 <div class="paragraph">
 495 <p>Certain bitmap extensions are supported (see: Appendix B). No extensions are
 496 required for bitmaps corresponding to packfiles. For bitmaps that correspond to
 497 MIDXs, both the bit-cache and rev-cache extensions are required.</p>
 498 </div>
 499 </div>
 500 </div>
 501 <div class="sect1">
 502 <h2 id="_on_disk_format">On-disk format</h2>
 503 <div class="sectionbody">
 504 <div class="ulist">
 505 <ul>
 506 <li>
 507 <p>A header appears at the beginning:</p>
 508 <div class="dlist">
 509 <dl>
 510 <dt class="hdlist1">4-byte signature: </dt>
 511 <dd>
 512 <p>{<em>B</em>, <em>I</em>, <em>T</em>, <em>M</em>}</p>
 513 </dd>
 514 <dt class="hdlist1">2-byte version number (network byte order): </dt>
 515 <dd>
 516 <p>The current implementation only supports version 1
 517 of the bitmap index (the same one as JGit).</p>
 518 </dd>
 519 <dt class="hdlist1">2-byte flags (network byte order): </dt>
 520 <dd>
 521 <p>The following flags are supported:</p>
 522 <div class="ulist">
 523 <ul>
 524 <li>
 525 <p></p>
 526 <div class="dlist">
 527 <dl>
 528 <dt class="hdlist1">BITMAP_OPT_FULL_DAG (0x1) REQUIRED: </dt>
 529 <dd>
 530 <p>This flag must always be present. It implies that the
 531 bitmap index has been generated for a packfile or
 532 multi-pack index (MIDX) with full closure (i.e. where
 533 every single object in the packfile/MIDX can find its
 534 parent links inside the same packfile/MIDX). This is a
 535 requirement for the bitmap index format, also present in
 536 JGit, that greatly reduces the complexity of the
 537 implementation.</p>
 538 </dd>
 539 </dl>
 540 </div>
 541 </li>
 542 <li>
 543 <p></p>
 544 <div class="dlist">
 545 <dl>
 546 <dt class="hdlist1">BITMAP_OPT_HASH_CACHE (0x4): </dt>
 547 <dd>
 548 <p>If present, the end of the bitmap file contains
 549 <code>N</code> 32-bit name-hash values, one per object in the
 550 pack/MIDX. The format and meaning of the name-hash is
 551 described below.</p>
 552 </dd>
 553 </dl>
 554 </div>
 555 </li>
 556 <li>
 557 <p></p>
 558 <div class="dlist">
 559 <dl>
 560 <dt class="hdlist1">BITMAP_OPT_LOOKUP_TABLE (0x10): </dt>
 561 <dd>
 562 <p>If present, the end of the bitmap file contains a table
 563 containing a list of <code>N</code> &lt;commit_pos, offset, xor_row&gt;
 564 triplets. The format and meaning of the table is described
 565 below.</p>
 566 <div class="admonitionblock note">
 567 <table>
 568 <tr>
 569 <td class="icon">
 570 <div class="title">Note</div>
 571 </td>
 572 <td class="content">
 573 Unlike the xor_offset used to compress an individual bitmap,
 574 <code>xor_row</code> stores an <strong>absolute</strong> index into the lookup table, not a location
 575 relative to the current entry.
 576 </td>
 577 </tr>
 578 </table>
 579 </div>
 580 </dd>
 581 </dl>
 582 </div>
 583 </li>
 584 </ul>
 585 </div>
 586 </dd>
 587 <dt class="hdlist1">4-byte entry count (network byte order): </dt>
 588 <dd>
 589 <p>The total count of entries (bitmapped commits) in this bitmap index.</p>
 590 </dd>
 591 <dt class="hdlist1">20-byte checksum: </dt>
 592 <dd>
 593 <p>The SHA1 checksum of the pack/MIDX this bitmap index
 594 belongs to.</p>
 595 </dd>
 596 </dl>
 597 </div>
 598 </li>
 599 <li>
 600 <p>4 EWAH bitmaps that act as type indexes</p>
 601 <div class="paragraph">
 602 <p>Type indexes are serialized after the hash cache in the shape
 603 of four EWAH bitmaps stored consecutively (see Appendix A for
 604 the serialization format of an EWAH bitmap).</p>
 605 </div>
 606 <div class="paragraph">
 607 <p>There is a bitmap for each Git object type, stored in the following
 608 order:</p>
 609 </div>
 610 <div class="ulist">
 611 <ul>
 612 <li>
 613 <p>Commits</p>
 614 </li>
 615 <li>
 616 <p>Trees</p>
 617 </li>
 618 <li>
 619 <p>Blobs</p>
 620 </li>
 621 <li>
 622 <p>Tags</p>
 623 </li>
 624 </ul>
 625 </div>
 626 <div class="paragraph">
 627 <p>In each bitmap, the `n`th bit is set to true if the `n`th object
 628 in the packfile or multi-pack index is of that type.</p>
 629 </div>
 630 <div class="paragraph">
 631 <p>The obvious consequence is that the OR of all 4 bitmaps will result
 632 in a full set (all bits set), and the AND of all 4 bitmaps will
 633 result in an empty bitmap (no bits set).</p>
 634 </div>
 635 </li>
 636 <li>
 637 <p>N entries with compressed bitmaps, one for each indexed commit</p>
 638 <div class="paragraph">
 639 <p>Where <code>N</code> is the total number of entries in this bitmap index.
 640 Each entry contains the following:</p>
 641 </div>
 642 <div class="ulist">
 643 <ul>
 644 <li>
 645 <p></p>
 646 <div class="dlist">
 647 <dl>
 648 <dt class="hdlist1">4-byte object position (network byte order): </dt>
 649 <dd>
 650 <p>The position <strong>in the index for the packfile or
 651 multi-pack index</strong> where the bitmap for this commit is
 652 found.</p>
 653 </dd>
 654 </dl>
 655 </div>
 656 </li>
 657 <li>
 658 <p></p>
 659 <div class="dlist">
 660 <dl>
 661 <dt class="hdlist1">1-byte XOR-offset: </dt>
 662 <dd>
 663 <p>The xor offset used to compress this bitmap. For an entry
 664 in position <code>x</code>, an XOR offset of <code>y</code> means that the actual
 665 bitmap representing this commit is composed by XORing the
 666 bitmap for this entry with the bitmap in entry <code>x-y</code> (i.e.
 667 the bitmap <code>y</code> entries before this one).</p>
 668 <div class="admonitionblock note">
 669 <table>
 670 <tr>
 671 <td class="icon">
 672 <div class="title">Note</div>
 673 </td>
 674 <td class="content">
 675 This compression can be recursive. In order to
 676 XOR this entry with a previous one, the previous entry needs
 677 to be decompressed first, and so on.
 678 </td>
 679 </tr>
 680 </table>
 681 </div>
 682 <div class="paragraph">
 683 <p>The hard-limit for this offset is 160 (an entry can only be
 684 xor&#8217;ed against one of the 160 entries preceding it). This
 685 number is always positive, and hence entries are always xor&#8217;ed
 686 with <strong>previous</strong> bitmaps, not bitmaps that will come afterwards
 687 in the index.</p>
 688 </div>
 689 </dd>
 690 </dl>
 691 </div>
 692 </li>
 693 <li>
 694 <p></p>
 695 <div class="dlist">
 696 <dl>
 697 <dt class="hdlist1">1-byte flags for this bitmap: </dt>
 698 <dd>
 699 <p>At the moment the only available flag is <code>0x1</code>, which hints
 700 that this bitmap can be re-used when rebuilding bitmap indexes
 701 for the repository.</p>
 702 </dd>
 703 </dl>
 704 </div>
 705 </li>
 706 <li>
 707 <p>The compressed bitmap itself, see Appendix A.</p>
 708 </li>
 709 </ul>
 710 </div>
 711 </li>
 712 <li>
 713 <p></p>
 714 <div class="dlist">
 715 <dl>
 716 <dt class="hdlist1">TRAILER: </dt>
 717 <dd>
 718 <p>Trailing checksum of the preceding contents.</p>
 719 </dd>
 720 </dl>
 721 </div>
 722 </li>
 723 </ul>
 724 </div>
 725 </div>
 726 </div>
 727 <div class="sect1">
 728 <h2 id="_appendix_a_serialization_format_for_an_ewah_bitmap">Appendix A: Serialization format for an EWAH bitmap</h2>
 729 <div class="sectionbody">
 730 <div class="paragraph">
 731 <p>Ewah bitmaps are serialized in the same protocol as the JAVAEWAH
 732 library, making them backwards compatible with the JGit
 733 implementation:</p>
 734 </div>
 735 <div class="ulist">
 736 <ul>
 737 <li>
 738 <p>4-byte number of bits of the resulting UNCOMPRESSED bitmap</p>
 739 </li>
 740 <li>
 741 <p>4-byte number of words of the COMPRESSED bitmap, when stored</p>
 742 </li>
 743 <li>
 744 <p>N x 8-byte words, as specified by the previous field</p>
 745 <div class="paragraph">
 746 <p>This is the actual content of the compressed bitmap.</p>
 747 </div>
 748 </li>
 749 <li>
 750 <p>4-byte position of the current RLW for the compressed
 751 bitmap</p>
 752 </li>
 753 </ul>
 754 </div>
 755 <div class="paragraph">
 756 <p>All words are stored in network byte order for their corresponding
 757 sizes.</p>
 758 </div>
 759 <div class="paragraph">
 760 <p>The compressed bitmap is stored in a form of run-length encoding, as
 761 follows.  It consists of a concatenation of an arbitrary number of
 762 chunks.  Each chunk consists of one or more 64-bit words</p>
 763 </div>
 764 <div class="literalblock">
 765 <div class="content">
 766 <pre>H  L_1  L_2  L_3 .... L_M</pre>
 767 </div>
 768 </div>
 769 <div class="paragraph">
 770 <p>H is called RLW (run length word).  It consists of (from lower to higher
 771 order bits):</p>
 772 </div>
 773 <div class="ulist">
 774 <ul>
 775 <li>
 776 <p>1 bit: the repeated bit B</p>
 777 </li>
 778 <li>
 779 <p>32 bits: repetition count K (unsigned)</p>
 780 </li>
 781 <li>
 782 <p>31 bits: literal word count M (unsigned)</p>
 783 </li>
 784 </ul>
 785 </div>
 786 <div class="paragraph">
 787 <p>The bitstream represented by the above chunk is then:</p>
 788 </div>
 789 <div class="ulist">
 790 <ul>
 791 <li>
 792 <p>K repetitions of B</p>
 793 </li>
 794 <li>
 795 <p>The bits stored in <code>L_1</code> through <code>L_M</code>.  Within a word, bits at
 796 lower order come earlier in the stream than those at higher
 797 order.</p>
 798 </li>
 799 </ul>
 800 </div>
 801 <div class="paragraph">
 802 <p>The next word after <code>L_M</code> (if any) must again be a RLW, for the next
 803 chunk.  For efficient appending to the bitstream, the EWAH stores a
 804 pointer to the last RLW in the stream.</p>
 805 </div>
 806 </div>
 807 </div>
 808 <div class="sect1">
 809 <h2 id="_appendix_b_optional_bitmap_sections">Appendix B: Optional Bitmap Sections</h2>
 810 <div class="sectionbody">
 811 <div class="paragraph">
 812 <p>These sections may or may not be present in the .<code>bitmap</code> file; their
 813 presence is indicated by the header flags section described above.</p>
 814 </div>
 815 </div>
 816 </div>
 817 <div class="sect1">
 818 <h2 id="_name_hash_cache">Name-hash cache</h2>
 819 <div class="sectionbody">
 820 <div class="paragraph">
 821 <p>If the BITMAP_OPT_HASH_CACHE flag is set, the end of the bitmap contains
 822 a cache of 32-bit values, one per object in the pack/MIDX. The value at
 823 position <code>i</code> is the hash of the pathname at which the `i`th object
 824 (counting in index or multi-pack index order) in the pack/MIDX can be found.
 825 This can be fed into the delta heuristics to compare objects with similar
 826 pathnames.</p>
 827 </div>
 828 <div class="paragraph">
 829 <p>The hash algorithm used is:</p>
 830 </div>
 831 <div class="literalblock">
 832 <div class="content">
 833 <pre>hash = 0;
 834 while ((c = *name++))
 835  if (!isspace(c))
 836   hash = (hash &gt;&gt; 2) + (c &lt;&lt; 24);</pre>
 837 </div>
 838 </div>
 839 <div class="paragraph">
 840 <p>Note that this hashing scheme is tied to the BITMAP_OPT_HASH_CACHE flag.
 841 If implementations want to choose a different hashing scheme, they are
 842 free to do so, but MUST allocate a new header flag (because comparing
 843 hashes made under two different schemes would be pointless).</p>
 844 </div>
 845 </div>
 846 </div>
 847 <div class="sect1">
 848 <h2 id="_commit_lookup_table">Commit lookup table</h2>
 849 <div class="sectionbody">
 850 <div class="paragraph">
 851 <p>If the BITMAP_OPT_LOOKUP_TABLE flag is set, the last <code>N</code> * (<code>4</code> <code>+</code> <code>8</code> <code>+</code> <code>4</code>)
 852 bytes (preceding the name-hash cache and trailing hash) of the .<code>bitmap</code>
 853 file contains a lookup table specifying the information needed to get
 854 the desired bitmap from the entries without parsing previous unnecessary
 855 bitmaps.</p>
 856 </div>
 857 <div class="paragraph">
 858 <p>For a .<code>bitmap</code> containing <code>nr_entries</code> reachability bitmaps, the table
 859 contains a list of <code>nr_entries</code> &lt;commit_pos, offset, xor_row&gt; triplets
 860 (sorted in the ascending order of <code>commit_pos</code>). The content of the i&#8217;th
 861 triplet is -</p>
 862 </div>
 863 <div class="ulist">
 864 <ul>
 865 <li>
 866 <p></p>
 867 <div class="dlist">
 868 <dl>
 869 <dt class="hdlist1">commit_pos (4 byte integer, network byte order): </dt>
 870 <dd>
 871 <p>It stores the object position of a commit (in the midx or pack
 872 index).</p>
 873 </dd>
 874 </dl>
 875 </div>
 876 </li>
 877 <li>
 878 <p></p>
 879 <div class="dlist">
 880 <dl>
 881 <dt class="hdlist1">offset (8 byte integer, network byte order): </dt>
 882 <dd>
 883 <p>The offset from which that commit&#8217;s bitmap can be read.</p>
 884 </dd>
 885 </dl>
 886 </div>
 887 </li>
 888 <li>
 889 <p></p>
 890 <div class="dlist">
 891 <dl>
 892 <dt class="hdlist1">xor_row (4 byte integer, network byte order): </dt>
 893 <dd>
 894 <p>The position of the triplet whose bitmap is used to compress
 895 this one, or <code>0xffffffff</code> if no such bitmap exists.</p>
 896 </dd>
 897 </dl>
 898 </div>
 899 </li>
 900 </ul>
 901 </div>
 902 </div>
 903 </div>
 904 <div class="sect1">
 905 <h2 id="_pseudo_merge_bitmaps">Pseudo-merge bitmaps</h2>
 906 <div class="sectionbody">
 907 <div class="paragraph">
 908 <p>If the <code>BITMAP_OPT_PSEUDO_MERGES</code> flag is set, a variable number of
 909 bytes (preceding the name-hash cache, commit lookup table, and trailing
 910 checksum) of the .<code>bitmap</code> file is used to store pseudo-merge bitmaps.</p>
 911 </div>
 912 <div class="paragraph">
 913 <p>For more information on what pseudo-merges are, why they are useful, and
 914 how to configure them, see the information in <a href="../gitpacking.html">gitpacking(7)</a>.</p>
 915 </div>
 916 <div class="sect2">
 917 <h3 id="_file_format">File format</h3>
 918 <div class="paragraph">
 919 <p>If enabled, pseudo-merge bitmaps are stored in an optional section at
 920 the end of a .<code>bitmap</code> file. The format is as follows:</p>
 921 </div>
 922 <div class="literalblock">
 923 <div class="content">
 924 <pre>+-------------------------------------------+
 925 |               .bitmap File                |
 926 +-------------------------------------------+
 927 |                                           |
 928 |  Pseudo-merge bitmaps (Variable Length)   |
 929 |  +---------------------------+            |
 930 |  | commits_bitmap (EWAH)     |            |
 931 |  +---------------------------+            |
 932 |  | merge_bitmap (EWAH)       |            |
 933 |  +---------------------------+            |
 934 |                                           |
 935 +-------------------------------------------+
 936 |                                           |
 937 |  Lookup Table                             |
 938 |  +---------------------------+            |
 939 |  | commit_pos (4 bytes)      |            |
 940 |  +---------------------------+            |
 941 |  | offset (8 bytes)          |            |
 942 |  +------------+--------------+            |
 943 |                                           |
 944 |  Offset Cases:                            |
 945 |  -------------                            |
 946 |                                           |
 947 |  1. MSB Unset: single pseudo-merge bitmap |
 948 |     + offset to pseudo-merge bitmap       |
 949 |                                           |
 950 |  2. MSB Set: multiple pseudo-merges       |
 951 |     + offset to extended lookup table     |
 952 |                                           |
 953 +-------------------------------------------+
 954 |                                           |
 955 |  Extended Lookup Table (Optional)         |
 956 |  +----+----------+----------+----------+  |
 957 |  | N  | Offset 1 |   ....   | Offset N |  |
 958 |  +----+----------+----------+----------+  |
 959 |  |    |  8 bytes |   ....   |  8 bytes |  |
 960 |  +----+----------+----------+----------+  |
 961 |                                           |
 962 +-------------------------------------------+
 963 |                                           |
 964 |  Pseudo-merge position table              |
 965 |  +----+----------+----------+----------+  |
 966 |  | N  | Offset 1 |   ....   | Offset N |  |
 967 |  +----+----------+----------+----------+  |
 968 |  |    |  8 bytes |   ....   |  8 bytes |  |
 969 |  +----+----------+----------+----------+  |
 970 |                                           |
 971 +-------------------------------------------+
 972 |                                           |
 973 |  Pseudo-merge Metadata                    |
 974 |  +-----------------------------------+    |
 975 |  | # pseudo-merges (4 bytes)         |    |
 976 |  +-----------------------------------+    |
 977 |  | # commits (4 bytes)               |    |
 978 |  +-----------------------------------+    |
 979 |  | Lookup offset (8 bytes)           |    |
 980 |  +-----------------------------------+    |
 981 |  | Extension size (8 bytes)          |    |
 982 |  +-----------------------------------+    |
 983 |                                           |
 984 +-------------------------------------------+</pre>
 985 </div>
 986 </div>
 987 <div class="ulist">
 988 <ul>
 989 <li>
 990 <p>One or more pseudo-merge bitmaps, each containing:</p>
 991 <div class="ulist">
 992 <ul>
 993 <li>
 994 <p><code>commits_bitmap</code>, an EWAH-compressed bitmap describing the set of
 995 commits included in the this psuedo-merge.</p>
 996 </li>
 997 <li>
 998 <p><code>merge_bitmap</code>, an EWAH-compressed bitmap describing the union of
 999 the set of objects reachable from all commits listed in the
1000 <code>commits_bitmap</code>.</p>
1001 </li>
1002 </ul>
1003 </div>
1004 </li>
1005 <li>
1006 <p>A lookup table, mapping pseudo-merged commits to the pseudo-merges
1007 they belong to. Entries appear in increasing order of each commit&#8217;s
1008 bit position. Each entry is 12 bytes wide, and is comprised of the
1009 following:</p>
1010 <div class="ulist">
1011 <ul>
1012 <li>
1013 <p><code>commit_pos</code>, a 4-byte unsigned value (in network byte-order)
1014 containing the bit position for this commit.</p>
1015 </li>
1016 <li>
1017 <p><code>offset</code>, an 8-byte unsigned value (also in network byte-order)
1018 containing either one of two possible offsets, depending on whether or
1019 not the most-significant bit is set.</p>
1020 <div class="ulist">
1021 <ul>
1022 <li>
1023 <p>If unset (i.e. <code>offset</code> &amp; ((<code>uint64_t</code>)<code>1</code>&lt;&lt;63) <code>==</code> <code>0</code>), the offset
1024 (relative to the beginning of the .<code>bitmap</code> file) at which the
1025 pseudo-merge bitmap for this commit can be read. This indicates
1026 only a single pseudo-merge bitmap contains this commit.</p>
1027 </li>
1028 <li>
1029 <p>If set (i.e. <code>offset</code> &amp; ((<code>uint64_t</code>)<code>1</code>&lt;&lt;63) != <code>0</code>), the offset
1030 (again relative to the beginning of the .<code>bitmap</code> file) at which
1031 the extended offset table can be located describing the set of
1032 pseudo-merge bitmaps which contain this commit. This indicates
1033 that multiple pseudo-merge bitmaps contain this commit.</p>
1034 </li>
1035 </ul>
1036 </div>
1037 </li>
1038 </ul>
1039 </div>
1040 </li>
1041 <li>
1042 <p>An (optional) extended lookup table (written if and only if there is
1043 at least one commit which appears in more than one pseudo-merge).
1044 There are as many entries as commits which appear in multiple
1045 pseudo-merges. Each entry contains the following:</p>
1046 <div class="ulist">
1047 <ul>
1048 <li>
1049 <p><code>N</code>, a 4-byte unsigned value equal to the number of pseudo-merges
1050 which contain a given commit.</p>
1051 </li>
1052 <li>
1053 <p>An array of <code>N</code> 8-byte unsigned values, each of which is
1054 interpreted as an offset (relative to the beginning of the
1055 .<code>bitmap</code> file) at which a pseudo-merge bitmap for this commit can
1056 be read. These values occur in no particular order.</p>
1057 </li>
1058 </ul>
1059 </div>
1060 </li>
1061 <li>
1062 <p>Positions for all pseudo-merges, each stored as an 8-byte unsigned
1063 value (in network byte-order) containing the offset (relative to the
1064 beginning of the .<code>bitmap</code> file) of each consecutive pseudo-merge.</p>
1065 </li>
1066 <li>
1067 <p>A 4-byte unsigned value (in network byte-order) equal to the number of
1068 pseudo-merges.</p>
1069 </li>
1070 <li>
1071 <p>A 4-byte unsigned value (in network byte-order) equal to the number of
1072 unique commits which appear in any pseudo-merge.</p>
1073 </li>
1074 <li>
1075 <p>An 8-byte unsigned value (in network byte-order) equal to the number
1076 of bytes between the start of the pseudo-merge section and the
1077 beginning of the lookup table.</p>
1078 </li>
1079 <li>
1080 <p>An 8-byte unsigned value (in network byte-order) equal to the number
1081 of bytes in the pseudo-merge section (including this field).</p>
1082 </li>
1083 </ul>
1084 </div>
1085 </div>
1086 </div>
1087 </div>
1088 </div>
1089 <div id="footer">
1090 <div id="footer-text">
1091 Last updated 2024-06-24 17:32:59 -0700
1092 </div>
1093 </div>
1094 </body>
1095 </html>