1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
// This file is part of Golly.
// See docs/License.html for the copyright notice.
#ifndef GHASHBASE_H
#define GHASHBASE_H
#include "lifealgo.h"
#include "liferules.h"
#include "util.h"
/*
* This class forms the basis of all hashlife-type algorithms except
* the highly-optimized hlifealgo (which is most appropriate for
* simple two-state automata). This more generalized class is used
* for multi-state algorithms.
*/
/**
* The size of a state. Unsigned char works for now.
*/
typedef unsigned char state ;
/**
* Nodes, like the standard hlifealgo nodes.
*/
struct ghnode {
ghnode *next ; /* hash link */
ghnode *nw, *ne, *sw, *se ; /* constant; nw != 0 means nonjleaf */
ghnode *res ; /* cache */
} ;
/*
* Leaves, like the standard hlifealgo leaves.
*/
struct ghleaf {
ghnode *next ; /* hash link */
ghnode *isghnode ; /* must always be zero for leaves */
state nw, ne, sw, se ; /* constant */
bigint leafpop ; /* how many set bits */
} ;
/*
* If it is a struct ghnode, this returns a non-zero value, otherwise it
* returns a zero value.
*/
#define is_ghnode(n) (((ghnode *)(n))->nw)
/*
* For explicit prefetching we retain some state for our lookup
* routines.
*/
#ifdef USEPREFETCH
struct ghsetup_t {
g_uintptr_t h ;
struct ghnode *nw, *ne, *sw, *se ;
void prefetch(struct ghnode **addr) const { PREFETCH(addr) ; }
} ;
#endif
/**
* Our ghashbase class. Note that this is an abstract class; you need
* to expand specific methods to specialize it for a particular multi-state
* automata.
*/
class ghashbase : public lifealgo {
public:
ghashbase() ;
virtual ~ghashbase() ;
// This is the method that computes the next generation, slowly.
// This should be overridden by a deriving class.
virtual state slowcalc(state nw, state n, state ne, state w, state c,
state e, state sw, state s, state se) = 0 ;
// note that for ghashbase, clearall() releases no memory; it retains
// the full cache information but just sets the current pattern to
// the empty pattern.
virtual void clearall() ;
virtual int setcell(int x, int y, int newstate) ;
virtual int getcell(int x, int y) ;
virtual int nextcell(int x, int y, int &v) ;
virtual void endofpattern() ;
virtual void setIncrement(bigint inc) ;
virtual void setIncrement(int inc) { setIncrement(bigint(inc)) ; }
virtual void setGeneration(bigint gen) { generation = gen ; }
virtual const bigint &getPopulation() ;
virtual int isEmpty() ;
virtual int hyperCapable() { return 1 ; }
virtual void setMaxMemory(int m) ;
virtual int getMaxMemory() { return (int)(maxmem >> 20) ; }
virtual const char *setrule(const char *) ;
virtual const char *getrule() { return "" ; }
virtual void step() ;
virtual void* getcurrentstate() { return root ; }
virtual void setcurrentstate(void *n) ;
/*
* The contract of draw() is that it render every pixel in the
* viewport precisely once. This allows us to eliminate all
* flashing. Later we'll make this be damage-specific.
*/
virtual void draw(viewport &view, liferender &renderer) ;
virtual void fit(viewport &view, int force) ;
virtual void lowerRightPixel(bigint &x, bigint &y, int mag) ;
virtual void findedges(bigint *t, bigint *l, bigint *b, bigint *r) ;
virtual const char *readmacrocell(char *line) ;
virtual const char *writeNativeFormat(std::ostream &os, char *comments) ;
static void doInitializeAlgoInfo(staticAlgoInfo &) ;
private:
/*
* Some globals representing our universe. The root is the
* real root of the universe, and the depth is the depth of the
* tree where 2 means that root is a ghleaf, and 3 means that the
* children of root are leaves, and so on. The center of the
* root is always coordinate position (0,0), so at startup the
* x and y coordinates range from -4..3; in general,
* -(2**depth)..(2**depth)-1. The zeroghnodea is an
* array of canonical `empty-space' ghnodes at various depths.
* The ngens is an input parameter which is the second power of
* the number of generations to run.
*/
ghnode *root ;
int depth ;
ghnode **zeroghnodea ;
int nzeros ;
/*
* Finally, our gc routine. We keep a `stack' of all the `roots'
* we want to preserve. Nodes not reachable from here, we allow to
* be freed. Same with leaves.
*/
ghnode **stack ;
int stacksize ;
g_uintptr_t hashpop, hashlimit, hashprime ;
#ifndef PRIMEMOD
g_uintptr_t hashmask ;
#endif
static double maxloadfactor ;
ghnode **hashtab ;
int halvesdone ;
int gsp ;
g_uintptr_t alloced, maxmem ;
ghnode *freeghnodes ;
int okaytogc ;
g_uintptr_t totalthings ;
ghnode *ghnodeblocks ;
bigint population ;
bigint setincrement ;
bigint pow2step ; // greatest power of two in increment
int nonpow2 ; // increment / pow2step
int ngens ; // log2(pow2step)
int popValid, needPop, inGC ;
/*
* When rendering we store the relevant bits here rather than
* passing them deep into recursive subroutines.
*/
liferender *renderer ;
viewport *view ;
int uviewh, uvieww, viewh, vieww, mag, pmag ;
int llbits, llsize ;
char *llxb, *llyb ;
int hashed ;
int cacheinvalid ;
g_uintptr_t cellcounter ; // used when writing
g_uintptr_t writecells ; // how many to write
int gccount ; // how many gcs total this pattern
int gcstep ; // how many gcs this step
hperf running_hperf, step_hperf, inc_hperf ;
int softinterrupt ;
static char statusline[] ;
//
void resize() ;
ghnode *find_ghnode(ghnode *nw, ghnode *ne, ghnode *sw, ghnode *se) ;
#ifdef USEPREFETCH
ghnode *find_ghnode(ghsetup_t &su) ;
void setupprefetch(ghsetup_t &su, ghnode *nw, ghnode *ne, ghnode *sw, ghnode *se) ;
#endif
void unhash_ghnode(ghnode *n) ;
void unhash_ghnode2(ghnode *n) ;
void rehash_ghnode(ghnode *n) ;
ghleaf *find_ghleaf(state nw, state ne, state sw, state se) ;
ghnode *getres(ghnode *n, int depth) ;
ghnode *dorecurs(ghnode *n, ghnode *ne, ghnode *t, ghnode *e, int depth) ;
ghnode *dorecurs_half(ghnode *n, ghnode *ne, ghnode *t, ghnode *e, int depth) ;
ghleaf *dorecurs_ghleaf(ghleaf *n, ghleaf *ne, ghleaf *t, ghleaf *e) ;
ghnode *newghnode() ;
ghleaf *newghleaf() ;
ghnode *newclearedghnode() ;
ghleaf *newclearedghleaf() ;
void pushroot_1() ;
int ghnode_depth(ghnode *n) ;
ghnode *zeroghnode(int depth) ;
ghnode *pushroot(ghnode *n) ;
ghnode *gsetbit(ghnode *n, int x, int y, int newstate, int depth) ;
int getbit(ghnode *n, int x, int y, int depth) ;
int nextbit(ghnode *n, int x, int y, int depth, int &v) ;
ghnode *hashpattern(ghnode *root, int depth) ;
ghnode *popzeros(ghnode *n) ;
const bigint &calcpop(ghnode *root, int depth) ;
void aftercalcpop2(ghnode *root, int depth) ;
void afterwritemc(ghnode *root, int depth) ;
void calcPopulation() ;
ghnode *save(ghnode *n) ;
void pop(int n) ;
void clearstack() ;
void clearcache() ;
void gc_mark(ghnode *root, int invalidate) ;
void do_gc(int invalidate) ;
void clearcache(ghnode *n, int depth, int clearto) ;
void clearcache_p1(ghnode *n, int depth, int clearto) ;
void clearcache_p2(ghnode *n, int depth, int clearto) ;
void new_ngens(int newval) ;
int log2(unsigned int n) ;
ghnode *runpattern() ;
void renderbm(int x, int y) ;
void fill_ll(int d) ;
void drawghnode(ghnode *n, int llx, int lly, int depth, ghnode *z) ;
void ensure_hashed() ;
g_uintptr_t writecell(std::ostream &os, ghnode *root, int depth) ;
g_uintptr_t writecell_2p1(ghnode *root, int depth) ;
g_uintptr_t writecell_2p2(std::ostream &os, ghnode *root, int depth) ;
void drawpixel(int x, int y);
void draw4x4_1(state sw, state se, state nw, state ne, int llx, int lly) ;
void draw4x4_1(ghnode *n, ghnode *z, int llx, int lly) ;
// AKT: set all pixels to background color
void killpixels();
} ;
#endif
|
