; 
; Distribution Counting --> Bucket Sort
;
; Copyright (c) 1998 by Michael Neumann
;
; programmed by Michael Neumann (neumann@s-direktnet.de)
; for the 3D-engine, for the facesorting
;
; the algorithm which is used, is very easy, every byte of the dword
; is sorted and at the end the whole dword is sorted!!! ;)
;
; data structure to sort, is as follows:
;       DWORD key(z_value)              ; must be at offset 0
;       DWORD value(index in array)     ; must be at offset 4
;
; for WATCOM C++ V.11.0 // tested
;

public bucketSort_

.data

count           DD 256 DUP(?)
sort            DD ?
buffer          DD ?
anz_values      DD ?
bytenum         DD ?


.code


;
; EAX = sort(array)
; EDX = buffer(array)
; EBX = anz_values
;
; The array is sorted inplace
;
bucketSort_ proc near
        
        pushad                                  ; save all registers        
        mov [sort],eax                          ; copy into variables
        mov [buffer],edx                        ;         "
        mov [anz_values],ebx                    ;         "
        
        xor eax,eax
        mov [bytenum],eax                       ; set bytenum to 0
        
        
        ;
        ; the bytenum_loop, sorts for every byte (= 4 times)
        ;
        @@bytenum_loop:
        
                ;
                ; first, the count-array must be set to 0
                ;
                mov ecx,256
                xor eax,eax
                mov esi,OFFSET count
                @@count_zero:
                        mov [esi],eax
                        add esi,4
                        dec ecx
                jnz @@count_zero
                
                
                
                ;
                ; Häufigkeiten will be calculated
                ;             
                mov ecx,[anz_values]
                mov ebx,[sort]
                add ebx,[bytenum]
                xor eax,eax                             ; is not necessary, because before it eax is 0
                mov esi,OFFSET count
        
                @@calc_haufig:        
                        mov al,[ebx]                    ; loads the byte
                        inc dword ptr[esi+eax*4]        ; incs at count[al]
                        add ebx,8                       ; skips to the next data-struc
                        dec ecx
                jnz @@calc_haufig
                
                
                

                ;
                ; now the haufigkeiten are added to get the positions
                ;
                xor ecx,ecx
                mov cl,1
                mov esi,OFFSET count                    ; is not necessar because has before the same value
                @@add_haufig:
                        mov eax,[count-4+ecx*4]
                        add [esi+ecx*4],eax
                        inc cl                          ; if 256 then == 0, so it goes maximal till 255
                jnz @@add_haufig
       
       
              
       
                ; 
                ; now the real sorting is done
                ;                                
                mov ecx,[anz_values]                    ;
                dec ecx                                 ; number of loops
                                
                mov ebx,ecx                             ; calculate
                shl ebx,3                               ; the adress of sort[i]
                add ebx,[sort]                          ; ebx is the adress of sort[i]
                mov esi,ebx
                add esi,[bytenum]                       ; esi is the adress of sort[i]+bytenum
                mov edi,[buffer]
                
                @@sort_loop:
                        xor eax,eax
                        mov al,[esi]                        
                        sub esi,8
                        
                        dec dword ptr [count+eax*4]     ; count decrease
                        mov eax,[count+eax*4]
                                                
                        ; copy DATA_STRUC                                                
                        mov edx,[ebx]                   ; sort[i]
                        mov [edi+eax*8],edx
                        mov edx,[ebx+4]                 ; sort[i] next dword in DATA_STRUC
                        mov [4+edi+eax*8],edx
                                                
                        sub ebx,8                       ; sort[i] <--  i--
                                                
                        dec ecx
                jns @@sort_loop
                
                
                
                mov eax,[sort]
                mov ebx,[buffer]
                mov [sort],ebx
                mov [buffer],eax
        

                inc [bytenum]
                mov eax,3
                cmp [bytenum],eax
        jbe @@bytenum_loop
        
        
        popad        
        ret               
        
bucketSort_ endp


end