#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdarg.h>
#include <signal.h>
#include <strings.h>
#include <setjmp.h>
#include <errno.h>

int matchhere(char *, char *);
int matchstar(int, char *, char *);

int
match(char *regexp, char *text)
{
	if (regexp[0] == '^')
		return (matchhere(regexp + 1, text));

	do {
		if (matchhere(regexp, text))
			return (1);
	} while (*text++ != '\0');

	return (0);
}

int
matchhere(char *regexp, char *text)
{
	if (regexp[0] == '\0')
		return (1);

	if (regexp[1] == '*')
		return (matchstar(regexp[0], regexp + 2, text));

	if (regexp[0] == '$' && regexp[1] == '\0')
		return (*text == '\0');

	if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
		return (matchhere(regexp + 1, text + 1));

	return (0);
}

int
matchstar(int c, char *regexp, char *text)
{
	do {
		if (matchhere(regexp, text))
			return (1);
	} while (*text != '\0' && (*text++ == c || c == '.'));

	return (0);
}

static char g_altstack[8192];
static sigjmp_buf g_env;
static char *g_pname;

static void
fatal(const char *fmt, ...)
{
	va_list ap;

	va_start(ap, fmt);

	(void) fprintf(stderr, "%s: ", g_pname);
	(void) vfprintf(stderr, fmt, ap);

	va_end(ap);

	if (fmt[strlen(fmt) - 1] != '\n')
		(void) fprintf(stderr, ": %s\n", strerror(errno));

	exit(1);
}

/*ARGSUSED*/
static void
busted(int sig)
{
	siglongjmp(g_env, -1);
}

void
main(int argc, char **argv)
{
	char *buf;
	size_t size = 10000000, i;
	size_t lower, upper, guess;
	struct sigaction act;
	stack_t ss;

	g_pname = argv[0];

	(void) sigfillset(&act.sa_mask);
	act.sa_handler = busted;
	act.sa_flags = SA_ONSTACK;

	(void) sigaction(SIGBUS, &act, NULL);
	(void) sigaction(SIGSEGV, &act, NULL);

	ss.ss_flags = 0;
	ss.ss_sp = g_altstack;
	ss.ss_size = sizeof (g_altstack);

	if (sigaltstack(&ss, NULL) != 0)
		fatal("couldn't set alternative signal stack");

	if (argc > 2)
		fatal("expected exactly one argument: a maximum size\n");

	if (argc == 2) {
		errno = 0;

		if ((size = strtoul(argv[1], NULL, 0)) == 0 || errno != 0)
			fatal("invalid size argument '%s'\n", argv[1]);
	}
		
	if ((buf = malloc(size + 1)) == NULL)
		fatal("couldn't allocate buffer of size %d\n", size);

	(void) memset(buf, '*', size);
	buf[size] = '\0';

	upper = size;
	lower = 1;

	if (sigsetjmp(g_env, 1) != 0) {
		while (upper - lower > 1) {
			guess = (upper + lower) / 2;

			if (sigsetjmp(g_env, 1) != 0) {
				upper = guess;
				continue;
			}

			(void) match(&buf[size - guess], "");
			lower = guess;
		}

		(void) printf("%s: found maximum to be %d\n", g_pname, lower);
		exit(0);
	} else {
		(void) match(buf, "");
		fatal("maximum is beyond %d\n", size);
	}
}