---
tags: linux2024
---

# [2024q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 18 週測驗題

:::info
目的: 檢驗學員對 bitwise operation 的認知
:::

==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSfDf-9XtzFj9HoijJOaQAjcIe-rM2FIp4nXGftRcxF28VgxCw/viewform)== (針對 Linux 核心「實作」課程)

### 測驗 `1`

延伸〈[Linux 核心原始程式碼的整數除法](https://hackmd.io/@sysprog/linux-intdiv)〉和[第 7 週測驗 `2`](https://hackmd.io/@sysprog/linux2024-quiz7)，[fastdiv](https://gist.github.com/jserv/22ca89155b028dddd9bccd1bae9a01e9) (部分程式碼遮蔽) 提出快速除法實作。以下是測試程式碼:

#include <assert.h>
#include <stdio.h>

#include "fastdiv.h"

int main(int argc, char **argv)
{
    const uint64_t MAX_NUM = 1 << 16;
    const uint64_t MAX_DIV = 1 << 14;

    for (uint64_t d = 1U; d < MAX_DIV; ++d) {
        div_t fd;        /* general method */
        fastdiv(&fd, d); /* divide-by-d */
        const uint64_t mul = fd.mul, add = fd.add, shift = fd.shift;

        div_t fd2;                         /* bounded method optimization */
        fastdiv_bounded(&fd2, d, MAX_DIV); /* divide-by-d */
        const uint64_t mul2 = fd2.mul, add2 = fd2.add, shift2 = fd2.shift;
        assert(mul2 == 1U || add2 == 0U || shift2 == 0U);
        assert(add2 == 0U);
        for (uint64_t num = 0; num < MAX_NUM; ++num) {
            const uint64_t normal = num / d;
            const uint64_t general = (num * mul + add) >> shift;
            const uint64_t bounded = (num * mul2) >> shift2;
            assert(general == normal);
            assert(bounded == normal);
        }
    }
}

請補完程式碼，使 `assert` 巨集不會在執行時期觸發錯誤並運作符合預期。作答規範:
* `AAAA`, `BBBB`, `CCCC`, `DDDD` 皆為整數
* 不該存在小括號 (即 `(` 和 `)`)，以最精簡的形式書寫

:::success
延伸問題:
1. 解釋上述程式碼運作原理，設計實驗來比較除法和 `fastdiv` 的效率，並試圖解釋其行為
2. 以 jemalloc 為例，解說快速除法運算的應用場景。嘗試在 Linux 核心原始程式碼找出類似的技巧
3. [GCC Bug #89845](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=89845) 提及針對整數除法的加速機制，參照到 [Faster Remainder by Direct Computation Applications to Compilers and Software Libraries](https://arxiv.org/pdf/1902.01961.pdf)，嘗試解讀其手段並舉例說明
4. [libdivine](https://github.com/ridiculousfish/libdivide) 提供更進階的除法加速機制，嘗試解釋其原理
:::