Хороший выбор для легкого алгоритма контрольной суммы?

Ответ 1

CRC32 не слишком сложно реализовать на любом языке, он достаточно хорош, чтобы обнаруживать простое повреждение данных и при правильном использовании, это очень быстро. Однако вы также можете попробовать Adler32, который почти одинаково хорош как CRC32, но его еще проще реализовать (и примерно одинаково быстро).

Adler32 в Википедии

Пример реализации CRC32 JavaScript

Любой из этих двух (или, возможно, даже обоих) доступен в Java прямо из коробки.

Ответ 2

Знают, что и TCP, и UDP (и IP, и Ethernet и...) уже обеспечивают защиту контрольной суммы для данных в пути?

Если вы делаете что-то действительно странное, если вы видите коррупцию, что-то очень не так. Я предлагаю начать с тестера памяти.

Кроме того, вы получаете надежную защиту целостности данных, если используете SSL/TLS.

Ответ 3

[UPDATE 30/5/2013: ссылка на старую реализацию JS CRC32 умерла, поэтому я теперь связан с другим.]

Google CRC32: быстрый и гораздо более легкий вес, чем MD5 и др. Существует реализация Javascript здесь.

Ответ 4

Выполнение Javascript MD4, MD5 и SHA1. Лицензия BSD.

Ответ 5

Другие люди уже упоминали CRC32, но здесь ссылка на реализация W3C CRC-32 для PNG, как один из немногих известных, авторитетных сайтов с эталонной CRC-реализацией.

(Несколько лет назад я попытался найти известный сайт с алгоритмом CRC или, по крайней мере, тот, который привел источник для его алгоритма, и почти разорвал мои волосы, пока не нашел страницу PNG.)

Ответ 6

В моем поиске реализации JavaScript хорошего алгоритма контрольной суммы я столкнулся с этим вопросом. Andrzej Doyle по праву выбрал Adler32 в качестве контрольной суммы, поскольку ее действительно легко реализовать и обладает отличными свойствами. Затем DroidOS предоставил фактическую реализацию в JavaScript, которая продемонстрировала простоту.

Однако алгоритм может быть дополнительно улучшен, как описано на странице Википедии, и как это реализовано ниже. Фокус в том, что вам не нужно определять модуль на каждом шаге. Скорее, вы можете отложить это до конца. Это значительно увеличивает скорость реализации, до 6 раз быстрее в Chrome и Safari. Кроме того, эта оптимизация не влияет на читаемость кода, что делает его беспроигрышным. Таким образом, он определенно хорошо вписывается в исходный вопрос о том, что алгоритм/реализация, которая является вычислительно легкой.

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

edit: imaya создала сравнение jsperf, показывая разницу в скорости при запуске простой версии, как подробно описано DroidOS, по сравнению с оптимизированной версией, которая отменяет операцию по модулю. Я добавил вышеприведенную реализацию под именем полной длины на страницу jsperf, указав, что приведенная выше реализация составляет около 25 % быстрее, чем у имаи и на 570% быстрее, чем простая реализация (тесты выполняются в Chrome 30): http://jsperf.com/adler-32-simple-vs-optimized/6

edit2: не забывайте, что при работе с большими файлами вы в конечном итоге попадете в предел вашей реализации JavaScript в терминах переменных a и b. Таким образом, при работе с большим источником данных вы должны выполнять промежуточные операции с модулями, чтобы гарантировать, что вы не превысите максимальное значение целого, которое вы можете надежно хранить.

Ответ 7

Используйте SHA-1 JS-реализация. Это не так медленно, как вы думаете (Firefox 3.0 на Core 2 Duo 2.4Ghz хэширует более 100 КБ в секунду).

Ответ 8

Здесь относительно простой, который я "придумал" - там нет математических исследований, но он очень быстрый и работает на практике. Я также включил эквивалент Java, который проверяет алгоритм и показывает, что существует менее 1 из 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;
}

Java

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

Ответ 9

Это довольно старый поток, но я подозреваю, что он по-прежнему просматривается довольно часто - если вам нужно всего лишь короткая, но надежная часть кода для создания контрольной суммы 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;
}

Соответствующая скрипка, демонизирующая алгоритм в действии, здесь.