Modularize the libdimension codebase.

9 files changed, 760 insertions, 0 deletions

diff --git a/libdimension/internal/bvh.h b/libdimension/internal/bvh.h
new file mode 100644
index 0000000..c97e2ba
--- /dev/null
+++ b/libdimension/internal/bvh.h
@@ -0,0 +1,79 @@
+/*************************************************************************
+ * Copyright (C) 2012-2014 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file.
+ * Bounding volume hierarchy.  This generic interface allows different data
+ * structures to be represented in the same way, thus sharing code for their
+ * traversal algorithm.
+ */
+
+#ifndef DMNSN_INTERNAL_BVH_H
+#define DMNSN_INTERNAL_BVH_H
+
+#include "internal.h"
+#include "dimension/math.h"
+#include "dimension/model.h"
+#include <stdbool.h>
+
+/// A bounding volume hierarchy.
+typedef struct dmnsn_bvh dmnsn_bvh;
+
+/// Available BVH implementations.
+typedef enum dmnsn_bvh_kind {
+  DMNSN_BVH_NONE,
+  DMNSN_BVH_PRTREE,
+} dmnsn_bvh_kind;
+
+/// Create a BVH.
+DMNSN_INTERNAL dmnsn_bvh *dmnsn_new_bvh(const dmnsn_array *objects,
+                                        dmnsn_bvh_kind kind);
+/// Delete a BVH.
+DMNSN_INTERNAL void dmnsn_delete_bvh(dmnsn_bvh *bvh);
+
+/// Find the closest ray-object intersection in the tree.
+DMNSN_INTERNAL bool dmnsn_bvh_intersection(const dmnsn_bvh *bvh, dmnsn_ray ray, dmnsn_intersection *intersection, bool reset);
+/// Determine whether a point is inside any object in the tree.
+DMNSN_INTERNAL bool dmnsn_bvh_inside(const dmnsn_bvh *bvh, dmnsn_vector point);
+/// Return the bounding box of the whole hierarchy.
+DMNSN_INTERNAL dmnsn_aabb dmnsn_bvh_aabb(const dmnsn_bvh *bvh);
+
+/// A non-flat BVH representation, used by BVH implementations.
+typedef struct dmnsn_bvh_node {
+  dmnsn_aabb aabb;                   ///< The bounding box of this node.
+  dmnsn_object *object;              ///< The object, for leaf nodes.
+  unsigned int nchildren;            ///< How many children this node has.
+  unsigned int max_children;         ///< Maximum number of children.
+  struct dmnsn_bvh_node *children[]; ///< Flexible array of children.
+} dmnsn_bvh_node;
+
+/// Create a BVH node.
+DMNSN_INTERNAL dmnsn_bvh_node *dmnsn_new_bvh_node(unsigned int max_children);
+
+/// Create a BVH leaf node.
+DMNSN_INTERNAL dmnsn_bvh_node *dmnsn_new_bvh_leaf_node(dmnsn_object *object);
+
+/// Delete a BVH node.
+DMNSN_INTERNAL void dmnsn_delete_bvh_node(dmnsn_bvh_node *node);
+
+/// Add a child to a BVH node.
+DMNSN_INTERNAL void dmnsn_bvh_node_add(dmnsn_bvh_node *parent, dmnsn_bvh_node *child);
+
+#endif // DMNSN_INTERNAL_BVH_H
diff --git a/libdimension/internal/compiler.h b/libdimension/internal/compiler.h
new file mode 100644
index 0000000..e3555a4
--- /dev/null
+++ b/libdimension/internal/compiler.h
@@ -0,0 +1,71 @@
+/*************************************************************************
+ * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * Internally-used compiler abstractions.
+ */
+
+#ifndef DMNSN_INTERNAL_H
+#error "Please include \"internal.h\" instead of this header directly."
+#endif
+
+#include <stdalign.h>
+
+/**
+ * @def DMNSN_HOT
+ * Mark a function as a hot path.
+ */
+/**
+ * @def DMNSN_INTERNAL
+ * Mark a function as internal linkage.
+ */
+/**
+ * @def DMNSN_DESTRUCTOR
+ * Queue a function to run at program termination.
+ */
+/**
+ * @def DMNSN_LATE_DESTRUCTOR
+ * Queue a function to run at program termination, after those labeled
+ * DMNSN_DESTRUCTOR.
+ */
+#if DMNSN_GNUC
+  #define DMNSN_HOT             __attribute__((hot))
+  #define DMNSN_INTERNAL        __attribute__((visibility("hidden")))
+  #define DMNSN_DESTRUCTOR      __attribute__((destructor(102)))
+  #define DMNSN_LATE_DESTRUCTOR __attribute__((destructor(101)))
+#else
+  #define DMNSN_HOT
+  #define DMNSN_INTERNAL
+  #define DMNSN_DESTRUCTOR
+  #define DMNSN_LATE_DESTRUCTOR
+#endif
+
+/// Synonym for _Atomic that stdatomic.h doesn't define for some reason
+#define atomic _Atomic
+
+/// Nearly-compliant alloca variant
+#define DMNSN_ALLOCA(var, size) DMNSN_ALLOCA_IMPL(var, size, __LINE__)
+
+#define DMNSN_ALLOCA_IMPL(var, size, ctr) DMNSN_ALLOCA_IMPL2(var, size, ctr)
+
+#define DMNSN_ALLOCA_IMPL2(var, size, ctr)              \
+  alignas(max_align_t) char dmnsn_alloca##ctr[size];    \
+  var = (void *)dmnsn_alloca##ctr
diff --git a/libdimension/internal/concurrency.h b/libdimension/internal/concurrency.h
new file mode 100644
index 0000000..e9c024a
--- /dev/null
+++ b/libdimension/internal/concurrency.h
@@ -0,0 +1,236 @@
+/*************************************************************************
+ * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * Internal threading abstraction.
+ */
+
+#ifndef DMNSN_INTERNAL_CONCURRENCY_H
+#define DMNSN_INTERNAL_CONCURRENCY_H
+
+#include "internal.h"
+#include "dimension/concurrency.h"
+#include <pthread.h>
+
+/// Allocate a new future object.
+DMNSN_INTERNAL dmnsn_future *dmnsn_new_future(void);
+
+/// Set the total number of loop iterations.
+DMNSN_INTERNAL void dmnsn_future_set_total(dmnsn_future *future, size_t total);
+/// Increment the progress of a background task.
+DMNSN_INTERNAL void dmnsn_future_increment(dmnsn_future *future);
+/// Instantly complete the background teask.
+DMNSN_INTERNAL void dmnsn_future_finish(dmnsn_future *future);
+/// Set the number of worker threads.
+DMNSN_INTERNAL void dmnsn_future_set_nthreads(dmnsn_future *future, unsigned int nthreads);
+/// Notify completion of a worker thread.
+DMNSN_INTERNAL void dmnsn_future_finish_thread(dmnsn_future *future);
+
+/**
+ * Thread callback type.
+ * @param[in,out] ptr  An arbitrary pointer.
+ * @return 0 on success, non-zero on failure.
+ */
+typedef int dmnsn_thread_fn(void *ptr);
+
+/**
+ * Create a thread that cleans up after itself on errors.
+ * @param[in,out] future     The future object to associate with the thread.
+ * @param[in]     thread_fn  The thread callback.
+ * @param[in,out] arg        The pointer to pass to the thread callback.
+ */
+DMNSN_INTERNAL void dmnsn_new_thread(dmnsn_future *future,
+                                     dmnsn_thread_fn *thread_fn, void *arg);
+
+/**
+ * Thread callback type for parallel tasks.
+ * @param[in,out] ptr       An arbitrary pointer.
+ * @param[in]     thread    An ID for this thread, in [0, \p nthreads).
+ * @param[in]     nthreads  The number of concurrent threads.
+ * @return 0 on success, non-zero on failure.
+ */
+typedef int dmnsn_ccthread_fn(void *ptr, unsigned int thread,
+                              unsigned int nthreads);
+
+/**
+ * Run \p nthreads threads in parallel.
+ * @param[in,out] future       The future object to associate with the threads,
+ *                             possibly NULL.
+ * @param[in]     ccthread_fn  The routine to run in each concurrent thread.
+ * @param[in,out] arg          The pointer to pass to the thread callbacks.
+ * @param[in]     nthreads     The number of concurrent threads to run.
+ * @return 0 if all threads were successful, and an error code otherwise.
+ */
+DMNSN_INTERNAL int dmnsn_execute_concurrently(dmnsn_future *future,
+                                              dmnsn_ccthread_fn *ccthread_fn,
+                                              void *arg, unsigned int nthreads);
+
+/**
+ * Initialize a mutex, bailing out on failure.
+ * @param[out] mutex  The mutex to initialize.
+ */
+DMNSN_INTERNAL void dmnsn_initialize_mutex(pthread_mutex_t *mutex);
+
+/// dmnsn_lock_mutex() implementation.
+DMNSN_INTERNAL void dmnsn_lock_mutex_impl(pthread_mutex_t *mutex);
+/// dmnsn_unlock_mutex() implementation.
+DMNSN_INTERNAL void dmnsn_unlock_mutex_impl(void *mutex);
+
+/**
+ * Lock a mutex, bailing out on failure.
+ * Contains a {, so must be used in the same block as dmnsn_unlock_mutex().
+ * @param[in,out] mutex  The mutex to lock.
+ */
+#define dmnsn_lock_mutex(mutex) do { dmnsn_lock_mutex_impl((mutex))
+
+/**
+ * Unlock a mutex, bailing out on failure.
+ * Contains a }, so must be used in the same block as dmnsn_lock_mutex().
+ * @param[in,out] mutex  The mutex to unlock.
+ */
+#define dmnsn_unlock_mutex(mutex) dmnsn_unlock_mutex_impl((mutex)); } while (0)
+
+/**
+ * Destroy a mutex, warning on failure.
+ * @param[in,out] mutex  The mutex to destroy.
+ */
+DMNSN_INTERNAL void dmnsn_destroy_mutex(pthread_mutex_t *mutex);
+
+/**
+ * Initialize a read-write lock, bailing out on failure.
+ * @param[out] rwlock  The read-write lock to initialize.
+ */
+DMNSN_INTERNAL void dmnsn_initialize_rwlock(pthread_rwlock_t *rwlock);
+
+/// dmnsn_read_lock() implementation.
+DMNSN_INTERNAL void dmnsn_read_lock_impl(pthread_rwlock_t *rwlock);
+/// dmnsn_write_lock() implementation.
+DMNSN_INTERNAL void dmnsn_write_lock_impl(pthread_rwlock_t *rwlock);
+/// dmnsn_unlock_rwlock() implementation.
+DMNSN_INTERNAL void dmnsn_unlock_rwlock_impl(pthread_rwlock_t *rwlock);
+
+/**
+ * Read-lock a read-write lock, bailing out on failure.
+ * Contains a {, so must be used in the same block as dmnsn_unlock_rwlock().
+ * @param[in,out] rwlock  The read-write lock to lock.
+ */
+#define dmnsn_read_lock(rwlock) do { dmnsn_read_lock_impl((rwlock))
+
+/**
+ * Write-lock a read-write lock, bailing out on failure.
+ * Contains a {, so must be used in the same block as dmnsn_unlock_rwlock().
+ * @param[in,out] rwlock  The read-write lock to lock.
+ */
+#define dmnsn_write_lock(rwlock) do { dmnsn_write_lock_impl((rwlock))
+
+/**
+ * Unlock a read-write lock, bailing out on failure.
+ * Contains a }, so must be used in the same block as dmnsn_read_lock() or
+ * dmnsn_write_lock().
+ * @param[in,out] rwlock  The read-write lock to lock.
+ */
+#define dmnsn_unlock_rwlock(rwlock)                     \
+  dmnsn_unlock_rwlock_impl((rwlock)); } while (0)
+
+/**
+ * Destroy a read-write lock, warning on failure.
+ * @param[in,out] rwlock  The read-write lock to destroy.
+ */
+DMNSN_INTERNAL void dmnsn_destroy_rwlock(pthread_rwlock_t *rwlock);
+
+/**
+ * Initialize a condition variable, bailing out on failure.
+ * @param[out] cond  The condition variable to initialize.
+ */
+DMNSN_INTERNAL void dmnsn_initialize_cond(pthread_cond_t *cond);
+
+/**
+ * Wait on a condition variable, bailing out on error.
+ * @param[in] cond   The condition variable to wait on.
+ * @param[in] mutex  The associated mutex.
+ */
+DMNSN_INTERNAL void dmnsn_cond_wait(pthread_cond_t *cond,
+                                    pthread_mutex_t *mutex);
+
+/**
+ * Wait on a condition variable, bailing out on error, and unlock the mutex if
+ * cancelled.
+ * @param[in] cond   The condition variable to wait on.
+ * @param[in] mutex  The associated mutex.
+ */
+#define dmnsn_cond_wait_safely(cond, mutex)                     \
+  do {                                                          \
+    pthread_cleanup_push(dmnsn_unlock_mutex_impl, (mutex));     \
+    dmnsn_cond_wait((cond), (mutex));                           \
+    pthread_cleanup_pop(false);                                 \
+  } while (0)
+
+/**
+ * Signal a condition variable, bailing out on error.
+ * @param[in] cond   The condition variable to signal.
+ */
+DMNSN_INTERNAL void dmnsn_cond_broadcast(pthread_cond_t *cond);
+
+/**
+ * Destroy a condition variable, warning on failure.
+ * @param[in,out] cond  The condition variable to destroy.
+ */
+DMNSN_INTERNAL void dmnsn_destroy_cond(pthread_cond_t *cond);
+
+/**
+ * Once-called callback type.
+ */
+typedef void dmnsn_once_fn(void);
+
+/**
+ * Call a function exactly once, bailing out on failure.
+ * @param[in,out] once     The once control.
+ * @param[in]     once_fn  The function to call.
+ */
+DMNSN_INTERNAL void dmnsn_once(pthread_once_t *once, dmnsn_once_fn *once_fn);
+
+/**
+ * Initialize a thread-local storage key, bailing out on failure.
+ * @param[out] key         The key to initialize.
+ * @param[in]  destructor  An optional destructor callback.
+ */
+DMNSN_INTERNAL void dmnsn_key_create(pthread_key_t *key, dmnsn_callback_fn *destructor);
+
+/**
+ * Set a thread-specific pointer, bailing out on failure.
+ * @param[in] key    The thread-local storage key.
+ * @param[in] value  The value to set.
+ */
+DMNSN_INTERNAL void dmnsn_setspecific(pthread_key_t key, const void *value);
+
+/**
+ * Destroy a thread-local storage key, warning on failure.
+ * @param[out] key         The key to destroy.
+ */
+DMNSN_INTERNAL void dmnsn_key_delete(pthread_key_t key);
+
+/**
+ * Join a thread, bailing out on failure.
+ * @param[in,out] thread  The thread to join.
+ */
+DMNSN_INTERNAL void dmnsn_join_thread(pthread_t thread, void **retval);
+
+#endif // DMNSN_INTERNAL_CONCURRENCY_H
diff --git a/libdimension/internal/future.h b/libdimension/internal/future.h
new file mode 100644
index 0000000..047523e
--- /dev/null
+++ b/libdimension/internal/future.h
@@ -0,0 +1,61 @@
+/*************************************************************************
+ * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * Future object implementation.
+ */
+
+#ifndef DMNSN_INTERNAL_FUTURE_H
+#define DMNSN_INTERNAL_FUTURE_H
+
+#include <pthread.h>
+
+struct dmnsn_future {
+  size_t progress; ///< Completed loop iterations.
+  size_t total;    ///< Total expected loop iterations.
+
+  /// The worker thread.
+  pthread_t thread;
+
+  /// Mutex to guard progress and total.
+  pthread_mutex_t mutex;
+
+  /// Condition variable for waiting for a particular amount of progress.
+  pthread_cond_t cond;
+
+  /// Minimum waited-on value.
+  double min_wait;
+
+  /// Number of threads working on the future's background task.
+  unsigned int nthreads;
+  /// Number of threads not yet paused.
+  unsigned int nrunning;
+  /// Count of threads holding the future paused.
+  unsigned int npaused;
+  /// Condition variable for waiting for nrunning == 0.
+  pthread_cond_t none_running_cond;
+  /// Condition variable for waiting for nrunning == nthreads.
+  pthread_cond_t all_running_cond;
+  /// Condition variable for waiting for npaused == 0.
+  pthread_cond_t resume_cond;
+};
+
+#endif // DMNSN_INTERNAL_FUTURE_H
diff --git a/libdimension/internal/platform.h b/libdimension/internal/platform.h
new file mode 100644
index 0000000..e037d21
--- /dev/null
+++ b/libdimension/internal/platform.h
@@ -0,0 +1,67 @@
+/*************************************************************************
+ * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * Internal platform abstractions.
+ */
+
+#ifndef DMNSN_INTERNAL_PLATFORM_H
+#define DMNSN_INTERNAL_PLATFORM_H
+
+#include "internal.h"
+#include "dimension/platform.h"
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+
+/**
+ * Print a stack trace, if implemented for the current platform.
+ * @param[in,out] file  The file to which to write the stack trace.
+ */
+DMNSN_INTERNAL void dmnsn_backtrace(FILE *file);
+
+/**
+ * Is the calling thread the main thread?
+ * @return Whether this is the main execution thread, or \c true if we can't
+ *         tell.
+ */
+DMNSN_INTERNAL bool dmnsn_is_main_thread(void);
+
+/**
+ * Are we running on a little-endian computer?
+ * @return Whether the current architecture is little-endian.
+ */
+DMNSN_INTERNAL bool dmnsn_is_little_endian(void);
+
+/**
+ * How many CPUs are available?
+ * @return The number of CPUs available to dimension.
+ */
+DMNSN_INTERNAL size_t dmnsn_ncpus(void);
+
+/**
+ * Calculate process times.
+ * @param[out] timer  The timer in which to store the current total process
+ *                    times.
+ */
+DMNSN_INTERNAL void dmnsn_get_times(dmnsn_timer *timer);
+
+#endif // DMNSN_INTERNAL_PLATFORM_H
diff --git a/libdimension/internal/polynomial.h b/libdimension/internal/polynomial.h
new file mode 100644
index 0000000..7af3e5a
--- /dev/null
+++ b/libdimension/internal/polynomial.h
@@ -0,0 +1,85 @@
+/*************************************************************************
+ * Copyright (C) 2009-2011 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * Utility functions for working with and numerically solving polynomials.
+ * Polynomials are represented as simple arrays where the ith element is the
+ * coefficient on x^i.  In general, we are only interested in positive roots.
+ */
+
+#include "internal.h"
+#include <stddef.h>
+#include <stdio.h>
+
+/**
+ * Evaluate a polynomial at \p x.
+ * @param[in] poly    The coefficients of the polynomial to evaluate, in order
+ *                    from lowest degree to highest degree.  The array should
+ *                    have dimension <tt>degree + 1</tt>.
+ * @param[in] degree  The degree of the polynomial.
+ * @param[in] x       The value of the variable at which to evaluate.
+ */
+DMNSN_INTERNAL DMNSN_INLINE double
+dmnsn_polynomial_evaluate(const double poly[], size_t degree, double x)
+{
+  double ret = poly[degree];
+  size_t i;
+  for (i = degree; i-- > 0;) {
+    ret = ret*x + poly[i];
+  }
+  return ret;
+}
+
+/**
+ * Evaluate the derivative of a polynomial at \p x.
+ * @param[in] poly    The coefficients of the polynomial to evaluate.
+ * @param[in] degree  The degree of the polynomial.
+ * @param[in] x       The value of the variable at which to evaluate.
+ */
+DMNSN_INTERNAL DMNSN_INLINE double
+dmnsn_polynomial_evaluate_derivative(const double poly[], size_t degree, double x)
+{
+  double ret = poly[degree]*degree;
+  size_t i;
+  for (i = degree - 1; i >= 1; --i) {
+    ret = ret*x + poly[i]*i;
+  }
+  return ret;
+}
+
+/**
+ * Find the positive roots of a polynomial.
+ * @param[in]  poly    The coefficients of the polynomial to solve.
+ * @param[in]  degree  The degree of the polynomial.
+ * @param[out] x       An array in which to store the roots.  It should have
+ *                     dimension \p degree.
+ * @return The number of positive roots stored in \c x[].
+ */
+DMNSN_INTERNAL size_t dmnsn_polynomial_solve(const double poly[], size_t degree, double x[]);
+
+/**
+ * Output a polynomial.  The polynomial is printed as a function of x suitable
+ * for input into a CAS, and without a trailing newline.
+ * @param[in,out] file    The file to write to.
+ * @param[in]     poly    The coefficients of the polynomial to print.
+ * @param[in]     degree  The degree of the polynomial.
+ */
+DMNSN_INTERNAL void dmnsn_polynomial_print(FILE *file, const double poly[], size_t degree);
diff --git a/libdimension/internal/profile.h b/libdimension/internal/profile.h
new file mode 100644
index 0000000..0f59b8f
--- /dev/null
+++ b/libdimension/internal/profile.h
@@ -0,0 +1,68 @@
+/*************************************************************************
+ * Copyright (C) 2010-2011 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * Built-in branch profiler.
+ */
+
+#ifndef DMNSN_INTERNAL_H
+#error "Please include \"internal.h\" instead of this header directly."
+#endif
+
+#include <stdbool.h>
+
+/**
+ * @def dmnsn_likely
+ * Indicate that a test is likely to succeed.
+ * @param test  The test to perform.
+ * @return The truth value of \p test.
+ */
+/**
+ * @def dmnsn_unlikely
+ * Indicate that a test is unlikely to succeed.
+ * @param test  The test to perform.
+ * @return The truth value of \p test.
+ */
+#ifdef DMNSN_PROFILE
+  #define dmnsn_likely(test)                                      \
+    dmnsn_expect(!!(test), true, DMNSN_FUNC, __FILE__, __LINE__)
+  #define dmnsn_unlikely(test)                                    \
+    dmnsn_expect(!!(test), false, DMNSN_FUNC, __FILE__, __LINE__)
+#elif DMNSN_GNUC
+  #define dmnsn_likely(test)   __builtin_expect(!!(test), true)
+  #define dmnsn_unlikely(test) __builtin_expect(!!(test), false)
+#else
+  #define dmnsn_likely(test)   (!!(test))
+  #define dmnsn_unlikely(test) (!!(test))
+#endif
+
+/**
+ * Record a test and its expected result.  Called by dmnsn_[un]likely();
+ * don't call directly.
+ * @param[in] result    The result of the test.
+ * @param[in] expected  The expected result of the test.
+ * @param[in] func      The name of the function the test occurs in.
+ * @param[in] file      The name of the file the test occurs in.
+ * @param[in] line      The line number on which the test occurs.
+ * @return \p result.
+ */
+DMNSN_INTERNAL bool dmnsn_expect(bool result, bool expected, const char *func,
+                                 const char *file, unsigned int line);
diff --git a/libdimension/internal/prtree.h b/libdimension/internal/prtree.h
new file mode 100644
index 0000000..7d85f44
--- /dev/null
+++ b/libdimension/internal/prtree.h
@@ -0,0 +1,38 @@
+/*************************************************************************
+ * Copyright (C) 2010-2012 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file.
+ * Priority R-trees.  PR-trees are a data structure introduced by Arge, de Berg,
+ * Haverkort, and Yi, which provides asymptotically optimal worst-case lookup,
+ * while remaining efficient with real-world data.  Their structure is derived
+ * from B-trees.
+ */
+
+#ifndef DMNSN_INTERNAL_PRTREE_H
+#define DMNSN_INTERNAL_PRTREE_H
+
+#include "internal.h"
+#include "internal/bvh.h"
+
+/// Create a PR-tree.
+DMNSN_INTERNAL dmnsn_bvh_node *dmnsn_new_prtree(const dmnsn_array *objects);
+
+#endif // DMNSN_INTERNAL_PRTREE_H
diff --git a/libdimension/internal/rgba.h b/libdimension/internal/rgba.h
new file mode 100644
index 0000000..964d622
--- /dev/null
+++ b/libdimension/internal/rgba.h
@@ -0,0 +1,55 @@
+/*************************************************************************
+ * Copyright (C) 2010-2014 Tavian Barnes <tavianator@tavianator.com>     *
+ *                                                                       *
+ * This file is part of The Dimension Library.                           *
+ *                                                                       *
+ * The Dimension Library is free software; you can redistribute it and/  *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version.                       *
+ *                                                                       *
+ * The Dimension Library is distributed in the hope that it will be      *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty   *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  *
+ * Lesser General Public License for more details.                       *
+ *                                                                       *
+ * You should have received a copy of the GNU Lesser General Public      *
+ * License along with this program.  If not, see                         *
+ * <http://www.gnu.org/licenses/>.                                       *
+ *************************************************************************/
+
+/**
+ * @file
+ * RGBA canvas optimizer interface, used by image optimizers.
+ */
+
+#ifndef DMNSN_INTERNAL_RGBA_H
+#define DMNSN_INTERNAL_RGBA_H
+
+#include "internal.h"
+#include "dimension/canvas.h"
+#include <stdint.h>
+
+/// RGBA8 optimizer type.
+typedef struct dmnsn_rgba8_optimizer {
+  dmnsn_canvas_optimizer optimizer;
+  uint8_t data[];
+} dmnsn_rgba8_optimizer;
+
+/// RGBA16 optimizer type.
+typedef struct dmnsn_rgba16_optimizer {
+  dmnsn_canvas_optimizer optimizer;
+  uint16_t data[];
+} dmnsn_rgba16_optimizer;
+
+/// Apply the RGBA8 optimizer to a canvas.
+DMNSN_INTERNAL void dmnsn_rgba8_optimize_canvas(dmnsn_pool *pool, dmnsn_canvas *canvas);
+/// Apply the RGBA16 optimizer to a canvas.
+DMNSN_INTERNAL void dmnsn_rgba16_optimize_canvas(dmnsn_pool *pool, dmnsn_canvas *canvas);
+
+/// RGBA8 optimizer callback.
+DMNSN_INTERNAL void dmnsn_rgba8_optimizer_fn(dmnsn_canvas_optimizer *optimizer, const dmnsn_canvas *canvas, size_t x, size_t y);
+/// RGBA16 optimizer callback.
+DMNSN_INTERNAL void dmnsn_rgba16_optimizer_fn(dmnsn_canvas_optimizer *optimizer, const dmnsn_canvas *canvas, size_t x, size_t y);
+
+#endif // DMNSN_INTERNAL_RGBA_H