2022q1 Homework3 (quiz3)

contributed by < jim12312321 >

測驗題目

測驗 1 ：連續的 bitmask

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

解析︰
先觀察程式碼，~0UL 等於 0xFFFFFFFFFFFFFFFF ，有出現 shift ，中間用 AND 相連，因此我們可以合理猜測本題中應該是想透過將 ~0UL 經過特定的 shift 後再透過 AND 將不在 [h,l] 中的 1 消除。

e.g.
要產生 GENMASK(6,4) ，要先產生 0x000000000000007F （~0UL 右移 57 個 bits）和 0xFFFFFFFFFFFFFFF0 （~0UL 左移 4 個 bits），再藉由 AND 產生 0x0000000000000070 。

由上述例子進行延伸討論，我們可以知道若要透過 ~0UL 產生 0x000000000000007F 需要右移，反之要產生 0xFFFFFFFFFFFFFFF0 則需要左移。
再與程式碼比較後可知，(~0UL) >> (LEFT) 僅有右移，(~0UL) >> (l) << (RIGHT) 包含左移操作。因此可知若對應上述例子，(~0UL) >> (LEFT) 目的在於產生 0x000000000000007F ，(~0UL) >> (l) << (RIGHT) 目的在於產生 0xFFFFFFFFFFFFFFF0 ，不過由於在 (~0UL) >> (l) << (RIGHT) 中還含有右移行為，因此產生出來的 bitmask 應該為 0x0FFFFFFFFFFFFFF0 。

最後可以發現右移操作中的 57 來自於 64-1-h ，而左移操作中的 4 來自於 l。

LEFT

\to

63 - h

RIGHT

\to

延伸問題 2

比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量

在 linux kernel v5.16.12 中的 isst.h 中可以發現 GENMASK 的程式碼

#define GENMASK(h, l) (((~0UL) << (l)) & (~0UL >> (sizeof(long) * 8 - 1 - (h))))

在這段程式碼中可以發現與本題中的 GENMASK 幾乎一致，僅差在 (~0UL) << (l) 的操作中沒有先左移 l ，但這對於答案是沒有差別的。

另外在 linux kernel v5.16.12 中的 bits.h 中也可以發現 GENMASK 的程式碼。

#define GENMASK(h, l) \
	(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))

接著我們分別來看 GENMASK_INPUT_CHECK(h, l) 和 __GENMASK(h, l)

GENMASK_INPUT_CHECK

#if !defined(__ASSEMBLY__)
#include <linux/build_bug.h>
#define GENMASK_INPUT_CHECK(h, l) \
	(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
		__is_constexpr((l) > (h)), (l) > (h), 0)))
#else
/*
 * BUILD_BUG_ON_ZERO is not available in h files included from asm files,
 * disable the input check if that is the case.
 */
#define GENMASK_INPUT_CHECK(h, l) 0
#endif

搭配 BUILD_BUG_ON_ZERO 的說明

#ifdef __CHECKER__
#define BUILD_BUG_ON_ZERO(e) (0)
#else /* __CHECKER__ */
/*
 * Force a compilation error if condition is true, but also produce a
 * result (of value 0 and type int), so the expression can be used
 * e.g. in a structure initializer (or where-ever else comma expressions
 * aren't permitted).
 */
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
#endif /* __CHECKER__ */

我們可知在 BUILD_BUG_ON_ZERO（e）中當 e 這個情況為 0 時沒事，而不為 0 時（condition is true），印出錯誤訊息。

接著來看 __builtin_choose_expr 的說明

Built-in Function: type __builtin_choose_expr (const_exp, exp1, exp2)

You can use the built-in function __builtin_choose_expr to evaluate code depending on the value of a constant expression. This built-in function returns exp1 if const_exp, which is an integer constant expression, is nonzero. Otherwise it returns exp2.

再來看 __is_constexpr 的說明

/*
 * This returns a constant expression while determining if an argument is
 * a constant expression, most importantly without evaluating the argument.
 * Glory to Martin Uecker <Martin.Uecker@med.uni-goettingen.de>
 */
#define __is_constexpr(x) \
	(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))

最後透過整理上述三個資訊可知，GENMASK_INPUT_CHECK(h, l) 的目的在於確認 h > l ，若是輸出 0；若否（h <= l），則印出錯誤訊息。

__GENMASK

#define __GENMASK(h, l) \
	(((~UL(0)) - (UL(1) << (l)) + 1) & \
	 (~UL(0) >> (BITS_PER_LONG - 1 - (h))))

我們一樣來舉個例子說明（不舉例給自己看我真的腦袋卡住）

e.g.
要產生 GENMASK(6,4) ，要先產生 0x000000000000007F （~0UL 右移 57 個 bits）和 0xFFFFFFFFFFFFFFF0 （~0UL 左移 4 個 bits），再藉由 AND 產生 0x0000000000000070 。

這跟上面舉的例子是完全相同的，而觀察程式碼可以發現， ~UL(0) >> (BITS_PER_LONG - 1 - (h)) 的作用等同 (~0UL) >> (63 - h) ，一樣是為了左移 4 個 bits 產生 0x000000000000007F 。

接著來看 (((~UL(0)) - (UL(1) << (l)) + 1) 想做什麼。

(~UL(0)) 產生 0xFFFFFFFFFFFFFFFF
(~UL(0)) - (UL(1) << (l)) 產生 0xFFFFFFFFFFFFFFEF
((~UL(0)) - (UL(1) << (l)) + 1) 產生 0xFFFFFFFFFFFFFFF0

ya！結果和 ((~0UL) << (l)) 是等價的！只是這裡的想法是先目標位置（l）的 bit 設為 0 ，再透過 +1 產生我們想要的 bitmask 。（雖然我覺得想法上沒有 ((~0UL) << (l)) 來的簡潔和直覺就是了）。

總結來說在 linux kernel 中的 GENMASK 並沒有什麼很特別的技術，僅是在 linux kernel v5.16.12 理的 bits.h 中的 GENMASK 多了要求 h 恆大於 l 的限制罷了。

延伸問題 3

舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

在 linux 中有不少 GENMASK 巨集和 include/linux/bitfield.h 的應用案例（請看這裡）。大部分跟裝置驅動程式或是網路挺有關係的，礙於能力有限，我會盡量理解後留下心得。

device driver 請稱呼全名「裝置驅動程式」，不要簡稱「驅動」，不然日後涉及到編譯器和資料庫，都有對應的 compiler driver 和 database driver，必然會混淆。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

應用案例 1

本段程式碼可以在 linux/sound/soc/intel/keembay/kmb_platform.h 的第 64 到 66 行中找到。




/*line 64 to 66*/
/* Interrupt Flag */
#define TX_INT_FLAG		GENMASK(5, 4)
#define RX_INT_FLAG		GENMASK(1, 0)

可以猜測這是用來設立 flag 用以判斷該發送數據或是接收數據。

參考：What do ‘TX’ and ‘RX’ refer to in the Network Charts?

接著繼續追蹤 TX_INT_FLAG 和 RX_INT_FLAG

static inline void kmb_i2s_irq_trigger(struct kmb_i2s_info *kmb_i2s,
				       u32 stream, int chan_nr, bool trigger)
{
	u32 i, irq;
	u32 flag;

	if (stream == SNDRV_PCM_STREAM_PLAYBACK)
		flag = TX_INT_FLAG;
	else
		flag = RX_INT_FLAG;

	for (i = 0; i < chan_nr / 2; i++) {
		irq = readl(kmb_i2s->i2s_base + IMR(i));

		if (trigger)
			irq = irq & ~flag;
		else
			irq = irq | flag;

		writel(irq, kmb_i2s->i2s_base + IMR(i));
	}
}

可發現當 stream 狀態為播放時，將 flag 設定為傳輸模式；否則將 flag 設定為接收模式。

應用案例2

本段程式碼可以在 linux/net/dsa/tag_ar9331.c 的第 13 到 15 行中找到。



#define AR9331_HDR_VERSION		1

#define AR9331_HDR_VERSION_MASK		GENMASK(15, 14)

接著追蹤 AR9331_HDR_VERSION_MASK ，可以在同一個檔案中的第 36 行找到他。(下面程式碼中的第 10 行)


















static struct sk_buff *ar9331_tag_xmit(struct sk_buff *skb,
				       struct net_device *dev)
{
	struct dsa_port *dp = dsa_slave_to_port(dev);
	__le16 *phdr;
	u16 hdr;

	phdr = skb_push(skb, AR9331_HDR_LEN);

	hdr = FIELD_PREP(AR9331_HDR_VERSION_MASK, AR9331_HDR_VERSION);
	hdr |= AR9331_HDR_FROM_CPU | dp->index;
	/* 0b10 for AR8216 and 0b11 for AR9331 */
	hdr |= AR9331_HDR_RESERVED_MASK;

	phdr[0] = cpu_to_le16(hdr);

	return skb;
}

再來看看 FIELD_PREP 的說明。

/**
 * FIELD_PREP() - prepare a bitfield element
 * @_mask: shifted mask defining the field's length and position
 * @_val:  value to put in the field
 *
 * FIELD_PREP() masks and shifts up the value.  The result should
 * be combined with other fields of the bitfield using logical OR.
 */
#define FIELD_PREP(_mask, _val)						\
	({								\
		__BF_FIELD_CHECK(_mask, 0ULL, _val, "FIELD_PREP: ");	\
		((typeof(_mask))(_val) << __bf_shf(_mask)) & (_mask);	\
	})

結合上述的內容我們可以推斷在 linux/net/dsa/tag_ar9331.c 中的 GENMASK 目的是為了結合 FIELD_PREP 將特定的值左移到特定位置。

測驗 2 ：記憶體向下對齊

在進入程式碼解析之前，先來複習什麼是記憶體向上對齊和向下對齊，在⟨你所不知道的 C 語言：記憶體管理、對齊及硬體特性⟩ 中的 data alignment 中有提到，記憶體對齊就是讓記憶體內的資料落在 4 個 bytes 或是 8 個 btyes 的倍數位置(當然也可以根據需求設置對齊任意位置) ，方便 cpu 抓取資料。

以下例子皆以對齊 4 個 bytes 為例。

向上對齊
- 將記憶體內的資料對齊到 4 bytes + 1 bytes 的位置上。
  對應到記憶體定址中，就是最後 2 個 bits clear ，並對第 3 個 bit + 1 。

address (after align up) :
$0001_{2}$
address (before align up) :
$0100_{2}$

向下對齊
- 將記憶體內的資料對齊到 4 bytes 的位置上。
  對應到記憶體定址中，就是最後 2 個 bits clear。

address (after align up) :
$0001_{2}$
address (before align up) :
$0000_{2}$

看完說明之後就可以來解析程式碼了。









struct fd {
    struct foo *foo;
    unsigned int flags;
};

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

由於本題要將結構體中第一個成員的地址向下對齊 4 個 bytes ，又因為 forward declaration 的關係，所以在這個回傳式中要加入對 (struct foo *) 的操作。

EXP1

\to

(struct foo *)(v & ~3)

延伸問題 2

在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

在 linux/include/uapi/linux/const.h 中可以找到對齊相關的程式碼

以下程式碼節錄自 const.h 第 31,32 行


#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))

__ALIGN_KERNEL_MASK
針對特定的 bitmask (e.g.
$15_{10} = 1111_{2}$ ) 進行向上對齊
__ALIGN_KERNEL
在 __ALIGN_KERNEL_MASK 的基礎上，對特定長度的數字(通常是
$2^{n}, n \in N$ ) 進行向上對齊

接著在 linux/include/linux/align.h 中可以找到向上對齊/向下對齊的程式碼。

以下程式碼節錄自 align.h 第 7 至 9 行



/* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)	__ALIGN_KERNEL((x) - ((a) - 1), (a))

ALIGN
本來在 __ALIGN_KERNEL 中就是向上對齊了，所以他就是向上對齊。
ALIGN_DOWN
在要對齊的地址中先 - ((a) - 1) ，達到把 a - 1以下的位元全部 clear 並且不 +1 ，完成向下對齊。

測驗 3 ︰ reverse bits








#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | (EXP2);
    x = ((x & 0xAA) >> 1) | (EXP3);
    return x;
}

觀察程式碼行為可以得知，這段程式碼正在逐步將位元交換，一開始先交換前 4 個 bits 和後 4 個 bits，接著將交換完的 4 個 bits 內的 bits 兩兩互換，最後在將兩個 bits 互換。（有點 mergesort 的感覺）

origin

reverse (4 bits)

x = (x >> 4) | (x << 4);

reverse (2 bits)

x = ((x & 0xCC) >> 2) | (EXP2);

reverse (1 bit)

x = ((x & 0xAA) >> 1) | (EXP3);

EXP2

\to

(x & 0x33) << 2

EXP3

\to

(x & 0x55) << 1

延伸問題 2

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

在 linux/lib/bitrev.c 中可以發現由於反轉 8 bits 僅有 256 種可能，因此開發者直接把 8 bits 反轉的查詢表內建在裡面了。

節錄自 bitrev.c 中第 11 至 44 行


































const u8 byte_rev_table[256] = {
	0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
	0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
	0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
	0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
	0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
	0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
	0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
	0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
	0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
	0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
	0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
	0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
	0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
	0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
	0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
	0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
	0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
	0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
	0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
	0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
	0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
	0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
	0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
	0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
	0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
	0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
	0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
	0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
	0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
	0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
	0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
	0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
};

而在 linux/include/linux/bitrev.h 中則可以看到基於 byte_rev_table 延伸出來的 16 位元、 32 位元版本。














static inline u8 __bitrev8(u8 byte)
{
	return byte_rev_table[byte];
}

static inline u16 __bitrev16(u16 x)
{
	return (__bitrev8(x & 0xff) << 8) | __bitrev8(x >> 8);
}

static inline u32 __bitrev32(u32 x)
{
	return (__bitrev16(x & 0xffff) << 16) | __bitrev16(x >> 16);
}

另外在 bitrev.h 中有提供用於 reverse 編譯時常數的版本，作法就根本題是幾乎一模一樣了。








#define __constant_bitrev8(x)	\
({					\
	u8 ___x = x;			\
	___x = (___x >> 4) | (___x << 4);	\
	___x = ((___x & (u8)0xCCU) >> 2) | ((___x & (u8)0x33U) << 2);	\
	___x = ((___x & (u8)0xAAU) >> 1) | ((___x & (u8)0x55U) << 1);	\
	___x;								\
})

因此在 linux 中真正在使用 bit reverse 時也是要先考慮輸入值是否為編譯時常數。







#define bitrev8(x) \
({			\
	u8 __x = x;	\
	__builtin_constant_p(__x) ?	\
	__constant_bitrev8(__x) :			\
	__bitrev8(__x)	;			\
 })

應用情境

在很多裝置驅動程式相關的程式碼中都能看到 bit reverse 的身影，以下程式碼雖不能完整解釋，就當放上來作為實際應用情境參考。

在 linux/drivers/media/usb/cx231xx/cx231xx-input.c 的 get_key_isdbt 函式中可以看到以下程式碼。



scancode = bitrev8(cmd);

dev_dbg(&ir->rc->dev, "cmd %02x, scan = %02x\n", cmd, scancode);

又或者在 linux/drivers/media/rc/img-ir/img-ir-nec.c 中的 img_ir_nec_scancode 函式可以看到解析 raw code to scan code 時用到 bitrev8 。




request->scancode = bitrev8(addr)     << 24 |
		bitrev8(addr_inv) << 16 |
		bitrev8(data)     <<  8 |
		bitrev8(data_inv);

測驗 4 ： foreach macro

foreach 的概念很簡單，就是依序提取出特定 array 內的所有資料。

先來看程式碼。
















#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
    assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))

#define foreach_int(i, ...)                                            \
    for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
         _foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int);      \
         (i) = ((int[]){__VA_ARGS__, 0})[EXP4])

#define foreach_ptr(i, ...)                                                 \
    for (unsigned _foreach_i =                                              \
             (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
         (i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__,            \
                                                    NULL})[EXP5],   \
                  _foreach_no_nullval(_foreach_i, i,                        \
                                      ((const void *[]){__VA_ARGS__})))

無論是 foreach_int 或 foreach_ptr 目標都是為了走訪 array 中所有資料，對應到 c 中 for 的虛擬碼就會是：



for(take the first element and get first index;
   assert(index < MAX_LEN_ARRAY);
   update the element and index)

為求精簡，題目中在一行內就要更新 element (題目中的 i) 與 index (題目中的 _foreach_i) 因此使用 ++Variable 的技巧。

EXP4

\to

++_foreach_i

EXP5

\to

++_foreach_i

延伸問題 2

在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

在 drivers/net/ethernet/mellanox/mlxfw/mlxfw_mfa2_tlv_multi.h 中可以找到類似的實作技巧。



#define mlxfw_mfa2_tlv_foreach(mfa2_file, tlv, idx, from_tlv, count) \
	for (idx = 0, tlv = from_tlv; idx < (count); \
	     idx++, tlv = mlxfw_mfa2_tlv_next(mfa2_file, tlv))

這邊的作法跟 list.h 中的 list_for_each 之類的實作挺類似的，就不特別解說。

這類型的技巧可以用來檢查特定變數/結構體有沒有符合特定條件。在同個目錄中的 mlxfw_mfa2.c 可以看到應用的場景。












/* check that all the devices exist */
mlxfw_mfa2_tlv_foreach(mfa2_file, tlv, idx, mfa2_file->first_dev,
               mfa2_file->dev_count) {
    if (!tlv) {
        pr_err("Device TLV error\n");
        return false;
    }

    /* Check each device */
    if (!mlxfw_mfa2_file_dev_validate(mfa2_file, tlv, idx))
        return false;
}

測驗 5 ： LeetCode 29. Divide Two Integers
































#include <limits.h>
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    while (dvd > (EXP6))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            shift--;                         
        res |= (unsigned int) 1 << shift;
        EXP7;
    }

    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    return res * signal;
}

EXP6

\to

dvs << shift

EXP7

\to

dvd -= dvs << shift

測驗 6 ： LeetCode 149. Max Points on a Line

本題程式的目的在於將可連成一條線的點（

\frac{y}{x}

相同者，在本題中 x 與 y 都有先除以 gcd(x,y) ，以確保 hash 值相同），存在 hash table 同個 hash 值的 linked list 中。







static bool can_insert(struct list_head *head, int p1, int p2)
{
    struct point_node *pn;
    list_for_each_entry (pn, head, link)
        return EXP8;
    return true;
}

所以 EXP8 的目的在於判斷傳進來的 (p1,p2) 與原先 list 中的 (p1,p2) 是否一致。
EXP8

\to

p1 == pn->p1 or p2 == pn->p2






if (can_insert(&heads[hash], i, j)) {
    struct point_node *pn = malloc(sizeof(*pn));
    pn->p1 = i;
    pn->p2 = j;
    EXP9;
}

而 EXP9 的目的就在於將新的節點放進 heads 中對應 hash 的位置。
EXP9

\to

list_add(&pn->link, &heads[hash])

測驗 7 ： ilog32

考慮題目一開始的要求

針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存

相當於對特定的數字進行

l o g_{2}

的操作再取 floor 。因此這題便是對前述概念的實作。


















int ilog32(uint32_t v)
{
    int ret = v > 0;
    int m = (v > 0xFFFFU) << 4;
    v >>= m;
    ret |= m;
    m = (v > 0xFFU) << 3;
    v >>= m;
    ret |= m;
    m = (v > 0xFU) << 2;
    v >>= m;
    ret |= m;
    m = EXP10;
    v >>= m;
    ret |= m;
    EXP11;
    return ret;
}

觀察題目後可以發現有類似的模組重複發生，如下所示。



m = (v > 0xFFU) << 3;
v >>= m;
ret |= m;

每次對半檢查，判斷對半後較高位的那組中是否有值。若有則記錄判斷了幾個 bits ，反覆檢查直至全部檢查過。
到 EXP10 之前的程式碼檢查到 4 個 bits ，因此可知 EXP10 要檢查剩下未確定的 4 個 bits 中，較高位的 2 個 bits 是否為 0。

EXP10

\to

(v > 0x3) << 1

理論上還要再進行一次針對剩下 2 個 bits 的操作， ret 的結果才會是最終答案，如下所示。



m = (v > 0x1);
v >>= m;
ret |= m;

題目中顯然是希望最後這三道指令能濃縮成一道，首先 v >>= m ，與最後回傳值無關，不理他。剩下 m = (v > 0x1) 跟 ret |= m 。不過由於最初就是考慮到每次位移的 bits 都不會重複，因此在這個情況下 |= 等價於 += 。
EXP11

\to

ret |= v > 1 or ret += v > 1

測驗 8 ： binary tree

以下解說只挑有填空的位置講解。






while (*p != 0 && (*p)->data != d) {
    if (d < (*p)->data)
        EXP12;
    else
        EXP13;
}

根據二元搜尋樹的特性，若在當前節點無法匹配到指定值且當前節點不為葉節點，匹配值較當前值大則向右搜尋，反之向左。
EXP12

\to

p = &(*p)->left
EXP13

\to

p = &(*p)->right






tnode **r = &q->right;
while ((*r)->left)
    r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;

這段在處理欲移除節點擁有同時擁有左右子樹的情況，此時應拿全部小於該數值中最接近該數值的值取代(左子樹中最右邊的值)，或全部大於該數值中最接近該數值的值取代(右子樹中最左邊的值)，而在本題中使用的是後者。
EXP14

\to

&(*r)->left

測驗 9 ： round up alignment

上面有解釋過何謂向上對齊，這邊簡單複習。

以下例子皆以對齊 4 個 bytes 為例。

向上對齊
- 將記憶體內的資料對齊到 4 bytes + 1 bytes 的位置上。
  對應到記憶體定址中，就是最後 2 個 bits clear ，並對第 3 個 bit + 1 。

address (after align up) :
$0001_{2}$
address (before align up) :
$0100_{2}$

接著來看程式碼。







/* maximum alignment needed for any type on this platform, rounded up to a
   power of two */
#define MAX_ALIGNMENT 16

/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - MMM) & ~(NNN))

因此本題希望將 x 向上對齊到 4 的倍數的位置上 (e.g.

0000 0010_{2} \to 00001 0000_{2}

) ，並且將最低 4 個 bits 清空。
MMM

\to

1
NNN

\to

MAX_ALIGNMENT - 1

測驗 10 ： DIVIDE_ROUND_CLOSEST









#define DIVIDE_ROUND_CLOSEST(x, divisor)                       \
    ({                                                         \
        typeof(x) __x = x;                                     \
        typeof(divisor) __d = divisor;                         \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
         (((__x) > 0) == ((__d) > 0)))                         \
            ? ((RRR) / (__d))                  \
            : ((SSS) / (__d));                 \
    })

用來進行判斷進入 ((RRR) / (__d)) 或 ((SSS) / (__d)) 的三個條件，主要目的便是拿來判別運算結果有沒有可能為負，若不可能就進 ((RRR) / (__d)) 否則進 ((SSS) / (__d)) 。
三個條件中須注意的是 ((typeof(x)) -1) 這是用以將 -1 cast 成 typeof(x) ，假設 x 的 type 為 int ，則 ((typeof(x)) -1) > 0 不成立，若 x 的 type 為 unsigned int ，則 ((typeof(x)) -1) > 0 成立(之所以要檢查是否為 unsigned ，是因為跟 unsigned 運算的 signed 數值也會變 unsigned ，因此恆大於等於 0)。

考慮到在 c 中除法會無條件捨去，因此對於除完後餘數大於等於 0.5 的數值要補齊這一半，利用加上這一半的值讓他進位；而對於小於 0.5 的情況，有沒有補都不會造成進位，因此補上去也沒關係。而在負數的除法中情況相反，對於除完後餘數大於等於 0.5 的數值要補齊這一半，利用減去這一半的值讓他進位。

RRR

\to

(__x) + ((__d) >> 1)
SSS

\to

(__x) - ((__d) >> 1)

測驗 11 ： floor sqrt

fls(x) 的目的在於找出最高位的 set bit 的位置。

fls(1) == 0, fls(2) == 1, fls(0x8000 0000 0000 0000) == 63





















unsigned long i_sqrt(unsigned long x)
{
    unsigned long b, m, y = 0;

    if (x <= 1)
        return x;

    m = 1UL << (fls(x) & ~1UL);
    while (m) {
        b = y + m;
        XXX;

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }

    return y;
}

一直卡住沒什麼想法，在參考 kdnvt 同學的解釋之後有了一點頭緒。

用 2 進位的邏輯

N^{2}

可以被表示為

(a_{n} + . . . + a_{0})^{2}

，其中

a_{m}

(

0 \leq m \leq n

) 表示

2^{m}

或 0 ，因此我們可以從

a_{n}

找回

a_{0}

並把結果記錄下來

P_{m} = a_{n} + . . . + a_{0}

。
為了決定

P_{m}

中的

a_{m}

屬於

a^{m}

或 0 ，利用以下規則︰

If
$P_{m}^{2} \leq N^{2}$ ,
$P_{m + 1} = P_{m} - 2^{m}$
Else,
$P_{m + 1} = P_{m}$

對應的程式碼




if (x >= b) {
    YYY;
    y += m;
}

並且為了每次都去計算

P_{m}^{2}

，在每一次計算的時候，我們僅紀錄

X_{m} = N^{2} - P_{m}^{2}

，並用

X_{m + 1} = X_{m} + Y_{m}

的方式更新

X_{m}

。（其中

Y_{m} = P_{m}^{2} - P_{m + 1}^{2} = 2 P_{m + 1} a_{m} + a_{m}^{2}

）
接著要從最大的 n 開始往下找，也就是 m = 1UL << (fls(x) & ~1UL) 這行的作用，並令

P_{n} = a_{n}

。然後我們用兩個新變數

c_{m}

和

d_{m}

分別儲存

Y_{m}

中的兩個部份。

$c_{m} = P_{m + 1} 2^{m + 1}$ （本題的 y）

$d_{m} = (2^{m})^{2}$ (本題的 m）

最後

c_{m}

和

d_{m}

會利用以下方式更新。

$c_{m - 1} = P_{m} 2^{m} = P_{m + 1} 2^{m} + a_{m} 2^{m}$ .
If
$a_{m} = 2^{m}$ ,
$c_{m - 1} = \frac{c_{m}}{2} + d_{m}$ . Else
$c_{m - 1} = \frac{c_{m}}{2}$

$d_{m - 1} = \frac{d_{m}}{4}$

XXX

\to

y >>= 1
YYY

\to

x -= b
ZZZ

\to

m >>= 2

2022q1 Homework3 (quiz3)

測驗 1 ： 連續的 bitmask

延伸問題 2

延伸問題 3

應用案例 1

應用案例2

測驗 2 ： 記憶體向下對齊

延伸問題 2

測驗 3 ︰ reverse bits

延伸問題 2

應用情境

測驗 4 ： foreach macro

延伸問題 2

測驗 5 ： LeetCode 29. Divide Two Integers

測驗 6 ： LeetCode 149. Max Points on a Line

測驗 7 ： ilog32

測驗 8 ： binary tree

測驗 9 ： round up alignment

測驗 10 ： DIVIDE_ROUND_CLOSEST

測驗 11 ： floor sqrt

測驗 1 ：連續的 bitmask

測驗 2 ：記憶體向下對齊