2023q1 Homework2 (quiz2)

contributed by <Urbaner3>

tags: linux2022 Linux Kernal

測驗 1

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
	x |= x >> 1; /*add a line to make it work*/
    x |= x >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}

將 x 右移並與 x 做或運算，會從有1的位數，右移後加回本為零的位數，增加顯示1的位元。題目有提示說到，依次右移1,2,4,8,16,32,64。因為一旦到達指定數字樣式，即1…1，右移多少位元，因為沒有零的位數，數字都不會變，且是我們要的樣式。若不是按照2的等比數列，如1,3,5,…中間會有零的位數，就不是冪減一了，不是全位數1的2進位數。所以 AAAA = 1。 奇怪這樣有落差，少了一行右移一，加入一行。AAAA = 8, BBBB = 32, CCCC = x+1

延伸問題

1. 解釋上述程式碼原理，並用 __builtin_clzl 改寫
   (程式POW)

#include <stdint.h>
static unsigned long int next_pow2(unsigned long int x)
{
    int zs = __builtin_clzl(x); /*zeros;*/
    return 1 << (sizeof(unsigned long int)-zs);
} 

解釋如前段，為了得到相同輸出，直接對1做左移。
2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
weak clz/ctz

int __weak __clzdi2(long val)
{
	return 64 - fls64((u64)val);
}

fls64 not in <linux/export.h, kernel.h> = linux/include/linux/kernel.h better eq. 函數回傳由右向左數的非零位數，用64減去該數，得到左邊開始連續0的位數數量。
3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？
參考 aaron ，執行 cc

	.file	"next_pow2.c"
	.text
	.ident	"GCC: (Ubuntu 12.2.0-3ubuntu1) 12.2.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

沒有出現，圖例為對程式POW執行的結果。

測驗 2

參考作業發現 len 與 i 有關聯，但沒有進一步想到，一起合併，紀錄在 ans 並每次更新，以致於一時之間沒有發現。有些對2進位表示不習慣，我以為還要經過一個函數，有個固定語法的印象，一沒找到就認不出來，沒有想法了。也可說是對串接數字的方式沒有清楚的概念。
實驗共筆

測驗 3

解釋原理：
因為2進位補數 0b10111111 是負數，所以更大的數，數值較小，第六第七位會是後續位元組開頭的樣式。所以用-65當作 magic number 這個演算法可以算出是否為後續位元組。
參考範本
AAAA=3, BBBB=7, CCCC=7
新演算法把8個數字串在一起，當作一個數字運算，如同題目開頭2數字串接的例子一樣，範本中，使用題目的說法，利用位元運算的性質，反轉再經過 mask 讓其他六位數字歸零，再繼續整理，讓目標樣式輸出一，計算一的數量。 好解釋

測驗 4

參考列表

pattern: 0x8000 = 0b1000 0000 0000 0000
pattern: 0xc000 = 0b1100 0000 0000 0000
pattern: 0xe000 = 0b1110 0000 0000 0000
pattern: 0xf000 = 0b1111 0000 0000 0000
pattern: 0xf800 = 0b1111 1000 0000 0000
pattern: 0xfc00 = 0b1111 1100 0000 0000
pattern: 0xfe00 = 0b1111 1110 0000 0000
pattern: 0xff00 = 0b1111 1111 0000 0000
pattern: 0xff80 = 0b1111 1111 1000 0000
pattern: 0xffc0 = 0b1111 1111 1100 0000
pattern: 0xffe0 = 0b1111 1111 1110 0000
pattern: 0xfff0 = 0b1111 1111 1111 0000
pattern: 0xfff8 = 0b1111 1111 1111 1000
pattern: 0xfffc = 0b1111 1111 1111 1100
pattern: 0xfffe = 0b1111 1111 1111 1110
pattern: 0xffff = 0b1111 1111 1111 1111

同義解，

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x+1;
    return (n ^ x) < x;
}

改寫程式碼為 pattern 的生成器：

bool is_pattern(uint16_t x)
{
    int n = __builtin_popcountll(x ^ 0x8000llu);
	uint16_t gen = 0x8000llu;
	for (int i=0; i<n; i++)
		gen |= gen>>1;
	
	return gen;
}

考慮到
0x8000 =

$-2^{15}$ (mod

$2^{16}$)，每一行都是前一行右移1位元，也就是除以二，這裡要邏輯位移，補上 MSB digit =1，所以新程式碼告訴我們邏輯位移的實做，x |= x>>1，我想也是除以2的實做。
x^-x = x<<1 = x * 2 = x - (-x)