# [2020q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 4 週測驗題
###### tags: `linux2020`

:::info
目的: 檢驗學員對 **[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)**, **[指標操作](https://hackmd.io/@sysprog/c-pointer)**, **[前置處理器應用](https://hackmd.io/@sysprog/c-preprocessor)** 的認知
:::

==[作答表單](https://forms.gle/SYroLNik2QYsDQV39)==

---

### 測驗 `1`

考慮到以下 `bitcpy` 實作，允許開發者對指定的記憶體區域，逐 bit 進行資料複製:

#include <stdint.h>
#include <stdio.h>
#include <string.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)
{
    uint8_t data, original, mask;
    size_t bitsize;
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = _src + (_read / 8);
    size_t write_lhs = _write & KK1;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = _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) {
        data = *source++;
        bitsize = (_count > 8) ? 8 : _count;
        if (read_lhs > 0) {
            data <<= read_lhs;
            if (bitsize > read_rhs)
                data |= (*source >> read_rhs);
        }

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

        original = *dest;
        if (write_lhs > 0) {
            mask = read_mask[write_lhs];
            if (bitsize > write_rhs) {
                *dest++ = (original & mask) | (data >> write_lhs);
                original = *dest & write_mask[bitsize - write_rhs];
                *dest = original | (data << write_rhs);
            } else {
                if ((bitsize - write_lhs) > 0)
                    mask = mask | write_mask[8 - (bitsize - write_lhs)];
                *dest++ = (original & mask) | (data >> write_lhs);
            }
        } else {
            if (bitsize < 8)
                data = data | (original & write_mask[bitsize]);
            *dest++ = data;
        }

        _count -= KK2;
    }
}

對應的測試程式碼:

static uint8_t output[8], input[8];

static inline void dump_8bits(uint8_t _data)
{
    for (int i = 0; i < 8; ++i)
        printf("%d", (_data & (0x80 >> i)) ? 1 : 0);
}
static inline void dump_binary(uint8_t *_buffer, size_t _length)
{
    for (int i = 0; i < _length; ++i)
        dump_8bits(*_buffer++);
}

int main(int _argc, char **_argv)
{
    memset(&input[0], 0xFF, sizeof(input));

    for (int i = 1; i <= 32; ++i) {
        for (int j = 0; j < 16; ++j) {
            for (int k = 0; k < 16; ++k) {
                memset(&output[0], 0x00, sizeof(output));
                printf("%2d:%2d:%2d ", i, k, j);
                bitcpy(&output[0], k, &input[0], j, i);
                dump_binary(&output[0], 8);
                printf("\n");
            }
        }
    }

    return 0;
}

測試程式碼的參考輸出:

 1: 0: 0 1000000000000000000000000000000000000000000000000000000000000000
 1: 1: 0 0100000000000000000000000000000000000000000000000000000000000000
 1: 2: 0 0010000000000000000000000000000000000000000000000000000000000000                                                                                     
 ...
 1:15: 0 0000000000000001000000000000000000000000000000000000000000000000
 1: 0: 1 1000000000000000000000000000000000000000000000000000000000000000
 1: 1: 1 0100000000000000000000000000000000000000000000000000000000000000
 1: 2: 1 0010000000000000000000000000000000000000000000000000000000000000
 ...
 1:15: 1 0000000000000001000000000000000000000000000000000000000000000000
 ...

請補完程式碼。

==作答區==

KK1 = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` 4
* `(e)` 5
* `(f)` 6
* `(g)` 7
* `(h)` 8

KK2 = ?
* `(a)` 1
* `(b)` -1
* `(c)` 0xFF
* `(d)` bitsize
* `(e)` write_rhs
* `(f)` write_lhs

:::success
延伸問題:
1. 解釋上述程式運作的原理，改寫為更精簡且等效的程式碼;
2. 考慮到 alignment 和 word size，改寫為執行效率更高的程式碼;
3. 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境;
> 提示: 觀察 [linux/bitops.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/bitops.h) 裡頭巨集在原始程式碼的運用狀況
:::

---

### 測驗 `2`

考慮到一個針對空間處理最佳化的 vector 實作
支援以下操作:
* `vec_push_back` : 新增元素至 vector 的尾端，必要時會進行記憶體配置;
* `vec_pop_back()` : 刪除 vector 最尾端的元素;

每個 vector 都有兩個重要的屬性:
* 容量 (capacity) : 是這個 vector 擁有的空間。
* 長度 (size): 實際儲存了元素的空間大小。capacity 永遠不小於 size

使用示範:

int main()
{
    v(float, 3, vec1);
    v(int, 2, vec2, 13, 42);

    printf("pos(vec2,0)=%d, pos(vec2,1)=%d\n", vec_pos(vec2, 0),
           vec_pos(vec2, 1));
    vec_push_back(vec2, 88);
    vec_reserve(vec2, 100);
    printf("capacity(vec1)=%zu, capacity(vec2)=%zu\n", vec_capacity(vec1),
           vec_capacity(vec2));
    printf("pos(vec2,2)=%d\n", vec_pos(vec2, 2));

#define display(v)                               \
    do {                                         \
        for (size_t i = 0; i < vec_size(v); i++) \
            printf("%.2f ", vec_pos(v, i));      \
        puts(v.on_heap ? "heap" : "stack");      \
    } while (0)

    display(vec1);
    vec_push_back(vec1, 0.0);
    display(vec1);
    vec_push_back(vec1, 1.1);
    display(vec1);
    vec_push_back(vec1, 2.2);
    display(vec1);
    vec_push_back(vec1, 3.3);
    display(vec1);
    vec_push_back(vec1, 4.4);
    display(vec1);
    vec_push_back(vec1, 5.5);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);
    vec_pop_back(vec1);
    display(vec1);

    return 0;
}

預期輸出:

pos(vec2,0)=13, pos(vec2,1)=42
capacity(vec1)=4, capacity(vec2)=128
pos(vec2,2)=88
stack
0.00 stack
0.00 1.10 stack
0.00 1.10 2.20 stack
0.00 1.10 2.20 3.30 stack
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 4.40 5.50 heap
0.00 1.10 2.20 3.30 4.40 heap
0.00 1.10 2.20 3.30 heap
0.00 1.10 2.20 heap
0.00 1.10 heap
0.00 heap
heap

本體的實作程式如下:

#include <stddef.h>
#include <stdio.h>                           
#include <stdlib.h>
#include <string.h>

/* vector with small buffer optimization */

#define STRUCT_BODY(type)                                                  \
    struct {                                                               \
        size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
            flag3 : 1;                                                     \
        type *ptr;                                                         \
    }

#define NEXT_POWER_OF_2(s) \
    VV1                    \
        ? s                \
        : (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */

#define v(t, s, name, ...)                                              \
    union {                                                             \
        STRUCT_BODY(t);                                                 \
        struct {                                                        \
            size_t filler;                                              \
            t buf[NEXT_POWER_OF_2(s)];                                  \
        };                                                              \
    } name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
    name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) /   \
                    sizeof(name.buf[0]) - 1;                            \
    name.capacity = sizeof(name.buf) / sizeof(name.buf[0])

#define vec_size(v) v.size
#define vec_capacity(v) \
    (v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))

#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */

#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */

#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e)                                            \
    __vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
                    vec_capacity(v))

#define vec_pop_back(v) (void) (VV2)

/* This function attribute specifies function parameters that are not supposed
 * to be null pointers. This enables the compiler to generate a warning on
 * encountering such a parameter.
 */
#define NON_NULL __attribute__((nonnull))

static NON_NULL void vec_free(void *p)
{
    STRUCT_BODY(void) *s = p;
    if (s->on_heap)
        free(s->ptr);
}

static inline int ilog2(size_t n)
{
    return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}

static NON_NULL void __vec_reserve(void *vec,
                                   size_t n,
                                   size_t elemsize,
                                   size_t capacity)
{
    union {
        STRUCT_BODY(void);
        struct {
            size_t filler;
            char buf[];
        };
    } *v = vec;

    if (n > capacity) {
        if (v->on_heap) {
            v->ptr = realloc(v->ptr,
                             elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
        } else {
            void *tmp =
                malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
            memcpy(tmp, v->buf, elemsize * v->size);
            v->ptr = tmp;
            v->on_heap = 1;
        }
    }
}

static NON_NULL void __vec_push_back(void *restrict vec,
                                     void *restrict e,
                                     size_t elemsize,
                                     size_t capacity)
{
    union {
        STRUCT_BODY(char);
        struct {
            size_t filler;
            char buf[];
        };
    } *v = vec;

    if (v->on_heap) {
        if (v->size == capacity)
            v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
        memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
    } else {
        if (v->size == capacity) {
            void *tmp =
                malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
            memcpy(tmp, v->buf, elemsize * v->size);
            v->ptr = tmp;
            v->on_heap = 1;
            memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
        } else
            memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
    }
}

請補完程式碼。
> 參閱 [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick) 以得知 GCC extension: attribute cleanup 使用技巧。

==作答區==

VV1 =
* `(a)` s
* `(b)` s - 1
* `(c)` s & (s - 1)
* `(d)` (s & (s - 1)) == 0

VV2 =
* `(a)` `v.size -= 1`
* `(b)` `v.capacity--`

:::success
延伸問題:
1. 解釋上述程式運作的原理，比照 [quiz2](https://hackmd.io/@sysprog/BJXNYx5NL) 進行效率分析;
2. 指出上述實作的限制並提出改進方案;
3. 參照 [folly::fbvector](https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md) 文件和對應原始程式碼，以上述程式為基礎，實作 vector 經典操作
:::