Warning, /include/opencascade/Standard_HashUtils.lxx is written in an unsupported language. File is not indexed.
0001 // Copyright (c) 2023 OPEN CASCADE SAS
0002 //
0003 // This file is part of Open CASCADE Technology software library.
0004 //
0005 // This library is free software; you can redistribute it and/or modify it under
0006 // the terms of the GNU Lesser General Public License version 2.1 as published
0007 // by the Free Software Foundation, with special exception defined in the file
0008 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
0009 // distribution for complete text of the license and disclaimer of any warranty.
0010 //
0011 // Alternatively, this file may be used under the terms of Open CASCADE
0012 // commercial license or contractual agreement.
0013
0014 #include <cstring>
0015
0016 namespace opencascade
0017 {
0018 namespace MurmurHash
0019 {
0020 namespace MurmurHashUtils
0021 {
0022 inline uint64_t shift_mix(uint64_t theV) noexcept
0023 {
0024 return theV ^ (theV >> 47);
0025 }
0026
0027 // Loads n bytes, where 1 <= n < 8
0028 inline uint64_t load_bytes(const char* thePnt, int theNb) noexcept
0029 {
0030 // Initialize result value
0031 uint64_t aResult = 0;
0032
0033 // Use switch with fall-through for better performance and branch prediction
0034 switch (theNb)
0035 {
0036 case 7:
0037 aResult = (static_cast<uint64_t>(static_cast<unsigned char>(thePnt[6])) << 48) | aResult;
0038 [[fallthrough]];
0039 case 6:
0040 aResult = (static_cast<uint64_t>(static_cast<unsigned char>(thePnt[5])) << 40) | aResult;
0041 [[fallthrough]];
0042 case 5:
0043 aResult = (static_cast<uint64_t>(static_cast<unsigned char>(thePnt[4])) << 32) | aResult;
0044 [[fallthrough]];
0045 case 4:
0046 aResult = (static_cast<uint64_t>(static_cast<unsigned char>(thePnt[3])) << 24) | aResult;
0047 [[fallthrough]];
0048 case 3:
0049 aResult = (static_cast<uint64_t>(static_cast<unsigned char>(thePnt[2])) << 16) | aResult;
0050 [[fallthrough]];
0051 case 2:
0052 aResult = (static_cast<uint64_t>(static_cast<unsigned char>(thePnt[1])) << 8) | aResult;
0053 [[fallthrough]];
0054 case 1:
0055 aResult = static_cast<uint64_t>(static_cast<unsigned char>(thePnt[0])) | aResult;
0056 [[fallthrough]];
0057 default:
0058 break;
0059 }
0060
0061 return aResult;
0062 }
0063
0064 template <typename T>
0065 inline T unaligned_load(const char* thePnt) noexcept
0066 {
0067 T aRes;
0068 memcpy(&aRes, thePnt, sizeof(aRes));
0069 return aRes;
0070 }
0071 } // namespace MurmurHashUtils
0072
0073 //=================================================================================================
0074
0075 inline uint64_t MurmurHash64A(const void* theKey, int theLen, uint64_t theSeed) noexcept
0076 {
0077 static constexpr uint64_t aMul = (((uint64_t)0xc6a4a793UL) << 32UL) + (uint64_t)0x5bd1e995UL;
0078 const char* const aBuf = static_cast<const char*>(theKey);
0079
0080 // Remove the bytes not divisible by the sizeof(uint64_t). This
0081 // allows the main loop to process the data as 64-bit integers.
0082 const uint64_t aLenAligned = theLen & ~(uint64_t)0x7;
0083 const char* const anEnd = aBuf + aLenAligned;
0084 uint64_t aHash = theSeed ^ (theLen * aMul);
0085 for (const char* aPnt = aBuf; aPnt != anEnd; aPnt += 8)
0086 {
0087 const uint64_t aData =
0088 MurmurHashUtils::shift_mix(MurmurHashUtils::unaligned_load<uint64_t>(aPnt) * aMul) * aMul;
0089 aHash ^= aData;
0090 aHash *= aMul;
0091 }
0092 if ((theLen & 0x7) != 0)
0093 {
0094 const uint64_t data = MurmurHashUtils::load_bytes(anEnd, theLen & 0x7);
0095 aHash ^= data;
0096 aHash *= aMul;
0097 }
0098 aHash = MurmurHashUtils::shift_mix(aHash) * aMul;
0099 aHash = MurmurHashUtils::shift_mix(aHash);
0100 return aHash;
0101 }
0102
0103 //=================================================================================================
0104
0105 inline uint32_t MurmurHash2A(const void* theKey, int theLen, uint32_t theSeed) noexcept
0106 {
0107 constexpr uint32_t aMul = 0x5bd1e995;
0108 uint32_t aHash = theSeed ^ theLen;
0109 const char* aBuf = static_cast<const char*>(theKey);
0110
0111 // Mix 4 bytes at a time into the hash.
0112 while (theLen >= 4)
0113 {
0114 uint32_t aKey = MurmurHashUtils::unaligned_load<uint32_t>(aBuf);
0115 aKey *= aMul;
0116 aKey ^= aKey >> 24;
0117 aKey *= aMul;
0118 aHash *= aMul;
0119 aHash ^= aKey;
0120 aBuf += 4;
0121 theLen -= 4;
0122 }
0123
0124 uint32_t aKey;
0125 // Handle the last few bytes of the input array.
0126 switch (theLen)
0127 {
0128 case 3:
0129 aKey = static_cast<unsigned char>(aBuf[2]);
0130 aHash ^= aKey << 16;
0131 [[fallthrough]];
0132 case 2:
0133 aKey = static_cast<unsigned char>(aBuf[1]);
0134 aHash ^= aKey << 8;
0135 [[fallthrough]];
0136 case 1:
0137 aKey = static_cast<unsigned char>(aBuf[0]);
0138 aHash ^= aKey;
0139 aHash *= aMul;
0140 };
0141
0142 // Do a few final mixes of the hash.
0143 aHash ^= aHash >> 13;
0144 aHash *= aMul;
0145 aHash ^= aHash >> 15;
0146 return aHash;
0147 }
0148 } // namespace MurmurHash
0149
0150 namespace FNVHash
0151 {
0152 //=================================================================================================
0153
0154 inline uint32_t FNVHash1A(const void* theKey, int theLen, uint32_t theSeed) noexcept
0155 {
0156 const char* cptr = static_cast<const char*>(theKey);
0157 for (; theLen; --theLen)
0158 {
0159 theSeed ^= static_cast<uint32_t>(*cptr++);
0160 theSeed *= static_cast<uint32_t>(16777619UL);
0161 }
0162 return theSeed;
0163 }
0164
0165 //=================================================================================================
0166
0167 inline uint64_t FNVHash64A(const void* theKey, int theLen, uint64_t theSeed) noexcept
0168 {
0169 const char* cptr = static_cast<const char*>(theKey);
0170 for (; theLen; --theLen)
0171 {
0172 theSeed ^= static_cast<uint64_t>(*cptr++);
0173 theSeed *= static_cast<uint64_t>(1099511628211ULL);
0174 }
0175 return theSeed;
0176 }
0177 } // namespace FNVHash
0178 } // namespace opencascade
