[pschweitzer] 53859: [NTOSKRNL] Fix FsRtlIs*InExpression() by (finally) implementing backtracking. No regressions noticed regarding kmtest. Also commented code.
26 Sep
2011
26 Sep
'11
5:58 a.m.
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?…
==============================================================================
--- 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=…
==============================================================================
--- 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));
4742
days inactive
4742
days old
0 comments
1 participants
participants (1)
-
pschweitzer＠svn.reactos.org