java - reste - ¿Buena elección para un algoritmo de suma de comprobación ligera?
suma de dos numeros en java grafico (9)
Me resulta necesario generar una suma de comprobación para una cadena de datos, para fines de coherencia. La idea general es que el cliente puede regenerar la suma de comprobación en función de la carga útil que recibe y así detectar cualquier corrupción que haya tenido lugar en tránsito. Soy vagamente consciente de que hay todo tipo de principios matemáticos detrás de este tipo de cosas, y que es muy fácil para los errores sutiles hacer que todo el algoritmo sea inefectivo si intentas rodarlo tú mismo.
Así que estoy buscando consejos sobre un algoritmo hash / checksum con los siguientes criterios:
- Será generado por Javascript, por lo que debe ser relativamente ligero computacionalmente.
- La validación será hecha por Java (aunque no puedo ver que esto sea realmente un problema).
- Tomará una entrada textual (Unicode codificado en URL, que creo que es ASCII) de una longitud moderada; típicamente alrededor de 200-300 caracteres y en todos los casos debajo de 2000.
- El resultado también debe ser texto ASCII, y cuanto más corto, mejor.
Principalmente estoy interesado en algo ligero, en lugar de obtener el menor potencial posible de colisiones. ¿Sería ingenuo imaginar que un hash de ocho caracteres fuera adecuado para esto? También debería aclarar que no es el fin del mundo si la corrupción no se detecta en la etapa de validación (y me doy cuenta de que esto no será 100% confiable), aunque el resto de mi código es notablemente menos eficiente para cada Entrada corrupta que se desliza.
Editar - gracias a todo lo que contribuyó. Fui con la opción Adler32 y dado que era nativamente compatible con Java, extremadamente fácil de implementar en Javascript, rápido para calcular en ambos extremos y tener una salida de 8 bytes, era exactamente lo que necesitaba.
(Tenga en cuenta que me doy cuenta de que es poco probable que el transporte de la red sea responsable de cualquier error de corrupción y que no abro los brazos sobre este tema, sin embargo, al agregar la validación de la suma de verificación se elimina un punto de falla y podemos centrarnos en otras áreas si esto vuelve a ocurrir.)
¿Sabe que tanto TCP como UDP (e IP, y Ethernet, y ...) ya proporcionan protección de suma de comprobación a los datos en tránsito?
A menos que estés haciendo algo realmente extraño, si estás viendo corrupción, algo está muy mal. Sugiero comenzar con un probador de memoria .
Además, recibirá una sólida protección de integridad de datos si usa SSL / TLS.
CRC32 no es demasiado difícil de implementar en ningún idioma, es lo suficientemente bueno para detectar datos simples de corrupción y cuando se implementa de una buena manera, es muy rápido. Sin embargo, también puedes probar Adler32, que es casi tan bueno como CRC32, pero es incluso más fácil de implementar (y casi igual de rápido).
Ejemplo de implementación de JavaScript CRC32
Cualquiera de estos dos (o incluso ambos) están disponibles en Java desde el primer momento.
Otras personas ya han mencionado CRC32, pero aquí hay un enlace a la implementación W3C de CRC-32 para PNG , como uno de los pocos sitios conocidos y de buena reputación con una implementación de CRC de referencia.
(Hace unos años traté de encontrar un sitio conocido con un algoritmo CRC o al menos uno que citara la fuente de su algoritmo, y casi me arranqué el pelo hasta que encontré la página PNG).
Use la implementación SHA-1 JS . No es tan lento como crees (Firefox 3.0 en hash Core 2 Duo 2.4Ghz más de 100 KB por segundo).
Implementación de Javascript de MD4, MD5 y SHA1 . Licencia BSD.
Aquí hay uno relativamente simple que he "inventado": no hay investigación matemática detrás, pero es extremadamente rápido y funciona en la práctica. También incluí el equivalente de Java que prueba el algoritmo y muestra que hay menos de 1 en 10,000,000 de probabilidades de falla (se tarda uno o dos minutos en ejecutarse).
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;
}
}
[ACTUALIZACIÓN 30/5/2013: el enlace a la implementación anterior de JS CRC32 murió, así que ahora he vinculado a uno diferente.]
Google CRC32: rápido y mucho más ligero que MD5 et al. Hay una implementación de Javascript aquí .
Este es un hilo bastante antiguo, pero sospecho que todavía se ve con bastante frecuencia, por lo que si lo único que necesita es una pieza breve pero confiable para generar una suma de comprobación, el algoritmo de bits Adler32 debe ser su elección. Aquí está el código de 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;
}
El violín correspondiente que demuestra el algoritmo en acción está aquí .
En mi búsqueda de una implementación de JavaScript de un buen algoritmo de suma de verificación me encontré con esta pregunta. Andrzej Doyle eligió Adler32 como la suma de comprobación, ya que de hecho es fácil de implementar y tiene excelentes propiedades. DroidOS luego proporcionó una implementación real en JavaScript, que demostró la simplicidad.
Sin embargo, el algoritmo puede mejorarse más como se detalla en la página de Wikipedia y como se implementa a continuación. El truco es que no necesita determinar el módulo en cada paso. Por el contrario, puede diferir esto hasta el final. Esto aumenta considerablemente la velocidad de la implementación, hasta 6 veces más rápido en Chrome y Safari. Además, esta optimización no afecta la legibilidad del código, por lo que es beneficioso para todos. Como tal, definitivamente encaja bien con la pregunta original de tener un algoritmo / implementación que sea computacionalmente ligero.
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 creó una comparación jsperf un tiempo atrás mostrando la diferencia de velocidad al ejecutar la versión simple, según lo detalla DroidOS , en comparación con una versión optimizada que difiere la operación del módulo. He agregado la implementación anterior con el nombre completo a la página jsperf que muestra que la implementación anterior es aproximadamente un 25% más rápida que la de imaya y aproximadamente un 570% más rápida que la implementación simple (las pruebas se ejecutan en Chrome 30): http: //jsperf.com/adler-32-simple-vs-optimized/6
edit2: no olvide que, cuando trabaje en archivos de gran tamaño, eventualmente llegará al límite de su implementación de JavaScript en términos de las variables a y b. Como tal, cuando trabaje con una fuente de datos grande, debe realizar operaciones de módulo intermedias para asegurarse de no exceder el valor máximo del entero que puede almacenar confiablemente.