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
-------- &
A0C0E0G0  ---- >> 1 : 0A0C0E0G

ABCDEFGH
01010101
-------- &
0B0D0F0H  ---- << 1 : B0D0F0H0

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

BADCFEHG
11001100
--------- &
BA00FE00  ---- >> 2: 00BA00FE

BADCFEHG
00110011
--------- &
00DC00HG  ---- << 2: DC00HG00

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


Finally, we now get DCBAHGFE 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);
}