# 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` 合併在一起
```CPP
#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`
* 為何不用下列程式碼
```CPP
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`
```CPP
#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)`
```CPP
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` 問題!!
```CPP
#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`
```CPP
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`
* 我還沒想透呢
```CPP
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
```CPP
#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)
```CPP
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