Kleines Bruteforce-Programm in C

[nufan]

Schade ^^
Wenn du die Länge des Strings schon in der aufrufenden Funktion kennst, ist es vielleicht schneller sie direkt mitzugeben, als jedes mal strlen() aufzurufen.

Wie siehts mit meiner Generierungs-Funktion aus?

[3VAD_YNCAL]

Schade ^^
Wenn du die Länge des Strings schon in der aufrufenden Funktion kennst, ist es vielleicht schneller sie direkt mitzugeben, als jedes mal strlen() aufzurufen.

Wie siehts mit meiner Generierungs-Funktion aus?

Okay, also anstatt strlen() einfach 16. Werde ich ausprobieren. Mit deiner Generierungs-Funktion fange ich jetzt an.
Werde aber vielleicht später deine Hilfe benötigen mit openmp.

Meine main()-Funktion sieht gerade so aus:

Code: Alles auswählen

int main( void )
{
    time( &zeit1 );

    #pragma omp parallel default( shared )
    for( int len = 0; len < 9; ++len ) /* Max. Länge der Passwörter */
    {
	int erster_eingang[len], letzter_eingang[len];

	for( int j = 0; j < len; ++j )
	    erster_eingang[j] = letzter_eingang[j] = 0;

	#pragma omp for schedule( dynamic, 2 )
	for( int i = 0; i < nbzeichen; ++i )
	{
	    erster_eingang[0]  = i;
	    letzter_eingang[0] = i + 1;
	    brute_force( erster_eingang, letzter_eingang, len, md5_hash );
	}
    }

    time( &zeit2 );

    printf( "!!! Passwort nicht gefunden !!!\n" );
    printf( "Elapsed time: %ld minutes %ld seconds.\n\n", ( zeit2 - zeit1 ) / 60, ( zeit2 - zeit1 ) % 60 );

    return EXIT_FAILURE; /* NICHT GEFUNDEN !!! */
}

[nufan]

Okay, also anstatt strlen() einfach 16.

Nein ^^ Dein String den du ausprobierst ist doch nicht 16 Zeichen lang, oder?

Werde aber vielleicht später deine Hilfe benötigen mit openmp.

Davon hab ich zwar wenig Ahnung, aber mal sehen ^^
Soweit ich mich erinnere, behandeln diese Videos OpenMP: http://www.dailymotion.com/playlist/x1p ... deo=xksoje

[3VAD_YNCAL]

Oh sorry, klar nicht 16 sondern 6. Kleiner Denkfehler.
Deine Funktion ist übrigens ziemlich cool. Habe es erst mal so getestet.

Danke für den Link.

[3VAD_YNCAL]

Habe mal deine Funktion mit meiner verglichen. Deine ist ganz schön schnell.
Für das Wort 'testi' braucht deine 54 Sekunden. Meine mit openmp 35 Sekunden.

[nufan]

Habe mal deine Funktion mit meiner verglichen. Deine ist ganz schön schnell.
Für das Wort 'testi' braucht deine 54 Sekunden. Meine mit openmp 35 Sekunden.

Wie meinst du das genau? Meine Funktion braucht auf einem Prozessor 54 Sekunden und deine auf mehreren (wie vielen?) 35? Vielleicht kann ich sie umschreiben, dass man sie parallelisieren kann...

[3VAD_YNCAL]

Wie meinst du das genau? Meine Funktion braucht auf einem Prozessor 54 Sekunden und deine auf mehreren (wie vielen?) 35? Vielleicht kann ich sie umschreiben, dass man sie parallelisieren kann...

Ja mach das Mal. Ich war auch ganz erstaunt. Teste es gerade auf meinem Notebook mit einem Intel i5-2430M, 2.4 GHz. Ist ein Dual-Core der dank HT oder SMT noch zwei weitere Kerne simuliert.

[nufan]

Teste es gerade auf meinem Notebook mit einem Intel i5-2430M, 2.4 GHz. Ist ein Dual-Core der dank HT oder SMT noch zwei weitere Kerne simuliert.

War das ein "Ja"? ^^ Wie lange braucht denn dein Code ohne OpenMP? Dein Code ist zwar aufwändiger, aber auch deutlich leichter zu parallelisieren...

[3VAD_YNCAL]

War das ein "Ja"? ^^ Wie lange braucht denn dein Code ohne OpenMP? Dein Code ist zwar aufwändiger, aber auch deutlich leichter zu parallelisieren...

Ja - deine brauchte nur 19 Sekunden weniger (auf einem Kern) als meine 'mit Parallelisierung mittels openmp' .
Gute Idee, ich glaube, dass ich das noch gar nicht ausprobiert habe. Teste ich nachher gleich. Ich poste dann das Ergebnis.

Alles klar - meine braucht ohne openmp für das Wort 'testi' 1 min. und 33 sek. D.h. deine Funktion ist deutlich schneller.

[nufan]

War das ein "Ja"? ^^ Wie lange braucht denn dein Code ohne OpenMP? Dein Code ist zwar aufwändiger, aber auch deutlich leichter zu parallelisieren...

Ja - deine brauchte nur 19 Sekunden weniger (auf einem Kern) als meine 'mit Parallelisierung mittels openmp' .

Naja das ist doch ne ganze Menge ^^

Alles klar - meine braucht ohne openmp für das Wort 'testi' 1 min. und 33 sek. D.h. deine Funktion ist deutlich schneller.

Ja, aber deine kann man viel schöner parallelisieren. Ich hab zwar von der Struktur her ein viel einfacheres Programm, aber viele deiner Iterationen sind unabhängig von einander, was man dann natürlich schön parallelisieren kann. Ich brauche schon einen Mehraufwand, um eine Parallelisierung überhaupt möglich zu machen.

Ich hab mal versucht meinen Code für OpenMP aufzubereiten... Ich hab das nicht getestet oder kompiliert, eventuell musst du noch wo nachbessern ^^

Code: Alles auswählen

static char pool[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
static const int maxPoolIndex = sizeof( pool ) - 2;
static const int maxLength = 50;
static char str[maxLength];
static char strCpy[maxLength];
static int poolIndex[maxLength];
static char *strIt;
static int *indexIt;

void crack( int length )
{
  static int oldLength = length;
  ++length;
  #pragma omp sections
  {
    #pragma omp section
    {
      memset( str, '0', length );
    }
    #pragma omp section
    {
      memset( strCpy, '\0', length );
    }
    #pragma omp section
    {
      memset( poolIndex, 0, length * sizeof( int ) );
    }
    #pragma omp section
    {
      static char *last = str + oldLength;
    }
  }

  while( *last == '0' ) 
  {
    memcpy( strCpy, str, oldLength );
    #pragma omp task
    {
      //////////////////////////////////////
      // do stuff...
        fprintf( stdout, "%s\n", strCpy );
      //////////////////////////////////////
    }
    #pragma omp sections
    {
      #pragma omp section
      {
        *str = pool[++( *poolIndex )];
      }
      #pragma omp section
      {
        strIt = str;
        indexIt = poolIndex;
      }
    }
    while( *indexIt > maxPoolIndex ) 
    {
      #pragma omp sections
      {
        #pragma omp section
        {
          *strIt = '0';
          ++strIt;
        }
        #pragma omp section
        {
          *indexIt = 0;
          ++indexIt;
          ++( *indexIt );
        }
      }
      *strIt = pool[*indexIt];
    }
  }
}

An der Stelle "do stuff..." musst du natürlich noch die Hash-Funktion aufrufen. Du kannst auch mal versuchen nur "do stuff..." mit OpenMP aufzurufen. Die anderen Anweisungen sind alle sehr klein, eventuell ist da der Overhead schon zu hoch.
Kannst du bitte vielleicht mal zwischendurch den schnellsten Code mit Kompilier-Anweisungen posten, damit hier wieder alle auf dem gleichen Stand sind?

Der nächste Schritt wäre es das übers Netzwerk zu verteilen ^^ Ich kann mir schon gut vorstellen, was unser nächstes Community-Projekt wird, wenn Dedupe irgendwann mal fertig ist... ^^
Die Latte liegt übrigens hoch: http://toolsyard.thehackernews.com/2012 ... speed.html