{"thread":{"id":"52611","subject":"Question about the pack OBJ_OFS_DELTA format","startedAt":"2020-01-10T08:26:30Z","lastAt":"2020-01-11T09:56:06Z","messageCount":5,"participants":["Erik Fastermann","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"389568","messageId":"1032627506.120165.1578644787174@email.ionos.de","threadId":"52611","inReplyTo":null,"subject":"Question about the pack OBJ_OFS_DELTA format","fromName":"Erik Fastermann","fromEmail":"erik@fastermann.de","sentAt":"2020-01-10T08:26:27Z","receivedAt":"2020-01-10T08:26:30Z","isPatch":false,"sender":{"key":"erik@fastermann.de","avatar":null},"body":"Hi all,\n\nI'm trying to implement the Git pack format. Parsing the index file and\nunpacking undeltified objects already works. However I'm unable to get\nthe offset, if the type is OBJ_OFS_DELTA.\n\nThe very much work-in-progress Go code and data can be found here:\nhttps://github.com/erikfastermann/notes/tree/wip/git\n\nFrom the docs (https://git-scm.com/docs/pack-format) I assume, that\nthe offset is a variable length integer, like the size.  However my\ncaclulation leads to a illogical result.\n\nWhen trying the hash 8c40ff4767d973b672fe5aa431cb8ba0593dd26a with:\n\ngit verify-pack -v pack.pack\n\nI get: offset: 138650 size: 30.\n\nThe base object 9b25d441c1bf358af01edc4eeba65870581a5ac1 (shown by\nverify-pack) has the offset 136887, which I think means the delta should\nbe: 138650 - 136887 = 1763.\n\nUsing the command:\n\ndd skip=138650 count=4 if=pack.pack bs=1 status=none | hexdump -C\n\nI get: ee 01 8c 63\n\nThe first two bytes, the type and the size are correctly computed.\n\nSo the next varint should be the offset.\n\n8c: 10001100 --- 63: 01100011\n\n-> 1100011_0001100\n\n-> 12684 ???\n\nThe result is the same when calculating it manually and with my program.\n\nI probably have some crucial misunderstanding about the format, so a\nclarification would be nice.\n\nThank you for your help.\n\nErik\n"},{"id":"389571","messageId":"20200110095707.GA459765@coredump.intra.peff.net","threadId":"52611","inReplyTo":"1032627506.120165.1578644787174@email.ionos.de","subject":"Re: Question about the pack OBJ_OFS_DELTA format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-10T09:57:07Z","receivedAt":"2020-01-10T09:57:10Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 10, 2020 at 09:26:27AM +0100, Erik Fastermann wrote:\n\n> I get: ee 01 8c 63\n> \n> The first two bytes, the type and the size are correctly computed.\n> \n> So the next varint should be the offset.\n> \n> 8c: 10001100 --- 63: 01100011\n> \n> -> 1100011_0001100\n> \n> -> 12684 ???\n> \n> The result is the same when calculating it manually and with my program.\n\nThe pack-format.txt file says:\n\n       offset encoding:\n            n bytes with MSB set in all but the last one.\n            The offset is then the number constructed by\n            concatenating the lower 7 bit of each byte, and\n            for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))\n            to the result.\n\nbut I think is missing two bits of information:\n\n  - the bytes are in most-significant to least-significant order, which\n    IIRC is the opposite of the size varint\n\n  - each 7-bit byte sneaks in some extra data by implicitly adding \"1\"\n    to all but the last byte\n\nSo the low seven bits of \"8c\" is \"12\". Add one and multiply by 2^7 gets\nyou 1664. The low seven of \"63\" is 99. No addition or multiply because\nit's the last byte.\n\nThe result is 1763, which is what you expected.\n\nIt does seem like the documentation could be a lot better. I had to dig\ninto the source (packfile.c:get_delta_base is pretty clear, but if\nyou're trying to do a non-GPL clean-room implementation, then obviously\ndon't look at it).\n\n-Peff\n"},{"id":"389581","messageId":"1429594513.146357.1578664568182@email.ionos.de","threadId":"52611","inReplyTo":"20200110095707.GA459765@coredump.intra.peff.net","subject":"Re: Question about the pack OBJ_OFS_DELTA format","fromName":"Erik Fastermann","fromEmail":"erik@fastermann.de","sentAt":"2020-01-10T13:56:08Z","receivedAt":"2020-01-10T13:56:12Z","isPatch":false,"sender":{"key":"erik@fastermann.de","avatar":null},"body":"Thanks mate. That helped me a lot.\n\nErik\n"},{"id":"389593","messageId":"xmqq1rs7m757.fsf@gitster-ct.c.googlers.com","threadId":"52611","inReplyTo":"20200110095707.GA459765@coredump.intra.peff.net","subject":"Re: Question about the pack OBJ_OFS_DELTA format","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-01-10T19:41:08Z","receivedAt":"2020-01-10T19:41:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> The pack-format.txt file says:\n>\n>        offset encoding:\n>             n bytes with MSB set in all but the last one.\n>             The offset is then the number constructed by\n>             concatenating the lower 7 bit of each byte, and\n>             for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))\n>             to the result.\n>\n> but I think is missing two bits of information:\n>\n>   - the bytes are in most-significant to least-significant order, which\n>     IIRC is the opposite of the size varint\n>\n>   - each 7-bit byte sneaks in some extra data by implicitly adding \"1\"\n>     to all but the last byte\n\nIsn't the latter mentioned in the paragraph you quoted?\n"},{"id":"389606","messageId":"20200111095604.GA1605786@coredump.intra.peff.net","threadId":"52611","inReplyTo":"xmqq1rs7m757.fsf@gitster-ct.c.googlers.com","subject":"Re: Question about the pack OBJ_OFS_DELTA format","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-01-11T09:56:04Z","receivedAt":"2020-01-11T09:56:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 10, 2020 at 11:41:08AM -0800, Junio C Hamano wrote:\n\n> Jeff King <peff@peff.net> writes:\n> \n> > The pack-format.txt file says:\n> >\n> >        offset encoding:\n> >             n bytes with MSB set in all but the last one.\n> >             The offset is then the number constructed by\n> >             concatenating the lower 7 bit of each byte, and\n> >             for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))\n> >             to the result.\n> >\n> > but I think is missing two bits of information:\n> >\n> >   - the bytes are in most-significant to least-significant order, which\n> >     IIRC is the opposite of the size varint\n> >\n> >   - each 7-bit byte sneaks in some extra data by implicitly adding \"1\"\n> >     to all but the last byte\n> \n> Isn't the latter mentioned in the paragraph you quoted?\n\nHmm, yeah. I admit I had trouble parsing exactly what that part was\ntrying to say, and thought it was trying to talk about how you'd shift\nthe individual bytes. But reading more carefully, it does say \"adding\",\nso yeah, it accounts for the extra.\n\nIt's a little confusing, I think, because in code you'd add just\ncontinually add one before shifting, rather than trying to add in the\nextra values at the end.\n\n-Peff\n"}]}