2636375edf4bcab802c8ecafebdf9399884febfe
[xscreensaver] / hacks / munch.c
1 /* Munching Squares and Mismunch
2  *
3  * Portions copyright 1992-2008 Jamie Zawinski <jwz@jwz.org>
4  *
5  *   Permission to use, copy, modify, distribute, and sell this
6  *   software and its documentation for any purpose is hereby
7  *   granted without fee, provided that the above copyright notice
8  *   appear in all copies and that both that copyright notice and
9  *   this permission notice appear in supporting documentation.  No
10  *   representations are made about the suitability of this software
11  *   for any purpose.  It is provided "as is" without express or
12  *   implied warranty.
13  *
14  * Portions Copyright 1997, Tim Showalter
15  *
16  *   Permission is granted to copy, modify, and use this as long
17  *   as this notice remains intact.  No warranties are expressed or
18  *   implied.  CMU Sucks.
19  * 
20  * Portions Copyright 2004 Steven Hazel <sah@thalassocracy.org>
21  *
22  *   (The "mismunch" part).
23  * 
24  * "munch.c" and "mismunch.c" merged by jwz, 29-Aug-2008.
25  *
26  *
27  *
28  ***********************************************************************
29  *
30  * HAKMEM
31  *
32  * MIT AI Memo 239, Feb. 29, 1972.
33  * Beeler, M., Gosper, R.W., and Schroeppel, R.
34  *
35  * http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item146
36  *
37  ***********************************************************************
38  *
39  * ITEM 146: MUNCHING SQUARES
40  *
41  *     Another simple display program. It is thought that this was
42  *     discovered by Jackson Wright on the RLE PDP-1 circa 1962.
43  *
44  *          DATAI 2
45  *          ADDB 1,2
46  *          ROTC 2,-22
47  *          XOR 1,2
48  *          JRST .-4
49  *
50  *     2=X, 3=Y. Try things like 1001002 in data switches. This also
51  *     does * interesting things with operations other than XOR, and
52  *     rotations * other than -22. (Try IOR; AND; TSC; FADR; FDV(!);
53  *     ROT * -14, -9, -20, * ...)
54  *
55  * ITEM 147 (Schroeppel):
56  *
57  *     Munching squares is just views of the graph Y = X XOR T for
58  *     consecutive values of T = time.
59  *
60  * ITEM 147 (Cohen, Beeler):
61  *
62  *     A modification to munching squares which reveals them in frozen
63  *     states through opening and closing curtains: insert FADR 2,1
64  *     before the XOR. Try data switches =
65  *
66  *          4000,,4         1000,,2002      2000,,4        0,,1002
67  *
68  *     (Notation: <left half>,,<right half>)
69  *     Also try the FADR after the XOR, switches = 1001,,1.
70  *
71  ***********************************************************************
72  */
73
74 #include <math.h>
75 #include "screenhack.h"
76
77 typedef struct _muncher {
78   int mismunch;
79   int width;
80   int atX, atY;
81   int kX, kT, kY;
82   int grav;
83   XColor fgc;
84   int yshadow, xshadow;
85   int x, y, t;
86   int doom;
87   int done;
88 } muncher;
89
90
91 struct state {
92   Display *dpy;
93   Window window;
94
95   GC gc;
96   int delay, simul, clear, xor;
97   int logminwidth, logmaxwidth;
98   int restart, window_width, window_height;
99
100   int draw_n;  /* number of squares before we have to clear */
101   int draw_i;
102   int mismunch;
103
104   muncher **munchers;
105 };
106
107
108 /*
109  * dumb way to get # of digits in number.  Probably faster than actually
110  * doing a log and a division, maybe.
111  */
112 static int dumb_log_2(int k) 
113 {
114   int r = -1;
115   while (k > 0) {
116     k >>= 1; r++;
117   }
118   return r;
119 }
120
121
122 static void calc_logwidths (struct state *st) 
123 {
124   /* Choose a range of square sizes based on the window size.  We want
125      a power of 2 for the square width or the munch doesn't fill up.
126      Also, if a square doesn't fit inside an area 20% smaller than the
127      window, it's too big.  Mismunched squares that big make things
128      look too noisy. */
129
130   if (st->window_height < st->window_width) {
131     st->logmaxwidth = (int)dumb_log_2(st->window_height * 0.8);
132   } else {
133     st->logmaxwidth = (int)dumb_log_2(st->window_width * 0.8);
134   }
135
136   if (st->logmaxwidth < 2) {
137     st->logmaxwidth = 2;
138   }
139
140   /* we always want three sizes of squares */
141   st->logminwidth = st->logmaxwidth - 2;
142
143   if (st->logminwidth < 2) {
144     st->logminwidth = 2;
145   }
146 }
147
148
149
150 static muncher *make_muncher (struct state *st) 
151 {
152   int logwidth;
153   XWindowAttributes xgwa;
154   muncher *m = (muncher *) malloc(sizeof(muncher));
155
156   XGetWindowAttributes(st->dpy, st->window, &xgwa);
157
158   m->mismunch = st->mismunch;
159
160   /* choose size -- power of two */
161   logwidth = (st->logminwidth +
162               (random() % (1 + st->logmaxwidth - st->logminwidth)));
163
164   m->width = 1 << logwidth;
165
166   /* draw at this location */
167   m->atX = (random() % (xgwa.width <= m->width ? 1
168                         : xgwa.width - m->width));
169   m->atY = (random() % (xgwa.height <= m->width ? 1
170                         : xgwa.width - m->width));
171
172   /* wrap-around by these values; no need to % as we end up doing that
173      later anyway */
174   m->kX = ((random() % 2)
175            ? (random() % m->width) : 0);
176   m->kT = ((random() % 2)
177            ? (random() % m->width) : 0);
178   m->kY = ((random() % 2)
179            ? (random() % m->width) : 0);
180
181   /* set the gravity of the munch, or rather, which direction we draw
182      stuff in. */
183   m->grav = random() % 2;
184
185   /* I like this color scheme better than random colors. */
186   switch (random() % 4) {
187     case 0:
188       m->fgc.red = random() % 65536;
189       m->fgc.blue = random() % 32768;
190       m->fgc.green = random() % 16384;
191       break;
192
193     case 1:
194       m->fgc.red = 0;
195       m->fgc.blue = random() % 65536;
196       m->fgc.green = random() % 16384;
197       break;
198
199     case 2:
200       m->fgc.red = random() % 8192;
201       m->fgc.blue = random() % 8192;
202       m->fgc.green = random() % 49152;
203       break;
204
205     case 3:
206       m->fgc.red = random() % 65536;
207       m->fgc.green = m->fgc.red;
208       m->fgc.blue = m->fgc.red;
209       break;
210   }
211
212   /* Sometimes draw a mostly-overlapping copy of the square.  This
213      generates all kinds of neat blocky graphics when drawing in xor
214      mode. */
215   if (!m->mismunch || (random() % 4)) {
216     m->xshadow = 0;
217     m->yshadow = 0;
218   } else {
219     m->xshadow = (random() % (m->width/3)) - (m->width/6);
220     m->yshadow = (random() % (m->width/3)) - (m->width/6);
221   }
222
223   /* Start with a random y value -- this sort of controls the type of
224      deformities seen in the squares. */
225   m->y = random() % 256;
226
227   m->t = 0;
228
229   /*
230     Doom each square to be aborted at some random point.
231     (When doom == (width - 1), the entire square will be drawn.)
232   */
233   m->doom = (m->mismunch ? (random() % m->width) : (m->width - 1));
234   m->done = 0;
235
236   return m;
237 }
238
239
240 static void munch (struct state *st, muncher *m) 
241 {
242   int drawX, drawY;
243   XWindowAttributes xgwa;
244
245   if (m->done) {
246     return;
247   }
248
249   XGetWindowAttributes(st->dpy, st->window, &xgwa);
250
251   if (!mono_p) {
252     /* XXX there are probably bugs with this. */
253     if (XAllocColor(st->dpy, xgwa.colormap, &m->fgc)) {
254       XSetForeground(st->dpy, st->gc, m->fgc.pixel);
255     }
256   }
257
258   /* Finally draw this pass of the munching error. */
259
260   for(m->x = 0; m->x < m->width; m->x++) {
261     /* figure out the next point */
262
263     /*
264       The ordinary Munching Squares calculation is:
265       m->y = ((m->x ^ ((m->t + m->kT) % m->width)) + m->kY) % m->width;
266
267       We create some feedback by plugging in y in place of x, and
268       make a couple of values negative so that some parts of some
269       squares get drawn in the wrong place.
270     */
271     if (m->mismunch)
272       m->y = ((-m->y ^ ((-m->t + m->kT) % m->width)) + m->kY) % m->width;
273     else
274       m->y = ((m->x ^ ((m->t + m->kT) % m->width)) + m->kY) % m->width;
275
276     drawX = ((m->x + m->kX) % m->width) + m->atX;
277     drawY = (m->grav ? m->y + m->atY : m->atY + m->width - 1 - m->y);
278
279     XDrawPoint(st->dpy, st->window, st->gc, drawX, drawY);
280     if ((m->xshadow != 0) || (m->yshadow != 0)) {
281       /* draw the corresponding shadow point */
282       XDrawPoint(st->dpy, st->window, st->gc, drawX + m->xshadow, drawY + m->yshadow);
283     }
284     /* XXX may want to change this to XDrawPoints,
285        but it's fast enough without it for the moment. */
286
287   }
288
289   m->t++;
290   if (m->t > m->doom) {
291     m->done = 1;
292   }
293 }
294
295
296 static void *
297 munch_init (Display *dpy, Window w)
298 {
299   struct state *st = (struct state *) calloc (1, sizeof(*st));
300   XWindowAttributes xgwa;
301   XGCValues gcv;
302   int i;
303   char *mm;
304
305   st->dpy = dpy;
306   st->window = w;
307   st->restart = 0;
308
309   /* get the dimensions of the window */
310   XGetWindowAttributes(st->dpy, w, &xgwa);
311
312   /* create the gc */
313   gcv.foreground= get_pixel_resource(st->dpy, xgwa.colormap,
314                                      "foreground","Foreground");
315   gcv.background= get_pixel_resource(st->dpy, xgwa.colormap,
316                                      "background","Background");
317
318   st->gc = XCreateGC(st->dpy, w, GCForeground|GCBackground, &gcv);
319
320   st->delay = get_integer_resource(st->dpy, "delay", "Integer");
321   if (st->delay < 0) st->delay = 0;
322
323   st->simul = get_integer_resource(st->dpy, "simul", "Integer");
324   if (st->simul < 1) st->simul = 1;
325
326   st->clear = get_integer_resource(st->dpy, "clear", "Integer");
327   if (st->clear < 0) st->clear = 0;
328
329   st->xor = get_boolean_resource(st->dpy, "xor", "Boolean");
330
331   mm = get_string_resource (st->dpy, "mismunch", "Mismunch");
332   if (!mm || !*mm || !strcmp(mm, "random"))
333     st->mismunch = random() & 1;
334   else
335     st->mismunch = get_boolean_resource (st->dpy, "mismunch", "Mismunch");
336
337   st->window_width = xgwa.width;
338   st->window_height = xgwa.height;
339
340   calc_logwidths(st);
341
342   /* always draw xor on mono. */
343   if (mono_p || st->xor) {
344     XSetFunction(st->dpy, st->gc, GXxor);
345   }
346
347   st->munchers = (muncher **) calloc(st->simul, sizeof(muncher *));
348   for (i = 0; i < st->simul; i++) {
349     st->munchers[i] = make_muncher(st);
350   }
351
352   return st;
353 }
354
355 static unsigned long
356 munch_draw (Display *dpy, Window w, void *closure)
357 {
358   struct state *st = (struct state *) closure;
359   int i;
360
361   for (i = 0; i < 5; i++) {
362
363   /* for (draw_i = 0; draw_i < simul; draw_i++)  */
364   {
365     munch(st, st->munchers[st->draw_i]);
366
367     if (st->munchers[st->draw_i]->done) {
368       st->draw_n++;
369
370       free(st->munchers[st->draw_i]);
371       st->munchers[st->draw_i] = make_muncher(st);
372     }
373   }
374
375   st->draw_i++;
376   if (st->draw_i >= st->simul) {
377     int i = 0;
378     st->draw_i = 0;
379     if (st->restart || (st->clear && st->draw_n >= st->clear)) {
380
381       char *mm = get_string_resource (st->dpy, "mismunch", "Mismunch");
382       if (!mm || !*mm || !strcmp(mm, "random"))
383         st->mismunch = random() & 1;
384
385       for (i = 0; i < st->simul; i++) {
386         free(st->munchers[i]);
387         st->munchers[i] = make_muncher(st);
388       }
389
390       XClearWindow(st->dpy, w);
391       st->draw_n = 0;
392       st->restart = 0;
393     }
394   }
395
396   }
397
398   return st->delay;
399 }
400
401
402 static void
403 munch_reshape (Display *dpy, Window window, void *closure, 
404                  unsigned int w, unsigned int h)
405 {
406   struct state *st = (struct state *) closure;
407   if (w != st->window_width ||
408       h != st->window_height) {
409     st->window_width = w;
410     st->window_height = h;
411     calc_logwidths(st);
412     st->restart = 1;
413     st->draw_i = 0;
414   }
415 }
416
417 static Bool
418 munch_event (Display *dpy, Window window, void *closure, XEvent *event)
419 {
420   return False;
421 }
422
423 static void
424 munch_free (Display *dpy, Window window, void *closure)
425 {
426   struct state *st = (struct state *) closure;
427   free (st);
428 }
429
430
431 static const char *munch_defaults [] = {
432   ".background:       black",
433   ".foreground:       white",
434   "*fpsSolid:         true",
435   "*delay:            10000",
436   "*mismunch:         random",
437   "*simul:            5",
438   "*clear:            65",
439   "*xor:              True",
440   0
441 };
442
443 static XrmOptionDescRec munch_options [] = {
444   { "-delay",         ".delay",       XrmoptionSepArg,  0 },
445   { "-simul",         ".simul",       XrmoptionSepArg,  0 },
446   { "-clear",         ".clear",       XrmoptionSepArg, "true" },
447   { "-xor",           ".xor",         XrmoptionNoArg,  "true" },
448   { "-no-xor",        ".xor",         XrmoptionNoArg,  "false" },
449   { "-classic",       ".mismunch",    XrmoptionNoArg,  "false" },
450   { "-mismunch",      ".mismunch",    XrmoptionNoArg,  "true" },
451   { "-random",        ".mismunch",    XrmoptionNoArg,  "random" },
452   { 0, 0, 0, 0 }
453 };
454
455
456 XSCREENSAVER_MODULE ("Munch", munch)