On 6/26/2022 9:10 AM, Abhradeep Chakraborty via GitGitGadget wrote:
> From: Abhradeep Chakraborty <chakrabortyabhradeep79@xxxxxxxxx>
>
> The bitmap lookup table extension was documentated by an earlier
s/documentated/documented/
> change, but Git does not yet knowhow to write that extension.
s/knowhow/know how/
> +static int table_cmp(const void *_va, const void *_vb, void *commit_positions)
> +{
> + int8_t result = 0;
> + uint32_t *positions = (uint32_t *) commit_positions;
nit: drop the space between the cast and commit_positions.
> + uint32_t a = positions[*(uint32_t *)_va];
> + uint32_t b = positions[*(uint32_t *)_vb];
> +
> + if (a > b)
> + result = 1;
> + else if (a < b)
> + result = -1;
> + else
> + result = 0;
> +
> + return result;
> +}
Ok, here you are sorting by commit OID (indirectly by the order in the
[multi-]pack-index). I suppose that I misunderstood in the previous
patch, so that could use some more specific language, maybe.
> +static void write_lookup_table(struct hashfile *f,
> + uint64_t *offsets,
> + uint32_t *commit_positions)
> +{
> + uint32_t i;
> + uint32_t *table, *table_inv;
> +
> + ALLOC_ARRAY(table, writer.selected_nr);
> + ALLOC_ARRAY(table_inv, writer.selected_nr);
> +
> + for (i = 0; i < writer.selected_nr; i++)
> + table[i] = i;
> +
> + QSORT_S(table, writer.selected_nr, table_cmp, commit_positions);
At the end of this sort, table[j] = i means that the ith bitmap corresponds
to the jth bitmapped commit in lex order of OIDs.
> + for (i = 0; i < writer.selected_nr; i++)
> + table_inv[table[i]] = i;
And table_inv helps us discover that relationship (ith bitmap to jth commit
by j = table_inv[i]).
> + for (i = 0; i < writer.selected_nr; i++) {
> + struct bitmapped_commit *selected = &writer.selected[table[i]];
> + uint32_t xor_offset = selected->xor_offset;
Here, xor_offset is "number of bitmaps in relationship to the current bitmap"
> + hashwrite_be32(f, commit_positions[table[i]]);
> + hashwrite_be64(f, offsets[table[i]]);
> + hashwrite_be32(f, xor_offset ?
> + table_inv[table[i] - xor_offset]: 0xffffffff);
Which means that if "k = table[i] - xor_offset" that the xor base is the kth
bitmap. table_inv[k] gets us the position in this table of that bitmap's
commit.
(It's also strange to me that the offset is being _subtracted_, but I guess
the bitmap format requires the xor base to appear first so the offset does
not need to be a negative number ever.)
This last line is a bit complex.
uint32_t xor_offset = selected->xor_offset;
uint32_t xor_row = 0xffffffff;
if (xor_offset) {
uint32_t xor_order = table[i] - xor_offset;
xor_row = table_inf[xor_order];
}
...then we can "hashwrite_be32(f, xor_row);" when necessary. I'm not sure
that we need the "uint32_t xor_order" inside the "if (xor_offset)" block,
but splitting it helps add clarity to the multi-step computation.
> enum pack_bitmap_opts {
> - BITMAP_OPT_FULL_DAG = 1,
> - BITMAP_OPT_HASH_CACHE = 4,
> + BITMAP_OPT_FULL_DAG = 0x1,
> + BITMAP_OPT_HASH_CACHE = 0x4,
> + BITMAP_OPT_LOOKUP_TABLE = 0x10,
> };
Excellent.
Thanks,
-Stolee
