Makefile

ref: http://tetralet.luna.com.tw/?op=ViewArticle&articleId=185

Makefile語法:

● 語法:

target: dependencies
<tab>Commands

target:  要建立的檔案
  make在編譯時，會比較檔案時間，決定是否重新建立target
  若該項目並非檔案，則為fake項目，而不會建立target檔案。(利用 .PHONY來指定fake項目)

dependencies: make根據這些項目決定是否重新編譯
  建立target前，必定先檢查的項目。可以不指定。

commands: 建立的指令
  必定以 \Tab 開頭(Tab開頭的都會被視為Shell script)
  每條command會啟動一個新的Shell，可以用; 將指令寫在同一行，或是 &&

● PHONY:

.PHONY: clean
clean:
<tab>rm *.o

  不論檔案時間必定執行，不會建立target

● 特別字元:

  @: 不顯示執行的命令
  -:   即使指令出錯，也不中斷make

.PHONY: clean
clean:
    @echo "Clean..."
    -rm *.o

● 隱性法則：

foo.o: common.h
    gcc -c foo.c

由於產生foo.o的指令就是foo.c，因此在make中可以簡化為:

foo.o: common.h

也可以用空白指令避免make利用隱性法則編譯

foo.o: common.h
<tab>

● 註解:

以#開頭即為註解

● 變數宣告:(macro)

利用=指定

target = foo
$(target): command
<tab>gcc -o $(target) foo.c

●Make參數:

可以用參數蓋過makefile裡的參數

make CFLAGS="-g -O2"

可以在make後接要重新建立的target

make clean

[OpenGL]Visual studio 環境設定與Error隨手記

1. visual studio 製作執行檔：
將debug模式調整為release模式

ref: https://sites.google.com/site/sjdsalg/materials/program/generateexe

2. 增加library和 link：

ref : https://social.msdn.microsoft.com/Forums/vstudio/en-US/a494abb8-3561-4ebe-9eb0-6f644a679862/visual-studio-2010-professional-how-to-add-include-directory-for-all-projects?forum=vcgeneral

3. Error: 'C:\Windows\SysWOW64\ntdll.dll'。找不到或無法開啟 PDB 檔案。

ref: http://vs-imaxlive.blogspot.tw/2013/06/cwindowssyswow64ntdlldll-pdb.html


4. Error: error LNK2001: unresolved external symbol __imp____glewBindBuffer

確定glew.lib在有在library中
(glew32.lib)

ref : http://stackoverflow.com/questions/16390078/build-error-when-trying-to-run-an-opengl-example-in-vc

Regular Expression-javascript

可以參考
http://www.w3schools.com/jsref/jsref_obj_regexp.asp

● /pattern/modifiers
  ○ pattern
    ◎ 運算元：
      [abc]：找到有abc字元(a或b或c)
      [^abc]：不包含abc字元
      a|b    ：找到a或b
      n+    ：找到n至少一次
      n*    ：找到n 零次或一次以上
      n?    ：找到n 零次或一次
   
   
    ◎ 特殊符號：
      \w ：word-character (a-z, A-Z, 0-9,_)
      \W：非word-character
      \d ：digit (0-9)
      \D：非digit
      \s ：空白
      \S：非空白
      \b：在開頭或結尾
      \B：不在開頭或結尾
      \n：換行符號
      \r： carriage return
      \t： tab
   

  ○ modifiers

     i: 忽略大小寫

     g: 找出所有pattern，而非只找到一個就停

     m: multiline matching，和換行有關

● javascript RegExp Object：
  ○建構：

    var res = new RegExp(pattern, modifiers);

  ○Method：

    1. exec()

    2. test()：  match時回傳true，否則回傳false

    3. toString()

e.g.

  var res = new RegExp(/[2-9]/g);
  if (res.test(input_txt.value))
  {
    alert("Sorry! " + input_txt.value + " is not accepted");
    clear_in();
    return;
  }

● replace()：  (String method)

1.  str.replace("str1", "str2")：str1被取代為str2

2.  str.replace(/pattern/modifiers, "str1")：match的pattern取代為str1

3.  str.replace(res, "str1")：利用ResExp object，將match到的pattern取代為str1

4. 利用$1可以取得()中match到的pattern  (一定要用小括號)

e.g. (將2進位數字轉換成number) 

  str.replace(/([0-1]+)/g, "parseInt(\"$1\",2)")
  eval(str)

● test($str)：  (regexp method)
  用來測試string是否包含pattern(回傳true或false)
e.g.

 var res = new RegExp(pattern, modifier);
 var str = "...";
 res.test(str);

● match： (String method)
  用來測試string 是否包含pattern(回傳match的pattern)
e.g.

 var str = "...";
 var res = str.match(/pattern/modifier);

Cryptography and Network Security-ch8

Ch8. Encipherment using modern symmetric-key cipher

5 mode to used with modern block cipher:
1.  Electronic Codebook (ECB)：每個block單獨去加密
   加密：

   解密：

2. Cipher Block Chaining (CBC)：將加密後的block和下一次的plaintext做XOR再加密(第一組需要initial vector)

加密：

解密：

3. Cipher Feedback (CFB)：對shift register加密，加密後再和plaintext做XOR，得到的ciphertext再傳到下一個shift register

 加密：

4. Output Feedback(OFB)：和CFB類似，但是傳到下一個block的是shift register加密後的temporary register

 加密：

5. Counter (CTR)：直接利用counter加密，再和plaintext做XOR
 加密：

● mode 3, 4, 5 plaintext 中一個bit計算完及可以傳送這個bit，因此類似stream cipher
● ciphertext stealing：最後兩個block可以交換順序計算，進而避免最後一個block因位數不足做padding(也就是不需要做padding)
  在ECB mode下：
    X = E_k(P_N-1)              → C_N = head_m(X)
    Y = P_N | tail_n-m(X)    → C_N-1 = E_K(Y)

  在CBC mode下：
    U = P_N-1 + C_N-2      →  X = E_k(U)     →  C_N = head_m(X)
    V = P_N | pad_n-m(0)   → Y = X + V      → C_N-1 = E_k(Y)

ref: wiki
http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_Codebook_.28ECB.29

Regular Expression-perl

文章轉
http://user.frdm.info/ckhung/b/re/rules.php
http://ind.ntou.edu.tw/~dada/cgi/Perlsynx.htm


/regular expression/expression modifier
● Modifiers：
  g: Match globally, i.e. find all occurrences. (搜尋全部)

  i: Makes the search case-insensitive. (區分大小寫)

  m: If the string has new-line characters embedded within it, the metacharacters ^ and $ will not work correctly. This modifier tells Perl to treat this line as a multiple line. (包含多行)

  o: Only compile pattern once.

  s: The character . matches any character except a new line. This modifier treats this line as a single line, which allows . to match a new-line character. 

  x: Allows white space in the expression.

● regular expression:
  ○特殊意義字元：
    \  跳脫字元
    ^ 以...為開頭
    . 除了換行的所有字串
    $ 以...為結尾
    | 或
    [] 搜尋誇號中字元
    () 括號

  ○ 字元數量關係：
    * 大於等於0次
    + 大於等於一次
    ? 0或1次
    {n} n次
    {n.} 至少n次
    {n, m} 最少n次，不超過m次

  ○ 特定字元：
    \r: carriage return(CR)
    \n: 換行
    \t: tab
    \w: 英文字母
    \W: 非英文字母
    \s white space
    \S non-white space
    \d: 數字
    \D: 非數字
    \b:  word boundary
    \B: non-word boundary
    \033: octal char
    \x1B: hex char

●

字串比對:

1. $string =~ /regular expression/expression modifier
2. if /regular expression/expression modifier

example:
(將C #define 轉換成verilog #parameter)

###read file
open($fp, "test1.c");
foreach $word (<$fp>)
{
 if ($word=~/^#define (\w+) (\d+)/)
 {
  $word =~ s/define (\w+) (\d+)\n/parameter/g;
  $word = $word . sprintf(" %s = 2'b%b\n",$1 , $2);;
  print "$word";
 }
}
close($fp);

字串取代:

s/PATTERN/REPLACEMENT/egimox

Formal language and automata - ch3

Regular language and regular grammar

Regular expression:

● definition:
 1. 元素：φ, λ, a ∈ Σ 為Regular expression
 2. 運算元：若r₁, r₂為Regular expression
    r₁ + r₂  (union)
    r₁ ⋅ r₂  (concatenation)
    r₁*       (star-closure)
   (r₁)
  均為regular expression
3. 根據有限次數的1和2造出的字串均為regular expression

● language associated with regular expression:

 1. φ is a regular expression {}  (empty set)

 2. λ is a regular expression {λ}

 3. for a ∈ Σ, a is a regular expression denote  {a}

 4. L(r₁ + r₂) = L(r₁) ∪ L(r₂)
 5. L(r₁ ⋅ r₂) = L(r₁)L(r₂)
 6. L((r₁)) = L(r₁)
 7. L(r₁*) = (L(r₁))*

● operation priority:

  star closure > concatenation > union

Regular expression and regular language:

Regular expression -> Regular language

● 所有regular expression 定義的都可以畫成nfa
1. nfa accept φ

2. nfa accept {λ}

3. nfa accept {a}

4. nfa accept L(r₁ + r₂)

5. nfa accept L(r₁ ‧ r₂)

6. nfa accept L((r₁))：直接去掉括號
7. nfa accept (L(r₁))*

Regular language-> Regular expression

● Generalized transition graph(GTG)：一個label為regular expression的transition graph

● nfa轉成complete GTG：將所有沒有連接的edge連上並標上φ
 e.g.

轉換成

● 2 state GTG轉換成regular expression：

r = r₁r₂ (r₄ + r₃r₁*r₂)*

● 3 state(或以上) complete GTG轉換成regular expression：將state減少，直到剩兩個state（initial state和final state）
每次減少state時，考慮將會經過的state，將它加到graph的其他路徑上
e.g.

reduce成：

○完整procedure：
  1. 將nfa轉換成單一final state的GTG，並使它complete
  2. 若GTG state為2，直接代公式
  3. 若GTG state為3，選擇一個要刪除的state(qi)(非final 也非initial的state)
  對於另外兩個state，考慮經過qi的路線
   r1 + r2r3*r4
(均為這種type)
 4. 若GTG大於4，選擇要刪除的state，對所有state均套用 r1 + r2r3*r4找關係
     降為3個state後，再用step3

Regular grammar:

● definition：
 ○left-linear grammar：每次production左側最多只出現1個variable，variable為最左側的symbol
  e.g.：
    A →Bx
    A →x
 ○right-linear grammar：每次production左側最多只出現1個variable，variable為最右側的symbol

 ○regular grammar：left-linear 或 right-linear

 ○linear grammar：每次production左側最多只出現1個variable

● right-linear grammar 轉換成 regular language(nfa)：
  variable → state
  alphabet → state轉換的label

●  regular language轉換成 right-linear grammar：
  δ(q_i, a_j) = q_k 轉換成 q_i → a_jq_k
  (若 q_k 為final state：則轉換成q_k →λ)

● regular language轉換成 left-linear grammar：
  略

● regular expression <=> dfa or nfa <=> regular grammar

  為等價，可以互相轉換

Formal language and automata - ch2

Ch2. Finite automata

Deterministic Finite Accepter(dfa)

● deterministic accepter
  ○ definition:
    M = (Q, Σ, δ, q₀, F)
      Q: set of internal state
      Σ: set of symbol (input alphabet)
      δ:  Q × Σ → Q transition function   (表示state的轉換)
        e.g.  
         δ(q₀, 0) = q₁
         即在q₀ state 、當input alphbet為0時，移動到state q₁
      q₀ ∈ Q: initial state
      F: set of final state

     每一步都要清楚定義(每個state都要考慮所有alphbet的可能)

  ○ operate:

     1. 一開始在initial state(q₀)
     2. 每次移動(move)，讀入一個input alphabet，根據讀到的input和當前的state，移動到下一個state
     3. 讀完所有input時，若在final state則為accept，否則為not accept

  ○ transition graph:

    state: 以圓圈表示
    transition function: 以箭頭表示
    input: 箭頭上的label
    initial state: 一個圓圈有一個箭頭沒有前一個state
    final state: 雙圓圈

      ※ transition graph 可以表示所有的dfa
    e.g.
      M = ({q₀, q₁, q₂}, {0, 1}, δ, q₀, {q₁})
     with transition function δ:
        δ(q₀, 0) = q_0,   δ(q₀, 1) = q₁
        δ(q₁, 0) = q_0,   δ(q₁, 1) = q₂
        δ(q₂, 0) = q_2,   δ(q₂, 1) = q₁

  ○ extended transition function:
     δ(q₀, a) = q₁
     δ(q₁, b) = q₂
⇒ δ*(q₀, ab) = q₂

● Language and dfa:

   dfa可以接受的language即為所有dfa產生的字串的集合

   L(M) = {w ∈ Σ*: δ*(q₀, w) ∈ F}

  Language L is regular language if and only if there exist a dfa M使得
    L = L(M)

Nondeterministic finite accepter (nfa)

● definition:
    M = (Q, Σ, δ, q₀, F)
      和dfa類似，除了transion function不同:
      δ:  Q × (Σ ∪ λ) → 2^Q transition function   (表示state的轉換)

● 和dfa不同處:
          1. transition function 對應出來為一個set，而不是單一state (next state有多種可能性)
              e.g. δ(q₀, a) = {q₀, q₁}  

          2. transition function 第二的element可為λ                              (可不消耗alphabet切換到下一個state)

          3.  δ(q₀, a) 可為empty                                                               (transition 沒有定義)

          4. 可接受的string為：只要可以停在final state的string
● extended transition function: same as dfa

● transition graph:
 

                δ*(q₁, a) = {q₀, q₁, q₂}

                δ*(q₂, λ) = {q₀, q₂}

                δ*(q₂, a) = {q₀, q₁, q₂}

                note: 每個state本身都有一個λ cycle  (即透過λ 可在原本的state)

● language:

   nfa可以接受的language即為所有nfa產生的字串的集合

   L(M) = {w ∈ Σ*: δ*(q₀, w)  ∩ F ≠ φ}

  即w可以走到final state (有一個state即可)

Equivalence of deterministic and nondeterministic finite accepter

● equivalence of finite accepter:
   two finite accepter are same

   L(M₁) = L(M₂)

  if both accept same language

● equivalence of nfa and dfa:

    dfa 為一種nfa

    nfa 可以轉為dfa

      利用powerset ，新的graph的vertex為nfa的powerset

  ○ nfa轉換為 dfa:
          1. 創造一個新的graph G從 {q₀} 開始
          2. 對於所有G上的vertex {q_i, q_j, ..., q_l}，和一個 a ∈ Σ
              找出所有從 {qi, qj, ..., ,ql} 經過a 可以到的vertex，並標為一個新的state
          3. 重複2直到沒有新的vertex
              (必定結束，因為新的graph最多2^Q |Σ| edge)

          4. 標上final state: 任何有包含原本final state的vertex在新的graph均為final state
          5. 若 λ 也accept，則q₀也是final state

        e.g. 

           nfa

            第一步：

            第二步：

            完成所有vertex：

            完成圖：

Reduce the number of state

● indistinguishable/ distinguishable state:
   two state are indistinguishable if
       δ(p, w) ∈ F implies δ(q, w) ∈ F
   and
       δ(p, w) ∉ F implies δ(q, w) ∉ F

    for all w ∈ Σ*

● reducing produce :

  ○ produce mark:

     1. remove 所有無法到達的state

     2. 對所有state進行區分，分成final state和非final state (兩者為distinguishable，同set裡為distinguishable)

     3. 對所有indistinguishable state區分：

         若有 a ∈ Σ 使得兩個state p, q

            δ(p, a) = p_a

            δ(q, a) = q_a

       且p_a 和q_a為distinguishable，則p q為distinguishable

即
     對於所有字母a
     若p q經過接受a產生的state不再同一個set(distinguishable)，則p q不是同個state (distinguishable)

     4. 重複3直到沒有新的state被區分

  ○ produce reduce: 利用procedure mark找出所有相同的state，並根據相同state建立新的dfa

     1. 找出相同state: {q_i, q_j,...}，在新的dfa M' 中視為一個state

     2. 對於原本的dfa所有transition rule δ(p, a) ＝ q: 找出在M'中，p 和q 所在的state p' 和q'
         建立新的transition: δ(p', a) = q'

     3. 重複2直到原本的的dfa所有transition rule完成

     4. 標示initial state: M'中，包含initial state 的state即為initial state

     5. 標示final state: M'中，包含原本dfa final state的state均為final state