Uneven chunk size in xxh3 stream computes wrong hash

WayneD commented

2020-05-28 13:05:56 -05:00

(Migrated from github.com)

I noticed a difference in the computing of an xxh3 (and xxh128) hash when the chunks of data are of uneven size. I'm testing xxh3 for eventual inclusion in rsync (once it stabilizes), and when transfer compression is used, the chunk sizes on the receiving side can vary wildly, causing the file checksum to be erroneous.

I created a simple test case while I was diagnosing the issue, but it appears to not really depend on the data (though I supplied some in the test case) but on the weird chunk sizes. Just run "make" and it will compile the simple C program and process the 2 test files through it (one with even chunks, and one with uneven chunks).

streaming-bug.tar.gz

(Note: I updated the tar file to avoid an extra 0-length update call after each chunk. The input files have a trailing newline added to each chunk's text and tester.c was not discarding it, resulting in a 0-byte chunk due to the empty line. It didn't affect the end result, but it's cleaner with the change.)

I noticed a difference in the computing of an xxh3 (and xxh128) hash when the chunks of data are of uneven size. I'm testing xxh3 for eventual inclusion in rsync (once it stabilizes), and when transfer compression is used, the chunk sizes on the receiving side can vary wildly, causing the file checksum to be erroneous. I created a simple test case while I was diagnosing the issue, but it appears to not really depend on the data (though I supplied some in the test case) but on the weird chunk sizes. Just run "make" and it will compile the simple C program and process the 2 test files through it (one with even chunks, and one with uneven chunks). [streaming-bug.tar.gz](https://github.com/Cyan4973/xxHash/files/4697941/streaming-bug.tar.gz) (Note: I updated the tar file to avoid an extra 0-length update call after each chunk. The input files have a trailing newline added to each chunk's text and tester.c was not discarding it, resulting in a 0-byte chunk due to the empty line. It didn't affect the end result, but it's cleaner with the change.)

👍 1 👀 1

Cyan4973 commented

2020-05-28 17:14:27 -05:00

(Migrated from github.com)

I confirm I can reproduce the issue with the linked source code.

Reasons for the error is still unclear.
Another test, which ingests data in segments of random length, seems to work fine so far, using exactly the same API.
Investigation is ongoing.

I confirm I can reproduce the issue with the linked source code. Reasons for the error is still unclear. Another test, which ingests data in segments of random length, seems to work fine so far, using exactly the same API. Investigation is ongoing.

easyaspi314 commented

2020-05-28 17:44:10 -05:00

(Migrated from github.com)

Hmmmmmmm there's definitely more things awry here.

If I add the single shot function as well, I get a third result.

./tester normal-chunks uneven-chunks

normal-chunks
incr:   cf3093cedd619ac9
full:   cf3093cedd619ac9
single: 8ef77a435d6e1fa9

uneven-chunks
incr:   ba74115927b80788
full:   cf3093cedd619ac9
single: 8ef77a435d6e1fa9

But if I replace everything with the equivalent XXH64 functions, they all return the same result.

./tester normal-chunks uneven-chunks
                                                                                   normal-chunks
incr:   98a65b63b84f8277
full:   98a65b63b84f8277
single: 98a65b63b84f8277

uneven-chunks
incr:   98a65b63b84f8277
full:   98a65b63b84f8277
single: 98a65b63b84f8277

Hmmmmmmm there's definitely more things awry here. If I add the single shot function as well, I get a *third* result. ``` ./tester normal-chunks uneven-chunks normal-chunks incr: cf3093cedd619ac9 full: cf3093cedd619ac9 single: 8ef77a435d6e1fa9 uneven-chunks incr: ba74115927b80788 full: cf3093cedd619ac9 single: 8ef77a435d6e1fa9 ``` But if I replace everything with the equivalent XXH64 functions, they all return the same result. ``` ./tester normal-chunks uneven-chunks normal-chunks incr: 98a65b63b84f8277 full: 98a65b63b84f8277 single: 98a65b63b84f8277 uneven-chunks incr: 98a65b63b84f8277 full: 98a65b63b84f8277 single: 98a65b63b84f8277 ```

👍 1

Cyan4973 commented

2020-05-28 17:55:24 -05:00

(Migrated from github.com)

OK, I think I get it.
It requires a specific sequence of sizes to show up,
but I'm nonetheless surprised this issue did not show up during tests.
Something must be improved there.

OK, I think I get it. It requires a specific sequence of sizes to show up, but I'm nonetheless surprised this issue did not show up during tests. Something must be improved there.

Cyan4973 commented

2020-05-28 17:59:06 -05:00

(Migrated from github.com)

OK, fixed it.
Indeed, it was a pretty nasty bug. Thanks @WayneD for pointing that out !

I must now think of a way to trigger that bug during tests, and make it part of the PR.

OK, fixed it. Indeed, it was a pretty nasty bug. Thanks @WayneD for pointing that out ! I must now think of a way to trigger that bug during tests, and make it part of the PR.

WayneD commented

2020-05-28 19:39:34 -05:00

(Migrated from github.com)

Great work! I'm glad it wasn't too hard to fix it. I guess I just got "lucky" with an rsync test run combo of xxh128 checksums + a compression test then ended up with reproducible failure (and then I just had rsync write out the checksum call sequence that was failing in a simple file format).

I've verified that your "fix378" branch works fine in my rsync test run that was failing.

Great work! I'm glad it wasn't too hard to fix it. I guess I just got "lucky" with an rsync test run combo of xxh128 checksums + a compression test then ended up with reproducible failure (and then I just had rsync write out the checksum call sequence that was failing in a simple file format). I've verified that your "fix378" branch works fine in my rsync test run that was failing.

👍 1

WayneD commented

2020-05-28 19:55:44 -05:00

(Migrated from github.com)

Now I just need to figure out why rsync is computing a different checksum value for about 1/4 of the copied files I just copied compared to what xxh128 outputs (where no such issue occurs when comparing xxh64 values).

WayneD commented

2020-05-28 20:46:52 -05:00

(Migrated from github.com)

Things are matching up correctly now. I think that I had only re-linked my code initially and I had to recompile it for it to be fully fixed.

👍 1

Rows
Columns

Uneven chunk size in xxh3 stream computes wrong hash #378