libs/unicode/sortkey.c

   1 /*
   2  * Unicode sort key generation
   3  *
   4  * Copyright 2003 Dmitry Timoshkov
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20 #include "wine/unicode.h"
  21
  22 extern int get_decomposition(WCHAR src, WCHAR *dst, unsigned int dstlen);
  23 extern const unsigned int collation_table[];
  24
  25 /*
  26  * flags - normalization NORM_* flags
  27  *
  28  * FIXME: 'variable' flag not handled
  29  */
  30 int wine_get_sortkey(int flags, const WCHAR *src, int srclen, char *dst, int dstlen)
  31 {
  32     WCHAR dummy[4]; /* no decomposition is larger than 4 chars */
  33     int key_len[4];
  34     char *key_ptr[4];
  35     const WCHAR *src_save = src;
  36     int srclen_save = srclen;
  37
  38     key_len[0] = key_len[1] = key_len[2] = key_len[3] = 0;
  39     for (; srclen; srclen--, src++)
  40     {
  41         int decomposed_len = 1;/*get_decomposition(*src, dummy, 4);*/
  42         dummy[0] = *src;
  43         if (decomposed_len)
  44         {
  45             int i;
  46             for (i = 0; i < decomposed_len; i++)
  47             {
  48                 WCHAR wch = dummy[i];
  49                 unsigned int ce;
  50
  51                 /* tests show that win2k just ignores NORM_IGNORENONSPACE,
  52                  * and skips white space and punctuation characters for
  53                  * NORM_IGNORESYMBOLS.
  54                  */
  55                 if ((flags & NORM_IGNORESYMBOLS) && (get_char_typeW(wch) & (C1_PUNCT | C1_SPACE)))
  56                     continue;
  57
  58                 if (flags & NORM_IGNORECASE) wch = tolowerW(wch);
  59
  60                 ce = collation_table[collation_table[wch >> 8] + (wch & 0xff)];
  61                 if (ce != (unsigned int)-1)
  62                 {
  63                     if (ce >> 16) key_len[0] += 2;
  64                     if ((ce >> 8) & 0xff) key_len[1]++;
  65                     if ((ce >> 4) & 0x0f) key_len[2]++;
  66                     if (ce & 1)
  67                     {
  68                         if (wch >> 8) key_len[3]++;
  69                         key_len[3]++;
  70                     }
  71                 }
  72                 else
  73                 {
  74                     key_len[0] += 2;
  75                     if (wch >> 8) key_len[0]++;
  76                     if (wch & 0xff) key_len[0]++;
  77                 }
  78             }
  79         }
  80     }
  81
  82     if (!dstlen) /* compute length */
  83         /* 4 * '\1' + 1 * '\0' + key length */
  84         return key_len[0] + key_len[1] + key_len[2] + key_len[3] + 4 + 1;
  85
  86     if (dstlen < key_len[0] + key_len[1] + key_len[2] + key_len[3] + 4 + 1)
  87         return 0; /* overflow */
  88
  89     src = src_save;
  90     srclen = srclen_save;
  91
  92     key_ptr[0] = dst;
  93     key_ptr[1] = key_ptr[0] + key_len[0] + 1;
  94     key_ptr[2] = key_ptr[1] + key_len[1] + 1;
  95     key_ptr[3] = key_ptr[2] + key_len[2] + 1;
  96
  97     for (; srclen; srclen--, src++)
  98     {
  99         int decomposed_len = 1;/*get_decomposition(*src, dummy, 4);*/
 100         dummy[0] = *src;
 101         if (decomposed_len)
 102         {
 103             int i;
 104             for (i = 0; i < decomposed_len; i++)
 105             {
 106                 WCHAR wch = dummy[i];
 107                 unsigned int ce;
 108
 109                 /* tests show that win2k just ignores NORM_IGNORENONSPACE,
 110                  * and skips white space and punctuation characters for
 111                  * NORM_IGNORESYMBOLS.
 112                  */
 113                 if ((flags & NORM_IGNORESYMBOLS) && (get_char_typeW(wch) & (C1_PUNCT | C1_SPACE)))
 114                     continue;
 115
 116                 if (flags & NORM_IGNORECASE) wch = tolowerW(wch);
 117
 118                 ce = collation_table[collation_table[wch >> 8] + (wch & 0xff)];
 119                 if (ce != (unsigned int)-1)
 120                 {
 121                     WCHAR key;
 122                     if ((key = ce >> 16))
 123                     {
 124                         *key_ptr[0]++ = key >> 8;
 125                         *key_ptr[0]++ = key & 0xff;
 126                     }
 127                     /* make key 1 start from 2 */
 128                     if ((key = (ce >> 8) & 0xff)) *key_ptr[1]++ = key + 1;
 129                     /* make key 2 start from 2 */
 130                     if ((key = (ce >> 4) & 0x0f)) *key_ptr[2]++ = key + 1;
 131                     /* key 3 is always a character code */
 132                     if (ce & 1)
 133                     {
 134                         if (wch >> 8) *key_ptr[3]++ = wch >> 8;
 135                         if (wch & 0xff) *key_ptr[3]++ = wch & 0xff;
 136                     }
 137                 }
 138                 else
 139                 {
 140                     *key_ptr[0]++ = 0xff;
 141                     *key_ptr[0]++ = 0xfe;
 142                     if (wch >> 8) *key_ptr[0]++ = wch >> 8;
 143                     if (wch & 0xff) *key_ptr[0]++ = wch & 0xff;
 144                 }
 145             }
 146         }
 147     }
 148
 149     *key_ptr[0] = '\1';
 150     *key_ptr[1] = '\1';
 151     *key_ptr[2] = '\1';
 152     *key_ptr[3]++ = '\1';
 153     *key_ptr[3] = 0;
 154
 155     return key_ptr[3] - dst;
 156 }
 157
 158 static inline int compare_unicode_weights(int flags, const WCHAR *str1, int len1,
 159                                           const WCHAR *str2, int len2)
 160 {
 161     unsigned int ce1, ce2;
 162     int ret;
 163
 164     /* 32-bit collation element table format:
 165      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 166      * case weight - high 4 bit of low 8 bit.
 167      */
 168     while (len1 > 0 && len2 > 0)
 169     {
 170         if (flags & NORM_IGNORESYMBOLS)
 171         {
 172             int skip = 0;
 173             /* FIXME: not tested */
 174             if (get_char_typeW(*str1) & (C1_PUNCT | C1_SPACE))
 175             {
 176                 str1++;
 177                 len1--;
 178                 skip = 1;
 179             }
 180             if (get_char_typeW(*str2) & (C1_PUNCT | C1_SPACE))
 181             {
 182                 str2++;
 183                 len2--;
 184                 skip = 1;
 185             }
 186             if (skip) continue;
 187         }
 188
 189        /* hyphen and apostrophe are treated differently depending on
 190         * whether SORT_STRINGSORT specified or not
 191         */
 192         if (!(flags & SORT_STRINGSORT))
 193         {
 194             if (*str1 == '-' || *str1 == '\'')
 195             {
 196                 if (*str2 != '-' && *str2 != '\'')
 197                 {
 198                     str1++;
 199                     len1--;
 200                     continue;
 201                 }
 202             }
 203             else if (*str2 == '-' || *str2 == '\'')
 204             {
 205                 str2++;
 206                 len2--;
 207                 continue;
 208             }
 209         }
 210
 211         ce1 = collation_table[collation_table[*str1 >> 8] + (*str1 & 0xff)];
 212         ce2 = collation_table[collation_table[*str2 >> 8] + (*str2 & 0xff)];
 213
 214         if (ce1 != (unsigned int)-1 && ce2 != (unsigned int)-1)
 215             ret = (ce1 >> 16) - (ce2 >> 16);
 216         else
 217             ret = *str1 - *str2;
 218
 219         if (ret) return ret;
 220
 221         str1++;
 222         str2++;
 223         len1--;
 224         len2--;
 225     }
 226     return len1 - len2;
 227 }
 228
 229 static inline int compare_diacritic_weights(int flags, const WCHAR *str1, int len1,
 230                                             const WCHAR *str2, int len2)
 231 {
 232     unsigned int ce1, ce2;
 233     int ret;
 234
 235     /* 32-bit collation element table format:
 236      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 237      * case weight - high 4 bit of low 8 bit.
 238      */
 239     while (len1 > 0 && len2 > 0)
 240     {
 241         if (flags & NORM_IGNORESYMBOLS)
 242         {
 243             int skip = 0;
 244             /* FIXME: not tested */
 245             if (get_char_typeW(*str1) & (C1_PUNCT | C1_SPACE))
 246             {
 247                 str1++;
 248                 len1--;
 249                 skip = 1;
 250             }
 251             if (get_char_typeW(*str2) & (C1_PUNCT | C1_SPACE))
 252             {
 253                 str2++;
 254                 len2--;
 255                 skip = 1;
 256             }
 257             if (skip) continue;
 258         }
 259
 260         ce1 = collation_table[collation_table[*str1 >> 8] + (*str1 & 0xff)];
 261         ce2 = collation_table[collation_table[*str2 >> 8] + (*str2 & 0xff)];
 262
 263         if (ce1 != (unsigned int)-1 && ce2 != (unsigned int)-1)
 264             ret = ((ce1 >> 8) & 0xff) - ((ce2 >> 8) & 0xff);
 265         else
 266             ret = *str1 - *str2;
 267
 268         if (ret) return ret;
 269
 270         str1++;
 271         str2++;
 272         len1--;
 273         len2--;
 274     }
 275     return len1 - len2;
 276 }
 277
 278 static inline int compare_case_weights(int flags, const WCHAR *str1, int len1,
 279                                        const WCHAR *str2, int len2)
 280 {
 281     unsigned int ce1, ce2;
 282     int ret;
 283
 284     /* 32-bit collation element table format:
 285      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 286      * case weight - high 4 bit of low 8 bit.
 287      */
 288     while (len1 > 0 && len2 > 0)
 289     {
 290         if (flags & NORM_IGNORESYMBOLS)
 291         {
 292             int skip = 0;
 293             /* FIXME: not tested */
 294             if (get_char_typeW(*str1) & (C1_PUNCT | C1_SPACE))
 295             {
 296                 str1++;
 297                 len1--;
 298                 skip = 1;
 299             }
 300             if (get_char_typeW(*str2) & (C1_PUNCT | C1_SPACE))
 301             {
 302                 str2++;
 303                 len2--;
 304                 skip = 1;
 305             }
 306             if (skip) continue;
 307         }
 308
 309         ce1 = collation_table[collation_table[*str1 >> 8] + (*str1 & 0xff)];
 310         ce2 = collation_table[collation_table[*str2 >> 8] + (*str2 & 0xff)];
 311
 312         if (ce1 != (unsigned int)-1 && ce2 != (unsigned int)-1)
 313             ret = ((ce1 >> 4) & 0x0f) - ((ce2 >> 4) & 0x0f);
 314         else
 315             ret = *str1 - *str2;
 316
 317         if (ret) return ret;
 318
 319         str1++;
 320         str2++;
 321         len1--;
 322         len2--;
 323     }
 324     return len1 - len2;
 325 }
 326
 327 static inline int real_length(const WCHAR *str, int len)
 328 {
 329     int real_len = 0;
 330     while (len-- && *str++) real_len++;
 331     return real_len;
 332 }
 333
 334 int wine_compare_string(int flags, const WCHAR *str1, int len1,
 335                         const WCHAR *str2, int len2)
 336 {
 337     int ret;
 338
 339     len1 = real_length(str1, len1);
 340     len2 = real_length(str2, len2);
 341
 342     ret = compare_unicode_weights(flags, str1, len1, str2, len2);
 343     if (!ret)
 344     {
 345         if (!(flags & NORM_IGNORENONSPACE))
 346             ret = compare_diacritic_weights(flags, str1, len1, str2, len2);
 347         if (!ret && !(flags & NORM_IGNORECASE))
 348             ret = compare_case_weights(flags, str1, len1, str2, len2);
 349     }
 350     return ret;
 351 }