git@vger.kernel.org mailing list mirror (one of many)
 help / color / mirror / code / Atom feed
From: Jeff King <peff@peff.net>
To: Erik Fastermann <erik@fastermann.de>
Cc: git@vger.kernel.org
Subject: Re: Question about the pack OBJ_OFS_DELTA format
Date: Fri, 10 Jan 2020 04:57:07 -0500	[thread overview]
Message-ID: <20200110095707.GA459765@coredump.intra.peff.net> (raw)
In-Reply-To: <1032627506.120165.1578644787174@email.ionos.de>

On Fri, Jan 10, 2020 at 09:26:27AM +0100, Erik Fastermann wrote:

> I get: ee 01 8c 63
> 
> The first two bytes, the type and the size are correctly computed.
> 
> So the next varint should be the offset.
> 
> 8c: 10001100 --- 63: 01100011
> 
> -> 1100011_0001100
> 
> -> 12684 ???
> 
> The result is the same when calculating it manually and with my program.

The pack-format.txt file says:

       offset encoding:
            n bytes with MSB set in all but the last one.
            The offset is then the number constructed by
            concatenating the lower 7 bit of each byte, and
            for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))
            to the result.

but I think is missing two bits of information:

  - the bytes are in most-significant to least-significant order, which
    IIRC is the opposite of the size varint

  - each 7-bit byte sneaks in some extra data by implicitly adding "1"
    to all but the last byte

So the low seven bits of "8c" is "12". Add one and multiply by 2^7 gets
you 1664. The low seven of "63" is 99. No addition or multiply because
it's the last byte.

The result is 1763, which is what you expected.

It does seem like the documentation could be a lot better. I had to dig
into the source (packfile.c:get_delta_base is pretty clear, but if
you're trying to do a non-GPL clean-room implementation, then obviously
don't look at it).

-Peff

  reply	other threads:[~2020-01-10  9:57 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-01-10  8:26 Question about the pack OBJ_OFS_DELTA format Erik Fastermann
2020-01-10  9:57 ` Jeff King [this message]
2020-01-10 13:56   ` Erik Fastermann
2020-01-10 19:41   ` Junio C Hamano
2020-01-11  9:56     ` Jeff King

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: http://vger.kernel.org/majordomo-info.html

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20200110095707.GA459765@coredump.intra.peff.net \
    --to=peff@peff.net \
    --cc=erik@fastermann.de \
    --cc=git@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://80x24.org/mirrors/git.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).