# 2021q1 Homework2 (quiz2)
###### tags: `linux2021`
contributed by < `Billy4195` >
> [Problem Set](https://hackmd.io/@sysprog/linux2021-quiz2)

## Problem 1

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (COND1 || COND2)
            break;
        fast = fast->next->next;
    }
    return list_entry(TTT, list_ele_t, list);
}

### Explanation
`get_middle()` uses two pointer `fast` and `slow` to traverse the linked-list try to get the middle element. The algorithm is that the `fast` pointer move two-step(two elements) in each iteration. When it reach the end of the list, the middle element is pointed by the `slow` pointer.

So the end condition for the traverse is when the `fast` pointer reach the end of the linked-list.

COND1 = ?
`(c) fast->next == list`

COND2 = ?
`(b) fast->next->next == list`

MMM = ?
`(e) &get_middle(&q->list)->list`

TTT = ?
`(a) slow`

### Extened questions
* [x] Explain the implementation
* [ ] Try to improve the implementation
* [ ] Read the [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) in Linux kernel, and learn from [sysprog21/linux-list](https://github.com/sysprog21/linux-list).
* [ ] Extract the [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) to be a standalone user level application.
* [ ] Design profiling experiments and explain the optimization in Linux kernel
* [ ] Improve implementation of quiz1 and compare with [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) using benchmark

## Quiz 2
The `func` receive an 16bits unsigned int N, it will return an number which is power of 2 and less than or equal to N

### Explanation

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> X;
    N |= N >> Y;
    N |= N >> Z;

    return (N + 1) >> 1;
}

At the first glance, it's hard to understand how it works. However, I guess the answers of `X`, `Y`, `Z` may have something to do with power of 2.

I write a simple program to test the behavior of this function, and fill the `X`, `Y` and `Z` with 2, 4, 8, respectively.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

int main() {
    uint16_t ret = 0;
    ret = func(7);
    printf("func(7) = %u\n", ret);
    ret = func(26);
    printf("func(26) = %u\n", ret);

    return 0;
}

$ gcc -o test main.c
$ ./test
func(7) = 4
func(26) = 16

The program works as expected so far, and we need to understand what it did.
#### For N = 7
If the given `N` for the `func` is 7, the binary expression is `0000111`

After Line 7 executed (`N |= N >> 1`), `N` is still 7. After Line 7-10 is executed, the N remains `7`.

The finaly statement add 1 to N (N=8 `00001000`), and right shift 1 bit will be 4 (`00000100`).

#### For N = 26
The binary expression of 26 is `00011010`

`N |= N >> 1`
> N = `00011111` = 31

`N |= N >> 2`
> N = `00011111` = 31

`N |= N >> 4`
> N = `00011111` = 31

`N |= N >> 8`
> N = `00011111` = 31

` (N+1) >> 1`
> N = `00001000` = 16

---

According above two cases, I guess the `func` will fill all the bits on the right hand side of the leading `1` bit with `1`, and the add 1 to make it be an number is power of 2 and larger than `N`. Then the right shift 1 bit to make it to be an power of 2 and less than or equal to N.

#### Prove from the simplified uint8_t cases
To prove my guessing is correct, I take a simplified case for uint8.

The `func` will become as follows:

uint8_t func(uint8_t N) {
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    
    return (N+1) >> 1;
}

#### For the given unsigned 8 bits integer
For the given N is 128

digraph {
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    values [label="{bit 7 | 1 } | {bit 6 | 0 }| {bit 5 | 0}| {bit 4 | 0} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    { rank=same; values }

}

#### For N |= N >> 1

digraph {
    node [shape=plaintext];
    "Result" [fontcolor=red]
    "N"
    
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    { rank=same; "N"; values  }
    { rank=same; values1 }
    { rank=same; "Result"; valuesR }
    
    
    values [label="{bit 7 | 1 } | {bit 6 | <F0_1> 0 }| {bit 5 | 0}| {bit 4 | 0} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    values1 [label="{<F1_0> bit 7 | 1 } | {bit 6 | 0 }| {bit 5 | 0}| {bit 4 | 0} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    valuesR [label="{ bit 7 | 1 } | {bit 6 | <F2_1>1 }| {bit 5 | 0}| {bit 4 | 0} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    valuesR:F2_1 [color=red]
    values:F0_1 -> values1:F1_0 [style=invis]
    values1:F1_0 -> valuesR:F2_1 [style=invis]
}

#### For N |= N >> 2

digraph {
    node [shape=plaintext];
    "Result" [fontcolor=red]
    "N"
    
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    { rank=same; "N"; values  }
    { rank=same; values1 }
    { rank=same; "Result"; valuesR }
    
    
    values [label="{<F0>bit 7 | 1 } | {bit 6 | 1 }| {<F2>bit 5 | 0}| {bit 4 | 0} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    values1 [label="{<F0> bit 7 | 1 } | {bit 6 | 1 }| {bit 5 | 0}| {bit 4 | 0} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    valuesR [label="{<F0> bit 7 | 1 } | {bit 6 | 1 }| {<F2>bit 5 | 1}| {bit 4 | 1} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    valuesR:F1 [color=red]
    values:F2 -> values1:F0 [style=invis]
    values1:F0 -> valuesR:F2 [style=invis]
}

#### For N |= N >> 4

digraph {
    node [shape=plaintext];
    "Result" [fontcolor=red]
    "N"
    
    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
    
    { rank=same; "N"; values  }
    { rank=same; values1 }
    { rank=same; "Result"; valuesR }
    
    values [label="{<F0>bit 7 | 1 } | {bit 6 | 1 }| {<F2>bit 5 | 1}| {bit 4 | 1} | {<F4>bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    values1 [label="{<F0> bit 7 | 1 } | {bit 6 | 1 }| {bit 5 | 1}| {bit 4 | 1} | {bit 3 | 0} | {bit 2 | 0} | {bit 1 | 0} | {bit 0 | 0}"];

    valuesR [label="{<F0> bit 7 | 1 } | {bit 6 | 1 }| {<F2>bit 5 | 1}| {bit 4 | 1} | {<F4>bit 3 | 1} | {bit 2 | 1} | {bit 1 | 1} | {bit 0 | 1}"];

    valuesR:F1 [color=red]
    values:F4 -> values1:F0 [style=invis]
    values1:F0 -> valuesR:F4 [style=invis]
}

---

> TODO: Explain implementation
> TODO: Add more complex test cases
> Discuss the case of N = MAX_UINT16 or 0

X = ?
`(b) 2`

Y = ?
`(d) 4`

Z = ?
`(h) 8`

## Quiz 3

#include <stdint.h>

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = (const uint8_t *) _src + (_read / 8);
    size_t write_lhs = _write & 7;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = (uint8_t *) _dest + (_write / 8);

    static const uint8_t read_mask[] = {
        0x00, /*    == 0    00000000b   */
        0x80, /*    == 1    10000000b   */
        0xC0, /*    == 2    11000000b   */
        0xE0, /*    == 3    11100000b   */
        0xF0, /*    == 4    11110000b   */
        0xF8, /*    == 5    11111000b   */
        0xFC, /*    == 6    11111100b   */
        0xFE, /*    == 7    11111110b   */
        0xFF  /*    == 8    11111111b   */
    };

    static const uint8_t write_mask[] = {
        0xFF, /*    == 0    11111111b   */
        0x7F, /*    == 1    01111111b   */
        0x3F, /*    == 2    00111111b   */
        0x1F, /*    == 3    00011111b   */
        0x0F, /*    == 4    00001111b   */
        0x07, /*    == 5    00000111b   */
        0x03, /*    == 6    00000011b   */
        0x01, /*    == 7    00000001b   */
        0x00  /*    == 8    00000000b   */
    };

    while (count > 0) {
        uint8_t data = *source++;
        size_t bitsize = (count > 8) ? 8 : count;
        if (read_lhs > 0) {
            RRR;
            if (bitsize > read_rhs)
                data |= (*source >> read_rhs);
        }

        if (bitsize < 8)
            data &= read_mask[bitsize];

        uint8_t original = *dest;
        uint8_t mask = read_mask[write_lhs];
        if (bitsize > write_rhs) {
            /* Cross multiple bytes */
            *dest++ = (original & mask) | (data >> write_lhs);
            original = *dest & write_mask[bitsize - write_rhs];
            *dest = original | (data << write_rhs);
        } else {
            // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
            DDD;
            *dest++ = (original & mask) | (data >> write_lhs);
        }

        count -= bitsize;
    }
}

### Explanation

RRR = ?

`(a) data <<= read_lhs`

For line 43-47, `data` will store the first 1 bytes data from `source`.

If `read_lhs == 0`, then `data` is just the same as `source`
If `read_lhs > 0`, we need to eliminate the bits of left hand side.
Therefore, `RRR` should be `(a)` which left shift `read_lhs` bits to make the extra bits of source to be deleted.

DDD = ?

`(b) mask |= write_mask[write_lhs + bitsize]`

## Quiz 4

CCC = ?

(a) strlen(str) + 1
(b) strlen(str) * 2
(c) s->hash_size
(d) s->size
(e) strlen(s->cstr) + 1