eao197

md5_bruteforce2 solution with SObjectizer-5.5.5-alpha

Apr 13th, 2015
236
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <chrono>
  4. #include <iterator>
  5. #include <list>
  6. #include <map>
  7. #include <regex>
  8. #include <cctype>
  9.  
  10. #include <so_5/all.hpp>
  11.  
  12. #include <md5_cpp11/all.hpp>
  13.  
  14. #include <various_helpers_1/ensure.hpp>
  15.  
  16. using namespace std;
  17. using namespace std::chrono;
  18.  
  19. using namespace so_5;
  20. using namespace so_5::rt;
  21. using namespace so_5::disp;
  22.  
  23. // Just an alias for distinguish between ordinary strings and passwords.
  24. using password_t = string;
  25.  
  26. // Description of one task.
  27. struct task_t
  28. {
  29.     string m_md5; // MD5 value to find.
  30.     password_t m_left; // The left (inclusive) border of range.
  31.     password_t m_right; // The right (inclusive) border of range.
  32. };
  33.  
  34. //
  35. // Messages
  36. //
  37.  
  38. // Process next task.
  39. using msg_process_line = tuple_as_message_t< mtag<0>, string >;
  40. // Successful result of task processing (worker,password).
  41. using msg_password_found = tuple_as_message_t< mtag<1>, string, string >;
  42. // Unsuccessful result of task processing (worker).
  43. using msg_password_not_found = tuple_as_message_t< mtag<2>, string >;
  44. // Request for new task from stream.
  45. struct msg_load_next : public so_5::rt::signal_t {};
  46. // Signal about end-of-stream (no more task will be received).
  47. struct msg_no_more_lines : public so_5::rt::signal_t {};
  48.  
  49. //
  50. // Worker agent.
  51. //
  52. class worker_t : public agent_t
  53. {
  54. public :
  55.     worker_t( context_t ctx, string self_id, mbox_t manager )
  56.         :   agent_t( ctx )
  57.         ,   m_self_id( self_id )
  58.         ,   m_self_mbox( so_environment().create_local_mbox( self_id ) )
  59.         ,   m_manager( manager )
  60.     {}
  61.  
  62.     virtual void so_define_agent() override
  63.     {
  64.         so_subscribe( m_self_mbox ).event( &worker_t::evt_process_line );
  65.     }
  66.  
  67. private :
  68.     static const regex m_line_format;
  69.  
  70.     const string m_self_id;
  71.     const mbox_t m_self_mbox;
  72.     const mbox_t m_manager;
  73.  
  74.     void evt_process_line( const msg_process_line & evt )
  75.     {
  76.         const auto task = parse_task( get<0>( evt ) );
  77.         const auto etalon = md5_cpp11::from_hex_string( task.m_md5 );
  78.  
  79.         auto pw = task.m_left;
  80.         auto stop_point = [&] { auto r = task.m_right; next_pass(r); return r; }();
  81.         // This form of loop is important because there could be ranges
  82.         // like [0000,zzzz] for which stop_point will be 0000.
  83.         // Because of that we must do at least one iteration.
  84.         do
  85.         {
  86.             if( md5_cpp11::make_digest( pw ) != etalon )
  87.                 next_pass( pw );
  88.             else
  89.             {
  90.                 so_5::send< msg_password_found >( m_manager, m_self_id, pw );
  91.                 return;
  92.             }
  93.         } while( pw != stop_point );
  94.  
  95.         so_5::send< msg_password_not_found >( m_manager, m_self_id );
  96.     }
  97.  
  98.     static task_t parse_task( const string & line )
  99.     {
  100.         smatch parts;
  101.         const auto match_result = regex_match( line, parts, m_line_format );
  102.         ensure( match_result, "task line has wrong format, line: '" + line + "'" );
  103.         const task_t task{ parts.str(1), parts.str(2), parts.str(3) };
  104.         ensure_valid_password_range( task.m_left, task.m_right );
  105.  
  106.         return task;
  107.     }
  108.  
  109.     static void ensure_valid_password_range(
  110.         const password_t & left, const password_t & right )
  111.     {
  112.         ensure( left.size() == right.size(),
  113.             "range borders must be same size [" + left + ", " + right + "]" );
  114.  
  115.         auto valid_alphabet = []( const password_t & p ) {
  116.             return end(p) == find_if_not( begin(p), end(p),
  117.                     []( password_t::value_type ch ) {
  118.                         return (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z');
  119.                     } );
  120.         };
  121.         ensure( valid_alphabet( left ), "illegal char in left border: " + left );
  122.         ensure( valid_alphabet( right ), "illegal char in right border: " + right );
  123.  
  124.         ensure( !(right < left),
  125.             "invalid range (left must not be "
  126.                     "greater than right): [" + left + ", " + right + "]" );
  127.     }
  128.  
  129.     static password_t::value_type next_byte( password_t::value_type b )
  130.     {
  131.         switch( b )
  132.         {
  133.             case 'z' : return '0';
  134.             case '9' : return 'a';
  135.             default : return b + 1;
  136.         }
  137.     }
  138.  
  139.     static void next_pass( password_t & p )
  140.     {
  141.         for( auto e = p.rbegin(); e != p.rend(); ++e )
  142.         {
  143.             *e = next_byte( *e );
  144.             if( '0' != *e )
  145.                 break;
  146.         }
  147.     }
  148. };
  149.  
  150. const regex worker_t::m_line_format( "^\\s*(\\S+)\\s+(\\S+)\\s+(\\S+)\\s*$" );
  151.  
  152. //
  153. // Task loader agent.
  154. //
  155. class input_loader_t : public agent_t
  156. {
  157. public :
  158.     input_loader_t( context_t ctx )
  159.         :   agent_t( ctx )
  160.         {}
  161.  
  162.     void set_manager( const mbox_t & manager )
  163.     {
  164.         m_manager = manager;
  165.     }
  166.  
  167.     virtual void so_define_agent() override
  168.     {
  169.         // In normal state will try to load next line.
  170.         so_default_state().event< msg_load_next >( &input_loader_t::evt_load_next );
  171.         // Sends NO_MORE_TASK signal immediatelly if EOF reached.
  172.         st_eof.event< msg_load_next >( [this] { send_eof_signal(); } );
  173.     }
  174.  
  175. private :
  176.     const state_t st_eof = so_make_state( "EOF" );
  177.     mbox_t m_manager;
  178.  
  179.     void evt_load_next()
  180.     {
  181.         bool read_more;
  182.         do {
  183.             read_more = false;
  184.  
  185.             string line;
  186.             if( getline( cin, line ) )
  187.             {
  188.                 strip_spaces( line );
  189.                 if( line.empty() )
  190.                     read_more = true;
  191.                 else
  192.                     send< msg_process_line >( m_manager, line );
  193.             }
  194.             else
  195.             {
  196.                 this >>= st_eof;
  197.                 send_eof_signal();
  198.             }
  199.         } while( read_more );
  200.     }
  201.  
  202.     void send_eof_signal()
  203.     {
  204.         send< msg_no_more_lines >( m_manager );
  205.     }
  206.  
  207.     static void strip_spaces( string & line )
  208.     {
  209.         auto space = []( string::value_type c ) { return isspace( c ); };
  210.  
  211.         auto s = find_if_not( line.begin(), line.end(), space );
  212.         auto e = find_if_not( line.rbegin(), string::reverse_iterator(s), space ).base();
  213.         line = string( s, e );
  214.     }
  215. };
  216.  
  217. //
  218. // manager_t
  219. //
  220. class manager_t : public agent_t
  221. {
  222. public :
  223.     manager_t( context_t ctx, mbox_t input_loader, size_t worker_count )
  224.         :   agent_t( ctx )
  225.         ,   m_input_loader( input_loader )
  226.         ,   m_worker_count( worker_count )
  227.         ,   m_worker_disp(
  228.                 thread_pool::create_private_disp(
  229.                         so_environment(),
  230.                         worker_count ) )
  231.     {}
  232.  
  233.     virtual void so_define_agent() override
  234.     {
  235.         so_subscribe_self()
  236.             .event( &manager_t::evt_next_line_received )
  237.             .event< msg_no_more_lines >( &manager_t::evt_no_more_lines )
  238.             .event( &manager_t::evt_password_found )
  239.             .event( &manager_t::evt_password_not_found )
  240.             .event( &manager_t::evt_worker_coop_started )
  241.             .event( &manager_t::evt_worker_coop_destroyed );
  242.     }
  243.  
  244.     virtual void so_evt_start() override
  245.     {
  246.         for( size_t i = 0; i != m_worker_count; ++i )
  247.             create_new_worker();
  248.     }
  249.  
  250. private :
  251.     const mbox_t m_input_loader;
  252.  
  253.     const size_t m_worker_count;
  254.     size_t m_worker_ordinal = { 0 };
  255.  
  256.     // Dedicated thread pool for workers.
  257.     thread_pool::private_dispatcher_handle_t m_worker_disp;
  258.  
  259.     // List of free workers.
  260.     // Items from this list will be extracted when next_task_received
  261.     // arrived and placed back after getting task processing result.
  262.     list< string > m_free_workers;
  263.  
  264.     // Map of scheduled tasks (worker_id -> line).
  265.     map< string, string > m_scheduled_lines;
  266.  
  267.     void evt_next_line_received( const msg_process_line & evt )
  268.     {
  269.         auto worker_id = m_free_workers.front();
  270.         m_free_workers.pop_front();
  271.  
  272.         // We must know what task is scheduled to the worker.
  273.         const auto & line = get<0>( evt );
  274.         m_scheduled_lines[ worker_id ] = line;
  275.  
  276.         cout << "*** " << line << " scheduled to " << worker_id << endl;
  277.  
  278.         send< msg_process_line >(
  279.                 so_environment().create_local_mbox( worker_id ),
  280.                 line );
  281.     }
  282.  
  283.     void evt_no_more_lines()
  284.     {
  285.         if( m_scheduled_lines.empty() )
  286.             // No more tasks to wait. Work can be finished.
  287.             so_deregister_agent_coop_normally();
  288.     }
  289.  
  290.     void evt_password_found( const msg_password_found & evt )
  291.     {
  292.         handle_worker_result( get<0>(evt), get<1>(evt) );
  293.     }
  294.  
  295.     void evt_password_not_found( const msg_password_not_found & evt )
  296.     {
  297.         handle_worker_result( get<0>(evt), "NOT FOUND" );
  298.     }
  299.  
  300.     void evt_worker_coop_started( const msg_coop_registered & evt )
  301.     {
  302.         // New worker available.
  303.         m_free_workers.push_back( evt.m_coop_name );
  304.         // We need new task for it.
  305.         request_next_task();
  306.     }
  307.  
  308.     void evt_worker_coop_destroyed( const msg_coop_deregistered & evt )
  309.     {
  310.         auto it = m_scheduled_lines.find( evt.m_coop_name );
  311.         if( it != m_scheduled_lines.end() )
  312.         {
  313.             // Cooperation destroyed during task processing!
  314.             cerr << "TASK(" << it->second << ") STOPPED! "
  315.                 << ", deregistration reason: " << evt.m_reason.reason()
  316.                 << endl;
  317.  
  318.             m_scheduled_lines.erase( it );
  319.  
  320.             create_new_worker();
  321.         }
  322.     }
  323.  
  324.     void create_new_worker()
  325.     {
  326.         const auto worker_id = "worker-" + to_string( m_worker_ordinal++ );
  327.         introduce_child_coop( *this,
  328.             // Worker id will be name of the worker cooperation.
  329.             worker_id,
  330.             // Worker will work on thread pool.
  331.             m_worker_disp->binder( thread_pool::params_t{} ),
  332.             [&]( agent_coop_t & coop ) {
  333.                 // We must receive notifications about start and deregistration
  334.                 // of this cooperation.
  335.                 coop.add_reg_notificator(
  336.                         make_coop_reg_notificator( so_direct_mbox() ) );
  337.                 coop.add_dereg_notificator(
  338.                         make_coop_dereg_notificator( so_direct_mbox() ) );
  339.                 // Cooperation with agent must be deregistered in the case of
  340.                 // exception.
  341.                 coop.set_exception_reaction(
  342.                         exception_reaction_t::deregister_coop_on_exception );
  343.                 // The single agent in the cooperation.
  344.                 coop.make_agent< worker_t >( worker_id, so_direct_mbox() );
  345.             } );
  346.     }
  347.  
  348.     void handle_worker_result(
  349.         const string & worker_id, const string & result )
  350.     {
  351.         auto it = m_scheduled_lines.find( worker_id );
  352.         if( it != m_scheduled_lines.end() )
  353.         {
  354.             cout << "result(" << it->second << "): " << result << endl;
  355.             m_scheduled_lines.erase( it );
  356.         }
  357.         else
  358.             throw std::runtime_error(
  359.                     "UNEXPECTED RESPONSE! worker_id: " + worker_id +
  360.                     ", result: " );
  361.  
  362.         m_free_workers.push_back( worker_id );
  363.         request_next_task();
  364.     }
  365.  
  366.     void request_next_task()
  367.     {
  368.         send< msg_load_next >( m_input_loader );
  369.     }
  370. };
  371.  
  372. void run( environment_t & env, size_t desired_workers )
  373. {
  374.     const auto actual_workers = desired_workers ? desired_workers :
  375.             thread::hardware_concurrency();
  376.  
  377.     env.introduce_coop( [&]( agent_coop_t & coop ) {
  378.             // Task loader must work on its own thread.
  379.             auto input_loader = coop.make_agent_with_binder< input_loader_t >(
  380.                     one_thread::create_private_disp( env )->binder() );
  381.             // Manager will work on the default dispatcher.
  382.             auto manager = coop.make_agent< manager_t >(
  383.                     // Manager must be bound to input_loader.
  384.                     input_loader->so_direct_mbox(), actual_workers );
  385.             // And input_loader must be bound to manager.
  386.             input_loader->set_manager( manager->so_direct_mbox() );
  387.         } );
  388. }
  389.  
  390. size_t detect_workers_count( int argc, char ** argv )
  391. {
  392.     if( 2 == argc )
  393.         return stoul( argv[ 1 ] );
  394.     else
  395.         return 0;
  396. }
  397.  
  398. double time_spent( const steady_clock::time_point s )
  399. {
  400.     const auto e = steady_clock::now();
  401.     return duration_cast< milliseconds >( e - s ).count() / 1000.0;
  402. }
  403.  
  404. int main( int argc, char ** argv )
  405. {
  406.     try
  407.     {
  408.         auto workers = detect_workers_count( argc, argv );
  409.  
  410.         const auto started_at = steady_clock::now();
  411.  
  412.         so_5::launch( [workers]( environment_t & env ) {
  413.                 run( env, workers );
  414.             } );
  415.  
  416.         cout << "time: " << time_spent( started_at ) << "s" << endl;
  417.  
  418.         return 0;
  419.     }
  420.     catch( const exception & x )
  421.     {
  422.         cerr << "Exception: " << x.what() << endl;
  423.     }
  424.  
  425.     return 2;
  426. }
RAW Paste Data