Re: [PATCH 11/14] object-name: simplify computing common prefixes
- From
Karthik Nayak <karthik.188@gmail.com>
- Date
- Mar 20, 2026, 10:01 UTC
- Message-ID
- <CAOLa=ZRU3=FqDo8SiJ=+qTsU79NEfoyAVp1uZYBX57SNPTZomw@mail.gmail.com>
- In-Reply-To
- <20260319-b4-pks-odb-source-abbrev-v1-11-5ddebad292b0@pks.im>
Patrick Steinhardt <ps@pks.im> writes:
Show 42 quoted lines
> The function `extend_abbrev_len()` computes the length of common hex
> characters between two object IDs. This is done by:
>
> - Making the caller provide the `hex` string for the needle object ID.
>
> - Comparing every hex position of the haystack object ID with
> `get_hex_char_from_oid()`.
>
> Turning the binary representation into hex first is roundabout though:
> we can simply compare the binary representation and give some special
> attention to the final nibble.
>
> Introduce a new function `oid_common_prefix_hexlen()` that does exactly
> this and refactor the code to use the new function. This allows us to
> drop the `struct min_abbrev_data::hex` field. Furthermore, this function
> will be used in by some other callsites in subsequent commits.
>
> Signed-off-by: Patrick Steinhardt <ps@pks.im>
> ---
> hash.c | 18 ++++++++++++++++++
> hash.h | 3 +++
> object-name.c | 23 +++--------------------
> 3 files changed, 24 insertions(+), 20 deletions(-)
>
> diff --git a/hash.c b/hash.c
> index 553f2008ea..e925b9754e 100644
> --- a/hash.c
> +++ b/hash.c
> @@ -317,3 +317,21 @@ const struct git_hash_algo *unsafe_hash_algo(const struct git_hash_algo *algop)
> /* Otherwise use the default one. */
> return algop;
> }
> +
> +unsigned oid_common_prefix_hexlen(const struct object_id *a,
> + const struct object_id *b)
> +{
> + unsigned rawsz = hash_algos[a->algo].rawsz;
> +
> + for (unsigned i = 0; i < rawsz; i++) {
> + if (a->hash[i] == b->hash[i])
> + continue;
> +Instead of transforming the bytes into 2 hex components we now compare the bytes themselves and perhaps then compare parts of it?
> + if ((a->hash[i] ^ b->hash[i]) & 0xf0)
Okay so if the 4 MSB are the same then we end up here and return i * 2. Makes sense.
> + return i * 2; > + else > + return i * 2 + 1;
If not, its the 4 LSB.
Show 37 quoted lines
> + }
> +
> + return rawsz * 2;
> +}
> diff --git a/hash.h b/hash.h
> index d51efce1d3..c082a53c9a 100644
> --- a/hash.h
> +++ b/hash.h
> @@ -396,6 +396,9 @@ static inline int oideq(const struct object_id *oid1, const struct object_id *oi
> return !memcmp(oid1->hash, oid2->hash, GIT_MAX_RAWSZ);
> }
>
> +unsigned oid_common_prefix_hexlen(const struct object_id *a,
> + const struct object_id *b);
> +
> static inline void oidcpy(struct object_id *dst, const struct object_id *src)
> {
> memcpy(dst->hash, src->hash, GIT_MAX_RAWSZ);
> diff --git a/object-name.c b/object-name.c
> index d82fb49f39..32e9c23e40 100644
> --- a/object-name.c
> +++ b/object-name.c
> @@ -585,32 +585,16 @@ static unsigned msb(unsigned long val)
> struct min_abbrev_data {
> unsigned int init_len;
> unsigned int cur_len;
> - char *hex;
> struct repository *repo;
> const struct object_id *oid;
> };
>
> -static inline char get_hex_char_from_oid(const struct object_id *oid,
> - unsigned int pos)
> -{
> - static const char hex[] = "0123456789abcdef";
> -
> - if ((pos & 1) == 0)So this basically alternates between odd/even positions.
So walking with an example:
if we have '10101011 11111010 10101010' pos 1 should get the hex for '1010' pos 2 should get the hex for '1011' pos 3 should get the hex for '1111' ...
> - return hex[oid->hash[pos >> 1] >> 4];
So for pos 1 '1010', to obtain the byte we first do 'pos >> 1'. Then we only care about the 4 MSB so we do `oid->hash[pos >> 1] >> 4`.
Finally we map it to the hex[] char array.
Show 11 quoted lines
> - else
> - return hex[oid->hash[pos >> 1] & 0xf];
> -}
> -
> static int extend_abbrev_len(const struct object_id *oid,
> struct min_abbrev_data *mad)
> {
> - unsigned int i = mad->init_len;
> - while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))
> - i++;
> -So earlier, we were iterating through the mad->hex which already had the computed hex. So to compare it with oid, we needed to get the hex at each position i of the oid.
That's where `get_hex_char_from_oid()` came in place.
Show 20 quoted lines
> - if (mad->hex[i] && i >= mad->cur_len) > - mad->cur_len = i + 1; > - > + unsigned len = oid_common_prefix_hexlen(oid, mad->oid); > + if (len != hash_algos[oid->algo].hexsz && len >= mad->cur_len) > + mad->cur_len = len + 1; > return 0; > } > > @@ -785,7 +769,6 @@ int repo_find_unique_abbrev_r(struct repository *r, char *hex, > mad.repo = r; > mad.init_len = len; > mad.cur_len = len; > - mad.hex = hex; > mad.oid = oid; > > find_abbrev_len_packed(&mad); > > -- > 2.53.0.1055.ga2ffed1127.dirty
The patch looks good.