Return to utf8.c CVS log

Up to [local] / src / usr.bin / tmux

Instead of storing all UTF-8 characters in the extended cell which means
that 14 bytes are wasted for each character in the BMP, only store
characters of three bytes or less in the cell itself and store others
(outside the BMP or with combining characters) in a separate global
tree. Can reduce grid memory use for heavy Unicode users by around 30%.

/* $OpenBSD: utf8.c,v 1.45 2020/05/25 09:32:10 nicm Exp $ */

/*
 * Copyright (c) 2008 Nicholas Marriott <nicholas.marriott@gmail.com>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF MIND, USE, DATA OR PROFITS, WHETHER
 * IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING
 * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>

#include <ctype.h>
#include <errno.h>
#include <stdlib.h>
#include <string.h>
#include <vis.h>
#include <wchar.h>

#include "tmux.h"

static int	utf8_width(wchar_t);

struct utf8_big_item {
	u_int			index;
	RB_ENTRY(utf8_big_item)	entry;

	char			data[UTF8_SIZE];
	u_char			size;
};
RB_HEAD(utf8_big_tree, utf8_big_item);

static int
utf8_big_cmp(struct utf8_big_item *bi1, struct utf8_big_item *bi2)
{
	if (bi1->size < bi2->size)
		return (-1);
	if (bi1->size > bi2->size)
		return (1);
	return (memcmp(bi1->data, bi2->data, bi1->size));
}
RB_GENERATE_STATIC(utf8_big_tree, utf8_big_item, entry, utf8_big_cmp);
static struct utf8_big_tree utf8_big_tree = RB_INITIALIZER(utf8_big_tree);

static struct utf8_big_item *utf8_big_list;
static u_int utf8_big_list_size;
static u_int utf8_big_list_used;

union utf8_big_map {
	uint32_t	value;
	struct {
		u_char	flags;
#define UTF8_BIG_SIZE 0x1f
#define UTF8_BIG_WIDTH2 0x20

		u_char	data[3];
	};
} __packed;

static const union utf8_big_map utf8_big_space1 = {
	.flags = 1,
	.data = " "
};
static const union utf8_big_map utf8_big_space2 = {
	.flags = UTF8_BIG_WIDTH2|2,
	.data = "  "
};

/* Get a big item by index. */
static struct utf8_big_item *
utf8_get_big_item(const char *data, size_t size)
{
	struct utf8_big_item bi;

	memcpy(bi.data, data, size);
	bi.size = size;

	return (RB_FIND(utf8_big_tree, &utf8_big_tree, &bi));
}

/* Add a big item. */
static int
utf8_put_big_item(const char *data, size_t size, u_int *index)
{
	struct utf8_big_item	*bi;

	bi = utf8_get_big_item(data, size);
	if (bi != NULL) {
		*index = bi->index;
		log_debug("%s: have %.*s at %u", __func__, (int)size, data,
		    *index);
		return (0);
	}

	if (utf8_big_list_used == utf8_big_list_size) {
		if (utf8_big_list_size == 0xffffff)
			return (-1);
		if (utf8_big_list_size == 0)
			utf8_big_list_size = 256;
		else if (utf8_big_list_size > 0x7fffff)
			utf8_big_list_size = 0xffffff;
		else
			utf8_big_list_size *= 2;
		utf8_big_list = xreallocarray(utf8_big_list, utf8_big_list_size,
		    sizeof *utf8_big_list);
	}
	*index = utf8_big_list_used++;

	bi = &utf8_big_list[*index];
	bi->index = *index;
	memcpy(bi->data, data, size);
	bi->size = size;
	RB_INSERT(utf8_big_tree, &utf8_big_tree, bi);

	log_debug("%s: added %.*s at %u", __func__, (int)size, data, *index);
	return (0);
}

/* Get UTF-8 as index into buffer. */
uint32_t
utf8_map_big(const struct utf8_data *ud)
{
	union utf8_big_map	 m = { .value = 0 };
	u_int			 o;
	const char		*data = ud->data;
	size_t			 size = ud->size;

	if (ud->width != 1 && ud->width != 2)
		return (utf8_big_space1.value);

	if (size > UTF8_BIG_SIZE)
		goto fail;
	if (size == 1)
		return (utf8_set_big(data[0], 1));

	m.flags = size;
	if (ud->width == 2)
		m.flags |= UTF8_BIG_WIDTH2;

	if (size <= 3) {
		memcpy(&m.data, data, size);
		return (m.value);
	}

	if (utf8_put_big_item(data, size, &o) != 0)
		goto fail;
	m.data[0] = (o & 0xff);
	m.data[1] = (o >> 8) & 0xff;
	m.data[2] = (o >> 16);
	return (m.value);

fail:
	if (ud->width == 1)
		return (utf8_big_space1.value);
	return (utf8_big_space2.value);
}

/* Get UTF-8 from index into buffer. */
void
utf8_get_big(uint32_t v, struct utf8_data *ud)
{
	union utf8_big_map	 m = { .value = v };
	struct utf8_big_item	*bi;
	u_int			 o;

	memset(ud, 0, sizeof *ud);
	ud->size = ud->have = (m.flags & UTF8_BIG_SIZE);
	if (m.flags & UTF8_BIG_WIDTH2)
		ud->width = 2;
	else
		ud->width = 1;

	if (ud->size <= 3) {
		memcpy(ud->data, m.data, ud->size);
		return;
	}

	o = ((uint32_t)m.data[2] << 16)|((uint32_t)m.data[1] << 8)|m.data[0];
	if (o >= utf8_big_list_used)
		memset(ud->data, ' ', ud->size);
	else {
		bi = &utf8_big_list[o];
		memcpy(ud->data, bi->data, ud->size);
	}
}

/* Get big value for UTF-8 single character. */
uint32_t
utf8_set_big(char c, u_int width)
{
	union utf8_big_map	m = { .flags = 1, .data[0] = c };

	if (width == 2)
		m.flags |= UTF8_BIG_WIDTH2;
	return (m.value);
}

/* Set a single character. */
void
utf8_set(struct utf8_data *ud, u_char ch)
{
	static const struct utf8_data empty = { { 0 }, 1, 1, 1 };

	memcpy(ud, &empty, sizeof *ud);
	*ud->data = ch;
}

/* Copy UTF-8 character. */
void
utf8_copy(struct utf8_data *to, const struct utf8_data *from)
{
	u_int	i;

	memcpy(to, from, sizeof *to);

	for (i = to->size; i < sizeof to->data; i++)
		to->data[i] = '\0';
}

/*
 * Open UTF-8 sequence.
 *
 * 11000010-11011111 C2-DF start of 2-byte sequence
 * 11100000-11101111 E0-EF start of 3-byte sequence
 * 11110000-11110100 F0-F4 start of 4-byte sequence
 */
enum utf8_state
utf8_open(struct utf8_data *ud, u_char ch)
{
	memset(ud, 0, sizeof *ud);
	if (ch >= 0xc2 && ch <= 0xdf)
		ud->size = 2;
	else if (ch >= 0xe0 && ch <= 0xef)
		ud->size = 3;
	else if (ch >= 0xf0 && ch <= 0xf4)
		ud->size = 4;
	else
		return (UTF8_ERROR);
	utf8_append(ud, ch);
	return (UTF8_MORE);
}

/* Append character to UTF-8, closing if finished. */
enum utf8_state
utf8_append(struct utf8_data *ud, u_char ch)
{
	wchar_t	wc;
	int	width;

	if (ud->have >= ud->size)
		fatalx("UTF-8 character overflow");
	if (ud->size > sizeof ud->data)
		fatalx("UTF-8 character size too large");

	if (ud->have != 0 && (ch & 0xc0) != 0x80)
		ud->width = 0xff;

	ud->data[ud->have++] = ch;
	if (ud->have != ud->size)
		return (UTF8_MORE);

	if (ud->width == 0xff)
		return (UTF8_ERROR);

	if (utf8_combine(ud, &wc) != UTF8_DONE)
		return (UTF8_ERROR);
	if ((width = utf8_width(wc)) < 0)
		return (UTF8_ERROR);
	ud->width = width;

	return (UTF8_DONE);
}

/* Get width of Unicode character. */
static int
utf8_width(wchar_t wc)
{
	int	width;

	width = wcwidth(wc);
	if (width < 0 || width > 0xff) {
		log_debug("Unicode %04lx, wcwidth() %d", (long)wc, width);
		return (-1);
	}
	return (width);
}

/* Combine UTF-8 into Unicode. */
enum utf8_state
utf8_combine(const struct utf8_data *ud, wchar_t *wc)
{
	switch (mbtowc(wc, ud->data, ud->size)) {
	case -1:
		log_debug("UTF-8 %.*s, mbtowc() %d", (int)ud->size, ud->data,
		    errno);
		mbtowc(NULL, NULL, MB_CUR_MAX);
		return (UTF8_ERROR);
	case 0:
		return (UTF8_ERROR);
	default:
		return (UTF8_DONE);
	}
}

/* Split Unicode into UTF-8. */
enum utf8_state
utf8_split(wchar_t wc, struct utf8_data *ud)
{
	char	s[MB_LEN_MAX];
	int	slen;

	slen = wctomb(s, wc);
	if (slen <= 0 || slen > (int)sizeof ud->data)
		return (UTF8_ERROR);

	memcpy(ud->data, s, slen);
	ud->size = slen;

	ud->width = utf8_width(wc);
	return (UTF8_DONE);
}

/*
 * Encode len characters from src into dst, which is guaranteed to have four
 * bytes available for each character from src (for \abc or UTF-8) plus space
 * for \0.
 */
int
utf8_strvis(char *dst, const char *src, size_t len, int flag)
{
	struct utf8_data	 ud;
	const char		*start, *end;
	enum utf8_state		 more;
	size_t			 i;

	start = dst;
	end = src + len;

	while (src < end) {
		if ((more = utf8_open(&ud, *src)) == UTF8_MORE) {
			while (++src < end && more == UTF8_MORE)
				more = utf8_append(&ud, *src);
			if (more == UTF8_DONE) {
				/* UTF-8 character finished. */
				for (i = 0; i < ud.size; i++)
					*dst++ = ud.data[i];
				continue;
			}
			/* Not a complete, valid UTF-8 character. */
			src -= ud.have;
		}
		if (src[0] == '$' && src < end - 1) {
			if (isalpha((u_char)src[1]) ||
			    src[1] == '_' ||
			    src[1] == '{')
				*dst++ = '\\';
			*dst++ = '$';
		} else if (src < end - 1)
			dst = vis(dst, src[0], flag, src[1]);
		else if (src < end)
			dst = vis(dst, src[0], flag, '\0');
		src++;
	}

	*dst = '\0';
	return (dst - start);
}

/* Same as utf8_strvis but allocate the buffer. */
int
utf8_stravis(char **dst, const char *src, int flag)
{
	char	*buf;
	int	 len;

	buf = xreallocarray(NULL, 4, strlen(src) + 1);
	len = utf8_strvis(buf, src, strlen(src), flag);

	*dst = xrealloc(buf, len + 1);
	return (len);
}

/* Does this string contain anything that isn't valid UTF-8? */
int
utf8_isvalid(const char *s)
{
	struct utf8_data	 ud;
	const char		*end;
	enum utf8_state		 more;

	end = s + strlen(s);
	while (s < end) {
		if ((more = utf8_open(&ud, *s)) == UTF8_MORE) {
			while (++s < end && more == UTF8_MORE)
				more = utf8_append(&ud, *s);
			if (more == UTF8_DONE)
				continue;
			return (0);
		}
		if (*s < 0x20 || *s > 0x7e)
			return (0);
		s++;
	}
	return (1);
}

/*
 * Sanitize a string, changing any UTF-8 characters to '_'. Caller should free
 * the returned string. Anything not valid printable ASCII or UTF-8 is
 * stripped.
 */
char *
utf8_sanitize(const char *src)
{
	char			*dst;
	size_t			 n;
	enum utf8_state		 more;
	struct utf8_data	 ud;
	u_int			 i;

	dst = NULL;

	n = 0;
	while (*src != '\0') {
		dst = xreallocarray(dst, n + 1, sizeof *dst);
		if ((more = utf8_open(&ud, *src)) == UTF8_MORE) {
			while (*++src != '\0' && more == UTF8_MORE)
				more = utf8_append(&ud, *src);
			if (more == UTF8_DONE) {
				dst = xreallocarray(dst, n + ud.width,
				    sizeof *dst);
				for (i = 0; i < ud.width; i++)
					dst[n++] = '_';
				continue;
			}
			src -= ud.have;
		}
		if (*src > 0x1f && *src < 0x7f)
			dst[n++] = *src;
		else
			dst[n++] = '_';
		src++;
	}

	dst = xreallocarray(dst, n + 1, sizeof *dst);
	dst[n] = '\0';
	return (dst);
}

/* Get UTF-8 buffer length. */
size_t
utf8_strlen(const struct utf8_data *s)
{
	size_t	i;

	for (i = 0; s[i].size != 0; i++)
		/* nothing */;
	return (i);
}

/* Get UTF-8 string width. */
u_int
utf8_strwidth(const struct utf8_data *s, ssize_t n)
{
	ssize_t	i;
	u_int	width;

	width = 0;
	for (i = 0; s[i].size != 0; i++) {
		if (n != -1 && n == i)
			break;
		width += s[i].width;
	}
	return (width);
}

/*
 * Convert a string into a buffer of UTF-8 characters. Terminated by size == 0.
 * Caller frees.
 */
struct utf8_data *
utf8_fromcstr(const char *src)
{
	struct utf8_data	*dst;
	size_t			 n;
	enum utf8_state		 more;

	dst = NULL;

	n = 0;
	while (*src != '\0') {
		dst = xreallocarray(dst, n + 1, sizeof *dst);
		if ((more = utf8_open(&dst[n], *src)) == UTF8_MORE) {
			while (*++src != '\0' && more == UTF8_MORE)
				more = utf8_append(&dst[n], *src);
			if (more == UTF8_DONE) {
				n++;
				continue;
			}
			src -= dst[n].have;
		}
		utf8_set(&dst[n], *src);
		n++;
		src++;
	}

	dst = xreallocarray(dst, n + 1, sizeof *dst);
	dst[n].size = 0;
	return (dst);
}

/* Convert from a buffer of UTF-8 characters into a string. Caller frees. */
char *
utf8_tocstr(struct utf8_data *src)
{
	char	*dst;
	size_t	 n;

	dst = NULL;

	n = 0;
	for(; src->size != 0; src++) {
		dst = xreallocarray(dst, n + src->size, 1);
		memcpy(dst + n, src->data, src->size);
		n += src->size;
	}

	dst = xreallocarray(dst, n + 1, 1);
	dst[n] = '\0';
	return (dst);
}

/* Get width of UTF-8 string. */
u_int
utf8_cstrwidth(const char *s)
{
	struct utf8_data	tmp;
	u_int			width;
	enum utf8_state		more;

	width = 0;
	while (*s != '\0') {
		if ((more = utf8_open(&tmp, *s)) == UTF8_MORE) {
			while (*++s != '\0' && more == UTF8_MORE)
				more = utf8_append(&tmp, *s);
			if (more == UTF8_DONE) {
				width += tmp.width;
				continue;
			}
			s -= tmp.have;
		}
		if (*s > 0x1f && *s != 0x7f)
			width++;
		s++;
	}
	return (width);
}

/* Pad UTF-8 string to width on the left. Caller frees. */
char *
utf8_padcstr(const char *s, u_int width)
{
	size_t	 slen;
	char	*out;
	u_int	  n, i;

	n = utf8_cstrwidth(s);
	if (n >= width)
		return (xstrdup(s));

	slen = strlen(s);
	out = xmalloc(slen + 1 + (width - n));
	memcpy(out, s, slen);
	for (i = n; i < width; i++)
		out[slen++] = ' ';
	out[slen] = '\0';
	return (out);
}

/* Pad UTF-8 string to width on the right. Caller frees. */
char *
utf8_rpadcstr(const char *s, u_int width)
{
	size_t	 slen;
	char	*out;
	u_int	  n, i;

	n = utf8_cstrwidth(s);
	if (n >= width)
		return (xstrdup(s));

	slen = strlen(s);
	out = xmalloc(slen + 1 + (width - n));
	for (i = 0; i < width - n; i++)
		out[i] = ' ';
	memcpy(out + i, s, slen);
	out[i + slen] = '\0';
	return (out);
}

int
utf8_cstrhas(const char *s, const struct utf8_data *ud)
{
	struct utf8_data	*copy, *loop;
	int			 found = 0;

	copy = utf8_fromcstr(s);
	for (loop = copy; loop->size != 0; loop++) {
		if (loop->size != ud->size)
			continue;
		if (memcmp(loop->data, ud->data, loop->size) == 0) {
			found = 1;
			break;
		}
	}
	free(copy);

	return (found);
}