汇编语言使用有符号整数乘法数学来执行移位

Question

这有点转机。

通常人们会尝试使用移位来执行乘法，而不是相反。

在Hitachi/Motorola 6309 上没有移位n 位。只有一位移动。

但是有一个 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

您是否使用定点乘法逆运算将高半结果用于右移？

如果您只是左移，乘以 0x8000 应该可行。 无论输入被视为有符号还是无符号，NxN => 2N 位乘法的低半部分是相同的。或者您是否需要 16 位输入的 32 位移位结果？

对于小的移位计数，乘法指令实际上比几个 1 位移位更快吗？（如果仅使用 2 或 3 add same,same 链或左移指令链，2 或 3 的编译时间常数计数会更快，我不会感到惊讶。）

无论如何，对于 15 的编译时常量移位计数，也许只需乘以 1<<14 然后 做最后一次计数1 位移位 (add same,same).

或者，如果您的 ISA 进行了循环，则向右循环 1 并屏蔽掉低位，跳过乘法。或者将一个寄存器置零，将低位右移到进位标志中，然后循环进位到置零寄存器的顶部。

（后者可能对没有大立即数且不能在一条指令中 "mask away all the low bits" 的 ISA 有用。或者只有 RCR 而没有 ROR 的 ISA。我不知道 6309完全)

如果您正在使用 运行时计数从 table 中查找乘数，可能会针对这种情况进行分支，或者调整您的 LUT，以便每个条目都需要一个额外的 1 位移位，所以你可以做 mul(lut[count]) 和一个无条件的额外移位。

（仅当您不需要支持零班次计数时才有效。）

Answer 2

我从问题描述中可以看出，通过使用 unsigned 16x16->32 位乘法，可以实现 32 位移位。这可以很容易地通过利用二进制补码整数表示从带符号的 16x16->32 乘法指令合成。如果两个因数为a和b，当a为负时，在有符号乘积的高16位上加上b，在a上加上a当 b 为负时，对有符号乘积的高 16 位将给出无符号乘法结果。

以下 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/Motorola 6309 架构。我假设它使用一个特殊的 32 位寄存器来保存宽乘法的结果，从中可以提取高和低一半到 16 位通用寄存器中，然后可以将条件更正应用于保存高 16 位。

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 ,,,,,,,,00,00,00,00
   fdb 00,00,00,00

汇编语言使用有符号整数乘法数学来执行移位

Assembly language using signed int multiplication math to perform shifts

algorithm

assembly

bit-shift

motorola

integer-arithmetic