48 비트 결과를 가진 16 비트 * 32 비트 MUL

Question

16 비트 * 32 비트 연산을 원하지만 32 비트 레지스터 만 사용하고 싶습니다. 출력은 48 비트이기 때문에 두 개의 32 비트 레지스터로 결과를 포착 할 수 있습니다. 이 문제의 C 코드를 원합니다! 64 비트 출력 기능을 가진 32 비트 * 32 비트 MUL을 가지고 있지만 신호 때문에이 기능을 제대로 사용할 수 없습니다. exapmle 16 비트에서 1을 뺀 값은 0xFFFF이고 32 비트에서 1을 뺀 값은 0xFFFFFFFF입니다. 이 코드는 MUL의 LLVM 번역에 사용됩니다.

Answer 1

이와 비슷한 작업을하려고하십니까?

#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); 
} 

당신은 모든 기본 65536 (** 16 2)에서 두 자리 숫자 한 자리 수를 곱하고 실현하면 그것은 훨씬 더 쉽다.

출력을 확인하고 표시하기 위해 64 비트 만 사용했습니다. 곱셈은 32 비트에서 작동합니다.

여기는 테스트 하니스에 : 여기

#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

16 비트 레지스터를 32 비트 레지스터로 부호 확장 한 다음 부호있는 32 비트 x 32 비트 곱셈을 사용하십시오.

Answer 3

어려운 부분은 이전 버전의 C 언어 (*) ... 및 int, long 및 long long에서 명시 적으로 정의되지 않았기 때문에 16 비트, 32 비트 및 64 비트 정수가 어떻게 정의되는지를 아는 것입니다 그런 식으로.

은 당신이 int32_t와 int64_t, 당신이 할 수있는, int16_t 있다고 가정

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; 
} 

(*) 그것은 C99의 일부입니다 만> 2010 년

편집 OP 코멘트 당 MSVC에서 제공

하나의 16 비트 정수 (상위 부분)와 하나의 32 비트 정수로 결과를 얻으려면 위의 약간의 차이가 있습니다.

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; 
} 

물론 32 비트 연산과 시프트를 사용하여 제품 16 비트 * 32 비트를 직접 처리 할 수도 있습니다. 하지만 컴파일러가 64 비트 연산을 직접 수행하는 것보다 효율적이지는 않습니다.

Answer 4

32 * 32 MUL이다. 누군가가 LLVM을 이해하면 도움이 될 것입니다. 16 비트 부호 확장을위한 다음이 기능.

/*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; 
}