1/*
2 * Copyright (c) 1997 by Massimino Pascal <Pascal.Massimon@ens.fr>
3 * Copyright 2006-2014, Haiku, Inc. All rights reserved.
4 *
5 * Distributed under the terms of the MIT License.
6 *
7 * Authors:
8 *		Stephan A��mus, superstippi@gmx.de
9 *		Massimino Pascal, Pascal.Massimon@ens.fr
10 *		John Scipione, jscipione@gmail.com
11 */
12
13/*! When shown ifs, Diana Rose (4 years old) said, "It looks like dancing."
14 */
15
16#include "IFS.h"
17
18#include <new>
19#include <malloc.h>
20#include <stdio.h>
21#include <string.h>
22
23#include <Bitmap.h>
24#include <OS.h>
25#include <Screen.h>
26#include <View.h>
27
28#include <unistd.h>
29	// for getpid()
30#include <sys/time.h>
31	// for gettimeofday()
32
33
34#define HALF 0
35#define random() ya_random()
36
37#define FLOAT_TO_INT(x) (int32)((float)(UNIT)*(x))
38
39#define LRAND() ((long) (random() & 0x7fffffff))
40#define NRAND(n) ((int) (LRAND() % (n)))
41#define MAXRAND (2147483648.0)
42	// unsigned 1<<31 as a float
43#define SRAND(n)
44	// already seeded by screenhack.c TODO: ?!? is it?
45
46// The following 'random' numbers are taken from CRC, 18th Edition, page 622.
47// Each array element was taken from the corresponding line in the table,
48// except that a[0] was from line 100. 8s and 9s in the table were simply
49// skipped. The high order digit was taken mod 4.
50
51#define VECTOR_SIZE 55
52
53static unsigned int a[VECTOR_SIZE] = {
54	035340171546, 010401501101, 022364657325, 024130436022, 002167303062, //  5
55	037570375137, 037210607110, 016272055420, 023011770546, 017143426366, // 10
56	014753657433, 021657231332, 023553406142, 004236526362, 010365611275, // 14
57	007117336710, 011051276551, 002362132524, 001011540233, 012162531646, // 20
58	007056762337, 006631245521, 014164542224, 032633236305, 023342700176, // 25
59	002433062234, 015257225043, 026762051606, 000742573230, 005366042132, // 30
60	012126416411, 000520471171, 000725646277, 020116577576, 025765742604, // 35
61	007633473735, 015674255275, 017555634041, 006503154145, 021576344247, // 40
62	014577627653, 002707523333, 034146376720, 030060227734, 013765414060, // 45
63	036072251540, 007255221037, 024364674123, 006200353166, 010126373326, // 50
64	015664104320, 016401041535, 016215305520, 033115351014, 017411670323  // 55
65};
66
67
68static int i1;
69static int i2;
70
71
72unsigned int
73ya_random(void)
74{
75	int ret = a[i1] + a[i2];
76	a[i1] = ret;
77	if (++i1 >= VECTOR_SIZE)
78		i1 = 0;
79
80	if (++i2 >= VECTOR_SIZE)
81		i2 = 0;
82
83	return ret;
84}
85
86
87void
88ya_rand_init(unsigned int seed)
89{
90	int i;
91	if (seed == 0) {
92		struct timeval tp;
93		struct timezone tzp;
94		gettimeofday(&tp, &tzp);
95		// ignore overflow
96		seed = (999*tp.tv_sec) + (1001*tp.tv_usec) + (1003 * getpid());
97	}
98
99	a[0] += seed;
100	for (i = 1; i < VECTOR_SIZE; i++) {
101		seed = a[i-1]*1001 + seed*999;
102		a[i] += seed;
103	}
104
105	i1 = a[0] % VECTOR_SIZE;
106	i2 = (i1 + 24) % VECTOR_SIZE;
107}
108
109
110
111static float
112gauss_rand(float c, float A, float S)
113{
114	float y = (float) LRAND() / MAXRAND;
115	y = A * (1.0 - exp(-y * y * S)) / (1.0 - exp(-S));
116	if (NRAND(2))
117		return (c + y);
118
119	return (c - y);
120}
121
122
123static float
124half_gauss_rand(float c, float A, float S)
125{
126	float y = (float) LRAND() / MAXRAND;
127	y = A * (1.0 - exp(-y * y * S)) / (1.0 - exp(-S));
128
129	return (c + y);
130}
131
132
133inline void
134transform(SIMILITUDE* Similitude, int32 xo, int32 yo, int32* x, int32* y)
135{
136	int32 xx;
137	int32 yy;
138
139	xo = xo - Similitude->Cx;
140	xo = (xo * Similitude->R) / UNIT;
141	yo = yo - Similitude->Cy;
142	yo = (yo * Similitude->R) / UNIT;
143
144	xx = xo - Similitude->Cx;
145	xx = (xx * Similitude->R2) / UNIT;
146	yy = -yo - Similitude->Cy;
147	yy = (yy * Similitude->R2) / UNIT;
148
149	*x = ((xo * Similitude->Ct - yo * Similitude->St + xx * Similitude->Ct2
150		- yy * Similitude->St2) / UNIT) + Similitude->Cx;
151	*y = ((xo * Similitude->St + yo * Similitude->Ct + xx * Similitude->St2
152		+ yy * Similitude->Ct2) / UNIT) + Similitude->Cy;
153}
154
155
156
157IFS::IFS(BRect bounds)
158	:
159	fRoot(NULL),
160	fCurrentFractal(NULL),
161	fPointBuffer(NULL),
162	fCurrentPoint(0),
163	fAdditive(false),
164	fCurrentMarkValue(1)
165{
166	if (!bounds.IsValid())
167		return;
168
169	ya_rand_init(system_time());
170
171	int i;
172	FRACTAL* Fractal;
173
174	if (fRoot == NULL) {
175		fRoot = (FRACTAL*)calloc(1, sizeof(FRACTAL));
176		if (fRoot == NULL)
177			return;
178	}
179	Fractal = fRoot;
180
181	_FreeBuffers(Fractal);
182	i = (NRAND(4)) + 2;
183		// Number of centers
184	switch (i) {
185		case 2:
186		default:
187			Fractal->Depth = fAdditive ? MAX_DEPTH_2 + 1 : MAX_DEPTH_2;
188			Fractal->r_mean = 0.7;
189			Fractal->dr_mean = 0.3;
190			Fractal->dr2_mean = 0.4;
191			break;
192
193		case 3:
194			Fractal->Depth = fAdditive ? MAX_DEPTH_3 + 1 : MAX_DEPTH_3;
195			Fractal->r_mean = 0.6;
196			Fractal->dr_mean = 0.4;
197			Fractal->dr2_mean = 0.3;
198			break;
199
200		case 4:
201			Fractal->Depth = MAX_DEPTH_4;
202			Fractal->r_mean = 0.5;
203			Fractal->dr_mean = 0.4;
204			Fractal->dr2_mean = 0.3;
205			break;
206
207		case 5:
208			Fractal->Depth = MAX_DEPTH_5;
209			Fractal->r_mean = 0.5;
210			Fractal->dr_mean = 0.4;
211			Fractal->dr2_mean = 0.3;
212			break;
213	}
214
215	Fractal->SimilitudeCount = i;
216	Fractal->MaxPoint = Fractal->SimilitudeCount - 1;
217	for (i = 0; i <= Fractal->Depth + 2; ++i)
218		Fractal->MaxPoint *= Fractal->SimilitudeCount;
219
220	if ((Fractal->buffer1 = (Point *)calloc(Fractal->MaxPoint,
221			sizeof(Point))) == NULL) {
222		_FreeIFS(Fractal);
223		return;
224	}
225	if ((Fractal->buffer2 = (Point *)calloc(Fractal->MaxPoint,
226			sizeof(Point))) == NULL) {
227		_FreeIFS(Fractal);
228		return;
229	}
230	Fractal->Speed = 6;
231#if HALF
232	Fractal->Width = bounds.IntegerWidth() / 2 + 1;
233	Fractal->Height = bounds.IntegerHeight() / 2 + 1;
234#else
235	Fractal->Width = bounds.IntegerWidth() + 1;
236	Fractal->Height = bounds.IntegerHeight() + 1;
237#endif
238	Fractal->CurrentPoint = 0;
239	Fractal->Count = 0;
240	Fractal->Lx = (Fractal->Width - 1) / 2;
241	Fractal->Ly = (Fractal->Height - 1) / 2;
242	Fractal->Col = NRAND(Fractal->Width * Fractal->Height - 1) + 1;
243
244	_RandomSimilitudes(Fractal, Fractal->Components, 5 * MAX_SIMILITUDE);
245
246	delete Fractal->bitmap;
247	Fractal->bitmap = new BBitmap(BRect(0.0, 0.0,
248		Fractal->Width - 1, Fractal->Height - 1), 0, B_RGB32);
249	delete Fractal->markBitmap;
250	Fractal->markBitmap = new BBitmap(BRect(0.0, 0.0,
251		Fractal->Width - 1, Fractal->Height - 1), 0, B_GRAY8);
252
253	// allocation checked
254	if (Fractal->bitmap != NULL && Fractal->bitmap->IsValid())
255		memset(Fractal->bitmap->Bits(), 0, Fractal->bitmap->BitsLength());
256	else {
257		delete Fractal->bitmap;
258		Fractal->bitmap = NULL;
259	}
260
261	if (Fractal->markBitmap != NULL && Fractal->markBitmap->IsValid()) {
262		memset(Fractal->markBitmap->Bits(), 0,
263			Fractal->markBitmap->BitsLength());
264	} else {
265		delete Fractal->markBitmap;
266		Fractal->markBitmap = NULL;
267	}
268}
269
270
271IFS::~IFS()
272{
273	if (fRoot != NULL) {
274		_FreeIFS(fRoot);
275		free((void*)fRoot);
276	}
277}
278
279
280void
281IFS::Draw(BView* view, const buffer_info* info, int32 frames)
282{
283	int i;
284	float u;
285	float uu;
286	float v;
287	float vv;
288	float u0;
289	float u1;
290	float u2;
291	float u3;
292	SIMILITUDE* S;
293	SIMILITUDE* S1;
294	SIMILITUDE* S2;
295	SIMILITUDE* S3;
296	SIMILITUDE* S4;
297	FRACTAL* F;
298
299	if (fRoot == NULL)
300		return;
301
302	F = fRoot;
303	if (F->buffer1 == NULL)
304		return;
305
306	// do this as many times as necessary to calculate the missing frames
307	// so the animation doesn't jerk when we miss a few frames
308	for (int32 frame = 0; frame < frames; frame++) {
309		u = (float) (F->Count) * (float) (F->Speed) / 1000.0;
310		uu = u * u;
311		v = 1.0 - u;
312		vv = v * v;
313		u0 = vv * v;
314		u1 = 3.0 * vv * u;
315		u2 = 3.0 * v * uu;
316		u3 = u * uu;
317
318		S = F->Components;
319		S1 = S + F->SimilitudeCount;
320		S2 = S1 + F->SimilitudeCount;
321		S3 = S2 + F->SimilitudeCount;
322		S4 = S3 + F->SimilitudeCount;
323
324		for (i = F->SimilitudeCount; i; --i, S++, S1++, S2++, S3++, S4++) {
325			S->c_x = u0 * S1->c_x + u1 * S2->c_x + u2 * S3->c_x + u3 * S4->c_x;
326			S->c_y = u0 * S1->c_y + u1 * S2->c_y + u2 * S3->c_y + u3 * S4->c_y;
327			S->r = u0 * S1->r + u1 * S2->r + u2 * S3->r + u3 * S4->r;
328			S->r2 = u0 * S1->r2 + u1 * S2->r2 + u2 * S3->r2 + u3 * S4->r2;
329			S->A = u0 * S1->A + u1 * S2->A + u2 * S3->A + u3 * S4->A;
330			S->A2 = u0 * S1->A2 + u1 * S2->A2 + u2 * S3->A2 + u3 * S4->A2;
331		}
332
333		if (frame == frames - 1)
334			_DrawFractal(view, info);
335
336		if (F->Count >= 1000 / F->Speed) {
337			S = F->Components;
338			S1 = S + F->SimilitudeCount;
339			S2 = S1 + F->SimilitudeCount;
340			S3 = S2 + F->SimilitudeCount;
341			S4 = S3 + F->SimilitudeCount;
342
343			for (i = F->SimilitudeCount; i; --i, S++, S1++, S2++, S3++, S4++) {
344				S2->c_x = 2.0 * S4->c_x - S3->c_x;
345				S2->c_y = 2.0 * S4->c_y - S3->c_y;
346				S2->r = 2.0 * S4->r - S3->r;
347				S2->r2 = 2.0 * S4->r2 - S3->r2;
348				S2->A = 2.0 * S4->A - S3->A;
349				S2->A2 = 2.0 * S4->A2 - S3->A2;
350
351				*S1 = *S4;
352			}
353			_RandomSimilitudes(F, F->Components + 3 * F->SimilitudeCount,
354				F->SimilitudeCount);
355			_RandomSimilitudes(F, F->Components + 4 * F->SimilitudeCount,
356				F->SimilitudeCount);
357
358			F->Count = 0;
359		} else
360			F->Count++;
361	}
362}
363
364
365void
366IFS::SetAdditive(bool additive)
367{
368	fAdditive = additive;
369}
370
371
372void
373IFS::SetSpeed(int32 speed)
374{
375	if (fRoot && speed > 0 && speed <= 12)
376		fRoot->Speed = speed;
377}
378
379
380void
381IFS::_DrawFractal(BView* view, const buffer_info* info)
382{
383	FRACTAL* F = fRoot;
384	int i;
385	int j;
386	int32 x;
387	int32 y;
388	int32 xo;
389	int32 yo;
390	SIMILITUDE* Current;
391	SIMILITUDE* Similitude;
392
393	for (Current = F->Components, i = F->SimilitudeCount; i; --i, Current++) {
394		Current->Cx = FLOAT_TO_INT(Current->c_x);
395		Current->Cy = FLOAT_TO_INT(Current->c_y);
396
397		Current->Ct = FLOAT_TO_INT(cos(Current->A));
398		Current->St = FLOAT_TO_INT(sin(Current->A));
399		Current->Ct2 = FLOAT_TO_INT(cos(Current->A2));
400		Current->St2 = FLOAT_TO_INT(sin(Current->A2));
401
402		Current->R = FLOAT_TO_INT(Current->r);
403		Current->R2 = FLOAT_TO_INT(Current->r2);
404	}
405
406	fCurrentPoint = 0;
407	fCurrentFractal = F;
408	fPointBuffer = F->buffer2;
409	for (Current = F->Components, i = F->SimilitudeCount; i; --i, Current++) {
410		xo = Current->Cx;
411		yo = Current->Cy;
412		for (Similitude = F->Components, j = F->SimilitudeCount; j;
413				--j, Similitude++) {
414			if (Similitude == Current)
415				continue;
416
417			transform(Similitude, xo, yo, &x, &y);
418			_Trace(F, x, y);
419		}
420	}
421
422	if (F->bitmap != NULL && F->markBitmap != NULL) {
423		uint8* bits = (uint8*)F->bitmap->Bits();
424		uint32 bpr = F->bitmap->BytesPerRow();
425		uint8* markBits = (uint8*)F->markBitmap->Bits();
426		uint32 markBPR = F->markBitmap->BytesPerRow();
427		int32 minX = F->Width;
428		int32 minY = F->Height;
429		int32 maxX = 0;
430		int32 maxY = 0;
431
432		// Erase previous dots from bitmap,
433		// but only if we're not in BDirectWindow mode,
434		// since the dots will have been erased already
435		if (info == NULL) {
436			if (F->CurrentPoint) {
437				for (int32 i = 0; i <  F->CurrentPoint; i++) {
438					Point p = F->buffer1[i];
439					if (p.x >= 0 && p.x < F->Width
440						&& p.y >= 0 && p.y < F->Height) {
441						int32 offset = bpr * p.y + p.x * 4;
442						*(uint32*)&bits[offset] = 0;
443						if (minX > p.x)
444							minX = p.x;
445
446						if (minY > p.y)
447							minY = p.y;
448
449						if (maxX < p.x)
450							maxX = p.x;
451
452						if (maxY < p.y)
453							maxY = p.y;
454					}
455				}
456			}
457		}
458
459		// draw the new dots into the bitmap
460		if (fCurrentPoint != 0) {
461			if (info != NULL) {
462				for (int32 i = 0; i <  fCurrentPoint; i++) {
463					Point p = F->buffer2[i];
464					if (p.x >= 0 && p.x < F->Width
465						&& p.y >= 0 && p.y < F->Height) {
466						int32 offset = bpr * p.y + p.x * 4;
467						if (fAdditive) {
468							if (bits[offset + 0] < 255) {
469								bits[offset + 0] += 51;
470								bits[offset + 1] += 51;
471								bits[offset + 2] += 51;
472							}
473						} else
474							*(uint32*)&bits[offset] = 0xffffffff;
475					}
476				}
477			} else {
478				// in this version, remember the bounds rectangle
479				for (int32 i = 0; i < fCurrentPoint; i++) {
480					Point p = F->buffer2[i];
481					if (p.x >= 0 && p.x < F->Width
482						&& p.y >= 0 && p.y < F->Height) {
483						int32 offset = bpr * p.y + p.x * 4;
484						if (fAdditive) {
485							if (bits[offset + 0] < 255) {
486								bits[offset + 0] += 15;
487								bits[offset + 1] += 15;
488								bits[offset + 2] += 15;
489							}
490						} else
491							*(uint32*)&bits[offset] = 0xffffffff;
492
493						if (minX > p.x)
494							minX = p.x;
495
496						if (minY > p.y)
497							minY = p.y;
498
499						if (maxX < p.x)
500							maxX = p.x;
501
502						if (maxY < p.y)
503							maxY = p.y;
504					}
505				}
506			}
507		}
508
509		if (info != NULL && info->bits != NULL) {
510			uint8* screenBits = (uint8*)info->bits;
511			uint32 screenBPR = info->bytesPerRow;
512			int32 left = info->bounds.left;
513			int32 top = info->bounds.top;
514			int32 bpp = info->bits_per_pixel;
515			screenBits += left * bpp + top * bpr;
516
517			int32 screenWidth = info->bounds.right - left;
518			int32 screenHeight = info->bounds.bottom - top;
519
520			// redraw the previous points on screen
521			// with the contents of the current bitmap
522			//
523			// draw the new points, erasing the bitmap as we go
524			int32 maxPoints = max_c(F->CurrentPoint, fCurrentPoint);
525			if (maxPoints > 0) {
526				for (int32 i = 0; i < maxPoints; i++) {
527					// copy previous points (black)
528					if (i < F->CurrentPoint) {
529						Point p = F->buffer1[i];
530						if (p.x >= 0 && p.x < F->Width && p.x < screenWidth
531							&& p.y >= 0 && p.y < F->Height
532							&& p.y < screenHeight) {
533							int32 markOffset = markBPR * p.y + p.x;
534							if (markBits[markOffset] != fCurrentMarkValue) {
535								int32 offset = bpr * p.y + p.x * 4;
536								// copy the pixel to the screen
537								uint32* src = (uint32*)&bits[offset];
538								if (bpp == 32) {
539									int32 screenOffset = screenBPR * p.y
540										+ p.x * 4;
541									*(uint32*)&screenBits[screenOffset] = *src;
542								} else if (bpp == 16) {
543									int32 screenOffset = screenBPR * p.y
544										+ p.x * 2;
545									*(uint16*)&screenBits[screenOffset] =
546										(uint16)(((bits[offset + 2] & 0xf8)
547											<< 8)
548										| ((bits[offset + 1] & 0xfc) << 3)
549										| (bits[offset] >> 3));
550								} else if (bpp == 15) {
551									int32 screenOffset = screenBPR * p.y
552										+ p.x * 2;
553									*(uint16*)&screenBits[screenOffset] =
554										(uint16)(((bits[offset + 2] & 0xf8)
555											<< 7)
556										| ((bits[offset + 1] & 0xf8) << 2)
557										| (bits[offset] >> 3));
558								} else if (bpp == 8) {
559									int32 screenOffset = screenBPR * p.y + p.x;
560									screenBits[screenOffset] = bits[offset];
561								}
562								*src = 0;
563								markBits[markOffset] = fCurrentMarkValue;
564							}
565							// else it means the pixel has been copied already
566						}
567					}
568
569					// copy current points (white) and erase them from the
570					// bitmap
571					if (i < fCurrentPoint) {
572						Point p = F->buffer2[i];
573						if (p.x >= 0 && p.x < F->Width && p.x < screenWidth
574							&& p.y >= 0 && p.y < F->Height
575							&& p.y < screenHeight) {
576							int32 markOffset = markBPR * p.y + p.x;
577							int32 offset = bpr * p.y + p.x * 4;
578
579							// copy the pixel to the screen
580							uint32* src = (uint32*)&bits[offset];
581							if (markBits[markOffset] != fCurrentMarkValue) {
582								if (bpp == 32) {
583									int32 screenOffset = screenBPR * p.y
584										+ p.x * 4;
585									*(uint32*)&screenBits[screenOffset] = *src;
586								} else if (bpp == 16) {
587									int32 screenOffset = screenBPR * p.y
588										+ p.x * 2;
589									*(uint16*)&screenBits[screenOffset] =
590										(uint16)(((bits[offset + 2] & 0xf8)
591											<< 8)
592										| ((bits[offset + 1] & 0xfc) << 3)
593										| (bits[offset] >> 3));
594								} else if (bpp == 15) {
595									int32 screenOffset = screenBPR * p.y
596										+ p.x * 2;
597									*(uint16*)&screenBits[screenOffset] =
598										(uint16)(((bits[offset + 2] & 0xf8)
599											<< 7)
600										| ((bits[offset + 1] & 0xf8) << 2)
601										| (bits[offset] >> 3));
602								} else if (bpp == 1) {
603									int32 screenOffset = screenBPR * p.y + p.x;
604									screenBits[screenOffset] = bits[offset];
605								}
606								markBits[markOffset] = fCurrentMarkValue;
607							}
608							// else it means the pixel has been copied already
609							*src = 0;
610						}
611					}
612				}
613			}
614		} else {
615			// if not in BDirectWindow mode, draw the bitmap
616			BRect b(minX, minY, maxX, maxY);
617			view->DrawBitmapAsync(F->bitmap, b, b);
618		}
619	}
620
621	// flip buffers
622	F->CurrentPoint = fCurrentPoint;
623	fPointBuffer = F->buffer1;
624	F->buffer1 = F->buffer2;
625	F->buffer2 = fPointBuffer;
626
627	if (fCurrentMarkValue == 255)
628		fCurrentMarkValue = 0;
629	else
630		fCurrentMarkValue++;
631}
632
633
634void
635IFS::_Trace(FRACTAL* F, int32 xo, int32 yo)
636{
637	int32 x;
638	int32 y;
639	SIMILITUDE* Current;
640
641	Current = fCurrentFractal->Components;
642	for (int32 i = fCurrentFractal->SimilitudeCount; i; --i, Current++) {
643		transform(Current, xo, yo, &x, &y);
644		fPointBuffer->x = (UNIT * 2 + x) * F->Lx / (UNIT * 2);
645		fPointBuffer->y = (UNIT * 2 - y) * F->Ly / (UNIT * 2);
646		fPointBuffer++;
647		fCurrentPoint++;
648
649		if (F->Depth && ((x - xo) >> 4) && ((y - yo) >> 4)) {
650			F->Depth--;
651			_Trace(F, x, y);
652			F->Depth++;
653		}
654	}
655}
656
657
658void
659IFS::_RandomSimilitudes(FRACTAL* fractal, SIMILITUDE* current, int i) const
660{
661	while (i-- > 0) {
662		current->c_x = gauss_rand(0.0, .8, 4.0);
663		current->c_y = gauss_rand(0.0, .8, 4.0);
664		current->r   = gauss_rand(fractal->r_mean, fractal->dr_mean, 3.0);
665		current->r2  = half_gauss_rand(0.0,fractal->dr2_mean, 2.0);
666		current->A   = gauss_rand(0.0, 360.0, 4.0) * (M_PI / 180.0);
667		current->A2  = gauss_rand(0.0, 360.0, 4.0) * (M_PI / 180.0);
668		current++;
669	}
670}
671
672
673void
674IFS::_FreeBuffers(FRACTAL* f)
675{
676	if (f->buffer1) {
677		free((void*)f->buffer1);
678		f->buffer1 = (Point*)NULL;
679	}
680
681	if (f->buffer2) {
682		free((void*)f->buffer2);
683		f->buffer2 = (Point*)NULL;
684	}
685}
686
687
688void
689IFS::_FreeIFS(FRACTAL* f)
690{
691	_FreeBuffers(f);
692	delete f->bitmap;
693	f->bitmap = NULL;
694	delete f->markBitmap;
695	f->markBitmap = NULL;
696}
697