Cómo obtener un algoritmo de archivo de hash rápido para archivos de gran tamaño en un dispositivo móvil

Question

prólogo
Sin embargo, un importante descubrimiento que hago durante las pruebas del MD5, Adler32 y crc32 en un archivo de 100 Mb, es que extrañamente se tarda el mismo hora. Esto solo puede significar una de dos cosas, supongo que en el dispositivo Android, el sistema de archivos es el cuello de botella y no puede alimentar el algoritmo lo suficientemente rápido, o cometí un error fundamental al implementar JNI, el último con el que podría vivir.

Hashing pequeños archivos como imágenes, mp3 y archivos de menos de 10Mb toman unos segundos utilizando el algoritmo MD5 .

Mi problema es que tengo archivos con tamaños de más de 100-700MB.

Mi requisito es que los archivos descargados deben coincidir con el archivo fuente original.

Hice algunas pruebas para hacer hash MD5 para un archivo con el tamaño de 100Mb.

En el dispositivo HTC Desire Android v2.2 ejecuto una prueba nativa jni y la prueba java MessageDigest.getInstance("MD5");.

Ambas pruebas calcularon el MD5 del mismo archivo y la aproximación de ejecución de prueba durante el mismo período de tiempo 1-2min. He reparado la depuración.

Tenía entendido que la prueba nativa sería más rápida.

¿Cómo puedo obtener el tiempo de hashing hacia abajo para dejar decir 10-15sec para 100MB en el dispositivo anterior.
El costo de esto es, por supuesto, la precisión de colisión, pero puedo vivir con que el hash no es el mismo en uno en un millón.

ACTUALIZACIÓN Im no c gurú, pero aquí está mi prueba de c-code para MD5. La velocidad en este caso no fue mucho más rápida que Java MessageDigest. Me sentí como si estuviera ejecutando el hilo de interfaz de usuario principal de Android.

#include <android/log.h> 
#include <stdio.h> 
#include <sys/types.h> 
#include <time.h> 
#include <string.h> 
#include <inttypes.h> 
#include <jni.h> 
#include <stdlib.h> 
/* typedef a 32 bit type */ 
typedef unsigned long int UINT4; 

/* Data structure for MD5 (Message Digest) computation */ 
typedef struct { 
    UINT4 i[2];     /* number of _bits_ handled mod 2^64 */ 
    UINT4 buf[4];         /* scratch buffer */ 
    unsigned char in[64];        /* input buffer */ 
    unsigned char digest[16];  /* actual digest after MD5Final call */ 
} MD5_CTX; 

void MD5Init(); 
void MD5Update(); 
void MD5Final(); 



/* forward declaration */ 
static void Transform(); 

static unsigned char PADDING[64] = { 
    0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 
}; 

/* F, G and H are basic MD5 functions: selection, majority, parity */ 
#define F(x, y, z) (((x) & (y)) | ((~x) & (z))) 
#define G(x, y, z) (((x) & (z)) | ((y) & (~z))) 
#define H(x, y, z) ((x)^(y)^(z)) 
#define I(x, y, z) ((y)^((x) | (~z))) 

/* ROTATE_LEFT rotates x left n bits */ 
#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) 

/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4 */ 
/* Rotation is separate from addition to prevent recomputation */ 
#define FF(a, b, c, d, x, s, ac) \ 
    {(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \ 
    (a) = ROTATE_LEFT ((a), (s)); \ 
    (a) += (b); \ 
    } 
#define GG(a, b, c, d, x, s, ac) \ 
    {(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \ 
    (a) = ROTATE_LEFT ((a), (s)); \ 
    (a) += (b); \ 
    } 
#define HH(a, b, c, d, x, s, ac) \ 
    {(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \ 
    (a) = ROTATE_LEFT ((a), (s)); \ 
    (a) += (b); \ 
    } 
#define II(a, b, c, d, x, s, ac) \ 
    {(a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \ 
    (a) = ROTATE_LEFT ((a), (s)); \ 
    (a) += (b); \ 
    } 

void MD5Init (mdContext) 
MD5_CTX *mdContext; 
{ 
    mdContext->i[0] = mdContext->i[1] = (UINT4)0; 

    /* Load magic initialization constants. 
    */ 
    mdContext->buf[0] = (UINT4)0x67452301; 
    mdContext->buf[1] = (UINT4)0xefcdab89; 
    mdContext->buf[2] = (UINT4)0x98badcfe; 
    mdContext->buf[3] = (UINT4)0x10325476; 
} 

void MD5Update (mdContext, inBuf, inLen) 
MD5_CTX *mdContext; 
unsigned char *inBuf; 
unsigned int inLen; 
{ 
    UINT4 in[16]; 
    int mdi; 
    unsigned int i, ii; 

    /* compute number of bytes mod 64 */ 
    mdi = (int)((mdContext->i[0] >> 3) & 0x3F); 

    /* update number of bits */ 
    if ((mdContext->i[0] + ((UINT4)inLen << 3)) < mdContext->i[0]) 
    mdContext->i[1]++; 
    mdContext->i[0] += ((UINT4)inLen << 3); 
    mdContext->i[1] += ((UINT4)inLen >> 29); 

    while (inLen--) { 
    /* add new character to buffer, increment mdi */ 
    mdContext->in[mdi++] = *inBuf++; 

    /* transform if necessary */ 
    if (mdi == 0x40) { 
     for (i = 0, ii = 0; i < 16; i++, ii += 4) 
     in[i] = (((UINT4)mdContext->in[ii+3]) << 24) | 
       (((UINT4)mdContext->in[ii+2]) << 16) | 
       (((UINT4)mdContext->in[ii+1]) << 8) | 
       ((UINT4)mdContext->in[ii]); 
     Transform (mdContext->buf, in); 
     mdi = 0; 
    } 
    } 
} 

void MD5Final (mdContext) 
MD5_CTX *mdContext; 
{ 
    UINT4 in[16]; 
    int mdi; 
    unsigned int i, ii; 
    unsigned int padLen; 

    /* save number of bits */ 
    in[14] = mdContext->i[0]; 
    in[15] = mdContext->i[1]; 

    /* compute number of bytes mod 64 */ 
    mdi = (int)((mdContext->i[0] >> 3) & 0x3F); 

    /* pad out to 56 mod 64 */ 
    padLen = (mdi < 56) ? (56 - mdi) : (120 - mdi); 
    MD5Update (mdContext, PADDING, padLen); 

    /* append length in bits and transform */ 
    for (i = 0, ii = 0; i < 14; i++, ii += 4) 
    in[i] = (((UINT4)mdContext->in[ii+3]) << 24) | 
      (((UINT4)mdContext->in[ii+2]) << 16) | 
      (((UINT4)mdContext->in[ii+1]) << 8) | 
      ((UINT4)mdContext->in[ii]); 
    Transform (mdContext->buf, in); 

    /* store buffer in digest */ 
    for (i = 0, ii = 0; i < 4; i++, ii += 4) { 
    mdContext->digest[ii] = (unsigned char)(mdContext->buf[i] & 0xFF); 
    mdContext->digest[ii+1] = 
     (unsigned char)((mdContext->buf[i] >> 8) & 0xFF); 
    mdContext->digest[ii+2] = 
     (unsigned char)((mdContext->buf[i] >> 16) & 0xFF); 
    mdContext->digest[ii+3] = 
     (unsigned char)((mdContext->buf[i] >> 24) & 0xFF); 
    } 
} 

/* Basic MD5 step. Transform buf based on in. 
*/ 
static void Transform (buf, in) 
UINT4 *buf; 
UINT4 *in; 
{ 
    UINT4 a = buf[0], b = buf[1], c = buf[2], d = buf[3]; 

    /* Round 1 */ 
#define S11 7 
#define S12 12 
#define S13 17 
#define S14 22 
    FF (a, b, c, d, in[ 0], S11, 3614090360u); /* 1 */ 
    FF (d, a, b, c, in[ 1], S12, 3905402710u); /* 2 */ 
    FF (c, d, a, b, in[ 2], S13, 606105819u); /* 3 */ 
    FF (b, c, d, a, in[ 3], S14, 3250441966u); /* 4 */ 
    FF (a, b, c, d, in[ 4], S11, 4118548399u); /* 5 */ 
    FF (d, a, b, c, in[ 5], S12, 1200080426u); /* 6 */ 
    FF (c, d, a, b, in[ 6], S13, 2821735955u); /* 7 */ 
    FF (b, c, d, a, in[ 7], S14, 4249261313u); /* 8 */ 
    FF (a, b, c, d, in[ 8], S11, 1770035416u); /* 9 */ 
    FF (d, a, b, c, in[ 9], S12, 2336552879u); /* 10 */ 
    FF (c, d, a, b, in[10], S13, 4294925233u); /* 11 */ 
    FF (b, c, d, a, in[11], S14, 2304563134u); /* 12 */ 
    FF (a, b, c, d, in[12], S11, 1804603682u); /* 13 */ 
    FF (d, a, b, c, in[13], S12, 4254626195u); /* 14 */ 
    FF (c, d, a, b, in[14], S13, 2792965006u); /* 15 */ 
    FF (b, c, d, a, in[15], S14, 1236535329u); /* 16 */ 

    /* Round 2 */ 
#define S21 5 
#define S22 9 
#define S23 14 
#define S24 20 
    GG (a, b, c, d, in[ 1], S21, 4129170786u); /* 17 */ 
    GG (d, a, b, c, in[ 6], S22, 3225465664u); /* 18 */ 
    GG (c, d, a, b, in[11], S23, 643717713u); /* 19 */ 
    GG (b, c, d, a, in[ 0], S24, 3921069994u); /* 20 */ 
    GG (a, b, c, d, in[ 5], S21, 3593408605u); /* 21 */ 
    GG (d, a, b, c, in[10], S22, 38016083u); /* 22 */ 
    GG (c, d, a, b, in[15], S23, 3634488961u); /* 23 */ 
    GG (b, c, d, a, in[ 4], S24, 3889429448u); /* 24 */ 
    GG (a, b, c, d, in[ 9], S21, 568446438u); /* 25 */ 
    GG (d, a, b, c, in[14], S22, 3275163606u); /* 26 */ 
    GG (c, d, a, b, in[ 3], S23, 4107603335u); /* 27 */ 
    GG (b, c, d, a, in[ 8], S24, 1163531501u); /* 28 */ 
    GG (a, b, c, d, in[13], S21, 2850285829u); /* 29 */ 
    GG (d, a, b, c, in[ 2], S22, 4243563512u); /* 30 */ 
    GG (c, d, a, b, in[ 7], S23, 1735328473u); /* 31 */ 
    GG (b, c, d, a, in[12], S24, 2368359562u); /* 32 */ 

    /* Round 3 */ 
#define S31 4 
#define S32 11 
#define S33 16 
#define S34 23 
    HH (a, b, c, d, in[ 5], S31, 4294588738u); /* 33 */ 
    HH (d, a, b, c, in[ 8], S32, 2272392833u); /* 34 */ 
    HH (c, d, a, b, in[11], S33, 1839030562u); /* 35 */ 
    HH (b, c, d, a, in[14], S34, 4259657740u); /* 36 */ 
    HH (a, b, c, d, in[ 1], S31, 2763975236u); /* 37 */ 
    HH (d, a, b, c, in[ 4], S32, 1272893353u); /* 38 */ 
    HH (c, d, a, b, in[ 7], S33, 4139469664u); /* 39 */ 
    HH (b, c, d, a, in[10], S34, 3200236656u); /* 40 */ 
    HH (a, b, c, d, in[13], S31, 681279174u); /* 41 */ 
    HH (d, a, b, c, in[ 0], S32, 3936430074u); /* 42 */ 
    HH (c, d, a, b, in[ 3], S33, 3572445317u); /* 43 */ 
    HH (b, c, d, a, in[ 6], S34, 76029189u); /* 44 */ 
    HH (a, b, c, d, in[ 9], S31, 3654602809u); /* 45 */ 
    HH (d, a, b, c, in[12], S32, 3873151461u); /* 46 */ 
    HH (c, d, a, b, in[15], S33, 530742520u); /* 47 */ 
    HH (b, c, d, a, in[ 2], S34, 3299628645u); /* 48 */ 

    /* Round 4 */ 
#define S41 6 
#define S42 10 
#define S43 15 
#define S44 21 
    II (a, b, c, d, in[ 0], S41, 4096336452u); /* 49 */ 
    II (d, a, b, c, in[ 7], S42, 1126891415u); /* 50 */ 
    II (c, d, a, b, in[14], S43, 2878612391u); /* 51 */ 
    II (b, c, d, a, in[ 5], S44, 4237533241u); /* 52 */ 
    II (a, b, c, d, in[12], S41, 1700485571u); /* 53 */ 
    II (d, a, b, c, in[ 3], S42, 2399980690u); /* 54 */ 
    II (c, d, a, b, in[10], S43, 4293915773u); /* 55 */ 
    II (b, c, d, a, in[ 1], S44, 2240044497u); /* 56 */ 
    II (a, b, c, d, in[ 8], S41, 1873313359u); /* 57 */ 
    II (d, a, b, c, in[15], S42, 4264355552u); /* 58 */ 
    II (c, d, a, b, in[ 6], S43, 2734768916u); /* 59 */ 
    II (b, c, d, a, in[13], S44, 1309151649u); /* 60 */ 
    II (a, b, c, d, in[ 4], S41, 4149444226u); /* 61 */ 
    II (d, a, b, c, in[11], S42, 3174756917u); /* 62 */ 
    II (c, d, a, b, in[ 2], S43, 718787259u); /* 63 */ 
    II (b, c, d, a, in[ 9], S44, 3951481745u); /* 64 */ 

    buf[0] += a; 
    buf[1] += b; 
    buf[2] += c; 
    buf[3] += d; 
} 

JNIEXPORT jstring 
    Java_com_carlsberg_IntentServiceSendFiles_gethash(JNIEnv* env, jobject thiz , 
jstring filename) 
{ 

    const char *fi = (*env)->GetStringUTFChars(env,filename, 0); 

     FILE *inFile = fopen (fi, "rb"); 
     MD5_CTX mdContext; 
     int bytes; 
     unsigned char data[1024]; 

     if (inFile == NULL) { 
     printf ("%s can't be opened.\n",fi); 
     return; 
     } 

     MD5Init (&mdContext); 
     while ((bytes = fread (data, 1, 1024, inFile)) != 0) 
     MD5Update (&mdContext, data, bytes); 
     MD5Final (&mdContext); 
     fclose (inFile); 

     char tempValue[33]; // 32 hex digits + 0-terminator 
     int i; 
     // convert to hex 
     for (i = 0; i < 16; ++i) 
      sprintf(tempValue + 2*i, "%02x", (unsigned char)mdContext.digest[i]); 

     return (*env)->NewStringUTF(env,tempValue); 

} 

Answer 1

Android usa BouncyCastle para el crytpoapi que implementa todos sus algoritmos de resumen en java. Así que tienes razón, debería ser más rápido cuando se hace completamente nativo. Cuando tenga el conocimiento y el tiempo (y la necesidad de) utilizarlos en el código nativo, será (de acuerdo con sus mediciones) un poco más rápido.

También sould utiliza TCP u otro protocolo que asegura que los datos llegan correctamente (supongo que ya utiliza TCP y no UDP como se utiliza FTP)

Lo que quiero hacer es lo siguiente en este caso:

Crearía dos hilos nuevos (además del hilo de la interfaz de usuario que realiza una elegante impresión en la barra de progreso), donde el primero es responsable de la descarga y el segundo es responsable del hash.

El hilo de descarga ahora notificará al hilo hash sobre los trozos recién llegados. Los trozos podrían ser de 10 MB o menos.Por lo tanto, el subproceso hash procesa solo fragmentos de 10 MB que deben ser razonablemente rápidos y también deben preservar la capacidad de detectar saltos de archivos antes. Con este enfoque, también podría detectar cuándo se descargó la descarga y podría volver a descargar el archivo con el primer fragmento roto. Por supuesto, tendría que crear y transferir una lista de fragmentos al cliente antes de que esto pueda funcionar.

Aquí también puede usar un algoritmo de hashing muy rápido que es adecuado para detectar interrupciones de transferencia (que no deberían aparecer al usar TCP que garantiza que los datos lleguen correctamente si lo envía).

Después de volver a leer el texto, se siente como un torrente (basado en fragmentos, hash para ver si todo es correcto, puede retransmitir ...).

Puntos de bonificación: hágalo en código nativo, por lo que es un poco más rápido.

Answer 2

puede probar con el método rsync es decir, utilizar inicialmente un hash rápido como Adler32 o CRC-32 y sólo utilizar el MD5 más lento cuando se obtiene una colisión en el hash rápido.