git.iko.soy/text
on 3cf8564 help sign in
text/cbits/cbits.c
210 lines 6.2 kB history raw
1/*
2 * Copyright (c) 2011 Bryan O'Sullivan <bos@serpentine.com>.
3 *
4 * Portions copyright (c) 2008-2010 Björn Höhrmann <bjoern@hoehrmann.de>.
5 *
6 * See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.
7 */
9#include <string.h>
10#include <stdint.h>
11#include <stdio.h>
12#include "text_cbits.h"
14void _hs_text_memcpy(void *dest, size_t doff, const void *src, size_t soff,
15 size_t n)
17 memcpy(dest + (doff<<1), src + (soff<<1), n<<1);
20int _hs_text_memcmp(const void *a, size_t aoff, const void *b, size_t boff,
21 size_t n)
23 return memcmp(a + (aoff<<1), b + (boff<<1), n<<1);
26#define UTF8_ACCEPT 0
27#define UTF8_REJECT 12
29static const uint8_t utf8d[] = {
30 /*
31 * The first part of the table maps bytes to character classes that
32 * to reduce the size of the transition table and create bitmasks.
33 */
34 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,
35 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,
36 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,
37 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,
38 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
39 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
40 8,8,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,
41 10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8,
43 /*
44 * The second part is a transition table that maps a combination of
45 * a state of the automaton and a character class to a state.
46 */
47 0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,
48 12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,
49 12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,
50 12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,
51 12,36,12,12,12,12,12,12,12,12,12,12,
52};
54static inline uint32_t
55decode(uint32_t *state, uint32_t* codep, uint32_t byte) {
56 uint32_t type = utf8d[byte];
58 *codep = (*state != UTF8_ACCEPT) ?
59 (byte & 0x3fu) | (*codep << 6) :
60 (0xff >> type) & (byte);
62 return *state = utf8d[256 + *state + type];
65/*
66 * The ISO 8859-1 (aka latin-1) code points correspond exactly to the first 256 unicode
67 * code-points, therefore we can trivially convert from a latin-1 encoded bytestring to
68 * an UTF16 array
69 */
70void
71_hs_text_decode_latin1(uint16_t *dest, const uint8_t const *src,
72 const uint8_t const *srcend)
74 const uint8_t *p = src;
76#if defined(__i386__) || defined(__x86_64__)
77 /* This optimization works on a little-endian systems by using
78 (aligned) 32-bit loads instead of 8-bit loads
79 */
81 /* consume unaligned prefix */
82 while (p != srcend && (uintptr_t)p & 0x3)
83 *dest++ = *p++;
85 /* iterate over 32-bit aligned loads */
86 while (p < srcend - 3) {
87 const uint32_t w = *((const uint32_t *)p);
89 *dest++ = w & 0xff;
90 *dest++ = (w >> 8) & 0xff;
91 *dest++ = (w >> 16) & 0xff;
92 *dest++ = (w >> 24) & 0xff;
94 p += 4;
95 }
96#endif
98 /* handle unaligned suffix */
99 while (p != srcend)
100 *dest++ = *p++;
103/*
104 * A best-effort decoder. Runs until it hits either end of input or
105 * the start of an invalid byte sequence.
106 *
107 * At exit, we update *destoff with the next offset to write to, *src
108 * with the next source location past the last one successfully
109 * decoded, and return the next source location to read from.
110 *
111 * Moreover, we expose the internal decoder state (state0 and
112 * codepoint0), allowing one to restart the decoder after it
113 * terminates (say, due to a partial codepoint).
114 *
115 * In particular, there are a few possible outcomes,
116 *
117 * 1) We decoded the buffer entirely:
118 * In this case we return srcend
119 * state0 == UTF8_ACCEPT
120 *
121 * 2) We met an invalid encoding
122 * In this case we return the address of the first invalid byte
123 * state0 == UTF8_REJECT
124 *
125 * 3) We reached the end of the buffer while decoding a codepoint
126 * In this case we return a pointer to the first byte of the partial codepoint
127 * state0 != UTF8_ACCEPT, UTF8_REJECT
128 *
129 */
130const uint8_t *
131_hs_text_decode_utf8_state(uint16_t *const dest, size_t *destoff,
132 const uint8_t **const src,
133 const uint8_t *const srcend,
134 uint32_t *codepoint0, uint32_t *state0)
136 uint16_t *d = dest + *destoff;
137 const uint8_t *s = *src, *last = *src;
138 uint32_t state = *state0;
139 uint32_t codepoint = *codepoint0;
141 while (s < srcend) {
142#if defined(__i386__) || defined(__x86_64__)
143 /*
144 * This code will only work on a little-endian system that
145 * supports unaligned loads.
146 *
147 * It gives a substantial speed win on data that is purely or
148 * partly ASCII (e.g. HTML), at only a slight cost on purely
149 * non-ASCII text.
150 */
152 if (state == UTF8_ACCEPT) {
153 while (s < srcend - 4) {
154 codepoint = *((uint32_t *) s);
155 if ((codepoint & 0x80808080) != 0)
156 break;
157 s += 4;
159 /*
160 * Tried 32-bit stores here, but the extra bit-twiddling
161 * slowed the code down.
162 */
164 *d++ = (uint16_t) (codepoint & 0xff);
165 *d++ = (uint16_t) ((codepoint >> 8) & 0xff);
166 *d++ = (uint16_t) ((codepoint >> 16) & 0xff);
167 *d++ = (uint16_t) ((codepoint >> 24) & 0xff);
168 }
169 last = s;
170 }
171#endif
173 if (decode(&state, &codepoint, *s++) != UTF8_ACCEPT) {
174 if (state != UTF8_REJECT)
175 continue;
176 break;
177 }
179 if (codepoint <= 0xffff)
180 *d++ = (uint16_t) codepoint;
181 else {
182 *d++ = (uint16_t) (0xD7C0 + (codepoint >> 10));
183 *d++ = (uint16_t) (0xDC00 + (codepoint & 0x3FF));
184 }
185 last = s;
186 }
188 /* Invalid encoding, back up to the errant character */
189 if (state == UTF8_REJECT)
190 s -= 1;
192 *destoff = d - dest;
193 *codepoint0 = codepoint;
194 *state0 = state;
195 *src = last;
197 return s;
200/*
201 * Helper to decode buffer and discard final decoder state
202 */
203const uint8_t *
204_hs_text_decode_utf8(uint16_t *const dest, size_t *destoff,
205 const uint8_t *src, const uint8_t *const srcend)
207 uint32_t codepoint;
208 uint32_t state = UTF8_ACCEPT;
209 return _hs_text_decode_utf8_state(dest, destoff, &src, srcend, &codepoint, &state);