//
// Perlin noise generator
//

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>

#define B 0x100
#define BM 0xff

#define N 0x1000
#define NP 12   /* 2^N */
#define NM 0xfff

static int p[B + B + 2];
static float g2[B + B + 2][2];
static int start = 1;

static void init(void);

#define s_curve(t) ( t * t * (3. - 2. * t) )

#define lerp(t, a, b) ( a + t * (b - a) )

#define setup(i,b0,b1,r0,r1)\
	t = vec[i] + N;\
	b0 = ((int)t) & BM;\
	b1 = (b0+1) & BM;\
	r0 = t - (int)t;\
	r1 = r0 - 1.;

float noise2(float vec[2])
{
	int bx0, bx1, by0, by1, b00, b10, b01, b11;
	float rx0, rx1, ry0, ry1, *q, sx, sy, a, b, t, u, v;
	register int i, j;

	if (start) {
		start = 0;
		init();
	}

	setup(0, bx0,bx1, rx0,rx1);
	setup(1, by0,by1, ry0,ry1);

	i = p[ bx0 ];
	j = p[ bx1 ];

	b00 = p[ i + by0 ];
	b10 = p[ j + by0 ];
	b01 = p[ i + by1 ];
	b11 = p[ j + by1 ];

	sx = s_curve(rx0);
	sy = s_curve(ry0);

#define at2(rx,ry) ( rx * q[0] + ry * q[1] )

	q = g2[ b00 ] ; u = at2(rx0,ry0);
	q = g2[ b10 ] ; v = at2(rx1,ry0);
	a = lerp(sx, u, v);

	q = g2[ b01 ] ; u = at2(rx0,ry1);
	q = g2[ b11 ] ; v = at2(rx1,ry1);
	b = lerp(sx, u, v);

	return lerp(sy, a, b);
}

static void normalize2(float v[2])
{
	float s;

	s = sqrt(v[0] * v[0] + v[1] * v[1]);
	v[0] = v[0] / s;
	v[1] = v[1] / s;
}

static int randomize(void) {
	static unsigned int seed = 0;

	if (seed == 0) {
		seed = time(NULL);
		srand(seed);
	}

	return rand();
}

static void init(void)
{
	int i, j, k;

	for (i = 0 ; i < B ; i++) {
		p[i] = i;

		for (j = 0 ; j < 2 ; j++)
			g2[i][j] = (float)((randomize() % (B + B)) - B) / B;
		normalize2(g2[i]);
	}

	while (--i) {
		k = p[i];
		p[i] = p[j = randomize() % B];
		p[j] = k;
	}

	for (i = 0 ; i < B + 2 ; i++) {
		p[B + i] = p[i];
		for (j = 0 ; j < 2 ; j++)
			g2[B + i][j] = g2[i][j];
	}
}

//
// Display code (allegro)
//

#include <allegro5/allegro.h>

#define fatal_error(str)  { fputs(str, stderr); goto errquit; }

int main(int argc, char **argv) {
	ALLEGRO_DISPLAY *display = NULL;
	ALLEGRO_BITMAP *bmp = NULL;
	int x, y;
	float vec[2];
	float noise;

	if (!al_init())	fatal_error("failed to initialize allegro!");

	display = al_create_display(800, 600);
	if (!display) fatal_error("failed to create display!");
	al_set_window_title(display, "Allegro Perlin Display");

	bmp = al_create_bitmap(80, 60);
	al_lock_bitmap(bmp, ALLEGRO_PIXEL_FORMAT_ANY, ALLEGRO_LOCK_WRITEONLY);
	al_set_target_bitmap(bmp);

	// Begin Perlin usage
	for(x = 0; x<80; x++) {
		for(y = 0; y<60; y++) {
			vec[0] = (x+.5)/5.;
			vec[1] = (y+.5)/5.;
			noise = (noise2(vec) + 1) / 2.;
			al_put_pixel(x, y, al_map_rgb_f(noise, noise, noise));
		}
	}
	// End Perlin usage

	al_set_target_bitmap(al_get_backbuffer(display));
	al_unlock_bitmap(bmp);

	al_draw_scaled_bitmap(bmp,    0, 0,    80, 60,    0, 0,    800, 600,    0);

	al_flip_display();
	al_rest(10.);

	al_destroy_display(display);

	return 0;

errquit:
	return -1;
}