2 * Copyright 1997, 1998, 1999 Computing Research Labs,
3 * New Mexico State University
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY
19 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
20 * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
21 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 static char rcsid[] = "$Id: utbm.c,v 1.1 1999/09/21 15:45:17 mleisher Exp $";
29 * 1. Case conversions of UTF-16 characters must also be UTF-16 characters.
30 * 2. Case conversions are all one-to-one.
31 * 3. Text and pattern have already been normalized in some fashion.
40 * Single pattern character.
53 typedef struct _utbm_pattern_t {
57 unsigned long pat_used;
58 unsigned long pat_size;
62 unsigned long skip_used;
63 unsigned long skip_size;
68 /*************************************************************************
72 *************************************************************************/
75 * Routine to look up the skip value for a character.
78 _utbm_skip(utbm_pattern_t p, ucs2_t *start, ucs2_t *end)
88 c2 = (start + 1 < end) ? *(start + 1) : ~0;
89 if (0xd800 <= c1 && c1 <= 0xdbff && 0xdc00 <= c2 && c2 <= 0xdfff)
90 c1 = 0x10000 + (((c1 & 0x03ff) << 10) | (c2 & 0x03ff));
92 for (i = 0, sp = p->skip; i < p->skip_used; i++, sp++) {
93 if (!((c1 ^ sp->ch->uc) & (c1 ^ sp->ch->lc) & (c1 ^ sp->ch->tc))) {
94 return ((unsigned long) (end - start) < sp->skip) ?
95 end - start : sp->skip;
102 _utbm_match(utbm_pattern_t pat, ucs2_t *text, ucs2_t *start, ucs2_t *end,
103 unsigned long *match_start, unsigned long *match_end)
111 * Set the potential match endpoint first.
113 *match_end = (start - text) + 1;
116 c2 = (start + 1 < end) ? *(start + 1) : ~0;
117 if (0xd800 <= c1 && c1 <= 0xdbff && 0xdc00 <= c2 && c2 <= 0xdfff) {
118 c1 = 0x10000 + (((c1 & 0x03ff) << 10) | (c2 & 0x03ff));
120 * Adjust the match end point to occur after the UTF-16 character.
122 *match_end = *match_end + 1;
125 if (pat->pat_used == 1) {
126 *match_start = start - text;
133 cp = pat->pat + (pat->pat_used - 1);
135 for (count = pat->patlen; start > text && count > 0;) {
137 * Ignore non-spacing characters if indicated.
139 if (pat->flags & UTBM_IGNORE_NONSPACING) {
140 while (start > text && _utbm_nonspacing(c1)) {
142 c1 = (start - 1 > text) ? *(start - 1) : ~0;
143 if (0xdc00 <= c2 && c2 <= 0xdfff &&
144 0xd800 <= c1 && c1 <= 0xdbff) {
145 c1 = 0x10000 + (((c1 & 0x03ff) << 10) | (c2 & 0x03ff));
153 * Handle space compression if indicated.
155 if (pat->flags & UTBM_SPACE_COMPRESS) {
157 while (start > text &&
158 (_utbm_isspace(c1, 1) || _utbm_iscntrl(c1))) {
159 check_space = _utbm_isspace(c1, 1);
161 c1 = (start - 1 > text) ? *(start - 1) : ~0;
162 if (0xdc00 <= c2 && c2 <= 0xdfff &&
163 0xd800 <= c1 && c1 <= 0xdbff) {
164 c1 = 0x10000 + (((c1 & 0x03ff) << 10) | (c2 & 0x03ff));
170 * Handle things if space compression was indicated and one or
171 * more member characters were found.
182 * Handle the normal comparison cases.
184 if (count > 0 && ((c1 ^ cp->uc) & (c1 ^ cp->lc) & (c1 ^ cp->tc)))
187 count -= (c1 >= 0x10000) ? 2 : 1;
192 * Get the next preceding character.
196 c1 = (start - 1 > text) ? *(start - 1) : ~0;
197 if (0xdc00 <= c2 && c2 <= 0xdfff &&
198 0xd800 <= c1 && c1 <= 0xdbff) {
199 c1 = 0x10000 + (((c1 & 0x03ff) << 10) | (c2 & 0x03ff));
208 * Set the match start position.
210 *match_start = start - text;
214 /*************************************************************************
218 *************************************************************************/
221 utbm_create_pattern(void)
225 p = (utbm_pattern_t) malloc(sizeof(_utbm_pattern_t));
226 (void) memset((char *) p, '\0', sizeof(_utbm_pattern_t));
231 utbm_free_pattern(utbm_pattern_t pattern)
236 if (pattern->pat_size > 0)
237 free((char *) pattern->pat);
239 if (pattern->skip_size > 0)
240 free((char *) pattern->skip);
242 free((char *) pattern);
246 utbm_compile(ucs2_t *pat, unsigned long patlen, unsigned long flags,
250 unsigned long i, j, k, slen;
253 ucs4_t c1, c2, sentinel;
255 if (p == 0 || pat == 0 || *pat == 0 || patlen == 0)
259 * Reset the pattern buffer.
261 p->patlen = p->pat_used = p->skip_used = 0;
269 * Initialize the extra skip flag.
274 * Allocate more storage if necessary.
276 if (patlen > p->pat_size) {
277 if (p->pat_size == 0) {
278 p->pat = (_utbm_char_t *) malloc(sizeof(_utbm_char_t) * patlen);
279 p->skip = (_utbm_skip_t *) malloc(sizeof(_utbm_skip_t) * patlen);
281 p->pat = (_utbm_char_t *)
282 realloc((char *) p->pat, sizeof(_utbm_char_t) * patlen);
283 p->skip = (_utbm_skip_t *)
284 realloc((char *) p->skip, sizeof(_utbm_skip_t) * patlen);
286 p->pat_size = p->skip_size = patlen;
290 * Preprocess the pattern to remove controls (if specified) and determine
293 for (have_space = 0, cp = p->pat, i = 0; i < patlen; i++) {
295 c2 = (i + 1 < patlen) ? pat[i + 1] : ~0;
296 if (0xd800 <= c1 && c1 <= 0xdbff && 0xdc00 <= c2 && c2 <= 0xdfff)
297 c1 = 0x10000 + (((c1 & 0x03ff) << 10) | (c2 & 0x03ff));
300 * Make sure the `have_space' flag is turned off if the character
301 * is not an appropriate one.
303 if (!_utbm_isspace(c1, flags & UTBM_SPACE_COMPRESS))
307 * If non-spacing characters should be ignored, do it here.
309 if ((flags & UTBM_IGNORE_NONSPACING) && _utbm_nonspacing(c1))
313 * Check if spaces and controls need to be compressed.
315 if (flags & UTBM_SPACE_COMPRESS) {
316 if (_utbm_isspace(c1, 1)) {
319 * Add a space and set the flag.
321 cp->uc = cp->lc = cp->tc = ' ';
325 * Increase the real pattern length.
335 * Ignore all control characters.
337 if (_utbm_iscntrl(c1))
344 if (flags & UTBM_CASEFOLD) {
345 cp->uc = _utbm_toupper(c1);
346 cp->lc = _utbm_tolower(c1);
347 cp->tc = _utbm_totitle(c1);
349 cp->uc = cp->lc = cp->tc = c1;
352 * Set the sentinel character.
357 * Move to the next character.
362 * Increase the real pattern length appropriately.
364 p->patlen += (c1 >= 0x10000) ? 2 : 1;
367 * Increment the loop index for UTF-16 characters.
369 i += (c1 >= 0x10000) ? 1 : 0;
374 * Set the number of characters actually used.
376 p->pat_used = cp - p->pat;
379 * Go through and construct the skip array and determine the actual length
380 * of the pattern in UCS2 terms.
382 slen = p->patlen - 1;
384 for (i = k = 0; i < p->pat_used; i++, cp++) {
386 * Locate the character in the skip array.
388 for (sp = p->skip, j = 0;
389 j < p->skip_used && sp->ch->uc != cp->uc; j++, sp++) ;
392 * If the character is not found, set the new skip element and
393 * increase the number of skip elements.
395 if (j == p->skip_used) {
401 * Set the updated skip value. If the character is UTF-16 and is
402 * not the last one in the pattern, add one to its skip value.
405 if (cp->uc >= 0x10000 && k + 2 < slen)
409 * Set the new extra skip for the sentinel character.
411 if (((cp->uc >= 0x10000 && k + 2 <= slen) || k + 1 <= slen) &&
416 * Increase the actual index.
418 k += (cp->uc >= 0x10000) ? 2 : 1;
423 utbm_exec(utbm_pattern_t pat, ucs2_t *text, unsigned long textlen,
424 unsigned long *match_start, unsigned long *match_end)
429 if (pat == 0 || pat->pat_used == 0 || text == 0 || textlen == 0 ||
430 textlen < pat->patlen)
433 start = text + pat->patlen;
434 end = text + textlen;
437 * Adjust the start point if it points to a low surrogate.
439 if (0xdc00 <= *start && *start <= 0xdfff &&
440 0xd800 <= *(start - 1) && *(start - 1) <= 0xdbff)
443 while (start < end) {
444 while ((k = _utbm_skip(pat, start, end))) {
446 if (start < end && 0xdc00 <= *start && *start <= 0xdfff &&
447 0xd800 <= *(start - 1) && *(start - 1) <= 0xdbff)
452 _utbm_match(pat, text, start, end, match_start, match_end))
456 if (start < end && 0xdc00 <= *start && *start <= 0xdfff &&
457 0xd800 <= *(start - 1) && *(start - 1) <= 0xdbff)