# 2021q1 Homework6 (quiz6) contributed by < `secminhr` > ## Test1 ### Structure We can tell how number is stored in `bn` by observing the function `bn_from_int`. ```c static inline void bn_from_int(struct bn *n, UTYPE_TMP i) { bn_init(n); /* FIXME: what if machine is not little-endian? */ n->array[0] = i; /* bit-shift with U64 operands to force 64-bit results */ UTYPE_TMP tmp = i >> 32; n->array[1] = tmp; } ``` We can see that it stores **less significant bytes with a smaller index of array**. We can verify that using gdb. Create a simple test file with following `main` function: ```c int main() { struct bn num; bn_from_int(&num, 0xFFFFFFFFCCCCCCCC); return 0; } ``` If our observation is correct, then `num.array` should be `{0xCCCCCCCC, 0xFFFFFFFF, 0, 0,...}` after `bn_from_int`. Let's see if it is true. ``` (gdb) b main Breakpoint 1 at 0x11bd: file test.c, line 24. (gdb) r Starting program: /home/ubuntu/week6/a.out Breakpoint 1, main () at test.c:24 24 int main() { (gdb) n 26 bn_from_int(&num, 0xFFFFFFFFCCCCCCCC); (gdb) n 27 return 0; (gdb) p/x num.array $2 = {0xcccccccc, 0xffffffff, 0x0 <repeats 30 times>} ``` ### COND ```c /* Decrement: subtract 1 from n */ static 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; } } ``` The execution flow of `bn_dec` can be separated in 2 cases: 1. `n->array[0]` is not 0 In this case, `res` will be less than `tmp`, and we have to break the loop in `COND`, so ```c if (res < tmp) { break; } ``` 2. `n->array[0]` is 0 If `n->array[0]` is 0, then we need to use a borrow and `n->array[0]` should be 0xFFFFFFFF. So `COND` should do no work and let the loop keeps going to achieve borrowing behaviour. `0-1` in unsigned arithmetic will be the biggest number it can represent, 0xFFFFFFFF in this case, so we don't have to deal with that. We can now conclude that `COND` = `if (res < tmp) break`. The closest answer is `if (!(res > tmp)) break`. **The answer is `(c)`**. :::info Note that `res < tmp` and `!(res > tmp)` does not give the same result when `res == tmp`. However, `res == tmp` will never happen in this case, so they can be used interchangeably. ::: ### III ```c static 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; bn_from_int(&tmp, intermediate); lshift_unit(&tmp, i + j); bn_add(&tmp, &row, &row); } } bn_add(c, &row, c); } } ``` The process of `bn_mul` in decimal would look like this: ``` (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) 981 981 981 981 981 981 769 --> 769 --> 769 --> 769 --> 769 --> 769 ------ ------ ------ ------ ------ ------ 9 729 8829 8829 08829 008829 (1, 0) (1, 1) (1, 2) (1, 3) (1, 4) 981 981 981 981 981 769 769 769 769 769 ------ --> ------ --> ------ --> ------ --> ------ 008829 008829 008829 008829 008829 6 486 5886 5886 05886 (2, 1) (2, 2) (2, 3) 981 981 981 769 769 769 ------ --> ------ --> ------ 008829 008829 008829 05886 05886 05886 7 567 6867 ...... ``` `III` is the only place that can give out `intermediate`, and we know that in each iteration `intermediate` should be `a->array[i] * b->array[j]`. Therefore, `III` is `UTYPE_TMP intermediate = a->array[i] * (UTYPE_TMP) b->array[j]` **The answer is `(c)`** Two things worth noting: 1. We cast the type of `b->array` to `UTYPE_TMP`, otherwise, the result of multiplication might be trimmed. (since the result might exceed 4 bytes) 2. The type of `intermediate` is also `UTYPE_TMP` to hold the result. ### Structure revisit In [the previous section](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#Structure), we've figured out how `bn` stores a number. In this section, I'll show a more abstract view of `bn`. The declaration of `bn` is list below: ```c /* bn consists of array of TYPE */ struct bn { UTYPE array[BN_ARRAY_SIZE]; }; ``` Since we know that `bn` stores less significant bytes with a smaller index of array, we can actually think of `bn` as a base-32 number with 32 digit (by analogizing each array element to a "digit"). That is: ```graphviz digraph { bn[shape=record, label="<l>0|1|2|...|30|<m>31"] least[label="least significant digit"] least -> bn:l most[label="most significant digit"] most -> bn:m } ``` We'll find it easier to understand related functions of `bn` with this idea in mind. ### Functions Some functions that are more obvious, such as `bn_init` , are ignored. #### bn_from_int Discussed in [this section](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#Structure). #### bn_to_str The function read bn from its last element, since the string representation start with most significant byte. ```c /* 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 */ } ``` Since format string `"%.08x"` will write 8 digit at a time, there's a chance to overflow the buffer when the size of `buf` is not a multiple of 8. We'll [fix](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#bn_to_str-overflow-problem) this in later section. After the loop, the function starts to eliminate leading zeros. ```c /* 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; ``` But actually, why don't we just [skip zeros at the very start](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#bn_to_str-skipping-zeros)? #### bn_dec Discussed in [this section](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#COND). #### bn_add Most of lines are plain and straight forward. The interesting part of this function is the last line of the loop: ```c c->array[i] = (tmp & MAX_VAL); ``` If we check the corresponding assembly of this line, we can find that `tmp & MAX_VAL` part disappeared. It is replaced by taking the lowest 4 bytes: `mov ecx, eax`. ```asm mov rax,QWORD PTR [rbp-0x10] ;tmp mov ecx,eax ;truncate mov rax,QWORD PTR [rbp-0x28] ;c mov edx,DWORD PTR [rbp-0x8] ;i movsxd rdx,edx mov DWORD PTR [rax+rdx*4],ecx ``` > Full assembly of `bn_add`: https://gist.github.com/secminhr/385b0ea61d825862ea469cd441bae2fb We can see this technique in `bn_from_int`, too. ```asm mov rax,QWORD PTR [rbp-0x20] ;i mov edx,eax mov rax,QWORD PTR [rbp-0x18] ;n mov DWORD PTR [rax],edx ``` > Full assembly of `bn_from_int`: https://gist.github.com/secminhr/9ca3f23553d8eaf9f4e977cf700d3867 However, its correspoding line has a comment `/* FIXME: what if machine is not little-endian? */` It seems that there are some problems about endianness. I'm looking for ways to get a big-endian machine to test that. #### bn_mul Plsea read [this section](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#III) first. A clever part of this function is the condition `i + j < BN_ARRAY_SIZE`. If you follow the column multiplication process provided in [previous section](https://hackmd.io/M6gXVDTzR4CV5MOi_STEJw#III), you may find that when reaching the end of array, the result of `i + j` will always be `BN_ARRAY_SIZE - 1`. Therefore, the condition can prevent it from calculating unnecessary digits. ### Fixes & Improvements #### bn_to_str: skipping zeros #### bn_to_str: overflow problem We first verify that buffer overflow does happen when size of `buf` is not a multiple of 8. Change the size of `buf` to 3 and run it. ```shell $ ./overflow_test factorial(100) = *** stack smashing detected ***: terminated Aborted (core dumped) ``` The message `*** stack smashing detected ***: terminated` indicates that a stack buffer overflow has happened.
Last changed by  
 
secminhr
333

Read more

quiz7B - multi-threaded web server

contributed by < secminhr > github repo 進度表 [x] http [x] gain full understand of current codes (including request parsing and response) [ ] 並行與多執行緒程式設計講座 [ ] io_uring

7/16/2021
2021q1 Homework2 (quiz2)

contributed by < secminhr > 題目 問題 1. COND1 = ? 出現在這個函式裡面： static list_ele_t *get_middle(struct list_head *list) {

6/28/2021
2021q1 Homework5 (quiz5)

contributed by < secminhr > Quiz Problems VV1 = ? #define NEXT_POWER_OF_2(s) \ VV1 ? s : (size_t) 1 << (64 - __builtin_clzl(s)) We can see that if VV1 is true then s will be returned, which indicates that s is a power of 2. Since a power of 2 has only a bit set, we can easily see that s & (s-1) must be 0, so VV1 is !(s & (s-1)). The answer is (e).

4/12/2021
2021q1 Homework4 (quiz4)

contributed by < secminhr > 題目 FFF = ? /** * Return the result when it becomes available. * If @seconds is non-zero and the result does not arrive within specified time, * NULL is returned. Each tpool_future_get() resets the timeout status on * @future. */

4/7/2021
Read more from secminhr
Published on HackMD