---
tags: linux2022
---

# Quiz 3
contributed by < `linchi1997yeh` >

## 測驗`1`: [GENMASK](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-1)

### 1. Code explaination

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

- `GENMASK(6, 4)` 產生 01110000
- `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)

`output = A & B`
from the code and example above we can be sure that:
* Since we are shifting unsigned numbers both right and left shifts will be padded with zeros [Shift Operators](https://linuxhint.com/shift-operators-in-c/)

* Where `A` is responsible for producing the left hand side mask, and `B` the right hand side.
* `A` have must create a leading zeros between highest-order-bit to h (not including h) => LEFT = `64 - (h-1)` = `(63 - h)`
* `B` is responsible for producing the right hand side mask. So it mush shift l times => RIGHT = `l`

LEFT = `(63 - h)`
RIGHT = `l`

:::info
The above code I think there is this redundant part where `B` is first shifted `l` times left first.
:::

### 2. Linux Kernel additional considerations

#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

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

In line `3-6` it checks whether `l` is greater than `h`, if so it returns `1` instead of the mask that we expected from the explaination above.
It also has a comment stating that `BUILD_BUG_ON_ZERO` is not available from asm files ([Assembly source code file created by Microsoft Visual Studio](https://fileinfo.com/extension/asm#:~:text=Assembly%20source%20code%20file%20created,small%20segments%20of%20application%20code.)), So `GENMASK_INPUT_CHECK` is redefined through lines `11-12` assuming that `h` is always greater than `l`.
### Usage of GENMASK
:::spoiler additional source code for reference

/*
* Built-in Function: int __builtin_ffs (int x)
* Returns one plus the index of the least significant 1-bit of x,
* or if x is zero, returns zero.
*/

#define __bf_shf(x) (__builtin_ffsll(x) - 1)
// __builtin_ffsll(x) => same as __builtin_ffs for long long

:::
In bitfield.h :

/*
* Example:
 *
 *  #define REG_FIELD_A  GENMASK(6, 0)
 *  #define REG_FIELD_B  BIT(7)
 *  #define REG_FIELD_C  GENMASK(15, 8)
 *  #define REG_FIELD_D  GENMASK(31, 16)
 *
 * Get:
 *  a = FIELD_GET(REG_FIELD_A, reg);
 *  b = FIELD_GET(REG_FIELD_B, reg);
 *
 * Set:
 *  reg = FIELD_PREP(REG_FIELD_A, 1) |
 *	  FIELD_PREP(REG_FIELD_B, 0) |
 *	  FIELD_PREP(REG_FIELD_C, c) |
 *	  FIELD_PREP(REG_FIELD_D, 0x40);
 *
 * Modify:
 *  reg &= ~REG_FIELD_C;
 *  reg |= FIELD_PREP(REG_FIELD_C, c);
 */

`GENMASK` is used to create a mask for accessing, setting, and modifying registers information.
- `REG_FIELD_A` would refer to the first 6 bits counting from the rigth hand side. Same case for `REG_FIELD_C` and `REG_FIELD_D`.
- `FIELD_GET` read the value from register from the specified mask.
- `FIELD_SET` set value of the register from the specified mask.
- `Modify` clears/prevail the masked bits from the register.

Source code reference:
[__builtin_ffs](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)

## 測驗`2`: [Align Down](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-2)

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

enum {
    FOO_DEFAULT = 0,
    FOO_ACTION,                           
    FOO_UNLOCK,
} FOO_FLAGS;

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

Refer to [jim12312321](https://hackmd.io/@jim12312321/linux2022-quiz3#%E6%B8%AC%E9%A9%97-2-%EF%BC%9A-%E8%A8%98%E6%86%B6%E9%AB%94%E5%90%91%E4%B8%8B%E5%B0%8D%E9%BD%8A) notes on data alignment
Since we need to align bits by multiples of 4, meaning the last 2 bits should be 0, we can achieve that using (v & ~3)
EXP1 = `(struct foo *)(v & ~3)`

## 測驗`3`: [Reverse Bit](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-3)

#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;
}

EXP2= `(x & 0x33) << 2`
EXP3= `(x & 0x55) << 1`

### answer

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

[Linux Kernel bitrev.h](https://elixir.bootlin.com/linux/latest/source/include/linux/bitrev.h#L15)
## 測驗`4`: [For Each](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-3)

#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__})))

EXP4 = `++_foreach_i`
EXP5 = `++_foreach_i`

## 測驗`5` [Divide Two Integers](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-5)

Possible answer to LeetCode [29.Divide Two Intergers](https://leetcode.com/problems/divide-two-integers/)

#include <limits.h>
int divide(int dividend, int divisor)
{
/* 
 * Turn sign division into unsign division
 */
    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;
    }

/* 
 * We should first align the most significant bit of 
 * the dividend and divisor to start binary division
 */
    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 = `dvs << shift`
EXP7 = `dvd -= (dvs<<shift)`