/*++

Copyright (c) 1993  Microsoft Corporation

Module Name:

    walkx86.c

Abstract:

    This file implements the Intel x86 stack walking api.  This api allows for
    the presence of "real mode" stack frames.  This means that you can trace
    into WOW code.

Author:

    Wesley Witt (wesw) 1-Oct-1993

Environment:

    User Mode

--*/

#define TARGET_i386
#define _IMAGEHLP_SOURCE_
#include "walk.h"
#include "i386.h"


#define SAVE_EBP(f)        f->Reserved[0]
#define TRAP_TSS(f)        f->Reserved[1]
#define TRAP_EDITED(f)     f->Reserved[1]
#define SAVE_STDCALL(f)    f->Reserved[1]
#define SAVE_TRAP(f)       f->Reserved[2]

#define STACK_SIZE         (sizeof(DWORD))
#define FRAME_SIZE         (STACK_SIZE * 2)

#define MAX_STACK_SEARCH   16   // in STACK_SIZE units

#define DoMemoryRead(addr,buf,sz,br) \
    ReadMemoryInternal( hProcess, hThread, addr, buf, sz, \
                        br, ReadMemory, TranslateAddress )

#define ReadControlSpace(hProcess,Address,Buffer,Size) \
    ReadMemory( hProcess, (PVOID)Address, Buffer, Size, (LPDWORD)-1 )

#define  SELECTOR_CACHE_LENGTH          6

typedef struct _sc {
        struct _sc            *nextYoungest;
        struct _sc            *nextOldest;
        USHORT                 processor;
        DESCRIPTOR_TABLE_ENTRY desc;
} SELCACHEENTRY;

BOOL fSelCacheInitialized;
SELCACHEENTRY SelectorCache[SELECTOR_CACHE_LENGTH], *selYoungest, *selOldest;


BOOL
WalkX86Init(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    );

BOOL
WalkX86Next(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    );

BOOL
ReadMemoryInternal(
    HANDLE                          hProcess,
    HANDLE                          hThread,
    LPADDRESS                       lpBaseAddress,
    LPVOID                          lpBuffer,
    DWORD                           nSize,
    LPDWORD                         lpNumberOfBytesRead,
    PREAD_PROCESS_MEMORY_ROUTINE    ReadMemory,
    PTRANSLATE_ADDRESS_ROUTINE      TranslateAddress
    );

BOOL
IsFarCall(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    BOOL                              *Ok,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    );

DWORD
ScanForReturnAddress(
    HANDLE                          hProcess,
    LPDWORD                         pdwStackAddr,
    PREAD_PROCESS_MEMORY_ROUTINE    ReadMemory,
    PGET_MODULE_BASE_ROUTINE        GetModuleBase
    );




BOOL
WalkX86(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      StackFrame,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    BOOL rval;

    if (StackFrame->Virtual) {

        rval = WalkX86Next( hProcess,
                                        hThread,
                                        StackFrame,
                                        ContextRecord,
                                        ReadMemory,
                                        FunctionTableAccess,
                                        GetModuleBase,
                                        TranslateAddress
                                      );

    } else {

        rval = WalkX86Init( hProcess,
                                        hThread,
                                        StackFrame,
                                        ContextRecord,
                                        ReadMemory,
                                        FunctionTableAccess,
                                        GetModuleBase,
                                        TranslateAddress
                                      );

    }

    return rval;
}

BOOL
ReadMemoryInternal(
    HANDLE                          hProcess,
    HANDLE                          hThread,
    LPADDRESS                       lpBaseAddress,
    LPVOID                          lpBuffer,
    DWORD                           nSize,
    LPDWORD                         lpNumberOfBytesRead,
    PREAD_PROCESS_MEMORY_ROUTINE    ReadMemory,
    PTRANSLATE_ADDRESS_ROUTINE      TranslateAddress
    )
{
    ADDRESS addr;

    addr = *lpBaseAddress;
    if (addr.Mode != AddrModeFlat) {
        TranslateAddress( hProcess, hThread, &addr );
    }
    return ReadMemory( hProcess, (LPVOID)addr.Offset, lpBuffer,
                       nSize, lpNumberOfBytesRead );
}

DWORD
ScanForReturnAddress(
    HANDLE                            hProcess,
    LPDWORD                           pdwStackAddr,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase
    )
{
    DWORD       stack[MAX_STACK_SEARCH];
    DWORD       i, sw;

    sw = MAX_STACK_SEARCH * STACK_SIZE;
    if(!ReadMemory(hProcess, (LPVOID)*pdwStackAddr, (LPVOID)stack, sw, &sw)) {
        sw = 0xFFF - (*pdwStackAddr & 0xFFF);
        if(!ReadMemory(hProcess, (LPVOID)*pdwStackAddr, (LPVOID)stack, sw, &sw)) {
            return 0;
        }
    }

    //
    // scan thru the stack looking for a return address
    //
    for (i=0; i<sw/STACK_SIZE; i++) {
        if (GetModuleBase(hProcess, stack[i])) {
            *pdwStackAddr += (i * STACK_SIZE);
            return stack[i];
        }
    }

    return 0;
}

BOOL
ReadTrapFrame(
    HANDLE                            hProcess,
    DWORD                             TrapFrameAddress,
    PKTRAP_FRAME                      TrapFrame,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory
    )
{
    DWORD          cb;

    if (!ReadMemory(hProcess,
                    (LPVOID)TrapFrameAddress,
                    TrapFrame,
                    sizeof(*TrapFrame),
                    &cb)) {
        return FALSE;
    }

    if (cb < sizeof(*TrapFrame)) {
        if (cb < sizeof(*TrapFrame) - 20) {
            //
            // shorter then the smallest possible frame type
            //
            return FALSE;
        }

        if ((TrapFrame->SegCs & 1) &&  cb < sizeof(*TrapFrame) - 16 ) {
            //
            // too small for inter-ring frame
            //
            return FALSE;
        }

        if (TrapFrame->EFlags & EFLAGS_V86_MASK) {
            //
            // too small for V86 frame
            //
            return FALSE;
        }
    }

    return TRUE;
}

VOID
InitSelCache(
    VOID
    )
{
    INT i;

    for(i=0;i<SELECTOR_CACHE_LENGTH;i++){
            SelectorCache[i].nextYoungest = &SelectorCache[i+1];
            SelectorCache[i].nextOldest   = &SelectorCache[i-1];
            SelectorCache[i].processor    = (USHORT) -1;
            SelectorCache[i].desc.Selector = 0;
    }

    SelectorCache[--i].nextYoungest = NULL;
    SelectorCache[0].nextOldest     = NULL;
    selYoungest = &SelectorCache[i];
    selOldest   = &SelectorCache[0];
    fSelCacheInitialized = TRUE;
}

BOOLEAN
FindSelector(
    USHORT                   Processor,
    PDESCRIPTOR_TABLE_ENTRY  pdesc
    )
{
    INT i;

    for(i=0;i<SELECTOR_CACHE_LENGTH;i++)
        if (SelectorCache[i].desc.Selector == pdesc->Selector &&
            SelectorCache[i].processor == Processor) {
                *pdesc = SelectorCache[i].desc;
                return TRUE;
        }
    return FALSE;
}

VOID
PutSelector(
    USHORT                   Processor,
    PDESCRIPTOR_TABLE_ENTRY  pdesc
    )
{
    selOldest->desc = *pdesc;
    selOldest->processor = Processor;
    (selOldest->nextYoungest)->nextOldest = NULL;
    selOldest->nextOldest    = selYoungest;
    selYoungest->nextYoungest= selOldest;
    selYoungest = selOldest;
    selOldest   = selOldest->nextYoungest;
}

BOOL
LookupSelector(
    HANDLE                            hProcess,
    USHORT                            Processor,
    PDESCRIPTOR_TABLE_ENTRY           pDescriptorTableEntry,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory
    )
{
    ULONG       Address;
    PVOID       TableBase;
    USHORT      TableLimit;
    ULONG       Index;
    LDT_ENTRY   Descriptor;
    ULONG       bytesread;



    if (!fSelCacheInitialized) {
        InitSelCache();
    }

    if (FindSelector(Processor, pDescriptorTableEntry)) {
        return TRUE;
    }

    //
    // Fetch the address and limit of the GDT
    //
    Address = (ULONG)&(((PKPROCESSOR_STATE)0)->SpecialRegisters.Gdtr.Base);
    ReadControlSpace( hProcess, (PVOID)Address, &TableBase, sizeof(TableBase) );
    Address = (ULONG)&(((PKPROCESSOR_STATE)0)->SpecialRegisters.Gdtr.Limit);
    ReadControlSpace( hProcess, (PVOID)Address, &TableLimit, sizeof(TableLimit) );

    //
    // Find out whether this is a GDT or LDT selector
    //
    if (pDescriptorTableEntry->Selector & 0x4) {

        //
        // This is an LDT selector, so we reload the TableBase and TableLimit
        // with the LDT's Base & Limit by loading the descriptor for the
        // LDT selector.
        //

        if (!ReadMemory(hProcess,
                        (PUCHAR)TableBase+KGDT_LDT,
                        &Descriptor,
                        sizeof(Descriptor),
                        &bytesread)) {
            return FALSE;
        }

        TableBase = (PVOID)((ULONG)Descriptor.BaseLow +
                    ((ULONG)Descriptor.HighWord.Bits.BaseMid << 16) +
                    ((ULONG)Descriptor.HighWord.Bytes.BaseHi << 24));

        TableLimit = Descriptor.LimitLow;  // LDT can't be > 64k

        if(Descriptor.HighWord.Bits.Granularity == GRAN_PAGE) {

            //
            //  I suppose it's possible, although silly, to have an
            //  LDT with page granularity.
            //
            TableLimit <<= PAGE_SHIFT;
        }
    }

    Index = (USHORT)(pDescriptorTableEntry->Selector) & ~0x7;
                                                    // Irrelevant bits
    //
    // Check to make sure that the selector is within the table bounds
    //
    if (Index >= TableLimit) {

        //
        // Selector is out of table's bounds
        //

        return FALSE;
    }

    if (!ReadMemory(hProcess,
                    (PUCHAR)TableBase+Index,
                    &(pDescriptorTableEntry->Descriptor),
                    sizeof(pDescriptorTableEntry->Descriptor),
                    &bytesread)) {
        return FALSE;
    }

    PutSelector(Processor, pDescriptorTableEntry);
    return TRUE;
}

BOOL
TaskGate2TrapFrame(
    HANDLE                            hProcess,
    USHORT                            TaskRegister,
    PKTRAP_FRAME                      TrapFrame,
    PULONG                            off,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory
    )
{
    DESCRIPTOR_TABLE_ENTRY   desc;
    ULONG                    bytesread;
    struct  {
        ULONG   r1[8];
        ULONG   Eip;
        ULONG   EFlags;
        ULONG   Eax;
        ULONG   Ecx;
        ULONG   Edx;
        ULONG   Ebx;
        ULONG   Esp;
        ULONG   Ebp;
        ULONG   Esi;
        ULONG   Edi;
        ULONG   Es;
        ULONG   Cs;
        ULONG   Ss;
        ULONG   Ds;
        ULONG   Fs;
        ULONG   Gs;
    } TaskState;


    //
    // Lookup task register
    //

    desc.Selector = TaskRegister;
    if (!LookupSelector(hProcess, 0, &desc, ReadMemory)) {
        return FALSE;
    }

    if (desc.Descriptor.HighWord.Bits.Type != 9  &&
        desc.Descriptor.HighWord.Bits.Type != 0xb) {
        //
        // not a 32bit task descriptor
        //
        return FALSE;
    }

    //
    // Read in Task State Segment
    //

    *off = ((ULONG)desc.Descriptor.BaseLow +
           ((ULONG)desc.Descriptor.HighWord.Bytes.BaseMid << 16) +
           ((ULONG)desc.Descriptor.HighWord.Bytes.BaseHi  << 24) );

    if (!ReadMemory(hProcess,
                    (LPVOID)*off,
                    &TaskState,
                    sizeof(TaskState),
                    &bytesread)) {
        return FALSE;
    }

    //
    // Move fields from Task State Segment to TrapFrame
    //

    ZeroMemory( TrapFrame, sizeof(*TrapFrame) );

    TrapFrame->Eip    = TaskState.Eip;
    TrapFrame->EFlags = TaskState.EFlags;
    TrapFrame->Eax    = TaskState.Eax;
    TrapFrame->Ecx    = TaskState.Ecx;
    TrapFrame->Edx    = TaskState.Edx;
    TrapFrame->Ebx    = TaskState.Ebx;
    TrapFrame->Ebp    = TaskState.Ebp;
    TrapFrame->Esi    = TaskState.Esi;
    TrapFrame->Edi    = TaskState.Edi;
    TrapFrame->SegEs  = TaskState.Es;
    TrapFrame->SegCs  = TaskState.Cs;
    TrapFrame->SegDs  = TaskState.Ds;
    TrapFrame->SegFs  = TaskState.Fs;
    TrapFrame->SegGs  = TaskState.Gs;
    TrapFrame->HardwareEsp = TaskState.Esp;
    TrapFrame->HardwareSegSs = TaskState.Ss;

    return TRUE;
}

BOOL
ProcessTrapFrame(
    HANDLE                            hProcess,
    LPSTACKFRAME                      lpstkfrm,
    PFPO_DATA                         pFpoData,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess
    )
{
    KTRAP_FRAME    TrapFrame;
    DWORD          StackAddr;


    if (((PFPO_DATA)lpstkfrm->FuncTableEntry)->cbFrame == FRAME_TSS) {
        StackAddr = SAVE_TRAP(lpstkfrm);
        TaskGate2TrapFrame( hProcess, KGDT_TSS, &TrapFrame, &StackAddr, ReadMemory );
    } else {
        if (!ReadTrapFrame( hProcess,
                            SAVE_TRAP(lpstkfrm),
                            &TrapFrame,
                            ReadMemory)) {
            SAVE_TRAP(lpstkfrm) = 0;
            return FALSE;
        }
    }

    SAVE_TRAP(lpstkfrm) = 0;

    if (pFpoData) {
        if (((TrapFrame.SegCs & MODE_MASK) != KernelMode) ||
            (TrapFrame.EFlags & EFLAGS_V86_MASK)) {
            //
            // User-mode frame, real value of Esp is in HardwareEsp
            //
            lpstkfrm->AddrFrame.Offset = TrapFrame.HardwareEsp - STACK_SIZE;
        }
        else {
            //
            // We ignore if Esp has been edited for now, and we will print a
            // separate line indicating this later.
            //
            // Calculate kernel Esp
            //

            if (((PFPO_DATA)lpstkfrm->FuncTableEntry)->cbFrame == FRAME_TRAP) {
                //
                // plan trap frame
                //
                if ((TrapFrame.SegCs & FRAME_EDITED) == 0) {
                    lpstkfrm->AddrFrame.Offset = TrapFrame.TempEsp;
                } else {
                    lpstkfrm->AddrFrame.Offset = (ULONG)
                        (&(((PKTRAP_FRAME)lpstkfrm->AddrFrame.Offset)->HardwareEsp));
                }
            } else {
                //
                // tss converted to trap frame
                //
                lpstkfrm->AddrFrame.Offset = TrapFrame.HardwareEsp;
            }

            lpstkfrm->AddrFrame.Offset += pFpoData->cdwLocals * STACK_SIZE;
            if (pFpoData->cbFrame == FRAME_FPO) {
                lpstkfrm->AddrFrame.Offset += pFpoData->cbRegs * STACK_SIZE - STACK_SIZE;
            }
        }
    }
    else {
        lpstkfrm->AddrFrame.Offset = TrapFrame.Ebp;
    }

    SAVE_EBP(lpstkfrm) = TrapFrame.Ebp;
    lpstkfrm->FuncTableEntry = pFpoData;

    return TRUE;
}

BOOL
IsFarCall(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    BOOL                              *Ok,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    BOOL       fFar = FALSE;
    WORD       wStk[ 3 ];
    DWORD      dwStk[ 3 ];
    int        cb;
    ADDRESS    Addr;

    *Ok = TRUE;

    if (lpstkfrm->AddrFrame.Mode == AddrModeFlat) {
        /*
         * If we are working with 32 bit offset stack pointers, we
         *      will say that the return address if far if the address
         *      treated as a FAR pointer makes any sense,  if not then
         *      it must be a near return
         */

        if (lpstkfrm->AddrFrame.Offset &&
            DoMemoryRead( &lpstkfrm->AddrFrame, dwStk, sizeof(dwStk), &cb )) {
            //
            //  See if segment makes sense
            //

            Addr.Offset   = dwStk[1];
            Addr.Segment  = (WORD)dwStk[2];
            Addr.Mode = AddrModeFlat;

            if (TranslateAddress( hProcess, hThread, &Addr ) && Addr.Offset) {
                fFar = TRUE;
            }
        } else {
            *Ok = FALSE;
        }
    } else {
        /*
         * For 16 bit (i.e. windows WOW code) we do the following tests
         *      to check to see if an address is a far return value.
         *
         *      1.  if the saved BP register is odd then it is a far
         *              return values
         *      2.  if the address treated as a far return value makes sense
         *              then it is a far return value
         *      3.  else it is a near return value
         */

        if (lpstkfrm->AddrFrame.Offset &&
            DoMemoryRead( &lpstkfrm->AddrFrame, wStk, 6, &cb )) {

            if ( wStk[0] & 0x0001 ) {
                fFar = TRUE;
            } else {

                //
                //  See if segment makes sense
                //

                Addr.Offset   = dwStk[1];
                Addr.Segment  = (WORD)dwStk[2];
                Addr.Mode = AddrModeFlat;

                if (TranslateAddress( hProcess, hThread, &Addr  ) && Addr.Offset) {
                    fFar = TRUE;
                }
            }
        } else {
            *Ok = FALSE;
        }
    }
    return fFar;
}


BOOL
SetNonOff32FrameAddress(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    BOOL    fFar;
    WORD    Stk[ 3 ];
    int     cb;
    BOOL    Ok;

    fFar = IsFarCall( hProcess, hThread, lpstkfrm, &Ok, ReadMemory, TranslateAddress );

    if (!Ok) {
        return FALSE;
    }

    if (!DoMemoryRead( &lpstkfrm->AddrFrame, Stk, fFar ? 6 : 4, &cb )) {
        return FALSE;
    }

    if (SAVE_EBP(lpstkfrm) > 0) {
        lpstkfrm->AddrFrame.Offset = SAVE_EBP(lpstkfrm) & 0xffff;
        lpstkfrm->AddrPC.Offset = Stk[1];
        if (fFar) {
            lpstkfrm->AddrPC.Segment = Stk[2];
        }
        SAVE_EBP(lpstkfrm) = 0;
    } else
    if (Stk[1] == 0) {
        return FALSE;
    } else {
        lpstkfrm->AddrFrame.Offset = Stk[0];
        lpstkfrm->AddrFrame.Offset &= 0xFFFFFFFE;
        lpstkfrm->AddrPC.Offset = Stk[1];
        if (fFar) {
            lpstkfrm->AddrPC.Segment = Stk[2];
        }
    }

    return TRUE;
}

VOID
GetFunctionParameters(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    BOOL                Ok;
    DWORD               cb;
    ADDRESS             ParmsAddr;


    ParmsAddr = lpstkfrm->AddrFrame;

    //
    // calculate the frame size
    //
    if (lpstkfrm->AddrPC.Mode == AddrModeFlat) {

        ParmsAddr.Offset += FRAME_SIZE;

    } else
    if ( IsFarCall( hProcess, hThread, lpstkfrm, &Ok,
                    ReadMemory, TranslateAddress ) ) {

        lpstkfrm->Far = TRUE;
        ParmsAddr.Offset += 6;

    } else {

        lpstkfrm->Far = FALSE;
        ParmsAddr.Offset += STACK_SIZE;

    }

    //
    // read the memory
    //
    if (!DoMemoryRead( &ParmsAddr, lpstkfrm->Params, STACK_SIZE*4, &cb )) {
        lpstkfrm->Params[0] =
        lpstkfrm->Params[1] =
        lpstkfrm->Params[2] =
        lpstkfrm->Params[3] = 0;
    }
}

VOID
GetReturnAddress(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    int                 cb;
    DWORD               stack[2];


    if (SAVE_TRAP(lpstkfrm)) {
        //
        // if a trap frame was encountered then
        // the return address was already calculated
        //
        return;
    }

    if (lpstkfrm->AddrPC.Mode == AddrModeFlat) {

        //
        // read the frame from the process's memory
        //
        if (!DoMemoryRead( &lpstkfrm->AddrFrame, stack, FRAME_SIZE, &cb )) {
            //
            // if we could not read the memory then set
            // the return address to zero so that the stack trace
            // will terminate
            //

            stack[1] = 0;

        }

        lpstkfrm->AddrReturn.Offset = stack[1];

    } else {

        lpstkfrm->AddrReturn.Offset = lpstkfrm->AddrPC.Offset;
        lpstkfrm->AddrReturn.Segment = lpstkfrm->AddrPC.Segment;

    }
}

BOOL
WalkX86FpoFpo(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    PFPO_DATA                         pFpoData,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    KTRAP_FRAME    TrapFrame;
    DWORD          cb;
    ADDRESS        EbpAddr;
    DWORD          StackAddr;



    if (pFpoData->fUseBP) {

        //
        // get the saved ebp register off the stack
        //

        EbpAddr = lpstkfrm->AddrFrame;
        EbpAddr.Offset += (FRAME_SIZE +
              (((PFPO_DATA)lpstkfrm->FuncTableEntry)->cdwParams * STACK_SIZE));

        if (!DoMemoryRead( &EbpAddr, &SAVE_EBP(lpstkfrm), STACK_SIZE, &cb )) {
            return FALSE;
        }

    } else {

        lpstkfrm->AddrFrame.Offset -= STACK_SIZE;

    }

    lpstkfrm->AddrFrame.Offset += FRAME_SIZE;
    lpstkfrm->AddrFrame.Offset += (((PFPO_DATA)lpstkfrm->FuncTableEntry)->cdwParams * STACK_SIZE);
    lpstkfrm->AddrFrame.Offset += (pFpoData->cdwLocals * STACK_SIZE);
    lpstkfrm->AddrFrame.Offset += (pFpoData->cbRegs * STACK_SIZE);

    lpstkfrm->FuncTableEntry = pFpoData;

    if (pFpoData->cbFrame == FRAME_FPO) {

        //
        // this is necessary for 4 reasons:
        //
        //      1) random compiler bugs where regs are saved on the
        //         stack but the fpo data does not account for them
        //
        //      2) inline asm code that does a push
        //
        //      3) any random code that does a push and it isn't
        //         accounted for in the fpo data
        //
        //      4) _cdecl functions
        //
        // this is such a shitty hack but there is no way around it!
        // this can actually return a bad address if there is semi-realistic
        // data on the stack.  the only way to improve it is to unassemble
        // the code and look for a call, but this has even more problems!
        // it also slows the stacktrace down.
        //
        StackAddr = lpstkfrm->AddrFrame.Offset + STACK_SIZE;
        if (ScanForReturnAddress( hProcess, &StackAddr,
                                  ReadMemory, GetModuleBase )) {

            lpstkfrm->AddrFrame.Offset = StackAddr - STACK_SIZE;

        }

    } else if (pFpoData->cbFrame == FRAME_TRAP) {

        if (SAVE_EBP(lpstkfrm) > 0) {
            lpstkfrm->AddrFrame.Offset = SAVE_EBP(lpstkfrm);
            lpstkfrm->AddrFrame.Mode = AddrModeFlat;
            lpstkfrm->AddrFrame.Segment = 0;
            SAVE_EBP(lpstkfrm) = 0;
        }

        SAVE_TRAP(lpstkfrm) = lpstkfrm->AddrFrame.Offset;

        if (!ReadTrapFrame( hProcess, lpstkfrm->AddrFrame.Offset, &TrapFrame, ReadMemory )) {
            return FALSE;
        }

        TRAP_EDITED(lpstkfrm) = TrapFrame.SegCs & FRAME_EDITED;

        lpstkfrm->AddrReturn.Offset = TrapFrame.Eip;
        lpstkfrm->AddrReturn.Mode = AddrModeFlat;
        lpstkfrm->AddrReturn.Segment = 0;

    } else if (pFpoData->cbFrame == FRAME_TSS) {

        SAVE_TRAP(lpstkfrm) = lpstkfrm->AddrFrame.Offset;
        TRAP_TSS(lpstkfrm) = KGDT_TSS;

        StackAddr = lpstkfrm->AddrFrame.Offset;

        TaskGate2TrapFrame( hProcess, KGDT_TSS, &TrapFrame, &StackAddr, ReadMemory );

        lpstkfrm->AddrReturn.Offset = TrapFrame.Eip;
        lpstkfrm->AddrReturn.Mode = AddrModeFlat;
        lpstkfrm->AddrReturn.Segment = 0;

    }

    return TRUE;
}

BOOL
WalkX86FpoNonFpo(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    PFPO_DATA                         pFpoData,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    DWORD       stack[FRAME_SIZE*4];
    DWORD       cb;


    //
    // read the first 2 dwords off the stack
    //
    if (!DoMemoryRead( &lpstkfrm->AddrFrame, stack, FRAME_SIZE, &cb )) {

        return FALSE;

    }

    if (((PFPO_DATA)lpstkfrm->FuncTableEntry)->fUseBP == 1) {

        lpstkfrm->AddrFrame.Offset = SAVE_EBP(lpstkfrm);
        SAVE_EBP(lpstkfrm) = 0;

    }
    else if (SAVE_EBP(lpstkfrm)) {

        lpstkfrm->AddrFrame.Offset = SAVE_EBP(lpstkfrm);
        SAVE_EBP(lpstkfrm) = 0;

    } else {

        lpstkfrm->AddrFrame.Offset = stack[0];

    }

    lpstkfrm->FuncTableEntry = NULL;

    return TRUE;
}

BOOL
WalkX86NonFpoFpo(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    PFPO_DATA                         pFpoData,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    DWORD          stack[FRAME_SIZE*4];
    DWORD          cb;
    KTRAP_FRAME    TrapFrame;
    ADDRESS        EbpAddr;
    DWORD          StackAddr;



    //
    // read the first 2 dwords off the stack
    //
    if (!DoMemoryRead( &lpstkfrm->AddrFrame, stack, FRAME_SIZE, &cb )) {

        return FALSE;

    }

    SAVE_EBP(lpstkfrm) = stack[0];

    if (pFpoData->fUseBP == 1) {

        //
        // get the saved ebp register off the stack
        //

        EbpAddr = lpstkfrm->AddrFrame;
        EbpAddr.Offset += (FRAME_SIZE + SAVE_STDCALL(lpstkfrm));

        if (!DoMemoryRead( &EbpAddr, &SAVE_EBP(lpstkfrm), STACK_SIZE, &cb )) {

            return FALSE;

        }

    } else if (pFpoData->cbFrame == FRAME_FPO) {

        lpstkfrm->AddrFrame.Offset -= STACK_SIZE;

    }

    //
    // update the frame pointer to the next frame
    //
    lpstkfrm->AddrFrame.Offset += ((pFpoData->cdwLocals * STACK_SIZE) +
                                   (pFpoData->cbRegs * STACK_SIZE)    +
                                   SAVE_STDCALL(lpstkfrm) + FRAME_SIZE);

    SAVE_STDCALL(lpstkfrm) = 0;

    if (pFpoData->cbFrame == FRAME_FPO) {
        //
        // this is necessary for 4 reasons:
        //
        //      1) random compiler bugs where regs are saved on the
        //         stack but the fpo data does not account for them
        //
        //      2) inline asm code that does a push
        //
        //      3) any random code that does a push and it isn't
        //         accounted for in the fpo data
        //
        //      4) _cdecl functions
        //
        // this is such a shitty hack but there is no way around it!
        // this can actually return a bad address if there is semi-realistic
        // data on the stack.  the only way to improve it is to unassemble
        // the code and look for a call, but this has even more problems!
        // it also slows the stacktrace down.
        //
        StackAddr = lpstkfrm->AddrFrame.Offset + STACK_SIZE;
        if (ScanForReturnAddress( hProcess, &StackAddr,
                                  ReadMemory, GetModuleBase )) {

            lpstkfrm->AddrFrame.Offset = StackAddr - STACK_SIZE;

        }
    }

    if (pFpoData->cbFrame == FRAME_TRAP) {

        //
        // read a kernel mode trap frame from the stack
        //

        SAVE_TRAP(lpstkfrm) = lpstkfrm->AddrFrame.Offset;

        if (!ReadTrapFrame( hProcess, lpstkfrm->AddrFrame.Offset,
                            &TrapFrame, ReadMemory )) {
            return FALSE;
        }

        TRAP_EDITED(lpstkfrm) = TrapFrame.SegCs & FRAME_EDITED;

        if (!DoMemoryRead( &lpstkfrm->AddrFrame, stack, FRAME_SIZE, &cb )) {

            return FALSE;

        }

        lpstkfrm->AddrReturn.Offset = TrapFrame.Eip;
        lpstkfrm->AddrReturn.Mode = AddrModeFlat;
        lpstkfrm->AddrReturn.Segment = 0;

    } else if (pFpoData->cbFrame == FRAME_TSS) {

        TRAP_TSS(lpstkfrm) = KGDT_TSS;
        SAVE_TRAP(lpstkfrm) = lpstkfrm->AddrFrame.Offset;

        StackAddr = lpstkfrm->AddrFrame.Offset;

        TaskGate2TrapFrame( hProcess, KGDT_TSS, &TrapFrame, &StackAddr, ReadMemory );

        lpstkfrm->AddrReturn.Offset = TrapFrame.Eip;
        lpstkfrm->AddrReturn.Mode = AddrModeFlat;
        lpstkfrm->AddrReturn.Segment = 0;

    }

    lpstkfrm->FuncTableEntry = pFpoData;

    return TRUE;
}

BOOL
WalkX86NonFpoNonFpo(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    PFPO_DATA                         pFpoData,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    DWORD       stack[FRAME_SIZE*4];
    DWORD       cb;

    //
    // read the first 2 dwords off the stack
    //
    if (!DoMemoryRead( &lpstkfrm->AddrFrame, stack, FRAME_SIZE, &cb )) {
        return FALSE;
    }

    //
    // a previous function in the call stack was a fpo function that used ebp as
    // a general purpose register.  ul contains the ebp value that was good  before
    // that function executed.  it is that ebp that we want, not what was just read
    // from the stack.  what was just read from the stack is totally bogus.
    //
    if (SAVE_EBP(lpstkfrm)) {

        stack[0] = SAVE_EBP(lpstkfrm);
        SAVE_EBP(lpstkfrm) = 0;

    }

    lpstkfrm->AddrFrame.Offset = stack[0];

    lpstkfrm->FuncTableEntry = NULL;

    return TRUE;
}

BOOL
WalkX86Next(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    PFPO_DATA      pFpoData = NULL;
    BOOL           rVal = TRUE;


    //
    // the previous frame's return address is this frame's pc
    //
    lpstkfrm->AddrPC = lpstkfrm->AddrReturn;

    if (lpstkfrm->AddrPC.Mode != AddrModeFlat) {
        SetNonOff32FrameAddress( hProcess,
                                 hThread,
                                 lpstkfrm,
                                 ReadMemory,
                                 FunctionTableAccess,
                                 GetModuleBase,
                                 TranslateAddress
                               );
        goto exit;
    }

    //
    // check to see if the current frame is an fpo frame
    //
    if (lpstkfrm->AddrPC.Mode == AddrModeFlat) {
        if ((!GetModuleBase(hProcess, lpstkfrm->AddrReturn.Offset)) ||
            (!GetModuleBase(hProcess, lpstkfrm->AddrPC.Offset))) {
            return FALSE;
        }
        pFpoData = FunctionTableAccess(hProcess, lpstkfrm->AddrPC.Offset);
    }

    if (pFpoData && pFpoData->ulOffStart == 0xffffffff) {
        //
        // the function is not and fpo function but a stdcall
        // function.  in this case the cdwParams is set to the
        // parameters size
        //
        SAVE_STDCALL(lpstkfrm) = pFpoData->cdwParams;
        pFpoData = NULL;
    }

    //
    // if there is a trap frame then handle it
    //
    if (SAVE_TRAP(lpstkfrm)) {
        if (!ProcessTrapFrame( hProcess, lpstkfrm, pFpoData,
                               ReadMemory, FunctionTableAccess )) {
            return FALSE;
        }
    } else if (pFpoData) {
        if (lpstkfrm->FuncTableEntry) {

            rVal = WalkX86FpoFpo( hProcess,
                                  hThread,
                                  pFpoData,
                                  lpstkfrm,
                                  ContextRecord,
                                  ReadMemory,
                                  FunctionTableAccess,
                                  GetModuleBase,
                                  TranslateAddress
                                );

        } else {

            rVal = WalkX86NonFpoFpo( hProcess,
                                     hThread,
                                     pFpoData,
                                     lpstkfrm,
                                     ContextRecord,
                                     ReadMemory,
                                     FunctionTableAccess,
                                     GetModuleBase,
                                     TranslateAddress
                                   );

        }
    } else {
        if (lpstkfrm->FuncTableEntry) {

            rVal = WalkX86FpoNonFpo( hProcess,
                                     hThread,
                                     pFpoData,
                                     lpstkfrm,
                                     ContextRecord,
                                     ReadMemory,
                                     FunctionTableAccess,
                                     GetModuleBase,
                                     TranslateAddress
                                   );

        } else {

            rVal = WalkX86NonFpoNonFpo( hProcess,
                                        hThread,
                                        pFpoData,
                                        lpstkfrm,
                                        ContextRecord,
                                        ReadMemory,
                                        FunctionTableAccess,
                                        GetModuleBase,
                                        TranslateAddress
                                      );

        }
    }

exit:
    lpstkfrm->AddrFrame.Mode = lpstkfrm->AddrPC.Mode;
    lpstkfrm->AddrReturn.Mode = lpstkfrm->AddrPC.Mode;

    GetFunctionParameters( hProcess, hThread, lpstkfrm,
                           ReadMemory, GetModuleBase, TranslateAddress );

    GetReturnAddress( hProcess, hThread, lpstkfrm,
                      ReadMemory, GetModuleBase, TranslateAddress );

    return rVal;
}

BOOL
WalkX86Init(
    HANDLE                            hProcess,
    HANDLE                            hThread,
    LPSTACKFRAME                      lpstkfrm,
    PCONTEXT                          ContextRecord,
    PREAD_PROCESS_MEMORY_ROUTINE      ReadMemory,
    PFUNCTION_TABLE_ACCESS_ROUTINE    FunctionTableAccess,
    PGET_MODULE_BASE_ROUTINE          GetModuleBase,
    PTRANSLATE_ADDRESS_ROUTINE        TranslateAddress
    )
{
    UCHAR               code[3];
    PFPO_DATA           pFpoData = NULL;
    int                 cb;
    DWORD               dwModuleBase;


    lpstkfrm->Virtual = TRUE;
    lpstkfrm->Reserved[0] =
    lpstkfrm->Reserved[1] =
    lpstkfrm->Reserved[2] = 0;
    lpstkfrm->AddrReturn = lpstkfrm->AddrPC;

    if (lpstkfrm->AddrPC.Mode == AddrModeFlat) {
        pFpoData = FunctionTableAccess(hProcess, lpstkfrm->AddrPC.Offset);
    } else {
        goto exit;
    }

    if (pFpoData && pFpoData->ulOffStart == 0xffffffff) {
        //
        // the function is not and fpo function but a stdcall
        // function.  in this case the cdwParams is set to the
        // parameters size
        //
        SAVE_STDCALL(lpstkfrm) = pFpoData->cdwParams;
        pFpoData = NULL;
    }

    lpstkfrm->FuncTableEntry = pFpoData;

    if (pFpoData) {
        dwModuleBase = GetModuleBase( hProcess, lpstkfrm->AddrPC.Offset );
        if (!dwModuleBase) {
            return FALSE;
        }

        if (lpstkfrm->AddrPC.Offset == dwModuleBase+pFpoData->ulOffStart) {
            //
            // first byte of code
            //
            SAVE_EBP(lpstkfrm) = lpstkfrm->AddrFrame.Offset;
            lpstkfrm->AddrFrame.Offset = lpstkfrm->AddrStack.Offset - STACK_SIZE;
        } else {
            //
            // somewhere in the body
            //
            SAVE_EBP(lpstkfrm) = lpstkfrm->AddrFrame.Offset;
            lpstkfrm->AddrFrame.Offset = lpstkfrm->AddrStack.Offset +
                                         (pFpoData->cdwLocals * STACK_SIZE);
            if (pFpoData->fUseBP) {
                //
                // the last item pushed onto the stack was EBP
                //
                if (!DoMemoryRead( &lpstkfrm->AddrStack, &SAVE_EBP(lpstkfrm),
                                   STACK_SIZE, &cb )) {
                    SAVE_EBP(lpstkfrm) = 0;
                }
            } else {
                lpstkfrm->AddrFrame.Offset -= STACK_SIZE;
            }
            if (pFpoData->cbFrame == FRAME_FPO) {
                lpstkfrm->AddrFrame.Offset += (pFpoData->cbRegs * STACK_SIZE);
            }
        }
    } else {
        //
        // this code determines whether eip is in the function prolog
        //
        if (!DoMemoryRead( &lpstkfrm->AddrPC, code, 3, &cb )) {
            //
            // assume a call to a bad address if the memory read fails
            //
            code[0] = 0x55;
        }
        if ((code[0] == 0x55) || (code[0] == 0x8b && code[1] == 0xec)) {
            lpstkfrm->AddrFrame.Offset = lpstkfrm->AddrStack.Offset;
            if (!lpstkfrm->AddrPC.Mode == AddrModeFlat) {
                lpstkfrm->AddrFrame.Offset &= 0xffff;
            }
            if (code[0] == 0x55) {
                lpstkfrm->AddrFrame.Offset -= (lpstkfrm->AddrPC.Mode == AddrModeFlat) ? FRAME_SIZE : 2;
            } else {
                SAVE_EBP(lpstkfrm) = 0;
            }
        } else {
            SAVE_EBP(lpstkfrm) = 0;
            if (!lpstkfrm->AddrPC.Mode == AddrModeFlat) {
                lpstkfrm->AddrFrame.Offset &= 0x0000FFFF;
            }
        }

    }

exit:
    lpstkfrm->AddrFrame.Mode = lpstkfrm->AddrPC.Mode;

    GetFunctionParameters( hProcess, hThread, lpstkfrm,
                           ReadMemory, GetModuleBase, TranslateAddress );

    GetReturnAddress( hProcess, hThread, lpstkfrm,
                      ReadMemory, GetModuleBase, TranslateAddress );

    return TRUE;
}
