1 #ifndef __INST_GEN_MARKOV_2_HPP_ 2 #define __INST_GEN_MARKOV_2_HPP_ 3 4 /* "Species" - a CoreWars evolver. Copyright (C) 2003 'Varfar' 5 * 6 * This program is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License as published by the Free 8 * Software Foundation; either version 1, or (at your option) any later 9 * version. 10 * 11 * This program is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for 14 * more details. 15 * 16 * You should have received a copy of the GNU General Public License along 17 * with this program; if not, write to the Free Software Foundation, Inc., 18 * 675 Mass Ave, Cambridge, MA 02139, USA. 19 */ 20 21 #include "inst_gen.hpp" 22 #include "exhaust.hpp" 23 #include "warrior.hpp" 24 25 #include <iostream> 26 #include <list> 27 28 /** 29 * the datastructures for efficiently collecting and collating markovs is so 30 * different compared to those for recalling them, that I have implemented two 31 * different classes for the two purposes: CMutableMarkov and CImmutableMarkov 32 **/ 33 34 class CInstGeneratorMarkov2: public CInstGenerator { 35 public: 36 // construction/destruction 37 CInstGeneratorMarkov2(); // creates a special empty one to be read from ini 38 CInstGeneratorMarkov2(const unsigned coresize); // creates a mutable markov 39 CInstGeneratorMarkov2(const char *lookup_filename); // creates an immutable markov 40 void load(const char *lookup_filename); 41 // actual query points 42 virtual void suggest_instruction(insn_t &instruction,const MODE mode); 43 // learning 44 void learn(const std::string rc_filename); 45 void cull(const unsigned threshold); 46 void prepare(); // mostly sorts 47 void save(const std::string lookup_filename); 48 // and saving 49 virtual void write_ini(std::ostream &os); 50 virtual void write_override_ini(std::ostream &os,const CInstGenerator *parent); 51 // trivia 52 void dump(std::ostream &out); // list *all* markovs 53 protected: 54 virtual void read_ini_impl(INIFile &ini); 55 virtual CInstGenerator *read_override_ini_impl(INIFile &ini); 56 private: 57 static const unsigned FILE_VERSION = 0x10F4; 58 bool _mutable; 59 unsigned _coresize, _threshold; 60 std::string _filename; 61 // shared bases 62 class CStartBase { 63 public: 64 virtual void dump(std::ostream &out) = 0; 65 protected: 66 struct TEntry { 67 // construction TEntryCInstGeneratorMarkov2::CStartBase::TEntry68 TEntry() {} TEntryCInstGeneratorMarkov2::CStartBase::TEntry69 TEntry(const u16_t in): _in(in), _count(1) {} 70 // for sorting compCInstGeneratorMarkov2::CStartBase::TEntry71 static bool comp(const TEntry &a,const TEntry &b) { return a._in < b._in; } 72 // fields, public 73 u16_t _in; 74 unsigned _count; 75 }; 76 }; 77 // mutable declarations 78 class CMutableStart: public CStartBase { 79 public: 80 void learn(const u16_t in); 81 void prepare(); 82 void save(std::ostream &out); 83 virtual void dump(std::ostream &out); 84 private: 85 typedef std::list<TEntry> TStart; 86 typedef TStart::iterator TStartIter; 87 TStart _data; 88 } *_mutable_start; 89 friend class CMutableStart; 90 class CMutableMarkov { 91 public: 92 // construction/destruction 93 CMutableMarkov(); // default is only appropriate for root 94 CMutableMarkov(const u16_t in); 95 ~CMutableMarkov(); 96 // getters in() const97 u16_t in() const { return _count; } // the instruction, packing opcode,modifier,addressing modes count() const98 unsigned count() const { return _count; } 99 CMutableMarkov *get(const u16_t in); // this can be a setter too 100 // setters inc()101 void inc() { _count++; } 102 void cull(const unsigned threshold); 103 void cull_leaves(); 104 void save(std::ostream &out); 105 // for sorting 106 void prepare(); operator <(const CMutableMarkov & other) const107 bool operator<(const CMutableMarkov &other) const { return in() < other.in(); } 108 // trivia 109 void dump(std::ostream &out); 110 private: 111 typedef std::list<CMutableMarkov*> TChain; 112 typedef TChain::iterator TChainIter; 113 u16_t _in; 114 unsigned _count; 115 TChain _chain; is_leaf() const116 bool is_leaf() const { return (0 == _chain.size()); } 117 unsigned count_leaves(); 118 void dump(std::ostream &out,std::string &path,const int len = 0); comp(const CMutableMarkov * a,const CMutableMarkov * b)119 static bool comp(const CMutableMarkov *a,const CMutableMarkov *b) { return *a < *b; } 120 } *_mutable_root; 121 friend class CMutableMarkov; 122 // immutable declarations 123 class CImmutableStart: public CStartBase { 124 public: 125 CImmutableStart(std::istream &in,const CInstGenerator *opcode_allowed); 126 virtual void dump(std::ostream &out); 127 u16_t suggest() const; 128 private: 129 unsigned _count; 130 u16_t _size; 131 TEntry *_data; 132 } *_immutable_start; 133 friend class CImmutableStart; 134 class CImmutableMarkov { 135 public: 136 typedef std::list<const CImmutableMarkov*> TMarkovList; 137 // construction/destruction 138 CImmutableMarkov(); // default is only appropriate for root 139 CImmutableMarkov(std::istream &in,const CInstGenerator *opcode_allowed); 140 ~CImmutableMarkov(); 141 // getters in() const142 u16_t in() const { return _in; } // the instruction, packing opcode,modifier,addressing modes count() const143 unsigned count() const { return _count; } 144 CImmutableMarkov *get(const u16_t in) const; // null if not found 145 CImmutableMarkov *suggest() const; // null if chain is to end 146 // suggestion 147 void suggest(TMarkovList &ret,unsigned &sumprob,const u16_t before,const u16_t after,const bool is_after = false) const; // populate the list with all markovs that are between these two operands; maintain count 148 // trivia 149 void dump(std::ostream &out) const; 150 private: 151 u16_t _in, 152 _size; // well, how many can there be? ;-) 153 unsigned _count; 154 CImmutableMarkov **_chain; 155 unsigned count_leaves() const; 156 void dump(std::ostream &out,std::string &path,const int len = 0) const; 157 } *_immutable_root; 158 friend class CImmutableMarkov; 159 CImmutableMarkov *suggest(const u16_t before,const u16_t after) const; // suggest an opcode that is between before and after 160 // utilities 161 static void dump(std::ostream &out,const u16_t in); 162 static void bwrite_u16_t(std::ostream &out,const u16_t i); 163 static void bwrite_unsigned(std::ostream &out,const unsigned i); 164 static u16_t bread_u16_t(std::istream &in); 165 static unsigned bread_unsigned(std::istream &in); 166 }; 167 168 #endif // ifndef __INST_GEN_MARKOV_2_HPP__ 169 170