private pure subroutine fnv1a_byte64(state, byte_value)
One FNV-1a round: exclusive-or in a byte, then multiply by the prime.
There is no integer kind wider than int64 to compute the product in
and mask back, the way the 32-bit round does. Instead the multiply is
done modulo 264 directly, using the structure of the prime:
0x100000001B3 is exactly 240 + 435, so
h * prime = (h << 40) + h * 435 (mod 2**64)
The shift discards the bits that leave the top, which is the reduction
modulo 264. The remaining h * 435 is formed on two 32-bit limbs.
Each partial product is below 241, so neither can overflow a signed
int64, and no carry has to be propagated between them: the low
limb’s product is added in whole, and the high limb’s contributes only
the 32 bits that have not already left the top of the word. Both
additions go through u64_add, which wraps rather than overflowing.
Two multiplies per byte, against the ten a general u64_mul would
cost. A 16-bit-limb version with carries is also exact but needs four,
and measured 2.18x the cost of the 32-bit hash per byte where this one
measures 1.77x (gfortran -O2, 64 MiB, best of three).
Nodes of different colours represent the following:
Solid arrows point from a procedure to one which it calls. Dashed
arrows point from an interface to procedures which implement that interface.
This could include the module procedures in a generic interface or the
implementation in a submodule of an interface in a parent module.
Where possible, edges connecting nodes are
given different colours to make them easier to distinguish in
large graphs.
Nodes of different colours represent the following:
Solid arrows point from a procedure to one which it calls. Dashed
arrows point from an interface to procedures which implement that interface.
This could include the module procedures in a generic interface or the
implementation in a submodule of an interface in a parent module.
Where possible, edges connecting nodes are
given different colours to make them easier to distinguish in
large graphs.
Variables
Type
Visibility
Attributes
Name
Initial
integer(kind=int64),
private
::
h
integer(kind=int64),
private
::
high
integer(kind=int64),
private
::
low
Source Code
pure subroutine fnv1a_byte64(state,byte_value)!! One FNV-1a round: exclusive-or in a byte, then multiply by the prime.!!!! There is no integer kind wider than `int64` to compute the product in!! and mask back, the way the 32-bit round does. Instead the multiply is!! done modulo 2**64 directly, using the structure of the prime:!! 0x100000001B3 is exactly 2**40 + 435, so!!!! ```!! h * prime = (h << 40) + h * 435 (mod 2**64)!! ```!!!! The shift discards the bits that leave the top, which is the reduction!! modulo 2**64. The remaining `h * 435` is formed on two 32-bit limbs.!! Each partial product is below 2**41, so neither can overflow a signed!! `int64`, and no carry has to be propagated between them: the low!! limb's product is added in whole, and the high limb's contributes only!! the 32 bits that have not already left the top of the word. Both!! additions go through `u64_add`, which wraps rather than overflowing.!!!! Two multiplies per byte, against the ten a general `u64_mul` would!! cost. A 16-bit-limb version with carries is also exact but needs four,!! and measured 2.18x the cost of the 32-bit hash per byte where this one!! measures 1.77x (gfortran -O2, 64 MiB, best of three).integer(int64),intent(inout)::stateinteger(int64),intent(in)::byte_value!! A single byte, 0 to 255.integer(int64)::h,low,highh=ieor(state,byte_value)low=iand(h,LIMB_MASK)*FNV64_SMALLhigh=ibits(h,LIMB_BITS,LIMB_BITS)*FNV64_SMALL! The high limb's product is shifted back up, which drops the bits that! leave the top -- part of the same reduction modulo 2**64. `ishft` is! used rather than a multiply because the result may set bit 63, and! reaching that bit arithmetically would be signed overflow.state=u64_add(ishft(h,FNV64_SHIFT),&u64_add(low,ishft(iand(high,LIMB_MASK),LIMB_BITS)))end subroutine fnv1a_byte64