Add support for Morton order.

7 files changed, 106 insertions, 43 deletions

diff --git a/Makefile b/Makefile
index da25811..6041235 100644
--- a/Makefile
+++ b/Makefile
@@ -15,12 +15,12 @@ LDFLAGS = -Wl,-O1,--sort-common,--as-needed,-z,relro
 LIBS = -lm -lpng
 RM = rm -f
 
-DEPS = Makefile color.h kd-forest.h options.h util.h
+DEPS = Makefile color.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 kd-forest.o main.o options.o util.o
+kd-forest: color.o generate.o kd-forest.o main.o options.o util.o
 	$(CC) $(CFLAGS) $(LDFLAGS) $^ $(LIBS) -o kd-forest
 
 %.o: %.c $(DEPS)
diff --git a/color.h b/color.h
index 6fec82d..0abafbd 100644
--- a/color.h
+++ b/color.h
@@ -12,7 +12,6 @@
 #ifndef COLOR_H
 #define COLOR_H
 
-#include "kd-forest.h"
 #include <stdint.h>
 
 // Unpack a color into 8-bit RGB values
diff --git a/generate.c b/generate.c
new file mode 100644
index 0000000..6b7e925
--- /dev/null
+++ b/generate.c
@@ -0,0 +1,77 @@
+/*********************************************************************
+ * 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 "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;
+
+    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
new file mode 100644
index 0000000..2b78150
--- /dev/null
+++ b/generate.h
@@ -0,0 +1,21 @@
+/*********************************************************************
+ * 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/main.c b/main.c
index 94a0780..055c854 100644
--- a/main.c
+++ b/main.c
@@ -10,6 +10,7 @@
  *********************************************************************/
 
 #include "color.h"
+#include "generate.h"
 #include "kd-forest.h"
 #include "options.h"
 #include "util.h"
@@ -68,44 +69,6 @@ main(int argc, char *argv[])
   return EXIT_SUCCESS;
 }
 
-static uint32_t *
-create_colors(const options_t *options)
-{
-  const unsigned int bit_depth = options->bit_depth;
-
-  // From least to most perceptually important
-  const unsigned int bskip = 1U << (24 - bit_depth)/3;
-  const unsigned int rskip = 1U << (24 - bit_depth + 1)/3;
-  const unsigned int gskip = 1U << (24 - bit_depth + 2)/3;
-
-  uint32_t *colors = xmalloc(options->ncolors*sizeof(uint32_t));
-  for (unsigned int b = 0, i = 0; b < 0x100; b += bskip) {
-    for (unsigned int g = 0; g < 0x100; g += gskip) {
-      for (unsigned int r = 0; r < 0x100; r += rskip, ++i) {
-        colors[i] = (r << 16) | (g << 8) | b;
-      }
-    }
-  }
-
-  switch (options->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;
-  }
-
-  return colors;
-}
-
 static pixel_t *
 create_pixels(const options_t *options)
 {
@@ -143,7 +106,7 @@ init_state(state_t *state, const options_t *options)
   xsrand(options->seed);
 
   state->options = options;
-  state->colors = create_colors(options);
+  state->colors = generate_colors(options);
   state->pixels = create_pixels(options);
   state->bitmap = create_bitmap(options);
 }
diff --git a/options.c b/options.c
index 5a5b446..db48615 100644
--- a/options.c
+++ b/options.c
@@ -225,7 +225,7 @@ print_usage(FILE *file, const char *command, bool verbose)
 #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]\n", whitespace);
+  usage("    %s [-s|--hue-sort] [-r|--random] [-M|--morton]\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);
@@ -303,6 +303,8 @@ parse_options(options_t *options, int argc, char *argv[])
       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, "-l", "--selection", &value, &i, &error)) {
       if (strcmp(value, "min") == 0) {
         options->selection = SELECTION_MIN;
diff --git a/options.h b/options.h
index 382f5fc..06ad69b 100644
--- a/options.h
+++ b/options.h
@@ -19,6 +19,7 @@
 typedef enum {
   MODE_HUE_SORT,
   MODE_RANDOM,
+  MODE_MORTON,
 } mode_t;
 
 // Possible pixel selection modes