1 #ifndef __INST_GEN_MARKOV_HPP_ 2 #define __INST_GEN_MARKOV_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 "exhaust.hpp" 22 #include "error.hpp" 23 #include "rand.hpp" 24 25 #include "inst_gen.hpp" 26 27 #include <ostream> 28 #include <string> 29 #include <stdio.h> 30 31 /******* CInstGeneratorMarkov declaration ************************/ 32 33 template<unsigned BITS> class CHighLowField { 34 public: CHighLowField()35 CHighLowField() { _data = 0; } set(const unsigned high=0)36 void set(const unsigned high=0) { _data = 0; set_high(high); } get_high() const37 unsigned get_high() const { return _data >> HIGH_SHIFT; } set_high(const unsigned high)38 void set_high(const unsigned high) { _data = (high << HIGH_SHIFT) | (_data & LOW_MASK); } get_low() const39 unsigned get_low() const { return _data & LOW_MASK; } set_low(const unsigned low)40 void set_low(const unsigned low) { _data = (_data & HIGH_MASK) | (low & LOW_MASK); } inc_low()41 void inc_low() { // not super fast, but safeish 42 unsigned low = get_low(); 43 if(low == LOW_MASK) // overflow imminent? 44 PANIC(MISC,"inc past field capability",NULL); 45 set_low(low+1); 46 } used() const47 bool used() const { return (get_low() != 0); } get_data() const48 unsigned get_data() const { return _data; } set_data(const unsigned data)49 void set_data(const unsigned data) { _data = data; } 50 private: 51 static const unsigned intBITS = 31, // zero-based; that was a nasty bug to track down! 52 HIGH_SHIFT = intBITS-BITS, 53 HIGH_MASK = ((1<<BITS)-1) << HIGH_SHIFT, 54 LOW_MASK = ~HIGH_MASK; 55 unsigned _data; 56 }; 57 58 class COpcodeModifier: private CHighLowField<opBITS+moBITS> { 59 public: set(const unsigned i)60 void set(const unsigned i) { set_high(i); set_low(0); } set(const OPCODE op,const MODIFIER mod)61 void set(const OPCODE op,const MODIFIER mod) { set_high(_OP(op,mod)); set_low(0); } get_opcode() const62 OPCODE get_opcode() const { return (OPCODE)(get_high() >> moBITS); } get_opcode_modifier() const63 unsigned get_opcode_modifier() const { return get_high(); } set_opcode(OPCODE op)64 void set_opcode(OPCODE op) { set_high(_OP(op,get_modifier())); } get_modifier() const65 MODIFIER get_modifier() const { return (MODIFIER)(get_high() & moBITS); } set_modifier(MODIFIER mod)66 void set_modifier(MODIFIER mod) { set_high(_OP(get_opcode(),mod)); } get_count() const67 unsigned get_count() const { return get_low(); } set_count(const unsigned count)68 void set_count(const unsigned count) { set_low(count); } inc_count()69 void inc_count() { inc_low(); } used() const70 bool used() const { return (get_low() != 0); } get_literal() const71 unsigned get_literal() const { return get_data(); } set_literal(const unsigned data)72 void set_literal(const unsigned data) { set_data(data); } 73 }; 74 75 template<unsigned BITS> class CHighLowArray { 76 public: 77 typedef CHighLowField<BITS> CData; CHighLowArray()78 CHighLowArray() { 79 _count = 0; 80 _data = 0; 81 } ~CHighLowArray()82 ~CHighLowArray() { 83 delete [] _data; 84 } init(unsigned count)85 void init(unsigned count) { 86 _count = count; 87 delete [] _data; 88 _data = new CData[_count]; 89 } count() const90 unsigned count() const { return _count; } operator [](unsigned index)91 CData &operator[](unsigned index) { 92 check_bounds(index); 93 return _data[index]; 94 } operator [](unsigned index) const95 CData operator[](unsigned index) const { 96 check_bounds(index); 97 return _data[index]; 98 } used() const99 unsigned used() const { 100 unsigned count = 0; 101 for(unsigned i=0; i<_count; i++) 102 if(_data[i].used()) 103 count++; 104 return count; 105 } calc_sum()106 unsigned calc_sum() { 107 _sum = 0; 108 for(unsigned i=0; i<count(); i++) 109 _sum += _data[i].get_low(); 110 return _sum; 111 } sum() const112 unsigned sum() const { return _sum; } suggest() const113 unsigned suggest() const { // get a random one 114 const unsigned TARGET = CRand::irand(sum()); 115 unsigned y = 0; 116 for(unsigned x = 0; x < count(); x++) { 117 y += _data[x].get_low(); 118 if(TARGET < y) 119 return _data[x].get_high(); 120 } 121 PANIC(MISC,"roulette off end of CHighLowArray suggest",NULL); 122 } 123 private: 124 unsigned _count, 125 _sum; 126 CData *_data; check_bounds(unsigned index)127 void check_bounds(unsigned index) { 128 if((index < 0) || (index >= _count)) 129 PANIC(MISC,"array index out of bounds",NULL); 130 } 131 }; 132 133 class CInstGeneratorMarkov: public CInstGenerator { 134 public: 135 CInstGeneratorMarkov(); 136 virtual ~CInstGeneratorMarkov(); 137 // actual query points 138 virtual void suggest_instruction(insn_t &instruction,const MODE mode); 139 // and saving 140 virtual void write_ini(std::ostream &os); 141 virtual void write_override_ini(std::ostream &os,const CInstGenerator *parent); 142 // for creating new lookup files 143 void init(const unsigned coresize); 144 void load(const char *binfilename); 145 void append(const char *rcfilename); 146 void save(const char *binfilename) const; 147 void dump(std::ostream &out) const; 148 protected: 149 virtual void read_ini_impl(INIFile &ini); 150 virtual CInstGenerator *read_override_ini_impl(INIFile &ini); 151 private: 152 static const unsigned 153 OPCODE_MODIFIER_LAST = _OP(OPCODE_LAST,MODIFIER_LAST), 154 INVALID_INDEX = ~0; 155 std::string _filename; 156 bool readonly; 157 unsigned CORESIZE, 158 opcodes, 159 opcode_modifiers; 160 friend struct CFreq; 161 struct CFreq { 162 COpcodeModifier key; 163 // markov for next instruction 164 unsigned markovs, 165 opcode_modifiers; 166 COpcodeModifier *markov; used_markovsCInstGeneratorMarkov::CFreq167 unsigned used_markovs() const { 168 unsigned count = 0; 169 for(unsigned i=0; i<markovs; i++) 170 if(markov[i].used()) 171 count++; 172 return count; 173 } 174 unsigned suggest_opcode_modifier() const; 175 // stuff for this opcode/modifier combo 176 CHighLowArray<mBITS> addrmode_a, addrmode_b; 177 CHighLowArray<16> a, b; 178 } *opcode; used_opcodes() const179 unsigned used_opcodes() const { 180 unsigned count = 0; 181 for(unsigned i=0; i<opcodes; i++) 182 if(opcode[i].key.used()) 183 count++; 184 return count; 185 } 186 static const float DEFAULT_DAT; 187 float _dat; // probability of a dat being allowed 188 bool dat() const; // test that this can be a dat 189 unsigned opcode_modifier_2_index(const unsigned opcode_modifier) const; 190 // random generators 191 unsigned suggest_opcode_modifier() const; // returns an index 192 // loading stuff 193 void record(const OPCODE opcode_prev,const MODIFIER mod_prev,const insn_st &code); 194 void clear(); write(const unsigned x,FILE * f) const195 void write(const unsigned x,FILE *f) const { 196 if(fwrite(&x,sizeof(x),1,f) != 1) 197 PANIC(MISC,"Could not write to opcode lookup file",NULL); 198 } read(unsigned & x,FILE * f) const199 void read(unsigned &x,FILE *f) const { 200 if(fread(&x,sizeof(x),1,f) != 1) 201 PANIC(MISC,"Could not read from opcode lookup file",NULL); 202 } 203 }; 204 205 #endif // ifndef __INST_GEN_MARKOV_HPP_ 206 207