I am currently learning 8086 programming and this one was demonstrated in our lab on a 8086 kit. The following code sorts sequence of numbers to ascending order:
mov si, 2000
mov cl, [si]
dec cl
loop1: mov si, 2000
mov ch, [si]
dec ch
inc si
loop2: mov al, [si]
inc si
cmp al, [si]
jc loop3
xchg al, [si]
dec si
xchg di, [si]
inc si
loop3: dec ch
jnz loop2
dec cl
jnz loop1
int a5
How exactly does this function?
Say we have an array of N numbers d1, d2, ..., dN as follows:
Address |2000|2001|2002|2003|...|2000+N|...|
Data |N |d1 |d2 |d3 |...|dN |...|
|si |
cl <-- [si]
{cl:N --> N-1}
LOOP 1:
ch <-- [si]
{ch:N --> N-1}
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data |N |d1 |d2 |d3 |...|dN |...|
|si |
LOOP 2:
al <-- [si] = d1
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data |N |d1 |d2 |d3 |...|dN |...|
|si |
Compare [si] = d2 with al = d1.
If d1 > d2, jump to LOOP 3,
else d1 <= d2 and exchange d1 in al with d2 at si = 2002.
al = d2
Address |2000|2001|2002|2003|...|2000+N|...|
Data |N |d1 |d1 |d3 |...|dN |...|
|si |
si --> si - 1
[di] = d1 (at 2001)
LOOP 3:
{ch:N-1 --> N-2}
If ch is not zero then jump to LOOP 2.
al <-- [si] = d2 and so on.
At this point I feel like I am losing track of how the code really works. So, how does this work? Am I missing something? The example demonstrated was:
Address |2000|2001|2002|2003|2004|2005|...|
Input |5 |04 |03 |01 |00 |02 |...|
Output |5 |00 |01 |02 |03 |04 |...|
xchg di, [si]
. It should be clear that the code does not use the di
register anywhere else, so this particular exchange instruction is useless. What would make sense is xchg al, [si]
, but even better would be a simple mov [si], al
.At this point I feel like I am losing track of how the code really works. So, how does this work? Am I missing something?
You are mis-interpreting the conditional jump in:
cmp al, [si] <<<< AL = d1, [si], d2 jc loop3
when you state:
If d1 > d2, jump to LOOP 3, else d1 <= d2 and exchange d1 in al with d2 at si = 2002.
The jc
instruction should have been written as jb
that has exactly the same encoding but that better conveys what it does: "If AL is below the byte at [si] then jump to LOOP3". So if d1 < d2
which is just the opposite of what you stated ("if d1 > d2").
Incidently, LOOP3 is a really bad name for this label! A more suitable name could be SKIP.
I would be so grateful if you could post a better-version of this code that is easy to understand.
mov si, 2000 ; Where the count resides
mov cl, [si] ; CL is number of elements
dec cl ; CL is number of iterations outer loop
Outer: mov si, 2001 ; Where the first element resides
mov ch, cl ; Ever smaller number of iterations inner loop (*)
Inner: mov al, [si]
inc si
cmp al, [si] ; Compare two adjacent elements
jb Skip ; Skip the Swap if ordered fine already
Swap: xchg al, [si]
mov [si-1], al
Skip: dec ch
jnz Inner ; Iterate on the Inner loop
dec cl
jnz Outer ; Iterate on the Outer loop
(*) This is the magic that makes bubble sort somewhat acceptable as a sorting method for small arrays!
More about writing a bubble sort code can be found at Sort 10 integer numbers read from keyboard and display in ascending order.