pack v4: initial pack dictionary structure and code

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
export packed_object_info()

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: scan tree objects

Let's read a pack to feed our dictionary with all the path strings
contained in all the tree objects.

Dump the resulting dictionary sorted by frequency to stdout.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: add tree entry mode support to dictionary entries

Augment dict entries with a 16-bit prefix in order to store the file
mode value of tree entries.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: add commit object parsing

Let's create another dictionary table to hold the author and committer
entries.  We use the same table format used for tree entries where the
16 bit data prefix is conveniently used to store the timezone value.

In order to copy straight from a commit object buffer, dict_add_entry()
is modified to get the string length as the provided string pointer is
not always be null terminated.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: split the object list and dictionary creation

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: move to struct pack_idx_entry and get rid of our own struct idx_entry

Let's create a struct pack_idx_entry list with sorted sha1 which will
be useful later.  The offset sorted list is now a separate indirect
list.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: basic SHA1 reference encoding

The SHA1 reference is either an index into a SHA1 table using the variable
length number encoding, or the literal 20 bytes SHA1 prefixed with a 0.

The index 0 discriminates between an actual index value or the literal
SHA1.  Therefore when the index is used its value must be increased by 1.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
introduce get_sha1_lowhex()

This is like get_sha1_hex() but stricter in accepting lowercase letters
only.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: commit object encoding

This goes as follows:

- Tree reference: either variable length encoding of the index
  into the SHA1 table or the literal SHA1 prefixed by 0 (see
  encode_sha1ref()).

- Parent count: variable length encoding of the number of parents.
  This is normally going to occupy a single byte but doesn't have to.

- List of parent references: a list of encode_sha1ref() encoded
  references, or nothing if the parent count was zero.

- Committer time stamp: variable length encoded.  Year 2038 ready!
  Unlike the canonical representation, this is stored close to the
  list of parents so the important data for history traversal can be
  retrieved without parsing the rest of the object.

- Committer reference: variable length encoding of an index into the
  ident dictionary table which also covers the time zone.  To make
  the overall encoding efficient, the ident table is sorted by usage
  frequency so the most used entries are first and require the shortest
  index encoding.

- Author time stamp: encoded as a difference against the committer
  time stamp, with the LSB used to indicate commit time is behind
  author time.

- Author reference: same as committer reference.

The remainder of the canonical commit object content is then zlib
compressed and appended to the above.

Rationale: The most important commit object data is densely encoded while
requiring no zlib inflate processing on access, and all SHA1 references
are most likely to be direct indices into the pack index file requiring
no SHA1 search into the pack index file.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>

create_commit

create_commit
pack v4: tree object encoding

This goes as follows:

- Number of tree entries: variable length encoded.

Then for each tree entry:

- Path component reference: variable length encoded index into the path
  dictionary table which also covers the entry mode. To make the overall
  encoding efficient, the path table is already sorted by usage frequency
  so the most used path names are first and require the shortest index
  encoding.

- SHA1 reference: either variable length encoding of the index into the
  SHA1 table or the literal SHA1 prefixed by 0 (see encode_sha1ref()).

Rationale: all the tree object data is densely encoded while requiring
no zlib inflate processing on access, and all SHA1 references are most
likely to be direct indices into the pack index file requiring no SHA1
search.  Path filtering can be accomplished on the path index directly
without any string comparison during the tree traversal.

Still lacking is some kind of delta encoding for multiple tree objects
with only small differences between them.  But that'll come later.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: dictionary table output

Here's the code to dump a table into a pack.  Table entries are written
according to the current sort order. This is important as objects use
this order to index into the table.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: creation code

Let's actually open the destination pack file and write the header and
the tables.

The header isn't much different from pack v3, except for the pack version
number of course.

The first table is the sorted SHA1 table normally found in the pack index
file.  With pack v4 we write this table in the main pack file instead as
it is index referenced by subsequent objects in the pack.  Doing so has
many advantages:

- The SHA1 references used to be duplicated on disk: once in the pack
  index file, and then at least once or more within commit and tree
  objects referencing them.  The only SHA1 which is not being listed more
  than once this way is the one for a branch tip commit object and those
  are normally very few.  Now all that SHA1 data is represented only once.

- The SHA1 references found in commit and tree objects can be obtained
  on disk directly without having to deflate those objects first.

The SHA1 table size is obtained by multiplying the number of objects by 20.

And then the commit and path dictionary tables are written right after
the SHA1 table.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: object headers

In pack v4 the object size and type is encoded differently from pack v3.
The object size uses the same efficient variable length number encoding
already used elsewhere.

The object type has 4 bits allocated to it compared to 3 bits in pack v3.
This should be quite sufficient for the foreseeable future, especially
since pack v4 has only one type of delta object instead of two.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: object data copy

Blob and tag objects have no particular changes except for their object
header.

Delta objects are also copied as is, except for their delta base reference
which is converted to the new way as used elsewhere in pack v4 encoding
i.e. an index into the SHA1 table or a literal SHA1 prefixed by 0 if not
found in the table (see encode_sha1ref).  This is true for both REF_DELTA
as well as OFS_DELTA.

Object payload is validated against the recorded CRC32 in the source
pack index file when possible before being copied.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: object writing

This adds the missing code to finally be able to produce a complete
pack file version 4.  We trap commit and tree objects as those have
a completely new encoding.  Other object types are copied almost
unchanged.

As we go the pack index entries are updated  in place to store the new
object offsets once they're written to the destination file.  This will
be needed later for writing the pack index file.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: tree object delta encoding

In order to be able to quickly walk tree objects, let's encode their
"delta" as a range of entries into another tree object.

In order to discriminate between a copy sequence from a regular entry,
the entry index LSB is reserved to indicate a copy sequence.  Therefore
the actual index of a path component is shifted left one bit.

The encoding allows for the base object to change so multiple base
objects can be borrowed from.  The code doesn't try to exploit this
possibility at the moment though.

The code isn't optimal at the moment as it doesn't consider the case
where a copy sequence could be larger than the local sequence it
means to replace.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: load delta candidate for encoding tree objects

The SHA1 of the base object is retrieved and the corresponding object
is loaded in memory for pv4_encode_tree() to look at.  Simple but
effective.  Obviously this relies on the delta matching already performed
during the pack v3 delta search.  Some native delta search for pack v4
could be investigated eventually.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
packv4-create: optimize delta encoding

Make sure the copy sequence is smaller than the list of tree entries it
is meant to replace.  We do so by encoding tree entries in parallel with
the delta entry comparison, and then comparing the length of both
sequences.

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
pack v4: honor pack.compression config option

Signed-off-by: Nicolas Pitre <nico@fluxnic.net>