2

I have an embedded 16 bit CPU. On this machine ints are 16 bit wide and it supports longs that are 32 bits wide. I need to do some multiplications that will need to be stored in 64 bits (e.g. multiply a 32 bit number by a 16 bit number). How can I do that with the given constraints? I do not have a math library to do this.

SeanLabs
  • 1,739
  • 4
  • 18
  • 22
  • 1
    You need a math library that provides that kind of service as a function call. – RenniePet Aug 25 '13 at 04:12
  • 1
    Well ... you're not providing enough information. Are you programming this in assembler or C or something else? You will need to obtain or write yourself a function or subroutine that does the multiplication. Try a Google search for "name of microprocessor math library". Open source if possible, then you can see the source code for how it's done, and just copy the instructions if you don't want to include the whole library with your program. (This is not my field of expertise, it's 35 years since I did this kind of programming, I'm amazed that it is still necessary.) – RenniePet Aug 25 '13 at 04:26
  • It might help if you provide the name of the microprocessor, instead of just saying "embedded 16-bit cpu". – RenniePet Aug 25 '13 at 04:29
  • 1
    Looks like a dupe of http://stackoverflow.com/questions/15709714/64-bit-arithmetic-with-16-bit-word-lengthstore-64-bit-number-across-4-words – BergQuester Aug 25 '13 at 05:25
  • 1
    Now that I think of it, in the "good old days" the manufacturer of the microprocessor typically provided a free math library and/or published suggested arithmetic functions for doing this sort of thing. But like I say, I have no knowledge of how low-level programming for microprocessors is done nowadays. – RenniePet Aug 25 '13 at 09:22
  • Similar to [Efficient Multiply/Divide of two 128-bit Integers on x86 (no 64-bit)](http://stackoverflow.com/q/8776073/995714) and [How can I multiply 64 bit operands and get 128 bit result portably?](http://stackoverflow.com/q/25095741/995714). Just change the types to a half – phuclv Jan 07 '17 at 07:02

2 Answers2

3

A suggestion in C. Note that this code probably will be easier to implement with inline assembler as carry detection in C doesn't seem that easy

// Change the typedefs to what your compiler expects
typedef unsigned __int16     uint16   ;
typedef unsigned __int32     uint32   ;

// The 64bit int
typedef struct uint64__
{
    uint32       lower   ;
    uint32       upper   ;
} uint64;

typedef int boolt;

typedef struct addresult32__
{
    uint32      result  ;
    boolt       carry   ;
} addresult32;

// Adds with carry. There doesn't seem to be 
// a real good way to do this is in C so I 
// cheated here. Typically in assembler one
// would detect the carry after the add operation
addresult32 add32(uint32 left, uint32 right)
{
    unsigned __int64 res;
    addresult32 result  ;

    res = left;
    res += right;


    result.result = res & 0xFFFFFFFF;
    result.carry  = (res - result.result) != 0;

    return result;
}

// Multiplies two 32bit ints
uint64 multiply32(uint32 left, uint32 right)
{
    uint32 lleft, uleft, lright, uright, a, b, c, d;
    addresult32 sr1, sr2;
    uint64 result;

    // Make 16 bit integers but keep them in 32 bit integer
    // to retain the higher bits

    lleft   = left          & 0xFFFF;
    lright  = right         & 0xFFFF;
    uleft   = (left >> 16)  ;
    uright  = (right >> 16) ;

    a = lleft * lright;
    b = lleft * uright;
    c = uleft * lright;
    d = uleft * uright;

    sr1 = add32(a, (b << 16));
    sr2 = add32(sr1.result, (c << 16));

    result.lower = sr2.result;
    result.upper = d + (b >> 16) + (c >> 16);
    if (sr1.carry)
    {
        ++result.upper;
    }

    if (sr2.carry)
    {
        ++result.upper;
    }

    return result;
}
phuclv
  • 37,963
  • 15
  • 156
  • 475
Just another metaprogrammer
  • 11,499
  • 2
  • 35
  • 54
3

You might want to check out Hacker's Delight (it's a book and a website). They have C implementations of Knuth's signed multiword multiplication and unsigned multiword multiplication from The Art of Computer Programming Vol.2.

ldav1s
  • 15,885
  • 2
  • 53
  • 56