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
|
/*** /
This file is part of Golly, a Game of Life Simulator.
Copyright (C) 2009 Andrew Trevorrow and Tomas Rokicki.
This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Web site: http://sourceforge.net/projects/golly
Authors: rokicki@gmail.com andrew@trevorrow.com
/ ***/
#ifndef GHASHBASE_H
#define GHASHBASE_H
#include "lifealgo.h"
#include "liferules.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 */
unsigned short 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)
/**
* 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 &getIncrement() { return increment ; }
virtual const bigint &getPopulation() ;
virtual const bigint &getGeneration() { return generation ; }
virtual int isEmpty() ;
virtual int hyperCapable() { return 1 ; }
virtual void setMaxMemory(int m) ;
virtual int getMaxMemory() { return maxmem >> 20 ; }
virtual const char *setrule(const char *) ;
virtual const char *getrule() { return "" ; }
virtual void step() ;
/*
* 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(FILE *f, 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 ;
ghnode **hashtab ;
int halvesdone ;
int gsp ;
g_uintptr_t alloced, maxmem ;
ghnode *freeghnodes ;
int okaytogc ;
g_uintptr_t totalthings ;
ghnode *ghnodeblocks ;
bigint generation ;
bigint population ;
bigint increment ;
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
static char statusline[] ;
//
void resize() ;
ghnode *find_ghnode(ghnode *nw, ghnode *ne, ghnode *sw, ghnode *se) ;
void unhash_ghnode(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 *setbit(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, int cleanbigints) ;
void calcPopulation(ghnode *root) ;
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 new_ngens(int newval) ;
int log2(unsigned int n) ;
ghnode *runpattern() ;
void clearrect(int x, int y, int w, int h) ;
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(FILE *f, ghnode *root, int depth) ;
g_uintptr_t writecell_2p1(ghnode *root, int depth) ;
g_uintptr_t writecell_2p2(FILE *f, 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
|
