8-分支程序设计

一、分支程序设计

（1）分支程序设计示例

1. 两种分支结构

  • if结构（图a）；if-else结构（图b）
  • 需要注意一下用汇编写if-else结构的时候，if分支结束后要用无条件转跳过else分支，后面详细说明

2. 简单分支示例

  • 有简单分支程序
1
2
3
4
5
6
7
//大写字母转小写
int cf315(int ch)
{
	if(ch>='A' && ch<='Z')
		ch+=0x20;
	return ch;
}
  • 现在把它反汇编（关闭优化）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//子过程cf315
//入口参数：堆栈传递ch
//出口参数：eax
_asm
{
CF315:
	push ebp
	mov ebp,esp
	
	cmp DWORD PTR[ebp+8],65
	jl SHORT lab1				//<A跳转
	cmp DWORD PTR[ebp+8],90	
	jg SHORT lab1				//>Z跳转
	
	mov eax,DWORD PTR[ebp+8]	//是大写字母，转小写
	add eax,32
	mov DWORD PTR[ebp+8],eax

lab1:							//用eax返回结果
	mov eax,DWORD PTR[ebp+8]
	pop ebp
	ret

}
  • 现在再打开优化反汇编一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
_asm
{
CF315:
	push ebp
	mov ebp,esp
	
	mov eax,DWORD PTR[ebp+8]	//ch取到eax中
	lea ecx,DWORD PTR[eax-65]	//ecx=eax-65
	cmp ecx,25
	ja lab1						//看作无符号数，如果ecx>25，意味着ch不是大写字母
	add ecx,32					

lab1:							//用eax返回结果
	pop ebp
	ret
}
  • 观察到的优化手段：
    1. 巧妙地把两个分支减少到一个
    2. 充分利用寄存器，减少从内存取值

3. 双分支示例

  • 有双分支程序
1
2
3
4
5
6
7
8
9
10
//把十进制数m转十六进制字符的ASCII码
int cf316(int m)
{
	m = m & 0x0f;	//确保m的值在0~15
	if(m<10)
		m+=0x30;	//如：1->'1'
	else
		m+=0x37;	//如：10->'A'
	return m;
}
  • 现在把它反汇编（关闭优化）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
_asm
{
CF316:
	push ebp
	mov ebp,esp
	
	mov eax,DWORD PTR[ebp+8]	//m = m & 0x15;
	and eax,15
	mov DWORD PTR[ebp+8],eax
	
	cmp DWORD PTR[ebp+8],10		
	jge SHORT lab1				//m>=10转lab1
	
	mov ecx,DWORD PTR[ebp+8]	//m<10,m+=0x30
	add ecx,48
	mov DWORD PTR[ebp+8],ecx
	jmp lab2					//绕过else分支，注意！！！
lab1:
	mov ecx,DWORD PTR[ebp+8]	//m>=10,m+=0x37
	add ecx,55
	mov DWORD PTR[ebp+8],ecx
lab2:							//统一的返回位置
	mov eax,DWORD PTR[ebp+8]
	pop ebp
	ret
}
  • 现在打开优化再反汇编一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
_asm
{
	push ebp
	mov ebp,esp
	
	mov eax,DWORD PTR[ebp+8]
	and eax,15
	
	cmp eax,10
	jge SHORT lab1
	
	add eax,48
	pop ebp
	ret
	
lab1:
	add eax,55
	pop ebp
	ret
}

观察：

  1. 如果不开优化，参数或局部变量都存在堆栈，要修改必须要进行：取到Reg，修改，写回堆栈三步
  2. 汇编程序是自上往下顺序执行的，（不像C语言中if-else可以选择分支执行；while、for可以循环执行一段代码），它只能用jcc指令修改下一条程序代码的位置，就好像不能用if、else、while、for，只能用goto的C程序。因此像if-else结构，必须在if分支最后jmp跳过else，否则会顺序把else也执行一次。
  3. 优化手段：
    1. 用寄存器减少从内存取值
    2. 避免了jmp指令，两个分支不再合并而是各自返回。减少跳转次数
  • 优化源程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int cf317(int m)
{
	m=m&0x0f;
	m+=0x30;
	if(m>'9')
		m+=7;
	return m;
}

//开优化反汇编
_asm
{
	push ebp
	mov ebp,esp
	
	mov eax,DWORD PTR[ebp+8]
	and eax,15

	add eax,48
	cmp eax,57
	jle lab1
	add eax,7
lab1:
	pop ebp
	ret
}
  • 小结：
    1. 靠编译器自动优化，再好也是依赖于源C程序的，要想真正提高程序效率，还得从源程序上改进
    2. 优化策略：
      1. 减少内存的存取数据，多用寄存器
      2. 减少跳转数量
      3. 避免时钟数多的指令（右移代替除法）
      4. 减少循环次数
      5. 用内联函数减少call和ret

（2）无条件和条件转移指令

1. 基本概念

  • 段内转移（近转移）：转移时只重置指令指针寄存器EIP，不重置代码段寄存器CS，
  • 段间转移（远转移）：转移时重置指令指针寄存器EIP和代码段寄存器CS
  • 转移类型判断
转移 属于段内还是段间
条件转移 段内
循环指令 段内
无条件转移 段内或段间
过程调用和返回 段内或段间
软中断指令 段间
中断返回指令 段间
  • 直接转移：转移指令中直接给出转移目的地址
  • 间接转移：转移指令中给出包含转移目的地址的寄存器或存储单元

2. 无条件转移指令

  1. 无条件段内直接转移
    1. 无条件段内直接转移指令的机器码格式
      image.png
    2. 操作码OP：转移指令的机器码
    3. 地址差rel：转移目标地址偏移（标号LABEL所指定指令的地址偏移）与紧随JMP指令的下一条指令的地址偏移之间的差值。
      1. rel会被汇编器自动计算，并自动选取为8/16/32位来表示。如果只用了8位，就称为短（short）转移。
      2. 如果程序不能自动计算地址偏差了多少，用32位来表示rel
      3. 如果编程时可以判断地址偏差不超过8位范围，可以用SHORT指令强制汇编器用8位表示rel
      4. 由于rel是有符号数，转移方向可以向前也可以向后
    4. 执行无条件段内转移指令时，把指令中的地址差rel加到指令指针寄存器EIP上，使EIP之内容为转移目标地址偏移，从而实现转移。
名称 jmp（无条件段内直接转移指令）
格式 jmp label
动作 下一条指令转移到 label 处执行
  1. 无条件段内间接转移
名称 jmp（无条件段内间接转移指令）
格式 jmp OPDR
动作 指令使控制无条件地转移到由操作数OPRD的内容给定的目标地址处
合法值 OPDR：32位寄存器、32位存储单元
注意 OPRD内容直接被装入指令指针寄存器EIP，从而实现转移

3. 条件转移指令

  1. 之前的文章已经写过，见jcc相关部分：
  2. 条件转移指令通过判断状态标志确定转移是否发生，但是本身不影响标志状态
  3. 也是通过label标记确定转移位置，在机器码层面的实现和无条件段内直接转移一样

（3）多分支的实现

  • 多分枝类似C中的switch-case
  • 源程序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//示例函数cf319
int  cf319(int x, int operation)
{
	int  y;
	//多路分支
	switch (operation) {
	case 1:
		y = 3 * x;
		break;
	case 2:
		y = 5 * x + 6;
		break;
	case 4:
	case 5:
		y = x * x;
		break;
	case 8:
		y = x * x + 4 * x;
		break;
	default:			//0 3 6 7 9 10 ...
		y = x;
	}
	if (y > 1000)
		y = 1000;
	return  y;
}
  • 进行反汇编
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//返汇编（速度最大化）
	push  ebp
    mov   ebp, esp
                                   ; switch ( operation ) {
    mov   eax, DWORD PTR [ebp+12]  ;取得参数operation（case值）
    dec   eax                      ;从0开始计算，所以先减去1
    cmp   eax, 7                   ;从0开始计算，最多就是7
    ja    SHORT LN2cf319           ;超过，则转default
    ;
    jmp   DWORD  PTR  LN12cf319[ eax*4 ]     ;实施多路分支
    ;
LN6cf319:                            ; case 1:
                                     ; y = 3*x;
    mov   eax, DWORD PTR [ebp+8]
    lea   eax, DWORD PTR [eax+eax*2]
    jmp   SHORT  LN7cf319            ; break;
    ;
LN5cf319:                            ; case 2:
                                     ; y = 5*x+6;
    mov   eax, DWORD PTR [ebp+8]
    lea   eax, DWORD PTR [eax+eax*4+6]
    jmp   SHORT  LN7cf319            ; break;
    
LN4cf319:                            ; case 4:
                                     ; y = x*x ;
    mov   eax, DWORD PTR [ebp+8]
    imul  eax, eax
    jmp   SHORT LN7cf319             ;  break;
    ;
LN3cf319:                            ; case 8:
                                     ; y = x*x+4*x;
    mov   ecx, DWORD PTR [ebp+8]
    lea   eax, DWORD PTR [ecx+4]
    imul  eax, ecx
    jmp   SHORT LN7cf319             ; break;

LN2cf319:                            ; default:
                                     ; y = x ;
    mov   eax, DWORD PTR [ebp+8]
                                     ; }
LN7cf319:                            ; if ( y > 1000 )
    cmp   eax, 1000
    jle   SHORT  LN1cf319
                                     ; y = 1000;
    mov   eax, 1000
LN1cf319:                            ; return  y;
    pop   ebp                        ;撤销堆栈框架
    ret
    ;

LN12cf319:                           ;多向分支目标地址表
    DD    LN6cf319                   ; case 1	(DD代表双字，每4个字节存放一个入口地址)
    DD    LN5cf319                   ; case 2
    DD    LN2cf319                   ; default
    DD    LN4cf319                   ; case 4
    DD    LN4cf319                   ; case 5
    DD    LN2cf319                   ; default
    DD    LN2cf319                   ; default
    DD    LN3cf319                   ; case 8

分析

  1. 最后LN12cf319部分，开启了多向分支目标地址表，DD代表地址表中每一项占4个字节，因此LN12cf319+4*0就是LN6cf319；LN12cf319+4*1就是LN5cf319，依次类推
  2. jmp DWORD PTR LN12cf319[ eax*4 ]这句，跳转到地址LN12cf319+eax*4执行，这是实现switch-case的关键。注意eax要改到0起始
  3. 空位置default必须留出，否则转换过来的时候会出错
  4. 可以看到地址表是按地址排列的，适用于多分枝且没有大空洞的情况。如果各个case间有大间距，会导致地址表中default项过多，最好预处理一下，或者改用if-else逻辑