Return to md5p8.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync / lib

Annotation of embedaddon/rsync/lib/md5p8.c, revision 1.1

1.1     ! misho       1: /*
        !             2:  * MD5-based hash friendly to parallel processing, reference implementation
        !             3:  *
        !             4:  * Author: Jorrit Jongma, 2020
        !             5:  *
        !             6:  * Released in the public domain falling back to the MIT license
        !             7:  * ( http://www.opensource.org/licenses/MIT ) in case public domain does not
        !             8:  * apply in your country.
        !             9:  */
        !            10: /*
        !            11:  * MD5P8 is an MD5-based hash friendly to parallel processing. The input
        !            12:  * stream is divided into 8 independent streams. For each 512 bytes of input,
        !            13:  * the first 64 bytes are send to the first stream, the second 64 bytes to
        !            14:  * the second stream, etc. The input stream is padded with zeros to the next
        !            15:  * multiple of 512 bytes, then a normal MD5 hash is computed on a buffer
        !            16:  * containing the A, B, C, and D states of the 8 individual streams, followed
        !            17:  * by the (unpadded) length of the input.
        !            18:  *
        !            19:  * On non-SIMD accelerated CPUs the performance of MD5P8 is slightly lower
        !            20:  * than normal MD5 (particularly on files smaller than 10 kB), but with
        !            21:  * SIMD-based parallel processing it can be two to six times as fast. Even in
        !            22:  * the best-case scenario, xxHash is still at least twice as fast and should
        !            23:  * be preferred when available.
        !            24:  */
        !            25: 
        !            26: #include "rsync.h"
        !            27: 
        !            28: #ifdef HAVE_SIMD
        !            29: #define MD5P8_Init MD5P8_Init_c
        !            30: #define MD5P8_Update MD5P8_Update_c
        !            31: #define MD5P8_Final MD5P8_Final_c
        !            32: #endif
        !            33: 
        !            34: /* each MD5_CTX needs to be 8-byte aligned */
        !            35: #define MD5P8_Contexts_c(ctx, index) ((MD5_CTX*)((((uintptr_t)((ctx)->context_storage) + 7) & ~7) + (index)*((sizeof(MD5_CTX) + 7) & ~7)))
        !            36: 
        !            37: void MD5P8_Init(MD5P8_CTX *ctx)
        !            38: {
        !            39:     int i;
        !            40:     for (i = 0; i < 8; i++) {
        !            41:         MD5_Init(MD5P8_Contexts_c(ctx, i));
        !            42:     }
        !            43:     ctx->used = 0;
        !            44:     ctx->next = 0;
        !            45: }
        !            46: 
        !            47: void MD5P8_Update(MD5P8_CTX *ctx, const uchar *input, uint32 length)
        !            48: {
        !            49:     uint32 pos = 0;
        !            50: 
        !            51:     if ((ctx->used) || (length < 64)) {
        !            52:         int cpy = MIN(length, 64 - ctx->used);
        !            53:         memmove(&ctx->buffer[ctx->used], input, cpy);
        !            54:         ctx->used += cpy;
        !            55:         length -= cpy;
        !            56:         pos += cpy;
        !            57: 
        !            58:         if (ctx->used == 64) {
        !            59:             MD5_Update(MD5P8_Contexts_c(ctx, ctx->next), ctx->buffer, 64);
        !            60:             ctx->used = 0;
        !            61:             ctx->next = (ctx->next + 1) % 8;
        !            62:         }
        !            63:     }
        !            64: 
        !            65:     while (length >= 64) {
        !            66:         MD5_Update(MD5P8_Contexts_c(ctx, ctx->next), &input[pos], 64);
        !            67:         ctx->next = (ctx->next + 1) % 8;
        !            68:         pos += 64;
        !            69:         length -= 64;
        !            70:     }
        !            71: 
        !            72:     if (length) {
        !            73:         memcpy(ctx->buffer, &input[pos], length);
        !            74:         ctx->used = length;
        !            75:     }
        !            76: }
        !            77: 
        !            78: void MD5P8_Final(uchar digest[MD5_DIGEST_LEN], MD5P8_CTX *ctx)
        !            79: {
        !            80:     int i;
        !            81:     uint32 low = 0, high = 0, sub = ctx->used ? 64 - ctx->used : 0;
        !            82:     if (ctx->used) {
        !            83:         uchar tmp[64];
        !            84:         memset(tmp, 0, 64);
        !            85:         MD5P8_Update(ctx, tmp, 64 - ctx->used);
        !            86:     }
        !            87:     memset(ctx->buffer, 0, 64);
        !            88:     while (ctx->next != 0) {
        !            89:         MD5P8_Update(ctx, ctx->buffer, 64);
        !            90:         sub += 64;
        !            91:     }
        !            92: 
        !            93:     uchar state[34*4] = {0};
        !            94: 
        !            95:     for (i = 0; i < 8; i++) {
        !            96:         MD5_CTX* md = MD5P8_Contexts_c(ctx, i);
        !            97: #ifdef USE_OPENSSL
        !            98:         if (low + md->Nl < low) high++;
        !            99:         low += md->Nl;
        !           100:         high += md->Nh;
        !           101: #else
        !           102:         if (low + md->totalN < low) high++;
        !           103:         low += md->totalN;
        !           104:         high += md->totalN2;
        !           105: #endif
        !           106:         SIVALu(state, i*16, md->A);
        !           107:         SIVALu(state, i*16 + 4, md->B);
        !           108:         SIVALu(state, i*16 + 8, md->C);
        !           109:         SIVALu(state, i*16 + 12, md->D);
        !           110:     }
        !           111: 
        !           112: #ifndef USE_OPENSSL
        !           113:        high = (low >> 29) | (high << 3);
        !           114:        low = (low << 3);
        !           115: #endif
        !           116: 
        !           117:     sub <<= 3;
        !           118:     if (low - sub > low) high--;
        !           119:     low -= sub;
        !           120: 
        !           121:     SIVALu(state, 32*4, low);
        !           122:     SIVALu(state, 33*4, high);
        !           123: 
        !           124:     MD5_CTX md;
        !           125:     MD5_Init(&md);
        !           126:     MD5_Update(&md, state, 34*4);
        !           127:     MD5_Final(digest, &md);
        !           128: }