0

我在 16 位 x86 asm 中有这个重复的迭代过程

rec_loop:
  mul bx          ; constant value of 0x11bf
  add ax, 0x4743
  loop rec_loop

它运行了几次，但对于我们的例子，假设它运行了 3 次，现在完成后我得到dx:ax并且需要恢复ax该程序的初始值（初始dx值为 0）。乍一看，我们可以看到关于 dx 的信息在这个过程中丢失了，因为用新mul的覆盖了最后dx一个。

如果可能的话，我正在寻找一种方法来扭转这个过程，当然假设上面的代码不能改变。

如果我忘记解释某事或没有提供有关问题的足够详细信息，请告诉我，我会回答。

4

1 回答 1

2

计算 x n+1 := (a * x n + c) mod m, a = 0x11bf, c = 0x4743, m= 2 16形成一个伪随机数生成器。具体来说，一个周期为 2 11的线性同余生成器。显然这不是一个高质量的 PRNG，但对于只需要看起来有点随机的数据的用例来说可能就足够了。我注意到该问题并未说明使用此代码的上下文。

x i的序列（这里是在 中连续生成的AX）可以通过使用模乘逆 a逆来反转，如下所示：x n-1 = a逆* (x n - c) mod m。在这种情况下，模乘逆是0xde3f。

请注意，DX在向后计算中不需要 的值，并且在序列中的任何点都可以根据AX需要轻松确定。下面的乘法逆的确定使用基于定义的朴素方法。对于较大的操作数大小，这是非常低效的，人们可能希望使用扩展欧几里得算法。

简单的 C99 代码，用于试验乘法逆的计算和 中的值序列的反转AX：

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

#define X_0   (0xc001)
#define ITERS (3)

uint32_t modular_inverse (uint32_t a, uint32_t m)
{
    for (uint32_t x = 1; x < m; x++) {
        if (((a % m) * (x % m)) % m == 1) {
            return x;
        }
    }
    printf ("no inverse found\n");
    return 0;
}

uint16_t umul16_lo (uint16_t a, uint16_t b)
{
    return (uint16_t)(a * b);
}

uint16_t umul16_hi (uint16_t a, uint16_t b)
{
    return (uint16_t)(((uint32_t)a * b) >> 16);
}

int main (void)
{
    const uint16_t a = 0x11bf;   // multiplier of PRNG
    const uint16_t c = 0x4743;   // additive offset of PRNG
    const uint32_t m = 0x10000U; // modulo of PRNG
    uint16_t a_inverse;

    a_inverse = modular_inverse (a, m);

    printf ("a_inverse = %04x\n", a_inverse);

    const uint16_t bx = a; 
    uint16_t dx = 0;
    uint16_t ax = X_0;

    printf ("starting values:    ax=%04x  dx=%04x  bx=%04x\n", ax, dx, bx);
    printf ("forward computation\n");

    for (int i = 0; i < ITERS; i++) {
        dx = umul16_hi (ax, bx);
        ax = umul16_lo (ax, bx) + c;
    }
    printf ("after %d iterations: ax=%04x  dx=%04x  bx=%04x\n", ITERS, ax, dx, bx);
    printf ("backward computation\n");

    for (int i = 0; i < ITERS; i++) {
        ax = umul16_lo (ax - c, a_inverse);
    }

    printf ("after %d iterations: ax=%04x\n", ITERS, ax);

    return EXIT_SUCCESS;
}
于 2022-02-15T00:08:29.557 回答