/*
 * Copyright (C) 2010 Jeroen Oortwijn <oortwijn@gmail.com>
 *
 * Partly based on the Haiku BFS driver by
 *     Axel Dörfler <axeld@pinc-software.de>
 *
 * Also inspired by the Linux BeFS driver by
 *     Will Dyson <will_dyson@pobox.com>, et al.
 *
 * This file may be redistributed under the terms of the
 * GNU Lesser General Public License.
 */
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <inttypes.h>

#include "superblocks.h"

#define B_OS_NAME_LENGTH	0x20
#define SUPER_BLOCK_MAGIC1	0x42465331	/* BFS1 */
#define SUPER_BLOCK_MAGIC2	0xdd121031
#define SUPER_BLOCK_MAGIC3	0x15b6830e
#define SUPER_BLOCK_FS_ENDIAN	0x42494745	/* BIGE */
#define INODE_MAGIC1		0x3bbe0ad9
#define BPLUSTREE_MAGIC		0x69f6c2e8
#define BPLUSTREE_NULL		-1LL
#define NUM_DIRECT_BLOCKS	12
#define B_UINT64_TYPE		0x554c4c47	/* ULLG */
#define KEY_NAME		"be:volume_id"
#define KEY_SIZE		8

#define FS16_TO_CPU(value, fs_is_le) (fs_is_le ? le16_to_cpu(value) \
							: be16_to_cpu(value))
#define FS32_TO_CPU(value, fs_is_le) (fs_is_le ? le32_to_cpu(value) \
							: be32_to_cpu(value))
#define FS64_TO_CPU(value, fs_is_le) (fs_is_le ? le64_to_cpu(value) \
							: be64_to_cpu(value))

typedef struct block_run {
	int32_t		allocation_group;
	uint16_t	start;
	uint16_t	len;
} __attribute__((packed)) block_run, inode_addr;

struct befs_super_block {
	char		name[B_OS_NAME_LENGTH];
	int32_t		magic1;
	int32_t		fs_byte_order;
	uint32_t	block_size;
	uint32_t	block_shift;
	int64_t		num_blocks;
	int64_t		used_blocks;
	int32_t		inode_size;
	int32_t		magic2;
	int32_t		blocks_per_ag;
	int32_t		ag_shift;
	int32_t		num_ags;
	int32_t		flags;
	block_run	log_blocks;
	int64_t		log_start;
	int64_t		log_end;
	int32_t		magic3;
	inode_addr	root_dir;
	inode_addr	indices;
	int32_t		pad[8];
} __attribute__((packed));

typedef struct data_stream {
	block_run	direct[NUM_DIRECT_BLOCKS];
	int64_t		max_direct_range;
	block_run	indirect;
	int64_t		max_indirect_range;
	block_run	double_indirect;
	int64_t		max_double_indirect_range;
	int64_t		size;
} __attribute__((packed)) data_stream;

struct befs_inode {
	int32_t		magic1;
	inode_addr	inode_num;
	int32_t		uid;
	int32_t		gid;
	int32_t		mode;
	int32_t		flags;
	int64_t		create_time;
	int64_t		last_modified_time;
	inode_addr	parent;
	inode_addr	attributes;
	uint32_t	type;
	int32_t		inode_size;
	uint32_t	etc;
	data_stream	data;
	int32_t		pad[4];
	int32_t		small_data[0];
} __attribute__((packed));

struct small_data {
	uint32_t	type;
	uint16_t	name_size;
	uint16_t	data_size;
	char		name[0];
} __attribute__((packed));

struct bplustree_header {
	uint32_t	magic;
	uint32_t	node_size;
	uint32_t	max_number_of_levels;
	uint32_t	data_type;
	int64_t		root_node_pointer;
	int64_t		free_node_pointer;
	int64_t		maximum_size;
} __attribute__((packed));

struct bplustree_node {
	int64_t		left_link;
	int64_t		right_link;
	int64_t		overflow_link;
	uint16_t	all_key_count;
	uint16_t	all_key_length;
	char		name[0];
} __attribute__((packed));

static unsigned char *get_block_run(blkid_probe pr, const struct befs_super_block *bs,
					const struct block_run *br, int fs_le)
{
	return blkid_probe_get_buffer(pr,
			((uint64_t) FS32_TO_CPU(br->allocation_group, fs_le)
					<< FS32_TO_CPU(bs->ag_shift, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le))
				+ ((uint64_t) FS16_TO_CPU(br->start, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le)),
			(uint64_t) FS16_TO_CPU(br->len, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le));
}

static unsigned char *get_custom_block_run(blkid_probe pr,
				const struct befs_super_block *bs,
				const struct block_run *br,
				int64_t offset, uint32_t length, int fs_le)
{
	if (offset + length > (int64_t) FS16_TO_CPU(br->len, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le))
		return NULL;

	return blkid_probe_get_buffer(pr,
			((uint64_t) FS32_TO_CPU(br->allocation_group, fs_le)
					<< FS32_TO_CPU(bs->ag_shift, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le))
				+ ((uint64_t) FS16_TO_CPU(br->start, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le))
				+ offset,
			length);
}

static unsigned char *get_tree_node(blkid_probe pr, const struct befs_super_block *bs,
				const struct data_stream *ds,
				int64_t start, uint32_t length, int fs_le)
{
	if (start < (int64_t) FS64_TO_CPU(ds->max_direct_range, fs_le)) {
		int64_t br_len;
		size_t i;

		for (i = 0; i < NUM_DIRECT_BLOCKS; i++) {
			br_len = (int64_t) FS16_TO_CPU(ds->direct[i].len, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le);
			if (start < br_len)
				return get_custom_block_run(pr, bs,
							&ds->direct[i],
							start, length, fs_le);
			else
				start -= br_len;
		}
	} else if (start < (int64_t) FS64_TO_CPU(ds->max_indirect_range, fs_le)) {
		struct block_run *br;
		int64_t max_br, br_len, i;

		start -= FS64_TO_CPU(ds->max_direct_range, fs_le);
		max_br = ((int64_t) FS16_TO_CPU(ds->indirect.len, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le))
				/ sizeof(struct block_run);

		br = (struct block_run *) get_block_run(pr, bs, &ds->indirect,
									fs_le);
		if (!br)
			return NULL;

		for (i = 0; i < max_br; i++) {
			br_len = (int64_t) FS16_TO_CPU(br[i].len, fs_le)
					<< FS32_TO_CPU(bs->block_shift, fs_le);
			if (start < br_len)
				return get_custom_block_run(pr, bs, &br[i],
							start, length, fs_le);
			else
				start -= br_len;
		}
	} else if (start < (int64_t) FS64_TO_CPU(ds->max_double_indirect_range, fs_le)) {
		struct block_run *br;
		int64_t max_br, di_br_size, br_per_di_br, di_index, i_index;

		start -= (int64_t) FS64_TO_CPU(ds->max_indirect_range, fs_le);

		di_br_size = (int64_t) FS16_TO_CPU(ds->double_indirect.len,
				fs_le) << FS32_TO_CPU(bs->block_shift, fs_le);
		if (di_br_size == 0)
			return NULL;

		br_per_di_br = di_br_size / sizeof(struct block_run);
		if (br_per_di_br == 0)
			return NULL;

		di_index = start / (br_per_di_br * di_br_size);
		i_index = (start % (br_per_di_br * di_br_size)) / di_br_size;
		start = (start % (br_per_di_br * di_br_size)) % di_br_size;

		if (di_index >= br_per_di_br)
			return NULL; /* Corrupt? */

		br = (struct block_run *) get_block_run(pr, bs,
						&ds->double_indirect, fs_le);
		if (!br)
			return NULL;

		max_br = ((int64_t)FS16_TO_CPU(br[di_index].len, fs_le)
			  << FS32_TO_CPU(bs->block_shift, fs_le))
			/ sizeof(struct block_run);

		if (i_index >= max_br)
			return NULL; /* Corrupt? */

		br = (struct block_run *) get_block_run(pr, bs, &br[di_index],
									fs_le);
		if (!br)
			return NULL;

		return get_custom_block_run(pr, bs, &br[i_index], start, length,
									fs_le);
	}
	return NULL;
}

#define BAD_KEYS -2

static int32_t compare_keys(const char keys1[], uint16_t keylengths1[],
			    int32_t index, const char *key2,
			    uint16_t keylength2, uint16_t all_key_length,
			    int fs_le)
{
	const char *key1;
	uint16_t keylength1, keystart1;
	int32_t result;

	keystart1 = index == 0 ? 0 : FS16_TO_CPU(keylengths1[index - 1], fs_le);
	keylength1 = FS16_TO_CPU(keylengths1[index], fs_le) - keystart1;

	if (keystart1 + keylength1 > all_key_length)
		return BAD_KEYS; /* Corrupt? */

	key1 = &keys1[keystart1];

	result = strncmp(key1, key2, min(keylength1, keylength2));

	if (result == 0)
		return keylength1 - keylength2;

	if (result < 0) /* Don't clash with BAD_KEYS */
		result = -1;

	return result;
}

static int64_t get_key_value(blkid_probe pr, const struct befs_super_block *bs,
			const struct befs_inode *bi, const char *key, int fs_le)
{
	struct bplustree_header *bh;
	struct bplustree_node *bn;
	uint16_t *keylengths;
	int64_t *values;
	int64_t node_pointer;
	uint32_t bn_size, all_key_count, all_key_length;
	uint32_t keylengths_offset, values_offset;
	int32_t first, last, mid, cmp;
	int loop_detect = 0;

	errno = 0;
	bh = (struct bplustree_header *) get_tree_node(pr, bs, &bi->data, 0,
					sizeof(struct bplustree_header), fs_le);
	if (!bh)
		return errno ? -errno : -ENOENT;

	if ((int32_t) FS32_TO_CPU(bh->magic, fs_le) != BPLUSTREE_MAGIC)
		return -ENOENT;

	node_pointer = FS64_TO_CPU(bh->root_node_pointer, fs_le);
	bn_size = FS32_TO_CPU(bh->node_size, fs_le);

	if (bn_size < sizeof(struct bplustree_node))
		return -ENOENT; /* Corrupt? */

	do {
		errno = 0;

		bn = (struct bplustree_node *) get_tree_node(pr, bs, &bi->data,
			node_pointer, bn_size, fs_le);
		if (!bn)
			return errno ? -errno : -ENOENT;

		all_key_count = FS16_TO_CPU(bn->all_key_count, fs_le);
		all_key_length = FS16_TO_CPU(bn->all_key_length, fs_le);
		keylengths_offset =
			(sizeof(struct bplustree_node) + all_key_length
			 + sizeof(int64_t) - 1) & ~(sizeof(int64_t) - 1);
		values_offset = keylengths_offset +
			all_key_count * sizeof(uint16_t);

		if (values_offset + all_key_count * sizeof(uint64_t) > bn_size)
			return -ENOENT; /* Corrupt? */

		keylengths = (uint16_t *) ((uint8_t *) bn + keylengths_offset);
		values = (int64_t *) ((uint8_t *) bn + values_offset);

		first = 0;
		mid = 0;
		last = all_key_count - 1;

		cmp = compare_keys(bn->name, keylengths, last, key,
				   strlen(key), all_key_length, fs_le);
		if (cmp == BAD_KEYS)
			return -ENOENT;

		if (cmp == 0) {
			if ((int64_t) FS64_TO_CPU(bn->overflow_link, fs_le)
							== BPLUSTREE_NULL)
				return FS64_TO_CPU(values[last], fs_le);
			else
				node_pointer = FS64_TO_CPU(values[last], fs_le);
		} else if (cmp < 0)
			node_pointer = FS64_TO_CPU(bn->overflow_link, fs_le);
		else {
			while (first <= last) {
				mid = (first + last) / 2;

				cmp = compare_keys(bn->name, keylengths, mid,
						   key, strlen(key),
						   all_key_length, fs_le);
				if (cmp == BAD_KEYS)
					return -ENOENT;

				if (cmp == 0) {
					if ((int64_t) FS64_TO_CPU(bn->overflow_link,
						fs_le) == BPLUSTREE_NULL)
						return FS64_TO_CPU(values[mid],
									fs_le);
					else
						break;
				} else if (cmp < 0)
					first = mid + 1;
				else
					last = mid - 1;
			}
			if (cmp < 0)
				node_pointer = FS64_TO_CPU(values[mid + 1],
									fs_le);
			else
				node_pointer = FS64_TO_CPU(values[mid], fs_le);
		}
	} while (++loop_detect < 100 &&
		(int64_t) FS64_TO_CPU(bn->overflow_link, fs_le)
						!= BPLUSTREE_NULL);
	return 0;
}

static int get_uuid(blkid_probe pr, const struct befs_super_block *bs,
					uint64_t * const uuid, int fs_le)
{
	struct befs_inode *bi;
	struct small_data *sd;
	uint64_t bi_size, offset, sd_size, sd_total_size;

	bi = (struct befs_inode *) get_block_run(pr, bs, &bs->root_dir, fs_le);
	if (!bi)
		return errno ? -errno : BLKID_PROBE_NONE;

	if (FS32_TO_CPU(bi->magic1, fs_le) != INODE_MAGIC1)
		return BLKID_PROBE_NONE;

	bi_size = (uint64_t)FS16_TO_CPU(bs->root_dir.len, fs_le) <<
		FS32_TO_CPU(bs->block_shift, fs_le);
	sd_total_size = min(bi_size - sizeof(struct befs_inode),
			    (uint64_t)FS32_TO_CPU(bi->inode_size, fs_le));

	offset = 0;

	while (offset + sizeof(struct small_data) <= sd_total_size) {
		sd = (struct small_data *) ((uint8_t *)bi->small_data + offset);
		sd_size = sizeof(struct small_data)
			+ FS16_TO_CPU(sd->name_size, fs_le) + 3
			+ FS16_TO_CPU(sd->data_size, fs_le) + 1;

		if (offset + sd_size > sd_total_size)
			break;

		if (FS32_TO_CPU(sd->type, fs_le) == B_UINT64_TYPE
			&& FS16_TO_CPU(sd->name_size, fs_le) == strlen(KEY_NAME)
			&& FS16_TO_CPU(sd->data_size, fs_le) == KEY_SIZE
			&& strcmp(sd->name, KEY_NAME) == 0) {

			memcpy(uuid,
			       sd->name + FS16_TO_CPU(sd->name_size, fs_le) + 3,
			       sizeof(uint64_t));

			break;
		} else if (FS32_TO_CPU(sd->type, fs_le) == 0
				&& FS16_TO_CPU(sd->name_size, fs_le) == 0
				&& FS16_TO_CPU(sd->data_size, fs_le) == 0)
			break;

		offset += sd_size;
	}

	if (*uuid == 0
		&& (FS32_TO_CPU(bi->attributes.allocation_group, fs_le) != 0
			|| FS16_TO_CPU(bi->attributes.start, fs_le) != 0
			|| FS16_TO_CPU(bi->attributes.len, fs_le) != 0)) {
		int64_t value;

		bi = (struct befs_inode *) get_block_run(pr, bs,
							&bi->attributes, fs_le);
		if (!bi)
			return errno ? -errno : BLKID_PROBE_NONE;

		if (FS32_TO_CPU(bi->magic1, fs_le) != INODE_MAGIC1)
			return BLKID_PROBE_NONE;

		value = get_key_value(pr, bs, bi, KEY_NAME, fs_le);
		if (value < 0)
			return value == -ENOENT ? BLKID_PROBE_NONE : value;

		else if (value > 0) {
			bi = (struct befs_inode *) blkid_probe_get_buffer(pr,
				value << FS32_TO_CPU(bs->block_shift, fs_le),
				FS32_TO_CPU(bs->block_size, fs_le));
			if (!bi)
				return errno ? -errno : BLKID_PROBE_NONE;

			if (FS32_TO_CPU(bi->magic1, fs_le) != INODE_MAGIC1)
				return 1;

			if (FS32_TO_CPU(bi->type, fs_le) == B_UINT64_TYPE
				&& FS64_TO_CPU(bi->data.size, fs_le) == KEY_SIZE
				&& FS16_TO_CPU(bi->data.direct[0].len, fs_le)
									== 1) {
				uint64_t *attr_data;

				attr_data = (uint64_t *) get_block_run(pr, bs,
						&bi->data.direct[0], fs_le);
				if (!attr_data)
					return errno ? -errno : BLKID_PROBE_NONE;

				*uuid = *attr_data;
			}
		}
	}
	return 0;
}

static int probe_befs(blkid_probe pr, const struct blkid_idmag *mag)
{
	struct befs_super_block *bs;
	const char *version = NULL;
	uint64_t volume_id = 0;
	uint32_t block_size, block_shift;
	int fs_le, ret;

	bs = (struct befs_super_block *) blkid_probe_get_buffer(pr,
					mag->sboff - B_OS_NAME_LENGTH,
					sizeof(struct befs_super_block));
	if (!bs)
		return errno ? -errno : BLKID_PROBE_NONE;

	if (le32_to_cpu(bs->magic1) == SUPER_BLOCK_MAGIC1
		&& le32_to_cpu(bs->magic2) == SUPER_BLOCK_MAGIC2
		&& le32_to_cpu(bs->magic3) == SUPER_BLOCK_MAGIC3
		&& le32_to_cpu(bs->fs_byte_order) == SUPER_BLOCK_FS_ENDIAN) {
		fs_le = 1;
		version = "little-endian";
	} else if (be32_to_cpu(bs->magic1) == SUPER_BLOCK_MAGIC1
		&& be32_to_cpu(bs->magic2) == SUPER_BLOCK_MAGIC2
		&& be32_to_cpu(bs->magic3) == SUPER_BLOCK_MAGIC3
		&& be32_to_cpu(bs->fs_byte_order) == SUPER_BLOCK_FS_ENDIAN) {
		fs_le = 0;
		version = "big-endian";
	} else
		return BLKID_PROBE_NONE;

	block_size = FS32_TO_CPU(bs->block_size, fs_le);
	block_shift = FS32_TO_CPU(bs->block_shift, fs_le);

	if (block_shift < 10 || block_shift > 13 ||
	    block_size != 1U << block_shift)
		return BLKID_PROBE_NONE;

	ret = get_uuid(pr, bs, &volume_id, fs_le);

	if (ret != 0)
		return ret;

	/*
	 * all checks pass, set LABEL, VERSION and UUID
	 */
	if (*bs->name != '\0')
		blkid_probe_set_label(pr, (unsigned char *) bs->name,
							sizeof(bs->name));
	if (version)
		blkid_probe_set_version(pr, version);

	if (volume_id)
		blkid_probe_sprintf_uuid(pr, (unsigned char *) &volume_id,
					sizeof(volume_id), "%016" PRIx64,
					FS64_TO_CPU(volume_id, fs_le));
	return BLKID_PROBE_OK;
}

const struct blkid_idinfo befs_idinfo =
{
	.name		= "befs",
	.usage		= BLKID_USAGE_FILESYSTEM,
	.probefunc	= probe_befs,
	.minsz		= 1024 * 1440,
	.magics		= {
		{ .magic = "BFS1", .len = 4, .sboff = B_OS_NAME_LENGTH },
		{ .magic = "1SFB", .len = 4, .sboff = B_OS_NAME_LENGTH },
		{ .magic = "BFS1", .len = 4, .sboff = 0x200 +
							B_OS_NAME_LENGTH },
		{ .magic = "1SFB", .len = 4, .sboff = 0x200 +
							B_OS_NAME_LENGTH },
		{ NULL }
	}
};