[pschweitzer] 53859: [NTOSKRNL] Fix FsRtlIs*InExpression() by (finally) implementing backtracking. No regressions noticed regarding kmtest. Also commented code.
Author: pschweitzer Date: Mon Sep 26 05:58:13 2011 New Revision: 53859
URL: http://svn.reactos.org/svn/reactos?rev=53859&view=rev Log: [NTOSKRNL] Fix FsRtlIs*InExpression() by (finally) implementing backtracking. No regressions noticed regarding kmtest. Also commented code.
Modified: trunk/reactos/ntoskrnl/fsrtl/dbcsname.c trunk/reactos/ntoskrnl/fsrtl/name.c
Modified: trunk/reactos/ntoskrnl/fsrtl/dbcsname.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/fsrtl/dbcsname.c?r... ============================================================================== --- trunk/reactos/ntoskrnl/fsrtl/dbcsname.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/fsrtl/dbcsname.c [iso-8859-1] Mon Sep 26 05:58:13 2011 @@ -160,7 +160,9 @@ FsRtlIsDbcsInExpression(IN PANSI_STRING Expression, IN PANSI_STRING Name) { - USHORT ExpressionPosition = 0, NamePosition = 0, MatchingChars, StarFound = MAXUSHORT; + SHORT StarFound = -1; + PUSHORT BackTracking = NULL; + USHORT ExpressionPosition = 0, NamePosition = 0, MatchingChars; PAGED_CODE();
ASSERT(Name->Length); @@ -169,74 +171,44 @@
while (NamePosition < Name->Length && ExpressionPosition < Expression->Length) { + /* Basic check to test if chars are equal */ if ((Expression->Buffer[ExpressionPosition] == Name->Buffer[NamePosition])) { NamePosition++; ExpressionPosition++; } - else if (StarFound != MAXUSHORT && (Expression->Buffer[StarFound + 1] == '*' || - Expression->Buffer[StarFound + 1] == '?' || Expression->Buffer[StarFound + 1] == ANSI_DOS_DOT)) - { - ExpressionPosition = StarFound + 1; - switch (Expression->Buffer[ExpressionPosition]) - { - case '*': - StarFound = MAXUSHORT; - break; - - case '?': - if (++ExpressionPosition == Expression->Length) - { - NamePosition = Name->Length; - break; - } - - MatchingChars = NamePosition; - while (NamePosition < Name->Length && - Name->Buffer[NamePosition] != Expression->Buffer[ExpressionPosition]) - { - NamePosition++; - } - - if (NamePosition - MatchingChars > 0) - { - StarFound = MAXUSHORT; - } - break; - - case ANSI_DOS_DOT: - while (NamePosition < Name->Length && Name->Buffer[NamePosition] != '.') - { - NamePosition++; - } - ExpressionPosition++; - StarFound = MAXUSHORT; - break; - - default: - /* Should never happen */ - ASSERT(FALSE); - } - } + /* Check cases that eat one char */ else if ((Expression->Buffer[ExpressionPosition] == '?') || (Expression->Buffer[ExpressionPosition] == ANSI_DOS_QM) || (Expression->Buffer[ExpressionPosition] == ANSI_DOS_DOT && Name->Buffer[NamePosition] == '.')) { NamePosition++; ExpressionPosition++; - StarFound = MAXUSHORT; - } + } + /* Test star */ else if (Expression->Buffer[ExpressionPosition] == '*') { - StarFound = ExpressionPosition++; + /* Save star position */ + if (!BackTracking) + { + BackTracking = ExAllocatePoolWithTag(PagedPool | POOL_RAISE_IF_ALLOCATION_FAILURE, + Expression->Length * sizeof(USHORT), 'nrSF'); + } + BackTracking[++StarFound] = ExpressionPosition++; + + /* If star is at the end, then eat all rest and leave */ if (ExpressionPosition == Expression->Length) { NamePosition = Name->Length; break; } - } + else if (Expression->Buffer[ExpressionPosition] != '?') + { + NamePosition++; + } + } + /* Check DOS_STAR */ else if (Expression->Buffer[ExpressionPosition] == ANSI_DOS_STAR) { - StarFound = MAXUSHORT; MatchingChars = NamePosition; while (MatchingChars < Name->Length) { @@ -248,18 +220,23 @@ } ExpressionPosition++; } - else if (StarFound != MAXUSHORT) - { - ExpressionPosition = StarFound + 1; - while (NamePosition < Name->Length && - Name->Buffer[NamePosition] != Expression->Buffer[ExpressionPosition]) - { - NamePosition++; - } - } + /* If nothing match, try to backtrack */ + else if (StarFound >= 0) + { + ExpressionPosition = BackTracking[StarFound--]; + } + /* Otherwise, fail */ else { break; + } + + /* Under certain circumstances, expression is over, but name isn't + * and we can backtrack, then, backtrack */ + if (ExpressionPosition == Expression->Length && + NamePosition != Name->Length && StarFound >= 0) + { + ExpressionPosition = BackTracking[StarFound--]; } } if (ExpressionPosition + 1 == Expression->Length && NamePosition == Name->Length &&
Modified: trunk/reactos/ntoskrnl/fsrtl/name.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/ntoskrnl/fsrtl/name.c?rev=5... ============================================================================== --- trunk/reactos/ntoskrnl/fsrtl/name.c [iso-8859-1] (original) +++ trunk/reactos/ntoskrnl/fsrtl/name.c [iso-8859-1] Mon Sep 26 05:58:13 2011 @@ -23,8 +23,10 @@ IN BOOLEAN IgnoreCase, IN PWCHAR UpcaseTable OPTIONAL) { - USHORT ExpressionPosition = 0, NamePosition = 0, MatchingChars, StarFound = MAXUSHORT; + SHORT StarFound = -1; + PUSHORT BackTracking = NULL; UNICODE_STRING IntExpression; + USHORT ExpressionPosition = 0, NamePosition = 0, MatchingChars; PAGED_CODE();
/* Check if we were given strings at all */ @@ -99,76 +101,45 @@
while (NamePosition < Name->Length / sizeof(WCHAR) && ExpressionPosition < Expression->Length / sizeof(WCHAR)) { + /* Basic check to test if chars are equal */ if ((Expression->Buffer[ExpressionPosition] == (IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] : Name->Buffer[NamePosition]))) { NamePosition++; ExpressionPosition++; } - else if (StarFound != MAXUSHORT && (Expression->Buffer[StarFound + 1] == L'*' || - Expression->Buffer[StarFound + 1] == L'?' || Expression->Buffer[StarFound + 1] == DOS_DOT)) - { - ExpressionPosition = StarFound + 1; - switch (Expression->Buffer[ExpressionPosition]) - { - case L'*': - StarFound = MAXUSHORT; - break; - - case L'?': - if (++ExpressionPosition == Expression->Length / sizeof(WCHAR)) - { - NamePosition = Name->Length / sizeof(WCHAR); - break; - } - - MatchingChars = NamePosition; - while (NamePosition < Name->Length / sizeof(WCHAR) && - (IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] : - Name->Buffer[NamePosition]) != Expression->Buffer[ExpressionPosition]) - { - NamePosition++; - } - - if (NamePosition - MatchingChars > 0) - { - StarFound = MAXUSHORT; - } - break; - - case DOS_DOT: - while (NamePosition < Name->Length / sizeof(WCHAR) && - Name->Buffer[NamePosition] != L'.') - { - NamePosition++; - } - ExpressionPosition++; - StarFound = MAXUSHORT; - break; - - default: - /* Should never happen */ - ASSERT(FALSE); - } - } + /* Check cases that eat one char */ else if (Expression->Buffer[ExpressionPosition] == L'?' || (Expression->Buffer[ExpressionPosition] == DOS_QM) || (Expression->Buffer[ExpressionPosition] == DOS_DOT && Name->Buffer[NamePosition] == L'.')) { NamePosition++; ExpressionPosition++; - StarFound = MAXUSHORT; - } + } + /* Test star */ else if (Expression->Buffer[ExpressionPosition] == L'*') { - StarFound = ExpressionPosition++; + /* Save star position */ + if (!BackTracking) + { + BackTracking = ExAllocatePoolWithTag(PagedPool | POOL_RAISE_IF_ALLOCATION_FAILURE, + (Expression->Length / sizeof(WCHAR)) * sizeof(USHORT), + 'nrSF'); + } + BackTracking[++StarFound] = ExpressionPosition++; + + /* If star is at the end, then eat all rest and leave */ if (ExpressionPosition == Expression->Length / sizeof(WCHAR)) { NamePosition = Name->Length / sizeof(WCHAR); break; } - } + else if (Expression->Buffer[ExpressionPosition] != L'?') + { + NamePosition++; + } + } + /* Check DOS_STAR */ else if (Expression->Buffer[ExpressionPosition] == DOS_STAR) { - StarFound = MAXUSHORT; MatchingChars = NamePosition; while (MatchingChars < Name->Length / sizeof(WCHAR)) { @@ -180,25 +151,35 @@ } ExpressionPosition++; } - else if (StarFound != MAXUSHORT) - { - ExpressionPosition = StarFound + 1; - while (NamePosition < Name->Length / sizeof(WCHAR) && - (IgnoreCase ? UpcaseTable[Name->Buffer[NamePosition]] : - Name->Buffer[NamePosition]) != Expression->Buffer[ExpressionPosition]) - { - NamePosition++; - } - } + /* If nothing match, try to backtrack */ + else if (StarFound >= 0) + { + ExpressionPosition = BackTracking[StarFound--]; + } + /* Otherwise, fail */ else { break; + } + + /* Under certain circumstances, expression is over, but name isn't + * and we can backtrack, then, backtrack */ + if (ExpressionPosition == Expression->Length / sizeof(WCHAR) && + NamePosition != Name->Length / sizeof(WCHAR) && + StarFound >= 0) + { + ExpressionPosition = BackTracking[StarFound--]; } } if (ExpressionPosition + 1 == Expression->Length / sizeof(WCHAR) && NamePosition == Name->Length / sizeof(WCHAR) && Expression->Buffer[ExpressionPosition] == DOS_DOT) { ExpressionPosition++; + } + + if (BackTracking) + { + ExFreePoolWithTag(BackTracking, 'nrSF'); }
return (ExpressionPosition == Expression->Length / sizeof(WCHAR) && NamePosition == Name->Length / sizeof(WCHAR));
-
pschweitzer＠svn.reactos.org