考慮到 memcmp [1] 一種實作如下: (行為和 ISO C90 有出入)

#include <stdint.h>
#include <stddef.h>
int memcmp(const uint8_t *m1, const uint8_t *m1, size_t n) {
    for (size_t i = 0; i < n; ++i ) {
        int diff = m1[i] - m2[i];
        if (diff != 0) return (diff < 0) ? -1 : +1;
    }
    return 0;
}

我們可能因此承受 information leakage [2] 的風險，於是著手避免使用 conditional branching 一類的指令，從而避免 side-channel attack [3]。

為了避免 conditional branch 指令的出現，我們可將 (res > 0) - (res < 0) 替換為 ((res - 1) >> 8) + (res >> 8) + 1。隨後我們實作下方功能等價但避免 branch 的 memcmp:

#include <stdint.h>
#include <stddef.h>
int cst_memcmp(const void *m1, const void *m2, size_t n) {
    const uint8_t *pm1 = (const uint8_t *) m1 + n;
    const uint8_t *pm2 = (const uint8_t *) m2 + n;
    int res = 0;
    if (n) {
        do {
            int diff = *--pm1 - *--pm2;
            res = (res & ((X & ~diff) >> 8)) | Y;
        } while (pm1 != m1);
    }
    return ((res - 1) >> 8) + (res >> 8) + 1;
}

注意: 在 Linux 核心內部的實作方式可見:

* [PATCH] crypto_memcmp: add constant-time memcmp (https://www.spinics.net/lists/linux-crypto/msg09542.html)
* Re: [PATCH] crypto_memcmp: add constant-time memcmp (https://www.spinics.net/lists/linux-crypto/msg09551.html)

請補完程式碼。

[1] http://man7.org/linux/man-pages/man3/memcmp.3.html
[2] https://en.wikipedia.org/wiki/Information_leakage
[3] https://en.wikipedia.org/wiki/Side-channel_attack

1. 解釋上述程式的原理，需要從機率統計的觀點分析;
    * 為何不能用事先計算好的表格呢？ (提示: cache 的影響)
    * 如何驗證程式正確以及 constant-time 呢？
2. 研讀下方論文並解說:
    * Remote timing attacks are practical (https://crypto.stanford.edu/~dabo/abstracts/ssl-timing.html)
    * A Lesson In Timing Attacks (or, Don’t use MessageDigest.isEquals) (https://codahale.com/a-lesson-in-timing-attacks/)
3. 在 Linux 核心找到這類 constant-time 的操作程式碼，予以解說和設計實驗;

考慮以下計算平方根的程式:

#include <stdint.h>
 
/* The algorithm uses the property that computing x² is trivial compared to
 * sqrt. It will search the biggest x so that x² <= v, assuming we compute
 * sqrt(v).
 */
int32_t sqrt_I2I(int32_t v) {
    uint32_t r = v;           // r = v - x²
    uint32_t b = 0x40000000;  // a²
    uint32_t q = 0;           // 2ax
    while (b > 0) {
        uint32_t t = q + b;  // t = 2ax + a²
        q >>= 1;             // if a' = a/2, then q' = q/2
        if (r >= t) {        // if (v - x²) >= 2ax + a²
            r -= t;          // r' = (v - x²) - (2ax + a²)
            q += b;          // if x' = (x + a) then ax' = ax + a²,
                             // thus q' = q' + b
        }
        b >>= 2;  // if a' = a/2, then b' = b / 4
    }
    return q;
}

該函式利用 (x + a)^2 = x^2 + 2ax + a^2 漸進找出平方根。不過上面的程式僅能處理整數，我們引入 fixed point [1] 來表達浮點數，改寫程式碼如下:

/* A fixed point is a 32 bit value with the comma between
 * the bits 15 and 16, where bit 0 is the less significant bit of the value.
 * FIXME: Larger numbers might cause overflow and rounding error.
 */
typedef int32_t fixed;

fixed sqrt_I2F(int32_t v) {
    if (!v) return 0;
    uint32_t r = v;
    uint32_t b = 0x40000000;
    uint32_t q = 0;
    while (b > 0) {
        uint32_t t = q + b;
        if (r >= t) {
            r -= t, q = t + b;
        }
        Q;
    }
    if (r >= q) ++q;
    return q;
}

請補完程式。

[1] http://www-inst.eecs.berkeley.edu/~cs61c/sp06/handout/fixedpt.html

1. 解釋上述程式碼運作原理，並找出類似的開放原始碼程式;
2. 上述 sqrt_I2F 函式存在 overflow 風險，請提出修正方案並驗證;

考慮以下 linked list 程式:

#include <stddef.h>
struct node {
    int data;
    struct node *next;
} *head;

void insert(struct node *newt) {
    struct node *node = head, *prev = NULL;
    while (node != NULL && node->data < newt->data) {
        prev = node;
        node = node->next;
    }
    newt->next = node;
    if (prev == NULL)
        head = newt;
    else
        prev->next = newt;
}

可透過以下 pointer to pointer 改寫 insert 函式，功能等價但更簡潔，如下:

void insert(struct node *newt)
{
    struct node **link = &head;
    while (*link && A)
        B;
    newt->next = *link;
    *link = newt;

請補完程式碼。