Примечание. Как указано в комментариях @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] = 0x17upperLow хранит младший байт частного: upperLow[0xa7] = 0xdbupperRem сохраняет остаток: upperRem[0xa7] = 3
И мы вычисляем частное и остаток от байта lower:
0x32 / 7 = 0x07
0x32 % 7 = 1
Итак, нам понадобятся две таблицы:
lowerLow хранит младший байт частного: lowerLow[0x32] = 0x07lowerRem сохраняет остаток: lowerRem[0x32] = 1
Теперь нам нужно собрать окончательный ответ. Остаток - это сумма двух остатков. Поскольку каждый остаток находится в диапазоне [0,6], сумма находится в диапазоне [0,12]. Таким образом, мы можем использовать два поиска по 13 байт, чтобы преобразовать сумму в окончательный остаток и перенос.
Младший байт частного представляет собой сумму этого переноса и значений из таблиц lowerLow и upperLow. Обратите внимание, что сумма может генерировать перенос в старший байт.
Старший байт частного представляет собой сумму этого переноса и значения из таблицы 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;
}
}
person
user3386109
schedule
19.07.2018
022222вот так. Я думаю, что вы также можете использовать LUT для переключения 3 в вышеупомянутом подходе, потому что у вас нет переключателя ствола. Таким образом, вы также можете выполнить параллельную операцию по модулю 7, потому что это просто сумма цифр в базе 8 по модулю 7. - person phuclv schedule 19.07.2018