1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 #include "ltlalgo.h"
5 #include "util.h"
6 #include <string.h> // for memset and memcpy
7
8 // -----------------------------------------------------------------------------
9
10 // A 256x256 pixmap is good for OpenGL and matches the size
11 // used in qlifedraw.cpp and hlifedraw.cpp.
12 // Note that logpmsize *must* be 8 in iOS 9.x to avoid drawing problems
13 // in my iPad (probably due to a bug in the OpenGL ES 2 driver).
14
15 const int logpmsize = 8; // 8=256x256
16 const int pmsize = (1<<logpmsize); // pixmap wd and ht, in pixels
17 const int bpp = 4; // bytes per pixel (RGBA)
18 const int rowoff = (pmsize*bpp); // row offset, in bytes
19 const int ibufsize = (pmsize*pmsize*bpp); // buffer size, in bytes
20 static unsigned char ipixbuf[ibufsize]; // shared buffer for pixels
21 static unsigned char *pixbuf = ipixbuf;
22
23 // RGBA view of pixbuf
24 static unsigned int *pixRGBAbuf = (unsigned int *)ipixbuf;
25
26 // arrays of RGB colors for each cell state (set by getcolors call)
27 static unsigned char* cellred;
28 static unsigned char* cellgreen;
29 static unsigned char* cellblue;
30
31 // alpha values for dead pixels and live pixels (also set by getcolors call)
32 static unsigned char deada;
33 static unsigned char livea;
34
35 static unsigned int cellRGBA[256]; // cell colors in RGBA format
36
37 // -----------------------------------------------------------------------------
38
39 // kill all cells in pixbuf
40
killpixels()41 static void killpixels()
42 {
43 // pmag is 1 so pixblit assumes pixbuf contains 4 bytes (RGBA) for each pixel
44 if (deada == 0) {
45 // dead cells are 100% transparent so we can use fast method
46 // (RGB values are irrelevant if alpha is 0)
47 memset(pixbuf, 0, sizeof(ipixbuf));
48 } else {
49 // use slower method
50 unsigned int deadRGBA = cellRGBA[0];
51 unsigned int *rgbabuf = pixRGBAbuf;
52
53 // fill the first row with the dead pixel state
54 for (int i = 0; i < pmsize; i++) {
55 *rgbabuf++ = deadRGBA;
56 }
57 // copy 1st row to remaining rows
58 for (int i = rowoff; i < ibufsize; i += rowoff) {
59 memcpy(&pixbuf[i], pixbuf, rowoff);
60 }
61 }
62 }
63
64 // -----------------------------------------------------------------------------
65
66 // this is the top-level drawing routine
67
draw(viewport & view,liferender & renderer)68 void ltlalgo::draw(viewport &view, liferender &renderer)
69 {
70 if (population == 0) return;
71
72 if (!renderer.justState()) {
73 // get cell colors and alpha values for dead and live pixels
74 renderer.getcolors(&cellred, &cellgreen, &cellblue, &deada, &livea);
75
76 // create RGBA view
77 unsigned char *rgbaptr = (unsigned char *)cellRGBA;
78
79 // create dead color
80 *rgbaptr++ = cellred[0];
81 *rgbaptr++ = cellgreen[0];
82 *rgbaptr++ = cellblue[0];
83 *rgbaptr++ = deada;
84
85 // create live colors
86 unsigned int livestates = NumCellStates() - 1;
87 for (unsigned int ui = 1; ui <= livestates; ui++) {
88 *rgbaptr++ = cellred[ui];
89 *rgbaptr++ = cellgreen[ui];
90 *rgbaptr++ = cellblue[ui];
91 *rgbaptr++ = livea;
92 }
93 }
94
95 int mag, pmag;
96 int vieww = view.getwidth();
97 int viewh = view.getheight();
98 if (view.getmag() > 0) {
99 pmag = 1 << view.getmag();
100 mag = 0;
101 } else {
102 pmag = 1;
103 mag = -view.getmag();
104 }
105
106 // get pixel position in view of grid's top left cell
107 pair<int,int> ltpxl = view.screenPosOf(gridleft, gridtop, this);
108
109 if (renderer.justState() || pmag > 1) {
110 if (unbounded) {
111 // simply display the entire grid -- ie. no need to use pixbuf
112 int x = ltpxl.first; // already multiplied by pmag
113 int y = ltpxl.second; // ditto
114 int wd = gwd * pmag;
115 int ht = ght * pmag;
116 if (renderer.justState())
117 renderer.stateblit(x, y, wd, ht, currgrid) ;
118 else
119 renderer.pixblit(x, y, wd, ht, currgrid, pmag);
120 } else {
121 // the universe is bounded so we need to include the outer border
122 bigint outerleft = gridleft;
123 bigint outertop = gridtop;
124 outerleft -= border;
125 outertop -= border;
126 ltpxl = view.screenPosOf(outerleft, outertop, this);
127 int x = ltpxl.first;
128 int y = ltpxl.second;
129 int wd = outerwd * pmag;
130 int ht = outerht * pmag;
131 if (renderer.justState())
132 renderer.stateblit(x, y, wd, ht, outergrid1) ;
133 else
134 renderer.pixblit(x, y, wd, ht, outergrid1, pmag);
135 }
136 } else {
137 // pmag is 1 so first fill pixbuf with dead cells
138 killpixels();
139 if (mag == 0) {
140 // divide grid into pmsize * pmsize blocks and draw them at scale 1:1
141 for (int row = 0; row < ght; row += pmsize) {
142 for (int col = 0; col < gwd; col += pmsize) {
143
144 // don't go beyond bottom/right edges of grid
145 int jmax = row + pmsize <= ght ? pmsize : pmsize - (row + pmsize - ght);
146 int imax = col + pmsize <= gwd ? pmsize : pmsize - (col + pmsize - gwd);
147
148 // check if this block is visible in view
149 int x = ltpxl.first + col;
150 int y = ltpxl.second + row;
151 if (x >= vieww || y >= viewh || x+imax <= 0 || y+jmax <= 0) {
152 // not visible
153 } else {
154 // get cell at top left corner of this block
155 unsigned char* cellptr = currgrid + row * outerwd + col;
156
157 // find live cells in this block and store their RGBA data in pixbuf
158 for (int j = 0; j < jmax; j++) {
159 unsigned char* p = cellptr;
160 int pixrow = j * pmsize;
161 for (int i = 0; i < imax; i++) {
162 if (*p > 0) pixRGBAbuf[pixrow + i] = cellRGBA[*p];
163 p++;
164 }
165 cellptr += outerwd;
166 }
167
168 // draw this block
169 renderer.pixblit(x, y, pmsize, pmsize, pixbuf, 1);
170 killpixels();
171 }
172 }
173 }
174 } else {
175 // mag > 0 (actually zoomed out);
176 // divide grid into pmsize*(2^mag) * pmsize*(2^mag) blocks, shrinking them down
177 // to pmsize * pmsize, and draw all non-zero cells using the state 1 color
178 unsigned int state1RGBA = cellRGBA[1];
179
180 // check if grid shrinks to 1 pixel
181 if ((gwd >> mag) == 0 && (ght >> mag) == 0) {
182 pixRGBAbuf[0] = state1RGBA; // there is at least 1 live cell in grid
183 int x = ltpxl.first;
184 int y = ltpxl.second;
185 renderer.pixblit(x, y, pmsize, pmsize, pixbuf, 1);
186 pixRGBAbuf[0] = cellRGBA[0];
187 return;
188 }
189
190 // above check should avoid overflow in blocksize calc, but play safe
191 if (mag > 20) mag = 20;
192 pmag = 1 << mag;
193 int blocksize = pmsize * pmag;
194 for (int row = 0; row < ght; row += blocksize) {
195 for (int col = 0; col < gwd; col += blocksize) {
196
197 // check if shrunken block is visible in view
198 int x = ltpxl.first + (col >> mag);
199 int y = ltpxl.second + (row >> mag);
200 if (x >= vieww || y >= viewh || x+pmsize <= 0 || y+pmsize <= 0) {
201 // not visible
202 } else {
203 // get cell at top left corner of this big block
204 unsigned char* cellptr = currgrid + row * outerwd + col;
205
206 // avoid going way beyond bottom/right edges of grid
207 int jmax = row + blocksize <= ght ? blocksize : blocksize - (row + blocksize - ght);
208 int imax = col + blocksize <= gwd ? blocksize : blocksize - (col + blocksize - gwd);
209
210 for (int j = 0; j < jmax; j += pmag) {
211 unsigned char* p = cellptr;
212 int sqtop = row + j;
213 for (int i = 0; i < imax; i += pmag) {
214
215 // shrink pmag*pmag cells in grid down to 1 pixel in pixbuf
216 int sqleft = col + i;
217 for (int r = 0; r < pmag; r++) {
218 if (sqtop + r < ght) {
219 unsigned char* topleft = p + r * outerwd;
220 for (int c = 0; c < pmag; c++) {
221 if (sqleft + c < gwd) {
222 unsigned char* q = topleft + c;
223 if (*q > 0) {
224 pixRGBAbuf[(j >> mag) * pmsize + (i >> mag)] = state1RGBA;
225 // no need to keep looking in this square
226 goto found1;
227 }
228 }
229 }
230 }
231 }
232 found1:
233 p += pmag;
234
235 }
236 cellptr += outerwd * pmag;
237 }
238
239 // draw the shrunken block
240 renderer.pixblit(x, y, pmsize, pmsize, pixbuf, 1);
241 killpixels();
242 }
243 }
244 }
245 }
246 }
247 }
248
249 // -----------------------------------------------------------------------------
250
findedges(bigint * ptop,bigint * pleft,bigint * pbottom,bigint * pright)251 void ltlalgo::findedges(bigint *ptop, bigint *pleft, bigint *pbottom, bigint *pright)
252 {
253 if (population == 0) {
254 // return impossible edges to indicate an empty pattern;
255 // not really a problem because caller should check first
256 *ptop = 1;
257 *pleft = 1;
258 *pbottom = 0;
259 *pright = 0;
260 return;
261 }
262
263 // the code in ltlalgo.cpp maintains a boundary of live cells in
264 // minx,miny,maxx,maxy but it might not be the minimal boundary
265 // (eg. if user deleted some live cells)
266
267 // find the top edge (miny)
268 for (int row = miny; row <= maxy; row++) {
269 unsigned char* cellptr = currgrid + row * outerwd + minx;
270 for (int col = minx; col <= maxx; col++) {
271 if (*cellptr > 0) {
272 miny = row;
273 goto found_top;
274 }
275 cellptr++;
276 }
277 }
278 // should never get here if population > 0
279 lifefatal("Bug detected in ltlalgo::findedges!");
280
281 found_top:
282
283 // find the bottom edge (maxy)
284 for (int row = maxy; row >= miny; row--) {
285 unsigned char* cellptr = currgrid + row * outerwd + minx;
286 for (int col = minx; col <= maxx; col++) {
287 if (*cellptr > 0) {
288 maxy = row;
289 goto found_bottom;
290 }
291 cellptr++;
292 }
293 }
294
295 found_bottom:
296
297 // find the left edge (minx)
298 for (int col = minx; col <= maxx; col++) {
299 unsigned char* cellptr = currgrid + miny * outerwd + col;
300 for (int row = miny; row <= maxy; row++) {
301 if (*cellptr > 0) {
302 minx = col;
303 goto found_left;
304 }
305 cellptr += outerwd;
306 }
307 }
308
309 found_left:
310
311 // find the right edge (maxx)
312 for (int col = maxx; col >= minx; col--) {
313 unsigned char* cellptr = currgrid + miny * outerwd + col;
314 for (int row = miny; row <= maxy; row++) {
315 if (*cellptr > 0) {
316 maxx = col;
317 goto found_right;
318 }
319 cellptr += outerwd;
320 }
321 }
322
323 found_right:
324
325 // set pattern edges (in cell coordinates)
326 *ptop = int(miny + gtop);
327 *pleft = int(minx + gleft);
328 *pbottom = int(maxy + gtop);
329 *pright = int(maxx + gleft);
330 }
331
332 // -----------------------------------------------------------------------------
333
fit(viewport & view,int force)334 void ltlalgo::fit(viewport &view, int force)
335 {
336 if (population == 0) {
337 view.center();
338 view.setmag(MAX_MAG);
339 return;
340 }
341
342 bigint top, left, bottom, right;
343 findedges(&top, &left, &bottom, &right);
344
345 if (!force) {
346 // if all four of the above dimensions are in the viewport, don't change
347 if (view.contains(left, top) && view.contains(right, bottom))
348 return;
349 }
350
351 bigint midx = right;
352 midx -= left;
353 midx += bigint::one;
354 midx.div2();
355 midx += left;
356
357 bigint midy = bottom;
358 midy -= top;
359 midy += bigint::one;
360 midy.div2();
361 midy += top;
362
363 int mag = MAX_MAG;
364 for (;;) {
365 view.setpositionmag(midx, midy, mag);
366 if (view.contains(left, top) && view.contains(right, bottom))
367 break;
368 mag--;
369 }
370 }
371
372 // -----------------------------------------------------------------------------
373
lowerRightPixel(bigint & x,bigint & y,int mag)374 void ltlalgo::lowerRightPixel(bigint &x, bigint &y, int mag)
375 {
376 if (mag >= 0) return;
377 x >>= -mag;
378 x <<= -mag;
379 y -= 1;
380 y >>= -mag;
381 y <<= -mag;
382 y += 1;
383 }
384