2021q1 Homework6 (quiz6)

contributed by < linD026 >

tags: `linux2021`

2021 年第 6 週隨堂測驗題目

0 進度

測驗 1

解釋程式碼以及改進

struct bn

/* how large the underlying array size should be */
#define UNIT_SIZE 4

/* These are dedicated to UNIT_SIZE == 4 */
#define UTYPE uint32_t
#define UTYPE_TMP uint64_t
#define MAX_VAL ((UTYPE_TMP)0xFFFFFFFF)

#define BN_ARRAY_SIZE (128 / UNIT_SIZE) /* size of big-numbers in bytes */

/* bn consists of array of TYPE */
struct bn {
  UTYPE array[BN_ARRAY_SIZE];
};

FORMAT_STRING

Linux Programmer's Manual - printf(3)
The unsigned int argument is converted to unsigned octal (o), unsigned decimal (u), or unsigned hexadecimal (x and X) notation.
```
#define FORMAT_STRING "%.08x"
```
會在 bn_to_str 函式 UTPYE 轉換至 char 實用到：
```
...
sprintf(&str[i], FORMAT_STRING, n->array[j]);
...
```

bn_from_int
把 UTYPE_TMP 型態的 i 儲存進 struct bn 。
其中原程式碼對於儲存位置是假定為 little-endian ，亦即 n->array[0] = i; 等操作。
然而電腦也有可能為 big-endian ，因此我在儲存前先做了處理。

static inline void bn_from_int(struct bn *n, UTYPE_TMP i) {
  bn_init(n);

  /* FIXME: what if machine is not little-endian? */
  const union {
    uint16_t set;
    char get[2];
  } _type = {.set = 0x1122};
  int start = 0;
  int next = 1;
  if (_type.get[0] == 0x11) {
    start = BN_ARRAY_SIZE - 1;
    next = start - 1;
  }
  n->array[start] = i;

  /* bit-shift with U64 operands to force 64-bit results */
  UTYPE_TMP tmp = i >> 32;
  n->array[next] = tmp;
}

所謂的 big endian 是指資料儲存於記憶體的方向與記憶體位址不同。也就是說資料的最高位元組是放置在低記憶體位址。

而 little endian 則是兩者方向相同。

Big-Endian 與 Little-Endian 的差異與判斷程式碼

至於 array[0] 為何就會是低記憶體位址？
規格書有定義到：

6.5.8 Relational operators
5 If the objects pointed to are members of the same aggregate object, pointers to structure members declared later compare greater than pointers to members declared earlier in the structure, and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values.

而關於實作部份，則會涉及 Memory Address Decoding 。

void bn_to_str(struct bn *n, char *str, int nbytes) {
    /* index into array - reading "MSB" first -> big-endian */
    int j = BN_ARRAY_SIZE - 1;
    int i = 0; /* index into string representation */

    /* reading last array-element "MSB" first -> big endian */
    while ((j >= 0) && (nbytes > (i + 1))) {
        sprintf(&str[i], FORMAT_STRING, n->array[j]);
        i += (2 *
              UNIT_SIZE); /* step UNIT_SIZE hex-byte(s) forward in the string */
        j -= 1;           /* step one element back in the array */
    }

    /* Count leading zeros: */
    for (j = 0; str[j] == '0'; j++)
        ;

    /* Move string j places ahead, effectively skipping leading zeros */
    for (i = 0; i < (nbytes - j); ++i)
        str[i] = str[i + j];

    str[i] = 0;
}

/* Decrement: subtract 1 from n */
void bn_dec(struct bn *n) {
    for (int i = 0; i < BN_ARRAY_SIZE; ++i) {
        UTYPE tmp = n->array[i];
        UTYPE res = tmp - 1;
        n->array[i] = res;

        // COND;
        if (!(res > tmp)) break;
    }
}

void bn_add(struct bn *a, struct bn *b, struct bn *c) {
    int carry = 0;
    for (int i = 0; i < BN_ARRAY_SIZE; ++i) {
        UTYPE_TMP tmp = (UTYPE_TMP) a->array[i] + b->array[i] + carry;
        carry = (tmp > MAX_VAL);
        c->array[i] = (tmp & MAX_VAL);
    }
}

void bn_mul(struct bn *a, struct bn *b, struct bn *c) {
    struct bn row, tmp;
    bn_init(c);

    for (int i = 0; i < BN_ARRAY_SIZE; ++i) {
        bn_init(&row);

        for (int j = 0; j < BN_ARRAY_SIZE; ++j) {
            if (i + j < BN_ARRAY_SIZE) {
                bn_init(&tmp);
                // III;
                UTYPE_TMP intermediate = a->array[i] * (UTYPE_TMP) b->array[j];
                bn_from_int(&tmp, intermediate);
                lshift_unit(&tmp, i + j);
                bn_add(&tmp, &row, &row);
            }
        }
        bn_add(c, &row, c);
    }
}

bool bn_is_zero(struct bn *n) {
    for (int i = 0; i < BN_ARRAY_SIZE; ++i)
        if (n->array[i])
            return false;
    return true;
}

/* Copy src into dst. i.e. dst := src */
void bn_assign(struct bn *dst, struct bn *src) {
    for (int i = 0; i < BN_ARRAY_SIZE; ++i)
        dst->array[i] = src->array[i];
}

階乘運算十進位輸出改進

#define NORMAL_SIZE(array, size)                                               \
  do {                                                                         \
    for (int _i = 0; _i < BN_ARRAY_SIZE; _i++) {                               \
      if (!array[_i]) {                                                        \
        size = _i - 1;                                                         \
        break;                                                                 \
      }                                                                        \
    }                                                                          \
  } while (0)

#define digit_div(n1, n0, d, q, r)                                             \
  __asm__("divq %4" : "=a"(q), "=d"(r) : "0"(n0), "1"(n1), "rm"(d))

#define SWAP(A, B)                                                             \
  do {                                                                         \
    typeof(A) tmp = A;                                                         \
    A = B;                                                                     \
    B = tmp;                                                                   \
  } while (0)

static UTYPE ddivi(struct bn *n, size_t size) {
  size_t tsize = size;
  UTYPE s1 = 0;
  do {
    UTYPE q, r;
    if (s1 == 0) {
      UTYPE s0 = n->array[tsize];
      q = s0 / 10;
      r = s0 % 10;
    } else {
      UTYPE_TMP s0 = s1;
      s0 = s0 << 32;
      s0 += n->array[tsize];
      q = s0 / 10;
      r = s0 % 10;
    }
    n->array[tsize] = q;
    s1 = r;
    tsize--;
  } while (tsize != -1);
  return s1;
}

static const char radix_chars[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
void bn_2_str(struct bn *n, char *out) {
  size_t size = 0;
  char *const head_out = out;
  NORMAL_SIZE(n->array, size);
  struct bn _n = *n;
  do {
    // extract
    UTYPE s1 = ddivi(&_n, size);
    *out++ = radix_chars[s1];
  } while(!bn_is_zero(&_n));

  char *f = out - 1;
  /* Eliminate leading (trailing) zeroes */
  while (*f == '0')
    --f;
  /* NULL terminate */
  f[1] = '\0';
  /* Reverse digits */
  for (char *s = head_out; s < f; ++s, --f)
    SWAP(*s, *f);
  out = head_out;
}

2021q1 Homework6 (quiz6)

tags: `linux2021`

0 進度

測驗 1

解釋程式碼以及改進

階乘運算十進位輸出改進

Karatsuba algorithm 和 Schönhage–Strassen algorithm

Linux kernel 中的大數運算

測驗 2

解釋程式碼

研讀 Linux 核心原始程式碼

測驗 3

解釋程式碼以及改進

interleaving 問題

研讀 A (Bare-Bones) User-Level Thread Library 以及實驗

2021q1 Homework6 (quiz6)

tags: linux2021

0 進度

測驗 1

解釋程式碼以及改進

階乘運算十進位輸出改進

Karatsuba algorithm 和 Schönhage–Strassen algorithm

Linux kernel 中的大數運算

測驗 2

解釋程式碼

研讀 Linux 核心原始程式碼

測驗 3

解釋程式碼以及改進

interleaving 問題

研讀 A (Bare-Bones) User-Level Thread Library 以及實驗

Read more

[Linux 核心 Copy On Write 實作機制](https://hackmd.io/@linD026/Linux-kernel-COW-content)

Linux 核心採納 Rust 的狀況

Linux 核心 Read-Copy Update 筆記整理

[Linux 核心 Copy On Write - Memory Region](https://hackmd.io/@linD026/Linux-kernel-COW-content)

tags: `linux2021`