与 Intel 的 SSE4.2 硬件实现兼容的 Javascript CRC32C 实现

Question

在开始之前，有一个免责声明:虽然我可以使用 C/C++ 代码，但我不是巫师，我也没有做过足够的编程来称自己是一个有能力的程序员。

我正在尝试使用 CRC32C 来验证从浏览器进入我们服务器的数据。目前，两种实现都使用相同的代码(服务器上的nodeJS)，但我们想切换到硬件实现( blog post ， github repo )(如果可用)，为此我需要在浏览器中提供正确运行的版本。

我尝试使用this implementation (另一个，内部开发，但也不起作用)但使用正确的多项式(0x82F63B78而不是0xEDB88320，以及0x1EDC6F41和0x8F6E37A0)，但我使用的多项式都不能产生正确的输出。

继续我的研究，我发现了来自 Mark Adler 的帖子其中包括一个软件实现，并决定尝试将其转换为 Javascript(以我对 C 的最佳理解)。

结果:

function crc32c_table_intel() {
var POLY = 0x82f63b78;
var n, crc, k;
var crc32c_table = gen2darr(8, 256, 0);

for (n = 0; n < 256; n++) {
    crc = n;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    crc32c_table[0][n] = crc;
}
for (n = 0; n < 256; n++) {
    crc = crc32c_table[0][n];
    for (k = 1; k < 8; k++) {
        crc = crc32c_table[0][crc & 0xff] ^ (crc >> 8);
        crc32c_table[k][n] = crc;
      _crc_tmptable.push(crc32c_table[k][n]);
    }
}
return crc32c_table;
}


function crc32c_sw(crci, str) {
var len = str.length;
var crc;
var crc32c_table = crc32c_table_intel();

crc = crci ^ 0xffffffff;
for(var next = 0; next < 7; next++) { // was: while (len && ((uintptr_t)next & 7) != 0) {
    crc = crc32c_table[0][(crc ^ str.charCodeAt(next++)) & 0xff] ^ (crc >> 8);
    len--;
}
while (len >= 8) {
    // was: crc ^= *(uint64_t *)next;
    crc ^= str.charCodeAt(next);
    crc = crc32c_table[7][crc & 0xff] ^
          crc32c_table[6][(crc >> 8) & 0xff] ^
          crc32c_table[5][(crc >> 16) & 0xff] ^
          crc32c_table[4][(crc >> 24) & 0xff] ^
          crc32c_table[3][(crc >> 32) & 0xff] ^
          crc32c_table[2][(crc >> 40) & 0xff] ^
          crc32c_table[1][(crc >> 48) & 0xff] ^
          crc32c_table[0][crc >> 56];
    next += 1;
    len -= 1;
}
while (len) {
    // was: crc = crc32c_table[0][(crc ^ *next++) & 0xff] ^ (crc >> 8);
    crc = crc32c_table[0][(crc ^ str.charCodeAt(next++)) & 0xff] ^ (crc >> 8);
    len--;
}
return crc ^ 0xffffffff;
}


// a helper function
function gen2darr( rows, cols, defaultValue){
    var arr = [];
    for(var i=0; i < rows; i++){
            arr.push([]);
            arr[i].push( new Array(cols));
            for(var j=0; j < cols; j++){
                    arr[i][j] = defaultValue;
                    }
            }
    return arr;
}

不过，还是没有运气。无论我使用什么函数、什么表格或什么多项式，结果都不匹配:

SSE4.2: 606105071
JS (example): 1249991249 

然后我开始思考，这一定是从 Javascript 字符串到 C/C++ 数据的转换，我发现 NodeJS 实现使用 UTF8 ( https://github.com/Voxer/sse4_crc32/blob/master/src/sse4_crc32.cpp#L56 )，而 Javascript 使用 UCS-2 编码。

现在，我的问题是:

1. 这些函数有效吗？第一个似乎是这样，对于我发布的那个，我不确定我是否正确翻译了所有位运算
2. 如何解决编码问题？正如我怀疑的那样，这是否是一个编码问题？有没有人有任何其他想法如何确保nodeJS硬件实现和客户端实现返回相同的输出？

感谢您的任何想法!

Answer 1

参见this answer用于兼容的软件实现和使用硬件指令的快速实现。

您遇到了一些问题。一是在 Javascript 中，您需要使用逻辑右移 >>> 而不是算术右移 >>。其次，您使用的是 charCodeAt，它返回一个字符的 Unicode 值，该值可能超过一个字节。 CRC 算法对字节序列进行操作，而不是对 Unicode 字符序列进行操作。第三，您每次都计算同一个表——该表应该只计算一次。最后，您将直接跳到复杂的实现。

作为一个简单的示例，这将在 Javascript 中对预期为 0..255 范围内的整数(即字节)的值数组计算 CRC-32C:

function crc32c(crc, bytes) {
  var POLY = 0x82f63b78;
  var n;

  crc ^= 0xffffffff;
  for (n = 0; n < bytes.length; n++) {
    crc ^= bytes[n];
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
    crc = crc & 1 ? (crc >>> 1) ^ POLY : crc >>> 1;
  }
  return crc ^ 0xffffffff;
}