2020q3 Homework2 (quiz2)

contributed by < ZhuMon >

tags: sysprog2020 quiz

2020q3 第 2 週測驗題

Table of Contents

• 2020q3 Homework2 (quiz2)
  • Table of Contents
  • 測驗 1
    • 題目
    • 解答
    • 延伸問題
  • 測驗 2
    • 題目
    • 解答
  • 測驗 3
    • 題目
    • 解答
  • 測驗 4
    • 題目
    • 解答
  • 測驗 5
    • 題目
  • 測驗 6

---

測驗 1

題目

#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;
}

解答

• MMM = (d) 0x8080808080808080
• 從原始程式碼可知，is_ascii 藉由將 byte 與 0x80 做 and，確認 byte 的第一個 bit 是否為 1，藉此確認是否為 ASCII 的有效字元
• 改寫後，為了達成一次比對 8 個 byte，一次將 8 個 byte 存到 payload (第 12 行)，因此 mask 也要擴展，從只能判斷 1 個 byte 的 0x80 擴展到可以比對 8 個 byte 的 0x8080808080808080

延伸問題

1. 為何使用 memcpy?
   根據 glibc 2.33 的 memcpy.c，將註解去掉後，如下

   ​​​​#include <string.h>
   ​​​​#include <memcopy.h>
   
   ​​​​#ifndef MEMCPY
   ​​​​# define MEMCPY memcpy
   ​​​​#endif
   
   ​​​​void *
   ​​​​MEMCPY (void *dstpp, const void *srcpp, size_t len)
   ​​​​{
   ​​​​  unsigned long int dstp = (long int) dstpp;
   ​​​​  unsigned long int srcp = (long int) srcpp;
   
   ​​​​  if (len >= OP_T_THRES)
   ​​​​  {
   ​​​​      len -= (-dstp) % OPSIZ;
   ​​​​      BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
   
   ​​​​      PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
   
   ​​​​      WORD_COPY_FWD (dstp, srcp, len, len);
   
   ​​​​  }
   ​​​​  BYTE_COPY_FWD (dstp, srcp, len);
   
   ​​​​  return dstpp;
   ​​​​}
   ​​​​libc_hidden_builtin_def (MEMCPY)
   

   以下幾個 macro 會根據不同的架構而有所不同，在 glibc 的 generic memcopy.h 定義如下

   ​​​​#define OP_T_THRES      16
   ​​​​#define OPSIZ   (sizeof(op_t))
   ​​​​#define op_t    unsigned long int	
   

   • memcpy 解釋
     若是要複製長度大於 OP_T_THRES 的記憶體，先將沒有對齊的資料複製完成後 (line17)，便可以直接以 Page 作為單位快速的複製記憶體(PAGE_COPY_FWD_MAYBE)，接著以 word 作為單位複製剩下的記憶體，然後複製剩下的 byte

   • memcopy.h 對於 BYTE_COPY_FWD(dst_bp, src_bp, nbytes) 的描述為

     Copy exactly NBYTES bytes from SRC_BP to DST_BP,
     without any assumptions about alignment of the pointers.

     也就是說，BYTE_COPY_FWD 會從 src_bp 開頭逐一複製 nbytes 個 byte 到 dst_bp 的開頭 (另一個 macro BYTE_COPY_BWD 則是將來源位址和目標位址都視為結束位址來複製)

     ​​​​​​​​#define BYTE_COPY_BWD(dst_ep, src_ep, nbytes)				      \
     ​​​​​​​​  do									      \
     ​​​​​​​​    {									      \
     ​​​​​​​​      size_t __nbytes = (nbytes);					      \
     ​​​​​​​​      while (__nbytes > 0)						      \
     ​​​​​​​​        {								      \
     ​​​​​​​​          byte __x;							      \
     ​​​​​​​​          src_ep -= 1;							      \
     ​​​​​​​​          __x = ((byte *) src_ep)[0];					      \
     ​​​​​​​​          dst_ep -= 1;							      \
     ​​​​​​​​          __nbytes -= 1;						      \
     ​​​​​​​​          ((byte *) dst_ep)[0] = __x;					      \
     ​​​​​​​​        }								      \
     ​​​​​​​​    } while (0)
     

---

2. 給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母
   查看 ASCII Table，可以知道英文大小寫字母所對應的 ASCII code 為 0x41~0x5A, 0x61~0x7A，以二進位表示如下

   Char	Bin	Hex
   A	0100 0001	0x41
   Z	0101 1010	0x5A
   -	––	-
   a	0110 0001	0x61
   z	0111 1010	0x7A

   以 * 代表 don't care

   觀察可知，英文字母的 ASCII code 前兩個 bit 必為 01，但是在 01** ****的範圍中，{01000000, 01011011 ~ 01100000, 01111011 ~ 01111111} 這三個區間內所對應的字元不是英文字母，總共有 12 個 (

   $2^6-26\ast 2=12$)

   繼續觀察，將上述 12 個字元以第三個 bit 分成兩類，可以再歸納出三組

   1. 01*0 0000
   2. 01*1 1011
   3. 01*1 11**

   hex	bin	hex	bin
   0x40	0100 0000	0x60	0110 0000
   0x5b	0101 1011	0x7b	0111 1011
   0x5c	0101 1100	0x7c	0111 1100
   0x5d	0101 1101	0x7d	0111 1101
   0x5e	0101 1110	0x7e	0111 1110
   0x5f	0101 1111	0x7f	0111 1111

   因此只要 ASCII code 同時符合以下四點，便為英文字母

   1. (char & 11000000) == 01000000
   2. (char & 00011111) != 0
   3. (char & 00011111) != 00011011
   4. (char & 00011100) != 00011100

   但是要在單個 byte 實作很簡單，多個 byte 同時判斷就很困難

   TODO: 第五題似乎有較好的解決方法

---

測驗 2

題目

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

已知 in 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。
預期 hexchar2val('F') 和 hexchar2val('f') 回傳 15，且 hexchar2val('0') 回傳 0，其他輸入都有對應的數值。

解答

MASK = 0x40
AAA = 3
BBB = 6

1. 從結尾回推
   從第 5 行的 return 值可以看到 (in + shift) 與 0xf 做 mask，因此 return 值只會在 0~15 之間。

   • 數字部分
     因為數字的 ASCII code 介於 0x30~0x39，因此 shift 只要不會影響 in 的後 4 bit，便可以使數字部分達成目的，預計 shift 為 0x?0
   • 英文字母
     要將 0x61 (a) 和 0x41 (A) 對應到 10 (b'1010)，因此最簡單的想法就是將 shift 設為 9 (0x09)

   明顯兩個規則矛盾，因此 shift 應該符合下述條件

   • shift = 0x?0, if in
     $\in$ {'0', '1', …, '9'}
   • shift = 0x?9, if in
     $\in$ {'A', …, 'F', 'a', …, 'f'}

2. 判斷 letter 為何
   從字面意義大概猜出 letter 代表英文字母，從選項來看，可以知道要將 in 的前 4 bit 的某些 bit 取出來

   • (a) 0x10
   • (b) 0x20
   • (c) 0x40
   • (d) 0x60
   • (e) 0x80

   而可以判斷英文字母與數字的 bit 為第 2 個 bit 和第 4 個 bit

   • 數字: 0011 xxxx
   • 大寫: 0100 xxxx
   • 小寫: 0110 xxxx

   稍微瞄到下一行 (line 4)，shift 會以 letter 來決定值，而我們的 shift 在 in 為數字時，不需要有值，因此應該以第 2 個 bit 作為 mask，也就是

   • MASK = (c) 0x40

3. AAA & BBB
   由於前面已經知道在 in 為英文字母時，letter 為 b'0100 0000，而要讓 shift 的後 4 bit 為 9 (b'0000 1001)，必須讓 letter 向左位移 3 位和向左位移 6 位，因此可以得到

   • AAA = 3
   • BBB = 6

---

測驗 3

題目

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;
}

解答

為了得到餘數，function 必須返回

$\begin{array}{rl}n\mathrm{\%}d& =n-x\times d\end{array}$

其中

$x$ 為

$n/d$ 的整數部分，也就是 quotient，將

$M={\displaystyle \frac{XXX}{d}}+1$ 帶入下式

$\begin{array}{rl}x& =quotient\\ & ={\displaystyle \frac{M\times n}{2^{64}}}\\ & ={\displaystyle \frac{({\displaystyle \frac{XXX}{d}}+1)\times n}{2^{64}}}\mathrm{重}\mathrm{新}\mathrm{排}\mathrm{列}\mathrm{後}\\ & =n\times {\displaystyle \frac{{\displaystyle \frac{XXX}{d}}+1}{2^{64}}}\end{array}$
對照題目可知 (XXX / d) + 1 便是 2⁶⁴/d，而 XXX 最接近的選項便是 0xFFFFFFFFFFFFFFFF

> 關於為甚麼要先除以 d 再加 1，可以參考 @cmwchw 的解說

也就是說

$n\times {\displaystyle \frac{{\displaystyle \frac{XXX}{d}}+1}{2^{64}}}=n\times {\displaystyle \frac{{\displaystyle \frac{2^{64}}{d}}}{2^{64}}}$

設

$Q={\displaystyle \frac{n}{d}}$

$=>{\displaystyle \frac{XXX}{2^{64}}}Q+{\displaystyle \frac{n}{2^{64}}}=Q$

由於

$n<<2^{64}$

所以

${\displaystyle \frac{n}{2^{64}}}$ 可以捨去

$=>{\displaystyle \frac{XXX}{2^{64}}}Q=Q$

$XXX=2^{64}$

---

測驗 4

題目

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

判斷 n 是否被 d 整除

解答

將 M 帶入後可得

$n\times ({\displaystyle \frac{2^{64}-1}{d}}+1)\le YYY$
…

將 n = 1 帶入，可以得到選項 (a) (b) (e) 都矛盾，因此只有可能是

$M-1$ 或

$M>>1$
試過所有值(0~2³²-1)後發現兩者依舊可以達成目的，懷疑等號右方只要小於

$M$ 便可以達成目的

---

測驗 5

題目

#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);
}

---

測驗 6