Что не так с моим кодом сборки ARM для подсчета числа 0 в 32-битном регистре - PullRequest
0 голосов
/ 21 ноября 2018
test:
       mov r1,#32

loop:
       cmp r0, #0

       beq done
       mov r3, r0 
       lsr r0, r0, #1
       cmp r0, r3
       blt sub
       b done
sub:

      sub r1, r1, #1
      b loop
done:

       mov r0, r1
       mov  pc, lr

Я настроил его так, чтобы он уменьшался всякий раз, когда присутствует один, но он не совсем работает, и я не знаю, почему

1 Ответ

0 голосов
/ 21 ноября 2018

Ваша идея дизайна несколько усложнена, что затруднило для вас правильность кода.Я не совсем уверен, почему вы подумали (x>>1) < x (сравнение со знаком после беззнакового сдвига вправо).

Вы можете воспользоваться флагами, чтобы получить информацию о старшем бите, но вам не нуженcmp сделать так.Используйте сдвиг влево (или add same,same), который устанавливает флаги, и протестируйте флаг S, используя условие MInus, чтобы выяснить, каков старший бит результата.

Или посмотрите на флаг C, чтобы увидеть сдвинутый бит, но тогда вам нужно будет что-то сделать с флагом C после последней итерации (после того, как регистр станет нулевым).Это нормально, вы можете очистить эту последнюю итерацию.

Использование вправо сдвига (ваш lsr) не может работать, если вы используете условия, которые зависят от знака знака.


test:
       movs  r1, r0            @ copy and set flags
       mov   r0, #32

          @ loop invariants:
          @ r0 = return value
          @ r1 = input
          @ flags set according to the current value of r1
.loop:                         @ do {
      submi r0, r0, #1    @ predicated subtract: if(high_bit_set(r1)) r0--;
      adds  r1, r1        @ left-shift by 1 and set flags
      bne  .loop          @ keep looping until there are no set bits
                               @ }while(r1<<=1);

      mov  pc, lr        @ or bx lr

Вместо ветвления вы определенно хотите воспользоваться преимуществом предикатного выполнения ARM любой инструкции, но добавив условие к мнемонике.submi - это sub, который не используется, если условие MI ложно.


Конечно, если вы заботитесь о производительности, 8-битная таблица поиска может быть хорошейспособ реализовать popcnt, или есть формула битхака, которую ARM, вероятно, может сделать очень эффективно с помощью своего переключателя ствола. Как посчитать количество установленных бит в 32-разрядном целом числе?

AFAIK, ARM не имеет инструкции аппаратного подсчета битов, как некоторые другие архитектуры, например, x86 popcnt.

В компьютерных программах обычно встречаются небольшие числа .Сдвиг влево займет ~ 30 итераций, чтобы сдвинуть все биты для чисел с любым установленным младшим битом.Но сдвиг вправо может завершиться в несколько итераций для небольших чисел, таких как 7 (только набор младших 3 битов).

Если для ваших входов характерно очищать все смежные старшие биты, то левыецикл переключения передач, который я написал для этого ответа, является худшим.

...