# 2021q1 Homework6 (quiz6)
contributed by < [`linD026`](https://github.com/linD026) >
###### tags: `linux2021`
> [2021 年第 6 週隨堂測驗題目](https://hackmd.io/@sysprog/linux2021-quiz6)
---
## 0 進度
- [ ] 測驗 1
- [ ] 解釋程式碼以及改進
- [ ] 階乘運算十進位輸出改進
- [ ] Karatsuba algorithm 和 Schönhage–Strassen algorithm
- [ ] Linux kernel 中的大數運算
- [ ] 測驗 2
- [ ] 解釋程式碼
- [ ] 研讀 Linux 核心原始程式碼
- [ ] 測驗 3
- [ ] 解釋程式碼以及改進
- [ ] interleaving 問題
- [ ] 研讀 A (Bare-Bones) User-Level Thread Library 以及實驗
---
## 測驗 1
### 解釋程式碼以及改進
* `struct bn`
```graphviz
digraph main {
node [shape = record]
rankdir = LR
label = "struct bn"
subgraph cluster {
label = "2 indexs of array"
temp [label = "64 bits (UTYPE_TMP)|{<h>32 bits(UTYPE)| 32 bits(UTYPE)}"]
}
array -> temp
}
```
```cpp
/* how large the underlying array size should be */
#define UNIT_SIZE 4
/* These are dedicated to UNIT_SIZE == 4 */
#define UTYPE uint32_t
#define UTYPE_TMP uint64_t
#define MAX_VAL ((UTYPE_TMP)0xFFFFFFFF)
#define BN_ARRAY_SIZE (128 / UNIT_SIZE) /* size of big-numbers in bytes */
/* bn consists of array of TYPE */
struct bn {
UTYPE array[BN_ARRAY_SIZE];
};
```
* `FORMAT_STRING`
> **Linux Programmer's Manual - printf(3)**
> The unsigned int argument is converted to unsigned octal (o), unsigned decimal (u), or unsigned hexadecimal (x and X) notation.
```cpp
#define FORMAT_STRING "%.08x"
```
會在 `bn_to_str` 函式 `UTPYE` 轉換至 `char` 實用到：
```cpp
...
sprintf(&str[i], FORMAT_STRING, n->array[j]);
...
```
* `bn_from_int`
把 UTYPE_TMP 型態的 i 儲存進 struct bn 。
其中原程式碼對於儲存位置是假定為 little-endian ，亦即 n->array[0] = i; 等操作。
然而電腦也有可能為 big-endian ，因此我在儲存前先做了處理。
```cpp
static inline void bn_from_int(struct bn *n, UTYPE_TMP i) {
bn_init(n);
/* FIXME: what if machine is not little-endian? */
const union {
uint16_t set;
char get[2];
} _type = {.set = 0x1122};
int start = 0;
int next = 1;
if (_type.get[0] == 0x11) {
start = BN_ARRAY_SIZE - 1;
next = start - 1;
}
n->array[start] = i;
/* bit-shift with U64 operands to force 64-bit results */
UTYPE_TMP tmp = i >> 32;
n->array[next] = tmp;
}
```
所謂的 big endian 是指資料儲存於記憶體的方向與記憶體位址不同。也就是說資料的最高位元組是放置在低記憶體位址。
```graphviz
digraph {
rankdir = LR
node [shape = record]
label = "Big Endian"
memory [label = "memory address|{low\n0x33|...\n0x22|high\n0x11}"]
data [label = "data|{low\n0x11|...\n0x22|high\n0x33}"]
data -> memory
}
```
而 little endian 則是兩者方向相同。
```graphviz
digraph {
rankdir = LR
node [shape = record]
label = "Little Endian"
memory [label = "memory address|{low\n0x11|...\n0x22|high\n0x33}"]
data [label = "data|{low\n0x11|...\n0x22|high\n0x33}"]
data -> memory
}
```
> [Big-Endian 與 Little-Endian 的差異與判斷程式碼](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/)
:::info
至於 array[0] 為何就會是低記憶體位址？
規格書有定義到：
> **6.5.8 Relational operators**
> **5** If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values.
而關於實作部份，則會涉及 [Memory Address Decoding](https://ece-research.unm.edu/jimp/310/slides/8086_memory2.html) 。
:::
```cpp
void bn_to_str(struct bn *n, char *str, int nbytes) {
/* index into array - reading "MSB" first -> big-endian */
int j = BN_ARRAY_SIZE - 1;
int i = 0; /* index into string representation */
/* reading last array-element "MSB" first -> big endian */
while ((j >= 0) && (nbytes > (i + 1))) {
sprintf(&str[i], FORMAT_STRING, n->array[j]);
i += (2 *
UNIT_SIZE); /* step UNIT_SIZE hex-byte(s) forward in the string */
j -= 1; /* step one element back in the array */
}
/* Count leading zeros: */
for (j = 0; str[j] == '0'; j++)
;
/* Move string j places ahead, effectively skipping leading zeros */
for (i = 0; i < (nbytes - j); ++i)
str[i] = str[i + j];
str[i] = 0;
}
```
```cpp
/* Decrement: subtract 1 from n */
void bn_dec(struct bn *n) {
for (int i = 0; i < BN_ARRAY_SIZE; ++i) {
UTYPE tmp = n->array[i];
UTYPE res = tmp - 1;
n->array[i] = res;
// COND;
if (!(res > tmp)) break;
}
}
void bn_add(struct bn *a, struct bn *b, struct bn *c) {
int carry = 0;
for (int i = 0; i < BN_ARRAY_SIZE; ++i) {
UTYPE_TMP tmp = (UTYPE_TMP) a->array[i] + b->array[i] + carry;
carry = (tmp > MAX_VAL);
c->array[i] = (tmp & MAX_VAL);
}
}
```
```cpp
void bn_mul(struct bn *a, struct bn *b, struct bn *c) {
struct bn row, tmp;
bn_init(c);
for (int i = 0; i < BN_ARRAY_SIZE; ++i) {
bn_init(&row);
for (int j = 0; j < BN_ARRAY_SIZE; ++j) {
if (i + j < BN_ARRAY_SIZE) {
bn_init(&tmp);
// III;
UTYPE_TMP intermediate = a->array[i] * (UTYPE_TMP) b->array[j];
bn_from_int(&tmp, intermediate);
lshift_unit(&tmp, i + j);
bn_add(&tmp, &row, &row);
}
}
bn_add(c, &row, c);
}
}
```
```cpp
bool bn_is_zero(struct bn *n) {
for (int i = 0; i < BN_ARRAY_SIZE; ++i)
if (n->array[i])
return false;
return true;
}
```
```cpp
/* Copy src into dst. i.e. dst := src */
void bn_assign(struct bn *dst, struct bn *src) {
for (int i = 0; i < BN_ARRAY_SIZE; ++i)
dst->array[i] = src->array[i];
}
```
### 階乘運算十進位輸出改進
```cpp
#define NORMAL_SIZE(array, size) \
do { \
for (int _i = 0; _i < BN_ARRAY_SIZE; _i++) { \
if (!array[_i]) { \
size = _i - 1; \
break; \
} \
} \
} while (0)
#define digit_div(n1, n0, d, q, r) \
__asm__("divq %4" : "=a"(q), "=d"(r) : "0"(n0), "1"(n1), "rm"(d))
#define SWAP(A, B) \
do { \
typeof(A) tmp = A; \
A = B; \
B = tmp; \
} while (0)
static UTYPE ddivi(struct bn *n, size_t size) {
size_t tsize = size;
UTYPE s1 = 0;
do {
UTYPE q, r;
if (s1 == 0) {
UTYPE s0 = n->array[tsize];
q = s0 / 10;
r = s0 % 10;
} else {
UTYPE_TMP s0 = s1;
s0 = s0 << 32;
s0 += n->array[tsize];
q = s0 / 10;
r = s0 % 10;
}
n->array[tsize] = q;
s1 = r;
tsize--;
} while (tsize != -1);
return s1;
}
static const char radix_chars[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
void bn_2_str(struct bn *n, char *out) {
size_t size = 0;
char *const head_out = out;
NORMAL_SIZE(n->array, size);
struct bn _n = *n;
do {
// extract
UTYPE s1 = ddivi(&_n, size);
*out++ = radix_chars[s1];
} while(!bn_is_zero(&_n));
char *f = out - 1;
/* Eliminate leading (trailing) zeroes */
while (*f == '0')
--f;
/* NULL terminate */
f[1] = '\0';
/* Reverse digits */
for (char *s = head_out; s < f; ++s, --f)
SWAP(*s, *f);
out = head_out;
}
```
### Karatsuba algorithm 和 Schönhage–Strassen algorithm
### Linux kernel 中的大數運算
---
## 測驗 2
### 解釋程式碼
### 研讀 Linux 核心原始程式碼
---
## 測驗 3
### 解釋程式碼以及改進
### interleaving 問題
### 研讀 A (Bare-Bones) User-Level Thread Library 以及實驗
Sign in with Wallet
Connect another wallet