Snowdream

这个lab主要考察gdb的使用和对汇编代码的理解。后者在平时的作业中涉及得较多，这里不再赘述，主要介绍一下gdb
其实偶对这个也不是很熟，有错误请指正 @@

简单的说，gdb是一款强大的调试工具，尽管它只有文本界面（需要图形界面可以使用ddd，不过区别不大），但是功能却比eclipse等调试环境强很多。

接下来看看怎样让它为lab2拆炸弹服务，在命令行下运行gdb bomb就能开始调试这个炸弹程序，提高警惕，恩

首先最重要的，就是如何阻止炸弹的引爆，gdb自然提供了一般调试工具都包括的断点功能——break命令

在gdb中输入help break能够看到相关的信息

(gdb) help break

Set breakpoint at specified line or function.
Argument may be line number, function name, or "*" and an address.
If line number is specified, break at start of code for that line.
If function is specified, break at start of code for that function.
If an address is specified, break at that exact address.
With no arg, uses current execution address of selected stack frame.
This is useful for breaking on return to a stack frame.
Multiple breakpoints at one place are permitted, and useful if conditional.
Do "help breakpoints" for info on other commands dealing with breakpoints.

可以看到break允许我们使用行号、函数名或地址设置断点

按ctrl+z暂时挂起当前的gdb进程，运行objdump –d bomb | more 查看反编译后的炸弹文件，可以看到里面有这么一行（开始的那个地址每个人都不同）：

08049719 <explode_bomb>:

这个就是万恶的引爆炸弹的函数了，运行fg返回gdb环境，在这个函数设置断点：

break explode_bomb （可以使用tab键自动补齐）

显示

Breakpoint 1 at 0x8049707

接下来你可以喘口气，一般情况下炸弹是不会引爆的了

下面我们来拆第一个炸弹，首先同样是设置断点，bomb.c中给出了各个关卡的函数名，第一关就是phase_1，使用break phase_1在第一关设置断点

接下来就开始运行吧，输入run

Welcome to my fiendish little bomb. You hava 6 phases with

which to blow yourself up. Hava a nice day!

我们已经设置了炸弹断点，这些恐吓可以直接无视。

输入ABC继续（输入这个是为了方便在后面的测试中找到自己的输入串地址）

提示Breakpoint 2, 0x08048c2e in phase_1 ()，说明现在程序已经停在第一个关了

接下来就是分析汇编代码，使用disassemble phase_1显示这个函数的汇编代码

注意其中关键的几行：

8048c2e:68 b4 99 04 08          push   $0x80499b4

8048c33:ff 75 08              pushl 0x8(%ebp)

8048c36:e8 b1 03 00 00        call   8048fec <strings_not_equal>

这个lab很厚道的一点就是函数名很明确地说明了函数的功能 ^_^

估计这三行代码的意思就是比较两个字符串相等，不相等的话应该就会让炸弹爆炸了

因为字符串很大，所以传递给这个比较函数的肯定是他们的地址，分别为0x80499b4和0x8(%ebp)

我们先来看后者，使用p/x *(int*)($ebp + 8)查看字符串所在的地址

$1 = 0x804a720，继续使用p/x *0x804a720查看内存中这个地址的内容

$2 = 0x434241，连续的三个数，是不是想起什么了？把这三个数分别转换为十进制，就是67 66 65，分别为CBA的ASCII码，看来这里保存了我们输入的串。

接下来0x80499b4里肯定保存着过关的密码

p/x *0x80499b4，显示$3 = 0x62726556，c中的字符串是以0结尾的，看来这个字符串还不止这个长度，继续使用

p/x *0x80499b4@10查看这个地址及其后面36个字节的内容，终于在第二行中出现了终结符”0x0”（不一定是四个字节）

$4 = {0x62726556, 0x7469736f, 0x656c2079, 0x20736461, 0x75206f74, 0x656c636e, 0x202c7261, 0x72616e69,

 0x75636974, 0x6574616c, 0x69687420, 0x2e73676e, 0x0, 0x21776f57, 0x756f5920, 0x20657627, 0x75666564,

 0x20646573, 0x20656874, 0x72636573}

把开头到0x0的所有信息字节下来，通过手算或者自己写程序得出最后的密码串（注意little endian中字符的排列方式！）

输入run重新运行，输入刚才得出的密码串，如果前面的计算正确的话，就会提示

Phase 1 defused. How about the next one?

关于这个lab的一些其他心得：

1.       VMware中开发很不舒服，屏幕小、字体丑@@、需要Ctrl+Alt切换回windows，不怎么方便，推荐在windows下使用pietty登录虚拟机中的linux系统（RedHat 9默认安装了sshd），个人觉得这样比较方便。

2.       ASCII查询可以在linux终端中运行man ascii。

3.       退出gdb后，再次进入时一定要注意使用break给explode_bomb上断点，不可大意 ~.~

4.       后面的几关涉及递归等内容，也有和前面几次作业很相似的东东。

5.    gdb中还有一个很好用的jump指令，可以在运行时任意跳转。
6.    看汇编代码时，使用objdump -d bomb > bomb.asm把汇编代码保存到bomb.asm中，然后使用sftp工具把这个文件下载到windows或者直接在vim中查看，这样比在gdb中看方便一些。
7.    个人认为lab2和期中考试不冲突，这个lab2可以帮你理清很多汇编语言的概念

其他补充：
sfox: 
可以通过GDB中的x /s addr输出以\0结尾的字符串
ICSLab: 
为了防止每次拆的时候都不停的输入之前的stage的key，可以把key存入文本文件，一行一个key，不要有多余字符
然后GDB run 的时候用gdb bomb 回车
(gdb) b .... ....
(gdb) r password.txt
这样bomb就会自动从password.txt中读入之前的密码
直到到达最后一个空行处，如Lab2的说明文档中所述。

http://www.wiki.cn/wiki/Exponentiation_by_squaring

Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. In additive groups the appropriate name is double-and-add algorithm. It implicitly uses the binary expansion of the exponent. It is of quite general use, for example in modular arithmetic.

1. 纯虚函数的声明：将函数赋值为0
virtual void gen_elems(int pos) = 0;

2. 通常情况下，定义了一个或多个虚函数的基类要定义一个虚析构函数，因为在释放子类内存时具体析构函数需要在运行期才能确定。
作者也不建议把析构函数定义为纯虚的，即使没有任何具体的实现。

恩，睡觉

O(1)空间求矩阵转置的算法，貌似是分解成几个循环群，分别处理。
from wikipedia

http://www.blogjava.net/Files/zellux/In-place_matrix_transposition.zip

Pitfall 1：判断x的奇偶性 当x为负奇数时，x % 2的值为负数。
Note：把 x % 2 == 1 改为 x % 2 != 0

Pitfall 2：长整数计算
long MICROS_PER_DAY = 24 * 60 * 60 * 1000 * 1000;
这个表达式先计算左边几个int的乘积，然后再把值转换为long，因此仍会溢出
Note：把24改成24L

Pitfall 3：看看这句话的结果
System.out.println(12345+5432l);
Note：5432后面的l很容易被看成1，因此建议使用L表示长整形时都使用大写。

Pitfall 4：下面这句话又会是什么结果
System.out.println(Long.toHexString(0x100000000L + 0xcafebabe));
Java计算时先用sign-extension把后面一个数转成long，然后再计算
Note：尽量避免混合类型计算

Pitfall 5：这句话呢？
System.out.println((int) (char) (byte) -1);
结果是65535
Note：char是无符号类型，将char转为int时使用zero-extension

Pitfall 6：交换变量值
int x = 1984;
int y = 2001;
x ^= y ^= x ^= y;
最终结果是x == 0, y == 1984
Note：Java中操作符是从左往右计算的 (JLS 15.7)
改成 y = (x ^ (y ^= x) ^ y; 就可以，但是永远不要这么做 
 
Pitfall 7：问号操作符
char x = 'X';
int i = 0;
System.out.print(true ? x : 0);
System.out.print(false ? i : x);
输出结果为X88
Note：同样是混合类型计算导致的问题，建议在条件表达式中使用类型相同的第二和第三操作符。
 
Pitfall 8：看似相同的表达式的不同结果
short x = 0;
int i = 123456;
1) x += i; // 隐含了类型转换，结果为-7616
2) x = x + i; // 编译无法通过，因为损失了精度 
 

第一次接触后缀树应该是在某次省队集训，徐串大牛做的讲座。
不过当时只是有了个印象。
现在发现这东东还是很好用的  @,@

http://www.blogjava.net/Files/zellux/SuffixT1withFigs.rar

On–line construction of suffix trees
by Esko Ukkonen

Key Words.
Linear time algorithm, suffix tree, suffix trie, suffix automaton, DAWG.

Abstract.
An on–line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It has always the suffix tree for the scanned part of the string ready. The method is developed as a linear–time version of a very simple algorithm for (quadratic size) suffix tries. Regardless of its quadratic worst-case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give in a natural way the well–known algorithms for constructing suffix automata (DAWGs).

发现居然还是Pascal描述，亲切啊亲切

http://iprai.hust.edu.cn/icl2002/algorithm/datastructure/basic/binary_tree/chapter5_4.htm

线索二叉树

当用二叉链表作为二叉树的存储结构时，因为每个结点中只有指向其左、右儿子结点的指针，所以从任一结点出发只能直接找到该结点的左、右儿子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率。

我们可以证明：在n个结点的二叉链表中含有n+1个空指针。因为含n个结点的二叉链表中含有个指针，除了根结点，每个结点都有一个从父结点指向该结点的指针，因此一共使用了n-1个指针，所以在n个结点的二叉链表中含有n+1个空指针。

因此可以利用这些空指针，存放指向结点在某种遍历次序下的前驱和后继结点的指针。这种附加的指针称为线索，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。为了区分一个结点的指针是指向其儿子的指针，还是指向其前驱或后继结点的线索，可在每个结点中增加两个线索标志。这样，线索二叉树结点类型定义为：

其中ltag为左线索标志，rtag为右线索标志。它们的含义是:

• ltag=0，LeftChild是指向结点左儿子的指针；
• ltag=1，LeftChild是指向结点前驱的左线索。
  
• rtag=0，RightChild是指向结点右儿子的指针；
• rtag=1，RihgtChild是指向结点后继的右线索。

例如图13(a)是一棵中序线索二叉树，它的线索链表如图13(b)所示。

(a)

(b)

图13 线索二叉树及其线索链表

图13(b)中，在二叉树的线索链表上增加了一个头结点，其LeftChild指针指向二叉树的根结点，其RightChild指针指向中序遍历时的最后一个结点。另外，二叉树中依中序列表的第一个结点的LeftChild指针，和最后一个结点的RightChild指针都指向头结点。这就像为二叉树建立了一个双向线索链表，既可从第一个结点起，顺着后继进行遍历，也可从最后一个结点起顺着前驱进行遍历。

如何在线索二叉树中找结点的前驱和后继结点？以图13的中序线索二叉树为例。树中所有叶结点的右链是线索，因此叶结点的RightChild指向该结点的后继结点，如图13中结点"b"的后继为结点"*"。当一个内部结点右线索标志为0时，其RightChild指针指向其右儿子，因此无法由RightChild得到其后继结点。然而，由中序遍历的定义可知，该结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。例如在找结点"*"的后继时，首先沿右指针找到其右子树的根结点"-"，然后沿其LeftChild指针往下直至其左线索标志为1的结点，即为其后继结点(在图中是结点"c")。类似地，在中序线索树中找结点的前驱结点的规律是：若该结点的左线索标志为1，则LeftChild为线索，直接指向其前驱结点，否则遍历左子树时最后访问的那个结点，即左子树中最右下的结点为其前驱结点。由此可知，若线索二叉树的高度为h，则在最坏情况下，可在O(h)时间内找到一个结点的前驱或后继结点。在对中序线索二叉树进行遍历时，无须像非线索树的遍历那样，利用递归引入栈来保存待访问的子树信息。

对一棵非线索二叉树以某种次序遍历使其变为一棵线索二叉树的过程称为二叉树的线索化。由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。为了记下遍历过程中访问结点的先后次序，可附设一个指针pre始终指向刚刚访问过的结点。当指针p指向当前访问的结点时，pre指向它的前驱。由此也可推知pre所指结点的后继为p所指的当前结点。这样就可在遍历过程中将二叉树线索化。对于找前驱和后继结点这二种运算而言，线索树优于非线索树。但线索树也有其缺点。在进行插人和删除操作时，线索树比非线索树的时间开销大。原因在于在线索树中进行插人和删除时，除了修改相应的指针外，还要修改相应的线索。

要做个和Java3D有关的项目，需要稍微了解下相关的知识。
看的资料是The Java3d Tutorial，版本有点早，凑合着看了。 
    
Java 3D 的虚拟环境是从场景图(scene graph)中建立的，场景图聚合(assemble)了各种定义几何、声音、光、位置、方位等元素的类。 

一种常用的定义图的数据结构由结点(node)和弧(arc)组成。结点都是Java 3D类的实例，而弧则代表了实例间两种不同的关系。
最常见的关系是父子(parent-child)关系。一个组结点(group node)可以包含任意多的子结点，但只能有一个父结点。
另一种关系是引用(reference)，引用通过一个场景图的结点关联了一个NodeComponent类，NodeComponent类定义了各种视图对象的几何和外观属性。
这种结构可以用树来描述，从根结点到任一叶子结点的路成为场景图路径(scene graph path). 每条路径都完整地描述了它的叶子结点的状态。 
 

这就是一个简单的场景图的结构，其中包括VisualUniverse  Locale  GroupNode  Leaf 等元素 

每个场景图都有单一的VirtualUniverse，后者包含一串Locale对象。一个程序可以包含多个VirtualUniverse对象，但是没有一种简单的方法实现它们相互之间的通信。 
 
写Java3D程序的通常步骤：
 1. 创建一个Canvas3D对象
 2. 创建一个VirtualUniverse对象
 3. 创建一个Locale对象，将其与VirtualUniverse相关联
 4. 构造视图分支(view branch graph)：分别创建一个View ViewPlatform PhysicalBody PhysicalEnvironment对象，将后面三个及Canvas3D与View对象关联
 5. 构造内容分支(content branch graph)
 6. 编译(compile)各个分支
 7. 将子图(subgraph)插入Locale中 
 
使用SimpleUniverse可以简化这些步骤 
 

虚线框起来的部分就是SimpleUniverse中提供的内容 
 
通过它可以将步骤简化为
 1. 创建一个Canvas3D对象
 2. 创建一个引用了之前的Canvas3D对象的SimpleUniverse类，并定制该类
 3. 构造一个内容分支，编译后插入SimpleUniverse的Locale
 
什么是编译(compile)：通过编译BranchGroup，可以将它及其祖先转换为一种更高效的实现方式。建议在最后一步中做编译。

     摘要: 问题：
有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。  阅读全文

算法课的习题
题目很简单，但是代码很漂亮

[zz]