1.28.4 Setting and clearing specific bits: FPU example

Here is the layout of the bits present in the float type in IEEE 754 format:

Since I don't like passing over something without explaining and interpreting it, let me break this down quickly:

* S (Sign) — the highest bit (Most Significant Bit - MSB). If it is 0 the number is positive, if 1 the number is negative.

* Exponent — 8 bits that determine the power of 2 for the number, but in a biased representation (add 127).

* Mantissa — 23 bits that define the digits after the decimal point.

So if you want to change the sign of a number from positive to negative or vice versa, all you need to do is flip bit 31 from 0 to 1 or from 1 to 0. The rest of the number (the exponent and mantissa) stays exactly as it is.

Getting back to our topic — the sign of the number lives in the highest bit (MSB). Is it possible to change the sign of a floating point number without any FPU instructions?

1
#include <stdio.h>
2

3
float my_abs (float i)
4
{
5
    // clear bit 31 (sign bit) — force the number to be positive
6
    unsigned int tmp = (*(unsigned int*)&i) & 0x7FFFFFFF; // AND with mask: all 1s except bit 31
7
    return *(float*)&tmp; // reinterpret the modified bits as float
8
};
9

10
float set_sign (float i)
11
{
12
    // set bit 31 (sign bit) — force the number to be negative
13
    unsigned int tmp = (*(unsigned int*)&i) | 0x80000000; // OR with mask: only bit 31 is 1
14
    return *(float*)&tmp; // reinterpret the modified bits as float
15
};
16

17
float negate (float i)
18
{
19
    // flip bit 31 (sign bit) — toggle the sign
20
    unsigned int tmp = (*(unsigned int*)&i) ^ 0x80000000; // XOR with mask: flips only bit 31
21
    return *(float*)&tmp; // reinterpret the modified bits as float
22
};
23

24
int main()
25
{
26
    printf ("my_abs():\n");
27
    printf ("%f\n", my_abs (123.456));   // should print 123.456
28
    printf ("%f\n", my_abs (-456.123));  // should print 456.123
29
    printf ("set_sign():\n");
30
    printf ("%f\n", set_sign (123.456)); // should print -123.456
31
    printf ("%f\n", set_sign (-456.123)); // should print -456.123
32
    printf ("negate():\n");
33
    printf ("%f\n", negate (123.456));   // should print -123.456
34
    printf ("%f\n", negate (-456.123));  // should print 456.123
35
};

We need this trick in C/C++ to copy to and from a float value without any actual conversion. There are three functions: my_abs() clears the MSB (sets it to 0); set_sign() sets the MSB (forces it to 1); and negate() flips it. XOR can be used to flip a bit.

x86

The code is straightforward at this point.

Listing 1.286: Optimizing MSVC 2012

1
_tmp$ = 8
2
_i$   = 8
3

4
_my_abs PROC
5
    and DWORD PTR _i$[esp-4], 2147483647    ; AND with 0x7FFFFFFF — clear bit 31 (sign bit)
6
    fld DWORD PTR _tmp$[esp-4]              ; load the modified float from stack into ST0 (FPU return register)
7
    ret 0
8
_my_abs ENDP
9

10
_tmp$ = 8
11
_i$   = 8
12

13
_set_sign PROC
14
    or  DWORD PTR _i$[esp-4], -2147483648  ; OR with 0x80000000 — set bit 31 (sign bit)
15
    fld DWORD PTR _tmp$[esp-4]             ; load the modified float into ST0
16
    ret 0
17
_set_sign ENDP
18

19
_tmp$ = 8
20
_i$   = 8
21

22
_negate PROC
23
    xor DWORD PTR _i$[esp-4], -2147483648  ; XOR with 0x80000000 — flip bit 31 (sign bit)
24
    fld DWORD PTR _tmp$[esp-4]             ; load the modified float into ST0
25
    ret 0
26
_negate ENDP

A quick explanation:

* DWORD PTR _i$[esp-4] — points to the first parameter on the stack (because in Win32 the function receives a float on the stack).

* and ... 0x7FFFFFFF — modifies the bit directly in memory.

* fld — loads the modified value from its new location into the FPU register ST0 in order to return it.

AND clears and OR sets the desired bit. XOR flips it. Finally, the modified value is loaded into ST0, because floating point values are returned in that register.

Now let's try MSVC 2012 optimizing for x64:

1
tmp$ = 8
2
i$   = 8
3

4
my_abs PROC
5
    movss DWORD PTR [rsp+8], xmm0       ; spill float argument from XMM0 onto stack
6
    mov   eax, DWORD PTR i$[rsp]        ; load the 32-bit representation into EAX
7
    btr   eax, 31                       ; BTR: test bit 31 then reset (clear) it
8
    mov   DWORD PTR tmp$[rsp], eax      ; store modified value back onto stack
9
    movss xmm0, DWORD PTR tmp$[rsp]     ; load modified float into XMM0 (return register in Win64)
10
    ret   0
11
my_abs ENDP
12

13
set_sign PROC
14
    movss DWORD PTR [rsp+8], xmm0       ; spill float argument from XMM0 onto stack
15
    mov   eax, DWORD PTR i$[rsp]        ; load the 32-bit representation into EAX
16
    bts   eax, 31                       ; BTS: test bit 31 then set it
17
    mov   DWORD PTR tmp$[rsp], eax      ; store modified value back onto stack
18
    movss xmm0, DWORD PTR tmp$[rsp]     ; load modified float into XMM0
19
    ret   0
20
set_sign ENDP
21

22
negate PROC
23
    movss DWORD PTR [rsp+8], xmm0       ; spill float argument from XMM0 onto stack
24
    mov   eax, DWORD PTR i$[rsp]        ; load the 32-bit representation into EAX
25
    btc   eax, 31                       ; BTC: test bit 31 then complement (flip) it
26
    mov   DWORD PTR tmp$[rsp], eax      ; store modified value back onto stack
27
    movss xmm0, DWORD PTR tmp$[rsp]     ; load modified float into XMM0
28
    ret   0
29
negate ENDP

Here the first float parameter arrives in xmm0 and is temporarily copied to the local stack. Then three new instructions appear:

* BTR (Bit Test and Reset) — tests the bit value (puts it in the Carry Flag), then clears it (sets it to zero). A shorthand for AND with an inverted mask.

* BTS (Bit Test and Set) — tests then sets the bit.

* BTC (Bit Test and Complement) — tests then flips the bit.

Finally, the result is copied into XMM0, because floating point values are returned through XMM0 in the Win64 environment.

MIPS

1
my_abs:
2
    ; move from coprocessor 1 (FPU) to integer register:
3
    mfc1    $v1, $f12               ; $v1 = float argument from FPU register $f12
4
    li      $v0, 0x7FFFFFFF         ; $v0 = 0x7FFFFFFF (mask to clear sign bit)
5
    and     $v0, $v1                ; $v0 = $v1 & 0x7FFFFFFF — clear bit 31
6
    mtc1    $v0, $f0                ; move result back to FPU register $f0 (return value)
7
    jr      $ra                     ; return
8
    or      $at, $zero              ; branch delay slot (NOP)
9

10
set_sign:
11
    ; move from coprocessor 1 (FPU) to integer register:
12
    mfc1    $v0, $f12               ; $v0 = float argument from FPU register $f12
13
    lui     $v1, 0x8000             ; $v1 = 0x80000000 (load upper immediate: 0x8000 << 16)
14
    or      $v0, $v1, $v0           ; $v0 = $v0 | 0x80000000 — set bit 31
15
    mtc1    $v0, $f0                ; move result back to FPU register $f0
16
    jr      $ra                     ; return
17
    or      $at, $zero              ; branch delay slot (NOP)
18

19
negate:
20
    ; move from coprocessor 1 (FPU) to integer register:
21
    mfc1    $v0, $f12               ; $v0 = float argument from FPU register $f12
22
    lui     $v1, 0x8000             ; $v1 = 0x80000000
23
    xor     $v0, $v1, $v0           ; $v0 = $v0 ^ 0x80000000 — flip bit 31
24
    mtc1    $v0, $f0                ; move result back to FPU register $f0
25
    jr      $ra                     ; return
26
    or      $at, $zero              ; branch delay slot (NOP)

GCC 4.4.5 for MIPS does roughly the same thing:

Listing 1.288: Optimizing GCC 4.4.5 (IDA)

1
my_abs:
2
    mfc1    $v1, $f12               ; Move From Coprocessor 1: transfer float from $f12 to integer $v1
3
    li      $v0, 0x7FFFFFFF         ; load mask 0x7FFFFFFF into $v0
4
    and     $v0, $v1                ; $v0 = float_bits & 0x7FFFFFFF — clear sign bit
5
    mtc1    $v0, $f0                ; Move To Coprocessor 1: transfer result to FPU return register $f0
6
    jr      $ra                     ; return
7
    or      $at, $zero              ; branch delay slot (NOP)
8

9
set_sign:
10
    mfc1    $v0, $f12               ; transfer float from $f12 to integer $v0
11
    lui     $v1, 0x8000             ; $v1 = 0x8000 << 16 = 0x80000000
12
    or      $v0, $v1, $v0           ; $v0 = float_bits | 0x80000000 — set sign bit
13
    mtc1    $v0, $f0                ; transfer result to FPU return register $f0
14
    jr      $ra                     ; return
15
    or      $at, $zero              ; branch delay slot (NOP)
16

17
negate:
18
    mfc1    $v0, $f12               ; transfer float from $f12 to integer $v0
19
    lui     $v1, 0x8000             ; $v1 = 0x80000000
20
    xor     $v0, $v1, $v0           ; $v0 = float_bits ^ 0x80000000 — flip sign bit
21
    mtc1    $v0, $f0                ; transfer result to FPU return register $f0
22
    jr      $ra                     ; return
23
    or      $at, $zero              ; branch delay slot (NOP)

A quick explanation:

* mfc1 $v1, $f12 — Move From Coprocessor 1. Transfers from $f12 (first parameter) to $v1 (integer CPU register).

* The modification is done using and/or/xor with the appropriate mask.

* mtc1 $v0, $f0 — Move To Coprocessor 1. Returns the result in $f0 (FPU return register).

Loading 0x80000000 is done with lui $v1, 0x8000 (Load Upper Immediate): it places 0x8000 in the upper 16 bits and zeros the lower 16 bits, producing 0x80000000 because 0x8000 << 16 = 0x80000000. This saves us from needing an extra ori.

ARM

Optimizing Keil 6/2013 (ARM mode)

1
my_abs PROC
2
    BIC r0, r0, #0x80000000     ; clear bit 31 — BIC = Bitwise bit Clear (AND with inverted mask)
3
    BX  lr                      ; return
4
    ENDP
5

6
set_sign PROC
7
    ORR r0, r0, #0x80000000     ; set bit 31 — ORR = logical OR
8
    BX  lr                      ; return
9
    ENDP
10

11
negate PROC
12
    EOR r0, r0, #0x80000000     ; flip bit 31 — EOR = Exclusive OR (ARM name for XOR)
13
    BX  lr                      ; return
14
    ENDP

All good so far. ARM has the BIC instruction that clears specific bits explicitly. EOR is the ARM instruction name for the XOR operation ("Exclusive OR").

Optimizing Keil 6/2013 (Thumb mode)

1
my_abs PROC
2
    LSLS r0, r0, #1             ; R0 = i << 1  (shifts out the sign bit MSB)
3
    LSRS r0, r0, #1             ; R0 = (i << 1) >> 1  (shifts back, MSB is now 0)
4
    BX   lr                     ; return
5
    ENDP
6

7
set_sign PROC
8
    MOVS r1, #1                 ; R1 = 1
9
    LSLS r1, r1, #31            ; R1 = 1 << 31 = 0x80000000  (build the mask)
10
    ORRS r0, r0, r1             ; R0 = R0 | 0x80000000 — set bit 31
11
    BX   lr                     ; return
12
    ENDP
13

14
negate PROC
15
    MOVS r1, #1                 ; R1 = 1
16
    LSLS r1, r1, #31            ; R1 = 1 << 31 = 0x80000000  (build the mask)
17
    EORS r0, r0, r1             ; R0 = R0 ^ 0x80000000 — flip bit 31
18
    BX   lr                     ; return
19
    ENDP

Thumb mode in ARM offers 16-bit instructions, and not much data can be encoded in them, so the MOVS/LSLS instruction pair is used here to build the constant 0x80000000. It works like this: 1 << 31 = 0x80000000.

The my_abs code looks strange — it is effectively doing (i << 1) >> 1. That expression seems meaningless. But when input << 1 executes, the MSB (the sign bit) gets dropped. When the result is then >> 1, all bits shift back to their positions, but the MSB is now zero, because all "new" bits that appear from shift operations are always zeros. So the LSLS/LSRS pair effectively clears the MSB.

Optimizing GCC 4.6.3 (Raspberry Pi, ARM mode)

Listing 1.291: Optimizing GCC 4.6.3 for Raspberry Pi (ARM mode)

1
my_abs:
2
    FMRS R2, S0                 ; copy float from FPU register S0 to integer register R2
3
    BIC  R3, R2, #0x80000000    ; clear bit 31 — R3 = R2 & ~0x80000000
4
    FMSR S0, R3                 ; copy result from R3 back to FPU register S0 (return value)
5
    BX   LR                     ; return
6

7
set_sign:
8
    FMRS R2, S0                 ; copy float from FPU register S0 to integer register R2
9
    ORR  R3, R2, #0x80000000    ; set bit 31 — R3 = R2 | 0x80000000
10
    FMSR S0, R3                 ; copy result back to FPU register S0
11
    BX   LR                     ; return
12

13
negate:
14
    FMRS R2, S0                 ; copy float from FPU register S0 to integer register R2
15
    ADD  R3, R2, #0x80000000    ; flip bit 31 using ADD — equivalent to XOR here (see explanation below)
16
    FMSR S0, R3                 ; copy result back to FPU register S0
17
    BX   LR                     ; return

We are running Raspberry Pi Linux in QEMU which emulates the ARM FPU, so S-registers are used here for floating point numbers instead of R-registers.

The FMRS instruction moves data between GPR (general purpose registers) and the FPU and vice versa.

my_abs() and set_sign() work as expected, but what about negate()? Why is there ADD instead of XOR?

Hard to believe, but the instruction ADD register, 0x80000000 works exactly like XOR register, 0x80000000. First, what is our goal? The goal is to flip the MSB. Forget XOR for a moment. From school math we may remember that adding values like 1000 to other numbers does not affect the last 3 digits at all. Example: 1234567 + 10000 = 1244567 (the last 4 digits are unaffected).

But here we are working in binary, and 0x80000000 is 0b10000000000000000000000000000000 — meaning only the highest bit is set.

Adding 0x80000000 to any value never affects the lower 31 bits — it only affects the MSB. Adding 1 to 0 gives 1. Adding 1 to 1 gives 0b10 in binary, but bit 32 (counting from zero) gets dropped because our registers are 32 bits wide, so the result becomes 0. That is why XOR can be replaced by ADD here. It is hard to say why GCC decided to do it this way, but it works correctly.

1.28.5 Counting bits set to 1

This is a simple example of a function that counts the number of bits whose value is 1 in the input value.

These operations are also called "population count".

1
#include <stdio.h>
2
#define IS_SET(flag, bit) ((flag) & (bit)) // macro: checks if a specific bit is set in flag using bitwise AND
3

4
int f(unsigned int a)
5
{
6
    int i;
7
    int rt = 0;                      // bit counter, starts at 0
8
    for (i = 0; i < 32; i++)         // iterate over all 32 bit positions
9
        if (IS_SET(a, 1 << i))       // check if bit i is set in a
10
            rt++;                    // if set, increment counter
11
    return rt;                       // return total count of set bits
12
}
13

14
int main()
15
{
16
    f(0x12345678);                   // test call
17
}

In this loop, the counter i counts from 0 to 31, so 1 << i produces values from 1 to 0x80000000. To describe this operation in natural language, we say "shift 1 left by n bits". In other words, 1 << i sequentially produces every possible bit position in a 32-bit number. The bit that is freed on the right is always zeroed (set to 0).

C/C++ expression	Power of 2	Decimal	Hexadecimal
1 << 0	2^0	1	1
1 << 1	2^1	2	2
1 << 2	2^2	4	4
1 << 3	2^3	8	8
1 << 4	2^4	16	0x10
1 << 5	2^5	32	0x20
1 << 6	2^6	64	0x40
1 << 7	2^7	128	0x80
1 << 8	2^8	256	0x100
1 << 9	2^9	512	0x200
1 << 10	2^10	1024	0x400
1 << 11	2^11	2048	0x800
1 << 12	2^12	4096	0x1000
1 << 13	2^13	8192	0x2000
1 << 14	2^14	16384	0x4000
1 << 15	2^15	32768	0x8000
1 << 16	2^16	65536	0x10000
1 << 17	2^17	131072	0x20000
1 << 18	2^18	262144	0x40000
1 << 19	2^19	524288	0x80000
1 << 20	2^20	1048576	0x100000
1 << 21	2^21	2097152	0x200000
1 << 22	2^22	4194304	0x400000
1 << 23	2^23	8388608	0x800000
1 << 24	2^24	16777216	0x1000000
1 << 25	2^25	33554432	0x2000000
1 << 26	2^26	67108864	0x4000000
1 << 27	2^27	134217728	0x8000000
1 << 28	2^28	268435456	0x10000000
1 << 29	2^29	536870912	0x20000000
1 << 30	2^30	1073741824	0x40000000
1 << 31	2^31	2147483648	0x80000000

These constants (bit masks) appear very frequently in code, and the reverse engineer must be able to recognize them quickly. Decimal numbers below 65536 and hexadecimal ones are very easy to memorize. Decimal numbers above 65536 are generally not worth memorizing. These constants are used very heavily to set flags for specific bits. Example: a portion of ssl_private.h from Apache 2.4.6 source code:

1
#define SSL_OPT_NONE           (0)       // no options set
2
#define SSL_OPT_RELSET         (1<<0)    // bit 0: relative set
3
#define SSL_OPT_STDENVVARS     (1<<1)    // bit 1: standard environment variables
4
#define SSL_OPT_EXPORTCERTDATA (1<<3)    // bit 3: export certificate data
5
#define SSL_OPT_FAKEBASICAUTH  (1<<4)    // bit 4: fake basic auth
6
#define SSL_OPT_STRICTREQUIRE  (1<<5)    // bit 5: strict require
7
#define SSL_OPT_OPTRENEGOTIATE (1<<6)    // bit 6: optional renegotiation
8
#define SSL_OPT_LEGACYDNFORMAT (1<<7)    // bit 7: legacy DN format

Let's return to our example.

The IS_SET macro checks for the presence of a bit in a. The IS_SET macro is in fact an AND operation (logical AND) and returns 0 if the specified bit is not present, or returns the bit mask itself if the bit is present. The if statement in C/C++ fires if the expression inside it is non-zero (it can even be 123456), and that is why it always works correctly.

x86

MSVC

Listing 1.292: MSVC 2010

1
_rt$ = -8      ; size = 4 bytes
2
_i$  = -4      ; size = 4 bytes
3
_a$  = 8       ; size = 4 bytes
4

5
_f PROC
6
    push ebp
7
    mov ebp, esp
8
    sub esp, 8                            ; allocate 8 bytes on stack for rt and i
9
    mov DWORD PTR _rt$[ebp], 0            ; rt = 0
10
    mov DWORD PTR _i$[ebp], 0            ; i = 0
11
    jmp SHORT $LN4@f                     ; jump to loop condition check
12
$LN3@f:
13
    mov eax, DWORD PTR _i$[ebp]          ; load i into EAX
14
    add eax, 1                           ; EAX = i + 1
15
    mov DWORD PTR _i$[ebp], eax          ; i++
16
$LN4@f:
17
    cmp DWORD PTR _i$[ebp], 32           ; compare i with 32 (0x20)
18
    jge SHORT $LN2@f                     ; if i >= 32, exit loop
19
    mov edx, 1                           ; EDX = 1 (base bit mask)
20
    mov ecx, DWORD PTR _i$[ebp]          ; ECX = i (shift amount)
21
    shl edx, cl                          ; EDX = 1 << i  (build the bit mask)
22
    and edx, DWORD PTR _a$[ebp]          ; EDX = mask & a  (test if bit i is set)
23
    je SHORT $LN1@f                      ; AND result was 0? skip increment
24
    mov eax, DWORD PTR _rt$[ebp]         ; load rt
25
    add eax, 1                           ; rt + 1
26
    mov DWORD PTR _rt$[ebp], eax         ; rt++
27
$LN1@f:
28
    jmp SHORT $LN3@f                     ; loop back to increment
29
$LN2@f:
30
    mov eax, DWORD PTR _rt$[ebp]         ; return rt in EAX
31
    mov esp, ebp
32
    pop ebp
33
    ret 0
34
_f ENDP

x32dbg

We will run the above example in x32dbg, using the value 0x12345678 (God willing I will explain it in detail so everything is clear and easy).

Let's step into the first iteration when i = 0, and see how i is loaded into ECX:

The first instruction mov edx, 1 places the value 1 into EDX — this is the mask for bit zero.

Then the instruction mov ecx, dword ptr ss:[ebp-0x04] loads the value of i into ECX, which is 0 since this is the beginning of the loop.

Then the instruction shl edx, cl — the most important one (Shift Logical Left) — shifts the value of EDX (which is 1) left by the number of bits in CL (the low byte of ECX, containing i=0). Result: 1 << 0 = 1.

So EDX is still 1, and it is the mask that will check bit zero.

After that it will execute je.

When i = 1, we see how i is loaded into ECX:

EDX holds 1. And SHL will now execute.

EDX now holds 1 << 1 (i.e. 2). This is the bit mask as we said before.

The AND sets ZF to 1, which means that the input value (0x12345678) ANDed with 2:

So, there is no corresponding bit set in the input value.

The part of the code that increments the counter will not execute: the JZ instruction skips it.

Let's trace a bit more. Now i = 4. SHL will execute:

EDX = 1 << 4 (i.e. 0x10 or 16):

Another mask.

When the AND executes:

ZF became 0 because this bit is present in the input value.

Indeed, 0x12345678 & 0x10 = 0x10. This bit gets counted: the jump does not take place, and the bit counter is incremented.

The function returns 13. That is the total count of bits set to 1 in 0x12345678.

GCC

Let's compile it in GCC 4.4.1:

Listing 1.293: GCC 4.4.1

1
public f
2
f proc near
3
rt      = dword ptr -0Ch   ; local variable: bit counter
4
i       = dword ptr -8     ; local variable: loop index
5
arg_0   = dword ptr  8     ; function argument: input value a
6

7
    push ebp
8
    mov ebp, esp
9
    push ebx                       ; save EBX (callee-saved register)
10
    sub esp, 10h                   ; allocate 16 bytes on stack
11
    mov [ebp+rt], 0                ; rt = 0
12
    mov [ebp+i], 0                 ; i = 0
13
    jmp short loc_80483EF          ; jump to loop condition check
14
loc_80483D0:
15
    mov eax, [ebp+i]               ; load i into EAX (shift amount)
16
    mov edx, 1                     ; EDX = 1 (base value for mask)
17
    mov ebx, edx                   ; EBX = 1 (copy to working register)
18
    mov ecx, eax                   ; ECX = i (shift amount)
19
    shl ebx, cl                    ; EBX = 1 << i  (build the bit mask)
20
    mov eax, ebx                   ; EAX = 1 << i
21
    and eax, [ebp+arg_0]           ; EAX = mask & a  (test if bit i is set)
22
    test eax, eax                  ; is EAX zero?
23
    jz short loc_80483EB           ; if zero, skip increment
24
    add [ebp+rt], 1                ; rt++
25
loc_80483EB:
26
    add [ebp+i], 1                 ; i++
27
loc_80483EF:
28
    cmp [ebp+i], 1Fh               ; compare i with 31 (0x1F)
29
    jle short loc_80483D0          ; if i <= 31, continue loop
30
    mov eax, [ebp+rt]              ; return rt in EAX
31
    add esp, 10h
32
    pop ebx                        ; restore EBX
33
    pop ebp
34
    retn
35
f endp

x64

Let's modify the example slightly to extend it to 64-bit:

1
#include <stdio.h>
2
#include <stdint.h>
3
#define IS_SET(flag, bit) ((flag) & (bit)) // macro: tests whether a specific bit is set
4

5
int f(uint64_t a)
6
{
7
    uint64_t i;
8
    int rt = 0;                        // bit counter
9
    for (i = 0; i < 64; i++)           // iterate over all 64 bit positions
10
        if (IS_SET(a, 1ULL << i))      // 1ULL ensures a 64-bit shift
11
            rt++;
12
    return rt;
13
}

Non-optimizing GCC 4.8.2

Listing 1.294: Non-optimizing GCC 4.8.2

1
f:
2
    push rbp
3
    mov rbp, rsp
4
    mov QWORD PTR [rbp-24], rdi    ; store argument a on stack
5
    mov DWORD PTR [rbp-12], 0      ; rt = 0
6
    mov QWORD PTR [rbp-8], 0       ; i = 0
7
    jmp .L2                        ; jump to loop condition
8
.L4:
9
    mov rax, QWORD PTR [rbp-8]     ; RAX = i
10
    mov rdx, QWORD PTR [rbp-24]    ; RDX = a
11
    mov ecx, eax                   ; ECX = i (shift amount)
12
    shr rdx, cl                    ; RDX = a >> i  (shift a right by i bits)
13
    mov rax, rdx                   ; RAX = a >> i
14
    and eax, 1                     ; EAX = (a>>i) & 1  (isolate lowest bit)
15
    test rax, rax                  ; is lowest bit zero?
16
    je .L3                         ; if zero, skip increment
17
    add DWORD PTR [rbp-12], 1      ; rt++
18
.L3:
19
    add QWORD PTR [rbp-8], 1       ; i++
20
.L2:
21
    cmp QWORD PTR [rbp-8], 63      ; i <= 63?
22
    jbe .L4                        ; if yes, jump back to loop body
23
    mov eax, DWORD PTR [rbp-12]    ; rt into EAX for return
24
    pop rbp
25
    ret

Optimizing GCC 4.8.2

Listing 1.295: Optimizing GCC 4.8.2

1
f:
2
    xor eax, eax             ; rt lives in EAX, initialize to 0
3
    xor ecx, ecx             ; i lives in ECX, initialize to 0
4
.L3:
5
    mov rsi, rdi             ; load input value (a)
6
    lea edx, [rax+1]         ; EDX = EAX + 1  (proposed new value of rt)
7
    shr rsi, cl              ; RSI = RSI >> CL  (i.e. a >> i)
8
    and esi, 1               ; ESI = (a>>i) & 1  (isolate lowest bit)
9
    cmovne eax, edx          ; if ZF=0 (bit was set): EAX = EDX (commit rt++)
10
    add rcx, 1               ; i++
11
    cmp rcx, 64              ; i == 64?
12
    jne .L3                  ; if not, repeat loop
13
    rep ret                  ; FATRET — AMD-recommended return after conditional jump

This code is shorter, but a bit unusual.

In all the examples we have seen so far, we incremented the value of "rt" after comparing a specific bit, but here the code increments "rt" beforehand (line 6), writing the new value into register EDX. This means: if the last bit was 1, the CMOVNE instruction (which is equivalent to CMOVNZ) commits the new value of "rt" by moving EDX ("proposed rt value") into EAX ("the current rt that will be returned").

Consequently, the increment operation happens at every step of the loop — that is, 64 times — regardless of the input value.

The advantage of this code is that it contains only one conditional jump (at the end of the loop) instead of two (one to skip the rt++ increment and one at the end of the loop). This can make it faster on modern processors that have branch predictors: section 2.4.1 on page 575.

The last instruction is REP RET (opcode F3 C3), also called FATRET by MSVC. This is an optimized variant of RET, recommended by AMD to be placed at the end of a function when RET immediately follows a conditional jump.

Optimizing MSVC 2010

Listing 1.296: Optimizing MSVC 2010

1
a$ = 8
2
f PROC
3
    ; RCX = input value
4
    xor eax, eax                          ; rt = 0
5
    mov edx, 1                            ; RDX = 1 (initial bit mask)
6
    lea r8d, QWORD PTR [rax+64]           ; R8D = 64 (loop counter, counts down)
7
    npad 5                                ; padding for alignment
8
$LL4@f:
9
    test rdx, rcx                         ; is this bit set in the input value?
10
    je SHORT $LN3@f                       ; if not, skip increment
11
    inc eax                               ; rt++
12
$LN3@f:
13
    rol rdx, 1                            ; RDX rotated left by 1 (cycles the bit, same as SHL here)
14
    dec r8                                ; R8--
15
    jne SHORT $LL4@f                      ; if R8 != 0, continue loop
16
    fatret 0                              ; optimized return (AMD FATRET)
17
f ENDP

Here the ROL instruction is used instead of SHL; it is actually "rotate left" rather than "shift left", but in this example it works exactly like SHL.

R8 counts down from 64 to 0. It is like i but in reverse. This is a table of some register values during execution:

RDX	R8
0x0000000000000001	64
0x0000000000000002	63
0x0000000000000004	62
0x0000000000000008	61
...	...
0x4000000000000000	2
0x8000000000000000	1

At the end we see the FATRET instruction.

Optimizing MSVC 2012

Listing 1.297: Optimizing MSVC 2012

1
a$ = 8
2
f PROC
3
    ; RCX = input value
4
    xor eax, eax
5
    mov edx, 1
6
    lea r8d, QWORD PTR [rax+32]           ; R8D = 32 (loop runs 32 times, 2 bits per iteration)
7
    npad 5
8
$LL4@f:
9
    ; first pass --------------------------------
10
    test rdx, rcx                         ; is bit set in input?
11
    je SHORT $LN3@f
12
    inc eax                               ; rt++
13
$LN3@f:
14
    rol rdx, 1                            ; rotate mask left (advance to next bit)
15
    ; second pass --------------------------------
16
    test rdx, rcx                         ; test the next bit (loop unrolling: 2 bits per iteration)
17
    je SHORT $LN11@f
18
    inc eax                               ; rt++
19
$LN11@f:
20
    rol rdx, 1                            ; rotate mask left again
21
    ; -------------------------------------------
22
    dec r8                                ; R8--
23
    jne SHORT $LL4@f                      ; if R8 != 0, continue
24
    fatret 0
25
f ENDP

Optimizing MSVC 2012 does almost the same work as MSVC 2010, but somehow it generates two identical loop bodies and the iteration count became 32 instead of 64.

Honestly, it is hard to say why. Perhaps an optimization trick? Perhaps a longer loop body is faster? Either way, this code is shown here to demonstrate that compiler output can sometimes be very strange and illogical — yet it works perfectly.

ARM

ARM + Optimizing Xcode 4.6.3 (LLVM) (ARM mode)

Listing 1.298: Optimizing Xcode 4.6.3 (LLVM) (ARM mode)

1
MOV R1, R0              ; R1 = input value a (preserve it)
2
MOV R0, #0              ; R0 = 0 (rt counter)
3
MOV R2, #1              ; R2 = 1 (base mask value)
4
MOV R3, R0              ; R3 = 0 (i counter)
5
loc_2E54:
6
TST R1, R2, LSL R3      ; set flags based on R1 & (R2 << R3)  i.e. a & (1<<i)
7
ADD R3, R3, #1          ; R3++ (i++)
8
ADDNE R0, R0, #1        ; if ZF was cleared by TST (bit was set), increment R0 (rt++)
9
CMP R3, #32             ; compare i with 32
10
BNE loc_2E54            ; if i != 32, continue loop
11
BX LR                   ; return

TST is the same as TEST in x86.

As we said before, there are no separate shift instructions in ARM mode. Instead there are modifiers such as LSL (Logical Shift Left), LSR (Logical Shift Right), ASR (Arithmetic Shift Right), ROR (Rotate Right), and RRX (Rotate Right with Extend), which can be appended to instructions like MOV, TST, CMP, ADD, SUB, RSB.

These modifiers specify how to shift the second operand and by how many bits. So the instruction TST R1, R2, LSL R3 works here as:

1
R1 ∧ (R2 ≪ R3)   ; bitwise AND of R1 with (R2 shifted left by R3 positions)

ARM + Optimizing Xcode 4.6.3 (LLVM) (Thumb-2 mode)

Almost the same thing, but here two instructions LSL.W/TST are used instead of a single TST, because in Thumb mode it is not possible to embed an LSL modifier directly into TST.

1
MOV R1, R0              ; R1 = input value a
2
MOVS R0, #0             ; R0 = 0 (rt counter)
3
MOV.W R9, #1            ; R9 = 1 (base mask)
4
MOVS R3, #0             ; R3 = 0 (i counter)
5
loc_2F7A:
6
LSL.W R2, R9, R3        ; R2 = R9 << R3  i.e. 1 << i  (separate shift, required in Thumb)
7
TST R2, R1              ; set flags based on R2 & R1  i.e. (1<<i) & a
8
ADD.W R3, R3, #1        ; i++
9
IT NE                   ; if-then block: execute next instruction only if NE (ZF=0)
10
ADDNE R0, #1            ; rt++  (only if bit was set)
11
CMP R3, #32             ; compare i with 32
12
BNE loc_2F7A            ; if i != 32, continue loop
13
BX LR                   ; return

ARM64 + Optimizing GCC 4.9

Let's take the 64-bit example we used before.

Listing 1.299: Optimizing GCC (Linaro) 4.8

1
f:
2
    mov w2, 0            ; rt = 0
3
    mov x5, 1            ; X5 = 1 (base mask value)
4
    mov w1, w2           ; i = 0
5
.L2:
6
    lsl x4, x5, x1       ; X4 = X5 << X1  i.e. 1 << i  (build 64-bit mask)
7
    add w3, w2, 1        ; W3 = rt + 1  (proposed new rt)
8
    tst x4, x0           ; (1 << i) & a  (test if bit i is set in a)
9
    add w1, w1, 1        ; i++
10
    csel w2, w3, w2, ne  ; if NE (bit was set): w2 = w3 (rt = new_rt), else w2 = w2 (no change)
11
    cmp w1, 64           ; i < 64?
12
    bne .L2              ; if not done, repeat loop
13
    mov w0, w2           ; rt into W0 for return
14
    ret

The CSEL instruction is "Conditional SELect". It selects one of two values based on the flags set by TST, and copies the selected value into W2, which holds the variable rt.

ARM64 + Non-optimizing GCC 4.9

Listing 1.300: Non-optimizing GCC (Linaro) 4.8

1
f:
2
    sub sp, sp, #32
3
    str x0, [sp,8]           ; store argument "a" in register save area
4
    str wzr, [sp,24]         ; rt = 0
5
    str wzr, [sp,28]         ; i = 0
6
    b .L2                    ; jump to loop condition
7
.L4:
8
    ldr w0, [sp,28]          ; load i
9
    mov x1, 1                ; X1 = 1
10
    lsl x0, x1, x0           ; X0 = X1 << X0  i.e. 1 << i  (build mask)
11
    mov x1, x0               ; X1 = 1 << i
12
    ldr x0, [sp,8]           ; X0 = a
13
    and x0, x1, x0           ; X0 = (1<<i) & a
14
    cmp x0, xzr              ; compare X0 with zero
15
    beq .L3                  ; if zero, skip rt++
16
    ldr w0, [sp,24]          ; load rt
17
    add w0, w0, 1            ; rt + 1
18
    str w0, [sp,24]          ; rt++
19
.L3:
20
    ldr w0, [sp,28]          ; load i
21
    add w0, w0, 1            ; i + 1
22
    str w0, [sp,28]          ; i++
23
.L2:
24
    ldr w0, [sp,28]          ; load i
25
    cmp w0, 63               ; i <= 63?
26
    ble .L4                  ; if yes, jump to loop body
27
    ldr w0, [sp,24]          ; rt into W0 for return
28
    add sp, sp, 32
29
    ret

MIPS

Non-optimizing GCC

1
f:
2
    ; IDA does not know variable names, we assigned them manually:
3
    ; rt = -0x10,  i = -0xC,  var_4 = -4,  a = 0
4

5
    addiu $sp, -0x18                     ; allocate 24 bytes on stack
6
    sw $fp, 0x18+var_4($sp)              ; save frame pointer
7
    move $fp, $sp                        ; set frame pointer
8
    sw $a0, 0x18+a($fp)                  ; store argument a on stack
9
    sw $zero, 0x18+rt($fp)               ; rt = 0
10
    sw $zero, 0x18+i($fp)               ; i = 0
11
    b loc_68                             ; jump to loop condition check
12
    or $at, $zero                        ; branch delay slot (NOP)
13
loc_20:
14
    li $v1, 1                            ; $v1 = 1 (base mask value)
15
    lw $v0, 0x18+i($fp)                  ; $v0 = i (shift amount)
16
    or $at, $zero                        ; load delay slot (NOP)
17
    sllv $v0, $v1, $v0                   ; $v0 = 1 << i  (SLLV: variable shift amount from register)
18
    move $v1, $v0                        ; $v1 = mask
19
    lw $v0, 0x18+a($fp)                  ; $v0 = a
20
    or $at, $zero                        ; load delay slot (NOP)
21
    and $v0, $v1, $v0                    ; $v0 = a & (1<<i)
22
    beqz $v0, loc_58                     ; if zero (bit not set), skip rt++
23
    or $at, $zero                        ; branch delay slot (NOP)
24
    lw $v0, 0x18+rt($fp)                 ; load rt
25
    or $at, $zero                        ; load delay slot (NOP)
26
    addiu $v0, 1                         ; rt + 1
27
    sw $v0, 0x18+rt($fp)                ; rt++
28
loc_58:
29
    lw $v0, 0x18+i($fp)                  ; load i
30
    or $at, $zero                        ; load delay slot (NOP)
31
    addiu $v0, 1                         ; i + 1
32
    sw $v0, 0x18+i($fp)                 ; i++
33
loc_68:
34
    lw $v0, 0x18+i($fp)                  ; load i
35
    or $at, $zero                        ; load delay slot (NOP)
36
    slti $v0, 0x20                       ; $v0 = (i < 32) ? 1 : 0
37
    bnez $v0, loc_20                     ; if i < 32, loop back
38
    or $at, $zero                        ; branch delay slot (NOP)
39
    lw $v0, 0x18+rt($fp)                 ; return rt
40
    move $sp, $fp                        ; load delay slot: restore stack pointer
41
    lw $fp, 0x18+var_4($sp)              ; restore frame pointer
42
    addiu $sp, 0x18                      ; load delay slot: deallocate stack
43
    jr $ra                               ; return to caller
44
    or $at, $zero                        ; branch delay slot (NOP)

This code is long: all local variables live in the local stack and are loaded every time they are needed.

The SLLV instruction is "Shift Word Left Logical Variable" — it differs from SLL in that the shift amount in SLL is embedded in the instruction itself (and therefore fixed), whereas SLLV takes the shift amount from a register.

Optimizing GCC

This code is shorter. There are two shift instructions instead of one. Why?

We could replace the first SLLV instruction with an unconditional branch that jumps directly to the second SLLV. But that would be an extra jump instruction in the function, and it is always better to get rid of it.

1
f:
2
    ; $a0 = a
3
    ; variable rt will be in $v0:
4
    move $v0, $zero
5
    ; variable i will be in $v1:
6
    move $v1, $zero
7
    li $t0, 1
8
    li $a3, 32
9
    sllv $a1, $t0, $v1      ; $a1 = $t0 << $v1 = 1 << i
10
loc_14:
11
    and $a1, $a0            ; $a1 = a & (1<<i)
12
    ; increment i:
13
    addiu $v1, 1
14
    ; jump to loc_28 if a&(1<<i) == 0 and increment rt:
15
    beqz $a1, loc_28
16
    addiu $a2, $v0, 1
17
    ; if BEQZ was not triggered, store the updated rt in $v0:
18
    move $v0, $a2
19
loc_28:
20
    ; if i != 32, jump to loc_14 and prepare the next shifted value:
21
    bne $v1, $a3, loc_14
22
    sllv $a1, $t0, $v1
23
    ; return
24
    jr $ra
25
    or $at, $zero           ; branch delay slot, NOP

1.28.6 Conclusion

Just like the << and >> operations in C/C++, the shift instructions in x86 are SHR/SHL (for unsigned values) and SAR/SHL (for signed values).

The shift instructions in ARM are LSR/LSL (for unsigned values) and ASR/LSL (for signed values).

It is also possible to add a shift suffix to some instructions (called "data processing instructions").

Checking a specific bit (known at compile time)

Test if bit 0b1000000 (0x40) is present in a register value:

Listing 1.303: C/C++

1
if (input & 0x40) ...

Listing 1.304: x86

1
TEST REG, 40h
2
JNZ is_set
3
; bit is not set

Listing 1.305: x86

1
TEST REG, 40h
2
JZ is_cleared
3
; bit is set

Listing 1.306: ARM (ARM mode)

1
TST REG, #0x40
2
BNE is_set
3
; bit is not set

Sometimes, AND is used instead of TEST, but the flags that get set are the same.

Checking a specific bit (determined at runtime)

This is usually done via this C/C++ code snippet (shift the value n bits to the right, then mask the lowest bit):

Listing 1.307: C/C++

1
if ((value >> n) & 1) ...

This is typically implemented in x86 code as:

Listing 1.308: x86

1
; REG = input_value
2
; CL = n
3
SHR REG, CL
4
AND REG, 1

Or (shift 1 bit n times to the left, isolate that bit in the input value and test if it is non-zero):

Listing 1.309: C/C++

1
if (value & (1 << n)) ...

This is typically implemented in x86 code as:

Listing 1.310: x86

1
; CL = n
2
MOV REG, 1
3
SHL REG, CL
4
AND input_value, REG

Setting a specific bit (known at compile time)

Listing 1.311: C/C++

1
value = value | 0x40;

Listing 1.312: x86

1
OR REG, 40h

Listing 1.313: ARM (ARM mode) and ARM64

1
ORR R0, R0, #0x40

Setting a specific bit (determined at runtime)

Listing 1.314: C/C++

1
value = value | (1 << n);

This is typically implemented in x86 code as:

Listing 1.315: x86

1
; CL = n
2
MOV REG, 1
3
SHL REG, CL
4
OR input_value, REG

Clearing a specific bit (known at compile time)

Simply apply an AND operation with the inverted value:

Listing 1.316: C/C++

1
value = value & (~0x40);

Listing 1.317: x86

1
AND REG, 0FFFFFFBFh

Listing 1.318: x64

1
AND REG, 0FFFFFFFFFFFFFFBFh

This effectively causes all bits to be set except one.

ARM in ARM mode has the BIC instruction, which works like the NOT + AND instruction pair:

Listing 1.319: ARM (ARM mode)

1
BIC R0, R0, #0x40

Clearing a specific bit (determined at runtime)

Listing 1.320: C/C++

1
value = value & (~(1 << n));

Listing 1.321: x86

1
; CL = n
2
MOV REG, 1
3
SHL REG, CL
4
NOT REG
5
AND input_value, REG

0xV3n0m

1.28.4 Setting and clearing specific bits: FPU example

x86

MIPS

ARM

Optimizing Keil 6/2013 (ARM mode)

Optimizing Keil 6/2013 (Thumb mode)

Optimizing GCC 4.6.3 (Raspberry Pi, ARM mode)

1.28.5 Counting bits set to 1

x86

MSVC

x32dbg

GCC

x64

Optimizing GCC 4.8.2

Optimizing MSVC 2010

Optimizing MSVC 2012

ARM

ARM + Optimizing Xcode 4.6.3 (LLVM) (ARM mode)

ARM + Optimizing Xcode 4.6.3 (LLVM) (Thumb-2 mode)

ARM64 + Optimizing GCC 4.9

ARM64 + Non-optimizing GCC 4.9

MIPS

Non-optimizing GCC

Optimizing GCC

1.28.6 Conclusion

Checking a specific bit (known at compile time)

Checking a specific bit (determined at runtime)

Setting a specific bit (known at compile time)

Setting a specific bit (determined at runtime)

Clearing a specific bit (known at compile time)

Clearing a specific bit (determined at runtime)

Table of Contents