# 2020q1 Homework3 (quiz4)
contributed by < `StevenChen8759` >

###### tags: `linux2020`

> [quiz4 題目說明](https://hackmd.io/@sysprog/linux2020-quiz4)

## :Camera: 測驗一 - bitcpy

### :camera_with_flash: 運作原理與填答
* 觀察下列函式 `bitcpy` 的操作，可發現在寫入位址的操作計算上採用了位元運算。

size_t read_lhs = _read & 7;                // Perform _read mod 8 in bitwise operation
size_t read_rhs = 8 - read_lhs;             // Get bit position offset in a uint8_t space
const uint8_t *source = _src + (_read / 8); // Offset to assigned array position for reading src

size_t write_lhs = _write & KK1;            // Perform _write mod 8 in bitwise operation
size_t write_rhs = 8 - write_lhs;           // Get bit position offset in a uint8_t space
uint8_t *dest = _dest + (_write / 8);       // Offset to assigned array position for writing dest

* 函式 `bitcpy` 會將 `source` 之第0個位元算起偏移 `_read` 個位元，複製 `_count` 個位元到`dest` 之第0個位元算起偏移 `_write` 個位元
* 因為儲存位元的資料型態為 `uint8_t` ，每一個陣列欄位為 8 bits ，因此在**陣列元素的欄位偏移**為 `_write` 值除以 8，而**陣列元素內的位元偏移**則為 `_write` 取餘數8，其操作等價於取 `_write` 的最低 3 位元，故填答 `KK1` 之值為 7。

#define KK1 7

* 我們接著分析實作位元複製的迴圈，其程式碼實現如下：

/* Copy all bits in number _count */
    while (_count > 0) {

        // Read data from source and move to next position
        data = *source++;
        bitsize = (_count > 8) ? 8 : _count;   // Set Operating bit size

        // Bit offset in uint8_t space is not zero
        if (read_lhs > 0) {
            data <<= read_lhs;        // Align to position zero
            if (bitsize > read_rhs)   // If tailed reading bits in the next position of array
                data |= (*source >> read_rhs);    // Concate these bit into current position of array
        }

        // Reading bit size is smaller than 8, mask bits which are not necessary
        if (bitsize < 8)
            data &= read_mask[bitsize];

        // Assign data before writing to variable original
        original = *dest;

        // Bit offset in uint8_t space is not zero
        if (write_lhs > 0) {

            // Assign read mask for leading 0~8 bits
            mask = read_mask[write_lhs];

            // Writing bits is crossing two elements in array
            if (bitsize > write_rhs) {
                // Mask bits in front of start position, and write available bits started from offset
                *dest++ = (original & mask) | (data >> write_lhs);

                // Write bits which cannot write into previous position
                original = *dest & write_mask[bitsize - write_rhs];

                // Move written bits to correct position
                *dest = original | (data << write_rhs);
            } else {

                // For writing position is not started from zero case, adjust mask for writing bits
                if ((bitsize - write_lhs) > 0)
                    mask = mask | write_mask[8 - (bitsize - write_lhs)];

                // Assign data with mask and concate data if necessary
                *dest++ = (original & mask) | (data >> write_lhs);
            }
        } else {

            // Mask data output while uint8_t is not fully written
            if (bitsize < 8)
                data = data | (original & write_mask[bitsize]);

            // Data assignment
            *dest++ = data;
        }

        _count -= KK2; // Write bitsize bits for each iteration, minus bitsize
    }

*

### :camera_with_flash: 原始程式碼效能改善

### :camera_with_flash: 考慮 `Alignment` 以及 `Word Size` 之效能改善

### :camera_with_flash: Linux 原始碼中的運用 `bitcpy` 技巧的場合

## :camera: 測驗二 - Vector

### :camera_with_flash: 運作原理與填答

### :camera_with_flash: 程式效率分析

### :camera_with_flash: 實作上限制與改善方案

### :camera_with_flash: 基於上述程式實現 `folly::fbvector` 中的經典操作