XXH128 questions #479

New issue

Closed

opened 2020-11-28 03:20:34 -06:00 by yuvalroc · 28 comments

yuvalroc commented 2020-11-28 03:20:34 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Hi,
I have some questions on how xxh128 works:

1. Is it a bijective function from 16 Bytes input to 16 Bytes?
2. I saw that the code is quit different from xxh32\xxh64. However, I not sure I understand how it goes. When a documentation will be available on it?

Hi, I have some questions on how xxh128 works: 1) Is it a bijective function from 16 Bytes input to 16 Bytes? 2) I saw that the code is quit different from xxh32\xxh64. However, I not sure I understand how it goes. When a documentation will be available on it?

Cyan4973 commented 2020-11-28 12:25:39 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Is it a bijective function from 16 Bytes input to 16 Bytes?

Yes

When a documentation will be available on it?

Probably for v1.0. not anytime soon.

> Is it a bijective function from 16 Bytes input to 16 Bytes? Yes > When a documentation will be available on it? Probably for v1.0. not anytime soon.

yuvalroc commented 2021-01-15 08:24:45 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Thanks!
Following the question- is xxh128_low a permutation (the low bits 64 bits) between 8B keys and 8B keys?

Thanks! Following the question- is xxh128_low a permutation (the low bits 64 bits) between 8B keys and 8B keys?

Cyan4973 commented 2021-01-15 14:08:03 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

What do you mean ? Are you referring to a specific operation in the pipeline ?
Or do you inquire about the status of the lower 64-bits of XXH128 when the input is always a 64-bit value ?

What do you mean ? Are you referring to a specific operation in the pipeline ? Or do you inquire about the status of the lower 64-bits of `XXH128` when the input is always a 64-bit value ?

yuvalroc commented 2021-01-15 14:27:52 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Or do you inquire about the status of the lower 64-bits of XXH128 when the input is always a 64-bit value ?

This- i.e., the input is always 64-bit, the output is the low 64 bits of xxh3-128.

The high 64-bits can be shown that they are not a permutation.

>>Or do you inquire about the status of the lower 64-bits of XXH128 when the input is always a 64-bit value ? This- i.e., the input is always 64-bit, the output is the low 64 bits of xxh3-128. The high 64-bits can be shown that they are not a permutation.

yuvalroc commented 2021-01-16 08:21:40 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Using https://en.wikipedia.org/wiki/Cycle_detection, it can be shown two inputs x,y of 64bit, such that xxhash128low(x)=xxhash128low(y).
This means, xxhash128low does not avoids collisions, as opposed to xxh3-64.

Using https://en.wikipedia.org/wiki/Cycle_detection, it can be shown two inputs x,y of 64bit, such that xxhash128low(x)=xxhash128low(y). This means, xxhash128low does not avoids collisions, as opposed to xxh3-64.

yuvalroc commented 2021-01-16 08:23:06 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

The inputs 4547874448270207647 17028758783872633121, have the same 64-bit output (18437082715045604585).

The inputs 4547874448270207647 17028758783872633121, have the same 64-bit output (18437082715045604585).

Cyan4973 commented 2021-01-16 11:01:18 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Indeed, XXH3_64bits() is designed for 64->64 permutation,
while XXH3_128bits() is designed for 128->128 permutation.

It never was an objective to make XXH3_128.low64 a permutation of 64 bits input, and it seems it doesn't.

Indeed, `XXH3_64bits()` is designed for 64->64 permutation, while `XXH3_128bits()` is designed for 128->128 permutation. It never was an objective to make `XXH3_128.low64` a permutation of 64 bits input, and it seems it doesn't.

yuvalroc commented 2021-01-17 08:48:51 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Thanks!
Also, why there is a difference between 17-128B version, with 128B-240B and 240B-inf versions?
Why not use for all cases the 17-128B version?

Thanks! Also, why there is a difference between 17-128B version, with 128B-240B and 240B-inf versions? Why not use for all cases the 17-128B version?

easyaspi314 commented 2021-01-17 10:27:02 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Thanks!
Also, why there is a difference between 17-128B version, with 128B-240B and 240B-inf versions?
Why not use for all cases the 17-128B version?

Because then it would just be MUM hash.

Joking aside, the main reason is latency. The long loop uses SIMD code which often takes hundreds of cycles to start up

> Thanks! > Also, why there is a difference between 17-128B version, with 128B-240B and 240B-inf versions? > Why not use for all cases the 17-128B version? Because then it would just be MUM hash. Joking aside, the main reason is latency. The long loop uses SIMD code which often takes hundreds of cycles to start up

Cyan4973 commented 2021-01-17 13:22:39 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Indeed, the main loop is designed for vector processing.
But it's only efficient for a certain "minimum amount" of data (exact amount varies depending on cpu and compiler).
The 17-128B codec is designed to bridge that gap.

Later on, it was discovered that 128B might not be enough, since there is systematically a performance drop at 129B.
So this "area" was extended to 240B. However, as the formula for 17-128B wasn't immediately adaptable for 129-240B, another one was created instead for this second range.

There is a case to say that 17-240B could have been merged into a single range with a single formula, and that's fair. It wasn't that straightforward though, would have negatively impacted the existing 17-128 range, and with every change requiring a time-intensive validation, there is only so much time and attention available. So this 2-areas setup became permanent.

Indeed, the main loop is designed for vector processing. But it's only efficient for a certain "minimum amount" of data (exact amount varies depending on cpu and compiler). The 17-128B codec is designed to bridge that gap. Later on, it was discovered that 128B might not be enough, since there is systematically a performance drop at 129B. So this "area" was extended to 240B. However, as the formula for 17-128B wasn't immediately adaptable for 129-240B, another one was created instead for this second range. There is a case to say that 17-240B could have been merged into a single range with a single formula, and that's fair. It wasn't that straightforward though, would have negatively impacted the existing 17-128 range, and with every change requiring a time-intensive validation, there is only so much time and attention available. So this 2-areas setup became permanent.

yuvalroc commented 2021-01-17 13:45:13 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

I understand.
Do you know the quality of using the 17-128B codec over large keys?
For my purposes, I want to investigate the hash function as a term of quality and number of operations (i.e. minimize the number of adding, multiplying by constant, shifting and rotating). This is regardless of CPU.
The 17-128B codec seems to me simple, and maybe with great smhasher quality.

I understand. Do you know the quality of using the 17-128B codec over large keys? For my purposes, I want to investigate the hash function as a term of quality and number of operations (i.e. minimize the number of adding, multiplying by constant, shifting and rotating). This is regardless of CPU. The 17-128B codec seems to me simple, and maybe with great smhasher quality.

Cyan4973 commented 2021-01-17 14:12:52 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Do you know the quality of using the 17-128B codec over large keys?

You mean, using it for inputs larger than 128B ?

As mentioned, the 17-128 formula is not generic enough to go above 128B.
If it's updated naively in order to support more than 128B, there are some issues with risks of repeats and cancelations across 128B segments.

The 129-240B is much better in this respect, and could potentially be generalized to larger sizes. Yet, it has only been validated for 2x 128B segments, and going beyond that would likely require time and validation, as the scrambling stage and secret variability are a bit rigid. In short, it would require some work to reach "high quality" levels.

> Do you know the quality of using the 17-128B codec over large keys? You mean, using it for inputs larger than 128B ? As mentioned, the 17-128 formula is not generic enough to go above 128B. If it's updated naively in order to support more than 128B, there are some issues with risks of repeats and cancelations across 128B segments. The 129-240B is much better in this respect, and could _potentially_ be generalized to larger sizes. Yet, it has only been validated for 2x 128B segments, and going beyond that would likely require time and validation, as the scrambling stage and secret variability are a bit rigid. In short, it would require some work to reach "high quality" levels.

goodengineer commented 2021-03-10 05:31:17 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Hi,
I have some questions on how xxh128 works:

1. Is it a bijective function from 16 Bytes input to 16 Bytes?
2. I saw that the code is quite different from xxh32\xxh64. However, I'm not sure I understand how it goes. When a documentation will be available on it?

Please have tiny typo correction: ↥

> Hi, > I have some questions on how xxh128 works: > > 1. Is it a bijective function from 16 Bytes input to 16 Bytes? > 2. I saw that the code is quite different from xxh32\xxh64. However, I'm not sure I understand how it goes. When a documentation will be available on it? Please have tiny typo correction: ↥

flawrist commented 2021-03-17 14:55:45 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Err… Sorry, but I am lost. xxhsum (0.8.0) says -H switch (aggrrhh, have to press SHIFT, why not -a or something) enables us to select an algorithm to use: either 0, 1, or 2 (aggrrhh, enumerating countable objects from zero is beyond my comprehension). Now, here comes the confusion, because there are XXH32, XXH64, XXH128, and… XXH3. And some hashing apps pour on the fire. Could you be so kind to state clearly, once and for all, which is which?

Err… Sorry, but I am lost. `xxhsum` (0.8.0) says `-H` switch (aggrrhh, have to press SHIFT, why not `-a` or something) enables us to select an algorithm to use: either `0`, `1`, or `2` (aggrrhh, enumerating countable objects from zero is beyond my comprehension). Now, here comes the confusion, because there are XXH32, XXH64, XXH128, and… XXH3. And some hashing apps pour on the fire. Could you be so kind to state clearly, once and for all, which is which?  ` ` 

Cyan4973 commented 2021-03-17 15:07:36 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

man xxhsum
(...)
       -HHASHTYPE
              Hash selection. HASHTYPE means 0=32bits, 1=64bits, 2=128bits. Alternatively, HASHTYPE 32=32bits, 64=64bits, 128=128bits. Default value is 1 (64bits)

I would recommend to rather use -H32, -H64 and -H128 for clarity.

Now, more accurately :
-H32 => XXH32(,,0)
-H64 => XXH64(,,0)
-H128 => XXH128(,,0) => XXH3_128bits()

As one can see, there is no option to make xxhsum output XXH3_64bits() return value,
precisely to avoid confusion with XXH64() return value (which is still the default).

Though this capability has been asked a few times already,
so maybe an option will be created for it.
Be sure that when it happens, it will be designed in a way which avoids confusion with XXH64().

``` man xxhsum (...) -HHASHTYPE Hash selection. HASHTYPE means 0=32bits, 1=64bits, 2=128bits. Alternatively, HASHTYPE 32=32bits, 64=64bits, 128=128bits. Default value is 1 (64bits) ``` I would recommend to rather use `-H32`, `-H64` and `-H128` for clarity. Now, more accurately : `-H32` => `XXH32(,,0)` `-H64` => `XXH64(,,0)` `-H128` => `XXH128(,,0)` => `XXH3_128bits()` As one can see, there is no option to make `xxhsum` output `XXH3_64bits()` return value, precisely to avoid confusion with `XXH64()` return value (which is still the default). Though this capability has been asked a few times already, so maybe an option will be created for it. Be sure that when it happens, it will be designed in a way which avoids confusion with `XXH64()`.

👀 1

flawrist commented 2021-03-17 19:31:22 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

And one more thing, once and for all, @Cyan4973. Is it true that XXH (preferably with -H128) is to be used (by the masses) instead of CRC32 only to check if data is transmitted w/o errors and to detect data rot, whereas if one needs to detect malicious changes when filesize stays the same, it is recommended to use Blake3 or another (not broken) cryptohash?

cc: @oconnor663, @namazso, @Dhyfer1

And one more thing, once and for all, @Cyan4973. Is it true that XXH (preferably with `-H128`) is to be used (by _the masses_) instead of `CRC32` only to check if data is transmitted w/o errors and to detect data rot, whereas if one needs to detect malicious changes when filesize stays the same, it is recommended to use Blake3 or another (not broken) cryptohash? cc: @oconnor663, @namazso, @Dhyfer1

Cyan4973 commented 2021-03-17 19:44:48 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Yep, that's correct.

Although for the second case, one also has to design an out-of-band channel to pass the crypto checksum, not just send it alongside the data, otherwise it's just as easy to simply change both the content and the checksum so they still match.

Yep, that's correct. Although for the second case, one also has to design an out-of-band channel to pass the crypto checksum, not just send it alongside the data, otherwise it's just as easy to simply change both the content _and_ the checksum so they still match.

👀 1

flawrist commented 2021-03-19 11:56:25 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

@Cyan4973, just to let you know how confusion about XXH128 vs XXH3 spreads. Now it comes from Rsync.

@Cyan4973, just to let you know how confusion about XXH128 vs XXH3 spreads. Now it comes from [Rsync][1].  [1]: https://jl-workshop.com/RSync-for-Windows-Free-Download/

flawrist commented 2021-04-17 13:50:50 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

$ xxhsum080 -b
Sample of 100 KB...
 1#XXH32                         :     102400 ->    63431 it/s ( 6194.5 MB/s)
 3#XXH64                         :     102400 ->    64590 it/s ( 6307.6 MB/s)
 5#XXH3_64b                      :     102400 ->    77303 it/s ( 7549.2 MB/s)
11#XXH128                        :     102400 ->    77150 it/s ( 7534.2 MB/s)

XXH3_64b algo, not ready to be used via -H switch at present, is yet competing with others during the benchmark.
I wonder if it will replace the current default XXH64 over time, given its more impressive results?

``` console $ xxhsum080 -b Sample of 100 KB... 1#XXH32 : 102400 -> 63431 it/s ( 6194.5 MB/s) 3#XXH64 : 102400 -> 64590 it/s ( 6307.6 MB/s) 5#XXH3_64b : 102400 -> 77303 it/s ( 7549.2 MB/s) 11#XXH128 : 102400 -> 77150 it/s ( 7534.2 MB/s) ``` XXH3_64b algo, not ready to be used via `-H` switch at present, is yet competing with others during the benchmark. I wonder if it will replace the current default XXH64 over time, given its more impressive results?

Cyan4973 commented 2021-08-09 18:49:04 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

I wonder if it will replace the current default XXH64 over time, given its more impressive results?

XXH3_64b will never "replace" XXH64, since this last one is present since a long time and has been deployed in many applications,
but it could be added as another output format,
provided there is a way to guarantee that its output can't be confused with XXH64.

> I wonder if it will replace the current default XXH64 over time, given its more impressive results? `XXH3_64b` will never "replace" `XXH64`, since this last one is present since a long time and has been deployed in many applications, but it could be added as another output format, provided there is a way to guarantee that its output can't be confused with `XXH64`.

👀 1

flawrist commented 2021-12-06 05:23:41 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

0.8.1 changelog contains a few claims about the performance improvement, but (0.8.0 results)…

$ xxhsum081.exe -b
xxhsum.exe 0.8.1 by Yann Collet
compiled as 64-bit x86_64 autoVec little endian with GCC 11.2.0
Sample of 100 KB...
 1#XXH32                         :     102400 ->    62565 it/s ( 6109.9 MB/s)
 3#XXH64                         :     102400 ->    63748 it/s ( 6225.4 MB/s)
 5#XXH3_64b                      :     102400 ->    67592 it/s ( 6600.8 MB/s)
11#XXH128                        :     102400 ->    67390 it/s ( 6581.1 MB/s)

0.8.1 changelog contains a few claims about the performance improvement, but ([0.8.0 results][1])… ``` console $ xxhsum081.exe -b xxhsum.exe 0.8.1 by Yann Collet compiled as 64-bit x86_64 autoVec little endian with GCC 11.2.0 Sample of 100 KB... 1#XXH32 : 102400 -> 62565 it/s ( 6109.9 MB/s) 3#XXH64 : 102400 -> 63748 it/s ( 6225.4 MB/s) 5#XXH3_64b : 102400 -> 67592 it/s ( 6600.8 MB/s) 11#XXH128 : 102400 -> 67390 it/s ( 6581.1 MB/s) ``` [1]: https://github.com/Cyan4973/xxHash/issues/479#issuecomment-821869872

Cyan4973 commented 2021-12-06 11:57:41 -06:00 (Migrated from github.com)

• Copy link
• Copy Markdown

v0.8.1 performance improvements are only for the streaming mode, which is not tested in the "basic" -b benchmark mode.

For example, to benchmark XXH3_stream on v0.8.1, try xxhsum -b21.

The exact list of modes can change depending on versions. For a detailed list of all benchmarked modes, try xxhsum -b99i0

`v0.8.1` performance improvements are only for the streaming mode, which is not tested in the "basic" `-b` benchmark mode. For example, to benchmark `XXH3_stream` on v0.8.1, try `xxhsum -b21`. The exact list of modes can change depending on versions. For a detailed list of all benchmarked modes, try `xxhsum -b99i0`

👀 1

AlonGuetaR commented 2022-08-20 05:21:34 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Indeed, XXH3_64bits() is designed for 64->64 permutation, while XXH3_128bits() is designed for 128->128 permutation.

It never was an objective to make XXH3_128.low64 a permutation of 64 bits input, and it seems it doesn't.

So, in case I want to hash a 128 bits key to a 64 bits hash value, what should be my preferred option, XXH3_64bits() or XXH3_128bits() (and taking only the low/high bits)? In terms of speed and collision ratio.

> Indeed, `XXH3_64bits()` is designed for 64->64 permutation, while `XXH3_128bits()` is designed for 128->128 permutation. > > It never was an objective to make `XXH3_128.low64` a permutation of 64 bits input, and it seems it doesn't. So, in case I want to hash a 128 bits key to a 64 bits hash value, what should be my preferred option, `XXH3_64bits()` or `XXH3_128bits()` (and taking only the low/high bits)? In terms of speed and collision ratio.

Cyan4973 commented 2022-08-20 14:06:40 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

XXH3_64bits() is expected to be slightly better for this scenario.

`XXH3_64bits()` is expected to be slightly better for this scenario.

calvin2021y commented 2024-07-03 06:30:48 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Is it a bijective function from 16 Bytes input to 16 Bytes?

Yes

When a documentation will be available on it?

Probably for v1.0. not anytime soon.

hi @Cyan4973

Correct me if I am wrong.

A bijective function from 16 Bytes input to 16 Bytes is able to do the reverse compute. like this:

const a = random();
const b = bijective(a);
const c = bijective(b);
assert( a == c);

The default XXH3_128bits is not able to do this. Any comments ?

> > Is it a bijective function from 16 Bytes input to 16 Bytes? > > Yes > > > When a documentation will be available on it? > > Probably for v1.0. not anytime soon. hi @Cyan4973 Correct me if I am wrong. A bijective function from 16 Bytes input to 16 Bytes is able to do the reverse compute. like this: ```c const a = random(); const b = bijective(a); const c = bijective(b); assert( a == c); ``` The default XXH3_128bits is not able to do this. Any comments ?

Cyan4973 commented 2024-07-03 16:45:30 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Your example would imply that bijective functions are their own inverse.
Such corner case is called an involution.
Most bijective functions are not involutions.

Your example would imply that bijective functions are their own inverse. Such corner case is called an [involution](https://en.wikipedia.org/wiki/Involution_(mathematics)). Most bijective functions are not involutions.

calvin2021y commented 2024-07-04 05:37:20 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Thanks for explain.

Is is possible to modify XXH128 to make it involution?

Thanks for explain. Is is possible to modify XXH128 to make it involution?

Cyan4973 commented 2024-07-04 16:03:26 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

No, this would mean changing XXH128 results so that they are no longer compatible with already deployed XXH128.

No, this would mean changing `XXH128` results so that they are no longer compatible with already deployed `XXH128`.

Sign in to join this conversation.

No Branch/Tag specified

Branches Tags

dev

dependabot/github_actions/actions/upload-artifact-7.0.2

dependabot/github_actions/actions/download-artifact-8.0.2

dependabot/github_actions/actions/setup-node-7.1.0

archive/20261011T062114Z-rescue/fhgffy/fix/cmake-dispatch-off

dependabot/github_actions/msys2/setup-msys2-2.33.0

archive/20261011T062114Z-rescue/filtede98/fix-null-guards

ci/release-windows

fix/mingw-exe-symlink

gh-pages

release

ci/pin-actions

docs/refresh-readme

archive/20261011T062114Z-recovered/docs/refresh-readme

v0.8.4

v0.8.3

v0.8.2

v0.8.1

v0.8.0

v0.7.4

v0.7.3

v0.7.2

v0.7.1

v0.7.0

graphs

v0.6.5

v0.6.4

v0.6.3

v0.6.2

v0.6.1

v0.6.0

v0.5.1

v0.5.0

r42

r41

r40

r39

r38

r37

r36

r35

Labels

Clear labels   

announcement

  

bug

  

build

  

CI

Continuous Integration tests

  

dependencies

Pull requests that update a dependency file

  

documentation

  

duplicate

  

enhancement

  

experience feedback

  

feature request

  

github_actions

Pull requests that update GitHub Actions code

  

help wanted

  

install

  

invalid

  

Long-term

  

optimization

  

portability

  

question

  

target-specific

issue triggered in a specific environment (harware, compiler, OS)

  

test issue

  

wontfix

No labels

announcement

bug

build

CI

dependencies

documentation

duplicate

enhancement

experience feedback

feature request

github_actions

help wanted

install

invalid

Long-term

optimization

portability

question

target-specific

test issue

wontfix

Milestone

Clear milestone

No items

No milestone

Assignees

Clear assignees

No assignees

1 participant

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

gh-Cyan4973/xxHash#479

No description provided.