Build using merge sort the ordered string of bytes that contain all characters from s1 and s2

Question

Being given two alphabetical ordered strings of characters, s1 and s2, build using merge sort the ordered string of bytes that contain all characters from s1 and s2.

my take on this was like this:


global start        

extern exit         
import exit msvcrt.dll
segment data use32 class=data
    ; ...
    s1 db 'cdefrstwxyz' ; first string in alphabetical order
    len_s1 equ ($ - s1) ; length of first string
    s2 db 'bcdfhij' ; second string in alphabetical order
    len_s2 equ ($ - s2) ; length of second string
    rez times len_s1 + len_s2 db 0
    str_reminder dd 0

segment code use32 class=code
    start:
        cld ; set direction flag to 0 to go from left to right
        
        mov ESI, s1 ; s1 in source
        mov EDI, s2 ; s2 in destination
       
        mov ECX, len_s1 + len_s2 ; the max length (len_s1 + len_s2)
        
        mov EBX, 0 ; for s2, how many elements we went through
        mov EAX, 0 ; for s1, how many elements we went through
        mov EDX, 0 ; for indexing in the result string
        
        repeat_this:
            cmpsb ; comparing the elements of the two strings
            
            jb smaller_s1 ; s1[pos] < s2[pos]
            jg larger_s1 ; s1[pos] > s2[pos]
            je equals; s1[pos] = s2[pos]
            
            smaller_s1:
                dec ESI ; decrementing ESI (s1)
                dec EDI ; decrementing EDI (s2)
                
                mov [str_reminder], EAX ; save the value of EAX
                
                lodsb ; put in AL the current value of ESI
                
                mov [rez + EDX], AL ; put in the result on the position EDX the value from AL
                mov EAX, [str_reminder] ; reset the value from EAX
                
                inc EDX ; incrementing length of the result
                inc EAX ; incrementing EAX
                
                cmp EAX, len_s1 ; if we are done with the elements in s1
                
                jge sf_prg ; jump to sf_prog
                loop repeat_this ; repeating the loop
                jecxz sf_prg ; if ecx = 00000000, we jump to sf_prog
            
            larger_s1:
                dec EDI ; decrementing EDI
                dec ESI ; decrementing ESI
                
                mov [str_reminder], EAX ; save the value of EAX
                mov AL, [EDI]
                
                mov [rez + EDX], AL
                mov EAX, [str_reminder]
                
                inc EDI ; incrementing EAX (the index where we were in s1)
                inc EDX ; incrementing EAX (the index where we were in rez)
                inc EBX ; incrementing EAX (the index where we were in s2)
                
                cmp EBX, len_s2
                
                jge sf_prg ; jump to sf_prog
                loop repeat_this ; repeating the loop
                jecxz sf_prg ; if ebx = 00000000, we jump to sf_prog
            
            equals:
                dec ESI
                
                mov [str_reminder], EAX ; save the value of EAX (the index where we were in s1)
                
                lodsb
                mov [rez + EDX], AL
                mov EAX, [str_reminder]
                
                inc EDX ; incrementing length of the result
                inc EBX ; incrementing EBX
                
                cmp EBX, len_s2 ; if we are done with the elements in s2
                
                jge sf_prg
                
                inc EAX ; incrementing EAX (the index where we were in s1)
                
                cmp EAX, len_s1 ; if we are done with the elements in s2
                
                jge sf_prg ; jump to sf_prog
                loop repeat_this ; repeating the loop
                jecxz sf_prg ; if eax = 00000000, we jump to sf_prog
        sf_prg:
        
        cmp EAX, len_s1 ; comparing EAX with the length of s1, if EAX = len_s1 then we are done with the terms of s1 
        je ebx_bigger; if we have to add terms from s2
        jne ebx_smaller ; if EAX is not equal to len_s1 we are done with the terms of s2
        
        ebx_bigger: ; the remaining terms of s1
            mov ECX, len_s2
            sbb ECX, EBX
            repeat_:
                mov AL, [EDI]
                mov [rez + EDX], AL
                inc EDX
                inc EDI
            loop repeat_
            jmp end_prg
        
        ebx_smaller:
            mov ECX, len_s1
            sub ECX, EAX
            repeat__:
                lodsb
                mov [rez + EDX], AL
                inc EDX
            loop repeat__
        
        
        end_prg:
        push    dword 0      
        call    [exit]

how can I change it so that I only use LODSB, STOSB, MOVSB, SCASB or CMPSB?

my second attempt

; plan:

set esi to the first character of the first string.
set edi to the destination memory
clear the direction flag
read one byte using lodsb
write the same byte using the stosb instruction
if the al register is not zero -> continue with 4 (loop)
decrement edi
set esi to the first character of the second string
perform the loop (steps 4 - 6) again

bits 32

global start        

extern exit         
import exit msvcrt.dll
segment data use32 class=data
    ; ...
    s1 db 'cdefrstwxyz' ; first string in alphabetical order
    len_s1 equ ($ - s1) ; length of first string
    s2 db 'bcdfhij' ; second string in alphabetical order
    len_s2 equ ($ - s2) ; length of second string
    reult times len_s1 + len_s2 db 0

segment code use32 class=code
    start:
        ; plan:
        ; 1. set esi to the first character of the first string.
        ; 2. set edi to the destination memory
        ; 3. clear the direction flag
        ; 4. read one byte using lodsb 
        ; 5. write the same byte using the stosb instruction
        ; 6. if the al register is not zero -> continue with 4 (loop)
        ; 7. decrement edi
        ; 8. set esi to the first character of the second string
        ; 9. perform the loop (steps 4 - 6) again
        
        mov esi, s1 ; the first character of the first string (?)
        mov edi, result  ; set edi to the destination memory
        
        cld ; set direction flag to 0 to go from left to right
        
        repeat_comparing:
            lodsb  ; read one byte
            stosb 
            cmpsb ; if the al register is not 0
            
            loop repeat_comparing
            
        dec edi
        mov esi, s2 ; the first character of the second string (?)
            
        repeat_comparing:
            lodsb  ; read one byte
            stosb 
            cmpsb ; if the al register is not 0
            
            loop repeat_comparing
            
        push    dword 0      
        call    [exit]

I am afraid it'll not be possible to implement this functionality using just these instructions. Please elaborate your restrictions and what specifically you don't know how to do. — fuz, Nov 16 '20 at 19:56
@fuz well insead of let's say mov [rez + edx], how can I use stosb? and inseaad of inc / dec esi / esi can I use lodsb? — just1frustredstudent, Nov 16 '20 at 19:59
Read the instruction set refernece on these instructions, then use your imagination. — fuz, Nov 16 '20 at 20:02
Then post what exactly you tried, what you expected to happen and what happened instead. I can help you explain what mistakes you make, but I can't understand it for you. — fuz, Nov 16 '20 at 20:11
Cross-post: https://codereview.stackexchange.com/questions/252208/build-using-merge-sort-the-ordered-string-of-bytes-that-contain-all-characters-f — Arkadiusz Drabczyk, Nov 16 '20 at 20:49
The `repeat_comparing` part won't work as is. `cmpsb` increments `esi` and `edi` as it goes through the string, so that won't work. A normal `cmp` seems to be more appropriate for your usage. — fuz, Nov 16 '20 at 20:50

Jester · Answer 1 · 2020-11-16T21:48:01.907

3

My plan would be:

CMPSB to compare the current inputs
If you need to copy from the second string swap the input pointers (XCHG ESI, EDI)
Back up the read pointers by STD; CMPSB; CLD
Put the output pointer into EDI (e.g. XCHG EDI, EDX)
Copy the character using MOVSB
Put the input pointer back
If you swapped in step 2 swap again
Loop while there are characters remaining in both strings
Copy anything left over

edited Nov 16 '20 at 21:48

answered Nov 16 '20 at 21:04

Jester

56,577
4
81
125

one issue, I'm not familiar with xchg, and can't use it for this. – just1frustredstudent Nov 16 '20 at 21:07
2

Well, use whatever you are allowed. You can mov to a temporary register, e.g. `ebx`. – Jester Nov 16 '20 at 21:08
@just1frustredstudent: If you're willing to learn / use x86's funky "string" instructions and [the slow `loop` instruction](https://stackoverflow.com/questions/35742570/why-is-the-loop-instruction-slow-couldnt-intel-have-implemented-it-efficiently), you should definitely check out `xchg` in Intel's manual: https://www.felixcloutier.com/x86/xchg. (It's also very useful for code-size optimization, e.g. `xchg eax, reg` is only 1 byte. IDK if that's why you're using the string instructions; it would probably be more efficient and likely simpler to just load characters into registers.) – Peter Cordes Nov 16 '20 at 21:41

Build using merge sort the ordered string of bytes that contain all characters from s1 and s2

1 Answers1