flat assembler
Message board for the users of flat assembler.

Index > Examples and Tutorials > rather simple example of red-black trees

Author
Thread Post new topic Reply to topic
tthsqe



Joined: 20 May 2009
Posts: 721
tthsqe
Code:
format PE64 GUI 4.0
entry Start

include 'win64axp.inc'

TT_MAX_ENTRIES     fix 1024


IDI_MAIN        = 17
ID_DLGMAIN      = 37
ID_EXPRESSION   = 39
ID_RESULT       = 200


struct NODE    ; 32 bytes in size
  LEFT   dq ?      ; left child
  RIGHT  dq ?      ; right child
  UP     dq ?      ; parent
  COL    db ?      ; 0 for black, 1 for red   \
         db ?,?,?  ; unused
  NUM    dd ?      ; number
ends

LG_NODE_SIZE fix 5  ; log2(sizeof.NODE)


section '.text' code readable executable



Start:
                       push  rbp
                     invoke  InitCommonControls
                     invoke  GetModuleHandle,NULL
                     invoke  DialogBoxParam,rax,ID_DLGMAIN,NULL,DlgProc,NULL
                     invoke  ExitProcess,0

proc DlgProc,.hDlg,.uMsg,.wParam,.lParam
                        mov  [.hDlg],rcx
                        mov  [.uMsg],rdx
                        mov  [.wParam],r8
                        mov  [.lParam],r9
                        mov  eax,dword[.uMsg]
                        cmp  eax,WM_COMMAND
                         je  .wmcommand
                        cmp  eax,WM_CLOSE
                         je  .wmclose
                        cmp  eax,WM_INITDIALOG
                         je  .wminitdialog
 .default:
                        xor  eax, eax
                        ret
 .wmcommand:
                      movzx  edx,word[.wParam+2]
                      movzx  eax,word[.wParam]
                        cmp  eax,ID_EXPRESSION
                        jne  .default
                        cmp  edx, EN_CHANGE
                        jne  .default
 .edit_changed:
                      invoke  SendDlgItemMessage,[.hDlg],ID_EXPRESSION,WM_GETTEXT,1023,InputString

                       push  rsi rdi
                       call  TT_Clear
                        lea  rsi,[InputString]
       .read_next:     call  SkipSpaces
                        cmp  byte[rsi],0
                         je  .read_done
                       call  ParseInteger
                        mov  ecx,eax
                       call  TT_FindNode
                        jmp  .read_next
       .read_done:      lea  rdi,[ResultString]
                       call  TT_InOrderTraverse
                        xor  eax,eax
                      stosb
                        pop  rdi rsi

                     invoke  SetDlgItemText,[.hDlg],ID_RESULT,ResultString
                        jmp  .default
 .wmclose:
                      invoke  EndDialog,[.hDlg],0
                         jmp  .default
 .wminitdialog:
                      invoke  SendDlgItemMessage,[.hDlg],ID_EXPRESSION,EM_LIMITTEXT,1022,0
 .processed:
                         mov  eax,1
 .return:
                         ret
endp








                ; return in rax address of node that corresponds to number in ecx
                ; if ecx is not in table, then a new node is made
                ; if table is full, then TTNull is returned
                ; NOTE: insertion code is stolen from wikipedia

                      align  16
TT_FindNode:
                        mov  edx,dword[TTEntries]
                       test  edx,edx
                        jnz  .OldTree

.NewTree:               lea  rax,[TT]
                        add  edx,1
                        mov  dword[TTEntries],edx
                        mov  qword[rax+NODE.UP],TTHead
                        mov  qword[rax+NODE.LEFT],TTNull
                        mov  qword[rax+NODE.RIGHT],TTNull
                        mov  dword[rax+NODE.COL],0
                        mov  dword[rax+NODE.NUM],ecx
                        mov  qword[TTHead+NODE.LEFT],rax
                        ret


                      align  16

.TreeFull:              lea  rax,[TTNull]
                        ret



               ; this can be called to skip the previous branch if it is known that the tree is not empty

                      align  16
.OldTree:
                        mov  r10,qword[TTHead+NODE.LEFT]
                        mov  edx,dword[TTEntries]

                        lea  r11d,[rdx+1]
                        shl  rdx,LG_NODE_SIZE
                        lea  rdx,[rdx+TT]
 .Compare:
                        mov  r8,qword[r10+NODE.LEFT]
                        mov  r9,qword[r10+NODE.RIGHT]
                        mov  eax,dword[r10+NODE.NUM]
                        cmp  eax,ecx
                         jg  .GoLeft
                         jl  .GoRight

 .Found:                mov  rax,r10
                        ret

 .GoLeft:               cmp  r8,TTNull
                         je  .MakeNewLeft
                        mov  r10,r8
                        jmp  .Compare

 .GoRight:              cmp  r9,TTNull
                         je  .MakeNewRight
                        mov  r10,r9
                        jmp  .Compare

.MakeNewLeft:           cmp  r11d,TT_MAX_ENTRIES
                         ja  .TreeFull
                        mov  qword[r10+NODE.LEFT],rdx
                        jmp  .FixTree

.MakeNewRight:          cmp  r11d,TT_MAX_ENTRIES
                         ja  .TreeFull
                        mov  qword[r10+NODE.RIGHT],rdx


.FixTree:               mov  dword[TTEntries],r11d
                        mov  qword[rdx+NODE.UP],r10
                        mov  qword[rdx+NODE.LEFT],TTNull
                        mov  qword[rdx+NODE.RIGHT],TTNull
                        mov  dword[rdx+NODE.COL],1                ; set color to red
                        mov  dword[rdx+NODE.NUM],ecx
                        mov  rax,rdx                             ; this is the node to return

.FixNode:               ; node is in rdx

; Case 1: The current node N is at the root of the tree. In this case, it is repainted black to satisfy property 2 (the root is black). Since this adds one black node to every path at once, property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated.
 .Case1:                mov  r8,qword[rdx+NODE.UP]
                        cmp  r8,TTHead
                        jne  .Case2
                        mov  byte[rdx+NODE.COL],0    ; set as black
                        ret

; Case 2: The current node's parent P is black, so property 4 (both children of every red node are black) is not invalidated. In this case, the tree is still valid. Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not threatened, because the current node N has two black leaf children, but because N is red, the paths through each of its children have the same number of black nodes as the path through the leaf it replaced, which was black, and so this property remains satisfied.
 .Case2:                cmp  byte[r8+NODE.COL],0
                        jne  .Case3
                        ret

; Case 3: If both the parent P and the uncle U are red, then both of them can be repainted black and the grandparent G becomes red (to maintain property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes)). Now, the current red node N has a black parent. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent G may now violate properties 2 (The root is black) or 4 (Both children of every red node are black) (property 4 possibly being violated since G may have a red parent). To fix this, the entire procedure is recursively performed on G from case 1
 .Case3:                mov  r9,qword[r8+NODE.UP]    ; r8 must have a parent
                        mov  r10,qword[r9+NODE.LEFT]
                        mov  r11,qword[r9+NODE.RIGHT]
                        cmp  r8,r10
                      cmove  r10,r11
                        cmp  r10,TTNull
                         je  .Case4
                        cmp  byte[r10+NODE.COL],0
                         je  .Case4
                        mov  rdx,r9
                        mov  byte[r8+NODE.COL],0
                        mov  byte[r9+NODE.COL],1
                        mov  byte[r10+NODE.COL],0
                        jmp  .FixNode

; Case 4: The parent P is red but the uncle U is black; also, the current node N is the right child of P, and P in turn is the left child of its parent G. In this case, a left rotation on P that switches the roles of the current node N and
 .Case4:                mov  r10,qword[r9+NODE.UP]     ; r10 = great grandparent of rdx
 .Case4A:               cmp  rdx,qword[r8+NODE.RIGHT]
                        jne  .Case4B
                        cmp  r8,qword[r9+NODE.LEFT]
                        jne  .Case4B
                        mov  r11,qword[rdx+NODE.LEFT]
                        mov  qword[r9+NODE.LEFT],rdx
                        mov  qword[rdx+NODE.LEFT],r8
                        mov  qword[r8+NODE.RIGHT],r11
                        mov  qword[r8+NODE.UP],rdx
                        mov  qword[rdx+NODE.UP],r9
                        mov  qword[r11+NODE.UP],r8
                        jmp  .Case4Done

  .Case4B:              cmp  rdx,qword[r8+NODE.LEFT]
                        jne  .Case5
                        cmp  r8,qword[r9+NODE.RIGHT]
                        jne  .Case5
                        mov  r11,qword[rdx+NODE.RIGHT]
                        mov  qword[r9+NODE.RIGHT],rdx
                        mov  qword[rdx+NODE.RIGHT],r8
                        mov  qword[r8+NODE.LEFT],r11
                        mov  qword[r8+NODE.UP],rdx
                        mov  qword[rdx+NODE.UP],r9
                        mov  qword[r11+NODE.UP],r8

 .Case4Done:           xchg  rdx,r8

; Case 5: The parent P is red but the uncle U is black, the current node N is the left child of P, and P is the left child of its parent G. In this case, a right rotation on G is performed; the result is a tree where the former parent P is now the parent of both the current node N and the former grandparent G.
 .Case5:
                        mov  r11,qword[r10+NODE.RIGHT]
                        cmp  r11,r9
                      cmove  r11,r8
                        mov  qword[r10+NODE.RIGHT],r11
                        mov  r11,qword[r10+NODE.LEFT]
                        cmp  r11,r9
                      cmove  r11,r8
                        mov  qword[r10+NODE.LEFT],r11

                        mov  qword[r8+NODE.UP],r10
                        mov  byte[r8+NODE.COL],0
                        mov  qword[r9+NODE.UP],r8
                        mov  byte[r9+NODE.COL],1

                        mov  r11,qword[r8+NODE.RIGHT]
                        mov  r10,qword[r8+NODE.LEFT]
                        cmp  rdx,r10
                        jne  .Case5Left

  .Case5Right:          mov  qword[r8+NODE.RIGHT],r9
                        mov  qword[r9+NODE.LEFT],r11
                        mov  qword[r11+NODE.UP],r9
                        ret

  .Case5Left:           mov  qword[r8+NODE.LEFT],r9
                        mov  qword[r9+NODE.RIGHT],r10
                        mov  qword[r10+NODE.UP],r9
                        ret






                ; Clears the transposition table

                      align  16
TT_Clear:
                        mov  qword[TTHead+NODE.LEFT],TTNull
                        mov  dword[TTEntries],0
                        ret



               ; Prints the table to rdi

                      align  16
TT_InOrderTraverse:
                        mov  rcx,qword[TTHead+NODE.LEFT]
  .entry:               cmp  rcx,TTNull
                         je  .ret
                       push  rcx
                        mov  rcx,[rcx+NODE.LEFT]
                       call  .entry
                        mov  rcx,[rsp]
                       call  TT_PrintNode
                        pop  rcx
                        mov  rcx,[rcx+NODE.RIGHT]
                       call  .entry
           .ret:        ret


               ; Prints node at rcx

                      align  16
TT_PrintNode:
                     movsxd  rax,dword[rcx+NODE.NUM]
                       call  PrintInteger
                        mov  eax,' '
                      stosb
                        ret








PrintInteger:       ; rax: number
                       push  rbp
                       push  rdx
                        mov  rbp,rsp
                       test  rax,rax
                        jns  .l1
                        mov  byte[rdi],'-'
                        add  rdi,1
                        neg  rax
                .l1:    xor  edx,edx
                        div  [OutputBase]
                       push  rdx
                       test  rax,rax
                        jnz  .l1
                .l2:    pop  rax
                        cmp  al,9
                        jbe  @f
                        add  al,'a'-10-'0'
                 @@:    add  al,'0'
                      stosb
                        cmp  rsp,rbp
                         jb  .l2
                        pop  rdx
                        pop  rbp
                        ret


ParseInteger:       ; string at rsi, integer to rax
                        xor  ecx,ecx
                        xor  eax,eax
                        xor  edx,edx
                        cmp  byte[rsi],'-'
                         je  .neg
                        cmp  byte[rsi],'+'
                         je  .pos
                        jmp  .next
          .neg:         not  rdx
          .pos:         add  rsi,1
          .next:        mov  cl,byte[rsi]
                       test  cl,cl
                         jz  .done
                        sub  cl,'0'
                         js  .done
                        cmp  cl,9
                         ja  .done
                        add  rsi,1
                       imul  rax,[OutputBase]
                        add  rax,rcx
                        jmp  .next
         .done:         xor  rax,rdx
                        sub  rax,rdx
                        ret



SkipSpaces:     ; rsi string
                ; skip over anything that is not a digit or NULL
                       sub  rsi,1
                @@:    add  rsi,1
                       cmp  byte[rsi],0
                        je  .done
                       cmp  byte[rsi],'0'
                        jb  @b
                       cmp  byte[rsi],'9'
                        ja  @b
.done:                 ret





section '.data' data readable writeable

align 8
  OutputBase  dq 10


align 4
  TTEntries         dd ?


InputString  rb 1024
ResultString rb 1024

align 64
  TTHead    NODE
  TTNull    NODE
  TT        rb sizeof.NODE*TT_MAX_ENTRIES


section '.idata' import data readable writeable


 library kernel32,'KERNEL32.DLL',\
         user32,'USER32.DLL',\
         gdi32,'GDI32.DLL',\
         comctl32,'COMCTL32.DLL'

include 'api/kernel32.inc'
include 'api/user32.inc'
include 'api/gdi32.inc'

 import  comctl32,\
         InitCommonControls,'InitCommonControls'




section '.rsrc' resource data readable

  directory RT_DIALOG,dialogs

  resource dialogs,\
           ID_DLGMAIN,LANG_ENGLISH+SUBLANG_DEFAULT,calculator

  dialog calculator,'red-black sorter',10,10,384,60,DS_CENTER+DS_MODALFRAME+WS_SYSMENU+WS_MINIMIZEBOX,0,0;ID_MENUMAIN
    dialogitem 'STATIC','enter number to sort separated by spaces',-1,  2,02,380,8, WS_VISIBLE+SS_LEFT+WS_GROUP
    dialogitem 'EDIT','',ID_EXPRESSION,                                 2,14,380,12,WS_VISIBLE+WS_TABSTOP+WS_BORDER+ES_AUTOHSCROLL
    dialogitem 'EDIT','',ID_RESULT,                                     2,30,380,12,WS_VISIBLE+WS_BORDER+WS_TABSTOP+ES_READONLY+ES_AUTOHSCROLL
  enddialog
                     
Post 07 Feb 2014, 18:05
View user's profile Send private message Reply with quote
typedef



Joined: 25 Jul 2010
Posts: 2914
Location: 0x77760000
typedef
So you want to also provide a 32-bit version?
Post 07 Feb 2014, 18:29
View user's profile Send private message Reply with quote
tthsqe



Joined: 20 May 2009
Posts: 721
tthsqe
32 bit version
Code:
format PE GUI 4.0
entry Start

include 'win32axp.inc'

TT_MAX_ENTRIES     fix 1024


IDI_MAIN        = 17
ID_DLGMAIN      = 37
ID_EXPRESSION   = 39
ID_RESULT       = 200


struct NODE    ; 32 bytes in size
  LEFT   dd ?      ; left child
  RIGHT  dd ?      ; right child
  UP     dd ?      ; parent
  COL    db ?      ; 0 for black, 1 for red   \
         db ?,?,?  ; unused
  NUM    dd ?      ; number
         dd ?,?,?
ends

LG_NODE_SIZE fix 5  ; log2(sizeof.NODE)


section '.text' code readable executable



Start:
                     invoke  InitCommonControls
                     invoke  GetModuleHandle,NULL
                     invoke  DialogBoxParam,eax,ID_DLGMAIN,NULL,DlgProc,NULL
                     invoke  ExitProcess,0

proc DlgProc,.hDlg,.uMsg,.wParam,.lParam
                        mov  eax,dword[.uMsg]
                        cmp  eax,WM_COMMAND
                         je  .wmcommand
                        cmp  eax,WM_CLOSE
                         je  .wmclose
                        cmp  eax,WM_INITDIALOG
                         je  .wminitdialog
 .default:
                        xor  eax, eax
                        ret
 .wmcommand:
                      movzx  edx,word[.wParam+2]
                      movzx  eax,word[.wParam]
                        cmp  eax,ID_EXPRESSION
                        jne  .default
                        cmp  edx, EN_CHANGE
                        jne  .default
 .edit_changed:
                      invoke  SendDlgItemMessage,[.hDlg],ID_EXPRESSION,WM_GETTEXT,1023,InputString

                       push  esi edi
                       call  TT_Clear
                        lea  esi,[InputString]
       .read_next:     call  SkipSpaces
                        cmp  byte[esi],0
                         je  .read_done
                       call  ParseInteger
                        mov  ecx,eax
                       call  TT_FindNode
                        jmp  .read_next
       .read_done:      lea  edi,[ResultString]
                       call  TT_InOrderTraverse
                        xor  eax,eax
                      stosb
                        pop  edi esi

                     invoke  SetDlgItemText,[.hDlg],ID_RESULT,ResultString
                        jmp  .default
 .wmclose:
                     invoke  EndDialog,[.hDlg],0
                        jmp  .default
 .wminitdialog:
                     invoke  SendDlgItemMessage,[.hDlg],ID_EXPRESSION,EM_LIMITTEXT,1022,0
 .processed:
                        mov  eax,1
 .return:
                        ret
endp


                ; return in eax address of node that corresponds to number in ecx
                ; if ecx is not in table, then a new node is made
                ; if table is full, then TTNull is returned
                ; NOTE: insertion code is stolen from wikipedia

                      align  16
TT_FindNode:
                        mov  edx,dword[TTEntries]
                       test  edx,edx
                        jnz  .OldTree

.NewTree:               lea  eax,[TT]
                        add  edx,1
                        mov  dword[TTEntries],edx
                        mov  dword[eax+NODE.UP],TTHead
                        mov  dword[eax+NODE.LEFT],TTNull
                        mov  dword[eax+NODE.RIGHT],TTNull
                        mov  dword[eax+NODE.COL],0
                        mov  dword[eax+NODE.NUM],ecx
                        mov  dword[TTHead+NODE.LEFT],eax
                        ret


                      align  16

.TreeFull:              lea  eax,[TTNull]

.Ret:                   pop  ebx esi edi ebp
                        ret



               ; this can be called to skip the previous branch if it is known that the tree is not empty

                      align  16
.OldTree:              push  ebp edi esi ebx
                        mov  ebx,dword[TTHead+NODE.LEFT]
                        mov  edx,dword[TTEntries]

                        lea  ebp,[edx+1]
                        shl  edx,LG_NODE_SIZE
                        lea  edx,[edx+TT]
 .Compare:
                        mov  esi,dword[ebx+NODE.LEFT]
                        mov  edi,dword[ebx+NODE.RIGHT]
                        mov  eax,dword[ebx+NODE.NUM]
                        cmp  eax,ecx
                         jg  .GoLeft
                         jl  .GoRight

 .Found:                mov  eax,ebx
                        jmp  .Ret

 .GoLeft:               cmp  esi,TTNull
                         je  .MakeNewLeft
                        mov  ebx,esi
                        jmp  .Compare

 .GoRight:              cmp  edi,TTNull
                         je  .MakeNewRight
                        mov  ebx,edi
                        jmp  .Compare

.MakeNewLeft:           cmp  ebp,TT_MAX_ENTRIES
                         ja  .TreeFull
                        mov  dword[ebx+NODE.LEFT],edx
                        jmp  .FixTree

.MakeNewRight:          cmp  ebp,TT_MAX_ENTRIES
                         ja  .TreeFull
                        mov  dword[ebx+NODE.RIGHT],edx


.FixTree:               mov  dword[TTEntries],ebp
                        mov  dword[edx+NODE.UP],ebx
                        mov  dword[edx+NODE.LEFT],TTNull
                        mov  dword[edx+NODE.RIGHT],TTNull
                        mov  dword[edx+NODE.COL],1                ; set color to red
                        mov  dword[edx+NODE.NUM],ecx
                        mov  eax,edx                             ; this is the node to return

.FixNode:               ; node is in rdx

; Case 1: The current node N is at the root of the tree. In this case, it is repainted black to satisfy property 2 (the root is black). Since this adds one black node to every path at once, property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not violated.
 .Case1:                mov  esi,dword[edx+NODE.UP]
                        cmp  esi,TTHead
                        jne  .Case2
                        mov  byte[edx+NODE.COL],0    ; set as black
                        jmp  .Ret

; Case 2: The current node's parent P is black, so property 4 (both children of every red node are black) is not invalidated. In this case, the tree is still valid. Property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes) is not threatened, because the current node N has two black leaf children, but because N is red, the paths through each of its children have the same number of black nodes as the path through the leaf it replaced, which was black, and so this property remains satisfied.
 .Case2:                cmp  byte[esi+NODE.COL],0
                         je  .Ret

; Case 3: If both the parent P and the uncle U are red, then both of them can be repainted black and the grandparent G becomes red (to maintain property 5 (all paths from any given node to its leaf nodes contain the same number of black nodes)). Now, the current red node N has a black parent. Since any path through the parent or uncle must pass through the grandparent, the number of black nodes on these paths has not changed. However, the grandparent G may now violate properties 2 (The root is black) or 4 (Both children of every red node are black) (property 4 possibly being violated since G may have a red parent). To fix this, the entire procedure is recursively performed on G from case 1
 .Case3:                mov  edi,dword[esi+NODE.UP]    ; rsi must have a parent
                        mov  ebx,dword[edi+NODE.LEFT]
                        mov  ebp,dword[edi+NODE.RIGHT]
                        cmp  esi,ebx
                      cmove  ebx,ebp
                        cmp  ebx,TTNull
                         je  .Case4
                        cmp  byte[ebx+NODE.COL],0
                         je  .Case4
                        mov  edx,edi
                        mov  byte[esi+NODE.COL],0
                        mov  byte[edi+NODE.COL],1
                        mov  byte[ebx+NODE.COL],0
                        jmp  .FixNode

; Case 4: The parent P is red but the uncle U is black; also, the current node N is the right child of P, and P in turn is the left child of its parent G. In this case, a left rotation on P that switches the roles of the current node N and
 .Case4:                mov  ebx,dword[edi+NODE.UP]     ; rbx = great grandparent of rdx
 .Case4A:               cmp  edx,dword[esi+NODE.RIGHT]
                        jne  .Case4B
                        cmp  esi,dword[edi+NODE.LEFT]
                        jne  .Case4B
                        mov  ebp,dword[edx+NODE.LEFT]
                        mov  dword[edi+NODE.LEFT],edx
                        mov  dword[edx+NODE.LEFT],esi
                        mov  dword[esi+NODE.RIGHT],ebp
                        mov  dword[esi+NODE.UP],edx
                        mov  dword[edx+NODE.UP],edi
                        mov  dword[ebp+NODE.UP],esi
                        jmp  .Case4Done

  .Case4B:              cmp  edx,dword[esi+NODE.LEFT]
                        jne  .Case5
                        cmp  esi,dword[edi+NODE.RIGHT]
                        jne  .Case5
                        mov  ebp,dword[edx+NODE.RIGHT]
                        mov  dword[edi+NODE.RIGHT],edx
                        mov  dword[edx+NODE.RIGHT],esi
                        mov  dword[esi+NODE.LEFT],ebp
                        mov  dword[esi+NODE.UP],edx
                        mov  dword[edx+NODE.UP],edi
                        mov  dword[ebp+NODE.UP],esi

 .Case4Done:           xchg  edx,esi

; Case 5: The parent P is red but the uncle U is black, the current node N is the left child of P, and P is the left child of its parent G. In this case, a right rotation on G is performed; the result is a tree where the former parent P is now the parent of both the current node N and the former grandparent G.
 .Case5:
                        mov  ebp,dword[ebx+NODE.RIGHT]
                        cmp  ebp,edi
                      cmove  ebp,esi
                        mov  dword[ebx+NODE.RIGHT],ebp
                        mov  ebp,dword[ebx+NODE.LEFT]
                        cmp  ebp,edi
                      cmove  ebp,esi
                        mov  dword[ebx+NODE.LEFT],ebp

                        mov  dword[esi+NODE.UP],ebx
                        mov  byte[esi+NODE.COL],0
                        mov  dword[edi+NODE.UP],esi
                        mov  byte[edi+NODE.COL],1

                        mov  ebp,dword[esi+NODE.RIGHT]
                        mov  ebx,dword[esi+NODE.LEFT]
                        cmp  edx,ebx
                        jne  .Case5Left

  .Case5Right:          mov  dword[esi+NODE.RIGHT],edi
                        mov  dword[edi+NODE.LEFT],ebp
                        mov  dword[ebp+NODE.UP],edi
                        jmp  .Ret

  .Case5Left:           mov  dword[esi+NODE.LEFT],edi
                        mov  dword[edi+NODE.RIGHT],ebx
                        mov  dword[ebx+NODE.UP],edi
                        jmp  .Ret






                ; Clears the transposition table

                      align  16
TT_Clear:
                        mov  dword[TTHead+NODE.LEFT],TTNull
                        mov  dword[TTEntries],0
                        ret



               ; Prints the table to rdi

                      align  16
TT_InOrderTraverse:
                        mov  ecx,dword[TTHead+NODE.LEFT]
  .entry:               cmp  ecx,TTNull
                         je  .ret
                       push  ecx
                        mov  ecx,dword[ecx+NODE.LEFT]
                       call  .entry
                        mov  ecx,[esp]
                       call  TT_PrintNode
                        pop  ecx
                        mov  ecx,dword[ecx+NODE.RIGHT]
                       call  .entry
           .ret:        ret


               ; Prints node at rcx

                      align  16
TT_PrintNode:
                        mov  eax,dword[ecx+NODE.NUM]
                       call  PrintInteger
                        mov  eax,' '
                      stosb
                        ret








PrintInteger:       ; rax: number
                       push  ebp
                       push  edx
                        mov  ebp,esp
                       test  eax,eax
                        jns  .l1
                        mov  byte[edi],'-'
                        add  edi,1
                        neg  eax
                .l1:    xor  edx,edx
                        div  [OutputBase]
                       push  edx
                       test  eax,eax
                        jnz  .l1
                .l2:    pop  eax
                        add  al,'0'
                      stosb
                        cmp  esp,ebp
                         jb  .l2
                        pop  edx
                        pop  ebp
                        ret


ParseInteger:       ; string at rsi, integer to rax
                        xor  ecx,ecx
                        xor  eax,eax
                        xor  edx,edx
                        cmp  byte[esi],'-'
                         je  .neg
                        cmp  byte[esi],'+'
                         je  .pos
                        jmp  .next
          .neg:         not  edx
          .pos:         add  esi,1
          .next:        mov  cl,byte[esi]
                       test  cl,cl
                         jz  .done
                        sub  cl,'0'
                         js  .done
                        cmp  cl,9
                         ja  .done
                        add  esi,1
                       imul  eax,[OutputBase]
                        add  eax,ecx
                        jmp  .next
         .done:         xor  eax,edx
                        sub  eax,edx
                        ret



SkipSpaces:     ; rsi string
                ; skip over anything that is not a digit or NULL
                       sub  esi,1
                @@:    add  esi,1
                       cmp  byte[esi],0
                        je  .done
                       cmp  byte[esi],'0'
                        jb  @b
                       cmp  byte[esi],'9'
                        ja  @b
.done:                 ret





section '.data' data readable writeable

align 4
  OutputBase  dd 10


align 4
  TTEntries         dd ?


InputString  rb 1024
ResultString rb 1024

align 64
  TTHead    NODE
  TTNull    NODE
  TT        rb sizeof.NODE*TT_MAX_ENTRIES


section '.idata' import data readable writeable


 library kernel32,'KERNEL32.DLL',\
         user32,'USER32.DLL',\
         gdi32,'GDI32.DLL',\
         comctl32,'COMCTL32.DLL'

include 'api/kernel32.inc'
include 'api/user32.inc'
include 'api/gdi32.inc'

 import  comctl32,\
         InitCommonControls,'InitCommonControls'




section '.rsrc' resource data readable

  directory RT_DIALOG,dialogs

  resource dialogs,\
           ID_DLGMAIN,LANG_ENGLISH+SUBLANG_DEFAULT,calculator

  dialog calculator,'red-black sorter',10,10,384,60,DS_CENTER+DS_MODALFRAME+WS_SYSMENU+WS_MINIMIZEBOX,0,0;ID_MENUMAIN
    dialogitem 'STATIC','enter number to sort separated by spaces',-1,  2,02,380,8, WS_VISIBLE+SS_LEFT+WS_GROUP
    dialogitem 'EDIT','',ID_EXPRESSION,                                 2,14,380,12,WS_VISIBLE+WS_TABSTOP+WS_BORDER+ES_AUTOHSCROLL
    dialogitem 'EDIT','',ID_RESULT,                                     2,30,380,12,WS_VISIBLE+WS_BORDER+WS_TABSTOP+ES_READONLY+ES_AUTOHSCROLL
  enddialog    
Post 07 Feb 2014, 19:10
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.