---
title: 2020q3 Homework2 (quiz2)
tags: sysprog
---
# 2020q3 Homework2 (quiz2)
contributed by < `TsundereChen` >
> GitHub: [TsundereChen/sysprog2020-quiz2](https://github.com/TsundereChen/sysprog2020-quiz2)
> [Homework2 (quiz2)](https://hackmd.io/@sysprog/B1zAbkAEP)
:::danger
進度落後太多，想辦法跟上
:notes: jserv
:::
## 測驗 `1`
題目 code
```clike=
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#define MMM 0x8080808080808080
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;
}
```
- 解釋上述程式的運作原理，特別是為何用到 `memcpy` 呢？
- `is_ascii` 會檢查 `str[]` 裡的字元是否都屬於 ASCII 字元
- 會從 `str[]` 的開頭判斷，每次比對 8 bytes
- ASCII 的範圍是 `0x00 ~ 0x7F` ，從 `0x80 ~ 0xFF` 都是 extended ASCII
- 這樣只要比較每個 byte 的最高 bit 是否為 1，只要是 1 就代表是 extended ASCII
- 由於一次比較一個 byte 太沒效率，能一次比較越多 byte 越好，所以使用 `uint64_t`
一次能比較 8 bytes
- 利用 `memcpy` 把 `str[]` 裡的 byte 複製進 `payload`
:::info
照 memcpy() 的 source code 看起來是每個 byte 依序複製
如果呼叫 memcpy() 的時候 len 是 constant 不知道編譯器會不會在這裡優化?
:::
[gcc/libgcc/memcpy.c](https://github.com/gcc-mirror/gcc/blob/master/libgcc/memcpy.c)
```clike=
/* Public domain. */
#include <stddef.h>
void *
memcpy (void *dest, const void *src, size_t len)
{
char *d = dest;
const char *s = src;
while (len--)
*d++ = *s++;
return dest;
}
```
:::info
越想越覺得這一段程式簡單到很奇怪，直到看了其他同學的筆記
才發現越來找到的版本實在太簡略了...
- [tsengsam/2020q3_homework2](https://hackmd.io/@shanvia/HJU75IXSw)
:::
[glibc/string/memcpy.c](https://github.com/lattera/glibc/blob/master/string/memcpy.c)
```clike=
#include <string.h>
#include <memcopy.h>
#undef memcpy
void *
memcpy (void *dstpp, const void *srcpp, size_t len)
{
unsigned long int dstp = (long int) dstpp;
unsigned long int srcp = (long int) srcpp;
/* Copy from the beginning to the end. */
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES)
{
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address manipulation,
as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known alignment of
DSTP. Number of bytes remaining is put in the third argument,
i.e. in LEN. This number may vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
return dstpp;
}
```
- 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
- ASCII 大寫英文字母: `0x41(A) ~ 0x5A(Z)`
- ASCII 小寫英文字母: `0x61(a) ~ 0x7A(z)`
- 承上，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
## 測驗 `2`
題目 code
```clike=
#define MASK 0x40
#define AAA 3
#define BBB 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;
}
```
- 解釋上述程式的運作原理
- 要把十六進制的符號轉成十進制
- 第一個變數 `letter` 用來確認 `in` 是數值還是是字符
- `in` 的數值範圍是
- `0 ~ 9`, `a ~ f`, `A ~ F`
- 而字符和數值的差別在，字符都有 `0x40` 這個 bit
- 所以要判別是否是字符，只要判斷 `0x40` 即可，所以 `MASK` 是這個值
- 接下來看輸入字符時輸入輸出的關係
```
0x42 (B) -> 11
0100 0010 -> 0000 1011
0x64 (d) -> 13
0110 0100 -> 0000 1101
```
- 我們知道 `letter` 只會有一個 bit 在 `0x40` 的位置
而從上面的輸入輸出中，我們可以發現
```
0000 [0]00[0]
```
這兩個 bit 數值和輸入時不一樣，而我們只要補上這兩個 bit，就能得到我們要的輸出
- 所以利用 `MASK` 來補足這兩個 bit
分別 right shift 3 bit 和 6 bit
- 將 `hexchar2val` 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
```clike=
void hexstr2val(uint8_t *in, int length) {
for (int i = 2; i < length; i++) {
const uint8_t letter = in[i] & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
printf("%d", (int)((in[i] + shift) & 0xf));
if (i != length - 1)
printf(" ");
}
printf("\n");
}
```
## 測驗 `3`
題目 code
```clike=
const uint32_t D = 3;
#define XXX
#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;
}
```
- 解釋上述程式的原理
- 閱讀 [jemalloc/include/jemalloc/internal/div.h](https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/div.h) 和 [jemalloc/src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c)
## 測驗 `4`
題目 code
```clike=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
## 測驗 `5`
題目 code
```clike=
#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.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);
}
int main()
{
/* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
char str[] =
"This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever. You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
int n = strlen(str);
strlower_vector(str, n);
puts(str);
}
```
- 解釋上述程式的原理
- 和測驗 `1` 相似，要一次處理多個 byte 的大小寫轉換
- 有個 MACRO `PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)`
- 最後的 `0x0101010101010101u`，拿去與其他數值相乘後，效果是把該數值擴展
- 舉例
`0x12 * 0x0101010101010101 = 0x1212121212121212`
- 裡面的 `0xff` 用來限制只能取數值最後的 8 bit
- 不論 `b` 傳了什麼數值，依舊只會被取到最後 8 bit
- `VV1` 行後面的註解是 `is ASCII?`
- 從這個註解推測這行程式是要用來判斷 `*chunk` 內的值是否在 ASCII 範圍內，還是屬於 extended ASCII
- 和測驗 `1` 一樣，只要判斷 `0x80` bit 即可
- 而如果我們要一次比對 8 bytes，利用 `PACKED_BYTE()` 將數值擴展
- 所以 `VV1 => 0x80`
- `VV2` 和 `VV3` 看起來沒什麼頭緒，試看看從後面想回來
- 從 `*chunk ^= mask` 可推測我們要利用 `mask` 完成大小寫轉換
- 看 `uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2`
- 我們已經知道大小寫轉換需要用到 `0x20` bit
- 而 mask 有經過兩個 right shift 運算，所以如果最後要用到 0x20 bit，我們得先給 0x80
- 從這裡可以得知 `VV4` 應該是 `0x80`，經過擴展後會是 `0x8080808080808080`，再去和 `A ^ Z` 運算
- 我們可以理解 `A ^ Z` 應該會用某種方式標記每個字元是大寫或小寫
- 如果傳入的是大寫字元
- `A ^ Z` 應該要是 `1xxx xxxx`
- 如果傳入的是小寫字元
- `A ^ Z` 應該要是 `0xxx xxxx`
- 我們觀察 `A` 和 `Z`
- `A = *chunk + PACKED_BYTE(128 - 'A' + VV2)`
- 等同於 `A = *chunk + PACKED_BYTE(63 + VV2)`
- 假設輸入大寫字元，那 `A` 的範圍應該在
- `010x xxxx + 0011 1111 >= 0100 0001 (A) + 0011 1111 = 1000 0000`
- `010x xxxx + 0011 1111 <= 0101 1010 (Z) + 0011 1111 = 1001 1001`
- 假設輸入小寫字元， `A` 的範圍應該在
- `011x xxxx + 0011 1111 >= 0110 0001 (a) + 0011 1111 = 1010 0000`
- `011x xxxx + 0011 1111 <= 0111 1010 (z) + 0011 1111 = 1011 1001`
- `Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3)`
- 和上面做一樣的操作，假設輸入大寫字元
- `010x xxxx + 0010 0110 >= 0100 0001 (A) + 0010 0110 = 0110 0111`
- `010x xxxx + 0010 0110 <= 0101 1010 (Z) + 0010 0110 = 1000 0000`
- 假設輸入小寫字元
- `011x xxxx + 0010 0110 >= 0110 0001 (a) + 0010 0110 = 1000 0111`
- `011x xxxx + 0010 0110 <= 0111 1010 (z) + 0010 0110 = 1010 0000`
- 回到上面的標記部分，如果是大寫的話， `A` 和 `Z` 應該要分別是 `1xxx xxxx` 和 `0xxx xxxx`
- 如果是小寫，則要都是 `1xxx xxxx` 或 `0xxx xxxx`
- 從上面能發現，小寫部分沒有問題都是 `1xxx xxxx`，但大寫部分只有要偵測的字元是 `Z` 的時候，變數 `Z` 的規律和其他不同
- 而變數 `A` 沒辦法調整，故只能調整變數 `Z`，讓 `Z` -1
- 故 `VV2 = 0`, `VV3 = -1`
- `將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為`
- 執行時發生 `segmentation fault`
- 從 C98/99 規格書中
- 6.4.5 String literals
- `2. A character string literal is a sequence of zero or more multibyte characters enclosed in double-quotes, as in "xyz". A wide string literal is the same, expect prefixed by the letter L.`
- `6. It is unspecified whether these arrays are distinct provided their elements have the appropriate values. **If the program attempts to modify such an array, the behavior is undefined**`
- 可以看到規格書內定義，更改 string literals 是 undefined behavior
## 測驗 `6`
```clike=
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;
}
```
Sign in with Wallet
Connect another wallet