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

Question

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

Поэтому я ищу совет по алгоритму хеширования / контрольной суммы по следующим критериям:

• Он будет сгенерирован Javascript, поэтому должен быть относительно легким в вычислительном отношении.
• Проверка будет выполняться Java (хотя я не вижу в этом проблемы).
• Это займет текстовый ввод (кодированный URL-адрес Unicode, который я считаю ASCII) умеренной длины; обычно около 200-300 символов и во всех случаях ниже 2000.
• Выходные данные должны быть также в формате ASCII, и чем короче, тем лучше.

Меня в первую очередь интересует что-то более легкое, чем получение минимально возможного столкновения. Буду ли я наивным думать, что для этого подойдет хэш из восьми символов? Я также должен уточнить, что это не конец света, если коррупция не обнаружена на этапе проверки (и я действительно понимаю, что это не будет на 100% надежно), хотя остальная часть моего кода заметно менее эффективна для каждого поврежденная запись, которая проскальзывает.

Редактировать - спасибо всем, кто внес вклад. Я выбрал опцию Adler32 и, учитывая, что она изначально поддерживается в Java, чрезвычайно проста для реализации в Javascript, быстро рассчитывается на обоих концах и имеет 8-байтовый вывод, это было точно для моих требований.

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

Answer 1

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

Adler32 в Википедии

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

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

Answer 2

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

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

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

Answer 3

В моем поиске реализации хорошего алгоритма контрольной суммы на 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 , по сравнению с оптимизированная версия, которая откладывает операцию по модулю. Я добавил вышеупомянутую реализацию под именем full-length на страницу jsperf , показывающую, что вышеупомянутая реализация примерно на 25% быстрее, чем та, что из imaya и примерно на 570% быстрее, чем простая реализация (тесты выполняются в Chrome 30): http://jsperf.com/adler-32-simple-vs-optimized/6

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

Answer 4

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

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

Answer 5

Реализация JavaScript для MD4, MD5 и SHA1 . Лицензия BSD.

Answer 6

[ОБНОВЛЕНИЕ 30/5/2013: связь со старой реализацией JS CRC32 прекратилась, поэтому я теперь связался с другой.]

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

Answer 7

Вот сравнительно простой, который я «изобрел» - за ним нет математических исследований, но он очень быстрый и работает на практике. Я также включил 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;
    }
}

Answer 8

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

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

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