libs/wine/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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  */
  20 #include "wine/unicode.h"
  21
  22 extern unsigned int wine_decompose( WCHAR ch, 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         unsigned int i, decomposed_len = 1;/*wine_decompose(*src, dummy, 4);*/
  42         dummy[0] = *src;
  43         if (decomposed_len)
  44         {
  45             for (i = 0; i < decomposed_len; i++)
  46             {
  47                 WCHAR wch = dummy[i];
  48                 unsigned int ce;
  49
  50                 /* tests show that win2k just ignores NORM_IGNORENONSPACE,
  51                  * and skips white space and punctuation characters for
  52                  * NORM_IGNORESYMBOLS.
  53                  */
  54                 if ((flags & NORM_IGNORESYMBOLS) && (get_char_typeW(wch) & (C1_PUNCT | C1_SPACE)))
  55                     continue;
  56
  57                 if (flags & NORM_IGNORECASE) wch = tolowerW(wch);
  58
  59                 ce = collation_table[collation_table[wch >> 8] + (wch & 0xff)];
  60                 if (ce != (unsigned int)-1)
  61                 {
  62                     if (ce >> 16) key_len[0] += 2;
  63                     if ((ce >> 8) & 0xff) key_len[1]++;
  64                     if ((ce >> 4) & 0x0f) key_len[2]++;
  65                     if (ce & 1)
  66                     {
  67                         if (wch >> 8) key_len[3]++;
  68                         key_len[3]++;
  69                     }
  70                 }
  71                 else
  72                 {
  73                     key_len[0] += 2;
  74                     if (wch >> 8) key_len[0]++;
  75                     if (wch & 0xff) key_len[0]++;
  76                 }
  77             }
  78         }
  79     }
  80
  81     if (!dstlen) /* compute length */
  82         /* 4 * '\1' + 1 * '\0' + key length */
  83         return key_len[0] + key_len[1] + key_len[2] + key_len[3] + 4 + 1;
  84
  85     if (dstlen < key_len[0] + key_len[1] + key_len[2] + key_len[3] + 4 + 1)
  86         return 0; /* overflow */
  87
  88     src = src_save;
  89     srclen = srclen_save;
  90
  91     key_ptr[0] = dst;
  92     key_ptr[1] = key_ptr[0] + key_len[0] + 1;
  93     key_ptr[2] = key_ptr[1] + key_len[1] + 1;
  94     key_ptr[3] = key_ptr[2] + key_len[2] + 1;
  95
  96     for (; srclen; srclen--, src++)
  97     {
  98         unsigned int i, decomposed_len = 1;/*wine_decompose(*src, dummy, 4);*/
  99         dummy[0] = *src;
 100         if (decomposed_len)
 101         {
 102             for (i = 0; i < decomposed_len; i++)
 103             {
 104                 WCHAR wch = dummy[i];
 105                 unsigned int ce;
 106
 107                 /* tests show that win2k just ignores NORM_IGNORENONSPACE,
 108                  * and skips white space and punctuation characters for
 109                  * NORM_IGNORESYMBOLS.
 110                  */
 111                 if ((flags & NORM_IGNORESYMBOLS) && (get_char_typeW(wch) & (C1_PUNCT | C1_SPACE)))
 112                     continue;
 113
 114                 if (flags & NORM_IGNORECASE) wch = tolowerW(wch);
 115
 116                 ce = collation_table[collation_table[wch >> 8] + (wch & 0xff)];
 117                 if (ce != (unsigned int)-1)
 118                 {
 119                     WCHAR key;
 120                     if ((key = ce >> 16))
 121                     {
 122                         *key_ptr[0]++ = key >> 8;
 123                         *key_ptr[0]++ = key & 0xff;
 124                     }
 125                     /* make key 1 start from 2 */
 126                     if ((key = (ce >> 8) & 0xff)) *key_ptr[1]++ = key + 1;
 127                     /* make key 2 start from 2 */
 128                     if ((key = (ce >> 4) & 0x0f)) *key_ptr[2]++ = key + 1;
 129                     /* key 3 is always a character code */
 130                     if (ce & 1)
 131                     {
 132                         if (wch >> 8) *key_ptr[3]++ = wch >> 8;
 133                         if (wch & 0xff) *key_ptr[3]++ = wch & 0xff;
 134                     }
 135                 }
 136                 else
 137                 {
 138                     *key_ptr[0]++ = 0xff;
 139                     *key_ptr[0]++ = 0xfe;
 140                     if (wch >> 8) *key_ptr[0]++ = wch >> 8;
 141                     if (wch & 0xff) *key_ptr[0]++ = wch & 0xff;
 142                 }
 143             }
 144         }
 145     }
 146
 147     *key_ptr[0] = '\1';
 148     *key_ptr[1] = '\1';
 149     *key_ptr[2] = '\1';
 150     *key_ptr[3]++ = '\1';
 151     *key_ptr[3] = 0;
 152
 153     return key_ptr[3] - dst;
 154 }
 155
 156 static inline int compare_unicode_weights(int flags, const WCHAR *str1, int len1,
 157                                           const WCHAR *str2, int len2)
 158 {
 159     unsigned int ce1, ce2;
 160     int ret;
 161
 162     /* 32-bit collation element table format:
 163      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 164      * case weight - high 4 bit of low 8 bit.
 165      */
 166     while (len1 > 0 && len2 > 0)
 167     {
 168         if (flags & NORM_IGNORESYMBOLS)
 169         {
 170             int skip = 0;
 171             /* FIXME: not tested */
 172             if (get_char_typeW(*str1) & (C1_PUNCT | C1_SPACE))
 173             {
 174                 str1++;
 175                 len1--;
 176                 skip = 1;
 177             }
 178             if (get_char_typeW(*str2) & (C1_PUNCT | C1_SPACE))
 179             {
 180                 str2++;
 181                 len2--;
 182                 skip = 1;
 183             }
 184             if (skip) continue;
 185         }
 186
 187        /* hyphen and apostrophe are treated differently depending on
 188         * whether SORT_STRINGSORT specified or not
 189         */
 190         if (!(flags & SORT_STRINGSORT))
 191         {
 192             if (*str1 == '-' || *str1 == '\'')
 193             {
 194                 if (*str2 != '-' && *str2 != '\'')
 195                 {
 196                     str1++;
 197                     len1--;
 198                     continue;
 199                 }
 200             }
 201             else if (*str2 == '-' || *str2 == '\'')
 202             {
 203                 str2++;
 204                 len2--;
 205                 continue;
 206             }
 207         }
 208
 209         ce1 = collation_table[collation_table[*str1 >> 8] + (*str1 & 0xff)];
 210         ce2 = collation_table[collation_table[*str2 >> 8] + (*str2 & 0xff)];
 211
 212         if (ce1 != (unsigned int)-1 && ce2 != (unsigned int)-1)
 213             ret = (ce1 >> 16) - (ce2 >> 16);
 214         else
 215             ret = *str1 - *str2;
 216
 217         if (ret) return ret;
 218
 219         str1++;
 220         str2++;
 221         len1--;
 222         len2--;
 223     }
 224     while (len1 && !*str1)
 225     {
 226         str1++;
 227         len1--;
 228     }
 229     while (len2 && !*str2)
 230     {
 231         str2++;
 232         len2--;
 233     }
 234     return len1 - len2;
 235 }
 236
 237 static inline int compare_diacritic_weights(int flags, const WCHAR *str1, int len1,
 238                                             const WCHAR *str2, int len2)
 239 {
 240     unsigned int ce1, ce2;
 241     int ret;
 242
 243     /* 32-bit collation element table format:
 244      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 245      * case weight - high 4 bit of low 8 bit.
 246      */
 247     while (len1 > 0 && len2 > 0)
 248     {
 249         if (flags & NORM_IGNORESYMBOLS)
 250         {
 251             int skip = 0;
 252             /* FIXME: not tested */
 253             if (get_char_typeW(*str1) & (C1_PUNCT | C1_SPACE))
 254             {
 255                 str1++;
 256                 len1--;
 257                 skip = 1;
 258             }
 259             if (get_char_typeW(*str2) & (C1_PUNCT | C1_SPACE))
 260             {
 261                 str2++;
 262                 len2--;
 263                 skip = 1;
 264             }
 265             if (skip) continue;
 266         }
 267
 268         ce1 = collation_table[collation_table[*str1 >> 8] + (*str1 & 0xff)];
 269         ce2 = collation_table[collation_table[*str2 >> 8] + (*str2 & 0xff)];
 270
 271         if (ce1 != (unsigned int)-1 && ce2 != (unsigned int)-1)
 272             ret = ((ce1 >> 8) & 0xff) - ((ce2 >> 8) & 0xff);
 273         else
 274             ret = *str1 - *str2;
 275
 276         if (ret) return ret;
 277
 278         str1++;
 279         str2++;
 280         len1--;
 281         len2--;
 282     }
 283     while (len1 && !*str1)
 284     {
 285         str1++;
 286         len1--;
 287     }
 288     while (len2 && !*str2)
 289     {
 290         str2++;
 291         len2--;
 292     }
 293     return len1 - len2;
 294 }
 295
 296 static inline int compare_case_weights(int flags, const WCHAR *str1, int len1,
 297                                        const WCHAR *str2, int len2)
 298 {
 299     unsigned int ce1, ce2;
 300     int ret;
 301
 302     /* 32-bit collation element table format:
 303      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 304      * case weight - high 4 bit of low 8 bit.
 305      */
 306     while (len1 > 0 && len2 > 0)
 307     {
 308         if (flags & NORM_IGNORESYMBOLS)
 309         {
 310             int skip = 0;
 311             /* FIXME: not tested */
 312             if (get_char_typeW(*str1) & (C1_PUNCT | C1_SPACE))
 313             {
 314                 str1++;
 315                 len1--;
 316                 skip = 1;
 317             }
 318             if (get_char_typeW(*str2) & (C1_PUNCT | C1_SPACE))
 319             {
 320                 str2++;
 321                 len2--;
 322                 skip = 1;
 323             }
 324             if (skip) continue;
 325         }
 326
 327         ce1 = collation_table[collation_table[*str1 >> 8] + (*str1 & 0xff)];
 328         ce2 = collation_table[collation_table[*str2 >> 8] + (*str2 & 0xff)];
 329
 330         if (ce1 != (unsigned int)-1 && ce2 != (unsigned int)-1)
 331             ret = ((ce1 >> 4) & 0x0f) - ((ce2 >> 4) & 0x0f);
 332         else
 333             ret = *str1 - *str2;
 334
 335         if (ret) return ret;
 336
 337         str1++;
 338         str2++;
 339         len1--;
 340         len2--;
 341     }
 342     while (len1 && !*str1)
 343     {
 344         str1++;
 345         len1--;
 346     }
 347     while (len2 && !*str2)
 348     {
 349         str2++;
 350         len2--;
 351     }
 352     return len1 - len2;
 353 }
 354
 355 int wine_compare_string(int flags, const WCHAR *str1, int len1,
 356                         const WCHAR *str2, int len2)
 357 {
 358     int ret;
 359
 360     ret = compare_unicode_weights(flags, str1, len1, str2, len2);
 361     if (!ret)
 362     {
 363         if (!(flags & NORM_IGNORENONSPACE))
 364             ret = compare_diacritic_weights(flags, str1, len1, str2, len2);
 365         if (!ret && !(flags & NORM_IGNORECASE))
 366             ret = compare_case_weights(flags, str1, len1, str2, len2);
 367     }
 368     return ret;
 369 }