경량 체크섬 알고리즘을 위한 좋은 선택인가요?

StackOverflow https://stackoverflow.com/questions/421419

문제

일관성을 위해 데이터 문자열에 대한 체크섬을 생성해야 합니다.광범위한 아이디어는 클라이언트가 수신한 페이로드를 기반으로 체크섬을 재생성하여 전송 중에 발생한 모든 손상을 감지할 수 있다는 것입니다.나는 이런 종류의 일 뒤에 온갖 수학적 원리가 있다는 것을 막연히 알고 있으며, 스스로 굴려 보면 미묘한 오류로 인해 전체 알고리즘이 비효율적으로 변하기가 매우 쉽다는 것을 막연하게 알고 있습니다.

그래서 저는 다음 기준에 따라 해싱/체크섬 알고리즘에 대한 조언을 찾고 있습니다.

  • 이는 Javascript에 의해 생성되므로 상대적으로 계산이 가벼워야 합니다.
  • 유효성 검사는 Java에 의해 수행됩니다(실제로 이것이 문제라고 볼 수는 없습니다).
  • 적당한 길이의 텍스트 입력(ASCII라고 생각되는 URL 인코딩 유니코드)이 필요합니다.일반적으로 약 200~300자이며 모든 경우에 2000자 미만입니다.
  • 출력 역시 ASCII 텍스트여야 하며, 길이가 짧을수록 좋습니다.

나는 충돌 가능성을 최대한 줄이는 것보다 가벼운 것에 주로 관심이 있습니다.8자 해시가 이에 적합할 것이라고 상상하는 것이 순진한 생각일까요?또한 유효성 검사 단계에서 손상이 발견되지 않으면 세상이 끝나는 것이 아니라는 점을 분명히 해야 합니다(그리고 이것이 100% 신뢰할 수는 없다는 것을 알고 있습니다). 하지만 내 코드의 나머지 부분은 모든 경우에 현저히 덜 효율적입니다. 빠져 나가는 손상된 항목.

편집 - 기여해주신 모든 분들께 감사드립니다.나는 Adler32 옵션을 선택했고 그것이 Java에서 기본적으로 지원되고 Javascript로 구현하기가 매우 쉽고 양쪽 끝에서 계산이 빠르고 8바이트 출력이 있다는 점을 고려하면 내 요구 사항에 정확히 맞았습니다.

(네트워크 전송이 손상 오류에 대해 책임을 질 가능성이 거의 없으며 아직 이 문제에 대해 팔짱을 끼지 않을 것임을 알고 있습니다.그러나 체크섬 유효성 검사를 추가하면 한 가지 실패 지점이 제거되고 이 문제가 다시 발생할 경우 다른 영역에 집중할 수 있습니다.)

도움이 되었습니까?

해결책

CRC32는 어떤 언어로든 구현하기가 그리 어렵지 않으며 단순한 데이터 손상을 감지하는 데 충분하며 좋은 방식으로 구현하면 매우 빠릅니다.그러나 CRC32와 거의 동일하지만 구현하기가 더 쉽고 속도도 거의 비슷한 Adler32를 사용해 볼 수도 있습니다.

Wikipedia의 Adler32

CRC32 JavaScript 구현 샘플

이 두 가지 중 하나(또는 둘 다)를 즉시 Java로 사용할 수 있습니다.

다른 팁

TCP와 UDP (및 IP 및 이더넷 및 ...)가 이미 운송중인 데이터에 대한 체크섬 보호를 제공한다는 것을 알고 있습니까?

당신이 정말로 이상한 일을하지 않는 한, 부패를보고 있다면 무언가가 매우 잘못되었습니다. a로 시작하는 것이 좋습니다 메모리 테스터.

또한 SSL/TLS를 사용하는 경우 강력한 데이터 무결성 보호를받습니다.

다른 사람들은 이미 CRC32를 언급했지만 여기에 링크가 있습니다. PNG 용 CRC-32의 W3C 구현, 참조 CRC 구현이있는 잘 알려진 평판이 좋은 사이트 중 하나입니다.

(몇 년 전 CRC 알고리즘이있는 잘 알려진 사이트 또는 알고리즘의 소스를 인용 한 적어도 하나의 사이트를 찾으려고 노력했으며 PNG 페이지를 찾을 때까지 거의 머리카락을 찢어 버렸습니다.)

업데이트 30/5/2013 : 이전 JS CRC32 구현에 대한 링크가 죽었으므로 이제 다른 것과 연결되었습니다.

Google CRC32 : MD5 et al.보다 빠르고 가벼운 무게. JavaScript 구현이 있습니다 여기.

좋은 체크섬 알고리즘의 JavaScript 구현을 검색 할 때이 질문을 발견했습니다. Andrzej Doyle Adler32를 체크섬으로 정당하게 선택했습니다. 실제로 구현하기 쉽고 몇 가지 우수한 특성이 있기 때문입니다. 드로이도 그런 다음 JavaScript의 실제 구현을 제공하여 단순성을 보여주었습니다.

그러나 알고리즘은 Wikipedia 페이지에서 자세히 설명하고 아래에서 구현 된 바와 같이 더욱 향상 될 수 있습니다. 요령은 각 단계에서 모듈로를 결정할 필요가 없다는 것입니다. 오히려, 당신은 이것을 끝까지 연기 할 수 있습니다. 이는 크롬과 사파리에서 최대 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;
}

편집하다: 이마야 jsperf 비교를 잠시 동안 만들었습니다. 드로이도, 모듈로 작동을 방어하는 최적화 된 버전과 비교합니다. 위의 구현을 이름으로 추가했습니다 전장 ~로 JSPERF 페이지 위의 구현이 이마야 간단한 구현보다 약 570% 더 빠릅니다 (테스트는 Chrome 30에서 실행) : http://jsperf.com/adler-32-simple-vs-optimized/6

edit2 : 큰 파일을 작업 할 때는 결국 A 및 B 변수 측면에서 JavaScript 구현 한도에 도달합니다. 따라서 대형 데이터 소스로 작업 할 때는 안정적으로 저장할 수있는 정수의 최대 값을 초과하지 않도록 중간 모듈로 작업을 수행해야합니다.

사용 SHA-1 JS 구현. 생각만큼 느리지 않습니다 (Core 2 Duo 2.4GHz 해시의 Firefox 3.0은 초당 100kb 이상).

여기에 내가 '발명 한'비교적 간단한 것이 있습니다. 그 뒤에는 수학적 연구가 없지만 매우 빠르며 실제로 작동합니다. 또한 알고리즘을 테스트하는 Java 동등성을 포함 시켰으며 실패 할 확률이 10,000,000 명 중 1 명 미만인 것으로 나타났습니다 (실행하는 데 1 ~ 2 분이 소요됨).

자바 스크립트

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

이것은 다소 오래된 스레드이지만 여전히 자주 보는 것으로 생각됩니다. 필요한 것이 짧지 만 신뢰할 수있는 코드가 있다면 체크섬을 생성합니다. 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;
}

작동하는 알고리즘을 악영활시키는 해당 바이올린은 다음과 같습니다 여기.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top