Saturday, November 26, 2016

Theory vs Practice -- Linked List and Array

When I was a student, in algorithm course about data structures, we were comparing arrays and linked lists. Arrays are faster than linked lists on random access (O(1) vs O(n)). However, listed lists are faster than arrays for random insertion/deletion operations (O(1) vs O(n)).

In reality, when we consider the L1 and L2 cache in a computer system, the above is not always true. Recently, I found a good page comparing the performance of C++ std::vector (dynamic array), std::list (linked list) and std::deque. When the size of an element is small, vectors and deques perform better than lists. It's because the spatial locality. In arrays, elements are packed next to each others in memory, but in lists, elements are located randomly and linked by pointers. Therefore, when iterating the elements in lists, it will have much higher chance of cache missed. In other words, lists can't get the benefit from cache.

Monday, October 10, 2016

Setup Another Instance of sshd Support Google's Two-Factor Authentication in Raspberry Pi

For security reason, I want to enhance the sshd running in my Raspberry Pi to make use of Two-Factor Authentication (i.e. SSH Key plus Google Authenticator), if an user logins from WAN (from public network). However, if an user logins from LAN (local network), it just needs password or SSH Key for authentication.

To archive this, I need to setup a new instance of sshd with Two-Factor Authentication. The original sshd remains unchange for LAN users. Moreover, I also need to install google-authenticator related packages.

(Note: need to use root account to do below steps)

  1. install the google-authenticator
    apt-get install libpam-google-authenticator libqrencode3
  2. link sshd-second to sshd. The name of executable sshd-second will be used to load the corresponding PAM config.
    ln /usr/sbin/sshd /usr/sbin/sshd-second
  3. create sshd_config-second by copying from sshd_config
    cp /etc/ssh/sshd_config /etc/ssh/sshd_config-second
  4. update the sshd_config-second: Change the "Port" to 9022 (you can use any available port you want); change "ChallengeResponseAuthentication" to "yes"; Set "PasswordAuthentication" to "no"; add "AuthenticationMethods publickey,keyboard-interactive:pam" and add "PidFile /var/run/". Here shows the diff between /etc/ssh/sshd_config and /etc/ssh/sshd_config-second after edited:
    # diff sshd_config sshd_config-second 
    < Port 22
    > Port 9022
    < ChallengeResponseAuthentication no
    > ChallengeResponseAuthentication yes
    < #PasswordAuthentication yes
    > PasswordAuthentication no
    > AuthenticationMethods publickey,keyboard-interactive:pam
    > PidFile /var/run/
  5. create /etc/pam.d/sshd-second by copying from /etc/pam.d/sshd
  6. cp /etc/pam.d/sshd /etc/pam.d/sshd-second
  7. updte the /etc/pam.d/sshd-second: comment out the line "@include common-auth" and add a line "auth required" after "@include common-auth". Here shows the diff between /etc/pam.d/sshd-second and /etc/pam.d/sshd after edited:
    # diff sshd sshd-second 
    < @include common-auth
    > #@include common-auth
    > auth required
    (I comment out the "common-auth" here because I don't want it prompts for password during login.)
  8. create /lib/systemd/system/sshd-second.service by copying from /lib/systemd/system/sshd.service
    cp /lib/systemd/system/sshd.service /lib/systemd/system/sshd-second.service
  9. edit /lib/systemd/system/sshd-second.service: Update the "Description"; update the "ExecStart" to "/usr/sbin/sshd-second -f /etc/ssh/sshd_config-second -D $SSHD_OPTS"; update the "Alias" to "sshd-second.service". Here shows the diff between sshd-second.service and sshd.service after edited:
    # diff sshd.service sshd-second.service 
    < Description=OpenBSD Secure Shell server
    > Description=OpenBSD Secure Shell server (2nd)
    < ExecStart=/usr/sbin/sshd -D $SSHD_OPTS
    > ExecStart=/usr/sbin/sshd-second -f /etc/ssh/sshd_config-second -D $SSHD_OPTS
    < Alias=sshd.service
    > Alias=sshd-second.service
  10. enable and start the new sshd instance:
    systemctl enable sshd-second
    systemctl start sshd-second
    (To check the status of the new sshd, you can run "systemctl status sshd-second")
Up to now, the new sshd setup is done. Next, need to setup Google Authenticator for each users.
  1. Login as user and run "google-authenticator". Like below:
  2. On user's smart phone, open the Google Authenticator app. Then, add the account using the QRCode or input the secret key. (If the user's phone doesn't have the app, please follow this link to install).
  3. To test the login, use ssh command, e.g:
    ssh localhost -o Port=9022
    Then, it prompts for "Verification code". The user can get the code from the Google Authenticator App. As long as the user input the code correctly and with correct ssh-key, he/she can login.
Last but not least, need to update router/firewall setting, such that it blocks the original sshd (port 22) from public network and opens for the port (9022 in my case) of the new sshd instance to be access from public network.

[the demo environment is Raspbian GNU/Linux 8 (jessie)]

Saturday, October 01, 2016

Correct Way to Convert Local Time with DST to GMT/UTC in C

The earth is round (not flat). Timezone and light saving handling is rocket science. Below is a program in C to demonstrate how to convert a string of local time in 'yyyy-mm-dd HH:SS' format to GMT/UTC time. Please note that line "27" is very critical. Without setting the tm_isdst to -1, DST won't be correctly converted.

#include <stdio.h>
#include <time.h>
#include <string.h>

//input should be string of local time in 'yyyy-mm-dd HH:SS' format
int printgmttime(const char * input)
    struct tm localtm;
    struct tm gmttm;
    time_t timestamp;
    int rtval;

    memset(&localtm, 0, sizeof(struct tm));

    rtval = sscanf(input, "%4d-%2d-%2d %2d:%2d",
            &localtm.tm_year, &localtm.tm_mon, &localtm.tm_mday,
            &localtm.tm_hour, &localtm.tm_min);

    if (rtval < 5)
        printf("unable to parse date time '%s'\n", input);
        return 1;

    localtm.tm_year -= 1900; //tm_year = Year - 1900 
    localtm.tm_mon -= 1; //Month (0-11)
    localtm.tm_isdst= -1; //-1 means using system timezone info

    timestamp = timelocal(&localtm);

    gmtime_r(&timestamp, &gmttm);

    printf("GMT Date Time: %04d-%02d-%02d %02d:%02d\n",
            gmttm.tm_year+1900, gmttm.tm_mon +1, gmttm.tm_mday,
            gmttm.tm_hour, gmttm.tm_min);
    return 0;

int main(int argc, char** argv)
    if (argc <= 1)
        printf("Wrong number of argument\n");
        printf("\t%s 'yyyy-mm-dd HH:SS'\n", argv[0]);
        return 1;

    return printgmttime(argv[1]);

Friday, September 30, 2016

WinMerge Alternative in Linux Terminal

WinMerge is a good open source tool to compare text files, but it only runs in Windows platforms. When I need to compare text files in Linux terminal, I use vimdiff (Vim in diff mode). Actually, Emacs also has similar feature. However, I prefer Vim because it's more handy.

To compare two files with vimdiff, you just need to run the vimdiff command with the path of the files you want to compare:
vimdiff file1 file2
Then, you will see something like below:
You can edit the files as a normal Vim editor. However, I would like to highlight some useful commands in diff mode of vim:
Jump to next change
Jump to prev change
Update the current change by copying the change of another buffer.
Update change of another buffer by copying the current change of this buffer.
Ctrl-w Ctrl-w
Switch to another buffer

Wednesday, September 28, 2016

VLC vs MPlayer for DVB playback with hardware decode (vdpau)

Regularly, I have some TV programs been recorded with USB TV tuner. So, I need a program to playback the recorded videos in my Linux box. In Linux world, there are two popular video players -- VLC and MPlayer. I tried both, and here are my comments:

  • VLC provides better GUI. Although mplayer also provide GUI frontends, but they didn't works well. Some of the frontends can't even run. One of the frontend "SMPlayer" can run on my box, but it has some bugs which unable to display the subtitle of the recorded TV programs.
  • In terms of hardware decode, MPlayer works much more stable than VLC. VLC occasionally has errors on decoding and shows blank screen. 
    Decoding Errors of VLC
Finally, I can only use the command line MPlayer. Here is the scripts to playback the videos:

mplayer -vc ffh264vdpau,ffmpeg12vdpau,ffwmv3vdpau,ffvc1vdpau -vo vdpau:deint=3 -framedrop -ao pulse -dr -cache 8192 "$@"

[Testing environment: XUbuntu 16.04, vlc 2.2.2-5, mplayer 2:1.2.1-1ubuntu1, smplayer 15.11.0~ds0-1, libvdpau1 1.1.1-3ubuntu1, vdpau-driver-all 1.1.1-3ubuntu1, Nvidia Linux Driver 367.44]

Sunday, September 25, 2016

Fine Tuning X Window Settings of My Desktop (Nvidia, Dual Mon, Xubuntu 16.04)

Recently, I bought a new desktop and two new monitors. I spent some time to get them working nicely. So, I would like to share my story here.

I installed Xubuntu 16.04 to the desktop. The display card is GeForce GTX 950. Then, I downloaded and installed the Nvidia Linux Driver. I run the Nvidia X Server Settings and export a xorg.conf file.

Here was the "Screen" section of xorg.conf file:
Section "Screen"
    Identifier     "Screen0"
    Device         "Device0"
    Monitor        "Monitor0"
    DefaultDepth    24
    Option         "Stereo" "0"
    Option         "nvidiaXineramaInfoOrder" "DFP-2.8"
    Option         "metamodes" "DP-0.8: nvidia-auto-select +0+503, DP-0.1.8: nvidia-auto-select +1920+0 {rotation=left}"
    Option         "SLI" "Off"
    Option         "MultiGPU" "Off"
    Option         "BaseMosaic" "off"
    SubSection     "Display"
        Depth       24
You can see the "metamodes" was to setup the screen positions and rotation. Please note that the monitor on left is rotated.

Basically, the Nvidia driver worked, but with some issues:
  1. Heavy tearing
  2. In text mode (i.e. alt-F1), the text is on the monitor rotated left. 
After some googling on the web, issue 1 can be fixed by adding "ForceCompositionPipeline = On" in the metamodes. So, the "metamodes" becomes:
"DP-0.8: nvidia-auto-select +0+503 {ForceCompositionPipeline = On}, DP-0.1.8: nvidia-auto-select +1920+0 {rotation=left, ForceCompositionPipeline = On}"
However, issue 2 is bit tricky. After some trial-and-error, I found that the sequence of screens declare on the "metamodes"did the trick. The last screen shows the text in text mode. So, I swapped the DP-0.8 and DP-0.1.8 in the "metamodes":
"DP-0.1.8: nvidia-auto-select +1920+0 {rotation=left, ForceCompositionPipeline = On}, DP-0.8: nvidia-auto-select +0+503 {ForceCompositionPipeline = On}"
Now, it works perfectly.

Sunday, July 20, 2014

Trying Noto Font in Ubuntu 14.04

Google and Adobe developed new Open Source fonts recently. I installed Noto Sans on my Ubuntu 14.04 Desktop. The screenshot below shows three different fonts displaying in a Facebook page in Chrome browser (Ver. 36.0.1985.125) in Ubuntu 14.04 Desktop. The upper screenshot is Google's Noto Sans Traditional Chinese font. Middle one is Microsoft JhengHei (a M$ font from Windows 7). The lower one is WenQuanYi Zen Hei (another open source font come with Ubuntu). You can see Noto Sans performs well. Now, I no longer need M$ fonts for my Linux box.