Быстрое подписанное 16-разрядное деление на 7 для 6502

Ответ 1

Примечание. Как отмечал @Damien_The_Unbeliever в комментариях, таблицы upperHigh и lowerLow идентичны. Таким образом, их можно объединить в одну таблицу. Однако эта оптимизация сделает код более трудным для чтения, а объяснение сложнее написать, поэтому объединение таблиц остается в качестве упражнения для читателя.

В приведенном ниже коде показано, как сгенерировать фактор и остаток при делении 16-разрядного значения без знака на 7. Простейший способ объяснить код (IMO) приведен в примере, поэтому рассмотрим деление 0xa732 на 7. Ожидаемый результат:

quotient = 0x17e2
remainder = 4  

Мы начнем с рассмотрения ввода как двух 8-битных значений, upper байта и lower байта. upper байты 0xa7 и lower байт 0x32.

Мы вычисляем коэффициент и остаток от upper байта:

0xa700 / 7 = 0x17db
0xa700 % 7 = 3 

Поэтому нам нужны три таблицы:

• upperHigh хранит старший байт фактора: upperHigh[0xa7] = 0x17
• upperLow хранит upperLow байт частного: upperLow[0xa7] = 0xdb
• upperRem хранит остаток: upperRem[0xa7] = 3

И мы вычисляем коэффициент и остаток от lower байта:

0x32 / 7 = 0x07
0x32 % 7 = 1

Поэтому нам нужны две таблицы:

• lowerLow хранит lowerLow байт частного: lowerLow[0x32] = 0x07
• lowerRem хранит остаток: lowerRem[0x32] = 1

Теперь нам нужно собрать окончательный ответ. Остаток представляет собой сумму двух остатков. Поскольку каждый остаток находится в диапазоне [0,6], сумма находится в диапазоне [0,12]. Таким образом, мы можем использовать два 13-байтовых поиска для преобразования суммы в конечный остаток и перенос.

Низкий байт частного представляет собой сумму этого переноса и значений из lowerLow и upperLow. Обратите внимание, что сумма может генерировать перенос в старший байт.

Высокий байт частного представляет собой сумму этого переноса и значение из upperHigh таблицы upperHigh.

Итак, чтобы завершить пример:

remainder = 1 + 3 = 4              // simple add (no carry in)
lowResult = 0x07 + 0xdb = 0xe2     // add with carry from remainder
highResult = 0x17                  // add with carry from lowResult

Код сборки для его реализации состоит из 7 табличных запросов, команды добавления без переноса и двух инструкций с дополнением к переносу.

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

uint8_t upperHigh[256];  // index:(upper 8 bits of the number)  value:(high 8 bits of the quotient)
uint8_t upperLow[256];   // index:(upper 8 bits of the number)  value:(low  8 bits of the quotient)
uint8_t upperRem[256];   // index:(upper 8 bits of the number)  value:(remainder when dividing the upper bits by 7)
uint8_t lowerLow[256];   // index:(lower 8 bits of the number)  value:(low  8 bits of the quotient)
uint8_t lowerRem[256];   // index:(lower 8 bits of the number)  value:(remainder when dividing the lower bits by 7)
uint8_t carryRem[13]    = { 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1 };
uint8_t combinedRem[13] = { 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5 };

void populateLookupTables(void)
{
    for (uint16_t i = 0; i < 256; i++)
    {
        uint16_t upper = i << 8;
        upperHigh[i] = (upper / 7) >> 8;
        upperLow[i] = (upper / 7) & 0xff;
        upperRem[i] = upper % 7;

        uint16_t lower = i;
        lowerLow[i] = lower / 7;
        lowerRem[i] = lower % 7;
    }
}

void divideBy7(uint8_t upperValue, uint8_t lowerValue, uint8_t *highResult, uint8_t *lowResult, uint8_t *remainder)
{
    uint8_t temp = upperRem[upperValue] + lowerRem[lowerValue];
    *remainder = combinedRem[temp];
    *lowResult = upperLow[upperValue] + lowerLow[lowerValue] + carryRem[temp];
    uint8_t carry = (upperLow[upperValue] + lowerLow[lowerValue] + carryRem[temp]) >> 8;  // Note this is just the carry flag from the 'lowResult' calcaluation
    *highResult = upperHigh[upperValue] + carry;
}

int main(void)
{
    populateLookupTables();

    uint16_t n = 0;
    while (1)
    {
        uint8_t upper = n >> 8;
        uint8_t lower = n & 0xff;

        uint16_t quotient1  = n / 7;
        uint16_t remainder1 = n % 7;

        uint8_t high, low, rem;
        divideBy7(upper, lower, &high, &low, &rem);
        uint16_t quotient2 = (high << 8) | low;
        uint16_t remainder2 = rem;

        printf("n=%u q1=%u r1=%u q2=%u r2=%u", n, quotient1, remainder1, quotient2, remainder2);
        if (quotient1 != quotient2 || remainder1 != remainder2)
            printf(" **** failed ****");
        printf("\n");

        n++;
        if (n == 0)
            break;
    }
}

Ответ 2

В Unsigned Integer Division Routines для 8-битного деления на 7:

;Divide by 7 (From December '84 Apple Assembly Line)
;15 bytes, 27 cycles
  sta  temp
  lsr
  lsr
  lsr
  adc  temp
  ror
  lsr
  lsr
  adc  temp
  ror
  lsr
  lsr

Оценка около 100 циклов со сдвигами была довольно точной: 104 цикла до последнего времени, 106 циклов, не считая rts, 112 циклов для всей функции.
ПРИМЕЧАНИЕ: после сборки для C64 и использования эмулятора VICE для C64 я обнаружил, что алгоритм не работает, например 65535 дает 9343, а правильный ответ - 9362.

   ; for 16 bit division  by 7
   ; input:
  ;   register A is low byte
  ;   register X is high byte
  ; output 
  ;   register A is low byte
  ;   register X is high byte
  ;
  ; memory on page zero
  ; temp     is on page zero, 2 bytes
  ; aHigh    is on page zero, 1 byte
  --
  sta temp
  stx temp+1
  stx aHigh
  --
  lsr aHigh
  ror a
  lsr aHigh
  ror a
  lsr aHigh
  ror a
  ---
  adc temp
  tax
  lda aHigh
  adc temp+1
  sta aHigh
  txa
  --
  ror aHigh
  ror a
  lsr aHigh
  ror a
  lsr aHigh
  ror a
  --
  adc temp
  tax
  lda aHigh
  adc temp+1
  sta aHigh
  txa
  --
  ror aHigh
  ror a
  lsr aHigh
  ror a
  lsr aHigh
  ror a     -- 104 cycles
  ;-------
  ldx aHigh  ; -- 106
  rts        ; -- 112 cycles