Come ottenere un algoritmo di file di hashing veloce per file di grandi dimensioni su un dispositivo mobile

Question

prologo
Tuttavia una scoperta importante faccio durante i test del md5, Adler32 e CRC32 su un file di 100 MB, è che stranamente ci vuole lo stesso tempo. Questo può significare solo una delle due cose che immagino, che sul dispositivo Android, il filesystem è il collo di bottiglia e non può alimentare abbastanza velocemente l'algoritmo, o ho fatto un errore fondamentale nell'implementare JNI, il successivo con cui avrei potuto convivere.

Hash di file di piccole dimensioni come immagini, file mp3 e sotto i 10Mb impiegano secondi utilizzando l'algoritmo MD5 .

Il mio problema è che ho file con dimensioni superiori a 100-700 MB.

Il mio requisito è che i file scaricati debbano corrispondere al file sorgente originale.

Ho eseguito alcuni test per la creazione di hash MD5 per un file della dimensione di 100 Mb.

Sul dispositivo HTC Desire Android v2.2 eseguo entrambi un test jni nativo e il test java MessageDigest.getInstance("MD5");.

Entrambi i test hanno calcolato l'MD5 dello stesso file e l'approssimazione del test per lo stesso intervallo di tempo 1-2 minuti. Ho fatto il debugging di.

Era a mia conoscenza che il test nativo sarebbe stato più veloce.

Come posso ottenere il tempo di hash per dire 10-15 sec per 100 MB sul dispositivo sopra.
Il costo per questo è, naturalmente, l'accuratezza della collisione, ma posso convivere che l'hash non è lo stesso in uno su un milione.

UPDATE Im no c guru, ma qui è il mio test c-code per MD5. La velocità su questo non era molto più veloce di Java MessageDigest. Sembrava che stavo correndo sul thread dell'interfaccia utente principale di 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 utilizza BouncyCastle per il crytpoapi che implementa tutti i suoi algoritmi di digest in java. Quindi hai ragione, dovrebbe essere più veloce quando è completamente nativo. Quando hai la conoscenza e il tempo (e la necessità di) di usarli nel codice nativo, sarà (secondo le tue misure) un po 'più veloce.

Si sould anche utilizzare il protocollo TCP o un altro protocollo che assicura che i dati arrivino correttamente (immagino si sta già utilizzando il protocollo TCP e non UDP come si usa FTP)

Quello che vorrei fare è la seguente, in questo caso:

Vorrei creare 2 nuovi thread (oltre al thread UI che fa una stampa progressbar di fantasia) dove il primo è responsabile per il download e il secondo è responsabile per l'hashing.

Il thread di download ora notificherà il thread di hashing sui blocchi appena arrivati. I blocchi potrebbero essere 10 MB o così.Quindi il thread di hashing elabora solo blocchi da 10 MB che dovrebbero essere ragionevolmente veloci e dovrebbero anche conservare la possibilità di notare le interruzioni di file in anticipo. Con questo approccio è anche possibile rilevare quando il download si interrompe e può scaricare nuovamente il file con il primo blocco interrotto. Ovviamente dovresti creare e trasferire una chunklist al client prima che questo possa funzionare.

Qui puoi anche utilizzare un algoritmo di hashing molto veloce che è adatto per rilevare le interruzioni di trasferimento (che non dovrebbero venire quando usi TCP che garantisce che i dati arrivino correttamente se inviati così).

Dopo aver letto di nuovo il mio messaggio questo sembra un po 'come un torrent (chunkbased, hash per vedere se tutto è corretto, in grado di ritrasmettere ...).

Punti bonus: farlo nel codice nativo quindi è un po 'più veloce.

Answer 2

Si potrebbe provare l'approccio rsync cioè inizialmente utilizzare un hash veloce come Adler32 o CRC-32 e usare solo il MD5 più lento quando si ottiene una collisione sul hash veloce.