Try   HackMD

2020q3 Homework2 (quiz2)

題目

1. is_ascii

目的: 改善效率

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>

#define MMM 0x8080808080808080

bool is_ascii(const char str[], size_t size)
{
  if (size == 0)
    return false;
  int i = 0;
  while ((i + 8) <= size) {
    uint64_t payload;
    memcpy(&payload, str + i, 8);
    if (payload & MMM)
      return false;
    i += 8;
  }
  while (i < size) {
    if (str[i] & 0x80)
      return false;
    i++;
  }
  return true;
}

int main(int argc, char **argv) {
  int i;
  for(i = 1; i < argc; i++)
    printf("%s: %s\n", argv[i], is_ascii(argv[i], strlen(argv[i])) ? "True" : "False");
  return 0;
}

執行結果:

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 →

美國資訊交換標準代碼:
American Standard Code for Information Interchange
定義了128個字元,它主要用於顯示現代英語。

原版的is_ascii()是逐個char做比對,一個char只有8bit很慢。
所以 uint64_t payload; 這行的用意是,指定一個64bit的空間作暫存。
再來透過memcpy把字串讀進這個空間。

再來就是整個程式的核心
payload & MMM
判斷字串是否在ASCII的範圍裡,最直觀的做法就是,每個byte要小於128(即0~127)。

在二進位的世界裡:

12710=0111 11112

也就是最左邊的位元(Most Significant Bit)必須是零,因此只要這的bit是1,這個字元必定不符合ASCII的基本規範。
最簡單的判斷方法就是直接用AND來過濾。
XXXX XXXX AND 1000 0000 得到 X000 0000
再用if判斷有無,馬上就會知道條件是否符合。
而二進位1000 0000用十六進位表達就會是 0x80 (8bit)
又payload有64bit那麼大,(64bit) / (8bit) = (8組0x80)
故這題答案是8組0x80,即 0x8080808080808080

延伸問題 memcpy

延伸問題:
為何用到 memcpy

memcpy語法:
memcpy(target_address, source_address, size_in_bytes)
其功能是把指定區域的內容複寫到目標空間。







structs



source

source

0

1

0

...

0

1

0



target

target

0

1

0

...

0

1

0



source:0->target:0





source:1->target:1





source:2->target:2





source:3->target:3





source:4->target:4





source:5->target:5





source:6->target:6





雖會因架構而異,但 CPU 一般不會一次只處理 1 byte 的資料。
Block size指每次執行的所抓取的資料塊大小,memcpy有多個版本,byte-by-byte, word-by-word所以編譯器會選一個適合尺寸,在資料對齊後,讓CPU可以更有效率去複寫,減少cycle數。

若是不用memcpy而改用strcpy或是其他函數,則難以預料其後果,很可能會變慢或有預想外的行為。

比如說用強轉,在ARM上有可能會造成Unaligned Data Access
uint64_t *payload = (uint64_t *) str

效能差異: 我丟了一個NGS實驗的DNA序列檔,避開讀檔時間,針對個別函數去計時,觀察到6倍以上的速度差距。

int main(int argc, char **argv) {
  char * buffer = 0;
  unsigned long long length;
  FILE *f;
  if (argv[1])
  f = fopen(argv[1], "rb");
  else return 1;
  if(f) {
    fseek (f, 0, SEEK_END);
    length = ftell (f);
    fseek (f, 0, SEEK_SET);
    buffer = malloc (length);
    if(buffer)
    fread (buffer, 1, length, f);
    fclose(f);
  } else return 1;
  double time_spent = 0.0;
  clock_t begin = clock();
  bool b = ori_is_ascii(buffer, length);
  clock_t end = clock();
  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("Time elpased for original is_ascii is %f seconds\n", time_spent);
  begin = clock();
  b = opt_is_ascii(buffer, length);
  end = clock();
  time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("Time elpased for optimized is_ascii is %f seconds\n", time_spent);
  return 0;
}

$ ./run ~/Analysis/25ctrl24_L4_1.fq
Time elpased for original is_ascii is 3.680090 seconds
Time elpased for optimized is_ascii is 0.590715 seconds

2. hexchar2val

目的: 將十六進位的字元轉換成值

#include <stdint.h>
#include <stdio.h>

#define MASK 0x40
#define AAA  3
#define BBB  6

uint8_t hexchar2val(uint8_t in)
{
  const uint8_t letter = in & MASK;
  const uint8_t shift = (letter >> AAA) | (letter >> BBB);
  return (in + shift) & 0xf;
}

int main(int argc, char **argv) {
  int i;
  for(i = 1; i < argc; i++)
    printf("%s = %d\n", argv[i], hexchar2val(*(argv[i])));
  return 0;
}

執行結果:

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 →

首先我們先觀察一下字元的編碼 [0-9],[A-F],[a-f]
數字組0x30, 0x31, 0x32, … 0x39
字母大寫 0x41, 0x42, … 0x46
字母小寫 0x61, 0x62, … 0x66
取字元'0'改用二進位表達,即0x30
0011 0000
取字元'A'改用二進位表達,即0x41
0100 0001
取字元'0'改用二進位表達,即0x61
0110 0001

我們可以看到數字的值剛好等於十六進位的個位數。
而字母的值剛好等於十六進位的個位數再+9

同時,在這裡可以發現,用0100 0000當MASK可以很簡單地把數字跟字母分開。
MASK完後,後續的shift只要選好適當的AAA, BBB值,就可以使shift變數保持恆為0。
in + 0 還是inin再跟0xfAND一次就只剩後面4個bit,這4個bit就是十六進位的個位數值。
到這裡,數字的轉換解決了。

字母的部分,只要想辦法讓in可以+9,就可以得到它的值。
在這裡,letter的值就是0100 0000
再來就是湊數字了,想辦法讓shift變數恆等於9:
往右位移 3, 6次,分別得到0000 10000000 0001
這兩個再OR起來就是9了,即0000 1001
這時(in + shift) & 0xf就會是我們要的東西了。

延伸問題 Hexspeak

延伸問題: Hexspeak
擴充hexchar2val,並輸出對應的十進位數值

#include <stdint.h>
#include <stdio.h>
#include <string.h>
uint8_t hexchar2val(uint8_t in)
{
  const uint8_t letter = in & 0x40;
  const uint8_t shift = (letter >> 3) | (letter >> 6);
  return (in + shift) & 0xf;
}
int hexspeak(const char *in) {
  const char *str;
  str = in + 2;
  int r = 0;
  while (*str) {
    r = r << 4; // r * 16
    r += hexchar2val(*str);
    str++;
  }
  return r;
}
int main(int argc, char const *argv[]) {
  for (size_t i = 1; i < argc; i++) {
    printf("%s = %d\n", argv[i], hexspeak(argv[i]));
  }
  return 0;
}

輸入的字串格式上都以"0x"做開頭,因此可以直接跳過前兩個字元(str = in + 2),剩下的部分再加總起來,因為是16進位,所以每個位數要作加法前都要乘以16,可以用位移簡化。

執行結果:


3. quickmod

目的: 當除數已知,快速求餘數

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

const uint32_t D = 3;

#if defined (__aarch64__) | defined(__amd64__) | defined(__x86_64__)

#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n) {
    uint64_t quotient = ((__uint128_t) M * n) >> 64;
    // {[(2^N - 1) / D] + 1} * [ n / (2^N)]
    return n - quotient * D;
}

#else

#define M ((uint32_t)(UINT32_C(0xFFFFFFFF) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n) {
    uint32_t quotient = ((__uint64_t) M * n) >> 32;
    // {[(2^N - 1) / D] + 1} * [ n / (2^N)]
    return n - quotient * D;
}

#endif

int main(int argc, char **argv) {
    uint32_t i = quickmod(5);
    printf("%d\n", i);
    i = quickmod(55);
    printf("%d\n", i);
    i = quickmod(555);
    printf("%d\n", i);
    return 0;
}

計算

n/d有個特別的方法,由於分子分母同乘任意值,其值不變。所以只要把會用到的最大值事先除以已知的分母
d
(denominator),之後再乘回去變數
n
,這樣做的理由是,對電腦而言,除法計算所需要的操作遠比乘法來的複雜,用乘法取代除法,就可以節省運算所需的時間。

在電腦上,

N位元的組合可以表達
(2N)
個數字。 故
nd=n(2N)d(2N)=n×(2Nd)÷(2N)

從上式可知,除法可拆成三個部分

  1. 變數
    n
  2. 2Nd
    >
    2N1d+1
  3. 2N

(1)由函數的參數提供;(3)除以二的N次方可用位移N次簡化;剩下的就是(2),又

d已知,只要將計算所得作為常數儲存,即可迅速帶入公式求解。

但因為受限於電腦編碼的特性,數字組合包括零,所以最大值其實是

(2N1) ,我們只能用
2N1
作為近似值計算。
2N1
就是全部填滿,即0xFFF直到填滿空間。而為了補足使用近似值所造成的誤差,可再將計算結果加一。 以
(2N1d+1)
取代
2Nd

舉個簡單的例子: 設

N=4 (即只用4bit簡化計算),求
n/3
;在此假設下,最大值為
241=1510
,可表示成
11112
。當
d
已知(d=3),可得
n/d=[n×(153+1)]>>4
。設
n=7
,帶入算式得
422>>4
位移後得 0010 0011,即商為
2
。欲計算餘數,則
ndq=732=1

以相同原理可推廣到更高的位元 (8-bit,16-bit,32-bit,64-bit)

程式的改良:
受限於硬體限制,有些機器沒有 __uint128_t 可用,所以我稍微改寫了一下原始碼,讓它可以在編譯時,選擇比較適當的大小作運算。

多數編譯器可利用以下巨集簡單分辨是否為64位元處理器

#if defined (aarch64) | defined(amd64) | defined(x86_64)
#define code for 64-bit
#else
#define code for 32-bit
#endif

參考資料: Faster remainders when the divisor is a constant: beating compilers and libdivide


4. divisible

目的: 當除數已知,判斷是否整除

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

const uint32_t D = 3;

#if defined (__aarch64__) | defined(__amd64__) | defined(__x86_64__)

#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n) {
  uint64_t quotient = ((__uint128_t) M * n) >> 64;
  // {[(2^N - 1) / D] + 1} * [ n / (2^N)]
  return n - quotient * D;
}

#else

#define M ((uint32_t)(UINT32_C(0xFFFFFFFF) / (D) + 1))

/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n) {
  uint32_t quotient = ((__uint64_t) M * n) >> 32;
  // {[(2^N - 1) / D] + 1} * [ n / (2^N)]
  return n - quotient * D;
}

#endif

typedef unsigned char bool;
#define YYY (M - 1)
bool divisible(uint32_t n)
{
  return n * M <= YYY;
}

int main(int argc, char **argv) {
  uint32_t i = 5;
  printf("MOD = %d, %s\n", quickmod(i), divisible(i) ? "divisible" : "undivisible");
  i = 55;
  printf("MOD = %d, %s\n", quickmod(i), divisible(i) ? "divisible" : "undivisible");
  i = 555;
  printf("MOD = %d, %s\n", quickmod(i), divisible(i) ? "divisible" : "undivisible");
  return 0;
}

除法部分,原理與上題quickmod相同。
回顧一下除法原理: 被除數

÷ 除數 = 商 + 餘(小數點以後的部分)
nd=q+r ; qZ ; 0r<1

假設我們的機器是64位元,當兩個64位元數字相乘會得到128位元的數字。參考到上一題的解法,會發現

q (商)就是
n×M
的前64位元,
r
(餘)就是剩下來的64位元。

在驗證的地方運用到overflow的特性,剛剛說到商就是

n×M的前64位元,因為這裡沒有做位移的操作,所以單純的
n×M
必定overflow,留下來的是後面的64位元。

換句話說,現在留下來的值是

r (小數點以後的部分)
r=ndq ; r{0/d,1/d,2/d,...,i/d} ; i{0,1,2,...,q1}

欲判斷是否整除,

i必須為
0
,由於會有誤差,可以改為判斷
r<1/d

知道這些後,用程式碼表達就是return n * M < M

因為題目要求return n * M <= YYY,考慮到等號造成的誤差M-1才會是適合這題的答案。


5. strlower_vector

目的: 轉換字元編碼成小寫

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#include <ctype.h>
#include <stddef.h>
/* in-place implementation for converting all characters into lowercase. */
void strlower(char *s, size_t n)
{
  for (size_t j = 0; j < n; j++) {
    if (s[j] >= 'A' && s[j] <= 'Z')
      s[j] ^= 1 << 5;
    else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
      s[j] = tolower(s[j]);
  }
}

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

#define VV1 0x80
#define VV2 0
#define VV3 -1
#define VV4 0x80

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
  size_t k = n / 8;
  for (size_t i = 0; i < k; i++, s += 8) {
    uint64_t *chunk = (uint64_t *) s;
    if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
      uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
      uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
      uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
      *chunk ^= mask;
    } else
      strlower(s, 8);
  }
  
  k = n % 8;
  if (k)
    strlower(s, k);
}
int main()
{
  /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
  char str[] = // why not __char *str__, if so, str can not be modified
    "This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever.  You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
  int n = strlen(str);
  strlower_vector(str, n);
  puts(str);
  return 0;
}

比較字元編碼: [A-Z],[a-z]
字母大寫 0x41, 0x42, … 0x5A
二進位 0100 0001, 0100 0002, … 0101 1010
字母小寫 0x61, 0x62, … 0x7A
二進位 0110 0001, 0110 0002, … 0111 1010

巨集PACKED_BYTE的用意跟第1題(is_ascii)的變數payload相近,把小單位的變數拓展成較大的尺寸,達成一口氣比對更多位元的效果。

if ((*chunk & PACKED_BYTE(VV1)) == 0)
欲判斷一個字元是否符合ASCII,直接比對8-bit變數裡的Most Significant Bit

1000 00002=8016
所以VV10x80

指標chunk型態為(uint64_t *),寬度達64-bit。
PACKED_BYTE用乘法把0x80展開,以符合chunk的大小,即0x8080808080808080

VV2VV3 一起看,要圈出字母A~Z的範圍,直觀上分別判斷每個byte是否介於兩者之間(

AbyteZ)。

換個角度想,就是要判斷(byte - 'A' >= 0 && byte - 'Z' <= 0),只是光這樣仍無法簡單用bitwise操作處理。

於是再加一些變化,等式兩邊同加0x80,得到(byte + 128 - 'A' >= 128 && byte + 128 - 'Z' <= 128)

考慮一下溢位,修改一些參數,融合bitwise的精神,整理後得(byte + 128 - 'A' & 0x80)byte + 128 - 'Z' - 1 & 0x80)這兩個條件。

由此可知題目的VV2 = 0;VV3 = -1。

變數AZ利用XOR的特性,做為mask以判斷*chunk是否同時符合條件(介於兩者之間)。

轉換小寫的另一個方法:
只要每個byte都跟

0010 00002OR一下
大寫會轉小寫,小寫依然是小寫。
XOR則比較適合大小寫的轉換。

XOR做完之後,如果是範圍內的數,Most Significant Bit必會是1,上面藍框內提到轉換小寫會用到這個

0010 00002,它跟MSB差了兩個shift,所以mask最後還需要向右位移兩次。

延伸問題 str[] *str

延伸問題:
如果把char str[]更換為char *str,會發生什麼事?

一般這麼做會收到Segmentation fault的訊息,通常指動到不該動的記憶體位址。
*str是唯讀的,屬於靜態配置的string literal,如果你去改它就會觸發undefined behavior。
str[]則會在初始化時,於記憶體裡的stack中建立可修改的副本,不會觸發UB。

6.4.5 String literals

It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.

參考資料: C語言規格書


6. singleNumber

目的: 已知array所有元素必存在三個copies,僅一個元素沒有,求該元素

#define KKK ~higher
#define JJJ ~lower
int singleNumber(int* nums, int numsSize){
  int lower = 0, higher = 0;
  for (int i = 0; i < numsSize; i++) {
    lower ^= nums[i];
    lower &= KKK;
    higher ^= nums[i];
    higher &= JJJ;
  }
  return lower;
}
int main() {
  int data[] = {2,2,3,2};
  return singleNumber(data, 4);
}

原理: 這題的解法很不直觀,先來看看另一種做法的解題思路。
Counting Set Bit - 通過計算位元總數來求解。
data[] = {2,2,3,2}為例可得下表: (

210=102
310=112
)

1 0
1 0
1 1
1 0
將所有數字的各個位元分別加總起來,在左邊這行(column)總合是4,右邊這行是1。分別對3取餘數,各會得到1。兩邊併在一起用二進位表達就是
112=310

這樣做可以很直觀的找到我們要找的single number,但問題是一個int不小,通常有32位元,這意味著有32個bit要數,實作上很可能比先排序再搜尋還要慢。

這裡就要用上一個特別的邏輯操作XOR,XOR有個特性,取任意一個數字,對另一個數字XOR兩次,其值不變,即自反性

pqq=p0=p

真值表如下:

p
q
pq
0 0 0
0 1 1
1 0 1
1 1 0

利用這個會自己回歸的特性,可以用來記錄狀態。如果題目的設定是所有數字兩兩成對,僅一個數單獨存在,那把整個數列(array)從頭XOR到底,就可以很快地得到答案。但由於題目是三個重複,所以還要加一點修改讓變數可以載運行三次後回歸為零。

換句話說,這題的本質就是利用bitwise操作達成三進位的計算。

這題利用兩個變數lower, higher來記錄位元的變化,暫時先用True/False簡化以理解其原理。這裡先畫出我們想要的規律。

出現次數 lower higher
1 True False
2 False True
3 False False
再來答案湊一湊就知道這樣寫可以滿足上面這張表所要的效果。
for (int i = 0; i < numsSize; i++) {
  lower ^= nums[i];
  lower &= ~higher;
  higher ^= nums[i];
  higher &= ~lower;
}

實際去一步一步展開就會是以下結果:

i nums[i] action lower higher
0 2 - 0 0
0 2 lower ^= nums[i] 2 0
0 2 lower &= ~higher 2 0
0 2 higher ^= nums[i] 2 2
0 2 higher &= ~lower 2 0
1 2 lower ^= nums[i] 0 0
1 2 lower &= ~higher 0 0
1 2 higher ^= nums[i] 0 2
1 2 higher &= ~lower 0 2
2 3 lower ^= nums[i] 3 2
2 3 lower &= ~higher 1 2
2 3 higher ^= nums[i] 1 1
2 3 higher &= ~lower 1 0
3 2 lower ^= nums[i] 3 0
3 2 lower &= ~higher 3 0
3 2 higher ^= nums[i] 3 2
3 2 higher &= ~lower 3 0
最終回傳lower=3

延伸問題 LeetCode

延伸問題:
請撰寫不同上述的程式碼,並確保在 LeetCode 137. Single Number II 執行結果正確且不超時

int singleNumber(int* nums, int numsSize){
  if (numsSize == 1) {
    return nums[0];
  }
  int once = 0, twice = 0, thrice = 0;
  for (size_t i = 0; i < numsSize; i++) {
    twice |= once & nums[i];
    once ^= nums[i];
    thrice = once & twice;
    once &= ~thrice;
    twice &= ~thrice;
  }
  return once;
}

利用三個變數搭配邏輯操作,達成三次一循環的效果。
once, twice 分別表示出現的次數。
thrice則在第三次出現時,作為MASK使用,修正oncetwice的狀態。

twice |= once & nums[i];

twice必須比once先執行,確保值的正確性。
如果在oncenums[i]同時有值,代表這個bit已經是第二次出現了,透過AND即可過濾出來。

once ^= nums[i];

once與輸入值nums利用自反性,加入第一次出現的值,同時削去第二次出現的值。

thrice = once & twice;
once &= ~thrice;
twice &= ~thrice;

這三個操作是為了找出出現三次的bit,並記錄在thrice變數,再利用thrice變數反轉作為MASK去除oncetwice的狀態。

LeetCode執行結果:

延伸問題 重複多次

延伸問題:
將重複 3 次改為改為重複 4 次或 5 次

重複 4 次

int singleNumber(int* nums, int numsSize){
  int r = 0;
  for (int i = 0; i < numsSize; i++) {
    r ^= nums[i];
  }
  return r;
}

作法很單純,任何偶數次的都可以這樣處理。
只要一路XOR到底,利用自反性把位元消除,剩下的就會是多出來的那個數字的位元組態。

重複 5 次

#include<stdio.h>
int singleNumber(int* nums, int numsSize){
  if (numsSize == 1) {
    return nums[0];
  }
  int once = 0, twice = 0, thrice = 0, quarce = 0, quince = 0;
  for (size_t i = 0; i < numsSize; i++) {
    quarce |= thrice & nums[i];
    thrice |= twice & nums[i];
    twice |= once & nums[i];
    once ^= nums[i];
    quince = once & twice & thrice & quarce;
    once &= ~quince;
    twice &= ~quince;
    thrice &= ~quince;
    quarce &=~quince;
  }
  return once;
}
int main() {
  int data[] = {0,2,1,2,0,1,0,2,2,1,9,0,1,2,0,1};
  printf("Ans: %d\n", singleNumber(data, sizeof(data)/sizeof(int)));
  return 0;
}

一樣的道理,後面的變數先跟前一個處理(有點像進位),最後處理once

quarce |= thrice & nums[i];
thrice |= twice & nums[i];
twice |= once & nums[i];
once ^= nums[i];

生成出現五次的MASK。

quince = once & twice & thrice & quarce;

最後再消除前面各變數的狀態。

once &= ~quince;
twice &= ~quince;
thrice &= ~quince;
quarce &= ~quince;

執行結果: