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.

x86 real mode eip is 32bit

Imagine what would happen if we execute the last command of the 16bit segment so the IP of the next command would be 0x10000. Strange, but 16bit wrapping to zero doesn't ocuur and normally general protection exception is generated.

x86 rep instruction owerwrites itself

One can write an x86 code with rep stos which overwrites itself. It seems like intel core i5 stops execution of rep stos as soon as it overwrites the rep prefix and then executes the new code (with eip unmodified). However, amd seems to ignore self modifications and it executes rep stos till the end and after it eip points to (new) code right after rep stos.

least significant bt

Obtaining a least signigicant bit of x is very easy: x & (-x). Since x + (-x) = 0 = 2^(word size) the number -x must have the same value of lsb as x. Addition of these two bits yeilds zero and a carry, and this carry is passed all the way to the right leaving zeros in the result. But the latter can only happen if other bits of x and -x are inverse of each other. This completes an explanation

mean for unsigned integers

from http://spamsink.livejournal.com/360680.html:

 floor((a+b)/2) = (a^b)/2 + a&b

negation without multiplying

To negate an integer x one can simply do ~x+1. To see why this works consider ~x = -1U - x which is equivalent to ~x+1 = -x

Spurious interrupts

8259A programmable interrupt controller is famous for it's spurious interrupts. I haven't caught any on core i5 with intel chipset, but on a machine with AMD processor and GeForce 7025 chipset one is constantly bugging me right after I enable interrupts. It happens only once, so just having a spurious handler for it is fine.

loop over one-bits of an integer

If you need to have a loop iterated as many times as there are 1-bits in an integer v it is better to write for (;v;v &= v-1) than for (i = popcnt(v); i>0; i--) because the former has O(popcnt(v)) compexity against the latter's O(width(v)).

a submatrix problem

This problem is said to be proposed by Knuth: given an m*n (m<n) maxtix A of rank m find its m*m submatrix B such that all elements of of B^{-1}A have absolute value at most one.

Source: Local Search in Combinatorial Optimization E. Aarts, K. Lenstra, chapter 2