[PATCH v2] kernel32: Implement FindNLSStringEx. Tests included.

[Sergio Gómez Del Real]

On 12/03/18 10:52, Sergio Gómez Del Real wrote:

> On 12/03/18 10:36, Huw Davies wrote:
>
>> On Mon, Mar 12, 2018 at 10:31:31AM -0500, Sergio Gómez Del Real wrote:
>>> On 12/03/18 10:13, Huw Davies wrote:
>>>
>>>> On Mon, Mar 12, 2018 at 09:39:16AM -0500, Sergio Gómez Del Real wrote:
>>>>> On 12/03/18 06:03, Nikolay Sivov wrote:
>>>>>       On 3/12/2018 12:25 PM, Huw Davies wrote:
>>>>>                 +                           LPARAM sort_handle)
>>>>>                 +{
>>>>>                 +
>>>>>                 +    DWORD mask = flags;
>>>>>                 +
>>>>>                 +    TRACE("%s %x %s %d %s %d %p %p %p %ld\n",
>>>>>                 wine_dbgstr_w(localename), flags,
>>>>>                 +          wine_dbgstr_w(src), src_size,
>>>>>                 wine_dbgstr_w(value), value_size, found,
>>>>>                 +          version_info, reserved, sort_handle);
>>>>>                 +    FIXME("strings should be normalized once
>>>>>                 NormalizeString() is implemented\n");
>>>>>            I don't think we want the noise that this FIXME would
>>>>>            generate.  Just add a comment.
>>>>>       Actually it might be possible that CompareString() handles decomposed
>>>>>       case on its own, I haven't tested that.
>>>>>
>>>>> Yeah, you are right Nikolai; I just tested on Windows and it seems that
>>>>> CompareString() shares the same comparison semantics with FindNLSStringEx(). On
>>>>> Wine it fails, however, so I guess I'd code FindNLSStringEx() assuming a
>>>>> working CompareString(), and then see what is missing there.
>>>>> I actually had it like this in my first patch, relying on CompareString
>>>>> (assuming the shared semantics). I wanted to normalize first in this v2 patch
>>>>> so that the substring search would be worst case o(n) instead of o(n.m).
>>>>> However, reading the Unicode standard, it seems that I can make some
>>>>> assumptions about the maximum expansion factor in decomposition (when assuming
>>>>> canonical decomposition).
>>>> If CompareStringEx handles the normailization, then you'd call it in
>>>> pretty much the same way as you do in the current patch (though you'd
>>>> loop right through to the end, not stopping value_size from the end).
>>>> The tricky bit would be getting the 'found' length.  For that you'd
>>>> probably use an internal version of CompareStringEx that returned
>>>> this info.
>>>>
>>>> For now, I'd stick with the fixme comment.
>>>>
>>>> Huw.
>>> Hi, Huw,
>>> Maybe I'm not following well, but in the current patch I'm always calling
>>> CompareStringEx() with the same string length for both strings (value_size).
>>> Being this the case, I'm not sure if CompareStringEx() would succeed when it
>>> needs to, even if it did normalization.
>> Grrr, right.   This is why you'd do the normailization before calling
>> CompareStringEx().
>>
>> Huw.
>
> I'm not really sure what assumptions I can make to avoid an o(n.m), 
> since both of the strings can be presented with characters in any 
> (pre)composed form... I don't know if the trouble trying to find a way 
> to upper-bound the search with a length (3x? 5x?) would be worth 
> considering that it seems to be the normal case that we don't get too 
> long strings to compare, and relatively little use of the function 
> itself. Would brute-force o(n.m) be /too/ bad?
>

That is, it seems that the substring search for Unicode strings can get 
arbitrarily complex, so as to make o(n.m) unavoidable.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.winehq.org/pipermail/wine-devel/attachments/20180312/8dffd7ee/attachment.html>