/src/h2o/lib/common/string.c

Source (jump to first uncovered line)
/*
 * Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku, Justin Zhu, Fastly, Inc.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "h2o/string_.h"

h2o_iovec_t h2o_strdup(h2o_mem_pool_t *pool, const char *s, size_t slen)
{
    /* We do not need this check to be here, but it needs to be somewhere, see the definition of H2O_SIZE_T_LONGEST_STR */
    H2O_BUILD_ASSERT(sizeof(size_t) <= sizeof(uint64_t));

    h2o_iovec_t ret;

    if (slen == SIZE_MAX)
        slen = strlen(s);

    if (pool != NULL) {
        ret.base = h2o_mem_alloc_pool(pool, char, slen + 1);
    } else {
        ret.base = h2o_mem_alloc(slen + 1);
    }
    h2o_memcpy(ret.base, s, slen);
    ret.base[slen] = '\0';
    ret.len = slen;
    return ret;
}

h2o_iovec_t h2o_strdup_shared(h2o_mem_pool_t *pool, const char *s, size_t slen)
{
    h2o_iovec_t ret;

    if (slen == SIZE_MAX)
        slen = strlen(s);

    ret.base = h2o_mem_alloc_shared(pool, slen + 1, NULL);
    memcpy(ret.base, s, slen);
    ret.base[slen] = '\0';
    ret.len = slen;
    return ret;
}

h2o_iovec_t h2o_strdup_slashed(h2o_mem_pool_t *pool, const char *src, size_t len)
{
    h2o_iovec_t ret;

    ret.len = len != SIZE_MAX ? len : strlen(src);
    ret.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, ret.len + 2) : h2o_mem_alloc(ret.len + 2);
    memcpy(ret.base, src, ret.len);
    if (ret.len != 0 && ret.base[ret.len - 1] != '/')
        ret.base[ret.len++] = '/';
    ret.base[ret.len] = '\0';

    return ret;
}

int h2o__lcstris_core(const char *target, const char *test, size_t test_len)
{
    for (; test_len != 0; --test_len)
        if (h2o_tolower(*target++) != *test++)
            return 0;
    return 1;
}

size_t h2o_strtosize(const char *s, size_t len)
{
    uint64_t v = 0, m = 1;
    const char *p = s + len;

    if (len == 0)
        goto Error;

    while (1) {
        int ch = *--p;
        if (!('0' <= ch && ch <= '9'))
            goto Error;
        v += (ch - '0') * m;
        if (p == s)
            break;
        m *= 10;
        /* do not even try to overflow */
        if (m == 10000000000000000000ULL)
            goto Error;
    }

    if (v >= SIZE_MAX)
        goto Error;
    return v;

Error:
    return SIZE_MAX;
}

size_t h2o_strtosizefwd(char **s, size_t len)
{
    uint64_t v, c;
    char *p = *s, *p_end = *s + len;

    if (len == 0)
        goto Error;

    int ch = *p++;
    if (!('0' <= ch && ch <= '9'))
        goto Error;
    v = ch - '0';
    c = 1;

    while (1) {
        ch = *p;
        if (!('0' <= ch && ch <= '9'))
            break;
        v *= 10;
        v += ch - '0';
        p++;
        c++;
        if (p == p_end)
            break;
        /* similar as above, do not even try to overflow */
        if (c == 20)
            goto Error;
    }

    if (v >= SIZE_MAX)
        goto Error;
    *s = p;
    return v;

Error:
    return SIZE_MAX;
}

static uint32_t decode_base64url_quad(const char *src)
{
    const char *src_end = src + 4;
    uint32_t decoded = 0;

    while (1) {
        if ('A' <= *src && *src <= 'Z') {
            decoded |= *src - 'A';
        } else if ('a' <= *src && *src <= 'z') {
            decoded |= *src - 'a' + 26;
        } else if ('0' <= *src && *src <= '9') {
            decoded |= *src - '0' + 52;
        } else if (*src == '-') {
            decoded |= 62;
        } else if (*src == '_') {
            decoded |= 63;
#if 1 /* curl uses normal base64 */
        } else if (*src == '+') {
            decoded |= 62;
        } else if (*src == '/') {
            decoded |= 63;
#endif
        } else {
            return UINT32_MAX;
        }
        if (++src == src_end)
            break;
        decoded <<= 6;
    }

    return decoded;
}

h2o_iovec_t h2o_decode_base64url(h2o_mem_pool_t *pool, const char *src, size_t len)
{
    h2o_iovec_t decoded;
    uint32_t t;
    uint8_t *dst;
    char remaining_input[4];

    decoded.len = len * 3 / 4;
    decoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, decoded.len + 1) : h2o_mem_alloc(decoded.len + 1);
    dst = (uint8_t *)decoded.base;

    while (len >= 4) {
        if ((t = decode_base64url_quad(src)) == UINT32_MAX)
            goto Error;
        *dst++ = t >> 16;
        *dst++ = t >> 8;
        *dst++ = t;
        src += 4;
        len -= 4;
    }
    switch (len) {
    case 0:
        break;
    case 1:
        goto Error;
    case 2:
        remaining_input[0] = *src++;
        remaining_input[1] = *src++;
        remaining_input[2] = 'A';
        remaining_input[3] = 'A';
        if ((t = decode_base64url_quad(remaining_input)) == UINT32_MAX)
            goto Error;
        *dst++ = t >> 16;
        break;
    case 3:
        remaining_input[0] = *src++;
        remaining_input[1] = *src++;
        remaining_input[2] = *src++;
        remaining_input[3] = 'A';
        if ((t = decode_base64url_quad(remaining_input)) == UINT32_MAX)
            goto Error;
        *dst++ = t >> 16;
        *dst++ = t >> 8;
        break;
    }

    assert((char *)dst - decoded.base == decoded.len);
    decoded.base[decoded.len] = '\0';

    return decoded;

Error:
    if (pool == NULL)
        free(decoded.base);
    return h2o_iovec_init(NULL, 0);
}

size_t h2o_base64_encode(char *_dst, const void *_src, size_t len, int url_encoded)
{
    static const char *MAP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                             "abcdefghijklmnopqrstuvwxyz"
                             "0123456789+/";
    static const char *MAP_URL_ENCODED = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                                         "abcdefghijklmnopqrstuvwxyz"
                                         "0123456789-_";

    char *dst = _dst;
    const uint8_t *src = _src;
    const char *map = url_encoded ? MAP_URL_ENCODED : MAP;
    uint32_t quad;

    for (; len >= 3; src += 3, len -= 3) {
        quad = ((uint32_t)src[0] << 16) | ((uint32_t)src[1] << 8) | src[2];
        *dst++ = map[quad >> 18];
        *dst++ = map[(quad >> 12) & 63];
        *dst++ = map[(quad >> 6) & 63];
        *dst++ = map[quad & 63];
    }
    if (len != 0) {
        quad = (uint32_t)src[0] << 16;
        *dst++ = map[quad >> 18];
        if (len == 2) {
            quad |= (uint32_t)src[1] << 8;
            *dst++ = map[(quad >> 12) & 63];
            *dst++ = map[(quad >> 6) & 63];
            if (!url_encoded)
                *dst++ = '=';
        } else {
            *dst++ = map[(quad >> 12) & 63];
            if (!url_encoded) {
                *dst++ = '=';
                *dst++ = '=';
            }
        }
    }

    *dst = '\0';
    return dst - _dst;
}

static int decode_hex(int ch)
{
    if ('0' <= ch && ch <= '9')
        return ch - '0';
    if ('A' <= ch && ch <= 'F')
        return ch - 'A' + 0xa;
    if ('a' <= ch && ch <= 'f')
        return ch - 'a' + 0xa;
    return -1;
}

int h2o_hex_decode(void *_dst, const char *src, size_t src_len)
{
    unsigned char *dst = _dst;

    if (src_len % 2 != 0)
        return -1;
    for (; src_len != 0; src_len -= 2) {
        int hi, lo;
        if ((hi = decode_hex(*src++)) == -1 || (lo = decode_hex(*src++)) == -1)
            return -1;
        *dst++ = (hi << 4) | lo;
    }
    return 0;
}

void h2o_hex_encode(char *dst, const void *_src, size_t src_len)
{
    const unsigned char *src = _src, *src_end = src + src_len;
    for (; src != src_end; ++src) {
        *dst++ = "0123456789abcdef"[*src >> 4];
        *dst++ = "0123456789abcdef"[*src & 0xf];
    }
    *dst = '\0';
}

h2o_iovec_t h2o_uri_escape(h2o_mem_pool_t *pool, const char *s, size_t l, const char *preserve_chars)
{
    h2o_iovec_t encoded;
    size_t i, capacity = l * 3 + 1;

    encoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, capacity) : h2o_mem_alloc(capacity);
    encoded.len = 0;

    /* RFC 3986:
        path-noscheme = segment-nz-nc *( "/" segment )
        segment-nz-nc = 1*( unreserved / pct-encoded / sub-delims / "@" )
        unreserved  = ALPHA / DIGIT / "-" / "." / "_" / "~"
        sub-delims    = "!" / "$" / "&" / "'" / "(" / ")"
                     / "*" / "+" / "," / ";" / "="
    */
    for (i = 0; i != l; ++i) {
        int ch = s[i];
        if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') || ('0' <= ch && ch <= '9') || ch == '-' || ch == '.' ||
            ch == '_' || ch == '~' || ch == '!' || ch == '$' || ch == '&' || ch == '\'' || ch == '(' || ch == ')' || ch == '*' ||
            ch == '+' || ch == ',' || ch == ';' || ch == '=' ||
            (ch != '\0' && preserve_chars != NULL && strchr(preserve_chars, ch) != NULL)) {
            encoded.base[encoded.len++] = ch;
        } else {
            encoded.base[encoded.len++] = '%';
            encoded.base[encoded.len++] = "0123456789ABCDEF"[(ch >> 4) & 0xf];
            encoded.base[encoded.len++] = "0123456789ABCDEF"[ch & 0xf];
        }
    }
    encoded.base[encoded.len] = '\0';

    return encoded;
}

h2o_iovec_t h2o_get_filext(const char *path, size_t len)
{
    const char *end = path + len, *p = end;

    while (--p != path) {
        if (*p == '.') {
            return h2o_iovec_init(p + 1, end - (p + 1));
        } else if (*p == '/') {
            break;
        }
    }
    return h2o_iovec_init(NULL, 0);
}

static int is_ws(int ch)
{
    return ch == ' ' || ch == '\t' || ch == '\r' || ch == '\n';
}

h2o_iovec_t h2o_str_stripws(const char *s, size_t len)
{
    const char *end = s + len;

    while (s != end) {
        if (!is_ws(*s))
            break;
        ++s;
    }
    while (s != end) {
        if (!is_ws(end[-1]))
            break;
        --end;
    }
    return h2o_iovec_init(s, end - s);
}

size_t h2o_strstr(const char *haysack, size_t haysack_len, const char *needle, size_t needle_len)
{
    /* TODO optimize */
    if (haysack_len >= needle_len) {
        size_t off, max = haysack_len - needle_len + 1;
        if (needle_len == 0)
            return 0;
        for (off = 0; off != max; ++off)
            if (haysack[off] == needle[0] && memcmp(haysack + off + 1, needle + 1, needle_len - 1) == 0)
                return off;
    }
    return SIZE_MAX;
}

/* note: returns a zero-width match as well */
const char *h2o_next_token(h2o_iovec_t *iter, int inner, int outer, size_t *element_len, h2o_iovec_t *value)
{
    const char *cur = iter->base, *end = iter->base + iter->len, *token_start, *token_end;

    /* find start */
    for (;; ++cur) {
        if (cur == end)
            return NULL;
        if (!(*cur == ' ' || *cur == '\t'))
            break;
    }
    token_start = cur;
    token_end = cur;

    /* find last */
    for (;; ++cur) {
        if (cur == end)
            break;
        if (*cur == inner) {
            ++cur;
            break;
        }
        if (*cur == outer) {
            if (token_start == cur) {
                ++cur;
                token_end = cur;
            }
            break;
        }
        if (value != NULL && *cur == '=') {
            ++cur;
            goto FindValue;
        }
        if (!(*cur == ' ' || *cur == '\t'))
            token_end = cur + 1;
    }

    /* found */
    *iter = h2o_iovec_init(cur, end - cur);
    *element_len = token_end - token_start;
    if (value != NULL)
        *value = (h2o_iovec_t){NULL};
    return token_start;

FindValue:
    *iter = h2o_iovec_init(cur, end - cur);
    *element_len = token_end - token_start;
    if ((value->base = (char *)h2o_next_token(iter, inner, outer, &value->len, NULL)) == NULL) {
        *value = (h2o_iovec_t){"", 0};
    } else if (h2o_memis(value->base, value->len, H2O_STRLIT(","))) {
        *value = (h2o_iovec_t){"", 0};
        iter->base -= 1;
        iter->len += 1;
    }
    return token_start;
}

int h2o_contains_token(const char *haysack, size_t haysack_len, const char *needle, size_t needle_len, int separator)
{
    h2o_iovec_t iter = h2o_iovec_init(haysack, haysack_len);
    const char *token = NULL;
    size_t token_len = 0;

    while ((token = h2o_next_token(&iter, separator, ',', &token_len, NULL)) != NULL) {
        if (h2o_lcstris(token, token_len, needle, needle_len)) {
            return 1;
        }
    }
    return 0;
}

h2o_iovec_t h2o_htmlescape(h2o_mem_pool_t *pool, const char *src, size_t len)
{
    const char *s, *end = src + len;
    size_t add_size = 0;

#define ENTITY_MAP()                                                                                                               \
    ENTITY('"', "&quot;");                                                                                                         \
    ENTITY('&', "&amp;");                                                                                                          \
    ENTITY('\'', "&#39;");                                                                                                         \
    ENTITY('<', "&lt;");                                                                                                           \
    ENTITY('>', "&gt;");

    for (s = src; s != end; ++s) {
        if ((unsigned)(unsigned char)*s - '"' <= '>' - '"') {
            switch (*s) {
#define ENTITY(code, quoted)                                                                                                       \
    case code:                                                                                                                     \
        add_size += sizeof(quoted) - 2;                                                                                            \
        break
                ENTITY_MAP()
#undef ENTITY
            }
        }
    }

    /* escape and return the result if necessary */
    if (add_size != 0) {
        /* allocate buffer and fill in the chars that are known not to require escaping */
        h2o_iovec_t escaped = {h2o_mem_alloc_pool(pool, char, len + add_size + 1), 0};
        /* fill-in the rest */
        for (s = src; s != end; ++s) {
            switch (*s) {
#define ENTITY(code, quoted)                                                                                                       \
    case code:                                                                                                                     \
        memcpy(escaped.base + escaped.len, quoted, sizeof(quoted) - 1);                                                            \
        escaped.len += sizeof(quoted) - 1;                                                                                         \
        break
                ENTITY_MAP()
#undef ENTITY
            default:
                escaped.base[escaped.len++] = *s;
                break;
            }
        }
        assert(escaped.len == len + add_size);
        escaped.base[escaped.len] = '\0';

        return escaped;
    }

#undef ENTITY_MAP

    /* no need not escape; return the original */
    return h2o_iovec_init(src, len);
}

h2o_iovec_t h2o_concat_list(h2o_mem_pool_t *pool, h2o_iovec_t *list, size_t count)
{
    h2o_iovec_t ret = {NULL, 0};
    size_t i;

    /* calc the length */
    for (i = 0; i != count; ++i) {
        ret.len += list[i].len;
    }

    /* allocate memory */
    if (pool != NULL)
        ret.base = h2o_mem_alloc_pool(pool, char, ret.len + 1);
    else
        ret.base = h2o_mem_alloc(ret.len + 1);

    /* concatenate */
    ret.len = 0;
    for (i = 0; i != count; ++i) {
        h2o_memcpy(ret.base + ret.len, list[i].base, list[i].len);
        ret.len += list[i].len;
    }
    ret.base[ret.len] = '\0';

    return ret;
}

h2o_iovec_t h2o_join_list(h2o_mem_pool_t *pool, h2o_iovec_t *list, size_t count, h2o_iovec_t delimiter)
{
    if (count == 0) {
        return h2o_iovec_init(NULL, 0);
    }

    size_t joined_len = 0;
    h2o_iovec_t *joined = alloca(sizeof(*joined) * (count * 2 - 1));

    size_t i;
    for (i = 0; i != count; ++i) {
        if (i != 0) {
            joined[joined_len++] = delimiter;
        }
        joined[joined_len++] = list[i];
    }
    return h2o_concat_list(pool, joined, joined_len);
}

void h2o_split(h2o_mem_pool_t *pool, h2o_iovec_vector_t *list, h2o_iovec_t str, const char needle)
{
    const char *p = str.base, *end = str.base + str.len, *found;

    while (p < end && (found = memchr(p, needle, end - p)) != NULL) {
        h2o_vector_reserve(pool, list, list->size + 1);
        list->entries[list->size++] = h2o_strdup(pool, p, found - p);
        p = found + 1;
    }
    h2o_vector_reserve(pool, list, list->size + 1);
    list->entries[list->size++] = h2o_strdup(pool, p, end - p);
}

int h2o_str_at_position(char *buf, const char *src, size_t src_len, int lineno, int column)
{
    const char *src_end = src + src_len;
    int i;

    /* find the line */
    if (lineno <= 0 || column <= 0)
        return -1;
    for (--lineno; lineno != 0; --lineno) {
        do {
            if (src == src_end)
                return -1;
        } while (*src++ != '\n');
    }

    /* adjust the starting column */
    while (column > 40) {
        if (src != src_end)
            ++src;
        --column;
    }

    /* emit */
    for (i = 1; i <= 76; ++i) {
        if (src == src_end || *src == '\n')
            break;
        *buf++ = *src++;
    }
    if (i < column)
        column = i;
    *buf++ = '\n';
    for (i = 1; i < column; ++i)
        *buf++ = ' ';
    *buf++ = '^';
    *buf++ = '\n';
    *buf = '\0';
    return 0;
}

h2o_iovec_t h2o_encode_sf_string(h2o_mem_pool_t *pool, const char *s, size_t slen)
{
    if (slen == SIZE_MAX)
        slen = strlen(s);

    /* https://tools.ietf.org/html/rfc8941#section-3.3.3 */
    size_t to_escape = 0;
    for (size_t i = 0; i < slen; ++i) {
        if (s[i] == '\\' || s[i] == '"')
            ++to_escape;
    }

    h2o_iovec_t ret;
    ret.len = slen + to_escape + 2;
    if (pool != NULL) {
        ret.base = h2o_mem_alloc_pool(pool, char, ret.len + 1);
    } else {
        ret.base = h2o_mem_alloc(ret.len + 1);
    }
    char *dst = ret.base;
    *dst++ = '"';
    for (size_t i = 0; i < slen; ++i) {
        if (s[i] == '\\' || s[i] == '"')
            *dst++ = '\\';
        *dst++ = s[i];
    }
    *dst++ = '"';
    *dst++ = '\0';
    return ret;
}

Coverage Report

Created: 2023-06-07 06:21

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Copyright (c) 2014-2016 DeNA Co., Ltd., Kazuho Oku, Justin Zhu, Fastly, Inc.
3		*
4		* Permission is hereby granted, free of charge, to any person obtaining a copy
5		* of this software and associated documentation files (the "Software"), to
6		* deal in the Software without restriction, including without limitation the
7		* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8		* sell copies of the Software, and to permit persons to whom the Software is
9		* furnished to do so, subject to the following conditions:
10		*
11		* The above copyright notice and this permission notice shall be included in
12		* all copies or substantial portions of the Software.
13		*
14		* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15		* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16		* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17		* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18		* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19		* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20		* IN THE SOFTWARE.
21		*/
22		#include <stdint.h>
23		#include <stdio.h>
24		#include <stdlib.h>
25		#include <string.h>
26		#include <time.h>
27		#include "h2o/string_.h"
28
29		h2o_iovec_t h2o_strdup(h2o_mem_pool_t pool, const char s, size_t slen)
30	6.93k	{
31		/* We do not need this check to be here, but it needs to be somewhere, see the definition of H2O_SIZE_T_LONGEST_STR */
32	6.93k	H2O_BUILD_ASSERT(sizeof(size_t) <= sizeof(uint64_t));
33
34	6.93k	h2o_iovec_t ret;
35
36	6.93k	if (slen == SIZE_MAX)
37	3.57k	slen = strlen(s);
38
39	6.93k	if (pool != NULL) {
40	6.92k	ret.base = h2o_mem_alloc_pool(pool, char, slen + 1);
41	6.92k	} else {
42	12	ret.base = h2o_mem_alloc(slen + 1);
43	12	}
44	6.93k	h2o_memcpy(ret.base, s, slen);
45	6.93k	ret.base[slen] = '\0';
46	6.93k	ret.len = slen;
47	6.93k	return ret;
48	6.93k	}
49
50		h2o_iovec_t h2o_strdup_shared(h2o_mem_pool_t pool, const char s, size_t slen)
51	0	{
52	0	h2o_iovec_t ret;
53
54	0	if (slen == SIZE_MAX)
55	0	slen = strlen(s);
56
57	0	ret.base = h2o_mem_alloc_shared(pool, slen + 1, NULL);
58	0	memcpy(ret.base, s, slen);
59	0	ret.base[slen] = '\0';
60	0	ret.len = slen;
61	0	return ret;
62	0	}
63
64		h2o_iovec_t h2o_strdup_slashed(h2o_mem_pool_t pool, const char src, size_t len)
65	2	{
66	2	h2o_iovec_t ret;
67
68	2	ret.len = len != SIZE_MAX ? len : strlen(src);
69	2	ret.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, ret.len + 2) : h2o_mem_alloc(ret.len + 2);
70	2	memcpy(ret.base, src, ret.len);
71	2	if (ret.len != 0 && ret.base[ret.len - 1] != '/')
72	1	ret.base[ret.len++] = '/';
73	2	ret.base[ret.len] = '\0';
74
75	2	return ret;
76	2	}
77
78		int h2o__lcstris_core(const char target, const char test, size_t test_len)
79	3.53k	{
80	15.9k	for (; test_len != 0; --test_len)
81	13.9k	if (h2o_tolower(target++) != test++)
82	1.53k	return 0;
83	2.00k	return 1;
84	3.53k	}
85
86		size_t h2o_strtosize(const char *s, size_t len)
87	995	{
88	995	uint64_t v = 0, m = 1;
89	995	const char *p = s + len;
90
91	995	if (len == 0)
92	8	goto Error;
93
94	5.17k	while (1) {
95	5.17k	int ch = *--p;
96	5.17k	if (!('0' <= ch && ch <= '9'))
97	25	goto Error;
98	5.14k	v += (ch - '0') * m;
99	5.14k	if (p == s)
100	961	break;
101	4.18k	m *= 10;
102		/* do not even try to overflow */
103	4.18k	if (m == 10000000000000000000ULL)
104	1	goto Error;
105	4.18k	}
106
107	961	if (v >= SIZE_MAX)
108	0	goto Error;
109	961	return v;
110
111	34	Error:
112	34	return SIZE_MAX;
113	961	}
114
115		size_t h2o_strtosizefwd(char **s, size_t len)
116	0	{
117	0	uint64_t v, c;
118	0	char p = s, p_end = s + len;
119
120	0	if (len == 0)
121	0	goto Error;
122
123	0	int ch = *p++;
124	0	if (!('0' <= ch && ch <= '9'))
125	0	goto Error;
126	0	v = ch - '0';
127	0	c = 1;
128
129	0	while (1) {
130	0	ch = *p;
131	0	if (!('0' <= ch && ch <= '9'))
132	0	break;
133	0	v *= 10;
134	0	v += ch - '0';
135	0	p++;
136	0	c++;
137	0	if (p == p_end)
138	0	break;
139		/* similar as above, do not even try to overflow */
140	0	if (c == 20)
141	0	goto Error;
142	0	}
143
144	0	if (v >= SIZE_MAX)
145	0	goto Error;
146	0	*s = p;
147	0	return v;
148
149	0	Error:
150	0	return SIZE_MAX;
151	0	}
152
153		static uint32_t decode_base64url_quad(const char *src)
154	1.05M	{
155	1.05M	const char *src_end = src + 4;
156	1.05M	uint32_t decoded = 0;
157
158	4.11M	while (1) {
159	4.11M	if ('A' <= src && src <= 'Z') {
160	798k	decoded \|= *src - 'A';
161	3.31M	} else if ('a' <= src && src <= 'z') {
162	2.66M	decoded \|= *src - 'a' + 26;
163	2.66M	} else if ('0' <= src && src <= '9') {
164	10.0k	decoded \|= *src - '0' + 52;
165	641k	} else if (*src == '-') {
166	523k	decoded \|= 62;
167	523k	} else if (*src == '_') {
168	2.02k	decoded \|= 63;
169	2.02k	#if 1 /* curl uses normal base64 */
170	116k	} else if (*src == '+') {
171	2.55k	decoded \|= 62;
172	113k	} else if (*src == '/') {
173	9.20k	decoded \|= 63;
174	9.20k	#endif
175	104k	} else {
176	104k	return UINT32_MAX;
177	104k	}
178	4.01M	if (++src == src_end)
179	950k	break;
180	3.06M	decoded <<= 6;
181	3.06M	}
182
183	950k	return decoded;
184	1.05M	}
185
186		h2o_iovec_t h2o_decode_base64url(h2o_mem_pool_t pool, const char src, size_t len)
187	200k	{
188	200k	h2o_iovec_t decoded;
189	200k	uint32_t t;
190	200k	uint8_t *dst;
191	200k	char remaining_input[4];
192
193	200k	decoded.len = len * 3 / 4;
194	200k	decoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, decoded.len + 1) : h2o_mem_alloc(decoded.len + 1);
195	200k	dst = (uint8_t *)decoded.base;
196
197	1.07M	while (len >= 4) {
198	972k	if ((t = decode_base64url_quad(src)) == UINT32_MAX)
199	102k	goto Error;
200	870k	*dst++ = t >> 16;
201	870k	*dst++ = t >> 8;
202	870k	*dst++ = t;
203	870k	src += 4;
204	870k	len -= 4;
205	870k	}
206	98.0k	switch (len) {
207	14.5k	case 0:
208	14.5k	break;
209	940	case 1:
210	940	goto Error;
211	79.9k	case 2:
212	79.9k	remaining_input[0] = *src++;
213	79.9k	remaining_input[1] = *src++;
214	79.9k	remaining_input[2] = 'A';
215	79.9k	remaining_input[3] = 'A';
216	79.9k	if ((t = decode_base64url_quad(remaining_input)) == UINT32_MAX)
217	679	goto Error;
218	79.2k	*dst++ = t >> 16;
219	79.2k	break;
220	2.61k	case 3:
221	2.61k	remaining_input[0] = *src++;
222	2.61k	remaining_input[1] = *src++;
223	2.61k	remaining_input[2] = *src++;
224	2.61k	remaining_input[3] = 'A';
225	2.61k	if ((t = decode_base64url_quad(remaining_input)) == UINT32_MAX)
226	1.54k	goto Error;
227	1.07k	*dst++ = t >> 16;
228	1.07k	*dst++ = t >> 8;
229	1.07k	break;
230	98.0k	}
231
232	94.8k	assert((char *)dst - decoded.base == decoded.len);
233	0	decoded.base[decoded.len] = '\0';
234
235	94.8k	return decoded;
236
237	105k	Error:
238	105k	if (pool == NULL)
239	105k	free(decoded.base);
240	105k	return h2o_iovec_init(NULL, 0);
241	98.0k	}
242
243		size_t h2o_base64_encode(char _dst, const void _src, size_t len, int url_encoded)
244	0	{
245	0	static const char *MAP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
246	0	"abcdefghijklmnopqrstuvwxyz"
247	0	"0123456789+/";
248	0	static const char *MAP_URL_ENCODED = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
249	0	"abcdefghijklmnopqrstuvwxyz"
250	0	"0123456789-_";
251
252	0	char *dst = _dst;
253	0	const uint8_t *src = _src;
254	0	const char *map = url_encoded ? MAP_URL_ENCODED : MAP;
255	0	uint32_t quad;
256
257	0	for (; len >= 3; src += 3, len -= 3) {
258	0	quad = ((uint32_t)src[0] << 16) \| ((uint32_t)src[1] << 8) \| src[2];
259	0	*dst++ = map[quad >> 18];
260	0	*dst++ = map[(quad >> 12) & 63];
261	0	*dst++ = map[(quad >> 6) & 63];
262	0	*dst++ = map[quad & 63];
263	0	}
264	0	if (len != 0) {
265	0	quad = (uint32_t)src[0] << 16;
266	0	*dst++ = map[quad >> 18];
267	0	if (len == 2) {
268	0	quad \|= (uint32_t)src[1] << 8;
269	0	*dst++ = map[(quad >> 12) & 63];
270	0	*dst++ = map[(quad >> 6) & 63];
271	0	if (!url_encoded)
272	0	*dst++ = '=';
273	0	} else {
274	0	*dst++ = map[(quad >> 12) & 63];
275	0	if (!url_encoded) {
276	0	*dst++ = '=';
277	0	*dst++ = '=';
278	0	}
279	0	}
280	0	}
281
282	0	*dst = '\0';
283	0	return dst - _dst;
284	0	}
285
286		static int decode_hex(int ch)
287	0	{
288	0	if ('0' <= ch && ch <= '9')
289	0	return ch - '0';
290	0	if ('A' <= ch && ch <= 'F')
291	0	return ch - 'A' + 0xa;
292	0	if ('a' <= ch && ch <= 'f')
293	0	return ch - 'a' + 0xa;
294	0	return -1;
295	0	}
296
297		int h2o_hex_decode(void _dst, const char src, size_t src_len)
298	0	{
299	0	unsigned char *dst = _dst;
300
301	0	if (src_len % 2 != 0)
302	0	return -1;
303	0	for (; src_len != 0; src_len -= 2) {
304	0	int hi, lo;
305	0	if ((hi = decode_hex(src++)) == -1 \|\| (lo = decode_hex(src++)) == -1)
306	0	return -1;
307	0	*dst++ = (hi << 4) \| lo;
308	0	}
309	0	return 0;
310	0	}
311
312		void h2o_hex_encode(char dst, const void _src, size_t src_len)
313	0	{
314	0	const unsigned char src = _src, src_end = src + src_len;
315	0	for (; src != src_end; ++src) {
316	0	dst++ = "0123456789abcdef"[src >> 4];
317	0	dst++ = "0123456789abcdef"[src & 0xf];
318	0	}
319	0	*dst = '\0';
320	0	}
321
322		h2o_iovec_t h2o_uri_escape(h2o_mem_pool_t pool, const char s, size_t l, const char *preserve_chars)
323	0	{
324	0	h2o_iovec_t encoded;
325	0	size_t i, capacity = l * 3 + 1;
326
327	0	encoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, capacity) : h2o_mem_alloc(capacity);
328	0	encoded.len = 0;
329
330		/* RFC 3986:
331		path-noscheme = segment-nz-nc *( "/" segment )
332		segment-nz-nc = 1*( unreserved / pct-encoded / sub-delims / "@" )
333		unreserved = ALPHA / DIGIT / "-" / "." / "_" / "~"
334		sub-delims = "!" / "$" / "&" / "'" / "(" / ")"
335		/ "*" / "+" / "," / ";" / "="
336		*/
337	0	for (i = 0; i != l; ++i) {
338	0	int ch = s[i];
339	0	if (('A' <= ch && ch <= 'Z') \|\| ('a' <= ch && ch <= 'z') \|\| ('0' <= ch && ch <= '9') \|\| ch == '-' \|\| ch == '.' \|\|
340	0	ch == '_' \|\| ch == '~' \|\| ch == '!' \|\| ch == '$' \|\| ch == '&' \|\| ch == '\'' \|\| ch == '(' \|\| ch == ')' \|\| ch == '*' \|\|
341	0	ch == '+' \|\| ch == ',' \|\| ch == ';' \|\| ch == '=' \|\|
342	0	(ch != '\0' && preserve_chars != NULL && strchr(preserve_chars, ch) != NULL)) {
343	0	encoded.base[encoded.len++] = ch;
344	0	} else {
345	0	encoded.base[encoded.len++] = '%';
346	0	encoded.base[encoded.len++] = "0123456789ABCDEF"[(ch >> 4) & 0xf];
347	0	encoded.base[encoded.len++] = "0123456789ABCDEF"[ch & 0xf];
348	0	}
349	0	}
350	0	encoded.base[encoded.len] = '\0';
351
352	0	return encoded;
353	0	}
354
355		h2o_iovec_t h2o_get_filext(const char *path, size_t len)
356	0	{
357	0	const char end = path + len, p = end;
358
359	0	while (--p != path) {
360	0	if (*p == '.') {
361	0	return h2o_iovec_init(p + 1, end - (p + 1));
362	0	} else if (*p == '/') {
363	0	break;
364	0	}
365	0	}
366	0	return h2o_iovec_init(NULL, 0);
367	0	}
368
369		static int is_ws(int ch)
370	0	{
371	0	return ch == ' ' \|\| ch == '\t' \|\| ch == '\r' \|\| ch == '\n';
372	0	}
373
374		h2o_iovec_t h2o_str_stripws(const char *s, size_t len)
375	0	{
376	0	const char *end = s + len;
377
378	0	while (s != end) {
379	0	if (!is_ws(*s))
380	0	break;
381	0	++s;
382	0	}
383	0	while (s != end) {
384	0	if (!is_ws(end[-1]))
385	0	break;
386	0	--end;
387	0	}
388	0	return h2o_iovec_init(s, end - s);
389	0	}
390
391		size_t h2o_strstr(const char haysack, size_t haysack_len, const char needle, size_t needle_len)
392	2.34k	{
393		/* TODO optimize */
394	2.34k	if (haysack_len >= needle_len) {
395	2.16k	size_t off, max = haysack_len - needle_len + 1;
396	2.16k	if (needle_len == 0)
397	0	return 0;
398	59.5k	for (off = 0; off != max; ++off)
399	57.3k	if (haysack[off] == needle[0] && memcmp(haysack + off + 1, needle + 1, needle_len - 1) == 0)
400	0	return off;
401	2.16k	}
402	2.34k	return SIZE_MAX;
403	2.34k	}
404
405		/* note: returns a zero-width match as well */
406		const char h2o_next_token(h2o_iovec_t iter, int inner, int outer, size_t element_len, h2o_iovec_t value)
407	417k	{
408	417k	const char cur = iter->base, end = iter->base + iter->len, token_start, token_end;
409
410		/* find start */
411	420k	for (;; ++cur) {
412	420k	if (cur == end)
413	102k	return NULL;
414	317k	if (!(cur == ' ' \|\| cur == '\t'))
415	315k	break;
416	317k	}
417	315k	token_start = cur;
418	315k	token_end = cur;
419
420		/* find last */
421	4.89M	for (;; ++cur) {
422	4.89M	if (cur == end)
423	100k	break;
424	4.79M	if (*cur == inner) {
425	6.01k	++cur;
426	6.01k	break;
427	6.01k	}
428	4.78M	if (*cur == outer) {
429	205k	if (token_start == cur) {
430	103k	++cur;
431	103k	token_end = cur;
432	103k	}
433	205k	break;
434	205k	}
435	4.58M	if (value != NULL && *cur == '=') {
436	2.80k	++cur;
437	2.80k	goto FindValue;
438	2.80k	}
439	4.58M	if (!(cur == ' ' \|\| cur == '\t'))
440	4.56M	token_end = cur + 1;
441	4.58M	}
442
443		/* found */
444	312k	*iter = h2o_iovec_init(cur, end - cur);
445	312k	*element_len = token_end - token_start;
446	312k	if (value != NULL)
447	105k	*value = (h2o_iovec_t){NULL};
448	312k	return token_start;
449
450	2.80k	FindValue:
451	2.80k	*iter = h2o_iovec_init(cur, end - cur);
452	2.80k	*element_len = token_end - token_start;
453	2.80k	if ((value->base = (char *)h2o_next_token(iter, inner, outer, &value->len, NULL)) == NULL) {
454	454	*value = (h2o_iovec_t){"", 0};
455	2.35k	} else if (h2o_memis(value->base, value->len, H2O_STRLIT(","))) {
456	221	*value = (h2o_iovec_t){"", 0};
457	221	iter->base -= 1;
458	221	iter->len += 1;
459	221	}
460	2.80k	return token_start;
461	315k	}
462
463		int h2o_contains_token(const char haysack, size_t haysack_len, const char needle, size_t needle_len, int separator)
464	664	{
465	664	h2o_iovec_t iter = h2o_iovec_init(haysack, haysack_len);
466	664	const char *token = NULL;
467	664	size_t token_len = 0;
468
469	1.32k	while ((token = h2o_next_token(&iter, separator, ',', &token_len, NULL)) != NULL) {
470	664	if (h2o_lcstris(token, token_len, needle, needle_len)) {
471	0	return 1;
472	0	}
473	664	}
474	664	return 0;
475	664	}
476
477		h2o_iovec_t h2o_htmlescape(h2o_mem_pool_t pool, const char src, size_t len)
478	0	{
479	0	const char s, end = src + len;
480	0	size_t add_size = 0;
481
482	0	#define ENTITY_MAP() \
483	0	ENTITY('"', """); \
484	0	ENTITY('&', "&"); \
485	0	ENTITY('\'', "'"); \
486	0	ENTITY('<', "<"); \
487	0	ENTITY('>', ">");
488
489	0	for (s = src; s != end; ++s) {
490	0	if ((unsigned)(unsigned char)*s - '"' <= '>' - '"') {
491	0	switch (*s) {
492	0	#define ENTITY(code, quoted) \
493	0	case code: \
494	0	add_size += sizeof(quoted) - 2; \
495	0	break
496	0	ENTITY_MAP()
497	0	#undef ENTITY
498	0	}
499	0	}
500	0	}
501
502		/* escape and return the result if necessary */
503	0	if (add_size != 0) {
504		/* allocate buffer and fill in the chars that are known not to require escaping */
505	0	h2o_iovec_t escaped = {h2o_mem_alloc_pool(pool, char, len + add_size + 1), 0};
506		/* fill-in the rest */
507	0	for (s = src; s != end; ++s) {
508	0	switch (*s) {
509	0	#define ENTITY(code, quoted) \
510	0	case code: \
511	0	memcpy(escaped.base + escaped.len, quoted, sizeof(quoted) - 1); \
512	0	escaped.len += sizeof(quoted) - 1; \
513	0	break
514	0	ENTITY_MAP()
515	0	#undef ENTITY
516	0	default:
517	0	escaped.base[escaped.len++] = *s;
518	0	break;
519	0	}
520	0	}
521	0	assert(escaped.len == len + add_size);
522	0	escaped.base[escaped.len] = '\0';
523
524	0	return escaped;
525	0	}
526
527	0	#undef ENTITY_MAP
528
529		/* no need not escape; return the original */
530	0	return h2o_iovec_init(src, len);
531	0	}
532
533		h2o_iovec_t h2o_concat_list(h2o_mem_pool_t pool, h2o_iovec_t list, size_t count)
534	1.41k	{
535	1.41k	h2o_iovec_t ret = {NULL, 0};
536	1.41k	size_t i;
537
538		/* calc the length */
539	4.08k	for (i = 0; i != count; ++i) {
540	2.66k	ret.len += list[i].len;
541	2.66k	}
542
543		/* allocate memory */
544	1.41k	if (pool != NULL)
545	1.41k	ret.base = h2o_mem_alloc_pool(pool, char, ret.len + 1);
546	0	else
547	0	ret.base = h2o_mem_alloc(ret.len + 1);
548
549		/* concatenate */
550	1.41k	ret.len = 0;
551	4.08k	for (i = 0; i != count; ++i) {
552	2.66k	h2o_memcpy(ret.base + ret.len, list[i].base, list[i].len);
553	2.66k	ret.len += list[i].len;
554	2.66k	}
555	1.41k	ret.base[ret.len] = '\0';
556
557	1.41k	return ret;
558	1.41k	}
559
560		h2o_iovec_t h2o_join_list(h2o_mem_pool_t pool, h2o_iovec_t list, size_t count, h2o_iovec_t delimiter)
561	26	{
562	26	if (count == 0) {
563	0	return h2o_iovec_init(NULL, 0);
564	0	}
565
566	26	size_t joined_len = 0;
567	26	h2o_iovec_t joined = alloca(sizeof(joined) * (count * 2 - 1));
568
569	26	size_t i;
570	339	for (i = 0; i != count; ++i) {
571	313	if (i != 0) {
572	287	joined[joined_len++] = delimiter;
573	287	}
574	313	joined[joined_len++] = list[i];
575	313	}
576	26	return h2o_concat_list(pool, joined, joined_len);
577	26	}
578
579		void h2o_split(h2o_mem_pool_t pool, h2o_iovec_vector_t list, h2o_iovec_t str, const char needle)
580	0	{
581	0	const char p = str.base, end = str.base + str.len, *found;
582
583	0	while (p < end && (found = memchr(p, needle, end - p)) != NULL) {
584	0	h2o_vector_reserve(pool, list, list->size + 1);
585	0	list->entries[list->size++] = h2o_strdup(pool, p, found - p);
586	0	p = found + 1;
587	0	}
588	0	h2o_vector_reserve(pool, list, list->size + 1);
589	0	list->entries[list->size++] = h2o_strdup(pool, p, end - p);
590	0	}
591
592		int h2o_str_at_position(char buf, const char src, size_t src_len, int lineno, int column)
593	0	{
594	0	const char *src_end = src + src_len;
595	0	int i;
596
597		/* find the line */
598	0	if (lineno <= 0 \|\| column <= 0)
599	0	return -1;
600	0	for (--lineno; lineno != 0; --lineno) {
601	0	do {
602	0	if (src == src_end)
603	0	return -1;
604	0	} while (*src++ != '\n');
605	0	}
606
607		/* adjust the starting column */
608	0	while (column > 40) {
609	0	if (src != src_end)
610	0	++src;
611	0	--column;
612	0	}
613
614		/* emit */
615	0	for (i = 1; i <= 76; ++i) {
616	0	if (src == src_end \|\| *src == '\n')
617	0	break;
618	0	buf++ = src++;
619	0	}
620	0	if (i < column)
621	0	column = i;
622	0	*buf++ = '\n';
623	0	for (i = 1; i < column; ++i)
624	0	*buf++ = ' ';
625	0	*buf++ = '^';
626	0	*buf++ = '\n';
627	0	*buf = '\0';
628	0	return 0;
629	0	}
630
631		h2o_iovec_t h2o_encode_sf_string(h2o_mem_pool_t pool, const char s, size_t slen)
632	0	{
633	0	if (slen == SIZE_MAX)
634	0	slen = strlen(s);
635
636		/* https://tools.ietf.org/html/rfc8941#section-3.3.3 */
637	0	size_t to_escape = 0;
638	0	for (size_t i = 0; i < slen; ++i) {
639	0	if (s[i] == '\\' \|\| s[i] == '"')
640	0	++to_escape;
641	0	}
642
643	0	h2o_iovec_t ret;
644	0	ret.len = slen + to_escape + 2;
645	0	if (pool != NULL) {
646	0	ret.base = h2o_mem_alloc_pool(pool, char, ret.len + 1);
647	0	} else {
648	0	ret.base = h2o_mem_alloc(ret.len + 1);
649	0	}
650	0	char *dst = ret.base;
651	0	*dst++ = '"';
652	0	for (size_t i = 0; i < slen; ++i) {
653	0	if (s[i] == '\\' \|\| s[i] == '"')
654	0	*dst++ = '\\';
655	0	*dst++ = s[i];
656	0	}
657	0	*dst++ = '"';
658	0	*dst++ = '\0';
659	0	return ret;
660	0	}