git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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.
Previous: Patrick SteinhardtNext: Patrick Steinhardt
Message 26 of 52 in “odb: generic object name handling”
  1. 00/14 odb: generic object name handlingPatrick Steinhardt, Mar 19, 2026
  2. 01/14 oidtree: modernize the code a bitPatrick Steinhardt, Mar 19, 2026
  3. Junio C HamanoMar 19, 2026
  4. Patrick SteinhardtMar 20, 2026
  5. brian m. carlsonMar 20, 2026
  6. Patrick SteinhardtMar 23, 2026
  7. 02/14 oidtree: extend iteration to allow for arbitrary return codesPatrick Steinhardt, Mar 19, 2026
  8. Junio C HamanoMar 19, 2026
  9. Patrick SteinhardtMar 20, 2026
  10. Karthik NayakMar 19, 2026
  11. 03/14 odb: introduce `struct odb_for_each_object_options`Patrick Steinhardt, Mar 19, 2026
  12. Junio C HamanoMar 19, 2026
  13. Patrick SteinhardtMar 19, 2026
  14. Karthik NayakMar 20, 2026
  15. 04/14 object-name: move logic to iterate through loose prefixed objectsPatrick Steinhardt, Mar 19, 2026
  16. 05/14 object-name: move logic to iterate through packed prefixed objectsPatrick Steinhardt, Mar 19, 2026
  17. 06/14 object-name: extract function to parse object ID prefixesPatrick Steinhardt, Mar 19, 2026
  18. 07/14 object-name: backend-generic `repo_collect_ambiguous()`Patrick Steinhardt, Mar 19, 2026
  19. Junio C HamanoMar 19, 2026
  20. Patrick SteinhardtMar 19, 2026
  21. Karthik NayakMar 20, 2026
  22. 08/14 object-name: backend-generic `get_short_oid()`Patrick Steinhardt, Mar 19, 2026
  23. 09/14 object-name: merge `update_candidates()` and `match_prefix()`Patrick Steinhardt, Mar 19, 2026
  24. 10/14 object-name: abbreviate loose object names without `disambiguate_state`Patrick Steinhardt, Mar 19, 2026
  25. 11/14 object-name: simplify computing common prefixesPatrick Steinhardt, Mar 19, 2026
  26. Karthik NayakMar 20, 2026
  27. Patrick SteinhardtMar 20, 2026
  28. 12/14 object-name: move logic to compute loose abbreviation lengthPatrick Steinhardt, Mar 19, 2026
  29. 13/14 object-file: move logic to compute packed abbreviation lengthPatrick Steinhardt, Mar 19, 2026
  30. 14/14 odb: introduce generic `odb_find_abbrev_len()`Patrick Steinhardt, Mar 19, 2026
  31. 00/14 odb: generic object name handlingPatrick Steinhardt, Mar 20, 2026
  32. 01/14 oidtree: modernize the code a bitPatrick Steinhardt, Mar 20, 2026
  33. 02/14 oidtree: extend iteration to allow for arbitrary return codesPatrick Steinhardt, Mar 20, 2026
  34. 03/14 odb: introduce `struct odb_for_each_object_options`Patrick Steinhardt, Mar 20, 2026
  35. 04/14 object-name: move logic to iterate through loose prefixed objectsPatrick Steinhardt, Mar 20, 2026
  36. 05/14 object-name: move logic to iterate through packed prefixed objectsPatrick Steinhardt, Mar 20, 2026
  37. Toon ClaesMar 30, 2026
  38. 06/14 object-name: extract function to parse object ID prefixesPatrick Steinhardt, Mar 20, 2026
  39. 07/14 object-name: backend-generic `repo_collect_ambiguous()`Patrick Steinhardt, Mar 20, 2026
  40. 08/14 object-name: backend-generic `get_short_oid()`Patrick Steinhardt, Mar 20, 2026
  41. Toon ClaesMar 30, 2026
  42. 09/14 object-name: merge `update_candidates()` and `match_prefix()`Patrick Steinhardt, Mar 20, 2026
  43. 10/14 object-name: abbreviate loose object names without `disambiguate_state`Patrick Steinhardt, Mar 20, 2026
  44. 11/14 object-name: simplify computing common prefixesPatrick Steinhardt, Mar 20, 2026
  45. 12/14 object-name: move logic to compute loose abbreviation lengthPatrick Steinhardt, Mar 20, 2026
  46. 13/14 object-file: move logic to compute packed abbreviation lengthPatrick Steinhardt, Mar 20, 2026
  47. 14/14 odb: introduce generic `odb_find_abbrev_len()`Patrick Steinhardt, Mar 20, 2026
  48. Karthik NayakMar 20, 2026
  49. Patrick SteinhardtMar 20, 2026
  50. Toon ClaesMar 30, 2026
  51. Junio C HamanoMar 30, 2026
  52. Patrick SteinhardtMar 31, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.