X86 OF and CF calculaton

For sub and add instructions CF can be calculated using comparing operator for unsigned values:

sub_cf = (src1 <src2)

add_cf = (res < src1)

Note, that for add res < src1 if and only if res < src2 so it doesn't matter which argument to compare against the result.

Both CF and OF flags can be calculated knowing sign bits of the result and arguments:

sub_cf = (src1&src2&res) | ((~src1)&(src2|res))

sub_of = (src1^src2)&(src1^res)

add_cf = ((src1^src2)&(~res)) | (src1&src2)

add_of = (~(src1^src2))&(src1^res)

To assert first formula see that we can carry if the minuend is large, the subtrahend is large and the result is large. If the subtrahend or the result are small then carry is unnecessary. If the minuend is small then we should carry if either the subtrahend or the result is large.
The second formula says that signed subtraction overflows only if the minuend and the subtrahend have different sign and furthermore, the result has the sign different from the minuend.
Third formula uses the fact that unsigned addition generates carry only if both summand are large or if one of the summands is large and the result is not.
The last formula verifies that signed add overflows only if both summands have the same sign different from result's one.

PS as for the note, on ARM sub_cf is the same as on x86, but add_cf is inverted

Difference between binary op and compound assignment

In the C language these two operations have different semantics:

x = x >> 8;

x >>= 8;

If x is 8bit type, then right x in the first operation is promoted to int, while in the second one there is 8-bit shift. Clang gives a warning in the second case.

multiline grep

A very nice way to extract block of text knowing the first and the last line (from here):

awk '/Start pattern/,/End pattern/'

X86 pop instruction bizarre semantics

in an instruction, say pop [esp], the esp value in the effective address calculation should be an updated one. And if memory store raises #PF the esp value should be the one right before instruction execution. Oh Jesus.

Yet Another Eulerian Graph Indication

Each edge in a graph belongs to odd number of cycles. Prove that the graph is Eulerian.

Arm program counter

In ARM command set PC register is equal to current instruction address plus eight, that is the address of the instruction which is to be executed right after the next one. Oh, arm.

Some problems on sequences and linked lists

sequences:
1) In a sequence if integers every integer except one appears even number of times. Determine exception's value using O(1) memory and one lookup through the sequence.
2) In a sequence of integers more than half of elements are the same. Dermine it's value using O(1) memory and one lookup through the sequence.

lists:
1) There is a single-linked list with unknown number of elements. Determine if the last element of the list links to NULL or to some element in the list using O(1) memory.
2) Show how to implement a doubly-linked list using only sizeof(void*) bytes for linking information. a) only one iterator is allowed, b) many independent iterators are allowed. Assume no elements are added to/deleted from the list when iterators start working.