понеділок, 22 травня 2017 р.

Чи потрібен Вам VPN?

Як переконатися в тому, що вашій компанії необхідний VPN? Чи дійсно VPN зможе допомогти бізнесу розширитись? Хоча постійно розмовляють про вигоду, яку дають організація технології VPN, існують лише певні області і засоби, де ці технології можуть бути корисними.
Області, де технологія VPN вигідна:
■         Доступ віддаленого користувача
■         Додатки екстранет
■         Міжнародні вузли

■         Різноманітні географічні бази користувачів
■         Підтримка різноманітних географічних баз користувачів
■         Недорогі ринкові розширення
■         Помірні вимоги до полоси пропускання
■         Необхідність в глобальному оступі з низькою вартістю
■         Аутосорсинг комутованого доступу
■         Віртуальні орендовані лінії
Існують також області, де технологія VPN не підходить. Це внутрішня інфраструктура компанії і деякі спеціальні вимоги.
Технологія VPN не підходить:
■         Коли надзвичайно важлива продуктивність
■         Коли затримка по часу не допустима
■         Коли використовуються нестандартні протоколи, які неможливо інкапсулювати в власний протокол інтернету (IP)
■         Коли використовується ізохронний трафік, наприклад телефон

Що таке VPN

Віртуальні приватні мережі (VPN, Virtual Private Network) - це одна з тих технологій, про які не відомо, звідки вони з'явилися. Однак, коли такі технології вкорінюються в інфраструктурі компанії, всі дивуються, як раніше обходилися без них. Еверет М. Роджерс, якого багато визнають батьком теорії поширення, в роботі "Поширення нововведень" обгрунтував природу цього процесу. Хоча в цій галузі було багато значних досліджень, робота вважається фундаментальною.
У ній доктор Роджерс визначає поширення в такий спосіб: Поширення є процесом, в ході якого нововведення розходиться по певних каналах протягом деякого часу серед членів соціальної системи. Ключовим словом тут є "нововведення", описане Роджерсом, як ідея, практика або об'єкт, які сприймаються як нові окремою людиною або якимось пристроєм.
Саме це поняття - "сприймається як новий" - дає нововведенню право на життя. Прикладом може служити метод-шифрування PGP (Pretty Good Privacy, "досить хороша секретність") Філа Ціммермана. PGP був доступний, але, завдяки Філу Ціммерманну, одному з лідерів технології шифрування, він став широко визнаним - навіть деякою різновидом фактичного стандарту. Віртуальні приватні мережі належать тій же категорії, що і PGP. Технологія VPN не є новою технологією, але сприймають люди. Технологія VPN існує протягом деякого часу, проте її важко зрозуміти, спроектувати і реалізувати. Причина цього - відсутність чіткої інформації про всі частини, які, доповнюючи один одного, забезпечують роботу віртуальних приватних мереж. Щоб зрозуміти технологію VPN, перш за все слід усвідомити, що це інфраструктура, а не сутність сама по собі. PGP є інфраструктурою для RSA, IDEA, MD5 і для генераторів випадкових чисел. VPN є інфраструктурою, де шифрування, аутентифікація і секретність можуть співіснувати і діяти. Віртуальні приватні мережі дозволяють вам використовувати Інтернет як нашу власну приватну мережу. Ця технологія важка для розуміння перш за все через її багатогранності. Вона включає в себе такі аспекти, як шифрування, служби аутентифікації, розміри ключів, криптографію і ступінь захищеності. Безпека є найважливішою частиною даної технології. Технологія VPN змінює правила, коли справа стосується безпеки вашої компанії. Безпека стає новою моделлю, де не підходить традиційне мислення. Зазвичай компанії намагаються захистити свою мережу від хакерів і споруджують деяку різновид стіни, наприклад брандмауер, який не дозволяє проникнути в мережу стороннім. При наявності VPN компанія може передавати дані в Інтернет і сподіватися, що ніхто не зможе їх змінити. Відкриваючи вхід в свою мережу (наприклад, поштовий трафік), можна припустити, що ніхто не зможе увійти в неї через цей вхід без правильної авторизації.

Питання реалізації VPN зрозумілі, якщо відомі базові принципи створення мереж взагалі. Щоб зрозуміти питання, пов'язані з безпекою VPN, буде потрібно багато часу. Ви повинні бути в курсі всіх розробок. Технології VPN використовують шифрування, а шифрування, на думку уряду, вважається зброєю, таким же, як танки і бойові літаки. Зараз уряди регламентують питання шифрування, а це означає, що ваша технологія VPN, яка спирається на шифрування для безпеки, регламентується урядом. Зазвичай урядові чиновники не люблять людей, які використовують шифрування, так як вони (чиновники) не можуть прочитати зашифровані дані. Тому вони забороняють застосування потужних засобів шифрування. Однак відсутність шифрування дозволить зловмисникам скористатися секретними даними.

середа, 18 травня 2016 р.

Багато літачків з OpenGL

Усього лише багато літачків реалізованих на основі функціоналу OpenGL - добавляйте та віднімайте їх в своє задоволення.









Source code: glutplane.c.


/* Copyright (c) Mark J. Kilgard, 1994. */

/* This program is freely distributable without licensing fees
and is provided without guarantee or warrantee expressed or
implied. This program is -not- in the public domain. */

#include <stdlib.h>
#include <stdio.h>
#ifndef WIN32
#include <unistd.h>
#else
#define random rand
#define srandom srand
#endif
#include <math.h>
#include <GL/glut.h>

/* Some <math.h> files do not define M_PI... */
#ifndef M_PI
#define M_PI 3.14159265
#endif
#ifndef M_PI_2
#define M_PI_2 1.57079632
#endif

GLboolean moving = GL_FALSE;

#define MAX_PLANES 15

struct {
float speed; /* zero speed means not flying */
GLfloat red, green, blue;
float theta;
float x, y, z, angle;
} planes[MAX_PLANES];

#define v3f glVertex3f /* v3f was the short IRIS GL name for
glVertex3f */

void
draw(void)
{
GLfloat red, green, blue;
int i;

glClear(GL_DEPTH_BUFFER_BIT);
/* paint black to blue smooth shaded polygon for background */
glDisable(GL_DEPTH_TEST);
glShadeModel(GL_SMOOTH);
glBegin(GL_POLYGON);
glColor3f(0.0, 0.0, 0.0);
v3f(-20, 20, -19);
v3f(20, 20, -19);
glColor3f(0.0, 0.0, 1.0);
v3f(20, -20, -19);
v3f(-20, -20, -19);
glEnd();
/* paint planes */
glEnable(GL_DEPTH_TEST);
glShadeModel(GL_FLAT);
for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed != 0.0) {
glPushMatrix();
glTranslatef(planes[i].x, planes[i].y, planes[i].z);
glRotatef(290.0, 1.0, 0.0, 0.0);
glRotatef(planes[i].angle, 0.0, 0.0, 1.0);
glScalef(1.0 / 3.0, 1.0 / 4.0, 1.0 / 4.0);
glTranslatef(0.0, -4.0, -1.5);
glBegin(GL_TRIANGLE_STRIP);
/* left wing */
v3f(-7.0, 0.0, 2.0);
v3f(-1.0, 0.0, 3.0);
glColor3f(red = planes[i].red, green = planes[i].green,
blue = planes[i].blue);
v3f(-1.0, 7.0, 3.0);
/* left side */
glColor3f(0.6 * red, 0.6 * green, 0.6 * blue);
v3f(0.0, 0.0, 0.0);
v3f(0.0, 8.0, 0.0);
/* right side */
v3f(1.0, 0.0, 3.0);
v3f(1.0, 7.0, 3.0);
/* final tip of right wing */
glColor3f(red, green, blue);
v3f(7.0, 0.0, 2.0);
glEnd();
glPopMatrix();
}
glutSwapBuffers();
}

void
tick_per_plane(int i)
{
float theta = planes[i].theta += planes[i].speed;
planes[i].z = -9 + 4 * cos(theta);
planes[i].x = 4 * sin(2 * theta);
planes[i].y = sin(theta / 3.4) * 3;
planes[i].angle = ((atan(2.0) + M_PI_2) * sin(theta) - M_PI_2) * 180 / M_PI;
if (planes[i].speed < 0.0)
planes[i].angle += 180;
}

void
add_plane(void)
{
int i;

for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed == 0) {

#define SET_COLOR(r,g,b) \
planes[i].red=r; planes[i].green=g; planes[i].blue=b;

switch (random() % 6) {
case 0:
SET_COLOR(1.0, 0.0, 0.0); /* red */
break;
case 1:
SET_COLOR(1.0, 1.0, 1.0); /* white */
break;
case 2:
SET_COLOR(0.0, 1.0, 0.0); /* green */
break;
case 3:
SET_COLOR(1.0, 0.0, 1.0); /* magenta */
break;
case 4:
SET_COLOR(1.0, 1.0, 0.0); /* yellow */
break;
case 5:
SET_COLOR(0.0, 1.0, 1.0); /* cyan */
break;
}
planes[i].speed = ((float) (random() % 20)) * 0.001 + 0.02;
if (random() & 0x1)
planes[i].speed *= -1;
planes[i].theta = ((float) (random() % 257)) * 0.1111;
tick_per_plane(i);
if (!moving)
glutPostRedisplay();
return;
}
}

void
remove_plane(void)
{
int i;

for (i = MAX_PLANES - 1; i >= 0; i--)
if (planes[i].speed != 0) {
planes[i].speed = 0;
if (!moving)
glutPostRedisplay();
return;
}
}

void
tick(void)
{
int i;

for (i = 0; i < MAX_PLANES; i++)
if (planes[i].speed != 0.0)
tick_per_plane(i);
}

void
animate(void)
{
tick();
glutPostRedisplay();
}

void
visible(int state)
{
if (state == GLUT_VISIBLE) {
if (moving)
glutIdleFunc(animate);
} else {
if (moving)
glutIdleFunc(NULL);
}
}

/* ARGSUSED1 */
void
keyboard(unsigned char ch, int x, int y)
{
switch (ch) {
case ' ':
if (!moving) {
tick();
glutPostRedisplay();
}
break;
case 27: /* ESC */
exit(0);
break;
}
}

#define ADD_PLANE 1
#define REMOVE_PLANE 2
#define MOTION_ON 3
#define MOTION_OFF 4
#define QUIT 5

void
menu(int item)
{
switch (item) {
case ADD_PLANE:
add_plane();
break;
case REMOVE_PLANE:
remove_plane();
break;
case MOTION_ON:
moving = GL_TRUE;
glutChangeToMenuEntry(3, "Motion off", MOTION_OFF);
glutIdleFunc(animate);
break;
case MOTION_OFF:
moving = GL_FALSE;
glutChangeToMenuEntry(3, "Motion", MOTION_ON);
glutIdleFunc(NULL);
break;
case QUIT:
exit(0);
break;
}
}

int
main(int argc, char *argv[])
{
glutInit(&argc, argv);
/* use multisampling if available */
glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGB | GLUT_DEPTH | GLUT_MULTISAMPLE);
glutCreateWindow("glutplane");
glutDisplayFunc(draw);
glutKeyboardFunc(keyboard);
glutVisibilityFunc(visible);
glutCreateMenu(menu);
glutAddMenuEntry("Add plane", ADD_PLANE);
glutAddMenuEntry("Remove plane", REMOVE_PLANE);
glutAddMenuEntry("Motion", MOTION_ON);
glutAddMenuEntry("Quit", QUIT);
glutAttachMenu(GLUT_RIGHT_BUTTON);
/* setup OpenGL state */
glClearDepth(1.0);
glClearColor(0.0, 0.0, 0.0, 0.0);
glMatrixMode(GL_PROJECTION);
glFrustum(-1.0, 1.0, -1.0, 1.0, 1.0, 20);
glMatrixMode(GL_MODELVIEW);
/* add three initial random planes */
srandom(getpid());
add_plane();
add_plane();
add_plane();
/* start event processing */
glutMainLoop();
return 0; /* ANSI C requires main to return int. */
}

Snapshots: flying high (shown).

OpenGL 3D-головоломка.

3D-головоломка, яка може вирішитися автоматично на основі функціоналу OpenGL.







Source code: glpuzzle.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
#include <GL/glut.h>
#include "trackball.h"

#define WIDTH 4
#define HEIGHT 5
#define PIECES 10
#define OFFSETX -2
#define OFFSETY -2.5
#define OFFSETZ -0.5

typedef char Config[HEIGHT][WIDTH];

struct puzzle {
struct puzzle *backptr;
struct puzzle *solnptr;
Config pieces;
struct puzzle *next;
unsigned hashvalue;
};

#define HASHSIZE 10691

struct puzzlelist {
struct puzzle *puzzle;
struct puzzlelist *next;
};

static char convert[PIECES + 1] =
{0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 4};

static unsigned char colors[PIECES + 1][3] =
{
{0, 0, 0},
{255, 255, 127},
{255, 255, 127},
{255, 255, 127},
{255, 255, 127},
{255, 127, 255},
{255, 127, 255},
{255, 127, 255},
{255, 127, 255},
{255, 127, 127},
{255, 255, 255},
};

void changeState(void);

static struct puzzle *hashtable[HASHSIZE];
static struct puzzle *startPuzzle;
static struct puzzlelist *puzzles;
static struct puzzlelist *lastentry;

int curX, curY, visible;

#define MOVE_SPEED 0.2
static unsigned char movingPiece;
static float move_x, move_y;
static float curquat[4];
static int doubleBuffer = 1;
static int depth = 1;

static char xsize[PIECES + 1] =
{0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2};
static char ysize[PIECES + 1] =
{0, 1, 1, 1, 1, 2, 2, 2, 2, 1, 2};
static float zsize[PIECES + 1] =
{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.6};

static Config startConfig =
{
{8, 10, 10, 7},
{8, 10, 10, 7},
{6, 9, 9, 5},
{6, 4, 3, 5},
{2, 0, 0, 1}
};

static Config thePuzzle =
{
{8, 10, 10, 7},
{8, 10, 10, 7},
{6, 9, 9, 5},
{6, 4, 3, 5},
{2, 0, 0, 1}
};

static int xadds[4] =
{-1, 0, 1, 0};
static int yadds[4] =
{0, -1, 0, 1};

static int W = 400, H = 300;
static GLint viewport[4];

#define srandom srand
#define random() (rand() >> 2)

unsigned
hash(Config config)
{
int i, j, value;

value = 0;
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
value = value + convert[config[i][j]];
value *= 6;
}
}
return (value);
}

int
solution(Config config)
{
if (config[4][1] == 10 && config[4][2] == 10)
return (1);
return (0);
}

float boxcoords[][3] =
{
{0.2, 0.2, 0.9},
{0.8, 0.2, 0.9},
{0.8, 0.8, 0.9},
{0.2, 0.8, 0.9},
{0.2, 0.1, 0.8},
{0.8, 0.1, 0.8},
{0.9, 0.2, 0.8},
{0.9, 0.8, 0.8},
{0.8, 0.9, 0.8},
{0.2, 0.9, 0.8},
{0.1, 0.8, 0.8},
{0.1, 0.2, 0.8},
{0.2, 0.1, 0.2},
{0.8, 0.1, 0.2},
{0.9, 0.2, 0.2},
{0.9, 0.8, 0.2},
{0.8, 0.9, 0.2},
{0.2, 0.9, 0.2},
{0.1, 0.8, 0.2},
{0.1, 0.2, 0.2},
{0.2, 0.2, 0.1},
{0.8, 0.2, 0.1},
{0.8, 0.8, 0.1},
{0.2, 0.8, 0.1},
};

float boxnormals[][3] =
{
{0, 0, 1}, /* 0 */
{0, 1, 0},
{1, 0, 0},
{0, 0, -1},
{0, -1, 0},
{-1, 0, 0},
{0.7071, 0.7071, 0.0000}, /* 6 */
{0.7071, -0.7071, 0.0000},
{-0.7071, 0.7071, 0.0000},
{-0.7071, -0.7071, 0.0000},
{0.7071, 0.0000, 0.7071}, /* 10 */
{0.7071, 0.0000, -0.7071},
{-0.7071, 0.0000, 0.7071},
{-0.7071, 0.0000, -0.7071},
{0.0000, 0.7071, 0.7071}, /* 14 */
{0.0000, 0.7071, -0.7071},
{0.0000, -0.7071, 0.7071},
{0.0000, -0.7071, -0.7071},
{0.5774, 0.5774, 0.5774}, /* 18 */
{0.5774, 0.5774, -0.5774},
{0.5774, -0.5774, 0.5774},
{0.5774, -0.5774, -0.5774},
{-0.5774, 0.5774, 0.5774},
{-0.5774, 0.5774, -0.5774},
{-0.5774, -0.5774, 0.5774},
{-0.5774, -0.5774, -0.5774},
};

int boxfaces[][4] =
{
{0, 1, 2, 3}, /* 0 */
{9, 8, 16, 17},
{6, 14, 15, 7},
{20, 23, 22, 21},
{12, 13, 5, 4},
{19, 11, 10, 18},
{7, 15, 16, 8}, /* 6 */
{13, 14, 6, 5},
{18, 10, 9, 17},
{19, 12, 4, 11},
{1, 6, 7, 2}, /* 10 */
{14, 21, 22, 15},
{11, 0, 3, 10},
{20, 19, 18, 23},
{3, 2, 8, 9}, /* 14 */
{17, 16, 22, 23},
{4, 5, 1, 0},
{20, 21, 13, 12},
{2, 7, 8, -1}, /* 18 */
{16, 15, 22, -1},
{5, 6, 1, -1},
{13, 21, 14, -1},
{10, 3, 9, -1},
{18, 17, 23, -1},
{11, 4, 0, -1},
{20, 12, 19, -1},
};

#define NBOXFACES (sizeof(boxfaces)/sizeof(boxfaces[0]))

/* Draw a box. Bevel as desired. */
void
drawBox(int piece, float xoff, float yoff)
{
int xlen, ylen;
int i, k;
float x, y, z;
float zlen;
float *v;

xlen = xsize[piece];
ylen = ysize[piece];
zlen = zsize[piece];

glColor3ubv(colors[piece]);
glBegin(GL_QUADS);
for (i = 0; i < 18; i++) {
glNormal3fv(boxnormals[i]);
for (k = 0; k < 4; k++) {
if (boxfaces[i][k] == -1)
continue;
v = boxcoords[boxfaces[i][k]];
x = v[0] + OFFSETX;
if (v[0] > 0.5)
x += xlen - 1;
y = v[1] + OFFSETY;
if (v[1] > 0.5)
y += ylen - 1;
z = v[2] + OFFSETZ;
if (v[2] > 0.5)
z += zlen - 1;
glVertex3f(xoff + x, yoff + y, z);
}
}
glEnd();
glBegin(GL_TRIANGLES);
for (i = 18; i < NBOXFACES; i++) {
glNormal3fv(boxnormals[i]);
for (k = 0; k < 3; k++) {
if (boxfaces[i][k] == -1)
continue;
v = boxcoords[boxfaces[i][k]];
x = v[0] + OFFSETX;
if (v[0] > 0.5)
x += xlen - 1;
y = v[1] + OFFSETY;
if (v[1] > 0.5)
y += ylen - 1;
z = v[2] + OFFSETZ;
if (v[2] > 0.5)
z += zlen - 1;
glVertex3f(xoff + x, yoff + y, z);
}
}
glEnd();
}

float containercoords[][3] =
{
{-0.1, -0.1, 1.0},
{-0.1, -0.1, -0.1},
{4.1, -0.1, -0.1},
{4.1, -0.1, 1.0},
{1.0, -0.1, 0.6}, /* 4 */
{3.0, -0.1, 0.6},
{1.0, -0.1, 0.0},
{3.0, -0.1, 0.0},
{1.0, 0.0, 0.0}, /* 8 */
{3.0, 0.0, 0.0},
{3.0, 0.0, 0.6},
{1.0, 0.0, 0.6},
{0.0, 0.0, 1.0}, /* 12 */
{4.0, 0.0, 1.0},
{4.0, 0.0, 0.0},
{0.0, 0.0, 0.0},
{0.0, 5.0, 0.0}, /* 16 */
{0.0, 5.0, 1.0},
{4.0, 5.0, 1.0},
{4.0, 5.0, 0.0},
{-0.1, 5.1, -0.1}, /* 20 */
{4.1, 5.1, -0.1},
{4.1, 5.1, 1.0},
{-0.1, 5.1, 1.0},
};

float containernormals[][3] =
{
{0, -1, 0},
{0, -1, 0},
{0, -1, 0},
{0, -1, 0},
{0, -1, 0},
{0, 1, 0},
{0, 1, 0},
{0, 1, 0},
{1, 0, 0},
{1, 0, 0},
{1, 0, 0},
{-1, 0, 0},
{-1, 0, 0},
{-1, 0, 0},
{0, 1, 0},
{0, 0, -1},
{0, 0, -1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
{0, 0, 1},
};

int containerfaces[][4] =
{
{1, 6, 4, 0},
{0, 4, 5, 3},
{1, 2, 7, 6},
{7, 2, 3, 5},
{16, 19, 18, 17},

{23, 22, 21, 20},
{12, 11, 8, 15},
{10, 13, 14, 9},

{15, 16, 17, 12},
{2, 21, 22, 3},
{6, 8, 11, 4},

{1, 0, 23, 20},
{14, 13, 18, 19},
{9, 7, 5, 10},

{12, 13, 10, 11},

{1, 20, 21, 2},
{4, 11, 10, 5},

{15, 8, 19, 16},
{19, 8, 9, 14},
{8, 6, 7, 9},
{0, 3, 13, 12},
{13, 3, 22, 18},
{18, 22, 23, 17},
{17, 23, 0, 12},
};

#define NCONTFACES (sizeof(containerfaces)/sizeof(containerfaces[0]))

/* Draw the container */
void
drawContainer(void)
{
int i, k;
float *v;

/* Y is reversed here because the model has it reversed */

/* Arbitrary bright wood-like color */
glColor3ub(209, 103, 23);
glBegin(GL_QUADS);
for (i = 0; i < NCONTFACES; i++) {
v = containernormals[i];
glNormal3f(v[0], -v[1], v[2]);
for (k = 3; k >= 0; k--) {
v = containercoords[containerfaces[i][k]];
glVertex3f(v[0] + OFFSETX, -(v[1] + OFFSETY), v[2] + OFFSETZ);
}
}
glEnd();
}

void
drawAll(void)
{
int i, j;
int piece;
char done[PIECES + 1];
float m[4][4];

build_rotmatrix(m, curquat);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glTranslatef(0, 0, -10);
glMultMatrixf(&(m[0][0]));
glRotatef(180, 0, 0, 1);

if (depth) {
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
} else {
glClear(GL_COLOR_BUFFER_BIT);
}
for (i = 1; i <= PIECES; i++) {
done[i] = 0;
}
glLoadName(0);
drawContainer();
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
piece = thePuzzle[i][j];
if (piece == 0)
continue;
if (done[piece])
continue;
done[piece] = 1;
glLoadName(piece);
if (piece == movingPiece) {
drawBox(piece, move_x, move_y);
} else {
drawBox(piece, j, i);
}
}
}
}

void
redraw(void)
{
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPerspective(45, 1.0, 0.1, 100.0);

drawAll();

if (doubleBuffer)
glutSwapBuffers();
else
glFinish();
}

void
solidifyChain(struct puzzle *puzzle)
{
int i;
char buf[256];

i = 0;
while (puzzle->backptr) {
i++;
puzzle->backptr->solnptr = puzzle;
puzzle = puzzle->backptr;
}
sprintf(buf, "%d moves to complete!", i);
glutSetWindowTitle(buf);
}

int
addConfig(Config config, struct puzzle *back)
{
unsigned hashvalue;
struct puzzle *newpiece;
struct puzzlelist *newlistentry;

hashvalue = hash(config);

newpiece = hashtable[hashvalue % HASHSIZE];
while (newpiece != NULL) {
if (newpiece->hashvalue == hashvalue) {
int i, j;

for (i = 0; i < WIDTH; i++) {
for (j = 0; j < HEIGHT; j++) {
if (convert[config[j][i]] !=
convert[newpiece->pieces[j][i]])
goto nomatch;
}
}
return 0;
}
nomatch:
newpiece = newpiece->next;
}

newpiece = (struct puzzle *) malloc(sizeof(struct puzzle));
newpiece->next = hashtable[hashvalue % HASHSIZE];
newpiece->hashvalue = hashvalue;
memcpy(newpiece->pieces, config, HEIGHT * WIDTH);
newpiece->backptr = back;
newpiece->solnptr = NULL;
hashtable[hashvalue % HASHSIZE] = newpiece;

newlistentry = (struct puzzlelist *) malloc(sizeof(struct puzzlelist));
newlistentry->puzzle = newpiece;
newlistentry->next = NULL;

if (lastentry) {
lastentry->next = newlistentry;
} else {
puzzles = newlistentry;
}
lastentry = newlistentry;

if (back == NULL) {
startPuzzle = newpiece;
}
if (solution(config)) {
solidifyChain(newpiece);
return 1;
}
return 0;
}

/* Checks if a space can move */
int
canmove0(Config pieces, int x, int y, int dir, Config newpieces)
{
char piece;
int xadd, yadd;
int l, m;

xadd = xadds[dir];
yadd = yadds[dir];

if (x + xadd < 0 || x + xadd >= WIDTH ||
y + yadd < 0 || y + yadd >= HEIGHT)
return 0;
piece = pieces[y + yadd][x + xadd];
if (piece == 0)
return 0;
memcpy(newpieces, pieces, HEIGHT * WIDTH);
for (l = 0; l < WIDTH; l++) {
for (m = 0; m < HEIGHT; m++) {
if (newpieces[m][l] == piece)
newpieces[m][l] = 0;
}
}
xadd = -xadd;
yadd = -yadd;
for (l = 0; l < WIDTH; l++) {
for (m = 0; m < HEIGHT; m++) {
if (pieces[m][l] == piece) {
int newx, newy;

newx = l + xadd;
newy = m + yadd;
if (newx < 0 || newx >= WIDTH ||
newy < 0 || newy >= HEIGHT)
return 0;
if (newpieces[newy][newx] != 0)
return 0;
newpieces[newy][newx] = piece;
}
}
}
return 1;
}

/* Checks if a piece can move */
int
canmove(Config pieces, int x, int y, int dir, Config newpieces)
{
int xadd, yadd;

xadd = xadds[dir];
yadd = yadds[dir];

if (x + xadd < 0 || x + xadd >= WIDTH ||
y + yadd < 0 || y + yadd >= HEIGHT)
return 0;
if (pieces[y + yadd][x + xadd] == pieces[y][x]) {
return canmove(pieces, x + xadd, y + yadd, dir, newpieces);
}
if (pieces[y + yadd][x + xadd] != 0)
return 0;
return canmove0(pieces, x + xadd, y + yadd, (dir + 2) % 4, newpieces);
}

int
generateNewConfigs(struct puzzle *puzzle)
{
int i, j, k;
Config pieces;
Config newpieces;

memcpy(pieces, puzzle->pieces, HEIGHT * WIDTH);
for (i = 0; i < WIDTH; i++) {
for (j = 0; j < HEIGHT; j++) {
if (pieces[j][i] == 0) {
for (k = 0; k < 4; k++) {
if (canmove0(pieces, i, j, k, newpieces)) {
if (addConfig(newpieces, puzzle))
return 1;
}
}
}
}
}
return 0;
}

void
freeSolutions(void)
{
struct puzzlelist *nextpuz;
struct puzzle *puzzle, *next;
int i;

while (puzzles) {
nextpuz = puzzles->next;
free((char *) puzzles);
puzzles = nextpuz;
}
lastentry = NULL;
for (i = 0; i < HASHSIZE; i++) {
puzzle = hashtable[i];
hashtable[i] = NULL;
while (puzzle) {
next = puzzle->next;
free((char *) puzzle);
puzzle = next;
}
}
startPuzzle = NULL;
}

int
continueSolving(void)
{
struct puzzle *nextpuz;
int i, j;
int movedPiece;
int movedir;
int fromx, fromy;
int tox, toy;

if (startPuzzle == NULL)
return 0;
if (startPuzzle->solnptr == NULL) {
freeSolutions();
return 0;
}
nextpuz = startPuzzle->solnptr;
movedPiece = 0;
movedir = 0;
for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
if (startPuzzle->pieces[i][j] != nextpuz->pieces[i][j]) {
if (startPuzzle->pieces[i][j]) {
movedPiece = startPuzzle->pieces[i][j];
fromx = j;
fromy = i;
if (i < HEIGHT - 1 && nextpuz->pieces[i + 1][j] == movedPiece) {
movedir = 3;
} else {
movedir = 2;
}
goto found_piece;
} else {
movedPiece = nextpuz->pieces[i][j];
if (i < HEIGHT - 1 &&
startPuzzle->pieces[i + 1][j] == movedPiece) {
fromx = j;
fromy = i + 1;
movedir = 1;
} else {
fromx = j + 1;
fromy = i;
movedir = 0;
}
goto found_piece;
}
}
}
}
glutSetWindowTitle("What! No change?");
freeSolutions();
return 0;

found_piece:
if (!movingPiece) {
movingPiece = movedPiece;
move_x = fromx;
move_y = fromy;
}
move_x += xadds[movedir] * MOVE_SPEED;
move_y += yadds[movedir] * MOVE_SPEED;

tox = fromx + xadds[movedir];
toy = fromy + yadds[movedir];

if (move_x > tox - MOVE_SPEED / 2 && move_x < tox + MOVE_SPEED / 2 &&
move_y > toy - MOVE_SPEED / 2 && move_y < toy + MOVE_SPEED / 2) {
startPuzzle = nextpuz;
movingPiece = 0;
}
memcpy(thePuzzle, startPuzzle->pieces, HEIGHT * WIDTH);
changeState();
return 1;
}

int
solvePuzzle(void)
{
struct puzzlelist *nextpuz;
char buf[256];
int i;

if (solution(thePuzzle)) {
glutSetWindowTitle("Puzzle already solved!");
return 0;
}
addConfig(thePuzzle, NULL);
i = 0;

while (puzzles) {
i++;
if (generateNewConfigs(puzzles->puzzle))
break;
nextpuz = puzzles->next;
free((char *) puzzles);
puzzles = nextpuz;
}
if (puzzles == NULL) {
freeSolutions();
sprintf(buf, "I can't solve it! (%d positions examined)", i);
glutSetWindowTitle(buf);
return 1;
}
return 1;
}

int
selectPiece(int mousex, int mousey)
{
long hits;
GLuint selectBuf[1024];
GLuint closest;
GLuint dist;

glSelectBuffer(1024, selectBuf);
(void) glRenderMode(GL_SELECT);
glInitNames();

/* Because LoadName() won't work with no names on the stack */
glPushName(-1);

glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluPickMatrix(mousex, H - mousey, 4, 4, viewport);
gluPerspective(45, 1.0, 0.1, 100.0);

drawAll();

hits = glRenderMode(GL_RENDER);
if (hits <= 0) {
return 0;
}
closest = 0;
dist = 4294967295;
while (hits) {
if (selectBuf[(hits - 1) * 4 + 1] < dist) {
dist = selectBuf[(hits - 1) * 4 + 1];
closest = selectBuf[(hits - 1) * 4 + 3];
}
hits--;
}
return closest;
}

void
nukePiece(int piece)
{
int i, j;

for (i = 0; i < HEIGHT; i++) {
for (j = 0; j < WIDTH; j++) {
if (thePuzzle[i][j] == piece) {
thePuzzle[i][j] = 0;
}
}
}
}

void
multMatrices(const GLfloat a[16], const GLfloat b[16], GLfloat r[16])
{
int i, j;

for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
r[i * 4 + j] =
a[i * 4 + 0] * b[0 * 4 + j] +
a[i * 4 + 1] * b[1 * 4 + j] +
a[i * 4 + 2] * b[2 * 4 + j] +
a[i * 4 + 3] * b[3 * 4 + j];
}
}
}

void
makeIdentity(GLfloat m[16])
{
m[0 + 4 * 0] = 1;
m[0 + 4 * 1] = 0;
m[0 + 4 * 2] = 0;
m[0 + 4 * 3] = 0;
m[1 + 4 * 0] = 0;
m[1 + 4 * 1] = 1;
m[1 + 4 * 2] = 0;
m[1 + 4 * 3] = 0;
m[2 + 4 * 0] = 0;
m[2 + 4 * 1] = 0;
m[2 + 4 * 2] = 1;
m[2 + 4 * 3] = 0;
m[3 + 4 * 0] = 0;
m[3 + 4 * 1] = 0;
m[3 + 4 * 2] = 0;
m[3 + 4 * 3] = 1;
}

/*
** inverse = invert(src)
*/
int
invertMatrix(const GLfloat src[16], GLfloat inverse[16])
{
int i, j, k, swap;
double t;
GLfloat temp[4][4];

for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
temp[i][j] = src[i * 4 + j];
}
}
makeIdentity(inverse);

for (i = 0; i < 4; i++) {
/*
** Look for largest element in column */
swap = i;
for (j = i + 1; j < 4; j++) {
if (fabs(temp[j][i]) > fabs(temp[i][i])) {
swap = j;
}
}

if (swap != i) {
/*
** Swap rows. */
for (k = 0; k < 4; k++) {
t = temp[i][k];
temp[i][k] = temp[swap][k];
temp[swap][k] = t;

t = inverse[i * 4 + k];
inverse[i * 4 + k] = inverse[swap * 4 + k];
inverse[swap * 4 + k] = t;
}
}
if (temp[i][i] == 0) {
/*
** No non-zero pivot. The matrix is singular, which
shouldn't ** happen. This means the user gave us a
bad matrix. */
return 0;
}
t = temp[i][i];
for (k = 0; k < 4; k++) {
temp[i][k] /= t;
inverse[i * 4 + k] /= t;
}
for (j = 0; j < 4; j++) {
if (j != i) {
t = temp[j][i];
for (k = 0; k < 4; k++) {
temp[j][k] -= temp[i][k] * t;
inverse[j * 4 + k] -= inverse[i * 4 + k] * t;
}
}
}
}
return 1;
}

/*
** This is a screwball function. What it does is the following:
** Given screen x and y coordinates, compute the corresponding object space
** x and y coordinates given that the object space z is 0.9 + OFFSETZ.
** Since the tops of (most) pieces are at z = 0.9 + OFFSETZ, we use that
** number.
*/
int
computeCoords(int piece, int mousex, int mousey,
GLfloat * selx, GLfloat * sely)
{
GLfloat modelMatrix[16];
GLfloat projMatrix[16];
GLfloat finalMatrix[16];
GLfloat in[4];
GLfloat a, b, c, d;
GLfloat top, bot;
GLfloat z;
GLfloat w;
GLfloat height;

if (piece == 0)
return 0;
height = zsize[piece] - 0.1 + OFFSETZ;

glGetFloatv(GL_PROJECTION_MATRIX, projMatrix);
glGetFloatv(GL_MODELVIEW_MATRIX, modelMatrix);
multMatrices(modelMatrix, projMatrix, finalMatrix);
if (!invertMatrix(finalMatrix, finalMatrix))
return 0;

in[0] = (2.0 * (mousex - viewport[0]) / viewport[2]) - 1;
in[1] = (2.0 * ((H - mousey) - viewport[1]) / viewport[3]) - 1;

a = in[0] * finalMatrix[0 * 4 + 2] +
in[1] * finalMatrix[1 * 4 + 2] +
finalMatrix[3 * 4 + 2];
b = finalMatrix[2 * 4 + 2];
c = in[0] * finalMatrix[0 * 4 + 3] +
in[1] * finalMatrix[1 * 4 + 3] +
finalMatrix[3 * 4 + 3];
d = finalMatrix[2 * 4 + 3];

/*
** Ok, now we need to solve for z: ** (a + b z) / (c + d

z) = height. ** ("height" is the height in object space we

want to solve z for) ** ** ==> a + b z = height c +
height d z ** bz - height d z = height c - a ** z =
(height c - a) / (b - height d) */
top = height * c - a;
bot = b - height * d;
if (bot == 0.0)
return 0;

z = top / bot;

/*
** Ok, no problem. ** Now we solve for x and y. We know
that w = c + d z, so we compute it. */
w = c + d * z;

/*
** Now for x and y: */
*selx = (in[0] * finalMatrix[0 * 4 + 0] +
in[1] * finalMatrix[1 * 4 + 0] +
z * finalMatrix[2 * 4 + 0] +
finalMatrix[3 * 4 + 0]) / w - OFFSETX;
*sely = (in[0] * finalMatrix[0 * 4 + 1] +
in[1] * finalMatrix[1 * 4 + 1] +
z * finalMatrix[2 * 4 + 1] +
finalMatrix[3 * 4 + 1]) / w - OFFSETY;
return 1;
}

static int selected;
static int selectx, selecty;
static float selstartx, selstarty;

void
grabPiece(int piece, float selx, float sely)
{
int hit;

selectx = selx;
selecty = sely;
if (selectx < 0 || selecty < 0 || selectx >= WIDTH || selecty >= HEIGHT) {
return;
}
hit = thePuzzle[selecty][selectx];
if (hit != piece)
return;
if (hit) {
movingPiece = hit;
while (selectx > 0 && thePuzzle[selecty][selectx - 1] == movingPiece) {
selectx--;
}
while (selecty > 0 && thePuzzle[selecty - 1][selectx] == movingPiece) {
selecty--;
}
move_x = selectx;
move_y = selecty;
selected = 1;
selstartx = selx;
selstarty = sely;
} else {
selected = 0;
}
changeState();
}

void
moveSelection(float selx, float sely)
{
float deltax, deltay;
int dir;
Config newpieces;

if (!selected)
return;
deltax = selx - selstartx;
deltay = sely - selstarty;

if (fabs(deltax) > fabs(deltay)) {
deltay = 0;
if (deltax > 0) {
if (deltax > 1)
deltax = 1;
dir = 2;
} else {
if (deltax < -1)
deltax = -1;
dir = 0;
}
} else {
deltax = 0;
if (deltay > 0) {
if (deltay > 1)
deltay = 1;
dir = 3;
} else {
if (deltay < -1)
deltay = -1;
dir = 1;
}
}
if (canmove(thePuzzle, selectx, selecty, dir, newpieces)) {
move_x = deltax + selectx;
move_y = deltay + selecty;
if (deltax > 0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selectx++;
selstartx++;
} else if (deltax < -0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selectx--;
selstartx--;
} else if (deltay > 0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selecty++;
selstarty++;
} else if (deltay < -0.5) {
memcpy(thePuzzle, newpieces, HEIGHT * WIDTH);
selecty--;
selstarty--;
}
} else {
if (deltay > 0 && thePuzzle[selecty][selectx] == 10 &&
selectx == 1 && selecty == 3) {
/* Allow visual movement of solution piece outside of the

box */
move_x = selectx;
move_y = sely - selstarty + selecty;
} else {
move_x = selectx;
move_y = selecty;
}
}
}

void
dropSelection(void)
{
if (!selected)
return;
movingPiece = 0;
selected = 0;
changeState();
}

static int left_mouse, middle_mouse;
static int mousex, mousey;
static int solving;
static int spinning;
static float lastquat[4];
static int sel_piece;

static void
Reshape(int width, int height)
{

W = width;
H = height;
glViewport(0, 0, W, H);
glGetIntegerv(GL_VIEWPORT, viewport);
}

void
toggleSolve(void)
{
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
} else {
glutChangeToMenuEntry(1, "Stop solving", 1);
glutSetWindowTitle("Solving...");
if (solvePuzzle()) {
solving = 1;
}
}
changeState();
glutPostRedisplay();
}

void reset(void)
{
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
changeState();
}
memcpy(thePuzzle, startConfig, HEIGHT * WIDTH);
glutPostRedisplay();
}

void
keyboard(unsigned char c, int x, int y)
{
int piece;

switch (c) {
case 27:
exit(0);
break;
case 'D':
case 'd':
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
changeState();
}
piece = selectPiece(x, y);
if (piece) {
nukePiece(piece);
}
glutPostRedisplay();
break;
case 'R':
case 'r':
reset();
break;
case 'S':
case 's':
toggleSolve();
break;
case 'b':
case 'B':
depth = 1 - depth;
if (depth) {
glEnable(GL_DEPTH_TEST);
} else {
glDisable(GL_DEPTH_TEST);
}
glutPostRedisplay();
break;
default:
break;
}
}

void
motion(int x, int y)
{
float selx, sely;

if (middle_mouse && !left_mouse) {
if (mousex != x || mousey != y) {
trackball(lastquat,
(2.0*mousex - W) / W,
(H - 2.0*mousey) / H,
(2.0*x - W) / W,
(H - 2.0*y) / H);
spinning = 1;
} else {
spinning = 0;
}
changeState();
} else {
computeCoords(sel_piece, x, y, &selx, &sely);
moveSelection(selx, sely);
}
mousex = x;
mousey = y;
glutPostRedisplay();
}

void
mouse(int b, int s, int x, int y)
{
float selx, sely;

mousex = x;
mousey = y;
curX = x;
curY = y;
if (s == GLUT_DOWN) {
switch (b) {
case GLUT_LEFT_BUTTON:
if (solving) {
freeSolutions();
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
movingPiece = 0;
}
left_mouse = GL_TRUE;
sel_piece = selectPiece(mousex, mousey);
if (computeCoords(sel_piece, mousex, mousey, &selx, &sely)) {
grabPiece(sel_piece, selx, sely);
}
glutPostRedisplay();
break;
case GLUT_MIDDLE_BUTTON:
middle_mouse = GL_TRUE;
glutPostRedisplay();
break;
}
} else {
switch (b) {
case GLUT_LEFT_BUTTON:
left_mouse = GL_FALSE;
dropSelection();
glutPostRedisplay();
break;
case GLUT_MIDDLE_BUTTON:
middle_mouse = GL_FALSE;
glutPostRedisplay();
break;
}
}
motion(x, y);
}

void
animate(void)
{
if (spinning) {
add_quats(lastquat, curquat, curquat);

}
glutPostRedisplay();
if (solving) {
if (!continueSolving()) {
solving = 0;
glutChangeToMenuEntry(1, "Solving", 1);
glutSetWindowTitle("glpuzzle");
}
}
if (!solving && !spinning && !visible) {
glutIdleFunc(NULL);
}
}

void
changeState(void)
{
if (visible) {
if (!solving && !spinning) {
glutIdleFunc(NULL);
} else {
glutIdleFunc(animate);
}
} else {
glutIdleFunc(NULL);
}
}

void
init(void)
{
static float lmodel_ambient[] =
{0.0, 0.0, 0.0, 0.0};
static float lmodel_twoside[] =
{GL_FALSE};
static float lmodel_local[] =
{GL_FALSE};
static float light0_ambient[] =
{0.1, 0.1, 0.1, 1.0};
static float light0_diffuse[] =
{1.0, 1.0, 1.0, 0.0};
static float light0_position[] =
{0.8660254, 0.5, 1, 0};
static float light0_specular[] =
{0.0, 0.0, 0.0, 0.0};
static float bevel_mat_ambient[] =
{0.0, 0.0, 0.0, 1.0};
static float bevel_mat_shininess[] =
{40.0};
static float bevel_mat_specular[] =
{0.0, 0.0, 0.0, 0.0};
static float bevel_mat_diffuse[] =
{1.0, 0.0, 0.0, 0.0};

glEnable(GL_CULL_FACE);
glCullFace(GL_BACK);
glEnable(GL_DEPTH_TEST);
glClearDepth(1.0);

glClearColor(0.5, 0.5, 0.5, 0.0);
glLightfv(GL_LIGHT0, GL_AMBIENT, light0_ambient);
glLightfv(GL_LIGHT0, GL_DIFFUSE, light0_diffuse);
glLightfv(GL_LIGHT0, GL_SPECULAR, light0_specular);
glLightfv(GL_LIGHT0, GL_POSITION, light0_position);
glEnable(GL_LIGHT0);

glLightModelfv(GL_LIGHT_MODEL_LOCAL_VIEWER, lmodel_local);
glLightModelfv(GL_LIGHT_MODEL_TWO_SIDE, lmodel_twoside);
glLightModelfv(GL_LIGHT_MODEL_AMBIENT, lmodel_ambient);
glEnable(GL_LIGHTING);

glMaterialfv(GL_FRONT, GL_AMBIENT, bevel_mat_ambient);
glMaterialfv(GL_FRONT, GL_SHININESS, bevel_mat_shininess);
glMaterialfv(GL_FRONT, GL_SPECULAR, bevel_mat_specular);
glMaterialfv(GL_FRONT, GL_DIFFUSE, bevel_mat_diffuse);

glColorMaterial(GL_FRONT_AND_BACK, GL_DIFFUSE);
glEnable(GL_COLOR_MATERIAL);
glShadeModel(GL_FLAT);

trackball(curquat, 0.0, 0.0, 0.0, 0.0);
srandom(time(NULL));
}

static void
Usage(void)
{
printf("Usage: puzzle [-s]\n");
printf(" -s: Run in single buffered mode\n");
exit(-1);
}

void
visibility(int v)
{
if (v == GLUT_VISIBLE) {
visible = 1;
} else {
visible = 0;
}
changeState();
}

void
menu(int choice)
{
switch(choice) {
case 1:
toggleSolve();
break;
case 2:
reset();
break;
case 3:
exit(0);
break;
}
}

int
main(int argc, char **argv)
{
long i;

glutInit(&argc, argv);
for (i = 1; i < argc; i++) {
if (argv[i][0] == '-') {
switch (argv[i][1]) {
case 's':
doubleBuffer = 0;
break;
default:
Usage();
}
} else {
Usage();
}
}

glutInitWindowSize(W, H);
if (doubleBuffer) {
glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_DOUBLE | GLUT_MULTISAMPLE);
} else {
glutInitDisplayMode(GLUT_DEPTH | GLUT_RGB | GLUT_SINGLE | GLUT_MULTISAMPLE);
}

glutCreateWindow("glpuzzle");

init();

glGetIntegerv(GL_VIEWPORT, viewport);

printf("\n");
printf("r Reset puzzle\n");
printf("s Solve puzzle (may take a few seconds to compute)\n");
printf("d Destroy a piece - makes the puzzle easier\n");
printf("b Toggles the depth buffer on and off\n");
printf("\n");
printf("Left mouse moves pieces\n");
printf("Middle mouse spins the puzzle\n");
printf("Right mouse has menu\n");

glutReshapeFunc(Reshape);
glutDisplayFunc(redraw);
glutKeyboardFunc(keyboard);
glutMotionFunc(motion);
glutMouseFunc(mouse);
glutVisibilityFunc(visibility);
glutCreateMenu(menu);
glutAddMenuEntry("Solve", 1);
glutAddMenuEntry("Reset", 2);
glutAddMenuEntry("Quit", 3);
glutAttachMenu(GLUT_RIGHT_BUTTON);
glutMainLoop();
return 0; /* ANSI C requires main to return int. */
}

Snapshots: mid-game (shown).