64 bit product

[rich]

When multiplying two 32-bit signed integers a 32-bit result is returned.

I would like the complete 64-bits that this multiply produces.

How is it possible?

cheers.
richard

[mikep]

As no-one has replied to this, I will give you a few hints without actually writing the full code for you. Math is shown in italics and code in bold.

I don't know what you are going to do with the 64-bit answer but you will need a way to store it as two 32-bit integers.

Assume we have a constant for value of 2^16=65536 called m. Note that m is only used to illustrate the arithmetic and is not needed in the final code.

You can divide a 32-bit integer into two 16-bit ones using simple arithmetic. For example a = ah * m + al
where ah is the top 16 bits can be derived using HiWord and al is the lower 16 bits derived using LoWord.
ah = HiWord(a)
al = LoWord(a)

Similarly with b, bh, and bl where b = bh * m + bl.
bh = HiWord(b)
bl = LoWord(b)

Now multiplying a and b will result in a 64-bit integer represented by x where
x is split into two 32-bit integers xh and xl where x = xh * m * m + xl

Using simple algebra x = (ah * m + al)(bh * m + bl) = ah*bh*m*m + ah*bl*m + al*bh*m + al*bl

We need to split out the parts of ah*bl and al*bh that straggle the lower 16 bits of xh and the top 16 bits of xl

xh = ah*bh + HiWord(ah*bl) + HiWord(al*bh)
xl = al*bl + m * (LoWord(ah*bl) + LoWord(al*bh)

Now you may actually spot a problem with the code above. What happens if LoWord(ah*bl) + LoWord(al*bh) actually carries over and is more than 16 bits. It will overflow when you multiply it by m (or use a SHL operator with 16).

That means calculating an intermediate answer y for this value where y = yh * m + yl

So the final code is something like this:
y = LoWord(ah*bl) + LoWord(al*bh)
xh = ah*bh + HiWord(ah*bl) + HiWord(al*bh) + HiWord(y)
xl = al*bl + SHL((LoWord(y),16)

All of this has assumed UNSIGNED integers. But you asked for signed. The simplest thing is to use the ABS function to convert and then figure out the sign of the answer afterwards. Remember different signs means negative and same sign means positive. The SIGNUM function may be helpful here.

[dkinzer]

I would like the complete 64-bits that [a 32x32 bit] multiply produces.

Which ZX target device are you using? If you're using a native mode device the easiest solution may be to use a special assembly language routine to do the 32x32 bit multiplcation and return a 64-bit result (a google search returns some promising results). Then, you would add a C-language "glue" function to act as an intermediary to pass the 32-bit values to the multiplication routine with the result as a "long long" type and then split that into two 32-bit values to return to the caller.

If you're using a non-native device, you'll have to do the piecewise multiplication as Mike suggested. In either case, since ZBasic doesn't have a 64-bit type you would probably want to define a structure to hold the two halves.

[GTBecker]

Ha! I saw that subject line and immediately thought I'd be reading about a new 64-bit ZBasic product. Yeah! Alas, no.

[mikep]

Ha! I saw that subject line and immediately thought I'd be reading about a new 64-bit ZBasic product. Yeah! Alas, no.

A skilled programmer could create a 64-bit integer and floating point library using all of the constructs that already exist in ZBasic. Wrapping some 64-bit C code in native mode would work the best. Now I did the hard bit throwing out the challenge - the rest is easy

[rich]

Thank for the response.

So C has an int64_t in Arduino world.

If i had a 64-bit multiply,divide, add, subtract library that would probable be the cleanest way to do it.

How to you pass 64-bit values to and from the ZBasic code?

cheers,
Richard

[dkinzer]

How to you pass 64-bit values to and from the ZBasic code?

You either use two 32-bit values or define a structure with two 32-bit members.

For example in ZBasic code:

Code: Select all

'define a structure to hold 64-bit values
Structure i64
    Dim lo32 as UnsignedLong
    Dim hi32 as Long
End Structure

' declare the glue routine implemented in C
Declare Sub mul32(ByVal val1 as Long, ByVal val2 as Long, ByRef result as i64)

Dim v1 as Long
Dim v2 as Long
Dim res64 as i64

Sub Main()
    ' invoke the glue routine to do the multiplication
    Call mul32(v1, v2, res64)
End Sub

And then define a glue function in C:

Code: Select all

#include <inttypes.h>

typedef struct
&#123;
   int32_t lo;
   int32_t hi;
&#125; i64_t;

typedef union
&#123;
   i64_t zval;
   int64_t val;
&#125; comp_t;

void
mul32&#40;int32_t v1, int32_t v2, comp_t *res&#41;
&#123;
    int64_t result;

    // add code here to call the 32x32 multiplication routine
    // passing the v1 and v2 values, placing the result in the
    // 64-bit local variable 'result'

    // and then pass the result back to the caller indirectly
    res->val = result;
&#125;

Some would criticize this code because it relies on word order in the C code matching the word order in ZBasic. Since we know that they do match the risk is not great but one must be aware of that caveat.

This code will work whether you implement the 32x32 multiplication in C or in assembly language although the exact details of invoking the worker routine may differ depending on the implementation language.

[rich]

Thank you much for the c-code example.

It answers lots of questions.

cheers,
rich

[dkinzer]

The attached .zip file contains a working example with a lightly tested 32x32 multiplication routine. The mul32x32.S file contains an assembly language implementation of 32x32 unsigned multiplication with a 64-bit result. The glue.c file contains a helper function, callable from ZBasic, that makes the input values unsigned, calls the unsigned multiplication routine and then, if necessary, corrects the sign of the result. The glue.c file also contains routines to produce a sequence of decimal digits corresponding to signed and unsigned 64-bit values. Finally, the mul32x32_test.bas file shows how you can do some testing.

It is possible to implement signed multiplication directly in assembly language using the muls and mulsu instructions but I didn't take the time to figure out how to use them properly to get the correct results. I believe that the register allocation strategy would need to be changed because mulsu is restricted as to which registers it can use.

[dkinzer]

The attached .zip file contains updated versions of the files in the previous attachment plus it includes imul32x32.S which implements a signed 32x32 multiplication routine. Using this routine avoids the need to make the arguments positive and then set the sign of the result afterward.

There is a conditional definition in glue.c that controls which strategy is used. Also, there is a conditional in mul32x32_test.bas that controls whether elapsed time for the multiplication is calculated rather than reporting the result of a multiplication.

It turns out that the signed and unsigned routines are nearly the same speed if the values to be multiplied are both positive. If one value is negative and the other positive the signed routine is faster (about 13uS vs 15uS). I didn't check timing on the case where both values are negative but I assume that it would be somewhere between those two times.

[rich]

@dkinzer
So now i got it to compile.

I had to choose a device that was native mode to get it to work.
You said that but i did not know what that was until i tried it.

I also i did not realize the actual work was in asm but that makes sense now.

Thanks much, this nooby could not have done it on my own.

Also if i use a TTL output USB to serial adapter, what circuit is recommend to generate the ATN pulse form the DTR TTL signal?

Now to get a part and see if i can set the hardware up.

cheer,
Richard

[dkinzer]

Also if i use a TTL output USB to serial adapter, what circuit is recommend to generate the ATN pulse form the DTR TTL signal?

The capacitively-coupled ATN circuit is mostly the same but you'll probably need an inversion of the DTR signal before applying it to the base of a transistor. You'll find suggested ATN circuits in the appendices of the ZBasic Language manual.

http://www.zbasic.net/doc/ZBasicRef.html

[dkinzer]

you'll probably need an inversion of the DTR signal before applying it to the base of a transistor.

After posting this I remembered that the ZX-1280 development board has circuitry that allows either a standard RS-232 port or USB to be used for serial communication. It has a switch that selects which is being used and in each position routes the DTR signal, either at RS-232 level or TTL level to a transistor to generate the ATN pulse. The FT232RL used on the board uses the standard factory configuration so I suspect that many or most USB-serial implementations might generate a DTR signal that can be used directly (i.e. without inversion).

See the schematics for the ZX-1280 development board:
http://www.zbasic.net/doc/ZX-1280_DevBoard/