/*
** (c) Copyright 2003-2005 Matt Messier and John Viega
** All rights reserved.
** 
** Redistribution and use in source and binary forms, with or without
** modification, are permitted provided that the following conditions are
** met:
** 
** Redistributions of source code must retain the above copyright notice,
** this list of conditions and the following disclaimer.
** 
** 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.
** 
** Neither the name of the primary nor the names of the contributors may
** be used to endorse or promote products derived from this software
** without specific prior written permission.
** 
** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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 COPYRIGHT
** OWNER 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 "isafestr.h"

u_int32_t         safestr_cookie     = 0;
u_int64_t         safestr_maxlength  = ((u_int64_t)1 << (sizeof(u_int32_t) * 8)) - sizeof(small_isafestr_t);
safestr_malloc_t  safestr_malloc_fn  = safestr_default_malloc;
safestr_realloc_t safestr_realloc_fn = safestr_default_realloc;
safestr_free_t    safestr_free_fn    = safestr_default_free;

static xxl_assettype_t map_asset(u_int32_t);
static int             compare_strings(isafestr_t, isafestr_t, unsigned char *, u_int32_t);
static void            free_isafestr_asset(isafestr_t, void *);
static void            free_void_asset(void *, void *);
static void            bake_cookie(void);
static u_int32_t       get_cookie(void);
static safestr_t *     charlist(isafestr_t, const char *, unsigned int);

unsigned char safestr_casemap_none[256] =
{
      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, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
    112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
    128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
    144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
    160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
    176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
    192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
    208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
    224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
    240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
};

unsigned char safestr_casemap_upper[256] =
{
      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,  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, 123, 124, 125, 126, 127,
    128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
    144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
    160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
    176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
    192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
    208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
    224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
    240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
};

unsigned char safestr_casemap_lower[256] =
{
      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,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
    112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122,  91,  92,  93,  94,  95,
     96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
    112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
    128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143,
    144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
    160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175,
    176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191,
    192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207,
    208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223,
    224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
    240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255
};

static xxl_assettype_t
map_asset(u_int32_t flag)
{
    switch ((flag & SAFESTR_ASSET_MASK))
    {
        case SAFESTR_ASSET_PERMANENT: return XXL_ASSET_PERMANENT;
        case SAFESTR_ASSET_TEMPORARY: return XXL_ASSET_TEMPORARY;
        case SAFESTR_ASSET_PROMOTE:   return XXL_ASSET_PROMOTE;
        case SAFESTR_ASSET_DEMOTE:    return XXL_ASSET_DEMOTE;
    }

    return XXL_ASSET_PERMANENT;
}

static int
compare_strings(isafestr_t istr1, isafestr_t istr2, unsigned char *map, u_int32_t limit)
{
    u_int32_t       i, length;
    unsigned char   *s1, *s2;

    if (map == safestr_casemap_none && limit == (u_int32_t)-1 && istr1->hdr.length == istr2->hdr.length)
        return memcmp(istr1->str, istr2->str, istr1->hdr.length);
    s1 = (unsigned char *)istr1->str;
    s2 = (unsigned char *)istr2->str;
    length = SAFESTR_MIN(istr1->hdr.length, istr2->hdr.length);
    if (limit != (u_int32_t)-1 && limit < length)
        length = limit;

    for (i = 0;  i < length;  i++)
    {
        if (map[s1[i]] == map[s2[i]])
            continue;
        else if (map[s1[i]] < map[s2[i]])
            return -1;
        return 1;
    }

    if (istr1->hdr.length == istr2->hdr.length)
        return 0;
    if (limit == -1)
        return (istr1->hdr.length < istr2->hdr.length ? -1 : 1);
    if (istr1->hdr.length < istr2->hdr.length)
        return (limit <= istr1->hdr.length ? 0 : -1);
    return (limit <= istr2->hdr.length ? 0 : 1);
}

static void
free_isafestr_asset(isafestr_t str, void *arg)
{
    if ((XXL_EXCEPTION_CODE() && !(str->hdr.flags & SAFESTR_ORIGINAL)) ||
        (!XXL_EXCEPTION_CODE() && (str->hdr.flags & SAFESTR_RESIZED)))
    {
        safestr_memzero(str->str, str->hdr.size + 1);
        str->hdr.size = str->hdr.length = str->hdr.flags = str->hdr.cookie = 0;
        safestr_free_fn(str, __FILE__, __LINE__);
        return;
    }

    str->hdr.flags &= ~(SAFESTR_ORIGINAL | SAFESTR_RESIZED);
    DEC_REF_COUNT(str);
    if (REF_COUNT(str) <= 0 ||
        (REF_COUNT(str) == 1 && (str->hdr.flags & SAFESTR_TEMPORARY)))
    {
        if (str->hdr.cookie != safestr_cookie)
            XXL_THROW_ERROR(SAFESTR_ERROR_BAD_ADDRESS, NULL);
#ifdef _DEBUG
        if (getenv("SAFESTR_TRACE"))
        {
            fprintf(stderr, "Freeing string 0x%08X (\"%s\")\n",
                    (unsigned int)str->str, str->str);
        }
#endif
        safestr_memzero(str->str, str->hdr.size + 1);
        str->hdr.size = str->hdr.length = str->hdr.flags = str->hdr.cookie = 0;
        safestr_free_fn(str, __FILE__, __LINE__);
    }
}

static void
free_void_asset(void *ptr, void *arg)
{
    safestr_free_fn(ptr, __FILE__, __LINE__);
}

static void
bake_cookie(void)
{
#ifdef WIN32
    HCRYPTPROV  c;

    if (!CryptAcquireContext(&c, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) 
        XXL_THROW_ERROR(SAFESTR_ERROR_PRNG_FAILURE, NULL);
    do
    {
        if (!CryptGenRandom(c, sizeof(safestr_cookie), (BYTE *)&safestr_cookie))
        {
            CryptReleaseContext(c, 0);
            XXL_THROW_ERROR(SAFESTR_ERROR_PRNG_FAILURE, NULL);
        }
    } while (!safestr_cookie);
    CryptReleaseContext(c, 0);
#else
    int fd;

    if ((fd = open("/dev/urandom", O_RDONLY)) == -1)
        XXL_THROW_ERROR(SAFESTR_ERROR_PRNG_FAILURE, NULL);
    do
    {
        read(fd, &safestr_cookie, sizeof(safestr_cookie));
    } while (!safestr_cookie);
    close(fd);
#endif
}

static u_int32_t
get_cookie(void)
{
    if (!safestr_cookie)
        bake_cookie();
    return safestr_cookie;
}

static safestr_t *
charlist(isafestr_t str, const char *file, unsigned int lineno)
{
    safestr_t   *ret;
    u_int32_t   i, size;
    isafestr_t  istr;

    /* Assets saved in this function will be saved within the context of the
     * caller: safestr_split()
     */

    size = sizeof(safestr_t) * (str->hdr.length + 1);
    ret = (safestr_t *)safestr_malloc(size, XXL_ASSET_PROMOTE, file, lineno);

    for (i = 0;  i < str->hdr.length;  i++)
    {
        ret[i] = safestr_do_alloc(1, (str->hdr.flags & SAFESTR_TRUSTED), file, lineno);
        istr   = (isafestr_t)((char *)ret[i] - sizeof(small_isafestr_t));
        XXL_ASSET_SAVE(istr, free_isafestr_asset, NULL, XXL_ASSET_PROMOTE);
        istr->hdr.length = 1;
        istr->str[0] = str->str[i];
        istr->str[1] = '\0';
    }
    ret[str->hdr.length] = NULL;
    return ret;
}

/* ------------------------------------------------------------------------- */

void *
safestr_malloc(size_t size, xxl_assettype_t type, const char *file, unsigned int lineno)
{
    void    *ptr;

    if (!(ptr = safestr_malloc_fn(size, file, lineno)))
        XXL_THROW_ERROR(SAFESTR_ERROR_OUT_OF_MEMORY, NULL);
    XXL_ASSET_SAVE(ptr, free_void_asset, NULL, type);

    return ptr;
}

void *
safestr_realloc(void *old_ptr, size_t size, const char *file, unsigned int lineno)
{
    void    *new_ptr;

    if (!(new_ptr = safestr_realloc_fn(old_ptr, size, file, lineno)))
        XXL_THROW_ERROR(SAFESTR_ERROR_OUT_OF_MEMORY, NULL);
    XXL_ASSET_UPDATE(old_ptr, new_ptr);

    return new_ptr;
}

isafestr_t
safestr_get(safestr_t s, u_int32_t flags)
{
    isafestr_t  str;

    if (!s)
        XXL_THROW_ERROR(SAFESTR_ERROR_INVALID_PARAMETER, NULL);
    str = (isafestr_t)((char *)s - sizeof(small_isafestr_t));
    if (str->hdr.cookie != safestr_cookie)
        XXL_THROW_ERROR(SAFESTR_ERROR_BAD_ADDRESS, NULL);
    if ((flags & SAFESTR_GET_WRITABLE) && (str->hdr.flags & SAFESTR_IMMUTABLE))
        XXL_THROW_ERROR(SAFESTR_ERROR_IMMUTABLE_STRING, s);
    if ((flags & SAFESTR_GET_WRITABLE) && (REF_COUNT(str) > 1))
        XXL_THROW_ERROR(SAFESTR_ERROR_IMMUTABLE_STRING, s);
    if (REF_COUNT(str) == 0xFFFFFFFF)
        XXL_THROW_ERROR(SAFESTR_ERROR_TOO_MANY_REFERENCES, s);
    str->hdr.flags |= SAFESTR_ORIGINAL;
    INC_REF_COUNT(str);
    XXL_ASSET_SAVE(str, free_isafestr_asset, NULL, XXL_ASSET_TEMPORARY);
    return str;
}

isafestr_t
safestr_resize(isafestr_t str, u_int32_t length)
{
    u_int32_t   size;
    isafestr_t  new_str;

    /* neither length nor str->hdr.size consider null-terminator */
    if (length <= str->hdr.size)
    {
        safestr_memzero(str->str + length, str->hdr.size - length);
        str->hdr.length = length;
        return str;
    }
    if (length + 1 > safestr_maxlength)
        XXL_THROW_ERROR(SAFESTR_ERROR_STRING_TOO_LONG, NULL);

    size = SAFESTR_ROUND(sizeof(small_isafestr_t) + length + 1);
    new_str = (isafestr_t)safestr_malloc(size, XXL_ASSET_PERMANENT, __FILE__, __LINE__);
    new_str->hdr.size   = size - sizeof(small_isafestr_t) - 1;
    new_str->hdr.length = length;
    new_str->hdr.flags  = str->hdr.flags & ~SAFESTR_ORIGINAL;
    new_str->hdr.refs   = str->hdr.refs;
    new_str->hdr.cookie = str->hdr.cookie;
    memcpy(new_str->str, str->str, str->hdr.length + 1);
    str->hdr.flags |= SAFESTR_RESIZED;

    XXL_ASSET_SAVE(new_str, free_isafestr_asset, NULL, XXL_ASSET_TEMPORARY);
    return new_str;
}

safestr_t
safestr_complete(isafestr_t iold, isafestr_t inew)
{
    u_int32_t   newsize;
    safestr_t   new_safestr, old_safestr;

    if (iold != inew)
    {
        newsize = inew->hdr.size + sizeof(small_isafestr_t) + 1;
        old_safestr = (safestr_t)iold->str;
        iold = (isafestr_t)safestr_realloc(iold, newsize, __FILE__, __LINE__);
        new_safestr = (safestr_t)iold->str;
        memcpy(iold, inew, newsize);

        iold->hdr.flags &= ~(SAFESTR_ORIGINAL | SAFESTR_RESIZED);
        inew->hdr.flags |= (SAFESTR_ORIGINAL | SAFESTR_RESIZED);

        /* Now, the original exposed pointer may still be on the asset stack
         * somewhere, so we need to update that as well (note that the call to
         * safestr_realloc() takes care of the base isafestr_t pointer for us.
         */
        XXL_ASSET_UPDATE(old_safestr, new_safestr);
    }

    return (safestr_t)iold->str;
}

/* ------------------------------------------------------------------------- */

safestr_t
safestr_do_alloc(u_int32_t length, u_int32_t flags, const char *file, unsigned int lineno)
{
    u_int32_t       size;
    isafestr_t      str;
    xxl_assettype_t asset;

    /* Is the length requested too big? */
    if (length + 1 > safestr_maxlength)
        XXL_THROW_ERROR(SAFESTR_ERROR_STRING_TOO_LONG, NULL);

    size   = SAFESTR_ROUND(sizeof(small_isafestr_t) + length + 1);
    asset  = map_asset(flags);
    flags &= (SAFESTR_TEMPORARY | SAFESTR_IMMUTABLE | SAFESTR_TRUSTED);

    str = (isafestr_t)safestr_malloc(size, XXL_ASSET_PERMANENT, file, lineno);
    str->hdr.size   = size - sizeof(small_isafestr_t) - 1;
    str->hdr.length = 0;
    str->hdr.flags  = flags;
    str->hdr.refs   = 1;
    str->hdr.cookie = get_cookie();
    str->str[0]     = 0;

    XXL_ASSET_SAVE(str->str, safestr_cleanup_asset, NULL, asset);
    return (safestr_t)str->str;
}

char
safestr_charat(safestr_t s, u_int32_t i)
{
    char        result;
    isafestr_t  str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);
        if (i >= str->hdr.length)
            XXL_THROW_ERROR(SAFESTR_ERROR_INDEX_OUT_OF_RANGE, NULL);
        result = str->str[i];
    }
    XXL_ASSET_BLOCK_END;

    return result;
}

void
safestr_cleanup_asset(void *ptr, void *arg)
{
    isafestr_t  istr;

    istr = (isafestr_t)((char *)ptr - sizeof(small_isafestr_t));
    if (istr->hdr.cookie != safestr_cookie)
        XXL_THROW_ERROR(SAFESTR_ERROR_BAD_ADDRESS, NULL);
    if (REF_COUNT(istr) == 0xFFFFFFFF)
        XXL_THROW_ERROR(SAFESTR_ERROR_TOO_MANY_REFERENCES, istr);
    istr->hdr.flags |= SAFESTR_ORIGINAL;
    free_isafestr_asset(istr, NULL);
}

safestr_t
safestr_do_clone(safestr_t s, u_int32_t flags, const char *file, unsigned int lineno)
{
    u_int32_t       size;
    isafestr_t      clone, str;
    xxl_assettype_t asset;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);

        /* Taint flag inheritance is independent of flags.  Can't pass taint by
         * calling _rw, because we have no need to check immutable.
         */
        asset  = map_asset(flags);
        flags &= (SAFESTR_TEMPORARY | SAFESTR_IMMUTABLE);
        flags |= (str->hdr.flags & SAFESTR_TRUSTED);

        size = SAFESTR_ROUND(sizeof(small_isafestr_t) + str->hdr.length + 1);
        clone = (isafestr_t)safestr_malloc(size, XXL_ASSET_PERMANENT, file, lineno);
        clone->hdr.size   = size - sizeof(small_isafestr_t) - 1;
        clone->hdr.length = str->hdr.length;
        clone->hdr.flags  = flags;
        clone->hdr.refs   = 1;
        clone->hdr.cookie = get_cookie();
        memcpy(clone->str, str->str, str->hdr.length + 1);
    }
    XXL_ASSET_BLOCK_END;

    XXL_ASSET_SAVE(clone->str, safestr_cleanup_asset, NULL, asset);
    return (safestr_t)clone->str;
}

int
safestr_compare(safestr_t str1, safestr_t str2, u_int32_t flags, ...)
{
    int             result;
    va_list         ap;
    u_int32_t       length = (u_int32_t)-1;
    isafestr_t      istr1, istr2;
    unsigned char   *map;

    XXL_ASSET_BLOCK_BEGIN
    {
        if (str1 == str2)
        {
            istr1  = safestr_get(str1, SAFESTR_GET_READONLY);
            result = 0;
        }
        else
        {
            if (flags & SAFESTR_COMPARE_LIMIT)
            {
                va_start(ap, flags);
                length = va_arg(ap, u_int32_t);
                va_end(ap);
            }

            istr1  = safestr_get(str1, SAFESTR_GET_READONLY);
            istr2  = safestr_get(str2, SAFESTR_GET_READONLY);
            map    = ((flags & SAFESTR_COMPARE_NOCASE) ? safestr_casemap_lower : safestr_casemap_none);
            result = compare_strings(istr1, istr2, map, length);
        }
    }
    XXL_ASSET_BLOCK_END;

    return result;
}

void
safestr_concatenate(safestr_t *dst, safestr_t s, u_int32_t flags, ...)
{
    va_list     ap;
    u_int32_t   dst_length, src_length, tmp_length;
    isafestr_t  idst, iorig, isrc;

    XXL_ASSET_BLOCK_BEGIN
    {
        isrc = safestr_get(s, SAFESTR_GET_READONLY);
        idst = iorig = safestr_get(*dst, SAFESTR_GET_WRITABLE);

        dst_length = idst->hdr.length;
        src_length = isrc->hdr.length;
        if (flags & SAFESTR_COPY_LIMIT)
        {
            /* SAFESTR_COPY_LIMIT specifies the maximum length of the resulting
             * string, so we need to subtract the value from the current length
             * to get the max.
             */
            va_start(ap, flags);
            tmp_length = va_arg(ap, u_int32_t);
            va_end(ap);
            src_length = (tmp_length < src_length ? 0 : tmp_length - src_length);
        }

        if (src_length > 0)
        {
            idst = safestr_resize(idst, dst_length + src_length);
            memcpy(idst->str + dst_length, isrc->str, src_length);
            *(idst->str + idst->hdr.length) = 0;
            if (!(isrc->hdr.flags & SAFESTR_TRUSTED))
                idst->hdr.flags &= ~SAFESTR_TRUSTED;
            *dst = safestr_complete(iorig, idst);
        }
    }
    XXL_ASSET_BLOCK_END;
}

safestr_t *
safestr_do_convertarray(char **arr, u_int32_t flags, const char *file, unsigned int lineno)
{
    int         c, i;
    safestr_t   *res;
    isafestr_t  str;

    XXL_ASSET_BLOCK_BEGIN
    {
        for (c = 0;  arr[c];  c++);
        res = (safestr_t *)safestr_malloc(sizeof(safestr_t) * (c + 1), XXL_ASSET_PROMOTE, file, lineno);

        for (i = 0;  arr[i];  i++)
        {
            res[i] = safestr_do_create(arr[i], flags, file, lineno);
            str = (isafestr_t)((char *)res[i] - sizeof(small_isafestr_t));
            XXL_ASSET_SAVE(str, free_isafestr_asset, NULL, XXL_ASSET_PROMOTE);
        }
        res[i] = NULL;
    }
    XXL_ASSET_BLOCK_END;

    return res;
}

safestr_t
safestr_do_create(char *s, u_int32_t flags, const char *file, unsigned int lineno)
{
    safestr_t   str;
    u_int32_t   length;
    isafestr_t  istr;

#ifndef WIN32
    length = strlen(s);
#else
    length = lstrlenA(s);
#endif
    str = safestr_do_alloc(length, flags, file, lineno);
    memcpy((char *)str, s, length + 1);
    istr = (isafestr_t)((char *)str - sizeof(small_isafestr_t));
    istr->hdr.length = length;
    return str;
}

void
safestr_delete(safestr_t *s, u_int32_t pos, u_int32_t count)
{
    isafestr_t  str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(*s, SAFESTR_GET_WRITABLE);

        if (pos < str->hdr.length)
        {
            if (pos + count >= str->hdr.length)
            {
                str->hdr.length = pos;
                *(str->str + str->hdr.length) = 0;
            }
            else
            {
                str->hdr.length -= count;
                memmove(str->str + pos, str->str + pos + count, 
                        str->hdr.length - pos + 1);
            }
        }
        *s = (safestr_t)str->str;
    }
    XXL_ASSET_BLOCK_END;
}

void
safestr_duplicate(safestr_t *dst, safestr_t src, u_int32_t flags, ...)
{
    va_list     ap;
    u_int32_t   length;
    isafestr_t  idst, iorig, isrc;

    XXL_ASSET_BLOCK_BEGIN
    {
        isrc = safestr_get(src, SAFESTR_GET_READONLY);
        idst = iorig = safestr_get(*dst, SAFESTR_GET_WRITABLE);

        if (!(flags & SAFESTR_COPY_LIMIT))
            length = isrc->hdr.length;
        else
        {
            va_start(ap, flags);
            length = va_arg(ap, u_int32_t);
            va_end(ap);
            length = SAFESTR_MIN(length, isrc->hdr.length);
        }

        idst = safestr_resize(idst, length);
        memcpy(idst->str, isrc->str, length);
        *(idst->str + length) = 0;
        if (!(isrc->hdr.flags & SAFESTR_TRUSTED))
            idst->hdr.flags &= ~SAFESTR_TRUSTED;
        *dst = safestr_complete(iorig, idst);
    }
    XXL_ASSET_BLOCK_END;
}

int
safestr_endswith(safestr_t str, safestr_t substr)
{
    int         match = 0;
    isafestr_t  istr, isubstr;

    XXL_ASSET_BLOCK_BEGIN
    {
        istr    = safestr_get(str, SAFESTR_GET_READONLY);
        isubstr = safestr_get(substr, SAFESTR_GET_READONLY);

        if (istr->hdr.length >= isubstr->hdr.length &&
            !memcmp(istr->str + istr->hdr.length - isubstr->hdr.length, isubstr->str, isubstr->hdr.length))
        {
            match = 1;
        }
    }
    XXL_ASSET_BLOCK_END;

    return match;
}

int
safestr_equal(safestr_t str1, safestr_t str2, u_int32_t flags, ...)
{
    int             result;
    va_list         ap;
    u_int32_t       length = (u_int32_t)-1;
    isafestr_t      istr1, istr2;
    unsigned char   *map;

    XXL_ASSET_BLOCK_BEGIN
    {
        if (str1 == str2)
        {
            istr1  = safestr_get(str1, SAFESTR_GET_READONLY);
            result = 1;
        }
        else
        {
            if (flags & SAFESTR_COMPARE_LIMIT)
            {
                va_start(ap, flags);
                length = va_arg(ap, u_int32_t);
                va_end(ap);
            }

            istr1  = safestr_get(str1, SAFESTR_GET_READONLY);
            istr2  = safestr_get(str2, SAFESTR_GET_READONLY);
            map    = ((flags & SAFESTR_COMPARE_NOCASE) ? safestr_casemap_lower : safestr_casemap_none);
            result = (compare_strings(istr1, istr2, map, length) == 0);
        }
    }
    XXL_ASSET_BLOCK_END;

    return result;
}

void
safestr_free(safestr_t s)
{
    isafestr_t str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);
        DEC_REF_COUNT(str);
    }
    XXL_ASSET_BLOCK_END;
}

void
safestr_freelist(safestr_t *list)
{
    u_int32_t   i;
    isafestr_t  str;

    for (i = 0;  list[i];  i++)
    {
        XXL_ASSET_BLOCK_BEGIN
        {
            str = safestr_get(list[i], SAFESTR_GET_READONLY);
            DEC_REF_COUNT(str);
        }
        XXL_ASSET_BLOCK_END;
    }
    safestr_free_fn(list, __FILE__, __LINE__);
}

void
safestr_insert(safestr_t *dst, u_int32_t pos, safestr_t s)
{
    u_int32_t   old_length;
    isafestr_t  idst, iorig, isrc;

    XXL_ASSET_BLOCK_BEGIN
    {
        isrc = safestr_get(s, SAFESTR_GET_READONLY);
        idst = iorig = safestr_get(*dst, SAFESTR_GET_WRITABLE);

        if (pos > idst->hdr.length)
            XXL_THROW_ERROR(SAFESTR_ERROR_INDEX_OUT_OF_RANGE, NULL);
        old_length = idst->hdr.length;
        idst = safestr_resize(idst, idst->hdr.length + isrc->hdr.length);
        memmove(idst->str + pos + isrc->hdr.length, idst->str + pos, old_length - pos + 1);
        memcpy(idst->str + pos, isrc->str, isrc->hdr.length);
        if (!isrc->hdr.flags & SAFESTR_TRUSTED)
            idst->hdr.flags &= ~SAFESTR_TRUSTED;
        *dst = safestr_complete(iorig, idst);
    }
    XXL_ASSET_BLOCK_END;
}

safestr_t
safestr_do_join(safestr_t *s, safestr_t joiner, const char *file, unsigned int lineno)
{
    char        *outp;
    safestr_t   ret;
    u_int32_t   i, count, len, trust = SAFESTR_TRUSTED;
    isafestr_t  ijoiner, istr, *strs;

    XXL_ASSET_BLOCK_BEGIN
    {
        ijoiner = safestr_get(joiner, SAFESTR_GET_READONLY);
        trust  &= ijoiner->hdr.flags;

        for (count = 0;  s[count];  count++);
        if (!count)
            ret = safestr_do_alloc(0, SAFESTR_TRUSTED, file, lineno);
        else
        {
            strs = (isafestr_t *)safestr_malloc(sizeof(isafestr_t) * count, XXL_ASSET_TEMPORARY, __FILE__, __LINE__);

            for (i = len = 0;  i < count;  i++)
            {
                strs[i] = safestr_get(s[i], SAFESTR_GET_READONLY);
                len    += strs[i]->hdr.length;
                trust  &= strs[i]->hdr.flags;
            }
            len += (ijoiner->hdr.length * (count - 1));
            ret  = safestr_do_alloc(len, trust, file, lineno);
            istr = (isafestr_t)((char *)ret - sizeof(small_isafestr_t));
            istr->hdr.length = len;
            istr->str[len] = '\0';
            memcpy(istr->str, strs[0]->str, strs[0]->hdr.length);
            for (outp = istr->str + strs[0]->hdr.length, i = 1;  i < count;  i++)
            {
                memcpy(outp, ijoiner->str, ijoiner->hdr.length);
                memcpy(outp + ijoiner->hdr.length, strs[i]->str, strs[i]->hdr.length);
                outp += (ijoiner->hdr.length + strs[i]->hdr.length);
            }
        }
    }
    XXL_ASSET_BLOCK_END;

    return ret;
}

u_int32_t
safestr_length(safestr_t s)
{
    u_int32_t   length;
    isafestr_t  str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);
        length = str->hdr.length;
    }
    XXL_ASSET_BLOCK_END;

    return length;
}

void 
safestr_memzero(volatile void *str, u_int32_t len)
{
    volatile char   *buf;

    for (buf = (volatile char *)str;  len;  buf[--len] = 0);
}

safestr_t
safestr_reference(safestr_t s)
{
    isafestr_t  str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);
        INC_REF_COUNT(str);
    }
    XXL_ASSET_BLOCK_END;

    return s;
}

void
safestr_replace(safestr_t *str, safestr_t oldp, safestr_t newp)
{
    char        *c;
    u_int32_t   new_len, str_len, zero_len = 0;
    isafestr_t  inewp, ioldp, iorig, istr;

    XXL_ASSET_BLOCK_BEGIN
    {
        ioldp = safestr_get(oldp, SAFESTR_GET_READONLY);
        istr  = iorig = safestr_get(*str, SAFESTR_GET_WRITABLE);

        if (istr->hdr.length >= ioldp->hdr.length)
        {
            inewp   = safestr_get(newp, SAFESTR_GET_READONLY);
            new_len = 0;
            str_len = istr->hdr.length;
            for (c = istr->str;  c < istr->str + str_len - ioldp->hdr.length + 1;  c++)
            {
                if (memcmp(c, ioldp->str, ioldp->hdr.length))
                {
                    new_len++;
                    continue;
                }
                new_len += inewp->hdr.length;
                c += (ioldp->hdr.length) - 1;
            }
            if (c < istr->str + str_len)
                new_len += (ioldp->hdr.length - 1);

            /* Note that we cannot use safestr_resize() here if the new length
             * is less than the old length, because the string will be pre-
             * maturely zeroed, resulting in a loss of data.  Instead, we need
             * to do the zero after we move stuff around.
             */
            if (new_len > str_len)
                istr  = safestr_resize(istr, new_len);
            else
            {
                zero_len = istr->hdr.length - new_len;
                istr->hdr.length = new_len;
            }
            if (!(inewp->hdr.flags & SAFESTR_TRUSTED))
                istr->hdr.flags &= ~SAFESTR_TRUSTED;

            for (c = istr->str;  c < istr->str + str_len - ioldp->hdr.length + 1;  c++)
            {
                if (memcmp(c, ioldp->str, ioldp->hdr.length))
                    continue;
                memmove(c + inewp->hdr.length, c + ioldp->hdr.length,
                        (str_len - (c - istr->str) - ioldp->hdr.length) + 1);
                memcpy(c, inewp->str, inewp->hdr.length);
                if (inewp->hdr.length > ioldp->hdr.length)
                    str_len += (inewp->hdr.length - ioldp->hdr.length);
                else
                    str_len -= (ioldp->hdr.length - inewp->hdr.length);
                c += (inewp->hdr.length - 1);
            }
            if (zero_len > 0)
                safestr_memzero(istr->str + new_len, zero_len);
        }

        *str = safestr_complete(iorig, istr);
    }
    XXL_ASSET_BLOCK_END;
}

u_int32_t
safestr_search(safestr_t s, safestr_t sub, u_int32_t flags, ...)
{
    int             match;
    va_list         ap;
    u_int32_t       from = 0, fromchar = 0, i, n = 1, result, sublength = 0;
    isafestr_t      str, substr = NULL;
    unsigned char   findchar = 0, *map, *uptr, *usub;
    
    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);
        if (!(flags & SAFESTR_FIND_CHARACTER)) {
            substr = safestr_get(sub, SAFESTR_GET_READONLY);
            sublength = substr->hdr.length;
        }

        va_start(ap, flags);
        if (flags & SAFESTR_FIND_FROMCHAR)
            fromchar = va_arg(ap, u_int32_t);
        if (flags & SAFESTR_FIND_FROMNTH)
            from = va_arg(ap, u_int32_t);
        if (flags & SAFESTR_FIND_NTH)
            n = va_arg(ap, u_int32_t);
        if (flags & SAFESTR_FIND_CHARACTER) {
            findchar = (unsigned char)va_arg(ap, int);
            sublength = 1;
        }
        va_end(ap);

        n += from;
        if (n < 1 || fromchar >= str->hdr.length || sublength > str->hdr.length)
            result = SAFESTR_ERROR_NOTFOUND;
        else
        {
            map  = ((flags & SAFESTR_FIND_NOMATCHCASE) ? safestr_casemap_lower : safestr_casemap_none);
            usub = ((flags & SAFESTR_FIND_CHARACTER) ? &findchar : (unsigned char *)substr->str);
            if (flags & SAFESTR_FIND_REVERSE)
            {
                for (uptr = (unsigned char *)str->str + str->hdr.length - fromchar - sublength;
                     uptr >= (unsigned char *)str->str;
                     uptr--)
                {
                    match = 1;
                    for (i = 0;  i < sublength;  i++)
                    {
                        if (map[uptr[i]] != map[usub[i]])
                        {
                            match = 0;
                            break;
                        }
                    }
                    if (match && !--n)
                        break;
                }
                result = (uptr < (unsigned char *)str->str ?
                          SAFESTR_ERROR_NOTFOUND : (u_int32_t)(uptr - (unsigned char *)str->str));
            }
            else
            {
                for (uptr = (unsigned char *)str->str + fromchar;
                     uptr <= (unsigned char *)str->str + str->hdr.length - sublength;
                     uptr++)
                {
                    match = 1;
                    for (i = 0;  i < sublength;  i++)
                    {
                        if (map[uptr[i]] != map[usub[i]])
                        {
                            match = 0;
                            break;
                        }
                    }
                    if (match && !--n)
                        break;
                }
                result = (uptr > (unsigned char *)str->str + str->hdr.length - sublength ?
                          SAFESTR_ERROR_NOTFOUND : (u_int32_t)(uptr - (unsigned char *)str->str));
            }
        }
    }
    XXL_ASSET_BLOCK_END;

    return result;
}

void
safestr_setcharat(safestr_t s, u_int32_t i, char c, int trust)
{
    isafestr_t  str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_WRITABLE);
        if (i >= str->hdr.length)
            XXL_THROW_ERROR(SAFESTR_ERROR_INDEX_OUT_OF_RANGE, NULL);
        if (!trust)
            str->hdr.flags &= ~SAFESTR_TRUSTED;
        str->str[i] = c;
    }
    XXL_ASSET_BLOCK_END;
}

void
safestr_setmemfns(safestr_malloc_t malloc_fn, safestr_realloc_t realloc_fn,
                  safestr_free_t free_fn)
{
    safestr_malloc_fn  = (malloc_fn  ? malloc_fn  : safestr_default_malloc);
    safestr_realloc_fn = (realloc_fn ? realloc_fn : safestr_default_realloc);
    safestr_free_fn    = (free_fn    ? free_fn    : safestr_default_free);
}

safestr_t
safestr_do_slice(safestr_t s, u_int32_t start, u_int32_t end, const char *file, unsigned int lineno)
{
    u_int32_t   length = 0, size;
    isafestr_t  new_str, str;

    XXL_ASSET_BLOCK_BEGIN
    {
        str = safestr_get(s, SAFESTR_GET_READONLY);
        if (start < str->hdr.length)
        {
            length  = end - start;
            length  = SAFESTR_MIN(str->hdr.length - start, length);
        }

        size = SAFESTR_ROUND(sizeof(small_isafestr_t) + length + 1);
        new_str = (isafestr_t)safestr_malloc(size, XXL_ASSET_PERMANENT, file, lineno);
        new_str->hdr.size    = size - sizeof(small_isafestr_t) - 1;
        new_str->hdr.length  = length;
        new_str->hdr.flags   = (str->hdr.flags & SAFESTR_TRUSTED);
        new_str->hdr.refs    = 1;
        new_str->hdr.cookie  = get_cookie();
        new_str->str[length] = 0;
        memcpy(new_str->str, str->str + start, length);
    }
    XXL_ASSET_BLOCK_END;

    return (safestr_t)new_str->str;
}

safestr_t *
safestr_do_split(safestr_t s, safestr_t sub, const char *file, unsigned int lineno)
{
    char        *c, *cursor;
    safestr_t   *ret;
    u_int32_t   count;
    isafestr_t  istr, str, substr;

    XXL_ASSET_BLOCK_BEGIN
    {
        str    = safestr_get(s, SAFESTR_GET_READONLY);
        substr = safestr_get(sub, SAFESTR_GET_READONLY);

        if (!substr->hdr.length)
            ret = charlist(str, file, lineno);
        else if (substr->hdr.length > str->hdr.length)
        {
            ret = (safestr_t *)safestr_malloc(sizeof(safestr_t) * 2, XXL_ASSET_PROMOTE, file, lineno);
            ret[0] = safestr_do_clone(s, (str->hdr.flags & SAFESTR_TRUSTED), file, lineno);
            ret[1] = NULL;
        }
        else
        {
            /* Figure out how many array elements are needed */
            count = 1;
            for (c = str->str;  *(c + substr->hdr.length - 1);  c++)
                if (!memcmp(c, substr->str, substr->hdr.length))
                {
                    count++;
                    c += (substr->hdr.length - 1);
                }

            ret = (safestr_t *)safestr_malloc(sizeof(safestr_t) * (count + 1), XXL_ASSET_PROMOTE, file, lineno);

            count = 0;
            for (c = cursor = str->str;  *(c + substr->hdr.length - 1);  c++)
            {
                if (!memcmp(c, substr->str, substr->hdr.length))
                {
                    ret[count] = safestr_do_alloc(c - cursor, (str->hdr.flags & SAFESTR_TRUSTED), file, lineno);
                    istr = (isafestr_t)((char *)ret[count] - sizeof(small_isafestr_t));
                    XXL_ASSET_SAVE(istr, free_isafestr_asset, NULL, XXL_ASSET_PROMOTE);
                    istr->hdr.length = c - cursor;
                    memcpy(istr->str, cursor, istr->hdr.length);
                    istr->str[istr->hdr.length] = '\0';
                    cursor = c + substr->hdr.length;
                    c += (substr->hdr.length - 1);
                    count++;
                }
            }
            if (*c)
                c += (substr->hdr.length - 1);
            ret[count] = safestr_do_alloc(c - cursor, (str->hdr.flags & SAFESTR_TRUSTED), file, lineno);
            istr = (isafestr_t)((char *)ret[count] - sizeof(small_isafestr_t));
            XXL_ASSET_SAVE(istr, free_isafestr_asset, NULL, XXL_ASSET_PROMOTE);
            istr->hdr.length = c - cursor;
            memcpy(istr->str, cursor, istr->hdr.length);
            istr->str[istr->hdr.length] = '\0';
            ret[++count] = NULL;
        }
    }
    XXL_ASSET_BLOCK_END;

    return ret;
}

int
safestr_startswith(safestr_t str, safestr_t substr)
{
    int         match = 0;
    isafestr_t  istr, isubstr;

    XXL_ASSET_BLOCK_BEGIN
    {
        istr    = safestr_get(str, SAFESTR_GET_READONLY);
        isubstr = safestr_get(substr, SAFESTR_GET_READONLY);

        if (istr->hdr.length >= isubstr->hdr.length &&
            !memcmp(istr->str, isubstr->str, isubstr->hdr.length))
        {
            match = 1;
        }
    }
    XXL_ASSET_BLOCK_END;

    return match;
}

char *
safestr_do_strdup(char *s, const char *file, unsigned int lineno)
{
    char        *new_s;
    u_int32_t   len;

#ifndef WIN32
    len = strlen(s) + 1;
#else
    len = lstrlenA(s) + 1;
#endif
    new_s = (char *)safestr_malloc(len, XXL_ASSET_PERMANENT, file, lineno);
    memcpy(new_s, s, len);
    return new_s;
}

void
safestr_truncate(safestr_t *s, u_int32_t length)
{
    u_int32_t   old_length;
    isafestr_t  iorig, istr;

    XXL_ASSET_BLOCK_BEGIN
    {
        istr = iorig = safestr_get(*s, SAFESTR_GET_WRITABLE);
        old_length = istr->hdr.length;
        istr = safestr_resize(istr, length);

        if (length > old_length)
            memset(istr->str + old_length, ' ', length - old_length);
        *(istr->str + istr->hdr.length) = 0;
        *s = safestr_complete(iorig, istr);
    }
    XXL_ASSET_BLOCK_END;
}

/* ------------------------------------------------------------------------- */

void
safestr_trust(safestr_t s)
{
    XXL_ASSET_BLOCK_BEGIN
    {
        safestr_get(s, SAFESTR_GET_READONLY)->hdr.flags |= SAFESTR_TRUSTED;
    }
    XXL_ASSET_BLOCK_END;
}

void
safestr_untrust(safestr_t s)
{
    XXL_ASSET_BLOCK_BEGIN
    {
        safestr_get(s, SAFESTR_GET_READONLY)->hdr.flags &= ~SAFESTR_TRUSTED;
    }
    XXL_ASSET_BLOCK_END;
}

int
safestr_istrusted(safestr_t s)
{
    u_int32_t   trusted;

    XXL_ASSET_BLOCK_BEGIN
    {
        trusted = safestr_get(s, SAFESTR_GET_READONLY)->hdr.flags & SAFESTR_TRUSTED;
    }
    XXL_ASSET_BLOCK_END;

    return !!trusted;
}

void 
safestr_makereadonly(safestr_t s)
{
    XXL_ASSET_BLOCK_BEGIN
    {
        safestr_get(s, SAFESTR_GET_READONLY)->hdr.flags |= SAFESTR_IMMUTABLE;
    }
    XXL_ASSET_BLOCK_END;
}

void
safestr_makewritable(safestr_t s)
{
    XXL_ASSET_BLOCK_BEGIN
    {
        safestr_get(s, SAFESTR_GET_READONLY)->hdr.flags &= ~SAFESTR_IMMUTABLE;
    }
    XXL_ASSET_BLOCK_END;
}

int
safestr_isreadonly(safestr_t s)
{
    u_int32_t   immutable;

    XXL_ASSET_BLOCK_BEGIN
    {
        immutable = safestr_get(s, SAFESTR_GET_READONLY)->hdr.flags & SAFESTR_IMMUTABLE;
    }
    XXL_ASSET_BLOCK_END;

    return !!immutable;
}

/* ------------------------------------------------------------------------- */

void *
safestr_default_malloc(size_t nbytes, const char *file, unsigned int lineno)
{
    return malloc(nbytes);
}

void *
safestr_default_realloc(void *ptr, size_t nbytes, const char *file, unsigned int lineno)
{
    return realloc(ptr, nbytes);
}

void
safestr_default_free(void *ptr, const char *file, unsigned int lineno)
{
    free(ptr);
}