2006年04月12日

http://kevinwan.cnblogs.com

2006年04月10日

求两个string的最长公共子序列

如:
"abcdef", "aabacfe" => "abce"
"swew", "wews" => "wew"

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <time.h>

enum { MAX_LEN = 100 };

void LCS_Aux(const char* s1, int l1, const char* s2, int l2, char* output, int& lo)
{
    if (l1 <= 0 || l2 <= 0 || l1 > MAX_LEN || l2 > MAX_LEN)
    {
        lo = 0;
    }
    else if (s1[l1-1] == s2[l2-1])
    {
        LCS_Aux(s1, l1-1, s2, l2-1, output, lo);
        output[lo] = s1[l1-1];
        lo++;
    }
    else
    {
        int len1, len2;
        char tmp[MAX_LEN] = {0};
        LCS_Aux(s1, l1-1, s2, l2, output, len1);
        LCS_Aux(s1, l1, s2, l2-1, tmp, len2);
        if (len1 < len2)
        {
            strncpy(output, tmp, len2);
            lo = len2;
        }
        else
        {
            lo = len1;
        }
    }
}

char* LCS_Recursive(const char* s1, const char* s2)
{
    if (s1 == 0 || s2 == 0)
        return 0;

    int len1 = strlen(s1);
    int len2 = strlen(s2);
    char* output = new char[len1];
    memset(output, 0, len1);
    int olen = 0;
    LCS_Aux(s1, len1, s2, len2, output, olen);
    return output;
}

int max(int a, int b)
{
    return a > b ? a : b;
}

char* LCS_DP(const char* s1, const char* s2)
{
    if (s1 == 0 || s2 == 0)
        return 0;

    int l1 = strlen(s1);
    int l2 = strlen(s2);
    if (l1 > MAX_LEN || l2 > MAX_LEN)
        return 0;

    int m[MAX_LEN][MAX_LEN] = {0};
    char d[MAX_LEN][MAX_LEN] = {0};

    for (int i = 0; i < l1; ++i)
    {
        for (int j = 0; j < l2; ++j)
        {
            if (s1[i] == s2[j])
            {
                if (i == 0 || j == 0)
                {
                    d[i][j] = ‘\\’;
                    m[i][j] = 1;
                }
                else
                {
                    d[i][j] = ‘\\’;
                    m[i][j] = m[i-1][j-1] + 1;
                }
            }
            else
            {
                if (i == 0)
                {
                    d[i][j] = ‘-’;
                    m[i][j] = m[i][j-1];
                }
                else if (j == 0)
                {
                    d[i][j] = ‘|’;
                    m[i][j] = m[i-1][j];
                }
                else
                {
                    if (m[i][j-1] > m[i-1][j])
                    {
                        d[i][j] = ‘-’;
                        m[i][j] = m[i][j-1];
                    }
                    else
                    {
                        d[i][j] = ‘|’;
                        m[i][j] = m[i-1][j];
                    }
                }
            }
        }
    }

    // Print the matrix
    for (int i = 0; i < l1; ++i)
    {
        for (int j = 0; j < l2; ++j)
        {
            printf("%d ", m[i][j]);
        }
        printf("\n");
    }

    // Print the path
    for (int i = 0; i < l1; ++i)
    {
        for (int j = 0; j < l2; ++j)
        {
            printf("%c ", d[i][j]);
        }
        printf("\n");
    }

    int len = m[l1-1][l2-1];
    char* result = new char[len+1];
    memset(result, 0, l1);
    char* p = result + len;
    –l1, –l2;
    *p = 0;
    while (l1 >= 0 && l2 >= 0)
    {
        if (d[l1][l2] == ‘\\’)
        {
            *–p = s1[l1];
            –l1, –l2;
        }
        else if (d[l1][l2] == ‘-’)
        {
            –l2;
        }
        else if (d[l1][l2] == ‘|’)
        {
            –l1;
        }
    }
    return result;
}

int main(int argc, char* argv[])
{
    char* input[2][16] =
    {
        { "abcdef", "aabacfe", "abce" },
        { "swew", "wews", "wew" },
    };

    for (int i = 0; i < 2; ++i)
    {
        time_t start = time(0);
        char* result = LCS_Recursive(input[i][0], input[i][1]);
        printf("%s\n", result);
        assert(strcmp(result, input[i][2]) == 0);
        delete[] result;
        printf("%u\n\n", time(0)-start);

        start = time(0);
        result = LCS_DP(input[i][0], input[i][1]);
        printf("%s\n", result);
        assert(strcmp(result, input[i][2]) == 0);
        delete[] result;
        printf("%u\n\n", time(0)-start);
    }
    return 0;
}

2006年03月28日

有两个string,str1 = "i am a boy", str2 = "iamaboy"
写出下面函数的实现
char* AddBackSpaces(const char* str, const set<string>& words)
{
    …
}
传入的str是"iamaboy",words是["i", "am", "a", "boy"],期望的输出是"i am a boy".

谁想试试?

写一个程序删除给定的一个string中的重复的words
void RemoveDupWords(char* str)
{
}
结果保存在str中。

谁想试试?:)

2006年03月23日

一.最基本题型(说明:此类题型比较简单)

1. 1到100有多少个9

2. 连续整数之和为1000的共有几组

3. U2合唱团在17分钟内得赶到演唱会场,途中必需跨过一座桥,四个人从桥的
同一端出发,你得帮助他们到达另一端,天色很暗,而他们只有一只手电筒。
一次同时最多可以有两人一起过桥,而过桥的时候必须持有手电筒,所以就
得有人把手电筒带来带去,来回桥两端。手电筒是不能用丢的方式来传递的。
四个人的步行速度各不同,若两人同行则以较慢者的速度为准。 Bono需花1
分钟过桥 Edge需花2分钟过桥 Adam需花5分钟过桥 Larry需花10分钟过桥
他们要如何在17分钟内过桥呢?(这是Micrsoft征聘人员时问的问题,你必须
在五分钟内答出来才可能获得聘用)。

4.   说有一份遗产3500元一个女人的老公留下来的,如果这个女人生的是儿子那么
她将分到她儿子的一半,如果是女儿,他将分得她女儿的2倍,如果这个女人生
了一对,一男一女,问各得多少遗产?

5. 老师d的物理测验答案在教室里丢失了,今天那个教室上了5堂课,老师d上了3
堂,有可能是a、b、c三个同学盗窃
已知:  1、a上了两堂课
        2、b上了三堂课
        3、c上了四堂课
        4、a、b、c每个人都上了老师d的两堂课
        5、五堂课中,三个人到堂的组合各不相同
        6、老师d的课中有一堂,三个人中到了两个,事后证明不是那两个人偷得
问?是谁偷得

6. a b c d e
           * f
__________________
=g g g g g g
问,a b c d e f g各是什么数字(不重复)

7. a进行一次C和D之间往返旅行,希望在整个旅行中能够达到60km/h的平均速度,
但是当他从C到达D的时候发现平均速度只有30km/h,问a应当怎么做才能够使
这次往返旅行的平局速度到达60km/h

8. 烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有若干条材质相同的
绳子,问如何用烧绳的方法来计时一个小时十五分钟呢?

9. 你有一桶果冻,其中有黄色、绿色、红色三种,闭上眼睛抓取同种颜色的两个。
抓取多少个就可以确定你肯定有两个同一颜色的果冻?

10. 如果你有无穷多的水,一个3公升的提捅,一个5公升的提捅,两只提捅形状上
下都不均匀,问你如何才能准确称出4公升的水?

11. 一个岔路口分别通向诚实国和说谎国。来了两个人,已知一个是诚实国的,另
一个是说谎国的。诚实国永远说实话,说谎国永远说谎话。现在你要去说谎国,
但不知道应该走哪条路,需要问这两个人。请问应该怎么问?

12. 12个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就
找到那个球。13个呢?

13.在9个点上画10条直线,要求每条直线上至少有三个点?

14.在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有
几次?都分别是什么时间?你怎样算出来的?

二.没有答案型(说明:这些题显然不是考你智力。而考的是你的反应能力。 这种题大多数没有答案,但是要看你的反应喽!)

1.为什么下水道的盖子是圆的?

2.中国有多少辆汽车?

3.将汽车钥匙插入车门,向哪个方向旋转就可以打开车锁?

4.如果你要去掉中国的34个省(含自治区、直辖市和港澳特区及台湾省)中的
任何一个,你会去掉哪一个,为什么?

5.多少个加油站才能满足中国的所有汽车?

6.想象你站在镜子前,请问,为什么镜子中的影象可以颠倒左右,却不能颠倒上下?

7.为什么在任何旅馆里,你打开热水,热水都会瞬间倾泻而出?

8.你怎样将Excel的用法解释给你的奶奶听?

9.你怎样重新改进和设计一个ATM银行自动取款机?

10.如果你不得不重新学习一种新的计算机语言,你打算怎样着手来开始?

11.如果你的生涯规划中打算在5年内受到奖励,那获取该项奖励的动机是什么?
观众是谁?

12.如果微软告诉你,我们打算投资五百万美元来启动你的投资计划,你将开始什
么样商业计划?为什么?
13.如果你能够将全世界的电脑厂商集合在一个办公室里,然后告诉他们将被强迫
做一件事,那件事将是什么?

三.难题(说明:这类题有一定难度,如果得不到答案,也不能说明什么。 如果你想到了解题思路,那么答案马上就能出来。如果想不到思路, 那么……就别想解出来了。)

1.你让工人为你工作7天,回报是一根金条,这个金条平分成相连的7段,
你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断,
你如何给你的工人付费?

2.有一辆火车以每小时15公里的速度离开北京直奔广州,同时另一辆火车
每小时20公里的速度从广州开往北京。如果有一只鸟,以30公里每小时的速
度和两辆火车同时启动,从北京出发,碰到另一辆车后就向相反的方向返回
去飞,就这样依次在两辆火车之间来回地飞,直到两辆火车相遇。请问,这
只鸟共飞行了多长的距离?

3.你有四个装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被
污染的药丸的重量+1。只称量一次,如何判断哪个罐子的药被污染了?

4.门外三个开关分别对应室内三盏灯,线路良好,在门外控制开关时候不能
看到室内灯的情况,现在只允许进门一次,确定开关和灯的对应关系?

5.人民币为什么只有1、2、5、10的面值?

6.你有两个罐子以及50个红色弹球和50个蓝色弹球,随机选出一个罐子,
随机选出一个弹球放入罐子,怎么给出红色弹球最大的选中机会?在你的计
划里,得到红球的几率是多少?

四.超难题(说明:如果你是第一次看到这种题,并且以前从来没有见过类
似的题型,并且能够在半个小时之内做出答案。只能说明你的智力超常……)

第一题  五个海盗抢到了100颗宝石,每一颗都一样大小和价值连城。
他们决定这么分:
抽签决定自己的号码(1、2、3、4、5)
首先,由1号提出分配方案,然后大家表决,当且仅当超过半数的人同意时,
按照他的方案进行分配,否则将被扔进大海喂鲨鱼如果1号死后,再由2号提
出分配方案,然后剩下的4人进行表决,当且仅当超过半数的人同意时,按照
他的方案进行分配,否则将被扔入大海喂鲨鱼
依此类推
条件:每个海盗都是很聪明的人,都能很理智地做出判断,从而做出选择。
问题:第一个海盗提出怎样的分配方案才能使自己的收益最大化?

第二题 . 一道关于飞机加油的问题,已知:
每个飞机只有一个油箱, 飞机之间可以相互加油(注意是相互,没有加油机) 一箱油可供一架飞机绕地球飞半圈,

问题: 为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?
(所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间
没有飞机场)

五.主观题(说明:在以后的工作过程中,我们可定会犯这样那样的错误。 既然错误已经酿成,损失在所难免,我们只能想办法把损失减少到最小。 如果能巧妙地回答出这些问题,再发生错误的情况下。能让客户有最少的抱
怨,公司有最少的损失。)

1.某手机厂家由于设计失误,有可能造成电池寿命比原来设计的寿命短一半 (不是冲放电时间),解决方案就是免费更换电池或给50元购买该厂家新手机 的折换券。请给所有已购买的用户写信告诉解决方案。

2.一高层领导在参观某博物馆时,向博物馆馆员小王要了一块明代的城砖作 为纪念,按国家规定,任何人不得将博物馆收藏品变为私有。博物馆馆长需要如何写信给这位领导,将城砖取回。

3.营业员小姐由于工作失误,将2万元的笔记本电脑以1.2万元错卖给李先生,
王小姐的经理怎么写信给李先生试图将钱要回来?

六.算法题(说明:这些题就不是什么花样了,考的是你的基础知识怎么样。 再聪明而没有实学的人都将会被这些题所淘汰。)

1.链表和数组的区别在哪里?

2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法?

3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法?

4.编写能直接实现strstr()函数功能的代码。

5.编写反转字符串的程序,要求优化速度、优化空间。

6.在链表里如何发现循环链接?

7.给出洗牌的一个算法,并将洗好的牌存储在一个整形数组里。

8.写一个函数,检查字符是否是整数,如果是,返回其整数值。
(或者:怎样只用4行代码编写出一个从字符串到长整形的函数?)

9.给出一个函数来输出一个字符串的所有排列。

10.请编写实现malloc()内存分配函数功能一样的代码。

11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串
B的前几个字节重叠。

12.怎样编写一个程序,把一个有序整数数组放到二叉树中?

13.怎样从顶部开始逐层打印二叉树结点数据?请编程。

14.怎样把一个链表掉个顺序(也就是反序,注意链表的边界条件并考虑空链表)?

七.几个微软技术支持中心电话面试的题目

1.如果只想让程序有一个实例运行,不能运行两个。象winnamp一样, 只能开一个窗口,怎么作?

2.如何截取键盘的响应,让所有的’a'变成’b'?

3.apartment在com中有什么用?为什么要引入这个?

4.存储过程是什么,有什么用,什么优点?

5.template有什么特点,什么时候用?

6.好像最好要了解win32sdk底层的知识。比如消息响应的过程等等。

7.对.net的理解,对web service的理解,对三层结构的理解

8.两层的负载平衡与三层结构的负载平衡有什么差别,优点

9.windows DNA结构的特点,优点。

2006年03月22日

1, control the schedule
If don’t know how to control the schedule, the manager will fail. Typically, for a small company, they have no enough resource to wait. If the project failed, the first person to fire is the manager.

2, keep engineers life easy
Try to make them happy. Don’t blame them, even if they made mistakes. Try to encourage them. Encouraging makes people happy, full of passion, and eager to do more contributions. 1:1 meeting with each engineer once per 2 weeks.

3, guarantee quality of the product
The quality should be guaranteed step by step. Code review every 1 or 2 weeks. Refactoring once per week. Unit test for all components (try test driven development).

2006年01月10日

文件浏览器:
Total Commander: http://www.ghisler.com/
Krusader: http://krusader.sourceforge.net/

2006年01月09日

C++ performs name lookup and then overload resolution before accessibility checking.

2005年12月07日

CLD Clear the direction flag (set to forward direction)

将方向标志置0,使si和di增量,串处理从低地址向高地址处理

8088 汇编速查手册          



一、数据传输指令
───────────────────────────────────────
  它们在存贮器和寄存器、寄存器和输入输出端口之间传送数据.
  1. 通用数据传送指令.
    MOV  传送字或字节.
    MOVSX 先符号扩展,再传送.
    MOVZX 先零扩展,再传送.
    PUSH  把字压入堆栈.
    POP  把字弹出堆栈.
    PUSHA 把AX,CX,DX,BX,SP,BP,SI,DI依次压入堆栈.
    POPA  把DI,SI,BP,SP,BX,DX,CX,AX依次弹出堆栈.
    PUSHAD 把EAX,ECX,EDX,EBX,ESP,EBP,ESI,EDI依次压入堆栈.
    POPAD 把EDI,ESI,EBP,ESP,EBX,EDX,ECX,EAX依次弹出堆栈.
    BSWAP 交换32位寄存器里字节的顺序
    XCHG  交换字或字节.( 至少有一个操作数为寄存器,段寄存器不可作为操作数)
    CMPXCHG 比较并交换操作数.( 第二个操作数必须为累加器AL/AX/EAX )
    XADD  先交换再累加.( 结果在第一个操作数里 )
    XLAT  字节查表转换.
        ── BX 指向一张 256 字节的表的起点, AL 为表的索引值 (0-255,即
        0-FFH); 返回 AL 为查表结果. ( [BX+AL]->AL )
  2. 输入输出端口传送指令.
    IN   I/O端口输入. ( 语法: IN 累加器, {端口号│DX} )
    OUT  I/O端口输出. ( 语法: OUT {端口号│DX},累加器 )
     输入输出端口由立即方式指定时, 其范围是 0-255; 由寄存器 DX 指定时,
     其范围是 0-65535.
  3. 目的地址传送指令.
    LEA  装入有效地址.
     例: LEA DX,string ;把偏移地址存到DX.
    LDS  传送目标指针,把指针内容装入DS.
     例: LDS SI,string ;把段地址:偏移地址存到DS:SI.
    LES  传送目标指针,把指针内容装入ES.
     例: LES DI,string ;把段地址:偏移地址存到ES:DI.
    LFS  传送目标指针,把指针内容装入FS.
     例: LFS DI,string ;把段地址:偏移地址存到FS:DI.
    LGS  传送目标指针,把指针内容装入GS.
     例: LGS DI,string ;把段地址:偏移地址存到GS:DI.
    LSS  传送目标指针,把指针内容装入SS.
     例: LSS DI,string ;把段地址:偏移地址存到SS:DI.
  4. 标志传送指令.
    LAHF  标志寄存器传送,把标志装入AH.
    SAHF  标志寄存器传送,把AH内容装入标志寄存器.
    PUSHF 标志入栈.
    POPF  标志出栈.
    PUSHD 32位标志入栈.
    POPD  32位标志出栈.


二、算术运算指令
───────────────────────────────────────
      ADD  加法.
    ADC  带进位加法.
    INC  加 1.
    AAA  加法的ASCII码调整.
    DAA  加法的十进制调整.
    SUB  减法.
    SBB  带借位减法.
    DEC  减 1.
    NEC  求反(以 0 减之).
    CMP  比较.(两操作数作减法,仅修改标志位,不回送结果).
    AAS  减法的ASCII码调整.
    DAS  减法的十进制调整.
    MUL  无符号乘法.
    IMUL  整数乘法.
     以上两条,结果回送AH和AL(字节运算),或DX和AX(字运算),
    AAM  乘法的ASCII码调整.
    DIV  无符号除法.
    IDIV  整数除法.
     以上两条,结果回送:
       商回送AL,余数回送AH, (字节运算);
     或 商回送AX,余数回送DX, (字运算).
    AAD  除法的ASCII码调整.
    CBW  字节转换为字. (把AL中字节的符号扩展到AH中去)
    CWD  字转换为双字. (把AX中的字的符号扩展到DX中去)
    CWDE  字转换为双字. (把AX中的字符号扩展到EAX中去)
    CDQ  双字扩展.  (把EAX中的字的符号扩展到EDX中去)


三、逻辑运算指令
───────────────────────────────────────
      AND  与运算.
    OR   或运算.
    XOR  异或运算.
    NOT  取反.
    TEST  测试.(两操作数作与运算,仅修改标志位,不回送结果).
    SHL  逻辑左移.
    SAL  算术左移.(=SHL)
    SHR  逻辑右移.
    SAR  算术右移.(=SHR)
    ROL  循环左移.
    ROR  循环右移.
    RCL  通过进位的循环左移.
    RCR  通过进位的循环右移.
     以上八种移位指令,其移位次数可达255次.
       移位一次时, 可直接用操作码. 如 SHL AX,1.
       移位>1次时, 则由寄存器CL给出移位次数.
        如 MOV CL,04
          SHL AX,CL


四、串指令
───────────────────────────────────────
       DS:SI 源串段寄存器 :源串变址.
      ES:DI 目标串段寄存器:目标串变址.
      CX   重复次数计数器.
      AL/AX 扫描值.
      D标志 0表示重复操作中SI和DI应自动增量; 1表示应自动减量.
      Z标志 用来控制扫描或比较操作的结束.
    MOVS  串传送.
      ( MOVSB 传送字符.  MOVSW 传送字.  MOVSD 传送双字. )
    CMPS  串比较.
      ( CMPSB 比较字符.  CMPSW 比较字. )
    SCAS  串扫描.
      把AL或AX的内容与目标串作比较,比较结果反映在标志位.
    LODS  装入串.
      把源串中的元素(字或字节)逐一装入AL或AX中.
      ( LODSB 传送字符.  LODSW 传送字.  LODSD 传送双字. )
    STOS  保存串.
      是LODS的逆过程.
    REP      当CX/ECX<>0时重复.
    REPE/REPZ   当ZF=1或比较结果相等,且CX/ECX<>0时重复.
    REPNE/REPNZ  当ZF=0或比较结果不相等,且CX/ECX<>0时重复.
    REPC     当CF=1且CX/ECX<>0时重复.
    REPNC     当CF=0且CX/ECX<>0时重复.


五、程序转移指令
───────────────────────────────────────
   1>无条件转移指令 (长转移)
    JMP  无条件转移指令
    CALL  过程调用
    RET/RETF过程返回.
  2>条件转移指令 (短转移,-128到+127的距离内)
    ( 当且仅当(SF XOR OF)=1时,OP1<OP2 )
    JA/JNBE 不小于或不等于时转移.
    JAE/JNB 大于或等于转移.
    JB/JNAE 小于转移.
    JBE/JNA 小于或等于转移.
     以上四条,测试无符号整数运算的结果(标志C和Z).
    JG/JNLE 大于转移.
    JGE/JNL 大于或等于转移.
    JL/JNGE 小于转移.
    JLE/JNG 小于或等于转移.
     以上四条,测试带符号整数运算的结果(标志S,O和Z).
    JE/JZ 等于转移.
    JNE/JNZ 不等于时转移.
    JC   有进位时转移.
    JNC  无进位时转移.
    JNO  不溢出时转移.
    JNP/JPO 奇偶性为奇数时转移.
    JNS  符号位为 "0" 时转移.
    JO   溢出转移.
    JP/JPE 奇偶性为偶数时转移.
    JS   符号位为 "1" 时转移.
  3>循环控制指令(短转移)
    LOOP      CX不为零时循环.
    LOOPE/LOOPZ  CX不为零且标志Z=1时循环.
    LOOPNE/LOOPNZ CX不为零且标志Z=0时循环.
    JCXZ      CX为零时转移.
    JECXZ     ECX为零时转移.
  4>中断指令
    INT  中断指令
    INTO  溢出中断
    IRET  中断返回
  5>处理器控制指令
    HLT  处理器暂停, 直到出现中断或复位信号才继续.
    WAIT  当芯片引线TEST为高电平时使CPU进入等待状态.
    ESC  转换到外处理器.
    LOCK  封锁总线.
    NOP  空操作.
    STC  置进位标志位.
    CLC  清进位标志位.
    CMC  进位标志取反.
    STD  置方向标志位.
    CLD  清方向标志位.
    STI  置中断允许位.
    CLI  清中断允许位.


六、伪指令
───────────────────────────────────────
      DW   定义字(2字节).
    PROC  定义过程.
    ENDP  过程结束.
    SEGMENT 定义段.
    ASSUME 建立段寄存器寻址.
    ENDS  段结束.
    END  程序结束.



Linux 汇编语言开发指南



内容:
一、简介
二、Linux 汇编语法格式
三、Hello World!
四、Linux 汇编工具
五、系统调用
六、命令行参数
七、GCC 内联汇编
八、小结
九、参考资料
关于作者


相关内容:
介绍
介绍


在 Linux 专区还有:
教程
工具与产品
代码与组件
项目
文章


肖文鹏(xiaowp@263.net)
北京理工大学计算机系硕士研究生
2003 年 7 月


汇编语言的优点是速度快,可以直接对硬件进行操作,这对诸如图形处理等关键应用是非常重要的。Linux 是一个用 C 语言开发的操作系统,这使得很多程序员开始忘记在 Linux 中还可以直接使用汇编这一底层语言来优化程序的性能。本文为那些在Linux 平台上编写汇编代码的程序员提供指南,介绍 Linux 汇编语言的语法格式和开发工具,并辅以具体的例子讲述如何开发实用的Linux 汇编程序。

一、简介

作为最基本的编程语言之一,汇编语言虽然应用的范围不算很广,但重要性却勿庸置疑,因为它能够完成许多其它语言所无法完成的功能。就拿 Linux 内核来讲,虽然绝大部分代码是用 C 语言编写的,但仍然不可避免地在某些关键地方使用了汇编代码,其中主要是在 Linux 的启动部分。由于这部分代码与硬件的关系非常密切,即使是 C 语言也会有些力不从心,而汇编语言则能够很好扬长避短,最大限度地发挥硬件的性能。


多数情况下 Linux 程序员不需要使用汇编语言,因为即便是硬件驱动这样的底层程序在 Linux 操作系统中也可以用完全用 C
语言来实现,再加上 GCC
这一优秀的编译器目前已经能够对最终生成的代码进行很好的优化,的确有足够的理由让我们可以暂时将汇编语言抛在一边了。但实现情况是 Linux
程序员有时还是需要使用汇编,或者不得不使用汇编,理由很简单:精简、高效和 libc 无关性。假设要移植 Linux 到某一特定的嵌入式硬件环境下,首先必然面临如何减少系统大小、提高执行效率等问题,此时或许只有汇编语言能帮上忙了。

汇编语言直接同计算机的底层软件甚至硬件进行交互,它具有如下一些优点:

  • 能够直接访问与硬件相关的存储器或 I/O 端口;
  • 能够不受编译器的限制,对生成的二进制代码进行完全的控制;
  • 能够对关键代码进行更准确的控制,避免因线程共同访问或者硬件设备共享引起的死锁;
  • 能够根据特定的应用对代码做最佳的优化,提高运行速度;
  • 能够最大限度地发挥硬件的功能。

同时还应该认识到,汇编语言是一种层次非常低的语言,它仅仅高于直接手工编写二进制的机器指令码,因此不可避免地存在一些缺点:

  • 编写的代码非常难懂,不好维护;
  • 很容易产生 bug,难于调试;
  • 只能针对特定的体系结构和处理器进行优化;
  • 开发效率很低,时间长且单调。

Linux 下用汇编语言编写的代码具有两种不同的形式。第一种是完全的汇编代码,指的是整个程序全部用汇编语言编写。尽管是完全的汇编代码,Linux 平台下的汇编工具也吸收了 C 语言的长处,使得程序员可以使用 #include、#ifdef 等预处理指令,并能够通过宏定义来简化代码。第二种是内嵌的汇编代码,指的是可以嵌入到C语言程序中的汇编代码片段。虽然 ANSI 的 C 语言标准中没有关于内嵌汇编代码的相应规定,但各种实际使用的 C 编译器都做了这方面的扩充,这其中当然就包括 Linux 平台下的 GCC。

二、Linux 汇编语法格式

绝大多数 Linux 程序员以前只接触过DOS/Windows 下的汇编语言,这些汇编代码都是 Intel 风格的。但在 Unix 和 Linux 系统中,更多采用的还是 AT&T 格式,两者在语法格式上有着很大的不同:

  1. AT&T 汇编格式中,寄存器名要加上 ‘%’ 作为前缀;而在 Intel 汇编格式中,寄存器名不需要加前缀。例如:

    AT&T 格式 Intel 格式
    pushl %eax push eax
  2. AT&T 汇编格式中,用 ‘$’ 前缀表示一个立即操作数;而在 Intel 汇编格式中,立即数的表示不用带任何前缀。例如:

    AT&T 格式 Intel 格式
    pushl $1 push 1
  3. AT&T 和 Intel 格式中的源操作数和目标操作数的位置正好相反。在 Intel 汇编格式中,目标操作数在源操作数的左边;而在 AT&T 汇编格式中,目标操作数在源操作数的右边。例如:

    AT&T 格式 Intel 格式
    addl $1, %eax add eax, 1
  4. AT&T 汇编格式中,操作数的字长由操作符的最后一个字母决定,后缀’b'、’w'、’l'分别表示操作数为字节(byte,8 比特)、字(word,16 比特)和长字(long,32比特);而在 Intel 汇编格式中,操作数的字长是用 "byte ptr" 和 "word ptr" 等前缀来表示的。例如:

    AT&T 格式 Intel 格式
    movb val, %al mov al, byte ptr val
  5. AT&T 汇编格式中,绝对转移和调用指令(jump/call)的操作数前要加上’*'作为前缀,而在 Intel 格式中则不需要。
  6. 远程转移指令和远程子调用指令的操作码,在 AT&T 汇编格式中为 "ljump" 和 "lcall",而在 Intel 汇编格式中则为 "jmp far" 和 "call far",即:

    AT&T 格式 Intel 格式
    ljump $section, $offset jmp far section:offset
    lcall $section, $offset call far section:offset

    与之相应的远程返回指令则为:

    AT&T 格式 Intel 格式
    lret $stack_adjust ret far stack_adjust
  7. AT&T 汇编格式中,内存操作数的寻址方式是

     section:disp(base, index, scale) 

    而在 Intel 汇编格式中,内存操作数的寻址方式为:

     section:[base + index*scale + disp] 

    由于 Linux 工作在保护模式下,用的是 32 位线性地址,所以在计算地址时不用考虑段基址和偏移量,而是采用如下的地址计算方法:

     disp + base + index * scale 

    下面是一些内存操作数的例子:

    AT&T 格式 Intel 格式
    movl -4(%ebp), %eax mov eax, [ebp - 4]
    movl array(, %eax, 4), %eax mov eax, [eax*4 + array]
    movw array(%ebx, %eax, 4), %cx mov cx, [ebx + 4*eax + array]
    movb $4, %fs:(%eax) mov fs:eax, 4

三、Hello World!

真不知道打破这个传统会带来什么样的后果,但既然所有程序设计语言的第一个例子都是在屏幕上打印一个字符串 "Hello World!",那我们也以这种方式来开始介绍 Linux 下的汇编语言程序设计。


Linux 操作系统中,你有很多办法可以实现在屏幕上显示一个字符串,但最简洁的方式是使用 Linux
内核提供的系统调用。使用这种方法最大的好处是可以直接和操作系统的内核进行通讯,不需要链接诸如 libc 这样的函数库,也不需要使用 ELF
解释器,因而代码尺寸小且执行速度快。

Linux 是一个运行在保护模式下的 32 位操作系统,采用 flat memory
模式,目前最常用到的是 ELF 格式的二进制代码。一个 ELF 格式的可执行程序通常划分为如下几个部分:.text、.data 和
.bss,其中 .text 是只读的代码区,.data 是可读可写的数据区,而 .bss 则是可读可写且没有初始化的数据区。代码区和数据区在
ELF 中统称为 section,根据实际需要你可以使用其它标准的 section,也可以添加自定义 section,但一个 ELF
可执行程序至少应该有一个 .text 部分。下面给出我们的第一个汇编程序,用的是 AT&T 汇编语言格式:

例1. AT&T 格式

 #hello.s .data # 数据段声明 msg : .string "Hello, world!\\n" # 要输出的字符串 len = . - msg # 字串长度 .text # 代码段声明 .global _start # 指定入口函数 _start: # 在屏幕上显示一个字符串 movl $len, %edx # 参数三:字符串长度 movl $msg, %ecx # 参数二:要显示的字符串 movl $1, %ebx # 参数一:文件描述符(stdout) movl $4, %eax # 系统调用号(sys_write) int $0x80 # 调用内核功能 # 退出程序 movl $0,%ebx # 参数一:退出代码 movl $1,%eax # 系统调用号(sys_exit) int $0x80 # 调用内核功能 

初次接触到 AT&T 格式的汇编代码时,很多程序员都认为太晦涩难懂了,没有关系,在 Linux 平台上你同样可以使用 Intel 格式来编写汇编程序:

例2. Intel 格式

 ; hello.asm section .data ; 数据段声明 msg db "Hello, world!", 0xA ; 要输出的字符串 len equ $ - msg ; 字串长度 section .text ; 代码段声明 global _start ; 指定入口函数 _start: ; 在屏幕上显示一个字符串 mov edx, len ; 参数三:字符串长度 mov ecx, msg ; 参数二:要显示的字符串 mov ebx, 1 ; 参数一:文件描述符(stdout) mov eax, 4 ; 系统调用号(sys_write) int 0x80 ; 调用内核功能 ; 退出程序 mov ebx, 0 ; 参数一:退出代码 mov eax, 1 ; 系统调用号(sys_exit) int 0x80 ; 调用内核功能 


面两个汇编程序采用的语法虽然完全不同,但功能却都是调用 Linux 内核提供的 sys_write 来显示一个字符串,然后再调用
sys_exit 退出程序。在 Linux 内核源文件 include/asm-i386/unistd.h 中,可以找到所有系统调用的定义。

四、Linux 汇编工具

Linux 平台下的汇编工具虽然种类很多,但同 DOS/Windows 一样,最基本的仍然是汇编器、连接器和调试器。

1.汇编器

汇编器(assembler)的作用是将用汇编语言编写的源程序转换成二进制形式的目标代码。Linux 平台的标准汇编器是 GAS,它是 GCC 所依赖的后台汇编工具,通常包含在 binutils 软件包中。GAS 使用标准的 AT&T 汇编语法,可以用来汇编AT&T 格式编写的程序:

 [xiaowp@gary code]$ as -o hello.o hello.s 

Linux
平台上另一个经常用到的汇编器是 NASM,它提供了很好的宏指令功能,并能够支持相当多的目标代码格式,包括
bin、a.out、coff、elf、rdf 等。NASM 采用的是人工编写的语法分析器,因而执行速度要比 GAS
快很多,更重要的是它使用的是 Intel 汇编语法,可以用来编译用 Intel 语法格式编写的汇编程序:

 [xiaowp@gary code]$ nasm -f elf hello.asm 

2.链接器


汇编器产生的目标代码是不能直接在计算机上运行的,它必须经过链接器的处理才能生成可执行代码。链接器通常用来将多个目标代码连接成一个可执行代码,这样
可以先将整个程序分成几个模块来单独开发,然后才将它们组合(链接)成一个应用程序。 Linux 使用 ld 作为标准的链接程序,它同样也包含在
binutils 软件包中。汇编程序在成功通过 GAS 或 NASM 的编译并生成目标代码后,就可以使用 ld 将其链接成可执行程序了:

 [xiaowp@gary code]$ ld -s -o hello hello.o 

3.调试器

有人说程序不是编出来而是调出来的,足见调试在软件开发中的重要作用,在用汇编语言编写程序时尤其如此。Linux 下调试汇编代码既可以用 GDB、DDD 这类通用的调试器,也可以使用专门用来调试汇编代码的 ALD(Assembly Language Debugger)。

从调试的角度来看,使用 GAS 的好处是可以在生成的目标代码中包含符号表(symbol table),这样就可以使用 GDB 和 DDD 来进行源码级的调试了。要在生成的可执行程序中包含符号表,可以采用下面的方式进行编译和链接:

 [xiaowp@gary code]$ as --gstabs -o hello.o hello.s [xiaowp@gary code]$ ld -o hello hello.o 

执行 as 命令时带上参数 –gstabs 可以告诉汇编器在生成的目标代码中加上符号表,同时需要注意的是,在用 ld 命令进行链接时不要加上 -s 参数,否则目标代码中的符号表在链接时将被删去。

在 GDB 和 DDD 中调试汇编代码和调试 C 语言代码是一样的,你可以通过设置断点来中断程序的运行,查看变量和寄存器的当前值,并可以对代码进行单步跟踪。图1 是在 DDD 中调试汇编代码时的情景:


图1 用 DDD 中调试汇编程序

汇编程序员通常面对的都是一些比较苛刻的软硬件环境,短小精悍的ALD可能更能符合实际的需要,因此下面主要介绍一下如何用ALD来调试汇编程序。首先在命令行方式下执行ald命令来启动调试器,该命令的参数是将要被调试的可执行程序:

 [xiaowp@gary doc]$ ald hello Assembly Language Debugger 0.1.3 Copyright (C) 2000-2002 Patrick Alken hello: ELF Intel 80386 (32 bit), LSB, Executable, Version 1 (current) Loading debugging symbols...(15 symbols loaded) ald> 

当 ALD 的提示符出现之后,用 disassemble 命令对代码段进行反汇编:

 ald> disassemble -s .text Disassembling section .text (0x08048074 - 0x08048096) 08048074 BA0F000000 mov edx, 0xf 08048079 B998900408 mov ecx, 0x8049098 0804807E BB01000000 mov ebx, 0x1 08048083 B804000000 mov eax, 0x4 08048088 CD80 int 0x80 0804808A BB00000000 mov ebx, 0x0 0804808F B801000000 mov eax, 0x1 08048094 CD80 int 0x80 

上述输出信息的第一列是指令对应的地址码,利用它可以设置在程序执行时的断点:

 ald> break 0x08048088 Breakpoint 1 set for 0x08048088 

断点设置好后,使用 run 命令开始执行程序。ALD 在遇到断点时将自动暂停程序的运行,同时会显示所有寄存器的当前值:

 ald> run Starting program: hello Breakpoint 1 encountered at 0x08048088 eax = 0x00000004 ebx = 0x00000001 ecx = 0x08049098 edx = 0x0000000F esp = 0xBFFFF6C0 ebp = 0x00000000 esi = 0x00000000 edi = 0x00000000 ds = 0x0000002B es = 0x0000002B fs = 0x00000000 gs = 0x00000000 ss = 0x0000002B cs = 0x00000023 eip = 0x08048088 eflags = 0x00000246 Flags: PF ZF IF 08048088 CD80 int 0x80 

如果需要对汇编代码进行单步调试,可以使用 next 命令:

 ald> next Hello, world! eax = 0x0000000F ebx = 0x00000000 ecx = 0x08049098 edx = 0x0000000F esp = 0xBFFFF6C0 ebp = 0x00000000 esi = 0x00000000 edi = 0x00000000 ds = 0x0000002B es = 0x0000002B fs = 0x00000000 gs = 0x00000000 ss = 0x0000002B cs = 0x00000023 eip = 0x0804808F eflags = 0x00000346 Flags: PF ZF TF IF 0804808F B801000000 mov eax, 0x1 

若想获得 ALD 支持的所有调试命令的详细列表,可以使用 help 命令:

 ald> help Commands may be abbreviated. If a blank command is entered, the last command is repeated. Type `help ' for more specific information on . General commands attach clear continue detach disassemble enter examine file help load next quit register run set step unload window write Breakpoint related commands break delete disable enable ignore lbreak tbreak 

五、系统调用

即便是最简单的汇编程序,也难免要用到诸如输入、输出以及退出等操作,而要进行这些操作则需要调用操作系统所提供的服务,也就是系统调用。除非你的程序只完成加减乘除等数学运算,否则将很难避免使用系统调用,事实上除了系统调用不同之外,各种操作系统的汇编编程往往都是很类似的。

在 Linux 平台下有两种方式来使用系统调用:利用封装后的 C 库(libc)或者通过汇编直接调用。其中通过汇编语言来直接调用系统调用,是最高效地使用 Linux 内核服务的方法,因为最终生成的程序不需要与任何库进行链接,而是直接和内核通信。


DOS 一样,Linux 下的系统调用也是通过中断(int 0×80)来实现的。在执行 int 80 指令时,寄存器 eax
中存放的是系统调用的功能号,而传给系统调用的参数则必须按顺序放到寄存器 ebx,ecx,edx,esi,edi
中,当系统调用完成之后,返回值可以在寄存器 eax 中获得。

所有的系统调用功能号都可以在文件 /usr/include/bits/syscall.h 中找到,为了便于使用,它们是用 SYS_ 这样的宏来定义的,如 SYS_write、SYS_exit 等。例如,经常用到的 write 函数是如下定义的:

 ssize_t write(int fd, const void *buf, size_t count); 


函数的功能最终是通过 SYS_write 这一系统调用来实现的。根据上面的约定,参数 fb、buf 和 count 分别存在寄存器
ebx、ecx 和 edx 中,而系统调用号 SYS_write 则放在寄存器 eax 中,当 int 0×80
指令执行完毕后,返回值可以从寄存器 eax 中获得。

或许你已经发现,在进行系统调用时至多只有 5 个寄存器能够用来保存参数,难道所有系统调用的参数个数都不超过 5 吗?当然不是,例如 mmap 函数就有 6 个参数,这些参数最后都需要传递给系统调用 SYS_mmap:

 void * mmap(void *start, size_t length, int prot , int flags, int fd, off_t offset); 


一个系统调用所需的参数个数大于 5 时,执行int 0×80 指令时仍需将系统调用功能号保存在寄存器 eax
中,所不同的只是全部参数应该依次放在一块连续的内存区域里,同时在寄存器 ebx
中保存指向该内存区域的指针。系统调用完成之后,返回值仍将保存在寄存器 eax 中。

由于只是需要一块连续的内存区域来保存系统调用的
参数,因此完全可以像普通的函数调用一样使用栈(stack)来传递系统调用所需的参数。但要注意一点,Linux 采用的是 C
语言的调用模式,这就意味着所有参数必须以相反的顺序进栈,即最后一个参数先入栈,而第一个参数则最后入栈。如果采用栈来传递系统调用所需的参数,在执行
int 0×80 指令时还应该将栈指针的当前值复制到寄存器 ebx中。

六、命令行参数


Linux 操作系统中,当一个可执行程序通过命令行启动时,其所需的参数将被保存到栈中:首先是 argc,然后是指向各个命令行参数的指针数组
argv,最后是指向环境变量的指针数据 envp。在编写汇编语言程序时,很多时候需要对这些参数进行处理,下面的代码示范了如何在汇编代码中进行命令行参数的处理:

例3. 处理命令行参数

 # args.s .text .globl _start _start: popl %ecx # argc vnext: popl %ecx # argv test %ecx, %ecx # 空指针表明结束 jz exit movl %ecx, %ebx xorl %edx, %edx strlen: movb (%ebx), %al inc %edx inc %ebx test %al, %al jnz strlen movb $10, -1(%ebx) movl $4, %eax # 系统调用号(sys_write) movl $1, %ebx # 文件描述符(stdout) int $0x80 jmp vnext exit: movl $1,%eax # 系统调用号(sys_exit) xorl %ebx, %ebx # 退出代码 int $0x80 ret 

七、GCC 内联汇编

汇编编写的程序虽然运行速度快,但开发速度非常慢,效率也很低。如果只是想对关键代码段进行优化,或许更好的办法是将汇编指令嵌入到 C 语言程序中,从而充分利用高级语言和汇编语言各自的特点。但一般来讲,在 C 代码中嵌入汇编语句要比"纯粹"的汇编语言代码复杂得多,因为需要解决如何分配寄存器,以及如何与C代码中的变量相结合等问题。

GCC 提供了很好的内联汇编支持,最基本的格式是:

 __asm__("asm statements"); 

例如:

 __asm__("nop"); 

如果需要同时执行多条汇编语句,则应该用"\\n\\t"将各个语句分隔开,例如:

 __asm__( "pushl %%eax \\n\\t" "movl $0, %%eax \\n\\t" "popl %eax"); 

通常嵌入到 C 代码中的汇编语句很难做到与其它部分没有任何关系,因此更多时候需要用到完整的内联汇编格式:

 __asm__("asm statements" : outputs : inputs : registers-modified); 

插入到 C 代码中的汇编语句是以":"分隔的四个部分,其中第一部分就是汇编代码本身,通常称为指令部,其格式和在汇编语言中使用的格式基本相同。指令部分是必须的,而其它部分则可以根据实际情况而省略。

在将汇编语句嵌入到C代码中时,操作数如何与C代码中的变量相结合是个很大的问题。GCC采用如下方法来解决这个问题:程序员提供具体的指令,而对寄存器的使用则只需给出"样板"和约束条件就可以了,具体如何将寄存器与变量结合起来完全由GCC和GAS来负责。

在GCC内联汇编语句的指令部中,加上前缀’%'的数字(如%0,%1)表示的就是需要使用寄存器的"样板"操作数。指令部中使用了几个样板操作数,就表明有几个变量需要与寄存器相结合,这样GCC和GAS在编译和汇编时会根据后面给定的约束条件进行恰当的处理。由于样板操作数也使用’%'作为前缀,因此在涉及到具体的寄存器时,寄存器名前面应该加上两个’%',以免产生混淆。


跟在指令部后面的是输出部,是规定输出变量如何与样板操作数进行结合的条件,每个条件称为一个"约束",必要时可以包含多个约束,相互之间用逗号分隔开就
可以了。每个输出约束都以’='号开始,然后紧跟一个对操作数类型进行说明的字后,最后是如何与变量相结合的约束。凡是与输出部中说明的操作数相结合的寄
存器或操作数本身,在执行完嵌入的汇编代码后均不保留执行之前的内容,这是GCC在调度寄存器时所使用的依据。

输出部后面是输入部,输入约束的格式和输出约束相似,但不带’='号。如果一个输入约束要求使用寄存器,则GCC在预处理时就会为之分配一个寄存器,并插入必要的指令将操作数装入该寄存器。与输入部中说明的操作数结合的寄存器或操作数本身,在执行完嵌入的汇编代码后也不保留执行之前的内容。

有时在进行某些操作时,除了要用到进行数据输入和输出的寄存器外,还要使用多个寄存器来保存中间计算结果,这样就难免会破坏原有寄存器的内容。在GCC内联汇编格式中的最后一个部分中,可以对将产生副作用的寄存器进行说明,以便GCC能够采用相应的措施。

下面是一个内联汇编的简单例子:

例4.内联汇编


 /* inline.c */ int main() { int a = 10, b = 0; __asm__ __volatile__("movl %1, %%eax;\\n\\r" "movl %%eax, %0;" :"=r"(b) /* 输出 */ :"r"(a) /* 输入 */ :"%eax"); /* 不受影响的寄存器 */ printf("Result: %d, %d\\n", a, b); } 

上面的程序完成将变量a的值赋予变量b,有几点需要说明:

  • 变量b是输出操作数,通过%0来引用,而变量a是输入操作数,通过%1来引用。
  • 输入操作数和输出操作数都使用r进行约束,表示将变量a和变量b存储在寄存器中。输入约束和输出约束的不同点在于输出约束多一个约束修饰符’='。
  • 在内联汇编语句中使用寄存器eax时,寄存器名前应该加两个’%',即%%eax。内联汇编中使用%0、%1等来标识变量,任何只带一个’%'的标识符都看成是操作数,而不是寄存器。
  • 内联汇编语句的最后一个部分告诉GCC它将改变寄存器eax中的值,GCC在处理时不应使用该寄存器来存储任何其它的值。
  • 由于变量b被指定成输出操作数,当内联汇编语句执行完毕后,它所保存的值将被更新。

在内联汇编中用到的操作数从输出部的第一个约束开始编号,序号从0开始,每个约束记数一次,指令部要引用这些操作数时,只需在序号前加上’%'作为前缀就可以了。需要注意的是,内联汇编语句的指令部在引用一个操作数时总是将其作为32位的长字使用,但实际情况可能需要的是字或字节,因此应该在约束中指明正确的限定符:

限定符 意义
"m"、"v"、"o" 内存单元
"r" 任何寄存器
"q" 寄存器eax、ebx、ecx、edx之一
"i"、"h" 直接操作数
"E"和"F" 浮点数
"g" 任意
"a"、"b"、"c"、"d" 分别表示寄存器eax、ebx、ecx和edx
"S"和"D" 寄存器esi、edi
"I" 常数(0至31)

八、小结

Linux操作系统是用C语言编写的,汇编只在必要的时候才被人们想到,但它却是减少代码尺寸和优化代码性能的一种非常重要的手段,特别是在与硬件直接交互的时候,汇编可以说是最佳的选择。Linux提供了非常优秀的工具来支持汇编程序的开发,使用GCC的内联汇编能够充分地发挥C语言和汇编语言各自的优点。

九、参考资料

  1. 在网站http://linuxassembly.org上可以找到大量的Linux汇编资源。
  2. 软件包binutils提供了as和ld等实用工具,其相关信息可以在网站http://sources.redhat.com/binutils/上找到。
  3. NASM是Intel格式的汇编器,其相关信息可以在网站http://nasm.sourceforge.net上找到。
  4. ALD是一个短小精悍的汇编调试器,其相关信息可以在网站http://dunx1.irt.drexel.edu/~psa22/ald.html上找到。
  5. intel2gas是一个能够将Intel汇编格式转换成AT&T汇编格式的小工具,其相关信息可以在网站http://www.niksula.cs.hut.fi/~mtiihone/intel2gas/上找到。
  6. IBM developerWorks上有一篇介绍GCC内联汇编的文章(http://www-900.ibm.com/developerworks/cn/linux/sdk/assemble/inline/index_eng.shtml)。
  7. 本文代码下载:代码


关于作者
本文作者肖文鹏是北京理工大学计算机系的一名硕士研究生,主要从事操作系统和分布式计算环境的研究,喜爱Linux和Python。你可以通过xiaowp@263.net与他取得联系。

AT&T x86 asm 语法
http://www.chinaunix.net 作者:e4gle  发表于:2002-11-12 15:06:51

///////////////////////////////////////////////////////////////////////////////
linux下gcc的汇编格式是at&t格式的,和我们平时用的intel格式的汇编语法不一样,所以
很多熟悉windows汇编的人到linux下有点无所适从,所以我贴了我以前写的这篇文档,帮助
大家理解at&t汇编,做个参考手册
////////////////////////////////////////////////////////////////////////////////


AT&T x86 asm 语法

Author:  e4gle
Email:   e4gle@whitecell.org
Homepage:http://www.whitecell.org 

DJGPP 使用AT&T格式的汇编语法。和一般的intel格式的语法有点不同。主要不同点如下:

AT&T 语法颠倒了源和目的操作数的位置, 目的操作数在源操作数之后。寄存器操作数要有个%的前缀,
立即数操作数要有个$符号的前缀。 存储器操作数的大小取决于操作码的最后一个字符。 它们是b 
(8-bit), w (16-bit), 和 l (32-bit). 
这里有一些例子。 左边部分是intel指令格式,右边是at&t格式。
movw %bx, %ax// mov ax, bx
xorl %eax, %eax// xor eax, eax
movw $1, %ax// mov ax,1
movb X, %ah// mov ah, byte ptr X
movw X, %ax// mov ax, word ptr X
movl X, %eax// mov eax, X
大部分操作指令,at%t和intel都是差不多的,除了这些: 
movsSD // movsx 
movzSD // movz

S和D分辨代表源和目的操作数后缀。
movswl %ax, %ecx// movsx ecx, ax
cbtw        // cbw
cwtl        // cwde 
cwtd        // cwd 
cltd        // cdq
lcall $S,$O // call far S:O
ljmp $S,$O  // jump far S:O
lret $V     // ret far V
操作嘛前缀不能与他们作用的指令写在同一行。 例如, rep 和stosd应该是两个相互独立的指令, 存储器
的情况也有一点不同。通常intel格式的如下: 

section:[base + index*scale + disp] 

被写成: 

section:disp(base, index, scale) 

这里有些例子: 

movl 4(%ebp), %eax            // mov eax, [ebp+4])
addl (%eax,%eax,4), %ecx      // add ecx, [eax + eax*4])
movb $4, %fs%eax)           // mov fs:eax, 4)
movl _array(,%eax,4), %eax    // mov eax, [4*eax + array])
movw _array(%ebx,%eax,4), %cx// mov cx, [ebx + 4*eax + array])

Jump 指令通常是个短跳转。 可是, 下面这些指令都是只能在一个字节的范围内跳转: jcxz, jecxz, 
loop, loopz, loope, loopnz 和loopne。象在线文档所说的那样,一个jcxz foo可以扩展成以下工作: 
jcxz cx_zero
jmp cx_nonzero
cx_zero: 
jmp foo
cx_nonzero:
文档也注意到了mul和imul指令。 扩展的乘法指令只用一个操作数,例如, imul $ebx, $ebx将不会把结
果放入edx:eax。使用imul %ebx中的单操作数来获得扩展结果。 


——————————————————————————–

Inline Asm
我将首先开始inline asm, 因为似乎关于这方面的疑问非常多。这是最基本的语法了, 就象在线帮助信息
中描述的:
__asm__(asm statements : outputs : inputs : registers-modified); 

这四个字段的含义是: 

asm statements - AT&T 的结构, 每新行都是分开的。 
outputs - 修饰符一定要用引号引起来, 用逗号分隔 
inputs - 修饰符一定要用引号引起来, 用逗号分隔 
registers-modified - 名字用逗号分隔
一个小小的例子: 
__asm__("
pushl %eax\n
movl $1, %eax\n 
popl %eax"
);
假如你不用到特别的输入输出变量或者修改任何寄存器的值,一般来说是不会使用到其他的三个字段的, 
让我们来分析一下输入变量。

int i = 0;

__asm__("
pushl %%eax\n
movl %0, %%eax\n
addl $1, %%eax\n
movl %%eax, %0\n
popl %%eax"
:
: "g" (i)
);// increment i
不要为上面的代码所困扰! 我将尽力来解释它。我们想让输入变量i加1,没有任何输出变量, 也没有
改变寄存器值(我们保存了eax值)。 因此,第二个和最后一个字段是空的。 因为指定了输入字段, 我们
仍需要保留一个空的输出字段, 但是没有最后一个字段, 因为它没被使用。在两个空冒号之间留下一个新
行或者至少一个空格。

下面让我们来看看输入字段。 附加描述符可以修正指令来让你给定的编译器来正确处理这些变量。他们
一般被附上双引号。 那么这个"g"是用来做什么的呢?  只要是合法的汇编指令,"g"就让编译器决定该
在哪里加载i的值。一般来说,你的大部分输入变量都可以被赋予"g", 让编译器决定如何去加载它们 (gcc
甚至可以优化它们!)。 其他描述符使用"r" (加载到任何可用的寄存器去), "a" (ax/eax), "b" 
(bx/ebx), "c" (cx/ecx), "d" (dx/edx), "D" (di/edi), "S" (si/esi), 等等。 

我们将要提到一个在asm代码里面的如%0的输入变量。如果我们有两个输入, 他们会一个是%0一个是%1,
 在输入段里按顺序排列 (如下一个例子)。假如N个输入变量且没有输出变量, 从%0 到%N-1将和输入字段
里的变量相对应, 按顺序排列。 

如果任何的输入, 输出, 寄存器修改字段被使用, 汇编代码里的寄存器名必须用两个%来代替一个%。对应
于第一个没有使用最后三个字段的例子。

让我们看看两个输入变量且引入了"volatile"的例子: 

int i=0, j=1;
__asm__ __volatile__("
pushl %%eax\n
movl %0, %%eax\n
addl %1, %%eax\n
movl %%eax, %0\n
popl %%eax"
:
: "g" (i), "g" (j)
);// increment i by j
Okay, 现在我们已经有了两个输入变量了。没问题了, 我们只需要记住%0对应第一个输入变量(在这个例
子中是i), %1对应在i后面的列出的j。
Oh yeah, 这个volatile到底是什么意思呢? 它防止你的编译器修改你的汇编代码,就是不进行优化(纪录
, 删除, 结合,等等优化手段。), 不改变代码原样来汇编它们。建议一般情况下使用volatile选项。

让我们来看看输出字段:

int i=0;
__asm__ __volatile__("
pushl %%eax\n
movl $1, %%eax\n
movl %%eax, %0\n
popl %%eax"
: "=g" (i)
);// assign 1 to i
这看起来非常象我们前面提到的输入字段的例子; 确实也没有很大的不同。所有的输出修饰符前面都应该
加上=字符,他们同样在汇编代码里面用%0到%N-1来表示, 在输出字段按顺序排列。你一定会问如果同时
有输入和输出字段会怎么排序的呢? 好,下面一个例子就是让大家知道如何同时处理输入输出字段的。
 
int i=0, j=1, k=0;
__asm__ __volatile__("
pushl %%eax\n
movl %1, %%eax\n
addl %2, %%eax\n
movl %%eax, %0\n
popl %%eax"
: "=g" (k)
: "g" (i), "g" (j)
);// k = i + j
Okay, 唯一个不清楚的地方就是汇编代码中的变量的个数。我马上来解释一下。 
当同时使用输入字段和输出字段的时候: 

%0 … %K 是输出变量 

%K+1 … %N 是输入变量 

在我们的例子中, %0 对应k, %1 对应i, %2对应j。很简单,是吧? 

到现在为止我们都没有使用最后一个字段(registers-modified)。如果我们要在我们的汇编代码里使用
任何寄存器, 我们要明确的用push和pop指令来保存它们, 或者列到最后一个字段里面让gcc来处理它们。


这是前面的一个例子, 没有明确的保留和存贮eax。 

int i=0, j=1, k=0;
__asm__ __volatile__("
pushl %%eax\n    /*译者注:好像原文说的有点问题,明明是保存了eax的值,*/
movl %1, %%eax\n
addl %2, %%eax\n
movl %%eax, %0\n
popl %%eax"
: "=g" (k)
: "g" (i), "g" (j)
: "ax", "memory"
);// k = i + j
我们让gcc来保存和存贮eax, 如果必要的话。一个16-bit寄存器名代表了32-, 16-或8-bit寄存器。 如果
我们要改写内存 (写入一个变量等。), 建议在register-modified字段里面来指定"memroy"修饰符。这意
味着除了第一个例子我们都应该加上这个修饰符, 但是直到现在我才提出来, 是为了更简单易懂。

在你的内联汇编里面定位标号应该使用b或f来作为终止符, 尤其是向后向前的跳转。(译者注:b代表向
后跳转,f代表向前跳转)

For example, 

__asm__ __volatile__("
0:\n

jmp 0b\n

jmp 1f\n

1:\n

);
这里有个用c代码和内联汇编代码混合写的跳转程序的例子(thanks to Srikanth B.R for this tip).

void MyFunction( int x, int y 

__asm__( "Start:" ;
__asm__( …do some comparison… 
__asm__( "jl Label_1" 

CallFunction( &x, &y 
__asm__("jmp Start"

Label_1: 
return; 
}

——————————————————————————–

External Asm
Blah… Okay fine. Here’s a clue: Get some of your C/C++ files, 且用gcc -S file.c来编译。 然
后查看file.S文件。基本结构如下: 
.file "myasm.S"

.data
somedata: .word 0

 
.text
.globl __myasmfunc
__myasmfunc:

ret
Macros, macros! 头文件libc/asmdefs.h便于你写asm。 在你的汇编代码最前面包含此头文件然后就可以
使用宏了。一个例子: myasm.S: 
#include 

.file "myasm.S"

.data
.align 2
somedata: .word  0


.text
.align 4
FUNC(__MyExternalAsmFunc)
ENTER
movl   ARG1, %eax

jmp    mylabel

mylabel:

LEAVE
这是一个很经典的汇编代码框架。 


WSS(Whitecell Security Systems),一个非营利性民间技术组织,致力于各种系统安全技术的研究。坚持传统的hacker精神,追求技术的精纯。
WSS 主页:http://www.whitecell.org/ 
WSS 论坛:http://www.whitecell.org/forum/ 

微机原理与汇编语言基础

C语言能实现汇编语言的大部分功能,能进行位运算,可以直接对硬件进行操作,例如可以允许直接访问内存或端口的物理地址。因此,学习C语言的人掌握一定的汇编语言基础是必要的。

一、80×86系列CPU的编程结构

寄存器在汇编语言中的地位类似于变量。寄存器变量的访问时间远小于内存变量的访问时间。在汇编语言中大量的使用寄存器而不是直接访问内存。

1 寄存器堆

8086CPU是Intel系列的16位微处理器,有16根数据线和20根地址线,直接寻址空间为2^20即1MB。8088CPU的对外数据总线为8位,称为准16位微处理器。

8086/8088的内部寄存器(register)共有14个,如下:

(1)通用寄存器:8个,包括数据寄存器、地址指针寄存器、变址寄存器。

数据寄存器4个:AX BX CX DX,它们又可作为8个8位的寄存器使用,即AH BH CH DH AL BL CL DL

AX称为累加器,I/O指令均使用该寄存器,访问外部硬件和接口。

BX称为基址寄存器,在访问内存时用于存放基地址。

CX称为计数寄存器,用于循环、字符串的循环控制。

DX称为数据寄存器,在寄存器间接寻址的i/o指令中存放i/o地址,在作双字运算时[DX][AX]构成一个双字。

地址指针寄存器2个:SP BP

SP称为堆栈指针寄存器,BP称为基址指针寄存器,在作数组和字符串运算时,用于存放内存的偏移地址。

变址寄存器2个:SI DI

SI称为源变址寄存器,DI称为目的变址寄存器,用于数据块操作的内存寻址。

(2)段寄存器4个:CS DS ES SS

CS代码段寄存器,DS数据段寄存器,ES附加段寄存器,SS堆栈段寄存器

用于存放段地址(段基址)

(3)指令指针IP:始终指向将要执行的指令。用户不能直接访问和编程。

(4)标志寄存器FLAGS:16位寄存器,8086/8088仅使用了九个标志位。

2 标志寄存器

CF:进位标志位

PF:奇偶标志位

AF:辅助进位位

ZF:零标志位

SF:符号标志位

OF:溢出标志位

TF:跟踪标志位:单步标志

IF:中断标志位

DF:方向标志位

其中前六个为状态标志位,也叫条件码,用作条件转移指令中的判断条件。

后三个为控制标志位,对相关的操作起控制作用。

14个寄存器的内容,将要执行的指令,将要处理的数据,被称作CPU的“现场”,用debug的r命令可以清楚地看到“现场”

二、内存的分段组织

计算机的基本存储单位是字节,由8个二进制位组成,8个位捆绑使用。可用一个两位16进制数表示其内容。16位CPU一次可以处理两个字节。

为了正确访问内存,每一个存储器单位即字节必须给出一个地址。地址编号从0开始,依次加1,被称为线性编址

8086的地址线有20根,(详述)能够直接访问的地址空间为2^20即1MB。即内存的地址编号可以从0编到1M。用16进制数表示内存的物理地址,其地址范围为00000H~FFFFFH,为5位16进制数。每一个内存单元都有一个确定的20位物理地址。

但是,16位CPU的字长为16位,一次只能访问2^16=64k内存,如何访问1M的内存空间呢,在8086CPU中采用了地址分段的办法。即每一个存储单元的物理地址都有段地址和偏移地址两部分构成。

规定:(详述)只有地址为16的整数倍的物理地址可以作为段地址。这样,1MB的内存空间被分为了1M/16=64K个段。段地址的特征为xxxx0H。

我们知道了段地址和相对于段地址的段内偏移量(偏移地址)后就可以确定一个内存单元的物理地址了。所谓的偏移地址等于内存单元的物理地址减去段地址,不得超过一段(即64k)。

段地址可以不用20位表示,而用16位表示,即xxxx0H=xxxxH*10H表示为xxxxH,用4位16进制数表示。

物理地址的计算公式为:

物理地址=段地址*16+偏移地址

或者,物理地址=段地址*10H+偏移地址

乘以16相当于左移4位。即段地址左移4位和偏移地址相加。按十六进制数描述为,段地址左移一位和偏移地址相加。通常表示为

物理地址=段地址:偏移地址

例如:02002=0200:0002

可以看出,实际上偏移地址也是16位的,每一段的最大空间为2^16=64K,这样,不同的段之间有重叠。也即意味着物理地址可以有不同的表示方法。或者说不同的表示方法可以表示同一个物理地址

例如:02020=0200:0020=0100:1020=0000:2020=0202:0000=……

举例说明:摩天大楼。

注意:实际上每个段并不一定占用64k的最大空间。

总结:如此麻烦的做法带来的好处是扩大了内存的表示空间,更重要的是,原本很麻烦的程序的再定位工作变得异常简单,实际上一般的程序员以及高级语言并不关心段地址,段地址的分配工作交给操作系统了。

在高级语言中,变量有两个含义:首先表示的是内存的偏移地址,对于占用两个以上存储单元的变量,其地址是低地址,一般为偶数。其次,表示存储的内容,对于字数据(两个字节),其高位存入高地址,低位存入低地址,如

xxxx:0200 2b  …var

xxxx:0201 01

xxxx:0202 00

xxxx:0203 01

对于整型变量 var,地址为0200,内容为01H*256+2BH=01H*100H+2BH=256+32+11

若为双字长整型变量var,则地址一般为4的整数倍。var的地址为0200,其内容为01H*1000000H+01H*100H+2BH=4096+256+32+11。

640K~1M 的内存称为 UMB (upper memory block)

它分为a000H,b000H,c000H,d000H,e000H,f000H六个段,f000H段为ROM。存放的是ROM-BIOS(加电自检程序、固化子程序库、硬件参数等)。

加电时,尽管主机板厂家可以不同,计算机总是从 ffff:0000开始运行,其中存放的总是jmp指令,指向加电自检程序(post)真正的起始处。

ffff段除了前16个内存单元(物理地址<1M)外,还可以访问地址超过1M的部分内存,这部分内存称为HMA。

三、寻址方式(略)

取得操作数地址的方式称为寻址方式。

(1)数据寻址

立即寻址:mov al,5

寄存器寻址:mov ax,bx

直接寻址:mov ax,[2000H]

寄存器间接寻址:mov ax,[bx]

寄存器相对寻址:mov ax,offset[si]

基址变址寻址:mov ax,[bx][di]

相对基址变址寻址:mov offset[bx][si]

(2)指令寻址

段内直接寻址:jmp near ptr label1  //near ptr|short

段内间接寻址:jmp word ptr [offset][bp]

段间直接寻址:jmp far ptr label2

段间间接寻址:jmp dword ptr [offset][bx]

(3)端口寻址:

四、指令系统(略)

(一) 指令的执行时间

若时钟周期为T,则指令的基本执行时间如下(最佳寻址方式):

传送mov,     2T

加法add,     3T

整数乘法imul,      128T~154T

整数除法idiv,      165T~184T

移位(即乘以2或除以2),      2T

无条件转移,      15T

条件转移,      不转移 4T   转移 16T

采用不同方式寻址的加法指令执行时间如下:

寄存器到寄存器3T

存储器到寄存器9T+EA

寄存器到存储器16T+EA(访问两次存储器)

立即数到寄存器4T

立即数到存储器17T+EA(访问两次存储器)

不同寻址方式计算有效地址EA所需时间:

直接寻址 6T

寄存器间接寻址 5T

寄存器相对寻址 9T

基址寻址 7T~8T

相对基址变址寻址 11T~12T

总结:从指令执行时间上看,应尽量采用加法,避免乘法,尽量用移位不用乘法

尽量使用寄存器,少用存储器。尽量用简单的寻址方式,少用复杂的寻址方式。

(二) 指令系统

1.1 mov push pop xchg

1.2 in out xlat

1.3 lea lds les

1.4 lahf sahf pushf popf

注意:mov 等传送指令相当于赋值语句。in/out为基本的端口输入和输出

2.1 add adc inc

2.2 sub sbb dec neg cmp

2.3 mul imul

2.4 div idiv cbw cwd

2.5a daa das

2.5b aaa aas aam aad

3.1 and or not xor test

3.2 shl sal shr sal rol ror rcl rcr

4 movs cmps scas lods stos… …rep repe|repz repne|repnz

5.1 jmp

5.2 jz|je jnz|jne js jns jo jno jp|jpe jnp|jpo jb|jnae|jc jnb|jae|jnc

… …jb|jnae|jc jnb|jae|jnc jbe|jna jnbe|ja jl|jnge jnl|jge jle|jng jnle|jg

… …jcxz

5.3 loop loopz|loope loopnz|loopne

5.4 call ret

5.5 int into iret

6.1 clc cmc stc cld std cli sti

6.2 nop hlt wait esc lock

五、汇编程序的格式

(1)汇编语言的语句种类与格式

1 指令语句

标号:指令助记符 操作数1,操作数2;注释

2 伪指令语句

名字 伪指令 参数1,参数2,…;注释

符号定义语句:equ =

数据块定义语句:db dw dd dq dt dup(?)

标号及其属性:

        分析符type length size offset seg

        标号类型label byte word dword near far

        合成符ptr this

3 宏指令

4 段定义

segment ends

定位类型:para bye word page

组合类型:public common stack memory at 

类别:code data stack 

5 过程定义

proc endp

6 其他伪定义

assume org end

name title

even

radix 

short high low

+ – * / mod

and or xor not

eq ne lt gt le ge

(2) com 文件格式(略)

code segment public ‘code’

     org   100H

     assume cs:code,ds:data,es:data

main proc near

     jmp start

message db ‘How are u?$’

start:mov ah,9

      mov dx,offse message

      int 21H

      int 20H

main  endp

code  ends

      end main

(3) exe 文件格式(略)

stack segment stack ’stack’

      db 256dup(?)

stack ends

data segment public ‘data’

     ……

data ends

code segment public ‘code’

     assume cs:code,ds:data,es:data,ss:stack

main proc far

     push ds         ;保护psp前缀

     xor  ax,ax

     push ax         ;保护偏移0地址

     mov ax,data

     mov ds,ax

     mov es,ax

     ……

     ret

main endp

code ends

     end main

六、BIOS中断和DOS功能调用(略)

相当于高级语言中的库函数或者系统子程序。

七、debug和汇编语言上机(略)

微机原理与汇编语言基础

C语言能实现汇编语言的大部分功能,能进行位运算,可以直接对硬件进行操作,例如可以允许直接访问内存或端口的物理地址。因此,学习C语言的人掌握一定的汇编语言基础是必要的。

一、80×86系列CPU的编程结构

寄存器在汇编语言中的地位类似于变量。寄存器变量的访问时间远小于内存变量的访问时间。在汇编语言中大量的使用寄存器而不是直接访问内存。

1 寄存器堆

8086CPU是Intel系列的16位微处理器,有16根数据线和20根地址线,直接寻址空间为2^20即1MB。8088CPU的对外数据总线为8位,称为准16位微处理器。

8086/8088的内部寄存器(register)共有14个,如下:

(1)通用寄存器:8个,包括数据寄存器、地址指针寄存器、变址寄存器。

数据寄存器4个:AX BX CX DX,它们又可作为8个8位的寄存器使用,即AH BH CH DH AL BL CL DL

AX称为累加器,I/O指令均使用该寄存器,访问外部硬件和接口。

BX称为基址寄存器,在访问内存时用于存放基地址。

CX称为计数寄存器,用于循环、字符串的循环控制。

DX称为数据寄存器,在寄存器间接寻址的i/o指令中存放i/o地址,在作双字运算时[DX][AX]构成一个双字。

地址指针寄存器2个:SP BP

SP称为堆栈指针寄存器,BP称为基址指针寄存器,在作数组和字符串运算时,用于存放内存的偏移地址。

变址寄存器2个:SI DI

SI称为源变址寄存器,DI称为目的变址寄存器,用于数据块操作的内存寻址。

(2)段寄存器4个:CS DS ES SS

CS代码段寄存器,DS数据段寄存器,ES附加段寄存器,SS堆栈段寄存器

用于存放段地址(段基址)

(3)指令指针IP:始终指向将要执行的指令。用户不能直接访问和编程。

(4)标志寄存器FLAGS:16位寄存器,8086/8088仅使用了九个标志位。

2 标志寄存器

CF:进位标志位

PF:奇偶标志位

AF:辅助进位位

ZF:零标志位

SF:符号标志位

OF:溢出标志位

TF:跟踪标志位:单步标志

IF:中断标志位

DF:方向标志位

其中前六个为状态标志位,也叫条件码,用作条件转移指令中的判断条件。

后三个为控制标志位,对相关的操作起控制作用。

14个寄存器的内容,将要执行的指令,将要处理的数据,被称作CPU的“现场”,用debug的r命令可以清楚地看到“现场”

二、内存的分段组织

计算机的基本存储单位是字节,由8个二进制位组成,8个位捆绑使用。可用一个两位16进制数表示其内容。16位CPU一次可以处理两个字节。

为了正确访问内存,每一个存储器单位即字节必须给出一个地址。地址编号从0开始,依次加1,被称为线性编址

8086的地址线有20根,(详述)能够直接访问的地址空间为2^20即1MB。即内存的地址编号可以从0编到1M。用16进制数表示内存的物理地址,其地址范围为00000H~FFFFFH,为5位16进制数。每一个内存单元都有一个确定的20位物理地址。

但是,16位CPU的字长为16位,一次只能访问2^16=64k内存,如何访问1M的内存空间呢,在8086CPU中采用了地址分段的办法。即每一个存储单元的物理地址都有段地址和偏移地址两部分构成。

规定:(详述)只有地址为16的整数倍的物理地址可以作为段地址。这样,1MB的内存空间被分为了1M/16=64K个段。段地址的特征为xxxx0H。

我们知道了段地址和相对于段地址的段内偏移量(偏移地址)后就可以确定一个内存单元的物理地址了。所谓的偏移地址等于内存单元的物理地址减去段地址,不得超过一段(即64k)。

段地址可以不用20位表示,而用16位表示,即xxxx0H=xxxxH*10H表示为xxxxH,用4位16进制数表示。

物理地址的计算公式为:

物理地址=段地址*16+偏移地址

或者,物理地址=段地址*10H+偏移地址

乘以16相当于左移4位。即段地址左移4位和偏移地址相加。按十六进制数描述为,段地址左移一位和偏移地址相加。通常表示为

物理地址=段地址:偏移地址

例如:02002=0200:0002

可以看出,实际上偏移地址也是16位的,每一段的最大空间为2^16=64K,这样,不同的段之间有重叠。也即意味着物理地址可以有不同的表示方法。或者说不同的表示方法可以表示同一个物理地址

例如:02020=0200:0020=0100:1020=0000:2020=0202:0000=……

举例说明:摩天大楼。

注意:实际上每个段并不一定占用64k的最大空间。

总结:如此麻烦的做法带来的好处是扩大了内存的表示空间,更重要的是,原本很麻烦的程序的再定位工作变得异常简单,实际上一般的程序员以及高级语言并不关心段地址,段地址的分配工作交给操作系统了。

在高级语言中,变量有两个含义:首先表示的是内存的偏移地址,对于占用两个以上存储单元的变量,其地址是低地址,一般为偶数。其次,表示存储的内容,对于字数据(两个字节),其高位存入高地址,低位存入低地址,如

xxxx:0200 2b  …var

xxxx:0201 01

xxxx:0202 00

xxxx:0203 01

对于整型变量 var,地址为0200,内容为01H*256+2BH=01H*100H+2BH=256+32+11

若为双字长整型变量var,则地址一般为4的整数倍。var的地址为0200,其内容为01H*1000000H+01H*100H+2BH=4096+256+32+11。

640K~1M 的内存称为 UMB (upper memory block)

它分为a000H,b000H,c000H,d000H,e000H,f000H六个段,f000H段为ROM。存放的是ROM-BIOS(加电自检程序、固化子程序库、硬件参数等)。

加电时,尽管主机板厂家可以不同,计算机总是从 ffff:0000开始运行,其中存放的总是jmp指令,指向加电自检程序(post)真正的起始处。

ffff段除了前16个内存单元(物理地址<1M)外,还可以访问地址超过1M的部分内存,这部分内存称为HMA。

三、寻址方式(略)

取得操作数地址的方式称为寻址方式。

(1)数据寻址

立即寻址:mov al,5

寄存器寻址:mov ax,bx

直接寻址:mov ax,[2000H]

寄存器间接寻址:mov ax,[bx]

寄存器相对寻址:mov ax,offset[si]

基址变址寻址:mov ax,[bx][di]

相对基址变址寻址:mov offset[bx][si]

(2)指令寻址

段内直接寻址:jmp near ptr label1  //near ptr|short

段内间接寻址:jmp word ptr [offset][bp]

段间直接寻址:jmp far ptr label2

段间间接寻址:jmp dword ptr [offset][bx]

(3)端口寻址:

四、指令系统(略)

(一) 指令的执行时间

若时钟周期为T,则指令的基本执行时间如下(最佳寻址方式):

传送mov,     2T

加法add,     3T

整数乘法imul,      128T~154T

整数除法idiv,      165T~184T

移位(即乘以2或除以2),      2T

无条件转移,      15T

条件转移,      不转移 4T   转移 16T

采用不同方式寻址的加法指令执行时间如下:

寄存器到寄存器3T

存储器到寄存器9T+EA

寄存器到存储器16T+EA(访问两次存储器)

立即数到寄存器4T

立即数到存储器17T+EA(访问两次存储器)

不同寻址方式计算有效地址EA所需时间:

直接寻址 6T

寄存器间接寻址 5T

寄存器相对寻址 9T

基址寻址 7T~8T

相对基址变址寻址 11T~12T

总结:从指令执行时间上看,应尽量采用加法,避免乘法,尽量用移位不用乘法

尽量使用寄存器,少用存储器。尽量用简单的寻址方式,少用复杂的寻址方式。

(二) 指令系统

1.1 mov push pop xchg

1.2 in out xlat

1.3 lea lds les

1.4 lahf sahf pushf popf

注意:mov 等传送指令相当于赋值语句。in/out为基本的端口输入和输出

2.1 add adc inc

2.2 sub sbb dec neg cmp

2.3 mul imul

2.4 div idiv cbw cwd

2.5a daa das

2.5b aaa aas aam aad

3.1 and or not xor test

3.2 shl sal shr sal rol ror rcl rcr

4 movs cmps scas lods stos… …rep repe|repz repne|repnz

5.1 jmp

5.2 jz|je jnz|jne js jns jo jno jp|jpe jnp|jpo jb|jnae|jc jnb|jae|jnc

… …jb|jnae|jc jnb|jae|jnc jbe|jna jnbe|ja jl|jnge jnl|jge jle|jng jnle|jg

… …jcxz

5.3 loop loopz|loope loopnz|loopne

5.4 call ret

5.5 int into iret

6.1 clc cmc stc cld std cli sti

6.2 nop hlt wait esc lock

五、汇编程序的格式

(1)汇编语言的语句种类与格式

1 指令语句

标号:指令助记符 操作数1,操作数2;注释

2 伪指令语句

名字 伪指令 参数1,参数2,…;注释

符号定义语句:equ =

数据块定义语句:db dw dd dq dt dup(?)

标号及其属性:

        分析符type length size offset seg

        标号类型label byte word dword near far

        合成符ptr this

3 宏指令

4 段定义

segment ends

定位类型:para bye word page

组合类型:public common stack memory at 

类别:code data stack 

5 过程定义

proc endp

6 其他伪定义

assume org end

name title

even

radix 

short high low

+ – * / mod

and or xor not

eq ne lt gt le ge

(2) com 文件格式(略)

code segment public ‘code’

     org   100H

     assume cs:code,ds:data,es:data

main proc near

     jmp start

message db ‘How are u?$’

start:mov ah,9

      mov dx,offse message

      int 21H

      int 20H

main  endp

code  ends

      end main

(3) exe 文件格式(略)

stack segment stack ’stack’

      db 256dup(?)

stack ends

data segment public ‘data’

     ……

data ends

code segment public ‘code’

     assume cs:code,ds:data,es:data,ss:stack

main proc far

     push ds         ;保护psp前缀

     xor  ax,ax

     push ax         ;保护偏移0地址

     mov ax,data

     mov ds,ax

     mov es,ax

     ……

     ret

main endp

code ends

     end main

六、BIOS中断和DOS功能调用(略)

相当于高级语言中的库函数或者系统子程序。

七、debug和汇编语言上机(略)

2005年11月16日

罗马数字共有七个,即
I(1),V(5),X(10),L(50),C(100),D(500),M(1000)。

按照下面三条规则可以表示任意正整数。

重复数次:一个罗马数字重复几次,就表示这个数的几倍。

右加左减:在一个较大的罗马数字的右边记上一个较小的罗马数字,
表示大数字加小数字。在一个较大的数字的左边记上一个较小的罗
马数字,表示大数字减小数字。但是,左减不能跨越等级。
比如,99不可以用IC表示,用XCIX表示

基本数字Ⅰ、X 、C 中的任何一个,自身连用构成数目,或者放在大数的右边连用构成数目,都不能超过三个,比如40不能用XXXX,而用XL表示

设计一个函数,将100(包括100)以内的整数转换成罗马数字,超过100不考虑
int itor(int n,char* buf,int bufLength)
其中,n是要转换的整数,buf是要输出的字符串,bufLength是buf的字符长度
成功,返回0,否则,返回 -1;

比如:
char buf[256];
result = itor(n,buf,sizeof(buf));

when n = 28; result = 0, 输出"XXVIII";
when n = 72; result = 0, 输出"LXXII";

答案如下:

#include <stdio.h>
#include <string.h>

static const char* a[] =
{"","I","II","III","IV","V","VI","VII","VIII","IX"};
static const char* b[] =
{"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC","C"};
static const char* c[] =
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM", "M"};

int itor(int n, char *buf, int bufLength)
{
    if (n < 0 || n > 100)
        return -1;

    int num1,num2, num3;

    num1 = n % 10;
    num2 = (n / 10) % 10;
    num3 = n / 100;

    int index = 0;

    if (strlen(c[num3]) + strlen(b[num2]) + strlen(a[num1]) > bufLength)
        return -1;

    strcpy(buf, c[num3]);
    strcat(buf, b[num2]);
    strcat(buf, a[num1]);

    return 0;
}

int main(int ac, char** av)
{
    int i;
    char buffer[64] = {0};
    scanf("%d", &i);
    if (itor(i, buffer, 63) == 0)
        printf("%s\n", buffer);
}

###################################################################

有一个N*N的矩阵, 里面有N*N个数,这个矩阵的每一行,每一列都是排序好的,下面是一
个例子
1 3 7 9
2 5 13 14
6 7 25 26
20 24 30 40
现在设计一个算法,在这个矩阵中search一个数,要求尽可能快

####################################################################

1、写一个在一百万个数字中求十个最大的数算法

2、已知一个算法是NLog2N的,有没有办法把它搞成O(N)

3、写一个inttochar的函数,int未知长度

4、已知一组数据符合正态分布,如果要排序,用什么算法最快?