13

为了保持一致性，我发现自己需要为一串数据生成校验和。广义的想法是客户端可以根据接收到的有效负载重新生成校验和，从而检测传输过程中发生的任何损坏。我隐约知道这种事情背后有各种各样的数学原理，如果你自己尝试滚动它，很容易出现细微的错误使整个算法失效。

因此，我正在寻找有关具有以下标准的散列/校验和算法的建议：

  • 它将由 Javascript 生成，因此需要相对较轻的计算量。
  • 验证将由 Java 完成（尽管我看不出这实际上是一个问题）。
  • 它将采用中等长度的文本输入（URL 编码的 Unicode，我认为是 ASCII）；通常大约 200-300 个字符，并且在所有情况下都低于 2000 个。
  • 输出也应该是 ASCII 文本，越短越好。

我主要对轻量级的东西感兴趣，而不是获得绝对最小的碰撞可能性。我会天真地想象一个八字符的哈希会适合这个吗？我还应该澄清，如果在验证阶段没有发现损坏，这不是世界末日（而且我确实意识到这不会 100% 可靠），尽管我的其余代码对每个人来说效率明显较低漏掉的损坏条目。

编辑 - 感谢所有的贡献。我选择了 Adler32 选项，考虑到它在 Java 中得到原生支持，在 Javascript 中非常容易实现，两端计算速度快，输出 8 字节，完全符合我的要求。

（请注意，我意识到网络传输不太可能对任何损坏错误负责，并且暂时不会在这个问题上袖手旁观；但是添加校验和验证可以消除一个故障点，意味着我们可以专注于其他领域如果这种情况再次发生。）

4

9 回答 9

14

CRC32 用任何语言都不太难实现，它足以检测简单的数据损坏，并且当以良好的方式实现时，它非常快。但是，您也可以尝试 Adler32，它几乎与 CRC32 一样好，但它更容易实现（而且速度也差不多）。

维基百科中的 Adler32

CRC32 JavaScript 实现示例

这两者中的任何一个（或者甚至两者）都可以在 Java 中开箱即用。

于 2009-01-07T18:28:59.827 回答
6

是否知道 TCP 和 UDP（以及 IP、以太网和...）已经为传输中的数据提供校验和保护？

除非你在做一些非常奇怪的事情，否则如果你看到腐败，那就是大错特错了。我建议从内存测试仪开始。

此外，如果您使用 SSL/TLS，您将获得强大的数据完整性保护。

于 2009-01-07T19:13:41.890 回答
2

[更新 30/5/2013：旧 JS CRC32 实现的链接失效了，所以我现在链接到另一个。]

Google CRC32：速度快，重量比 MD5 等轻得多。这里有一个 Javascript 实现。

于 2009-01-07T18:27:44.307 回答
2

MD4、MD5 和 SHA1 的 Javascript 实现。BSD 许可证。

于 2009-01-07T18:30:52.427 回答
2

其他人已经提到了 CRC32，但这里有一个指向PNG 的 CRC-32 的 W3C 实现的链接，它是为数不多的具有参考 CRC 实现的知名网站之一。

（几年前，我试图找到一个有 CRC 算法的知名网站，或者至少有一个引用了其算法来源的网站，在找到 PNG 页面之前，我差点把头发扯掉。）

于 2009-01-07T20:12:09.137 回答
2

在我寻找一个好的校验和算法的 JavaScript 实现时，我遇到了这个问题。Andrzej Doyle正确地选择了 Adler32 作为校验和，因为它确实很容易实现并且具有一些出色的特性。DroidOS然后用 JavaScript 提供了一个实际的实现，这证明了它的简单性。

但是，该算法可以进一步改进，如 Wikipedia 页面中所详述并在下面实现。诀窍是您不需要确定每个步骤中的模数。相反，您可以将其推迟到最后。这大大提高了实施速度，在 Chrome 和 Safari 上速度提高了 6 倍。此外，这种优化不会影响代码的可读性，从而实现双赢。因此，它绝对适合最初的问题，即拥有计算量轻的算法/实现。

function adler32(data) {
  var MOD_ADLER = 65521;
  var a = 1, b = 0;

  var len = data.length;

  for (var i = 0; i < len; i++) {
    a += data.charCodeAt(i);
    b += a;
  }

  a %= MOD_ADLER;
  b %= MOD_ADLER;

  return (b << 16) | a;
}

编辑： imaya 不久前创建了一个 jsperf 比较，显示了运行简单版本时的速度差异，如DroidOS所详述，与延迟模运算的优化版本相比。我在jsperf 页面中添加了名为full-length的上述实现，显示上述实现比imaya的实现快约 25%，比简单实现快约 570%（测试在 Chrome 30 上运行）：http： //jsperf.com/adler-32-simple-vs-optimized/6

编辑2：请不要忘记，在处理大文件时，您最终会在 a 和 b 变量方面达到 JavaScript 实现的限制。因此，在处理大型数据源时，您应该执行中间模运算，以确保您不会超过可以可靠存储的整数的最大值。

于 2013-11-07T14:48:56.520 回答
1

使用SHA-1 JS 实现。它没有你想象的那么慢（Core 2 Duo 2.4Ghz 上的 Firefox 3.0 每秒散列超过 100KB）。

于 2009-01-07T18:27:14.200 回答
1

这是我“发明”的一个相对简单的方法——它背后没有数学研究，但它非常快并且在实践中有效。我还包括了测试算法的 Java 等效项，并显示失败的可能性不到 10,000,000 分之一（运行需要一两分钟）。

JavaScript

function getCrc(s) {
    var result = 0;
    for(var i = 0; i < s.length; i++) {
        var c = s.charCodeAt(i);
        result = (result << 1) ^ c;
    }
    return result;
}

爪哇

package test;

import java.util.*;

public class SimpleCrc {

    public static void main(String[] args) {
        final Random randomGenerator = new Random();
        int lastCrc = -1;
        int dupes = 0;
        for(int i = 0; i < 10000000; i++) {
            final StringBuilder sb = new StringBuilder();
            for(int j = 0; j < 1000; j++) {
                final char c = (char)(randomGenerator.nextInt(128 - 32) + 32);
                sb.append(c);
            }
            final int crc = crc(sb.toString());
            if(lastCrc == crc) {
                dupes++;
            }
            lastCrc = crc;
        }
        System.out.println("Dupes: " + dupes);
    }

    public static int crc(String string) {
        int result = 0;
        for(final char c : string.toCharArray()) {
            result = (result << 1) ^ c;
        }
        return result;
    }
}
于 2012-11-16T09:19:42.990 回答
0

这是一个相当古老的线程，但我怀疑它仍然经常被查看 - 如果您只需要一段简短但可靠的代码来生成校验和，那么Adler32位算法必须是您的选择。这是JavaScript代码

function adler32(data)
{
 var MOD_ADLER = 65521;
 var a = 1, b = 0;

 for (var i = 0;i < data.length;i++) 
 {
  a = (a + data.charCodeAt(i)) % MOD_ADLER;
  b = (b + a) % MOD_ADLER;
 }

 var adler = a | (b << 16);
 return adler;
}

演示该算法的相应小提琴在这里。

于 2013-10-13T05:49:14.060 回答