Assembly x86 TASM Sorting

Question

I am a begginer in Assembly language (TASM 86x) working on my first program assignment. It's not complicated in nature, however being new to this language I'm having a hard time figuring out a simple bubble sort.

So far I have only programed witch C++, hardest part overall is to grasp the syntax.

Task is to take any string (typed in by user) and rearrange it ascending by ASCII value (as in, if you type beda it should give abde)

I'm not certain about my output, but that should come after the sort is done I'm confused, because it just allows me to input my string and then quits to the command prompt. Can't trace where I've made a mistake where it points to the end of the code prematurely.

I would be very grateful if someone more experienced would take a look at my code and point me in the right direction and maybe even explain a thing or two to a newbie

.model small
.stack 100h

.data
request     db 'Enter symbols:', 0Dh, 0Ah, '$'  

    buffer      db 100, ?, 100 dup (0)

.code

start:
    MOV ax, @data                   
    MOV ds, ax                      

; request
    MOV ah, 09h
    MOV dx, offset request
    int 21h

; read string                    ;reading string to buffer
    MOV dx, offset buffer           
    MOV ah, 0Ah                     
    INT 21h                         
    MOV si, offset buffer           


    INC si                        ;going from buffer size to actual length 
                                  ;of the string
    MOV cl, [si]              ;string length - loop counter
    mov ch, [si]                  ;string length - loop counter
    mov bl, [si]                  ;bl will be used to reset inner loop counter 
    DEC cl                        ;correcting the values, since count goes
    dec ch                        ; from 0 to n-1 instead of 1 to n

    inc si                        ;moving to strings first byte


outer:                            ;outer loop

    dec ch                        ;decrease counter each pass
    jz ending                     ;when counter reaches 0 end program
    mov cl, bl                    ; reset inner loop counter value


inner:                            ;inner loop
    mov al,byte ptr[si]           ;assigning byte(sybol) to al
    mov ah, byte ptr[si+1]        ;assigning following byte(symbol) to ah
    cmp al,ah                     ;compare the two
    jle after_switch              ;if the latter's value is higher, no need to switch

problems with the switch, not sure if it will work right in assembly

    mov bh, al           ;main problem-switching values, tried a few different   
    mov al, ah           ;ways of doing it (will show them below), but to no avail
    mov ah, bh           ;using familiar C syntax

    jmp output           ;outputing the value

after_switch:         ;no switch needed

somewhere in the outer switch there is supposed to be jump to output, however i cant figure out the way to include it without messing up the rest of the sequence

    inc [si]              ;going to the next byte
    dec cl                ;decreasing inner loop counter
    jnz inner             ;back to the beginning of inner loop until counter reaches 0 (resetting in the outer loop)
    jmp outer             ;if counter reaches zero, get back to outer


output:             ;outputting value from the very first bit 
    mov ah, 2
    mov dl, al          ;which after switch is supposed to be stored in al
    int 21h
    jmp inner           ;returning to inner loop to run next course of comparison

ending:
    MOV ax, 4c00h               
    INT 21h                              
end start

Previously tried methods of switch in inner loop

    mov al,[si+1]
    mov byte ptr[si+1],[si]
    mov byte ptr[si], al

returns illegal memory reference error, but this question has already been answered on this board in the past, found it.

tried the same method, but utilizing the dx:di register

    mov al, byte ptr[si+1]
    mov dx:[di], [si]
    mov byte ptr[si+1], dx:[di]
    mov byte ptr[si], al

returns illegal override register error, couldn't find anything on it

Answer 1

Logical error

mov al, byte ptr[si+1]
mov dx:[di], [si]             <<-- there is no dx:[di] register.
mov byte ptr[si+1], dx:[di]   <<-- memory to memory move not allowed.
mov byte ptr[si], al          <<-- `byte ptr` is superflous, because `al` is already byte sized.

You can use a segment register here, but because you're only working with the ds segment there's no need for that.

So this would be valid:

mov DS:[di],si   <-- ds segment (but DS is already the default)

Note that a memory to memory move is not allowed, data has to either come from a constant:

mov [di],1000    <-- direct assignment using a constant

Or has to pass through a register

mov ax,[di]
mov [si],ax      <--- memory to memory must be a 2 step process.

Remember [reg] is memory; reg is a register
Another error is here:

inc [si] <<-- error, increases some memory location, not `si` the pointer.
dec cl                ;decreasing inner loop counter
jnz inner             ;back to the beginning of inner loop until counter reaches 0 (resetting in the outer loop)
jmp outer             ;if counter reaches zero, get back to outer

This should be:

inc si                ;next char in the string
dec cl                ;decreasing inner loop counter
jnz inner             ;back to the beginning of inner loop until counter reaches 0 (resetting in the outer loop)
jmp outer             ;if counter reaches zero, get back to outer

Simplification
Flipping two values around does not require movs. Replace this code:

mov bh, al           ;main problem-switching values, tried a few different   
mov al, ah           ;ways of doing it (will show them below), but to no avail
mov ah, bh           ;using familiar C syntax

With this much simpler variant, saving a register in the process:

xchg ah, al           ;flip chars around

After you're done flipping al and ah around you need to write them back to memory, otherwise all that work is for nothing.

xchg ah, al           ;flip chars around
mov [si],al           ;save flipped values
mov [si+1],ah         

Reading past the end of the string
In this snippet you've got the correct idea, but because you're letting [si] run all the way to the end of the string you're reading 1 byte too many.

inner:                            ;inner loop
  mov al,byte ptr[si]           ;<<-- both are correct, but [si+1] will read
  mov ah, byte ptr[si+1]        ;<<-- past the end of the string at the last byte  

So you need to change this section:

DEC cl                     ;correcting the values, since count goes
dec ch                     ; from 0 to n-1 instead of 1 to n

To this:

sub bl,2                   ;if bl is used to reset inner loop counter it must be
                           ;adjusted as well.
;sub cl,2                  ;inner loop from 0 to n-2
mov cl,bl                  ;bl=cl, so a mov makes more sense
dec ch                     ;outer loop from 0 to n-1 instead of 1 to n

Finally efficiency tips
Never read from memory if you don't have to. Change this code:

MOV si, offset buffer           
INC si                        ;going from buffer size to actual length 
                              ;of the string
MOV cl, [si]              ;string length - loop counter
mov ch, [si]                  ;string length - loop counter
mov bl, [si]                  ;bl will be used to reset inner loop counter

To this:

MOV si, offset buffer+1       ;start at length byte of the string    
MOV cl, [si]                  ;string length - loop counter
mov ch, cl                    ;string length - loop counter
mov bl, cl                    ;bl will be used to reset inner loop counter

There are more speed optimizations that can be done but I don't want to overcomplicate things.

Answer 2

For a speed optimization the xchg-instruction is not a very fast instruction on all x86. So i prefer to use a third register for switching values instead and replacing the xchg-instruction with it, because simple mov-instructions are better pairable with other simple instruction in the prefetch input queue of the instruction pipelines and the CPU can translate simple instructions easier to micro operations(μops).

With consideration of the number of stages in the prefetch input queue of each pipeline, where each instruction will be pass through like fetching, decoding and storing, we can place some other instructions (that have no dependencies to the others) between our mov-instructions for switching the values, for to prevent stalls while executing.

Examples of placing instructions for to prevent stalls:

(Note: Not all x86-CPUs use exactly the same number of executing stages in their pipelines, but the schematic is similar.)

Bad placements of instructions results a stall:

mov eax,value1
add eax,value2 ; reading after writing the same register = results a stall
mov ebx,value3
add ebx,value4 ; stall
mov ecx,value5
add ecx,value6 ; stall
mov edx,value7
add edx,value8 ; stall
mov esi,value9
add esi,value10 ; stall
mov edi,value11
add edi,value12 ; stall
mov ebp,value13
add ebp,value14 ; stall

Better placements of instructions:

mov eax,value1 ; first instruction
mov ebx,value3 ; second instruction
mov ecx,value5 ; third ...
mov edx,value7 ; ...
mov esi,value9
mov edi,value11
mov ebp,value13
; no stall, because the execution progress of the first instruction is fully complete
add eax,value2
add ebx,value4 ; ... of the second instruction is fully complete
add ecx,value6 ; ... of the third instruction is fully complete
add edx,value8 ; ...
add esi,value10
add edi,value12
add ebp,value14

Dirk

Answer 3

If we want to write an immediate value to a memory location, then we need to specify how many bytes we want to access, only one byte, a word, or a dword.

mov word [di],1000    <-- direct assignment using a constant (immediate value)

Dirk