const char * const xdwCopyright=
/*===========================================================================*/
 " xdesktopwaves 1.3 - simulation of water waves on the X Windows desktop  \n"
 "                                                                         \n"
 " Copyright (C) 2004 Oliver Hamann (olha@users.sourceforge.net)           \n"
 "                                                                         \n"
 " This program is free software; you can redistribute it and/or modify    \n"
 " it under the terms of the GNU General Public License as published by    \n"
 " the Free Software Foundation; either version 2 of the License, or       \n"
 " (at your option) any later version.                                     \n"
 "                                                                         \n"
 " This program is distributed in the hope that it will be useful,         \n"
 " but WITHOUT ANY WARRANTY; without even the implied warranty of          \n"
 " MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the           \n"
 " GNU General Public License for more details.                            \n"
 "                                                                         \n"
 " You should have received a copy of the GNU General Public License       \n"
 " along with this program; if not, write to the Free Software             \n"
 " Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA \n";
/*===========================================================================*/

#include <sys/times.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <errno.h>
#include <signal.h>
#include <unistd.h>
#include <math.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include <X11/Xatom.h>
#include <X11/extensions/shape.h>


/*============================================================================*/
/*================================= Options ==================================*/
/*============================================================================*/

typedef enum {
	XDW_USE_ROOT,
	XDW_BACKDROP,
	XDW_WMBACKDROP,
	XDW_WINDOW
} xdwWindowCreationType;


typedef enum {
	XDW_OPAQUE,
	XDW_STIPPLED,
	XDW_SHAPED,
	XDW_WMOPACITY
} xdwTransparencyType;


/* Path/name of executable */
const char * xdwArg0="xdesktopwaves";


/* Option variables. */
int xdwOptVerb;
const char * xdwOptDisplay;
Bool xdwOptEnd;
xdwWindowCreationType xdwOptWindowCreation;
xdwTransparencyType xdwOptTransparency;
int xdwOptTranspaParam;
int xdwOptFrameRate;
int xdwOptSimsPerFrame;
int xdwOptEventsPerFrame;
int xdwOptResDivX;
int xdwOptResDivY;
int xdwOptCellW;
int xdwOptCellH;
int xdwOptMaxColors;
Bool xdwOptDoubleBuffer;
int xdwOptNice;
Bool xdwOptIdle;
int xdwOptMaxOptimization;
const char * xdwOptWaterColor;
const char * xdwOptSkyColor;
const char * xdwOptLightColor;
Bool xdwOptWavesByMouse;
Bool xdwOptWavesByWindows;
int xdwOptRain;
int xdwOptStorm;
int xdwOptViscosity;
int xdwOptSkyIntensity;
int xdwOptLightIntensity;
int xdwOptLightAltitude;
int xdwOptLightAzimuth;


/* Parameters for the quality option. */
const struct {
	int frameRate;
	int simsPerFrame;
	int eventsPerFrame;
	int resDivX;
	int resDivY;
	int cellWidth;
	int cellHeight;
	int maxColors;
} xdwQualityParams[10]={
	{ 12, 2, 1, 6, 6, 3, 3,   8 },
	{ 14, 3, 1, 5, 5, 3, 3,  12 },
	{ 16, 4, 1, 4, 4, 3, 3,  16 },
	{ 18, 5, 1, 3, 3, 3, 3,  22 },
	{ 20, 5, 1, 2, 2, 3, 3,  32 },
	{ 20, 6, 1, 2, 2, 2, 2,  48 },
	{ 25, 5, 2, 1, 2, 4, 2,  64 },
	{ 20, 9, 2, 2, 2, 1, 1,  64 },
	{ 25, 8, 3, 1, 2, 2, 1,  96 },
	{ 25,12, 4, 1, 1, 1, 1, 128 }
};


/* Color themes. */
const char * const xdwColorThemes[10][3] = {
	{ "#406080", "#9696C0", "#FFFFFF" },
	{ "#1020C0", "#8080D0", "#FFFFFF" },
	{ "#000C18", "#122E20", "#FFFF80" },
	{ "#384840", "#90A0B0", "#FFFFE8" },
	{ "#808060", "#C0C080", "#FFF0F0" },
	{ "#000000", "#004030", "#FFFFFF" },
	{ "#78A020", "#80E098", "#F0FFF0" },
	{ "#504030", "#807050", "#FFFFE0" },
	{ "#800000", "#FF3060", "#C0FFFF" },
	{ "#F0F8FF", "#807050", "#586040" }
};


static void xdwSetDefaultOptions(void)
{
	/* Set default values for all the options. */
	xdwOptVerb           =0;
	xdwOptDisplay        =NULL;
	xdwOptEnd            =False;
	xdwOptWindowCreation =XDW_BACKDROP;
	xdwOptTransparency   =XDW_SHAPED;
	xdwOptTranspaParam   =0;
	xdwOptFrameRate      =xdwQualityParams[5].frameRate;
	xdwOptSimsPerFrame   =xdwQualityParams[5].simsPerFrame;
	xdwOptEventsPerFrame =xdwQualityParams[5].eventsPerFrame;
	xdwOptResDivX        =xdwQualityParams[5].resDivX;
	xdwOptResDivY        =xdwQualityParams[5].resDivY;
	xdwOptCellW          =xdwQualityParams[5].cellWidth;
	xdwOptCellH          =xdwQualityParams[5].cellHeight;
	xdwOptMaxColors      =xdwQualityParams[5].maxColors;
	xdwOptDoubleBuffer   =True;
	xdwOptNice           =0;
	xdwOptIdle           =True;
	xdwOptMaxOptimization=2;
	xdwOptWaterColor     =xdwColorThemes[0][0];
	xdwOptSkyColor       =xdwColorThemes[0][1];
	xdwOptLightColor     =xdwColorThemes[0][2];
	xdwOptWavesByMouse   =True;
	xdwOptWavesByWindows =True;
	xdwOptRain           =0;
	xdwOptStorm          =0;
	xdwOptViscosity      =3;
	xdwOptSkyIntensity   =5;
	xdwOptLightIntensity =5;
	xdwOptLightAltitude  =30;
	xdwOptLightAzimuth   =-35;
}


static Bool xdwParseInt(const char * str, int minVal, int maxVal, int * pVal)
{
	int sign, digit, val;

	/* Parse a decimal integer without allowing unexpected characters,
	   and check range. */
	if (*str=='-') { sign=-1; str++; }
	else if (*str=='+') { sign=1; str++; }
	else sign=1;
	if (!*str) return False;
	for (val=0; ; str++) {
		digit=*str;
		if (!digit) break;
		digit-='0';
		if (digit<0 || digit>9) return False;
		val=val*10+digit;
	}
	val*=sign;
	if (val<minVal || val>maxVal) return False;
	*pVal=val;
	return True;
}


static void xdwParseOptions(int argc, char * argv[])
{
	const char * opt, * nm;
	char transpaStr[256];
	int i, j;

	/* Keep name of executable. */
	xdwArg0=argv[0];

	/* Parse options. */
	for (i=1; i<argc; ) {
		opt=argv[i++];
		if (*opt!='-') {
			fprintf(stderr,"%s: not an option: %s\n",xdwArg0,opt);
			exit(1);
		}
		nm=opt+1;
		if (*nm=='-') nm++;
		if (!strcmp(nm,"h") || !strcmp(nm,"help")) {
			printf(
				"Usage: %s [<option>]...\n"
				"Options:\n"
				"   -h|-help                      -db|-doublebuffer\n"
				"   -V|-version                  -ndb|-nodoublebuffer\n"
				"   -v|-verbose                    -n|-nice <increment>\n"
				"  -vv|-veryverbose                -i|-idle\n"
				"   -d|-display <name>            -ni|-noidle\n"
				"   -e|-end                       -mo|-maxoptimization <level>\n"
				"   -r|-root                       -c|-colortheme <0-9>\n"
				"   -b|-backdrop                  -wc|-watercolor <color>\n"
				" -wmb|-wmbackdrop                -sc|-skycolor <color>\n"
				"   -w|-window                    -lc|-lightcolor <color>\n"
				"   -o|-opaque                    -wm|-wavesbymouse\n"
				"   -t|-stippled                 -nwm|-nowavesbymouse\n"
				"   -s|-shaped                    -ww|-wavesbywindows\n"
				" -wmo|-wmopacity <0-100>        -nww|-nowavesbywindows\n"
				"   -q|-quality <0-9>             -rn|-rain <0-10>\n"
				"  -fr|-framerate <rate>          -st|-storm <0-10>\n"
				"  -sf|-simsperframe <count>      -vs|-viscosity <1-5>\n"
				"  -ef|-eventsperframe <count>    -si|-skyintensity <1-10>\n"
				"  -rd|-resdivision <rdx> <rdy>   -li|-lightintensity <1-10>\n"
				"  -cs|-cellsize <cw> <ch>       -lal|-lightaltitude <degrees>\n"
				"  -mc|-maxcolors <2-128>        -laz|-lightazimuth <degrees>\n"
				"For details please refer to the manual page: xdesktopwaves(1)\n",
				xdwArg0
			);
			exit(0);
		}
		else if (!strcmp(nm,"V") || !strcmp(nm,"version")) {
			printf("\n%s\n",xdwCopyright);
			exit(0);
		}
		else if (!strcmp(nm,"v") || !strcmp(nm,"verbose")) {
			xdwOptVerb=1;
		}
		else if (!strcmp(nm,"vv") || !strcmp(nm,"veryverbose")) {
			xdwOptVerb=2;
		}
		else if (!strcmp(nm,"d") || !strcmp(nm,"display")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			xdwOptDisplay=argv[i++];
		}
		else if (!strcmp(nm,"e") || !strcmp(nm,"end")) {
			xdwOptEnd=True;
		}
		else if (!strcmp(nm,"r") || !strcmp(nm,"root")) {
			xdwOptWindowCreation=XDW_USE_ROOT;
		}
		else if (!strcmp(nm,"b") || !strcmp(nm,"backdrop")) {
			xdwOptWindowCreation=XDW_BACKDROP;
		}
		else if (!strcmp(nm,"wmb") || !strcmp(nm,"wmbackdrop")) {
			xdwOptWindowCreation=XDW_WMBACKDROP;
		}
		else if (!strcmp(nm,"w") || !strcmp(nm,"window")) {
			xdwOptWindowCreation=XDW_WINDOW;
		}
		else if (!strcmp(nm,"o") || !strcmp(nm,"opaque")) {
			xdwOptTransparency=XDW_OPAQUE;
		}
		else if (!strcmp(nm,"t") || !strcmp(nm,"stippled")) {
			xdwOptTransparency=XDW_STIPPLED;
		}
		else if (!strcmp(nm,"s") || !strcmp(nm,"shaped")) {
			xdwOptTransparency=XDW_SHAPED;
		}
		else if (!strcmp(nm,"wmo") || !strcmp(nm,"wmopacity")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,100,&j)) goto L_BAD_OPT_ARG;
			xdwOptTransparency=XDW_WMOPACITY;
			xdwOptTranspaParam=j;
		}
		else if (!strcmp(nm,"q") || !strcmp(nm,"quality")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,9,&j)) goto L_BAD_OPT_ARG;
			xdwOptFrameRate     =xdwQualityParams[j].frameRate;
			xdwOptSimsPerFrame  =xdwQualityParams[j].simsPerFrame;
			xdwOptEventsPerFrame=xdwQualityParams[j].eventsPerFrame;
			xdwOptResDivX       =xdwQualityParams[j].resDivX;
			xdwOptResDivY       =xdwQualityParams[j].resDivY;
			xdwOptCellW         =xdwQualityParams[j].cellWidth;
			xdwOptCellH         =xdwQualityParams[j].cellHeight;
			xdwOptMaxColors     =xdwQualityParams[j].maxColors;
		}
		else if (!strcmp(nm,"fr") || !strcmp(nm,"framerate")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,1000,&j)) goto L_BAD_OPT_ARG;
			xdwOptFrameRate=j;
		}
		else if (!strcmp(nm,"sf") || !strcmp(nm,"simsperframe")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,1000,&j)) goto L_BAD_OPT_ARG;
			xdwOptSimsPerFrame=j;
		}
		else if (!strcmp(nm,"ef") || !strcmp(nm,"eventsperframe")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,1000,&j)) goto L_BAD_OPT_ARG;
			xdwOptEventsPerFrame=j;
		}
		else if (!strcmp(nm,"rd") || !strcmp(nm,"resdivision")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,256,&j)) goto L_BAD_OPT_ARG;
			xdwOptResDivX=j;
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,256,&j)) goto L_BAD_OPT_ARG;
			xdwOptResDivY=j;
		}
		else if (!strcmp(nm,"cs") || !strcmp(nm,"cellsize")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,256,&j)) goto L_BAD_OPT_ARG;
			xdwOptCellW=j;
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,256,&j)) goto L_BAD_OPT_ARG;
			xdwOptCellH=j;
		}
		else if (!strcmp(nm,"mc") || !strcmp(nm,"maxcolors")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],2,128,&j)) goto L_BAD_OPT_ARG;
			xdwOptMaxColors=j;
		}
		else if (!strcmp(nm,"db") || !strcmp(nm,"doublebuffer")) {
			xdwOptDoubleBuffer=True;
		}
		else if (!strcmp(nm,"ndb") || !strcmp(nm,"nodoublebuffer")) {
			xdwOptDoubleBuffer=False;
		}
		else if (!strcmp(nm,"n") || !strcmp(nm,"nice")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],-100,100,&j)) goto L_BAD_OPT_ARG;
			xdwOptNice=j;
		}
		else if (!strcmp(nm,"i") || !strcmp(nm,"idle")) {
			xdwOptIdle=True;
		}
		else if (!strcmp(nm,"ni") || !strcmp(nm,"noidle")) {
			xdwOptIdle=False;
		}
		else if (!strcmp(nm,"mo") || !strcmp(nm,"maxoptimization")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,100,&j)) goto L_BAD_OPT_ARG;
			xdwOptMaxOptimization=j;
		}
		else if (!strcmp(nm,"c") || !strcmp(nm,"colortheme")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,9,&j)) goto L_BAD_OPT_ARG;
			xdwOptWaterColor=xdwColorThemes[j][0];
			xdwOptSkyColor  =xdwColorThemes[j][1];
			xdwOptLightColor=xdwColorThemes[j][2];
		}
		else if (!strcmp(nm,"wc") || !strcmp(nm,"watercolor")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			xdwOptWaterColor=argv[i++];
		}
		else if (!strcmp(nm,"sc") || !strcmp(nm,"skycolor")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			xdwOptSkyColor=argv[i++];
		}
		else if (!strcmp(nm,"lc") || !strcmp(nm,"lightcolor")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			xdwOptLightColor=argv[i++];
		}
		else if (!strcmp(nm,"wm") || !strcmp(nm,"wavesbymouse")) {
			xdwOptWavesByMouse=True;
		}
		else if (!strcmp(nm,"nwm") || !strcmp(nm,"nowavesbymouse")) {
			xdwOptWavesByMouse=False;
		}
		else if (!strcmp(nm,"ww") || !strcmp(nm,"wavesbywindows")) {
			xdwOptWavesByWindows=True;
		}
		else if (!strcmp(nm,"nww") || !strcmp(nm,"nowavesbywindows")) {
			xdwOptWavesByWindows=False;
		}
		else if (!strcmp(nm,"rn") || !strcmp(nm,"rain")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,10,&j)) goto L_BAD_OPT_ARG;
			xdwOptRain=j;
		}
		else if (!strcmp(nm,"st") || !strcmp(nm,"storm")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,10,&j)) goto L_BAD_OPT_ARG;
			xdwOptStorm=j;
		}
		else if (!strcmp(nm,"vs") || !strcmp(nm,"viscosity")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,5,&j)) goto L_BAD_OPT_ARG;
			xdwOptViscosity=j;
		}
		else if (!strcmp(nm,"si") || !strcmp(nm,"skyintensity")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,10,&j)) goto L_BAD_OPT_ARG;
			xdwOptSkyIntensity=j;
		}
		else if (!strcmp(nm,"li") || !strcmp(nm,"lightintensity")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],1,10,&j)) goto L_BAD_OPT_ARG;
			xdwOptLightIntensity=j;
		}
		else if (!strcmp(nm,"lal") || !strcmp(nm,"lightaltitude")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],0,90,&j)) goto L_BAD_OPT_ARG;
			xdwOptLightAltitude=j;
		}
		else if (!strcmp(nm,"laz") || !strcmp(nm,"lightazimuth")) {
			if (i>=argc) goto L_MISSING_OPT_ARG;
			if (!xdwParseInt(argv[i++],-360,360,&j)) goto L_BAD_OPT_ARG;
			xdwOptLightAzimuth=j;
		}
		/* --- deprecated options --- */
		else if (!strcmp(nm,"hc") || !strcmp(nm,"highlightcolor")) {
			fprintf(stderr,"%s: option %s is deprecated and should not be used any longer.\n",xdwArg0,opt);
			if (i>=argc) goto L_MISSING_OPT_ARG;
			xdwOptLightColor=argv[i++];
		}
		else if (!strcmp(nm,"wr") || !strcmp(nm,"wavesbyrain")) {
			fprintf(stderr,"%s: option %s is deprecated and should not be used any longer.\n",xdwArg0,opt);
			if (!xdwOptRain) xdwOptRain=9;
		}
		else if (!strcmp(nm,"nwr") || !strcmp(nm,"nowavesbyrain")) {
			fprintf(stderr,"%s: option %s is deprecated and should not be used any longer.\n",xdwArg0,opt);
			xdwOptRain=0;
		}
		else if (!strcmp(nm,"ws") || !strcmp(nm,"wavesbystorm")) {
			fprintf(stderr,"%s: option %s is deprecated and should not be used any longer.\n",xdwArg0,opt);
			if (!xdwOptStorm) xdwOptStorm=9;
		}
		else if (!strcmp(nm,"nws") || !strcmp(nm,"nowavesbystorm")) {
			fprintf(stderr,"%s: option %s is deprecated and should not be used any longer.\n",xdwArg0,opt);
			xdwOptStorm=0;
		}
		/* --------------------------- */
		else {
			fprintf(stderr,"%s: illegal option: %s\n",xdwArg0,opt);
			exit(1);
		}
	}

	/* Apply some rules on the options. */
	if (xdwOptWindowCreation==XDW_USE_ROOT && xdwOptTransparency!=XDW_OPAQUE &&
	    xdwOptTransparency!=XDW_STIPPLED) {
		if (xdwOptVerb) printf("Forcing stippled mode for drawing to root window.\n");
		xdwOptTransparency=XDW_STIPPLED;
	}
	if (xdwOptTransparency==XDW_SHAPED && !xdwOptDoubleBuffer) {
		if (xdwOptVerb) printf("Forcing double buffering for shaped mode.\n");
		xdwOptDoubleBuffer=True;
	}
	if (xdwOptTransparency==XDW_STIPPLED && xdwOptDoubleBuffer) {
		if (xdwOptVerb) printf("Forcing single buffering for stippled mode.\n");
		xdwOptDoubleBuffer=False;
	}

	/* Possibly report the resulting settings. */
	if (xdwOptVerb>=1) printf(
		"Applied settings:\n"
		"  display         : %-16s max optimization: %d\n"
		"  end             : %-16s water color     : \"%s\"\n"
		"  window mode     : %-16s sky color       : \"%s\"\n"
		"  transparency    : %-16s light color     : \"%s\"\n"
		"  max frame rate  : %-16d waves by mouse  : %s\n"
		"  sims per frame  : %-16d waves by windows: %s\n"
		"  events per frame: %-16d rain            : %d\n"
		"  resolution div  : %-2d %-13d storm           : %d\n"
		"  cell size       : %-2d %-13d viscosity       : %d\n"
		"  max color count : %-16d sky intensity   : %d\n"
		"  double buffering: %-16s light intensity : %d\n"
		"  nice            : %-16d light altitude  : %d\n"
		"  allow idle mode : %-16s light azimuth   : %d\n",
		xdwOptDisplay ? xdwOptDisplay : "",
		xdwOptMaxOptimization,
		xdwOptEnd ? "yes" : "no",
		xdwOptWaterColor,
		xdwOptWindowCreation==XDW_USE_ROOT ? "root" :
			xdwOptWindowCreation==XDW_BACKDROP ? "backdrop" :
				xdwOptWindowCreation==XDW_WMBACKDROP ? "wm-backdrop" :
					"normal window",
		xdwOptSkyColor,
		xdwOptTransparency==XDW_OPAQUE ? "opaque" :
			xdwOptTransparency==XDW_STIPPLED ? "stippled" :
				xdwOptTransparency==XDW_SHAPED ? "shaped" :
					(sprintf(transpaStr,"opacity %d",xdwOptTranspaParam), transpaStr),
		xdwOptLightColor,
		xdwOptFrameRate,
		xdwOptWavesByMouse ? "yes" : "no",
		xdwOptSimsPerFrame,
		xdwOptWavesByWindows ? "yes" : "no",
		xdwOptEventsPerFrame,
		xdwOptRain,
		xdwOptResDivX, xdwOptResDivY,
		xdwOptStorm,
		xdwOptCellW, xdwOptCellH,
		xdwOptViscosity,
		xdwOptMaxColors,
		xdwOptSkyIntensity,
		xdwOptDoubleBuffer ? "yes" : "no",
		xdwOptLightIntensity,
		xdwOptNice,
		xdwOptLightAltitude,
		xdwOptIdle ? "yes" : "no",
		xdwOptLightAzimuth
	);

	/* Ready. */
	return;

	/* Error handling. */
L_MISSING_OPT_ARG:
	fprintf(stderr,"%s: missing argument for option %s\n",xdwArg0,opt);
	exit(1);
L_BAD_OPT_ARG:
	fprintf(stderr,"%s: illegal argument for option %s\n",xdwArg0,opt);
	exit(1);
}


/*============================================================================*/
/*====================== Mathematical Helper Functions =======================*/
/*============================================================================*/

static int xdwSqrt32(unsigned x)
{
	unsigned a, b, c;
	int i;

	/* Calculate the square root of x. */
	a=0x8000; b=0x4000; c=0x40000000;
	for (i=14; x!=c && i>=0; i--, b>>=1) {
		if (x<c) { c-=(a+a-b)<<i; a-=b; }
		else     { c+=(a+a+b)<<i; a+=b; }
	}
	return (int)a;
}


static int xdwRandom(int minVal, int maxVal)
{
	/* Calculate a pseudo random number in the range from minVal to maxVal. */
	return minVal+(int)((((double)rand())*(maxVal-minVal)+RAND_MAX/2)/RAND_MAX);
}


/*============================================================================*/
/*========================== Data type for a region  =========================*/
/*============================================================================*/

/* xdwRegion is similar to XRegion. Main advantage is that we have direct
   access to the internal elements (which are scan line segments here). */


typedef struct xdwRegScanStruct {
	struct xdwRegScanStruct * next;
		/* Next element in the list of scan line segments. */
	int x1, x2;
		/* Horizontal extent of the scan line segment. */
} xdwRegScan;


typedef struct {
	int y1, y2;
		/* Vertical extent of the array of rows (see below). */
	xdwRegScan * * rows;
		/* Array of lists of scan line segments, or NULL. rows[index] is a
		   (possibly empty) list of segments at y=y1+index. index ranges
		   from 0 to y2-y1-1. For each element s, the following condition is
		   always true: s->x1 < s->x2 && (!s->next || s->x2 < s->next->x1). */
} xdwRegion;


xdwRegScan * xdwGarbageRegScans;
	/* List of garbage scan line segments for quick re-allocation. */


static xdwRegScan * xdwAllocRegScan()
{
	xdwRegScan * s;

	if (xdwGarbageRegScans) {
		s=xdwGarbageRegScans;
		xdwGarbageRegScans=s->next;
	}
	else {
		s=(xdwRegScan*)malloc(sizeof(xdwRegScan));
	}
	return s;
}


static void xdwFreeRegScanList(xdwRegScan * first)
{
	xdwRegScan * last;

	if (first) {
		for (last=first; last->next; last=last->next);
		last->next=xdwGarbageRegScans;
		xdwGarbageRegScans=first;
	}
}


static void xdwInitRegion(xdwRegion * reg)
{
	reg->y1=0;
	reg->y2=0;
	reg->rows=NULL;
}


static void xdwEmptyRegion(xdwRegion * reg)
{
	xdwRegScan * * r, * * re;

	if (reg->rows) {
		r=reg->rows;
		re=r+(reg->y2-reg->y1);
		do {
			if (*r) xdwFreeRegScanList(*r);
			r++;
		} while (r<re);
		free(reg->rows);
		reg->rows=NULL;
	}
	reg->y1=0;
	reg->y2=0;
}


static int xdwCountRegionPixels(const xdwRegion * reg)
{
	xdwRegScan * * r, * * re;
	xdwRegScan * s;
	int pixels;

	pixels=0;
	if (reg->rows) {
		r=reg->rows;
		re=r+(reg->y2-reg->y1);
		do {
			s=*r;
			if (s) {
				do {
					pixels+=s->x2-s->x1;
					s=s->next;
				} while (s);
			}
			r++;
		} while (r<re);
	}
	return pixels;
}


static void xdwSetRegionRect(xdwRegion * reg, int x1, int y1, int x2, int y2)
{
	xdwRegScan * * r, * * re;
	xdwRegScan *s;

	xdwEmptyRegion(reg);
	if (x1>=x2 || y1>=y2) return;
	reg->y1=y1;
	reg->y2=y2;
	reg->rows=(xdwRegScan**)malloc((y2-y1)*sizeof(xdwRegScan*));
	r=reg->rows;
	re=r+(y2-y1);
	do {
		s=xdwAllocRegScan();
		s->next=NULL;
		s->x1=x1;
		s->x2=x2;
		*r=s;
		r++;
	} while (r<re);
}


static void xdwRegAndRect(xdwRegion * reg, int x1, int y1, int x2, int y2)
{
	xdwRegScan * * r, * * re,  * * ps;
	xdwRegScan * s;

	if (!reg->rows) return;
	if (y1<reg->y1) y1=reg->y1;
	if (y2>reg->y2) y2=reg->y2;
	if (y1>=y2 || x1>=x2) {
		xdwEmptyRegion(reg);
		return;
	}
	r=reg->rows;
	if (y1>reg->y1) {
		re=r+(y1-reg->y1);
		do {
			if (*r) {
				xdwFreeRegScanList(*r);
				*r=NULL;
			}
			r++;
		} while (r<re);
	}
	re=r+(y2-y1);
	do {
		s=*r;
		if (s) {
			ps=r;
			do {
				if (s->x2>x1) {
					if (s->x1<x1) s->x1=x1;
					do {
						if (s->x2>x2) {
							if (s->x1<x2) {
								s->x2=x2;
								ps=&s->next;
								s=*ps;
								if (!s) break;
							}
							do {
								*ps=s->next;
								s->next=xdwGarbageRegScans;
								xdwGarbageRegScans=s;
								s=*ps;
							} while (s);
							break;
						}
						ps=&s->next;
						s=*ps;
					} while (s);
					break;
				}
				*ps=s->next;
				s->next=xdwGarbageRegScans;
				xdwGarbageRegScans=s;
				s=*ps;
			} while (s);
		}
		r++;
	} while (r<re);
	if (reg->y2>y2) {
		re=r+(reg->y2-y2);
		do {
			if (*r) {
				xdwFreeRegScanList(*r);
				*r=NULL;
			}
			r++;
		} while (r<re);
	}
}


static void xdwRegAndNotRect(xdwRegion * reg, int x1, int y1, int x2, int y2)
{
	xdwRegScan * * r, * * re,  * * ps;
	xdwRegScan * s, * s2;

	if (!reg->rows) return;
	if (y1<reg->y1) y1=reg->y1;
	if (y2>reg->y2) y2=reg->y2;
	if (y1>=y2 || x1>=x2) return;
	r=reg->rows+(y1-reg->y1);
	re=r+(y2-y1);
	do {
		s=*r;
		if (s) {
			ps=r;
			do {
				if (s->x2>x1) {
					if (s->x1<x1) {
						if (s->x2>x2) {
							s2=xdwAllocRegScan();
							s2->next=s->next;
							s->next=s2;
							s2->x1=x2;
							s2->x2=s->x2;
							s->x2=x1;
							break;
						}
						s->x2=x1;
						ps=&s->next;
						s=*ps;
						if (!s) break;
					}
					do {
						if (s->x2>x2) {
							if (s->x1>=x2) break;
							s->x1=x2;
							break;
						}
						*ps=s->next;
						s->next=xdwGarbageRegScans;
						xdwGarbageRegScans=s;
						s=*ps;
					} while (s);
					break;
				}
				ps=&s->next;
				s=*ps;
			} while (s);
		}
		r++;
	} while (r<re);
}


static void xdwRegAndNotReg(xdwRegion * reg, const xdwRegion * reg2)
{
	xdwRegScan * * r, * * re,  * * q, * * ps;
	xdwRegScan * s, * s2, * t;
	int y1, y2;

	if (!reg->rows || !reg2->rows) return;
	y1=reg2->y1; if (y1<reg->y1) y1=reg->y1;
	y2=reg2->y2; if (y2>reg->y2) y2=reg->y2;
	if (y1>=y2) return;
	r=reg->rows+(y1-reg->y1);
	re=r+(y2-y1);
	q=reg2->rows+(y1-reg2->y1);
	do {
		if ((s=*r)!=NULL && (t=*q)!=NULL) {
			for (ps=r;;) {
				if (s->x2<=t->x1) {
					ps=&s->next;
					s=*ps;
					if (s) continue;
				}
				else if (s->x1>=t->x2) {
					t=t->next;
					if (t) continue;
				}
				else if (s->x2<=t->x2) {
					if (s->x1>=t->x1) {
						*ps=s->next;
						s->next=xdwGarbageRegScans;
						xdwGarbageRegScans=s;
						s=*ps;
						if (s) continue;
					}
					else {
						s->x2=t->x1;
						ps=&s->next;
						s=*ps;
						if (s) continue;
					}
				}
				else if (s->x1>=t->x1) {
					s->x1=t->x2;
					t=t->next;
					if (t) continue;
				}
				else {
					s2=xdwAllocRegScan();
					s2->next=s->next;
					s->next=s2;
					s2->x1=t->x2;
					s2->x2=s->x2;
					s->x2=t->x1;
					ps=&s->next;
					s=s2;
					t=t->next;
					if (t) continue;
				}
				break;
			}
		}
		r++;
		q++;
	} while (r<re);
}


/*============================================================================*/
/*============================ Processor Features ============================*/
/*============================================================================*/

Bool xdwCPUHasCPUID      =False;
Bool xdwCPUIsAuthenticAMD=False;
Bool xdwCPUIsGenuineIntel=False;
Bool xdwCPUHasMMX        =False;
Bool xdwCPUHasFXSR       =False;
Bool xdwCPUHasSSE        =False;
Bool xdwCPUHasSSE2       =False;


static void xdwDetectCPUFeatures(void)
{
#if defined(XDW_MAX_OPTIMIZATION) && XDW_MAX_OPTIMIZATION < 1

	/* CPU detection not necessary for optimization level 0. */

#elif defined(__GNUC__) && defined(__i386__)
	int features;

	/* Detection of 32-bit x86 CPU. */

	/* Check for CPUID. */
	asm volatile (
		"  pushfl                   \n"
		"  popl   %%eax             \n"
		"  movl   %%eax,%%ecx       \n"
		"  xorl   $0x00200000,%%eax \n"
		"  pushl  %%eax             \n"
		"  popfl                    \n"
		"  pushfl                   \n"
		"  popl   %%eax             \n"
		"  xorl   %%ecx,%%eax       \n"
		"  pushl  %%ecx             \n"
		"  popfl                    \n"
		"  andl   $0x00200000,%%eax \n"
		"  shrl   $21,%%eax         \n"
		: "=a"(xdwCPUHasCPUID) : : "ecx","edx","cc"
	);

	/* Check for Authentic AMD. */
	if (xdwCPUHasCPUID) asm volatile (
		"  xorl   %%eax,%%eax       \n"
		"  cpuid                    \n"
		"  xorl   %%eax,%%eax       \n"
		"  cmp    $0x68747541,%%ebx \n"
		"  jne    XDWDCAA_1         \n"
		"  cmpl   $0x69746e65,%%edx \n"
		"  jne    XDWDCAA_1         \n"
		"  cmpl   $0x444d4163,%%ecx \n"
		"  jne    XDWDCAA_1         \n"
		"  movl   $1,%%eax          \n"
		"XDWDCAA_1:                 \n"
		: "=a"(xdwCPUIsAuthenticAMD) : : "ebx","ecx","edx","cc"
	);

	/* Check for Genuine Intel. */
	if (xdwCPUHasCPUID) asm volatile (
		"  xorl   %%eax,%%eax       \n"
		"  cpuid                    \n"
		"  xorl   %%eax,%%eax       \n"
		"  cmpl   $0x756e6547,%%ebx \n"
		"  jne    XDWDCGI_1         \n"
		"  cmpl   $0x49656e69,%%edx \n"
		"  jne    XDWDCGI_1         \n"
		"  cmpl   $0x6c65746e,%%ecx \n"
		"  jne    XDWDCGI_1         \n"
		"  movl   $1,%%eax          \n"
		"XDWDCGI_1:                 \n"
		: "=a"(xdwCPUIsGenuineIntel) : : "ebx","ecx","edx","cc"
	);

	/* Check for MMX, FXSR, SSE and SSE2. */
	if (xdwCPUIsAuthenticAMD || xdwCPUIsGenuineIntel) {
		asm volatile (
			"  movl $1,%%eax            \n"
			"  cpuid                    \n"
			: "=d"(features) : : "eax","ebx","ecx","cc"
		);
		if (features&(1<<23)) xdwCPUHasMMX =True;
		if (features&(1<<24)) xdwCPUHasFXSR=True;
		if (features&(1<<25)) xdwCPUHasSSE =True;
		if (features&(1<<26)) xdwCPUHasSSE2=True;
	}
#elif defined(__GNUC__) && defined(__x86_64__)
	int features;

	/* Detection of 64-bit x86 CPU. */

	/* Check for CPUID. */
	asm volatile (
		"  pushf                    \n"
		"  movl   (%%rsp),%%eax     \n"
		"  movl   %%eax,%%ecx       \n"
		"  xorl   $0x00200000,%%eax \n"
		"  movl   %%eax,(%%rsp)     \n"
		"  popf                     \n"
		"  pushf                    \n"
		"  movl   (%%rsp),%%eax     \n"
		"  xorl   %%ecx,%%eax       \n"
		"  movl   %%ecx,(%%rsp)     \n"
		"  popf                     \n"
		"  andl   $0x00200000,%%eax \n"
		"  shrl   $21,%%eax         \n"
		: "=a"(xdwCPUHasCPUID) : : "ecx","edx","cc"
	);

	/* Check for Authentic AMD. */
	if (xdwCPUHasCPUID) asm volatile (
		"  xorl   %%eax,%%eax       \n"
		"  cpuid                    \n"
		"  xorl   %%eax,%%eax       \n"
		"  cmp    $0x68747541,%%ebx \n"
		"  jne    XDWDCAA_1         \n"
		"  cmpl   $0x69746e65,%%edx \n"
		"  jne    XDWDCAA_1         \n"
		"  cmpl   $0x444d4163,%%ecx \n"
		"  jne    XDWDCAA_1         \n"
		"  movl   $1,%%eax          \n"
		"XDWDCAA_1:                 \n"
		: "=a"(xdwCPUIsAuthenticAMD) : : "ebx","ecx","edx","cc"
	);

	/* Check for Genuine Intel. */
	if (xdwCPUHasCPUID) asm volatile (
		"  xorl   %%eax,%%eax       \n"
		"  cpuid                    \n"
		"  xorl   %%eax,%%eax       \n"
		"  cmpl   $0x756e6547,%%ebx \n"
		"  jne    XDWDCGI_1         \n"
		"  cmpl   $0x49656e69,%%edx \n"
		"  jne    XDWDCGI_1         \n"
		"  cmpl   $0x6c65746e,%%ecx \n"
		"  jne    XDWDCGI_1         \n"
		"  movl   $1,%%eax          \n"
		"XDWDCGI_1:                 \n"
		: "=a"(xdwCPUIsGenuineIntel) : : "ebx","ecx","edx","cc"
	);

	/* Check for MMX, FXSR, SSE and SSE2. */
	if (xdwCPUIsAuthenticAMD || xdwCPUIsGenuineIntel) {
		asm volatile (
			"  movl $1,%%eax            \n"
			"  cpuid                    \n"
			: "=d"(features) : : "eax","ebx","ecx","cc"
		);
		if (features&(1<<23)) xdwCPUHasMMX =True;
		if (features&(1<<24)) xdwCPUHasFXSR=True;
		if (features&(1<<25)) xdwCPUHasSSE =True;
		if (features&(1<<26)) xdwCPUHasSSE2=True;
	}
#endif

	/* Report detected features if very verbose. */
	if (xdwOptVerb>=2) {
		if (xdwCPUHasCPUID      ) printf("CPUID detected\n");
		if (xdwCPUIsGenuineIntel) printf("Genuine Intel detected\n");
		if (xdwCPUIsAuthenticAMD) printf("Authentic AMD detected\n");
		if (xdwCPUHasMMX        ) printf("MMX detected\n");
		if (xdwCPUHasFXSR       ) printf("FXSR detected\n");
		if (xdwCPUHasSSE        ) printf("SSE detected\n");
		if (xdwCPUHasSSE2       ) printf("SSE2 detected\n");
	}
}


/*============================================================================*/
/*========================== The Cellular Automata ===========================*/
/*============================================================================*/

int xdwCellCols, xdwCellRows;
	/* Number of columns and rows in the grid of cells. */


int xdwCellMemCols;
	/* Number of columns in memory. This can be a little bit greater than
	   xdwCellCols. The additional cells are not used. Goal is to have the
	   same 16-byte alignment for each row. */


short * xdwCells;
	/* The grid of cells. This data structure is a little bit awkward, for a
	   better performance of the MMX and SSE2 variants of the algorithm. Each
	   cell (c,r) with c = 0 to xdwCellCols-1 and r = 0 to xdwCellRows-1 has
	   four states:
	     level    = xdwCells[(r*3+0)*xdwCellMemCols+c]
	     velocity = xdwCells[(r*3+1)*xdwCellMemCols+c]
	     covered  = xdwCells[(r*3+2)*xdwCellMemCols+c]&1023
	     fading   = xdwCells[(r*3+2)*xdwCellMemCols+c]>>10
	   "level" is the level of water or you can say the vertical position of
	   the mass. "velocity" is the vertical velocity of the water (or mass).
	   "covered" is the number of boats (windows and mouse) stacked on the
	   cell. "fading" is a trick variable for fading from covered=0 to
	   covered!=0 and back. It steps from 25 (got covered) down to 0 (ready
	   with covering) and from -25 (got uncovered) up to 0 (ready with
	   uncovering). The first column, the last column, the first row and the
	   last two rows are making up the borders (the algorithms are easier with
	   the additional border row at the end). They are always covered and should
	   have level=0 and velocity=0. The lower-right corner of the upper-left
	   cell lies in the center of the upper-left pixel of the canvas. And the
	   upper-left corner of the right cell of the second-last row lies in the
	   center of the lower-right pixel of the canvas. The second cell of each
	   row is 16-byte aligned, more precise: each pointer
	   (char*)&xdwCells[n*xdwCellMemCols+1] is a multiple of 16. */


short * xdwCellsMem;
	/* Pointer to the memory allocated for the cells. This may not be aligned
	   correctly. */


const int xdwCellFadingTable[64]={
	/* Table for the trick of fading from covered to uncovered and back. The
	   values are added to the level of a faded cell on each time slice. The
	   index is 32 plus the fading value which ranges from -25 to 25 (see
	   description of xdwCells). */
	   0,    0,    0,    0,    0,    0,    0,
	 -36,  -72, -108, -143, -178,
	-212, -246, -278, -310, -340,
	-369, -397, -424, -448, -472,
	-493, -513, -531, -546, -560,
	-572, -582, -590, -595, -598,
	   0,
	-450, -471, -485, -489, -484,
	-470, -445, -411, -367, -314,
	-253, -183, -107,  -24,   61,
	 151,  243,  335,  425,  512,
	 594,  669,  737,  795,  843,
	   0,    0,    0,    0,    0,    0
};


static void xdwInitCells(int windowWidth, int windowHeight)
{
	int col, row;

	/* Calculate number of columns and rows. */
	xdwCellCols=((windowWidth-1)/xdwOptResDivX-1)/xdwOptCellW+3;
	xdwCellRows=((windowHeight-1)/xdwOptResDivY-1)/xdwOptCellH+4;

	/* Calculate number of columns in memory (=>alignment). */
	xdwCellMemCols=(xdwCellCols+7)&~7;

	/* Allocate and clear memory for the cells. */
	xdwCellsMem=malloc((xdwCellMemCols*xdwCellRows*3+7)*2);
	memset(xdwCellsMem,0,(xdwCellMemCols*xdwCellRows*3+7)*2);

	/* Have a pointer for the grid of cells (=>alignment). */
	xdwCells=xdwCellsMem+((((short*)0)-xdwCellsMem-1)&7);

	/* Cover the borders. */
	for (row=0; row<xdwCellRows; row++) {
		xdwCells[(row*3+2)*xdwCellMemCols]=1;
		xdwCells[(row*3+2)*xdwCellMemCols+xdwCellCols-1]=1;
	}
	for (col=1; col<xdwCellCols-1; col++) {
		xdwCells[2*xdwCellMemCols+col]=1;
		xdwCells[((xdwCellRows-2)*3+2)*xdwCellMemCols+col]=1;
		xdwCells[((xdwCellRows-1)*3+2)*xdwCellMemCols+col]=1;
	}
}


static void xdwClearCells()
{
	short * p;
	int row;

	/* Zero the level and the velocity of all cells. */
	for (row=0; row<xdwCellRows; row++) {
		p=xdwCells+row*3*xdwCellMemCols;
		memset(p,0,sizeof(short)*xdwCellCols);
		memset(p+xdwCellMemCols,0,sizeof(short)*xdwCellCols);
	}
}


static Bool xdwCoverRect(int x1, int y1, int x2, int y2, int deltaCovering)
{
	short * p, * pe;
	short c;

	/* Increase or decrease the covering of a rectangular region of cells.
	   The given coordinates are in window pixels. */
	x1=(2*x1-xdwOptResDivX)/(2*xdwOptCellW*xdwOptResDivX)+1;
	x2=(2*x2-xdwOptResDivX-1)/(2*xdwOptCellW*xdwOptResDivX)+2;
	if (x1<1) x1=1;
	if (x2>xdwCellCols-1) x2=xdwCellCols-1;
	if (x1>=x2) return False;
	y1=(2*y1-xdwOptResDivY)/(2*xdwOptCellH*xdwOptResDivY)+1;
	y2=(2*y2-xdwOptResDivY-1)/(2*xdwOptCellH*xdwOptResDivY)+2;
	if (y1<1) y1=1;
	if (y2>xdwCellRows-2) y2=xdwCellRows-2;
	if (y1>=y2) return False;
	do {
		p=xdwCells+(y1*3+2)*xdwCellMemCols+x1;
		pe=p+(x2-x1);
		do {
			c=*p;
			if ((c&0x3ff)==0) c+=25<<10;
			c+=deltaCovering;
			if ((c&0x3ff)==0) c-=25<<10;
			*p=c;
			p++;
		} while (p<pe);
		y1++;
	} while (y1<y2);
	return True;
}


static Bool xdwCoverCircle(int x, int y, int r, int deltaCovering)
{
	int w, h;
	Bool b;

	/* Increase or decrease the covering of a circular region of cells.
	   The given coordinates are in window pixels. */
	for (h=0,b=False; h<r; h++) {
		w=xdwSqrt32(r*r-h*h);
		b|=xdwCoverRect(x-w,y+h,x+w,y+h+1,deltaCovering);
		b|=xdwCoverRect(x-w,y-h-1,x+w,y-h,deltaCovering);
	}
	return b;
}


static Bool xdwPutRaindropOnCell(int cx, int cy, int volume)
{
	static const int drop[9]={160,128,64,0,-48,-80,-96,-72,-24};
	short * pv, * pc;
	int x, y, x1, y1, x2, y2, v, r;
	Bool changed;

	if (volume<=0) return False;
	if (volume>100) volume=100;
	x1=cx-5;
	y1=cy-5;
	x2=cx+6;
	y2=cy+6;
	if (x1<1) x1=1;
	if (y1<1) y1=1;
	if (x2>xdwCellCols-1) x2=xdwCellCols-1;
	if (y2>xdwCellRows-2) y2=xdwCellRows-2;
	changed=False;
	for (y=y1; y<y2; y++) {
		pv=xdwCells+(y*3+1)*xdwCellMemCols;
		pc=pv+xdwCellMemCols;
		for (x=x1; x<x2; x++) {
			r=xdwSqrt32(((x-cx)*(x-cx)+(y-cy)*(y-cy))*2);
			if (r>8 || (pc[x]&1023)!=0) continue;
			changed=True;
			v=pv[x]+drop[r]*volume;
			if (v<-0x8000) v=-0x8000; else if (v>0x7fff) v=0x7fff;
			pv[x]=(short)v;
		}
	}
	return changed;
}


static Bool xdwPutRaindrop(int x, int y, int volume)
{
	return xdwPutRaindropOnCell(
		x/(xdwOptCellW*xdwOptResDivX)+1,
		y/(xdwOptCellH*xdwOptResDivY)+1,
		volume
	);
}


static Bool xdwUpdateRain(int timeSlices)
{
	static int rem=0;
	Bool changed;

	/* Create a number of raindrops per cell and time slice. A raindrop is
	   just a modification of the velocity of some cells. */
	if (xdwOptRain<=0) return False;
	rem+=xdwCellRows*xdwCellCols*timeSlices/100*
	     xdwOptRain*xdwOptRain/100+10*xdwOptRain;
	changed=False;
	while (rem>0) {
		rem-=xdwRandom(2000,6000);
		changed|=xdwPutRaindropOnCell(
			xdwRandom(1,xdwCellCols-2),
			xdwRandom(1,xdwCellRows-3),
			xdwRandom(25,100)
		);
	}
	return changed;
}


static void xdwUpdateStromRow(int row)
{
	short * p, * pe;
	int v, n, m, k;

	/* For one row, perform one time slice of the storm simulation. The basic
	   idea was to calculate the pressure (=acceleration of cells) from the
	   product of airflow vector and water surface vector. With some pressure
	   smoothing and "airflow-tear-offs", it's what this algorithm is nearly
	   doing... */
	if (xdwOptStorm<=0) return;
	p=xdwCells+row*3*xdwCellMemCols;
	pe=p+xdwCellCols-2;
	n=0;
	k=57+xdwOptStorm*xdwOptStorm*35/10;
	do {
		v=k;
		if (!p[2*xdwCellMemCols]) v=p[0];
		p++;
		v-=p[0];
		if ((unsigned)v>k) v=0;
		m=(n+7)>>3;
		n+=v;
		n-=m;
		v-=m;
		v+=p[xdwCellMemCols];
		if (v<-0x8000) v=-0x8000; else if (v>0x7fff) v=0x7fff;
		p[xdwCellMemCols]=(short)v;
	} while (p<pe);
}


static void xdwOperateCellsOpt0(short * cells, int count)
{
	short * p, * pe;
	int l1, l2, l3, v, c, cols, cols3;

	/* Here's the core algorithm of this program - at optimization level 0.
	   It performs one step (one time slice) of the cellular automata for one
	   row of cells (or less). The velocity of each cell is adapted by the
	   difference of the level and the average level of the adjacent cells
	   (think of springs between the cells). The velocity is even adapted by
	   friction (viscosity). Of course, the level of each cell is adapted by
	   velocity. Besides, the influence of covering (boats...) and its fading
	   is calculated here. Velocity is updated one row ahead of level and fading.
	   With i = 0 to count-1, cells[i] is the modified level and
	   cells[4*xdwCellMemCols+i] is the modified velocity. The macro stuff is
	   just for making true constants from viscosity parameters, this may
	   produce faster code. */
#	define XDWOCO0(C1,C2) \
		cols=xdwCellMemCols; \
		cols3=cols*3; \
		p=cells; \
		pe=p+count; \
		l1=p[cols3-1]; \
		l2=p[cols3]; \
		do { \
			v=p[4*cols]; \
			v-=(v+C1)>>C2; \
			v+=l1; \
			l1=l2; \
			l2<<=2; \
			v-=l2; \
			l3=p[0]; \
			v+=l3; \
			l3+=p[cols]>>2; \
			v+=p[2*cols3]; \
			c=p[2*cols]; \
			if (c) { \
				if ((c&0xfc00)!=0) { \
					l3+=xdwCellFadingTable[(c>>10)+32]; \
					if (c>0) { \
						c-=1<<10; \
						p[cols]=0; \
					} \
					else { \
						c+=1<<10; \
					} \
					p[2*cols]=c; \
				} \
				else { \
					l3=0; \
					p[cols]=0; \
				} \
			} \
			if (l3>0x7fff) l3=0x7fff; else if (l3<-0x8000) l3=-0x8000; \
			p[0]=(short)l3; \
			l2=p[cols3+1]; \
			v+=l2; \
			if (v>0x7fff) v=0x7fff; else if (v<-0x8000) v=-0x8000; \
			p[4*cols]=(short)v; \
			p++; \
		} while(p<pe)
	switch(xdwOptViscosity) {
		case 1: XDWOCO0(511,10); break;
		case 2: XDWOCO0(255, 9); break;
		case 3: XDWOCO0(127, 8); break;
		case 4: XDWOCO0( 63, 7); break;
		case 5: XDWOCO0( 31, 6); break;
	}
}


static Bool xdwOperateCellsOpt1(short * cells, int count)
{
#if defined(XDW_MAX_OPTIMIZATION) && XDW_MAX_OPTIMIZATION < 1

	return False;

#elif defined(__GNUC__) && defined(__i386__)

	/* Optimization level 1 of the cellular automata using the MMX instruction
	   set of a 32-bit x86 CPU, implemented as GNU-C inline assembler. It is
	   assumed that the covering of a cell is not greater than 255 (it can be up
	   to 1023 per definition). If it's greater, the algorithm is still correct
	   but takes some extra time. */

	static Bool reported=False;
	int i;

	if (xdwCPUHasMMX) {
		if (!reported) {
			if (xdwOptVerb>=1) printf("Using MMX instruction set of 32-bit x86 CPU\n");
			reported=True;
		}
		i=(((short*)0)-cells)&3;
		if (i) {
			xdwOperateCellsOpt0(cells,i);
			cells+=i;
			count-=i;
		}
#		define XDWOCO1(L,C1,C2) \
			asm volatile ( \
			"  pushl %%ebp                         \n" \
			"  pushl %%edx                         \n" \
			"  pushl %%edi                         \n" \
			"  subl $200,%%esp                     \n" \
			"  fnsave (%%esp)                      \n" \
			"  movl %%edx,%%ebp                    \n" \
			"  pcmpeqw %%mm7,%%mm7                 \n" \
			"  psrlw $" #C1 ",%%mm7                \n" \
			"  movq (%%edi,%%ecx),%%mm6            \n" \
			"  movzwl -2(%%edi,%%ecx),%%eax        \n" \
			"  movd %%eax,%%mm5                    \n" \
			"  movq %%mm6,%%mm0                    \n" \
			"  psllq $16,%%mm0                     \n" \
			"  paddsw %%mm0,%%mm5                  \n" \
			"  psubsw %%mm6,%%mm5                  \n" \
			"  jmp " #L "3                         \n" \
			"  .balign 16                          \n" \
			#L "1:                                 \n" \
			"  pxor %%mm4,%%mm4                    \n" \
			"  movq %%mm4,(%%edi,%%ebx)            \n" \
			#L "2:                                 \n" \
			"  psubsw %%mm2,%%mm3                  \n" \
			"  movq %%mm4,(%%edi)                  \n" \
			"  movq %%mm3,(%%edi,%%ebx,4)          \n" \
			"  addl $8,%%edi                       \n" \
			#L "3:                                 \n" \
			"  cmpl %%esi,%%edi                    \n" \
			"  jnc " #L "9                         \n" \
			"  movq (%%edi,%%ebx,4),%%mm3          \n" \
			"  pxor %%mm2,%%mm2                    \n" \
			"  pcmpeqb (%%edi,%%ebx,2),%%mm2       \n" \
			"  movq %%mm3,%%mm1                    \n" \
			"  paddsw %%mm5,%%mm3                  \n" \
			"  paddsw %%mm7,%%mm1                  \n" \
			"  movq (%%edi),%%mm4                  \n" \
			"  psrlq $16,%%mm5                     \n" \
			"  psllw $1,%%mm2                      \n" \
			"  psubsw %%mm5,%%mm3                  \n" \
			"  packsswb %%mm2,%%mm2                \n" \
			"  movq (%%edi,%%ecx,2),%%mm0          \n" \
			"  psraw $" #C2 ",%%mm1                \n" \
			"  movq %%mm6,%%mm5                    \n" \
			"  movd %%mm2,%%eax                    \n" \
			"  psubsw %%mm1,%%mm3                  \n" \
			"  psubsw %%mm4,%%mm6                  \n" \
			"  movq (%%edi,%%ebx),%%mm1            \n" \
			"  psubsw %%mm6,%%mm3                  \n" \
			"  psubsw %%mm5,%%mm0                  \n" \
			"  movq 8(%%edi,%%ecx),%%mm6           \n" \
			"  paddsw %%mm0,%%mm3                  \n" \
			"  psrlq $48,%%mm5                     \n" \
			"  movq %%mm6,%%mm0                    \n" \
			"  psraw $2,%%mm1                      \n" \
			"  psllq $16,%%mm0                     \n" \
			"  psubsw %%mm6,%%mm5                  \n" \
			"  paddsw %%mm1,%%mm4                  \n" \
			"  movq %%mm5,%%mm2                    \n" \
			"  cmpl $0xfefefefe,%%eax              \n" \
			"  psllq $48,%%mm2                     \n" \
			"  paddsw %%mm0,%%mm5                  \n" \
			"  je " #L "2                          \n" \
			"  cmpl $0x80808080,%%eax              \n" \
			"  je " #L "1                          \n" \
			"  pcmpeqd %%mm1,%%mm1                 \n" \
			"  psrlq $48,%%mm1                     \n" \
			"  movl $4,%%edx                       \n" \
			#L "4:                                 \n" \
			"  movzwl (%%edi,%%ebx,2),%%eax        \n" \
			"  testl %%eax,%%eax                   \n" \
			"  je " #L "8                          \n" \
			"  testl $0x0000fc00,%%eax             \n" \
			"  je " #L "6                          \n" \
			"  shrl $10,%%eax                      \n" \
			"  addl $32,%%eax                      \n" \
			"  andl $63,%%eax                      \n" \
			"  movd (%%ebp,%%eax,4),%%mm0          \n" \
			"  punpcklwd %%mm0,%%mm0               \n" \
			"  punpckldq %%mm0,%%mm0               \n" \
			"  pand %%mm1,%%mm0                    \n" \
			"  paddsw %%mm0,%%mm4                  \n" \
			"  testl $32,%%eax                     \n" \
			"  jne " #L "5                         \n" \
			"  addw $0x0400,(%%edi,%%ebx,2)        \n" \
			"  jmp " #L "8                         \n" \
			#L "5:                                 \n" \
			"  subw $0x0400,(%%edi,%%ebx,2)        \n" \
			"  jmp " #L "7                         \n" \
			#L "6:                                 \n" \
			"  movq %%mm1,%%mm0                    \n" \
			"  pandn %%mm4,%%mm0                   \n" \
			"  movq %%mm0,%%mm4                    \n" \
			#L "7:                                 \n" \
			"  movw $0,(%%edi,%%ebx)               \n" \
			#L "8:                                 \n" \
			"  psllq $16,%%mm1                     \n" \
			"  addl $2,%%edi                       \n" \
			"  decl %%edx                          \n" \
			"  jnz " #L "4                         \n" \
			"  subl $8,%%edi                       \n" \
			"  jmp " #L "2                         \n" \
			#L "9:                                 \n" \
			"  frstor (%%esp)                      \n" \
			"  addl $200,%%esp                     \n" \
			"  popl %%edi                          \n" \
			"  popl %%edx                          \n" \
			"  popl %%ebp                          \n" \
			: \
			: "D"(cells),"S"(cells+(count&~3)),"b"(2*xdwCellMemCols), \
			  "c"(3*2*xdwCellMemCols),"d"(xdwCellFadingTable) \
			: "eax","memory","cc" \
			)
		switch(xdwOptViscosity) {
			case 1: XDWOCO1(XDWOCO1_1_, 7,10); break;
			case 2: XDWOCO1(XDWOCO1_2_, 8, 9); break;
			case 3: XDWOCO1(XDWOCO1_3_, 9, 8); break;
			case 4: XDWOCO1(XDWOCO1_4_,10, 7); break;
			case 5: XDWOCO1(XDWOCO1_5_,11, 6); break;
		}
		i=count&3;
		if (i) xdwOperateCellsOpt0(cells+count-i,i);
		return True;
	}

#elif defined(__GNUC__) && defined(__x86_64__)

	/* Same as above, but for 64-bit x86 CPU. (Are there any 64-bit CPU's or
	   assemblers supporting MMX but not SSE2? Probably no, but to be
	   complete...) */

	static Bool reported=False;
	int i;

	if (xdwCPUHasMMX) {
		if (!reported) {
			if (xdwOptVerb>=1) printf("Using MMX instruction set of 64-bit x86 CPU\n");
			reported=True;
		}
		i=(((short*)0)-cells)&3;
		if (i) {
			xdwOperateCellsOpt0(cells,i);
			cells+=i;
			count-=i;
		}
#		define XDWOCO1(L,C1,C2) \
			asm volatile ( \
			"  pushq %%rdi                         \n" \
			"  subq $200,%%rsp                     \n" \
			"  fnsave (%%rsp)                      \n" \
			"  pcmpeqw %%mm7,%%mm7                 \n" \
			"  psrlw $" #C1 ",%%mm7                \n" \
			"  movq (%%rdi,%%rcx),%%mm6            \n" \
			"  movzwl -2(%%rdi,%%rcx),%%eax        \n" \
			"  movd %%eax,%%mm5                    \n" \
			"  movq %%mm6,%%mm0                    \n" \
			"  psllq $16,%%mm0                     \n" \
			"  paddsw %%mm0,%%mm5                  \n" \
			"  psubsw %%mm6,%%mm5                  \n" \
			"  jmp " #L "3                         \n" \
			"  .balign 16                          \n" \
			#L "1:                                 \n" \
			"  pxor %%mm4,%%mm4                    \n" \
			"  movq %%mm4,(%%rdi,%%rbx)            \n" \
			#L "2:                                 \n" \
			"  psubsw %%mm2,%%mm3                  \n" \
			"  movq %%mm4,(%%rdi)                  \n" \
			"  movq %%mm3,(%%rdi,%%rbx,4)          \n" \
			"  addq $8,%%rdi                       \n" \
			#L "3:                                 \n" \
			"  cmpq %%rsi,%%rdi                    \n" \
			"  jnc " #L "9                         \n" \
			"  movq (%%rdi,%%rbx,4),%%mm3          \n" \
			"  pxor %%mm2,%%mm2                    \n" \
			"  pcmpeqb (%%rdi,%%rbx,2),%%mm2       \n" \
			"  movq %%mm3,%%mm1                    \n" \
			"  paddsw %%mm5,%%mm3                  \n" \
			"  paddsw %%mm7,%%mm1                  \n" \
			"  movq (%%rdi),%%mm4                  \n" \
			"  psrlq $16,%%mm5                     \n" \
			"  psllw $1,%%mm2                      \n" \
			"  psubsw %%mm5,%%mm3                  \n" \
			"  packsswb %%mm2,%%mm2                \n" \
			"  movq (%%rdi,%%rcx,2),%%mm0          \n" \
			"  psraw $" #C2 ",%%mm1                \n" \
			"  movq %%mm6,%%mm5                    \n" \
			"  movd %%mm2,%%eax                    \n" \
			"  psubsw %%mm1,%%mm3                  \n" \
			"  psubsw %%mm4,%%mm6                  \n" \
			"  movq (%%rdi,%%rbx),%%mm1            \n" \
			"  psubsw %%mm6,%%mm3                  \n" \
			"  psubsw %%mm5,%%mm0                  \n" \
			"  movq 8(%%rdi,%%rcx),%%mm6           \n" \
			"  paddsw %%mm0,%%mm3                  \n" \
			"  psrlq $48,%%mm5                     \n" \
			"  movq %%mm6,%%mm0                    \n" \
			"  psraw $2,%%mm1                      \n" \
			"  psllq $16,%%mm0                     \n" \
			"  psubsw %%mm6,%%mm5                  \n" \
			"  paddsw %%mm1,%%mm4                  \n" \
			"  movq %%mm5,%%mm2                    \n" \
			"  cmpl $0xfefefefe,%%eax              \n" \
			"  psllq $48,%%mm2                     \n" \
			"  paddsw %%mm0,%%mm5                  \n" \
			"  je " #L "2                          \n" \
			"  cmpl $0x80808080,%%eax              \n" \
			"  je " #L "1                          \n" \
			"  pcmpeqd %%mm1,%%mm1                 \n" \
			"  psrlq $48,%%mm1                     \n" \
			"  movl $4,%%r8d                       \n" \
			#L "4:                                 \n" \
			"  movzwl (%%rdi,%%rbx,2),%%eax        \n" \
			"  testl %%eax,%%eax                   \n" \
			"  je " #L "8                          \n" \
			"  testl $0x0000fc00,%%eax             \n" \
			"  je " #L "6                          \n" \
			"  shrl $10,%%eax                      \n" \
			"  addl $32,%%eax                      \n" \
			"  andq $63,%%rax                      \n" \
			"  movd (%%rdx,%%rax,4),%%mm0          \n" \
			"  punpcklwd %%mm0,%%mm0               \n" \
			"  punpckldq %%mm0,%%mm0               \n" \
			"  pand %%mm1,%%mm0                    \n" \
			"  paddsw %%mm0,%%mm4                  \n" \
			"  testl $32,%%eax                     \n" \
			"  jne " #L "5                         \n" \
			"  addw $0x0400,(%%rdi,%%rbx,2)        \n" \
			"  jmp " #L "8                         \n" \
			#L "5:                                 \n" \
			"  subw $0x0400,(%%rdi,%%rbx,2)        \n" \
			"  jmp " #L "7                         \n" \
			#L "6:                                 \n" \
			"  movq %%mm1,%%mm0                    \n" \
			"  pandn %%mm4,%%mm0                   \n" \
			"  movq %%mm0,%%mm4                    \n" \
			#L "7:                                 \n" \
			"  movw $0,(%%rdi,%%rbx)               \n" \
			#L "8:                                 \n" \
			"  psllq $16,%%mm1                     \n" \
			"  addq $2,%%rdi                       \n" \
			"  decl %%r8d                          \n" \
			"  jnz " #L "4                         \n" \
			"  subq $8,%%rdi                       \n" \
			"  jmp " #L "2                         \n" \
			#L "9:                                 \n" \
			"  frstor (%%rsp)                      \n" \
			"  addq $200,%%rsp                     \n" \
			"  popq %%rdi                          \n" \
			: \
			: "D"(cells),"S"(cells+(count&~3)),"b"((long)2*xdwCellMemCols), \
			  "c"((long)3*2*xdwCellMemCols),"d"(xdwCellFadingTable) \
			: "rax","r8","memory","cc" \
			)
		switch(xdwOptViscosity) {
			case 1: XDWOCO1(XDWOCO1_1_, 7,10); break;
			case 2: XDWOCO1(XDWOCO1_2_, 8, 9); break;
			case 3: XDWOCO1(XDWOCO1_3_, 9, 8); break;
			case 4: XDWOCO1(XDWOCO1_4_,10, 7); break;
			case 5: XDWOCO1(XDWOCO1_5_,11, 6); break;
		}
		i=count&3;
		if (i) xdwOperateCellsOpt0(cells+count-i,i);
		return True;
	}
#endif
	return False;
}


static Bool xdwOperateCellsOpt2(short * cells, int count)
{
#if defined(XDW_MAX_OPTIMIZATION) && XDW_MAX_OPTIMIZATION < 2
	return False;
#elif defined(__GNUC__) && defined(__i386__)

	/* Optimization level 2 of the cellular automata using the SSE2 instruction
	   set of a 32-bit x86 CPU, implemented as GNU-C inline assembler. It is
	   assumed that the covering of a cell is not greater than 255 (it can be up
	   to 1023 per definition). If it's greater, the algorithm is still correct
	   but takes some extra time. */

	static Bool reported=False;
	int i;

	if (xdwCPUHasFXSR && xdwCPUHasSSE2) {
		if (!reported) {
			if (xdwOptVerb>=1) printf("Using SSE2 instruction set of 32-bit x86 CPU\n");
			reported=True;
		}
		i=(((short*)0)-cells)&7;
		if (i) {
			xdwOperateCellsOpt0(cells,i);
			cells+=i;
			count-=i;
		}
#		define XDWOCO2(L,C1,C2) \
			asm volatile ( \
			"  pushl %%ebp                         \n" \
			"  pushl %%edx                         \n" \
			"  pushl %%edi                         \n" \
			"  movl %%esp,%%eax                    \n" \
			"  subl $512,%%esp                     \n" \
			"  andl $0xfffffff0,%%esp              \n" \
			"  fxsave (%%esp)                      \n" \
			"  push %%eax                          \n" \
			"  movl %%edx,%%ebp                    \n" \
			"  pcmpeqw %%xmm7,%%xmm7               \n" \
			"  psrlw $" #C1 ",%%xmm7               \n" \
			"  movdqa (%%edi,%%ecx),%%xmm6         \n" \
			"  movzwl -2(%%edi,%%ecx),%%eax        \n" \
			"  movd %%eax,%%xmm5                   \n" \
			"  movdqa %%xmm6,%%xmm0                \n" \
			"  pslldq $16/8,%%xmm0                 \n" \
			"  paddsw %%xmm0,%%xmm5                \n" \
			"  psubsw %%xmm6,%%xmm5                \n" \
			"  jmp " #L "3                         \n" \
			"  .balign 16                          \n" \
			#L "1:                                 \n" \
			"  pxor %%xmm4,%%xmm4                  \n" \
			"  movdqa %%xmm4,(%%edi,%%ebx)         \n" \
			#L "2:                                 \n" \
			"  psubsw %%xmm2,%%xmm3                \n" \
			"  movdqa %%xmm4,(%%edi)               \n" \
			"  movdqa %%xmm3,(%%edi,%%ebx,4)       \n" \
			"  addl $16,%%edi                      \n" \
			#L "3:                                 \n" \
			"  cmpl %%esi,%%edi                    \n" \
			"  jnc " #L "9                         \n" \
			"  movdqa (%%edi,%%ebx,4),%%xmm3       \n" \
			"  pxor %%xmm2,%%xmm2                  \n" \
			"  movdqa %%xmm3,%%xmm1                \n" \
			"  pcmpeqb (%%edi,%%ebx,2),%%xmm2      \n" \
			"  paddsw %%xmm5,%%xmm3                \n" \
			"  paddsw %%xmm7,%%xmm1                \n" \
			"  movdqa (%%edi),%%xmm4               \n" \
			"  psrldq $16/8,%%xmm5                 \n" \
			"  movdqa (%%edi,%%ecx,2),%%xmm0       \n" \
			"  psubsw %%xmm5,%%xmm3                \n" \
			"  psraw $" #C2 ",%%xmm1               \n" \
			"  movdqa %%xmm6,%%xmm5                \n" \
			"  psubsw %%xmm1,%%xmm3                \n" \
			"  psubsw %%xmm4,%%xmm6                \n" \
			"  movdqa (%%edi,%%ebx),%%xmm1         \n" \
			"  psubsw %%xmm6,%%xmm3                \n" \
			"  pmovmskb %%xmm2,%%eax               \n" \
			"  psubsw %%xmm5,%%xmm0                \n" \
			"  movdqa 16(%%edi,%%ecx),%%xmm6       \n" \
			"  paddsw %%xmm0,%%xmm3                \n" \
			"  psrldq $112/8,%%xmm5                \n" \
			"  movdqa %%xmm6,%%xmm0                \n" \
			"  psraw $2,%%xmm1                     \n" \
			"  pslldq $16/8,%%xmm0                 \n" \
			"  psubsw %%xmm6,%%xmm5                \n" \
			"  paddsw %%xmm1,%%xmm4                \n" \
			"  movdqa %%xmm5,%%xmm2                \n" \
			"  cmpl $0x0000ffff,%%eax              \n" \
			"  pslldq $112/8,%%xmm2                \n" \
			"  paddsw %%xmm0,%%xmm5                \n" \
			"  je " #L "2                          \n" \
			"  cmpl $0x0000aaaa,%%eax              \n" \
			"  je " #L "1                          \n" \
			"  pcmpeqd %%xmm1,%%xmm1               \n" \
			"  psrldq $112/8,%%xmm1                \n" \
			"  movl $8,%%edx                       \n" \
			#L "4:                                 \n" \
			"  movzwl (%%edi,%%ebx,2),%%eax        \n" \
			"  testl %%eax,%%eax                   \n" \
			"  je " #L "8                          \n" \
			"  testl $0x0000fc00,%%eax             \n" \
			"  je " #L "6                          \n" \
			"  shrl $10,%%eax                      \n" \
			"  addl $32,%%eax                      \n" \
			"  andl $63,%%eax                      \n" \
			"  movd (%%ebp,%%eax,4),%%xmm0         \n" \
			"  pshuflw $0,%%xmm0,%%xmm0            \n" \
			"  pshufd $0,%%xmm0,%%xmm0             \n" \
			"  pand %%xmm1,%%xmm0                  \n" \
			"  paddsw %%xmm0,%%xmm4                \n" \
			"  testl $32,%%eax                     \n" \
			"  jne " #L "5                         \n" \
			"  addw $0x0400,(%%edi,%%ebx,2)        \n" \
			"  jmp " #L "8                         \n" \
			#L "5:                                 \n" \
			"  subw $0x0400,(%%edi,%%ebx,2)        \n" \
			"  jmp " #L "7                         \n" \
			#L "6:                                 \n" \
			"  movdqa %%xmm1,%%xmm0                \n" \
			"  pandn %%xmm4,%%xmm0                 \n" \
			"  movdqa %%xmm0,%%xmm4                \n" \
			#L "7:                                 \n" \
			"  movw $0,(%%edi,%%ebx)               \n" \
			#L "8:                                 \n" \
			"  pslldq $16/8,%%xmm1                 \n" \
			"  addl $2,%%edi                       \n" \
			"  decl %%edx                          \n" \
			"  jnz " #L "4                         \n" \
			"  subl $16,%%edi                      \n" \
			"  jmp " #L "2                         \n" \
			#L "9:                                 \n" \
			"  popl %%eax                          \n" \
			"  fxrstor (%%esp)                     \n" \
			"  movl %%eax,%%esp                    \n" \
			"  popl %%edi                          \n" \
			"  popl %%edx                          \n" \
			"  popl %%ebp                          \n" \
			: \
			: "D"(cells),"S"(cells+(count&~7)),"b"(2*xdwCellMemCols), \
			  "c"(3*2*xdwCellMemCols),"d"(xdwCellFadingTable) \
			: "eax","memory","cc" \
			)
		switch(xdwOptViscosity) {
			case 1: XDWOCO2(XDWOCO2_1_, 7,10); break;
			case 2: XDWOCO2(XDWOCO2_2_, 8, 9); break;
			case 3: XDWOCO2(XDWOCO2_3_, 9, 8); break;
			case 4: XDWOCO2(XDWOCO2_4_,10, 7); break;
			case 5: XDWOCO2(XDWOCO2_5_,11, 6); break;
		}
		i=count&7;
		if (i) xdwOperateCellsOpt0(cells+count-i,i);
		return True;
	}

#elif defined(__GNUC__) && defined(__x86_64__)

	/* Same as above, but for 64-bit x86 CPU.
	   TODO: This is still just a slightly modified "copy" of the 32-bit mode
	   implementation. Surely it could be improved a little bit, by making use
	   of the additional registers xmm8-xmm15. */

	static Bool reported=False;
	int i;

	if (xdwCPUHasFXSR && xdwCPUHasSSE2) {
		if (!reported) {
			if (xdwOptVerb>=1) printf("Using SSE2 instruction set of 64-bit x86 CPU\n");
			reported=True;
		}
		i=(((short*)0)-cells)&7;
		if (i) {
			xdwOperateCellsOpt0(cells,i);
			cells+=i;
			count-=i;
		}
#		define XDWOCO2(L,C1,C2) \
			asm volatile ( \
			"  pushq %%rdi                         \n" \
			"  movq %%rsp,%%rax                    \n" \
			"  subq $512,%%rsp                     \n" \
			"  andq $-16,%%rsp                     \n" \
			"  fxsave (%%rsp)                      \n" \
			"  pushq %%rax                         \n" \
			"  pcmpeqw %%xmm7,%%xmm7               \n" \
			"  psrlw $" #C1 ",%%xmm7               \n" \
			"  movdqa (%%rdi,%%rcx),%%xmm6         \n" \
			"  movzwl -2(%%rdi,%%rcx),%%eax        \n" \
			"  movd %%eax,%%xmm5                   \n" \
			"  movdqa %%xmm6,%%xmm0                \n" \
			"  pslldq $16/8,%%xmm0                 \n" \
			"  paddsw %%xmm0,%%xmm5                \n" \
			"  psubsw %%xmm6,%%xmm5                \n" \
			"  jmp " #L "3                         \n" \
			"  .balign 16                          \n" \
			#L "1:                                 \n" \
			"  pxor %%xmm4,%%xmm4                  \n" \
			"  movdqa %%xmm4,(%%rdi,%%rbx)         \n" \
			#L "2:                                 \n" \
			"  psubsw %%xmm2,%%xmm3                \n" \
			"  movdqa %%xmm4,(%%rdi)               \n" \
			"  movdqa %%xmm3,(%%rdi,%%rbx,4)       \n" \
			"  addq $16,%%rdi                      \n" \
			#L "3:                                 \n" \
			"  cmpq %%rsi,%%rdi                    \n" \
			"  jnc " #L "9                         \n" \
			"  movdqa (%%rdi,%%rbx,4),%%xmm3       \n" \
			"  pxor %%xmm2,%%xmm2                  \n" \
			"  movdqa %%xmm3,%%xmm1                \n" \
			"  pcmpeqb (%%rdi,%%rbx,2),%%xmm2      \n" \
			"  paddsw %%xmm5,%%xmm3                \n" \
			"  paddsw %%xmm7,%%xmm1                \n" \
			"  movdqa (%%rdi),%%xmm4               \n" \
			"  psrldq $16/8,%%xmm5                 \n" \
			"  movdqa (%%rdi,%%rcx,2),%%xmm0       \n" \
			"  psubsw %%xmm5,%%xmm3                \n" \
			"  psraw $" #C2 ",%%xmm1               \n" \
			"  movdqa %%xmm6,%%xmm5                \n" \
			"  psubsw %%xmm1,%%xmm3                \n" \
			"  psubsw %%xmm4,%%xmm6                \n" \
			"  movdqa (%%rdi,%%rbx),%%xmm1         \n" \
			"  psubsw %%xmm6,%%xmm3                \n" \
			"  pmovmskb %%xmm2,%%eax               \n" \
			"  psubsw %%xmm5,%%xmm0                \n" \
			"  movdqa 16(%%rdi,%%rcx),%%xmm6       \n" \
			"  paddsw %%xmm0,%%xmm3                \n" \
			"  psrldq $112/8,%%xmm5                \n" \
			"  movdqa %%xmm6,%%xmm0                \n" \
			"  psraw $2,%%xmm1                     \n" \
			"  pslldq $16/8,%%xmm0                 \n" \
			"  psubsw %%xmm6,%%xmm5                \n" \
			"  paddsw %%xmm1,%%xmm4                \n" \
			"  movdqa %%xmm5,%%xmm2                \n" \
			"  cmpl $0x0000ffff,%%eax              \n" \
			"  pslldq $112/8,%%xmm2                \n" \
			"  paddsw %%xmm0,%%xmm5                \n" \
			"  je " #L "2                          \n" \
			"  cmpl $0x0000aaaa,%%eax              \n" \
			"  je " #L "1                          \n" \
			"  pcmpeqd %%xmm1,%%xmm1               \n" \
			"  psrldq $112/8,%%xmm1                \n" \
			"  movl $8,%%r8d                       \n" \
			#L "4:                                 \n" \
			"  movzwl (%%rdi,%%rbx,2),%%eax        \n" \
			"  testl %%eax,%%eax                   \n" \
			"  je " #L "8                          \n" \
			"  testl $0x0000fc00,%%eax             \n" \
			"  je " #L "6                          \n" \
			"  shrl $10,%%eax                      \n" \
			"  addl $32,%%eax                      \n" \
			"  andq $63,%%rax                      \n" \
			"  movd (%%rdx,%%rax,4),%%xmm0         \n" \
			"  pshuflw $0,%%xmm0,%%xmm0            \n" \
			"  pshufd $0,%%xmm0,%%xmm0             \n" \
			"  pand %%xmm1,%%xmm0                  \n" \
			"  paddsw %%xmm0,%%xmm4                \n" \
			"  testl $32,%%eax                     \n" \
			"  jne " #L "5                         \n" \
			"  addw $0x0400,(%%rdi,%%rbx,2)        \n" \
			"  jmp " #L "8                         \n" \
			#L "5:                                 \n" \
			"  subw $0x0400,(%%rdi,%%rbx,2)        \n" \
			"  jmp " #L "7                         \n" \
			#L "6:                                 \n" \
			"  movdqa %%xmm1,%%xmm0                \n" \
			"  pandn %%xmm4,%%xmm0                 \n" \
			"  movdqa %%xmm0,%%xmm4                \n" \
			#L "7:                                 \n" \
			"  movw $0,(%%rdi,%%rbx)               \n" \
			#L "8:                                 \n" \
			"  pslldq $16/8,%%xmm1                 \n" \
			"  addq $2,%%rdi                       \n" \
			"  decl %%r8d                          \n" \
			"  jnz " #L "4                         \n" \
			"  subq $16,%%rdi                      \n" \
			"  jmp " #L "2                         \n" \
			#L "9:                                 \n" \
			"  popq %%rax                          \n" \
			"  fxrstor (%%rsp)                     \n" \
			"  movq %%rax,%%rsp                    \n" \
			"  popq %%rdi                          \n" \
			: \
			: "D"(cells),"S"(cells+(count&~7)),"b"((long)2*xdwCellMemCols), \
			  "c"((long)3*2*xdwCellMemCols),"d"(xdwCellFadingTable) \
			: "rax","r8","memory","cc" \
			)
		switch(xdwOptViscosity) {
			case 1: XDWOCO2(XDWOCO2_1_, 7,10); break;
			case 2: XDWOCO2(XDWOCO2_2_, 8, 9); break;
			case 3: XDWOCO2(XDWOCO2_3_, 9, 8); break;
			case 4: XDWOCO2(XDWOCO2_4_,10, 7); break;
			case 5: XDWOCO2(XDWOCO2_5_,11, 6); break;
		}
		i=count&7;
		if (i) xdwOperateCellsOpt0(cells+count-i,i);
		return True;
	}
#endif
	return False;
}


static void xdwUpdateCells(int timeSlices)
{
	short * p;
	int i, n, t, r, c;

	/* For all time slices of one frame, push forward the cellular automata
	   at all cells. Don't forget storm. After a row r has been operated for
	   one time slice, row r-2 can be operated for the next time slice.
	   That's good for cache utilization. */
	n=xdwCellRows-2+(timeSlices-1)*2;
	for (i=0; i<n; i++) {
		for (t=0; t<timeSlices; t++) {
			r=i-2*t;
			if (r>=0 && r<xdwCellRows-2) {
				p=xdwCells+r*3*xdwCellMemCols+1;
				c=xdwCellCols-2;
				switch (xdwOptMaxOptimization) {
					default: if (xdwOperateCellsOpt2(p,c)) break;
					case  1: if (xdwOperateCellsOpt1(p,c)) break;
					case  0: xdwOperateCellsOpt0(p,c);
				}
				if (xdwOptStorm && r>0) xdwUpdateStromRow(r);
			}
		}
	}
}


/*============================================================================*/
/*================ Visualization (Canvas, Palette & Lighting =================*/
/*============================================================================*/

/* The "canvas" holds the resulting image of the water and it knows where the
   output window (or back buffer) is up-to-date. One pixel of the canvas is a
   rectangle of xdwOptResDivX * xdwOptResDivY pixels on the output window. The
   upper-left corner of the upper-left pixel of the canvas lies in the
   upper-left corner of the upper-left pixel of the output window. */

int xdwCanvasWidth, xdwCanvasHeight;
	/* Width and height of the canvas. xdwCanvasWidth must be n*xdwOptCellW+1
	   with an integral n, xdwCanvasHeight must be appropriate. */

int xdwCanvasVisibleW, xdwCanvasVisibleH;
	/* Size of the visible part of the canvas. This may be a little smaller
	   than the canvas size.*/

signed char * xdwCanvas;
	/* The canvas (array of pixels). Bits 0 to 6 are the color as a palette
	   index. Bit 7 means: output window (or back buffer) is not up-to-date
	   here. */

int xdwTouchedCvRow1, xdwTouchedCvRow2;
	/* Minimum range of canvas rows, where something is not up-to-date.
	   If everything is up-to-date, xdwTouchedCvRow1 must be >=xdwCanvasHeight,
	   and xdwTouchedCvRow2 must be <=0.
	   TODO: Even try to develop this kind of optimization for columns. */

typedef struct {
	int count;
	XRectangle rects[256];
} xdwRectSet;
xdwRectSet * * xdwRectSets;
	/* This array reserves some memory for using XFillRectangles.
	   xdwRectSets[i] is a set of rectangles to be drawn with color
	   xdwPalette[i]. */

int xdwSkyColorIndex;
	/* Index of sky color. */

int xdwColorCount;
	/* Number of colors in the palette. */

unsigned long * xdwPalette;
	/* The color palette. The entries are X pixel values. Water color is
	   at index 0, sky color is at index xdwSkyColorIndex, and light
	   color is at index xdwColorCount-1. Other entries are fadings
	   between those base colors. */

signed char * xdwLightingTable;
	/* Table for speeding up lighting. */


static void xdwInitPalette(Display * display)
{
	Colormap cmap;
	XColor ec[3];
	XColor c;
	int i, a, b, q, n;

	/* Allocate and fill the palette. */
	xdwColorCount=xdwOptMaxColors;
	xdwPalette=malloc(sizeof(unsigned long)*xdwColorCount);
	xdwSkyColorIndex=xdwColorCount*3/4;
	cmap=DefaultColormap(display,DefaultScreen(display));
	if (!XLookupColor(display,cmap,xdwOptWaterColor,&ec[0],&c)) {
		fprintf(stderr,"%s: no such color: %s\n",xdwArg0,xdwOptWaterColor);
		exit(1);
	}
	if (!XLookupColor(display,cmap,xdwOptSkyColor,&ec[1],&c)) {
		fprintf(stderr,"%s: no such color: %s\n",xdwArg0,xdwOptSkyColor);
		exit(1);
	}
	if (!XLookupColor(display,cmap,xdwOptLightColor,&ec[2],&c)) {
		fprintf(stderr,"%s: no such color: %s\n",xdwArg0,xdwOptLightColor);
		exit(1);
	}
	for (i=0; i<xdwColorCount; i++) {
		if (i<=xdwSkyColorIndex) {
			q=i;
			n=xdwSkyColorIndex;
			a=0;
			b=1;
		}
		else {
			q=i-xdwSkyColorIndex;
			n=xdwColorCount-1-xdwSkyColorIndex;
			a=1;
			b=2;
		}
		c.red  =(ec[a].red  *(n-q)+ec[b].red  *q+n/2)/n;
		c.green=(ec[a].green*(n-q)+ec[b].green*q+n/2)/n;
		c.blue =(ec[a].blue *(n-q)+ec[b].blue *q+n/2)/n;
		if (XAllocColor(display,cmap,&c)) {
			xdwPalette[i]=c.pixel;
		}
		else if (i*2<xdwColorCount) {
			xdwPalette[i]=BlackPixel(display,DefaultScreen(display));
		}
		else {
			xdwPalette[i]=WhitePixel(display,DefaultScreen(display));
		}
	}

	/* Remove duplicated colors from the palette. */
	for (i=1, n=1; i<xdwColorCount; i++) {
		if (xdwPalette[n-1]!=xdwPalette[i]) xdwPalette[n++]=xdwPalette[i];
		if (xdwSkyColorIndex==i) xdwSkyColorIndex=n-1;
	}
	xdwColorCount=n;
	if (xdwOptVerb>=1) {
		printf("Palette has %d different colors (from %d)\n",
		       xdwColorCount,xdwOptMaxColors);
	}
}


static void xdwInitLighting(void)
{
	double lx, ly, lz, nx, ny, nz, r, c, k;
	int i, j, d1, d2;

	/* Direction where the light is. */
	r=cos(xdwOptLightAltitude*(M_PI/180.0));
	lx=r*sin(xdwOptLightAzimuth*(M_PI/180.0));
	ly=-r*cos(xdwOptLightAzimuth*(M_PI/180.0));
	lz=sin(xdwOptLightAltitude*(M_PI/180.0));

	/* Prepare a table for that xdwUpdateCanvas(..) can perform faster. */
	xdwLightingTable=malloc(sizeof(signed char)*0x40000);
	for (i=0; i<0x40000; i++) {

		/* Calculate norm vector of the water surface. */
		d1=i>>9;
		if (d1&0x100) d1|=~0xff;
		d2=i&0x1ff;
		if (d2&0x100) d2|=~0xff;
		nx=d1-d2;
		ny=d1+d2;
		nz=128.0;
		r=sqrt(nx*nx+ny*ny+nz*nz);
		nx/=r;
		ny/=r;
		nz/=r;

		/* Reflection of the sky. */
		k=xdwOptSkyIntensity*xdwOptSkyIntensity*(0.99-nz*nz)*0.2;
		if (k>1.0) k=1.0;
		if (k<0.0) k=0.0;
		c=k*xdwSkyColorIndex;

		/* Reflection of light source. */
		k=(nx*lx+ny*ly+nz*lz)*nz*2.0-lz;
		if (k>0.0) {
			k=(0.51+xdwOptLightIntensity*0.043-sqrt(1.0001-k*k))/0.47;
			if (k>0.0) {
				if (k>1.0) k=1.0;
				c+=k*k*(xdwColorCount-1);
			}
		}

		/* Saturate and set table entry. */
		j=(int)(c+0.5);
		if (j<0) j=0; else if (j>=xdwColorCount) j=xdwColorCount-1;
		xdwLightingTable[i]=j;
	}
}


static void xdwInitCanvas(int windowWidth, int windowHeight)
{
	int i;

	/* Calculate sizes. */
	xdwCanvasVisibleW=(windowWidth-1)/xdwOptResDivX+1;
	xdwCanvasVisibleH=(windowHeight-1)/xdwOptResDivY+1;
	xdwCanvasWidth=((xdwCanvasVisibleW-2)/xdwOptCellW+1)*xdwOptCellW+1;
	xdwCanvasHeight=((xdwCanvasVisibleH-2)/xdwOptCellH+1)*xdwOptCellH+1;

	/* Allocate the array of pixels, and mark all pixels as out-of-date. */
	xdwCanvas=malloc(sizeof(signed char)*xdwCanvasWidth*xdwCanvasHeight);
	memset(xdwCanvas,0x80,xdwCanvasWidth*xdwCanvasHeight);

	/* Allocate and initialize memory for sets of rectangles. */
	xdwRectSets=malloc(sizeof(xdwRectSet)*xdwColorCount);
	for (i=0; i<xdwColorCount; i++) {
		xdwRectSets[i]=malloc(sizeof(xdwRectSet));
		xdwRectSets[i]->count=0;
	}

	/* Nothing is up-to-date. */
	xdwTouchedCvRow1=0;
	xdwTouchedCvRow2=xdwCanvasHeight;
}


static Bool xdwTouchCanvas(int x1, int y1, int x2, int y2)
{
	signed char * p, * pe;

	/* Mark a rectangular region as out-of-date. The given coordinates
	   are in window pixels. */
	x1/=xdwOptResDivX;
	x2=(x2+xdwOptResDivX-1)/xdwOptResDivX;
	if (x1<0) x1=0;
	if (x2>xdwCanvasVisibleW) x2=xdwCanvasVisibleW;
	if (x1>=x2) return False;
	y1/=xdwOptResDivY;
	y2=(y2+xdwOptResDivY-1)/xdwOptResDivY;
	if (y1<0) y1=0;
	if (y2>xdwCanvasVisibleH) y2=xdwCanvasVisibleH;
	if (y1>=y2) return False;
	if (xdwTouchedCvRow1>y1) xdwTouchedCvRow1=y1;
	if (xdwTouchedCvRow2<y2) xdwTouchedCvRow2=y2;
	do {
		p=xdwCanvas+y1*xdwCanvasWidth+x1;
		pe=p+(x2-x1);
		do {
			*p|=0x80;
			p++;
		} while (p<pe);
		y1++;
	} while (y1<y2);
	return True;
}


/* - - - - - - - - - Helper functions for xdwUpdateCanvas() - - - - - - - - - */

static Bool xdwCvDoLighting(int y)
{
	signed char * q, * qe;
	short * p;
	int cols3;
	signed char c;

	cols3=xdwCellMemCols*3;
	p=xdwCells+y/xdwOptCellH*cols3;
	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	do {
		c=xdwLightingTable[
			(((p[0]-p[cols3+1])&0x3fe0)<<4)+
			(((p[1]-p[cols3])&0x3fe0)>>5)
		];
		p++;
		if (*q!=c) break;
		q+=xdwOptCellW;
	} while(q<qe);
	if (q>=qe) return False;
	*q=c|0x80;
	q+=xdwOptCellW;
	if (q>=qe) return True;
	do {
		c=xdwLightingTable[
			(((p[0]-p[cols3+1])&0x3fe0)<<4)+
			(((p[1]-p[cols3])&0x3fe0)>>5)
		];
		p++;
		if (*q!=c) *q=c|0x80;
		q+=xdwOptCellW;
	} while(q<qe);
	return True;
}


static void xdwCvIterpolateVer2(int y)
{
	signed char * q, * qe;
	int c;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	do {
		c=((q[0]&0x7f)+(q[2*xdwCanvasWidth]&0x7f)+1)>>1;
		if (q[xdwCanvasWidth]!=c) q[xdwCanvasWidth]=c|0x80;
		q+=xdwOptCellW;
	} while(q<qe);
}


static void xdwCvIterpolateVer3(int y)
{
	signed char * q, * qe;
	int c1, c2;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	do {
		c1=q[0]&0x7f;
		c2=c1+(q[3*xdwCanvasWidth]&0x7f);
		c1=(c1+c2+1)/3;
		if (q[xdwCanvasWidth]!=c1) q[xdwCanvasWidth]=c1|0x80;
		c2-=c1;
		if (q[2*xdwCanvasWidth]!=c2) q[2*xdwCanvasWidth]=c2|0x80;
		q+=xdwOptCellW;
	} while(q<qe);
}


static void xdwCvIterpolateVer4(int y)
{
	signed char * q, * qe;
	int c, c1, c2;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	do {
		c1=q[0]&0x7f;
		c2=q[4*xdwCanvasWidth]&0x7f;
		c=(c1+c2+1)>>1;
		if (q[2*xdwCanvasWidth]!=c) q[2*xdwCanvasWidth]=c|0x80;
		c1=(c1+c+1)>>1;
		if (q[xdwCanvasWidth]!=c1) q[xdwCanvasWidth]=c1|0x80;
		c2=(c2+c+1)>>1;
		if (q[3*xdwCanvasWidth]!=c2) q[3*xdwCanvasWidth]=c2|0x80;
		q+=xdwOptCellW;
	} while(q<qe);
}


static void xdwCvIterpolateVerN(int y)
{
	signed char * q, * qe, * t;
	int c, c1, c2, i;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	do {
		c1=q[0]&0x7f;
		c2=(q[xdwOptCellH*xdwCanvasWidth]&0x7f)-c1;
		c1=xdwOptCellH*c1+(xdwOptCellH>>1);
		t=q+xdwCanvasWidth;
		for (i=1; i<xdwOptCellH; i++, t+=xdwCanvasWidth) {
			c1+=c2;
			c=c1/xdwOptCellH;
			if (*t!=c) *t=c|0x80;
		}
		q+=xdwOptCellW;
	} while(q<qe);
}


static void xdwCvIterpolateHor2(int y)
{
	signed char * q, * qe;
	int c, c2;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	c2=*q&0x7f;
	q++;
	do {
		c=c2;
		c2=q[1]&0x7f;
		c=(c+c2+1)>>1;
		if (*q!=c) *q=c|0x80;
		q+=2;
	} while(q<qe);
}


static void xdwCvIterpolateHor3(int y)
{
	signed char * q, * qe;
	int c, c1, c2;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	c2=*q&0x7f;
	q++;
	do {
		c=c2;
		c2=q[2]&0x7f;
		c1=c+c2;
		c=(c+c1+1)/3;
		if (*q!=c) *q=c|0x80;
		c1-=c;
		if (q[1]!=c1) q[1]=c1|0x80;
		q+=3;
	} while(q<qe);
}


static void xdwCvIterpolateHor4(int y)
{
	signed char * q, * qe;
	int c, c1, c2;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	c2=*q&0x7f;
	q++;
	do {
		c1=c2;
		c2=q[3]&0x7f;
		c=(c1+c2+1)>>1;
		c1=(c1+c+1)>>1;
		if (*q!=c1) *q=c1|0x80;
		if (q[1]!=c) q[1]=c|0x80;
		c=c+c-c1;
		if (q[2]!=c) q[2]=c|0x80;
		q+=4;
	} while(q<qe);
}


static void xdwCvIterpolateHorN(int y)
{
	signed char * q, * qe;
	int c, c1, c2, c3, i;

	q=xdwCanvas+y*xdwCanvasWidth;
	qe=q+xdwCanvasWidth;
	c2=*q&0x7f;
	do {
		c1=c2;
		c2=q[xdwOptCellW]&0x7f;
		c3=c2-c1;
		c1=xdwOptCellW*c1+(xdwOptCellW>>1);
		for (i=1; i<xdwOptCellW; i++) {
			c1+=c3; c=c1/xdwOptCellW;
			if (c!=q[i]) q[i]=c|0x80;
		}
		q+=xdwOptCellW;
	} while(q<qe);
}

/* - - - - - - - End of helper functions for xdwUpdateCanvas() - - - - - - - */


static void xdwUpdateCanvas(void)
{
	int y1, y2;
	Bool prvChanged, curChanged;

	/* Update the canvas by the cells. For each canvas pixel where the center
	   falls in a corner of a cell, the color is calculated by the levels of
	   the four adjacent cells (lighting). The other pixels are interpolated
	   bi-linear. Pixels which are up-to-date, are not touched if the color
	   does not change. The loop processes from bottom to top for a better
	   cache utilization with regard to the other algorithms. */
	curChanged=False;
	for (y1=xdwCanvasHeight-1, y2=xdwCanvasHeight; y1>=0; y1-=xdwOptCellH) {
		prvChanged=curChanged;
		curChanged=xdwCvDoLighting(y1);
		if (!prvChanged && !curChanged) continue;
		if (xdwTouchedCvRow1>y1) xdwTouchedCvRow1=y1;
		if (xdwTouchedCvRow2<y2) xdwTouchedCvRow2=y2;
		if (y1<xdwCanvasHeight-1) {
			switch (xdwOptCellH) {
				case  1: break;
				case  2: xdwCvIterpolateVer2(y1); break;
				case  3: xdwCvIterpolateVer3(y1); break;
				case  4: xdwCvIterpolateVer4(y1); break;
				default: xdwCvIterpolateVerN(y1); break;
			}
		}
		do {
			y2--;
			switch (xdwOptCellW) {
				case  1: break;
				case  2: xdwCvIterpolateHor2(y2); break;
				case  3: xdwCvIterpolateHor3(y2); break;
				case  4: xdwCvIterpolateHor4(y2); break;
				default: xdwCvIterpolateHorN(y2); break;
			}
		} while (y1<y2);
	}
}


static void xdwDrawCanvas(Display * display, Drawable drawable, GC gc,
                          int * pXFRCalls, int * pRects)
{
	xdwRectSet * rs;
	XRectangle * r;
	signed char * px, * pxe, * py, * pye, * pxy, * p;
	signed char c, c7;
	int y, sx, sy;

	/* Draw the canvas to the given drawable (window or back buffer).
	   Optimization strategies are:
	    - Do not paint rectangles which are up-to-date.
	    - Try to merge multiple adjacent rectangles of same color into
	      larger rectangles.
	    - Paint multiple rectangles of same color with one call to
	      XFillRectangles.
	   Besides the number of calls to XFillRectangles is counted, and even
	   the total number of painted rectangles.
	   Important: Even the invisible pixels have to be marked as up-to-date. */
	(*pXFRCalls)=0;
	(*pRects)=0;
	y=(xdwTouchedCvRow2<xdwCanvasVisibleH ? xdwTouchedCvRow2 : xdwCanvasVisibleH);
	pye=xdwCanvas+xdwCanvasWidth*y;
	for (y=xdwTouchedCvRow1; y<xdwTouchedCvRow2; y++) {
		px=xdwCanvas+y*xdwCanvasWidth;
		pxe=px+xdwCanvasVisibleW;
		sx=0;
		sy=y*xdwOptResDivY;
		if (y<xdwCanvasVisibleH) {
			do {
				do {
					if (*px<0) break;
					px++;
					sx+=xdwOptResDivX;
				} while (px<pxe);
				if (px>=pxe) break;
				c=*px;
				c7=c&0x7f;
				rs=xdwRectSets[c7];
				if (rs->count>=256) {
					(*pXFRCalls)++;
					(*pRects)+=rs->count;
					XSetForeground(display,gc,xdwPalette[c7]);
					XFillRectangles(display,drawable,gc,rs->rects,rs->count);
					rs->count=0;
				}
				r=rs->rects+rs->count;
				rs->count++;
				r->x=sx;
				r->y=sy;
				r->width=xdwOptResDivX;
				r->height=xdwOptResDivY;
				*px=c7;
				py=px+xdwCanvasWidth;
				px++;
				sx+=xdwOptResDivX;
				if (px<pxe && *px==c) {
					*px=c7;
					r->width+=xdwOptResDivX;
					sx+=xdwOptResDivX;
					px++;
					if (py<pye && *py==c && py[1]==c) {
						*py=c7;
						py[1]=c7;
						r->height+=xdwOptResDivY;
						py+=xdwCanvasWidth;
						pxy=py+2;
						for (;;) {
							p=px;
							if (p<pxe) {
								do {
									if (*p!=c) break;
									p+=xdwCanvasWidth;
								} while (p<pxy);
							}
							if (p<pxy) {
								while (py<pye) {
									p=py;
									do {
										if (*p!=c) break;
										p++;
									} while (p<pxy);
									if (p<pxy) break;
									p=py;
									do {
										*p=c7;
										p++;
									} while (p<pxy);
									py+=xdwCanvasWidth;
									pxy+=xdwCanvasWidth;
									r->height+=xdwOptResDivY;
								}
								break;
							}
							p=px;
							do {
								*p=c7;
								p+=xdwCanvasWidth;
							} while (p<pxy);
							px++;
							pxy++;
							r->width+=xdwOptResDivX;
							sx+=xdwOptResDivX;
							p=py;
							if (p<pye) {
								do {
									if (*p!=c) break;
									p++;
								} while (p<pxy);
							}
							if (p<pxy) {
								while (px<pxe) {
									p=px;
									do {
										if (*p!=c) break;
										p+=xdwCanvasWidth;
									} while (p<pxy);
									if (p<pxy) break;
									p=px;
									do {
										*p=c7;
										p+=xdwCanvasWidth;
									} while (p<pxy);
									px++;
									pxy++;
									r->width+=xdwOptResDivX;
									sx+=xdwOptResDivX;
								}
								break;
							}
							p=py;
							do {
								*p=c7;
								p++;
							} while (p<pxy);
							py+=xdwCanvasWidth;
							pxy+=xdwCanvasWidth;
							r->height+=xdwOptResDivY;
						}
					}
					else if (px<pxe && *px==c) {
						do {
							*px=c7;
							px++;
							sx+=xdwOptResDivX;
							r->width+=xdwOptResDivX;
						} while (px<pxe && *px==c);
					}
				}
				else if (py<pye && *py==c) {
					do {
						*py=c7;
						py+=xdwCanvasWidth;
						r->height+=xdwOptResDivY;
					} while (py<pye && *py==c);
				}
			} while(px<pxe);
		}
		pxe+=xdwCanvasWidth-xdwCanvasVisibleW;
		if (px<pxe) {
			do {
				if (*px<0) *px&=0x7f;
				px++;
			} while (px<pxe);
		}
	}
	for (c=xdwColorCount-1; c>=0; c--) if ((rs=xdwRectSets[c])->count) {
		(*pXFRCalls)++;
		(*pRects)+=rs->count;
		XSetForeground(display,gc,xdwPalette[c]);
		XFillRectangles(display,drawable,gc,rs->rects,rs->count);
		rs->count=0;
	}
	xdwTouchedCvRow1=xdwCanvasHeight;
	xdwTouchedCvRow2=0;
}


/*============================================================================*/
/*================================== Times ===================================*/
/*============================================================================*/

unsigned xdwAbsTimeMS=0;
	/* Time in milliseconds (starts somewhere an may overflow). */


unsigned xdwProcTimeMS=0;
	/* Process busy time in milliseconds (starts somewhere an may overflow). */


static void xdwUpdateTimes(void)
{
	static long tps=-1;
	static clock_t atcks=0, ptcks=0;
	clock_t d;
	struct tms tb;

	if (tps<=0) {
		tps=sysconf(_SC_CLK_TCK);
		if (tps<=0) {
			fprintf(stderr,"%s: sysconf(_SC_CLK_TCK) failed\n",xdwArg0);
			exit(1);
		}
	}
	d=times(&tb)-atcks;
	if (d) {
		atcks+=d;
		xdwAbsTimeMS+=(unsigned)(
			((unsigned long)d)/((unsigned long)tps)*1000+
			((unsigned long)d)%((unsigned long)tps)*1000/(unsigned long)tps
		);
	}
	d=tb.tms_utime+tb.tms_stime-ptcks;
	if (d) {
		ptcks+=d;
		xdwProcTimeMS+=(unsigned)(
			((unsigned long)d)/((unsigned long)tps)*1000+
			((unsigned long)d)%((unsigned long)tps)*1000/(unsigned long)tps
		);
	}
}


/*============================================================================*/
/*============================= Signal Handling ==============================*/
/*============================================================================*/

Bool xdwTerminationRequested=False;
	/* True if the program should terminate. */


Bool xdwFreeze=False;
	/* True if the program should freeze (just for making screenshots).
	   Toggled by SIGUSR1. */


static void xdwSignalHandler(int signum)
{
	/* Handle a signal... */
	if (signum==SIGUSR1) xdwFreeze=!xdwFreeze;
	else xdwTerminationRequested=True;
}


static void xdwInitSignalHandling(void)
{
	/* Install the signal handler. */
	signal(SIGHUP ,xdwSignalHandler);
	signal(SIGINT ,xdwSignalHandler);
	signal(SIGQUIT,xdwSignalHandler);
	signal(SIGABRT,xdwSignalHandler);
	signal(SIGTERM,xdwSignalHandler);
	signal(SIGUSR1,xdwSignalHandler);
}


/*============================================================================*/
/*============================= X Error Handling =============================*/
/*============================================================================*/

int xdwXErrorAcceptance=0;
	/* Non-zero if X errors should be accepted/ignored, instead of terminating
	   the program. */


int (*xdwOriginalXErrorHandler)(Display *, XErrorEvent *);
	/* Original X error handler. */


static int xdwXErrorHandler(Display * display, XErrorEvent * errorEvent)
{
	char msg[256];

	/* Own X error handler: fall back to the original handler, or accept the
	   error. */
	if (!xdwXErrorAcceptance) {
		return (*xdwOriginalXErrorHandler)(display,errorEvent);
	}
	if (xdwOptVerb>=2) {
		XGetErrorText(display,errorEvent->error_code,msg,sizeof(msg));
		printf("XError accepted: %s\n",msg);
	}
	return 0;
}


static void xdwInitXErrorHandling(void)
{
	/* Install X error handler. */
	xdwOriginalXErrorHandler=XSetErrorHandler(xdwXErrorHandler);
}


static void xdwBeginAcceptXErrors(void)
{
	/* Increase nesting of accepting X errors. */
	xdwXErrorAcceptance++;
}


static void xdwEndAcceptXErrors(void)
{
	/* Decrease nesting of accepting X errors. */
	xdwXErrorAcceptance--;
}


/*============================================================================*/
/*==================== Detection of Virtual Root Window ======================*/
/*============================================================================*/

static Window xdwDetectVirtualRoot(Display * display, Window * pAboveWin,
                                   Bool * pIsNautilus)
{
	XWindowAttributes attr;
	Window rwin, win, win2, win3, win4, win5;
	Window * cwins, * cwins2, * cwins3;
	Atom atom,type;
	int i, j, k, l, m, n, r, rwidth, rheight, frmt;
	unsigned long len, rem;
	unsigned char * data;
	char * str;

	/* This code tries to find a virtual root window created by the window
	   manager. It's a horrible topic. I stole some ideas from Andreas
	   Stolcke's vroot.h, and some from Robin Hogan's toon_root.c (xpenguins). */

	/* Prepare some variables. */
	*pAboveWin=None;
	*pIsNautilus=False;
	rwin=DefaultRootWindow(display);
	rwidth=DisplayWidth(display,DefaultScreen(display));
	rheight=DisplayHeight(display,DefaultScreen(display));

	/* The good(?) old standard(?): Maybe there is a child-of-root window
	   which has a property named __SWM_VROOT, pointing to the virtual root
	   window. This even works with KDE if "Allow Programs in Desktop Window"
	   has been enabled in the desktop configuration. */
	atom=XInternAtom(display,"__SWM_VROOT",False);
	XQueryTree(display,rwin,&win,&win2,&cwins,(unsigned*)&n);
	for (win=None, i=0; i<n; i++) {
		data=NULL;
		r=XGetWindowProperty(display,cwins[i],atom,0,1,False,XA_WINDOW,
		                     &type,&frmt,&len,&rem,&data);
		if (r==Success && type==XA_WINDOW && data) win=*(Window*)data;
		if (data) XFree(data);
	}
	if (cwins) XFree(cwins);
	if (win) {
		if (xdwOptVerb>=1) printf("Virtual Root detected: 0x%lX\n",win);
		return win;
	}

	/* Nautilus has a root window property pointing to the desktop window.
	   But we have to go deeper within that desktop window... */
	atom=XInternAtom(display,"NAUTILUS_DESKTOP_WINDOW_ID",False);
	r=XGetWindowProperty(display,rwin,atom,0,1,False,XA_WINDOW,
	                     &type,&frmt,&len,&rem,&data);
	win=(r==Success && type==XA_WINDOW && data) ? *(Window*)data : None;
	if (data) XFree(data);
	if (win) {
		for (win2=win;;) {
			XQueryTree(display,win2,&win4,&win5,&cwins,(unsigned*)&n);
			for (win3=None, i=n-1; i>=0; i--) {
				XGetWindowAttributes(display,cwins[i],&attr);
				if (attr.x==0 && attr.y==0 && attr.width==rwidth &&
				    attr.height==rheight && attr.map_state==IsViewable &&
				    attr.override_redirect==False) {
					win3=cwins[i];
					break;
				}
			}
			if (cwins) XFree(cwins);
			if (win3==None) break;
			win2=win3;
		}
		if (xdwOptVerb>=1) {
			printf("Nautilus Desktop detected: 0x%lX, using 0x%lX\n",win,win2);
		}
		*pIsNautilus=True;
		return win2;
	}

	/* For old version of KDE, or if "Allow Programs in Desktop Window"
	   has not been enabled in the KDE Desktop Configuration: There is a
	   child-of-child-of-child-of-root window named "KDE Desktop". All
	   windows in that path are full-size. But we have to go deeper within
	   the desktop window, with large-size instead of full-size... */
	XQueryTree(display,rwin,&win,&win2,&cwins,(unsigned*)&n);
	for (win=None, i=n-1; win==None && i>=0; i--) {
		XGetWindowAttributes(display,cwins[i],&attr);
		if (attr.x!=0 || attr.y!=0 || attr.width!=rwidth ||
		    attr.height!=rheight || attr.map_state!=IsViewable) continue;
		XQueryTree(display,cwins[i],&win2,&win3,&cwins2,(unsigned*)&m);
		for (j=m-1; win==None && j>=0; j--) {
			XGetWindowAttributes(display,cwins2[j],&attr);
			if (attr.x!=0 || attr.y!=0 || attr.width!=rwidth ||
			    attr.height!=rheight || attr.map_state!=IsViewable ||
			    attr.override_redirect!=False) continue;
			XQueryTree(display,cwins2[j],&win2,&win3,&cwins3,(unsigned*)&l);
			for (k=l-1; win==None && k>=0; k--) {
				XGetWindowAttributes(display,cwins3[k],&attr);
				if (attr.x!=0 || attr.y!=0 || attr.width!=rwidth ||
				    attr.height!=rheight || attr.map_state!=IsViewable ||
				    attr.override_redirect!=False) continue;
				if (XFetchName(display,cwins3[k],&str)) {
					if (strcmp(str,"KDE Desktop")==0) win=cwins3[k];
					XFree(str);
				}
			}
			if (cwins3) XFree(cwins3);
		}
		if (cwins2) XFree(cwins2);
	}
	if (cwins) XFree(cwins);
	if (win) {
		for (win2=win;;) {
			XQueryTree(display,win2,&win4,&win5,&cwins,(unsigned*)&n);
			for (win3=None, i=n-1; i>=0; i--) {
				XGetWindowAttributes(display,cwins[i],&attr);
				if (attr.x>=0 && attr.y>=0 && attr.x+attr.width<=rwidth &&
				    attr.y+attr.height<=rheight && attr.width>=rwidth*3/4 &&
				    attr.height>=rheight*3/4 && attr.map_state==IsViewable &&
				    attr.override_redirect==False) {
					win3=cwins[i];
					break;
				}
			}
			if (cwins) XFree(cwins);
			if (win3==None) break;
			win2=win3;
		}
		if (xdwOptVerb>=1) {
			printf("KDE Desktop detected: 0x%lX, using 0x%lX\n",win,win2);
		}
		return win2;
	}

	/* For CDE and possibly others: Try to detect another backdrop window on
	   the real root and prepare for stacking our backdrop above the other
	   backdrop. This should be safe, because it is checked that the other
	   backdrop has no children, no button input and no other window behind. */
	XQueryTree(display,rwin,&win2,&win3,&cwins,(unsigned*)&n);
	win=(n>=1?cwins[0]:None);
	if (cwins) XFree(cwins);
	if (win!=None && XFetchName(display,win,&str) && str) {
		if (strcmp(str,"xdesktopwaves")==0) win=None;
		XFree(str);
	}
	if (win!=None) {
		XGetWindowAttributes(display,win,&attr);
		if (attr.x==0 && attr.y==0 && attr.width==rwidth &&
		    attr.height==rheight && attr.border_width==0 &&
		    attr.map_state==IsViewable && attr.override_redirect==True &&
		    attr.class==InputOutput && !(attr.all_event_masks&ButtonPressMask)) {
			XQueryTree(display,win,&win2,&win3,&cwins,(unsigned*)&n);
			if (cwins) XFree(cwins);
			if (n==0) {
				if (xdwOptVerb>=1) printf("Other backdrop detected (CDE?)\n");
				*pAboveWin=win;
				return rwin;
			}
		}
	}

	/* No special window found. Just return the real root window. */
	return rwin;
}


/*============================================================================*/
/*============================== Mouse on Water ==============================*/
/*============================================================================*/

int xdwMouseX=-1, xdwMouseY=-1;
	/* Position of the mouse pointer, or -1 if the mouse does not cover the
	   water. */


static Bool xdwChangeMouse(int mx, int my)
{
	Bool b;

	/* Change the mouse position and adapt the covering. */
	b=False;
	if (xdwOptWavesByMouse && (mx!=xdwMouseX || my!=xdwMouseY)) {
		if (xdwMouseX>=0) b|=xdwCoverCircle(xdwMouseX,xdwMouseY,6,-1);
		xdwMouseX=mx;
		xdwMouseY=my;
		if (xdwMouseX>=0) b|=xdwCoverCircle(xdwMouseX,xdwMouseY,6,1);
	}
	return b;
}


/*============================================================================*/
/*======== Windows on Water, Visibility, Event Selection, Backdropping =======*/
/*============================================================================*/

/* This ugly part has four jobs:
     - Interaction of windows and water.
     - Determine whether the output window is fully obscured by other windows.
     - Select events.
     - Update backdropping of the output window.
   To solve these, we are tracking a tree of windows. Our anchor to the tree
   is not the root window, but the output window (variable xdwWinPath). The
   windows w1=xdwWinPath, w2=w1->parent, w3=w2->parent... are making up the
   path from the output window up to the root window (possibly it's just one
   window). For each window in that path, we are tracking all their direct
   children. Several events have to be selected for keeping the tree
   up-to-date. And because XSelectInput has no and/or/xor option, the events
   from the other program parts are even selected here (e.g. mouse movements
   on the output window). Unfortunately the XVisibilityEvent would be useless
   here, because it does not respect child windows. Instead, the visibility
   is calculated from the mentioned windows, using xdwRegion. Finally, because
   we know the window lists in this program part, it is even a good place for
   updating the backdropping. */


typedef struct xdwWinNodeStruct {
	/* Data type for an element in the tree of windows. */

	struct xdwWinNodeStruct * sister;
		/* Next element in the parent's list of children. */

	struct xdwWinNodeStruct * parent;
		/* The parent (next element in path). */

	struct xdwWinNodeStruct * childInPath;
		/* The child where the output window is (previous element in path). */

	struct xdwWinNodeStruct * firstChild;
		/* List of all children. */

	Window window;
		/* Id of the window. */

	long eventMask, shapeEventMask;
		/* Selected events on the window. */

	XWindowAttributes attr;
		/* Attributes of the window. */

	XRectangle * shapeRects;
	int shapeRectCount;
		/* Array of rectangles, if it is a shaped window. */

	unsigned isInPath : 1;
		/* Whether this window is member of the path. */

	unsigned interaction : 1;
		/* Whether this window should interact with the water. */

	unsigned attrUpToDate : 1;
		/* Whether the attributes are up-to-date. */

	unsigned linkageUpToDate : 1;
		/* Whether the relationships to other windows are up-to-date. */

	unsigned shapeUpToDate : 1;
		/* Whether the shape information is up-to-date. */

	unsigned interactionUpToDate : 1;
		/* Whether the interaction information is up-to-date. */

} xdwWinNode;


xdwWinNode * xdwWinPath;
	/* (refer to the description above) */

int xdwWinPathX,xdwWinPathY;
	/* Position of the output window relative to the root window. */

int xdwShapeEventBase, xdwShapeErrorBase;
	/* General information about the XShape extension. */

Atom XDESKTOPWAVES_WINDOW_INTERACTION;
	/* Property of client windows. It overrides the waves-by-windows
	   option. */

xdwRegion xdwWindowShips;
	/* This region summarizes all windows which interact with the water. */

int xdwVisiblePixels;
	/* Number of visible pixels in the output window. */

Bool xdwWindowTrackingUpToDate;
	/* Whether everything here is up-to-date. */


static xdwWinNode * xdwCreateWinNode(Window window)
{
	xdwWinNode * n;

	/* Create a new window node. */
	n=malloc(sizeof(xdwWinNode));
	memset(n,0,sizeof(xdwWinNode));
	n->window=window;
	return n;
}


static void xdwDestroyWinTree(Display * display, xdwWinNode * tree)
{
	xdwWinNode * n;

	/* Destroy a node and all its descendants */
	if (tree) {
		while ((n=tree->firstChild)!=NULL) {
			tree->firstChild=n->sister;
			xdwDestroyWinTree(display,n);
		}
		if (tree->eventMask || tree->shapeEventMask) {
			xdwBeginAcceptXErrors();
				if (tree->eventMask) {
					XSelectInput(display,tree->window,0);
				}
				if (tree->shapeEventMask) {
					XShapeSelectInput(display,tree->window,0);
				}
				XSync(display,False);
			xdwEndAcceptXErrors();
		}
		if (tree->shapeRects) {
			XFree(tree->shapeRects);
		}
		free(tree);
	}
}


static void xdwDestroyWinAncestors(Display * display, xdwWinNode * node)
{
	xdwWinNode * n, * parent;
	xdwWinNode * * pn;

	/* Destroy all nodes but the given node and its descendants */
	if (node && node->parent) {
		parent=node->parent;
		node->parent=NULL;
		for (pn=&parent->firstChild, n=*pn; n; pn=&n->sister, n=*pn) {
			if (n==node) {
				*pn=n->sister;
				n->sister=NULL;
				break;
			}
		}
		while (parent->parent) parent=parent->parent;
		xdwDestroyWinTree(display,parent);
	}
}


static void xdwInitWindowTracking(Display * display, Window drawWin)
{
	/* Query Shape extension. */
	if (!XShapeQueryExtension(display,&xdwShapeEventBase,&xdwShapeErrorBase)) {
		fprintf(stderr,"%s: XShape extension not available\n",xdwArg0);
		exit(1);
	}

	/* Have an atom for the window interaction property. */
	XDESKTOPWAVES_WINDOW_INTERACTION=XInternAtom(
		display,"XDESKTOPWAVES_WINDOW_INTERACTION",False
	);

	/* Create a node for the output window. */
	xdwWinPath=xdwCreateWinNode(drawWin);
	xdwWinPath->isInPath=1;

	/* Prepare some other variables. */
	xdwWinPathX=0;
	xdwWinPathY=0;
	xdwInitRegion(&xdwWindowShips);
	xdwVisiblePixels=0;

	/* Not up-to-date. */
	xdwWindowTrackingUpToDate=False;
}


static xdwWinNode * xdwSearchWinNode(Window window)
{
	xdwWinNode * n;

	/* Search for a node by a given window id. */
	n=xdwWinPath;
	while (n->parent) n=n->parent;
	while (n->window!=window) {
		if (n->firstChild) n=n->firstChild;
		else if (n->sister) n=n->sister;
		else {
			do {
				n=n->parent;
			} while (n && !n->sister);
			if (!n) break;
			n=n->sister;
		}
	}
	return n;
}


static void xdwOnSubstructureChanged(Window window)
{
	xdwWinNode * n;

	/* Got a substructure notify event... */
	n=xdwSearchWinNode(window);
	if (n) {
		n->linkageUpToDate=0;
		for (n=n->firstChild; n; n=n->sister) {
			n->attrUpToDate=0;
			/* We will not get any shape notify events, if the window is
			   not shaped. Therefore: */
			if (n->shapeRects && n->shapeRectCount<=1) n->shapeUpToDate=0;
		}
		xdwWindowTrackingUpToDate=False;
	}
}


static void xdwOnInteractionPropertyChanged(Window window)
{
	xdwWinNode * n;

	/* Got a change event for the interaction property... */
	n=xdwSearchWinNode(window);
	if (n) {
		n->interactionUpToDate=0;
		xdwWindowTrackingUpToDate=False;
	}
}


static void xdwOnShapeChanged(Window window)
{
	xdwWinNode * n;

	/* Got a shape notify event... */
	n=xdwSearchWinNode(window);
	if (n) {
		n->shapeUpToDate=0;
		xdwWindowTrackingUpToDate=False;
	}
}


static Bool xdwUpdateWinNode(Display * display, xdwWinNode * node)
{
	xdwWinNode * n, * oldList;
	xdwWinNode * * pn, * * pn2;
	long eventMask, shapeEventMask;
	unsigned long len, rem;
	unsigned char * data;
	Window rwin, pwin;
	Window * cwins;
	Atom type;
	int i, ordering, r, frmt, cnt;

	/* Which events should be selected on the window? */
	if (node->isInPath) {
		eventMask=SubstructureNotifyMask;
		shapeEventMask=0;
		if (!node->parent) eventMask|=PropertyChangeMask;
		if (!node->childInPath) {
			eventMask|=ExposureMask|PointerMotionMask|EnterWindowMask|LeaveWindowMask;
		}
		else if (!node->childInPath->childInPath && xdwOptTransparency==XDW_SHAPED) {
			eventMask|=PointerMotionMask|EnterWindowMask|LeaveWindowMask;
		}
	}
	else {
		eventMask=PropertyChangeMask;
		shapeEventMask=ShapeNotifyMask;
	}

	/* Update event selection. */
	if (node->eventMask!=eventMask || node->shapeEventMask!=shapeEventMask) {
		xdwBeginAcceptXErrors();
			if (node->eventMask!=eventMask) {
				XSelectInput(display,node->window,eventMask);
				node->eventMask=eventMask;
			}
			if (node->shapeEventMask!=shapeEventMask) {
				XShapeSelectInput(display,node->window,shapeEventMask);
				node->shapeEventMask=shapeEventMask;
			}
			XSync(display,False);
		xdwEndAcceptXErrors();
	}

	/* Update attributes. */
	if (!node->attrUpToDate) {
		xdwBeginAcceptXErrors();
			r=XGetWindowAttributes(display,node->window,&node->attr);
			if (!r) memset(&node->attr,0,sizeof(node->attr));
			node->attrUpToDate=1;
		xdwEndAcceptXErrors();
	}

	/* Update shape information. */
	if (!node->shapeUpToDate) {
		if (node->shapeRects) {
			XFree(node->shapeRects);
			node->shapeRects=NULL;
			node->shapeRectCount=0;
		}
		if (!node->isInPath) {
			xdwBeginAcceptXErrors();
				node->shapeRects=XShapeGetRectangles(
					display,node->window,ShapeBounding,&node->shapeRectCount,
					&ordering
				);
			xdwEndAcceptXErrors();
		}
		node->shapeUpToDate=1;
	}

	/* Update interaction bit. */
	if (!node->interactionUpToDate) {
		if (node->isInPath) {
			node->interaction=1;
		}
		else {
			xdwBeginAcceptXErrors();
				data=NULL;
				r=XGetWindowProperty(
					display,node->window,XDESKTOPWAVES_WINDOW_INTERACTION,
					0,1,False,XA_CARDINAL,&type,&frmt,&len,&rem,&data
				);
				if (r==Success && type==XA_CARDINAL && data) {
					node->interaction = (*(unsigned*)data) ? 1 : 0;
				}
				else {
					node->interaction = xdwOptWavesByWindows ? 1 : 0;
				}
				if (data) XFree(data);
			xdwEndAcceptXErrors();
		}
		node->interactionUpToDate=1;
	}

	/* Update relationships. */
	if (!node->linkageUpToDate) {

		/* Query tree... */
		xdwBeginAcceptXErrors();
			r=XQueryTree(display,node->window,&rwin,&pwin,&cwins,(unsigned*)&cnt);
			if (!r) { rwin=None; pwin=None; cwins=NULL; cnt=0; }
		xdwEndAcceptXErrors();

		/* Do not have any children if this is a window "out-of-path". */
		if (!node->isInPath && cwins) {
			XFree(cwins);
			cwins=NULL;
			cnt=0;
		}

		/* Check parent relation. */
		if (
			(!node->parent && pwin!=None) ||
			(node->parent && node->parent->window!=pwin)
		) {
			if (node->isInPath) {
				if (node->parent) {
					xdwDestroyWinAncestors(display,node);
					node->parent=NULL;
				}
				if (pwin!=None) {
					node->parent=xdwCreateWinNode(pwin);
					node->parent->isInPath=1;
					node->parent->firstChild=node;
					node->parent->childInPath=node;
					node->sister=NULL;
				}
			}
			else {
				node->parent->linkageUpToDate=0;
				if (cwins) XFree(cwins);
				return False;
			}
		}

		/* Check child-in-path relation. */
		if (node->childInPath) {
			for (i=0; i<cnt && cwins[i]!=node->childInPath->window; i++);
			if (i>=cnt) {
				node->childInPath->linkageUpToDate=0;
				if (cwins) XFree(cwins);
				return False;
			}
		}

		/* Update the list of children. */
		oldList=node->firstChild;
		node->firstChild=NULL;
		pn=&node->firstChild;
		for (i=0; i<cnt; i++) {
			for (pn2=&oldList, n=*pn2; n; pn2=&n->sister, n=*pn2) {
				if (n->window==cwins[i]) break;
			}
			if (n) {
				*pn2=n->sister;
				n->sister=NULL;
			}
			else {
				n=xdwCreateWinNode(cwins[i]);
				n->parent=node;
				n->linkageUpToDate=1;
			}
			*pn=n;
			pn=&n->sister;
		}
		while ((n=oldList)!=NULL) {
			oldList=n->sister;
			xdwDestroyWinTree(display,n);
		}

		if (cwins) XFree(cwins);
		node->linkageUpToDate=1;
	}

	return True;
}


static Bool xdwUpdateWindowTracking(Display * display)
{
	xdwWinNode * pathElement, * child;
	xdwWinNode * node, * n;
	xdwRegion oldShips, noShips, visibility;
	xdwRegScan * s, * t;
	Bool coveringChanged;
	Window swins[2];
	int x0, y0, y, y2, i;

	/* Be quick if everything is up-to-date here. */
	if (xdwWindowTrackingUpToDate) return False;

	/* Update the tree... */
	for (pathElement=xdwWinPath; pathElement;) {
		if (!xdwUpdateWinNode(display,pathElement)) {
			pathElement=xdwWinPath;
		}
		else {
			for (child=pathElement->firstChild; ; child=child->sister) {
				if (!child) {
					pathElement=pathElement->parent;
					break;
				}
				if (!xdwUpdateWinNode(display,child)) {
					pathElement=xdwWinPath;
					break;
				}
			}
		}
	}

	/* Calculate region of visible areas (visibility), calculate region
	   of interacting windows (xdwWindowShips, but keep old variant
	   in oldShips), and calculate the relative position of the
	   output window (xdwWinPathX, xdwWinPathY).  */
	memcpy(&oldShips,&xdwWindowShips,sizeof(xdwRegion));
	xdwInitRegion(&xdwWindowShips);
	xdwInitRegion(&visibility);
	xdwInitRegion(&noShips);
	xdwSetRegionRect(
		&noShips,0,0,xdwWinPath->attr.width,xdwWinPath->attr.height
	);
	if (xdwWinPath->attr.map_state==IsViewable) {
		xdwSetRegionRect(
			&visibility,0,0,xdwWinPath->attr.width,xdwWinPath->attr.height
		);
	}
	for (x0=0, y0=0, node=xdwWinPath; node; node=node->parent) {
		if (node->childInPath) {
			n=node->childInPath;
			x0-=n->attr.x;
			y0-=n->attr.y;
			n=n->sister;
			xdwRegAndRect(
				&visibility,
				x0,
				y0,
				x0+node->attr.width,
				y0+node->attr.height
			);
		}
		else {
			n=node->firstChild;
		}
		for (; n; n=n->sister) {
			if (n->attr.map_state==IsViewable && n->attr.class!=InputOnly) {
				if (n->shapeRects) {
					for (i=0; i<n->shapeRectCount; i++) {
						xdwRegAndNotRect(
							n->interaction ? &noShips : &visibility,
							x0+n->attr.x+n->shapeRects[i].x,
							y0+n->attr.y+n->shapeRects[i].y,
							x0+n->attr.x+n->shapeRects[i].x+n->shapeRects[i].width,
							y0+n->attr.y+n->shapeRects[i].y+n->shapeRects[i].height
						);
					}
				}
				else {
					xdwRegAndNotRect(
						n->interaction ? &noShips : &visibility,
						x0+n->attr.x-n->attr.border_width,
						y0+n->attr.y-n->attr.border_width,
						x0+n->attr.x+n->attr.width+n->attr.border_width,
						y0+n->attr.y+n->attr.height+n->attr.border_width
					);
				}
			}
		}
	}
	xdwSetRegionRect(
		&xdwWindowShips,0,0,xdwWinPath->attr.width,xdwWinPath->attr.height
	);
	xdwRegAndNotReg(&xdwWindowShips,&noShips);
	xdwRegAndNotReg(&visibility,&xdwWindowShips);
	xdwWinPathX = -x0;
	xdwWinPathY = -y0;

	/* How many visible pixels do we have in the output window? */
	xdwVisiblePixels=xdwCountRegionPixels(&visibility);

	/* Update covering by windows. */
	coveringChanged=False;
	y=xdwWindowShips.y1; if (y>oldShips.y1) y=oldShips.y1;
	y2=xdwWindowShips.y2; if (y2<oldShips.y2) y2=oldShips.y2;
	for (s=NULL, t=NULL; y<y2; y++) {
		if (y>=oldShips.y1 && y<oldShips.y2) {
			s=oldShips.rows[y-oldShips.y1];
		}
		if (y>=xdwWindowShips.y1 && y<xdwWindowShips.y2) {
			t=xdwWindowShips.rows[y-xdwWindowShips.y1];
		}
		while (s || t) {
			if (!t || (s && s->x1<t->x1)) {
				coveringChanged|=xdwCoverRect(s->x1,y,s->x2,y+1,-1);
				s=s->next;
			}
			else if (!s || s->x1!=t->x1 || s->x2!=t->x2) {
				coveringChanged|=xdwCoverRect(t->x1,y,t->x2,y+1,1);
				t=t->next;
			}
			else {
				s=s->next;
				t=t->next;
			}
		}
	}

	/* Get rid of temporary regions. */
	xdwEmptyRegion(&visibility);
	xdwEmptyRegion(&noShips);
	xdwEmptyRegion(&oldShips);

	/* Backdropping: If there is a non-override-redirect window somewhere
	   behind our backdrop window, bring our window behind it. */
	if (xdwOptWindowCreation==XDW_BACKDROP && xdwWinPath->parent) {
		n=xdwWinPath->parent->firstChild;
		while (n!=xdwWinPath) {
			if (!n->attr.override_redirect) {
				swins[0]=n->window;
				swins[1]=xdwWinPath->window;
				xdwBeginAcceptXErrors();
					XRestackWindows(display,swins,2);
					XSync(display,False);
				xdwEndAcceptXErrors();
				break;
			}
			n=n->sister;
		}
	}

	/* Ready. */
	xdwWindowTrackingUpToDate=True;
	return coveringChanged;
}


/*============================================================================*/
/*======================= Inter client communications ========================*/
/*============================================================================*/

Window xdwWindow;
	/* A created window for receiving client messages. */

Atom XDESKTOPWAVES_WINDOW_ID;
	/* A root window property for the window id. */

Atom XDESKTOPWAVES_COMMAND_MESSAGE;
	/* Client message type for receiving commands. */

Atom xdw_WM_PROTOCOLS;
Atom xdw_WM_DELETE_WINDOW;
	/* Atoms for receiving deletion requests from the window manager. */

typedef struct xdwGhostStruct {
	/* Data type for a "ghost" on the water, generated by a client. */
	struct xdwGhostStruct * next; /* Next elements in the list. */
	int ghostId;    /* Identification number of the ghost. */
	int milliSecs;  /* Remaining lifetime in milliseconds. */
	Bool isCircle;  /* Whether it's a circle or a rectangle. */
	int x, y, width, height, radius; /* Coordinates... */
} xdwGhost;

xdwGhost * xdwGhostList;
	/* List of ghosts. */


static void xdwInitCommunications(Display * display, Window ownWin)
{
	/* Keep id of created window. */
	xdwWindow=ownWin;

	/* Have some atoms. */
	XDESKTOPWAVES_WINDOW_ID=XInternAtom(
		display,"XDESKTOPWAVES_WINDOW_ID",False
	);
	XDESKTOPWAVES_COMMAND_MESSAGE=XInternAtom(
		display,"XDESKTOPWAVES_COMMAND_MESSAGE",False
	);
	xdw_WM_PROTOCOLS=XInternAtom(
		display,"WM_PROTOCOLS",False
	);
	xdw_WM_DELETE_WINDOW=XInternAtom(
		display,"WM_DELETE_WINDOW",False
	);

	/* Set the window id property. Other instances will terminate after
	   recognizing the change. */
	XChangeProperty(display,DefaultRootWindow(display),XDESKTOPWAVES_WINDOW_ID,
	                XA_WINDOW,32,PropModeReplace,(unsigned char*)&xdwWindow,1);

	/* Just for terminating old versions of xdesktopwaves. */
	XDeleteProperty(display,DefaultRootWindow(display),
	                XInternAtom(display,"XDESKTOPWAVES_INSTANCE_ID",False));

	/* Finalize the property changes. */
	XSync(display,False);
}


static void xdwCheckInstance(Display * display)
{
	unsigned char * data;
	unsigned long len, bytesAfter;
	int format, ret;
	Atom type;

	/* See if there is a newer instance. If so, prepare for termination. */
	data=NULL;
	ret=XGetWindowProperty(
		display,DefaultRootWindow(display),XDESKTOPWAVES_WINDOW_ID,0,1,False,
		XA_WINDOW,&type,&format,&len,&bytesAfter,&data
	);
	if (
		ret!=Success || type!=XA_WINDOW || format!=32 || bytesAfter!=0 ||
		len!=1 || (*(Window*)data)!=xdwWindow
	) {
		xdwTerminationRequested=True;
	}
	if (data) XFree(data);
}


static Bool xdwCoverByGhost(xdwGhost * g, int deltaCovering)
{
	if (g->isCircle) {
		return xdwCoverCircle(g->x,g->y,g->radius,deltaCovering);
	}
	else {
		return xdwCoverRect(g->x,g->y,g->x+g->width,g->y+g->height,deltaCovering);
	}
}


static Bool xdwOnClientMessage(XClientMessageEvent * msg)
{
	xdwGhost * g;
	Bool changed;
	int removeId,intensity;

	changed=False;
	if (msg->message_type==xdw_WM_PROTOCOLS) {
		if (msg->data.l[0]==xdw_WM_DELETE_WINDOW) {
			if (xdwOptVerb>=2) printf("got WM_DELETE_WINDOW\n");
			xdwTerminationRequested=True;
		}
	}
	else if (msg->message_type==XDESKTOPWAVES_COMMAND_MESSAGE) {
		if (xdwOptVerb>=2) printf(
			"got command: %d %d %d %d %d %d %d %d %d %d\n",
			msg->data.s[0],msg->data.s[1],msg->data.s[2],msg->data.s[3],
			msg->data.s[4],msg->data.s[5],msg->data.s[6],msg->data.s[7],
			msg->data.s[8],msg->data.s[9]
		);
		switch (msg->data.s[0])
		{
		case 0: /* Ping */
			break;
		case 1: /* Clear */
			xdwClearCells();
			changed=True;
			break;
		case 2: /* SetRain */
			intensity=msg->data.s[1];
			if (intensity<0) intensity=0;
			else if (intensity>10) intensity=10;
			xdwOptRain=intensity;
			break;
		case 3: /* SetStorm */
			intensity=msg->data.s[1];
			if (intensity<0) intensity=0;
			else if (intensity>10) intensity=10;
			xdwOptStorm=intensity;
			changed=True; /* (to get out of idle mode) */
			break;
		case 4: /* PutRaindrop */
			changed=xdwPutRaindrop(
				msg->data.s[1]-xdwWinPathX,
				msg->data.s[2]-xdwWinPathY,
				msg->data.s[3]
			);
			break;
		case 5: /* PutGhostRect */
		case 6: /* PutGhostCircle */
			removeId=(((int)msg->data.s[3])<<16)|(unsigned short)msg->data.s[4];
			g=NULL;
			if (removeId) {
				for (g=xdwGhostList; g; g=g->next) {
					if (g->ghostId==removeId) break;
				}
			}
			if (g) {
				changed|=xdwCoverByGhost(g,-1);
			}
			else {
				g=(xdwGhost*)malloc(sizeof(xdwGhost));
				g->next=xdwGhostList;
				xdwGhostList=g;
			}
			g->ghostId=(((int)msg->data.s[1])<<16)|(unsigned short)msg->data.s[2];
			g->milliSecs=msg->data.s[5];
			g->x=msg->data.s[6]-xdwWinPathX;
			g->y=msg->data.s[7]-xdwWinPathY;
			if (msg->data.s[0]==5) {
				g->isCircle=False;
				g->width=msg->data.s[8];
				g->height=msg->data.s[9];
			}
			else {
				g->isCircle=True;
				g->radius=msg->data.s[8];
			}
			changed|=xdwCoverByGhost(g,1);
			break;
		}
	}
	return changed;
}


static Bool xdwUpdateGhosts(int milliSecsGone)
{
	xdwGhost * * ps;
	xdwGhost * s;
	Bool changed;

	if (milliSecsGone<0) milliSecsGone=0;
	changed=False;
	for (ps=&xdwGhostList, s=*ps; s; ) {
		s->milliSecs-=milliSecsGone;
		if (s->milliSecs<=0) {
			changed|=xdwCoverByGhost(s,-1);
			*ps=s->next;
			free(s);
		}
		else {
			ps=&s->next;
		}
		s=*ps;
	}
	return changed;
}


/*============================================================================*/
/*============================== Event Handling ==============================*/
/*============================================================================*/

static Bool xdwHandleEvent(Display * display, XEvent * event)
{
	Bool coveringChanged;

	coveringChanged=False;
	switch (event->type) {
	case ClientMessage:
		coveringChanged=xdwOnClientMessage(&event->xclient);
		break;
	case PropertyNotify:
		if (event->xproperty.atom==XDESKTOPWAVES_WINDOW_ID) {
			if (xdwOptVerb>=2) printf(
				"PropertyNotify: window=0x%lX atom=XDESKTOPWAVES_WINDOW_ID\n",
				event->xproperty.window
			);
			xdwCheckInstance(display);
		}
		else if (event->xproperty.atom==XDESKTOPWAVES_WINDOW_INTERACTION) {
			if (xdwOptVerb>=2) printf(
				"PropertyNotify: window=0x%lX atom=XDESKTOPWAVES_WINDOW_INTERACTION\n",
				event->xproperty.window
			);
			xdwOnInteractionPropertyChanged(event->xproperty.window);
		}
		break;
	case Expose:
		if (xdwOptVerb>=2) printf(
			"Expose: x=%d y=%d w=%d h=%d\n",
			event->xexpose.x,
			event->xexpose.y,
			event->xexpose.width,
			event->xexpose.height
		);
		/* TODO: If in double buffering mode, the exposed area should be
		   copied from the back buffer to the window, instead of touching
		   the canvas. (=> less flicker and less overhead) */
		xdwTouchCanvas(
			event->xexpose.x,
			event->xexpose.y,
			event->xexpose.x+event->xexpose.width,
			event->xexpose.y+event->xexpose.height
		);
		break;
	case MotionNotify:
		if (xdwOptVerb>=2) printf(
			"MotionNotify: x=%d y=%d\n",
			event->xmotion.x,
			event->xmotion.y
		);
		coveringChanged=xdwChangeMouse(event->xmotion.x,event->xmotion.y);
		break;
	case EnterNotify:
		if (xdwOptVerb>=2) printf(
			"EnterNotify: x=%d y=%d\n",
			event->xcrossing.x,
			event->xcrossing.y
		);
		coveringChanged=xdwChangeMouse(event->xcrossing.x,event->xcrossing.y);
		break;
	case LeaveNotify:
		if (xdwOptVerb>=2) printf("LeaveNotify\n");
		coveringChanged=xdwChangeMouse(-1,-1);
		break;
	case CreateNotify:
		if (xdwOptVerb>=2) printf(
			"CreateNotify parent=0x%lX window=0x%lX\n",
			event->xcreatewindow.parent,
			event->xcreatewindow.window
		);
		xdwOnSubstructureChanged(event->xcreatewindow.parent);
		break;
	case DestroyNotify:
		if (xdwOptVerb>=2) printf(
			"DestroyNotify window=0x%lX\n",
			event->xdestroywindow.window
		);
		if (event->xdestroywindow.window==xdwWinPath->window) {
			xdwTerminationRequested=True;
			break;
		}
		xdwOnSubstructureChanged(event->xdestroywindow.event);
		break;
	case MapNotify:
		if (xdwOptVerb>=2) printf(
			"MapNotify window=0x%lX\n",
			event->xmap.window
		);
		xdwOnSubstructureChanged(event->xmap.event);
		break;
	case UnmapNotify:
		if (xdwOptVerb>=2) printf(
			"UmapNotify window=0x%lX\n",
			event->xunmap.window
		);
		xdwOnSubstructureChanged(event->xunmap.event);
		break;
	case ConfigureNotify:
		if (xdwOptVerb>=2) printf(
			"ConfigureNotify window=0x%lX\n",
			event->xconfigure.window
		);
		xdwOnSubstructureChanged(event->xconfigure.event);
		break;
	case CirculateNotify:
		if (xdwOptVerb>=2) printf(
			"CirculateNotify window=0x%lX\n",
			event->xcirculate.window
		);
		xdwOnSubstructureChanged(event->xcirculate.event);
		break;
	case ReparentNotify:
		if (xdwOptVerb>=2) printf(
			"ReparentNotify event=0x%lX window=0x%lX parent=0x%lX\n",
			event->xreparent.event,
			event->xreparent.window,
			event->xreparent.parent
		);
		xdwOnSubstructureChanged(event->xreparent.event);
		break;
	default:
		if (event->type==xdwShapeEventBase+ShapeNotify) {
			if (xdwOptVerb>=2) printf(
				"ShapeNotify window=0x%lX\n",
				((XShapeEvent*)event)->window
			);
			xdwOnShapeChanged(((XShapeEvent*)event)->window);
		}
		break;
	}

	return coveringChanged;
}


/*============================================================================*/
/*=================================== main ===================================*/
/*============================================================================*/

int main(int argc, char * argv[])
{
	Display * display;
	Window rootWin, ownWin, drawWin, aboveWin;
	Pixmap pm, pm2, bufferPM;
	GC gc, drawGC, bufferGC;
	XGCValues gcv;
	XSetWindowAttributes xswa;
	XWindowAttributes xwa;
	XWindowChanges xwc;
	XSizeHints xsh;
	Bool isNautilus, idleByWaves, idleByVisibility, wasIdle;
	Atom atoms[8];
	XEvent event;
	int width, height, calls, rects, loopRate, tsRem, frRem, timeSlices;
	int skippedTimeSlices, totalCalls, totalRects, sleepMS, reportMS;
	int totalFrames;
	unsigned card, prevAbsTimeMS, reportAbsTimeMS, reportProcTimeMS, t;

	/* Initialize handling of X errors. */
	xdwInitXErrorHandling();

	/* Prepare options. */
	xdwSetDefaultOptions();
	xdwParseOptions(argc,argv);

	/* Have a display. */
	if (!(display=XOpenDisplay(xdwOptDisplay))) {
		fprintf(stderr,"%s: failed to open display %s\n",xdwArg0,
		        XDisplayName(xdwOptDisplay));
		exit(1);
	}

	/* Set process priority. */
	if (xdwOptNice) {
		if (nice(xdwOptNice)==-1) {
			fprintf(stderr,"%s: nice(%d) failed: %s\n",
			        xdwArg0,xdwOptNice,strerror(errno));
			exit(1);
		}
	}

	/* Look for CPU features. */
	xdwDetectCPUFeatures();

	/* Which root window and size should be used? */
	if (xdwOptWindowCreation==XDW_USE_ROOT || xdwOptWindowCreation==XDW_BACKDROP) {
		rootWin=xdwDetectVirtualRoot(display,&aboveWin,&isNautilus);
		XGetWindowAttributes(display,rootWin,&xwa);
		width=xwa.width;
		height=xwa.height;
		/* Nautilus: Make the backdrop window a little smaller. Otherwise
		   xpenguins 2.2 (and maybe others) would take it as the virtual root! */
		if (isNautilus && xdwOptWindowCreation==XDW_BACKDROP) height--;
	}
	else {
		rootWin=DefaultRootWindow(display);
		aboveWin=None;
		XGetWindowAttributes(display,rootWin,&xwa);
		width=xwa.width;
		height=xwa.height;
	}

	/* Initialize several data structures. */
	xdwInitCells(width,height);
	xdwInitPalette(display);
	xdwInitLighting();
	xdwInitCanvas(width,height);

	/* Have a window for drawing and an own window for receiving client
	   messages (maybe it's just one window). */
	if (xdwOptWindowCreation==XDW_USE_ROOT) {
		drawWin=rootWin;
		memset(&xswa,0,sizeof(xswa));
		xswa.override_redirect=True;
		ownWin=XCreateWindow(
			display,DefaultRootWindow(display),-100,-100,1,1,0,CopyFromParent,
			InputOnly,CopyFromParent,CWOverrideRedirect,&xswa
		);
		XStoreName(display,ownWin,"xdesktopwaves");
	}
	else {
		memset(&xswa,0,sizeof(xswa));
		if (xdwOptWindowCreation==XDW_BACKDROP) xswa.override_redirect=True;
		memset(&xsh,0,sizeof(xsh));
		if (xdwOptWindowCreation==XDW_WINDOW) {
			xsh.flags     =PMinSize|PMaxSize;
			xsh.x         =width/16;
			xsh.y         =height/16;
			xsh.width     =width*7/8;
			xsh.height    =height*7/8;
			xsh.min_width =width/16;
			xsh.min_height=height/16;
			xsh.max_width =width;
			xsh.max_height=height;
		}
		else {
			xsh.flags     =PPosition|PSize|USPosition|USSize|PMinSize|PMaxSize;
			xsh.x         =0;
			xsh.y         =0;
			xsh.width     =width;
			xsh.height    =height;
			xsh.min_width =width;
			xsh.min_height=height;
			xsh.max_width =width;
			xsh.max_height=height;
		}
		drawWin=XCreateWindow(
			display,rootWin,xsh.x,xsh.y,xsh.width,xsh.height,0,CopyFromParent,
			InputOutput,CopyFromParent,CWOverrideRedirect,&xswa
		);
		XSetWMProperties(display,drawWin,NULL,NULL,0,0,&xsh,0,NULL);
		XStoreName(display,drawWin,"xdesktopwaves");
		atoms[0]=XInternAtom(display,"WM_DELETE_WINDOW",False);
		XChangeProperty(
			display,drawWin,XInternAtom(display,"WM_PROTOCOLS",False),XA_ATOM,32,
			PropModeReplace,(const unsigned char*)atoms,1
		);
		if (xdwOptWindowCreation==XDW_WMBACKDROP) {
			atoms[0]=XInternAtom(display,"_NET_WM_STATE_BELOW",False);
			atoms[1]=XInternAtom(display,"_NET_WM_STATE_FULLSCREEN",False);
			atoms[2]=XInternAtom(display,"_NET_WM_STATE_STICKY",False);
			atoms[3]=XInternAtom(display,"_NET_WM_STATE_SKIP_TASKBAR",False);
			atoms[4]=XInternAtom(display,"_NET_WM_STATE_SKIP_PAGER",False);
			XChangeProperty(
				display,drawWin,XInternAtom(display,"_NET_WM_STATE",False),XA_ATOM,
				32,PropModeReplace,(const unsigned char*)atoms,5
			);
			card=-1;
			XChangeProperty(
				display,drawWin,XInternAtom(display,"_NET_WM_DESKTOP",False),
				XA_CARDINAL,32,PropModeReplace,(const unsigned char*)&card,1
			);
		}
		XMapWindow(display,drawWin);
		if (xdwOptWindowCreation==XDW_BACKDROP) {
			XLowerWindow(display,drawWin);
			if (aboveWin!=None) {
				memset(&xwc,0,sizeof(xwc));
				xwc.sibling=aboveWin;
				xwc.stack_mode=Above;
				XConfigureWindow(display,drawWin,CWSibling|CWStackMode,&xwc);
			}
		}
		ownWin=drawWin;
	}

	/* Have a GC for the window. */
	drawGC=XCreateGC(display,drawWin,0,&gcv);

	/* Possibly have Pixmap and GC for double buffering. */
	if (xdwOptDoubleBuffer) {
		XGetWindowAttributes(display,drawWin,&xwa);
		bufferPM=XCreatePixmap(display,drawWin,width,height,xwa.depth);
		bufferGC=XCreateGC(display,bufferPM,0,&gcv);
	}
	else {
		bufferPM=None;
		bufferGC=None;
	}

	/* Prepare for transparency. */
	switch (xdwOptTransparency) {
	case XDW_OPAQUE:
		if (xdwOptWindowCreation!=XDW_USE_ROOT) {
			XSetWindowBackground(display,drawWin,xdwPalette[0]);
		}
		break;
	case XDW_STIPPLED:
		pm=XCreateBitmapFromData(display,drawWin,"\252\125",2,2);
		XSetStipple(display,drawGC,pm);
		XSetFillStyle(display,drawGC,FillStippled);
		if (xdwOptWindowCreation!=XDW_USE_ROOT) {
			XSetWindowBackgroundPixmap(display,drawWin,ParentRelative);
			XClearWindow(display,drawWin);
		}
		break;
	case XDW_SHAPED:
		/* Very slow in drawing with large number of operations => double
		   buffering recommended. Even, if the mask is not horizontal striped
		   (e.g. checkered) everything is extremely slow. */
		pm=XCreateBitmapFromData(display,drawWin,"\0\377",2,2);
		pm2=XCreatePixmap(display,drawWin,width,height,1);
		gcv.foreground = 1;
		gcv.background = 0;
		gc=XCreateGC(display,pm2,(GCForeground|GCBackground),&gcv);
		XSetStipple(display,gc,pm);
		XSetFillStyle(display,gc,FillOpaqueStippled);
		XFillRectangle(display,pm2,gc,0,0,width,height);
		XFreeGC(display,gc);
		XShapeCombineMask(display,drawWin,ShapeBounding,0,0,pm2,ShapeSet);
		XSetWindowBackground(display,drawWin,xdwPalette[0]);
		break;
	case XDW_WMOPACITY:
		if (xdwOptTranspaParam<100 && xdwOptWindowCreation!=XDW_USE_ROOT) {
			card=((unsigned)xdwOptTranspaParam)*42949672U;
			XChangeProperty(
				display,drawWin,XInternAtom(display,"_NET_WM_WINDOW_OPACITY",False),
				XA_CARDINAL,32,PropModeReplace,(unsigned char *)&card,1
			);
		}
		break;
	}

	/* Prepare for signals. */
	xdwInitSignalHandling();

	/* Prepare for tracking other windows covering our window. */
	xdwInitWindowTracking(display,drawWin);

	/* Prepare communications: Be the only instance on the display - other
	   instances will terminate. And maybe that's the only job we have to
	   do... */
	xdwInitCommunications(display,ownWin);
	if (xdwOptEnd) goto THE_END;

	/* Calculate rate of processing events. */
	if (xdwOptEventsPerFrame<xdwOptSimsPerFrame) {
		loopRate=xdwOptFrameRate*xdwOptEventsPerFrame;
	}
	else {
		loopRate=xdwOptFrameRate*xdwOptSimsPerFrame;
	}

	/* Main loop. */
	idleByWaves=False;
	idleByVisibility=False;
	xdwUpdateTimes();
	prevAbsTimeMS=xdwAbsTimeMS;
	reportAbsTimeMS=xdwAbsTimeMS;
	reportProcTimeMS=xdwProcTimeMS;
	totalFrames=0;
	totalCalls=0;
	totalRects=0;
	reportMS=250;
	tsRem=0;
	frRem=0;
	skippedTimeSlices=0;
	sleepMS=500/loopRate;
	for (;;) {

		/* Remember previous idle state. */
		wasIdle = idleByWaves | idleByVisibility;

		/* Process events. */
		while (XPending(display) && !xdwTerminationRequested) {
			XNextEvent(display,&event);
			if (xdwHandleEvent(display,&event)) idleByWaves=False;
		}

		/* Terminate? */
		if (xdwTerminationRequested) goto THE_END;

		/* This updates covering by mouse & windows, event selection and
		   backdropping. */
		if (xdwUpdateWindowTracking(display)) idleByWaves=False;

		/* Enter or leave idle mode by visibility and freezing. */
		if ((xdwOptIdle && xdwVisiblePixels<1000) || xdwFreeze) {
			idleByVisibility=True;
		}
		else {
			idleByVisibility=False;
		}

		/* This updates covering by ghosts. */
		if (xdwUpdateGhosts(xdwAbsTimeMS-prevAbsTimeMS)) idleByWaves=False;

		/* Calculate number of time slices to be simulated (excluding skipped
		   time slices by idle mode). */
		tsRem+=xdwOptFrameRate*xdwOptSimsPerFrame;
		timeSlices=tsRem/loopRate;
		tsRem-=timeSlices*loopRate;

		/* Update rain. */
		if (!idleByVisibility && xdwOptRain) {
			if (xdwUpdateRain(timeSlices+skippedTimeSlices)) idleByWaves=False;
		}

		/* Update water (includes storm). */
		if (!idleByWaves && !idleByVisibility) xdwUpdateCells(timeSlices);

		/* Have a new frame? */
		frRem+=timeSlices+skippedTimeSlices;
		if (frRem>=xdwOptSimsPerFrame) {
			frRem-=xdwOptSimsPerFrame;
			if (frRem>=xdwOptSimsPerFrame) frRem=0;
			totalFrames++;

			/* Update canvas. */
			if (!idleByWaves && !idleByVisibility) xdwUpdateCanvas();

			/* Are there any changes to be drawn? */
			if (xdwTouchedCvRow1<xdwTouchedCvRow2) {
				/* Yes, update the output window. */
				if (xdwOptDoubleBuffer) {
					xdwDrawCanvas(display,bufferPM,bufferGC,&calls,&rects);
					if (calls) {
						/* TODO: reduce the copying to a minimum out-of-date area. */
						XCopyArea(display,bufferPM,drawWin,drawGC,0,0,
						          width,height,0,0);
						XSync(display,False);
					}
				}
				else {
					xdwDrawCanvas(display,drawWin,drawGC,&calls,&rects);
					if (calls) XSync(display,False);
				}
				totalCalls+=calls;
				totalRects+=rects;
			}
			else {
				/* There were no changes to be drawn. Possibly there are no waves? */
				if (!idleByVisibility && !xdwOptStorm && xdwOptIdle) idleByWaves=True;
			}
		}

		/* Perform sleeping. */
		if (idleByWaves || idleByVisibility) {
			/* Idle mode: Skip time slices by sleeping for a longer period. */
			if (xdwOptVerb>=1 && !wasIdle && !xdwFreeze) {
				printf("Frames/s=0 CPU=0%% MBit/s=0.0 (IDLE MODE)\n");
			}
			t=1000000/xdwOptFrameRate;
			if (t<200000) t=200000;
			usleep(t);
			skippedTimeSlices=
				(xdwOptFrameRate*xdwOptSimsPerFrame*(t/1000-1000/loopRate)+500)
				/1000
			;
			if (skippedTimeSlices<0) skippedTimeSlices=0;
		}
		else {
			/* Non-idle mode: sleep for the best known delay (synchronization). */
			if (sleepMS>0) usleep(sleepMS*1000);
			skippedTimeSlices=0;
		}

		/* Update times. */
		prevAbsTimeMS=xdwAbsTimeMS;
		xdwUpdateTimes();

		/* Synchronize on desired frame rate and report statistics. */
		if (!idleByWaves && !idleByVisibility) {
			if (wasIdle) {
				reportAbsTimeMS=xdwAbsTimeMS;
				reportProcTimeMS=xdwProcTimeMS;
				totalFrames=0;
				totalCalls=0;
				totalRects=0;
				reportMS=250;
			}
			else {
				sleepMS+=(1000/loopRate-(int)(xdwAbsTimeMS-prevAbsTimeMS))/2;
				if (sleepMS<-100) sleepMS=-100;
				else if (sleepMS>1000) sleepMS=1000;
				t=xdwAbsTimeMS-reportAbsTimeMS;
				if (t>reportMS && totalFrames>0) {
					if (xdwOptVerb>=1) {
						printf(
							"Frames/s=%d CPU=%d%% MBit/s=%.1f XFillRectangles's/Frm=%d Rects/Frm=%d\n",
							(int)(totalFrames*1000.0/t+0.5),
							(int)((xdwProcTimeMS-reportProcTimeMS)*100.0/t+0.5),
							totalRects*0.069/t,
							totalCalls/totalFrames,
							totalRects/totalFrames
						);
					}
					reportAbsTimeMS=xdwAbsTimeMS;
					reportProcTimeMS=xdwProcTimeMS;
					totalFrames=0;
					totalCalls=0;
					totalRects=0;
					reportMS=1000;
				}
			}
		}
	}

THE_END:
	/* Termination: possibly redraw root window. */
	if (xdwOptWindowCreation==XDW_USE_ROOT) {
		XClearArea(display,rootWin,0,0,width,height,True);
	}
	XCloseDisplay(display);
	if (xdwOptVerb>=1) printf("Exiting proper.\n");
	return 0;
}