2016年12月11日 星期日

聯發科經典面試題

1. Explain "#error"



所以他就只是一個丟出錯誤訊息的 macro 而已。

2. Explain "struct" and "union"


在 C 中,我們可以利用 struct 來定義自己要的資料結構,例如說二維坐標中的一個點,可以用 struct Point {int x, y;};

同樣的我們也可以用 union 做類似的事情,只是差別在於, union 中的每個成員是共用同樣的記憶體。

3. Explain "volatile". Can we use "const" and "volatile" in the same variable? Can we use "volatile" in a pointer?


volatile 是告訴 compiler 不要擅自對變數作最佳化。

參考以下的 code:

int *x = FOO;
for (int i = 0; i < 100; ++i) {
    bar(i, x);
    *x = FOO;
}

其中 x 在迴圈外被初始化成 FOO (的值),先不管 FOO 是什麼,在迴圈內 compiler 發現 *x = FOO; 可以做一下最佳化讓 *x 不要給值這麼多次以增加執行效率,所以可能忽略 *x = FOO; 做的事情。

但是如果 FOO 是一個硬體的記憶體位置,每次取值可能不同的結果,那 compiler 擅自做了最佳化以後就會造成 *x 只從硬體的記憶體位置中取值取一次 (int *x = FOO;),為了避免這種事情發生,可以利用 volatile 加在 x 宣告的時候:

volatile int *x = FOO;

那 const 可以跟 volatile 一起使用嗎?當然囉,這兩個 keyword 的意思並沒有牴觸。const 的意思是 read-only 而不是不變的,volatile 的意思是他可能會變而不是你可以改他。

4. For the following C code

unsigned long v1 = 0x 00001111;
unsigned long v2 = 0x 00001202;
unsigned long v;
v = v1&(~v2);
v = v | v2;

ask: the value of v?

最後一個 v 可以展開一下:

v = v | v2
  = (v1 & (~v2)) | v2
  = ( v1 | v2 ) & ( ~v2 | v2 )

因為 ~v2 | v2 等於 1,所以展開後

v = v1 | v2 = 0x00001111 | 0x00001202 = 0x0001313

5. For the following C code

int a[5] ={1,2,3,4,5};
int *p = (int *)(&a+1);

ask: the value of *(a+1), (*p-1)?

*(a+1) 其實就是 a[1],所以就是 2;
(*p - 1) 就比較奇怪了,因為 (&a+1) 的關係所以 p 其實存的是 a[5] 的記憶體位置,
(a_pointer + a_number) = (a_pointer + (a_number * sizeof(*a_pointer)))
所以 &a + 1 = &a + 1 * sizeof(*&a) = &a + 1 * 20 = a[5] (這邊是假設 int 大小是 4 bytes)
所以理論上來說 *p 應該是 garbage,就算 - 1 以後還是 garbage ,答案應該是:不知道?


6. write a code

a. set the specific bit
b. clear the specific bit
c. inverse the specific bit (0->1; 1->0)

Macro 的解法:

a.
#define SET_BIT(x, n)      ((x) |=    (1 << (n)))
b.
#define CLEAR_BIT(x, n)    ((x) &= ~(1 << (n)))
c.
#define INVERSE_BIT(x, n)  ((x) ^=   (1 << (n)))

Function 解法:

a.
static inline void set_bit(int *x, int n) { *x |= (1 << n); }
b.
static inline void clear_bit(int *x, int n) { *x &= ~(1 << n); }
c.
static inline void inverse_bit(int *x, int n) { *x ^= (1 << n); }

7. Fill the blank

void(*(*papf)[3])(char *); // Rewrite this
typedef ___________;
pf(*papf)[3];


第三行最後是用 pf 把 *papf 當作參數傳進去,所以把中間的 (*papf)[3] 取出來變成 pf:

typedef void(*pf)(char *);



8. Write a code that check the input is a multiple of 3 or not without using division or mod


最蠢的方式當然就是寫一個迴圈一直減 3 然後看最後是不是剩下 0 ... 但是超沒效率 XD"

直覺想到一個比較好一點的方式是把全部位數相加,如果總和大於 10 的話就繼續做全部位數相加,值到剩下一位數為止,然後看是不是 0, 3, 6, 9,是的話就是 3 的倍數。但是沒辦法用 mod 所以不曉得怎麼取得每個位數 ... 所以大概只能用 sprintf 吧 XD

但實際講起來 sprintf 大概也是有用到除法或者 mod 吧 ...

目前看到有個比較可行的做法是,在 N base 的系統中測試能否被 (N+1) 整除的方式是將偶數位數的和跟奇數位數的和相減,再看是否能被 N+1整除。最常見的例子就是 11 啦,不過那是因為是在 10 base 的系統中,所以在 2 base (也就是 2 進位啦) 的系統中可以用這種方式來判斷是否為 3 的倍數。


int multiple_of_three(int num) {

    if (num < 0)
        num = -num;

    if (num == 0)
        return 1; // true
    if (num == 1 || num == 2)
        return 0; // false

    int even = 0, odd = 0;

    while (num != 0) {
        even += (num & 0x1);
        num >>= 1;
        odd += (num & 0x1);
        num >>= 1;
    }

    return multiple_of_three(even - odd);
}



9. Explain lvalue and rvalue.


lvalue 跟 rvalue 分別指的是 = (等號) 的左邊跟右邊的值,但這樣講不太精確,因為 lvalue 跟 rvalue 描述的是 expression 而不是 object:

C++03 3.10/1 says: "Every expression is either an lvalue or an rvalue."  It's important to remember that lvalueness versus rvalueness is a property of expressions, not of objects

lvalue 可以 reference, rvalue 不能 reference。


2016年12月8日 星期四

[C] strrev

找了一下 kernel 似乎沒有 strrev 所以記錄一下
http://www8.cs.umu.se/~isak/snippets/strrev.c


/*
**  STRREV.C - reverse a string in place
**
**  public domain by Bob Stout
*/
#include <string.h>

char *strrev(char *str)
{
      char *p1, *p2;

      if (! str || ! *str)
            return str;
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}

#ifdef TEST

#include <string.h>

int main(int argc, char *argv[])
{
      while (--argc)
      {
            printf("\"%s\" backwards is ", *++argv);
            printf("\"%s\"\n", strrev(*argv));
      }
}

#endif /* TEST */



[C] Macro 中的 error 與 warning

其實很簡單,而且還很常見,只是我沒有意識到而已 XD

請看 Gnu C 解釋 https://gcc.gnu.org/onlinedocs/cpp/Diagnostics.html

第二個例子看完秒懂:

#if !defined(FOO) && defined(BAR)
     #error "BAR requires FOO."
#endif


這不就是我常常在 Gentoo 做 emerge 很常看到的錯誤訊息嗎 XD


CONFIG_OPENVSWITCH is not set


就只是顯示錯誤訊息而已,差別就 error 會停,warning 就只是警告然後繼續 compile。

[C] const volatile

http://stackoverflow.com/a/4597164 給了一個不錯的解釋。

以下是回答所提供的例子:

unsigned int const volatile *status_reg; // assume these are assigned to point to the 
unsigned char const volatile *recv_reg;  //   correct hardware addresses


#define UART_CHAR_READY 0x00000001

int get_next_char()
{
    while ((*status_reg & UART_CHAR_READY) == 0) {
        // do nothing but spin
    }

    return *recv_reg;
}

因為不希望這支程式改動到 status_reg 跟 recv_reg 指到的值,所以把他們設定為 const。

但並不表示其他程序不會動到 status_reg 跟 recv_reg 所指到的值,以這個例子來說就是硬體會改變那兩個記憶體位置的值。

如果 compiler 在這支程式做最佳化的話,那 while 迴圈可能就只會讀取 status_reg 一次,那就有可能面臨到無窮迴圈跳不出來的問題,所以只好把他們設定為 volatile,叫 compiler 不要偷懶,每次乖乖的去取值。


https://read01.com/oONo5Q.html 提到的一些觀念釐清:


  • const: 含意是「請做為常數使用,這個值只能讀不能寫」,而並非「這個值只是個常數而他不會變」
  • volatile: 含意是「請不要做最佳化,因為這個值可能會變」,而並非「你可以修改這個值」


所以其實 const 跟 volatile 是不矛盾的。


勉強になった。

2016年12月3日 星期六

[Gentoo] 在 Libvirt 上跑 Chromium OS

先裝 repo [1]


$ git clone https://chromium.googlesource.com/chromium/tools/depot_tools.git
$ export PATH=`pwd`/depot_tools:"$PATH"


然後安裝時候需要 sudo,我用 gentoo 沒在用 sudo 所以還要另外裝一下 ...

$ emerge sudo


然後下載 chromium source code

$ mkdir -p ${HOME}/chromiumos
$ cd ${HOME}/chromiumos
$ repo init -u https://chromium.googlesource.com/chromiumos/manifest.git --repo-url https://chromium.googlesource.com/external/repo.git
$ repo sync -j4


開始編譯 [2]


$ export BOARD=amd64-generic
$ cd ${HOME}/chromiumos/src/script
$ ./build_packages --board=${BOARD}
$ ./build_image --board=${BOARD} --noenable_rootfs_verification dev
$ ./image_to_vm.sh --board=${BOARD}

然後就可以看到編好的 vm 檔

$ ls -l ../build/images/amd64-generic/latest/chromiumos_qemu_image.bin
$ file ../build/images/amd64-generic/latest/chromiumos_qemu_image.bin
../build/images/amd64-generic/latest/chromiumos_qemu_image.bin: DOS/MBR boot sector; partition 1 : ID=0xee, start-CHS (0x0,0,2), end-CHS (0x3ff,255,63), startsector 1, 14995391 sectors


用 virt-install 來 import [4]

$ virt-install --virt-type kvm \
               --name chromium \
               --ram 2048 \
               --disk path=/home/mkfsn/chromiumos/src/build/images/amd64-generic/latest/chromiumos_qemu_image.bin \
               --network bridge=br0 \
               --graphics vnc,listen=192.168.0.159 \
               --noautoconsole \
               --os-type=linux \
               --import



因為 os-variant 裡面沒一個適合的,所以我就乾脆不給 XP

打完收工

$ virsh list
 Id    Name                           State
----------------------------------------------------
 4     chromium                       running



Reference
  1. https://www.chromium.org/developers/how-tos/install-depot-tools
  2. https://www.chromium.org/chromium-os/developer-guide
  3. https://www.chromium.org/chromium-os/how-tos-and-troubleshooting/running-chromeos-image-under-virtual-machines
  4. https://www.itfromallangles.com/2011/03/kvm-guests-using-virt-install-to-import-an-existing-disk-image/