Jump to content
Tuts 4 You

Concurrency threads problems

CodeExplorer

By CodeExplorer
in Programming and Coding

Recommended Posts

CodeExplorer

CodeExplorer

Posted
Posted

Concurrency threads problems...
Having this code:
  

int BruteForceFunction(void * BruteWayPtr)
{
int BruteWay = *(int*)BruteWayPtr;
printf("Brute way = %d\r\n", BruteWay);
time_t _tm = time(NULL);
struct tm * curtime = localtime (&_tm);
printf("start time %s\r\n", asctime(curtime));

	KnowSum = 0;
	unsigned int A = 1;
	unsigned int B = 2;
	unsigned int C = 3;
	unsigned int D = 4;
	unsigned int M[8] = {0x11111111, 0x22222222, 0x33333333, 4, 5, 0, 0, 0x33333333};  // 7FFFFFFF max int
	unsigned int Mn[8];
	unsigned int F = 0;  // {0x1, 0x2, 0x3, 4, 5, 0, 0, 0x92222222};
	unsigned int B_a[8];
// {0x11111111, 0x22222222, 0x33333333, 4, 5, 0, 0, 9999};
// {0x1, 0x2, 0x3, 4, 5, 0, 0, 0xFFFFFFFE}; - takes lot of time also 0xEFFFFFFE
	printf("Initial values:\n");
	printf("A = %d\n", A);
	printf("B = %d\n", B);
	printf("C = %d\n", C);
	printf("D = %d\n\n", D);


	for (int i=0;i<8;i++)
	{
	printf("i = %d\n", i);
	F = C xor (B or (not D));  // first time we calculate the operation in F
 // F = B[i-1] xor (B[i] or (not B[i-2]))
	printf("Operation F = %d\n", F);
	printf("M[%d] = %d\n", i, M[i]);

	unsigned int known_sum = A+M[i];
	printf("A+M[i] = %d\n", known_sum);

	F = F+A+M[i];  // A = B[i-3]
	printf("F = %d\n", F);
	printf("A = %d\n", A);
	printf("B = %d\n", B);
	printf("C = %d\n", C);
	printf("D = %d\n", D);

	if ((i-3)>=0)
	{
	if (A!=B_a[i-3])  // A value is lost!!!
	printf("IMPOSSIBLE!!!\n");
	}
	
	if ((i-2)>=0)
	{
	if (D!=B_a[i-2])
	printf("IMPOSSIBLE!!!\n");
	}

	if ((i-1)>=0)
	{
	if (C!=B_a[i-1])
	printf("IMPOSSIBLE!!!\n");

	}

	A = D;
	D = C;
	C = B;

	B_a[i] = B;
	printf("B[%d] = %d\n", i, B);

	printf("F bef. rotate = %d\n", F);
	unsigned int lr_val = leftrotate(F, s[i]);
	printf("lr_val = %d\n", lr_val);
	printf("B bef = %d\n", B);

	B = B + lr_val;
	printf("B after = %d\n\n", B);
	}

	printf("Final values:\n");
	printf("A = %d\n", A);
	printf("B = %d\n", B);
	printf("C = %d\n", C);
	printf("D = %d\n\n", D);

	unsigned int lr_values_1 = B-C;  // lr_value for last round
	printf("lr_values_1= %d\n", lr_values_1);

	unsigned int lr_values_2 = C-D;  // lr_value for ante-last round
	printf("lr_values_2= %d\n", lr_values_2);

	unsigned int lr_values_3 = D-A;  // lr_value for ante-ante-last round
	printf("lr_values_3= %d\n", lr_values_3);

	unsigned int F_1 = rightrotate(lr_values_1, s[8-1]);
	printf("F_1= %d\n", F_1);
	unsigned int F_2 = rightrotate(lr_values_2, s[8-2]);
	printf("F_2= %d\n", F_2);
	unsigned int F_3 = rightrotate(lr_values_3, s[8-3]);
	printf("F_3= %d\n", F_3);

	int B_old1 = B-lr_values_1;  // B[7]
	// C = D and D = A;
	int F_x1 = D xor (B_old1 or (not A));  // operation on last round
	int know_sum1 = F_1-F_x1;

	printf("A[%d]+M[%d] = %d \n\n", 8-1, 8-1, know_sum1);

	// where A is B computed at the end of i = 3 = round 4:
	// that means that A depends on M[0], M[1], M[2] and M[3]
	// in this specific case we have 8 dword of messages and only 4 dwords of hash
	// so 8*4 = 32 bytes of message over 4*4 = 16 bytes of hash
	// as result we have many 32 bytes messages which would generate same hash!!!
	// How we proceed: we choose (random) M[0], M[1], M[2] and M[3]
    // and we calculate M[4], M[5], M[6] and M[7]

	unsigned int Ban[8];

	// Just initial values of A, B, C, D:
	unsigned int An = 1;
	unsigned int Bn = 2;
	unsigned int Cn = 3;
	unsigned int Dn = 4;

	for (int i=0;i<1;i++)  // compute Ban[0]
	{
	F = Cn xor (Bn or (not Dn));
	F = F+An+Mn[i];

	An = Dn;
	Dn = Cn;
	Cn = Bn;

	Ban[i] = Bn;
	Bn = Bn + leftrotate(F, s[i]);

	// B[0] is calculated only from intial values!!!
	// B[1] depends on M[0]
	// B[2] depends on B[1] and M[1]
	// .... 
	}

	// Just initial values of A, B, C, D:
	An = 1;
	Bn = 2;
	Cn = 3;
	Dn = 4;

	unsigned int F1,F2,F3,F_x4;
	unsigned int dif1_div, dif2_div, dif3_div, dif4_div;

	// -----------------------------------------
	printf("\nThird way: random M[3], M[4], M[5] and M[6]\n");
	printf("Calculated M[0], M[1], M[2] and M[7]\n");

	Mn[3] = 4;
	Mn[4] = 5;
	Mn[5] = 0;
	Mn[6] = 0;

	// Ban[0] is known
	Ban[7] = B_old1;
	Ban[6] = Ban[7]-lr_values_2;  // B_old2
	Ban[5] = Ban[6]-lr_values_3;  // B_old3

	// We make some M[5] and M[6] substractions making calculations like if M[5]=0 and M[6]=0
	// For original MD5 these are not needed!!!
	unsigned int lr_values_2_Clean = lr_values_2-leftrotate(M[6], s[6]);
	unsigned int lr_values_3_Clean = lr_values_3-leftrotate(M[5], s[5]);

	// The final value after adding operation, A and M[i]
	unsigned int F_2_Clean = rightrotate(lr_values_2_Clean, s[6]);
	unsigned int F_3_Clean = rightrotate(lr_values_3_Clean, s[5]);

	// We clean final C (Ban[7]) by substracting leftrotate(M[6], s[6]) and leftrotate(M[5], s[5])
	unsigned int Ban7_Clean = Ban[7]-leftrotate(M[6], s[6])-leftrotate(M[5], s[5]);
	unsigned int Ban6_Clean = Ban7_Clean-lr_values_2_Clean;
	unsigned int Ban5_Clean = Ban6_Clean-lr_values_3_Clean;

	unsigned int F_1_Clean = Ban6_Clean xor (Ban7_Clean or (not A));  // operation on last round
	unsigned int F1_Clean_mul = leftrotate(F_1_Clean, s[7]);
	unsigned int F1_mul = leftrotate(F_x1, s[7]);

	unsigned int B_final = B-(F1_mul-F1_Clean_mul)-(Ban[7]-Ban7_Clean);
	// lr_values_1_Clean depends on M[7]
	unsigned int lr_values_1_Clean = lr_values_1-(F1_mul-F1_Clean_mul);
	F_1 = rightrotate(lr_values_1_Clean, s[8-1]);  // i = 7;
	F_x1 = Ban6_Clean xor (Ban7_Clean or (not A));  // operation on last round
	know_sum1 = F_1-F_x1;
	printf("B[4]+M[7] = %d \n", know_sum1);  // B[4] and M[7] relations
	// B[4] is computed from M[0], M[1] and M[2]

unsigned int lr_val1_bak = 0;
unsigned int Ban1Test = 0;
unsigned int lr_val2_bak = 0;
unsigned int Ban2Test;
unsigned int lr_val3_bak = 0;
unsigned int Ban3Test = 0;

	int IsFound = 0;
	// The trick is to substract from know_sum1 the Ban[0]
	unsigned int know_sum1_B0 = (Cn xor (Bn or (not Dn)))+An;
	unsigned int MultiPly = leftrotate(know_sum1_B0, s[0])+Bn;  // Bn is just B initial value
	unsigned int know_sum1_NoB0F = know_sum1-MultiPly;
	// i=1: A = 4, 3, 2 = D, C, B =>
	know_sum1_NoB0F -= leftrotate(Dn, s[1]);  // i = 1
	know_sum1_NoB0F -= leftrotate(Cn, s[2]);  // i = 2
	know_sum1_NoB0F -= leftrotate(Bn, s[3]);  // i = 3

	know_sum1_NoB0F -= leftrotate(Mn[3], s[3]);  // i = 3
	printf("knowSum NoB0 = %d \n", know_sum1_NoB0F);

	// Just initial values of A, B, C, D:
	unsigned int Al = 1;
	unsigned int Bl = 2;
	unsigned int Cl = 3;
	unsigned int Dl = 4;

	unsigned int F_x4_Orig = 0;
	unsigned int Lr_value_4_New = 0;
	unsigned int F4_Hot = 0;


	// lr_values_1_Clean - last round: i = 7

	// on ante-last round:
	F_2 = _rotr(lr_values_2_Clean, s[6]);  // i = 6
	F_3 = _rotr(lr_values_3_Clean, s[5]);  // i = 5

	F1 = (Cn xor (Bn or (not Dn)))+An;
	int Count = 0;

/* From the sum result: Ban[4]+Mn[7] = know_sum1:
Mn[7] start value = know_sum1 and they are two options:
A. substract 1 and gows until at zero
B. add 1 and gows until at int max value
Sometimes A. find a value is seconds; sometimes B.
*/

	//Mn7Val1 = total;
	Mn[7]=know_sum1;
	KnowSum = know_sum1;

	while (Mn[7]!=0)
	{
	if (BruteWay==1)
	{
	M7Brute1 = Mn[7];
	Mn[7]--;
	}
	else
	{
	M7Brute2 = Mn[7];
	Mn[7]++;
	}

	
	Ban[4] = know_sum1-Mn[7];

	// on ante-last round i = 6:
	Ban[3] = F_2-(A xor (Ban6_Clean or (not Ban[4])));  // since Mn[6]=0

	// on round i = 5:
	Ban[2] = F_3-(Ban[4] xor (Ban5_Clean or (not Ban[3])));  // since Mn[5]=0

	// On round i = 4:
	F_x4 = (Ban[3] xor (Ban[4] or (not Ban[2])));
	F_x4_Orig = _rotr(Ban5_Clean-Ban[4], s[4]);
	Ban[1] = F_x4_Orig-F_x4-Mn[4];  // Mn[4] is known

	// On round i = 3:
	dif4_div = _rotr(Ban[4]-Ban[3], s[3]);
	F4_Hot = (Ban[2] xor (Ban[3] or (not Ban[1])))+Bn;
	if (Mn[3]!=(dif4_div-F4_Hot)) continue;  // sanity check for round with i=3

	// Calculation of Mn[0]-Mn[3] (messages)
	dif1_div = _rotr(Ban[1]-Ban[0], s[0]);
	Mn[0] = dif1_div-F1;

	/*F1 += Mn[0]; // add the already computed Mn[0] value
	lr_val1_bak = leftrotate(F1, s[0]);
	Ban1Test = Ban[0]+lr_val1_bak;
	if (Ban[1]!=Ban1Test)
		{
			printf("WTF!!!\n");
			Count++;
			continue;
		}
	*/

	dif2_div = _rotr(Ban[2]-Ban[1], s[1]);
	F2 = (Bn xor (Ban[1] or (not Cn)))+Dn;  // 	F = C xor (B or (not D));
	
	Mn[1] = dif2_div-F2;

	/*
	F2 += Mn[1]; // add the already computed Mn[1] value
	lr_val2_bak = leftrotate(F2, s[1]);
	Ban2Test = Ban[1]+lr_val2_bak;
	if (Ban[2]!=Ban2Test)
	{
			printf("WTF!!!\n");
			Count++;
			continue;
	}
	*/

	dif3_div = _rotr(Ban[3]-Ban[2], s[2]);
	F3 = (Ban[1] xor (Ban[2] or (not Bn)))+Cn;
	Mn[2] = dif3_div-F3;


	/*
	F3 += Mn[2]; // add the already computed Mn[2] value
	lr_val3_bak = leftrotate(F3, s[2]);
	Ban3Test = Ban[2]+lr_val3_bak;
	if (Ban[3]!=Ban3Test)
	{
			printf("WTF!!!\n");
			Count++;
			continue;
	}
	*/

	// Just initial values:
	Al = 1;
	Bl = 2;
	Cl = 3;
	Dl = 4;

	for (int j=0;j<8;j++)
	{
	F = Cl xor (Bl or (not Dl));
	F = F+Al+Mn[j];
	Al = Dl;
	Dl = Cl;
	Cl = Bl;
	Bl = Bl + _rotl(F, s[j]);

	}

	if ((Al!=A)||(Bl!=B)||(Cl!=C)||(Dl!=D))
	{
	continue;
	}
	else
	{
	IsFound = 1;
	break;
	}

	}

	time_t _tm_end = time(NULL);
    curtime = localtime (&_tm_end);
	printf("end time %s", asctime(curtime));

	double dif = difftime (_tm_end,_tm);
	printf ("Elapsed time is %.2lf seconds.\n", dif );

	if (IsFound==1)
	{  	// We finnaly have M[0], M[1], M[2] values
	printf("Brute way = %d\r\n", BruteWay);
	printf("M[7] = %d \n", Mn[7]);
	printf("M[0] = %d \n", Mn[0]);
	printf("M[1] = %d \n", Mn[1]);
	printf("M[2] = %d \n", Mn[2]);
	return 1;
	}
	else
	{
	printf("Failed to find M[7] value!!!\n");
	return 0;
	}

}


And creating a thread for BruteWay1 = 2:

KnowSum = 0;
mRes = timeSetEvent(10, 0, &TimerProc, 0, TIME_PERIODIC);

int BruteWay1 = 2;
thrd_t thread;
if (thrd_create(&thread, BruteForceFunction, &BruteWay1) != thrd_success)
printf("th thread create error\n");

int BruteWay2 = 1;
BruteForceFunction(&BruteWay2);

What happens here is that "Brute way = 1" stacks at "99%" and is only executed after "BruteWay1 = 2" is finished.
I don't understand the reason; at start everything seems to works like it should.
The CPU usage over threads with ProcessExplorer.zip shows similar usage (~50%).
Also for other examples I've noticed that with 1 thread it took 4 seconds and with two threads it took 7 seconds;
shouldn't these values have appropriate values or even the same after all I have two CPU cores???

 

 

Link to comment
Progman

Progman

Posted
Posted

Maybe the printf statements are causing the other thread to always yield while one always keep printing new messages as to prevent text interleave it must wait until the end of the buffer is safe to write to and not locked, but then it just keeps ending up waiting again since the code on the first thread only yields to the second in printf which is what is blocking it.  I am not sure but it seems like this is the case here as there is no other synchronization.

Link to comment
CodeExplorer

CodeExplorer

Posted
  • Author
Posted (edited)

It doesn't have anything to do with printf statements,
I was also wrong: the program doesn't stacks at 99% is just slow, way to slow then I was expected,

Comparing speed time:
two threads elapsed 38/37 seconds
single thread 41 seconds

Way too humble difference, after all my CPU has two cores.
 

Edited by CodeExplorer
Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Go to topic listing
×
×
  • Create New...