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

Source
#include "common/hash.h"
#include "common/endian.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;
}

inline uint64_t read(WasmEdge::Span<const std::byte, 8> Data) noexcept {
  uint64_t V;
  std::memcpy(&V, Data.data(), 8);
  if constexpr (WasmEdge::Endian::native == WasmEdge::Endian::little) {
    return V;
  } else {
    return WasmEdge::byteswap(V);
  }
}
inline uint64_t read(WasmEdge::Span<const std::byte, 4> Data) noexcept {
  uint32_t V;
  std::memcpy(&V, Data.data(), 4);
  if constexpr (WasmEdge::Endian::native == WasmEdge::Endian::little) {
    return V;
  } else {
    return WasmEdge::byteswap(V);
  }
}

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-12-14 06:36

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