{"thread":{"id":"50455","subject":"Confusion about the PACK format","startedAt":"2019-02-10T16:03:46Z","lastAt":"2019-02-12T00:41:34Z","messageCount":4,"participants":["Florian Steenbuck","Ramsay Jones","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"368978","messageId":"CAA4q8U5JD1tA0KH1nxAhN1AuqYeB-Y5UGqXzichx-ZCipDKsgQ@mail.gmail.com","threadId":"50455","inReplyTo":null,"subject":"Confusion about the PACK format","fromName":"Florian Steenbuck","fromEmail":"steenbuckflorian@gmail.com","sentAt":"2019-02-10T16:02:16Z","receivedAt":"2019-02-10T16:03:46Z","isPatch":false,"sender":{"key":"steenbuckflorian@gmail.com","avatar":null},"body":"Hello to all,\n\nI try to understand the git protocol only on the server site. So I\nstart without reading any docs and which turns to be fine until I got\nto the PACK format (pretty early failure I know).\n\nI have read this documentation:\nhttps://raw.githubusercontent.com/git/git/c4df23f7927d8d00e666a3c8d1b3375f1dc8a3c1/Documentation/technical/pack-format.txt\n\nBut their are some confusion about this text.\n\nThe basic header is no problem, but somehow I got stuck while try to\nread the length and type of the objects, which are ints that can be\nresolved with 3-bits and 4-bits. The question is where and how ?\n\nI try to parse the int from the beginning of the bits:\n1 | 2 | 3 | 4 | 5 | 6 | 7 | 8\n1 - 3 = type\n4 - 7 = len\n(I using a python way to convert it to a int which is equal to:\nint('{0:08b}'.format(raw_objects[offset])[x:y], 2)\n)\nAs mentioned in the doc n is part of the len calculation. Question of\ninterest why ? And what is n ?\nI interpreted it as the type as it is a number and prefixed with n-byte.\n\nThis requires me to do one more step:\nlen = (type-1)*len\n\nWhich ends in a endless loop, because my byte offset never hits the\nend of, caused by often type that is 0.\n\nI then try to interpret it in a different way so I now take two bytes\nand on every byte I take the end of the bits for get the type and len:\n\nbyte a (equal to [offset+0])\n1 | 2 | 3 | 4 | 5 | 6 | 7 | 8\n6 - 8 = type\n\nbyte b (equal to [offset+1])\n1 | 2 | 3 | 4 | 5 | 6 | 7 | 8\n5 - 8 = len\n\nWhich in my case stops the endless loop, but seems to not get correct\ntyping, zero and five types appears everywhere, and not get the\ncorrect size of the object, I use the length that I calculate before.\nTheir are multiple errors that appears while try to decompress the\ndata.\n\nNow to complete other topic error handling, what is the suggest way to\nhandle a type 0 or type 5 and what is with type < 0 and type > 5 ?\n\nType 0 is invalid, should the parsing fail here ?\nType 5 is reserved for future expansion, where should we continue then ?\n\nAlso I do not understand this:\n`a negative relative offset from the delta object's position in the\npack if thisis an OBJ_OFS_DELTA object`\nWhat relative offset I need to check here ?\n\nKind Regards\nFlorian\n"},{"id":"368981","messageId":"e9a8ae8d-6f4a-5595-0287-80bf31923abf@ramsayjones.plus.com","threadId":"50455","inReplyTo":"CAA4q8U5JD1tA0KH1nxAhN1AuqYeB-Y5UGqXzichx-ZCipDKsgQ@mail.gmail.com","subject":"Re: Confusion about the PACK format","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2019-02-10T19:05:56Z","receivedAt":"2019-02-10T19:05:59Z","isPatch":false,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 10/02/2019 16:02, Florian Steenbuck wrote:\n> Hello to all,\n> \n> I try to understand the git protocol only on the server site. So I\n> start without reading any docs and which turns to be fine until I got\n> to the PACK format (pretty early failure I know).\n> \n> I have read this documentation:\n> https://raw.githubusercontent.com/git/git/c4df23f7927d8d00e666a3c8d1b3375f1dc8a3c1/Documentation/technical/pack-format.txt\n> \n> But their are some confusion about this text.\n> \n> The basic header is no problem, but somehow I got stuck while try to\n> read the length and type of the objects, which are ints that can be\n> resolved with 3-bits and 4-bits. The question is where and how ?\n> \n\nHmm, the 'type and length' encoding could be described more clearly!\nHopefully, just on this issue, the following could help:\n\nIn my git.git repo, which is fully packed, I have a single pack file, with\n\n  $ git count-objects -v\n  count: 0\n  size: 0\n  in-pack: 270277\n  packs: 1\n  size-pack: 101929\n  prune-packable: 0\n  garbage: 0\n  size-garbage: 0\n  $ \n\n... 270277 objects in it. The beginning of the file looks like:\n\n  $ xxd .git/objects/pack/pack-d554e6d8335601c2525b40487faf36493094ab50.pack | head\n  00000000: 5041 434b 0000 0002 0004 1fc5 9d13 789c  PACK..........x.\n  00000010: 9d8f cd6a c330 1084 ef7a 8a3d 171a b4ab  ...j.0...z.=....\n  00000020: 9525 8750 0abd 945c f304 ab95 5cfb 602b  .%.P...\\....\\.`+\n  00000030: b84a 7fde 3e2a 943e 406f c3f0 cd30 d3f6  .J..>*.>@o...0..\n  00000040: 5260 741a 5025 92e2 1458 917c c294 a3c3  R`t.P%...X.|....\n  00000050: 4803 e521 395f c2d8 4d73 95bd 6c0d 82f5  H..!9_..Ms..l...\n  00000060: 6172 310f 0529 7a2f d6a7 40c5 d9a0 d185  ar1..)z/..@.....\n  00000070: 622d 8789 9cb8 3f1e 5132 6366 4de4 8531  b-....?.Q2cfM..1\n  00000080: 114a 70ec 9447 2f5a 526f e29c 3847 23b7  .Jp..G/ZRo..8G#.\n  00000090: 36d7 1dce b76d a9f0 02af b2ca 56e1 f4b6  6....m......V...\n  $ \n\nYou can see the header, which consists of 3 32-bit values, where the\npackfile signature is the '5041 434b', then the version number which\nis '0000 0002', followed by the number of objects '0004 1fc5' which\nis 270277. Next comes the first 'object entry', which starts '9d13'.\n\nNow, the 'n-byte type and length' is a variable length encoding of\nthe object type and length. The number of bytes used to encode this\ndata is content dependant. If the top bit of a byte is set, then we\nneed to process the next byte, otherwise we are done. So, looking\nat the first 'object entry' byte (at offset 12) '9d', we take the\ntop nibble, remove the top bit, and shift right 4 bits to get the\nobject type. ie. (0x9d >> 4) & 7 which gives an object type of 1\n(which is a commit object). The lower nibble of the first byte\ncontains the first (or only) 4 bits of the size, here (0x9d & 15)\nwhich is 0xd. Given that the top bit of this byte is set, we now\nprocess the next byte. After the first byte, each byte contains 7\nbits of the size field which is combined with the value from the\nprevious byte by shifting and adding (first by 4 bits, then 11, 18,\n25 etc.). So, in this case we have (0x13 << 4) + 0xd = 317.\n\nThe compressed data follows, '789c' ...\n\nWe can use git-verify-pack to confirm the details here:\n\n  $ git verify-pack -v .git/objects/pack/pack-d554e6d8335601c2525b40487faf36493094ab50.idx | head -n 1\n  878e2cd30e1656909c5073043d32fe9d02204daa commit 317 216 12\n  $ \n \nSo the object 878e2cd30e, at offset 12 in the file, is a commit object\nwith size 317 (which has an in-pack size of 216).\n\nHope this helps.\n\nATB,\nRamsay Jones\n\n"},{"id":"368984","messageId":"a0e1ad5b-8d6b-7fa0-54f3-dc0b4b275533@ramsayjones.plus.com","threadId":"50455","inReplyTo":"e9a8ae8d-6f4a-5595-0287-80bf31923abf@ramsayjones.plus.com","subject":"Re: Confusion about the PACK format","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsayjones.plus.com","sentAt":"2019-02-10T19:35:38Z","receivedAt":"2019-02-10T19:35:41Z","isPatch":false,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\n\nOn 10/02/2019 19:05, Ramsay Jones wrote:\n> \n> \n> On 10/02/2019 16:02, Florian Steenbuck wrote:\n>> Hello to all,\n>>\n>> I try to understand the git protocol only on the server site. So I\n>> start without reading any docs and which turns to be fine until I got\n>> to the PACK format (pretty early failure I know).\n>>\n>> I have read this documentation:\n>> https://raw.githubusercontent.com/git/git/c4df23f7927d8d00e666a3c8d1b3375f1dc8a3c1/Documentation/technical/pack-format.txt\n>>\n>> But their are some confusion about this text.\n>>\n>> The basic header is no problem, but somehow I got stuck while try to\n>> read the length and type of the objects, which are ints that can be\n>> resolved with 3-bits and 4-bits. The question is where and how ?\n>>\n> \n> Hmm, the 'type and length' encoding could be described more clearly!\n> Hopefully, just on this issue, the following could help:\n> \n> In my git.git repo, which is fully packed, I have a single pack file, with\n> \n>   $ git count-objects -v\n>   count: 0\n>   size: 0\n>   in-pack: 270277\n>   packs: 1\n>   size-pack: 101929\n>   prune-packable: 0\n>   garbage: 0\n>   size-garbage: 0\n>   $ \n> \n> ... 270277 objects in it. The beginning of the file looks like:\n> \n>   $ xxd .git/objects/pack/pack-d554e6d8335601c2525b40487faf36493094ab50.pack | head\n>   00000000: 5041 434b 0000 0002 0004 1fc5 9d13 789c  PACK..........x.\n>   00000010: 9d8f cd6a c330 1084 ef7a 8a3d 171a b4ab  ...j.0...z.=....\n>   00000020: 9525 8750 0abd 945c f304 ab95 5cfb 602b  .%.P...\\....\\.`+\n>   00000030: b84a 7fde 3e2a 943e 406f c3f0 cd30 d3f6  .J..>*.>@o...0..\n>   00000040: 5260 741a 5025 92e2 1458 917c c294 a3c3  R`t.P%...X.|....\n>   00000050: 4803 e521 395f c2d8 4d73 95bd 6c0d 82f5  H..!9_..Ms..l...\n>   00000060: 6172 310f 0529 7a2f d6a7 40c5 d9a0 d185  ar1..)z/..@.....\n>   00000070: 622d 8789 9cb8 3f1e 5132 6366 4de4 8531  b-....?.Q2cfM..1\n>   00000080: 114a 70ec 9447 2f5a 526f e29c 3847 23b7  .Jp..G/ZRo..8G#.\n>   00000090: 36d7 1dce b76d a9f0 02af b2ca 56e1 f4b6  6....m......V...\n>   $ \n> \n> You can see the header, which consists of 3 32-bit values, where the\n> packfile signature is the '5041 434b', then the version number which\n> is '0000 0002', followed by the number of objects '0004 1fc5' which\n> is 270277. Next comes the first 'object entry', which starts '9d13'.\n> \n> Now, the 'n-byte type and length' is a variable length encoding of\n> the object type and length. The number of bytes used to encode this\n> data is content dependant. If the top bit of a byte is set, then we\n> need to process the next byte, otherwise we are done. So, looking\n> at the first 'object entry' byte (at offset 12) '9d', we take the\n> top nibble, remove the top bit, and shift right 4 bits to get the\n> object type. ie. (0x9d >> 4) & 7 which gives an object type of 1\n> (which is a commit object). The lower nibble of the first byte\n> contains the first (or only) 4 bits of the size, here (0x9d & 15)\n> which is 0xd. Given that the top bit of this byte is set, we now\n> process the next byte. After the first byte, each byte contains 7\n> bits of the size field which is combined with the value from the\n> previous byte by shifting and adding (first by 4 bits, then 11, 18,\n> 25 etc.). So, in this case we have (0x13 << 4) + 0xd = 317.\n\nSorry, to be clear, I should have said, \"mask off the top bit,\nshift and add\", so:\n\n  ((0x13 & 0x7f) << 4) + 0xd = 317\n\nATB,\nRamsay Jones\n\n> \n> The compressed data follows, '789c' ...\n> \n> We can use git-verify-pack to confirm the details here:\n> \n>   $ git verify-pack -v .git/objects/pack/pack-d554e6d8335601c2525b40487faf36493094ab50.idx | head -n 1\n>   878e2cd30e1656909c5073043d32fe9d02204daa commit 317 216 12\n>   $ \n>  \n> So the object 878e2cd30e, at offset 12 in the file, is a commit object\n> with size 317 (which has an in-pack size of 216).\n> \n> Hope this helps.\n> \n> ATB,\n> Ramsay Jones\n> \n> \n"},{"id":"369075","messageId":"20190212004130.GI13301@sigill.intra.peff.net","threadId":"50455","inReplyTo":"a0e1ad5b-8d6b-7fa0-54f3-dc0b4b275533@ramsayjones.plus.com","subject":"Re: Confusion about the PACK format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2019-02-12T00:41:30Z","receivedAt":"2019-02-12T00:41:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Feb 10, 2019 at 07:35:38PM +0000, Ramsay Jones wrote:\n\n> > Now, the 'n-byte type and length' is a variable length encoding of\n> > the object type and length. The number of bytes used to encode this\n> > data is content dependant. If the top bit of a byte is set, then we\n> > need to process the next byte, otherwise we are done. So, looking\n> > at the first 'object entry' byte (at offset 12) '9d', we take the\n> > top nibble, remove the top bit, and shift right 4 bits to get the\n> > object type. ie. (0x9d >> 4) & 7 which gives an object type of 1\n> > (which is a commit object). The lower nibble of the first byte\n> > contains the first (or only) 4 bits of the size, here (0x9d & 15)\n> > which is 0xd. Given that the top bit of this byte is set, we now\n> > process the next byte. After the first byte, each byte contains 7\n> > bits of the size field which is combined with the value from the\n> > previous byte by shifting and adding (first by 4 bits, then 11, 18,\n> > 25 etc.). So, in this case we have (0x13 << 4) + 0xd = 317.\n> \n> Sorry, to be clear, I should have said, \"mask off the top bit,\n> shift and add\", so:\n> \n>   ((0x13 & 0x7f) << 4) + 0xd = 317\n\nYes. Also, see the first 10 or so lines of builtin/index-pack.c's\nunpack_raw_entry() for real-world example code.\n\n-Peff\n"}]}