How to sum elements of an array only with direct addressing?

Question

Suppose we have an array of 100 numbers. I saw a question about this here but didn't understand how to solve the problem. These are the instructions we have:

Instruction	Meaning
mov addr1,addr2	Maddr1 = (Maddr2);
mov addr1,(addr2)	Maddr1 = (M_(Maddr2));
mov (addr1),addr2	M_(Maddr1) = (Maddr2);
add addr1,addr2	Maddr1 = (Maddr1) + (Maddr2);
sub addr1,addr2	Maddr1 = (Maddr1) - (Maddr2);
add addr1,(addr2)	Maddr1 = (Maddr1) + (M_(Maddr2));
sub addr1,(addr2)	Maddr1 = (Maddr1) - (M_(Maddr2));
jnz addr1,addr2	if (Maddr1)≠0 then PC = addr2;
jz addr1,addr2	if (Maddr1)=0 then PC = addr2;
jneg addr1,addr2	if (Maddr1)<0 then PC = addr2;
jpos addr1,addr2	if (Maddr1)>0 then PC = addr2;

And this is the code to solve the program using indirect addressing:

org 100h
loop:
add sum,(arrptr)
add arrptr,two
sub count,two
jnz count,loop

arrptr: dw array
sum: dw 0
count: dw 200
two: dw 2
array: dw 100 dup(?)

I wanted to know how to sum these elements without using <arrptr>. I know it will be a self modifying code but don't know exactly how to write this code.

I was looking for a way to move every element to the address of the first element of the array but didn't find a way.

Answer 1

I was looking for a way to move every element to the address of the first element of the array but didn't find a way.

Instead of moving the address of elements (in short, we can't do this), we modify the instruction to access successive elements at their sequential addresses.

To do self modifying code, we write an instruction to access the first element, run it, then increment the code instruction itself, in such a way that the instruction now points to the next element.

In pseudo code:

Loop:
    add sum,array    // this instruction is modified during iteration
    add loop,two     // and here's where we modify it
    sub count,two
    jnz count,Loop

On the very first iteration, the add sum,array will fetch the first element of the array.  During the loop body, this instruction itself is incremented so that for the second iteration that instruction now reads (in machine code and to the processor) as add sum,array+2.

Issues:

• This won't work on modern architectures with caches unless you also use cache flushing operations (which would make it very slow).

• Much like with global variables, the instruction at Loop: is modified during the execution of the loop, meaning this loop as a whole, in order to run the whole loop again, we would have to reset the instruction at Loop: back to refer to the beginning.

  The same is true for programs that rely on the initialization of mutable global variables — the parts of the program that rely on this global initialization will require re-initialization if that section of code is to be reused.

• The amount to increment depends on the size of the array elements.  For example, for an 8-bit integer, we would add 1 instead of 2.

• Instruction Set Encoding Issues

  On some architectures the encoding of the add will use a straightforward immediate value for which a simple increment of the whole machine code instruction as an integer word makes sense.

  However, on some architectures, an immediate of 0 is not encoded, thus with a naïve approach there could be no immediate to increment.

  On other architectures, the bits of immediates are distributed throughout the instruction and not necessarily consecutive making a simple increment of the immediate value difficult.

  Other problems include the immediate not being large enough to accommodate the indexing to elements far further in the array.

  And further, we should know the size of the instruction being incremented.

Answer 2

Based on the code snippet that you supply, this is how you can solve it for x86-16. The mov ax, [array] instruction is encoded with just 3 bytes and the last 2 bytes are the address of the array. The self-modification happens in the add word [TheLoop + 1], 2 instruction that advances through the array's memory. In the end the sub word [TheLoop + 1], 200 instruction restores the mov ax, [array] instruction to what it was before all the self-modification happened:

ORG 100h

  mov  cx, 100                   ; 100 times
TheLoop:
  mov  ax, [array]
  add  [sum], ax
  add  word [TheLoop + 1], 2     ; 2
  sub  cx, 1
  jnz  TheLoop
  sub  word [TheLoop + 1], 200   ; 100 times 2


sum:   dw 0
array: dw 100 dup(?)

don't know exactly how to write this code.

Your "These are the instructions we have"-list is not enough for me to present the solution in the language of choice (that you didn't mention), but I believe my code snippet should give you an idea...