Begin re-writing in Rust

21 files changed, 36 insertions, 2014 deletions

diff --git a/.gitattributes b/.gitattributes
new file mode 100644
index 0000000..c353fc3
--- /dev/null
+++ b/.gitattributes
@@ -0,0 +1 @@
+Cargo.lock binary
diff --git a/.gitignore b/.gitignore
index aea0ddb..ecd771b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,4 +1,13 @@
-*.o
-/kd-forest
+# Generated by Cargo
+# will have compiled files and executables
+/target/
+
+# Remove Cargo.lock from gitignore if creating an executable, leave it for libraries
+# More information here https://doc.rust-lang.org/cargo/guide/cargo-toml-vs-cargo-lock.html
+# Cargo.lock
+
+# These are backup files generated by rustfmt
+**/*.rs.bk
+
+# Generated images
 *.png
-*.mkv
diff --git a/COPYING b/COPYING
deleted file mode 100644
index c6c7def..0000000
--- a/COPYING
+++ /dev/null
@@ -1,13 +0,0 @@
-        DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
-                    Version 2, December 2004
-
- Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>
-
- Everyone is permitted to copy and distribute verbatim or modified
- copies of this license document, and changing it is allowed as long
- as the name is changed.
-
-            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
-   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
-
-  0. You just DO WHAT THE FUCK YOU WANT TO.
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..a63d677
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,5 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+[[package]]
+name = "kd-forest"
+version = "2.0.0"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..65ffec8
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,5 @@
+[package]
+name = "kd-forest"
+version = "2.0.0"
+authors = ["Tavian Barnes <tavianator@tavianator.com>"]
+edition = "2018"
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..9a254ab
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,12 @@
+Copyright (C) 2015-2020 Tavian Barnes <tavianator@tavianator.com>
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
diff --git a/Makefile b/Makefile
deleted file mode 100644
index 4e035e0..0000000
--- a/Makefile
+++ /dev/null
@@ -1,47 +0,0 @@
-#####################################################################
-# kd-forest                                                         #
-# Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      #
-#                                                                   #
-# This program is free software. It comes without any warranty, to  #
-# the extent permitted by applicable law. You can redistribute it   #
-# and/or modify it under the terms of the Do What The Fuck You Want #
-# To Public License, Version 2, as published by Sam Hocevar. See    #
-# the COPYING file or http://www.wtfpl.net/ for more details.       #
-#####################################################################
-
-CC = gcc
-CFLAGS = -std=c99 -D_POSIX_C_SOURCE=200809L -pipe -g -O3 -flto -Wall -Wpedantic -Wextra -Wno-sign-compare -Wno-unused-parameter -Wunreachable-code -Wshadow -Wpointer-arith -Wwrite-strings -Wcast-align -Wstrict-prototypes
-LDFLAGS = -Wl,-O1,--sort-common,--as-needed,-z,relro
-LIBS = -lm -lpng
-RM = rm -f
-
-DEPS = Makefile color.h hilbert.h generate.h kd-forest.h options.h util.h
-
-IMAGEFLAGS = -b 24 -s -l min -c Lab
-ANIMFLAGS = -b 19 -s -l mean -c Lab
-
-kd-forest: color.o generate.o hilbert.o kd-forest.o main.o options.o util.o
-	$(CC) $(CFLAGS) $(LDFLAGS) $^ $(LIBS) -o kd-forest
-
-%.o: %.c $(DEPS)
-	$(CC) $(CFLAGS) -c $< -o $@
-
-image: kd-forest.png
-
-kd-forest.png: kd-forest
-	./kd-forest $(IMAGEFLAGS) -o kd-forest.png
-
-anim: kd-forest.mkv
-
-kd-forest.mkv: kd-forest
-	$(RM) kd-forest.mkv
-	mkdir /tmp/kd-frames
-	./kd-forest $(ANIMFLAGS) -a -o /tmp/kd-frames
-	ffmpeg -r 60 -i /tmp/kd-frames/%04d.png -c:v libx264 -preset veryslow -qp 0 kd-forest.mkv
-	$(RM) -r /tmp/kd-frames
-
-clean:
-	$(RM) *.o
-	$(RM) kd-forest
-
-.PHONY: image anim clean
diff --git a/color.c b/color.c
deleted file mode 100644
index 9d15034..0000000
--- a/color.c
+++ /dev/null
@@ -1,176 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "color.h"
-#include <math.h>
-
-void
-color_unpack(uint8_t pixel[3], uint32_t color)
-{
-  pixel[0] = (color >> 16) & 0xFF;
-  pixel[1] = (color >> 8) & 0xFF;
-  pixel[2] = color & 0xFF;
-}
-
-void
-color_set_RGB(double coords[3], uint32_t color)
-{
-  uint8_t pixel[3];
-  color_unpack(pixel, color);
-  for (int i = 0; i < 3; ++i) {
-    coords[i] = pixel[i]/255.0;
-  }
-}
-
-// Inverse gamma for sRGB
-double
-sRGB_C_inv(double t)
-{
-  if (t <= 0.040449936) {
-    return t/12.92;
-  } else {
-    return pow((t + 0.055)/1.055, 2.4);
-  }
-}
-
-static void
-color_set_XYZ(double XYZ[3], uint32_t color)
-{
-  double RGB[3];
-  color_set_RGB(RGB, color);
-
-  RGB[0] = sRGB_C_inv(RGB[0]);
-  RGB[1] = sRGB_C_inv(RGB[1]);
-  RGB[2] = sRGB_C_inv(RGB[2]);
-
-  XYZ[0] = 0.4123808838268995*RGB[0] + 0.3575728355732478*RGB[1] + 0.1804522977447919*RGB[2];
-  XYZ[1] = 0.2126198631048975*RGB[0] + 0.7151387878413206*RGB[1] + 0.0721499433963131*RGB[2];
-  XYZ[2] = 0.0193434956789248*RGB[0] + 0.1192121694056356*RGB[1] + 0.9505065664127130*RGB[2];
-}
-
-// CIE L*a*b* and L*u*v* gamma
-static double
-Lab_f(double t)
-{
-  if (t > 216.0/24389.0) {
-    return pow(t, 1.0/3.0);
-  } else {
-    return 841.0*t/108.0 + 4.0/29.0;
-  }
-}
-
-// sRGB white point (CIE D50) in XYZ coordinates
-static const double WHITE[] = {
-  [0] = 0.9504060171449392,
-  [1] = 0.9999085943425312,
-  [2] = 1.089062231497274,
-};
-
-void
-color_set_Lab(double coords[3], uint32_t color)
-{
-  double XYZ[3];
-  color_set_XYZ(XYZ, color);
-
-  double fXYZ[] = {
-    [0] = Lab_f(XYZ[0]/WHITE[0]),
-    [1] = Lab_f(XYZ[1]/WHITE[1]),
-    [2] = Lab_f(XYZ[2]/WHITE[2]),
-  };
-
-  coords[0] = 116.0*fXYZ[1] - 16.0;
-  coords[1] = 500.0*(fXYZ[0] - fXYZ[1]);
-  coords[2] = 200.0*(fXYZ[1] - fXYZ[2]);
-}
-
-void
-color_set_Luv(double coords[3], uint32_t color)
-{
-  double XYZ[3];
-  color_set_XYZ(XYZ, color);
-
-  double uv_denom = XYZ[0] + 15.0*XYZ[1] + 3.0*XYZ[2];
-  if (uv_denom == 0.0) {
-    coords[0] = 0.0;
-    coords[1] = 0.0;
-    coords[2] = 0.0;
-    return;
-  }
-
-  double white_uv_denom = WHITE[0] + 16.0*WHITE[1] + 3.0*WHITE[2];
-
-  double fY = Lab_f(XYZ[1]/WHITE[1]);
-  double uprime = 4.0*XYZ[0]/uv_denom;
-  double unprime = 4.0*WHITE[0]/white_uv_denom;
-  double vprime = 9.0*XYZ[1]/uv_denom;
-  double vnprime = 9.0*WHITE[1]/white_uv_denom;
-
-  coords[0] = 116.0*fY - 16.0;
-  coords[1] = 13.0*coords[0]*(uprime - unprime);
-  coords[2] = 13.0*coords[0]*(vprime - vnprime);
-}
-
-int
-color_comparator(const void *a, const void *b)
-{
-  uint8_t aRGB[3], bRGB[3];
-  color_unpack(aRGB, *(uint32_t *)a);
-  color_unpack(bRGB, *(uint32_t *)b);
-
-  int anum = aRGB[1] - aRGB[2], adenom = 2*aRGB[0] - aRGB[1] - aRGB[2];
-  int bnum = bRGB[1] - bRGB[2], bdenom = 2*bRGB[0] - bRGB[1] - bRGB[2];
-
-  // The hue angle is defined as atan2(sqrt(3)*n/d) (+ 2*pi if negative).  But
-  // since atan2() is expensive, we compute an equivalent ordering while
-  // avoiding trig calls.  First, handle the quadrants.  We have:
-  //
-  //   hue(n, d)
-  //     | d >= 0 && n == 0  =  0
-  //     | d >= 0 && n >  0  =  atan(n/d)
-  //     | d >= 0 && n <  0  =  atan(n/d) + 2*pi
-  //     | d <  0            =  atan(n/d) + pi
-  //
-  // and since atan(n/d)'s range is [-pi/2, pi/2], each chunk can be strictly
-  // ordered relative to the other chunks.
-  if (adenom >= 0) {
-    if (anum >= 0) {
-      if (bdenom < 0 || bnum < 0) {
-        return -1;
-      }
-    } else {
-      if (bdenom < 0 || bnum >= 0) {
-        return 1;
-      }
-    }
-  } else if (bdenom >= 0) {
-    if (bnum >= 0) {
-      return 1;
-    } else {
-      return -1;
-    }
-  }
-
-  // Special-case zero numerators, because we treat 0/0 as 0, not NaN
-  if (anum == 0 || bnum == 0) {
-    int lhs = adenom >= 0 ? anum : -anum;
-    int rhs = bdenom >= 0 ? bnum : -bnum;
-    return lhs - rhs;
-  }
-
-  // The points are in the same/comparable quadrants.  We can still avoid
-  // calculating atan(n/d) though, because it's an increasing function in n/d.
-  // We can also avoid a division, by noting that an/ad < bn/bd iff
-  // an*bd*sgn(ad*bd) < bn*ad*sgn(ad*bd).  Due to the logic above, both
-  // denominators must have the same sign, so the sgn()s are redundant.
-  int lhs = anum*bdenom;
-  int rhs = bnum*adenom;
-  return lhs - rhs;
-}
diff --git a/color.h b/color.h
deleted file mode 100644
index 0abafbd..0000000
--- a/color.h
+++ /dev/null
@@ -1,30 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#ifndef COLOR_H
-#define COLOR_H
-
-#include <stdint.h>
-
-// Unpack a color into 8-bit RGB values
-void color_unpack(uint8_t pixel[3], uint32_t color);
-
-// Use RGB coordinates
-void color_set_RGB(double coords[3], uint32_t color);
-// Use CIE L*a*b* coordinates
-void color_set_Lab(double coords[3], uint32_t color);
-// Use CIE L*u*v* coordinates
-void color_set_Luv(double coords[3], uint32_t color);
-
-// For sorting by hue
-int color_comparator(const void *a, const void *b);
-
-#endif // COLOR_H
diff --git a/generate.c b/generate.c
deleted file mode 100644
index 9a4eac8..0000000
--- a/generate.c
+++ /dev/null
@@ -1,82 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2015 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "generate.h"
-#include "color.h"
-#include "hilbert.h"
-#include "util.h"
-#include <stdlib.h>
-
-uint32_t *
-generate_colors(const options_t *options)
-{
-  const unsigned int bit_depth = options->bit_depth;
-  mode_t mode = options->mode;
-
-  // Allocate bits from most to least perceptually important
-  unsigned int grb_bits[3];
-  for (unsigned int i = 0; i < 3; ++i) {
-    grb_bits[i] = (bit_depth + 2 - i)/3;
-  }
-
-  uint32_t *colors = xmalloc(options->ncolors*sizeof(uint32_t));
-  for (uint32_t i = 0; i < (1 << bit_depth); ++i) {
-    uint32_t n = i;
-    uint32_t grb[3] = {0, 0, 0};
-
-    switch (mode) {
-    case MODE_MORTON:
-      for (unsigned int j = 0; j < bit_depth; ++j) {
-        grb[j%3] |= (i & (1 << j)) >> (j - j/3);
-      }
-      break;
-
-    case MODE_HILBERT:
-      hilbert_point(3, grb_bits, n, grb);
-      break;
-
-    default:
-      for (unsigned int j = 0; j < 3; ++j) {
-        grb[j] = n & ((1 << grb_bits[j]) - 1);
-        n >>= grb_bits[j];
-      }
-      break;
-    }
-
-    // Pad out colors, and put them in RGB order
-    grb[0] <<= 16U - grb_bits[0];
-    grb[1] <<= 24U - grb_bits[1];
-    grb[2] <<=  8U - grb_bits[2];
-
-    colors[i] = grb[1] | grb[0] | grb[2];
-  }
-
-  switch (mode) {
-  case MODE_HUE_SORT:
-    qsort(colors, options->ncolors, sizeof(uint32_t), color_comparator);
-    break;
-
-  case MODE_RANDOM:
-    // Fisher-Yates shuffle
-    for (unsigned int i = options->ncolors; i-- > 0;) {
-      unsigned int j = xrand(i + 1);
-      uint32_t temp = colors[i];
-      colors[i] = colors[j];
-      colors[j] = temp;
-    }
-    break;
-
-  default:
-    break;
-  }
-
-  return colors;
-}
diff --git a/generate.h b/generate.h
deleted file mode 100644
index 2b78150..0000000
--- a/generate.h
+++ /dev/null
@@ -1,21 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2015 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#ifndef GENERATE_H
-#define GENERATE_H
-
-#include "options.h"
-#include <stdint.h>
-
-// Generate the colors according to the mode
-uint32_t *generate_colors(const options_t *options);
-
-#endif // GENERATE_H
diff --git a/hilbert.c b/hilbert.c
deleted file mode 100644
index 98cf247..0000000
--- a/hilbert.c
+++ /dev/null
@@ -1,170 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2015 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "hilbert.h"
-#include <stdint.h>
-
-// These algorithms are described in "Compact Hilbert Indices" by Chris Hamilton
-
-// Right rotation of x by b bits out of n
-static uint32_t
-ror(uint32_t x, unsigned int b, unsigned int n)
-{
-  uint32_t l = x & ((1 << b) - 1);
-  uint32_t r = x >> b;
-  return (l << (n - b)) | r;
-}
-
-// Left rotation of x by b bits out of n
-static uint32_t
-rol(uint32_t x, unsigned int b, unsigned int n)
-{
-  return ror(x, n - b, n);
-}
-
-// Binary reflected Gray code
-uint32_t
-gray_code(uint32_t i)
-{
-  return i ^ (i >> 1);
-}
-
-// e(i), the entry point for the ith sub-hypercube
-uint32_t
-entry_point(uint32_t i)
-{
-  if (i == 0) {
-    return 0;
-  } else {
-    return gray_code((i - 1) & ~1U);
-  }
-}
-
-// g(i), the inter sub-hypercube direction
-unsigned int
-inter_direction(uint32_t i)
-{
-  // g(i) counts the trailing set bits in i
-  unsigned int g = 0;
-  while (i & 1) {
-    ++g;
-    i >>= 1;
-  }
-  return g;
-}
-
-// d(i), the intra sub-hypercube direction
-unsigned int
-intra_direction(uint32_t i)
-{
-  if (i & 1) {
-    return inter_direction(i);
-  } else if (i > 0) {
-    return inter_direction(i - 1);
-  } else {
-    return 0;
-  }
-}
-
-// T transformation inverse
-uint32_t
-t_inverse(unsigned int dimensions, uint32_t e, unsigned int d, uint32_t a)
-{
-  return rol(a, d, dimensions) ^ e;
-}
-
-// GrayCodeRankInverse
-void
-gray_code_rank_inverse(unsigned int dimensions, uint32_t mu, uint32_t pi, unsigned int r, unsigned int free_bits, uint32_t *i, uint32_t *g)
-{
-  // *i is the inverse rank of r
-  // *g is gray_code(i)
-
-  *i = 0;
-  *g = 0;
-
-  for (unsigned int j = free_bits - 1, k = dimensions; k-- > 0;) {
-    if (mu & (1 << k)) {
-      *i |= ((r >> j) & 1) << k;
-      *g |= (*i ^ (*i >> 1)) & (1 << k);
-      --j;
-    } else {
-      *g |= pi & (1 << k);
-      *i |= (*g ^ (*i >> 1)) & (1 << k);
-    }
-  }
-}
-
-// ExtractMask
-void
-extract_mask(unsigned int dimensions, const unsigned int extents[], unsigned int i, uint32_t *mu, unsigned int *free_bits)
-{
-  // *mu is the mask
-  // *free_bits is popcount(*mu)
-
-  *mu = 0;
-  *free_bits = 0;
-
-  for (unsigned int j = dimensions; j-- > 0;) {
-    *mu <<= 1;
-
-    if (extents[j] > i) {
-      *mu |= 1;
-      *free_bits += 1;
-    }
-  }
-}
-
-// CompactHilbertIndexInverse
-void
-hilbert_point(unsigned int dimensions, const unsigned int extents[], uint32_t index, uint32_t point[])
-{
-  unsigned int max_extent = 0, total_extent = 0;
-  for (unsigned int i = 0; i < dimensions; ++i) {
-    if (extents[i] > max_extent) {
-      max_extent = extents[i];
-    }
-    total_extent += extents[i];
-    point[i] = 0;
-  }
-
-  uint32_t e = 0;
-  unsigned int k = 0;
-
-  // Next direction; we use d instead of d + 1 everywhere
-  unsigned int d = 1;
-
-  for (unsigned int i = max_extent; i-- > 0;) {
-    uint32_t mu;
-    unsigned int free_bits;
-    extract_mask(dimensions, extents, i, &mu, &free_bits);
-    mu = ror(mu, d, dimensions);
-
-    uint32_t pi = ror(e, d, dimensions) & ~mu;
-
-    unsigned int r = (index >> (total_extent - k - free_bits)) & ((1 << free_bits) - 1);
-
-    k += free_bits;
-
-    uint32_t w, l;
-    gray_code_rank_inverse(dimensions, mu, pi, r, free_bits, &w, &l);
-
-    l = t_inverse(dimensions, e, d, l);
-
-    for (unsigned int j = 0; j < 3; ++j) {
-      point[j] |= (l & 1) << i;
-      l >>= 1;
-    }
-
-    e = e ^ ror(entry_point(w), d, dimensions);
-    d = (d + intra_direction(w) + 1)%dimensions;
-  }
-}
diff --git a/hilbert.h b/hilbert.h
deleted file mode 100644
index 4628ad6..0000000
--- a/hilbert.h
+++ /dev/null
@@ -1,31 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2015 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#ifndef HILBERT_H
-#define HILBERT_H
-
-#include <stdint.h>
-
-/**
- * Compute the point corresponding to the given (compact) Hilbert index.
- *
- * @param dimensions
- *         The number of spatial dimensions.
- * @param extents
- *         The bit depth of each dimension.
- * @param index
- *         The (compact) Hilbert index of the desired point.
- * @param[out] point
- *         Will hold the point on the Hilbert curve at index.
- */
-void hilbert_point(unsigned int dimensions, const unsigned int extents[], uint32_t index, uint32_t point[]);
-
-#endif // HILBERT_H
diff --git a/kd-forest.c b/kd-forest.c
deleted file mode 100644
index 3840a61..0000000
--- a/kd-forest.c
+++ /dev/null
@@ -1,327 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "kd-forest.h"
-#include "util.h"
-#include <math.h>
-#include <stdbool.h>
-#include <stdlib.h>
-#include <string.h>
-
-kd_node_t *
-new_kd_node(double coords[KD_DIMEN], unsigned int x, unsigned int y)
-{
-  kd_node_t *node = xmalloc(sizeof(kd_node_t));
-  memcpy(node->coords, coords, sizeof(node->coords));
-  node->left = node->right = NULL;
-  node->x = x;
-  node->y = y;
-  node->removed = false;
-  return node;
-}
-
-static void
-kd_destroy(kd_node_t *node)
-{
-  if (node) {
-    kd_destroy(node->left);
-    kd_destroy(node->right);
-    free(node);
-  }
-}
-
-static size_t
-kd_collect_nodes(kd_node_t *root, kd_node_t **buffer, bool include_removed)
-{
-  size_t count = 0;
-
-  if (include_removed || !root->removed) {
-    buffer[0] = root;
-    ++count;
-  }
-
-  if (root->left) {
-    count += kd_collect_nodes(root->left, buffer + count, include_removed);
-  }
-  if (root->right) {
-    count += kd_collect_nodes(root->right, buffer + count, include_removed);
-  }
-
-  if (root->removed && !include_removed) {
-    free(root);
-  }
-
-  return count;
-}
-
-typedef int kd_comparator(const void *a, const void* b);
-
-static int kd_compare0(const void *a, const void *b) {
-  double aval = (*(const kd_node_t **)a)->coords[0];
-  double bval = (*(const kd_node_t **)b)->coords[0];
-  return (aval > bval) - (aval < bval);
-}
-
-static int kd_compare1(const void *a, const void *b) {
-  double aval = (*(const kd_node_t **)a)->coords[1];
-  double bval = (*(const kd_node_t **)b)->coords[1];
-  return (aval > bval) - (aval < bval);
-}
-
-static int kd_compare2(const void *a, const void *b) {
-  double aval = (*(const kd_node_t **)a)->coords[2];
-  double bval = (*(const kd_node_t **)b)->coords[2];
-  return (aval > bval) - (aval < bval);
-}
-
-static kd_comparator *kd_comparators[KD_DIMEN] = {
-  kd_compare0,
-  kd_compare1,
-  kd_compare2,
-};
-
-// When building k-d trees, we use KD_DIMEN sorted arrays of nodes plus one
-// extra array for scratch space
-#define KD_BUFSIZE (KD_DIMEN + 1)
-
-static kd_node_t *
-kd_build_tree_recursive(kd_node_t **buffers[KD_BUFSIZE], size_t size, unsigned int coord)
-{
-  if (size == 0) {
-    return NULL;
-  }
-
-  size_t split = size/2;
-  size_t left_size = split, right_size = size - left_size - 1;
-  kd_node_t *root = buffers[coord][split];
-  for (size_t i = 0; i < size; ++i) {
-    buffers[coord][i]->is_left = i < left_size;
-  }
-
-  kd_node_t **right_buffers[KD_BUFSIZE];
-  for (int i = 0; i < KD_DIMEN; ++i) {
-    right_buffers[i] = buffers[i] + left_size + 1;
-  }
-
-  kd_node_t **scratch = buffers[KD_DIMEN];
-  right_buffers[KD_DIMEN] = scratch;
-
-  for (size_t i = 0; i < KD_DIMEN; ++i) {
-    if (i == coord) {
-      continue;
-    }
-
-    kd_node_t **buffer = buffers[i];
-    kd_node_t **right_buffer = right_buffers[i];
-    for (size_t j = 0, k = 0, skip = 0; j < size; ++j) {
-      if (buffer[j]->is_left) {
-        buffer[j - skip] = buffer[j];
-      } else {
-        if (buffer[j] != root) {
-          scratch[k] = buffer[j];
-          ++k;
-        }
-        ++skip;
-      }
-    }
-    for (size_t j = 0; j < right_size; ++j) {
-      right_buffer[j] = scratch[j];
-    }
-  }
-
-  coord = (coord + 1)%KD_DIMEN;
-  root->left = kd_build_tree_recursive(buffers, left_size, coord);
-  root->right = kd_build_tree_recursive(right_buffers, right_size, coord);
-
-  return root;
-}
-
-static kd_node_t *
-kd_build_tree(kd_node_t **buffers[KD_BUFSIZE], size_t size)
-{
-  for (int i = 1; i < KD_DIMEN; ++i) {
-    memcpy(buffers[i], buffers[0], size*sizeof(kd_node_t *));
-  }
-  for (int i = 0; i < KD_DIMEN; ++i) {
-    qsort(buffers[i], size, sizeof(kd_node_t *), kd_comparators[i]);
-  }
-  return kd_build_tree_recursive(buffers, size, 0);
-}
-
-static double
-kd_distance_sq(const double a[KD_DIMEN], const double b[KD_DIMEN])
-{
-  double result = 0.0;
-  for (int i = 0; i < KD_DIMEN; ++i) {
-    double d = a[i] - b[i];
-    result += d*d;
-  }
-  return result;
-}
-
-static void
-kd_find_nearest_recursive(kd_node_t *node, const double target[KD_DIMEN], const double closest[KD_DIMEN], kd_node_t **best, double *limit, unsigned int coord)
-{
-  if (!node->removed) {
-    double node_dist_sq = kd_distance_sq(node->coords, target);
-    if (node_dist_sq < *limit) {
-      *limit = node_dist_sq;
-      *best = node;
-    }
-  }
-
-  kd_node_t *first;
-  kd_node_t *second;
-  if (target[coord] < node->coords[coord]) {
-    first = node->left;
-    second = node->right;
-  } else {
-    first = node->right;
-    second = node->left;
-  }
-
-  unsigned int next = (coord + 1)%KD_DIMEN;
-
-  if (first) {
-    kd_find_nearest_recursive(first, target, closest, best, limit, next);
-  }
-
-  if (second) {
-    double new_closest[KD_DIMEN];
-    memcpy(new_closest, closest, sizeof(new_closest));
-    new_closest[coord] = node->coords[coord];
-
-    if (kd_distance_sq(new_closest, target) < *limit) {
-      kd_find_nearest_recursive(second, target, new_closest, best, limit, next);
-    }
-  }
-}
-
-static void
-kd_find_nearest(kd_node_t *root, const double target[KD_DIMEN], kd_node_t **best, double *limit)
-{
-  kd_find_nearest_recursive(root, target, target, best, limit, 0);
-}
-
-void
-kdf_init(kd_forest_t *kdf)
-{
-  kdf->roots = NULL;
-  kdf->size = kdf->size_est = 0;
-  kdf->roots_size = kdf->roots_capacity = 0;
-}
-
-void
-kdf_destroy(kd_forest_t *kdf)
-{
-  for (unsigned int i = 0; i < kdf->roots_size; ++i) {
-    kd_destroy(kdf->roots[i]);
-  }
-
-  free(kdf->roots);
-}
-
-static size_t
-kdf_collect_nodes(kd_forest_t *kdf, kd_node_t **buffer, unsigned int slot, bool include_removed)
-{
-  size_t count = 0;
-  for (unsigned int i = 0; i < slot; ++i) {
-    if (kdf->roots[i]) {
-      count += kd_collect_nodes(kdf->roots[i], buffer + count, include_removed);
-    }
-  }
-  return count;
-}
-
-static void
-kdf_balance(kd_forest_t *kdf, kd_node_t *new_node, bool force)
-{
-  ++kdf->size;
-
-  size_t slot, buffer_size;
-  if (force) {
-    buffer_size = kdf->size_est = kdf->size;
-    slot = kdf->roots_size;
-  } else {
-    ++kdf->size_est;
-    for (slot = 0; slot < kdf->roots_size; ++slot) {
-      if (!kdf->roots[slot]) {
-        break;
-      }
-    }
-    buffer_size = 1 << slot;
-  }
-
-  kd_node_t **buffer = xmalloc(buffer_size*sizeof(kd_node_t *));
-  buffer[0] = new_node;
-  kdf_collect_nodes(kdf, buffer + 1, slot, !force);
-
-  kd_node_t **buffers[KD_BUFSIZE];
-  for (int i = 1; i < KD_BUFSIZE; ++i) {
-    buffers[i] = xmalloc(buffer_size*sizeof(kd_node_t *));
-  }
-
-  if (slot >= kdf->roots_capacity) {
-    kdf->roots_capacity = slot + 1;
-    kdf->roots = xrealloc(kdf->roots, kdf->roots_capacity*sizeof(kd_node_t *));
-  }
-
-  size_t i, offset;
-  for (i = 0, offset = 0; offset < buffer_size; ++i) {
-    size_t chunk_size = 1 << i;
-    if (buffer_size & chunk_size) {
-      buffers[0] = buffer + offset;
-      kdf->roots[i] = kd_build_tree(buffers, chunk_size);
-      offset |= chunk_size;
-    } else {
-      kdf->roots[i] = NULL;
-    }
-  }
-  if (force || i > kdf->roots_size) {
-    kdf->roots_size = i;
-  }
-
-  free(buffer);
-  for (i = 1; i < KD_BUFSIZE; ++i) {
-    free(buffers[i]);
-  }
-}
-
-void
-kdf_insert(kd_forest_t *kdf, kd_node_t *node)
-{
-  // If half or more of the nodes are removed, force a complete rebalance
-  bool force = (kdf->size_est + 1) >= 2*(kdf->size + 1);
-  kdf_balance(kdf, node, force);
-}
-
-void
-kdf_remove(kd_forest_t *kdf, kd_node_t *node)
-{
-  --kdf->size;
-  node->removed = true;
-}
-
-kd_node_t *
-kdf_find_nearest(const kd_forest_t *kdf, const double target[KD_DIMEN])
-{
-  double limit = INFINITY;
-  kd_node_t *best = NULL;
-
-  for (unsigned int i = 0; i < kdf->roots_size; ++i) {
-    kd_node_t *root = kdf->roots[i];
-    if (root != NULL) {
-      kd_find_nearest(root, target, &best, &limit);
-    }
-  }
-
-  return best;
-}
diff --git a/kd-forest.h b/kd-forest.h
deleted file mode 100644
index 3651bfe..0000000
--- a/kd-forest.h
+++ /dev/null
@@ -1,56 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#ifndef KD_FOREST_H
-#define KD_FOREST_H
-
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-
-#define KD_DIMEN 3
-
-// Single node in a k-d tree
-typedef struct kd_node_t {
-  // Node coordinates
-  double coords[KD_DIMEN];
-  // Sub-trees
-  struct kd_node_t *left, *right;
-  // Used to keep track of which sub-tree a node is in during construction
-  bool is_left;
-  // Weak delete support
-  bool removed;
-
-  // Corresponding image position for this node
-  unsigned int x, y;
-} kd_node_t;
-
-kd_node_t *new_kd_node(double coords[KD_DIMEN], unsigned int x, unsigned int y);
-
-// A forest of k-d trees
-typedef struct {
-  // Array of k-d tree roots
-  kd_node_t **roots;
-  // Size and capacity of the roots array
-  unsigned int roots_size, roots_capacity;
-  // The actual size of this tree
-  size_t size;
-  // The size estimate for this tree, counting removed nodes
-  size_t size_est;
-} kd_forest_t;
-
-void kdf_init(kd_forest_t *kdf);
-void kdf_destroy(kd_forest_t *kdf);
-void kdf_insert(kd_forest_t *kdf, kd_node_t *node);
-void kdf_remove(kd_forest_t *kdf, kd_node_t *node);
-kd_node_t *kdf_find_nearest(const kd_forest_t *kdf, const double target[KD_DIMEN]);
-
-#endif // KD_FOREST_H
diff --git a/main.c b/main.c
deleted file mode 100644
index 109f9f6..0000000
--- a/main.c
+++ /dev/null
@@ -1,480 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "color.h"
-#include "generate.h"
-#include "kd-forest.h"
-#include "options.h"
-#include "util.h"
-#include <math.h>
-#include <png.h>
-#include <setjmp.h>
-#include <stdarg.h>
-#include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#if __unix__
-#  include <unistd.h>
-#endif
-
-// A single pixel in all its glory
-typedef struct {
-  double value[KD_DIMEN];
-  kd_node_t *node;
-  unsigned int x, y;
-  bool filled;
-} pixel_t;
-
-// All-encompasing state struct
-typedef struct {
-  const options_t *options;
-  uint32_t *colors;
-  pixel_t *pixels;
-  png_byte **bitmap;
-  unsigned int iteration;
-  unsigned int update_interval;
-  unsigned int frame;
-  size_t max_boundary;
-} state_t;
-
-static void init_state(state_t *state, const options_t *options);
-static void generate_image(state_t *state);
-static void destroy_state(state_t *state);
-
-// Entry point
-int
-main(int argc, char *argv[])
-{
-  options_t options;
-  if (!parse_options(&options, argc, argv)) {
-    fprintf(stderr, "\n");
-    print_usage(stderr, argv[0], options.help);
-    return EXIT_FAILURE;
-  }
-
-  if (options.help) {
-    print_usage(stdout, argv[0], true);
-    return EXIT_SUCCESS;
-  }
-
-  state_t state;
-  init_state(&state, &options);
-  generate_image(&state);
-  destroy_state(&state);
-  return EXIT_SUCCESS;
-}
-
-static pixel_t *
-create_pixels(const options_t *options)
-{
-  pixel_t *pixels = xmalloc(options->npixels*sizeof(pixel_t));
-  for (unsigned int y = 0, i = 0; y < options->height; ++y) {
-    for (unsigned int x = 0; x < options->width; ++x, ++i) {
-      pixel_t *pixel = pixels + i;
-      pixel->node = NULL;
-      pixel->x = x;
-      pixel->y = y;
-      pixel->filled = false;
-    }
-  }
-  return pixels;
-}
-
-static png_byte **
-create_bitmap(const options_t *options)
-{
-  png_byte **rows = xmalloc(options->height*sizeof(png_byte *));
-  const size_t row_size = 4*options->width*sizeof(png_byte);
-  for (unsigned int i = 0; i < options->height; ++i) {
-    rows[i] = xmalloc(row_size);
-    memset(rows[i], 0, row_size);
-  }
-  return rows;
-}
-
-static void
-init_state(state_t *state, const options_t *options)
-{
-  printf("Generating a %u-bit, %ux%u image (%zu pixels)\n",
-         options->bit_depth, options->width, options->height, options->npixels);
-
-  xsrand(options->seed);
-
-  state->options = options;
-  state->colors = generate_colors(options);
-  state->pixels = create_pixels(options);
-  state->bitmap = create_bitmap(options);
-  state->iteration = 0;
-  state->update_interval = 1U << (state->options->bit_depth + 1)/2;
-  state->frame = 0;
-  state->max_boundary = 0;
-}
-
-static void generate_bitmap(state_t *state);
-static void write_png(const state_t *state, const char *filename);
-
-static void
-generate_image(state_t *state)
-{
-  generate_bitmap(state);
-
-  if (!state->options->animate) {
-    write_png(state, state->options->filename);
-  }
-}
-
-static void
-destroy_state(state_t *state)
-{
-  for (unsigned int i = 0; i < state->options->height; ++i) {
-    free(state->bitmap[i]);
-  }
-  free(state->bitmap);
-  free(state->pixels);
-  free(state->colors);
-}
-
-static pixel_t *
-get_pixel(const state_t *state, unsigned int x, unsigned int y)
-{
-  return state->pixels + state->options->width*y + x;
-}
-
-static pixel_t *
-try_neighbor(const state_t *state, pixel_t *pixel, int dx, int dy)
-{
-  if (dx < 0 && pixel->x < -dx) {
-    return NULL;
-  } else if (dx > 0 && pixel->x + dx >= state->options->width) {
-    return NULL;
-  } else if (dy < 0 && pixel->y < -dy) {
-    return NULL;
-  } else if (dy > 0 && pixel->y + dy >= state->options->height) {
-    return NULL;
-  }
-
-  return pixel + (int)state->options->width*dy + dx;
-}
-
-static unsigned int
-get_all_neighbors(const state_t *state, pixel_t *pixel, pixel_t *neighbors[8])
-{
-  unsigned int size = 0;
-
-  for (int dy = -1; dy <= 1; ++dy) {
-    for (int dx = -1; dx <= 1; ++dx) {
-      if (dx == 0 && dy == 0) {
-        continue;
-      }
-
-      pixel_t *neighbor = try_neighbor(state, pixel, dx, dy);
-      if (neighbor) {
-        neighbors[size++] = neighbor;
-      }
-    }
-  }
-
-  return size;
-}
-
-static unsigned int
-get_neighbors(const state_t *state, pixel_t *pixel, pixel_t *neighbors[8], bool filled)
-{
-  unsigned int size = 0;
-
-  for (int dy = -1; dy <= 1; ++dy) {
-    for (int dx = -1; dx <= 1; ++dx) {
-      if (dx == 0 && dy == 0) {
-        continue;
-      }
-
-      pixel_t *neighbor = try_neighbor(state, pixel, dx, dy);
-      if (neighbor && neighbor->filled == filled) {
-        neighbors[size++] = neighbor;
-      }
-    }
-  }
-
-  return size;
-}
-
-static pixel_t *
-select_empty_neighbor(const state_t *state, pixel_t *pixel)
-{
-  pixel_t *neighbors[8];
-  unsigned int size = get_neighbors(state, pixel, neighbors, false);
-  return neighbors[xrand(size)];
-}
-
-static pixel_t *
-find_next_pixel(const state_t *state, const kd_forest_t *kdf, const double target[KD_DIMEN])
-{
-  kd_node_t *nearest = kdf_find_nearest(kdf, target);
-  pixel_t *pixel = get_pixel(state, nearest->x, nearest->y);
-
-  if (state->options->selection == SELECTION_MIN) {
-    pixel = select_empty_neighbor(state, pixel);
-  }
-
-  return pixel;
-}
-
-static void
-ensure_pixel_removed(kd_forest_t *kdf, pixel_t *pixel)
-{
-  if (pixel->node) {
-    kdf_remove(kdf, pixel->node);
-    pixel->node = NULL;
-  }
-}
-
-static bool
-has_empty_neighbors(const state_t *state, pixel_t *pixel)
-{
-  for (int dy = -1; dy <= 1; ++dy) {
-    for (int dx = -1; dx <= 1; ++dx) {
-      if (dx == 0 && dy == 0) {
-        continue;
-      }
-
-      pixel_t *neighbor = try_neighbor(state, pixel, dx, dy);
-      if (neighbor && !neighbor->filled) {
-        return true;
-      }
-    }
-  }
-
-  return false;
-}
-
-static void
-insert_new_pixel_min(state_t *state, kd_forest_t *kdf, pixel_t *pixel)
-{
-  pixel->filled = true;
-
-  if (has_empty_neighbors(state, pixel)) {
-    pixel->node = new_kd_node(pixel->value, pixel->x, pixel->y);
-    kdf_insert(kdf, pixel->node);
-  }
-
-  pixel_t *neighbors[8];
-  unsigned int size = get_all_neighbors(state, pixel, neighbors);
-  for (unsigned int i = 0; i < size; ++i) {
-    pixel_t *neighbor = neighbors[i];
-    if (!has_empty_neighbors(state, neighbor)) {
-      ensure_pixel_removed(kdf, neighbor);
-    }
-  }
-}
-
-static void
-insert_new_pixel_mean(state_t *state, kd_forest_t *kdf, pixel_t *pixel)
-{
-  pixel->filled = true;
-  ensure_pixel_removed(kdf, pixel);
-
-  pixel_t *neighbors[8];
-  unsigned int size = get_neighbors(state, pixel, neighbors, false);
-  for (unsigned int i = 0; i < size; ++i) {
-    pixel_t *neighbor = neighbors[i];
-
-    double value[KD_DIMEN] = { 0.0 };
-
-    pixel_t *filled[8];
-    unsigned int nfilled = get_neighbors(state, neighbor, filled, true);
-    for (unsigned int j = 0; j < nfilled; ++j) {
-      for (unsigned int k = 0; k < KD_DIMEN; ++k) {
-        value[k] += filled[j]->value[k];
-      }
-    }
-
-    for (unsigned int j = 0; j < KD_DIMEN; ++j) {
-      value[j] /= nfilled;
-    }
-
-    ensure_pixel_removed(kdf, neighbor);
-    neighbor->node = new_kd_node(value, neighbor->x, neighbor->y);
-    kdf_insert(kdf, neighbor->node);
-  }
-}
-
-static void
-insert_new_pixel(state_t *state, kd_forest_t *kdf, pixel_t *pixel)
-{
-  switch (state->options->selection) {
-  case SELECTION_MIN:
-    insert_new_pixel_min(state, kdf, pixel);
-    break;
-
-  case SELECTION_MEAN:
-    insert_new_pixel_mean(state, kdf, pixel);
-    break;
-  }
-}
-
-static void
-print_progress(const char *format, ...)
-{
-#if __unix__
-  static bool tty_checked = false;
-  static bool tty = false;
-  if (!tty_checked) {
-    tty = isatty(STDOUT_FILENO);
-    tty_checked = true;
-  }
-  const char *clear_line = tty ? "\033[2K\r" : "";
-  const char *new_line = tty ? "" : "\n";
-#else
-  const char *clear_line = "";
-  const char *new_line = "\n";
-#endif
-
-  printf("%s", clear_line);
-
-  va_list args;
-  va_start(args, format);
-  vprintf(format, args);
-  va_end(args);
-
-  printf("%s", new_line);
-  fflush(stdout);
-}
-
-static void
-place_color(state_t *state, kd_forest_t *kdf, unsigned int i)
-{
-  if (state->iteration % state->update_interval == 0) {
-    if (state->options->animate) {
-      char filename[strlen(state->options->filename) + 10];
-      sprintf(filename, "%s/%04u.png", state->options->filename, state->frame);
-      write_png(state, filename);
-      ++state->frame;
-    }
-
-    print_progress("%.2f%%\t| boundary size: %zu\t| max boundary size: %zu",
-                   100.0*state->iteration/state->options->ncolors, kdf->size, state->max_boundary);
-  }
-
-  uint32_t color = state->colors[i];
-
-  double target[KD_DIMEN];
-  switch (state->options->color_space) {
-  case COLOR_SPACE_RGB:
-    color_set_RGB(target, color);
-    break;
-  case COLOR_SPACE_LAB:
-    color_set_Lab(target, color);
-    break;
-  case COLOR_SPACE_LUV:
-    color_set_Luv(target, color);
-    break;
-  }
-
-  pixel_t *pixel;
-  if (state->iteration == 0) {
-    pixel = get_pixel(state, state->options->x, state->options->y);
-  } else {
-    pixel = find_next_pixel(state, kdf, target);
-  }
-
-  memcpy(pixel->value, target, sizeof(target));
-  insert_new_pixel(state, kdf, pixel);
-  if (kdf->size > state->max_boundary) {
-    state->max_boundary = kdf->size;
-  }
-
-  png_byte *png_pixel = state->bitmap[pixel->y] + 4*pixel->x;
-  color_unpack(png_pixel, color);
-  png_pixel[3] = 0xFF;
-}
-
-static void
-generate_bitmap(state_t *state)
-{
-  // Make the forest
-  kd_forest_t kdf;
-  kdf_init(&kdf);
-
-  if (state->options->stripe) {
-    for (unsigned int i = 1; i <= state->options->bit_depth + 1; ++i) {
-      unsigned int stripe = 1 << i;
-      for (unsigned int j = stripe/2 - 1; j < state->options->ncolors; j += stripe, ++state->iteration) {
-        place_color(state, &kdf, j);
-      }
-    }
-  } else {
-    for (unsigned int i = 0; i < state->options->ncolors; ++i, ++state->iteration) {
-      place_color(state, &kdf, i);
-    }
-  }
-
-  if (state->options->animate) {
-    char filename[strlen(state->options->filename) + 10];
-
-#if __unix__
-    sprintf(filename, "%s/last.png", state->options->filename);
-    write_png(state, filename);
-
-    for (int i = 0; i < 120; ++i) {
-      sprintf(filename, "%s/%04u.png", state->options->filename, state->frame + i);
-      if (symlink("last.png", filename) != 0) {
-        abort();
-      }
-    }
-#else
-    for (int i = 0; i < 120; ++i) {
-      sprintf(filename, "%s/%04u.png", state->options->filename, state->frame + i);
-      write_png(state, filename);
-    }
-#endif
-  }
-
-  print_progress("%.2f%%\t| boundary size: %zu\t| max boundary size: %zu\n",
-                 100.0, kdf.size, state->max_boundary);
-
-  kdf_destroy(&kdf);
-}
-
-static void
-write_png(const state_t *state, const char *filename)
-{
-  FILE *file = fopen(filename, "wb");
-  if (!file) {
-    abort();
-  }
-
-  png_struct *png_ptr =
-    png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);
-  if (!png_ptr) {
-    abort();
-  }
-
-  png_info *info_ptr = png_create_info_struct(png_ptr);
-  if (!info_ptr) {
-    abort();
-  }
-
-  // libpng will longjmp here if it encounters an error from now on
-  if (setjmp(png_jmpbuf(png_ptr))) {
-    abort();
-  }
-
-  png_init_io(png_ptr, file);
-  png_set_IHDR(png_ptr, info_ptr, state->options->width, state->options->height, 8,
-               PNG_COLOR_TYPE_RGBA, PNG_INTERLACE_ADAM7,
-               PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);
-  png_set_sRGB_gAMA_and_cHRM(png_ptr, info_ptr, PNG_sRGB_INTENT_ABSOLUTE);
-  png_set_rows(png_ptr, info_ptr, state->bitmap);
-  png_write_png(png_ptr, info_ptr, PNG_TRANSFORM_IDENTITY, NULL);
-  png_destroy_write_struct(&png_ptr, &info_ptr);
-  fclose(file);
-}
diff --git a/options.c b/options.c
deleted file mode 100644
index e25930a..0000000
--- a/options.c
+++ /dev/null
@@ -1,431 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "options.h"
-#include <ctype.h>
-#include <limits.h>
-#include <stdarg.h>
-#include <stdlib.h>
-#include <string.h>
-#if __unix__
-#  include <unistd.h>
-#endif
-
-static bool
-parse_arg(int argc, char *argv[],
-          const char *short_form, const char *long_form,
-          const char **value, int *i, bool *error)
-{
-  size_t short_len = short_form ? strlen(short_form) : 0;
-  size_t long_len = long_form ? strlen(long_form) : 0;
-
-  const char *actual_form;
-  const char *arg = argv[*i];
-  const char *candidate = NULL;
-
-  if (short_form && strncmp(arg, short_form, short_len) == 0) {
-    actual_form = short_form;
-    if (strlen(arg) > short_len) {
-      candidate = arg + short_len;
-    }
-  } else if (long_form && strncmp(arg, long_form, long_len) == 0) {
-    actual_form = long_form;
-    if (strlen(arg) > long_len) {
-      if (arg[long_len] == '=') {
-        candidate = arg + long_len + 1;
-      } else {
-        return false;
-      }
-    }
-  } else {
-    return false;
-  }
-
-  if (value) {
-    if (candidate) {
-      *value = candidate;
-    } else if (*i < argc - 1) {
-      ++*i;
-      *value = argv[*i];
-    } else {
-      fprintf(stderr, "Expected a value for %s\n", arg);
-      *error = true;
-      return false;
-    }
-  } else if (candidate) {
-    fprintf(stderr, "Unexpected value for %s: `%s'\n",
-            actual_form, candidate);
-    *error = true;
-    return false;
-  }
-
-  return true;
-}
-
-static bool
-str_to_uint(const char *str, unsigned int *value)
-{
-  char *endptr;
-  long result = strtol(str, &endptr, 10);
-  if (*str == '\0' || *endptr != '\0') {
-    return false;
-  }
-  if (result < 0 || result > UINT_MAX) {
-    return false;
-  }
-
-  *value = result;
-  return true;
-}
-
-static void
-strcatinc(char **destp, const char *src)
-{
-  strcpy(*destp, src);
-  *destp += strlen(src);
-}
-
-typedef enum {
-  COLORIZE_NORMAL,
-  COLORIZE_AT,
-  COLORIZE_BANG,
-  COLORIZE_STAR,
-  COLORIZE_SHORT_OPTION,
-  COLORIZE_LONG_OPTION,
-} colorize_state_t;
-
-static void
-print_colorized(FILE *file, bool tty, const char *format, ...)
-{
-  const char *bold = tty ? "\033[1m" : "";
-  const char *red = tty ? "\033[1;31m" : "";
-  const char *green = tty ? "\033[1;32m" : "";
-  const char *normal = tty ? "\033[0m" : "";
-
-  size_t size = strlen(format) + 1;
-  char colorized[16*size];
-  char *builder = colorized;
-
-  colorize_state_t state = COLORIZE_NORMAL;
-  for (size_t i = 0; i < size; ++i) {
-    char c = format[i];
-
-    if (c == '\\') {
-      *builder++ = format[++i];
-      continue;
-    }
-
-    switch (state) {
-    case COLORIZE_AT:
-      if (c == '@') {
-        strcatinc(&builder, normal);
-        state = COLORIZE_NORMAL;
-      } else {
-        *builder++ = c;
-      }
-      break;
-
-    case COLORIZE_BANG:
-      if (c == '!') {
-        strcatinc(&builder, normal);
-        state = COLORIZE_NORMAL;
-      } else {
-        *builder++ = c;
-      }
-      break;
-
-    case COLORIZE_STAR:
-      if (c == '*') {
-        strcatinc(&builder, normal);
-        state = COLORIZE_NORMAL;
-      } else {
-        *builder++ = c;
-      }
-      break;
-
-    case COLORIZE_SHORT_OPTION:
-      *builder++ = c;
-      strcatinc(&builder, normal);
-      state = COLORIZE_NORMAL;
-      break;
-
-    case COLORIZE_LONG_OPTION:
-      if (!isalpha(c) && c != '-') {
-        strcatinc(&builder, normal);
-        state = COLORIZE_NORMAL;
-      }
-      *builder++ = c;
-      break;
-
-    default:
-      switch (c) {
-      case '@':
-        state = COLORIZE_AT;
-        strcatinc(&builder, green);
-        break;
-
-      case '!':
-        state = COLORIZE_BANG;
-        strcatinc(&builder, bold);
-        break;
-
-      case '*':
-        state = COLORIZE_STAR;
-        strcatinc(&builder, red);
-        break;
-
-      case '-':
-        if (c == '-') {
-          if (format[i + 1] == '-') {
-            state = COLORIZE_LONG_OPTION;
-          } else {
-            state = COLORIZE_SHORT_OPTION;
-          }
-          strcatinc(&builder, red);
-        }
-        *builder++ = c;
-        break;
-
-      default:
-        *builder++ = c;
-        break;
-      }
-      break;
-    }
-  }
-
-  va_list args;
-  va_start(args, format);
-  vprintf(colorized, args);
-  va_end(args);
-}
-
-void
-print_usage(FILE *file, const char *command, bool verbose)
-{
-#if __unix__
-  bool tty = isatty(fileno(file));
-#else
-  bool tty = false;
-#endif
-
-  size_t length = strlen(command);
-  char whitespace[length + 1];
-  memset(whitespace, ' ', length);
-  whitespace[length] = '\0';
-
-#define usage(...) print_colorized(file, tty, __VA_ARGS__)
-  usage("Usage:\n");
-  usage("  !$! *%s* [-b|--bit-depth @DEPTH@]\n", command);
-  usage("    %s [-s|--hue-sort] [-r|--random] [-M|--morton] [-H|--hilbert]\n", whitespace);
-  usage("    %s [-t|--stripe] [-T|--no-stripe]\n", whitespace);
-  usage("    %s [-l|--selection @min@|@mean@]\n", whitespace);
-  usage("    %s [-c|--color-space @RGB@|@Lab@|@Luv@]\n", whitespace);
-  usage("    %s [-w|--width @WIDTH@] [-h|--height @HEIGHT@]\n", whitespace);
-  usage("    %s [-x @X@] [-y @Y@]\n", whitespace);
-  usage("    %s [-a|--animate]\n", whitespace);
-  usage("    %s [-o|--output @PATH@]\n", whitespace);
-  usage("    %s [-e|--seed @SEED@]\n", whitespace);
-  usage("    %s [-?|--help]\n", whitespace);
-
-  if (!verbose) {
-    return;
-  }
-
-  usage("\n");
-  usage("  -b, --bit-depth @DEPTH@:\n");
-  usage("          Use all @DEPTH@\\-bit colors (!default!: @24@)\n\n");
-  usage("  -s, --hue-sort:\n");
-  usage("          Sort colors by hue (!default!)\n");
-  usage("  -r, --random:\n");
-  usage("          Randomize colors\n");
-  usage("  -M, --morton:\n");
-  usage("          Place colors in Morton order (Z\\-order)\n");
-  usage("  -H, --hilbert:\n");
-  usage("          Place colors in Hilbert curve order\n\n");
-  usage("  -t, --stripe:\n");
-  usage("  -T, --no-stripe:\n");
-  usage("          Whether to reduce artifacts by iterating through the colors in\n");
-  usage("          multiple stripes (!default!: --stripe)\n\n");
-  usage("  -l, --selection @min@|@mean@:\n");
-  usage("          Specify the selection mode (!default!: @min@)\n\n");
-  usage("          @min@:  Pick the pixel with the closest neighboring pixel\n");
-  usage("          @mean@: Pick the pixel with the closest average of all its neighbors\n\n");
-  usage("  -c, --color-space @RGB@|@Lab@|@Luv@:\n");
-  usage("          Use the given color space (!default!: @Lab@)\n\n");
-  usage("  -w, --width @WIDTH@\n");
-  usage("  -h, --height @HEIGHT@:\n");
-  usage("          Generate a @WIDTH@x@HEIGHT@ image (!default!: @as small as possible@)\n\n");
-  usage("  -x @X@\n");
-  usage("  -y @Y@:\n");
-  usage("          Place the first pixel at (@X@, @Y@) (!default!: @center@)\n\n");
-  usage("  -a, --animate:\n");
-  usage("          Generate frames of an animation\n\n");
-  usage("  -o, --output @PATH@:\n");
-  usage("          Output a PNG file at @PATH@ (!default!: @kd\\-forest.png@)\n\n");
-  usage("          If -a/--animate is specified, this is treated as a directory which\n");
-  usage("          will hold many frames\n\n");
-  usage("  -e, --seed @SEED@:\n");
-  usage("          Seed the random number generator (!default!: @0@)\n\n");
-  usage("  -?, --help:\n");
-  usage("          Show this message\n");
-#undef usage
-}
-
-bool
-parse_options(options_t *options, int argc, char *argv[])
-{
-  // Set defaults
-  options->bit_depth = 24;
-  options->mode = MODE_HUE_SORT;
-  options->stripe = true;
-  options->selection = SELECTION_MIN;
-  options->color_space = COLOR_SPACE_LAB;
-  options->animate = false;
-  options->filename = NULL;
-  options->seed = 0;
-  options->help = false;
-
-  bool width_set = false, height_set = false;
-  bool x_set = false, y_set = false;
-  bool result = true;
-
-  for (int i = 1; i < argc; ++i) {
-    const char *value;
-    bool error = false;
-
-    if (parse_arg(argc, argv, "-b", "--bit-depth", &value, &i, &error)) {
-      if (!str_to_uint(value, &options->bit_depth)
-          || options->bit_depth <= 1
-          || options->bit_depth > 24) {
-        fprintf(stderr, "Invalid bit depth: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-s", "--hue-sort", NULL, &i, &error)) {
-      options->mode = MODE_HUE_SORT;
-    } else if (parse_arg(argc, argv, "-r", "--random", NULL, &i, &error)) {
-      options->mode = MODE_RANDOM;
-    } else if (parse_arg(argc, argv, "-M", "--morton", NULL, &i, &error)) {
-      options->mode = MODE_MORTON;
-    } else if (parse_arg(argc, argv, "-H", "--hilbert", NULL, &i, &error)) {
-      options->mode = MODE_HILBERT;
-    } else if (parse_arg(argc, argv, "-t", "--stripe", NULL, &i, &error)) {
-      options->stripe = true;
-    } else if (parse_arg(argc, argv, "-T", "--no-stripe", NULL, &i, &error)) {
-      options->stripe = false;
-    } else if (parse_arg(argc, argv, "-l", "--selection", &value, &i, &error)) {
-      if (strcmp(value, "min") == 0) {
-        options->selection = SELECTION_MIN;
-      } else if (strcmp(value, "mean") == 0) {
-        options->selection = SELECTION_MEAN;
-      } else {
-        fprintf(stderr, "Invalid selection mode: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-c", "--color-space", &value, &i, &error)) {
-      if (strcmp(value, "RGB") == 0) {
-        options->color_space = COLOR_SPACE_RGB;
-      } else if (strcmp(value, "Lab") == 0) {
-        options->color_space = COLOR_SPACE_LAB;
-      } else if (strcmp(value, "Luv") == 0) {
-        options->color_space = COLOR_SPACE_LUV;
-      } else {
-        fprintf(stderr, "Invalid color space: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-w", "--width", &value, &i, &error)) {
-      if (str_to_uint(value, &options->width)) {
-        width_set = true;
-      } else {
-        fprintf(stderr, "Invalid width: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-h", "--height", &value, &i, &error)) {
-      if (str_to_uint(value, &options->height)) {
-        height_set = true;
-      } else {
-        fprintf(stderr, "Invalid height: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-x", NULL, &value, &i, &error)) {
-      if (str_to_uint(value, &options->x)) {
-        x_set = true;
-      } else {
-        fprintf(stderr, "Invalid x coordinate: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-y", NULL, &value, &i, &error)) {
-      if (str_to_uint(value, &options->y)) {
-        y_set = true;
-      } else {
-        fprintf(stderr, "Invalid y coordinate: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-a", "--animate", NULL, &i, &error)) {
-      options->animate = true;
-    } else if (parse_arg(argc, argv, "-o", "--output", &value, &i, &error)) {
-      options->filename = value;
-    } else if (parse_arg(argc, argv, "-e", "--seed", &value, &i, &error)) {
-      if (!str_to_uint(value, &options->seed)) {
-        fprintf(stderr, "Invalid random seed: `%s'\n", value);
-        error = true;
-      }
-    } else if (parse_arg(argc, argv, "-?", "--help", NULL, &i, &error)) {
-      options->help = true;
-    } else if (!error) {
-      fprintf(stderr, "Unexpected argument `%s'\n", argv[i]);
-      error = true;
-    }
-
-    if (error) {
-      result = false;
-    }
-  }
-
-  options->ncolors = (size_t)1 << options->bit_depth;
-
-  if (!width_set && !height_set) {
-    // Round width up to make widescreen the default
-    options->width = 1U << (options->bit_depth + 1)/2;
-    options->height = 1U << options->bit_depth/2;
-  } else if (width_set && !height_set) {
-    options->height = (options->ncolors + options->width - 1)/options->width;
-  } else if (!width_set && height_set) {
-    options->width = (options->ncolors + options->height - 1)/options->height;
-  }
-
-  options->npixels = (size_t)options->width*options->height;
-  if (options->npixels < options->ncolors) {
-    fprintf(stderr, "Image too small (at least %zu pixels needed)\n", options->ncolors);
-    result = false;
-  }
-
-  if (!x_set) {
-    options->x = options->width/2;
-  } else if (options->x >= options->width) {
-    fprintf(stderr, "-x coordinate too big, should be less than %u\n", options->width);
-    result = false;
-  }
-
-  if (!y_set) {
-    options->y = options->height/2;
-  } else if (options->y >= options->height) {
-    fprintf(stderr, "-y coordinate too big, should be less than %u\n", options->height);
-    result = false;
-  }
-
-  // Default filename depends on -a flag
-  if (!options->filename) {
-    options->filename = options->animate ? "frames" : "kd-forest.png";
-  }
-
-  return result;
-}
diff --git a/options.h b/options.h
deleted file mode 100644
index 07ecc45..0000000
--- a/options.h
+++ /dev/null
@@ -1,58 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#ifndef OPTIONS_H
-#define OPTIONS_H
-
-#include <stdbool.h>
-#include <stdio.h>
-
-// Possible generation modes
-typedef enum {
-  MODE_HUE_SORT,
-  MODE_RANDOM,
-  MODE_MORTON,
-  MODE_HILBERT,
-} mode_t;
-
-// Possible pixel selection modes
-typedef enum {
-  SELECTION_MIN,
-  SELECTION_MEAN,
-} selection_t;
-
-// Possible color spaces
-typedef enum {
-  COLOR_SPACE_RGB,
-  COLOR_SPACE_LAB,
-  COLOR_SPACE_LUV,
-} color_space_t;
-
-// Command-line options
-typedef struct {
-  unsigned int bit_depth;
-  mode_t mode;
-  bool stripe;
-  selection_t selection;
-  color_space_t color_space;
-  unsigned int width, height;
-  size_t ncolors, npixels;
-  unsigned int x, y;
-  bool animate;
-  const char *filename;
-  unsigned int seed;
-  bool help;
-} options_t;
-
-bool parse_options(options_t *options, int argc, char *argv[]);
-void print_usage(FILE *file, const char *command, bool verbose);
-
-#endif // OPTIONS_H
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..f328e4d
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1 @@
+fn main() {}
diff --git a/util.c b/util.c
deleted file mode 100644
index a2573a4..0000000
--- a/util.c
+++ /dev/null
@@ -1,66 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#include "util.h"
-#include <stdlib.h>
-
-void *
-xmalloc(size_t size)
-{
-  void *ret = malloc(size);
-  if (!ret) {
-    abort();
-  }
-  return ret;
-}
-
-void *
-xrealloc(void *ptr, size_t size)
-{
-  void *ret = realloc(ptr, size);
-  if (!ret) {
-    abort();
-  }
-  return ret;
-}
-
-// Based on sample rand() implementation from POSIX.1-2001
-
-static unsigned long xrand_next = 0;
-
-void xsrand(unsigned int seed) {
-  xrand_next = seed;
-}
-
-static unsigned int xrand_simple(void) {
-  xrand_next = xrand_next*1103515245 + 12345;
-  return (unsigned int)(xrand_next/65536)%32768;
-}
-
-static unsigned int xrand_full(void) {
-  unsigned int low = xrand_simple();
-  unsigned int high = xrand_simple();
-  return low | (high << 15);
-}
-
-#define XRAND_RANGE 1073741824U
-
-unsigned int
-xrand(unsigned int range)
-{
-  // Compensate for bias if XRAND_RANGE isn't a multiple of range
-  unsigned int limit = XRAND_RANGE - XRAND_RANGE%range;
-  unsigned int res;
-  do {
-    res = xrand_full();
-  } while (res >= limit);
-  return res%range;
-}
diff --git a/util.h b/util.h
deleted file mode 100644
index 9cb5013..0000000
--- a/util.h
+++ /dev/null
@@ -1,23 +0,0 @@
-/*********************************************************************
- * kd-forest                                                         *
- * Copyright (C) 2014 Tavian Barnes <tavianator@tavianator.com>      *
- *                                                                   *
- * This program is free software. It comes without any warranty, to  *
- * the extent permitted by applicable law. You can redistribute it   *
- * and/or modify it under the terms of the Do What The Fuck You Want *
- * To Public License, Version 2, as published by Sam Hocevar. See    *
- * the COPYING file or http://www.wtfpl.net/ for more details.       *
- *********************************************************************/
-
-#ifndef UTIL_H
-#define UTIL_H
-
-#include <stddef.h>
-
-void *xmalloc(size_t size);
-void *xrealloc(void *ptr, size_t size);
-
-unsigned int xrand(unsigned int range);
-void xsrand(unsigned int seed);
-
-#endif // UTIL_H