root/trunk/qd/test19.d

Revision 778, 17.4 kB (checked in by FeepingCreature, 4 years ago)

Small fixes

Line 
1 module test19;
2
3 import qd;
4
5 import tools.base, tools.functional, tools.log, tools.time, tools.compat;
6
7 alias tools.base.max max;
8 alias tools.base.min min;
9
10 alias ubyte Cell;
11
12 int scale = 1;
13
14 struct rect {
15   int x, y, w, h;
16   bool overlaps(rect other) {
17     if (x > other.x + other.w) return false; // right of it
18     if (x+w < other.x) return false; // left of it
19     if (y > other.y + other.h) return false; // bottom of it
20     if (y+h < other.y) return false; // top of it
21     return true; // otherwise overlap
22   }
23 }
24
25 struct subtree {
26     /**
27        x 0 1
28        y ___
29        0|0 2
30        1|1 3
31     **/
32   static assert(Cell.sizeof < (subtree*).sizeof);
33   union {
34     Repeat!(subtree*, 4) subtrees;           Repeat!(Cell, 4) values;
35     subtree*[2][2] subtrees_xy;              Cell[2][2] values_xy;
36     struct { subtree* tl, bl, tr, br; }      struct { Cell c_tl, c_bl, c_tr, c_br; }
37   }
38   bool bottom() { return !br; }
39   int level() {
40     if (bottom) return 0;
41     else return 1 + tl.level;
42   }
43   bool isNull() {
44     if (bottom) {
45       return !c_tl && !c_bl && !c_tr && !c_br;
46     } else {
47       if (!tl.isNull) return false;
48       // logln("Start");
49       foreach (i, tree; subtrees) {
50         // logln("Loop ", i, " @", this, ", child: ", tree);
51         // if (!i) continue; BREAKS LDC
52         if (i) {
53           // if (tree is tl) continue; BREAKS SEE ABOVE // null
54           if (!(tree is tl)) {
55             if (!tree.isNull) return false;
56             // we found a duplicate null. adapt.
57             subtrees[i] = tl;
58           }
59         }
60       }
61       return true;
62     }
63   }
64   int descend(int xbase, int ybase, int delegate(int x, int y, ref Cell v) dg) {
65     if (bottom) {
66       foreach (x; Tuple!(0, 1))
67         foreach (y; Tuple!(0, 1))
68           if (auto res = dg(xbase + x, ybase + y, values_xy[x][y]))
69             return res;
70     } else {
71       foreach (x; Tuple!(0, 1))
72         foreach (y; Tuple!(0, 1))
73           if (auto res = subtrees_xy[x][y].descend(xbase + (size / 2) * x, ybase + (size / 2) * y, dg))
74             return res;
75     }
76     return 0;
77   }
78   int opApply(int delegate(ref int x, ref int y, ref Cell v) dg) {
79     return descend(0, 0, (int x, int y, ref Cell v) { return dg(x, y, v); });
80   }
81   void render() {
82     int a, b, c, d;
83     foreach (x, y, cell; *this) {
84       auto xp = x * scale, yp = y * scale;
85       if (xp !< screen.w || yp !< screen.h) continue;
86       rgb color;
87       switch (cell) {
88         case 0: color = Black; a ++; break;
89         case 1: color = Yellow; b ++; break;
90         case 2: color = Blue ~ White; c ++; break;
91         case 3: color = Red; d ++; break;
92       }
93       for (int i = 0; i < scale; ++i)
94         for (int j = 0; j < scale; ++j)
95           pset(xp+i, yp+j, color);
96     }
97   }
98   void renderAt(int x, int y, int w, int h, void delegate(int, int, Cell) dg, int my_x = 0, int my_y = 0) {
99     if (bottom) {
100       dg(my_x, my_y, c_tl);
101       dg(my_x+1, my_y, c_tr);
102       dg(my_x, my_y+1, c_bl);
103       dg(my_x+1, my_y+1, c_br);
104     } else {
105       auto s = size();
106       auto my_xr = my_x + s, my_yr = my_y + s;
107       auto my_xhalf = my_x + s / 2, my_yhalf = my_y + s / 2;
108       auto scr = rect(x, y, w, h);
109       if (scr.overlaps(rect(my_x, my_y, s/2, s/2))) tl.renderAt(x, y, w, h, dg, my_x, my_y);
110       if (scr.overlaps(rect(my_x, my_yhalf, s/2, s/2))) bl.renderAt(x, y, w, h, dg, my_x, my_yhalf);
111       if (scr.overlaps(rect(my_xhalf, my_y, s/2, s/2))) tr.renderAt(x, y, w, h, dg, my_xhalf, my_y);
112       if (scr.overlaps(rect(my_xhalf, my_yhalf, s/2, s/2))) br.renderAt(x, y, w, h, dg, my_xhalf, my_yhalf);
113     }
114   }
115   ulong size() { return 2UL << level; }
116 }
117
118 void delegate()[] cleans;
119
120 class MyDict(K, V) {
121   const K EmptyKey = K.init;
122   bool emptySet;
123   Entry empty;
124   struct Entry {
125     K key;
126     V value;
127   }
128   static uint hash(K key) {
129     static if (K.sizeof == 4)
130       return *(cast(uint*) &key);
131     else {
132       return typeid(K).getHash(&key);
133     }
134   }
135   this(int i) { setSizePower2(i); cleans ~= &clean; }
136   Entry[4][] list;
137   uint mask;
138  
139   void clean() {
140     emptySet = false;
141     foreach (ref entry; list) {
142       entry[] = Init!(Entry[8]);
143     }
144   }
145   void setSizePower2(int p2) {
146     if (p2 >= 2) p2 -= 2;
147     list.length = 1 << p2;
148     mask = list.length - 1;
149   }
150  
151   Entry* findPos(K key, ref bool found) {
152     if (empty.key == key) { scope(success) emptySet = true; found = emptySet; return &empty; }
153     auto h = hash(key);
154     auto le = &(list[h&mask]);
155     foreach (k, ref entry; *le) {
156       if (entry.key == key) {
157         found = true;
158         if (k) {
159           swap(entry, (*le)[k-1]);
160           return &((*le)[k-1]);
161         } else return &entry;
162       } else if (entry.key == EmptyKey) {
163         found = false;
164         return &entry;
165       }
166     }
167     found = false;
168     return &((*le)[$-1]);
169   }
170   int size() { return list.length; }
171 }
172
173 final class MemoCache(K, V) {
174   MyDict!(K, V) backend;
175   this() { New(backend, 20); }
176   size_t length() { return backend.size; }
177   V get(string FN)(K k) {
178     bool found = void;
179     auto pos = backend.findPos(k, found);
180     if (found) {
181       return pos.value;
182     }
183     auto v = mixin(FN);
184     pos.key = k; pos.value = v;
185     return v;
186   }
187 }
188 }
189
190 int Size(int d) {
191   switch (d) {
192     case 0, 1: return 22;
193     case 2, 3, 4, 5, 6: return 20;
194     case 7: return 16;
195     default: return 12;
196   }
197 }
198
199 final class MemoCacheDepthBased(K, V, alias D) {
200   alias MyDict!(K, V) Dict;
201   Dict[] backend;
202   size_t length() { return 0; }
203   V get(string FN)(K k) {
204     auto d = D(k);
205     while (d !< backend.length) { backend ~= new Dict(Size(backend.length)); }
206    
207     bool found = void;
208     auto entry = backend[d].findPos(k, found);
209     if (found) {
210       return entry.value;
211     }
212     auto v = mixin(FN);
213     entry.key = k;
214     entry.value = v;
215     return v;
216   }
217 }
218
219 template hasDepth(T) {
220   const hasDepth = is(typeof(Init!(T).level())) || is(typeof(Init!(T)._0.level()));
221 }
222
223 int getDepth(T)(T t) {
224   static if (is(typeof(!t))) if (!t) return 0; // failure in progress; returned value doesn't really matter
225   static if (is(typeof(!t._0))) if (!t._0) return 0; // failure in progress; returned value doesn't really matter
226  
227   static if (is(typeof(t.level()))) return t.level(); else
228   static if (is(typeof(t._0.level()))) return t._0.level(); else
229   static assert(false, "Whuh? "~T.stringof);
230 }
231
232 template Memoize(string FN, string NEWNAME, string SALT = "") {
233   const string Memoize = ctReplace(`
234     alias Ret!(typeof(&FN)) IDENT_R;
235     alias Params!(typeof(&FN)) IDENT_P;
236     static if (hasDepth!(Stuple!(IDENT_P)))
237       MemoCacheDepthBased!(Stuple!(IDENT_P), IDENT_R, getDepth!(Stuple!(IDENT_P))) IDENT_cache;
238     else
239       MemoCache!(Stuple!(IDENT_P), IDENT_R) IDENT_cache;
240     static this() { New(IDENT_cache); logln("STATIC CONSTRUCTOR: built IDENT_cache"); }
241     IDENT_R NEWNAME(IDENT_P p) { return IDENT_cache.get!("FN"~"(k.tupleof)")(stuple(p)); }
242     `, `NEWNAME`, NEWNAME, `IDENT`, NEWNAME~SALT, `FN`, FN
243   );
244 }
245
246 class CheapHeap {
247   void[] mem;
248   int freeptr;
249   this(int size) { mem = cmalloc(size)[0 .. size]; }
250   ~this() { cfree(mem.ptr); }
251   int size() { return mem.length; }
252   int free() { return mem.length - freeptr; }
253   int used() { return freeptr; }
254   float load() { return used * 1f / size; }
255   void* malloc(int i) {
256     if (freeptr + i < size) {
257       auto res = &mem[freeptr];
258       freeptr += i;
259       return res;
260     } else {
261       return null;
262     }
263   }
264   T* alloc(T)() {
265     return cast(T*) malloc(T.sizeof);
266   }
267 }
268
269 CheapHeap chirp;
270 static this() { New(chirp, 64*1024*1024); }
271
272 subtree* _getSubtree1(Repeat!(subtree*, 4) trees) {
273   foreach (tree; trees) if (!tree) return null;
274   debug foreach (value; Tuple!(0, 1, 2)) {
275     assert(trees[value].level == trees[value+1].level, Format(
276       "Cannot build subtree from trees with different levels: ",
277       [trees[0].level, trees[1].level, trees[2].level, trees[3].level]
278     ));
279   }
280   auto res = chirp.alloc!(subtree);
281   if (!res) return null;
282   foreach (id, value; trees) res.subtrees[id] = value;
283   return res;
284 }
285
286 subtree* _getSubtree2(Repeat!(Cell, 4) values) {
287   auto res = chirp.alloc!(subtree);
288   if (!res) return null;
289   foreach (id, value; values) res.values[id] = value;
290   return res;
291 }
292
293 mixin(Memoize!("_getSubtree1", "getSubtree", "1") ~ Memoize!("_getSubtree2", "getSubtree", "2"));
294
295 subtree* _getNulltree(ulong level) {
296   if (!level) {
297     return chirp.alloc!(subtree);
298   }
299   auto below = getNulltree(level-1);
300   return getSubtree(below, below, below, below);
301 }
302
303 mixin(Memoize!("_getNulltree", "getNulltree"));
304
305 subtree* grow(subtree* center) {
306   if (!center) return null;
307   /**
308     0 0 | 0 0
309     0 tl|tr 0    0 2
310     - - + - -    1 3
311     0 bl|br 0
312     0 0 | 0 0
313   **/
314   const string RET = "return getSubtree(
315     getSubtree(·, ·, ·, %tl),
316     getSubtree(·, ·, %bl, ·),
317     getSubtree(·, %tr, ·, ·),
318     getSubtree(%br, ·, ·, ·)
319   );";
320   if (center.bottom) { mixin(ctReplace(RET, "·", "0", "%", "center.c_")); }
321   else {
322     auto zero = getNulltree(center.level - 1);
323     mixin(ctReplace(RET, "·", "zero", "%", "center."));
324   }
325 }
326
327 subtree* buildSubtree(int width, int height, Cell delegate(int, int) dg) {
328   auto size = cast(int) (tools.compat.log(max(width, height)) / tools.compat.log(2) + 1);
329   subtree* build_descend(int x, int y, int level) {
330     if (x > width || y > height) return getNulltree(level);
331     if (!level) {
332       return getSubtree(dg(x, y), dg(x, y+1), dg(x+1, y), dg(x+1, y+1));
333     }
334     auto offs = 1 << level;
335     return getSubtree(
336       build_descend(x, y, level - 1), build_descend(x, y + offs, level - 1),
337       build_descend(x + offs, y, level - 1), build_descend(x + offs, y + offs, level - 1)
338     );
339   }
340   return build_descend(0, 0, size);
341 }
342
343 Cell calc(Repeat!(Cell, 9) field) {
344   switch (field[4]) {
345     case 0: return 0;
346     case 2: return 3;
347     case 3: return 1;
348     case 1:
349       ubyte heads;
350       foreach (id, value; field)
351         if (id != 4 && value == 2) ++heads;
352       if (heads == 1 /or/ 2) return 2;
353       return 1;
354   }
355 }
356
357 import tools.threadpool, tools.page_queue;
358 Threadpool tp;
359
360 // grows input if needed to make sure its periphery is null
361 subtree* force_shrink(subtree* input) {
362   if (!input) return null;
363   assert(!input.bottom, "Cannot shrink bottom");
364   if (input.tl.bottom) {
365     return getSubtree(input.tl.c_br, input.bl.c_tr, input.tr.c_bl, input.br.c_tl);
366   } else {
367     return getSubtree(input.tl.br, input.bl.tr, input.tr.bl, input.br.tl);
368   }
369 }
370
371 // returns a subtree one level below the parameter, centered on the parameter
372 subtree* _step(subtree* node, int depth) {
373   if (!node) return null;
374   assert(node.level, "Cannot step LV0 node");
375   if (node.level == 1) {
376     assert(!depth);
377     /**
378       00 02      20 22   00 02     08 10
379       01  +--  --+  23   01  +-- --+  11
380           |03  21|           |03 09|
381
382           |12  30|           |06 12|
383       10  +--  --+  32   04  +-- --+  14
384       11 13      31 33   05 07     13 15
385     **/
386     alias Tuple!(
387        0,  2,  8,  1,  3,  9,  4,  6, 12,
388        1,  3,  9,  4,  6, 12,  5,  7, 13,
389        2,  8, 10,  3,  9, 11,  6, 12, 14,
390        3,  9, 11,  6, 12, 14,  7, 13, 15
391     ) indices;
392     Repeat!(Cell, 36) values;
393     foreach (id, value; indices)
394       values[id] = node.subtrees[value/4].values[value%4];
395     return getSubtree(
396       calc(values[ 0 ..  9]), calc(values[ 9 .. 18]),
397       calc(values[18 .. 27]), calc(values[27 .. 36])
398     );
399   }
400   with (*node) {
401     /**
402       0 1 2
403       3 4 5
404       6 7 8
405     **/
406     Repeat!(subtree*, 9) nines;
407     auto next = depth; if (next) next--;
408    
409     nines[0] = step(tl, next); nines[1] = step(getSubtree(tl.tr, tl.br, tr.tl, tr.bl), next); nines[2] = step(tr, next);
410     nines[3] = step(getSubtree(tl.bl, bl.tl, tl.br, bl.tr), next); // left
411     nines[4] = step(getSubtree(tl.br, bl.tr, tr.bl, br.tl), next); // center
412     nines[5] = step(getSubtree(tr.bl, br.tl, tr.br, br.tr), next); // right
413     nines[6] = step(bl, next); nines[7] = step(getSubtree(bl.tr, bl.br, br.tl, br.bl), next); nines[8] = step(br, next);
414     foreach (nine; nines) if (!nine) return null;
415     // now split into fours to calculate the inner quad
416     alias Tuple!(
417       0, 3, 1, 4, // first square
418       3, 6, 4, 7, // second square
419       1, 4, 2, 5, // etc
420       4, 7, 5, 8
421     ) indices;
422     Repeat!(subtree*, 16) values;
423     foreach (id, value; indices) values[id] = nines[value];
424     if (depth)
425       return getSubtree(
426         step(getSubtree(values[ 0 ..  4]), next), step(getSubtree(values[ 4 ..  8]), next),
427         step(getSubtree(values[ 8 .. 12]), next), step(getSubtree(values[12 .. 16]), next)
428       );
429     else
430       return getSubtree(
431         force_shrink(getSubtree(values[ 0 ..  4])), force_shrink(getSubtree(values[ 4 ..  8])),
432         force_shrink(getSubtree(values[ 8 .. 12])), force_shrink(getSubtree(values[12 .. 16]))
433       );
434   }
435 }
436
437 mixin(Memoize!("_step", "step"));
438
439 // grows input if needed to make sure its periphery is null
440 subtree* grow_if_needed(subtree* input) {
441   if (!input) return null;
442   if (input.bottom) return grow(input);
443   /**
444      0  2  8 10
445      1  3  9 11
446      4  6 12 14
447      5  7 13 15
448   **/
449   alias Tuple!(0, 2, 8, 10, 1, 11, 4, 14, 5, 7, 13, 15) border;
450   if (input.tl.bottom) {
451     foreach (v; border) if (input.subtrees[v/4].values[v%4]) return grow(input);
452   } else {
453     foreach (v; border) if (!input.subtrees[v/4].subtrees[v%4].isNull()) return grow(input);
454   }
455   return input;
456 }
457
458 subtree* rebuild(subtree* st) {
459   if (!st) throw new Exception("Bad. ");
460   if (st.bottom) return getSubtree(st.values);
461   else return getSubtree(
462     rebuild(st.subtrees[0]), rebuild(st.subtrees[1]),
463     rebuild(st.subtrees[2]), rebuild(st.subtrees[3])
464   );
465 }
466
467 Lock DeletionLock;
468 static this() { New(DeletionLock); }
469
470 void wipe(ref subtree* root) {
471   logln("Wiping caches");
472   foreach (dg; cleans) dg();
473   auto backup = chirp; chirp = new CheapHeap(chirp.size);
474   logln("Rebuild tree");
475   root = rebuild(root);
476   if (!root) {
477     logln("Couldn't fit main tree into new heap. Cannot continue. ");
478     exit(1);
479   }
480   logln("Load post-rebuild: ", chirp.load);
481   DeletionLock.Synchronized = delete backup;
482 }
483
484 subtree* iterate(subtree* input, ref subtree* forble, int steps) {
485   while (steps) {
486     auto grown = grow_if_needed(input);
487     // yes this circuitous back and forth is indeed, _necessary_.
488     if (!grown) { forble = input; wipe(forble); input = forble; continue; }
489     auto l = grown.level;
490     // find closest power of two
491     int i = 1, k = 0;
492     while (i <= steps) { if (k == l) break; i *= 2; k ++; }
493     i /= 2; k --;
494     auto stepped = step(grown, k);
495     if (!stepped) { forble = input; wipe(forble); input = forble; continue; }
496     input = stepped;
497     steps -= i;
498   }
499   return input;
500 }
501
502 bool isDigit(char c) { return c >= '0' && c <= '9'; }
503
504 extern(C) void exit(int);
505
506 import tools.rd;
507 void main(string[] args) {
508   scope(failure) exit(0);
509   auto exec = args[0]; args = args[1 .. $];
510   tp = new Threadpool(3);
511   string filename = "primes.wi";
512   if (args.length) filename = args[0];
513   if (args.length > 1) scale = args[1].atoi();
514   auto wf = (cast(string) tools.compat.read(filename)).split("\n")[1 .. $];
515   int maxlen;
516   foreach (line; wf) if (line.length > maxlen) maxlen = line.length;
517   auto temp = new ubyte[maxlen];
518   ubyte[] array;
519   foreach (i, line; wf) {
520     foreach (k, ch; line) {
521       switch (ch) {
522         case ' ': temp[k] = 0; break;
523         case '#': temp[k] = 1; break;
524         case '@': temp[k] = 2; break;
525         case '~': temp[k] = 3; break;
526       }
527     }
528     foreach (ref value; temp[line.length .. $]) value = 0;
529     array ~= temp;
530   }
531   auto test = buildSubtree(maxlen, wf.length, (int x, int y) { if (y>=wf.length || x >= maxlen) return cast(ubyte) 0; return array[y * maxlen + x]; });
532   // screen(maxlen * scale, wf.length * scale);
533   screen(640, 480);
534   ulong gen, last; auto start = sec(), last_sec = sec();
535   int stepsize = 256;
536   tp.addTask({
537     int sz;
538     while (true) {
539       volatile sz = stepsize;
540       test = iterate(test, test, sz);
541       gen += sz;
542     }
543   });
544   int xoffs, yoffs, factor = 1;
545   while (true) {
546     if (key.pressed('+') || key.pressed(93)) { stepsize *= 2; logln("Stepsize now ", stepsize); }
547     if (key.pressed('-') || key.pressed(47)) { if (stepsize > 1) stepsize /= 2; logln("Stepsize now ", stepsize); }
548     auto xstep = screen.w * factor / 4, ystep = screen.h * factor / 4;
549     if (key.pressed(276)) xoffs -= xstep;
550     if (key.pressed(275)) xoffs += xstep;
551     if (key.pressed(273)) yoffs -= ystep;
552     if (key.pressed(274)) yoffs += ystep;
553     if (key.pressed('y')) { factor *= 2; logln("Factor -> ", factor); }
554     if (key.pressed('x')) { if (factor > 1) factor /= 2; logln("Factor -> ", factor); }
555     scope(failure) logln("Render failure");
556     auto diff = gen - last;
557     if (diff > 0) {
558       last = gen;
559       auto s = sec(), sec_diff = s - last_sec;
560       last_sec = s;
561       logln(s - start, "s: generation ", gen, "; ", diff / sec_diff, " gen/s; ", gen / (s - start), " total gen/s");
562       logln("subtree1 [", getSubtree1_cache.length, "] subtree2 [", getSubtree2_cache.length, "] getNulltree [",
563         getNulltree_cache.length, "] step [", step_cache.length, "]");
564     }
565     // logln("Render ", screen.w * factor, "x", screen.h * factor, " at ", xoffs, ", ", yoffs);
566     cls;
567     DeletionLock.Synchronized = test.renderAt(xoffs, yoffs, screen.w * factor, screen.h * factor, (int x, int y, Cell cell) {
568       rgb color;
569       switch (cell) {
570         case 0: color = Black; break;
571         case 1: color = Yellow; break;
572         case 2: color = Blue ~ White; break;
573         case 3: color = Red; break;
574       }
575       if (factor == 1) pset(x-xoffs, y-yoffs, color);
576       else pset((x-xoffs) / factor, (y-yoffs) / factor, color);
577     });
578     flip; events;
579     // test.render; flip; events;
580   }
581 }
Note: See TracBrowser for help on using the browser.