1 /* $NetBSD: ucstr.c,v 1.1.1.2 2010/03/08 02:14:20 lukem Exp $ */ 2 3 /* OpenLDAP: pkg/ldap/libraries/liblunicode/ucstr.c,v 1.37.2.5 2009/01/22 00:00:57 kurt Exp */ 4 /* This work is part of OpenLDAP Software <http://www.openldap.org/>. 5 * 6 * Copyright 1998-2009 The OpenLDAP Foundation. 7 * All rights reserved. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted only as authorized by the OpenLDAP 11 * Public License. 12 * 13 * A copy of this license is available in file LICENSE in the 14 * top-level directory of the distribution or, alternatively, at 15 * <http://www.OpenLDAP.org/license.html>. 16 */ 17 18 #include "portable.h" 19 20 #include <ac/bytes.h> 21 #include <ac/ctype.h> 22 #include <ac/string.h> 23 #include <ac/stdlib.h> 24 25 #include <lber_pvt.h> 26 27 #include <ldap_utf8.h> 28 #include <ldap_pvt_uc.h> 29 30 #define malloc(x) ber_memalloc_x(x,ctx) 31 #define realloc(x,y) ber_memrealloc_x(x,y,ctx) 32 #define free(x) ber_memfree_x(x,ctx) 33 34 int ucstrncmp( 35 const ldap_unicode_t *u1, 36 const ldap_unicode_t *u2, 37 ber_len_t n ) 38 { 39 for(; 0 < n; ++u1, ++u2, --n ) { 40 if( *u1 != *u2 ) { 41 return *u1 < *u2 ? -1 : +1; 42 } 43 if ( *u1 == 0 ) { 44 return 0; 45 } 46 } 47 return 0; 48 } 49 50 int ucstrncasecmp( 51 const ldap_unicode_t *u1, 52 const ldap_unicode_t *u2, 53 ber_len_t n ) 54 { 55 for(; 0 < n; ++u1, ++u2, --n ) { 56 ldap_unicode_t uu1 = uctolower( *u1 ); 57 ldap_unicode_t uu2 = uctolower( *u2 ); 58 59 if( uu1 != uu2 ) { 60 return uu1 < uu2 ? -1 : +1; 61 } 62 if ( uu1 == 0 ) { 63 return 0; 64 } 65 } 66 return 0; 67 } 68 69 ldap_unicode_t * ucstrnchr( 70 const ldap_unicode_t *u, 71 ber_len_t n, 72 ldap_unicode_t c ) 73 { 74 for(; 0 < n; ++u, --n ) { 75 if( *u == c ) { 76 return (ldap_unicode_t *) u; 77 } 78 } 79 80 return NULL; 81 } 82 83 ldap_unicode_t * ucstrncasechr( 84 const ldap_unicode_t *u, 85 ber_len_t n, 86 ldap_unicode_t c ) 87 { 88 c = uctolower( c ); 89 for(; 0 < n; ++u, --n ) { 90 if( uctolower( *u ) == c ) { 91 return (ldap_unicode_t *) u; 92 } 93 } 94 95 return NULL; 96 } 97 98 void ucstr2upper( 99 ldap_unicode_t *u, 100 ber_len_t n ) 101 { 102 for(; 0 < n; ++u, --n ) { 103 *u = uctoupper( *u ); 104 } 105 } 106 107 struct berval * UTF8bvnormalize( 108 struct berval *bv, 109 struct berval *newbv, 110 unsigned flags, 111 void *ctx ) 112 { 113 int i, j, len, clen, outpos, ucsoutlen, outsize, last; 114 char *out, *outtmp, *s; 115 ac_uint4 *ucs, *p, *ucsout; 116 117 static unsigned char mask[] = { 118 0, 0x7f, 0x1f, 0x0f, 0x07, 0x03, 0x01 }; 119 120 unsigned casefold = flags & LDAP_UTF8_CASEFOLD; 121 unsigned approx = flags & LDAP_UTF8_APPROX; 122 123 if ( bv == NULL ) { 124 return NULL; 125 } 126 127 s = bv->bv_val; 128 len = bv->bv_len; 129 130 if ( len == 0 ) { 131 return ber_dupbv_x( newbv, bv, ctx ); 132 } 133 134 if ( !newbv ) { 135 newbv = ber_memalloc_x( sizeof(struct berval), ctx ); 136 if ( !newbv ) return NULL; 137 } 138 139 /* Should first check to see if string is already in proper 140 * normalized form. This is almost as time consuming as 141 * the normalization though. 142 */ 143 144 /* finish off everything up to character before first non-ascii */ 145 if ( LDAP_UTF8_ISASCII( s ) ) { 146 if ( casefold ) { 147 outsize = len + 7; 148 out = (char *) ber_memalloc_x( outsize, ctx ); 149 if ( out == NULL ) { 150 return NULL; 151 } 152 outpos = 0; 153 154 for ( i = 1; (i < len) && LDAP_UTF8_ISASCII(s + i); i++ ) { 155 out[outpos++] = TOLOWER( s[i-1] ); 156 } 157 if ( i == len ) { 158 out[outpos++] = TOLOWER( s[len-1] ); 159 out[outpos] = '\0'; 160 newbv->bv_val = out; 161 newbv->bv_len = outpos; 162 return newbv; 163 } 164 } else { 165 for ( i = 1; (i < len) && LDAP_UTF8_ISASCII(s + i); i++ ) { 166 /* empty */ 167 } 168 169 if ( i == len ) { 170 return ber_str2bv_x( s, len, 1, newbv, ctx ); 171 } 172 173 outsize = len + 7; 174 out = (char *) ber_memalloc_x( outsize, ctx ); 175 if ( out == NULL ) { 176 return NULL; 177 } 178 outpos = i - 1; 179 memcpy(out, s, outpos); 180 } 181 } else { 182 outsize = len + 7; 183 out = (char *) ber_memalloc_x( outsize, ctx ); 184 if ( out == NULL ) { 185 return NULL; 186 } 187 outpos = 0; 188 i = 0; 189 } 190 191 p = ucs = ber_memalloc_x( len * sizeof(*ucs), ctx ); 192 if ( ucs == NULL ) { 193 ber_memfree_x(out, ctx); 194 return NULL; 195 } 196 197 /* convert character before first non-ascii to ucs-4 */ 198 if ( i > 0 ) { 199 *p = casefold ? TOLOWER( s[i-1] ) : s[i-1]; 200 p++; 201 } 202 203 /* s[i] is now first non-ascii character */ 204 for (;;) { 205 /* s[i] is non-ascii */ 206 /* convert everything up to next ascii to ucs-4 */ 207 while ( i < len ) { 208 clen = LDAP_UTF8_CHARLEN2( s + i, clen ); 209 if ( clen == 0 ) { 210 ber_memfree_x( ucs, ctx ); 211 ber_memfree_x( out, ctx ); 212 return NULL; 213 } 214 if ( clen == 1 ) { 215 /* ascii */ 216 break; 217 } 218 *p = s[i] & mask[clen]; 219 i++; 220 for( j = 1; j < clen; j++ ) { 221 if ( (s[i] & 0xc0) != 0x80 ) { 222 ber_memfree_x( ucs, ctx ); 223 ber_memfree_x( out, ctx ); 224 return NULL; 225 } 226 *p <<= 6; 227 *p |= s[i] & 0x3f; 228 i++; 229 } 230 if ( casefold ) { 231 *p = uctolower( *p ); 232 } 233 p++; 234 } 235 /* normalize ucs of length p - ucs */ 236 uccompatdecomp( ucs, p - ucs, &ucsout, &ucsoutlen, ctx ); 237 if ( approx ) { 238 for ( j = 0; j < ucsoutlen; j++ ) { 239 if ( ucsout[j] < 0x80 ) { 240 out[outpos++] = ucsout[j]; 241 } 242 } 243 } else { 244 ucsoutlen = uccanoncomp( ucsout, ucsoutlen ); 245 /* convert ucs to utf-8 and store in out */ 246 for ( j = 0; j < ucsoutlen; j++ ) { 247 /* allocate more space if not enough room for 248 6 bytes and terminator */ 249 if ( outsize - outpos < 7 ) { 250 outsize = ucsoutlen - j + outpos + 6; 251 outtmp = (char *) ber_memrealloc_x( out, outsize, ctx ); 252 if ( outtmp == NULL ) { 253 ber_memfree_x( ucsout, ctx ); 254 ber_memfree_x( ucs, ctx ); 255 ber_memfree_x( out, ctx ); 256 return NULL; 257 } 258 out = outtmp; 259 } 260 outpos += ldap_x_ucs4_to_utf8( ucsout[j], &out[outpos] ); 261 } 262 } 263 264 ber_memfree_x( ucsout, ctx ); 265 ucsout = NULL; 266 267 if ( i == len ) { 268 break; 269 } 270 271 last = i; 272 273 /* Allocate more space in out if necessary */ 274 if (len - i >= outsize - outpos) { 275 outsize += 1 + ((len - i) - (outsize - outpos)); 276 outtmp = (char *) ber_memrealloc_x(out, outsize, ctx); 277 if (outtmp == NULL) { 278 ber_memfree_x( ucs, ctx ); 279 ber_memfree_x( out, ctx ); 280 return NULL; 281 } 282 out = outtmp; 283 } 284 285 /* s[i] is ascii */ 286 /* finish off everything up to char before next non-ascii */ 287 for ( i++; (i < len) && LDAP_UTF8_ISASCII(s + i); i++ ) { 288 out[outpos++] = casefold ? TOLOWER( s[i-1] ) : s[i-1]; 289 } 290 if ( i == len ) { 291 out[outpos++] = casefold ? TOLOWER( s[len-1] ) : s[len-1]; 292 break; 293 } 294 295 /* convert character before next non-ascii to ucs-4 */ 296 *ucs = casefold ? TOLOWER( s[i-1] ) : s[i-1]; 297 p = ucs + 1; 298 } 299 300 ber_memfree_x( ucs, ctx ); 301 out[outpos] = '\0'; 302 newbv->bv_val = out; 303 newbv->bv_len = outpos; 304 return newbv; 305 } 306 307 /* compare UTF8-strings, optionally ignore casing */ 308 /* slow, should be optimized */ 309 int UTF8bvnormcmp( 310 struct berval *bv1, 311 struct berval *bv2, 312 unsigned flags, 313 void *ctx ) 314 { 315 int i, l1, l2, len, ulen, res = 0; 316 char *s1, *s2, *done; 317 ac_uint4 *ucs, *ucsout1, *ucsout2; 318 319 unsigned casefold = flags & LDAP_UTF8_CASEFOLD; 320 unsigned norm1 = flags & LDAP_UTF8_ARG1NFC; 321 unsigned norm2 = flags & LDAP_UTF8_ARG2NFC; 322 323 if (bv1 == NULL) { 324 return bv2 == NULL ? 0 : -1; 325 326 } else if (bv2 == NULL) { 327 return 1; 328 } 329 330 l1 = bv1->bv_len; 331 l2 = bv2->bv_len; 332 333 len = (l1 < l2) ? l1 : l2; 334 if (len == 0) { 335 return l1 == 0 ? (l2 == 0 ? 0 : -1) : 1; 336 } 337 338 s1 = bv1->bv_val; 339 s2 = bv2->bv_val; 340 done = s1 + len; 341 342 while ( (s1 < done) && LDAP_UTF8_ISASCII(s1) && LDAP_UTF8_ISASCII(s2) ) { 343 if (casefold) { 344 char c1 = TOLOWER(*s1); 345 char c2 = TOLOWER(*s2); 346 res = c1 - c2; 347 } else { 348 res = *s1 - *s2; 349 } 350 s1++; 351 s2++; 352 if (res) { 353 /* done unless next character in s1 or s2 is non-ascii */ 354 if (s1 < done) { 355 if (!LDAP_UTF8_ISASCII(s1) || !LDAP_UTF8_ISASCII(s2)) { 356 break; 357 } 358 } else if (((len < l1) && !LDAP_UTF8_ISASCII(s1)) || 359 ((len < l2) && !LDAP_UTF8_ISASCII(s2))) 360 { 361 break; 362 } 363 return res; 364 } 365 } 366 367 /* We have encountered non-ascii or strings equal up to len */ 368 369 /* set i to number of iterations */ 370 i = s1 - done + len; 371 /* passed through loop at least once? */ 372 if (i > 0) { 373 if (!res && (s1 == done) && 374 ((len == l1) || LDAP_UTF8_ISASCII(s1)) && 375 ((len == l2) || LDAP_UTF8_ISASCII(s2))) { 376 /* all ascii and equal up to len */ 377 return l1 - l2; 378 } 379 380 /* rewind one char, and do normalized compare from there */ 381 s1--; 382 s2--; 383 l1 -= i - 1; 384 l2 -= i - 1; 385 } 386 387 /* Should first check to see if strings are already in 388 * proper normalized form. 389 */ 390 ucs = malloc( ( ( norm1 || l1 > l2 ) ? l1 : l2 ) * sizeof(*ucs) ); 391 if ( ucs == NULL ) { 392 return l1 > l2 ? 1 : -1; /* what to do??? */ 393 } 394 395 /* 396 * XXYYZ: we convert to ucs4 even though -llunicode 397 * expects ucs2 in an ac_uint4 398 */ 399 400 /* convert and normalize 1st string */ 401 for ( i = 0, ulen = 0; i < l1; i += len, ulen++ ) { 402 ucs[ulen] = ldap_x_utf8_to_ucs4( s1 + i ); 403 if ( ucs[ulen] == LDAP_UCS4_INVALID ) { 404 free( ucs ); 405 return -1; /* what to do??? */ 406 } 407 len = LDAP_UTF8_CHARLEN( s1 + i ); 408 } 409 410 if ( norm1 ) { 411 ucsout1 = ucs; 412 l1 = ulen; 413 ucs = malloc( l2 * sizeof(*ucs) ); 414 if ( ucs == NULL ) { 415 free( ucsout1 ); 416 return l1 > l2 ? 1 : -1; /* what to do??? */ 417 } 418 } else { 419 uccompatdecomp( ucs, ulen, &ucsout1, &l1, ctx ); 420 l1 = uccanoncomp( ucsout1, l1 ); 421 } 422 423 /* convert and normalize 2nd string */ 424 for ( i = 0, ulen = 0; i < l2; i += len, ulen++ ) { 425 ucs[ulen] = ldap_x_utf8_to_ucs4( s2 + i ); 426 if ( ucs[ulen] == LDAP_UCS4_INVALID ) { 427 free( ucsout1 ); 428 free( ucs ); 429 return 1; /* what to do??? */ 430 } 431 len = LDAP_UTF8_CHARLEN( s2 + i ); 432 } 433 434 if ( norm2 ) { 435 ucsout2 = ucs; 436 l2 = ulen; 437 } else { 438 uccompatdecomp( ucs, ulen, &ucsout2, &l2, ctx ); 439 l2 = uccanoncomp( ucsout2, l2 ); 440 free( ucs ); 441 } 442 443 res = casefold 444 ? ucstrncasecmp( ucsout1, ucsout2, l1 < l2 ? l1 : l2 ) 445 : ucstrncmp( ucsout1, ucsout2, l1 < l2 ? l1 : l2 ); 446 free( ucsout1 ); 447 free( ucsout2 ); 448 449 if ( res != 0 ) { 450 return res; 451 } 452 if ( l1 == l2 ) { 453 return 0; 454 } 455 return l1 > l2 ? 1 : -1; 456 } 457