Skip to content

Instantly share code, notes, and snippets.

@kotarou3

kotarou3/mandelbrot.c

Last active December 16, 2015 11:39
Show Gist options
  • Save kotarou3/5429379 to your computer and use it in GitHub Desktop.
Save kotarou3/5429379 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
mandelbrot.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/select.h>
#include <sys/time.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include "mandelbrot.h"
#include "pixelColor.h"
#define HTTP_METHOD "GET"
#define RECV_BUFFER_SIZE 256
#define RECV_TIMEOUT_SECONDS 2
#define TILE_WIDTH 512
#define TILE_HEIGHT 512
#define TILE_SIZE (TILE_WIDTH * TILE_HEIGHT * 4)
#define MAXIMUM_STEPS 256
#define ESCAPE_BOUNDARY_RADIUS 2
#define BITMAP_RED_POSITION 2
#define BITMAP_BLUE_POSITION 0
#define BITMAP_GREEN_POSITION 1
#define BITMAP_ALPHA_POSITION 3
#ifndef SO_RCVTIMEO
#define SO_RCVTIMEO 20
#endif
#ifndef MSG_NOSIGNAL
#define MSG_NOSIGNAL 0x4000
#endif
#ifndef SHUT_WR
#define SHUT_WR 1
#endif
static double powz(double a, int n) {
double result = a;
if (n > 1)
while (n > 1) {
result *= a;
--n;
}
else if (n < 1)
while (n < 1) {
result /= a;
++n;
}
return result;
}
static bool isSpace(char c) {
return c == ' ' || c == '\t' || c == '\n' || c == '\r';
}
int escapeSteps(double cX, double cY) {
int iteration = 0;
double zX = 0;
double zY = 0;
double tX, tY;
while (iteration < MAXIMUM_STEPS && zX * zX + zY * zY < ESCAPE_BOUNDARY_RADIUS * ESCAPE_BOUNDARY_RADIUS) {
++iteration;
tX = zX;
tY = zY;
zX = tX * tX - tY * tY + cX;
zY = 2 * tX * tY + cY;
}
return iteration;
}
static ssize_t sendData(int fd, const void* buffer, size_t length) {
size_t totalSent = 0;
ssize_t sent = 0;
while (totalSent < length && (sent = send(fd, (const char*)buffer + totalSent, length - totalSent, MSG_NOSIGNAL)) >= 0)
totalSent += sent;
if (sent < 0)
return sent;
else
return totalSent;
}
static ssize_t sendString(int fd, const char* string) {
return sendData(fd, string, strlen(string));
}
static void serveStatusWithHeaders(int socket, const char* status, const char* headers) {
sendString(socket, "HTTP/1.1 ");
sendString(socket, status);
sendString(socket, "\r\n");
if (headers != NULL)
sendString(socket, headers);
sendString(socket, "Content-Type: text/plain\r\nConnection: close\r\n\r\n");
sendString(socket, status);
}
static void serveStatus(int socket, const char* status) {
serveStatusWithHeaders(socket, status, NULL);
}
static void serveIndex(int socket) {
sendString(socket,
"HTTP/1.1 200 OK\r\n"
"Content-Type: text/html\r\n"
"Connection: close\r\n"
"\r\n"
"<!DOCTYPE html>\n"
"<script type=\"application/javascript\" src=\"https://almondbread.openlearning.com/tileviewer.js\"></script>"
);
}
static void serveMandelbrot(int socket, double point[3]) {
// Structures and defines are stuck here because we're not allowed to use our own headers
#pragma pack(push, 2)
struct {
unsigned short bfType;
unsigned int bfSize;
unsigned short bfReserved1;
unsigned short bfReserved2;
unsigned int bfOffBits;
} bmpFileHeader;
struct CIEXYZ {
int ciexyzX;
int ciexyzY;
int ciexyzZ;
};
struct {
unsigned int bV5Size;
int bV5Width;
int bV5Height;
unsigned short bV5Planes;
unsigned short bV5BitCount;
unsigned int bV5Compression;
unsigned int bV5SizeImage;
int bV5XPelsPerMeter;
int bV5YPelsPerMeter;
unsigned int bV5ClrUsed;
unsigned int bV5ClrImportant;
unsigned int bV5RedMask;
unsigned int bV5GreenMask;
unsigned int bV5BlueMask;
unsigned int bV5AlphaMask;
unsigned int bV5CSType;
struct {
struct CIEXYZ ciexyzRed;
struct CIEXYZ ciexyzGreen;
struct CIEXYZ ciexyzBlue;
} bV5Endpoints;
unsigned int bV5GammaRed;
unsigned int bV5GammaGreen;
unsigned int bV5GammaBlue;
unsigned int bV5Intent;
unsigned int bV5ProfileData;
unsigned int bV5ProfileSize;
unsigned int bV5Reserved;
} dibHeader;
#define BI_BITFIELDS 3
#define LCS_WINDOWS_COLOR_SPACE 0x57696e20
#pragma pack(pop)
memset(&bmpFileHeader, 0, sizeof(bmpFileHeader));
bmpFileHeader.bfType = ('M' << 8) + 'B';
bmpFileHeader.bfOffBits = sizeof(bmpFileHeader) + sizeof(dibHeader);
bmpFileHeader.bfSize = bmpFileHeader.bfOffBits + TILE_SIZE;
memset(&dibHeader, 0, sizeof(dibHeader));
dibHeader.bV5Size = sizeof(dibHeader);
dibHeader.bV5Width = TILE_WIDTH;
dibHeader.bV5Height = -TILE_HEIGHT;
dibHeader.bV5Planes = 1;
dibHeader.bV5BitCount = 32;
dibHeader.bV5Compression = BI_BITFIELDS;
dibHeader.bV5SizeImage = TILE_SIZE;
dibHeader.bV5RedMask = 0xff << (BITMAP_RED_POSITION * 8);
dibHeader.bV5GreenMask = 0xff << (BITMAP_GREEN_POSITION * 8);
dibHeader.bV5BlueMask = 0xff << (BITMAP_BLUE_POSITION * 8);
dibHeader.bV5AlphaMask = 0xff << (BITMAP_ALPHA_POSITION * 8);
dibHeader.bV5CSType = LCS_WINDOWS_COLOR_SPACE;
sendString(socket, "HTTP/1.1 200 OK\r\nContent-Type: image/bmp\r\nConnection: close\r\n\r\n");
sendData(socket, &bmpFileHeader, sizeof(bmpFileHeader));
sendData(socket, &dibHeader, sizeof(dibHeader));
double xInterval = powz(2, 9 - point[2]) / TILE_WIDTH;
double yInterval = powz(2, 9 - point[2]) / TILE_HEIGHT;
double startX = point[0] - (TILE_WIDTH - 1) / 2.0 * xInterval;
double startY = point[1] + (TILE_HEIGHT - 1) / 2.0 * yInterval;
size_t row = 0;
while (row < TILE_HEIGHT) {
unsigned char bmpRowBuffer[TILE_WIDTH * 4];
size_t column = 0;
while (column < TILE_WIDTH) {
int steps = escapeSteps(startX + xInterval * column, startY - yInterval * row);
bmpRowBuffer[column * 4 + BITMAP_RED_POSITION] = stepsToRed(steps);
bmpRowBuffer[column * 4 + BITMAP_BLUE_POSITION] = stepsToBlue(steps);
bmpRowBuffer[column * 4 + BITMAP_GREEN_POSITION] = stepsToGreen(steps);
bmpRowBuffer[column * 4 + BITMAP_ALPHA_POSITION] = 0xff;
++column;
}
sendData(socket, bmpRowBuffer, TILE_WIDTH * 4);
++row;
}
}
static bool decodeMandelbrotUri(const char* uri, double* point) {
// /\/X(-?[0-9]+\.[0-9]+)_Y(-?[0-9]+\.[0-9]+)_Z(-?[0-9]+\.[0-9]+)/
size_t uriLength = strlen(uri);
if (uriLength < 6 || uri[0] != '/' || strcmp(uri + uriLength - 4, ".bmp") != 0)
return false;
char pointString[uriLength];
strncpy(pointString, uri + 1, uriLength - 5); // Strip off leading forward slash and trailing .bmp
pointString[uriLength - 5] = 0;
char pointOrder[] = {'X', 'Y', 'Z'};
char* token = strtok(pointString, "_");
size_t t = 0;
while (token != NULL) {
if (t >= sizeof(pointOrder) || strlen(token) < 2 || token[0] != pointOrder[t])
return false;
point[t] = atof(token + 1);
++t;
token = strtok(NULL, "_");
}
return true;
}
// Receiving stuff below
static size_t recvLine(int fd, char* buffer, size_t bufferSize) {
size_t length = 0;
while (length + 1 < bufferSize && recv(fd, buffer + length, 1, MSG_NOSIGNAL) > 0 && buffer[length] != '\n')
++length;
buffer[length + 1] = 0;
return length;
}
static void trim(char* string)
{
char* c = string;
while (isSpace(*c))
++c;
char* end = c + strlen(c) - 1;
while (end > c && isSpace(*end))
--end;
end[1] = 0;
memmove(string, c, strlen(c) + 1);
}
static void handleClient(int socket) {
char buffer[RECV_BUFFER_SIZE];
ssize_t bufferLength = recvLine(socket, buffer, RECV_BUFFER_SIZE);
// Test for GET /path/to/file
if (strncmp(buffer, HTTP_METHOD" ", strlen(HTTP_METHOD" ")) != 0) {
serveStatusWithHeaders(socket, "405 Method Not Allowed", "Allow: GET\r\n");
return;
}
// Strip off anything but the URI
char* uriEnd = strchr(buffer + strlen(HTTP_METHOD" "), ' ');
if (uriEnd == NULL)
uriEnd = buffer + bufferLength;
memmove(buffer, buffer + strlen(HTTP_METHOD" "), uriEnd - buffer - strlen(HTTP_METHOD" "));
buffer[uriEnd - buffer - strlen(HTTP_METHOD" ")] = 0;
trim(buffer);
// buffer now contains the URI
// Ignore any other incoming data (eg. request headers and data)
if (strcmp(buffer, "/") == 0)
serveIndex(socket);
else {
double point[3] = {0};
if (decodeMandelbrotUri(buffer, point))
serveMandelbrot(socket, point);
else
serveStatus(socket, "404 Not Found");
}
}
// Connection stuff below
static int createServer(unsigned short port) {
int serverSocket = socket(AF_INET6, SOCK_STREAM, IPPROTO_TCP);
int on = true;
setsockopt(serverSocket, SOL_SOCKET, SO_REUSEADDR, (char*)&on, sizeof(int));
struct sockaddr_in6 sockInfo = {0};
sockInfo.sin6_family = AF_INET6;
sockInfo.sin6_port = htons(port);
#ifdef IN6ADDR_ANY_INIT // Hack for code to compile on test computer
sockInfo.sin6_addr = IN6ADDR_ANY_INIT;
#endif
bind(serverSocket, (struct sockaddr*)&sockInfo, sizeof(sockInfo));
listen(serverSocket, SOMAXCONN);
return serverSocket;
}
int main(void) {
int serverSocket = createServer(7191);
puts("Entering main server loop. Type q to quit.");
bool isExiting = false;
while (!isExiting) {
fd_set listenOn;
FD_ZERO(&listenOn);
FD_SET(serverSocket, &listenOn);
FD_SET(STDIN_FILENO, &listenOn);
select((serverSocket > STDIN_FILENO ? serverSocket : STDIN_FILENO) + 1, &listenOn, NULL, NULL, NULL);
if (FD_ISSET(STDIN_FILENO, &listenOn))
if (getchar() == 'q') {
puts("Exiting...");
isExiting = true;
}
if (FD_ISSET(serverSocket, &listenOn)) {
int clientSocket = accept(serverSocket, NULL, NULL);
struct timeval tv = {.tv_sec = RECV_TIMEOUT_SECONDS, .tv_usec = 0};
setsockopt(clientSocket, SOL_SOCKET, SO_RCVTIMEO, (char*)&tv, sizeof(tv));
handleClient(clientSocket);
// Cleanly close socket
shutdown(clientSocket, SHUT_WR);
char blackHoleBuffer[RECV_BUFFER_SIZE];
while (recv(clientSocket, blackHoleBuffer, RECV_BUFFER_SIZE, MSG_NOSIGNAL) > 0)
;
close(clientSocket);
}
}
close(serverSocket);
return EXIT_SUCCESS;
}
Raw
pixelColor.c
#include "pixelColor.h"
#define MAXIMUM_STEPS 256
#define VALUE_CURVE_N 5 // Increase for a sharper increase and decrease in value
#define MAXIMUM_VALUE 0.8
struct HSV {
double h, s, v;
};
struct RGB {
double r, g, b;
};
static double powz(double a, int n) {
double result = a;
if (n > 1)
while (n > 1) {
result *= a;
--n;
}
else if (n < 1)
while (n < 1) {
result /= a;
++n;
}
return result;
}
static double fabs(double n) {
if (n < 0)
return -n;
return n;
}
// Warning: Naive algorithm that only works with small (x / y)
static double fmod(double x, double y) {
return x - (long long)(x / y) * y;
}
static double valueFunction(double x) {
double intercept = (MAXIMUM_STEPS - 1.0) / 2.0;
return -powz(x - intercept - 1.0, 2 * VALUE_CURVE_N) + powz(intercept, 2 * VALUE_CURVE_N);
}
static double stepsToValue(int steps) {
return valueFunction(steps) / valueFunction(MAXIMUM_STEPS / 2.0) * MAXIMUM_VALUE;
}
static struct HSV stepsToHsv(int steps) {
struct HSV hsv;
hsv.h = fmod(steps / (MAXIMUM_STEPS + 1.0) * 1080.0, 360.0);
hsv.s = 1;
hsv.v = stepsToValue(steps);
return hsv;
}
static struct RGB hsvToRgb(struct HSV hsv)
{
double chroma = hsv.v * hsv.s;
double secondary = chroma * (1.0 - fabs(fmod(hsv.h / 60.0, 2.0) - 1.0));
struct RGB rgb;
unsigned char cubeFace = hsv.h / 60.0;
switch (cubeFace) {
case 0:
rgb.r = chroma;
rgb.g = secondary;
rgb.b = 0;
break;
case 1:
rgb.r = secondary;
rgb.g = chroma;
rgb.b = 0;
break;
case 2:
rgb.r = 0;
rgb.g = chroma;
rgb.b = secondary;
break;
case 3:
rgb.r = 0;
rgb.g = secondary;
rgb.b = chroma;
break;
case 4:
rgb.r = secondary;
rgb.g = 0;
rgb.b = chroma;
break;
case 5:
rgb.r = chroma;
rgb.g = 0;
rgb.b = secondary;
break;
}
double offset = hsv.v - chroma;
rgb.r += offset;
rgb.g += offset;
rgb.b += offset;
return rgb;
}
unsigned char stepsToRed(int steps) {
return hsvToRgb(stepsToHsv(steps)).r * 255.0;
}
unsigned char stepsToGreen(int steps) {
return hsvToRgb(stepsToHsv(steps)).g * 255.0;
}
unsigned char stepsToBlue(int steps) {
return hsvToRgb(stepsToHsv(steps)).b * 255.0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment