Mic1, язык микро-ассемблера, создание множителя

Question

В настоящее время я работаю с языком микро-ассемблера (MAL) и использую симулятор Mic1mmv для его тестирования. Я пытаюсь понять, как создать программу, которая умножает два числа, но я пытаюсь понять, как это сделать.

Вот следующий код MAL для сложения и вычитания:

iadd1   MAR = SP = SP - 1; rd       // Read in next-to-top word on stack
iadd2   H = TOS                     // H = top of stack
iadd3   MDR = TOS = MDR + H; wr; goto Main1 // Add top two words; write to top of stack

isub1   MAR = SP = SP - 1; rd       // Read in next-to-top word on stack
isub2   H = TOS                    // H = top of stack
isub3   MDR = TOS = MDR - H; wr; goto Main1 // Do subtraction; write to top of stack

В качестве примера, скажем, я хочу сделать 3 х 4. Мои мысли о том, чтобы сделать это, - взять 3 и добавить его с другим 3 4 раза (3+3+3+3), но мне еще предстоит выяснить, как Я могу сделать цикл if / else / или обратный отсчет, который отслеживает, сколько раз он был добавлен вместе.

Если кто-нибудь знает, как решить эту проблему или есть какие-либо советы по этому поводу, я был бы очень благодарен, спасибо!

Answer 1

Я знаю, что этот вопрос немного устарел, но, возможно, я все еще смогу помочь кому-то еще, кто пытается понять проблему.

Очевидный ответ

Учитывая умножение. Как вы уже догадались, очевидный ответ, который приходит в голову в первую очередь, - это просто вычислить b + b + b + b + [...]. И на самом деле это правильный подход, хотя необходимые циклы вычислений теперь полностью зависят от b, поэтому чем больше b становится, тем больше времени потребуется для вычисления этого подхода.

Лучший способ

Но, конечно, есть выход. Учитывая предыдущее умножение a * b где оба числа беззнаковые и 32-битные, b можно описать как сумму b(i) * 2^(i)(0 <= я <= 32). Теперь, если мы умножим это на a, мы получим b(i) * (a * 2^(i))(0 <= я <= 32). Чтобы объяснить это словами, мы перебираем каждый из битов и умножаем их соответствующее значение в двоичном формате. Результатом теперь является просто сумма каждого расчета. Остается 32 вычисления.

В коде C это будет выглядеть примерно так:

      unsigned multiply(unsigned a, unsigned b) { 
    unsigned i, product = 0;
    for (i = 0; i < 32; ++i) {
        if ((b & 1) == 1) { 
            product = product + a;
        }
        a = a << 1;
        b = b >> 1;
    } 
    return product;
}

Но этот код как есть пока не может быть переведен в микрокоманды.

1. for а также if нельзя перевести 1:1
2. Мы ограничены возможностями ALU, а именно операциями переключения
3. ALU может выдавать только числа 0, 1 и -1.

В следующем, втором подходе мы заменяем цикл for на цикл while. Это возможно, потому что мы каждый раз половину b, сдвигая биты, поэтому b должен быть равен 0 в одной точке. Явно после 32 смен.

      unsigned multiply(unsigned a, unsigned b) { 
    unsigned product = 0;
    while (b != 0) {
        if ((b & 1) == 1) { 
            product = product + a;
        }
        a = a << 1;
        b = b >> 1;
    }
    return product;
}

Теперь мы можем заменить более высокие управляющие структуры, такие как цикл while:

      unsigned multiply(unsigned a, unsigned b) { 
    unsigned product = 0;
loop:
    if (b == 0) goto finish;
    if ((b & 1) == 0) goto next; 
    product = product + a;
next:
    a = a << 1;
    b = b >> 1;
    goto loop;
finish:
    return product; 
}

Теперь мы можем начать проецировать его на микрофон-1.

1. Переменная a находится под переменной b в стеке. Поэтому сначала мы должны инициировать инструкцию чтения. Это означает, что a будет в регистре MDR.
2. Переменная b находится на вершине стека. Это означает, что его значение уже находится в регистре TOS.
3. Для сохранения и обновления конечного результата я назвал его 'product', нам остался регистр OPC, так как это единственный другой регистр без ограничений.

Мы также должны проецировать все наши операции на микрофон-1.

1. Проверить, является ли b == 0, можно немедленно, посмотрев на Z-флаг (нулевой флаг, равен 1, если выход ALU равен 0)
2. Проверка, если b & 1 == 0 должен быть выполнен в два этапа, поэтому мы используем регистр H для хранения 1
3. Сдвиг a влево на 1 не может быть выполнен непосредственно ALU, но a = a << 1 не что иное, как a = a + a, потому что мы находимся в двоичном
4. Сдвиг b вправо на 1 может быть выполнен непосредственно с помощью ALU.

После всего этого давайте посмотрим, где мы находимся:

      unsigned multiply(unsigned mdr, unsigned tos) { 
    unsigned z, h, opc = 0;
loop:
    z = tos;
    if (z == 0) goto finish; h = 1;
    z = tos & h;
    if (z == 0) goto next;
    h = mdr;
    opc = opc + h; 
next:
    h = mdr;
    mdr = mdr + h; tos = tos >> 1; goto loop;
finish:
    return opc;
}

Теперь мы можем перевести это прямо в программу на микроассемблере:

      imul1  | MAR = SP = SP - 1; rd
imul2  | OPC = 0
loop   | Z = TOS; if (Z) goto finish; else goto imul4 
imul4  | H=1
imul5  | Z = TOS AND H; if (Z) goto next; else goto imul6 
imul6  | H = MDR
imul7  | OPC = OPC + H
next   | H = MDR
imul9  | MDR = MDR + H
imul10 | TOS = TOS >> 1; goto loop
finish | MDR = TOS = OPC; wr; goto Main1