# linux2021: [e361](https://github.com/e361)

:::warning
注意細節!
:notes: jserv
:::

## 測驗 $\alpha$-1 舉出linux核心原始程式碼裡頭的案例並說明

>linux kernel裡的 <bitop.h> 定義的幾個circular shift macro,包含

static inline rol64(__u64 word, unsigned int shift)
static inline ror64(__u64 word, unsigned int shift)
static inline rol32(__u32 word, unsigned int shift)
static inline ror32(__u32 word, unsigned int shift)
static inline rol16(__u16 word, unsigned int shift)
ror16(...), rol8(...), ro8(...)

* 這些聚集根據操作的位元數不同,做出往右/往左的 circular shift
共同的操作為:
word >> (shift & x) | word << (-shift & x) [往左循環位移]
word << (shift & x) | word >> (-shift & x) [往右循環位移]
其中 x 是操作對象的位元數在少1

* shift 為主要位移的數量, 而 -shift 則是反方向需要補上去的
跟 x 做 AND bitwise operation 是為了消除符號
最後 OR bitwise operation 將個別部份連接起來
----------------------------------------------------------------------

## 測驗$\alpha$-2 x86-64具備rotr和rotl指令,上述C程式碼經過編譯器最佳化後,能否運用到這兩個指令？

C code

int main(void){
    int ch = 0b11010001;
    printf("%d\n", rotr8(ch, 2));
    printf("%d\n", rotl8(ch, 1));
    
    return 0;
}    

>使用gcc編譯的結果：
:::spoiler

$gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$gcc -S -o rotate.s rotate.c

節錄自rotate.s
rotl8:
.LFB2:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, %eax
	movl	%esi, -24(%rbp)
	movb	%al, -20(%rbp)
	movl	$7, -4(%rbp)
	movl	-4(%rbp), %eax
	andl	%eax, -24(%rbp)
	movzbl	-20(%rbp), %edx
	movl	-24(%rbp), %eax
	movl	%eax, %ecx
	sall	%cl, %edx
	movl	%edx, %eax
	movl	%eax, %esi
	movzbl	-20(%rbp), %edx
	movl	-24(%rbp), %eax
	negl	%eax
	andl	-4(%rbp), %eax
	movl	%eax, %ecx
	sarl	%cl, %edx
	movl	%edx, %eax
	orl	%esi, %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	rotl8, .-rotl8
	.type	rotr8, @function
rotr8:
.LFB3:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, %eax
	movl	%esi, -24(%rbp)
	movb	%al, -20(%rbp)
	movl	$7, -4(%rbp)
	movl	-4(%rbp), %eax
	andl	%eax, -24(%rbp)
	movzbl	-20(%rbp), %edx
	movl	-24(%rbp), %eax
	movl	%eax, %ecx
	sarl	%cl, %edx
	movl	%edx, %eax
	movl	%eax, %esi
	movzbl	-20(%rbp), %edx
	movl	-24(%rbp), %eax
	negl	%eax
	andl	-4(%rbp), %eax
	movl	%eax, %ecx
	sall	%cl, %edx
	movl	%edx, %eax
	orl	%esi, %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret

:::
* 根據編譯完的結果,編譯器把需要位移的bytes數做位置偏移,並沒有利用到 ROR,ROL
而是利用SAR,SAL 算術位移運算來達到等同的效果
----------------------------------------------------------
## 測驗$\beta$-1 說明上述程式碼的原理

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
    uintptr_t mask = alignment - 1;
    if ((alignment & mask) == 0) {  /* power of two? */
        return (sz + mask) & ~mask;       
    }
    return (((sz + mask) / alignment) * alignment);
}

* 分為兩階段討論,上述程式碼alignment非2^次方時,其實是在做ceiling的動作,
* (sz + mask) / alignment == $\lceil$sz / alignment$\rceil$
* 在alignment是2^次方部份, &~mask指的是說對所需的總對齊數求商,因為mask是alignemnt的餘數,而(sz+mask)指的是說原本有沒有剩餘無法被alignment整除的部份,如果有得補回去

:::warning
power of 2 的翻譯是「2 的冪」
:notes: jserv
:::

---

## 測驗$\beta$-2 Linux kernel 的 align-up alike macro?

* some linux kernel align macro

#define ALIGN(x, a) __ALIGN_MASK(x, (typeof(x))(a)-1)
#define __ALIGN_MASK(x, mask) (((x) + (mask))&~(mask))

* eg. ALIGN(16, 4) ---> 16
* 更具通用性
* 有保護的功能???