# 2022q1 Homework3 (quiz3)
contributed by <`yaohwang99` >
> [quiz3](https://hackmd.io/@sysprog/linux2022-quiz3)
## Problem 1

In Linux kernel,`GENMASK` gernerates bitmask for the given range.
+ GENMASK(6, 4) produces 01110000~2~
+ GENMASK(39, 21) produces 0x000000FFFFE00000

For the above 2 examples to be true, we can deduct that ==`LEFT` is `63 - h` and `RIGHT` is `l`==.
1. To clear the more significant bits, ==`LEFT` must be `63 - h`==.
2. To clear the less significant bits, ==`RIGHT` is `l`==.

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

:::danger

**However, I believe that the code is not correct because:**
+ GENMASK(63, 8) produces `0xFFFFFFFFFFFFFFFF & 0x00FFFFFFFFFFFF00 == 0x00FFFFFFFFFFFF00 `which is not the correct result.
:::
I believe the following code is correct.

#define GENMASK(h, l) \
    (((~0UL) >> (63-h) & ((~0UL) << l)))

## Problem 2
### Memory alignment

struct foo;
  
struct fd {
    struct foo *foo;
    unsigned int flags;
};

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

The function `to_fd` use the parameter `v` , align down to 4, and use it as the address of `*foo`.
Align down to 4 means that we clear the last 2 bits of `v`, therefore, ==EXP1 is `v & ~3`==.

## Problem 3

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

0xCC = 11001100~2~
0xAA = 10101010~2~
line 4 swaps the most significant 4 bits with the less significant 4 bits
line 5 swaps every 2 bits
line 6 swaps every bit.
==EXP2: `x & 0x33) << 2`==
==EXP3: `x & 0x55) << 2`==

## Problem 4

    int i;
    foreach_int(i, 0, -1, 100, 0, -99) {
        printf("i is %i\n", i);
    }
    const char *p;
    foreach_ptr(p, "Hello", "world") {
        printf("p is %s\n", p);
    }

#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[EXP4])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[EXP5],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

From [C99 Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf)

> **6.5.17 Comma operator**
**Syntax**
>+ expression:
+ *assignment-expression*
+ *expression , assignment-expression*
>**Semantics**
The left operand of a comma operator is evaluated as a void expression; there is a sequence point between its evaluation and that of the right operand. Then the right operand is evaluated; the result has its type and value.
For example, the function `f(a, (t=3, t+2), c)` has three arguments, the second of which has the value 5.

`unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)` assigns `((int[]){__VA_ARGS__})[0])` to `i`, then assign the second `0` to `_foreach_i `

Just like a common `for(int i = 0; i < n; ++i)` , we can deduct that ==EXP4 and EXP5 is `++_foreach_1`==.

## Problem 5

#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        EXP7;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

## Problem 6

digraph {
rankdir = LR
compound = true
    subgraph cluster0{
    style = filled 
    color = gray90
    node1[shape = record label = "heads[0]|<1>heads[1]|...|heads[slope_size-1]"]
    
    }
subgraph cluster1{
    style = filled 
    color = gray90
    label = point_node
    node2[shape = record label = "p1|p2|<link>link"]
    }
    subgraph cluster2{
    style = filled 
    color = gray90
    label = point_node
    node3[shape = record label = "p1|p2|<link>link"]
    }

    node1:1 -> node2:link[dir = both]
    node2:link -> node3:link[dir = both]
}

    for (i = 0; i < pointsSize; i++) {
        for (j = i + 1; j < pointsSize; j++) {
            if (points[i].x == points[j].x)
                hori_cnts[i]++, hori_cnts[j]++;

            if (points[i].y == points[j].y)
                vert_cnts[i]++, vert_cnts[j]++;

            if (points[i].x == points[j].x && points[i].y == points[j].y)
                dup_cnts[i]++, dup_cnts[j]++;

            if (points[i].x != points[j].x && points[i].y != points[j].y) {
                int dx = points[j].x - points[i].x;
                int dy = points[j].y - points[i].y;
                int tmp = gcd(dx, dy);
                dx /= tmp;
                dy /= tmp;
                int hash = dx * dy - 1333 * (dx + dy);
                if (hash < 0)
                    hash = -hash;
                hash %= slope_size;
                if (can_insert(&heads[hash], i, j)) {
                    struct point_node *pn = malloc(sizeof(*pn));
                    pn->p1 = i;
                    pn->p2 = j;
                    EXP9;
                }
            }
        }
    }

Line 3 to 7 counts the number of points in a vertical line and horizontal line for a given point. For example, if `hori_cnts[1]` is 5, that means `points[1]` is in a horizontal line consist of other 5 points and itself.
Line 9 and 10 counts the number of duplicated points for a given point. For example, if `dup_cnts[2]` is `2`, that means there are 2 other identical points.
Line 12 to 28 uses different slope as hash and put the points into the hash. Therefore, ==EXP9 is `list_add(pn, &heads[hash])`==

In line 22, we first check if we can insert the pair.

static bool can_insert(struct list_head *head, int p1, int p2)
{
    struct point_node *pn;
    list_for_each_entry (pn, head, link)
        return EXP8;
    return true;
}

To deduct EXP8, consider the following example.
The traverse order is <`points[1]`, `points[2]`> $\to$ <`points[1]`, `points[3]`> $\to$ <`points[1]`, `points[4]`> $\to$,<`points[2]`, `points[3]`> $\to$<`points[2]`, `points[4]`> $\to$ <`points[3], points[4]`>. To count the correct number of points in the line, we need each pair consist of the point with the smallest index(because of the traverse order). Therefore, we check if we can insert by ==EXP8: `p1 == pn->p1`==.

## Problem 7
If `v > 0`, then `ret` must be greater or equal to 1.
Check if any of the 32 more significant bits are set.
If so, then `ret` must be greater then 32.
Set `v` as the remaining 32 bits.

int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;

Check if any of the 16 more significant bits are set.
If so, then `ret` must be greater then 16.
Set `v` as the remaining 16 bits.
Repeat the same process for 8,4,2 more significant bits.
Therefore, ==EXP10 is `(v > 0x3) << 1`==

    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = EXP10;
    v >>= m;
    ret |= m;

`v` then becomes 01~2~, 10~2~,or 11~2~
We will need one more bit if `v > 1`, therefore, ==EXP11 is `ret += v > 1`==

    EXP11;
    return ret;
}

## Problem 8

digraph {
compound = true

    subgraph cluster0{
        label = tnode
        style = filled
        color = gray90
        node0[shape = record, label ="data|<l>left|<r>right"]
    }
    subgraph cluster1{
        label = tnode
        style = filled
        color = gray90
        node1[shape = record, label ="{data}|<l>left|<r>right"]
    }
    subgraph cluster2{
        label = tnode
        style = filled
        color = gray90
        node2[shape = record, label ="data|<l>left|<r>right"]
    }
    subgraph cluster3{
        label = tnode
        style = filled
        color = gray90
        node3[shape = record, label ="data|<l>left|<r>right"]
    }
    subgraph cluster4{
        label = tnode
        style = filled
        color = gray90
        node4[shape = record, label ="data|<l>left|<r>right"]
    }
    node0:l->node1[lhead = cluster1]
    node0:r->node2[lhead = cluster2]
    node1:l->node3[lhead = cluster3]
    node1:r->node4[lhead = cluster4]
}

Use the technique of indirect pointer.

void remove_data(tree &t, int d)
{
    tnode **p = &t;
    while (*p != 0 && (*p)->data != d) {
        if (d < (*p)->data)
            EXP12;
        else
            EXP13;
    }

Traverse to left or right child according to current value.
==EXP12: `p = &(*p)->left`==
==EXP13: `p = &(*p)->right`==

digraph {
compound = true

    subgraph cluster0{
        label = tnode
        style = filled
        color = gray90
        node0[shape = record, label ="data|<l>left|<r>right"]
    }
    subgraph cluster1{
        label = tnode
        style = filled
        color = gray90
        node1[shape = record, label ="{data}|<l>left|<r>right"]
    }
    subgraph cluster2{
        label = tnode
        style = filled
        color = gray90
        node2[shape = record, label ="data|<l>left|<r>right"]
    }
    subgraph cluster3{
        label = tnode
        style = filled
        color = gray90
        node3[shape = record, label ="data|<l>left|<r>right"]
    }
    subgraph cluster4{
        label = tnode
        style = filled
        color = pink
        node4[shape = record, label ="data = d|<l>left|<r>right"]
    }
    lsubtree[label = "left subtree", shape = triangle]
    rsubtree[label = "right subtree", shape = triangle]
    node0:l->node1[lhead = cluster1]
    node0:r->node2[lhead = cluster2]
    node1:l->node3[lhead = cluster3]
    node1:r->node4[lhead = cluster4]
    node4:l->lsubtree
    node4:r->rsubtree
}

For a binary tree, after removing the target, move the smallest child element in the right subtree to target, or move the largest element in the left subtree to target.
In the following code, we move the smallest child element in the right subtree to target.

    tnode *q = *p;
    if (!q)
        return;

    if (!q->left)
        *p = q->right;
    else if (!q->right)
        *p = q->left;
    else {
        tnode **r = &q->right;
        while ((*r)->left)
            r = EXP14;
        q->data = (*r)->data;
        q = *r;
        *r = q->right;
    }
    delete q;
}

Therefore, ==EXP14 is `r = &(*r)->left`==

## Problem 9

/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - MMM) & ~(NNN))

Using the fact that $\lceil\frac{a}{b}\rceil =\lfloor\frac{a}{b}+\frac{b-1}{b}\rfloor$
x round up to 16 $= \lceil\frac{x}{16}\rceil *16=\lfloor\frac{x+15}{16}\rfloor *16$
Therefore, ==MMM is `1`, NNN is `MAX_ALIGNMENT-1`==

## Problem 10

#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

$round(\frac{a}{b})=\lfloor\frac{a+\frac{b}{2}}{b}\rfloor$
If
1. x or divisor is unsigned
2. x and divisor is both positive or negetive
then return `(__x)+(__d)>>1`
otherwise, return `-(__x)+(__d)>>1`

Therefore, ==RRR is `(__x)+(__d)>>1`, SSS is `-(__x)+(__d)>>1`==.

## Problem 11
`fls()` returns the position of the most significant bit.
1. Set the current value to 63, the greatest possible number.
2. If all of the 32 more significant bit is 0, the reult is 32 less than the current number.
3. Repeat step 2. for 16, 8, 4, 2, 1, return the final number.

static inline unsigned long fls(unsigned long word)
{
    int num = 64 - 1;
        
    if (!(word & (~0ul << 32))) {
        num -= 32;
        word <<= 32;
    }
    if (!(word & (~0ul << (64 - 16)))) {
        num -= 16;
        word <<= 16;
    }
    if (!(word & (~0ul << (64 - 8)))) {
        num -= 8;
        word <<= 8;
    }
    if (!(word & (~0ul << (64 - 4)))) {
        num -= 4;
        word <<= 4;
    }   
    if (!(word & (~0ul << (64 - 2)))) {
        num -= 2;
        word <<= 2;
    }   
    if (!(word & (~0ul << (64 - 1))))
        num -= 1;
    return num;
} 

The following code is used fore calculating $\lfloor\sqrt{x}\rfloor$

unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        XXX;

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }

    return y;
}

To understand how the code works, we need to know how to calculate the square root of a binary number.
[source](https://www.cantorsparadise.com/the-square-root-algorithm-f97ab5c29d6d)

1. We calculate the answer every two digits.
2. `y` corresponds the leftmost column.
3. `m = 1UL << (fls(x) & ~1UL);` the return value of fls() is rounded down to even number.

For the above example, $x = 169_10 = 10101001_2$, $fls(x) = 7$, $m = 1000000_2$
`y` of the next iteration is equal to `(y+m)>>1` if `x > y + m`.
Therefore,==XXX is `y >>= 1`, YYY is `x -= b`, ZZZ is `m >>= 2`==.