Assembly Gems
dflund.se
dflund.se
For bit unpacking in C, the natural inclination is to shift out the least significant bit with something like this:
u1 getbit() { u1 lsb = x & 1; x >>= 1; return lsb; }
However, most assembly languages have a better alternative if you instead shift out the most significant bit. Suppose that the bit buffer is in ECX. Then you would do ADD ECX, ECX to left shift ECX and (this is the important part) put the shifted-out bit into the carry flag. From there the carry flag can be shifted into the least significant bit of another register, say EAX, with ADC EAX, EAX, or you can branch based on the carry with JC/JNCAs a full example, here is the gamma decoder from apack/aplib, which despite its simplicity rewards careful study:
getbit:
add dl, dl
jnz .stillbitsleft
mov dl, [esi]
inc esi
adc dl, dl
.stillbitsleft:
ret
getgamma:
xor ecx, ecx
getgamma_no_ecx:
inc ecx
.getgammaloop:
call getbit
adc ecx, ecx
call getbit
jc .getgammaloop
rethttp://dflund.se/~john_e/gems/gem003a.html
It would be a little adventure to try to figure out how it was conceived, as although it looks like something a superoptimiser would produce, it was around before superoptimisation, and I think it was generated by a human likely related to the demoscene.
Microinstructione are like a CPU's firmware which implements the external-facing macroinstruction set into a simpler set of microinstructions which coordinate various internal state.
The neg (two's complement) of 0x80000000 is 0x80000000. Thus his trick results in an infinite loop for the most negative value.
For what it's worth, my copy of the C11 spec says
The abs, labs, and llabs functions compute the absolute value of an integer j. If the result cannot be represented, the behavior is undefined. 304)
304) The absolute value of the most negative number cannot be represented in two’s complement.Some things are due to an algorithmical trick, while others are a translation trick. Some are both.
A lot of these are crucial enough that they've been codified in transistors now, and generally can execute in a cycle without consuming extra registers. There are still some very valid bit tricks though.