hw0506 bonus

這個題目我在做測試的時候主要在UBUNTU的環境，用mac的人要注意一下，mac沒有gdb，但有lldb（我不會用。
至於sanitizer的部分，在clang3.1之後應該都有。

這題的重點在於是否懂 Little Endian ，如果懂就結束了。
如果你不知道什麼是 Little Endian 就真的該打屁股了，上課都不認真，去二刷一遍 L紀的課再回來寫這題，我知道你懶得去找哪一部影片，看我多貼心連結我都給你了，趕快去二刷一下（或者有人可能是第一次看？）。

Alice code

一開始我們來看看 Alice 的程式

#include <stdio.h>
#include <stdint.h>
int main(){
    int16_t array[10] = {0};
    for(int32_t i = 0;i < 5;i++){
        scanf("%d", &array[i]);
    }
    for(int32_t i = 5;i > 0;i--){
        printf("%d ", array[i - 1]);
    }
    printf("\n");
    
    return 0;
}

$ gcc hw0506.c -o hw0506
$ ./hw0506
1
2
3
4
5
5 4 3 2 1 

這應該是大家一開始預期中的答案對吧，好那我們看看 Bob 的程式

Bob code

#include <stdio.h>
#include <stdint.h>
int main(){
    int16_t array[10] = {0};
    for(int32_t i = 5;i > 0;i--){
        scanf("%d", &array[i - 1]);
    }
    for(int32_t i = 0;i < 5;i++){
        printf("%d ", array[i]);
    }
    printf("\n");
    
    return 0;
}

$ gcc hw0506.c -o hw0506
$ ./hw0506
1
2
3
4
5
5 0 0 0 0 

有趣的事情來了，為什麼我們的輸出變成5 0 0 0 0了？
我們不是只有把 scanf 和 printf 的順序修改而已嗎？
我剛看到這個問題的時候我就用 gdb 去除錯一下，我發現每次迭代更新之後我舊的值會被覆蓋，我就很納悶為什麼會如此，這邊我告訴各位把這份 code 修改成正確的方式，那就是把 scanf 修改成scanf("%hd", &array[i - 1]);，這樣就好了嗎？對沒錯這樣就好了，不信你自己去試試看。

Solution

我們總該知道為什麼會這樣，為何這樣修改就會是正確的？
首先你先觀察我們的 array 的大小，可以發現是 int16_t ，而 %d 代表的是我要讀取的格式會是一個 int32_t 型態大小的整數，所以我們把 %d 改成 %hd 之後讀取的格式就會是 int16_t 型態大小的整數。意識到問題了嗎？
原因是程式跟電腦要記憶體的時候要的是 2bytes(16bits) ，但是 scanf 讀取的時候卻會把輸入的資料以 4bytes(32bits) 去儲存，這會造成後面輸入的值會覆蓋掉前面輸入的值。

記憶體位置	0x16facb800	0x16facb801	0x16facb802	0x16facb803	0x16facb804	0x16facb805	0x16facb806	0x16facb807	0x16facb808	0x16facb809	0x16facb80a	0x16facb80b
第一次輸入	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x01	0x00	0x00	0x00
第二次輸入	0x00	0x00	0x00	0x00	0x00	0x00	0x02	0x00	0x00	0x00	0x00	0x00
第三次輸入	0x00	0x00	0x00	0x00	0x03	0x00	0x00	0x00	0x00	0x00	0x00	0x00
第四次輸入	0x00	0x00	0x04	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00
第五次輸入	0x05	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00	0x00

由於電腦是使用 Little Endian 的方式去除存，因此會把最不重要的位元儲存在最前面，此外由於我們的 scanf 每次讀入的數值是以 4bytes(32bits) 去儲存，因此會把舊的資料用 0 覆蓋過去，才會導致最後的輸出會是 5 0 0 0 0 。

那 Alice 的程式之所以可以得到預期的答案是因為，她是從第 0 個元素開始迭代，因此不會有被覆蓋的問題，你可以把記憶體位置輸出來看看，你就會懂了，這個部分交給你。

Why the array size is ten? What will happen if the size is five?

題目還沒結束喔，你不覺得奇怪嗎？明明我只需要輸入5個數字，但題目給的code竟然在宣告的地方使用int32_t array[10]，宣告了10個空間，這是為什麼呢？
最一開始我給的解釋會是，因為int16_t是2個bytes，而scanf時使用%d，讀入的數值是以 4bytes 去儲存，因此可以得到：

$$2(bytes)\times 10(\mathrm{宣}\mathrm{告}\mathrm{陣}\mathrm{列}\mathrm{元}\mathrm{素}\mathrm{數}\mathrm{量})=4(bytes)\times 5(\mathrm{輸}\mathrm{入}\mathrm{時}\mathrm{要}\mathrm{存}\mathrm{取}\mathrm{的}\mathrm{元}\mathrm{素}\mathrm{數}\mathrm{量})$$
挺漂亮的，等式成立，當我把array宣告的數量改成 5 並期待他會出錯來佐證我的想法，但編譯程式的時候發現竟然沒有 error 或是 warning ，執行之後也沒有出現 segmentation fault 之類的錯誤，得到的解答與原本 array 宣告10個元素時是一樣的，這時我就很納悶，到底為什麼，你知道為什麼嗎？或許你可以先用你的方式來試試看能不能找出問題，實在不行再往下看。

#include <stdio.h>
#include <stdint.h>
int main(){
    freopen("inp.in", "r", stdin);
    int16_t array[5] = {0};
    for(int32_t i = 0;i < 5;i++){
        scanf("%d", &array[i]);
//        uint8_t *ptr = (uint8_t *)&array[i - 1];
//        for(int32_t j = 0;j < sizeof(int32_t);j++){
//            printf("ptr: %p, 0x%02x\n", (ptr + j), *(ptr + j));
//        }
//        printf("================\n");
    }
    for(int32_t i = 5;i > 0;i--){
        printf("%d ", array[i - 1]);
    }
    printf("\n");

    return 0;
}

好，這題我們先看 Alice 的 code ，我修改了程式碼，從記憶體位置慢慢的找，後來把 gdb 和 sanitizer 打開，我使用 AddressSanitizer 來找問題的所在，不出意外的，打開 sanitizer 後噴錯了，我們來慢慢分析吧。
我先寫一個測試用的檔案叫做 test2.c ，編譯他

$ gcc -fsanitize=address -g test2.c -o test2

是一個 stack-buffer-overflow ，我記得L紀說過 array 是在 stack 裡面的，因此這個錯誤應該能佐證是 array 那邊爆掉，

• memory allocate 時電腦會從 heap 那邊拿記憶體給你，你用 array 電腦會從 stack 拿記憶體給你L紀

我將會把我找出問題的步驟寫出來：
首先我們利用 gdb 去排錯，我發現在 i = 4的時候 sanitizer 會噴錯，所以我在輸入第5個數字之前先把各個元素的記憶體位置輸出，如下：

(gdb) p &array[0]
$21 = (int16_t *) 0xfffffffff510
(gdb) p &array[1]
$22 = (int16_t *) 0xfffffffff512
(gdb) p &array[2]
$23 = (int16_t *) 0xfffffffff514
(gdb) p &array[3]
$24 = (int16_t *) 0xfffffffff516
(gdb) p &array[4]
$25 = (int16_t *) 0xfffffffff518

這讓我知道在前4次的輸入不是造成錯誤的起因，而問題出現在第五次輸入，此外可以注意的是各個記憶體位置是(int16_t *)，因此每一次都是加 2 個bytes，L紀說過，每次增加的量會是指標指過去的那個資料的型別是多少，而 array 是 16bits ，因此每次是加 2 個 bytes ，千萬不要看到 i 是 int32_t 就認為每一次增加的都會是 4 個 bytes 呦。接著看下面那張圖：

因此每一次我們增加的都會是兩個bytes，無論 scanf 時是讀取的格式是 int16_t 型態大小的整數還是 int32_t 型態大小的整數，都是增加兩個bytes，差別在於他每次存取會跨越多少個 bytes ，很明顯我們在使用 32bits 時會跨越到我們原本如果宣告array是5個元素大小陣列以外的記憶體，這就是為何sanitizer會報錯的原因，因此要解決這個問題我們一開始就要把陣列宣告大一點，不然會碰觸到不該碰的地方。
這個例子中我們可以宣告array[6]的大小，之後sanitizer就不會報錯了。
回歸到題目What will happen if the size is five?
這個部分我的解釋就會是如果size是5的話，我們的程式就會碰觸到不該碰觸的地方，也就是我們沒有預先跟記憶體要的位置，因此會有錯誤，因此我們必須宣告一個較大的空間。

但我寫到這邊其實我還是不知道為何在使用 sanitizer 之前執行 array 大小是 5 的程式不會報錯，我在猜是不是剛好碰到後面空的記憶體，所以沒事？希望知道的人能分享自己的想法給我聽，謝謝。

我覺得這一題的價值會是在自己去分析問題，找到問題點，並切入，因此若能自己找出問題點，更能發現這題有趣的地方。