如何将这个 Go 语言的 CRC32 块正确地翻译成 JavaScript?

huangapple go评论73阅读模式
英文:

How to correctly translate this block CRC32 from Go to JavaScript?

问题

我有一个Go语言的函数:

package main

import (
	"fmt"
	"github.com/snksoft/crc"
)

var crcTable *crc.Table

func init() {
	params := crc.CRC32
	params.FinalXor = 0
	params.ReflectOut = false
	crcTable = crc.NewTable(params)
}

func crcCalculateBlock(data []byte) uint32 {

	if len(data)%4 > 0 {
		panic("block size needs to be a multiple of 4")
	}

	h := crc.NewHashWithTable(crcTable)

	var buf [4]byte
	for i := 0; i < len(data); i += 4 {
		buf[0] = data[i+3]
		buf[1] = data[i+2]
		buf[2] = data[i+1]
		buf[3] = data[i+0]
		h.Update(buf[:])
	}

	return h.CRC32()
}

func main() {
	data := []byte{1, 2, 3, 4, 5, 6, 7, 8}
	crc := crcCalculateBlock([]byte(data))
	fmt.Printf("CRC is 0x%04X\n", crc)
}

结果是:0x948B389D

我正在尝试将其翻译为JavaScript,但是我缺少一些东西:

var makeCRCTable = function(){
    var c;
    var crcTable = [];
    for(var n =0; n < 256; n++){
        c = n;
        for(var k =0; k < 8; k++){
            c = ((c&1) ? (0xEDB88320 ^ (c >>> 1)) : (c >>> 1));
        }
        crcTable[n] = c;
    }
    return crcTable;
}

var crc32 = function(u8array) {
    var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
    var crc = 0 ^ (-1);

    for (var i = 0; i < u8array.length; i+=4 ) {
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+3]) & 0xFF];
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+2]) & 0xFF];
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+1]) & 0xFF];
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i]) & 0xFF];
    }

    return (crc ^ (-1)) >>> 0;
};

console.log(crc32(Uint8Array.from([1,2,3,4,5,6,7,8])).toString(16))

但结果不同(46e32ed6)即使没有最终的异或操作,我得到的结果是b91cd129。

有人能解释一下如何纠正这个问题以及为什么会出错吗?

英文:

I have this function in Go:

package main

import (
	&quot;fmt&quot;
	&quot;github.com/snksoft/crc&quot;
)

var crcTable *crc.Table

func init() {
        params := crc.CRC32
        params.FinalXor = 0
        params.ReflectOut = false
        crcTable = crc.NewTable(params)
}

func crcCalculateBlock(data []byte) uint32 {

	if len(data)%4 &gt; 0 {
		panic(&quot;block size needs to be a multiple of 4&quot;)
	}

	h := crc.NewHashWithTable(crcTable)

	var buf [4]byte
	for i := 0; i &lt; len(data); i += 4 {
		buf[0] = data[i+3]
		buf[1] = data[i+2]
		buf[2] = data[i+1]
		buf[3] = data[i+0]
		h.Update(buf[:])
	}

	return h.CRC32()
}

func main() {
  data := []byte{1, 2, 3, 4, 5, 6, 7, 8}
	crc := crcCalculateBlock([]byte(data))
	fmt.Printf(&quot;CRC is 0x%04X\n&quot;, crc)
}

The result is: 0x948B389D

I am trying to translate it to JavaScript but I am missing something:

var makeCRCTable = function(){
    var c;
    var crcTable = [];
    for(var n =0; n &lt; 256; n++){
        c = n;
        for(var k =0; k &lt; 8; k++){
            c = ((c&amp;1) ? (0xEDB88320 ^ (c &gt;&gt;&gt; 1)) : (c &gt;&gt;&gt; 1));
        }
        crcTable[n] = c;
    }
    return crcTable;
}

var crc32 = function(u8array) {
    var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
    var crc = 0 ^ (-1);

    for (var i = 0; i &lt; u8array.length; i+=4 ) {
        crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+3]) &amp; 0xFF];
        crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+2]) &amp; 0xFF];
        crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+1]) &amp; 0xFF];
        crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i]) &amp; 0xFF];
    }

    return (crc ^ (-1)) &gt;&gt;&gt; 0;
};

console.log(crc32(Uint8Array.from([1,2,3,4,5,6,7,8])).toString(16))

but the result is different. ( 46e32ed6 )
even without the final xor I get b91cd129

Can anyone explain to me how to correct that and why is that wrong?

答案1

得分: 3

有两个区别:

  1. Go语言实现中调用了reflect(参见https://github.com/snksoft/crc/blob/03404db21ad4e7182edf4843b51f6252799f7140/crc.go#L168-L170):

    if t.crcParams.ReflectOut != t.crcParams.ReflectIn {
    	ret = reflect(ret, t.crcParams.Width)
    }
    
  2. Go语言中的FinalXor0params.FinalXor = 0),而JavaScript中是-1return (crc ^ (-1)) >>> 0;

以下是生成相同哈希值的更新后的JavaScript实现。

var makeCRCTable = function () {
  var c;
  var crcTable = [];
  for (var n = 0; n < 256; n++) {
    c = n;
    for (var k = 0; k < 8; k++) {
      c = c & 1 ? 0xedb88320 ^ (c >>> 1) : c >>> 1;
    }
    crcTable[n] = c;
  }
  return crcTable;
};

var crc32 = function (u8array) {
  var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  var crc = 0 ^ -1;

  for (var i = 0; i < u8array.length; i += 4) {
    crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i + 3]) & 0xff];
    crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i + 2]) & 0xff];
    crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i + 1]) & 0xff];
    crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i]) & 0xff];
  }

  crc = reverseBits(crc, 32);

  return (crc ^ 0) >>> 0;
};

function reverseBits(integer, bitLength) {
  if (bitLength > 32) {
    throw Error(
      'Bit manipulation is limited to <= 32 bit numbers in JavaScript.'
    );
  }

  let result = 0;
  for (let i = 0; i < bitLength; i++) {
    result |= ((integer >> i) & 1) << (bitLength - 1 - i);
  }

  return result >>> 0; // >>> 0 makes it unsigned even if bit 32 (the sign bit) was set
}

console.log(crc32(Uint8Array.from([1, 2, 3, 4, 5, 6, 7, 8])).toString(16));

注意reverseBits函数是从这个答案中复制的:https://stackoverflow.com/a/67064710/1369400

英文:

There are two differences:

  1. the Go implementation has called reflect (see https://github.com/snksoft/crc/blob/03404db21ad4e7182edf4843b51f6252799f7140/crc.go#L168-L170):

    if t.crcParams.ReflectOut != t.crcParams.ReflectIn {
    	ret = reflect(ret, t.crcParams.Width)
    }
    
  2. the FinalXor in Go is 0 (params.FinalXor = 0) while in js it's -1 (return (crc ^ (-1)) &gt;&gt;&gt; 0;)

Here is the updated js implementation that generates the same hash value.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

var makeCRCTable = function () {
var c;
var crcTable = [];
for (var n = 0; n &lt; 256; n++) {
c = n;
for (var k = 0; k &lt; 8; k++) {
c = c &amp; 1 ? 0xedb88320 ^ (c &gt;&gt;&gt; 1) : c &gt;&gt;&gt; 1;
}
crcTable[n] = c;
}
return crcTable;
};
var crc32 = function (u8array) {
var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
var crc = 0 ^ -1;
for (var i = 0; i &lt; u8array.length; i += 4) {
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i + 3]) &amp; 0xff];
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i + 2]) &amp; 0xff];
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i + 1]) &amp; 0xff];
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i]) &amp; 0xff];
}
crc = reverseBits(crc, 32);
return (crc ^ 0) &gt;&gt;&gt; 0;
};
function reverseBits(integer, bitLength) {
if (bitLength &gt; 32) {
throw Error(
&#39;Bit manipulation is limited to &lt;= 32 bit numbers in JavaScript.&#39;
);
}
let result = 0;
for (let i = 0; i &lt; bitLength; i++) {
result |= ((integer &gt;&gt; i) &amp; 1) &lt;&lt; (bitLength - 1 - i);
}
return result &gt;&gt;&gt; 0; // &gt;&gt;&gt; 0 makes it unsigned even if bit 32 (the sign bit) was set
}
console.log(crc32(Uint8Array.from([1, 2, 3, 4, 5, 6, 7, 8])).toString(16));

<!-- end snippet -->

Note: the reverseBits function is copied from this answer: https://stackoverflow.com/a/67064710/1369400

答案2

得分: 0

感谢Zeke Lu,我更喜欢这段代码。

function rev(x) {
    x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
    x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
    x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
    x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
    x = (x >>> 16) | (x << 16);

    return x >>> 0;
}
var makeCRCTable = function(){
    var c;
    var crcTable = [];
    for(var n =0; n < 256; n++){
        c = n;
        for(var k =0; k < 8; k++){
            c = ((c&1) ? (0xEDB88320 ^ (c >>> 1)) : (c >>> 1));
        }
        crcTable[n] = c;
    }
    return crcTable;
}

var crc32 = function(u8array) {
    var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
    var crc = 0 ^ (-1);

    for (var i = 0; i < u8array.length; i+=4 ) {
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+3]) & 0xFF];
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+2]) & 0xFF];
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+1]) & 0xFF];
        crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i]) & 0xFF];
    }

    return rev(crc);
};

console.log(crc32(Uint8Array.from([1,2,3,4,5,6,7,8])).toString(16))

希望对你有帮助!

英文:

Thanks to Zeke Lu, I prefer this code.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function rev(x) {
x = ((x &gt;&gt; 1) &amp; 0x55555555) | ((x &amp; 0x55555555) &lt;&lt; 1);
x = ((x &gt;&gt; 2) &amp; 0x33333333) | ((x &amp; 0x33333333) &lt;&lt; 2);
x = ((x &gt;&gt; 4) &amp; 0x0F0F0F0F) | ((x &amp; 0x0F0F0F0F) &lt;&lt; 4);
x = ((x &gt;&gt; 8) &amp; 0x00FF00FF) | ((x &amp; 0x00FF00FF) &lt;&lt; 8);
x = (x &gt;&gt;&gt; 16) | (x &lt;&lt; 16);
return x &gt;&gt;&gt; 0;
}
var makeCRCTable = function(){
var c;
var crcTable = [];
for(var n =0; n &lt; 256; n++){
c = n;
for(var k =0; k &lt; 8; k++){
c = ((c&amp;1) ? (0xEDB88320 ^ (c &gt;&gt;&gt; 1)) : (c &gt;&gt;&gt; 1));
}
crcTable[n] = c;
}
return crcTable;
}
var crc32 = function(u8array) {
var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
var crc = 0 ^ (-1);
for (var i = 0; i &lt; u8array.length; i+=4 ) {
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+3]) &amp; 0xFF];
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+2]) &amp; 0xFF];
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+1]) &amp; 0xFF];
crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i]) &amp; 0xFF];
}
return rev(crc);
};
console.log(crc32(Uint8Array.from([1,2,3,4,5,6,7,8])).toString(16))

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年2月7日 06:20:46
  • 转载请务必保留本文链接:https://go.coder-hub.com/75367179.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定