From: Karthik Nayak Date: Fri, 20 Mar 2026 10:01:48 GMT Subject: Re: [PATCH 11/14] object-name: simplify computing common prefixes Message-ID: In-Reply-To: <20260319-b4-pks-odb-source-abbrev-v1-11-5ddebad292b0@pks.im> Patrick Steinhardt writes: > 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 > --- > 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. > + } > + > + 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. > - 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. > - 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.