shithub: femtolisp

ref: f5e20c5823337a159618f02c861af69879b0f0e8
dir: /llt/utf8.c/

View raw version
/*
  Basic UTF-8 manipulation routines
  by Jeff Bezanson
  placed in the public domain Fall 2005

  This code is designed to provide the utilities you need to manipulate
  UTF-8 as an internal string encoding. These functions do not perform the
  error checking normally needed when handling UTF-8 data, so if you happen
  to be from the Unicode Consortium you will want to flay me alive.
  I do this because error checking can be performed at the boundaries (I/O),
  with these routines reserved for higher performance on data known to be
  valid.
  A UTF-8 validation routine is included.
*/

#include "llt.h"

static const uint32_t offsetsFromUTF8[6] = {
	0x00000000UL, 0x00003080UL, 0x000E2080UL,
	0x03C82080UL, 0xFA082080UL, 0x82082080UL
};

static const char trailingBytesForUTF8[256] = {
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
	1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2, 3,3,3,3,3,3,3,3,4,4,4,4,5,5,5,5
};

// straight from musl
int
u8_iswprint(uint32_t c)
{
	if(c < 0xff)
		return ((c+1) & 0x7f) >= 0x21;
	if(c < 0x2028 || c-0x202a < 0xd800-0x202a || c-0xe000 < 0xfff9-0xe000)
		return 1;
	return !(c-0xfffc > 0x10ffff-0xfffc || (c&0xfffe) == 0xfffe);
}

/* returns length of next utf-8 sequence */
size_t
u8_seqlen(const char *s)
{
	return trailingBytesForUTF8[(unsigned int)(uint8_t)s[0]] + 1;
}

/* returns the # of bytes needed to encode a certain character
   0 means the character cannot (or should not) be encoded. */
size_t
u8_charlen(uint32_t ch)
{
	if(ch < 0x80)
		return 1;
	if(ch < 0x800)
		return 2;
	if(ch < 0x10000)
		return 3;
	if(ch < 0x110000)
		return 4;
	return 0;
}

size_t
u8_codingsize(uint32_t *wcstr, size_t n)
{
	size_t i, c = 0;

	for(i = 0; i < n; i++)
		c += u8_charlen(wcstr[i]);
	return c;
}

/* conversions without error checking
   only works for valid UTF-8, i.e. no 5- or 6-byte sequences
   srcsz = source size in bytes
   sz = dest size in # of wide characters

   returns # characters converted
   if sz == srcsz+1 (i.e. 4*srcsz+4 bytes), there will always be enough space.
*/
size_t
u8_toucs(uint32_t *dest, size_t sz, const char *src, size_t srcsz)
{
	uint32_t ch;
	const char *src_end = src + srcsz;
	size_t nb, i = 0;

	if(sz == 0 || srcsz == 0)
		return 0;

	while(i < sz){
		if(!isutf(*src)){ // invalid sequence
			dest[i++] = 0xFFFD;
			src++;
			if(src >= src_end)
				break;
			continue;
		}
		nb = trailingBytesForUTF8[(uint8_t)*src];
		if(src + nb >= src_end)
			break;
		ch = 0;
		switch(nb){
		case 5: ch += (uint8_t)*src++; ch <<= 6; // fallthrough
		case 4: ch += (uint8_t)*src++; ch <<= 6; // fallthrough
		case 3: ch += (uint8_t)*src++; ch <<= 6; // fallthrough
		case 2: ch += (uint8_t)*src++; ch <<= 6; // fallthrough
		case 1: ch += (uint8_t)*src++; ch <<= 6; // fallthrough
		case 0: ch += (uint8_t)*src++;
		}
		ch -= offsetsFromUTF8[nb];
		dest[i++] = ch;
	}
	return i;
}

/*
 * srcsz = number of source characters
 * sz = size of dest buffer in bytes
 * returns # bytes stored in dest
 * the destination string will never be bigger than the source string.
*/
size_t
u8_toutf8(char *dest, size_t sz, const uint32_t *src, size_t srcsz)
{
	uint32_t ch;
	size_t i = 0;
	char *dest0 = dest;
	char *dest_end = dest + sz;

	while(i < srcsz){
		ch = src[i];
		if(ch < 0x80){
			if(dest >= dest_end)
				break;
			*dest++ = (char)ch;
		}else if(ch < 0x800){
			if(dest >= dest_end-1)
				break;
			*dest++ = (ch>>6) | 0xC0;
			*dest++ = (ch & 0x3F) | 0x80;
		}else if(ch < 0x10000){
			if(dest >= dest_end-2)
				break;
			*dest++ = (ch>>12) | 0xE0;
			*dest++ = ((ch>>6) & 0x3F) | 0x80;
			*dest++ = (ch & 0x3F) | 0x80;
		}else if(ch < 0x110000){
			if(dest >= dest_end-3)
				break;
			*dest++ = (ch>>18) | 0xF0;
			*dest++ = ((ch>>12) & 0x3F) | 0x80;
			*dest++ = ((ch>>6) & 0x3F) | 0x80;
			*dest++ = (ch & 0x3F) | 0x80;
		}
		i++;
	}
	return dest-dest0;
}

size_t
u8_wc_toutf8(char *dest, uint32_t ch)
{
	if(ch < 0x80){
		dest[0] = (char)ch;
		return 1;
	}
	if(ch < 0x800){
		dest[0] = (ch>>6) | 0xC0;
		dest[1] = (ch & 0x3F) | 0x80;
		return 2;
	}
	if(ch < 0x10000){
		dest[0] = (ch>>12) | 0xE0;
		dest[1] = ((ch>>6) & 0x3F) | 0x80;
		dest[2] = (ch & 0x3F) | 0x80;
		return 3;
	}
	if(ch < 0x110000){
		dest[0] = (ch>>18) | 0xF0;
		dest[1] = ((ch>>12) & 0x3F) | 0x80;
		dest[2] = ((ch>>6) & 0x3F) | 0x80;
		dest[3] = (ch & 0x3F) | 0x80;
		return 4;
	}
	return 0;
}

/* charnum => byte offset */
size_t
u8_offset(const char *s, size_t charnum)
{
	size_t i = 0;

	while(charnum > 0){
		if(s[i++] & 0x80)
			(void)(isutf(s[++i]) || isutf(s[++i]) || ++i);
		charnum--;
	}
	return i;
}

/* byte offset => charnum */
size_t
u8_charnum(const char *s, size_t offset)
{
	size_t charnum = 0, i = 0;

	while(i < offset){
		if((s[i++] & 0x80) != 0 && !isutf(s[++i]) && !isutf(s[++i]))
			i++;
		charnum++;
	}
	return charnum;
}

/* number of characters in NUL-terminated string */
size_t
u8_strlen(const char *s)
{
	size_t count = 0;
	size_t i = 0, lasti;

	while(1) {
		lasti = i;
		while(s[i] > 0)
			i++;
		count += (i-lasti);
		if(s[i++] == 0)
			break;
		(void)(isutf(s[++i]) || isutf(s[++i]) || ++i);
		count++;
	}
	return count;
}

size_t
u8_strwidth(const char *s)
{
	uint32_t ch;
	size_t nb, tot = 0;
	int w;
	signed char sc;

	while((sc = (signed char)*s) != 0){
		if(sc >= 0){
			s++;
			if(sc)
				tot++;
		}else{
			if(!isutf(sc)){
				tot++;
				s++;
				continue;
			}
			nb = trailingBytesForUTF8[(uint8_t)sc];
			ch = 0;
			switch(nb){
			case 5: ch += (uint8_t)*s++; ch <<= 6; // fallthrough
			case 4: ch += (uint8_t)*s++; ch <<= 6; // fallthrough
			case 3: ch += (uint8_t)*s++; ch <<= 6; // fallthrough
			case 2: ch += (uint8_t)*s++; ch <<= 6; // fallthrough
			case 1: ch += (uint8_t)*s++; ch <<= 6; // fallthrough
			case 0: ch += (uint8_t)*s++;
			}
			ch -= offsetsFromUTF8[nb];
			w = wcwidth(ch); // might return -1
			if(w > 0)
				tot += w;
		}
	}
	return tot;
}

/* reads the next utf-8 sequence out of a string, updating an index */
uint32_t
u8_nextchar(const char *s, size_t *i)
{
	uint32_t ch = 0;
	size_t sz = 0;

	do{
		ch <<= 6;
		ch += (uint8_t)s[(*i)];
		sz++;
	}while(s[*i] && (++(*i)) && !isutf(s[*i]));
	return ch - offsetsFromUTF8[sz-1];
}

/* next character without NUL character terminator */
uint32_t
u8_nextmemchar(const char *s, size_t *i)
{
	uint32_t ch = 0;
	size_t sz = 0;

	do{
		ch <<= 6;
		ch += (uint8_t)s[(*i)++];
		sz++;
	}while(!isutf(s[*i]));
	return ch - offsetsFromUTF8[sz-1];
}

void
u8_inc(const char *s, size_t *i)
{
	(void)(isutf(s[++(*i)]) || isutf(s[++(*i)]) || isutf(s[++(*i)]) || ++(*i));
}

void
u8_dec(const char *s, size_t *i)
{
	(void)(isutf(s[--(*i)]) || isutf(s[--(*i)]) || isutf(s[--(*i)]) || --(*i));
}

int
octal_digit(char c)
{
	return (c >= '0' && c <= '7');
}

int
hex_digit(char c)
{
	return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
}

char
read_escape_control_char(char c)
{
	switch(c){
	case 'n': return '\n';
	case 't': return '\t';
	case 'a': return '\a';
	case 'b': return '\b';
	case 'e': return '\e';
	case 'f': return '\f';
	case 'r': return '\r';
	case 'v': return '\v';
	}
	return c;
}

/* assumes that src points to the character after a backslash
   returns number of input characters processed, 0 if error */
size_t
u8_read_escape_sequence(const char *str, size_t ssz, uint32_t *dest)
{
	assert(ssz > 0);
	uint32_t ch;
	char digs[10];
	int dno = 0, ndig;
	size_t i = 1;
	char c0 = str[0];

	if(octal_digit(c0)){
		i = 0;
		do{
			digs[dno++] = str[i++];
		}while(i < ssz && octal_digit(str[i]) && dno < 3);
		digs[dno] = '\0';
		ch = strtol(digs, nil, 8);
	}else if((c0 == 'x' && (ndig = 2)) || (c0 == 'u' && (ndig = 4)) || (c0 == 'U' && (ndig = 8))){
		while(i<ssz && hex_digit(str[i]) && dno < ndig)
			digs[dno++] = str[i++];
		if(dno == 0)
			return 0;
		digs[dno] = '\0';
		ch = strtol(digs, nil, 16);
	}else{
		ch = (uint32_t)read_escape_control_char(c0);
	}
	*dest = ch;

	return i;
}

/* convert a string with literal \uxxxx or \Uxxxxxxxx characters to UTF-8
   example: u8_unescape(mybuf, 256, "hello\\u220e")
   note the double backslash is needed if called on a C string literal */
size_t
u8_unescape(char *buf, size_t sz, const char *src)
{
	size_t c = 0, amt;
	uint32_t ch;
	char temp[4];

	while(*src && c < sz){
		if(*src == '\\'){
			src++;
			amt = u8_read_escape_sequence(src, 1000, &ch);
		}else{
			ch = (uint32_t)*src;
			amt = 1;
		}
		src += amt;
		amt = u8_wc_toutf8(temp, ch);
		if(amt > sz-c)
			break;
		memmove(&buf[c], temp, amt);
		c += amt;
	}
	if(c < sz)
		buf[c] = '\0';
	return c;
}

static inline int
buf_put2c(char *buf, const char *src)
{
	buf[0] = src[0];
	buf[1] = src[1];
	buf[2] = '\0';
	return 2;
}

int
u8_escape_wchar(char *buf, size_t sz, uint32_t ch)
{
	assert(sz > 2);
	if(ch >= 0x20 && ch < 0x7f){
		buf[0] = ch;
		buf[1] = '\0';
		return 1;
	}
	if(ch > 0xffff)
		return snprintf(buf, sz, "\\U%.8x", ch);
	if(ch >= 0x80)
		return snprintf(buf, sz, "\\u%04x", ch);
	switch(ch){
	case '\n': return buf_put2c(buf, "\\n");
	case '\t': return buf_put2c(buf, "\\t");
	case '\\': return buf_put2c(buf, "\\\\");
	case '\a': return buf_put2c(buf, "\\a");
	case '\b': return buf_put2c(buf, "\\b");
	case '\e': return buf_put2c(buf, "\\e");
	case '\f': return buf_put2c(buf, "\\f");
	case '\r': return buf_put2c(buf, "\\r");
	case '\v': return buf_put2c(buf, "\\v");
	}
	return snprintf(buf, sz, "\\x%02x", ch);
}

size_t
u8_escape(char *buf, size_t sz, const char *src, size_t *pi, size_t end, int escape_quotes, int ascii)
{
	size_t i = *pi, i0;
	uint32_t ch;
	char *start = buf;
	char *blim = start + sz-11;
	assert(sz > 11);

	while(i < end && buf < blim){
		// sz-11: leaves room for longest escape sequence
		if(escape_quotes && src[i] == '"'){
			buf += buf_put2c(buf, "\\\"");
			i++;
		}else if(src[i] == '\\'){
			buf += buf_put2c(buf, "\\\\");
			i++;
		}else{
			i0 = i;
			ch = u8_nextmemchar(src, &i);
			if(ascii || !u8_iswprint(ch)){
				buf += u8_escape_wchar(buf, sz - (buf-start), ch);
			}else{
				i = i0;
				do{
					*buf++ = src[i++];
				}while(!isutf(src[i]));
			}
		}
	}
	*buf++ = '\0';
	*pi = i;
	return (buf-start);
}

char *
u8_strchr(const char *s, uint32_t ch, size_t *charn)
{
	size_t i = 0, lasti = 0;
	uint32_t c;

	*charn = 0;
	while(s[i]){
		c = u8_nextchar(s, &i);
		if(c == ch){
			/* it's const for us, but not necessarily the caller */
			return (char*)&s[lasti];
		}
		lasti = i;
		(*charn)++;
	}
	return nil;
}

char *
u8_memchr(const char *s, uint32_t ch, size_t sz, size_t *charn)
{
	size_t i = 0, lasti = 0;
	uint32_t c;
	int csz;

	*charn = 0;
	while(i < sz){
		c = csz = 0;
		do{
			c <<= 6;
			c += (uint8_t)s[i++];
			csz++;
		}while(i < sz && !isutf(s[i]));
		c -= offsetsFromUTF8[csz-1];

		if(c == ch)
			return (char*)&s[lasti];
		lasti = i;
		(*charn)++;
	}
	return nil;
}

char *
u8_memrchr(const char *s, uint32_t ch, size_t sz)
{
	size_t i = sz-1, tempi = 0;
	uint32_t c;

	if(sz == 0)
		return nil;

	while(i && !isutf(s[i]))
		i--;

	while(1){
		tempi = i;
		c = u8_nextmemchar(s, &tempi);
		if(c == ch)
			return (char*)&s[i];
		if(i == 0)
			break;
		tempi = i;
		u8_dec(s, &i);
		if(i > tempi)
			break;
	}
	return nil;
}

size_t
u8_vprintf(const char *fmt, va_list ap)
{
	size_t cnt, sz, nc, needfree = 0;
	char *buf, tmp[512];
	uint32_t *wcs;

	sz = 512;
	buf = tmp;
	cnt = vsnprintf(buf, sz, fmt, ap);
	if((ssize_t)cnt < 0)
		return 0;
	if(cnt >= sz){
		buf = (char*)malloc(cnt + 1);
		needfree = 1;
		vsnprintf(buf, cnt+1, fmt, ap);
	}
	wcs = (uint32_t*)malloc((cnt+1) * sizeof(uint32_t));
	nc = u8_toucs(wcs, cnt+1, buf, cnt);
	wcs[nc] = 0;
#if defined(__plan9__)
	print("%S", (Rune*)wcs);
#else
	printf("%ls", (wchar_t*)wcs);
#endif
	free(wcs);
	if(needfree)
		free(buf);
	return nc;
}

size_t
u8_printf(const char *fmt, ...)
{
	size_t cnt;
	va_list args;

	va_start(args, fmt);
	cnt = u8_vprintf(fmt, args);

	va_end(args);
	return cnt;
}

/* based on the valid_utf8 routine from the PCRE library by Philip Hazel

   length is in bytes, since without knowing whether the string is valid
   it's hard to know how many characters there are! */
int
u8_isvalid(const char *str, int length)
{
	const uint8_t *p, *pend = (uint8_t*)str + length;
	uint8_t c;
	int ab;

	for(p = (uint8_t*)str; p < pend; p++){
		c = *p;
		if(c < 128)
			continue;
		if((c & 0xc0) != 0xc0)
			return 0;
		ab = trailingBytesForUTF8[c];
		if(length < ab)
			return 0;
		length -= ab;

		p++;
		/* Check top bits in the second byte */
		if((*p & 0xc0) != 0x80)
			return 0;

		/* Check for overlong sequences for each different length */
		switch(ab){
			/* Check for xx00 000x */
		case 1:
			if((c & 0x3e) == 0)
				return 0;
			continue; /* We know there aren't any more bytes to check */

			/* Check for 1110 0000, xx0x xxxx */
		case 2:
			if(c == 0xe0 && (*p & 0x20) == 0)
				return 0;
			break;

			/* Check for 1111 0000, xx00 xxxx */
		case 3:
			if(c == 0xf0 && (*p & 0x30) == 0)
				return 0;
			break;

			/* Check for 1111 1000, xx00 0xxx */
		case 4:
			if(c == 0xf8 && (*p & 0x38) == 0)
				return 0;
			break;

			/* Check for leading 0xfe or 0xff and then for 1111 1100, xx00 00xx */
		case 5:
			if(c == 0xfe || c == 0xff || (c == 0xfc && (*p & 0x3c) == 0))
				return 0;
			break;
		}

		/* Check for valid bytes after the 2nd, if any; all must start 10 */
		while(--ab > 0)
			if((*(++p) & 0xc0) != 0x80)
				return 0;
	}

	return 1;
}

int
u8_reverse(char *dest, char * src, size_t len)
{
	size_t si = 0, di = len;
	uint8_t c;

	dest[di] = '\0';
	while(si < len){
		c = (uint8_t)src[si];
		if((~c) & 0x80){
			di--;
			dest[di] = c;
			si++;
		}else{
			switch(c>>4){
			case 0xc:
			case 0xd:
				di -= 2;
				*((int16_t*)&dest[di]) = *((int16_t*)&src[si]);
				si += 2;
				break;
			case 0xe:
				di -= 3;
				dest[di] = src[si];
				*((int16_t*)&dest[di+1]) = *((int16_t*)&src[si+1]);
				si += 3;
				break;
			case 0xf:
				di -= 4;
				*((int32_t*)&dest[di]) = *((int32_t*)&src[si]);
				si += 4;
				break;
			default:
				return 1;
			}
		}
	}
	return 0;
}