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

​