1

I am trying to convert my C++ code to MASM code. I got trouble with 2D arrays.

Please help me!

Problem: Find the longest common substrings

My C++ code:

#include<stdio.h>
#include<string.h>
char s[20],t[20];
int b[20][20];
int n,m;
void substr(int i,int j) {
    if (i&&j) {
        if (b[i][j]==1) {
            substr(i-1,j-1);
            printf ("%c",s[i]);
        } else if (b[i][j]==2)
            substr(i-1,j);
        else substr(i,j-1);
    }
}
int main() {
    int f[20][20];
    gets(s+1);
    gets(t+1);
    m=strlen(s+1);
    n=strlen(t+1);
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
            if (s[i]==t[j]) {
                f[i][j]=f[i-1][j-1]+1;
                b[i][j]=1;
            } else {
                if (f[i-1][j]>=f[i][j-1]) {
                    f[i][j]=f[i-1][j];
                    b[i][j]=2;
                } else {
                    f[i][j]=f[i][j-1];
                    b[i][j]=3;
                }
            }
    printf("\n::: OUTPUT :::\n");
    if(n==0){
        printf("There is no common substring of S and T!");
    } else {
        printf("The longest substring: \"");
        substr(m,n);
        printf("\".");
    }
    return 0;
}

And my ASM code:

    .model small
; input s, m is lenght of s
    input macro s,m 
        push ax
        push dx                                  
        mov ah, 0Ah 
        lea dx, s
        int 21h                 
        mov al, s + 1 
        xor ah, ah
        mov m, ax
        pop ax
        pop dx     
    endM 
   
    substr macro i,j
        push ax
        push bx
        push cx
    if_s:
    loopij:
        cmp i,0
        jne halt
        cmp j,0
        jne halt
        if_2s:
            cmp b[i][j],1 
            jne else_if
            dec i
            dec j
            substr(i,j)
            lea dx, s[i]
            mov ah, 9
            int 21h
            jmp halt
         else_ifs:
             cmp b[i][j],2
             jne else
             dec i
             substr(i,j)
             jmp halt
          elses:          
             dec j
             substr(i,j)
             jump halt
        jmp loopij 
        ret       
     halt:
     pop ax
     pop bx
     pop cx
endm
.stack 100h
.data 
    newline db 10,13, "$"
    s db  255, ?, 255 dup(0)
    t db  255, ?, 255 dup(0)
    m dw ?
    n dw ?
    i dw ?
    j dw ?
    arr1 db i dup(0)
         db j dup (0)
    arr2 db i dup (0)
         db j dup (0)
.code  
main proc        
    mov  ax,@data
    mov  ds,ax

    input s, m
    call newln
    input t, n
    call newln

    xor ax, ax
    inc ax
    mov i, 2
loopi:
    add ax, m
    cmp i, ax
    ja outloopi
    mov j, 2
loopj:
    mov ax, 1
    add ax, n 
    cmp j, ax
    ja outloopj
    if_:
        mov dx, s[i]
        cmp dx, t[j]
        jne else
        mov cx, f[i-1][j-1]
        mov f[i-1][j-1], cx
        mov b[i][j],1
    else:
        else_if:
            cmp f[i-1][j], f[i][j-1]
            jb else_else
            mov cx,f[i-1][j] 
            mov f[i][j], cx
            mov b[i][j],2
        else_else:
            mov cx,f[i][j-1] 
            mov f[i][j], cx                
            mov b[i][j],3
    jmp loopj
outloopj:
    jmp loopi 
outloopi:       
    substr m, n

    mov  ax,4ch
    int  21h  
main endp

newln proc
    mov ah, 9
    lea dx, newline
    int 21h
    ret
newln endp

end main

How to declare a 2D array in ASM?

How to work with 2D arrays in ASM?

Can I convert 2D array into single dimension array in this case?

Thanks a lot!

hieveryone
  • 11
  • 1
  • 3
    Memory is linear (i.e. 1d) so we always have to convert 2d or higher into 1d. – Erik Eidt Jul 07 '21 at 03:43
  • 2
    @ErikEidt: If you use a 2-register addressing mode with a static array, you *can* have one be the byte offset to the start of the row, and the other be the byte offset within a row. But yeah you should be thinking in terms of linear bytes, even if you use separate registers for parts of an addressing mode. – Peter Cordes Jul 07 '21 at 04:31

1 Answers1

2

How to declare a 2D array in ASM?
How to work with 2D arrays in ASM?

Let's take the example of a 3 X 4 matrix, that's 3 rows by 4 columns.

(0,0) (0,1) (0,2) (0,3)    <- 1st row
(1,0) (1,1) (1,2) (1,3)    <- 2nd row
(2,0) (2,1) (2,2) (2,3)    <- 3rd row

  ^     ^     ^     ^
 1st   2nd   3rd   4th
 col   col   col   col

Assuming that the elements are to be byte-sized, all it takes is writing:

MyArray db 3*4 dup (0)

This sets aside a 12-byte block of memory. The special nature of it being a 2-dimensional array purely comes from how you, the programmer, will interact with it and interpret its content.

Looking at the matrix in row-order:

| MyArray
|
<        row 0        > <        row 1        > <        row 2        >
----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
(0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)

Below is how you address any element of the array.

OffsetInTheArray = (RowIndex * NumberOfColumns + ColumnIndex) * BytesPerElement

The assignment MyArray[Row][Col] = 1 in emu8086 style:

mov     ax, Cols      ; CONST, (Cols equ ...)
mul     Row
add     ax, Col
;;;shl     ax, 1      ; Only for word-sized elements
mov     bx, ax
mov     byte ptr MyArray[bx], 1

Looking at the matrix in column-order:

| MyArray
|
<     col 0     > <     col 1     > <     col 2     > <     col 3     >
----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
(0,0) (1,0) (2,0) (0,1) (1,1) (2,1) (0,2) (1,2) (2,2) (0,3) (1,3) (2,3)

Below is how you address any element of the array.

OffsetInTheArray = (ColumnIndex * NumberOfRows + RowIndex) * BytesPerElement

The assignment MyArray[Row][Col] = 1 in emu8086 style:

mov     ax, Rows      ; CONST, (Rows equ ...)
mul     Col
add     ax, Row
;;;shl     ax, 1      ; Only for word-sized elements
mov     bx, ax
mov     byte ptr MyArray[bx], 1

Unrelated to the question concerning the 2-D arrays, but very important nonetheless.

input macro s,m 
  push ax
  push dx                                  
  ...
  pop ax
  pop dx
endM

You must restore these registers in reverse order! The stack is a last-in-first-out (LIFO) structure:

push    ax
push    dx
...
pop     dx
pop     ax

substr macro i,j
  push ax
  push bx
  push cx
  ...
  pop ax
  pop bx
  pop cx
endm

Here also you must restore these registers in reverse order. And just as important, seeing that substr is meant to be a recursive procedure, you should not turn this into a macro.

cmp i,0
jne halt
cmp j,0
jne halt

This snippet is not a correct translation of if (i&&j). It's quite the opposite:

cmp     i, 0
je      halt
cmp     j, 0
je      halt

mov  ax,4ch
int  21h

The DOS function number goes into the AH register. Your instruction places it into AL.

mov     ax, 4C00h   ; DOS.TerminateWithReturnCode
int     21h

lea dx, s[i]
mov ah, 9
int 21h

This will not work like in printf ("%c",s[i]). The DOS.PrintString function 09h expects DX to point at a $-terminated string. Another DOS function can do it though:

mov     bx, i
mov     dl, s[bx+2] 
mov     ah, 02h     ; DOS.PrintCharacter
int     21h

In case you're wondering about the +2, well you have obtained the string s from using the DOS.BufferedInput function 0Ah which has returned the characters at offset 2 from the buffer that you named s. You will have to watch out for this at numerous places.

Next is a quick solution to the problem:

  db      255, 0
s db      255 dup (0)
  ...
  lea     dx, s-2
  mov     ah, 0Ah   ; DOS.BufferedInput
  int     21h

There are additional problems in this code but I think that with all of the above you should be able to write a first attempt. And with that code you can always come back...

Sep Roland
  • 33,889
  • 7
  • 43
  • 76