Unrar Kütüphanesiyle Paralel Şifre Bulucu #3

Herşeyden önce Soma'daki kömür madeni kazasından ötürü herkese baş sağlığı dileyerek başlıyorum.

Birşeyler yazmayalı ve yayınlamayalı çok uzun zaman olmuştu. Bu zaman zarfında, bilgisayarı yenileyince başta Euro Truck Simulator gibi her erkeğin hayali olan saçma sapan oyunlar yada eski bilgisayarımda çalışmayan ve uzun zamandır oynamak istediğim oyunlardan dolayı hemen hiçbirşey yapmadığım gibi yazmaya da zaman ayırmadım. O nedenle neredeyse üzerinden bir yıl geçecek olan yazı dizisine hiçbirşey olmamış gibi devam ediyorum. Bir de 4-5 hafta sonrasına yazılması gereken bir rapor var, onu yazmamak için blog yazayım dedim.

Önce seri sürümünün kodunu açıklayacağım. Daha önceki yazılarda da söyledim, benim yazdığım seri sürümden çok daha iyi (ve hızlı) sürümler internette de bulunabilir. Benim yaptığım tek yenilik sözlük dosyasını bilgisayarlar arasında bölüp işlemi paralelleştirmek oldu.

Kodla ilgili açıklamaları yine kodun içerisinde açıklama satırlarında yaptım. Bölük pörçük olmaması için kodu bölen başka bir açıklama girmeyeceğim. Uzun yorum satırları bölünmesin diye karakter boyutunu küçülttüm. İnceleyecek olan zaten kodu Notepad++ yada gedit gibi bir programda inceleyebilirse daha iyi olur.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

// unrar kutuphanesine ait header dosyalari
#include<raros.hpp>
#include<dll.hpp>


void DosyaCoz(char *arsiv, int sira)    {
    // dosya adlari acik, dosya sifreliyse cozme islemi
    HANDLE PASCAL hArsiv;
    struct RAROpenArchiveData *AcmaVerisi;    // RAR dosyayla ilgili veriler
    struct RARHeaderData *Baslik;    // RAR icerisindeki dosyalarla ilgili veriler
    char sozluk[] = "sozluk.txt";    // sozluk.txt denenecek kelimelerin oldugu dosya
    char kelime[256];
    FILE *hDosya;
    int status, k1, k2 = 0;

    hDosya = fopen(sozluk, "r");

    AcmaVerisi = (struct RAROpenArchiveData *)malloc(sizeof(struct RAROpenArchiveData));
    Baslik     = (struct RARHeaderData *)malloc(sizeof(struct RARHeaderData));

    while(!feof(hDosya))        {
    // sozlukten bir kelime oku
        fscanf(hDosya, "%s", kelime);

    // RAR kutuphanesinin dosya acmak icin kullandigi yapi
        AcmaVerisi->ArcName    = arsiv;
        AcmaVerisi->OpenMode   = RAR_OM_EXTRACT;
        AcmaVerisi->CmtBuf     = NULL;
        AcmaVerisi->CmtBufSize = 0;

    // RAR dosyasini ac.
        hArsiv = RAROpenArchive(AcmaVerisi);
        Baslik->CmtBuf   = NULL;

        for(k1 = 0; k1 < (sira - 1); k1++)    {
            // ilk sifreli dosyaya kadar oku, yalnizca bazi dosyalar sifrelenmis
            // olabilir.
            RARReadHeader(hArsiv, Baslik);
            RARProcessFile(hArsiv, RAR_SKIP, NULL, NULL);
        }

        // ilk sifreli dosyayi oku
        RARReadHeader(hArsiv, Baslik);
        RARSetPassword(hArsiv, kelime);

        // sifreyle birlikte dosyayi test et. eger sifir dondururse sifre dogrudur.
        status = RARProcessFile(hArsiv, RAR_TEST, NULL, NULL);
        fprintf(stdout, "%8d", ++k2);
        fflush(stdout);

        if(status == 0)    break;  // dogru sifre bulunduysa donguyu sonlandir.

        RARCloseArchive(hArsiv);
    }

    // sozluk.txt'nin sonuna gelinmemisse (break ile cikildiysa) sifre bulunmustur
    if(!feof(hDosya))
        // sifre bulunduysa ekrana yaz
        printf("Sifre: %s\n", kelime);
    else
        printf("Sifre bulunamadi.\n\n");

    fclose(hDosya);

    return;

}


void ArsivCoz(char *arsiv)    {
    // dosya adlari sifrelenmisse cozme altprogrami
    HANDLE PASCAL hArsiv;
    struct RAROpenArchiveData *AcmaVerisi;    // RAR dosyayla ilgili veriler
    struct RARHeaderData *Baslik;    // RAR icerisindeki dosyalarla ilgili veriler
    char sozluk[] = "sozluk.txt";    // sozluk.txt denenecek kelimelerin oldugu dosya
    char kelime[256];
    FILE *hDosya;
    int status;

    hDosya = fopen(sozluk, "r");

    AcmaVerisi = (struct RAROpenArchiveData *)malloc(sizeof(struct RAROpenArchiveData));
    Baslik     = (struct RARHeaderData *)malloc(sizeof(struct RARHeaderData));

    while(!feof(hDosya))    {
        // sozlukten bir kelime oku
        fscanf(hDosya, "%s", kelime);

        // RAR kutuphanesinin dosya acmak icin kullandigi yapiyi doldur:
        AcmaVerisi->ArcName    = arsiv;
        AcmaVerisi->OpenMode   = RAR_OM_EXTRACT;
        AcmaVerisi->CmtBuf     = NULL;
        AcmaVerisi->CmtBufSize = 0;

        // doldurulan verilerle RAR dosyayi ac
        hArsiv = RAROpenArchive(AcmaVerisi);

        Baslik->CmtBuf   = NULL;
        RARSetPassword(hArsiv, kelime);
        // sifreyi belirttikten sonra RAR dosya basligini oku
        status = RARReadHeader(hArsiv, Baslik);
   
        // eger baslik okuma isi basariyla sonlanmissa status'da sifir degeri
        // doner. yani sifre bulunmus olur. bu durumda donguyu sonlandir.
        if(status == 0)    break;   

        RARCloseArchive(hArsiv);
    }

   // sozluk.txt'nin sonuna gelinmemisse (break ile cikildiysa) sifre bulunmustur
    if(!feof(hDosya))
        // sifre bulunduysa ekrana yaz
        printf("Sifre: %s\n", kelime);
    else
        printf("Sifre bulunamadi.\n\n");

    fclose(hDosya);
    return;
}


int main(int argc, char *argv[])    {
    HANDLE PASCAL hArsiv;
    struct RAROpenArchiveData *AcmaVerisi;
    struct RARHeaderData *Baslik;
    char dosyaadi[] = "deneme1.rar";   
    // programa parametre olarak herhangi bir dosya adi belirtilmezse bu dosya
    // adindaki RAR dosyayi acmaya calisir.
    int status, k1 = 0, k2 = 1;

    // RAR dosyanin acma verisi icin bellek ayir. malloc'un sonucunu kontrol
    // ettirmedim, ancak istenirse bu kontrol eklenebilir.
    AcmaVerisi = (struct RAROpenArchiveData *)malloc(sizeof(struct RAROpenArchiveData));

    // programa bir arguman dosya adi verildiyse bu dosya adini ac.
    if(argc > 1)    strcpy(dosyaadi, argv[1]);

    AcmaVerisi->ArcName    = dosyaadi;
    AcmaVerisi->OpenMode   = RAR_OM_EXTRACT;
    AcmaVerisi->CmtBuf     = NULL;
    AcmaVerisi->CmtBufSize = 0;
   
    if((hArsiv = RAROpenArchive(AcmaVerisi)) == NULL)    {
        // dosyayi bulamazsa
        printf("Arsivi acma basarisiz oldu.\n");
        return 1;
    }

    // RAR dosyayi ac, baslik icin gereken yapilari bellekte ayir.
    Baslik = (struct RARHeaderData *)malloc(sizeof(struct RARHeaderData));
    Baslik->CmtBuf   = NULL;    // RAR dosyadaki yorumlar okunmayacak

    while(1)    {
        // RAR dosya icerisindeki dosya bilgilerini oku
        status = RARReadHeader(hArsiv, Baslik);
        // eger RAR dosyanin sonuna gelindiyse while'i sonlandir.
        if(status == ERAR_END_ARCHIVE)    break;
        // dosya adlari sifrelenmisse ArsivCoz fonksiyonu cagirilacak
        if(status == ERAR_MISSING_PASSWORD)    {
            printf("Dosya adlari sifrelenmis.\n");
            ArsivCoz(dosyaadi);
            break;
        }

        k1 = k1 + k2;    // ilk adimda k1 = 0, k2 = 1. eger bir tane sifrelenmis
                        // dosya varsa k2 = 0 olacak, sayma islemi sonlandirilacak.
        printf("Arsivdeki dosyanin adi: %s", Baslik->ArcName);
        if(Baslik->Flags & 0x04)    {    // flags'da 3. bitin set edilmesi dosyanin
            printf("*\n");                // sifrelendigini gosterir. sifrelenmis
            k2 = 0;                        // dosyayi yaninda * ile ekrana yazip dosya
        }                                // sayimini sonlandir.
        else    printf("\n");            // dosya sifrelenmemisse * koyma

        status = RARProcessFile(hArsiv, RAR_SKIP, NULL, NULL);    // bir sonraki dosyaya gec
        if(status != 0)    printf("Dosyalari islerken birseyler oldu (%d).\n", status);
    }

    RARCloseArchive(hArsiv);

    // k1'de ilk sifreli dosyanin numarasi var.
    if(status != ERAR_MISSING_PASSWORD)
    // eger MISSING_PASSWORD varsa zaten tum dosya sifrelidir.
    // tek bir dosya sifreliyse DosyaCoz fonksiyonunu cagir.
        DosyaCoz(dosyaadi, k1);

    return 0;
}

Bu arada program kodunu vim'de yazıp Notepad++'ya aktardım. Vim'de tabstop 8, Notepad++'da 4 karakter. Bu nedenle de kodun bazı yerlerinde hizalama (indentation) kaydı. Beni suçlamak yerine alıcılarınızın ayarlarıyla oynayın lütfen.

Gelelim bilgisayarına MPI kuracaklar veya hesaplama kümesi erişimi olanlar için asıl olay paralel koda:

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<mpi.h>

// unrar kutuphanesine ait header dosyalari
#include<raros.hpp>
#include<dll.hpp>

#define MAX_PASS_LENGTH 16
#define MAX_NAME_LENGTH 256        // olabilecek en uzun dosya adi.
#define CALL_ArsivCoz   0x04
#define CALL_DosyaCoz   0x08
#define TAG             0x10

void DosyaCoz(char *arsiv, char *sozluk, int blksiz, int ofset, int sira)    {
    /*
        DosyaCoz(...): Dosya adlari acik, dosya sifreliyse cozme islemi
        arsiv:    RAR dosyanin adini tutan string.
        sozluk:   Sifrelerin listelendigi sozluk dosyasinin adini tutan string
        blksiz:   her bir islemciye sozluk dosyasindan dusen kelime sayisi
        ofset:    her islemcinin sozluk dosyasinin hangi satirini okuyacagi
        sira:     sifresi cozulecek dosyanin arsiv dosyasindaki sirasi
    */
    HANDLE PASCAL hArsiv;
    struct RAROpenArchiveData *AcmaVerisi;    // RAR dosyayla ilgili veriler
    struct RARHeaderData *Baslik;  // RAR icerisindeki dosyalarla ilgili veriler
    char kelime[MAX_PASS_LENGTH];
    FILE *hDosya;
    int status, k1, k2, rank;
    double sure;

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    // MPI uzayinda kacinci islemciyim?
    sure = MPI_Wtime();        // sure olcumunu baslat

#ifdef DEBUG
        printf("(%d): blok buyuklugu: %d, ofset: %d\n", rank, blksiz, ofset);
#endif

    hDosya = fopen(sozluk, "r");
        for(k2 = 0; k2 < ofset; k2++)
            fgets(kelime, MAX_PASS_LENGTH, hDosya);
            // her islemci kendi okuyacagi yere kadar gelsin

    // RAR dosya ve icindeki verileri acmak icin gerekli yapilari bellekte ayir
    AcmaVerisi = (struct RAROpenArchiveData *)malloc(sizeof(struct RAROpenArchiveData));
    Baslik     = (struct RARHeaderData *)malloc(sizeof(struct RARHeaderData));
    // burada malloc'un dondurdugu degerlerin test edilmesi eksik
   
    k2 = 0;
    while(k2 < blksiz)        {
        // sozlukten bir kelime oku
        fscanf(hDosya, "%s", kelime);

#ifdef DEBUG
            printf("(%d): (sayac %d) denenen kelime: %s\n", rank, k2, kelime);
            fflush(stdout);
#endif

        // RAR kutuphanesinin dosya acmak icin kullandigi yapi
        AcmaVerisi->ArcName    = arsiv;
        AcmaVerisi->OpenMode   = RAR_OM_EXTRACT;
        AcmaVerisi->CmtBuf     = NULL;
        AcmaVerisi->CmtBufSize = 0;

        // RAR dosyasini ac
        hArsiv = RAROpenArchive(AcmaVerisi);
        Baslik->CmtBuf   = NULL;

        for(k1 = 0; k1 < (sira - 1); k1++)      {
        // ilk sifreli dosyaya kadar oku, yalnizca bazi dosyalar sifrelenmis
        // olabilir.
        RARReadHeader(hArsiv, Baslik);
        RARProcessFile(hArsiv, RAR_SKIP, NULL, NULL);
        }

        // ilk sifreli dosyayi oku
        RARReadHeader(hArsiv, Baslik);
        RARSetPassword(hArsiv, kelime);

        // sifreyle birlikte dosyayi test et. eger sifir dondururse sifre dogrudur.
        status = RARProcessFile(hArsiv, RAR_TEST, NULL, NULL);

        if(status == 0)    break;    // dogru sifre bulunduysa donguyu sonlandir

        RARCloseArchive(hArsiv);
        k2++;
    }

    if(k2 < blksiz)     {    // dongu bitiminde islemci kendisine dusen blogun
        // sonuna gelmemisse arada bir yerde sifreyi buldu demektir.
        printf("Sifre: %s\n", kelime);
        MPI_Abort(MPI_COMM_WORLD, 8);
    }
    else
        printf("Sifre bulunamadi.\n\n");

        printf("Islemci %d icin calisma suresi %f saniye.\n", rank, MPI_Wtime() - sure);
    fclose(hDosya);

    return;

}

void ArsivCoz(char *arsiv, char *sozluk, int blksiz, int ofset)    {
    /*
        ArsivCoz(...): Dosya adlari sifrelenmisse cozme algoritmasi
        arsiv:    RAR dosyanin adini tutan string.
        sozluk:   Sifrelerin listelendigi sozluk dosyasinin adini tutan string
        blksiz:   her bir islemciye sozluk dosyasindan dusen kelime sayisi
        ofset:    her islemcinin sozluk dosyasinin hangi satirini okuyacagi
    */

    HANDLE PASCAL hArsiv;
    struct RAROpenArchiveData *AcmaVerisi;    // RAR dosyasiyla ilgili veriler
    struct RARHeaderData *Baslik; // RAR icerisindeki dosyalarla ilgili veriler
    char kelime[MAX_PASS_LENGTH];
    FILE *hDosya;
    int status, k1, rank;
    double sure;

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);    // MPI uzayinda kacinci islemciyim?
    sure = MPI_Wtime();  // sure olcumunu baslat..

#ifdef DEBUG
    printf("(%d): blok buyuklugu: %d, ofset: %d\n", rank, blksiz, ofset);
#endif

    hDosya = fopen(sozluk, "r");

        for(k1 = 0; k1 < ofset; k1++)
            fgets(kelime, MAX_PASS_LENGTH, hDosya);
            // herkes sozluk dosyasinda kendi okuyacagi yere kadar gelsin

    // RAR dosya ve icindeki verileri acmak icin gerekli yapilari bellekte ayir
    AcmaVerisi = (struct RAROpenArchiveData *)malloc(sizeof(struct RAROpenArchiveData));
    Baslik     = (struct RARHeaderData *)malloc(sizeof(struct RARHeaderData));
    // burada malloc'un dondurdugu degerlerin test edilmesi eksik

    k1 = 0;
    while(k1 < blksiz)        {
        // sozlukten bir kelime oku
            fgets(kelime, MAX_PASS_LENGTH, hDosya);

#ifdef DEBUG
        printf("(%d): (sayac %d) denenen kelime: %s\n", rank, k1, kelime);
        fflush(stdout);
#endif

        // RAR kutuphanesinin dosya acmak icin kullandigi yapiyi doldur
        AcmaVerisi->ArcName    = arsiv;
        AcmaVerisi->OpenMode   = RAR_OM_EXTRACT;
        AcmaVerisi->CmtBuf     = NULL;
        AcmaVerisi->CmtBufSize = 0;

        // doldurulan verilerle RAR dosyayi ac
        hArsiv = RAROpenArchive(AcmaVerisi);

        // CommentBuffer = NULL : Comment'leri okuma
        Baslik->CmtBuf   = NULL;
        RARSetPassword(hArsiv, kelime);
        // sifreyi belirttikten sonra RAR dosya basligini oku
        status = RARReadHeader(hArsiv, Baslik);

        // eger baslik okuma isi basariyla sonlanmissa status'da sifir degeri
        // doner yani sifre bulunmus olur. bu durumda donguyu sonlandir.
        if(status == 0) break;

        RARCloseArchive(hArsiv);
        k1++;
    }

    if(k1 < blksiz)       {    // dongu bitiminde islemci kendisine dusen blogun
        // sonuna gelmemisse arada bir yerde sifreyi buldu demektir.
        printf("Sifre: %s\n", kelime);
        MPI_Abort(MPI_COMM_WORLD, 9);
    }
    else
        printf("Sifre bulunamadi.\n\n");

    printf("Islemci %d icin calisma suresi %f saniye.\n", rank, MPI_Wtime() - sure);
    fclose(hDosya);

        return;
}

int main(int argc, char *argv[])    {
    FILE *hSozluk;
    int size, rank, nsatir, krkt, mesaj, blksiz, ofset, status;
    int k1 = 0, k2 = 1;
    HANDLE PASCAL *hArsiv;
    struct RAROpenArchiveData *AcmaVerisi;
    struct RARHeaderData *Baslik;
    char dosyaadi[MAX_NAME_LENGTH];
    char sozluk[MAX_NAME_LENGTH] = "sozluk.txt";
    char tmp[MAX_PASS_LENGTH];
    double sure;

    MPI_Init(&argc, &argv);
    // MPI'i initle, islemci sayisini ve sira sayilarini al.
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    sure = MPI_Wtime();

    if(argc > 1)    {
        // RAR dosyanin adi programa arguman olarak verilir.
        strcpy(dosyaadi, argv[1]);
        // eger birden fazla arguman verilmisse ikinci arguman sozluk dosyasidir
        if(argc > 2)    strcpy(sozluk, argv[2]);
    }
    else    {
        if(rank == 0)   printf("Kullanim: rarsolve <dosyaadi.rar> [sozluk.txt]\n");
        MPI_Abort(MPI_COMM_WORLD, 1);
        return 1;
    }

    if(rank == 0)    {
        // sifirinci islemci sozlugun satir sayisini belirler
        hSozluk = fopen(sozluk, "r");

        nsatir = 0;

        do    {
        krkt = fgetc(hSozluk);
        if(krkt == '\n')    nsatir++;
        } while(krkt != EOF);

        fclose(hSozluk);
    }

    // satir sayisini butun islemcilere bildir.
    MPI_Bcast(&nsatir, 1, MPI_INT, 0, MPI_COMM_WORLD);
   
    blksiz = nsatir / size;
    ofset  = rank * blksiz;
    // herkes kendine dusen sozluk blogunu ve ilk kelimesini bulsun

    if((nsatir % size) && (rank == (size - 1)))
        blksiz = nsatir - (blksiz * size - blksiz);
        // tamsayi duzenlemeleri

    if(rank == 0)    {
        // RAR dosyanin acma verisi icin bellekte yer ayir.
        AcmaVerisi = (struct RAROpenArchiveData *)malloc(sizeof(struct RAROpenArchiveData));

        AcmaVerisi->ArcName    = dosyaadi;
        AcmaVerisi->OpenMode   = RAR_OM_EXTRACT;
        AcmaVerisi->CmtBuf     = NULL;
        AcmaVerisi->CmtBufSize = 0;

        if((hArsiv = RAROpenArchive(AcmaVerisi)) == NULL)   {
            // dosyayi bulamazsa
            printf("Arsivi acma basarisiz oldu.\n");
            MPI_Abort(MPI_COMM_WORLD, 2);
            return 2;
        }

        // RAR dosyayi ac, baslik icin gereken yapilari bellekte ayir.
        Baslik = (struct RARHeaderData *)malloc(sizeof(struct RARHeaderData));
        Baslik->CmtBuf   = NULL;    // RAR dosyadaki yorumlar okunmayacak

        while(1)    {
            // RAR arsivi icerisindeki dosya bilgilerini oku.
            status = RARReadHeader(hArsiv, Baslik);
            // eger RAR dosyanin sonuna gelindiyse while'i sonlandir.
            if(status == ERAR_END_ARCHIVE)  break;
            // dosya adlari sifrelenmisse ArsivCoz fonksiyonu cagirilacak.
            if(status == ERAR_MISSING_PASSWORD)     {
                printf("Dosya adlari sifrelenmis.\n");
                mesaj = CALL_ArsivCoz;
                for(krkt = 1; krkt < size; krkt++)
                    // sifirinci butun islemcilere ArsivCoz fonksiyonunun
                    // cagirilacagini mesajla bildiriyor.
                    MPI_Send(&mesaj, 1, MPI_INT, krkt, TAG, MPI_COMM_WORLD);
                // sifirinci islemcinin kendisi de ArsivCoz'u cagiriyor.
                ArsivCoz(dosyaadi, sozluk, blksiz, ofset);
                break;
            }

            k1 = k1 + k2;   // ilk adimda k1 = 0, k2 = 1. eger bir tane sifrelenmis dosya varsa
                            // k2 = 0 olacak, sayma islemi sonlandirilacak.
            printf("Arsiv adi: %s", Baslik->ArcName);
            if(Baslik->Flags & 0x04)  {     // flags'da 3. bitin set edilmesi
                printf("*\n");          // dosyanin sifrelendigini gosterir.
                k2 = 0;                  // sifrelenmis dosyayi yaninda * ile yaz
            }
            else    printf("\n");

            status = RARProcessFile(hArsiv, RAR_SKIP, NULL, NULL);  // bir sonraki dosyaya gec
            if(status != 0) printf("Dosyalari islerken birseyler oldu (%d).\n", status);
        }

        RARCloseArchive(hArsiv);

        // k1'de ilk sifreli dosyanin numarasi var.
        if(status != ERAR_MISSING_PASSWORD)    {
        // eger MISSING_PASSWORD varsa zaten tum dosya sifrelidir.
                mesaj = CALL_DosyaCoz;
            // sifirinci islemci diger islemcilere DosyaCoz fonksiyonunun
            // cagirilacagini mesajla bildiriyor
                for(krkt = 1; krkt < size; krkt++)
                    MPI_Send(&mesaj, 1, MPI_INT, krkt, TAG, MPI_COMM_WORLD);
                // sifirinci islemcinin kendisi de ArsivCoz'u cagiriyor.
                DosyaCoz(dosyaadi, sozluk, blksiz, ofset, k1);
            }
    }

    else    {
        // sifirinci islemci haricindeki islemciler sifirincidan mesaj bekliyor
        MPI_Recv(&mesaj, 1, MPI_INT, 0, TAG, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
        if(mesaj == CALL_ArsivCoz)   
            ArsivCoz(dosyaadi, sozluk, blksiz, ofset);
        else if(mesaj == CALL_DosyaCoz)
            DosyaCoz(dosyaadi, sozluk, blksiz, ofset, k1);
    }

    if(rank == 0)
        printf("Toplam %f saniyede %d kelime denendi.\n", MPI_Wtime() - sure, nsatir);
   
    MPI_Finalize();

    return 0;
}

Son olarak herşey tamamsa son bir soru kalıyor: "Sözlük dosyaları nasıl oluşturulacak?" Onun için de basit bir MATLAB kodu yazdım. Yaptığı tek şey belirli kriterlere göre 5 ile 10 karakter arası rastgele kelimeler üretip bunları sozluk.txt dosyasina yazıyor. Aslında bunun için daha amaca daha yönelik araçlar yazılabilir. Örneğin sozluk.txt olarak imla kılavuzunu alıp imla kılavuzundaki kelimelerin başına yada sonuna sayılar eklemek gibi. Matlab kodu görece basit olduğundan pek açıklama yazmayacağım ancak onunla ilgili tek söyleyebileceğim 33 ve 36. satırlardaki iki for döngüsü yüzünden bir hayli yavaş çalıştığı. 

kucuk_harfler = true;
buyuk_harfler = false;
sayilar       = true;
karakterler   = false;
kel_sayi = 200000;        % 200bin kelime uret

kHavuz = [ ];
bharf_tablo = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
kharf_tablo = 'abcdefghijklmnopqrstuvwxyz';
sayi_tablo  = '0123456789';
karak_tablo = '!#$%&()*+,-./:;<=>?@_';

if(kucuk_harfler)
    kHavuz = strcat(kHavuz, kharf_tablo);
end

if(buyuk_harfler)
    kHavuz = strcat(kHavuz, bharf_tablo);
end

if(sayilar)
    kHavuz = strcat(kHavuz, sayi_tablo);
end

if(karakterler)
    kHavuz = strcat(kHavuz, karak_tablo);
end

lHavuz = length(kHavuz);
hSozluk = fopen('sozluk.txt', 'w');

for k1 = 1:kel_sayi
    kelime = [ ];
    uzunluk = floor(rand * 5 + 5);    % kelime uzunluklari rastgele
    for k2 = 1:uzunluk
        Havuz_ptr = floor(rand * lHavuz + 1);
        kelime = strcat(kelime, kHavuz(Havuz_ptr));
    end
    fprintf(hSozluk, '%s\n', kelime);
   
end

fclose(hSozluk);

Buraya kadar kodlardan ötürü bir hayli uzunca bir yazı oldu. Bu ara tekrar yazmak için zaman bulabilirsem gerçekten ne kadar gereksiz işlerle uğraştığımı anlatan bir yazı daha yayınlayabilirim.

Unrar Kütüphanesiyle Paralel Şifre Bulucu #2

Unrar kütüphanesi beş tane fonksiyonuyla (aslında yedi ancak ben beşini anlattım) programcıya kolaylıkla .rar dosyaları için arabirim sağlıyor. Kütüphanenin bazı kısıtları var, bunun en başında hız geliyor. Hız kısıtlaması .rar dosyaların yapısından kaynaklı olabilir. Programı yazarken karşıma çıkan sıkıntı her şifre denemesi için dosyanın kapatılıp yeniden açılması oldu. Bu her defasında arşiv dosyası için gerekli bellek yapılarının silinip bellekte yeniden ayrılması demek. Belki gelecekte kodu daha da hızlandırmak için kendi .rar kütüphanemi yazmam gerekebilir. Yazının bu kısmında paralel programlama ve MPI paralel programlama kütüphanesini anlatacağım.

Büyük işlem gücü gerektiren işlemlerin küçük parçalara ayrılarak paralel olarak işlenmesi fikri yeni değil. Paralel hesaplamayı popüler hale getiren SETI@Home projesi bundan 15 yıl önce başladı. Daha sonra United Devices'ın kanser ve şarbona karşı ilaç için molekül araştırma projeleri geldi. Diğer yandan 2000'lerin başında 3DS MAX render işlerini küçük parçalara bölüp şebeke üzerinden birbirine bağlı makinalara gönderebiliyordu. 3DS MAX'i çalıştıran ve render işini başlatan bir ana makina vardı. Diğer makinalarda hesaplama işleri için istemciler kuruluydu. Ana makina iş parçalarını diğer makinalara dağıtıyor, sonuçları alıyor, işleyip renderi tamamlıyordu. Günümüzdeyse küme bilgisayarlar (Cluster Computing) artık yüksek performanslı hesaplama işlerinin vazgeçilmez bir parçası. Birçok araştırma merkezinde bu bilgisayarlardan kurulu ve bilgisayarların konfigürasyonları basit ve eski masaüstü Pentium 4'lerden 16 MB cep belleğe (cache) sahip son teknoloji Xeon'lara kadar geniş bir yelpazede yer alıyor. Üstelik düşük bütçeli araştırma merkezleri bile ikinci el bilgisayarlarla Beowulf kümeleri kurabiliyorlar. Son olarak bu konuda nerd'lüğün en uç noktası Flash Mob Computing geliyor. Büyükçe bir merkezde bir araya gelen ve bilgisayarlarını getiren katılımcılar dağıtılan bir linux CD'siyle bilgisayarlarını açıyorlar. Dağıtımda, gerekli istemci programlar kurulu geliyor. Katılım sağlandıktan sonra bütün bilgisayarların işlem gücü ana makinada toplanıyor. Gerekli hesaplama yapılıp bittikten yada akşam olduktan sonra herkes bilgisayarını alıp tekrar evine dönüyor.

MPI (Message Passing Interface) bilgisayar kümelerinde artık standart hale gelmiş bir arayüz. MPI, dağıtık bilgisayarlarda basit bir programlama arayüzüyle TCP/IP yada sunucu/istemci kodlarıyla uğraşmadan belli sayıda bilgisayarda çalışarak işleri paralel olarak çalıştırmaya olanak veriyor. Kütüphanenin mantığı oldukça basit: Bütün işler aynı anda programı çalıştıran kişinin belirttiği sayıda spawn ediliyor. Aslında bütün makinalarda çalışan kod birbirinin aynı. MPI dilinde bu makinalara artık "işlemci" (processor) deniyor. Her işlemcinin kendine ait bir numarası bulunuyor. Makinaların birbirinden farklı davranması bu numaraya göre sağlanabiliyor. Aynı zamanda toplam kullanılabilen makina sayısı da alınabiliyor.

Örneğin MPI ile 8 işlemci kullanılarak [a, b] aralığında integral alınacak olsun. Bu durumda işlemci sayısı n olmak üzere her bir işlemciye t = (b - a) / n kadarlık bir aralık düşecektir. Her işlemcinin numarası p olursa, işlemciler (a + p * t)'den (a + (p + 1) * t)'ye kadar olan bölümü integral alacaklar demektir. İntegral alma işleminde parçalar birbirine bağlı olmadığından işlemciler arası herhangi bir haberleşme olmadan birbirlerinden bağımsız hesaplamayı tamamlayabilirler. Hesaplama bittiğinde her işlemcinin bulduğu sonuç bir bilgisayara gönderilir ve orada toplanır. İntegralin sonucu, bulunan bu toplamdır. Bu örnekte .rar şifresini bulurken de herhangi bir veri bağımlılığı bulunmadığından veri bağımlılığı bulunan karmaşık örneklerden kaçınmaya çalıştım.

Arşivin şifresini bulmak için sözlük tabanlı deneme yapan başka programlar da piyasada kolayca bulunabilir. (Mesela RAR Password Cracker) Bunun yanında MPI tabanlı MD5 reverse hash algoritması yada Paralel John the Ripper bulabilmek de mümkün. Ancak MPI tabanlı RAR çözücü ben rastlamadım, bu nedenle yazdığım bu programın piyasada ilk olduğunu iddia edebilirim.

Elbette ki bütün MPI kütüphanesini burada anlatmam mantıklı olmayacağından ben sadece programda kullandığım fonksiyonları anlatacağım.

int MPI_Init( int *argc, char ***argv ): Bu fonksiyonla bütün işlemciler paralel işlem yapmaya hazırlanır, başka bir deyişle işlemcilere hazır olmalarını, diğer MPI fonksiyonlarının çağırılacağını bildirir. Fonksiyonun argümanları main(int argc, char *argv[]) fonksiyonunun argümanlarıyla aynıdır (gösterici olmaları dışında). Hemen her MPI programı ilk olarak bu fonksiyonu çağırmak zorundadır.

int MPI_Comm_size( MPI_Comm comm, int *size ): MPI_Init çağırıldığında bir haberleşme dünyası oluşturulur. Haberleşme dünyası tüm işlemcileri kapsayan bir üst küme olarak düşünülebilir.

http://nf.nci.org.au/training/MPIProg/slides/slides.028.html

MPI_Init çağırılır çağırılmaz oluşturulan default haberleşme dünyasının handle'ı MPI_Comm türünde bir sabit olan MPI_COMM_WORLD'dür ve bu haberleşme dünyası bütün işlemcileri içerir. Daha sonra istenirse bunun alt kümesi olan yeni haberleşme dünyaları da oluşturulabilir. MPI_Comm_size fonksiyonu verilen comm haberleşme dünyasının içerdiği işlemci sayısını size adı verilen değişkene yazar. Yandaki resimde fonksiyon size değişkeninde 7 değerini döndürecektir. Bu fonksiyonun aynı haberleşme dünyası içerisindeki bütün işlemciler için aynı değeri döndüreceği açıktır.

int MPI_Comm_rank( MPI_Comm comm, int *rank ): Bu fonksiyon comm ile belirtilen haberleşme dünyasında her işlemciye özgü olan sıra numarasını rank değişkeninde döndürür. Bu fonksiyonun aynı haberleşme dünyası içerisinde bütün işlemciler için farklı değeri döndüreceği açıktır.

int MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm): MPI_Send fonksiyonu işlemcilerin kendi arasında haberleşmeyi sağlayabilmeleri için gerekli en basit fonksiyondur. buf ile belirtilen bellek bölgesinden başlayarak, count tane MPI_Datatype türündeki datatype'ı, dest ile belirtilen işlemciye tag etiketiyle comm haberleşme dünyası içerisinde yollar.

İfade biraz açılacak olursa; buf önceden bellekte ayrılmış herhangi bir değer yada dizi olabilir. count bu dizinin büyüklüğüdür. MPI'da C'deki veri tiplerine karşılık gelen veri tipleri MPI_Datatype türünde kodlanmıştır. datatype değişkeni MPI_INT, MPI_DOUBLE, MPI_CHAR vb. yada bunlardan türetilmiş bir veri türü olabilir. Bu türün büyüklüğü count ile çarpılarak toplamda kaç byte veri gönderileceği hesaplanır. Örneğin count = 16 ve MPI_INT'in büyüklüğü 4 byte ise toplamda 64 byte veri gönderilecektir. MPI'ın derlendiği makinanın mimarisine ve derleme parametrelerine bağlı olarak MPI_INT'in büyüklüğü değişebilir.

dest haberleşme dünyası içerisindeki herhangi bir işlemci numarasıdır. Sıfırdan MPI_Comm_size'ın döndürdüğü size değişkeninin bir eksiğine kadar herhangi bir değer olabilir. Bu değerden daha büyük yada sıfırdan küçük değerler programın yanlış çalışmasına ve çökmesine yol açabilir. Burada bir açıklama daha gerekiyor. MPI'ın bir standardı ve bu standartlara göre üreticiler tarafından yazılmış uyarlamaları (implementation) bulunmaktadır. Standartlar konunun ana hatlarını tamamlasa da bazı noktaları bilerek (örneğin esneklik açısından) yada bilmeyerek boş bırakmış olabilir. Bu boşluklardan biri kendine veri göndermeye çalışan program hakkındadır. MPI'ın Intel uyarlaması buna kesinlikle izin vermez ve program kendi kendine veri göndermeye kalkıştığında çöker. OpenMPI uyarlaması ise sorunsuz çalışır ve program kendi kendine veri gönderip alabilir. (En son hatırladığım bu şekildeydi. Sonradan uyarlamalar yada standartlar değişmiş olabilir.)

tag gönderilen mesajlara etiket vermeye yarayan bir sayıdır ve kaç olduğunun bir önemi yoktur sadece gönderme ve almada (MPI_Recv) aynı sayı olmalıdır. Karmaşık ve ardarda gönderilen birden fazla mesaj bulunduğu durumlarda işleri oldukça kolaylaştırır. Ve son olarak dest ile bildirilen işlemcinin hangi haberleşme dünyasına ait olduğunu bilebilmek için comm değişkeni haberleşme dünyasını tutar.

int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status *status): MPI_Send ile gönderilen veri bir başka işlemci tarafından MPI_Recv çağırılarak belleğe alınır. Bu fonksiyonda benzer biçimde buf ile belirtilen adrese count tane datatype türünde değişken source numaralı işlemciden tag etiketiyle comm haberleşme dünyası içerisinde okunur. MPI_Send'den tek farkı burada MPI_Status türünde bir durum döndürülür ancak genellikle bu değer MPI_STATUS_IGNORE değeriyle görmezden gelinir.

buf adresi MPI_Recv çağırılmadan önce bellekte ayrılmış olmalıdır. datatype, MPI_Send'in veri türüyle uyumlu olmak zorunda değilse de bunlar her zaman birbirinin aynı verilir. source yine gönderici işlemcinin sıra numarasıdır. Sıra numarasının bilinmediği yada fark etmediği durumlarda MPI_ANY_SOURCE kullanılabilir. Yine benzer şekilde etiket numaraları birbirini mutlaka tutmak zorundadır ancak etiket numarasının önemsenmediği durumlarda MPI_ANY_TAG kullanılabilir.

int MPI_Bcast( void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm ): MPI_Bcast fonksiyonu comm haberleşme dünyasında root numaralı işlemcinin buffer adresindeki count tane datatype türündeki veriyi diğer işlemcilere de kopyalar. Fonksiyon çağırılmadan önce bütün işlemciler buffer bellek adresini bellekte ayırmış olmalıdırlar.

http://www.mathcs.emory.edu/~cheung/Courses/355/Syllabus/92-MPI/group-comm.html

Peki bir MPI_Bcast çağrısının, 0'dan (size - 1)'e kadar olan bir for döngüsü içerisindeki MPI_Send'den farkı nedir? Yapılan iş aynı olmakla birlikte nasıl yapıldığı farklıdır. MPI_Send yaklaşımında haberleşme dünyasındaki işlemci sayısı kadar MPI_Send çağrısı gerçekleşir. Öte yandan MPI_Bcast'in çalışma prensibi şöyledir: Haberleşme dünyasında sekiz işlemci olduğunu ve root'u 0. işlemci olan bir MPI_Bcast çağrısı yapıldığını varsayalım. İlk adımda 0. işlemci buffer'ının tamamını 4. işlemciye gönderir. İkinci adımda 0. ve 4. işlemciler buffer'larının tamamını sırasıyla 2. ve 6. işlemcilere gönderirler. Son adımdaysa 0., 2., 4. ve 6. işlemciler buffer'larının tamamını sırayla 1., 3., 5. ve 7. işlemcilere yolladıkları zaman işlem üç adımda tamamlanır. Yani işlemci sayısı p olmak üzere MPI_Send ile p adımda yaptığımız işlemi MPI_Bcast bize log₂(p) adımda tamamlamaya olanak sağlar. p sayısının en az 1 olacağını düşünürsek her durumda sayının logaritması kendisinden küçüktür. 

MPI_Bcast kullanırken dikkat edilmesi gereken bütün işlemcilerin MPI_Bcast fonksiyonunu çağırma zorunluluğudur. Yani fonksiyon, rank değişkeni işlemci numarasını göstermek üzere if(rank == 3) yada if(rank % 2) gibi bir ifade içerisinde çağırılamaz. Bunun yerine ikinci ifade için tek ve çift sayılı işlemcilerden oluşan yeni bir haberleşme dünyası tanımlanmalıdır.

int MPI_Abort(MPI_Comm comm, int errorcode): MPI_Abort çağrısı bir işlemcinin hatayla karşılaşması durumunda bütün haberleşme dünyasını sonlandırmak ve programdan çıkmak için kullanılır.

int MPI_Finalize( void ): Bu fonksiyon diğer işlemcileri öldürür. Genellikle main()'den çıkılmadan hemen önce kullanılır ve bütün MPI kodları bu fonksiyonla bitmek zorundadır. Bu fonksiyondan sonra yapılacak herhangi bir MPI fonksiyon çağrısı hataya sebep olur.

Son olarak MPI kurmak için bir hesaplama kümesi sahibi olmaya gerek yoktur. Herkes makinasına MPI kurabilir. Makinaların dağıtık olmasına gerek olmaksızın MPI tek bir makinadaki işlemcileri ve çekirdekleri ayrı işlemciler olarak etkin biçimde kullanabilir. MPI ile yazılmış kodları derlemek için, MPI kurulurken icc yada cc için kendi wrapper derleyicisini mpiicc yada mpicc adında kurar. mpicc kullanırken -L, -I gibi parametreleri ayrıca vermeye gerek kalmaz. MPI kodu mpi derleyicisiyle derlendikten sonra mpirun yada mpiexec komutlarıyla çalıştırılır. Örneğin mpirun -np 4 ./deneme.x biçiminde bir komut deneme.x çalıştırılabilir dosyasını 4 işlemcide çalıştırır. Çalıştırılan makinada 4 işlemci olmasa bile mpirun 4 işlemci varmış gibi çalışıp çıktı üretecektir. Ancak dört çekirdekli bir makinada programın 4 işlemciyle çalışma süresi 2 işlemciyle çalışma süresinin yarısı olacakken tek çekirdekli bir makinada herhangi bir fark görülmez hatta 4 işlemciyle daha uzun sürede çalışacaktır. MPI ile ilgili kod örneklerine burada değinmeyeceğim ancak internette bunlarla ilgili bir sürü örnek bulmak olası. Bir sonraki bölümde yayınlayacağım kod ve açıklamaları zaten bu fonksiyonlara ve bir önceki bölümde anlattığım fonksiyonlara bir örnek olacaktır.