# 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.