課前測驗參考解答: Q1

# 課前測驗參考解答: Q1 ( contributed by coldnew, riversnow, 黃鈺盛 ) - [ ] 考慮以下 C99 程式，解釋其具體作用，並用 for/while 迴圈改寫，隨後提供 uint16\_t 的版本。在什麼場合會用到下方的程式碼？ ```cpp #include <stdint.h> uint32_t func(uint32_t x) { uint32_t n = x; n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } ``` --- ### 想法 & 思考一開始看到這樣的題目可能不知道怎樣解，所以我們可以套用個數值 `0x12345678` 進去一行一行的測試: ```cpp uint32_t n = 0x12345678; n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); printf("0x%x\n", n); // => 0x56781234 ``` 可以發現到第一行是前後 2byte 進行對換的動作，即 `0xAABBCCDD => 0xCCDDAABB` 。接下來讓我們看第二組: ```cpp uint32_t n = 0x56781234; n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); printf("0x%x\n", n); // => 0x78563412 ``` 可以注意到這一組命令，會做出 `0xAABBCCDD` => `0xBBAADDCC` 這樣的運作，也就是對兩個兩個 byte 進行 swap。接下來看第三組，這一組則是將 4 位元 (半個 byte, 英文為 `nibble` ) 進行了 swap。 ```cpp uint32_t n = 0x78563412; n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); printf("0x%x\n", n); // => 0x87654321 ``` 到此，我們已經將原本的 `0x12345678` 轉換成 `0x87654321` 了。接下來這一組直接看看不懂 ```cpp uint32_t n = 0x87654321; n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); printf("0x%x\n", n); // => 0x2d951c84 ``` 因為看不懂，所以我們用二進制來觀察 ``` 從: 0x87654321 => 1000 0111 0110 0101 0100 0011 0010 0001 到: 0x2d951c84 => 0010 1101 1001 0101 0001 1100 1000 0100 ``` 可以看到是對續的兩個 bit 進行對調，用這樣的圖來看就好懂了: ![](https://i.imgur.com/5mhKJbA.png) 終於到了最後一組，來跑看看 ```cpp uint32_t n = 0x2d951c84; n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); printf("0x%x\n", n); // => 0x1e6a2c48 ``` 因為看不懂，所以我們一樣用二進位來觀察 ``` ？: 0xaaaaaaaa => 1010 1010 1010 1010 1010 1010 1010 1010 ？: 0x55555555 => 0101 0101 0101 0101 0101 0101 0101 0101 從: 0x2d951c84 => 0010 1101 1001 0101 0001 1100 1000 0100 到: 0x1e6a2c48 => 0001 1110 0110 1010 0010 1100 0100 1000 原: 0x12345678 => 0001 0010 0011 0100 0101 0110 0111 1000 ``` 在這邊，我們可以透過 `0xaaaaaaaa` 和 `0x55555555` 發現到這邊的運算是對奇數/偶數的位元進行 swap 的動作。此外，如果仔細看可以看出，原本的 `0x12345678` 經過這一系列的運作，變成了 `0x1e6a2c48` ，而從 2 進制來看， `0x12345678` 將所有的 bit 進行反轉，就會得到 `0x1e6a2c48` 。於是我們知道了這個函式用途是作位元的反轉，此函式在將變數做 **LSB->MSB** 和 **LSB->MSB** 之間的轉換，也就是**revserse bit**。我們可以整理前面的分析並將註解加回原始題目去: ```cpp #include <stdint.h> uint32_t reverse_bits_32 (uint32_t n) { /* swap 2-byte long pairs 0xAABBCCDD => 0xCCDDAABB */ n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); /* swap bytes 0xAABBCCDD => 0xBBAADDCC */ n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); /* swap nibbles 0x12345678 => 0x21436587*/ n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); /* swap consecutive pairs */ n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); /* swap odd/even bits */ n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } ``` <a id="orgd6d8041"></a> ### for/while 迴圈版本先建立函式原型 ```cpp uint32_t reverse_bits_32(uint32_t x) { /* FIXME: return the reverse_bits result */ } ``` 接下來需要一個暫存用的變數，我命名為 `reverse_x` (輸入到這函式的變數為 x) ```cpp uint32_t reverse_x = 0; ``` 那要怎樣處理我們的迴圈呢? 我們知道要進行反轉的目標字元數是 `32` , 因此這個迴圈要跑 `32` 次, 所以作個簡單的雛形如下: ```cpp for (int i = 0; i < 32; i++) { /* FIXME: How to do ? */ } ``` 在這個迴圈裡面，我們檢查每一次要被處理的位元，假設他是 `1` 的話，再去更新 `reverse_x` 的內容。(reverse\_x 預設是 0) 更新的方法很簡單，透過 `or` 運算子 `|` 來進行處理，由於我們要做的是字元反轉，因此假如我們 bit[3] 是 1 的話，則 ``` 從: 0000 0000 0000 0000 0000 0000 0000 1000 <- bit[3] = 1 到: 0001 0000 0000 0000 0000 0000 0000 0000 <- bit[28] = 1, bit[32 - 1 - 3] 從: 0000 0000 0000 0000 0000 1000 0000 0000 <- bit[11] = 1 到: 0000 0000 0001 0000 0000 0000 0000 0000 <- bit[20] = 1, bit[32 - 1 - 11] ``` 所以可以知道，當要被處理的位元為 `1` 的時候，我們要這樣處理: ```cpp for (int i = 0; i < 32; i++) { if((x & (1 << i))) reverse_x |= 1 << ((32 - 1) - i); } ``` 因此最後的程式如下: ```cpp #include <stdint.h> uint32_t reverse_bits_32(uint32_t x) { uint32_t reverse_x = 0; for (int i = 0; i < 32; i++) { if((x & (1 << i))) reverse_x |= 1 << ((32 - 1) - i); } return reverse_x; } int main(int argc, char *argv[]) { uint32_t reverse1 = reverse_bits_32( 0x12345678 ); uint32_t reverse2 = reverse_bits_32( reverse1 ); printf("0x12345678 -> 0x%x -> 0x%x\n", reverse1, reverse2); return 0; } ``` 而這程式其實可以再簡化，省掉 `if` 的判斷: ```cpp #include <stdint.h> uint32_t reverse_bits_32(uint32_t x) { uint32_t reverse_x = 0; for (int i = 0; i < 32; i++){ reverse_x |= ( x >> ( ( 32 - 1 ) - i ) & 1 ) << i; } return reverse_x; } ``` <a id="orgc187eb9"></a> ### uint16\_t 版本: 目標為 32-bit 系統或是以上假如目標平台本身就是 32-bit 系統或是更高位元 (64-bit, 128-bit ... etc)，則我們可以直接使用題目的版本作點 shift 就可以得到 `uint16_t` 的版本: ```C #include <stdint.h> uint32_t reverse_bits_32(uint32_t n) { n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); return n; } uint16_t reverse_bits_16(uint16_t x) { return (uint16_t) (reverse_bits_32(x) >> 16); } ``` 這樣子的程式，一樣是可以順利運作的: ``` 從: 0x1234 => 0001 0010 0011 0100 到: 0x3c48 => 0010 1100 0100 1000 ``` <a id="org299c11e"></a> ### uint16\_t 版本: 目標為 16-bit 系統假設今天的目標為 16-bit 系統，我們就不能用 `uint32_t` 的版本，因為系統最大的位元數是 `16-bit` ，如果要用軟體先做到模擬 32-bit 系統，在將其轉換回來這中間的損耗是划不來的。因此我們要考慮自己改寫 `uint32_t` 的版本成 `uint16_t`, 其結果如下: (其實大部分都可以直接套用 32-bit 版本的演算法) ```cpp #include <stdint.h> uint16_t reverse_bits_16(uint16_t n) { /* swap bytes */ n = ((n & 0xff00) >> 8) | ((n & 0x00ff) << 8); /* swap nibbles */ n = ((n & 0xf0f0) >> 4) | ((n & 0x0f0f) << 4); /* swap bit pairs */ n = ((n & 0xcccc) >> 2) | ((n & 0x3333) << 2); /* swap odd/even bits */ n = ((n & 0xaaaa) >> 1) | ((n & 0x5555) << 1); return n; } int main(int argc, char *argv[]) { uint16_t reverse1 = reverse_bits_16( 0x1234 ); uint16_t reverse2 = reverse_bits_16( reverse1 ); printf("0x1234 -> 0x%x -> 0x%x\n", reverse1, reverse2); return 0; } // => 0x1234 -> 0x2c48 -> 0x1234 ``` <a id="org94f27b4"></a> ### uint16\_t 版本: 目標為 16-bit 系統 (迴圈) 承上，目標一樣是 16-bit 的系統，這時候我們的迴圈版本就變成這樣了 (其實和 [for/while 迴圈版本](#orgd6d8041) 差不多): ```cpp #include <stdint.h> uint16_t reverse_bits_16(uint16_t x) { uint16_t reverse_x = 0; for (int i = 0; i < 16; i++) { reverse_x |= ( x >> ( ( 16 - 1 ) - i) & 1 ) << i; } return reverse_x; } int main(int argc, char *argv[]) { uint16_t reverse1 = reverse_bits_16( 0x1234 ); uint16_t reverse2 = reverse_bits_16( reverse1 ); printf("0x1234 -> 0x%x -> 0x%x\n", reverse1, reverse2); return 0; } // => 0x1234 -> 0x2c48 -> 0x1234 ``` 原本的數字為(0xC6A5)_16 = (50863)_10 = (1100 0110 1010 0101)_2 顛倒後的數字(0xA563)_16 = (42339)_10 = (1010 0101 0110 0011)_2 [程式碼視覺化](https://goo.gl/Pud7yW) 這網頁要讓他跑一下 | shift | if (orig & (0x01 << shift)) | result | | :----: | :-----: | :--------: | | 0 | 1 | (32768)_10 = (1000 0000 0000 0000)_2 | | 1 | 0 | (32768)_10 = (1000 0000 0000 0000)_2 | | 2 | 1 | (40960)_10 = (1010 0000 0000 0000)_2 | | 3 | 0 | (40960)_10 = (1010 0000 0000 0000)_2 | | ... | ... | ... | | 14 | 1 | (42338)_10 = (1010 0101 0110 0010)_2 | | 15 | 1 | (42339)_10 = (1010 0101 0110 0011)_2 | ### 硬體指令支援 ARMCortex-M3也有提供RBIT的指令，用來支援FFT運算效能。 ## 應用場景 LSB <-> MSB轉換位元反轉與**Big/Little Endian**的問題類似，常聽到的是指 byte 儲存在記憶體位址的順序，其實Bit也是依照相同順序儲存，在Intel x86架構下，Bit和Byte順序是Little Endian，由LSB (*Least Significant Bit First*)優先；Sun Sparc則是Big Endian，由MSB (*Most Significant Bit First* )優先，ARM則是兩種都支援。 Bit Reverse相關問題也出現在**Data Transmission Order**時，舉例來說，Ethernet Transimission在**Byte**順序是 *Big Endian(leftmost byte is sent first)*，在**Bit**順序是 *little-endian ( LSB Least Significant Bit)*，舉MAC為例說明傳送4bytes的MAC位址，是由LSB開始傳送： | 11100001 | 00001111 | 10101010 | 10010011 | | -------- | -------- | -------- |----------| | Byte1 | Byte2 | Byte3 | Byte4 | 因此接收MAC位址時，每個Byte會是反轉的： | 10000111 | 11110000 | 01010101 | 11001001 | | -------- | -------- | -------- |----------| | Byte1 | Byte2 | Byte3 | Byte4 | 在開發網路、匯流排、序列埠...應用等，都會遇到類似的問題。 :::info [最原始的通訊介面 — RS232與UART的差別](https://makerpro.cc/2019/08/the-difference-between-rs232-and-uart/) ::: 例如CS4215 Audio Codec晶片，當驅動程式透過Short Pipe傳送資料時，Short Pipe是以LSB優先，然而CS4215在接受資料時是用MSB，因此在傳送音樂訊號前，需要先將程式反轉。 ```cpp // sound/sparc/dbri.c static __u32 reverse_bytes(__u32 b, int len) { switch (len) { case 32: b = ((b & 0xffff0000) >> 16) | ((b & 0x0000ffff) << 16); case 16: b = ((b & 0xff00ff00) >> 8) | ((b & 0x00ff00ff) << 8); case 8: b = ((b & 0xf0f0f0f0) >> 4) | ((b & 0x0f0f0f0f) << 4); case 4: b = ((b & 0xcccccccc) >> 2) | ((b & 0x33333333) << 2); case 2: b = ((b & 0xaaaaaaaa) >> 1) | ((b & 0x55555555) << 1); case 1: case 0: break; } return b; } /* DBRI short pipes always transmit LSB first */ if (dbri->pipes[pipe].sdp & D_SDP_MSB) data = reverse_bytes(data, dbri->pipes[pipe].length); ``` ### 使用到的場合: 快速傅利葉轉換背景知識: [Wave](http://www.csie.ntnu.edu.tw/~u91029/Wave.html) - 運用正向傅立葉轉換分解一個波，運用逆向傅立葉轉換合成一個波，運用頻譜解讀波的詳細內容。傅立葉轉換是一對一函數，一種波對應一種頻譜。頻譜的左側到右側，是低頻到高頻。 - 把一個波實施正向傅立葉轉換，將低頻數值或者高頻數值改成零，再實施逆向傅立葉轉換，改造原本的波。這是十分常用的技巧。 - 頻譜是非常實用的分析工具。凡是學習科學的人，都有必要了解頻譜！各種物質的振動或振盪，皆可求得頻譜，發掘其特性。例如震譜是震波的頻譜，光譜是光波的頻譜，聲譜是聲波的頻譜。世間萬物皆有譜，應用無限廣泛。在進行快速傅利葉轉換(Fast Fourier Transform, FFT)之前，我們會需要進行位元反轉 (bit reverse)，從 [FAST BIT-REVERSAL ALGORITHM](http://www.idi.ntnu.no/~elster/pubs/elster-bit-rev-1989.pdf) 論文一開頭的描述來看: ![](https://i.imgur.com/HkEzXe7.png) 足以知道位元反轉 (bit reverse) 對於快速傅利葉轉換(FFT)的重要性。因為只使用到bitwise operator與data move，這個函式的時間複雜度是O(1)，換言之，程式碼執行時間是 deterministic (明確的、已確定的)。 (註: [Unscrambling for fast DFT algorithms](http://ieeexplore.ieee.org/document/1631/?denied) 此外，在 [Bit Reversal on Uniprocessors](http://www.hpl.hp.com/techreports/93/HPL-93-89.pdf) 這篇文章也列舉了 30 種用來作位元反轉(bit reverse)的演算法，用來測試在不同硬體上面的效能比較。 ### 使用到的場合: 加解密運算透過本題的程式，可以將 `0x12345678` 轉變成 `0x1e6a2c48` ，而這動作是可以反向的, 我們一樣可以將此函式套用在 `0x1e6a2c48` 從而得到 `0x12345678` 這樣的答案，也就是說將東西丟給這個函式，再把結果丟給這函式，可以得到原本的輸入: ```cpp 0x12345678 == reverse_bits( reverse_bits(0x12345678) ) /* 兩者相等 */ ``` 利用這種特性，我們可以實作簡單的加解密程式 `rcf.c` ，如下: ```cpp #include <stdio.h> #include <stdlib.h> #include <stdint.h> uint32_t reverse_bit(uint32_t x) { x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16); x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8); x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4); x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2); x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1); return x; } int main(int argc, char *argv[]) { if (argc < 3) { printf( "\nUsage:" "\t %s input.txt output.txt\n\n" "This is a simple encrypt/decrypt app " "based on reverse_bit algorithm.\n\n" , argv[0]); return 0; } const char *input_path = argv[1]; FILE *fin = fopen(input_path, "rb"); if (!fin) { fprintf(stderr, "ERROR: failed to open input file %s\n", input_path); exit(-1); } const char *output_path = argv[2]; FILE *fout = fopen(output_path, "wb"); if (!fout) { fclose(fin); fprintf(stderr, "ERROR: failed to open output file %s\n", output_path); exit(-1); } uint32_t ch; int nread; while((nread = fread(&ch, 1, sizeof(uint32_t), fin)) > 0) { /* if read size less than sizeof(uint32_t), just write it */ if (nread < sizeof(uint32_t)) { fwrite(&ch, 1, nread, fout); } else { uint32_t chn = reverse_bit(ch); fwrite(&chn, 1, nread, fout); } } fclose(fin); fclose(fout); return 0; } ``` 這個程式可以使用以下命令進行編譯: ``` gcc rcf.c -o rcf ``` 那要如何使用呢? 我們可以建立一個名為 `hello.txt` 的文字檔，有以下內容: ``` hello, this is a test ``` 接下來使用這隻加密程式產生新的檔案叫做 `hello_enc.txt` ``` ./rcf hello.txt hello_enc.txt ``` 打開可以看到內容如下: (是不是成功加密了!) ``` 66¦^V.^D4ö^DÎ<96>^V<86>^DÎ<96>Î¦.^Dt ``` 而這個檔案我們一樣可以透過這隻程式進行解密成 `hello_dec.txt` ``` ./rcf hello_enc.txt hello_dec.txt ``` 打開 `hello_dec.txt` 看看，內容是不是和原來的一樣 ? ``` hello, this is a test ``` ### 使用到的場合: CRC-32 運算從 [使用到的場合: 加解密運算](#org15beed3) 這邊可以知道僅僅只是反轉一下位元就可以製作加解密程式，[循環冗餘校驗 (CRC)](https://zh.wikipedia.org/zh-tw/循環冗餘校驗) 的實作也可以用到位元反轉 (bit reverse) 的部分。具體實作可以參考: - [Hacker's Delight - crc.c](http://www.hackersdelight.org/hdcodetxt/crc.c.txt) ### 使用到的場合: Linux Kernel Linux kernel 裡面有實作 `bitrev32` 等位元反轉的命令，可以在 [bitrev.h](http://elixir.free-electrons.com/linux/v4.12/source/include/linux/bitrev.h) 看到，最常用到的用途，則是在 `ether_crc()` 這個函式上: ```cpp /* * Helpers for hash table generation of ethernet nics: * * Ethernet sends the least significant bit of a byte first, thus crc32_le * is used. The output of crc32_le is bit reversed [most significant bit * is in bit nr 0], thus it must be reversed before use. Except for * nics that bit swap the result internally... */ #define ether_crc(length, data) bitrev32(crc32_le(~0, data, length)) #define ether_crc_le(length, data) crc32_le(~0, data, length) ``` ### 使用到的場合: redis - [redis](https://github.com/antirez/redis/blob/3.0/src/dict.c#L755) ### 補充: Clang 與 GCC 支援 Clang 是有內建 [字元反轉](http://clang.llvm.org/docs/LanguageExtensions.html#builtin-bitreverse) 的函式的，然而根據 [BUG 50481](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=50481) 來看 GCC 是尚未支援內建這功能。以下為 Clang 內建的版本說明如下: ![](https://i.imgur.com/1tqbwFE.png) <a id="org486d8c7"></a> ### 補充: C 語言實作 2 進制的 print 函式以下提供以將 `uint32_t` 型別的輸入，以二進制的形式顯示出來的工具函式: ```cpp #include <stdint.h> void print_binary(uint32_t x) { unsigned char *p = (unsigned char *) &x; unsigned char byte; for (int i = sizeof(uint32_t) -1; i >= 0; i--) { for (int j = 7; j >= 0; j--) { byte = (p[i] >> j) & 1; printf("%u", byte); if (0 == (j % 4)) printf(" "); } } printf("\n"); } int main(int argc, char *argv[]) { print_binary(0x12345678); return 0; } // => 0001 0010 0011 0100 0101 0110 0111 1000 ``` ### 延伸閱讀 * [Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C - Stack Overflow](https://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c) * [In C/C++ what's the simplest way to reverse the order of bits in a byte? - Stack Overflow](https://stackoverflow.com/questions/2602823/in-c-c-whats-the-simplest-way-to-reverse-the-order-of-bits-in-a-byte) * [Bit Twiddling Hacks - Reverse an N-bit quantity in parallel in 5 \* lg(N) operations](http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious) * [The Aggregate Magic Algorithms - Bit Reversal](http://aggregate.org/MAGIC/#Bit%2520Reversal) * [Reversing Bits and Bytes](http://bsmartt13.github.io/blog/2012/01/05/reversing-bits-and-bytes/) * [Bit Reversal on Uniprocessors](http://www.hpl.hp.com/techreports/93/HPL-93-89.pdf) * [一般信號處理，常用快速傅立葉轉換（FFT）來求得信所對應的頻譜](http://eshare.stust.edu.tw/EshareFile/2010_6/2010_6_a78298c9.pdf) * [快速傅立葉轉換 | 線代啟示錄](https://ccjou.wordpress.com/2012/05/25/%E5%BF%AB%E9%80%9F%E5%82%85%E7%AB%8B%E8%91%89%E8%BD%89%E6%8F%9B/)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.