Initial commit

16 files changed, 2985 insertions, 0 deletions

diff --git a/COPYING b/COPYING
new file mode 100644
index 0000000..d60c31a
--- /dev/null
+++ b/COPYING
@@ -0,0 +1,340 @@
+		    GNU GENERAL PUBLIC LICENSE
+		       Version 2, June 1991
+
+ Copyright (C) 1989, 1991 Free Software Foundation, Inc.
+     59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ Everyone is permitted to copy and distribute verbatim copies
+ of this license document, but changing it is not allowed.
+
+			    Preamble
+
+  The licenses for most software are designed to take away your
+freedom to share and change it.  By contrast, the GNU General Public
+License is intended to guarantee your freedom to share and change free
+software--to make sure the software is free for all its users.  This
+General Public License applies to most of the Free Software
+Foundation's software and to any other program whose authors commit to
+using it.  (Some other Free Software Foundation software is covered by
+the GNU Library General Public License instead.)  You can apply it to
+your programs, too.
+
+  When we speak of free software, we are referring to freedom, not
+price.  Our General Public Licenses are designed to make sure that you
+have the freedom to distribute copies of free software (and charge for
+this service if you wish), that you receive source code or can get it
+if you want it, that you can change the software or use pieces of it
+in new free programs; and that you know you can do these things.
+
+  To protect your rights, we need to make restrictions that forbid
+anyone to deny you these rights or to ask you to surrender the rights.
+These restrictions translate to certain responsibilities for you if you
+distribute copies of the software, or if you modify it.
+
+  For example, if you distribute copies of such a program, whether
+gratis or for a fee, you must give the recipients all the rights that
+you have.  You must make sure that they, too, receive or can get the
+source code.  And you must show them these terms so they know their
+rights.
+
+  We protect your rights with two steps: (1) copyright the software, and
+(2) offer you this license which gives you legal permission to copy,
+distribute and/or modify the software.
+
+  Also, for each author's protection and ours, we want to make certain
+that everyone understands that there is no warranty for this free
+software.  If the software is modified by someone else and passed on, we
+want its recipients to know that what they have is not the original, so
+that any problems introduced by others will not reflect on the original
+authors' reputations.
+
+  Finally, any free program is threatened constantly by software
+patents.  We wish to avoid the danger that redistributors of a free
+program will individually obtain patent licenses, in effect making the
+program proprietary.  To prevent this, we have made it clear that any
+patent must be licensed for everyone's free use or not licensed at all.
+
+  The precise terms and conditions for copying, distribution and
+modification follow.
+
+		    GNU GENERAL PUBLIC LICENSE
+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION
+
+  0. This License applies to any program or other work which contains
+a notice placed by the copyright holder saying it may be distributed
+under the terms of this General Public License.  The "Program", below,
+refers to any such program or work, and a "work based on the Program"
+means either the Program or any derivative work under copyright law:
+that is to say, a work containing the Program or a portion of it,
+either verbatim or with modifications and/or translated into another
+language.  (Hereinafter, translation is included without limitation in
+the term "modification".)  Each licensee is addressed as "you".
+
+Activities other than copying, distribution and modification are not
+covered by this License; they are outside its scope.  The act of
+running the Program is not restricted, and the output from the Program
+is covered only if its contents constitute a work based on the
+Program (independent of having been made by running the Program).
+Whether that is true depends on what the Program does.
+
+  1. You may copy and distribute verbatim copies of the Program's
+source code as you receive it, in any medium, provided that you
+conspicuously and appropriately publish on each copy an appropriate
+copyright notice and disclaimer of warranty; keep intact all the
+notices that refer to this License and to the absence of any warranty;
+and give any other recipients of the Program a copy of this License
+along with the Program.
+
+You may charge a fee for the physical act of transferring a copy, and
+you may at your option offer warranty protection in exchange for a fee.
+
+  2. You may modify your copy or copies of the Program or any portion
+of it, thus forming a work based on the Program, and copy and
+distribute such modifications or work under the terms of Section 1
+above, provided that you also meet all of these conditions:
+
+    a) You must cause the modified files to carry prominent notices
+    stating that you changed the files and the date of any change.
+
+    b) You must cause any work that you distribute or publish, that in
+    whole or in part contains or is derived from the Program or any
+    part thereof, to be licensed as a whole at no charge to all third
+    parties under the terms of this License.
+
+    c) If the modified program normally reads commands interactively
+    when run, you must cause it, when started running for such
+    interactive use in the most ordinary way, to print or display an
+    announcement including an appropriate copyright notice and a
+    notice that there is no warranty (or else, saying that you provide
+    a warranty) and that users may redistribute the program under
+    these conditions, and telling the user how to view a copy of this
+    License.  (Exception: if the Program itself is interactive but
+    does not normally print such an announcement, your work based on
+    the Program is not required to print an announcement.)
+
+These requirements apply to the modified work as a whole.  If
+identifiable sections of that work are not derived from the Program,
+and can be reasonably considered independent and separate works in
+themselves, then this License, and its terms, do not apply to those
+sections when you distribute them as separate works.  But when you
+distribute the same sections as part of a whole which is a work based
+on the Program, the distribution of the whole must be on the terms of
+this License, whose permissions for other licensees extend to the
+entire whole, and thus to each and every part regardless of who wrote it.
+
+Thus, it is not the intent of this section to claim rights or contest
+your rights to work written entirely by you; rather, the intent is to
+exercise the right to control the distribution of derivative or
+collective works based on the Program.
+
+In addition, mere aggregation of another work not based on the Program
+with the Program (or with a work based on the Program) on a volume of
+a storage or distribution medium does not bring the other work under
+the scope of this License.
+
+  3. You may copy and distribute the Program (or a work based on it,
+under Section 2) in object code or executable form under the terms of
+Sections 1 and 2 above provided that you also do one of the following:
+
+    a) Accompany it with the complete corresponding machine-readable
+    source code, which must be distributed under the terms of Sections
+    1 and 2 above on a medium customarily used for software interchange; or,
+
+    b) Accompany it with a written offer, valid for at least three
+    years, to give any third party, for a charge no more than your
+    cost of physically performing source distribution, a complete
+    machine-readable copy of the corresponding source code, to be
+    distributed under the terms of Sections 1 and 2 above on a medium
+    customarily used for software interchange; or,
+
+    c) Accompany it with the information you received as to the offer
+    to distribute corresponding source code.  (This alternative is
+    allowed only for noncommercial distribution and only if you
+    received the program in object code or executable form with such
+    an offer, in accord with Subsection b above.)
+
+The source code for a work means the preferred form of the work for
+making modifications to it.  For an executable work, complete source
+code means all the source code for all modules it contains, plus any
+associated interface definition files, plus the scripts used to
+control compilation and installation of the executable.  However, as a
+special exception, the source code distributed need not include
+anything that is normally distributed (in either source or binary
+form) with the major components (compiler, kernel, and so on) of the
+operating system on which the executable runs, unless that component
+itself accompanies the executable.
+
+If distribution of executable or object code is made by offering
+access to copy from a designated place, then offering equivalent
+access to copy the source code from the same place counts as
+distribution of the source code, even though third parties are not
+compelled to copy the source along with the object code.
+
+  4. You may not copy, modify, sublicense, or distribute the Program
+except as expressly provided under this License.  Any attempt
+otherwise to copy, modify, sublicense or distribute the Program is
+void, and will automatically terminate your rights under this License.
+However, parties who have received copies, or rights, from you under
+this License will not have their licenses terminated so long as such
+parties remain in full compliance.
+
+  5. You are not required to accept this License, since you have not
+signed it.  However, nothing else grants you permission to modify or
+distribute the Program or its derivative works.  These actions are
+prohibited by law if you do not accept this License.  Therefore, by
+modifying or distributing the Program (or any work based on the
+Program), you indicate your acceptance of this License to do so, and
+all its terms and conditions for copying, distributing or modifying
+the Program or works based on it.
+
+  6. Each time you redistribute the Program (or any work based on the
+Program), the recipient automatically receives a license from the
+original licensor to copy, distribute or modify the Program subject to
+these terms and conditions.  You may not impose any further
+restrictions on the recipients' exercise of the rights granted herein.
+You are not responsible for enforcing compliance by third parties to
+this License.
+
+  7. If, as a consequence of a court judgment or allegation of patent
+infringement or for any other reason (not limited to patent issues),
+conditions are imposed on you (whether by court order, agreement or
+otherwise) that contradict the conditions of this License, they do not
+excuse you from the conditions of this License.  If you cannot
+distribute so as to satisfy simultaneously your obligations under this
+License and any other pertinent obligations, then as a consequence you
+may not distribute the Program at all.  For example, if a patent
+license would not permit royalty-free redistribution of the Program by
+all those who receive copies directly or indirectly through you, then
+the only way you could satisfy both it and this License would be to
+refrain entirely from distribution of the Program.
+
+If any portion of this section is held invalid or unenforceable under
+any particular circumstance, the balance of the section is intended to
+apply and the section as a whole is intended to apply in other
+circumstances.
+
+It is not the purpose of this section to induce you to infringe any
+patents or other property right claims or to contest validity of any
+such claims; this section has the sole purpose of protecting the
+integrity of the free software distribution system, which is
+implemented by public license practices.  Many people have made
+generous contributions to the wide range of software distributed
+through that system in reliance on consistent application of that
+system; it is up to the author/donor to decide if he or she is willing
+to distribute software through any other system and a licensee cannot
+impose that choice.
+
+This section is intended to make thoroughly clear what is believed to
+be a consequence of the rest of this License.
+
+  8. If the distribution and/or use of the Program is restricted in
+certain countries either by patents or by copyrighted interfaces, the
+original copyright holder who places the Program under this License
+may add an explicit geographical distribution limitation excluding
+those countries, so that distribution is permitted only in or among
+countries not thus excluded.  In such case, this License incorporates
+the limitation as if written in the body of this License.
+
+  9. The Free Software Foundation may publish revised and/or new versions
+of the General Public License from time to time.  Such new versions will
+be similar in spirit to the present version, but may differ in detail to
+address new problems or concerns.
+
+Each version is given a distinguishing version number.  If the Program
+specifies a version number of this License which applies to it and "any
+later version", you have the option of following the terms and conditions
+either of that version or of any later version published by the Free
+Software Foundation.  If the Program does not specify a version number of
+this License, you may choose any version ever published by the Free Software
+Foundation.
+
+  10. If you wish to incorporate parts of the Program into other free
+programs whose distribution conditions are different, write to the author
+to ask for permission.  For software which is copyrighted by the Free
+Software Foundation, write to the Free Software Foundation; we sometimes
+make exceptions for this.  Our decision will be guided by the two goals
+of preserving the free status of all derivatives of our free software and
+of promoting the sharing and reuse of software generally.
+
+			    NO WARRANTY
+
+  11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY
+FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.  EXCEPT WHEN
+OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES
+PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED
+OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS
+TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU.  SHOULD THE
+PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING,
+REPAIR OR CORRECTION.
+
+  12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING
+WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR
+REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES,
+INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING
+OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED
+TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
+YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
+PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGES.
+
+		     END OF TERMS AND CONDITIONS
+
+	    How to Apply These Terms to Your New Programs
+
+  If you develop a new program, and you want it to be of the greatest
+possible use to the public, the best way to achieve this is to make it
+free software which everyone can redistribute and change under these terms.
+
+  To do so, attach the following notices to the program.  It is safest
+to attach them to the start of each source file to most effectively
+convey the exclusion of warranty; and each file should have at least
+the "copyright" line and a pointer to where the full notice is found.
+
+    <one line to give the program's name and a brief idea of what it does.>
+    Copyright (C) <year>  <name of author>
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program; if not, write to the Free Software
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+Also add information on how to contact you by electronic and paper mail.
+
+If the program is interactive, make it output a short notice like this
+when it starts in an interactive mode:
+
+    Gnomovision version 69, Copyright (C) year  name of author
+    Gnomovision comes with ABSOLUTELY NO WARRANTY; for details type `show w'.
+    This is free software, and you are welcome to redistribute it
+    under certain conditions; type `show c' for details.
+
+The hypothetical commands `show w' and `show c' should show the appropriate
+parts of the General Public License.  Of course, the commands you use may
+be called something other than `show w' and `show c'; they could even be
+mouse-clicks or menu items--whatever suits your program.
+
+You should also get your employer (if you work as a programmer) or your
+school, if any, to sign a "copyright disclaimer" for the program, if
+necessary.  Here is a sample; alter the names:
+
+  Yoyodyne, Inc., hereby disclaims all copyright interest in the program
+  `Gnomovision' (which makes passes at compilers) written by James Hacker.
+
+  <signature of Ty Coon>, 1 April 1989
+  Ty Coon, President of Vice
+
+This General Public License does not permit incorporating your program into
+proprietary programs.  If your program is a subroutine library, you may
+consider it more useful to permit linking proprietary applications with the
+library.  If this is what you want to do, use the GNU Library General
+Public License instead of this License.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..1dca00b
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,32 @@
+TARGETS = dtc
+CFLAGS = -Wall -g
+
+OBJS = dtc.o livetree.o flattree.o data.o treesource.o fstree.o \
+	y.tab.o lex.yy.o
+
+all: $(TARGETS)
+
+dtc:	$(OBJS)
+	$(LINK.c) -o $@ $^
+
+$(OBJS): dtc.h
+
+y.tab.c y.tab.h: dtc-parser.y
+	$(YACC) -d $<
+
+lex.yy.c: dtc-lexer.l
+	$(LEX) $<
+
+lex.yy.o: lex.yy.c y.tab.h
+
+dtc-parser.c:	dtc-lexer.c
+
+check: all
+	cd tests && $(MAKE) check
+
+clean:
+	rm -f *~ *.o a.out core $(TARGETS)
+	rm -f *.tab.[ch] lex.yy.c
+	rm -f *.i *.output vgcore.*
+	cd tests && $(MAKE) clean
+
diff --git a/TODO b/TODO
new file mode 100644
index 0000000..7136979
--- /dev/null
+++ b/TODO
@@ -0,0 +1,19 @@
+- Bugfixes:
+
+- Error handling / reporting
+	* Report line/column numbers for syntax errors
+	* Better categorization of errors into severity levels
+- Generate mem reserve map
+	* Command line options to place a number of blank entries to be
+	  filled in by bootloader
+	* memory reserve section in source
+- Testsuite
+- Actually number releases, revision control, all that kind of jazz
+
+- Labels:
+	Allow labels in tree source, which will be propogated and
+	exported as symbols in asm output
+- Autogenerate phandles
+	Allow property values to contain a reference to another node
+	(by path or label) which will be turned into a phandle for that node
+	in the output.
diff --git a/comment-test.dts b/comment-test.dts
new file mode 100644
index 0000000..b8d5637
--- /dev/null
+++ b/comment-test.dts
@@ -0,0 +1,35 @@
+/* regexps for lexing comments are.. tricky.  Check if we've actually
+ * got it right */
+
+/ {
+	// line comment
+	prop1;
+	/* comment */
+	prop2;
+	/* multiline
+
+	notaprop1;
+
+	   comment */
+	prop3;
+	/**/
+	prop4;
+	/***/
+	prop5;
+	/****/
+	prop6;
+	/* another
+	 * multiline
+	 * comment */
+	prop7;
+	/* yet
+	 * another
+	 * multline
+	 * comment
+	 */
+	prop8;
+	/** try this */
+	prop9;
+	/* and this **/
+};
+/* final comment */
diff --git a/data.c b/data.c
new file mode 100644
index 0000000..aef8c36
--- /dev/null
+++ b/data.c
@@ -0,0 +1,250 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include "dtc.h"
+
+#if 0
+static struct data data_init_buf(char *buf, int len)
+{
+	struct data d;
+
+	d.asize = 0;
+	d.len = len;
+	d.val = buf;
+
+	return d;
+}
+
+struct data data_ref_string(char *str)
+{
+	return data_init_buf(str, strlen(str)+1);
+}
+#endif
+
+void data_free(struct data d)
+{
+	assert(!d.val || d.asize);
+
+	if (d.val)
+		free(d.val);
+}
+
+struct data data_grow_for(struct data d, int xlen)
+{
+	struct data nd;
+	int newsize;
+
+	/* we must start with an allocated datum */
+	assert(!d.val || d.asize);
+
+	if (xlen == 0)
+		return d;
+
+	newsize = xlen;
+
+	while ((d.len + xlen) > newsize)
+		newsize *= 2;
+
+	nd.asize = newsize;
+	nd.val = xrealloc(d.val, newsize);
+	nd.len = d.len;
+
+	assert(nd.asize >= (d.len + xlen));
+
+	return nd;
+}
+
+struct data data_copy_mem(char *mem, int len)
+{
+	struct data d;
+
+	d = data_grow_for(empty_data, len);
+
+	d.len = len;
+	memcpy(d.val, mem, len);
+
+	return d;
+}
+
+char hexval(char c)
+{
+	switch (c) {
+	case '0' ... '9':
+		return c - '0';
+	case 'a' ... 'f':
+		return c - 'a';
+	case 'A' ... 'F':
+		return c - 'A';
+	default:
+		assert(0);
+	}
+}
+
+char get_oct_char(char *s, int *i)
+{
+	char x[4];
+	char *endx;
+	long val;
+
+	x[3] = '\0';
+	x[0] = s[(*i)];
+	if (x[0]) {
+		x[1] = s[(*i)+1];
+		if (x[1])
+			x[2] = s[(*i)+2];
+	}
+
+	val = strtol(x, &endx, 8);
+	if ((endx - x) == 0)
+		fprintf(stderr, "Empty \\nnn escape\n");
+		
+	(*i) += endx - x;
+	return val;
+}
+
+char get_hex_char(char *s, int *i)
+{
+	char x[3];
+	char *endx;
+	long val;
+
+	x[2] = '\0';
+	x[0] = s[(*i)];
+	if (x[0])
+		x[1] = s[(*i)+1];
+
+	val = strtol(x, &endx, 16);
+	if ((endx - x) == 0)
+		fprintf(stderr, "Empty \\x escape\n");
+		
+	(*i) += endx - x;
+	return val;
+}
+
+struct data data_copy_escape_string(char *s, int len)
+{
+	int i = 0;
+	struct data d;
+	char *q;
+
+	d = data_grow_for(empty_data, strlen(s)+1);
+
+	q = d.val;
+	while (i < len) {
+		char c = s[i++];
+
+		if (c != '\\') {
+			q[d.len++] = c;
+			continue;
+		}
+
+		c = s[i++];
+		assert(c);
+		switch (c) {
+		case 't':
+			q[d.len++] = '\t';
+			break;
+		case 'n':
+			q[d.len++] = '\n';
+			break;
+		case 'r':
+			q[d.len++] = '\r';
+			break;
+		case '0' ... '7':
+			i--; /* need to re-read the first digit as
+			      * part of the octal value */
+			q[d.len++] = get_oct_char(s, &i);
+			break;
+		case 'x':
+			q[d.len++] = get_hex_char(s, &i);
+			break;
+		default:
+			q[d.len++] = c;
+		}
+	}
+
+	q[d.len++] = '\0';
+	return d;
+}
+
+struct data data_copy_file(FILE *f, size_t len)
+{
+	struct data d;
+
+	d = data_grow_for(empty_data, len);
+
+	d.len = len;
+	fread(d.val, len, 1, f);
+
+	return d;
+}
+
+struct data data_append_data(struct data d, void *p, int len)
+{
+	d = data_grow_for(d, len);
+	memcpy(d.val + d.len, p, len);
+	d.len += len;
+	return d;
+}
+
+struct data data_append_cell(struct data d, cell_t word)
+{
+	cell_t beword = cpu_to_be32(word);
+
+	return data_append_data(d, &beword, sizeof(beword));
+}
+
+struct data data_append_byte(struct data d, uint8_t byte)
+{
+	return data_append_data(d, &byte, 1);
+}
+
+struct data data_append_zeroes(struct data d, int len)
+{
+	d = data_grow_for(d, len);
+
+	memset(d.val + d.len, 0, len);
+	d.len += len;
+	return d;
+}
+
+struct data data_append_align(struct data d, int align)
+{
+	int newlen = ALIGN(d.len, align);
+	return data_append_zeroes(d, newlen - d.len);
+}
+
+int data_is_one_string(struct data d)
+{
+	int i;
+	int len = d.len;
+
+	if (len == 0)
+		return 0;
+
+	for (i = 0; i < len-1; i++)
+		if (d.val[i] == '\0')
+			return 0;
+
+	if (d.val[len-1] != '\0')
+		return 0;
+
+	return 1;
+}
diff --git a/dtc-lexer.l b/dtc-lexer.l
new file mode 100644
index 0000000..02283a9
--- /dev/null
+++ b/dtc-lexer.l
@@ -0,0 +1,140 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+%option noyywrap
+
+%x CELLDATA
+%x BYTESTRING
+
+PROPCHAR	[a-zA-Z0-9,._+*#?-]
+UNITCHAR	[0-9a-f,]
+WS		[ \t\n]
+
+%%
+
+%{
+#include "dtc.h"
+
+#include "y.tab.h"
+
+#undef LEXDEBUG	1
+
+%}
+
+\"[^"]*\"	{
+#ifdef LEXDEBUG
+			fprintf(stderr, "String: %s\n", yytext);
+#endif
+			yylval.data = data_copy_escape_string(yytext+1,
+					yyleng-2);
+			return DT_STRING;
+		}
+
+<CELLDATA>[0-9a-fA-F]+	{
+			if (yyleng > 2*sizeof(yylval.cval)) {
+				fprintf(stderr,
+					"Cell value %s too long\n", yytext);
+			}
+			yylval.cval = strtol(yytext, NULL, 16);
+#ifdef LEXDEBUG
+			fprintf(stderr, "Cell: %x\n", yylval.cval);
+#endif
+			return DT_CELL;
+		}
+
+<CELLDATA>">"	{
+#ifdef LEXDEBUG
+			fprintf(stderr, "/CELLDATA\n");
+#endif
+			BEGIN(INITIAL);
+			return '>';
+		}
+
+<BYTESTRING>[0-9a-fA-F]{2} {
+			yylval.byte = strtol(yytext, NULL, 16);
+#ifdef LEXDEBUG
+			fprintf(stderr, "Byte: %02x\n", (int)yylval.byte);
+#endif
+			return DT_BYTE;
+		}
+
+<BYTESTRING>"]"	{
+#ifdef LEXDEBUG
+			fprintf(stderr, "/BYTESTRING\n");
+#endif
+			BEGIN(INITIAL);
+			return ']';
+		}
+
+{PROPCHAR}+(@{UNITCHAR}+)?/{WS}*\{ {
+#ifdef LEXDEBUG
+			fprintf(stderr, "NodeName: %s\n", yytext);
+#endif
+			yylval.str = strdup(yytext);
+			return DT_NODENAME;
+		}
+
+{PROPCHAR}+	{
+#ifdef LEXDEBUG
+			fprintf(stderr, "PropName: %s\n", yytext);
+#endif
+			yylval.str = strdup(yytext);
+			return DT_PROPNAME;
+		}
+
+
+<*>{WS}+	/* eat whitespace */
+
+<*>"/*"([^*]|\*+[^*/])*\*+"/"	{
+#ifdef LEXDEBUG
+			fprintf(stderr, "Comment: %s\n", yytext);
+			/* eat comments */
+#endif
+		}
+
+<*>"//".*\n	/* eat line comments */
+
+.		{
+			switch (yytext[0]) {
+				case '<':
+#ifdef LEXDEBUG
+					fprintf(stderr, "CELLDATA\n");
+#endif
+					BEGIN(CELLDATA);
+					break;
+				case '[':
+#ifdef LEXDEBUG
+					fprintf(stderr, "BYTESTRING\n");
+#endif
+					BEGIN(BYTESTRING);
+					break;
+				default:
+
+#ifdef LEXDEBUG
+			fprintf(stderr, "Char: %c (\\x%02x)\n", yytext[0],
+				(unsigned)yytext[0]);
+#endif
+					break;
+			}
+
+			return yytext[0];
+		}
+
+%%
diff --git a/dtc-parser.y b/dtc-parser.y
new file mode 100644
index 0000000..f177fb7
--- /dev/null
+++ b/dtc-parser.y
@@ -0,0 +1,116 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+%{
+#include "dtc.h"
+
+int yylex (void);
+void yyerror (char const *);
+
+extern struct node *device_tree;
+
+%}
+
+%union {
+	cell_t cval;
+	uint8_t byte;
+	char *str;
+	struct data data;
+	struct property *prop;
+	struct property *proplist;
+	struct node *node;
+	struct node *nodelist;
+	int datalen;
+	int hexlen;
+}
+
+%token <str> DT_PROPNAME
+%token <str> DT_NODENAME
+%token <cval> DT_CELL
+%token <byte> DT_BYTE
+%token <data> DT_STRING
+%token <str> DT_UNIT
+
+%type <data> propdata
+%type <data> celllist
+%type <data> bytestring
+%type <prop> propdef
+%type <proplist> proplist
+
+%type <node> nodedef
+%type <node> subnode
+%type <nodelist> subnodes
+
+%%
+
+devicetree:	{
+			assert(device_tree == NULL);
+		} '/' nodedef { device_tree = name_node($3, ""); }
+	;
+
+nodedef:	'{' proplist subnodes '}' ';' {
+			$$ = build_node($2, $3);
+		}
+	;
+
+proplist:	propdef proplist {
+			$$ = chain_property($1, $2);
+		}
+	|	/* empty */	{
+			$$ = NULL;
+		}
+	;
+
+propdef:	DT_PROPNAME '=' propdata ';' {
+			$$ = build_property($1, $3);
+		}
+	|	DT_PROPNAME ';' {
+			$$ = build_empty_property($1);
+		}
+	;
+
+propdata:	DT_STRING { $$ = $1; }
+	|	'<' celllist '>' { $$ = $2; }
+	|	'[' bytestring ']' { $$ = $2; }
+	;
+
+celllist:	celllist DT_CELL { $$ = data_append_cell($1, $2); }
+	|	/* empty */ { $$ = empty_data; }
+	;
+
+bytestring:	bytestring DT_BYTE { $$ = data_append_byte($1, $2); }
+	|	/* empty */ { $$ = empty_data; }
+	;
+
+subnodes:	subnode subnodes {
+			$$ = chain_node($1, $2);
+		}
+	|	/* empty */ { $$ = NULL; }
+	;
+
+subnode:	DT_NODENAME nodedef { $$ = name_node($2, $1); }
+	;
+
+%%
+
+void yyerror (char const *s)
+{
+	fprintf (stderr, "%s\n", s);
+}
diff --git a/dtc.c b/dtc.c
new file mode 100644
index 0000000..f527e08
--- /dev/null
+++ b/dtc.c
@@ -0,0 +1,198 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include "dtc.h"
+
+char *join_path(char *path, char *name)
+{
+	int lenp = strlen(path);
+	int lenn = strlen(name);
+	int len;
+	int needslash = 1;
+	char *str;
+
+	len = lenp + lenn + 2;
+	if ((lenp > 0) && (path[lenp-1] == '/')) {
+		needslash = 0;
+		len--;
+	}
+
+	str = xmalloc(len);
+	memcpy(str, path, lenp);
+	if (needslash) {
+		str[lenp] = '/';
+		lenp++;
+	}
+	memcpy(str+lenp, name, lenn+1);
+	return str;
+}
+
+void fill_fullpaths(struct node *tree, char *prefix)
+{
+	struct node *child;
+	char *unit;
+
+	tree->fullpath = join_path(prefix, tree->name);
+
+	unit = strchr(tree->name, '@');
+	if (unit)
+		tree->basenamelen = unit - tree->name;
+	else
+		tree->basenamelen = strlen(tree->name);
+
+	for_each_child(tree, child)
+		fill_fullpaths(child, tree->fullpath);
+}
+
+static FILE *dtc_open_file(char *fname)
+{
+	FILE *f;
+
+	if (streq(fname, "-"))
+		f = stdin;
+	else
+		f = fopen(fname, "r");
+
+	if (! f)
+		die("Couldn't open \"%s\": %s\n", fname, strerror(errno));
+
+	return f;
+}
+
+static void usage(void)
+{
+	fprintf(stderr, "Usage:\n");
+	fprintf(stderr, "\tdtc [options] <input file>\n");
+	fprintf(stderr, "\nOptions:\n");
+	fprintf(stderr, "\t-I <input format>\n");
+	fprintf(stderr, "\t\tInput formats are:\n");
+	fprintf(stderr, "\t\t\tdts - device tree source text\n");
+	fprintf(stderr, "\t\t\tdtb - device tree blob\n");
+	fprintf(stderr, "\t\t\tfs - /proc/device-tree style directory\n");
+	fprintf(stderr, "\t-O <output format>\n");
+	fprintf(stderr, "\t\tOutput formats are:\n");
+	fprintf(stderr, "\t\t\tdts - device tree source text\n");
+	fprintf(stderr, "\t\t\tdtb - device tree blob\n");
+	fprintf(stderr, "\t\t\tasm - assembler source\n");
+	fprintf(stderr, "\t-V <output version>\n");
+	fprintf(stderr, "\t\tBlob version to produce, defaults to 3 (relevant for dtb\n\t\tand asm output only)\n");
+	fprintf(stderr, "\t-R <number>\n");
+	fprintf(stderr, "\t\tMake space for <number> reserve map entries (relevant for \n\t\tdtb and asm output only)\n");
+	fprintf(stderr, "\t-f\n");
+	fprintf(stderr, "\t\tForce - try to produce output even if the input tree has errors\n");
+	exit(2);
+}
+
+int main(int argc, char *argv[])
+{
+	struct node *dt;
+	char *inform = "dts";
+	char *outform = "dts";
+	char *outname = "-";
+	int force = 0;
+	char *arg;
+	int opt;
+	FILE *inf = NULL;
+	FILE *outf = NULL;
+	int outversion = 3;
+	int reservenum = 1;
+
+	while ((opt = getopt(argc, argv, "I:O:o:V:R:f")) != EOF) {
+		switch (opt) {
+		case 'I':
+			inform = optarg;
+			break;
+		case 'O':
+			outform = optarg;
+			break;
+		case 'o':
+			outname = optarg;
+			break;
+		case 'V':
+			outversion = strtol(optarg, NULL, 0);
+			break;
+		case 'R':
+			reservenum = strtol(optarg, NULL, 0);
+			break;
+		case 'f':
+			force = 1;
+			break;
+		default:
+			usage();
+		}
+	}
+
+	if (argc > (optind+1))
+		usage();
+	else if (argc < (optind+1))
+		arg = "-";
+	else
+		arg = argv[optind];
+
+	fprintf(stderr, "DTC: %s->%s  on file \"%s\"\n",
+		inform, outform, arg);
+
+	if (streq(inform, "dts")) {
+		inf = dtc_open_file(arg);
+		dt = dt_from_source(inf);
+	} else if (streq(inform, "fs")) {
+		dt = dt_from_fs(arg);
+	} else if(streq(inform, "dtb")) {
+		inf = dtc_open_file(arg);
+		dt = dt_from_blob(inf);
+	} else {
+		die("Unknown input format \"%s\"\n", inform);
+	}
+
+	if (inf && (inf != stdin))
+		fclose(inf);
+
+	if (! dt)
+		die("Couldn't read input tree\n");
+
+	if (! check_device_tree(dt)) {
+		fprintf(stderr, "Input tree has errors\n");
+		if (! force)
+			exit(1);
+	}
+
+	if (streq(outname, "-")) {
+		outf = stdout;
+	} else {
+		outf = fopen(outname, "w");
+		if (! outf)
+			die("Couldn't open output file %s: %s\n",
+			    outname, strerror(errno));
+	}
+
+	if (streq(outform, "dts")) {
+		write_tree_source(outf, dt, 0);
+	} else if (streq(outform, "dtb")) {
+		write_dt_blob(outf, dt, outversion, reservenum);
+	} else if (streq(outform, "asm")) {
+		write_dt_asm(outf, dt, outversion, reservenum);
+	} else if (streq(outform, "null")) {
+		/* do nothing */
+	} else {
+		die("Unknown output format \"%s\"\n", outform);
+	}
+		
+	exit(0);
+}
diff --git a/dtc.h b/dtc.h
new file mode 100644
index 0000000..75a1ac5
--- /dev/null
+++ b/dtc.h
@@ -0,0 +1,181 @@
+#ifndef _DTC_H
+#define _DTC_H
+
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdarg.h>
+#include <assert.h>
+#include <ctype.h>
+#include <errno.h>
+#include <unistd.h>
+#include <netinet/in.h>
+
+static inline void die(char * str, ...)
+{
+	va_list ap;
+
+	va_start(ap, str);
+	fprintf(stderr, "FATAL ERROR: ");
+	vfprintf(stderr, str, ap);
+	exit(1);
+}
+
+static inline void *xmalloc(size_t len)
+{
+	void *new = malloc(len);
+
+	if (! new)
+		die("malloc() failed\n");
+
+	return new;
+}
+
+static inline void *xrealloc(void *p, size_t len)
+{
+	void *new = realloc(p, len);
+
+	if (! new)
+		die("realloc() failed (len=%d)\n", len);
+
+	return new;
+}
+
+typedef uint16_t u16;
+typedef uint32_t u32;
+typedef uint64_t u64;
+typedef u32 cell_t;
+
+#define cpu_to_be16(x)	htons(x)
+#define be16_to_cpu(x)	ntohs(x)
+
+#define cpu_to_be32(x)	htonl(x)
+#define be32_to_cpu(x)	ntohl(x)
+
+
+
+#define streq(a, b)	(strcmp((a), (b)) == 0)
+#define ALIGN(x, a)	(((x) + (a) - 1) & ~((a) - 1))
+#define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
+
+/* Data blobs */
+struct data {
+	int len;
+	char *val;
+	int asize;
+};
+
+#define empty_data ((struct data){.len = 0, .val = NULL, .asize = 0})
+
+void data_free(struct data d);
+
+struct data data_grow_for(struct data d, int xlen);
+
+struct data data_copy_mem(char *mem, int len);
+struct data data_copy_escape_string(char *s, int len);
+struct data data_copy_file(FILE *f, size_t len);
+
+struct data data_append_data(struct data d, void *p, int len);
+struct data data_append_cell(struct data d, cell_t word);
+struct data data_append_byte(struct data d, uint8_t byte);
+struct data data_append_zeroes(struct data d, int len);
+struct data data_append_align(struct data d, int align);
+
+int data_is_one_string(struct data d);
+
+/* DT constraints */
+
+#define MAX_PROPNAME_LEN	31
+#define MAX_NODENAME_LEN	31
+
+/* Live trees */
+struct property {
+	char *name;
+	struct data val;
+
+	struct property *next;
+};
+
+struct node {
+	char *name;
+	struct property *proplist;
+	struct node *children;
+
+	struct node *parent;
+	struct node *next_sibling;
+
+	char *fullpath;
+	int basenamelen;
+
+	cell_t phandle;
+	int addr_cells, size_cells;
+};
+
+#define for_each_property(n, p) \
+	for ((p) = (n)->proplist; (p); (p) = (p)->next)
+
+#define for_each_child(n, c)	\
+	for ((c) = (n)->children; (c); (c) = (c)->next_sibling)
+
+struct property *build_property(char *name, struct data val);
+struct property *build_empty_property(char *name);
+struct property *chain_property(struct property *first, struct property *list);
+
+struct node *build_node(struct property *proplist, struct node *children);
+struct node *name_node(struct node *node, char *name);
+struct node *chain_node(struct node *first, struct node *list);
+
+void add_property(struct node *node, struct property *prop);
+void add_child(struct node *parent, struct node *child);
+
+int check_device_tree(struct node *dt);
+
+/* Flattened trees */
+
+enum flat_dt_format {
+	FFMT_BIN,
+	FFMT_ASM,
+};
+
+void write_dt_blob(FILE *f, struct node *tree, int version, int reservenum);
+void write_dt_asm(FILE *f, struct node *tree, int version, int reservenum);
+
+struct node *dt_from_blob(FILE *f);
+
+/* Tree source */
+
+void write_tree_source(FILE *f, struct node *tree, int level);
+
+struct node *dt_from_source(FILE *f);
+
+/* FS trees */
+
+struct node *dt_from_fs(char *dirname);
+
+/* misc */
+
+char *join_path(char *path, char *name);
+void fill_fullpaths(struct node *tree, char *prefix);
+
+#endif /* _DTC_H */
diff --git a/flattree.c b/flattree.c
new file mode 100644
index 0000000..76d7e5d
--- /dev/null
+++ b/flattree.c
@@ -0,0 +1,799 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include "dtc.h"
+
+#define OF_DT_HEADER            0xd00dfeed      /* 4: version, 4: total size */
+
+#define OF_DT_BEGIN_NODE	0x1             /* Start node: full name */
+#define OF_DT_END_NODE		0x2             /* End node */
+#define OF_DT_PROP		0x3             /* Property: name off,
+                                                   size, content */
+#define OF_DT_END               0x9
+
+struct boot_param_header {
+	u32 magic;                  /* magic word OF_DT_HEADER */
+	u32 totalsize;              /* total size of DT block */
+	u32 off_dt_struct;          /* offset to structure */
+	u32 off_dt_strings;         /* offset to strings */
+	u32 off_mem_rsvmap;         /* offset to memory reserve map */
+	u32 version;                /* format version */
+	u32 last_comp_version;      /* last compatible version */
+
+        /* version 2 fields below */
+	u32 boot_cpuid_phys;        /* Which physical CPU id we're
+					    booting on */
+	/* version 3 fields below */
+        u32 size_dt_strings;        /* size of the strings block */
+};
+
+#define BPH_V1_SIZE	(7*sizeof(u32))
+#define BPH_V2_SIZE	(BPH_V1_SIZE + sizeof(u32))
+#define BPH_V3_SIZE	(BPH_V2_SIZE + sizeof(u32))
+
+struct reserve_entry {
+	u64 address;
+	u64 size;
+};
+
+#define FTF_FULLPATH	0x1
+#define FTF_VARALIGN	0x2
+#define FTF_NAMEPROPS	0x4
+#define FTF_BOOTCPUID	0x8
+#define FTF_STRTABSIZE	0x10
+
+struct version_info {
+	int version;
+	int last_comp_version;
+	int hdr_size;
+	int flags;
+} version_table[] = {
+	{1, 1, BPH_V1_SIZE,
+	 FTF_FULLPATH|FTF_VARALIGN|FTF_NAMEPROPS},
+	{2, 1, BPH_V2_SIZE,
+	 FTF_FULLPATH|FTF_VARALIGN|FTF_NAMEPROPS|FTF_BOOTCPUID},
+	{3, 1, BPH_V3_SIZE,
+	 FTF_FULLPATH|FTF_VARALIGN|FTF_NAMEPROPS|FTF_BOOTCPUID|FTF_STRTABSIZE},
+	{0x10, 0x10, BPH_V3_SIZE,
+	 FTF_BOOTCPUID|FTF_STRTABSIZE},
+};
+
+struct emitter {
+	void (*cell)(void *, cell_t);
+	void (*string)(void *, char *, int);
+	void (*align)(void *, int);
+	void (*data)(void *, struct data);
+	void (*beginnode)(void *);
+	void (*endnode)(void *);
+	void (*property)(void *);
+};
+
+static void bin_emit_cell(void *e, cell_t val)
+{
+	struct data *dtbuf = e;
+
+	*dtbuf = data_append_cell(*dtbuf, val);
+}
+
+static void bin_emit_string(void *e, char *str, int len)
+{
+	struct data *dtbuf = e;
+
+	if (len == 0)
+		len = strlen(str);
+
+	*dtbuf = data_append_data(*dtbuf, str, len);
+	*dtbuf = data_append_byte(*dtbuf, '\0');
+}
+
+static void bin_emit_align(void *e, int a)
+{
+	struct data *dtbuf = e;
+
+	*dtbuf = data_append_align(*dtbuf, a);
+}
+
+static void bin_emit_data(void *e, struct data d)
+{
+	struct data *dtbuf = e;
+
+	*dtbuf = data_append_data(*dtbuf, d.val, d.len);
+}
+
+static void bin_emit_beginnode(void *e)
+{
+	bin_emit_cell(e, OF_DT_BEGIN_NODE);
+}
+
+static void bin_emit_endnode(void *e)
+{
+	bin_emit_cell(e, OF_DT_END_NODE);
+}
+
+static void bin_emit_property(void *e)
+{
+	bin_emit_cell(e, OF_DT_PROP);
+}
+
+struct emitter bin_emitter = {
+	.cell = bin_emit_cell,
+	.string = bin_emit_string,
+	.align = bin_emit_align,
+	.data = bin_emit_data,
+	.beginnode = bin_emit_beginnode,
+	.endnode = bin_emit_endnode,
+	.property = bin_emit_property,	
+};
+
+static void asm_emit_cell(void *e, cell_t val)
+{
+	FILE *f = e;
+
+	fprintf(f, "\t.long\t0x%x\n", be32_to_cpu(val));
+}
+
+static void asm_emit_string(void *e, char *str, int len)
+{
+	FILE *f = e;
+	char c;
+
+	if (len != 0) {
+		/* XXX: ewww */
+		c = str[len];
+		str[len] = '\0';
+	}
+		
+	fprintf(f, "\t.string\t\"%s\"\n", str);
+
+	if (len != 0) {
+		str[len] = c;
+	}
+}
+
+static void asm_emit_align(void *e, int a)
+{
+	FILE *f = e;
+
+	fprintf(f, "\t.balign\t%d\n", a);
+}
+
+static void asm_emit_data(void *e, struct data d)
+{
+	FILE *f = e;
+	int off = 0;
+
+	while ((d.len - off) >= sizeof(u32)) {
+		fprintf(f, "\t.long\t0x%x\n",
+			be32_to_cpu(*((u32 *)(d.val+off))));
+		off += sizeof(u32);
+	}
+
+	if ((d.len - off) >= sizeof(u16)) {
+		fprintf(f, "\t.short\t0x%hx\n", 
+			be16_to_cpu(*((u16 *)(d.val+off))));
+		off += sizeof(u16);
+	}
+
+	if ((d.len - off) >= 1) {
+		fprintf(f, "\t.byte\t0x%hhx\n", d.val[off]);
+		off += 1;
+	}
+
+	assert(off == d.len);
+}
+
+static void asm_emit_beginnode(void *e)
+{
+	FILE *f = e;
+
+	fprintf(f, "\t.long\tOF_DT_BEGIN_NODE\n");
+}
+
+static void asm_emit_endnode(void *e)
+{
+	FILE *f = e;
+
+	fprintf(f, "\t.long\tOF_DT_END_NODE\n");
+}
+
+static void asm_emit_property(void *e)
+{
+	FILE *f = e;
+
+	fprintf(f, "\t.long\tOF_DT_PROP\n");
+}
+
+struct emitter asm_emitter = {
+	.cell = asm_emit_cell,
+	.string = asm_emit_string,
+	.align = asm_emit_align,
+	.data = asm_emit_data,
+	.beginnode = asm_emit_beginnode,
+	.endnode = asm_emit_endnode,
+	.property = asm_emit_property,	
+};
+
+static int stringtable_insert(struct data *d, char *str)
+{
+	int i;
+
+	/* FIXME: do this more efficiently? */
+
+	for (i = 0; i < d->len; i++) {
+		if (streq(str, d->val + i))
+			return i;
+	}
+
+	*d = data_append_data(*d, str, strlen(str)+1);
+	return i; /* i equals the old data length */
+}
+
+static void flatten_tree(struct node *tree, struct emitter *emit,
+			 void *etarget, struct data *strbuf,
+			 struct version_info *vi)
+{
+	struct property *prop;
+	struct node *child;
+	int seen_name_prop = 0;
+
+	emit->beginnode(etarget);
+
+	if (vi->flags & FTF_FULLPATH)
+		emit->string(etarget, tree->fullpath, 0);
+	else
+		emit->string(etarget, tree->name, 0);
+
+	emit->align(etarget, sizeof(cell_t));
+
+	for_each_property(tree, prop) {
+		int nameoff;
+
+		if (streq(prop->name, "name"))
+			seen_name_prop = 1;
+
+		nameoff = stringtable_insert(strbuf, prop->name);
+
+		emit->property(etarget);
+		emit->cell(etarget, prop->val.len);
+		emit->cell(etarget, nameoff);
+
+		if ((vi->flags & FTF_VARALIGN) && (prop->val.len >= 8))
+			emit->align(etarget, 8);
+
+		emit->data(etarget, prop->val);
+		emit->align(etarget, sizeof(cell_t));
+	}
+
+	if ((vi->flags & FTF_NAMEPROPS) && !seen_name_prop) {
+		emit->property(etarget);
+		emit->cell(etarget, tree->basenamelen+1);
+		emit->cell(etarget, stringtable_insert(strbuf, "name"));
+
+		if ((vi->flags & FTF_VARALIGN) && ((tree->basenamelen+1) >= 8))
+			emit->align(etarget, 8);
+
+		emit->string(etarget, tree->name, tree->basenamelen);
+	}
+
+	for_each_child(tree, child) {
+		flatten_tree(child, emit, etarget, strbuf, vi);
+	}
+
+	emit->endnode(etarget);
+}
+
+static void make_bph(struct boot_param_header *bph,
+			     struct version_info *vi,
+			     int reservenum,
+			     int dtsize, int strsize)
+{
+	int reservesize = (reservenum+1) * sizeof(struct reserve_entry);
+
+	memset(bph, 0xff, sizeof(*bph));
+
+	bph->magic = cpu_to_be32(OF_DT_HEADER);
+	bph->version = vi->version;
+	bph->last_comp_version = vi->last_comp_version;
+
+	bph->off_mem_rsvmap = cpu_to_be32(vi->hdr_size);
+	bph->off_dt_struct = cpu_to_be32(vi->hdr_size + reservesize);
+	bph->off_dt_strings = cpu_to_be32(vi->hdr_size + reservesize
+					  + dtsize);
+	bph->totalsize = cpu_to_be32(vi->hdr_size + reservesize
+				     + dtsize + strsize);
+		
+	if (vi->flags & FTF_BOOTCPUID)
+		bph->boot_cpuid_phys = 0xfeedbeef;
+	if (vi->flags & FTF_STRTABSIZE)
+		bph->size_dt_strings = cpu_to_be32(strsize);
+}
+
+void write_dt_blob(FILE *f, struct node *tree, int version, int reservenum)
+{
+	struct version_info *vi = NULL;
+	int i;
+	struct data dtbuf = empty_data;
+	struct data strbuf = empty_data;
+	struct boot_param_header bph;
+	struct reserve_entry re = {.address = 0, .size = 0};
+
+	for (i = 0; i < ARRAY_SIZE(version_table); i++) {
+		if (version_table[i].version == version)
+			vi = &version_table[i];
+	}
+	if (!vi)
+		die("Unknown device tree blob version %d\n", version);
+
+	dtbuf = empty_data;
+	strbuf = empty_data;
+
+	flatten_tree(tree, &bin_emitter, &dtbuf, &strbuf, vi);
+	bin_emit_cell(&dtbuf, OF_DT_END);
+
+	make_bph(&bph, vi, reservenum, dtbuf.len, strbuf.len);
+
+	fwrite(&bph, vi->hdr_size, 1, f);
+	for (i = 0; i < reservenum+1; i++)
+		fwrite(&re, sizeof(re), 1, f);
+
+	fwrite(dtbuf.val, dtbuf.len, 1, f);
+	fwrite(strbuf.val, strbuf.len, 1, f);
+
+	if (ferror(f))
+		die("Error writing device tree blob: %s\n", strerror(errno));
+
+	data_free(dtbuf);
+	data_free(strbuf);
+}
+
+void dump_stringtable_asm(FILE *f, struct data strbuf)
+{
+	char *p;
+	int len;
+
+	p = strbuf.val;
+
+	while (p < (strbuf.val + strbuf.len)) {
+		len = strlen(p);
+		fprintf(f, "\t.string \"%s\"\n", p);
+		p += len+1;
+	}
+}
+
+void emit_label(FILE *f, char *prefix, char *label)
+{
+	fprintf(f, "\t.globl\t%s_%s\n", prefix, label);
+	fprintf(f, "%s_%s:\n", prefix, label);
+	fprintf(f, "_%s_%s:\n", prefix, label);
+}
+
+void write_dt_asm(FILE *f, struct node *tree, int version, int reservenum)
+{
+	struct version_info *vi = NULL;
+	int i;
+	struct data strbuf = empty_data;
+	char *symprefix = "dt";
+
+	for (i = 0; i < ARRAY_SIZE(version_table); i++) {
+		if (version_table[i].version == version)
+			vi = &version_table[i];
+	}
+	if (!vi)
+		die("Unknown device tree blob version %d\n", version);
+
+	fprintf(f, "/* autogenerated by dtc, do not edit */\n\n");
+	fprintf(f, "#define OF_DT_HEADER 0x%x\n", OF_DT_HEADER);
+	fprintf(f, "#define OF_DT_BEGIN_NODE 0x%x\n", OF_DT_BEGIN_NODE);
+	fprintf(f, "#define OF_DT_END_NODE 0x%x\n", OF_DT_END_NODE);
+	fprintf(f, "#define OF_DT_PROP 0x%x\n", OF_DT_PROP);
+	fprintf(f, "#define OF_DT_END 0x%x\n", OF_DT_END);
+	fprintf(f, "\n");
+
+	emit_label(f, symprefix, "blob_start");
+	emit_label(f, symprefix, "header");
+	fprintf(f, "\t.long\tOF_DT_HEADER /* magic */\n");
+	fprintf(f, "\t.long\t_%s_blob_end - _%s_blob_start /* totalsize */\n",
+		symprefix, symprefix);
+	fprintf(f, "\t.long\t_%s_struct_start - _%s_blob_start /* off_dt_struct */\n",
+		symprefix, symprefix);
+	fprintf(f, "\t.long\t_%s_strings_start - _%s_blob_start /* off_dt_strings */\n",
+		symprefix, symprefix);
+	fprintf(f, "\t.long\t_%s_reserve_map - _%s_blob_start /* off_dt_strings */\n",
+		symprefix, symprefix);
+	fprintf(f, "\t.long\t%d /* version */\n", vi->version);
+	fprintf(f, "\t.long\t%d /* last_comp_version */\n",
+		vi->last_comp_version);
+
+	if (vi->flags & FTF_BOOTCPUID)
+		fprintf(f, "\t.long\t0xdeadbeef\t/*boot_cpuid_phys*/\n");
+
+	if (vi->flags & FTF_STRTABSIZE)
+		fprintf(f, "\t.long\t_%s_strings_end - _%s_strings_start\t/* size_dt_strings */\n",
+			symprefix, symprefix);
+
+	emit_label(f, symprefix, "reserve_map");
+	/* reserve map entry for the device tree itself */
+	fprintf(f, "\t.long\t0, _%s_blob_start\n", symprefix);
+	fprintf(f, "\t.long\t0, _%s_blob_end - _%s_blob_start\n",
+		symprefix, symprefix);
+	for (i = 0; i < reservenum+1; i++) {
+		fprintf(f, "\t.llong\t0\n");
+		fprintf(f, "\t.llong\t0\n");
+	}
+
+	emit_label(f, symprefix, "struct_start");
+	flatten_tree(tree, &asm_emitter, f, &strbuf, vi);
+	fprintf(f, "\t.long\tOF_DT_END\n");
+	emit_label(f, symprefix, "struct_end");
+
+	emit_label(f, symprefix, "strings_start");
+	dump_stringtable_asm(f, strbuf);
+	emit_label(f, symprefix, "strings_end");
+
+	emit_label(f, symprefix, "blob_end");
+
+	data_free(strbuf);
+}
+
+struct inbuf {
+	char *base, *limit, *ptr;
+};
+
+static void inbuf_init(struct inbuf *inb, void *base, void *limit)
+{
+	inb->base = base;
+	inb->limit = limit;
+	inb->ptr = inb->base;
+}
+
+static void flat_read_chunk(struct inbuf *inb, void *p, int len)
+{
+	if ((inb->ptr + len) > inb->limit)
+		die("Premature end of data parsing flat device tree\n");
+
+	memcpy(p, inb->ptr, len);
+
+	inb->ptr += len;
+}
+
+static u32 flat_read_word(struct inbuf *inb)
+{
+	u32 val;
+
+	assert(((inb->ptr - inb->base) % sizeof(val)) == 0);
+
+	flat_read_chunk(inb, &val, sizeof(val));
+
+	return be32_to_cpu(val);
+}
+
+static void flat_realign(struct inbuf *inb, int align)
+{
+	int off = inb->ptr - inb->base;
+
+	inb->ptr = inb->base + ALIGN(off, align);
+	if (inb->ptr > inb->limit)
+		die("Premature end of data parsing flat device tree\n");
+}
+
+static char *flat_read_string(struct inbuf *inb)
+{
+	int len = 0;
+	char *p = inb->ptr;
+	char *str;
+
+	do {
+		if (p >= inb->limit)
+			die("Premature end of data parsing flat device tree\n");
+		len++;
+	} while ((*p++) != '\0');
+
+	str = strdup(inb->ptr);
+
+	inb->ptr += len;
+
+	flat_realign(inb, sizeof(u32));
+
+	return str;
+}
+
+static struct data flat_read_data(struct inbuf *inb, int len)
+{
+	struct data d = empty_data;
+
+	if (len == 0)
+		return empty_data;
+
+	d = data_grow_for(d, len);
+	d.len = len;
+
+	flat_read_chunk(inb, d.val, len);
+
+	flat_realign(inb, sizeof(u32));
+
+	return d;
+}
+
+static char *flat_read_stringtable(struct inbuf *inb, int offset)
+{
+	char *p;
+
+	p = inb->base + offset;
+	while (1) {
+		if (p >= inb->limit)
+			die("String offset %d overruns string table\n");
+
+		if (*p == '\0')
+			break;
+
+		p++;
+	}
+
+	return strdup(inb->base + offset);
+}
+
+struct property *flat_read_property(struct inbuf *dtbuf, struct inbuf *strbuf,
+				    int flags)
+{
+	u32 proplen, stroff;
+	char *name;
+	struct data val;
+
+	proplen = flat_read_word(dtbuf);
+	stroff = flat_read_word(dtbuf);
+
+	name = flat_read_stringtable(strbuf, stroff);
+
+	if ((flags & FTF_VARALIGN) && (proplen >= 8))
+		flat_realign(dtbuf, 8);
+
+	val = flat_read_data(dtbuf, proplen);
+
+	return build_property(name, val);
+}
+
+static char *nodename_from_path(char *ppath, char *cpath)
+{
+	char *lslash;
+	int plen;
+
+	lslash = strrchr(cpath, '/');
+	if (! lslash)
+		return NULL;
+
+	plen = lslash - cpath;
+
+	if (streq(cpath, "/") && streq(ppath, ""))
+		return "";
+
+	if ((plen == 0) && streq(ppath, "/"))
+		return strdup(lslash+1);
+
+	if (strncmp(ppath, cpath, plen) != 0)
+		return NULL;
+	
+	return strdup(lslash+1);
+}
+
+static const char PROPCHAR[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789,._+*#?-";
+static const char UNITCHAR[] = "0123456789abcdef,";
+
+static int check_node_name(char *name)
+{
+	char *atpos;
+	int basenamelen;
+
+	atpos = strrchr(name, '@');
+
+	if (atpos)
+		basenamelen = atpos - name;
+	else
+		basenamelen = strlen(name);
+
+	if (strspn(name, PROPCHAR) < basenamelen)
+		return -1;
+
+	if (atpos
+	    && ((basenamelen + 1 + strspn(atpos+1, UNITCHAR)) < strlen(name)))
+		return -1;
+
+	return basenamelen;
+}
+
+static struct node *unflatten_tree(struct inbuf *dtbuf,
+				   struct inbuf *strbuf,
+				   char *parent_path, int flags)
+{
+	struct node *node;
+	u32 val;
+
+	node = build_node(NULL, NULL);
+
+	if (flags & FTF_FULLPATH) {
+		node->fullpath = flat_read_string(dtbuf);
+		node->name = nodename_from_path(parent_path, node->fullpath);
+
+		if (! node->name)
+			die("Path \"%s\" is not valid as a child of \"%s\"\n",
+			    node->fullpath, parent_path);
+	} else {
+		node->name = flat_read_string(dtbuf);
+		node->fullpath = join_path(parent_path, node->name);
+	}
+	
+	node->basenamelen = check_node_name(node->name);
+	if (node->basenamelen < 0) {
+		fprintf(stderr, "Warning \"%s\" has incorrect format\n", node->name);
+	}
+
+	do {
+		struct property *prop;
+		struct node *child;
+
+		val = flat_read_word(dtbuf);
+		switch (val) {
+		case OF_DT_PROP:
+			prop = flat_read_property(dtbuf, strbuf, flags);
+			add_property(node, prop);
+			break;
+
+		case OF_DT_BEGIN_NODE:
+			child = unflatten_tree(dtbuf,strbuf, node->fullpath,
+					       flags);
+			add_child(node, child);
+			break;
+
+		case OF_DT_END_NODE:
+			break;
+
+		case OF_DT_END:
+			die("Premature OF_DT_END in device tree blob\n");
+			break;
+
+		default:
+			die("Invalid opcode word %08x in device tree blob\n",
+			    val);
+		}
+	} while (val != OF_DT_END_NODE);
+
+	return node;
+}
+
+struct node *dt_from_blob(FILE *f)
+{
+	u32 magic, totalsize, off_dt, off_str, version, size_str;
+	int rc;
+	char *blob;
+	struct boot_param_header *bph;
+	char *p;
+	struct inbuf dtbuf, strbuf;
+	int sizeleft;
+	struct node *tree;
+	u32 val;
+	int flags = 0;
+
+	rc = fread(&magic, sizeof(magic), 1, f);
+	if (ferror(f))
+		die("Error reading DT blob magic number: %s\n",
+		    strerror(errno));
+	if (rc < 1) {
+		if (feof(f))
+			die("EOF reading DT blob magic number\n");
+		else
+			die("Mysterious short read reading magic number\n");
+	}
+
+	magic = be32_to_cpu(magic);
+	if (magic != OF_DT_HEADER)
+		die("Blob has incorrect magic number\n");
+
+	rc = fread(&totalsize, sizeof(totalsize), 1, f);
+	if (ferror(f))
+		die("Error reading DT blob size: %s\n", strerror(errno));
+	if (rc < 1) {
+		if (feof(f))
+			die("EOF reading DT blob size\n");
+		else
+			die("Mysterious short read reading blob size\n");
+	}
+
+	totalsize = be32_to_cpu(totalsize);
+	if (totalsize < BPH_V1_SIZE)
+		die("DT blob size (%d) is too small\n", totalsize);
+
+	blob = xmalloc(totalsize);
+
+	bph = (struct boot_param_header *)blob;
+	bph->magic = cpu_to_be32(magic);
+	bph->totalsize = cpu_to_be32(totalsize);
+
+	sizeleft = totalsize - sizeof(magic) - sizeof(totalsize);
+	p = blob + sizeof(magic)  + sizeof(totalsize);
+
+	while (sizeleft) {
+		if (feof(f))
+			die("EOF before reading %d bytes of DT blob\n",
+			    totalsize);
+
+		rc = fread(p, 1, sizeleft, f);
+		if (ferror(f))
+			die("Error reading DT blob: %s\n",
+			    strerror(errno));
+
+		sizeleft -= rc;
+		p += rc;
+	}
+
+	off_dt = be32_to_cpu(bph->off_dt_struct);
+	off_str = be32_to_cpu(bph->off_dt_strings);
+	version = be32_to_cpu(bph->version);
+
+	fprintf(stderr, "\tmagic:\t\t\t0x%x\n", magic);
+	fprintf(stderr, "\ttotalsize:\t\t%d\n", totalsize);
+	fprintf(stderr, "\toff_dt_struct:\t\t0x%x\n", off_dt);
+	fprintf(stderr, "\toff_dt_strings:\t\t0x%x\n", off_str);
+	fprintf(stderr, "\toff_mem_rsvmap:\t\t0x%x\n",
+		be32_to_cpu(bph->off_mem_rsvmap));
+	fprintf(stderr, "\tversion:\t\t0x%x\n", version );
+	fprintf(stderr, "\tlast_comp_version:\t0x%x\n",
+		be32_to_cpu(bph->last_comp_version));
+
+	if (off_dt >= totalsize)
+		die("DT structure offset exceeds total size\n");
+
+	if (off_str > totalsize)
+		die("String table offset exceeds total size\n");
+
+	if (version >= 2)
+		fprintf(stderr, "\tboot_cpuid_phys:\t0x%x\n",
+			be32_to_cpu(bph->boot_cpuid_phys));
+
+	if (version >= 3) {
+		size_str = be32_to_cpu(bph->size_dt_strings);
+		fprintf(stderr, "\tsize_dt_strings:\t%d\n", size_str);
+		if (off_str+size_str > totalsize)
+			die("String table extends past total size\n");
+	}
+			
+	if (version < 0x10) {
+		flags |= FTF_FULLPATH | FTF_NAMEPROPS | FTF_VARALIGN;
+	}
+
+	inbuf_init(&dtbuf, blob + off_dt, blob + totalsize);
+	inbuf_init(&strbuf, blob + off_str, blob + totalsize);
+
+	if (version >= 3)
+		strbuf.limit = strbuf.base + size_str;
+
+	val = flat_read_word(&dtbuf);
+
+	if (val != OF_DT_BEGIN_NODE)
+		die("Device tree blob doesn't begin with OF_DT_BEGIN_NODE\n");
+
+	tree = unflatten_tree(&dtbuf, &strbuf, "", flags);
+
+	val = flat_read_word(&dtbuf);
+	if (val != OF_DT_END)
+		die("Device tree blob doesn't end with OF_DT_END\n");
+
+	free(blob);
+
+	return tree;
+}
diff --git a/fstree.c b/fstree.c
new file mode 100644
index 0000000..5fe8e40
--- /dev/null
+++ b/fstree.c
@@ -0,0 +1,92 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include "dtc.h"
+
+#include <dirent.h>
+#include <sys/stat.h>
+
+static struct node *read_fstree(char *dirname)
+{
+	DIR *d;
+	struct dirent *de;
+	struct stat st;
+	struct node *tree;
+
+	d = opendir(dirname);
+	if (! d)
+		die("opendir(): %s\n", strerror(errno));
+
+	tree = build_node(NULL, NULL);
+
+	while ((de = readdir(d)) != NULL) {
+		char *tmpnam;
+
+		if (streq(de->d_name, ".")
+		    || streq(de->d_name, ".."))
+			continue;
+
+		tmpnam = join_path(dirname, de->d_name);
+		
+		if (lstat(tmpnam, &st) < 0)
+			die("stat(%s): %s\n", tmpnam, strerror(errno));
+
+		if (S_ISREG(st.st_mode)) {
+			struct property *prop;
+			FILE *pfile;
+
+			pfile = fopen(tmpnam, "r");
+			if (! pfile) {
+				fprintf(stderr,
+					"WARNING: Cannot open %s: %s\n",
+					tmpnam, strerror(errno));
+			} else {
+				prop = build_property(strdup(de->d_name),
+						      data_copy_file(pfile,
+								     st.st_size));
+				add_property(tree, prop);
+				fclose(pfile);
+			}
+		} else if (S_ISDIR(st.st_mode)) {
+			struct node *newchild;
+
+			newchild = read_fstree(tmpnam);
+			newchild = name_node(newchild, strdup(de->d_name));
+			add_child(tree, newchild);
+		}
+
+		free(tmpnam);
+	}
+
+	return tree;
+}
+
+struct node *dt_from_fs(char *dirname)
+{
+	struct node *tree;
+
+	tree = read_fstree(dirname);
+	tree = name_node(tree, "");
+
+	fill_fullpaths(tree, "");
+
+	return tree;
+}
+
diff --git a/livetree.c b/livetree.c
new file mode 100644
index 0000000..227b5e8
--- /dev/null
+++ b/livetree.c
@@ -0,0 +1,590 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include "dtc.h"
+
+/*
+ * Tree building functions
+ */
+
+struct property *build_property(char *name, struct data val)
+{
+	struct property *new = xmalloc(sizeof(*new));
+
+	new->name = name;
+	new->val = val;
+
+	new->next = NULL;
+
+	return new;
+}
+
+struct property *build_empty_property(char *name)
+{
+	struct property *new = xmalloc(sizeof(*new));
+
+	new->name = name;
+	new->val.len = 0;
+	new->val.val = NULL;
+
+	new->next = NULL;
+
+	return new;
+}
+
+struct property *chain_property(struct property *first, struct property *list)
+{
+	assert(first->next == NULL);
+	
+	first->next = list;
+	return first;      
+}
+
+struct node *build_node(struct property *proplist, struct node *children)
+{
+	struct node *new = xmalloc(sizeof(*new));
+	struct node *child;
+
+	memset(new, 0, sizeof(*new));
+
+	new->proplist = proplist;
+	new->children = children;
+
+	for_each_child(new, child) {
+		child->parent = new;
+	}
+
+	return new;
+}
+
+struct node *name_node(struct node *node, char *name)
+{
+	assert(node->name == NULL);
+
+	node->name = name;
+	return node;
+}
+
+struct node *chain_node(struct node *first, struct node *list)
+{
+	assert(first->next_sibling == NULL);
+
+	first->next_sibling = list;
+	return first;
+}
+
+void add_property(struct node *node, struct property *prop)
+{
+	node->proplist = chain_property(prop, node->proplist);
+}
+
+void add_child(struct node *parent, struct node *child)
+{
+	parent->children = chain_node(child, parent->children);
+}
+
+
+/*
+ * Tree accessor functions
+ */
+
+char *get_unitname(struct node *node)
+{
+	if (node->name[node->basenamelen] == '\0')
+		return "";
+	else
+		return node->name + node->basenamelen + 1;
+}
+
+struct property *get_property(struct node *node, char *propname)
+{
+	struct property *prop;
+
+	for_each_property(node, prop)
+		if (streq(prop->name, propname))
+			return prop;
+
+	return NULL;
+}
+
+static cell_t propval_cell(struct property *prop)
+{
+	assert(prop->val.len == sizeof(cell_t));
+	return be32_to_cpu(*((cell_t *)prop->val.val));
+}
+
+static struct node *get_subnode(struct node *node, char *nodename)
+{
+	struct node *child;
+
+	for_each_child(node, child) {
+		if (strcmp(child->name, nodename) == 0)
+			return child;
+	}
+
+	return NULL;
+}
+
+static struct node *get_node_by_phandle(struct node *tree, cell_t phandle)
+{
+	struct node *child, *node;	
+
+	assert((phandle != 0) && (phandle != -1));
+
+	if (tree->phandle == phandle)
+		return tree;
+
+	for_each_child(tree, child) {
+		node = get_node_by_phandle(child, phandle);
+		if (node)
+			return node;
+	}
+
+	return NULL;
+}
+/*
+ * Tree checking functions
+ */
+
+#define ERRMSG(...) fprintf(stderr, "ERROR: " __VA_ARGS__)
+#define WARNMSG(...) fprintf(stderr, "Warning: " __VA_ARGS__)
+
+static int must_be_one_cell(struct property *prop, struct node *node)
+{
+	if (prop->val.len != sizeof(cell_t)) {
+		ERRMSG("\"%s\" property in %s has the wrong length (should be 1 cell)\n",
+		       prop->name, node->fullpath);
+		return 0;
+	}
+
+	return 1;
+}
+
+static int must_be_cells(struct property *prop, struct node *node)
+{
+	if ((prop->val.len % sizeof(cell_t)) != 0) {
+		ERRMSG("\"%s\" property in %s is not a multiple of cell size\n",
+		       prop->name, node->fullpath);
+		return 0;
+	}
+
+	return 1;
+}
+
+static int must_be_string(struct property *prop, struct node *node)
+{
+	if (! data_is_one_string(prop->val)) {
+		ERRMSG("\"%s\" property in %s is not a string\n",
+		       prop->name, node->fullpath);
+		return 0;
+	}
+
+	return 1;
+}
+
+static int name_prop_check(struct property *prop, struct node *node)
+{
+	if ((prop->val.len != node->basenamelen+1)
+	    || (strncmp(prop->val.val, node->name, node->basenamelen) != 0)) {
+		ERRMSG("name property \"%s\" does not match node basename in %s\n",
+		       prop->val.val,
+		       node->fullpath);
+		return 0;
+	}
+
+	return 1;
+}
+
+struct {
+	char *propname;
+	int (*check_fn)(struct property *prop, struct node *node);
+} prop_checker_table[] = {
+	{"name", must_be_string},
+	{"name", name_prop_check},
+	{"linux,phandle", must_be_one_cell},
+	{"#address-cells", must_be_one_cell},
+	{"#size-cells", must_be_one_cell},
+	{"reg", must_be_cells},
+	{"model", must_be_string},
+	{"device_type", must_be_string},
+};
+
+#define DO_ERR(...) do {ERRMSG(__VA_ARGS__); ok = 0; } while (0)
+
+static int check_properties(struct node *node)
+{
+	struct property *prop, *prop2;
+	int ok = 1;
+
+	for_each_property(node, prop) {
+		int i;
+
+		/* check for duplicates */
+		/* FIXME: do this more efficiently */
+		for (prop2 = prop->next; prop2; prop2 = prop2->next) {
+			if (streq(prop->name, prop2->name)) {
+				DO_ERR("Duplicate propertyname %s in node %s\n",
+					prop->name, node->fullpath);
+			}
+		}
+			
+
+		/* check name length */
+		if (strlen(prop->name) > MAX_PROPNAME_LEN)
+			DO_ERR("Property name %s is too long in %s\n",
+			      prop->name, node->fullpath);
+			
+		/* check this property */
+		for (i = 0; i < ARRAY_SIZE(prop_checker_table); i++) {
+			if (streq(prop->name, prop_checker_table[i].propname))
+				if (! prop_checker_table[i].check_fn(prop, node)) {
+					ok = 0;
+					break;
+				}
+		}
+	}
+
+	return ok;
+}
+
+static int check_node_name(struct node *node)
+{
+	int ok = 1;
+	int len = strlen(node->name);
+
+	if (len == 0 && node->parent)
+		DO_ERR("Empty, non-root nodename at %s\n", node->fullpath);
+
+	if (len > MAX_NODENAME_LEN)
+		DO_ERR("Overlength nodename at %s\n", node->fullpath);
+
+
+	return ok;
+}
+
+static int check_structure(struct node *tree)
+{
+	struct node *child, *child2;
+	int ok = 1;
+
+	if (! check_node_name(tree))
+		ok = 0;
+
+	if (! check_properties(tree))
+		ok = 0;
+
+	for_each_child(tree, child) {
+		/* Check for duplicates */
+
+		for (child2 = child->next_sibling;
+		     child2;
+		     child2 = child2->next_sibling) {
+			if (streq(child->name, child2->name))
+				DO_ERR("Duplicate node name %s\n",
+					child->fullpath);
+		}
+		if (! check_structure(child))
+			ok = 0;
+	}
+
+	return ok;
+}
+
+#define CHECK_HAVE(node, propname) \
+	do { \
+		if (! (prop = get_property((node), (propname)))) \
+			DO_ERR("Missing \"%s\" property in %s\n", (propname), \
+				(node)->fullpath); \
+	} while (0);
+
+#define CHECK_HAVE_WARN(node, propname) \
+	do { \
+		if (! (prop  = get_property((node), (propname)))) \
+			WARNMSG("%s has no \"%s\" property\n", \
+				(node)->fullpath, (propname)); \
+	} while (0)
+
+#define CHECK_HAVE_STRING(node, propname) \
+	do { \
+		CHECK_HAVE((node), (propname)); \
+		if (prop && !data_is_one_string(prop->val)) \
+			DO_ERR("\"%s\" property in %s is not a string\n", \
+				(propname), (node)->fullpath); \
+	} while (0)
+
+#define CHECK_HAVE_STREQ(node, propname, value) \
+	do { \
+		CHECK_HAVE_STRING((node), (propname)); \
+		if (prop && !streq(prop->val.val, (value))) \
+			DO_ERR("%s has wrong %s, %s (should be %s\n", \
+				(node)->fullpath, (propname), \
+				prop->val.val, (value)); \
+	} while (0)
+		 
+#define CHECK_HAVE_ONECELL(node, propname) \
+	do { \
+		CHECK_HAVE((node), (propname)); \
+		if (prop && (prop->val.len != sizeof(cell_t))) \
+			DO_ERR("\"%s\" property in %s has wrong size %d (should be 1 cell)\n", (propname), (node)->fullpath, prop->val.len); \
+	} while (0)
+
+#define CHECK_HAVE_WARN_ONECELL(node, propname) \
+	do { \
+		CHECK_HAVE_WARN((node), (propname)); \
+		if (prop && (prop->val.len != sizeof(cell_t))) \
+			DO_ERR("\"%s\" property in %s has wrong size %d (should be 1 cell)\n", (propname), (node)->fullpath, prop->val.len); \
+	} while (0)
+
+#define CHECK_HAVE_WARN_PHANDLE(xnode, propname, root) \
+	do { \
+		struct node *ref; \
+		CHECK_HAVE_WARN_ONECELL((xnode), (propname)); \
+		if (prop) {\
+			ref = get_node_by_phandle((root), propval_cell(prop)); \
+			if (! ref) \
+				DO_ERR("\"%s\" property in %s refers to non-existant phandle %x\n", (propname), (xnode)->fullpath, propval_cell(prop)); \
+		} \
+	} while (0)
+
+#define CHECK_HAVE_WARN_STRING(node, propname) \
+	do { \
+		CHECK_HAVE_WARN((node), (propname)); \
+		if (prop && !data_is_one_string(prop->val)) \
+			DO_ERR("\"%s\" property in %s is not a string\n", \
+				(propname), (node)->fullpath); \
+	} while (0)
+
+static int check_root(struct node *root)
+{
+	struct property *prop;
+	int ok = 1;
+
+	CHECK_HAVE_STRING(root, "model");
+
+	CHECK_HAVE(root, "#address-cells");
+	CHECK_HAVE(root, "#size-cells");
+
+	CHECK_HAVE_WARN(root, "compatible");
+
+	return ok;
+}
+
+static int check_cpus(struct node *root)
+{
+	struct node *cpus, *cpu;
+	struct property *prop;
+	struct node *bootcpu = NULL;
+	int ok = 1;
+
+	cpus = get_subnode(root, "cpus");
+	if (! cpus) {
+		ERRMSG("Missing /cpus node\n");
+		return 0;
+	}
+
+	CHECK_HAVE_WARN(cpus, "#address-cells");
+	CHECK_HAVE_WARN(cpus, "#size-cells");
+
+	for_each_child(cpus, cpu) {
+		CHECK_HAVE_STREQ(cpu, "device_type", "cpu");
+
+		if (cpu->addr_cells != 1)
+			DO_ERR("%s has bad #address-cells value %d (should be 1)\n",
+			       cpu->fullpath, cpu->addr_cells);
+		if (cpu->size_cells != 0)
+			DO_ERR("%s has bad #size-cells value %d (should be 0)\n",
+			       cpu->fullpath, cpu->size_cells);
+
+		CHECK_HAVE_ONECELL(cpu, "reg");
+		if (prop) {
+			cell_t unitnum;
+			char *eptr;
+
+			unitnum = strtol(get_unitname(cpu), &eptr, 16);
+			if (*eptr)
+				WARNMSG("%s has bad format unit name %s (should be CPU number\n",
+					cpu->fullpath, get_unitname(cpu));
+			else if (unitnum != propval_cell(prop))
+				WARNMSG("%s unit name \"%s\" does not match \"reg\" property <%x>\n",
+				       cpu->fullpath, get_unitname(cpu),
+				       propval_cell(prop));
+		}
+
+/* 		CHECK_HAVE_ONECELL(cpu, "d-cache-line-size"); */
+/* 		CHECK_HAVE_ONECELL(cpu, "i-cache-line-size"); */
+		CHECK_HAVE_ONECELL(cpu, "d-cache-size");
+		CHECK_HAVE_ONECELL(cpu, "i-cache-size");
+
+		CHECK_HAVE_WARN_ONECELL(cpu, "clock-frequency");
+		CHECK_HAVE_WARN_ONECELL(cpu, "timebase-frequency");
+
+		prop = get_property(cpu, "linux,boot-cpu");
+		if (prop) {
+			if (prop->val.len)
+				WARNMSG("\"linux,boot-cpu\" property in %s is non-empty\n",
+					cpu->fullpath);
+			if (bootcpu)
+				DO_ERR("Multiple boot cpus (%s and %s)\n",
+				       bootcpu->fullpath, cpu->fullpath);
+			else
+				bootcpu = cpu;
+		}
+	}
+
+	if (! bootcpu)
+		WARNMSG("No cpu has \"linux,boot-cpu\" property\n");
+
+	return ok;	
+}
+
+static int check_memory(struct node *root)
+{
+	struct node *mem;
+	struct property *prop;
+	int nnodes = 0;
+	int ok = 1;
+
+	for_each_child(root, mem) {
+		if (strncmp(mem->name, "memory", mem->basenamelen) != 0)
+			continue;
+
+		nnodes++;
+
+		CHECK_HAVE_STREQ(mem, "device_type", "memory");
+		CHECK_HAVE(mem, "reg");
+	}
+
+	if (nnodes == 0) {
+		ERRMSG("No memory nodes\n");
+		return 0;
+	}
+
+	return ok;	
+}
+
+static int check_chosen(struct node *root)
+{
+	struct node *chosen;
+	struct property *prop;
+	int ok = 1;
+
+	chosen = get_subnode(root, "chosen");
+	if (! chosen) {
+		ERRMSG("Missing /chosen node\n");
+		return 0;
+	}
+
+	CHECK_HAVE_ONECELL(chosen, "linux,platform");
+
+	CHECK_HAVE_WARN_STRING(chosen, "bootargs");
+	CHECK_HAVE_WARN_STRING(chosen, "linux,stdout-path");
+	CHECK_HAVE_WARN_PHANDLE(chosen, "interrupt-controller", root);
+
+	return ok;	
+}
+
+static int check_addr_size_reg(struct node *node,
+			       int p_addr_cells, int p_size_cells)
+{
+	int addr_cells = p_addr_cells;
+	int size_cells = p_size_cells;
+	struct property *prop;
+	struct node *child;
+	int ok = 1;
+
+	node->addr_cells = addr_cells;
+	node->size_cells = size_cells;
+
+	prop = get_property(node, "reg");
+	if (prop) {
+		int len = prop->val.len / 4;
+
+		if ((len % (addr_cells+size_cells)) != 0)
+			DO_ERR("\"reg\" property in %s has invalid length (%d) for given #address-cells (%d) and #size-cells (%d)\n",
+			       node->fullpath, prop->val.len,
+			       addr_cells, size_cells);
+	}
+
+	prop = get_property(node, "#address-cells");
+	if (prop)
+		addr_cells = propval_cell(prop);
+
+	prop = get_property(node, "#size-cells");
+	if (prop)
+		size_cells = propval_cell(prop);
+
+	for_each_child(node, child) {
+		ok = ok && check_addr_size_reg(child, addr_cells, size_cells);
+	}
+
+	return ok;
+}
+
+static int check_phandles(struct node *root, struct node *node)
+{
+	struct property *prop;
+	struct node *child, *other;
+	cell_t phandle;
+	int ok = 1;
+
+	prop = get_property(node, "linux,phandle");
+	if (prop) {
+		phandle = propval_cell(prop);
+		if ((phandle == 0) || (phandle == -1)) {
+			DO_ERR("%s has invalid linux,phandle %x\n",
+			       node->fullpath, phandle);
+		} else {
+			other = get_node_by_phandle(root, phandle);
+			if (other)
+				DO_ERR("%s has duplicated phandle %x (seen before at %s)\n",
+				       node->fullpath, phandle, other->fullpath);
+
+			node->phandle = phandle;
+		}
+	}
+
+	for_each_child(node, child)
+		ok = ok && check_phandles(root, child);
+
+	return 1;
+}
+
+int check_device_tree(struct node *dt)
+{
+	int ok = 1;
+
+	if (! check_structure(dt))
+		return 0;
+
+	ok = ok && check_addr_size_reg(dt, -1, -1);
+	ok = ok && check_phandles(dt, dt);
+
+	if (! ok)
+		return 0;
+
+	ok = ok && check_root(dt);
+	ok = ok && check_cpus(dt);
+	ok = ok && check_memory(dt);
+	ok = ok && check_chosen(dt);
+	if (! ok)
+		return 0;
+
+	return 1;
+}
diff --git a/test.dts b/test.dts
new file mode 100644
index 0000000..bda4288
--- /dev/null
+++ b/test.dts
@@ -0,0 +1,39 @@
+/ {
+	model = "MyBoardName";
+	compatible = "MyBoardFamilyName";
+	#address-cells = <2>;
+	#size-cells = <2>;
+
+	cpus {
+		linux,phandle = <1>;
+		#address-cells = <1>;
+		#size-cells = <0>;
+		PowerPC,970@0 {
+			name = "PowerPC,970";
+			device_type = "cpu";
+			reg = <0>;
+			clock-frequency = <5f5e1000>;
+			linux,boot-cpu;
+			linux,phandle = <2>;
+		};
+
+	};
+
+	randomnode {
+		string = "\xff\0stuffstuff\t\t\t\n\n\n\n";
+		blob = [0a 0b 0c 0d de ea ad be ef];
+	};
+
+	memory@0 {
+		device_type = "memory";
+		reg = <00000000 00000000 00000000 20000000>;
+		linux,phandle = <3>;
+	};
+
+	chosen {
+		bootargs = "root=/dev/sda2";
+		linux,platform = <00000600>;
+		linux,phandle = <4>;
+	};
+
+};
diff --git a/tests/Makefile b/tests/Makefile
new file mode 100644
index 0000000..912f832
--- /dev/null
+++ b/tests/Makefile
@@ -0,0 +1,12 @@
+DTC = ../dtc
+VG_DTC = valgrind --tool=memcheck ../dtc
+
+check: all
+	./run_all_tests.sh
+
+all:
+
+clean:
+	rm -f *~
+
+
diff --git a/tests/run_all_tests.sh b/tests/run_all_tests.sh
new file mode 100644
index 0000000..a8b7c3e
--- /dev/null
+++ b/tests/run_all_tests.sh
@@ -0,0 +1,2 @@
+#! /bin/sh
+
diff --git a/treesource.c b/treesource.c
new file mode 100644
index 0000000..6b0c974
--- /dev/null
+++ b/treesource.c
@@ -0,0 +1,140 @@
+/*
+ * (C) Copyright David Gibson <dwg@au1.ibm.com>, IBM Corporation.  2005.
+ *
+ * 
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ *  General Public License for more details.
+ *                                                                       
+ *  You should have received a copy of the GNU General Public License    
+ *  along with this program; if not, write to the Free Software          
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 
+ *                                                                   USA 
+ */
+
+#include "dtc.h"
+
+struct node *device_tree;
+
+extern FILE *yyin;
+extern int yyparse(void);
+
+struct node *dt_from_source(FILE *f)
+{
+	yyin = f;
+	if (yyparse() != 0)
+		return NULL;
+
+	fill_fullpaths(device_tree, "");
+
+	return device_tree;
+}
+
+static void write_prefix(FILE *f, int level)
+{
+	int i;
+
+	for (i = 0; i < level; i++)
+		fputc('\t', f);
+}
+
+enum proptype {
+	PROP_EMPTY,
+	PROP_STRING,
+	PROP_CELLS,
+	PROP_BYTES,
+};
+
+static enum proptype guess_type(struct property *prop)
+{
+	int len = prop->val.len;
+	char *p = prop->val.val;
+	int nnoprint = 0;
+	int i;
+
+	if (len == 0)
+		return PROP_EMPTY;
+
+	for (i = 0; i < len; i++) {
+		if (! isprint(p[i]))
+			nnoprint++;
+	}
+
+	if ((nnoprint == 1) && (p[len-1] == '\0'))
+		return PROP_STRING;
+	else if ((len % sizeof(cell_t)) == 0)
+		return PROP_CELLS;
+	else
+		return PROP_BYTES;
+		
+}
+
+void write_tree_source(FILE *f, struct node *tree, int level)
+{
+	struct property *prop;
+	struct node *child;
+
+	write_prefix(f, level);
+	if (tree->name && (*tree->name))
+		fprintf(f, "%s {\n", tree->name);
+	else
+		fprintf(f, "/ {\n");
+
+	for_each_property(tree, prop) {
+		cell_t *cp;
+		char *bp;
+		void *propend;
+		enum proptype type;
+
+		write_prefix(f, level);
+		fprintf(f, "\t%s", prop->name);
+		type = guess_type(prop);
+		propend = prop->val.val + prop->val.len;
+
+		switch (type) {
+		case PROP_EMPTY:
+			fprintf(f, ";\n");
+			break;
+
+		case PROP_STRING:
+			fprintf(f, " = \"%s\";\n", (char *)prop->val.val);
+			break;
+
+		case PROP_CELLS:
+			fprintf(f, " = <");
+			cp = (cell_t *)prop->val.val;
+			for (;;) {
+				fprintf(f, "%x", be32_to_cpu(*cp++));
+				if ((void *)cp >= propend)
+					break;
+				fprintf(f, " ");
+			}
+			fprintf(f, ">;\n");
+			break;
+
+		case PROP_BYTES:
+			fprintf(f, " = [");
+			bp = prop->val.val;
+			for (;;) {
+				fprintf(f, "%02hhx", *bp++);
+				if ((void *)bp >= propend)
+					break;
+				fprintf(f, " ");
+			}
+			fprintf(f, "];\n");
+			break;
+		}
+	}
+	for_each_child(tree, child) {
+		fprintf(f, "\n");
+		write_tree_source(f, child, level+1);
+	}
+	write_prefix(f, level);
+	fprintf(f, "};\n");
+}