[NKU]sweet @ Google && TopCoder && CodeForces

  BlogJava :: 首页 :: 联系 :: 聚合  :: 管理
  33 Posts :: 1 Stories :: 15 Comments :: 0 Trackbacks

2011年10月7日 #

应刁哥多年前的约稿,外加结合编译原理系列连载,整理一下上一篇文章,写一个简易的汇编教程……
尽管谬误,疏漏若干,但是本文的目的不在于培养学霸,而在于让不会汇编的人简单看看就能写出个基本能用的汇编程序……
在程序设计中,我们知道一项基本原理:语言越高级,一般来讲容易编写,形式简洁,可移植性强,效率低……
反过来,语言越低级,越难编写,代码越容易是又臭又长还看不懂,越难移植,但是效率会很高……
汇编就是比较低级的语言了,由于其不太好移植,汇编版本又多种多样
因此,本着活学活用,到时候不会就查手册的原则,本文不会太着重强调语法,语法以intel语法为主……
Chapter1:一些基本知识
首先,CPU有若干寄存器,在32位CPU中,形如eax,ebx,ecx,edx……64位CPU则为rax,rbx……
虽然寄存器这个名字很NB,其实它的本质上就是int,为了向下兼容的需要,一些老的程序,也有可能能在新型的CPU上运行(详见DOS老游戏,有的能玩,有的不能玩)
以64位举例:
64位寄存器rax,低32位是eax,eax低16位是ax,ax高8位叫ah,低8位叫al……
CPU只能直接对寄存器进行运算……因为电路结构就是那样的……因此,所有的操作,都需要经过寄存器
譬如赋值:A = 1,实际上是 AX = 1; A = AX; 譬如 A = A + B,应该是 AX = A; AX += B; A = AX; 这样
我是比较不求甚解的,99%功能(运算,判断,指针)等,使用eax,ebx,ecx,edx都能搞定……于是咱们也就不说别的了……
Chapter2:汇编的基本语法:
汇编语言大概分为四个段,其中比较需要记住的就是代码段和数据段……
用类似高级语言的思路来讲,数据段用于定义一些全局变量,代码段用于写程序……
来看一个简单的 Hello World(环境:yasm,64位)
global main 
extern printf 
section .data 
ctrlout   db      '%s', 10, 0 
hw    db      'Hello World', 0 
; this is a comment
section .text
main:
mov rax, 0
mov rdi, ctrlout
mov rsi, hw
call printf
        mov rax, 0
ret
其中,刚开始global main 表示程序入口,由于这里直接调用了Linux的函数printf,之后需要gcc编译,所以叫做main,如果只使用中断输出的话,可以搞成_start
之后extern意义和C++类似,表示这个函数在别处,叫编译器以为他有就行……
section .data  表示数据段,后面是一些定义,以及初始化
注意这里定义的东西类型都像是指针一样,ctrlout,hw 实际上是地址……
初始化必须搞的干净一点,有一次调了半天不对,就是因为一个64位int,前4位没有初始化成0……
之后 section .text 表示代码段,这里调用C语言函数,网上说,64位汇编中,参数传递方式有了修改,大概是有4~5个寄存器专门保存参数,如果参数过多,再放入栈,rax存放栈中的参数个数……我们想printf("%s","Hello World"),就要调用两个参数,于是,我们把第一个参数,字符串ctrlout的指针mov进rdi,hw mov进rsi,rax赋值为0 ,然后,调用……
(实现时,需要手册自行查阅一下本机怎么搞)
函数的返回值在rax,于是return 0
然后 yasm -f elf64 XXX.asm
gcc -o XXX XXX.o
./XXX
一个崭新的hello world 出现了……
Chapter3:汇编的一些简单指令:
由于这是速成教程,选取一部分指令……要记住,CPU只能直接对寄存器进行运算……
mov:相当于赋值, mov eax,b  相当于eax = b;
注意:mov 后面的两个东西至少要有一个是寄存器……
同时,和高级语言一样,不能搞什么 mov 10,eax……
add:add eax,b 相当于eax+=b
sub:基本同上……
mul || imul:前面是无符号的乘,后面是有符号的乘,默认被乘数在AX,于是指令形如:mul BX,如果有溢出,则高位溢出到DX,记得备份DX的东西……
div  ||  idiv:前面是无符号整除,后面是有符号整除,默认被除数是DX(高16位)和AX(低16位),因此,除法之前记得把DX清零,否则数会不对……
之后商在AX,余数在DX
指令形如:div BX
push/pop:每个程序都有栈,或者是在程序中定义堆栈段,或者使用默认栈
push eax,表示把eax放进栈里,pop ebx,表示取出栈顶,放在ebx中……
push和pop异常重要,一个重要作用就是保护寄存器,譬如DX中有内容,但是现在要做乘法,没准会破坏DX(见上),于是,先PUSH DX,然后,乘法,然后POP DX,又好比你要调用一个函数,但是寄存器里有有用的信息,不保证这个函数不会破坏,于是,把所有寄存器先push进去,运行函数,然后再pop出来,这是常用技巧……
另外也可以用来给函数传参数,传时倒序压入,用时顺序取出,栈,先进后出,你们懂的……
Chapter4:if以及循环
首先我们要记得,被Dijkstra老爷子骂的一文不值的goto……
jmp语法和C++里的goto基本一样
start:
XXX
jmp start
然后,汇编没有if then,但是有条件goto
有个语句叫做cmp
cmp X,Y (老原则,这两个得有一个寄存器……如果和常数比较,常数必须在后面)
传说中具体实现是减法……
这个的效果是可能改变若干标识位的值……譬如:0标识,进位标识,溢出标识……等等……
然后,有若干指令
jl XX(l==less) 相当于 if (x<y) goto XX; 下同
jg XX(g==greater)
jle XX(ne==less or equal)
jge XX(ge==greter or equal)
jnle XX(n==no->nle==g)
jnge XX(n==no->nge==l)
有了if then,各种运算,我们就能做出来&&,||的逻辑
有了if then,我们也能做出循环……
很多的功能就有了……
Chapter5:实战
看看
int main() {
    int a,b,c;
    input(a);
    input(b);
    if (a < b) {
        c = a;
    } else {
        c = b;
    }
    print(c);
}
用汇编翻译出来啥样:
global main 
extern printf 
extern scanf 
section .data 
ctrlout   db      '%lld', 10, 0 
ctrlin    db      '%lld', 0 
_a db 0,0,0,0,0,0,0,0
_b db 0,0,0,0,0,0,0,0
_c db 0,0,0,0,0,0,0,0
section .text
main:
mov rax, 0
mov rdi, ctrlin
mov rsi, _a
call scanf
mov rax, 0
mov rdi, ctrlin
mov rsi, _b
call scanf
MOV rax, [_a]
CMP rax, [_b]
jl @0
jmp @2
@0:
MOV rax, [_a]
MOV [_c], rax
jmp @1
@2:
MOV rax, [_b]
MOV [_c], rax
@1:
mov rax, 0
mov rdi, ctrlout
mov rsi, [_c]
call printf
mov rax, 0
ret
Chapter6:其它
由于现实生活中,我需要写汇编时候实在是少,因此也没啥经验……尽管借助手册,可以对付着写一点汇编代码,但是那是不科学的……对我来讲,汇编告诉我们的一些底层的东西更有价值,可以在高级语言中有所体现:譬如一些表达式的写法,可以考虑写的更科学一些,譬如 c = a / b, q = a % b,记得写成 c = a / b; q = a - c * b,譬如灵活使用switch,等等……
posted @ 2012-01-26 22:42 sweetsc 阅读(670) | 评论 (0)编辑 收藏

最近,做OS大作业,编译大作业,和进行实验室工作,强烈认识到了自己对C语言的了解不多……
于是今天老图借了本书,学习一下……
来看一下我最头疼的define……
define的作用:
一是直接定义一个东西……类似标记
譬如:
1 #ifndef test
2 #define test
3 /*
4 balabalabala.
5 */
6 #endif
刘JX老师在大一C++课上教育我们,写头文件一定要加上这么个东西……为什么呢……
再提一下include的事情…… #include<XXXX>,实际上是直接把XXXX整个文件COPY了进来……
如果出现这样的情况:
1 #include <set>
2 #include <map>
我们知道,Cpp的 map 实际上是用 set 做的,map的头文件里肯定有一个 #include <set>,那么,相当于set这个文件在这段程序里面出现了两次……
如果没有ifndef这套的话,相当于将set中的代码重复贴了两次,就粗大事了……
代码第一段ifndef test 代表:如果没有define test,则执行下面的那段,先 define test,然后balabala,最后endif,下次再看到这段代码的时候,ifndef test ,此时会发现test已经define过了,直接endif,中间balabala的代码不会重复两次……

二是直接定义一些……怎么说呢,类似替换规则的东西……

譬如:直接定义常量:
1 #define MAXN 10000
这个实际上就是直接在程序编译之前,将里面的MAXN都替换成10000
预先定义一些常量,好处大家都懂:避免程序内部太多的“magic number”,增强可读性,也便于修改……这里相当于直接替换,貌似C的数组,定义的时候不能用int做下标,const int也不行,只能通过这个方法,用立即数……

譬如:给一些东西改个名字:
  1 #include <stdio.h> 
  2 #define Q scanf 
  3  
  4 int main() { 
  5     int a; 
  6     Q("%d",&a); 
  7     printf("%d\n",a); 
  8     return 0; 
  9 } 

这里有一些玄机:
1:#似乎是因为没有转义?所以不能胡用……
譬如:#define USEMATH #include <math.h> 是不能达到预期效果的……
2:如果这一行太长,可以用\表示和下一行连起来…… 貌似这个'\'也没转义, #define BACKSLASH \ 也是不行的……

譬如:可以定义一些简单的函数:
#define max(a,b) ((a) > (b) ? (a) : (b))
某种意义上这比template NB...
这样,int c = max(a,b); 就自动替换成 int c =((a) > (b) ? (a) : (b)); 了
此处有一个技巧:有的时候,咱们需要用大括号来实现这个"函数",但是,由define直接替换知道,这个替换出来,相当于{/*balabala*/};这样,语法是错的……
于是怎么办呢……咱们可以用 do {/*balabala*/} while(0) 这样的形式,绕开这个问题…… 在上次OS大作业上咱们都见到了……
此处还有两个玄机:一是千万记得要加括号……为什么呢……
譬如:
#define mul(a,b) a * b
看着挺好,mul(1,2 + 3)就出事了…… 直接替换出来,是 1 * 2 + 3,就错了……
正确方法是:#define mul(a,b) ((a) * (b)),万无一失……
另一个玄机是避免++,--之类的,譬如
#define sqr(a) ((a) * (a))
sqr(a++),如果sqr是真的函数的话,计算出没有问题……但是define会忠实的给你替换成((a++) * (a++))……怎么加的不重要,结果就不是你想的了……

最后有两个用法,一个是#,#会将你作为“函数”的“参数”传入的东西转化为字符串;一个是...,作用一看便知:
 1 #include <stdio.h>
 2 #define max(a,b) ((a) > (b) ? (a) : (b))
 3 #define PRINT() printf(__VA_ARGS__)
 4 #define debug(x) do { \
 5     PRINT(#x);  \
 6     PRINT(" = %d\n",(x)); \
 7     } while (0)
 8 
 9 int main() {
10     int a,b;
11     scanf("%d%d",&a,&b);
12     debug(a);
13     debug(b);
14     debug(a + b);
15     debug(max(a,b));
16     return 0;
17 }
posted @ 2011-12-02 01:59 sweetsc 阅读(320) | 评论 (0)编辑 收藏

题意很简单……双方给N个人(N<=6)打三国杀1V1,你知道对手每个人能克制你哪些人,我们认为两个人对打,他能克你则他胜利,否则你胜利;某人的N个人死光就输了……你需要组织阵容按照顺序对抗对手……求有没有一个顺序,无论对手顺序如何,你都能胜……
N!枚举自己的顺序,然后N!枚举对方的顺序,O(N)验证即可……
注意字典序最小……

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <map>
 5 #include <algorithm>
 6 #include <iostream>
 7 
 8 using namespace std;
 9 
10 map<string,int> mp;
11 int n;
12 int res[10];
13 int my[10];
14 char buf[50];
15 char name[10][50];
16 string ans;
17 
18 void check() {
19     int enemy[] = {0,1,2,3,4,5,6,7,8,9};
20     do {
21         int i = 0;
22         int j = 0;
23         while (i < n && j < n) {
24             if ((1 << my[i]) & res[enemy[j]]) i ++else j++;
25         }
26         if (i == n) return;
27     } while (next_permutation(enemy,enemy + n));
28     string tmp;
29     for (int i = 0; i < n; i++) {
30         if (i) tmp += " ";
31         tmp += name[my[i]];
32     }
33     if (ans == "" || ans > tmp) ans = tmp;
34 }
35 
36 int main() {
37     int nn; scanf("%d",&nn);
38     for (int ii = 1; ii <= nn; ii++) {
39         mp.clear();
40         memset(res,0,sizeof(res));
41         scanf("%d",&n);
42         for (int i = 0; i < n; i++) {
43             scanf("%s",name[i]);
44             mp[string(name[i])] = i;
45         }
46         for (int i = 0; i < n; i++) {
47             int m; scanf("%d",&m);
48             for (int j = 0; j < m; j++) {
49                 scanf("%s",buf);
50                 int tmp = mp[string(buf)];
51                 res[i] |= 1 << tmp;
52             }
53         }
54         for (int i = 0; i < n; i++) {
55             my[i] = i;
56         }
57         ans = "";
58         do {
59             check();
60         } while (next_permutation(my,my + n));
61         printf("Case %d: ",ii);
62         if (ans == "") {
63             puts("No");
64         } else {
65             puts("Yes");
66             for (int i = 0; i < ans.length(); i++) putchar(ans[i]);
67             putchar(10);
68         }
69     }
70     return 0;
71 }
posted @ 2011-10-07 20:15 sweetsc 阅读(612) | 评论 (0)编辑 收藏