# 課前測驗參考解答: 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 進行對調，用這樣的圖來看就好懂了:
終於到了最後一組，來跑看看
```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) 論文一開頭的描述來看:
足以知道位元反轉 (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 內建的版本說明如下:
<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/)
Sign in with Wallet
Connect another wallet