twowaymergesort.asm

一个演示了用汇编语言编写的数据排序算法,源代码非常详细

; Date: 14.03.2004 - 15.03.2004

IFNDEF TWMS_Arr
  .data?
    TWMS_Arr     DWORD ?
ENDIF

.code

IFNDEF PURE_ALGORITHM


  TwoWayMergeSort         PROTO :DWORD, :DWORD
  NaturalTwoWayMergeSort  PROTO :DWORD, :DWORD
  StraightTwoWayMergeSort PROTO :DWORD, :DWORD

  TwoWayMergeSort_Sort    PROTO :DWORD, :DWORD
  TwoWayMergeSort_Merge   PROTO :DWORD, :DWORD, :DWORD


TwoWayMergeSort PROC Arr:DWORD, count:DWORD

    mov    eax, Arr
    mov    TWMS_Arr, eax


    mov    eax, count
    shl    eax, 2
    mov    SortInfo.usedMemory, eax
    invoke SysAllocStringByteLen, 0, eax
    test   eax, eax
    jz     @InsufficientMemory

    mov    SortInfo.hMemory, eax

    mov    eax, count
    dec    eax
    push   eax
    push   0
    call   TwoWayMergeSort_Sort

    invoke SysFreeString, SortInfo.hMemory



@Return:
  ret
@InsufficientMemory:
  mov    SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
  ret

TwoWayMergeSort ENDP



NaturalTwoWayMergeSort PROC Arr:DWORD, count:DWORD

    mov    eax, Arr
    mov    TWMS_Arr, eax


    mov    eax, count
    shl    eax, 2
    mov    SortInfo.usedMemory, eax
    invoke SysAllocStringByteLen, 0, eax
    test   eax, eax
    jz     @InsufficientMemory

    mov    SortInfo.hMemory, eax


    mov    esi, TWMS_Arr
    mov    edi, count
    lea    edi, [esi + edi*4 - 4]

@Loop1:
    mov    eax, esi
    sub    eax, 4    
    @Loop2:
        mov    ebx, eax
        add    ebx, 4        
        mov    ecx, ebx
        
        @Loop3:
            cmp    ecx, edi
            jnb    @Loop2a

;-------------------------------------------------------------------------------
  IncCMPCounter

  push   ebx
    lea    ebx, [ecx + 4]
    DelayAfterComparison ecx, ebx
  pop    ebx
;-------------------------------------------------------------------------------

            mov    edx, DWORD PTR [ecx]
            add    ecx, 4
            cmp    DWORD PTR [ecx], edx
            jae    @Loop3

            sub    ecx, 4            
    @Loop2a:
        mov    eax, ecx
        cmp    ecx, edi
        jnb    @Loop2Foot

        add    eax, 4        

        @Loop4:
            cmp    eax, edi
            jnb    @Loop2b

;-------------------------------------------------------------------------------
  IncCMPCounter

  push   ebx
    lea    ebx, [eax + 4]
    DelayAfterComparison eax, ebx
  pop    ebx
;-------------------------------------------------------------------------------

            mov    edx, DWORD PTR [eax]
            add    eax, 4
            cmp    DWORD PTR [eax], edx
            jae    @Loop4

            sub    eax, 4

    @Loop2b:
        push   ebx
        push   esi
        push   eax
        push   edi

            sub    ebx, esi
            sub    ecx, esi
            sub    eax, esi

            shr    ebx, 2
            shr    ecx, 2
            shr    eax, 2

            push   eax
            push   ecx
            push   ebx
            call   TwoWayMergeSort_Merge

        pop    edi
        pop    eax
        pop    esi
        pop    ebx

;-------------------------------------------------------------------------------
  DelayAfterPass
;-------------------------------------------------------------------------------

    @Loop2Foot:
        cmp    eax, edi
        jb     @Loop2

        cmp    ebx, esi
        jne    @Loop1


    invoke SysFreeString, SortInfo.hMemory



@Return:
  ret
@InsufficientMemory:
  mov    SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
  ret

NaturalTwoWayMergeSort ENDP



StraightTwoWayMergeSort PROC Arr:DWORD, count:DWORD

    mov    eax, Arr  
    mov    TWMS_Arr, eax


    mov    eax, count
    shl    eax, 2
    mov    SortInfo.usedMemory, eax
    invoke SysAllocStringByteLen, 0, eax
    test   eax, eax
    jz     @InsufficientMemory

    mov    SortInfo.hMemory, eax


    mov    esi, count
    dec    esi
    mov    eax, 1

@Loop1:
    mov    edx, -1

    @Loop2:
        mov    ecx, edx
        add    ecx, eax
        cmp    ecx, esi
        jnb    @Loop1a

        mov    edi, edx
        inc    edi

        mov    ebx, edx
        add    ebx, eax

        mov    edx, ebx
        add    edx, eax
        cmp    edx, esi
        jbe    @Merge

        mov    edx, esi

    @Merge:
        push   eax
        push   edx
        push   esi

            push   edx
            push   ebx
            push   edi
            call   TwoWayMergeSort_Merge

        pop    esi
        pop    edx
        pop    eax

;-------------------------------------------------------------------------------
  DelayAfterPass
;-------------------------------------------------------------------------------

        jmp    @Loop2

@Loop1a:
    shl    eax, 1
    cmp    eax, esi
    jbe    @Loop1


    invoke SysFreeString, SortInfo.hMemory



@Return:
  ret
@InsufficientMemory:
  mov    SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
  ret

StraightTwoWayMergeSort ENDP



TwoWayMergeSort_Sort PROC left:DWORD, right:DWORD

    mov    ebx, left
    mov    ecx, right
    cmp    ebx, ecx
    je     @Return

    mov    eax, ebx
    add    eax, ecx
    shr    eax, 1

    push   eax
    push   ebx
    push   ecx

        push   eax
        push   ebx
        call   TwoWayMergeSort_Sort ; sort from left to middle

    pop    ecx
    pop    ebx
    pop    eax

    push   eax
    push   ebx
    push   ecx

        push   ecx
        inc    eax
        push   eax
        call   TwoWayMergeSort_Sort ; sort from middle + 1 to right

    pop    ecx
    pop    ebx
    pop    eax

    push   ecx                      ; index of the right element
    push   eax                      ; index of the medially element
    push   ebx                      ; index of the left element
    call   TwoWayMergeSort_Merge    ; merge

;-------------------------------------------------------------------------------
  DelayAfterPass
;-------------------------------------------------------------------------------



@Return:
  ret

TwoWayMergeSort_Sort ENDP



TwoWayMergeSort_Merge PROC left:DWORD, mid:DWORD, right:DWORD

    mov    edi, SortInfo.hMemory    ; EDI = offset of a buffer 
    mov    edx, TWMS_Arr            ; EDX = offset of the subset that shall be merged

    mov    eax, left
    lea    eax, [edx + eax*4]       ; EAX = offset of the left subset

    mov    ecx, mid
    lea    ecx, [edx + ecx*4]       ; ECX = end of the left subset

    lea    ebx, [ecx + 4]           ; EBX = offset of the right subset

    mov    esi, right
    lea    esi, [edx + esi*4]       ; ESI = end of the right subset

    ;---------------------------------------------------------------------------
    ;-- If either the left or the right subset is processed abort the loop.
  @Loop1:
      cmp    eax, ecx
      ja     @CopyTemp

      cmp    ebx, esi
      ja     @Copy1stSequence

;-------------------------------------------------------------------------------
  IncCMPCounter

  DelayAfterComparison eax, ebx
;-------------------------------------------------------------------------------

      ;-------------------------------------------------------------------------
      ;-- Is the element from the left subset greater thab the one from the
      ;-- right?
      mov    edx, DWORD PTR [eax]
      cmp    edx, DWORD PTR [ebx]
      ja     @CopyFrom2nd

        ;-----------------------------------------------------------------------
        ;-- No. Copy the element from the left subset to the buffer.
        mov    DWORD PTR [edi], edx

;-------------------------------------------------------------------------------
  IncMOVCounter
;-------------------------------------------------------------------------------

        ;-----------------------------------------------------------------------
        ;-- Increment the indices of the left subset and of the buffer.
        add    eax, 4
        add    edi, 4
        jmp    @Loop1


        ;-----------------------------------------------------------------------
        ;-- Yes. Copy the element from the right subset to the buffer.
      @CopyFrom2nd:
        mov    edx, DWORD PTR [ebx]
        mov    DWORD PTR [edi], edx

;-------------------------------------------------------------------------------
  IncMOVCounter
;-------------------------------------------------------------------------------

      ;-------------------------------------------------------------------------
      ;-- Increment the indices of the right subset and of the buffer.
      add    ebx, 4
      add    edi, 4
      jmp    @Loop1


    ;---------------------------------------------------------------------------
    ;-- The right subset is completely processed. Now copy the remaining (not
    ;-- processed) elements of the left subset to the buffer.
  @Copy1stSequence:

      ;-------------------------------------------------------------------------
      ;-- Move the index of the right subset to the last element.
      sub    ebx, 4


      ;-------------------------------------------------------------------------
      ;-- Load the next element from the left subset and copy it to the right
      ;-- subset.
      mov    edx, DWORD PTR [ecx]
      mov    DWORD PTR [ebx], edx

;-------------------------------------------------------------------------------
  IncMOVCounter

  RefreshElement ebx

  DelayAfterExchange
;-------------------------------------------------------------------------------

      ;---------------------------------------------------------------------------
      ;-- Move the index of the left subset to the previos element.
      sub    ecx, 4


      ;-------------------------------------------------------------------------
      ;-- If not all remaining elements have been copyied copy the next one.
      cmp    ecx, eax
      jae    @Copy1stSequence


    ;---------------------------------------------------------------------------
    ;-- The left subset is completely processed. Now copy the buffer to the
    ;-- source.
  @CopyTemp:
      mov    edi, SortInfo.hMemory  ; EDI = offset of the buffer
      mov    eax, left
      shl    eax, 2
      add    eax, TWMS_Arr          ; EAX = offset of the merged subset

    @@:
        ;-----------------------------------------------------------------------
        ;-- Copy the element of the buffer to the merged subset.
        mov    edx, DWORD PTR [edi]
        mov    DWORD PTR [eax], edx

;-------------------------------------------------------------------------------
  IncMOVCounter

  RefreshElement eax

  DelayAfterExchange
;-------------------------------------------------------------------------------