Язык ассемблера, использующий математику умножения со знаком для выполнения смен

Question

Это немного оборачивается.

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

На Hitachi / Motorola 6309 нетсдвиг на n бит. Существует только сдвиг на 1 бит.

Однако существует умножение со знаком 16 бит x 16 бит (обеспечивает 32-битный результат со знаком).

(EDIT) Использование этого не является проблемой дляСдвиг 16 бит (влево), однако я пытаюсь использовать 2 x 16x16 знаковых мультов для сдвига 32 бит. Старшее слово результата для сдвига младшего слова является проблемой. (Это имеет смысл?)

Какой-то псевдокод может помочь:

result.highword = low word of (val.highword * shiftmulttable[shift])
temp = val.lowword * shiftmulttable[shift]
result.lowword = temp.lowword
result.highword = or (result.highword, temp.highword)
(with some magic on temp.highword to consider signed values)

Я использовал свою логику в попытке использовать эту инструкцию для выполнения смен, но пока у меня естьне удалось.

Я легко могу добиться любого сдвига положительного значения от 0 до 14, но когда дело доходит до сдвига на 15 бит (мульт на 0x8000) или сдвига любых отрицательных значений, определенные комбинации значений требуют либо:

• добавление результата к 1
• добавление результата к 2
• добавление 1 к результату
• без изменений к результату

И я просто не вижу никакой картины этих значений.

Любые идеи приветствуются!

Answer 1

Насколько я могу судить по описанию проблемы, реализация 32-битного сдвига будет работать так, как нужно, используя unsigned 16x16-> 32-битное умножение. Это можно легко синтезировать из знаковой команды умножения 16x16-> 32, используя целочисленное представление дополнения к двум. Если двумя факторами являются a и b, добавление b к старшим 16 битам подписанного продукта, когда a отрицательно, и добавление a к старшим 16 битам подписанного продуктапроизведение при отрицательном b даст нам результат умножения без знака.

Следующий код C реализует этот подход и полностью его тестирует:

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

/* signed 16x16->32 bit multiply. Hardware instruction */
int32_t mul16_wide (int16_t a, int16_t b)
{
    return (int32_t)a * (int32_t)b;
}

/* unsigned 16x16->32 bit multiply (synthetic) */
int32_t umul16_wide (int16_t a, int16_t b)
{
    int32_t p = mul16_wide (a, b); // signed 16x16->32 bit multiply
    if (a < 0) p = p + (b << 16);  // add 'b' to upper 16 bits of product
    if (b < 0) p = p + (a << 16);  // add 'a' to upper 16 bits of product
    return p;
}

/* unsigned 16x16->32 bit multiply (reference) */
uint32_t umul16_wide_ref (uint16_t a, uint16_t b)
{
     return (uint32_t)a * (uint32_t)b;
}

/* test synthetic unsigned multiply exhaustively */
int main (void)
{
    int16_t a, b;
    int32_t res, ref;
    uint64_t count = 0;

    a = -32768;
    do {
        b = -32768;
        do {
            res = umul16_wide (a, b);
            ref = umul16_wide_ref (a, b);
            count++;
            if (res != ref) {
                printf ("!!!! a=%d b=%d res=%d ref=%d\n", a, b, res, ref);
                return EXIT_FAILURE;
            }
            if (b == 32767) break;
            b = b + 1;
        } while (1);
        if (a == 32767) break;
        a = a + 1;
    } while (1);
    printf ("test cases passed: %llx\n", count);
    return EXIT_SUCCESS;
}

Я не знаком с Hitachi /Моторола 6309 с архитектурой. Я предполагаю, что он использует специальный 32-битный регистр для хранения результата широкого умножения, из которого старшая и младшая половина могут быть извлечены в 16-битные регистры общего назначения, а затем условные поправки могут быть применены к регистру, содержащемустаршие 16 бит.

Answer 2

Используете ли вы мультипликативные инверсии с фиксированной точкой, чтобы использовать высокий половинный результат для сдвига вправо?

Если вы просто сдвигаете влево, умножение на 0x8000 должно работать. Нижняя половина умножения NxN => 2N-бит одинакова независимо от того, обрабатываются ли входы как подписанные или без знака. Или вам нужен 32-битный результат сдвига с вашего 16-битного входа?

Является ли инструкция умножения на самом деле быстрее, чем несколько 1-битных сдвигов для небольших подсчетов? (Я не удивлюсь, если бы счетчики времени компиляции 2 или 3 были бы быстрее только с цепочкой из 2 или 3 add same,same или инструкций влево.)

---

В любом случае, для счетчика сдвига с постоянной во время компиляции 15 , возможно, просто умножьте на 1<<14, а затем выполните последний подсчет с 1-разрядным сдвигом (add same,same) .

Или, если ваш ISA вращается, поверните вправо на 1 и замаскируйте младшие биты, пропуская умножение. Или обнулите регистр, сдвиньте младший бит вправо в флаг переноса, затем поверните сквозной перенос в верхнюю часть обнуленного регистра.

(Последний может быть полезен на ISA, который не имеетбольшое значение сразу же и не может «замаскировать все младшие биты» в одной инструкции. Или ISA, который имеет только RCR, а не ROR. Я вообще не знаю 6309)

---

Если выиспользуя счетчик времени выполнения, чтобы найти множитель из таблицы , возможно, ответвление для этого случая или настроить LUT так, чтобы каждая запись нуждалась в дополнительном 1-битном сдвиге, чтобы вы могли сделать mul(lut[count]) и безусловныйдополнительная смена.

(работает только в том случае, если вам не нужно поддерживать нулевой счетчик смещения).

Answer 3

Не то чтобы было много заинтересованных людей, которые хотели бы увидеть код 6309, но вот он:

Совместим с OS9 C ABI.

Указатель на результат и выдвинутые аргументыстек справа налево.

U,PC,val(4bytes),shift(2bytes),*result(2bytes)
0 2  4           8              10

:

* 10,s pointer to long result
* 4,s 4 byte value
* 8,s 2 byte shift
* x = pointer to result
  pshs u
  ldx 10,s * load pointer to result
  ldd 8,s * load shift
* if shift amount is greater than 31 then
* just return zero.  OS9 C standard.
  cmpd #32
  blt _10x
  ldq #0
  stq 4,s
  bra _13x
* if shift amount is greater than 16 than
* move bottom word of value into top word 
* and clear bottom word  
_10x
  cmpb #16
  blt _1x
  ldu 6,s
  stu 4,s
  clr 6,s
  clr 7,s
_1x
* setup pointer u and offset e into mult table _2x
  leau _2x,pc
  andb #15
* if there is no shift value just return value
  beq _13x
  aslb * need to double shift to use as word table offset
  stb 8,s     * save double shft
  tfr b,e 
* shift top word q = val.word.high * multtab[shft]
  ldd 4,s
  muld e,u
  stw ,x * result.word.high = low word of mult
* shift bottom word q = val.word.low * multtab[shft]
  lde 8,s     * reload double shft
  ldd 6,s
  muld e,u
  stw 2,x     * result.word.low = low word of mult
* The high word or mult needs to be corrected for sign
* if val is negative then muld will return negated results
* and need to un negate it
  lde 8,s     * reload double shift
  tst 4,s     * test top byte of val for negative
  bge _11x
  addd e,u    * add the multtab[shft] again to top word 
_11x
* if multtab[shft] is negative (shft is 15 or shft<<1 is 30)
* also need to un negate result
  cmpe #30
  bne _12x
  addd 6,s    * add val.word.low to top word
_12x
* combine top and bottom and save bottom half of result 
  ord ,x
  std ,x
  bra _14x
* this is only reached if the result is in value (let result = value) 
_13x
  ldq 4,s     * load value
  stq ,x      * result = value
_14x
  puls u,pc
_2x fdb $01,$02,$04,$08,$10,$20,$40,$80,$0100,$0200,$0400,$0800
   fdb $1000,$2000,$4000,$8000