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

Source
/*
 * 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_uri_unescape(h2o_mem_pool_t *pool, const char *str, size_t len)
{
    h2o_iovec_t decoded;

    decoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, len + 1) : h2o_mem_alloc(len + 1);
    decoded.len = 0;

    for (size_t i = 0; i < len; ++i) {
        if (str[i] == '%') {
            if (i + 2 >= len)
                goto Fail;
            int hi = decode_hex(str[i + 1]);
            int lo = decode_hex(str[i + 2]);
            if (hi < 0 || lo < 0 || (hi == 0 && lo == 0))
                goto Fail;
            decoded.base[decoded.len++] = (hi << 4) | lo;
            i += 2;
        } else {
            decoded.base[decoded.len++] = str[i];
        }
    }
    decoded.base[decoded.len] = '\0';
    return decoded;

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

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: 2025-10-13 07:14

Line	Count	Source
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	154k	{
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	154k	H2O_BUILD_ASSERT(sizeof(size_t) <= sizeof(uint64_t));
33
34	154k	h2o_iovec_t ret;
35
36	154k	if (slen == SIZE_MAX)
37	17.2k	slen = strlen(s);
38
39	154k	if (pool != NULL) {
40	154k	ret.base = h2o_mem_alloc_pool(pool, char, slen + 1);
41	154k	} else {
42	35	ret.base = h2o_mem_alloc(slen + 1);
43	35	}
44	154k	h2o_memcpy(ret.base, s, slen);
45	154k	ret.base[slen] = '\0';
46	154k	ret.len = slen;
47	154k	return ret;
48	154k	}
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	6	{
66	6	h2o_iovec_t ret;
67
68	6	ret.len = len != SIZE_MAX ? len : strlen(src);
69	6	ret.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, ret.len + 2) : h2o_mem_alloc(ret.len + 2);
70	6	memcpy(ret.base, src, ret.len);
71	6	if (ret.len != 0 && ret.base[ret.len - 1] != '/')
72	3	ret.base[ret.len++] = '/';
73	6	ret.base[ret.len] = '\0';
74
75	6	return ret;
76	6	}
77
78		int h2o__lcstris_core(const char target, const char test, size_t test_len)
79	9.35k	{
80	48.3k	for (; test_len != 0; --test_len)
81	43.6k	if (h2o_tolower(target++) != test++)
82	4.70k	return 0;
83	4.65k	return 1;
84	9.35k	}
85
86		size_t h2o_strtosize(const char *s, size_t len)
87	7.89k	{
88	7.89k	uint64_t v = 0, m = 1;
89	7.89k	const char *p = s + len;
90
91	7.89k	if (len == 0)
92	27	goto Error;
93
94	20.3k	while (1) {
95	20.3k	int ch = *--p;
96	20.3k	if (!('0' <= ch && ch <= '9'))
97	115	goto Error;
98	20.1k	v += (ch - '0') * m;
99	20.1k	if (p == s)
100	7.74k	break;
101	12.4k	m *= 10;
102		/* do not even try to overflow */
103	12.4k	if (m == 10000000000000000000ULL)
104	4	goto Error;
105	12.4k	}
106
107	7.74k	if (v >= SIZE_MAX)
108	0	goto Error;
109	7.74k	return v;
110
111	146	Error:
112	146	return SIZE_MAX;
113	7.74k	}
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	610k	{
155	610k	const char *src_end = src + 4;
156	610k	uint32_t decoded = 0;
157
158	2.40M	while (1) {
159	2.40M	if ('A' <= src && src <= 'Z') {
160	583k	decoded \|= *src - 'A';
161	1.82M	} else if ('a' <= src && src <= 'z') {
162	1.35M	decoded \|= *src - 'a' + 26;
163	1.35M	} else if ('0' <= src && src <= '9') {
164	60.1k	decoded \|= *src - '0' + 52;
165	406k	} else if (*src == '-') {
166	276k	decoded \|= 62;
167	276k	} else if (*src == '_') {
168	4.88k	decoded \|= 63;
169	4.88k	#if 1 /* curl uses normal base64 */
170	125k	} else if (*src == '+') {
171	51.4k	decoded \|= 62;
172	73.6k	} else if (*src == '/') {
173	52.9k	decoded \|= 63;
174	52.9k	#endif
175	52.9k	} else {
176	20.6k	return UINT32_MAX;
177	20.6k	}
178	2.38M	if (++src == src_end)
179	589k	break;
180	1.79M	decoded <<= 6;
181	1.79M	}
182
183	589k	return decoded;
184	610k	}
185
186		h2o_iovec_t h2o_decode_base64url(h2o_mem_pool_t pool, const char src, size_t len)
187	134k	{
188	134k	h2o_iovec_t decoded;
189	134k	uint32_t t;
190	134k	uint8_t *dst;
191	134k	char remaining_input[4];
192
193	134k	decoded.len = len * 3 / 4;
194	134k	decoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, decoded.len + 1) : h2o_mem_alloc(decoded.len + 1);
195	134k	dst = (uint8_t *)decoded.base;
196
197	663k	while (len >= 4) {
198	545k	if ((t = decode_base64url_quad(src)) == UINT32_MAX)
199	16.6k	goto Error;
200	529k	*dst++ = t >> 16;
201	529k	*dst++ = t >> 8;
202	529k	*dst++ = t;
203	529k	src += 4;
204	529k	len -= 4;
205	529k	}
206	117k	switch (len) {
207	47.8k	case 0:
208	47.8k	break;
209	5.24k	case 1:
210	5.24k	goto Error;
211	49.7k	case 2:
212	49.7k	remaining_input[0] = *src++;
213	49.7k	remaining_input[1] = *src++;
214	49.7k	remaining_input[2] = 'A';
215	49.7k	remaining_input[3] = 'A';
216	49.7k	if ((t = decode_base64url_quad(remaining_input)) == UINT32_MAX)
217	2.00k	goto Error;
218	47.7k	*dst++ = t >> 16;
219	47.7k	break;
220	14.9k	case 3:
221	14.9k	remaining_input[0] = *src++;
222	14.9k	remaining_input[1] = *src++;
223	14.9k	remaining_input[2] = *src++;
224	14.9k	remaining_input[3] = 'A';
225	14.9k	if ((t = decode_base64url_quad(remaining_input)) == UINT32_MAX)
226	2.07k	goto Error;
227	12.9k	*dst++ = t >> 16;
228	12.9k	*dst++ = t >> 8;
229	12.9k	break;
230	117k	}
231
232	117k	assert((char *)dst - decoded.base == decoded.len);
233	108k	decoded.base[decoded.len] = '\0';
234
235	108k	return decoded;
236
237	25.9k	Error:
238	25.9k	if (pool == NULL)
239	25.9k	free(decoded.base);
240	25.9k	return h2o_iovec_init(NULL, 0);
241	108k	}
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_uri_unescape(h2o_mem_pool_t pool, const char str, size_t len)
356	0	{
357	0	h2o_iovec_t decoded;
358
359	0	decoded.base = pool != NULL ? h2o_mem_alloc_pool(pool, char, len + 1) : h2o_mem_alloc(len + 1);
360	0	decoded.len = 0;
361
362	0	for (size_t i = 0; i < len; ++i) {
363	0	if (str[i] == '%') {
364	0	if (i + 2 >= len)
365	0	goto Fail;
366	0	int hi = decode_hex(str[i + 1]);
367	0	int lo = decode_hex(str[i + 2]);
368	0	if (hi < 0 \|\| lo < 0 \|\| (hi == 0 && lo == 0))
369	0	goto Fail;
370	0	decoded.base[decoded.len++] = (hi << 4) \| lo;
371	0	i += 2;
372	0	} else {
373	0	decoded.base[decoded.len++] = str[i];
374	0	}
375	0	}
376	0	decoded.base[decoded.len] = '\0';
377	0	return decoded;
378
379	0	Fail:
380	0	if (pool == NULL)
381	0	free(decoded.base);
382	0	return h2o_iovec_init(NULL, 0);
383	0	}
384
385		h2o_iovec_t h2o_get_filext(const char *path, size_t len)
386	0	{
387	0	const char end = path + len, p = end;
388
389	0	while (--p != path) {
390	0	if (*p == '.') {
391	0	return h2o_iovec_init(p + 1, end - (p + 1));
392	0	} else if (*p == '/') {
393	0	break;
394	0	}
395	0	}
396	0	return h2o_iovec_init(NULL, 0);
397	0	}
398
399		static int is_ws(int ch)
400	0	{
401	0	return ch == ' ' \|\| ch == '\t' \|\| ch == '\r' \|\| ch == '\n';
402	0	}
403
404		h2o_iovec_t h2o_str_stripws(const char *s, size_t len)
405	0	{
406	0	const char *end = s + len;
407
408	0	while (s != end) {
409	0	if (!is_ws(*s))
410	0	break;
411	0	++s;
412	0	}
413	0	while (s != end) {
414	0	if (!is_ws(end[-1]))
415	0	break;
416	0	--end;
417	0	}
418	0	return h2o_iovec_init(s, end - s);
419	0	}
420
421		size_t h2o_strstr(const char haysack, size_t haysack_len, const char needle, size_t needle_len)
422	13.3k	{
423		/* TODO optimize */
424	13.3k	if (haysack_len >= needle_len) {
425	8.76k	size_t off, max = haysack_len - needle_len + 1;
426	8.76k	if (needle_len == 0)
427	0	return 0;
428	1.70M	for (off = 0; off != max; ++off)
429	1.69M	if (haysack[off] == needle[0] && memcmp(haysack + off + 1, needle + 1, needle_len - 1) == 0)
430	0	return off;
431	8.76k	}
432	13.3k	return SIZE_MAX;
433	13.3k	}
434
435		/* note: returns a zero-width match as well */
436		const char h2o_next_token(h2o_iovec_t iter, int inner, int outer, size_t element_len, h2o_iovec_t value)
437	318k	{
438	318k	const char cur = iter->base, end = iter->base + iter->len, token_start, token_end;
439
440		/* find start */
441	325k	for (;; ++cur) {
442	325k	if (cur == end)
443	65.9k	return NULL;
444	260k	if (!(cur == ' ' \|\| cur == '\t'))
445	253k	break;
446	260k	}
447	253k	token_start = cur;
448	253k	token_end = cur;
449
450		/* find last */
451	3.09M	for (;; ++cur) {
452	3.09M	if (cur == end)
453	63.7k	break;
454	3.02M	if (*cur == inner) {
455	18.8k	++cur;
456	18.8k	break;
457	18.8k	}
458	3.00M	if (*cur == outer) {
459	163k	if (token_start == cur) {
460	87.1k	++cur;
461	87.1k	token_end = cur;
462	87.1k	}
463	163k	break;
464	163k	}
465	2.84M	if (value != NULL && *cur == '=') {
466	6.47k	++cur;
467	6.47k	goto FindValue;
468	6.47k	}
469	2.83M	if (!(cur == ' ' \|\| cur == '\t'))
470	2.82M	token_end = cur + 1;
471	2.83M	}
472
473		/* found */
474	246k	*iter = h2o_iovec_init(cur, end - cur);
475	246k	*element_len = token_end - token_start;
476	246k	if (value != NULL)
477	91.2k	*value = (h2o_iovec_t){NULL};
478	246k	return token_start;
479
480	6.47k	FindValue:
481	6.47k	*iter = h2o_iovec_init(cur, end - cur);
482	6.47k	*element_len = token_end - token_start;
483	6.47k	if ((value->base = (char *)h2o_next_token(iter, inner, outer, &value->len, NULL)) == NULL) {
484	712	*value = (h2o_iovec_t){"", 0};
485	5.76k	} else if (h2o_memis(value->base, value->len, H2O_STRLIT(","))) {
486	567	*value = (h2o_iovec_t){"", 0};
487	567	iter->base -= 1;
488	567	iter->len += 1;
489	567	}
490	6.47k	return token_start;
491	253k	}
492
493		int h2o_contains_token(const char haysack, size_t haysack_len, const char needle, size_t needle_len, int separator)
494	5.50k	{
495	5.50k	h2o_iovec_t iter = h2o_iovec_init(haysack, haysack_len);
496	5.50k	const char *token = NULL;
497	5.50k	size_t token_len = 0;
498
499	11.9k	while ((token = h2o_next_token(&iter, separator, ',', &token_len, NULL)) != NULL) {
500	8.13k	if (h2o_lcstris(token, token_len, needle, needle_len)) {
501	1.68k	return 1;
502	1.68k	}
503	8.13k	}
504	3.81k	return 0;
505	5.50k	}
506
507		h2o_iovec_t h2o_htmlescape(h2o_mem_pool_t pool, const char src, size_t len)
508	0	{
509	0	const char s, end = src + len;
510	0	size_t add_size = 0;
511
512	0	#define ENTITY_MAP() \
513	0	ENTITY('"', """); \
514	0	ENTITY('&', "&"); \
515	0	ENTITY('\'', "'"); \
516	0	ENTITY('<', "<"); \
517	0	ENTITY('>', ">");
518
519	0	for (s = src; s != end; ++s) {
520	0	if ((unsigned)(unsigned char)*s - '"' <= '>' - '"') {
521	0	switch (*s) {
522	0	#define ENTITY(code, quoted) \
523	0	case code: \
524	0	add_size += sizeof(quoted) - 2; \
525	0	break
526	0	ENTITY_MAP()
527	0	#undef ENTITY
528	0	}
529	0	}
530	0	}
531
532		/* escape and return the result if necessary */
533	0	if (add_size != 0) {
534		/* allocate buffer and fill in the chars that are known not to require escaping */
535	0	h2o_iovec_t escaped = {h2o_mem_alloc_pool(pool, char, len + add_size + 1), 0};
536		/* fill-in the rest */
537	0	for (s = src; s != end; ++s) {
538	0	switch (*s) {
539	0	#define ENTITY(code, quoted) \
540	0	case code: \
541	0	memcpy(escaped.base + escaped.len, quoted, sizeof(quoted) - 1); \
542	0	escaped.len += sizeof(quoted) - 1; \
543	0	break
544	0	ENTITY_MAP()
545	0	#undef ENTITY
546	0	default:
547	0	escaped.base[escaped.len++] = *s;
548	0	break;
549	0	}
550	0	}
551	0	assert(escaped.len == len + add_size);
552	0	escaped.base[escaped.len] = '\0';
553
554	0	return escaped;
555	0	}
556
557	0	#undef ENTITY_MAP
558
559		/* no need not escape; return the original */
560	0	return h2o_iovec_init(src, len);
561	0	}
562
563		h2o_iovec_t h2o_concat_list(h2o_mem_pool_t pool, h2o_iovec_t list, size_t count)
564	7.93k	{
565	7.93k	h2o_iovec_t ret = {NULL, 0};
566	7.93k	size_t i;
567
568		/* calc the length */
569	433k	for (i = 0; i != count; ++i) {
570	425k	ret.len += list[i].len;
571	425k	}
572
573		/* allocate memory */
574	7.93k	if (pool != NULL)
575	7.93k	ret.base = h2o_mem_alloc_pool(pool, char, ret.len + 1);
576	0	else
577	0	ret.base = h2o_mem_alloc(ret.len + 1);
578
579		/* concatenate */
580	7.93k	ret.len = 0;
581	433k	for (i = 0; i != count; ++i) {
582	425k	h2o_memcpy(ret.base + ret.len, list[i].base, list[i].len);
583	425k	ret.len += list[i].len;
584	425k	}
585	7.93k	ret.base[ret.len] = '\0';
586
587	7.93k	return ret;
588	7.93k	}
589
590		h2o_iovec_t h2o_join_list(h2o_mem_pool_t pool, h2o_iovec_t list, size_t count, h2o_iovec_t delimiter)
591	385	{
592	385	if (count == 0) {
593	0	return h2o_iovec_init(NULL, 0);
594	0	}
595
596	385	size_t joined_len = 0;
597	385	h2o_iovec_t joined = alloca(sizeof(joined) * (count * 2 - 1));
598
599	385	size_t i;
600	207k	for (i = 0; i != count; ++i) {
601	207k	if (i != 0) {
602	206k	joined[joined_len++] = delimiter;
603	206k	}
604	207k	joined[joined_len++] = list[i];
605	207k	}
606	385	return h2o_concat_list(pool, joined, joined_len);
607	385	}
608
609		void h2o_split(h2o_mem_pool_t pool, h2o_iovec_vector_t list, h2o_iovec_t str, const char needle)
610	0	{
611	0	const char p = str.base, end = str.base + str.len, *found;
612
613	0	while (p < end && (found = memchr(p, needle, end - p)) != NULL) {
614	0	h2o_vector_reserve(pool, list, list->size + 1);
615	0	list->entries[list->size++] = h2o_strdup(pool, p, found - p);
616	0	p = found + 1;
617	0	}
618	0	h2o_vector_reserve(pool, list, list->size + 1);
619	0	list->entries[list->size++] = h2o_strdup(pool, p, end - p);
620	0	}
621
622		int h2o_str_at_position(char buf, const char src, size_t src_len, int lineno, int column)
623	0	{
624	0	const char *src_end = src + src_len;
625	0	int i;
626
627		/* find the line */
628	0	if (lineno <= 0 \|\| column <= 0)
629	0	return -1;
630	0	for (--lineno; lineno != 0; --lineno) {
631	0	do {
632	0	if (src == src_end)
633	0	return -1;
634	0	} while (*src++ != '\n');
635	0	}
636
637		/* adjust the starting column */
638	0	while (column > 40) {
639	0	if (src != src_end)
640	0	++src;
641	0	--column;
642	0	}
643
644		/* emit */
645	0	for (i = 1; i <= 76; ++i) {
646	0	if (src == src_end \|\| *src == '\n')
647	0	break;
648	0	buf++ = src++;
649	0	}
650	0	if (i < column)
651	0	column = i;
652	0	*buf++ = '\n';
653	0	for (i = 1; i < column; ++i)
654	0	*buf++ = ' ';
655	0	*buf++ = '^';
656	0	*buf++ = '\n';
657	0	*buf = '\0';
658	0	return 0;
659	0	}
660
661		h2o_iovec_t h2o_encode_sf_string(h2o_mem_pool_t pool, const char s, size_t slen)
662	0	{
663	0	if (slen == SIZE_MAX)
664	0	slen = strlen(s);
665
666		/* https://tools.ietf.org/html/rfc8941#section-3.3.3 */
667	0	size_t to_escape = 0;
668	0	for (size_t i = 0; i < slen; ++i) {
669	0	if (s[i] == '\\' \|\| s[i] == '"')
670	0	++to_escape;
671	0	}
672
673	0	h2o_iovec_t ret;
674	0	ret.len = slen + to_escape + 2;
675	0	if (pool != NULL) {
676	0	ret.base = h2o_mem_alloc_pool(pool, char, ret.len + 1);
677	0	} else {
678	0	ret.base = h2o_mem_alloc(ret.len + 1);
679	0	}
680	0	char *dst = ret.base;
681	0	*dst++ = '"';
682	0	for (size_t i = 0; i < slen; ++i) {
683	0	if (s[i] == '\\' \|\| s[i] == '"')
684	0	*dst++ = '\\';
685	0	*dst++ = s[i];
686	0	}
687	0	*dst++ = '"';
688	0	*dst++ = '\0';
689	0	return ret;
690	0	}