与 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 中计算一个 CRC-32C 值数组，该数组的值预计为 0..255 范围内的整数，即字节:

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;
}