你所知道的最 Hack 的解決問題的過程是？

01-22

偉大的幾乎唯一性的 Hash Hack：

基於 Hash 的病毒雲查殺

基於 Hash 的第三方 Flash 通用組件的 XSS 漏洞檢測

基於 Hash 的文件篡改對比

基於無數 Hash 組成的彩虹表的密碼碰撞破解

...

@Yong He 曾經跟我講過，他當年在浙大的圖形實驗室打工的時候，看見侯啟明同學通過debug他自己的shader編譯器來看別人寫的shader到底掛在了什麼地方。

不過其實所有不包含debugger的編譯器都得這麼干，我也干過類似的事情。當然不同的地方在於，侯啟明寫的代碼實在太ACM，實驗室只有他一個人能搞定。

這是個傳奇的故事！做過 ACM 的人大概都知道：

Quake-III Arena (雷神之錘3)是90年代的經典遊戲之一。該系列的遊戲不但畫面和內容不錯，而且即使計算機配置低，也能極其流暢地運行。這要歸功於它3D引擎的開發者約翰-卡馬克（John Carmack）。事實上早在90年代初DOS時代，只要能在PC上搞個小動畫都能讓人驚嘆一番的時候，John Carmack就推出了石破天驚的Castle Wolfstein, 然後再接再勵，doom, doomII, Quake...每次都把3-D技術推到極致。他的3D引擎代碼資極度高效，幾乎是在壓榨PC機的每條運算指令。當初MS的Direct3D也得聽取他的意見，修改了不少API。
最近，QUAKE的開發商ID SOFTWARE 遵守GPL協議，公開了QUAKE-III的原代碼，讓世人有幸目睹Carmack傳奇的3D引擎的原碼。這是QUAKE-III原代碼的下載地址：
http://www.fileshack.com/file.x?fid=7547
(下面是官方的下載網址，搜索「quake3-1.32b-source.zip」可以找到一大堆中文網頁的。ftp://ftp.idsoftware.com/idstuff/source/quake3-1.32b-source.zip)
我們知道，越底層的函數，調用越頻繁。3D引擎歸根到底還是數學運算。那麼找到最底層的數學運算函數（在game/code/q_math.c），必然是精心編寫的。裡面有很多有趣的函數，很多都令人驚奇，估計我們幾年時間都學不完。在game/code/q_math.c里發現了這樣一段代碼。它的作用是將一個數開平方並取倒，經測試這段代碼比(float)(1.0/sqrt(x))快4倍：

float Q_rsqrt( float number ) { long i; float x2, y; const float threehalfs = 1.5F;
x2 = number * 0.5F; y = number; i = * ( long * ) y; // evil floating point bit level hacking i = 0x5f3759df - ( i &>&> 1 ); // what the fuck? y = * ( float * ) i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM #ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE? #endif #endif return y; }
函數返回1/sqrt(x)，這個函數在圖像處理中比sqrt(x)更有用。
注意到這個函數只用了一次疊代！（其實就是根本沒用疊代，直接運算）。編譯，實驗，這個函數不僅工作的很好，而且比標準的sqrt()函數快4倍！要知道，編譯器自帶的函數，可是經過嚴格仔細的彙編優化的啊！
這個簡潔的函數，最核心，也是最讓人費解的，就是標註了「what the fuck?」的一句
i = 0x5f3759df - ( i &>&> 1 );
再加上y = y * ( threehalfs - ( x2 * y * y ) );
兩句話就完成了開方運算！而且注意到，核心那句是定點移位運算，速度極快！特別在很多沒有乘法指令的RISC結構CPU上，這樣做是極其高效的。
演算法的原理其實不複雜,就是牛頓迭代法,用x-f(x)/f"(x)來不斷的逼近f(x)=a的根。
沒錯，一般的求平方根都是這麼循環迭代算的但是卡馬克(quake3作者)真正牛B的地方是他選擇了一個神秘的常數0x5f3759df 來計算那個猜測值，就是我們加註釋的那一行，那一行算出的值非常接近1/sqrt(n)，這樣我們只需要2次牛頓迭代就可以達到我們所需要的精度。好吧如果這個還不算NB,接著看:
普渡大學的數學家Chris Lomont看了以後覺得有趣，決定要研究一下卡馬克弄出來的這個猜測值有什麼奧秘。Lomont也是個牛人，在精心研究之後從理論上也推導出一個最佳猜測值，和卡馬克的數字非常接近, 0x5f37642f。卡馬克真牛，他是外星人嗎？
傳奇並沒有在這裡結束。Lomont計算出結果以後非常滿意，於是拿自己計算出的起始值和卡馬克的神秘數字做比賽，看看誰的數字能夠更快更精確的求得平方根。結果是卡馬克贏了... 誰也不知道卡馬克是怎麼找到這個數字的。

最後Lomont怒了，採用暴力方法一個數字一個數字試過來，終於找到一個比卡馬克數字要好上那麼一丁點的數字，雖然實際上這兩個數字所產生的結果非常近似，這個暴力得出的數字是0x5f375a86。
Lomont為此寫下一篇論文，"Fast Inverse Square Root"。論文下載地址：
http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf
http://www.matrix67.com/data/InvSqrt.pdf
參考：&&
最後，給出最精簡的1/sqrt()函數：
float InvSqrt(float x) { float xhalf = 0.5f*x; int i = *(int*)x; // get bits for floating VALUE i = 0x5f375a86- (i&>&>1); // gives initial guess y0 x = *(float*)i; // convert bits BACK to float x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy return x; }
大家可以嘗試在PC機、51、AVR、430、ARM、上面編譯並實驗，驚訝一下它的工作效率。
前兩天有一則新聞，大意是說 Ryszard Sommefeldt 很久以前看到這麼樣的一段 code (可能出自 Quake III 的 source code)：
float InvSqrt (float x) { float xhalf = 0.5f*x; int i = *(int*)x; i = 0x5f3759df - (i&>&>1); x = *(float*)i; x = x*(1.5f - xhalf*x*x); return x; }
他一看之下驚為天人，想要拜見這位前輩高人，但是一路追尋下去卻一直找不到人；同時間也有其他人在找，雖然也沒找到出處，但是 Chris Lomont 寫了一篇論文 (in PDF) 解析這段 code 的演算法 (用的是 Newton』s Method，牛頓法；比較重要的是後半段講到怎麼找出神奇的 0x5f3759df 的)。
PS. 這個 function 之所以重要，是因為求開根號倒數這個動作在 3D 運算 (向量運算的部份) 裡面常常會用到，如果你用最原始的 sqrt() 然後再倒數的話，速度比上面的這個版本大概慢了四倍吧… XD

PS2. 在他們追尋的過程中，有人提到一份叫做 MIT HACKMEM 的文件，這是 1970 年代的 MIT 強者們做的一些筆記 (hack memo)，大部份是 algorithm，有些 code 是 PDP-10 asm 寫的，另外有少數是 C code (有人整理了一份列表)

copying pasting from StackOverflow

黑客精神就是：別人做過的東西，就不要跟2B一樣再做一遍

圖是不知道偷哪的，誰的版權告訴我，我刪

－－－－－－－－－－－－－－－－－－－

有一個同學，上C語言這門課的時候，教授把標準答案的binary放出來了，只要你寫的程序test的結果跟這個binary一樣，作業就滿分。同學直接反編譯了。。。

CS的學生一般不要幹這種事。好好作弊實際上比好好讀書要難的多，上面這位同學是職業的，他知道自己在幹什麼。

大一參加個啥比賽，提交了報告後發現報告裡面有錯別字，然而平台並沒有修改功能，只能把平台日了然後自己把新報告覆蓋上去..

悄悄地修改了已經掛掉的那門課的成績。

然後被學校發現了。

實在不是師兄捉急，而是老師手裡有成績備份=.=!