Re: [Firebird-devel] FB2b2 3221225477

[Adriano d. S. F. <adr...@uo...>]

Vlad Horsun wrote:
>>> template <typename CharType>
>>> static void preKmp(const CharType *x, int m, SLONG kmpNext[]) 
>>> {
>>>     SLONG i = 0;
>>>     SLONG j = kmpNext[0] = -1;
>>>     while (i < m) {
>>>         while (j > -1 && x[i] != x[j])
>>>             j = kmpNext[j];
>>>         i++;
>>>         j++;
>>>         if (x[i] == x[j])         // AV here
>>>             kmpNext[i] = kmpNext[j];
>>>         else
>>>         kmpNext[i] = j;
>>>         }
>>> }
>>>
>>> Some variables at AV time :     m == 0x80, i == 0x80, j == 0x00
>>> Since i must be in range 0..0x7F (0..m-1) we have an AV when x[i] evaluated
>>>
>>>
>>>     As i understand this is a part of CONTAINING evaluation. The algorithm 
>>> was written by Nickolay and i unfortunately have no knowledge of how it must 
>>> work. May be Adriano can say more ?
>>>   
>>>       
>> I don't have knowledge of Knuth-Morris-Pratt algorithm, but I can say 
>> that preKmp is always accessing a invalid location.
>> The AV will occur with a "magic" string length, causing the invalid 
>> location is in another memory page.
>>
>> As it's probably that compare of garbage with part of the string is 
>> false, I propose to change the line to "if (i < m && x[i] == x[j])".
>>     
>
>     In that case we'll have invalid i (i == m) in kmpNext[i] = j expression.
No, because kmpNext has size = m + 1:
        kmpNext = reinterpret_cast<SLONG*>(alloc((_pattern_len + 1) * 
sizeof(SLONG)));

> It seems that we must change while (i < m) to while (i < m-1)
BTW, I have search for Knuth-Morris-Pratt and found that "official" 
algorithm is the one we have now.
This guy have the same problem of us: 
http://www.programmersheaven.com/c/MsgBoard/read.asp?Board=3&MsgID=258799&Setting=A9999F0001

And I found a Java version that do what you say (i < m - 1): 
http://www.koders.com/java/fid60C727551976C066420000B5CDF85F93A31A00BB.aspx?s=%22Knuth-Morris-Pratt%22. 
But I'm not sure the search part of the algorithm is the same of our.

First option seems more safe for me.


Adriano