我正在尝试从 Mozilla Firefox 代码库转换此函数,它称为 HashString
。它调用了一系列函数,这些函数都在这个文件中:https://dxr.mozilla.org/mozilla-central/source/mfbt/HashFunctions.h#294
所以这些是它调用的 C 函数:
static const uint32_t kGoldenRatioU32 = 0x9E3779B9U;
MOZ_WARN_UNUSED_RESULT inline uint32_t
HashString(const wchar_t* aStr)
{
return detail::HashUntilZero(aStr);
}
template<typename T>
uint32_t
HashUntilZero(const T* aStr)
{
uint32_t hash = 0;
for (T c; (c = *aStr); aStr++) {
hash = AddToHash(hash, c);
}
return hash;
}
MOZ_WARN_UNUSED_RESULT inline uint32_t
AddToHash(uint32_t aHash, A* aA)
{
/*
* You might think this function should just take a void*. But then we'd only
* catch data pointers and couldn't handle function pointers.
*/
static_assert(sizeof(aA) == sizeof(uintptr_t), "Strange pointer!");
return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, uintptr_t(aA));
}
inline uint32_t
AddUintptrToHash<8>(uint32_t aHash, uintptr_t aValue)
{
/*
* The static cast to uint64_t below is necessary because this function
* sometimes gets compiled on 32-bit platforms (yes, even though it's a
* template and we never call this particular override in a 32-bit build). If
* we do aValue >> 32 on a 32-bit machine, we're shifting a 32-bit uintptr_t
* right 32 bits, and the compiler throws an error.
*/
uint32_t v1 = static_cast<uint32_t>(aValue);
uint32_t v2 = static_cast<uint32_t>(static_cast<uint64_t>(aValue) >> 32);
return AddU32ToHash(AddU32ToHash(aHash, v1), v2);
}
inline uint32_t
AddU32ToHash(uint32_t aHash, uint32_t aValue)
{
return kGoldenRatioU32 * (RotateBitsLeft32(aHash, 5) ^ aValue);
}
inline uint32_t
RotateBitsLeft32(uint32_t aValue, uint8_t aBits)
{
MOZ_ASSERT(aBits < 32);
return (aValue << aBits) | (aValue >> (32 - aBits));
}
这是我的 js 代码:
function HashString(aStr, aLength) {
// moz win32 hash function
if (aLength) {
console.error('NS_ERROR_NOT_IMPLEMENTED');
throw Components.results.NS_ERROR_NOT_IMPLEMENTED;
} else {
return HashUntilZero(aStr);
}
}
function HashUntilZero(aStr) {
var hash = 0;
//for (T c; (c = *aStr); aStr++) {
for (var c=0; c<aStr.length; c++) {
hash = AddToHash(hash, aStr.charCodeAt(c));
}
return hash;
}
function AddToHash(aHash, aA) {
//return detail::AddU32ToHash(aHash, aA);
//return AddU32ToHash(aHash, aA);
//return detail::AddUintptrToHash<sizeof(uintptr_t)>(aHash, aA);
return AddUintptrToHash(aHash, aA);
}
function AddUintptrToHash(aHash, aValue) {
//return AddU32ToHash(aHash, static_cast<uint32_t>(aValue));
return AddU32ToHash(aHash, aValue);
}
function AddU32ToHash(aHash, aValue) {
var kGoldenRatioU32 = 0x9E3779B9;
return (kGoldenRatioU32 * (RotateBitsLeft32(aHash, 5) ^ aValue));
}
function RotateBitsLeft32(aValue, aBits) {
// MOZ_ASSERT(aBits < 32);
return (aValue << aBits) | (aValue >> (32 - aBits));
}
console.log(HashString('C:\Users\Vayeate\AppData\Roaming\Mozilla\Firefox\Profiles\aksozfjt.Unnamed Profile 10')); // should return 3181739213
这不起作用,执行 HashString('C:\Users\Vayeate\AppData\Roaming\Mozilla\Firefox\Profiles\aksozfjt.Unnamed Profile 10')
应该返回给我3181739213
但事实并非如此。它不断返回给我:-159266146140
最佳答案
让我们首先实现一个更简单的 C++ 版本,它还会转储中间值,以便我们稍后进行比较。
#include <iostream>
#include <iomanip>
#include <stdint.h>
using namespace std;
static const uint32_t gr = 0x9E3779B9U;
template<typename T>
static uint32_t add(uint32_t hash, T val) {
const uint32_t rv = gr * (((hash << 5) | (hash >> 27)) ^ val);
cerr << dec << setw(7) << (uint32_t)val << " " << setw(14) << rv << " " << hex << rv << endl;
return rv;
}
int main() {
const auto text = string("C:\\Users\\Vayeate\\AppData\\Roaming\\Mozilla\\Firefox\\Profiles\\aksozfjt.Unnamed Profile 10");
uint32_t rv = 0;
for (auto c: text) {
rv = add(rv, c);
}
cout << "Result: " << dec << setw(14) << rv << " " << hex << rv << endl;
}
结果:3181739213 bda57ccd
,所以我们走在正确的轨道上。
现在,来看一些 Javascript:
GetNativePath
返回一个nsAutoCString
又名。 8位字符串,通过将内部16位字符串转换为UTF-8。- Javascript实际上并不知道32位无符号整数,只知道32位有符号整数,但是有一些肮脏的技巧(主要是
>>> 0
“无符号转换”)。< - 32 位无符号乘法不起作用,但我们实际上可以自己实现该运算。
- 正确转义测试字符串中的反斜杠
\
也有帮助;)
将这些东西放在一起,我得到了以下函数,它似乎产生了正确的结果。
/**
* Javascript implementation of
* https://hg.mozilla.org/mozilla-central/file/0cefb584fd1a/mfbt/HashFunctions.h
* aka. the mfbt hash function.
*/
let HashString = (function() {
// Note: >>>0 is basically a cast-to-unsigned for our purposes.
const encoder = new TextEncoder("utf-8");
const kGoldenRatio = 0x9E3779B9;
// Multiply two uint32_t like C++ would ;)
const mul32 = (a, b) => {
// Split into 16-bit integers (hi and lo words)
let ahi = (a >> 16) & 0xffff;
let alo = a & 0xffff;
let bhi = (b >> 16) & 0xffff
let blo = b & 0xffff;
// Compute new hi and lo seperately and recombine.
return (
(((((ahi * blo) + (alo * bhi)) & 0xffff) << 16) >>> 0) +
(alo * blo)
) >>> 0;
};
// kGoldenRatioU32 * (RotateBitsLeft32(aHash, 5) ^ aValue);
const add = (hash, val) => {
// Note, cannot >> 27 here, but / (1<<27) works as well.
let rotl5 = (
((hash << 5) >>> 0) |
(hash / (1<<27)) >>> 0
) >>> 0;
return mul32(kGoldenRatio, (rotl5 ^ val) >>> 0);
}
return function(text) {
// Convert to utf-8.
// Also decomposes the string into uint8_t values already.
let data = encoder.encode(text);
// Compute the actual hash
let rv = 0;
for (let c of data) {
rv = add(rv, c | 0);
}
return rv;
};
})();
let res = HashString('C:\\Users\\Vayeate\\AppData\\Roaming\\Mozilla\\Firefox\\Profiles\\aksozfjt.Unnamed Profile 10');
console.log(res, res === 3181739213);
可能不是最有效的实现,但至少它有效;)
关于javascript - 将 HashString 从 C 转换为 JS,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28653641/