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