Traversing a 2-d array

Question

I'm having trouble understanding how to traverse a 2-d array in x86 assembly language. I am missing a bit of understanding. This is what I have so far.

The issue is the lines with //offset and //moving through array For the //offset line the error I am getting is "non constant expression in second operand" and also "ebx: illegal register in second operand"

For the next line I get the error "edx: illegal register in second operand"

    mov esi, dim
    mul esi
    mov eax, 0 // row index
    mov ebx, 0 // column index
    mov ecx, dim
StartFor:
    cmp ecx, esi
    jge EndFor
    lea edi, image;
    mov edx, [eax *dim + ebx] // offset
    mov dl, byte ptr [edi + esi*edx] // moving through array
    mov edx, edi
    and edx, 0x80
    cmp edx, 0x00
    jne OverThreshold
    mov edx, 0xFF


OverThreshold:
    mov edx, 0x0

What does `need to fix this` mean? Can you explain what the actual problem is? — Blorgbeard, May 10 '16 at 03:22
That was just something unrelated. I edited my post to better explain my issue. Sorry, new poster — user6313136, May 10 '16 at 03:26
OK. I don't think you can do that much math in an offset. IIRC, you're limited to [REGISTER + CONSTANT_OFFSET]. You may have to calculate the offset manually (ADD and MUL), or just keep track of it as you go. — Blorgbeard, May 10 '16 at 03:39
Ah, [here](http://stackoverflow.com/questions/13329611/x86-x64-add-displacement-addressing) we go - you can multiply by a constant, but you can't multiply two registers. — Blorgbeard, May 10 '16 at 03:41
@Blorgbeard Okay I changed it mov edx, eax*dim(number of row/cols as parameter) + ebx. Still getting the same errors — user6313136, May 10 '16 at 03:48

score 1 · Accepted Answer · edited May 23 '17 at 12:15

See x86 tag wiki, including the list of addressing modes.

You can scale an index register by a constant, but you can't multiply two registers in an addressing mode. You'll have to do that yourself (e.g. with imul edx, esi, if the number of columns isn't a compile time constant. If it's a power-of-2 constant, you can shift, or even use a scaled addressing mode like [reg + reg*8]).

re: edit: *dim should work if dim is defined with something like dim equ 8. If it's a memory location holding a value, then of course it's not going to work. The scale factor can be 1, 2, 4, or 8. (The machine code format has room for a 2-bit shift count, which is why the options are limited.)

I'd also recommend loading with movzx to zero-extend a byte into edx, instead of only writing dl (the low byte). Actually nvm, your code doesn't need that. In fact, you overwrite the value you loaded with edi. I assume that's a bug.

You can replace

imul  edx, esi
mov dl, byte ptr [edi + edx]   ; note the different addressing mode
mov edx, edi                   ; bug?  throw away the value you just loaded
and edx, 0x80                  ; AND already sets flags according to the result
cmp edx, 0x00                  ; so this is redundant
jne OverThreshold

with

imul   edx, esi
test   0x80, byte ptr [edi + edx]   ; AND, discard the result and set flags.
jnz

Of course, instead of multiplying inside the inner loop, you can just add the columns in the outer loop. This is called Strength Reduction. So you do p+=1 along each row, and p+=cols to go from row to row. Or if you don't need to care about rows and columns, you can just iterate over the flat memory of the 2D array.

Ruslan Osmanov · Answer 2 · 2016-05-10T14:26:16.827

A 2-dimensional array is just an interpretation of a sequence of bytes. You'll have to choose in which order to store the items. For example, you might choose "row-major order".

I've written a demo where a buffer is filled with a sequence of numbers. Then the sequence is interpreted as single- and two-dimensional array.

tx86.s

%define ITEM_SIZE 4

    extern printf

    section .bss

cols:   equ     3
rows:   equ     4
buf:    resd    cols * rows
c:      resd    1
r:      resd    1

    section .data

fmt:        db "%-4d", 0          ; fmt string, '0'
fmt_nl:     db 10, 0              ; "\n", '0'

    section .text           ; Code section.

    global main

main:
    push    ebp
    mov     ebp, esp

    ; fill buf
    mov     ecx, cols * rows - 1
    mov     [buf + ITEM_SIZE], ecx
.fill_buf:
    mov     [buf + ecx * ITEM_SIZE], ecx
    dec     ecx
    jnz     .fill_buf

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; buf as 1-dimensional array
; buf[c] = [buf + c * ITEM_SIZE]
    xor     ecx, ecx
    mov     [c], ecx
.lp1d:
    mov     ecx, [c]

    push    dword [buf + ecx * ITEM_SIZE]
    push    dword fmt
    call    printf

    mov     ecx, [c]
    inc     ecx
    mov     [c], ecx
    cmp     ecx, cols * rows
    jl      .lp1d

    ; print new line
    push    dword fmt_nl
    call    printf

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; buf as 2-dimensional array
; buf[r][c] = [buf + (r * cols + c) * ITEM_SIZE]
    xor     ecx, ecx
    mov     [r], ecx
.lp1:
    xor     ecx, ecx
    mov     [c], ecx
.lp2:
    ; calculate address
    mov     eax, [r]
    mov     edx, cols
    mul     edx         ; eax = r * cols
    add     eax, [c]    ; eax = r * cols + c

    ; print buf[r][c]
    push    dword [buf + eax * ITEM_SIZE]
    push    dword fmt
    call    printf

    ; next column
    mov     ecx, [c]
    inc     ecx
    mov     [c], ecx
    cmp     ecx, cols
    jl      .lp2

    ; print new line
    push    dword fmt_nl
    call    printf

    ; next row
    mov     ecx, [r]
    inc     ecx
    mov     [r], ecx
    cmp     ecx, rows
    jl      .lp1


    mov     esp, ebp
    pop     ebp         ; restore stack

    xor     eax, eax    ; normal exit code
    ret

Buidling(on Linux)

nasm -f elf32 -l tx86.lst tx86.s
gcc -Wall -g -O0 -m32 -o tx86 tx86.o

Running

./tx86
0   1   2   3   4   5   6   7   8   9   10  11  
0   1   2   
3   4   5   
6   7   8   
9   10  11

Traversing a 2-d array

2 Answers2