#include <linux/types.h>
#include <sys/types.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

typedef __u32 uint32_t;
typedef __s32 ngx_int_t;
typedef __u32 ngx_uint_t;

static uint32_t  usual[] = {
    0xffffdbfe, /* 1111 1111 1111 1111  1101 1011 1111 1110 */

                /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
    0x7fff37d6, /* 0111 1111 1111 1111  0011 0111 1101 0110 */

                /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
    0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */

                /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
    0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */

    0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
    0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
    0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
    0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
};

typedef unsigned char u_char;

typedef struct {
    u_char *data;
    size_t len;
} ngx_str_t;

typedef struct {
    void *pool;
    void *connection;
} ngx_http_request_t;

#define ngx_inline			inline
#define ngx_path_separator(x)		(x == '/')
#define ngx_pnalloc(pool, size)		malloc((size) + 1)
#define ngx_memcpy(dst, src, n)		memcpy(dst, src, n)
#define ngx_log_error(a, b, c, d, e)	do {} while (0)

#define NGX_ERROR		-1
#define NGX_OK			0
#define NGX_HTTP_LOG_UNSAFE	0

static ngx_inline ngx_int_t
ngx_http_parse_test_doubledot(const u_char *ptr, const u_char *begin);

ngx_int_t
ngx_http_parse_unsafe_uri(ngx_http_request_t *r, ngx_str_t *uri,
    ngx_str_t *args, ngx_uint_t *flags);

void test(const char *str, const char *uri, const char *args);

int main(void)
{
	test("", NULL, NULL);
	test("?", NULL, NULL);
	test("?ccc", NULL, NULL);
	test("%3fccc", "?ccc", NULL);

	test("a", "a", NULL);
	test("aa", "aa", NULL);
	test("aaa", "aaa", NULL);
	test("/aaa/bbb", "/aaa/bbb", NULL);
	test("/aaa%2fbbb", "/aaa/bbb", NULL);

	test("/aaa/bbb?ccc", "/aaa/bbb", "ccc");
	test("/aaa%2fbbb?ccc", "/aaa/bbb", "ccc");
	test("/aaa%2fbbb?c%63c", "/aaa/bbb", "c%63c");

	test("/aaa/bbb%", "/aaa/bbb%", NULL);
	test("/aaa/bbb%Z", "/aaa/bbb%Z", NULL);
	test("/aaa/bbb%2", "/aaa/bbb%2", NULL);
	test("/aaa/bbb%?ccc", "/aaa/bbb%", "ccc");
	test("/aaa/bbb%Z?ccc", "/aaa/bbb%Z", "ccc");
	test("/aaa/bbb%2?ccc", "/aaa/bbb%2", "ccc");

	test("%2%%f%", "%2%%f%", NULL);
	test("%2%%f%2", "%2%%f%2", NULL);
	test("%2%%f%2e", "%2%%f.", NULL);

	test("../aaa", NULL, NULL);
	test("%2e./aaa", NULL, NULL);
	test(".%2e/aaa", NULL, NULL);
	test("%2e%2e/aaa", NULL, NULL);
	test("%2e%2e%2faaa", NULL, NULL);
	test("%2e%2e%2faaa?ccc", NULL, NULL);

	test("/aaa/../bbb", NULL, NULL);
	test("/aaa/%2e./bbb", NULL, NULL);
	test("/aaa/.%2e/bbb", NULL, NULL);
	test("/aaa/%2e%2e/bbb", NULL, NULL);
	test("/aaa/%2e%2e%2fbbb", NULL, NULL);
	test("/aaa%2f%2e%2e/bbb", NULL, NULL);
	test("/aaa%2f%2e%2e%2fbbb", NULL, NULL);
	test("/aaa%2f..%2fbbb", NULL, NULL);
	test("/aaa%2f.%2fbbb%3f?ccc", "/aaa/./bbb?", "ccc");
	test("/aaa%%2f.%2fbbb%3f?ccc", "/aaa%/./bbb?", "ccc");
	test("/aaa%5%2f.%2fbbb%3f?ccc", "/aaa%5/./bbb?", "ccc");

	test("%2e%2e", NULL, NULL);
	test("..", NULL, NULL);
	test("..?ccc", NULL, NULL);
	test("..?ccc", NULL, NULL);
	test("../", NULL, NULL);
	test("../?ccc", NULL, NULL);
	test("./..", NULL, NULL);
	test("./..?ccc", NULL, NULL);
	test("./%2e.", NULL, NULL);
	test("./%2e.?ccc", NULL, NULL);
	test("/%2e.", NULL, NULL);
	test("/%2e.?ccc", NULL, NULL);

	return 0;
}

void test(const char *str, const char *uri, const char *args)
{
	ngx_int_t n_res;
	ngx_str_t n_uri;
	ngx_str_t n_args;
	ngx_uint_t n_flags;

	n_args.len = 0;
	n_args.data = NULL;

	n_uri.len = strlen(str);
	n_uri.data = alloca(1024);
	memset(n_uri.data, 'X', 1024);
	memcpy(n_uri.data, str, n_uri.len);

	n_flags = 0;
	n_res = ngx_http_parse_unsafe_uri(NULL, &n_uri, &n_args, &n_flags);

	if (n_res != NGX_OK) {
		if (uri == NULL) {
			printf("test: '%s' OK\n", str);
		} else {
			printf("test: '%s' FAIL:NGX_ERROR\n", str);
		}
		return;
	}

	n_uri.data[n_uri.len] = '\0';

	if (uri == NULL) {
		printf("test: '%s' FAIL:extra uri: '%s'\n",
		       str, (char *)n_uri.data);
		return;
	}

	if (strcmp(uri, (char *)n_uri.data)) {
		printf("test: '%s' FAIL:uri: '%s'\n",
		       str, (char *)n_uri.data);
		return;
	}

	if (!args && !n_args.data) {
		printf("test: '%s' OK\n", str);
		return;
	}

	if (args && !n_args.data) {
		printf("test: '%s' FAIL:args missing\n", str);
		return;
	}

	n_args.data[n_args.len] = '\0';

	if (n_args.data && !args) {
		printf("test: '%s' FAIL:extra args: '%s'\n",
		       str, (char *)n_args.data);
		return;
	}

	if (strcmp(args, (char *)n_args.data)) {
		printf("test: '%s' FAIL:args: '%s'\n",
		       str, (char *)n_args.data);
		return;
	}

	printf("test: '%s' OK\n", str);
}

/*
 * ngx_http_parse_unsafe_uri() as is
 */

static ngx_inline ngx_int_t
ngx_http_parse_test_doubledot(const u_char *p, const u_char *begin)
{
    /* assume *p is the path separator or
       p points to the next byte after the end */

    if (p - 2 > begin &&
        *(p - 1) == '.' && *(p - 2) == '.' &&
        ngx_path_separator(*(p - 3))) {
        return 1;
    }

    if (p - 2 == begin &&
        begin[0] == '.' && begin[1] == '.') {
        return 1;
    }

    return 0;
}


ngx_int_t
ngx_http_parse_unsafe_uri(ngx_http_request_t *r, ngx_str_t *uri,
    ngx_str_t *args, ngx_uint_t *flags)
{
    u_char   *src, *dst, *newuri, ch, c, decoded;
    ngx_int_t unescape;
    size_t    len;
    enum {
        sw_usual = 0,
        sw_quoted,
        sw_quoted_second
    } state;

    src = uri->data;
    len = uri->len;
    unescape = 0;

    if (len == 0 || src[0] == '?') {
        goto unsafe;
    }

    for ( /* void */ ; len; len--) {

        ch = *src++;

        if (usual[ch >> 5] & (1 << (ch & 0x1f))) {
            continue;
        }

        if (ch == '%') {
            unescape++;
            continue;
        }

        if (ch == '?') {
            args->len = len - 1;
            args->data = src;

            if (unescape) {
                src--;
                goto unescape;
            }

            /* detect "/.." at the end or whole uri is ".." */
            if (ngx_http_parse_test_doubledot(src - 1, uri->data)) {
                goto unsafe;
            }

            uri->len -= len;

            return NGX_OK;
        }

        if (ch == '\0') {
            goto unsafe;
        }

        /* detect "../" at the beginning or "/../" in the middle */
        if (ngx_path_separator(ch) &&
            ngx_http_parse_test_doubledot(src - 1, uri->data)) {
            goto unsafe;
        }
    }

    /* detect "/.." at the end or whole uri is ".." */
    if (ngx_http_parse_test_doubledot(src, uri->data)) {
        goto unsafe;
    }

    if (!unescape) {
        return NGX_OK;
    }

unescape:

    len = src - uri->data;
    newuri = ngx_pnalloc(r->pool, len);

    if (newuri == NULL) {
        return NGX_ERROR;
    }

    ngx_memcpy(newuri, uri->data, len);

    src = uri->data;
    dst = newuri;
    decoded = 0;
    state = 0;

    for ( /* void */ ; len; len--) {

        ch = *src++;

        switch (state) {

        case sw_usual:
            if (usual[ch >> 5] & (1 << (ch & 0x1f))) {
                *dst++ = ch;
                break;
            }

            if (ch == '%') {
                state = sw_quoted;
                break;
            }

            /* detect "../" at the beginning or "/../" in the middle */
            if (ngx_path_separator(ch) &&
                ngx_http_parse_test_doubledot(dst, newuri)) {
                goto unsafe;
            }

            *dst++ = ch;
            break;

        case sw_quoted:
            if (ch >= '0' && ch <= '9') {
                decoded = (u_char) (ch - '0');
                state = sw_quoted_second;
                break;
            }

            c = (u_char) (ch | 0x20);
            if (c >= 'a' && c <= 'f') {
                decoded = (u_char) (c - 'a' + 10);
                state = sw_quoted_second;
                break;
            }

            if (ch == '%') {
                *dst++ = '%';
                break;
            }

            *dst++ = '%';
            *dst++ = ch;
            state = sw_usual;
            break;

        case sw_quoted_second:

            state = sw_usual;

            if (ch >= '0' && ch <= '9') {
                ch = (u_char) ((decoded << 4) + ch - '0');

                if (ch == '\0') {
                    goto unsafe;
                }

                *dst++ = ch;
                break;
            }

            c = (u_char) (ch | 0x20);
            if (c >= 'a' && c <= 'f') {
                ch = (u_char) ((decoded << 4) + c - 'a' + 10);

                /* detect "../" at the beginning or "/../" in the middle */
                if (ngx_path_separator(ch) &&
                    ngx_http_parse_test_doubledot(dst, newuri)) {
                    goto unsafe;
                }

                *dst++ = ch;
                break;
            }

            if (ch == '%') {
                *dst++ = '%';
                *dst++ = *(src - 2);
                state = sw_quoted;
                break;
            }

            *dst++ = '%';
            *dst++ = *(src - 2);
            *dst++ = ch;
            break;
        }
    }

    switch (state) {
    case sw_usual:
        break;
    case sw_quoted:
        *dst++ = '%';
        break;
    case sw_quoted_second:
        *dst++ = '%';
        *dst++ = *(src - 1);
        break;
    }

    /* detect "/.." at the end or whole uri is ".." */
    if (ngx_http_parse_test_doubledot(dst, newuri)) {
        goto unsafe;
    }

    uri->len = dst - newuri;
    uri->data = newuri;

    return NGX_OK;

unsafe:

    if (*flags & NGX_HTTP_LOG_UNSAFE) {
        ngx_log_error(NGX_LOG_ERR, r->connection->log, 0,
                      "unsafe URI \"%V\" was detected", uri);
    }

    return NGX_ERROR;
}