從 select.h 學 bit mask

最近在寫的程式需要同時開很多檔案以便做 N-way merge。為了記錄已經 open 了哪些 file descriptors，就必須要有一個資料結構可以儲存這些開開關關的資訊。
對於處理這種「不是 on，就是 off」狀態的資訊，最直覺的做法就是用 bit mask。 在 FreeBSD amd64 中，一個 long 型態的變數是 8 bytes， 64 bits，所以一個 long 就有 64 個 bit flags 可以用，也就是可以記錄由 0 ~ 63 的 fd 編號：
        long fd_mask;
        /* set on bit no.64 */
        fd_mask |= 1 << 63;
        /* set on bit no.1 */
        fd_mask |= 1 << 0;
假如需要記錄的 fd 個數超過 64 個，那就必須另外宣告一個 long 型態的變數來使用。而把相同功能的變數放在一起最直覺的方式就是用陣列，現在要記錄的是 1024 個 fds（0~1023），那就宣告一個 16 個 long 的陣列：
        long fd_setsize = 1024;
        /* 1024 / 64 = 16 */
        long fd_mask[16];
接著遇到的問題是，對於一個 fd（0~1023），我怎麼知道要把它定位在「哪一個 long （layer）的哪一個 bit（position）」？透過除法與取餘數可以分別解決這兩個定位的問題，所以：
        long fd_setsize = 1024;
        long fd_mask[16];

        int x;
        int layer = x / 64;
        int position = x % 64;
有這樣的知識後，我們就可以產生一個設定 bit mask 的函式：
        long fd_setsize = 1024;
        long fd_mask[16];
        void fd_set(fd, long *fd_set) {
                fd_set[fd_setsize / 64] |= (1 << (x % 64));
        }
        /* will set 1 on layer 0, bit no.1 */
        fd_set(0, fd_mask);
        /* will set 1 on layer 15, bit no.64 */
        fd_set(1023, fd_mask);
這也是在 select.h 中，FD_SET 巨集的概念，其它的 FD_ZERO、FD_ISSET 和 FD_CLR 也都採用相同的定位方式。
還有一個問題在於：如何宣告一開始的 long array 要多大？
如果要處理的 fd 個數可以有 1024 個，那麼由 1024 / 64 得到的值，就會是剛好的大小；但是如果要處理的 fd 個數是 1025 個，那麼除出來的值（沒有小數），會跟上面一樣，因此得到錯誤的結果（需要 17 而不是 16）。
        #define how_big(x) (x) / 64
        long fd_mask[how_big(x)];
        /* x = 64, fd: 0 ~ 63 */
        => long fd_mask[1];
        /* x = 65, fd: 0 ~ 64 */
        => long fd_mask[1]; /* wrong, we need 2 layers. */
如果把純的除法改成這樣，那問題就解決了：
        #define how_big(x) ((x) + 64 - 1) / 64
        long fd_mask[how_big(x)];
        /* x = 64, fd: 0 ~ 63 */
        => long fd_mask[1];
        /* x = 65, fd: 0 ~ 64 */
        => long fd_mask[2];
實際上，這樣的函數是一個 ceiling function，剛好符合這個問是的特性：
        z = (x + (y - 1)) / y,  y = 64
        x = 0, z => 0
        x = 1~64, z => 1
        x = 65~128, z => 2
以上，是從 select.h 裡面學到的技巧…。