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

Re: Bad behavior in xhistogram.c in the face of hash collisions?

From
Greg Hurrell <greg@hurrell.net>
Date
Aug 26, 2022, 15:53 UTC
Message-ID
<70e68b28-73fa-4d16-a135-cbb03ea09d35@betaapp.fastmail.com>
In-Reply-To
<4e0eff48-4a3e-4f0e-9ed2-d01ec38442a5@www.fastmail.com>
On Mon, Aug 16, 2021, at 2:40 PM, Greg Hurrell wrote:
Show 5 quoted lines
> 
> I think I may have found a bug in the histogram diff algorithm that
> manifests when there is a hash collision.  This behavior seems to exist
> in the JGit implimentation (https://git.io/J0Ud8) too, and was brought
> across with the port-to-C in 8c912eea94a2.

Thought I had better bump the thread as I did a fire-and-forget on it a year ago and never followed up because I wasn't super confident about my findings.

I'd be interested in corroboration of my analysis, to see whether there really is a bug there. Not quoting my entire email here so as to keep things brief, but the original can be seen at:

https://public-inbox.org/git/4e0eff48-4a3e-4f0e-9ed2-d01ec38442a5@www.fastmail.com/

(Phillip, CC'ing you for an opinion because I see you have made a few changes to xdiff/xhistogram.c relatively recently.)

Best wishes, Greg

Previous: Greg Hurrell
Message 2 of 2 in “Bad behavior in xhistogram.c in the face of hash collisions?”
  1. Greg HurrellAug 16, 2021
  2. Greg HurrellAug 26, 2022

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.