fork download
copy 
  1. #include <cstring>
  2.  
  3. // Will use ALL available options by default
  4. // Pwd. complexity: 26 + 10 + 32 + 26 = 94^N
  5. struct GeneratePwdOptions {
  6.   enum ECharSetType {
  7.     CST_ALPHA,  // latin letters; low: [97, 122] AND up: [65, 90] (total of 26 unique)
  8.     CST_DIGITS, // arabic numbers [48, 57] (10 unique)
  9.     CST_SYMBOLS // printable symbols: punctuation AND so on, EXCLUDING space
  10.   };
  11.  
  12.   static const ECharSetType CHAR_SETS[];
  13.   static const size_t CHAR_SET_COUNT_; // big AND small alphas counts as a one charset
  14.  
  15.   //// ALL codes are shown for the ANSI ASCII table
  16.   bool useAlpha      = true;
  17.   bool useDigits     = true;
  18.   bool useSymbols    = true;
  19.   bool caseSensetive = true; // use both lower AND upper case (if false - ONLY lowercase)
  20. };
  21. const GeneratePwdOptions DEFAULT_GENERATE_PWD_OPTIONS_;
  22. const GeneratePwdOptions::ECharSetType GeneratePwdOptions::CHAR_SETS[] =
  23.   {ECharSetType::CST_ALPHA, ECharSetType::CST_DIGITS, ECharSetType::CST_SYMBOLS};
  24. const size_t GeneratePwdOptions::CHAR_SET_COUNT_ = sizeof(CHAR_SETS) / sizeof(*CHAR_SETS);
  25.  
  26. #include <functional>
  27. #include <random>
  28. #include <chrono>
  29.  
  30. // 'pwdBuf' should be at least (len + 1U) large
  31. // 'len' should be >= 8U (returns empty str. if NOT)
  32. // Returns empty str. on ANY error
  33. // 'charPerSet' is an OUTPUT statistics (OPTIONAL)
  34. // Complexity - linear: O(2*len)
  35. template <const bool Optimized = true>
  36. char* generatePwd(char* pwdBuf, const size_t len = 16U,
  37.                   const GeneratePwdOptions& options = DEFAULT_GENERATE_PWD_OPTIONS_,
  38.                   size_t charPerSet[GeneratePwdOptions::CHAR_SET_COUNT_] = nullptr) throw()
  39. {
  40.   static const auto MIN_PWD_LEN_ = 8U;
  41.   static_assert('z' > 'a' && 'Z' > 'A' && '9' > '0', "Incorrect char codes");
  42.   // [33, 47] U [58, 64] U [91, 96] U [123, 126]
  43.   static const char SPEC_SYMBOLS[] = {"!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"};
  44.  
  45.   if (!pwdBuf || !len) return nullptr;
  46.   *pwdBuf = '\0';
  47.   if (len < MIN_PWD_LEN_) return pwdBuf;
  48.  
  49.   const size_t timeSeed =
  50.     static_cast<size_t>(std::chrono::system_clock::now().time_since_epoch().count());
  51.   const std::mt19937 engine(timeSeed);
  52.  
  53.   const std::uniform_int_distribution<size_t> charIdxDistribution(size_t(), len - 1U);
  54.   auto rollCharIdx = std::bind(charIdxDistribution, engine); // callable
  55.  
  56.   auto charSetCount = size_t();
  57.   if (options.useAlpha) ++charSetCount;
  58.   if (options.useDigits) ++charSetCount;
  59.   if (options.useSymbols) ++charSetCount;
  60.  
  61.   if (!charSetCount) return pwdBuf; // error: charset NOT specified
  62.  
  63.   // Each set can place a strictly limited amount of chars
  64.   const auto maxCharPerSetCount = len / charSetCount;
  65.   // At least 1 char form each set
  66.   const std::uniform_int_distribution<size_t> charPerSetDistribution(1U, maxCharPerSetCount);
  67.   auto rollCharPerSetCount = std::bind(charPerSetDistribution, engine); // callable
  68.  
  69.   size_t localCharPerSet[GeneratePwdOptions::CHAR_SET_COUNT_] = {0}; // statistics
  70.   auto const currCharPerSet = charPerSet ? charPerSet : localCharPerSet; // replace if NOT provided
  71.  
  72.   struct Randomizer_ {
  73.     Randomizer_() throw() { // 'srand' will be called ONLY once during initialiation
  74.       srand(static_cast<unsigned int>(time(nullptr)));
  75.     }
  76.   };
  77.   static const Randomizer_ R_; // static init. is a thread safe in C++11
  78.  
  79.   auto charSetLeftCount = charSetCount;
  80.   size_t charPlacedCount = size_t(); // total amount of chars already placed in the buf.
  81.  
  82.   auto getCharCountPerSet = [&]() throw() {
  83.     // If last - fill the rest of the buf.
  84.     return charSetLeftCount ? rollCharPerSetCount() : (len - charPlacedCount);
  85.   };
  86.  
  87.   // Also updates statistics for the specified charset
  88.   auto getRandomChar = [&](const GeneratePwdOptions::ECharSetType charSetType) throw() {
  89.     size_t firstIdx = size_t(), lastIdx = size_t();
  90.     switch (charSetType) {
  91.       case GeneratePwdOptions::CST_ALPHA: lastIdx = 'z' - 'a'; break;
  92.       case GeneratePwdOptions::CST_DIGITS: lastIdx = '9' - '0'; break;
  93.       case GeneratePwdOptions::CST_SYMBOLS:
  94.         lastIdx = (sizeof(SPEC_SYMBOLS) / sizeof(*SPEC_SYMBOLS)) - 2U; break; // skip '\0'
  95.     }
  96.     const auto idx = firstIdx + (rand() % (lastIdx - firstIdx + 1U)); // from set
  97.  
  98.     auto actualChar = '\0';
  99.     switch (charSetType) {
  100.       case GeneratePwdOptions::CST_ALPHA:
  101.         // Randomize case (if neeeded)
  102.         actualChar = options.caseSensetive ? (rand() % 2 ? 'A' : 'a') : 'a';
  103.         actualChar += idx;
  104.         ++currCharPerSet[0U];
  105.       break;
  106.       case GeneratePwdOptions::CST_DIGITS:
  107.         actualChar = '0' + idx;
  108.         ++currCharPerSet[1U];
  109.       break;
  110.       case GeneratePwdOptions::CST_SYMBOLS:
  111.         actualChar = SPEC_SYMBOLS[idx];
  112.         ++currCharPerSet[2U];
  113.       break;
  114.     }
  115.     return actualChar;
  116.   };
  117.  
  118.   // Places random count of a random chars from the specified set at random blank positions
  119.   auto addCharsA = [&](const GeneratePwdOptions::ECharSetType charSetType) throw() {
  120.     --charSetLeftCount;
  121.     const auto charCount = getCharCountPerSet();
  122.  
  123.     size_t charIdx = size_t(); // actual idx. in the array
  124.     // Add random chars from the curr. set
  125.     for (size_t charNumber = size_t(); charNumber < charCount; ++charNumber) {
  126.       while (pwdBuf[charIdx = rollCharIdx()]); // roll while NOT free space for the symbol
  127.       pwdBuf[charIdx] = getRandomChar(charSetType);
  128.     }
  129.     charPlacedCount += charCount;
  130.   };
  131.  
  132.   // Places random count of a random chars from the specified set at predefined positions
  133.   //  (sequentially)
  134.   auto addCharsB = [&](const GeneratePwdOptions::ECharSetType charSetType) throw() {
  135.     --charSetLeftCount;
  136.     const auto charCount = getCharCountPerSet();
  137.  
  138.     // Add random chars from the curr. set: O(charCount)
  139.     for (size_t charNumber = size_t(); charNumber < charCount; ++charNumber, ++charPlacedCount) {
  140.       pwdBuf[charPlacedCount] = getRandomChar(charSetType);
  141.     }
  142.   };
  143.  
  144.   switch (Optimized) {
  145.     case false:
  146.       memset(pwdBuf, 0, len + 1U);
  147.       if (options.useDigits) addCharsA(GeneratePwdOptions::ECharSetType::CST_DIGITS);
  148.       if (options.useSymbols) addCharsA(GeneratePwdOptions::ECharSetType::CST_SYMBOLS);
  149.       if (options.useAlpha) addCharsA(GeneratePwdOptions::ECharSetType::CST_ALPHA);
  150.     break;
  151.     default: // true
  152.       if (options.useDigits) addCharsB(GeneratePwdOptions::ECharSetType::CST_DIGITS);
  153.       if (options.useSymbols) addCharsB(GeneratePwdOptions::ECharSetType::CST_SYMBOLS);
  154.       if (options.useAlpha) addCharsB(GeneratePwdOptions::ECharSetType::CST_ALPHA);
  155.       // Random shuffle: O(charPlacedCount)
  156.       for (size_t charNumber = size_t(); charNumber < charPlacedCount; ++charNumber) {
  157.         std::swap(pwdBuf[charNumber], pwdBuf[rollCharIdx()]);
  158.       }
  159.       pwdBuf[charPlacedCount] = '\0';
  160.   }
  161.   return pwdBuf;
  162. }
  163.  
  164. #include <cassert>
  165. #include <iostream>
  166.  
  167. int main(int argc, char* argv[])
  168. {
  169.   static const auto EXEC_COUNT = 55000U;
  170.   char pwdBuf[128U] = {0};
  171.  
  172.   auto time1 = std::chrono::system_clock::now();
  173.   for (size_t idx = size_t(); idx < EXEC_COUNT; ++idx) {
  174.     generatePwd(pwdBuf, sizeof(pwdBuf) - 1U);
  175.   }
  176.   auto time2 = std::chrono::system_clock::now();
  177.   auto count1 = (time2 - time1).count();
  178.   std::cout << "Optimzed version: " << count1 << std::endl;
  179.  
  180.   time1 = std::chrono::system_clock::now();
  181.   for (size_t idx = size_t(); idx < EXEC_COUNT; ++idx) {
  182.     generatePwd<false>(pwdBuf, sizeof(pwdBuf) - 1U);
  183.   }
  184.   time2 = std::chrono::system_clock::now();
  185.   auto count2 = (time2 - time1).count();
  186.   std::cout << "Old version: " << count2 << std::endl;
  187.  
  188.   std::cout << "New (optimzed) version is " << static_cast<double>(count2) / 
  189. 	count1 << " times faster" << std::endl;
  190.  
  191.   return 0;
  192. }
Success #stdin #stdout 4.75s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Optimzed version: 1392535754
Old version: 3381367898
New (optimzed) version is 2.42821 times faster
https://ideone.com/bI8GA6
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!