Creative Misuse of Branches

Overflow Checking in Assembly

C++ just blindly ignores overflow, so it's possible for a program to fail silently and give you the wrong answer. In assembly, you can check the overflow flag with "jo" (jump-if-overflow), like this:

mov edi,1000000000

add edi,edi
jo uhoh ; error-check the add

mov eax,edi
ret ; ordinary return

uhoh:
mov eax,-999 ; Special value to indicate we had an overflow
ret ; error return

(Try this in NetRun now!)

This program will hence return the right answer, or admit something failed. You do have to be careful to do a "jo uhoh" after every possible arithmetic instruction, since the overflow flag gets re-set after each "add".

warning: comparison between signed and unsigned integer expressions

Why do you care about all those silly jump instructions we talked about last class?

Well, for one thing, it affects how you can write C++ code. For example, this code produces a warning, then gives the wrong answer "999":

unsigned int i=3000000000;
if (i<-3) return 999; /* what?! */
else return 0;

(Try this in NetRun now!)

The problem is, in assembly language:

When comparing unsigned numbers, you use "ja" and "jb", which read the CF (carry flag).
When comparing signed numbers, you use "jg" and "jl", which read SF and OF (sign and overflow flags).

When comparing unsigned i to signed -3, which jump do you use? Well, sadly, they both give the wrong answer! This is a hardware limitation (no mixed-sign comparisons) that ends up as a language limitation (warning and wrong answer for mixed-sign comparisons).

In the above code, if the compiler decides to perform the signed comparison:
unsigned 3 billion < signed -3
(convert to signed)
signed -1 billion < signed -3
So this will return true: 3 billion is less than -3 if they're both converted to signed 32-bit values.

It doesn't actually help if we perform an unsigned comparison:
unsigned 3 billion < signed -3
(convert to unsigned)
unsigned 3 billion < signed 4 billion
This will also return true: 3 billion is less than -3 if they're both converted to unsigned 32-bit values.

On a 64-bit machine, you can fix this problem by typecasting both sides to a "long" before doing the compare. This works because a signed long has enough bits to represent +3 billion without wraparound:

unsigned int i=3000000000;
if ((long)i<(long)-3) return 999;
else return 0;

(Try this in NetRun now!)

This fixes the problem, but "unsigned long" suffers from the same exact malfunction at 15 quadrillion:

unsigned long i=15000000000000000000ul;
if ((long)i<(long)-3) return 999;
else return 0;

(Try this in NetRun now!)

Bottom line: you can't reliably compare signed and unsigned numbers. Pick one or the other, and stick with it.

Reminder: negative signed numbers are represented by setting the high bit, which corresponds to a really huge unsigned number; similarly, huge unsigned numbers like above correspond to negative signed numbers.

Low-Branch Bounds Checking

You can actually exploit the signed/unsigned comparison differences to speed up this common bounds-checking code:

int i=3;
const int n=10;
int arr[n];
int foo(void) {
	if (i>=0 && i<n) return arr[i];
	else return 0;
}

(Try this in NetRun now!)

Note that we have to do two separate tests on "i": it could be negative, so we check against zero; or it could be n or bigger, so we compare against n. But if you look at the code the compiler generates, there's only one test on "i":

	mov    edx, <<i>>
	mov    eax,0x0
	cmp    edx,0x9
	ja     bad
	... load up arr[i] ...
bad:	ret

Wait, only one comparison, and it's an *unsigned* compare? But "i" is signed!

This is intentional: if "i" is negative (signed), then treated as an unsigned number, it's huge. This lets us replace a two-test signed "negative or too big" with a single unsigned "too big" test!

Conditionals via the Multiply Instruction

The simplest example of this sort of non-branch switching is just a multiply instruction. For example, here "doit" determines whether the output will be 4, or 6:

for (int doit=0;doit<=1;doit++) {
	int blended=4+doit*2;
	std::cout<<"doit=="<<doit<<"  -> "<<blended<<"\n";
}

(Try this in NetRun now!)

This outputs:

doit==0  -> 4
doit==1  -> 6
Program complete.  Return 0 (0x0)

More generally, if you want to return A if doit is false (0), and B if doit is true (1), then you can do:

for (int doit=0;doit<=1;doit++) {
	int A=4;
	int B=6;
	int blended=A+doit*(B-A);
	std::cout<<"doit=="<<doit<<"  -> "<<blended<<"\n";
}

(Try this in NetRun now!)

You also see this written as the algebraically equivalent "blended = (1-doit)*A+doit*B;". This has four operations instead of the three above, so you don't see it as much anymore.

There are some interesting advantages of the multiply approach to conditionals. One is you can do "fuzzy conditionals", where your code blends between A and B if doit is somewhere between 0 and 1:

for (float doit=0.0;doit<=1.0;doit+=0.25) {
	int A=4;
	int B=6;
	float blended=A+doit*(B-A);
	std::cout<<"doit == "<<doit<<"	->	"<<blended<<"\n";
}

(Try this in NetRun now!)

This outputs:

doit == 0	->	4
doit == 0.25	->	4.5
doit == 0.5	->	5
doit == 0.75	->	5.5
doit == 1	->	6
Program complete.  Return 0 (0x0)

Multiply-based conditionals work fine for a single digit, but they don't scale well to multiple digits. For example, "0x4444 + 0x0100*(0x6666-0x4444)" gives you "0x226644", not "0x4644".