16bit*32bit MUL with 48bit result

Question

I want to do 16bit * 32bit Mul operation but using only 32bit register. Result can be caught by two 32 bit registers as output is 48bits. I want C code for this problem! I have 32bit*32bit MUL with 64bit output function but i can not use this function here properly because of signs. For exapmle 16bit minus one is 0xFFFF and 32bit minus one is 0xFFFFFFFF. I will be using this code for LLVM translation of MUL.

Answer 1

Are you trying to do something like this?

#include <inttypes.h>

void multiply(uint16_t*top,uint32_t*bottom, uint16_t lhs,uint32_t rhs){

    uint32_t low=lhs*(rhs&0xFFFF);
    uint32_t high=lhs*(rhs>>16)+(low>>16);
    *bottom=(high)<<16)|(low&0xFFFF);
    *top=(high>>16);
}

It's a whole lot easier when you realize you're multiplying a single digit number by a two digit number all in base 65536 (2**16).

I've only used 64-bit to check and display the output. The multiply operates in 32-bit.

Here it is in test harness:

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>

void multiply(uint16_t*top,uint32_t*bottom, uint16_t lhs,uint32_t rhs){

    uint32_t low=lhs*(rhs&0xFFFF);
    uint32_t high=lhs*(rhs>>16)+(low>>16);
    *bottom=(high)<<16)|(low&0xFFFF);
    *top=(high>>16);
}

uint64_t encode64(uint16_t top,uint32_t bottom){
    return (((uint64_t)top)<<32)|((uint64_t)bottom);
}

int check(uint16_t lhs,uint32_t rhs){
    uint16_t t16;
    uint32_t t32;

    multiply(&t16,&t32,lhs,rhs);
    const uint64_t result=encode64(t16,t32);

    uint64_t llhs=lhs;
    uint64_t lrhs=rhs;
    uint64_t expect=llhs*lrhs;

    if(result==expect){
        return 0;
    }
    printf("%"PRIu16"*%"PRIu32"==%"PRIu64"!=%"PRIu64"\n",lhs,rhs,result,expect);
    return 1;
}

int main(void) {
    int error=0;
    uint16_t top;
    uint32_t bottom;
    uint16_t lhs=58989;
    uint32_t rhs=5978342;
    error+=check(2U,20UL);
    error+=check(0xFFFF,0xFFFFFFFF);
    error+=check(768U,565354767UL);
    error+=check(26434U,566534767UL);
    error+=check(26434U,690789UL);
    error+=check(5678U,9767889UL);
    error+=check(3674U,784367UL);
    error+=check(0,690789ULL);
    error+=check(0,0xFFFFFFFF);
    error+=check(0xFFFF,0);
    error+=check(0xFFFF,1);
    error+=check(1,0xFFFFFFFF);
    error+=check(0x2,0xAFFFFFFF);       
    multiply(&top,&bottom,lhs,rhs);

    uint64_t result=encode64(top,bottom);

    printf("%"PRIu16"*%"PRIu32"==%"PRIu64"\n",lhs,rhs,result);

    if(error!=0){
        printf("\nErrors=%d\n",error);
    }

    return error==0?EXIT_SUCCESS:EXIT_FAILURE;
}

Answer 2

The hard part is to know how are defined 16bits, 32 bits and 64 bits integers, because it was not specified in old revisions of C language (*) ... and int, long and long long and not explicitely defined that way.

Assuming you have int16_t, int32_t and int64_t, you could do

int64_t product16_35(int16_t val1, int32_t val2) {
    int64_t v1 = val1, v2 = val2, resul;
    resul = v1 * v2; /* resul uses 48 bits on 64, with sign extended to 64 bits */
    resul &= 0x00FFFFFFFFFFFFFF; /* truncate resul at 48 bits */ 
    return resul;
}

(*) It is part of C99 and only shipped in MSVC > 2010.

Edit per OP comment

If you want the result in one 16 bit integer (high order part) and one 32 bits integer, here is a slight variation of above :

struct int48 {
    int16_t h;
    uint32_t l; /* sign has no sense for lower part */
}

int48 product16_35(int16_t val1, int32_t val2) {
    int48 res48;
    int64_t v1 = val1, v2 = val2, resul;
    resul = v1 * v2; /* resul uses 48 bits on 64, with sign extended to 64 bits */
    resul &= 0x00FFFFFFFFFFFFFF; /* truncate resul at 48 bits */
    res48.l = resul & 0xFFFFFFFF;
    res48.h = (resul >> 32) & 0xFFFF;
    return res48;
}

Of course, I could also do by hand the product 16bits * 32 bits using only 32 bits operations and shifting. But it would certainly be less efficient than what the compiler does when I ask it do do directly 64 bits operations.

Answer 3

Sign-extend your 16 bit register into a 32 bit register, then use your signed 32bit x 32bit multiply.

Answer 4

Here is 32*32 MUL. If someone understands LLVM then it would be helpful for them. for 16bit just sign extension and then this function.

/*static*/
enum bin2vm_status_codes bin2vm::IrModuleWriter::getSignedMul32_Result64bit(llvm::Value* tempFirstOp,llvm::Value* tempSecondOp,llvm::Value** result_Right32,llvm::Value** result_Left32, IRBuilder* irBuilder )
{
  enum bin2vm_status_codes status = BIN2VM_STATUS_SUCCESS;
  oef_debug_print(( "bin2vm::IrModuleWriter::getSignedMul32_Result64bit(): ENTERED\n" ));
  llvm::Value* Op1IsNeg = nullptr;
  llvm::Value* bool_Op1IsNeg = nullptr;
  llvm::Value* Op2IsNeg = nullptr;
  llvm::Value* bool_Op2IsNeg = nullptr;
  llvm::ConstantInt* int32One = irBuilder->getInt32(1);
  llvm::Value* finalResult_right32 = nullptr;
  llvm::Value* bool_bothNeg = nullptr;
  llvm::Value* firstOp_right = nullptr;
  llvm::Value* firstOp_left = nullptr;
  llvm::Value* secondOp_right = nullptr;
  llvm::Value* secondOp_left = nullptr;
  llvm::Value* partialProduct_0 = nullptr;
  llvm::Value* partialProduct_1 = nullptr;
  llvm::Value* partialProduct_2 = nullptr;
  llvm::Value* partialProduct_3 = nullptr;
  llvm::Value* partialProduct_1_left = nullptr;
  llvm::Value* partialProduct_1_right = nullptr;
  llvm::Value* partialProduct_2_left = nullptr;
  llvm::Value* partialProduct_2_right = nullptr;
  llvm::Value* sumPartial_temp = nullptr;
  llvm::Value* sumPartial = nullptr;
  llvm::Value* finalResult_left32 = nullptr;
  llvm::Value* sumPartial_op1Neg = nullptr;
  llvm::Value* sumPartial_op2Neg = nullptr;
  llvm::Value* sumPartial_bothNeg = nullptr;
  llvm::Value* bothNeg = nullptr;


  //Mul operation   
  finalResult_right32 = irBuilder->CreateMul(tempFirstOp,tempSecondOp,"mulResult");


  //Calculation for left 32 bits
  //Can have a look at http://stackoverflow.com/questions/22845801/32-bit-signed-multiplication-without-using-64-bit-data-type
  firstOp_right = irBuilder->CreateAnd(tempFirstOp,0x0000FFFF,"firstOp_right");
  firstOp_left = irBuilder->CreateLShr(tempFirstOp, 16, "firstOp_left");
  secondOp_right = irBuilder->CreateAnd(tempSecondOp,0x0000FFFF,"secondOp_right");
  secondOp_left = irBuilder->CreateLShr(tempSecondOp, 16, "secondOp_left");

  /* compute partial products */
  partialProduct_0 = irBuilder->CreateMul(firstOp_right,secondOp_right,"partialProduct_0");
  partialProduct_1 = irBuilder->CreateMul(firstOp_right,secondOp_left,"partialProduct_1");
  partialProduct_2 = irBuilder->CreateMul(firstOp_left,secondOp_right,"partialProduct_2");
  partialProduct_3 = irBuilder->CreateMul(firstOp_left,secondOp_left,"partialProduct_3");

  partialProduct_0 = irBuilder->CreateLShr(partialProduct_0,16,"partialProduct_0");
  partialProduct_1_left = irBuilder->CreateLShr(partialProduct_1,16,"partialProduct_1_left");
  partialProduct_1_right = irBuilder->CreateAnd(partialProduct_1,0x0000FFFF, "partialProduct_1_right");
  partialProduct_2_left = irBuilder->CreateLShr(partialProduct_2,16,"partialProduct_2_left");
  partialProduct_2_right = irBuilder->CreateAnd(partialProduct_2,0x0000FFFF, "partialProduct_2_right");

  //sumPartial_temp = ((p0 >> 16) + (uint16_t)p1 + (uint16_t)p2) >> 16
  sumPartial_temp = irBuilder->CreateAdd(partialProduct_0,partialProduct_1_right,"sumPartial_temp");
  sumPartial_temp = irBuilder->CreateAdd(sumPartial_temp,partialProduct_2_right,"sumPartial_temp");
  sumPartial_temp = irBuilder->CreateLShr(sumPartial_temp,16,"sumPartial_temp");

  // p3 + (p2 >> 16) + (p1 >> 16) + sumPartial_temp
  sumPartial = irBuilder->CreateAdd(sumPartial_temp,partialProduct_3,"sumPartial");
  sumPartial = irBuilder->CreateAdd(sumPartial,partialProduct_2_left,"sumPartial");
  sumPartial = irBuilder->CreateAdd(sumPartial,partialProduct_1_left,"sumPartial");

  //Now for signed Mul we look at sumPartial- ((op1 < 0) ? op2 : 0) - ((op2 < 0) ? op1 : 0)
  sumPartial_op1Neg = irBuilder->CreateSub(sumPartial,tempSecondOp,"sumPartial_op1Neg");
  sumPartial_op2Neg = irBuilder->CreateSub(sumPartial,tempFirstOp,"sumPartial_op2Neg");
  sumPartial_bothNeg = irBuilder->CreateSub(sumPartial_op1Neg,tempFirstOp,"sumPartial_bothNeg");

  //MUL signed adaptation
  Op1IsNeg = irBuilder->CreateLShr(tempFirstOp,31,"bool_Op1IsNeg");
  bool_Op1IsNeg = irBuilder->CreateICmpEQ(Op1IsNeg, int32One,"bool_Op1IsNeg");
  Op2IsNeg = irBuilder->CreateLShr(tempSecondOp,31,"bool_Op2IsNeg");
  bool_Op2IsNeg = irBuilder->CreateICmpEQ(Op2IsNeg, int32One,"bool_Op2IsNeg");
  bothNeg = irBuilder->CreateAnd(Op1IsNeg,Op2IsNeg,"bothNeg");
  bool_bothNeg = irBuilder->CreateICmpEQ(bothNeg,int32One,"bool_bothNeg");

  //Resul left 32 bits
  finalResult_left32 = irBuilder->CreateSelect(bool_Op1IsNeg,sumPartial_op1Neg,sumPartial);
  finalResult_left32 = irBuilder->CreateSelect(bool_Op2IsNeg,sumPartial_op2Neg,finalResult_left32);
  finalResult_left32 = irBuilder->CreateSelect(bool_bothNeg,sumPartial_bothNeg,finalResult_left32);


  *result_Right32 = finalResult_right32; 
  *result_Left32 = finalResult_left32;

  return status;
}