记录学习过程中的点点滴滴
2010年十一月
linux下x86架构下的内联汇编用法
十一 30th
如果您是 Linux 内核的开发人员,您会发现自己经常要对与体系结构高度相关的功能进行编码或优化代码路径。您很可能是通过将汇编语言指令插入到 C 语句的中间(又称为内联汇编的一种方法)来执行这些任务的。让我们看一下 Linux 中内联汇编的特定用法。(我们将讨论限制在 IA32 汇编。)
GNU 汇编程序简述
让我们首先看一下 Linux 中使用的基本汇编程序语法。GCC(用于 Linux 的 GNU C 编译器)使用 AT&T 汇编语法。下面列出了这种语法的一些基本规则。(该列表肯定不完整;只包括了与内联汇编相关的那些规则。)
寄存器命名
寄存器名称有 % 前缀。即,如果必须使用 eax,它应该用作 %eax。
源操作数和目的操作数的顺序
在所有指令中,先是源操作数,然后才是目的操作数。这与将源操作数放在目的操作数之后的 Intel 语法不同。
mov %eax, %ebx, transfers the contents of eax to ebx. |
操作数大小
根据操作数是字节 (byte)、字 (word) 还是长型 (long),指令的后缀可以是 b、w 或 l。这并不是强制性的;GCC 会尝试通过读取操作数来提供相应的后缀。但手工指定后缀可以改善代码的可读性,并可以消除编译器猜测不正确的可能性。
movb %al, %bl -- Byte move movw %ax, %bx -- Word move movl %eax, %ebx -- Longword move |
立即操作数
通过使用 $ 指定直接操作数。
movl $0xffff, %eax -- will move the value of 0xffff into eax register. |
更多 >
程序员眼中的编程语言
十一 22nd
下图是一个搞笑的图片——程序员眼中的编程语言。
- 图片的横轴是编程语言。
- 纵轴是各语言的程序员、粉丝、信徒。
- 中间的各个小图片则是,粉丝眼中的编程语言的形象。
比如说,
- 第一行第一列,是Java程序员看Java语言的样子,一幢现代化的大厦。
- 第一行第二列,是Java程序员看C语言,一个年老过时的骨灰级老头。
- 当然,C程序员看Java语言也比较搞,见第二行第一列。呵呵。
其它的大家自己看吧。还有另外一个关于操作系统的《粉丝眼中的操作系统》
poj3691分析与解题报告
十一 21st
题目链接:http://poj.org/problemstatus?problem_id=3691
题目大意
给定一系列代表疾病的DNA序列,同时已知一条DNA序列,计算改变最少的DNA序列来使这个DNA序列不包含疾病的DNA序列
例如:
AAA AAG #前面两列代表疾病的DNA序列 AAAG #正常的DNA序列 输出:1 #修改第三个字符即可
解题思路
AC自动机+状态dp
首先由desease的DNA序列,构造出Trie树即AC自动机,也可以叫做DFA图,每个节点代表一种状态,然后利用状态转移的动态规划方法,dp[i][j] 表示到目标串的第 i 个字符,DFA 状态为 j 时的最小修改数量,具体方程分为两种,已知dp[i-1][j]:
1,child[sequence[i]] 状态j的匹配第i个字符的子节点 && !is_danger
dp[i][child[sequence[i]]] = min{dp[i][child[sequence[j]]], dp[i-1][j]}
2,状态j的其他子节点 && is_danger
dp[i][other_child] = min{dp[i][other_child], dp[i-1][other_child] + 1}
最后在所有的dp[len-1][j] &&!is_danger 中找到 最小的值极为所求
更多 >
gdb调试程序之查看运行时数据【五】
十一 20th
在用gdb调试程序时,当程序运行到之前设置的断点时,很容易想到的操作就是查看当前变量的值,而gdb可以很轻易地满足的你的需求的~~
在gdb中最常用的命令就是print(简写p),具体格式如下:
print <expr> print/f <expr> f代表输出的格式 x 按十六进制格式显示变量 d 按十进制格式显示变量 u 按十六进制格式显示无符号整型 o 按八进制格式显示变量 t 按二进制格式显示变量 a 按十六进制格式显示变量 c 按字符格式显示变量 f 按浮点数格式显示变量
表达式
print命令可以接受表达式,其中表达式的定义遵循C/C++语法,需要注意的是表达式中不能出现程序中定义的宏表达式;同时在gdb表达式中,还支持以下三种特殊的操作符:
@ 是一个和数组有关的操作符,在后面会有更详细的说明 :: 指定一个在文件或是一个函数中的变量,注意与C++语法中的::操作符的区分 {} 表示一个指向内存地址的类型为type的一个对象
更多 >
gdb调试程序之栈和源码信息【四】
十一 15th
显示栈信息
当程序停在你设置的断点处时,你首先需要看的是函数调用的过程即函数调用栈,及每层栈中函数的名称、参数和局部变量等信息,这时可以用gdb提供的backtrace(bt)来查看函数调用栈信息
backtrace <n>, bt <n> n是一个正整数,表示只打印栈顶上n层的栈信息。 backtrace <-n> ,bt <-n> -n表一个负整数,表示只打印栈底下n层的栈信息。
(gdb) bt #0 func (n=250) at tst.c:6 #1 0x08048524 in main (argc=1, argv=0xbffff674) at tst.c:30 #2 0x400409ed in __libc_start_main () from /lib/libc.so.6
从上可以看出函数的调用栈信息:__libc_start_main –> main() –> func()
如果你要查看某一层的信息,你需要在切换当前的栈,一般来说,程序停止时,最顶层的栈就是当前栈,如果你要查看栈下面层的详细信息,首先要做的是切换当前栈,此时可以用frame命令来进行切换
frame <n> 是一个从0开始的整数,是栈中的层编号。比如:frame 0,表示栈顶,frame 1,表示栈的第二层。 up 表示向栈的上面移动n层,可以不打n,表示向上移动一层。 down 表示向栈的下面移动n层,可以不打n,表示向下移动一层。
当切换到某个某层frame时,可以使用info命令来查看当前函数的具体信息
info frame 显示当前frame的详细信息 info args 显示函数的参数的详细信息 info locals 打印出当前函数中所有局部变量及其值 info catch 打印出当前的函数中的异常处理信息
更多 >
gdb调试程序之单步调试【三】
十一 15th
断点维护
在gdb中,如果觉得设置的断点已经没有用处了,可以使用delete clair disable|enable 对断点进行操作
clear 清除所有的已定义的停止点。 clear <function>,clear <filename:function> 清除所有设置在函数上的停止点。 clear <linenum>,clear <filename:linenum> 清除所有设置在指定行上的停止点。 delete [breakpoints] [range...] 删除指定的断点,breakpoints为断点号。如果不指定断点号,则表示删除所有的断点。range 表示断点号的范围(如:3-7)。其简写命令为d。
比删除更好的方法是disable停止点,disable了的停止点,GDB不会删除,当你还需要时,enable即可.
disable [breakpoints] [range...] disable所指定的停止点,breakpoints为停止点号。如果什么都不指定,表示disable所有的停止点。简写命令是dis. enable [breakpoints] [range...] enable所指定的停止点,breakpoints为停止点号。 enable [breakpoints] once range... enable所指定的停止点一次,当程序停止后,该停止点马上被GDB自动disable。 enable [breakpoints] delete range... enable所指定的停止点一次,当程序停止后,该停止点马上被GDB自动删除。

poj2513分析与解题报告
十一 14th
题目大意:
给定一系列sticks,每个木棒的两端都涂有颜色,判断是否能够找到将所有的木棒连接起来的方法,使相互连接的木棒的两端的颜色是相同的?
题目链接:http://poj.org/problem?id=2513
解题思路
知识考查点:1,字典树;2,欧拉路:其中又考察了判断是否为连通图;3,并查集
可以将木棒间的关系抽象为一个无向图,无向图的边即代表一根木棒,节点代表木棒两端的颜色
现在要解决的问题是找到一条路径,遍历图的每条边一次,即欧拉路问题
要存在欧拉路就要满足:
1.该图必须是一个连通图
2.该图每个点的度数要么全为偶数,要么有且仅有两个点的度数为奇数
解决方法
1,给所有的颜色进行编号,同时计算所有颜色节点的度数(在木棒断点出现的次数);这里我试了两种选择:
1>一种是map进行映射,颜色作为key,
2> 还有就是构建Trie树,判断节点是否出现过
在实际编程过程中,使用map提交时超时,最后只好选择Trie树这种更高效率的查找方法
2,使用并查集来检验图的连通性,关于并查集的概念请google之
3,计算所有节点的度数,然后判断是否满足欧拉路的第二个条件
参考资料
1,关于并查集:http://hi.baidu.com/fandywang_jlu/blog/item/b49e40893ddbb0b00f244485.html
2,关于欧拉路:http://hi.baidu.com/luyade1987/blog/item/f2304d0fd6b4922f6059f3ab.html/cmtid/79f3bcecb3b02a30269791b1
近期评论