Hash.h 4.19 KB
Newer Older
Kenneth Moreland's avatar
Kenneth Moreland committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 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 80 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
//============================================================================
//  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.
//
//  Copyright 2017 Sandia Corporation.
//  Copyright 2017 UT-Battelle, LLC.
//  Copyright 2017 Los Alamos National Security.
//
//  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
//  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
{

static const vtkm::HashType FNV1A_OFFSET = 2166136261;
static const vtkm::HashType FNV1A_PRIME = 16777619;

/// \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).
template <typename NumericTag, vtkm::Id DataSize>
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