diceware-c

Interactive Diceware Generator
git clone git://git.sgregoratto.me/diceware-c
Log | Files | Refs

commit 9d6c0d30f36b0e666ce055d3d0169cc51aa4f1f1
Author: Stephen Gregoratto <dev@sgregoratto.me>
Date:   Fri, 24 Jan 2020 10:02:16 +1100

initial commit

Diffstat:
A.gitignore | 7+++++++
AMakefile | 9+++++++++
Acompats.c | 1440+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aconfigure | 1997+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adiceware.c | 112+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adiceware.h | 8++++++++
Arng.c | 100+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Arng.h | 5+++++
Atests.c | 517+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Awords.c | 1115+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
10 files changed, 5310 insertions(+), 0 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -0,0 +1,7 @@ +*.log +*.o +*.old +Makefile.configure +config.h +diceware +tags diff --git a/Makefile b/Makefile @@ -0,0 +1,9 @@ +include Makefile.configure + +OBJS = diceware.o words.o rng.o compats.o + +diceware: $(OBJS) + $(CC) $(LDFLAGS) -o $@ $(OBJS) + +clean: + rm -f diceware $(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 = TCASOFT; +#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,1997 @@ +#! /bin/sh +# +# Copyright (c) 2014, 2015, 2016 Ingo Schwarze <schwarze@openbsd.org> +# Copyright (c) 2017, 2018 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 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.16" + +# +# 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_GETRANDOM= +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 getrandom GETRANDOM || 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_GETRANDOM ${HAVE_GETRANDOM} +#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/diceware.c b/diceware.c @@ -0,0 +1,112 @@ +#include "config.h" +#if HAVE_ERR +#include <err.h> +#endif +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +#include "rng.h" +#include "diceware.h" + +/* Enough for ten six-character words and their seperators */ +static char buf[70] = {0}; +static size_t buflen = 0; + +int +main(int argc, char **argv) +{ + int num; + const char *errstr; + + if (argc > 2) { + warnx("too many arguments: %s", argv[2]); + } else if (argc == 2) { + if (argv[1][0] == '-' && argv[1][1] == 'h') + goto usage; + num = strtonum(argv[1], 1, 10, &errstr); + if (errstr != NULL) + errx(1, "number of words is %s: %s", errstr, argv[1]); + + generate(num); + } else { + interactive(); + } + + return 0; +usage: + fprintf(stderr, "usage: %s [num-words]\n", getprogname()); + + return 1; +} + +void +generate(int num_words) +{ + static char roll[6] = {0}; + const char *word; + uint32_t num, rem; + + for (int i = 0; i < num_words; i++) { + num = rng_uniform(NUM_WORDS); + word = words[num]; + + for (size_t i = 0; i < 5; i++) { + rem = num % 6; + roll[4 - i] = rem + '1'; + num /= 6; + } + + fprintf(stderr, "%s %s\n", roll, word); + buflen = strlcat(buf, word, sizeof(buf)); + buf[buflen] = ' '; + } + buf[buflen] = '\n'; + + (void)fwrite(buf, 1, buflen + 1, stdout); +} + +void +interactive(void) +{ + static const uint32_t exps[5] = {1296, 216, 36, 6, 1}; + uint32_t num; + char *line = NULL; + size_t size = 0; + ssize_t len; + size_t i = 0; + + do { + fprintf(stderr, "Roll %2zu: ", i + 1); + len = getline(&line, &size, stdin); + if (len == -1) { + if (feof(stdin)) + break; + else if (ferror(stdin)) + err(1, "getline"); + } else if (len != 6) { + warnx("roll is not 5 numbers long, skipping"); + continue; + } + line[len] = '\0'; + + num = 0; + for (size_t j = 0; j < 5; j++) { + if (line[j] < '1' || line[j] > '6') { + warnx("invalid roll, skipping: %s", line); + continue; + } + num += (line[j] - '1') * exps[j]; + } + + buflen = strlcat(buf, words[num], sizeof(buf)); + buf[buflen] = ' '; + i++; + } while (i < 10); + fputc('\n', stderr); + free(line); + + buf[buflen] = '\n'; + fputs("Your password is: ", stderr); + (void)fwrite(buf, 1, buflen + 1, stdout); +} diff --git a/diceware.h b/diceware.h @@ -0,0 +1,8 @@ +#ifndef DICEWARE_H +#define DICEWARE_H +#define NUM_WORDS 7776 +extern const char *words[]; + +void generate(int); +void interactive(void); +#endif /* DICEWARE_H */ diff --git a/rng.c b/rng.c @@ -0,0 +1,100 @@ +/* + * Copyright (c) 2008, Damien Miller <djm@openbsd.org> + * Copyright (c) 2020, Stephen Gregoratto <dev@sgregoratto.me> + * + * 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_GETRANDOM +#include <sys/random.h> +uint32_t +rng(void) +{ + uint32_t num = 0; + + (void)getrandom(&num, 4, 0); + + return num; +} +#elif 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/tests.c b/tests.c @@ -0,0 +1,517 @@ +#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_GETRANDOM +#include <sys/random.h> +#include <stdlib.h> + +int +main(void) +{ + ssize_t len; + int num; + + len = getrandom(&num, sizeof(len), 0); + return (len != -1) ? 0 : 1; +} +#endif /* TEST_GETRANDOM */ +#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 */ diff --git a/words.c b/words.c @@ -0,0 +1,1115 @@ +#include "diceware.h" + +const char *words[] = { + "a", "a&p", "a's", "aa", "aaa", "aaaa", "aaron", + "ab", "aba", "ababa", "aback", "abase", "abash", "abate", + "abbas", "abbe", "abbey", "abbot", "abbott", "abc", "abe", + "abed", "abel", "abet", "abide", "abject", "ablaze", "able", + "abner", "abo", "abode", "abort", "about", "above", "abrade", + "abram", "absorb", "abuse", "abut", "abyss", "ac", "acadia", + "accra", "accrue", "ace", "acetic", "ache", "acid", "acidic", + "acm", "acme", "acorn", "acre", "acrid", "act", "acton", + "actor", "acts", "acuity", "acute", "ad", "ada", "adage", + "adagio", "adair", "adam", "adams", "adapt", "add", "added", + "addict", "addis", "addle", "adele", "aden", "adept", "adieu", + "adjust", "adler", "admit", "admix", "ado", "adobe", "adonis", + "adopt", "adore", "adorn", "adult", "advent", "advert", "advise", + "ae", "aegis", "aeneid", "af", "afar", "affair", "affine", + "affix", "afire", "afoot", "afraid", "africa", "afro", "aft", + "ag", "again", "agate", "agave", "age", "agee", "agenda", + "agent", "agile", "aging", "agnes", "agnew", "ago", "agone", + "agony", "agree", "ague", "agway", "ah", "ahead", "ahem", + "ahoy", "ai", "aid", "aida", "aide", "aides", "aiken", + "ail", "aile", "aim", "ain't", "ainu", "air", "aires", + "airman", "airway", "airy", "aisle", "aj", "ajar", "ajax", + "ak", "akers", "akin", "akron", "al", "ala", "alai", + "alamo", "alan", "alarm", "alaska", "alb", "alba", "album", + "alcoa", "alden", "alder", "ale", "alec", "aleck", "aleph", + "alert", "alex", "alexei", "alga", "algae", "algal", "alger", + "algol", "ali", "alia", "alias", "alibi", "alice", "alien", + "alight", "align", "alike", "alive", "all", "allah", "allan", + "allay", "allen", "alley", "allied", "allis", "allot", "allow", + "alloy", "allure", "ally", "allyl", "allyn", "alma", "almost", + "aloe", "aloft", "aloha", "alone", "along", "aloof", "aloud", + "alp", "alpha", "alps", "also", "alsop", "altair", "altar", + "alter", "alto", "alton", "alum", "alumni", "alva", "alvin", + "alway", "am", "ama", "amass", "amaze", "amber", "amble", + "ambush", "amen", "amend", "ames", "ami", "amid", "amide", + "amigo", "amino", "amiss", "amity", "amman", "ammo", "amoco", + "amok", "among", "amort", "amos", "amp", "ampere", "ampex", + "ample", "amply", "amra", "amulet", "amuse", "amy", "an", + "ana", "and", "andes", "andre", "andrew", "andy", "anent", + "anew", "angel", "angelo", "anger", "angie", "angle", "anglo", + "angola", "angry", "angst", "angus", "ani", "anion", "anise", + "anita", "ankle", "ann", "anna", "annal", "anne", "annex", + "annie", "annoy", "annul", "annuli", "annum", "anode", "ansi", + "answer", "ant", "ante", "anti", "antic", "anton", "anus", + "anvil", "any", "anyhow", "anyway", "ao", "aok", "aorta", + "ap", "apart", "apathy", "ape", "apex", "aphid", "aplomb", + "appeal", "append", "apple", "apply", "april", "apron", "apse", + "apt", "aq", "aqua", "ar", "arab", "araby", "arc", + "arcana", "arch", "archer", "arden", "ardent", "are", "area", + "arena", "ares", "argive", "argo", "argon", "argot", "argue", + "argus", "arhat", "arid", "aries", "arise", "ark", "arlen", + "arlene", "arm", "armco", "army", "arnold", "aroma", "arose", + "arpa", "array", "arrear", "arrow", "arson", "art", "artery", + "arthur", "artie", "arty", "aruba", "arum", "aryl", "as", + "ascend", "ash", "ashen", "asher", "ashley", "ashy", "asia", + "aside", "ask", "askew", "asleep", "aspen", "aspire", "ass", + "assai", "assam", "assay", "asset", "assort", "assure", "aster", + "astm", "astor", "astral", "at", "at&t", "ate", "athens", + "atlas", "atom", "atomic", "atone", "atop", "attic", "attire", + "au", "aubrey", "audio", "audit", "aug", "auger", "augur", + "august", "auk", "aunt", "aura", "aural", "auric", "austin", + "auto", "autumn", "av", "avail", "ave", "aver", "avert", + "avery", "aviate", "avid", "avis", "aviv", "avoid", "avon", + "avow", "aw", "await", "awake", "award", "aware", "awash", + "away", "awe", "awful", "awl", "awn", "awoke", "awry", + "ax", "axe", "axes", "axial", "axiom", "axis", "axle", + "axon", "ay", "aye", "ayers", "az", "aztec", "azure", + "b", "b's", "ba", "babe", "babel", "baby", "bach", + "back", "backup", "bacon", "bad", "bade", "baden", "badge", + "baffle", "bag", "baggy", "bah", "bahama", "bail", "baird", + "bait", "bake", "baku", "bald", "baldy", "bale", "bali", + "balk", "balkan", "balky", "ball", "balled", "ballot", "balm", + "balmy", "balsa", "bam", "bambi", "ban", "banal", "band", + "bandit", "bandy", "bane", "bang", "banish", "banjo", "bank", + "banks", "bantu", "bar", "barb", "bard", "bare", "barfly", + "barge", "bark", "barley", "barn", "barnes", "baron", "barony", + "barr", "barre", "barry", "barter", "barth", "barton", "basal", + "base", "basel", "bash", "basic", "basil", "basin", "basis", + "bask", "bass", "bassi", "basso", "baste", "bat", "batch", + "bate", "bater", "bates", "bath", "bathe", "batik", "baton", + "bator", "batt", "bauble", "baud", "bauer", "bawd", "bawdy", + "bawl", "baxter", "bay", "bayda", "bayed", "bayou", "bazaar", + "bb", "bbb", "bbbb", "bc", "bcd", "bd", "be", + "beach", "bead", "beady", "beak", "beam", "bean", "bear", + "beard", "beast", "beat", "beau", "beauty", "beaux", "bebop", + "becalm", "beck", "becker", "becky", "bed", "bedim", "bee", + "beebe", "beech", "beef", "beefy", "been", "beep", "beer", + "beet", "befall", "befit", "befog", "beg", "began", "beget", + "beggar", "begin", "begun", "behind", "beige", "being", "beirut", + "bel", "bela", "belch", "belfry", "belie", "bell", "bella", + "belle", "belly", "below", "belt", "bema", "beman", "bemoan", + "ben", "bench", "bend", "bender", "benny", "bent", "benz", + "berea", "bereft", "beret", "berg", "berlin", "bern", "berne", + "bernet", "berra", "berry", "bert", "berth", "beryl", "beset", + "bess", "bessel", "best", "bestir", "bet", "beta", "betel", + "beth", "bethel", "betsy", "bette", "betty", "bevel", "bevy", + "beware", "bey", "bezel", "bf", "bg", "bh", "bhoy", + "bi", "bias", "bib", "bibb", "bible", "bicep", "biceps", + "bid", "biddy", "bide", "bien", "big", "biggs", "bigot", + "bile", "bilge", "bilk", "bill", "billow", "billy", "bin", + "binary", "bind", "bing", "binge", "bingle", "bini", "biota", + "birch", "bird", "birdie", "birth", "bison", "bisque", "bit", + "bitch", "bite", "bitt", "bitten", "biz", "bizet", "bj", + "bk", "bl", "blab", "black", "blade", "blair", "blake", + "blame", "blanc", "bland", "blank", "blare", "blast", "blat", + "blatz", "blaze", "bleak", "bleat", "bled", "bleed", "blend", + "bless", "blest", "blew", "blimp", "blind", "blink", "blinn", + "blip", "bliss", "blithe", "blitz", "bloat", "blob", "bloc", + "bloch", "block", "bloke", "blond", "blonde", "blood", "bloom", + "bloop", "blot", "blotch", "blow", "blown", "blue", "bluet", + "bluff", "blum", "blunt", "blur", "blurt", "blush", "blvd", + "blythe", "bm", "bmw", "bn", "bo", "boa", "boar", + "board", "boast", "boat", "bob", "bobbin", "bobby", "bobcat", + "boca", "bock", "bode", "body", "bog", "bogey", "boggy", + "bogus", "bogy", "bohr", "boil", "bois", "boise", "bold", + "bole", "bolo", "bolt", "bomb", "bombay", "bon", "bona", + "bond", "bone", "bong", "bongo", "bonn", "bonus", "bony", + "bonze", "boo", "booby", "boogie", "book", "booky", "boom", + "boon", "boone", "boor", "boost", "boot", "booth", "booty", + "booze", "bop", "borax", "border", "bore", "borg", "boric", + "boris", "born", "borne", "borneo", "boron", "bosch", "bose", + "bosom", "boson", "boss", "boston", "botch", "both", "bottle", + "bough", "bouncy", "bound", "bourn", "bout", "bovine", "bow", + "bowel", "bowen", "bowie", "bowl", "box", "boxy", "boy", + "boyar", "boyce", "boyd", "boyle", "bp", "bq", "br", + "brace", "bract", "brad", "brady", "brae", "brag", "bragg", + "braid", "brain", "brainy", "brake", "bran", "brand", "brandt", + "brant", "brash", "brass", "brassy", "braun", "brave", "bravo", + "brawl", "bray", "bread", "break", "bream", "breath", "bred", + "breed", "breeze", "bremen", "brent", "brest", "brett", "breve", + "brew", "brian", "briar", "bribe", "brice", "brick", "bride", + "brief", "brig", "briggs", "brim", "brine", "bring", "brink", + "briny", "brisk", "broad", "brock", "broil", "broke", "broken", + "bronx", "brood", "brook", "brooke", "broom", "broth", "brow", + "brown", "browse", "bruce", "bruit", "brunch", "bruno", "brunt", + "brush", "brute", "bryan", "bryant", "bryce", "bryn", "bs", + "bstj", "bt", "btl", "bu", "bub", "buck", "bud", + "budd", "buddy", "budge", "buena", "buenos", "buff", "bug", + "buggy", "bugle", "buick", "build", "built", "bulb", "bulge", + "bulk", "bulky", "bull", "bully", "bum", "bump", "bun", + "bunch", "bundy", "bunk", "bunny", "bunt", "bunyan", "buoy", + "burch", "bureau", "buret", "burg", "buried", "burke", "burl", + "burly", "burma", "burn", "burnt", "burp", "burr", "burro", + "burst", "burt", "burton", "burtt", "bury", "bus", "busch", + "bush", "bushel", "bushy", "buss", "bust", "busy", "but", + "butane", "butch", "buteo", "butt", "butte", "butyl", "buxom", + "buy", "buyer", "buzz", "buzzy", "bv", "bw", "bx", + "by", "bye", "byers", "bylaw", "byline", "byrd", "byrne", + "byron", "byte", "byway", "byword", "bz", "c", "c's", + "ca", "cab", "cabal", "cabin", "cable", "cabot", "cacao", + "cache", "cacm", "cacti", "caddy", "cadent", "cadet", "cadre", + "cady", "cafe", "cage", "cagey", "cahill", "caiman", "cain", + "caine", "cairn", "cairo", "cake", "cal", "calder", "caleb", + "calf", "call", "calla", "callus", "calm", "calve", "cam", + "camber", "came", "camel", "cameo", "camp", "can", "can't", + "canal", "canary", "cancer", "candle", "candy", "cane", "canis", + "canna", "cannot", "canny", "canoe", "canon", "canopy", "cant", + "canto", "canton", "cap", "cape", "caper", "capo", "car", + "carbon", "card", "care", "caress", "caret", "carey", "cargo", + "carib", "carl", "carla", "carlo", "carne", "carob", "carol", + "carp", "carpet", "carr", "carrie", "carry", "carson", "cart", + "carte", "caruso", "carve", "case", "casey", "cash", "cashew", + "cask", "casket", "cast", "caste", "cat", "catch", "cater", + "cathy", "catkin", "catsup", "cauchy", "caulk", "cause", "cave", + "cavern", "cavil", "cavort", "caw", "cayuga", "cb", "cbs", + "cc", "ccc", "cccc", "cd", "cdc", "ce", "cease", + "cecil", "cedar", "cede", "ceil", "celia", "cell", "census", + "cent", "ceres", "cern", "cetera", "cetus", "cf", "cg", + "ch", "chad", "chafe", "chaff", "chai", "chain", "chair", + "chalk", "champ", "chance", "chang", "chant", "chao", "chaos", + "chap", "chapel", "char", "chard", "charm", "chart", "chase", + "chasm", "chaste", "chat", "chaw", "cheap", "cheat", "check", + "cheek", "cheeky", "cheer", "chef", "chen", "chert", "cherub", + "chess", "chest", "chevy", "chew", "chi", "chic", "chick", + "chide", "chief", "child", "chile", "chili", "chill", "chilly", + "chime", "chin", "china", "chine", "chink", "chip", "chirp", + "chisel", "chit", "chive", "chock", "choir", "choke", "chomp", + "chop", "chopin", "choral", "chord", "chore", "chose", "chosen", + "chou", "chow", "chris", "chub", "chuck", "chuff", "chug", + "chum", "chump", "chunk", "churn", "chute", "ci", "cia", + "cicada", "cider", "cigar", "cilia", "cinch", "cindy", "cipher", + "circa", "circe", "cite", "citrus", "city", "civet", "civic", + "civil", "cj", "ck", "cl", "clad", "claim", "clam", + "clammy", "clamp", "clan", "clang", "clank", "clap", "clara", + "clare", "clark", "clarke", "clash", "clasp", "class", "claus", + "clause", "claw", "clay", "clean", "clear", "cleat", "cleft", + "clerk", "cliche", "click", "cliff", "climb", "clime", "cling", + "clink", "clint", "clio", "clip", "clive", "cloak", "clock", + "clod", "clog", "clomp", "clone", "close", "closet", "clot", + "cloth", "cloud", "clout", "clove", "clown", "cloy", "club", + "cluck", "clue", "cluj", "clump", "clumsy", "clung", "clyde", + "cm", "cn", "co", "coach", "coal", "coast", "coat", + "coax", "cobb", "cobble", "cobol", "cobra", "coca", "cock", + "cockle", "cocky", "coco", "cocoa", "cod", "coda", "coddle", + "code", "codon", "cody", "coed", "cog", "cogent", "cohen", + "cohn", "coil", "coin", "coke", "col", "cola", "colby", + "cold", "cole", "colon", "colony", "colt", "colza", "coma", + "comb", "combat", "come", "comet", "cometh", "comic", "comma", + "con", "conch", "cone", "coney", "congo", "conic", "conn", + "conner", "conway", "cony", "coo", "cook", "cooke", "cooky", + "cool", "cooley", "coon", "coop", "coors", "coot", "cop", + "cope", "copra", "copy", "coral", "corbel", "cord", "core", + "corey", "cork", "corn", "corny", "corp", "corps", "corvus", + "cos", "cosec", "coset", "cosh", "cost", "costa", "cosy", + "cot", "cotta", "cotty", "couch", "cough", "could", "count", + "coup", "coupe", "court", "cousin", "cove", "coven", "cover", + "covet", "cow", "cowan", "cowl", "cowman", "cowry", "cox", + "coy", "coyote", "coypu", "cozen", "cozy", "cp", "cpa", + "cq", "cr", "crab", "crack", "craft", "crag", "craig", + "cram", "cramp", "crane", "crank", "crap", "crash", "crass", + "crate", "crater", "crave", "craw", "crawl", "craze", "crazy", + "creak", "cream", "credit", "credo", "creed", "creek", "creep", + "creole", "creon", "crepe", "crept", "cress", "crest", "crete", + "crew", "crib", "cried", "crime", "crimp", "crisp", "criss", + "croak", "crock", "crocus", "croft", "croix", "crone", "crony", + "crook", "croon", "crop", "cross", "crow", "crowd", "crown", + "crt", "crud", "crude", "cruel", "crumb", "crump", "crush", + "crust", "crux", "cruz", "cry", "crypt", "cs", "ct", + "cu", "cub", "cuba", "cube", "cubic", "cud", "cuddle", + "cue", "cuff", "cull", "culpa", "cult", "cumin", "cuny", + "cup", "cupful", "cupid", "cur", "curb", "curd", "cure", + "curfew", "curia", "curie", "curio", "curl", "curry", "curse", + "curt", "curve", "cusp", "cut", "cute", "cutlet", "cv", + "cw", "cx", "cy", "cycad", "cycle", "cynic", "cyril", + "cyrus", "cyst", "cz", "czar", "czech", "d", "d'art", + "d's", "da", "dab", "dacca", "dactyl", "dad", "dada", + "daddy", "dade", "daffy", "dahl", "dahlia", "dairy", "dais", + "daisy", "dakar", "dale", "daley", "dally", "daly", "dam", + "dame", "damn", "damon", "damp", "damsel", "dan", "dana", + "dance", "dandy", "dane", "dang", "dank", "danny", "dante", + "dar", "dare", "dark", "darken", "darn", "darry", "dart", + "dash", "data", "date", "dater", "datum", "daub", "daunt", + "dave", "david", "davis", "davit", "davy", "dawn", "dawson", + "day", "daze", "db", "dc", "dd", "ddd", "dddd", + "de", "deacon", "dead", "deaf", "deal", "dealt", "dean", + "deane", "dear", "death", "debar", "debby", "debit", "debra", + "debris", "debt", "debug", "debut", "dec", "decal", "decay", + "decca", "deck", "decker", "decor", "decree", "decry", "dee", + "deed", "deem", "deep", "deer", "deere", "def", "defer", + "deform", "deft", "defy", "degas", "degum", "deify", "deign", + "deity", "deja", "del", "delay", "delft", "delhi", "delia", + "dell", "della", "delta", "delve", "demark", "demit", "demon", + "demur", "den", "deneb", "denial", "denny", "dense", "dent", + "denton", "deny", "depot", "depth", "depute", "derby", "derek", + "des", "desist", "desk", "detach", "deter", "deuce", "deus", + "devil", "devoid", "devon", "dew", "dewar", "dewey", "dewy", + "dey", "df", "dg", "dh", "dhabi", "di", "dial", + "diana", "diane", "diary", "dibble", "dice", "dick", "dicta", + "did", "dido", "die", "died", "diego", "diem", "diesel", + "diet", "diety", "dietz", "dig", "digit", "dilate", "dill", + "dim", "dime", "din", "dinah", "dine", "ding", "dingo", + "dingy", "dint", "diode", "dip", "dirac", "dire", "dirge", + "dirt", "dirty", "dis", "disc", "dish", "disk", "disney", + "ditch", "ditto", "ditty", "diva", "divan", "dive", "dixie", + "dixon", "dizzy", "dj", "dk", "dl", "dm", "dn", + "dna", "do", "dobbs", "dobson", "dock", "docket", "dod", + "dodd", "dodge", "dodo", "doe", "doff", "dog", "doge", + "dogma", "dolan", "dolce", "dole", "doll", "dolly", "dolt", + "dome", "don", "don't", "done", "doneck", "donna", "donor", + "doom", "door", "dope", "dora", "doria", "doric", "doris", + "dose", "dot", "dote", "double", "doubt", "douce", "doug", + "dough", "dour", "douse", "dove", "dow", "dowel", "down", + "downs", "dowry", "doyle", "doze", "dozen", "dp", "dq", + "dr", "drab", "draco", "draft", "drag", "drain", "drake", + "dram", "drama", "drank", "drape", "draw", "drawl", "drawn", + "dread", "dream", "dreamy", "dreg", "dress", "dressy", "drew", + "drib", "dried", "drier", "drift", "drill", "drink", "drip", + "drive", "droll", "drone", "drool", "droop", "drop", "dross", + "drove", "drown", "drub", "drug", "druid", "drum", "drunk", + "drury", "dry", "dryad", "ds", "dt", "du", "dual", + "duane", "dub", "dubhe", "dublin", "ducat", "duck", "duct", + "dud", "due", "duel", "duet", "duff", "duffy", "dug", + "dugan", "duke", "dull", "dully", "dulse", "duly", "duma", + "dumb", "dummy", "dump", "dumpy", "dun", "dunce", "dune", + "dung", "dunham", "dunk", "dunlop", "dunn", "dupe", "durer", + "dusk", "dusky", "dust", "dusty", "dutch", "duty", "dv", + "dw", "dwarf", "dwell", "dwelt", "dwight", "dwyer", "dx", + "dy", "dyad", "dye", "dyer", "dying", "dyke", "dylan", + "dyne", "dz", "e", "e'er", "e's", "ea", "each", + "eagan", "eager", "eagle", "ear", "earl", "earn", "earth", + "ease", "easel", "east", "easy", "eat", "eaten", "eater", + "eaton", "eave", "eb", "ebb", "eben", "ebony", "ec", + "echo", "eclat", "ecole", "ed", "eddie", "eddy", "eden", + "edgar", "edge", "edgy", "edict", "edify", "edit", "edith", + "editor", "edna", "edt", "edwin", "ee", "eee", "eeee", + "eel", "eeoc", "eerie", "ef", "efface", "effie", "efg", + "eft", "eg", "egan", "egg", "ego", "egress", "egret", + "egypt", "eh", "ei", "eider", "eight", "eire", "ej", + "eject", "ek", "eke", "el", "elan", "elate", "elba", + "elbow", "elder", "eldon", "elect", "elegy", "elena", "eleven", + "elfin", "elgin", "eli", "elide", "eliot", "elite", "elk", + "ell", "ella", "ellen", "ellis", "elm", "elmer", "elope", + "else", "elsie", "elton", "elude", "elute", "elves", "ely", + "em", "embalm", "embark", "embed", "ember", "emcee", "emery", + "emil", "emile", "emily", "emit", "emma", "emory", "empty", + "en", "enact", "enamel", "end", "endow", "enemy", "eng", + "engel", "engle", "engulf", "enid", "enjoy", "enmity", "enoch", + "enol", "enos", "enrico", "ensue", "enter", "entrap", "entry", + "envoy", "envy", "eo", "ep", "epa", "epic", "epoch", + "epoxy", "epsom", "eq", "equal", "equip", "er", "era", + "erase", "erato", "erda", "ere", "erect", "erg", "eric", + "erich", "erie", "erik", "ernest", "ernie", "ernst", "erode", + "eros", "err", "errand", "errol", "error", "erupt", "ervin", + "erwin", "es", "essay", "essen", "essex", "est", "ester", + "estes", "estop", "et", "eta", "etc", "etch", "ethan", + "ethel", "ether", "ethic", "ethos", "ethyl", "etude", "eu", + "eucre", "euler", "eureka", "ev", "eva", "evade", "evans", + "eve", "even", "event", "every", "evict", "evil", "evoke", + "evolve", "ew", "ewe", "ewing", "ex", "exact", "exalt", + "exam", "excel", "excess", "exert", "exile", "exist", "exit", + "exodus", "expel", "extant", "extent", "extol", "extra", "exude", + "exult", "exxon", "ey", "eye", "eyed", "ez", "ezra", + "f", "f's", "fa", "faa", "faber", "fable", "face", + "facet", "facile", "fact", "facto", "fad", "fade", "faery", + "fag", "fahey", "fail", "fain", "faint", "fair", "fairy", + "faith", "fake", "fall", "false", "fame", "fan", "fancy", + "fang", "fanny", "fanout", "far", "farad", "farce", "fare", + "fargo", "farley", "farm", "faro", "fast", "fat", "fatal", + "fate", "fatty", "fault", "faun", "fauna", "faust", "fawn", + "fay", "faze", "fb", "fbi", "fc", "fcc", "fd", + "fda", "fe", "fear", "feast", "feat", "feb", "fed", + "fee", "feed", "feel", "feet", "feign", "feint", "felice", + "felix", "fell", "felon", "felt", "femur", "fence", "fend", + "fermi", "fern", "ferric", "ferry", "fest", "fetal", "fetch", + "fete", "fetid", "fetus", "feud", "fever", "few", "ff", + "fff", "ffff", "fg", "fgh", "fh", "fi", "fiat", + "fib", "fibrin", "fiche", "fide", "fief", "field", "fiend", + "fiery", "fife", "fifo", "fifth", "fifty", "fig", "fight", + "filch", "file", "filet", "fill", "filler", "filly", "film", + "filmy", "filth", "fin", "final", "finale", "finch", "find", + "fine", "finite", "fink", "finn", "finny", "fir", "fire", + "firm", "first", "fish", "fishy", "fisk", "fiske", "fist", + "fit", "fitch", "five", "fix", "fj", "fjord", "fk", + "fl", "flack", "flag", "flail", "flair", "flak", "flake", + "flaky", "flam", "flame", "flank", "flap", "flare", "flash", + "flask", "flat", "flatus", "flaw", "flax", "flea", "fleck", + "fled", "flee", "fleet", "flesh", "flew", "flex", "flick", + "flier", "flinch", "fling", "flint", "flip", "flirt", "flit", + "flo", "float", "floc", "flock", "floe", "flog", "flood", + "floor", "flop", "floppy", "flora", "flour", "flout", "flow", + "flown", "floyd", "flu", "flub", "flue", "fluff", "fluid", + "fluke", "flung", "flush", "flute", "flux", "fly", "flyer", + "flynn", "fm", "fmc", "fn", "fo", "foal", "foam", + "foamy", "fob", "focal", "foci", "focus", "fodder", "foe", + "fog", "foggy", "fogy", "foil", "foist", "fold", "foley", + "folio", "folk", "folly", "fond", "font", "food", "fool", + "foot", "foote", "fop", "for", "foray", "force", "ford", + "fore", "forge", "forgot", "fork", "form", "fort", "forte", + "forth", "forty", "forum", "foss", "fossil", "foul", "found", + "fount", "four", "fovea", "fowl", "fox", "foxy", "foyer", + "fp", "fpc", "fq", "fr", "frail", "frame", "fran", + "franc", "franca", "frank", "franz", "frau", "fraud", "fray", + "freak", "fred", "free", "freed", "freer", "frenzy", "freon", + "fresh", "fret", "freud", "frey", "freya", "friar", "frick", + "fried", "frill", "frilly", "frisky", "fritz", "fro", "frock", + "frog", "from", "front", "frost", "froth", "frown", "froze", + "fruit", "fry", "frye", "fs", "ft", "ftc", "fu", + "fuchs", "fudge", "fuel", "fugal", "fugue", "fuji", "full", + "fully", "fum", "fume", "fun", "fund", "fungal", "fungi", + "funk", "funny", "fur", "furl", "furry", "fury", "furze", + "fuse", "fuss", "fussy", "fusty", "fuzz", "fuzzy", "fv", + "fw", "fx", "fy", "fz", "g", "g's", "ga", + "gab", "gable", "gabon", "gad", "gadget", "gaff", "gaffe", + "gag", "gage", "gail", "gain", "gait", "gal", "gala", + "galaxy", "gale", "galen", "gall", "gallop", "galt", "gam", + "game", "gamin", "gamma", "gamut", "gander", "gang", "gao", + "gap", "gape", "gar", "garb", "garish", "garner", "garry", + "garth", "gary", "gas", "gash", "gasp", "gassy", "gate", + "gates", "gator", "gauche", "gaudy", "gauge", "gaul", "gaunt", + "gaur", "gauss", "gauze", "gave", "gavel", "gavin", "gawk", + "gawky", "gay", "gaze", "gb", "gc", "gd", "ge", + "gear", "gecko", "gee", "geese", "geigy", "gel", "geld", + "gem", "gemma", "gene", "genie", "genii", "genoa", "genre", + "gent", "gentry", "genus", "gerbil", "germ", "gerry", "get", + "getty", "gf", "gg", "ggg", "gggg", "gh", "ghana", + "ghent", "ghetto", "ghi", "ghost", "ghoul", "gi", "giant", + "gibbs", "gibby", "gibe", "giddy", "gift", "gig", "gil", + "gila", "gild", "giles", "gill", "gilt", "gimbal", "gimpy", + "gin", "gina", "ginn", "gino", "gird", "girl", "girth", + "gist", "give", "given", "gj", "gk", "gl", "glad", + "gladdy", "glade", "glamor", "gland", "glans", "glare", "glass", + "glaze", "gleam", "glean", "glee", "glen", "glenn", "glib", + "glide", "glint", "gloat", "glob", "globe", "glom", "gloom", + "glory", "gloss", "glove", "glow", "glue", "glued", "gluey", + "gluing", "glum", "glut", "glyph", "gm", "gmt", "gn", + "gnarl", "gnash", "gnat", "gnaw", "gnome", "gnp", "gnu", + "go", "goa", "goad", "goal", "goat", "gob", "goer", + "goes", "goff", "gog", "goggle", "gogh", "gogo", "gold", + "golf", "golly", "gone", "gong", "goo", "good", "goode", + "goody", "goof", "goofy", "goose", "gop", "gordon", "gore", + "goren", "gorge", "gorky", "gorse", "gory", "gosh", "gospel", + "got", "gouda", "gouge", "gould", "gourd", "gout", "gown", + "gp", "gpo", "gq", "gr", "grab", "grace", "grad", + "grade", "grady", "graff", "graft", "grail", "grain", "grand", + "grant", "grape", "graph", "grasp", "grass", "grata", "grate", + "grater", "grave", "gravy", "gray", "graze", "great", "grebe", + "greed", "greedy", "greek", "green", "greer", "greet", "greg", + "gregg", "greta", "grew", "grey", "grid", "grief", "grieve", + "grill", "grim", "grime", "grimm", "grin", "grind", "grip", + "gripe", "grist", "grit", "groan", "groat", "groin", "groom", + "grope", "gross", "groton", "group", "grout", "grove", "grow", + "growl", "grown", "grub", "gruff", "grunt", "gs", "gsa", + "gt", "gu", "guam", "guano", "guard", "guess", "guest", + "guide", "guild", "guile", "guilt", "guise", "guitar", "gules", + "gulf", "gull", "gully", "gulp", "gum", "gumbo", "gummy", + "gun", "gunk", "gunky", "gunny", "gurgle", "guru", "gus", + "gush", "gust", "gusto", "gusty", "gut", "gutsy", "guy", + "guyana", "gv", "gw", "gwen", "gwyn", "gx", "gy", + "gym", "gyp", "gypsy", "gyro", "gz", "h", "h's", + "ha", "haag", "haas", "habib", "habit", "hack", "had", + "hades", "hadron", "hagen", "hager", "hague", "hahn", "haifa", + "haiku", "hail", "hair", "hairy", "haiti", "hal", "hale", + "haley", "half", "hall", "halma", "halo", "halt", "halvah", + "halve", "ham", "hamal", "hamlin", "han", "hand", "handy", + "haney", "hang", "hank", "hanna", "hanoi", "hans", "hansel", + "hap", "happy", "hard", "hardy", "hare", "harem", "hark", + "harley", "harm", "harp", "harpy", "harry", "harsh", "hart", + "harvey", "hash", "hasp", "hast", "haste", "hasty", "hat", + "hatch", "hate", "hater", "hath", "hatred", "haul", "haunt", + "have", "haven", "havoc", "haw", "hawk", "hay", "haydn", + "hayes", "hays", "hazard", "haze", "hazel", "hazy", "hb", + "hc", "hd", "he", "he'd", "he'll", "head", "heady", + "heal", "healy", "heap", "hear", "heard", "heart", "heat", + "heath", "heave", "heavy", "hebe", "hebrew", "heck", "heckle", + "hedge", "heed", "heel", "heft", "hefty", "heigh", "heine", + "heinz", "heir", "held", "helen", "helga", "helix", "hell", + "hello", "helm", "helmut", "help", "hem", "hemp", "hen", + "hence", "henri", "henry", "her", "hera", "herb", "herd", + "here", "hero", "heroic", "heron", "herr", "hertz", "hess", + "hesse", "hettie", "hetty", "hew", "hewitt", "hewn", "hex", + "hey", "hf", "hg", "hh", "hhh", "hhhh", "hi", + "hiatt", "hick", "hicks", "hid", "hide", "high", "hij", + "hike", "hill", "hilly", "hilt", "hilum", "him", "hind", + "hindu", "hines", "hinge", "hint", "hip", "hippo", "hippy", + "hiram", "hire", "hirsch", "his", "hiss", "hit", "hitch", + "hive", "hj", "hk", "hl", "hm", "hn", "ho", + "hoagy", "hoar", "hoard", "hob", "hobbs", "hobby", "hobo", + "hoc", "hock", "hodge", "hodges", "hoe", "hoff", "hog", + "hogan", "hoi", "hokan", "hold", "holdup", "hole", "holly", + "holm", "holst", "holt", "home", "homo", "honda", "hondo", + "hone", "honey", "hong", "honk", "hooch", "hood", "hoof", + "hook", "hookup", "hoop", "hoot", "hop", "hope", "horde", + "horn", "horny", "horse", "horus", "hose", "host", "hot", + "hotbox", "hotel", "hough", "hound", "hour", "house", "hove", + "hovel", "hover", "how", "howdy", "howe", "howl", "hoy", + "hoyt", "hp", "hq", "hr", "hs", "ht", "hu", + "hub", "hubbub", "hubby", "huber", "huck", "hue", "hued", + "huff", "hug", "huge", "hugh", "hughes", "hugo", "huh", + "hulk", "hull", "hum", "human", "humid", "hump", "humus", + "hun", "hunch", "hung", "hunk", "hunt", "hurd", "hurl", + "huron", "hurrah", "hurry", "hurst", "hurt", "hurty", "hush", + "husky", "hut", "hutch", "hv", "hw", "hx", "hy", + "hyde", "hydra", "hydro", "hyena", "hying", "hyman", "hymen", + "hymn", "hymnal", "hz", "i", "i'd", "i'll", "i'm", + "i's", "i've", "ia", "iambic", "ian", "ib", "ibex", + "ibid", "ibis", "ibm", "ibn", "ic", "icc", "ice", + "icing", "icky", "icon", "icy", "id", "ida", "idaho", + "idea", "ideal", "idiom", "idiot", "idle", "idol", "idyll", + "ie", "ieee", "if", "iffy", "ifni", "ig", "igloo", + "igor", "ih", "ii", "iii", "iiii", "ij", "ijk", + "ik", "ike", "il", "ileum", "iliac", "iliad", "ill", + "illume", "ilona", "im", "image", "imbue", "imp", "impel", + "import", "impute", "in", "inane", "inapt", "inc", "inca", + "incest", "inch", "incur", "index", "india", "indies", "indy", + "inept", "inert", "infect", "infer", "infima", "infix", "infra", + "ingot", "inhere", "injun", "ink", "inlay", "inlet", "inman", + "inn", "inner", "input", "insect", "inset", "insult", "intend", + "inter", "into", "inure", "invoke", "io", "ion", "ionic", + "iota", "iowa", "ip", "ipso", "iq", "ir", "ira", + "iran", "iraq", "irate", "ire", "irene", "iris", "irish", + "irk", "irma", "iron", "irony", "irs", "irvin", "irwin", + "is", "isaac", "isabel", "ising", "isis", "islam", "island", + "isle", "isn't", "israel", "issue", "it", "it&t", "it'd", + "it'll", "italy", "itch", "item", "ito", "itt", "iu", + "iv", "ivan", "ive", "ivory", "ivy", "iw", "ix", + "iy", "iz", "j", "j's", "ja", "jab", "jack", + "jacky", "jacm", "jacob", "jacobi", "jade", "jag", "jail", + "jaime", "jake", "jam", "james", "jan", "jane", "janet", + "janos", "janus", "japan", "jar", "jason", "java", "jaw", + "jay", "jazz", "jazzy", "jb", "jc", "jd", "je", + "jean", "jed", "jeep", "jeff", "jejune", "jelly", "jenny", + "jeres", "jerk", "jerky", "jerry", "jersey", "jess", "jesse", + "jest", "jesus", "jet", "jew", "jewel", "jewett", "jewish", + "jf", "jg", "jh", "ji", "jibe", "jiffy", "jig", + "jill", "jilt", "jim", "jimmy", "jinx", "jive", "jj", + "jjj", "jjjj", "jk", "jkl", "jl", "jm", "jn", + "jo", "joan", "job", "jock", "jockey", "joe", "joel", + "joey", "jog", "john", "johns", "join", "joint", "joke", + "jolla", "jolly", "jolt", "jon", "jonas", "jones", "jorge", + "jose", "josef", "joshua", "joss", "jostle", "jot", "joule", + "joust", "jove", "jowl", "jowly", "joy", "joyce", "jp", + "jq", "jr", "js", "jt", "ju", "juan", "judas", + "judd", "jude", "judge", "judo", "judy", "jug", "juggle", + "juice", "juicy", "juju", "juke", "jukes", "julep", "jules", + "julia", "julie", "julio", "july", "jumbo", "jump", "jumpy", + "junco", "june", "junk", "junky", "juno", "junta", "jura", + "jure", "juror", "jury", "just", "jut", "jute", "jv", + "jw", "jx", "jy", "jz", "k", "k's", "ka", + "kabul", "kafka", "kahn", "kajar", "kale", "kalmia", "kane", + "kant", "kapok", "kappa", "karate", "karen", "karl", "karma", + "karol", "karp", "kate", "kathy", "katie", "katz", "kava", + "kay", "kayo", "kazoo", "kb", "kc", "kd", "ke", + "keats", "keel", "keen", "keep", "keg", "keith", "keller", + "kelly", "kelp", "kemp", "ken", "keno", "kent", "kenya", + "kepler", "kept", "kern", "kerr", "kerry", "ketch", "kevin", + "key", "keyed", "keyes", "keys", "kf", "kg", "kh", + "khaki", "khan", "khmer", "ki", "kick", "kid", "kidde", + "kidney", "kiev", "kigali", "kill", "kim", "kin", "kind", + "king", "kink", "kinky", "kiosk", "kiowa", "kirby", "kirk", + "kirov", "kiss", "kit", "kite", "kitty", "kiva", "kivu", + "kiwi", "kj", "kk", "kkk", "kkkk", "kl", "klan", + "klaus", "klein", "kline", "klm", "klux", "km", "kn", + "knack", "knapp", "knauer", "knead", "knee", "kneel", "knelt", + "knew", "knick", "knife", "knit", "knob", "knock", "knoll", + "knot", "knott", "know", "known", "knox", "knurl", "ko", + "koala", "koch", "kodak", "kola", "kombu", "kong", "koran", + "korea", "kp", "kq", "kr", "kraft", "krause", "kraut", + "krebs", "kruse", "ks", "kt", "ku", "kudo", "kudzu", + "kuhn", "kulak", "kurd", "kurt", "kv", "kw", "kx", + "ky", "kyle", "kyoto", "kz", "l", "l's", "la", + "lab", "laban", "label", "labia", "labile", "lac", "lace", + "lack", "lacy", "lad", "laden", "ladle", "lady", "lag", + "lager", "lagoon", "lagos", "laid", "lain", "lair", "laity", + "lake", "lam", "lamar", "lamb", "lame", "lamp", "lana", + "lance", "land", "lane", "lang", "lange", "lanka", "lanky", + "lao", "laos", "lap", "lapel", "lapse", "larch", "lard", + "lares", "large", "lark", "larkin", "larry", "lars", "larva", + "lase", "lash", "lass", "lasso", "last", "latch", "late", + "later", "latest", "latex", "lath", "lathe", "latin", "latus", + "laud", "laue", "laugh", "launch", "laura", "lava", "law", + "lawn", "lawson", "lax", "lay", "layup", "laze", "lazy", + "lb", "lc", "ld", "le", "lea", "leach", "lead", + "leaf", "leafy", "leak", "leaky", "lean", "leap", "leapt", + "lear", "learn", "lease", "leash", "least", "leave", "led", + "ledge", "lee", "leech", "leeds", "leek", "leer", "leery", + "leeway", "left", "lefty", "leg", "legal", "leggy", "legion", + "leigh", "leila", "leland", "lemma", "lemon", "len", "lena", + "lend", "lenin", "lenny", "lens", "lent", "leo", "leon", + "leona", "leone", "leper", "leroy", "less", "lessee", "lest", + "let", "lethe", "lev", "levee", "level", "lever", "levi", + "levin", "levis", "levy", "lew", "lewd", "lewis", "leyden", + "lf", "lg", "lh", "li", "liar", "libel", "libido", + "libya", "lice", "lick", "lid", "lie", "lied", "lien", + "lieu", "life", "lifo", "lift", "light", "like", "liken", + "lila", "lilac", "lilly", "lilt", "lily", "lima", "limb", + "limbo", "lime", "limit", "limp", "lin", "lind", "linda", + "linden", "line", "linen", "lingo", "link", "lint", "linus", + "lion", "lip", "lipid", "lisa", "lise", "lisle", "lisp", + "list", "listen", "lit", "lithe", "litton", "live", "liven", + "livid", "livre", "liz", "lizzie", "lj", "lk", "ll", + "lll", "llll", "lloyd", "lm", "lmn", "ln", "lo", + "load", "loaf", "loam", "loamy", "loan", "loath", "lob", + "lobar", "lobby", "lobe", "lobo", "local", "loci", "lock", + "locke", "locus", "lodge", "loeb", "loess", "loft", "lofty", + "log", "logan", "loge", "logic", "loin", "loire", "lois", + "loiter", "loki", "lola", "loll", "lolly", "lomb", "lome", + "lone", "long", "look", "loom", "loon", "loop", "loose", + "loot", "lop", "lope", "lopez", "lord", "lore", "loren", + "los", "lose", "loss", "lossy", "lost", "lot", "lotte", + "lotus", "lou", "loud", "louis", "louise", "louse", "lousy", + "louver", "love", "low", "lowe", "lower", "lowry", "loy", + "loyal", "lp", "lq", "lr", "ls", "lsi", "lt", + "ltv", "lu", "lucas", "lucia", "lucid", "luck", "lucky", + "lucre", "lucy", "lug", "luge", "luger", "luis", "luke", + "lull", "lulu", "lumbar", "lumen", "lump", "lumpy", "lunar", + "lunch", "lund", "lung", "lunge", "lura", "lurch", "lure", + "lurid", "lurk", "lush", "lust", "lusty", "lute", "lutz", + "lux", "luxe", "luzon", "lv", "lw", "lx", "ly", + "lydia", "lye", "lying", "lykes", "lyle", "lyman", "lymph", + "lynch", "lynn", "lynx", "lyon", "lyons", "lyra", "lyric", + "lz", "m", "m&m", "m's", "ma", "mabel", "mac", + "mace", "mach", "macho", "mack", "mackey", "macon", "macro", + "mad", "madam", "made", "madman", "madsen", "mae", "magi", + "magic", "magma", "magna", "magog", "maid", "maier", "mail", + "maim", "main", "maine", "major", "make", "malady", "malay", + "male", "mali", "mall", "malt", "malta", "mambo", "mamma", + "mammal", "man", "mana", "manama", "mane", "mange", "mania", + "manic", "mann", "manna", "manor", "mans", "manse", "mantle", + "many", "mao", "maori", "map", "maple", "mar", "marc", + "march", "marco", "marcy", "mardi", "mare", "margo", "maria", + "marie", "marin", "marine", "mario", "mark", "marks", "marlin", + "marrow", "marry", "mars", "marsh", "mart", "marty", "marx", + "mary", "maser", "mash", "mask", "mason", "masque", "mass", + "mast", "mat", "match", "mate", "mateo", "mater", "math", + "matte", "maul", "mauve", "mavis", "maw", "mawr", "max", + "maxim", "maxima", "may", "maya", "maybe", "mayer", "mayhem", + "mayo", "mayor", "mayst", "mazda", "maze", "mb", "mba", + "mc", "mccoy", "mcgee", "mckay", "mckee", "mcleod", "md", + "me", "mead", "meal", "mealy", "mean", "meant", "meat", + "meaty", "mecca", "mecum", "medal", "medea", "media", "medic", + "medley", "meek", "meet", "meg", "mega", "meier", "meir", + "mel", "meld", "melee", "mellow", "melon", "melt", "memo", + "memoir", "men", "mend", "menlo", "menu", "merck", "mercy", + "mere", "merge", "merit", "merle", "merry", "mesa", "mescal", + "mesh", "meson", "mess", "messy", "met", "metal", "mete", + "meter", "metro", "mew", "meyer", "meyers", "mezzo", "mf", + "mg", "mh", "mi", "miami", "mica", "mice", "mickey", + "micky", "micro", "mid", "midas", "midge", "midst", "mien", + "miff", "mig", "might", "mike", "mila", "milan", "milch", + "mild", "mildew", "mile", "miles", "milk", "milky", "mill", + "mills", "milt", "mimi", "mimic", "mince", "mind", "mine", + "mini", "minim", "mink", "minnow", "minor", "minos", "minot", + "minsk", "mint", "minus", "mira", "mirage", "mire", "mirth", + "miser", "misery", "miss", "missy", "mist", "misty", "mit", + "mite", "mitre", "mitt", "mix", "mixup", "mizar", "mj", + "mk", "ml", "mm", "mmm", "mmmm", "mn", "mno", + "mo", "moan", "moat", "mob", "mobil", "mock", "modal", + "mode", "model", "modem", "modish", "moe", "moen", "mohr", + "moire", "moist", "molal", "molar", "mold", "mole", "moll", + "mollie", "molly", "molt", "molten", "mommy", "mona", "monad", + "mondo", "monel", "money", "monic", "monk", "mont", "monte", + "month", "monty", "moo", "mood", "moody", "moon", "moor", + "moore", "moose", "moot", "mop", "moral", "morale", "moran", + "more", "morel", "morn", "moron", "morse", "morsel", "mort", + "mosaic", "moser", "moses", "moss", "mossy", "most", "mot", + "motel", "motet", "moth", "mother", "motif", "motor", "motto", + "mould", "mound", "mount", "mourn", "mouse", "mousy", "mouth", + "move", "movie", "mow", "moyer", "mp", "mph", "mq", + "mr", "mrs", "ms", "mt", "mu", "much", "muck", + "mucus", "mud", "mudd", "muddy", "muff", "muffin", "mug", + "muggy", "mugho", "muir", "mulch", "mulct", "mule", "mull", + "multi", "mum", "mummy", "munch", "mung", "munson", "muon", + "muong", "mural", "muriel", "murk", "murky", "murre", "muse", + "mush", "mushy", "music", "musk", "muslim", "must", "musty", + "mute", "mutt", "muzak", "muzo", "mv", "mw", "mx", + "my", "myel", "myers", "mylar", "mynah", "myopia", "myra", + "myron", "myrrh", "myself", "myth", "mz", "n", "n's", + "na", "naacp", "nab", "nadir", "nag", "nagoya", "nagy", + "naiad", "nail", "nair", "naive", "naked", "name", "nan", + "nancy", "naomi", "nap", "nary", "nasa", "nasal", "nash", + "nasty", "nat", "natal", "nate", "nato", "natty", "nature", + "naval", "nave", "navel", "navy", "nay", "nazi", "nb", + "nbc", "nbs", "nc", "ncaa", "ncr", "nd", "ne", + "neal", "near", "neat", "neath", "neck", "ned", "nee", + "need", "needy", "neff", "negate", "negro", "nehru", "neil", + "nell", "nelsen", "neon", "nepal", "nero", "nerve", "ness", + "nest", "net", "neuron", "neva", "neve", "new", "newel", + "newt", "next", "nf", "ng", "nh", "ni", "nib", + "nibs", "nice", "nicety", "niche", "nick", "niece", "niger", + "nigh", "night", "nih", "nikko", "nil", "nile", "nimbus", + "nimh", "nina", "nine", "ninth", "niobe", "nip", "nit", + "nitric", "nitty", "nixon", "nj", "nk", "nl", "nm", + "nn", "nnn", "nnnn", "no", "noaa", "noah", "nob", + "nobel", "noble", "nod", "nodal", "node", "noel", "noise", + "noisy", "nolan", "noll", "nolo", "nomad", "non", "nonce", + "none", "nook", "noon", "noose", "nop", "nor", "nora", + "norm", "norma", "north", "norway", "nose", "not", "notch", + "note", "notre", "noun", "nov", "nova", "novak", "novel", + "novo", "now", "np", "nq", "nr", "nrc", "ns", + "nsf", "nt", "ntis", "nu", "nuance", "nubia", "nuclei", + "nude", "nudge", "null", "numb", "nun", "nurse", "nut", + "nv", "nw", "nx", "ny", "nyc", "nylon", "nymph", + "nyu", "nz", "o", "o'er", "o's", "oa", "oaf", + "oak", "oaken", "oakley", "oar", "oases", "oasis", "oat", + "oath", "ob", "obese", "obey", "objet", "oboe", "oc", + "occur", "ocean", "oct", "octal", "octave", "octet", "od", + "odd", "ode", "odin", "odium", "oe", "of", "off", + "offal", "offend", "offer", "oft", "often", "og", "ogden", + "ogle", "ogre", "oh", "ohio", "ohm", "ohmic", "oi", + "oil", "oily", "oint", "oj", "ok", "okay", "ol", + "olaf", "olav", "old", "olden", "oldy", "olga", "olin", + "olive", "olsen", "olson", "om", "omaha", "oman", "omega", + "omen", "omit", "on", "once", "one", "onion", "only", + "onset", "onto", "onus", "onward", "onyx", "oo", "ooo", + "oooo", "ooze", "op", "opal", "opec", "opel", "open", + "opera", "opium", "opt", "optic", "opus", "oq", "or", + "oral", "orate", "orb", "orbit", "orchid", "ordain", "order", + "ore", "organ", "orgy", "orin", "orion", "ornery", "orono", + "orr", "os", "osaka", "oscar", "osier", "oslo", "ot", + "other", "otis", "ott", "otter", "otto", "ou", "ouch", + "ought", "ounce", "our", "oust", "out", "ouvre", "ouzel", + "ouzo", "ov", "ova", "oval", "ovary", "ovate", "oven", + "over", "overt", "ovid", "ow", "owe", "owens", "owing", + "owl", "owly", "own", "ox", "oxen", "oxeye", "oxide", + "oxnard", "oy", "oz", "ozark", "ozone", "p", "p's", + "pa", "pablo", "pabst", "pace", "pack", "packet", "pact", + "pad", "paddy", "padre", "paean", "pagan", "page", "paid", + "pail", "pain", "paine", "paint", "pair", "pal", "pale", + "pall", "palm", "palo", "palsy", "pam", "pampa", "pan", + "panama", "panda", "pane", "panel", "pang", "panic", "pansy", + "pant", "panty", "paoli", "pap", "papa", "papal", "papaw", + "paper", "pappy", "papua", "par", "parch", "pardon", "pare", + "pareto", "paris", "park", "parke", "parks", "parr", "parry", + "parse", "part", "party", "pascal", "pasha", "paso", "pass", + "passe", "past", "paste", "pasty", "pat", "patch", "pate", + "pater", "path", "patio", "patsy", "patti", "patton", "patty", + "paul", "paula", "pauli", "paulo", "pause", "pave", "paw", + "pawn", "pax", "pay", "payday", "payne", "paz", "pb", + "pbs", "pc", "pd", "pe", "pea", "peace", "peach", + "peak", "peaky", "peal", "peale", "pear", "pearl", "pease", + "peat", "pebble", "pecan", "peck", "pecos", "pedal", "pedro", + "pee", "peed", "peek", "peel", "peep", "peepy", "peer", + "peg", "peggy", "pelt", "pen", "penal", "pence", "pencil", + "pend", "penh", "penn", "penna", "penny", "pent", "peony", + "pep", "peppy", "pepsi", "per", "perch", "percy", "perez", + "peril", "perk", "perky", "perle", "perry", "persia", "pert", + "perth", "peru", "peruse", "pest", "peste", "pet", "petal", + "pete", "peter", "petit", "petri", "petty", "pew", "pewee", + "pf", "pg", "ph", "ph.d", "phage", "phase", "phd", + "phenol", "phi", "phil", "phlox", "phon", "phone", "phony", + "photo", "phyla", "physic", "pi", "piano", "pica", "pick", + "pickup", "picky", "pie", "piece", "pier", "pierce", "piety", + "pig", "piggy", "pike", "pile", "pill", "pilot", "pimp", + "pin", "pinch", "pine", "ping", "pinion", "pink", "pint", + "pinto", "pion", "piotr", "pious", "pip", "pipe", "piper", + "pique", "pit", "pitch", "pith", "pithy", "pitney", "pitt", + "pity", "pius", "pivot", "pixel", "pixy", "pizza", "pj", + "pk", "pl", "place", "plague", "plaid", "plain", "plan", + "plane", "plank", "plant", "plasm", "plat", "plate", "plato", + "play", "playa", "plaza", "plea", "plead", "pleat", "pledge", + "pliny", "plod", "plop", "plot", "plow", "pluck", "plug", + "plum", "plumb", "plume", "plump", "plunk", "plus", "plush", + "plushy", "pluto", "ply", "pm", "pn", "po", "poach", + "pobox", "pod", "podge", "podia", "poe", "poem", "poesy", + "poet", "poetry", "pogo", "poi", "point", "poise", "poke", + "pol", "polar", "pole", "police", "polio", "polis", "polk", + "polka", "poll", "polo", "pomona", "pomp", "ponce", "pond", + "pong", "pont", "pony", "pooch", "pooh", "pool", "poole", + "poop", "poor", "pop", "pope", "poppy", "porch", "pore", + "pork", "porous", "port", "porte", "portia", "porto", "pose", + "posey", "posh", "posit", "posse", "post", "posy", "pot", + "potts", "pouch", "pound", "pour", "pout", "pow", "powder", + "power", "pp", "ppm", "ppp", "pppp", "pq", "pqr", + "pr", "prado", "pram", "prank", "pratt", "pray", "preen", + "prefix", "prep", "press", "prexy", "prey", "priam", "price", + "prick", "pride", "prig", "prim", "prima", "prime", "primp", + "prince", "print", "prior", "prism", "prissy", "privy", "prize", + "pro", "probe", "prod", "prof", "prom", "prone", "prong", + "proof", "prop", "propyl", "prose", "proud", "prove", "prow", + "prowl", "proxy", "prune", "pry", "ps", "psalm", "psi", + "psych", "pt", "pta", "pu", "pub", "puck", "puddly", + "puerto", "puff", "puffy", "pug", "pugh", "puke", "pull", + "pulp", "pulse", "puma", "pump", "pun", "punch", "punic", + "punish", "punk", "punky", "punt", "puny", "pup", "pupal", + "pupil", "puppy", "pure", "purge", "purl", "purr", "purse", + "pus", "pusan", "pusey", "push", "pussy", "put", "putt", + "putty", "pv", "pvc", "pw", "px", "py", "pygmy", + "pyle", "pyre", "pyrex", "pyrite", "pz", "q", "q's", + "qa", "qatar", "qb", "qc", "qd", "qe", "qed", + "qf", "qg", "qh", "qi", "qj", "qk", "ql", + "qm", "qn", "qo", "qp", "qq", "qqq", "qqqq", + "qr", "qrs", "qs", "qt", "qu", "qua", "quack", + "quad", "quaff", "quail", "quake", "qualm", "quark", "quarry", + "quart", "quash", "quasi", "quay", "queasy", "queen", "queer", + "quell", "query", "quest", "queue", "quick", "quid", "quiet", + "quill", "quilt", "quinn", "quint", "quip", "quirk", "quirt", + "quit", "quite", "quito", "quiz", "quo", "quod", "quota", + "quote", "qv", "qw", "qx", "qy", "qz", "r", + "r&d", "r's", "ra", "rabat", "rabbi", "rabbit", "rabid", + "rabin", "race", "rack", "racy", "radar", "radii", "radio", + "radium", "radix", "radon", "rae", "rafael", "raft", "rag", + "rage", "raid", "rail", "rain", "rainy", "raise", "raj", + "rajah", "rake", "rally", "ralph", "ram", "raman", "ramo", + "ramp", "ramsey", "ran", "ranch", "rand", "randy", "rang", + "range", "rangy", "rank", "rant", "raoul", "rap", "rape", + "rapid", "rapt", "rare", "rasa", "rascal", "rash", "rasp", + "rat", "rata", "rate", "rater", "ratio", "rattle", "raul", + "rave", "ravel", "raven", "raw", "ray", "raze", "razor", + "rb", "rc", "rca", "rd", "re", "reach", "read", + "ready", "reagan", "real", "realm", "ream", "reap", "rear", + "reave", "reb", "rebel", "rebut", "recipe", "reck", "recur", + "red", "redeem", "reduce", "reed", "reedy", "reef", "reek", + "reel", "reese", "reeve", "refer", "regal", "regina", "regis", + "reich", "reid", "reign", "rein", "relax", "relay", "relic", + "reman", "remedy", "remit", "remus", "rena", "renal", "rend", + "rene", "renown", "rent", "rep", "repel", "repent", "resin", + "resort", "rest", "ret", "retch", "return", "reub", "rev", + "reveal", "revel", "rever", "revet", "revved", "rex", "rf", + "rg", "rh", "rhea", "rheum", "rhine", "rhino", "rho", + "rhoda", "rhode", "rhyme", "ri", "rib", "rica", "rice", + "rich", "rick", "rico", "rid", "ride", "ridge", "rifle", + "rift", "rig", "riga", "rigel", "riggs", "right", "rigid", + "riley", "rill", "rilly", "rim", "rime", "rimy", "ring", + "rink", "rinse", "rio", "riot", "rip", "ripe", "ripen", + "ripley", "rise", "risen", "risk", "risky", "rite", "ritz", + "rival", "riven", "river", "rivet", "riyadh", "rj", "rk", + "rl", "rm", "rn", "ro", "roach", "road", "roam", + "roar", "roast", "rob", "robe", "robin", "robot", "rock", + "rocket", "rocky", "rod", "rode", "rodeo", "roe", "roger", + "rogue", "roil", "role", "roll", "roman", "rome", "romeo", + "romp", "ron", "rondo", "rood", "roof", "rook", "rookie", + "rooky", "room", "roomy", "roost", "root", "rope", "rosa", + "rose", "rosen", "ross", "rosy", "rot", "rotc", "roth", + "rotor", "rouge", "rough", "round", "rouse", "rout", "route", + "rove", "row", "rowdy", "rowe", "roy", "royal", "royce", + "rp", "rpm", "rq", "rr", "rrr", "rrrr", "rs", + "rst", "rsvp", "rt", "ru", "ruanda", "rub", "rube", + "ruben", "rubin", "rubric", "ruby", "ruddy", "rude", "rudy", + "rue", "rufus", "rug", "ruin", "rule", "rum", "rumen", + "rummy", "rump", "rumpus", "run", "rune", "rung", "runge", + "runic", "runt", "runty", "rupee", "rural", "ruse", "rush", + "rusk", "russ", "russo", "rust", "rusty", "rut", "ruth", + "rutty", "rv", "rw", "rx", "ry", "ryan", "ryder", + "rye", "rz", "s", "s's", "sa", "sabine", "sable", + "sabra", "sac", "sachs", "sack", "sad", "saddle", "sadie", + "safari", "safe", "sag", "saga", "sage", "sago", "said", + "sail", "saint", "sake", "sal", "salad", "sale", "salem", + "saline", "salk", "salle", "sally", "salon", "salt", "salty", + "salve", "salvo", "sam", "samba", "same", "sammy", "samoa", + "samuel", "san", "sana", "sand", "sandal", "sandy", "sane", + "sang", "sank", "sans", "santa", "santo", "sao", "sap", + "sappy", "sara", "sarah", "saran", "sari", "sash", "sat", + "satan", "satin", "satyr", "sauce", "saucy", "saud", "saudi", + "saul", "sault", "saute", "save", "savoy", "savvy", "saw", + "sawyer", "sax", "saxon", "say", "sb", "sc", "scab", + "scala", "scald", "scale", "scalp", "scam", "scamp", "scan", + "scant", "scar", "scare", "scarf", "scary", "scat", "scaup", + "scene", "scent", "school", "scion", "scm", "scoff", "scold", + "scoop", "scoot", "scope", "scops", "score", "scoria", "scorn", + "scot", "scott", "scour", "scout", "scowl", "scram", "scrap", + "scrape", "screw", "scrim", "scrub", "scuba", "scud", "scuff", + "scull", "scum", "scurry", "sd", "se", "sea", "seal", + "seam", "seamy", "sean", "sear", "sears", "season", "seat", + "sec", "secant", "sect", "sedan", "seder", "sedge", "see", + "seed", "seedy", "seek", "seem", "seen", "seep", "seethe", + "seize", "self", "sell", "selma", "semi", "sen", "send", + "seneca", "senor", "sense", "sent", "sentry", "seoul", "sepal", + "sepia", "sepoy", "sept", "septa", "sequin", "sera", "serf", + "serge", "serif", "serum", "serve", "servo", "set", "seth", + "seton", "setup", "seven", "sever", "severe", "sew", "sewn", + "sex", "sexy", "sf", "sg", "sh", "shack", "shad", + "shade", "shady", "shafer", "shaft", "shag", "shah", "shake", + "shaken", "shako", "shaky", "shale", "shall", "sham", "shame", + "shank", "shape", "shard", "share", "shari", "shark", "sharp", + "shave", "shaw", "shawl", "shay", "she", "she'd", "shea", + "sheaf", "shear", "sheath", "shed", "sheen", "sheep", "sheer", + "sheet", "sheik", "shelf", "shell", "shied", "shift", "shill", + "shim", "shin", "shine", "shinto", "shiny", "ship", "shire", + "shirk", "shirt", "shish", "shiv", "shoal", "shock", "shod", + "shoe", "shoji", "shone", "shoo", "shook", "shoot", "shop", + "shore", "short", "shot", "shout", "shove", "show", "shown", + "showy", "shrank", "shred", "shrew", "shrike", "shrub", "shrug", + "shu", "shuck", "shun", "shunt", "shut", "shy", "si", + "sial", "siam", "sian", "sib", "sibley", "sibyl", "sic", + "sick", "side", "sidle", "siege", "siena", "sieve", "sift", + "sigh", "sight", "sigma", "sign", "signal", "signor", "silas", + "silk", "silky", "sill", "silly", "silo", "silt", "silty", + "sima", "simon", "simons", "sims", "sin", "sinai", "since", + "sine", "sinew", "sing", "singe", "sinh", "sink", "sinus", + "sioux", "sip", "sir", "sire", "siren", "sis", "sisal", + "sit", "site", "situ", "situs", "siva", "six", "sixgun", + "sixth", "sixty", "size", "sj", "sk", "skat", "skate", + "skeet", "skew", "ski", "skid", "skied", "skiff", "skill", + "skim", "skimp", "skimpy", "skin", "skip", "skirt", "skit", + "skulk", "skull", "skunk", "sky", "skye", "sl", "slab", + "slack", "slag", "slain", "slake", "slam", "slang", "slant", + "slap", "slash", "slat", "slate", "slater", "slav", "slave", + "slay", "sled", "sleek", "sleep", "sleet", "slept", "slew", + "slice", "slick", "slid", "slide", "slim", "slime", "slimy", + "sling", "slip", "slit", "sliver", "sloan", "slob", "sloe", + "slog", "sloop", "slop", "slope", "slosh", "slot", "sloth", + "slow", "slug", "sluice", "slum", "slump", "slung", "slur", + "slurp", "sly", "sm", "smack", "small", "smart", "smash", + "smear", "smell", "smelt", "smile", "smirk", "smith", "smithy", + "smog", "smoke", "smoky", "smug", "smut", "sn", "snack", + "snafu", "snag", "snail", "snake", "snap", "snare", "snark", + "snarl", "snatch", "sneak", "sneer", "snell", "snick", "sniff", + "snip", "snipe", "snob", "snook", "snoop", "snore", "snort", + "snout", "snow", "snowy", "snub", "snuff", "snug", "so", + "soak", "soap", "soapy", "soar", "sob", "sober", "social", + "sock", "sod", "soda", "sofa", "sofia", "soft", "soften", + "soggy", "soil", "sol", "solar", "sold", "sole", "solemn", + "solid", "solo", "solon", "solve", "soma", "somal", "some", + "son", "sonar", "song", "sonic", "sonny", "sonora", "sony", + "soon", "soot", "sooth", "sop", "sora", "sorb", "sore", + "sorry", "sort", "sos", "sou", "sough", "soul", "sound", + "soup", "sour", "source", "sousa", "south", "sow", "sown", + "soy", "soya", "sp", "spa", "space", "spade", "spain", + "span", "spar", "spare", "sparge", "spark", "spasm", "spat", + "spate", "spawn", "spay", "speak", "spear", "spec", "speck", + "sped", "speed", "spell", "spend", "spent", "sperm", "sperry", + "spew", "spica", "spice", "spicy", "spike", "spiky", "spill", + "spilt", "spin", "spine", "spiny", "spire", "spiro", "spit", + "spite", "spitz", "splat", "splay", "spline", "split", "spoil", + "spoke", "spoof", "spook", "spooky", "spool", "spoon", "spore", + "sport", "spot", "spout", "sprain", "spray", "spree", "sprig", + "spruce", "sprue", "spud", "spume", "spun", "spunk", "spur", + "spurn", "spurt", "spy", "sq", "squad", "squat", "squaw", + "squibb", "squid", "squint", "sr", "sri", "ss", "sss", + "ssss", "sst", "st", "st.", "stab", "stack", "stacy", + "staff", "stag", "stage", "stagy", "stahl", "staid", "stain", + "stair", "stake", "stale", "stalk", "stall", "stamp", "stan", + "stance", "stand", "stank", "staph", "star", "stare", "stark", + "starr", "start", "stash", "state", "statue", "stave", "stay", + "stead", "steak", "steal", "steam", "steed", "steel", "steele", + "steen", "steep", "steer", "stein", "stella", "stem", "step", + "stern", "steve", "stew", "stick", "stiff", "stile", "still", + "stilt", "sting", "stingy", "stink", "stint", "stir", "stock", + "stoic", "stoke", "stole", "stomp", "stone", "stony", "stood", + "stool", "stoop", "stop", "store", "storey", "stork", "storm", + "story", "stout", "stove", "stow", "strafe", "strap", "straw", + "stray", "strewn", "strip", "stroll", "strom", "strop", "strum", + "strut", "stu", "stuart", "stub", "stuck", "stud", "study", + "stuff", "stuffy", "stump", "stun", "stung", "stunk", "stunt", + "sturm", "style", "styli", "styx", "su", "suave", "sub", + "subtly", "such", "suck", "sud", "sudan", "suds", "sue", + "suey", "suez", "sugar", "suit", "suite", "sulfa", "sulk", + "sulky", "sully", "sultry", "sum", "sumac", "summon", "sun", + "sung", "sunk", "sunny", "sunset", "suny", "sup", "super", + "supra", "sure", "surf", "surge", "sus", "susan", "sushi", + "susie", "sutton", "sv", "sw", "swab", "swag", "swain", + "swam", "swami", "swamp", "swampy", "swan", "swank", "swap", + "swarm", "swart", "swat", "swath", "sway", "swear", "sweat", + "sweaty", "swede", "sweep", "sweet", "swell", "swelt", "swept", + "swift", "swig", "swim", "swine", "swing", "swipe", "swirl", + "swish", "swiss", "swoop", "sword", "swore", "sworn", "swum", + "swung", "sx", "sy", "sybil", "sykes", "sylow", "sylvan", + "synge", "synod", "syria", "syrup", "sz", "t", "t's", + "ta", "tab", "table", "taboo", "tabu", "tabula", "tacit", + "tack", "tacky", "tacoma", "tact", "tad", "taffy", "taft", + "tag", "tahoe", "tail", "taint", "take", "taken", "talc", + "tale", "talk", "talky", "tall", "tallow", "tally", "talon", + "talus", "tam", "tame", "tamp", "tampa", "tan", "tang", + "tango", "tangy", "tanh", "tank", "tansy", "tanya", "tao", + "taos", "tap", "tapa", "tape", "taper", "tapir", "tapis", + "tappa", "tar", "tara", "tardy", "tariff", "tarry", "tart", + "task", "tass", "taste", "tasty", "tat", "tate", "tater", + "tattle", "tatty", "tau", "taunt", "taut", "tavern", "tawny", + "tax", "taxi", "tb", "tc", "td", "te", "tea", + "teach", "teal", "team", "tear", "tease", "teat", "tech", + "tecum", "ted", "teddy", "tee", "teem", "teen", "teensy", + "teet", "teeth", "telex", "tell", "tempo", "tempt", "ten", + "tend", "tenet", "tenney", "tenon", "tenor", "tense", "tensor", + "tent", "tenth", "tepee", "tepid", "term", "tern", "terra", + "terre", "terry", "terse", "tess", "test", "testy", "tete", + "texan", "texas", "text", "tf", "tg", "th", "thai", + "than", "thank", "that", "thaw", "the", "thea", "thee", + "theft", "their", "them", "theme", "then", "there", "these", + "theta", "they", "thick", "thief", "thigh", "thin", "thine", + "thing", "think", "third", "this", "thong", "thor", "thorn", + "thorny", "those", "thou", "thread", "three", "threw", "throb", + "throes", "throw", "thrum", "thud", "thug", "thule", "thumb", + "thump", "thus", "thy", "thyme", "ti", "tiber", "tibet", + "tibia", "tic", "tick", "ticket", "tid", "tidal", "tidbit", + "tide", "tidy", "tie", "tied", "tier", "tift", "tiger", + "tight", "til", "tilde", "tile", "till", "tilt", "tilth", + "tim", "time", "timex", "timid", "timon", "tin", "tina", + "tine", "tinge", "tint", "tiny", "tioga", "tip", "tipoff", + "tippy", "tipsy", "tire", "tit", "titan", "tithe", "title", + "titus", "tj", "tk", "tl", "tm", "tn", "tnt", + "to", "toad", "toady", "toast", "toby", "today", "todd", + "toe", "tofu", "tog", "togo", "togs", "toil", "toilet", + "token", "tokyo", "told", "toll", "tom", "tomb", "tome", + "tommy", "ton", "tonal", "tone", "tong", "toni", "tonic", + "tonk", "tonsil", "tony", "too", "took", "tool", "toot", + "tooth", "top", "topaz", "topic", "topple", "topsy", "tor", + "torah", "torch", "tore", "tori", "torn", "torr", "torso", + "tort", "torus", "tory", "toss", "tot", "total", "tote", + "totem", "touch", "tough", "tour", "tout", "tow", "towel", + "tower", "town", "toxic", "toxin", "toy", "tp", "tq", + "tr", "trace", "track", "tract", "tracy", "trade", "trag", + "trail", "train", "trait", "tram", "tramp", "trap", "trash", + "trawl", "tray", "tread", "treat", "treble", "tree", "trek", + "trench", "trend", "tress", "triad", "trial", "tribe", "trick", + "tried", "trig", "trill", "trim", "trio", "trip", "tripe", + "trite", "triton", "trod", "troll", "troop", "trot", "trout", + "troy", "truce", "truck", "trudge", "trudy", "true", "truly", + "trump", "trunk", "truss", "trust", "truth", "trw", "try", + "ts", "tsar", "tt", "ttl", "ttt", "tttt", "tty", + "tu", "tub", "tuba", "tube", "tuck", "tudor", "tuff", + "tuft", "tug", "tulane", "tulip", "tulle", "tulsa", "tum", + "tun", "tuna", "tune", "tung", "tunic", "tunis", "tunnel", + "tuple", "turf", "turin", "turk", "turn", "turvy", "tusk", + "tussle", "tutor", "tutu", "tuv", "tv", "tva", "tw", + "twa", "twain", "tweak", "tweed", "twice", "twig", "twill", + "twin", "twine", "twirl", "twist", "twisty", "twit", "two", + "twx", "tx", "ty", "tyburn", "tying", "tyler", "type", + "typic", "typo", "tyson", "tz", "u", "u's", "ua", + "ub", "uc", "ucla", "ud", "ue", "uf", "ug", + "ugh", "ugly", "uh", "ui", "uj", "uk", "ul", + "ulan", "ulcer", "ultra", "um", "umber", "umbra", "umpire", + "un", "unary", "uncle", "under", "unify", "union", "unit", + "unite", "unity", "unix", "until", "uo", "up", "upend", + "uphold", "upon", "upper", "uproar", "upset", "uptake", "upton", + "uq", "ur", "urban", "urbane", "urea", "urge", "uri", + "urine", "uris", "urn", "ursa", "us", "usa", "usaf", + "usage", "usc", "usda", "use", "useful", "usgs", "usher", + "usia", "usn", "usps", "ussr", "usual", "usurp", "usury", + "ut", "utah", "utica", "utile", "utmost", "utter", "uu", + "uuu", "uuuu", "uv", "uvw", "uw", "ux", "uy", + "uz", "v", "v's", "va", "vacua", "vacuo", "vade", + "vaduz", "vague", "vail", "vain", "vale", "valet", "valeur", + "valid", "value", "valve", "vamp", "van", "vance", "vane", + "vary", "vase", "vast", "vat", "vault", "vb", "vc", + "vd", "ve", "veal", "veda", "vee", "veer", "veery", + "vega", "veil", "vein", "velar", "veldt", "vella", "vellum", + "venal", "vend", "venial", "venom", "vent", "venus", "vera", + "verb", "verde", "verdi", "verge", "verity", "verna", "verne", + "versa", "verse", "verve", "very", "vessel", "vest", "vet", + "vetch", "veto", "vex", "vf", "vg", "vh", "vi", + "via", "vial", "vicar", "vice", "vichy", "vicky", "vida", + "video", "vie", "viet", "view", "vigil", "vii", "viii", + "vile", "villa", "vine", "vinyl", "viola", "violet", "virgil", + "virgo", "virus", "vis", "visa", "vise", "visit", "visor", + "vista", "vita", "vitae", "vital", "vito", "vitro", "viva", + "vivian", "vivid", "vivo", "vixen", "viz", "vj", "vk", + "vl", "vm", "vn", "vo", "vocal", "vogel", "vogue", + "voice", "void", "volt", "volta", "volvo", "vomit", "von", + "voss", "vote", "vouch", "vow", "vowel", "vp", "vq", + "vr", "vs", "vt", "vu", "vulcan", "vv", "vvv", + "vvvv", "vw", "vx", "vy", "vying", "vz", "w", + "w's", "wa", "waals", "wac", "wack", "wacke", "wacky", + "waco", "wad", "wade", "wadi", "wafer", "wag", "wage", + "waggle", "wah", "wahl", "wail", "waist", "wait", "waite", + "waive", "wake", "waken", "waldo", "wale", "walk", "walkie", + "wall", "walls", "wally", "walsh", "walt", "walton", "waltz", + "wan", "wand", "wane", "wang", "want", "war", "ward", + "ware", "warm", "warmth", "warn", "warp", "warren", "wart", + "warty", "wary", "was", "wash", "washy", "wasp", "wast", + "waste", "watch", "water", "watt", "watts", "wave", "wavy", + "wax", "waxen", "waxy", "way", "wayne", "wb", "wc", + "wd", "we", "we'd", "we'll", "we're", "we've", "weak", + "weal", "wealth", "wean", "wear", "weary", "weave", "web", + "webb", "weber", "weco", "wed", "wedge", "wee", "weed", + "weedy", "week", "weeks", "weep", "wehr", "wei", "weigh", + "weir", "weird", "weiss", "welch", "weld", "well", "wells", + "welsh", "welt", "wendy", "went", "wept", "were", "wert", + "west", "wet", "wf", "wg", "wh", "whack", "whale", + "wham", "wharf", "what", "wheat", "whee", "wheel", "whelk", + "whelm", "whelp", "when", "where", "whet", "which", "whiff", + "whig", "while", "whim", "whine", "whinny", "whip", "whir", + "whirl", "whisk", "whit", "white", "whiz", "who", "who'd", + "whoa", "whole", "whom", "whoop", "whoosh", "whop", "whose", + "whup", "why", "wi", "wick", "wide", "widen", "widow", + "width", "wield", "wier", "wife", "wig", "wild", "wile", + "wiley", "wilkes", "will", "willa", "wills", "wilma", "wilt", + "wily", "win", "wince", "winch", "wind", "windy", "wine", + "wing", "wink", "winnie", "wino", "winter", "winy", "wipe", + "wire", "wiry", "wise", "wish", "wishy", "wisp", "wispy", + "wit", "witch", "with", "withe", "withy", "witt", "witty", + "wive", "wj", "wk", "wl", "wm", "wn", "wo", + "woe", "wok", "woke", "wold", "wolf", "wolfe", "wolff", + "wolve", "woman", "womb", "women", "won", "won't", "wonder", + "wong", "wont", "woo", "wood", "woods", "woody", "wool", + "woozy", "word", "wordy", "wore", "work", "world", "worm", + "wormy", "worn", "worry", "worse", "worst", "worth", "wotan", + "would", "wound", "wove", "woven", "wow", "wp", "wq", + "wr", "wrack", "wrap", "wrath", "wreak", "wreck", "wrest", + "wring", "wrist", "writ", "write", "writhe", "wrong", "wrote", + "wry", "ws", "wt", "wu", "wuhan", "wv", "ww", + "www", "wwww", "wx", "wxy", "wy", "wyatt", "wyeth", + "wylie", "wyman", "wyner", "wynn", "wz", "x", "x's", + "xa", "xb", "xc", "xd", "xe", "xenon", "xerox", + "xf", "xg", "xh", "xi", "xj", "xk", "xl", + "xm", "xn", "xo", "xp", "xq", "xr", "xs", + "xt", "xu", "xv", "xw", "xx", "xxx", "xxxx", + "xy", "xylem", "xyz", "xz", "y", "y's", "ya", + "yacht", "yah", "yak", "yale", "yalta", "yam", "yamaha", + "yang", "yank", "yap", "yaqui", "yard", "yarn", "yates", + "yaw", "yawl", "yawn", "yb", "yc", "yd", "ye", + "yea", "yeah", "year", "yearn", "yeast", "yeasty", "yeats", + "yell", "yelp", "yemen", "yen", "yet", "yf", "yg", + "yh", "yi", "yield", "yin", "yip", "yj", "yk", + "yl", "ym", "ymca", "yn", "yo", "yodel", "yoder", + "yoga", "yogi", "yoke", "yokel", "yolk", "yon", "yond", + "yore", "york", "yost", "you", "you'd", "young", "your", + "youth", "yow", "yp", "yq", "yr", "ys", "yt", + "yu", "yucca", "yuck", "yuh", "yuki", "yukon", "yule", + "yv", "yves", "yw", "ywca", "yx", "yy", "yyy", + "yyyy", "yz", "z", "z's", "za", "zag", "zaire", + "zan", "zap", "zazen", "zb", "zc", "zd", "ze", + "zeal", "zealot", "zebra", "zeiss", "zen", "zero", "zest", + "zesty", "zeta", "zeus", "zf", "zg", "zh", "zi", + "zig", "zilch", "zinc", "zing", "zion", "zip", "zj", + "zk", "zl", "zloty", "zm", "zn", "zo", "zoe", + "zomba", "zone", "zoo", "zoom", "zorn", "zp", "zq", + "zr", "zs", "zt", "zu", "zurich", "zv", "zw", + "zx", "zy", "zz", "zzz", "zzzz", "0", "1", + "2", "3", "4", "5", "6", "7", "8", + "9", "10", "11", "12", "13", "14", "15", + "16", "17", "18", "19", "20", "21", "22", + "23", "24", "25", "26", "27", "28", "29", + "30", "31", "32", "33", "34", "35", "36", + "37", "38", "39", "40", "41", "42", "43", + "44", "45", "46", "47", "48", "49", "50", + "51", "52", "53", "54", "55", "56", "57", + "58", "59", "60", "61", "62", "63", "64", + "65", "66", "67", "68", "69", "70", "71", + "72", "73", "74", "75", "76", "77", "78", + "79", "80", "81", "82", "83", "84", "85", + "86", "87", "88", "89", "90", "91", "92", + "93", "94", "95", "96", "97", "98", "99", + "100", "101", "111", "123", "200", "222", "234", + "300", "333", "345", "400", "444", "456", "500", + "555", "567", "600", "666", "678", "700", "777", + "789", "800", "888", "900", "999", "1000", "1111", + "1234", "1492", "1500", "1600", "1700", "1776", "1800", + "1812", "1900", "1910", "1920", "1925", "1930", "1935", + "1940", "1945", "1950", "1955", "1960", "1965", "1970", + "1975", "1980", "1985", "1990", "1991", "1992", "1993", + "1994", "1995", "1996", "1997", "2000", "2001", "2020", + "2222", "2345", "2468", "3000", "3333", "3456", "4000", + "4321", "4444", "4567", "5000", "5555", "5678", "6000", + "6666", "6789", "7000", "7777", "8000", "8888", "9000", + "9876", "9999", "100th", "101st", "10th", "11th", "12th", + "13th", "14th", "15th", "16th", "17th", "18th", "19th", + "1st", "20th", "21st", "22nd", "23rd", "24th", "25th", + "26th", "27th", "28th", "29th", "2nd", "30th", "31st", + "32nd", "33rd", "34th", "35th", "36th", "37th", "38th", + "39th", "3rd", "40th", "41st", "42nd", "43rd", "44th", + "45th", "46th", "47th", "48th", "49th", "4th", "50th", + "51st", "52nd", "53rd", "54th", "55th", "56th", "57th", + "58th", "59th", "5th", "60th", "61st", "62nd", "63rd", + "65th", "66th", "67th", "68th", "69th", "6th", "70th", + "71st", "72nd", "73rd", "74th", "75th", "76th", "77th", + "78th", "79th", "7th", "80th", "81st", "82nd", "83rd", + "84th", "85th", "86th", "87th", "88th", "89th", "8th", + "90th", "91st", "92nd", "93rd", "94th", "95th", "96th", + "97th", "98th", "99th", "9th", "!", "!!", "\"", + "#", "##", "$", "$$", "%", "\%%", "&", + "(", "()", ")", "*", "**", "+", "-", + ":", ";", "=", "?", "??", "@", +};