summaryrefslogtreecommitdiffstats
path: root/libdimension/internal
diff options
context:
space:
mode:
Diffstat (limited to 'libdimension/internal')
-rw-r--r--libdimension/internal/bvh.h79
-rw-r--r--libdimension/internal/compiler.h71
-rw-r--r--libdimension/internal/concurrency.h236
-rw-r--r--libdimension/internal/future.h61
-rw-r--r--libdimension/internal/platform.h67
-rw-r--r--libdimension/internal/polynomial.h85
-rw-r--r--libdimension/internal/profile.h68
-rw-r--r--libdimension/internal/prtree.h38
-rw-r--r--libdimension/internal/rgba.h55
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