ntoskrnl/kdbg/kdb_expr.c

   1 /*
   2  *  ReactOS kernel
   3  *  Copyright (C) 2005 ReactOS Team
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License along
  16  *  with this program; if not, write to the Free Software Foundation, Inc.,
  17  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18  */
  19 /*
  20  * PROJECT:         ReactOS kernel
  21  * FILE:            ntoskrnl/kdbg/kdb_expr.c
  22  * PURPOSE:         Kernel debugger expression evaluation
  23  * PROGRAMMER:      Gregor Anich (blight@blight.eu.org)
  24  * UPDATE HISTORY:
  25  *                  Created 15/01/2005
  26  */
  27
  28 /* Note:
  29  *
  30  * The given expression is parsed and stored in reverse polish notation,
  31  * then it is evaluated and the result is returned.
  32  */
  33
  34 /* INCLUDES ******************************************************************/
  35
  36 #include <ntoskrnl.h>
  37 #define NDEBUG
  38 #include <debug.h>
  39
  40 /* TYPES *********************************************************************/
  41 typedef enum _RPN_OP_TYPE
  42 {
  43     RpnOpNop,
  44     RpnOpBinaryOperator,
  45     RpnOpUnaryOperator,
  46     RpnOpImmediate,
  47     RpnOpRegister,
  48     RpnOpDereference
  49 } RPN_OP_TYPE;
  50
  51 typedef ULONGLONG (*RPN_BINARY_OPERATOR)(ULONGLONG a, ULONGLONG b);
  52
  53 typedef struct _RPN_OP
  54 {
  55     RPN_OP_TYPE  Type;
  56     ULONG        CharacterOffset;
  57     union
  58     {
  59         /* RpnOpBinaryOperator */
  60         RPN_BINARY_OPERATOR  BinaryOperator;
  61         /* RpnOpImmediate */
  62         ULONGLONG            Immediate;
  63         /* RpnOpRegister */
  64         UCHAR                Register;
  65         /* RpnOpDereference */
  66         UCHAR                DerefMemorySize;
  67     }
  68     Data;
  69 }
  70 RPN_OP, *PRPN_OP;
  71
  72 typedef struct _RPN_STACK
  73 {
  74     ULONG   Size;     /* Number of RPN_OPs on Ops */
  75     ULONG   Sp;       /* Stack pointer */
  76     RPN_OP  Ops[1];   /* Array of RPN_OPs */
  77 }
  78 RPN_STACK, *PRPN_STACK;
  79
  80 /* DEFINES *******************************************************************/
  81 #define stricmp _stricmp
  82
  83 #ifndef RTL_FIELD_SIZE
  84 # define RTL_FIELD_SIZE(type, field) (sizeof(((type *)0)->field))
  85 #endif
  86
  87 #define CONST_STRCPY(dst, src) \
  88     do { if ((dst)) { memcpy(dst, src, sizeof(src)); } } while (0);
  89
  90 #define RPN_OP_STACK_SIZE     256
  91 #define RPN_VALUE_STACK_SIZE  256
  92
  93 /* GLOBALS *******************************************************************/
  94 static struct
  95 {
  96     ULONG Size;
  97     ULONG Sp;
  98     RPN_OP Ops[RPN_OP_STACK_SIZE];
  99 }
 100 RpnStack =
 101 {
 102     RPN_OP_STACK_SIZE,
 103     0
 104 };
 105
 106 static const struct
 107 {
 108     PCHAR Name;
 109     UCHAR Offset;
 110     UCHAR Size;
 111 }
 112 RegisterToTrapFrame[] =
 113 {
 114     {"eip",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Eip),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Eip)},
 115     {"eflags",  FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.EFlags),  RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.EFlags)},
 116     {"eax",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Eax),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Eax)},
 117     {"ebx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Ebx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Ebx)},
 118     {"ecx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Ecx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Ecx)},
 119     {"edx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Edx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Edx)},
 120     {"esi",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Esi),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Esi)},
 121     {"edi",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Edi),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Edi)},
 122     {"esp",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.HardwareEsp),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.HardwareEsp)},
 123     {"ebp",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Ebp),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Ebp)},
 124     {"cs",      FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.SegCs),      2 }, /* Use only the lower 2 bytes */
 125     {"ds",      FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.SegDs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.SegDs)},
 126     {"es",      FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.SegEs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.SegEs)},
 127     {"fs",      FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.SegFs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.SegFs)},
 128     {"gs",      FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.SegGs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.SegGs)},
 129     {"ss",      FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.HardwareSegSs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.HardwareSegSs)},
 130     {"dr0",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Dr0),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Dr0)},
 131     {"dr1",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Dr1),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Dr1)},
 132     {"dr2",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Dr2),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Dr2)},
 133     {"dr3",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Dr3),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Dr3)},
 134     {"dr6",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Dr6),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Dr6)},
 135     {"dr7",     FIELD_OFFSET(KDB_KTRAP_FRAME, Tf.Dr7),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Tf.Dr7)},
 136     {"cr0",     FIELD_OFFSET(KDB_KTRAP_FRAME, Cr0),        RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Cr0)},
 137     {"cr2",     FIELD_OFFSET(KDB_KTRAP_FRAME, Cr2),        RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Cr2)},
 138     {"cr3",     FIELD_OFFSET(KDB_KTRAP_FRAME, Cr3),        RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Cr3)},
 139     {"cr4",     FIELD_OFFSET(KDB_KTRAP_FRAME, Cr4),        RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Cr4)}
 140 };
 141 static const INT RegisterToTrapFrameCount = sizeof (RegisterToTrapFrame) / sizeof (RegisterToTrapFrame[0]);
 142
 143 /* FUNCTIONS *****************************************************************/
 144
 145 ULONGLONG
 146 RpnBinaryOperatorAdd(
 147     ULONGLONG a,
 148     ULONGLONG b)
 149 {
 150     return a + b;
 151 }
 152
 153 ULONGLONG
 154 RpnBinaryOperatorSub(
 155     ULONGLONG a,
 156     ULONGLONG b)
 157 {
 158     return a - b;
 159 }
 160
 161 ULONGLONG
 162 RpnBinaryOperatorMul(
 163     ULONGLONG a,
 164     ULONGLONG b)
 165 {
 166     return a * b;
 167 }
 168
 169 ULONGLONG
 170 RpnBinaryOperatorDiv(
 171     ULONGLONG a,
 172     ULONGLONG b)
 173 {
 174     return a / b;
 175 }
 176
 177 ULONGLONG
 178 RpnBinaryOperatorMod(
 179     ULONGLONG a,
 180     ULONGLONG b)
 181 {
 182     return a % b;
 183 }
 184
 185 ULONGLONG
 186 RpnBinaryOperatorEquals(
 187     ULONGLONG a,
 188     ULONGLONG b)
 189 {
 190     return (a == b);
 191 }
 192
 193 ULONGLONG
 194 RpnBinaryOperatorNotEquals(
 195     ULONGLONG a,
 196     ULONGLONG b)
 197 {
 198     return (a != b);
 199 }
 200
 201 ULONGLONG
 202 RpnBinaryOperatorLessThan(
 203     ULONGLONG a,
 204     ULONGLONG b)
 205 {
 206     return (a < b);
 207 }
 208
 209 ULONGLONG
 210 RpnBinaryOperatorLessThanOrEquals(
 211     ULONGLONG a,
 212     ULONGLONG b)
 213 {
 214     return (a <= b);
 215 }
 216
 217 ULONGLONG
 218 RpnBinaryOperatorGreaterThan(
 219     ULONGLONG a,
 220     ULONGLONG b)
 221 {
 222     return (a > b);
 223 }
 224
 225 ULONGLONG
 226 RpnBinaryOperatorGreaterThanOrEquals(
 227     ULONGLONG a,
 228     ULONGLONG b)
 229 {
 230     return (a >= b);
 231 }
 232
 233 /*!\brief Dumps the given RPN stack content
 234  *
 235  * \param Stack  Pointer to a RPN_STACK structure.
 236  */
 237 VOID
 238 RpnpDumpStack(
 239     IN PRPN_STACK Stack)
 240 {
 241     ULONG ul;
 242
 243     ASSERT(Stack);
 244     DbgPrint("\nStack size: %ld\n", Stack->Sp);
 245
 246     for (ul = 0; ul < Stack->Sp; ul++)
 247     {
 248         PRPN_OP Op = Stack->Ops + ul;
 249         switch (Op->Type)
 250         {
 251             case RpnOpNop:
 252                 DbgPrint("NOP,");
 253                 break;
 254
 255             case RpnOpImmediate:
 256                 DbgPrint("0x%I64x,", Op->Data.Immediate);
 257                 break;
 258
 259             case RpnOpBinaryOperator:
 260                 if (Op->Data.BinaryOperator == RpnBinaryOperatorAdd)
 261                     DbgPrint("+,");
 262                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorSub)
 263                     DbgPrint("-,");
 264                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorMul)
 265                     DbgPrint("*,");
 266                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorDiv)
 267                     DbgPrint("/,");
 268                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorMod)
 269                     DbgPrint("%%,");
 270                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorEquals)
 271                     DbgPrint("==,");
 272                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorNotEquals)
 273                     DbgPrint("!=,");
 274                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorLessThan)
 275                     DbgPrint("<,");
 276                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorLessThanOrEquals)
 277                     DbgPrint("<=,");
 278                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorGreaterThan)
 279                     DbgPrint(">,");
 280                 else if (Op->Data.BinaryOperator == RpnBinaryOperatorGreaterThanOrEquals)
 281                     DbgPrint(">=,");
 282                 else
 283                     DbgPrint("UNKNOWN OP,");
 284
 285                 break;
 286
 287             case RpnOpRegister:
 288                 DbgPrint("%s,", RegisterToTrapFrame[Op->Data.Register].Name);
 289                 break;
 290
 291             case RpnOpDereference:
 292                 DbgPrint("[%s],",
 293                     (Op->Data.DerefMemorySize == 1) ? ("byte") :
 294                     ((Op->Data.DerefMemorySize == 2) ? ("word") :
 295                     ((Op->Data.DerefMemorySize == 4) ? ("dword") : ("qword"))));
 296                 break;
 297
 298             default:
 299                 DbgPrint("\nUnsupported Type: %d\n", Op->Type);
 300                 ul = Stack->Sp;
 301                 break;
 302         }
 303     }
 304
 305     DbgPrint("\n");
 306 }
 307
 308 /*!\brief Clears the given RPN stack.
 309  *
 310  * \param Stack  Pointer to a RPN_STACK structure.
 311  */
 312 static VOID
 313 RpnpClearStack(
 314     OUT PRPN_STACK Stack)
 315 {
 316     ASSERT(Stack);
 317     Stack->Sp = 0;
 318 }
 319
 320 /*!\brief Pushes an RPN_OP onto the stack.
 321  *
 322  * \param Stack  Pointer to a RPN_STACK structure.
 323  * \param Op     RPN_OP to be copied onto the stack.
 324  */
 325 static BOOLEAN
 326 RpnpPushStack(
 327     IN OUT PRPN_STACK Stack,
 328     IN     PRPN_OP Op)
 329 {
 330     ASSERT(Stack);
 331     ASSERT(Op);
 332
 333     if (Stack->Sp >= Stack->Size)
 334         return FALSE;
 335
 336     memcpy(Stack->Ops + Stack->Sp, Op, sizeof (RPN_OP));
 337     Stack->Sp++;
 338
 339     return TRUE;
 340 }
 341
 342 /*!\brief Pops the top op from the stack.
 343  *
 344  * \param Stack  Pointer to a RPN_STACK structure.
 345  * \param Op     Pointer to an RPN_OP to store the popped op into (can be NULL).
 346  *
 347  * \retval TRUE   Success.
 348  * \retval FALSE  Failure (stack empty)
 349  */
 350 static BOOLEAN
 351 RpnpPopStack(
 352     IN OUT PRPN_STACK Stack,
 353     OUT    PRPN_OP Op  OPTIONAL)
 354 {
 355     ASSERT(Stack);
 356
 357     if (Stack->Sp == 0)
 358         return FALSE;
 359
 360     Stack->Sp--;
 361     if (Op)
 362         memcpy(Op, Stack->Ops + Stack->Sp, sizeof (RPN_OP));
 363
 364     return TRUE;
 365 }
 366
 367 /*!\brief Gets the top op from the stack (not popping it)
 368  *
 369  * \param Stack  Pointer to a RPN_STACK structure.
 370  * \param Op     Pointer to an RPN_OP to copy the top op into.
 371  *
 372  * \retval TRUE   Success.
 373  * \retval FALSE  Failure (stack empty)
 374  */
 375 static BOOLEAN
 376 RpnpTopStack(
 377     IN  PRPN_STACK Stack,
 378     OUT PRPN_OP Op)
 379 {
 380     ASSERT(Stack);
 381     ASSERT(Op);
 382
 383     if (Stack->Sp == 0)
 384         return FALSE;
 385
 386     memcpy(Op, Stack->Ops + Stack->Sp - 1, sizeof (RPN_OP));
 387
 388     return TRUE;
 389 }
 390
 391 /*!\brief Parses an expression.
 392  *
 393  * This functions parses the given expression until the end of string or a closing
 394  * brace is found. As the function parses the string it pushes RPN_OPs onto the
 395  * stack.
 396  *
 397  * Examples: 1+2*3 ; eax+10 ; (eax+16) * (ebx+4) ; dword[eax]
 398  *
 399  * \param Stack            Pointer to a RPN_STACK structure.
 400  * \param Expression       String to parse.
 401  * \param CharacterOffset  Character offset of the subexpression from the beginning of the expression.
 402  * \param End              On success End is set to the character at which parsing stopped.
 403  * \param ErrOffset        On failure this is set to the character offset at which the error occoured.
 404  * \param ErrMsg           On failure a message describing the problem is copied into this buffer (128 bytes)
 405  *
 406  * \retval TRUE   Success.
 407  * \retval FALSE  Failure.
 408  */
 409 static BOOLEAN
 410 RpnpParseExpression(
 411     IN  PRPN_STACK Stack,
 412     IN  PCHAR Expression,
 413     OUT PCHAR *End  OPTIONAL,
 414     IN  ULONG CharacterOffset,
 415     OUT PLONG ErrOffset  OPTIONAL,
 416     OUT PCHAR ErrMsg  OPTIONAL)
 417 {
 418     PCHAR p = Expression;
 419     PCHAR pend;
 420     PCHAR Operator = NULL;
 421     LONG OperatorOffset = -1;
 422     RPN_OP RpnOp;
 423     RPN_OP PoppedOperator;
 424     BOOLEAN HavePoppedOperator = FALSE;
 425     RPN_OP ComparativeOp;
 426     BOOLEAN ComparativeOpFilled = FALSE;
 427     BOOLEAN IsComparativeOp;
 428     INT i, i2;
 429     ULONG ul;
 430     UCHAR MemorySize;
 431     CHAR Buffer[16];
 432     BOOLEAN First;
 433
 434     ASSERT(Stack);
 435     ASSERT(Expression);
 436
 437     First = TRUE;
 438     for (;;)
 439     {
 440         /* Skip whitespace */
 441         while (isspace(*p))
 442         {
 443             p++;
 444             CharacterOffset++;
 445         }
 446
 447         /* Check for end of expression */
 448         if (p[0] == '\0' || p[0] == ')' || p[0] == ']')
 449             break;
 450
 451         if (!First)
 452         {
 453             /* Remember operator */
 454             Operator = p++;
 455             OperatorOffset = CharacterOffset++;
 456
 457             /* Pop operator (to get the right operator precedence) */
 458             HavePoppedOperator = FALSE;
 459             if (*Operator == '*' || *Operator == '/' || *Operator == '%')
 460             {
 461                 if (RpnpTopStack(Stack, &PoppedOperator) &&
 462                     PoppedOperator.Type == RpnOpBinaryOperator &&
 463                     (PoppedOperator.Data.BinaryOperator == RpnBinaryOperatorAdd ||
 464                     PoppedOperator.Data.BinaryOperator == RpnBinaryOperatorSub))
 465                 {
 466                     RpnpPopStack(Stack, NULL);
 467                     HavePoppedOperator = TRUE;
 468                 }
 469                 else if (PoppedOperator.Type == RpnOpNop)
 470                 {
 471                     RpnpPopStack(Stack, NULL);
 472                     /* Discard the NOP - it was only pushed to indicate there was a
 473                      * closing brace, so the previous operator shouldn't be popped.
 474                      */
 475                 }
 476             }
 477             else if ((Operator[0] == '=' && Operator[1] == '=') ||
 478                      (Operator[0] == '!' && Operator[1] == '=') ||
 479                      Operator[0] == '<' || Operator[0] == '>')
 480             {
 481                 if (Operator[0] == '=' || Operator[0] == '!' ||
 482                     (Operator[0] == '<' && Operator[1] == '=') ||
 483                     (Operator[0] == '>' && Operator[1] == '='))
 484                 {
 485                     p++;
 486                     CharacterOffset++;
 487                 }
 488 #if 0
 489                 /* Parse rest of expression */
 490                 if (!RpnpParseExpression(Stack, p + 1, &pend, CharacterOffset + 1,
 491                                          ErrOffset, ErrMsg))
 492                 {
 493                     return FALSE;
 494                 }
 495                 else if (pend == p + 1)
 496                 {
 497                     CONST_STRCPY(ErrMsg, "Expression expected");
 498
 499                     if (ErrOffset)
 500                         *ErrOffset = CharacterOffset + 1;
 501
 502                     return FALSE;
 503                 }
 504
 505                 goto end_of_expression; /* return */
 506 #endif
 507             }
 508             else if (Operator[0] != '+' && Operator[0] != '-')
 509             {
 510                 CONST_STRCPY(ErrMsg, "Operator expected");
 511
 512                 if (ErrOffset)
 513                     *ErrOffset = OperatorOffset;
 514
 515                 return FALSE;
 516             }
 517
 518             /* Skip whitespace */
 519             while (isspace(*p))
 520             {
 521                 p++;
 522                 CharacterOffset++;
 523             }
 524         }
 525
 526         /* Get operand */
 527         MemorySize = sizeof(ULONG_PTR); /* default to pointer size */
 528
 529 get_operand:
 530         i = strcspn(p, "+-*/%()[]<>!=");
 531         if (i > 0)
 532         {
 533             i2 = i;
 534
 535             /* Copy register name/memory size */
 536             while (isspace(p[--i2]));
 537
 538             i2 = min(i2 + 1, (INT)sizeof (Buffer) - 1);
 539             strncpy(Buffer, p, i2);
 540             Buffer[i2] = '\0';
 541
 542             /* Memory size prefix */
 543             if (p[i] == '[')
 544             {
 545                 if (stricmp(Buffer, "byte") == 0)
 546                     MemorySize = 1;
 547                 else if (stricmp(Buffer, "word") == 0)
 548                     MemorySize = 2;
 549                 else if (stricmp(Buffer, "dword") == 0)
 550                     MemorySize = 4;
 551                 else if (stricmp(Buffer, "qword") == 0)
 552                     MemorySize = 8;
 553                 else
 554                 {
 555                     CONST_STRCPY(ErrMsg, "Invalid memory size prefix");
 556
 557                     if (ErrOffset)
 558                         *ErrOffset = CharacterOffset;
 559
 560                     return FALSE;
 561                 }
 562
 563                 p += i;
 564                 CharacterOffset += i;
 565                 goto get_operand;
 566             }
 567
 568             /* Try to find register */
 569             for (i = 0; i < RegisterToTrapFrameCount; i++)
 570             {
 571                 if (stricmp(RegisterToTrapFrame[i].Name, Buffer) == 0)
 572                     break;
 573             }
 574
 575             if (i < RegisterToTrapFrameCount)
 576             {
 577                 RpnOp.Type = RpnOpRegister;
 578                 RpnOp.CharacterOffset = CharacterOffset;
 579                 RpnOp.Data.Register = i;
 580                 i = strlen(RegisterToTrapFrame[i].Name);
 581                 CharacterOffset += i;
 582                 p += i;
 583             }
 584             else
 585             {
 586                 /* Immediate value */
 587                 /* FIXME: Need string to ULONGLONG function */
 588                 ul = strtoul(p, &pend, 0);
 589                 if (p != pend)
 590                 {
 591                     RpnOp.Type = RpnOpImmediate;
 592                     RpnOp.CharacterOffset = CharacterOffset;
 593                     RpnOp.Data.Immediate = (ULONGLONG)ul;
 594                     CharacterOffset += pend - p;
 595                     p = pend;
 596                 }
 597                 else
 598                 {
 599                     CONST_STRCPY(ErrMsg, "Operand expected");
 600
 601                     if (ErrOffset)
 602                         *ErrOffset = CharacterOffset;
 603
 604                     return FALSE;
 605                 }
 606             }
 607
 608             /* Push operand */
 609             if (!RpnpPushStack(Stack, &RpnOp))
 610             {
 611                 CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 612
 613                 if (ErrOffset)
 614                     *ErrOffset = -1;
 615
 616                 return FALSE;
 617             }
 618         }
 619         else if (i == 0)
 620         {
 621             if (p[0] == '(' || p[0] == '[') /* subexpression */
 622             {
 623                 if (!RpnpParseExpression(Stack, p + 1, &pend, CharacterOffset + 1,
 624                                          ErrOffset, ErrMsg))
 625                 {
 626                     return FALSE;
 627                 }
 628                 else if (pend == p + 1)
 629                 {
 630                     CONST_STRCPY(ErrMsg, "Expression expected");
 631
 632                     if (ErrOffset)
 633                         *ErrOffset = CharacterOffset + 1;
 634
 635                     return FALSE;
 636                 }
 637
 638                 if (p[0] == '[') /* dereference */
 639                 {
 640                     ASSERT(MemorySize == 1 || MemorySize == 2 ||
 641                            MemorySize == 4 || MemorySize == 8);
 642
 643                     if (pend[0] != ']')
 644                     {
 645                         CONST_STRCPY(ErrMsg, "']' expected");
 646
 647                         if (ErrOffset)
 648                             *ErrOffset = CharacterOffset + (pend - p);
 649
 650                         return FALSE;
 651                     }
 652
 653                     RpnOp.Type = RpnOpDereference;
 654                     RpnOp.CharacterOffset = CharacterOffset;
 655                     RpnOp.Data.DerefMemorySize = MemorySize;
 656
 657                     if (!RpnpPushStack(Stack, &RpnOp))
 658                     {
 659                         CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 660
 661                         if (ErrOffset)
 662                             *ErrOffset = -1;
 663
 664                         return FALSE;
 665                     }
 666                 }
 667                 else /* p[0] == '(' */
 668                 {
 669                     if (pend[0] != ')')
 670                     {
 671                         CONST_STRCPY(ErrMsg, "')' expected");
 672
 673                         if (ErrOffset)
 674                             *ErrOffset = CharacterOffset + (pend - p);
 675
 676                         return FALSE;
 677                     }
 678                 }
 679
 680                 /* Push a "nop" to prevent popping of the + operator (which would
 681                  * result in (10+10)/2 beeing evaluated as 15)
 682                  */
 683                 RpnOp.Type = RpnOpNop;
 684                 if (!RpnpPushStack(Stack, &RpnOp))
 685                 {
 686                     CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 687
 688                     if (ErrOffset)
 689                         *ErrOffset = -1;
 690
 691                     return FALSE;
 692                 }
 693
 694                 /* Skip closing brace/bracket */
 695                 pend++;
 696
 697                 CharacterOffset += pend - p;
 698                 p = pend;
 699             }
 700             else if (First && p[0] == '-') /* Allow expressions like "- eax" */
 701             {
 702                 RpnOp.Type = RpnOpImmediate;
 703                 RpnOp.CharacterOffset = CharacterOffset;
 704                 RpnOp.Data.Immediate = 0;
 705
 706                 if (!RpnpPushStack(Stack, &RpnOp))
 707                 {
 708                     CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 709
 710                     if (ErrOffset)
 711                         *ErrOffset = -1;
 712
 713                     return FALSE;
 714                 }
 715             }
 716             else
 717             {
 718                 CONST_STRCPY(ErrMsg, "Operand expected");
 719
 720                 if (ErrOffset)
 721                     *ErrOffset = CharacterOffset;
 722
 723                 return FALSE;
 724             }
 725         }
 726         else
 727         {
 728             CONST_STRCPY(ErrMsg, "strcspn() failed");
 729
 730             if (ErrOffset)
 731                 *ErrOffset = -1;
 732
 733             return FALSE;
 734         }
 735
 736         if (!First)
 737         {
 738             /* Push operator */
 739             RpnOp.CharacterOffset = OperatorOffset;
 740             RpnOp.Type = RpnOpBinaryOperator;
 741             IsComparativeOp = FALSE;
 742
 743             switch (*Operator)
 744             {
 745                 case '+':
 746                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorAdd;
 747                     break;
 748
 749                 case '-':
 750                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorSub;
 751                     break;
 752
 753                 case '*':
 754                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorMul;
 755                     break;
 756
 757                 case '/':
 758                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorDiv;
 759                     break;
 760
 761                 case '%':
 762                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorMod;
 763                     break;
 764
 765                 case '=':
 766                     ASSERT(Operator[1] == '=');
 767                     IsComparativeOp = TRUE;
 768                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorEquals;
 769                     break;
 770
 771                 case '!':
 772                     ASSERT(Operator[1] == '=');
 773                     IsComparativeOp = TRUE;
 774                     RpnOp.Data.BinaryOperator = RpnBinaryOperatorNotEquals;
 775                     break;
 776
 777                 case '<':
 778                     IsComparativeOp = TRUE;
 779
 780                     if (Operator[1] == '=')
 781                         RpnOp.Data.BinaryOperator = RpnBinaryOperatorLessThanOrEquals;
 782                     else
 783                         RpnOp.Data.BinaryOperator = RpnBinaryOperatorLessThan;
 784
 785                     break;
 786
 787                 case '>':
 788                     IsComparativeOp = TRUE;
 789
 790                     if (Operator[1] == '=')
 791                         RpnOp.Data.BinaryOperator = RpnBinaryOperatorGreaterThanOrEquals;
 792                     else
 793                         RpnOp.Data.BinaryOperator = RpnBinaryOperatorGreaterThan;
 794
 795                     break;
 796
 797                 default:
 798                     ASSERT(0);
 799                     break;
 800             }
 801
 802             if (IsComparativeOp)
 803             {
 804                 if (ComparativeOpFilled && !RpnpPushStack(Stack, &ComparativeOp))
 805                 {
 806                     CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 807
 808                     if (ErrOffset)
 809                         *ErrOffset = -1;
 810
 811                     return FALSE;
 812                 }
 813
 814                 memcpy(&ComparativeOp, &RpnOp, sizeof(RPN_OP));
 815                 ComparativeOpFilled = TRUE;
 816             }
 817             else if (!RpnpPushStack(Stack, &RpnOp))
 818             {
 819                 CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 820
 821                 if (ErrOffset)
 822                     *ErrOffset = -1;
 823
 824                 return FALSE;
 825             }
 826
 827             /* Push popped operator */
 828             if (HavePoppedOperator)
 829             {
 830                 if (!RpnpPushStack(Stack, &PoppedOperator))
 831                 {
 832                     CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 833
 834                     if (ErrOffset)
 835                         *ErrOffset = -1;
 836
 837                     return FALSE;
 838                 }
 839             }
 840         }
 841
 842         First = FALSE;
 843     }
 844
 845 //end_of_expression:
 846
 847     if (ComparativeOpFilled && !RpnpPushStack(Stack, &ComparativeOp))
 848     {
 849         CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 850
 851         if (ErrOffset)
 852             *ErrOffset = -1;
 853
 854         return FALSE;
 855     }
 856
 857     /* Skip whitespace */
 858     while (isspace(*p))
 859     {
 860         p++;
 861         CharacterOffset++;
 862     }
 863
 864     if (End)
 865         *End = p;
 866
 867     return TRUE;
 868 }
 869
 870 /*!\brief Evaluates the RPN op stack and returns the result.
 871  *
 872  * \param Stack      Pointer to a RPN_STACK structure.
 873  * \param TrapFrame  Register values.
 874  * \param Result     Pointer to an ULONG to store the result into.
 875  * \param ErrOffset  On failure this is set to the character offset at which the error occoured.
 876  * \param ErrMsg     Buffer which receives an error message on failure (128 bytes)
 877  *
 878  * \retval TRUE   Success.
 879  * \retval FALSE  Failure.
 880  */
 881 static BOOLEAN
 882 RpnpEvaluateStack(
 883     IN  PRPN_STACK Stack,
 884     IN  PKDB_KTRAP_FRAME TrapFrame,
 885     OUT PULONGLONG Result,
 886     OUT PLONG ErrOffset  OPTIONAL,
 887     OUT PCHAR ErrMsg  OPTIONAL)
 888 {
 889     ULONGLONG ValueStack[RPN_VALUE_STACK_SIZE];
 890     ULONG ValueStackPointer = 0;
 891     ULONG index;
 892     ULONGLONG ull;
 893     ULONG ul;
 894     USHORT us;
 895     UCHAR uc;
 896     PVOID p;
 897     BOOLEAN Ok;
 898 #ifdef DEBUG_RPN
 899     ULONG ValueStackPointerMax = 0;
 900 #endif
 901
 902     ASSERT(Stack);
 903     ASSERT(TrapFrame);
 904     ASSERT(Result);
 905
 906     for (index = 0; index < Stack->Sp; index++)
 907     {
 908         PRPN_OP Op = Stack->Ops + index;
 909
 910 #ifdef DEBUG_RPN
 911         ValueStackPointerMax = max(ValueStackPointerMax, ValueStackPointer);
 912 #endif
 913
 914         switch (Op->Type)
 915         {
 916             case RpnOpNop:
 917                 /* No operation */
 918                 break;
 919
 920             case RpnOpImmediate:
 921                 if (ValueStackPointer == RPN_VALUE_STACK_SIZE)
 922                 {
 923                     CONST_STRCPY(ErrMsg, "Value stack overflow");
 924
 925                     if (ErrOffset)
 926                         *ErrOffset = -1;
 927
 928                     return FALSE;
 929                 }
 930
 931                 ValueStack[ValueStackPointer++] = Op->Data.Immediate;
 932                 break;
 933
 934             case RpnOpRegister:
 935                 if (ValueStackPointer == RPN_VALUE_STACK_SIZE)
 936                 {
 937                     CONST_STRCPY(ErrMsg, "Value stack overflow");
 938
 939                     if (ErrOffset)
 940                         *ErrOffset = -1;
 941
 942                     return FALSE;
 943                 }
 944
 945                 ul = Op->Data.Register;
 946                 p = (PVOID)((ULONG_PTR)TrapFrame + RegisterToTrapFrame[ul].Offset);
 947
 948                 switch (RegisterToTrapFrame[ul].Size)
 949                 {
 950                     case 1: ull = (ULONGLONG)(*(PUCHAR)p); break;
 951                     case 2: ull = (ULONGLONG)(*(PUSHORT)p); break;
 952                     case 4: ull = (ULONGLONG)(*(PULONG)p); break;
 953                     case 8: ull = (ULONGLONG)(*(PULONGLONG)p); break;
 954                     default: ASSERT(0); return FALSE; break;
 955                 }
 956
 957                 ValueStack[ValueStackPointer++] = ull;
 958                 break;
 959
 960             case RpnOpDereference:
 961                 if (ValueStackPointer < 1)
 962                 {
 963                     CONST_STRCPY(ErrMsg, "Value stack underflow");
 964
 965                     if (ErrOffset)
 966                         *ErrOffset = -1;
 967
 968                     return FALSE;
 969                 }
 970
 971                 /* FIXME: Print a warning when address is out of range */
 972                 p = (PVOID)(ULONG_PTR)ValueStack[ValueStackPointer - 1];
 973                 Ok = FALSE;
 974
 975                 switch (Op->Data.DerefMemorySize)
 976                 {
 977                     case 1:
 978                         if (NT_SUCCESS(KdbpSafeReadMemory(&uc, p, sizeof (uc))))
 979                         {
 980                             Ok = TRUE;
 981                             ull = (ULONGLONG)uc;
 982                         }
 983                         break;
 984
 985                     case 2:
 986                         if (NT_SUCCESS(KdbpSafeReadMemory(&us, p, sizeof (us))))
 987                         {
 988                             Ok = TRUE;
 989                             ull = (ULONGLONG)us;
 990                         }
 991                         break;
 992
 993                     case 4:
 994                         if (NT_SUCCESS(KdbpSafeReadMemory(&ul, p, sizeof (ul))))
 995                         {
 996                             Ok = TRUE;
 997                             ull = (ULONGLONG)ul;
 998                         }
 999                         break;
1000
1001                     case 8:
1002                         if (NT_SUCCESS(KdbpSafeReadMemory(&ull, p, sizeof (ull))))
1003                         {
1004                             Ok = TRUE;
1005                         }
1006                         break;
1007
1008                     default:
1009                         ASSERT(0);
1010                         return FALSE;
1011                         break;
1012                 }
1013
1014                 if (!Ok)
1015                 {
1016                     _snprintf(ErrMsg, 128, "Couldn't access memory at 0x%lx", (ULONG)p);
1017
1018                     if (ErrOffset)
1019                         *ErrOffset = Op->CharacterOffset;
1020
1021                     return FALSE;
1022                 }
1023
1024                 ValueStack[ValueStackPointer - 1] = ull;
1025                 break;
1026
1027             case RpnOpBinaryOperator:
1028                 if (ValueStackPointer < 2)
1029                 {
1030                     CONST_STRCPY(ErrMsg, "Value stack underflow");
1031
1032                     if (ErrOffset)
1033                         *ErrOffset = -1;
1034
1035                     return FALSE;
1036                 }
1037
1038                 ValueStackPointer--;
1039                 ull = ValueStack[ValueStackPointer];
1040
1041                 if (ull == 0 && Op->Data.BinaryOperator == RpnBinaryOperatorDiv)
1042                 {
1043                     CONST_STRCPY(ErrMsg, "Division by zero");
1044
1045                     if (ErrOffset)
1046                         *ErrOffset = Op->CharacterOffset;
1047
1048                     return FALSE;
1049                 }
1050
1051                 ull = Op->Data.BinaryOperator(ValueStack[ValueStackPointer - 1], ull);
1052                 ValueStack[ValueStackPointer - 1] = ull;
1053                 break;
1054
1055             default:
1056                 ASSERT(0);
1057                 return FALSE;
1058         }
1059     }
1060
1061 #ifdef DEBUG_RPN
1062     DPRINT1("Max value stack pointer: %d\n", ValueStackPointerMax);
1063 #endif
1064
1065     if (ValueStackPointer != 1)
1066     {
1067         CONST_STRCPY(ErrMsg, "Stack not empty after evaluation");
1068
1069         if (ErrOffset)
1070             *ErrOffset = -1;
1071
1072         return FALSE;
1073     }
1074
1075     *Result = ValueStack[0];
1076     return TRUE;
1077 }
1078
1079 /*!\brief Evaluates the given expression
1080  *
1081  * \param Expression  Expression to evaluate.
1082  * \param TrapFrame   Register values.
1083  * \param Result      Variable which receives the result on success.
1084  * \param ErrOffset   Variable which receives character offset on parse error (-1 on other errors)
1085  * \param ErrMsg      Buffer which receives an error message on failure (128 bytes)
1086  *
1087  * \retval TRUE   Success.
1088  * \retval FALSE  Failure.
1089  */
1090 BOOLEAN
1091 KdbpRpnEvaluateExpression(
1092     IN  PCHAR Expression,
1093     IN  PKDB_KTRAP_FRAME TrapFrame,
1094     OUT PULONGLONG Result,
1095     OUT PLONG ErrOffset  OPTIONAL,
1096     OUT PCHAR ErrMsg  OPTIONAL)
1097 {
1098     PRPN_STACK Stack = (PRPN_STACK)&RpnStack;
1099
1100     ASSERT(Expression);
1101     ASSERT(TrapFrame);
1102     ASSERT(Result);
1103
1104     /* Clear the stack and parse the expression */
1105     RpnpClearStack(Stack);
1106     if (!RpnpParseExpression(Stack, Expression, NULL, 0, ErrOffset, ErrMsg))
1107         return FALSE;
1108
1109 #ifdef DEBUG_RPN
1110     RpnpDumpStack(Stack);
1111 #endif
1112
1113     /* Evaluate the stack */
1114     if (!RpnpEvaluateStack(Stack, TrapFrame, Result, ErrOffset, ErrMsg))
1115         return FALSE;
1116
1117     return TRUE;
1118 }
1119
1120 /*!\brief Parses the given expression and returns a "handle" to it.
1121  *
1122  * \param Expression  Expression to evaluate.
1123  * \param ErrOffset   Variable which receives character offset on parse error (-1 on other errors)
1124  * \param ErrMsg      Buffer which receives an error message on failure (128 bytes)
1125  *
1126  * \returns "Handle" for the expression, NULL on failure.
1127  *
1128  * \sa KdbpRpnEvaluateExpression
1129  */
1130 PVOID
1131 KdbpRpnParseExpression(
1132     IN  PCHAR Expression,
1133     OUT PLONG ErrOffset  OPTIONAL,
1134     OUT PCHAR ErrMsg  OPTIONAL)
1135 {
1136     LONG Size;
1137     PRPN_STACK Stack = (PRPN_STACK)&RpnStack;
1138     PRPN_STACK NewStack;
1139
1140     ASSERT(Expression);
1141
1142     /* Clear the stack and parse the expression */
1143     RpnpClearStack(Stack);
1144     if (!RpnpParseExpression(Stack, Expression, NULL, 0, ErrOffset, ErrMsg))
1145         return FALSE;
1146
1147 #ifdef DEBUG_RPN
1148     RpnpDumpStack(Stack);
1149 #endif
1150
1151     /* Duplicate the stack and return a pointer/handle to it */
1152     ASSERT(Stack->Sp >= 1);
1153     Size = sizeof (RPN_STACK) + (RTL_FIELD_SIZE(RPN_STACK, Ops[0]) * (Stack->Sp - 1));
1154     NewStack = ExAllocatePoolWithTag(NonPagedPool, Size, TAG_KDBG);
1155
1156     if (!NewStack)
1157     {
1158         CONST_STRCPY(ErrMsg, "Out of memory");
1159
1160         if (ErrOffset)
1161             *ErrOffset = -1;
1162
1163         return NULL;
1164     }
1165
1166     memcpy(NewStack, Stack, Size);
1167     NewStack->Size = NewStack->Sp;
1168
1169     return NewStack;
1170 }
1171
1172 /*!\brief Evaluates the given expression and returns the result.
1173  *
1174  * \param Expression  Expression "handle" returned by KdbpRpnParseExpression.
1175  * \param TrapFrame   Register values.
1176  * \param Result      Variable which receives the result on success.
1177  * \param ErrOffset   Variable which receives character offset on parse error (-1 on other errors)
1178  * \param ErrMsg      Buffer which receives an error message on failure (128 bytes)
1179  *
1180  * \returns "Handle" for the expression, NULL on failure.
1181  *
1182  * \sa KdbpRpnParseExpression
1183  */
1184 BOOLEAN
1185 KdbpRpnEvaluateParsedExpression(
1186     IN  PVOID Expression,
1187     IN  PKDB_KTRAP_FRAME TrapFrame,
1188     OUT PULONGLONG Result,
1189     OUT PLONG ErrOffset  OPTIONAL,
1190     OUT PCHAR ErrMsg  OPTIONAL)
1191 {
1192     PRPN_STACK Stack = (PRPN_STACK)Expression;
1193
1194     ASSERT(Expression);
1195     ASSERT(TrapFrame);
1196     ASSERT(Result);
1197
1198     /* Evaluate the stack */
1199     return RpnpEvaluateStack(Stack, TrapFrame, Result, ErrOffset, ErrMsg);
1200 }
1201