struct sk_buff

Linux kernel 的封包用 struct sk_buff 管理，程式碼常用 skb 表示

• 定義：include/linux/skbuff.h
• 取得：alloc_skb() 或 dev_alloc_skb()
• 釋出：kfree_skb() 或 dev_kfree_skb()

一些欄位

• struct sk_buff *next, *prev
• head、data、tail、end：head 和 end 分別指到整個資料區塊的開頭和結束，其中有一段是封包的部份，用 data 和 tail 分別指到封包的開頭和結束。skb_pull(len) 將開頭後移 len。
• len
• transport_header (h)、network_header (nh)、mac_header (mac)：三個 union 經過這些層時分別指到不同協定層的信頭，分別用 skb_transport_header(skb)、skb_network_header(skb) 及 skb_mac_header(skb) 取得這些指標。
• pkt_type 封包類型：PACKET_BROADCAST、PACKET_MULTICAST、PACKET_OTHERHOST、PACKET_LOOPBCK (針對位址決定？什麼位址？)
• prev、next、list
• sk
• ktime_t tstamp：收到封包的時間。net_enable_timestamp() must be called in order to get values
• struct net_device *dev, *rx_dev
• struct dst_entry *dst：系統決定的路由，有兩個重要的函數指標：
• int (*input)(struct sk_buff*)：可指定為 ip_local_deliver, ip_forward, ip_mr_input, ip_error 或 dst_discard_in
• int (*output)(struct sk_buff*)：可指定為 ip_output, ip_mc_output, ip_rt_bug, 或 dst_discard_out.
一般只有一個 dst_entry。當在 IPSec 時是一個 linked list，只用最後一個來路由，其它的作為 IPSec transformers，flag 會設 DST_NOHASH。
• data_len
• mac_len
• __be16 protocol：1536 以上的 EtherType、或 ETH_P_802_3、ETH_P_802_2 等其它 ETH_P_xxx 協定。

skb_shared()

• 檢查 sk_buff 是毋是共有，就是看伊 reference count (users) 不是 1。
• kfree_skb() 會將 reference count 減 1，在 reference count 是 0 時才會真正釋出。
• 通常一個封包使用者用 skb_shared() 檢查是否 shared，如果是的話用 skb_clone() 複製一份，並用 kfree_skb() 將原本的 reference count 減 1。這些動作可用 skb_share_check() 完成。
• 什麼情況需要 skb_shared() 檢查？
• skb_clone() 是複製資料結構，封包資料仍是共用的。如果封包資料也要複製一份，則用 skb_copy()；如果只是部份封包資料要複製一份，則用 pskb_copy()。
• 大部分 reference count 是 1，什麼時候會大於 1 呢？

skb_clone()

參考來源

1. Linux Kernel Networking by Rami Rosen at Haifux, August 2007
2. Linux Kernel Source Codes

最後更新 20200721

字串複製

C 標準函式庫的字串是以 0 為結尾的 char 陣列，字串長度不計結尾 0，實際儲存空間至少要字串長度加 1。

函數	字串結尾？	回傳值	說明
strcpy()	必定	結果字串	事先確保結果空間要足夠。
strncpy()	未必		限定結果最大長度。
strlcpy()	必定		libbsd，非 POSIX，限定結果最大長度。
memcpy()	必定		事先需要知道字串長度或最大長度。
memmove()	必定		同 memcpy()，並允許記憶體空間可以重複。
strdup()	必定	動態取得的結果字串
strndup()			限定結果最大長度。
strdupa()			函式結束時結果空間自動釋出。
strndupa()			函式結束時結果空間自動釋出，限定結果最大長度。
sprintf() vsprintf()	必定	字串長度	類似 strcpy()。
snprintf() vsnprintf()			限定結果最大長度。類似 strlcpy()。
asprintf() vasprintf()			結果空間動態取得，類似 strdup()。

最簡單的字串複製，莫過於

char *strcpy(char *dst, const char *src)

複製 src 字串到 dst，回傳 dst。其內部基本作法是從位址 src 開始一個 byte 一個 byte 複製到 dst 開始的記憶體空間，直到複製的資料內容是 0 結束。必須確保 src 字串有結尾 0，以及 dst 開始有足夠的記憶體空間，至少是 src 字串長度加 1。另外一點就是 src 跟 dst 記憶體空間避免重複 (dst 指標比 src 指標小應該沒關係，但不能保證)。

如果 src 字串可能大於 dst 可容納的空間的話，就要限制最大的複製大小。

char *strncpy(char *dst, const char *src, size_t n)

跟 strcpy() 一樣，但多了檢查最多複製 n bytes。要注意的是可能沒複製到字串結尾 0，這樣的話 dst 字串就沒結尾。如果要確保 dst 有結尾，dst 最後要多預留一個 byte 並且放 0。

libbsd 提供 (來自 BSD，非 POSIX 標準) 跟上述 snprintf() 作用一樣，但樣子像 strncpy()：

size_t strlcpy(char *dst, const char *src, size_t n)

一樣最多從 src 複製 n-1 byte，回傳值為複製的 byte 數。如果回傳值 >= n，則有截斷情形。

sprintf()、snprintf()、vsprintf()、或 vsnprintf() 是複製成某種格式的字串，格式也可以包含字串。這些會自動確保複製結果的字串有結尾 0，他們的回傳值是不含結尾 0 總共複製了幾個 byte。其中 snprintf() 跟 vsnprintf() 有限制含結尾 0 總共複製的大小。

int snprintf(dst, n, "%s", src)

跟 strncpy() 的作用的相像，但最多只會從 src 複製 n-1 bytes 到 dst，回傳值 ≥ n，就表示 src 後面有截斷沒複製到。

如果已經知道 src 字串的長度，其實未必需要使用字串複製的函數，直接使用記憶體複製，複製過程不用檢查字串結尾 0。

void *memcpy(void *dst, const void *src, size_t n)

跟 strncpy() 很像，但純粹是從 src 複製 n bytes 到 dst。如果 n 放 src 字串長度加 1，剛好就是你要的。

如果 src 跟 dst 記憶體空間有重複，可以使用

void *memmove(void *dst, const void *src, size_t n)

標準 C 的字串是以 0 為結尾，但事實上字串也可以用別的方式表示，常見的另一種方式是除了字串本身外，也紀錄字串長度。這樣很容易得知字串長度，不需要一個 byte 一個 byte 查到結尾 0 才知道字串長度。
int snprintf(dst, size, "%.*s", src_len, src)

• 格式裡用「%.*s」：「*」對應的參數表示複製的字串長度，不管來源字串有無結尾 0

其它相關

• void *memccpy(void *dst, const void *src, int c, size_t n)
• void bcopy(const void *src, void *dst, size_t n) obsolete
• stpcpy
• stpncpy
• strdup(const char *src)
• strndup()
• strdupa()
• strndupa()
• wcscpy
• wcsncpy
• strcat
• strncat
• string operations
  => strXXX() 系列 (以及 index, rindex)
  byte string operations
  => memXXX() 系列
  => bXXX() 系列 obsolete
   

運算子順序

運算子順序 (Operator Precedence) 除了先乘除後加減、由左到右外，還有許多運算子：

運算子	說明
()、[]、->、.	函數呼叫, array subscripting、membership 存取
~、!、++、--、+、-、*、&、(type)、sizeof	Unary 運算，右到左
*、/、%
+、-
<<、>>
>、<、>=、<=
==、!=
&	位元邏輯運算
^
|
&&	邏輯運算
||
?:	右到左
=、+=、-=、/=、%=、&=、^=、|=、<<=、>>=、、	指派運算，右到左
,

相不相等優先序比位元邏輯運算高

參考來源

1. http://www.gnu.org/software/gnu-c-manual/gnu-c-manual.html#Operator-Precedence 
2. http://pydoing.blogspot.tw/2010/06/c-operator.html

printf()

格式化輸出：printf() 這類函數有一個 format 參數用來表示輸出的字串格式。

#include <stdio.h>

int printf(const char *format, ...);
int fprintf(FILE *stream, const char *format, ...);
int dprintf(int fd, const char *format, ...);
int sprintf(char *str, const char *format, ...);
int snprintf(char *str, size_t size, const char *format, ...);
int asprintf(char **strp, const char *format, ...);

#include <stdarg.h>

int vprintf(const char *format, va_list ap);
int vfprintf(FILE *stream, const char *format, va_list ap);
int vdprintf(int fd, const char *format, va_list ap);
int vsprintf(char *str, const char *format, va_list ap);
int vsnprintf(char *str, size_t size, const char *format, va_list ap);
int vasprintf(char **strp, const char *format, va_list ap);

成功回傳打算寫入的字串長度，失敗回傳負值。如果 snprintf() 和 vsnprintf() 回傳值 ≥ size，表示有截短。glibc 從 v2.1 開始符合以上 C99 標準，之前截短回傳 -1。

基本型是 printf 輸出到 stdout，前面加

• f：列印到 FILE。
• d：列印到 fd。
• s：列印到 str 字串暫存區。
• sn：列印到 str 字串暫存區，含結尾 0 最多寫入長度 size。
  
• as：列印到自動配置的字串暫存區，從提供的 strp 回傳。最後不用需 free(*strp) 釋出。
  
• v：參數採用 va_list。

format 格式字串

格式字串內容	printf() 系列	scanf() 系列
% 開頭的轉換規範	printf()	scanf()
空白字元集 (space、tab、newline 等)	直接輸出	比對 0 個以上的空白字元集
一般字元		直接比對

輸出格式由 format 字串決定，包含兩種物件 -- 直接輸出的一般字元、以及轉換規範。每個轉換規範 (conversion specification) 通常轉換一個參數，格式：

%[flags][最小寬度][.精確度][資料類型]轉換字元

對 % 開始到轉換字元，中央會使有 flags、width (最小寬度)、precision (精確度)、和 length (資料類型)。其中最小寬度和精確度是「非 0」的數字，或用「*」來取用下個參數 (須為數字)。預設按照順序每個「*」及轉換字元取用一個參數。UNIX 規範也可以用「%m$」和「*m$」來取代 % 和 *，明確指定使用第 m 個參數，但 C99 標準不支援。如果有用 $，所有需要取用參數的都要用，且使用的參數不能有 gap。

轉換字元 (conversion specifier)

字元	輸出	. 精確度
d, i	有號十進位	位數
u	無號十進位	位數
o	無號八進位	位數
x, X	無號十六進位	位數
c	字元
s	字串	最長長度
f, F	[-]mmm.dddddd	d 數目
e, E	[-]m.dddddde±xx 或 [-]m.ddddddE±xx	d 數目
g, G	較小的數使用 e 或 E，否則用 f	significant 位數
p	指標值
n	目前為止輸出的字數
%	印「%」

flags

• -：向左對齊
• +：數字都印 +- 符號
• 空白字元：如果要印的第一個字元不是符號，多插入一個空白字元。
• 0：數字前面補 0。
• #：數字轉換成 alternate form，可看出是幾進位或是不是浮點。
• o：前置 0
• x 或 X：前置 0x 或 0X
• e、E、f、g、或 G 保留小數點
• g 或 G：保留小數點，且不移除尾部的 0。
• '：十進位轉換 (i, d, u, f, F, g, G) 輸出，每千位依據 locale 隔開 (見 setlocale())。
• I：十進位轉換 (i, d, u) 輸出使用 locale 語文。

資料類型 (length modifier) 指示對應的參數

• hh：signed char 或 unsigned char
• h：short 或 unsigned short
• l：long 或 unsigned long
• ll：long long 或 unsigned long long
• L：long double
• j：intmax_t 或 uintmax_t
• z：size_t 或 ssize_t
• t：ptrdiff_t

void printf(const char *fmt, ...)
{
    va_list ap;

    va_start(ap, fmt);
    vprintf(fmt, ap);
    va_end(ap);
}

參考：

1. The C Programming Language, Brian W. Kernighan & Dennis M. Ritchie
2. man 3 printf
3. format string attack：https://bamboofox.cs.nctu.edu.tw/uploads/material/attachment/11/format_string_exploit.pdf
4. stdout 預設是 line buffered，換行時才會輸出。但有些方式可以馬上輸出：
• fflush(stdout)
• setbuf(stdout, NULL)
• setvbuf(stdout, NULL, _IONBF, 0);

• scanf() 系列標準函數
  

JTAG

JTAG (Joint Test Action Group) 是一個在 1985 年成立的電子工業協會，致力於發展產品製造後如何驗證設計及測試印刷電路板接線的方法。在 1990 年結果寫成 IEEE Standard 1149.1-1990，標題是「Standard Test Access Port and Boundary-Scan Architecture」，但坊間仍俗稱 JTAG。JTAG 除了可用來作 Boundary-Scan Test，也就是測試電路板上元件間的接線是否正確外，常常擴充提供許多廠商自定的功能，例如燒錄、In-Circuit Emulation 等。

JTAG 存取界面稱為 TAP (Test Access Port)，包括跟外部通訊的序列訊號接腳、內部的狀態機器及暫存器。

圖來自 Spartan-6 FPGA Configuration User Guide

TAP 接腳有 TCK、TMS、TDI、TDO 四個訊號，透過控制 TAP 狀態機器來存取 TAP 暫存器。所有 JTAG 功能都透過這四個訊號完成。

• TCK (Test Clock) 輸入：TAP 的運作時脈。
• TMS (Test Mode Select) 輸入：選擇下個 TAP 狀態轉移，TCK 上升緣動作。TAP 採用序列狀態機器，下個狀態只依據 TMS 只有 0 跟 1 兩種選擇。TMS 持續輸入 1 可回復重置狀態，一般會有內部 pull-up 提供邏輯 1 輸入。
• TDI (Test Data In) 輸入：序列位移進 TAP 暫存器，TCK 上升緣動作。
• TDO (Test Data Out) 輸出：序列位移出 TAP 暫存器，在 TCK 下降緣動作，且只有在位移輸出暫存器時才驅動輸出。

另外可能還有 TRST (Test Reset) 接腳，強制 TAP 重置，但 TMS 持續輸入 1 也可以重置，所以不是必要的。

圖來自 Spartan-6 FPGA Configuration User Guide

多個 JTAG 可以串接使用，其中 TCK 跟 TMS 是共用，而 TDI 跟 TDO 則是串接。

TAP 暫存器會有一個指令暫存器 (Instruction Register, IR)，其它為資料暫存器 (Data Register, DR)。DR 數目不一定，可能有 BYPASS、IDCODE、EXTEST、INTEST 等，有些是 IEEE 定義的，其它則廠商自己定義。TAP 狀態跟 IR 的內容，決定 TDI 輸入到及 TDO 輸出自哪個暫存器。

• IR：至少 2-bit，由廠商決定長度，不同指令選擇不同的資料暫存器，而有不同的功能。
• BYPASS：IEEE Std 1149.1 定義的標準暫存器，只有 1-bit，作為多個 JTAG 元件串接時，把 TDI 跟 TDO 以序列方式串起來，來 bypass 特定元件，在 CAPTURE-DR 時會初始化為 0。
• IDCODE：大部分 JTAG 相容元件都有 32-bit IDCODE，儲存元件特定的識別碼，可看出製造商及元件型號。
• Bound-Scan Register (BSR)
• EXTEST, INTEST, SAMPLE, USERCODE, and HIGHZ

JTAG 相容元件用 Boundary Scan Description Language (BSDL) 檔案定義其功能，BSDL 用 VHDL 語言撰寫，描述元件的接腳及 boundary-scan 暫存器。

狀態機器

圖來自 Spartan-6 FPGA Configuration User Guide

TAP 有 16 種狀態，由 TCK 時脈的 rising edge 看 TMS 的 0 或 1 決定狀態的轉換。主要有兩種路徑分別是要對 IR 或 DR 作內容移位。IR 在實作上可能分成兩部份，一是解碼使用的 IR，另一是位移的時候用。DR 未必有這樣的設計。

• Test-Logic-Reset (TLR)：測試邏輯於重置狀態，也就是測試邏輯電路是關閉的，此時元件可正常使用。不論目前在哪個狀態，只要 5 次 TMS 1 就會進入 Test-Logic-Reset 狀態。持續 1 維持在 Test-Logig-Reset，0 離開。
• Run-Test/Idle (RTI)：在特定的指令下進入並停留在此狀態來執行測試 (Run-Test)，直到 TMS 接腳為 1 結束。其它指令則為閒置 (Idle)。
• Select-DR-Scan：選擇是否進入 DR 路徑。
• Select-IR-Scan：選擇是否進入 IR 路徑。
• Capture-IR 或 Capture-DR：擷取 IR 或 DR 作為 TDO 輸出用。
• IR 在實作上可能分成兩部份，一是寫入的版本作為解碼使用，另一是位移的版本。Capture-IR 時將位移的版本載入固定值，且這個固定值最後 2-bit 為 01，不是寫入的 IR。之後 Update-IR 時，會將位移的版本平行載入作為寫入的版本。
• DR 未必有這樣的設計。Capture-DR 則擷取 IR 所選擇 DR 作為輸出，實際上可能沒區分出專作位移的版本，而沒有實際擷取的動作。
• Shift-IR 或 Shift-DR：此時暫存器跟接腳 TDI 及 TDO 串起來進行內容位移。TMS 為 0 時持續進行位移，為 1 時結束。
• Exit1-IR 或 Exit1-DR：控制是要進入 Pause-IR (Pause-DR) 還是 Update-IR (Update-DR)。
• Pause-IR 或 Pause-DR：暫停位移。
• Exit2-DR 或 Exit2-DR：控制是要進入 Shift-IR (Shift-DR)，還是進入 Update-IR (Update-DR)。
• Update-IR 或 Update-DR：在 TCK falling edge 更新 IR 或 DR。

範例：讀取 IDCODE，首先 IR 寫入指令 IDCODE，然後在從 DR 讀出 IDCODE

TAP state	TDI	TMS	#TCK	說明
any
	x	1	5	回復到重置狀態
Test-Logic-Reset
	x	0	1
Run-Test/Idle
	x	1	1
Select-DR-Scan
	x	1	1
Select-IR-Scan
	x	0	1
Capture-IR
	x	0	1
Shift-IR
	01001	0	5	從 LSB 開始位移 IDCODE 指令
Shift-IR
	0	1	1	位移 IDCODE 指令最後 MSB，並離開位移狀態
Exit1-IR
	x	1	1	更新指令為 IDCODE = 0x09
Update-IR
	x	1	1
Select-DR-Scan
	x	0	1
Capture-DR
	x	0	1
Shift-DR
	?	0	31	TDO 從 LSB 開始位移出 IDCODE
Shift-DR
	?	1	1	TDO 位移出 IDCODE 最後 bit，並離開位移狀態
Exit1-DR
	x	1	1
Update-DR
	x	0	1	回到 Run-Test/Idle 完成動作
Run-Test/Idle

如果多個元件串接時，由於 TMS 是接在一起的，所以每個元件的 TAP 停留的狀態是一致的，只差在讀寫暫存器所需要位移的長度變長了

1. IR 寫入指令 IDCODE 時，需要依照跟所有元件串接的順序排指令碼，目標元件填 IDCODE 指令碼，其它元件則填 BYPASS 指令碼。BYPASS 指令碼都是 1，只是不同元件 IR 的長度會有所不同。
2. DR 讀出 IDCODE 時，需要把讀到的 BYPASS 過濾掉，每個 BYPASS 佔 1-bit。

JTAG 雖然有 16 種狀態，除了重置及 Run-Test 外，其它都是為了存取 IR 及 DR。JTAG 訊號很像 SPI，多了 TMS 來轉移狀態，多了 IR/DR 可無限擴充可能的功能。

參考來源：

1. https://en.wikipedia.org/wiki/Joint_Test_Action_Group
2. Spartan-6 FPGA Configuration User Guide

DTMF Decoder: HM9270D

HM9270D 是 DTMF 解碼器，將 16 種 DTMF 組合轉換成 4-bit 碼。

1. IN+：內部 Op Amp 差動輸入
2. IN-：內部 Op Amp 差動輸入
3. GS：內部 Op Amp 差動輸出，作為回授使用。
4. V_REF：V_DD/2 電壓輸出。
5. INH：接 High 不偵測 A/B/C/D DTMF。內部 pull-down
6. PWDN
7. OSC1
8. OSC2
9. V_SS：Ground。
10. TOE (輸入)：high 時輸出 Q1 ~ Q4 ，否則 tri-state。
11. Q1 (data 輸出)
12. Q2 (data 輸出)
13. Q3 (data 輸出)
14. Q4 (data 輸出)
15. StD (Delayed Steering 輸出)：high 時，表示有新的 Q1 ~ Q4
    
16. ESt (Early Steering 輸出)：偵測到 tone 立即輸出 high，否則立即輸出 low。
17. St/GT (Steering 輸入及 Guard Time 輸出)：包括 St 及 GT 兩種功能。St 是偵測電壓，如果 < V_TSt 表示 DTMF 碼還在確認中。如果一超過 V_TSt 表示已確認，允許更新內部 Q1~Q4 紀錄，此時 GT 輸出 high 直到 tone 結束。St/GT 通常接 RC 電路，V_TSt 是 2.35V。
18. V_DD：5V 電源。

參考來源：

1. http://www.teleic.com/PDF/EM9270.PDF

其它相關

1. MT8870：DTMF 解碼
2. HT9170：DTMF 解碼
3. HT9172：DTMF 解碼
4. MT8880：DTMF 解編碼
5. DT210：DTMF 解編碼
6. DTMF V1：DTMF 解編碼
7. HT9032D：FSK 解碼

Gray Code

Hamming distance 為 1，相鄰兩數之間只改變一個位元。

binary-reflected Gray code

C 跟 Java 的實作，奇數項都變個位數，偶數項變從個位數數起第一個 1 再過來那個位數：http://202.193.64.35/dept7/acm/web/AlgorithmGossip/GrayCode.htm

Binary Code 跟 Gray Code 的轉換。

• encode：G = B ^ (B>>1)
• decode 較麻煩，需從左邊開始一位一位算。