--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/pws-file.c	Tue Feb 10 11:29:54 2015 +0100
@@ -0,0 +1,1502 @@
+/*
+ * 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));
+}