Ответ 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;
}
}