29
\$\begingroup\$

Exercise from an Assembly course I'm enrolled into:

Write a program that takes three numbers x,y,z as input, and returns:

  • 0 if (x+y+z) is even.

  • 1 if (x+y+z) is odd.

(Note that here + means arithmetic addition). Do it without actually adding the numbers. HINT: Use the XOR instruction.

Full exercise-sheet here: GitHub

Here's the code I've written. Please mind the comments I've added for to explain my ideas.

format PE console
entry start

include 'win32a.inc' 

; ===============================================
section '.text' code readable executable

start:

    call    read_hex              ; Provided by the teacher. Reads a hexadecimal number from stdin.
    mov     ebx,    eax
    call    read_hex
    add     ebx,    eax
    call    read_hex
    add     ebx,    eax         

    mov     eax,    ebx           ; Move the sum of the three given numbers into eax.
    xor     eax,    0x1           ; If the number is odd then the lowest bit becomes 0. If the number is even then the lowest bit becomes 1.
    ror     eax,    0x1           ; Rotate the lowest bit out of the register. So that the carry-flag gets a new state.
    jc      evenNumber            ; jc == Jump if the carry-flag has become 1. Means the last bit has been a 1, which in turn means that the number is even.
    mov     eax,    0x1           ; Otherwise just write 0 into eax, which signals an odd number. And prints this to stdout.
    jmp     print_result

evenNumber:
    mov     eax,    0x0

print_result:
    call    print_eax_binary    ; Provided by the teacher. Prints a binary number to stdout.

        ; Exit the process:
    push    0
    call    [ExitProcess]

include 'training.inc'

I'm not completely sure if I have gotten the exercise-task correctly. But let's assume that the entered three numbers have to be summed up and that one has to use xor in some way.

How could I improve my solution? Is there a better solution?

\$\endgroup\$
58
\$\begingroup\$

First off, you have nice, clean, well-formatted, easy-to-read code. You have even included comments that explain the goal of each instruction. Too much of the time I review assembly-language code, these are the things that go wrong. You've gotten them all correct. Nice job! Now I don't have to pull my hair out trying to read and understand your code.

Unfortunately, were I your instructor, I'd still have to give you a failing score on the assignment because you didn't follow the rules. The assignment says that you must "Do it without actually adding the numbers.", but right off the bat, you ADD the input values together. And we were off to such a good start… :-(

Now, personally, I think these types of assignments are rather silly, so I wouldn't be giving them. If I wanted you to learn how to use the bitwise operators, I'd find something useful and real-world that they are good for, and then give you that assignment. It's not like I'd have to work very hard. The chip designers didn't put them in merely for fun.

Oh well; you have to do the assignment that you were given. So follow the hint, use XOR. Maybe you don't know exactly what that means, so what I'd do is open up a programmer's calculator (all major desktop operating systems have a "programmer" mode for their calculators) and play around with it. Pick random combinations of positive and negative numbers, and compare what the results are when you add them together versus when you XOR them together. Try to get a feel for what XOR does. Then, look up a formal definition of XOR (exclusive-OR). If you're like me, your eyes glaze over at the symbolic logic stuff (which wasn't so great when I took that course in college); feel free to skip over that for the purposes of this assignment. Your real goal here is to find out what XOR actually does at the bit level. There are lots of detailed explanations of bitwise manipulation online, or you may have a textbook that covers this stuff, too.

For example:

    01101101
XOR 11010100
_____________
    10111001

Notice that each column follows the truth table for an XOR operation, which basically just says that the output is 1 (true) whenever the inputs differ. That's the "exclusive" part of the OR.

Eventually, while doing this preliminary research, I suspect you'd come across someone talking about how XOR operations are used to implement parity checks. Mast's answer here already spilled the beans. Parity indicates whether an integer is even or odd, and can be calculated simply by a XOR sum of the bits. Judging from your comments in the code, you already know that for a binary number, the lowest (least significant) bit determines whether it is odd or even.

So the good news is that your code is almost entirely correct. If you change the ADDs to XORs, it will follow the rules of the assignment and produce the correct result. Thus, you would have:

call    read_hex              ; Provided by the teacher. Reads a hexadecimal number from stdin.
mov     ebx,    eax
call    read_hex
xor     ebx,    eax
call    read_hex
xor     ebx,    eax    

Now we've XOR-summed all of the bits from the three inputs. All that's left is figuring out the parity of the result—i.e., whether the XOR-sum is odd or even.

You've already implemented one way of doing that, but as Quuxplusone pointed out, it is an unnecessarily complicated way. While it doesn't always hold when you start getting into more advanced things, for simple arithmetic operations, fewer instructions means faster code. Arguably more importantly, it means simpler code, which is more likely to be correct code. Moreover, fewer branches virtually always mean faster code, and certainly code whose flow of execution is easier to follow, and thus easier to debug.

I'd disagree slightly with Quuxplusone here and say that clever is totally fine, as long as your cleverness has some notable advantage. You don't always have to write code the "normal" way, because the "normal" way might be sub-optimal. Generally, if we're dropping down to write in assembly, it's because we want to write the best code we possibly can (either fastest, shortest, or whatever metric we are using to judge "best"), which means that "normal" isn't necessarily an important goal. Sometimes, "readable" isn't even an important goal. But, by the same token, I do agree there's no point in deviating from what is normal if your deviation is inferior, and that's certainly the case here.

Your XOR-sum is in the EBX register. You know that the XOR-sum tells you the parity in the least-significant bit. So what is the obvious thing to do? Mask off everything but the least-significant bit, and that'll be your answer! How do we mask off bits? Use a logical AND operation:

and  ebx, 1   ; mask off all but the low-order bit

Oh, and finally, since we need the result in EAX, we'll do:

mov  eax, ebx

(We could have just as easily done the MOV first, before the AND. It doesn't matter.)

Go through your current code, and prove to yourself that this gives exactly the same results, without needing to flip the bit with the XOR, without needing to involve the carry flag (CF) via ROR, and without needing to do any conditional branching (JC).

Putting it all together, the code is essentially:

call    read_hex              ; Provided by the teacher. Reads a hexadecimal number from stdin into EAX.
mov     ebx, eax
call    read_hex
xor     ebx, eax
call    read_hex
xor     ebx, eax         

mov     eax, ebx              ; Move XOR-sum of three given numbers into EAX.
and     eax, 0x1              ; Mask off all but the lowest-order bit.
call    print_eax_binary      ; Provided by the teacher. Prints a binary number in EAX to stdout.

; Exit the process:
push    0
call    [ExitProcess]

Simpler, clearer, faster. Rarely is it possible to say this about any piece of code, but I believe this really is the most optimal way to write this.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer, but I think that mentioning "parity" is misleading in this context. Parity usually refers to a property of all the bits of a number, not to its evenness, which is a property only of the least-significant bit. \$\endgroup\$ – Toby Speight May 15 '17 at 11:13
  • 5
    \$\begingroup\$ You can compact a little further by replacing xor ebx, eax, mov eax,ebx with the single instruction xor eax,ebx. \$\endgroup\$ – Edward May 15 '17 at 12:07
  • 1
    \$\begingroup\$ If we were really trying to optimise the function (perfectly pointless obviously) I'd say using three different registers to shorten the dependency chains might theoretically be marginally faster (the registers are available anyhow, why not use them). \$\endgroup\$ – Voo May 15 '17 at 20:59
  • 5
    \$\begingroup\$ @TobySpeight, Cody is using "parity" according to its common mathematical definition, which is exactly whether a number is even or odd. This is the source and basis of the specialized use of the term as shorthand for the evenness or oddness of the count of 1 bits in a given collection of bits. \$\endgroup\$ – John Bollinger May 15 '17 at 22:11
  • 1
    \$\begingroup\$ @Voo: how would extra registers help? With three inputs, there are only two xor operations, and they have to depend on each other. With 4 or more inputs you could get some ILP from (a^b) ^ (c^d). But if d is ready later than the others, then ((a^b)^c)^d has lower latency from d to the result: 1 xor instead of 2. It's counter-intuitive, but it can actually be better to do the naive serial dependency chain into a single accumulator, if you're feeding it with something that bottlenecks at 1 result per clock e.g. because of running on only 1 execution unit. \$\endgroup\$ – Peter Cordes May 16 '17 at 21:02
11
\$\begingroup\$

The beginning of your program obviously should be following the "HINT" and using xor instead of add.


This is some really wacky code:

    ror     eax,    0x1           ; Rotate the lowest bit out of the register. So that the carry-flag gets a new state.
    jc      evenNumber            ; jc == Jump if the carry-flag has become 1. Means the last bit has been a 1, which in turn means that the number is even.
    mov     eax,    0x1           ; Otherwise just write 0 into eax, which signals an odd number. And prints this to stdout.
    jmp     print_result

evenNumber:
    mov     eax,    0x0

print_result:

Typically, if you're just trying to test some bit(s) of a register, you use test, not this wacky ror-and-jc trick. I mean it's clever, but it's not normal — and thus it's not good style. Just do the normal thing, please:

    test    eax, 0x1
    jz      evenNumber

Here, I'll give you a cleverness to make up for the lost ror. The x86 has conditional move instructions, and mov specifically never clears the flags, meaning that you don't need any jumps here:

    test    eax, 0x1
    mov     eax, 0x0   ; set eax to 0...
    cmovz   eax, 0x1   ; ...but immediately set it to 1 *if* the zero flag was set

Or equivalently:

    test    eax, 0x1
    mov     eax, 0x0   ; set the high bytes of eax to 0
    setz    al         ; set the low byte of eax to the value of the zero flag

But best of all:

    andl    eax, 0x1   ; just extract the low-order bit...
    xorl    eax, 0x1   ; ...and flip it
\$\endgroup\$
  • 2
    \$\begingroup\$ Ah, unfortunately your CMOV trick won't work as written. The conditional move instructions don't take immediate operands—only registers. You will need to clobber another register that you have pre-initialized to 1. (Or, better yet, pre-initialize the clobber register to 0, so that you can use xor reg, reg, and then do mov eax, 1 in between the TEST and the CMOVNZ.) \$\endgroup\$ – Cody Gray May 15 '17 at 7:39
  • 2
    \$\begingroup\$ And even better than your "best of all": neg eax + and eax, 1 (never say "best" :-) \$\endgroup\$ – Cody Gray May 15 '17 at 7:41
6
\$\begingroup\$

"But let's assume that the entered three numbers have to be summed up and that one has to use xor in some way." Read the instructions again. You're explicitly not allowed to actually sum the numbers. This can be done using XOR as suggested. Your first part of the solution uses add, disqualifying your code.

The keyword to the actual solution would be checking for parity.

Keep in mind you don't have to add the numbers to know whether the result of a sum would be odd or even:

  • Odd + odd = even
  • Odd + even = odd
  • Even + even = even

Whether you do this for 2, 3 or 100 numbers is quite irrelevant, just as the actual value of the result.

\$\endgroup\$
  • \$\begingroup\$ The wiki article you linked is about the horizontal-xor meaning of the term "parity", not whether the number is odd or even. 0b1001 has even parity (two set bits), but is an odd number. The sum property doesn't hold for this kind of parity: 0b0111 + 0b0001 = 0b1000 (odd parity), but 0b1110 + 0b0001 = 0b1111 (even parity), for inputs that each have the same number of set bits (same parity), just in different places. \$\endgroup\$ – Peter Cordes May 16 '17 at 21:25
  • \$\begingroup\$ @PeterCordes Good catch, when you look at it that way my answer is quite confusing. Hopefully I'm able to clean it up later today. \$\endgroup\$ – Mast May 17 '17 at 5:57
  • \$\begingroup\$ There's more discussion of the same thing in comments on Cody's answer \$\endgroup\$ – Peter Cordes May 17 '17 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.