# 2020q3 Homework2 (quiz2)
contributed by < `CW-B-W` >
[github](https://github.com/CW-B-W/sysprog2020q3-quiz2)

###### tags: `sysprog2020`

## Outline
[TOC]

## 測驗`1`
### is_ascii
* MMM = `0x8080808080808080`
* 若任一個 char 超過 0x7F 則非 ascii
* 以 `c & 0x80` 判斷是否超過 `0x7F`
* 注意 `c` 範圍必須是 `0x00~0xFF`
* 若 `c` 範圍是 `0x00~0xFF` 且 `bit7` 為 1，則其超出 `0x7F`
* 將 8 個 char 合併在一起，同時做 `& 0x80`，則可得知 MMM 為 8 個 `0x80` 合併在一起

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

* 延伸問題1. `為何用 memcpy`
* 為何不用下列程式碼

        uint64_t* pPayload = (uint64_t*)(str+i);
        if (*pPayload & MMM)
            ...

* 若 str 沒有 `word-aligned` ， CPU 有可能會發出 `Alignment Trap`
* memcpy 會先將沒有 word aligned 的前幾 bytes 複製，之後再將有 aligned 的 words 複製
* 但這個問題下，複製量只有 `1 word`
* 只是為了保證不會出錯嗎? (*pPayload 若沒有 word aligned，可能會 error)
* 有效率優勢嗎?
### 延伸問題2: 判斷 string 裡是否都是 english alphabet
* 可參考 測驗`5` 裡 `VV2` 與 `VV3` ， 用到的判別法
* 詳細推導參考下方 測驗`5`

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

inline int isAlphabetChar(char c)
{
    return 
        (('A' <= c) && (c <= 'Z')) ||
        (('a' <= c) && (c <= 'z')) ;
}

/*
 * return whether s only contains english alphabets, i.e., 'a'~'z' or 'A'~'Z'
 */
int isAlphabetString(char *s, size_t n)
{
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)    
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(0x80)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - ('A' + 0)); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - ('Z' + 1));
            uint64_t a = *chunk + PACKED_BYTE(128 - ('a' + 0)); 
            uint64_t z = *chunk + PACKED_BYTE(128 - ('z' + 1));
            uint64_t isAlpha = (((A ^ Z) | (a ^ z)) & PACKED_BYTE(0x80));
            if (isAlpha != 0x8080808080808080) {
                return 0;
            }
        } else {
            return 0;
        }
    }
    
    k = n % 8;
    if (k)
        while (k--) {
            if (!isAlphabetChar(*s))
                return 0;
            s++;
        }
    return 1;
#undef PACKED_BYTE
}

* 延伸問題3.
* 目前不懂題意

## 測驗`2`
### haxchar2val
* MMM = `0x40`
* AAA = `3`
* BBB = `6`
* `letter` 的用途在於判別 `in` 是不是 `A~F or a~f`
* `a~f` 的 binary 為 `8'b1100_0xxx`
* `A~F` 的 binary 為 `8'b0100_0xxx`
* 兩者共通點為 `8'b0100_0000`
* `0~9` 的 binary 為 `8'b0011_xxxx`
* 故以 `MASK = 8'b0100_0000 = 0x40` 可確認是否為 `A~F` or `a~f` 且不為 `0~9`
* `(in + shift) & 0x0F` 分析
* 如果 `in = '0'~'9'` ，則 `in & 0x0F` 直接是答案
* 如果 `in = 'a'~'f'` ，則 `(in+0x09) & 0x0F` 是答案
* 如果 `in = 'A'~'F'` ，則 `(in+0x09) & 0x0F` 是答案
* 故 shift 為
* 當 `in = '0'~'9'` ， `shift = 0x00`
* 此時 `letter = 8'b0000_0000`
* 當 `in = 'a'~'f' or 'A'~'F'` ， `shift = 0x09`
* 此時 `letter = 8'b0100_0000`
* 綜合可得 `0x09 = (letter >> 3) | (letter >> 6)`

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}

### 延伸問題 - 32bit hex string to decimal
* 需注意 Machine 為 `Little Endian` or `Big Endian`
* 先將 8 個 char 分別用 hexchar2val 的方式轉成 hex value ， 在將此 8 個 values 合併在一個 uint32_t 裡面
* e.g. 輸入 `"0DEFACED"` ， 先將其轉為 `0x00_0D_0E_0F_0A_0C_0E_0D` ， 再合併為 `0x0DEFACED`
* 合併時需注意 `endian` 問題!!

#include <iostream>
#include <cstddef>
#include <cstring>
#include <cstdint>
#include <cassert>

using namespace std;

/* return true if your machine is little-endian */
bool isLittleEndian()
{
    const uint8_t a8[8] = {
        0x01, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00
    };
    assert((&a8[1] - &a8[0]) > 0); // make sure address of &a8[0] is before &a8[1]
    uint64_t* p64 = (uint64_t*)a8;
    return (*p64 == 1);
}

uint32_t hex2val(uint8_t in_vec[8])
{
    uint64_t in;
    memcpy(&in, (void*)in_vec, sizeof(uint64_t));
    const uint64_t letter = in & 0x4040404040404040;
    const uint64_t shift = (letter >> 3) | (letter >> 6);

    const uint64_t tmp = (in + shift) & 0x0F0F0F0F0F0F0F0F;

    uint32_t out = (
        (((tmp >>  0) & 0x0F) << 28) |
        (((tmp >>  8) & 0x0F) << 24) |
        (((tmp >> 16) & 0x0F) << 20) |
        (((tmp >> 24) & 0x0F) << 16) |
        (((tmp >> 32) & 0x0F) << 12) |
        (((tmp >> 40) & 0x0F) <<  8) |
        (((tmp >> 48) & 0x0F) <<  4) |
        (((tmp >> 56) & 0x0F) <<  0)
    );
    return out;
}

int main()
{
    cout << isLittleEndian() << endl;
    uint8_t in_vec[8] = {
        '0', 'D', 'E', 'F', 'A', 'C', 'E', 'D'
    };
    uint32_t dec = hex2val(in_vec);
    cout << dec << endl;
    return 0;
}

## 測驗`3`
### quickmod
* XXX = `0xFFFFFFFFFFFFFFFF`
* 須滿足 `floor(M * n / 2^64) = floor(n / d)` ， 故 `M = 2^64 / d` 。 因 `2^64` 超出 `uint64_t` ， 故先考慮取 `M = (2^64-1) / d` ， 但當 `n 為 d 的倍數` 時算出的 quotient 會少 1 ， 故需將 `M` 再加上一 。 得 `M = (2^64-1) / d + 1`

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{   uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

## 測驗`4`
### divisible
* YYY = `M - 1`
* 我還沒想透呢

bool divisible(uint32_t n)
{
    return n * M <= YYY;
}

## 測驗`5`
### strlower_vector
* `A = 8'b0100_0001` , `Z = 8'b0101_1010`
* `a = 8'b0110_0001` , `z = 8'b0111_1010`
* VV1 = `0x80`
* 如果 `bit7` 不為 1 ， 則判斷其非 `ascii`
* VV2 = `0` & VV3 = `-1`
* `A` 用來判斷是否 char 有 `>= 'A'`
* e.g. `'A' + 128 - 'A' = 128 + 0 = 8'b1000_0000` ， 因為 `bit7` 為 `1` ，故其`有`超過 `'A'`
* e.g. `'@' + 128 - 'A' = 128 - 1 = 8'b0111_1111` ， 因為 `bit7` 為 `0` ，故其`沒有`超過 `'A'`
* PS: `'@'` 為 `'A'` 在 ascii 上前一個字元
* `Z` 同理，但是要判斷有沒有 ` > 'Z'` ， 也就是有沒有 ` >= 'Z' + 1`
* 故 `VV2` 原型為 `c + 128 - ('A'+0)`
* 而 `VV3` 原型為 `c + 128 - ('Z'+1)`
* `A ^ Z` 用來判斷 是否 ` >= 'A'` 與 ` > 'Z'` 只有一個成立，若只有一個成立，則 `A ^ Z = true`，即 `c為需要處理的 byte`；反之若同時成立或同時不成立，i.e. `c > 'Z'` or `c < 'A'` ，則 `A ^ Z = false`，即 `c 為不需處理的 byte`
* 延伸用法可見 測驗`1`--延伸問題`2`
* VV4 = `0x80`
* 因為判斷是否 `'A' <= c <= 'Z'` 只需要 `bit7` ， 故將 `bit6~bit0` 全設為 0

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

* 延伸問題2. 將 `char str[]` 改為 `char* str`
* C 語言規格書 [ISO/IEC 9899:1999](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) p.130
* 感謝 `Rsysz` 同學，因為我參考了他的回答，找到了頁數
> On the other hand, the declaration
> char* p = "abc";
> defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type "array of char" with length 4 whose elements are initialized with a character string literal. If an attempt is made to use p to
modify the contents of the array, the behavior is undefined.

* 改成 `char* str` 會 `segmentation fault`
* 通常此時 str 指向 `read-only` 的 `text section` (string literal 一般存在此) ， 因為 `strlower_vector` 會更動到 `str` 裡面的值，故會造成嘗試寫入被保護的 `text section` 而導致 `segmentation fault`
* Reference: [Stackoverflow: Why do I get a segmentation fault when writing to a “char *s” initialized with a string literal, but not “char s[]”?](https://stackoverflow.com/questions/164194/why-do-i-get-a-segmentation-fault-when-writing-to-a-char-s-initialized-with-a)
* Reference: [Wikipedia: Data segment](https://en.wikipedia.org/wiki/Data_segment)
* 用 `char str[]` 則會在 `stack` 新配置一塊空間，再將 `string literal` 內容 copy 到此空間，故沒有問題
## 測驗`6`
### Single Number II
* KKK = `~higher`
* 我還沒想透呢
* JJJ = `~lower`
* 我還沒想透呢
* 雖然還沒想透，但這篇的實作法直觀上比較容易理解 [【leetcode】在一堆每个数字都出现三次的数组中，找到那个只出现一次的数(Single Number II)](https://blog.csdn.net/exceptional_derek/article/details/17636909)

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= KKK;
        higher ^= nums[i];
        higher &= JJJ;
    }
    return lower;
}