fnv_mul_prime Function

private pure function fnv_mul_prime(hash_code) result(new_hash)

Multiply a 32-bit FNV state by the FNV prime, modulo 2**32.

Writing hash_code*prime directly in integer(int32) overflows for very nearly every state – for a five-byte key, every single round overflows. Signed integer overflow is not defined by the Fortran standard and is trappable: -ftrapv, -fsanitize=signed-integer-overflow and Intel’s -check all abort on it. It only appears to work because most compilers choose to wrap. This function gets the same answer by construction.

  1. The product is formed in int64, where it cannot overflow: the state is at most 231 in magnitude and the prime is below 224, so the exact product stays below 2**55.
  2. iand with mask_32 reduces it modulo 232. iand is defined on the integer bit model, so a negative hash_code widened to int64 keeps its two’s-complement bit pattern and the mask yields its correct residue as a value in [0, 232 - 1].
  3. That residue cannot simply be assigned to int32: anything above huge(int32) is not representable and the conversion would itself be undefined. Subtracting 232 first – still in int64, where the result is exact and in range – maps [231, 232 - 1] onto [-231, -1], which is exactly the bit pattern a wrapping 32-bit multiply leaves behind. Only then is the value narrowed, from a range int32 can hold.

The result is therefore bit-identical to the old wrapping code on every two’s-complement machine, while being defined on every compiler.

Arguments

Type IntentOptional Attributes Name
integer(kind=int_hash), intent(in) :: hash_code

Return Value integer(kind=int_hash)


Called by

proc~~fnv_mul_prime~~CalledByGraph proc~fnv_mul_prime fnv_mul_prime proc~int8_fnv_1 int8_fnv_1 proc~int8_fnv_1->proc~fnv_mul_prime proc~int8_fnv_1a int8_fnv_1a proc~int8_fnv_1a->proc~fnv_mul_prime

Variables

Type Visibility Attributes Name Initial
integer(kind=int64), private :: acc

Source Code

   pure function fnv_mul_prime(hash_code) result(new_hash)
!! Multiply a 32-bit FNV state by the FNV prime, modulo 2**32.
!!
!! Writing `hash_code*prime` directly in `integer(int32)` overflows for very
!! nearly every state -- for a five-byte key, every single round overflows.
!! Signed integer overflow is not defined by the Fortran standard and is
!! trappable: `-ftrapv`, `-fsanitize=signed-integer-overflow` and Intel's
!! `-check` all abort on it. It only appears to work because most compilers
!! choose to wrap. This function gets the same answer by construction.
!!
!! 1. The product is formed in `int64`, where it cannot overflow: the state is
!!    at most 2**31 in magnitude and the prime is below 2**24, so the exact
!!    product stays below 2**55.
!! 2. `iand` with `mask_32` reduces it modulo 2**32. `iand` is defined on the
!!    integer bit model, so a negative `hash_code` widened to `int64` keeps
!!    its two's-complement bit pattern and the mask yields its correct
!!    residue as a value in [0, 2**32 - 1].
!! 3. That residue cannot simply be assigned to `int32`: anything above
!!    `huge(int32)` is not representable and the conversion would itself be
!!    undefined. Subtracting 2**32 first -- still in `int64`, where the result
!!    is exact and in range -- maps [2**31, 2**32 - 1] onto [-2**31, -1],
!!    which is exactly the bit pattern a wrapping 32-bit multiply leaves
!!    behind. Only then is the value narrowed, from a range `int32` can hold.
!!
!! The result is therefore bit-identical to the old wrapping code on every
!! two's-complement machine, while being defined on every compiler.
      integer(int_hash), intent(in) :: hash_code
      integer(int_hash)             :: new_hash

      integer(int64) :: acc

      acc = iand(int(hash_code, int64)*prime, mask_32)
      if (acc > int32_max) acc = acc - two_pow_32
      new_hash = int(acc, int_hash)

   end function fnv_mul_prime