Import new (BSDL) device tree compiler. Now built by default, so that it can't

be used on the host system (and not installed on the device, if required).  The
GPL'd one is still available if there are any devices that need it (make
universe passes with it, including kernels that use fdt, but there may be some
out-of-tree ones).  WITH_GPL_DTC can be used to select the old one, for now.

Probably won't be MFC'd, but we'll remove the GPL'd version in head after the
new one has had a lot more testing and ship it in 10.0.

19 files changed, 5070 insertions, 2 deletions

diff --git a/Makefile.inc1 b/Makefile.inc1
index 7584935..c1782f1 100644
--- a/Makefile.inc1
+++ b/Makefile.inc1
@@ -1112,7 +1112,10 @@ _dtrace_tools= cddl/usr.bin/sgsmsg cddl/lib/libctf lib/libelf \
     lib/libdwarf cddl/usr.bin/ctfconvert cddl/usr.bin/ctfmerge
 .endif
 
-.if ${MK_FDT} != "no"
+# Default to building the BSDL DTC, but build the GPL one if users explicitly
+# request it.
+_dtc= /usr.bin/dtc
+.if ${MK_GPL_DTC} != "no"
 _dtc= gnu/usr.bin/dtc
 .endif
 
diff --git a/gnu/usr.bin/Makefile b/gnu/usr.bin/Makefile
index 3a61327..386c957 100644
--- a/gnu/usr.bin/Makefile
+++ b/gnu/usr.bin/Makefile
@@ -30,7 +30,7 @@ _groff=		groff
 _cvs=		cvs
 .endif
 
-.if ${MK_FDT}	!= "no"
+.if ${MK_GPL_DTC} != "no"
 _dtc=		dtc
 .endif
 
diff --git a/share/man/man5/src.conf.5 b/share/man/man5/src.conf.5
index 1d757f7..cc06acc 100644
--- a/share/man/man5/src.conf.5
+++ b/share/man/man5/src.conf.5
@@ -476,6 +476,9 @@ Set to not build GPIB bus support.
 Set to not build
 .Xr gpioctl 8
 as part of the base system.
+.It Va WITH_GPL_DTC
+Set to build the GPL'd version of the device tree compiler from elinux.org,
+instead of the BSD licensed one.
 .It Va WITHOUT_GROFF
 .\" from FreeBSD: head/tools/build/options/WITHOUT_GROFF 218941 2011-02-22 08:13:49Z uqs
 Set to not build
diff --git a/share/mk/bsd.own.mk b/share/mk/bsd.own.mk
index be00ce4..88d887a 100644
--- a/share/mk/bsd.own.mk
+++ b/share/mk/bsd.own.mk
@@ -364,6 +364,7 @@ __DEFAULT_NO_OPTIONS = \
     BSD_GREP \
     CLANG_EXTRAS \
     CTF \
+    GPL_DTC \
     HESIOD \
     ICONV \
     IDEA \
diff --git a/usr.bin/dtc/HACKING b/usr.bin/dtc/HACKING
new file mode 100644
index 0000000..4fb46da
--- /dev/null
+++ b/usr.bin/dtc/HACKING
@@ -0,0 +1,65 @@
+$FreeBSD$
+
+Notes for people hacking on dtc
+===============================
+
+This file contains some notes for people wishing to hack on dtc.
+
+Upstreaming
+-----------
+
+This code is developed in the FreeBSD svn repository:
+
+https://svn.freebsd.org/base/head/usr.bin/dtc
+
+If you got the source from anywhere else and wish to make changes, please
+ensure that you are working against the latest version, or you may end up
+fixing bugs that are already fixed upstream.  Although the license makes no
+requirement that you share any improvements that you make, patches are very
+welcome.
+
+C++11
+-----
+
+This project currently aims to compile with g++ 4.2.1 and so doesn't make any
+use of C++11 features.  It would be a good idea to relax this restriction once
+clang is the default compiler for ARM, MIPS and PowerPC.
+
+This code makes use of a lot of iterator loops, which would be cleaner using
+the new syntax in C++11.  It also explicitly deletes a lot of objects held in
+collections in destructors that have these collections as their members.  This
+could be simplified by using `shared_ptr`.
+
+The code does make use of `static_assert()`, but uses a macro in utility.hh to
+remove these if they are not supported.  The FreeBSD standard headers also
+define a compatibility macro the implements static asserts in terms of an array
+with 1 element on success and -1 elements on failure.
+
+Adding New Checks
+-----------------
+
+Currently, the biggest weakness of this version of the tool is that it lacks
+most of the semantic checkers that can be implemented by simply reading the
+ePAPR spec.  The `checker` class provides a simple superclass for implementing
+these quite easily.  There are also helper methods on `device_tree` for finding
+specific nodes, for checks that require some understanding of the structure of
+the tree.
+
+We should probably add a parent pointer to the `node` class for easily walking
+up the tree.
+
+Adding Direct C Output
+----------------------
+
+The FreeBSD build system currently uses dtc to generate a blob and then
+converts this to C source code.  A new `output_writer` subclass could easily
+generate the C directly.
+
+Parser Improvements
+-------------------
+
+There are a few FIXME lines in the parser for some corner cases that are not
+currently used by FreeBSD.  These are mainly related to labels in the middle of
+values.  These can be fixed by creating a new `property_value` with the
+specified label, starting at the location of the label.  Don't forget to remove
+the associated comments from the BUGS section of the man page if you fix this.
diff --git a/usr.bin/dtc/Makefile b/usr.bin/dtc/Makefile
new file mode 100644
index 0000000..78973fc
--- /dev/null
+++ b/usr.bin/dtc/Makefile
@@ -0,0 +1,11 @@
+# $FreeBSD$
+
+PROG_CXX=dtc
+SRCS=	dtc.cc input_buffer.cc string.cc dtb.cc fdt.cc checking.cc
+MAN=	dtc.1
+
+WARNS?=	3
+
+NO_SHARED?=NO
+
+.include <bsd.prog.mk>
diff --git a/usr.bin/dtc/checking.cc b/usr.bin/dtc/checking.cc
new file mode 100644
index 0000000..aff3752
--- /dev/null
+++ b/usr.bin/dtc/checking.cc
@@ -0,0 +1,210 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#include "checking.hh"
+
+namespace dtc
+{
+namespace fdt
+{
+namespace checking
+{
+
+bool
+checker::visit_node(device_tree *tree, node *n)
+{
+	path.push_back(std::make_pair(n->name, n->unit_address));
+	// Check this node
+	if (!check_node(tree, n))
+	{
+		return false;
+	}
+	// Now check its properties
+	for (node::property_iterator i=n->property_begin(), e=n->property_end()
+	     ; i!=e ; ++i)
+	{
+		if (!check_property(tree, n, *i))
+		{
+			return false;
+		}
+	}
+	// And then recursively check the children
+	for (node::child_iterator i=n->child_begin(), e=n->child_end() ; i!=e ;
+	     ++i)
+	{
+		if (!visit_node(tree, *i))
+		{
+			return false;
+		}
+	}
+	path.pop_back();
+	return true;
+}
+
+void
+checker::report_error(const char *errmsg)
+{
+	fprintf(stderr, "Error: %s, while checking node: ", errmsg);
+	for (device_tree::node_path::iterator p=path.begin()+1, pe=path.end() ;
+	     p!=pe ; ++p)
+	{
+		putc('/', stderr);
+		p->first.dump();
+		if (!(p->second.empty()))
+		{
+			putc('@', stderr);
+			p->second.dump();
+		}
+	}
+	fprintf(stderr, " [-W%s]\n", checker_name);
+}
+
+bool
+property_checker::check_property(device_tree *tree, node *n, property *p)
+{
+	if (p->get_key() == key)
+	{
+		if (!check(tree, n, p))
+		{
+			report_error("property check failed");
+			return false;
+		}
+	}
+	return true;
+}
+
+bool
+property_size_checker::check(device_tree *tree, node *n, property *p)
+{
+	uint32_t psize = 0;
+	for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ; ++i)
+	{
+		if (!i->is_binary())
+		{
+			return false;
+		}
+		psize += i->byte_data.size();
+	}
+	return psize == size;
+}
+
+template<property_value::value_type T>
+void
+check_manager::add_property_type_checker(const char *name, string prop)
+{
+	checkers.insert(std::make_pair(string(name),
+		new property_type_checker<T>(name, prop)));
+}
+
+void
+check_manager::add_property_size_checker(const char *name,
+                                         string prop,
+                                         uint32_t size)
+{
+	checkers.insert(std::make_pair(string(name),
+		new property_size_checker(name, prop, size)));
+}
+
+check_manager::~check_manager()
+{
+	while (checkers.begin() != checkers.end())
+	{
+		delete checkers.begin()->second;
+		checkers.erase(checkers.begin());
+	}
+	while (disabled_checkers.begin() != disabled_checkers.end())
+	{
+		delete disabled_checkers.begin()->second;
+	}
+}
+
+check_manager::check_manager()
+{
+	// NOTE: All checks listed here MUST have a corresponding line
+	// in the man page!
+	add_property_type_checker<property_value::STRING_LIST>(
+			"type-compatible", string("compatible"));
+	add_property_type_checker<property_value::STRING>(
+			"type-model", string("model"));
+	add_property_size_checker("type-phandle", string("phandle"), 4);
+}
+
+bool
+check_manager::run_checks(device_tree *tree, bool keep_going)
+{
+	bool success = true;
+	for (std::map<string, checker*>::iterator i=checkers.begin(),
+	     e=checkers.end() ; i!=e ; ++i)
+	{
+		success &= i->second->check_tree(tree);
+		if (!(success || keep_going))
+		{
+			break;
+		}
+	}
+	return success;
+}
+
+bool
+check_manager::disable_checker(string name)
+{
+	std::map<string, checker*>::iterator checker = checkers.find(name);
+	if (checker != checkers.end())
+	{
+		disabled_checkers.insert(std::make_pair(name,
+		                                        checker->second));
+		checkers.erase(checker);
+		return true;
+	}
+	return false;
+}
+
+bool
+check_manager::enable_checker(string name)
+{
+	std::map<string, checker*>::iterator checker =
+		disabled_checkers.find(name);
+	if (checker != disabled_checkers.end())
+	{
+		checkers.insert(std::make_pair(name, checker->second));
+		disabled_checkers.erase(checker);
+		return true;
+	}
+	return false;
+}
+
+} // namespace checking
+
+} // namespace fdt
+
+} // namespace dtc
+
diff --git a/usr.bin/dtc/checking.hh b/usr.bin/dtc/checking.hh
new file mode 100644
index 0000000..0de1d60
--- /dev/null
+++ b/usr.bin/dtc/checking.hh
@@ -0,0 +1,308 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _CHECKING_HH_
+#define _CHECKING_HH_
+#include "string.hh"
+#include "fdt.hh"
+
+namespace dtc
+{
+namespace fdt
+{
+namespace checking
+{
+/**
+ * Base class for all checkers.  This will visit the entire tree and perform
+ * semantic checks defined in subclasses.  Note that device trees are generally
+ * small (a few dozen nodes at most) and so we optimise for flexibility and
+ * extensibility here, not for performance.  Each checker will visit the entire
+ * tree.
+ */
+class checker
+{
+	/**
+	 * The path to the current node being checked.  This is used for
+	 * printing error messages.
+	 */
+	device_tree::node_path path;
+	/**
+	 * The name of the checker.  This is used for printing error messages
+	 * and for enabling / disabling specific checkers from the command
+	 * line. 
+	 */
+	const char *checker_name;
+	/**
+	 * Visits each node, calling the checker functions on properties and
+	 * nodes.
+	 */
+	bool visit_node(device_tree *tree, node *n);
+	protected:
+	/**
+	 * Prints the error message, along with the path to the node that
+	 * caused the error and the name of the checker.
+	 */
+	void report_error(const char *errmsg);
+	public:
+	/**
+	 * Constructor.  Takes the name of this checker, which is which is used
+	 * when reporting errors.
+	 */
+	checker(const char *name) : checker_name(name) {}
+	/**
+	 * Virtual destructor in case any subclasses need to do cleanup.
+	 */
+	virtual ~checker() {}
+	/**
+	 * Method for checking that a node is valid.  The root class version
+	 * does nothing, subclasses should override this.
+	 */
+	virtual bool check_node(device_tree *tree, node *n)
+	{
+		return true;
+	}
+	/**
+	 * Method for checking that a property is valid.  The root class
+	 * version does nothing, subclasses should override this.
+	 */
+	virtual bool check_property(device_tree *tree, node *n, property *p)
+	{
+		return true;
+	}
+	/**
+	 * Runs the checker on the specified device tree.
+	 */
+	bool check_tree(fdt::device_tree *tree)
+	{
+		return visit_node(tree, tree->get_root());
+	}
+};
+
+/**
+ * Abstract base class for simple property checks.  This class defines a check
+ * method for subclasses, which is invoked only when it finds a property with
+ * the matching name.  To define simple property checkers, just subclass this
+ * and override the check() method.
+ */
+class property_checker : public checker
+{
+	/**
+	 * The name of the property that this checker is looking for.
+	 */
+	string key;
+	public:
+	/**
+	 * Implementation of the generic property-checking method that checks
+	 * for a property with the name specified in the constructor 
+	 */
+	virtual bool check_property(device_tree *tree, node *n, property *p);
+	/**
+	 * Constructor.  Takes the name of the checker and the name of the
+	 * property to check.
+	 */
+	property_checker(const char* name, string property_name)
+		: checker(name), key(property_name) {}
+	/**
+	 * The check method, which subclasses should implement.
+	 */
+	virtual bool check(device_tree *tree, node *n, property *p) = 0;
+};
+
+/**
+ * Property type checker.
+ */
+template<property_value::value_type T>
+struct property_type_checker : public property_checker
+{
+	/**
+	 * Constructor, takes the name of the checker and the name of the
+	 * property to check as arguments.
+	 */
+	property_type_checker(const char* name, string property_name) : 
+		property_checker(name, property_name) {}
+	virtual bool check(device_tree *tree, node *n, property *p) = 0;
+};
+
+/**
+ * Empty property checker.  This checks that the property has no value.
+ */
+template<>
+struct property_type_checker <property_value::EMPTY> : public property_checker
+{
+	property_type_checker(const char* name, string property_name) : 
+		property_checker(name, property_name) {}
+	virtual bool check(device_tree *tree, node *n, property *p)
+	{
+		return p->begin() == p->end();
+	}
+};
+
+/**
+ * String property checker.  This checks that the property has exactly one
+ * value, which is a string.
+ */
+template<>
+struct property_type_checker <property_value::STRING> : public property_checker
+{
+	property_type_checker(const char* name, string property_name) : 
+		property_checker(name, property_name) {}
+	virtual bool check(device_tree *tree, node *n, property *p)
+	{
+		return (p->begin() + 1 == p->end()) && p->begin()->is_string();
+	}
+};
+/**
+ * String list property checker.  This checks that the property has at least
+ * one value, all of which are strings.
+ */
+template<>
+struct property_type_checker <property_value::STRING_LIST> :
+	public property_checker
+{
+	property_type_checker(const char* name, string property_name) : 
+		property_checker(name, property_name) {}
+	virtual bool check(device_tree *tree, node *n, property *p)
+	{
+		for (property::value_iterator i=p->begin(),e=p->end() ; i!=e ;
+		     ++i)
+		{
+			if (!(i->is_string() || i->is_string_list()))
+			{
+				return false;
+			}
+		}
+		return p->begin() != p->end();
+	}
+};
+
+/**
+ * Phandle property checker.  This checks that the property has exactly one
+ * value, which is a valid phandle.
+ */
+template<>
+struct property_type_checker <property_value::PHANDLE> : public property_checker
+{
+	property_type_checker(const char* name, string property_name) : 
+		property_checker(name, property_name) {}
+	virtual bool check(device_tree *tree, node *n, property *p)
+	{
+		return (p->begin() + 1 == p->end()) && 
+			(tree->referenced_node(*p->begin()) != 0);
+	}
+};
+
+/**
+ * Check that a property has the correct size.
+ */
+struct property_size_checker : public property_checker
+{
+	/**
+	 * The expected size of the property.
+	 */
+	uint32_t size;
+	public:
+	/**
+	 * Constructor, takes the name of the checker, the name of the property
+	 * to check, and its expected size as arguments.
+	 */
+	property_size_checker(const char* name, string property_name, uint32_t bytes)
+		: property_checker(name, property_name), size(bytes) {}
+	/**
+	 * Check, validates that the property has the correct size.
+	 */
+	virtual bool check(device_tree *tree, node *n, property *p);
+};
+
+
+/**
+ * The check manager is the interface to running the checks.  This allows
+ * default checks to be enabled, non-default checks to be enabled, and so on.
+ */
+class check_manager
+{
+	/**
+	 * The enabled checkers, indexed by their names.  The name is used when
+	 * disabling checkers from the command line.  When this manager runs,
+	 * it will only run the checkers from this map.
+	 */
+	std::map<string, checker*> checkers;
+	/**
+	 * The disabled checkers.  Moving checkers to this list disables them,
+	 * but allows them to be easily moved back.
+	 */
+	std::map<string, checker*> disabled_checkers;
+	/**
+	 * Helper function for adding a property value checker.
+	 */
+	template<property_value::value_type T>
+	void add_property_type_checker(const char *name, string prop);
+	/**
+	 * Helper function for adding a simple type checker.
+	 */
+	void add_property_type_checker(const char *name, string prop);
+	/**
+	 * Helper function for adding a property value checker.
+	 */
+	void add_property_size_checker(const char *name,
+	                               string prop,
+	                               uint32_t size);
+	public:
+	/**
+	 * Delete all of the checkers that are part of this checker manager.
+	 */
+	~check_manager();
+	/**
+	 * Default constructor, creates check manager containing all of the
+	 * default checks.
+	 */
+	check_manager();
+	/**
+	 * Run all of the checks on the specified tree.
+	 */
+	bool run_checks(device_tree *tree, bool keep_going);
+	/**
+	 * Disables the named checker.
+	 */
+	bool disable_checker(string name);
+	/**
+	 * Enables the named checker.  
+	 */
+	bool enable_checker(string name);
+};
+
+} // namespace checking
+
+} // namespace fdt
+
+} // namespace dtc
+
+#endif // !_CHECKING_HH_
diff --git a/usr.bin/dtc/dtb.cc b/usr.bin/dtc/dtb.cc
new file mode 100644
index 0000000..82ccc47
--- /dev/null
+++ b/usr.bin/dtc/dtb.cc
@@ -0,0 +1,308 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#include "dtb.hh"
+#include <inttypes.h>
+
+namespace dtc
+{
+namespace dtb
+{
+
+void output_writer::write_data(byte_buffer b)
+{
+	for (byte_buffer::iterator i=b.begin(), e=b.end(); i!=e ; i++)
+	{
+		write_data(*i);
+	}
+}
+
+void
+binary_writer::write_string(string name)
+{
+	name.push_to_buffer(buffer);
+	// Trailing nul
+	buffer.push_back(0);
+}
+
+void
+binary_writer::write_data(uint8_t v)
+{
+	buffer.push_back(v);
+}
+
+void
+binary_writer::write_data(uint32_t v)
+{
+	while (buffer.size() % 4 != 0)
+	{
+		buffer.push_back(0);
+	}
+	push_big_endian(buffer, v);
+}
+
+void
+binary_writer::write_data(uint64_t v)
+{
+	while (buffer.size() % 8 != 0)
+	{
+		buffer.push_back(0);
+	}
+	push_big_endian(buffer, v);
+}
+
+void
+binary_writer::write_to_file(int fd)
+{
+	// FIXME: Check return
+	write(fd, buffer.data(), buffer.size());
+}
+
+uint32_t
+binary_writer::size()
+{
+	return buffer.size();
+}
+
+void
+asm_writer::write_string(const char *c)
+{
+	while (*c)
+	{
+		buffer.push_back((uint8_t)*(c++));
+	}
+}
+
+void
+asm_writer::write_line(const char *c)
+{
+	if (byte_count != 0)
+	{
+		byte_count = 0;
+		buffer.push_back('\n');
+	}
+	write_string(c);
+}
+
+void
+asm_writer::write_byte(uint8_t b)
+{
+	char out[3] = {0};
+	if (byte_count++ == 0)
+	{
+		buffer.push_back('\t');
+	}
+	write_string(".byte 0x");
+	snprintf(out, 3, "%.2hhx", b);
+	buffer.push_back(out[0]);
+	buffer.push_back(out[1]);
+	if (byte_count == 4)
+	{
+		buffer.push_back('\n');
+		byte_count = 0;
+	}
+	else
+	{
+		buffer.push_back(';');
+		buffer.push_back(' ');
+	}
+}
+
+void
+asm_writer::write_label(string name)
+{
+	write_line("\t.globl ");
+	name.push_to_buffer(buffer);
+	buffer.push_back('\n');
+	name.push_to_buffer(buffer);
+	buffer.push_back(':');
+	buffer.push_back('\n');
+	buffer.push_back('_');
+	name.push_to_buffer(buffer);
+	buffer.push_back(':');
+	buffer.push_back('\n');
+	
+}
+
+void
+asm_writer::write_comment(string name)
+{
+	write_line("\t/* ");
+	name.push_to_buffer(buffer);
+	write_string(" */\n");
+}
+
+void
+asm_writer::write_string(string name)
+{
+	write_line("\t.string \"");
+	name.push_to_buffer(buffer);
+	write_line("\"\n");
+	bytes_written += name.size() + 1;
+}
+
+void
+asm_writer::write_data(uint8_t v)
+{
+	write_byte(v);
+	bytes_written++;
+}
+
+void
+asm_writer::write_data(uint32_t v)
+{
+	if (bytes_written % 4 != 0)
+	{
+		write_line("\t.balign 4\n");
+		bytes_written += (4 - (bytes_written % 4));
+	}
+	write_byte((v >> 24) & 0xff);
+	write_byte((v >> 16) & 0xff);
+	write_byte((v >> 8) & 0xff);
+	write_byte((v >> 0) & 0xff);
+	bytes_written += 4;
+}
+
+void
+asm_writer::write_data(uint64_t v)
+{
+	if (bytes_written % 8 != 0)
+	{
+		write_line("\t.balign 8\n");
+		bytes_written += (8 - (bytes_written % 8));
+	}
+	write_byte((v >> 56) & 0xff);
+	write_byte((v >> 48) & 0xff);
+	write_byte((v >> 40) & 0xff);
+	write_byte((v >> 32) & 0xff);
+	write_byte((v >> 24) & 0xff);
+	write_byte((v >> 16) & 0xff);
+	write_byte((v >> 8) & 0xff);
+	write_byte((v >> 0) & 0xff);
+	bytes_written += 8;
+}
+
+void
+asm_writer::write_to_file(int fd)
+{
+	// FIXME: Check return
+	write(fd, buffer.data(), buffer.size());
+}
+
+uint32_t
+asm_writer::size()
+{
+	return bytes_written;
+}
+
+void
+header::write(output_writer &out)
+{
+	out.write_label(string("dt_blob_start"));
+	out.write_label(string("dt_header"));
+	out.write_comment("magic");
+	out.write_data(magic);
+	out.write_comment("totalsize");
+	out.write_data(totalsize);
+	out.write_comment("off_dt_struct");
+	out.write_data(off_dt_struct);
+	out.write_comment("off_dt_strings");
+	out.write_data(off_dt_strings);
+	out.write_comment("off_mem_rsvmap");
+	out.write_data(off_mem_rsvmap);
+	out.write_comment("version");
+	out.write_data(version);
+	out.write_comment("last_comp_version");
+	out.write_data(last_comp_version);
+	out.write_comment("boot_cpuid_phys");
+	out.write_data(boot_cpuid_phys);
+	out.write_comment("size_dt_strings");
+	out.write_data(size_dt_strings);
+	out.write_comment("size_dt_struct");
+	out.write_data(size_dt_struct);
+}
+
+bool
+header::read_dtb(input_buffer &input)
+{
+	if (!(input.consume_binary(magic) && magic == 0xd00dfeed))
+	{
+		fprintf(stderr, "Missing magic token in header.  Got %" PRIx32
+		                " expected 0xd00dfeed\n", magic);
+		return false;
+	}
+	return input.consume_binary(totalsize) &&
+	       input.consume_binary(off_dt_struct) &&
+	       input.consume_binary(off_dt_strings) &&
+	       input.consume_binary(off_mem_rsvmap) &&
+	       input.consume_binary(version) &&
+	       input.consume_binary(last_comp_version) &&
+	       input.consume_binary(boot_cpuid_phys) &&
+	       input.consume_binary(size_dt_strings) &&
+	       input.consume_binary(size_dt_struct);
+}
+uint32_t
+string_table::add_string(string str)
+{
+	std::map<string, uint32_t>::iterator old = string_offsets.find(str);
+	if (old == string_offsets.end())
+	{
+		uint32_t start = size;
+		// Don't forget the trailing nul
+		size += str.size() + 1;
+		string_offsets.insert(std::make_pair(str, start));
+		strings.push_back(str);
+		return start;
+	}
+	else
+	{
+		return old->second;
+	}
+}
+
+void
+string_table::write(dtb::output_writer &writer)
+{
+	writer.write_comment(string("Strings table."));
+	writer.write_label(string("dt_strings_start"));
+	for (std::vector<string>::iterator i=strings.begin(), e=strings.end() ;
+	     i!=e ; ++i)
+	{
+		writer.write_string(*i);
+	}
+	writer.write_label(string("dt_strings_end"));
+}
+
+} // namespace dtb
+
+} // namespace dtc
+
diff --git a/usr.bin/dtc/dtb.hh b/usr.bin/dtc/dtb.hh
new file mode 100644
index 0000000..2c5f39e
--- /dev/null
+++ b/usr.bin/dtc/dtb.hh
@@ -0,0 +1,365 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _DTB_HH_
+#define _DTB_HH_
+#include <map>
+#include "string.hh"
+
+#include <assert.h>
+
+namespace dtc
+{
+/**
+ * The dtb namespace contains code related to the generation of device tree
+ * blobs, the binary representation of flattened device trees.  The abstract
+ * tree representation calls into this code to generate the output.
+ */
+namespace dtb
+{
+/** The token types in the DTB, as defined by §7.4.1 of the ePAPR
+ * specification.  All of these values are written in big-endian format in the
+ * output.
+ */
+enum token_type
+{
+	/**
+	 * Marker indicating the start of a node in the tree.  This is followed
+	 * by the nul-terminated name.  If a unit address is specified, then
+	 * the name also contains the address, with an @ symbol between the end
+	 * of the name and the start of the address.
+	 *
+	 * The name is then padded such that the next token begins on a 4-byte
+	 * boundary.  The node may contain properties, other nodes, both, or be
+	 * empty.
+	 */
+	FDT_BEGIN_NODE = 0x00000001,
+	/**
+	 * Marker indicating the end of a node.  
+	 */
+	FDT_END_NODE   = 0x00000002,
+	/**
+	 * The start of a property.  This is followed by two 32-bit big-endian
+	 * values.  The first indicates the length of the property value, the
+	 * second its index in the strings table.  It is then followed by the
+	 * property value, if the value is of non-zero length.
+	 */
+	FDT_PROP       = 0x00000003,
+	/**
+	 * Ignored token.  May be used for padding inside DTB nodes.
+	 */
+	FDT_NOP        = 0x00000004,
+	/**
+	 * Marker indicating the end of the tree.
+	 */
+	FDT_END        = 0x00000009
+};
+
+/**
+ * Returns the token as a string.  This is used for debugging and for printing
+ * human-friendly error messages about malformed DTB input.
+ */
+inline const char *token_type_name(token_type t)
+{
+	switch(t)
+	{
+		case FDT_BEGIN_NODE:
+			return "FDT_BEGIN_NODE";
+		case FDT_END_NODE:
+			return "FDT_END_NODE";
+		case FDT_PROP:
+			return "FDT_PROP";
+		case FDT_NOP:
+			return "FDT_NOP";
+		case FDT_END:
+			return "FDT_END";
+	}
+	assert(0);
+}
+
+/**
+ * Abstract class for writing a section of the output.  We create one
+ * of these for each section that needs to be written.  It is intended to build
+ * a temporary buffer of the output in memory and then write it to a file
+ * stream.  The size can be returned after all of the data has been written
+ * into the internal buffer, so the sizes of the three tables can be calculated
+ * before storing them in the buffer.
+ */
+struct output_writer
+{
+	/**
+	 * Writes a label into the output stream.  This is only applicable for
+	 * assembly output, where the labels become symbols that can be
+	 * resolved at link time.
+	 */
+	virtual void write_label(string name)   = 0;
+	/**
+	 * Writes a comment into the output stream.  Useful only when debugging
+	 * the output.
+	 */
+	virtual void write_comment(string name) = 0;
+	/**
+	 * Writes a string.  A nul terminator is implicitly added.
+	 */
+	virtual void write_string(string name)  = 0;
+	/**
+	 * Writes a single 8-bit value.
+	 */
+	virtual void write_data(uint8_t)        = 0;
+	/**
+	 * Writes a single 32-bit value.  The value is written in big-endian
+	 * format, but should be passed in the host's native endian.
+	 */
+	virtual void write_data(uint32_t)       = 0;
+	/**
+	 * Writes a single 64-bit value.  The value is written in big-endian
+	 * format, but should be passed in the host's native endian.
+	 */
+	virtual void write_data(uint64_t)       = 0;
+	/**
+	 * Writes the collected output to the specified file descriptor.
+	 */
+	virtual void write_to_file(int fd)      = 0;
+	/**
+	 * Returns the number of bytes.
+	 */
+	virtual uint32_t size()                 = 0;
+	/**
+	 * Helper for writing tokens to the output stream.  This writes a
+	 * comment above the token describing its value, for easier debugging
+	 * of the output.
+	 */
+	inline void write_token(token_type t)
+	{
+		write_comment(token_type_name(t));
+		write_data((uint32_t)t);
+	}
+	/**
+	 * Helper function that writes a byte buffer to the output, one byte at
+	 * a time.
+	 */
+	void write_data(byte_buffer b);
+};
+
+/**
+ * Binary file writer.  This class is responsible for writing the DTB output
+ * directly in blob format.
+ */
+class binary_writer : public output_writer
+{
+	/**
+	 * The internal buffer used to store the blob while it is being
+	 * constructed.
+	 */
+	byte_buffer buffer;
+	public:
+	/**
+	 *  The binary format does not support labels, so this method
+	 * does nothing.
+	 */
+	virtual void write_label(string name) {}
+	/**
+	 * Comments are ignored by the binary writer.
+	 */
+	virtual void write_comment(string name) {}
+	virtual void write_string(string name);
+	virtual void write_data(uint8_t v);
+	virtual void write_data(uint32_t v);
+	virtual void write_data(uint64_t v);
+	virtual void write_to_file(int fd);
+	virtual uint32_t size();
+};
+/**
+ * Assembly writer.  This class is responsible for writing the output in an
+ * assembly format that is suitable for linking into a kernel, loader, and so
+ * on.
+ */
+class asm_writer : public output_writer
+{
+	/**
+	 * The internal buffer for temporary values.  Note that this actually
+	 * contains ASCII text, but it is a byte buffer so that we can just
+	 * copy strings across as-is.
+	 */
+	byte_buffer buffer;
+	/**
+	 * The number of bytes written to the current line.  This is used to
+	 * allow line wrapping, where we aim to write four .byte directives to
+	 * make the alignment clearer.
+	 */
+	int byte_count;
+	/**
+	 * The current number of bytes written.  This is the number in binary
+	 * format, not the number of bytes in the buffer.
+	 */
+	uint32_t bytes_written;
+
+	/**
+	 * Writes a C string directly to the ouput as-is.  This is mainly used
+	 * for writing directives.
+	 */
+	void write_string(const char *c);
+	/**
+	 * Writes the string, starting on a new line.  
+	 */
+	void write_line(const char *c);
+	/**
+	 * Writes a byte in binary format.  This will emit a single .byte
+	 * directive, with up to four per line.
+	 */
+	void write_byte(uint8_t b);
+	public:
+	asm_writer() : byte_count(0), bytes_written(0) {}
+	virtual void write_label(string name);
+	virtual void write_comment(string name);
+	virtual void write_string(string name);
+	virtual void write_data(uint8_t v);
+	virtual void write_data(uint32_t v);
+	virtual void write_data(uint64_t v);
+	virtual void write_to_file(int fd);
+	virtual uint32_t size();
+};
+
+/**
+ * Class encapsulating the device tree blob header.  This class stores all of
+ * the values found in the header and is responsible for writing them to the
+ * output.
+ */
+struct header
+{
+	/**
+	 * Magic value, used to validate that this really is a device tree
+	 * blob.  Should always be set to 0xd00dfeed.
+	 */
+	uint32_t magic;
+	/**
+	 * The total size of the blob, including header, reservations, strings
+	 * table, and padding.
+	 */
+	uint32_t totalsize;
+	/**
+	 * The offset from the start of the blob of the struct table (i.e. the
+	 * part of the blob containing the entire device tree).
+	 */
+	uint32_t off_dt_struct;
+	/**
+	 * The offset from the start of the blob of the strings table.  
+	 */
+	uint32_t off_dt_strings;
+	/**
+	 * The offset of the reservation map from the start of the blob.
+	 */
+	uint32_t off_mem_rsvmap;
+	/**
+	 * The version of the blob.  This should always be 17.
+	 */
+	uint32_t version;
+	/**
+	 * The earliest version of the DTB specification with which this blob
+	 * is backwards compatible.  This should always be 16.
+	 */
+	uint32_t last_comp_version;
+	/**
+	 * The ID of the CPU where this boots.
+	 */
+	uint32_t boot_cpuid_phys;
+	/**
+	 * The size of the strings table.
+	 */
+	uint32_t size_dt_strings;
+	/**
+	 * The size of the struct table.
+	 */
+	uint32_t size_dt_struct;
+	/**
+	 * Writes the entire header to the specified output buffer.  
+	 */
+	void write(output_writer &out);
+	/**
+	 * Reads the header from bits binary representation in a blob.
+	 */
+	bool read_dtb(input_buffer &input);
+	/**
+	 * Default constructor.  Initialises the values that have sensible
+	 * defaults, leaves the others blank.
+	 */
+	header() : magic(0xd00dfeed), version(17), last_comp_version(16),
+		boot_cpuid_phys(0) {}
+};
+
+/**
+ * Class encapsulating the string table.  FDT strings are stored in a string
+ * section.  This maintains a map from strings to their offsets in the strings
+ * section.
+ *
+ * Note: We don't currently do suffix matching, which may save a small amount
+ * of space.
+ */
+class string_table {
+	/**
+	 * Map from strings to their offset. 
+	 */
+	std::map<string, uint32_t> string_offsets;
+	/**
+	 * The strings, in the order in which they should be written to the
+	 * output.  The order must be stable - adding another string must not
+	 * change the offset of any that we have already referenced - and so we
+	 * simply write the strings in the order that they are passed.
+	 */
+	std::vector<string> strings;
+	/**
+	 * The current size of the strings section.
+	 */
+	uint32_t size;
+	public:
+	/**
+	 * Default constructor, creates an empty strings table.
+	 */
+	string_table() : size(0) {}
+	/**
+	 * Adds a string to the table, returning the offset from the start
+	 * where it will be written.  If the string is already present, this
+	 * will return its existing offset, otherwise it will return a new
+	 * offset.
+	 */
+	uint32_t add_string(string str);
+	/**
+	 * Writes the strings table to the specified output.
+	 */
+	void write(dtb::output_writer &writer);
+};
+
+} // namespace dtb
+
+} // namespace dtc
+
+#endif // !_DTB_HH_
diff --git a/usr.bin/dtc/dtc.1 b/usr.bin/dtc/dtc.1
new file mode 100644
index 0000000..79c3bee
--- /dev/null
+++ b/usr.bin/dtc/dtc.1
@@ -0,0 +1,280 @@
+.\"-
+.\" Copyright (c) 2013 David Chisnall
+.\" All rights reserved.
+.\"
+.\" This software was developed by SRI International and the University of
+.\" Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+.\" ("CTSRD"), as part of the DARPA CRASH research programme.
+.\"
+.\" This software was developed by SRI International and the University of
+.\" Redistribution and use in source and binary forms, with or without
+.\" modification, are permitted provided that the following conditions
+.\" are met:
+.\" 1. Redistributions of source code must retain the above copyright
+.\"    notice, this list of conditions and the following disclaimer.
+.\" 2. Redistributions in binary form must reproduce the above copyright
+.\"    notice, this list of conditions and the following disclaimer in the
+.\"    documentation and/or other materials provided with the distribution.
+.\"
+.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+.\" SUCH DAMAGE.
+.\"
+.\" $FreeBSD$
+.\"/
+.Dd January 1, 2013
+.Dt DTC 1
+.Os
+.Sh NAME
+.Nm dtc
+.Nd device tree compiler
+.Sh SYNOPSIS
+.Nm
+.Op Fl fhsv
+.Op Fl b Ar boot_cpu_id
+.Op Fl d Ar dependency_file
+.Op Fl E Ar [no-]checker_name
+.Op Fl H Ar phandle_format
+.Op Fl I Ar input_format
+.Op Fl O Ar output_format
+.Op Fl o Ar output_file
+.Op Fl R Ar entries
+.Op Fl S Ar bytes
+.Op Fl p Ar bytes
+.Op Fl V Ar blob_version
+.Op Fl W Ar [no-]checker_name
+.Ar input_file
+.Sh DESCRIPTION
+The
+.Nm
+utility converts flattened device tree (FDT) representations.  It is most
+commonly used to generate device tree blobs (DTB), the binary representation of
+an FDT, from device tree sources (DTS), the ASCII text source representation.
+.Pp
+The binary can be written in two formats, binary and assembly.  The binary is
+identical to the in-memory representation and can be used directly by firmware,
+loaders, and so on.  The assembly format, documented in
+.Sx "ASM FORMAT" ,
+will produce the same binary format when assembled, but also includes some
+global variables that refer to parts of the table.  This format is most
+commonly used to produce a kernel specific to a device, with the device tree
+blob compiled in.
+.Pp
+The options are as follows:
+.Bl -tag -width indent
+.It Fl d Ar dependency_file
+Writes a dependency file understandable by make to the specified file.  This
+file can be included in a Makefile and will ensure that the output file depends
+on the input file and any files that it includes.  This argument is only useful
+when the input is DTS, as only the source format has a notion of inclusions.
+.It Fl E Ar [no-]checker_name
+Enable or disable a specified checker.  The argument is the name of the
+checker.  The full list of checkers is given in
+.Sx CHECKERS .
+.It Fl f
+Force the tool to attempt to generate the output, even if the input had errors.
+.It Fl h
+Display the help text and exit.
+.It Fl H Ar phandle_format 
+Specifies the type of phandle nodes to generate in the output.  Valid values
+are:
+.Pp
+.Bl -tag -width indent -compact
+.It Ar linux
+Generate the legacy linux,phandle nodes expected by older systems.
+.It Ar epapr
+Generate the phandle nodes, as described in the ePAPR specification.  This is
+the most sensible option for device trees being used with
+.Fx .
+.It Ar both
+Generate both, for maximum compatibility.
+.El
+.It Fl I Ar input_format
+Specifies the input format.  Valid values are:
+.Pp
+.Bl -tag -width indent -compact
+.It Ar dtb
+Device tree blob.  The binary representation of the FDT.
+.It Ar dts
+Device tree source.  The ASCII representation of the FDT.  This is the default
+if the input format is not explicitly stated.
+.El
+.It Fl O Ar output_format
+Specifies the output format.  Valid values are:
+.Pp
+.Bl -tag -width indent -compact
+.It Ar asm
+Assembler source for generating a device tree blob, as described in
+.Sx "ASM FORMAT" .
+.It Ar dtb
+Device tree blob.  The binary representation of the FDT.  This is the default
+if the output format is not explicitly stated.
+.It Ar dts
+Device tree source.  The ASCII representation of the FDT.
+.El
+.It Fl o Ar output_file
+The file to which to write the output.  
+.It Fl R Ar entries
+The number of empty reservation table entries to pad the table with.  This is
+useful if you are generating a device tree blob for bootloader or similar that
+needs to reserve some memory before passing control to the operating system.
+.It Fl S Ar bytes
+The minimum size in bytes of the blob.  The blob will be padded after the
+strings table to ensure that it is the correct size.  This is useful for
+environments where the device tree blob must be modified in place.  
+.It Fl p Ar bytes
+The number of bytes of padding to add to the blob.  The blob will be padded
+after the strings table to ensure that it is the correct size.  This is useful
+for environments where the device tree blob must be modified in place.  
+.It Fl W Ar [no-]checker_name
+Enable or disable a specified checker.  This is an alias for
+.Fl E .
+.It Fl s
+Sorts the properties and nodes in the tree.  This is mainly useful when using
+tools like
+.Xr diff 1
+to compare two device tree sources.
+.It Fl V Ar output_version
+The version of the format to output.  This is only relevant for binary outputs,
+and only a value of 17 is currently supported.
+.It Fl v
+Display the tool version and exit.
+.It Ar input_file
+The source file.
+.El
+.Sh "ASM FORMAT"
+The assembly format defines several globals that can be referred to from other
+compilation units, in addition to any labels specified in the source.  These
+are:
+.Pp
+.Bl -tag -width "dt_strings_start" -compact -offset indent
+.It dt_blob_start
+start of the device tree blob.
+.It dt_header
+start of the header, usually identical to the start of the blob.
+.It dt_reserve_map
+start of the reservation map.
+.It dt_struct_start
+start of the structure table.
+.It dt_struct_end
+end of the structure table.
+.It dt_strings_start
+start of the strings table.
+.It dt_strings_end
+end of the strings table.
+.It dt_blob_end
+end of the device tree blob.
+.El
+.Pp
+.Sh CHECKERS
+The utility provides a number of semantic checks on the correctness of the
+tree.  These can be disabled with the
+.Fl W
+flag.  For example,
+.Fl W Ar no-type-phandle
+will disable the phandle type check.  The supported checks are:
+.Pp
+.Bl -tag -width "no-type-phandle" -compact -offset indent
+.It type-compatible
+Checks the type of the 
+.Va compatible
+property.
+.It type-model
+Checks the type of the 
+.Va model
+property.
+.It type-compatible
+Checks the type of the 
+.Va compatible 
+property.
+.El
+.Sh EXAMPLES
+The command:
+.Pp
+.Dl "dtc -o blob.S -O asm device.dts"
+.Pp
+will generate a 
+.Pa blob.S
+file from the device tree source
+.Pa device.dts
+and print errors if any occur during parsing or property checking.  The
+resulting file can be assembled and linked into a binary.
+.Pp
+The command:
+.Pp
+.Dl "dtc -o - -O dts -I dtb device.dtb"
+.Pp
+will write the device tree source for the device tree blob
+.Pa device.dtb
+to the standard output.  This is useful when debugging device trees.
+.Sh COMPATIBILITY
+This utility is intended to be compatible with the device tree compiler
+provided by elinux.org.  Currently, it implements the subset of features
+required to build FreeBSD and others that have been requested by FreeBSD
+developers.
+.Pp
+The 
+.Ar fs
+input format is not supported.  This builds a tree from a Linux
+.Pa  /proc/device-tree ,
+a file system hierarchy not found in FreeBSD, which instead exposes the DTB
+directly via a sysctl.
+.Pp
+The warnings and errors supported by the elinux.org tool are not documented.
+This tool supports the warnings described in the
+.Sx CHECKERS
+section.
+.Sh STANDARDS
+The device tree formats understood by this tool conform to the Power.org
+Standard for Embedded Power Architecture Platform Requirements
+.Pq Vt ePAPR ,
+except as noted in the
+.Sx BUGS
+section and with the following exceptions for compatibility with the elinux.org
+tool:
+.Pp
+.Bl -bullet -compact
+.It
+The target of cross references is defined to be a node name in the
+specification, but is in fact a label.
+.El
+.Pp
+The /include/ directive is not part of the standard, however it is implemented
+with the semantics compatible with the elinux.org tool.  It must appear in the
+top level of a file, and imports a new root definition.  If a file, plus all of
+its inclusions, contains multiple roots then they 
+.Sh HISTORY
+A dtc tool first appeared in
+.Fx 9.0 .
+This version of the tool first appeared in 
+.Fx 10.0 .
+.Sh AUTHORS
+.An David T. Chisnall
+.Pp
+Note: The fact that the tool and the author share the same initials is entirely
+coincidental.
+.Sh BUGS
+The device tree compiler does not yet support the following features:
+.Pp
+.Bl -bullet -compact
+.It
+Labels in the middle of property values.  This is only useful in the assembly
+output, and only vaguely useful there, so is unlikely to be added soon.
+.It
+Full paths, rather than labels, as the targets for phandles.  This is not very
+hard to add, but will probably not be added until something actually needs it.
+.El
+.Pp
+The current version performs a very limited set of semantic checks on the tree.
+This will be improved in future versions.
+.Sh SEE ALSO
+.Xr fdt 4
+.Pp
diff --git a/usr.bin/dtc/dtc.cc b/usr.bin/dtc/dtc.cc
new file mode 100644
index 0000000..6d1966f
--- /dev/null
+++ b/usr.bin/dtc/dtc.cc
@@ -0,0 +1,333 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#include <sys/resource.h>
+#include <time.h>
+#include <stdio.h>
+#include <fcntl.h>
+#include <libgen.h>
+
+#include "fdt.hh"
+#include "checking.hh"
+
+using namespace dtc;
+
+/**
+ * The current major version of the tool.
+ */
+int version_major = 0;
+/**
+ * The current minor version of the tool.
+ */
+int version_minor = 4;
+/**
+ * The current patch level of the tool.
+ */
+int version_patch = 0;
+
+static void usage(const char* argv0)
+{
+	fprintf(stderr, "Usage:\n"
+		"\t%s\t[-fhsv] [-b boot_cpu_id] [-d dependency_file]"
+			"[-E [no-]checker_name]\n"
+		"\t\t[-H phandle_format] [-I input_format]"
+			"[-O output_format]\n"
+		"\t\t[-o output_file] [-R entries] [-S bytes] [-p bytes]"
+			"[-V blob_version]\n"
+		"\t\t-W [no-]checker_name] input_file\n", basename(argv0));
+}
+
+/**
+ * Prints the current version of this program..
+ */
+static void version(const char* progname)
+{
+	fprintf(stderr, "Version: %s %d.%d.%d\n", progname, version_major,
+			version_minor, version_patch);
+}
+
+using fdt::device_tree;
+
+int
+main(int argc, char **argv)
+{
+	int ch;
+	int outfile = fileno(stdout);
+	const char *outfile_name = "-";
+	const char *in_file = "-";
+	FILE *depfile = 0;
+	bool debug_mode = false;
+	void (device_tree::*write_fn)(int) = &device_tree::write_binary;
+	void (device_tree::*read_fn)(const char*, FILE*) =
+		&device_tree::parse_dts;
+	uint32_t boot_cpu;
+	bool boot_cpu_specified = false;
+	bool keep_going = false;
+	bool sort = false;
+	clock_t c0 = clock();
+	class device_tree tree;
+	fdt::checking::check_manager checks;
+	const char *options = "hqI:O:o:V:d:R:S:p:b:fisvH:W:E:D";
+
+	// Don't forget to update the man page if any more options are added.
+	while ((ch = getopt(argc, argv, options)) != -1)
+	{
+		switch (ch)
+		{
+		case 'h':
+			usage(argv[0]);
+			return EXIT_SUCCESS;
+		case 'v':
+			version(argv[0]);
+			return EXIT_SUCCESS;
+		case 'I':
+		{
+			string arg = string(optarg);
+			if (arg == string("dtb"))
+			{
+				read_fn = &device_tree::parse_dtb;
+			}
+			else if (arg == string("dts"))
+			{
+				read_fn = &device_tree::parse_dts;
+			}
+			else
+			{
+				fprintf(stderr, "Unknown input format: %s\n", optarg);
+				return EXIT_FAILURE;
+			}
+			break;
+		}
+		case 'O':
+		{
+			string arg = string(optarg);
+			if (arg == string("dtb"))
+			{
+				write_fn = &device_tree::write_binary;
+			}
+			else if (arg == string("asm"))
+			{
+				write_fn = &device_tree::write_asm;
+			}
+			else if (arg == string("dts"))
+			{
+				write_fn = &device_tree::write_dts;
+			}
+			else
+			{
+				fprintf(stderr, "Unknown output format: %s\n", optarg);
+				return EXIT_FAILURE;
+			}
+			break;
+		}
+		case 'o':
+		{
+			outfile_name = optarg;
+			outfile = open(optarg, O_CREAT | O_TRUNC | O_WRONLY, 0666);
+			if (outfile == -1)
+			{
+				perror("Unable to open output file");
+				return EXIT_FAILURE;
+			}
+			break;
+		}
+		case 'D':
+			debug_mode = true;
+			break;
+		case 'V':
+			if (string(optarg) == string("17"))
+			{
+				fprintf(stderr, "Unknown output format version: %s\n", optarg);
+				return EXIT_FAILURE;
+			}
+			break;
+		case 'd':
+		{
+			if (depfile != 0)
+			{
+				fclose(depfile);
+			}
+			if (string(optarg) == string("-"))
+			{
+				depfile = stdout;
+			}
+			else
+			{
+				depfile = fdopen(open(optarg, O_CREAT | O_TRUNC | O_WRONLY, 0666), "w");
+				if (depfile == 0)
+				{
+					perror("Unable to open dependency file");
+					return EXIT_FAILURE;
+				}
+			}
+			break;
+		}
+		case 'H':
+		{
+			string arg = string(optarg);
+			if (arg == string("both"))
+			{
+				tree.set_phandle_format(device_tree::BOTH);
+			}
+			else if (arg == string("epapr"))
+			{
+				tree.set_phandle_format(device_tree::EPAPR);
+			}
+			else if (arg == string("linux"))
+			{
+				tree.set_phandle_format(device_tree::LINUX);
+			}
+			else
+			{
+				fprintf(stderr, "Unknown phandle format: %s\n", optarg);
+				return EXIT_FAILURE;
+			}
+			break;
+		}
+		case 'b':
+			// Don't bother to check if strtoll fails, just
+			// use the 0 it returns.
+			boot_cpu = (uint32_t)strtoll(optarg, 0, 10);
+			boot_cpu_specified = true;
+			break;
+		case 'f':
+			keep_going = true;
+			break;
+		case 'W':
+		case 'E':
+		{
+			string arg = string(optarg);
+			if ((arg.size() > 3) && (strncmp(optarg, "no-", 3) == 0))
+			{
+				arg = string(optarg+3);
+				if (!checks.disable_checker(arg))
+				{
+					fprintf(stderr, "Checker %s either does not exist or is already disabled\n", optarg+3);
+				}
+				break;
+			}
+			if (!checks.enable_checker(arg))
+			{
+				fprintf(stderr, "Checker %s either does not exist or is already enabled\n", optarg);
+			}
+			break;
+		}
+		case 's':
+		{
+			sort = true;
+			break;
+		}
+		case 'i':
+		{
+			tree.add_include_path(optarg);
+			break;
+		}
+		// Should quiet warnings, but for now is silently ignored.
+		case 'q':
+			break;
+		case 'R':
+			tree.set_empty_reserve_map_entries(strtoll(optarg, 0, 10));
+			break;
+		case 'S':
+			tree.set_blob_minimum_size(strtoll(optarg, 0, 10));
+			break;
+		case 'p':
+			tree.set_blob_padding(strtoll(optarg, 0, 10));
+			break;
+		default:
+			fprintf(stderr, "Unknown option %c\n", ch);
+			return EXIT_FAILURE;
+		}
+	}
+	if (optind < argc)
+	{
+		in_file = argv[optind];
+	}
+	if (depfile != 0)
+	{
+		fputs(outfile_name, depfile);
+		fputs(": ", depfile);
+		fputs(in_file, depfile);
+	}
+	clock_t c1 = clock();
+	(tree.*read_fn)(in_file, depfile);
+	// Override the boot CPU found in the header, if we're loading from dtb
+	if (boot_cpu_specified)
+	{
+		tree.set_boot_cpu(boot_cpu);
+	}
+	if (sort)
+	{
+		tree.sort();
+	}
+	if (depfile != 0)
+	{
+		putc('\n', depfile);
+		fclose(depfile);
+	}
+	if (!(tree.is_valid() || keep_going))
+	{
+		fprintf(stderr, "Failed to parse tree.  Unhappy face!\n");
+		return EXIT_FAILURE;
+	}
+	clock_t c2 = clock();
+	if (!(checks.run_checks(&tree, true) || keep_going))
+	{
+		return EXIT_FAILURE;
+	}
+	clock_t c3 = clock();
+	(tree.*write_fn)(outfile);
+	close(outfile);
+	clock_t c4 = clock();
+
+	if (debug_mode)
+	{
+		struct rusage r;
+
+		getrusage(RUSAGE_SELF, &r);
+		fprintf(stderr, "Peak memory usage: %ld bytes\n", r.ru_maxrss);
+		fprintf(stderr, "Setup and option parsing took %f seconds\n",
+				((double)(c1-c0))/CLOCKS_PER_SEC);
+		fprintf(stderr, "Parsing took %f seconds\n",
+				((double)(c2-c1))/CLOCKS_PER_SEC);
+		fprintf(stderr, "Checking took %f seconds\n",
+				((double)(c3-c2))/CLOCKS_PER_SEC);
+		fprintf(stderr, "Generating output took %f seconds\n",
+				((double)(c4-c3))/CLOCKS_PER_SEC);
+		fprintf(stderr, "Total time: %f seconds\n",
+				((double)(c4-c0))/CLOCKS_PER_SEC);
+		// This is not needed, but keeps valgrind quiet.
+		fclose(stdin);
+	}
+	return EXIT_SUCCESS;
+}
+
diff --git a/usr.bin/dtc/fdt.cc b/usr.bin/dtc/fdt.cc
new file mode 100644
index 0000000..70b7d45
--- /dev/null
+++ b/usr.bin/dtc/fdt.cc
@@ -0,0 +1,1357 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#include "fdt.hh"
+
+#include <algorithm>
+#include <inttypes.h>
+#include <fcntl.h>
+#include <libgen.h>
+#include "dtb.hh"
+
+namespace dtc
+{
+
+namespace fdt
+{
+
+uint32_t
+property_value::get_as_uint32()
+{
+	if (byte_data.size() != 4)
+	{
+		return 0;
+	}
+	uint32_t v = 0;
+	v &= byte_data[0] << 24;
+	v &= byte_data[1] << 16;
+	v &= byte_data[2] << 8;
+	v &= byte_data[3] << 0;
+	return v;
+}
+
+void
+property_value::push_to_buffer(byte_buffer &buffer)
+{
+	if (!byte_data.empty())
+	{
+		buffer.insert(buffer.end(), byte_data.begin(), byte_data.end());
+	}
+	else
+	{
+		string_data.push_to_buffer(buffer, true);
+		// Trailing nul
+		buffer.push_back(0);
+	}
+}
+
+void
+property_value::write_dts(FILE *file)
+{
+	resolve_type();
+	switch (type)
+	{
+		default:
+			assert(0 && "Invalid type");
+		case STRING:
+		case STRING_LIST:
+		case CROSS_REFERENCE:
+			write_as_string(file);
+			break;
+		case PHANDLE:
+			write_as_cells(file);
+			break;
+		case BINARY:
+			if (byte_data.size() % 4 == 0)
+			{
+				write_as_cells(file);
+				break;
+			}
+			write_as_bytes(file);
+			break;
+	}
+}
+
+void
+property_value::resolve_type()
+{
+	if (type != UNKNOWN)
+	{
+		return;
+	}
+	if (byte_data.empty())
+	{
+		type = STRING;
+		return;
+	}
+	if (byte_data.back() == 0)
+	{
+		bool is_all_printable = true;
+		int nuls = 0;
+		int bytes = 0;
+		for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i<e ; i++)
+		{
+			bytes++;
+			is_all_printable &= (*i == '\0') || isprint(*i);
+			if (*i == '\0')
+			{
+				nuls++;
+			}
+			if (!is_all_printable)
+			{
+				break;
+			}
+		}
+		if (is_all_printable && (bytes > nuls))
+		{
+			type = STRING;
+			if (nuls > 0)
+			{
+				type = STRING_LIST;
+			}
+			return;
+		}
+	}
+	type = BINARY;
+}
+
+void
+property_value::write_as_string(FILE *file)
+{
+	putc('"', file);
+	if (byte_data.empty())
+	{
+		string_data.print(file);
+	}
+	else
+	{
+		for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end()-1; i!=e ; ++i)
+		{
+			// FIXME Escape tabs, newlines, and so on.
+			if (*i == '\0')
+			{
+				fputs("\", \"", file);
+				continue;
+			}
+			putc(*i, file);
+		}
+	}
+	putc('"', file);
+}
+
+void
+property_value::write_as_cells(FILE *file)
+{
+	putc('<', file);
+	assert((byte_data.size() % 4) == 0);
+	for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; ++i)
+	{
+		uint32_t v = 0;
+		v = (v << 8) | *i;
+		++i;
+		v = (v << 8) | *i;
+		++i;
+		v = (v << 8) | *i;
+		++i;
+		v = (v << 8) | *i;
+		fprintf(file, "0x%" PRIx32, v);
+		if (i+1 != e)
+		{
+			putc(' ', file);
+		}
+	}
+	putc('>', file);
+}
+
+void
+property_value::write_as_bytes(FILE *file)
+{
+	putc('[', file);
+	for (byte_buffer::iterator i=byte_data.begin(), e=byte_data.end(); i!=e ; i++)
+	{
+		fprintf(file, "%hhx", *i);
+		if (i+1 != e)
+		{
+			putc(' ', file);
+		}
+	}
+	putc(']', file);
+}
+
+void
+property::parse_string(input_buffer &input)
+{
+	property_value v;
+	assert(input[0] == '"');
+	++input;
+	const char *start = (const char*)input;
+	int length = 0;
+	while (char c = input[0])
+	{
+		if (c == '"' && input[-1] != '\\')
+		{
+			input.consume('"');
+			break;
+		}
+		++input;
+		++length;
+	}
+	v.string_data = string(start, length);
+	values.push_back(v);
+}
+
+void
+property::parse_cells(input_buffer &input)
+{
+	assert(input[0] == '<');
+	++input;
+	property_value v;
+	input.next_token();
+	while (!input.consume('>'))
+	{
+		input.next_token();
+		// If this is a phandle then we need to get the name of the
+		// referenced node
+		if (input.consume('&'))
+		{
+			input.next_token();
+			// FIXME: We should support full paths here, but we
+			// don't.
+			string referenced = string::parse_node_name(input);
+			if (referenced.empty())
+			{
+				input.parse_error("Expected node name");
+				valid = false;
+				return;
+			}
+			input.next_token();
+			// If we already have some bytes, make the phandle a
+			// separate component.
+			if (!v.byte_data.empty())
+			{
+				values.push_back(v);
+				v = property_value();
+			}
+			v.string_data = referenced;
+			v.type = property_value::PHANDLE;
+			values.push_back(v);
+			v = property_value();
+		}
+		else
+		{
+			//FIXME: We should support labels in the middle
+			//of these, but we don't.
+			long long val;
+			if (!input.consume_integer(val))
+			{
+				input.parse_error("Expected numbers in array of cells");
+				valid = false;
+				return;
+			}
+			push_big_endian(v.byte_data, (uint32_t)val);
+			input.next_token();
+		}
+	}
+	// Don't store an empty string value here.
+	if (v.byte_data.size() > 0)
+	{
+		values.push_back(v);
+	}
+}
+
+void
+property::parse_bytes(input_buffer &input)
+{
+	assert(input[0] == '[');
+	++input;
+	property_value v;
+	input.next_token();
+	while (!input.consume(']'))
+	{
+		{
+			//FIXME: We should support
+			//labels in the middle of
+			//these, but we don't.
+			uint8_t val;
+			if (!input.consume_hex_byte(val))
+			{
+				input.parse_error("Expected hex bytes in array of bytes");
+				valid = false;
+				return;
+			}
+			v.byte_data.push_back(val);
+			input.next_token();
+		}
+	}
+	values.push_back(v);
+}
+
+void
+property::parse_reference(input_buffer &input)
+{
+	assert(input[0] == '&');
+	++input;
+	input.next_token();
+	property_value v;
+	v.string_data = string::parse_node_name(input);
+	if (v.string_data.empty())
+	{
+		input.parse_error("Expected node name");
+		valid = false;
+		return;
+	}
+	v.type = property_value::CROSS_REFERENCE;
+	values.push_back(v);
+}
+
+property::property(input_buffer &structs, input_buffer &strings)
+{
+	uint32_t name_offset;
+	uint32_t length;
+	valid = structs.consume_binary(length) &&
+		structs.consume_binary(name_offset);
+	if (!valid)
+	{
+		fprintf(stderr, "Failed to read property\n");
+		return;
+	}
+	// Find the name
+	input_buffer name_buffer = strings.buffer_from_offset(name_offset);
+	if (name_buffer.empty())
+	{
+		fprintf(stderr, "Property name offset %" PRIu32
+			" is past the end of the strings table\n",
+			name_offset);
+		valid = false;
+		return;
+	}
+	key = string(name_buffer);
+	// Read the value
+	uint8_t byte;
+	property_value v;
+	for (uint32_t i=0 ; i<length ; i++)
+	{
+		if (!(valid = structs.consume_binary(byte)))
+		{
+			fprintf(stderr, "Failed to read property value\n");
+			return;
+		}
+		v.byte_data.push_back(byte);
+	}
+	values.push_back(v);
+}
+
+property::property(input_buffer &input, string k, string l) : key(k), label(l),
+	valid(true)
+{
+	do {
+		input.next_token();
+		switch (input[0])
+		{
+			default:
+				input.parse_error("Invalid property value.");
+				valid = false;
+				return;
+			case '"':
+				parse_string(input);
+				break;
+			case '<':
+				parse_cells(input);
+				break;
+			case '[':
+				parse_bytes(input);
+				break;
+			case '&':
+				parse_reference(input);
+				break;
+			case ';':
+			{
+				break;
+			}
+		}
+		input.next_token();
+	} while (input.consume(','));
+	if (!input.consume(';'))
+	{
+		input.parse_error("Expected ; at end of property");
+		valid = false;
+	}
+}
+
+property*
+property::parse_dtb(input_buffer &structs, input_buffer &strings)
+{
+	property *p = new property(structs, strings);
+	if (!p->valid)
+	{
+		delete p;
+		p = 0;
+	}
+	return p;
+}
+
+property*
+property::parse(input_buffer &input, string key, string label)
+{
+	property *p = new property(input, key, label);
+	if (!p->valid)
+	{
+		delete p;
+		p = 0;
+	}
+	return p;
+}
+
+void
+property::write(dtb::output_writer &writer, dtb::string_table &strings)
+{
+	writer.write_token(dtb::FDT_PROP);
+	byte_buffer value_buffer;
+	for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
+	{
+		i->push_to_buffer(value_buffer);
+	}
+	writer.write_data((uint32_t)value_buffer.size());
+	writer.write_comment(key);
+	writer.write_data(strings.add_string(key));
+	writer.write_data(value_buffer);
+}
+
+void
+property::write_dts(FILE *file, int indent)
+{
+	for (int i=0 ; i<indent ; i++)
+	{
+		putc('\t', file);
+	}
+	if (label != string())
+	{
+		label.print(file);
+		fputs(": ", file);
+	}
+	if (key != string())
+	{
+		key.print(file);
+	}
+	if (!values.empty())
+	{
+		fputs(" = ", file);
+		for (value_iterator i=begin(), e=end() ; i!=e ; ++i)
+		{
+			i->write_dts(file);
+			if (i+1 != e)
+			{
+				putc(',', file);
+				putc(' ', file);
+			}
+		}
+	}
+	fputs(";\n", file);
+}
+
+string
+node::parse_name(input_buffer &input, bool &is_property, const char *error)
+{
+	if (!valid)
+	{
+		return string();
+	}
+	input.next_token();
+	if (is_property)
+	{
+		return string::parse_property_name(input);
+	}
+	string n = string::parse_node_or_property_name(input, is_property);
+	if (n.empty())
+	{
+		if (n.empty())
+		{
+			input.parse_error(error);
+			valid = false;
+		}
+	}
+	return n;
+}
+
+node::node(input_buffer &structs, input_buffer &strings) : valid(true)
+{
+	const char *name_start = (const char*)structs;
+	int name_length = 0;
+	while (structs[0] != '\0' && structs[0] != '@')
+	{
+		name_length++;
+		++structs;
+	}
+	name = string(name_start, name_length);
+	if (structs[0] == '@')
+	{
+		++structs;
+		name_start = (const char*)structs;
+		name_length = 0;
+		while (structs[0] != '\0')
+		{
+			name_length++;
+			++structs;
+		}
+		unit_address = string(name_start, name_length);
+	}
+	++structs;
+	uint32_t token;
+	while (structs.consume_binary(token))
+	{
+		switch (token)
+		{
+			default:
+				fprintf(stderr, "Unexpected token 0x%" PRIx32
+					" while parsing node.\n", token);
+				valid = false;
+				return;
+			// Child node, parse it.
+			case dtb::FDT_BEGIN_NODE:
+			{
+				node *child = node::parse_dtb(structs, strings);
+				if (child == 0)
+				{
+					valid = false;
+					return;
+				}
+				children.push_back(child);
+				break;
+			}
+			// End of this node, no errors.
+			case dtb::FDT_END_NODE:
+				return;
+			// Property, parse it.
+			case dtb::FDT_PROP:
+			{
+				property *prop = property::parse_dtb(structs, strings);
+				if (prop == 0)
+				{
+					valid = false;
+					return;
+				}
+				properties.push_back(prop);
+				break;
+			}
+				break;
+			// End of structs table.  Should appear after
+			// the end of the last node.
+			case dtb::FDT_END:
+				fprintf(stderr, "Unexpected FDT_END token while parsing node.\n");
+				valid = false;
+				return;
+			// NOPs are padding.  Ignore them.
+			case dtb::FDT_NOP:
+				break;
+		}
+	}
+	fprintf(stderr, "Failed to read token from structs table while parsing node.\n");
+	valid = false;
+	return;
+}
+
+node::node(input_buffer &input, string n, string l, string a) : 
+	label(l), name(n), unit_address(a), valid(true)
+{
+	if (!input.consume('{'))
+	{
+		input.parse_error("Expected { to start new device tree node.\n");
+	}
+	input.next_token();
+	while (valid && !input.consume('}'))
+	{
+		// flag set if we find any characters that are only in
+		// the property name character set, not the node 
+		bool is_property = false;
+		string child_name, child_label, child_address;
+		child_name = parse_name(input, is_property,
+				"Expected property or node name");
+		if (input.consume(':'))
+		{
+			// Node labels can contain any characters?  The
+			// spec doesn't say, so we guess so...
+			is_property = false;
+			child_label = child_name;
+			child_name = parse_name(input, is_property, "Expected property or node name");
+		}
+		if (input.consume('@'))
+		{
+			child_address = parse_name(input, is_property, "Expected unit address");
+		}
+		if (!valid)
+		{
+			return;
+		}
+		input.next_token();
+		// If we're parsing a property, then we must actually do that.
+		if (input.consume('='))
+		{
+			property *p= property::parse(input, child_name,
+					child_label);
+			if (p == 0)
+			{
+				valid = false;
+			}
+			else
+			{
+				properties.push_back(p);
+			}
+		}
+		else if (!is_property && input[0] == ('{'))
+		{
+			node *child = node::parse(input, child_name,
+					child_label, child_address);
+			if (child)
+			{
+				children.push_back(child);
+			}
+			else
+			{
+				valid = false;
+			}
+		}
+		else if (input.consume(';'))
+		{
+			properties.push_back(new property(child_name, child_label));
+		}
+		else
+		{
+			input.parse_error("Error parsing property.");
+			valid = false;
+		}
+		input.next_token();
+	}
+	input.consume(';');
+}
+
+bool
+node::cmp_properties(property *p1, property *p2)
+{
+	return p1->get_key() < p2->get_key();
+}
+
+bool
+node::cmp_children(node *c1, node *c2)
+{
+	if (c1->name == c2->name)
+	{
+		return c1->unit_address < c2->unit_address;
+	}
+	return c1->name < c2->name;
+}
+
+void
+node::sort()
+{
+	std::sort(property_begin(), property_end(), cmp_properties);
+	std::sort(child_begin(), child_end(), cmp_children);
+	for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+	{
+		(*i)->sort();
+	}
+}
+
+node*
+node::parse(input_buffer &input, string name, string label, string address)
+{
+	node *n = new node(input, name, label, address);
+	if (!n->valid)
+	{
+		delete n;
+		n = 0;
+	}
+	return n;
+}
+
+node*
+node::parse_dtb(input_buffer &structs, input_buffer &strings)
+{
+	node *n = new node(structs, strings);
+	if (!n->valid)
+	{
+		delete n;
+		n = 0;
+	}
+	return n;
+}
+
+node::~node()
+{
+	while (!children.empty())
+	{
+		delete children.back();
+		children.pop_back();
+	}
+	while (!properties.empty())
+	{
+		delete properties.back();
+		properties.pop_back();
+	}
+}
+
+property*
+node::get_property(string key)
+{
+	for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+	{
+		if ((*i)->get_key() == key)
+		{
+			return *i;
+		}
+	}
+	return 0;
+}
+
+void
+node::merge_node(node *other)
+{
+	if (!other->label.empty())
+	{
+		label = other->label;
+	}
+	// Note: this is an O(n*m) operation.  It might be sensible to
+	// optimise this if we find that there are nodes with very
+	// large numbers of properties, but for typical usage the
+	// entire vector will fit (easily) into cache, so iterating
+	// over it repeatedly isn't that expensive.
+	while (!other->properties.empty())
+	{
+		property *p = other->properties.front();
+		for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+		{
+			if ((*i)->get_key() == p->get_key())
+			{
+				delete *i;
+				properties.erase(i);
+				break;
+			}
+		}
+		add_property(p);
+		other->properties.erase(other->properties.begin());
+	}
+	while (!other->children.empty())
+	{
+		node *c = other->children.front();
+		bool found = false;
+		for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+		{
+			if ((*i)->name == c->name && (*i)->unit_address == c->unit_address)
+			{
+				(*i)->merge_node(c);
+				delete c;
+				found = true;
+				break;
+			}
+		}
+		if (!found)
+		{
+			children.push_back(c);
+		}
+		other->children.erase(other->children.begin());
+	}
+}
+
+void
+node::write(dtb::output_writer &writer, dtb::string_table &strings)
+{
+	writer.write_token(dtb::FDT_BEGIN_NODE);
+	byte_buffer name_buffer;
+	name.push_to_buffer(name_buffer);
+	if (unit_address != string())
+	{
+		name_buffer.push_back('@');
+		unit_address.push_to_buffer(name_buffer);
+	}
+	writer.write_comment(name);
+	writer.write_data(name_buffer);
+	writer.write_data((uint8_t)0);
+	for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+	{
+		(*i)->write(writer, strings);
+	}
+	for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+	{
+		(*i)->write(writer, strings);
+	}
+	writer.write_token(dtb::FDT_END_NODE);
+}
+
+void
+node::write_dts(FILE *file, int indent)
+{
+	for (int i=0 ; i<indent ; i++)
+	{
+		putc('\t', file);
+	}
+	if (label != string())
+	{
+		label.print(file);
+		fputs(": ", file);
+	}
+	if (name != string())
+	{
+		name.print(file);
+	}
+	if (unit_address != string())
+	{
+		putc('@', file);
+		unit_address.print(file);
+	}
+	fputs(" {\n\n", file);
+	for (property_iterator i=property_begin(), e=property_end() ; i!=e ; ++i)
+	{
+		(*i)->write_dts(file, indent+1);
+	}
+	for (child_iterator i=child_begin(), e=child_end() ; i!=e ; ++i)
+	{
+		(*i)->write_dts(file, indent+1);
+	}
+	for (int i=0 ; i<indent ; i++)
+	{
+		putc('\t', file);
+	}
+	fputs("};\n", file);
+}
+
+void
+device_tree::collect_names_recursive(node* n, node_path &path)
+{
+	string name = n->label;
+	path.push_back(std::make_pair(n->name, n->unit_address));
+	if (name != string())
+	{
+		if (node_names.find(name) == node_names.end())
+		{
+			node_names.insert(std::make_pair(name, n));
+			node_paths.insert(std::make_pair(name, path));
+		}
+		else
+		{
+			node_names[name] = (node*)-1;
+			std::map<string, node_path>::iterator i = node_paths.find(name);
+			if (i != node_paths.end())
+			{
+				node_paths.erase(name);
+			}
+			fprintf(stderr, "Label not unique: ");
+			name.dump();
+			fprintf(stderr, ".  References to this label will not be resolved.");
+		}
+	}
+	for (node::child_iterator i=n->child_begin(), e=n->child_end() ; i!=e ; ++i)
+	{
+		collect_names_recursive(*i, path);
+	}
+	path.pop_back();
+	// Now we collect the phandles and properties that reference
+	// other nodes.
+	for (node::property_iterator i=n->property_begin(), e=n->property_end() ; i!=e ; ++i)
+	{
+		for (property::value_iterator p=(*i)->begin(),pe=(*i)->end() ; p!=pe ; ++p)
+		{
+			if (p->is_phandle())
+			{
+				phandles.push_back(&*p);
+			}
+			if (p->is_cross_reference())
+			{
+				cross_references.push_back(&*p);
+			}
+		}
+		if ((*i)->get_key() == string("phandle") ||
+		    (*i)->get_key() == string("linux,phandle"))
+		{
+			if ((*i)->begin()->byte_data.size() != 4)
+			{
+				fprintf(stderr, "Invalid phandle value for node ");
+				n->name.dump();
+				fprintf(stderr, ".  Should be a 4-byte value.\n");
+				valid = false;
+			}
+			else
+			{
+				uint32_t phandle = (*i)->begin()->get_as_uint32();
+				used_phandles.insert(std::make_pair(phandle, n));
+			}
+		}
+	}
+}
+
+void
+device_tree::collect_names()
+{
+	node_path p;
+	collect_names_recursive(root, p);
+}
+
+void
+device_tree::resolve_cross_references()
+{
+	for (std::vector<property_value*>::iterator i=cross_references.begin(), e=cross_references.end() ; i!=e ; ++i)
+	{
+		property_value* pv = *i;
+		node_path path = node_paths[pv->string_data];
+		// Skip the first name in the path.  It's always "", and implicitly /
+		for (node_path::iterator p=path.begin()+1, pe=path.end() ; p!=pe ; ++p)
+		{
+			pv->byte_data.push_back('/');
+			p->first.push_to_buffer(pv->byte_data);
+			if (!(p->second.empty()))
+			{
+				pv->byte_data.push_back('@');
+				p->second.push_to_buffer(pv->byte_data);
+			}
+		}
+		pv->byte_data.push_back(0);
+	}
+	uint32_t phandle = 1;
+	for (std::vector<property_value*>::iterator i=phandles.begin(), e=phandles.end() ; i!=e ; ++i)
+	{
+		string target_name = (*i)->string_data;
+		node *target = node_names[target_name];
+		if (target == 0)
+		{
+			fprintf(stderr, "Failed to find node with label:");
+			target_name.dump();
+			fprintf(stderr, "\n");
+			valid = 0;
+			return;
+		}
+		// If there is an existing phandle, use it
+		property *p = target->get_property("phandle");
+		if (p == 0)
+		{
+			p = target->get_property("linux,phandle");
+		}
+		if (p == 0)
+		{
+			// Otherwise insert a new phandle node
+			property_value v;
+			while (used_phandles.find(phandle) != used_phandles.end())
+			{
+				// Note that we only don't need to
+				// store this phandle in the set,
+				// because we are monotonically
+				// increasing the value of phandle and
+				// so will only ever revisit this value
+				// if we have used 2^32 phandles, at
+				// which point our blob won't fit in
+				// any 32-bit system and we've done
+				// something badly wrong elsewhere
+				// already.
+				phandle++;
+			}
+			push_big_endian(v.byte_data, phandle++);
+			if (phandle_node_name == BOTH || phandle_node_name == LINUX)
+			{
+				p = new property(string("linux,phandle"));
+				p->add_value(v);
+				target->add_property(p);
+			}
+			if (phandle_node_name == BOTH || phandle_node_name == EPAPR)
+			{
+				p = new property(string("phandle"));
+				p->add_value(v);
+				target->add_property(p);
+			}
+		}
+		p->begin()->push_to_buffer((*i)->byte_data);
+		assert((*i)->byte_data.size() == 4);
+	}
+}
+
+void
+device_tree::parse_roots(input_buffer &input, std::vector<node*> &roots)
+{
+	input.next_token();
+	while (valid && input.consume('/'))
+	{
+		input.next_token();
+		node *n = node::parse(input, string("", 1));
+		if (n)
+		{
+			roots.push_back(n);
+		}
+		else
+		{
+			valid = false;
+		}
+	}
+}
+
+input_buffer*
+device_tree::buffer_for_file(const char *path)
+{
+	if (string(path) == string("-"))
+	{
+		input_buffer *b = new stream_input_buffer();
+		buffers.push_back(b);
+		return b;
+	}
+	int source = open(path, O_RDONLY);
+	if (source == -1)
+	{
+		fprintf(stderr, "Unable to open file %s\n", path);
+		return 0;
+	}
+	input_buffer *b = new mmap_input_buffer(source);
+	// Keep the buffer that owns the memory around for the lifetime
+	// of this FDT.  Ones simply referring to it may have shorter
+	// lifetimes.
+	buffers.push_back(b);
+	close(source);
+	return b;
+}
+
+template<class writer> void
+device_tree::write(int fd)
+{
+	dtb::string_table st;
+	dtb::header head;
+	writer head_writer;
+	writer reservation_writer;
+	writer struct_writer;
+	writer strings_writer;
+
+	// Build the reservation table
+	reservation_writer.write_comment(string("Memory reservations"));
+	reservation_writer.write_label(string("dt_reserve_map"));
+	for (std::vector<reservation>::iterator i=reservations.begin(),
+	     e=reservations.end() ; i!=e ; ++i)
+	{
+		reservation_writer.write_comment(string("Reservation start"));
+		reservation_writer.write_data(i->first);
+		reservation_writer.write_comment(string("Reservation length"));
+		reservation_writer.write_data(i->first);
+	}
+	// Write n spare reserve map entries, plus the trailing 0.
+	for (uint32_t i=0 ; i<=spare_reserve_map_entries ; i++)
+	{
+		reservation_writer.write_data((uint64_t)0);
+		reservation_writer.write_data((uint64_t)0);
+	}
+
+
+	struct_writer.write_comment(string("Device tree"));
+	struct_writer.write_label(string("dt_struct_start"));
+	root->write(struct_writer, st);
+	struct_writer.write_token(dtb::FDT_END);
+	struct_writer.write_label(string("dt_struct_end"));
+
+	st.write(strings_writer);
+	// Find the strings size before we stick padding on the end.
+	// Note: We should possibly use a new writer for the padding.
+	head.size_dt_strings = strings_writer.size();
+
+	// Stick the padding in the strings writer, but after the
+	// marker indicating that it's the end.
+	// Note: We probably should add a padding call to the writer so
+	// that the asm back end can write padding directives instead
+	// of a load of 0 bytes.
+	for (uint32_t i=0 ; i<blob_padding ; i++)
+	{
+		strings_writer.write_data((uint8_t)0);
+	}
+	head.totalsize = sizeof(head) + strings_writer.size() +
+		struct_writer.size() + reservation_writer.size();
+	while (head.totalsize < minimum_blob_size)
+	{
+		head.totalsize++;
+		strings_writer.write_data((uint8_t)0);
+	}
+	head.off_dt_struct = sizeof(head) + reservation_writer.size();;
+	head.off_dt_strings = head.off_dt_struct + struct_writer.size();
+	head.off_mem_rsvmap = sizeof(head);
+	head.boot_cpuid_phys = boot_cpu;
+	head.size_dt_struct = struct_writer.size();
+	head.write(head_writer);
+
+	head_writer.write_to_file(fd);
+	reservation_writer.write_to_file(fd);
+	struct_writer.write_to_file(fd);
+	strings_writer.write_label(string("dt_blob_end"));
+	strings_writer.write_to_file(fd);
+}
+
+node*
+device_tree::referenced_node(property_value &v)
+{
+	if (v.is_phandle())
+	{
+		return node_names[v.string_data];
+	}
+	if (v.is_binary())
+	{
+		return used_phandles[v.get_as_uint32()];
+	}
+	return 0;
+}
+
+void
+device_tree::write_binary(int fd)
+{
+	write<dtb::binary_writer>(fd);
+}
+
+void
+device_tree::write_asm(int fd)
+{
+	write<dtb::asm_writer>(fd);
+}
+
+void
+device_tree::write_dts(int fd)
+{
+	FILE *file = fdopen(fd, "w");
+	fputs("/dtc-v1/;\n\n", file);
+
+	if (!reservations.empty())
+	{
+		const char msg[] = "/memreserve/";
+		fwrite(msg, sizeof(msg), 1, file);
+		for (std::vector<reservation>::iterator i=reservations.begin(),
+		     e=reservations.end() ; i!=e ; ++i)
+		{
+			fprintf(stderr, " %" PRIx64 " %" PRIx64, i->first, i->second);
+		}
+		fputs(";\n\n", file);
+	}
+	putc('/', file);
+	putc(' ', file);
+	root->write_dts(file, 0);
+	fclose(file);
+}
+
+void
+device_tree::parse_dtb(const char *fn, FILE *depfile)
+{
+	input_buffer *in = buffer_for_file(fn);
+	if (in == 0)
+	{
+		valid = false;
+		return;
+	}
+	input_buffer &input = *in;
+	dtb::header h;
+	valid = h.read_dtb(input);
+	boot_cpu = h.boot_cpuid_phys;
+	if (h.last_comp_version > 17)
+	{
+		fprintf(stderr, "Don't know how to read this version of the device tree blob");
+		valid = false;
+	}
+	if (!valid)
+	{
+		return;
+	}
+	input_buffer reservation_map =
+		input.buffer_from_offset(h.off_mem_rsvmap, 0);
+	uint64_t start, length;
+	do
+	{
+		if (!(reservation_map.consume_binary(start) &&
+		      reservation_map.consume_binary(length)))
+		{
+			fprintf(stderr, "Failed to read memory reservation table\n");
+			valid = false;
+			return;
+		}
+	} while (!((start == 0) && (length == 0)));
+	input_buffer struct_table =
+		input.buffer_from_offset(h.off_dt_struct, h.size_dt_struct);
+	input_buffer strings_table =
+		input.buffer_from_offset(h.off_dt_strings, h.size_dt_strings);
+	uint32_t token;
+	if (!(struct_table.consume_binary(token) &&
+		(token == dtb::FDT_BEGIN_NODE)))
+	{
+		fprintf(stderr, "Expected FDT_BEGIN_NODE token.\n");
+		valid = false;
+		return;
+	}
+	root = node::parse_dtb(struct_table, strings_table);
+	if (!(struct_table.consume_binary(token) && (token == dtb::FDT_END)))
+	{
+		fprintf(stderr, "Expected FDT_END token after parsing root node.\n");
+		valid = false;
+		return;
+	}
+	valid = (root != 0);
+}
+
+void
+device_tree::parse_dts(const char *fn, FILE *depfile)
+{
+	input_buffer *in = buffer_for_file(fn);
+	if (in == 0)
+	{
+		valid = false;
+		return;
+	}
+	std::vector<node*> roots;
+	input_buffer &input = *in;
+	input.next_token();
+	bool read_header = false;
+	// Read the header
+	if (input.consume("/dts-v1/;"))
+	{
+		read_header = true;
+	}
+	input.next_token();
+	while(input.consume("/include/"))
+	{
+		input.next_token();
+		if (!input.consume('"'))
+		{
+			input.parse_error("Expected quoted filename");
+			valid = false;
+			return;
+		}
+		int length = 0;
+		while (input[length] != '"') length++;
+
+		const char *file = (const char*)input;
+		const char *dir = dirname(fn);
+		int dir_length = strlen(dir);
+		char *include_file = (char*)malloc(strlen(dir) + length + 2);
+		memcpy(include_file, dir, dir_length);
+		include_file[dir_length] = '/';
+		memcpy(include_file+dir_length+1, file, length);
+		include_file[dir_length+length+1] = 0;
+		input_buffer *include_buffer = buffer_for_file(include_file);
+
+		if (include_buffer == 0)
+		{
+			for (std::vector<const char*>::iterator i=include_paths.begin(), e=include_paths.end() ; e!=i ; ++i)
+			{
+				free(include_file);
+				dir = *i;
+				dir_length = strlen(dir);
+				include_file = (char*)malloc(strlen(dir) +
+						length + 2);
+				memcpy(include_file, dir, dir_length);
+				include_file[dir_length] = '/';
+				memcpy(include_file+dir_length+1, file, length);
+				include_file[dir_length+length+1] = 0;
+				include_buffer = buffer_for_file(include_file);
+				if (include_buffer != 0)
+				{
+					break;
+				}
+			}
+		}
+		if (depfile != 0)
+		{
+			putc(' ', depfile);
+			fputs(include_file, depfile);
+		}
+		if (include_buffer == 0)
+		{
+			valid = false;
+			return;
+		}
+		input_buffer &include = *include_buffer;
+		input.consume(include_file+dir_length+1);
+		input.consume('"');
+		free((void*)include_file);
+
+		if (!read_header)
+		{
+			include.next_token();
+			read_header = include.consume("/dts-v1/;");
+		}
+		parse_roots(include, roots);
+	}
+	input.next_token();
+	if (!read_header)
+	{
+		input.parse_error("Expected /dts-v1/; version string");
+	}
+	// Read any memory reservations
+	while(input.consume("/memreserve/"))
+	{
+		long long start, len;
+		input.next_token();
+		// Read the start and length.
+		if (!(input.consume_integer(start) &&
+		    (input.next_token(),
+		    input.consume_integer(len))))
+		{
+			input.parse_error("Expected /dts-v1/; version string");
+		}
+		input.next_token();
+		input.consume(';');
+		reservations.push_back(reservation(start, len));
+	}
+	parse_roots(input, roots);
+	switch (roots.size())
+	{
+		case 0:
+			valid = false;
+			input.parse_error("Failed to find root node /.");
+			return;
+		case 1:
+			root = roots[0];
+			break;
+		default:
+		{
+			root = roots[0];
+			for (std::vector<node*>::iterator i=roots.begin()+1,
+			     e=roots.end() ; i!=e ; ++i)
+			{
+				root->merge_node(*i);
+				delete *i;
+			}
+			roots.resize(1);
+		}
+	}
+	collect_names();
+	resolve_cross_references();
+}
+
+device_tree::~device_tree()
+{
+	if (root != 0)
+	{
+		delete root;
+	}
+	while (!buffers.empty())
+	{
+		delete buffers.back();
+		buffers.pop_back();
+	}
+}
+
+} // namespace fdt
+
+} // namespace dtc
+
diff --git a/usr.bin/dtc/fdt.hh b/usr.bin/dtc/fdt.hh
new file mode 100644
index 0000000..b00ea48
--- /dev/null
+++ b/usr.bin/dtc/fdt.hh
@@ -0,0 +1,782 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _FDT_HH_
+#define _FDT_HH_
+#include <map>
+
+#include "util.hh"
+#include "string.hh"
+
+namespace dtc
+{
+
+namespace dtb 
+{
+struct output_writer;
+class string_table;
+}
+
+namespace fdt
+{
+/**
+ * Properties may contain a number of different value, each with a different
+ * label.  This class encapsulates a single value.
+ */
+struct property_value
+{
+	/**
+	 * The label for this data.  This is usually empty.
+	 */
+	string label;
+	/**
+	 * If this value is a string, or something resolved from a string (a
+	 * reference) then this contains the source string.
+	 */
+	string string_data;
+	/**
+	 * The data that should be written to the final output.
+	 */
+	byte_buffer byte_data;
+	/**
+	 * Enumeration describing the possible types of a value.  Note that
+	 * property-coded arrays will appear simply as binary (or possibly
+	 * string, if they happen to be nul-terminated and printable), and must
+	 * be checked separately.
+	 */
+	enum value_type
+	{
+		/**
+		 * This is a list of strings.  When read from source, string
+		 * lists become one property value for each string, however
+		 * when read from binary we have a single property value
+		 * incorporating the entire text, with nul bytes separating the
+		 * strings.
+		 */
+		STRING_LIST,
+		/**
+		 * This property contains a single string.
+		 */
+		STRING,
+		/**
+		 * This is a binary value.  Check the size of byte_data to
+		 * determine how many bytes this contains.
+		 */
+		BINARY,
+		/** This contains a short-form address that should be replaced
+		 * by a fully-qualified version.  This will only appear when
+		 * the input is a device tree source.  When parsed from a
+		 * device tree blob, the cross reference will have already been
+		 * resolved and the property value will be a string containing
+		 * the full path of the target node.  */
+		CROSS_REFERENCE,
+		/**
+		 * This is a phandle reference.  When parsed from source, the
+		 * string_data will contain the node label for the target and,
+		 * after cross references have been resolved, the binary data
+		 * will contain a 32-bit integer that should match the phandle
+		 * property of the target node.
+		 */
+		PHANDLE,
+		/**
+		 * An empty property value.  This will never appear on a real
+		 * property value, it is used by checkers to indicate that no
+		 * property values should exist for a property.
+		 */
+		EMPTY,
+		/**
+		 * The type of this property has not yet been determined.
+		 */
+		UNKNOWN
+	};
+	/**
+	 * The type of this property.
+	 */
+	value_type type;
+	/**
+	 * Returns true if this value is a cross reference, false otherwise.
+	 */
+	inline bool is_cross_reference()
+	{
+		return is_type(CROSS_REFERENCE);
+	}
+	/**
+	 * Returns true if this value is a phandle reference, false otherwise.
+	 */
+	inline bool is_phandle()
+	{
+		return is_type(PHANDLE);
+	}
+	/**
+	 * Returns true if this value is a string, false otherwise.
+	 */
+	inline bool is_string()
+	{
+		return is_type(STRING);
+	}
+	/**
+	 * Returns true if this value is a string list (a nul-separated
+	 * sequence of strings), false otherwise.
+	 */
+	inline bool is_string_list()
+	{
+		return is_type(STRING_LIST);
+	}
+	/**
+	 * Returns true if this value is binary, false otherwise.
+	 */
+	inline bool is_binary()
+	{
+		return is_type(BINARY);
+	}
+	/**
+	 * Returns this property value as a 32-bit integer.  Returns 0 if this
+	 * property value is not 32 bits long.  The bytes in the property value
+	 * are assumed to be in big-endian format, but the return value is in
+	 * the host native endian.
+	 */
+	uint32_t get_as_uint32();
+	/**
+	 * Default constructor, specifying the label of the value.
+	 */
+	property_value(string l=string()) : label(l), type(UNKNOWN) {}
+	/**
+	 * Writes the data for this value into an output buffer.
+	 */
+	void push_to_buffer(byte_buffer &buffer);
+
+	/**
+	 * Writes the property value to the standard output.  This uses the
+	 * following heuristics for deciding how to print the output:
+	 *
+	 * - If the value is nul-terminated and only contains printable
+	 *   characters, it is written as a string.
+	 * - If it is a multiple of 4 bytes long, then it is printed as cells.
+	 * - Otherwise, it is printed as a byte buffer.
+	 */
+	void write_dts(FILE *file);
+	private:
+	/**
+	 * Returns whether the value is of the specified type.  If the type of
+	 * the value has not yet been determined, then this calculates it.
+	 */
+	inline bool is_type(value_type v)
+	{
+		if (type == UNKNOWN)
+		{
+			resolve_type();
+		}
+		return type == v;
+	}
+	/**
+	 * Determines the type of the value based on its contents.
+	 */
+	void resolve_type();
+	/**
+	 * Writes the property value to the specified file as a quoted string.
+	 * This is used when generating DTS.
+	 */
+	void write_as_string(FILE *file);
+	/**
+	 * Writes the property value to the specified file as a sequence of
+	 * 32-bit big-endian cells.  This is used when generating DTS.
+	 */
+	void write_as_cells(FILE *file);
+	/**
+	 * Writes the property value to the specified file as a sequence of
+	 * bytes.  This is used when generating DTS.
+	 */
+	void write_as_bytes(FILE *file);
+};
+
+/**
+ * A value encapsulating a single property.  This contains a key, optionally a
+ * label, and optionally one or more values.
+ */
+class property
+{
+	/**
+	 * The name of this property.
+	 */
+	string key;
+	/**
+	 * An optional label.
+	 */
+	string label;
+	/**
+	 * The values in this property.
+	 */
+	std::vector<property_value> values;
+	/**
+	 * Value indicating that this is a valid property.  If a parse error
+	 * occurs, then this value is false.
+	 */
+	bool valid;
+	/**
+	 * Parses a string property value, i.e. a value enclosed in double quotes.
+	 */
+	void parse_string(input_buffer &input);
+	/**
+	 * Parses one or more 32-bit values enclosed in angle brackets.
+	 */
+	void parse_cells(input_buffer &input);
+	/**
+	 * Parses an array of bytes, contained within square brackets.
+	 */
+	void parse_bytes(input_buffer &input);
+	/**
+	 * Parses a reference.  This is a node label preceded by an ampersand
+	 * symbol, which should expand to the full path to that node.
+	 *
+	 * Note: The specification says that the target of such a reference is
+	 * a node name, however dtc assumes that it is a label, and so we
+	 * follow their interpretation for compatibility.
+	 */
+	void parse_reference(input_buffer &input);
+	/**
+	 * Constructs a new property from two input buffers, pointing to the
+	 * struct and strings tables in the device tree blob, respectively.
+	 * The structs input buffer is assumed to have just consumed the
+	 * FDT_PROP token.
+	 */
+	property(input_buffer &structs, input_buffer &strings);
+	/**
+	 * Parses a new property from the input buffer.  
+	 */
+	property(input_buffer &input, string k, string l);
+	public:
+	/**
+	 * Creates an empty property.
+	 */
+	property(string k, string l=string()) : key(k), label(l), valid(true)
+	{}
+	/**
+	 * Copy constructor.
+	 */
+	property(property &p) : key(p.key), label(p.label), values(p.values),
+		valid(p.valid) {}
+	/**
+	 * Factory method for constructing a new property.  Attempts to parse a
+	 * property from the input, and returns it on success.  On any parse
+	 * error, this will return 0.
+	 */
+	static property* parse_dtb(input_buffer &structs,
+	                           input_buffer &strings);
+	/**
+	 * Factory method for constructing a new property.  Attempts to parse a
+	 * property from the input, and returns it on success.  On any parse
+	 * error, this will return 0.
+	 */
+	static property* parse(input_buffer &input,
+	                       string key,
+	                       string label=string());
+	/**
+	 * Iterator type used for accessing the values of a property.
+	 */
+	typedef std::vector<property_value>::iterator value_iterator;
+	/**
+	 * Returns an iterator referring to the first value in this property.
+	 */
+	inline value_iterator begin()
+	{
+		return values.begin();
+	}
+	/**
+	 * Returns an iterator referring to the last value in this property.
+	 */
+	inline value_iterator end()
+	{
+		return values.end();
+	}
+	/**
+	 * Adds a new value to an existing property.
+	 */
+	inline void add_value(property_value v)
+	{
+		values.push_back(v);
+	}
+	/**
+	 * Returns the key for this property.
+	 */
+	inline string get_key()
+	{
+		return key;
+	}
+	/**
+	 * Writes the property to the specified writer.  The property name is a
+	 * reference into the strings table.
+	 */
+	void write(dtb::output_writer &writer, dtb::string_table &strings);
+	/**
+	 * Writes in DTS format to the specified file, at the given indent
+	 * level.  This will begin the line with the number of tabs specified
+	 * as the indent level and then write the property in the most
+	 * applicable way that it can determine.
+	 */
+	void write_dts(FILE *file, int indent);
+};
+
+/**
+ * Class encapsulating a device tree node.  Nodes may contain properties and
+ * other nodes.
+ */
+class node
+{
+	public:
+	/**
+	 * The label for this node, if any.  Node labels are used as the
+	 * targets for cross references.
+	 */
+	string label;
+	/**
+	 * The name of the node.
+	 */
+	string name;
+	/**
+	 * The unit address of the node, which is optionally written after the
+	 * name followed by an at symbol.
+	 */
+	string unit_address;
+	private:
+	/**
+	 * The properties contained within this node.
+	 */
+	std::vector<property*> properties;
+	/**
+	 * The children of this node.
+	 */
+	std::vector<node*> children;
+	/**
+	 * A flag indicating whether this node is valid.  This is set to false
+	 * if an error occurs during parsing.
+	 */
+	bool valid;
+	/**
+	 * Parses a name inside a node, writing the string passed as the last
+	 * argument as an error if it fails.  
+	 */
+	string parse_name(input_buffer &input,
+	                  bool &is_property,
+	                  const char *error);
+	/**
+	 * Constructs a new node from two input buffers, pointing to the struct
+	 * and strings tables in the device tree blob, respectively.
+	 */
+	node(input_buffer &structs, input_buffer &strings);
+	/**
+	 * Parses a new node from the specified input buffer.  This is called
+	 * when the input cursor is on the open brace for the start of the
+	 * node.  The name, and optionally label and unit address, should have
+	 * already been parsed.
+	 */
+	node(input_buffer &input, string n, string l, string a);
+	/**
+	 * Comparison function for properties, used when sorting the properties
+	 * vector.  Orders the properties based on their names.
+	 */
+	static inline bool cmp_properties(property *p1, property *p2);
+		/*
+	{
+		return p1->get_key() < p2->get_key();
+	}
+	*/
+	/**
+	 * Comparison function for nodes, used when sorting the children
+	 * vector.  Orders the nodes based on their names or, if the names are
+	 * the same, by the unit addresses.
+	 */
+	static inline bool cmp_children(node *c1, node *c2);
+		/*
+	{
+		if (c1->name == c2->name)
+		{
+			return c1->unit_address < c2->unit_address;
+		}
+		return c1->name < c2->name;
+	}
+	*/
+	public:
+	/**
+	 * Sorts the node's properties and children into alphabetical order and
+	 * recursively sorts the children.
+	 */
+	void sort();
+	/**
+	 * Iterator type for child nodes.
+	 */
+	typedef std::vector<node*>::iterator child_iterator;
+	/**
+	 * Returns an iterator for the first child of this node.
+	 */
+	inline child_iterator child_begin()
+	{
+		return children.begin();
+	}
+	/**
+	 * Returns an iterator after the last child of this node.
+	 */
+	inline child_iterator child_end()
+	{
+		return children.end();
+	}
+	/**
+	 * Iterator type for properties of a node.
+	 */
+	typedef std::vector<property*>::iterator property_iterator;
+	/**
+	 * Returns an iterator after the last property of this node.
+	 */
+	inline property_iterator property_begin()
+	{
+		return properties.begin();
+	}
+	/**
+	 * Returns an iterator for the first property of this node.
+	 */
+	inline property_iterator property_end()
+	{
+		return properties.end();
+	}
+	/**
+	 * Factory method for constructing a new node.  Attempts to parse a
+	 * node in DTS format from the input, and returns it on success.  On
+	 * any parse error, this will return 0.  This should be called with the
+	 * cursor on the open brace of the property, after the name and so on
+	 * have been parsed.
+	 */
+	static node* parse(input_buffer &input,
+	                   string name,
+	                   string label=string(),
+	                   string address=string());
+	/**
+	 * Factory method for constructing a new node.  Attempts to parse a
+	 * node in DTB format from the input, and returns it on success.  On
+	 * any parse error, this will return 0.  This should be called with the
+	 * cursor on the open brace of the property, after the name and so on
+	 * have been parsed.
+	 */
+	static node* parse_dtb(input_buffer &structs, input_buffer &strings);
+	/**
+	 * Destroys the node, recursively deleting all of its properties and
+	 * children.
+	 */
+	~node();
+	/**
+	 * Returns a property corresponding to the specified key, or 0 if this
+	 * node does not contain a property of that name.
+	 */
+	property *get_property(string key);
+	/**
+	 * Adds a new property to this node.
+	 */
+	inline void add_property(property *p)
+	{
+		properties.push_back(p);
+	}
+	/**
+	 * Merges a node into this one.  Any properties present in both are
+	 * overridden, any properties present in only one are preserved.
+	 */
+	void merge_node(node *other);
+	/**
+	 * Write this node to the specified output.  Although nodes do not
+	 * refer to a string table directly, their properties do.  The string
+	 * table passed as the second argument is used for the names of
+	 * properties within this node and its children.
+	 */
+	void write(dtb::output_writer &writer, dtb::string_table &strings);
+	/**
+	 * Writes the current node as DTS to the specified file.  The second
+	 * parameter is the indent level.  This function will start every line
+	 * with this number of tabs.  
+	 */
+	void write_dts(FILE *file, int indent);
+};
+
+/**
+ * Class encapsulating the entire parsed FDT.  This is the top-level class,
+ * which parses the entire DTS representation and write out the finished
+ * version.
+ */
+class device_tree
+{
+	public:
+	/**
+	 * Type used for node paths.  A node path is sequence of names and unit
+	 * addresses.
+	 */
+	typedef std::vector<std::pair<string,string> > node_path;
+	/**
+	 * Name that we should use for phandle nodes.
+	 */
+	enum phandle_format
+	{
+		/** linux,phandle */
+		LINUX,
+		/** phandle */
+		EPAPR,
+		/** Create both nodes. */
+		BOTH
+	};
+	private:
+	/**
+	 * The format that we should use for writing phandles.
+	 */
+	phandle_format phandle_node_name;
+	/**
+	 * Flag indicating that this tree is valid.  This will be set to false
+	 * on parse errors. 
+	 */
+	bool valid;
+	/**
+	 * Type used for memory reservations.  A reservation is two 64-bit
+	 * values indicating a base address and length in memory that the
+	 * kernel should not use.  The high 32 bits are ignored on 32-bit
+	 * platforms.
+	 */
+	typedef std::pair<uint64_t, uint64_t> reservation;
+	/**
+	 * The memory reserves table.
+	 */
+	std::vector<reservation> reservations;
+	/**
+	 * Root node.  All other nodes are children of this node.
+	 */
+	node *root;
+	/**
+	 * Mapping from names to nodes.  Only unambiguous names are recorded,
+	 * duplicate names are stored as (node*)-1.
+	 */
+	std::map<string, node*> node_names;
+	/**
+	 * A map from labels to node paths.  When resolving cross references,
+	 * we look up referenced nodes in this and replace the cross reference
+	 * with the full path to its target.
+	 */
+	std::map<string, node_path> node_paths;
+	/**
+	 * A collection of property values that are references to other nodes.
+	 * These should be expanded to the full path of their targets.
+	 */
+	std::vector<property_value*> cross_references;
+	/**
+	 * A collection of property values that refer to phandles.  These will
+	 * be replaced by the value of the phandle property in their
+	 * destination.
+	 */
+	std::vector<property_value*> phandles;
+	/**
+	 * A collection of input buffers that we are using.  These input
+	 * buffers are the ones that own their memory, and so we must preserve
+	 * them for the lifetime of the device tree.  
+	 */
+	std::vector<input_buffer*> buffers;
+	/**
+	 * A map of used phandle values to nodes.  All phandles must be unique,
+	 * so we keep a set of ones that the user explicitly provides in the
+	 * input to ensure that we don't reuse them.
+	 *
+	 * This is a map, rather than a set, because we also want to be able to
+	 * find phandles that were provided by the user explicitly when we are
+	 * doing checking.
+	 */
+	std::map<uint32_t, node*> used_phandles;
+	/**
+	 * Paths to search for include files.  This contains a set of
+	 * nul-terminated strings, which are not owned by this class and so
+	 * must be freed separately.
+	 */
+	std::vector<const char*> include_paths;
+	/**
+	 * The default boot CPU, specified in the device tree header.
+	 */
+	uint32_t boot_cpu;
+	/**
+	 * The number of empty reserve map entries to generate in the blob.
+	 */
+	uint32_t spare_reserve_map_entries;
+	/**
+	 * The minimum size in bytes of the blob.
+	 */
+	uint32_t minimum_blob_size;
+	/**
+	 * The number of bytes of padding to add to the end of the blob.
+	 */
+	uint32_t blob_padding;
+	/**
+	 * Visit all of the nodes recursively, and if they have labels then add
+	 * them to the node_paths and node_names vectors so that they can be
+	 * used in resolving cross references.  Also collects phandle
+	 * properties that have been explicitly added.  
+	 */
+	void collect_names_recursive(node* n, node_path &path);
+	/**
+	 * Calls the recursive version of this method on every root node.
+	 */
+	void collect_names();
+	/**
+	 * Resolves all cross references.  Any properties that refer to another
+	 * node must have their values replaced by either the node path or
+	 * phandle value.
+	 */
+	void resolve_cross_references();
+	/**
+	 * Parses root nodes from the top level of a dts file.  
+	 */
+	void parse_roots(input_buffer &input, std::vector<node*> &roots);
+	/**
+	 * Allocates a new mmap()'d input buffer for use in parsing.  This
+	 * object then keeps a reference to it, ensuring that it is not
+	 * deallocated until the device tree is destroyed.
+	 */
+	input_buffer *buffer_for_file(const char *path);
+	/**
+	 * Template function that writes a dtb blob using the specified writer.
+	 * The writer defines the output format (assembly, blob).
+	 */
+	template<class writer>
+	void write(int fd);
+	public:
+	/**
+	 * Returns the node referenced by the property.  If this is a tree that
+	 * is in source form, then we have a string that we can use to index
+	 * the cross_references array and so we can just look that up.  
+	 */
+	node *referenced_node(property_value &v);
+	/**
+	 * Writes this FDT as a DTB to the specified output.
+	 */
+	void write_binary(int fd);
+	/**
+	 * Writes this FDT as an assembly representation of the DTB to the
+	 * specified output.  The result can then be assembled and linked into
+	 * a program.
+	 */
+	void write_asm(int fd);
+	/**
+	 * Writes the tree in DTS (source) format.
+	 */
+	void write_dts(int fd);
+	/**
+	 * Default constructor.  Creates a valid, but empty FDT.
+	 */
+	device_tree() : phandle_node_name(EPAPR), valid(true), root(0),
+		boot_cpu(0), spare_reserve_map_entries(0),
+		minimum_blob_size(0), blob_padding(0) {}
+	/**
+	 * Constructs a device tree from the specified file name, referring to
+	 * a file that contains a device tree blob.
+	 */
+	void parse_dtb(const char *fn, FILE *depfile);
+	/**
+	 * Constructs a device tree from the specified file name, referring to
+	 * a file that contains device tree source.
+	 */
+	void parse_dts(const char *fn, FILE *depfile);
+	/**
+	 * Destroy the tree and any input buffers that it holds.
+	 */
+	~device_tree();
+	/**
+	 * Returns whether this tree is valid.
+	 */
+	inline bool is_valid()
+	{
+		return valid;
+	}
+	/**
+	 * Sets the format for writing phandle properties.
+	 */
+	inline void set_phandle_format(phandle_format f)
+	{
+		phandle_node_name = f;
+	}
+	/**
+	 * Returns a pointer to the root node of this tree.  No ownership
+	 * transfer.
+	 */
+	inline node *get_root() const
+	{
+		return root;
+	}
+	/**
+	 * Sets the physical boot CPU.
+	 */
+	void set_boot_cpu(uint32_t cpu)
+	{
+		boot_cpu = cpu;
+	}
+	/**
+	 * Sorts the tree.  Useful for debugging device trees.
+	 */
+	void sort()
+	{
+		root->sort();
+	}
+	/**
+	 * Adds a path to search for include files.  The argument must be a
+	 * nul-terminated string representing the path.  The device tree keeps
+	 * a pointer to this string, but does not own it: the caller is
+	 * responsible for freeing it if required.
+	 */
+	void add_include_path(const char *path)
+	{
+		include_paths.push_back(path);
+	}
+	/**
+	 * Sets the number of empty reserve map entries to add.
+	 */
+	void set_empty_reserve_map_entries(uint32_t e)
+	{
+		spare_reserve_map_entries = e;
+	}
+	/**
+	 * Sets the minimum size, in bytes, of the blob.
+	 */
+	void set_blob_minimum_size(uint32_t s)
+	{
+		minimum_blob_size = s;
+	}
+	/**
+	 * Sets the amount of padding to add to the blob.
+	 */
+	void set_blob_padding(uint32_t p)
+	{
+		blob_padding = p;
+	}
+};
+
+} // namespace fdt
+
+} // namespace dtc
+
+#endif // !_FDT_HH_
diff --git a/usr.bin/dtc/input_buffer.cc b/usr.bin/dtc/input_buffer.cc
new file mode 100644
index 0000000..cd08dd3
--- /dev/null
+++ b/usr.bin/dtc/input_buffer.cc
@@ -0,0 +1,258 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#include "input_buffer.hh"
+#include <string.h>
+#include <stdint.h>
+
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <assert.h>
+
+namespace dtc
+{
+
+void
+input_buffer::skip_spaces()
+{
+	if (cursor >= size) { return; }
+	if (cursor < 0) { return; }
+	char c = buffer[cursor];
+	while ((c == ' ') || (c == '\t') || (c == '\n') || (c == '\f')
+	       || (c == '\v') || (c == '\r'))
+	{
+		cursor++;
+		if (cursor > size)
+		{
+			c = '\0';
+		}
+		else
+		{
+			c = buffer[cursor];
+		}
+	}
+}
+
+input_buffer
+input_buffer::buffer_from_offset(int offset, int s)
+{
+	if (s == 0)
+	{
+		s = size - offset;
+	}
+	if (offset > size)
+	{
+		return input_buffer();
+	}
+	if (s > (size-offset))
+	{
+		return input_buffer();
+	}
+	return input_buffer(&buffer[offset], s);
+}
+
+bool
+input_buffer::consume(const char *str)
+{
+	int len = strlen(str);
+	if (len > size - cursor)
+	{
+		return false;
+	}
+	else
+	{
+		for (int i=0 ; i<len ; ++i)
+		{
+			if (str[i] != buffer[cursor + i])
+			{
+				return false;
+			}
+		}
+		cursor += len;
+		return true;
+	}
+	return false;
+}
+
+bool
+input_buffer::consume_integer(long long &outInt)
+{
+	// The first character must be a digit.  Hex and octal strings
+	// are prefixed by 0 and 0x, respectively.
+	if (!isdigit((*this)[0]))
+	{
+		return false;
+	}
+	char *end=0;
+	outInt = strtoll(&buffer[cursor], &end, 0);
+	if (end == &buffer[cursor])
+	{
+		return false;
+	}
+	cursor = end - buffer;
+	return true;
+}
+
+bool
+input_buffer::consume_hex_byte(uint8_t &outByte)
+{
+	if (!ishexdigit((*this)[0]) && !ishexdigit((*this)[1]))
+	{
+		return false;
+	}
+	outByte = (digittoint((*this)[0]) << 4) | digittoint((*this)[1]);
+	cursor += 2;
+	return true;
+}
+
+input_buffer&
+input_buffer::next_token()
+{
+	int start;
+	do {
+		start = cursor;
+		skip_spaces();
+		// Parse /* comments
+		if (((*this)[0] == '/') && ((*this)[1] == '*'))
+		{
+			// eat the start of the comment
+			++(*this);
+			++(*this);
+			do {
+				// Find the ending * of */
+				while ((**this != '\0') && (**this != '*'))
+				{
+					++(*this);
+				}
+				// Eat the *
+				++(*this);
+			} while ((**this != '\0') && (**this != '/'));
+			// Eat the /
+			++(*this);
+		}
+		// Parse // comments
+		if (((*this)[0] == '/') && ((*this)[1] == '/'))
+		{
+			// eat the start of the comment
+			++(*this);
+			++(*this);
+			// Find the ending * of */
+			while (**this != '\n')
+			{
+				++(*this);
+			}
+			// Eat the \n
+			++(*this);
+		}
+	} while (start != cursor);
+	return *this;
+}
+
+void
+input_buffer::parse_error(const char *msg)
+{
+	int line_count = 1;
+	int line_start = 0;
+	int line_end = cursor;
+	for (int i=cursor ; i>0 ; --i)
+	{
+		if (buffer[i] == '\n')
+		{
+			line_count++;
+			if (line_start == 0)
+			{
+				line_start = i+1;
+			}
+		}
+	}
+	for (int i=cursor+1 ; i<size ; ++i)
+	{
+		if (buffer[i] == '\n')
+		{
+			line_end = i;
+			break;
+		}
+	}
+	fprintf(stderr, "Error on line %d: %s\n", line_count, msg);
+	fwrite(&buffer[line_start], line_end-line_start, 1, stderr);
+	putc('\n', stderr);
+	for (int i=0 ; i<(cursor-line_start) ; ++i)
+	{
+		putc(' ', stderr);
+	}
+	putc('^', stderr);
+	putc('\n', stderr);
+}
+void
+input_buffer::dump()
+{
+	fprintf(stderr, "Current cursor: %d\n", cursor);
+	fwrite(&buffer[cursor], size-cursor, 1, stderr);
+}
+
+mmap_input_buffer::mmap_input_buffer(int fd) : input_buffer(0, 0)
+{
+	struct stat sb;
+	if (fstat(fd, &sb))
+	{
+		perror("Failed to stat file");
+	}
+	size = sb.st_size;
+	buffer = (const char*)mmap(0, size, PROT_READ,
+		MAP_PREFAULT_READ, fd, 0);
+	if (buffer == 0)
+	{
+		perror("Failed to mmap file");
+	}
+}
+
+mmap_input_buffer::~mmap_input_buffer()
+{
+	if (buffer != 0)
+	{
+		munmap((void*)buffer, size);
+	}
+}
+
+stream_input_buffer::stream_input_buffer() : input_buffer(0, 0)
+{
+	int c;
+	while ((c = fgetc(stdin)) != EOF)
+	{
+		b.push_back(c);
+	}
+	buffer = b.data();
+	size = b.size();
+}
+
+} // namespace dtc
+
diff --git a/usr.bin/dtc/input_buffer.hh b/usr.bin/dtc/input_buffer.hh
new file mode 100644
index 0000000..9a38312
--- /dev/null
+++ b/usr.bin/dtc/input_buffer.hh
@@ -0,0 +1,289 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _INPUT_BUFFER_HH_
+#define _INPUT_BUFFER_HH_
+#include "util.hh"
+#include <assert.h>
+
+namespace dtc
+{
+
+/**
+ * Class encapsulating the input file.  Can be used as a const char*, but has
+ * range checking.  Attempting to access anything out of range will return a 0
+ * byte.  The input buffer can be cheaply copied, without copying the
+ * underlying memory, however it is the user's responsibility to ensure that
+ * such copies do not persist beyond the lifetime of the underlying memory.
+ *
+ * This also contains methods for reporting errors and for consuming the token
+ * stream.
+ */
+class input_buffer
+{
+	protected:
+	/**
+	 * The buffer.  This class doesn't own the buffer, but the
+	 * mmap_input_buffer subclass does.
+	 */
+	const char* buffer;
+	/**
+	 * The size of the buffer.
+	 */
+	int size;
+	private:
+	/**
+	 * The current place in the buffer where we are reading.  This class
+	 * keeps a separate size, pointer, and cursor so that we can move
+	 * forwards and backwards and still have checks that we haven't fallen
+	 * off either end.
+	 */
+	int cursor;
+	/**
+	 * Private constructor.  This is used to create input buffers that
+	 * refer to the same memory, but have different cursors.
+	 */
+	input_buffer(const char* b, int s, int c) : buffer(b), size(s),
+		cursor(c) {}
+	/**
+	 * Reads forward past any spaces.  The DTS format is not whitespace
+	 * sensitive and so we want to scan past whitespace when reading it.
+	 */
+	void skip_spaces();
+	public:
+	/**
+	 * Virtual destructor.  Does nothing, but exists so that subclasses
+	 * that own the memory can run cleanup code for deallocating it.
+	 */
+	virtual ~input_buffer() {};
+	/**
+	 * Constructs an empty buffer.
+	 */
+	input_buffer() : buffer(0), size(0), cursor(0) {}
+	/**
+	 * Constructs a new buffer with a specified memory region and size.
+	 */
+	input_buffer(const char* b, int s) : buffer(b), size(s), cursor(0){}
+	/**
+	 * Returns a new input buffer referring into this input, clamped to the
+	 * specified size.  If the requested buffer would fall outside the
+	 * range of this one, then it returns an empty buffer.
+	 *
+	 * The returned buffer shares the same underlying storage as the
+	 * original.  This is intended to be used for splitting up the various
+	 * sections of a device tree blob.  Requesting a size of 0 will give a
+	 * buffer that extends to the end of the available memory.
+	 */
+	input_buffer buffer_from_offset(int offset, int s=0);
+	/**
+	 * Returns true if this buffer has no unconsumed space in it.
+	 */
+	inline bool empty()
+	{
+		return cursor >= size;
+	}
+	/**
+	 * Dereferencing operator, allows the buffer to be treated as a char*
+	 * and dereferenced to give a character.  This returns a null byte if
+	 * the cursor is out of range.
+	 */
+	inline char operator*()
+	{
+		if (cursor >= size) { return '\0'; }
+		if (cursor < 0) { return '\0'; }
+		return buffer[cursor];
+	}
+	/**
+	 * Array subscripting operator, returns a character at the specified
+	 * index offset from the current cursor.  The offset may be negative,
+	 * to reread characters that have already been read.  If the current
+	 * cursor plus offset is outside of the range, this returns a nul
+	 * byte.
+	 */
+	inline char operator[](int offset)
+	{
+		if (cursor + offset >= size) { return '\0'; }
+		if (cursor + offset < 0) { return '\0'; }
+		return buffer[cursor + offset];
+	}
+	/**
+	 * Increments the cursor, iterating forward in the buffer.
+	 */
+	inline input_buffer &operator++()
+	{
+		cursor++; 
+		return *this;
+	}
+	/**
+	 * Cast to char* operator.  Returns a pointer into the buffer that can
+	 * be used for constructing strings.
+	 */
+	inline operator const char*()
+	{
+		if (cursor >= size) { return 0; }
+		if (cursor < 0) { return 0; }
+		return &buffer[cursor];
+	}
+	/**
+	 * Consumes a character.  Moves the cursor one character forward if the
+	 * next character matches the argument, returning true.  If the current
+	 * character does not match the argument, returns false.
+	 */
+	inline bool consume(char c)
+	{
+		if ((*this)[0] == c) 
+		{
+			++(*this);
+			return true;
+		}
+		return false;
+	}
+	/**
+	 * Consumes a string.  If the (null-terminated) string passed as the
+	 * argument appears in the input, advances the cursor to the end and
+	 * returns true.  Returns false if the string does not appear at the
+	 * current point in the input.
+	 */
+	bool consume(const char *str);
+	/**
+	 * Reads an integer in base 8, 10, or 16.  Returns true and advances
+	 * the cursor to the end of the integer if the cursor points to an
+	 * integer, returns false and does not move the cursor otherwise.
+	 *
+	 * The parsed value is returned via the argument.
+	 */
+	bool consume_integer(long long &outInt);
+	/**
+	 * Template function that consumes a binary value in big-endian format
+	 * from the input stream.  Returns true and advances the cursor if
+	 * there is a value of the correct size.  This function assumes that
+	 * all values must be natively aligned, and so advances the cursor to
+	 * the correct alignment before reading.
+	 */
+	template<typename T>
+	bool consume_binary(T &out)
+	{
+		int align = 0;
+		int type_size = sizeof(T);
+		if (cursor % type_size != 0)
+		{
+			align = type_size - (cursor % type_size);
+		}
+		if (size < cursor + align + type_size)
+		{
+			return false;
+		}
+		cursor += align;
+		assert(cursor % type_size == 0);
+		out = 0;
+		for (int i=0 ; i<type_size ; ++i)
+		{
+			out <<= 8;
+			out |= (((T)buffer[cursor++]) & 0xff);
+		}
+		return true;
+	}
+	/**
+	 * Consumes two hex digits and return the resulting byte via the first
+	 * argument.  If the next two characters are hex digits, returns true
+	 * and advances the cursor.  If not, then returns false and leaves the
+	 * cursor in place.
+	 */
+	bool consume_hex_byte(uint8_t &outByte);
+	/**
+	 * Advances the cursor to the start of the next token, skipping
+	 * comments and whitespace.  If the cursor already points to the start
+	 * of a token, then this function does nothing.
+	 */
+	input_buffer &next_token();
+	/**
+	 * Prints a message indicating the location of a parse error.
+	 */
+	void parse_error(const char *msg);
+	/**
+	 * Dumps the current cursor value and the unconsumed values in the
+	 * input buffer to the standard error.  This method is intended solely
+	 * for debugging.
+	 */
+	void dump();
+};
+/**
+ * Explicit specialisation for reading a single byte.
+ */
+template<>
+inline bool input_buffer::consume_binary(uint8_t &out)
+{
+	if (size < cursor + 1)
+	{
+		return false;
+	}
+	out = buffer[cursor++];
+	return true;
+}
+
+/**
+ * Subclass of input_buffer that mmap()s a file and owns the resulting memory.
+ * When this object is destroyed, the memory is unmapped.
+ */
+struct mmap_input_buffer : public input_buffer
+{
+	/**
+	 * Constructs a new buffer from the file passed in as a file
+	 * descriptor.  
+	 */
+	mmap_input_buffer(int fd);
+	/**
+	 * Unmaps the buffer, if one exists.
+	 */
+	virtual ~mmap_input_buffer();
+};
+/**
+ * Input buffer read from standard input.  This is used for reading device tree
+ * blobs and source from standard input.  It reads the entire input into
+ * malloc'd memory, so will be very slow for large inputs.  DTS and DTB files
+ * are very rarely more than 10KB though, so this is probably not a problem.
+ */
+struct stream_input_buffer : public input_buffer
+{
+	/**
+	 * The buffer that will store the data read from the standard input.
+	 */
+	std::vector<char> b;
+	/**
+	 * Constructs a new buffer from the standard input.
+	 */
+	stream_input_buffer();
+};
+
+} // namespace dtc
+
+#endif // !_INPUT_BUFFER_HH_
diff --git a/usr.bin/dtc/string.cc b/usr.bin/dtc/string.cc
new file mode 100644
index 0000000..2f617cc
--- /dev/null
+++ b/usr.bin/dtc/string.cc
@@ -0,0 +1,256 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#include "string.hh"
+
+namespace
+{
+/**
+ * The source files are ASCII, so we provide a non-locale-aware version of
+ * isalpha.  This is a class so that it can be used with a template function
+ * for parsing strings.
+ */
+struct is_alpha 
+{
+	static inline bool check(const char c)
+	{
+		return ((c >= 'a') && (c <= 'z')) || ((c >= 'A') &&
+			(c <= 'Z'));
+	}
+};
+/**
+ * Check whether a character is in the set allowed for node names.  This is a
+ * class so that it can be used with a template function for parsing strings.
+ */
+struct is_node_name_character
+{
+	static inline bool check(const char c)
+	{
+		switch(c)
+		{
+			default:
+				return false;
+			case 'a'...'z': case 'A'...'Z': case '0'...'9':
+			case ',': case '.': case '+': case '-':
+			case '_':
+				return true;
+		}
+	}
+};
+/**
+ * Check whether a character is in the set allowed for property names.  This is
+ * a class so that it can be used with a template function for parsing strings.
+ */
+struct is_property_name_character
+{
+	static inline bool check(const char c)
+	{
+		switch(c)
+		{
+			default:
+				return false;
+			case 'a'...'z': case 'A'...'Z': case '0'...'9':
+			case ',': case '.': case '+': case '-':
+			case '_': case '#':
+				return true;
+		}
+	}
+};
+
+}
+
+namespace dtc
+{
+
+template<class T> string
+string::parse(input_buffer &s)
+{
+	const char *start = s;
+	int l=0;
+	while (T::check(*s)) { l++; ++s; }
+	return string(start, l);
+}
+
+string::string(input_buffer &s) : start((const char*)s), length(0)
+{
+	while(s[length] != '\0')
+	{
+		length++;
+	}
+}
+
+string
+string::parse_node_name(input_buffer &s)
+{
+	return parse<is_node_name_character>(s);
+}
+
+string
+string::parse_property_name(input_buffer &s)
+{
+	return parse<is_property_name_character>(s);
+}
+string
+string::parse_node_or_property_name(input_buffer &s, bool &is_property)
+{
+	if (is_property)
+	{
+		return parse_property_name(s);
+	}
+	const char *start = s;
+	int l=0;
+	while (is_node_name_character::check(*s))
+	{
+		l++;
+		++s;
+	}
+	while (is_property_name_character::check(*s))
+	{
+		l++;
+		++s;
+		is_property = true;
+	}
+	return string(start, l);
+}
+
+bool
+string::operator==(const string& other) const
+{
+	return (length == other.length) &&
+	       (memcmp(start, other.start, length) == 0);
+}
+
+bool
+string::operator==(const char *other) const
+{
+	return strncmp(other, start, length) == 0;
+}
+
+bool
+string::operator<(const string& other) const
+{
+	if (length < other.length) { return true; }
+	if (length > other.length) { return false; }
+	return memcmp(start, other.start, length) < 0;
+}
+
+void
+string::push_to_buffer(byte_buffer &buffer, bool escapes)
+{
+	for (int i=0 ; i<length ; ++i)
+	{
+		uint8_t c = start[i];
+		if (escapes && c == '\\' && i+1 < length)
+		{
+			c = start[++i];
+			switch (c)
+			{
+				// For now, we just ignore invalid escape sequences.
+				default:
+				case '"':
+				case '\'':
+				case '\\':
+					break;
+				case 'a':
+					c = '\a';
+					break;
+				case 'b':
+					c = '\b';
+					break;
+				case 't':
+					c = '\t';
+					break;
+				case 'n':
+					c = '\n';
+					break;
+				case 'v':
+					c = '\v';
+					break;
+				case 'f':
+					c = '\f';
+					break;
+				case 'r':
+					c = '\r';
+					break;
+				case '0'...'7':
+				{
+					int v = digittoint(c);
+					if (i+1 < length && start[i+1] <= '7' && start[i+1] >= '0')
+					{
+						v <<= 3;
+						v |= digittoint(start[i+1]);
+						i++;
+						if (i+1 < length && start[i+1] <= '7' && start[i+1] >= '0')
+						{
+							v <<= 3;
+							v |= digittoint(start[i+1]);
+						}
+					}
+					c = (uint8_t)v;
+					break;
+				}
+				case 'x':
+				{
+					++i;
+					if (i >= length)
+					{
+						break;
+					}
+					int v = digittoint(start[i]);
+					if (i+1 < length && ishexdigit(start[i+1]))
+					{
+						v <<= 4;
+						v |= digittoint(start[++i]);
+					}
+					c = (uint8_t)v;
+					break;
+				}
+			}
+		}
+		buffer.push_back(c);
+	}
+}
+
+void
+string::print(FILE *file)
+{
+	fwrite(start, length, 1, file);
+}
+
+void
+string::dump()
+{
+	print(stderr);
+}
+
+} // namespace dtc
+
diff --git a/usr.bin/dtc/string.hh b/usr.bin/dtc/string.hh
new file mode 100644
index 0000000..45bc4fd
--- /dev/null
+++ b/usr.bin/dtc/string.hh
@@ -0,0 +1,147 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _STRING_HH_
+#define _STRING_HH_
+#include "input_buffer.hh"
+
+namespace dtc
+{
+
+/**
+ * String, referring to a place in the input file.  We don't bother copying
+ * strings until we write them to the final output.  These strings should be
+ * two words long: a start and a length.  They are intended to be cheap to copy
+ * and store in collections.  Copying the string object does not copy the
+ * underlying storage.
+ *
+ * Strings are not nul-terminated.
+ */
+class string
+{
+	/** Start address.  Contained within the mmap()'d input file and not
+	 * owned by this object. */
+	const char *start;
+	/** length of the string.  DTS strings are allowed to contain nuls */
+	int length;
+	/** Generic function for parsing strings matching the character set
+	 * defined by the template argument.  */
+	template<class T>
+	static string parse(input_buffer &s);
+	public:
+	/**
+	 * Constructs a string referring into another buffer.
+	 */
+	string(const char *s, int l) : start(s), length(l) {}
+	/** Constructs a string from a C string.  */
+	string(const char *s) : start(s), length(strlen(s)) {}
+	/** Default constructor, returns an empty string. */
+	string() : start(0), length(0) {}
+	/** Construct a from an input buffer, ending with a nul terminator. */
+	string(input_buffer &s);
+	/**
+	 * Returns the longest string in the input buffer starting at the
+	 * current cursor and composed entirely of characters that are valid in
+	 * node names.
+	 */
+	static string parse_node_name(input_buffer &s);
+	/**
+	 * Returns the longest string in the input buffer starting at the
+	 * current cursor and composed entirely of characters that are valid in
+	 * property names.
+	 */
+	static string parse_property_name(input_buffer &s);
+	/**
+	 * Parses either a node or a property name.  If is_property is true on
+	 * entry, then only property names are parsed.  If it is false, then it
+	 * will be set, on return, to indicate whether the parsed name is only
+	 * valid as a property.
+	 */
+	static string parse_node_or_property_name(input_buffer &s,
+	                                          bool &is_property);
+	/**
+	 * Compares two strings for equality.  Strings are equal if they refer
+	 * to identical byte sequences.
+	 */
+	bool operator==(const string& other) const;
+	/**
+	 * Compares a string against a C string.  The trailing nul in the C
+	 * string is ignored for the purpose of comparison, so this will always
+	 * fail if the string contains nul bytes.
+	 */
+	bool operator==(const char *other) const;
+	/**
+	 * Inequality operator, defined as the inverse of the equality
+	 * operator.
+	 */
+	template <typename T>
+	inline bool operator!=(T other)
+	{
+		return !(*this == other);
+	}
+	/**
+	 * Comparison operator, defined to allow strings to be used as keys in
+	 * maps.
+	 */
+	bool operator<(const string& other) const;
+	/**
+	 * Returns true if this is the empty string, false otherwise.
+	 */
+	inline bool empty() const
+	{
+		return length == 0;
+	}
+	/**
+	 * Returns the size of the string, in bytes.
+	 */
+	inline size_t size()
+	{
+		return length;
+	}
+	/**
+	 * Writes the string to the specified buffer.
+	 */
+	void push_to_buffer(byte_buffer &buffer, bool escapes=false);
+	/**
+	 * Prints the string to the specified output stream.
+	 */
+	void print(FILE *file);
+	/**
+	 * Dumps the string to the standard error stream.  Intended to be used
+	 * for debugging.
+	 */
+	void dump();
+};
+
+} // namespace dtc
+
+#endif // !_STRING_HH_
diff --git a/usr.bin/dtc/util.hh b/usr.bin/dtc/util.hh
new file mode 100644
index 0000000..7f2ec67
--- /dev/null
+++ b/usr.bin/dtc/util.hh
@@ -0,0 +1,92 @@
+/*-
+ * Copyright (c) 2013 David Chisnall
+ * All rights reserved.
+ *
+ * This software was developed by SRI International and the University of
+ * Cambridge Computer Laboratory under DARPA/AFRL contract (FA8750-10-C-0237)
+ * ("CTSRD"), as part of the DARPA CRASH research programme.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _UTIL_HH_
+#define _UTIL_HH_
+
+#include <vector>
+
+// If we aren't using C++11, then just ignore static asserts.
+#if __cplusplus < 201103L
+#ifndef static_assert
+#define static_assert(x, y) ((void)0)
+#endif
+#endif
+
+namespace dtc {
+
+/**
+ * Type for a buffer of bytes.  This is used for a lot of short-lived temporary
+ * variables, so may eventually be changed to something like LLVM's
+ * SmallVector, but currently the program runs in a tiny fraction of a second,
+ * so this is not an issue.
+ */
+typedef std::vector<uint8_t> byte_buffer;
+
+/**
+ * Helper function to push a big endian value into a byte buffer.  We use
+ * native-endian values for all of the in-memory data structures and only
+ * transform them into big endian form for output.
+ */
+template<typename T>
+inline void push_big_endian(byte_buffer &v, T val)
+{
+	static_assert(sizeof(T) > 1,
+		"Big endian doesn't make sense for single-byte values");
+	for (int bit=(sizeof(T) - 1)*8 ; bit>=0 ; bit-= 8)
+	{
+		v.push_back((val >> bit) & 0xff);
+	}
+}
+
+/**
+ * Simple inline non-locale-aware check that this is a valid ASCII
+ * digit.
+ */
+inline bool isdigit(char c)
+{
+	return (c >= '0') && (c <= '9');
+}
+
+/**
+ * Simple inline non-locale-aware check that this is a valid ASCII
+ * hex digit.
+ */
+inline bool ishexdigit(char c)
+{
+	return ((c >= '0') && (c <= '9')) || ((c >= 'a') && (c <= 'f')) ||
+		((c >= 'A') && (c <= 'Z'));
+}
+
+}// namespace dtc
+
+#endif // !_UTIL_HH_