apa_partition_t *prev = table->parts + (i > 0 ? i - 1 : table->part_count - 1);
	  apa_partition_t *curr = table->parts + i;
	  apa_partition_t *next = table->parts + (i + 1 < table->part_count ? i + 1 : 0);
	  /* no need to be endian-aware, since both have same endianess */
	  if (curr->header.prev != prev->header.start)
	    {
	      curr->modified = 1;
	      curr->header.prev = prev->header.start;
	    }
	  if (curr->header.next != next->header.start)
	    {
	      curr->modified = 1;
	      curr->header.next = next->header.start;
	    }
	  if (curr->modified)
	    set_u32 (&curr->header.checksum, apa_partition_checksum (&curr->header));
	}
    }
}


/**************************************************************/
int
apa_allocate_space (apa_partition_table_t *table,
		    const char *partition_name,
		    u_int32_t size_in_mb,
		    u_int32_t *new_partition_start,
		    int decreasing_size)
{
  int result = RET_OK;
  char *map = table->chunks_map;
  u_int32_t i;
  int found;

  /* check whether that partition name is not already used */
  found = 0;
  for (i=0; i<table->part_count; ++i)
    if (get_u16 (&table->parts [i].header.flags) == 0 &&
	get_u32 (&table->parts [i].header.main) == 0)
      if (caseless_compare (partition_name, table->parts [i].header.id))
	{
	  found = 1;
	  break;
	}
  if (found)
    return (RET_PART_EXISTS);

  if (table->free_chunks * 128 >= size_in_mb)
    {
      u_int32_t max_part_size_in_entries = table->total_chunks < 32 ? 1 : table->total_chunks / 32;
      u_int32_t max_part_size_in_mb = max_part_size_in_entries * 128;
      u_int32_t estimated_entries = (size_in_mb + 127) / 128 + 1;
      u_int32_t partitions_used = 0;
      ps2_partition_run_t *partitions = (ps2_partition_run_t *)
	osal_alloc (estimated_entries * sizeof (ps2_partition_run_t));
      if (partitions != NULL)
	{
	  /* use the most straight forward approach possible:
	     fill from the first gap onwards */
	  u_int32_t mb_remaining = size_in_mb;
	  u_int32_t allocated_mb, overhead_mb;
	  for (i=0; i<estimated_entries; ++i)
	    { /* initialize */
	      partitions [i].sector = 0;
	      partitions [i].size_in_mb = 0;
	    }
	  for (i=0; mb_remaining>0 && i<table->total_chunks; ++i)
	    if (map [i] == MAP_AVAIL)
	      {
		partitions [partitions_used].sector = i * ((128 _MB) / 512);
		partitions [partitions_used].size_in_mb = 128;
		map [i] = MAP_ALLOC; /* "allocate" chunk */
		++(partitions_used);
		mb_remaining = (mb_remaining > 128 ? mb_remaining - 128 : 0);
	      }

	  optimize_partitions (partitions, &partitions_used, max_part_size_in_mb);

	  /* calculate overhead (4M for main + 1M for each sub)
	     and allocate additional 128 M partition if necessary */
	  allocated_mb = 0; overhead_mb = 3;
	  for (i=0; i<partitions_used; ++i)
	    {
	      allocated_mb += partitions [i].size_in_mb;
	      ++overhead_mb;
	    }
	  if (allocated_mb < size_in_mb + overhead_mb)
	    { /* add one more partition or return RET_NO_SPACE */
	      int free_entry_found = 0; /* if free entry not found return RET_NO_SPACE */
	      for (i=0; i<table->total_chunks; ++i)
		if (map [i] == MAP_AVAIL)
		  {
		    partitions [partitions_used].sector = i * ((128 _MB) / 512);
		    partitions [partitions_used].size_in_mb = 128;
		    ++partitions_used;
		    optimize_partitions (partitions, &partitions_used, max_part_size_in_mb);

		    free_entry_found = 1;
		    break;
		  }
	      result = free_entry_found ? RET_OK : RET_NO_SPACE;
	    }
	  else
	    result = RET_OK;

	  if (result == RET_OK)
	    { /* create new partitions in the partition table */
	      ps2_partition_header_t part;
	      u_int32_t last_partition_start =
		table->part_count > 0 ?
		get_u32 (&table->parts [table->part_count - 1].header.start) : 0;

	      if (decreasing_size)
		sort_partitions (partitions, partitions_used);

	      /* current last partition would be remapped by normalize */
	      setup_main_part (&part, partition_name, partitions, partitions_used,
			       last_partition_start);
	      result = apa_part_add (table, &part, 0, 1);
	      for (i=1; result == RET_OK && i<partitions_used; ++i)
		{
		  setup_sub_part (&part, i, partitions, partitions_used);
		  result = apa_part_add (table, &part, 0, 1);
		}
	      if (result == RET_OK)
		{
		  normalize_linked_list (table);
		  *new_partition_start = partitions [0].sector;
		}
	    }
	  osal_free (partitions);
	}
      else
	result = RET_NO_MEM; /* out-of-memory */
    }
  else
    result = RET_NO_SPACE; /* not enough free space */

  return (result);
}


/**************************************************************/
int
apa_delete_partition (apa_partition_table_t *table,
		      const char *partition_name)
{
  u_int32_t partition_index;
  int result = apa_find_partition (table, partition_name, &partition_index);
  if (result == RET_OK)
    {
      u_int32_t i, count = 1;
      u_int32_t pending_deletes [PS2_PART_MAXSUB]; /* starting sectors of parts pending delete */
      const ps2_partition_header_t *part = &table->parts [partition_index].header;

      if (get_u16 (&part->type) == 1)
	return (RET_NOT_ALLOWED); /* deletion of system partitions is not allowed */

      /* preserve a list of partitions to be deleted */
      pending_deletes [0] = get_u32 (&part->start);
      for (i=0; i<get_u32 (&part->nsub); ++i)
	pending_deletes [count++] = get_u32 (&part->subs [i].start);

      /* remove partitions from the double-linked list */
      i = 0;
      while (i < table->part_count)
	{
	  u_int32_t j;
	  int found = 0;
	  for (j=0; j<count; ++j)
	    if (get_u32 (&table->parts [i].header.start) == pending_deletes [j])
	      {
		found = 1;
		break;
	      }
	  if (found)
	    { /* remove this partition */
	      u_int32_t part_no = get_u32 (&table->parts [i].header.start) / 262144; /* 262144 sectors == 128M */
	      u_int32_t num_parts = get_u32 (&table->parts [i].header.length) / 262144;

	      memmove (table->parts + i, table->parts + i + 1,
		       sizeof (apa_partition_t) * (table->part_count - i - 1));
	      --table->part_count;

	      /* "free" num_parts starting at part_no */
	      while (num_parts)
		{
		  table->chunks_map [part_no] = MAP_AVAIL;
		  ++part_no;
		  --num_parts;
		  --table->allocated_chunks;
		  ++table->free_chunks;
		}
	    }
	  else
	    ++i;
	}

      normalize_linked_list (table);
    }
  return (result);
}


/**************************************************************/
int
apa_commit (const char *path,
	    const apa_partition_table_t *table)
{
  int result = apa_check (table);
  if (result == RET_OK)
    {
      hio_t *hio;
      result = hio_probe (path, &hio);
      if (result == OSAL_OK)
	{
	  result = apa_commit_ex (hio, table);
	  result = hio->close (hio) == OSAL_OK ? result : OSAL_ERR;
	}
    }
  return (result);
}


/**************************************************************/
int
apa_commit_ex (hio_t *hio,
	       const apa_partition_table_t *table)
{
  int result = apa_check (table);
  if (result == RET_OK)
    {
      u_int32_t i;
      for (i=0; result == RET_OK && i<table->part_count; ++i)
	{
	  if (table->parts [i].modified)
	    {
	      u_int32_t bytes;
	      const ps2_partition_header_t *part = &table->parts [i].header;
	      result = hio->write (hio, get_u32 (&part->start),
				   sizeof (*part) / 512, part, &bytes);
	      if (result == OSAL_OK)
		result = bytes == sizeof (ps2_partition_header_t) ? OSAL_OK : RET_ERR;
	    }
	}
    }
  return (result);
}


/**************************************************************/
#define ADD_PROBLEM(buff,size,problem,len) \
  if ((len) < (size))			   \
    {					   \
      memcpy (buff, problem, len);	   \
      (size) -= (len);			   \
      (buff) += (len);			   \
       *(buff) = '\0';			   \
    }

static int
apa_list_problems (const apa_partition_table_t *table,
		   char *buffer,
		   size_t buffer_size)
{ /* NOTE: keep in sync with apa_check */
  u_int32_t i, j, k;
  char tmp [1024];
  size_t len;

  const u_int32_t total_sectors = table->device_size_in_mb * 1024 * 2;

  *buffer = '\0';
  for (i=0; i<table->part_count; ++i)
    {
      const ps2_partition_header_t *part = &table->parts [i].header;
      u_int32_t checksum = apa_partition_checksum (part);
      if (get_u32 (&part->checksum) != checksum)
	{
	  len = sprintf (tmp, "%06lx00: bad checksum: 0x%08lx instead of 0x%08lx;\n",
			 (unsigned long) (get_u32 (&part->start) >> 8),
			 (unsigned long) get_u32 (&part->checksum),
			 (unsigned long) checksum);
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
	}

      if (get_u32 (&part->start) < total_sectors &&
	  get_u32 (&part->start) + get_u32 (&part->length) <= total_sectors)
	;
      else
	{
#if defined (LIMIT_HDD_TO_128GB)
	  len = sprintf (tmp, "%06lx00 +%06lx00: across 128GB mark;\n",
			 (unsigned long) (get_u32 (&part->start) >> 8),
			 (unsigned long) (get_u32 (&part->length) >> 8));
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
#else
	  len = sprintf (tmp, "%06lx00 +%06lx00: outside HDD data area;\n",
			 (unsigned long) (get_u32 (&part->start) >> 8),
			 (unsigned long) (get_u32 (&part->length) >> 8));
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
#endif
	}

      if ((get_u32 (&part->length) % ((128 _MB) / 512)) != 0)
	{
	  len = sprintf (tmp, "%06lx00: size %06lx00 not multiple to 128MB;\n",
			 (unsigned long) (get_u32 (&part->start) >> 8),
			 (unsigned long) (get_u32 (&part->length) >> 8));
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
	}

      if ((get_u32 (&part->start) % get_u32 (&part->length)) != 0)
	{
	  len = sprintf (tmp, "%06lx00: start not multiple to size %06lx00;\n",
			 (unsigned long) (get_u32 (&part->start) >> 8),
			 (unsigned long) (get_u32 (&part->length) >> 8));
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
	}

      if (get_u32 (&part->main) == 0 &&
	  get_u16 (&part->flags) == 0 &&
	  get_u32 (&part->start) != 0)
	{ /* check sub-partitions */
	  u_int32_t count = 0;
	  for (j=0; j<table->part_count; ++j)
	    {
	      const ps2_partition_header_t *part2 = &table->parts [j].header;
	      if (get_u32 (&part2->main) == get_u32 (&part->start))
		{ /* sub-partition of current main partition */
		  int found;
		  if (get_u16 (&part2->flags) != PS2_PART_FLAG_SUB)
		    {
		      len = sprintf (tmp, "%06lx00: mismatching sub-partition flag;\n",
				     (unsigned long) (get_u32 (&part2->start) >> 8));
		      ADD_PROBLEM (buffer, buffer_size, tmp, len);
		    }

		  found = 0;
		  for (k=0; k<get_u32 (&part->nsub); ++k)
		    if (get_u32 (&part->subs [k].start) == get_u32 (&part2->start))
		      { /* in list */
			if (get_u32 (&part->subs [k].length) != get_u32 (&part2->length))
			  {
			    len = sprintf (tmp, "%06lx00: mismatching sub-partition size: %06lx00 != %06lx00;\n",
					   (unsigned long) (get_u32 (&part2->start) >> 8),
					   (unsigned long) (get_u32 (&part2->length) >> 8),
					   (unsigned long) (get_u32 (&part->subs [k].length) >> 8));
			    ADD_PROBLEM (buffer, buffer_size, tmp, len);
			  }
			found = 1;
			break;
		      }
		  if (!found)
		    {
		      len = sprintf (tmp, "%06lx00: not a sub-partition of %06lx00;\n",
				     (unsigned long) (get_u32 (&part2->start) >> 8),
				     (unsigned long) (get_u32 (&part->start) >> 8));
		      ADD_PROBLEM (buffer, buffer_size, tmp, len);
		    }

		  ++count;
		}
	    }
	  if (count != get_u32 (&part->nsub))
	    {
	      len = sprintf (tmp, "%06lx00: only %u sub-partitions found of %u;\n",
			     (unsigned long) (get_u32 (&part->start) >> 8),
			     (unsigned int) count, (unsigned int) get_u32 (&part->nsub));
	      ADD_PROBLEM (buffer, buffer_size, tmp, len);
	    }
	}
    }

  /* verify double-linked list */
  for (i=0; i<table->part_count; ++i)
    {
      apa_partition_t *prev = table->parts + (i > 0 ? i - 1 : table->part_count - 1);
      apa_partition_t *curr = table->parts + i;
      apa_partition_t *next = table->parts + (i + 1 < table->part_count ? i + 1 : 0);
      if (get_u32 (&curr->header.prev) != get_u32 (&prev->header.start))
	{
	  len = sprintf (tmp, "%06lx00: %06lx00 is previous, not %06lx00;\n",
			 (unsigned long) (get_u32 (&curr->header.start) >> 8),
			 (unsigned long) (get_u32 (&prev->header.start) >> 8),
			 (unsigned long) (get_u32 (&curr->header.prev) >> 8));
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
	}
      if (get_u32 (&curr->header.next) != get_u32 (&next->header.start))
	{
	  len = sprintf (tmp, "%06lx00: %06lx00 is next, not %06lx00;\n",
			 (unsigned long) (get_u32 (&curr->header.start) >> 8),
			 (unsigned long) (get_u32 (&next->header.start) >> 8),
			 (unsigned long) (get_u32 (&curr->header.next) >> 8));
	  ADD_PROBLEM (buffer, buffer_size, tmp, len);
	}
	return (RET_BAD_APA); /* bad links */
    }

  return (RET_OK);
}


/**************************************************************/
static int
apa_check (const apa_partition_table_t *table)
{ /* NOTE: keep in sync with apa_list_problems */
  u_int32_t i, j, k;

  const u_int32_t total_sectors = table->device_size_in_mb * 1024 * 2;

  for (i=0; i<table->part_count; ++i)
    {
      const ps2_partition_header_t *part = &table->parts [i].header;
      if (get_u32 (&part->checksum) != apa_partition_checksum (part))
	return (RET_BAD_APA); /* bad checksum */

      if (get_u32 (&part->start) < total_sectors &&
	  get_u32 (&part->start) + get_u32 (&part->length) <= total_sectors)
	;
      else
	{
#if defined (LIMIT_HDD_TO_128GB)
	  return (RET_CROSS_128GB); /* data behind 128GB mark */
#else
	  return (RET_BAD_APA); /* data behind end-of-HDD */
#endif
	}

      if ((get_u32 (&part->length) % ((128 _MB) / 512)) != 0)
	return (RET_BAD_APA); /* partition size not multiple to 128MB */

      if ((get_u32 (&part->start) % get_u32 (&part->length)) != 0)
	return (RET_BAD_APA); /* partition start not multiple on partition size */

      if (get_u32 (&part->main) == 0 &&
	  get_u16 (&part->flags) == 0 &&
	  get_u32 (&part->start) != 0)
	{ /* check sub-partitions */
	  u_int32_t count = 0;
	  for (j=0; j<table->part_count; ++j)
	    {
	      const ps2_partition_header_t *part2 = &table->parts [j].header;
	      if (get_u32 (&part2->main) == get_u32 (&part->start))
		{ /* sub-partition of current main partition */
		  int found;
		  if (get_u16 (&part2->flags) != PS2_PART_FLAG_SUB)
		    return (RET_BAD_APA);

		  found = 0;
		  for (k=0; k<get_u32 (&part->nsub); ++k)
		    if (get_u32 (&part->subs [k].start) == get_u32 (&part2->start))
		      { /* in list */
			if (get_u32 (&part->subs [k].length) != get_u32 (&part2->length))
			  return (RET_BAD_APA);
			found = 1;
			break;
		      }
		  if (!found)
		    return (RET_BAD_APA); /* not found in the list */

		  ++count;
		}
	    }
	  if (count != get_u32 (&part->nsub))
	    return (RET_BAD_APA); /* wrong number of sub-partitions */
	}
    }

  /* verify double-linked list */
  for (i=0; i<table->part_count; ++i)
    {
      apa_partition_t *prev = table->parts + (i > 0 ? i - 1 : table->part_count - 1);
      apa_partition_t *curr = table->parts + i;
      apa_partition_t *next = table->parts + (i + 1 < table->part_count ? i + 1 : 0);
      if (get_u32 (&curr->header.prev) != get_u32 (&prev->header.start) ||
	  get_u32 (&curr->header.next) != get_u32 (&next->header.start))
	return (RET_BAD_APA); /* bad links */
    }

  return (RET_OK);
}