{"thread":{"id":"47025","subject":"[PATCH 0/4] (x)diff cleanup: remove duplicate code","startedAt":"2017-10-24T18:59:28Z","lastAt":"2017-10-30T19:07:16Z","messageCount":31,"participants":["Stefan Beller","René Scharfe","Jonathan Nieder","Eric Sunshine","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"330948","messageId":"20171024185917.20515-1-sbeller@google.com","threadId":"47025","inReplyTo":null,"subject":"[PATCH 0/4] (x)diff cleanup: remove duplicate code","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T18:59:13Z","receivedAt":"2017-10-24T18:59:28Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Junio wrote:\n\n> * I was hoping that the next_byte() and string_hash() thing, once\n> they are cleaned up, will eventually be shared with the xdiff/\n> code at the lower layer, which needs to do pretty much the same\n> in order to implement various whitespace ignoring options. I am\n> not sure how well the approach taken by the WIP patch meshes with\n> the needs of the lower layer.\n\nThis series does exactly this; although I chose to reuse the code in\nxdiff/xutils.c instead of the new fancy next_byte/string_hash, as that\ncode has seen more exercise already (hence I assume it has fewer bugs\nif any as well as its performance implications are well understood).\n\nHowever to do so, we need to pollute xdiff/xutils.c and include\nhashmap.h there (which also requires cache.h as that header has\nan inline function using BUG()), which I find a bit unfortunate but\nworth the trade off of using better tested code.\n\nThanks,\nStefan\n\nStefan Beller (4):\n hashmap: introduce memhash_feed to access the internals of FNV-1 hash\n xdiff-interface: export comparing and hashing strings\n xdiff: use stronger hash function internally\n diff.c: get rid of duplicate implementation\n\n diff.c | 82 +++----------------------------------------------------\n hashmap.c | 7 ++++-\n hashmap.h | 3 ++\n xdiff-interface.c | 11 ++++++++\n xdiff-interface.h | 5 ++++\n xdiff/xutils.c | 19 ++++++-------\n 6 files changed, 37 insertions(+), 90 deletions(-)\n\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330949","messageId":"20171024185917.20515-2-sbeller@google.com","threadId":"47025","inReplyTo":"20171024185917.20515-1-sbeller@google.com","subject":"[PATCH 1/4] hashmap: introduce memhash_feed to access the internals of FNV-1 hash","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T18:59:14Z","receivedAt":"2017-10-24T18:59:30Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This will be useful shortly.\n\nSigned-off-by: Stefan Beller \n---\n hashmap.c | 7 ++++++-\n hashmap.h | 3 +++\n 2 files changed, 9 insertions(+), 1 deletion(-)\n\ndiff --git a/hashmap.c b/hashmap.c\nindex d42f01ff5a..d103eb1fd2 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -26,13 +26,18 @@ unsigned int strihash(const char *str)\n \treturn hash;\n }\n \n+unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next)\n+{\n+\treturn (hash_seed * FNV32_PRIME) ^ next;\n+}\n+\n unsigned int memhash(const void *buf, size_t len)\n {\n \tunsigned int hash = FNV32_BASE;\n \tunsigned char *ucbuf = (unsigned char *) buf;\n \twhile (len--) {\n \t\tunsigned int c = *ucbuf++;\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t\thash = memhash_feed(hash, c);\n \t}\n \treturn hash;\n }\ndiff --git a/hashmap.h b/hashmap.h\nindex 7cb29a6aed..c2464385ed 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -105,10 +105,13 @@\n * `strihash` and `memihash` are case insensitive versions.\n * `memihash_cont` is a variant of `memihash` that allows a computation to be\n * continued with another chunk of data.\n+ * `memhash_feed` takes just one character and returns the hash based off\n+ * a previous hash.\n */\n extern unsigned int strhash(const char *buf);\n extern unsigned int strihash(const char *buf);\n extern unsigned int memhash(const void *buf, size_t len);\n+extern unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next);\n extern unsigned int memihash(const void *buf, size_t len);\n extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);\n \n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330950","messageId":"20171024185917.20515-3-sbeller@google.com","threadId":"47025","inReplyTo":"20171024185917.20515-1-sbeller@google.com","subject":"[PATCH 2/4] xdiff-interface: export comparing and hashing strings","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T18:59:15Z","receivedAt":"2017-10-24T18:59:34Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This will turn out to be useful in a later patch\n\nSigned-off-by: Stefan Beller \n---\n xdiff-interface.c | 11 +++++++++++\n xdiff-interface.h | 5 +++++\n 2 files changed, 16 insertions(+)\n\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 018e033089..fd002ebbc2 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -5,6 +5,7 @@\n #include \"xdiff/xdiffi.h\"\n #include \"xdiff/xemit.h\"\n #include \"xdiff/xmacros.h\"\n+#include \"xdiff/xutils.h\"\n \n struct xdiff_emit_state {\n \txdiff_emit_consume_fn consume;\n@@ -296,6 +297,16 @@ void xdiff_clear_find_func(xdemitconf_t *xecfg)\n \t}\n }\n \n+unsigned long xdiff_hash_string(const char *s, size_t len, long flags)\n+{\n+\treturn xdl_hash_record(&s, s + len, flags);\n+}\n+\n+int xdiff_compare_lines(const char *l1, long s1, const char *l2, long s2, long flags)\n+{\n+\treturn xdl_recmatch(l1, s1, l2, s2, flags);\n+}\n+\n int git_xmerge_style = -1;\n \n int git_xmerge_config(const char *var, const char *value, void *cb)\ndiff --git a/xdiff-interface.h b/xdiff-interface.h\nindex 6f6ba9095d..d3cb9285c5 100644\n--- a/xdiff-interface.h\n+++ b/xdiff-interface.h\n@@ -29,4 +29,9 @@ extern void xdiff_clear_find_func(xdemitconf_t *xecfg);\n extern int git_xmerge_config(const char *var, const char *value, void *cb);\n extern int git_xmerge_style;\n \n+extern int xdiff_compare_lines(const char *l1, long s1,\n+\t\t\t const char *l2, long s2, long flags);\n+\n+extern unsigned long xdiff_hash_string(const char *s, size_t len, long flags);\n+\n #endif\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330951","messageId":"20171024185917.20515-4-sbeller@google.com","threadId":"47025","inReplyTo":"20171024185917.20515-1-sbeller@google.com","subject":"[PATCH 3/4] xdiff: use stronger hash function internally","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T18:59:16Z","receivedAt":"2017-10-24T18:59:37Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"Instead of using the hash seeded with 5381, and updated via\n`(hash << 5) ^ new_byte`, use the FNV-1 primitives as offered by\nhashmap.h, which is seeded with 0x811c9dc5 and computed as\n`(hash * 0x01000193) ^ new_byte`.\n\nSigned-off-by: Stefan Beller \n---\n xdiff/xutils.c | 19 ++++++++-----------\n 1 file changed, 8 insertions(+), 11 deletions(-)\n\ndiff --git a/xdiff/xutils.c b/xdiff/xutils.c\nindex 04d7b32e4e..a58a28c687 100644\n--- a/xdiff/xutils.c\n+++ b/xdiff/xutils.c\n@@ -24,7 +24,8 @@\n #include \n #include \"xinclude.h\"\n \n-\n+#include \"cache.h\"\n+#include \"hashmap.h\"\n \n \n long xdl_bogosqrt(long n) {\n@@ -228,7 +229,7 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n \n static unsigned long xdl_hash_record_with_whitespace(char const **data,\n \t\tchar const *top, long flags) {\n-\tunsigned long ha = 5381;\n+\tunsigned long ha = memhash(NULL, 0);\n \tchar const *ptr = *data;\n \n \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n@@ -243,21 +244,18 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n \t\t\t\t; /* already handled */\n \t\t\telse if (flags & XDF_IGNORE_WHITESPACE_CHANGE\n \t\t\t\t && !at_eol) {\n-\t\t\t\tha += (ha << 5);\n-\t\t\t\tha ^= (unsigned long) ' ';\n+\t\t\t\tha = memhash_feed(ha, (unsigned char) ' ');\n \t\t\t}\n \t\t\telse if (flags & XDF_IGNORE_WHITESPACE_AT_EOL\n \t\t\t\t && !at_eol) {\n \t\t\t\twhile (ptr2 != ptr + 1) {\n-\t\t\t\t\tha += (ha << 5);\n-\t\t\t\t\tha ^= (unsigned long) *ptr2;\n+\t\t\t\t\tha = memhash_feed(ha, (unsigned char) *ptr2);\n \t\t\t\t\tptr2++;\n \t\t\t\t}\n \t\t\t}\n \t\t\tcontinue;\n \t\t}\n-\t\tha += (ha << 5);\n-\t\tha ^= (unsigned long) *ptr;\n+\t\tha = memhash_feed(ha, (unsigned char) *ptr);\n \t}\n \t*data = ptr < top ? ptr + 1: ptr;\n \n@@ -265,15 +263,14 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n }\n \n unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n-\tunsigned long ha = 5381;\n+\tunsigned long ha = memhash(NULL, 0);\n \tchar const *ptr = *data;\n \n \tif (flags & XDF_WHITESPACE_FLAGS)\n \t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n \n \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n-\t\tha += (ha << 5);\n-\t\tha ^= (unsigned long) *ptr;\n+\t\tha = memhash_feed(ha, (unsigned char) *ptr);\n \t}\n \t*data = ptr < top ? ptr + 1: ptr;\n \n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330952","messageId":"20171024185917.20515-5-sbeller@google.com","threadId":"47025","inReplyTo":"20171024185917.20515-1-sbeller@google.com","subject":"[PATCH 4/4] diff.c: get rid of duplicate implementation","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T18:59:17Z","receivedAt":"2017-10-24T18:59:39Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"The implementations in diff.c to detect moved lines\nneeds to compare strings and hash strings, which is\nimplemented in that file, as well as in the xdiff\nlibrary.\n\nRemove the rather recent implementation in diff.c\nand rely on the well exercised code in the xdiff lib.\n\nSigned-off-by: Stefan Beller \n---\n diff.c | 82 ++++--------------------------------------------------------------\n 1 file changed, 4 insertions(+), 78 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex c4a669ffa8..e6814b9e9c 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -707,88 +707,14 @@ struct moved_entry {\n \tstruct moved_entry *next_line;\n };\n \n-static int next_byte(const char **cp, const char **endp,\n-\t\t const struct diff_options *diffopt)\n-{\n-\tint retval;\n-\n-\tif (*cp >= *endp)\n-\t\treturn -1;\n-\n-\tif (isspace(**cp)) {\n-\t\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_CHANGE)) {\n-\t\t\twhile (*cp < *endp && isspace(**cp))\n-\t\t\t\t(*cp)++;\n-\t\t\t/*\n-\t\t\t * After skipping a couple of whitespaces,\n-\t\t\t * we still have to account for one space.\n-\t\t\t */\n-\t\t\treturn (int)' ';\n-\t\t}\n-\n-\t\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE)) {\n-\t\t\twhile (*cp < *endp && isspace(**cp))\n-\t\t\t\t(*cp)++;\n-\t\t\t/*\n-\t\t\t * return the first non-ws character via the usual\n-\t\t\t * below, unless we ate all of the bytes\n-\t\t\t */\n-\t\t\tif (*cp >= *endp)\n-\t\t\t\treturn -1;\n-\t\t}\n-\t}\n-\n-\tretval = (unsigned char)(**cp);\n-\t(*cp)++;\n-\treturn retval;\n-}\n-\n static int moved_entry_cmp(const struct diff_options *diffopt,\n \t\t\t const struct moved_entry *a,\n \t\t\t const struct moved_entry *b,\n \t\t\t const void *keydata)\n {\n-\tconst char *ap = a->es->line, *ae = a->es->line + a->es->len;\n-\tconst char *bp = b->es->line, *be = b->es->line + b->es->len;\n-\n-\tif (!(diffopt->xdl_opts & XDF_WHITESPACE_FLAGS))\n-\t\treturn a->es->len != b->es->len || memcmp(ap, bp, a->es->len);\n-\n-\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_AT_EOL)) {\n-\t\twhile (ae > ap && isspace(ae[-1]))\n-\t\t\tae--;\n-\t\twhile (be > bp && isspace(be[-1]))\n-\t\t\tbe--;\n-\t}\n-\n-\twhile (1) {\n-\t\tint ca, cb;\n-\t\tca = next_byte(&ap, &ae, diffopt);\n-\t\tcb = next_byte(&bp, &be, diffopt);\n-\t\tif (ca != cb)\n-\t\t\treturn 1;\n-\t\tif (ca < 0)\n-\t\t\treturn 0;\n-\t}\n-}\n-\n-static unsigned get_string_hash(struct emitted_diff_symbol *es, struct diff_options *o)\n-{\n-\tif (o->xdl_opts & XDF_WHITESPACE_FLAGS) {\n-\t\tstatic struct strbuf sb = STRBUF_INIT;\n-\t\tconst char *ap = es->line, *ae = es->line + es->len;\n-\t\tint c;\n-\n-\t\tstrbuf_reset(&sb);\n-\t\twhile (ae > ap && isspace(ae[-1]))\n-\t\t\tae--;\n-\t\twhile ((c = next_byte(&ap, &ae, o)) >= 0)\n-\t\t\tstrbuf_addch(&sb, c);\n-\n-\t\treturn memhash(sb.buf, sb.len);\n-\t} else {\n-\t\treturn memhash(es->line, es->len);\n-\t}\n+\treturn !xdiff_compare_lines(a->es->line, a->es->len,\n+\t\t\t\t b->es->line, b->es->len,\n+\t\t\t\t diffopt->xdl_opts);\n }\n \n static struct moved_entry *prepare_entry(struct diff_options *o,\n@@ -797,7 +723,7 @@ static struct moved_entry *prepare_entry(struct diff_options *o,\n \tstruct moved_entry *ret = xmalloc(sizeof(*ret));\n \tstruct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no];\n \n-\tret->ent.hash = get_string_hash(l, o);\n+\tret->ent.hash = xdiff_hash_string(l->line, l->len, o->xdl_opts);\n \tret->es = l;\n \tret->next_line = NULL;\n \n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330953","messageId":"CAGZ79kZftQoP-Ht+VRakCZsQxh1tjfu=4DFJn_R6fiKD2MmzMA@mail.gmail.com","threadId":"47025","inReplyTo":"20171024185917.20515-1-sbeller@google.com","subject":"Re: [PATCH 0/4] (x)diff cleanup: remove duplicate code","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T19:02:37Z","receivedAt":"2017-10-24T19:02:47Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Oct 24, 2017 at 11:59 AM, Stefan Beller wrote:\n> Junio wrote:\n>\n>> * I was hoping that the next_byte() and string_hash() thing, once\n>> they are cleaned up, will eventually be shared with the xdiff/\n>> code at the lower layer, which needs to do pretty much the same\n>> in order to implement various whitespace ignoring options. I am\n>> not sure how well the approach taken by the WIP patch meshes with\n>> the needs of the lower layer.\n>\n> This series does exactly this; although I chose to reuse the code in\n> xdiff/xutils.c instead of the new fancy next_byte/string_hash, as that\n> code has seen more exercise already (hence I assume it has fewer bugs\n> if any as well as its performance implications are well understood).\n>\n> However to do so, we need to pollute xdiff/xutils.c and include\n> hashmap.h there (which also requires cache.h as that header has\n> an inline function using BUG()), which I find a bit unfortunate but\n> worth the trade off of using better tested code.\n>\n\nThis, of course, applies on top of jk/diff-color-moved-fix.\n"},{"id":"330962","messageId":"06c950e8-92c6-4926-ccac-2827d480f373@web.de","threadId":"47025","inReplyTo":"20171024185917.20515-2-sbeller@google.com","subject":"Re: [PATCH 1/4] hashmap: introduce memhash_feed to access the internals of FNV-1 hash","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-10-24T20:23:29Z","receivedAt":"2017-10-24T20:23:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.10.2017 um 20:59 schrieb Stefan Beller:\n> This will be useful shortly.\n> \n> Signed-off-by: Stefan Beller \n> ---\n> hashmap.c | 7 ++++++-\n> hashmap.h | 3 +++\n> 2 files changed, 9 insertions(+), 1 deletion(-)\n> \n> diff --git a/hashmap.c b/hashmap.c\n> index d42f01ff5a..d103eb1fd2 100644\n> --- a/hashmap.c\n> +++ b/hashmap.c\n> @@ -26,13 +26,18 @@ unsigned int strihash(const char *str)\n> \treturn hash;\n> }\n> \n> +unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next)\n\nWhy is the second parameter const and the first one isn't? (We tend\nnot to bother with const for value types.)\n\n> +{\n> +\treturn (hash_seed * FNV32_PRIME) ^ next;\n> +}\n> +\n> unsigned int memhash(const void *buf, size_t len)\n> {\n> \tunsigned int hash = FNV32_BASE;\n> \tunsigned char *ucbuf = (unsigned char *) buf;\n> \twhile (len--) {\n> \t\tunsigned int c = *ucbuf++;\n> -\t\thash = (hash * FNV32_PRIME) ^ c;\n> +\t\thash = memhash_feed(hash, c);\n\nI guess compilers inline a copy of the function here with -O2. My\nknee-jerk reaction, however, is horror in the face of adding a function\ncall to the inner loop of a hash function. Do you have performance\ntest results, ideally also with -O0? And why not make memhash_feed()\nan inline function or macro to sidestep that issue?\n\n> \t}\n> \treturn hash;\n> }\n> diff --git a/hashmap.h b/hashmap.h\n> index 7cb29a6aed..c2464385ed 100644\n> --- a/hashmap.h\n> +++ b/hashmap.h\n> @@ -105,10 +105,13 @@\n> * `strihash` and `memihash` are case insensitive versions.\n> * `memihash_cont` is a variant of `memihash` that allows a computation to be\n> * continued with another chunk of data.\n> + * `memhash_feed` takes just one character and returns the hash based off\n> + * a previous hash.\n> */\n> extern unsigned int strhash(const char *buf);\n> extern unsigned int strihash(const char *buf);\n> extern unsigned int memhash(const void *buf, size_t len);\n> +extern unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next);\n> extern unsigned int memihash(const void *buf, size_t len);\n> extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);\n> \n> \n"},{"id":"330963","messageId":"9f5c5cd5-9491-3163-60d4-ad36d75981ce@web.de","threadId":"47025","inReplyTo":"20171024185917.20515-3-sbeller@google.com","subject":"Re: [PATCH 2/4] xdiff-interface: export comparing and hashing strings","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-10-24T20:23:38Z","receivedAt":"2017-10-24T20:23:45Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.10.2017 um 20:59 schrieb Stefan Beller:\n> This will turn out to be useful in a later patch\n> \n> Signed-off-by: Stefan Beller \n> ---\n> xdiff-interface.c | 11 +++++++++++\n> xdiff-interface.h | 5 +++++\n> 2 files changed, 16 insertions(+)\n> \n> diff --git a/xdiff-interface.c b/xdiff-interface.c\n> index 018e033089..fd002ebbc2 100644\n> --- a/xdiff-interface.c\n> +++ b/xdiff-interface.c\n> @@ -5,6 +5,7 @@\n> #include \"xdiff/xdiffi.h\"\n> #include \"xdiff/xemit.h\"\n> #include \"xdiff/xmacros.h\"\n> +#include \"xdiff/xutils.h\"\n> \n> struct xdiff_emit_state {\n> \txdiff_emit_consume_fn consume;\n> @@ -296,6 +297,16 @@ void xdiff_clear_find_func(xdemitconf_t *xecfg)\n> \t}\n> }\n> \n> +unsigned long xdiff_hash_string(const char *s, size_t len, long flags)\n> +{\n> +\treturn xdl_hash_record(&s, s + len, flags);\n> +}\n> +\n> +int xdiff_compare_lines(const char *l1, long s1, const char *l2, long s2, long flags)\n> +{\n> +\treturn xdl_recmatch(l1, s1, l2, s2, flags);\n> +}\n\nxdl_recmatch() is already exported; why not use it without this\nwrapper?\n\n> +\n> int git_xmerge_style = -1;\n> \n> int git_xmerge_config(const char *var, const char *value, void *cb)\n> diff --git a/xdiff-interface.h b/xdiff-interface.h\n> index 6f6ba9095d..d3cb9285c5 100644\n> --- a/xdiff-interface.h\n> +++ b/xdiff-interface.h\n> @@ -29,4 +29,9 @@ extern void xdiff_clear_find_func(xdemitconf_t *xecfg);\n> extern int git_xmerge_config(const char *var, const char *value, void *cb);\n> extern int git_xmerge_style;\n> \n> +extern int xdiff_compare_lines(const char *l1, long s1,\n> +\t\t\t const char *l2, long s2, long flags);\n> +\n> +extern unsigned long xdiff_hash_string(const char *s, size_t len, long flags);\n\nDocumenting the meaning of their parameters would be nice. s and len\nare easy enough to guess, but which flags can be used? At least a\npointer to their definition in xdiff/xdiff.h would be helpful. And\nrenaming l1, s1, l2, s2 to a, alen, b, blen or line1, len1, line2, len2\nor similar would leave me less confused, but perhaps that's just me.\n\n> +\n> #endif\n> \n"},{"id":"330964","messageId":"16718615-c5df-24dd-fa62-2b42f5d83a02@web.de","threadId":"47025","inReplyTo":"20171024185917.20515-4-sbeller@google.com","subject":"Re: [PATCH 3/4] xdiff: use stronger hash function internally","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-10-24T20:23:42Z","receivedAt":"2017-10-24T20:23:51Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.10.2017 um 20:59 schrieb Stefan Beller:\n> Instead of using the hash seeded with 5381, and updated via\n> `(hash << 5) ^ new_byte`, use the FNV-1 primitives as offered by\n> hashmap.h, which is seeded with 0x811c9dc5 and computed as\n> `(hash * 0x01000193) ^ new_byte`.\n\nThe hash function you're replacing is called DJB2; I think that's worth\nmentioning.\n\nPerformance test results would be nice. No idea how to find edge cases,\nthough, or better: demonstrate a lack thereof.\n\n> \n> Signed-off-by: Stefan Beller \n> ---\n> xdiff/xutils.c | 19 ++++++++-----------\n> 1 file changed, 8 insertions(+), 11 deletions(-)\n> \n> diff --git a/xdiff/xutils.c b/xdiff/xutils.c\n> index 04d7b32e4e..a58a28c687 100644\n> --- a/xdiff/xutils.c\n> +++ b/xdiff/xutils.c\n> @@ -24,7 +24,8 @@\n> #include \n> #include \"xinclude.h\"\n> \n> -\n> +#include \"cache.h\"\n> +#include \"hashmap.h\"\n\nOuch. Defining FNV32_BASE and FNV32_PRIME here would be much easier\noverall. And if that's too much duplication then those definitions\ncould be extracted into a new header file (fnv32.h?) included by both\nhashmap.h and xutils.c.\n\n> \n> \n> long xdl_bogosqrt(long n) {\n> @@ -228,7 +229,7 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n> \n> static unsigned long xdl_hash_record_with_whitespace(char const **data,\n> \t\tchar const *top, long flags) {\n> -\tunsigned long ha = 5381;\n> +\tunsigned long ha = memhash(NULL, 0);\n> \tchar const *ptr = *data;\n> \n> \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n> @@ -243,21 +244,18 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n> \t\t\t\t; /* already handled */\n> \t\t\telse if (flags & XDF_IGNORE_WHITESPACE_CHANGE\n> \t\t\t\t && !at_eol) {\n> -\t\t\t\tha += (ha << 5);\n> -\t\t\t\tha ^= (unsigned long) ' ';\n> +\t\t\t\tha = memhash_feed(ha, (unsigned char) ' ');\n\nAll the memhash_feed() callers in this file cast to unsigned char. A\nmacro or a function (possibly inline) defined at the top could do\nthat for them.\n\n> \t\t\t}\n> \t\t\telse if (flags & XDF_IGNORE_WHITESPACE_AT_EOL\n> \t\t\t\t && !at_eol) {\n> \t\t\t\twhile (ptr2 != ptr + 1) {\n> -\t\t\t\t\tha += (ha << 5);\n> -\t\t\t\t\tha ^= (unsigned long) *ptr2;\n> +\t\t\t\t\tha = memhash_feed(ha, (unsigned char) *ptr2);\n> \t\t\t\t\tptr2++;\n> \t\t\t\t}\n> \t\t\t}\n> \t\t\tcontinue;\n> \t\t}\n> -\t\tha += (ha << 5);\n> -\t\tha ^= (unsigned long) *ptr;\n> +\t\tha = memhash_feed(ha, (unsigned char) *ptr);\n> \t}\n> \t*data = ptr < top ? ptr + 1: ptr;\n> \n> @@ -265,15 +263,14 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n> }\n> \n> unsigned long xdl_hash_record(char const **data, char const *top, long flags) {\n> -\tunsigned long ha = 5381;\n> +\tunsigned long ha = memhash(NULL, 0);\n> \tchar const *ptr = *data;\n> \n> \tif (flags & XDF_WHITESPACE_FLAGS)\n> \t\treturn xdl_hash_record_with_whitespace(data, top, flags);\n> \n> \tfor (; ptr < top && *ptr != '\\n'; ptr++) {\n> -\t\tha += (ha << 5);\n> -\t\tha ^= (unsigned long) *ptr;\n> +\t\tha = memhash_feed(ha, (unsigned char) *ptr);\n> \t}\n> \t*data = ptr < top ? ptr + 1: ptr;\n> \n> \n"},{"id":"330965","messageId":"CAGZ79kbJS68qL0=WTZVBfmSDXCii0HT60TGxx2MSiH_cK_tBCw@mail.gmail.com","threadId":"47025","inReplyTo":"9f5c5cd5-9491-3163-60d4-ad36d75981ce@web.de","subject":"Re: [PATCH 2/4] xdiff-interface: export comparing and hashing strings","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T20:42:28Z","receivedAt":"2017-10-24T20:42:34Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Oct 24, 2017 at 1:23 PM, René Scharfe wrote:\n\n> xdl_recmatch() is already exported; why not use it without this\n> wrapper?\n\nIt is exported in xdiff/xutils.h, to be used by various xdiff/*.c files, but\nnot outside of xdiff/. This one makes it available to the outside, too.\n\n>> +extern unsigned long xdiff_hash_string(const char *s, size_t len, long flags);\n>\n> Documenting the meaning of their parameters would be nice.\n\nI'll do that.\n"},{"id":"330966","messageId":"CAGZ79kZF+kL0uCFpVE0o9cU2zgjqm=yzeCZSEWtsC1=q+8N3Yg@mail.gmail.com","threadId":"47025","inReplyTo":"16718615-c5df-24dd-fa62-2b42f5d83a02@web.de","subject":"Re: [PATCH 3/4] xdiff: use stronger hash function internally","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T20:46:52Z","receivedAt":"2017-10-24T20:46:58Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Oct 24, 2017 at 1:23 PM, René Scharfe wrote:\n> Am 24.10.2017 um 20:59 schrieb Stefan Beller:\n>> Instead of using the hash seeded with 5381, and updated via\n>> `(hash << 5) ^ new_byte`, use the FNV-1 primitives as offered by\n>> hashmap.h, which is seeded with 0x811c9dc5 and computed as\n>> `(hash * 0x01000193) ^ new_byte`.\n>\n> The hash function you're replacing is called DJB2; I think that's worth\n> mentioning.\n\nI was not aware of the name. I'll look it up; thanks!\n\n>\n> Performance test results would be nice. No idea how to find edge cases,\n> though, or better: demonstrate a lack thereof.\n\nMy reasoning, though not in the commit message, is that the operations\nare essentially equal, just with different numeric values, hence no impact.\n\nI can look at the assembly and measure, too.\n\n>\n>>\n>> Signed-off-by: Stefan Beller \n>> ---\n>> xdiff/xutils.c | 19 ++++++++-----------\n>> 1 file changed, 8 insertions(+), 11 deletions(-)\n>>\n>> diff --git a/xdiff/xutils.c b/xdiff/xutils.c\n>> index 04d7b32e4e..a58a28c687 100644\n>> --- a/xdiff/xutils.c\n>> +++ b/xdiff/xutils.c\n>> @@ -24,7 +24,8 @@\n>> #include \n>> #include \"xinclude.h\"\n>>\n>> -\n>> +#include \"cache.h\"\n>> +#include \"hashmap.h\"\n>\n> Ouch. Defining FNV32_BASE and FNV32_PRIME here would be much easier\n> overall. And if that's too much duplication then those definitions\n> could be extracted into a new header file (fnv32.h?) included by both\n> hashmap.h and xutils.c.\n\nI guess fnv32.h would do; it would contain the defines as well as the\nstatic inline\nfunction to be used in the inner loop of patch 1.\n\n>\n>>\n>>\n>> long xdl_bogosqrt(long n) {\n>> @@ -228,7 +229,7 @@ int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags)\n>>\n>> static unsigned long xdl_hash_record_with_whitespace(char const **data,\n>> char const *top, long flags) {\n>> - unsigned long ha = 5381;\n>> + unsigned long ha = memhash(NULL, 0);\n>> char const *ptr = *data;\n>>\n>> for (; ptr < top && *ptr != '\\n'; ptr++) {\n>> @@ -243,21 +244,18 @@ static unsigned long xdl_hash_record_with_whitespace(char const **data,\n>> ; /* already handled */\n>> else if (flags & XDF_IGNORE_WHITESPACE_CHANGE\n>> && !at_eol) {\n>> - ha += (ha << 5);\n>> - ha ^= (unsigned long) ' ';\n>> + ha = memhash_feed(ha, (unsigned char) ' ');\n>\n> All the memhash_feed() callers in this file cast to unsigned char. A\n> macro or a function (possibly inline) defined at the top could do\n> that for them.\n\nThat would go away when using fnv32.h\n\nThanks for the review!\nStefan\n"},{"id":"330967","messageId":"CAGZ79kaQA90t6o2bn=H4Xrf2RiBOHc=gBE8XuKb+iHB6oEQVqA@mail.gmail.com","threadId":"47025","inReplyTo":"06c950e8-92c6-4926-ccac-2827d480f373@web.de","subject":"Re: [PATCH 1/4] hashmap: introduce memhash_feed to access the internals of FNV-1 hash","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T20:48:54Z","receivedAt":"2017-10-24T20:49:01Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":">> +unsigned int memhash_feed(unsigned int hash_seed, const unsigned char next)\n>\n> Why is the second parameter const and the first one isn't? (We tend\n> not to bother with const for value types.)\n\nwill do.\n\n>> + hash = memhash_feed(hash, c);\n>\n> I guess compilers inline a copy of the function here with -O2. My\n> knee-jerk reaction, however, is horror in the face of adding a function\n> call to the inner loop of a hash function. Do you have performance\n> test results, ideally also with -O0? And why not make memhash_feed()\n> an inline function or macro to sidestep that issue?\n\nMy gut feeling was similar, but then I assumed compilers of today would\nbe smart.\n\nAs per the discussion on a later patch, we could migrate all memhash* functions\nto fnv32.c except for the _feed, which will be static in its header fnv32.h\n\nThanks,\nStefan\n"},{"id":"330970","messageId":"20171024230413.sm2pzlf4qhd2rirk@aiede.mtv.corp.google.com","threadId":"47025","inReplyTo":"20171024185917.20515-4-sbeller@google.com","subject":"Re: [PATCH 3/4] xdiff: use stronger hash function internally","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2017-10-24T23:04:13Z","receivedAt":"2017-10-24T23:04:37Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Stefan Beller wrote:\n\n> --- a/xdiff/xutils.c\n> +++ b/xdiff/xutils.c\n> @@ -24,7 +24,8 @@\n> #include \n> #include \"xinclude.h\"\n> \n> -\n> +#include \"cache.h\"\n> +#include \"hashmap.h\"\n\n#includes like \"git-compat-util.h\" and \"cache.h\" can only be used as\nthe *first* #include.\n\nOtherwise the feature test macros they set do not take effect, causing\nlots of unpleasant platform-specific breakage.\n\nThanks,\nJonathan\n"},{"id":"330971","messageId":"20171024234234.10944-1-sbeller@google.com","threadId":"47025","inReplyTo":"CAGZ79kZftQoP-Ht+VRakCZsQxh1tjfu=4DFJn_R6fiKD2MmzMA@mail.gmail.com","subject":"[PATCHv2 0/2] (x)diff cleanup: remove duplicate code","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T23:42:32Z","receivedAt":"2017-10-24T23:42:51Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"v2:\n* I realized that we don't have to change the hashing function of xdiff;\n we can rather change the hashing function for the move detection,\n which is less fundamental.\n (That way I can shrink the series down to 2 patches)\n* commented and renamed function parameters in the exposed xdiff functions.\n* applies on top of jk/diff-color-moved-fix.\n\nThanks,\nStefan\n\nv1:\nJunio wrote:\n\n> * I was hoping that the next_byte() and string_hash() thing, once\n> they are cleaned up, will eventually be shared with the xdiff/\n> code at the lower layer, which needs to do pretty much the same\n> in order to implement various whitespace ignoring options. I am\n> not sure how well the approach taken by the WIP patch meshes with\n> the needs of the lower layer.\n\nThis series does exactly this; although I chose to reuse the code in\nxdiff/xutils.c instead of the new fancy next_byte/string_hash, as that\ncode has seen more exercise already (hence I assume it has fewer bugs\nif any as well as its performance implications are well understood).\n\nHowever to do so, we need to pollute xdiff/xutils.c and include\nhashmap.h there (which also requires cache.h as that header has\nan inline function using BUG()), which I find a bit unfortunate but\nworth the trade off of using better tested code.\n\nThanks,\nStefan\n\n\nStefan Beller (2):\n xdiff-interface: export comparing and hashing strings\n diff.c: get rid of duplicate implementation\n\n diff.c | 82 +++----------------------------------------------------\n xdiff-interface.c | 11 ++++++++\n xdiff-interface.h | 16 +++++++++++\n 3 files changed, 31 insertions(+), 78 deletions(-)\n\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330972","messageId":"20171024234234.10944-2-sbeller@google.com","threadId":"47025","inReplyTo":"20171024234234.10944-1-sbeller@google.com","subject":"[PATCH 1/2] xdiff-interface: export comparing and hashing strings","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T23:42:33Z","receivedAt":"2017-10-24T23:42:53Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This will turn out to be useful in a later patch.\n\nxdl_recmatch is exported in xdiff/xutils.h, to be used by various\nxdiff/*.c files, but not outside of xdiff/. This one makes it available\nto the outside, too.\n\nWhile at it, add documentation.\n\nSigned-off-by: Stefan Beller \n---\n xdiff-interface.c | 11 +++++++++++\n xdiff-interface.h | 16 ++++++++++++++++\n 2 files changed, 27 insertions(+)\n\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 018e033089..9b35af2455 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -5,6 +5,7 @@\n #include \"xdiff/xdiffi.h\"\n #include \"xdiff/xemit.h\"\n #include \"xdiff/xmacros.h\"\n+#include \"xdiff/xutils.h\"\n \n struct xdiff_emit_state {\n \txdiff_emit_consume_fn consume;\n@@ -296,6 +297,16 @@ void xdiff_clear_find_func(xdemitconf_t *xecfg)\n \t}\n }\n \n+unsigned long xdiff_hash_string(const char *s, size_t len, long flags)\n+{\n+\treturn xdl_hash_record(&s, s + len, flags);\n+}\n+\n+int xdiff_compare_lines(const char *a, long len_a, const char *b, long len_b, long flags)\n+{\n+\treturn xdl_recmatch(a, len_a, b, len_b, flags);\n+}\n+\n int git_xmerge_style = -1;\n \n int git_xmerge_config(const char *var, const char *value, void *cb)\ndiff --git a/xdiff-interface.h b/xdiff-interface.h\nindex 6f6ba9095d..6f5abaf8d3 100644\n--- a/xdiff-interface.h\n+++ b/xdiff-interface.h\n@@ -29,4 +29,20 @@ extern void xdiff_clear_find_func(xdemitconf_t *xecfg);\n extern int git_xmerge_config(const char *var, const char *value, void *cb);\n extern int git_xmerge_style;\n \n+/*\n+ * Compare the strings l1 with l2 which are of size s1 and s2 respectively.\n+ * Returns 1 if the strings are deemed equal, 0 otherwise.\n+ * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n+ * are treated for the comparision.\n+ */\n+extern int xdiff_compare_lines(const char *a, long len_a,\n+\t\t\t const char *b, long len_b, long flags);\n+\n+/*\n+ * Returns a hash of the string s of length len.\n+ * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n+ * are treated for the hash.\n+ */\n+extern unsigned long xdiff_hash_string(const char *s, size_t len, long flags);\n+\n #endif\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330973","messageId":"20171024234234.10944-3-sbeller@google.com","threadId":"47025","inReplyTo":"20171024234234.10944-1-sbeller@google.com","subject":"[PATCH 2/2] diff.c: get rid of duplicate implementation","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T23:42:34Z","receivedAt":"2017-10-24T23:42:58Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"The implementations in diff.c to detect moved lines needs to compare\nstrings and hash strings, which is implemented in that file, as well\nas in the xdiff library.\n\nRemove the rather recent implementation in diff.c and rely on the well\nexercised code in the xdiff lib.\n\nWith this change the hash used for bucketing the strings for the moved\nline detection changes from FNV32 (that is provided via the hashmaps\nmemhash) to DJB2 (which is used internally in xdiff). Benchmarks found\non the web[1] do not indicate that these hashes are different in\nperformance for readable strings.\n\n[1] https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed\n\nSigned-off-by: Stefan Beller \n---\n diff.c | 82 ++++--------------------------------------------------------------\n 1 file changed, 4 insertions(+), 78 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex c4a669ffa8..e6814b9e9c 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -707,88 +707,14 @@ struct moved_entry {\n \tstruct moved_entry *next_line;\n };\n \n-static int next_byte(const char **cp, const char **endp,\n-\t\t const struct diff_options *diffopt)\n-{\n-\tint retval;\n-\n-\tif (*cp >= *endp)\n-\t\treturn -1;\n-\n-\tif (isspace(**cp)) {\n-\t\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_CHANGE)) {\n-\t\t\twhile (*cp < *endp && isspace(**cp))\n-\t\t\t\t(*cp)++;\n-\t\t\t/*\n-\t\t\t * After skipping a couple of whitespaces,\n-\t\t\t * we still have to account for one space.\n-\t\t\t */\n-\t\t\treturn (int)' ';\n-\t\t}\n-\n-\t\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE)) {\n-\t\t\twhile (*cp < *endp && isspace(**cp))\n-\t\t\t\t(*cp)++;\n-\t\t\t/*\n-\t\t\t * return the first non-ws character via the usual\n-\t\t\t * below, unless we ate all of the bytes\n-\t\t\t */\n-\t\t\tif (*cp >= *endp)\n-\t\t\t\treturn -1;\n-\t\t}\n-\t}\n-\n-\tretval = (unsigned char)(**cp);\n-\t(*cp)++;\n-\treturn retval;\n-}\n-\n static int moved_entry_cmp(const struct diff_options *diffopt,\n \t\t\t const struct moved_entry *a,\n \t\t\t const struct moved_entry *b,\n \t\t\t const void *keydata)\n {\n-\tconst char *ap = a->es->line, *ae = a->es->line + a->es->len;\n-\tconst char *bp = b->es->line, *be = b->es->line + b->es->len;\n-\n-\tif (!(diffopt->xdl_opts & XDF_WHITESPACE_FLAGS))\n-\t\treturn a->es->len != b->es->len || memcmp(ap, bp, a->es->len);\n-\n-\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_AT_EOL)) {\n-\t\twhile (ae > ap && isspace(ae[-1]))\n-\t\t\tae--;\n-\t\twhile (be > bp && isspace(be[-1]))\n-\t\t\tbe--;\n-\t}\n-\n-\twhile (1) {\n-\t\tint ca, cb;\n-\t\tca = next_byte(&ap, &ae, diffopt);\n-\t\tcb = next_byte(&bp, &be, diffopt);\n-\t\tif (ca != cb)\n-\t\t\treturn 1;\n-\t\tif (ca < 0)\n-\t\t\treturn 0;\n-\t}\n-}\n-\n-static unsigned get_string_hash(struct emitted_diff_symbol *es, struct diff_options *o)\n-{\n-\tif (o->xdl_opts & XDF_WHITESPACE_FLAGS) {\n-\t\tstatic struct strbuf sb = STRBUF_INIT;\n-\t\tconst char *ap = es->line, *ae = es->line + es->len;\n-\t\tint c;\n-\n-\t\tstrbuf_reset(&sb);\n-\t\twhile (ae > ap && isspace(ae[-1]))\n-\t\t\tae--;\n-\t\twhile ((c = next_byte(&ap, &ae, o)) >= 0)\n-\t\t\tstrbuf_addch(&sb, c);\n-\n-\t\treturn memhash(sb.buf, sb.len);\n-\t} else {\n-\t\treturn memhash(es->line, es->len);\n-\t}\n+\treturn !xdiff_compare_lines(a->es->line, a->es->len,\n+\t\t\t\t b->es->line, b->es->len,\n+\t\t\t\t diffopt->xdl_opts);\n }\n \n static struct moved_entry *prepare_entry(struct diff_options *o,\n@@ -797,7 +723,7 @@ static struct moved_entry *prepare_entry(struct diff_options *o,\n \tstruct moved_entry *ret = xmalloc(sizeof(*ret));\n \tstruct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no];\n \n-\tret->ent.hash = get_string_hash(l, o);\n+\tret->ent.hash = xdiff_hash_string(l->line, l->len, o->xdl_opts);\n \tret->es = l;\n \tret->next_line = NULL;\n \n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330974","messageId":"20171024234505.11823-1-sbeller@google.com","threadId":"47025","inReplyTo":"CAGZ79kZftQoP-Ht+VRakCZsQxh1tjfu=4DFJn_R6fiKD2MmzMA@mail.gmail.com","subject":"[PATCH 1/5] fnv: migrate code from hashmap to fnv","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-24T23:45:05Z","receivedAt":"2017-10-24T23:45:15Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"The functions regarding the Fowler–Noll–Vo hash function are put in a\nseparate compilation unit, as it is logically different from the hashmap\nfunctionality.\n\nSigned-off-by: Stefan Beller \n---\n\nThis may still be an interesting cleanup on its own.\n\nThanks,\nStefan\n\n Makefile | 1 +\n attr.c | 1 +\n builtin/fast-export.c | 1 +\n diff.c | 1 +\n fnv.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++\n fnv.h | 20 ++++++++++++++++\n hashmap.c | 64 +------------------------------------------------\n hashmap.h | 15 ------------\n merge-recursive.c | 1 +\n remote.c | 1 +\n submodule-config.c | 1 +\n t/helper/test-hashmap.c | 1 +\n 12 files changed, 93 insertions(+), 78 deletions(-)\n create mode 100644 fnv.c\n create mode 100644 fnv.h\n\ndiff --git a/Makefile b/Makefile\nindex cd75985991..8e1c5988f3 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -793,6 +793,7 @@ LIB_OBJS += ewah/ewah_io.o\n LIB_OBJS += ewah/ewah_rlw.o\n LIB_OBJS += exec_cmd.o\n LIB_OBJS += fetch-pack.o\n+LIB_OBJS += fnv.o\n LIB_OBJS += fsck.o\n LIB_OBJS += gettext.o\n LIB_OBJS += gpg-interface.o\ndiff --git a/attr.c b/attr.c\nindex dfc3a558d8..2e4217c4f1 100644\n--- a/attr.c\n+++ b/attr.c\n@@ -16,6 +16,7 @@\n #include \"utf8.h\"\n #include \"quote.h\"\n #include \"thread-utils.h\"\n+#include \"fnv.h\"\n \n const char git_attr__true[] = \"(builtin)true\";\n const char git_attr__false[] = \"\\0(builtin)false\";\ndiff --git a/builtin/fast-export.c b/builtin/fast-export.c\nindex 2fb60d6d48..62f4010510 100644\n--- a/builtin/fast-export.c\n+++ b/builtin/fast-export.c\n@@ -21,6 +21,7 @@\n #include \"quote.h\"\n #include \"remote.h\"\n #include \"blob.h\"\n+#include \"fnv.h\"\n \n static const char *fast_export_usage[] = {\n \tN_(\"git fast-export [rev-list-opts]\"),\ndiff --git a/diff.c b/diff.c\nindex c4a669ffa8..a23f4521fb 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -22,6 +22,7 @@\n #include \"argv-array.h\"\n #include \"graph.h\"\n #include \"packfile.h\"\n+#include \"fnv.h\"\n \n #ifdef NO_FAST_WORKING_DIRECTORY\n #define FAST_WORKING_DIRECTORY 0\ndiff --git a/fnv.c b/fnv.c\nnew file mode 100644\nindex 0000000000..b4cbf39f0a\n--- /dev/null\n+++ b/fnv.c\n@@ -0,0 +1,64 @@\n+#include \"fnv.h\"\n+\n+#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n+#define FNV32_PRIME ((unsigned int) 0x01000193)\n+\n+unsigned int strhash(const char *str)\n+{\n+\tunsigned int c, hash = FNV32_BASE;\n+\twhile ((c = (unsigned char) *str++))\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\treturn hash;\n+}\n+\n+unsigned int strihash(const char *str)\n+{\n+\tunsigned int c, hash = FNV32_BASE;\n+\twhile ((c = (unsigned char) *str++)) {\n+\t\tif (c >= 'a' && c <= 'z')\n+\t\t\tc -= 'a' - 'A';\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n+unsigned int memhash(const void *buf, size_t len)\n+{\n+\tunsigned int hash = FNV32_BASE;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n+\twhile (len--) {\n+\t\tunsigned int c = *ucbuf++;\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n+unsigned int memihash(const void *buf, size_t len)\n+{\n+\tunsigned int hash = FNV32_BASE;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n+\twhile (len--) {\n+\t\tunsigned int c = *ucbuf++;\n+\t\tif (c >= 'a' && c <= 'z')\n+\t\t\tc -= 'a' - 'A';\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\n+\n+/*\n+ * Incoporate another chunk of data into a memihash\n+ * computation.\n+ */\n+unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)\n+{\n+\tunsigned int hash = hash_seed;\n+\tunsigned char *ucbuf = (unsigned char *) buf;\n+\twhile (len--) {\n+\t\tunsigned int c = *ucbuf++;\n+\t\tif (c >= 'a' && c <= 'z')\n+\t\t\tc -= 'a' - 'A';\n+\t\thash = (hash * FNV32_PRIME) ^ c;\n+\t}\n+\treturn hash;\n+}\ndiff --git a/fnv.h b/fnv.h\nnew file mode 100644\nindex 0000000000..b425c85c66\n--- /dev/null\n+++ b/fnv.h\n@@ -0,0 +1,20 @@\n+#ifndef FNV_H\n+#define FNV_H\n+\n+#include \n+/*\n+ * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see\n+ * http://www.isthe.com/chongo/tech/comp/fnv).\n+ * `strhash` and `strihash` take 0-terminated strings, while `memhash` and\n+ * `memihash` operate on arbitrary-length memory.\n+ * `strihash` and `memihash` are case insensitive versions.\n+ * `memihash_cont` is a variant of `memihash` that allows a computation to be\n+ * continued with another chunk of data.\n+ */\n+extern unsigned int strhash(const char *buf);\n+extern unsigned int strihash(const char *buf);\n+extern unsigned int memhash(const void *buf, size_t len);\n+extern unsigned int memihash(const void *buf, size_t len);\n+extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);\n+\n+#endif\ndiff --git a/hashmap.c b/hashmap.c\nindex d42f01ff5a..1605edbbc3 100644\n--- a/hashmap.c\n+++ b/hashmap.c\n@@ -3,69 +3,7 @@\n */\n #include \"cache.h\"\n #include \"hashmap.h\"\n-\n-#define FNV32_BASE ((unsigned int) 0x811c9dc5)\n-#define FNV32_PRIME ((unsigned int) 0x01000193)\n-\n-unsigned int strhash(const char *str)\n-{\n-\tunsigned int c, hash = FNV32_BASE;\n-\twhile ((c = (unsigned char) *str++))\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n-\treturn hash;\n-}\n-\n-unsigned int strihash(const char *str)\n-{\n-\tunsigned int c, hash = FNV32_BASE;\n-\twhile ((c = (unsigned char) *str++)) {\n-\t\tif (c >= 'a' && c <= 'z')\n-\t\t\tc -= 'a' - 'A';\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n-\t}\n-\treturn hash;\n-}\n-\n-unsigned int memhash(const void *buf, size_t len)\n-{\n-\tunsigned int hash = FNV32_BASE;\n-\tunsigned char *ucbuf = (unsigned char *) buf;\n-\twhile (len--) {\n-\t\tunsigned int c = *ucbuf++;\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n-\t}\n-\treturn hash;\n-}\n-\n-unsigned int memihash(const void *buf, size_t len)\n-{\n-\tunsigned int hash = FNV32_BASE;\n-\tunsigned char *ucbuf = (unsigned char *) buf;\n-\twhile (len--) {\n-\t\tunsigned int c = *ucbuf++;\n-\t\tif (c >= 'a' && c <= 'z')\n-\t\t\tc -= 'a' - 'A';\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n-\t}\n-\treturn hash;\n-}\n-\n-/*\n- * Incoporate another chunk of data into a memihash\n- * computation.\n- */\n-unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len)\n-{\n-\tunsigned int hash = hash_seed;\n-\tunsigned char *ucbuf = (unsigned char *) buf;\n-\twhile (len--) {\n-\t\tunsigned int c = *ucbuf++;\n-\t\tif (c >= 'a' && c <= 'z')\n-\t\t\tc -= 'a' - 'A';\n-\t\thash = (hash * FNV32_PRIME) ^ c;\n-\t}\n-\treturn hash;\n-}\n+#include \"fnv.h\"\n \n #define HASHMAP_INITIAL_SIZE 64\n /* grow / shrink by 2^2 */\ndiff --git a/hashmap.h b/hashmap.h\nindex 7cb29a6aed..96176f7d8c 100644\n--- a/hashmap.h\n+++ b/hashmap.h\n@@ -97,21 +97,6 @@\n * }\n */\n \n-/*\n- * Ready-to-use hash functions for strings, using the FNV-1 algorithm (see\n- * http://www.isthe.com/chongo/tech/comp/fnv).\n- * `strhash` and `strihash` take 0-terminated strings, while `memhash` and\n- * `memihash` operate on arbitrary-length memory.\n- * `strihash` and `memihash` are case insensitive versions.\n- * `memihash_cont` is a variant of `memihash` that allows a computation to be\n- * continued with another chunk of data.\n- */\n-extern unsigned int strhash(const char *buf);\n-extern unsigned int strihash(const char *buf);\n-extern unsigned int memhash(const void *buf, size_t len);\n-extern unsigned int memihash(const void *buf, size_t len);\n-extern unsigned int memihash_cont(unsigned int hash_seed, const void *buf, size_t len);\n-\n /*\n * Converts a cryptographic hash (e.g. SHA-1) into an int-sized hash code\n * for use in hash tables. Cryptographic hashes are supposed to have\ndiff --git a/merge-recursive.c b/merge-recursive.c\nindex 1d3f8f0d22..d1fb2f5f3d 100644\n--- a/merge-recursive.c\n+++ b/merge-recursive.c\n@@ -22,6 +22,7 @@\n #include \"attr.h\"\n #include \"merge-recursive.h\"\n #include \"dir.h\"\n+#include \"fnv.h\"\n #include \"submodule.h\"\n \n struct path_hashmap_entry {\ndiff --git a/remote.c b/remote.c\nindex b220f0dfc6..24957ba32c 100644\n--- a/remote.c\n+++ b/remote.c\n@@ -10,6 +10,7 @@\n #include \"string-list.h\"\n #include \"mergesort.h\"\n #include \"argv-array.h\"\n+#include \"fnv.h\"\n \n enum map_direction { FROM_SRC, FROM_DST };\n \ndiff --git a/submodule-config.c b/submodule-config.c\nindex 2aa8a1747f..432423f876 100644\n--- a/submodule-config.c\n+++ b/submodule-config.c\n@@ -5,6 +5,7 @@\n #include \"submodule.h\"\n #include \"strbuf.h\"\n #include \"parse-options.h\"\n+#include \"fnv.h\"\n \n /*\n * submodule cache lookup structure\ndiff --git a/t/helper/test-hashmap.c b/t/helper/test-hashmap.c\nindex 1145d51671..b5ac97886f 100644\n--- a/t/helper/test-hashmap.c\n+++ b/t/helper/test-hashmap.c\n@@ -1,5 +1,6 @@\n #include \"git-compat-util.h\"\n #include \"hashmap.h\"\n+#include \"fnv.h\"\n \n struct test_entry\n {\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"330987","messageId":"CAPig+cR1Lw=JGJ7BoTdvM_PG+sjAoas=GTbs2fkRTYq35Mj2sg@mail.gmail.com","threadId":"47025","inReplyTo":"20171024234234.10944-2-sbeller@google.com","subject":"Re: [PATCH 1/2] xdiff-interface: export comparing and hashing strings","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2017-10-25T04:26:31Z","receivedAt":"2017-10-25T04:26:36Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Oct 24, 2017 at 7:42 PM, Stefan Beller wrote:\n> This will turn out to be useful in a later patch.\n>\n> xdl_recmatch is exported in xdiff/xutils.h, to be used by various\n> xdiff/*.c files, but not outside of xdiff/. This one makes it available\n> to the outside, too.\n>\n> While at it, add documentation.\n>\n> Signed-off-by: Stefan Beller \n> ---\n> diff --git a/xdiff-interface.h b/xdiff-interface.h\n> @@ -29,4 +29,20 @@ extern void xdiff_clear_find_func(xdemitconf_t *xecfg);\n> +/*\n> + * Compare the strings l1 with l2 which are of size s1 and s2 respectively.\n> + * Returns 1 if the strings are deemed equal, 0 otherwise.\n> + * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n> + * are treated for the comparision.\n> + */\n> +extern int xdiff_compare_lines(const char *a, long len_a,\n> + const char *b, long len_b, long flags);\n\nThe comment block talks about 'l1', 'l2', 's1', and 's2', but the\ndeclaration uses 'a', 'b, 'len_a', 'len_b'. Confusing.\n"},{"id":"330992","messageId":"xmqqinf3izgm.fsf@gitster.mtv.corp.google.com","threadId":"47025","inReplyTo":"20171024234234.10944-1-sbeller@google.com","subject":"Re: [PATCHv2 0/2] (x)diff cleanup: remove duplicate code","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-25T05:11:21Z","receivedAt":"2017-10-25T05:11:28Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> v2:\n> * I realized that we don't have to change the hashing function of xdiff;\n> we can rather change the hashing function for the move detection,\n> which is less fundamental.\n> (That way I can shrink the series down to 2 patches)\n> * commented and renamed function parameters in the exposed xdiff functions.\n> * applies on top of jk/diff-color-moved-fix.\n\nYes, by reusing the line hashing and comparison from xdiff/ we can\nensure that we will use consistent comparison function, and the\nthing we need to focus on will become how correctly the caller uses\nthe xdiff interface. This looks much better than the previous one.\n\nEric's comment on the function parameters is right. We keep them in\nsync with the naming convention of xdiff/ as long as they are still\npart of xdiff layer, and the convention there is that the lines\nbeing compared are l1[] and l2[] whose lengths are s1 and s2, if I\nam not mistaken (well, I am not, as I just touched the function\nthere during my lunch break ;-).\n\n\n"},{"id":"331028","messageId":"CAGZ79kYUMv2GhSqhsUxgagoYFObwt+3wiD0oN-uEf-HpnPV7OA@mail.gmail.com","threadId":"47025","inReplyTo":"xmqqinf3izgm.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCHv2 0/2] (x)diff cleanup: remove duplicate code","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-25T18:47:32Z","receivedAt":"2017-10-25T18:47:39Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Tue, Oct 24, 2017 at 10:11 PM, Junio C Hamano wrote:\n> Stefan Beller writes:\n>\n>> v2:\n>> * I realized that we don't have to change the hashing function of xdiff;\n>> we can rather change the hashing function for the move detection,\n>> which is less fundamental.\n>> (That way I can shrink the series down to 2 patches)\n>> * commented and renamed function parameters in the exposed xdiff functions.\n>> * applies on top of jk/diff-color-moved-fix.\n>\n> Yes, by reusing the line hashing and comparison from xdiff/ we can\n> ensure that we will use consistent comparison function, and the\n> thing we need to focus on will become how correctly the caller uses\n> the xdiff interface. This looks much better than the previous one.\n>\n> Eric's comment on the function parameters is right. We keep them in\n> sync with the naming convention of xdiff/ as long as they are still\n> part of xdiff layer, and the convention there is that the lines\n> being compared are l1[] and l2[] whose lengths are s1 and s2, if I\n> am not mistaken (well, I am not, as I just touched the function\n> there during my lunch break ;-).\n>\n\nYes, I am torn on the naming as Rene commented on it and did not like\nthe (l1, s1) and rather would see a (a, alen) / (b, blen) approach.\nAnd I thought that was a good idea initially as that patch is explicitly about\nexposing the internals of xdiff to the world. So when the world copes better\nwith (a, alen), then the function added in xdiff-interface.c should take that\nparameter as to not confuse the outside world. And one could argue\nthat xdiff-interface is not part of the xdiff layer any more as that is the\nglue-gap to the rest of Git.\n\nHowever I agree that we may want to keep l1[], s1 at that place, as the\nrest of the xdiff interface looks like it is kept in line with xdiff.\n\nThanks,\nStefan\n"},{"id":"331029","messageId":"20171025184912.21657-3-sbeller@google.com","threadId":"47025","inReplyTo":"20171025184912.21657-1-sbeller@google.com","subject":"[PATCH 2/2] diff.c: get rid of duplicate implementation","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-25T18:49:12Z","receivedAt":"2017-10-25T18:49:27Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"The implementations in diff.c to detect moved lines needs to compare\nstrings and hash strings, which is implemented in that file, as well\nas in the xdiff library.\n\nRemove the rather recent implementation in diff.c and rely on the well\nexercised code in the xdiff lib.\n\nWith this change the hash used for bucketing the strings for the moved\nline detection changes from FNV32 (that is provided via the hashmaps\nmemhash) to DJB2 (which is used internally in xdiff). Benchmarks found\non the web[1] do not indicate that these hashes are different in\nperformance for readable strings.\n\n[1] https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed\n\nSigned-off-by: Stefan Beller \n---\n diff.c | 82 ++++--------------------------------------------------------------\n 1 file changed, 4 insertions(+), 78 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex c4a669ffa8..e6814b9e9c 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -707,88 +707,14 @@ struct moved_entry {\n \tstruct moved_entry *next_line;\n };\n \n-static int next_byte(const char **cp, const char **endp,\n-\t\t const struct diff_options *diffopt)\n-{\n-\tint retval;\n-\n-\tif (*cp >= *endp)\n-\t\treturn -1;\n-\n-\tif (isspace(**cp)) {\n-\t\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_CHANGE)) {\n-\t\t\twhile (*cp < *endp && isspace(**cp))\n-\t\t\t\t(*cp)++;\n-\t\t\t/*\n-\t\t\t * After skipping a couple of whitespaces,\n-\t\t\t * we still have to account for one space.\n-\t\t\t */\n-\t\t\treturn (int)' ';\n-\t\t}\n-\n-\t\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE)) {\n-\t\t\twhile (*cp < *endp && isspace(**cp))\n-\t\t\t\t(*cp)++;\n-\t\t\t/*\n-\t\t\t * return the first non-ws character via the usual\n-\t\t\t * below, unless we ate all of the bytes\n-\t\t\t */\n-\t\t\tif (*cp >= *endp)\n-\t\t\t\treturn -1;\n-\t\t}\n-\t}\n-\n-\tretval = (unsigned char)(**cp);\n-\t(*cp)++;\n-\treturn retval;\n-}\n-\n static int moved_entry_cmp(const struct diff_options *diffopt,\n \t\t\t const struct moved_entry *a,\n \t\t\t const struct moved_entry *b,\n \t\t\t const void *keydata)\n {\n-\tconst char *ap = a->es->line, *ae = a->es->line + a->es->len;\n-\tconst char *bp = b->es->line, *be = b->es->line + b->es->len;\n-\n-\tif (!(diffopt->xdl_opts & XDF_WHITESPACE_FLAGS))\n-\t\treturn a->es->len != b->es->len || memcmp(ap, bp, a->es->len);\n-\n-\tif (DIFF_XDL_TST(diffopt, IGNORE_WHITESPACE_AT_EOL)) {\n-\t\twhile (ae > ap && isspace(ae[-1]))\n-\t\t\tae--;\n-\t\twhile (be > bp && isspace(be[-1]))\n-\t\t\tbe--;\n-\t}\n-\n-\twhile (1) {\n-\t\tint ca, cb;\n-\t\tca = next_byte(&ap, &ae, diffopt);\n-\t\tcb = next_byte(&bp, &be, diffopt);\n-\t\tif (ca != cb)\n-\t\t\treturn 1;\n-\t\tif (ca < 0)\n-\t\t\treturn 0;\n-\t}\n-}\n-\n-static unsigned get_string_hash(struct emitted_diff_symbol *es, struct diff_options *o)\n-{\n-\tif (o->xdl_opts & XDF_WHITESPACE_FLAGS) {\n-\t\tstatic struct strbuf sb = STRBUF_INIT;\n-\t\tconst char *ap = es->line, *ae = es->line + es->len;\n-\t\tint c;\n-\n-\t\tstrbuf_reset(&sb);\n-\t\twhile (ae > ap && isspace(ae[-1]))\n-\t\t\tae--;\n-\t\twhile ((c = next_byte(&ap, &ae, o)) >= 0)\n-\t\t\tstrbuf_addch(&sb, c);\n-\n-\t\treturn memhash(sb.buf, sb.len);\n-\t} else {\n-\t\treturn memhash(es->line, es->len);\n-\t}\n+\treturn !xdiff_compare_lines(a->es->line, a->es->len,\n+\t\t\t\t b->es->line, b->es->len,\n+\t\t\t\t diffopt->xdl_opts);\n }\n \n static struct moved_entry *prepare_entry(struct diff_options *o,\n@@ -797,7 +723,7 @@ static struct moved_entry *prepare_entry(struct diff_options *o,\n \tstruct moved_entry *ret = xmalloc(sizeof(*ret));\n \tstruct emitted_diff_symbol *l = &o->emitted_symbols->buf[line_no];\n \n-\tret->ent.hash = get_string_hash(l, o);\n+\tret->ent.hash = xdiff_hash_string(l->line, l->len, o->xdl_opts);\n \tret->es = l;\n \tret->next_line = NULL;\n \n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"331030","messageId":"20171025184912.21657-2-sbeller@google.com","threadId":"47025","inReplyTo":"20171025184912.21657-1-sbeller@google.com","subject":"[PATCH 1/2] xdiff-interface: export comparing and hashing strings","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-25T18:49:11Z","receivedAt":"2017-10-25T18:50:50Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"This will turn out to be useful in a later patch.\n\nxdl_recmatch is exported in xdiff/xutils.h, to be used by various\nxdiff/*.c files, but not outside of xdiff/. This one makes it available\nto the outside, too.\n\nWhile at it, add documentation.\n\nSigned-off-by: Stefan Beller \n---\n xdiff-interface.c | 12 ++++++++++++\n xdiff-interface.h | 16 ++++++++++++++++\n 2 files changed, 28 insertions(+)\n\ndiff --git a/xdiff-interface.c b/xdiff-interface.c\nindex 018e033089..770e1f7f81 100644\n--- a/xdiff-interface.c\n+++ b/xdiff-interface.c\n@@ -5,6 +5,7 @@\n #include \"xdiff/xdiffi.h\"\n #include \"xdiff/xemit.h\"\n #include \"xdiff/xmacros.h\"\n+#include \"xdiff/xutils.h\"\n \n struct xdiff_emit_state {\n \txdiff_emit_consume_fn consume;\n@@ -296,6 +297,17 @@ void xdiff_clear_find_func(xdemitconf_t *xecfg)\n \t}\n }\n \n+unsigned long xdiff_hash_string(const char *s, size_t len, long flags)\n+{\n+\treturn xdl_hash_record(&s, s + len, flags);\n+}\n+\n+int xdiff_compare_lines(const char *l1, long s1,\n+\t\t\tconst char *l2, long s2, long flags)\n+{\n+\treturn xdl_recmatch(l1, s1, l2, s2, flags);\n+}\n+\n int git_xmerge_style = -1;\n \n int git_xmerge_config(const char *var, const char *value, void *cb)\ndiff --git a/xdiff-interface.h b/xdiff-interface.h\nindex 6f6ba9095d..135fc05d72 100644\n--- a/xdiff-interface.h\n+++ b/xdiff-interface.h\n@@ -29,4 +29,20 @@ extern void xdiff_clear_find_func(xdemitconf_t *xecfg);\n extern int git_xmerge_config(const char *var, const char *value, void *cb);\n extern int git_xmerge_style;\n \n+/*\n+ * Compare the strings l1 with l2 which are of size s1 and s2 respectively.\n+ * Returns 1 if the strings are deemed equal, 0 otherwise.\n+ * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n+ * are treated for the comparision.\n+ */\n+extern int xdiff_compare_lines(const char *l1, long s1,\n+\t\t\t const char *l2, long s2, long flags);\n+\n+/*\n+ * Returns a hash of the string s of length len.\n+ * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n+ * are treated for the hash.\n+ */\n+extern unsigned long xdiff_hash_string(const char *s, size_t len, long flags);\n+\n #endif\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"331031","messageId":"20171025184912.21657-1-sbeller@google.com","threadId":"47025","inReplyTo":"xmqqinf3izgm.fsf@gitster.mtv.corp.google.com","subject":"[PATCHv3 0/2] (x)diff cleanup: remove duplicate code","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-25T18:49:10Z","receivedAt":"2017-10-25T18:50:52Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"V3:\n* changed parameter names back to xdiff standard\n\nv2:\n* I realized that we don't have to change the hashing function of xdiff;\n we can rather change the hashing function for the move detection,\n which is less fundamental.\n (That way I can shrink the series down to 2 patches)\n* commented and renamed function parameters in the exposed xdiff functions.\n* applies on top of jk/diff-color-moved-fix.\n\nThanks,\nStefan\n\nv1:\nJunio wrote:\n\n> * I was hoping that the next_byte() and string_hash() thing, once\n> they are cleaned up, will eventually be shared with the xdiff/\n> code at the lower layer, which needs to do pretty much the same\n> in order to implement various whitespace ignoring options. I am\n> not sure how well the approach taken by the WIP patch meshes with\n> the needs of the lower layer.\n\nThis series does exactly this; although I chose to reuse the code in\nxdiff/xutils.c instead of the new fancy next_byte/string_hash, as that\ncode has seen more exercise already (hence I assume it has fewer bugs\nif any as well as its performance implications are well understood).\n\nHowever to do so, we need to pollute xdiff/xutils.c and include\nhashmap.h there (which also requires cache.h as that header has\nan inline function using BUG()), which I find a bit unfortunate but\nworth the trade off of using better tested code.\n\nThanks,\nStefan\n\nStefan Beller (2):\n xdiff-interface: export comparing and hashing strings\n diff.c: get rid of duplicate implementation\n\n diff.c | 82 +++----------------------------------------------------\n xdiff-interface.c | 12 ++++++++\n xdiff-interface.h | 16 +++++++++++\n 3 files changed, 32 insertions(+), 78 deletions(-)\n\n-- \n2.15.0.rc2.6.g953226eb5f\n\n"},{"id":"331061","messageId":"xmqqy3nyfy0h.fsf@gitster.mtv.corp.google.com","threadId":"47025","inReplyTo":"20171025184912.21657-3-sbeller@google.com","subject":"Re: [PATCH 2/2] diff.c: get rid of duplicate implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-26T02:23:10Z","receivedAt":"2017-10-26T02:23:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stefan Beller writes:\n\n> The implementations in diff.c to detect moved lines needs to compare\n> strings and hash strings, which is implemented in that file, as well\n> as in the xdiff library.\n>\n> Remove the rather recent implementation in diff.c and rely on the well\n> exercised code in the xdiff lib.\n> ...\n> static int moved_entry_cmp(const struct diff_options *diffopt,\n> \t\t\t const struct moved_entry *a,\n> \t\t\t const struct moved_entry *b,\n> \t\t\t const void *keydata)\n> {\n> -\tconst char *ap = a->es->line, *ae = a->es->line + a->es->len;\n> -\tconst char *bp = b->es->line, *be = b->es->line + b->es->len;\n> - ...\n> +\treturn !xdiff_compare_lines(a->es->line, a->es->len,\n> +\t\t\t\t b->es->line, b->es->len,\n> +\t\t\t\t diffopt->xdl_opts);\n> }\n\nOK, xdiff's xdl_recmatch() takes counted strings, and line[len] is\none byte beyond the end of the line (where LF typically sits), which\nis the same convention as how \"emitted_symbol\" represents a line, so\nnot just the implementation replaced with a known-working one, but\nalso the code calls the helper with correct calling convention ;-)\n\n> -\tret->ent.hash = get_string_hash(l, o);\n> +\tret->ent.hash = xdiff_hash_string(l->line, l->len, o->xdl_opts);\n\nLikewise. Looks good.\n\nWill queue.\n"},{"id":"331096","messageId":"347a9bca-29f3-9847-2f51-1682d7a6da53@web.de","threadId":"47025","inReplyTo":"CAGZ79kbJS68qL0=WTZVBfmSDXCii0HT60TGxx2MSiH_cK_tBCw@mail.gmail.com","subject":"Re: [PATCH 2/4] xdiff-interface: export comparing and hashing strings","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-10-26T17:03:57Z","receivedAt":"2017-10-26T17:04:06Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 24.10.2017 um 22:42 schrieb Stefan Beller:\n> On Tue, Oct 24, 2017 at 1:23 PM, René Scharfe wrote:\n> \n>> xdl_recmatch() is already exported; why not use it without this\n>> wrapper?\n> \n> It is exported in xdiff/xutils.h, to be used by various xdiff/*.c files, but\n> not outside of xdiff/. This one makes it available to the outside, too.\n\nAh, right, somehow I mixed that up with xdiff/xdiff.h, which is already\nincluded by two builtins.\n\nRené\n"},{"id":"331097","messageId":"3f656948-273f-e01d-ad52-e460059571da@web.de","threadId":"47025","inReplyTo":"20171025184912.21657-2-sbeller@google.com","subject":"Re: [PATCH 1/2] xdiff-interface: export comparing and hashing strings","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-10-26T17:12:15Z","receivedAt":"2017-10-26T17:12:33Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 25.10.2017 um 20:49 schrieb Stefan Beller:\n> +/*\n> + * Compare the strings l1 with l2 which are of size s1 and s2 respectively.\n> + * Returns 1 if the strings are deemed equal, 0 otherwise.\n> + * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n> + * are treated for the comparision.\n> + */\n> +extern int xdiff_compare_lines(const char *l1, long s1,\n> +\t\t\t const char *l2, long s2, long flags);\n\nWith the added comment it's OK here.\n\nStill, I find the tendency in libxdiff to use the shortest possible\nvariable names to be hard on the eyes. That math-like notation may have\nits place in that external library, but I think we should be careful\nlest it spreads.\n\nRené\n"},{"id":"331100","messageId":"b6012c19-c067-1700-12de-2a42c25c9c7d@web.de","threadId":"47025","inReplyTo":"20171025184912.21657-3-sbeller@google.com","subject":"Re: [PATCH 2/2] diff.c: get rid of duplicate implementation","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-10-26T17:43:19Z","receivedAt":"2017-10-26T17:43:39Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 25.10.2017 um 20:49 schrieb Stefan Beller:\n> The implementations in diff.c to detect moved lines needs to compare\n> strings and hash strings, which is implemented in that file, as well\n> as in the xdiff library.\n> \n> Remove the rather recent implementation in diff.c and rely on the well\n> exercised code in the xdiff lib.\n> \n> With this change the hash used for bucketing the strings for the moved\n> line detection changes from FNV32 (that is provided via the hashmaps\n> memhash) to DJB2 (which is used internally in xdiff). Benchmarks found\n> on the web[1] do not indicate that these hashes are different in\n> performance for readable strings.\n> \n> [1] https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed\n\nAwesome comparison! It calls the variant used in libxdiff DJB2a (which\nuses xor to mix in the new char) instead of DJB2 (which uses addition).\n\nThere's also https://www.strchr.com/hash_functions, which lists DJB2\nas Bernstein. Both functions rank somewhere in the middle of that list.\n\n> Signed-off-by: Stefan Beller \n> ---\n> diff.c | 82 ++++--------------------------------------------------------------\n> 1 file changed, 4 insertions(+), 78 deletions(-)\n\nVery nice.\n\nRené\n"},{"id":"331143","messageId":"xmqqefppcbec.fsf@gitster.mtv.corp.google.com","threadId":"47025","inReplyTo":"3f656948-273f-e01d-ad52-e460059571da@web.de","subject":"Re: [PATCH 1/2] xdiff-interface: export comparing and hashing strings","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-27T07:12:11Z","receivedAt":"2017-10-27T07:12:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe writes:\n\n> Am 25.10.2017 um 20:49 schrieb Stefan Beller:\n>> +/*\n>> + * Compare the strings l1 with l2 which are of size s1 and s2 respectively.\n>> + * Returns 1 if the strings are deemed equal, 0 otherwise.\n>> + * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n>> + * are treated for the comparision.\n>> + */\n>> +extern int xdiff_compare_lines(const char *l1, long s1,\n>> +\t\t\t const char *l2, long s2, long flags);\n>\n> With the added comment it's OK here.\n>\n> Still, I find the tendency in libxdiff to use the shortest possible\n> variable names to be hard on the eyes. That math-like notation may have\n> its place in that external library, but I think we should be careful\n> lest it spreads.\n\nYeah, I tend to agree. The xdiff-interface is at the (surprise!)\ninterface layer, so we could make it follow the style of either one,\nbut we seem to have picked up the convention of the lower layer,\nso...\n\nBy the way, I was looking at the code around this area while\nreviewing the cr-at-eol thing, and noticed a couple of things:\n\n\n * combine-diff.c special cases only IGNORE_WHITESPACE and\n IGNORE_WHITESPACE_CHANGE but no other IGNORE_WHITESPACE things; I\n have a suspicion that this is not because IGNORE_WHITESPACE_AT_EOL\n does not have to special cased by the codepath, but only because\n the combine-diff.c refactoring predates the introduction of\n ws-at-eol thing?\n\n The machinery uses its own match_string_spaces() helper; it may\n make sense to use the same xdiff_compare_lines() in its callers\n and get rid of this helper function.\n\n * diff_setup_done() sets DIFF_FROM_CONTENTS when any of the\n IGNORE_WHITESPACE bits is true, to allow \"git diff -q\n --ignore-something\" would do the right thing. We do not however\n give a similar special case to XDF_IGNORE_BLANK_LINES.\n\n $ echo >>Makefile && git diff $option --ignore-blank-lines Makefile\n\n exits with 1 when option=--exit-code and it exits with 0 when\n option=-q\n\n\nFor now I'll leve these as #leftoverbits, but I may come back to the\nlatter soonish. I won't come back to the former until Stefan's\nrefactor hits 'master', though.\n\n"},{"id":"331178","messageId":"CAGZ79kZgXZsBOf=9MZnoOCpJmARbaEaLPDBVAGN4GMvxhMotog@mail.gmail.com","threadId":"47025","inReplyTo":"xmqqefppcbec.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH 1/2] xdiff-interface: export comparing and hashing strings","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2017-10-27T17:15:30Z","receivedAt":"2017-10-27T17:15:37Z","isPatch":true,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Oct 27, 2017 at 12:12 AM, Junio C Hamano wrote:\n> René Scharfe writes:\n>\n>> Am 25.10.2017 um 20:49 schrieb Stefan Beller:\n>>> +/*\n>>> + * Compare the strings l1 with l2 which are of size s1 and s2 respectively.\n>>> + * Returns 1 if the strings are deemed equal, 0 otherwise.\n>>> + * The `flags` given as XDF_WHITESPACE_FLAGS determine how white spaces\n>>> + * are treated for the comparision.\n>>> + */\n>>> +extern int xdiff_compare_lines(const char *l1, long s1,\n>>> + const char *l2, long s2, long flags);\n>>\n>> With the added comment it's OK here.\n>>\n>> Still, I find the tendency in libxdiff to use the shortest possible\n>> variable names to be hard on the eyes. That math-like notation may have\n>> its place in that external library, but I think we should be careful\n>> lest it spreads.\n>\n> Yeah, I tend to agree. The xdiff-interface is at the (surprise!)\n> interface layer, so we could make it follow the style of either one,\n> but we seem to have picked up the convention of the lower layer,\n> so...\n>\n> By the way, I was looking at the code around this area while\n> reviewing the cr-at-eol thing, and noticed a couple of things:\n>\n>\n> * combine-diff.c special cases only IGNORE_WHITESPACE and\n> IGNORE_WHITESPACE_CHANGE but no other IGNORE_WHITESPACE things; I\n> have a suspicion that this is not because IGNORE_WHITESPACE_AT_EOL\n> does not have to special cased by the codepath, but only because\n> the combine-diff.c refactoring predates the introduction of\n> ws-at-eol thing?\n\nI wonder how much overlap between the IGNORE_WHITESPACE_AT_EOL\nand CRLF-AT-EOL is (maybe these can be combined, as per the root of\nthis discussion)\n\n> The machinery uses its own match_string_spaces() helper; it may\n> make sense to use the same xdiff_compare_lines() in its callers\n> and get rid of this helper function.\n\nSpeaking of xdiff_compare_lines, it serves the special purpose of the\nmove detection as well as its internal use cases, but we may need to\nchange its interface/implementation in the future, to align it with strcmp,\ncurrently the compare function only returns equality, not an order.\n\n> * diff_setup_done() sets DIFF_FROM_CONTENTS when any of the\n> IGNORE_WHITESPACE bits is true, to allow \"git diff -q\n> --ignore-something\" would do the right thing. We do not however\n> give a similar special case to XDF_IGNORE_BLANK_LINES.\n>\n> $ echo >>Makefile && git diff $option --ignore-blank-lines Makefile\n>\n> exits with 1 when option=--exit-code and it exits with 0 when\n> option=-q\n>\n>\n> For now I'll leve these as #leftoverbits, but I may come back to the\n> latter soonish. I won't come back to the former until Stefan's\n> refactor hits 'master', though.\n\nwhich is presumably after the 2.15 release.\n\nTo tack on the #leftoverbits: The --color-moved detection doesn't\npay attention to XDF_IGNORE_BLANK_LINES (which is tricky as\nit is on the per-line layer. If we want to ignore spurious blank lines,\nwe'd have to check for this flag in diff.c in mark_color_as_moved(..)\nin the block\n /* Check any potential block runs, advance each or nullify */\n\nThanks,\nStefan\n"},{"id":"331397","messageId":"20171030175941.tbjlfp72txgod22x@sigill.intra.peff.net","threadId":"47025","inReplyTo":"b6012c19-c067-1700-12de-2a42c25c9c7d@web.de","subject":"Re: [PATCH 2/2] diff.c: get rid of duplicate implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-30T17:59:41Z","receivedAt":"2017-10-30T17:59:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Oct 26, 2017 at 07:43:19PM +0200, René Scharfe wrote:\n\n> Am 25.10.2017 um 20:49 schrieb Stefan Beller:\n> > The implementations in diff.c to detect moved lines needs to compare\n> > strings and hash strings, which is implemented in that file, as well\n> > as in the xdiff library.\n> > \n> > Remove the rather recent implementation in diff.c and rely on the well\n> > exercised code in the xdiff lib.\n> > \n> > With this change the hash used for bucketing the strings for the moved\n> > line detection changes from FNV32 (that is provided via the hashmaps\n> > memhash) to DJB2 (which is used internally in xdiff). Benchmarks found\n> > on the web[1] do not indicate that these hashes are different in\n> > performance for readable strings.\n> > \n> > [1] https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed\n> \n> Awesome comparison! It calls the variant used in libxdiff DJB2a (which\n> uses xor to mix in the new char) instead of DJB2 (which uses addition).\n> \n> There's also https://www.strchr.com/hash_functions, which lists DJB2\n> as Bernstein. Both functions rank somewhere in the middle of that list.\n\nFWIW, I did some experiments with Murmur3 and SipHash a while back, but\nI don't think I came up with anything faster than the existing code.\nOTOH, moving to SipHash gives us the ability to randomize the hashes,\nwhich can resist some DoS attacks (although as I've said before,\ncomputing arbitrary diffs for untrusted strangers is pretty much a\nDoS-in-a-box).\n\nAnyway, I rebased them and ran p4000[1], with does show some results:\n\nTest origin jk/xdl-murmur3-wip jk/xdl-siphash-wip \n-------------------------------------------------------------------------------------------------------\n4000.1: log -3000 (baseline) 0.05(0.05+0.00) 0.05(0.05+0.00) +0.0% 0.05(0.05+0.00) +0.0% \n4000.2: log --raw -3000 (tree-only) 0.30(0.28+0.02) 0.30(0.28+0.01) +0.0% 0.30(0.28+0.02) +0.0% \n4000.3: log -p -3000 (Myers) 2.06(1.98+0.08) 1.90(1.85+0.05) -7.8% 2.32(2.25+0.07) +12.6%\n4000.4: log -p -3000 --histogram 2.50(2.42+0.07) 2.25(2.21+0.04) -10.0% 2.70(2.62+0.08) +8.0% \n4000.5: log -p -3000 --patience 2.58(2.52+0.06) 2.47(2.42+0.04) -4.3% 2.86(2.77+0.08) +10.9%\n\nSo it looks like murmur3 is indeed a little faster. SipHash is slower,\nwhich is too bad (because the randomization would be nice). I _think_\nback then I compared to XDL_FAST_HASH, which was a little faster even\nthan murmur3 (but generated too many collisions, which led to bad\nbehavior for certain cases).\n\nAnyway, those branches are at https://github.com/peff/git if anybody\nwants to look further. They probably need some cleanup. At the very\nleast, we'd probably need to teach the whitespace-ignoring hash function\nto use the same algorithm.\n\n-Peff\n\n[1] Actually, I added \"--no-merges\" to each command in p4000. It seems\n silly as it is, since the point is to compute a bunch of diffs.\n"},{"id":"331404","messageId":"20171030190710.w7pyokbfxzkjdqcx@sigill.intra.peff.net","threadId":"47025","inReplyTo":"20171030175941.tbjlfp72txgod22x@sigill.intra.peff.net","subject":"Re: [PATCH 2/2] diff.c: get rid of duplicate implementation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-10-30T19:07:10Z","receivedAt":"2017-10-30T19:07:16Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Oct 30, 2017 at 10:59:41AM -0700, Jeff King wrote:\n\n> > There's also https://www.strchr.com/hash_functions, which lists DJB2\n> > as Bernstein. Both functions rank somewhere in the middle of that list.\n> \n> FWIW, I did some experiments with Murmur3 and SipHash a while back, but\n> I don't think I came up with anything faster than the existing code.\n> OTOH, moving to SipHash gives us the ability to randomize the hashes,\n> which can resist some DoS attacks (although as I've said before,\n> computing arbitrary diffs for untrusted strangers is pretty much a\n> DoS-in-a-box).\n\nBy the way, one of the things that complicates plugging new functions\ninto xdiff's hashing is that xdl_hash_record() simultaneously computes\nthe hash _and_ finds the end-of-line marker.\n\nSo the \"siphash is only 10% slower\" number I showed came with quite a\nfew contortions to do both. Here it is compared to a more naive\napplication of the siphash code (i.e., memchr to find end-of-line, and\nthen feed the resulting bytes to siphash):\n\nTest origin HEAD^ jk/xdl-siphash-wip\n-------------------------------------------------------------------------------------------------------\n4000.1: log -3000 (baseline) 0.05(0.05+0.00) 0.05(0.05+0.00) +0.0% 0.05(0.05+0.00) +0.0%\n4000.2: log --raw -3000 (tree-only) 0.31(0.27+0.03) 0.31(0.27+0.03) +0.0% 0.31(0.27+0.03) +0.0%\n4000.3: log -p -3000 (Myers) 2.06(2.01+0.05) 2.30(2.21+0.09) +11.7% 2.96(2.91+0.04) +43.7%\n4000.4: log -p -3000 --histogram 2.44(2.38+0.06) 2.67(2.60+0.07) +9.4% 3.32(3.26+0.06) +36.1%\n4000.5: log -p -3000 --patience 2.57(2.47+0.09) 2.90(2.82+0.08) +12.8% 3.48(3.43+0.05) +35.4%\n\nThere \"origin\" is the existing djb hash, \"HEAD^\" is the complicated\n\"fast\" siphash (which I very well may have screwed up), and the final is\nthe more naive version, which is quite a bit slower.\n\n-Peff\n"}]}