String library

string.c

#include "module.h"

// Advances the source string by `count`.
void
string_advance(string *str, sint count)
{
    str->data += count;
    str->count -= count;
}

// Returns zero if both strings are identical and nonzero otherwise.
int
string_cmp(string a, string b)
{
    if (a.count != b.count) {
        return a.count - b.count;
    }

    return memcmp(a.data, b.data, a.count);
}

int
string_casecmp(string a, string b)
{
    uint i;

    if (a.count != b.count) {
        return a.count - b.count;
    }

    for (i = 0; i < a.count; ++i) {
        if (char_tolower(a.data[i]) != char_tolower(b.data[i]))
            return a.data[i] - b.data[i];
    }

    return 0;
}

// Compares a string with a NUL terminated string.
int
string_cmpl(string a, char *b)
{
    string c;
    c.count = strlen(b);
    c.data  = b;

    return string_cmp(a, c);
}

// Compares a string with a NUL terminated string (case insensitive).
int
string_casecmpl(string a, char *b)
{
    string c;
    c.count = strlen(b);
    c.data  = b;

    return string_casecmp(a, c);
}

// Advances the source string and parses a token until any one of the delimiters are
// found. If no delimiter is found, the result is the entire source string. The delimiter
// is consumed, such that neither the source or resulting string contain the first
// instance of the delimiter. Leading whitespace is ignored. If the token starts with a
// quote (") it is parsed until a closing quote is found, delimiter is ignored. Escaping
// quotes is not supported since that would require modifying the original string.
string
string_next_token(string *str, const char *delimiter)
{
    while (str->count != 0 && char_isspace(*str->data)) {
        string_advance(str, 1);
    }

    if (str->count != 0 && *str->data == '"') {
        delimiter = "\"";
        string_advance(str, 1);
    }

    string result;
    result.count = 0;
    result.data  = str->data;

    for (; str->count != 0; string_advance(str, 1), ++result.count) {
        for (uint i = 0; delimiter[i]; ++i) {
            if (*str->data == delimiter[i]) {
                string_advance(str, 1);
                return result;
            }
        }
    }

    return result;
}

// Advances the source string and parses a line ending in \n, \r, or \r\n.
string
string_next_line(string *str)
{
    string result;
    result.count = 0;
    result.data  = str->data;

    for (; str->count != 0; string_advance(str, 1), ++result.count) {
        if (*str->data == '\r') {
            string_advance(str, 1);
            if (str->count != 0 && *str->data == '\n') {
                string_advance(str, 1);
            }
            break;
        }
        if (*str->data == '\n') {
            string_advance(str, 1);
            break;
        }
    }
    return result;
}

// Removes comments from text. Comments start with any one character given in chars.
void
string_strip_comments(string *line, char *chars)
{
    bool quote = false;

    string str  = *line;
    line->count = 0;
    line->data  = str.data;

    for (; str.count != 0; string_advance(&str, 1), ++line->count) {
        if (*str.data == '"')
            quote = !quote;

        if (quote) {
            continue;
        }

        for (uint i = 0; chars[i]; ++i) {
            if (*str.data == chars[i]) {
                return;
            }
        }
    }
}

// Converts text into a struct. One format character is used for each struct member.
//
// The following format characters are accepted:
//
//    b   bool
//    s   null terminated string, must be prefixed with a max count.
//    S   string view into `str.data`
//
//    C   uint8
//    W   uint16
//    D   uint32
//    L   uint32
//    Q   uint64
//
//    c   sint8
//    w   sint16
//    d   sint32
//    l   sint32
//    q   sint64
//
//    f   float
//
//    x   1 byte padding
//
//   ' '  optional spaces
//    ?   indicates parsing the remaining tokens is options [1]
//
// Additionally, a numerical prefix can be combined with any types above for arrays,
// for example:
//
//    struct __attribute((packed)) {
//        char   name[32];   // "32s"
//        string text;       // "S"
//        float  pos[3];     // "3f"
//        int    values[16]; // "16l"
//        uint32 uvalue;     // "L"
//    };
//
// [1]: For example "64s?LL" parses a 64 character string followed by two optional
//      integers. If the optional tokens are not parsed, the remaining bytes in `result`
//      are left unmodified. This is useful for setting default values.
//
// Returns false if either:
//    - The format string is invalid
//    - Parsing would exceed `size`
//    - Parsing failed
//
bool
string_parse_struct(void *result, uint size, char *format, string str, char *delimiter)
{
    static uint8 table[64] = {
    //  @  A  B   C  D  E  F  G  H  I  J  K  L  M  N  O
        0, 0, 0,  1, 4, 0, 0, 0, 0, 4, 0, 0, 4, 0, 0, 0,
    //  P  Q  R   S  T  U  V  W  X  Y  Z
        0, 8, 0, 16, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0,
    //  `  a  b   c  d  e  f  g  h  i  j  k  l  m  n  o
        0, 0, 1,  1, 4, 2, 4, 0, 0, 4, 0, 0, 4, 0, 0, 0,
    //  p  q  r   s  t  u  v  w  x  y  z
        0, 4, 0,  1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0,
    };

    union {
        uint64 ui;
        sint64 si;
        bool   b;
        float  f;
        string s;
    } value;

    uint offset = 0;
    uint8 *bytes = result;
    uint count = 0;
    bool optional = false;

    for (; *format; ++format) {
        char ch = *format;
        void *copy_src = &value.ui;
        uint copy_avail = 0;
        uint copy_size = 0;
        value.ui = 0;

        if (ch >= '0' && ch <= '9') {
            count *= 10;
            count += ch - '0';
            continue;
        }

        if (ch == ' ' && !count)
            continue;         // allow spaces between characters

        if (ch == '?' && !count) {
            optional = true;  // remaining tokens are optional
            continue;
        }

        if (ch < '@' || ch > 'z')
            return false;     // invalid format character

        uint n = table[ch - '@'];

        if (!n)
            return false;     // invalid format character

        if (ch == 'x')
            goto copy_value;  // padding byte

        string tok = string_next_token(&str, delimiter);

        if (!tok.count)
            return optional;  // out of input, not an error if remaining tokens are optional

        switch (ch) {
        case 'b':
            if (tok.data[0] == '1')
                value.ui = 1;
            else if (tok.data[0] == '0')
                value.ui = 0;
            else
                return false; // invalid bool
            break;

        case 'S':
            value.s = tok;    // string will point to source string
            break;

        case 's':
            if (!count)
                return false; // count is required

            // nul terminated string, copy and truncate
            copy_avail = min(count - 1, tok.count);
            copy_src = tok.data;
            break;

        case 'f':
            if (!string_parse_float(&value.f, tok))
                return false;
            break;

        default:
            // integer
            if (ch <= 'Z' && !string_parse_int(&value.si, tok, 0))
                return false;
            else if (ch <= 'z' && !string_parse_int(&value.si, tok, 0))
                return false;
        }

copy_value:

        copy_size = n * max(1, count);

        if (!copy_avail)
            copy_avail = copy_size;

        if (offset + copy_size > size)
            return false;

        memcpy(bytes + offset, copy_src, copy_avail);

        if (copy_avail < copy_size)
            memset(bytes + offset + copy_avail, 0, copy_size - copy_avail);

        offset += copy_size;
        count = 0; // reset number of objects
    }

    return offset == size;
}

// Converts a string to a signed integer. Ignores leading whitespace.
//
// base:
//   If 0, the int base will be determined by the string format: If the string
//   begins with a `0x` it is assumed to be in base 16, if the string begins
//   with a `0` then base 8 is assumed. Otherwise the default is base 10.
bool
string_parse_int(sint64 *result, string str, uint base)
{
    uint64 acc = 0;
    bool neg = false;

    while (str.count && char_isspace(str.data[0])) {
        string_advance(&str, 1);
    }
    if (str.count == 0) goto err;
    if (str.data[0] == '-' || str.data[0] == '+') {
        neg = str.data[0] == '-';
        string_advance(&str, 1);
        if (str.count == 0) goto err;
    }

    if (str.data[0] == '0') {
        if ((base == 0 || base == 16)
                && str.count > 1
                && (str.data[1] == 'x' || str.data[1] == 'X')) {
            base = 16;
            string_advance(&str, 2);
        } else if ((base == 0 || base == 2)
                && str.count > 1
                && (str.data[1] == 'b' || str.data[1] == 'B')) {
            base = 2;
            string_advance(&str, 2);
        } else if (base == 0 || base == 8) {
            base = 8;
            string_advance(&str, 1);
        }
    }
    if (base == 0) base = 10;

    for (; str.count; string_advance(&str, 1)) {
        char c = *str.data;
        if (c >= '0' && c <= '9')
            c -= '0';
        else if (c >= 'a' && c <= 'z')
            c -= ('a' - 10);
        else if (c >= 'A' && c <= 'Z')
            c -= ('A' - 10);
        else
            goto err;

        if ((uint8)c >= base) goto err;

        acc *= base;
        acc += c;
    }

    *result = (sint64)acc;
    if (neg) *result = -(*result);
    return true;
err:
    *result = 0;
    return false;
}

// Converts a string to a float. Ignores leading whitespace.
bool
string_parse_float(float *result, string str)
{
    bool parsed_dot = false;
    bool parsed_e = false;
    bool neg = false;
    float64 num = 0.0;
    sint64 e = 0;
    uint i = 0;

    while (str.count && char_isspace(str.data[0])) {
        string_advance(&str, 1);
    }
    if (str.count == 0) goto err;

    if (str.data[0] == '-' || str.data[0] == '+') {
        neg = str.data[0] == '-';
        string_advance(&str, 1);
        if (str.count == 0) goto err;
    }

    for (; i < str.count; ++i) {
        char c = str.data[i];
        if (c >= '0' && c <= '9') {
            num = num * 10.0 + (c - '0');
        } else if (!parsed_dot && c == '.') {
            parsed_dot = true;
            continue;
        } else if (c == 'e' || c == 'E') {
            parsed_e = true;
            break;
        } else {
            goto err;
        }

        if (parsed_dot) --e;
    }

    if (parsed_e) {
        sint64 e_part;
        if (i + 1 >= str.count) goto err;

        string int_part = (string){str.count - (i + 1), str.data + i + 1};
        if (!string_parse_int(&e_part, int_part, 10)) goto err;
        e += e_part;
    }

    if (e < 0)
        for (; e != 0; ++e) num /= 10;
    else
        for (; e != 0; --e) num *= 10;

    if (neg)
        *result = -num;
    else
        *result = num;

    return true;
err:
    *result = 0.0;
    return false;
}

int
string_atoi(string str)
{
    sint64 result;
    bool valid_int;
    (void)valid_int;

    valid_int = string_parse_int(&result, str, 0);

    assert(valid_int);
    assert(result >= INT_MIN && result <= INT_MAX);

    return (int)result;
}

float
string_atof(string str)
{
    float result;
    bool valid_float;
    (void)valid_float;

    valid_float = string_parse_float(&result, str);
    assert(valid_float);

    return result;
}

// Decodes an RLE sequence.
//
// dst:
//   Destination buffer, at least size*count in size.
//
// size:
//   Size of each object in bytes.
//
// count:
//   Number of objects to read.
uint
string_run_length_decode(void *dst, uint size, uint count, string src)
{
    uint i;
    char copy[32];

    assert(size <= 32);

    if (size > 32)
        return 0;

    for (i = 0; i < count;) {
        if (!src.count)
            break;

        uint8 packet = *src.data;
        string_advance(&src, 1);

        int length = (packet & 0x7F) + 1;
        i += length;

        if (packet & 0x80) {
            // run-length packet
            if (src.count < size)
                break;

            memcpy(&copy, src.data, size);
            string_advance(&src, size);

            for (; length; dst += size, length--)
                memcpy(dst, copy, size);
        } else {
            // Raw packet
            uint packetsize = size * length;
            if (src.count < packetsize)
                break;

            memcpy(dst, src.data, packetsize);
            string_advance(&src, packetsize);
            dst += packetsize;
        }
    }

    return i;
}

bool
string_compress_encode_length(string *dst, uint length)
{
    for (; length >= 0xFF; length -= 0xFF) {
        if (!dst->count)
            return false;

        *dst->data = 0xFF;
        string_advance(dst, 1);
    }

    if (!dst->count)
        return false;

    *dst->data = length;
    string_advance(dst, 1);

    return true;
}

uint
string_compress_decode_length(string *src)
{
    uint length = 0;
    uint8 ch;

    do {
        if (!src->count)
            return 0;

        ch = *src->data;
        length += ch;
        string_advance(src, 1);
    } while (ch == 0xFF);

    return length;
}

// Returns the worst-case maximum size of a compressed block.
uint
string_compress_bounds(uint count)
{
    return count + count / 255 + 16;
}

// LZ77 compression encoded as LZ4.
//
// dst:
//   Must be at least string_compress_bounds(src.count) in size.
//
// Returns the compressed size, or 0 on error.
uint
string_compress(string dst, string src)
{
    enum {
        MIN_MATCH       = 4,
        MIN_TAIL        = 12,
        MAX_MATCH       = 0xFFFF,
        MAX_OFFSET      = 0xFFFF,
        LOG2_TABLE_SIZE = 12,
    };

    static uint table[1 << LOG2_TABLE_SIZE];

    uint i = 0;
    char *dst_base = dst.data;

    if (src.count < MIN_TAIL)
        goto last_literal; // too small to compress

    memset(table, 0xFF, sizeof table);
    uint limit = src.count - MIN_TAIL;

    while (i < limit) {
        uint literal = i;
        uint match = 0;

        // find the start of a match
        for (; i < limit; ++i) {
            uint32 h;
            memcpy(&h, &src.data[i], sizeof h);
            h = (h * 2654435761u) >> (32 - LOG2_TABLE_SIZE);
            match = table[h];
            table[h] = i;

            if (i > match && (i - match) <= MAX_OFFSET
                    && !memcmp(src.data + i, src.data + match, MIN_MATCH))
            {
                // found the start of a match
                break;
            }
        }

        if (i == limit) {
            i = literal;
            goto last_literal;
        }

        assert(i >= match);
        uint literal_count = i - literal;
        uint16 match_offset = i - match;

        // find max match length
        i += MIN_MATCH;
        uint match_count = 0;

        while (src.data[i] == src.data[match + match_count + MIN_MATCH]
                && match_count < MAX_MATCH
                && i < limit)
        {
            i += 1;
            match_count += 1;
        }

        // emit token
        char *token = dst.data;
        if (!dst.count)
            return 0;

        string_advance(&dst, 1);

        // emit literal length
        if (literal_count < 0xF) {
            *token = literal_count << 4;
        } else {
            *token = 0xF0;
            if (!string_compress_encode_length(&dst, literal_count - 0xF))
                return 0;
        }

        if (dst.count < literal_count)
            return 0;

        memcpy(dst.data, &src.data[literal], literal_count);
        string_advance(&dst, literal_count);

        // emit match offset
        if (dst.count < sizeof(uint16))
            return 0;

        assert(match_offset <= MAX_OFFSET);
        memcpy(dst.data, &match_offset, sizeof(uint16));
        string_advance(&dst, sizeof(uint16));

        // emit match length
        if (match_count < 0xF) {
            *token |= match_count;
        } else {
            *token |= 0x0F;
            if (!string_compress_encode_length(&dst, match_count - 0xF))
                return 0;
        }
    }

last_literal:

    if (i < src.count) {
        if (!dst.count)
            return 0;

        char *token = dst.data;
        string_advance(&dst, 1);

        uint literal_count = src.count - i;

        // last literal
        if (literal_count < 0xF) {
            *token = literal_count << 4;
        } else {
            *token = 0xF0;
            if (!string_compress_encode_length(&dst, literal_count - 0xF))
                return 0;
        }

        if (dst.count < literal_count)
            return 0;

        memcpy(dst.data, &src.data[i], literal_count);
        string_advance(&dst, literal_count);
    }

    return dst.data - dst_base;
}


// Decodes an LZ4 block.
uint
string_decompress(string dst, string src)
{
    uint ip = 0;

    while (src.count) {
        // decode token
        uint8 token = *src.data;
        string_advance(&src, 1);

        uint literal_length = token >> 4;
        uint match_length = token & 0xF;

        // literal length
        if (literal_length == 0xF)
            literal_length += string_compress_decode_length(&src);

        // copy literal
        if (literal_length > src.count || ip + literal_length > dst.count)
            return 0;

        memcpy(&dst.data[ip], src.data, literal_length);
        string_advance(&src, literal_length);
        ip += literal_length;

        if (!src.count)
            break;

        // match offset
        if (src.count < sizeof(uint16))
            return 0;

        uint16 match_offset;
        memcpy(&match_offset, src.data, sizeof match_offset);
        string_advance(&src, sizeof match_offset);

        // match length
        if (match_length == 0xF)
            match_length += string_compress_decode_length(&src);

        match_length += 4;

        // copy match
        if (match_offset > ip || ip + match_length > dst.count)
            return 0;

        uint match = ip - match_offset;

        if (likely(match + match_length < ip)) {
            // safe to memcpy
            memcpy(&dst.data[ip], &dst.data[match], match_length);
        } else {
            for (uint i = 0; i < match_length; ++i) {
                dst.data[ip + i] = dst.data[match + i];
            }
        }

        ip += match_length;
    }

    return ip;
}

// Returns a non-cryptographic hash, good enough for hash tables.
//
// h:
//   Initial hash, or 0 for default hash state.
//   Can be used to add prefix bytes to the hash:
//
//   prefix = string_hash(0, random_bytes);
//   hash   = string_hash(prefix, str);
//
//   or hash long streams of data in chunks:
//
//   h = 0;
//   while (buffer.count = fread(buffer.data, 1, buffer.count, file))
//       h = string_hash(h, buffer);
uint64
string_hash(uint64 h, string key)
{
    // FNV-1a 64
    // http://www.isthe.com/chongo/tech/comp/fnv/index.html
    if (!h) h = 0xCBF29CE484222325ULL;
    for (; key.count; --key.count) {
        h ^= (uint64)(*key.data++);
        h *= 0x00000100000001B3ULL;
    }
    return h;
}

uint32
char_tolower(uint32 c)
{
    if (c >= 'A' && c <= 'Z')
        return c + ('a' - 'A');

    return c;
}

uint32
char_toupper(uint32 c)
{
    if (c >= 'a' && c <= 'z')
        return c - ('a' - 'A');

    return c;
}

bool
char_isspace(uint32 c)
{
    return c == ' ' || c == '\t' || c == '\n' || c == '\r'
        || c == '\v' || c == '\f';
}

// Add an 's' if count is plural.
//
//     printf("%d block%s\n", nblocks, char_plural(nblocks));
//
char *
char_plural(int count)
{
    if (count == 1)
        return "";

    return "s";
}

attr(always_inline) void
memswap(void *a, void *b, uint size)
{
    char t[0x400];

    assert(size <= 0x400);

    memcpy(t, a, size);
    memcpy(a, b, size);
    memcpy(b, t, size);
}

int
strcasecmp(const char *a, const char *b)
{
    while (char_tolower(*a) == char_tolower(*b++))
        if (*a++ == '\0')
            return 0;

    return *a - *(b - 1);
}

void
io_seek(io_t *io, sint offset)
{
    assert(offset <= (sint)io->count && (io->data + offset >= io->start));

    io->data  += offset;
    io->count -= offset;
}

void
io_rewind(io_t *io)
{
    io->count += io->data - io->start;
    io->data = io->start;
}

uint
io_size(io_t io)
{
    if (!io.start)
        return 0;

    char *end = io.data + io.count;
    return end - io.start;
}

void
io_read(void *result, uint size, io_t *io)
{
    assert(io->count >= size);

    memcpy(result, io->data, size);
    io->data += size;
    io->count -= size;
}

uint
size_divide(uint size)
{
    if (size >= 1024) size /= 1024;
    return size;
}

char *
size_suffix(uint size)
{
    if (size < 1024) return "  ";
    return "KB";
}