Given a permutation and a starting array, I need to calculate the number of permutations I need to apply to get the starting array again

Question

The code seems to work until it gets to work with ASCII numbers that are bigger than "16". I think it's a problem of how I'm accessing and calculating the indexes and the ASCII conversion.

I need to calculate the number of permutations and display each of the permutations to the user.



;-----------------------------------------------------------------
;    M  A  C  R  O
;-----------------------------------------------------------------

display macro xxx
    push ax
    push dx 
    mov dx, offset xxx
    mov ah, 9
    int 21h
    pop dx
    pop ax
endm     
;-----------------------------------------------------------------
; Definizione costanti
CR EQU 13                      ; carriage return
LF EQU 10                      ; line feed
DOLLAR EQU "$" 


;-----------------------------------------------------------------
;
PILA SEGMENT STACK 'STACK'     ; stack' segment definition
      DB      64 DUP('STACK')  ; stack is filled with the string "stack"
                               ; per identificarlo meglio in fase di debug
PILA ENDS                      

;-----------------------------------------------------------------
;

DATI SEGMENT PUBLIC 'DATA'    ; data segment definition

CRLF db CR,LF,DOLLAR  
msg_p  db "permutation:", DOLLAR
msg_n db "number:",DOLLAR  
r db "0", DOLLAR ; the number of permutations
                                                 
look_up  db "0", "4", "1", "5", "8", "12", "9", "13", "17", "21", "24" , "28", "25","29", "26", "30", "27","31","18", "22", "19", "23", "10", "14", "11", "15", "2", "6", "3", "7"      ; permutation law
     
string  db "0","1","2" ,"3","4","5","6","7","8","9","10", "11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31", DOLLAR             ; string Ill apply the permutation on
stringainitial db "0","1","2" ,"3","4","5","6","7","8","9","10", "11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31", DOLLAR      ; constant to check if the permutation changed the string back to the starting point
DATI ENDS  
 
;=================================================================

CSEG1 SEGMENT PUBLIC 'CODE'

MAIN proc far
        ASSUME CS:CSEG1,DS:DATI,SS:PILA,ES:NOTHING;      initialization

        MOV AX, DATI
        MOV DS, AX   
        
        XOR CX, CX  ; using CX for indexes
        xor ax, ax  ; ax as r counter
        MOV BX, OFFSET string   
        mov si, offset stringainitial 
        
        display string
        display CRLF
        
        cicle:  
             mov dx, offset look_up    ; I use the register multiple times, so Ill initialize it each cicle
             inc ax
             push dx
             push bx
             call permucalc  
             pop bx
             pop dx
             display msg_p     ; display string after permutation
             display string         
             display CRLF
             xor cx,cx
        checkifokay:  ; check if the string is the same as at the starting point
        add bx, cx         
        add si, cx  
        mov di, [bx]
        mov dx, [si]
        sub bx, cx
        sub si, cx
        cmp di,dx  
        jne cicle
        cmp cx, 32 
        je exit    
        inc cx
        jmp checkifokay
        
        
    exit:   
        mov bx, offset r
        sub [bx], "0" 
        add [bx], ax
        add [bx], "0" 
        display msg_n
        display r
        display CRLF

main endp 

;-----------------------------------------------------------------
;

permucalc proc
    push ax
    push bx
    push cx 
    push dx
    push si
    push bp
    mov  bp, sp
    mov bx, [bp+14] ; (stringa)
    mov si, [bp+16] ; (table) 
    xor cx,cx  
    cicleproc:
        cmp cx, 32
        je terminate
        add bx, cx ; need this to access the correct index 
        sub [bx], "0" ; to transform the number from ASCII
        mov ax, [bx]
        xor ah, ah
        add si, ax  
        mov dx, [si]  
        sub si, ax
        xor dh, dh
        mov [bx], dl
        sub bx, cx    ; need to go back to the starting offset
        inc cx 
        jmp cicleproc  
        
    terminate:
        pop bp
        pop si
        pop dx
        pop cx
        pop bx
        pop ax
        ret
endp

I tried isolating 8 bits and it seemed like it worked until the number got bigger than 16.

Why do you have strings of multi-digit numbers concatenated with no separator, instead of an array of 8-bit values in the first place? `db "9", "10"` assembles to the same bytes in memory as `db '9', '1', '0'`, so there's no unique way to find the number boundaries that exist in the source. Probably you want an array like `db 9, 10, 11` where each element is a 1-byte integer. (See [Displaying numbers with DOS](https://stackoverflow.com/q/45904075) for how to print them.) — Peter Cordes, Jun 16 '23 at 21:51
the problem with that solution is that I cant display the string and I really dont know how to convert numbers like 22 in ascii. Another solution I came up was defining a look_up table using lots of each individual elements initialized in the same spot, therefore I could move with the offset from one to another. — Babboboncia, Jun 18 '23 at 07:35

score 1 · Answer 1 · answered Jun 18 '23 at 19:24

The normal solution for this task would use byte-sized arrays with elements whose values are in the range [0,31]. You say that you don't know how to display these values afterwards. Well that's precisely what Displaying Numbers with DOS can teach you, as was suggested by @PeterCordes in a comment.

It is worth trying

We could adapt your approach and keep everything in ASCII. The trick will be to store every value in 2 characters, so "00", "01", ... , "31". Only for establishing an offset in the lookup table will we need to convert into an actual number:

; AX = {"00", "01", ... "31"}
sub  ax, "00"     ; From ASCII to number
xchg al, ah
aad               ; AH * 10 + AL -> AX=[0,31]

Because the strings now use 2 bytes per element, we also need to double this number before we can use it as an offset.

The result is a number

Currently, showing the number of permutations is flawed in two ways: you are loosing the mandatory $-character because you overwrite it with garbage, and you are forgetting that the number of permutations could be greater than 9. Next code shows how to do it for values not exceeding 99:

; AX is number of permutations [0,99] 
aam               ; AH = AL / 10, AL = AL MOD 10
add  ax, "00"
xchg al, ah
mov  [msg_r], ax

A hard-to-see bug

The lookup table has only 30 elements! Your program would be using garbage for the indexes 30 and 31.

Test program

Next program works perfectly. It reports 28 permutations. It does not use the required syntax for emu8086 but all the important stuff is there. You should be able to understand what it does and manage to adapt it to the necessary emu8086 syntax. I have appended the missing numbers "16" and "20" to the lookup table...

    ORG  256

    mov  dx, string
    mov  ah, 09h
    int  21h

    xor  bp, bp                   ; BP as r counter
 cicle:
    inc  bp
    mov  bx, look_up
    mov  si, string
    push bx
    push si
    call permucalc  
    pop  si
    pop  bx

    mov  dx, msg_p
    mov  ah, 09h
    int  21h
    mov  dx, si
    mov  ah, 09h
    int  21h

    mov  di, stringainitial 
    xor  bx, bx
checkifokay:  ; check if the string is the same as at the starting point
    mov  ax, [si+bx]
    cmp  ax, [di+bx]
    jne  cicle
    add  bx, 2
    cmp  bx, 64
    jb   checkifokay
   
exit:   
    mov  dx, msg_n
    mov  ah, 09h
    int  21h

    mov  ax, bp         ; [0,99] ?
    aam
    add  ax, "00"
    xchg al, ah
    mov  [msg_r], ax
    mov  dx, msg_r
    mov  ah, 09h
    int  21h

    mov  ax, 4C00h
    int  21h
; ------------------------------
permucalc:
    push ax bx cx si di bp
    mov  bp, sp
    mov  cx, 32
    mov  si, [bp+14]        ; (string)
    mov  bx, [bp+16]        ; (look_up) 
  cicleproc:
    mov  ax, [si]
    sub  ax, "00"           ; From ASCII to number
    xchg al, ah
    aad                     ; -> AX=[0,31]
    shl  ax, 1
    mov  di, ax
    mov  ax, [bx+di]  
    mov  [si], ax
    add  si, 2
    loop cicleproc  
    pop  bp di si cx bx ax
    ret
; ------------------------------  
msg_p:  db "permutation: $"
msg_n:  db "number: $"
msg_r:  db "00", 13, 10, '$'    ; the number of permutations
                                                 
; *** I appended "16" and "20" that were missing! ***
look_up:        db "00","04","01","05","08","12","09","13","17","21","24","28","25","29","26","30"
                db "27","31","18","22","19","23","10","14","11","15","02","06","03","07","16","20"
string:         db "00","01","02","03","04","05","06","07","08","09","10","11","12","13","14","15"
                db "16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31",  13,10,"$"
stringainitial: db "00","01","02","03","04","05","06","07","08","09","10","11","12","13","14","15"
                db "16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31",  13,10,"$"

Thanks a lot for the answer, you really helped me out here! Sorry for responding this late. :/ — Babboboncia, Jul 05 '23 at 19:57

Given a permutation and a starting array, I need to calculate the number of permutations I need to apply to get the starting array again

1 Answers1

It is worth trying

The result is a number

A hard-to-see bug

Test program