Walking the Matrix in short steps

[frktons]

Code Select Expand


.data
MyMatrix0   DB  0,1,2,3,4,5,6
MyMatrix1   DB  0,1,2,3,4,5,6
MyMatrix2   DB  0,1,2,3,4,5,6
MyMatrix3   DB  0,1,2,3,4,5,6
MyMatrix4   DB  0,1,2,3,4,5,6
MyMatrix5   DB  0,1,2,3,4,5,6
MyMatrix6   DB  0,1,2,3,4,5,6

Pivot       DD  MyMatrix3
.code
start:
add  Pivot, 3
----
end start


My problem is: How to reach the single bytes, using
the shortest path, in bits or bytes [better bits]?
Pivot points to the center of the Matrix, to make it possible
to reach each other position with the minimum number of
moves and bits. Using 8 directions there are three steps
as maximum required, less if the point to reach is not
on the border.
How to code the required steps with the smallest number
of bits?

As an example I have to reach in sequence:
Row 1, Col 1
Row 2, Col 6
Row 3, Col 1
Row 5, Col 5
Row 0, Col 0
Row 6, Col 4

Thanks for your help.

Frank

[jj2007]

It depends. If you have a fixed number of columns, imul eax, rowmem32, colimm8 is short and fast.

[dedndave]

if the sequence is fixed, then you can direct address
let the assembler do some calculations for you to make it easy to read
you can make a set of equates to make it really easy to read

Code Select Expand

ROW_SIZE EQU 7

ROW_0    EQU 0*ROW_SIZE
ROW_1    EQU 1*ROW_SIZE
ROW_2    EQU 2*ROW_SIZE
ROW_3    EQU 3*ROW_SIZE
ROW_4    EQU 4*ROW_SIZE
ROW_5    EQU 5*ROW_SIZE
ROW_6    EQU 6*ROW_SIZE

COL_0    EQU 0
COL_1    EQU 1
COL_2    EQU 2
COL_3    EQU 3
COL_4    EQU 4
COL_5    EQU 5
COL_6    EQU 6

        mov     al,MyMatrix0+ROW_1+COL_1
        mov     cl,MyMatrix0+ROW_2+COL_6
        mov     dl,MyMatrix0+ROW_3+COL_1
        mov     ah,MyMatrix0+ROW_5+COL_5
        mov     ch,MyMatrix0+ROW_0+COL_0
        mov     dh,MyMatrix0+ROW_6+COL_4

if you want to have variable locations, you can use regsiters to index rows and columns

Code Select Expand

        mov     al,MyMatrix0[ecx+edx]
or - a single register variable

Code Select Expand

        mov     al,MyMatrix0[edx]ROW_4

[frktons]

It depends. If you have a fixed number of columns,
imul eax, rowmem32, colimm8 is short and fast.

Hi Jochen.
1)As the example shows, the matrix has a fixed number of
rows and columns.
2) four bytes x rowmem32 + imul + colimm8 = a lot of bytes.

I need to reach the element with much less bits.

Hi Dave, same thing for your solution. Too many bytes.

Quoting myself:

How to code the required steps with the smallest number
of bits?

[qWord]

You are searching for a algorithm to "draw" lines in an 2D bit array?

http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

[jj2007]

It really depends on how you want to access the locations. Take the example of a [6,6] WORD array:
   mov ecx, 3
   mov MyWords(3, 3), 11h   ; easy...
   nops 2
   mov MyWords(3, ecx), 22h
   nops 2
   mov MyWords(ecx, 3), 33h
   nops 2
   mov MyWords(ecx, ecx), 44h
   nops 2

Disassembled (the nops separate the lines):
00401030      ³?  B9 03000000        mov ecx, 3
00401035      ³.  8B15 B83E4100      mov edx, [ArrayPtr]
0040103B      ³.  66:C742 30 1100    mov word ptr [edx+30], 11
00401041      ³.  90                 nop
00401042      ³.  90                 nop
00401043      ³.  8B15 B83E4100      mov edx, [ArrayPtr]
00401049      ³.  66:C7444A 2A 2200  mov word ptr [ecx*2+edx+2A], 22
00401050      ³.  90                 nop
00401051      ³.  90                 nop
00401052      ³.  8B15 B83E4100      mov edx, [ArrayPtr]
00401058      ³.  50                 push eax
00401059      ³.  6BC1 0E            imul eax, ecx, 0E
0040105C      ³.  03D0               add edx, eax
0040105E      ³.  58                 pop eax
0040105F      ³.  66:C742 06 3300    mov word ptr [edx+6], 33
00401065      ³.  90                 nop

[dedndave]

then use a base address for the array...

Code Select Expand

ROW_SIZE EQU 7

ROW_0    EQU 0*ROW_SIZE
ROW_1    EQU 1*ROW_SIZE
ROW_2    EQU 2*ROW_SIZE
ROW_3    EQU 3*ROW_SIZE
ROW_4    EQU 4*ROW_SIZE
ROW_5    EQU 5*ROW_SIZE
ROW_6    EQU 6*ROW_SIZE

COL_0    EQU 0
COL_1    EQU 1
COL_2    EQU 2
COL_3    EQU 3
COL_4    EQU 4
COL_5    EQU 5
COL_6    EQU 6

        mov     esi,offset MyMatrix0
        mov     al,[esi]ROW_1+COL_1
        mov     cl,[esi]ROW_2+COL_6
        mov     dl,[esi]ROW_3+COL_1
        mov     ah,[esi]ROW_5+COL_5
        mov     ch,[esi]ROW_0+COL_0
        mov     dh,[esi]ROW_6+COL_4

if you want it any smaller, you will have to use ESI and LODSB, adjusting ESI each time
not sure it is really any smaller   :P
and, Hutch will tell you it is definately slower

[frktons]

In this particular case smallest is the magic word,
fastest doesn't matter.

I throw in an idea of what short could be:
bits 0-2 to indicate first direction [UP,UP-RIGHT,RIGHT,DOWN-RIGHT...] 8 possible directions
bits 3-5 to indicate second direction [as above]
bits 6-7 to indicate third direction [4 directions only, no need to go back]

in 8 bits [1 byte] I have the path from the center [Pivot] to whatever the element
inside the 7*7 matrix.

Any better idea?

[dedndave]

do you mind a data table ?
or are you just interested in code size ?

[dedndave]

what eats up code bytes are the 32-bit addresses
to avoid that, create a table and load the addresses from there

Code Select Expand

IndxTable dd MyMatrix0+ROW_1+COL_1
          dd MyMatrix0+ROW_2+COL_6
          dd MyMatrix0+ROW_3+COL_1
          dd MyMatrix0+ROW_5+COL_5
          dd MyMatrix0+ROW_0+COL_0
          dd MyMatrix0+ROW_6+COL_4

        mov     esi,offset IndxTable
        lodsd                        ;EAX = first index
        mov     dl,[eax]
        lodsd                        ;EAX = second index
        mov     dh,[eax]

that makes for very small code, but we added the size of the table to the data section

[dedndave]

another possibility is to make each row of the matrix 8 bytes instead of 7 by padding
then, you can do something like you were talking about
bits 0,1,2 = column index
bits 3,4,5 = row index

[frktons]

I'm thinking about the ways I can use to shrink data
size for the tests with "File Compressor".
So anything that works in this direction is good enough
to think about, improve, test, and so on.

If the structure I presented, or a bigger one, is used to
keep tokens, that point to the data table with actual data
or the data is in the matrix itself, it depends on what
will be more convenient to manage, and with the smallest
quantity of bytes, of course.