Thursday, August 17, 2017

Some Videos showing Embedded projects I have done

Couple of projects done during my spare time:

ATMega32 interfacing to MAX7219 7seg via SPI 

PIC18F9520 doing ultrasonic ranging 

I wish I made video for the PIC-based IoT sensors I made (part of Computer Engineering project in my master program; It was able to push temperatur and humidty data to 'remote' server periodically, which then display it on the web)

Thursday, August 10, 2017

FizzBuzz Analysis

Recently I was asked this kind of question. As I was told not to worry too much about it and I got many other questions to answer within short time, I did not pay attention to much on it and just scribbled it on a piece of paper, no time to mentally test the algorithm.

At home I realized I did not complete the answer (blame that to the recruiter).  Anyway, the fizz buzz interview question is to ask interviewee to write a code to print number from 1 to 100, but for every multiplication of 3 to print string "FIZZ" (or something), for every multiplication of 5 to print string "BUZZ", and for every multiplication of 3 and 5 (which is another way to say multiplication of 15) to print "FIZZBUZZ".

Here's my working code in C++:

#include <iostream>

using namespace std;

const static char *s1 = "FIZZ";
const static char *s2 = "BUZZ";

int main()
{
    for(int i=1; i<=100; i++)
    {
        if (i% 3*5==0)
        {
            cout << s1 << s2 << endl;
            continue;
        }
        if (i % 3 == 0)
        {
            cout << s1 << endl;
            continue;
        }
        if (i % 5 == 0)
        {
            cout << s2 << endl;
            continue;
        }

        cout << i << endl;
    }
}

No matter whay you do, the optimal solution is always O(n) (unless you're crazy enough to just print manually without loop, such as cout << "1\n2\FIZZ\n4\BUZZ\n...|").

Some silly optimization can be performed in printing the string, though.

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()
{
    for(int i=1; i<=100; i++)
    {
        if (i%15==0)
        {
            cout << s << endl;
            continue;
        }
        if (i % 3 == 0)
        {
            cout << s.substr(0,3) << endl;
            continue;
        }
        if (i % 5 == 0)
        {
            cout << s.substr(4) << endl;
            continue;
        }

        cout << i << endl;
    }
}

Another thought is to eliminate mod 15.  For example:

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()
{
    int m;
    for(int i=1; i<=100; i++)
    {
        m = 0;
        if (i%3==0)
        {
            cout << s.substr(0,3);
            m++;
        }
        if (i % 5 == 0)
        {
            cout << s.substr(4);
            m++;
        }
        if (m > 0)
            cout << endl;
        else
            cout << i << endl;
    }
}

When I tested it (upper limit set to 1000 and perform "time <program>", the last algorithm shows some speedup.

The last few lines can be optimized to be:

        if (m == 0)
            cout << i;
        cout << endl;

Another tiny optimization is instead of doing post increment (i++), we do preincrement (++i).  This saves tiny bit (no copy to extra variable internally).

Last, we can write it down in Assembly if we want.  The following is suitable for embedded device:

main:
leal 4(%esp), %ecx
andl    $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %edi
pushl %esi
pushl %ebx
pushl %ecx

subl $8, %esp
movl $1, %ebx         ; EBX=1
movl $3, %esi         ; ESI=3
movl $5, %edi         ; EDI=5
jmp CHECK_FIZZ

FOR_I_NEXT:
movl %ebx, %eax       ; eax stores current value of i
cltd
idivl %edi             ; i / 5, result in eax and mod in edx
testl %edx, %edx       ; i % 5
jne PRINT_I          ; i % 5 != 0 -> jump to PRINT_I

CHECK_FUZZ:
subl $8, %esp
pushl stdout
pushl 'f'
call _IO_putc
popl %edx
popl %ecx
pushl stdout
pushl 'i'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'z'
call _IO_putc
popl %ecx
popl %eax
pushl stdout
pushl 'z'
call _IO_putc
addl $16, %esp

PRINT_CR:
subl   $8, %esp
pushl stdout
pushl '\n'
call _IO_putc
incl %ebx
addl $16, %esp
cmpl $101, %ebx           ; i == 101 ?
je MAIN_EXIT            ; if (i ==101) goto MAIN_EXIT

CHECK_FIZZ:
movl %ebx, %eax
cltd
idivl %esi
testl %edx, %edx           ; i % 3 == 0
jne FOR_I_NEXT
subl $8, %esp             ; if (i%3==0):
pushl stdout
pushl 'b'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'u'
call _IO_putc
popl %ecx
popl %eax
pushl stdout
pushl 'z'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'z'
call _IO_putc
movl %ebx, %eax
cltd
idivl %edi
addl $16, %esp
testl %edx, %edx
jne PRINT_CR
jmp CHECK_FUZZ

PRINT_I:
pushl %eax
pushl %ebx
pushl $.LC0
pushl $1
call __printf_chk
addl $16, %esp
jmp PRINT_CR
MAIN_EXIT:
xorl   %eax, %eax
leal -16(%ebp), %esp
popl %ecx
popl %ebx
popl %esi
popl %edi
popl %ebp
leal -4(%ecx), %esp
ret



Thursday, June 22, 2017

Onion Omega2+ Terminal on browser

After I installed the web-based Terminal on my Omega2, I was able to login to the terminal via web-browser. Cool!


Tuesday, June 20, 2017

My Omeaga2+ OpenWRT Card

Finally, after waiting for almost 10 months, my order of Omega2+ from Onion arrived yesterday.
Will post later about the getting started experience.  For now, only pictures.



Tuesday, June 13, 2017

Interesting opinions About Job Interviews

I one day stumbled upon this site (Things I Learned From Failing Technical Interviews), a section called "Do not be Yourself" intrigued me.

Contrary to the popular suggestions from many career advisers to be yourself during job interview, the person suggests the interviewee not to be him/herself, but to be a robot.  I totally agree with his opinion.  If you've done multiple job interviews for software engineer job position, you might have experience unease when the interviewer expect you to be perfect in coding in front of him/her. No syntax errors, have to memorize the APIs, etc.  The blogger continues to say that hiring a candidate is just like another upgrade of server or adding another PC in the server cluster, which is to offload work from the team to the new hired.

It is almost a guarantee that you will be asked something you don't know and even an hour of thinking about it and problem solving around it you still won't know.  Sometimes you get asked something you've known it long time ago, but can no longer able to grasp it and explain it to them.  You feel like you're an idiot with glamorous title and said experiences (and preconceive that the interviewer must says in his mind, "why the heck this guy is applying for this position"?)

Another jobseeking-related blog: I will get That Job at Google

Wednesday, June 7, 2017

Swamping two variables without temporary variable

Based on the Boolean Algebra, where XOR operator is commutative and associative:

A = A ⊕ B
B = B ⊕ A = B ⊕ (A ⊕ B) = B ⊕ (B ⊕ A) = (B ⊕ B) ⊕ A
  = 0 ⊕ A = A
A = A ⊕ B = (A ⊕ B) ⊕ A = B ⊕ (A ⊕ A) = B

So the steps are:

A = A^B;
B = B^A;
A = A^B;

Another way is by doing arithmetics:

A = A - B;
B = A + B;
A = B - A;

Or
A = A + B;
B = A - B;

A = A - B;

If we look at carefully, the XOR operator is actually a half-adder operation (with carry bit).

A ⊕ B = A' * B + A * B', where if A=1 the result would be equal to B', else equal to B.

Tuesday, May 23, 2017

Bits Reversal - Advanced

Suppose we have 16-bit number where we want to reverse some bits between bits i'th and j'th.  To illustrate that, say we have a 16-bit value stored in v:

|<-------- L = sizeof(short)*CHAR_BIT --------->|
 15                       7                1   0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  | x| x| x| x| x| x| x|  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 
          ^                  ^
          |                  |
         i=12               j=6
|<------>|
 L - i - 1
  

So, we want to reverse bits between bits 6th to 12th.

Assume i is always greater than j (i > j):
Number of bits to reverse: n = (i - j) + 1

Mask to use: (2^n - 1) << j

Or, in the case above:

n = (12 - 6) + 1 = 7
mask = (2^7 - 1) << 6 = 127 << 6  = 0x1FC0 (0001111111000000 in binary)

Then we mask the bits stored in v and shift it back to 0 (to do reverse operation):

r = (v & mask)  >> j;

r =
 15                       7                1   0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 0| 0| 0| 0| 0| 0| 0| 0| 0| x| x| x| x| x| x| x|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+


We use bit reversal operation as posted previously on r:

r = bit_reversal(r);

After this call, the bits are reversed, but filled in from MSB.  We need to put them to the position originally started.

 15                       7                1   0
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| x| x| x| x| x| x| x|  |  |  |  |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                    |-------> shr 3

<========= sizeof(unsigned int)* CHAR_BIT ======>


m = sizeof(short) * CHAR_BIT - n - j
m = 2*8 - 7 -6 = 16 - 13 = 3

Final result is:

(v & !mask) | ((r >> m) & mask);

Bit Reversal - Explained

The page Bit Twiddling Hacks shows how to reverse bits in an integer (e.g, reverse LSB with MSB bits or reading bits from the opposite direction), but seems it doesn't explain anything why that works.

Here I try to explain it step by step.  Let start with a 8-bit char first.  Assume each letter in ABCDEFGH represents each bits in the char (e.g, A is for MSB etc.).

x = ABCDEFGH

ABCDEFGH
10101010 (or 0xAA)
-------- &
A0C0E0G0  ---- >> 1 : 0A0C0E0G

ABCDEFGH
01010101 (or 0x55)
-------- &
0B0D0F0H  ---- << 1 : B0D0F0H0

0A0C0E0G
B0D0F0H0
-------- |
BADCFEHG  ---> stored as a new x, then we do next operation

BADCFEHG
11001100  (or 0xCC)
--------- &
BA00FE00  ---- >> 2: 00BA00FE

BADCFEHG
00110011  (or 0x33)
--------- &
00DC00HG  ---- << 2: DC00HG00

00BA00FE
DC00HG00
-------- |
DCBAHGFE


Last, we operate the similar thing on the high and low nibbes:

DCBAHGFE
11110000 (or 0xF0)
-------- &
DCBA0000   ==> >> 4 = 0000DCBA

DCBAHGFE
00001111 (or 0x0F)
-------- &
0000HGFE   ==> << 4 = HGFE0000

0000DCBA
HGFE0000
--------|
HGFEDCBA

Finally, we now get HGFEDCBA which is the reversed bits of ABCDEFGH!  For operation on 32-bit data, we do the similar one, except we do with 32-bit mask (instead of 10101010 binary or 0xAA, we mask with 0xAAAAAAAA) plus extra two pair of masks (0xF0F0F0F0 and 0x0F0F0F0F, 0xFF00FF00 and 0x00FF00FF) with shift left/right 4, 8 and 16 bit.

So, bit-reversal computation or algorithm for 32-bit integer:

unsigned int reverse_bits(unsigned int x)
{
    x = ((x & 0xA0A0A0A0) >> 1) | ((x & 0x05050505) << 1);
    x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
    x = ((x & 0x0F0F0F0F) >> 4) | ((x & 0xF0F0F0F0) << 4);
    x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8);
    return (x >> 16) | (x << 16);
}




Monday, April 17, 2017

Infrastructure of Data Science and Analytics

Data Science apparently is now becoming a trend.  It basically a collection of methods and paradigms in querying, analysing, processing and visualizing big data.  Oil companies, business intelligence and marketing, social media, Artificial Intelligence, etc. want that.

Definition
Big Data: Extremely large data sets that may be analyzed computationally to revel patterns, trends, and associations, especially relating to human behavior an interactions.

  • Cluster: a collection of computers working together in parallel (distributed processing) and in the same local network and using the similar hardware
  • Grid: Similar to grid, but computers are geographically spread out and use more heterogeneous hardware.  
  • Hadoop: a Java-based programming framework that supports the processing and storage of extremely large data sets by using MapReduce framework.  It's open source under Apache license.
  • MapReduce, a core component of the Apache's Hadoop Software Framework.  Originated from Google Research paper with the same name.
  • Hiv
  • Pig: a high-level platform for creating programs that run on Apache Hadoop.  It consists of high-level language called Pig Latin abstracting underlying Java on Hadoop.
  • SQL
  • Full-stack
  • MIKE2.0
  • Groovy
  • Tez

Monday, March 20, 2017

OpenWRT Modules: JUCI

JUCI = JavaScript for UCI (Unified Configuration Interface): the Web UI interface to the UCI (or, simply "The GUI front end" of OpenWRT).  Mainly developed by Martin K.  Schröder <mkschreder.uk@gmail.com>
Foundation: The jQuery and angularJS famework.

About
URL
JUCI GIT Repohttps://github.com/mkschreder/juci
JUCI Documentation in HTML formhttp://mkschreder.github.io/juci
overview of how juci workshttp://mkschreder.github.io/juci/manual/how-juci-works.html
AngularJS
AngularJS version 1 Documentationhttps://docs.angularjs.org/guide

Client Browser

Must be HTML5-enabled browser with Javascript enabled.

Principles

OpenWrt's central configuration is split into several files located in the /etc/config/ directory. Each file relates roughly to the part of the system it configures. 

Flow

  1. Modify config file (a file in /etc/config)
  2. restart service that uses that config file (/etc/init.d/<service script>)

Directory Structure

TOPDIR=$HOME/work/raptor/openwrt
As defined in $TOPDIR/feeds/juci/juci/Makefile, the tarballed juci package is downloaded into $TOPDIR/dl/juci-<ver#>.tar.gz
and untarred into $TOPDIR/build_dir/target-arm_cortex-a9_uClibs-<ver>

MAKE
====
Steps done in pakage/feeds//Makefile:
TARGETNAME=target-arm_cortex-a9_uClibc-0.9.33.2_eabi
PKG_BUILD_DIR=$TOPDIR/build_dir/$TARGETNAME/
mkdir -p ${PKG_BUILD_DIR}
cp $TOPDIR/package/feeds//src/* ${PKG_BUILD_DIR}/
make -C $TOPDIR/staging_dir/${TARGETNAME}/usr/src/juci/ MODULE=${PKG_BUILD_DIR}

Files

To see the latest pull of JUCI into our branch, check PKG_VERSION in $TOPDIR/feeds/juci/juci/Makefile
In $TOPDIR/target/linux/bcm5301x/base-files/etc/uci-defaults/config:
  • content-filter
  • juci
  • srg-diagnostics
  • system
  • user-interfaces

In $TOPDIR//packages/juci-full-/files/etc/config/:
  • capo

In $TOPDIR//packages/juci--family-shield/files/etc/config/family-shield/:
  • family-shield

In $TOPDIR/package/base-files/files/etc/config/:
  • iptv
  • network
  • ntra
  • webdav
  • wifi-insight

In $TOPDIR/network/services/ipset-dns/files/:
  • ipset-dns.config (installed as ipset-dns in target's /etc/config)


To do clean build of the whole JUCI + Juci modules:

Building Juci
make package/feeds/juci/juci/{clean,prepare,compile} package/index V=s

JUCI html files are compiled into the *.js files by command:

HTML to JS
./scripts/juci-build-tpl-cache


(The Makefile above converts html files into *.js and put in tarball file named: node_modules.tar.gz

JUCI in feed

This subdirectory is used when we want to create a JUCI patch.  We git pull the juci module into $TOPDIR/feeds/juci/juci. 

See Creating patches to JUCI core modules

The following script might be useful to do the steps as described above

JUCI Checkout
#!/bin/bash
if [ $# -lt 1 ]
then
    echo ""
    echo "$0 <juci version/tag>"
    echo ""
    echo "Current version for SOS: v2.16.09"
    exit
fi
tag=$1
cd ~/work/raptor/openwrt
./scripts/feeds update juci
pushd feeds/juci
git submodule init
git submodule update
cd juci/src
git checkout ${tag}
popd
make package/juci/clean V=s && make V=s


Once we've done the script above, we can start editing files needed.  Once we're done, just create a patch (assuming we're already in directory $TOPDIR/feeds/juci/juci/src):

Creating patch
git diff -p --stat > ../patches/01x-my-patch-name.patch


JUCI Components

  • JUCI core (juci.js)
  • Plugins (for example: js/50-juci-ddns.js, etc.)
  • Theme *.js

The plugins are located (to be exact: extracted to) $BUILD_DIR/$TARGETNAME/juci-<juci-ver#>/plugins/
For example, for menu "WIFI", the plugin is in $HOME/work/raptor/openwrt/build_dir/target-arm_cortex-a9_uClibc-0.9.33.2_eabi/juci-fcfb1fcd85735c69ffad89a9d3d9b6c26d3df810/plugins/juci-openwrt-wireless

JUCI on Target Device

The JUCI config file is /etc/config/juci, which contains menus and submenus
To tell juci to reload, type juci-update

Creating JUCI Patch

Creating patches to JUCI core modules

LINKS

Juci Coding Standard
JUCI Build Environment Setup
Testing juci core patches
JUCI Debugging Tips
Creating patches to JUCI core modules
JUCI Coding Standard