Умножение 32-разрядного целого числа со знаком без использования 64-разрядного типа данных

Question

Я хочу сделать 32-разрядное целочисленное умножение со знаком без использования 64-разрядного типа данных. Мои входные данные в формате Q1.31 (оба).

input1 = A32 (Ah Al) - higher, lower half's of A32
input2 = B32 (Bh Bl) - higher, lower half's of B32

Результат должен быть в формате Q1.31, оставьте случай переполнения.

Мне нужен код C Пожалуйста, предоставьте объяснение с форматами также.

Answer 1

Знаковый формат Q1.31 - это полностью дробный формат, способный представлять операнды от -1 до почти +1. Коэффициент масштабирования составляет 2³¹. Это означает, что когда каждый операнд Q1.31 хранится в 32-разрядном целом числе со знаком, мы можем сгенерировать произведение Q1.31, вычислив полное произведение двойной ширины целых чисел со знаком, а затем сдвинув результат вправо на 31 бит. Сдвиг вправо необходим, потому что продукт включает масштабный коэффициент дважды, а сдвиг действует как деление, которое удаляет один экземпляр масштабного коэффициента.

Мы можем вычислить произведение двойной ширины двух 32-разрядных целых чисел, отдельно вычислив старшие и младшие 32 бита полного произведения. Младшие 32 бита вычисляются тривиально как обычное произведение двух входов. Чтобы вычислить старшие 32 бита, нам нужно написать функцию mul32hi(), Чтобы не использовать более широкий тип (т. Е. Тот, который использует более 32 бит) в промежуточных вычислениях, нам нужно разбить исходные операнды на две половины, вычислить их частичные произведения, а затем соответствующим образом сложить эти частичные произведения.

Обратите внимание, что различные процессоры предоставляют аппаратную инструкцию, которая реализует функциональность mul32hi(), В этом случае можно использовать соответствующий встроенный код или немного встроенного ассемблерного кода, если встроенного кода не существует, вместо использования кода эмуляции, представленного здесь.

Это помогает свести проблему сначала к соответствующему умножению без знака, umul32hi()затем извлеките подписанный результат из этого путем определения представления дополнения 2 (что предполагается в следующем коде C):

#include <stdint.h>

/* compute the upper 32 bits of the product of two unsigned 32-bit integers */
uint32_t umul32hi (uint32_t a, uint32_t b)
{
    /* split operands into halves */
    uint32_t al = (uint16_t)a;
    uint32_t ah = a >> 16;
    uint32_t bl = (uint16_t)b;
    uint32_t bh = b >> 16;
    /* compute partial products */
    uint32_t p0 = al * bl;
    uint32_t p1 = al * bh;
    uint32_t p2 = ah * bl;
    uint32_t p3 = ah * bh;
    /* sum partial products */
    uint32_t cy = ((p0 >> 16) + (uint16_t)p1 + (uint16_t)p2) >> 16;
    return p3 + (p2 >> 16) + (p1 >> 16) + cy;
}

/* compute the upper 32 bits of the product of two signed 32-bit integers */
int32_t mul32hi (int32_t a, int32_t b)
{
    return umul32hi (a, b) - ((a < 0) ? b : 0) - ((b < 0) ? a : 0);
}

/* compute the full 64-bit product of two signed 32-bit integers */
void mul32wide (int32_t a, int32_t b, int32_t *rhi, int32_t *rlo)
{
    *rlo = a * b;           /* bits <31:0> of the product a * b */
    *rhi = mul32hi (a, b);  /* bits <63:32> of the product a * b */
}

/* compute the product of two signed Q1.31 fixed-point numbers */    
int32_t mul_q_1_31 (int32_t a, int32_t b)
{
    int32_t hi, lo;
    mul32wide (a, b, &hi, &lo);
    /* Q1.31 is scaled by 2**31, trim out scale factor */
    return (int32_t)(((uint32_t)hi << 1) | ((uint32_t)lo >> 31));
}

Я интерпретировал запрос "оставить случай переполнения", чтобы означать игнорирование переполнения. Как следствие, умножение -1 (0x80000000) на -1 (0x80000000) с mul_q_1_31() вернет -1 (0x80000000).

Answer 2

На следующем сайте предлагается 32-разрядная реализация библиотеки ANSI-C для работы с Q-числами в целом: http://www.ti.com/tool/sprc542

Я не пробовал это и не могу поручиться за то, что он будет или не будет делать для вас, но на этом сайте есть ссылка, где вы можете запросить исходный код.