读《Professional Assembly Language》之插入排序

图1 Program Virtual Memory Area

今年是离开校园的第五年，这五年来我一直在从事应用软件的设计、开发工作，大部分时间是在与高级编程语言、设计模式、业务逻辑打交道。它们大多流于表面，久而久之，与技术底层疏远了，诸如计算机组成原理、汇编语言、编译原理、数据结构以及算法慢慢得生疏，时至今日，我已经弄不懂IA-32里有几类寄存器、间接寻址、词法分析是怎么一回事情了。五年是一个契机，趁着下一个五年开始之际，我计划用三个月至半年时想间，重新学习这些知识，以期达到巩固基础，厚积薄发的目的。

学习过程肯定会有问题，找不出问题的学生不是好学生。因此，我把遇到的问题和解决的方法记录下来，便形成了读书笔记。本篇博文便是我在阅读《Professional Assembly Language》一书时，所作的其中一篇读书笔记。《Professional Assembly Language》，中文译作《汇编语言程序设计》，是我学习汇编语言时选择的工具书，该书对于我这种已经有了高级语言的使用经验，又热衷Linux的人来说非常合适。

《Professional Assembly Language》看完了第一、二部分，回顾这段时间的学习，收获似乎并没有想象中那么大，觉得掌握的还是皮毛。期间，搭配阅读《Computer System: A Programmer’s Perspective》、《The C Programming Language》，对计算机的理解和对程序的掌控能力只是有提升，而谈不上跃升。我想，最主要的原因还是缺少动手去写代码。

插入排序常常是书本当中用来引导读者进入算法领域的hello, world，这次我尝试用汇编代码来实现它。在这之前，首先把C语言实现版本张贴如下，以便参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void insertion_sort(int array[], int length)
{
    int j;
    for (j = 1; j < length; j++)
    {
        int i = j - 1;
        int key = *(array + j);
        while (i >= 0 && *(array + i) > key)
        {
            *(array + i + 1) = *(array + i);
            i--;
        }
        *(array + i + 1) = key;
    }
 
}

采用汇编代码实现如下：

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

.section .text
.type insertion_sort, @function
.globl insertion_sort
insertion_sort:
	pushl %ebp
	movl %esp, %ebp
 
	# apply 12-byte to store local variables
	subl $0xc, %esp
 
	# save ECX register
	pushl %ecx
 
	# initinate ECX register with the second argument which is the array length
	movl 8(%ebp), %ecx
	decl %ecx
loop1:
	pushl %eax
	pushl %ebx
	pushl %edx
 
	# local variable: j
	movl 8(%ebp), %eax
	movl %eax, -4(%ebp)
	subl %ecx, -4(%ebp)
 
	# local variable: key
	movl 12(%ebp), %eax
	movl -4(%ebp), %ebx
	movl (%eax, %ebx, 4), %edx
	movl %edx, -8(%ebp)
 
	popl %edx
	popl %ebx
	popl %eax
 
	# local variable: i
	pushl %ecx
	movl -4(%ebp), %ecx
	decl %ecx
loop2:
	pushl %eax
	pushl %ebx
 
	# local variable: temp
	movl 12(%ebp), %eax
	movl (%eax, %ecx, 4), %ebx
	movl %ebx, -12(%ebp)
 
	movl -8(%ebp), %eax
	movl -12(%ebp), %ebx
	cmpl %ebx, %eax
	jg loop2_end
 
	movl 12(%ebp), %eax
	incl %ecx
	movl %ebx, (%eax, %ecx, 4)
	decl %ecx
 
	popl %ebx
	popl %eax
 
	loop loop2
	jmp loop1_end
loop2_end:
	movl 12(%ebp), %ebx
	incl %ecx
	movl %eax, (%ebx, %ecx, 4)
	decl %ecx
 
	popl %ebx
	popl %eax
loop1_end:	
	popl %ecx
	loop loop1
end:	
	# restore ECX register
	popl %ecx
 
	movl %ebp, %esp
	pop %ebp
	ret

在写这段代码的过程中，围绕数组元素，我遇到了这么两个问题：

  1. 如何传递数组参数给函数
  2. 如何将数组元素赋值给局部变量

汇编语言里没有数组类型。从内存的角度来看，所谓的数组，不过是一串连续的存储空间以相同的步长截取后，每段空间所代表的信息组成的这么一个集合。

如果一个函数需要调用者传递数组给它，那么将数组中每一个值都逐一加入到参数列表里，这样固然可行，但实际上谁都不会这么做，通常只把数组的开始地址传给函数。

array:
	.int 2, 42, 4, 35, 364, 23, 75, 0, 123, 435, 3, 8, 90, 83, 421

array就是第一个数组元素，把array地址传递给函数，除了上面代码所示，还可以：

leal array, %eax
pushl %eax

如果要访问数组元素，则需要先取得array的内存地址，然后加上偏移量，得出后续的其他元素地址，最后根据地址获得对应的元素值，即：baseAddress(offsetAddress, index, unitSize)，以此写代码如下：

(12(%ebp), -4(%ecx), 4)

这样的写法是不行的，因为offsetAddress和index不能是内存地址，需要放到通用寄存器当中。

上面的实现固然实现了插入排序，但是我更想对比一下，对C代码由GCC生成的汇编代码，采用以下命令可得到：

gcc -m32 -O1 -s insertion_sort.s insertion_sort.c

最后得到的代码如下：

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

	.section	__TEXT,__text,regular,pure_instructions
	.globl	_insertion_sort
	.align	4, 0x90
_insertion_sort:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ebx
	pushl	%edi
	pushl	%esi
	movl	12(%ebp), %eax
	cmpl	$2, %eax
	jl	LBB1_7
	movl	8(%ebp), %ecx
	decl	%eax
	xorl	%edx, %edx
	.align	4, 0x90
LBB1_2:
	movl	4(%ecx,%edx,4), %esi
	movl	%edx, %edi
	jmp	LBB1_4
	.align	4, 0x90
LBB1_3:
	movl	(%ecx,%edi,4), %ebx
	movl	%ebx, 4(%ecx,%edi,4)
	decl	%edi
LBB1_4:
	testl	%edi, %edi
	js	LBB1_6
	cmpl	%esi, (%ecx,%edi,4)
	jg	LBB1_3
LBB1_6:
	incl	%edx
	movl	%esi, 4(%ecx,%edi,4)
	cmpl	%edx, %eax
	jne	LBB1_2
LBB1_7:
	popl	%esi
	popl	%edi
	popl	%ebx
	popl	%ebp
	ret

比较GCC和自己的汇编代码，最明显的区别在于，GCC代码压根没有使用栈来保存局部变量，代码简洁，自己的火候还差很远。

22 9 月, 2011 in Software | tags: ,

Leave a comment

Your comment