第19章 位操作

有很多程序都把输入参数的某些比特位当作标识位处理。在表面看来,使用布尔变量足以替代标志位寄存器,但是这种替代的做法并不理智。

19.1 特定位

19.1.1 x86

Win32的API 中有这么一段接口声明:

    HANDLE fh;

    fh=CreateFile ("file", GENERIC_WRITE | GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_ALWAYS ,↙
    ↘FILE_ATTRIBUTE_NORMAL, NULL);

经过MSVC 2010编译,可得到如下所示的指令。

指令清单19.1 MSVC 2010

    push    0
    push    128                            ; 00000080H
    push    4
    push    0
    push    1
    push    -1073741824                    ; c0000000H
    push    OFFSET $SG78813
    call    DWORD PTR __imp__CreateFileA@28
    mov     DWORD PTR _fh$[ebp], eax

库文件WinNT.h对有关常量的相关位域进行了定义。

指令清单19.2 WinNT.h

#define GENERIC_READ           (0x80000000L)
#define GENERIC_WRITE          (0x40000000L)
#define GENERIC_EXECUTE        (0x20000000L)
#define GENERIC_ALL            (0x10000000L)

毫无疑问,在API声明里,CreatFile()函数的第二个参数为“GENERIC_READ | GENERIC_WRITE” = 0x80000000 | 0x40000000 = 0xC0000000。

CreatFile()函数如何检测标志位呢?

我们可以在Windows XP SP3 x86的KERNEL32.DLL中,找到CreateFileW()函数的相关代码。

指令清单19.3 KERNEL32.DLL (Windows XP SP3 x86)

.text:7C83D429  test       byte ptr [ebp+dwDesiredAccess+3], 40h
.text:7C83D42   Dmov       [ebp+var_8], 1
.text:7C83D434  jz         short loc_7C83D417
.text:7C83D436  jmp        loc_7C810817

比较讲究的是TEST指令。在这里,它没有整个使用第二个参数,而是仅仅拿它数权最高的头一个字节(ebp+dwDesiredAccess+3)和0x40(对应GENERIC_WRITE标志)进行与运算。

TEST与AND指令的唯一区别是前者不保存运算结果,CMP指令和SUB指令之间也存在这种差别(请参见本书7.3.1节)。

即,上述可执行的程序源代码逻辑是:

if ((dwDesiredAccess&0x40000000) == 0) goto loc_7C83D417

如果此处的与运算(&)的结果是1,则会清零ZF标志位,而不会触发JZ跳转。只有在dwDesiredAccess变量与0x40000000的计算结果为0的情况下,条件转移指令才会被触发;即与运算(&)的结果是零、ZF标志位为1,从而触发条件转移指令。

如果使用Linux的GCC 4.4.1编译下面的代码:

#include <stdio.h>
#include <fcntl.h>

void main() 
{
        int handle;
        handle=open ("file", O_RDWR | O_CREAT);
};

得到的汇编指令会如下所示。

指令清单19.4 GCC 4.4.1

           public main
main       proc near

var_20     = dword ptr -20h
var_1C     = dword ptr -1Ch
var_4      = dword ptr -4

           push    ebp
           mov     ebp, esp
           and     esp, 0FFFFFFF0h
           sub     esp, 20h
           mov     [esp+20h+var_1C], 42h
           mov     [esp+20h+var_20], offset aFile ; "file"
           call    _open
           mov     [esp+20h+var_4], eax
           leave
           retn
main       endp

在库文件libc.so.6里,open()函数只是调用syscall而已。

指令清单19.5 open() (libc.so.6)

.text:000BE69B            mov  edx, [esp+4+mode] ; mode
.text:000BE69F            mov  ecx, [esp+4+flags] ; flags
.text:000BE6A3            mov  ebx, [esp+4+filename] ; filename
.text:000BE6A7            mov  eax, 5
.text:000BE6AC            int  80h       ; LINUX - sys_open

可见,在执行Open()函数时,Linux内核会检测某些标识位。

当然,我们可以下载Glibc和Linux 内核源代码来一窥究竟。但是本文旨在粗略地介绍原理,就不逐行地解释代码了。

在Linux 2.6中,当程序通过syscall调用 sys_open的时候,它调用的函数实际上是内核函数 do_sys_open()。在执行函数do_sys_open()的时候,系统又会调用do_filp_open() 函数。有兴趣的读者,可以在Linux内核源代码里的fs/namei.c里找到这部分内容。

编译器不仅会使用栈来传递参数,它还会使用寄存器传递部分参数。编译器最常采用的函数调用约定是fastcall(参见6.4.3节)。这个规范优先使用寄存器来传递参数。这使得CPU不必每次都要访问内存里的数据栈,大大提升了程序的运行效率。此外,我们可以通过GCC的regparm选项[1],设置传递参数的寄存器数量。

在Linux 2.6内核的编译选项中,设定了寄存器选项“-mregparm=3”。[2]

这个选项决定,编译器首先通过EAX、EDX和ECX寄存器传递函数所需的头3个参数,再通过栈传递其余的参数。当然,如果参数的总数不足3个,它只会用到部分寄存器。

在Ubuntu里下载Linux Kernel 2.6.31,并用“make vmlinux”指令编译,然后使用IDA打开程序,寻找函数do_filp_open()。这个函数的开头部分大体是这样的。

指令清单19.6 do_filp_open() (Linux kernel 2.6.31)

do_filp_open    proc near
...... 
                push    ebp
                mov     ebp, esp
                push    edi
                push    esi
                push    ebx
                mov     ebx, ecx
                add     ebx, 1
                sub     esp, 98h
                mov     esi, [ebp+arg_4]  ; acc_mode (5th arg)
                test    bl, 3
                mov     [ebp+var_80], eax ; dfd (1th arg)
                mov     [ebp+var_7C], edx ; pathname (2th arg)
                mov     [ebp+var_78], ecx ; open_flag (3th arg)
                jnz     short loc_C01EF684
                mov     ebx, ecx          ; ebx <- open_flag

函数序言部分,GCC就把3个寄存器里的参数值存储在栈里。若非如此,那么后续程序可能出现寄存器不够使用的资源紧张问题。

我们再来看下do_filp_open()函数的另外一段代码。

指令清单19.7 do\_filp\_open() (Linux kernel 2.6.31)

loc_C01EF6B4:                       ; CODE XREF: do_filp_open+4F
                test    bl, 40h     ; O_CREAT
                jnz     loc_C01EF810
                mov     edi, ebx
                shr     edi, 11h
                xor     edi, 1
                and     edi, 1
                test    ebx, 10000h
                jz      short loc_C01EF6D3
                or      edi, 2

汇编宏O_CREAT的值就是0x40h。TEST指令检查open_flag里是否存在0x40的标志位,如果这个位是1,则会触发下一条JNZ指令。

19.1.2 ARM

在Linux Kernel 3.8.0平台的系统里,O_CREAT的检查操作有所不同。

指令清单19.8 Linux kernel 3.8.0

struct file *do_filp_open(int dfd, struct filename *pathname,
                const struct open_flags *op)
{
...
        filp = path_openat(dfd, pathname, &nd, op, flags | LOOKUP_RCU);
...
}

static struct file *path_openat(int dfd, struct filename *pathname,
                struct nameidata *nd, const struct open_flags *op, int flags)
{
...
        error = do_last(nd, &path, file, op, &opened, pathname);
...
}
static int do_last(struct nameidata *nd, struct path *path,
                   struct file *file, const struct open_flags *op,
                   int *opened, struct filename *name)
{ ...
        if (!(open_flag & O_CREAT)) {
    ...
                error = lookup_fast(nd, path, &inode);
    ...
        } else {
    ...
                error = complete_walk(nd);
        }
...
}

使用IDA打开ARM模式的内核程序,可以看到do_last()函数的代码如下所示。

指令清单19.9 do_last() (vmlinux)

...
.text:C0169EA8     MOV        R9, R3  ; R3 - (4th argument) open_flag
...
.text:C0169ED4     LDR        R6, [R9] ; R6 - open_flag
...
.text:C0169F68     TST        R6, #0x40 ; jumptable C0169F00 default case
.text:C0169F6C     BNE        loc_C016A128
.text:C0169F70     LDR        R2, [R4,#0x10]
.text:C0169F74     ADD        R12, R4, #8
.text:C0169F78     LDR        R3, [R4,#0xC]
.text:C0169F7C     MOV        R0, R4
.text:C0169F80     STR        R12, [R11,#var_50]
.text:C0169F84     LDRB       R3, [R2,R3]
.text:C0169F88     MOV        R2, R8
.text:C0169F8C     CMP        R3, #0
.text:C0169F90     ORRNE      R1, R1, #3
.text:C0169F94     STRNE      R1, [R4,#0x24]
.text:C0169F98     ANDS       R3, R6, #0x200000
.text:C0169F9C     MOV        R1, R12
.text:C0169FA0     LDRNE      R3, [R4,#0x24]
.text:C0169FA4     ANDNE      R3, R3, #1
.text:C0169FA8     EORNE      R3, R3, #1
.text:C0169FAC     STR        R3, [R11,#var_54]
.text:C0169FB0     SUB        R3, R11, #-var_38
.text:C0169FB4     BL         lookup_fast
...
.text:C016A128 loc_C016A128                  ; CODE XREF: do_last.isra.14+DC
.text:C016A128     MOV        R0, R4
.text:C016A12C     BL         complete_walk
...

TST指令的功能与x86平台的TEST指令相同。

显而易见,程序在某一条件下会调用lookup_fast()函数,而在另一条件下会调用complete_walk()函数。这种行为符合do_last()函数的源代码。

这里的汇编宏O_CREAT也等于0x40。

19.2 设置/清除特定位

本节将会围绕下面这个程序进行讨论:

#include <stdio.h>

#define IS_SET(flag, bit)       ((flag) & (bit))
#define SET_BIT(var, bit)       ((var) |= (bit))
#define REMOVE_BIT(var, bit)    ((var) &= ~(bit))

int f(int a) 
{
    int rt=a;
    SET_BIT (rt, 0x4000);
    REMOVE_BIT (rt, 0x200);
    return rt; 
};

int main() 
{
    f(0x12340678);
};
19.2.1 x86

Non-optimizing MSVC

经过MSVC 2010(未启用任何优化选项)编译上述程序,可得到如下所示的指令。

指令清单19.10 MSVC 2010

_rt$ = -4             ; size = 4
_a$ = 8               ; size = 4

_f  PROC
    push   ebp
    mov    ebp, esp
    push   ecx
    mov    eax, DWORD PTR _a$[ebp]
    mov    DWORD PTR _rt$[ebp], eax
    mov    ecx, DWORD PTR _rt$[ebp]
    or     ecx, 16384               ; 00004000H
    mov    DWORD PTR _rt$[ebp], ecx
    mov    edx, DWORD PTR _rt$[ebp]
    and    edx, -513                ; fffffdffH
    mov    DWORD PTR _rt$[ebp], edx
    mov    eax, DWORD PTR _rt$[ebp]
    mov    esp, ebp
    pop    ebp
    ret    0
_f  ENDP

OR 指令就是逐位进行或运算的指令,可用来将指定位置1。

AND指令的作用是重置bit位。效果上说,如果立即数的某个bit位为1,AND指令则会保留寄存器里的这个bit位;如果立即数的某个bit位为0,AND指令就会把寄存器里这个bit的值设置为0。按照bit位掩码(bitmask)的方式理解,就会非常容易地记住这些指令的作用。

OllyDbg

用OllyDbg打开这个程序,可以清楚地看到常量的各个位:

0x200的二进制数是00000000000000000001000000000,第10位是1。

0x200的逻辑非运算结果是0xFFFFFDFF(11111111111111111110111111111)。

0x4000的第15位是1。

如图19.1所示,输入变量为0x12340678 (10010001101000000011001111000)。

..\TU\1901.tif{}

图19.1 OllyDbg:ECX寄存器载入输入变量

执行OR指令的情形如图19.2所示。

..\TU\1902.tif{}

图19.2 OllyDbg:执行OR指令

在执行OR指令的时候,第15位被设为1。

因为没有进行优化编译,所以程序中有些无用指令。如图19.3所示,它又加载了一次这个值。

..\TU\1903.tif{}

图19.3 OllyDbg:EDX寄存器再次加载运算结果

然后进行了AND与操作,如图19.4所示。

..\TU\1904.tif{}

图19.4 OllyDbg:执行与操作

这时寄存器的第10位被清零。换句话说,第10位之外的所有位都被保留了。最终运算结果是0x12344478,即二进制的10010001101000100010001111000。

Optimizing MSVC

如果开启了MSVC的优化选项/Ox,生成的代码就会精简很多。

指令清单19.11 Optimizing MSVC

_a$ = 8                      ; size = 4
_f     PROC
    mov    eax, DWORD PTR _a$[esp-4]
    and    eax, -513         ; fffffdffH
    or     eax, 16384        ; 00004000H
    ret    0 
_f     ENDP

Non-optimizing GCC

如果关闭GCC 4.4.1的优化选项,则会生成下列代码。

指令清单19.12 Non-optimizing GCC

           public f
f          proc near

var_4      = dword ptr -4
arg_0      = dword ptr  8

           push     ebp
           mov      ebp, esp
           sub      esp, 10h
           mov      eax, [ebp+arg_0]
           mov      [ebp+var_4], eax
           or       [ebp+var_4], 4000h
           and      [ebp+var_4], 0FFFFFDFFh
           mov      eax, [ebp+var_4]
           leave
           retn
f          endp

虽然GCC的非优化编译结果中存在冗余指令,但是这个程序仍然比MSVC的非优化编译程序要短。

接下来启用GCC的-O3选项进行优化编译。

Optimizing GCC

指令清单19.13 Optimizing GCC

           public f
f          proc near

arg_0      = dword ptr  8

           push     ebp
           mov      ebp, esp
           mov      eax, [ebp+arg_0]
           pop      ebp
           or       ah, 40h
           and      ah, 0FDh
           retn
f          endp

它比MSVC优化编译生成的程序还要短。值得注意的是,它直接使用了EAX寄存器的部分空间——EAX寄存器的第8到第15位(第1个字节),即AH寄存器。

7th (字节号)
6th
5th
4th
3rd
2nd
1st
0th
RAX x64
EAX
AX
AH
AL

在早期的16位8086 CPU里,AX寄存器分为2个8位寄存器——即AL/AH寄存器。而80386差不多把所有的寄存器都扩展为32位,形成了EAX寄存器。但是出于兼容性的考虑,后续的CPU保留了AX/AH/AL寄存器的命名空间。

世上先有的16位 8086 CPU,后有的32位x86 CPU。在早期16位CPU上运行短程序,其opcode比在32位CPU上运行的opcode要短。所以,操作AH寄存器的“or ah,40h”的指令只占用了3字节的opcode。虽然说似乎“or eax,04000h”这样的指令更合乎情理,但是那样就会占用5字节的opcode;如果第一个操作符不是EAX寄存器,同等的指令甚至会使用6字节的opcode。

Optimizing GCC and regparm

如果同时启用优化选项“-O3”和寄存器分配选项“regparm=3”,生成的指令会更为简短。

指令清单19.14 Optimizing GCC

           public f
f          proc near
           push     ebp
           or       ah, 40h
           mov      ebp, esp
           and      ah, 0FDh
           pop      ebp
           retn 
f          endp

第一个参数原本就在EAX寄存器里(fastcall规范),所以可直接使用EAX寄存器。函数引言的“push ebp / mov ebp,esp”指令,以及函数尾声的“pop ebp”完全可以省略;但是GCC还做不到这种程度的智能优化。这种代码完全可以作为内嵌函数(参见第43章)来使用。

19.2.2 ARM + Optimizing Keil 6/2013 (ARM mode)

指令清单19.15 Optimizing Keil 6/2013 (ARM mode)

02 0C C0 E3     BIC     R0, R0, #0x200
01 09 80 E3     ORR     R0, R0, #0x4000
1E FF 2F E1     BX      LR

BIC是逐位清除的“(反码)逻辑与”指令,它将第一个操作数与第二个操作数的反码(非求非运算的结果,进行逻辑与运算,比)x86指令集里“逻辑与”指令多作了一次求非运算,ORR是“逻辑或指令”,与x86“逻辑或”的作用相同。

19.2.3 ARM + Optimizing Keil 6/2013 (Thumb mode)

指令清单19.16 Optimizing Keil 6/2013 (Thumb mode)

01 21 89 03     MOVS      R1, 0x4000
08 43ORRS       R0,       R1
49 11ASRS       R1,       R1, #5   ; generate 0x200 and place to R1
88 43           BICS      R0, R1
70 47           BX        LR

编译器借助了算术右移指令,由0x4000>>5生成0x200。与直接对寄存器进行立即数赋值(0x200)相比,这种算术指令的opcode比较短。

所以,后面的ASRS(算术右移)指令通过计算0x4000>>5得到0x200。

19.2.4 ARM + Optimizing Xcode (LLVM) + ARM mode

指令清单19.17 Optimizing Xcode 4.6.3 (LLVM) (ARM mode)

42 0C C0 E3     BIC             R0, R0, #0x4200
01 09 80 E3     ORR             R0, R0, #0x4000
1E FF 2F E1     BX              LR

这段代码由LLVM编译而得。其源代码大体应该是:

REMOVE_BIT (rt, 0x4200);
SET_BIT (rt, 0x4000);

它确实足以完成所需功能。但是哪里来的0x4200? 或许,LLVM优化功能对原有指令进行了再加工,或许这是负负得正。总之这段代码没有质量问题。

有时候编译器确实会做这种类型的代码处理,详细情况请参见第91章。

使用Xcode 4.6.3 进行优化编译而生成的代码也非常相似,本文不再介绍。

19.2.5 ARM:BIC指令详解

把本章开头的源代码略加修改:

int f(int a) 
{
    int rt=a;

    REMOVE_BIT (rt, 0x1234);

    return rt; 
};

用Keil 5.03进行优化编译[3],可得ARM模式的指令如下:

f PROC
        BIC      r0,r0,#0x1000
        BIC      r0,r0,#0x234
        BX       lr
        ENDP

上述程序使用了两条BIC指令,即它需要通过两次处理才能清除0x1234对应的比特位。这是因为立即数0x1234无法和BIC指令封装在同一条指令里。所以编译器进行了等效处理,通过两条指令实现清空0x1000和0x234相应的比特位。

19.2.6 ARM64: Optimizing GCC(Linaro) 4.9

面向ARM64的GCC编译器,可直接使用AND指令、而不用BIC指令。

指令清单19.18 Optimizing GCC (Linaro) 4.9

f:
        add   w0, w0, -513    ; 0xFFFFFFFFFFFFFDFF
        orr   w0, w0, 16384   ; 0x4000
        ret
19.2.7 ARM64: Non-optimizing GCC (Linaro) 4.9

关闭优化选项之后,GCC生成的代码中会加载无用指令,但是功能相同。

指令清单19.19 Non-optimizing GCC (Linaro) 4.9

f:
        sub     sp, sp, #32
        str     w0, [sp,12]
        ldr     w0, [sp,12]
        str     w0, [sp,28]
        ldr     w0, [sp,28]
        orr     w0, w0, 16384        ; 0x4000
        str     w0, [sp,28]
        ldr     w0, [sp,28]
        and     w0, w0, -513         ; 0xFFFFFFFFFFFFFDFF
        str     w0, [sp,28]
        ldr     w0, [sp,28]
        add     sp, sp, 32
        ret
19.2.8 MIPS

指令清单19.20 Optimizing GCC 4.4.5 (IDA)

f:
; $a0=a
                ori     $a0, 0x4000
; $a0=a|0x4000
                li      $v0, 0xFFFFFDFF
                jr      $ra
                and     $v0, $a0, $v0
; at finish: $v0 = $a0&$v0 = a|0x4000 & 0xFFFFFDFF

ORI无疑还是OR指令。指令中的“I”意味着它使用机械码存储数值。

但是后面的AND指令可就不能是ANDI指令了。这是因为它涉及的立即数0xFFFFFDFF太长,无法连同操作指令封装在同一条指令里。所以编译器把这个数赋值给$V0寄存器,然后让它与其他寄存器进行AND/与运算。

19.3 位移

C/C++的位移运算符是<<和>>。

x86指令集里有对应的左移SHL和右移SHR指令。

位移操作通常用来实现与“2的n次幂”有关的乘法和除法运算。有关介绍请参见本书的16.1.2节和16.2.1节。

位移指令可用来对特定位进行取值或隔离,用途十分广泛。

19.4 在FPU上设置特定位

FPU存储数据的IEEE 754格式如下:

..\TU\p1901.tif

最高数权位MSB为符号位。是否可能在不使用FPU指令的前提下变更浮点数的符号呢?

#include <stdio.h>

float my_abs (float i)
{
        unsigned int tmp=(*(unsigned int*)&i) & 0x7FFFFFFF;
        return *(float*)&tmp;
};

float set_sign (float i)
{
        unsigned int tmp=(*(unsigned int*)&i) | 0x80000000;
        return *(float*)&tmp;
};
float negate (float i)
{
        unsigned int tmp=(*(unsigned int*)&i) ^ 0x80000000;
        return *(float*)&tmp;
};

int main() 
{
        printf ("my_abs():\n");
        printf ("%f\n", my_abs (123.456));
        printf ("%f\n", my_abs (-456.123));
        printf ("set_sign():\n");
        printf ("%f\n", set_sign (123.456));
        printf ("%f\n", set_sign (-456.123));
        printf ("negate():\n");
        printf ("%f\n", negate (123.456));
        printf ("%f\n", negate (-456.123));
};

使用位操作C/C++指令之后,我们不必在CPU和FPU的寄存器之间传递数据、再进行数学运算了。本节列举了三个位操作函数:清除MSB符号位的my_abs()函数、设置符号位的set_sign()函数及求负函数negate()。

19.4.1 XOR操作详解

XOR指令常用于使一个操作数的某些位取反的场合。若操作数A的某个位为1,那么XOR指令将对另一个数的相应位求非。

输入A

输入B

输出

0

0

0

0

1

1

1

0

1

1

1

0

若某个参数为零,XOR则不会进行任何操作。这种指令也就是所谓的空操作。这是XOR指令非常重要的属性,建议记住它。

19.4.2 x86

编译生成的指令简单易懂。

指令清单19.21 Optimizing MSVC 2012

_tmp$ = 8
_i$ = 8
_my_abs PROC
        and     DWORD PTR _i$[esp-4], 2147483647    ; 7fffffffH
        fld     DWORD PTR _tmp$[esp-4]
        ret     0
_my_abs ENDP

_tmp$ = 8
_i$ = 8
_set_sign PROC
        or      DWORD PTR _i$[esp-4], -2147483648   ; 80000000H
        fld     DWORD PTR _tmp$[esp-4]
        ret     0
_set_sign ENDP

_tmp$ = 8
_i$ = 8
_negate PROC
        xor     DWORD PTR _i$[esp-4], -2147483648   ; 80000000H
        fld     DWORD PTR _tmp$[esp-4]
        ret     0
_negate ENDP

函数从栈中提取一个浮点类型的数据,但是把它当作整数类型数据进行处理。

AND和OR设置相应的比特位,而XOR用来设置相反的符号位。

因为要把浮点数还给FPU,所以最后把修改后的处理结果保存到ST0寄存器。

接下来,使用 64位的MSVC 2012进行优化编译,得到的代码如下所示。

指令清单19.22 Optimizing MSVC 2012 x64

tmp$ = 8
i$ = 8
my_abs  PROC
        movss   DWORD PTR [rsp+8], xmm0
        mov     eax, DWORD PTR i$[rsp]
        btr     eax, 31
        mov     DWORD PTR tmp$[rsp], eax
        movss   xmm0, DWORD PTR tmp$[rsp]
        ret     0
my_abs  ENDP
_TEXT   ENDS

tmp$ = 8
i$ = 8
set_sign PROC
        movss   DWORD PTR [rsp+8], xmm0
        mov     eax, DWORD PTR i$[rsp]
        bts     eax, 31
        mov     DWORD PTR tmp$[rsp], eax
        movss   xmm0, DWORD PTR tmp$[rsp]
        ret     0
set_sign ENDP

tmp$ = 8
i$ = 8
negate  PROC
        movss   DWORD PTR [rsp+8], xmm0
        mov     eax, DWORD PTR i$[rsp]
        btc     eax, 31
        mov     DWORD PTR tmp$[rsp], eax
        movss   xmm0, DWORD PTR tmp$[rsp]
        ret     0
negate  END

输入值会经XMM0寄存器存储到局部数据栈,然后通过BTR、BTS、BTC等指令进行处理。

这些指令用于重置(BTR)、置位(BTS)和翻转(BTC)特定比特位。如果从0开始数的话,浮点数的第31位才是MSB。

最终,运算结果被复制到XMM0寄存器。在Win64系统中,浮点型返回值要保存在这个寄存器里。

19.4.3 MIPS

面向MIPS的GCC 4.4.5生成的程序几乎没什么区别。

指令清单19.23 Optimizing GCC 4.4.5 (IDA)

my_abs:
; move from coprocessor 1:
                   mfc1     $v1, $f12
                   li       $v0, 0x7FFFFFFF
; $v0=0x7FFFFFFF
; do AND:
                   and      $v0, $v1
; move to coprocessor 1:
                   mtc1     $v0, $f0
; return
                   jr       $ra
                   or       $at, $zero ; branch delay slot

set_sign:
; move from coprocessor 1:
                   mfc1     $v0, $f12
                   lui      $v1, 0x8000
; $v1=0x80000000
; do OR:
                   or       $v0, $v1, $v0
; move to coprocessor 1:
                   mtc1    $v0, $f0
; return                
                   jr       $ra
                   or       $at, $zero ; branch delay slot
negate:
; move from coprocessor 1:
                   mfc1     $v0, $f12
                   lui      $v1, 0x8000
; $v1=0x80000000
; do XOR
                   xor      $v0, $v1, $v0
; move to coprocessor 1:
                   mtc1     $v0, $f0
; return
                   jr       $ra
                   or       $at, $zero ; branch delay slot

因为LUI在传递高16位数据时会清除寄存器的低16位,所以单条LUI指令就可以完成0x80000000的赋值,无需再用ORI指令。

19.4.4 ARM

Optimizing Keil 6/2013 (ARM mode)

指令清单19.24 Optimizing Keil 6/2013 (ARM mode)

my_abs PROC
; clear bit:
        BIC      r0,r0,#0x80000000
        BX       lr
        ENDP

set_sign PROC
; do OR:
        ORR      r0,r0,#0x80000000
        BX       lr
        ENDP

negate PROC
; do XOR:
        EOR      r0,r0,#0x80000000
        BX       lr
        ENDP

ARM模式的程序可以使用BIC指令直接清除指定的比特位。上述程序中的EOR指令是ARM模式下进行XOR(异或)运算的指令。

Optimizing Keil 6/2013 (Thumb mode)

指令清单19.25 Optimizing Keil 6/2013 (Thumb mode)

my_abs PROC
        LSLS     r0,r0,#1
; r0=i<<1
        LSRS     r0,r0,#1
; r0=(i<<1)>>1
        BX       lr
        ENDP

set_sign PROC
        MOVS     r1,#1
; r1=1
        LSLS     r1,r1,#31
; r1=1<<31=0x80000000
        ORRS     r0,r0,r1
; r0=r0 | 0x80000000
        BX       lr
        ENDP

negate PROC
        MOVS     r1,#1
; r1=1
        LSLS     r1,r1,#31
; r1=1<<31=0x80000000
        EORS     r0,r0,r1
; r0=r0 ^ 0x80000000
        BX       lr
        ENDP

ARM平台的Thumb模式指令都是16位定长指令。因为单条指令无法封装太大的数据,所以编译器使用了MOVS/LSLS指令对传递常量0x80000000。这种赋值操作基于数学机制:1<<31=0x80000000。

然而my_abs的指令令人费解,它做的运算是(i<<1)>>1。虽然看上去是画蛇添足,但是在进行“输入变量<<1”的运算时,最高数权位被舍弃了。继而在执行“运算结果>>1”的语句时,根据右移运算规则最高数权位变为零,而其他各位数值回归原位。借助LSLS/LSRS指令对,该函数清除了最高数权位MSB。

Optimizing GCC 4.6.3 (Raspberry Pi, ARM mode)

指令清单19.26 Optimizing GCC 4.6.3 for Raspberry Pi (ARM mode)

my_abs
; copy from S0 to R2:
                FMRS    R2, S0
; clear bit:
                BIC     R3, R2, #0x80000000
; copy from R3 to S0:
                FMSR    S0, R3
                BX      LR

set_sign
; copy from S0 to R2:
                FMRS    R2, S0
; do OR:
                ORR     R3, R2, #0x80000000
; copy from R3 to S0:
                FMSR    S0, R3
                BX      LR

negate
; copy from S0 to R2:
                FMRS    R2, S0
; do ADD:
                ADD     R3, R2, #0x80000000
; copy from R3 to S0:
                FMSR    S0, R3
                BX      LR

在 QEMU的仿真环境下启动Raspberry Pi Linux即可模拟ARM FPU。所以上述程序使用S-字头寄存器存储浮点数,而不会使用R-字头寄存器。

FMRS指令用于在通用寄存器GPR和FPU之间交换数据。

上述程序中的my_abs()函数和set_sign()函数都中规中矩。但是negate()函数在应该出现XOR指令的地方使用了ADD指令。

其实“ADD register, 0x80000000”和“XOR register, 0x80000000”是等效指令,只是不特别直观而已。整个函数用于变更最高数权位的值。在数学上,1000与任意三位数相加,运算结果的最后3位仍然和被加数的最后三位相等。同理,1234567+10000=1244567,和的最后四位与第一个数的最后四位等值。以二进制数的角度来看,0x80000000就是100000000000000000000000000000000,只有最高位是1。因此,当0x80000000与任意数值相加时,运算结果的最后31位还是被加数的最后31位,只是最高数权位会发生变化。再看MSB:1+0=1,1+1=0(高于32位的数值被舍弃了)。因此,对于这个特定加数来说,ADD指令和XOR指令可以互换。虽然替换的必要性不甚明朗,但是整个程序还是没有问题的。

19.5 位校验

我们介绍一个测算输入变量的2进制数里有多少个1的函数。这种函数叫作“population count/点数”函数。在支持SSE4的x86 CPU的指令集里,甚至有直接对应的POPCNT指令。

#include <stdio.h>

#define IS_SET(flag, bit)    ((flag) & (bit))

int f(unsigned int a)
{
    int i;
    int rt=0;

for (i=0; i<32; i++)
    if (IS_SET (a, 1<<i))
        rt++;

    return rt;
};
int main()
{
    f(0x12345678); // test
};

在这个循环里,循环计数变量i的取值范围是0~31。因此“1<<i”表达式的取值范围是0到0x80000000,用人类语言解释,它的含义就是“将数字1左移n位”。“1<<i”将会使“1”逐一遍历32位数字的每一位,同时将其他位置零。

这段程序里,1<<i可能产生的值有:

C/C++表达式

2的指数

十进制数

十六进制数

1<<0

20

1

1

1<<1

21

2

2

1<<2

22

4

4

1<<3

23

8

8

1<<4

24

16

0x10

1<<5

25

32

0x20

1<<6

26

64

0x40

1<<7

27

128

0x80

1<<8

28

256

0x100

1<<9

29

512

0x200

1<<10

210

1024

0x400

1<<11

211

2048

0x800

1<<12

212

4096

0x1000

1<<13

213

8192

0x2000

1<<14

214

16384

0x4000

1<<15

215

32768

0x8000

1<<16

216

65536

0x10000

1<<17

217

131072

0x20000

1<<18

218

262144

0x40000

1<<19

219

524288

0x80000

1<<20

220

1048576

0x100000

1<<21

221

2097152

0x200000

1<<22

222

4194304

0x400000

1<<23

223

8388608

0x800000

1<<24

224

16777216

0x1000000

1<<25

225

33554432

0x2000000

1<<26

226

67108864

0x4000000

1<<27

227

134217728

0x8000000

1<<28

228

268435456

0x10000000

1<<29

229

536870912

0x20000000

1<<30

230

1073741824

0x40000000

1<<31

231

2147483648

0x80000000

逆向工程的实际工作中经常出现这些常数(bit mask)。逆向工程人员应当常备这个表格。虽然10进制常数很难记忆,但是背下十六进制数并不太困难。

它们经常被用作各种标志位。例如,在Apache 2.4.6的源代码中,ssl_private.h就用到了其中的部分常量:

/**
 * Define the SSL options
 */
#define SSL_OPT_NONE            (0)
#define SSL_OPT_RELSET          (1<<0)
#define SSL_OPT_STDENVVARS      (1<<1)
#define SSL_OPT_EXPORTCERTDATA  (1<<3)
#define SSL_OPT_FAKEBASICAUTH   (1<<4)
#define SSL_OPT_STRICTREQUIRE   (1<<5)
#define SSL_OPT_OPTRENEGOTIATE  (1<<6)
#define SSL_OPT_LEGACYDNFORMAT  (1<<7)

现在言归正传,看看“点数”程序。

宏IS_SET的作用是检测flag参数(变量a)的第n位是否为1。

如果变量a对应的比特位不是1,则宏IS_SET返回0;如果变量a对应的比特位是1,则返回bit mask。因为触发if()then{}语句的条件是“条件表达式不是零”,所以哪怕条件返回值是123456,它都会照样执行then模块的指令。

19.5.1 x86

MSVC

使用MSVC2010编译上述程序,得到的代码如下所示。

指令清单19.27 MSVC 2010

_rt$ = -8             ;size=4
_i$ =-4               ;size=4
_a$ =8                ;size=4

_f PROC
    push   ebp
    mov    ebp, esp
    sub    esp, 8
    mov    WORD PTR _rt$[ebp], 0
    mov    DWORD PTR _i$[ebp], 0
    jmp    SHORT $LN4@f
$LN3@f:
    mov    ax, DWORD PTR _i$[ebp]    ; 递增
    add    x, 1
    mov    WORD PTR _i$[ebp], eax
$LN4@f:
    cmp    DWORD PTR _i$[ebp], 32    ; 00000020H
    jge    SHORT $LN2@f              ; 循环结束?
    mov    edx, 1
    mov    ecx, DWORD PTR _i$[ebp]
    shl    edx, cl                   ; EDX=EDX<<CL
    and    edx, DWORD PTR _a$[ebp]
    je     SHORT $LN1@f              ; result of AND instruction was 0?
                                     ; then skip next instructions
    mov    eax, DWORD PTR _rt$[ebp]  ; no, not zero
    add    eax, 1                    ; increment rt
    mov    DWORD PTR _rt$[ebp], eax
$LN1@f:
    jmp    SHORT $LN3@f
    $LN2@f:
    mov    eax, DWORD PTR _rt$[ebp]
    mov    esp, ebp
    pop    ebp
    ret    0
_f    ENDP

OllyDbg

为了方便使用OllyDbg进行演示,我们设置变量a的值为0x12345678。

i=1时的情况如图19.5所示。

..\TU\1905.tif{}

图19.5 OllyDbg:i=1时,i被加载到ECX寄存器

此刻EDX的值为1。

执行SHL指令的情况,如图19.6所示。

..\TU\1906.tif{}

图19.6 OllyDbg:i = 1,EDX=1<<1 = 2

EDX寄存器的值是bit mask ,1<<1=2。

在执行AND指令后,ZF=1。就是说,输入变量0x12345678和数字2的AND计算结果是0,如图19.7所示。

..\TU\1907.tif{}

图19.7 OllyDbg:i=1,输入变量的对应比特位是1么?否(ZF=1)

这意味着输入变量的对应比特位是0。这种情况下,程序通过JZ指令进行跳转,绕过了操作点数计数器rt的递增指令。

继续执行程序,看看i=4的情况。如图19.8所示,此时要执行SHL指令。

..\TU\1908.tif{}

图19.8 OllyDbg:i=4, ECX加载i的值

此刻EDX寄存器的值是0x10,它是1<<4的结果,如图19.9所示。

..\TU\1909.tif{}

图19.9 OllyDbg:i = 4, EDX =1<<4 = 0x10

i=4时,对应的bit mask存在。

执行AND指令的情形如图19.10所示。

..\TU\1910.tif{}

图19.10 OllyDbg:i=4,输入变量的对应位是否为1?是(ZF=0)

因为对应bit位是1,所以ZF=0。确实,0x12345678 & 0x10 = 0x10。这种情况下,将不会触发jz转移指令,点数计数器rt的值递增。

最终,函数的返回值是13。输入变量0x12345678的二进制数里有13个1。

GCC

使用GCC 4.4.1编译上述程序,可得如下所示的指令。

指令清单19.28 GCC 4.4.1

             public f
f            proc near

rt           = dword ptr -0Ch
i            = dword ptr -8
arg_0        = dword ptr  8

             push    ebp
             mov     ebp, esp
             push    ebx
             sub     esp, 10h
             mov     [ebp+rt], 0
             mov     [ebp+i], 0
             jmp     short loc_80483EF
loc_80483D0:
             mov     eax, [ebp+i]
             mov     edx, 1
             mov     ebx, edx
             mov     ecx, eax
             shl     ebx, cl
             mov     eax, ebx
             and     eax, [ebp+arg_0]
             test    eax, eax
             jz      short loc_80483EB
             add     [ebp+rt], 1
loc_80483EB:
             add     [ebp+i], 1
loc_80483EF:
             cmp     [ebp+i], 1Fh
             jle     short loc_80483D0
             mov     eax, [ebp+rt]
             add     esp, 10h
             pop     ebx
             pop     ebp
             retn
f            endp
19.5.2 x64

为了进行演示,本节对源程序略加修改,将数据类型扩展为64位:

#include <stdio.h>
#include <stdint.h>

#define IS_SET(flag, bit)   ((flag) & (bit))

int f(uint64_t a)
{
    uint64_t i;
    int rt=0;

    for (i=0; i<64; i++)
        if (IS_SET (a, 1ULL<<i))
            rt++;

    return rt; 
};

Non-optimizing GCC 4.8.2

指令清单19.29 Non-optimizing GCC 4.8.2

f:
        push    rbp
        mov     rbp, rsp
        mov     QWORD PTR [rbp-24], rdi   ; a
        mov     DWORD PTR [rbp-12], 0     ; rt=0
        mov     QWORD PTR [rbp-8], 0      ; i=0
        jmp     .L2
.L4:
        mov     rax, QWORD PTR [rbp-8]
        mov     rdx, QWORD PTR [rbp-24]
; RAX = i, RDX = a
        mov     ecx, eax
; ECX = i
        shr     rdx, cl
; RDX = RDX>>CL = a>>i
        mov     rax, rdx
; RAX = RDX = a>>i
        and     eax, 1
; EAX = EAX&1 = (a>>i)&1
        test    rax, rax
; the last bit is zero?
; skip the next ADD instruction, if it was so.
        je      .L3
        add     DWORD PTR [rbp-12], 1     ; rt++
.L3:
        add     QWORD PTR [rbp-8], 1      ; i++
.L2:
        cmp     QWORD PTR [rbp-8], 63     ; i< 63?
        jbe     .L4                       ; jump to the loop boday begin, if so
        mov     eax, DWORD PTR [rbp-12]   ; return rt
        pop     rbp
        ret

Optimizing GCC 4.8.2

指令清单19.30 Optimizing GCC 4.8.2

 1 f:
 2      xor     eax, eax             ; rt variable will be in EAX register
 3      xor     ecx, ecx             ; i variable will be in ECX register
 4 .L3:
 5      mov     rsi, rdi             ; load input value
 6      lea     edx, [rax+1]         ; EDX=EAX+1
 7 ; EDX here is a "new version of rt", which will be written into rt variable, if the last bit is 1
 8      shr     rsi, cl              ; RSI=RSI>>CL
 9      and     esi, 1               ; ESI=ESI&1
10 ; the last bit is 1? If so, write "new version of rt" into EAX
11      cmovne  eax, edx
12      add     rcx, 1               ; RCX++
13      cmp     rcx, 64
14      jne     .L3
15      rep ret                      ; AKA fatret

这段程序简洁又兼具特色。在本节前面介绍过的各个例子里,程序都是先比较特定位、然后在递增“rt”的值。但是这段程序的顺序有所不同,它先递增rt再把新的值写到EDX寄存器。这样一来,如果最后的比特位是1,那么程序将使用CMOVNE[4]指令(等同于CMOVNZ[5])把EDX寄存器(rt的候选值)传递给EAX寄存器(当前的rt值,也是函数的返回值),从而完成rt的更新。所以,无论输入值是什么,每次迭代结束之后,循环控制变量的值都要进行递增,它肯定会被递增64次。

因为它只含有一个条件转移指令(在循环的尾部),所以这种编译方法独具优势。如果编译的方式过于机械化,那么程序要在递增rt和循环尾部进行两次条件转移。现在的CPU都具有分支预测的功能(请参加本书33.1节)。在性能方面,本例这类程序的效率更高。

最后一则指令是REP RET(opcode为F3 C3)。它就是MSVC里的FATRET。这个指令是由RET衍生出来的向优化指令。AMD建议:如果RET指令的前一条指令是条件转移指令,那么在函数最后的返回指令最好使用REP RET指令。(请参见AMD13b,p15)[6]

Optimizing MSVC 2010

指令清单19.31 MSVC 2010

a$ = 8
f       PROC
; RCX = input value
        xor     eax, eax
        mov     edx, 1
        lea     r8d, QWORD PTR [rax+64]
; R8D=64
        npad    5
$LL4@f:
        test    rdx, rcx
; there are no such bit in input value?
; skip the next INC instruction then.
        je      SHORT $LN3@f
        inc     eax     ; rt++
$LN3@f:
        rol     rdx, 1  ; RDX=RDX<<1
        dec     r8      ; R8--
        jne     SHORT $LL4@f
        fatret  0
f       ENDP

本例中,编译器用ROL指令替代了SHL指令。ROL的确切作用是“rotate left”,SHL的含义则是“shift left”。不过在本例中,它们的效果相同。

有关旋转指令的详细介绍,请参见附录A.6.3。

R8的值将从64逐渐递减为0,它的变化过程和变量i完全相反。

在程序的执行过程中,寄存器的关系如下图所示。

RDX

R8

0x0000000000000001

64

0x0000000000000002

63

0x0000000000000004

62

0x0000000000000008

61

……

……

0x4000000000000000

2

0x8000000000000000

1

程序最后使用了FATRET指令,我们在上一个例子里已经介绍过它了。

Optimizing MSVC 2012

指令清单19.32 MSVC 2012

a$ = 8
f       PROC
; RCX = input value
        xor      eax, eax
        mov      edx, 1
        lea      r8d, QWORD PTR [rax+32]
; EDX = 1, R8D = 32
        npad     5
$LL4@f:
; pass 1 ------------------------------------
        test     rdx, rcx
        je       SHORT $LN3@f
        inc      eax     ; rt++
$LN3@f:
        rol      rdx, 1  ; RDX=RDX<<1
; -------------------------------------------
; pass 2 ------------------------------------
        test     rdx, rcx
        je       SHORT $LN11@f
        inc      eax     ; rt++
$LN11@f:
        rol      rdx, 1  ; RDX=RDX<<1
; -------------------------------------------
        dec      r8      ; R8--
        jne      SHORT $LL4@f
        fatret  0
f       ENDP

MSVC 2012优化编译而生成的代码与MSVC 2010大体相同。但是MSVC 2012把迭代次数为64次的循环,拆解为两个迭代32次的循环。坦白讲,笔者也不清楚个中缘由。或许是优化的结果,或许循环体更长一些比较好。总之,我特地把这个例子记录下来,希望读者注意:编译器可能生成各种匪夷所思的代码,但是这些代码的功能仍然会忠实于源程序。

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

指令清单19.33 Optimizing Xcode 4.6.3 (LLVM) (ARM mode)

           MOV             R1, R0
           MOV             R0, #0
           MOV             R2, #1
           MOV             R3, R0
loc_2E54
           TST             R1, R2,LSL R3 ; 根据R1 & (R2<<R3)设置标记
           ADD             R3, R3, #1    ; R3++
           ADDNE           R0, R0, #1    ; if ZF flag is cleared by TST, then R0++
           CMP             R3, #32
           BNE             loc_2E54
           BX              LR

ARM模式的TST指令相当于x86指令集的TEST指令。

ARM模式的指令里没有单独的位移操作指令(参见本书41.2.1节)。但是在数据处理指令——即MOV、TST、CMP、ADD、SUB、RSB指令中,可以使用参数调节符(如LSL、LSR、ASR、ROR、RRX)实现位移运算。

通过“参数调节符(modificators)”进行位移运算的指令,必须明确位移的方法和位移的位数。

此处的“TST R1, R2, LSL R3”,可理解为R1^(R2<<R3)。

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

Thumb-2模式的代码与ARM模式的代码基本相同。只不过在Thumb-2模式下,不可能直接在TST指令里直接使用参数调节符LSL,所以它使用LSL.W和TST指令替代了ARM模式下的单条TST指令。

           MOV             R1, R0
           MOVS            R0, #0
           MOV.W           R9, #1
           MOVS            R3, #0
loc_2F7A
           LSL.W           R2, R9, R3
           TST             R2, R1
           ADD.W           R3, R3, #1
           IT NE
           ADDNE           R0, #1
           CMP             R3, #32
           BNE             loc_2F7A
           BX              LR
19.5.5 ARM64 + Optimizing GCC 4.9

本节使用的源程序,是19.5.2节中所示程序的64位修改版。

指令清单19.34 Optimizing GCC (Linaro) 4.8

f:
        mov     w2, 0       ; rt=0
        mov     x5, 1
        mov     w1, w2
.L2:
        lsl     x4, x5, x1  ; w4 = w5<<w1 = 1<<i
        add     w3, w2, 1   ; new_rt=rt+1
        tst     x4, x0      ; (1<<i) & a
        add     w1, w1, 1   ; i++
; result of TST was non-zero?
; then w2=w3 or rt=new_rt.
; otherwise: w2=w2 or rt=rt (idle operation)
        csel    w2, w3, w2, ne
        cmp     w1, 64      ; i<64?
        bne     .L2         ;yes
        mov     w0, w2      ; return rt
        ret

这个程序与GCC生成的x64程序(请参见指令清单19.30)十分相似。

其中,CSEL指令的全称是“Conditional SELect”。它依据TST指令设置的标志位,相应地从候选的两个操作符中选取一个数据并复制给W2。本例中,它传递的值是rt。

19.5.6 ARM64 + Non-optimizing GCC 4.9

本节再次使用19.5.2节中所示程序的64位修改版。

由于编译时关闭了优化功能,所以编译器生成的代码十分庞大。

指令清单19.35 Non-optimizing GCC (Linaro) 4.8

f:
        sub     sp, sp, #32
        str     x0, [sp,8]      ; store "a" value to Register Save Area
        str     wzr, [sp,24]    ; rt=0
        str     wzr, [sp,28]    ; i=0
        b       .L2
.L4:
        ldr     w0, [sp,28]
        mov     x1, 1
        lsl     x0, x1, x0      ; X0 = X1<<X0 = 1<<i
        mov     x1, x0
; X1 = 1<<i
        ldr     x0, [sp,8]
; X0 = a
        and     x0, x1, x0
; X0 = X1&X0 = (1<<i) & a
; X0 contain zero? then jump to .L3, skipping "rt" increment
        cmp     x0, xzr
        beq     .L3
; rt++
        ldr     w0, [sp,24]
        add     w0, w0, 1
        str     w0, [sp,24]
.L3:
; i++
        ldr     w0, [sp,28]
        add     w0, w0, 1
        str     w0, [sp,28]
.L2:
; i<=63? then jump to .L4
        ldr     w0, [sp,28]
        cmp     w0, 63
        ble     .L4
; return rt
        ldr     w0, [sp,24]
        add     sp, sp, 32
        ret
19.5.7 MIPS

Non-optimizing GCC

指令清单19.36 Non-optimizing GCC 4.4.5 (IDA)

f:
; IDA is not aware of variable names, we gave them manually:
rt              = -0x10
i               = -0xC
var_4           = -4
a               = 0

                addiu   $sp, -0x18
                sw      $fp, 0x18+var_4($sp)
                move    $fp, $sp
                sw      $a0, 0x18+a($fp)
; initialize rt and i variables to zero:
                sw      $zero, 0x18+rt($fp)
                sw      $zero, 0x18+i($fp)
; jump to loop check instructions:
                b       loc_68
                or      $at, $zero ; branch delay slot, NOP
loc_20:
                li      $v1, 1
                lw      $v0, 0x18+i($fp)
                or      $at, $zero ; load delay slot, NOP
                sllv    $v0, $v1, $v0
; $v0 = 1<<i
                move    $v1, $v0
                lw      $v0, 0x18+a($fp)
                or      $at, $zero ; load delay slot, NOP
                and     $v0, $v1, $v0
; $v0 = a&(1<<i)
; is a&(1<<i) equals to zero? jump to loc_58 then:
                beqz    $v0, loc_58
                or      $at, $zero
; no jump occurred, that means a&(1<<i)!=0, so increment "rt" then:
                lw      $v0, 0x18+rt($fp)
                or      $at, $zero ; load delay slot, NOP
                addiu   $v0, 1
                sw      $v0, 0x18+rt($fp)

loc_58:
; increment i:
                lw       $v0, 0x18+i($fp)
                or       $at, $zero ; load delay slot, NOP
                addiu    $v0, 1
                sw       $v0, 0x18+i($fp)

loc_68:
; load i and compare it with 0x20 (32).
; jump to loc_20 if it is less then 0x20 (32):
                lw       $v0, 0x18+i($fp)
                or       $at, $zero ; load delay slot, NOP
                slti     $v0, 0x20 # ' '
                bnez     $v0, loc_20
                or       $at, $zero ; branch delay slot, NOP
; function epilogue. return rt:
                lw       $v0, 0x18+rt($fp)
                move     $sp, $fp ; load delay slot
                lw       $fp, 0x18+var_4($sp)
                addiu    $sp, 0x18 ; load delay slot
                jr       $ra
                or       $at, $zero ; branch delay slot, NOP

这段程序十分直观:程序首先把所有的局部变量存储在局部栈里。在使用变量的时候,再把它们从栈里取出来。SLLV指令的全称是“Shift Word Left Logical Variable”。SLL指令只能把某个操作位移事先确定的比特位(这个位数是封装在opcode里的固定值),而SLLV指令从寄存器里读取位移的具体位数(编译时不能确定的变量)。

Optimizing GCC

启用优化功能之后,编译器生成的程序就会简略许多。不过它却使用了2条位移指令,比非优化编译而生成的程序还要多用一条位移指令。这是为什么?固然第一条SLLV指令可以替换为“跳转到第二个 SLLV的无条件转移指令”,但是如此一来函数中就需要多用一个转移指令。而编译器的优化功能会刻意减少这种转移指令的使用次数,更多详情请参见本书33.1节。

指令清单19.37 Optimizing GCC 4.4.5 (IDA)

f:
; $a0=a
; rt variable will reside in $v0:
                move    $v0, $zero
; i variable will reside in $v1:
                move    $v1, $zero
                li      $t0, 1
                li      $a3, 32
                sllv    $a1, $t0, $v1
; $a1 = $t0<<$v1 = 1<<i
loc_14:
                and     $a1, $a0
; $a1 = a&(1<<i)
; increment i:
                addiu   $v1, 1
; jump to loc\_28 if a&(1<<i)==0 and increment rt:
                beqz    $a1, loc_28
                addiu   $a2, $v0, 1
; if BEQZ was not triggered, save updated rt into $v0:
                move    $v0, $a2
loc_28:
; if i!=32, jump to loc_14 and also prepare next shifted value:
                bne     $v1, $a3, loc_14
                sllv    $a1, $t0, $v1
; return
                jr      $ra
                or      $at, $zero ; branch delay slot, NOP

19.6 本章小结

与C/C++语言中的位移操作符<<和>>相对应,x86指令集中有操作无符号数的SHR/SHL指令和操作有符号数的SAR/SHL指令。

在ARM平台上,对无符号数进行位移运算的指令是LSR/LSL,对有符号数进行位移运算的指令是ASR/LSL。而且,ARM指令还可以通过“参数调节符”的形式使用“后缀型”位移运算指令。此类对其他数进行运算的指令,又叫做“数据处理指令”。

19.6.1 检测特定位(编译阶段)

对某数值的二进制1000000位(即16进制的0x40)进行检测的指令大体如下。

指令清单19.38 C/C++

if (input&0x40)
    ...

指令清单19.39 x86

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

指令清单19.40 x86

TEST REG, 40h
JZ is_cleared
; bit is set

指令清单19.41 ARM (ARM mode)

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

某些情况下,编译器会使用AND指令而不使用TEST指令。无论编译器选取了哪个指令,都不会影响程序将要检测的标志位。

19.6.2 检测特定位(runtime阶段)

在C/C++代码编译而得的程序中,检测特定位的指令(右移n位,然后舍弃最低位)大体如下。

指令清单19.42 C/C++

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

相应的x86代码如下所示。

指令清单19.43 x86

; REG=input_value
; CL=n
SHR REG, CL
AND REG, 1

此外还可以把1左移n次,逐次鉴定各位是否为零。

指令清单19.44 C/C++

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

上述源程序对应的x86指令如下所示。

指令清单19.45 x86

; CL=n
MOV REG, 1
SHL REG, CL
AND input_value, REG
19.6.3 设置特定位(编译阶段)

指令清单19.46 C/C++

value=value|0x40;

指令清单19.47 x86

OR REG, 40h

指令清单19.48 ARM (ARM mode) and ARM64

ORR R0, R0, #0x40
19.6.4 设置特定位(runtime阶段)

指令清单19.49 C/C++

value=value|(1<<n);

对应的x86指令大体如下所示。

指令清单19.50 x86

; CL=n
MOV REG, 1
SHL REG, CL
OR input_value, REG
19.6.5 清除特定位(编译阶段)

如需清除特定位,只需使用AND指令操作相应数值即可。

指令清单19.51 C/C++

value=value&(~0x40);

指令清单19.52 x86

AND REG, 0FFFFFFBFh

指令清单19.53 x64

AND REG, 0FFFFFFFFFFFFFFBFh

上述指令仅仅把被操作数的某个位置零,其他位保持不变。

ARM平台的ARM模式指令集有BIC指令。它相当于NOT和AND指令对。

指令清单19.54 ARM (ARM mode)

BIC R0, R0, #0x40
19.6.6 清除特定位(runtime阶段)

指令清单19.55 C/C++

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

指令清单19.56 x86

; CL=n
MOV REG, 1
SHL REG, CL
NOT REG
AND input_value, REG

19.7 练习题

19.7.1 题目1

请描述下述代码的功能。

指令清单19.57 Optimizing MSVC 2010

_a$ = 8
_f      PROC
        mov     ecx, DWORD PTR _a$[esp-4]
        mov     eax, ecx
        mov     edx, ecx
        shl     edx, 16         ; 00000010H
        and     eax, 65280      ; 0000ff00H
        or      eax, edx
        mov     edx, ecx
        and     edx, 16711680   ; 00ff0000H
        shr     ecx, 16         ; 00000010H
        or      edx, ecx
        shl     eax, 8
        shr     edx, 8
        or      eax, edx
        ret     0
_f      ENDP

指令清单19.58 Optimizing Keil 6/2013 (ARM mode)

f PROC
        MOV     r1,#0xff0000
        AND     r1,r1,r0,LSL #8
        MOV     r2,#0xff00
        ORR     r1,r1,r0,LSR #24
        AND     r2,r2,r0,LSR #8
        ORR     r1,r1,r2
        ORR     r0,r1,r0,LSL #24
        BX      lr
        ENDP

指令清单19.59 Optimizing Keil 6/2013 (Thumb mode)

f  PROC
        MOVS    r3,#0xff
        LSLS    r2,r0,#8
        LSLS    r3,r3,#16
        ANDS    r2,r2,r3
        LSRS    r1,r0,#24
        ORRS    r1,r1,r2
        LSRS    r2,r0,#8
        ASRS    r3,r3,#8
        ANDS    r2,r2,r3
        ORRS    r1,r1,r2
        LSLS    r0,r0,#24
        ORRS    r0,r0,r1
        BX      lr
        ENDP

指令清单19.60 Optimizing GCC 4.9 (ARM64)

f:
        rev     w0, w0
        ret

指令清单19.61 Optimizing GCC 4.4.5 (MIPS) (IDA)

f:
           srl     $v0, $a0, 24
           sll     $v1, $a0, 24
           sll     $a1, $a0, 8
           or      $v1, $v0
           lui     $v0, 0xFF
           and     $v0, $a1, $v0
           srl     $a0, 8
           or      $v0, $v1, $v0
           andi    $a0, 0xFF00
           jr      $ra
           or      $v0, $a0
19.7.2 题目2

请描述下述程序的功能。

指令清单19.62 Optimizing MSVC 2010

_a$ = 8                                    ; size = 4
_f      PROC
        push   esi
        mov    esi, DWORD PTR _a$[esp]
        xor    ecx, ecx
        push   edi
        lea    edx, DWORD PTR [ecx+1]
        xor    eax, eax
        npad   3 ; align next label
$LL3@f:
        mov    edi, esi
        shr    edi, cl
        add    ecx, 4
        and    edi, 15
        imul   edi, edx
        lea    edx, DWORD PTR [edx+edx*4]
        add    eax, edi
        add    edx, edx
        cmp    ecx, 28
        jle    SHORT $LL3@f
        pop    edi
        pop    esi
        ret    0
_f      ENDP

指令清单19.63 Optimizing Keil 6/2013 (ARM mode)

f PROC
        MOV    r3,r0
        MOV    r1,#0
        MOV    r2,#1
        MOV    r0,r1
|L0.16|
        LSR    r12,r3,r1
        AND    r12,r12,#0xf
        MLA    r0,r12,r2,r0
        ADD    r1,r1,#4
        ADD    r2,r2,r2,LSL #2
        CMP    r1,#0x1c
        LSL    r2,r2,#1
        BLE    |L0.16|
        BX     lr
        ENDP

指令清单19.64 Optimizing Keil 6/2013 (Thumb mode)

f  PROC
        PUSH     {r4,lr}
        MOVS     r3,r0
        MOVS     r1,#0
        MOVS     r2,#1
        MOVS     r0,r1
|L0.10|
        MOVS     r4,r3
        LSRS     r4,r4,r1
        LSLS     r4,r4,#28
        LSRS     r4,r4,#28
        MULS     r4,r2,r4
        ADDS     r0,r4,r0
        MOVS     r4,#0xa
        MULS     r2,r4,r2
        ADDS     r1,r1,#4
        CMP      r1,#0x1c
        BLE      |L0.10|
        POP      {r4,pc}
        ENDP

指令清单19.65 Non-optimizing GCC 4.9 (ARM64)

f:
        sub     sp, sp, #32
        str     w0, [sp,12]
        str     wzr, [sp,28]
        mov     w0, 1
        str     w0, [sp,24]
        str     wzr, [sp,20]
        b       .L2
.L3:
        ldr     w0, [sp,28]
        ldr     w1, [sp,12]
        lsr     w0, w1, w0
        and     w1, w0, 15
        ldr     w0, [sp,24]
        mul     w0, w1, w0
        ldr     w1, [sp,20]
        add     w0, w1, w0
        str     w0, [sp,20]
        ldr     w0, [sp,28]
        add     w0, w0, 4
        str     w0, [sp,28]
        ldr     w1, [sp,24]
        mov     w0, w1
        lsl     w0, w0, 2
        add     w0, w0, w1
        lsl     w0, w0, 1
        str     w0, [sp,24]
.L2:
        ldr     w0, [sp,28]
        cmp     w0, 28
        ble     .L3
        ldr     w0, [sp,20]
        add     sp, sp, 32
        ret

指令清单19.66 Optimizing GCC 4.4.5 (MIPS) (IDA)

f:
                rl      $v0, $a0, 8
                srl     $a3, $a0, 20
                andi    $a3, 0xF
                andi    $v0, 0xF
                srl     $a1, $a0, 12
                srl     $a2, $a0, 16
                andi    $a1, 0xF
                andi    $a2, 0xF
                sll     $t2, $v0, 4
                sll     $v1, $a3, 2
                sll     $t0, $v0, 2
                srl     $t1, $a0, 4
                sll     $t5, $a3, 7
                addu    $t0, $t2
                subu    $t5, $v1
                andi    $t1, 0xF
                srl     $v1, $a0, 28
                sll     $t4, $a1, 7
                sll     $t2, $a2, 2
                sll     $t3, $a1, 2
                sll     $t7, $a2, 7
                srl     $v0, $a0, 24
                addu    $a3, $t5, $a3
                subu    $t3, $t4, $t3
                subu    $t7, $t2
                andi    $v0, 0xF
                sll     $t5, $t1, 3
                sll     $t6, $v1, 8
                sll     $t2, $t0, 2
                sll     $t4, $t1, 1
                sll     $t1, $v1, 3
                addu    $a2, $t7, $a2
                subu    $t1, $t6, $t1
                addu    $t2, $t0, $t2
                addu    $t4, $t5
                addu    $a1, $t3, $a1
                sll     $t5, $a3, 2
                sll     $t3, $v0, 8
                sll     $t0, $v0, 3
                addu    $a3, $t5
                subu    $t0, $t3, $t0
                addu    $t4, $t2, $t4
                sll     $t3, $a2, 2
                sll     $t2, $t1, 6
                sll     $a1, 3
                addu    $a1, $t4, $a1
                subu    $t1, $t2, $t1
                addu    $a2, $t3
                sll     $t2, $t0, 6
                sll     $t3, $a3, 2
                andi    $a0, 0xF
                addu    $v1, $t1, $v1
                addu    $a0, $a1
                addu    $a3, $t3
                subu    $t0, $t2, $t0
                sll     $a2, 4
                addu    $a2, $a0, $a2
                addu    $v0, $t0, $v0
                sll     $a1, $v1, 2
                sll     $a3, 5
                addu    $a3, $a2, $a3
                addu    $v1, $a1
                sll     $v0, 6
                addu    $v0, $a3, $v0
                sll     $v1, 7
                jr      $ra
                addu    $v0, $v1, $v0
19.7.3 题目3

请查阅MSDN资料,找到MessageBox()函数使用了哪些标志位。

指令清单19.67 Optimizing MSVC 2010

_main   PROC
        push    278595          ; 00044043H
        push    OFFSET $SG79792 ; 'caption'
        push    OFFSET $SG79793 ; 'hello, world!'
        push    0
        call    DWORD PTR __imp__MessageBoxA@16
        xor     eax, eax
        ret     0
_main   ENDP
19.7.4 题目4

请描述下述代码的功能。

指令清单19.68 Optimizing MSVC 2010

_m$ = 8         ; size = 4
_n$ = 12        ; size = 4
_f      PROC
        mov     ecx, DWORD PTR _n$[esp-4]
        xor     eax, eax
        xor     edx, edx
        test    ecx, ecx
        je      SHORT $LN2@f
        push    esi
        mov     esi, DWORD PTR _m$[esp]
$LL3@f:
        test    cl, 1
        je      SHORT $LN1@f
        add     eax, esi
        adc     edx, 0
$LN1@f:
        add     esi, esi
        shr     ecx, 1
        jne     SHORT $LL3@f
        pop     esi
$LN1@f:
        ret     0
_f      ENDP

指令清单19.69 Optimizing Keil 6/2013 (ARM mode)

f PROC
        PUSH     {r4,lr}
        MOV      r3,r0
        MOV      r0,#0
        MOV      r2,r0
        MOV      r12,r0
        B        |L0.48|
|L0.24|
        TST      r1,#1
        BEQ      |L0.40|
        ADDS     r0,r0,r3
        ADC      r2,r2,r12
|L0.40|
        LSL      r3,r3,#1
        LSR      r1,r1,#1
|L0.48|
        CMP      r1,#0
        MOVEQ    r1,r2
        BNE      |L0.24|
        POP      {r4,pc}
        ENDP

指令清单19.70 Optimizing Keil 6/2013 (Thumb mode)

f  PROC
        PUSH    {r4,r5,lr}
        MOVS    r3,r0
        MOVS    r0,#0
        MOVS    r2,r0
        MOVS    r4,r0
        B       |L0.24|
|L0.12|
        LSLS    r5,r1,#31
        BEQ     |L0.20|
        ADDS    r0,r0,r3
        ADCS    r2,r2,r4
|L0.20|
        LSLS    r3,r3,#1
        LSRS    r1,r1,#1
|L0.24|
        CMP     r1,#0
        BNE     |L0.12|
        MOVS    r1,r2
        POP     {r4,r5,pc}
        ENDP

指令清单19.71 Optimizing GCC 4.9 (ARM64)

f:
        mov     w2, w0
        mov     x0, 0
        cbz     w1, .L2
.L3:
        and     w3, w1, 1
        lsr     w1, w1, 1
        cmp     w3, wzr
        add     x3, x0, x2, uxtw
        lsl     w2, w2, 1
        csel    x0, x3, x0, ne
        cbnz    w1, .L3
.L2:
        ret

指令清单19.72 Optimizing GCC 4.4.5 (MIPS) (IDA)

mult:
               beqz   $a1, loc_40
               move   $a3, $zero
               move   $a2, $zero
               addu   $t0, $a3, $a0
loc_10:                               # CODE XREF: mult+38
               sltu   $t1, $t0, $a3
               move   $v1, $t0
               andi   $t0, $a1, 1
               addu   $t1, $a2
               beqz   $t0, loc_30
               srl    $a1, 1
               move   $a3, $v1
               move   $a2, $t1
loc_30:                               # CODE XREF: mult+20
               beqz   $a1, loc_44
               sll    $a0, 1
               b      loc_10
               addu   $t0, $a3, $a0
loc_40:                               # CODE XREF: mult
               move   $a2, $zero
loc_44:                               # CODE XREF: mult:loc_30
               move   $v0, $a2
               jr     $ra
               move   $v1, $a3

[1] http://ohse.de/uwe/articles/gcc-attributes.html#func-regparm。

[2] 参见:http://kernelnewbies.org/Linux_2_6_20#head-042c62f290834eb1fe0a1942bbf5bb9a4accbc8f以及源代码文件。

[3] 确切地说,使用的编译器是LLVM build 2410.2.00 bundled with Apple Xcode 4.6.3。

[4] Conditional MOVe if Not Equal。

[5] Conditional MOVe if Not Zero。

[6] 更多介绍请参见http://repzret.org/p/repzret/。