/*
 * Copyright (C) 2015 Guido Berhoerster <guido+libpws@berhoerster.name>
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "compat.h"

#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdarg.h>
#include <errno.h>
#ifdef	HAVE_ENDIAN_H
#include <endian.h>
#endif /* HAVE_ENDIAN_H */
#ifdef	HAVE_SYS_ENDIAN_H
#include <sys/endian.h>
#endif /* HAVE_ENDIAN_H */
#include <nettle/twofish.h>
#include <nettle/cbc.h>
#include <nettle/hmac.h>
#include <nettle/sha.h>

#include "pws-internal.h"

#define	MAX_ITER		(1 << 22)
#define	DEFAULT_ITER		10000
#define	KEY_SIZE		32UL
#define	SALT_SIZE		32UL
#define	METADATA_SIZE		(sizeof (psafe3_tag) + SALT_SIZE + 4 +\
    SHA256_DIGEST_SIZE + KEY_SIZE + KEY_SIZE + TWOFISH_BLOCK_SIZE)

static const unsigned char psafe3_tag[] = { 'P', 'W', 'S', '3' };
static const unsigned char eof_marker[] = { 'P', 'W', 'S', '3', '-', 'E', 'O',
    'F', 'P', 'W', 'S', '3', '-', 'E', 'O', 'F' };

RB_HEAD(empty_groups_tree, pws3_field);

RB_HEAD(records_tree, pws3_record);

struct pws3_file {
	struct pws3_field	*fields[256];
	struct empty_groups_tree *empty_groups_tree;
	struct records_tree	*records_tree;
	struct pws_file_error {
		enum pws_error_code code;
		int		errnum;
		char		*msg;
	} error;
};

struct twofish_cbc_ctx CBC_CTX(struct twofish_ctx, TWOFISH_BLOCK_SIZE);

struct pws_file_ctx {
	FILE		*fp;
	unsigned char	*mem;
	size_t		mem_size;
	size_t		mem_pos;
	struct twofish_cbc_ctx cipher_ctx;
	struct hmac_sha256_ctx hmac_ctx;
	struct pws3_file *pws_file;
	uint32_t	n_iter;
};

static int	empty_groups_cmp(struct pws3_field *, struct pws3_field *);
static int	record_cmp(struct pws3_record *, struct pws3_record *);
RB_PROTOTYPE_STATIC(empty_groups_tree, pws3_field, tree_entry, empty_groups_cmp)
RB_PROTOTYPE_STATIC(records_tree, pws3_record, tree_entry, record_cmp)

RB_GENERATE_STATIC(empty_groups_tree, pws3_field, tree_entry, empty_groups_cmp)

RB_GENERATE_STATIC(records_tree, pws3_record, tree_entry, record_cmp)

static int
empty_groups_cmp(struct pws3_field *field1, struct pws3_field *field2)
{
	PWS_ASSERT(pws3_field_is_header(field1) &&
	    pws3_field_is_header(field2));
	PWS_ASSERT((pws3_field_get_type(field1) ==
	    PWS3_HEADER_FIELD_EMPTY_GROUPS) &&
	    (pws3_field_get_type(field2) == PWS3_HEADER_FIELD_EMPTY_GROUPS));

	return (strcmp(pws3_field_get_text(field1),
	    pws3_field_get_text(field2)));
}

static int
record_cmp(struct pws3_record *record1, struct pws3_record *record2)
{
	struct pws3_field	*uuid_field1;
	struct pws3_field	*uuid_field2;

	uuid_field1 = pws3_record_get_field(record1, PWS3_RECORD_FIELD_UUID);
	uuid_field2 = pws3_record_get_field(record2, PWS3_RECORD_FIELD_UUID);
	PWS_ASSERT((uuid_field1 != NULL) && (uuid_field2 != NULL));

	return (memcmp(pws3_field_get_uuid(uuid_field1),
	    pws3_field_get_uuid(uuid_field2), PWS3_UUID_SIZE));
}

static void
pws_set_system_error(struct pws3_file *pws_file, enum pws_error_code code,
    int errnum, const char *fmt, ...)
{
	char	system_error_buf[4096] = "";
	size_t	system_error_len;
	int	error_len;
	va_list	args;
	va_list	args2;

	pws_file->error.code = code;
	pws_file->error.errnum = errnum;

	strerror_r(errnum, system_error_buf, sizeof (system_error_buf) - 1);
	system_error_len = strlen(system_error_buf);

	pws_free(pws_file->error.msg, (pws_file->error.msg != NULL) ?
	    strlen(pws_file->error.msg) + 1 : 0);
	if (fmt != NULL) {
		va_start(args, fmt);
		va_copy(args2, args);
		error_len = vsnprintf(NULL, 0, fmt, args);
		pws_file->error.msg = pws_alloc(error_len + 2 +
		    system_error_len + 1);
		if (pws_file->error.msg == NULL) {
			va_end(args2);
			va_end(args);
			return;
		}
		vsnprintf(pws_file->error.msg, error_len + 1, fmt, args2);
		va_end(args2);
		va_end(args);
		strcpy(pws_file->error.msg + error_len, ": ");
		strcpy(pws_file->error.msg + error_len + 2, system_error_buf);
	} else {
		pws_file->error.msg = pws_alloc(system_error_len + 1);
		snprintf(pws_file->error.msg, system_error_len + 1, "%s",
		    system_error_buf);
	}
}

static void
pws_set_error(struct pws3_file *pws_file, enum pws_error_code code,
    const char *fmt, ...)
{
	va_list	args;
	va_list	args2;
	int	error_len;

	pws_file->error.code = code;
	pws_file->error.errnum = 0;

	pws_free(pws_file->error.msg, (pws_file->error.msg != NULL) ?
	    strlen(pws_file->error.msg) + 1 : 0);
	va_start(args, fmt);
	va_copy(args2, args);
	error_len = vsnprintf(NULL, 0, fmt, args);
	pws_file->error.msg = pws_alloc(error_len + 1);
	if (pws_file->error.msg == NULL) {
		va_end(args2);
		va_end(args);
		return;
	}
	vsnprintf(pws_file->error.msg, error_len + 1, fmt, args2);
	va_end(args2);
	va_end(args);
}

static int
read_buf(struct pws_file_ctx *ctx, unsigned char *buf, size_t buf_size)
{
	if (ctx->fp != NULL) {
		if (fread(buf, 1, buf_size, ctx->fp) != buf_size) {
			if (ferror(ctx->fp) != 0) {
				return (-1);
			} else if (feof(ctx->fp) != 0) {
				return (1);
			}
		}
	} else {
		PWS_ASSERT(ctx->mem != NULL);
		if (ctx->mem_size - ctx->mem_pos < buf_size) {
			return (1);
		}
		memcpy(buf, &ctx->mem[ctx->mem_pos], buf_size);
		ctx->mem_pos += buf_size;
	}

	return (0);
}

static int
write_buf(struct pws_file_ctx *ctx, const unsigned char *buf, size_t buf_size)
{
	size_t		remaining;
	unsigned char	*tmp;

	if (ctx->fp != NULL) {
		if (fwrite(buf, 1, buf_size, ctx->fp) != buf_size) {
			return (-1);
		}
		if (fflush(ctx->fp) != 0) {
			return (-1);
		}
	} else {
		remaining = ctx->mem_size - ctx->mem_pos;
		if (remaining < buf_size) {
			tmp = pws_realloc(ctx->mem, ctx->mem_size +
			    (buf_size - remaining));
			if (tmp == NULL) {
				return (-1);
			}
			ctx->mem = tmp;
			ctx->mem_size += (buf_size - remaining);
		}
		memcpy(&ctx->mem[ctx->mem_pos], buf, buf_size);
		ctx->mem_pos += buf_size;
	}

	return (0);
}

static void
pws_file_clear(struct pws3_file *pws_file)
{
	size_t			i;
	struct pws3_field	*empty_group_field;
	struct pws3_field	*empty_group_field_tmp;
	struct pws3_record	*record;
	struct pws3_record	*record_tmp;

	for (i = 0x00; i <= 0xff; i++) {
		pws3_field_destroy(pws_file->fields[i]);
		pws_file->fields[i] = NULL;
	}

	RB_FOREACH_SAFE(empty_group_field, empty_groups_tree,
	    pws_file->empty_groups_tree, empty_group_field_tmp) {
		pws3_field_destroy(RB_REMOVE(empty_groups_tree,
		    pws_file->empty_groups_tree, empty_group_field));
	}

	RB_FOREACH_SAFE(record, records_tree, pws_file->records_tree,
	    record_tmp) {
		pws3_record_destroy(RB_REMOVE(records_tree,
		    pws_file->records_tree, record));
	}
}

void
pws3_file_destroy(struct pws3_file *pws_file)
{
	if (pws_file == NULL) {
		return;
	}

	pws_free(pws_file->error.msg, (pws_file->error.msg != NULL) ?
	    strlen(pws_file->error.msg) + 1 : 0);
	pws_file_clear(pws_file);
	pws_free(pws_file->empty_groups_tree,
	    sizeof (struct empty_groups_tree));
	pws_free(pws_file->records_tree, sizeof (struct records_tree));
	pws_free(pws_file, sizeof (struct pws3_file));
}

struct pws3_file *
pws3_file_create(void)
{
	struct pws3_field	*version_field = NULL;
	struct pws3_file	*pws_file = NULL;
	size_t			i;

	/* version field is mandatory */
	version_field = pws3_field_create(1, PWS3_HEADER_FIELD_VERSION);
	if (version_field == NULL) {
		goto err;
	}
	pws3_field_set_uint16(version_field, PWS3_VERSION);

	pws_file = pws_alloc(sizeof (struct pws3_file));
	if (pws_file == NULL) {
		goto err;
	}
	for (i = 0x00; i <= 0xff; i++) {
		pws_file->fields[i] = NULL;
	}
	pws_file->empty_groups_tree = NULL;
	pws_file->records_tree = NULL;
	pws_file->error.errnum = 0;
	pws_file->error.code = 0;
	pws_file->error.msg = NULL;

	pws_file->empty_groups_tree =
	    pws_alloc(sizeof (struct empty_groups_tree));
	if (pws_file->empty_groups_tree == NULL) {
		goto err;
	}
	RB_INIT(pws_file->empty_groups_tree);

	pws_file->records_tree = pws_alloc(sizeof (struct records_tree));
	if (pws_file->records_tree == NULL) {
		goto err;
	}
	RB_INIT(pws_file->records_tree);

	pws3_file_set_header_field(pws_file, version_field);

	return (pws_file);
err:
	pws3_field_destroy(version_field);
	if (pws_file != NULL) {
		pws_free(pws_file->records_tree, sizeof (struct records_tree));
		pws_free(pws_file->empty_groups_tree,
		    sizeof (struct empty_groups_tree));
	}
	pws_free(pws_file, sizeof (struct pws3_file));

	return (NULL);
}

enum pws_error_code
pws3_file_get_error_code(struct pws3_file *pws_file)
{
	return (pws_file->error.code);
}

const char *
pws3_file_get_error_message(struct pws3_file *pws_file)
{
	return ((pws_file->error.msg != NULL) ? pws_file->error.msg : "");
}

static void
stretch_key(unsigned char *stretched_key, uint32_t n_iter, const char *key,
    size_t key_size, const unsigned char *salt, size_t salt_size)
{
	uint32_t	i;
	struct sha256_ctx md_ctx;

	sha256_init(&md_ctx);
	sha256_update(&md_ctx, key_size, (uint8_t *)key);
	sha256_update(&md_ctx, salt_size, salt);
	sha256_digest(&md_ctx, SHA256_DIGEST_SIZE, stretched_key);

	for (i = 0; i < n_iter; i++) {
		sha256_update(&md_ctx, SHA256_DIGEST_SIZE, stretched_key);
		sha256_digest(&md_ctx, SHA256_DIGEST_SIZE, stretched_key);
	}
}

static int
read_metadata(struct pws_file_ctx *ctx, const char *password)
{
	int		retval = -1;
	unsigned char	buf[METADATA_SIZE];
	unsigned char	*p = buf;
	unsigned char	*stretched_key = NULL;
	unsigned char	*key_k = NULL;
	unsigned char	*key_l = NULL;
	int		read_retval;
	unsigned char	salt[SALT_SIZE];
	unsigned char	key_digest[SHA256_DIGEST_SIZE];
	struct sha256_ctx md_ctx;
	struct twofish_ctx cipher_ctx;

	stretched_key = pws_secure_alloc(SHA256_DIGEST_SIZE);
	if (stretched_key == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	key_k = pws_secure_alloc(KEY_SIZE);
	if (key_k == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	key_l = pws_secure_alloc(KEY_SIZE);
	if (key_l == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	read_retval = read_buf(ctx, buf, sizeof (buf));
	if (read_retval == 1) {
		pws_set_error(ctx->pws_file, PWS_ERR_TRUNCATED_FILE,
		    "unexpected end of file");
		goto out;
	} else if (read_retval != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		goto out;
	}

	/* check tag */
	if (memcmp(p, psafe3_tag, sizeof (psafe3_tag)) != 0) {
		pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
		    "unknown filetype");
		goto out;
	}
	p += sizeof (psafe3_tag);

	/* salt */
	memcpy(salt, p, SALT_SIZE);
	p += SALT_SIZE;

	/* iterations */
	memcpy(&ctx->n_iter, p, 4);
	ctx->n_iter = le32toh(ctx->n_iter);
	if ((ctx->n_iter < 1) || (ctx->n_iter > MAX_ITER)) {
		pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
		    "invalid number of iterations: %d", ctx->n_iter);
		goto out;
	}
	p += 4;

	/* verify password */
	stretch_key(stretched_key, ctx->n_iter, password, strlen(password),
	    salt, SALT_SIZE);
	sha256_init(&md_ctx);
	sha256_update(&md_ctx, SHA256_DIGEST_SIZE, stretched_key);
	sha256_digest(&md_ctx, SHA256_DIGEST_SIZE, key_digest);
	if (memcmp(key_digest, p, SHA256_DIGEST_SIZE) != 0) {
		pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
		    "wrong password");
		goto out;
	}
	p += SHA256_DIGEST_SIZE;

	/* decrypt keys */
	twofish_set_key(&cipher_ctx, KEY_SIZE, stretched_key);
	twofish_decrypt(&cipher_ctx, KEY_SIZE, key_k, p);
	p += KEY_SIZE;
	twofish_decrypt(&cipher_ctx, KEY_SIZE, key_l, p);
	p += KEY_SIZE;

	/* set key for decryption */
	twofish_set_key(&ctx->cipher_ctx.ctx, KEY_SIZE, key_k);

	/* set IV */
	CBC_SET_IV(&ctx->cipher_ctx, p);

	/* set key for HMAC */
	HMAC_SET_KEY(&ctx->hmac_ctx, &nettle_sha256, KEY_SIZE, key_l);

	retval = 0;

out:
	pws_secure_free(stretched_key, (stretched_key != NULL) ?
	    SHA256_DIGEST_SIZE : 0);
	pws_secure_free(key_l, (key_l != NULL) ? KEY_SIZE : 0);
	pws_secure_free(key_k, (key_k != NULL) ? KEY_SIZE : 0);

	return (retval);
}

static int
read_block(struct pws_file_ctx *ctx, unsigned char *block)
{
	unsigned char	buf[TWOFISH_BLOCK_SIZE];
	int		read_retval;

	read_retval = read_buf(ctx, buf, sizeof (buf));
	if (read_retval == 1) {
		pws_set_error(ctx->pws_file, PWS_ERR_TRUNCATED_FILE,
		    "unexpected end of file");
		return (-1);
	} else if (read_retval != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		return (-1);
	}

	/* reached the EOF block marking the end of encrypted records */
	if (memcmp(buf, eof_marker, TWOFISH_BLOCK_SIZE) == 0) {
		return (1);
	}

	CBC_DECRYPT(&ctx->cipher_ctx, twofish_decrypt, TWOFISH_BLOCK_SIZE,
	    block, buf);

	return (0);
}

static int
read_field(struct pws_file_ctx *ctx, struct pws3_field **fieldp, int is_header)
{
	int		retval = -1;
	enum pws_data_type data_type;
	struct pws3_field *field = NULL;
	unsigned char	*block_buf = NULL;
	unsigned char	*p;
	int		read_retval;
	unsigned char	*field_buf = NULL;
	uint32_t	field_size;
	size_t		remaining;
	size_t		field_buf_size = 0;
	uint8_t field_type = 0xff;
	time_t		data_time;
	uint32_t	data_uint32;
	uint16_t	data_uint16;
	uint8_t		data_uint8;

	block_buf = pws_secure_alloc(TWOFISH_BLOCK_SIZE);
	if (block_buf == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

next_field:
	p = block_buf;

	/* read first block */
	read_retval = read_block(ctx, block_buf);
	if (read_retval != 0) {
		retval = read_retval;
		goto out;
	}

	/* determine field length */
	memcpy(&field_size, p, 4);
	remaining = field_buf_size = field_size = le32toh(field_size);
	p += 4;
	/* determine field type */
	memcpy(&field_type, p, 1);
	p++;

	/* check for end of header fields or end of record */
	if ((is_header && (field_type == PWS3_HEADER_FIELD_END)) ||
	    (!is_header && (field_type == PWS3_RECORD_FIELD_END))) {
		retval = 1;
		goto out;
	}

	/* skip empty fields */
	if (field_size == 0) {
		goto next_field;
	}

	/* determine data type */
	data_type = pws3_field_get_data_type(&(struct pws3_field){ .is_header =
	    is_header, .field_type = field_type });

	/* make room for a terminating \0 in text fields */
	if (data_type == PWS_DATA_TYPE_TEXT) {
		field_buf_size++;
	}

	/* validate field length */
	switch (data_type) {
	case PWS_DATA_TYPE_UUID:
		if ((field_size != 0) && (field_size != PWS3_UUID_SIZE)) {
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
			    "invalid field length");
			goto out;
		}
		break;
	case PWS_DATA_TYPE_TIME:  /* FALLTHROUGH */
	case PWS_DATA_TYPE_UINT32:
		if ((field_size != 0) && (field_size != 4)) {
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
			    "invalid field length");
			goto out;
		}
		break;
	case PWS_DATA_TYPE_UINT8:
		if ((field_size != 0) && (field_size != 1)) {
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
			    "invalid field length");
			goto out;
		}
		break;
	case PWS_DATA_TYPE_UINT16:
		if ((field_size != 0) && (field_size != 2)) {
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
			    "invalid field length");
			goto out;
		}
		break;
	default:
		/* text or bytes */
		if ((!is_header &&
		    (field_type == PWS3_RECORD_FIELD_PASSWORD) &&
		    (field_buf_size > PWS3_MAX_PASSWORD_LEN)) ||
		    (field_buf_size > PWS3_MAX_FIELD_SIZE)) {
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
			    "invalid field length");
			goto out;
		}
	}

	field = pws3_field_create(is_header, field_type);
	if (field == NULL) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_NO_MEMORY, errno,
		    NULL);
		goto out;
	}

	/* create field */
	if (field_buf_size > 0) {
		if (!is_header && (field_type == PWS3_RECORD_FIELD_PASSWORD)) {
			field_buf = pws_secure_alloc(field_buf_size);
		} else {
			field_buf = pws_alloc(field_buf_size);
		}
		if (field_buf == NULL) {
			pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
			    "out of memory");
			goto out;
		}
		memset(field_buf, 0, field_buf_size);

		memcpy(field_buf, p, MIN(remaining,
		    (size_t)TWOFISH_BLOCK_SIZE - (p - block_buf)));
		remaining -= MIN(remaining,
		    (size_t)TWOFISH_BLOCK_SIZE - (p - block_buf));

		while (remaining > 0) {
			read_retval = read_block(ctx, block_buf);
			if (read_retval != 0) {
				goto out;
			}
			memcpy(field_buf + (field_size - remaining),
			    block_buf, MIN(remaining, TWOFISH_BLOCK_SIZE));
			remaining -= MIN(remaining, TWOFISH_BLOCK_SIZE);
		}

		hmac_sha256_update(&ctx->hmac_ctx, field_size, field_buf);

		switch (data_type) {
		case PWS_DATA_TYPE_UUID:
			retval = pws3_field_set_uuid(field, field_buf);
			break;
		case PWS_DATA_TYPE_TEXT:
			retval = pws3_field_set_text(field, (char *)field_buf);
			break;
		case PWS_DATA_TYPE_TIME:
			memcpy(&data_uint32, field_buf, 4);
			data_time = le32toh(data_uint32);
			retval = pws3_field_set_time(field, data_time);
			break;
		case PWS_DATA_TYPE_UINT8:
			memcpy(&data_uint8, field_buf, 1);
			retval = pws3_field_set_uint8(field, data_uint8);
			break;
		case PWS_DATA_TYPE_UINT16:
			memcpy(&data_uint16, field_buf, 2);
			data_uint16 = le16toh(data_uint16);
			retval = pws3_field_set_uint16(field, data_uint16);
			break;
		case PWS_DATA_TYPE_UINT32:
			memcpy(&data_uint32, field_buf, 4);
			data_uint32 = le32toh(data_uint32);
			retval = pws3_field_set_uint32(field, data_uint32);
			break;
		case PWS_DATA_TYPE_BYTES:
			retval = pws3_field_set_bytes(field, field_buf,
			    field_buf_size);
		}
		if (retval != 0) {
			goto out;
		}
	}

	retval = 0;

out:
	if (!is_header && (field_type == PWS3_RECORD_FIELD_PASSWORD)) {
		pws_secure_free(field_buf, field_buf_size);
	} else {
		pws_free(field_buf, field_buf_size);
	}
	pws_secure_free(block_buf, (block_buf != NULL) ?
	    (size_t)TWOFISH_BLOCK_SIZE : 0);

	if (retval == 0) {
		*fieldp = field;
	} else {
		pws3_field_destroy(field);
	}

	return (retval);
}

static int
read_header(struct pws_file_ctx *ctx)
{
	int		retval;
	struct pws3_field *field = NULL;

	/* the header must start with a version field */
	retval = read_field(ctx, &field, 1);
	if (retval != 0) {
		/* error or end of headers */
		pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
		    "header does not start with a version field");
		return (-1);
	} else if (field->field_type != PWS3_HEADER_FIELD_VERSION) {
		/* header does not start with a version field */
		pws3_field_destroy(field);
		pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
		    "header does not start with a version field");
		return (-1);
	} else if (field->value.uint16 > PWS3_VERSION) {
		/* unsupported database version */
		pws3_field_destroy(field);
		pws_set_error(ctx->pws_file, PWS_ERR_UNSUPPORTED_VERSION,
		    "unsupported database version");
		return (-1);
	}
	pws3_file_set_header_field(ctx->pws_file, field);

	for (;;) {
		retval = read_field(ctx, &field, 1);
		if (retval == 1) {
			/* end of headers */
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_HEADER,
			    "unexpected end of headers");
			break;
		} else if (retval != 0) {
			return (-1);
		}
		pws3_file_set_header_field(ctx->pws_file, field);
	}

	return (0);
}

static int
read_records(struct pws_file_ctx *ctx)
{
	int		retval;
	struct pws3_record *record = NULL;
	struct pws3_field *field = NULL;

	for (;;) {
		/*
		 * a record must consist of at least three fields, instead of
		 * the first field there could also be an EOF marker
		 */
		retval = read_field(ctx, &field, 0);
		if (retval == 1) {
			/* EOF marker */
			retval = 0;
			goto out;
		} else if (retval != 0) {
			/* read error */
			goto out;
		} else if (field->field_type == PWS3_RECORD_FIELD_END) {
			/* empty record */
			retval = -1;
			goto out;
		}

		record = pws3_record_create();
		if (record == NULL) {
			pws_set_system_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
			    errno, NULL);
			goto out;
		}

		pws3_record_set_field(record, field);
		field = NULL;

		/* read the remaining fileds */
		for (;;) {
			retval = read_field(ctx, &field, 0);
			if (retval == 1) {
				/* end of record */
				break;
			} else if (retval != 0) {
				/* read error */
				retval = -1;
				goto out;
			}
			pws3_record_set_field(record, field);
			field = NULL;
		}

		/* check whether UUID is not empty */
		if (pws3_record_get_field(record, PWS3_RECORD_FIELD_UUID) ==
		    NULL) {
			/* record is missing mandatory fields */
			pws_set_error(ctx->pws_file, PWS_ERR_INVALID_RECORD,
			    "record is missing mandatory fields");
			pws3_record_destroy(record);
			retval = -1;
			goto out;
		}

		pws3_file_insert_record(ctx->pws_file, record);
		record = NULL;
	}

out:
	if (retval != 0) {
		pws3_field_destroy(field);
		pws3_record_destroy(record);
	}

	return (retval);
}

static int
verify_checksum(struct pws_file_ctx *ctx)
{
	int		retval;
	unsigned char	hmac_file[SHA256_DIGEST_SIZE];
	unsigned char	hmac[SHA256_DIGEST_SIZE];

	retval = read_buf(ctx, hmac_file, sizeof (hmac_file));
	if (retval == 1) {
		pws_set_error(ctx->pws_file, PWS_ERR_TRUNCATED_FILE,
		    "unexpected end of file");
		return (-1);
	} else if (retval != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		return (-1);
	}

	hmac_sha256_digest(&ctx->hmac_ctx, sizeof (hmac), hmac);
	if (memcmp(hmac_file, hmac, sizeof (hmac_file)) != 0) {
		/* inconsistent database */
		pws_set_error(ctx->pws_file, PWS_ERR_INVALID_CHECKSUM,
		    "checksum failed");
		return (-1);
	}

	return (0);
}

static int
pws3_file_read(struct pws3_file *pws_file, const char *password,
    unsigned char *s, size_t n, FILE *fp)
{
	int		retval = -1;
	struct pws_file_ctx	ctx = {
		.fp = fp,
		.mem = s,
		.mem_size = n,
		.mem_pos = 0,
		.pws_file = pws_file,
	};

	pws_file_clear(pws_file);

	retval = read_metadata(&ctx, password);
	if (retval != 0) {
		goto out;
	}

	retval = read_header(&ctx);
	if (retval != 0) {
		goto out;
	}

	retval = read_records(&ctx);
	if (retval != 0) {
		goto out;
	}

	retval = verify_checksum(&ctx);
	if (retval != 0) {
		goto out;
	}

out:
	if (retval != 0) {
		pws_file_clear(ctx.pws_file);
	}

	return (retval);
}

int
pws3_file_read_mem(struct pws3_file *pws_file, const char *password,
    unsigned char *s, size_t n)
{
	return (pws3_file_read(pws_file, password, s, n, NULL));
}

int
pws3_file_read_stream(struct pws3_file *pws_file, const char *password,
    FILE *fp)
{
	return (pws3_file_read(pws_file, password, NULL, 0, fp));
}

static int
write_metadata(struct pws_file_ctx *ctx, const char *password)
{
	int		retval = -1;
	unsigned char	*stretched_key = NULL;
	unsigned char	*key_k = NULL;
	unsigned char	*key_l = NULL;
	unsigned char	metadata[METADATA_SIZE];
	unsigned char	*p = metadata;
	unsigned char	*salt;
	uint32_t	n_iter_le;
	struct sha256_ctx md_ctx;
	unsigned char	*b1;
	unsigned char	*b3;
	unsigned char	*iv;
	struct twofish_ctx cipher_ctx;

	stretched_key = pws_secure_alloc(SHA256_DIGEST_SIZE);
	if (stretched_key == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	key_k = pws_secure_alloc(KEY_SIZE);
	if (key_k == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	key_l = pws_secure_alloc(KEY_SIZE);
	if (key_l == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	/* generate new keys */
	if (pws_random_bytes(key_k, KEY_SIZE) != 0) {
		pws_set_error(ctx->pws_file, PWS_ERR_GENERIC_ERROR,
		    "failed to generate key");
		goto out;
	}

	if (pws_random_bytes(key_l, KEY_SIZE) != 0) {
		pws_set_error(ctx->pws_file, PWS_ERR_GENERIC_ERROR,
		    "failed to generate key");
		goto out;
	}

	/* tag */
	memcpy(p, psafe3_tag, sizeof (psafe3_tag));
	p += sizeof (psafe3_tag);

	/* generate new salt */
	salt = p;
	if (pws_random_bytes(salt, SALT_SIZE) != 0) {
		pws_set_error(ctx->pws_file, PWS_ERR_GENERIC_ERROR,
		    "failed to generate salt");
		goto out;
	}
	p += SALT_SIZE;

	/* number of iterations */
	n_iter_le = htole32(ctx->n_iter);
	memcpy(p, &n_iter_le, 4);
	p += 4;

	/* stretch, hash password */
	stretch_key(stretched_key, ctx->n_iter, password, strlen(password),
	    salt, SALT_SIZE);
	sha256_init(&md_ctx);
	sha256_update(&md_ctx, SHA256_DIGEST_SIZE, stretched_key);
	sha256_digest(&md_ctx, SHA256_DIGEST_SIZE, p);
	p += SHA256_DIGEST_SIZE;

	b1 = p;
	p += KEY_SIZE;

	b3 = p;
	p += KEY_SIZE;

	/* generate IV */
	iv = p;
	if (pws_random_bytes(iv, TWOFISH_BLOCK_SIZE) != 0) {
		pws_set_error(ctx->pws_file, PWS_ERR_GENERIC_ERROR,
		    "failed to generate IV");
		goto out;
	}

	/* encrypt keys */
	twofish_set_key(&cipher_ctx, KEY_SIZE, stretched_key);
	twofish_encrypt(&cipher_ctx, KEY_SIZE, b1, key_k);
	twofish_encrypt(&cipher_ctx, KEY_SIZE, b3, key_l);

	/* set key for decryption */
	twofish_set_key(&ctx->cipher_ctx.ctx, KEY_SIZE, key_k);

	/* set IV */
	CBC_SET_IV(&ctx->cipher_ctx, p);

	/* set key for HMAC */
	hmac_sha256_set_key(&ctx->hmac_ctx, KEY_SIZE, key_l);

	/* write metadata */
	if (write_buf(ctx, metadata, sizeof (metadata)) != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		retval = -1;
		goto out;
	}

	retval = 0;

out:
	pws_secure_free(key_k, (key_k != NULL) ? KEY_SIZE : 0);
	pws_secure_free(key_l, (key_l != NULL) ? KEY_SIZE : 0);
	pws_secure_free(stretched_key, (stretched_key != NULL) ?
	    SHA256_DIGEST_SIZE : 0);

	return (retval);
}

static int
write_block(struct pws_file_ctx *ctx, unsigned char *block)
{
	unsigned char	buf[TWOFISH_BLOCK_SIZE];

	CBC_ENCRYPT(&ctx->cipher_ctx, twofish_encrypt, sizeof (buf), buf,
	    block);

	if (write_buf(ctx, buf, sizeof (buf)) != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		return (-1);
	}

	return (0);
}

static int
write_field(struct pws_file_ctx *ctx, struct pws3_field *field)
{
	int		retval = -1;
	unsigned char	*buf = NULL;
	unsigned char	*p;
	unsigned char	*field_data;
	enum pws_data_type data_type;
	size_t		blocks = (field->size + 4 + 1) / TWOFISH_BLOCK_SIZE +
	    ((field->size + 4 + 1) % TWOFISH_BLOCK_SIZE != 0);
	size_t		i;
	size_t		j;
	uint32_t	len_le;

	buf = pws_secure_alloc(TWOFISH_BLOCK_SIZE);
	if (buf == NULL) {
		pws_set_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
		    "out of memory");
		goto out;
	}

	data_type = pws3_field_get_data_type(field);

	for (i = 0, j = 0; i < blocks; i++) {
		p = field_data = buf;
		if (pws_random_bytes(buf, TWOFISH_BLOCK_SIZE) != 0) {
			pws_set_error(ctx->pws_file, PWS_ERR_GENERIC_ERROR,
			    "could not get random numbers");
			goto out;
		}

		/* the first block of the field contains the length and type */
		if (i == 0) {
			len_le = htole32(field->size);
			memcpy(p, &len_le, 4);
			p += 4;

			*p = field->field_type;
			p++;
			field_data = p;
		}

		while ((j < field->size) &&
		    (p - buf < (ptrdiff_t)TWOFISH_BLOCK_SIZE)) {
			switch (data_type) {
			case PWS_DATA_TYPE_UINT8:
				*p = field->value.uint8;
				break;
			case PWS_DATA_TYPE_UINT16:
				/* little endian */
				*p = (field->value.uint16 >> (8 * j)) & 0xff;
				break;
			case PWS_DATA_TYPE_TIME: /* FALLTHROUGH */
			case PWS_DATA_TYPE_UINT32:
				/* little endian */
				*p = (field->value.uint32 >> (8 * j)) & 0xff;
				break;
			case PWS_DATA_TYPE_TEXT:
				*p = field->value.text[j];
				break;
			case PWS_DATA_TYPE_UUID:
				*p = field->value.uuid[j];
				break;
			default:
				*p = field->value.bytes[j];
			}

			p++;
			j++;
		}

		hmac_sha256_update(&ctx->hmac_ctx, p - field_data, field_data);

		retval = write_block(ctx, buf);
		if (retval != 0) {
			goto out;
		}
	}

	retval = 0;

out:
	pws_secure_free(buf, (buf != NULL) ? TWOFISH_BLOCK_SIZE : 0);

	return (retval);
}

static int
write_header(struct pws_file_ctx *ctx)
{
	int		retval = -1;
	size_t		i;
	struct pws3_field *version_field;
	struct pws3_field *field = NULL;
	struct pws3_field *end_field = NULL;

	version_field = pws3_file_get_header_field(ctx->pws_file,
	    PWS3_HEADER_FIELD_VERSION);
	if (version_field == NULL) {
		/* add mandatory version header version_field if necessary */
		version_field = pws3_field_create(1, PWS3_HEADER_FIELD_VERSION);
		if (version_field == NULL) {
			pws_set_system_error(ctx->pws_file, PWS_ERR_NO_MEMORY,
			    errno, NULL);
			goto out;
		}
		pws3_field_set_uint16(version_field, PWS3_VERSION);
		pws3_file_set_header_field(ctx->pws_file, version_field);
	}
	retval = write_field(ctx, version_field);
	if (retval != 0) {
		goto out;
	}

	for (i = 0x01; i < 0xff; i++) {
		if (ctx->pws_file->fields[i] != NULL) {
			retval = write_field(ctx, ctx->pws_file->fields[i]);
			if (retval != 0) {
				goto out;
			}
		}
	}

	RB_FOREACH(field, empty_groups_tree, ctx->pws_file->empty_groups_tree) {
		retval = write_field(ctx, field);
		if (retval != 0) {
			goto out;
		}
	}

	end_field = pws3_field_create(1, PWS3_HEADER_FIELD_END);
	retval = write_field(ctx, end_field);
	if (retval != 0) {
		goto out;
	}

out:
	pws3_field_destroy(end_field);

	return (retval);
}

static int
write_records(struct pws_file_ctx *ctx)
{
	int		retval = -1;
	struct pws3_field *end_field = NULL;
	size_t		i;
	struct pws3_record *record;

	end_field = pws3_field_create(0, PWS3_RECORD_FIELD_END);
	if (end_field == NULL) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_NO_MEMORY, errno,
		    NULL);
		goto out;
	}

	RB_FOREACH(record, records_tree, ctx->pws_file->records_tree) {
		/* record fields */
		for (i = 0x01; i < 0xff; i++) {
			if (record->fields[i] != NULL) {
				retval = write_field(ctx, record->fields[i]);
				if (retval != 0) {
					goto out;
				}
			}
		}

		/* end of entry marker */
		retval = write_field(ctx, end_field);
		if (retval != 0) {
			goto out;
		}
	}

	/* end of file marker */
	if (write_buf(ctx, eof_marker, sizeof (eof_marker)) != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		retval = -1;
		goto out;
	}

	retval = 0;

out:
	pws3_field_destroy(end_field);

	return (retval);
}

static int
write_checksum(struct pws_file_ctx *ctx)
{
	unsigned char	hmac[SHA256_DIGEST_SIZE];

	hmac_sha256_digest(&ctx->hmac_ctx, sizeof (hmac), hmac);

	if (write_buf(ctx, hmac, sizeof (hmac)) != 0) {
		pws_set_system_error(ctx->pws_file, PWS_ERR_IO_ERROR, errno,
		    NULL);
		return (-1);
	}

	return (0);
}

static int
pws3_file_write(struct pws3_file *pws_file, const char *password,
    uint32_t n_iter, unsigned char **memp, size_t *mem_sizep, FILE *fp)
{
	int		retval = -1;
	struct pws_file_ctx	ctx = {
		.fp = fp,
		.pws_file = pws_file,
		.n_iter = n_iter
	};

	retval = write_metadata(&ctx, password);
	if (retval != 0) {
		goto out;
	}

	retval = write_header(&ctx);
	if (retval != 0) {
		goto out;
	}

	retval = write_records(&ctx);
	if (retval != 0) {
		goto out;
	}

	retval = write_checksum(&ctx);
	if (retval != 0) {
		goto out;
	}

	if (memp != NULL) {
		*memp = ctx.mem;
		*mem_sizep = ctx.mem_size;
	}

out:
	if (retval != 0) {
		pws_free(ctx.mem, ctx.mem_size);
	}

	return (retval);
}

int
pws3_file_write_mem(struct pws3_file *pws_file, const char *password,
    uint32_t n_iter, unsigned char **memp, size_t *mem_sizep)
{
	PWS_ASSERT(memp != NULL);
	PWS_ASSERT(mem_sizep != NULL);

	return (pws3_file_write(pws_file, password, n_iter, memp, mem_sizep,
	    NULL));
}

int
pws3_file_write_stream(struct pws3_file *pws_file, const char *password,
    uint32_t n_iter, FILE *fp)
{
	PWS_ASSERT(fp != NULL);

	return (pws3_file_write(pws_file, password, n_iter, NULL, NULL, fp));
}

void
pws3_file_set_header_field(struct pws3_file *pws_file, struct pws3_field *field)
{
	PWS_ASSERT(pws3_field_is_header(field));
	PWS_ASSERT((pws3_field_get_data_type(field) != PWS_DATA_TYPE_TEXT) ||
	    (field->value.text != NULL));
	PWS_ASSERT((pws3_field_get_data_type(field) != PWS_DATA_TYPE_BYTES) ||
	    (field->value.bytes != NULL));

	if (field->field_type == PWS3_HEADER_FIELD_EMPTY_GROUPS) {
		pws3_file_insert_empty_group(pws_file, field);
		return;
	}

	pws3_field_destroy(pws3_file_remove_header_field(pws_file,
	    field->field_type));
	pws_file->fields[field->field_type] = field;
}

struct pws3_field *
pws3_file_get_header_field(struct pws3_file *pws_file, uint8_t field_type)
{
	if (field_type == PWS3_HEADER_FIELD_EMPTY_GROUPS) {
		return (pws3_file_first_empty_group(pws_file));
	}

	return (pws_file->fields[field_type]);
}

struct pws3_field *
pws3_file_remove_header_field(struct pws3_file *pws_file, uint8_t field_type)
{
	struct pws3_field	*field;

	if (field_type == PWS3_HEADER_FIELD_EMPTY_GROUPS) {
		return (NULL);
	}

	field = pws3_file_get_header_field(pws_file, field_type);
	pws_file->fields[field_type] = NULL;

	return (field);
}

void
pws3_file_insert_empty_group(struct pws3_file *pws_file,
    struct pws3_field *field)
{
	const char	*group_name;

	PWS_ASSERT(pws3_field_is_header(field));
	PWS_ASSERT(pws3_field_get_type(field) ==
	    PWS3_HEADER_FIELD_EMPTY_GROUPS);

	group_name = pws3_field_get_text(field);
	pws3_field_destroy(pws3_file_remove_empty_group(pws_file, group_name));
	RB_INSERT(empty_groups_tree, pws_file->empty_groups_tree, field);
}

struct pws3_field *
pws3_file_get_empty_group(struct pws3_file *pws_file, const char *group_name)
{
	return (RB_FIND(empty_groups_tree, pws_file->empty_groups_tree,
	    (&(struct pws3_field){ .is_header = 1,
	    .field_type = PWS3_HEADER_FIELD_EMPTY_GROUPS,
	    .value.text = (char *)group_name })));
}

struct pws3_field *
pws3_file_remove_empty_group(struct pws3_file *pws_file, const char *group_name)
{
	struct pws3_field *field;

	field = RB_FIND(empty_groups_tree, pws_file->empty_groups_tree,
	    (&(struct pws3_field){ .is_header = 1,
	    .field_type = PWS3_HEADER_FIELD_EMPTY_GROUPS,
	    .value.text = (char *)group_name }));
	if (field != NULL) {
		RB_REMOVE(empty_groups_tree, pws_file->empty_groups_tree,
		    field);
	}

	return (field);
}

struct pws3_field *
pws3_file_first_empty_group(struct pws3_file *pws_file)
{
	return (RB_MIN(empty_groups_tree, pws_file->empty_groups_tree));
}

struct pws3_field *
pws3_file_last_empty_group(struct pws3_file *pws_file)
{
	return (RB_MAX(empty_groups_tree, pws_file->empty_groups_tree));
}

struct pws3_field *
pws3_file_next_empty_group(struct pws3_file *pws_file, struct pws3_field *field)
{
	return (RB_NEXT(empty_groups_tree, pws_file->empty_groups_tree, field));
}

struct pws3_field *
pws3_file_prev_empty_group(struct pws3_file *pws_file, struct pws3_field *field)
{
	return (RB_PREV(empty_groups_tree, pws_file->empty_groups_tree, field));
}

void
pws3_file_insert_record(struct pws3_file *pws_file, struct pws3_record *record)
{
	struct pws3_field	*uuid_field;
	const unsigned char	*uuid;

	uuid_field = pws3_record_get_field(record, PWS3_RECORD_FIELD_UUID);
	PWS_ASSERT(uuid_field != NULL);
	uuid = pws3_field_get_uuid(uuid_field);

	/* replace existing record */
	pws3_record_destroy(pws3_file_remove_record(pws_file, uuid));

	RB_INSERT(records_tree, pws_file->records_tree, record);
}

struct pws3_record *
pws3_file_get_record(struct pws3_file *pws_file,
    const unsigned char uuid[static PWS3_UUID_SIZE])
{
	struct pws3_field uuid_field = {
		.is_header = 0,
		.field_type = PWS3_RECORD_FIELD_UUID
	};
	struct pws3_record search_record = {
		.fields[PWS3_RECORD_FIELD_UUID] = &uuid_field
	};

	memcpy(uuid_field.value.uuid, uuid, PWS3_UUID_SIZE);

	return (RB_FIND(records_tree, pws_file->records_tree, &search_record));
}

struct pws3_record *
pws3_file_remove_record(struct pws3_file *pws_file,
    const unsigned char uuid[static PWS3_UUID_SIZE])
{
	struct pws3_record *record;

	record = pws3_file_get_record(pws_file, uuid);
	if (record != NULL) {
		RB_REMOVE(records_tree, pws_file->records_tree, record);
	}

	return (record);
}

struct pws3_record *
pws3_file_first_record(struct pws3_file *pws_file)
{
	return (RB_MIN(records_tree, pws_file->records_tree));
}

struct pws3_record *
pws3_file_last_record(struct pws3_file *pws_file)
{
	return (RB_MAX(records_tree, pws_file->records_tree));
}

struct pws3_record *
pws3_file_next_record(struct pws3_file *pws_file, struct pws3_record *record)
{
	return (RB_NEXT(records_tree, pws_file->records_tree, record));
}

struct pws3_record *
pws3_file_prev_record(struct pws3_file *pws_file, struct pws3_record *record)
{
	return (RB_PREV(records_tree, pws_file->records_tree, record));
}