libblkid/befs.c - android_bootable_recovery - Gitiles

 /*
  * 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 <byteswap.h>
 #include "bitops.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,
 			((blkid_loff_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))
 				+ ((blkid_loff_t) FS16_TO_CPU(br->start, fs_le)
 					<< FS32_TO_CPU(bs->block_shift, fs_le)),
 			(blkid_loff_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,
 			((blkid_loff_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))
 				+ ((blkid_loff_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 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;

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

 		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;
 }

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

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

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

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

 	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;
 	int32_t first, last, mid, cmp;

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

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

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

 	do {
 		bn = (struct bplustree_node *) get_tree_node(pr, bs, &bi->data,
 			node_pointer, FS32_TO_CPU(bh->node_size, fs_le), fs_le);
 		if (!bn)
 			return -1;

 		keylengths = (uint16_t *) ((uint8_t *) bn
 				+ ((sizeof(struct bplustree_node)
 					+ FS16_TO_CPU(bn->all_key_length, fs_le)
 					+ sizeof(int64_t) - 1)
 						& ~(sizeof(int64_t) - 1)));
 		values = (int64_t *) ((uint8_t *) keylengths
 					+ FS16_TO_CPU(bn->all_key_count, fs_le)
 						* sizeof(uint16_t));
 		first = 0;
 		mid = 0;
 		last = FS16_TO_CPU(bn->all_key_count, fs_le) - 1;

 		cmp = compare_keys(bn->name, keylengths, last, key, strlen(key),
 									fs_le);
 		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), fs_le);
 				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 ((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;

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

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

 	sd = (struct small_data *) bi->small_data;

 	do {
 		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;

 		sd = (struct small_data *) ((uint8_t *) sd
 				+ sizeof(struct small_data)
 				+ FS16_TO_CPU(sd->name_size, fs_le) + 3
 				+ FS16_TO_CPU(sd->data_size, fs_le) + 1);

 	} while ((intptr_t) sd < (intptr_t) bi
 				+ (int32_t) FS32_TO_CPU(bi->inode_size, fs_le)
 				- (int32_t) sizeof(struct small_data));
 	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 -1;

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

 		value = get_key_value(pr, bs, bi, KEY_NAME, fs_le);

 		if (value < 0)
 			return 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 -1;

 			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 -1;

 				*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;
 	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 -1;

 	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 -1;

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

 	if (ret < 0)
 		return ret;

 	/*
 	 * all checks pass, set LABEL, VERSION and UUID
 	 */
 	if (strlen(bs->name))
 		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 0;
 }

 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 }
 	}
 };
	/*
	* 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 <byteswap.h>
	#include "bitops.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,
	((blkid_loff_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))
	+ ((blkid_loff_t) FS16_TO_CPU(br->start, fs_le)
	<< FS32_TO_CPU(bs->block_shift, fs_le)),
	(blkid_loff_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,
	((blkid_loff_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))
	+ ((blkid_loff_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 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;

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

	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;
	}

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

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

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

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

	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;
	int32_t first, last, mid, cmp;

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

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

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

	do {
	bn = (struct bplustree_node *) get_tree_node(pr, bs, &bi->data,
	node_pointer, FS32_TO_CPU(bh->node_size, fs_le), fs_le);
	if (!bn)
	return -1;

	keylengths = (uint16_t ) ((uint8_t ) bn
	+ ((sizeof(struct bplustree_node)
	+ FS16_TO_CPU(bn->all_key_length, fs_le)
	+ sizeof(int64_t) - 1)
	& ~(sizeof(int64_t) - 1)));
	values = (int64_t ) ((uint8_t ) keylengths
	+ FS16_TO_CPU(bn->all_key_count, fs_le)
	* sizeof(uint16_t));
	first = 0;
	mid = 0;
	last = FS16_TO_CPU(bn->all_key_count, fs_le) - 1;

	cmp = compare_keys(bn->name, keylengths, last, key, strlen(key),
	fs_le);
	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), fs_le);
	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 ((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;

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

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

	sd = (struct small_data *) bi->small_data;

	do {
	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;

	sd = (struct small_data ) ((uint8_t ) sd
	+ sizeof(struct small_data)
	+ FS16_TO_CPU(sd->name_size, fs_le) + 3
	+ FS16_TO_CPU(sd->data_size, fs_le) + 1);

	} while ((intptr_t) sd < (intptr_t) bi
	+ (int32_t) FS32_TO_CPU(bi->inode_size, fs_le)
	- (int32_t) sizeof(struct small_data));
	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 -1;

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

	value = get_key_value(pr, bs, bi, KEY_NAME, fs_le);

	if (value < 0)
	return 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 -1;

	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 -1;

	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;
	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 -1;

	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 -1;

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

	if (ret < 0)
	return ret;

	/*
	* all checks pass, set LABEL, VERSION and UUID
	*/
	if (strlen(bs->name))
	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 0;
	}

	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 }
	}
	};