Not your average assembly question...

[HarryW]

Well I doubt if this is the kind of question anybody is used to seeing.

I am writing an instruction for the IJVM instruction set on a very simple CPU, which has to multiply two 32-bit 2's complement signed operands on the stack and place the result into two 32-bit operands back on the stack, as a high word and a low word.

I am posting it here because being an assembler forum I fugured a lot of people would probably know about the internal workings of a CPU. Maybe even know how to do what I'm trying to do :)

Essentially I have these registers:

MAR - Memory Address Register
MDR - Memory Data Register
PC - Program Counter
MBR - Memory Buffer Register
SP - Stack Pointer
LV - Local Variable pointer
CPP - Constant Pool Pointer
TOS - Top Of Stack register (can be used as a temp. space)
OPC - temporary (ie scratch) register
H - Holding register, used for a second input to the ALU/shifter

I need to make a microprogram using microcode that will basically read in data from the stack to MDR, move values from register to register, use the ALU and shifter on the values in the registers, and write data back to the stack from MDR.


Okay, here's what I'm asking :)

I would very much appreciate any ideas for algorithms to multiply operands with sign extension. I also would like to know how to get the result into two 32-bit words. I have a few ideas running around in my head for all these things but nothing concrete.

Now if anybody fancies trying their hand at some microcode (or if they've done it before) then that would be greatly appreciated. I will outline the basic syntax:

First a quick example:


MAR = SP = SP + 1 Increment SP and copy to MAR
MDR = TOS; wr Write new stack word


That is the IJVM idup instruction, which duplicates the word on top of the stack, placing the duplicate on the stack too.

Each line represents one CPU cycle, and seperate actions are divided by semicolons (;).

"wr" represents a write to the stack at the position the value in SP (stack pointer) points to, writing the value contained in MDR (memory data register). "rd" does the opposite, placing the value pointed to by SP into MDR. At the beginning of each instruction (ie at the beginning of the microprogram) TOS contains the value on the top of the stack. This is for convenience, and it can be overwritten and used as a temporary workspace if necessary.

MAR and MBR work with bytes (8 bits). MDR and SP and the others use words (32 bits). When you assign a word value to MAR, it gets shifted automatically so you don't have to worry about it. You can also use MBRU, which is the unsigned version of the value in MBR. You can use "fetch" to get a byte value at the address in MAR and put it in MBR.

Here is another example, iload, which loads a variable onto the stack.
The offset of the local variable to put on the stack is in MBRU.


H = LV MBR contains index; Copy LV to H
MAR = MBRU + H; rd MAR = address of local variable to push
MAR = SP = SP + 1 SP points to new top of stack; prepare write
PC = PC + 1; fetch; wr Inc PC; get next opcode; write top of stack
TOS = MDR Update top of stack




I feel like I'm the only person in the world that is doing this at the moment. Does anybody even know what I'm talking about?


Well I know this is probably all really boring, so it's a good thing that I think I can handle the microcode. Actually just writing this has helped me to understand it :)

I would really, really, appreciate some help on the algorithm to do the multiplication though.

Right that's it, thanks for your time if you've read this far :)

[sebs]

I know that ASM is very hard, i remember learning it at
school, just for multiplying 2 digits number, it took about
(if i rember right)15-20 lines,(imagine 3 digits).

My book is at my dad and i'll go there tomorow, so i'll take a look and i'll post some example for u(tomorow night though)!

If u want to i'll post the 2 digits code if i put my hand on it!!

I don't what you'r trying to do but i'll try to help anyway!!

[HarryW]

Thanks a lot, I would very much appreciate that :)

I have found one technique called the Booth Algorithm, which I don't entirely understand at the moment. For an example you can look here (http://ivs.cs.uni-magdeburg.de/EuK/Lehre/booth.html).

The problem is that it seems to be multiplying two 5-bit operands within a 16-bit variable, which I find more than slightly confusing.

I need to multiply 2 32-bit operands and produce both a high 32-bit signed word and low 32-bit unsigned word.


For anybody who's taken any interest in the microcode, it's documented on this site (http://www.ontko.com/mic1/mal.html). It's called MAL (Micro-Assembly Language).

[sebs]

I Harry, sorry for the laps of time, i found a few notes
but i dunno if it will help.

I'll tell u what i've got and tell me if u want to know them:

-conditionnal jump(JE,JG,JGE,JL,JLE)
-DOS interrutions(end a program,get a random #,end a program that still reside in the computer,lot more.....)

and i can give u my program that add 2 digits number.

[HarryW]

Hi, thanks :) I have actually found the solution I think. I know how to code the Booth Algorithm into mocrocode and I know which registers to use, it's just a case of implementing it now.

Thank you anyway, but I'm not coding in Intel x86 assembly, it's a subset of Java Virtual Machine assembly which doesn't deal with floating point numbers, it's just integers.

Anyway thanks, I think I have the solution now :)

[HarryW]

In case anyone cares, this was my solution (couldn't get the simulator to work so I could test it) and I'm pretty sure it's right.

imul1 OPC=0x20 // Set OPC as a counter... OPC = 32
imul2 MAR=SP-1; rd // Read first operand (second word on the stack)
imul3 H=TOS // Operands are now in H and MDR, TOS freed to be accumulator
imul4 TOS=0 // Clear accumulator. One 0 just handled.
imul5 MDR=MDR; SRA1; if (notLSB) goto imul17 // Check for 00, else carry on for 10
imul6 TOS=TOS-H; SRA1 // 10 - subtract multiplicand, start the shift
imul7 MDR=MDR; RROT // Bitwise rotate on MDR, LSB has the next recode bit
imul8 OPC=OPC-1; if (Z) goto imul18 // Decrement the counter (OPC), if it's 0 then we've finished
imul9 MDR=MDR; SRA1; if (notLSB) goto imul14 // One 1 just handled, Check for 11/10 and skip one line if 10
imul10 TOS=TOS; SRA1; goto imul10 // 11 so start a shift then check for 10
imul11 TOS=TOS+H; SRA1 // 01 so add multiplicand then shift
imul12 MDR=MDR; RROT // Bitwise rotate on MDR, LSB has the next recode bit
imul13 OPC=OPC-1; if (Z) goto imul19 else goto imul8 // Decrement counter. Set JAM then set again if counter=zero
imul14 TOS=TOS; SRA1; goto imul15 // 00 so middle of string of 0s - keep shifting.
imul15 wr; goto imul20 // Write MDR to SP-1 (most significant word). Skip next line.
imul16 wr // Extra end-point, due to the way mic-1 conditional jumps work
imul17 MAR=SP // Prepare to write LSW to top of stack.
imul18 MDR=TOS; wr; goto Main1 // Write least significant word to top of stack. End instruction

That has to be the hardest piece of coursework I have ever had to do. Still, the lecturer said he would give people high marks (80%+) just for attempting this (I picked the hardest question ;) ).