adjtimex()

adjtimex() 是 Linux 才有的調校時間系統呼叫，使用 David L. Mills 的 clock adjustment algorithm (見 RFC 5905)，透過 struct timex * 設定參數和回傳資料。ntp_adjtime() 只是用不同的 mode 名稱，偏好用在 NTP daemon。

#include <sys/timex.h>
int adjtimex(struct timex *buf);
int ntp_adjtime(struct timex *buf);

struct timex {
    int  modes;      /* Mode selector */
    long offset;     /* Time offset; nanoseconds (有設 STA_NANO) 或 microseconds */
    long freq;       /* Frequency offset; see NOTES for units */
    long maxerror;   /* Maximum error (microseconds) */
    long esterror;   /* Estimated error (microseconds) */
    int  status;     /* Clock command/status */
    long constant;   /* PLL time constant */
    long precision;  /* Clock precision
                        (microseconds, read-only) */
    long tolerance;  /* Clock frequency tolerance (read-only);
                        see NOTES for units */
    struct timeval time;
                     /* Current time (read-only, except for
                        ADJ_SETOFFSET); upon return, time.tv_usec
                        contains nanoseconds, if STA_NANO status
                        flag is set, otherwise microseconds */
    long tick;       /* Microseconds between clock ticks */
    long ppsfreq;    /* PPS (pulse per second) frequency
                        (read-only); see NOTES for units */
    long jitter;     /* PPS jitter (read-only); nanoseconds, if
                        STA_NANO status flag is set, otherwise
                        microseconds */
    int  shift;      /* PPS interval duration
                        (seconds, read-only) */
    long stabil;     /* PPS stability (read-only);
                        see NOTES for units */
    long jitcnt;     /* PPS count of jitter limit exceeded
                        events (read-only) */
    long calcnt;     /* PPS count of calibration intervals
                        (read-only) */
    long errcnt;     /* PPS count of calibration errors
                        (read-only) */
    long stbcnt;     /* PPS count of stability limit exceeded
                        events (read-only) */
    int tai;         /* TAI offset, as set by previous ADJ_TAI
                        operation (seconds, read-only,
                        since Linux 2.6.26) */
    /* Further padding bytes to allow for future expansion */
};

modes 決定哪些參數需要設，是下列的 bit‐wise 組合：

• ADJ_OFFSET：offset 設定時間偏移。Linux 2.6.26 以後會切去大於 ±0.5s 的部份，之前超出回 EINVAL。
• ADJ_FREQUENCY：freq 設定頻率偏移。Linux 2.6.26 以後會切去大於 ±32768000 的部份，之前超出範圍回 EINVAL。
• ADJ_MAXERROR：maxerror 設定 maximum time error。
• ADJ_ESTERROR：esterror 設定 estimated time error。
• ADJ_STATUS：status 設定 clock status bits，如下：

• The buf.status field is a bit mask that is used to set and/or  retrieve
         status  bits  associated with the NTP implementation.  Some bits in the
         mask are both readable and settable, while others are read-only.
  
         STA_PLL (read-write)
                Enable phase-locked loop (PLL) updates via ADJ_OFFSET.
  
         STA_PPSFREQ (read-write)
                Enable PPS (pulse-per-second) frequency discipline.
  
         STA_PPSTIME (read-write)
                Enable PPS time discipline.
  
         STA_FLL (read-write)
                Select frequency-locked loop (FLL) mode.
  
         STA_INS (read-write)
                Insert a leap second after the last second of the UTC day,  thus
                extending the last minute of the day by one second.  Leap-second
                insertion will occur each day, so long as this flag remains set.
  
         STA_DEL (read-write)
                Delete a leap second at the last second of the  UTC  day.   Leap
                second  deletion  will  occur each day, so long as this flag re‐
                mains set.
  
         STA_UNSYNC (read-write)
                Clock unsynchronized.
  
         STA_FREQHOLD (read-write)
                Hold frequency.  Normally adjustments made via ADJ_OFFSET result
                in  dampened frequency adjustments also being made.  So a single
                call corrects the current offset, but as offsets in the same di‐
                rection  are  made  repeatedly,  the small frequency adjustments
                will accumulate to fix the long-term skew.
  
                This flag prevents the small  frequency  adjustment  from  being
                made when correcting for an ADJ_OFFSET value.
  
         STA_PPSSIGNAL (read-only)
                A valid PPS (pulse-per-second) signal is present.
  
         STA_PPSJITTER (read-only)
                PPS signal jitter exceeded.
  
         STA_PPSWANDER (read-only)
                PPS signal wander exceeded.
  
         STA_PPSERROR (read-only)
                PPS signal calibration error.
  
         STA_CLOCKERR (read-only)
                Clock hardware fault.
  
         STA_NANO (read-only; since Linux 2.6.26)
                Resolution   (0  =  microsecond,  1  =  nanoseconds).   Set  via
                ADJ_NANO, cleared via ADJ_MICRO.
  
         STA_MODE (since Linux 2.6.26)
                Mode (0 = Phase Locked Loop, 1 = Frequency Locked Loop).
  
         STA_CLK (read-only; since Linux 2.6.26)
                Clock source (0 = A, 1 = B); currently unused.
  
         Attempts to set read-only status bits are silently ignored.

• ADJ_TIMECONST：constant 設定 PLL time constant。If the STA_NANO status flag (see below) is clear, the kernel adds 4 to this value.
• ADJ_SETOFFSET (Linux 2.6.39+)：time 增加到 current time. If buf.status includes the ADJ_NANO flag, then buf.time.tv_usec is interpreted as a nanosecond value; otherwise it is interpreted as microseconds.
• ADJ_MICRO、ADJ_NANO (Linux 2.6.26+)：分別選擇 microsecond 或 nanosecond resolution，兩者不能同時使用。
• ADJ_TAI (Linux 2.6.26+)：constant 設 TAI (Atomic International Time) offset。 ADJ_TAI should not be used in conjunction with ADJ_TIMECONST, since the latter mode also employs the buf.constant field. For a complete explanation of TAI and the difference between TAI and UTC, see BIPM ⟨http://www.bipm.org/en/bipm/tai/tai.html⟩
• ADJ_TICK：tick 設定 tick value。

另外，modes 可以使用下列多 bit 組成的值，此時其它 bit 不能使用：

• ADJ_OFFSET_SINGLESHOT (含有 ADJ_OFFSET)：傳統 adjtime() 方式，使用 offset 的 µs，kernel 進行每次最多 MAX_TICKADJ 逐步調整。offset 回傳之前剩餘未調整的。
  
• ADJ_OFFSET_SS_READ (Linux 2.6.28+)：offset 回傳先前 ADJ_OFFSET_SINGLESHOT 還有多少未調整。

一般使用者 modes 只能用 0 或 ADJ_OFFSET_SS_READ，其它要 superuser。

回傳值：成功回傳如下 clock state，失敗回傳 -1 並設 errno。

• TIME_OK：Clock synchronized, no leap second adjustment pending.
• TIME_INS：Indicates that a leap second will be added at the end of the UTC day.
• TIME_DEL：Indicates that a leap second will be deleted at the end of the UTC day.
• TIME_OOP：Insertion of a leap second is in progress.
• TIME_WAIT：A leap-second insertion or deletion has been completed. This value will be returned until the next ADJ_STATUS oper‐ ation clears the STA_INS and STA_DEL flags.
• TIME_ERROR (或 TIME_BAD)：The system clock is not synchronized to a reliable server. This value is returned when any of the following holds true:
• Either STA_UNSYNC or STA_CLOCKERR is set.
• STA_PPSSIGNAL is clear and either STA_PPSFREQ or STA_PPSTIME is set.
• STA_PPSTIME and STA_PPSJITTER are both set.
• STA_PPSFREQ is set and either STA_PPSWANDER or STA_PPSJITTER is set.

註：Linux 3.4 開始，the call operates asynchronously and the return value usually will not reflect a state change caused by the call itself.

失敗 errno 有：

• EFAULT：參數不可寫。
• EINVAL (kernels before Linux 2.6.26) An attempt was made to set buf.freq to a value outside the range (-33554432, +33554432).
• EINVAL (kernels before Linux 2.6.26) An attempt was made to set buf.offset to a value outside the permitted range. In kernels before Linux 2.0, the permitted range was (-131072, +131072). From Linux 2.0 onwards, the per‐ mitted range was (-512000, +512000).
• EINVAL An attempt was made to set buf.status to a value other than those listed above.
• EINVAL An attempt was made to set buf.tick to a value outside the range 900000/HZ to 1100000/HZ, where HZ is the system timer interrupt frequency.
• EPERM buf.modes is neither 0 nor ADJ_OFFSET_SS_READ, and the caller does not have sufficient privilege. Under Linux, the CAP_SYS_TIME capability is required.

NOTES
       In  struct timex, freq, ppsfreq, and stabil are ppm (parts per million)
       with a 16-bit fractional part, which means that a value of 1 in one  of
       those  fields  actually means 2^-16 ppm, and 2^16=65536 is 1 ppm.  This
       is the case for both input values (in the case of freq) and output val‐
       ues.

       The  leap-second processing triggered by STA_INS and STA_DEL is done by
       the kernel in timer context.  Thus, it will take one tick into the sec‐
       ond for the leap second to be inserted or deleted.

SEE ALSO
       settimeofday(2),  adjtime(3), ntp_gettime(3), capabilities(7), time(7),
       adjtimex(8), hwclock(8)

       NTP "Kernel Application Program Interface"
       ⟨http://www.slac.stanford.edu/comp/unix/package/rtems/src/ssrlApps/
       ntpNanoclock/api.htm⟩

#define ADJ_OFFSET              0x0001  /* time offset */
#define ADJ_FREQUENCY           0x0002  /* frequency offset */
#define ADJ_MAXERROR            0x0004  /* maximum time error */
#define ADJ_ESTERROR            0x0008  /* estimated time error */
#define ADJ_STATUS              0x0010  /* clock status */
#define ADJ_TIMECONST           0x0020  /* pll time constant */
#define ADJ_TICK                0x4000  /* tick value */
#define ADJ_OFFSET_SINGLESHOT   0x8001  /* old-fashioned adjtime */

asmlinkage long sys_adjtimex(struct timex __user *txc_p)
{
        struct timex txc;               /* Local copy of parameter */
        int ret;

        /* Copy the user data space into the kernel copy
         * structure. But bear in mind that the structures
         * may change
         */
        if(copy_from_user(&txc, txc_p, sizeof(struct timex)))
                return -EFAULT;
        ret = do_adjtimex(&txc);
        return copy_to_user(txc_p, &txc, sizeof(struct timex)) ? -EFAULT : ret;
}

參考

1. man adjtimex
2. Linux kernel 原始碼
   

• 軟體時鐘使用系統呼叫 adjtimex 來同步其它外部時鐘來源時，可以每 11 分鐘去調整硬體時鐘。

[C] isdigit() performance

使用函式庫 isdigit() 的程式未必較小。

參考

https://stackoverflow.com/questions/28425292/shouldnt-isdigit-be-faster-in-c

line buffer

stream 有 3 種緩衝方式 -- unbuffered、block buffered、和 line buffered：

• block buffered：一般檔案採用的方式，以 block 方式 (滿 block？) 寫入。檔案頭次 I/O 操作會 malloc() 取得緩衝區。
• line buffered：一般終端機的輸入 (stdin) 或輸出 (stdout) 採用的方式，遇到換行傳送。
  
• unbuffered：沒緩衝、馬上輸出。stderr 預設是 unbuffered。

改變緩衝方式。

int setvbuf(FILE *stream, char *buf, int mode, size_t size);

mode 是 _IONBF (unbuffered)、_IOLBF (line buffered)、和 _IOFBF (fully buffered，指 block buffer？) 之一。除了 unbuffered，size 大小的 buf 取代原本的緩衝區 (會釋出？)。如果 buf 是 NULL，在下次讀寫操作時自動配置新的緩衝區。setvbuf() 可能只能在 stream 任何其它操作之前使用。

注意：需要確認 stream 關閉時，buffer 是可用的。

void setbuf(FILE *stream, char *buf); 相當於 setvbuf(stream, buf, buf ? _IOFBF : _IONBF, BUFSIZ);

void setbuffer(FILE *stream, char *buf, size_t size); 相當於 setvbuf(stream, buf, buf ? _IOFBF : _IONBF, size);

void setlinebuf(FILE *stream); 相當於 setvbuf(stream, NULL, _IOLBF, 0);

fflush() 強迫輸出。 (見 fclose().)

註：開啟 file stream
#include <stdio.h>
fopen(), fdopen(), freopen

皆會用到 mode，可能是 r、r+、w、w+、a、a+。為了相容，都可以加上 b。

fopen()：開啟檔名
fdopen()：開啟 file descriptor
freopen()：fclose() 再 fopen()？用來改變 stdin、stdout、stderr 使用的 file。

參考

1. https://linux.die.net/man/3/setlinebuf
2. https://jenyiw.pixnet.net/blog/post/9391777 和 https://jenyiw.pixnet.net/blog/post/9391585：fwrite() 是 library 函數，使用緩衝區減少頻繁呼叫 syscall write()，在多次少量時效率會比直接用 write() 好。但 fwrite() 多了一次緩衝讀寫，在一次多量效率就會比 write() 差。
3. 相關函數：fseek()、fgetpos()、open()、fclose()、fileno()、fmemopen()、fopencookie()。
4. https://man7.org/linux/man-pages/man3/termios.3.html
5. https://blog.xuite.net/uwlib_mud/twblog/108242774
6. http://lwn.net/images/pdf/LDD3/ch18.pdf
7. termios
8. 在 canonical 模式 (正規模式)，終端設備會處理特殊字元，一次一行的方式輸入給應用程式。例如 Linux 的 shell指令。非正規模式終端設備不會處理特殊字元，一次一個字元的方式輸入給應用程式。
9. tty 名稱來自 teletypewriter 的縮寫，用來表示任何序列埠樣式的裝置,，可能是實體的裝置如 serial ports、USB-to-serial-port converters、一些需要特殊處理的數據機，或者是虛擬裝置用來登入。
   

遞迴呼叫 c-recursion

遞迴呼叫

遞迴是副程式直接或間接呼叫自己。相對於迭代 (iterative)

分治 (Divide and Conquer) 是種運用遞迴的特性來設計演算法的策略。

https://hackmd.io/@sysprog/c-recursion

https://www.facebook.com/groups/system.software2020/permalink/434463677487837/

窮舉與遞迴(enumeration and recursion)

inet_pton() and inet_ntop()

IPv4 或 IPv6 位址表示字串，如：

• 204.152.189.116 (dotted-decimal 的 IPv4 位址)
• ::1 (colon-separated hexadecimal 的 IPv6 位址)
• ::FFFF:204.152.189.116 (IPv4-mapped 的 IPv6 位址)

inet_pton() 可轉換成為二進位格式 (struct in_addr 或 strut in6_addr)。而 inet_ntop() 反之。 函數名稱中的 p 是「presentation」，指文字表示字串；n 是「network」。

#include <arpa/inet.h>

// 轉換 IPv4 或 IPv6 數字位址 (表示字串) src_str 為二進位格式 addrptr
int inet_pton(
    int family, // AF_INET 或 AF_INET6
    const char *src_str,
    void *addrptr);
// 回傳 1：成功、0：src_str 格式不是表示字串、–1 on error

// 轉換二進位格式 addrptr 為表示字串 dst_str
const char *inet_ntop(
    int family,
    const void *addrptr,
    char *dst_str,
    size_t len);
// 回傳 指向 dst_str 的文字字串: 成功, NULL: 錯誤

• family 可以是 AF_INET 或 AF_INET6。擴充並捨棄 inet_aton() 與 inet_ntoa() (只能用在 IPv4)。問題：程式如何判斷位址是 IPv4 或 IPv6?
• addrptr 依據 family 可指到 struct in_addr 或 struct in6_addr。
• 呼叫 inet_ntop() 需提供長度 len 的 dst_str buffer，適當的長度是 INET_ADDRSTRLEN (16) 或 INET6_ADDRSTRLEN (46)。

參考來源

TLPI §59.6 §59.13.1

C: variable argument lists

函數可有未知數目和 type 的引數。

#include <stdarg.h>

void va_start(va_list ap, last);
type va_arg(va_list ap, type);
void va_end(va_list ap);
void va_copy(va_list dest, va_list src);

首先宣告一個 va_list 物件，然後使用 va_start() 初始化物件，和 va_end() 成對使用，之間用 va_arg()、或 vprintf() 等使用 va_list 物件。
va_arg() 將第一個引數定義為 type 後指到下個引數。

#include <stdarg.h>

void my_printf(const char *fmt, ...)
{
    va_list ap;        //宣告一個 va_list 物件 ap
 
    va_start(ap, fmt); //初始化 ap
    vprintf(fmt, ap);  //使用 ap 並更新指到下個未用的引數
    va_end(ap);        //結束 ap
}

va_list 最普遍是一個指標指到函數的 stack frame，複製可以直接指定：

va_list aq = ap

但也有系統是一個陣列，內容是一個指標，需要：

va_list aq;
*aq = *ap;

另外，argument 如果是透過暫存器傳遞的系統，va_start() 需要配置記憶體存 arguments 和指示哪個是下個 argument，va_end() 可以釋出配置的記憶體。

因應不同情況, C99 新增 va_copy()，複製變成：

va_list aq;
va_copy(aq, ap);
...
va_end(aq);

Singly Linked List

Linked List 是程式常見的資料結構，通常是指 Double Linked List (如 linux/list.h)，但這裡說 Singly Linked List。

Singly linked list 第一個 node 透過 head 指標存取，每個 node 有一個 next 指標串下個 node，最後 node (稱為 tail) 的next 為 nil。

移除 node

typedef struct list {
    item *head;
} list;

static inline item **ll_find(list *list, item *node)
{
    item **pp = &list->head;
    while(*pp != node)
        pp = &(*pp)->next;
    return pp;
}

void ll_remove(list *list, item *node)
{
    item **pp = ll_find(list, node);
    *pp = node->next;
}

• https://github.com/mkirchner/linked-list-good-taste：傳統用 prev 和 cur 指標，這裡用 ndirect pointer 是指到 node pointer 的 pointer，可用來移除一個 node (remove 只是將 node 脫離 list，而 delete 還包括抹除) 和在 node 之前插入一個 node。

如果作為 FIFO 常常需要將 node 放到 tail，額外紀錄 tail 指標：

typedef struct list {
    item *head;
    item *tail;
} list;

// 先準備好 node, node->next = null;
void ll_insert_tail(list *list, item *node)
{
    if (list->tail)
        list->tail->next = node; // 避免 node 加入時，tail 剛好刪除
    else
        list->head = node;
    list->tail = node;
}

item *ll_remove_head(list *list)
{
    item *node = list->head;
    list->head = node->next;
    if (list->tail == node)
        list->tail = NULL;
    return node;
}

lock-free linked list 用在 concurrent 環境：兩個或以上 thread 執行操作不干擾彼此間的工作。

基本操作有兩個

1. 插入 node p 之後
2. 移除 node p 之後那個 node
   

// compare and swap
void *cas(void **addr, void *old, void *new)
{
    void *value = ∗addr
    if (value == old)
        ∗add = new
    return value;
}

void ll_insert_after(item *p, item *n)
{
    do {
        item *next = p->next;
        n->next = next;
    } while (cas(address-of(p->next), next, n));
}

itme *ll_remove_after(item *p)
{
}

問題：如何確認某個 node 是否有其它 thread 仍在使用？例如 thread A 停在 node n (可能搜尋一半，或其它)，此時 thread B 移除 node n 並釋出記憶體，會造成 thread A 問題

問題
cache unfriendly

https://en.wikipedia.org/wiki/Non-blocking_linked_list
https://ithelp.ithome.com.tw/articles/10214944
https://gcc.gnu.org/onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html

Circular doubly linked list

C Library rand()

產生虛擬亂數 (pseudo-random number)，不是真的亂數，也不是機密的，而是一系列看起來像亂數的數列，這些數字實際上是有固定順序的。

#include <stdlib.h>

void srand(unsigned int seed); // 設定函式庫內部的 seed，一開始預設是 1。

int rand(void); // 依據 seed 運算產生範圍為 [0, RAND_MAX] 的虛擬亂數回傳，並儲存為新的 seed。

int rand_r(unsigned int *seedp); //

rand_r() 為 reentrant 版的 rand()，需要傳入儲存 seed 的記憶體指標，在 thread 程式得以不被其它 thread 干擾來產生同樣的數列。在 POSIX.1-2008 標注為廢棄。

POSIX.1-2001 rand() 和 srand() 的實作範例：

static unsigned long next = 1;

/* RAND_MAX assumed to be 32767 */
int myrand(void) {
    next = next * 1103515245 + 12345;
    return((unsigned)(next/65536) % 32768);
}

void mysrand(unsigned int seed) {
    next = seed;
}

注意

• 虛擬亂數是有一定順序的，知道 seed 就知道下一個產生的值。假設初始 seed 設為目前的時間秒數，已知是今年的話，大約有 2²⁵ 個可能的值，縮小範圍後依現今運算能力很容易試出來。
• 產生序列的最低 bit 固定 01010101..，其實不夠亂。
• 1995 發現 Netscape 瀏覽器產生的 SSL session keys 使用時間和 process ID 作為 seed，猜得到，所以 SSL sessions 可在幾分鐘內破壞。...

以上經驗告訴我們，作為 secure 的虛擬亂數產生器，有兩個基本原則：

1. seed 必須是無法預測的 (實際上只能難以預測？)。要有足夠的可能性，例如 2¹²⁸ 就足夠 (隨著計算能力越來越強，暴力破解越容易，需要更多 bit)，所有可能出現的機率相同，沒有東西讓攻擊者可以縮小範圍。
2. 產生虛擬亂數的 algorithm 必須是 secure，pseudorandom bits 沒有可辨別的 patterns。即使攻擊者學到或猜到一些 pseudorandom bits，也無法預測其它 pseudorandom bits。

參考

1. https://inst.eecs.berkeley.edu//~cs161/fa08/Notes/random.pdf

• drand48()：較長的虛擬亂數產生器。
• 在 Linux C Library，rand() 使用和 random() 相同的亂數產生器。
• GNU C Pseudo-Random Numbers
• https://blog.gtwang.org/programming/c-cpp-rand-random-number-generation-tutorial-examples/
  

[C] VLA

VLA (Variable-Length Array) 起自 C99，讓陣列大小可以在執行時才決定，雖然有方便性，但有缺點：

• 執行時需要決定陣列大小，會慢一點，程式也會大一點。(或許最終使用的記憶體較少)
• LLVM Clang 不支援在 struct 裡放 VLA (GCC 支援)，只支援 C99 形式的 VLA。
• 最重要的是 VLA 的使用在 kernel 堆疊有安全疑慮 (security implication)。 

Linux v4.20 移除了 VLA，並加了「-Wvla」來發出編譯告警，避免不經意再加入 VLA 的程式碼。

參考：

1. The Linux Kernel Is Now VLA-Free: A Win For Security, Less Overhead & Better For Clang

延伸閱讀：

• 大小 0 的陣列

scanf()

輸入格式轉換，存到記憶體

#include <stdio.h>

int scanf(const char *format, ...);
int fscanf(FILE *stream, const char *format, ...);
int sscanf(const char *str, const char *format, ...);

#include <stdarg.h>

int vscanf(const char *format, va_list ap);
int vsscanf(const char *str, const char *format, va_list ap);
int vfscanf(FILE *stream, const char *format, va_list ap);

format 是一個字串，描述如何處理輸入字元。如果沒有輸入、或比對失敗，就停止，回傳轉換成功的次數。format 內容可以是：

• 空白字元集，包括 space、tab、newline 等，比對 0 個以上的空白字元集。
• % 開頭的轉換規範。
• 其它一般字元

每個轉換規範以 '%' 或 %n$ 開始，後者指定用第幾個變數存。接著：

• (optional) '*'：依照轉換定義讀取，但不儲存，不計成功轉換次數。
• (optional) 'm'：用在字串轉換 (%s, %c, %[)，自動配置足夠的記憶體放字串，之後需要 free()。
• (optional) 十位數字說明最大 field width，不含字串結尾 0。
• (optional) 改變存成的資料型態
• h：存成 short int 或 unsigned short int
• hh：存成 signed char 或 unsigned char
• j：存成 intmax_t 或 uintmax_t
• l：整數存成 long 或 unsigned long，浮點存成 double
• ll：跟 L 一樣，用在 %c 或 %s 表示寬字元。
• L：整數存成 long long，浮點存成 long double
• t：存成 ptrdiff_t
• z：存成 size_t
• 轉換定義
• %：比對 %
• d：比對十進位整數，可以是有號，結果存到 int
• i：比對對整數，可以是有號，可以是 0x 或 0X 開始的十六進位數字、0 開頭的八進位數字、不然則是十進位。結果存到 int。
• o：比對無號八進位整數，結果存到 unsigned int。
• u：比對無號十進位整數，結果存到 unsigned int。
• x, X：比對無號十六進位整數，結果存到 unsigned int。
• f, e, g, E, a：有號浮點數字，結果存到 float。
• s：不含 white-space 的字串，存到字串。
• c：數個字元，存到 char 陣列。
• [字元集]：比對字元集存到字串。字元集不能是空的，不省略開頭的 white space。排除這些字元集的話，字元集以 ^ 開始。如果字元集要包含 ]，可放在第一個字元。兩字元間可夾 - 表示範圍。例如 [^]0-9-] 表示任何字元不含 ]、0 到 9、-。
• p：比對指標值存到 void 指標。
• n：計數字元數目存到 int。可能不計成功的轉換次數。

問題：可以忽略開頭字元嗎？

參考：printf

GCC 使用 MIPS DSP ASE

MIPS DSP ASE

gcc 編譯選項

• 加「-mdsp」(24KE, 34K) 或「-mdsp2」(74K, M14KE)，不然會有「undefined reference to `__ssaddhq3'」之類的錯誤
• 加「-mips32r2」可使用 INS 指令，存取 SIMD 變數的單元有較好的效能
• M14KE 的 DSP instructions 可組譯成 microMIPS opcode (加「-mmicromips」)

C 定義

• __mips_dsp 或 __mips_dsp_rev=1
• __mips_dspr2 或 __mips_dsp_rev=2
• __MIPSEL__

Data types 及變數初始化

• typedef short q15;
  q15 a = 0.1234 * 32768.0;
• typedef int q31;
  q31 b = 0.2468 * 2147483648.0;
• typedef long long a64;
• typedef signed char v4i8 __attribute__ ((vector_size(4)));
  v4i8 a = {1, 2, 3, 4};
  v4i8 b;
  b = (v4i8) {5, 6, 7, 8};
• typedef short v2q15 __attribute__ ((vector_size(4)));
  v2q15 a = {0x0fcb, 0x3a75};
  v2q15 b;
  b = (v2q15) {0.1234 * 32768.0, 0.4567 * 32768.0};
• endian 問題，詳見 MD00485 2.4 2.5

C 運算子

• fractional data 的 +, - 跟 integer data 一樣 (addu, subu)，但 * (乘法) 後需要位移來對齊小數點
• SIMD 變數可以使用 +, -, *, /, unary minus, ^, |, &, ~ 作運算，但只有 +, - 有指令 (addu.qb, subu.qb, addq.ph, subq.ph)，其它 GCC 則 synthesizes 一系列指令。

暫存器多三組 HI-LO (共四組) 及 DSPControl
DSP Control Register

• 有 6 欄位：

  name	bits	mask	說明
  CCOND	27:24	16	condition code
  OUFLAG	23:16	8	overflow/underflow。只能用 wrdsp 清掉 16：HI-LO 0 17：HI-LO 1 18：HI-LO 2 19：HI-LO 3 20： 21： 22： 23：
  EFI	14	32	extract fail indicator
  C	13	4	carry bit，用在 addsc, addwc
  SCOUNT	12:7	2	size count
  POS	5:0	1	position bits

• 專用來存取的指令：rddsp/wrdsp
• SCOUNT 及 POS 視為全域變數，會改變它們的指令或函數不會優化掉，包括 wrdsp, extpdp, extpdpv、及 mthlip。
• For correctness, programmers must assume that a function call clobbers all fields of the DSP control register. That is, programmers cannot depend on the values in CCOND, OUFLAG, EFI or C across a function-call boundary. They must re-initialize the values of CCOND, OUFLAG, EFI or C before using them.

比較：使用內建函數 (Intrinsic) 及組合語言巨集 (macro)
內建函數已對 pipeline 延遲做最佳化，而 macro 沒有，而造成 code scheduling 較差、及增加 stall。

C 內建函數 (Intrinsics)

• Q31
• q31 __builtin_mips_addq_s_w (q31, q31);
  q31 __builtin_mips_subq_s_w (q31, q31);
• q31 __builtin_mips_absq_s_w (q31);
• q31 __builtin_mips_shll_s_w (q31, imm0_31);
  q31 __builtin_mips_shll_s_w (q31, i32);
• q31 __builtin_mips_shra_r_w (q31, imm0_31);
  q31 __builtin_mips_shra_r_w (q31, i32);
• a64 __builtin_mips_dpaq_sa_l_w (a64, q31, q31); // Q63 + Q31 * Q31 => Q63
  a64 __builtin_mips_dpsq_sa_l_w (a64, q31, q31); // Q63 - Q31 * Q31
• q31 __builtin_mips_mulq_rs_w (q31, q31); // DSPR2
• q31 __builtin_mips_mulq_s_w (q31, q31); // DSPR2
• q31 __builtin_mips_addqh_w (q31, q31); // DSPR2
  q31 __builtin_mips_addqh_r_w (q31, q31); // DSPR2
• q31 __builtin_mips_subqh_w (q31, q31); // DSPR2
  q31 __builtin_mips_subqh_r_w (q31, q31); // DSPR2
• Q15
• v2q15 __builtin_mips_addq_ph (v2q15, v2q15);
  v2q15 __builtin_mips_addq_s_ph (v2q15, v2q15);
  v2q15 __builtin_mips_subq_ph (v2q15, v2q15);
  v2q15 __builtin_mips_subq_s_ph (v2q15, v2q15);
• v2q15 __builtin_mips_absq_s_ph (v2q15);
• v2q15 __builtin_mips_shll_ph (v2q15, imm0_15);
  v2q15 __builtin_mips_shll_ph (v2q15, i32);
  v2q15 __builtin_mips_shll_s_ph (v2q15, imm0_15);
  v2q15 __builtin_mips_shll_s_ph (v2q15, i32);
• v2q15 __builtin_mips_shra_ph (v2q15, imm0_15);
  v2q15 __builtin_mips_shra_ph (v2q15, i32);
  v2q15 __builtin_mips_shra_r_ph (v2q15, imm0_15);
  v2q15 __builtin_mips_shra_r_ph (v2q15, i32);
• v2q15 __builtin_mips_mulq_rs_ph (v2q15, v2q15); // Q15 * Q15 => Q15
• a64 __builtin_mips_dpaq_s_w_ph (a64, v2q15, v2q15); // 累加兩個乘積
  a64 __builtin_mips_dpsq_s_w_ph (a64, v2q15, v2q15); // 累減兩個乘積
• a64 __builtin_mips_mulsaq_s_w_ph (a64, v2q15, v2q15); // 累加第一個乘積，減第二個乘積，跟 endian 有關
• a64 __builtin_mips_maq_s_w_phl (a64, v2q15, v2q15); // 只累加其中一個乘積
  a64 __builtin_mips_maq_s_w_phr (a64, v2q15, v2q15);
  a64 __builtin_mips_maq_sa_w_phl (a64, v2q15, v2q15);
  a64 __builtin_mips_maq_sa_w_phr (a64, v2q15, v2q15);
• q31 __builtin_mips_muleq_s_w_phl (v2q15, v2q15); // Q15 * Q15 => Q31，只相乘一組
  q31 __builtin_mips_muleq_s_w_phr (v2q15, v2q15);
• Replicate a Fixed Half-word into Elements
  v2q15 __builtin_mips_repl_ph (imm_n512_511);
  v2q15 __builtin_mips_repl_ph (i32);
• void __builtin_mips_cmp_eq_ph (v2q15, v2q15);
  void __builtin_mips_cmp_lt_ph (v2q15, v2q15);
  void __builtin_mips_cmp_le_ph (v2q15, v2q15);
• v2q15 __builtin_mips_pick_ph (v2q15, v2q15);
• v2q15 __builtin_mips_packrl_ph (v2q15, v2q15);
• v2q15 __builtin_mips_mulq_s_ph (v2q15, v2q15); // DSPR2
• v2q15 __builtin_mips_addqh_ph (v2q15, v2q15); // DSPR2
  v2q15 __builtin_mips_addqh_r_ph (v2q15, v2q15); // DSPR2
• v2q15 __builtin_mips_subqh_ph (v2q15, v2q15); // DSPR2
  v2q15 __builtin_mips_subqh_r_ph (v2q15, v2q15); // DSPR2
• a64 __builtin_mips_dpaqx_s_w_ph (a64, v2q15, v2q15); // DSPR2
  a64 __builtin_mips_dpaqx_sa_w_ph (a64, v2q15, v2q15); // DSPR2
  a64 __builtin_mips_dpsqx_s_w_ph (a64, v2q15, v2q15); // DSPR2
  a64 __builtin_mips_dpsqx_sa_w_ph (a64, v2q15, v2q15); // DSPR2
• 8-bit
• v4i8 __builtin_mips_addu_qb (v4i8, v4i8);
  v4i8 __builtin_mips_addu_s_qb (v4i8, v4i8);
  v4i8 __builtin_mips_subu_qb (v4i8, v4i8);
  v4i8 __builtin_mips_subu_s_qb (v4i8, v4i8);
• i32 __builtin_mips_raddu_w_qb (v4i8);
• v4i8 __builtin_mips_shll_qb (v4i8, imm0_7);
  v4i8 __builtin_mips_shll_qb (v4i8, i32);
  v4i8 __builtin_mips_shrl_qb (v4i8, imm0_7);
  v4i8 __builtin_mips_shrl_qb (v4i8, i32);
• a64 __builtin_mips_dpau_h_qbl (a64, v4i8, v4i8);
  a64 __builtin_mips_dpau_h_qbr (a64, v4i8, v4i8);
  a64 __builtin_mips_dpsu_h_qbl (a64, v4i8, v4i8);
  a64 __builtin_mips_dpsu_h_qbr (a64, v4i8, v4i8);
• v4i8 __builtin_mips_repl_qb (imm0_255);
  v4i8 __builtin_mips_repl_qb (i32);
• void __builtin_mips_cmpu_eq_qb (v4i8, v4i8);
  void __builtin_mips_cmpu_lt_qb (v4i8, v4i8);
  void __builtin_mips_cmpu_le_qb (v4i8, v4i8);
  i32 __builtin_mips_cmpgu_eq_qb (v4i8, v4i8);
  i32 __builtin_mips_cmpgu_lt_qb (v4i8, v4i8);
  i32 __builtin_mips_cmpgu_le_qb (v4i8, v4i8);
  i32 __builtin_mips_cmpgdu_eq_qb (v4i8, v4i8); // DSPR2
  i32 __builtin_mips_cmpgdu_lt_qb (v4i8, v4i8); // DSPR2
  i32 __builtin_mips_cmpgdu_le_qb (v4i8, v4i8); // DSPR2
• v4i8 __builtin_mips_pick_qb (v4i8, v4i8);
• v4i8 __builtin_mips_absq_s_qb (v4i8); // DSPR2
• v4i8 __builtin_mips_adduh_qb (v4i8, v4i8); // DSPR2
  v4i8 __builtin_mips_adduh_r_qb (v4i8, v4i8); // DSPR2
• v4i8 __builtin_mips_shra_qb (v4i8, imm0_7); // DSPR2
  v4i8 __builtin_mips_shra_r_qb (v4i8, imm0_7); // DSPR2
  v4i8 __builtin_mips_shra_qb (v4i8, i32); // DSPR2
  v4i8 __builtin_mips_shra_r_qb (v4i8, i32); // DSPR2
• v4i8 __builtin_mips_subuh_qb (v4i8, v4i8); // DSPR2
  v4i8 __builtin_mips_subuh_r_qb (v4i8, v4i8); // DSPR2
• a64
• i32 __builtin_mips_extr_w (a64, imm0_31);
  i32 __builtin_mips_extr_w (a64, i32);
  i32 __builtin_mips_extr_r_w (a64, imm0_31);
  i32 __builtin_mips_extr_r_w (a64, i32);
  i32 __builtin_mips_extr_rs_w (a64, imm0_31);
  i32 __builtin_mips_extr_rs_w (a64, i32);
• i32 __builtin_mips_extr_s_h (a64, imm0_31);
  i32 __builtin_mips_extr_s_h (a64, i32);
• i32 __builtin_mips_extp (a64, imm0_31);
  i32 __builtin_mips_extp (a64, i32);
• i32 __builtin_mips_extpdp (a64, imm0_31);
  i32 __builtin_mips_extpdp (a64, i32);
• a64 __builtin_mips_shilo (a64, imm_n32_31);
  a64 __builtin_mips_shilo (a64, i32);
• a64 __builtin_mips_mthlip (a64, i32);
• Precision Reduce/Expand
• v4i8 __builtin_mips_precrq_qb_ph (v2q15, v2q15);
• v4i8 __builtin_mips_precrqu_s_qb_ph (v2q15, v2q15);
• v2q15 __builtin_mips_precequ_ph_qbl (v4i8);
  v2q15 __builtin_mips_precequ_ph_qbr (v4i8);
  v2q15 __builtin_mips_precequ_ph_qbla (v4i8);
  v2q15 __builtin_mips_precequ_ph_qbra (v4i8);
• v2q15 __builtin_mips_preceu_ph_qbl (v4i8);
  v2q15 __builtin_mips_preceu_ph_qbr (v4i8);
  v2q15 __builtin_mips_preceu_ph_qbla (v4i8);
  v2q15 __builtin_mips_preceu_ph_qbra (v4i8);
• v4i8 __builtin_mips_precr_qb_ph (v2i16, v2i16); // DSPR2
• v2q15 __builtin_mips_precrq_ph_w (q31, q31);
• v2q15 __builtin_mips_precrq_rs_ph_w (q31, q31);
• q31 __builtin_mips_preceq_w_phl (v2q15);
  q31 __builtin_mips_preceq_w_phr (v2q15);
• Int8 * Q15 => Q15
• v2q15 __builtin_mips_muleu_s_ph_qbl (v4i8, v2q15);
  v2q15 __builtin_mips_muleu_s_ph_qbr (v4i8, v2q15);
• Add and Set Carry/Add with Carry
  i32 __builtin_mips_addsc (i32, i32);
  i32 __builtin_mips_addwc (i32, i32);
• Modular Subtraction on an Index Value
  i32 __builtin_mips_modsub (i32, i32);
• Bit Reverse a Half-word
  i32 __builtin_mips_bitrev (i32);
• Insert Bit Field Variable
  i32 __builtin_mips_insv (i32, i32);
• Load Unsigned Byte/Halfword/Word Indexed
  i32 __builtin_mips_lbux (void *, i32);
  i32 __builtin_mips_lhx (void *, i32);
  i32 __builtin_mips_lwx (void *, i32);
• Signed Multiply and Add
  a64 __builtin_mips_madd (a64, i32, i32);
• Unsigned Mulitply and Add
  a64 __builtin_mips_maddu (a64, ui32, ui32);
• Signed Multiply and Subtract
  a64 __builtin_mips_msub (a64, i32, i32);
• Unsigned Multiply and Subtract
  a64 __builtin_mips_msubu (a64, ui32, ui32);
• Signed Multiply
  a64 __builtin_mips_mult (i32, i32);
• Unsigned Multiply
  a64 __builtin_mips_multu (ui32, ui32);
• Left Shift and Append Bits (DSPR2)
  i32 __builtin_mips_append (i32, i32, imm0_31); // DSPR2
• Byte Align Contents from Two Registers (DSPR2)
  i32 __builtin_mips_balign (i32, i32, imm0_3); // DSPR2
• Right Shift and Prepend Bits (DSPR2)
  i32 __builtin_mips_prepend (i32, i32, imm0_31); // DSPR2
• 3.9, 3.10

其它方式：

• 全組合語言，或夾雜在 C 裡面
• 使用 Fixed-point data types (_Frac) 搭配 C 運算子

參考資料：

1. MD00485 -- 主要參考來源
2. MD00086 The MIPS32® Instruction Set
3. MD00374 The MIPS® DSP Application-Specific Extension to the MIPS32® Architecture
4. GCC: Using Vector Instructions through Built-in Functions

相關文章：

1. GCC Inline Assembly

malloc(), calloc(), realloc() 和 alloca()

可以從兩個所在動態取得記憶體，一般 malloc() 是從 heap，另一款是從 stack。

從 stack 動態配置記憶體，函數結束自動釋出。只是調整 stack 指標，效率足好。

#include <alloca.h>

void *alloca(size_t size);

• 可簡化 longjmp() 或 siglongjmp() 的記憶體釋放，不鼓勵用在其它地方 (為什麼？？？)
• 不能直接用在函數參數內，配置的記憶體夾在函數參數間可能會有問題。
• stack overflow 時不會傳回 NULL，SIGSEGV

從 heap 動態配置記憶體

#include <stdlib.h>

// 取得 size 大小位元組、未初始化的記憶體空間。
void *malloc(size_t size);

// 從 heap 動態配置的記憶體，都需要用 free() 歸還，或者在程式結束時自動消失。
// 重複釋出可能發生不可預期的結果。ptr 可以是 NULL，不進行任何動作。
void free(void *ptr);

// 基於 malloc()，取得 nmemb * size 大小的記憶體空間，並清為 0。
void *calloc(size_t nmemb, size_t size);


// 記憶體空間重新配置為 size 大小，重複部份會相同。
// 加大配置的空間時，位置可能變或不變。位置改變時會複製重複的部份，效能會較差。
void *realloc(void *ptr, size_t size);

其它使用 malloc() 的函式：strdup() 等。

malloc() 細節

heap 一般放在 Uninitialize data (bss) 後面生向高位址，另一端是 stack 生向 heap。

典型 x86-32 Linux layout

	Kernel
0xC000 0000
	argv, environment
	Stack
Top of stack →
	↓ (unallocated memory) ↑
Program break →
	Heap
	Uninitialized data (bss)
	Initialized data
	Text (program code)
0x0804 8000
0x0000 0000

heap 跟 stack 中間是實際沒用到的記憶體。heap 的盡頭就是 program break，不夠用時會用 sbrk() 調整 program break 來加大 heap，但通常不會縮減 heap。sbrk(0) 傳回目前 program break 位置。

藏在每一個 malloc() 的記憶體前面，會紀錄這段記憶體的大小。當 free() 時，利用記憶體空間形成 doubly link list 歸還回到 free 列表，並嘗試合併相鄰的記憶體區塊。

配置的記憶體區塊 (前置區塊大小)
size	可使用的部份
已釋出可使用的列表 (利用可使用的部份存放 link list 指標)
size	prev	next	剩下可使用的部份

每次 malloc() 會先從 free 列表取得記憶體，例如用 first-fit 或 best-fit 等演算法，如取不到則嘗試加大 heap。

當配置的記憶體區塊大於 MMAP_THRESHOLD，glibc 改用系統呼叫 mmap() 配置，在 Linux 4.7 之後會受到 RLIMIT_DATA 限制。MMAP_THRESHOLD 預設 128 kB，可透過 mallopt() 調整。

在 multithread 應用，內部使用 mutex 保護相關資料結構，glibc 並建立額外的 memory allocation arenas。每個 arena 是內部用 brk() 或 mmap() 配置的大記憶體空間。

每個 process 有自己的虛擬記憶體，虛擬記憶體中實際有使用的區塊才會對應到實體記憶體。malloc() 不保證可以取得實體記憶體，萬一沒有實體記憶體體了，有些 process 會被 OOM killer 結束掉 (見 proc 檔案系統 /proc/sys/vm/overcommit_memory 和 /proc/sys/vm/oom_adj 的說明，以及 Linux kernel 的 Documentation/vm/overcommit-accounting)。

malloc() 除錯

mtrace()、muntrace()
mcheck()、mprobe()
malloc() 除錯函式庫：Electric Fence (http://www.perens.com/FreeSoftware/)、dmalloc (http://dmalloc.com/)、Valgrind (http://valgrind.org/)、Insure++ (http://www.parasoft.com/)。
mallopt()、mallinfo()

參考

1. TLPI §7
2. man alloca 
3. malloc() man-page

• asprintf()
• mmap()
• memalign()、posix_memalign()
• malloc_trim()

字串複製

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() 系列標準函數
  

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 較麻煩，需從左邊開始一位一位算。

ioctl 系統呼叫

驅動程式除了 read()/write() 外，通常可以透過 ioctl() 系統呼叫進行一些控制或設定，如鎖門、退片、回報錯誤、改變 baud rate、或 self destruct 等。

在 user space 格式如下：

#include <sys/ioctl.h>
int ioctl(int fd, unsigned long cmd, ...);

其中 fd 是開的 file descriptor，cmd 是指令碼，和之後可能的參數。在這裡，... 只會有一個選擇性的第三個參數，看 cmd 需要來定，可以沒有、可以是整數、可以是指標傳送任意量的任意資料。

每個驅動程式的 ioctl cmd 基本上是不同的、通常未文件化的，而無法 audit these calls in any sort of comprehensive manner. It is also difficult to make the unstructured ioctl arguments work identically on all systems; for example, consider 64-bit systems with a user-space process running in 32-bit mode. 以致於有實作其它各種方式的控制操作的驅求，包括 embedding commands into the data stream 或使用 sysfs 或驅動程式特有的 virtual filesystems 等。

基本上 cmd 的編碼只要和對應的驅動程式配合好就好，但如果 cmd 編號在整個系統是唯一的，這樣 cmd 發給錯誤的 device 就可以偵測到，不處理而回 EINVAL。為協助建立唯一的 cmd 編號，在 <linux/ioctl.h> 將 cmd 分成幾個欄位：

• 2-bit dir：bit 0 = write，bit 1 = read
• 14-bit size：資料長度，並不強制使用，kernel 本身並不檢查。
• 8-bit type：magic number (神奇數字)，Documentation/ioctl-number.txt 有列表，可用來選擇不重複的 magic number。
  
• 8-bit number：command number (指令編號)
  

0x54 is just a magic number to make these relatively unique ('T')

ioctl() 和 read() 或 write() 一樣，可能需要 copy_from_user() 在 user-space 和 kernel-space 之間搬移資料。

如果只是設定的話，第三個參數、甚至 cmd 可直接放設定的資料，只要大小不要超過 unsigned long，未必需要是一個指標指到設定的資料。這樣不用取資料位址，也不用 copy_from_user()，效能會好一點點吧。

ioctl() 錯誤時回傳 -1，並設定 errno。如果只是讀取 1 個或 2 個 byte，也可以直接用回傳正值，不用第三個參數指標指到回傳 buffer，也不用 copy_to_user()，效能會好一點點吧。

Kernel 內部是執行 vfs_ioctl(filp, fd, cmd, arg)，如果需要 security 檢查會先執行 security_file_ioctl()。vfs_ioctl() 會處理 cmd FIOCLEX、FIONCLEX、FIONBIO、FIOASYNC、和 FIOQSIZE，這些 cmd 的 magic 使用 'T'，有些架構用 'f'。其它 cmd，如果是一般檔案則執行 file_ioctl()，否則執行 do_ioctl()。do_ioctl() 執行 unlocked_ioctl() 或 Big Kernel Lock 執行 ioctl()。

另一個會呼叫 vfs_ioctl() 的地方是 compat_sys_ioctl()，在 64 位元系統才有，有一些相容設計。

在驅動程式的格式是

int (*ioctl) (struct inode *inode, struct file *filp, unsigned int cmd, unsigned long arg);

inode 和 filp 來自應用程式提供的 file descriptor fd。cmd 不變地來自應用程式。unsigned long arg 來自應用程式的第三個參數，無論是整數或指標、或者無。

大部分驅動程式實作，會有個針對 cmd 的 大 switch，選擇對應的行為，不同 cmd 有不同數值，通常在 header 檔定義成 symbolic names，給驅動程式和應用程式共用。

參考

1. LDD ch. 6
2. Linux Kernel

• file_operations unlocked_ioctl
• socket ioctls

assert()

#include <assert.h>

void assert(scalar expression);

assert(表示式) 是個標準的 macro，用來方便程式除錯。當表示式結果為 0 (邏輯判斷為假) 時，會印包含檔名、行數、函數名及表示式的訊息到 stderr，然後呼叫 abort() 結束程式。如果在 <assert.h> 之前有定義 NDEBUG 的話，就會關閉 assert() 功能，整個 assert() 會省略掉，不會產生任何程式碼。所以 assert() 不能含有有作用的程式。

簡略的 assert.h 如下：

#ifdef  NDEBUG
#define assert(expr)        ((void) (0))
#else /* Not NDEBUG.  */
#define assert(expr)       ((void) ((expr) ? 0 :                                                             \
                       (__assert (__STRING(expr), __FILE__, __LINE__, __func__), 0)))
#endif /* NDEBUG.  */

而 __assert() 函數如下：

static smallint in_assert;                      /* bss inits to 0. */

void __assert(const char *assertion, const char * filename,
              unsigned int linenumber, register const char * function)
{
        if (!in_assert) {
                in_assert = 1;

                fprintf(stderr,
                                "%s: %d: %s: Assertion `%s' failed.\n",
                                filename,
                                linenumber,
                                /* Function name isn't available with some compilers. */
                                ((function == NULL) ? "?function?" : function),
                                assertion
                                );
        }
        abort();
}

參考來源：man assert, assert.h, __assert.c

程式註解的標籤

標籤有助於索引問題，常見的有：

• FIXME：需要修正
• XXX：該刪除
• TODO：打算要實作。久了之後可能會累積很多，建議加上日期及名子。
• NOTE：說明程式碼內部運作方式及可能的陷阱。

參考來源

1. wikipedia: Comment (computer_programming)#Tags

inline

行內函數、內聯函數

就軟體工程觀點，使用函數是很好的作法，但多了函數呼叫來回的額外負擔，特別是小的、經常呼叫的函數。將函數 qualifier 為 inline 可節省呼叫的額外負擔。

• 空間換取時間 -- 函數程式碼會複製多份，可能使得程式變大了。
• 如果 inline 函數的參數有常數，編譯時可以加以簡化，所以未必包含整個 inline 函數的程式碼。
• 只是建議編譯器 inline 處理，未必採納，編譯器保有最終決定權。
• 比較：static inline 強迫編譯器 inline 處理
• GCC -Winline 提供 inline 函數失敗的原因
• 只需要定義於表頭檔
• inline 的函數改變時，使用它的程式都需要重新編譯。
• 告訴 GCC 嘗試 inline 所有夠簡單的函數：-finline-functions。

跟 #define (巨集) 比較

• 巨集不能將 C++ 非 public 變數傳出去
• 兩者結果有時不同。巨集像是字串取代，inline 像是函數
• 巨集在行數多時不易理解
• 題外話：#define function(x) do{...}while(0) /* 避掉 ; 問題 */

參考：

1. http://blog.yam.com/swwuyam/article/11745212
2. GCC: An Inline Function is As Fast As a Macro