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
  21 #include "wine/asm.h"
  22
  23 #ifdef __ASM_OBSOLETE
  24
  25 #include "wine/unicode.h"
  26
  27 extern const unsigned int collation_table[];
  28 extern const unsigned short nfd_table[] DECLSPEC_HIDDEN;
  29
  30 static const WCHAR *get_decomposition( WCHAR ch, unsigned int *len )
  31 {
  32     unsigned short offset = nfd_table[nfd_table[ch >> 8] + ((ch >> 4) & 0xf)] + (ch & 0xf);
  33     unsigned short start = nfd_table[offset];
  34     unsigned short end = nfd_table[offset + 1];
  35
  36     if ((*len = end - start)) return nfd_table + start;
  37     *len = 1;
  38     return NULL;
  39 }
  40
  41 /*
  42  * flags - normalization NORM_* flags
  43  *
  44  * FIXME: 'variable' flag not handled
  45  */
  46 int wine_get_sortkey_obsolete(int flags, const WCHAR *src, int srclen, char *dst, int dstlen)
  47 {
  48     WCHAR dummy[4]; /* no decomposition is larger than 4 chars */
  49     int key_len[4];
  50     char *key_ptr[4];
  51     const WCHAR *src_save = src;
  52     int srclen_save = srclen;
  53
  54     key_len[0] = key_len[1] = key_len[2] = key_len[3] = 0;
  55     for (; srclen; srclen--, src++)
  56     {
  57         unsigned int i, decomposed_len = 1;/*wine_decompose(*src, dummy, 4);*/
  58         dummy[0] = *src;
  59         if (decomposed_len)
  60         {
  61             for (i = 0; i < decomposed_len; i++)
  62             {
  63                 WCHAR wch = dummy[i];
  64                 unsigned int ce;
  65
  66                 /* tests show that win2k just ignores NORM_IGNORENONSPACE,
  67                  * and skips white space and punctuation characters for
  68                  * NORM_IGNORESYMBOLS.
  69                  */
  70                 if ((flags & NORM_IGNORESYMBOLS) && (get_char_typeW(wch) & (C1_PUNCT | C1_SPACE)))
  71                     continue;
  72
  73                 if (flags & NORM_IGNORECASE) wch = tolowerW(wch);
  74
  75                 ce = collation_table[collation_table[collation_table[wch >> 8] + ((wch >> 4) & 0x0f)] + (wch & 0xf)];
  76                 if (ce != (unsigned int)-1)
  77                 {
  78                     if (ce >> 16) key_len[0] += 2;
  79                     if ((ce >> 8) & 0xff) key_len[1]++;
  80                     if ((ce >> 4) & 0x0f) key_len[2]++;
  81                     if (ce & 1)
  82                     {
  83                         if (wch >> 8) key_len[3]++;
  84                         key_len[3]++;
  85                     }
  86                 }
  87                 else
  88                 {
  89                     key_len[0] += 2;
  90                     if (wch >> 8) key_len[0]++;
  91                     if (wch & 0xff) key_len[0]++;
  92                 }
  93             }
  94         }
  95     }
  96
  97     if (!dstlen) /* compute length */
  98         /* 4 * '\1' + key length */
  99         return key_len[0] + key_len[1] + key_len[2] + key_len[3] + 4;
 100
 101     if (dstlen < key_len[0] + key_len[1] + key_len[2] + key_len[3] + 4 + 1)
 102         return 0; /* overflow */
 103
 104     src = src_save;
 105     srclen = srclen_save;
 106
 107     key_ptr[0] = dst;
 108     key_ptr[1] = key_ptr[0] + key_len[0] + 1;
 109     key_ptr[2] = key_ptr[1] + key_len[1] + 1;
 110     key_ptr[3] = key_ptr[2] + key_len[2] + 1;
 111
 112     for (; srclen; srclen--, src++)
 113     {
 114         unsigned int i, decomposed_len = 1;/*wine_decompose(*src, dummy, 4);*/
 115         dummy[0] = *src;
 116         if (decomposed_len)
 117         {
 118             for (i = 0; i < decomposed_len; i++)
 119             {
 120                 WCHAR wch = dummy[i];
 121                 unsigned int ce;
 122
 123                 /* tests show that win2k just ignores NORM_IGNORENONSPACE,
 124                  * and skips white space and punctuation characters for
 125                  * NORM_IGNORESYMBOLS.
 126                  */
 127                 if ((flags & NORM_IGNORESYMBOLS) && (get_char_typeW(wch) & (C1_PUNCT | C1_SPACE)))
 128                     continue;
 129
 130                 if (flags & NORM_IGNORECASE) wch = tolowerW(wch);
 131
 132                 ce = collation_table[collation_table[collation_table[wch >> 8] + ((wch >> 4) & 0x0f)] + (wch & 0xf)];
 133                 if (ce != (unsigned int)-1)
 134                 {
 135                     WCHAR key;
 136                     if ((key = ce >> 16))
 137                     {
 138                         *key_ptr[0]++ = key >> 8;
 139                         *key_ptr[0]++ = key & 0xff;
 140                     }
 141                     /* make key 1 start from 2 */
 142                     if ((key = (ce >> 8) & 0xff)) *key_ptr[1]++ = key + 1;
 143                     /* make key 2 start from 2 */
 144                     if ((key = (ce >> 4) & 0x0f)) *key_ptr[2]++ = key + 1;
 145                     /* key 3 is always a character code */
 146                     if (ce & 1)
 147                     {
 148                         if (wch >> 8) *key_ptr[3]++ = wch >> 8;
 149                         if (wch & 0xff) *key_ptr[3]++ = wch & 0xff;
 150                     }
 151                 }
 152                 else
 153                 {
 154                     *key_ptr[0]++ = 0xff;
 155                     *key_ptr[0]++ = 0xfe;
 156                     if (wch >> 8) *key_ptr[0]++ = wch >> 8;
 157                     if (wch & 0xff) *key_ptr[0]++ = wch & 0xff;
 158                 }
 159             }
 160         }
 161     }
 162
 163     *key_ptr[0] = '\1';
 164     *key_ptr[1] = '\1';
 165     *key_ptr[2] = '\1';
 166     *key_ptr[3]++ = '\1';
 167     *key_ptr[3] = 0;
 168
 169     return key_ptr[3] - dst;
 170 }
 171
 172 enum weight
 173 {
 174     UNICODE_WEIGHT,
 175     DIACRITIC_WEIGHT,
 176     CASE_WEIGHT
 177 };
 178
 179 static unsigned int get_weight(WCHAR ch, enum weight type)
 180 {
 181     unsigned int ret;
 182
 183     ret = collation_table[collation_table[collation_table[ch >> 8] + ((ch >> 4) & 0x0f)] + (ch & 0xf)];
 184     if (ret == (unsigned int)-1)
 185         return ch;
 186
 187     switch(type)
 188     {
 189     case UNICODE_WEIGHT:
 190         return ret >> 16;
 191     case DIACRITIC_WEIGHT:
 192         return (ret >> 8) & 0xff;
 193     case CASE_WEIGHT:
 194     default:
 195         return (ret >> 4) & 0x0f;
 196     }
 197 }
 198
 199 static void inc_str_pos(const WCHAR **str, int *len, unsigned int *dpos, unsigned int *dlen)
 200 {
 201     (*dpos)++;
 202     if (*dpos == *dlen)
 203     {
 204         *dpos = *dlen = 0;
 205         (*str)++;
 206         (*len)--;
 207     }
 208 }
 209
 210 static inline int compare_weights(int flags, const WCHAR *str1, int len1,
 211                                   const WCHAR *str2, int len2, enum weight type)
 212 {
 213     unsigned int ce1, ce2, dpos1 = 0, dpos2 = 0, dlen1 = 0, dlen2 = 0;
 214     const WCHAR *dstr1 = NULL, *dstr2 = NULL;
 215
 216     /* 32-bit collation element table format:
 217      * unicode weight - high 16 bit, diacritic weight - high 8 bit of low 16 bit,
 218      * case weight - high 4 bit of low 8 bit.
 219      */
 220     while (len1 > 0 && len2 > 0)
 221     {
 222         if (!dlen1 && !(dstr1 = get_decomposition( *str1, &dlen1 ))) dstr1 = str1;
 223         if (!dlen2 && !(dstr2 = get_decomposition( *str2, &dlen2 ))) dstr2 = str2;
 224
 225         if (flags & NORM_IGNORESYMBOLS)
 226         {
 227             int skip = 0;
 228             /* FIXME: not tested */
 229             if (get_char_typeW(dstr1[dpos1]) & (C1_PUNCT | C1_SPACE))
 230             {
 231                 inc_str_pos(&str1, &len1, &dpos1, &dlen1);
 232                 skip = 1;
 233             }
 234             if (get_char_typeW(dstr2[dpos2]) & (C1_PUNCT | C1_SPACE))
 235             {
 236                 inc_str_pos(&str2, &len2, &dpos2, &dlen2);
 237                 skip = 1;
 238             }
 239             if (skip) continue;
 240         }
 241
 242        /* hyphen and apostrophe are treated differently depending on
 243         * whether SORT_STRINGSORT specified or not
 244         */
 245         if (type == UNICODE_WEIGHT && !(flags & SORT_STRINGSORT))
 246         {
 247             if (dstr1[dpos1] == '-' || dstr1[dpos1] == '\'')
 248             {
 249                 if (dstr2[dpos2] != '-' && dstr2[dpos2] != '\'')
 250                 {
 251                     inc_str_pos(&str1, &len1, &dpos1, &dlen1);
 252                     continue;
 253                 }
 254             }
 255             else if (dstr2[dpos2] == '-' || dstr2[dpos2] == '\'')
 256             {
 257                 inc_str_pos(&str2, &len2, &dpos2, &dlen2);
 258                 continue;
 259             }
 260         }
 261
 262         ce1 = get_weight(dstr1[dpos1], type);
 263         if (!ce1)
 264         {
 265             inc_str_pos(&str1, &len1, &dpos1, &dlen1);
 266             continue;
 267         }
 268         ce2 = get_weight(dstr2[dpos2], type);
 269         if (!ce2)
 270         {
 271             inc_str_pos(&str2, &len2, &dpos2, &dlen2);
 272             continue;
 273         }
 274
 275         if (ce1 - ce2) return ce1 - ce2;
 276
 277         inc_str_pos(&str1, &len1, &dpos1, &dlen1);
 278         inc_str_pos(&str2, &len2, &dpos2, &dlen2);
 279     }
 280     while (len1)
 281     {
 282         if (!dlen1 && !(dstr1 = get_decomposition( *str1, &dlen1 ))) dstr1 = str1;
 283         ce1 = get_weight(dstr1[dpos1], type);
 284         if (ce1) break;
 285         inc_str_pos(&str1, &len1, &dpos1, &dlen1);
 286     }
 287     while (len2)
 288     {
 289         if (!dlen2 && !(dstr2 = get_decomposition( *str2, &dlen2 ))) dstr2 = str2;
 290         ce2 = get_weight(dstr2[dpos2], type);
 291         if (ce2) break;
 292         inc_str_pos(&str2, &len2, &dpos2, &dlen2);
 293     }
 294     return len1 - len2;
 295 }
 296
 297 int wine_compare_string_obsolete(int flags, const WCHAR *str1, int len1,
 298                                  const WCHAR *str2, int len2)
 299 {
 300     int ret;
 301
 302     ret = compare_weights(flags, str1, len1, str2, len2, UNICODE_WEIGHT);
 303     if (!ret)
 304     {
 305         if (!(flags & NORM_IGNORENONSPACE))
 306             ret = compare_weights(flags, str1, len1, str2, len2, DIACRITIC_WEIGHT);
 307         if (!ret && !(flags & NORM_IGNORECASE))
 308             ret = compare_weights(flags, str1, len1, str2, len2, CASE_WEIGHT);
 309     }
 310     return ret;
 311 }
 312
 313 __ASM_OBSOLETE(wine_get_sortkey);
 314 __ASM_OBSOLETE(wine_compare_string);
 315
 316 #endif /* __ASM_OBSOLETE */