3.30.2010

從 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),我怎麼知道要把它定位在「哪一個 longlayer)的哪一個 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_ZEROFD_ISSETFD_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 裡面學到的技巧…。

2 則留言:

匿名 提到...

To get pleasure from our VIP video games, you must have a minimum of|no less than} 20,000 Credits in 카지노사이트 your on-line account. However, Golden Buffalo is a recreation that's broadly tested on a number of} casino websites. For this cause, we can to} affirm that it has an RTP of round 96%.

1rt9uu06w7 提到...

In most varieties of the game, a participant receiving two cards of the identical rank might cut up them, receiving a second card for every, and play the 2 hands independently of each other. Another widespread rule is to permit “doubling down” with two cards that complete 11 —the participant doubles the guess, turns up the playing cards, and takes another card facedown. In some video games a participant wins additional by getting 5 cards without “going bust” . In this on-line casino recreation, your host will briefly explain blackjack guidelines and primary technique, including the essential ideas of dealing, common gameplay, when to hit, and when to stay. Then, players will put their skills to the take a look at in an internet blackjack recreation. Each participant will 카지노사이트 place their bets for every round utilizing the virtual poker chips proven on the desk with the objective of accumulating as many chips as possible.