Есть алгоритмы, которые лучше для более чем 8 бит. Ответ @ rcgldr - это полезное начало для 16- или 32-битного попконта. См. Как подсчитать количество установленных бит в 32-разрядном целом числе? для некоторых битхаков и других алгоритмов, включая поиск в таблице.
Вы могли бы рассмотреть 4-битную таблицу поиска. Сдвиги MSP430 медленные (1 цикл на бит и 1 инструкция на бит, если у вас нет MSP430X). Или используйте большую 8-битную справочную таблицу.
Или перебрать установленные биты, очистив младший бит с помощью v &= v - 1;. В MSP430 это принимает MOV, DEC и AND. Это замечательно, если обычно устанавливается только пара битов, но они часто разбросаны.
Но самый простой и наименьший способ с размером кода - просто зациклить все биты по одному за раз.
Если вы собираетесь зацикливаться по одному биту за раз, чтобы он был простым и компактным, вы хотите использовать флаг переноса, переключаясь на перенос и используя ADDC (add-with-carry).
Я пытался написать C, чтобы компиляторы могли превратиться в хороший asm с помощью ADDC, но https://godbolt.org/z/2Ev2IC - лучшее, что мне удалось. GCC и clang не очень хорошо подходят для MSP430 с идиомой tmp = a+a; carry = tmp<a;, которую они распознают для x86 и большинства других архитектур.
Так или иначе, вы хотели asm в первую очередь:
;; simple naive bit-count. Small code-size and not too slow for 8 bits
;; input in r12, result: r11 = popcount(r12)
mov.w #0, r11 ; retval = 0
.popcount_loop: ; do{
add.b r12,r12 ; shift a bit into carry flag
addc #0, r11 ; add that bit to r11: r11 += 0 + C
tst.b r12
jnz .popcount_loop ; } while( (uint8_t)r12 != 0);
Использование размера байтового операнда для add означает, что бит 7 переходит в C, а не бит 15.
Вместо этого мы могли бы использовать сдвиг вправо, чтобы поместить младший бит в флаг C , особенно если мы ожидаем, что многие входные данные будут маленькими числами (поэтому ненулевые биты все направлены к нижнему концу ). Согласно эта копия ссылки на набор инструкций MSP430 / MSP430X google найдена, обычный MSP430 не имеет сдвига вправо, а только поворота вправо при переносе. RRC[.W] / RRC.B. MSP430X имеет некоторые «повороты», которые фактически сдвигаются в нули, поэтому они действительно сдвигаются. Но нам это не нужно, если мы удостоверимся, что C = 0, прежде чем запустить его. Поскольку подсчет населения не будет изменен, ADDC надежно очистит для нас C.
Мы можем оптимизировать это для меньшего количества инструкций внутри цикла (тот же размер кода, но работает быстрее), поскольку JNZ и ADDC используют флаги от одного и того же ADD. Поскольку ADDC также записывает флаги, это означает, что он должен быть в следующей итерации. Таким образом, мы должны перекосить петлю. Мы можем очистить первую итерацию и сделать ее ADD вне цикла. Мы не будем проверять ноль после этого, но это нормально. Выполнение одной дополнительной итерации для ввода = 0x80 не является проблемой правильности и не стоит тратить дополнительные инструкции на
.
; simple looping popcount, optimized for small numbers (right shift)
; and optimized for fewer instructions inside the loop
;; input in r12, result: r11 = popcount(r12)
xor.w r11, r11 ; r11=0, C=!Z=0. (mov doesn't set flags; this saves a CLRC)
rrc.b r12 ; C = lsb(r12); r12 >>= 1 ; prep for first iter
.popcount_loop: ; do{
addc #0, r11 ; result += C; Clears C because r11 won't wrap
rrc.b r12 ; C = lsb(r12); r12 >>= 1; Z = (r12==0)
jnz .popcount_loop ; } while( (uint8_t)r12 != 0);
addc #0, r11 ; we left the loop with the last bit still in C
Если ваше входное значение расширено до нуля, вы можете использовать rrc.w r12, чтобы цикл работал для 8 или 16-битных значений. Но он не медленнее, потому что он все еще выходит после сдвига всех бит вправо.
Наклонение цикла и очистка первой половины первой итерации и последней половины последней итерации обойдется нам всего в одну дополнительную инструкцию. (И это все еще инструкции из одного слова.)
Вы упоминаете нечетное / четное. Вы на самом деле просто хотите паритет? (Счетчик чисел нечетный или четный)? Это то же самое, что и горизонтальное XOR всех битов.
; Needs MSP430X for rrum, otherwise you can only shift by 1 bit per instruction
;; input in r12, result: r12=parity(r12)
;; clobbers: r11
mov.b r12, r11 ; copy the low byte, zero the upper byte of R11 (not that it matters)
rrum #4, r11 ; costs 4 cycles for shift-count = 4
xor r11, r12 ; low 4 bits ^= (high 4 bits >> 4)
mov.b r12, r11
rrum #2, r11 ; costs 2 cycles for shift-count = 2
xor r11, r12 ; narrow again to 2 bits
mov.b r12, r11
rrum #1, r11 ; costs 1 cycle for shift-count = 1.
xor r11, r12 ; narrow again to 2 bits
and #1, r12 ; clear high garbage from the high bits.
; ret if this isn't inline
Вы можете сделать это с помощью цикла, например, используйте цикл popcount и выполните and #1, r12 в конце.
Мне кажется, что, возможно, мы могли бы сохранить инструкции, если бы мы сместились влево (на 4, затем на 2) и сделали последний шаг (смещение на 1) с add.b r12,r12, потому что переполнение со знаком (флаг V) = carry_in XOR carry_out для знакового бита . Для обоих входов одинаковые для сложения существующий знаковый бит всегда будет 0 + 0 = 00 или 1 + 1 = 10, поэтому знаковый бит = carry_in в знаковый бит.
Таким образом, с битовым шаблоном, подобным r12.b = XY??????, add.b r12,r12 устанавливает V = X^Y, горизонтальное XOR двух верхних битов входа . Потому что Y - это перенос в MSB, а X - это перенос.
Это было бы хорошо, если вы хотите перейти на него, но MSP430, похоже, не имеет jXX, который разветвляется на V, установлен или нет.У него есть JL и JGE, который ветвится на (N XOR V) (то есть со знаком сравнения), но N будет равен MSB, поэтому N ^ V это просто C, после того, как наши V смещены влево V = N ^ C,Я полагаю, вам нужно вывести слово флага из регистра флага и сдвинуть / замаскировать его!Или проверьте этот бит флага и JNZ.