1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 
5 using System.Diagnostics;
6 using System.Runtime.InteropServices;
7 
8 namespace System.Globalization
9 {
10     public partial class CompareInfo
11     {
InitSort(CultureInfo culture)12         private unsafe void InitSort(CultureInfo culture)
13         {
14             _sortName = culture.SortName;
15 
16             if (_invariantMode)
17             {
18                 _sortHandle = IntPtr.Zero;
19             }
20             else
21             {
22                 const uint LCMAP_SORTHANDLE = 0x20000000;
23 
24                 IntPtr handle;
25                 int ret = Interop.Kernel32.LCMapStringEx(_sortName, LCMAP_SORTHANDLE, null, 0, &handle, IntPtr.Size, null, null, IntPtr.Zero);
26                 _sortHandle = ret > 0 ? handle : IntPtr.Zero;
27             }
28         }
29 
FindStringOrdinal( uint dwFindStringOrdinalFlags, string stringSource, int offset, int cchSource, string value, int cchValue, bool bIgnoreCase)30         private static unsafe int FindStringOrdinal(
31             uint dwFindStringOrdinalFlags,
32             string stringSource,
33             int offset,
34             int cchSource,
35             string value,
36             int cchValue,
37             bool bIgnoreCase)
38         {
39             Debug.Assert(!GlobalizationMode.Invariant);
40 
41             fixed (char* pSource = stringSource)
42             fixed (char* pValue = value)
43             {
44                 int ret = Interop.Kernel32.FindStringOrdinal(
45                             dwFindStringOrdinalFlags,
46                             pSource + offset,
47                             cchSource,
48                             pValue,
49                             cchValue,
50                             bIgnoreCase ? 1 : 0);
51                 return ret < 0 ? ret : ret + offset;
52             }
53         }
54 
IndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)55         internal static int IndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)
56         {
57             Debug.Assert(!GlobalizationMode.Invariant);
58 
59             Debug.Assert(source != null);
60             Debug.Assert(value != null);
61 
62             return FindStringOrdinal(FIND_FROMSTART, source, startIndex, count, value, value.Length, ignoreCase);
63         }
64 
LastIndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)65         internal static int LastIndexOfOrdinalCore(string source, string value, int startIndex, int count, bool ignoreCase)
66         {
67             Debug.Assert(!GlobalizationMode.Invariant);
68 
69             Debug.Assert(source != null);
70             Debug.Assert(value != null);
71 
72             return FindStringOrdinal(FIND_FROMEND, source, startIndex - count + 1, count, value, value.Length, ignoreCase);
73         }
74 
GetHashCodeOfStringCore(string source, CompareOptions options)75         private unsafe int GetHashCodeOfStringCore(string source, CompareOptions options)
76         {
77             Debug.Assert(!_invariantMode);
78 
79             Debug.Assert(source != null);
80             Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
81 
82             if (source.Length == 0)
83             {
84                 return 0;
85             }
86 
87             int tmpHash = 0;
88 
89             fixed (char* pSource = source)
90             {
91                 if (Interop.Kernel32.LCMapStringEx(_sortHandle != IntPtr.Zero ? null : _sortName,
92                                                   LCMAP_HASH | (uint)GetNativeCompareFlags(options),
93                                                   pSource, source.Length,
94                                                   &tmpHash, sizeof(int),
95                                                   null, null, _sortHandle) == 0)
96                 {
97                     Environment.FailFast("LCMapStringEx failed!");
98                 }
99             }
100 
101             return tmpHash;
102         }
103 
CompareStringOrdinalIgnoreCase(char* string1, int count1, char* string2, int count2)104         private static unsafe int CompareStringOrdinalIgnoreCase(char* string1, int count1, char* string2, int count2)
105         {
106             Debug.Assert(!GlobalizationMode.Invariant);
107 
108             // Use the OS to compare and then convert the result to expected value by subtracting 2
109             return Interop.Kernel32.CompareStringOrdinal(string1, count1, string2, count2, true) - 2;
110         }
111 
112         // TODO https://github.com/dotnet/coreclr/issues/13827:
113         // This method shouldn't be necessary, as we should be able to just use the overload
114         // that takes two spans.  But due to this issue, that's adding significant overhead.
CompareString(ReadOnlySpan<char> string1, string string2, CompareOptions options)115         private unsafe int CompareString(ReadOnlySpan<char> string1, string string2, CompareOptions options)
116         {
117             Debug.Assert(string2 != null);
118             Debug.Assert(!_invariantMode);
119             Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
120 
121             string localeName = _sortHandle != IntPtr.Zero ? null : _sortName;
122 
123             fixed (char* pLocaleName = localeName)
124             fixed (char* pString1 = &MemoryMarshal.GetReference(string1))
125             fixed (char* pString2 = &string2.GetRawStringData())
126             {
127                 int result = Interop.Kernel32.CompareStringEx(
128                                     pLocaleName,
129                                     (uint)GetNativeCompareFlags(options),
130                                     pString1,
131                                     string1.Length,
132                                     pString2,
133                                     string2.Length,
134                                     null,
135                                     null,
136                                     _sortHandle);
137 
138                 if (result == 0)
139                 {
140                     Environment.FailFast("CompareStringEx failed");
141                 }
142 
143                 // Map CompareStringEx return value to -1, 0, 1.
144                 return result - 2;
145             }
146         }
147 
CompareString(ReadOnlySpan<char> string1, ReadOnlySpan<char> string2, CompareOptions options)148         private unsafe int CompareString(ReadOnlySpan<char> string1, ReadOnlySpan<char> string2, CompareOptions options)
149         {
150             Debug.Assert(!_invariantMode);
151             Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
152 
153             string localeName = _sortHandle != IntPtr.Zero ? null : _sortName;
154 
155             fixed (char* pLocaleName = localeName)
156             fixed (char* pString1 = &MemoryMarshal.GetReference(string1))
157             fixed (char* pString2 = &MemoryMarshal.GetReference(string2))
158             {
159                 int result = Interop.Kernel32.CompareStringEx(
160                                     pLocaleName,
161                                     (uint)GetNativeCompareFlags(options),
162                                     pString1,
163                                     string1.Length,
164                                     pString2,
165                                     string2.Length,
166                                     null,
167                                     null,
168                                     _sortHandle);
169 
170                 if (result == 0)
171                 {
172                     Environment.FailFast("CompareStringEx failed");
173                 }
174 
175                 // Map CompareStringEx return value to -1, 0, 1.
176                 return result - 2;
177             }
178         }
179 
FindString( uint dwFindNLSStringFlags, string lpStringSource, int startSource, int cchSource, string lpStringValue, int startValue, int cchValue, int* pcchFound)180         private unsafe int FindString(
181                     uint dwFindNLSStringFlags,
182                     string lpStringSource,
183                     int startSource,
184                     int cchSource,
185                     string lpStringValue,
186                     int startValue,
187                     int cchValue,
188                     int* pcchFound)
189         {
190             Debug.Assert(!_invariantMode);
191 
192             string localeName = _sortHandle != IntPtr.Zero ? null : _sortName;
193 
194             fixed (char* pLocaleName = localeName)
195             fixed (char* pSource = lpStringSource)
196             fixed (char* pValue = lpStringValue)
197             {
198                 char* pS = pSource + startSource;
199                 char* pV = pValue + startValue;
200 
201                 return Interop.Kernel32.FindNLSStringEx(
202                                     pLocaleName,
203                                     dwFindNLSStringFlags,
204                                     pS,
205                                     cchSource,
206                                     pV,
207                                     cchValue,
208                                     pcchFound,
209                                     null,
210                                     null,
211                                     _sortHandle);
212             }
213         }
214 
IndexOfCore(string source, string target, int startIndex, int count, CompareOptions options, int* matchLengthPtr)215         internal unsafe int IndexOfCore(string source, string target, int startIndex, int count, CompareOptions options, int* matchLengthPtr)
216         {
217             Debug.Assert(!string.IsNullOrEmpty(source));
218             Debug.Assert(target != null);
219             Debug.Assert((options & CompareOptions.OrdinalIgnoreCase) == 0);
220 
221             int index;
222 
223             // TODO: Consider moving this up to the relevent APIs we need to ensure this behavior for
224             // and add a precondition that target is not empty.
225             if (target.Length == 0)
226             {
227                 if(matchLengthPtr != null)
228                     *matchLengthPtr = 0;
229                 return startIndex;       // keep Whidbey compatibility
230             }
231 
232             if ((options & CompareOptions.Ordinal) != 0)
233             {
234                 index = FastIndexOfString(source, target, startIndex, count, target.Length, findLastIndex: false);
235                 if(index != -1 && matchLengthPtr != null)
236                     *matchLengthPtr = target.Length;
237 
238                 return index;
239             }
240             else
241             {
242                 int retValue = FindString(FIND_FROMSTART | (uint)GetNativeCompareFlags(options),
243                                                                source,
244                                                                startIndex,
245                                                                count,
246                                                                target,
247                                                                0,
248                                                                target.Length,
249                                                                matchLengthPtr);
250                 if (retValue >= 0)
251                 {
252                     return retValue + startIndex;
253                 }
254             }
255 
256             return -1;
257         }
258 
LastIndexOfCore(string source, string target, int startIndex, int count, CompareOptions options)259         private unsafe int LastIndexOfCore(string source, string target, int startIndex, int count, CompareOptions options)
260         {
261             Debug.Assert(!_invariantMode);
262 
263             Debug.Assert(!string.IsNullOrEmpty(source));
264             Debug.Assert(target != null);
265             Debug.Assert((options & CompareOptions.OrdinalIgnoreCase) == 0);
266 
267             // TODO: Consider moving this up to the relevent APIs we need to ensure this behavior for
268             // and add a precondition that target is not empty.
269             if (target.Length == 0)
270                 return startIndex;       // keep Whidbey compatibility
271 
272             if ((options & CompareOptions.Ordinal) != 0)
273             {
274                 return FastIndexOfString(source, target, startIndex, count, target.Length, findLastIndex: true);
275             }
276             else
277             {
278                 int retValue = FindString(FIND_FROMEND | (uint)GetNativeCompareFlags(options),
279                                                                source,
280                                                                startIndex - count + 1,
281                                                                count,
282                                                                target,
283                                                                0,
284                                                                target.Length,
285                                                                null);
286 
287                 if (retValue >= 0)
288                 {
289                     return retValue + startIndex - (count - 1);
290                 }
291             }
292 
293             return -1;
294         }
295 
StartsWith(string source, string prefix, CompareOptions options)296         private unsafe bool StartsWith(string source, string prefix, CompareOptions options)
297         {
298             Debug.Assert(!_invariantMode);
299 
300             Debug.Assert(!string.IsNullOrEmpty(source));
301             Debug.Assert(!string.IsNullOrEmpty(prefix));
302             Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
303 
304             return FindString(FIND_STARTSWITH | (uint)GetNativeCompareFlags(options),
305                                                    source,
306                                                    0,
307                                                    source.Length,
308                                                    prefix,
309                                                    0,
310                                                    prefix.Length,
311                                                    null) >= 0;
312         }
313 
EndsWith(string source, string suffix, CompareOptions options)314         private unsafe bool EndsWith(string source, string suffix, CompareOptions options)
315         {
316             Debug.Assert(!_invariantMode);
317 
318             Debug.Assert(!string.IsNullOrEmpty(source));
319             Debug.Assert(!string.IsNullOrEmpty(suffix));
320             Debug.Assert((options & (CompareOptions.Ordinal | CompareOptions.OrdinalIgnoreCase)) == 0);
321 
322             return FindString(FIND_ENDSWITH | (uint)GetNativeCompareFlags(options),
323                                                    source,
324                                                    0,
325                                                    source.Length,
326                                                    suffix,
327                                                    0,
328                                                    suffix.Length,
329                                                    null) >= 0;
330         }
331 
332         // PAL ends here
333         [NonSerialized]
334         private IntPtr _sortHandle;
335 
336         private const uint LCMAP_SORTKEY = 0x00000400;
337         private const uint LCMAP_HASH = 0x00040000;
338 
339         private const int FIND_STARTSWITH = 0x00100000;
340         private const int FIND_ENDSWITH = 0x00200000;
341         private const int FIND_FROMSTART = 0x00400000;
342         private const int FIND_FROMEND = 0x00800000;
343 
344         // TODO: Instead of this method could we just have upstack code call IndexOfOrdinal with ignoreCase = false?
FastIndexOfString(string source, string target, int startIndex, int sourceCount, int targetCount, bool findLastIndex)345         private static unsafe int FastIndexOfString(string source, string target, int startIndex, int sourceCount, int targetCount, bool findLastIndex)
346         {
347             int retValue = -1;
348 
349             int sourceStartIndex = findLastIndex ? startIndex - sourceCount + 1 : startIndex;
350 
351             fixed (char* pSource = source, spTarget = target)
352             {
353                 char* spSubSource = pSource + sourceStartIndex;
354 
355                 if (findLastIndex)
356                 {
357                     int startPattern = (sourceCount - 1) - targetCount + 1;
358                     if (startPattern < 0)
359                         return -1;
360 
361                     char patternChar0 = spTarget[0];
362                     for (int ctrSrc = startPattern; ctrSrc >= 0; ctrSrc--)
363                     {
364                         if (spSubSource[ctrSrc] != patternChar0)
365                             continue;
366 
367                         int ctrPat;
368                         for (ctrPat = 1; ctrPat < targetCount; ctrPat++)
369                         {
370                             if (spSubSource[ctrSrc + ctrPat] != spTarget[ctrPat])
371                                 break;
372                         }
373                         if (ctrPat == targetCount)
374                         {
375                             retValue = ctrSrc;
376                             break;
377                         }
378                     }
379 
380                     if (retValue >= 0)
381                     {
382                         retValue += startIndex - sourceCount + 1;
383                     }
384                 }
385                 else
386                 {
387                     int endPattern = (sourceCount - 1) - targetCount + 1;
388                     if (endPattern < 0)
389                         return -1;
390 
391                     char patternChar0 = spTarget[0];
392                     for (int ctrSrc = 0; ctrSrc <= endPattern; ctrSrc++)
393                     {
394                         if (spSubSource[ctrSrc] != patternChar0)
395                             continue;
396                         int ctrPat;
397                         for (ctrPat = 1; ctrPat < targetCount; ctrPat++)
398                         {
399                             if (spSubSource[ctrSrc + ctrPat] != spTarget[ctrPat])
400                                 break;
401                         }
402                         if (ctrPat == targetCount)
403                         {
404                             retValue = ctrSrc;
405                             break;
406                         }
407                     }
408 
409                     if (retValue >= 0)
410                     {
411                         retValue += startIndex;
412                     }
413                 }
414             }
415 
416             return retValue;
417         }
418 
CreateSortKey(String source, CompareOptions options)419         private unsafe SortKey CreateSortKey(String source, CompareOptions options)
420         {
421             Debug.Assert(!_invariantMode);
422 
423             if (source == null) { throw new ArgumentNullException(nameof(source)); }
424 
425             if ((options & ValidSortkeyCtorMaskOffFlags) != 0)
426             {
427                 throw new ArgumentException(SR.Argument_InvalidFlag, nameof(options));
428             }
429 
430             byte [] keyData = null;
431             if (source.Length == 0)
432             {
433                 keyData = Array.Empty<byte>();
434             }
435             else
436             {
437                 fixed (char *pSource = source)
438                 {
439                     int result = Interop.Kernel32.LCMapStringEx(_sortHandle != IntPtr.Zero ? null : _sortName,
440                                                 LCMAP_SORTKEY | (uint) GetNativeCompareFlags(options),
441                                                 pSource, source.Length,
442                                                 null, 0,
443                                                 null, null, _sortHandle);
444                     if (result == 0)
445                     {
446                         throw new ArgumentException(SR.Argument_InvalidFlag, "source");
447                     }
448 
449                     keyData = new byte[result];
450 
451                     fixed (byte* pBytes =  keyData)
452                     {
453                         result = Interop.Kernel32.LCMapStringEx(_sortHandle != IntPtr.Zero ? null : _sortName,
454                                                 LCMAP_SORTKEY | (uint) GetNativeCompareFlags(options),
455                                                 pSource, source.Length,
456                                                 pBytes, keyData.Length,
457                                                 null, null, _sortHandle);
458                     }
459                 }
460             }
461 
462             return new SortKey(Name, source, options, keyData);
463         }
464 
IsSortable(char* text, int length)465         private static unsafe bool IsSortable(char* text, int length)
466         {
467             Debug.Assert(!GlobalizationMode.Invariant);
468 
469             return Interop.Kernel32.IsNLSDefinedString(Interop.Kernel32.COMPARE_STRING, 0, IntPtr.Zero, text, length);
470         }
471 
472         private const int COMPARE_OPTIONS_ORDINAL = 0x40000000;       // Ordinal
473         private const int NORM_IGNORECASE = 0x00000001;       // Ignores case.  (use LINGUISTIC_IGNORECASE instead)
474         private const int NORM_IGNOREKANATYPE = 0x00010000;       // Does not differentiate between Hiragana and Katakana characters. Corresponding Hiragana and Katakana will compare as equal.
475         private const int NORM_IGNORENONSPACE = 0x00000002;       // Ignores nonspacing. This flag also removes Japanese accent characters.  (use LINGUISTIC_IGNOREDIACRITIC instead)
476         private const int NORM_IGNORESYMBOLS = 0x00000004;       // Ignores symbols.
477         private const int NORM_IGNOREWIDTH = 0x00020000;       // Does not differentiate between a single-byte character and the same character as a double-byte character.
478         private const int NORM_LINGUISTIC_CASING = 0x08000000;       // use linguistic rules for casing
479         private const int SORT_STRINGSORT = 0x00001000;       // Treats punctuation the same as symbols.
480 
GetNativeCompareFlags(CompareOptions options)481         private static int GetNativeCompareFlags(CompareOptions options)
482         {
483             // Use "linguistic casing" by default (load the culture's casing exception tables)
484             int nativeCompareFlags = NORM_LINGUISTIC_CASING;
485 
486             if ((options & CompareOptions.IgnoreCase) != 0) { nativeCompareFlags |= NORM_IGNORECASE; }
487             if ((options & CompareOptions.IgnoreKanaType) != 0) { nativeCompareFlags |= NORM_IGNOREKANATYPE; }
488             if ((options & CompareOptions.IgnoreNonSpace) != 0) { nativeCompareFlags |= NORM_IGNORENONSPACE; }
489             if ((options & CompareOptions.IgnoreSymbols) != 0) { nativeCompareFlags |= NORM_IGNORESYMBOLS; }
490             if ((options & CompareOptions.IgnoreWidth) != 0) { nativeCompareFlags |= NORM_IGNOREWIDTH; }
491             if ((options & CompareOptions.StringSort) != 0) { nativeCompareFlags |= SORT_STRINGSORT; }
492 
493             // TODO: Can we try for GetNativeCompareFlags to never
494             // take Ordinal or OrdinalIgnoreCase.  This value is not part of Win32, we just handle it special
495             // in some places.
496             // Suffix & Prefix shouldn't use this, make sure to turn off the NORM_LINGUISTIC_CASING flag
497             if (options == CompareOptions.Ordinal) { nativeCompareFlags = COMPARE_OPTIONS_ORDINAL; }
498 
499             Debug.Assert(((options & ~(CompareOptions.IgnoreCase |
500                                           CompareOptions.IgnoreKanaType |
501                                           CompareOptions.IgnoreNonSpace |
502                                           CompareOptions.IgnoreSymbols |
503                                           CompareOptions.IgnoreWidth |
504                                           CompareOptions.StringSort)) == 0) ||
505                              (options == CompareOptions.Ordinal), "[CompareInfo.GetNativeCompareFlags]Expected all flags to be handled");
506 
507             return nativeCompareFlags;
508         }
509 
GetSortVersion()510         private unsafe SortVersion GetSortVersion()
511         {
512             Debug.Assert(!_invariantMode);
513 
514             Interop.Kernel32.NlsVersionInfoEx nlsVersion = new Interop.Kernel32.NlsVersionInfoEx();
515             Interop.Kernel32.GetNLSVersionEx(Interop.Kernel32.COMPARE_STRING, _sortName, &nlsVersion);
516             return new SortVersion(
517                         nlsVersion.dwNLSVersion,
518                         nlsVersion.dwEffectiveId == 0 ? LCID : nlsVersion.dwEffectiveId,
519                         nlsVersion.guidCustomVersion);
520         }
521     }
522 }
523