Xtykutl

In my 80x86 assembly program, I am trying to calculate the equation of
(((((2^0 + 2^1) * 2^2) + 2^3) * 2^4) + 2^5)...(2^n), where each even exponent is preceded by a multiplication and each odd exponent is preceded by a plus. I have code, but my result is continuously off from the desired result. When 5 is put in for n, the result should be 354, however I get 330.

Any and all advice will be appreciated.

.586

.model flat



include io.h



.stack 4096



.data

number dword ?

prompt byte "enter the power", 0

string byte 40 dup (?), 0

result byte 11 dup (?), 0

lbl_msg byte "answer", 0

bool dword ?

runtot dword ?



.code

_MainProc proc

    input prompt, string, 40

    atod string

    push eax





    call power







    add esp, 4



    dtoa result, eax

    output lbl_msg, result



    mov eax, 0

    ret



_MainProc endp



power proc

    push ebp

    mov ebp, esp



    push ecx



    mov bool, 1     ;initial boolean value

    mov eax, 1

    mov runtot, 2   ;to keep a running total

    mov ecx, [ebp + 8]



    jecxz done



loop1:

    add eax, eax        ;power of 2

    test bool, ecx      ;test case for whether exp is odd/even

    jnz oddexp          ;if boolean is 1

    add runtot, eax     ;if boolean is 0

    loop loop1



oddexp:

    mov ebx, eax        ;move eax to seperate register for multiplication

    mov eax, runtot     ;move existing total for multiplication

    mul ebx             ;multiplication of old eax to new eax/running total

    loop loop1



done:

    mov eax, runtot     ;move final runtotal for print

    pop ecx

    pop ebp

    ret









power endp







end

You're overcomplicating your code with static variables and branching.

These are powers of 2, you can (and should) just left-shift by n instead of actually constructing 2^n and using a mul instruction.

add eax,eax is the best way to multiply by 2 (aka left shift by 1), but it's not clear why you're doing that to the value in EAX at that point. It's either the multiply result (which you probably should have stored back into runtot after mul), or it's that left-shifted by 1 after an even iteration.

If you were trying to make a 2^i variable (with a strength reduction optimization to shift by 1 every iteration instead of shifting by i), then your bug is that you clobber EAX with mul, and its setup, in the oddexp block.

As Jester points out, if the first loop loop1 falls through, it will fall through into oddexp:. When you're doing loop tail duplication, make sure you consider where fall-through will go from each tail if the loop does end there.

There's also no point in having a static variable called bool which holds a 1, which you only use as an operand for test. That implies to human readers that the mask sometimes needs to change; test ecx,1 is a lot clearer as a way to check the low bit for zero / non-zero.

You also don't need static storage for runtot, just use a register (like EAX where you want the result eventually anyway). 32-bit x86 has 7 registers (not including the stack pointer).

This is how I'd do it. Untested, but I simplified a lot by unrolling by 2. Then the test for odd/even goes away because that alternating pattern is hard-coded into the loop structure.

We increment and compare/branch twice in the loop, so unrolling didn't get rid of the loop overhead, just changed one of the loop branches into an an if() break that can leave the loop from the middle.

This is not the most efficient way to write this; the increment and early-exit check in the middle of the loop could be optimized away by counting another counter down from n, and leaving the loop if there are less than 2 steps left. (Then sort it out in the epilogue)

;; 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

I didn't check if the adding-odd-power step ever produces a carry into another bit. I think it doesn't, so it could be safe to implement it as bts eax, ecx (setting bit i). Effectively an OR instead of an ADD, but those are equivalent as long as the bit was previously cleared.

To make the asm look more like the source and avoid obscure instructions, I implemented 1<<i with shl to generate 2^i for total += 2^i, instead of a more-efficient-on-Intel xor ebx,ebx / bts ebx, ecx. (Variable-count shifts are 3 uops on Intel Sandybridge-family because of x86 flag-handling legacy baggage: flags have to be untouched if count=0). But that's worse on AMD Ryzen, where bts reg,reg is 2 uops but shl reg,cl is 1.

Update: i=3 does produce a carry when adding, so we can't OR or BTS the bit for that case. But optimizations are possible with more branching.

Using 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 */

...

The first few outputs are:

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

Peeling the first 3 iterations would enable the BTS optimization, where you just set the bit instead of actually creating 2^n and adding.

Instead of just peeling them, we can just hard-code the starting point for i=3 for larger n, and optimize the code that figures out a return value for the n<3 case. I came up with a branchless formula for that based on right-shifting the 0b1100 bit-pattern by 3, 2, or 0.

Also note that for n>=18, the last shift count is strictly greater than half the width of the register, and the 2^i from odd i has no low bits. So only the last 1 or 2 iterations can affect the result. It boils down to either 1<<n for odd n, or 0 for even n. This simplifies to (n&1) << n.

For n=14..17, there are at most 2 bits set. Starting with result=0 and doing the last 3 or 4 iterations should be enough to get the correct total. In fact, for any n, we only need to do the last k iterations, where k is enough that the total shift count from even i is >= 32. Any bits set by earlier iterations are shifted out. (I didn't add a branch for this special case.)

;; 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

By using BTS to set a bit in EAX avoids needing an extra scratch register to construct 1<<i in, so we don't have to save/restore EBX. So that's a minor bonus saving.

Notice that this time the main loop is entered with i=4, which is even, instead of i=1. So I swapped the add vs. shift.

I still didn't get around to pulling the cmp/jae out of the middle of the loop. Something like lea edx, [ecx-2] instead of mov would set the loop-exit condition, but would require a check to not run the loop at all for i=4 or 5. For large-count throughput, many CPUs can sustain 1 taken + 1 not-taken branch every 2 clocks, not creating a worse bottleneck than the loop-carried dep chains (through eax and ecx). But branch-prediction will be different, and it uses more branch-order-buffer entries to record more possible roll-back / fast-recovery points.