commit efb8d0ee374ca166717caedcfa6b5c5b7bdb714e
parent 2bfdbb2f891cddb5f7f1c720f846305223475f7e
Author: Stephen Gregoratto <dev@sgregoratto.me>
Date: Wed, 12 Feb 2020 00:24:31 +1100
Major improvements
- Switch build process to use oconfigure and overhaul the Makefile to
make use of it. Also removed the html manpage target.
- Remove program versioning
- Add pledge support for OpenBSD.
- Add custom, portable random number generation functions instead of
just arc4random.
- Add a bunch of other stuff from oconfigure compats.
- Simplify wording in manpage
Diffstat:
| A | .gitignore | | | 7 | +++++++ |
| M | Makefile | | | 44 | ++++++++++++-------------------------------- |
| A | compats.c | | | 1440 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | configure | | | 1993 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | rng.c | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | rng.h | | | 5 | +++++ |
| M | rpass.1 | | | 81 | +++++++++++++++++++++++++++++++++++++++++++------------------------------------ |
| M | rpass.c | | | 126 | +++++++++++++++++++++++++++++-------------------------------------------------- |
| A | tests.c | | | 503 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
9 files changed, 4140 insertions(+), 149 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,7 @@
+*.log
+*.o
+*.old
+Makefile.configure
+config.h
+rpass
+tags
diff --git a/Makefile b/Makefile
@@ -1,38 +1,18 @@
-PROG= rpass
+include Makefile.configure
-PREFIX = /usr/local
-BINDIR = $(PREFIX)/bin
-MANDIR = $(PREFIX)/man
+OBJS = rpass.o rng.o compats.o
-CFLAGS += -Wall -Wextra -pedantic-errors
+rpass: $(OBJS)
+ $(CC) $(LDFLAGS) -lm -o $@ $(OBJS)
-INSTALL_BIN = install -m 0555
-INSTALL_MAN = install -m 0444
+rpass.o: rng.h
+rng.o: rng.h
-INSTALL_DIR= install -dm 755
-INSTALL_BIN= install -m 555
-INSTALL_MAN= install -m 444
-
-VERSION_MAJOR = 0
-VERSION_MINOR = 2
-VERSION_PATCH = 1
-
-rpass: rpass.c
- ${CC} ${CFLAGS} -DVERSION_MAJOR=${VERSION_MAJOR} \
- -DVERSION_MINOR=${VERSION_MINOR} -DVERSION_PATCH=${VERSION_PATCH} \
- rpass.c -o $@ -lm
-
-rpass.1.html: rpass.1
- mandoc -T html -O style=man.css rpass.1 > rpass.1.html
-
-.PHONY: manhtml clean install
-manhtml: rpass.1.html
+install:
+ mkdir -p $(DESTDIR)/$(BINDIR)
+ mkdir -p $(DESTDIR)/$(MANDIR)/man1
+ $(INSTALL_PROGRAM) rpass $(DESTDIR)/$(BINDIR)/rpass
+ $(INSTALL_MAN) rpass.1 $(DESTDIR)/$(MANDIR)/man1/rpass.1
clean:
- rm -f rpass rpass.1.html
-
-install:
- ${INSTALL_DIR} ${DESTDIR}${BINDIR}
- ${INSTALL_DIR} ${DESTDIR}${MANDIR}/man1
- ${INSTALL_BIN} ${PROG} ${DESTDIR}${BINDIR}
- ${INSTALL_MAN} ${PROG}.1 ${DESTDIR}${MANDIR}/man1
+ rm -f rpass $(OBJS)
diff --git a/compats.c b/compats.c
@@ -0,0 +1,1440 @@
+#include "config.h"
+#if !HAVE_ERR
+/*
+ * Copyright (c) 1993
+ * The Regents of the University of California. 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.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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.
+ */
+
+#include <errno.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+void
+vwarnx(const char *fmt, va_list ap)
+{
+ fprintf(stderr, "%s: ", getprogname());
+ if (fmt != NULL)
+ vfprintf(stderr, fmt, ap);
+}
+
+void
+vwarn(const char *fmt, va_list ap)
+{
+ int sverrno;
+
+ sverrno = errno;
+ vwarnx(fmt, ap);
+ if (fmt != NULL)
+ fputs(": ", stderr);
+ fprintf(stderr, "%s\n", strerror(sverrno));
+}
+
+void
+err(int eval, const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ vwarn(fmt, ap);
+ va_end(ap);
+ exit(eval);
+}
+
+void
+errx(int eval, const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ vwarnx(fmt, ap);
+ va_end(ap);
+ fputc('\n', stderr);
+ exit(eval);
+}
+
+void
+warn(const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ vwarn(fmt, ap);
+ va_end(ap);
+}
+
+void
+warnx(const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ vwarnx(fmt, ap);
+ va_end(ap);
+ fputc('\n', stderr);
+}
+#endif /* !HAVE_ERR */
+#if !HAVE_B64_NTOP
+/* $OpenBSD$ */
+
+/*
+ * Copyright (c) 1996 by Internet Software Consortium.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS
+ * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE
+ * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL
+ * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
+ * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
+ * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
+ * SOFTWARE.
+ */
+
+/*
+ * Portions Copyright (c) 1995 by International Business Machines, Inc.
+ *
+ * International Business Machines, Inc. (hereinafter called IBM) grants
+ * permission under its copyrights to use, copy, modify, and distribute this
+ * Software with or without fee, provided that the above copyright notice and
+ * all paragraphs of this notice appear in all copies, and that the name of IBM
+ * not be used in connection with the marketing of any product incorporating
+ * the Software or modifications thereof, without specific, written prior
+ * permission.
+ *
+ * To the extent it has a right to do so, IBM grants an immunity from suit
+ * under its patents, if any, for the use, sale or manufacture of products to
+ * the extent that such products are used for performing Domain Name System
+ * dynamic updates in TCP/IP networks by means of the Software. No immunity is
+ * granted for any product per se or for any other function of any product.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", AND IBM DISCLAIMS ALL WARRANTIES,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL,
+ * DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER ARISING
+ * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE, EVEN
+ * IF IBM IS APPRISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ */
+
+#include <sys/types.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <arpa/inet.h>
+#include <arpa/nameser.h>
+
+#include <ctype.h>
+#include <resolv.h>
+#include <stdio.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+static const char b64_Base64[] =
+ "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
+static const char b64_Pad64 = '=';
+
+/* (From RFC1521 and draft-ietf-dnssec-secext-03.txt)
+ The following encoding technique is taken from RFC 1521 by Borenstein
+ and Freed. It is reproduced here in a slightly edited form for
+ convenience.
+
+ A 65-character subset of US-ASCII is used, enabling 6 bits to be
+ represented per printable character. (The extra 65th character, "=",
+ is used to signify a special processing function.)
+
+ The encoding process represents 24-bit groups of input bits as output
+ strings of 4 encoded characters. Proceeding from left to right, a
+ 24-bit input group is formed by concatenating 3 8-bit input groups.
+ These 24 bits are then treated as 4 concatenated 6-bit groups, each
+ of which is translated into a single digit in the base64 alphabet.
+
+ Each 6-bit group is used as an index into an array of 64 printable
+ characters. The character referenced by the index is placed in the
+ output string.
+
+ Table 1: The Base64 Alphabet
+
+ Value Encoding Value Encoding Value Encoding Value Encoding
+ 0 A 17 R 34 i 51 z
+ 1 B 18 S 35 j 52 0
+ 2 C 19 T 36 k 53 1
+ 3 D 20 U 37 l 54 2
+ 4 E 21 V 38 m 55 3
+ 5 F 22 W 39 n 56 4
+ 6 G 23 X 40 o 57 5
+ 7 H 24 Y 41 p 58 6
+ 8 I 25 Z 42 q 59 7
+ 9 J 26 a 43 r 60 8
+ 10 K 27 b 44 s 61 9
+ 11 L 28 c 45 t 62 +
+ 12 M 29 d 46 u 63 /
+ 13 N 30 e 47 v
+ 14 O 31 f 48 w (pad) =
+ 15 P 32 g 49 x
+ 16 Q 33 h 50 y
+
+ Special processing is performed if fewer than 24 bits are available
+ at the end of the data being encoded. A full encoding quantum is
+ always completed at the end of a quantity. When fewer than 24 input
+ bits are available in an input group, zero bits are added (on the
+ right) to form an integral number of 6-bit groups. Padding at the
+ end of the data is performed using the '=' character.
+
+ Since all base64 input is an integral number of octets, only the
+ -------------------------------------------------
+ following cases can arise:
+
+ (1) the final quantum of encoding input is an integral
+ multiple of 24 bits; here, the final unit of encoded
+ output will be an integral multiple of 4 characters
+ with no "=" padding,
+ (2) the final quantum of encoding input is exactly 8 bits;
+ here, the final unit of encoded output will be two
+ characters followed by two "=" padding characters, or
+ (3) the final quantum of encoding input is exactly 16 bits;
+ here, the final unit of encoded output will be three
+ characters followed by one "=" padding character.
+ */
+
+int
+b64_ntop(u_char const *src, size_t srclength, char *target, size_t targsize)
+{
+ size_t datalength = 0;
+ u_char input[3];
+ u_char output[4];
+ size_t i;
+
+ while (2 < srclength) {
+ input[0] = *src++;
+ input[1] = *src++;
+ input[2] = *src++;
+ srclength -= 3;
+
+ output[0] = input[0] >> 2;
+ output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4);
+ output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6);
+ output[3] = input[2] & 0x3f;
+
+ if (datalength + 4 > targsize)
+ return (-1);
+ target[datalength++] = b64_Base64[output[0]];
+ target[datalength++] = b64_Base64[output[1]];
+ target[datalength++] = b64_Base64[output[2]];
+ target[datalength++] = b64_Base64[output[3]];
+ }
+
+ /* Now we worry about padding. */
+ if (0 != srclength) {
+ /* Get what's left. */
+ input[0] = input[1] = input[2] = '\0';
+ for (i = 0; i < srclength; i++)
+ input[i] = *src++;
+
+ output[0] = input[0] >> 2;
+ output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4);
+ output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6);
+
+ if (datalength + 4 > targsize)
+ return (-1);
+ target[datalength++] = b64_Base64[output[0]];
+ target[datalength++] = b64_Base64[output[1]];
+ if (srclength == 1)
+ target[datalength++] = b64_Pad64;
+ else
+ target[datalength++] = b64_Base64[output[2]];
+ target[datalength++] = b64_Pad64;
+ }
+ if (datalength >= targsize)
+ return (-1);
+ target[datalength] = '\0'; /* Returned value doesn't count \0. */
+ return (datalength);
+}
+
+/* skips all whitespace anywhere.
+ converts characters, four at a time, starting at (or after)
+ src from base - 64 numbers into three 8 bit bytes in the target area.
+ it returns the number of data bytes stored at the target, or -1 on error.
+ */
+
+int
+b64_pton(char const *src, u_char *target, size_t targsize)
+{
+ int state, ch;
+ size_t tarindex;
+ u_char nextbyte;
+ char *pos;
+
+ state = 0;
+ tarindex = 0;
+
+ while ((ch = (unsigned char)*src++) != '\0') {
+ if (isspace(ch)) /* Skip whitespace anywhere. */
+ continue;
+
+ if (ch == b64_Pad64)
+ break;
+
+ pos = strchr(b64_Base64, ch);
+ if (pos == 0) /* A non-base64 character. */
+ return (-1);
+
+ switch (state) {
+ case 0:
+ if (target) {
+ if (tarindex >= targsize)
+ return (-1);
+ target[tarindex] = (pos - b64_Base64) << 2;
+ }
+ state = 1;
+ break;
+ case 1:
+ if (target) {
+ if (tarindex >= targsize)
+ return (-1);
+ target[tarindex] |= (pos - b64_Base64) >> 4;
+ nextbyte = ((pos - b64_Base64) & 0x0f) << 4;
+ if (tarindex + 1 < targsize)
+ target[tarindex+1] = nextbyte;
+ else if (nextbyte)
+ return (-1);
+ }
+ tarindex++;
+ state = 2;
+ break;
+ case 2:
+ if (target) {
+ if (tarindex >= targsize)
+ return (-1);
+ target[tarindex] |= (pos - b64_Base64) >> 2;
+ nextbyte = ((pos - b64_Base64) & 0x03) << 6;
+ if (tarindex + 1 < targsize)
+ target[tarindex+1] = nextbyte;
+ else if (nextbyte)
+ return (-1);
+ }
+ tarindex++;
+ state = 3;
+ break;
+ case 3:
+ if (target) {
+ if (tarindex >= targsize)
+ return (-1);
+ target[tarindex] |= (pos - b64_Base64);
+ }
+ tarindex++;
+ state = 0;
+ break;
+ }
+ }
+
+ /*
+ * We are done decoding Base-64 chars. Let's see if we ended
+ * on a byte boundary, and/or with erroneous trailing characters.
+ */
+
+ if (ch == b64_Pad64) { /* We got a pad char. */
+ ch = (unsigned char)*src++; /* Skip it, get next. */
+ switch (state) {
+ case 0: /* Invalid = in first position */
+ case 1: /* Invalid = in second position */
+ return (-1);
+
+ case 2: /* Valid, means one byte of info */
+ /* Skip any number of spaces. */
+ for (; ch != '\0'; ch = (unsigned char)*src++)
+ if (!isspace(ch))
+ break;
+ /* Make sure there is another trailing = sign. */
+ if (ch != b64_Pad64)
+ return (-1);
+ ch = (unsigned char)*src++; /* Skip the = */
+ /* Fall through to "single trailing =" case. */
+ /* FALLTHROUGH */
+
+ case 3: /* Valid, means two bytes of info */
+ /*
+ * We know this char is an =. Is there anything but
+ * whitespace after it?
+ */
+ for (; ch != '\0'; ch = (unsigned char)*src++)
+ if (!isspace(ch))
+ return (-1);
+
+ /*
+ * Now make sure for cases 2 and 3 that the "extra"
+ * bits that slopped past the last full byte were
+ * zeros. If we don't check them, they become a
+ * subliminal channel.
+ */
+ if (target && tarindex < targsize &&
+ target[tarindex] != 0)
+ return (-1);
+ }
+ } else {
+ /*
+ * We ended by seeing the end of the string. Make sure we
+ * have no partial bytes lying around.
+ */
+ if (state != 0)
+ return (-1);
+ }
+
+ return (tarindex);
+}
+#endif /* !HAVE_B64_NTOP */
+#if !HAVE_EXPLICIT_BZERO
+/* OPENBSD ORIGINAL: lib/libc/string/explicit_bzero.c */
+/*
+ * Public domain.
+ * Written by Ted Unangst
+ */
+
+#include <string.h>
+
+/*
+ * explicit_bzero - don't let the compiler optimize away bzero
+ */
+
+#if HAVE_MEMSET_S
+
+void
+explicit_bzero(void *p, size_t n)
+{
+ if (n == 0)
+ return;
+ (void)memset_s(p, n, 0, n);
+}
+
+#else /* HAVE_MEMSET_S */
+
+/*
+ * Indirect bzero through a volatile pointer to hopefully avoid
+ * dead-store optimisation eliminating the call.
+ */
+static void (* volatile ssh_bzero)(void *, size_t) = bzero;
+
+void
+explicit_bzero(void *p, size_t n)
+{
+ if (n == 0)
+ return;
+ /*
+ * clang -fsanitize=memory needs to intercept memset-like functions
+ * to correctly detect memory initialisation. Make sure one is called
+ * directly since our indirection trick above sucessfully confuses it.
+ */
+#if defined(__has_feature)
+# if __has_feature(memory_sanitizer)
+ memset(p, 0, n);
+# endif
+#endif
+
+ ssh_bzero(p, n);
+}
+
+#endif /* HAVE_MEMSET_S */
+#endif /* !HAVE_EXPLICIT_BZERO */
+#if !HAVE_GETPROGNAME
+/*
+ * Copyright (c) 2016 Nicholas Marriott <nicholas.marriott@gmail.com>
+ * Copyright (c) 2017 Kristaps Dzonsons <kristaps@bsd.lv>
+ * Copyright (c) 2020 Stephen Gregoratto <dev@sgregoratto.me>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER
+ * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
+ * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+
+#include <errno.h>
+
+#if HAVE_GETEXECNAME
+#include <stdlib.h>
+const char *
+getprogname(void)
+{
+ return getexecname();
+}
+#elif HAVE_PROGRAM_INVOCATION_SHORT_NAME
+const char *
+getprogname(void)
+{
+ return (program_invocation_short_name);
+}
+#elif HAVE___PROGNAME
+const char *
+getprogname(void)
+{
+ extern char *__progname;
+
+ return (__progname);
+}
+#else
+#error No getprogname available.
+#endif
+#endif /* !HAVE_GETPROGNAME */
+#if !HAVE_MD5
+/*
+ * This code implements the MD5 message-digest algorithm.
+ * The algorithm is due to Ron Rivest. This code was
+ * written by Colin Plumb in 1993, no copyright is claimed.
+ * This code is in the public domain; do with it what you wish.
+ *
+ * Equivalent code is available from RSA Data Security, Inc.
+ * This code has been tested against that, and is equivalent,
+ * except that you don't need to include two pages of legalese
+ * with every copy.
+ *
+ * To compute the message digest of a chunk of bytes, declare an
+ * MD5Context structure, pass it to MD5Init, call MD5Update as
+ * needed on buffers full of bytes, and then call MD5Final, which
+ * will fill a supplied 16-byte array with the digest.
+ */
+
+#include <sys/types.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define PUT_64BIT_LE(cp, value) do { \
+ (cp)[7] = (value) >> 56; \
+ (cp)[6] = (value) >> 48; \
+ (cp)[5] = (value) >> 40; \
+ (cp)[4] = (value) >> 32; \
+ (cp)[3] = (value) >> 24; \
+ (cp)[2] = (value) >> 16; \
+ (cp)[1] = (value) >> 8; \
+ (cp)[0] = (value); } while (0)
+
+#define PUT_32BIT_LE(cp, value) do { \
+ (cp)[3] = (value) >> 24; \
+ (cp)[2] = (value) >> 16; \
+ (cp)[1] = (value) >> 8; \
+ (cp)[0] = (value); } while (0)
+
+static u_int8_t PADDING[MD5_BLOCK_LENGTH] = {
+ 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+};
+
+/*
+ * Start MD5 accumulation. Set bit count to 0 and buffer to mysterious
+ * initialization constants.
+ */
+void
+MD5Init(MD5_CTX *ctx)
+{
+ ctx->count = 0;
+ ctx->state[0] = 0x67452301;
+ ctx->state[1] = 0xefcdab89;
+ ctx->state[2] = 0x98badcfe;
+ ctx->state[3] = 0x10325476;
+}
+
+/*
+ * Update context to reflect the concatenation of another buffer full
+ * of bytes.
+ */
+void
+MD5Update(MD5_CTX *ctx, const unsigned char *input, size_t len)
+{
+ size_t have, need;
+
+ /* Check how many bytes we already have and how many more we need. */
+ have = (size_t)((ctx->count >> 3) & (MD5_BLOCK_LENGTH - 1));
+ need = MD5_BLOCK_LENGTH - have;
+
+ /* Update bitcount */
+ ctx->count += (u_int64_t)len << 3;
+
+ if (len >= need) {
+ if (have != 0) {
+ memcpy(ctx->buffer + have, input, need);
+ MD5Transform(ctx->state, ctx->buffer);
+ input += need;
+ len -= need;
+ have = 0;
+ }
+
+ /* Process data in MD5_BLOCK_LENGTH-byte chunks. */
+ while (len >= MD5_BLOCK_LENGTH) {
+ MD5Transform(ctx->state, input);
+ input += MD5_BLOCK_LENGTH;
+ len -= MD5_BLOCK_LENGTH;
+ }
+ }
+
+ /* Handle any remaining bytes of data. */
+ if (len != 0)
+ memcpy(ctx->buffer + have, input, len);
+}
+
+/*
+ * Pad pad to 64-byte boundary with the bit pattern
+ * 1 0* (64-bit count of bits processed, MSB-first)
+ */
+void
+MD5Pad(MD5_CTX *ctx)
+{
+ u_int8_t count[8];
+ size_t padlen;
+
+ /* Convert count to 8 bytes in little endian order. */
+ PUT_64BIT_LE(count, ctx->count);
+
+ /* Pad out to 56 mod 64. */
+ padlen = MD5_BLOCK_LENGTH -
+ ((ctx->count >> 3) & (MD5_BLOCK_LENGTH - 1));
+ if (padlen < 1 + 8)
+ padlen += MD5_BLOCK_LENGTH;
+ MD5Update(ctx, PADDING, padlen - 8); /* padlen - 8 <= 64 */
+ MD5Update(ctx, count, 8);
+}
+
+/*
+ * Final wrapup--call MD5Pad, fill in digest and zero out ctx.
+ */
+void
+MD5Final(unsigned char digest[MD5_DIGEST_LENGTH], MD5_CTX *ctx)
+{
+ int i;
+
+ MD5Pad(ctx);
+ for (i = 0; i < 4; i++)
+ PUT_32BIT_LE(digest + i * 4, ctx->state[i]);
+ memset(ctx, 0, sizeof(*ctx));
+}
+
+
+/* The four core functions - F1 is optimized somewhat */
+
+/* #define F1(x, y, z) (x & y | ~x & z) */
+#define F1(x, y, z) (z ^ (x & (y ^ z)))
+#define F2(x, y, z) F1(z, x, y)
+#define F3(x, y, z) (x ^ y ^ z)
+#define F4(x, y, z) (y ^ (x | ~z))
+
+/* This is the central step in the MD5 algorithm. */
+#define MD5STEP(f, w, x, y, z, data, s) \
+ ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x )
+
+/*
+ * The core of the MD5 algorithm, this alters an existing MD5 hash to
+ * reflect the addition of 16 longwords of new data. MD5Update blocks
+ * the data and converts bytes into longwords for this routine.
+ */
+void
+MD5Transform(u_int32_t state[4], const u_int8_t block[MD5_BLOCK_LENGTH])
+{
+ u_int32_t a, b, c, d, in[MD5_BLOCK_LENGTH / 4];
+
+#if BYTE_ORDER == LITTLE_ENDIAN
+ memcpy(in, block, sizeof(in));
+#else
+ for (a = 0; a < MD5_BLOCK_LENGTH / 4; a++) {
+ in[a] = (u_int32_t)(
+ (u_int32_t)(block[a * 4 + 0]) |
+ (u_int32_t)(block[a * 4 + 1]) << 8 |
+ (u_int32_t)(block[a * 4 + 2]) << 16 |
+ (u_int32_t)(block[a * 4 + 3]) << 24);
+ }
+#endif
+
+ a = state[0];
+ b = state[1];
+ c = state[2];
+ d = state[3];
+
+ MD5STEP(F1, a, b, c, d, in[ 0] + 0xd76aa478, 7);
+ MD5STEP(F1, d, a, b, c, in[ 1] + 0xe8c7b756, 12);
+ MD5STEP(F1, c, d, a, b, in[ 2] + 0x242070db, 17);
+ MD5STEP(F1, b, c, d, a, in[ 3] + 0xc1bdceee, 22);
+ MD5STEP(F1, a, b, c, d, in[ 4] + 0xf57c0faf, 7);
+ MD5STEP(F1, d, a, b, c, in[ 5] + 0x4787c62a, 12);
+ MD5STEP(F1, c, d, a, b, in[ 6] + 0xa8304613, 17);
+ MD5STEP(F1, b, c, d, a, in[ 7] + 0xfd469501, 22);
+ MD5STEP(F1, a, b, c, d, in[ 8] + 0x698098d8, 7);
+ MD5STEP(F1, d, a, b, c, in[ 9] + 0x8b44f7af, 12);
+ MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
+ MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
+ MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
+ MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
+ MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
+ MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
+
+ MD5STEP(F2, a, b, c, d, in[ 1] + 0xf61e2562, 5);
+ MD5STEP(F2, d, a, b, c, in[ 6] + 0xc040b340, 9);
+ MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
+ MD5STEP(F2, b, c, d, a, in[ 0] + 0xe9b6c7aa, 20);
+ MD5STEP(F2, a, b, c, d, in[ 5] + 0xd62f105d, 5);
+ MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
+ MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
+ MD5STEP(F2, b, c, d, a, in[ 4] + 0xe7d3fbc8, 20);
+ MD5STEP(F2, a, b, c, d, in[ 9] + 0x21e1cde6, 5);
+ MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
+ MD5STEP(F2, c, d, a, b, in[ 3] + 0xf4d50d87, 14);
+ MD5STEP(F2, b, c, d, a, in[ 8] + 0x455a14ed, 20);
+ MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
+ MD5STEP(F2, d, a, b, c, in[ 2] + 0xfcefa3f8, 9);
+ MD5STEP(F2, c, d, a, b, in[ 7] + 0x676f02d9, 14);
+ MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
+
+ MD5STEP(F3, a, b, c, d, in[ 5] + 0xfffa3942, 4);
+ MD5STEP(F3, d, a, b, c, in[ 8] + 0x8771f681, 11);
+ MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
+ MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
+ MD5STEP(F3, a, b, c, d, in[ 1] + 0xa4beea44, 4);
+ MD5STEP(F3, d, a, b, c, in[ 4] + 0x4bdecfa9, 11);
+ MD5STEP(F3, c, d, a, b, in[ 7] + 0xf6bb4b60, 16);
+ MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
+ MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
+ MD5STEP(F3, d, a, b, c, in[ 0] + 0xeaa127fa, 11);
+ MD5STEP(F3, c, d, a, b, in[ 3] + 0xd4ef3085, 16);
+ MD5STEP(F3, b, c, d, a, in[ 6] + 0x04881d05, 23);
+ MD5STEP(F3, a, b, c, d, in[ 9] + 0xd9d4d039, 4);
+ MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
+ MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
+ MD5STEP(F3, b, c, d, a, in[2 ] + 0xc4ac5665, 23);
+
+ MD5STEP(F4, a, b, c, d, in[ 0] + 0xf4292244, 6);
+ MD5STEP(F4, d, a, b, c, in[7 ] + 0x432aff97, 10);
+ MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
+ MD5STEP(F4, b, c, d, a, in[5 ] + 0xfc93a039, 21);
+ MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
+ MD5STEP(F4, d, a, b, c, in[3 ] + 0x8f0ccc92, 10);
+ MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
+ MD5STEP(F4, b, c, d, a, in[1 ] + 0x85845dd1, 21);
+ MD5STEP(F4, a, b, c, d, in[8 ] + 0x6fa87e4f, 6);
+ MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
+ MD5STEP(F4, c, d, a, b, in[6 ] + 0xa3014314, 15);
+ MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
+ MD5STEP(F4, a, b, c, d, in[4 ] + 0xf7537e82, 6);
+ MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
+ MD5STEP(F4, c, d, a, b, in[2 ] + 0x2ad7d2bb, 15);
+ MD5STEP(F4, b, c, d, a, in[9 ] + 0xeb86d391, 21);
+
+ state[0] += a;
+ state[1] += b;
+ state[2] += c;
+ state[3] += d;
+}
+
+char *
+MD5End(MD5_CTX *ctx, char *buf)
+{
+ int i;
+ unsigned char digest[MD5_DIGEST_LENGTH];
+ static const char hex[]="0123456789abcdef";
+
+ if (!buf)
+ buf = malloc(2*MD5_DIGEST_LENGTH + 1);
+ if (!buf)
+ return 0;
+ MD5Final(digest, ctx);
+ for (i = 0; i < MD5_DIGEST_LENGTH; i++) {
+ buf[i+i] = hex[digest[i] >> 4];
+ buf[i+i+1] = hex[digest[i] & 0x0f];
+ }
+ buf[i+i] = '\0';
+ return buf;
+}
+#endif /* !HAVE_MD5 */
+#if !HAVE_MEMMEM
+/*-
+ * Copyright (c) 2005 Pascal Gloor <pascal.gloor@spale.com>
+ *
+ * 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.
+ * 3. The name of the author may not be used to endorse or promote
+ * products derived from this software without specific prior written
+ * permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 OR
+ * CONTRIBUTORS 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.
+ */
+/*
+ * Find the first occurrence of the byte string s in byte string l.
+ */
+void *
+memmem(const void *l, size_t l_len, const void *s, size_t s_len)
+{
+ const char *cur, *last;
+ const char *cl = l;
+ const char *cs = s;
+
+ /* a zero length needle should just return the haystack */
+ if (l_len == 0)
+ return (void *)cl;
+
+ /* "s" must be smaller or equal to "l" */
+ if (l_len < s_len)
+ return NULL;
+
+ /* special case where s_len == 1 */
+ if (s_len == 1)
+ return memchr(l, *cs, l_len);
+
+ /* the last position where its possible to find "s" in "l" */
+ last = cl + l_len - s_len;
+
+ for (cur = cl; cur <= last; cur++)
+ if (cur[0] == cs[0] && memcmp(cur, cs, s_len) == 0)
+ return (void *)cur;
+
+ return NULL;
+}
+#endif /* !HAVE_MEMMEM */
+#if !HAVE_MEMRCHR
+/*
+ * Copyright (c) 2007 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ */
+
+#include <string.h>
+
+/*
+ * Reverse memchr()
+ * Find the last occurrence of 'c' in the buffer 's' of size 'n'.
+ */
+void *
+memrchr(const void *s, int c, size_t n)
+{
+ const unsigned char *cp;
+
+ if (n != 0) {
+ cp = (unsigned char *)s + n;
+ do {
+ if (*(--cp) == (unsigned char)c)
+ return((void *)cp);
+ } while (--n != 0);
+ }
+ return(NULL);
+}
+#endif /* !HAVE_MEMRCHR */
+#if !HAVE_READPASSPHRASE
+/*
+ * Original: readpassphrase.c in OpenSSH portable
+ */
+/*
+ * Copyright (c) 2000-2002, 2007, 2010
+ * Todd C. Miller <millert@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Sponsored in part by the Defense Advanced Research Projects
+ * Agency (DARPA) and Air Force Research Laboratory, Air Force
+ * Materiel Command, USAF, under agreement number F39502-99-1-0512.
+ */
+
+#include <ctype.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <paths.h>
+#include <pwd.h>
+#include <signal.h>
+#include <string.h>
+#include <termios.h>
+#include <unistd.h>
+
+#if defined(_NSIG)
+static volatile sig_atomic_t readpassphrase_signo[_NSIG];
+#else
+static volatile sig_atomic_t readpassphrase_signo[NSIG];
+#endif
+
+static void
+readpassphrase_handler(int s)
+{
+
+ readpassphrase_signo[s] = 1;
+}
+
+char *
+readpassphrase(const char *prompt, char *buf, size_t bufsiz, int flags)
+{
+ ssize_t nr;
+ int input, output, save_errno, i, need_restart;
+ char ch, *p, *end;
+ struct termios term, oterm;
+ struct sigaction sa, savealrm, saveint, savehup, savequit, saveterm;
+ struct sigaction savetstp, savettin, savettou, savepipe;
+/* If we don't have TCSASOFT define it so that ORing it it below is a no-op. */
+#ifndef TCSASOFT
+ const int tcasoft = 0;
+#else
+ const int tcasoft = TCSASOFT;
+#endif
+
+ /* I suppose we could alloc on demand in this case (XXX). */
+ if (bufsiz == 0) {
+ errno = EINVAL;
+ return(NULL);
+ }
+
+restart:
+ for (i = 0; i < _NSIG; i++)
+ readpassphrase_signo[i] = 0;
+ nr = -1;
+ save_errno = 0;
+ need_restart = 0;
+ /*
+ * Read and write to /dev/tty if available. If not, read from
+ * stdin and write to stderr unless a tty is required.
+ */
+ if ((flags & RPP_STDIN) ||
+ (input = output = open(_PATH_TTY, O_RDWR)) == -1) {
+ if (flags & RPP_REQUIRE_TTY) {
+ errno = ENOTTY;
+ return(NULL);
+ }
+ input = STDIN_FILENO;
+ output = STDERR_FILENO;
+ }
+
+ /*
+ * Turn off echo if possible.
+ * If we are using a tty but are not the foreground pgrp this will
+ * generate SIGTTOU, so do it *before* installing the signal handlers.
+ */
+ if (input != STDIN_FILENO && tcgetattr(input, &oterm) == 0) {
+ memcpy(&term, &oterm, sizeof(term));
+ if (!(flags & RPP_ECHO_ON))
+ term.c_lflag &= ~(ECHO | ECHONL);
+#ifdef VSTATUS
+ if (term.c_cc[VSTATUS] != _POSIX_VDISABLE)
+ term.c_cc[VSTATUS] = _POSIX_VDISABLE;
+#endif
+ (void)tcsetattr(input, TCSAFLUSH|tcasoft, &term);
+ } else {
+ memset(&term, 0, sizeof(term));
+ term.c_lflag |= ECHO;
+ memset(&oterm, 0, sizeof(oterm));
+ oterm.c_lflag |= ECHO;
+ }
+
+ /*
+ * Catch signals that would otherwise cause the user to end
+ * up with echo turned off in the shell. Don't worry about
+ * things like SIGXCPU and SIGVTALRM for now.
+ */
+ sigemptyset(&sa.sa_mask);
+ sa.sa_flags = 0; /* don't restart system calls */
+ sa.sa_handler = readpassphrase_handler;
+ (void)sigaction(SIGALRM, &sa, &savealrm);
+ (void)sigaction(SIGHUP, &sa, &savehup);
+ (void)sigaction(SIGINT, &sa, &saveint);
+ (void)sigaction(SIGPIPE, &sa, &savepipe);
+ (void)sigaction(SIGQUIT, &sa, &savequit);
+ (void)sigaction(SIGTERM, &sa, &saveterm);
+ (void)sigaction(SIGTSTP, &sa, &savetstp);
+ (void)sigaction(SIGTTIN, &sa, &savettin);
+ (void)sigaction(SIGTTOU, &sa, &savettou);
+
+ if (!(flags & RPP_STDIN))
+ (void)write(output, prompt, strlen(prompt));
+ end = buf + bufsiz - 1;
+ p = buf;
+ while ((nr = read(input, &ch, 1)) == 1 && ch != '\n' && ch != '\r') {
+ if (p < end) {
+ if ((flags & RPP_SEVENBIT))
+ ch &= 0x7f;
+ if (isalpha((unsigned char)ch)) {
+ if ((flags & RPP_FORCELOWER))
+ ch = (char)tolower((unsigned char)ch);
+ if ((flags & RPP_FORCEUPPER))
+ ch = (char)toupper((unsigned char)ch);
+ }
+ *p++ = ch;
+ }
+ }
+ *p = '\0';
+ save_errno = errno;
+ if (!(term.c_lflag & ECHO))
+ (void)write(output, "\n", 1);
+
+ /* Restore old terminal settings and signals. */
+ if (memcmp(&term, &oterm, sizeof(term)) != 0) {
+ const int sigttou = readpassphrase_signo[SIGTTOU];
+
+ /* Ignore SIGTTOU generated when we are not the fg pgrp. */
+ while (tcsetattr(input, TCSAFLUSH|tcasoft, &oterm) == -1 &&
+ errno == EINTR && !readpassphrase_signo[SIGTTOU])
+ continue;
+ readpassphrase_signo[SIGTTOU] = sigttou;
+ }
+ (void)sigaction(SIGALRM, &savealrm, NULL);
+ (void)sigaction(SIGHUP, &savehup, NULL);
+ (void)sigaction(SIGINT, &saveint, NULL);
+ (void)sigaction(SIGQUIT, &savequit, NULL);
+ (void)sigaction(SIGPIPE, &savepipe, NULL);
+ (void)sigaction(SIGTERM, &saveterm, NULL);
+ (void)sigaction(SIGTSTP, &savetstp, NULL);
+ (void)sigaction(SIGTTIN, &savettin, NULL);
+ (void)sigaction(SIGTTOU, &savettou, NULL);
+ if (input != STDIN_FILENO)
+ (void)close(input);
+
+ /*
+ * If we were interrupted by a signal, resend it to ourselves
+ * now that we have restored the signal handlers.
+ */
+ for (i = 0; i < _NSIG; i++) {
+ if (readpassphrase_signo[i]) {
+ kill(getpid(), i);
+ switch (i) {
+ case SIGTSTP:
+ case SIGTTIN:
+ case SIGTTOU:
+ need_restart = 1;
+ }
+ }
+ }
+ if (need_restart)
+ goto restart;
+
+ if (save_errno)
+ errno = save_errno;
+ return(nr == -1 ? NULL : buf);
+}
+#endif /* !HAVE_READPASSPHRASE */
+#if !HAVE_REALLOCARRAY
+/*
+ * Copyright (c) 2008 Otto Moerbeek <otto@drijf.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+#include <errno.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+/*
+ * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
+ * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
+ */
+#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4))
+
+void *
+reallocarray(void *optr, size_t nmemb, size_t size)
+{
+ if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
+ nmemb > 0 && SIZE_MAX / nmemb < size) {
+ errno = ENOMEM;
+ return NULL;
+ }
+ return realloc(optr, size * nmemb);
+}
+#endif /* !HAVE_REALLOCARRAY */
+#if !HAVE_RECALLOCARRAY
+/*
+ * Copyright (c) 2008, 2017 Otto Moerbeek <otto@drijf.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+/* OPENBSD ORIGINAL: lib/libc/stdlib/recallocarray.c */
+
+#include <errno.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <unistd.h>
+
+/*
+ * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
+ * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
+ */
+#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4))
+
+void *
+recallocarray(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size)
+{
+ size_t oldsize, newsize;
+ void *newptr;
+
+ if (ptr == NULL)
+ return calloc(newnmemb, size);
+
+ if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
+ newnmemb > 0 && SIZE_MAX / newnmemb < size) {
+ errno = ENOMEM;
+ return NULL;
+ }
+ newsize = newnmemb * size;
+
+ if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
+ oldnmemb > 0 && SIZE_MAX / oldnmemb < size) {
+ errno = EINVAL;
+ return NULL;
+ }
+ oldsize = oldnmemb * size;
+
+ /*
+ * Don't bother too much if we're shrinking just a bit,
+ * we do not shrink for series of small steps, oh well.
+ */
+ if (newsize <= oldsize) {
+ size_t d = oldsize - newsize;
+
+ if (d < oldsize / 2 && d < (size_t)getpagesize()) {
+ memset((char *)ptr + newsize, 0, d);
+ return ptr;
+ }
+ }
+
+ newptr = malloc(newsize);
+ if (newptr == NULL)
+ return NULL;
+
+ if (newsize > oldsize) {
+ memcpy(newptr, ptr, oldsize);
+ memset((char *)newptr + oldsize, 0, newsize - oldsize);
+ } else
+ memcpy(newptr, ptr, newsize);
+
+ explicit_bzero(ptr, oldsize);
+ free(ptr);
+
+ return newptr;
+}
+#endif /* !HAVE_RECALLOCARRAY */
+#if !HAVE_STRLCAT
+/*
+ * Copyright (c) 1998 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+#include <string.h>
+
+/*
+ * Appends src to string dst of size siz (unlike strncat, siz is the
+ * full size of dst, not space left). At most siz-1 characters
+ * will be copied. Always NUL terminates (unless siz <= strlen(dst)).
+ * Returns strlen(src) + MIN(siz, strlen(initial dst)).
+ * If retval >= siz, truncation occurred.
+ */
+size_t
+strlcat(char *dst, const char *src, size_t siz)
+{
+ char *d = dst;
+ const char *s = src;
+ size_t n = siz;
+ size_t dlen;
+
+ /* Find the end of dst and adjust bytes left but don't go past end */
+ while (n-- != 0 && *d != '\0')
+ d++;
+ dlen = d - dst;
+ n = siz - dlen;
+
+ if (n == 0)
+ return(dlen + strlen(s));
+ while (*s != '\0') {
+ if (n != 1) {
+ *d++ = *s;
+ n--;
+ }
+ s++;
+ }
+ *d = '\0';
+
+ return(dlen + (s - src)); /* count does not include NUL */
+}
+#endif /* !HAVE_STRLCAT */
+#if !HAVE_STRLCPY
+/*
+ * Copyright (c) 1998 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+#include <string.h>
+
+/*
+ * Copy src to string dst of size siz. At most siz-1 characters
+ * will be copied. Always NUL terminates (unless siz == 0).
+ * Returns strlen(src); if retval >= siz, truncation occurred.
+ */
+size_t
+strlcpy(char *dst, const char *src, size_t siz)
+{
+ char *d = dst;
+ const char *s = src;
+ size_t n = siz;
+
+ /* Copy as many bytes as will fit */
+ if (n != 0) {
+ while (--n != 0) {
+ if ((*d++ = *s++) == '\0')
+ break;
+ }
+ }
+
+ /* Not enough room in dst, add NUL and traverse rest of src */
+ if (n == 0) {
+ if (siz != 0)
+ *d = '\0'; /* NUL-terminate dst */
+ while (*s++)
+ ;
+ }
+
+ return(s - src - 1); /* count does not include NUL */
+}
+#endif /* !HAVE_STRLCPY */
+#if !HAVE_STRNDUP
+/* $OpenBSD$ */
+/*
+ * Copyright (c) 2010 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+char *
+strndup(const char *str, size_t maxlen)
+{
+ char *copy;
+ size_t len;
+
+ len = strnlen(str, maxlen);
+ copy = malloc(len + 1);
+ if (copy != NULL) {
+ (void)memcpy(copy, str, len);
+ copy[len] = '\0';
+ }
+
+ return copy;
+}
+#endif /* !HAVE_STRNDUP */
+#if !HAVE_STRNLEN
+/* $OpenBSD$ */
+
+/*
+ * Copyright (c) 2010 Todd C. Miller <Todd.Miller@courtesan.com>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/types.h>
+#include <string.h>
+
+size_t
+strnlen(const char *str, size_t maxlen)
+{
+ const char *cp;
+
+ for (cp = str; maxlen != 0 && *cp != '\0'; cp++, maxlen--)
+ ;
+
+ return (size_t)(cp - str);
+}
+#endif /* !HAVE_STRNLEN */
+#if !HAVE_STRTONUM
+/*
+ * Copyright (c) 2004 Ted Unangst and Todd Miller
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <limits.h>
+#include <stdlib.h>
+
+#define INVALID 1
+#define TOOSMALL 2
+#define TOOLARGE 3
+
+long long
+strtonum(const char *numstr, long long minval, long long maxval,
+ const char **errstrp)
+{
+ long long ll = 0;
+ int error = 0;
+ char *ep;
+ struct errval {
+ const char *errstr;
+ int err;
+ } ev[4] = {
+ { NULL, 0 },
+ { "invalid", EINVAL },
+ { "too small", ERANGE },
+ { "too large", ERANGE },
+ };
+
+ ev[0].err = errno;
+ errno = 0;
+ if (minval > maxval) {
+ error = INVALID;
+ } else {
+ ll = strtoll(numstr, &ep, 10);
+ if (numstr == ep || *ep != '\0')
+ error = INVALID;
+ else if ((ll == LLONG_MIN && errno == ERANGE) || ll < minval)
+ error = TOOSMALL;
+ else if ((ll == LLONG_MAX && errno == ERANGE) || ll > maxval)
+ error = TOOLARGE;
+ }
+ if (errstrp != NULL)
+ *errstrp = ev[error].errstr;
+ errno = ev[error].err;
+ if (error)
+ ll = 0;
+
+ return (ll);
+}
+#endif /* !HAVE_STRTONUM */
diff --git a/configure b/configure
@@ -0,0 +1,1993 @@
+#! /bin/sh
+#
+# Copyright (c) 2014, 2015, 2016 Ingo Schwarze <schwarze@openbsd.org>
+# Copyright (c) 2017, 2018 Kristaps Dzonsons <kristaps@bsd.lv>
+#
+# Permission to use, copy, modify, and distribute this software for any
+# purpose with or without fee is hereby granted, provided that the above
+# copyright notice and this permission notice appear in all copies.
+#
+# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+# ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+# ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+# OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+
+OCONFIGURE_VERSION="0.1.17"
+
+#
+# This script outputs two files: config.h and Makefile.configure.
+# It tries to read from configure.local, which contains predefined
+# values we won't autoconfigure.
+#
+# If you want to use configure with your project, have your GNUmakefile
+# or BSDmakefile---whichever---try to import/include Makefile.configure
+# at the beginning of the file.
+#
+# Like so (note no quotes, no period, etc.):
+#
+# include Makefile.configure
+#
+# If it exists, configure was run; otherwise, it wasn't.
+#
+# You'll probably want to change parts of this file. I've noted the
+# parts that you'll probably change in the section documentation.
+#
+# See https://github.com/kristapsdz/oconfigure for more.
+
+set -e
+
+#----------------------------------------------------------------------
+# Prepare for running: move aside previous configure runs.
+# Output file descriptor usage:
+# 1 (stdout): config.h or Makefile.configure
+# 2 (stderr): original stderr, usually to the console
+# 3: config.log
+# You DO NOT want to change this.
+#----------------------------------------------------------------------
+
+[ -w config.log ] && mv config.log config.log.old
+[ -w config.h ] && mv config.h config.h.old
+
+exec 3> config.log
+echo "config.log: writing..."
+
+#----------------------------------------------------------------------
+# Initialize all variables here such that nothing can leak in from the
+# environment except for CC and CFLAGS, which we might have passed in.
+#----------------------------------------------------------------------
+
+CC=`printf "all:\\n\\t@echo \\\$(CC)\\n" | make -sf -`
+CFLAGS=`printf "all:\\n\\t@echo \\\$(CFLAGS)\\n" | make -sf -`
+CFLAGS="${CFLAGS} -g -W -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes"
+CFLAGS="${CFLAGS} -Wwrite-strings -Wno-unused-parameter"
+LDADD=
+CPPFLAGS=
+LDFLAGS=
+DESTDIR=
+PREFIX="/usr/local"
+BINDIR=
+SBINDIR=
+INCLUDEDIR=
+LIBDIR=
+MANDIR=
+SHAREDIR=
+INSTALL="install"
+INSTALL_PROGRAM=
+INSTALL_LIB=
+INSTALL_MAN=
+INSTALL_DATA=
+
+#----------------------------------------------------------------------
+# Allow certain variables to be overriden on the command line.
+#----------------------------------------------------------------------
+
+for keyvals in "$@"
+do
+ key=`echo $keyvals | cut -s -d '=' -f 1`
+ if [ -z "$key" ]
+ then
+ echo "$0: invalid key-value: $keyvals" 1>&2
+ exit 1
+ fi
+ val=`echo $keyvals | cut -d '=' -f 2-`
+ case "$key" in
+ LDADD)
+ LDADD="$val" ;;
+ LDFLAGS)
+ LDFLAGS="$val" ;;
+ CPPFLAGS)
+ CPPFLAGS="$val" ;;
+ DESTDIR)
+ DESTDIR="$val" ;;
+ PREFIX)
+ PREFIX="$val" ;;
+ MANDIR)
+ MANDIR="$val" ;;
+ LIBDIR)
+ LIBDIR="$val" ;;
+ BINDIR)
+ BINDIR="$val" ;;
+ SHAREDIR)
+ SHAREDIR="$val" ;;
+ SBINDIR)
+ SBINDIR="$val" ;;
+ INCLUDEDIR)
+ INCLUDEDIR="$val" ;;
+ *)
+ echo "$0: invalid key: $key" 1>&2
+ exit 1
+ esac
+done
+
+
+#----------------------------------------------------------------------
+# These are the values that will be pushed into config.h after we test
+# for whether they're supported or not.
+# Each of these must have a runtest(), below.
+# Please sort by alpha, for clarity.
+# You WANT to change this.
+#----------------------------------------------------------------------
+
+HAVE_ARC4RANDOM=
+HAVE_B64_NTOP=
+HAVE_CAPSICUM=
+HAVE_ENDIAN_H=
+HAVE_ERR=
+HAVE_EXPLICIT_BZERO=
+HAVE_GETEXECNAME=
+HAVE_GETPROGNAME=
+HAVE_INFTIM=
+HAVE_MD5=
+HAVE_MEMMEM=
+HAVE_MEMRCHR=
+HAVE_MEMSET_S=
+HAVE_PATH_MAX=
+HAVE_PLEDGE=
+HAVE_PROGRAM_INVOCATION_SHORT_NAME=
+HAVE_READPASSPHRASE=
+HAVE_REALLOCARRAY=
+HAVE_RECALLOCARRAY=
+HAVE_SANDBOX_INIT=
+HAVE_SECCOMP_FILTER=
+HAVE_SOCK_NONBLOCK=
+HAVE_STRLCAT=
+HAVE_STRLCPY=
+HAVE_STRNDUP=
+HAVE_STRNLEN=
+HAVE_STRTONUM=
+HAVE_SYS_QUEUE=
+HAVE_SYS_TREE=
+HAVE_SYSTRACE=
+HAVE_UNVEIL=
+HAVE_ZLIB=
+HAVE___PROGNAME=
+
+#----------------------------------------------------------------------
+# Allow configure.local to override all variables, default settings,
+# command-line arguments, and tested features, above.
+# You PROBABLY DO NOT want to change this.
+#----------------------------------------------------------------------
+
+if [ -r ./configure.local ]; then
+ echo "configure.local: reading..." 1>&2
+ echo "configure.local: reading..." 1>&3
+ cat ./configure.local 1>&3
+ . ./configure.local
+else
+ echo "configure.local: no (fully automatic configuration)" 1>&2
+ echo "configure.local: no (fully automatic configuration)" 1>&3
+fi
+
+echo 1>&3
+
+#----------------------------------------------------------------------
+# Infrastructure for running tests.
+# These consists of a series of functions that will attempt to run the
+# given test file and record its exit into a HAVE_xxx variable.
+# You DO NOT want to change this.
+#----------------------------------------------------------------------
+
+COMP="${CC} ${CFLAGS} ${CPPFLAGS} -Wno-unused -Werror"
+
+# Check whether this HAVE_ setting is manually overridden.
+# If yes, use the override, if no, do not decide anything yet.
+# Arguments: lower-case test name, manual value
+
+ismanual() {
+ [ -z "${3}" ] && return 1
+ echo "${1}: manual (HAVE_${2}=${3})" 1>&2
+ echo "${1}: manual (HAVE_${2}=${3})" 1>&3
+ echo 1>&3
+ return 0
+}
+
+# Run a single autoconfiguration test.
+# In case of success, enable the feature.
+# In case of failure, do not decide anything yet.
+# Arguments: lower-case test name, upper-case test name, additional
+# CFLAGS, additional LIBS.
+
+singletest() {
+ extralib=""
+ cat 1>&3 << __HEREDOC__
+${1}: testing...
+${COMP} -DTEST_${2} ${3} -o test-${1} tests.c ${4}
+__HEREDOC__
+ if ${COMP} -DTEST_${2} ${3} -o "test-${1}" tests.c ${4} 1>&3 2>&3; then
+ echo "${1}: ${CC} succeeded" 1>&3
+ else
+ if [ -n "${5}" ] ; then
+ echo "${1}: ${CC} failed with $? (retrying)" 1>&3
+ cat 1>&3 << __HEREDOC__
+${1}: testing...
+${COMP} -DTEST_${2} ${3} -o test-${1} tests.c ${5}
+__HEREDOC__
+ if ${COMP} -DTEST_${2} ${3} -o "test-${1}" tests.c ${5} 1>&3 2>&3; then
+ echo "${1}: ${CC} succeeded" 1>&3
+ extralib="(with ${5})"
+ else
+ echo "${1}: ${CC} failed with $?" 1>&3
+ echo 1>&3
+ return 1
+ fi
+ else
+ echo "${1}: ${CC} failed with $?" 1>&3
+ echo 1>&3
+ return 1
+ fi
+ fi
+
+ echo "${1}: yes ${extralib}" 1>&2
+ echo "${1}: yes ${extralib}" 1>&3
+ echo 1>&3
+ eval HAVE_${2}=1
+ rm "test-${1}"
+ return 0
+
+ # Don't actually run the test: none of our tests check for
+ # run-time behaviour.
+ # if ./test-${1} 1>&3 2>&3; then
+ # echo "${1}: yes" 1>&2
+ # echo "${1}: yes" 1>&3
+ # echo 1>&3
+ # eval HAVE_${2}=1
+ # rm "test-${1}"
+ # return 0
+ # else
+ # echo "${1}: execution failed with $?" 1>&3
+ # echo 1>&3
+ # rm "test-${1}"
+ # return 1
+ # fi
+}
+
+# Run a complete autoconfiguration test, including the check for
+# a manual override and disabling the feature on failure.
+# Arguments: lower case name, upper case name, additional CFLAGS,
+# additional LDADD, alternative LDADD.
+
+runtest() {
+ eval _manual=\${HAVE_${2}}
+ ismanual "${1}" "${2}" "${_manual}" && return 0
+ singletest "${1}" "${2}" "${3}" "${4}" "${5}" && return 0
+ echo "${1}: no" 1>&2
+ eval HAVE_${2}=0
+ return 1
+}
+
+#----------------------------------------------------------------------
+# Begin running the tests themselves.
+# All of your tests must be defined here.
+# Please sort as the HAVE_xxxx values were defined.
+# You WANT to change this.
+# It consists of the following columns:
+# runtest
+# (1) test file
+# (2) macro to set
+# (3) argument to cc *before* -o
+# (4) argument to cc *after*
+# (5) alternative argument to cc *after*
+#----------------------------------------------------------------------
+
+runtest arc4random ARC4RANDOM || true
+runtest b64_ntop B64_NTOP "" "" "-lresolv" || true
+runtest capsicum CAPSICUM || true
+runtest endian_h ENDIAN_H || true
+runtest err ERR || true
+runtest explicit_bzero EXPLICIT_BZERO || true
+runtest getexecname GETEXECNAME || true
+runtest getprogname GETPROGNAME || true
+runtest INFTIM INFTIM || true
+runtest md5 MD5 "" "" "-lmd" || true
+runtest memmem MEMMEM || true
+runtest memrchr MEMRCHR || true
+runtest memset_s MEMSET_S || true
+runtest PATH_MAX PATH_MAX || true
+runtest pledge PLEDGE || true
+runtest program_invocation_short_name PROGRAM_INVOCATION_SHORT_NAME || true
+runtest readpassphrase READPASSPHRASE || true
+runtest reallocarray REALLOCARRAY || true
+runtest recallocarray RECALLOCARRAY || true
+runtest sandbox_init SANDBOX_INIT "-Wno-deprecated" || true
+runtest seccomp-filter SECCOMP_FILTER || true
+runtest SOCK_NONBLOCK SOCK_NONBLOCK || true
+runtest strlcat STRLCAT || true
+runtest strlcpy STRLCPY || true
+runtest strndup STRNDUP || true
+runtest strnlen STRNLEN || true
+runtest strtonum STRTONUM || true
+runtest sys_queue SYS_QUEUE || true
+runtest sys_tree SYS_TREE || true
+runtest systrace SYSTRACE || true
+runtest unveil UNVEIL || true
+runtest zlib ZLIB "" "-lz" || true
+runtest __progname __PROGNAME || true
+
+#----------------------------------------------------------------------
+# Output writing: generate the config.h file.
+# This file contains all of the HAVE_xxxx variables necessary for
+# compiling your source.
+# You must include "config.h" BEFORE any other variables.
+# You WANT to change this.
+#----------------------------------------------------------------------
+
+exec > config.h
+
+# Start with prologue.
+
+cat << __HEREDOC__
+#ifndef OCONFIGURE_CONFIG_H
+#define OCONFIGURE_CONFIG_H
+#ifdef __cplusplus
+#error "Do not use C++: this is a C application."
+#endif
+#if !defined(__GNUC__) || (__GNUC__ < 4)
+#define __attribute__(x)
+#endif
+#if defined(__linux__) || defined(__MINT__)
+#define _GNU_SOURCE /* See test-*.c what needs this. */
+#endif
+#if !defined(__BEGIN_DECLS)
+# define __BEGIN_DECLS
+#endif
+#if !defined(__END_DECLS)
+# define __END_DECLS
+#endif
+__HEREDOC__
+
+# This is just for size_t.
+# Most of these functions, in the real world, pull in <string.h> or
+# someting that pulls in support for size_t.
+# Our function declarations are standalone, so specify them here.
+
+[ ${HAVE_MD5} -eq 0 -o \
+ ${HAVE_READPASSPHRASE} -eq 0 -o \
+ ${HAVE_REALLOCARRAY} -eq 0 -o \
+ ${HAVE_RECALLOCARRAY} -eq 0 -o \
+ ${HAVE_STRLCAT} -eq 0 -o \
+ ${HAVE_STRLCPY} -eq 0 -o \
+ ${HAVE_STRNDUP} -eq 0 -o \
+ ${HAVE_STRNLEN} -eq 0 ] \
+ && echo "#include <sys/types.h>"
+
+[ ${HAVE_ERR} -eq 0 ] \
+ && echo "#include <stdarg.h>"
+
+# Now we handle our HAVE_xxxx values.
+# Most will just be defined as 0 or 1.
+
+[ ${HAVE_PATH_MAX} -eq 0 ] \
+ && echo "#define PATH_MAX 4096"
+
+[ ${HAVE_INFTIM} -eq 0 ] \
+ && echo "#define INFTIM (-1)"
+
+cat << __HEREDOC__
+#define HAVE_ARC4RANDOM ${HAVE_ARC4RANDOM}
+#define HAVE_B64_NTOP ${HAVE_B64_NTOP}
+#define HAVE_CAPSICUM ${HAVE_CAPSICUM}
+#define HAVE_ENDIAN_H ${HAVE_ENDIAN_H}
+#define HAVE_ERR ${HAVE_ERR}
+#define HAVE_EXPLICIT_BZERO ${HAVE_EXPLICIT_BZERO}
+#define HAVE_GETEXECNAME ${HAVE_GETEXECNAME}
+#define HAVE_GETPROGNAME ${HAVE_GETPROGNAME}
+#define HAVE_INFTIM ${HAVE_INFTIM}
+#define HAVE_MD5 ${HAVE_MD5}
+#define HAVE_MEMMEM ${HAVE_MEMMEM}
+#define HAVE_MEMRCHR ${HAVE_MEMRCHR}
+#define HAVE_MEMSET_S ${HAVE_MEMSET_S}
+#define HAVE_PATH_MAX ${HAVE_PATH_MAX}
+#define HAVE_PLEDGE ${HAVE_PLEDGE}
+#define HAVE_PROGRAM_INVOCATION_SHORT_NAME ${HAVE_PROGRAM_INVOCATION_SHORT_NAME}
+#define HAVE_READPASSPHRASE ${HAVE_READPASSPHRASE}
+#define HAVE_REALLOCARRAY ${HAVE_REALLOCARRAY}
+#define HAVE_RECALLOCARRAY ${HAVE_RECALLOCARRAY}
+#define HAVE_SANDBOX_INIT ${HAVE_SANDBOX_INIT}
+#define HAVE_SECCOMP_FILTER ${HAVE_SECCOMP_FILTER}
+#define HAVE_SOCK_NONBLOCK ${HAVE_SOCK_NONBLOCK}
+#define HAVE_STRLCAT ${HAVE_STRLCAT}
+#define HAVE_STRLCPY ${HAVE_STRLCPY}
+#define HAVE_STRNDUP ${HAVE_STRNDUP}
+#define HAVE_STRNLEN ${HAVE_STRNLEN}
+#define HAVE_STRTONUM ${HAVE_STRTONUM}
+#define HAVE_SYS_QUEUE ${HAVE_SYS_QUEUE}
+#define HAVE_SYS_TREE ${HAVE_SYS_TREE}
+#define HAVE_SYSTRACE ${HAVE_SYSTRACE}
+#define HAVE_UNVEIL ${HAVE_UNVEIL}
+#define HAVE_ZLIB ${HAVE_ZLIB}
+#define HAVE___PROGNAME ${HAVE___PROGNAME}
+__HEREDOC__
+
+# Now we do our function declarations for missing functions.
+
+if [ ${HAVE_ERR} -eq 0 ]; then
+ echo "extern void err(int, const char *, ...);"
+ echo "extern void errx(int, const char *, ...);"
+ echo "extern void warn(const char *, ...);"
+ echo "extern void warnx(const char *, ...);"
+ echo "extern void vwarn(const char *, va_list);"
+ echo "extern void vwarnx(const char *, va_list);"
+fi
+
+if [ ${HAVE_MD5} -eq 0 ]; then
+ echo "#define MD5_BLOCK_LENGTH 64"
+ echo "#define MD5_DIGEST_LENGTH 16"
+ echo "#define MD5_DIGEST_STRING_LENGTH (MD5_DIGEST_LENGTH * 2 + 1)"
+ cat <<!!
+typedef struct MD5Context {
+ u_int32_t state[4];
+ u_int64_t count;
+ u_int8_t buffer[MD5_BLOCK_LENGTH];
+} MD5_CTX;
+!!
+ echo "extern void MD5Init(MD5_CTX *);"
+ echo "extern void MD5Update(MD5_CTX *, const u_int8_t *, size_t);"
+ echo "extern void MD5Pad(MD5_CTX *);"
+ echo "extern void MD5Transform(u_int32_t [4], const u_int8_t [MD5_BLOCK_LENGTH]);"
+ echo "extern char *MD5End(MD5_CTX *, char *);"
+ echo "extern void MD5Final(u_int8_t [MD5_DIGEST_LENGTH], MD5_CTX *);";
+fi
+
+if [ ${HAVE_SECCOMP_FILTER} -eq 1 ]; then
+ arch=`uname -m 2>/dev/null || echo unknown`
+ case "$arch" in
+ x86_64)
+ echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_X86_64"
+ ;;
+ i*86)
+ echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_I386"
+ ;;
+ arm*)
+ echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_ARM"
+ ;;
+ aarch64)
+ echo "#define SECCOMP_AUDIT_ARCH AUDIT_ARCH_AARCH64"
+ ;;
+ esac
+fi
+
+if [ ${HAVE_B64_NTOP} -eq 0 ]; then
+ echo "extern int b64_ntop(unsigned char const *, size_t, char *, size_t);";
+ echo "extern int b64_pton(char const *, unsigned char *, size_t);"
+fi
+
+if [ ${HAVE_EXPLICIT_BZERO} -eq 0 ]; then
+ echo "extern void explicit_bzero(void *, size_t);"
+fi
+
+if [ ${HAVE_MEMMEM} -eq 0 ]; then
+ echo "void *memmem(const void *, size_t, const void *, size_t);"
+fi
+
+if [ ${HAVE_MEMRCHR} -eq 0 ]; then
+ echo "void *memrchr(const void *b, int, size_t);"
+fi
+
+if [ ${HAVE_GETPROGNAME} -eq 0 ]; then
+ echo "extern const char *getprogname(void);"
+fi
+
+if [ ${HAVE_READPASSPHRASE} -eq 0 ]; then
+ echo "#define RPP_ECHO_OFF 0x00"
+ echo "#define RPP_ECHO_ON 0x01"
+ echo "#define RPP_REQUIRE_TTY 0x02"
+ echo "#define RPP_FORCELOWER 0x04"
+ echo "#define RPP_FORCEUPPER 0x08"
+ echo "#define RPP_SEVENBIT 0x10"
+ echo "#define RPP_STDIN 0x20"
+ echo "char *readpassphrase(const char *, char *, size_t, int);"
+fi
+
+if [ ${HAVE_REALLOCARRAY} -eq 0 ]; then
+ echo "extern void *reallocarray(void *, size_t, size_t);"
+fi
+
+if [ ${HAVE_RECALLOCARRAY} -eq 0 ]; then
+ echo "extern void *recallocarray(void *, size_t, size_t, size_t);"
+fi
+
+if [ ${HAVE_STRLCAT} -eq 0 ]; then
+ echo "extern size_t strlcat(char *, const char *, size_t);"
+fi
+
+if [ ${HAVE_STRLCPY} -eq 0 ]; then
+ echo "extern size_t strlcpy(char *, const char *, size_t);"
+fi
+
+if [ ${HAVE_STRNDUP} -eq 0 ]; then
+ echo "extern char *strndup(const char *, size_t);"
+fi
+
+if [ ${HAVE_STRNLEN} -eq 0 ]; then
+ echo "extern size_t strnlen(const char *, size_t);"
+fi
+
+if [ ${HAVE_STRTONUM} -eq 0 ]; then
+ echo "extern long long strtonum(const char *, long long, long long, const char **);"
+fi
+
+if [ ${HAVE_SYS_QUEUE} -eq 0 ]; then
+ cat << __HEREDOC__
+/* \$OpenBSD$ */
+/* \$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp \$ */
+
+/*
+ * Copyright (c) 1991, 1993
+ * The Regents of the University of California. 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.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``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 REGENTS OR CONTRIBUTORS 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.
+ *
+ * @(#)queue.h 8.5 (Berkeley) 8/20/94
+ */
+
+/* OPENBSD ORIGINAL: sys/sys/queue.h */
+
+/*
+ * Require for OS/X and other platforms that have old/broken/incomplete
+ * <sys/queue.h>.
+ */
+#undef SLIST_HEAD
+#undef SLIST_HEAD_INITIALIZER
+#undef SLIST_ENTRY
+#undef SLIST_FOREACH_PREVPTR
+#undef SLIST_FOREACH_SAFE
+#undef SLIST_FIRST
+#undef SLIST_END
+#undef SLIST_EMPTY
+#undef SLIST_NEXT
+#undef SLIST_FOREACH
+#undef SLIST_INIT
+#undef SLIST_INSERT_AFTER
+#undef SLIST_INSERT_HEAD
+#undef SLIST_REMOVE_HEAD
+#undef SLIST_REMOVE_AFTER
+#undef SLIST_REMOVE
+#undef SLIST_REMOVE_NEXT
+#undef LIST_HEAD
+#undef LIST_HEAD_INITIALIZER
+#undef LIST_ENTRY
+#undef LIST_FIRST
+#undef LIST_END
+#undef LIST_EMPTY
+#undef LIST_NEXT
+#undef LIST_FOREACH
+#undef LIST_FOREACH_SAFE
+#undef LIST_INIT
+#undef LIST_INSERT_AFTER
+#undef LIST_INSERT_BEFORE
+#undef LIST_INSERT_HEAD
+#undef LIST_REMOVE
+#undef LIST_REPLACE
+#undef SIMPLEQ_HEAD
+#undef SIMPLEQ_HEAD_INITIALIZER
+#undef SIMPLEQ_ENTRY
+#undef SIMPLEQ_FIRST
+#undef SIMPLEQ_END
+#undef SIMPLEQ_EMPTY
+#undef SIMPLEQ_NEXT
+#undef SIMPLEQ_FOREACH
+#undef SIMPLEQ_FOREACH_SAFE
+#undef SIMPLEQ_INIT
+#undef SIMPLEQ_INSERT_HEAD
+#undef SIMPLEQ_INSERT_TAIL
+#undef SIMPLEQ_INSERT_AFTER
+#undef SIMPLEQ_REMOVE_HEAD
+#undef TAILQ_HEAD
+#undef TAILQ_HEAD_INITIALIZER
+#undef TAILQ_ENTRY
+#undef TAILQ_FIRST
+#undef TAILQ_END
+#undef TAILQ_NEXT
+#undef TAILQ_LAST
+#undef TAILQ_PREV
+#undef TAILQ_EMPTY
+#undef TAILQ_FOREACH
+#undef TAILQ_FOREACH_REVERSE
+#undef TAILQ_FOREACH_SAFE
+#undef TAILQ_FOREACH_REVERSE_SAFE
+#undef TAILQ_INIT
+#undef TAILQ_INSERT_HEAD
+#undef TAILQ_INSERT_TAIL
+#undef TAILQ_INSERT_AFTER
+#undef TAILQ_INSERT_BEFORE
+#undef TAILQ_REMOVE
+#undef TAILQ_REPLACE
+#undef CIRCLEQ_HEAD
+#undef CIRCLEQ_HEAD_INITIALIZER
+#undef CIRCLEQ_ENTRY
+#undef CIRCLEQ_FIRST
+#undef CIRCLEQ_LAST
+#undef CIRCLEQ_END
+#undef CIRCLEQ_NEXT
+#undef CIRCLEQ_PREV
+#undef CIRCLEQ_EMPTY
+#undef CIRCLEQ_FOREACH
+#undef CIRCLEQ_FOREACH_REVERSE
+#undef CIRCLEQ_INIT
+#undef CIRCLEQ_INSERT_AFTER
+#undef CIRCLEQ_INSERT_BEFORE
+#undef CIRCLEQ_INSERT_HEAD
+#undef CIRCLEQ_INSERT_TAIL
+#undef CIRCLEQ_REMOVE
+#undef CIRCLEQ_REPLACE
+
+/*
+ * This file defines five types of data structures: singly-linked lists,
+ * lists, simple queues, tail queues, and circular queues.
+ *
+ *
+ * A singly-linked list is headed by a single forward pointer. The elements
+ * are singly linked for minimum space and pointer manipulation overhead at
+ * the expense of O(n) removal for arbitrary elements. New elements can be
+ * added to the list after an existing element or at the head of the list.
+ * Elements being removed from the head of the list should use the explicit
+ * macro for this purpose for optimum efficiency. A singly-linked list may
+ * only be traversed in the forward direction. Singly-linked lists are ideal
+ * for applications with large datasets and few or no removals or for
+ * implementing a LIFO queue.
+ *
+ * A list is headed by a single forward pointer (or an array of forward
+ * pointers for a hash table header). The elements are doubly linked
+ * so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before
+ * or after an existing element or at the head of the list. A list
+ * may only be traversed in the forward direction.
+ *
+ * A simple queue is headed by a pair of pointers, one the head of the
+ * list and the other to the tail of the list. The elements are singly
+ * linked to save space, so elements can only be removed from the
+ * head of the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the
+ * list. A simple queue may only be traversed in the forward direction.
+ *
+ * A tail queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or
+ * after an existing element, at the head of the list, or at the end of
+ * the list. A tail queue may be traversed in either direction.
+ *
+ * A circle queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the list.
+ * A circle queue may be traversed in either direction, but has a more
+ * complex end of list detection.
+ *
+ * For details on the use of these macros, see the queue(3) manual page.
+ */
+
+#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
+#define _Q_INVALIDATE(a) (a) = ((void *)-1)
+#else
+#define _Q_INVALIDATE(a)
+#endif
+
+/*
+ * Singly-linked List definitions.
+ */
+#define SLIST_HEAD(name, type) \\
+struct name { \\
+ struct type *slh_first; /* first element */ \\
+}
+
+#define SLIST_HEAD_INITIALIZER(head) \\
+ { NULL }
+
+#define SLIST_ENTRY(type) \\
+struct { \\
+ struct type *sle_next; /* next element */ \\
+}
+
+/*
+ * Singly-linked List access methods.
+ */
+#define SLIST_FIRST(head) ((head)->slh_first)
+#define SLIST_END(head) NULL
+#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
+#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
+
+#define SLIST_FOREACH(var, head, field) \\
+ for((var) = SLIST_FIRST(head); \\
+ (var) != SLIST_END(head); \\
+ (var) = SLIST_NEXT(var, field))
+
+#define SLIST_FOREACH_SAFE(var, head, field, tvar) \\
+ for ((var) = SLIST_FIRST(head); \\
+ (var) && ((tvar) = SLIST_NEXT(var, field), 1); \\
+ (var) = (tvar))
+
+/*
+ * Singly-linked List functions.
+ */
+#define SLIST_INIT(head) { \\
+ SLIST_FIRST(head) = SLIST_END(head); \\
+}
+
+#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \\
+ (elm)->field.sle_next = (slistelm)->field.sle_next; \\
+ (slistelm)->field.sle_next = (elm); \\
+} while (0)
+
+#define SLIST_INSERT_HEAD(head, elm, field) do { \\
+ (elm)->field.sle_next = (head)->slh_first; \\
+ (head)->slh_first = (elm); \\
+} while (0)
+
+#define SLIST_REMOVE_AFTER(elm, field) do { \\
+ (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \\
+} while (0)
+
+#define SLIST_REMOVE_HEAD(head, field) do { \\
+ (head)->slh_first = (head)->slh_first->field.sle_next; \\
+} while (0)
+
+#define SLIST_REMOVE(head, elm, type, field) do { \\
+ if ((head)->slh_first == (elm)) { \\
+ SLIST_REMOVE_HEAD((head), field); \\
+ } else { \\
+ struct type *curelm = (head)->slh_first; \\
+ \\
+ while (curelm->field.sle_next != (elm)) \\
+ curelm = curelm->field.sle_next; \\
+ curelm->field.sle_next = \\
+ curelm->field.sle_next->field.sle_next; \\
+ _Q_INVALIDATE((elm)->field.sle_next); \\
+ } \\
+} while (0)
+
+/*
+ * List definitions.
+ */
+#define LIST_HEAD(name, type) \\
+struct name { \\
+ struct type *lh_first; /* first element */ \\
+}
+
+#define LIST_HEAD_INITIALIZER(head) \\
+ { NULL }
+
+#define LIST_ENTRY(type) \\
+struct { \\
+ struct type *le_next; /* next element */ \\
+ struct type **le_prev; /* address of previous next element */ \\
+}
+
+/*
+ * List access methods
+ */
+#define LIST_FIRST(head) ((head)->lh_first)
+#define LIST_END(head) NULL
+#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
+#define LIST_NEXT(elm, field) ((elm)->field.le_next)
+
+#define LIST_FOREACH(var, head, field) \\
+ for((var) = LIST_FIRST(head); \\
+ (var)!= LIST_END(head); \\
+ (var) = LIST_NEXT(var, field))
+
+#define LIST_FOREACH_SAFE(var, head, field, tvar) \\
+ for ((var) = LIST_FIRST(head); \\
+ (var) && ((tvar) = LIST_NEXT(var, field), 1); \\
+ (var) = (tvar))
+
+/*
+ * List functions.
+ */
+#define LIST_INIT(head) do { \\
+ LIST_FIRST(head) = LIST_END(head); \\
+} while (0)
+
+#define LIST_INSERT_AFTER(listelm, elm, field) do { \\
+ if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \\
+ (listelm)->field.le_next->field.le_prev = \\
+ &(elm)->field.le_next; \\
+ (listelm)->field.le_next = (elm); \\
+ (elm)->field.le_prev = &(listelm)->field.le_next; \\
+} while (0)
+
+#define LIST_INSERT_BEFORE(listelm, elm, field) do { \\
+ (elm)->field.le_prev = (listelm)->field.le_prev; \\
+ (elm)->field.le_next = (listelm); \\
+ *(listelm)->field.le_prev = (elm); \\
+ (listelm)->field.le_prev = &(elm)->field.le_next; \\
+} while (0)
+
+#define LIST_INSERT_HEAD(head, elm, field) do { \\
+ if (((elm)->field.le_next = (head)->lh_first) != NULL) \\
+ (head)->lh_first->field.le_prev = &(elm)->field.le_next;\\
+ (head)->lh_first = (elm); \\
+ (elm)->field.le_prev = &(head)->lh_first; \\
+} while (0)
+
+#define LIST_REMOVE(elm, field) do { \\
+ if ((elm)->field.le_next != NULL) \\
+ (elm)->field.le_next->field.le_prev = \\
+ (elm)->field.le_prev; \\
+ *(elm)->field.le_prev = (elm)->field.le_next; \\
+ _Q_INVALIDATE((elm)->field.le_prev); \\
+ _Q_INVALIDATE((elm)->field.le_next); \\
+} while (0)
+
+#define LIST_REPLACE(elm, elm2, field) do { \\
+ if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \\
+ (elm2)->field.le_next->field.le_prev = \\
+ &(elm2)->field.le_next; \\
+ (elm2)->field.le_prev = (elm)->field.le_prev; \\
+ *(elm2)->field.le_prev = (elm2); \\
+ _Q_INVALIDATE((elm)->field.le_prev); \\
+ _Q_INVALIDATE((elm)->field.le_next); \\
+} while (0)
+
+/*
+ * Simple queue definitions.
+ */
+#define SIMPLEQ_HEAD(name, type) \\
+struct name { \\
+ struct type *sqh_first; /* first element */ \\
+ struct type **sqh_last; /* addr of last next element */ \\
+}
+
+#define SIMPLEQ_HEAD_INITIALIZER(head) \\
+ { NULL, &(head).sqh_first }
+
+#define SIMPLEQ_ENTRY(type) \\
+struct { \\
+ struct type *sqe_next; /* next element */ \\
+}
+
+/*
+ * Simple queue access methods.
+ */
+#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
+#define SIMPLEQ_END(head) NULL
+#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
+#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
+
+#define SIMPLEQ_FOREACH(var, head, field) \\
+ for((var) = SIMPLEQ_FIRST(head); \\
+ (var) != SIMPLEQ_END(head); \\
+ (var) = SIMPLEQ_NEXT(var, field))
+
+#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \\
+ for ((var) = SIMPLEQ_FIRST(head); \\
+ (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \\
+ (var) = (tvar))
+
+/*
+ * Simple queue functions.
+ */
+#define SIMPLEQ_INIT(head) do { \\
+ (head)->sqh_first = NULL; \\
+ (head)->sqh_last = &(head)->sqh_first; \\
+} while (0)
+
+#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \\
+ if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \\
+ (head)->sqh_last = &(elm)->field.sqe_next; \\
+ (head)->sqh_first = (elm); \\
+} while (0)
+
+#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \\
+ (elm)->field.sqe_next = NULL; \\
+ *(head)->sqh_last = (elm); \\
+ (head)->sqh_last = &(elm)->field.sqe_next; \\
+} while (0)
+
+#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\
+ if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\\
+ (head)->sqh_last = &(elm)->field.sqe_next; \\
+ (listelm)->field.sqe_next = (elm); \\
+} while (0)
+
+#define SIMPLEQ_REMOVE_HEAD(head, field) do { \\
+ if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \\
+ (head)->sqh_last = &(head)->sqh_first; \\
+} while (0)
+
+#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \\
+ if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \\
+ == NULL) \\
+ (head)->sqh_last = &(elm)->field.sqe_next; \\
+} while (0)
+
+/*
+ * Tail queue definitions.
+ */
+#define TAILQ_HEAD(name, type) \\
+struct name { \\
+ struct type *tqh_first; /* first element */ \\
+ struct type **tqh_last; /* addr of last next element */ \\
+}
+
+#define TAILQ_HEAD_INITIALIZER(head) \\
+ { NULL, &(head).tqh_first }
+
+#define TAILQ_ENTRY(type) \\
+struct { \\
+ struct type *tqe_next; /* next element */ \\
+ struct type **tqe_prev; /* address of previous next element */ \\
+}
+
+/*
+ * tail queue access methods
+ */
+#define TAILQ_FIRST(head) ((head)->tqh_first)
+#define TAILQ_END(head) NULL
+#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
+#define TAILQ_LAST(head, headname) \\
+ (*(((struct headname *)((head)->tqh_last))->tqh_last))
+/* XXX */
+#define TAILQ_PREV(elm, headname, field) \\
+ (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+#define TAILQ_EMPTY(head) \\
+ (TAILQ_FIRST(head) == TAILQ_END(head))
+
+#define TAILQ_FOREACH(var, head, field) \\
+ for((var) = TAILQ_FIRST(head); \\
+ (var) != TAILQ_END(head); \\
+ (var) = TAILQ_NEXT(var, field))
+
+#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \\
+ for ((var) = TAILQ_FIRST(head); \\
+ (var) != TAILQ_END(head) && \\
+ ((tvar) = TAILQ_NEXT(var, field), 1); \\
+ (var) = (tvar))
+
+
+#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \\
+ for((var) = TAILQ_LAST(head, headname); \\
+ (var) != TAILQ_END(head); \\
+ (var) = TAILQ_PREV(var, headname, field))
+
+#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \\
+ for ((var) = TAILQ_LAST(head, headname); \\
+ (var) != TAILQ_END(head) && \\
+ ((tvar) = TAILQ_PREV(var, headname, field), 1); \\
+ (var) = (tvar))
+
+/*
+ * Tail queue functions.
+ */
+#define TAILQ_INIT(head) do { \\
+ (head)->tqh_first = NULL; \\
+ (head)->tqh_last = &(head)->tqh_first; \\
+} while (0)
+
+#define TAILQ_INSERT_HEAD(head, elm, field) do { \\
+ if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \\
+ (head)->tqh_first->field.tqe_prev = \\
+ &(elm)->field.tqe_next; \\
+ else \\
+ (head)->tqh_last = &(elm)->field.tqe_next; \\
+ (head)->tqh_first = (elm); \\
+ (elm)->field.tqe_prev = &(head)->tqh_first; \\
+} while (0)
+
+#define TAILQ_INSERT_TAIL(head, elm, field) do { \\
+ (elm)->field.tqe_next = NULL; \\
+ (elm)->field.tqe_prev = (head)->tqh_last; \\
+ *(head)->tqh_last = (elm); \\
+ (head)->tqh_last = &(elm)->field.tqe_next; \\
+} while (0)
+
+#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \\
+ if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\\
+ (elm)->field.tqe_next->field.tqe_prev = \\
+ &(elm)->field.tqe_next; \\
+ else \\
+ (head)->tqh_last = &(elm)->field.tqe_next; \\
+ (listelm)->field.tqe_next = (elm); \\
+ (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \\
+} while (0)
+
+#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \\
+ (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \\
+ (elm)->field.tqe_next = (listelm); \\
+ *(listelm)->field.tqe_prev = (elm); \\
+ (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \\
+} while (0)
+
+#define TAILQ_REMOVE(head, elm, field) do { \\
+ if (((elm)->field.tqe_next) != NULL) \\
+ (elm)->field.tqe_next->field.tqe_prev = \\
+ (elm)->field.tqe_prev; \\
+ else \\
+ (head)->tqh_last = (elm)->field.tqe_prev; \\
+ *(elm)->field.tqe_prev = (elm)->field.tqe_next; \\
+ _Q_INVALIDATE((elm)->field.tqe_prev); \\
+ _Q_INVALIDATE((elm)->field.tqe_next); \\
+} while (0)
+
+#define TAILQ_REPLACE(head, elm, elm2, field) do { \\
+ if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \\
+ (elm2)->field.tqe_next->field.tqe_prev = \\
+ &(elm2)->field.tqe_next; \\
+ else \\
+ (head)->tqh_last = &(elm2)->field.tqe_next; \\
+ (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \\
+ *(elm2)->field.tqe_prev = (elm2); \\
+ _Q_INVALIDATE((elm)->field.tqe_prev); \\
+ _Q_INVALIDATE((elm)->field.tqe_next); \\
+} while (0)
+
+/*
+ * Circular queue definitions.
+ */
+#define CIRCLEQ_HEAD(name, type) \\
+struct name { \\
+ struct type *cqh_first; /* first element */ \\
+ struct type *cqh_last; /* last element */ \\
+}
+
+#define CIRCLEQ_HEAD_INITIALIZER(head) \\
+ { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
+
+#define CIRCLEQ_ENTRY(type) \\
+struct { \\
+ struct type *cqe_next; /* next element */ \\
+ struct type *cqe_prev; /* previous element */ \\
+}
+
+/*
+ * Circular queue access methods
+ */
+#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
+#define CIRCLEQ_LAST(head) ((head)->cqh_last)
+#define CIRCLEQ_END(head) ((void *)(head))
+#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
+#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
+#define CIRCLEQ_EMPTY(head) \\
+ (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
+
+#define CIRCLEQ_FOREACH(var, head, field) \\
+ for((var) = CIRCLEQ_FIRST(head); \\
+ (var) != CIRCLEQ_END(head); \\
+ (var) = CIRCLEQ_NEXT(var, field))
+
+#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \\
+ for ((var) = CIRCLEQ_FIRST(head); \\
+ (var) != CIRCLEQ_END(head) && \\
+ ((tvar) = CIRCLEQ_NEXT(var, field), 1); \\
+ (var) = (tvar))
+
+#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \\
+ for((var) = CIRCLEQ_LAST(head); \\
+ (var) != CIRCLEQ_END(head); \\
+ (var) = CIRCLEQ_PREV(var, field))
+
+#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \\
+ for ((var) = CIRCLEQ_LAST(head, headname); \\
+ (var) != CIRCLEQ_END(head) && \\
+ ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \\
+ (var) = (tvar))
+
+/*
+ * Circular queue functions.
+ */
+#define CIRCLEQ_INIT(head) do { \\
+ (head)->cqh_first = CIRCLEQ_END(head); \\
+ (head)->cqh_last = CIRCLEQ_END(head); \\
+} while (0)
+
+#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \\
+ (elm)->field.cqe_next = (listelm)->field.cqe_next; \\
+ (elm)->field.cqe_prev = (listelm); \\
+ if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \\
+ (head)->cqh_last = (elm); \\
+ else \\
+ (listelm)->field.cqe_next->field.cqe_prev = (elm); \\
+ (listelm)->field.cqe_next = (elm); \\
+} while (0)
+
+#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \\
+ (elm)->field.cqe_next = (listelm); \\
+ (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \\
+ if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \\
+ (head)->cqh_first = (elm); \\
+ else \\
+ (listelm)->field.cqe_prev->field.cqe_next = (elm); \\
+ (listelm)->field.cqe_prev = (elm); \\
+} while (0)
+
+#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \\
+ (elm)->field.cqe_next = (head)->cqh_first; \\
+ (elm)->field.cqe_prev = CIRCLEQ_END(head); \\
+ if ((head)->cqh_last == CIRCLEQ_END(head)) \\
+ (head)->cqh_last = (elm); \\
+ else \\
+ (head)->cqh_first->field.cqe_prev = (elm); \\
+ (head)->cqh_first = (elm); \\
+} while (0)
+
+#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \\
+ (elm)->field.cqe_next = CIRCLEQ_END(head); \\
+ (elm)->field.cqe_prev = (head)->cqh_last; \\
+ if ((head)->cqh_first == CIRCLEQ_END(head)) \\
+ (head)->cqh_first = (elm); \\
+ else \\
+ (head)->cqh_last->field.cqe_next = (elm); \\
+ (head)->cqh_last = (elm); \\
+} while (0)
+
+#define CIRCLEQ_REMOVE(head, elm, field) do { \\
+ if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \\
+ (head)->cqh_last = (elm)->field.cqe_prev; \\
+ else \\
+ (elm)->field.cqe_next->field.cqe_prev = \\
+ (elm)->field.cqe_prev; \\
+ if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \\
+ (head)->cqh_first = (elm)->field.cqe_next; \\
+ else \\
+ (elm)->field.cqe_prev->field.cqe_next = \\
+ (elm)->field.cqe_next; \\
+ _Q_INVALIDATE((elm)->field.cqe_prev); \\
+ _Q_INVALIDATE((elm)->field.cqe_next); \\
+} while (0)
+
+#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \\
+ if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \\
+ CIRCLEQ_END(head)) \\
+ (head).cqh_last = (elm2); \\
+ else \\
+ (elm2)->field.cqe_next->field.cqe_prev = (elm2); \\
+ if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \\
+ CIRCLEQ_END(head)) \\
+ (head).cqh_first = (elm2); \\
+ else \\
+ (elm2)->field.cqe_prev->field.cqe_next = (elm2); \\
+ _Q_INVALIDATE((elm)->field.cqe_prev); \\
+ _Q_INVALIDATE((elm)->field.cqe_next); \\
+} while (0)
+__HEREDOC__
+fi
+
+if [ ${HAVE_SYS_TREE} -eq 0 ]; then
+ cat << __HEREDOC__
+/* \$OpenBSD$ */
+/*
+ * 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.
+ */
+
+/* OPENBSD ORIGINAL: sys/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))
+__HEREDOC__
+fi
+
+cat << __HEREDOC__
+#endif /*!OCONFIGURE_CONFIG_H*/
+__HEREDOC__
+
+echo "config.h: written" 1>&2
+echo "config.h: written" 1>&3
+
+#----------------------------------------------------------------------
+# Now we go to generate our Makefile.configure.
+# This file is simply a bunch of Makefile variables.
+# They'll work in both GNUmakefile and BSDmakefile.
+# You MIGHT want to change this.
+#----------------------------------------------------------------------
+
+exec > Makefile.configure
+
+[ -z "${BINDIR}" ] && BINDIR="${PREFIX}/bin"
+[ -z "${SBINDIR}" ] && SBINDIR="${PREFIX}/sbin"
+[ -z "${INCLUDEDIR}" ] && INCLUDEDIR="${PREFIX}/include"
+[ -z "${LIBDIR}" ] && LIBDIR="${PREFIX}/lib"
+[ -z "${MANDIR}" ] && MANDIR="${PREFIX}/man"
+[ -z "${SHAREDIR}" ] && SHAREDIR="${PREFIX}/share"
+
+[ -z "${INSTALL_PROGRAM}" ] && INSTALL_PROGRAM="${INSTALL} -m 0555"
+[ -z "${INSTALL_LIB}" ] && INSTALL_LIB="${INSTALL} -m 0444"
+[ -z "${INSTALL_MAN}" ] && INSTALL_MAN="${INSTALL} -m 0444"
+[ -z "${INSTALL_DATA}" ] && INSTALL_DATA="${INSTALL} -m 0444"
+
+cat << __HEREDOC__
+CC = ${CC}
+CFLAGS = ${CFLAGS}
+CPPFLAGS = ${CPPFLAGS}
+LDADD = ${LDADD}
+LDFLAGS = ${LDFLAGS}
+STATIC = ${STATIC}
+PREFIX = ${PREFIX}
+BINDIR = ${BINDIR}
+SHAREDIR = ${SHAREDIR}
+SBINDIR = ${SBINDIR}
+INCLUDEDIR = ${INCLUDEDIR}
+LIBDIR = ${LIBDIR}
+MANDIR = ${MANDIR}
+INSTALL = ${INSTALL}
+INSTALL_PROGRAM = ${INSTALL_PROGRAM}
+INSTALL_LIB = ${INSTALL_LIB}
+INSTALL_MAN = ${INSTALL_MAN}
+INSTALL_DATA = ${INSTALL_DATA}
+__HEREDOC__
+
+echo "Makefile.configure: written" 1>&2
+echo "Makefile.configure: written" 1>&3
+
+exit 0
diff --git a/rng.c b/rng.c
@@ -0,0 +1,90 @@
+/*
+ * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
+ * Copyright (c) 2020, Stephen Gregoratto
+ *
+ * Permission to use, copy, modify, and/or distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+#include "config.h"
+
+#include <stdint.h>
+
+#include "rng.h"
+
+#if HAVE_ARC4RANDOM
+#include <stdlib.h>
+
+uint32_t
+rng(void)
+{
+
+ return arc4random();
+}
+#else
+#include <fcntl.h>
+#include <stdlib.h>
+#include <time.h>
+#include <unistd.h>
+
+uint32_t
+rng(void)
+{
+ uint32_t num = 0;
+ int fd;
+
+ if ((fd = open("/dev/urandom", O_RDONLY)) != -1) {
+ (void)read(fd, &num, 4);
+ close(fd);
+ } else {
+ srandom(time(NULL));
+ num = random();
+ }
+
+ return num;
+}
+#endif
+
+/*
+ * Calculate a uniformly distributed random number less than upper_bound
+ * avoiding "modulo bias".
+ *
+ * Uniformity is achieved by generating new random numbers until the one
+ * returned is outside the range [0, 2**32 % upper_bound). This
+ * guarantees the selected random number will be inside
+ * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
+ * after reduction modulo upper_bound.
+ */
+uint32_t
+rng_uniform(uint32_t upper_bound)
+{
+ uint32_t r, min;
+
+ if (upper_bound < 2)
+ return 0;
+
+ /* 2**32 % x == (2**32 - x) % x */
+ min = -upper_bound % upper_bound;
+
+ /*
+ * This could theoretically loop forever but each retry has
+ * p > 0.5 (worst case, usually far better) of selecting a
+ * number inside the range we need, so it should rarely need
+ * to re-roll.
+ */
+ for (;;) {
+ r = rng();
+ if (r >= min)
+ break;
+ }
+
+ return r % upper_bound;
+}
diff --git a/rng.h b/rng.h
@@ -0,0 +1,5 @@
+#ifndef RNG_H
+#define RNG_H
+uint32_t rng(void);
+uint32_t rng_uniform(uint32_t);
+#endif /* RNG_H */
diff --git a/rpass.1 b/rpass.1
@@ -1,4 +1,5 @@
.\" Copyright (c) 2017, 2019 Tim Kuijsten
+.\" Copyright (c) 2020 Stephen Gregoratto
.\"
.\" Permission to use, copy, modify, and/or distribute this software for any
.\" purpose with or without fee is hereby granted, provided that the above
@@ -12,7 +13,7 @@
.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
.\"
-.Dd $Mdocdate: December 13 2019 $
+.Dd February 11, 2020
.Dt RPASS 1
.Os
.Sh NAME
@@ -20,43 +21,43 @@
.Nd strong password generator for humans
.Sh SYNOPSIS
.Nm
-.Op Fl V
.Op Ar bitlen
.Sh DESCRIPTION
+The
.Nm
-is a strong password generator for human beings.
-The generated passwords are shorter than Diceware which suits them better for
-use on mobile devices, the command line or other environments where one has to
-frequently type the password.
+utility generates strong passwords for human beings.
+The generated passwords are shorter than Diceware, making them suitable for
+environments where one has to frequently input them.
The passwords are case-insensitive so that there is no alternation between
keyboards on insert.
-Blanks can be inserted at arbitrary places to enhance visual representation.
+Blanks are inserted at arbitrary places to enhance visual representation.
Furthermore, the passwords are both visually and phonetically unambiguous.
-.Bl -tag -width Ds
-.It Fl V
-Print the version of rpass.
-.It Ar bitlen
-Use a key space of the specified bit length, defaults to 40.
-.El
.Pp
-In order to determine the right
+The
.Ar bitlen
+argument determines the password's keyspace,
+defaulting to 40 if unspecified.
+In order to determine the right
+.Ar bitlen ,
three factors should be considered:
.Bl -enum -offset Ds
.It
-the hashing mechanism used to store the password
+The hashing mechanism used to store the password.
.It
-the time for which this password has to be secure
+The time for which this password has to be secure.
.It
-the processing power of the adversary
+The processing power of the adversary.
.El
.Pp
-The default
-.Ar bitlen
-of 40 bits relies on the following requirements: the password is stored using
+The 40 bit default relies on the following requirements:
+the password is stored using
.Xr bcrypt 3
-with 2^10 rounds, it should only be secure for one year and the adversary
-has no more than $25,000.00 to spend on brute forcing the password (as of 2019).
+with
+.EQ
+2 sup 10
+.EN
+rounds, it should only be secure for one year and the adversary has no more than
+$25,000.00 to spend on brute forcing the password (as of 2019).
.Sh EXIT STATUS
.Ex -std
.Sh EXAMPLES
@@ -73,26 +74,32 @@ jultar ramlap rinwun bemvuh
.Ed
.Pp
In order to calculate the required
-.Ar bitlen
-let's consider a scenario with the following requirements: the generated
+.Ar bitlen ,
+consider a scenario with the following requirements: the generated
password will be used for at most half a year and is stored using
PBKDF2-HMAC-SHA256 with a million iterations.
-Furthermore the adversary has $25,000.00 to spend.
-According to
-.Dq 8x Nvidia GTX 1080 Ti Hashcat Benchmarks
-as of 2019 the adversary can try 15 million hashes per second on
-PBKDF2-HMAC-SHA256 with a thousand iterations.
-This would be 15 thousand hashes per second on PBKDF2-HMAC-SHA256 with a million
+The adversary can compute 15 thousand hashes per second with a million
iterations.
-Hence the required key space is 15,000 * 3,600 * 24 * 183 * 2 = 38.8 bits.
+Thus the required key space is
+.EQ
+log sub 2 (15000 times 3600 times 24 times 183 times 2) approx 38.8
+.EN
.Sh SEE ALSO
-.Xr bcrypt 3 ,
-.Lk https://gist.github.com/epixoip/ace60d09981be09544fdd35005051505 8x Nvidia GTX 1080 Ti Hashcat Benchmarks
-.Lk http://world.std.com/~reinhold/diceware.html The Diceware Passphrase Home Page
-.Lk https://tools.ietf.org/html/rfc8018 PKCS #5: Password-Based Cryptography Specification
+.Xr bcrypt 3
+.Rs
+.%B PKCS #5: Password-Based Cryptography Specification
+.%I Internet Engineering Task Force
+.%D January 2017
+.%R RFC 8018
+.Re
.Sh AUTHORS
.An -nosplit
-.An Tim Kuijsten
-.Sh BUGS
+The
+.Nm
+utility was written by
+.An Tim Kuijsten Aq Mt info@netsend.nl
+and is maintained by
+.An Stephen Gregoratto Aq Mt dev@sgregoratto.me .
+.Sh CAVEATS
The phonetic ambiguity of the current set of mnemonics depends on the spoken
language and is currently optimized for the Dutch language.
diff --git a/rpass.c b/rpass.c
@@ -1,5 +1,6 @@
-/**
- * Copyright (c) 2017 Tim Kuijsten
+/*
+ * Copyright (c) 2017, Tim Kuijsten
+ * Copyright (c) 2020, Stephen Gregoratto
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
@@ -14,106 +15,71 @@
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
-#include <libgen.h>
+#include "config.h"
+#if HAVE_ERR
+#include <err.h>
+#endif
#include <math.h>
+#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
-#ifndef VERSION_MAJOR
-#define VERSION_MAJOR 0
-#define VERSION_MINOR 0
-#define VERSION_PATCH 0
-#endif
+#include "rng.h"
/*
* Dutch three letter "words" that are both visually and phonetically
* unambiguous.
*/
-static const char first[] = "bdfhjklmnprstvwxz"; /* drop c, g, q, y = 4 bpc */
-static const char secon[] = "aeiou"; /* vowels, 2.3 bpc */
-static const char third[] = "fhjklmnprstxz"; /* drop b, c, d, g, q, v, w,
- * y = 3.7 bpc */
-
-static const char *progname;
-
-void
-printversion(int d)
-{
- dprintf(d, "%s v%d.%d.%d\n", progname, VERSION_MAJOR, VERSION_MINOR,
- VERSION_PATCH);
-}
-
-static void
-printusage(int d)
-{
- dprintf(d, "usage: %s [-V] [bitlen]\n", progname);
-}
+/* drop c, g, q, y = 4 bpc */
+static const char first[] = "bdfhjklmnprstvwxz";
+/* vowels, 2.3 bpc */
+static const char secon[] = "aeiou";
+/* drop b, c, d, g, q, v, w, y = 3.7 bpc */
+static const char third[] = "fhjklmnprstxz";
int
main(int argc, char **argv)
{
- double bits, fbpc, sbpc, tbpc;
- int c;
-
- if ((progname = basename(argv[0])) == NULL) {
- perror("basename");
- exit(1);
- }
-
- while ((c = getopt(argc, argv, "Vh")) != -1)
- switch (c) {
- case 'V':
- printversion(STDOUT_FILENO);
- exit(0);
- case 'h':
- printusage(STDOUT_FILENO);
- exit(0);
- default:
- printusage(STDERR_FILENO);
- exit(1);
- }
-
- argc -= optind;
- argv += optind;
-
- if (argc > 1) {
- printusage(STDERR_FILENO);
- exit(1);
- }
-
- fbpc = log2(sizeof first - 1);
- sbpc = log2(sizeof secon - 1);
- tbpc = log2(sizeof third - 1);
-
- if (argc) {
- bits = strtol(argv[0], NULL, 10);
- } else {
- bits = 40.0;
- }
+ const double fbpc = log2(sizeof(first) - 1);
+ const double sbpc = log2(sizeof(secon) - 1);
+ const double tbpc = log2(sizeof(third) - 1);
+ double bits = 40.0;
+ const char *errstr;
+ uint32_t c = 0;
+
+#if HAVE_PLEDGE
+ if (pledge("stdio", NULL) == -1)
+ err(1, "pledge");
+#endif
- if (bits <= 0) {
- printusage(STDERR_FILENO);
- exit(1);
+ if (argc > 2) {
+ warnx("too many arguments: %s", argv[2]);
+ goto usage;
+ } else if (argc == 2) {
+ if (argv[1][0] == '-' && argv[1][1] == 'h')
+ goto usage;
+ bits = strtonum(argv[1], 1, 1000, &errstr);
+ if (errstr != NULL)
+ errx(1, "number of bits is %s: %s", errstr, argv[1]);
}
/* make three letter words */
- c = 0;
- while (bits > 0) {
- putchar(first[arc4random_uniform(sizeof first - 1)]);
- bits -= fbpc;
-
- putchar(secon[arc4random_uniform(sizeof secon - 1)]);
- bits -= sbpc;
+ do {
+ putchar(first[rng_uniform(sizeof(first) - 1)]);
+ putchar(secon[rng_uniform(sizeof(secon) - 1)]);
+ putchar(third[rng_uniform(sizeof(third) - 1)]);
+ bits -= (fbpc + sbpc + tbpc);
- putchar(third[arc4random_uniform(sizeof third - 1)]);
- bits -= tbpc;
-
- if (bits > 0 && c++ % 2)
+ if (c++ % 2)
putchar(' ');
- }
+ } while (bits > 0);
putchar('\n');
return 0;
+usage:
+ fprintf(stderr, "usage: %s [bitlen]\n", getprogname());
+
+ return 1;
}
diff --git a/tests.c b/tests.c
@@ -0,0 +1,503 @@
+#if TEST___PROGNAME
+int
+main(void)
+{
+ extern char *__progname;
+
+ return !__progname;
+}
+#endif /* TEST___PROGNAME */
+#if TEST_ARC4RANDOM
+#include <stdlib.h>
+
+int
+main(void)
+{
+ return (arc4random() + 1) ? 0 : 1;
+}
+#endif /* TEST_ARC4RANDOM */
+#if TEST_B64_NTOP
+#include <netinet/in.h>
+#include <resolv.h>
+
+int
+main(void)
+{
+ const char *src = "hello world";
+ char output[1024];
+
+ return b64_ntop((const unsigned char *)src, 11, output, sizeof(output)) > 0 ? 0 : 1;
+}
+#endif /* TEST_B64_NTOP */
+#if TEST_CAPSICUM
+#include <sys/capsicum.h>
+
+int
+main(void)
+{
+ cap_enter();
+ return(0);
+}
+#endif /* TEST_CAPSICUM */
+#if TEST_ENDIAN_H
+#include <endian.h>
+
+int
+main(void)
+{
+ return !htole32(23);
+}
+#endif /* TEST_ENDIAN_H */
+#if TEST_ERR
+/*
+ * Copyright (c) 2015 Ingo Schwarze <schwarze@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <err.h>
+
+int
+main(void)
+{
+ warnx("%d. warnx", 1);
+ warn("%d. warn", 2);
+ err(0, "%d. err", 3);
+ /* NOTREACHED */
+ return 1;
+}
+#endif /* TEST_ERR */
+#if TEST_EXPLICIT_BZERO
+#include <string.h>
+
+int
+main(void)
+{
+ char foo[10];
+
+ explicit_bzero(foo, sizeof(foo));
+ return(0);
+}
+#endif /* TEST_EXPLICIT_BZERO */
+#if TEST_GETEXECNAME
+#include <stdlib.h>
+
+int
+main(void)
+{
+ const char * progname;
+
+ progname = getexecname();
+ return progname == NULL;
+}
+#endif /* TEST_GETEXECNAME */
+#if TEST_GETPROGNAME
+#include <stdlib.h>
+
+int
+main(void)
+{
+ const char * progname;
+
+ progname = getprogname();
+ return progname == NULL;
+}
+#endif /* TEST_GETPROGNAME */
+#if TEST_INFTIM
+/*
+ * Linux doesn't (always?) have this.
+ */
+
+#include <poll.h>
+#include <stdio.h>
+
+int
+main(void)
+{
+ printf("INFTIM is defined to be %ld\n", (long)INFTIM);
+ return 0;
+}
+#endif /* TEST_INFTIM */
+#if TEST_MD5
+#include <sys/types.h>
+#include <md5.h>
+
+int main(void)
+{
+ MD5_CTX ctx;
+
+ MD5Init(&ctx);
+ MD5Update(&ctx, "abcd", 4);
+
+ return 0;
+}
+#endif /* TEST_MD5 */
+#if TEST_MEMMEM
+#define _GNU_SOURCE
+#include <string.h>
+
+int
+main(void)
+{
+ char *a = memmem("hello, world", strlen("hello, world"), "world", strlen("world"));
+ return(NULL == a);
+}
+#endif /* TEST_MEMMEM */
+#if TEST_MEMRCHR
+#if defined(__linux__) || defined(__MINT__)
+#define _GNU_SOURCE /* See test-*.c what needs this. */
+#endif
+#include <string.h>
+
+int
+main(void)
+{
+ const char *buf = "abcdef";
+ void *res;
+
+ res = memrchr(buf, 'a', strlen(buf));
+ return(NULL == res ? 1 : 0);
+}
+#endif /* TEST_MEMRCHR */
+#if TEST_MEMSET_S
+#include <string.h>
+
+int main(void)
+{
+ char buf[10];
+ memset_s(buf, 0, 'c', sizeof(buf));
+ return 0;
+}
+#endif /* TEST_MEMSET_S */
+#if TEST_PATH_MAX
+/*
+ * POSIX allows PATH_MAX to not be defined, see
+ * http://pubs.opengroup.org/onlinepubs/9699919799/functions/sysconf.html;
+ * the GNU Hurd is an example of a system not having it.
+ *
+ * Arguably, it would be better to test sysconf(_SC_PATH_MAX),
+ * but since the individual *.c files include "config.h" before
+ * <limits.h>, overriding an excessive value of PATH_MAX from
+ * "config.h" is impossible anyway, so for now, the simplest
+ * fix is to provide a value only on systems not having any.
+ * So far, we encountered no system defining PATH_MAX to an
+ * impractically large value, even though POSIX explicitly
+ * allows that.
+ *
+ * The real fix would be to replace all static buffers of size
+ * PATH_MAX by dynamically allocated buffers. But that is
+ * somewhat intrusive because it touches several files and
+ * because it requires changing struct mlink in mandocdb.c.
+ * So i'm postponing that for now.
+ */
+
+#include <limits.h>
+#include <stdio.h>
+
+int
+main(void)
+{
+ printf("PATH_MAX is defined to be %ld\n", (long)PATH_MAX);
+ return 0;
+}
+#endif /* TEST_PATH_MAX */
+#if TEST_PLEDGE
+#include <unistd.h>
+
+int
+main(void)
+{
+ return !!pledge("stdio", NULL);
+}
+#endif /* TEST_PLEDGE */
+#if TEST_PROGRAM_INVOCATION_SHORT_NAME
+#define _GNU_SOURCE /* See feature_test_macros(7) */
+#include <errno.h>
+
+int
+main(void)
+{
+
+ return !program_invocation_short_name;
+}
+#endif /* TEST_PROGRAM_INVOCATION_SHORT_NAME */
+#if TEST_READPASSPHRASE
+#include <stddef.h>
+#include <readpassphrase.h>
+
+int
+main(void)
+{
+ return !!readpassphrase("prompt: ", NULL, 0, 0);
+}
+#endif /* TEST_READPASSPHRASE */
+#if TEST_REALLOCARRAY
+#include <stdlib.h>
+
+int
+main(void)
+{
+ return !reallocarray(NULL, 2, 2);
+}
+#endif /* TEST_REALLOCARRAY */
+#if TEST_RECALLOCARRAY
+#include <stdlib.h>
+
+int
+main(void)
+{
+ return !recallocarray(NULL, 0, 2, 2);
+}
+#endif /* TEST_RECALLOCARRAY */
+#if TEST_SANDBOX_INIT
+#include <sandbox.h>
+
+int
+main(void)
+{
+ char *ep;
+ int rc;
+
+ rc = sandbox_init(kSBXProfileNoInternet, SANDBOX_NAMED, &ep);
+ if (-1 == rc)
+ sandbox_free_error(ep);
+ return(-1 == rc);
+}
+#endif /* TEST_SANDBOX_INIT */
+#if TEST_SECCOMP_FILTER
+#include <sys/prctl.h>
+#include <linux/seccomp.h>
+#include <errno.h>
+
+int
+main(void)
+{
+
+ prctl(PR_SET_SECCOMP, SECCOMP_MODE_FILTER, 0);
+ return(EFAULT == errno ? 0 : 1);
+}
+#endif /* TEST_SECCOMP_FILTER */
+#if TEST_SOCK_NONBLOCK
+/*
+ * Linux doesn't (always?) have this.
+ */
+
+#include <sys/socket.h>
+
+int
+main(void)
+{
+ int fd[2];
+ socketpair(AF_UNIX, SOCK_STREAM|SOCK_NONBLOCK, 0, fd);
+ return 0;
+}
+#endif /* TEST_SOCK_NONBLOCK */
+#if TEST_STRLCAT
+#include <string.h>
+
+int
+main(void)
+{
+ char buf[3] = "a";
+ return ! (strlcat(buf, "b", sizeof(buf)) == 2 &&
+ buf[0] == 'a' && buf[1] == 'b' && buf[2] == '\0');
+}
+#endif /* TEST_STRLCAT */
+#if TEST_STRLCPY
+#include <string.h>
+
+int
+main(void)
+{
+ char buf[2] = "";
+ return ! (strlcpy(buf, "a", sizeof(buf)) == 1 &&
+ buf[0] == 'a' && buf[1] == '\0');
+}
+#endif /* TEST_STRLCPY */
+#if TEST_STRNDUP
+#include <string.h>
+
+int
+main(void)
+{
+ const char *foo = "bar";
+ char *baz;
+
+ baz = strndup(foo, 1);
+ return(0 != strcmp(baz, "b"));
+}
+#endif /* TEST_STRNDUP */
+#if TEST_STRNLEN
+#include <string.h>
+
+int
+main(void)
+{
+ const char *foo = "bar";
+ size_t sz;
+
+ sz = strnlen(foo, 1);
+ return(1 != sz);
+}
+#endif /* TEST_STRNLEN */
+#if TEST_STRTONUM
+/*
+ * Copyright (c) 2015 Ingo Schwarze <schwarze@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdlib.h>
+
+int
+main(void)
+{
+ const char *errstr;
+
+ if (strtonum("1", 0, 2, &errstr) != 1)
+ return 1;
+ if (errstr != NULL)
+ return 2;
+ if (strtonum("1x", 0, 2, &errstr) != 0)
+ return 3;
+ if (errstr == NULL)
+ return 4;
+ if (strtonum("2", 0, 1, &errstr) != 0)
+ return 5;
+ if (errstr == NULL)
+ return 6;
+ if (strtonum("0", 1, 2, &errstr) != 0)
+ return 7;
+ if (errstr == NULL)
+ return 8;
+ return 0;
+}
+#endif /* TEST_STRTONUM */
+#if TEST_SYS_QUEUE
+#include <sys/queue.h>
+#include <stddef.h>
+
+struct foo {
+ int bar;
+ TAILQ_ENTRY(foo) entries;
+};
+
+TAILQ_HEAD(fooq, foo);
+
+int
+main(void)
+{
+ struct fooq foo_q;
+ struct foo *p, *tmp;
+ int i = 0;
+
+ TAILQ_INIT(&foo_q);
+
+ /*
+ * Use TAILQ_FOREACH_SAFE because some systems (e.g., Linux)
+ * have TAILQ_FOREACH but not the safe variant.
+ */
+
+ TAILQ_FOREACH_SAFE(p, &foo_q, entries, tmp)
+ p->bar = i++;
+ return 0;
+}
+#endif /* TEST_SYS_QUEUE */
+#if TEST_SYS_TREE
+#include <sys/tree.h>
+#include <stdlib.h>
+
+struct node {
+ RB_ENTRY(node) entry;
+ int i;
+};
+
+static int
+intcmp(struct node *e1, struct node *e2)
+{
+ return (e1->i < e2->i ? -1 : e1->i > e2->i);
+}
+
+RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
+RB_PROTOTYPE(inttree, node, entry, intcmp)
+RB_GENERATE(inttree, node, entry, intcmp)
+
+int testdata[] = {
+ 20, 16, 17, 13, 3, 6, 1, 8, 2, 4
+};
+
+int
+main(void)
+{
+ size_t i;
+ struct node *n;
+
+ for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
+ if ((n = malloc(sizeof(struct node))) == NULL)
+ return 1;
+ n->i = testdata[i];
+ RB_INSERT(inttree, &head, n);
+ }
+
+ return 0;
+}
+
+#endif /* TEST_SYS_TREE */
+#if TEST_SYSTRACE
+#include <sys/param.h>
+#include <dev/systrace.h>
+
+#include <stdlib.h>
+
+int
+main(void)
+{
+
+ return(0);
+}
+#endif /* TEST_SYSTRACE */
+#if TEST_UNVEIL
+#include <unistd.h>
+
+int
+main(void)
+{
+ return -1 != unveil(NULL, NULL);
+}
+#endif /* TEST_UNVEIL */
+#if TEST_ZLIB
+#include <stddef.h>
+#include <zlib.h>
+
+int
+main(void)
+{
+ gzFile gz;
+
+ if (NULL == (gz = gzopen("/dev/null", "w")))
+ return(1);
+ gzputs(gz, "foo");
+ gzclose(gz);
+ return(0);
+}
+#endif /* TEST_ZLIB */