Educational Source Code

Moderator: BarsMonster

Post Reply [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
EnabrenTane
Posts: 3
Joined: Wed Jan 13, 2010 7:11 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Educational Source Code

Post by EnabrenTane » Sun Mar 14, 2010 11:28 am

A while back you mentioned you might post unoptimized versions of source code. My largest interest is how you did the "job queue"

You could either have a centralized job queue that you refilled each thread launch, but that would be slow and limited by the CPU. You could also give each thread a "stride" so if it found its current string "A" didn't match, it would add "A" + NUM_THREADS and rehash that. value.

If you did strides then you would need a fairly advanced class to figure out the next message since you use character sets.

I would imagine you have constants for characters sets and you initialize the object(s) with the character sets that were passed in ARGV. They then figure out what the next character would be, if they had a carry, and if they needed to grow based on the carry.

Anyway...

There are many ways to do it, some better, some easier. I'm curious what your general architecture to schedule jobs is. As a side project I've been writing a SHA-1 brute forcer using OpenCL. (parts in Ruby parts in C )

Hopefully you can share,
Tane

User avatar
BarsMonster
Site Admin
Posts: 1118
Joined: Wed Oct 01, 2008 7:58 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Educational Source Code

Post by BarsMonster » Sun Mar 14, 2010 11:58 am

Well, my password generation class is being called each time when any thread need new working set.
It's being called from different threads, so there obviously must be a mutex.

It returns range of keys for each request (with like few millions of keys).
It does not return each individual key, just range boundaries, so it takes far less than 1% of CPU time to handle both CPU's and GPU's requests.

Next possible optimization is to allocate HUGE working sets for each thread, so that we can save of mutexes which are pretty slow.

EnabrenTane
Posts: 3
Joined: Wed Jan 13, 2010 7:11 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Educational Source Code

Post by EnabrenTane » Sun Mar 14, 2010 8:04 pm

So then it sounds like you have something of the following structure


// using this-> for clarity
bool done()
{
// value == md5_hash(message)
return this->value == TARGET_HASH;
}

void do()
{
while( this->message != this->range_end) // something like this each thread
{
// this->message is a string "A" and range_end is "zzzz"
this->message != this->range_end)
{
md5_digest(message); // hash it
++message;// "A" -> "B"
}
get_mutex(&mutex);
get_next_job_range();
release_mutex(&mutex);
}

while(!done()) //Something like this in main()
{
// Here you have an array of jobs and launch the thread wave
launch_jobs(&job_array,job->do());
}


The change you could try would be going from
get_mutex(&mutex);
get_next_job_range();
release_mutex(&mutex);

to

void next_job(){
this-> message += NUM_THREADS; // I.E if NUM_THREADS == 32. "A" -> "a"
}

That would eliminate the need for a mutex. However from experience. implementing this->message + int is much harder than this->message++. I am not sure if you could make operator+ faster ( or as fast ) as your operator++(). The other advantage is that you would never have to tear down and rebuild your message class. You would generate the number equal to the optimum thread count, and they would stay there until done. Construction and deconstruction time can be expensive.


I am still very interested in the source code for your password generation class. I have implimented operator++ and operator+ from string wrapper classes, and it was not easy. I had problems with operator+ when adding numbers larger than 2^32 - 1, even if they were compile time constants. C example:

#define MAX_VAL (((1 << (this->length * 8))) /* 8 == sizeof(unsigned char) * 8 bits */
typedef struct Object {
void (* add )(struct Object * , int);
float (*value)(struct Object *);
unsigned char * data;
int length;
} Object;

void add(struct Object * this, unsigned int amount)
{
/* other lines of code */
if(new_value >= MAX_VAL)
{
/* Tane - Calculate how much we need to grow by to accomodate the additive */
while(new_value > (MAX_VAL << ((amount_to_grow) * 8)))
{
++amount_to_grow;
printf("New max will be: %u\n", MAX_VAL << ((amount_to_grow) * 8)); /* DEBUG */
}
grow(this,amount_to_grow);
}
/* other lines of code */
}

When the length grew too long it would only pick up the bottom 4 bytes of MAX_VAL

Thanks,
Tane

P.S.
Code from here until lunch time :)

Sc00bz
Posts: 136
Joined: Fri Oct 03, 2008 8:28 am
Contact:

Re: Educational Source Code

Post by Sc00bz » Mon Mar 15, 2010 1:47 am

EnabrenTane wrote:void next_job(){
this-> message += NUM_THREADS; // I.E if NUM_THREADS == 32. "A" -> "a"
}

That would eliminate the need for a mutex. However from experience. implementing this->message + int is much harder than this->message++. I am not sure if you could make operator+ faster ( or as fast ) as your operator++(). The other advantage is that you would never have to tear down and rebuild your message class. You would generate the number equal to the optimum thread count, and they would stay there until done. Construction and deconstruction time can be expensive.
This is a bad idea since it will waste more time than mutexes as some threads will finish before others do. This is caused by other programs running in the background and other things too.

EnabrenTane
Posts: 3
Joined: Wed Jan 13, 2010 7:11 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Educational Source Code

Post by EnabrenTane » Mon Mar 15, 2010 2:04 am

@scoobz

I didn't convey the thought very well. The point is that you would leave the threads running continuously, each thread would know the next task. This would allow them to operate asynchronously as Nvidia encourages for optimal performance. When a thread found the matching key, they would modified a shared global variable or generate a software interrupt.

Given the following example.

thread_id = 7
Num_threads = 1024

first_job = 7
next_job = 1024 + 7
next_job = 1024 + 1024 + 7

I.E.
the jobs for a threads life time would be given by
Sigma (thread_id + i * Num_threads) for all integer values of i.

One could consider the number of threads the "stride" opposed a thread has a current "range"

Naturally the implementation would be more complex, but thats the basic architecture.

Tane

Post Reply
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Who is online

Users browsing this forum: No registered users and 1 guest