javascript - 将 HashString 从 C 转换为 JS

Question

我正在尝试从 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

Answer 1

让我们先实现一个更精简的 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“unsigned cast”)。<
• 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);

可能不是最有效的实现方式，但至少它是有效的 ;)