bucketsort.asm

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

; Date: 30.04.2004 - 01.05.2004

.code

IFNDEF PURE_ALGORITHM


  BucketSort PROTO :DWORD, :DWORD


BucketSort PROC Arr:DWORD, count:DWORD

  LOCAL buckets[256] :DWORD
  LOCAL temp         :DWORD
  LOCAL byteIndex    :DWORD

;-------------------------------------------------------------------------------
  LOCAL fSwitched    :BYTE

  mov    fSwitched, FALSE
;-------------------------------------------------------------------------------

    mov    eax, count
    lea    eax, [eax*4]
    mov    SortInfo.usedMemory, eax
    invoke SysAllocStringByteLen, 0, eax
    test   eax, eax
    jz     @InsufficientMemory

    mov    SortInfo.hMemory, eax
    mov    temp, eax

    mov    byteIndex, NULL

  @Loop1:
      ;-------------------------------------------------------------------------
      ;-- Set the members of the count array to NULL.
      mov    ecx, 256
      lea    esi, buckets

    @Loop2:
        mov    DWORD PTR [esi], NULL
        add    esi, 4
        dec    ecx
        jnz    @Loop2


      ;-------------------------------------------------------------------------
      ;-- Calculate the frequentness of the element values.
      mov    ecx, count
      mov    ebx, Arr
      add    ebx, byteIndex
      lea    esi, buckets
      xor    eax, eax

    @Loop3:
        mov    al, BYTE PTR [ebx]
        inc    DWORD PTR [esi + eax*4]
        add    ebx, 4
        dec    ecx
        jnz    @Loop3


      ;-------------------------------------------------------------------------
      ;-- Now add the frequentness of the element values.
      mov    ecx, 1
      lea    edi, [esi - 4]

    @Loop4:
        mov    eax, DWORD PTR [edi + ecx*4]
        add    DWORD PTR [esi + ecx*4], eax
        inc    cl
        jnz    @Loop4


      ;-------------------------------------------------------------------------
      ;-- Sort the elements (with respect to the current byte).
      mov    ecx, count
      dec    ecx

      mov    ebx, ecx
      shl    ebx, 2
      add    ebx, Arr
      mov    esi, ebx
      add    esi, byteIndex
      mov    edi, temp

    @Loop5:
        xor    eax, eax
        mov    al, BYTE PTR [esi]
        sub    esi, 4

        dec    DWORD PTR [buckets + eax*4]
        mov    eax, DWORD PTR [buckets + eax*4]

        mov    edx, DWORD PTR [ebx]
        mov    DWORD PTR [edi + eax*4], edx

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

  .IF fSwitched
    push eax
      lea eax, [edi + eax*4]
      RefreshElement eax
    pop eax

    DelayAfterExchange
  .ENDIF
;-------------------------------------------------------------------------------

        sub    ebx, 4

        dec    ecx
        jns    @Loop5


      mov    eax, Arr
      mov    ebx, temp
      mov    Arr, ebx
      mov    temp, eax

;-------------------------------------------------------------------------------
  xor fSwitched, 1
;-------------------------------------------------------------------------------

      inc    byteIndex
      cmp    byteIndex, 3
      jbe    @Loop1



@Return:
  invoke SysFreeString, SortInfo.hMemory
  ret
@InsufficientMemory:
  mov    SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
  ret

BucketSort ENDP


ELSE


  BucketSort_PURE PROTO :DWORD, :DWORD


BucketSort_PURE PROC Arr:DWORD, count:DWORD

  LOCAL buckets[256] :DWORD
  LOCAL temp         :DWORD
  LOCAL byteIndex    :DWORD

    mov    eax, count
    lea    eax, [eax*4]
    mov    SortInfo.usedMemory, eax
    invoke SysAllocStringByteLen, 0, eax
    test   eax, eax
    jz     @InsufficientMemory

    mov    SortInfo.hMemory, eax
    mov    temp, eax

    mov    byteIndex, NULL

  @Loop1:
      ;-------------------------------------------------------------------------
      ;-- Set the members of the count array to NULL.
      mov    ecx, 256
      lea    esi, buckets

    @Loop2:
        mov    DWORD PTR [esi], NULL
        add    esi, 4
        dec    ecx
        jnz    @Loop2


      ;-------------------------------------------------------------------------
      ;-- Calculate the frequentness of the element values.
      mov    ecx, count
      mov    ebx, Arr
      add    ebx, byteIndex
      lea    esi, buckets
      xor    eax, eax

    @Loop3:
        mov    al, BYTE PTR [ebx]
        inc    DWORD PTR [esi + eax*4]
        add    ebx, 4
        dec    ecx
        jnz    @Loop3


      ;-------------------------------------------------------------------------
      ;-- Now add the frequentness of the element values.
      mov    ecx, 1
      lea    edi, [esi - 4]

    @Loop4:
        mov    eax, DWORD PTR [edi + ecx*4]
        add    DWORD PTR [esi + ecx*4], eax
        inc    cl
        jnz    @Loop4


      ;-------------------------------------------------------------------------
      ;-- Sort the elements (with respect to the current byte).
      mov    ecx, count
      dec    ecx

      mov    ebx, ecx
      shl    ebx, 2
      add    ebx, Arr
      mov    esi, ebx
      add    esi, byteIndex
      mov    edi, temp

    @Loop5:
        xor    eax, eax
        mov    al, BYTE PTR [esi]
        sub    esi, 4

        dec    DWORD PTR [buckets + eax*4]
        mov    eax, DWORD PTR [buckets + eax*4]

        mov    edx, DWORD PTR [ebx]
        mov    DWORD PTR [edi + eax*4], edx

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

        sub    ebx, 4

        dec    ecx
        jns    @Loop5


      mov    eax, Arr
      mov    ebx, temp
      mov    Arr, ebx
      mov    temp, eax

      inc    byteIndex
      cmp    byteIndex, 3
      jbe    @Loop1



@Return:
  invoke SysFreeString, SortInfo.hMemory
  ret
@InsufficientMemory:
  mov    SortInfo.errorId, ERROR_NOT_ENOUGH_MEMORY
  ret

BucketSort_PURE ENDP


ENDIF