/src/WasmEdge/lib/common/hash.cpp

Source (jump to first uncovered line)
#include "common/hash.h"

namespace {

inline uint64_t mulMod(uint64_t A, uint64_t B, uint64_t M) noexcept {
  uint64_t R = 0;
  while (B) {
    if (B & 1) {
      uint64_t R2 = R + A;
      if (R2 < R) {
        R2 -= M;
      }
      R = R2 % M;
    }
    B >>= 1;
    if (B) {
      uint64_t A2 = A + A;
      if (A2 < A) {
        A2 -= M;
      }
      A = A2 % M;
    }
  }
  return R;
}

inline uint64_t powMod(uint64_t A, uint64_t B, uint64_t M) noexcept {
  uint64_t R = 1;
  while (B) {
    if (B & 1) {
      R = mulMod(R, A, M);
    }
    B >>= 1;
    if (B) {
      A = mulMod(A, A, M);
    }
  }
  return R;
}

inline bool sprp(uint64_t N, uint64_t A) noexcept {
  uint64_t D = N - 1;
  uint8_t S = 0;
  while (!(D & 0xff)) {
    D >>= 8;
    S += 8;
  }
  if (!(D & 0xf)) {
    D >>= 4;
    S += 4;
  }
  if (!(D & 0x3)) {
    D >>= 2;
    S += 2;
  }
  if (!(D & 0x1)) {
    D >>= 1;
    S += 1;
  }
  uint64_t B = powMod(A, D, N);
  if ((B == 1) || (B == (N - 1))) {
    return true;
  }
  uint8_t R;
  for (R = 1; R < S; R++) {
    B = mulMod(B, B, N);
    if (B <= 1) {
      return false;
    }
    if (B == (N - 1)) {
      return true;
    }
  }
  return false;
}

inline bool isPrime(uint64_t N) noexcept {
  if (N < 2 || !(N & 1)) {
    return false;
  }
  if (N < 4) {
    return true;
  }
  if (!sprp(N, 2)) {
    return false;
  }
  if (N < 2047) {
    return true;
  }
  if (!sprp(N, 3)) {
    return false;
  }
  if (!sprp(N, 5)) {
    return false;
  }
  if (!sprp(N, 7)) {
    return false;
  }
  if (!sprp(N, 11)) {
    return false;
  }
  if (!sprp(N, 13)) {
    return false;
  }
  if (!sprp(N, 17)) {
    return false;
  }
  if (!sprp(N, 19)) {
    return false;
  }
  if (!sprp(N, 23)) {
    return false;
  }
  if (!sprp(N, 29)) {
    return false;
  }
  if (!sprp(N, 31)) {
    return false;
  }
  if (!sprp(N, 37)) {
    return false;
  }
  return true;
}

inline int popcount(uint64_t X) noexcept {
#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
  return __builtin_popcountll(X);
#elif defined(_MSC_VER) && defined(_WIN64)
#if defined(_M_X64)
  return static_cast<int>(_mm_popcnt_u64(X));
#else
  return static_cast<int>(_CountOneBits64(X));
#endif
#else
  X -= (X >> 1) & 0x5555555555555555;
  X = (X & 0x3333333333333333) + ((X >> 2) & 0x3333333333333333);
  X = (X + (X >> 4)) & 0x0f0f0f0f0f0f0f0f;
  X = (X * 0x0101010101010101) >> 56;
  return static_cast<int>(X);
#endif
}

std::array<uint64_t, 4> generate() noexcept {
  std::array<uint64_t, 4> Secret;
  const std::array<uint8_t, 70> C = {
      0x0f, 0x17, 0x1b, 0x1d, 0x1e, 0x27, 0x2b, 0x2d, 0x2e, 0x33, 0x35, 0x36,
      0x39, 0x3a, 0x3c, 0x47, 0x4b, 0x4d, 0x4e, 0x53, 0x55, 0x56, 0x59, 0x5a,
      0x5c, 0x63, 0x65, 0x66, 0x69, 0x6a, 0x6c, 0x71, 0x72, 0x74, 0x78, 0x87,
      0x8b, 0x8d, 0x8e, 0x93, 0x95, 0x96, 0x99, 0x9a, 0x9c, 0xa3, 0xa5, 0xa6,
      0xa9, 0xaa, 0xac, 0xb1, 0xb2, 0xb4, 0xb8, 0xc3, 0xc5, 0xc6, 0xc9, 0xca,
      0xcc, 0xd1, 0xd2, 0xd4, 0xd8, 0xe1, 0xe2, 0xe4, 0xe8, 0xf0};
  std::uniform_int_distribution<uint64_t> Dist(
      UINT64_C(0), static_cast<uint64_t>(C.size() - 1));
  for (size_t I = 0; I < 4; I++) {
    bool Ok;
    do {
      Ok = true;
      Secret[I] = 0;
      for (size_t J = 0; J < 64; J += 8) {
        Secret[I] |= static_cast<uint64_t>(C[Dist(WasmEdge::Hash::RandEngine)])
                     << J;
      }
      if (Secret[I] % 2 == 0) {
        Ok = false;
        continue;
      }
      for (size_t J = 0; J < I; J++) {
        if (popcount(Secret[J] ^ Secret[I]) != 32) {
          Ok = false;
          break;
        }
      }
      if (Ok && !isPrime(Secret[I]))
        Ok = false;
    } while (!Ok);
  }
  return Secret;
}

#if WASMEDGE_ENDIAN_LITTLE_BYTE
inline uint64_t read(WasmEdge::Span<const std::byte, 8> Data) noexcept {
  uint64_t V;
  std::memcpy(&V, Data.data(), 8);
  return V;
}
inline uint64_t read(WasmEdge::Span<const std::byte, 4> Data) noexcept {
  uint32_t V;
  std::memcpy(&V, Data.data(), 4);
  return V;
}
#else
inline constexpr uint64_t bswap64(uint64_t V) noexcept {
#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
  return __builtin_bswap64(V);
#elif defined(_MSC_VER)
  return _byteswap_uint64(V);
#else
  return (((V >> 56) & 0xff) | ((V >> 40) & 0xff00) | ((V >> 24) & 0xff0000) |
          ((V >> 8) & 0xff000000) | ((V << 8) & 0xff00000000) |
          ((V << 24) & 0xff0000000000) | ((V << 40) & 0xff000000000000) |
          ((V << 56) & 0xff00000000000000));
#endif
}
inline constexpr uint32_t bswap32(uint32_t V) noexcept {
#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
  return __builtin_bswap32(V);
#elif defined(_MSC_VER)
  return _byteswap_ulong(V);
#else
  return (((V >> 24) & 0xff) | ((V >> 8) & 0xff00) | ((V << 8) & 0xff0000) |
          ((V << 24) & 0xff000000));
#endif
}
inline uint64_t read(WasmEdge::Span<const std::byte, 8> Data) noexcept {
  uint64_t V;
  std::memcpy(&V, Data.data(), 8);
  return bswap64(V);
}
inline uint64_t read(WasmEdge::Span<const std::byte, 4> Data) noexcept {
  uint32_t V;
  std::memcpy(&V, Data.data(), 4);
  return bswap32(V);
}
#endif

inline uint64_t read_small(WasmEdge::Span<const std::byte> Data) noexcept {
  return (static_cast<uint64_t>(Data[0]) << 56) |
         (static_cast<uint64_t>(Data[Data.size() >> 1]) << 32) |
         static_cast<uint64_t>(Data[Data.size() - 1]);
}

static const std::array<uint64_t, 4> Secret = generate();

} // namespace

namespace WasmEdge::Hash {

WASMEDGE_EXPORT uint64_t Hash::rapidHash(Span<const std::byte> Data) noexcept {
  const auto Size = Data.size();
  uint64_t Seed = Secret[3];
  Seed ^= rapidMix(Seed ^ Secret[0], Secret[1]) ^ Size;
  uint64_t A, B;
  if (likely(Data.size() <= 16)) {
    if (likely(Data.size() >= 4)) {
      A = (read(Data.first<4>()) << 32) | read(Data.last<4>());
      const uint64_t delta = ((Data.size() & 24) >> (Data.size() >> 3));
      B = (read(Data.subspan(delta).first<4>()) << 32) |
          read(Data.last(4 + delta).first<4>());
    } else if (likely(Data.size() > 0)) {
      A = read_small(Data);
      B = 0;
    } else {
      A = B = 0;
    }
  } else {
    if (unlikely(Data.size() > 48)) {
      uint64_t See1 = Seed, See2 = Seed;
      while (likely(Data.size() >= 96)) {
        Seed = rapidMix(read(Data.first<8>()) ^ Secret[0],
                        read(Data.subspan<8>().first<8>()) ^ Seed);
        See1 = rapidMix(read(Data.subspan<16>().first<8>()) ^ Secret[1],
                        read(Data.subspan<24>().first<8>()) ^ See1);
        See2 = rapidMix(read(Data.subspan<32>().first<8>()) ^ Secret[2],
                        read(Data.subspan<40>().first<8>()) ^ See2);
        Seed = rapidMix(read(Data.subspan<48>().first<8>()) ^ Secret[0],
                        read(Data.subspan<56>().first<8>()) ^ Seed);
        See1 = rapidMix(read(Data.subspan<64>().first<8>()) ^ Secret[1],
                        read(Data.subspan<72>().first<8>()) ^ See1);
        See2 = rapidMix(read(Data.subspan<80>().first<8>()) ^ Secret[2],
                        read(Data.subspan<88>().first<8>()) ^ See2);
        Data = Data.subspan<96>();
      }
      if (unlikely(Data.size() >= 48)) {
        Seed = rapidMix(read(Data.first<8>()) ^ Secret[0],
                        read(Data.subspan<8>().first<8>()) ^ Seed);
        See1 = rapidMix(read(Data.subspan<16>().first<8>()) ^ Secret[1],
                        read(Data.subspan<24>().first<8>()) ^ See1);
        See2 = rapidMix(read(Data.subspan<32>().first<8>()) ^ Secret[2],
                        read(Data.subspan<40>().first<8>()) ^ See2);
        Data = Data.subspan<48>();
      }

      Seed ^= See1 ^ See2;
    }
    if (Data.size() > 16) {
      Seed = rapidMix(read(Data.first<8>()) ^ Secret[2],
                      read(Data.subspan<8>().first<8>()) ^ Seed ^ Secret[1]);
      if (Data.size() > 32)
        Seed = rapidMix(read(Data.subspan<16>().first<8>()) ^ Secret[2],
                        read(Data.subspan<24>().first<8>()) ^ Seed);
    }
    A = read(Data.last<16>().first<8>());
    B = read(Data.last<8>());
  }
  A ^= Secret[1];
  B ^= Seed;
  rapidMum(A, B);
  return rapidMix(A ^ Secret[0] ^ Size, B ^ Secret[1]);
}

} // namespace WasmEdge::Hash

Coverage Report

Created: 2025-07-01 06:18

Line	Count	Source (jump to first uncovered line)
1		#include "common/hash.h"
2
3		namespace {
4
5	33.1k	inline uint64_t mulMod(uint64_t A, uint64_t B, uint64_t M) noexcept {
6	33.1k	uint64_t R = 0;
7	1.93M	while (B) {
8	1.90M	if (B & 1) {
9	952k	uint64_t R2 = R + A;
10	952k	if (R2 < R) {
11	108k	R2 -= M;
12	108k	}
13	952k	R = R2 % M;
14	952k	}
15	1.90M	B >>= 1;
16	1.90M	if (B) {
17	1.87M	uint64_t A2 = A + A;
18	1.87M	if (A2 < A) {
19	326k	A2 -= M;
20	326k	}
21	1.87M	A = A2 % M;
22	1.87M	}
23	1.90M	}
24	33.1k	return R;
25	33.1k	}
26
27	359	inline uint64_t powMod(uint64_t A, uint64_t B, uint64_t M) noexcept {
28	359	uint64_t R = 1;
29	22.4k	while (B) {
30	22.0k	if (B & 1) {
31	11.1k	R = mulMod(R, A, M);
32	11.1k	}
33	22.0k	B >>= 1;
34	22.0k	if (B) {
35	21.6k	A = mulMod(A, A, M);
36	21.6k	}
37	22.0k	}
38	359	return R;
39	359	}
40
41	359	inline bool sprp(uint64_t N, uint64_t A) noexcept {
42	359	uint64_t D = N - 1;
43	359	uint8_t S = 0;
44	359	while (!(D & 0xff)) {
45	0	D >>= 8;
46	0	S += 8;
47	0	}
48	359	if (!(D & 0xf)) {
49	45	D >>= 4;
50	45	S += 4;
51	45	}
52	359	if (!(D & 0x3)) {
53	154	D >>= 2;
54	154	S += 2;
55	154	}
56	359	if (!(D & 0x1)) {
57	232	D >>= 1;
58	232	S += 1;
59	232	}
60	359	uint64_t B = powMod(A, D, N);
61	359	if ((B == 1) \|\| (B == (N - 1))) {
62	88	return true;
63	88	}
64	271	uint8_t R;
65	504	for (R = 1; R < S; R++) {
66	289	B = mulMod(B, B, N);
67	289	if (B <= 1) {
68	0	return false;
69	0	}
70	289	if (B == (N - 1)) {
71	56	return true;
72	56	}
73	289	}
74	215	return false;
75	271	}
76
77	227	inline bool isPrime(uint64_t N) noexcept {
78	227	if (N < 2 \|\| !(N & 1)) {
79	0	return false;
80	0	}
81	227	if (N < 4) {
82	0	return true;
83	0	}
84	227	if (!sprp(N, 2)) {
85	215	return false;
86	215	}
87	12	if (N < 2047) {
88	0	return true;
89	0	}
90	12	if (!sprp(N, 3)) {
91	0	return false;
92	0	}
93	12	if (!sprp(N, 5)) {
94	0	return false;
95	0	}
96	12	if (!sprp(N, 7)) {
97	0	return false;
98	0	}
99	12	if (!sprp(N, 11)) {
100	0	return false;
101	0	}
102	12	if (!sprp(N, 13)) {
103	0	return false;
104	0	}
105	12	if (!sprp(N, 17)) {
106	0	return false;
107	0	}
108	12	if (!sprp(N, 19)) {
109	0	return false;
110	0	}
111	12	if (!sprp(N, 23)) {
112	0	return false;
113	0	}
114	12	if (!sprp(N, 29)) {
115	0	return false;
116	0	}
117	12	if (!sprp(N, 31)) {
118	0	return false;
119	0	}
120	12	if (!sprp(N, 37)) {
121	0	return false;
122	0	}
123	12	return true;
124	12	}
125
126	10.8k	inline int popcount(uint64_t X) noexcept {
127	10.8k	#if defined(__GNUC__) \|\| defined(__INTEL_COMPILER) \|\| defined(__clang__)
128	10.8k	return __builtin_popcountll(X);
129		#elif defined(_MSC_VER) && defined(_WIN64)
130		#if defined(_M_X64)
131		return static_cast<int>(_mm_popcnt_u64(X));
132		#else
133		return static_cast<int>(_CountOneBits64(X));
134		#endif
135		#else
136		X -= (X >> 1) & 0x5555555555555555;
137		X = (X & 0x3333333333333333) + ((X >> 2) & 0x3333333333333333);
138		X = (X + (X >> 4)) & 0x0f0f0f0f0f0f0f0f;
139		X = (X * 0x0101010101010101) >> 56;
140		return static_cast<int>(X);
141		#endif
142	10.8k	}
143
144	3	std::array<uint64_t, 4> generate() noexcept {
145	3	std::array<uint64_t, 4> Secret;
146	3	const std::array<uint8_t, 70> C = {
147	3	0x0f, 0x17, 0x1b, 0x1d, 0x1e, 0x27, 0x2b, 0x2d, 0x2e, 0x33, 0x35, 0x36,
148	3	0x39, 0x3a, 0x3c, 0x47, 0x4b, 0x4d, 0x4e, 0x53, 0x55, 0x56, 0x59, 0x5a,
149	3	0x5c, 0x63, 0x65, 0x66, 0x69, 0x6a, 0x6c, 0x71, 0x72, 0x74, 0x78, 0x87,
150	3	0x8b, 0x8d, 0x8e, 0x93, 0x95, 0x96, 0x99, 0x9a, 0x9c, 0xa3, 0xa5, 0xa6,
151	3	0xa9, 0xaa, 0xac, 0xb1, 0xb2, 0xb4, 0xb8, 0xc3, 0xc5, 0xc6, 0xc9, 0xca,
152	3	0xcc, 0xd1, 0xd2, 0xd4, 0xd8, 0xe1, 0xe2, 0xe4, 0xe8, 0xf0};
153	3	std::uniform_int_distribution<uint64_t> Dist(
154	3	UINT64_C(0), static_cast<uint64_t>(C.size() - 1));
155	15	for (size_t I = 0; I < 4; I++) {
156	12	bool Ok;
157	17.8k	do {
158	17.8k	Ok = true;
159	17.8k	Secret[I] = 0;
160	160k	for (size_t J = 0; J < 64; J += 8) {
161	142k	Secret[I] \|= static_cast<uint64_t>(C[Dist(WasmEdge::Hash::RandEngine)])
162	142k	<< J;
163	142k	}
164	17.8k	if (Secret[I] % 2 == 0) {
165	8.77k	Ok = false;
166	8.77k	continue;
167	8.77k	}
168	11.0k	for (size_t J = 0; J < I; J++) {
169	10.8k	if (popcount(Secret[J] ^ Secret[I]) != 32) {
170	8.82k	Ok = false;
171	8.82k	break;
172	8.82k	}
173	10.8k	}
174	9.05k	if (Ok && !isPrime(Secret[I]))
175	215	Ok = false;
176	17.8k	} while (!Ok);
177	12	}
178	3	return Secret;
179	3	}
180
181		#if WASMEDGE_ENDIAN_LITTLE_BYTE
182	20.5k	inline uint64_t read(WasmEdge::Span<const std::byte, 8> Data) noexcept {
183	20.5k	uint64_t V;
184	20.5k	std::memcpy(&V, Data.data(), 8);
185	20.5k	return V;
186	20.5k	}
187	29.5k	inline uint64_t read(WasmEdge::Span<const std::byte, 4> Data) noexcept {
188	29.5k	uint32_t V;
189	29.5k	std::memcpy(&V, Data.data(), 4);
190	29.5k	return V;
191	29.5k	}
192		#else
193		inline constexpr uint64_t bswap64(uint64_t V) noexcept {
194		#if defined(__GNUC__) \|\| defined(__INTEL_COMPILER) \|\| defined(__clang__)
195		return __builtin_bswap64(V);
196		#elif defined(_MSC_VER)
197		return _byteswap_uint64(V);
198		#else
199		return (((V >> 56) & 0xff) \| ((V >> 40) & 0xff00) \| ((V >> 24) & 0xff0000) \|
200		((V >> 8) & 0xff000000) \| ((V << 8) & 0xff00000000) \|
201		((V << 24) & 0xff0000000000) \| ((V << 40) & 0xff000000000000) \|
202		((V << 56) & 0xff00000000000000));
203		#endif
204		}
205		inline constexpr uint32_t bswap32(uint32_t V) noexcept {
206		#if defined(__GNUC__) \|\| defined(__INTEL_COMPILER) \|\| defined(__clang__)
207		return __builtin_bswap32(V);
208		#elif defined(_MSC_VER)
209		return _byteswap_ulong(V);
210		#else
211		return (((V >> 24) & 0xff) \| ((V >> 8) & 0xff00) \| ((V << 8) & 0xff0000) \|
212		((V << 24) & 0xff000000));
213		#endif
214		}
215		inline uint64_t read(WasmEdge::Span<const std::byte, 8> Data) noexcept {
216		uint64_t V;
217		std::memcpy(&V, Data.data(), 8);
218		return bswap64(V);
219		}
220		inline uint64_t read(WasmEdge::Span<const std::byte, 4> Data) noexcept {
221		uint32_t V;
222		std::memcpy(&V, Data.data(), 4);
223		return bswap32(V);
224		}
225		#endif
226
227	2.16k	inline uint64_t read_small(WasmEdge::Span<const std::byte> Data) noexcept {
228	2.16k	return (static_cast<uint64_t>(Data[0]) << 56) \|
229	2.16k	(static_cast<uint64_t>(Data[Data.size() >> 1]) << 32) \|
230	2.16k	static_cast<uint64_t>(Data[Data.size() - 1]);
231	2.16k	}
232
233		static const std::array<uint64_t, 4> Secret = generate();
234
235		} // namespace
236
237		namespace WasmEdge::Hash {
238
239	14.5k	WASMEDGE_EXPORT uint64_t Hash::rapidHash(Span<const std::byte> Data) noexcept {
240	14.5k	const auto Size = Data.size();
241	14.5k	uint64_t Seed = Secret[3];
242	14.5k	Seed ^= rapidMix(Seed ^ Secret[0], Secret[1]) ^ Size;
243	14.5k	uint64_t A, B;
244	14.5k	if (likely(Data.size() <= 16)) {
245	9.59k	if (likely(Data.size() >= 4)) {
246	7.38k	A = (read(Data.first<4>()) << 32) \| read(Data.last<4>());
247	7.38k	const uint64_t delta = ((Data.size() & 24) >> (Data.size() >> 3));
248	7.38k	B = (read(Data.subspan(delta).first<4>()) << 32) \|
249	7.38k	read(Data.last(4 + delta).first<4>());
250	7.38k	} else if (likely(Data.size() > 0)) {
251	2.16k	A = read_small(Data);
252	2.16k	B = 0;
253	2.16k	} else {
254	46	A = B = 0;
255	46	}
256	9.59k	} else {
257	4.91k	if (unlikely(Data.size() > 48)) {
258	19	uint64_t See1 = Seed, See2 = Seed;
259	42	while (likely(Data.size() >= 96)) {
260	23	Seed = rapidMix(read(Data.first<8>()) ^ Secret[0],
261	23	read(Data.subspan<8>().first<8>()) ^ Seed);
262	23	See1 = rapidMix(read(Data.subspan<16>().first<8>()) ^ Secret[1],
263	23	read(Data.subspan<24>().first<8>()) ^ See1);
264	23	See2 = rapidMix(read(Data.subspan<32>().first<8>()) ^ Secret[2],
265	23	read(Data.subspan<40>().first<8>()) ^ See2);
266	23	Seed = rapidMix(read(Data.subspan<48>().first<8>()) ^ Secret[0],
267	23	read(Data.subspan<56>().first<8>()) ^ Seed);
268	23	See1 = rapidMix(read(Data.subspan<64>().first<8>()) ^ Secret[1],
269	23	read(Data.subspan<72>().first<8>()) ^ See1);
270	23	See2 = rapidMix(read(Data.subspan<80>().first<8>()) ^ Secret[2],
271	23	read(Data.subspan<88>().first<8>()) ^ See2);
272	23	Data = Data.subspan<96>();
273	23	}
274	19	if (unlikely(Data.size() >= 48)) {
275	18	Seed = rapidMix(read(Data.first<8>()) ^ Secret[0],
276	18	read(Data.subspan<8>().first<8>()) ^ Seed);
277	18	See1 = rapidMix(read(Data.subspan<16>().first<8>()) ^ Secret[1],
278	18	read(Data.subspan<24>().first<8>()) ^ See1);
279	18	See2 = rapidMix(read(Data.subspan<32>().first<8>()) ^ Secret[2],
280	18	read(Data.subspan<40>().first<8>()) ^ See2);
281	18	Data = Data.subspan<48>();
282	18	}
283
284	19	Seed ^= See1 ^ See2;
285	19	}
286	4.91k	if (Data.size() > 16) {
287	4.89k	Seed = rapidMix(read(Data.first<8>()) ^ Secret[2],
288	4.89k	read(Data.subspan<8>().first<8>()) ^ Seed ^ Secret[1]);
289	4.89k	if (Data.size() > 32)
290	250	Seed = rapidMix(read(Data.subspan<16>().first<8>()) ^ Secret[2],
291	250	read(Data.subspan<24>().first<8>()) ^ Seed);
292	4.89k	}
293	4.91k	A = read(Data.last<16>().first<8>());
294	4.91k	B = read(Data.last<8>());
295	4.91k	}
296	14.5k	A ^= Secret[1];
297	14.5k	B ^= Seed;
298	14.5k	rapidMum(A, B);
299	14.5k	return rapidMix(A ^ Secret[0] ^ Size, B ^ Secret[1]);
300	14.5k	}
301
302		} // namespace WasmEdge::Hash