Вы слишком усложняете свой код статическими переменными и ветвлениями.
Это степени 2, вы можете (и должны) просто сдвинуть влево на n вместо фактического построения 2^n и использования инструкции mul.
add eax,eax - это лучший способ умножения на 2 (то есть сдвиг влево на 1), но не ясно, почему вы делаете это со значением в EAX на тот момент. Это либо результат умножения (который, вероятно, следовало бы сохранить в runtot после mul), либо сдвиг влево на 1 после четной итерации.
Если вы пытались создать переменную 2^i (с оптимизацией снижения прочности для смещения на 1 каждую итерацию вместо смещения на i), то ваша ошибка заключается в том, что вы заклинили EAX с помощью mul, и его в блоке oddexp.
Как указывает Шут, если первый loop loop1 провалится, он провалится в oddexp:. Когда вы выполняете дублирование хвоста цикла, убедитесь, что вы продумали, где провал будет с каждого хвоста, если цикл там заканчивается.
Также нет смысла иметь статическую переменную с именем bool, которая содержит 1, которую вы используете только в качестве операнда для test. Это подразумевает для читателей, что маску иногда нужно менять; test ecx,1 намного понятнее, как способ проверки младшего бита на ноль / ненулевое значение.
Вам также не нужно статическое хранилище для runtot, просто используйте регистр (например, EAX, где вы все равно хотите получить результат). 32-битный x86 имеет 7 регистров (не считая указателя стека).
Вот как я это сделаю. Не проверено, но я упростила многое, развернув на 2. Затем тест на нечетность / четность уходит, потому что этот чередующийся шаблон жестко запрограммирован в структуру цикла.
Мы дважды увеличиваем и сравниваем / разветвляемся в цикле, поэтому развертывание не избавило от накладных расходов цикла, а просто изменило одну из ветвей цикла на if() break, который может оставить цикл из середины.
Это не самый эффективный способ написать это; проверку приращения и раннего выхода в середине цикла можно было бы оптимизировать, считая еще один счетчик с n и выходя из цикла, если осталось менее 2 шагов. (Потом разберись в эпилоге)
;; UNTESTED
power proc ; fastcall calling convention: arg: ECX = unsigned int n
; clobbers: ECX, EDX
; returns: EAX
push ebx ; save a call-preserved register for scratch space
mov eax, 1 ; EAX = 2^0 running total / return value
test ecx,ecx
jz done
mov edx, ecx ; EDX = n
mov ecx, 1 ; ECX = i=1..n loop counter and shift count
loop1: ; do{ // unrolled by 2
; add 2^odd power
mov ebx, 1
shl ebx, cl ; 2^i ; xor ebx, ebx; bts ebx, ecx
add eax, ebx ; total += 2^i
inc ecx
cmp ecx, edx
jae done ; if (++i >= n) break;
; multiply by 2^even power
shl eax, cl ; total <<= i; // same as total *= (1<<i)
inc ecx ; ++i
cmp ecx, edx
jb loop1 ; }while(i<n);
done:
pop ebx
ret
Я не проверял, выдает ли шаг добавления нечетной мощности перенос в другой бит. Я думаю, что это не так, поэтому было бы безопасно реализовать его как bts eax, ecx (установка бита i). Эффективно ИЛИ вместо ДОБАВЛЕНИЯ, но они эквивалентны, если бит был предварительно очищен.
Чтобы ассемблер выглядел больше как источник и избегал непонятных инструкций, я реализовал 1<<i с shl для генерации 2^i для total += 2^i вместо более эффективного-на-Intel xor ebx,ebx / bts ebx, ecx. (Сдвиги с переменным числом в семействе Intel Sandybridge составляют 3 мопа из-за устаревшего багажа с обработкой флагов x86: флаги должны быть не тронуты, если count = 0). Но это хуже на AMD Ryzen, где bts reg,reg равно 2 моп, а shl reg,cl равно 1.
Обновление: i=3 создает перенос при переносе, поэтому мы не можем использовать бит OR или BTS для этого случая. Но оптимизация возможна с большим количеством ветвлений.
Использование calc:
; define shiftadd_power(n) { local res=1; local i; for(i=1;i<=n;i++){ res+=1<<i; i++; if(i>n)break; res<<=i;} return res;}
shiftadd_power(n) defined
; base2(2)
; shiftadd_power(0)
1 /* 1 */
...
Первые несколько выходов:
n shiftadd(n) (base2)
0 1
1 11
2 1100
3 10100 ; 1100 + 1000 carries
4 101000000
5 101100000 ; 101000000 + 100000 set a bit that was previously 0
6 101100000000000
7 101100010000000 ; increasing amounts of trailing zero around the bit being flipped by ADD
Очистка первых 3 итераций включит оптимизацию BTS, , где вы просто устанавливаете бит вместо фактического создания 2^n и добавления.
Вместо просто очистки, мы можем просто жестко закодировать начальную точку для i=3 для большего n и оптимизировать код, который вычисляет возвращаемое значение для случая n<3. Я придумал формулу без ответвлений, основанную на смещении вправо 0b1100 битового шаблона на 3, 2 или 0.
Также обратите внимание, что при n> = 18 счетчик последнего сдвига строго больше половины ширины регистра, а 2 ^ i из нечетного i не имеет младших битов . Таким образом, только последние 1 или 2 итерации могут повлиять на результат. Он сводится к 1<<n для нечетных n или 0 для четных n. Это упрощает до (n&1) << n.
Для n=14..17 установлено максимум 2 бита. Начиная с result = 0 и делая последние 3 или 4 итерации, должно быть достаточно, чтобы получить правильную сумму. Фактически, для любых n нам нужно только выполнить последние k итераций, где k достаточно, чтобы общее число сдвигов от четных i было> = 32. Любые биты, установленные более ранними итерациями, сдвигаются из. (Я не добавил ветку для этого особого случая.)
;; UNTESTED
;; special cases for n<3, and for n>=18
;; enabling an optimization in the main loop (BTS instead of add)
;; funky overflow behaviour for n>31: large odd n gives 1<<(n%32) instead of 0
power_optimized proc
; fastcall calling convention: arg: ECX = unsigned int n <= 31
; clobbers: ECX, EDX
; returns: EAX
mov eax, 14h ; 0b10100 = power(3)
cmp ecx, 3
ja n_gt_3 ; goto main loop or fall through to hard-coded low n
je early_ret
;; n=0, 1, or 2 => 1, 3, 12 (0b1, 0b11, 0b1100)
mov eax, 0ch ; 0b1100 to be right-shifted by 3, 2, or 0
cmp ecx, 1 ; count=0,1,2 => CF,ZF,neither flag set
setbe cl ; count=0,1,2 => cl=1,1,0
adc cl, cl ; 3,2,0 (cl = cl+cl + (count<1) )
shr eax, cl
early_ret:
ret
large_n: ; odd n: result = 1<<n. even n: result = 0
mov eax, ecx
and eax, 1 ; n&1
shl eax, cl ; n>31 will wrap the shift count so this "fails"
ret ; if you need to return 0 for all n>31, add another check
n_gt_3:
;; eax = running total for i=3 already
cmp ecx, 18
jae large_n
mov edx, ecx ; EDX = n
mov ecx, 4 ; ECX = i=4..n loop counter and shift count
loop1: ; do{ // unrolled by 2
; multiply by 2^even power
shl eax, cl ; total <<= i; // same as total *= (1<<i)
inc edx
cmp ecx, edx
jae done ; if (++i >= n) break;
; add 2^odd power. i>3 so it won't already be set (thus no carry)
bts eax, edx ; total |= 1<<i;
inc ecx ; ++i
cmp ecx, edx
jb loop1 ; }while(i<n);
done:
ret
Использование BTS для установки бита в EAX позволяет избежать необходимости в дополнительном чистом регистре для создания 1<<i, поэтому нам не нужно сохранять / восстанавливать EBX. Так что это небольшая бонусная экономия.
Обратите внимание, что на этот раз основной цикл вводится с i=4, который является четным, вместо i=1. Поэтому я поменялся надстройкой против сдвига.
Я все еще не удосужился вытянуть cmp / jae из середины петли. Нечто подобное lea edx, [ecx-2] вместо mov установило бы условие выхода из цикла, но потребовало бы проверки, чтобы вообще не запускать цикл для i = 4 или 5. Для пропускной способности большого количества многие ЦП могут выдержать 1 взятый + 1 не взятая ветвь каждые 2 такта, не создавая худшего узкого места, чем переносимые по петле цепи dep (через eax и ecx). Но прогноз ветвления будет другим, и он использует больше записей буфера порядка ветвления, чтобы записать больше возможных точек отката / быстрого восстановления.