[ros-diffs] [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?…
==============================================================================
--- 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));