1
\$\begingroup\$

My implementation of MD5 (hash function) works correctly, though it has terrible performance. As a laboratory work, I must write the algorithm myself and implement the brute force.


full code with simple test:

// Md5CpuSSE2.cpp: identifies entry point of the console program
// VS2015 IDE

#include "stdafx.h"
#include <math.h>
#include <iostream>
#include <string>
typedef unsigned int uint;



__m128i F(__m128i x, __m128i y, __m128i z) { return (_mm_or_si128(_mm_and_si128(x, y), _mm_andnot_si128(x, z))); }
__m128i G(__m128i x, __m128i y, __m128i z) { return (_mm_or_si128(_mm_and_si128(x, z), _mm_andnot_si128(z, y))); }
__m128i H(__m128i x, __m128i y, __m128i z) { return (_mm_xor_si128(_mm_xor_si128(x, y), z)); }
//__m128i I(__m128i x, __m128i y, __m128i z) { return (_mm_xor_si128(y, _mm_or_si128(x, _mm_andnot_si128(z, _mm_set1_epi32(0))))); } //посл сомнительно с нулем
__m128i I(__m128i x, __m128i y, __m128i z) { return _mm_xor_si128((y), _mm_or_si128((x), _mm_andnot_si128((z), _mm_cmpeq_epi32((z), (z))))); }
//__m128i rotate_left(__m128i x, int n)
//{
//  __m128i tmp; 
//  tmp = _mm_srli_epi32(x, 32 - n);
//  x = _mm_slli_epi32(x, n);
//  x = _mm_or_si128(x, tmp);
//  return x;
//}
__m128i rotate_left(__m128i x, int n) { return _mm_or_si128(_mm_slli_epi32((x), (n)), _mm_srli_epi32((x), (32 - (n)))); }



__m128i operator | (__m128i  x, __m128i  y)
{
    //return x + y;
    return _mm_add_epi32(x, y);

}


__m128i operator | (__m128i  x, uint  uy)
{
    //return x + y;
    return _mm_add_epi32(x, _mm_set1_epi32(uy));

}


std::string to_hex(__m128i value)
{
    std::string out;
    unsigned char hex;
    char hex_res[3];
    const int tmp = 0;
    uint val = _mm_extract_epi32(value, tmp);
    while (val)
    {
        hex = val % 256;
        _itoa_s(hex, hex_res, 16);
        if (hex_res[1] == '\0')
        {
            hex_res[1] = hex_res[0];
            hex_res[0] = '0';
            hex_res[2] = '\0';
        }
        out.append(hex_res);
        val /= 256;
    }
    return out;
}


std::string get_md5(std::string in)
{
    int length = in.length();
    int rest = length % 64;
    int size = 0;

    if (rest < 56)
        size = length - rest + 56 + 8;
    else
        size = length + 64 - rest + 56 + 8;

    unsigned char *msg_for_decode = new unsigned char[size];

    for (int i = 0; i < length; i++)
        msg_for_decode[i] = in[i];
    msg_for_decode[length] = 0x80;
    for (int i = length + 1; i < size; i++)
        msg_for_decode[i] = 0;

    __int64 bit_length = (uint)(length) * 8;

    for (int i = 0; i < 8; i++)
        msg_for_decode[size - 8 + i] = (unsigned char)(bit_length >> i * 8);

    __m128i A = _mm_set1_epi32(0x67452301), B = _mm_set1_epi32(0xefcdab89), C = _mm_set1_epi32(0x98badcfe), D = _mm_set1_epi32(0x10325476);
    __m128i T[64];

    for (int i = 0; i < 64; i++)
    {
        auto t = uint(pow(2, 32)*fabs(sin(i + 1)));
        T[i] = _mm_set1_epi32(t); //тут хз мб не все
    }

    uint *X = (uint*)(msg_for_decode);

    __m128i AA = _mm_set1_epi32(0), BB = _mm_set1_epi32(0), CC = _mm_set1_epi32(0), DD = _mm_set1_epi32(0);

    for (int i = 0; i < size / 4; i += 16) {
        AA = A; BB = B; CC = C; DD = D;
        //round 1
        A = B | rotate_left((A | F(B, C, D) | X[i + 0] | T[0]), 7);
        D = A | rotate_left((D | F(A, B, C) | X[i + 1] | T[1]), 12);
        C = D | rotate_left((C | F(D, A, B) | X[i + 2] | T[2]), 17);
        B = C | rotate_left((B | F(C, D, A) | X[i + 3] | T[3]), 22);



        A = B | rotate_left((A | F(B, C, D) | X[i + 4] | T[4]), 7);
        D = A | rotate_left((D | F(A, B, C) | X[i + 5] | T[5]), 12);
        C = D | rotate_left((C | F(D, A, B) | X[i + 6] | T[6]), 17);
        B = C | rotate_left((B | F(C, D, A) | X[i + 7] | T[7]), 22);

        A = B | rotate_left((A | F(B, C, D) | X[i + 8] | T[8]), 7);
        D = A | rotate_left((D | F(A, B, C) | X[i + 9] | T[9]), 12);
        C = D | rotate_left((C | F(D, A, B) | X[i + 10] | T[10]), 17);
        B = C | rotate_left((B | F(C, D, A) | X[i + 11] | T[11]), 22);

        A = B | rotate_left((A | F(B, C, D) | X[i + 12] | T[12]), 7);
        D = A | rotate_left((D | F(A, B, C) | X[i + 13] | T[13]), 12);
        C = D | rotate_left((C | F(D, A, B) | X[i + 14] | T[14]), 17);
        B = C | rotate_left((B | F(C, D, A) | X[i + 15] | T[15]), 22);

        //round 2                               
        A = B | rotate_left((A | G(B, C, D) | X[i + 1] | T[16]), 5);
        D = A | rotate_left((D | G(A, B, C) | X[i + 6] | T[17]), 9);
        C = D | rotate_left((C | G(D, A, B) | X[i + 11] | T[18]), 14);
        B = C | rotate_left((B | G(C, D, A) | X[i + 0] | T[19]), 20);

        A = B | rotate_left((A | G(B, C, D) | X[i + 5] | T[20]), 5);
        D = A | rotate_left((D | G(A, B, C) | X[i + 10] | T[21]), 9);
        C = D | rotate_left((C | G(D, A, B) | X[i + 15] | T[22]), 14);
        B = C | rotate_left((B | G(C, D, A) | X[i + 4] | T[23]), 20);

        A = B | rotate_left((A | G(B, C, D) | X[i + 9] | T[24]), 5);
        D = A | rotate_left((D | G(A, B, C) | X[i + 14] | T[25]), 9);
        C = D | rotate_left((C | G(D, A, B) | X[i + 3] | T[26]), 14);
        B = C | rotate_left((B | G(C, D, A) | X[i + 8] | T[27]), 20);

        A = B | rotate_left((A | G(B, C, D) | X[i + 13] | T[28]), 5);
        D = A | rotate_left((D | G(A, B, C) | X[i + 2] | T[29]), 9);
        C = D | rotate_left((C | G(D, A, B) | X[i + 7] | T[30]), 14);
        B = C | rotate_left((B | G(C, D, A) | X[i + 12] | T[31]), 20);

        //round 3                               
        A = B | rotate_left((A | H(B, C, D) | X[i + 5] | T[32]), 4);
        D = A | rotate_left((D | H(A, B, C) | X[i + 8] | T[33]), 11);
        C = D | rotate_left((C | H(D, A, B) | X[i + 11] | T[34]), 16);
        B = C | rotate_left((B | H(C, D, A) | X[i + 14] | T[35]), 23);

        A = B | rotate_left((A | H(B, C, D) | X[i + 1] | T[36]), 4);
        D = A | rotate_left((D | H(A, B, C) | X[i + 4] | T[37]), 11);
        C = D | rotate_left((C | H(D, A, B) | X[i + 7] | T[38]), 16);
        B = C | rotate_left((B | H(C, D, A) | X[i + 10] | T[39]), 23);

        A = B | rotate_left((A | H(B, C, D) | X[i + 13] | T[40]), 4);
        D = A | rotate_left((D | H(A, B, C) | X[i + 0] | T[41]), 11);
        C = D | rotate_left((C | H(D, A, B) | X[i + 3] | T[42]), 16);
        B = C | rotate_left((B | H(C, D, A) | X[i + 6] | T[43]), 23);

        A = B | rotate_left((A | H(B, C, D) | X[i + 9] | T[44]), 4);
        D = A | rotate_left((D | H(A, B, C) | X[i + 12] | T[45]), 11);
        C = D | rotate_left((C | H(D, A, B) | X[i + 15] | T[46]), 16);
        B = C | rotate_left((B | H(C, D, A) | X[i + 2] | T[47]), 23);

        //round 4                               2(  
        A = B | rotate_left((A | I(B, C, D) | X[i + 0] | T[48]), 6);
        D = A | rotate_left((D | I(A, B, C) | X[i + 7] | T[49]), 10);
        C = D | rotate_left((C | I(D, A, B) | X[i + 14] | T[50]), 15);
        B = C | rotate_left((B | I(C, D, A) | X[i + 5] | T[51]), 21);

        A = B | rotate_left((A | I(B, C, D) | X[i + 12] | T[52]), 6);
        D = A | rotate_left((D | I(A, B, C) | X[i + 3] | T[53]), 10);
        C = D | rotate_left((C | I(D, A, B) | X[i + 10] | T[54]), 15);
        B = C | rotate_left((B | I(C, D, A) | X[i + 1] | T[55]), 21);

        A = B | rotate_left((A | I(B, C, D) | X[i + 8] | T[56]), 6);
        D = A | rotate_left((D | I(A, B, C) | X[i + 15] | T[57]), 10);
        C = D | rotate_left((C | I(D, A, B) | X[i + 6] | T[58]), 15);
        B = C | rotate_left((B | I(C, D, A) | X[i + 13] | T[59]), 21);

        A = B | rotate_left((A | I(B, C, D) | X[i + 4] | T[60]), 6);
        D = A | rotate_left((D | I(A, B, C) | X[i + 11] | T[61]), 10);
        C = D | rotate_left((C | I(D, A, B) | X[i + 2] | T[62]), 15);
        B = C | rotate_left((B | I(C, D, A) | X[i + 9] | T[63]), 21);

        /*A += AA;
        B += BB;
        C += CC;
        D += DD;*/

        A = A | AA;
        B = B | BB;
        C = C | CC;
        D = D | DD;

    }

    delete[]msg_for_decode;
    std::string res = to_hex(A) + to_hex(B) + to_hex(C) + to_hex(D);
    return res;
}





int main()
{
    std::string md5result = get_md5("911");

    if (md5result == "b56a18e0eacdf51aa2a5306b0f533204")
    {
        bool good = true;
    }
    else
    {
        bool good = false;
    }


    return 0;
}

My concerns about the code are:

  • Ridiculous speed. For comparison, other SSE2 solution run with a speed of 250M p/s, but my solution only 0.8M p/s that is ridiculous). I have no idea why my implementation behaves this way.

  • General C++ style

  • Readability

  • Misc

\$\endgroup\$
  • 2
    \$\begingroup\$ Did you profile? Also, non English code/comments are really not appreciated. \$\endgroup\$ – Emily L. Jul 12 '17 at 8:09
  • 1
    \$\begingroup\$ Those SSE names look like they come straight from unreadable code hell... \$\endgroup\$ – Graipher Jul 12 '17 at 8:11
  • \$\begingroup\$ The algorithm itself is pretty simple, I do not consider it necessary to make comments in the code. Forgive me, but I'm just learning, I do not know how to profile and there is no one to show me how to do it( \$\endgroup\$ – beatsspam Jul 12 '17 at 8:23
  • \$\begingroup\$ I've translated the russian comments into english, I hope you don't mind. \$\endgroup\$ – Incomputable Jul 12 '17 at 12:39
  • \$\begingroup\$ Thank you, you have put in order. Now more chances to get an answer) \$\endgroup\$ – beatsspam Jul 12 '17 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.