From c653c8cda8f49d3bbe07190a6477367290ff7f04 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sun, 19 Apr 2020 16:28:10 -0400 Subject: Begin re-writing in Rust --- .gitattributes | 1 + .gitignore | 15 +- COPYING | 13 -- Cargo.lock | 5 + Cargo.toml | 5 + LICENSE | 12 ++ Makefile | 47 ------ color.c | 176 --------------------- color.h | 30 ---- generate.c | 82 ---------- generate.h | 21 --- hilbert.c | 170 -------------------- hilbert.h | 31 ---- kd-forest.c | 327 --------------------------------------- kd-forest.h | 56 ------- main.c | 480 --------------------------------------------------------- options.c | 431 --------------------------------------------------- options.h | 58 ------- src/main.rs | 1 + util.c | 66 -------- util.h | 23 --- 21 files changed, 36 insertions(+), 2014 deletions(-) create mode 100644 .gitattributes delete mode 100644 COPYING create mode 100644 Cargo.lock create mode 100644 Cargo.toml create mode 100644 LICENSE delete mode 100644 Makefile delete mode 100644 color.c delete mode 100644 color.h delete mode 100644 generate.c delete mode 100644 generate.h delete mode 100644 hilbert.c delete mode 100644 hilbert.h delete mode 100644 kd-forest.c delete mode 100644 kd-forest.h delete mode 100644 main.c delete mode 100644 options.c delete mode 100644 options.h create mode 100644 src/main.rs delete mode 100644 util.c delete mode 100644 util.h 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 - - 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 "] +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 + +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 # -# # -# 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 * - * * - * 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 - -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 * - * * - * 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 - -// 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 * - * * - * 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 - -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 * - * * - * 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 - -// 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 * - * * - * 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 - -// 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 * - * * - * 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 - -/** - * 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 * - * * - * 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 -#include -#include -#include - -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 * - * * - * 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 -#include -#include - -#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 * - * * - * 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 -#include -#include -#include -#include -#include -#include -#include -#if __unix__ -# include -#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 * - * * - * 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 -#include -#include -#include -#include -#if __unix__ -# include -#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 * - * * - * 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 -#include - -// 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 * - * * - * 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 - -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 * - * * - * 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 - -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 -- cgit v1.2.3