miden-vm icon indicating copy to clipboard operation
miden-vm copied to clipboard

Instruction to reverse elements on the stack

Open hackaugusto opened this issue 1 year ago • 4 comments

Some operations expect the stack to be in reverse order, so it can be useful to have an instruction to change the stack as follows:

[a,b,c,d] -> [d,c,b,a]
[a,b,c,d, e,f,g,h] -> [h,g,f,e, d,c,b,a]
[a,b,c,d, e,f,g,h, i,j,k,l] -> [l,k,j,i, h,g,f,e, d,c,b,a]

It may also be useful to have intermediary sizes:

[a,b,c,d, e,f] -> [f,e, d,c,b,a]
[a,b,c,d, e,f,g,h] -> [g,f,e, d,c,b,a]

hackaugusto avatar Mar 29 '23 08:03 hackaugusto

I think we usually call this "stack order" where the first element is deepest in the stack.

I think pretty much all operations assume that elements are in the stack order - but I might be missing some. Which ones expect elements to be not in the stack order?

bobbinth avatar Mar 29 '23 19:03 bobbinth

I have not found any inconsistencies on how the instructions are defined, AFAIK all operations are using stack order.

I usually pack the data word-by-word, which is inconsistent with how the VM works, so I found myself re-doing MASM code to have a word in stack order. The idea of the instructions it that may be useful to other people that makes the same mistakes as I

hackaugusto avatar Mar 29 '23 19:03 hackaugusto

I usually pack the data word-by-word, which is inconsistent with how the VM works

I think this should not cause problems. For example, if you have two words [a0, a1, a2, a3], [b0, b1, b2, b3] packed together and you push them onto the stack, they would appear as [b3, b2, b1, b0, a3, a2, a1, a0, ...] (with b3 being on the top of the stack) - so, the relative order of elements is preserved. Or am I misunderstanding the issue?

bobbinth avatar Mar 29 '23 19:03 bobbinth

I just have a tendency of writing code that pushes data to the stack in the order:

[a0, a1, a2, a3] [b0, b1, b2, b3]

It is perfectly possible to push the data in stack order (and well, after I notice my mistake I change the code to the right order 😅). The idea here is that an instruction to change

[a0, a1, a2, a3] -> [a3, a2, a1, a0]

Can be useful sometimes

hackaugusto avatar Mar 29 '23 19:03 hackaugusto