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

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

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

问题

我有一个Go语言的函数：

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"github.com/snksoft/crc"
  6. )
  8. var crcTable *crc.Table
  10. func init() {
  11. 	params := crc.CRC32
  12. 	params.FinalXor = 0
  13. 	params.ReflectOut = false
  14. 	crcTable = crc.NewTable(params)
  15. }
  17. func crcCalculateBlock(data []byte) uint32 {
  19. 	if len(data)%4 > 0 {
  20. 		panic("block size needs to be a multiple of 4")
  21. 	}
  23. 	h := crc.NewHashWithTable(crcTable)
  25. 	var buf [4]byte
  26. 	for i := 0; i < len(data); i += 4 {
  27. 		buf[0] = data[i+3]
  28. 		buf[1] = data[i+2]
  29. 		buf[2] = data[i+1]
  30. 		buf[3] = data[i+0]
  31. 		h.Update(buf[:])
  32. 	}
  34. 	return h.CRC32()
  35. }
  37. func main() {
  38. 	data := []byte{1, 2, 3, 4, 5, 6, 7, 8}
  39. 	crc := crcCalculateBlock([]byte(data))
  40. 	fmt.Printf("CRC is 0x%04X\n", crc)
  41. }

结果是：0x948B389D

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

  1. var makeCRCTable = function(){
  2.     var c;
  3.     var crcTable = [];
  4.     for(var n =0; n < 256; n++){
  5.         c = n;
  6.         for(var k =0; k < 8; k++){
  7.             c = ((c&1) ? (0xEDB88320 ^ (c >>> 1)) : (c >>> 1));
  8.         }
  9.         crcTable[n] = c;
  10.     }
  11.     return crcTable;
  12. }
  14. var crc32 = function(u8array) {
  15.     var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  16.     var crc = 0 ^ (-1);
  18.     for (var i = 0; i < u8array.length; i+=4 ) {
  19.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+3]) & 0xFF];
  20.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+2]) & 0xFF];
  21.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+1]) & 0xFF];
  22.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i]) & 0xFF];
  23.     }
  25.     return (crc ^ (-1)) >>> 0;
  26. };
  28. console.log(crc32(Uint8Array.from([1,2,3,4,5,6,7,8])).toString(16))

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

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

英文:

I have this function in Go:

  1. package main
  3. import (
  4. 	&quot;fmt&quot;
  5. 	&quot;github.com/snksoft/crc&quot;
  6. )
  8. var crcTable *crc.Table
  10. func init() {
  11.         params := crc.CRC32
  12.         params.FinalXor = 0
  13.         params.ReflectOut = false
  14.         crcTable = crc.NewTable(params)
  15. }
  17. func crcCalculateBlock(data []byte) uint32 {
  19. 	if len(data)%4 &gt; 0 {
  20. 		panic(&quot;block size needs to be a multiple of 4&quot;)
  21. 	}
  23. 	h := crc.NewHashWithTable(crcTable)
  25. 	var buf [4]byte
  26. 	for i := 0; i &lt; len(data); i += 4 {
  27. 		buf[0] = data[i+3]
  28. 		buf[1] = data[i+2]
  29. 		buf[2] = data[i+1]
  30. 		buf[3] = data[i+0]
  31. 		h.Update(buf[:])
  32. 	}
  34. 	return h.CRC32()
  35. }
  37. func main() {
  38.   data := []byte{1, 2, 3, 4, 5, 6, 7, 8}
  39. 	crc := crcCalculateBlock([]byte(data))
  40. 	fmt.Printf(&quot;CRC is 0x%04X\n&quot;, crc)
  41. }

The result is: 0x948B389D

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

  1. var makeCRCTable = function(){
  2.     var c;
  3.     var crcTable = [];
  4.     for(var n =0; n &lt; 256; n++){
  5.         c = n;
  6.         for(var k =0; k &lt; 8; k++){
  7.             c = ((c&amp;1) ? (0xEDB88320 ^ (c &gt;&gt;&gt; 1)) : (c &gt;&gt;&gt; 1));
  8.         }
  9.         crcTable[n] = c;
  10.     }
  11.     return crcTable;
  12. }
  14. var crc32 = function(u8array) {
  15.     var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  16.     var crc = 0 ^ (-1);
  18.     for (var i = 0; i &lt; u8array.length; i+=4 ) {
  19.         crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+3]) &amp; 0xFF];
  20.         crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+2]) &amp; 0xFF];
  21.         crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+1]) &amp; 0xFF];
  22.         crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i]) &amp; 0xFF];
  23.     }
  25.     return (crc ^ (-1)) &gt;&gt;&gt; 0;
  26. };
  28. 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）：

    1. if t.crcParams.ReflectOut != t.crcParams.ReflectIn {
    2. 	ret = reflect(ret, t.crcParams.Width)
    3. }

  2. Go语言中的FinalXor是0（params.FinalXor = 0），而JavaScript中是-1（return (crc ^ (-1)) >>> 0;）

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

  1. var makeCRCTable = function () {
  2.   var c;
  3.   var crcTable = [];
  4.   for (var n = 0; n < 256; n++) {
  5.     c = n;
  6.     for (var k = 0; k < 8; k++) {
  7.       c = c & 1 ? 0xedb88320 ^ (c >>> 1) : c >>> 1;
  8.     }
  9.     crcTable[n] = c;
  10.   }
  11.   return crcTable;
  12. };
  14. var crc32 = function (u8array) {
  15.   var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  16.   var crc = 0 ^ -1;
  18.   for (var i = 0; i < u8array.length; i += 4) {
  19.     crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i + 3]) & 0xff];
  20.     crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i + 2]) & 0xff];
  21.     crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i + 1]) & 0xff];
  22.     crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i]) & 0xff];
  23.   }
  25.   crc = reverseBits(crc, 32);
  27.   return (crc ^ 0) >>> 0;
  28. };
  30. function reverseBits(integer, bitLength) {
  31.   if (bitLength > 32) {
  32.     throw Error(
  33.       'Bit manipulation is limited to <= 32 bit numbers in JavaScript.'
  34.     );
  35.   }
  37.   let result = 0;
  38.   for (let i = 0; i < bitLength; i++) {
  39.     result |= ((integer >> i) & 1) << (bitLength - 1 - i);
  40.   }
  42.   return result >>> 0; // >>> 0 makes it unsigned even if bit 32 (the sign bit) was set
  43. }
  45. 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):

    1. if t.crcParams.ReflectOut != t.crcParams.ReflectIn {
    2. 	ret = reflect(ret, t.crcParams.Width)
    3. }

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

  1. var makeCRCTable = function () {
  2. var c;
  3. var crcTable = [];
  4. for (var n = 0; n &lt; 256; n++) {
  5. c = n;
  6. for (var k = 0; k &lt; 8; k++) {
  7. c = c &amp; 1 ? 0xedb88320 ^ (c &gt;&gt;&gt; 1) : c &gt;&gt;&gt; 1;
  8. }
  9. crcTable[n] = c;
  10. }
  11. return crcTable;
  12. };
  13. var crc32 = function (u8array) {
  14. var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  15. var crc = 0 ^ -1;
  16. for (var i = 0; i &lt; u8array.length; i += 4) {
  17. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i + 3]) &amp; 0xff];
  18. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i + 2]) &amp; 0xff];
  19. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i + 1]) &amp; 0xff];
  20. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i]) &amp; 0xff];
  21. }
  22. crc = reverseBits(crc, 32);
  23. return (crc ^ 0) &gt;&gt;&gt; 0;
  24. };
  25. function reverseBits(integer, bitLength) {
  26. if (bitLength &gt; 32) {
  27. throw Error(
  28. &#39;Bit manipulation is limited to &lt;= 32 bit numbers in JavaScript.&#39;
  29. );
  30. }
  31. let result = 0;
  32. for (let i = 0; i &lt; bitLength; i++) {
  33. result |= ((integer &gt;&gt; i) &amp; 1) &lt;&lt; (bitLength - 1 - i);
  34. }
  35. return result &gt;&gt;&gt; 0; // &gt;&gt;&gt; 0 makes it unsigned even if bit 32 (the sign bit) was set
  36. }
  37. 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，我更喜欢这段代码。

  1. function rev(x) {
  2.     x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
  3.     x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
  4.     x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
  5.     x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
  6.     x = (x >>> 16) | (x << 16);
  8.     return x >>> 0;
  9. }
  10. var makeCRCTable = function(){
  11.     var c;
  12.     var crcTable = [];
  13.     for(var n =0; n < 256; n++){
  14.         c = n;
  15.         for(var k =0; k < 8; k++){
  16.             c = ((c&1) ? (0xEDB88320 ^ (c >>> 1)) : (c >>> 1));
  17.         }
  18.         crcTable[n] = c;
  19.     }
  20.     return crcTable;
  21. }
  23. var crc32 = function(u8array) {
  24.     var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  25.     var crc = 0 ^ (-1);
  27.     for (var i = 0; i < u8array.length; i+=4 ) {
  28.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+3]) & 0xFF];
  29.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+2]) & 0xFF];
  30.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i+1]) & 0xFF];
  31.         crc = (crc >>> 8) ^ crcTable[(crc ^ u8array[i]) & 0xFF];
  32.     }
  34.     return rev(crc);
  35. };
  37. 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 -->

  1. function rev(x) {
  2. x = ((x &gt;&gt; 1) &amp; 0x55555555) | ((x &amp; 0x55555555) &lt;&lt; 1);
  3. x = ((x &gt;&gt; 2) &amp; 0x33333333) | ((x &amp; 0x33333333) &lt;&lt; 2);
  4. x = ((x &gt;&gt; 4) &amp; 0x0F0F0F0F) | ((x &amp; 0x0F0F0F0F) &lt;&lt; 4);
  5. x = ((x &gt;&gt; 8) &amp; 0x00FF00FF) | ((x &amp; 0x00FF00FF) &lt;&lt; 8);
  6. x = (x &gt;&gt;&gt; 16) | (x &lt;&lt; 16);
  7. return x &gt;&gt;&gt; 0;
  8. }
  9. var makeCRCTable = function(){
  10. var c;
  11. var crcTable = [];
  12. for(var n =0; n &lt; 256; n++){
  13. c = n;
  14. for(var k =0; k &lt; 8; k++){
  15. c = ((c&amp;1) ? (0xEDB88320 ^ (c &gt;&gt;&gt; 1)) : (c &gt;&gt;&gt; 1));
  16. }
  17. crcTable[n] = c;
  18. }
  19. return crcTable;
  20. }
  21. var crc32 = function(u8array) {
  22. var crcTable = window.crcTable || (window.crcTable = makeCRCTable());
  23. var crc = 0 ^ (-1);
  24. for (var i = 0; i &lt; u8array.length; i+=4 ) {
  25. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+3]) &amp; 0xFF];
  26. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+2]) &amp; 0xFF];
  27. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i+1]) &amp; 0xFF];
  28. crc = (crc &gt;&gt;&gt; 8) ^ crcTable[(crc ^ u8array[i]) &amp; 0xFF];
  29. }
  30. return rev(crc);
  31. };
  32. 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
  • checksum
  • crc32
  • go
  • javascript
匿名

发表评论

匿名网友

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

确定