MSB <-> LSB / bit reverse

定義

• MSB : Most Significant Bit(or Byte) 這邊指bit
• LSB : Least Significant Bit(or Byte) 這邊指bit
• C99標準庫 stdint.h

C語言中，有幾種基本資料型態
1. 整數: float, double
2. 浮點數: short, int, long
3. 字符: char

型態	記憶體大小(byte)
short	2
int	4
long	8
float	4
double	8
char	1

在stdint.h 用typedef定義了不同的資料型態
_t結尾表示使用typedef定義已知的資料型態，
只要include stdint.h標頭檔，即可使用

資料型態	typedef
char	int8_t
short	int16_t
int	int32_t
long	int64_t
long long	int64_t
unsigned char	uint8_t
unsigned short	uint16_t
unsigned int	uint32_t
unsigned long	uint64_t
unsigned long long	uint64_t

Reverse Bit (MSB <-> LSB) 程式碼

• uint32_t 版本

#include <stdint.h>
#include <stdio.h>
int main(){
    uint32_t n = 0x12345678;
    n = ((0xffff0000 & n) >> 16) | ((0x0000ffff & n) << 16);
    printf("0x%x \n", n);
    n = ((0xff00ff00 & n) >> 8) | ((0x00ff00ff & n) << 8);
    printf("0x%x \n", n);
    n = ((0xf0f0f0f0 & n) >> 4) | ((0x0f0f0f0f & n) << 4);
    printf("0x%x \n", n);
    n = ((0xcccccccc & n) >> 2) | ((0x33333333 & n) << 2);
    printf("0x%x \n", n);
    n = ((0xaaaaaaaa & n) >> 1) | ((0x55555555 & n) << 1);
    printf("0x%x \n", n);
}

Output:

0x56781234
0x78563412
0x87654321
0x2d951c84
0x1e6a2c48

講解

step 1:
n = 0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000

0xffff0000 : 1111 1111 1111 1111 0000 0000 0000 0000
0x0000ffff : 0000 0000 0000 0000 1111 1111 1111 1111

(n & 0xffff0000) >> 16 會剩下最左邊兩個bytes，然後往右邊shift 2bytes 就會被放到最右邊兩個bytes的位置
(n & 0x0000ffff) << 16 會剩下最右邊兩個bytes，然後往左邊shift 2bytes 就會被放到最左邊兩個bytes的位置
最後 or(|) 起來，就會左右兩個bytes對調

step 2:
n = 0x56781234 = 0101 0110 0111 1000 0001 0010 0011 0100

0xff00ff00 : 1111 1111 0000 0000 1111 1111 0000 0000
0x00ff00ff : 0000 0000 1111 1111 0000 0000 1111 1111

(n & 0xff00ff00) >> 8 會將四個bytes裡面從左邊數過來第1、3個bytes留下，然後往右邊shift 1byte 就會被移到第2、4個bytes
(n & 0x00ff00ff) << 8 會將四個bytes裡面從左邊數過來第2、4個bytes留下，然後往左邊shift 1byte 就會被移到第1、3個bytes
最後 or(|) 起來，就會是1、2互換 3、4互換

step 3:
n = 0x78563412 = 0111 1000 0101 0110 0011 0100 0001 0010

0xf0f0f0f0 : 1111 0000 1111 0000 1111 0000 1111 0000
0x0f0f0f0f : 0000 1111 0000 1111 0000 1111 0000 1111

(n & 0xf0f0f0f0) >> 4 會將8個半byte裡面的1、3、5、7留下，向右邊shift半個byte，會變成在2、4、6、8半byte的位置
(n & 0x0f0f0f0f) << 4 會將8個半byte裡面的2、4、6、8留下，向左邊shift半個byte，會變成在1、3、5、7半byte的位置
最後 or(|) 起來，就會是半byte swap， 1 and 2 / 3 and 4 / 5 and 6 / 7 and 8

step 4:
n = 0x87654321 = 1000 0111 0110 0101 0100 0011 0010 0001

0xcccccccc : 1100 1100 1100 1100 1100 1100 1100 1100
0x33333333 : 0011 0011 0011 0011 0011 0011 0011 0011

(n & 0xcccccccc) >> 2 會將每半byte裡面的前兩個bit留下，向右邊shift兩個bit，會變成在後兩個bit的位置
(n & 0x33333333) << 2 會將每半byte裡面的後兩個bit留下，向左邊shift兩個bit，會變成在前兩個bit的位置
最後 or(|) 起來，就會是每半個byte裡面的前兩個位元和後兩個位元交換

step 5:
n = 0x2d951c84 = 0010 1101 1001 0101 0001 1100 1000 0100

0xaaaaaaaa : 1010 1010 1010 1010 1010 1010 1010 1010
0x55555555 : 0101 0101 0101 0101 0101 0101 0101 0101

(n & 0xaaaaaaaa) >> 1 會將每半個byte裡面的1、3 bit 留下，往右shift 1 bit，會變成在2、4 bit的位置
(n & 0x55555555) << 1 會將每半個byte裡面的2、4 bit 留下，往左shift 1 bit，會變成在1、3 bit的位置
最後 or(|) 起來，就會是每半個byte裡面的1、2 bit交換，3、4 bit交換

最後 n = 0x1e6a2c48 = 0001 1110 0110 1010 0010 1100 0100 1000
原本 n = 0x12345678 = 0001 0010 0011 0100 0101 0110 0111 1000
reverse bit完成

• uint32_t while/for 版本

#include <stdint.h>
#include <stdio.h>
int main(){
    uint32_t n = 0x12345678;
    int x = 0;
    for (int i = 0; i < 32; i++) {
        int byte = (n >> (32 - 1 - i) & 1) << i;
        x |= byte;
    }
    /*
    0000 0000 0000 0000 0000 0000 0000 0000
    左邊第一位數開始編號為31 .... 最右邊為0
    (31th bit) shift (32 - 1) - 0 之後會跑到最右邊跟 1 & 判斷為0 or 1，最後往右邊shift 0 
    (30th bit) shift (32 - 1) - 1 之後會跑到最右邊跟 1 & 判斷為0 or 1，最後往右邊shift 1
    要替換的兩個bit，所在位置編號相加會是31
    */
    printf("0x%x \n", x);
}

• uint16_t 版本 (為 32-bit或者以上的系統)

#include <stdint.h>
#include <stdio.h>
uint32_t reverse_uint32(uint32_t n){

    n = ((0xffff0000 & n) >> 16) | ((0x0000ffff & n) << 16);
    n = ((0xff00ff00 & n) >> 8) | ((0x00ff00ff & n) << 8);
    n = ((0xf0f0f0f0 & n) >> 4) | ((0x0f0f0f0f & n) << 4);
    n = ((0xcccccccc & n) >> 2) | ((0x33333333 & n) << 2);
    n = ((0xaaaaaaaa & n) >> 1) | ((0x55555555 & n) << 1);
    return n;
}
uint16_t reverse_uint16(uint16_t n) {
    uint16_t x = (uint16_t)(reverse_uint32(n) >> 16);
    return x;
}

int main(){
    uint16_t a = 0x1234;
    uint32_t answer = reverse_uint16(a);
    printf("0x%x\n", answer);
}

Output:

0x2c48

• uint16_t 版本: (為 16-bit 系統)

16-bit的系統不能再使用uint_32，因為系統最高只有到16 bits

#include <stdint.h>
#include <stdio.h>

uint16_t reverse_uint16(uint16_t n){
    n = ((0xff00 & n) >> 8) | ((0x00ff & n) << 8);
    n = ((0xf0f0 & n) >> 4) | ((0x0f0f & n) << 4);
    n = ((0xcccc & n) >> 2) | ((0x3333 & n) << 2);
    n = ((0xaaaa & n) >> 1) | ((0x5555 & n) << 1);
    return n;
}

int main(){
    uint16_t a = 0x1234;
    uint16_t answer = reverse_uint16(a);
    printf("0x%x\n", answer);
}

Output:

0x2c48

• uint16_t while/for版本: (為 16-bit 系統)

#include <stdint.h>
#include <stdio.h>

uint16_t reverse_uint16(uint16_t n){
    uint16_t answer = 0;
    for (int i = 0; i < 16; i++) {
        // n >> (16 - 1 - i) & 1 << i, without parentheses will cause wrong answer
    uint16_t bit = (n >> (16 - 1 - i) & 1) << i;
    answer |= bit;
    }
    return answer;
}

int main(){
    uint16_t a = 0x1234;
    a = reverse_uint16(a);
    printf("0x%x\n", a);
    a = reverse_uint16(a);
    printf("0x%x\n", a);

}

Output:

0x2c48
0x1234

應用場景 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

在開發網路、匯流排、序列埠…應用等，都會遇到類似的問題。例如CS4215 Audio Codec晶片，當趨動程式透過Short Pipe傳送資料時，Short Pipe是以LSB優先，然而CS4215在接受資料時是用MSB，因此在傳送音樂訊號前，需要先將程式反轉。

參考資料

C語言資料型態
C語言stdint.h
位元組順序 (Byte Order or Endianness) — big-endian vs. little-endian
jserv Linux核心設計wiki

tags: C

​

Bit-wise Operation

• Clear a bit

a &= (1 << n) // clear nth bit

unsigned char a = 65;
printf("%c\n", a);
int n = 0;
a &= ~(1 << n); // a = 64
printf("%c\n", a);

Output:

A
@

• Set a bit

a |= (1 << n) // set nth bit

int main(){
    unsigned char b = 64;
    printf("%c \n", b);
    printf("%d \n", b);
    b |= (1 << 0);
    printf("%c \n", b);
    printf("%d \n", b);
}

Output:

@
64
A
65

• Toggle a bit

a ^= (1 << n) // Toggle nth bit

int main(){
    unsigned char b = 5;
    printf("Origin : %d \n", b);    // 0101

    b ^= (1 << 0);
    printf("Toggle 0th : %d \n", b);// 0100

    b ^= (1 << 1);
    printf("Toggle 1th : %d \n", b);// 0110

    b ^= (1 << 2);
    printf("Toggle 2th : %d \n", b);// 0010

    b ^= (1 << 3);
    printf("Toggle 3th : %d \n", b);// 1010
}

Output:

Origin : 5
Toggle 0th : 4
Toggle 1th : 6
Toggle 2th : 2
Toggle 3th : 10

• Two’s Complement

是一種用二進位表示有號數的方法，也是一種將數字的正負號變號的方式。
正數和0的二補數就是該數字本身。負數的二補數則是將其對應正數按位元取反再加1。
1 : 0001
-1: 1111
1 取反 -> 1110 -> 1110 + 1 -> 1111 -> -1

• Sign bit

// if value is 2 bytes
bool sign = val & 0x8000
/*
      val : 0001 0000 0101 0011
(&) 0x8000: 1000 0000 0000 0000
we only care about the sign bit(left first).
*/

• The right most byte(Least Significant byte / LSB)

// assuming val is 16 bit, 2-byte short integer
unsigned char lsb = val & 0xff
/*
     val: 0101 0101 "1010 1010"
(&) 0xff: 0000 0000  1111 1111
---------------------------------
          0000 0000  1010 1010
          Only get the last byte

*/

• The left most byte(Most Significant byte / MSB)

// assuming val is 16 bit, 2-byte short integer
unsigned char msb = (val >> 8) & 0xff 
/*
      val: "0101 0101" 1010 1010

val >> 8: 0000 0000 0101 0101
(&) 0xff: 0000 0000 1111 1111
---------------------------------
          0000 0000 0101 0101
          only get the first byte
*/

• Show Binary

int val = 85;
for (int i = 7; i >= 0; i--){
    int bit = (val >> i) & 1;
    printf("%d ", bit);
}
printf("\n");

Output:

0 1 0 1 0 1 0 1

• Test a bit

int d = 5; // 0101
int n = 2; 
unsigned char e = d & (1 << n); // 0101 & (0100)
printf("%d\n", e);

Output:

4

• Sample

#include <stdio.h>
#include <stdbool.h>
bool getBit(int n, int index) {
    return ((n & (1 << index)) > 0);
}

int setBit(int n, int index, bool b) {
    if (b)
        return (n | (1 << index));    
    int mask = ~(1 << index);
    return n & mask;
}

int main() {
    int num = 16, index;

    printf("Input\n");
    for (int i = 7; i >= 0; i--) 
        printf("%d ", getBit(num,i));
    printf("\n");

    /* set bit */
    index = 6;
    printf("Setting %d-th bit\n", index);
    num = setBit(num, index, true);
    for (int i = 7; i >= 0; i--) 
        printf("%d ", getBit(num,i));
    printf("\n");

    /* unset (clear) bit */
    index = 4;
    printf("Unsetting (Clearing) %d-th bit\n", index);
    num = setBit(num, index, false);
    for (int i = 7; i >= 0; i--) 
        printf("%d ", getBit(num,i));
    printf("\n");

    return 0;
}

Output:

Input
0 0 0 1 0 0 0 0
Setting 6-th bit
0 1 0 1 0 0 0 0
Unsetting (Clearing) 4-th bit
0 1 0 0 0 0 0 0

• 參考資料
  二補數
  Bit-wise Operations

tags: Linux C

​

Makefile筆記

引言

在了解Makefile之前，首先要了解C/C++的程式是怎麼被執行的，
C/C++的原始碼(.c / .cpp)，需要經由編譯器(compiler)編譯成機械碼(.o / .obj)，
也就是電腦系統看得懂的語言，最後經由Linker(連結器)將所有的*.o / *.obj做結合，產生.exe檔案。

Makefile 基本認識

如果單純只有少少的幾個檔案(.c / .h)之類的，
那只要在termial跑簡單幾個指令就可以完成編譯、連結的動作
$ gcc -c main.c // 產生 main.o
$ gcc -o test main.o // 產生 test.exe
這樣就結束了，但是當檔案一多，且彼此有了相依性(必須先執行A，才能再執行B)，
指令的下達就會變得非常的複雜。

此時有一個非常方便的工具 make，下達這個指令後，
電腦會到路徑下找到Makefile去依照裡面所撰寫的法則來進行編譯、連結。
p.s.
    1. .h: 方法聲明
    2. .c: 方法實現
    3. .o: 機械碼

使用Makefile的好處

1. 如果這個專案沒有編譯過，那麼我們的所有程式碼都要編譯並被連結
2. 如果這個專案的某幾份程式碼被修改，那麼我們只編譯被修改的程式，並連結目標程式 (會依檔案更改的時間做判斷)
3. 如果這個專案的標頭檔被改變了，那麼我們需要編譯引用了這幾個標頭檔的程式碼，並連結目標程式 (會依檔案更改的時間做判斷)

Makefile 包含

1、顯式規則。顯式規則說明了，如何生成一個或多的的目標檔案。這是由Makefile的書寫者明顯指出，要生成的檔案，檔案的相依性檔案，生成的命令。

2、隱晦規則。由於我們的make有自動推導的功能，所以隱晦的規則可以讓我們比較粗糙地簡略地書寫Makefile，這是由make所支持的。

3、變量的定義。在Makefile中我們要定義一系列的變量，變量一般都是字串，當Makefile被執行時，
其中的變量都會被擴展到相應的引用位置上。

4、檔案指示。其包括了三個部分，一個是在一個Makefile中引用另一個 Makefile，就像C語言中的include一樣；
另一個是指根據某些情況指定Makefile中的有效部分，就像C語言中的預編譯#if一樣；還有就是定義一個多行的命令。

5、註釋。Makefile中只有行註釋，和UNIX的Shell腳本一樣，其註釋是用「#」字符，
這個就像C/C++中的「//」一樣。如果你要在你的Makefile中使用「#」字符，可以用反斜框進行轉義，如：「\#」。

最後，還值得一提的是，在Makefile中的命令，必須要以[Tab]鍵開始。

Makefile 語法規則

• 在默認的狀況下我們在shell下達make的指令，會自動去找目錄下的Makefile or makefile
  $ make
• 顯性規則

冒號前面為目標文件，冒號後面表示需要產生目標文件的需要文件(相依性)，tab後面加入命令

# 產生test，需要main.o，如果有main.o執行下面命令以產生test
test:main.o
<tab> gcc -o test main.o

• 隱性規則

目標文件假設為.o檔案，make會自動將所對應的.cpp / .c 檔案歸類於必要條件，因此不用書寫。

main.o:(main.cpp) test.cpp
    g++ -c main.cpp

• 變數

1. 變數巨集
obj = main.o ball.o test.o
// 可以用 $(obj) 來表示這三個檔案

2. 自動化變數
$<: 表示第一個必要條件的檔名
$@: 工作目標的檔名
$^: 所有必要條件的檔名，用空格隔開
test: main.o
    g++ -o $@ $<

main.o: main.cpp test.cpp
    g++ -c $^

3. 特殊變數
-: 表示即使該行指令出錯，也不會中斷執行，而 make 只要遇到任何錯誤就會中斷執行。
但像是在進行 clean 時，也許根本沒有任何檔案可以 clean，因而 rm 會傳回錯誤值，
因而導致 make 中斷執行。我們可以利用 - 來關閉錯誤中斷功能，讓 make 不會因而中斷。

@: 不要顯示執行的指令，因執行 make 指令後會在終端機印出正在執行的指令

• 偽目標

在下例中，若不使用 .PHONY 來指定 clean 為 fake 項目的話，若目錄中同時存在了一個名為 clean 的檔案，
則 clean 這個項目將被視為要建立 clean 這個檔案，但 clean 這個項目卻又沒有任何的 dependencies，
也因此，clean 項目將永遠被視為 up-to-date，永遠不會被執行。
因為利用了 .PHONY 來指定 clean 為 fake 項目，所以 make 不會去檢查目錄中是否存在了一個名為 clean 的檔案。
如此也可以提昇 make 的執行效率。

p.s. 使用clean，要下達make clean的指令

.PHONY: clean
clean:
    rm *.o

Makefile簡單試寫

obj = source/main.o source/ball.o
test:source/main.o source/ball.o
    g++ -o test source/main.o source/ball.o
    #g++ -o $@ $^
main.o:source/main.cpp source/ball.cpp
    g++ -c source/main.cpp
#Ball.o:(source/ball.cpp) header/ball.h
Ball.o:source/ball.cpp header/ball.h
    g++ -c source/ball.cpp
.PHONY:clean
clean:
    echo "clean..."
    rm -f test source/*.o

補充說明

*.h檔案作為聲明使用，通常只會被*.cpp /*.c 所include
若有以下檔案: main.cpp, ball.cpp, ball.h
ball.cpp 會 include ball.h
main.cpp 也會include ball.h 但是不用include ball.cpp，因為只需要聲明，若main執行到需要用到ball的function時，
會jump到ball.cpp記憶體所在位置執行。(我的理解啦XD)

參考資料

編譯器與連結器的基本概念
Makefile寫法與語法
Makefile語法和示範
Makefile

tags: Linux

​

C++ Reference Variable 參考

概念

參考是變數別名，當參考被改變變數的值也會改變。
常常用在傳入函式的參數，因為一般的變數傳入函式中是複製一份去做計算，
但是參考的話是複製位址，因此更改後不會因為離開函式而變回原本的值。
另外，以參考為參數傳入函式，可以避免stack overflow的問題，
因為參考是複製位址，並非複製整個變數。

語法示範

• 以&為開頭表示使用參考，與取址一樣的符號，但在宣告時使用即是代表要做參考
  ex:

    string name = "Tony";
    // 使用參考
    string &nickName = name;
    // 取地址
    cout << &name << endl;

• 使用參考時必須一開始就初始化
• 參考一旦決定了為那個變數的參考後便不能再更改
  ex:

    string name = "Tony";
    string &nickname = name;
    string otherName = "Annie";
    &nickname = otherName; // 錯誤

• const參考與其他變數使用const相同，不能更改
  ex:

    string testName = "test";
    const string &ref = testName;
    testName = "pass";
    cout << testName << endl; // output: pass
    cout << ref << endl;      // output: pass

    // const can't be changed
    ref = "impossible"; // error

• 範例

#include <iostream>
using namespace std;

int main() {
    string name = "Tony";
    string others = "Annie";
    string &nickname = name;

    // reference need to be initialized at beginning
    // error : string &wrong;

    // reference can not change the connection
    // error : &nickname = others;   // because nickname is the reference of name

    // const can not be changed
    string testName = "test";
    const string &ref = testName;
    testName = "pass";
    cout << testName << endl; // output: pass
    cout << ref << endl;      // output: pass

    // const can't be changed
    // error : ref = "impossible";


    cout << "name: " << name << ", address: " << &name <<endl;        // name: Tony, address: 0x7fff59f9e918
    cout << "nickname: " << nickname << ", address: " << &nickname <<endl;    // name: Tony, address: 0x7fff59f9e918

    nickname = "Tom";
    cout << "name: " << name << ", address: " << &name <<endl;        // name: Tom, address: 0x7fff59f9e918
    cout << "nickname: " << nickname << ", address: " << &nickname <<endl;  // name: Tom, address: 0x7fff59f9e918

    name = "James";
    cout << "name: " << name << ", address: " << &name <<endl;         // name: James, address: 0x7fff59f9e918
    cout << "nickname: " << nickname << ", address: " << &nickname <<endl;  // name: James, address: 0x7fff59f9e918
}

應用

#include <iostream>
using namespace std;

void swapNormal(int, int);
void swapRef(int &, int &);

int main() {
     int a = 1000;
    int b = 10;
    cout << "Without any manipulation..." << endl;
    cout << "a: " << a << endl;
    cout << "b: " << b << endl;
    swapNormal(a, b);
    cout << "After swapNormal:" << endl;
    cout << "a : " << a << endl;
    cout << "b : " << b << endl;

    swapRef(a, b);
    cout << "After swapRef:" << endl;
    cout << "a : " << a << endl;
    cout << "b : " << b << endl;
}

void swapNormal(int x, int y) {
    cout << "In swapNormal..." << endl;
    /*
        複製一份
        x = a;
        y = b;
    */
    int tmp;
    tmp = x;
    x = y;
    y = tmp;

    cout << "a: " << x << endl;
    cout << "b: " << y << endl;
}
void swapRef(int &x, int &y) {
    cout << "In swapRef..." << endl;
    /*
        複製一份
        &x = a;
        &y = b;
    */
    int tmp;
    tmp = x;
    x = y;
    y = tmp;

    cout << "a: " << x << endl;
    cout << "b: " << y << endl;
}

output:

Without any manipulation...
a: 1000
b: 10
In swapNormal...
a: 10
b: 1000
After swapNormal:
a : 1000
b : 10
In swapRef...
a: 10
b: 1000
After swapRef:
a : 10
b : 1000

tags: C++

​