Add mkfs.ubifs

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

23 files changed, 6878 insertions, 0 deletions

diff --git a/mkfs.ubifs/COPYING b/mkfs.ubifs/COPYING
new file mode 100644
index 0000000..60549be
--- /dev/null
+++ b/mkfs.ubifs/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) 19yy  <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) 19yy 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/mkfs.ubifs/Makefile b/mkfs.ubifs/Makefile
new file mode 100644
index 0000000..9487c14
--- /dev/null
+++ b/mkfs.ubifs/Makefile
@@ -0,0 +1,23 @@
+DESTDIR := /usr/local
+SBINDIR=/usr/sbin
+ALL_SOURCES=*.[ch] hashtable/*.[ch]
+CFLAGS := $(CFLAGS) -Wall -O0 -ggdb
+LDFLAGS := $(LDFLAGS) -lz -llzo2 -lm -luuid
+TARGETS = mkfs.ubifs
+
+all: $(TARGETS)
+
+mkfs.ubifs: crc16.o crc32.o lpt.o compr.o hashtable/hashtable.o \
+            hashtable/hashtable_itr.o devtable.o
+
+clean:
+	rm -f *.o $(TARGETS) cscope.*
+
+cscope:
+	@echo $(ALL_SOURCES) > cscope.files
+	@cscope -bR
+	@rm cscope.files
+
+install: ${TARGETS}
+	mkdir -p ${DESTDIR}/${SBINDIR}
+	install -m0755 ${TARGETS} ${DESTDIR}/${SBINDIR}/
diff --git a/mkfs.ubifs/README b/mkfs.ubifs/README
new file mode 100644
index 0000000..4fbaa7d
--- /dev/null
+++ b/mkfs.ubifs/README
@@ -0,0 +1,10 @@
+UBIFS File System - Make File System program
+
+* crc16.h and crc16.c were copied from the linux kernel.
+* crc32.h and crc32.c were copied from mtd-utils and amended.
+* ubifs-media.h is fs/ubifs/ubifs-media.h from the linux kernel
+* ubifs.h is a selection of definitions from fs/ubifs/ubifs.h from the linux kernel.
+* key.h is copied from fs/ubifs/key.h from the linux kernel.
+* defs.h is a bunch of definitions to smooth things over.
+* lpt.c is a selection of functions copied from fs/ubifs/lpt.c from the linux kernel, and amended.
+* hashtable/* was downloaded from http://www.cl.cam.ac.uk/~cwc22/hashtable/
diff --git a/mkfs.ubifs/compr.c b/mkfs.ubifs/compr.c
new file mode 100644
index 0000000..285354e
--- /dev/null
+++ b/mkfs.ubifs/compr.c
@@ -0,0 +1,154 @@
+/*
+ * Copyright (C) 2008 Nokia Corporation.
+ * Copyright (C) 2008 University of Szeged, Hungary
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy
+ *          Adrian Hunter
+ *          Zoltan Sogor
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <stdint.h>
+#include <string.h>
+#include <zlib.h>
+#include <lzo/lzo1x.h>
+#include <linux/types.h>
+
+#include "compr.h"
+#include "ubifs-media.h"
+
+static void *lzo_mem;
+static unsigned long long errcnt = 0;
+
+#define DEFLATE_DEF_LEVEL     Z_DEFAULT_COMPRESSION
+#define DEFLATE_DEF_WINBITS   11
+#define DEFLATE_DEF_MEMLEVEL  8
+
+static int zlib_deflate(void *in_buf, size_t in_len, void *out_buf,
+			size_t *out_len)
+{
+	z_stream strm;
+
+	strm.zalloc = NULL;
+	strm.zfree = NULL;
+
+	/*
+	 * Match exactly the zlib parameters used by the linux kernel crypto
+	 * API.
+	 */
+        if (deflateInit2(&strm, DEFLATE_DEF_LEVEL, Z_DEFLATED,
+			 -DEFLATE_DEF_WINBITS, DEFLATE_DEF_MEMLEVEL,
+			 Z_DEFAULT_STRATEGY)) {
+		errcnt += 1;
+		return -1;
+	}
+
+	strm.next_in = in_buf;
+	strm.avail_in = in_len;
+	strm.total_in = 0;
+
+	strm.next_out = out_buf;
+	strm.avail_out = *out_len;
+	strm.total_out = 0;
+
+	if (deflate(&strm, Z_FINISH) != Z_STREAM_END) {
+		deflateEnd(&strm);
+		errcnt += 1;
+		return -1;
+	}
+
+	if (deflateEnd(&strm) != Z_OK) {
+		errcnt += 1;
+		return -1;
+	}
+
+	*out_len = strm.total_out;
+
+	return 0;
+}
+
+static int lzo_compress(void *in_buf, size_t in_len, void *out_buf,
+			size_t *out_len)
+{
+	lzo_uint len;
+	int ret;
+
+	len = *out_len;
+	ret = lzo1x_999_compress(in_buf, in_len, out_buf, &len, lzo_mem);
+	*out_len = len;
+
+	if (ret != LZO_E_OK) {
+		errcnt += 1;
+		return -1;
+	}
+
+	return 0;
+}
+
+static int no_compress(void *in_buf, size_t in_len, void *out_buf,
+		       size_t *out_len)
+{
+	memcpy(out_buf, in_buf, in_len);
+	*out_len = in_len;
+	return 0;
+}
+
+int compress_data(void *in_buf, size_t in_len, void *out_buf, size_t *out_len,
+		  int type)
+{
+	int ret = 1;
+
+	if (in_len < UBIFS_MIN_COMPR_LEN) {
+		no_compress(in_buf, in_len, out_buf, out_len);
+		return MKFS_UBIFS_COMPR_NONE;
+	}
+
+	switch (type) {
+	case MKFS_UBIFS_COMPR_LZO:
+		ret = lzo_compress(in_buf, in_len, out_buf, out_len);
+		break;
+	case MKFS_UBIFS_COMPR_ZLIB:
+		ret = zlib_deflate(in_buf, in_len, out_buf, out_len);
+		break;
+	case MKFS_UBIFS_COMPR_NONE:
+		ret = 1;
+		break;
+	default:
+		errcnt += 1;
+		break;
+	}
+	if (ret || *out_len >= in_len) {
+		no_compress(in_buf, in_len, out_buf, out_len);
+		return MKFS_UBIFS_COMPR_NONE;
+	}
+	return type;
+}
+
+int init_compression(void)
+{
+	lzo_mem = malloc(LZO1X_999_MEM_COMPRESS);
+	if (!lzo_mem)
+		return -1;
+	return 0;
+}
+
+void destroy_compression(void)
+{
+	free(lzo_mem);
+	if (errcnt)
+		fprintf(stderr, "%llu compression errors occurred\n", errcnt);
+}
diff --git a/mkfs.ubifs/compr.h b/mkfs.ubifs/compr.h
new file mode 100644
index 0000000..c76a5b9
--- /dev/null
+++ b/mkfs.ubifs/compr.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2008 Nokia Corporation.
+ * Copyright (C) 2008 University of Szeged, Hungary
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy
+ *          Adrian Hunter
+ *          Zoltan Sogor
+ */
+
+#ifndef __UBIFS_COMPRESS_H__
+#define __UBIFS_COMPRESS_H__
+
+enum compression_type
+{
+	MKFS_UBIFS_COMPR_NONE,
+	MKFS_UBIFS_COMPR_LZO,
+	MKFS_UBIFS_COMPR_ZLIB,
+};
+
+int compress_data(void *in_buf, size_t in_len, void *out_buf, size_t *out_len,
+		  int type);
+int init_compression(void);
+void destroy_compression(void);
+
+#endif
diff --git a/mkfs.ubifs/crc16.c b/mkfs.ubifs/crc16.c
new file mode 100644
index 0000000..a19512e
--- /dev/null
+++ b/mkfs.ubifs/crc16.c
@@ -0,0 +1,56 @@
+/*
+ * This code was taken from the linux kernel. The license is GPL Version 2.
+ */
+
+#include "crc16.h"
+
+/** CRC table for the CRC-16. The poly is 0x8005 (x^16 + x^15 + x^2 + 1) */
+uint16_t const crc16_table[256] = {
+	0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
+	0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
+	0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
+	0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
+	0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
+	0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
+	0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
+	0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
+	0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
+	0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
+	0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
+	0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
+	0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
+	0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
+	0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
+	0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
+	0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
+	0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
+	0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
+	0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
+	0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
+	0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
+	0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
+	0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
+	0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
+	0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
+	0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
+	0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
+	0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
+	0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
+	0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
+	0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
+};
+
+/**
+ * crc16 - compute the CRC-16 for the data buffer
+ * @crc:	previous CRC value
+ * @buffer:	data pointer
+ * @len:	number of bytes in the buffer
+ *
+ * Returns the updated CRC value.
+ */
+uint16_t crc16(uint16_t crc, uint8_t const *buffer, size_t len)
+{
+	while (len--)
+		crc = crc16_byte(crc, *buffer++);
+	return crc;
+}
diff --git a/mkfs.ubifs/crc16.h b/mkfs.ubifs/crc16.h
new file mode 100644
index 0000000..539d21a
--- /dev/null
+++ b/mkfs.ubifs/crc16.h
@@ -0,0 +1,27 @@
+/*
+ * Implements the standard CRC-16:
+ *   Width 16
+ *   Poly  0x8005 (x^16 + x^15 + x^2 + 1)
+ *   Init  0
+ *
+ * Copyright (c) 2005 Ben Gardner <bgardner@wabtec.com>
+ *
+ * This code was taken from the linux kernel. The license is GPL Version 2.
+ */
+
+#ifndef __CRC16_H__
+#define __CRC16_H__
+
+#include <stdlib.h>
+#include <stdint.h>
+
+extern uint16_t const crc16_table[256];
+
+extern uint16_t crc16(uint16_t crc, const uint8_t *buffer, size_t len);
+
+static inline uint16_t crc16_byte(uint16_t crc, const uint8_t data)
+{
+	return (crc >> 8) ^ crc16_table[(crc ^ data) & 0xff];
+}
+
+#endif /* __CRC16_H__ */
diff --git a/mkfs.ubifs/crc32.c b/mkfs.ubifs/crc32.c
new file mode 100644
index 0000000..6b1e50c
--- /dev/null
+++ b/mkfs.ubifs/crc32.c
@@ -0,0 +1,95 @@
+/*
+ *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
+ *  code or tables extracted from it, as desired without restriction.
+ *
+ *  First, the polynomial itself and its table of feedback terms.  The
+ *  polynomial is
+ *  X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
+ *
+ *  Note that we take it "backwards" and put the highest-order term in
+ *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
+ *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
+ *  the MSB being 1
+ *
+ *  Note that the usual hardware shift register implementation, which
+ *  is what we're using (we're merely optimizing it by doing eight-bit
+ *  chunks at a time) shifts bits into the lowest-order term.  In our
+ *  implementation, that means shifting towards the right.  Why do we
+ *  do it this way?  Because the calculated CRC must be transmitted in
+ *  order from highest-order term to lowest-order term.  UARTs transmit
+ *  characters in order from LSB to MSB.  By storing the CRC this way
+ *  we hand it to the UART in the order low-byte to high-byte; the UART
+ *  sends each low-bit to hight-bit; and the result is transmission bit
+ *  by bit from highest- to lowest-order term without requiring any bit
+ *  shuffling on our part.  Reception works similarly
+ *
+ *  The feedback terms table consists of 256, 32-bit entries.  Notes
+ *
+ *      The table can be generated at runtime if desired; code to do so
+ *      is shown later.  It might not be obvious, but the feedback
+ *      terms simply represent the results of eight shift/xor opera
+ *      tions for all combinations of data and CRC register values
+ *
+ *      The values must be right-shifted by eight bits by the "updcrc
+ *      logic; the shift must be unsigned (bring in zeroes).  On some
+ *      hardware you could probably optimize the shift in assembler by
+ *      using byte-swap instructions
+ *      polynomial $edb88320
+ */
+
+#include <stdint.h>
+
+const uint32_t crc32_table[256] = {
+	0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
+	0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
+	0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
+	0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
+	0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
+	0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
+	0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
+	0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
+	0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
+	0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
+	0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
+	0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
+	0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
+	0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
+	0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
+	0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
+	0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
+	0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
+	0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
+	0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
+	0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
+	0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
+	0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
+	0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
+	0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
+	0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
+	0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
+	0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
+	0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
+	0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
+	0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
+	0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
+	0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
+	0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
+	0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
+	0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
+	0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
+	0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
+	0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
+	0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
+	0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
+	0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
+	0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
+	0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
+	0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
+	0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
+	0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
+	0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
+	0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
+	0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
+	0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
+	0x2d02ef8dL
+};
diff --git a/mkfs.ubifs/crc32.h b/mkfs.ubifs/crc32.h
new file mode 100644
index 0000000..4b51177
--- /dev/null
+++ b/mkfs.ubifs/crc32.h
@@ -0,0 +1,22 @@
+/*
+ * This code was taken from the linux kernel. The license is GPL Version 2.
+ */
+
+#ifndef __CRC32_H__
+#define __CRC32_H__
+
+#include <stdint.h>
+
+extern const uint32_t crc32_table[256];
+
+/* Return a 32-bit CRC of the contents of the buffer. */
+static inline uint32_t crc32(uint32_t val, const void *ss, int len)
+{
+	const unsigned char *s = ss;
+
+	while (--len >= 0)
+		val = crc32_table[(val ^ *s++) & 0xff] ^ (val >> 8);
+	return val;
+}
+
+#endif /* __CRC32_H__ */
diff --git a/mkfs.ubifs/defs.h b/mkfs.ubifs/defs.h
new file mode 100644
index 0000000..06cf9e5
--- /dev/null
+++ b/mkfs.ubifs/defs.h
@@ -0,0 +1,107 @@
+/*
+ * Greate deal of the code was taken from the kernel UBIFS implementation, and
+ * this file contains some "glue" definitions.
+ */
+
+#ifndef __UBIFS_DEFS_H__
+#define __UBIFS_DEFS_H__
+
+#define t16(x) ({ \
+	uint16_t __b = (x); \
+	(__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_16(__b); \
+})
+
+#define t32(x) ({ \
+	uint32_t __b = (x); \
+	(__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_32(__b); \
+})
+
+#define t64(x) ({ \
+	uint64_t __b = (x); \
+	(__LITTLE_ENDIAN==__BYTE_ORDER) ? __b : bswap_64(__b); \
+})
+
+#define cpu_to_le16(x) ((__le16){t16(x)})
+#define cpu_to_le32(x) ((__le32){t32(x)})
+#define cpu_to_le64(x) ((__le64){t64(x)})
+
+#define le16_to_cpu(x) (t16((x)))
+#define le32_to_cpu(x) (t32((x)))
+#define le64_to_cpu(x) (t64((x)))
+
+#define ALIGN(x,a) __ALIGN_MASK(x,(typeof(x))(a)-1)
+#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))
+
+#define min_t(t,x,y) ({ \
+	typeof((x)) _x = (x); \
+	typeof((y)) _y = (y); \
+	(_x < _y) ? _x : _y; \
+})
+
+#define max_t(t,x,y) ({ \
+	typeof((x)) _x = (x); \
+	typeof((y)) _y = (y); \
+	(_x > _y) ? _x : _y; \
+})
+
+#define unlikely(x) (x)
+
+#define ubifs_assert(x) ({})
+
+struct qstr
+{
+	char *name;
+	size_t len;
+};
+
+/**
+ * fls - find last (most-significant) bit set
+ * @x: the word to search
+ *
+ * This is defined the same way as ffs.
+ * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
+ */
+static inline int fls(int x)
+{
+	int r = 32;
+
+	if (!x)
+		return 0;
+	if (!(x & 0xffff0000u)) {
+		x <<= 16;
+		r -= 16;
+	}
+	if (!(x & 0xff000000u)) {
+		x <<= 8;
+		r -= 8;
+	}
+	if (!(x & 0xf0000000u)) {
+		x <<= 4;
+		r -= 4;
+	}
+	if (!(x & 0xc0000000u)) {
+		x <<= 2;
+		r -= 2;
+	}
+	if (!(x & 0x80000000u)) {
+		x <<= 1;
+		r -= 1;
+	}
+	return r;
+}
+
+#define do_div(n,base) ({ \
+int __res; \
+__res = ((unsigned long) n) % (unsigned) base; \
+n = ((unsigned long) n) / (unsigned) base; \
+__res; })
+
+#if INT_MAX != 0x7fffffff
+#error : sizeof(int) must be 4 for this program
+#endif
+
+#if (~0ULL) != 0xffffffffffffffffULL
+#error : sizeof(long long) must be 8 for this program
+#endif
+
+#endif
diff --git a/mkfs.ubifs/devtable.c b/mkfs.ubifs/devtable.c
new file mode 100644
index 0000000..3f38339
--- /dev/null
+++ b/mkfs.ubifs/devtable.c
@@ -0,0 +1,524 @@
+/*
+ * Copyright (C) 2008 Nokia Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Author: Artem Bityutskiy
+ *
+ * Part of the device table parsing code was taken from the mkfs.jffs2 utility.
+ * The original author of that code is Erik Andersen, hence:
+ *	Copyright (C) 2001, 2002 Erik Andersen <andersen@codepoet.org>
+ */
+
+/*
+ * This file implemented device table support. Device table entries take the
+ * form of:
+ * <path>    <type> <mode> <uid> <gid> <major> <minor> <start>	<inc> <count>
+ * /dev/mem  c       640   0     0     1       1       0        0     -
+ *
+ * Type can be one of:
+ * f  A regular file
+ * d  Directory
+ * c  Character special device file
+ * b  Block special device file
+ * p  Fifo (named pipe)
+ *
+ * Don't bother with symlinks (permissions are irrelevant), hard links (special
+ * cases of regular files), or sockets (why bother).
+ *
+ * Regular files must exist in the target root directory. If a char, block,
+ * fifo, or directory does not exist, it will be created.
+ *
+ * Please, refer the device_table.txt file which can be found at MTD utilities
+ * for more information about what the device table is.
+ */
+
+#include "mkfs.ubifs.h"
+#include "hashtable/hashtable.h"
+#include "hashtable/hashtable_itr.h"
+
+/*
+ * The hash table which contains paths to files/directories/device nodes
+ * referred to in the device table. For example, if the device table refers
+ * "/dev/loop0", the @path_htbl will contain "/dev" element.
+ */
+static struct hashtable *path_htbl;
+
+/* Hash function used for hash tables */
+static unsigned int r5_hash(void *s)
+{
+	unsigned int a = 0;
+	const signed char *str = s;
+
+	while (*str) {
+		a += *str << 4;
+		a += *str >> 4;
+		a *= 11;
+		str++;
+	}
+
+	return a;
+}
+
+/*
+ * Check whether 2 keys of a hash table are equivalent. The keys are path/file
+ * names, so we simply use 'strcmp()'.
+ */
+static int is_equivalent(void *k1, void *k2)
+{
+	return !strcmp(k1, k2);
+}
+
+/**
+ * separate_last - separate out the last path component
+ * @buf: the path to split
+ * @len: length of the @buf string
+ * @path: the beginning of path is returned here
+ * @name: the last path component is returned here
+ *
+ * This helper function separates out the the last component of the full path
+ * string. For example, "/dev/loop" would be split on "/dev" and "loop". This
+ * function allocates memory for @path and @name and return the result there.
+ * Returns zero in case of success and a negative error code in case of
+ * failure.
+ */
+static int separate_last(const char *buf, int len, char **path, char **name)
+{
+	int path_len = len, name_len;
+	const char *p = buf + len, *n;
+
+	while (*--p != '/')
+		path_len -= 1;
+
+	/* Drop the final '/' unless this is the root directory */
+	name_len = len - path_len;
+	n = buf + path_len;
+	if (path_len > 1)
+		path_len -= 1;
+
+	*path = malloc(path_len + 1);
+	if (!*path)
+		return err_msg("cannot allocate %d bytes of memory",
+			       path_len + 1);
+	memcpy(*path, buf, path_len);
+	(*path)[path_len] = '\0';
+
+	*name = malloc(name_len + 1);
+	if (!*name) {
+		free(*path);
+		return err_msg("cannot allocate %d bytes of memory",
+			       name_len + 1);
+	}
+	memcpy(*name, n, name_len + 1);
+
+	return 0;
+}
+
+static int interpret_table_entry(const char *root, const char *line)
+{
+	char buf[1024], type, *path = NULL, *name = NULL;
+	int len;
+	struct path_htbl_element *ph_elt = NULL;
+	struct name_htbl_element *nh_elt = NULL;
+	unsigned int mode = 0755, uid = 0, gid = 0, major = 0, minor = 0;
+	unsigned int start = 0, increment = 0, count = 0;
+
+	if (sscanf(line, "%1023s %c %o %u %u %u %u %u %u %u",
+		   buf, &type, &mode, &uid, &gid, &major, &minor,
+		   &start, &increment, &count) < 0)
+		return sys_err_msg("sscanf failed");
+
+	dbg_msg(3, "name %s, type %c, mode %o, uid %u, gid %u, major %u, "
+		"minor %u, start %u, inc %u, cnt %u",
+		buf, type, mode, uid, gid, major, minor, start,
+		increment, count);
+
+	len = strnlen(buf, 1024);
+	if (len == 1024)
+		return err_msg("too long path");
+
+	if (!strcmp(buf, "/"))
+		return err_msg("device table entries require absolute paths");
+	if (buf[1] == '\0')
+		return err_msg("root directory cannot be created");
+	if (strstr(buf, "//"))
+		return err_msg("'//' cannot be used in the path");
+	if (buf[len - 1] == '/')
+		return err_msg("do not put '/' at the end");
+
+	if (strstr(buf, "/./") || strstr(buf, "/../") ||
+	    !strcmp(buf + len - 2, "/.") || !strcmp(buf + len - 3, "/.."))
+		return err_msg("'.' and '..' cannot be used in the path");
+
+	switch (type) {
+		case 'd':
+			mode |= S_IFDIR;
+			break;
+		case 'f':
+			mode |= S_IFREG;
+			break;
+		case 'p':
+			mode |= S_IFIFO;
+			break;
+		case 'c':
+			mode |= S_IFCHR;
+			break;
+		case 'b':
+			mode |= S_IFBLK;
+			break;
+		default:
+			return err_msg("unsupported file type '%c'", type);
+	}
+
+	if (separate_last(buf, len, &path, &name))
+		return -1;
+
+	/*
+	 * Check if this path already exist in the path hash table and add it
+	 * if it is not.
+	 */
+	ph_elt = hashtable_search(path_htbl, path);
+	if (!ph_elt) {
+		dbg_msg(3, "inserting '%s' into path hash table", path);
+		ph_elt = malloc(sizeof(struct path_htbl_element));
+		if (!ph_elt) {
+			err_msg("cannot allocate %d bytes of memory",
+				sizeof(struct path_htbl_element));
+			goto out_free;
+		}
+
+		if (!hashtable_insert(path_htbl, path, ph_elt)) {
+			err_msg("cannot insert into path hash table");
+			goto out_free;
+		}
+
+		ph_elt->path = path;
+		path = NULL;
+		ph_elt->name_htbl = create_hashtable(128, &r5_hash,
+						     &is_equivalent);
+		if (!ph_elt->name_htbl) {
+			err_msg("cannot create name hash table");
+			goto out_free;
+		}
+	}
+
+	if (increment != 0 && count == 0)
+		return err_msg("count cannot be zero if increment is non-zero");
+
+	/*
+	 * Add the file/directory/device node (last component of the path) to
+	 * the name hashtable. The name hashtable resides in the corresponding
+	 * path hashtable element.
+	 */
+
+	if (count == 0) {
+		/* This entry does not require any iterating */
+		nh_elt = malloc(sizeof(struct name_htbl_element));
+		if (!nh_elt) {
+			err_msg("cannot allocate %d bytes of memory",
+				sizeof(struct name_htbl_element));
+			goto out_free;
+		}
+
+		nh_elt->mode = mode;
+		nh_elt->uid = uid;
+		nh_elt->gid = gid;
+		nh_elt->dev = makedev(major, minor);
+
+		dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)",
+			name, major(nh_elt->dev), minor(nh_elt->dev));
+
+		if (hashtable_search(ph_elt->name_htbl, name))
+			return err_msg("'%s' is referred twice", buf);
+
+		nh_elt->name = name;
+		if (!hashtable_insert(ph_elt->name_htbl, name, nh_elt)) {
+			err_msg("cannot insert into name hash table");
+			goto out_free;
+		}
+	} else {
+		int i, num = start + increment * count, len = strlen(name) + 20;
+		char *nm;
+
+		for (i = start; i < num; i++) {
+			nh_elt = malloc(sizeof(struct name_htbl_element));
+			if (!nh_elt) {
+				err_msg("cannot allocate %d bytes of memory",
+					sizeof(struct name_htbl_element));
+				goto out_free;
+			}
+
+			nh_elt->mode = mode;
+			nh_elt->uid = uid;
+			nh_elt->gid = gid;
+			nh_elt->dev = makedev(major, minor + i - start);
+
+			nm = malloc(len);
+			if (!nm) {
+				err_msg("cannot allocate %d bytes of memory", len);
+				goto out_free;
+			}
+
+			sprintf(nm, "%s%d", name, i);
+			nh_elt->name = nm;
+
+			dbg_msg(3, "inserting '%s' into name hash table (major %d, minor %d)",
+			        nm, major(nh_elt->dev), minor(nh_elt->dev));
+
+			if (hashtable_search(ph_elt->name_htbl, nm)) {
+				err_msg("'%s' is referred twice", buf);
+				free (nm);
+				goto out_free;
+			}
+
+			if (!hashtable_insert(ph_elt->name_htbl, nm, nh_elt)) {
+				err_msg("cannot insert into name hash table");
+				free (nm);
+				goto out_free;
+			}
+		}
+		free(name);
+		name = NULL;
+	}
+
+	return 0;
+
+out_free:
+	free(ph_elt);
+	free(nh_elt);
+	free(path);
+	free(name);
+	return -1;
+}
+
+/**
+ * parse_devtable - parse the device table.
+ * @tbl_file: device table file name
+ *
+ * This function parses the device table and prepare the hash table which will
+ * later be used by mkfs.ubifs to create the specified files/device nodes.
+ * Returns zero in case of success and a negative error code in case of
+ * failure.
+ */
+int parse_devtable(const char *root, const char *tbl_file)
+{
+	FILE *f;
+	char *line = NULL;
+	struct stat st;
+	size_t len;
+
+	dbg_msg(1, "parsing device table file '%s'", tbl_file);
+
+	path_htbl = create_hashtable(128, &r5_hash, &is_equivalent);
+	if (!path_htbl)
+		return err_msg("cannot create path hash table");
+
+	f = fopen(tbl_file, "r");
+	if (!f)
+		return sys_err_msg("cannot open '%s'", tbl_file);
+
+	if (fstat(fileno(f), &st) < 0) {
+		sys_err_msg("cannot stat '%s'", tbl_file);
+		goto out_close;
+	}
+
+	if (st.st_size < 10) {
+		sys_err_msg("'%s' is too short", tbl_file);
+		goto out_close;
+	}
+
+	/*
+	 * The general plan now is to read in one line at a time, check for
+	 * leading comment delimiters ('#'), then try and parse the line as a
+	 * device table
+	 */
+	while (getline(&line, &len, f) != -1) {
+		/* First trim off any white-space */
+		len = strlen(line);
+
+		/* Trim trailing white-space */
+		while (len > 0 && isspace(line[len - 1]))
+			line[--len] = '\0';
+		/* Trim leading white-space */
+		memmove(line, &line[strspn(line, " \n\r\t\v")], len);
+
+		/* How long are we after trimming? */
+		len = strlen(line);
+
+		/* If this is not a comment line, try to interpret it */
+		if (len && *line != '#') {
+			if (interpret_table_entry(root, line)) {
+				err_msg("cannot parse '%s'", line);
+				goto out_close;
+			}
+		}
+
+		free(line);
+		line = NULL;
+	}
+
+	dbg_msg(1, "finished parsing");
+	fclose(f);
+	return 0;
+
+out_close:
+	fclose(f);
+	free_devtable_info();
+	return -1;
+}
+
+/**
+ * devtbl_find_path - find a path in the path hash table.
+ * @path: UBIFS path to find.
+ *
+ * This looks up the path hash table. Returns the path hash table element
+ * reference if @path was found and %NULL if not.
+ */
+struct path_htbl_element *devtbl_find_path(const char *path)
+{
+	if (!path_htbl)
+		return NULL;
+
+	return hashtable_search(path_htbl, (void *)path);
+}
+
+/**
+ * devtbl_find_name - find a name in the name hash table.
+ * @ph_etl: path hash table element to find at
+ * @name: name to find
+ *
+ * This looks up the name hash table. Returns the name hash table element
+ * reference if @name found and %NULL if not.
+ */
+struct name_htbl_element *devtbl_find_name(struct path_htbl_element *ph_elt,
+					   const char *name)
+{
+	if (!path_htbl)
+		return NULL;
+
+	return hashtable_search(ph_elt->name_htbl, (void *)name);
+}
+
+/**
+ * override_attributes - override inode attributes.
+ * @st: struct stat object to containing the attributes to override
+ * @ph_elt: path hash table element object
+ * @nh_elt: name hash table element object containing the new values
+ *
+ * The device table file may override attributes like UID of files. For
+ * example, the device table may contain a "/dev" entry, and the UBIFS FS on
+ * the host may contain "/dev" directory. In this case the attributes of the
+ * "/dev" directory inode has to be as the device table specifies.
+ *
+ * Note, the hash element is removed by this function as well.
+ */
+int override_attributes(struct stat *st, struct path_htbl_element *ph_elt,
+			struct name_htbl_element *nh_elt)
+{
+	if (!path_htbl)
+		return 0;
+
+	if (S_ISCHR(st->st_mode) || S_ISBLK(st->st_mode) ||
+	    S_ISFIFO(st->st_mode))
+		return err_msg("%s/%s both exists at UBIFS root at host, "
+			       "and is referred from the device table",
+			       strcmp(ph_elt->path, "/") ? ph_elt->path : "",
+			       nh_elt->name);
+
+	if ((st->st_mode & S_IFMT) != (nh_elt->mode & S_IFMT))
+		return err_msg("%s/%s is referred from the device table also exists in "
+			       "the UBIFS root directory at host, but the file type is "
+			       "different", strcmp(ph_elt->path, "/") ? ph_elt->path : "",
+			       nh_elt->name);
+
+	dbg_msg(3, "set UID %d, GID %d, mode %o for %s/%s as device table says",
+		nh_elt->uid, nh_elt->gid, nh_elt->mode, ph_elt->path, nh_elt->name);
+
+	st->st_uid = nh_elt->uid;
+	st->st_gid = nh_elt->gid;
+	st->st_mode = nh_elt->mode;
+
+	hashtable_remove(ph_elt->name_htbl, (void *)nh_elt->name);
+	return 0;
+}
+
+/**
+ * first_name_htbl_element - return first element of the name hash table.
+ * @ph_elt: the path hash table the name hash table belongs to
+ * @itr: double pointer to a 'struct hashtable_itr' object where the
+ *       information about further iterations is stored
+ *
+ * This function implements name hash table iteration together with
+ * 'next_name_htbl_element()'. Returns the first name hash table element or
+ * %NULL if the hash table is empty.
+ */
+struct name_htbl_element *
+first_name_htbl_element(struct path_htbl_element *ph_elt,
+			struct hashtable_itr **itr)
+{
+	if (!path_htbl || !ph_elt || hashtable_count(ph_elt->name_htbl) == 0)
+		return NULL;
+
+	*itr = hashtable_iterator(ph_elt->name_htbl);
+	return hashtable_iterator_value(*itr);
+}
+
+/**
+ * first_name_htbl_element - return next element of the name hash table.
+ * @ph_elt: the path hash table the name hash table belongs to
+ * @itr: double pointer to a 'struct hashtable_itr' object where the
+ *       information about further iterations is stored
+ *
+ * This function implements name hash table iteration together with
+ * 'first_name_htbl_element()'. Returns the next name hash table element or
+ * %NULL if there are no more elements.
+ */
+struct name_htbl_element *
+next_name_htbl_element(struct path_htbl_element *ph_elt,
+		       struct hashtable_itr **itr)
+{
+	if (!path_htbl || !ph_elt || !hashtable_iterator_advance(*itr))
+		return NULL;
+
+	return hashtable_iterator_value(*itr);
+}
+
+/**
+ * free_devtable_info - free device table information.
+ *
+ * This function frees the path hash table and the name hash tables.
+ */
+void free_devtable_info(void)
+{
+	struct hashtable_itr *ph_itr;
+	struct path_htbl_element *ph_elt;
+
+	if (!path_htbl)
+		return;
+
+	if (hashtable_count(path_htbl) > 0) {
+		ph_itr = hashtable_iterator(path_htbl);
+		do {
+			ph_elt = hashtable_iterator_value(ph_itr);
+			/*
+			 * Note, since we use the same string for the key and
+			 * @name in the name hash table elements, we do not
+			 * have to iterate name hash table because @name memory
+			 * will be freed when freeing the key.
+			 */
+			hashtable_destroy(ph_elt->name_htbl, 1);
+		} while (hashtable_iterator_advance(ph_itr));
+	}
+	hashtable_destroy(path_htbl, 1);
+}
diff --git a/mkfs.ubifs/hashtable/hashtable.c b/mkfs.ubifs/hashtable/hashtable.c
new file mode 100644
index 0000000..763357e
--- /dev/null
+++ b/mkfs.ubifs/hashtable/hashtable.c
@@ -0,0 +1,274 @@
+/* Copyright (C) 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
+
+#include "hashtable.h"
+#include "hashtable_private.h"
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+
+/*
+Credit for primes table: Aaron Krowne
+ http://br.endernet.org/~akrowne/
+ http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
+*/
+static const unsigned int primes[] = {
+53, 97, 193, 389,
+769, 1543, 3079, 6151,
+12289, 24593, 49157, 98317,
+196613, 393241, 786433, 1572869,
+3145739, 6291469, 12582917, 25165843,
+50331653, 100663319, 201326611, 402653189,
+805306457, 1610612741
+};
+const unsigned int prime_table_length = sizeof(primes)/sizeof(primes[0]);
+const float max_load_factor = 0.65;
+
+/*****************************************************************************/
+struct hashtable *
+create_hashtable(unsigned int minsize,
+                 unsigned int (*hashf) (void*),
+                 int (*eqf) (void*,void*))
+{
+    struct hashtable *h;
+    unsigned int pindex, size = primes[0];
+    /* Check requested hashtable isn't too large */
+    if (minsize > (1u << 30)) return NULL;
+    /* Enforce size as prime */
+    for (pindex=0; pindex < prime_table_length; pindex++) {
+        if (primes[pindex] > minsize) { size = primes[pindex]; break; }
+    }
+    h = (struct hashtable *)malloc(sizeof(struct hashtable));
+    if (NULL == h) return NULL; /*oom*/
+    h->table = (struct entry **)malloc(sizeof(struct entry*) * size);
+    if (NULL == h->table) { free(h); return NULL; } /*oom*/
+    memset(h->table, 0, size * sizeof(struct entry *));
+    h->tablelength  = size;
+    h->primeindex   = pindex;
+    h->entrycount   = 0;
+    h->hashfn       = hashf;
+    h->eqfn         = eqf;
+    h->loadlimit    = (unsigned int) ceil(size * max_load_factor);
+    return h;
+}
+
+/*****************************************************************************/
+unsigned int
+hash(struct hashtable *h, void *k)
+{
+    /* Aim to protect against poor hash functions by adding logic here
+     * - logic taken from java 1.4 hashtable source */
+    unsigned int i = h->hashfn(k);
+    i += ~(i << 9);
+    i ^=  ((i >> 14) | (i << 18)); /* >>> */
+    i +=  (i << 4);
+    i ^=  ((i >> 10) | (i << 22)); /* >>> */
+    return i;
+}
+
+/*****************************************************************************/
+static int
+hashtable_expand(struct hashtable *h)
+{
+    /* Double the size of the table to accomodate more entries */
+    struct entry **newtable;
+    struct entry *e;
+    struct entry **pE;
+    unsigned int newsize, i, index;
+    /* Check we're not hitting max capacity */
+    if (h->primeindex == (prime_table_length - 1)) return 0;
+    newsize = primes[++(h->primeindex)];
+
+    newtable = (struct entry **)malloc(sizeof(struct entry*) * newsize);
+    if (NULL != newtable)
+    {
+        memset(newtable, 0, newsize * sizeof(struct entry *));
+        /* This algorithm is not 'stable'. ie. it reverses the list
+         * when it transfers entries between the tables */
+        for (i = 0; i < h->tablelength; i++) {
+            while (NULL != (e = h->table[i])) {
+                h->table[i] = e->next;
+                index = indexFor(newsize,e->h);
+                e->next = newtable[index];
+                newtable[index] = e;
+            }
+        }
+        free(h->table);
+        h->table = newtable;
+    }
+    /* Plan B: realloc instead */
+    else 
+    {
+        newtable = (struct entry **)
+                   realloc(h->table, newsize * sizeof(struct entry *));
+        if (NULL == newtable) { (h->primeindex)--; return 0; }
+        h->table = newtable;
+        memset(newtable[h->tablelength], 0, newsize - h->tablelength);
+        for (i = 0; i < h->tablelength; i++) {
+            for (pE = &(newtable[i]), e = *pE; e != NULL; e = *pE) {
+                index = indexFor(newsize,e->h);
+                if (index == i)
+                {
+                    pE = &(e->next);
+                }
+                else
+                {
+                    *pE = e->next;
+                    e->next = newtable[index];
+                    newtable[index] = e;
+                }
+            }
+        }
+    }
+    h->tablelength = newsize;
+    h->loadlimit   = (unsigned int) ceil(newsize * max_load_factor);
+    return -1;
+}
+
+/*****************************************************************************/
+unsigned int
+hashtable_count(struct hashtable *h)
+{
+    return h->entrycount;
+}
+
+/*****************************************************************************/
+int
+hashtable_insert(struct hashtable *h, void *k, void *v)
+{
+    /* This method allows duplicate keys - but they shouldn't be used */
+    unsigned int index;
+    struct entry *e;
+    if (++(h->entrycount) > h->loadlimit)
+    {
+        /* Ignore the return value. If expand fails, we should
+         * still try cramming just this value into the existing table
+         * -- we may not have memory for a larger table, but one more
+         * element may be ok. Next time we insert, we'll try expanding again.*/
+        hashtable_expand(h);
+    }
+    e = (struct entry *)malloc(sizeof(struct entry));
+    if (NULL == e) { --(h->entrycount); return 0; } /*oom*/
+    e->h = hash(h,k);
+    index = indexFor(h->tablelength,e->h);
+    e->k = k;
+    e->v = v;
+    e->next = h->table[index];
+    h->table[index] = e;
+    return -1;
+}
+
+/*****************************************************************************/
+void * /* returns value associated with key */
+hashtable_search(struct hashtable *h, void *k)
+{
+    struct entry *e;
+    unsigned int hashvalue, index;
+    hashvalue = hash(h,k);
+    index = indexFor(h->tablelength,hashvalue);
+    e = h->table[index];
+    while (NULL != e)
+    {
+        /* Check hash value to short circuit heavier comparison */
+        if ((hashvalue == e->h) && (h->eqfn(k, e->k))) return e->v;
+        e = e->next;
+    }
+    return NULL;
+}
+
+/*****************************************************************************/
+void * /* returns value associated with key */
+hashtable_remove(struct hashtable *h, void *k)
+{
+    /* TODO: consider compacting the table when the load factor drops enough,
+     *       or provide a 'compact' method. */
+
+    struct entry *e;
+    struct entry **pE;
+    void *v;
+    unsigned int hashvalue, index;
+
+    hashvalue = hash(h,k);
+    index = indexFor(h->tablelength,hash(h,k));
+    pE = &(h->table[index]);
+    e = *pE;
+    while (NULL != e)
+    {
+        /* Check hash value to short circuit heavier comparison */
+        if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
+        {
+            *pE = e->next;
+            h->entrycount--;
+            v = e->v;
+            freekey(e->k);
+            free(e);
+            return v;
+        }
+        pE = &(e->next);
+        e = e->next;
+    }
+    return NULL;
+}
+
+/*****************************************************************************/
+/* destroy */
+void
+hashtable_destroy(struct hashtable *h, int free_values)
+{
+    unsigned int i;
+    struct entry *e, *f;
+    struct entry **table = h->table;
+    if (free_values)
+    {
+        for (i = 0; i < h->tablelength; i++)
+        {
+            e = table[i];
+            while (NULL != e)
+            { f = e; e = e->next; freekey(f->k); free(f->v); free(f); }
+        }
+    }
+    else
+    {
+        for (i = 0; i < h->tablelength; i++)
+        {
+            e = table[i];
+            while (NULL != e)
+            { f = e; e = e->next; freekey(f->k); free(f); }
+        }
+    }
+    free(h->table);
+    free(h);
+}
+
+/*
+ * Copyright (c) 2002, Christopher Clark
+ * All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 
+ * * 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.
+ * 
+ * * Neither the name of the original author; nor the names of any contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ * 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER
+ * 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.
+*/
diff --git a/mkfs.ubifs/hashtable/hashtable.h b/mkfs.ubifs/hashtable/hashtable.h
new file mode 100644
index 0000000..b90781a
--- /dev/null
+++ b/mkfs.ubifs/hashtable/hashtable.h
@@ -0,0 +1,199 @@
+/* Copyright (C) 2002 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
+
+#ifndef __HASHTABLE_CWC22_H__
+#define __HASHTABLE_CWC22_H__
+
+struct hashtable;
+
+/* Example of use:
+ *
+ *      struct hashtable  *h;
+ *      struct some_key   *k;
+ *      struct some_value *v;
+ *
+ *      static unsigned int         hash_from_key_fn( void *k );
+ *      static int                  keys_equal_fn ( void *key1, void *key2 );
+ *
+ *      h = create_hashtable(16, hash_from_key_fn, keys_equal_fn);
+ *      k = (struct some_key *)     malloc(sizeof(struct some_key));
+ *      v = (struct some_value *)   malloc(sizeof(struct some_value));
+ *
+ *      (initialise k and v to suitable values)
+ * 
+ *      if (! hashtable_insert(h,k,v) )
+ *      {     exit(-1);               }
+ *
+ *      if (NULL == (found = hashtable_search(h,k) ))
+ *      {    printf("not found!");                  }
+ *
+ *      if (NULL == (found = hashtable_remove(h,k) ))
+ *      {    printf("Not found\n");                 }
+ *
+ */
+
+/* Macros may be used to define type-safe(r) hashtable access functions, with
+ * methods specialized to take known key and value types as parameters.
+ * 
+ * Example:
+ *
+ * Insert this at the start of your file:
+ *
+ * DEFINE_HASHTABLE_INSERT(insert_some, struct some_key, struct some_value);
+ * DEFINE_HASHTABLE_SEARCH(search_some, struct some_key, struct some_value);
+ * DEFINE_HASHTABLE_REMOVE(remove_some, struct some_key, struct some_value);
+ *
+ * This defines the functions 'insert_some', 'search_some' and 'remove_some'.
+ * These operate just like hashtable_insert etc., with the same parameters,
+ * but their function signatures have 'struct some_key *' rather than
+ * 'void *', and hence can generate compile time errors if your program is
+ * supplying incorrect data as a key (and similarly for value).
+ *
+ * Note that the hash and key equality functions passed to create_hashtable
+ * still take 'void *' parameters instead of 'some key *'. This shouldn't be
+ * a difficult issue as they're only defined and passed once, and the other
+ * functions will ensure that only valid keys are supplied to them.
+ *
+ * The cost for this checking is increased code size and runtime overhead
+ * - if performance is important, it may be worth switching back to the
+ * unsafe methods once your program has been debugged with the safe methods.
+ * This just requires switching to some simple alternative defines - eg:
+ * #define insert_some hashtable_insert
+ *
+ */
+
+/*****************************************************************************
+ * create_hashtable
+   
+ * @name                    create_hashtable
+ * @param   minsize         minimum initial size of hashtable
+ * @param   hashfunction    function for hashing keys
+ * @param   key_eq_fn       function for determining key equality
+ * @return                  newly created hashtable or NULL on failure
+ */
+
+struct hashtable *
+create_hashtable(unsigned int minsize,
+                 unsigned int (*hashfunction) (void*),
+                 int (*key_eq_fn) (void*,void*));
+
+/*****************************************************************************
+ * hashtable_insert
+   
+ * @name        hashtable_insert
+ * @param   h   the hashtable to insert into
+ * @param   k   the key - hashtable claims ownership and will free on removal
+ * @param   v   the value - does not claim ownership
+ * @return      non-zero for successful insertion
+ *
+ * This function will cause the table to expand if the insertion would take
+ * the ratio of entries to table size over the maximum load factor.
+ *
+ * This function does not check for repeated insertions with a duplicate key.
+ * The value returned when using a duplicate key is undefined -- when
+ * the hashtable changes size, the order of retrieval of duplicate key
+ * entries is reversed.
+ * If in doubt, remove before insert.
+ */
+
+int 
+hashtable_insert(struct hashtable *h, void *k, void *v);
+
+#define DEFINE_HASHTABLE_INSERT(fnname, keytype, valuetype) \
+int fnname (struct hashtable *h, keytype *k, valuetype *v) \
+{ \
+    return hashtable_insert(h,k,v); \
+}
+
+/*****************************************************************************
+ * hashtable_search
+   
+ * @name        hashtable_search
+ * @param   h   the hashtable to search
+ * @param   k   the key to search for  - does not claim ownership
+ * @return      the value associated with the key, or NULL if none found
+ */
+
+void *
+hashtable_search(struct hashtable *h, void *k);
+
+#define DEFINE_HASHTABLE_SEARCH(fnname, keytype, valuetype) \
+valuetype * fnname (struct hashtable *h, keytype *k) \
+{ \
+    return (valuetype *) (hashtable_search(h,k)); \
+}
+
+/*****************************************************************************
+ * hashtable_remove
+   
+ * @name        hashtable_remove
+ * @param   h   the hashtable to remove the item from
+ * @param   k   the key to search for  - does not claim ownership
+ * @return      the value associated with the key, or NULL if none found
+ */
+
+void * /* returns value */
+hashtable_remove(struct hashtable *h, void *k);
+
+#define DEFINE_HASHTABLE_REMOVE(fnname, keytype, valuetype) \
+valuetype * fnname (struct hashtable *h, keytype *k) \
+{ \
+    return (valuetype *) (hashtable_remove(h,k)); \
+}
+
+
+/*****************************************************************************
+ * hashtable_count
+   
+ * @name        hashtable_count
+ * @param   h   the hashtable
+ * @return      the number of items stored in the hashtable
+ */
+unsigned int
+hashtable_count(struct hashtable *h);
+
+
+/*****************************************************************************
+ * hashtable_destroy
+   
+ * @name        hashtable_destroy
+ * @param   h   the hashtable
+ * @param       free_values     whether to call 'free' on the remaining values
+ */
+
+void
+hashtable_destroy(struct hashtable *h, int free_values);
+
+#endif /* __HASHTABLE_CWC22_H__ */
+
+/*
+ * Copyright (c) 2002, Christopher Clark
+ * All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 
+ * * 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.
+ * 
+ * * Neither the name of the original author; nor the names of any contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ * 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER
+ * 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.
+*/
diff --git a/mkfs.ubifs/hashtable/hashtable_itr.c b/mkfs.ubifs/hashtable/hashtable_itr.c
new file mode 100644
index 0000000..5dced84
--- /dev/null
+++ b/mkfs.ubifs/hashtable/hashtable_itr.c
@@ -0,0 +1,188 @@
+/* Copyright (C) 2002, 2004 Christopher Clark  <firstname.lastname@cl.cam.ac.uk> */
+
+#include "hashtable.h"
+#include "hashtable_private.h"
+#include "hashtable_itr.h"
+#include <stdlib.h> /* defines NULL */
+
+/*****************************************************************************/
+/* hashtable_iterator    - iterator constructor */
+
+struct hashtable_itr *
+hashtable_iterator(struct hashtable *h)
+{
+    unsigned int i, tablelength;
+    struct hashtable_itr *itr = (struct hashtable_itr *)
+        malloc(sizeof(struct hashtable_itr));
+    if (NULL == itr) return NULL;
+    itr->h = h;
+    itr->e = NULL;
+    itr->parent = NULL;
+    tablelength = h->tablelength;
+    itr->index = tablelength;
+    if (0 == h->entrycount) return itr;
+
+    for (i = 0; i < tablelength; i++)
+    {
+        if (NULL != h->table[i])
+        {
+            itr->e = h->table[i];
+            itr->index = i;
+            break;
+        }
+    }
+    return itr;
+}
+
+/*****************************************************************************/
+/* key      - return the key of the (key,value) pair at the current position */
+/* value    - return the value of the (key,value) pair at the current position */
+
+void *
+hashtable_iterator_key(struct hashtable_itr *i)
+{ return i->e->k; }
+
+void *
+hashtable_iterator_value(struct hashtable_itr *i)
+{ return i->e->v; }
+
+/*****************************************************************************/
+/* advance - advance the iterator to the next element
+ *           returns zero if advanced to end of table */
+
+int
+hashtable_iterator_advance(struct hashtable_itr *itr)
+{
+    unsigned int j,tablelength;
+    struct entry **table;
+    struct entry *next;
+    if (NULL == itr->e) return 0; /* stupidity check */
+
+    next = itr->e->next;
+    if (NULL != next)
+    {
+        itr->parent = itr->e;
+        itr->e = next;
+        return -1;
+    }
+    tablelength = itr->h->tablelength;
+    itr->parent = NULL;
+    if (tablelength <= (j = ++(itr->index)))
+    {
+        itr->e = NULL;
+        return 0;
+    }
+    table = itr->h->table;
+    while (NULL == (next = table[j]))
+    {
+        if (++j >= tablelength)
+        {
+            itr->index = tablelength;
+            itr->e = NULL;
+            return 0;
+        }
+    }
+    itr->index = j;
+    itr->e = next;
+    return -1;
+}
+
+/*****************************************************************************/
+/* remove - remove the entry at the current iterator position
+ *          and advance the iterator, if there is a successive
+ *          element.
+ *          If you want the value, read it before you remove:
+ *          beware memory leaks if you don't.
+ *          Returns zero if end of iteration. */
+
+int
+hashtable_iterator_remove(struct hashtable_itr *itr)
+{
+    struct entry *remember_e, *remember_parent;
+    int ret;
+
+    /* Do the removal */
+    if (NULL == (itr->parent))
+    {
+        /* element is head of a chain */
+        itr->h->table[itr->index] = itr->e->next;
+    } else {
+        /* element is mid-chain */
+        itr->parent->next = itr->e->next;
+    }
+    /* itr->e is now outside the hashtable */
+    remember_e = itr->e;
+    itr->h->entrycount--;
+    freekey(remember_e->k);
+
+    /* Advance the iterator, correcting the parent */
+    remember_parent = itr->parent;
+    ret = hashtable_iterator_advance(itr);
+    if (itr->parent == remember_e) { itr->parent = remember_parent; }
+    free(remember_e);
+    return ret;
+}
+
+/*****************************************************************************/
+int /* returns zero if not found */
+hashtable_iterator_search(struct hashtable_itr *itr,
+                          struct hashtable *h, void *k)
+{
+    struct entry *e, *parent;
+    unsigned int hashvalue, index;
+
+    hashvalue = hash(h,k);
+    index = indexFor(h->tablelength,hashvalue);
+
+    e = h->table[index];
+    parent = NULL;
+    while (NULL != e)
+    {
+        /* Check hash value to short circuit heavier comparison */
+        if ((hashvalue == e->h) && (h->eqfn(k, e->k)))
+        {
+            itr->index = index;
+            itr->e = e;
+            itr->parent = parent;
+            itr->h = h;
+            return -1;
+        }
+        parent = e;
+        e = e->next;
+    }
+    return 0;
+}
+
+
+/*
+ * Copyright (c) 2002, 2004, Christopher Clark
+ * All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 
+ * * 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.
+ * 
+ * * Neither the name of the original author; nor the names of any contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ * 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER
+ * 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.
+*/
diff --git a/mkfs.ubifs/hashtable/hashtable_itr.h b/mkfs.ubifs/hashtable/hashtable_itr.h
new file mode 100644
index 0000000..eea699a
--- /dev/null
+++ b/mkfs.ubifs/hashtable/hashtable_itr.h
@@ -0,0 +1,112 @@
+/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
+
+#ifndef __HASHTABLE_ITR_CWC22__
+#define __HASHTABLE_ITR_CWC22__
+#include "hashtable.h"
+#include "hashtable_private.h" /* needed to enable inlining */
+
+/*****************************************************************************/
+/* This struct is only concrete here to allow the inlining of two of the
+ * accessor functions. */
+struct hashtable_itr
+{
+    struct hashtable *h;
+    struct entry *e;
+    struct entry *parent;
+    unsigned int index;
+};
+
+
+/*****************************************************************************/
+/* hashtable_iterator
+ */
+
+struct hashtable_itr *
+hashtable_iterator(struct hashtable *h);
+
+/*****************************************************************************/
+/* hashtable_iterator_key
+ * - return the value of the (key,value) pair at the current position */
+
+extern inline void *
+hashtable_iterator_key(struct hashtable_itr *i)
+{
+    return i->e->k;
+}
+
+/*****************************************************************************/
+/* value - return the value of the (key,value) pair at the current position */
+
+extern inline void *
+hashtable_iterator_value(struct hashtable_itr *i)
+{
+    return i->e->v;
+}
+
+/*****************************************************************************/
+/* advance - advance the iterator to the next element
+ *           returns zero if advanced to end of table */
+
+int
+hashtable_iterator_advance(struct hashtable_itr *itr);
+
+/*****************************************************************************/
+/* remove - remove current element and advance the iterator to the next element
+ *          NB: if you need the value to free it, read it before
+ *          removing. ie: beware memory leaks!
+ *          returns zero if advanced to end of table */
+
+int
+hashtable_iterator_remove(struct hashtable_itr *itr);
+
+/*****************************************************************************/
+/* search - overwrite the supplied iterator, to point to the entry
+ *          matching the supplied key.
+            h points to the hashtable to be searched.
+ *          returns zero if not found. */
+int
+hashtable_iterator_search(struct hashtable_itr *itr,
+                          struct hashtable *h, void *k);
+
+#define DEFINE_HASHTABLE_ITERATOR_SEARCH(fnname, keytype) \
+int fnname (struct hashtable_itr *i, struct hashtable *h, keytype *k) \
+{ \
+    return (hashtable_iterator_search(i,h,k)); \
+}
+
+
+
+#endif /* __HASHTABLE_ITR_CWC22__*/
+
+/*
+ * Copyright (c) 2002, 2004, Christopher Clark
+ * All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 
+ * * 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.
+ * 
+ * * Neither the name of the original author; nor the names of any contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ * 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER
+ * 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.
+*/
diff --git a/mkfs.ubifs/hashtable/hashtable_private.h b/mkfs.ubifs/hashtable/hashtable_private.h
new file mode 100644
index 0000000..3e95f60
--- /dev/null
+++ b/mkfs.ubifs/hashtable/hashtable_private.h
@@ -0,0 +1,85 @@
+/* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
+
+#ifndef __HASHTABLE_PRIVATE_CWC22_H__
+#define __HASHTABLE_PRIVATE_CWC22_H__
+
+#include "hashtable.h"
+
+/*****************************************************************************/
+struct entry
+{
+    void *k, *v;
+    unsigned int h;
+    struct entry *next;
+};
+
+struct hashtable {
+    unsigned int tablelength;
+    struct entry **table;
+    unsigned int entrycount;
+    unsigned int loadlimit;
+    unsigned int primeindex;
+    unsigned int (*hashfn) (void *k);
+    int (*eqfn) (void *k1, void *k2);
+};
+
+/*****************************************************************************/
+unsigned int
+hash(struct hashtable *h, void *k);
+
+/*****************************************************************************/
+/* indexFor */
+static inline unsigned int
+indexFor(unsigned int tablelength, unsigned int hashvalue) {
+    return (hashvalue % tablelength);
+};
+
+/* Only works if tablelength == 2^N */
+/*static inline unsigned int
+indexFor(unsigned int tablelength, unsigned int hashvalue)
+{
+    return (hashvalue & (tablelength - 1u));
+}
+*/
+
+/*****************************************************************************/
+#define freekey(X) free(X)
+/*define freekey(X) ; */
+
+
+/*****************************************************************************/
+
+#endif /* __HASHTABLE_PRIVATE_CWC22_H__*/
+
+/*
+ * Copyright (c) 2002, Christopher Clark
+ * All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 
+ * * 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.
+ * 
+ * * Neither the name of the original author; nor the names of any contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ * 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT OWNER
+ * 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.
+*/
diff --git a/mkfs.ubifs/key.h b/mkfs.ubifs/key.h
new file mode 100644
index 0000000..2bdd431
--- /dev/null
+++ b/mkfs.ubifs/key.h
@@ -0,0 +1,533 @@
+/*
+ * This file is part of UBIFS.
+ *
+ * Copyright (C) 2006-2008 Nokia Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy (Битюцкий Артём)
+ *          Adrian Hunter
+ */
+
+/*
+ * This header contains various key-related definitions and helper function.
+ * UBIFS allows several key schemes, so we access key fields only via these
+ * helpers. At the moment only one key scheme is supported.
+ *
+ * Simple key scheme
+ * ~~~~~~~~~~~~~~~~~
+ *
+ * Keys are 64-bits long. First 32-bits are inode number (parent inode number
+ * in case of direntry key). Next 3 bits are node type. The last 29 bits are
+ * 4KiB offset in case of inode node, and direntry hash in case of a direntry
+ * node. We use "r5" hash borrowed from reiserfs.
+ */
+
+#ifndef __UBIFS_KEY_H__
+#define __UBIFS_KEY_H__
+
+/**
+ * key_r5_hash - R5 hash function (borrowed from reiserfs).
+ * @s: direntry name
+ * @len: name length
+ */
+static inline uint32_t key_r5_hash(const char *s, int len)
+{
+	uint32_t a = 0;
+	const signed char *str = (const signed char *)s;
+
+	while (*str) {
+		a += *str << 4;
+		a += *str >> 4;
+		a *= 11;
+		str++;
+	}
+
+	a &= UBIFS_S_KEY_HASH_MASK;
+
+	/*
+	 * We use hash values as offset in directories, so values %0 and %1 are
+	 * reserved for "." and "..". %2 is reserved for "end of readdir"
+	 * marker.
+	 */
+	if (unlikely(a >= 0 && a <= 2))
+		a += 3;
+	return a;
+}
+
+/**
+ * key_test_hash - testing hash function.
+ * @str: direntry name
+ * @len: name length
+ */
+static inline uint32_t key_test_hash(const char *str, int len)
+{
+	uint32_t a = 0;
+
+	len = min_t(uint32_t, len, 4);
+	memcpy(&a, str, len);
+	a &= UBIFS_S_KEY_HASH_MASK;
+	if (unlikely(a >= 0 && a <= 2))
+		a += 3;
+	return a;
+}
+
+/**
+ * ino_key_init - initialize inode key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: inode number
+ */
+static inline void ino_key_init(const struct ubifs_info *c,
+				union ubifs_key *key, ino_t inum)
+{
+	key->u32[0] = inum;
+	key->u32[1] = UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS;
+}
+
+/**
+ * ino_key_init_flash - initialize on-flash inode key.
+ * @c: UBIFS file-system description object
+ * @k: key to initialize
+ * @inum: inode number
+ */
+static inline void ino_key_init_flash(const struct ubifs_info *c, void *k,
+				      ino_t inum)
+{
+	union ubifs_key *key = k;
+
+	key->j32[0] = cpu_to_le32(inum);
+	key->j32[1] = cpu_to_le32(UBIFS_INO_KEY << UBIFS_S_KEY_BLOCK_BITS);
+	memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
+}
+
+/**
+ * lowest_ino_key - get the lowest possible inode key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: inode number
+ */
+static inline void lowest_ino_key(const struct ubifs_info *c,
+				union ubifs_key *key, ino_t inum)
+{
+	key->u32[0] = inum;
+	key->u32[1] = 0;
+}
+
+/**
+ * highest_ino_key - get the highest possible inode key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: inode number
+ */
+static inline void highest_ino_key(const struct ubifs_info *c,
+				union ubifs_key *key, ino_t inum)
+{
+	key->u32[0] = inum;
+	key->u32[1] = 0xffffffff;
+}
+
+/**
+ * dent_key_init - initialize directory entry key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: parent inode number
+ * @nm: direntry name and length
+ */
+static inline void dent_key_init(const struct ubifs_info *c,
+				 union ubifs_key *key, ino_t inum,
+				 const struct qstr *nm)
+{
+	uint32_t hash = c->key_hash(nm->name, nm->len);
+
+	ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
+	key->u32[0] = inum;
+	key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
+}
+
+/**
+ * dent_key_init_hash - initialize directory entry key without re-calculating
+ *                      hash function.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: parent inode number
+ * @hash: direntry name hash
+ */
+static inline void dent_key_init_hash(const struct ubifs_info *c,
+				      union ubifs_key *key, ino_t inum,
+				      uint32_t hash)
+{
+	ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
+	key->u32[0] = inum;
+	key->u32[1] = hash | (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS);
+}
+
+/**
+ * dent_key_init_flash - initialize on-flash directory entry key.
+ * @c: UBIFS file-system description object
+ * @k: key to initialize
+ * @inum: parent inode number
+ * @nm: direntry name and length
+ */
+static inline void dent_key_init_flash(const struct ubifs_info *c, void *k,
+				       ino_t inum, const struct qstr *nm)
+{
+	union ubifs_key *key = k;
+	uint32_t hash = c->key_hash(nm->name, nm->len);
+
+	ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
+	key->j32[0] = cpu_to_le32(inum);
+	key->j32[1] = cpu_to_le32(hash |
+				  (UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS));
+	memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
+}
+
+/**
+ * lowest_dent_key - get the lowest possible directory entry key.
+ * @c: UBIFS file-system description object
+ * @key: where to store the lowest key
+ * @inum: parent inode number
+ */
+static inline void lowest_dent_key(const struct ubifs_info *c,
+				   union ubifs_key *key, ino_t inum)
+{
+	key->u32[0] = inum;
+	key->u32[1] = UBIFS_DENT_KEY << UBIFS_S_KEY_HASH_BITS;
+}
+
+/**
+ * xent_key_init - initialize extended attribute entry key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: host inode number
+ * @nm: extended attribute entry name and length
+ */
+static inline void xent_key_init(const struct ubifs_info *c,
+				 union ubifs_key *key, ino_t inum,
+				 const struct qstr *nm)
+{
+	uint32_t hash = c->key_hash(nm->name, nm->len);
+
+	ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
+	key->u32[0] = inum;
+	key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
+}
+
+/**
+ * xent_key_init_hash - initialize extended attribute entry key without
+ *                      re-calculating hash function.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: host inode number
+ * @hash: extended attribute entry name hash
+ */
+static inline void xent_key_init_hash(const struct ubifs_info *c,
+				      union ubifs_key *key, ino_t inum,
+				      uint32_t hash)
+{
+	ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
+	key->u32[0] = inum;
+	key->u32[1] = hash | (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS);
+}
+
+/**
+ * xent_key_init_flash - initialize on-flash extended attribute entry key.
+ * @c: UBIFS file-system description object
+ * @k: key to initialize
+ * @inum: host inode number
+ * @nm: extended attribute entry name and length
+ */
+static inline void xent_key_init_flash(const struct ubifs_info *c, void *k,
+				       ino_t inum, const struct qstr *nm)
+{
+	union ubifs_key *key = k;
+	uint32_t hash = c->key_hash(nm->name, nm->len);
+
+	ubifs_assert(!(hash & ~UBIFS_S_KEY_HASH_MASK));
+	key->j32[0] = cpu_to_le32(inum);
+	key->j32[1] = cpu_to_le32(hash |
+				  (UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS));
+	memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
+}
+
+/**
+ * lowest_xent_key - get the lowest possible extended attribute entry key.
+ * @c: UBIFS file-system description object
+ * @key: where to store the lowest key
+ * @inum: host inode number
+ */
+static inline void lowest_xent_key(const struct ubifs_info *c,
+				   union ubifs_key *key, ino_t inum)
+{
+	key->u32[0] = inum;
+	key->u32[1] = UBIFS_XENT_KEY << UBIFS_S_KEY_HASH_BITS;
+}
+
+/**
+ * data_key_init - initialize data key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: inode number
+ * @block: block number
+ */
+static inline void data_key_init(const struct ubifs_info *c,
+				 union ubifs_key *key, ino_t inum,
+				 unsigned int block)
+{
+	ubifs_assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK));
+	key->u32[0] = inum;
+	key->u32[1] = block | (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS);
+}
+
+/**
+ * data_key_init_flash - initialize on-flash data key.
+ * @c: UBIFS file-system description object
+ * @k: key to initialize
+ * @inum: inode number
+ * @block: block number
+ */
+static inline void data_key_init_flash(const struct ubifs_info *c, void *k,
+				       ino_t inum, unsigned int block)
+{
+	union ubifs_key *key = k;
+
+	ubifs_assert(!(block & ~UBIFS_S_KEY_BLOCK_MASK));
+	key->j32[0] = cpu_to_le32(inum);
+	key->j32[1] = cpu_to_le32(block |
+				  (UBIFS_DATA_KEY << UBIFS_S_KEY_BLOCK_BITS));
+	memset(k + 8, 0, UBIFS_MAX_KEY_LEN - 8);
+}
+
+/**
+ * trun_key_init - initialize truncation node key.
+ * @c: UBIFS file-system description object
+ * @key: key to initialize
+ * @inum: inode number
+ *
+ * Note, UBIFS does not have truncation keys on the media and this function is
+ * only used for purposes of replay.
+ */
+static inline void trun_key_init(const struct ubifs_info *c,
+				 union ubifs_key *key, ino_t inum)
+{
+	key->u32[0] = inum;
+	key->u32[1] = UBIFS_TRUN_KEY << UBIFS_S_KEY_BLOCK_BITS;
+}
+
+/**
+ * key_type - get key type.
+ * @c: UBIFS file-system description object
+ * @key: key to get type of
+ */
+static inline int key_type(const struct ubifs_info *c,
+			   const union ubifs_key *key)
+{
+	return key->u32[1] >> UBIFS_S_KEY_BLOCK_BITS;
+}
+
+/**
+ * key_type_flash - get type of a on-flash formatted key.
+ * @c: UBIFS file-system description object
+ * @k: key to get type of
+ */
+static inline int key_type_flash(const struct ubifs_info *c, const void *k)
+{
+	const union ubifs_key *key = k;
+
+	return le32_to_cpu(key->u32[1]) >> UBIFS_S_KEY_BLOCK_BITS;
+}
+
+/**
+ * key_ino - fetch inode number from key.
+ * @c: UBIFS file-system description object
+ * @k: key to fetch inode number from
+ */
+static inline ino_t key_ino(const struct ubifs_info *c, const void *k)
+{
+	const union ubifs_key *key = k;
+
+	return key->u32[0];
+}
+
+/**
+ * key_ino_flash - fetch inode number from an on-flash formatted key.
+ * @c: UBIFS file-system description object
+ * @k: key to fetch inode number from
+ */
+static inline ino_t key_ino_flash(const struct ubifs_info *c, const void *k)
+{
+	const union ubifs_key *key = k;
+
+	return le32_to_cpu(key->j32[0]);
+}
+
+/**
+ * key_hash - get directory entry hash.
+ * @c: UBIFS file-system description object
+ * @key: the key to get hash from
+ */
+static inline int key_hash(const struct ubifs_info *c,
+			   const union ubifs_key *key)
+{
+	return key->u32[1] & UBIFS_S_KEY_HASH_MASK;
+}
+
+/**
+ * key_hash_flash - get directory entry hash from an on-flash formatted key.
+ * @c: UBIFS file-system description object
+ * @k: the key to get hash from
+ */
+static inline int key_hash_flash(const struct ubifs_info *c, const void *k)
+{
+	const union ubifs_key *key = k;
+
+	return le32_to_cpu(key->j32[1]) & UBIFS_S_KEY_HASH_MASK;
+}
+
+/**
+ * key_block - get data block number.
+ * @c: UBIFS file-system description object
+ * @key: the key to get the block number from
+ */
+static inline unsigned int key_block(const struct ubifs_info *c,
+				     const union ubifs_key *key)
+{
+	return key->u32[1] & UBIFS_S_KEY_BLOCK_MASK;
+}
+
+/**
+ * key_block_flash - get data block number from an on-flash formatted key.
+ * @c: UBIFS file-system description object
+ * @k: the key to get the block number from
+ */
+static inline unsigned int key_block_flash(const struct ubifs_info *c,
+					   const void *k)
+{
+	const union ubifs_key *key = k;
+
+	return le32_to_cpu(key->u32[1]) & UBIFS_S_KEY_BLOCK_MASK;
+}
+
+/**
+ * key_read - transform a key to in-memory format.
+ * @c: UBIFS file-system description object
+ * @from: the key to transform
+ * @to: the key to store the result
+ */
+static inline void key_read(const struct ubifs_info *c, const void *from,
+			    union ubifs_key *to)
+{
+	const union ubifs_key *f = from;
+
+	to->u32[0] = le32_to_cpu(f->j32[0]);
+	to->u32[1] = le32_to_cpu(f->j32[1]);
+}
+
+/**
+ * key_write - transform a key from in-memory format.
+ * @c: UBIFS file-system description object
+ * @from: the key to transform
+ * @to: the key to store the result
+ */
+static inline void key_write(const struct ubifs_info *c,
+			     const union ubifs_key *from, void *to)
+{
+	union ubifs_key *t = to;
+
+	t->j32[0] = cpu_to_le32(from->u32[0]);
+	t->j32[1] = cpu_to_le32(from->u32[1]);
+	memset(to + 8, 0, UBIFS_MAX_KEY_LEN - 8);
+}
+
+/**
+ * key_write_idx - transform a key from in-memory format for the index.
+ * @c: UBIFS file-system description object
+ * @from: the key to transform
+ * @to: the key to store the result
+ */
+static inline void key_write_idx(const struct ubifs_info *c,
+				 const union ubifs_key *from, void *to)
+{
+	union ubifs_key *t = to;
+
+	t->j32[0] = cpu_to_le32(from->u32[0]);
+	t->j32[1] = cpu_to_le32(from->u32[1]);
+}
+
+/**
+ * key_copy - copy a key.
+ * @c: UBIFS file-system description object
+ * @from: the key to copy from
+ * @to: the key to copy to
+ */
+static inline void key_copy(const struct ubifs_info *c,
+			    const union ubifs_key *from, union ubifs_key *to)
+{
+	to->u64[0] = from->u64[0];
+}
+
+/**
+ * keys_cmp - compare keys.
+ * @c: UBIFS file-system description object
+ * @key1: the first key to compare
+ * @key2: the second key to compare
+ *
+ * This function compares 2 keys and returns %-1 if @key1 is less than
+ * @key2, 0 if the keys are equivalent and %1 if @key1 is greater than @key2.
+ */
+static inline int keys_cmp(const struct ubifs_info *c,
+			   const union ubifs_key *key1,
+			   const union ubifs_key *key2)
+{
+	if (key1->u32[0] < key2->u32[0])
+		return -1;
+	if (key1->u32[0] > key2->u32[0])
+		return 1;
+	if (key1->u32[1] < key2->u32[1])
+		return -1;
+	if (key1->u32[1] > key2->u32[1])
+		return 1;
+
+	return 0;
+}
+
+/**
+ * is_hash_key - is a key vulnerable to hash collisions.
+ * @c: UBIFS file-system description object
+ * @key: key
+ *
+ * This function returns %1 if @key is a hashed key or %0 otherwise.
+ */
+static inline int is_hash_key(const struct ubifs_info *c,
+			      const union ubifs_key *key)
+{
+	int type = key_type(c, key);
+
+	return type == UBIFS_DENT_KEY || type == UBIFS_XENT_KEY;
+}
+
+/**
+ * key_max_inode_size - get maximum file size allowed by current key format.
+ * @c: UBIFS file-system description object
+ */
+static inline unsigned long long key_max_inode_size(const struct ubifs_info *c)
+{
+	switch (c->key_fmt) {
+	case UBIFS_SIMPLE_KEY_FMT:
+		return (1ULL << UBIFS_S_KEY_BLOCK_BITS) * UBIFS_BLOCK_SIZE;
+	default:
+		return 0;
+	}
+}
+#endif /* !__UBIFS_KEY_H__ */
diff --git a/mkfs.ubifs/lpt.c b/mkfs.ubifs/lpt.c
new file mode 100644
index 0000000..48ae03f
--- /dev/null
+++ b/mkfs.ubifs/lpt.c
@@ -0,0 +1,577 @@
+/*
+ * This file is part of UBIFS.
+ *
+ * Copyright (C) 2006, 2007 Nokia Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Adrian Hunter
+ *          Artem Bityutskiy
+ */
+
+#include "mkfs.ubifs.h"
+
+/**
+ * do_calc_lpt_geom - calculate sizes for the LPT area.
+ * @c: the UBIFS file-system description object
+ *
+ * Calculate the sizes of LPT bit fields, nodes, and tree, based on the
+ * properties of the flash and whether LPT is "big" (c->big_lpt).
+ */
+static void do_calc_lpt_geom(struct ubifs_info *c)
+{
+	int n, bits, per_leb_wastage;
+	long long sz, tot_wastage;
+
+	c->pnode_cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT;
+
+	n = (c->pnode_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT;
+	c->nnode_cnt = n;
+	while (n > 1) {
+		n = (n + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT;
+		c->nnode_cnt += n;
+	}
+
+	c->lpt_hght = 1;
+	n = UBIFS_LPT_FANOUT;
+	while (n < c->pnode_cnt) {
+		c->lpt_hght += 1;
+		n <<= UBIFS_LPT_FANOUT_SHIFT;
+	}
+
+	c->space_bits = fls(c->leb_size) - 3;
+	c->lpt_lnum_bits = fls(c->lpt_lebs);
+	c->lpt_offs_bits = fls(c->leb_size - 1);
+	c->lpt_spc_bits = fls(c->leb_size);
+
+	n = (c->max_leb_cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT;
+	c->pcnt_bits = fls(n - 1);
+
+	c->lnum_bits = fls(c->max_leb_cnt - 1);
+
+	bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
+	       (c->big_lpt ? c->pcnt_bits : 0) +
+	       (c->space_bits * 2 + 1) * UBIFS_LPT_FANOUT;
+	c->pnode_sz = (bits + 7) / 8;
+
+	bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
+	       (c->big_lpt ? c->pcnt_bits : 0) +
+	       (c->lpt_lnum_bits + c->lpt_offs_bits) * UBIFS_LPT_FANOUT;
+	c->nnode_sz = (bits + 7) / 8;
+
+	bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
+	       c->lpt_lebs * c->lpt_spc_bits * 2;
+	c->ltab_sz = (bits + 7) / 8;
+
+	bits = UBIFS_LPT_CRC_BITS + UBIFS_LPT_TYPE_BITS +
+	       c->lnum_bits * c->lsave_cnt;
+	c->lsave_sz = (bits + 7) / 8;
+
+	/* Calculate the minimum LPT size */
+	c->lpt_sz = (long long)c->pnode_cnt * c->pnode_sz;
+	c->lpt_sz += (long long)c->nnode_cnt * c->nnode_sz;
+	c->lpt_sz += c->ltab_sz;
+	c->lpt_sz += c->lsave_sz;
+
+	/* Add wastage */
+	sz = c->lpt_sz;
+	per_leb_wastage = max_t(int, c->pnode_sz, c->nnode_sz);
+	sz += per_leb_wastage;
+	tot_wastage = per_leb_wastage;
+	while (sz > c->leb_size) {
+		sz += per_leb_wastage;
+		sz -= c->leb_size;
+		tot_wastage += per_leb_wastage;
+	}
+	tot_wastage += ALIGN(sz, c->min_io_size) - sz;
+	c->lpt_sz += tot_wastage;
+}
+
+/**
+ * calc_dflt_lpt_geom - calculate default LPT geometry.
+ * @c: the UBIFS file-system description object
+ * @main_lebs: number of main area LEBs is passed and returned here
+ * @big_lpt: whether the LPT area is "big" is returned here
+ *
+ * The size of the LPT area depends on parameters that themselves are dependent
+ * on the size of the LPT area. This function, successively recalculates the LPT
+ * area geometry until the parameters and resultant geometry are consistent.
+ *
+ * This function returns %0 on success and a negative error code on failure.
+ */
+int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt)
+{
+	int i, lebs_needed;
+	long long sz;
+
+	/* Start by assuming the minimum number of LPT LEBs */
+	c->lpt_lebs = UBIFS_MIN_LPT_LEBS;
+	c->main_lebs = *main_lebs - c->lpt_lebs;
+	if (c->main_lebs <= 0)
+		return -EINVAL;
+
+	/* And assume we will use the small LPT model */
+	c->big_lpt = 0;
+
+	/*
+	 * Calculate the geometry based on assumptions above and then see if it
+	 * makes sense
+	 */
+	do_calc_lpt_geom(c);
+
+	/* Small LPT model must have lpt_sz < leb_size */
+	if (c->lpt_sz > c->leb_size) {
+		/* Nope, so try again using big LPT model */
+		c->big_lpt = 1;
+		do_calc_lpt_geom(c);
+	}
+
+	/* Now check there are enough LPT LEBs */
+	for (i = 0; i < 64 ; i++) {
+		sz = c->lpt_sz * 4; /* Allow 4 times the size */
+		sz += c->leb_size - 1;
+		do_div(sz, c->leb_size);
+		lebs_needed = sz;
+		if (lebs_needed > c->lpt_lebs) {
+			/* Not enough LPT LEBs so try again with more */
+			c->lpt_lebs = lebs_needed;
+			c->main_lebs = *main_lebs - c->lpt_lebs;
+			if (c->main_lebs <= 0)
+				return -EINVAL;
+			do_calc_lpt_geom(c);
+			continue;
+		}
+		if (c->ltab_sz > c->leb_size) {
+			err_msg("LPT ltab too big");
+			return -EINVAL;
+		}
+		*main_lebs = c->main_lebs;
+		*big_lpt = c->big_lpt;
+		return 0;
+	}
+	return -EINVAL;
+}
+
+/**
+ * pack_bits - pack bit fields end-to-end.
+ * @addr: address at which to pack (passed and next address returned)
+ * @pos: bit position at which to pack (passed and next position returned)
+ * @val: value to pack
+ * @nrbits: number of bits of value to pack (1-32)
+ */
+static void pack_bits(uint8_t **addr, int *pos, uint32_t val, int nrbits)
+{
+	uint8_t *p = *addr;
+	int b = *pos;
+
+	if (b) {
+		*p |= ((uint8_t)val) << b;
+		nrbits += b;
+		if (nrbits > 8) {
+			*++p = (uint8_t)(val >>= (8 - b));
+			if (nrbits > 16) {
+				*++p = (uint8_t)(val >>= 8);
+				if (nrbits > 24) {
+					*++p = (uint8_t)(val >>= 8);
+					if (nrbits > 32)
+						*++p = (uint8_t)(val >>= 8);
+				}
+			}
+		}
+	} else {
+		*p = (uint8_t)val;
+		if (nrbits > 8) {
+			*++p = (uint8_t)(val >>= 8);
+			if (nrbits > 16) {
+				*++p = (uint8_t)(val >>= 8);
+				if (nrbits > 24)
+					*++p = (uint8_t)(val >>= 8);
+			}
+		}
+	}
+	b = nrbits & 7;
+	if (b == 0)
+		p++;
+	*addr = p;
+	*pos = b;
+}
+
+/**
+ * pack_pnode - pack all the bit fields of a pnode.
+ * @c: UBIFS file-system description object
+ * @buf: buffer into which to pack
+ * @pnode: pnode to pack
+ */
+static void pack_pnode(struct ubifs_info *c, void *buf,
+		       struct ubifs_pnode *pnode)
+{
+	uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
+	int i, pos = 0;
+	uint16_t crc;
+
+	pack_bits(&addr, &pos, UBIFS_LPT_PNODE, UBIFS_LPT_TYPE_BITS);
+	if (c->big_lpt)
+		pack_bits(&addr, &pos, pnode->num, c->pcnt_bits);
+	for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
+		pack_bits(&addr, &pos, pnode->lprops[i].free >> 3,
+			  c->space_bits);
+		pack_bits(&addr, &pos, pnode->lprops[i].dirty >> 3,
+			  c->space_bits);
+		if (pnode->lprops[i].flags & LPROPS_INDEX)
+			pack_bits(&addr, &pos, 1, 1);
+		else
+			pack_bits(&addr, &pos, 0, 1);
+	}
+	crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
+		    c->pnode_sz - UBIFS_LPT_CRC_BYTES);
+	addr = buf;
+	pos = 0;
+	pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
+}
+
+/**
+ * pack_nnode - pack all the bit fields of a nnode.
+ * @c: UBIFS file-system description object
+ * @buf: buffer into which to pack
+ * @nnode: nnode to pack
+ */
+static void pack_nnode(struct ubifs_info *c, void *buf,
+		       struct ubifs_nnode *nnode)
+{
+	uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
+	int i, pos = 0;
+	uint16_t crc;
+
+	pack_bits(&addr, &pos, UBIFS_LPT_NNODE, UBIFS_LPT_TYPE_BITS);
+	if (c->big_lpt)
+		pack_bits(&addr, &pos, nnode->num, c->pcnt_bits);
+	for (i = 0; i < UBIFS_LPT_FANOUT; i++) {
+		int lnum = nnode->nbranch[i].lnum;
+
+		if (lnum == 0)
+			lnum = c->lpt_last + 1;
+		pack_bits(&addr, &pos, lnum - c->lpt_first, c->lpt_lnum_bits);
+		pack_bits(&addr, &pos, nnode->nbranch[i].offs,
+			  c->lpt_offs_bits);
+	}
+	crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
+		    c->nnode_sz - UBIFS_LPT_CRC_BYTES);
+	addr = buf;
+	pos = 0;
+	pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
+}
+
+/**
+ * pack_ltab - pack the LPT's own lprops table.
+ * @c: UBIFS file-system description object
+ * @buf: buffer into which to pack
+ * @ltab: LPT's own lprops table to pack
+ */
+static void pack_ltab(struct ubifs_info *c, void *buf,
+			 struct ubifs_lpt_lprops *ltab)
+{
+	uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
+	int i, pos = 0;
+	uint16_t crc;
+
+	pack_bits(&addr, &pos, UBIFS_LPT_LTAB, UBIFS_LPT_TYPE_BITS);
+	for (i = 0; i < c->lpt_lebs; i++) {
+		pack_bits(&addr, &pos, ltab[i].free, c->lpt_spc_bits);
+		pack_bits(&addr, &pos, ltab[i].dirty, c->lpt_spc_bits);
+	}
+	crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
+		    c->ltab_sz - UBIFS_LPT_CRC_BYTES);
+	addr = buf;
+	pos = 0;
+	pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
+}
+
+/**
+ * pack_lsave - pack the LPT's save table.
+ * @c: UBIFS file-system description object
+ * @buf: buffer into which to pack
+ * @lsave: LPT's save table to pack
+ */
+static void pack_lsave(struct ubifs_info *c, void *buf, int *lsave)
+{
+	uint8_t *addr = buf + UBIFS_LPT_CRC_BYTES;
+	int i, pos = 0;
+	uint16_t crc;
+
+	pack_bits(&addr, &pos, UBIFS_LPT_LSAVE, UBIFS_LPT_TYPE_BITS);
+	for (i = 0; i < c->lsave_cnt; i++)
+		pack_bits(&addr, &pos, lsave[i], c->lnum_bits);
+	crc = crc16(-1, buf + UBIFS_LPT_CRC_BYTES,
+		    c->lsave_sz - UBIFS_LPT_CRC_BYTES);
+	addr = buf;
+	pos = 0;
+	pack_bits(&addr, &pos, crc, UBIFS_LPT_CRC_BITS);
+}
+
+/**
+ * set_ltab - set LPT LEB properties.
+ * @c: UBIFS file-system description object
+ * @lnum: LEB number
+ * @free: amount of free space
+ * @dirty: amount of dirty space
+ */
+static void set_ltab(struct ubifs_info *c, int lnum, int free, int dirty)
+{
+	dbg_msg(3, "LEB %d free %d dirty %d to %d %d",
+		lnum, c->ltab[lnum - c->lpt_first].free,
+		c->ltab[lnum - c->lpt_first].dirty, free, dirty);
+	c->ltab[lnum - c->lpt_first].free = free;
+	c->ltab[lnum - c->lpt_first].dirty = dirty;
+}
+
+/**
+ * calc_nnode_num - calculate nnode number.
+ * @row: the row in the tree (root is zero)
+ * @col: the column in the row (leftmost is zero)
+ *
+ * The nnode number is a number that uniquely identifies a nnode and can be used
+ * easily to traverse the tree from the root to that nnode.
+ *
+ * This function calculates and returns the nnode number for the nnode at @row
+ * and @col.
+ */
+static int calc_nnode_num(int row, int col)
+{
+	int num, bits;
+
+	num = 1;
+	while (row--) {
+		bits = (col & (UBIFS_LPT_FANOUT - 1));
+		col >>= UBIFS_LPT_FANOUT_SHIFT;
+		num <<= UBIFS_LPT_FANOUT_SHIFT;
+		num |= bits;
+	}
+	return num;
+}
+
+/**
+ * create_lpt - create LPT.
+ * @c: UBIFS file-system description object
+ *
+ * This function returns %0 on success and a negative error code on failure.
+ */
+int create_lpt(struct ubifs_info *c)
+{
+	int lnum, err = 0, i, j, cnt, len, alen, row;
+	int blnum, boffs, bsz, bcnt;
+	struct ubifs_pnode *pnode = NULL;
+	struct ubifs_nnode *nnode = NULL;
+	void *buf = NULL, *p;
+	int *lsave = NULL;
+
+	pnode = malloc(sizeof(struct ubifs_pnode));
+	nnode = malloc(sizeof(struct ubifs_nnode));
+	buf = malloc(c->leb_size);
+	lsave = malloc(sizeof(int) * c->lsave_cnt);
+	if (!pnode || !nnode || !buf || !lsave) {
+		err = -ENOMEM;
+		goto out;
+	}
+	memset(pnode, 0 , sizeof(struct ubifs_pnode));
+	memset(nnode, 0 , sizeof(struct ubifs_pnode));
+
+	c->lscan_lnum = c->main_first;
+
+	lnum = c->lpt_first;
+	p = buf;
+	len = 0;
+	/* Number of leaf nodes (pnodes) */
+	cnt = (c->main_lebs + UBIFS_LPT_FANOUT - 1) >> UBIFS_LPT_FANOUT_SHIFT;
+	//printf("pnode_cnt=%d\n",cnt);
+
+	/*
+	 * To calculate the internal node branches, we keep information about
+	 * the level below.
+	 */
+	blnum = lnum; /* LEB number of level below */
+	boffs = 0; /* Offset of level below */
+	bcnt = cnt; /* Number of nodes in level below */
+	bsz = c->pnode_sz; /* Size of nodes in level below */
+
+	/* Add pnodes */
+	for (i = 0; i < cnt; i++) {
+		if (len + c->pnode_sz > c->leb_size) {
+			alen = ALIGN(len, c->min_io_size);
+			set_ltab(c, lnum, c->leb_size - alen, alen - len);
+			memset(p, 0xff, alen - len);
+			err = write_leb(lnum++, alen, buf);
+			if (err)
+				goto out;
+			p = buf;
+			len = 0;
+		}
+		/* Fill in the pnode */
+		for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
+			int k = (i << UBIFS_LPT_FANOUT_SHIFT) + j;
+
+			if (k < c->main_lebs)
+				pnode->lprops[j] = c->lpt[k];
+			else {
+				pnode->lprops[j].free = c->leb_size;
+				pnode->lprops[j].dirty = 0;
+				pnode->lprops[j].flags = 0;
+			}
+		}
+		pack_pnode(c, p, pnode);
+		p += c->pnode_sz;
+		len += c->pnode_sz;
+		/*
+		 * pnodes are simply numbered left to right starting at zero,
+		 * which means the pnode number can be used easily to traverse
+		 * down the tree to the corresponding pnode.
+		 */
+		pnode->num += 1;
+	}
+
+	row = c->lpt_hght - 1;
+	/* Add all nnodes, one level at a time */
+	while (1) {
+		/* Number of internal nodes (nnodes) at next level */
+		cnt = (cnt + UBIFS_LPT_FANOUT - 1) / UBIFS_LPT_FANOUT;
+		if (cnt == 0)
+			cnt = 1;
+		for (i = 0; i < cnt; i++) {
+			if (len + c->nnode_sz > c->leb_size) {
+				alen = ALIGN(len, c->min_io_size);
+				set_ltab(c, lnum, c->leb_size - alen,
+					    alen - len);
+				memset(p, 0xff, alen - len);
+				err = write_leb(lnum++, alen, buf);
+				if (err)
+					goto out;
+				p = buf;
+				len = 0;
+			}
+			/* The root is on row zero */
+			if (row == 0) {
+				c->lpt_lnum = lnum;
+				c->lpt_offs = len;
+			}
+			/* Set branches to the level below */
+			for (j = 0; j < UBIFS_LPT_FANOUT; j++) {
+				if (bcnt) {
+					if (boffs + bsz > c->leb_size) {
+						blnum += 1;
+						boffs = 0;
+					}
+					nnode->nbranch[j].lnum = blnum;
+					nnode->nbranch[j].offs = boffs;
+					boffs += bsz;
+					bcnt--;
+				} else {
+					nnode->nbranch[j].lnum = 0;
+					nnode->nbranch[j].offs = 0;
+				}
+			}
+			nnode->num = calc_nnode_num(row, i);
+			pack_nnode(c, p, nnode);
+			p += c->nnode_sz;
+			len += c->nnode_sz;
+		}
+		/* Row zero  is the top row */
+		if (row == 0)
+			break;
+		/* Update the information about the level below */
+		bcnt = cnt;
+		bsz = c->nnode_sz;
+		row -= 1;
+	}
+
+	if (c->big_lpt) {
+		/* Need to add LPT's save table */
+		if (len + c->lsave_sz > c->leb_size) {
+			alen = ALIGN(len, c->min_io_size);
+			set_ltab(c, lnum, c->leb_size - alen, alen - len);
+			memset(p, 0xff, alen - len);
+			err = write_leb(lnum++, alen, buf);
+			if (err)
+				goto out;
+			p = buf;
+			len = 0;
+		}
+
+		c->lsave_lnum = lnum;
+		c->lsave_offs = len;
+
+		for (i = 0; i < c->lsave_cnt; i++)
+			lsave[i] = c->main_first + i;
+
+		pack_lsave(c, p, lsave);
+		p += c->lsave_sz;
+		len += c->lsave_sz;
+	}
+
+	/* Need to add LPT's own LEB properties table */
+	if (len + c->ltab_sz > c->leb_size) {
+		alen = ALIGN(len, c->min_io_size);
+		set_ltab(c, lnum, c->leb_size - alen, alen - len);
+		memset(p, 0xff, alen - len);
+		err = write_leb(lnum++, alen, buf);
+		if (err)
+			goto out;
+		p = buf;
+		len = 0;
+	}
+
+	c->ltab_lnum = lnum;
+	c->ltab_offs = len;
+
+	/* Update ltab before packing it */
+	len += c->ltab_sz;
+	alen = ALIGN(len, c->min_io_size);
+	set_ltab(c, lnum, c->leb_size - alen, alen - len);
+
+	pack_ltab(c, p, c->ltab);
+	p += c->ltab_sz;
+
+	/* Write remaining buffer */
+	memset(p, 0xff, alen - len);
+	err = write_leb(lnum, alen, buf);
+	if (err)
+		goto out;
+
+	c->nhead_lnum = lnum;
+	c->nhead_offs = ALIGN(len, c->min_io_size);
+
+	dbg_msg(1, "space_bits:     %d", c->space_bits);
+	dbg_msg(1, "lpt_lnum_bits:  %d", c->lpt_lnum_bits);
+	dbg_msg(1, "lpt_offs_bits:  %d", c->lpt_offs_bits);
+	dbg_msg(1, "lpt_spc_bits:   %d", c->lpt_spc_bits);
+	dbg_msg(1, "pcnt_bits:      %d", c->pcnt_bits);
+	dbg_msg(1, "lnum_bits:      %d", c->lnum_bits);
+	dbg_msg(1, "pnode_sz:       %d", c->pnode_sz);
+	dbg_msg(1, "nnode_sz:       %d", c->nnode_sz);
+	dbg_msg(1, "ltab_sz:        %d", c->ltab_sz);
+	dbg_msg(1, "lsave_sz:       %d", c->lsave_sz);
+	dbg_msg(1, "lsave_cnt:      %d", c->lsave_cnt);
+	dbg_msg(1, "lpt_hght:       %d", c->lpt_hght);
+	dbg_msg(1, "big_lpt:        %d", c->big_lpt);
+	dbg_msg(1, "LPT root is at  %d:%d", c->lpt_lnum, c->lpt_offs);
+	dbg_msg(1, "LPT head is at  %d:%d", c->nhead_lnum, c->nhead_offs);
+	dbg_msg(1, "LPT ltab is at  %d:%d", c->ltab_lnum, c->ltab_offs);
+	if (c->big_lpt)
+		dbg_msg(1, "LPT lsave is at %d:%d",
+		        c->lsave_lnum, c->lsave_offs);
+out:
+	free(lsave);
+	free(buf);
+	free(nnode);
+	free(pnode);
+	return err;
+}
diff --git a/mkfs.ubifs/lpt.h b/mkfs.ubifs/lpt.h
new file mode 100644
index 0000000..4cde59d
--- /dev/null
+++ b/mkfs.ubifs/lpt.h
@@ -0,0 +1,28 @@
+/*
+ * Copyright (C) 2008 Nokia Corporation.
+ * Copyright (C) 2008 University of Szeged, Hungary
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy
+ *          Adrian Hunter
+ */
+
+#ifndef __UBIFS_LPT_H__
+#define __UBIFS_LPT_H__
+
+int calc_dflt_lpt_geom(struct ubifs_info *c, int *main_lebs, int *big_lpt);
+int create_lpt(struct ubifs_info *c);
+
+#endif
diff --git a/mkfs.ubifs/mkfs.ubifs.c b/mkfs.ubifs/mkfs.ubifs.c
new file mode 100644
index 0000000..419a9f1
--- /dev/null
+++ b/mkfs.ubifs/mkfs.ubifs.c
@@ -0,0 +1,2167 @@
+/*
+ * Copyright (C) 2008 Nokia Corporation.
+ * Copyright (C) 2008 University of Szeged, Hungary
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Adrian Hunter
+ *          Artem Bityutskiy
+ *          Zoltan Sogor
+ */
+
+#include "mkfs.ubifs.h"
+
+#define PROGRAM_VERSION "0.7"
+
+/* Size (prime number) of hash table for link counting */
+#define HASH_TABLE_SIZE 10099
+
+/* The node buffer must allow for worst case compression */
+#define NODE_BUFFER_SIZE (UBIFS_DATA_NODE_SZ + UBIFS_BLOCK_SIZE * 4)
+
+/* Default time granularity in nanoseconds */
+#define DEFAULT_TIME_GRAN 1000000000
+
+/**
+ * struct idx_entry - index entry.
+ * @next: next index entry (NULL at end of list)
+ * @prev: previous index entry (NULL at beginning of list)
+ * @key: key
+ * @name: directory entry name used for sorting colliding keys by name
+ * @lnum: LEB number
+ * @offs: offset
+ * @len: length
+ *
+ * The index is recorded as a linked list which is sorted and used to create
+ * the bottom level of the on-flash index tree. The remaining levels of the
+ * index tree are each built from the level below.
+ */
+struct idx_entry {
+	struct idx_entry *next;
+	struct idx_entry *prev;
+	union ubifs_key key;
+	char *name;
+	int lnum;
+	int offs;
+	int len;
+};
+
+/**
+ * struct inum_mapping - inode number mapping for link counting.
+ * @next: next inum_mapping (NULL at end of list)
+ * @prev: previous inum_mapping (NULL at beginning of list)
+ * @dev: source device on which the source inode number resides
+ * @inum: source inode number of the file
+ * @use_inum: target inode number of the file
+ * @use_nlink: number of links
+ * @path_name: a path name of the file
+ * @st: struct stat object containing inode attributes which have to be used
+ *      when the inode is being created (actually only UID, GID, access
+ *      mode, major and minor device numbers)
+ *
+ * If a file has more than one hard link, then the number of hard links that
+ * exist in the source directory hierarchy must be counted to exclude the
+ * possibility that the file is linked from outside the source directory
+ * hierarchy.
+ *
+ * The inum_mappings are stored in a hash_table of linked lists.
+ */
+struct inum_mapping {
+	struct inum_mapping *next;
+	struct inum_mapping *prev;
+	dev_t dev;
+	ino_t inum;
+	ino_t use_inum;
+	unsigned int use_nlink;
+	char *path_name;
+	struct stat st;
+};
+
+/*
+ * Because we copy functions from the kernel, we use a subset of the UBIFS
+ * file-system description object struct ubifs_info.
+ */
+static struct ubifs_info info_, *c = &info_;
+
+/* Debug levels are: 0 (none), 1 (statistics), 2 (files) ,3 (more details) */
+int debug_level;
+int verbose;
+
+static char *root;
+static int root_len;
+static struct stat root_st;
+static char *output;
+static int out_fd;
+static int squash_owner;
+
+/* The 'head' (position) which nodes are written */
+static int head_lnum;
+static int head_offs;
+static int head_flags;
+
+/* The index list */
+static struct idx_entry *idx_list_first;
+static struct idx_entry *idx_list_last;
+static size_t idx_cnt;
+
+/* Global buffers */
+static void *leb_buf;
+static void *node_buf;
+static void *block_buf;
+
+/* Hash table for inode link counting */
+static struct inum_mapping **hash_table;
+
+/* Inode creation sequence number */
+static unsigned long long creat_sqnum;
+
+static const char *optstring = "d:r:m:o:D:h?vVe:c:g:f:P:k:x:j:l:j:U";
+
+static const struct option longopts[] = {
+	{"root",          1, NULL, 'r'},
+	{"min-io-size",   1, NULL, 'm'},
+	{"leb-size",      1, NULL, 'e'},
+	{"max-leb-cnt",   1, NULL, 'c'},
+	{"output",        1, NULL, 'o'},
+	{"devtable",      1, NULL, 'D'},
+	{"help",          0, NULL, 'h'},
+	{"verbose",       0, NULL, 'v'},
+	{"version",       0, NULL, 'V'},
+	{"debug-level",   1, NULL, 'g'},
+	{"jrn-size",      1, NULL, 'j'},
+	{"compr",         1, NULL, 'x'},
+	{"fanout",        1, NULL, 'f'},
+	{"keyhash",       1, NULL, 'k'},
+	{"log-lebs",      1, NULL, 'l'},
+	{"orph-lebs",     1, NULL, 'p'},
+	{"squash-uids" ,  0, NULL, 'U'},
+	{NULL, 0, NULL, 0}
+};
+
+static const char *helptext =
+"Usage: mkfs.ubifs [OPTIONS]\n"
+"Make a UBIFS file system image from an existing directory tree\n\n"
+"Options:\n"
+"-r, -d, --root=DIR       build file system from directory DIR\n"
+"-m, --min-io-size=SIZE   minimum I/O unit size\n"
+"-e, --leb-size=SIZE      logical erase block size\n"
+"-c, --max-leb-cnt=COUNT  maximum logical erase block count\n"
+"-o, --output=FILE        output to FILE\n"
+"-j, --jrn-size=SIZE      journal size\n"
+"-x, --compr=TYPE         compression type - \"lzo\", \"zlib\" or \"none\"\n"
+"                         (default: \"lzo\")\n"
+"-f, --fanout=NUM         fanout NUM (default: 8)\n"
+"-k, --keyhash=TYPE       key hash type - \"r5\" or \"test\" (default: \"r5\")\n"
+"-l, --log-lebs=COUNT     count of erase blocks for the log\n"
+"-p, --orph-lebs=COUNT    count of erase blocks for orphans (default: 1)\n"
+"-D, --devtable=FILE      use device table FILE\n"
+"-U, --squash-uids        squash owners making all files owned by root\n"
+"-v, --verbose            verbose operation\n"
+"-V, --version            display version information\n"
+"-g, --debug=LEVEL        display debug information (0 - none, 1 - statistics,\n"
+"                         2 - files, 3 - more details)\n"
+"-h, --help               display this help text\n\n"
+"Note, SIZE is specified in bytes, but it may also be specified in Kilobytes,\n"
+"Megabytes, and Gigabytes if a KiB, MiB, or GiB suffix is used.\n";
+
+/**
+ * make_path - make a path name from a directory and a name.
+ * @dir: directory path name
+ * @name: name
+ */
+static char *make_path(const char *dir, const char *name)
+{
+	char *s;
+
+	s = malloc(strlen(dir) + strlen(name) + 2);
+	if (!s)
+		return NULL;
+	strcpy(s, dir);
+	if (dir[strlen(dir) - 1] != '/')
+		strcat(s, "/");
+	strcat(s, name);
+	return s;
+}
+
+/**
+ * same_dir - determine if two file descriptors refer to the same directory.
+ * @fd1: file descriptor 1
+ * @fd2: file descriptor 2
+ */
+static int same_dir(int fd1, int fd2)
+{
+	struct stat stat1, stat2;
+
+	if (fstat(fd1, &stat1) == -1)
+		return -1;
+	if (fstat(fd2, &stat2) == -1)
+		return -1;
+	return stat1.st_dev == stat2.st_dev && stat1.st_ino == stat2.st_ino;
+}
+
+/**
+ * do_openat - open a file in a directory.
+ * @fd: file descriptor of open directory
+ * @path: path relative to directory
+ * @flags: open flags
+ *
+ * This function is provided because the library function openat is sometimes
+ * not available.
+ */
+static int do_openat(int fd, const char *path, int flags)
+{
+	int ret;
+	char *cwd;
+
+	cwd = getcwd(NULL, 0);
+	if (!cwd)
+		return -1;
+	ret = fchdir(fd);
+	if (ret != -1)
+		ret = open(path, flags);
+	chdir(cwd);
+	free(cwd);
+	return ret;
+}
+
+/**
+ * in_path - determine if a file is beneath a directory.
+ * @dir_name: directory path name
+ * @file_name: file path name
+ */
+static int in_path(const char *dir_name, const char *file_name)
+{
+	char *fn = strdup(file_name);
+	char *dn;
+	int fd1, fd2, fd3, ret = -1, top_fd;
+
+	if (!fn)
+		return -1;
+	top_fd = open("/", O_RDONLY);
+	if (top_fd != -1) {
+		dn = dirname(fn);
+		fd1 = open(dir_name, O_RDONLY);
+		if (fd1 != -1) {
+			fd2 = open(dn, O_RDONLY);
+			if (fd2 != -1) {
+				while (1) {
+					int same;
+
+					same = same_dir(fd1, fd2);
+					if (same) {
+						ret = same;
+						break;
+					}
+					if (same_dir(fd2, top_fd)) {
+						ret = 0;
+						break;
+					}
+					fd3 = do_openat(fd2, "..", O_RDONLY);
+					if (fd3 == -1)
+						break;
+					close(fd2);
+					fd2 = fd3;
+				}
+				close(fd2);
+			}
+			close(fd1);
+		}
+		close(top_fd);
+	}
+	free(fn);
+	return ret;
+}
+
+/**
+ * calc_min_log_lebs - calculate the minimum number of log LEBs needed.
+ * @max_bud_bytes: journal size (buds only)
+ */
+static int calc_min_log_lebs(unsigned long long max_bud_bytes)
+{
+	int buds, log_lebs;
+	unsigned long long log_size;
+
+	buds = (max_bud_bytes + c->leb_size - 1) / c->leb_size;
+	log_size = ALIGN(UBIFS_REF_NODE_SZ, c->min_io_size);
+	log_size *= buds;
+	log_size += ALIGN(UBIFS_CS_NODE_SZ +
+			  UBIFS_REF_NODE_SZ * (c->jhead_cnt + 2),
+			  c->min_io_size);
+	log_lebs = (log_size + c->leb_size - 1) / c->leb_size;
+	log_lebs += 1;
+	return log_lebs;
+}
+
+static inline int is_power_of_2(unsigned long long n)
+{
+                return (n != 0 && ((n & (n - 1)) == 0));
+}
+
+static int validate_options(void)
+{
+	int tmp;
+
+	if (!root)
+		return err_msg("root directory was not specified");
+	if (!output)
+		return err_msg("no output file specified");
+	if (in_path(root, output))
+		return err_msg("output file cannot be in the UBIFS root "
+			       "directory");
+	if (!is_power_of_2(c->min_io_size))
+		return err_msg("min. I/O unit size should be power of 2");
+	if (c->leb_size < c->min_io_size)
+		return err_msg("min. I/O unit cannot be larger than LEB size");
+	if (c->leb_size < UBIFS_MIN_LEB_SZ)
+		return err_msg("too smal LEB size %d, minimum is %d",
+			       c->min_io_size, UBIFS_MIN_LEB_SZ);
+	if (c->leb_size % c->min_io_size)
+		return err_msg("LEB should be multiple of min. I/O units");
+	if (c->leb_size % 8)
+		return err_msg("LEB size has to be multiple of 8");
+	if (c->leb_size > 1024*1024)
+		return err_msg("too large LEB size %d", c->leb_size);
+	if (c->max_leb_cnt < UBIFS_MIN_LEB_CNT)
+		return err_msg("too low max. count of LEBs, minimum is %d",
+			       UBIFS_MIN_LEB_CNT);
+	if (c->fanout < UBIFS_MIN_FANOUT)
+		return err_msg("too low fanout, minimum is %d",
+			       UBIFS_MIN_FANOUT);
+	tmp = c->leb_size - UBIFS_IDX_NODE_SZ;
+	tmp /= UBIFS_BRANCH_SZ + UBIFS_MAX_KEY_LEN;
+	if (c->fanout > tmp)
+		return err_msg("too high fanout, maximum is %d", tmp);
+	if (c->log_lebs < UBIFS_MIN_LOG_LEBS)
+		return err_msg("too few log LEBs, minimum is %d",
+			       UBIFS_MIN_LOG_LEBS);
+	if (c->log_lebs >= c->max_leb_cnt - UBIFS_MIN_LEB_CNT)
+		return err_msg("too many log LEBs, maximum is %d",
+			       c->max_leb_cnt - UBIFS_MIN_LEB_CNT);
+	if (c->orph_lebs < UBIFS_MIN_ORPH_LEBS)
+		return err_msg("too few orphan LEBs, minimum is %d",
+			       UBIFS_MIN_ORPH_LEBS);
+	if (c->orph_lebs >= c->max_leb_cnt - UBIFS_MIN_LEB_CNT)
+		return err_msg("too many orphan LEBs, maximum is %d",
+			       c->max_leb_cnt - UBIFS_MIN_LEB_CNT);
+	tmp = UBIFS_SB_LEBS + UBIFS_MST_LEBS + c->log_lebs + c->lpt_lebs;
+	tmp += c->orph_lebs + 4;
+	if (tmp > c->max_leb_cnt)
+		return err_msg("too low max. count of LEBs, expected at "
+			       "least %d", tmp);
+	tmp = calc_min_log_lebs(c->max_bud_bytes);
+	if (c->log_lebs < calc_min_log_lebs(c->max_bud_bytes))
+		return err_msg("too few log LEBs, expected at least %d",
+			       tmp);
+	return 0;
+}
+
+/**
+ * get_multiplier - convert size specifier to an integer multiplier.
+ * @str: the size specifier string
+ *
+ * This function parses the @str size specifier, which may be one of
+ * 'KiB', 'MiB', or 'GiB' into an integer multiplier. Returns positive
+ * size multiplier in case of success and %-1 in case of failure.
+ */
+static int get_multiplier(const char *str)
+{
+	if (!str)
+		return 1;
+
+	/* Remove spaces before the specifier */
+	while (*str == ' ' || *str == '\t')
+		str += 1;
+
+	if (!strcmp(str, "KiB"))
+		return 1024;
+	if (!strcmp(str, "MiB"))
+		return 1024 * 1024;
+	if (!strcmp(str, "GiB"))
+		return 1024 * 1024 * 1024;
+
+	return -1;
+}
+
+/**
+ * get_bytes - convert a string containing amount of bytes into an
+ *             integer.
+ * @str: string to convert
+ *
+ * This function parses @str which may have one of 'KiB', 'MiB', or 'GiB' size
+ * specifiers. Returns positive amount of bytes in case of success and %-1 in
+ * case of failure.
+ */
+static long long get_bytes(const char *str)
+{
+	char *endp;
+	long long bytes = strtoull(str, &endp, 0);
+
+	if (endp == str || bytes < 0)
+		return err_msg("incorrect amount of bytes: \"%s\"", str);
+
+	if (*endp != '\0') {
+		int mult = get_multiplier(endp);
+
+		if (mult == -1)
+			return err_msg("bad size specifier: \"%s\" - "
+				       "should be 'KiB', 'MiB' or 'GiB'", endp);
+		bytes *= mult;
+	}
+
+	return bytes;
+}
+
+static int get_options(int argc, char**argv)
+{
+	int opt, i;
+	const char *tbl_file = NULL;
+	struct stat st;
+	char *endp;
+
+	c->fanout = 8;
+	c->orph_lebs = 1;
+	c->key_hash = key_r5_hash;
+	c->key_len = UBIFS_SK_LEN;
+	c->default_compr = UBIFS_COMPR_LZO;
+	c->lsave_cnt = 256;
+	c->leb_size = -1;
+	c->min_io_size = -1;
+	c->max_bud_bytes = -1;
+	c->log_lebs = -1;
+
+	while (1) {
+		opt = getopt_long(argc, argv, optstring, longopts, &i);
+		if (opt == -1)
+			break;
+		switch (opt) {
+		case 'r':
+		case 'd':
+			root_len = strlen(optarg);
+			root = malloc(root_len + 2);
+			if (!root)
+				return err_msg("cannot allocate memory");
+
+			/*
+			 * The further code expects '/' at the end of the root
+			 * UBIFS directory on the host.
+			 */
+			memcpy(root, optarg, root_len);
+			if (root[root_len - 1] != '/')
+				root[root_len++] = '/';
+			root[root_len] = 0;
+
+			/* Make sure the root directory exists */
+			if (stat(root, &st))
+				return sys_err_msg("bad root directory '%s'",
+						   root);
+			break;
+		case 'm':
+			c->min_io_size = get_bytes(optarg);
+			if (c->min_io_size <= 0)
+				return err_msg("bad min. I/O size");
+			break;
+		case 'e':
+			c->leb_size = get_bytes(optarg);
+			if (c->leb_size <= 0)
+				return err_msg("bad LEB size");
+			break;
+		case 'c':
+			c->max_leb_cnt = get_bytes(optarg);
+			if (c->max_leb_cnt <= 0)
+				return err_msg("bad maximum LEB count");
+			break;
+		case 'o':
+			output = strdup(optarg);
+			break;
+		case 'D':
+			tbl_file = optarg;
+			if (stat(tbl_file, &st) < 0)
+				return sys_err_msg("bad device table file '%s'",
+						   tbl_file);
+			break;
+		case 'h':
+		case '?':
+			printf(helptext);
+			exit(0);
+		case 'v':
+			verbose = 1;
+			break;
+		case 'V':
+			printf("Version " PROGRAM_VERSION "\n");
+			exit(0);
+		case 'g':
+			debug_level = strtol(optarg, &endp, 0);
+			if (*endp != '\0' || endp == optarg ||
+			    debug_level < 0 || debug_level > 3)
+				return err_msg("bad debugging level '%s'",
+					       optarg);
+			break;
+		case 'f':
+			c->fanout = strtol(optarg, &endp, 0);
+			if (*endp != '\0' || endp == optarg || c->fanout <= 0)
+				return err_msg("bad fanout %s", optarg);
+			break;
+		case 'l':
+			c->log_lebs = strtol(optarg, &endp, 0);
+			if (*endp != '\0' || endp == optarg || c->log_lebs <= 0)
+				return err_msg("bad count of log LEBs '%s'",
+					       optarg);
+			break;
+		case 'p':
+			c->orph_lebs = strtol(optarg, &endp, 0);
+			if (*endp != '\0' || endp == optarg ||
+			    c->orph_lebs <= 0)
+				return err_msg("bad orphan LEB count '%s'",
+					       optarg);
+			break;
+		case 'k':
+			if (strcmp(optarg, "r5") == 0) {
+				c->key_hash = key_r5_hash;
+				c->key_hash_type = UBIFS_KEY_HASH_R5;
+			} else if (strcmp(optarg, "test") == 0) {
+				c->key_hash = key_test_hash;
+				c->key_hash_type = UBIFS_KEY_HASH_TEST;
+			} else
+				return err_msg("bad key hash");
+			break;
+		case 'x':
+			if (strcmp(optarg, "lzo") == 0)
+				c->default_compr = UBIFS_COMPR_LZO;
+			else if (strcmp(optarg, "zlib") == 0)
+				c->default_compr = UBIFS_COMPR_ZLIB;
+			else if (strcmp(optarg, "none") == 0)
+				c->default_compr = UBIFS_COMPR_NONE;
+			else
+				return err_msg("bad compressor name");
+			break;
+		case 'j':
+			c->max_bud_bytes = get_bytes(optarg);
+			if (c->max_bud_bytes <= 0)
+				return err_msg("bad maximum amount of buds");
+			break;
+		case 'U':
+			squash_owner = 1;
+			break;
+		}
+	}
+
+	if (c->min_io_size == -1)
+		return err_msg("min. I/O unit was not specified "
+			       "(use -h for help)");
+
+	if (c->leb_size == -1)
+		return err_msg("LEB size was not specified (use -h for help)");
+
+	if (c->max_bud_bytes == -1) {
+		int lebs;
+
+		lebs = c->max_leb_cnt - UBIFS_SB_LEBS - UBIFS_MST_LEBS;
+		lebs -= c->orph_lebs;
+		if (c->log_lebs != -1)
+			lebs -= c->log_lebs;
+		else
+			lebs -= UBIFS_MIN_LOG_LEBS;
+		/*
+		 * We do not know lprops geometry so far, so assume minimum
+		 * count of lprops LEBs.
+		 */
+		lebs -= UBIFS_MIN_LPT_LEBS;
+		/* Make the journal about 12.5% of main area lebs */
+		c->max_bud_bytes = (lebs / 8) * (long long)c->leb_size;
+		/* Make the max journal size 8MiB */
+		if (c->max_bud_bytes > 8 * 1024 * 1024)
+			c->max_bud_bytes = 8 * 1024 * 1024;
+		if (c->max_bud_bytes < 4 * c->leb_size)
+			c->max_bud_bytes = 4 * c->leb_size;
+	}
+
+	if (c->log_lebs == -1) {
+		c->log_lebs = calc_min_log_lebs(c->max_bud_bytes);
+		c->log_lebs += 2;
+	}
+
+	if (verbose) {
+		printf("mkfs.ubifs\n");
+		printf("\troot:         %s\n", root);
+		printf("\tmin_io_size:  %d\n", c->min_io_size);
+		printf("\tleb_size:     %d\n", c->leb_size);
+		printf("\tmax_leb_cnt:  %d\n", c->max_leb_cnt);
+		printf("\toutput:       %s\n", output);
+		printf("\tjrn_size:     %llu\n", c->max_bud_bytes);
+		switch (c->default_compr) {
+		case UBIFS_COMPR_LZO:
+			printf("\tcompr:        lzo\n");
+			break;
+		case UBIFS_COMPR_ZLIB:
+			printf("\tcompr:        zlib\n");
+			break;
+		case UBIFS_COMPR_NONE:
+			printf("\tcompr:        none\n");
+			break;
+		}
+		printf("\tkeyhash:      %s\n", (c->key_hash == key_r5_hash) ?
+						"r5" : "test");
+		printf("\tfanout:       %d\n", c->fanout);
+		printf("\torph_lebs:    %d\n", c->orph_lebs);
+	}
+
+	if (c->min_io_size < 8)
+		c->min_io_size = 8;
+
+	if (validate_options())
+		return -1;
+
+	if (tbl_file && parse_devtable(root, tbl_file))
+		return err_msg("cannot parse device table file '%s'", tbl_file);
+
+	return 0;
+}
+
+/**
+ * prepare_node - fill in the common header.
+ * @node: node
+ * @len: node length
+ */
+static void prepare_node(void *node, int len)
+{
+	uint32_t crc;
+	struct ubifs_ch *ch = node;
+
+	ch->magic = cpu_to_le32(UBIFS_NODE_MAGIC);
+	ch->len = cpu_to_le32(len);
+	ch->group_type = UBIFS_NO_NODE_GROUP;
+	ch->sqnum = cpu_to_le64(++c->max_sqnum);
+	ch->padding[0] = ch->padding[1] = 0;
+	crc = crc32(UBIFS_CRC32_INIT, node + 8, len - 8);
+	ch->crc = cpu_to_le32(crc);
+}
+
+/**
+ * write_leb - copy the image of a LEB to the output file.
+ * @lnum: LEB number
+ * @len: length of data in the buffer
+ * @buf: buffer (must be at least c->leb_size bytes)
+ */
+int write_leb(int lnum, int len, void *buf)
+{
+	off64_t pos = (off64_t)lnum * c->leb_size;
+
+	dbg_msg(3, "LEB %d len %d", lnum, len);
+	if (lseek64(out_fd, pos, SEEK_SET) != pos)
+		return sys_err_msg("lseek64 failed seeking %lld", pos);
+
+	memset(buf + len, 0xff, c->leb_size - len);
+
+	if (write(out_fd, buf, c->leb_size) != c->leb_size)
+		return sys_err_msg("write failed writing %d bytes at pos %lld",
+				   c->leb_size, pos);
+
+	return 0;
+}
+
+/**
+ * write_empty_leb - copy the image of an empty LEB to the output file.
+ * @lnum: LEB number
+ */
+static int write_empty_leb(int lnum)
+{
+	return write_leb(lnum, 0, leb_buf);
+}
+
+/**
+ * do_pad - pad a buffer to the minimum I/O size.
+ * @buf: buffer
+ * @len: buffer length
+ */
+static int do_pad(void *buf, int len)
+{
+	int pad_len, alen = ALIGN(len, 8), wlen = ALIGN(alen, c->min_io_size);
+	uint32_t crc;
+
+	memset(buf + len, 0xff, alen - len);
+	pad_len = wlen - alen;
+	dbg_msg(3, "len %d pad_len %d", len, pad_len);
+	buf += alen;
+	if (pad_len >= UBIFS_PAD_NODE_SZ) {
+		struct ubifs_ch *ch = buf;
+		struct ubifs_pad_node *pad_node = buf;
+
+		ch->magic      = cpu_to_le32(UBIFS_NODE_MAGIC);
+		ch->node_type  = UBIFS_PAD_NODE;
+		ch->group_type = UBIFS_NO_NODE_GROUP;
+		ch->padding[0] = ch->padding[1] = 0;
+		ch->sqnum      = cpu_to_le64(0);
+		ch->len        = cpu_to_le32(UBIFS_PAD_NODE_SZ);
+
+		pad_len -= UBIFS_PAD_NODE_SZ;
+		pad_node->pad_len = cpu_to_le32(pad_len);
+
+		crc = crc32(UBIFS_CRC32_INIT, buf + 8, UBIFS_PAD_NODE_SZ - 8);
+		ch->crc = cpu_to_le32(crc);
+
+		memset(buf + UBIFS_PAD_NODE_SZ, 0, pad_len);
+	} else if (pad_len > 0)
+		memset(buf, UBIFS_PADDING_BYTE, pad_len);
+
+	return wlen;
+}
+
+/**
+ * write_node - write a node to a LEB.
+ * @node: node
+ * @len: node length
+ * @lnum: LEB number
+ */
+static int write_node(void *node, int len, int lnum)
+{
+	prepare_node(node, len);
+
+	memcpy(leb_buf, node, len);
+
+	len = do_pad(leb_buf, len);
+
+	return write_leb(lnum, len, leb_buf);
+}
+
+/**
+ * calc_dark - calculate LEB dark space size.
+ * @c: the UBIFS file-system description object
+ * @spc: amount of free and dirty space in the LEB
+ *
+ * This function calculates amount of dark space in an LEB which has @spc bytes
+ * of free and dirty space. Returns the calculations result.
+ *
+ * Dark space is the space which is not always usable - it depends on which
+ * nodes are written in which order. E.g., if an LEB has only 512 free bytes,
+ * it is dark space, because it cannot fit a large data node. So UBIFS cannot
+ * count on this LEB and treat these 512 bytes as usable because it is not true
+ * if, for example, only big chunks of uncompressible data will be written to
+ * the FS.
+ */
+static int calc_dark(struct ubifs_info *c, int spc)
+{
+	if (spc < c->dark_wm)
+		return spc;
+
+	/*
+	 * If we have slightly more space then the dark space watermark, we can
+	 * anyway safely assume it we'll be able to write a node of the
+	 * smallest size there.
+	 */
+	if (spc - c->dark_wm < MIN_WRITE_SZ)
+		return spc - MIN_WRITE_SZ;
+
+	return c->dark_wm;
+}
+
+/**
+ * set_lprops - set the LEB property values for a LEB.
+ * @lnum: LEB number
+ * @offs: end offset of data in the LEB
+ * @flags: LEB property flags
+ */
+static void set_lprops(int lnum, int offs, int flags)
+{
+	int i = lnum - c->main_first, free, dirty;
+	int a = max_t(int, c->min_io_size, 8);
+
+	free = c->leb_size - ALIGN(offs, a);
+	dirty = c->leb_size - free - ALIGN(offs, 8);
+	dbg_msg(3, "LEB %d free %d dirty %d flags %d", lnum, free, dirty,
+		flags);
+	c->lpt[i].free = free;
+	c->lpt[i].dirty = dirty;
+	c->lpt[i].flags = flags;
+	c->lst.total_free += free;
+	c->lst.total_dirty += dirty;
+	if (flags & LPROPS_INDEX)
+		c->lst.idx_lebs += 1;
+	else {
+		int spc;
+
+		spc = free + dirty;
+		if (spc < c->dead_wm)
+			c->lst.total_dead += spc;
+		else
+			c->lst.total_dark += calc_dark(c, spc);
+		c->lst.total_used += c->leb_size - spc;
+	}
+}
+
+/**
+ * add_to_index - add a node key and position to the index.
+ * @key: node key
+ * @lnum: node LEB number
+ * @offs: node offset
+ * @len: node length
+ */
+static int add_to_index(union ubifs_key *key, char *name, int lnum, int offs,
+			int len)
+{
+	struct idx_entry *e;
+
+	dbg_msg(3, "LEB %d offs %d len %d", lnum, offs, len);
+	e = malloc(sizeof(struct idx_entry));
+	if (!e)
+		return err_msg("out of memory");
+	e->next = NULL;
+	e->prev = idx_list_last;
+	e->key = *key;
+	e->name = name;
+	e->lnum = lnum;
+	e->offs = offs;
+	e->len = len;
+	if (!idx_list_first)
+		idx_list_first = e;
+	if (idx_list_last)
+		idx_list_last->next = e;
+	idx_list_last = e;
+	idx_cnt += 1;
+	return 0;
+}
+
+/**
+ * flush_nodes - write the current head and move the head to the next LEB.
+ */
+static int flush_nodes(void)
+{
+	int len, err;
+
+	if (!head_offs)
+		return 0;
+	len = do_pad(leb_buf, head_offs);
+	err = write_leb(head_lnum, len, leb_buf);
+	if (err)
+		return err;
+	set_lprops(head_lnum, head_offs, head_flags);
+	head_lnum += 1;
+	head_offs = 0;
+	return 0;
+}
+
+/**
+ * reserve_space - reserve space for a node on the head.
+ * @len: node length
+ * @lnum: LEB number is returned here
+ * @offs: offset is returned here
+ */
+static int reserve_space(int len, int *lnum, int *offs)
+{
+	int err;
+
+	if (len > c->leb_size - head_offs) {
+		err = flush_nodes();
+		if (err)
+			return err;
+	}
+	*lnum = head_lnum;
+	*offs = head_offs;
+	head_offs += ALIGN(len, 8);
+	return 0;
+}
+
+/**
+ * add_node - write a node to the head.
+ * @key: node key
+ * @node: node
+ * @len: node length
+ */
+static int add_node(union ubifs_key *key, char *name, void *node, int len)
+{
+	int err, lnum, offs;
+
+	prepare_node(node, len);
+
+	err = reserve_space(len, &lnum, &offs);
+	if (err)
+		return err;
+
+	memcpy(leb_buf + offs, node, len);
+	memset(leb_buf + offs + len, 0xff, ALIGN(len, 8) - len);
+
+	add_to_index(key, name, lnum, offs, len);
+
+	return 0;
+}
+
+/**
+ * add_inode_with_data - write an inode.
+ * @st: stat information of source inode
+ * @inum: target inode number
+ * @data: inode data (for special inodes e.g. symlink path etc)
+ * @data_len: inode data length
+ * @flags: source inode flags
+ */
+static int add_inode_with_data(struct stat *st, ino_t inum, void *data,
+			       unsigned int data_len, int flags)
+{
+	struct ubifs_ino_node *ino = node_buf;
+	union ubifs_key key;
+	int len, use_flags = 0;
+
+	if (c->default_compr != UBIFS_COMPR_NONE)
+		use_flags |= UBIFS_COMPR_FL;
+	if (flags & FS_COMPR_FL)
+		use_flags |= UBIFS_COMPR_FL;
+	if (flags & FS_SYNC_FL)
+		use_flags |= UBIFS_SYNC_FL;
+	if (flags & FS_IMMUTABLE_FL)
+		use_flags |= UBIFS_IMMUTABLE_FL;
+	if (flags & FS_APPEND_FL)
+		use_flags |= UBIFS_APPEND_FL;
+	if (flags & FS_DIRSYNC_FL && S_ISDIR(st->st_mode))
+		use_flags |= UBIFS_DIRSYNC_FL;
+
+	memset(ino, 0, UBIFS_INO_NODE_SZ);
+
+	ino_key_init(c, &key, inum);
+	ino->ch.node_type = UBIFS_INO_NODE;
+	key_write(c, &key, &ino->key);
+	ino->creat_sqnum = cpu_to_le64(creat_sqnum);
+	ino->size       = cpu_to_le64(st->st_size);
+	ino->nlink      = cpu_to_le32(st->st_nlink);
+	/*
+	 * The time fields are updated assuming the default time granularity
+	 * of 1 second. To support finer granularities, utime() would be needed.
+	 */
+	ino->atime_sec  = cpu_to_le64(st->st_atime);
+	ino->ctime_sec  = cpu_to_le64(st->st_ctime);
+	ino->mtime_sec  = cpu_to_le64(st->st_mtime);
+	ino->atime_nsec = 0;
+	ino->ctime_nsec = 0;
+	ino->mtime_nsec = 0;
+	ino->uid        = cpu_to_le32(st->st_uid);
+	ino->gid        = cpu_to_le32(st->st_gid);
+	ino->uid        = cpu_to_le32(st->st_uid);
+	ino->gid        = cpu_to_le32(st->st_gid);
+	ino->mode       = cpu_to_le32(st->st_mode);
+	ino->flags      = cpu_to_le32(use_flags);
+	ino->data_len   = cpu_to_le32(data_len);
+	ino->compr_type = cpu_to_le16(c->default_compr);
+	if (data_len)
+		memcpy(&ino->data, data, data_len);
+
+	len = UBIFS_INO_NODE_SZ + data_len;
+
+	return add_node(&key, NULL, ino, len);
+}
+
+/**
+ * add_inode - write an inode.
+ * @st: stat information of source inode
+ * @inum: target inode number
+ * @flags: source inode flags
+ */
+static int add_inode(struct stat *st, ino_t inum, int flags)
+{
+	return add_inode_with_data(st, inum, NULL, 0, flags);
+}
+
+/**
+ * add_dir_inode - write an inode for a directory.
+ * @dir: source directory
+ * @inum: target inode number
+ * @size: target directory size
+ * @nlink: target directory link count
+ * @st: struct stat object describing attributes (except size and nlink) of the
+ *      target inode to create
+ *
+ * Note, this function may be called with %NULL @dir, when the directory which
+ * is being created does not exist at the host file system, but is defined by
+ * the device table.
+ */
+static int add_dir_inode(DIR *dir, ino_t inum, loff_t size, unsigned int nlink,
+			 struct stat *st)
+{
+	int fd, flags = 0;
+
+	st->st_size = size;
+	st->st_nlink = nlink;
+
+	if (dir) {
+		fd = dirfd(dir);
+		if (fd == -1)
+			return sys_err_msg("dirfd failed");
+		if (ioctl(fd, FS_IOC_GETFLAGS, &flags) == -1)
+			flags = 0;
+	}
+
+	return add_inode(st, inum, flags);
+}
+
+/**
+ * add_dev_inode - write an inode for a character or block device.
+ * @st: stat information of source inode
+ * @inum: target inode number
+ * @flags: source inode flags
+ */
+static int add_dev_inode(struct stat *st, ino_t inum, int flags)
+{
+	union ubifs_dev_desc dev;
+
+	dev.huge = cpu_to_le64(makedev(major(st->st_rdev), minor(st->st_rdev)));
+	return add_inode_with_data(st, inum, &dev, 8, flags);
+}
+
+/**
+ * add_symlink_inode - write an inode for a symbolic link.
+ * @path_name: path name of symbolic link inode itself (not the link target)
+ * @st: stat information of source inode
+ * @inum: target inode number
+ * @flags: source inode flags
+ */
+static int add_symlink_inode(const char *path_name, struct stat *st, ino_t inum,
+			     int flags)
+{
+	char buf[UBIFS_MAX_INO_DATA + 2];
+	ssize_t len;
+
+	/* Take the symlink as is */
+	len = readlink(path_name, buf, UBIFS_MAX_INO_DATA + 1);
+	if (len <= 0)
+		return sys_err_msg("readlink failed for %s", path_name);
+	if (len > UBIFS_MAX_INO_DATA)
+		return err_msg("symlink too long for %s", path_name);
+
+	return add_inode_with_data(st, inum, buf, len, flags);
+}
+
+/**
+ * add_dent_node - write a directory entry node.
+ * @dir_inum: target inode number of directory
+ * @name: directory entry name
+ * @inum: target inode number of the directory entry
+ * @type: type of the target inode
+ */
+static int add_dent_node(ino_t dir_inum, const char *name, ino_t inum,
+			 unsigned char type)
+{
+	struct ubifs_dent_node *dent = node_buf;
+	union ubifs_key key;
+	struct qstr dname;
+	char *kname;
+	int len;
+
+	dbg_msg(3, "%s ino %lu type %u dir ino %lu", name, inum,
+		(unsigned)type, dir_inum);
+	memset(dent, 0, UBIFS_DENT_NODE_SZ);
+
+	dname.name = (void *)name;
+	dname.len = strlen(name);
+
+	dent->ch.node_type = UBIFS_DENT_NODE;
+
+	dent_key_init(c, &key, dir_inum, &dname);
+	key_write(c, &key, dent->key);
+	dent->inum = cpu_to_le64(inum);
+	dent->padding1 = 0;
+	dent->type = type;
+	dent->nlen = cpu_to_le16(dname.len);
+	memcpy(dent->name, dname.name, dname.len);
+	dent->name[dname.len] = '\0';
+
+	len = UBIFS_DENT_NODE_SZ + dname.len + 1;
+
+	kname = strdup(name);
+	if (!kname)
+		return err_msg("cannot allocate memory");
+
+	return add_node(&key, kname, dent, len);
+}
+
+/**
+ * lookup_inum_mapping - add an inode mapping for link counting.
+ * @dev: source device on which source inode number resides
+ * @inum: source inode number
+ */
+static struct inum_mapping *lookup_inum_mapping(dev_t dev, ino_t inum)
+{
+	struct inum_mapping *im;
+	unsigned int k;
+
+	k = inum % HASH_TABLE_SIZE;
+	im = hash_table[k];
+	while (im) {
+		if (im->dev == dev && im->inum == inum)
+			return im;
+		im = im->next;
+	}
+	im = malloc(sizeof(struct inum_mapping));
+	if (!im)
+		return NULL;
+	im->next = hash_table[k];
+	im->prev = NULL;
+	im->dev = dev;
+	im->inum = inum;
+	im->use_inum = 0;
+	im->use_nlink = 0;
+	if (hash_table[k])
+		hash_table[k]->prev = im;
+	hash_table[k] = im;
+	return im;
+}
+
+/**
+ * all_zero - does a buffer contain only zero bytes.
+ * @buf: buffer
+ * @len: buffer length
+ */
+static int all_zero(void *buf, int len)
+{
+	unsigned char *p = buf;
+
+	while (len--)
+		if (*p++ != 0)
+			return 0;
+	return 1;
+}
+
+/**
+ * add_file - write the data of a file and its inode to the output file.
+ * @path_name: source path name
+ * @st: source inode stat information
+ * @inum: target inode number
+ * @flags: source inode flags
+ */
+static int add_file(const char *path_name, struct stat *st, ino_t inum,
+		    int flags)
+{
+	struct ubifs_data_node *dn = node_buf;
+	void *buf = block_buf;
+	loff_t file_size = 0;
+	ssize_t ret, bytes_read;
+	union ubifs_key key;
+	int fd, dn_len, err, compr_type, use_compr;
+	unsigned int block_no = 0;
+	size_t out_len;
+
+	fd = open(path_name, O_RDONLY | O_LARGEFILE);
+	if (fd == -1)
+		return sys_err_msg("failed to open file '%s'", path_name);
+	do {
+		/* Read next block */
+		bytes_read = 0;
+		do {
+			ret = read(fd, buf + bytes_read,
+				   UBIFS_BLOCK_SIZE - bytes_read);
+			if (ret == -1) {
+				sys_err_msg("failed to read file '%s'",
+					    path_name);
+				close(fd);
+				return 1;
+			}
+			bytes_read += ret;
+		} while (ret != 0 && bytes_read != UBIFS_BLOCK_SIZE);
+		if (bytes_read == 0)
+			break;
+		file_size += bytes_read;
+		/* Skip holes */
+		if (all_zero(buf, bytes_read)) {
+			block_no += 1;
+			continue;
+		}
+		/* Make data node */
+		memset(dn, 0, UBIFS_DATA_NODE_SZ);
+		data_key_init(c, &key, inum, block_no++);
+		dn->ch.node_type = UBIFS_DATA_NODE;
+		key_write(c, &key, &dn->key);
+		dn->size = cpu_to_le32(bytes_read);
+		out_len = NODE_BUFFER_SIZE - UBIFS_DATA_NODE_SZ;
+		if (c->default_compr == UBIFS_COMPR_NONE &&
+		    (flags & FS_COMPR_FL))
+			use_compr = UBIFS_COMPR_LZO;
+		else
+			use_compr = c->default_compr;
+		compr_type = compress_data(buf, bytes_read, &dn->data,
+					   &out_len, use_compr);
+		dn->compr_type = cpu_to_le16(compr_type);
+		dn_len = UBIFS_DATA_NODE_SZ + out_len;
+		/* Add data node to file system */
+		err = add_node(&key, NULL, dn, dn_len);
+		if (err) {
+			close(fd);
+			return err;
+		}
+	} while (ret != 0);
+	if (close(fd) == -1)
+		return sys_err_msg("failed to close file '%s'", path_name);
+	if (file_size != st->st_size)
+		return err_msg("file size changed during writing file '%s'",
+			       path_name);
+	return add_inode(st, inum, flags);
+}
+
+/**
+ * add_non_dir - write a non-directory to the output file.
+ * @path_name: source path name
+ * @inum: target inode number is passed and returned here (due to link counting)
+ * @nlink: number of links if known otherwise zero
+ * @type: UBIFS inode type is returned here
+ * @st: struct stat object containing inode attributes which should be use when
+ *      creating the UBIFS inode
+ */
+static int add_non_dir(const char *path_name, ino_t *inum, unsigned int nlink,
+		       unsigned char *type, struct stat *st)
+{
+	int fd, flags = 0;
+
+	dbg_msg(2, "%s", path_name);
+
+	if (S_ISREG(st->st_mode)) {
+		fd = open(path_name, O_RDONLY);
+		if (fd == -1)
+			return sys_err_msg("failed to open file '%s'",
+					   path_name);
+		if (ioctl(fd, FS_IOC_GETFLAGS, &flags) == -1)
+			flags = 0;
+		if (close(fd) == -1)
+			return sys_err_msg("failed to close file '%s'",
+					   path_name);
+		*type = UBIFS_ITYPE_REG;
+	} else if (S_ISCHR(st->st_mode))
+		*type = UBIFS_ITYPE_CHR;
+	else if (S_ISBLK(st->st_mode))
+		*type = UBIFS_ITYPE_BLK;
+	else if (S_ISLNK(st->st_mode))
+		*type = UBIFS_ITYPE_LNK;
+	else if (S_ISSOCK(st->st_mode))
+		*type = UBIFS_ITYPE_SOCK;
+	else if (S_ISFIFO(st->st_mode))
+		*type = UBIFS_ITYPE_FIFO;
+	else
+		return err_msg("file '%s' has unknown inode type", path_name);
+
+	if (nlink)
+		st->st_nlink = nlink;
+	else if (st->st_nlink > 1) {
+		/*
+		 * If the number of links is greater than 1, then add this file
+		 * later when we know the number of links that we actually have.
+		 * For now, we just put the inode mapping in the hash table.
+		 */
+		struct inum_mapping *im;
+
+		im = lookup_inum_mapping(st->st_dev, st->st_ino);
+		if (!im)
+			return err_msg("out of memory");
+		if (im->use_nlink == 0) {
+			/* New entry */
+			im->use_inum = *inum;
+			im->use_nlink = 1;
+			im->path_name = malloc(strlen(path_name) + 1);
+			if (!im->path_name)
+				return err_msg("out of memory");
+			strcpy(im->path_name, path_name);
+		} else {
+			/* Existing entry */
+			*inum = im->use_inum;
+			im->use_nlink += 1;
+			/* Return unused inode number */
+			c->highest_inum -= 1;
+		}
+
+		memcpy(&im->st, st, sizeof(struct stat));
+		return 0;
+	} else
+		st->st_nlink = 1;
+
+	creat_sqnum = ++c->max_sqnum;
+
+	if (S_ISREG(st->st_mode))
+		return add_file(path_name, st, *inum, flags);
+	if (S_ISCHR(st->st_mode))
+		return add_dev_inode(st, *inum, flags);
+	if (S_ISBLK(st->st_mode))
+		return add_dev_inode(st, *inum, flags);
+	if (S_ISLNK(st->st_mode))
+		return add_symlink_inode(path_name, st, *inum, flags);
+	if (S_ISSOCK(st->st_mode))
+		return add_inode(st, *inum, flags);
+	if (S_ISFIFO(st->st_mode))
+		return add_inode(st, *inum, flags);
+
+	return err_msg("file '%s' has unknown inode type", path_name);
+}
+
+/**
+ * add_directory - write a directory tree to the output file.
+ * @dir_name: directory path name
+ * @dir_inum: UBIFS inode number of directory
+ * @st: directory inode statistics
+ * @non_existing: non-zero if this function is called for a directory which
+ *                does not exist on the host file-system and it is being
+ *                created because it is defined in the device table file.
+ */
+static int add_directory(const char *dir_name, ino_t dir_inum, struct stat *st,
+			 int non_existing)
+{
+	struct dirent *entry;
+	DIR *dir = NULL;
+	int err = 0;
+	loff_t size = UBIFS_INO_NODE_SZ;
+	char *name = NULL;
+	unsigned int nlink = 2;
+	struct path_htbl_element *ph_elt;
+	struct name_htbl_element *nh_elt = NULL;
+	struct hashtable_itr *itr;
+	ino_t inum;
+	unsigned char type;
+	unsigned long long dir_creat_sqnum = ++c->max_sqnum;
+
+	dbg_msg(2, "%s", dir_name);
+	if (!non_existing) {
+		dir = opendir(dir_name);
+		if (dir == NULL)
+			return sys_err_msg("cannot open directory '%s'",
+					   dir_name);
+	}
+
+	/*
+	 * Check whether this directory contains files which should be
+	 * added/changed because they were specified in the device table.
+	 * @ph_elt will be non-zero if yes.
+	 */
+	ph_elt = devtbl_find_path(dir_name + root_len - 1);
+
+	/*
+	 * Before adding the directory itself, we have to iterate over all the
+	 * entries the device table adds to this directory and create them.
+	 */
+	for (; !non_existing;) {
+		struct stat dent_st;
+
+		errno = 0;
+		entry = readdir(dir);
+		if (!entry) {
+			if (errno == 0)
+				break;
+			sys_err_msg("error reading directory '%s'", dir_name);
+			err = -1;
+			break;
+		}
+
+		if (strcmp(".", entry->d_name) == 0)
+			continue;
+		if (strcmp("..", entry->d_name) == 0)
+			continue;
+
+		if (ph_elt)
+			/*
+			 * This directory was referred to at the device table
+			 * file. Check if this directory entry is referred at
+			 * too.
+			 */
+			nh_elt = devtbl_find_name(ph_elt, entry->d_name);
+
+		/*
+		 * We are going to create the file corresponding to this
+		 * directory entry (@entry->d_name). We use 'struct stat'
+		 * object to pass information about file attributes (actually
+		 * only about UID, GID, mode, major, and minor). Get attributes
+		 * for this file from the UBIFS rootfs on the host.
+		 */
+		free(name);
+		name = make_path(dir_name, entry->d_name);
+		if (lstat(name, &dent_st) == -1) {
+			sys_err_msg("lstat failed for file '%s'", name);
+			goto out_free;
+		}
+
+		if (squash_owner)
+			/*
+			 * Squash UID/GID. But the device table may override
+			 * this.
+			 */
+			dent_st.st_uid = dent_st.st_gid = 0;
+
+		/*
+		 * And if the device table describes the same file, override
+		 * the attributes. However, this is not allowed for device node
+		 * files.
+		 */
+		if (nh_elt && override_attributes(&dent_st, ph_elt, nh_elt))
+			goto out_free;
+
+		inum = ++c->highest_inum;
+
+		if (S_ISDIR(dent_st.st_mode)) {
+			err = add_directory(name, inum, &dent_st, 0);
+			if (err)
+				goto out_free;
+			nlink += 1;
+			type = UBIFS_ITYPE_DIR;
+		} else {
+			err = add_non_dir(name, &inum, 0, &type, &dent_st);
+			if (err)
+				goto out_free;
+		}
+
+		err = add_dent_node(dir_inum, entry->d_name, inum, type);
+		if (err)
+			goto out_free;
+		size += ALIGN(UBIFS_DENT_NODE_SZ + strlen(entry->d_name) + 1,
+			      8);
+	}
+
+	/*
+	 * OK, we have created all files in this directory (recursively), let's
+	 * also create all files described in the device table. All t
+	 */
+	nh_elt = first_name_htbl_element(ph_elt, &itr);
+	while (nh_elt) {
+		struct stat fake_st;
+
+		/*
+		 * We prohibit creating regular files using the device table,
+		 * the device table may only re-define attributes of regular
+		 * files.
+		 */
+		if (S_ISREG(nh_elt->mode)) {
+			err_msg("Bad device table entry %s/%s - it is "
+				"prohibited to create regular files "
+				"via device table",
+				strcmp(ph_elt->path, "/") ? ph_elt->path : "",
+				nh_elt->name);
+			goto out_free;
+		}
+
+		memcpy(&fake_st, &root_st, sizeof(struct stat));
+		fake_st.st_uid  = nh_elt->uid;
+		fake_st.st_uid  = nh_elt->uid;
+		fake_st.st_mode = nh_elt->mode;
+		fake_st.st_rdev = nh_elt->dev;
+		fake_st.st_nlink = 1;
+
+		free(name);
+		name = make_path(dir_name, nh_elt->name);
+		inum = ++c->highest_inum;
+
+		if (S_ISDIR(nh_elt->mode)) {
+			err = add_directory(name, inum, &fake_st, 1);
+			if (err)
+				goto out_free;
+			nlink += 1;
+			type = UBIFS_ITYPE_DIR;
+		} else {
+			err = add_non_dir(name, &inum, 0, &type, &fake_st);
+			if (err)
+				goto out_free;
+		}
+
+		err = add_dent_node(dir_inum, nh_elt->name, inum, type);
+		if (err)
+			goto out_free;
+		size += ALIGN(UBIFS_DENT_NODE_SZ + strlen(nh_elt->name) + 1, 8);
+
+		nh_elt = next_name_htbl_element(ph_elt, &itr);
+	}
+
+	creat_sqnum = dir_creat_sqnum;
+
+	err = add_dir_inode(dir, dir_inum, size, nlink, st);
+	if (err)
+		goto out_free;
+
+	free(name);
+	if (!non_existing && closedir(dir) == -1)
+		return sys_err_msg("error closing directory '%s'", dir_name);
+
+	return 0;
+
+out_free:
+	free(name);
+	if (!non_existing)
+		closedir(dir);
+	return -1;
+}
+
+/**
+ * add_multi_linked_files - write all the files for which we counted links.
+ */
+static int add_multi_linked_files(void)
+{
+	int i, err;
+
+	for (i = 0; i < HASH_TABLE_SIZE; i++) {
+		struct inum_mapping *im;
+		unsigned char type = 0;
+
+		for (im = hash_table[i]; im; im = im->next) {
+			dbg_msg(2, "%s", im->path_name);
+			err = add_non_dir(im->path_name, &im->use_inum,
+					  im->use_nlink, &type, &im->st);
+			if (err)
+				return err;
+		}
+	}
+	return 0;
+}
+
+/**
+ * write_data - write the files and directories.
+ */
+static int write_data(void)
+{
+	int err;
+
+	err = stat(root, &root_st);
+	if (err)
+		return sys_err_msg("bad root file-system directory '%s'", root);
+	root_st.st_uid = root_st.st_gid = 0;
+	root_st.st_mode = S_IFDIR | S_IRWXU | S_IRWXG | S_IRWXO;
+
+	head_flags = 0;
+	err = add_directory(root, UBIFS_ROOT_INO, &root_st, 0);
+	if (err)
+		return err;
+	err = add_multi_linked_files();
+	if (err)
+		return err;
+	return flush_nodes();
+}
+
+static int namecmp(const char *name1, const char *name2)
+{
+	size_t len1 = strlen(name1), len2 = strlen(name2);
+	size_t clen = (len1 < len2) ? len1 : len2;
+	int cmp;
+
+	cmp = memcmp(name1, name2, clen);
+	if (cmp)
+		return cmp;
+	return (len1 < len2) ? -1 : 1;
+}
+
+static int cmp_idx(const void *a, const void *b)
+{
+	const struct idx_entry *e1 = *(const struct idx_entry **)a;
+	const struct idx_entry *e2 = *(const struct idx_entry **)b;
+	int cmp;
+
+	cmp = keys_cmp(c, &e1->key, &e2->key);
+	if (cmp)
+		return cmp;
+	return namecmp(e1->name, e2->name);
+}
+
+/**
+ * add_idx_node - write an index node to the head.
+ * @node: index node
+ * @child_cnt: number of children of this index node
+ */
+static int add_idx_node(void *node, int child_cnt)
+{
+	int err, lnum, offs, len;
+
+	len = ubifs_idx_node_sz(c, child_cnt);
+
+	prepare_node(node, len);
+
+	err = reserve_space(len, &lnum, &offs);
+	if (err)
+		return err;
+
+	memcpy(leb_buf + offs, node, len);
+	memset(leb_buf + offs + len, 0xff, ALIGN(len, 8) - len);
+
+	c->old_idx_sz += ALIGN(len, 8);
+
+	dbg_msg(3, "at %d:%d len %d index size %llu", lnum, offs, len,
+		c->old_idx_sz);
+
+	/* The last index node written will be the root */
+	c->zroot.lnum = lnum;
+	c->zroot.offs = offs;
+	c->zroot.len = len;
+
+	return 0;
+}
+
+/**
+ * write_index - write out the index.
+ */
+static int write_index(void)
+{
+	size_t sz, i, cnt, idx_sz, pstep, bcnt;
+	struct idx_entry **idx_ptr, **p;
+	struct ubifs_idx_node *idx;
+	struct ubifs_branch *br;
+	int child_cnt, j, level, blnum, boffs, blen, blast_len, err;
+
+	dbg_msg(1, "leaf node count: %d", idx_cnt);
+
+	/* Reset the head for the index */
+	head_flags = LPROPS_INDEX;
+	/* Allocate index node */
+	idx_sz = ubifs_idx_node_sz(c, c->fanout);
+	idx = malloc(idx_sz);
+	if (!idx)
+		return err_msg("out of memory");
+	/* Make an array of pointers to sort the index list */
+	sz = idx_cnt * sizeof(struct idx_entry *);
+	if (sz / sizeof(struct idx_entry *) != idx_cnt) {
+		free(idx);
+		return err_msg("index is too big (%zu entries)", idx_cnt);
+	}
+	idx_ptr = malloc(sz);
+	if (!idx_ptr) {
+		free(idx);
+		return err_msg("out of memory - needed %zu bytes for index",
+			       sz);
+	}
+	idx_ptr[0] = idx_list_first;
+	for (i = 1; i < idx_cnt; i++)
+		idx_ptr[i] = idx_ptr[i - 1]->next;
+	qsort(idx_ptr, idx_cnt, sizeof(struct idx_entry *), cmp_idx);
+	/* Write level 0 index nodes */
+	cnt = idx_cnt / c->fanout;
+	if (idx_cnt % c->fanout)
+		cnt += 1;
+	p = idx_ptr;
+	blnum = head_lnum;
+	boffs = head_offs;
+	for (i = 0; i < cnt; i++) {
+		/*
+		 * Calculate the child count. All index nodes are created full
+		 * except for the last index node on each row.
+		 */
+		if (i == cnt - 1) {
+			child_cnt = idx_cnt % c->fanout;
+			if (child_cnt == 0)
+				child_cnt = c->fanout;
+		} else
+			child_cnt = c->fanout;
+		memset(idx, 0, idx_sz);
+		idx->ch.node_type = UBIFS_IDX_NODE;
+		idx->child_cnt = cpu_to_le16(child_cnt);
+		idx->level = cpu_to_le16(0);
+		for (j = 0; j < child_cnt; j++, p++) {
+			br = ubifs_idx_branch(c, idx, j);
+			key_write_idx(c, &(*p)->key, &br->key);
+			br->lnum = cpu_to_le32((*p)->lnum);
+			br->offs = cpu_to_le32((*p)->offs);
+			br->len = cpu_to_le32((*p)->len);
+		}
+		add_idx_node(idx, child_cnt);
+	}
+	/* Write level 1 index nodes and above */
+	level = 0;
+	pstep = 1;
+	while (cnt > 1) {
+		/*
+		 * 'blast_len' is the length of the last index node in the level
+		 * below.
+		 */
+		blast_len = ubifs_idx_node_sz(c, child_cnt);
+		/* 'bcnt' is the number of index nodes in the level below */
+		bcnt = cnt;
+		/* 'cnt' is the number of index nodes in this level */
+		cnt = (cnt + c->fanout - 1) / c->fanout;
+		if (cnt == 0)
+			cnt = 1;
+		level += 1;
+		/*
+		 * The key of an index node is the same as the key of its first
+		 * child. Thus we can get the key by stepping along the bottom
+		 * level 'p' with an increasing large step 'pstep'.
+		 */
+		p = idx_ptr;
+		pstep *= c->fanout;
+		for (i = 0; i < cnt; i++) {
+			/*
+			 * Calculate the child count. All index nodes are
+			 * created full except for the last index node on each
+			 * row.
+			 */
+			if (i == cnt - 1) {
+				child_cnt = bcnt % c->fanout;
+				if (child_cnt == 0)
+					child_cnt = c->fanout;
+			} else
+				child_cnt = c->fanout;
+			memset(idx, 0, idx_sz);
+			idx->ch.node_type = UBIFS_IDX_NODE;
+			idx->child_cnt = cpu_to_le16(child_cnt);
+			idx->level = cpu_to_le16(level);
+			for (j = 0; j < child_cnt; j++) {
+				size_t bn = i * c->fanout + j;
+
+				/*
+				 * The length of the index node in the level
+				 * below is 'idx_sz' except when it is the last
+				 * node on the row. i.e. all the others on the
+				 * row are full.
+				 */
+				if (bn == bcnt - 1)
+					blen = blast_len;
+				else
+					blen = idx_sz;
+				/*
+				 * 'blnum' and 'boffs' hold the position of the
+				 * index node on the level below.
+				 */
+				if (boffs + blen > c->leb_size) {
+					blnum += 1;
+					boffs = 0;
+				}
+				/*
+				 * Fill in the branch with the key and position
+				 * of the index node from the level below.
+				 */
+				br = ubifs_idx_branch(c, idx, j);
+				key_write_idx(c, &(*p)->key, &br->key);
+				br->lnum = cpu_to_le32(blnum);
+				br->offs = cpu_to_le32(boffs);
+				br->len = cpu_to_le32(blen);
+				/*
+				 * Step to the next index node on the level
+				 * below.
+				 */
+				boffs += ALIGN(blen, 8);
+				p += pstep;
+			}
+			add_idx_node(idx, child_cnt);
+		}
+	}
+
+	/* Free stuff */
+	for (i = 0; i < idx_cnt; i++)
+		free(idx_ptr[i]);
+	free(idx_ptr);
+	free(idx);
+
+	dbg_msg(1, "zroot is at %d:%d len %d", c->zroot.lnum, c->zroot.offs,
+		c->zroot.len);
+
+	/* Set the index head */
+	c->ihead_lnum = head_lnum;
+	c->ihead_offs = ALIGN(head_offs, c->min_io_size);
+	dbg_msg(1, "ihead is at %d:%d", c->ihead_lnum, c->ihead_offs);
+
+	/* Flush the last index LEB */
+	err = flush_nodes();
+	if (err)
+		return err;
+
+	return 0;
+}
+
+/**
+ * set_gc_lnum - set the LEB number reserved for the garbage collector.
+ */
+static int set_gc_lnum(void)
+{
+	int err;
+
+	c->gc_lnum = head_lnum++;
+	err = write_empty_leb(c->gc_lnum);
+	if (err)
+		return err;
+	set_lprops(c->gc_lnum, 0, 0);
+	c->lst.empty_lebs += 1;
+	return 0;
+}
+
+/**
+ * finalize_leb_cnt - now that we know how many LEBs we used.
+ */
+static int finalize_leb_cnt(void)
+{
+	c->leb_cnt = head_lnum;
+	if (c->leb_cnt > c->max_leb_cnt)
+		/* TODO: in this case it segfaults because buffer overruns - we
+		 * somewhere allocate smaller buffers - fix */
+		return err_msg("max_leb_cnt too low (%d needed)", c->leb_cnt);
+	c->main_lebs = c->leb_cnt - c->main_first;
+	if (verbose) {
+		printf("\tsuper lebs:   %d\n", UBIFS_SB_LEBS);
+		printf("\tmaster lebs:  %d\n", UBIFS_MST_LEBS);
+		printf("\tlog_lebs:     %d\n", c->log_lebs);
+		printf("\tlpt_lebs:     %d\n", c->lpt_lebs);
+		printf("\torph_lebs:    %d\n", c->orph_lebs);
+		printf("\tmain_lebs:    %d\n", c->main_lebs);
+		printf("\tgc lebs:      %d\n", 1);
+		printf("\tindex lebs:   %d\n", c->lst.idx_lebs);
+		printf("\tleb_cnt:      %d\n", c->leb_cnt);
+	}
+	dbg_msg(1, "total_free:  %llu", c->lst.total_free);
+	dbg_msg(1, "total_dirty: %llu", c->lst.total_dirty);
+	dbg_msg(1, "total_used:  %llu", c->lst.total_used);
+	dbg_msg(1, "total_dead:  %llu", c->lst.total_dead);
+	dbg_msg(1, "total_dark:  %llu", c->lst.total_dark);
+	dbg_msg(1, "index size:  %llu", c->old_idx_sz);
+	dbg_msg(1, "empty_lebs:  %d", c->lst.empty_lebs);
+	return 0;
+}
+
+/**
+ * write_super - write the super block.
+ */
+static int write_super(void)
+{
+	struct ubifs_sb_node sup;
+
+	memset(&sup, 0, UBIFS_SB_NODE_SZ);
+
+	sup.ch.node_type  = UBIFS_SB_NODE;
+	sup.key_hash      = c->key_hash_type;
+	sup.min_io_size   = cpu_to_le32(c->min_io_size);
+	sup.leb_size      = cpu_to_le32(c->leb_size);
+	sup.leb_cnt       = cpu_to_le32(c->leb_cnt);
+	sup.max_leb_cnt   = cpu_to_le32(c->max_leb_cnt);
+	sup.max_bud_bytes = cpu_to_le64(c->max_bud_bytes);
+	sup.log_lebs      = cpu_to_le32(c->log_lebs);
+	sup.lpt_lebs      = cpu_to_le32(c->lpt_lebs);
+	sup.orph_lebs     = cpu_to_le32(c->orph_lebs);
+	sup.jhead_cnt     = cpu_to_le32(c->jhead_cnt);
+	sup.fanout        = cpu_to_le32(c->fanout);
+	sup.lsave_cnt     = cpu_to_le32(c->lsave_cnt);
+	sup.fmt_version   = cpu_to_le32(UBIFS_FORMAT_VERSION);
+	sup.default_compr = cpu_to_le16(c->default_compr);
+	sup.time_gran     = cpu_to_le32(DEFAULT_TIME_GRAN);
+	uuid_generate_random(sup.uuid);
+	if (verbose) {
+		char s[40];
+
+		uuid_unparse_upper(sup.uuid, s);
+		printf("\tUUID:         %s\n", s);
+	}
+	if (c->big_lpt)
+		sup.flags |= cpu_to_le32(UBIFS_FLG_BIGLPT);
+
+	return write_node(&sup, UBIFS_SB_NODE_SZ, UBIFS_SB_LNUM);
+}
+
+/**
+ * write_master - write the master node.
+ */
+static int write_master(void)
+{
+	struct ubifs_mst_node mst;
+	int err;
+
+	memset(&mst, 0, UBIFS_MST_NODE_SZ);
+
+	mst.ch.node_type = UBIFS_MST_NODE;
+	mst.log_lnum     = cpu_to_le32(UBIFS_LOG_LNUM);
+	mst.highest_inum = cpu_to_le64(c->highest_inum);
+	mst.cmt_no       = cpu_to_le64(0);
+	mst.flags        = cpu_to_le32(UBIFS_MST_NO_ORPHS);
+	mst.root_lnum    = cpu_to_le32(c->zroot.lnum);
+	mst.root_offs    = cpu_to_le32(c->zroot.offs);
+	mst.root_len     = cpu_to_le32(c->zroot.len);
+	mst.gc_lnum      = cpu_to_le32(c->gc_lnum);
+	mst.ihead_lnum   = cpu_to_le32(c->ihead_lnum);
+	mst.ihead_offs   = cpu_to_le32(c->ihead_offs);
+	mst.index_size   = cpu_to_le64(c->old_idx_sz);
+	mst.lpt_lnum     = cpu_to_le32(c->lpt_lnum);
+	mst.lpt_offs     = cpu_to_le32(c->lpt_offs);
+	mst.nhead_lnum   = cpu_to_le32(c->nhead_lnum);
+	mst.nhead_offs   = cpu_to_le32(c->nhead_offs);
+	mst.ltab_lnum    = cpu_to_le32(c->ltab_lnum);
+	mst.ltab_offs    = cpu_to_le32(c->ltab_offs);
+	mst.lsave_lnum   = cpu_to_le32(c->lsave_lnum);
+	mst.lsave_offs   = cpu_to_le32(c->lsave_offs);
+	mst.lscan_lnum   = cpu_to_le32(c->lscan_lnum);
+	mst.empty_lebs   = cpu_to_le32(c->lst.empty_lebs);
+	mst.idx_lebs     = cpu_to_le32(c->lst.idx_lebs);
+	mst.total_free   = cpu_to_le64(c->lst.total_free);
+	mst.total_dirty  = cpu_to_le64(c->lst.total_dirty);
+	mst.total_used   = cpu_to_le64(c->lst.total_used);
+	mst.total_dead   = cpu_to_le64(c->lst.total_dead);
+	mst.total_dark   = cpu_to_le64(c->lst.total_dark);
+	mst.leb_cnt      = cpu_to_le32(c->leb_cnt);
+
+	err = write_node(&mst, UBIFS_MST_NODE_SZ, UBIFS_MST_LNUM);
+	if (err)
+		return err;
+
+	err = write_node(&mst, UBIFS_MST_NODE_SZ, UBIFS_MST_LNUM + 1);
+	if (err)
+		return err;
+
+	return 0;
+}
+
+/**
+ * write_log - write an empty log.
+ */
+static int write_log(void)
+{
+	struct ubifs_cs_node cs;
+	int err, i, lnum;
+
+	lnum = UBIFS_LOG_LNUM;
+
+	cs.ch.node_type = UBIFS_CS_NODE;
+	cs.cmt_no = cpu_to_le64(0);
+
+	err = write_node(&cs, UBIFS_CS_NODE_SZ, lnum);
+	if (err)
+		return err;
+
+	lnum += 1;
+
+	for (i = 1; i < c->log_lebs; i++, lnum++) {
+		err = write_empty_leb(lnum);
+		if (err)
+			return err;
+	}
+
+	return 0;
+}
+
+/**
+ * write_lpt - write the LEB properties tree.
+ */
+static int write_lpt(void)
+{
+	int err, lnum;
+
+	err = create_lpt(c);
+	if (err)
+		return err;
+
+	lnum = c->nhead_lnum + 1;
+	while (lnum <= c->lpt_last) {
+		err = write_empty_leb(lnum++);
+		if (err)
+			return err;
+	}
+
+	return 0;
+}
+
+/**
+ * write_orphan_area - write an empty orphan area.
+ */
+static int write_orphan_area(void)
+{
+	int err, i, lnum;
+
+	lnum = UBIFS_LOG_LNUM + c->log_lebs + c->lpt_lebs;
+	for (i = 0; i < c->orph_lebs; i++, lnum++) {
+		err = write_empty_leb(lnum);
+		if (err)
+			return err;
+	}
+	return 0;
+}
+
+/**
+ * open_target - open the output file.
+ */
+static int open_target(void)
+{
+	out_fd = open(output, O_CREAT | O_RDWR | O_TRUNC,
+		      S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH);
+	if (out_fd == -1)
+		return sys_err_msg("cannot create output file '%s'", output);
+	return 0;
+}
+
+/**
+ * close_target - close the output file.
+ */
+static int close_target(void)
+{
+	if (close(out_fd) == -1)
+		return sys_err_msg("cannot close output file '%s'", output);
+	return 0;
+}
+
+/**
+ * init - initialize things.
+ */
+static int init(void)
+{
+	int err, i, main_lebs, big_lpt = 0, sz;
+
+	c->highest_inum = UBIFS_FIRST_INO;
+
+	c->jhead_cnt = 1;
+
+	main_lebs = c->max_leb_cnt - UBIFS_SB_LEBS - UBIFS_MST_LEBS;
+	main_lebs -= c->log_lebs + c->orph_lebs;
+
+	err = calc_dflt_lpt_geom(c, &main_lebs, &big_lpt);
+	if (err)
+		return err;
+
+	c->main_first = UBIFS_LOG_LNUM + c->log_lebs + c->lpt_lebs +
+			c->orph_lebs;
+	head_lnum = c->main_first;
+	head_offs = 0;
+
+	c->lpt_first = UBIFS_LOG_LNUM + c->log_lebs;
+	c->lpt_last = c->lpt_first + c->lpt_lebs - 1;
+
+	c->lpt = malloc(c->main_lebs * sizeof(struct ubifs_lprops));
+	if (!c->lpt)
+		return err_msg("unable to allocate LPT");
+
+	c->ltab = malloc(c->lpt_lebs * sizeof(struct ubifs_lprops));
+	if (!c->ltab)
+		return err_msg("unable to allocate LPT ltab");
+
+	/* Initialize LPT's own lprops */
+	for (i = 0; i < c->lpt_lebs; i++) {
+		c->ltab[i].free = c->leb_size;
+		c->ltab[i].dirty = 0;
+	}
+
+	c->dead_wm = ALIGN(MIN_WRITE_SZ, c->min_io_size);
+	c->dark_wm = ALIGN(UBIFS_MAX_NODE_SZ, c->min_io_size);
+	dbg_msg(1, "dead_wm %d  dark_wm %d", c->dead_wm, c->dark_wm);
+
+	leb_buf = malloc(c->leb_size);
+	if (!leb_buf)
+		return err_msg("out of memory");
+
+	node_buf = malloc(NODE_BUFFER_SIZE);
+	if (!node_buf)
+		return err_msg("out of memory");
+
+	block_buf = malloc(UBIFS_BLOCK_SIZE);
+	if (!block_buf)
+		return err_msg("out of memory");
+
+	sz = sizeof(struct inum_mapping *) * HASH_TABLE_SIZE;
+	hash_table = malloc(sz);
+	if (!hash_table)
+		return err_msg("out of memory");
+	memset(hash_table, 0, sz);
+
+	err = init_compression();
+	if (err)
+		return err;
+
+	return 0;
+}
+
+static void destroy_hash_table(void)
+{
+	int i;
+
+	for (i = 0; i < HASH_TABLE_SIZE; i++) {
+		struct inum_mapping *im, *q;
+
+		for (im = hash_table[i]; im; ) {
+			q = im;
+			im = im->next;
+			free(q->path_name);
+			free(q);
+		}
+	}
+}
+
+/**
+ * deinit - deinitialize things.
+ */
+static void deinit(void)
+{
+	free(c->lpt);
+	free(c->ltab);
+	free(leb_buf);
+	free(node_buf);
+	free(block_buf);
+	destroy_hash_table();
+	free(hash_table);
+	destroy_compression();
+	free_devtable_info();
+}
+
+/**
+ * mkfs - make the file system.
+ *
+ * Each on-flash area has a corresponding function to create it. The order of
+ * the functions reflects what information must be known to complete each stage.
+ * As a consequence the output file is not written sequentially. No effort has
+ * been made to make efficient use of memory or to allow for the possibility of
+ * incremental updates to the output file.
+ */
+static int mkfs(void)
+{
+	int err = 0;
+
+	err = init();
+	if (err)
+		goto out;
+
+	err = write_data();
+	if (err)
+		goto out;
+
+	err = set_gc_lnum();
+	if (err)
+		goto out;
+
+	err = write_index();
+	if (err)
+		goto out;
+
+	err = finalize_leb_cnt();
+	if (err)
+		goto out;
+
+	err = write_lpt();
+	if (err)
+		goto out;
+
+	err = write_super();
+	if (err)
+		goto out;
+
+	err = write_master();
+	if (err)
+		goto out;
+
+	err = write_log();
+	if (err)
+		goto out;
+
+	err = write_orphan_area();
+
+out:
+	deinit();
+	return err;
+}
+
+int main(int argc, char *argv[])
+{
+	int err;
+
+	err = get_options(argc, argv);
+	if (err)
+		return err;
+
+	err = open_target();
+	if (err)
+		return err;
+
+	err = mkfs();
+	if (err) {
+		close_target();
+		return err;
+	}
+
+	err = close_target();
+	if (err)
+		return err;
+
+	if (verbose)
+		printf("Success!\n");
+
+	return 0;
+}
diff --git a/mkfs.ubifs/mkfs.ubifs.h b/mkfs.ubifs/mkfs.ubifs.h
new file mode 100644
index 0000000..7f2bdc2
--- /dev/null
+++ b/mkfs.ubifs/mkfs.ubifs.h
@@ -0,0 +1,144 @@
+/*
+ * Copyright (C) 2008 Nokia Corporation.
+ * Copyright (C) 2008 University of Szeged, Hungary
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy
+ *          Adrian Hunter
+ *          Zoltan Sogor
+ */
+
+#ifndef __MKFS_UBIFS_H__
+#define __MKFS_UBIFS_H__
+
+#define _GNU_SOURCE
+#define _LARGEFILE64_SOURCE
+#include <unistd.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <limits.h>
+#include <string.h>
+#include <stdint.h>
+#include <endian.h>
+#include <byteswap.h>
+#include <linux/types.h>
+#include <linux/fs.h>
+
+#include <getopt.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/ioctl.h>
+#include <fcntl.h>
+#include <dirent.h>
+#include <errno.h>
+#include <libgen.h>
+#include <ctype.h>
+#include <uuid/uuid.h>
+
+#include "crc32.h"
+#include "defs.h"
+#include "crc16.h"
+#include "ubifs-media.h"
+#include "ubifs.h"
+#include "key.h"
+#include "lpt.h"
+#include "compr.h"
+
+/*
+ * Compression flags are duplicated so that compr.c can compile without ubifs.h.
+ * Here we make sure they are the same.
+ */
+#if MKFS_UBIFS_COMPR_NONE != UBIFS_COMPR_NONE
+#error MKFS_UBIFS_COMPR_NONE != UBIFS_COMPR_NONE
+#endif
+#if MKFS_UBIFS_COMPR_LZO != UBIFS_COMPR_LZO
+#error MKFS_UBIFS_COMPR_LZO != UBIFS_COMPR_LZO
+#endif
+#if MKFS_UBIFS_COMPR_ZLIB != UBIFS_COMPR_ZLIB
+#error MKFS_UBIFS_COMPR_ZLIB != UBIFS_COMPR_ZLIB
+#endif
+
+extern int verbose;
+extern int debug_level;
+
+#define dbg_msg(lvl, fmt, ...) do {if (debug_level >= lvl)                \
+	printf("mkfs.ubifs: %s: " fmt "\n", __FUNCTION__, ##__VA_ARGS__); \
+} while(0)
+
+#define err_msg(fmt, ...) ({                                \
+	fprintf(stderr, "Error: " fmt "\n", ##__VA_ARGS__); \
+	-1;                                                 \
+})
+
+#define sys_err_msg(fmt, ...) ({                                         \
+	int err_ = errno;                                                \
+	fprintf(stderr, "Error: " fmt "\n", ##__VA_ARGS__);              \
+	fprintf(stderr, "       %s (error %d)\n", strerror(err_), err_); \
+	-1;                                                              \
+})
+
+/**
+ * struct path_htbl_element - an element of the path hash table.
+ * @path: the UBIFS path the element describes (the key of the element)
+ * @name_htbl: one more (nested) hash table containing names of all
+ *             files/directories/device nodes which should be created at this
+ *             path
+ *
+ * See device table handling for more information.
+ */
+struct path_htbl_element {
+	const char *path;
+	struct hashtable *name_htbl;
+};
+
+/**
+ * struct name_htbl_element - an element in the name hash table
+ * @name: name of the file/directory/device node (the key of the element)
+ * @mode: accsess rights and file type
+ * @uid: user ID
+ * @gid: group ID
+ * @major: device node major number
+ * @minor: device node minor number
+ *
+ * This is an element of the name hash table. Name hash table sits in the path
+ * hash table elements and describes file names which should be created/changed
+ * at this path.
+ */
+struct name_htbl_element {
+	const char *name;
+	unsigned int mode;
+	unsigned int uid;
+	unsigned int gid;
+	dev_t dev;
+};
+
+struct hashtable_itr;
+
+int write_leb(int lnum, int len, void *buf);
+int parse_devtable(const char *root, const char *tbl_file);
+struct path_htbl_element *devtbl_find_path(const char *path);
+struct name_htbl_element *devtbl_find_name(struct path_htbl_element *ph_elt,
+					   const char *name);
+int override_attributes(struct stat *st, struct path_htbl_element *ph_elt,
+			struct name_htbl_element *nh_elt);
+struct name_htbl_element *
+first_name_htbl_element(struct path_htbl_element *ph_elt,
+			struct hashtable_itr **itr);
+struct name_htbl_element *
+next_name_htbl_element(struct path_htbl_element *ph_elt,
+		       struct hashtable_itr **itr);
+void free_devtable_info(void);
+
+#endif
diff --git a/mkfs.ubifs/ubifs-media.h b/mkfs.ubifs/ubifs-media.h
new file mode 100644
index 0000000..67c388f
--- /dev/null
+++ b/mkfs.ubifs/ubifs-media.h
@@ -0,0 +1,741 @@
+/*
+ * This file is part of UBIFS.
+ *
+ * Copyright (C) 2006-2008 Nokia Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy (Битюцкий Артём)
+ *          Adrian Hunter
+ */
+
+/*
+ * This file describes UBIFS on-flash format and contains definitions of all the
+ * relevant data structures and constants.
+ *
+ * All UBIFS on-flash objects are stored in the form of nodes. All nodes start
+ * with the UBIFS node magic number and have the same common header. Nodes
+ * always sit at 8-byte aligned positions on the media and node header sizes are
+ * also 8-byte aligned (except for the indexing node and the padding node).
+ */
+
+#ifndef __UBIFS_MEDIA_H__
+#define __UBIFS_MEDIA_H__
+
+/* UBIFS node magic number (must not have the padding byte first or last) */
+#define UBIFS_NODE_MAGIC  0x06101831
+
+/* UBIFS on-flash format version */
+#define UBIFS_FORMAT_VERSION 4
+
+/* Minimum logical eraseblock size in bytes */
+#define UBIFS_MIN_LEB_SZ (15*1024)
+
+/* Initial CRC32 value used when calculating CRC checksums */
+#define UBIFS_CRC32_INIT 0xFFFFFFFFU
+
+/*
+ * UBIFS does not try to compress data if its length is less than the below
+ * constant.
+ */
+#define UBIFS_MIN_COMPR_LEN 128
+
+/* Root inode number */
+#define UBIFS_ROOT_INO 1
+
+/* Lowest inode number used for regular inodes (not UBIFS-only internal ones) */
+#define UBIFS_FIRST_INO 64
+
+/*
+ * Maximum file name and extended attribute length (must be a multiple of 8,
+ * minus 1).
+ */
+#define UBIFS_MAX_NLEN 255
+
+/* Maximum number of data journal heads */
+#define UBIFS_MAX_JHEADS 1
+
+/*
+ * Size of UBIFS data block. Note, UBIFS is not a block oriented file-system,
+ * which means that it does not treat the underlying media as consisting of
+ * blocks like in case of hard drives. Do not be confused. UBIFS block is just
+ * the maximum amount of data which one data node can have or which can be
+ * attached to an inode node.
+ */
+#define UBIFS_BLOCK_SIZE  4096
+#define UBIFS_BLOCK_SHIFT 12
+#define UBIFS_BLOCK_MASK  0x00000FFF
+
+/* UBIFS padding byte pattern (must not be first or last byte of node magic) */
+#define UBIFS_PADDING_BYTE 0xCE
+
+/* Maximum possible key length */
+#define UBIFS_MAX_KEY_LEN 16
+
+/* Key length ("simple" format) */
+#define UBIFS_SK_LEN 8
+
+/* Minimum index tree fanout */
+#define UBIFS_MIN_FANOUT 2
+
+/* Maximum number of levels in UBIFS indexing B-tree */
+#define UBIFS_MAX_LEVELS 512
+
+/* Maximum amount of data attached to an inode in bytes */
+#define UBIFS_MAX_INO_DATA UBIFS_BLOCK_SIZE
+
+/* LEB Properties Tree fanout (must be power of 2) and fanout shift */
+#define UBIFS_LPT_FANOUT 4
+#define UBIFS_LPT_FANOUT_SHIFT 2
+
+/* LEB Properties Tree bit field sizes */
+#define UBIFS_LPT_CRC_BITS 16
+#define UBIFS_LPT_CRC_BYTES 2
+#define UBIFS_LPT_TYPE_BITS 4
+
+/* The key is always at the same position in all keyed nodes */
+#define UBIFS_KEY_OFFSET offsetof(struct ubifs_ino_node, key)
+
+/*
+ * LEB Properties Tree node types.
+ *
+ * UBIFS_LPT_PNODE: LPT leaf node (contains LEB properties)
+ * UBIFS_LPT_NNODE: LPT internal node
+ * UBIFS_LPT_LTAB: LPT's own lprops table
+ * UBIFS_LPT_LSAVE: LPT's save table (big model only)
+ * UBIFS_LPT_NODE_CNT: count of LPT node types
+ * UBIFS_LPT_NOT_A_NODE: all ones (15 for 4 bits) is never a valid node type
+ */
+enum {
+	UBIFS_LPT_PNODE,
+	UBIFS_LPT_NNODE,
+	UBIFS_LPT_LTAB,
+	UBIFS_LPT_LSAVE,
+	UBIFS_LPT_NODE_CNT,
+	UBIFS_LPT_NOT_A_NODE = (1 << UBIFS_LPT_TYPE_BITS) - 1,
+};
+
+/*
+ * UBIFS inode types.
+ *
+ * UBIFS_ITYPE_REG: regular file
+ * UBIFS_ITYPE_DIR: directory
+ * UBIFS_ITYPE_LNK: soft link
+ * UBIFS_ITYPE_BLK: block device node
+ * UBIFS_ITYPE_CHR: character device node
+ * UBIFS_ITYPE_FIFO: fifo
+ * UBIFS_ITYPE_SOCK: socket
+ * UBIFS_ITYPES_CNT: count of supported file types
+ */
+enum {
+	UBIFS_ITYPE_REG,
+	UBIFS_ITYPE_DIR,
+	UBIFS_ITYPE_LNK,
+	UBIFS_ITYPE_BLK,
+	UBIFS_ITYPE_CHR,
+	UBIFS_ITYPE_FIFO,
+	UBIFS_ITYPE_SOCK,
+	UBIFS_ITYPES_CNT,
+};
+
+/*
+ * Supported key hash functions.
+ *
+ * UBIFS_KEY_HASH_R5: R5 hash
+ * UBIFS_KEY_HASH_TEST: test hash which just returns first 4 bytes of the name
+ */
+enum {
+	UBIFS_KEY_HASH_R5,
+	UBIFS_KEY_HASH_TEST,
+};
+
+/*
+ * Supported key formats.
+ *
+ * UBIFS_SIMPLE_KEY_FMT: simple key format
+ */
+enum {
+	UBIFS_SIMPLE_KEY_FMT,
+};
+
+/*
+ * The simple key format uses 29 bits for storing UBIFS block number and hash
+ * value.
+ */
+#define UBIFS_S_KEY_BLOCK_BITS 29
+#define UBIFS_S_KEY_BLOCK_MASK 0x1FFFFFFF
+#define UBIFS_S_KEY_HASH_BITS  UBIFS_S_KEY_BLOCK_BITS
+#define UBIFS_S_KEY_HASH_MASK  UBIFS_S_KEY_BLOCK_MASK
+
+/*
+ * Key types.
+ *
+ * UBIFS_INO_KEY: inode node key
+ * UBIFS_DATA_KEY: data node key
+ * UBIFS_DENT_KEY: directory entry node key
+ * UBIFS_XENT_KEY: extended attribute entry key
+ * UBIFS_KEY_TYPES_CNT: number of supported key types
+ */
+enum {
+	UBIFS_INO_KEY,
+	UBIFS_DATA_KEY,
+	UBIFS_DENT_KEY,
+	UBIFS_XENT_KEY,
+	UBIFS_KEY_TYPES_CNT,
+};
+
+/* Count of LEBs reserved for the superblock area */
+#define UBIFS_SB_LEBS 1
+/* Count of LEBs reserved for the master area */
+#define UBIFS_MST_LEBS 2
+
+/* First LEB of the superblock area */
+#define UBIFS_SB_LNUM 0
+/* First LEB of the master area */
+#define UBIFS_MST_LNUM (UBIFS_SB_LNUM + UBIFS_SB_LEBS)
+/* First LEB of the log area */
+#define UBIFS_LOG_LNUM (UBIFS_MST_LNUM + UBIFS_MST_LEBS)
+
+/*
+ * The below constants define the absolute minimum values for various UBIFS
+ * media areas. Many of them actually depend of flash geometry and the FS
+ * configuration (number of journal heads, orphan LEBs, etc). This means that
+ * the smallest volume size which can be used for UBIFS cannot be pre-defined
+ * by these constants. The file-system that meets the below limitation will not
+ * necessarily mount. UBIFS does run-time calculations and validates the FS
+ * size.
+ */
+
+/* Minimum number of logical eraseblocks in the log */
+#define UBIFS_MIN_LOG_LEBS 2
+/* Minimum number of bud logical eraseblocks (one for each head) */
+#define UBIFS_MIN_BUD_LEBS 3
+/* Minimum number of journal logical eraseblocks */
+#define UBIFS_MIN_JNL_LEBS (UBIFS_MIN_LOG_LEBS + UBIFS_MIN_BUD_LEBS)
+/* Minimum number of LPT area logical eraseblocks */
+#define UBIFS_MIN_LPT_LEBS 2
+/* Minimum number of orphan area logical eraseblocks */
+#define UBIFS_MIN_ORPH_LEBS 1
+/*
+ * Minimum number of main area logical eraseblocks (buds, 2 for the index, 1
+ * for GC, 1 for deletions, and at least 1 for committed data).
+ */
+#define UBIFS_MIN_MAIN_LEBS (UBIFS_MIN_BUD_LEBS + 5)
+
+/* Minimum number of logical eraseblocks */
+#define UBIFS_MIN_LEB_CNT (UBIFS_SB_LEBS + UBIFS_MST_LEBS + \
+			   UBIFS_MIN_LOG_LEBS + UBIFS_MIN_LPT_LEBS + \
+			   UBIFS_MIN_ORPH_LEBS + UBIFS_MIN_MAIN_LEBS)
+
+/* Node sizes (N.B. these are guaranteed to be multiples of 8) */
+#define UBIFS_CH_SZ        sizeof(struct ubifs_ch)
+#define UBIFS_INO_NODE_SZ  sizeof(struct ubifs_ino_node)
+#define UBIFS_DATA_NODE_SZ sizeof(struct ubifs_data_node)
+#define UBIFS_DENT_NODE_SZ sizeof(struct ubifs_dent_node)
+#define UBIFS_TRUN_NODE_SZ sizeof(struct ubifs_trun_node)
+#define UBIFS_PAD_NODE_SZ  sizeof(struct ubifs_pad_node)
+#define UBIFS_SB_NODE_SZ   sizeof(struct ubifs_sb_node)
+#define UBIFS_MST_NODE_SZ  sizeof(struct ubifs_mst_node)
+#define UBIFS_REF_NODE_SZ  sizeof(struct ubifs_ref_node)
+#define UBIFS_IDX_NODE_SZ  sizeof(struct ubifs_idx_node)
+#define UBIFS_CS_NODE_SZ   sizeof(struct ubifs_cs_node)
+#define UBIFS_ORPH_NODE_SZ sizeof(struct ubifs_orph_node)
+/* Extended attribute entry nodes are identical to directory entry nodes */
+#define UBIFS_XENT_NODE_SZ UBIFS_DENT_NODE_SZ
+/* Only this does not have to be multiple of 8 bytes */
+#define UBIFS_BRANCH_SZ    sizeof(struct ubifs_branch)
+
+/* Maximum node sizes (N.B. these are guaranteed to be multiples of 8) */
+#define UBIFS_MAX_DATA_NODE_SZ  (UBIFS_DATA_NODE_SZ + UBIFS_BLOCK_SIZE)
+#define UBIFS_MAX_INO_NODE_SZ   (UBIFS_INO_NODE_SZ + UBIFS_MAX_INO_DATA)
+#define UBIFS_MAX_DENT_NODE_SZ  (UBIFS_DENT_NODE_SZ + UBIFS_MAX_NLEN + 1)
+#define UBIFS_MAX_XENT_NODE_SZ  UBIFS_MAX_DENT_NODE_SZ
+
+/* The largest UBIFS node */
+#define UBIFS_MAX_NODE_SZ UBIFS_MAX_INO_NODE_SZ
+
+/*
+ * On-flash inode flags.
+ *
+ * UBIFS_COMPR_FL: use compression for this inode
+ * UBIFS_SYNC_FL:  I/O on this inode has to be synchronous
+ * UBIFS_IMMUTABLE_FL: inode is immutable
+ * UBIFS_APPEND_FL: writes to the inode may only append data
+ * UBIFS_DIRSYNC_FL: I/O on this directory inode has to be synchronous
+ *
+ * Note, these are on-flash flags which correspond to ioctl flags
+ * (@FS_COMPR_FL, etc). They have the same values now, but generally, do not
+ * have to be the same.
+ */
+enum {
+	UBIFS_COMPR_FL     = 0x01,
+	UBIFS_SYNC_FL      = 0x02,
+	UBIFS_IMMUTABLE_FL = 0x04,
+	UBIFS_APPEND_FL    = 0x08,
+	UBIFS_DIRSYNC_FL   = 0x10,
+};
+
+/* Inode flag bits used by UBIFS */
+#define UBIFS_FL_MASK 0x0000001F
+
+/*
+ * UBIFS compression algorithms.
+ *
+ * UBIFS_COMPR_NONE: no compression
+ * UBIFS_COMPR_LZO: LZO compression
+ * UBIFS_COMPR_ZLIB: ZLIB compression
+ * UBIFS_COMPR_TYPES_CNT: count of supported compression types
+ */
+enum {
+	UBIFS_COMPR_NONE,
+	UBIFS_COMPR_LZO,
+	UBIFS_COMPR_ZLIB,
+	UBIFS_COMPR_TYPES_CNT,
+};
+
+/*
+ * UBIFS node types.
+ *
+ * UBIFS_INO_NODE: inode node
+ * UBIFS_DATA_NODE: data node
+ * UBIFS_DENT_NODE: directory entry node
+ * UBIFS_XENT_NODE: extended attribute node
+ * UBIFS_TRUN_NODE: truncation node
+ * UBIFS_PAD_NODE: padding node
+ * UBIFS_SB_NODE: superblock node
+ * UBIFS_MST_NODE: master node
+ * UBIFS_REF_NODE: LEB reference node
+ * UBIFS_IDX_NODE: index node
+ * UBIFS_CS_NODE: commit start node
+ * UBIFS_ORPH_NODE: orphan node
+ * UBIFS_NODE_TYPES_CNT: count of supported node types
+ *
+ * Note, we index arrays by these numbers, so keep them low and contiguous.
+ * Node type constants for inodes, direntries and so on have to be the same as
+ * corresponding key type constants.
+ */
+enum {
+	UBIFS_INO_NODE,
+	UBIFS_DATA_NODE,
+	UBIFS_DENT_NODE,
+	UBIFS_XENT_NODE,
+	UBIFS_TRUN_NODE,
+	UBIFS_PAD_NODE,
+	UBIFS_SB_NODE,
+	UBIFS_MST_NODE,
+	UBIFS_REF_NODE,
+	UBIFS_IDX_NODE,
+	UBIFS_CS_NODE,
+	UBIFS_ORPH_NODE,
+	UBIFS_NODE_TYPES_CNT,
+};
+
+/*
+ * Master node flags.
+ *
+ * UBIFS_MST_DIRTY: rebooted uncleanly - master node is dirty
+ * UBIFS_MST_NO_ORPHS: no orphan inodes present
+ * UBIFS_MST_RCVRY: written by recovery
+ */
+enum {
+	UBIFS_MST_DIRTY = 1,
+	UBIFS_MST_NO_ORPHS = 2,
+	UBIFS_MST_RCVRY = 4,
+};
+
+/*
+ * Node group type (used by recovery to recover whole group or none).
+ *
+ * UBIFS_NO_NODE_GROUP: this node is not part of a group
+ * UBIFS_IN_NODE_GROUP: this node is a part of a group
+ * UBIFS_LAST_OF_NODE_GROUP: this node is the last in a group
+ */
+enum {
+	UBIFS_NO_NODE_GROUP = 0,
+	UBIFS_IN_NODE_GROUP,
+	UBIFS_LAST_OF_NODE_GROUP,
+};
+
+/*
+ * Superblock flags.
+ *
+ * UBIFS_FLG_BIGLPT: if "big" LPT model is used if set
+ */
+enum {
+	UBIFS_FLG_BIGLPT = 0x02,
+};
+
+/**
+ * struct ubifs_ch - common header node.
+ * @magic: UBIFS node magic number (%UBIFS_NODE_MAGIC)
+ * @crc: CRC-32 checksum of the node header
+ * @sqnum: sequence number
+ * @len: full node length
+ * @node_type: node type
+ * @group_type: node group type
+ * @padding: reserved for future, zeroes
+ *
+ * Every UBIFS node starts with this common part. If the node has a key, the
+ * key always goes next.
+ */
+struct ubifs_ch {
+	__le32 magic;
+	__le32 crc;
+	__le64 sqnum;
+	__le32 len;
+	__u8 node_type;
+	__u8 group_type;
+	__u8 padding[2];
+} __attribute__ ((packed));
+
+/**
+ * union ubifs_dev_desc - device node descriptor.
+ * @new: new type device descriptor
+ * @huge: huge type device descriptor
+ *
+ * This data structure describes major/minor numbers of a device node. In an
+ * inode is a device node then its data contains an object of this type. UBIFS
+ * uses standard Linux "new" and "huge" device node encodings.
+ */
+union ubifs_dev_desc {
+	__le32 new;
+	__le64 huge;
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_ino_node - inode node.
+ * @ch: common header
+ * @key: node key
+ * @creat_sqnum: sequence number at time of creation
+ * @size: inode size in bytes (amount of uncompressed data)
+ * @atime_sec: access time seconds
+ * @ctime_sec: creation time seconds
+ * @mtime_sec: modification time seconds
+ * @atime_nsec: access time nanoseconds
+ * @ctime_nsec: creation time nanoseconds
+ * @mtime_nsec: modification time nanoseconds
+ * @nlink: number of hard links
+ * @uid: owner ID
+ * @gid: group ID
+ * @mode: access flags
+ * @flags: per-inode flags (%UBIFS_COMPR_FL, %UBIFS_SYNC_FL, etc)
+ * @data_len: inode data length
+ * @xattr_cnt: count of extended attributes this inode has
+ * @xattr_size: summarized size of all extended attributes in bytes
+ * @xattr_names: sum of lengths of all extended attribute names belonging to
+ *               this inode
+ * @compr_type: compression type used for this inode
+ * @padding: reserved for future, zeroes
+ * @data: data attached to the inode
+ *
+ * Note, even though inode compression type is defined by @compr_type, some
+ * nodes of this inode may be compressed with different compressor - this
+ * happens if compression type is changed while the inode already has data
+ * nodes. But @compr_type will be use for further writes to the inode.
+ *
+ * Note, do not forget to amend 'zero_ino_node_unused()' function when changing
+ * the padding fields.
+ */
+struct ubifs_ino_node {
+	struct ubifs_ch ch;
+	__u8 key[UBIFS_MAX_KEY_LEN];
+	__le64 creat_sqnum;
+	__le64 size;
+	__le64 atime_sec;
+	__le64 ctime_sec;
+	__le64 mtime_sec;
+	__le32 atime_nsec;
+	__le32 ctime_nsec;
+	__le32 mtime_nsec;
+	__le32 nlink;
+	__le32 uid;
+	__le32 gid;
+	__le32 mode;
+	__le32 flags;
+	__le32 data_len;
+	__le32 xattr_cnt;
+	__le64 xattr_size;
+	__le32 xattr_names;
+	__le16 compr_type;
+	__u8 padding[26]; /* Watch 'zero_ino_node_unused()' if changing! */
+	__u8 data[];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_dent_node - directory entry node.
+ * @ch: common header
+ * @key: node key
+ * @inum: target inode number
+ * @padding1: reserved for future, zeroes
+ * @type: type of the target inode (%UBIFS_ITYPE_REG, %UBIFS_ITYPE_DIR, etc)
+ * @nlen: name length
+ * @padding2: reserved for future, zeroes
+ * @name: zero-terminated name
+ *
+ * Note, do not forget to amend 'zero_dent_node_unused()' function when
+ * changing the padding fields.
+ */
+struct ubifs_dent_node {
+	struct ubifs_ch ch;
+	__u8 key[UBIFS_MAX_KEY_LEN];
+	__le64 inum;
+	__u8 padding1;
+	__u8 type;
+	__le16 nlen;
+	__u8 padding2[4]; /* Watch 'zero_dent_node_unused()' if changing! */
+	__u8 name[];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_data_node - data node.
+ * @ch: common header
+ * @key: node key
+ * @size: uncompressed data size in bytes
+ * @compr_type: compression type (%UBIFS_COMPR_NONE, %UBIFS_COMPR_LZO, etc)
+ * @padding: reserved for future, zeroes
+ * @data: data
+ *
+ * Note, do not forget to amend 'zero_data_node_unused()' function when
+ * changing the padding fields.
+ */
+struct ubifs_data_node {
+	struct ubifs_ch ch;
+	__u8 key[UBIFS_MAX_KEY_LEN];
+	__le32 size;
+	__le16 compr_type;
+	__u8 padding[2]; /* Watch 'zero_data_node_unused()' if changing! */
+	__u8 data[];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_trun_node - truncation node.
+ * @ch: common header
+ * @inum: truncated inode number
+ * @padding: reserved for future, zeroes
+ * @old_size: size before truncation
+ * @new_size: size after truncation
+ *
+ * This node exists only in the journal and never goes to the main area. Note,
+ * do not forget to amend 'zero_trun_node_unused()' function when changing the
+ * padding fields.
+ */
+struct ubifs_trun_node {
+	struct ubifs_ch ch;
+	__le32 inum;
+	__u8 padding[12]; /* Watch 'zero_trun_node_unused()' if changing! */
+	__le64 old_size;
+	__le64 new_size;
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_pad_node - padding node.
+ * @ch: common header
+ * @pad_len: how many bytes after this node are unused (because padded)
+ * @padding: reserved for future, zeroes
+ */
+struct ubifs_pad_node {
+	struct ubifs_ch ch;
+	__le32 pad_len;
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_sb_node - superblock node.
+ * @ch: common header
+ * @padding: reserved for future, zeroes
+ * @key_hash: type of hash function used in keys
+ * @key_fmt: format of the key
+ * @flags: file-system flags (%UBIFS_FLG_BIGLPT, etc)
+ * @min_io_size: minimal input/output unit size
+ * @leb_size: logical eraseblock size in bytes
+ * @leb_cnt: count of LEBs used by file-system
+ * @max_leb_cnt: maximum count of LEBs used by file-system
+ * @max_bud_bytes: maximum amount of data stored in buds
+ * @log_lebs: log size in logical eraseblocks
+ * @lpt_lebs: number of LEBs used for lprops table
+ * @orph_lebs: number of LEBs used for recording orphans
+ * @jhead_cnt: count of journal heads
+ * @fanout: tree fanout (max. number of links per indexing node)
+ * @lsave_cnt: number of LEB numbers in LPT's save table
+ * @fmt_version: UBIFS on-flash format version
+ * @default_compr: default compression algorithm (%UBIFS_COMPR_LZO, etc)
+ * @padding1: reserved for future, zeroes
+ * @rp_uid: reserve pool UID
+ * @rp_gid: reserve pool GID
+ * @rp_size: size of the reserved pool in bytes
+ * @padding2: reserved for future, zeroes
+ * @time_gran: time granularity in nanoseconds
+ * @uuid: UUID generated when the file system image was created
+ */
+struct ubifs_sb_node {
+	struct ubifs_ch ch;
+	__u8 padding[2];
+	__u8 key_hash;
+	__u8 key_fmt;
+	__le32 flags;
+	__le32 min_io_size;
+	__le32 leb_size;
+	__le32 leb_cnt;
+	__le32 max_leb_cnt;
+	__le64 max_bud_bytes;
+	__le32 log_lebs;
+	__le32 lpt_lebs;
+	__le32 orph_lebs;
+	__le32 jhead_cnt;
+	__le32 fanout;
+	__le32 lsave_cnt;
+	__le32 fmt_version;
+	__le16 default_compr;
+	__u8 padding1[2];
+	__le32 rp_uid;
+	__le32 rp_gid;
+	__le64 rp_size;
+	__le32 time_gran;
+	__u8 uuid[16];
+	__u8 padding2[3972];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_mst_node - master node.
+ * @ch: common header
+ * @highest_inum: highest inode number in the committed index
+ * @cmt_no: commit number
+ * @flags: various flags (%UBIFS_MST_DIRTY, etc)
+ * @log_lnum: start of the log
+ * @root_lnum: LEB number of the root indexing node
+ * @root_offs: offset within @root_lnum
+ * @root_len: root indexing node length
+ * @gc_lnum: LEB reserved for garbage collection (%-1 value means the LEB was
+ * not reserved and should be reserved on mount)
+ * @ihead_lnum: LEB number of index head
+ * @ihead_offs: offset of index head
+ * @index_size: size of index on flash
+ * @total_free: total free space in bytes
+ * @total_dirty: total dirty space in bytes
+ * @total_used: total used space in bytes (includes only data LEBs)
+ * @total_dead: total dead space in bytes (includes only data LEBs)
+ * @total_dark: total dark space in bytes (includes only data LEBs)
+ * @lpt_lnum: LEB number of LPT root nnode
+ * @lpt_offs: offset of LPT root nnode
+ * @nhead_lnum: LEB number of LPT head
+ * @nhead_offs: offset of LPT head
+ * @ltab_lnum: LEB number of LPT's own lprops table
+ * @ltab_offs: offset of LPT's own lprops table
+ * @lsave_lnum: LEB number of LPT's save table (big model only)
+ * @lsave_offs: offset of LPT's save table (big model only)
+ * @lscan_lnum: LEB number of last LPT scan
+ * @empty_lebs: number of empty logical eraseblocks
+ * @idx_lebs: number of indexing logical eraseblocks
+ * @leb_cnt: count of LEBs used by file-system
+ * @padding: reserved for future, zeroes
+ */
+struct ubifs_mst_node {
+	struct ubifs_ch ch;
+	__le64 highest_inum;
+	__le64 cmt_no;
+	__le32 flags;
+	__le32 log_lnum;
+	__le32 root_lnum;
+	__le32 root_offs;
+	__le32 root_len;
+	__le32 gc_lnum;
+	__le32 ihead_lnum;
+	__le32 ihead_offs;
+	__le64 index_size;
+	__le64 total_free;
+	__le64 total_dirty;
+	__le64 total_used;
+	__le64 total_dead;
+	__le64 total_dark;
+	__le32 lpt_lnum;
+	__le32 lpt_offs;
+	__le32 nhead_lnum;
+	__le32 nhead_offs;
+	__le32 ltab_lnum;
+	__le32 ltab_offs;
+	__le32 lsave_lnum;
+	__le32 lsave_offs;
+	__le32 lscan_lnum;
+	__le32 empty_lebs;
+	__le32 idx_lebs;
+	__le32 leb_cnt;
+	__u8 padding[344];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_ref_node - logical eraseblock reference node.
+ * @ch: common header
+ * @lnum: the referred logical eraseblock number
+ * @offs: start offset in the referred LEB
+ * @jhead: journal head number
+ * @padding: reserved for future, zeroes
+ */
+struct ubifs_ref_node {
+	struct ubifs_ch ch;
+	__le32 lnum;
+	__le32 offs;
+	__le32 jhead;
+	__u8 padding[28];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_branch - key/reference/length branch
+ * @lnum: LEB number of the target node
+ * @offs: offset within @lnum
+ * @len: target node length
+ * @key: key
+ */
+struct ubifs_branch {
+	__le32 lnum;
+	__le32 offs;
+	__le32 len;
+	__u8 key[];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_idx_node - indexing node.
+ * @ch: common header
+ * @child_cnt: number of child index nodes
+ * @level: tree level
+ * @branches: LEB number / offset / length / key branches
+ */
+struct ubifs_idx_node {
+	struct ubifs_ch ch;
+	__le16 child_cnt;
+	__le16 level;
+	__u8 branches[];
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_cs_node - commit start node.
+ * @ch: common header
+ * @cmt_no: commit number
+ */
+struct ubifs_cs_node {
+	struct ubifs_ch ch;
+	__le64 cmt_no;
+} __attribute__ ((packed));
+
+/**
+ * struct ubifs_orph_node - orphan node.
+ * @ch: common header
+ * @cmt_no: commit number (also top bit is set on the last node of the commit)
+ * @inos: inode numbers of orphans
+ */
+struct ubifs_orph_node {
+	struct ubifs_ch ch;
+	__le64 cmt_no;
+	__le64 inos[];
+} __attribute__ ((packed));
+
+#endif /* __UBIFS_MEDIA_H__ */
diff --git a/mkfs.ubifs/ubifs.h b/mkfs.ubifs/ubifs.h
new file mode 100644
index 0000000..0804801
--- /dev/null
+++ b/mkfs.ubifs/ubifs.h
@@ -0,0 +1,434 @@
+/*
+ * This file is part of UBIFS.
+ *
+ * Copyright (C) 2008 Nokia Corporation.
+ * Copyright (C) 2008 University of Szeged, Hungary
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 as published by
+ * the Free Software Foundation.
+ *
+ * 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., 51
+ * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * Authors: Artem Bityutskiy
+ *          Adrian Hunter
+ *          Zoltan Sogor
+ */
+
+#ifndef __UBIFS_H__
+#define __UBIFS_H__
+
+/* Minimum amount of data UBIFS writes to the flash */
+#define MIN_WRITE_SZ (UBIFS_DATA_NODE_SZ + 8)
+
+/* Largest key size supported in this implementation */
+#define CUR_MAX_KEY_LEN UBIFS_SK_LEN
+
+/*
+ * There is no notion of truncation key because truncation nodes do not exist
+ * in TNC. However, when replaying, it is handy to introduce fake "truncation"
+ * keys for truncation nodes because the code becomes simpler. So we define
+ * %UBIFS_TRUN_KEY type.
+ */
+#define UBIFS_TRUN_KEY UBIFS_KEY_TYPES_CNT
+
+/* The below union makes it easier to deal with keys */
+union ubifs_key
+{
+	uint8_t u8[CUR_MAX_KEY_LEN];
+	uint32_t u32[CUR_MAX_KEY_LEN/4];
+	uint64_t u64[CUR_MAX_KEY_LEN/8];
+	__le32 j32[CUR_MAX_KEY_LEN/4];
+};
+
+/*
+ * LEB properties flags.
+ *
+ * LPROPS_UNCAT: not categorized
+ * LPROPS_DIRTY: dirty > 0, not index
+ * LPROPS_DIRTY_IDX: dirty + free > UBIFS_CH_SZ and index
+ * LPROPS_FREE: free > 0, not empty, not index
+ * LPROPS_HEAP_CNT: number of heaps used for storing categorized LEBs
+ * LPROPS_EMPTY: LEB is empty, not taken
+ * LPROPS_FREEABLE: free + dirty == leb_size, not index, not taken
+ * LPROPS_FRDI_IDX: free + dirty == leb_size and index, may be taken
+ * LPROPS_CAT_MASK: mask for the LEB categories above
+ * LPROPS_TAKEN: LEB was taken (this flag is not saved on the media)
+ * LPROPS_INDEX: LEB contains indexing nodes (this flag also exists on flash)
+ */
+enum {
+	LPROPS_UNCAT     =  0,
+	LPROPS_DIRTY     =  1,
+	LPROPS_DIRTY_IDX =  2,
+	LPROPS_FREE      =  3,
+	LPROPS_HEAP_CNT  =  3,
+	LPROPS_EMPTY     =  4,
+	LPROPS_FREEABLE  =  5,
+	LPROPS_FRDI_IDX  =  6,
+	LPROPS_CAT_MASK  = 15,
+	LPROPS_TAKEN     = 16,
+	LPROPS_INDEX     = 32,
+};
+
+/**
+ * struct ubifs_lprops - logical eraseblock properties.
+ * @free: amount of free space in bytes
+ * @dirty: amount of dirty space in bytes
+ * @flags: LEB properties flags (see above)
+ */
+struct ubifs_lprops
+{
+	int free;
+	int dirty;
+	int flags;
+};
+
+/**
+ * struct ubifs_lpt_lprops - LPT logical eraseblock properties.
+ * @free: amount of free space in bytes
+ * @dirty: amount of dirty space in bytes
+ */
+struct ubifs_lpt_lprops
+{
+	int free;
+	int dirty;
+};
+
+struct ubifs_nnode;
+
+/**
+ * struct ubifs_cnode - LEB Properties Tree common node.
+ * @parent: parent nnode
+ * @cnext: next cnode to commit
+ * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE)
+ * @iip: index in parent
+ * @level: level in the tree (zero for pnodes, greater than zero for nnodes)
+ * @num: node number
+ */
+struct ubifs_cnode
+{
+	struct ubifs_nnode *parent;
+	struct ubifs_cnode *cnext;
+	unsigned long flags;
+	int iip;
+	int level;
+	int num;
+};
+
+/**
+ * struct ubifs_pnode - LEB Properties Tree leaf node.
+ * @parent: parent nnode
+ * @cnext: next cnode to commit
+ * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE)
+ * @iip: index in parent
+ * @level: level in the tree (always zero for pnodes)
+ * @num: node number
+ * @lprops: LEB properties array
+ */
+struct ubifs_pnode
+{
+	struct ubifs_nnode *parent;
+	struct ubifs_cnode *cnext;
+	unsigned long flags;
+	int iip;
+	int level;
+	int num;
+	struct ubifs_lprops lprops[UBIFS_LPT_FANOUT];
+};
+
+/**
+ * struct ubifs_nbranch - LEB Properties Tree internal node branch.
+ * @lnum: LEB number of child
+ * @offs: offset of child
+ * @nnode: nnode child
+ * @pnode: pnode child
+ * @cnode: cnode child
+ */
+struct ubifs_nbranch
+{
+	int lnum;
+	int offs;
+	union
+	{
+		struct ubifs_nnode *nnode;
+		struct ubifs_pnode *pnode;
+		struct ubifs_cnode *cnode;
+	};
+};
+
+/**
+ * struct ubifs_nnode - LEB Properties Tree internal node.
+ * @parent: parent nnode
+ * @cnext: next cnode to commit
+ * @flags: flags (%DIRTY_LPT_NODE or %OBSOLETE_LPT_NODE)
+ * @iip: index in parent
+ * @level: level in the tree (always greater than zero for nnodes)
+ * @num: node number
+ * @nbranch: branches to child nodes
+ */
+struct ubifs_nnode
+{
+	struct ubifs_nnode *parent;
+	struct ubifs_cnode *cnext;
+	unsigned long flags;
+	int iip;
+	int level;
+	int num;
+	struct ubifs_nbranch nbranch[UBIFS_LPT_FANOUT];
+};
+
+/**
+ * struct ubifs_lp_stats - statistics of eraseblocks in the main area.
+ * @empty_lebs: number of empty LEBs
+ * @taken_empty_lebs: number of taken LEBs
+ * @idx_lebs: number of indexing LEBs
+ * @total_free: total free space in bytes
+ * @total_dirty: total dirty space in bytes
+ * @total_used: total used space in bytes (includes only data LEBs)
+ * @total_dead: total dead space in bytes (includes only data LEBs)
+ * @total_dark: total dark space in bytes (includes only data LEBs)
+ */
+struct ubifs_lp_stats {
+	int empty_lebs;
+	int taken_empty_lebs;
+	int idx_lebs;
+	long long total_free;
+	long long total_dirty;
+	long long total_used;
+	long long total_dead;
+	long long total_dark;
+};
+
+/**
+ * struct ubifs_zbranch - key/coordinate/length branch stored in znodes.
+ * @key: key
+ * @znode: znode address in memory
+ * @lnum: LEB number of the indexing node
+ * @offs: offset of the indexing node within @lnum
+ * @len: target node length
+ */
+struct ubifs_zbranch
+{
+	union ubifs_key key;
+	struct ubifs_znode *znode;
+	int lnum;
+	int offs;
+	int len;
+};
+
+/**
+ * struct ubifs_znode - in-memory representation of an indexing node.
+ * @parent: parent znode or NULL if it is the root
+ * @cnext: next znode to commit
+ * @flags: flags
+ * @time: last access time (seconds)
+ * @level: level of the entry in the TNC tree
+ * @child_cnt: count of child znodes
+ * @iip: index in parent's zbranch array
+ * @alt: lower bound of key range has altered i.e. child inserted at slot 0
+ * @zbranch: array of znode branches (@c->fanout elements)
+ */
+struct ubifs_znode
+{
+	struct ubifs_znode *parent;
+	struct ubifs_znode *cnext;
+	unsigned long flags;
+	unsigned long time;
+	int level;
+	int child_cnt;
+	int iip;
+	int alt;
+#ifdef CONFIG_UBIFS_FS_DEBUG
+	int lnum, offs, len;
+#endif
+	struct ubifs_zbranch zbranch[];
+};
+
+/**
+ * struct ubifs_info - UBIFS file-system description data structure
+ * (per-superblock).
+ *
+ * @highest_inum: highest used inode number
+ * @max_sqnum: current global sequence number
+ *
+ * @jhead_cnt: count of journal heads
+ * @max_bud_bytes: maximum number of bytes allowed in buds
+ *
+ * @zroot: zbranch which points to the root index node and znode
+ * @ihead_lnum: LEB number of index head
+ * @ihead_offs: offset of index head
+ *
+ * @log_lebs: number of logical eraseblocks in the log
+ * @lpt_lebs: number of LEBs used for lprops table
+ * @lpt_first: first LEB of the lprops table area
+ * @lpt_last: last LEB of the lprops table area
+ * @main_lebs: count of LEBs in the main area
+ * @main_first: first LEB of the main area
+ * @default_compr: default compression type
+ *
+ * @key_hash_type: type of the key hash
+ * @key_hash: direntry key hash function
+ * @key_fmt: key format
+ * @key_len: key length
+ * @fanout: fanout of the index tree (number of links per indexing node)
+ *
+ * @min_io_size: minimal input/output unit size
+ * @leb_size: logical eraseblock size in bytes
+ * @leb_cnt: count of logical eraseblocks
+ * @max_leb_cnt: maximum count of logical eraseblocks
+ *
+ * @old_idx_sz: size of index on flash
+ * @lst: lprops statistics
+ *
+ * @dead_wm: LEB dead space watermark
+ * @dark_wm: LEB dark space watermark
+ *
+ * @gc_lnum: LEB number used for garbage collection
+ * @space_bits: number of bits needed to record free or dirty space
+ * @lpt_lnum_bits: number of bits needed to record a LEB number in the LPT
+ * @lpt_offs_bits: number of bits needed to record an offset in the LPT
+ * @lpt_spc_bits: number of bits needed to space in the LPT
+ * @pcnt_bits: number of bits needed to record pnode or nnode number
+ * @lnum_bits: number of bits needed to record LEB number
+ * @nnode_sz: size of on-flash nnode
+ * @pnode_sz: size of on-flash pnode
+ * @ltab_sz: size of on-flash LPT lprops table
+ * @lsave_sz: size of on-flash LPT save table
+ * @pnode_cnt: number of pnodes
+ * @nnode_cnt: number of nnodes
+ * @lpt_hght: height of the LPT
+ *
+ * @lpt_lnum: LEB number of the root nnode of the LPT
+ * @lpt_offs: offset of the root nnode of the LPT
+ * @nhead_lnum: LEB number of LPT head
+ * @nhead_offs: offset of LPT head
+ * @big_lpt: flag that LPT is too big to write whole during commit
+ * @lpt_sz: LPT size
+ *
+ * @ltab_lnum: LEB number of LPT's own lprops table
+ * @ltab_offs: offset of LPT's own lprops table
+ * @lpt: lprops table
+ * @ltab: LPT's own lprops table
+ * @lsave_cnt: number of LEB numbers in LPT's save table
+ * @lsave_lnum: LEB number of LPT's save table
+ * @lsave_offs: offset of LPT's save table
+ * @lsave: LPT's save table
+ * @lscan_lnum: LEB number of last LPT scan
+ */
+struct ubifs_info
+{
+	ino_t highest_inum;
+	unsigned long long max_sqnum;
+
+	int jhead_cnt;
+	long long max_bud_bytes;
+
+	struct ubifs_zbranch zroot;
+	int ihead_lnum;
+	int ihead_offs;
+
+	int log_lebs;
+	int lpt_lebs;
+	int lpt_first;
+	int lpt_last;
+	int orph_lebs;
+	int main_lebs;
+	int main_first;
+	int default_compr;
+
+	uint8_t key_hash_type;
+	uint32_t (*key_hash)(const char *str, int len);
+	int key_fmt;
+	int key_len;
+	int fanout;
+
+	int min_io_size;
+	int leb_size;
+	int leb_cnt;
+	int max_leb_cnt;
+
+	unsigned long long old_idx_sz;
+	struct ubifs_lp_stats lst;
+
+	int dead_wm;
+	int dark_wm;
+
+	int gc_lnum;
+
+	int space_bits;
+	int lpt_lnum_bits;
+	int lpt_offs_bits;
+	int lpt_spc_bits;
+	int pcnt_bits;
+	int lnum_bits;
+	int nnode_sz;
+	int pnode_sz;
+	int ltab_sz;
+	int lsave_sz;
+	int pnode_cnt;
+	int nnode_cnt;
+	int lpt_hght;
+
+	int lpt_lnum;
+	int lpt_offs;
+	int nhead_lnum;
+	int nhead_offs;
+	int big_lpt;
+	long long lpt_sz;
+
+	int ltab_lnum;
+	int ltab_offs;
+	struct ubifs_lprops *lpt;
+	struct ubifs_lpt_lprops *ltab;
+	int lsave_cnt;
+	int lsave_lnum;
+	int lsave_offs;
+	int *lsave;
+	int lscan_lnum;
+
+};
+
+/**
+ * ubifs_idx_node_sz - return index node size.
+ * @c: the UBIFS file-system description object
+ * @child_cnt: number of children of this index node
+ */
+static inline int ubifs_idx_node_sz(const struct ubifs_info *c, int child_cnt)
+{
+	return UBIFS_IDX_NODE_SZ + (UBIFS_BRANCH_SZ + c->key_len) * child_cnt;
+}
+
+/**
+ * ubifs_idx_branch - return pointer to an index branch.
+ * @c: the UBIFS file-system description object
+ * @idx: index node
+ * @bnum: branch number
+ */
+static inline
+struct ubifs_branch *ubifs_idx_branch(const struct ubifs_info *c,
+				      const struct ubifs_idx_node *idx,
+				      int bnum)
+{
+	return (struct ubifs_branch *)((void *)idx->branches +
+				       (UBIFS_BRANCH_SZ + c->key_len) * bnum);
+}
+
+/**
+ * ubifs_idx_key - return pointer to an index key.
+ * @c: the UBIFS file-system description object
+ * @idx: index node
+ */
+static inline void *ubifs_idx_key(const struct ubifs_info *c,
+				  const struct ubifs_idx_node *idx)
+{
+	return (void *)((struct ubifs_branch *)idx->branches)->key;
+}
+
+#endif /* __UBIFS_H__ */