diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/errors.c | 27 | ||||
| -rw-r--r-- | src/errors.h | 6 | ||||
| -rw-r--r-- | src/lexer.c | 34 | ||||
| -rw-r--r-- | src/lexer.h | 21 | ||||
| -rw-r--r-- | src/main.c | 68 | ||||
| -rw-r--r-- | src/unicode-avx2.c | 152 | ||||
| -rw-r--r-- | src/unicode-neon.c | 147 | ||||
| -rw-r--r-- | src/unicode-sse4_1.c | 158 | ||||
| -rw-r--r-- | src/unicode.c | 59 | ||||
| -rw-r--r-- | src/unicode.h | 17 |
10 files changed, 689 insertions, 0 deletions
diff --git a/src/errors.c b/src/errors.c new file mode 100644 index 0000000..49eb11d --- /dev/null +++ b/src/errors.c @@ -0,0 +1,27 @@ +#include <errno.h> +#include <stdarg.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "errors.h" + +void +err(const char *fmt, ...) +{ + va_list ap; + va_start(ap, fmt); + + int save = errno; + flockfile(stderr); + + fputs("oryx: ", stderr); + vfprintf(stderr, fmt, ap); + if (fmt[strlen(fmt) - 1] == ':') + fprintf(stderr, " %s", strerror(save)); + fputc('\n', stderr); + fflush(stderr); + funlockfile(stderr); + va_end(ap); + exit(EXIT_FAILURE); +} diff --git a/src/errors.h b/src/errors.h new file mode 100644 index 0000000..69c8ea0 --- /dev/null +++ b/src/errors.h @@ -0,0 +1,6 @@ +#ifndef ORYX_ERRORS_H +#define ORYX_ERRORS_H + +void err(const char *, ...); + +#endif /* !ORYX_ERRORS_H */ diff --git a/src/lexer.c b/src/lexer.c new file mode 100644 index 0000000..970202a --- /dev/null +++ b/src/lexer.c @@ -0,0 +1,34 @@ +#include <inttypes.h> +#include <stddef.h> +#include <stdio.h> + +#include "errors.h" +#include "lexer.h" +#include "unicode.h" + +struct lexeme * +lexstring(const char *code, size_t codesz, size_t *lcnt) +{ + struct { + struct lexeme *p; + size_t len, buf; + } data = {0}; + +#if ORYX_SIMD + if (!utf8_validate_simd(code, codesz)) { +#endif + size_t off = utf8_validate_off(code, codesz); + if (off != 0) + err("Invalid UTF-8 at byte-offset %zu", off - 1); +#if ORYX_SIMD + } +#endif + + const char *end = code + codesz; + while (code < end) { + rune ch = utf8_decode(&code); + } + + *lcnt = data.len; + return data.p; +} diff --git a/src/lexer.h b/src/lexer.h new file mode 100644 index 0000000..7271498 --- /dev/null +++ b/src/lexer.h @@ -0,0 +1,21 @@ +#ifndef ORYX_LEXER_H +#define ORYX_LEXER_H + +#include <stddef.h> +#include <stdint.h> + +enum { + LEXIDENT, +}; + +typedef uint8_t lexeme_kind; + +struct lexeme { + lexeme_kind kind; + const char *p; + size_t len; +}; + +struct lexeme *lexstring(const char *, size_t, size_t *); + +#endif /* !ORYX_LEXER_H */ diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..23b0471 --- /dev/null +++ b/src/main.c @@ -0,0 +1,68 @@ +#include <sys/stat.h> + +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> + +#include "errors.h" +#include "lexer.h" + +static char *readfile(const char *, size_t *); + +int +main(int argc, char **argv) +{ + if (argc != 2) { + fputs("Usage: oryx file\n", stderr); + exit(EXIT_FAILURE); + } + + struct { + char *p; + size_t len; + } file = { + .p = readfile(argv[1], &file.len), + }; + + struct { + struct lexeme *p; + size_t len; + } toks = { + .p = lexstring(file.p, file.len, &toks.len), + }; + +#if DEBUG + free(file.p); + free(toks.p); +#endif + return EXIT_SUCCESS; +} + +char * +readfile(const char *filename, size_t *n) +{ + int fd = open(filename, O_RDONLY); + if (fd == -1) + err("open: %s", filename); + + struct stat sb; + if (fstat(fd, &sb) == -1) + err("fstat: %s", filename); + + char *p = malloc(sb.st_size + 4); + if (p == NULL) + err("malloc:"); + + ssize_t nr; + for (size_t off = 0; (nr = read(fd, p + off, sb.st_blksize)) > 0; off += nr) + ; + if (nr == -1) + err("read: %s", filename); + for (int i = 0; i < 4; i++) + p[sb.st_size + i] = 0; + + *n = sb.st_size; + close(fd); + return p; +} diff --git a/src/unicode-avx2.c b/src/unicode-avx2.c new file mode 100644 index 0000000..6507ca2 --- /dev/null +++ b/src/unicode-avx2.c @@ -0,0 +1,152 @@ +#include <stdint.h> +#include <x86intrin.h> + +#include "unicode.h" + +#pragma GCC diagnostic ignored "-Woverflow" + +static const int8_t _first_len_tbl[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, +}; + +static const int8_t _first_range_tbl[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, +}; + +static const int8_t _range_min_tbl[] = { + 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, 0xC2, 0x7F, 0x7F, + 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, + 0x90, 0x80, 0xC2, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, +}; +static const int8_t _range_max_tbl[] = { + 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, 0xF4, 0x80, 0x80, + 0x80, 0x80, 0x80, 0x80, 0x80, 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, + 0xBF, 0x8F, 0xF4, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, +}; + +static const int8_t _df_ee_tbl[] = { + 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, + 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, +}; + +static const int8_t _ef_fe_tbl[] = { + 0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +}; + +static inline __m256i +push_last_byte_of_a_to_b(__m256i a, __m256i b) +{ + return _mm256_alignr_epi8(b, _mm256_permute2x128_si256(a, b, 0x21), 15); +} + +static inline __m256i +push_last_2bytes_of_a_to_b(__m256i a, __m256i b) +{ + return _mm256_alignr_epi8(b, _mm256_permute2x128_si256(a, b, 0x21), 14); +} + +static inline __m256i +push_last_3bytes_of_a_to_b(__m256i a, __m256i b) +{ + return _mm256_alignr_epi8(b, _mm256_permute2x128_si256(a, b, 0x21), 13); +} + +bool +utf8_validate_simd(const char *data, size_t len) +{ + const unsigned char *s = data; + if (len >= 32) { + __m256i prev_input = _mm256_set1_epi8(0); + __m256i prev_first_len = _mm256_set1_epi8(0); + + const __m256i first_len_tbl = _mm256_loadu_si256( + (const __m256i *)_first_len_tbl); + const __m256i first_range_tbl = _mm256_loadu_si256( + (const __m256i *)_first_range_tbl); + const __m256i range_min_tbl = _mm256_loadu_si256( + (const __m256i *)_range_min_tbl); + const __m256i range_max_tbl = _mm256_loadu_si256( + (const __m256i *)_range_max_tbl); + const __m256i df_ee_tbl = _mm256_loadu_si256( + (const __m256i *)_df_ee_tbl); + const __m256i ef_fe_tbl = _mm256_loadu_si256( + (const __m256i *)_ef_fe_tbl); + + __m256i error1 = _mm256_set1_epi8(0); + __m256i error2 = _mm256_set1_epi8(0); + + while (len >= 32) { + const __m256i input = _mm256_loadu_si256((const __m256i *)s); + + const __m256i high_nibbles = _mm256_and_si256( + _mm256_srli_epi16(input, 4), _mm256_set1_epi8(0x0F)); + + __m256i first_len = _mm256_shuffle_epi8(first_len_tbl, + high_nibbles); + + __m256i range = _mm256_shuffle_epi8(first_range_tbl, high_nibbles); + + range = _mm256_or_si256( + range, push_last_byte_of_a_to_b(prev_first_len, first_len)); + + __m256i tmp1, tmp2; + + tmp1 = push_last_2bytes_of_a_to_b(prev_first_len, first_len); + tmp2 = _mm256_subs_epu8(tmp1, _mm256_set1_epi8(1)); + + range = _mm256_or_si256(range, tmp2); + + tmp1 = push_last_3bytes_of_a_to_b(prev_first_len, first_len); + tmp2 = _mm256_subs_epu8(tmp1, _mm256_set1_epi8(2)); + range = _mm256_or_si256(range, tmp2); + + __m256i shift1, pos, range2; + + shift1 = push_last_byte_of_a_to_b(prev_input, input); + pos = _mm256_sub_epi8(shift1, _mm256_set1_epi8(0xEF)); + + tmp1 = _mm256_subs_epu8(pos, _mm256_set1_epi8(240)); + range2 = _mm256_shuffle_epi8(df_ee_tbl, tmp1); + tmp2 = _mm256_adds_epu8(pos, _mm256_set1_epi8(112)); + range2 = _mm256_add_epi8(range2, + _mm256_shuffle_epi8(ef_fe_tbl, tmp2)); + + range = _mm256_add_epi8(range, range2); + + __m256i minv = _mm256_shuffle_epi8(range_min_tbl, range); + __m256i maxv = _mm256_shuffle_epi8(range_max_tbl, range); + + error1 = _mm256_or_si256(error1, _mm256_cmpgt_epi8(minv, input)); + error2 = _mm256_or_si256(error2, _mm256_cmpgt_epi8(input, maxv)); + + prev_input = input; + prev_first_len = first_len; + + s += 32; + len -= 32; + } + + __m256i error = _mm256_or_si256(error1, error2); + if (!_mm256_testz_si256(error, error)) + return false; + + int32_t token4 = _mm256_extract_epi32(prev_input, 7); + const int8_t *token = (const int8_t *)&token4; + int lookahead = 0; + if (token[3] > (int8_t)0xBF) + lookahead = 1; + else if (token[2] > (int8_t)0xBF) + lookahead = 2; + else if (token[1] > (int8_t)0xBF) + lookahead = 3; + + s -= lookahead; + len += lookahead; + } + + /* Check remaining bytes with naïve method */ + return utf8_validate_off(s, len) == 0; +} diff --git a/src/unicode-neon.c b/src/unicode-neon.c new file mode 100644 index 0000000..2791117 --- /dev/null +++ b/src/unicode-neon.c @@ -0,0 +1,147 @@ +#include <arm_neon.h> +#include <stdint.h> + +#include "unicode.h" + +#pragma GCC diagnostic ignored "-Woverflow" + +static const uint8_t _first_len_tbl[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, +}; + +static const uint8_t _first_range_tbl[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, +}; + +static const uint8_t _range_min_tbl[] = { + 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, + 0xC2, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, +}; +static const uint8_t _range_max_tbl[] = { + 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, + 0xF4, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, +}; + +static const uint8_t _range_adjust_tbl[] = { + 2, 3, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, +}; + +bool +utf8_validate_simd(const char *data, size_t len) +{ + const unsigned char *s = data; + if (len >= 32) { + uint8x16_t prev_input = vdupq_n_u8(0); + uint8x16_t prev_first_len = vdupq_n_u8(0); + + const uint8x16_t first_len_tbl = vld1q_u8(_first_len_tbl); + const uint8x16_t first_range_tbl = vld1q_u8(_first_range_tbl); + const uint8x16_t range_min_tbl = vld1q_u8(_range_min_tbl); + const uint8x16_t range_max_tbl = vld1q_u8(_range_max_tbl); + const uint8x16x2_t range_adjust_tbl = vld2q_u8(_range_adjust_tbl); + + const uint8x16_t const_1 = vdupq_n_u8(1); + const uint8x16_t const_2 = vdupq_n_u8(2); + const uint8x16_t const_e0 = vdupq_n_u8(0xE0); + + uint8x16_t error1 = vdupq_n_u8(0); + uint8x16_t error2 = vdupq_n_u8(0); + uint8x16_t error3 = vdupq_n_u8(0); + uint8x16_t error4 = vdupq_n_u8(0); + + while (len >= 32) { +#if defined(__GNUC__) && !defined(__clang__) && (__GNUC__ < 8) + /* GCC doesn't support vldq1_u8_x2 until version 8 */ + const uint8x16_t input_a = vld1q_u8(data); + const uint8x16_t input_b = vld1q_u8(data + 16); +#else + /* Forces a double load on Clang */ + const uint8x16x2_t input_pair = vld1q_u8_x2(s); + const uint8x16_t input_a = input_pair.val[0]; + const uint8x16_t input_b = input_pair.val[1]; +#endif + + const uint8x16_t high_nibbles_a = vshrq_n_u8(input_a, 4); + const uint8x16_t high_nibbles_b = vshrq_n_u8(input_b, 4); + + const uint8x16_t first_len_a = vqtbl1q_u8(first_len_tbl, + high_nibbles_a); + const uint8x16_t first_len_b = vqtbl1q_u8(first_len_tbl, + high_nibbles_b); + + uint8x16_t range_a = vqtbl1q_u8(first_range_tbl, high_nibbles_a); + uint8x16_t range_b = vqtbl1q_u8(first_range_tbl, high_nibbles_b); + + range_a = vorrq_u8(range_a, + vextq_u8(prev_first_len, first_len_a, 15)); + range_b = vorrq_u8(range_b, vextq_u8(first_len_a, first_len_b, 15)); + + uint8x16_t tmp1_a, tmp2_a, tmp1_b, tmp2_b; + tmp1_a = vextq_u8(prev_first_len, first_len_a, 14); + tmp1_a = vqsubq_u8(tmp1_a, const_1); + range_a = vorrq_u8(range_a, tmp1_a); + + tmp1_b = vextq_u8(first_len_a, first_len_b, 14); + tmp1_b = vqsubq_u8(tmp1_b, const_1); + range_b = vorrq_u8(range_b, tmp1_b); + + tmp2_a = vextq_u8(prev_first_len, first_len_a, 13); + tmp2_a = vqsubq_u8(tmp2_a, const_2); + range_a = vorrq_u8(range_a, tmp2_a); + + tmp2_b = vextq_u8(first_len_a, first_len_b, 13); + tmp2_b = vqsubq_u8(tmp2_b, const_2); + range_b = vorrq_u8(range_b, tmp2_b); + + uint8x16_t shift1_a = vextq_u8(prev_input, input_a, 15); + uint8x16_t pos_a = vsubq_u8(shift1_a, const_e0); + range_a = vaddq_u8(range_a, vqtbl2q_u8(range_adjust_tbl, pos_a)); + + uint8x16_t shift1_b = vextq_u8(input_a, input_b, 15); + uint8x16_t pos_b = vsubq_u8(shift1_b, const_e0); + range_b = vaddq_u8(range_b, vqtbl2q_u8(range_adjust_tbl, pos_b)); + + uint8x16_t minv_a = vqtbl1q_u8(range_min_tbl, range_a); + uint8x16_t maxv_a = vqtbl1q_u8(range_max_tbl, range_a); + + uint8x16_t minv_b = vqtbl1q_u8(range_min_tbl, range_b); + uint8x16_t maxv_b = vqtbl1q_u8(range_max_tbl, range_b); + + error1 = vorrq_u8(error1, vcltq_u8(input_a, minv_a)); + error2 = vorrq_u8(error2, vcgtq_u8(input_a, maxv_a)); + + error3 = vorrq_u8(error3, vcltq_u8(input_b, minv_b)); + error4 = vorrq_u8(error4, vcgtq_u8(input_b, maxv_b)); + + prev_input = input_b; + prev_first_len = first_len_b; + + s += 32; + len -= 32; + } + error1 = vorrq_u8(error1, error2); + error1 = vorrq_u8(error1, error3); + error1 = vorrq_u8(error1, error4); + + if (vmaxvq_u8(error1)) + return -1; + + uint32_t token4; + vst1q_lane_u32(&token4, vreinterpretq_u32_u8(prev_input), 3); + + const int8_t *token = (const int8_t *)&token4; + int lookahead = 0; + if (token[3] > (int8_t)0xBF) + lookahead = 1; + else if (token[2] > (int8_t)0xBF) + lookahead = 2; + else if (token[1] > (int8_t)0xBF) + lookahead = 3; + + s -= lookahead; + len += lookahead; + } + + return utf8_validate_off(s, len) == 0; +} diff --git a/src/unicode-sse4_1.c b/src/unicode-sse4_1.c new file mode 100644 index 0000000..17a46a8 --- /dev/null +++ b/src/unicode-sse4_1.c @@ -0,0 +1,158 @@ +#include <stddef.h> +#include <stdint.h> +#include <x86intrin.h> + +#include "unicode.h" + +#pragma GCC diagnostic ignored "-Woverflow" + +static const int8_t _first_len_tbl[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 3, +}; + +static const int8_t _first_range_tbl[] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, 8, +}; + +static const int8_t _range_min_tbl[] = { + 0x00, 0x80, 0x80, 0x80, 0xA0, 0x80, 0x90, 0x80, + 0xC2, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, 0x7F, +}; +static const int8_t _range_max_tbl[] = { + 0x7F, 0xBF, 0xBF, 0xBF, 0xBF, 0x9F, 0xBF, 0x8F, + 0xF4, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, +}; + +static const int8_t _df_ee_tbl[] = { + 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, +}; +static const int8_t _ef_fe_tbl[] = { + 0, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, +}; + +/* Return 0 on success, -1 on error */ +bool +utf8_validate_simd(const char *data, size_t len) +{ + const unsigned char *s = data; + if (len >= 32) { + __m128i prev_input = _mm_set1_epi8(0); + __m128i prev_first_len = _mm_set1_epi8(0); + + const __m128i first_len_tbl = _mm_loadu_si128( + (const __m128i *)_first_len_tbl); + const __m128i first_range_tbl = _mm_loadu_si128( + (const __m128i *)_first_range_tbl); + const __m128i range_min_tbl = _mm_loadu_si128( + (const __m128i *)_range_min_tbl); + const __m128i range_max_tbl = _mm_loadu_si128( + (const __m128i *)_range_max_tbl); + const __m128i df_ee_tbl = _mm_loadu_si128((const __m128i *)_df_ee_tbl); + const __m128i ef_fe_tbl = _mm_loadu_si128((const __m128i *)_ef_fe_tbl); + + __m128i error = _mm_set1_epi8(0); + + while (len >= 32) { + /***************************** block 1 ****************************/ + const __m128i input_a = _mm_loadu_si128((const __m128i *)s); + + __m128i high_nibbles = _mm_and_si128(_mm_srli_epi16(input_a, 4), + _mm_set1_epi8(0x0F)); + + __m128i first_len_a = _mm_shuffle_epi8(first_len_tbl, high_nibbles); + + __m128i range_a = _mm_shuffle_epi8(first_range_tbl, high_nibbles); + + range_a = _mm_or_si128( + range_a, _mm_alignr_epi8(first_len_a, prev_first_len, 15)); + + __m128i tmp; + tmp = _mm_alignr_epi8(first_len_a, prev_first_len, 14); + tmp = _mm_subs_epu8(tmp, _mm_set1_epi8(1)); + range_a = _mm_or_si128(range_a, tmp); + + tmp = _mm_alignr_epi8(first_len_a, prev_first_len, 13); + tmp = _mm_subs_epu8(tmp, _mm_set1_epi8(2)); + range_a = _mm_or_si128(range_a, tmp); + + __m128i shift1, pos, range2; + shift1 = _mm_alignr_epi8(input_a, prev_input, 15); + pos = _mm_sub_epi8(shift1, _mm_set1_epi8(0xEF)); + tmp = _mm_subs_epu8(pos, _mm_set1_epi8(0xF0)); + range2 = _mm_shuffle_epi8(df_ee_tbl, tmp); + tmp = _mm_adds_epu8(pos, _mm_set1_epi8(0x70)); + range2 = _mm_add_epi8(range2, _mm_shuffle_epi8(ef_fe_tbl, tmp)); + + range_a = _mm_add_epi8(range_a, range2); + + __m128i minv = _mm_shuffle_epi8(range_min_tbl, range_a); + __m128i maxv = _mm_shuffle_epi8(range_max_tbl, range_a); + + tmp = _mm_or_si128(_mm_cmplt_epi8(input_a, minv), + _mm_cmpgt_epi8(input_a, maxv)); + error = _mm_or_si128(error, tmp); + + /***************************** block 2 ****************************/ + const __m128i input_b = _mm_loadu_si128((const __m128i *)(s + 16)); + + high_nibbles = _mm_and_si128(_mm_srli_epi16(input_b, 4), + _mm_set1_epi8(0x0F)); + + __m128i first_len_b = _mm_shuffle_epi8(first_len_tbl, high_nibbles); + + __m128i range_b = _mm_shuffle_epi8(first_range_tbl, high_nibbles); + + range_b = _mm_or_si128( + range_b, _mm_alignr_epi8(first_len_b, first_len_a, 15)); + + tmp = _mm_alignr_epi8(first_len_b, first_len_a, 14); + tmp = _mm_subs_epu8(tmp, _mm_set1_epi8(1)); + range_b = _mm_or_si128(range_b, tmp); + + tmp = _mm_alignr_epi8(first_len_b, first_len_a, 13); + tmp = _mm_subs_epu8(tmp, _mm_set1_epi8(2)); + range_b = _mm_or_si128(range_b, tmp); + + shift1 = _mm_alignr_epi8(input_b, input_a, 15); + pos = _mm_sub_epi8(shift1, _mm_set1_epi8(0xEF)); + tmp = _mm_subs_epu8(pos, _mm_set1_epi8(0xF0)); + range2 = _mm_shuffle_epi8(df_ee_tbl, tmp); + tmp = _mm_adds_epu8(pos, _mm_set1_epi8(0x70)); + range2 = _mm_add_epi8(range2, _mm_shuffle_epi8(ef_fe_tbl, tmp)); + + range_b = _mm_add_epi8(range_b, range2); + + minv = _mm_shuffle_epi8(range_min_tbl, range_b); + maxv = _mm_shuffle_epi8(range_max_tbl, range_b); + + tmp = _mm_or_si128(_mm_cmplt_epi8(input_b, minv), + _mm_cmpgt_epi8(input_b, maxv)); + error = _mm_or_si128(error, tmp); + + /************************ next iteration **************************/ + prev_input = input_b; + prev_first_len = first_len_b; + + s += 32; + len -= 32; + } + + if (!_mm_testz_si128(error, error)) + return false; + + int32_t token4 = _mm_extract_epi32(prev_input, 3); + const int8_t *token = (const int8_t *)&token4; + int lookahead = 0; + if (token[3] > (int8_t)0xBF) + lookahead = 1; + else if (token[2] > (int8_t)0xBF) + lookahead = 2; + else if (token[1] > (int8_t)0xBF) + lookahead = 3; + + s -= lookahead; + len += lookahead; + } + + return utf8_validate_off(s, len) == 0; +} diff --git a/src/unicode.c b/src/unicode.c new file mode 100644 index 0000000..e1faa55 --- /dev/null +++ b/src/unicode.c @@ -0,0 +1,59 @@ +#include "unicode.h" + +/* Branchless UTF-8 decoding and validation by Christopher Wellons. + + You can find the original source with comments at + https://github.com/skeeto/branchless-utf8. */ + +static const char lengths[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 3, 3, 4, 0}; +static const rune mins[] = {RUNE_C(4194304), 0, 128, 2048, RUNE_C(65536)}; +static const int masks[] = {0x00, 0x7f, 0x1f, 0x0f, 0x07}; +static const int shiftc[] = {0, 18, 12, 6, 0}; +static const int shifte[] = {0, 6, 4, 2, 0}; + +rune +utf8_decode(const char **buf) +{ + const unsigned char *s = *buf; + int len = lengths[s[0] >> 3]; + *buf = s + len + !len; + + rune c = (rune)(s[0] & masks[len]) << 18; + c |= (rune)(s[1] & 0x3f) << 12; + c |= (rune)(s[2] & 0x3f) << 6; + c |= (rune)(s[3] & 0x3f) << 0; + return c >> shiftc[len]; +} + +size_t +utf8_validate_off(const char *buf, size_t len) +{ + const char *start = buf, *end = start + len; + while (buf < end) { + const unsigned char *s = buf; + int len = lengths[s[0] >> 3]; + + const unsigned char *next = s + len + !len; + + rune c = (rune)(s[0] & masks[len]) << 18; + c |= (rune)(s[1] & 0x3f) << 12; + c |= (rune)(s[2] & 0x3f) << 6; + c |= (rune)(s[3] & 0x3f) << 0; + c >>= shiftc[len]; + + int e = (c < mins[len]) << 6; + e |= ((c >> 11) == 0x1B) << 7; + e |= (c > 0x10FFFF) << 8; + e |= (s[1] & 0xC0) >> 2; + e |= (s[2] & 0xC0) >> 4; + e |= (s[3]) >> 6; + e ^= 0x2A; + e >>= shifte[len]; + if (e != 0) + return buf - start + 1; + buf = next; + } + + return 0; +} diff --git a/src/unicode.h b/src/unicode.h new file mode 100644 index 0000000..701c8c7 --- /dev/null +++ b/src/unicode.h @@ -0,0 +1,17 @@ +#ifndef ORYX_UNICODE_H +#define ORYX_UNICODE_H + +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> + +#define RUNE_C(x) UINT32_C(x) +typedef uint32_t rune; + +rune utf8_decode(const char **); +size_t utf8_validate_off(const char *, size_t); +#if ORYX_SIMD +bool utf8_validate_simd(const char *, size_t); +#endif + +#endif /* !ORYX_UNICODE_H */ |