Hackpads are smart collaborative documents. .
185 days ago
4 / 4
Unfiled. Edited by Jim Huang 185 days ago
作業系統概念和文藝復興
Jim H (本頁不再更新,移往 http://hackfoldr.org/oscar )
 
228 days ago
0 / 1
Unfiled. Edited by Jim Huang 228 days ago
Jim H [ video ] 宇宙與原子
從原子到宇宙,用距離來呈現渺小和偉大。
 
 
235 days ago
Unfiled. Edited by Yen-Ju Lin 235 days ago
  • 由於二戰以來各國政府對於當時諜報工作的保密措施造成的事實混淆,再加上圖靈的不幸生世所引來的同情,圖靈這個名字似乎擁有了一種撲朔迷離的光環。人們把很多本來不是圖靈作出的貢獻歸結在他身上,把本來很平常的貢獻過分地誇大。圖靈的光環,掩蓋了許多對這些領域做出過更加重要貢獻的人。
  • 最初破掉Enigma密碼的,其實不是英國人,而是波蘭人。波蘭人不但截獲並且仿造了德國人的Enigma機器,而且發現了其中微妙的漏洞,發明了一種用於解密的機器叫做BOMBA,以及一種手工破解的方法叫做Zygalski sheets。BOMBA可以在兩個小時之內破解掉Enigma密碼。波蘭人一聲不吭地竊聽了德國人的通信長達六年半,最後在二戰爆發前夕把這技術送給了英法盟友。
  • BOMBA的工作原理,其實就是模擬好幾個Enigma機器,“並發”運轉,這樣可以加速猜出秘鑰。最開頭這樣還行,但後來德國人改進了Enigma機器,把可選的齒輪從3個增加到了5個。5選3,有60種情況,這樣秘鑰的空間增大了60倍。理論上BOMBA只要運轉60倍多的Enigma機器,就可以破解這增大的解空間,然而那已經超出了波蘭的物資和人力。再加上德國人就要打過去,所以波蘭只好請英法盟友幫忙。
  • 圖靈最重要的貢獻,就是改進波蘭人的BOMBA,設計了一個更好的機器叫BOMBE。BOMBE比起BOMBA,其實並沒有質的飛躍,只不過BOMBE同時模擬的Enigma機器更多,轉的更快。另外它加入了一些“優化”措施,盡早排除不可行的路徑,所以速度快很多。圖靈最初的設計,要求必須能夠事先猜出很長的文本,所以基本不能用。後來Gordon Welchman發明了一種電路,叫做diagonal board,才使Bombe能夠投入實用。關於Gordon Welchman的故事,你可以參考這個BBC紀錄片。
  • 在Bombe能夠投入使用之前,有一個叫John Herivel的人,發現了一種特殊的技巧,叫做Herivel tip,這種技術在Bombe投入使用之前幾個月就已經投入實用,破解掉很多德軍的消息,立下汗馬功勞。如果Herivel tip沒有被發明,盟軍可能在1940年5月就已經戰敗,BOMBE也就根本沒機會派上用場。
  • 同時在Bletchley Park,還誕生了一台大型可編程電子計算機Colossus,它是由一個叫Tommy Flowers的工程師設計的。Colossus不是用來破解Enigma密碼的,而是用於破解Lorenz SZ-40。那是一種比Enigma還要先進的密碼機器,用於發送希特勒的最高指令。
  • 德國人後來又改進了他們的通信方式,使用了一種具有四個齒輪的Enigma機器。這大大的增加了破解的難度,普通的Bombe機器也破不了它了。後來是Harold Keen設計了一個叫做Mammoth的機器,後來加上美國海軍的幫助,制造了更快的Bombe,才得以破解。
  • 所有這些人的工作加起來,才改善了二戰的局面。波蘭人的BOMBA,已經包含了最重要的思想。圖靈的工作其實更多是量的改進,而不是質的飛躍。現在很多人喜歡跟風,片面的誇大圖靈在其中的作用,這是不對的。
  • 圖靈機比起 lambda 演算來說,其實是一個歷史的倒退。1928年,Alonzo Church 發明了lambda演算(當時他 25 歲)。Lambda 演算被設計為一個通用的計算模型,並不是為了解決某個特定的問題而誕生的。1929 年,Church 成為普林斯頓大學教授。1932 年,Church 在 Annals of Mathematics 發表了一篇論文,糾正邏輯領域裡幾個常見的問題,他的論述中用了lambda演算。1935年,Church 發表論文,使用 lambda 演算證明基本數論中存在不可解決的問題。1936 年 4 月,Church發 表了一篇兩頁紙的 “note”,指出自己 1935 年那篇論文可以推論得出,著名的Hilbert“可判定性問題”是不可解決的。
  • 圖靈的論文投稿,比 Church 最早的結論發表,晚了整整一年。編輯從來沒見過圖靈機這樣的東西,而且它紛繁復雜,遠沒有 lambda 演算來得優雅。就像所有人對圖靈機的第一印像一樣,編輯很難相信這打字機一樣的操作方式,能夠容納「所有的計算」。他無法確定圖靈的論述是否正確,只好找人幫忙。Church 恐怕是當時世界上唯一能夠驗證圖靈的論文正確性的人。所以一番好心之下,編輯寫了封信給Church,說:「這個叫圖靈的年輕人很聰明,他寫了一篇論文,使用一種機器來證明跟你一樣的結果。他會把論文寄給你。如果你發現他的結果是正確的而且有用,希望你幫助他拿到獎學金,進入 Princeton 跟你學習。」圖靈就是這樣成為了 Church 的學生 ... 1937 年,在 Church 的幫助下,圖靈的那篇論文(起名為《Computable Numbers》)
  • lambda 演算其實非常的實用,它的本質跟電子線路沒什麼兩樣。幾乎所有現實可用的程序語言,其中的語義全都可以用 lambda 演算來解釋。而圖靈機卻沒有很多現實的意義,用起來非常蹩腳,所以只能在計算理論中作為模型。另外一個更加鮮為人知的事實是:lambda 演算其實在計算理論方面也可以完全取代圖靈機,它不但可以表達所有圖靈機能表達的理論,而且能夠更加簡潔和精確地表達它們。
  • 其實圖靈機所能表達的理論,全都可以用更加簡單的 lambda 演算(或者任何一種現在流行的程序語言)來表示。圖靈機的每一個狀態,不過對應了 lambda 演算(或者某種程序語言)裡面的一個「AST 節點」,然而用 lambda 演算來表示那些計算理論,卻可以比圖靈機清晰和容易很多。
 
  • Universal Machines and Single Loops
  • Simulating Branches
  • Simulating a Turing Machine
  • The Halting Problem
 
 Halting Problem 是圖靈在 1936 年提出並證明不可解的,但哥德爾在 1931 年就證明了一個類似的定律,稱為「哥德爾不完備定理」
 
 
  • 作業系統的核心裡面也有編譯器
  • 形式來說來,bpf 就是 in-kernel virtual machine
  • tcpdump 不但可分析封包的流向,連封包的內容也可以進行「監聽」
  • $ sudo tcpdump -p -ni eth0 -d "ip and udp"
  • (000) ldh      [12]
  • (001) jeq      #0x800           jt 2    jf 5
  • (002) ldb      [23]
  • (003) jeq      #0x11            jt 4    jf 5
  • (004) ret      #65535
  • (005) ret      #0
 
  • BCC is a toolkit for creating efficient kernel tracing and manipulation programs, and includes several useful tools and examples. It makes use of eBPF (Extended Berkeley Packet Filters), a new feature that was first added to Linux 3.15.
 
 
242 days ago
0 / 11
Unfiled. Edited by 吳彥寬 242 days ago
吳彥寬 P70. static 和 local 生成 assembly 的差別,少用 static good for compiler
 
P73. How to implement inline function? Link time optimize
 
 
261 days ago
3 / 6
Unfiled. Edited by 吳彥寬 261 days ago
  • In the minimal SST version, we assume the simplest possible critical section: one that unconditionally locks interrupts upon entry and unconditionally unlocks interrupts upon exit. Such simple critical sections should never nest, because interrupts will always be unlocked upon exit from the critical section, regardless of whether they were locked or unlocked before the entry.
  • 這篇作者再講的並非是 cortex-M 系列的 NVIC,所以他在 ISR 的用法不太一樣
吳彥寬
  • 使用 priority_ceiling 的方式來實作 mutex(簡潔)
 
270 days ago
1 / 5
292 days ago
Unfiled. Edited by Roy Wei 292 days ago
cgi (Common Gatway Interface) - is a standard way for web servers to interact with executable programs installed on a server that generates web pages dynamically. (from wiki)
 
Members (588)
Ming-Hung Tsai 王平 Craig Yang Joost Shao anthony 白客 Tina Huang 黃昕暐 Jason 楊 謝政宏(Jason) Folay Chen MH  Cheng 謝汶達 Yen-Ju Lin 林宜霆 Chien-Chung Ho 辛承宣 郭承杰 Roy Wei 鄭聖文

Create a New Collection

Cancel

Move XXX to XXX


XXX will be invited to the XXX on XXX.

Cancel

Contact Support



Please check out our How-to Guide and FAQ first to see if your question is already answered! :)

If you have a feature request, please add it to this pad. Thanks!


Log in