# 2019q1 Homework3 (review)
contributed by < `F74021200` >

[第三週測驗題(上)-測驗一](https://hackmd.io/s/S1weT4iLE#)

cst_memcmp

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 & (((diff - 1) & ~diff) >> 8)) | diff;
        } while (pm1 != m1);
    }
    return ((res - 1) >> 8) + (res >> 8) + 1;
}

由 [c99 standard-page 85](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) : The result of E1 >> E2 is E1 right-shifted E2 bit positions.If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of $E1/2^{E2}$.If E1 has a signed type and a negative value, the resulting value is implementation-defined. 因此，非負整數作 right shift n bits 時，是採用除法定義；但對於負整數之 right shift 則是 implementation-defined ，所以，對於負整數之 right shift 是 [logical right shift](https://en.wikipedia.org/wiki/Logical_shift) 還是 [arithmetic right shift](https://en.wikipedia.org/wiki/Arithmetic_shift) 或是[其他種 right shift](https://en.wikipedia.org/wiki/Circular_shift) ，取決於編譯器的實作，[由 gcc 之說明](https://gcc.gnu.org/onlinedocs/cpp/Implementation-defined-behavior.html#Implementation-defined-behavior) 知： ...implementation-defined. This term means that the implementation is free to do what it likes, but must document its choice and stick to it. 並[由此](https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html#Integers-implementation) 知： Signed ‘>>’ acts on negative numbers by sign extension. 此適用於 C90 6.3, C99 與 C11 6.5 ，因此，在使用 c99 標準時，有號負數在作 right shift 時，需要 sign extension

diff 之值域： $diff\in\\
\{\ 11111111\ 11111111\ 11111111\ 11111111\ \}\ \cup\ \\\{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111110 \geq x \geq 11111111\ 11111111\ 11111111\ 00000001\ \}\ \cup\ \\\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}\ \cup\\ \\\{\ 00000000\ 00000000\ 00000000\ 00000001\ \}\cup\\\{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000010 \leq x \leq 00000000\ 00000000\ 00000000\ 11111111\ \}$

對應以上之 diff 之值，
diff - 1 之值域： $diff - 1 \in\\ \\\{\ 11111111\ 11111111\ 11111111\ 11111110\ \}\ \cup\\\{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111101 \leq x \leq 11111111\ 11111111\ 11111111\ 00000000\ \}\ \cup\ \\\{\ 11111111\ 11111111\ 11111111\ 11111111\ \}\ \cup\\ \{\ 00000000\ 00000000\ 00000000\ 00000000\ \}\ \cup\\\{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000001 \leq x \leq 00000000\ 00000000\ 00000000\ 11111110\ \}$

~diff 之值域：
$\sim diff\in\\
\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}\ \cup\ \\\{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000001 \leq x \leq 00000000\ 00000000\ 00000000\ 11111110\ \}\ \cup\ \\\{\ 11111111\ 11111111\ 11111111\ 11111111\ \}\ \cup\\ \\\{\ 11111111\ 11111111\ 11111111\ 11111110\ \}\cup\\\{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111101 \leq x \leq 11111111\ 11111111\ 11111111\ 00000000\ \}$

### ((diff - 1) & ~diff) >> 8

#### case1.
If
$diff \in \{\ 11111111\ 11111111\ 11111111\ 11111111\ \}$
then
$diff - 1 \in\{\ 11111111\ 11111111\ 11111111\ 11111110\ \}$
$\sim diff \in\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$

$((diff - 1)\ \&\ \sim\ diff)\ >>\ 8 \in\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$

#### case2.
If $diff\\\in \{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111110 \geq x \geq 11111111\ 11111111\ 11111111\ 00000001\ \}$
then
$diff - 1 \in\\\{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111101 \leq x \leq 11111111\ 11111111\ 11111111\ 00000000\ \}$
$\sim diff \in\ \\\{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000001 \leq x \leq 00000000\ 00000000\ 00000000\ 11111110\ \}$

$((diff - 1)\ \&\ \sim diff)\ >>\ 8 \in\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$

#### case3.
If
$diff\in \{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$
then
$diff - 1 \in\{\ 11111111\ 11111111\ 11111111\ 11111111\ \}$
$\sim diff \in\{\ 11111111\ 11111111\ 11111111\ 11111111\ \}$

$((diff - 1)\ \&\ \sim\ diff)\ >>\ 8 \in\{\ 11111111\ 11111111\ 11111111\ 11111111\ \}$

#### case4.
If
$diff\in \{\ 00000000\ 00000000\ 00000000\ 00000001\ \}$
then
$diff - 1 \in\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$
$\sim diff \in\{\ 11111111\ 11111111\ 11111111\ 11111110\ \}$

$((diff - 1)\ \&\ \sim\ diff)\ >>\ 8 \in\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$

#### case5.
If $diff\\\in\{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000010 \leq x \leq 00000000\ 00000000\ 00000000\ 11111111\ \}$
then
$diff - 1 \in\\\{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000001 \leq x \leq 00000000\ 00000000\ 00000000\ 11111110\ \}$
$\sim diff \in\ \\\{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111101 \leq x \leq 11111111\ 11111111\ 11111111\ 00000000\ \}$

$((diff - 1)\ \&\ \sim diff)\ >>\ 8 \in\{\ 00000000\ 00000000\ 00000000\ 00000000\ \}$

### 由以上五點知：

$Let\ f(diff) = ((diff - 1) \& \sim diff)\ >>\ 8,\\
A = \{\ x\ |\ 11111111\ 11111111\ 11111111\ 11111111 \geq x \geq 11111111\ 11111111\ 11111111\ 00000001\ \},\\
B = \{\ x\ |\ 00000000\ 00000000\ 00000000\ 00000001 \leq x \leq 00000000\ 00000000\ 00000000\ 11111111\ \},\\and\ diff\ \in\ A\cup B\cup\{00000000\ 00000000\ 00000000\ 00000000\}
\\then\\f(diff) =\begin{cases}\ 11111111\ 11111111\ 11111111\ 11111111\ , & \text{if diff = 00000000 00000000 00000000 00000000} \\
\ 00000000\ 00000000\ 00000000\ 00000000\ , & \text{otherwise}\end{cases}$

### res = (res & f(diff)) | diff

$Let\ g(res,\ diff) = (res\ \&\ f(diff))\ |\ diff\\then\\g(res,\ diff)=\begin{cases}res, & \text{if diff = 00000000 00000000 00000000 00000000} \\diff, & \text{otherwise}\end{cases}$

當 $diff = 00000000\ 00000000\ 00000000\ 00000000$ 時， res 會等於進這次 loop 前的 res ，當 $diff\ \in A\cup B$ ， res 會等於這次 loop 的 diff 。

### 所以，每次遞迴，當比對的 byte 數值相同時， res 會等於進這次 loop 前的 res 值，當比對的 byte 不相同時， res 會等於這次 loop 的差值。也就是說，若比對的 n byte 中，每個 byte 都相同時， res 會等於 res 的初始值， 0 ；若比對的 n byte 中，出現不同的 byte 時， res 之值會等於最後一次兩 byte 比對發生不同時的兩 byte 之差值。

### 另外，由以上等式可知， res 的值域與 diff 相同。

### 最後討論回傳值：
### ((res - 1) >> 8) + (res >> 8) + 1

#### case1.
If
$res\ =\ 00000000\ 00000000\ 00000000\ 00000000,\\then\\res\ -\ 1\ =\ 11111111\ 11111111\ 11111111\ 11111111\\(res\ -\ 1)\ >>\ 8\ =\ 11111111\ 11111111\ 11111111\ 11111111\\res\ >>\ 8\ =\ 00000000\ 00000000\ 00000000\ 00000000\\((res\ -\ 1)\ >>\ 8)\ +\ (res\ >>\ 8)\ +\ 1\\=\ -1\ +\ 0\ +\ 1\ =\ 0$

#### case2.
If
$res\ \in\ A,\\then\\res\ -\ 1\ \in\ (A\cup\{\ 11111111\ 11111111\ 11111111\ 00000000\})\setminus \{11111111\ 11111111\ 11111111\ 11111111\}\\(res\ -\ 1)\ >>\ 8\ =\ 11111111\ 11111111\ 11111111\ 11111111\\res\ >>\ 8\ =\ 11111111\ 11111111\ 11111111\ 11111111\\((res\ -\ 1)\ >>\ 8)\ +\ (res\ >>\ 8)\ +\ 1\\=\ -1\ +\ (-1)\ +\ 1\ =\ -1$

#### case3.
If
$res\ \in\ B,\\then\\res\ -\ 1\ \in\ (B\cup\{\ 00000000\ 00000000\ 00000000\ 00000000\})\setminus \{00000000\ 00000000\ 00000000\ 11111111\}\\(res\ -\ 1)\ >>\ 8\ =\ 00000000\ 00000000\ 00000000\ 00000000\\res\ >>\ 8\ =\ 00000000\ 00000000\ 00000000\ 00000000\\((res\ -\ 1)\ >>\ 8)\ +\ (res\ >>\ 8)\ +\ 1\\=\ 0\ +\ 0\ +\ 1\ =\ 1$