vaseboot/VasEBoot-core/fs/hfsplus.c

/* hfsplus.c - HFS+ Filesystem.  */
/*
 *  VAS_EBOOT  --  GRand Unified Bootloader
 *  Copyright (C) 2005,2006,2007,2008,2009  Free Software Foundation, Inc.
 *
 *  VAS_EBOOT 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 3 of the License, or
 *  (at your option) any later version.
 *
 *  VAS_EBOOT 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 VAS_EBOOT.  If not, see <http://www.gnu.org/licenses/>.
 */

/* HFS+ is documented at http://developer.apple.com/technotes/tn/tn1150.html */

#define VasEBoot_fshelp_node VasEBoot_hfsplus_file
#include <VasEBoot/err.h>
#include <VasEBoot/file.h>
#include <VasEBoot/mm.h>
#include <VasEBoot/misc.h>
#include <VasEBoot/disk.h>
#include <VasEBoot/dl.h>
#include <VasEBoot/types.h>
#include <VasEBoot/fshelp.h>
#include <VasEBoot/hfs.h>
#include <VasEBoot/charset.h>
#include <VasEBoot/hfsplus.h>
#include <VasEBoot/safemath.h>

VAS_EBOOT_MOD_LICENSE ("GPLv3+");

/* The type of node.  */
enum VasEBoot_hfsplus_btnode_type
  {
    VAS_EBOOT_HFSPLUS_BTNODE_TYPE_LEAF = -1,
    VAS_EBOOT_HFSPLUS_BTNODE_TYPE_INDEX = 0,
    VAS_EBOOT_HFSPLUS_BTNODE_TYPE_HEADER = 1,
    VAS_EBOOT_HFSPLUS_BTNODE_TYPE_MAP = 2,
  };

/* The header of a HFS+ B+ Tree.  */
struct VasEBoot_hfsplus_btheader
{
  VasEBoot_uint16_t depth;
  VasEBoot_uint32_t root;
  VasEBoot_uint32_t leaf_records;
  VasEBoot_uint32_t first_leaf_node;
  VasEBoot_uint32_t last_leaf_node;
  VasEBoot_uint16_t nodesize;
  VasEBoot_uint16_t keysize;
  VasEBoot_uint32_t total_nodes;
  VasEBoot_uint32_t free_nodes;
  VasEBoot_uint16_t reserved1;
  VasEBoot_uint32_t clump_size;  /* ignored */
  VasEBoot_uint8_t btree_type;
  VasEBoot_uint8_t key_compare;
  VasEBoot_uint32_t attributes;
} VAS_EBOOT_PACKED;

struct VasEBoot_hfsplus_catfile
{
  VasEBoot_uint16_t type;
  VasEBoot_uint16_t flags;
  VasEBoot_uint32_t parentid; /* Thread only.  */
  VasEBoot_uint32_t fileid;
  VasEBoot_uint8_t unused1[4];
  VasEBoot_uint32_t mtime;
  VasEBoot_uint8_t unused2[22];
  VasEBoot_uint16_t mode;
  VasEBoot_uint8_t unused3[44];
  struct VasEBoot_hfsplus_forkdata data;
  struct VasEBoot_hfsplus_forkdata resource;
} VAS_EBOOT_PACKED;

/* Filetype information as used in inodes.  */
#define VAS_EBOOT_HFSPLUS_FILEMODE_MASK	0170000
#define VAS_EBOOT_HFSPLUS_FILEMODE_REG	0100000
#define VAS_EBOOT_HFSPLUS_FILEMODE_DIRECTORY	0040000
#define VAS_EBOOT_HFSPLUS_FILEMODE_SYMLINK	0120000

#define HFSPLUS_BTNODE_MINSZ	(1 << 9)
#define HFSPLUS_BTNODE_MAXSZ	(1 << 15)

#define HFSPLUS_CATKEY_MIN_LEN	6
#define HFSPLUS_CATKEY_MAX_LEN	516

/* Some pre-defined file IDs.  */
enum
  {
    VAS_EBOOT_HFSPLUS_FILEID_ROOTDIR = 2,
    VAS_EBOOT_HFSPLUS_FILEID_OVERFLOW = 3,
    VAS_EBOOT_HFSPLUS_FILEID_CATALOG	= 4,
    VAS_EBOOT_HFSPLUS_FILEID_ATTR	= 8
  };

enum VasEBoot_hfsplus_filetype
  {
    VAS_EBOOT_HFSPLUS_FILETYPE_DIR = 1,
    VAS_EBOOT_HFSPLUS_FILETYPE_REG = 2,
    VAS_EBOOT_HFSPLUS_FILETYPE_DIR_THREAD = 3,
    VAS_EBOOT_HFSPLUS_FILETYPE_REG_THREAD = 4
  };

#define VAS_EBOOT_HFSPLUSX_BINARYCOMPARE	0xBC
#define VAS_EBOOT_HFSPLUSX_CASEFOLDING	0xCF

static VasEBoot_dl_t my_mod;



VasEBoot_err_t (*VasEBoot_hfsplus_open_compressed) (struct VasEBoot_fshelp_node *node);
VasEBoot_ssize_t (*VasEBoot_hfsplus_read_compressed) (struct VasEBoot_hfsplus_file *node,
					      VasEBoot_off_t pos,
					      VasEBoot_size_t len,
					      char *buf);

/* Find the extent that points to FILEBLOCK.  If it is not in one of
   the 8 extents described by EXTENT, return -1.  In that case set
   FILEBLOCK to the next block.  */
static VasEBoot_disk_addr_t
VasEBoot_hfsplus_find_block (struct VasEBoot_hfsplus_extent *extent,
			 VasEBoot_disk_addr_t *fileblock)
{
  int i;
  VasEBoot_disk_addr_t blksleft = *fileblock;

  /* First lookup the file in the given extents.  */
  for (i = 0; i < 8; i++)
    {
      if (blksleft < VasEBoot_be_to_cpu32 (extent[i].count))
	return VasEBoot_be_to_cpu32 (extent[i].start) + blksleft;
      blksleft -= VasEBoot_be_to_cpu32 (extent[i].count);
    }

  *fileblock = blksleft;
  return 0xffffffffffffffffULL;
}

static int VasEBoot_hfsplus_cmp_extkey (struct VasEBoot_hfsplus_key *keya,
				    struct VasEBoot_hfsplus_key_internal *keyb);

/* Search for the block FILEBLOCK inside the file NODE.  Return the
   blocknumber of this block on disk.  */
static VasEBoot_disk_addr_t
VasEBoot_hfsplus_read_block (VasEBoot_fshelp_node_t node, VasEBoot_disk_addr_t fileblock)
{
  struct VasEBoot_hfsplus_btnode *nnode = 0;
  VasEBoot_disk_addr_t blksleft = fileblock;
  struct VasEBoot_hfsplus_extent *extents = node->compressed
    ? &node->resource_extents[0] : &node->extents[0];

  while (1)
    {
      struct VasEBoot_hfsplus_extkey *key;
      struct VasEBoot_hfsplus_key_internal extoverflow;
      VasEBoot_disk_addr_t blk;
      VasEBoot_off_t ptr;

      /* Try to find this block in the current set of extents.  */
      blk = VasEBoot_hfsplus_find_block (extents, &blksleft);

      /* The previous iteration of this loop allocated memory.  The
	 code above used this memory, it can be freed now.  */
      VasEBoot_free (nnode);
      nnode = 0;

      if (blk != 0xffffffffffffffffULL)
	return blk;

      /* For the extent overflow file, extra extents can't be found in
	 the extent overflow file.  If this happens, you found a
	 bug...  */
      if (node->fileid == VAS_EBOOT_HFSPLUS_FILEID_OVERFLOW)
	{
	  VasEBoot_error (VAS_EBOOT_ERR_READ_ERROR,
		      "extra extents found in an extend overflow file");
	  break;
	}

      /*
       * If the extent overflow tree isn't ready yet, we can't look
       * in it. This can happen where the catalog file is corrupted.
       */
      if (!node->data->extoverflow_tree_ready)
	{
	  VasEBoot_error (VAS_EBOOT_ERR_BAD_FS,
		      "attempted to read extent overflow tree before loading");
	  break;
	}

      /* Set up the key to look for in the extent overflow file.  */
      extoverflow.extkey.fileid = node->fileid;
      extoverflow.extkey.type = 0;
      extoverflow.extkey.start = fileblock - blksleft;
      extoverflow.extkey.type = node->compressed ? 0xff : 0;
      if (VasEBoot_hfsplus_btree_search (&node->data->extoverflow_tree,
				     &extoverflow,
				     VasEBoot_hfsplus_cmp_extkey, &nnode, &ptr)
	  || !nnode)
	{
	  VasEBoot_error (VAS_EBOOT_ERR_READ_ERROR,
		      "no block found for the file id 0x%x and the block"
		      " offset 0x%" PRIuVAS_EBOOT_UINT64_T,
		      node->fileid, fileblock);
	  break;
	}

      /* The extent overflow file has 8 extents right after the key.  */
      key = (struct VasEBoot_hfsplus_extkey *)
	VasEBoot_hfsplus_btree_recptr (&node->data->extoverflow_tree, nnode, ptr);
      extents = (struct VasEBoot_hfsplus_extent *) (key + 1);

      /* The block wasn't found.  Perhaps the next iteration will find
	 it.  The last block we found is stored in BLKSLEFT now.  */
    }

  VasEBoot_free (nnode);

  /* Too bad, you lose.  */
  return -1;
}


/* Read LEN bytes from the file described by DATA starting with byte
   POS.  Return the amount of read bytes in READ.  */
VasEBoot_ssize_t
VasEBoot_hfsplus_read_file (VasEBoot_fshelp_node_t node,
			VasEBoot_disk_read_hook_t read_hook, void *read_hook_data,
			VasEBoot_off_t pos, VasEBoot_size_t len, char *buf)
{
  return VasEBoot_fshelp_read_file (node->data->disk, node,
				read_hook, read_hook_data,
				pos, len, buf, VasEBoot_hfsplus_read_block,
				node->size,
				node->data->log2blksize - VAS_EBOOT_DISK_SECTOR_BITS,
				node->data->embedded_offset);
}

static struct VasEBoot_hfsplus_data *
VasEBoot_hfsplus_mount (VasEBoot_disk_t disk)
{
  struct VasEBoot_hfsplus_data *data;
  struct VasEBoot_hfsplus_btheader header;
  struct VasEBoot_hfsplus_btnode node;
  VasEBoot_uint16_t magic;
  union {
    struct VasEBoot_hfs_sblock hfs;
    struct VasEBoot_hfsplus_volheader hfsplus;
  } volheader;

  data = VasEBoot_malloc (sizeof (*data));
  if (!data)
    return 0;

  data->disk = disk;
  data->extoverflow_tree_ready = 0;

  /* Read the bootblock.  */
  VasEBoot_disk_read (disk, VAS_EBOOT_HFSPLUS_SBLOCK, 0, sizeof (volheader),
		  &volheader);
  if (VasEBoot_errno)
    goto fail;

  data->embedded_offset = 0;
  if (VasEBoot_be_to_cpu16 (volheader.hfs.magic) == VAS_EBOOT_HFS_MAGIC)
    {
      VasEBoot_disk_addr_t extent_start;
      VasEBoot_disk_addr_t ablk_size;
      VasEBoot_disk_addr_t ablk_start;

      /* See if there's an embedded HFS+ filesystem.  */
      if (VasEBoot_be_to_cpu16 (volheader.hfs.embed_sig) != VAS_EBOOT_HFSPLUS_MAGIC)
	{
	  VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "not a HFS+ filesystem");
	  goto fail;
	}

      /* Calculate the offset needed to translate HFS+ sector numbers.  */
      extent_start = VasEBoot_be_to_cpu16 (volheader.hfs.embed_extent.first_block);
      ablk_size = VasEBoot_be_to_cpu32 (volheader.hfs.blksz);
      ablk_start = VasEBoot_be_to_cpu16 (volheader.hfs.first_block);
      data->embedded_offset = (ablk_start
			       + extent_start
			       * (ablk_size >> VAS_EBOOT_DISK_SECTOR_BITS));

      VasEBoot_disk_read (disk, data->embedded_offset + VAS_EBOOT_HFSPLUS_SBLOCK, 0,
		      sizeof (volheader), &volheader);
      if (VasEBoot_errno)
	goto fail;
    }

  /* Make sure this is an HFS+ filesystem.  XXX: Do we really support
     HFX?  */
  magic = VasEBoot_be_to_cpu16 (volheader.hfsplus.magic);
  if (((magic != VAS_EBOOT_HFSPLUS_MAGIC) && (magic != VAS_EBOOT_HFSPLUSX_MAGIC))
      || volheader.hfsplus.blksize == 0
      || ((volheader.hfsplus.blksize & (volheader.hfsplus.blksize - 1)) != 0)
      || VasEBoot_be_to_cpu32 (volheader.hfsplus.blksize) < VAS_EBOOT_DISK_SECTOR_SIZE)
    {
      VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "not a HFS+ filesystem");
      goto fail;
    }

  VasEBoot_memcpy (&data->volheader, &volheader.hfsplus,
	       sizeof (volheader.hfsplus));

  for (data->log2blksize = 0;
       (1U << data->log2blksize) < VasEBoot_be_to_cpu32 (data->volheader.blksize);
       data->log2blksize++);

  /* Make a new node for the catalog tree.  */
  data->catalog_tree.file.data = data;
  data->catalog_tree.file.fileid = VAS_EBOOT_HFSPLUS_FILEID_CATALOG;
  data->catalog_tree.file.compressed = 0;
  VasEBoot_memcpy (&data->catalog_tree.file.extents,
	       data->volheader.catalog_file.extents,
	       sizeof data->volheader.catalog_file.extents);
  data->catalog_tree.file.size =
    VasEBoot_be_to_cpu64 (data->volheader.catalog_file.size);

  data->attr_tree.file.data = data;
  data->attr_tree.file.fileid = VAS_EBOOT_HFSPLUS_FILEID_ATTR;
  VasEBoot_memcpy (&data->attr_tree.file.extents,
	       data->volheader.attr_file.extents,
	       sizeof data->volheader.attr_file.extents);

  data->attr_tree.file.size =
    VasEBoot_be_to_cpu64 (data->volheader.attr_file.size);
  data->attr_tree.file.compressed = 0;

  /* Make a new node for the extent overflow file.  */
  data->extoverflow_tree.file.data = data;
  data->extoverflow_tree.file.fileid = VAS_EBOOT_HFSPLUS_FILEID_OVERFLOW;
  data->extoverflow_tree.file.compressed = 0;
  VasEBoot_memcpy (&data->extoverflow_tree.file.extents,
	       data->volheader.extents_file.extents,
	       sizeof data->volheader.catalog_file.extents);

  data->extoverflow_tree.file.size =
    VasEBoot_be_to_cpu64 (data->volheader.extents_file.size);

  /* Read the essential information about the trees.  */
  if (VasEBoot_hfsplus_read_file (&data->catalog_tree.file, 0, 0,
			      sizeof (struct VasEBoot_hfsplus_btnode),
			      sizeof (header), (char *) &header) <= 0)
    goto fail;

  data->catalog_tree.root = VasEBoot_be_to_cpu32 (header.root);
  data->catalog_tree.nodesize = VasEBoot_be_to_cpu16 (header.nodesize);
  data->case_sensitive = ((magic == VAS_EBOOT_HFSPLUSX_MAGIC) &&
			  (header.key_compare == VAS_EBOOT_HFSPLUSX_BINARYCOMPARE));

  if (data->catalog_tree.nodesize < 2)
    {
      VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "invalid catalog node size");
      goto fail;
    }

  if (VasEBoot_hfsplus_read_file (&data->extoverflow_tree.file, 0, 0,
			      sizeof (struct VasEBoot_hfsplus_btnode),
			      sizeof (header), (char *) &header) <= 0)
    goto fail;

  data->extoverflow_tree.root = VasEBoot_be_to_cpu32 (header.root);

  if (VasEBoot_hfsplus_read_file (&data->extoverflow_tree.file, 0, 0, 0,
			      sizeof (node), (char *) &node) <= 0)
    goto fail;

  data->extoverflow_tree.root = VasEBoot_be_to_cpu32 (header.root);
  data->extoverflow_tree.nodesize = VasEBoot_be_to_cpu16 (header.nodesize);

  if (data->extoverflow_tree.nodesize < 2)
    {
      VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "invalid extents overflow node size");
      goto fail;
    }

  data->extoverflow_tree_ready = 1;

  if (VasEBoot_hfsplus_read_file (&data->attr_tree.file, 0, 0,
			      sizeof (struct VasEBoot_hfsplus_btnode),
			      sizeof (header), (char *) &header) <= 0)
    {
      VasEBoot_errno = 0;
      data->attr_tree.root = 0;
      data->attr_tree.nodesize = 0;
    }
  else
    {
      data->attr_tree.root = VasEBoot_be_to_cpu32 (header.root);
      data->attr_tree.nodesize = VasEBoot_be_to_cpu16 (header.nodesize);
    }

  data->dirroot.data = data;
  data->dirroot.fileid = VAS_EBOOT_HFSPLUS_FILEID_ROOTDIR;

  return data;

 fail:

  if (VasEBoot_errno == VAS_EBOOT_ERR_OUT_OF_RANGE || VasEBoot_errno == VAS_EBOOT_ERR_NONE)
    VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "not a HFS+ filesystem");

  VasEBoot_free (data);
  return 0;
}

/* Compare the on disk catalog key KEYA with the catalog key we are
   looking for (KEYB).  */
static int
VasEBoot_hfsplus_cmp_catkey (struct VasEBoot_hfsplus_key *keya,
			 struct VasEBoot_hfsplus_key_internal *keyb)
{
  struct VasEBoot_hfsplus_catkey *catkey_a = &keya->catkey;
  struct VasEBoot_hfsplus_catkey_internal *catkey_b = &keyb->catkey;
  int diff;
  VasEBoot_size_t len;

  /* Safe unsigned comparison */
  VasEBoot_uint32_t aparent = VasEBoot_be_to_cpu32 (catkey_a->parent);
  if (aparent > catkey_b->parent)
    return 1;
  if (aparent < catkey_b->parent)
    return -1;

  len = VasEBoot_be_to_cpu16 (catkey_a->namelen);
  if (len > catkey_b->namelen)
    len = catkey_b->namelen;
  /* Since it's big-endian memcmp gives the same result as manually comparing
     uint16_t but may be faster.  */
  diff = VasEBoot_memcmp (catkey_a->name, catkey_b->name,
		      len * sizeof (catkey_a->name[0]));
  if (diff == 0)
    diff = VasEBoot_be_to_cpu16 (catkey_a->namelen) - catkey_b->namelen;

  return diff;
}

/* Compare the on disk catalog key KEYA with the catalog key we are
   looking for (KEYB).  */
static int
VasEBoot_hfsplus_cmp_catkey_id (struct VasEBoot_hfsplus_key *keya,
			 struct VasEBoot_hfsplus_key_internal *keyb)
{
  struct VasEBoot_hfsplus_catkey *catkey_a = &keya->catkey;
  struct VasEBoot_hfsplus_catkey_internal *catkey_b = &keyb->catkey;

  /* Safe unsigned comparison */
  VasEBoot_uint32_t aparent = VasEBoot_be_to_cpu32 (catkey_a->parent);
  if (aparent > catkey_b->parent)
    return 1;
  if (aparent < catkey_b->parent)
    return -1;

  return 0;
}

/* Compare the on disk extent overflow key KEYA with the extent
   overflow key we are looking for (KEYB).  */
static int
VasEBoot_hfsplus_cmp_extkey (struct VasEBoot_hfsplus_key *keya,
			 struct VasEBoot_hfsplus_key_internal *keyb)
{
  struct VasEBoot_hfsplus_extkey *extkey_a = &keya->extkey;
  struct VasEBoot_hfsplus_extkey_internal *extkey_b = &keyb->extkey;
  VasEBoot_uint32_t akey;

  /* Safe unsigned comparison */
  akey = VasEBoot_be_to_cpu32 (extkey_a->fileid);
  if (akey > extkey_b->fileid)
    return 1;
  if (akey < extkey_b->fileid)
    return -1;

  if (extkey_a->type > extkey_b->type)
    return 1;
  if (extkey_a->type < extkey_b->type)
    return -1;

  if (extkey_a->type > extkey_b->type)
    return +1;

  if (extkey_a->type < extkey_b->type)
    return -1;

  akey = VasEBoot_be_to_cpu32 (extkey_a->start);
  if (akey > extkey_b->start)
    return 1;
  if (akey < extkey_b->start)
    return -1;
  return 0;
}

static char *
VasEBoot_hfsplus_read_symlink (VasEBoot_fshelp_node_t node)
{
  char *symlink;
  VasEBoot_ssize_t numread;
  VasEBoot_size_t sz = node->size;

  if (VasEBoot_add (sz, 1, &sz))
    return NULL;

  symlink = VasEBoot_malloc (sz);
  if (!symlink)
    return 0;

  numread = VasEBoot_hfsplus_read_file (node, 0, 0, 0, node->size, symlink);
  if (numread != (VasEBoot_ssize_t) node->size)
    {
      VasEBoot_free (symlink);
      return 0;
    }
  symlink[node->size] = '\0';

  return symlink;
}

static int
VasEBoot_hfsplus_btree_iterate_node (struct VasEBoot_hfsplus_btree *btree,
				 struct VasEBoot_hfsplus_btnode *first_node,
				 VasEBoot_disk_addr_t first_rec,
				 int (*hook) (void *record, void *hook_arg),
				 void *hook_arg)
{
  VasEBoot_disk_addr_t rec;
  VasEBoot_uint64_t saved_node = -1;
  VasEBoot_uint64_t node_count = 0;

  for (;;)
    {
      char *cnode = (char *) first_node;

      /* Iterate over all records in this node.  */
      for (rec = first_rec; rec < VasEBoot_be_to_cpu16 (first_node->count); rec++)
	{
	  if (hook (VasEBoot_hfsplus_btree_recptr (btree, first_node, rec), hook_arg))
	    return 1;
	}

      if (! first_node->next)
	break;

      if (node_count && first_node->next == saved_node)
	{
	  VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "HFS+ btree loop");
	  return 0;
	}
      if (!(node_count & (node_count - 1)))
	saved_node = first_node->next;
      node_count++;

      if (VasEBoot_hfsplus_read_file (&btree->file, 0, 0,
				  (((VasEBoot_disk_addr_t)
				    VasEBoot_be_to_cpu32 (first_node->next))
				   * btree->nodesize),
				  btree->nodesize, cnode) <= 0)
	return 1;

      /* Don't skip any record in the next iteration.  */
      first_rec = 0;
    }

  return 0;
}

/* Lookup the node described by KEY in the B+ Tree BTREE.  Compare
   keys using the function COMPARE_KEYS.  When a match is found,
   return the node in MATCHNODE and a pointer to the data in this node
   in KEYOFFSET.  MATCHNODE should be freed by the caller.  */
VasEBoot_err_t
VasEBoot_hfsplus_btree_search (struct VasEBoot_hfsplus_btree *btree,
			   struct VasEBoot_hfsplus_key_internal *key,
			   int (*compare_keys) (struct VasEBoot_hfsplus_key *keya,
						struct VasEBoot_hfsplus_key_internal *keyb),
			   struct VasEBoot_hfsplus_btnode **matchnode,
			   VasEBoot_off_t *keyoffset)
{
  VasEBoot_uint64_t currnode;
  char *node;
  struct VasEBoot_hfsplus_btnode *nodedesc;
  VasEBoot_disk_addr_t rec;
  VasEBoot_uint64_t save_node;
  VasEBoot_uint64_t node_count = 0;

  if (!btree->nodesize)
    {
      *matchnode = 0;
      return 0;
    }

  if (btree->nodesize < HFSPLUS_BTNODE_MINSZ ||
      btree->nodesize > HFSPLUS_BTNODE_MAXSZ)
    return VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "invalid HFS+ btree node size");

  node = VasEBoot_malloc (btree->nodesize);
  if (! node)
    return VasEBoot_errno;

  currnode = btree->root;
  save_node = currnode - 1;
  while (1)
    {
      int match = 0;

      if (save_node == currnode)
	{
	  VasEBoot_free (node);
	  return VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "HFS+ btree loop");
	}
      if (!(node_count & (node_count - 1)))
	save_node = currnode;
      node_count++;

      /* Read a node.  */
      if (VasEBoot_hfsplus_read_file (&btree->file, 0, 0,
				  (VasEBoot_disk_addr_t) currnode
				  * (VasEBoot_disk_addr_t) btree->nodesize,
				  btree->nodesize, (char *) node) <= 0)
	{
	  VasEBoot_free (node);
	  return VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "couldn't read i-node");
	}

      nodedesc = (struct VasEBoot_hfsplus_btnode *) node;

      /* Find the record in this tree.  */
      for (rec = 0; rec < VasEBoot_be_to_cpu16 (nodedesc->count); rec++)
	{
	  struct VasEBoot_hfsplus_key *currkey;
	  currkey = VasEBoot_hfsplus_btree_recptr (btree, nodedesc, rec);

	  /* The action that has to be taken depend on the type of
	     record.  */
	  if (nodedesc->type == VAS_EBOOT_HFSPLUS_BTNODE_TYPE_LEAF
	      && compare_keys (currkey, key) == 0)
	    {
	      /* An exact match was found!  */

	      *matchnode = nodedesc;
	      *keyoffset = rec;

	      return 0;
	    }
	  else if (nodedesc->type == VAS_EBOOT_HFSPLUS_BTNODE_TYPE_INDEX)
	    {
	      void *pointer;

	      /* The place where the key could have been found didn't
		 contain the key.  This means that the previous match
		 is the one that should be followed.  */
	      if (compare_keys (currkey, key) > 0)
		break;

	      /* Mark the last key which is lower or equal to the key
		 that we are looking for.  The last match that is
		 found will be used to locate the child which can
		 contain the record.  */
	      pointer = ((char *) currkey
			 + VasEBoot_be_to_cpu16 (currkey->keylen)
			 + 2);

	      if ((char *) pointer > node + btree->nodesize - 2)
	        {
	          VasEBoot_free (node);
	          return VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "HFS+ key beyond end of node");
	        }

	      currnode = VasEBoot_be_to_cpu32 (VasEBoot_get_unaligned32 (pointer));
	      match = 1;
	    }
	}

      /* No match is found, no record with this key exists in the
	 tree.  */
      if (! match)
	{
	  *matchnode = 0;
	  VasEBoot_free (node);
	  return 0;
	}
    }
}

struct list_nodes_ctx
{
  int ret;
  VasEBoot_fshelp_node_t dir;
  VasEBoot_fshelp_iterate_dir_hook_t hook;
  void *hook_data;
};

static int
list_nodes (void *record, void *hook_arg)
{
  struct VasEBoot_hfsplus_catkey *catkey;
  char *filename;
  int i;
  struct VasEBoot_fshelp_node *node;
  VasEBoot_uint16_t *keyname;
  struct VasEBoot_hfsplus_catfile *fileinfo;
  enum VasEBoot_fshelp_filetype type = VAS_EBOOT_FSHELP_UNKNOWN;
  struct list_nodes_ctx *ctx = hook_arg;

  catkey = (struct VasEBoot_hfsplus_catkey *) record;

  if (VasEBoot_be_to_cpu16 (catkey->keylen) < HFSPLUS_CATKEY_MIN_LEN ||
      VasEBoot_be_to_cpu16 (catkey->keylen) > HFSPLUS_CATKEY_MAX_LEN)
    {
      VasEBoot_error (VAS_EBOOT_ERR_BAD_FS, "catalog key length is out of range");
      return 1;
    }

  fileinfo =
    (struct VasEBoot_hfsplus_catfile *) ((char *) record
				     + VasEBoot_be_to_cpu16 (catkey->keylen)
				     + 2 + (VasEBoot_be_to_cpu16(catkey->keylen)
					    % 2));

  /* Stop iterating when the last directory entry is found.  */
  if (VasEBoot_be_to_cpu32 (catkey->parent) != ctx->dir->fileid)
    return 1;

  /* Determine the type of the node that is found.  */
  switch (fileinfo->type)
    {
    case VasEBoot_cpu_to_be16_compile_time (VAS_EBOOT_HFSPLUS_FILETYPE_REG):
      {
	int mode = (VasEBoot_be_to_cpu16 (fileinfo->mode)
		    & VAS_EBOOT_HFSPLUS_FILEMODE_MASK);

	if (mode == 0) /* Created by pre-Mac OS X. */
          type = VAS_EBOOT_FSHELP_REG;
        else if (mode == VAS_EBOOT_HFSPLUS_FILEMODE_REG)
	  type = VAS_EBOOT_FSHELP_REG;
	else if (mode == VAS_EBOOT_HFSPLUS_FILEMODE_SYMLINK)
	  type = VAS_EBOOT_FSHELP_SYMLINK;
	else
	  type = VAS_EBOOT_FSHELP_UNKNOWN;
	break;
      }
    case VasEBoot_cpu_to_be16_compile_time (VAS_EBOOT_HFSPLUS_FILETYPE_DIR):
      type = VAS_EBOOT_FSHELP_DIR;
      break;
    case VasEBoot_cpu_to_be16_compile_time (VAS_EBOOT_HFSPLUS_FILETYPE_DIR_THREAD):
      if (ctx->dir->fileid == 2)
	return 0;
      node = VasEBoot_malloc (sizeof (*node));
      if (!node)
	return 1;
      node->data = ctx->dir->data;
      node->mtime = 0;
      node->size = 0;
      node->fileid = VasEBoot_be_to_cpu32 (fileinfo->parentid);

      ctx->ret = ctx->hook ("..", VAS_EBOOT_FSHELP_DIR, node, ctx->hook_data);
      return ctx->ret;
    }

  if (type == VAS_EBOOT_FSHELP_UNKNOWN)
    return 0;

  filename = VasEBoot_calloc (VasEBoot_be_to_cpu16 (catkey->namelen),
			  VAS_EBOOT_MAX_UTF8_PER_UTF16 + 1);
  if (! filename)
    return 0;

  keyname = VasEBoot_calloc (VasEBoot_be_to_cpu16 (catkey->namelen), sizeof (*keyname));
  if (!keyname)
    {
      VasEBoot_free (filename);
      return 0;
    }

  /* Make sure the byte order of the UTF16 string is correct.  */
  for (i = 0; i < VasEBoot_be_to_cpu16 (catkey->namelen); i++)
    {
      keyname[i] = VasEBoot_be_to_cpu16 (catkey->name[i]);

      if (keyname[i] == '/')
	keyname[i] = ':';

      /* If the name is obviously invalid, skip this node.  */
      if (keyname[i] == 0)
	{
	  VasEBoot_free (keyname);
	  VasEBoot_free (filename);
	  return 0;
	}
    }

  *VasEBoot_utf16_to_utf8 ((VasEBoot_uint8_t *) filename, keyname,
		       VasEBoot_be_to_cpu16 (catkey->namelen)) = '\0';

  VasEBoot_free (keyname);

  /* hfs+ is case insensitive.  */
  if (! ctx->dir->data->case_sensitive)
    type |= VAS_EBOOT_FSHELP_CASE_INSENSITIVE;

  /* A valid node is found; setup the node and call the
     callback function.  */
  node = VasEBoot_malloc (sizeof (*node));
  if (!node)
    {
      VasEBoot_free (filename);
      return 1;
    }
  node->data = ctx->dir->data;
  node->compressed = 0;
  node->cbuf = 0;
  node->compress_index = 0;

  VasEBoot_memcpy (node->extents, fileinfo->data.extents,
	       sizeof (node->extents));
  VasEBoot_memcpy (node->resource_extents, fileinfo->resource.extents,
	       sizeof (node->resource_extents));
  node->mtime = VasEBoot_be_to_cpu32 (fileinfo->mtime) - 2082844800;
  node->size = VasEBoot_be_to_cpu64 (fileinfo->data.size);
  node->resource_size = VasEBoot_be_to_cpu64 (fileinfo->resource.size);
  node->fileid = VasEBoot_be_to_cpu32 (fileinfo->fileid);

  ctx->ret = ctx->hook (filename, type, node, ctx->hook_data);

  VasEBoot_free (filename);

  return ctx->ret;
}

static int
VasEBoot_hfsplus_iterate_dir (VasEBoot_fshelp_node_t dir,
			  VasEBoot_fshelp_iterate_dir_hook_t hook, void *hook_data)
{
  struct list_nodes_ctx ctx =
  {
    .ret = 0,
    .dir = dir,
    .hook = hook,
    .hook_data = hook_data
  };

  struct VasEBoot_hfsplus_key_internal intern;
  struct VasEBoot_hfsplus_btnode *node = NULL;
  VasEBoot_disk_addr_t ptr = 0;

  {
    struct VasEBoot_fshelp_node *fsnode;
    fsnode = VasEBoot_malloc (sizeof (*fsnode));
    if (!fsnode)
      return 1;
    *fsnode = *dir;
    if (hook (".", VAS_EBOOT_FSHELP_DIR, fsnode, hook_data))
      return 1;
  }

  /* Create a key that points to the first entry in the directory.  */
  intern.catkey.parent = dir->fileid;
  intern.catkey.name = 0;
  intern.catkey.namelen = 0;

  /* First lookup the first entry.  */
  if (VasEBoot_hfsplus_btree_search (&dir->data->catalog_tree, &intern,
				 VasEBoot_hfsplus_cmp_catkey, &node, &ptr)
      || !node)
    return 0;

  /* Iterate over all entries in this directory.  */
  VasEBoot_hfsplus_btree_iterate_node (&dir->data->catalog_tree, node, ptr,
				   list_nodes, &ctx);

  VasEBoot_free (node);

  return ctx.ret;
}

/* Open a file named NAME and initialize FILE.  */
static VasEBoot_err_t
VasEBoot_hfsplus_open (struct VasEBoot_file *file, const char *name)
{
  struct VasEBoot_hfsplus_data *data;
  struct VasEBoot_fshelp_node *fdiro = 0;

  VasEBoot_dl_ref (my_mod);

  data = VasEBoot_hfsplus_mount (file->device->disk);
  if (!data)
    goto fail;

  VasEBoot_fshelp_find_file (name, &data->dirroot, &fdiro,
			 VasEBoot_hfsplus_iterate_dir,
			 VasEBoot_hfsplus_read_symlink, VAS_EBOOT_FSHELP_REG);
  if (VasEBoot_errno)
    goto fail;

  if (VasEBoot_hfsplus_open_compressed)
    {
      VasEBoot_err_t err;
      err = VasEBoot_hfsplus_open_compressed (fdiro);
      if (err)
	goto fail;
    }

  file->size = fdiro->size;
  data->opened_file = *fdiro;
  VasEBoot_free (fdiro);

  file->data = data;
  file->offset = 0;

  return 0;

 fail:
  if (data && fdiro != &data->dirroot)
    VasEBoot_free (fdiro);
  VasEBoot_free (data);

  VasEBoot_dl_unref (my_mod);

  return VasEBoot_errno;
}


static VasEBoot_err_t
VasEBoot_hfsplus_close (VasEBoot_file_t file)
{
  struct VasEBoot_hfsplus_data *data =
    (struct VasEBoot_hfsplus_data *) file->data;

  VasEBoot_free (data->opened_file.cbuf);
  VasEBoot_free (data->opened_file.compress_index);

  VasEBoot_free (data);

  VasEBoot_dl_unref (my_mod);

  return VAS_EBOOT_ERR_NONE;
}

/* Read LEN bytes data from FILE into BUF.  */
static VasEBoot_ssize_t
VasEBoot_hfsplus_read (VasEBoot_file_t file, char *buf, VasEBoot_size_t len)
{
  struct VasEBoot_hfsplus_data *data =
    (struct VasEBoot_hfsplus_data *) file->data;

  data->opened_file.file = file;

  if (VasEBoot_hfsplus_read_compressed && data->opened_file.compressed)
    return VasEBoot_hfsplus_read_compressed (&data->opened_file,
					 file->offset, len, buf);

  return VasEBoot_hfsplus_read_file (&data->opened_file,
				 file->read_hook, file->read_hook_data,
				 file->offset, len, buf);
}

/* Context for VasEBoot_hfsplus_dir.  */
struct VasEBoot_hfsplus_dir_ctx
{
  VasEBoot_fs_dir_hook_t hook;
  void *hook_data;
};

/* Helper for VasEBoot_hfsplus_dir.  */
static int
VasEBoot_hfsplus_dir_iter (const char *filename,
		       enum VasEBoot_fshelp_filetype filetype,
		       VasEBoot_fshelp_node_t node, void *data)
{
  struct VasEBoot_hfsplus_dir_ctx *ctx = data;
  struct VasEBoot_dirhook_info info;

  VasEBoot_memset (&info, 0, sizeof (info));
  info.dir = ((filetype & VAS_EBOOT_FSHELP_TYPE_MASK) == VAS_EBOOT_FSHELP_DIR);
  info.mtimeset = 1;
  info.mtime = node->mtime;
  info.inodeset = 1;
  info.inode = node->fileid;
  info.case_insensitive = !! (filetype & VAS_EBOOT_FSHELP_CASE_INSENSITIVE);
  VasEBoot_free (node);
  return ctx->hook (filename, &info, ctx->hook_data);
}

static VasEBoot_err_t
VasEBoot_hfsplus_dir (VasEBoot_device_t device, const char *path,
		  VasEBoot_fs_dir_hook_t hook, void *hook_data)
{
  struct VasEBoot_hfsplus_dir_ctx ctx = { hook, hook_data };
  struct VasEBoot_hfsplus_data *data = 0;
  struct VasEBoot_fshelp_node *fdiro = 0;

  VasEBoot_dl_ref (my_mod);

  data = VasEBoot_hfsplus_mount (device->disk);
  if (!data)
    goto fail;

  /* Find the directory that should be opened.  */
  VasEBoot_fshelp_find_file (path, &data->dirroot, &fdiro,
			 VasEBoot_hfsplus_iterate_dir,
			 VasEBoot_hfsplus_read_symlink, VAS_EBOOT_FSHELP_DIR);
  if (VasEBoot_errno)
    goto fail;

  /* Iterate over all entries in this directory.  */
  VasEBoot_hfsplus_iterate_dir (fdiro, VasEBoot_hfsplus_dir_iter, &ctx);

 fail:
  if (data && fdiro != &data->dirroot)
    VasEBoot_free (fdiro);
  VasEBoot_free (data);

  VasEBoot_dl_unref (my_mod);

  return VasEBoot_errno;
}


static VasEBoot_err_t
VasEBoot_hfsplus_label (VasEBoot_device_t device, char **label)
{
  struct VasEBoot_hfsplus_data *data;
  VasEBoot_disk_t disk = device->disk;
  struct VasEBoot_hfsplus_catkey *catkey;
  int i, label_len;
  VasEBoot_uint16_t *label_name;
  struct VasEBoot_hfsplus_key_internal intern;
  struct VasEBoot_hfsplus_btnode *node = NULL;
  VasEBoot_disk_addr_t ptr = 0;

  *label = 0;

  data = VasEBoot_hfsplus_mount (disk);
  if (!data)
    return VasEBoot_errno;

  /* Create a key that points to the label.  */
  intern.catkey.parent = 1;
  intern.catkey.name = 0;
  intern.catkey.namelen = 0;

  /* First lookup the first entry.  */
  if (VasEBoot_hfsplus_btree_search (&data->catalog_tree, &intern,
				 VasEBoot_hfsplus_cmp_catkey_id, &node, &ptr)
      || !node)
    {
      VasEBoot_free (data);
      return 0;
    }

  catkey = (struct VasEBoot_hfsplus_catkey *)
    VasEBoot_hfsplus_btree_recptr (&data->catalog_tree, node, ptr);

  label_len = VasEBoot_be_to_cpu16 (catkey->namelen);

  /* Ensure that the length is >= 0. */
  if (label_len < 0)
    label_len = 0;

  /* Ensure label length is at most 255 Unicode characters. */
  if (label_len > 255)
    label_len = 255;

  label_name = VasEBoot_calloc (label_len, sizeof (*label_name));
  if (!label_name)
    {
      VasEBoot_free (node);
      VasEBoot_free (data);
      return VasEBoot_errno;
    }

  for (i = 0; i < label_len; i++)
    {
      label_name[i] = VasEBoot_be_to_cpu16 (catkey->name[i]);

      /* If the name is obviously invalid, skip this node.  */
      if (label_name[i] == 0)
	{
	  VasEBoot_free (label_name);
	  VasEBoot_free (node);
	  VasEBoot_free (data);
	  return 0;
	}
    }

  *label = VasEBoot_calloc (label_len, VAS_EBOOT_MAX_UTF8_PER_UTF16 + 1);
  if (! *label)
    {
      VasEBoot_free (label_name);
      VasEBoot_free (node);
      VasEBoot_free (data);
      return VasEBoot_errno;
    }

  *VasEBoot_utf16_to_utf8 ((VasEBoot_uint8_t *) (*label), label_name,
		       label_len) = '\0';

  VasEBoot_free (label_name);
  VasEBoot_free (node);
  VasEBoot_free (data);

  return VAS_EBOOT_ERR_NONE;
}

/* Get mtime.  */
static VasEBoot_err_t
VasEBoot_hfsplus_mtime (VasEBoot_device_t device, VasEBoot_int64_t *tm)
{
  struct VasEBoot_hfsplus_data *data;
  VasEBoot_disk_t disk = device->disk;

  VasEBoot_dl_ref (my_mod);

  data = VasEBoot_hfsplus_mount (disk);
  if (!data)
    *tm = 0;
  else
    *tm = VasEBoot_be_to_cpu32 (data->volheader.utime) - 2082844800;

  VasEBoot_dl_unref (my_mod);

  VasEBoot_free (data);

  return VasEBoot_errno;

}

static VasEBoot_err_t
VasEBoot_hfsplus_uuid (VasEBoot_device_t device, char **uuid)
{
  struct VasEBoot_hfsplus_data *data;
  VasEBoot_disk_t disk = device->disk;

  VasEBoot_dl_ref (my_mod);

  data = VasEBoot_hfsplus_mount (disk);
  if (data)
    {
      *uuid = VasEBoot_xasprintf ("%016llx",
			     (unsigned long long)
			     VasEBoot_be_to_cpu64 (data->volheader.num_serial));
    }
  else
    *uuid = NULL;

  VasEBoot_dl_unref (my_mod);

  VasEBoot_free (data);

  return VasEBoot_errno;
}



static struct VasEBoot_fs VasEBoot_hfsplus_fs =
  {
    .name = "hfsplus",
    .fs_dir = VasEBoot_hfsplus_dir,
    .fs_open = VasEBoot_hfsplus_open,
    .fs_read = VasEBoot_hfsplus_read,
    .fs_close = VasEBoot_hfsplus_close,
    .fs_label = VasEBoot_hfsplus_label,
    .fs_mtime = VasEBoot_hfsplus_mtime,
    .fs_uuid = VasEBoot_hfsplus_uuid,
#ifdef VAS_EBOOT_UTIL
    .reserved_first_sector = 1,
    .blocklist_install = 1,
#endif
    .next = 0
  };

VAS_EBOOT_MOD_INIT(hfsplus)
{
  VasEBoot_hfsplus_fs.mod = mod;
  VasEBoot_fs_register (&VasEBoot_hfsplus_fs);
  my_mod = mod;
}

VAS_EBOOT_MOD_FINI(hfsplus)
{
  VasEBoot_fs_unregister (&VasEBoot_hfsplus_fs);
}