1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 #include "ruletreealgo.h"
5 #include "util.h" // for lifegetuserrules, lifegetrulesdir, lifewarning
6 #include <stdlib.h>
7 // for case-insensitive string comparison
8 #include <string.h>
9 #ifndef WIN32
10 #define stricmp strcasecmp
11 #endif
12 #include <vector>
13 #include <cstdio>
14 #include <string>
15 using namespace std ;
16
IsDefaultRule(const char * rulename)17 bool ruletreealgo::IsDefaultRule(const char* rulename)
18 {
19 // nicer to check for different versions of default rule
20 return (stricmp(rulename, "B3/S23") == 0 ||
21 stricmp(rulename, "B3S23") == 0 ||
22 strcmp(rulename, "23/3") == 0);
23 }
24
25 static FILE* static_rulefile = NULL;
26 static int static_lineno = 0;
27 static char static_endchar = 0;
28
LoadTree(FILE * rulefile,int lineno,char endchar,const char * s)29 const char* ruletreealgo::LoadTree(FILE* rulefile, int lineno, char endchar, const char* s)
30 {
31 // set static vars so setrule() will load tree data from .rule file
32 static_rulefile = rulefile;
33 static_lineno = lineno;
34 static_endchar = endchar;
35
36 const char* err = setrule(s);
37
38 // reset static vars
39 static_rulefile = NULL;
40 static_lineno = 0;
41 static_endchar = 0;
42
43 return err;
44 }
45
NumCellStates()46 int ruletreealgo::NumCellStates() {
47 return num_states ;
48 }
49
50 const int MAXFILELEN = 4096 ;
51
52 /* provide the ability to load the default rule without requiring a file */
53 static const char *defaultRuleData[] = {
54 "num_states=2", "num_neighbors=8", "num_nodes=32",
55 "1 0 0", "2 0 0", "1 0 1", "2 0 2", "3 1 3", "1 1 1", "2 2 5", "3 3 6",
56 "4 4 7", "2 5 0", "3 6 9", "4 7 10", "5 8 11", "3 9 1", "4 10 13",
57 "5 11 14", "6 12 15", "3 1 1", "4 13 17", "5 14 18", "6 15 19",
58 "7 16 20", "4 17 17", "5 18 22", "6 19 23", "7 20 24", "8 21 25",
59 "5 22 22", "6 23 27", "7 24 28", "8 25 29", "9 26 30", 0 } ;
60
OpenTreeFile(const char * rule,const char * dir,char * path)61 static FILE *OpenTreeFile(const char *rule, const char *dir, char *path)
62 {
63 // look for rule.tree in given dir and set path
64 if (strlen(dir) + strlen(rule) + 15 > (unsigned int)MAXFILELEN) {
65 lifewarning("Path too long") ;
66 return NULL ;
67 }
68 sprintf(path, "%s%s.tree", dir, rule) ;
69 // change "dangerous" characters to underscores
70 for (char *p=path + strlen(dir); *p; p++)
71 if (*p == '/' || *p == '\\') *p = '_' ;
72 return fopen(path, "r") ;
73 }
74
setrule(const char * s)75 const char* ruletreealgo::setrule(const char* s) {
76
77 const char *colonptr = strchr(s, ':');
78 string rule_name(s);
79 if (colonptr)
80 rule_name.assign(s,colonptr);
81
82 char strbuf[MAXFILELEN+1] ;
83 FILE *f = 0 ;
84 linereader lr(0) ;
85 int lineno = 0 ;
86
87 bool isDefaultRule = IsDefaultRule(rule_name.c_str()) ;
88 if (isDefaultRule) {
89 // no need to read tree data from a file
90 } else if (static_rulefile) {
91 // read tree data from currently open .rule file
92 lr.setfile(static_rulefile);
93 lr.setcloseonfree();
94 lineno = static_lineno;
95 } else {
96 if (strlen(rule_name.c_str()) >= (unsigned int)MAXRULESIZE) {
97 return "Rule length too long" ;
98 }
99 // look for rule.tree in user's rules dir then in Golly's rules dir
100 f = OpenTreeFile(rule_name.c_str(), lifegetuserrules(), strbuf);
101 if (f == 0)
102 f = OpenTreeFile(rule_name.c_str(), lifegetrulesdir(), strbuf);
103 if (f == 0) {
104 return "File not found" ;
105 }
106 lr.setfile(f) ;
107 lr.setcloseonfree() ;
108 }
109
110 // check for rule suffix like ":T200,100" to specify a bounded universe
111 if (colonptr) {
112 const char* err = setgridsize(colonptr);
113 if (err) return err;
114 } else {
115 // universe is unbounded
116 gridwd = 0;
117 gridht = 0;
118 }
119
120 int mnum_states=-1, mnum_neighbors=-1, mnum_nodes=-1 ;
121 vector<int> dat ;
122 vector<state> datb ;
123 vector<int> noff ;
124 vector<int> nodelev ;
125 int lev = 1000 ;
126 for (;;) {
127 if (isDefaultRule) {
128 if (defaultRuleData[lineno] == 0)
129 break ;
130 strcpy(strbuf, defaultRuleData[lineno]) ;
131 } else {
132 if (lr.fgets(strbuf, MAXFILELEN) == 0)
133 break ;
134 if (static_rulefile && strbuf[0] == static_endchar)
135 break;
136 }
137 lineno++ ;
138 if (strbuf[0] != '#' && strbuf[0] != 0 &&
139 sscanf(strbuf, " num_states = %d", &mnum_states) != 1 &&
140 sscanf(strbuf, " num_neighbors = %d", &mnum_neighbors) != 1 &&
141 sscanf(strbuf, " num_nodes = %d", &mnum_nodes) != 1) {
142 if (mnum_states < 2 || mnum_states > 256 ||
143 (mnum_neighbors != 4 && mnum_neighbors != 8) ||
144 mnum_nodes < mnum_neighbors || mnum_nodes > 100000000) {
145 return "Bad basic values" ;
146 }
147 if (strbuf[0] < '1' || strbuf[0] > '0' + 1 + mnum_neighbors) {
148 return "Bad line in tree data 1" ;
149 }
150 lev = strbuf[0] - '0' ;
151 int vcnt = 0 ;
152 char *p = strbuf + 1 ;
153 if (lev == 1)
154 noff.push_back((int)(datb.size())) ;
155 else
156 noff.push_back((int)(dat.size())) ;
157 nodelev.push_back(lev) ;
158 while (*p) {
159 while (*p && *p <= ' ')
160 p++ ;
161 int v = 0 ;
162 while (*p > ' ') {
163 if (*p < '0' || *p > '9') {
164 return "Bad line in tree data 2" ;
165 }
166 v = v * 10 + *p++ - '0' ;
167 }
168 if (lev == 1) {
169 if (v < 0 || v >= mnum_states) {
170 return "Bad state value in tree data" ;
171 }
172 datb.push_back((state)v) ;
173 } else {
174 if (v < 0 || ((unsigned int)v) >= noff.size()) {
175 return "Bad node value in tree data" ;
176 }
177 if (nodelev[v] != lev - 1) {
178 return "Bad node pointer does not point to one level down" ;
179 }
180 dat.push_back(noff[v]) ;
181 }
182 vcnt++ ;
183 }
184 if (vcnt != mnum_states) {
185 return "Bad number of values on tree data line" ;
186 }
187 }
188 }
189
190 if (dat.size() + datb.size() != (unsigned int)(mnum_nodes * mnum_states))
191 return "Bad count of values in tree data" ;
192 if (lev != mnum_neighbors + 1)
193 return "Bad last node (wrong level)" ;
194 int *na = (int*)calloc(sizeof(int), dat.size()) ;
195 state *nb = (state*)calloc(sizeof(state), datb.size()) ;
196 if (na == 0 || nb == 0)
197 return "Out of memory in tree allocation" ;
198 if (a)
199 free(a) ;
200 if (b)
201 free(b) ;
202 num_nodes = mnum_nodes ;
203 num_states = mnum_states ;
204 num_neighbors = mnum_neighbors ;
205 for (unsigned int i=0; i<dat.size(); i++)
206 na[i] = dat[i] ;
207 for (unsigned int i=0; i<datb.size(); i++)
208 nb[i] = datb[i] ;
209 a = na ;
210 b = nb ;
211 base = noff[noff.size()-1] ;
212 maxCellStates = num_states ;
213 ghashbase::setrule(rule_name.c_str()) ;
214
215 // set canonical rule string returned by getrule()
216 strcpy(rule,rule_name.c_str()) ;
217 if (gridwd > 0 || gridht > 0) {
218 // setgridsize() was successfully called above, so append suffix
219 int len = (int)strlen(rule) ;
220 const char* bounds = canonicalsuffix() ;
221 int i = 0 ;
222 while (bounds[i]) rule[len++] = bounds[i++] ;
223 rule[len] = 0 ;
224 }
225
226 return 0 ;
227 }
228
getrule()229 const char* ruletreealgo::getrule() {
230 return rule ;
231 }
232
DefaultRule()233 const char* ruletreealgo::DefaultRule() {
234 return "B3/S23" ;
235 }
236
ruletreealgo()237 ruletreealgo::ruletreealgo() : ghashbase(), a(0), base(0), b(0),
238 num_neighbors(0),
239 num_states(0), num_nodes(0) {
240 rule[0] = 0 ;
241 }
242
~ruletreealgo()243 ruletreealgo::~ruletreealgo() {
244 if (a != 0) {
245 free(a) ;
246 a = 0 ;
247 }
248 if (b != 0) {
249 free(b) ;
250 b = 0 ;
251 }
252 }
253
slowcalc(state nw,state n,state ne,state w,state c,state e,state sw,state s,state se)254 state ruletreealgo::slowcalc(state nw, state n, state ne, state w, state c, state e,
255 state sw, state s, state se) {
256 if (num_neighbors == 4)
257 return b[a[a[a[a[base+n]+w]+e]+s]+c] ;
258 else
259 return b[a[a[a[a[a[a[a[a[base+nw]+ne]+sw]+se]+n]+w]+e]+s]+c] ;
260 }
261
creator()262 static lifealgo *creator() { return new ruletreealgo() ; }
263
doInitializeAlgoInfo(staticAlgoInfo & ai)264 void ruletreealgo::doInitializeAlgoInfo(staticAlgoInfo &ai) {
265 ghashbase::doInitializeAlgoInfo(ai) ;
266 ai.setAlgorithmName("RuleTree") ;
267 ai.setAlgorithmCreator(&creator) ;
268 ai.minstates = 2 ;
269 ai.maxstates = 256 ;
270 // init default color scheme
271 ai.defgradient = true; // use gradient
272 ai.defr1 = 255; // start color = red
273 ai.defg1 = 0;
274 ai.defb1 = 0;
275 ai.defr2 = 255; // end color = yellow
276 ai.defg2 = 255;
277 ai.defb2 = 0;
278 // if not using gradient then set all states to white
279 for (int i=0; i<256; i++)
280 ai.defr[i] = ai.defg[i] = ai.defb[i] = 255;
281 }
282