"Jonathan Tan via GitGitGadget" <gitgitgadget@xxxxxxxxx> writes:
[snip]
> diff --git a/pack-objects.h b/pack-objects.h
> index b9898a4e64b..15be8368d21 100644
> --- a/pack-objects.h
> +++ b/pack-objects.h
> @@ -207,6 +207,34 @@ static inline uint32_t pack_name_hash(const char *name)
> return hash;
> }
>
> +static inline uint32_t pack_name_hash_v2(const char *name)
> +{
> + uint32_t hash = 0, base = 0, c;
> +
> + if (!name)
> + return 0;
> +
> + while ((c = *name++)) {
> + if (isspace(c))
> + continue;
> + if (c == '/') {
> + base = (base >> 6) ^ hash;
Just two questions about the implementation for my own knowledge.
1. Why use '6' here? I couldn't understand the reasoning for the
specific value.
2. Generally in hashing algorithms the XOR is used to ensure that the
output distribution is uniform which reduces collisions. Here, as you
noted, we're more finding values for sorting rather than hashing in the
traditional sense. So why use an XOR?
> + hash = 0;
> + } else {
> + /*
> + * 'c' is only a single byte. Reverse it and move
> + * it to the top of the hash, moving the rest to
> + * less-significant bits.
> + */
> + c = (c & 0xF0) >> 4 | (c & 0x0F) << 4;
> + c = (c & 0xCC) >> 2 | (c & 0x33) << 2;
> + c = (c & 0xAA) >> 1 | (c & 0x55) << 1;
> + hash = (hash >> 2) + (c << 24);
> + }
> + }
> + return (base >> 6) ^ hash;
> +}
> +
> static inline enum object_type oe_type(const struct object_entry *e)
> {
> return e->type_valid ? e->type_ : OBJ_BAD;
> --
> gitgitgadget
Attachment:
signature.asc
Description: PGP signature
