git.sesse.net Git - freerainbowtables/blob - Server Applications/rsearchi/RainbowTableSort.cpp

   1 /*
   2    RainbowCrack - a general propose implementation of Philippe Oechslin's faster time-memory trade-off technique.
   3
   4    Copyright (C) Zhu Shuanglei <shuanglei@hotmail.com>
   5 */
   6
   7 #include "Public.h"
   8
   9 #define ASSUMED_MIN_MEMORY 32 * 1024 * 1024
  10
  11 /////////////////////////////////////////////////////////////////////////////
  12
  13 /*
  14 int QuickSortCompare(const void* pElem1, const void* pElem2)
  15 {
  16         uint64 n1 = ((RainbowChain*)pElem1)->nIndexE;
  17         uint64 n2 = ((RainbowChain*)pElem2)->nIndexE;
  18
  19         if (n1 < n2)
  20                 return -1;
  21         else if (n1 == n2)
  22                 return 0;
  23         else
  24                 return 1;
  25 }
  26
  27 void QuickSort(RainbowChain* pChain, int nRainbowChainCount)
  28 {
  29         qsort(pChain, nRainbowChainCount, 16, QuickSortCompare);        // so slow!
  30 }
  31 */
  32
  33 /////////////////////////////////////////////////////////////////////////////
  34
  35 int QuickSortPartition(RainbowChain* pChain, int nLow, int nHigh)
  36 {
  37         int nRandomIndex = nLow + ((unsigned int)rand() * (RAND_MAX + 1) + (unsigned int)rand()) % (nHigh - nLow + 1);
  38         RainbowChain TempChain;
  39         TempChain = pChain[nLow];
  40         pChain[nLow] = pChain[nRandomIndex];
  41         pChain[nRandomIndex] = TempChain;
  42
  43         TempChain = pChain[nLow];
  44         uint64 nPivotKey = pChain[nLow].nIndexE;
  45         while (nLow < nHigh)
  46         {
  47                 while (nLow < nHigh && pChain[nHigh].nIndexE >= nPivotKey)
  48                         nHigh--;
  49                 pChain[nLow] = pChain[nHigh];
  50                 while (nLow < nHigh && pChain[nLow].nIndexE <= nPivotKey)
  51                         nLow++;
  52                 pChain[nHigh] = pChain[nLow];
  53         }
  54         pChain[nLow] = TempChain;
  55         return nLow;
  56 }
  57
  58 void QuickSort(RainbowChain* pChain, int nLow, int nHigh)
  59 {
  60         if (nLow < nHigh)
  61         {
  62                 int nPivotLoc = QuickSortPartition(pChain, nLow, nHigh);
  63                 QuickSort(pChain, nLow, nPivotLoc - 1);
  64                 QuickSort(pChain, nPivotLoc + 1, nHigh);
  65         }
  66 }
  67
  68 /////////////////////////////////////////////////////////////////////////////
  69
  70 #define SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY 1024
  71
  72 class CSortedSegment
  73 {
  74 public:
  75         CSortedSegment(FILE* file, unsigned int nFileChainOffset, int nFileChainCount)
  76         {
  77                 m_nChainCount     = 0;
  78                 m_nNextChainIndex = 0;
  79
  80                 m_file             = file;
  81                 m_nFileChainOffset = nFileChainOffset;
  82                 m_nFileChainCount  = nFileChainCount;
  83         }
  84
  85 private:
  86         RainbowChain m_Chain[SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY];
  87         int m_nChainCount;
  88         int m_nNextChainIndex;
  89
  90         FILE* m_file;
  91         unsigned int m_nFileChainOffset;
  92         int m_nFileChainCount;
  93
  94 public:
  95         RainbowChain* GetNextChain()    // Don't call this if no chain left
  96         {
  97                 if (m_nChainCount == m_nNextChainIndex)
  98                 {
  99                         int nChainCountToRead;
 100                         if (m_nFileChainCount < SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY)
 101                                 nChainCountToRead = m_nFileChainCount;
 102                         else
 103                                 nChainCountToRead = SORTED_SEGMENT_MAX_CHAIN_IN_MEMORY;
 104
 105                         //printf("reading... (offset = %u, chain count = %d)\n", m_nFileChainOffset, nChainCountToRead);
 106                         fseek(m_file, m_nFileChainOffset, SEEK_SET);
 107                         fread(m_Chain, 1, sizeof(RainbowChain) * nChainCountToRead, m_file);
 108                         m_nChainCount       = nChainCountToRead;
 109                         m_nNextChainIndex   = 0;
 110                         m_nFileChainOffset += sizeof(RainbowChain) * nChainCountToRead;
 111                         m_nFileChainCount  -= nChainCountToRead;
 112                 }
 113
 114                 return &m_Chain[m_nNextChainIndex];
 115         }
 116
 117         bool RemoveTopChain()   // return whether already empty
 118         {
 119                 m_nNextChainIndex++;
 120
 121                 if (m_nChainCount == m_nNextChainIndex)
 122                         if (m_nFileChainCount == 0)
 123                                 return true;
 124
 125                 return false;
 126         }
 127 };
 128
 129 FILE* CreateTemporaryFile(string sPathName, unsigned int nLen)
 130 {
 131         FILE* tempfile = fopen(sPathName.c_str(), "w+b");
 132         if (tempfile == NULL)
 133         {
 134                 printf("can't create temporary file %s\n", sPathName.c_str());
 135                 return NULL;
 136         }
 137
 138         // Set proper length - this is not a good method
 139         fseek(tempfile, nLen - 4, SEEK_SET);
 140         int x;
 141         fwrite(&x, 1, 4, tempfile);
 142         if (GetFileLen(tempfile) != nLen)
 143         {
 144                 printf("not enough temporary disk space, %u bytes required\n", nLen);
 145                 fclose(tempfile);
 146                 remove(sPathName.c_str());
 147                 return NULL;
 148         }
 149
 150         return tempfile;
 151 }
 152
 153 bool PrepareSortedSegment(list<CSortedSegment>& lSS, FILE* file, FILE* tempfile)
 154 {
 155         unsigned int nAvailPhys = GetAvailPhysMemorySize();
 156         if (nAvailPhys < ASSUMED_MIN_MEMORY)
 157                 nAvailPhys = ASSUMED_MIN_MEMORY;
 158         nAvailPhys = nAvailPhys / 16 * 16;
 159
 160         // Allocate memory
 161         unsigned char* pMem = new unsigned char[nAvailPhys];
 162         if (pMem == NULL)
 163         {
 164                 printf("memory allocation fail\n");
 165                 return false;
 166         }
 167
 168         // Run
 169         unsigned int nFileLen = GetFileLen(file);
 170         fseek(file, 0, SEEK_SET);
 171         fseek(tempfile, 0, SEEK_SET);
 172         int i;
 173         for (i = 0; ; i++)
 174         {
 175                 if (ftell(file) == nFileLen)
 176                         break;
 177
 178                 printf("reading segment #%d...\n", i);
 179                 unsigned int nRead = fread(pMem, 1, nAvailPhys, file);
 180
 181                 printf("sorting segment #%d...\n", i);
 182                 QuickSort((RainbowChain*)pMem, 0, nRead / 16 - 1);
 183
 184                 CSortedSegment ss(tempfile, ftell(tempfile), nRead / 16);
 185                 lSS.push_back(ss);
 186
 187                 printf("writing sorted segment #%d...\n", i);
 188                 fwrite(pMem, 1, nRead, tempfile);
 189         }
 190
 191         // Free memory
 192         delete pMem;
 193
 194         return true;
 195 }
 196
 197 void MergeSortedSegment(list<CSortedSegment>& lSS, FILE* file)
 198 {
 199         printf("merging sorted segments...\n");
 200
 201         fseek(file, 0, SEEK_SET);
 202         while (!lSS.empty())
 203         {
 204                 list<CSortedSegment>::iterator MinIt;
 205                 uint64 nMinIndexE;
 206                 list<CSortedSegment>::iterator it;
 207                 for (it = lSS.begin(); it != lSS.end(); it++)
 208                 {
 209                         if (it == lSS.begin())
 210                         {
 211                                 MinIt = it;
 212                                 nMinIndexE = ((*it).GetNextChain())->nIndexE;
 213                         }
 214                         else
 215                         {
 216                                 if (((*it).GetNextChain())->nIndexE < nMinIndexE)
 217                                 {
 218                                         MinIt = it;
 219                                         nMinIndexE = ((*it).GetNextChain())->nIndexE;
 220                                 }
 221                         }
 222                 }
 223
 224                 fwrite((*MinIt).GetNextChain(), 1, 16, file);
 225
 226                 if ((*MinIt).RemoveTopChain())
 227                         lSS.erase(MinIt);
 228         }
 229 }
 230
 231 void ExternalSort(FILE* file, string sTemporaryFilePathName)
 232 {
 233         FILE* tempfile = CreateTemporaryFile(sTemporaryFilePathName, GetFileLen(file));
 234         if (tempfile != NULL)
 235         {
 236                 list<CSortedSegment> lSS;
 237                 if (PrepareSortedSegment(lSS, file, tempfile))
 238                         MergeSortedSegment(lSS, file);
 239                 fclose(tempfile);
 240                 remove(sTemporaryFilePathName.c_str());
 241         }
 242 }
 243
 244 /////////////////////////////////////////////////////////////////////////////
 245
 246 int SortRainbowtable(string sPathName)
 247 {
 248 /*      if (argc != 2)
 249         {
 250                 Logo();
 251
 252                 printf("usage: rtsort rainbow_table_pathname\n");
 253                 return 0;
 254         }
 255         string sPathName = argv[1];
 256 */
 257         // Open file
 258         FILE* file = fopen(sPathName.c_str(), "r+b");
 259         if (file == NULL)
 260         {
 261                 printf("failed to open %s\n", sPathName.c_str());
 262                 return 0;
 263         }
 264
 265         // Sort
 266         unsigned int nFileLen = GetFileLen(file);
 267         if (nFileLen % 16 != 0)
 268                 printf("rainbow table size check fail\n");
 269         else
 270         {
 271                 // Available physical memory
 272                 unsigned int nAvailPhys = GetAvailPhysMemorySize();
 273                 printf("available physical memory: %u bytes\n", nAvailPhys);
 274
 275                 // QuickSort or ExternalSort
 276                 if (nAvailPhys >= nFileLen || nFileLen <= ASSUMED_MIN_MEMORY)
 277                 {
 278                         int nRainbowChainCount = nFileLen / 16;
 279                         RainbowChain* pChain = (RainbowChain*)new unsigned char[nFileLen];
 280                         if (pChain != NULL)
 281                         {
 282                                 // Load file
 283                                 printf("loading rainbow table...\n");
 284                                 fseek(file, 0, SEEK_SET);
 285                                 if (fread(pChain, 1, nFileLen, file) != nFileLen)
 286                                 {
 287                                         printf("disk read fail\n");
 288                                         goto ABORT;
 289                                 }
 290
 291                                 // Sort file
 292                                 printf("sorting rainbow table...\n");
 293                                 QuickSort(pChain, 0, nRainbowChainCount - 1);
 294
 295                                 // Write file
 296                                 printf("writing sorted rainbow table...\n");
 297                                 fseek(file, 0, SEEK_SET);
 298                                 fwrite(pChain, 1, nFileLen, file);
 299
 300                                 delete[] pChain;
 301                         }
 302                         else
 303                                 printf("memory allocation fail\n");
 304                 }
 305                 else
 306                 {
 307                         // External sort when memory is low
 308                         ExternalSort(file, sPathName + ".tmp");
 309                 }
 310         }
 311 ABORT:
 312
 313         // Close file
 314         fclose(file);
 315
 316         return 0;
 317 }