Mercurial > projects > libpws
changeset 0:d541e748cfd8
Initial revision
| author | Guido Berhoerster <guido+libpws@berhoerster.name> |
|---|---|
| date | Tue, 10 Feb 2015 11:29:54 +0100 |
| parents | |
| children | e1309515d111 |
| files | Makefile compat.h compat/endian.c compat/endian.h compat/getentropy.c compat/getentropy.h compat/pws-compat.h compat/tree.h deps.sed include/pws.h pws-field.c pws-file.c pws-internal.h pws-random.c pws-record.c pws.c |
| diffstat | 16 files changed, 3703 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Makefile Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,176 @@ +# +# 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. +# + +PACKAGE = libpws +VERSION = 1.0.0 +DISTNAME := $(PACKAGE)-$(VERSION) + +# gcc, clang, icc, Sun/Solaris Studio +CC := $(CC) -std=c99 +COMPILE.c = $(CC) $(CFLAGS) $(XCFLAGS) $(CPPFLAGS) $(XCPPFLAGS) $(TARGET_ARCH) -c +# gcc, clang, icc +MAKEDEPEND.c = $(CC) -MM $(CFLAGS) $(XCFLAGS) $(CPPFLAGS) $(XCPPFLAGS) +# Sun/Solaris Studio +#MAKEDEPEND.c = $(CC) -xM1 $(CFLAGS) $(XCFLAGS) $(CPPFLAGS) $(XCPPFLAGS) +# X makedepend +#MAKEDEPEND.c = makedepend -f- -Y -- $(CFLAGS) $(XCFLAGS) $(CPPFLAGS) $(XCPPFLAGS) -- +LINK.c = $(CC) $(CFLAGS) $(XCFLAGS) $(CPPFLAGS) $(XCPPFLAGS) $(LDFLAGS) $(XLDFLAGS) $(TARGET_ARCH) +LINK.o = $(CC) $(LDFLAGS) $(XLDFLAGS) $(TARGET_ARCH) +AR := ar +RANLIB := ranlib +INSTALL := install +INSTALL.exec := $(INSTALL) -D -m 0755 +INSTALL.lib := $(INSTALL) -D -m 0644 +INSTALL.data := $(INSTALL) -D -m 0644 +PAX := pax +GZIP := gzip +SED := sed + +DESTDIR ?= +prefix ?= /usr/local +bindir ?= $(prefix)/bin +libdir ?= $(prefix)/lib +includedir ?= $(prefix)/include +datadir ?= $(prefix)/share + +OS_NAME := $(shell uname -s) +OS_RELEASE := $(shell uname -r) + +ifeq ($(OS_NAME),Linux) + HAVE_ARC4RANDOM ?= 0 + HAVE_ENDIAN_H ?= 1 + HAVE_SYS_ENDIAN_H ?= 0 + HAVE_GETENTROPY ?= 0 + HAVE_SYS_TREE_H ?= 0 +else ifneq ($(findstring $(OS_NAME),FreeBSD DragonFly),) + HAVE_ARC4RANDOM ?= 1 + HAVE_ENDIAN_H ?= 0 + HAVE_SYS_ENDIAN_H ?= 1 + HAVE_GETENTROPY ?= 0 + HAVE_SYS_TREE_H ?= 1 +else ifeq ($(OS_NAME),NetBSD) + HAVE_ARC4RANDOM ?= 1 + HAVE_ENDIAN_H ?= 0 + HAVE_SYS_ENDIAN_H ?= 1 + HAVE_GETENTROPY ?= 0 + HAVE_SYS_TREE_H ?= 1 +else ifeq ($(OS_NAME),OpenBSD) + HAVE_ARC4RANDOM ?= 1 + HAVE_ENDIAN_H ?= 0 + HAVE_SYS_ENDIAN_H ?= 1 + HAVE_GETENTROPY ?= 1 + HAVE_SYS_TREE_H ?= 1 +else ifeq ($(OS_NAME),SunOS) + HAVE_ARC4RANDOM ?= 0 + HAVE_ENDIAN_H ?= 0 + HAVE_SYS_ENDIAN_H ?= 0 + HAVE_GETENTROPY ?= 0 + HAVE_SYS_TREE_H ?= 0 +else + HAVE_ARC4RANDOM ?= 0 + HAVE_ENDIAN_H ?= 0 + HAVE_SYS_ENDIAN_H ?= 0 + HAVE_GETENTROPY ?= 0 + HAVE_SYS_TREE_H ?= 0 +endif + +LIBPWS_OBJS = pws.o \ + pws-file.o \ + pws-record.o \ + pws-field.o \ + pws-random.o +LIBPWS_LIB = $(PACKAGE).a +LIBPWS_LIB_MEMBERS = $(LIBPWS_OBJS:%.o=$(LIBPWS_LIB)(%.o)) + +OBJS = $(LIBPWS_OBJS) + +.DEFAULT_TARGET = all + +.PHONY: all clean clobber dist install + +all: $(LIBPWS_LIB) + +XCPPFLAGS = -Iinclude +ifeq ($(HAVE_ARC4RANDOM),1) + XCPPFLAGS += -DHAVE_ARC4RANDOM +endif +ifeq ($(HAVE_ENDIAN_H),1) + XCPPFLAGS += -DHAVE_ENDIAN_H +else ifeq ($(HAVE_SYS_ENDIAN_H),1) + XCPPFLAGS += -DHAVE_SYS_ENDIAN_H +else + LIBPWS_OBJS += compat/endian.o +endif +ifeq ($(HAVE_GETENTROPY),1) + XCPPFLAGS += -DHAVE_GETENTROPY +else + LIBPWS_OBJS += compat/getentropy.o +endif +ifeq ($(HAVE_SYS_TREE_H),1) + XCPPFLAGS += -DHAVE_SYS_TREE_H +endif +ifneq ($(findstring $(OS_NAME),FreeBSD DragonFly OpenBSD),) + XCPPFLAGS += -I/usr/local/include + XLDFLAGS += -L/usr/local/lib +else ifeq ($(OS_NAME),NetBSD) + XCPPFLAGS += -I/usr/pkg/include + XLDFLAGS += -L/usr/pkg/lib +endif +ifeq ($(OS_NAME),SunOS) + XCPPFLAGS += -I/usr/xpg4/include -D__EXTENSIONS__ + XLDFLAGS += -L/usr/xpg4/lib -R/usr/xpg4/lib +endif +ifeq ($(findstring $(OS_NAME),FreeBSD DragonFly NetBSD OpenBSD),) + XCPPFLAGS += -D_XOPEN_SOURCE=600 +endif + +$(LIBPWS_LIB): $(LIBPWS_LIB_MEMBERS) + +%.o: %.c + $(MAKEDEPEND.c) $< | $(SED) -f deps.sed >$*.d + $(COMPILE.c) -o $@ $< + +(%): % + $(AR) $(ARFLAGS) $@ $< + $(RANLIB) $@ + +install: + for header in include/*.h; do \ + $(INSTALL.data) $${header} \ + "$(DESTDIR)$(includedir)/$(PACKAGE)/$${header##*/}"; \ + done + $(INSTALL.lib) $(LIBPWS_LIB) \ + "$(DESTDIR)$(libdir)/$(notdir $(LIBPWS_LIB))" + +clean: + rm -f $(LIBPWS_LIB) $(LIBPWS_OBJS) + +clobber: clean + rm -f $(patsubst %.o,%.d,$(OBJS)) + +dist: clobber + $(PAX) -w -x ustar -s ',.*/\..*,,' -s ',./[^/]*\.tar\.gz,,' \ + -s ',^\.$$,,' -s ',\./,$(DISTNAME)/,' . | \ + $(GZIP) > $(DISTNAME).tar.gz + +-include $(patsubst %.o,%.d,$(OBJS))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,47 @@ +/* + * 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. + */ + +#ifndef COMPAT_H +#define COMPAT_H + +#include "compat/pws-compat.h" + +/* for FreeBSD getline() */ +#define _WITH_GETLINE + +/* for glibc endian.h */ +#define _BSD_SOURCE + +#if !defined(HAVE_ENDIAN_H) && !defined(HAVE_SYS_ENDIAN_H) +#include "compat/endian.h" +#endif /* !defined(HAVE_ENDIAN_H) && !defined(HAVE_SYS_ENDIAN_H) */ + +#ifndef HAVE_GETENTROPY +#include "compat/getentropy.h" +#endif /* !HAVE_GETENTROPY */ + +#ifndef HAVE_SYS_TREE_H +#include "compat/tree.h" +#endif /* !HAVE_SYS_TREE_H */ + +#endif /* COMPAT_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat/endian.c Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,93 @@ +/* + * Copyright (C) 2015 Guido Berhoerster <guido+pws@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 <arpa/inet.h> + +#include "pws-compat.h" +#include "endian.h" + +uint16_t +le16toh(uint16_t little16) +{ + unsigned char *b = (unsigned char *)&little16; + + return ((b[0] << 0) | (b[1] << 8)); +} + +uint16_t +htole16(uint16_t host16) +{ + uint16_t little16; + unsigned char *b = (unsigned char *)&little16; + + b[0] = (unsigned char)(host16 >> 0); + b[1] = (unsigned char)(host16 >> 8); + + return (little16); +} + +uint32_t +le32toh(uint32_t little32) +{ + unsigned char *b = (unsigned char *)&little32; + + return ((b[0] << 0) | (b[1] << 8) | (b[2] << 16) | (b[3] << 24)); +} + +uint32_t +htole32(uint32_t host32) +{ + uint32_t little32; + unsigned char *b = (unsigned char *)&little32; + + b[0] = (unsigned char)(host32 >> 0); + b[1] = (unsigned char)(host32 >> 8); + b[2] = (unsigned char)(host32 >> 16); + b[3] = (unsigned char)(host32 >> 24); + + return (little32); +} + +uint16_t +be16toh(uint16_t big16) +{ + return (ntohs(big16)); +} + +uint16_t +htobe16(uint16_t host16) +{ + return (htons(host16)); +} + +uint32_t +be32toh(uint32_t big32) +{ + return (ntohl(big32)); +} + +uint32_t +htobe32(uint32_t host32) +{ + return (htonl(host32)); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat/endian.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,38 @@ +/* + * 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. + */ + +#ifndef ENDIAN_H +#define ENDIAN_H + +#include <stdint.h> + +uint16_t le16toh(uint16_t); +uint16_t htole16(uint16_t); +uint32_t le32toh(uint32_t); +uint32_t htole32(uint32_t); +uint16_t be16toh(uint16_t); +uint16_t htobe16(uint16_t); +uint32_t be32toh(uint32_t); +uint32_t htobe32(uint32_t); + +#endif /* !ENDIAN_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat/getentropy.c Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,112 @@ +/* + * 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. + */ + +/* needed for syscall(2) on Linux */ +#define _GNU_SOURCE + +/* Linux >= 3.17 has getrandom(2) system call */ +#ifdef __linux__ +#include <unistd.h> +#include <sys/syscall.h> +#include <linux/random.h> +#ifdef SYS_getrandom +#define HAVE_GETRANDOM +#endif /* SYS_getrandom */ +#endif /* __linux__ */ +/* + * on unknown Unix systems without getentropy(2) or Linux without getrandom(2) + * fall back to * reading from /dev/(u)random + */ +#ifndef HAVE_GETRANDOM +#include <stdio.h> +#ifndef RANDOM_DEVICE +#ifdef __linux__ +/* on Linux /dev/urandom should be good enough */ +#define RANDOM_DEVICE "/dev/urandom" +#else /* __linux__ */ +/* on unknown Unix systems use the possibly blocking /dev/random */ +#define RANDOM_DEVICE "/dev/random" +#endif /* __linux__ */ +#endif /* !RANDOM_DEVICE */ +#endif /* !HAVE_GETRANDOM */ +#include <errno.h> + +#include "pws-compat.h" + +#ifdef HAVE_GETRANDOM +static int +getentropy_linux_getrandom(void *buf, size_t buf_len) +{ + int retval; + + retval = syscall(SYS_getrandom, buf, buf_len, 0); + if (retval < 0) { + return (-1); + } else if ((size_t)retval != buf_len) { + errno = EIO; + return (-1); + } + + return (0); +} +#else +static int +getentropy_dev_random(void *buf, size_t buf_len) +{ + FILE *fp; + int saved_errno; + + fp = fopen(RANDOM_DEVICE, "r"); + if (fp == NULL) { + return (-1); + } + if (fread(buf, 1, buf_len, fp) != buf_len) { + saved_errno = errno; + fclose(fp); + errno = saved_errno; + return (-1); + } + if (fclose(fp) != 0) { + return (-1); + } + + return (0); +} +#endif /* HAVE_GETRANDOM */ + +int +getentropy(void *buf, size_t buf_len) +{ + if (buf_len > 256) { + errno = EIO; + return (-1); + } + + return ( +#ifdef HAVE_GETRANDOM + getentropy_linux_getrandom( +#else /* HAVE_GETRANDOM */ + getentropy_dev_random( +#endif /* HAVE_GETRANDOM */ + buf, buf_len)); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat/getentropy.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,31 @@ +/* + * 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. + */ + +#ifndef GETENTROPY_H +#define GETENTROPY_H + +#include <stddef.h> + +int getentropy(void *, size_t); + +#endif /* !GETENTROPY_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat/pws-compat.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,42 @@ +/* + * 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. + */ + +#ifndef PWS_COMPAT_H +#define PWS_COMPAT_H + +#if !defined(HAVE_ENDIAN_H) && !defined(HAVE_SYS_ENDIAN_H) +#define le16toh pws_compat_le16toh +#define htole16 pws_compat_htole16 +#define le32toh pws_compat_le32toh +#define htole32 pws_compat_htole32 +#define be16toh pws_compat_be16toh +#define htobe16 pws_compat_htobe16 +#define be32toh pws_compat_be32toh +#define htobe32 pws_compat_htobe32 +#endif /* !defined(HAVE_ENDIAN_H) && !defined(HAVE_SYS_ENDIAN_H) */ + +#ifndef HAVE_GETENTROPY +#define getentropy pws_compat_getentropy +#endif /* !HAVE_GETENTROPY */ + +#endif /* PWS_COMPAT_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/compat/tree.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,748 @@ +/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */ +/* + * Copyright 2002 Niels Provos <provos@citi.umich.edu> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef _SYS_TREE_H_ +#define _SYS_TREE_H_ + +/* + * This file defines data structures for different types of trees: + * splay trees and red-black trees. + * + * A splay tree is a self-organizing data structure. Every operation + * on the tree causes a splay to happen. The splay moves the requested + * node to the root of the tree and partly rebalances it. + * + * This has the benefit that request locality causes faster lookups as + * the requested nodes move to the top of the tree. On the other hand, + * every lookup causes memory writes. + * + * The Balance Theorem bounds the total access time for m operations + * and n inserts on an initially empty tree as O((m + n)lg n). The + * amortized cost for a sequence of m accesses to a splay tree is O(lg n); + * + * A red-black tree is a binary search tree with the node color as an + * extra attribute. It fulfills a set of conditions: + * - every search path from the root to a leaf consists of the + * same number of black nodes, + * - each red node (except for the root) has a black parent, + * - each leaf node is black. + * + * Every operation on a red-black tree is bounded as O(lg n). + * The maximum height of a red-black tree is 2lg (n+1). + */ + +#define SPLAY_HEAD(name, type) \ +struct name { \ + struct type *sph_root; /* root of the tree */ \ +} + +#define SPLAY_INITIALIZER(root) \ + { NULL } + +#define SPLAY_INIT(root) do { \ + (root)->sph_root = NULL; \ +} while (0) + +#define SPLAY_ENTRY(type) \ +struct { \ + struct type *spe_left; /* left element */ \ + struct type *spe_right; /* right element */ \ +} + +#define SPLAY_LEFT(elm, field) (elm)->field.spe_left +#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right +#define SPLAY_ROOT(head) (head)->sph_root +#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL) + +/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */ +#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ +} while (0) + +#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + (head)->sph_root = tmp; \ +} while (0) + +#define SPLAY_LINKLEFT(head, tmp, field) do { \ + SPLAY_LEFT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \ +} while (0) + +#define SPLAY_LINKRIGHT(head, tmp, field) do { \ + SPLAY_RIGHT(tmp, field) = (head)->sph_root; \ + tmp = (head)->sph_root; \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \ +} while (0) + +#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \ + SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \ + SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\ + SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \ + SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \ +} while (0) + +/* Generates prototypes and inline functions */ + +#define SPLAY_PROTOTYPE(name, type, field, cmp) \ +void name##_SPLAY(struct name *, struct type *); \ +void name##_SPLAY_MINMAX(struct name *, int); \ +struct type *name##_SPLAY_INSERT(struct name *, struct type *); \ +struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \ + \ +/* Finds the node with the same key as elm */ \ +static __inline struct type * \ +name##_SPLAY_FIND(struct name *head, struct type *elm) \ +{ \ + if (SPLAY_EMPTY(head)) \ + return(NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) \ + return (head->sph_root); \ + return (NULL); \ +} \ + \ +static __inline struct type * \ +name##_SPLAY_NEXT(struct name *head, struct type *elm) \ +{ \ + name##_SPLAY(head, elm); \ + if (SPLAY_RIGHT(elm, field) != NULL) { \ + elm = SPLAY_RIGHT(elm, field); \ + while (SPLAY_LEFT(elm, field) != NULL) { \ + elm = SPLAY_LEFT(elm, field); \ + } \ + } else \ + elm = NULL; \ + return (elm); \ +} \ + \ +static __inline struct type * \ +name##_SPLAY_MIN_MAX(struct name *head, int val) \ +{ \ + name##_SPLAY_MINMAX(head, val); \ + return (SPLAY_ROOT(head)); \ +} + +/* Main splay operation. + * Moves node close to the key of elm to top + */ +#define SPLAY_GENERATE(name, type, field, cmp) \ +struct type * \ +name##_SPLAY_INSERT(struct name *head, struct type *elm) \ +{ \ + if (SPLAY_EMPTY(head)) { \ + SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \ + } else { \ + int __comp; \ + name##_SPLAY(head, elm); \ + __comp = (cmp)(elm, (head)->sph_root); \ + if(__comp < 0) { \ + SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\ + SPLAY_RIGHT(elm, field) = (head)->sph_root; \ + SPLAY_LEFT((head)->sph_root, field) = NULL; \ + } else if (__comp > 0) { \ + SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\ + SPLAY_LEFT(elm, field) = (head)->sph_root; \ + SPLAY_RIGHT((head)->sph_root, field) = NULL; \ + } else \ + return ((head)->sph_root); \ + } \ + (head)->sph_root = (elm); \ + return (NULL); \ +} \ + \ +struct type * \ +name##_SPLAY_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *__tmp; \ + if (SPLAY_EMPTY(head)) \ + return (NULL); \ + name##_SPLAY(head, elm); \ + if ((cmp)(elm, (head)->sph_root) == 0) { \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \ + (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\ + } else { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\ + name##_SPLAY(head, elm); \ + SPLAY_RIGHT((head)->sph_root, field) = __tmp; \ + } \ + return (elm); \ + } \ + return (NULL); \ +} \ + \ +void \ +name##_SPLAY(struct name *head, struct type *elm) \ +{ \ + struct type __node, *__left, *__right, *__tmp; \ + int __comp; \ +\ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ + __left = __right = &__node; \ +\ + while ((__comp = (cmp)(elm, (head)->sph_root))) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) < 0){ \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if ((cmp)(elm, __tmp) > 0){ \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ +} \ + \ +/* Splay with either the minimum or the maximum element \ + * Used to find minimum or maximum element in tree. \ + */ \ +void name##_SPLAY_MINMAX(struct name *head, int __comp) \ +{ \ + struct type __node, *__left, *__right, *__tmp; \ +\ + SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\ + __left = __right = &__node; \ +\ + while (1) { \ + if (__comp < 0) { \ + __tmp = SPLAY_LEFT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp < 0){ \ + SPLAY_ROTATE_RIGHT(head, __tmp, field); \ + if (SPLAY_LEFT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKLEFT(head, __right, field); \ + } else if (__comp > 0) { \ + __tmp = SPLAY_RIGHT((head)->sph_root, field); \ + if (__tmp == NULL) \ + break; \ + if (__comp > 0) { \ + SPLAY_ROTATE_LEFT(head, __tmp, field); \ + if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\ + break; \ + } \ + SPLAY_LINKRIGHT(head, __left, field); \ + } \ + } \ + SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \ +} + +#define SPLAY_NEGINF -1 +#define SPLAY_INF 1 + +#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y) +#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y) +#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y) +#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y) +#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \ + : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF)) +#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \ + : name##_SPLAY_MIN_MAX(x, SPLAY_INF)) + +#define SPLAY_FOREACH(x, name, head) \ + for ((x) = SPLAY_MIN(name, head); \ + (x) != NULL; \ + (x) = SPLAY_NEXT(name, head, x)) + +/* Macros that define a red-black tree */ +#define RB_HEAD(name, type) \ +struct name { \ + struct type *rbh_root; /* root of the tree */ \ +} + +#define RB_INITIALIZER(root) \ + { NULL } + +#define RB_INIT(root) do { \ + (root)->rbh_root = NULL; \ +} while (0) + +#define RB_BLACK 0 +#define RB_RED 1 +#define RB_ENTRY(type) \ +struct { \ + struct type *rbe_left; /* left element */ \ + struct type *rbe_right; /* right element */ \ + struct type *rbe_parent; /* parent element */ \ + int rbe_color; /* node color */ \ +} + +#define RB_LEFT(elm, field) (elm)->field.rbe_left +#define RB_RIGHT(elm, field) (elm)->field.rbe_right +#define RB_PARENT(elm, field) (elm)->field.rbe_parent +#define RB_COLOR(elm, field) (elm)->field.rbe_color +#define RB_ROOT(head) (head)->rbh_root +#define RB_EMPTY(head) (RB_ROOT(head) == NULL) + +#define RB_SET(elm, parent, field) do { \ + RB_PARENT(elm, field) = parent; \ + RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \ + RB_COLOR(elm, field) = RB_RED; \ +} while (0) + +#define RB_SET_BLACKRED(black, red, field) do { \ + RB_COLOR(black, field) = RB_BLACK; \ + RB_COLOR(red, field) = RB_RED; \ +} while (0) + +#ifndef RB_AUGMENT +#define RB_AUGMENT(x) do {} while (0) +#endif + +#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \ + (tmp) = RB_RIGHT(elm, field); \ + if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \ + RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \ + } \ + RB_AUGMENT(elm); \ + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ + else \ + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ + } else \ + (head)->rbh_root = (tmp); \ + RB_LEFT(tmp, field) = (elm); \ + RB_PARENT(elm, field) = (tmp); \ + RB_AUGMENT(tmp); \ + if ((RB_PARENT(tmp, field))) \ + RB_AUGMENT(RB_PARENT(tmp, field)); \ +} while (0) + +#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \ + (tmp) = RB_LEFT(elm, field); \ + if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \ + RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \ + } \ + RB_AUGMENT(elm); \ + if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \ + if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \ + RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \ + else \ + RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \ + } else \ + (head)->rbh_root = (tmp); \ + RB_RIGHT(tmp, field) = (elm); \ + RB_PARENT(elm, field) = (tmp); \ + RB_AUGMENT(tmp); \ + if ((RB_PARENT(tmp, field))) \ + RB_AUGMENT(RB_PARENT(tmp, field)); \ +} while (0) + +/* Generates prototypes and inline functions */ +#define RB_PROTOTYPE(name, type, field, cmp) \ + RB_PROTOTYPE_INTERNAL(name, type, field, cmp,) +#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \ + RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) +#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \ +attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \ +attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\ +attr struct type *name##_RB_REMOVE(struct name *, struct type *); \ +attr struct type *name##_RB_INSERT(struct name *, struct type *); \ +attr struct type *name##_RB_FIND(struct name *, struct type *); \ +attr struct type *name##_RB_NFIND(struct name *, struct type *); \ +attr struct type *name##_RB_NEXT(struct type *); \ +attr struct type *name##_RB_PREV(struct type *); \ +attr struct type *name##_RB_MINMAX(struct name *, int); \ + \ + +/* Main rb operation. + * Moves node close to the key of elm to top + */ +#define RB_GENERATE(name, type, field, cmp) \ + RB_GENERATE_INTERNAL(name, type, field, cmp,) +#define RB_GENERATE_STATIC(name, type, field, cmp) \ + RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static) +#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \ +attr void \ +name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \ +{ \ + struct type *parent, *gparent, *tmp; \ + while ((parent = RB_PARENT(elm, field)) && \ + RB_COLOR(parent, field) == RB_RED) { \ + gparent = RB_PARENT(parent, field); \ + if (parent == RB_LEFT(gparent, field)) { \ + tmp = RB_RIGHT(gparent, field); \ + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ + RB_COLOR(tmp, field) = RB_BLACK; \ + RB_SET_BLACKRED(parent, gparent, field);\ + elm = gparent; \ + continue; \ + } \ + if (RB_RIGHT(parent, field) == elm) { \ + RB_ROTATE_LEFT(head, parent, tmp, field);\ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + RB_SET_BLACKRED(parent, gparent, field); \ + RB_ROTATE_RIGHT(head, gparent, tmp, field); \ + } else { \ + tmp = RB_LEFT(gparent, field); \ + if (tmp && RB_COLOR(tmp, field) == RB_RED) { \ + RB_COLOR(tmp, field) = RB_BLACK; \ + RB_SET_BLACKRED(parent, gparent, field);\ + elm = gparent; \ + continue; \ + } \ + if (RB_LEFT(parent, field) == elm) { \ + RB_ROTATE_RIGHT(head, parent, tmp, field);\ + tmp = parent; \ + parent = elm; \ + elm = tmp; \ + } \ + RB_SET_BLACKRED(parent, gparent, field); \ + RB_ROTATE_LEFT(head, gparent, tmp, field); \ + } \ + } \ + RB_COLOR(head->rbh_root, field) = RB_BLACK; \ +} \ + \ +attr void \ +name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \ +{ \ + struct type *tmp; \ + while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \ + elm != RB_ROOT(head)) { \ + if (RB_LEFT(parent, field) == elm) { \ + tmp = RB_RIGHT(parent, field); \ + if (RB_COLOR(tmp, field) == RB_RED) { \ + RB_SET_BLACKRED(tmp, parent, field); \ + RB_ROTATE_LEFT(head, parent, tmp, field);\ + tmp = RB_RIGHT(parent, field); \ + } \ + if ((RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ + (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ + RB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = RB_PARENT(elm, field); \ + } else { \ + if (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\ + struct type *oleft; \ + if ((oleft = RB_LEFT(tmp, field)))\ + RB_COLOR(oleft, field) = RB_BLACK;\ + RB_COLOR(tmp, field) = RB_RED; \ + RB_ROTATE_RIGHT(head, tmp, oleft, field);\ + tmp = RB_RIGHT(parent, field); \ + } \ + RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ + RB_COLOR(parent, field) = RB_BLACK; \ + if (RB_RIGHT(tmp, field)) \ + RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\ + RB_ROTATE_LEFT(head, parent, tmp, field);\ + elm = RB_ROOT(head); \ + break; \ + } \ + } else { \ + tmp = RB_LEFT(parent, field); \ + if (RB_COLOR(tmp, field) == RB_RED) { \ + RB_SET_BLACKRED(tmp, parent, field); \ + RB_ROTATE_RIGHT(head, parent, tmp, field);\ + tmp = RB_LEFT(parent, field); \ + } \ + if ((RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\ + (RB_RIGHT(tmp, field) == NULL || \ + RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\ + RB_COLOR(tmp, field) = RB_RED; \ + elm = parent; \ + parent = RB_PARENT(elm, field); \ + } else { \ + if (RB_LEFT(tmp, field) == NULL || \ + RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\ + struct type *oright; \ + if ((oright = RB_RIGHT(tmp, field)))\ + RB_COLOR(oright, field) = RB_BLACK;\ + RB_COLOR(tmp, field) = RB_RED; \ + RB_ROTATE_LEFT(head, tmp, oright, field);\ + tmp = RB_LEFT(parent, field); \ + } \ + RB_COLOR(tmp, field) = RB_COLOR(parent, field);\ + RB_COLOR(parent, field) = RB_BLACK; \ + if (RB_LEFT(tmp, field)) \ + RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\ + RB_ROTATE_RIGHT(head, parent, tmp, field);\ + elm = RB_ROOT(head); \ + break; \ + } \ + } \ + } \ + if (elm) \ + RB_COLOR(elm, field) = RB_BLACK; \ +} \ + \ +attr struct type * \ +name##_RB_REMOVE(struct name *head, struct type *elm) \ +{ \ + struct type *child, *parent, *old = elm; \ + int color; \ + if (RB_LEFT(elm, field) == NULL) \ + child = RB_RIGHT(elm, field); \ + else if (RB_RIGHT(elm, field) == NULL) \ + child = RB_LEFT(elm, field); \ + else { \ + struct type *left; \ + elm = RB_RIGHT(elm, field); \ + while ((left = RB_LEFT(elm, field))) \ + elm = left; \ + child = RB_RIGHT(elm, field); \ + parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (child) \ + RB_PARENT(child, field) = parent; \ + if (parent) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_LEFT(parent, field) = child; \ + else \ + RB_RIGHT(parent, field) = child; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = child; \ + if (RB_PARENT(elm, field) == old) \ + parent = elm; \ + (elm)->field = (old)->field; \ + if (RB_PARENT(old, field)) { \ + if (RB_LEFT(RB_PARENT(old, field), field) == old)\ + RB_LEFT(RB_PARENT(old, field), field) = elm;\ + else \ + RB_RIGHT(RB_PARENT(old, field), field) = elm;\ + RB_AUGMENT(RB_PARENT(old, field)); \ + } else \ + RB_ROOT(head) = elm; \ + RB_PARENT(RB_LEFT(old, field), field) = elm; \ + if (RB_RIGHT(old, field)) \ + RB_PARENT(RB_RIGHT(old, field), field) = elm; \ + if (parent) { \ + left = parent; \ + do { \ + RB_AUGMENT(left); \ + } while ((left = RB_PARENT(left, field))); \ + } \ + goto color; \ + } \ + parent = RB_PARENT(elm, field); \ + color = RB_COLOR(elm, field); \ + if (child) \ + RB_PARENT(child, field) = parent; \ + if (parent) { \ + if (RB_LEFT(parent, field) == elm) \ + RB_LEFT(parent, field) = child; \ + else \ + RB_RIGHT(parent, field) = child; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = child; \ +color: \ + if (color == RB_BLACK) \ + name##_RB_REMOVE_COLOR(head, parent, child); \ + return (old); \ +} \ + \ +/* Inserts a node into the RB tree */ \ +attr struct type * \ +name##_RB_INSERT(struct name *head, struct type *elm) \ +{ \ + struct type *tmp; \ + struct type *parent = NULL; \ + int comp = 0; \ + tmp = RB_ROOT(head); \ + while (tmp) { \ + parent = tmp; \ + comp = (cmp)(elm, parent); \ + if (comp < 0) \ + tmp = RB_LEFT(tmp, field); \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + RB_SET(elm, parent, field); \ + if (parent != NULL) { \ + if (comp < 0) \ + RB_LEFT(parent, field) = elm; \ + else \ + RB_RIGHT(parent, field) = elm; \ + RB_AUGMENT(parent); \ + } else \ + RB_ROOT(head) = elm; \ + name##_RB_INSERT_COLOR(head, elm); \ + return (NULL); \ +} \ + \ +/* Finds the node with the same key as elm */ \ +attr struct type * \ +name##_RB_FIND(struct name *head, struct type *elm) \ +{ \ + struct type *tmp = RB_ROOT(head); \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) \ + tmp = RB_LEFT(tmp, field); \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + return (NULL); \ +} \ + \ +/* Finds the first node greater than or equal to the search key */ \ +attr struct type * \ +name##_RB_NFIND(struct name *head, struct type *elm) \ +{ \ + struct type *tmp = RB_ROOT(head); \ + struct type *res = NULL; \ + int comp; \ + while (tmp) { \ + comp = cmp(elm, tmp); \ + if (comp < 0) { \ + res = tmp; \ + tmp = RB_LEFT(tmp, field); \ + } \ + else if (comp > 0) \ + tmp = RB_RIGHT(tmp, field); \ + else \ + return (tmp); \ + } \ + return (res); \ +} \ + \ +/* ARGSUSED */ \ +attr struct type * \ +name##_RB_NEXT(struct type *elm) \ +{ \ + if (RB_RIGHT(elm, field)) { \ + elm = RB_RIGHT(elm, field); \ + while (RB_LEFT(elm, field)) \ + elm = RB_LEFT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ +} \ + \ +/* ARGSUSED */ \ +attr struct type * \ +name##_RB_PREV(struct type *elm) \ +{ \ + if (RB_LEFT(elm, field)) { \ + elm = RB_LEFT(elm, field); \ + while (RB_RIGHT(elm, field)) \ + elm = RB_RIGHT(elm, field); \ + } else { \ + if (RB_PARENT(elm, field) && \ + (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \ + elm = RB_PARENT(elm, field); \ + else { \ + while (RB_PARENT(elm, field) && \ + (elm == RB_LEFT(RB_PARENT(elm, field), field)))\ + elm = RB_PARENT(elm, field); \ + elm = RB_PARENT(elm, field); \ + } \ + } \ + return (elm); \ +} \ + \ +attr struct type * \ +name##_RB_MINMAX(struct name *head, int val) \ +{ \ + struct type *tmp = RB_ROOT(head); \ + struct type *parent = NULL; \ + while (tmp) { \ + parent = tmp; \ + if (val < 0) \ + tmp = RB_LEFT(tmp, field); \ + else \ + tmp = RB_RIGHT(tmp, field); \ + } \ + return (parent); \ +} + +#define RB_NEGINF -1 +#define RB_INF 1 + +#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y) +#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y) +#define RB_FIND(name, x, y) name##_RB_FIND(x, y) +#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y) +#define RB_NEXT(name, x, y) name##_RB_NEXT(y) +#define RB_PREV(name, x, y) name##_RB_PREV(y) +#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF) +#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF) + +#define RB_FOREACH(x, name, head) \ + for ((x) = RB_MIN(name, head); \ + (x) != NULL; \ + (x) = name##_RB_NEXT(x)) + +#define RB_FOREACH_SAFE(x, name, head, y) \ + for ((x) = RB_MIN(name, head); \ + ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \ + (x) = (y)) + +#define RB_FOREACH_REVERSE(x, name, head) \ + for ((x) = RB_MAX(name, head); \ + (x) != NULL; \ + (x) = name##_RB_PREV(x)) + +#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \ + for ((x) = RB_MAX(name, head); \ + ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \ + (x) = (y)) + +#endif /* _SYS_TREE_H_ */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/deps.sed Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,26 @@ +/^[^:]\{1,\}:.*\\$/{ + h + s/\([^:]\{1,\}:\).*/\1/ + x + s/[^:]\{1,\}:// +} +/\\$/,/^$/bgen +/\\$/,/[^\\]$/{ +:gen + s/[[:blank:]]*\\$// + s/^[[:blank:]]*// + G + s/\(.*\)\n\(.*\)/\2 \1/ +} +/^[^:]\{1,\}:[[:blank:]]*$/d +/^[^:]\{1,\}\.o:/{ + s/[[:blank:]]*[^[:blank:]]\{1,\}\.[cC][[:blank:]]*/ /g + s/[[:blank:]]*[^[:blank:]]\{1,\}\.[cC]$//g + s/[[:blank:]]*[^[:blank:]]\{1,\}\.cc[[:blank:]]*/ /g + s/[[:blank:]]*[^[:blank:]]\{1,\}\.cc$//g + s/[[:blank:]]*[^[:blank:]]\{1,\}\.cpp[[:blank:]]*/ /g + s/[[:blank:]]*[^[:blank:]]\{1,\}\.cpp$//g + /^[^:]\{1,\}:[[:blank:]]*$/d + s/^\([^:]\{1,\}\)\.o[[:blank:]]*:[[:blank:]]*\(.*\)/\1.d: $(wildcard \2)\ +&/ +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/include/pws.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,205 @@ +/* + * 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. + */ + +#ifndef PWS_H +#define PWS_H + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +#include <stdint.h> +#include <sys/types.h> +#include <stdio.h> + +#define LIBPWS_VERSION_MAJOR 1 +#define LIBPWS_VERSION_MINOR 0 +#define LIBPWS_VERSION_MICRO 0 + +#define PWS3_VERSION 0x030D + +#define PWS3_MAX_FIELD_SIZE (16 * 1024) +#define PWS3_MAX_PASSWORD_LEN 1023 +#define PWS3_UUID_SIZE 16 + +struct pws3_field; +struct pws3_record; +struct pws3_file; + +enum pws_error_code { + PWS_ERR_GENERIC_ERROR, + PWS_ERR_NO_MEMORY, + PWS_ERR_IO_ERROR, + PWS_ERR_TRUNCATED_FILE, + PWS_ERR_INVALID_CHECKSUM, + PWS_ERR_INVALID_RECORD, + PWS_ERR_INVALID_HEADER, + PWS_ERR_UNSUPPORTED_VERSION +}; + +enum pws_data_type { + PWS_DATA_TYPE_BYTES, + PWS_DATA_TYPE_UUID, + PWS_DATA_TYPE_TEXT, + PWS_DATA_TYPE_TIME, + PWS_DATA_TYPE_UINT8, + PWS_DATA_TYPE_UINT16, + PWS_DATA_TYPE_UINT32 +}; + +enum pws3_header_field_type { + PWS3_HEADER_FIELD_VERSION, /* 0x00 */ + PWS3_HEADER_FIELD_UUID, /* 0x01 */ + PWS3_HEADER_FIELD_NON_DEFAULT_PREFERENCES, /* 0x02 */ + PWS3_HEADER_FIELD_TREE_DISPLAY_STATUS, /* 0x03 */ + PWS3_HEADER_FIELD_SAVE_TIMESTAMP, /* 0x04 */ + PWS3_HEADER_FIELD_SAVE_USER_HOST, /* 0x05 */ + PWS3_HEADER_FIELD_SAVE_APPLICATION, /* 0x06 */ + PWS3_HEADER_FIELD_SAVE_USER, /* 0x07 */ + PWS3_HEADER_FIELD_SAVE_HOST, /* 0x08 */ + PWS3_HEADER_FIELD_DATABASE_NAME, /* 0x09 */ + PWS3_HEADER_FIELD_DATABASE_DESCRIPTION, /* 0x0a */ + PWS3_HEADER_FIELD_DATABASE_FILTERS, /* 0x0b */ + PWS3_HEADER_FIELD_RESERVED_1, /* 0x0c */ + PWS3_HEADER_FIELD_RESERVED_2, /* 0x0d */ + PWS3_HEADER_FIELD_RESERVED_3, /* 0x0e */ + PWS3_HEADER_FIELD_RECENTLY_USED_ENTRIES, /* 0x0f */ + PWS3_HEADER_FIELD_NAMED_PASSWORD_POLICIES, /* 0x10 */ + PWS3_HEADER_FIELD_EMPTY_GROUPS, /* 0x11 */ + PWS3_HEADER_FIELD_YUBICO, /* 0x12 */ + PWS3_HEADER_FIELD_END = 0xff +}; + +enum pws3_record_field_type { + PWS3_RECORD_FIELD_UUID = 0x01, + PWS3_RECORD_FIELD_GROUP, /* 0x02 */ + PWS3_RECORD_FIELD_TITLE, /* 0x03 */ + PWS3_RECORD_FIELD_USERNAME, /* 0x04 */ + PWS3_RECORD_FIELD_NOTES, /* 0x05 */ + PWS3_RECORD_FIELD_PASSWORD, /* 0x06 */ + PWS3_RECORD_FIELD_CREATION_TIME, /* 0x07 */ + PWS3_RECORD_FIELD_PASSWORD_MODIFICATION_TIME, /* 0x08 */ + PWS3_RECORD_FIELD_ACCESS_TIME, /* 0x09 */ + PWS3_RECORD_FIELD_PASSWORD_EXPIRY_TIME, /* 0x0a */ + PWS3_RECORD_FIELD_RESERVED_1, /* 0x0b */ + PWS3_RECORD_FIELD_MODIFICATION_TIME, /* 0x0c */ + PWS3_RECORD_FIELD_URL, /* 0x0d */ + PWS3_RECORD_FIELD_AUTOTYPE, /* 0x0e */ + PWS3_RECORD_FIELD_PASSWORD_HISTORY, /* 0x0f */ + PWS3_RECORD_FIELD_PASSWORD_POLICY, /* 0x10 */ + PWS3_RECORD_FIELD_PASSWORD_EXPIRY_INTERVAL, /* 0x11 */ + PWS3_RECORD_FIELD_RUN_COMMAND, /* 0x12 */ + PWS3_RECORD_FIELD_DOUBLE_CLICK_ACTION, /* 0x13 */ + PWS3_RECORD_FIELD_EMAIL_ADDRESS, /* 0x14 */ + PWS3_RECORD_FIELD_PROTECTED, /* 0x15 */ + PWS3_RECORD_FIELD_ALLOWED_PASSWORD_SYMBOLS, /* 0x16 */ + PWS3_RECORD_FIELD_SHIFT_DOUBLE_CLICK_ACTION, /* 0x17 */ + PWS3_RECORD_FIELD_PASSWORD_POLICY_NAME, /* 0x18 */ + PWS3_RECORD_FIELD_KEYBOARD_SHORTCUT, /* 0x19 */ + PWS3_RECORD_FIELD_END = 0xff +}; + +int pws_init(void); +void pws_finalize(void); +void pws_set_alloc_functions(void *(*)(size_t), + void *(*)(void *, size_t), void (*)(void *, size_t), void *(*)(size_t), + void *(*)(void *, size_t), void (*)(void *, size_t)); +int pws_generate_uuid(unsigned char [static PWS3_UUID_SIZE]); + +struct pws3_field * pws3_field_create(int, uint8_t); +void pws3_field_destroy(struct pws3_field *); +int pws3_field_is_header(struct pws3_field *); +uint8_t pws3_field_get_type(struct pws3_field *); +enum pws_data_type pws3_field_get_data_type(struct pws3_field *); +int pws3_field_set_uuid(struct pws3_field *, + const unsigned char [static PWS3_UUID_SIZE]); +int pws3_field_set_text(struct pws3_field *, const char [static 1]); +int pws3_field_set_time(struct pws3_field *, time_t); +int pws3_field_set_uint8(struct pws3_field *, uint8_t); +int pws3_field_set_uint16(struct pws3_field *, uint16_t); +int pws3_field_set_uint32(struct pws3_field *, uint32_t); +int pws3_field_set_bytes(struct pws3_field *, + const unsigned char [static 1], size_t); +const unsigned char * pws3_field_get_uuid(struct pws3_field *); +const char * pws3_field_get_text(struct pws3_field *); +time_t pws3_field_get_time(struct pws3_field *); +uint8_t pws3_field_get_uint8(struct pws3_field *); +uint16_t pws3_field_get_uint16(struct pws3_field *); +uint32_t pws3_field_get_uint32(struct pws3_field *); +void pws3_field_get_bytes(struct pws3_field *, + const unsigned char **, size_t *); + +void pws3_record_destroy(struct pws3_record *); +struct pws3_record * pws3_record_create(void); +void pws3_record_set_field(struct pws3_record *, + struct pws3_field *); +struct pws3_field * pws3_record_get_field(struct pws3_record *, uint8_t); +struct pws3_field * pws3_record_remove_field(struct pws3_record *, uint8_t); + +void pws3_file_destroy(struct pws3_file *); +struct pws3_file * pws3_file_create(void); +enum pws_error_code pws3_file_get_error_code(struct pws3_file *); +const char * pws3_file_get_error_message(struct pws3_file *); +int pws3_file_read_mem(struct pws3_file *, const char *, + unsigned char *, size_t); +int pws3_file_read_stream(struct pws3_file *, const char *, FILE *); +int pws3_file_write_mem(struct pws3_file *, const char *, uint32_t, + unsigned char **, size_t *); +int pws3_file_write_stream(struct pws3_file *, const char *, + uint32_t, FILE *); + +void pws3_file_set_header_field(struct pws3_file *, + struct pws3_field *); +struct pws3_field * pws3_file_get_header_field(struct pws3_file *, uint8_t); +struct pws3_field * pws3_file_remove_header_field(struct pws3_file *, uint8_t); + +void pws3_file_insert_empty_group(struct pws3_file *, + struct pws3_field *); +struct pws3_field * pws3_file_get_empty_group(struct pws3_file *, const char *); +struct pws3_field * pws3_file_remove_empty_group(struct pws3_file *, + const char *); +struct pws3_field * pws3_file_first_empty_group(struct pws3_file *); +struct pws3_field * pws3_file_last_empty_group(struct pws3_file *); +struct pws3_field * pws3_file_next_empty_group(struct pws3_file *, + struct pws3_field *); +struct pws3_field * pws3_file_prev_empty_group(struct pws3_file *, + struct pws3_field *); + +void pws3_file_insert_record(struct pws3_file *, + struct pws3_record *); +struct pws3_record * pws3_file_get_record(struct pws3_file *, + const unsigned char [static PWS3_UUID_SIZE]); +struct pws3_record * pws3_file_remove_record(struct pws3_file *, + const unsigned char [static PWS3_UUID_SIZE]); +struct pws3_record * pws3_file_first_record(struct pws3_file *); +struct pws3_record * pws3_file_last_record(struct pws3_file *); +struct pws3_record * pws3_file_next_record(struct pws3_file *, + struct pws3_record *); +struct pws3_record * pws3_file_prev_record(struct pws3_file *, + struct pws3_record *); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif /* !PWS_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pws-field.c Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,332 @@ +/* + * 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 <string.h> +#include <limits.h> + +#include "pws-internal.h" + +static const enum pws_data_type header_data_types[256] = { + [PWS3_HEADER_FIELD_VERSION] = PWS_DATA_TYPE_UINT16, + [PWS3_HEADER_FIELD_UUID] = PWS_DATA_TYPE_UUID, + [PWS3_HEADER_FIELD_NON_DEFAULT_PREFERENCES] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_TREE_DISPLAY_STATUS] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_SAVE_TIMESTAMP] = PWS_DATA_TYPE_TIME, + [PWS3_HEADER_FIELD_SAVE_USER_HOST] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_SAVE_APPLICATION] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_SAVE_USER] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_SAVE_HOST] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_DATABASE_NAME] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_DATABASE_DESCRIPTION] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_DATABASE_FILTERS] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_RESERVED_1] = PWS_DATA_TYPE_BYTES, + [PWS3_HEADER_FIELD_RESERVED_2] = PWS_DATA_TYPE_BYTES, + [PWS3_HEADER_FIELD_RESERVED_3] = PWS_DATA_TYPE_BYTES, + [PWS3_HEADER_FIELD_RECENTLY_USED_ENTRIES] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_NAMED_PASSWORD_POLICIES] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_EMPTY_GROUPS] = PWS_DATA_TYPE_TEXT, + [PWS3_HEADER_FIELD_YUBICO] = PWS_DATA_TYPE_TEXT +}; + +static const enum pws_data_type record_data_types[256] = { + [PWS3_RECORD_FIELD_UUID] = PWS_DATA_TYPE_UUID, + [PWS3_RECORD_FIELD_GROUP] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_TITLE] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_USERNAME] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_NOTES] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_PASSWORD] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_CREATION_TIME] = PWS_DATA_TYPE_TIME, + [PWS3_RECORD_FIELD_PASSWORD_MODIFICATION_TIME] = PWS_DATA_TYPE_TIME, + [PWS3_RECORD_FIELD_ACCESS_TIME] = PWS_DATA_TYPE_TIME, + [PWS3_RECORD_FIELD_PASSWORD_EXPIRY_TIME] = PWS_DATA_TYPE_TIME, + [PWS3_RECORD_FIELD_RESERVED_1] = PWS_DATA_TYPE_BYTES, + [PWS3_RECORD_FIELD_MODIFICATION_TIME] = PWS_DATA_TYPE_TIME, + [PWS3_RECORD_FIELD_URL] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_AUTOTYPE] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_PASSWORD_HISTORY] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_PASSWORD_POLICY] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_PASSWORD_EXPIRY_INTERVAL] = PWS_DATA_TYPE_UINT32, + [PWS3_RECORD_FIELD_RUN_COMMAND] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_DOUBLE_CLICK_ACTION] = PWS_DATA_TYPE_BYTES, + [PWS3_RECORD_FIELD_EMAIL_ADDRESS] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_PROTECTED] = PWS_DATA_TYPE_UINT8, + [PWS3_RECORD_FIELD_ALLOWED_PASSWORD_SYMBOLS] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_SHIFT_DOUBLE_CLICK_ACTION] = PWS_DATA_TYPE_BYTES, + [PWS3_RECORD_FIELD_PASSWORD_POLICY_NAME] = PWS_DATA_TYPE_TEXT, + [PWS3_RECORD_FIELD_KEYBOARD_SHORTCUT] = PWS_DATA_TYPE_BYTES +}; + +struct pws3_field * +pws3_field_create(int is_header, uint8_t field_type) +{ + struct pws3_field *field; + + field = pws_alloc(sizeof (struct pws3_field)); + if (field == NULL) { + return (NULL); + } + + field->is_header = is_header; + field->field_type = field_type; + field->size = 0; + switch (pws3_field_get_data_type(field)) { + case PWS_DATA_TYPE_BYTES: + field->value.bytes = NULL; + break; + case PWS_DATA_TYPE_UUID: + memset(field->value.uuid, 0, PWS3_UUID_SIZE); + break; + case PWS_DATA_TYPE_TEXT: + field->value.text = NULL; + break; + case PWS_DATA_TYPE_UINT8: + field->value.uint8 = 0; + break; + case PWS_DATA_TYPE_UINT16: + field->value.uint16 = 0; + break; + case PWS_DATA_TYPE_TIME: /* FALLTHROUGH */ + case PWS_DATA_TYPE_UINT32: + field->value.uint32 = 0; + } + + return (field); +} + +void +pws3_field_destroy(struct pws3_field *field) +{ + if (field == NULL) { + return; + } + + switch (pws3_field_get_data_type(field)) { + case PWS_DATA_TYPE_BYTES: + pws_free(field->value.bytes, field->size); + break; + case PWS_DATA_TYPE_TEXT: + if (!field->is_header && + (field->field_type == PWS3_RECORD_FIELD_PASSWORD)) { + pws_secure_free(field->value.text, field->size + 1); + } else { + pws_free(field->value.text, field->size + 1); + } + break; + default: + break; + } + + pws_free(field, sizeof (struct pws3_field)); +} + +int +pws3_field_is_header(struct pws3_field *field) +{ + return (field->is_header); +} + +uint8_t +pws3_field_get_type(struct pws3_field *field) +{ + return (field->field_type); +} + +enum pws_data_type +pws3_field_get_data_type(struct pws3_field *field) +{ + return (field->is_header ? header_data_types[field->field_type] : + record_data_types[field->field_type]); +} + +int +pws3_field_set_uuid(struct pws3_field *field, + const unsigned char s[static PWS3_UUID_SIZE]) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UUID); + + field->size = PWS3_UUID_SIZE; + memcpy(field->value.uuid, s, PWS3_UUID_SIZE); + + return (0); +} + +int +pws3_field_set_text(struct pws3_field *field, const char s[static 1]) +{ + size_t len; + char *t; + + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_TEXT); + + len = strlen(s); + if (len > PWS3_MAX_FIELD_SIZE) { + return (-1); + } + + if (!field->is_header && + (field->field_type == PWS3_RECORD_FIELD_PASSWORD)) { + if (len > PWS3_MAX_PASSWORD_LEN) { + return (-1); + } + t = pws_secure_realloc(field->value.text, len + 1); + } else { + t = pws_realloc(field->value.text, len + 1); + } + if (t == NULL) { + return (-1); + } + field->value.text = t; + field->size = len + 1; + memcpy(field->value.text, s, field->size); + + return (0); +} + +int +pws3_field_set_time(struct pws3_field *field, time_t time) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_TIME); + + field->size = 4; + field->value.uint32 = CLAMP(time, 0, UINT32_MAX); + + return (0); +} + +int +pws3_field_set_uint8(struct pws3_field *field, uint8_t u8) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UINT8); + + field->size = 1; + field->value.uint8 = u8; + + return (0); +} + +int +pws3_field_set_uint16(struct pws3_field *field, uint16_t u16) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UINT16); + + field->size = 2; + field->value.uint16 = u16; + + return (0); +} + +int +pws3_field_set_uint32(struct pws3_field *field, uint32_t u32) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UINT32); + + field->size = 4; + field->value.uint32 = u32; + + return (0); +} + +int +pws3_field_set_bytes(struct pws3_field *field, const unsigned char s[static 1], + size_t n) +{ + unsigned char *t; + + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_BYTES); + + if (n > PWS3_MAX_FIELD_SIZE) { + return (-1); + } + + t = pws_realloc(field->value.bytes, n); + if (t == NULL) { + return (-1); + } + field->size = n; + field->value.bytes = t; + memcpy(t, s, n); + + return (0); +} + +const unsigned char * +pws3_field_get_uuid(struct pws3_field *field) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UUID); + + return (field->value.uuid); +} + +const char * +pws3_field_get_text(struct pws3_field *field) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_TEXT); + + return (field->value.text); +} + +time_t +pws3_field_get_time(struct pws3_field *field) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_TIME); + + /* assume time_t can hold at least a INT32_MAX */ + return ((time_t)CLAMP(field->value.uint32, 0, INT32_MAX)); +} + +uint8_t +pws3_field_get_uint8(struct pws3_field *field) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UINT8); + + return (field->value.uint8); +} + +uint16_t +pws3_field_get_uint16(struct pws3_field *field) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UINT16); + + return (field->value.uint16); +} + +uint32_t +pws3_field_get_uint32(struct pws3_field *field) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_UINT32); + + return (field->value.uint32); +} + +void +pws3_field_get_bytes(struct pws3_field *field, const unsigned char **sp, + size_t *np) +{ + PWS_ASSERT(pws3_field_get_data_type(field) == PWS_DATA_TYPE_BYTES); + + *sp = field->value.bytes; + *np = field->size; +}
--- /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)); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pws-internal.h Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,83 @@ +/* + * 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. + */ + +#ifndef PWS_INTERNAL_H +#define PWS_INTERNAL_H + +#include <signal.h> +#ifdef HAVE_SYS_TREE_H +#include <sys/tree.h> +#endif /* HAVE_SYS_TREE_H */ +#include <sys/types.h> +#include <unistd.h> + +#include "include/pws.h" + +#define MAX(x, y) (((x) > (y)) ? (x) : (y)) +#define MIN(x, y) (((x) < (y)) ? (x) : (y)) +#define CLAMP(x, min, max) (((x) > (max)) ? (max) : (((x) < (min)) ?\ + (min) : (x))) + +#ifdef NDEBUG +#include <signal.h> +#include <unistd.h> +#define PWS_ASSERT(cond) while (cond) {\ + write(STDERR_FIELNO, "assertion failed: " #cond "\n", \ + sizeof ("assertion failed: " #cond "\n"));\ + raise(SIGKILL);\ + } +#else +#include <assert.h> +#define PWS_ASSERT(cond) assert(cond) +#endif /* NDEBUG */ + +struct pws3_field { + int is_header; + uint8_t field_type; + size_t size; + union { + unsigned char *bytes; + unsigned char uuid[PWS3_UUID_SIZE]; + char *text; + uint8_t uint8; + uint16_t uint16; + uint32_t uint32; + } value; + RB_ENTRY(pws3_field) tree_entry; +}; + +struct pws3_record { + struct pws3_field *fields[256]; + RB_ENTRY(pws3_record) tree_entry; +}; + +extern void * (*pws_alloc)(size_t); +extern void * (*pws_realloc)(void *, size_t); +extern void (*pws_free)(void *, size_t); +extern void * (*pws_secure_alloc)(size_t); +extern void * (*pws_secure_realloc)(void *, size_t); +extern void (*pws_secure_free)(void *, size_t); + +int pws_random_bytes(void *, size_t); + +#endif /* PWS_INTERNAL_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pws-random.c Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,61 @@ +/* + * 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 "pws-internal.h" + +#ifdef HAVE_ARC4RANDOM +/* prefer system arc4random(3) implementation */ +#include <stdlib.h> +#else /* HAVE_ARC4RANDOM */ +#ifdef HAVE_GETENTROPY +/* + * otherwise use system getentropy(2) implementation or fallback to seed + * Yarrow-256 PRNG from libnettle + */ +#include <unistd.h> +#endif /* HAVE_GETENTROPY */ +#include <nettle/yarrow.h> +#endif /* HAVE_ARC4RANDOM */ + +#include "pws-internal.h" + +int +pws_random_bytes(void *buf, size_t buf_size) +{ +#ifdef HAVE_ARC4RANDOM + arc4random_buf(buf, buf_size); +#else /* HAVE_ARC4RANDOM */ + struct yarrow256_ctx ctx; + unsigned char seed_buf[YARROW256_SEED_FILE_SIZE]; + + if (getentropy(&seed_buf, sizeof (seed_buf)) != 0) { + return (-1); + } + yarrow256_init(&ctx, 0, NULL); + yarrow256_seed(&ctx, sizeof (seed_buf), seed_buf); + yarrow256_random(&ctx, buf_size, buf); +#endif /* HAVE_ARC4RANDOM */ + + return (0); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pws-record.c Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,116 @@ +/* + * 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 "pws-internal.h" + +void +pws3_record_destroy(struct pws3_record *record) +{ + size_t i; + + if (record == NULL) { + return; + } + + for (i = 0x01; i <= 0xff; i++) { + pws3_field_destroy(record->fields[i]); + } + pws_free(record, sizeof (record)); +} + +struct pws3_record * +pws3_record_create(void) +{ + struct pws3_field *uuid_field = NULL; + unsigned char uuid[PWS3_UUID_SIZE]; + struct pws3_record *record = NULL; + size_t i; + + /* + * always add an UUID field which is mandatory and needed for inserting + * a record into a database + */ + if (pws_generate_uuid(uuid) != 0) { + goto err; + } + uuid_field = pws3_field_create(0, PWS3_RECORD_FIELD_UUID); + if (uuid_field == NULL) { + goto err; + } + pws3_field_set_uuid(uuid_field, uuid); + + record = pws_alloc(sizeof (struct pws3_record)); + if (record == NULL) { + goto err; + } + + for (i = 0x00; i <= 0xff; i++) { + record->fields[i] = NULL; + } + + pws3_record_set_field(record, uuid_field); + + return (record); +err: + pws3_field_destroy(uuid_field); + pws_free(record, (record != NULL) ? sizeof (struct pws3_record) : 0); + + return (NULL); +} + +void +pws3_record_set_field(struct pws3_record *record, struct pws3_field *field) +{ + uint8_t field_type; + + 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)); + + field_type = pws3_field_get_type(field); + pws3_field_destroy(pws3_record_remove_field(record, field_type)); + record->fields[field_type] = field; +} + +struct pws3_field * +pws3_record_get_field(struct pws3_record *record, uint8_t field_type) +{ + return (record->fields[field_type]); +} + +struct pws3_field * +pws3_record_remove_field(struct pws3_record *record, uint8_t field_type) +{ + struct pws3_field *field; + + field = pws3_record_get_field(record, field_type); + record->fields[field_type] = NULL; + + return (field); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/pws.c Tue Feb 10 11:29:54 2015 +0100 @@ -0,0 +1,91 @@ +/* + * 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 <string.h> + +#include "pws-internal.h" + +static void default_free(void *, size_t); + +void * (*pws_alloc)(size_t) = malloc; +void * (*pws_realloc)(void *, size_t) = realloc; +void (*pws_free)(void *, size_t) = default_free; +void * (*pws_secure_alloc)(size_t) = malloc; +void * (*pws_secure_realloc)(void *, size_t) = realloc; +void (*pws_secure_free)(void *, size_t) = default_free; + +int +pws_init(void) +{ + return (0); +} + +void +pws_finalize(void) +{ +} + +static void +default_free(void *ptr, size_t n) +{ + free(ptr); +} + +void +pws_set_alloc_functions(void *(*alloc_function)(size_t), + void *(*realloc_function)(void *, size_t), + void (*free_function)(void *, size_t), + void *(*secure_alloc_function)(size_t), + void *(*secure_realloc_function)(void *, size_t), + void (*secure_free_function)(void *, size_t)) +{ + pws_alloc = (alloc_function != NULL) ? alloc_function : malloc; + pws_realloc = (realloc_function != NULL) ? realloc_function : realloc; + pws_free = (free_function != NULL) ? free_function : default_free; + pws_secure_alloc = (secure_alloc_function != NULL) ? + secure_alloc_function : malloc; + pws_secure_realloc = (secure_realloc_function != NULL) ? + secure_realloc_function : realloc; + pws_secure_free = (secure_free_function != NULL) ? + secure_free_function : default_free; +} + +int +pws_generate_uuid(unsigned char uuid[static PWS3_UUID_SIZE]) +{ + unsigned char buf[PWS3_UUID_SIZE]; + + if (pws_random_bytes(buf, sizeof (buf)) != 0) { + return (-1); + } + + /* UUID v4 from RFC 4122, section 4.4 */ + buf[6] = (buf[6] & 0x0f) | 0x40; + buf[8] = (buf[8] & 0x3f) | 0x80; + memcpy(uuid, buf, sizeof (buf)); + + return (0); +}