/*
* utf_validate.c: Validate a UTF-8 string
*
* ====================================================================
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
* ====================================================================
*/
/* Validate a UTF-8 string according to the rules in
*
* Table 3-6. Well-Formed UTF-8 Bytes Sequences
*
* in
*
* The Unicode Standard, Version 4.0
*
* which is available at
*
* http://www.unicode.org/
*
* UTF-8 was originally defined in RFC-2279, Unicode's "well-formed UTF-8"
* is a subset of that enconding. The Unicode enconding prohibits things
* like non-shortest encodings (some characters can be represented by more
* than one multi-byte encoding) and the encodings for the surrogate code
* points. RFC-3629 superceeds RFC-2279 and adopts the same well-formed
* rules as Unicode. This is the ABNF in RFC-3629 that describes
* well-formed UTF-8 rules:
*
* UTF8-octets = *( UTF8-char )
* UTF8-char = UTF8-1 / UTF8-2 / UTF8-3 / UTF8-4
* UTF8-1 = %x00-7F
* UTF8-2 = %xC2-DF UTF8-tail
* UTF8-3 = %xE0 %xA0-BF UTF8-tail /
* %xE1-EC 2( UTF8-tail ) /
* %xED %x80-9F UTF8-tail /
* %xEE-EF 2( UTF8-tail )
* UTF8-4 = %xF0 %x90-BF 2( UTF8-tail ) /
* %xF1-F3 3( UTF8-tail ) /
* %xF4 %x80-8F 2( UTF8-tail )
* UTF8-tail = %x80-BF
*
*/
#include "private/svn_utf_private.h"
#include "private/svn_eol_private.h"
#include "private/svn_dep_compat.h"
/* Lookup table to categorise each octet in the string. */
static const char octet_category[256] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /* 0x00-0x7f */
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, /* 0x80-0x8f */
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, /* 0x90-0x9f */
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, /* 0xa0-0xbf */
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, /* 0xc0-0xc1 */
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, /* 0xc2-0xdf */
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
6, /* 0xe0 */
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, /* 0xe1-0xec */
8, /* 0xed */
9, 9, /* 0xee-0xef */
10, /* 0xf0 */
11, 11, 11, /* 0xf1-0xf3 */
12, /* 0xf4 */
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13 /* 0xf5-0xff */
};
/* Machine states */
#define FSM_START 0
#define FSM_80BF 1
#define FSM_A0BF 2
#define FSM_80BF80BF 3
#define FSM_809F 4
#define FSM_90BF 5
#define FSM_80BF80BF80BF 6
#define FSM_808F 7
#define FSM_ERROR 8
/* In the FSM it appears that categories 0xc0-0xc1 and 0xf5-0xff make the
same transitions, as do categories 0xe1-0xec and 0xee-0xef. I wonder if
there is any great benefit in combining categories? It would reduce the
memory footprint of the transition table by 16 bytes, but might it be
harder to understand? */
/* Machine transition table */
static const char machine [9][14] = {
/* FSM_START */
{FSM_START, /* 0x00-0x7f */
FSM_ERROR, /* 0x80-0x8f */
FSM_ERROR, /* 0x90-0x9f */
FSM_ERROR, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_80BF, /* 0xc2-0xdf */
FSM_A0BF, /* 0xe0 */
FSM_80BF80BF, /* 0xe1-0xec */
FSM_809F, /* 0xed */
FSM_80BF80BF, /* 0xee-0xef */
FSM_90BF, /* 0xf0 */
FSM_80BF80BF80BF, /* 0xf1-0xf3 */
FSM_808F, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_80BF */
{FSM_ERROR, /* 0x00-0x7f */
FSM_START, /* 0x80-0x8f */
FSM_START, /* 0x90-0x9f */
FSM_START, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_A0BF */
{FSM_ERROR, /* 0x00-0x7f */
FSM_ERROR, /* 0x80-0x8f */
FSM_ERROR, /* 0x90-0x9f */
FSM_80BF, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_80BF80BF */
{FSM_ERROR, /* 0x00-0x7f */
FSM_80BF, /* 0x80-0x8f */
FSM_80BF, /* 0x90-0x9f */
FSM_80BF, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_809F */
{FSM_ERROR, /* 0x00-0x7f */
FSM_80BF, /* 0x80-0x8f */
FSM_80BF, /* 0x90-0x9f */
FSM_ERROR, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_90BF */
{FSM_ERROR, /* 0x00-0x7f */
FSM_ERROR, /* 0x80-0x8f */
FSM_80BF80BF, /* 0x90-0x9f */
FSM_80BF80BF, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_80BF80BF80BF */
{FSM_ERROR, /* 0x00-0x7f */
FSM_80BF80BF, /* 0x80-0x8f */
FSM_80BF80BF, /* 0x90-0x9f */
FSM_80BF80BF, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_808F */
{FSM_ERROR, /* 0x00-0x7f */
FSM_80BF80BF, /* 0x80-0x8f */
FSM_ERROR, /* 0x90-0x9f */
FSM_ERROR, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
/* FSM_ERROR */
{FSM_ERROR, /* 0x00-0x7f */
FSM_ERROR, /* 0x80-0x8f */
FSM_ERROR, /* 0x90-0x9f */
FSM_ERROR, /* 0xa0-0xbf */
FSM_ERROR, /* 0xc0-0xc1 */
FSM_ERROR, /* 0xc2-0xdf */
FSM_ERROR, /* 0xe0 */
FSM_ERROR, /* 0xe1-0xec */
FSM_ERROR, /* 0xed */
FSM_ERROR, /* 0xee-0xef */
FSM_ERROR, /* 0xf0 */
FSM_ERROR, /* 0xf1-0xf3 */
FSM_ERROR, /* 0xf4 */
FSM_ERROR}, /* 0xf5-0xff */
};
/* Scan MAX_LEN bytes in *DATA for chars that are not in the octet
* category 0 (FSM_START). Return the position of the first such char
* or DATA + MAX_LEN if all were cat 0.
*/
static const char *
first_non_fsm_start_char(const char *data, apr_size_t max_len)
{
#if SVN_UNALIGNED_ACCESS_IS_OK
/* Scan the input one machine word at a time. */
for (; max_len > sizeof(apr_uintptr_t)
; data += sizeof(apr_uintptr_t), max_len -= sizeof(apr_uintptr_t))
if (*(const apr_uintptr_t *)data & SVN__BIT_7_SET)
break;
#endif
/* The remaining odd bytes will be examined the naive way: */
for (; max_len > 0; ++data, --max_len)
if ((unsigned char)*data >= 0x80)
break;
return data;
}
const char *
svn_utf__last_valid(const char *data, apr_size_t len)
{
const char *start = first_non_fsm_start_char(data, len);
const char *end = data + len;
int state = FSM_START;
data = start;
while (data < end)
{
unsigned char octet = *data++;
int category = octet_category[octet];
state = machine[state][category];
if (state == FSM_START)
start = data;
}
return start;
}
svn_boolean_t
svn_utf__cstring_is_valid(const char *data)
{
if (!data)
return FALSE;
return svn_utf__is_valid(data, strlen(data));
}
svn_boolean_t
svn_utf__is_valid(const char *data, apr_size_t len)
{
const char *end = data + len;
int state = FSM_START;
if (!data)
return FALSE;
data = first_non_fsm_start_char(data, len);
while (data < end)
{
unsigned char octet = *data++;
int category = octet_category[octet];
state = machine[state][category];
}
return state == FSM_START;
}
const char *
svn_utf__last_valid2(const char *data, apr_size_t len)
{
const char *start = first_non_fsm_start_char(data, len);
const char *end = data + len;
int state = FSM_START;
data = start;
while (data < end)
{
unsigned char octet = *data++;
switch (state)
{
case FSM_START:
if (octet <= 0x7F)
break;
else if (octet <= 0xC1)
state = FSM_ERROR;
else if (octet <= 0xDF)
state = FSM_80BF;
else if (octet == 0xE0)
state = FSM_A0BF;
else if (octet <= 0xEC)
state = FSM_80BF80BF;
else if (octet == 0xED)
state = FSM_809F;
else if (octet <= 0xEF)
state = FSM_80BF80BF;
else if (octet == 0xF0)
state = FSM_90BF;
else if (octet <= 0xF3)
state = FSM_80BF80BF80BF;
else if (octet <= 0xF4)
state = FSM_808F;
else
state = FSM_ERROR;
break;
case FSM_80BF:
if (octet >= 0x80 && octet <= 0xBF)
state = FSM_START;
else
state = FSM_ERROR;
break;
case FSM_A0BF:
if (octet >= 0xA0 && octet <= 0xBF)
state = FSM_80BF;
else
state = FSM_ERROR;
break;
case FSM_80BF80BF:
if (octet >= 0x80 && octet <= 0xBF)
state = FSM_80BF;
else
state = FSM_ERROR;
break;
case FSM_809F:
if (octet >= 0x80 && octet <= 0x9F)
state = FSM_80BF;
else
state = FSM_ERROR;
break;
case FSM_90BF:
if (octet >= 0x90 && octet <= 0xBF)
state = FSM_80BF80BF;
else
state = FSM_ERROR;
break;
case FSM_80BF80BF80BF:
if (octet >= 0x80 && octet <= 0xBF)
state = FSM_80BF80BF;
else
state = FSM_ERROR;
break;
case FSM_808F:
if (octet >= 0x80 && octet <= 0x8F)
state = FSM_80BF80BF;
else
state = FSM_ERROR;
break;
default:
case FSM_ERROR:
return start;
}
if (state == FSM_START)
start = data;
}
return start;
}