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.aygfsteel.com/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.aygfsteel.com/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]