Hash.h 4.23 KB
Newer Older
Kenneth Moreland's avatar
Kenneth Moreland committed
1 2 3 4 5 6 7 8
//============================================================================
//  Copyright (c) Kitware, Inc.
//  All rights reserved.
//  See LICENSE.txt for details.
//  This software is distributed WITHOUT ANY WARRANTY; without even
//  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
//  PURPOSE.  See the above copyright notice for more information.
//
9
//  Copyright 2017 National Technology & Engineering Solutions of Sandia, LLC (NTESS).
Kenneth Moreland's avatar
Kenneth Moreland committed
10 11 12
//  Copyright 2017 UT-Battelle, LLC.
//  Copyright 2017 Los Alamos National Security.
//
13
//  Under the terms of Contract DE-NA0003525 with NTESS,
Kenneth Moreland's avatar
Kenneth Moreland committed
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
//  the U.S. Government retains certain rights in this software.
//
//  Under the terms of Contract DE-AC52-06NA25396 with Los Alamos National
//  Laboratory (LANL), the U.S. Government retains certain rights in
//  this software.
//============================================================================
#ifndef vtk_m_Hash_h
#define vtk_m_Hash_h

#include <vtkm/TypeTraits.h>
#include <vtkm/Types.h>
#include <vtkm/VecTraits.h>

namespace vtkm
{

using HashType = vtkm::UInt32;

namespace detail
{

35 36
static constexpr vtkm::HashType FNV1A_OFFSET = 2166136261;
static constexpr vtkm::HashType FNV1A_PRIME = 16777619;
Kenneth Moreland's avatar
Kenneth Moreland committed
37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

/// \brief Performs an FNV-1a hash on 32-bit integers returning a 32-bit hash
///
template <typename InVecType>
VTKM_EXEC_CONT inline vtkm::HashType HashFNV1a32(const InVecType& inVec)
{
  using Traits = vtkm::VecTraits<InVecType>;
  const vtkm::IdComponent numComponents = Traits::GetNumberOfComponents(inVec);

  vtkm::HashType hash = FNV1A_OFFSET;
  for (vtkm::IdComponent index = 0; index < numComponents; index++)
  {
    vtkm::HashType dataBits = static_cast<vtkm::HashType>(Traits::GetComponent(inVec, index));
    hash = (hash * FNV1A_PRIME) ^ dataBits;
  }

  return hash;
}

/// \brief Performs an FNV-1a hash on 64-bit integers returning a 32-bit hash
///
template <typename InVecType>
VTKM_EXEC_CONT inline vtkm::HashType HashFNV1a64(const InVecType& inVec)
{
  using Traits = vtkm::VecTraits<InVecType>;
  const vtkm::IdComponent numComponents = Traits::GetNumberOfComponents(inVec);

  vtkm::HashType hash = FNV1A_OFFSET;
  for (vtkm::IdComponent index = 0; index < numComponents; index++)
  {
    vtkm::UInt64 allDataBits = static_cast<vtkm::UInt64>(Traits::GetComponent(inVec, index));
    vtkm::HashType upperDataBits =
      static_cast<vtkm::HashType>((allDataBits & 0xFFFFFFFF00000000L) >> 32);
    hash = (hash * FNV1A_PRIME) ^ upperDataBits;
    vtkm::HashType lowerDataBits = static_cast<vtkm::HashType>(allDataBits & 0x00000000FFFFFFFFL);
    hash = (hash * FNV1A_PRIME) ^ lowerDataBits;
  }

  return hash;
}

// If you get a compile error saying that there is no implementation of the class HashChooser,
// then you have tried to make a hash from an invalid type (like a float).
80
template <typename NumericTag, std::size_t DataSize>
Kenneth Moreland's avatar
Kenneth Moreland committed
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
struct HashChooser;

template <>
struct HashChooser<vtkm::TypeTraitsIntegerTag, 4>
{
  template <typename InVecType>
  VTKM_EXEC_CONT static vtkm::HashType Hash(const InVecType& inVec)
  {
    return vtkm::detail::HashFNV1a32(inVec);
  }
};

template <>
struct HashChooser<vtkm::TypeTraitsIntegerTag, 8>
{
  template <typename InVecType>
  VTKM_EXEC_CONT static vtkm::HashType Hash(const InVecType& inVec)
  {
    return vtkm::detail::HashFNV1a64(inVec);
  }
};

} // namespace detail

/// \brief Returns a 32-bit hash on a group of integer-type values.
///
/// The input to the hash is expected to be a vtkm::Vec or a Vec-like object. The values can be
/// either 32-bit integers or 64-bit integers (signed or unsigned). Regardless, the resulting hash
/// is an unsigned 32-bit integer.
///
/// The hash is designed to minimize the probability of collisions, but collisions are always
/// possible. Thus, when using these hashes there should be a contingency for dealing with
/// collisions.
///
template <typename InVecType>
VTKM_EXEC_CONT inline vtkm::HashType Hash(const InVecType& inVec)
{
  using VecTraits = vtkm::VecTraits<InVecType>;
  using ComponentType = typename VecTraits::ComponentType;
  using ComponentTraits = vtkm::TypeTraits<ComponentType>;
  using Chooser = detail::HashChooser<typename ComponentTraits::NumericTag, sizeof(ComponentType)>;
  return Chooser::Hash(inVec);
}

} // namespace vtkm

#endif //vtk_m_Hash_h