Убедитесь, что значение в регистре является произведением 3 в AVR Studio, используя сборку.

Question

Я хочу убедиться, что число в регистре является умножением на 3, используя avr studio и язык asm, но на avr 8515, поэтому синтаксис div отсутствует.

я уже пробовал пару методов, таких как добавление регистра и 0b0011, ожидая, что будет установлен флаг переноса, но это не так

Answer 1

Итак, самый простой способ — позволить avr-gcc скомпилировать фрагмент кода C, а затем просмотреть сборку ¹ , которую он сгенерирует:

Для 8-битного беззнакового значения рассмотрим следующий C99:

      #include <stdint.h>
#include <stdbool.h>

bool is_udiv3_8 (uint8_t x)
{
    return x % 3 == 0;
}

С чем-то вроде

      > avr-gcc x.c -mmcu=atmega8515 -O2 -S

мы получаемx.s(как вариант, добавьте-save-tempsна обычную компиляцию, а затем перехватить файл *.s).

      is_udiv3_8:
    ldi r25,lo8(-85) ;1
    mul r24,r25      ;2
    mov r25,r1       ;3
    clr __zero_reg__ ;4
    lsr r25          ;5
    mov r18,r25      ;6
    lsl r18          ;7
    add r25,r18      ;8
    ldi r18,lo8(1)   ;9
    cpse r24,r25     ;10
    ldi r18,0        ;11
    mov r24,r18      ;12
    ret

Что делает avr-gcc, так это умножает входные данные на -256/3 и принимает старший байт продукта как частное после деления на 3. После некоторых корректировок он возвращает R24 True (1), если входные данные делятся на 3. и False (0) в противном случае.

Вы можете расширить это до 16-битных значений, но вам понадобится старшее слово умножения 16×16=32.

В этот момент вы помните ² , что натуральное число N, записанное в базе B, делится на B+1 тогда и только тогда, когда знакопеременная перекрестная сумма по цифрам в базе B делится на B+1.

Например, по основанию B=2: натуральное число N делится на 3 тогда и только тогда, когда знакопеременная перекрестная сумма битов N делится на 3.

Написано на ассемблере:

• Сначала выполняется цикл по битам, чтобы получить двоичную перекрестную сумму. Для скорости вы бы развернули этот цикл, который получил бы 8sbrsс и 8sbrcс.

• Перекрестная сумма q удовлетворяет условию -8 <= q <= 8. Отрицание не меняет того, делится ли q на 3, поэтому продолжайте с |q| что неотрицательно.

• Вычитайте 3, пока результат не станет 0, 1 или 2.

• Возвращайте True, если значение достигло 0, и False в противном случае (оно достигло 1 или 2).

      .text
.global is_div3_asm

is_div3_asm:
    ;; R26 holds R25:R24 mod 3
    clr r26
.Loop_bits:
    ;; Loop over all bits of R25:R24 to compute the alternating cross sum
    ;; over the binary digits of R25:R24.
    sbiw r24, 0
    breq .Loop_done
    sbrc r24, 0 $ inc  r26
    sbrc r24, 1 $ dec  r26
    lsr  r25 $ ror r24
    lsr  r25 $ ror r24
    rjmp .Loop_bits
.Loop_done:
    ;; r26 = abs(r26)
    sbrc r26, 7
    neg  r26
    ;; Now we have 0 <= r26 <= 8, so reduce to r26 < 3...
    cpi  r26, 3
    brlt .Ltobool
    subi r26, 3
    ;; ...now we have 0 <= r26 <= 5, so at most one more sub 3 will do.
    cpi  r26, 3
    brlt .Ltobool
    subi r26, 3
.Ltobool:
    ;; Return a bool in R24 as of avr-gcc ABI.
    ldi r24, 1                  ; True
    cpi r26, 0
    breq .Ldone
    ldi r24, 0                  ; False
.Ldone:    
    ret

Эта функция соответствует ABI avr-gcc и соглашению о вызовах . Вы можете использовать его из C/C++ с помощью прототипа.

      extern bool is_div3_asm (uint16_t); // C
extern "C" bool is_div3_asm (uint16_t); // C++

---

¹ Обратите внимание, что существуют разные диалекты ассемблера. В этом ответе используется диалект сборки GNU, поскольку он совместим с ассемблером GNU и создается с помощью avr-gcc и avr-g++.

² Результат на самом деле более сильный: натуральное число N принадлежит тому же самому классу покоя по модулю B+1, что и знакопеременная перекрестная сумма N по основанию B. Доказательство представляет собой всего лишь несколько строк модульной арифметики и сводится к следующему: B ≡ -1. мод Б+1.

Answer 2

Это всего лишь небольшой комментарий, и разработка , но он слишком длинный и сложный, чтобы быть комментарием Stackoverflow, поэтому это ответ Stackoverflow вики-сообщества.

Я скомпилировал 8, 16, 24 и 32-битные версии на с разными версиями avr-gcc (12.2.0 и 5.4.0) с одинаковыми параметрами компиляции (-std=c99 -O2 -g -mmcu=atmega8515). Оказывается, код, созданный avr-gcc 12.2.0, значительно короче, чем код, созданный avr-gcc 5.4.0.

Поскольку @emacs сводит меня с ума от ответаответ @emacs сводит меня с ума, он работает с относительно сложным кодом из avr-gcc 5.4.0, возможно, будет полезно взглянуть и на более простой код из 12.2.0.

Вариант из avr-gcc 5.4.0, похоже, является тем, над чем работает :

      is_udiv8_by_3:
        ldi r25,lo8(-85)  /* 1 */
        mul r24,r25       /* 2 */
        mov r25,r1        /* 1 */
        clr __zero_reg__  /* 1 */
        lsr r25           /* 1 */
        mov r18,r25       /* 1 */
        lsl r18           /* 1 */
        add r25,r18       /* 1 */
        ldi r18,lo8(1)    /* 1 */
        cpse r24,r25      /* 1 */
        ldi r18,0         /* 1 */
        mov r24,r18       /* 1 */
        ret               /* 13 cycles plus ret */

вариант из avr-gcc 12.2.0:

      is_udiv8_by_3:
        ldi r25,lo8(-85)  /* 1 */
        mul r24,r25       /* 2 */
        mov r25,r0        /* 1 */
        clr r1            /* 1 */
        ldi r24,lo8(1)    /* 1 */
        cpi r25,lo8(86)   /* 1 */
        brlo .L2          /* 2/1 */
        ldi r24,0         /* -/1 */
.L2:
        ret               /* 9 cycles plus ret */

The uint16_tвариант из avr-gcc 12.2.0 ненамного длиннее, чемuint8_tвариант из avr-gcc 5.4.0:

      is_udiv16_by_3:
        ldi r20,lo8(-85)  /* 1 */
        ldi r21,lo8(-86)  /* 1 */
        mul r24,r20       /* 2 */
        movw r18,r0       /* 2 */
        mul r24,r21       /* 2 */
        add r19,r0        /* 1 */
        mul r25,r20       /* 2 */
        add r19,r0        /* 1 */
        clr r1            /* 1 */
        ldi r24,lo8(1)    /* 1 */
        cpi r18,86        /* 1 */
        sbci r19,85       /* 1 */
        brlo .L5          /* 2/1 */
        ldi r24,0         /* -/1 */
.L5:
        ret               /* 18 cycles plus ret */

Кстати, количество цикловis_div3_asmфункция из зависит от входного значения и занимает более 18 циклов даже для одной итерации.Loop_bitsпетля.

При увеличении размера шрифта до 24 бит (__uint24вариант) и 32-битной версии avr-gcc 12.2.0 наконец начинает вызывать функцию деления__udivmodpsi4:

      is_udiv24_by_3:
        ldi r18,lo8(3)
        ldi r19,0
        ldi r20,0
        rcall __udivmodpsi4
        ldi r24,lo8(1)
        or r18,r19
        or r18,r20
        breq .L7
        ldi r24,0
.L7:
        ret

The uint32_tвызывает другую функцию деления__udivmodsi4и намного длиннее:

      is_udiv32_by_3:
        push r28
        push r29
        rcall .
        rcall .
        in r28,__SP_L__
        in r29,__SP_H__
        ldi r18,lo8(3)
        ldi r19,0
        ldi r20,0
        ldi r21,0
        rcall __udivmodsi4
        std Y+1,r22
        std Y+2,r23
        std Y+3,r24
        std Y+4,r25
        ldi r24,lo8(1)
        ldd r18,Y+1
        ldd r19,Y+2
        ldd r20,Y+3
        ldd r21,Y+4
        or r18,r19
        or r18,r20
        or r18,r21
        breq .L12
        ldi r24,0
.L12:
        pop __tmp_reg__
        pop __tmp_reg__
        pop __tmp_reg__
        pop __tmp_reg__
        pop r29
        pop r28
        ret

Итак, поиск других алгоритмов, таких как альтернативный алгоритм перекрестной суммы от godbolt.org@emacs, сводит меня с ума от ответа@emacs сводит меня с ума, ответответ @emacs или быстрые тесты на делимость (на 2,3,4,5,..., 16)?Ссылки @Peter Cordes выглядят интересными только для целых чисел размером более 16 бит.

Размеры кода и циклы цикла необходимо учитывать более тщательно.