src/lib/unichar.c

	unichar.c revision 576e0be735a03d1fa6e82a120aba03adabdcda66
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen/* Copyright (c) 2005-2009 Dovecot authors, see the included COPYING file */
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen#include "lib.h"
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen#include "array.h"
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen#include "bsearch-insert-pos.h"
e074ffeaee1ce283bd42f167c6810e3d013f8218Timo Sirainen#include "unichar.h"
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen#include "unicodemap.c"
08d6658a4e2ec8104cd1307f6baa75fdb07a24f8Mark Washenberger
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen#define HANGUL_FIRST 0xac00
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen#define HANGUL_LAST 0xd7a3
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen
08d6658a4e2ec8104cd1307f6baa75fdb07a24f8Mark Washenbergerstatic const uint8_t utf8_non1_bytes[256 - 192 - 2] = {
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,6,6,1,1
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen};
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen
78ed6a99e980228a75fa59cff84327dc0ea82857Timo Sirainenconst uint8_t *const uni_utf8_non1_bytes = utf8_non1_bytes;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainenunsigned int uni_strlen(const unichar_t *str)
97c339398f1aba6f315b55a9b6ee6b020e33bea4Timo Sirainen{
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    unsigned int len = 0;
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen
97c339398f1aba6f315b55a9b6ee6b020e33bea4Timo Sirainen    for (len = 0; str[len] != 0; len++) ;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen
97c339398f1aba6f315b55a9b6ee6b020e33bea4Timo Sirainen    return len;
6135260095e1704ed6edff9d00bdfc043c11429cTimo Sirainen}
e80203675151ef9d4f3f850cf02041042eb13096Timo Sirainen
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainenint uni_utf8_get_char(const char *input, unichar_t *chr_r)
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen{
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    return uni_utf8_get_char_n((const unsigned char *)input, (size_t)-1,
50782de8a9d5ebe11ee61496b4e695a1d3875230Timo Sirainen                   chr_r);
50782de8a9d5ebe11ee61496b4e695a1d3875230Timo Sirainen}
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainenint uni_utf8_get_char_n(const void *_input, size_t max_len, unichar_t *chr_r)
462b8c71015b2483cff3c59fa3668246dc72dfceAndrey Panin{
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    const unsigned char *input = _input;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    unichar_t chr;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    unsigned int i, len;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    int ret;
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen    i_assert(max_len > 0);
1e3a608d8d0e08cb7d549718fbfbcc148fdb236fTimo Sirainen
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    if (*input < 0x80) {
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        *chr_r = *input;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        return 1;
1e3a608d8d0e08cb7d549718fbfbcc148fdb236fTimo Sirainen    }
50782de8a9d5ebe11ee61496b4e695a1d3875230Timo Sirainen
50782de8a9d5ebe11ee61496b4e695a1d3875230Timo Sirainen    /* first byte has len highest bits set, followed by zero bit.
1e3a608d8d0e08cb7d549718fbfbcc148fdb236fTimo Sirainen       the rest of the bits are used as the highest bits of the value. */
1e3a608d8d0e08cb7d549718fbfbcc148fdb236fTimo Sirainen    chr = *input;
1e3a608d8d0e08cb7d549718fbfbcc148fdb236fTimo Sirainen    len = uni_utf8_char_bytes(*input);
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    switch (len) {
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    case 2:
4ac5448461b63de9637de839fbc611a3d503287cTimo Sirainen        chr &= 0x1f;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        break;
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen    case 3:
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        chr &= 0x0f;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        break;
1b81b28b2e7856748cffd7d01052a944b6c80b23Timo Sirainen    case 4:
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen        chr &= 0x07;
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen        break;
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen    case 5:
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        chr &= 0x03;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        break;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen    case 6:
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        chr &= 0x01;
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        break;
7bafda1813454621e03615e83d55bccfa7cc56bdTimo Sirainen    default:
7bafda1813454621e03615e83d55bccfa7cc56bdTimo Sirainen        /* only 7bit chars should have len==1 */
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        i_assert(len == 1);
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        return -1;
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen    }
73bfdbe28c2ce6d143eadf0bab8ccfbe4cab0faeTimo Sirainen
e70d5895795732b8247ab9abb045b438e954bc46Timo Sirainen    if (len <= max_len)
33c6d5807b449463e9b81db5ec99fe027cc1b984Timo Sirainen        ret = 1;
    else {
        /* check first if the input is invalid before returning 0 */
        ret = 0;
        len = max_len;
    }

    /* the following bytes must all be 10xxxxxx */
    for (i = 1; i < len; i++) {
        if ((input[i] & 0xc0) != 0x80)
            return input[i] == '\0' ? 0 : -1;

        chr <<= 6;
        chr |= input[i] & 0x3f;
    }

    *chr_r = chr;
    return ret;
}

int uni_utf8_to_ucs4(const char *input, ARRAY_TYPE(unichars) *output)
{
    unichar_t chr;

    while (*input != '\0') {
        if (uni_utf8_get_char(input, &chr) <= 0) {
            /* invalid input */
            return -1;
        }
                input += uni_utf8_char_bytes(*input);

        array_append(output, &chr, 1);
    }
    return 0;
}

void uni_ucs4_to_utf8(const unichar_t *input, size_t len, buffer_t *output)
{
    for (; len > 0 && *input != '\0'; input++, len--)
        uni_ucs4_to_utf8_c(*input, output);
}

void uni_ucs4_to_utf8_c(unichar_t chr, buffer_t *output)
{
    unsigned char first;
    int bitpos;

    if (chr < 0x80) {
        buffer_append_c(output, chr);
        return;
    }

    i_assert(chr < 0x80000000); /* 1 << (5*6 + 1) */

    if (chr < (1 << (6 + 5))) {
        /* 110xxxxx */
        bitpos = 6;
        first = 0x80 | 0x40;
    } else if (chr < (1 << ((2*6) + 4))) {
        /* 1110xxxx */
        bitpos = 2*6;
        first = 0x80 | 0x40 | 0x20;
    } else if (chr < (1 << ((3*6) + 3))) {
        /* 11110xxx */
        bitpos = 3*6;
        first = 0x80 | 0x40 | 0x20 | 0x10;
    } else if (chr < (1 << ((4*6) + 2))) {
        /* 111110xx */
        bitpos = 4*6;
        first = 0x80 | 0x40 | 0x20 | 0x10 | 0x08;
    } else {
        /* 1111110x */
        bitpos = 5*6;
        first = 0x80 | 0x40 | 0x20 | 0x10 | 0x08 | 0x04;
    }
    buffer_append_c(output, first | (chr >> bitpos));

    do {
        bitpos -= 6;
        buffer_append_c(output, 0x80 | ((chr >> bitpos) & 0x3f));
    } while (bitpos > 0);
}

unsigned int uni_utf8_strlen_n(const void *_input, size_t size)
{
    const unsigned char *input = _input;
    unsigned int len = 0;
    size_t i;

    for (i = 0; i < size && input[i] != '\0'; ) {
        i += uni_utf8_char_bytes(input[i]);
        if (i > size)
            break;
        len++;
    }
    return len;
}

static bool uint16_find(const uint16_t *data, unsigned int count,
            uint16_t value, unsigned int *idx_r)
{
    BINARY_NUMBER_SEARCH(data, count, value, idx_r);
}

static bool uint32_find(const uint32_t *data, unsigned int count,
            uint32_t value, unsigned int *idx_r)
{
    BINARY_NUMBER_SEARCH(data, count, value, idx_r);
}

unichar_t uni_ucs4_to_titlecase(unichar_t chr)
{
    unsigned int idx;

    if (chr <= 0xffff) {
        if (!uint16_find(titlecase16_keys, N_ELEMENTS(titlecase16_keys),
                 chr, &idx))
            return chr;
        else
            return titlecase16_values[idx];
    } else {
        if (!uint32_find(titlecase32_keys, N_ELEMENTS(titlecase32_keys),
                 chr, &idx))
            return chr;
        else
            return titlecase32_values[idx];
    }
}

static bool uni_ucs4_decompose_uni(unichar_t *chr)
{
    unsigned int idx;

    if (*chr <= 0xffff) {
        if (!uint16_find(uni16_decomp_keys,
                 N_ELEMENTS(uni16_decomp_keys),
                 *chr, &idx))
            return FALSE;
        *chr = uni16_decomp_values[idx];
    } else {
        if (!uint32_find(uni32_decomp_keys,
                 N_ELEMENTS(uni32_decomp_keys),
                 *chr, &idx))
            return FALSE;
        *chr = uni32_decomp_values[idx];
    }
    return TRUE;
}

static void uni_ucs4_decompose_hangul_utf8(unichar_t chr, buffer_t *output)
{
#define SBase HANGUL_FIRST
#define LBase 0x1100
#define VBase 0x1161
#define TBase 0x11A7
#define LCount 19
#define VCount 21
#define TCount 28
#define NCount (VCount * TCount)
    unsigned int SIndex = chr - SBase;
        unichar_t L = LBase + SIndex / NCount;
        unichar_t V = VBase + (SIndex % NCount) / TCount;
        unichar_t T = TBase + SIndex % TCount;

    uni_ucs4_to_utf8_c(L, output);
    uni_ucs4_to_utf8_c(V, output);
    if (T != TBase) uni_ucs4_to_utf8_c(T, output);
}

static bool uni_ucs4_decompose_multi_utf8(unichar_t chr, buffer_t *output)
{
    const uint16_t *value;
    unsigned int idx;

    if (chr > 0xffff)
        return FALSE;

    if (!uint32_find(multidecomp_keys, N_ELEMENTS(multidecomp_keys),
             chr, &idx))
        return FALSE;

    value = &multidecomp_values[multidecomp_offsets[idx]];
    for (; *value != 0; value++)
        uni_ucs4_to_utf8_c(*value, output);
    return TRUE;
}

static void output_add_replacement_char(buffer_t *output)
{
    /* 0xfffd */
    static const unsigned char replacement_utf8[] = { 0xef, 0xbf, 0xbd };
#define REPLACEMENT_UTF8_LEN 3

    if (output->used >= REPLACEMENT_UTF8_LEN &&
        memcmp(CONST_PTR_OFFSET(output->data,
                    output->used - REPLACEMENT_UTF8_LEN),
           replacement_utf8, REPLACEMENT_UTF8_LEN) == 0) {
        /* don't add the replacement char multiple times */
        return;
    }
    buffer_append(output, replacement_utf8, REPLACEMENT_UTF8_LEN);
}

int uni_utf8_to_decomposed_titlecase(const void *_input, size_t max_len,
                     buffer_t *output)
{
    const unsigned char *input = _input;
    unsigned int bytes;
    unichar_t chr;
    int ret = 0;

    while (max_len > 0 && *input != '\0') {
        if (uni_utf8_get_char_n(input, max_len, &chr) <= 0) {
            /* invalid input. try the next byte. */
            ret = -1;
            input++; max_len--;
            output_add_replacement_char(output);
            continue;
        }
        bytes = uni_utf8_char_bytes(*input);
        input += bytes;
        max_len -= bytes;

        chr = uni_ucs4_to_titlecase(chr);
        if (chr >= HANGUL_FIRST && chr <= HANGUL_LAST)
            uni_ucs4_decompose_hangul_utf8(chr, output);
        else if (uni_ucs4_decompose_uni(&chr) ||
             !uni_ucs4_decompose_multi_utf8(chr, output))
            uni_ucs4_to_utf8_c(chr, output);
    }
    return ret;
}

static inline unsigned int
is_valid_utf8_seq(const unsigned char *input, unsigned int size)
{
    size_t i, len;

    len = uni_utf8_char_bytes(input[0]);
    if (unlikely(len > size || len == 1))
        return 0;

    for (i = 1; i < len; i++) {
        if (unlikely(uni_utf8_char_bytes(input[i]) != len-i ||
                 input[i] < 192-2))
            return 0;
    }
    return len;
}

bool uni_utf8_get_valid_data(const unsigned char *input, size_t size,
                 buffer_t *buf)
{
    size_t i, len;

    /* find the first invalid utf8 sequence */
    for (i = 0; i < size;) {
        if (input[i] < 0x80)
            i++;
        else {
            len = is_valid_utf8_seq(input + i, size-i);
            if (unlikely(len == 0))
                goto broken;
            i += len;
        }
    }
    return TRUE;
broken:
    /* broken utf-8 input - skip the broken characters */
    buffer_append(buf, input, i++);

    output_add_replacement_char(buf);
    while (i < size) {
        if (input[i] < 0x80) {
            buffer_append_c(buf, input[i++]);
            continue;
        }

        len = is_valid_utf8_seq(input + i, size-i);
        if (len == 0) {
            i++;
            output_add_replacement_char(buf);
            continue;
        }
        buffer_append(buf, input + i, len);
        i += len;
    }
    return FALSE;
}