kdb_expr.c

Go to the documentation of this file.

/*
 *  ReactOS kernel
 *  Copyright (C) 2005 ReactOS Team
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
/*
 * PROJECT:         ReactOS kernel
 * FILE:            ntoskrnl/kdbg/kdb_expr.c
 * PURPOSE:         Kernel debugger expression evaluation
 * PROGRAMMER:      Gregor Anich (blight@blight.eu.org)
 * UPDATE HISTORY:
 *                  Created 15/01/2005
 */
 
/* Note:
 *
 * The given expression is parsed and stored in reverse polish notation,
 * then it is evaluated and the result is returned.
 */
 
/* INCLUDES ******************************************************************/
 
#include <ntoskrnl.h>
#define NDEBUG
#include <debug.h>
 
/* TYPES *********************************************************************/
typedef enum _RPN_OP_TYPE
{
    RpnOpNop,
    RpnOpBinaryOperator,
    RpnOpUnaryOperator,
    RpnOpImmediate,
    RpnOpRegister,
    RpnOpDereference
} RPN_OP_TYPE;
 
typedef ULONGLONG (*RPN_BINARY_OPERATOR)(ULONGLONG a, ULONGLONG b);
 
typedef struct _RPN_OP
{
    RPN_OP_TYPE  Type;
    ULONG        CharacterOffset;
    union
    {
        /* RpnOpBinaryOperator */
        RPN_BINARY_OPERATOR  BinaryOperator;
        /* RpnOpImmediate */
        ULONGLONG            Immediate;
        /* RpnOpRegister */
        UCHAR                Register;
        /* RpnOpDereference */
        UCHAR                DerefMemorySize;
    }
    Data;
}
RPN_OP, *PRPN_OP;
 
typedef struct _RPN_STACK
{
    ULONG   Size;     /* Number of RPN_OPs on Ops */
    ULONG   Sp;       /* Stack pointer */
    RPN_OP  Ops[1];   /* Array of RPN_OPs */
}
RPN_STACK, *PRPN_STACK;
 
/* DEFINES *******************************************************************/
#define stricmp _stricmp
 
#ifndef RTL_FIELD_SIZE
# define RTL_FIELD_SIZE(type, field) (sizeof(((type *)0)->field))
#endif
 
#define CONST_STRCPY(dst, src) \
    do { if ((dst)) { memcpy(dst, src, sizeof(src)); } } while (0);
 
#define RPN_OP_STACK_SIZE     256
#define RPN_VALUE_STACK_SIZE  256
 
/* GLOBALS *******************************************************************/
static struct
{
    ULONG Size;
    ULONG Sp;
    RPN_OP Ops[RPN_OP_STACK_SIZE];
}
RpnStack =
{
    RPN_OP_STACK_SIZE,
    0
};
 
static const struct
{
    PCHAR Name;
    UCHAR Offset;
    UCHAR Size;
}
RegisterToTrapFrame[] =
{
    /* FIXME: X86 only */
#ifdef _M_IX86
    {"eip",     FIELD_OFFSET(KDB_KTRAP_FRAME, Eip),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Eip)},
#else
    {"rip",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rip),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rip)},
#endif
    {"eflags",  FIELD_OFFSET(KDB_KTRAP_FRAME, EFlags),  RTL_FIELD_SIZE(KDB_KTRAP_FRAME, EFlags)},
#ifdef _M_IX86
    {"eax",     FIELD_OFFSET(KDB_KTRAP_FRAME, Eax),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Eax)},
    {"ebx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Ebx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Ebx)},
    {"ecx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Ecx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Ecx)},
    {"edx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Edx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Edx)},
    {"esi",     FIELD_OFFSET(KDB_KTRAP_FRAME, Esi),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Esi)},
    {"edi",     FIELD_OFFSET(KDB_KTRAP_FRAME, Edi),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Edi)},
    {"esp",     FIELD_OFFSET(KDB_KTRAP_FRAME, Esp),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Esp)},
    {"ebp",     FIELD_OFFSET(KDB_KTRAP_FRAME, Ebp),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Ebp)},
#else
    {"rax",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rax),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rax)},
    {"rbx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rbx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rbx)},
    {"rcx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rcx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rcx)},
    {"rdx",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rdx),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rdx)},
    {"rsi",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rsi),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rsi)},
    {"rdi",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rdi),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rdi)},
    {"rsp",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rsp),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rsp)},
    {"rbp",     FIELD_OFFSET(KDB_KTRAP_FRAME, Rbp),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Rbp)},
#endif
    {"cs",      FIELD_OFFSET(KDB_KTRAP_FRAME, SegCs),      2 }, /* Use only the lower 2 bytes */
    {"ds",      FIELD_OFFSET(KDB_KTRAP_FRAME, SegDs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, SegDs)},
    {"es",      FIELD_OFFSET(KDB_KTRAP_FRAME, SegEs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, SegEs)},
    {"fs",      FIELD_OFFSET(KDB_KTRAP_FRAME, SegFs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, SegFs)},
    {"gs",      FIELD_OFFSET(KDB_KTRAP_FRAME, SegGs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, SegGs)},
    {"ss",      FIELD_OFFSET(KDB_KTRAP_FRAME, SegSs),      RTL_FIELD_SIZE(KDB_KTRAP_FRAME, SegSs)},
    {"dr0",     FIELD_OFFSET(KDB_KTRAP_FRAME, Dr0),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Dr0)},
    {"dr1",     FIELD_OFFSET(KDB_KTRAP_FRAME, Dr1),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Dr1)},
    {"dr2",     FIELD_OFFSET(KDB_KTRAP_FRAME, Dr2),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Dr2)},
    {"dr3",     FIELD_OFFSET(KDB_KTRAP_FRAME, Dr3),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Dr3)},
    {"dr6",     FIELD_OFFSET(KDB_KTRAP_FRAME, Dr6),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Dr6)},
    {"dr7",     FIELD_OFFSET(KDB_KTRAP_FRAME, Dr7),     RTL_FIELD_SIZE(KDB_KTRAP_FRAME, Dr7)}
};
static const INT RegisterToTrapFrameCount = sizeof (RegisterToTrapFrame) / sizeof (RegisterToTrapFrame[0]);
 
/* FUNCTIONS *****************************************************************/
 
ULONGLONG
RpnBinaryOperatorAdd(
    ULONGLONG a,
    ULONGLONG b)
{
    return a + b;
}
 
ULONGLONG
RpnBinaryOperatorSub(
    ULONGLONG a,
    ULONGLONG b)
{
    return a - b;
}
 
ULONGLONG
RpnBinaryOperatorMul(
    ULONGLONG a,
    ULONGLONG b)
{
    return a * b;
}
 
ULONGLONG
RpnBinaryOperatorDiv(
    ULONGLONG a,
    ULONGLONG b)
{
    return a / b;
}
 
ULONGLONG
RpnBinaryOperatorMod(
    ULONGLONG a,
    ULONGLONG b)
{
    return a % b;
}
 
ULONGLONG
RpnBinaryOperatorEquals(
    ULONGLONG a,
    ULONGLONG b)
{
    return (a == b);
}
 
ULONGLONG
RpnBinaryOperatorNotEquals(
    ULONGLONG a,
    ULONGLONG b)
{
    return (a != b);
}
 
ULONGLONG
RpnBinaryOperatorLessThan(
    ULONGLONG a,
    ULONGLONG b)
{
    return (a < b);
}
 
ULONGLONG
RpnBinaryOperatorLessThanOrEquals(
    ULONGLONG a,
    ULONGLONG b)
{
    return (a <= b);
}
 
ULONGLONG
RpnBinaryOperatorGreaterThan(
    ULONGLONG a,
    ULONGLONG b)
{
    return (a > b);
}
 
ULONGLONG
RpnBinaryOperatorGreaterThanOrEquals(
    ULONGLONG a,
    ULONGLONG b)
{
    return (a >= b);
}
 
VOID
RpnpDumpStack(
    IN PRPN_STACK Stack)
{
    ULONG ul;
 
    ASSERT(Stack);
    KdpDprintf("\nStack size: %ld\n", Stack->Sp);
 
    for (ul = 0; ul < Stack->Sp; ul++)
    {
        PRPN_OP Op = Stack->Ops + ul;
        switch (Op->Type)
        {
            case RpnOpNop:
                KdpDprintf("NOP,");
                break;
 
            case RpnOpImmediate:
                KdpDprintf("0x%I64x,", Op->Data.Immediate);
                break;
 
            case RpnOpBinaryOperator:
                if (Op->Data.BinaryOperator == RpnBinaryOperatorAdd)
                    KdpDprintf("+,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorSub)
                    KdpDprintf("-,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorMul)
                    KdpDprintf("*,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorDiv)
                    KdpDprintf("/,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorMod)
                    KdpDprintf("%%,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorEquals)
                    KdpDprintf("==,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorNotEquals)
                    KdpDprintf("!=,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorLessThan)
                    KdpDprintf("<,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorLessThanOrEquals)
                    KdpDprintf("<=,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorGreaterThan)
                    KdpDprintf(">,");
                else if (Op->Data.BinaryOperator == RpnBinaryOperatorGreaterThanOrEquals)
                    KdpDprintf(">=,");
                else
                    KdpDprintf("UNKNOWN OP,");
 
                break;
 
            case RpnOpRegister:
                KdpDprintf("%s,", RegisterToTrapFrame[Op->Data.Register].Name);
                break;
 
            case RpnOpDereference:
                KdpDprintf("[%s],",
                    (Op->Data.DerefMemorySize == 1) ? ("byte") :
                    ((Op->Data.DerefMemorySize == 2) ? ("word") :
                    ((Op->Data.DerefMemorySize == 4) ? ("dword") : ("qword"))));
                break;
 
            default:
                KdpDprintf("\nUnsupported Type: %d\n", Op->Type);
                ul = Stack->Sp;
                break;
        }
    }
 
    KdpDprintf("\n");
}
 
static VOID
RpnpClearStack(
    OUT PRPN_STACK Stack)
{
    ASSERT(Stack);
    Stack->Sp = 0;
}
 
static BOOLEAN
RpnpPushStack(
    IN OUT PRPN_STACK Stack,
    IN     PRPN_OP Op)
{
    ASSERT(Stack);
    ASSERT(Op);
 
    if (Stack->Sp >= Stack->Size)
        return FALSE;
 
    memcpy(Stack->Ops + Stack->Sp, Op, sizeof (RPN_OP));
    Stack->Sp++;
 
    return TRUE;
}
 
static BOOLEAN
RpnpPopStack(
    IN OUT PRPN_STACK Stack,
    OUT    PRPN_OP Op  OPTIONAL)
{
    ASSERT(Stack);
 
    if (Stack->Sp == 0)
        return FALSE;
 
    Stack->Sp--;
    if (Op)
        memcpy(Op, Stack->Ops + Stack->Sp, sizeof (RPN_OP));
 
    return TRUE;
}
 
static BOOLEAN
RpnpTopStack(
    IN  PRPN_STACK Stack,
    OUT PRPN_OP Op)
{
    ASSERT(Stack);
    ASSERT(Op);
 
    if (Stack->Sp == 0)
        return FALSE;
 
    memcpy(Op, Stack->Ops + Stack->Sp - 1, sizeof (RPN_OP));
 
    return TRUE;
}
 
static BOOLEAN
RpnpParseExpression(
    IN  PRPN_STACK Stack,
    IN  PCHAR Expression,
    OUT PCHAR *End  OPTIONAL,
    IN  ULONG CharacterOffset,
    OUT PLONG ErrOffset  OPTIONAL,
    OUT PCHAR ErrMsg  OPTIONAL)
{
    PCHAR p = Expression;
    PCHAR pend;
    PCHAR Operator = NULL;
    LONG OperatorOffset = -1;
    RPN_OP RpnOp;
    RPN_OP PoppedOperator;
    BOOLEAN HavePoppedOperator = FALSE;
    RPN_OP ComparativeOp;
    BOOLEAN ComparativeOpFilled = FALSE;
    BOOLEAN IsComparativeOp;
    INT_PTR i, i2;
    ULONG64 ull;
    UCHAR MemorySize;
    CHAR Buffer[16];
    BOOLEAN First;
 
    ASSERT(Stack);
    ASSERT(Expression);
 
    First = TRUE;
    for (;;)
    {
        /* Skip whitespace */
        while (isspace(*p))
        {
            p++;
            CharacterOffset++;
        }
 
        /* Check for end of expression */
        if (p[0] == '\0' || p[0] == ')' || p[0] == ']')
            break;
 
        if (!First)
        {
            /* Remember operator */
            Operator = p++;
            OperatorOffset = CharacterOffset++;
 
            /* Pop operator (to get the right operator precedence) */
            HavePoppedOperator = FALSE;
            if (*Operator == '*' || *Operator == '/' || *Operator == '%')
            {
                if (RpnpTopStack(Stack, &PoppedOperator) &&
                    PoppedOperator.Type == RpnOpBinaryOperator &&
                    (PoppedOperator.Data.BinaryOperator == RpnBinaryOperatorAdd ||
                    PoppedOperator.Data.BinaryOperator == RpnBinaryOperatorSub))
                {
                    RpnpPopStack(Stack, NULL);
                    HavePoppedOperator = TRUE;
                }
                else if (PoppedOperator.Type == RpnOpNop)
                {
                    RpnpPopStack(Stack, NULL);
                    /* Discard the NOP - it was only pushed to indicate there was a
                     * closing brace, so the previous operator shouldn't be popped.
                     */
                }
            }
            else if ((Operator[0] == '=' && Operator[1] == '=') ||
                     (Operator[0] == '!' && Operator[1] == '=') ||
                     Operator[0] == '<' || Operator[0] == '>')
            {
                if (Operator[0] == '=' || Operator[0] == '!' ||
                    (Operator[0] == '<' && Operator[1] == '=') ||
                    (Operator[0] == '>' && Operator[1] == '='))
                {
                    p++;
                    CharacterOffset++;
                }
#if 0
                /* Parse rest of expression */
                if (!RpnpParseExpression(Stack, p + 1, &pend, CharacterOffset + 1,
                                         ErrOffset, ErrMsg))
                {
                    return FALSE;
                }
                else if (pend == p + 1)
                {
                    CONST_STRCPY(ErrMsg, "Expression expected");
 
                    if (ErrOffset)
                        *ErrOffset = CharacterOffset + 1;
 
                    return FALSE;
                }
 
                goto end_of_expression; /* return */
#endif
            }
            else if (Operator[0] != '+' && Operator[0] != '-')
            {
                CONST_STRCPY(ErrMsg, "Operator expected");
 
                if (ErrOffset)
                    *ErrOffset = OperatorOffset;
 
                return FALSE;
            }
 
            /* Skip whitespace */
            while (isspace(*p))
            {
                p++;
                CharacterOffset++;
            }
        }
 
        /* Get operand */
        MemorySize = sizeof(ULONG_PTR); /* default to pointer size */
 
get_operand:
        i = strcspn(p, "+-*/%()[]<>!=");
        if (i > 0)
        {
            i2 = i;
 
            /* Copy register name/memory size */
            while (isspace(p[--i2]));
 
            i2 = min(i2 + 1, (INT)sizeof (Buffer) - 1);
            strncpy(Buffer, p, i2);
            Buffer[i2] = '\0';
 
            /* Memory size prefix */
            if (p[i] == '[')
            {
                if (stricmp(Buffer, "byte") == 0)
                    MemorySize = 1;
                else if (stricmp(Buffer, "word") == 0)
                    MemorySize = 2;
                else if (stricmp(Buffer, "dword") == 0)
                    MemorySize = 4;
                else if (stricmp(Buffer, "qword") == 0)
                    MemorySize = 8;
                else
                {
                    CONST_STRCPY(ErrMsg, "Invalid memory size prefix");
 
                    if (ErrOffset)
                        *ErrOffset = CharacterOffset;
 
                    return FALSE;
                }
 
                p += i;
                CharacterOffset += i;
                goto get_operand;
            }
 
            /* Try to find register */
            for (i = 0; i < RegisterToTrapFrameCount; i++)
            {
                if (stricmp(RegisterToTrapFrame[i].Name, Buffer) == 0)
                    break;
            }
 
            if (i < RegisterToTrapFrameCount)
            {
                RpnOp.Type = RpnOpRegister;
                RpnOp.CharacterOffset = CharacterOffset;
                RpnOp.Data.Register = i;
                i = strlen(RegisterToTrapFrame[i].Name);
                CharacterOffset += i;
                p += i;
            }
            else
            {
                /* Immediate value */
                ull = strtoull(p, &pend, 0);
                if (p != pend)
                {
                    RpnOp.Type = RpnOpImmediate;
                    RpnOp.CharacterOffset = CharacterOffset;
                    RpnOp.Data.Immediate = ull;
                    CharacterOffset += pend - p;
                    p = pend;
                }
                else
                {
                    CONST_STRCPY(ErrMsg, "Operand expected");
 
                    if (ErrOffset)
                        *ErrOffset = CharacterOffset;
 
                    return FALSE;
                }
            }
 
            /* Push operand */
            if (!RpnpPushStack(Stack, &RpnOp))
            {
                CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                if (ErrOffset)
                    *ErrOffset = -1;
 
                return FALSE;
            }
        }
        else if (i == 0)
        {
            if (p[0] == '(' || p[0] == '[') /* subexpression */
            {
                if (!RpnpParseExpression(Stack, p + 1, &pend, CharacterOffset + 1,
                                         ErrOffset, ErrMsg))
                {
                    return FALSE;
                }
                else if (pend == p + 1)
                {
                    CONST_STRCPY(ErrMsg, "Expression expected");
 
                    if (ErrOffset)
                        *ErrOffset = CharacterOffset + 1;
 
                    return FALSE;
                }
 
                if (p[0] == '[') /* dereference */
                {
                    ASSERT(MemorySize == 1 || MemorySize == 2 ||
                           MemorySize == 4 || MemorySize == 8);
 
                    if (pend[0] != ']')
                    {
                        CONST_STRCPY(ErrMsg, "']' expected");
 
                        if (ErrOffset)
                            *ErrOffset = CharacterOffset + (pend - p);
 
                        return FALSE;
                    }
 
                    RpnOp.Type = RpnOpDereference;
                    RpnOp.CharacterOffset = CharacterOffset;
                    RpnOp.Data.DerefMemorySize = MemorySize;
 
                    if (!RpnpPushStack(Stack, &RpnOp))
                    {
                        CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                        if (ErrOffset)
                            *ErrOffset = -1;
 
                        return FALSE;
                    }
                }
                else /* p[0] == '(' */
                {
                    if (pend[0] != ')')
                    {
                        CONST_STRCPY(ErrMsg, "')' expected");
 
                        if (ErrOffset)
                            *ErrOffset = CharacterOffset + (pend - p);
 
                        return FALSE;
                    }
                }
 
                /* Push a "nop" to prevent popping of the + operator (which would
                 * result in (10+10)/2 beeing evaluated as 15)
                 */
                RpnOp.Type = RpnOpNop;
                if (!RpnpPushStack(Stack, &RpnOp))
                {
                    CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
 
                /* Skip closing brace/bracket */
                pend++;
 
                CharacterOffset += pend - p;
                p = pend;
            }
            else if (First && p[0] == '-') /* Allow expressions like "- eax" */
            {
                RpnOp.Type = RpnOpImmediate;
                RpnOp.CharacterOffset = CharacterOffset;
                RpnOp.Data.Immediate = 0;
 
                if (!RpnpPushStack(Stack, &RpnOp))
                {
                    CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
            }
            else
            {
                CONST_STRCPY(ErrMsg, "Operand expected");
 
                if (ErrOffset)
                    *ErrOffset = CharacterOffset;
 
                return FALSE;
            }
        }
        else
        {
            CONST_STRCPY(ErrMsg, "strcspn() failed");
 
            if (ErrOffset)
                *ErrOffset = -1;
 
            return FALSE;
        }
 
        if (!First)
        {
            /* Push operator */
            RpnOp.CharacterOffset = OperatorOffset;
            RpnOp.Type = RpnOpBinaryOperator;
            IsComparativeOp = FALSE;
 
            switch (*Operator)
            {
                case '+':
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorAdd;
                    break;
 
                case '-':
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorSub;
                    break;
 
                case '*':
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorMul;
                    break;
 
                case '/':
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorDiv;
                    break;
 
                case '%':
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorMod;
                    break;
 
                case '=':
                    ASSERT(Operator[1] == '=');
                    IsComparativeOp = TRUE;
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorEquals;
                    break;
 
                case '!':
                    ASSERT(Operator[1] == '=');
                    IsComparativeOp = TRUE;
                    RpnOp.Data.BinaryOperator = RpnBinaryOperatorNotEquals;
                    break;
 
                case '<':
                    IsComparativeOp = TRUE;
 
                    if (Operator[1] == '=')
                        RpnOp.Data.BinaryOperator = RpnBinaryOperatorLessThanOrEquals;
                    else
                        RpnOp.Data.BinaryOperator = RpnBinaryOperatorLessThan;
 
                    break;
 
                case '>':
                    IsComparativeOp = TRUE;
 
                    if (Operator[1] == '=')
                        RpnOp.Data.BinaryOperator = RpnBinaryOperatorGreaterThanOrEquals;
                    else
                        RpnOp.Data.BinaryOperator = RpnBinaryOperatorGreaterThan;
 
                    break;
 
                default:
                    ASSERT(0);
                    break;
            }
 
            if (IsComparativeOp)
            {
                if (ComparativeOpFilled && !RpnpPushStack(Stack, &ComparativeOp))
                {
                    CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
 
                memcpy(&ComparativeOp, &RpnOp, sizeof(RPN_OP));
                ComparativeOpFilled = TRUE;
            }
            else if (!RpnpPushStack(Stack, &RpnOp))
            {
                CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                if (ErrOffset)
                    *ErrOffset = -1;
 
                return FALSE;
            }
 
            /* Push popped operator */
            if (HavePoppedOperator)
            {
                if (!RpnpPushStack(Stack, &PoppedOperator))
                {
                    CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
            }
        }
 
        First = FALSE;
    }
 
//end_of_expression:
 
    if (ComparativeOpFilled && !RpnpPushStack(Stack, &ComparativeOp))
    {
        CONST_STRCPY(ErrMsg, "RPN op stack overflow");
 
        if (ErrOffset)
            *ErrOffset = -1;
 
        return FALSE;
    }
 
    /* Skip whitespace */
    while (isspace(*p))
    {
        p++;
        CharacterOffset++;
    }
 
    if (End)
        *End = p;
 
    return TRUE;
}
 
static BOOLEAN
RpnpEvaluateStack(
    IN  PRPN_STACK Stack,
    IN  PKDB_KTRAP_FRAME TrapFrame,
    OUT PULONGLONG Result,
    OUT PLONG ErrOffset  OPTIONAL,
    OUT PCHAR ErrMsg  OPTIONAL)
{
    ULONGLONG ValueStack[RPN_VALUE_STACK_SIZE];
    ULONG ValueStackPointer = 0;
    ULONG index;
    ULONGLONG ull;
    ULONG ul;
    USHORT us;
    UCHAR uc;
    PVOID p;
    BOOLEAN Ok;
#ifdef DEBUG_RPN
    ULONG ValueStackPointerMax = 0;
#endif
 
    ASSERT(Stack);
    ASSERT(TrapFrame);
    ASSERT(Result);
 
    for (index = 0; index < Stack->Sp; index++)
    {
        PRPN_OP Op = Stack->Ops + index;
 
#ifdef DEBUG_RPN
        ValueStackPointerMax = max(ValueStackPointerMax, ValueStackPointer);
#endif
 
        switch (Op->Type)
        {
            case RpnOpNop:
                /* No operation */
                break;
 
            case RpnOpImmediate:
                if (ValueStackPointer == RPN_VALUE_STACK_SIZE)
                {
                    CONST_STRCPY(ErrMsg, "Value stack overflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
 
                ValueStack[ValueStackPointer++] = Op->Data.Immediate;
                break;
 
            case RpnOpRegister:
                if (ValueStackPointer == RPN_VALUE_STACK_SIZE)
                {
                    CONST_STRCPY(ErrMsg, "Value stack overflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
 
                ul = Op->Data.Register;
                p = (PVOID)((ULONG_PTR)TrapFrame + RegisterToTrapFrame[ul].Offset);
 
                switch (RegisterToTrapFrame[ul].Size)
                {
                    case 1: ull = (ULONGLONG)(*(PUCHAR)p); break;
                    case 2: ull = (ULONGLONG)(*(PUSHORT)p); break;
                    case 4: ull = (ULONGLONG)(*(PULONG)p); break;
                    case 8: ull = (ULONGLONG)(*(PULONGLONG)p); break;
                    default: ASSERT(0); return FALSE; break;
                }
 
                ValueStack[ValueStackPointer++] = ull;
                break;
 
            case RpnOpDereference:
                if (ValueStackPointer < 1)
                {
                    CONST_STRCPY(ErrMsg, "Value stack underflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
 
                /* FIXME: Print a warning when address is out of range */
                p = (PVOID)(ULONG_PTR)ValueStack[ValueStackPointer - 1];
                Ok = FALSE;
 
                switch (Op->Data.DerefMemorySize)
                {
                    case 1:
                        if (NT_SUCCESS(KdbpSafeReadMemory(&uc, p, sizeof (uc))))
                        {
                            Ok = TRUE;
                            ull = (ULONGLONG)uc;
                        }
                        break;
 
                    case 2:
                        if (NT_SUCCESS(KdbpSafeReadMemory(&us, p, sizeof (us))))
                        {
                            Ok = TRUE;
                            ull = (ULONGLONG)us;
                        }
                        break;
 
                    case 4:
                        if (NT_SUCCESS(KdbpSafeReadMemory(&ul, p, sizeof (ul))))
                        {
                            Ok = TRUE;
                            ull = (ULONGLONG)ul;
                        }
                        break;
 
                    case 8:
                        if (NT_SUCCESS(KdbpSafeReadMemory(&ull, p, sizeof (ull))))
                        {
                            Ok = TRUE;
                        }
                        break;
 
                    default:
                        ASSERT(0);
                        return FALSE;
                        break;
                }
 
                if (!Ok)
                {
                    _snprintf(ErrMsg, 128, "Couldn't access memory at 0x%p", p);
 
                    if (ErrOffset)
                        *ErrOffset = Op->CharacterOffset;
 
                    return FALSE;
                }
 
                ValueStack[ValueStackPointer - 1] = ull;
                break;
 
            case RpnOpBinaryOperator:
                if (ValueStackPointer < 2)
                {
                    CONST_STRCPY(ErrMsg, "Value stack underflow");
 
                    if (ErrOffset)
                        *ErrOffset = -1;
 
                    return FALSE;
                }
 
                ValueStackPointer--;
                ull = ValueStack[ValueStackPointer];
 
                if (ull == 0 && Op->Data.BinaryOperator == RpnBinaryOperatorDiv)
                {
                    CONST_STRCPY(ErrMsg, "Division by zero");
 
                    if (ErrOffset)
                        *ErrOffset = Op->CharacterOffset;
 
                    return FALSE;
                }
 
                ull = Op->Data.BinaryOperator(ValueStack[ValueStackPointer - 1], ull);
                ValueStack[ValueStackPointer - 1] = ull;
                break;
 
            default:
                ASSERT(0);
                return FALSE;
        }
    }
 
#ifdef DEBUG_RPN
    DPRINT1("Max value stack pointer: %d\n", ValueStackPointerMax);
#endif
 
    if (ValueStackPointer != 1)
    {
        CONST_STRCPY(ErrMsg, "Stack not empty after evaluation");
 
        if (ErrOffset)
            *ErrOffset = -1;
 
        return FALSE;
    }
 
    *Result = ValueStack[0];
    return TRUE;
}
 
BOOLEAN
KdbpRpnEvaluateExpression(
    IN  PCHAR Expression,
    IN  PKDB_KTRAP_FRAME TrapFrame,
    OUT PULONGLONG Result,
    OUT PLONG ErrOffset  OPTIONAL,
    OUT PCHAR ErrMsg  OPTIONAL)
{
    PRPN_STACK Stack = (PRPN_STACK)&RpnStack;
 
    ASSERT(Expression);
    ASSERT(TrapFrame);
    ASSERT(Result);
 
    /* Clear the stack and parse the expression */
    RpnpClearStack(Stack);
    if (!RpnpParseExpression(Stack, Expression, NULL, 0, ErrOffset, ErrMsg))
        return FALSE;
 
#ifdef DEBUG_RPN
    RpnpDumpStack(Stack);
#endif
 
    /* Evaluate the stack */
    if (!RpnpEvaluateStack(Stack, TrapFrame, Result, ErrOffset, ErrMsg))
        return FALSE;
 
    return TRUE;
}
 
PVOID
KdbpRpnParseExpression(
    IN  PCHAR Expression,
    OUT PLONG ErrOffset  OPTIONAL,
    OUT PCHAR ErrMsg  OPTIONAL)
{
    LONG Size;
    PRPN_STACK Stack = (PRPN_STACK)&RpnStack;
    PRPN_STACK NewStack;
 
    ASSERT(Expression);
 
    /* Clear the stack and parse the expression */
    RpnpClearStack(Stack);
    if (!RpnpParseExpression(Stack, Expression, NULL, 0, ErrOffset, ErrMsg))
        return FALSE;
 
#ifdef DEBUG_RPN
    RpnpDumpStack(Stack);
#endif
 
    /* Duplicate the stack and return a pointer/handle to it */
    ASSERT(Stack->Sp >= 1);
    Size = sizeof (RPN_STACK) + (RTL_FIELD_SIZE(RPN_STACK, Ops[0]) * (Stack->Sp - 1));
    NewStack = ExAllocatePoolWithTag(NonPagedPool, Size, TAG_KDBG);
 
    if (!NewStack)
    {
        CONST_STRCPY(ErrMsg, "Out of memory");
 
        if (ErrOffset)
            *ErrOffset = -1;
 
        return NULL;
    }
 
    memcpy(NewStack, Stack, Size);
    NewStack->Size = NewStack->Sp;
 
    return NewStack;
}
 
BOOLEAN
KdbpRpnEvaluateParsedExpression(
    IN  PVOID Expression,
    IN  PKDB_KTRAP_FRAME TrapFrame,
    OUT PULONGLONG Result,
    OUT PLONG ErrOffset  OPTIONAL,
    OUT PCHAR ErrMsg  OPTIONAL)
{
    PRPN_STACK Stack = (PRPN_STACK)Expression;
 
    ASSERT(Expression);
    ASSERT(TrapFrame);
    ASSERT(Result);
 
    /* Evaluate the stack */
    return RpnpEvaluateStack(Stack, TrapFrame, Result, ErrOffset, ErrMsg);
}