diff options
| -rw-r--r-- | .gitattributes | 1 | ||||
| -rw-r--r-- | .gitignore | 15 | ||||
| -rw-r--r-- | COPYING | 13 | ||||
| -rw-r--r-- | Cargo.lock | 5 | ||||
| -rw-r--r-- | Cargo.toml | 5 | ||||
| -rw-r--r-- | LICENSE | 12 | ||||
| -rw-r--r-- | Makefile | 47 | ||||
| -rw-r--r-- | color.c | 176 | ||||
| -rw-r--r-- | color.h | 30 | ||||
| -rw-r--r-- | generate.c | 82 | ||||
| -rw-r--r-- | generate.h | 21 | ||||
| -rw-r--r-- | hilbert.c | 170 | ||||
| -rw-r--r-- | hilbert.h | 31 | ||||
| -rw-r--r-- | kd-forest.c | 327 | ||||
| -rw-r--r-- | kd-forest.h | 56 | ||||
| -rw-r--r-- | main.c | 480 | ||||
| -rw-r--r-- | options.c | 431 | ||||
| -rw-r--r-- | options.h | 58 | ||||
| -rw-r--r-- | src/main.rs | 1 | ||||
| -rw-r--r-- | util.c | 66 | ||||
| -rw-r--r-- | util.h | 23 |
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 @@ -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" @@ -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 @@ -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() {} @@ -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; -} @@ -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 |