My Stuff

Sunday, March 11, 2012

Computer Design Fun Party!

To compute expression A = (B-C)*(D-E)

Using accumulator:

Load B ; acc = B; opcode=1 B, oper=2B; mem.traf = 2 B

Sub C ; acc = B – C; 1 byte opcode, 2-bytes operand = 3 bytes

Store A ; A = B -C; 1 byte opcode, 2-bytes operand = 3 bytes

Load D ; acc = D; 1 byte opcode, 2-bytes operand = 3 bytes

Sub E ; acc = D -E; 1 byte opcode, 2-bytes operand = 3 bytes

Mul A ; acc = (B-C)* (D-E) ; 1 byte opcode, 2-bytes operand = 3 bytes

Store A ; A = (B-C) * (D-E) ; 1 byte opcode, 2-bytes operand = 3 bytes

Assume each opcode takes 8-bit, operands are 16-bit and data is move in 16-bit chunks:

Total bytes: 7 * 3 byte = 21 bytes

Memory traffic: 21 + 7 * 2 = 35 bytes

Using load-store:

Ld B, r1 ; r1 = B; opcode=1 B, op = 2 B; mem. traff = 2 bytes

Ld C, r2 ; r2 = C; memory traffic = 2 bytes

Sub r1, r2,r3 ; r3 = r1 * r2 = B – C; size=2 bytes, memory traffic = 0

Ld D, r1 ; r1 = D; memory traffic = 2 bytes

Ld E, r2 ; r2 = E; memory traffic = 2 bytes

Sub r1,r2,r4 ; r4 = r1 * r2 = D-E; memory traffic = 0 bytes

Mul r3, r4, r1 ; r1 = r3 * r4 = (B-C) * (D-E); memory traffic = 0 bytes

St r1,A ; A = r1 = (B-C) * (D-E); memory traffic = 2 bytes

Number of bytes for instructions: 3*7 = 21 bytes

Memory traffic: 21 + 5 *2 = 31 bytes

Using stack:

Push B ; mem. Traf = 2 bytes

Push C ; mem. Traf = 2 bytes

Sub ; B – C; mem. Traf. = 2 bytes

Push D ; mem traf = 2 bytes

Push E ; mem.traf = 2 bytes

Sub ; top of the stack contains D-E, below it is B-C

Mul ; top of the stack now contains (B-C) * (D-E)

Each instruction occupies 3 bytes (1 byte opcode and 2-byte operand), so total instructions use 3*7 = 21 bytes.

Memory traffic: 21 + 2*7 = 35 bytes

Register 0, 1, 2 (R0, R1, R2) are GPRs. R3 is initialized to 1 and make sure it is unchanged.
1. Control sequence that forms the 2’s complement difference (or, R0 ← R0 + (-R1) = R0 + 2^’s complement of R1) of the contents of R0 and R1:

Write Enable				A-bus enables				B-bus enables				F₀F₁		Time
0	1	2	3	0	1	2	3	0	1	2	3	F₀	F₁	T
0	1	0	0	0	1	0	0	0	0	0	0	1	1	0
0	1	0	0	0	1	0	0	0	0	0	1	0	0	1
1	0	0	0	1	1	0	0	1	0	0	0	0	0	2

Explanation:

At T=0:

F₀F₁ = 11 (A’), A-bus enable = 1, B-bus enable = all zeros. Data (say, Y) is placed in A-bus. C-bus contains Y’, Write-enable = pin 1. So Y is written to register 1 (R1 = Y’).

At T = 1:

F₀F₁ = 00 (add), A-bus enable = pin 1 (content of R1 which is X, is in A-bus), B-bus enable= pin 3 (content of R3 which is 1 is in B-bus), write-enable = pin 1 (C-bus contains Y’ + 1). So R1 = Y’ + 1 = 2’s compl. Of X.(or R1 = -Y)

At T = 2

B-bus = 0, hence data from R0, say X, is placed in B-bus. F₀F₁ = 00 (add), A-bus enable = 1 (which contains –Y). C-bus contains R0 + R1 = X - Y . Write-enable = pin 0, so result is stored in R0.

R0 XOR R1 (R0’ & R1 + R0 & R1’) = (R0 + R1)(R0’ + R1’), leaving the result in R0.

Write Enable				A-bus enables				B-bus enables				F₀F₁		Time	Note
0	1	2	3	0	1	2	3	0	1	2	3	F₀	F₁	T	(Movements etc.)
0	0	1	0	1	0	0	0	0	1	0	0	0	0	0	R2 ← A + B
1	0	0	0	1	0	0	0	0	0	0	0	1	1	1	R0 ← A’
0	1	0	0	0	1	0	0	0	0	0	0	1	1	2	R1 ← B’
0	1	0	0	1	0	0	0	0	1	0	0	0	0	3	R1 ← A’ + B’
1	0	0	0	0	1	0	0	0	0	1		0	1	4	R0 ← (A+B)&(A’+B’)

Booth Multiplication Algorithm:

/***********************************************************
Title: Booth Algorithm sample
Desc: To simulate booth multiplication algorithm
Author: Buhadram
Notes:

Ref:
- Computer Architecture: A Quantitative Approach
*************************************************************/
#include 
#include 
#include 
#include 

#define NUMTYPE	   	short int
#define NUMBITS		(8*sizeof(NUMTYPE))
#define MAX(x,y) 		((x) > (y) ? x : y)
#define MIN(x,y) 		((x) < (y) ? x : y)
#define BITMASK(x,mask) 	((x) & mask)
/*********************************
proc: bitmask
desc: return 1 if bit[pos] is set
      pos=0 for LSB, and p=sizeof(x)-1
      for MSB
*********************************/
#define BIT(x,pos)		( (BITMASK(x,1<<(pos))) >> (pos) )
#define ASCII_BIT(x)	((x) + '0')

char *get_input(const char *prompt, char *buf, int length)
{
	char *p;
	int i;
    printf("%s",prompt);
	// fgets is safer to avoid buffer overflow
	p = fgets(buf, length, stdin);
	// remove newline character
	buf[strlen(buf)-1] = 0;
	return p;
}

/********************************************
* Swapbits
* Desc: To swap bit orders, e.g LSB becomes MSB
        Note: b[0] is LSB, b[n-1] is MSB
********************************************/
void swapbits(NUMTYPE *b)
{
    int i;
    int tmp;

	tmp = 0;
	for(i=0; i base)
       base = 10;                    /* can only use 0-9, A-Z        */
    tail = &buf[BUFSIZE - 1];           /* last character position      */
    *tail-- = '\0';

    if (10 == base && N < 0L) {
	   *head++ = '-';
       uarg = -N;
    }
    else uarg = N;

    if (uarg) {
  	   	for (i = 1; uarg; ++i) {
       	   register ldiv_t r;
		   r = ldiv(uarg, base);
           *tail-- = (char)(r.rem + ((9L < r.rem) ? ('A' - 10L) : '0'));
           uarg    = r.quot;
    	}
    }
    else  *tail-- = '0';
	memcpy(head, ++tail, i);
    return str;
}

#endif


/******************************
proc: btol
desc: converts binary string to
	  long integer
******************************/
long btol(const char *bin)
{
    int n,i;
    long d;

	n = strlen(bin);
	d = 0;
	for(i=n-1; i>=0; i--) {
		d += (bin[i]-'0') * (1 << i);
    }
    return d;
}

/**************************************
Proc: Ashift_bits_right
desc: perform arithmetic shift right on
    bits in x, but preserving the sign bit.
***************************************/
void ashift_bits_right(long *x, int numbits)
{
    int neg;

    neg = (*x<0) ? 1 : 0;
    *x >>= numbits;

    if (neg)
       //*x |= (1<>= 1;
		qm = q0;
		q >>= 1;
		if (a0)
		   r |= b1;
		b1 <<= 1;
    }
    return r;
}


int main(int argc, char *argv[])
{
	#define BUF_SIZE	(1024+1)
	char *buf;
	NUMTYPE A, B;
	long res;
	char str[256];

	buf = (char *)malloc(BUF_SIZE+1);
	assert(buf);
    get_input("A = ", buf, BUF_SIZE);
    A = atol(buf);
    printf("A (in Binary) = %s\n", ltoa(A, str, 2));
    get_input("B = ", buf, BUF_SIZE);
    B = atol(buf);
    printf("B (in Binary) = %s\n", ltoa(B, str, 2));
    res = A+B;
    printf("A + B = %ld = 0x%0X\n", res, res);
    res = A - B;
	printf("A - B = %ld = 0x%0X\n", res, res);
    puts("\n\nBOOTH MULTIPLICATION\n");
    res = booth_mult(A,B);
	printf("A * B = %ld = 0x%0X = %sb\n", res, res, ltoa(B,str,2));
    free(buf);
	return 0;
}

Friday, March 9, 2012

Counting the number of "1" bits

Another "ridiculous" interview I had was when an interviewer asked me how to count the number of set bits in a 32-bit or 8-bit. I told him that there are various algorithms to do this, but the easiest way but yet good enough in performance is a function like this:

uint32_t count_bits(uint32_t b)
{
    int i;
    int n = 0;
    
    for(i=0; i<sizeof(b)*8; i++)
    {
        n += (b & 1);
        b >>= 1;
    }   
    return n;
}

I also told him that there are many ways to do this (referred him to look at "Beautiful Code" to see some of the beautiful algorithms).

But then the interviewer argued. FIrst, he said the upper border of the for-loop should be to "sizeof(b)*8" (meaning, instead of using "<", I should have used "<="). To bad, I said yes to him without thinking further (Probably got nervous. Later at home, I checked that he was wrong). Second, he said that the fastest is to use look-up table (n[0] = 0, n[1]=1, n[2]=1,...,n[255]=8,...). Although I agreed with his argument, but then he become inconsistent with his original question and there is a big downside of his argument. I said that this wouldn't be a choice in embedded programming where memory resource is limited. Secondly, his original question was to compute ones in a 32-bit number. That means we have to 2^32 (4,294,967,296 or about 4 GBytes) items set manually in an array. That's so ridiculous. Who wants to waste that much space just to calculate the number of bits in an integer? For a byte, although it seems acceptable ("only" 256 bytes of table), but compare that to the above algorithm:

movl $32,  %edx
 xorl %ecx, %ecx

.L2:
 movl %ecx, %ebx
 shrl %ecx
 andl $1,   %ebx
 addl %ebx, %eax
 decl %edx
 jne .L2

It's only 7 x86 mnemonic instructions (about 12-18 bytes) and no memory involvement in the loop!. Yes, it is O(32) for 32-bit, but it's a constant speed. Even further, if the function is called only once, the fully optimized version of the instructions would be inserted inline in the place (without calling the function), so we can CPU time from doing push-pop stack frames. That's another tiny speedup. It's probably fine for table lookup (yes, it's the fastest, O(1)), but it is limited to 8-bit. For 16 or higher, seems the space-time trade-off is too big not to consider. Besides, the above algorithm extendable into polymorphism in Object-Oriented code.

When I searched Google, I found the following (on Stanford's web):

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Which renders to instruction codes like below:

shrl %edx
 andl $1431655765, %edx
 subl %edx, %eax
 movl %eax, %edx
 shrl $2, %eax
 andl $858993459, %edx
 andl $858993459, %eax
 addl %edx, %eax
 movl %eax, %edx
 shrl $4, %edx
 leal (%edx,%eax), %eax
 andl $252645135, %eax
 imull $16843009, %eax, %eax
 shrl $24, %eax

(14 mnemonics). This seems the fastest and most optimized. It took some time for me to understand it.

Seems the interviewer doesn't have enough experience in embedded or microcontroller or doesn't think much about optimization. Nevertheless, I failed an interview again. I start to think that many interview questions are really not to dig the thinking ability of a candidate, but rather to get instant answers meet their mind. I just hope big software companies like IBM, Microsoft, Google or Apple shouldn't fall to this kind of trap, but rather ask logical questions to know if the candidate can think systematically.

What a waste!

Thursday, March 8, 2012

Parallelizable integer multiplication

At a recent interview with an Amazon, the hiring manager asked me about an algorithm to do integer multiplication without using any multiplication/division symbol in parallel computing. The following algorithm was suggested to do integer multiplication without using any "MULT" instruction:

int mult(int x, int y)
{
 int z;

 if ((x==0) || (y==0))
  return 0;
 if (x==1)
  return y;

 if (y==1)
  return x;

 z = mult(x, y>>1);
 if (y % 2 == 0)
  return z<<1;
 else
  return x + (z<<1);
}

My question came up, is this parallelizable? My argument to the interviewer was that this is not a good approach if he is asking from parallel computation perspective (See Robertazzi's papers on ACM journals to know more detail about parallel computation)

When a recursive call is made, the parameters are pushed into the stack before calling each subsequence recursive call. Involving stack in this manner is hardly parallelizable, because there is coupling of current result based on previous results. One of the principle of parallel computing is to decouple two or more computation as much as we can.

A dig into highly-optimized assembly language of the above code:

mult:
 pushl %ebp
 movl %esp, %ebp
 subl $24, %esp
 movl %ebx, -8(%ebp)
 movl %esi, -4(%ebp)
 movl 12(%ebp), %ebx
 movl 8(%ebp), %esi
 testl %ebx, %ebx
 je .L4
 testl %esi, %esi
 je .L4
 cmpl $1, %esi
 je .L2
 cmpl $1, %ebx
 .p2align 4,,3
 je .L5
 movl %ebx, %eax
 movl %esi, (%esp)
 sarl %eax
 movl %eax, 4(%esp)
 call mult
 andl $1, %ebx
 je .L7
 leal (%esi,%eax,2), %ebx
.L2:
 movl %ebx, %eax
 movl -4(%ebp), %esi
 movl -8(%ebp), %ebx
 leave
 ret
 .p2align 4,,10
 .p2align 3
.L4:
 xorl %ebx, %ebx
 movl -4(%ebp), %esi
 movl %ebx, %eax
 movl -8(%ebp), %ebx
 leave
 ret
 .p2align 4,,10
 .p2align 3
.L7:
 leal (%eax,%eax), %ebx
 movl -4(%ebp), %esi
 movl %ebx, %eax
 movl -8(%ebp), %ebx
 leave
 ret
 .p2align 4,,10
 .p2align 3
.L5:
 movl %esi, %ebx
 movl -4(%ebp), %esi
 movl %ebx, %eax
 movl -8(%ebp), %ebx
 leave
 ret

As can be seen, "SARL" (Shift Arithmetic Left) for the shift-left operation. Some issues after analyzing this code. First, there are multiple register-to-memory flow while doing the recursive:

movl %ebx, %eax
 movl %esi, (%esp)
 sarl %eax
 movl %eax, 4(%esp)

Memory access is expensive and the instructions might cause cache miss thus forcing CPU to reread data from RAM.
Another issue, how do we parallelize this, if there is stack push-pop coupling for the result?

My argument was to decompose the computation into two (or more) portions.

For example:

int pivot = b/2;

for(i=0; i<pivot; i++)
    sum1 += a;

for(i=pivot+1; i<b; i++)
    sum2 += a;
sum = sum1 + sum2;

No, let's check what we can see in the x86 assembly (gcc-generated):

mult:
 pushl %ebp
 movl %esp, %ebp
 subl $8, %esp
 movl 12(%ebp), %eax
 movl %ebx, (%esp)
 movl %esi, 4(%esp)
 movl 8(%ebp), %edx
 testl %eax, %eax
 je .L5
 testl %edx, %edx
 je .L5
 cmpl $1, %edx
 je .L2
 cmpl $1, %eax
 .p2align 4,,3
 je .L6
 movl %eax, %ecx
 xorl %esi, %esi
 shrl $31, %ecx
 xorl %ebx, %ebx
 addl %eax, %ecx
 sarl %ecx
 testl %ecx, %ecx
 jle .L3
 movl %ecx, %esi
 movl %ecx, %ebx
 imull %edx, %esi
.L3:
 xorl %ecx, %ecx
 cmpl %ebx, %eax
 jle .L4
 movl %eax, %ecx
 subl %ebx, %ecx
 imull %edx, %ecx
.L4:
 leal (%ecx,%esi), %eax
.L2:
 movl (%esp), %ebx
 movl 4(%esp), %esi
 leave
 ret
 .p2align 4,,10
 .p2align 3
.L5:
 xorl %eax, %eax
 movl (%esp), %ebx
 movl 4(%esp), %esi
 leave
 ret
 .p2align 4,,10
 .p2align 3
.L6:
 movl %edx, %eax
 jmp .L2

As can be seen, most of operations are in registers, also there is decoupling between 2 partitions (e.g, sum1 does not rely on sum2). The more we partition the calculation (e.g, pivot1 = b/4, and do 4 for-next loops for each partition), the more divisible partition can be accomplished by parallel computer. I was arguing that to optimize computation, hence lowering O(n), we should use divisible loops ("divide-et-empera") instead of recursive approach (seems the interviewer disagreed)

PS: My argument above caused me not to land job at Amazon.

Sunday, February 26, 2012

Simple UDP Client

<pre>

/* UDP client in the internet domain */
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))

void error(const char *);

int main(int argc, char *argv[])
{
int sock, n;
unsigned int length;
struct sockaddr_in server, from;
struct hostent *hp;
char buffer[256];

if (argc < 3) {
printf("Usage: %s <port>\n", argv[0]);
exit(1);
}
sock= socket(AF_INET, SOCK_DGRAM, 0);
if (sock < 0) error("socket");

server.sin_family = AF_INET;
hp = gethostbyname(argv[1]);
if (hp==0) error("Unknown host");

bcopy((char *)hp->h_addr,
(char *)&server.sin_addr,
hp->h_length);
server.sin_port = htons(atoi(argv[2]));
length=sizeof(struct sockaddr_in);
printf("Please enter the message: ");
bzero(buffer, sizeof(buffer));
fgets(buffer, sizeof(buffer)-1, stdin);
n=sendto(sock,buffer,
strlen(buffer),0,(const struct sockaddr *)&server,length);
if (n < 0)
error("Sendto");
n = recvfrom(sock, buffer, sizeof(buffer), 0, (struct sockaddr *)&from, &length);
if (n < 0)
error("recvfrom");
printf("Got an ack: %d bytes\n", n);
write(1, buffer, MIN(n, strlen(buffer)));
close(sock);
return 0;
}

void error(const char *msg)
{
perror(msg);
exit(0);
}

</pre>

Simple UDP Server

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <netdb.h>
#include <unistd.h>
#include <errno.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <arpa/inet.h>

extern int h_errno;

void error(const char *msg);

int UdpSocket(int protocol)
{
 int sockfd;

    sockfd = socket(AF_INET, SOCK_DGRAM, 0);
 if (-1 == sockfd)
 {
  error(__func__);
 }
 return sockfd;
}


void error(const char *msg)
{
 printf("Error Code: %d", errno);
 perror(msg);
}


int BindSocketToAddr(int sock, struct sockaddr_in *addr, int port)
{
 int rc;

    if (!addr)
    {
        printf("%s: NULL pointer in addr\n", __func__);
        return -1;
    }
 bzero(addr, sizeof(struct sockaddr_in));
 addr->sin_family = AF_INET;
 addr->sin_addr.s_addr = INADDR_ANY;
 addr->sin_port = htons(port);
 rc = bind(sock, (struct sockaddr *)addr, sizeof(struct sockaddr));
 if (rc < 0)
 {
  perror(__func__);
 }
    return rc;
}



int main(int argc, char **argv)
{
 int sockfd;
 struct sockaddr_in fromSockAddr;
 struct sockaddr_in serverSockAddr;
 socklen_t fromlen;
 char buf[1024];
 char fromAddrStr[512];
 int n;

    if (argc < 2)
    {
        printf("\n%s <PORT NUMBER>\n\n", argv[0]);
        exit(0);
    }
    setuid(0);

 printf("UDP Server\n");

 sockfd = UdpSocket(0);
 if (sockfd > 0)
 {
  BindSocketToAddr(sockfd, &serverSockAddr, atoi(argv[1]));
  fromlen = sizeof(fromSockAddr);
  while (1) {
   /* wait for client to send a message */
   n = recvfrom(sockfd, buf, sizeof(buf), 0, (struct sockaddr *)&fromSockAddr, &fromlen);
   if (n < 0)
   {
    error("recvfrom");
    break;
   }
   else {
    inet_ntop(fromSockAddr.sin_family, &fromSockAddr.sin_addr, fromAddrStr, sizeof(fromAddrStr));
    printf("GOT msg from: %s\n", fromAddrStr);
    /* echo back */
    n = sendto(sockfd, buf, n, 0, (struct sockaddr *)&fromSockAddr, sizeof(fromSockAddr));
    if (n < 0)
    {
     error("sendto");
     break;
    }
   }
  }
 }
 return 0;
}

Saturday, February 4, 2012

Intro to Ruby

Just got my hands dirty with Ruby today. It's an interesting language, yet simple to learn. Unlike some other dynamic programming languages that too cryptic to learn, Ruby is easy to learn, similar to Tcl.

Here's an example of a program I tested:

#!/usr/bin/ruby

presidents = ["Ford", "Carter", "Reagan", "Bush1", "Clinton", "Bush2", "Obama"]

for fwd in [-1,1]
    if fwd == 1 
        print "Forward/ascending\n"
        dec = 0
    else
        print "Backward/descending\n"
        dec = -1
    end
    for ss in 0...presidents.length
        print ss+1, ": ", presidents[ss*fwd+dec], "\n";
    end
end

The output:

Backward/descending
1: Obama
2: Bush2
3: Clinton
4: Bush1
5: Reagan
6: Carter
7: Ford
Forward/ascending
1: Ford
2: Carter
3: Reagan
4: Bush1
5: Clinton
6: Bush2
7: Obama

Sunday, November 6, 2011

TinyXML

#include <ltinyxml.h>

// ----------------------------------------------------------------------
// STDOUT dump and indenting utility functions
// ----------------------------------------------------------------------
const unsigned int NUM_INDENTS_PER_SPACE=2;

const char * getIndent( unsigned int numIndents )
{
 static const char * pINDENT="                                      + ";
 static const unsigned int LENGTH=strlen( pINDENT );
 unsigned int n=numIndents*NUM_INDENTS_PER_SPACE;
 if ( n > LENGTH ) n = LENGTH;
 
 return &pINDENT[ LENGTH-n ];
}

// same as getIndent but no "+" at the end
const char * getIndentAlt( unsigned int numIndents )
{
 static const char * pINDENT="                                        ";
 static const unsigned int LENGTH=strlen( pINDENT );
 unsigned int n=numIndents*NUM_INDENTS_PER_SPACE;
 if ( n > LENGTH ) n = LENGTH;
 
 return &pINDENT[ LENGTH-n ];
}

int dump_attribs_to_stdout(TiXmlElement* pElement, unsigned int indent)
{
 if ( !pElement ) return 0;
 
 TiXmlAttribute* pAttrib=pElement->FirstAttribute();
 int i=0;
 int ival;
 double dval;
 const char* pIndent=getIndent(indent);
 printf("\n");
 while (pAttrib)
 {
  printf( "%s%s: value=[%s]", pIndent, pAttrib->Name(), pAttrib->Value());
  
  if (pAttrib->QueryIntValue(&ival)==TIXML_SUCCESS)    printf( " int=%d", ival);
  if (pAttrib->QueryDoubleValue(&dval)==TIXML_SUCCESS) printf( " d=%1.1f", dval);
  printf( "\n" );
  i++;
  pAttrib=pAttrib->Next();
 }
 return i;
}

void dump_to_stdout( TiXmlNode* pParent, unsigned int indent = 0 )
{
 if ( !pParent ) return;
 
 TiXmlNode* pChild;
 TiXmlText* pText;
 int t = pParent->Type();
 printf( "%s", getIndent(indent));
 int num;
 
 switch ( t )
 {
  case TiXmlNode::TINYXML_DOCUMENT:
   printf( "Document" );
   break;
   
  case TiXmlNode::TINYXML_ELEMENT:
   printf( "Element [%s]", pParent->Value() );
   num=dump_attribs_to_stdout(pParent->ToElement(), indent+1);
   switch(num)
   {
    case 0:  printf( " (No attributes)"); break;
    case 1:  printf( "%s1 attribute", getIndentAlt(indent)); break;
    default: printf( "%s%d attributes", getIndentAlt(indent), num); break;
   }
   break;
   
    case TiXmlNode::TINYXML_COMMENT:
     printf( "Comment: [%s]", pParent->Value());
     break;
     
    case TiXmlNode::TINYXML_UNKNOWN:
     printf( "Unknown" );
     break;
     
    case TiXmlNode::TINYXML_TEXT:
     pText = pParent->ToText();
     printf( "Text: [%s]", pText->Value() );
     break;
     
    case TiXmlNode::TINYXML_DECLARATION:
     printf( "Declaration" );
     break;
    default:
     break;
 }
 printf( "\n" );
 for ( pChild = pParent->FirstChild(); pChild != 0; pChild = pChild->NextSibling())
 {
  dump_to_stdout( pChild, indent+1 );
 }
}

// load the named file and dump its structure to STDOUT
void dump_to_stdout(const char* pFilename)
{
 TiXmlDocument doc(pFilename);
 bool loadOkay = doc.LoadFile();
 if (loadOkay)
 {
  printf("\n%s:\n", pFilename);
  dump_to_stdout( &doc ); // defined later in the tutorial
 }
 else
 {
  printf("Failed to load file \"%s\"\n", pFilename);
 }
}


void build_simple_doc( )
{
 // Make xml: World
 TiXmlDocument doc;

 TiXmlDeclaration * declaration = new TiXmlDeclaration( "1.0", "UTF-8", "" );
 TiXmlElement * root = new TiXmlElement( "mipsdiag" );

 doc.LinkEndChild( declaration );
 doc.LinkEndChild( root );

 TiXmlElement * cpu = new TiXmlElement( "cpu" );
 root->LinkEndChild(cpu);
 
 TiXmlComment * comment = new TiXmlComment();
 comment->SetValue("-- CPU utilization --" );
 cpu->LinkEndChild(comment);

 TiXmlElement *cpu_res = new TiXmlElement("cpu_resouce");
 cpu_res->SetAttribute("type", "utilization");
 cpu_res->SetAttribute("units", "percent");
 cpu->LinkEndChild(cpu_res);

 TiXmlText *cpu_utilization = new TiXmlText("0.11");
 cpu_res->LinkEndChild(cpu_utilization);

 dump_to_stdout( &doc );
 doc.SaveFile( "mipsdiag.xml" );
}


int main()
{
 build_simple_doc();
}

Tuesday, October 18, 2011

Ooma has dialtone, but unable to make calls

There might be a bug in Old Ooma Broadband Voip device which for some reason could not establish voice connection (although it could connect to Ooma gateway and we could hear its unique dialtone).

To fix it is actually very simple, just unplug the power to it and leave it like that for about 15 seconds, and than replug it

iTunes fails to upgrade iPad with error 1611

This issue was due to SIM card.

Try remove the SIM card while doing upgrade. Once the upgrade is complete, we can reinsert the SIM card.

Monday, September 5, 2011

Recover file name copied from iPod/iPhone

With gtkPod, we are able to connect to iPhone/iPod and copy all the files, but the filenames are all cryptic (they are all in four letters). With the following script, we can recover the file names and convert them into readable format in the form of "artist - album" pattern.

#!/bin/sh
FULLPATH=$1
FILE=${FULLPATH##*/}
FILENAME=${FILE%.*}
EXT=${FILE##*.}
#echo "FILENAME=$FILENAME"
#echo "EXTension=$EXT"
shift
OPTS=$@
echo filename=$FILENAME

meta=`mp4info "$FULLPATH" | awk '/Metadata / {sub(/^[ \t]+/, "")};1'`
#echo meta=$meta
TITLE=`echo "$meta" | awk '/Metadata Name: / {gsub(/Metadata Name: /,""); print }'`
ARTIST=`echo "$meta" | awk '/Metadata Artist: / {gsub(/Metadata Artist: /,""); print }'`

if [ -z "$TITLE" ]
then
 TITLE="unknown"
else
 echo TITLE=$TITLE
fi

if [ -z "$ARTIST" ]
then
 ARTIST="unknown"
else
 echo ARTIST=$ARTIST
fi

TARGET="$ARTIST - $TITLE.$EXT"
cp "$FULLPATH" "$TARGET"

if [ -n $ "$TARGET" ]
then
 rm "$FULLPATH"
fi

Save the above script into an executable file, say mp4fixname.

To fix a filename, just run it and pass the encoded filename.
For example, if the file name is NXJA.m4a, we just run the script as below:

mp4fixname NXJA.m4a

The original filename will be replaced in artist and song name format according to metadata/tags stored in the original file.

Converting m4a song to mp3 format

Sometimes, I need to convert files I bought from iTunes to MP3 format. Well, actually not all songs we buy convertable to MP3. Only non-DRM format (with m4a extension) can be converted. The protected format with m4p extension still cannot be converted, theoritically at least (there is a hack to remove the DRM. But that's not easy and won't be covered here).

The following script converts an MP4 file to MP3 format.
It copies all the tags stored in the original file into the target file.
Make sure you have ffmpeg, mp4info, awk, and bc installed.

#!/bin/bash

#!/bin/bash

FULLPATH=$1
file=${FULLPATH##*/}
FILENAME=${file%.*}
EXT=${file##*.}
#echo "FILENAME=$FILENAME"
#echo "EXTension=$EXT"
shift
OPTS=$@

if [ `echo $EXT | tr [:upper:] [:lower:]` = "m4a" ]
then
 bitratekbps=`mp4info "$FULLPATH" | awk '$1 ~ /([0-9]+) kbps/g {print $8}'`
 bitratebps=`echo "scale=10; $bitratekbps*1000" | bc -l`
 hz=`mp4info "$FULLPATH" | awk '$1 ~ /([0-9]+) kbps/g {print $10}'`

 ffmpeg -i "$FILENAME.m4a" -aq 1 -ab $bitratebps -ar $hz -f mp3 \
        -metadata major_brand="MP3" \
         -metadata compatible_brands="MP3 libmp3lame" \
        "$FILENAME.mp3" $OPTS
fi

Save the file, say, to m4a2mp3 and make it executable.

To convert a song:

m4a2mp3 song.m4a

The target file name is the same, except the extension now is MP3. Also, some tags/metadata are replaced to reflect the new format. If you want to add other options, you can put that after file name. For example: m4a2mp3 song.m4a -metadata mymeta="converted from m4a"

Monday, August 8, 2011

Assembly in Linux

section .data
    hello:     db 'Hello world!',10    ; 'Hello world!' plus a linefeed character
    helloLen:  equ $-hello             ; Length of the 'Hello world!' string

section .text
    global _start

    _start:
    mov ecx,5            ; display the string 5 times

_loop:
    mov eax,4            ; The system call for write (sys_write)
    mov ebx,1            ; File descriptor 1 - standard output
    push ecx             ; save ecx as it is gonna be used as param to sys_write
    mov ecx,hello        ; Put the offset of hello in ecx
    mov edx,helloLen     ; helloLen is a constant, so we don't need to say
                         ;  mov edx,[helloLen] to get it's actual value
    int 80h              ; Call the kernel
    pop ecx              ; restore ecx (counter)
    loop _loop
    mov eax,1            ; The system call for exit (sys_exit)
    mov ebx,0            ; Exit with return code of 0 (no error)
    int 80h


Steps:
Save the file as syscall.asm  
Execute: nasm -f elf syscall.asm  
Execute: ld -s -o syscall syscall.o  
run it as: ./syscall   
To check the object file, we can use objdump, elfdump, or readelf. For example:  


$ readelf -a ./syscall.o
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x0
  Start of program headers:          0 (bytes into file)
  Start of section headers:          64 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0
  Size of section headers:           40 (bytes)
  Number of section headers:         7
  Section header string table index: 3

Section Headers:
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al

  [ 0]                   NULL            00000000 000000 000000 00      0   0  0

  [ 1] .data             PROGBITS        00000000 000160 00000d 00  WA  0   0  4

  [ 2] .text             PROGBITS        00000000 000170 00002b 00  AX  0   0 16

  [ 3] .shstrtab         STRTAB          00000000 0001a0 000031 00      0   0  1

  [ 4] .symtab           SYMTAB          00000000 0001e0 000080 10      5   7  4

  [ 5] .strtab           STRTAB          00000000 000260 000029 00      0   0  1

  [ 6] .rel.text         REL             00000000 000290 000008 08      4   2  4
$ readelf -a ./syscall.o
ELF Header:s:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF32unknown)
  Data:                              2's complement, little endianpecific)
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              REL (Relocatable file)
  Machine:                           Intel 80386
  Version:                           0x1 0x290 contains 1 entries:
  Entry point address:               0x0Value  Sym. Name
  Start of program headers:          0 (bytes into file)
  Start of section headers:          64 (bytes into file)
  Flags:                             0x0e.
  Size of this header:               52 (bytes)
  Size of program headers:           0 (bytes)
  Number of program headers:         0Vis      Ndx Name
  Size of section headers:           40 (bytes)UND
  Number of section headers:         7DEFAULT  ABS syscall.asm
  Section header string table index: 3DEFAULT    1
     3: 00000000     0 SECTION LOCAL  DEFAULT    2
Section Headers:     0 NOTYPE  LOCAL  DEFAULT    1 hello
  [Nr] Name              Type            Addr     Off    Size   ES Flg Lk Inf Al
  [ 0]                   NULL            00000000 000000 000000 00      0   0  0
  [ 1] .data             PROGBITS        00000000 000160 00000d 00  WA  0   0  4
  [ 2] .text             PROGBITS        00000000 000170 00002b 00  AX  0   0 16
  [ 3] .shstrtab         STRTAB          00000000 0001a0 000031 00      0   0  1
  [ 4] .symtab           SYMTAB          00000000 0001e0 000080 10      5   7  4
  [ 5] .strtab           STRTAB          00000000 000260 000029 00      0   0  1
  [ 6] .rel.text         REL             00000000 000290 000008 08      4   2  4
Key to Flags:
  W (write), A (alloc), X (execute), M (merge), S (strings)
  I (info), L (link order), G (group), x (unknown)
  O (extra OS processing required) o (OS specific), p (processor specific)

There are no section groups in this file.

There are no program headers in this file.

Relocation section '.rel.text' at offset 0x290 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00000011  00000201 R_386_32          00000000   .data

There are no unwind sections in this file.

Symbol table '.symtab' contains 8 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND
     1: 00000000     0 FILE    LOCAL  DEFAULT  ABS syscall.asm
     2: 00000000     0 SECTION LOCAL  DEFAULT    1
     3: 00000000     0 SECTION LOCAL  DEFAULT    2
     4: 00000000     0 NOTYPE  LOCAL  DEFAULT    1 hello
     5: 0000000d     0 NOTYPE  LOCAL  DEFAULT  ABS helloLen
     6: 00000005     0 NOTYPE  LOCAL  DEFAULT    2 _loop
     7: 00000000     0 NOTYPE  GLOBAL DEFAULT    2 _start

No version information found in this file.

Tuesday, July 5, 2011

Relacing OpenJDK with Oracle/Sun Java SDK as default java

According to some sources, Sun/Oracle JDK or JRE is slightly faster than OpenJDK. To install the SunJDK without removing the OpenJDK is as follow:

Download the SDK from here
Install the SDK. For example: sudo rpm -Uvih <sdk rpmfile> or sudo sh ./<sdk bin file>
Once it is installed, copy-paste the following script and execute it

#!/bin/sh

for FP in /usr/java/default/bin/* ; do
   NAME=${FP##*/}
   echo installing $NAME
   sudo alternatives --install /usr/bin/${NAME} ${NAME} /usr/java/default/bin/${NAME} 20000
   alternatives --display "${NAME}" | grep "${NAME}"
done

Sunday, June 12, 2011

New Nook v.s. Amazon Kindle

Today I went to Barnes & Noble store and attracted with a Nook display. Coincidentally, I was also carrying my Kindle with me, so now I have a chance to compare it visually. First of all, the overall physical size of the new Nook is smaller than Kindle, because it has got rid of physical keyboard. Instead, a visual keyboard would be displayed whenever needed. As you might have known, this new Nook is now equipped with touch screen and I guess it is capacitive touch screen as it is very responsive. The screen area is actually about the same as Kindle's screen.

For the resolution, Kindle is tad better. This is based on my visual check by starring at each screen very closely (I got to remove my glasses to get better visual). Letters on Kindle are darker and smoother (but not much better), but Nook screen is whiter. Screen refresh rate (refresh between page) is faster on the Nook. Page buttons are located the same as Kindle (page-up and page-down are on left and right edge of the body). For the weight, I guess Kindle is slightly lighter on my hand, but it's hard to make a correct and accurate judgment without put them on scale.

Something interesting is the power life. Nook is apparently is the winner, at least according to the sales person. It can last up to 2 months with Wi-Fi turned off, while on Kindle is about a month. Price wise, Kindle is a bit cheaper, especially if we're OK with ads-supplied screen-saver version of it. On Amazon website, the ads-supported version is $114 (with no sales tax if we buy from California, and no shipping cost), while the Nook is $139 + sales tax. The web browser on Nook is better.

For the collection of books available, Amazon seems has little bit more selection, but B&N is catching up quickly too. A feature that's not available on Kindle is "Rent" and "Read in store", and this would make Nook very appealing for some users who want to borrow a book from friend or just want to read a book in B&N store (although not all e-books can be read or rented). I hope Amazon will match it with the similar offering. Nook is also EPUB-compatible reader, while Amazon's Kindle uses a proprietary format (Mobile-pocket-based MOBI format with DRM added). While many books can be converted with a tool such as Calibre (EPUB to MOBI and vice versa), others are nonconvertible.

Internally, they both are based on Linux, although Nook is Android-base. No surprise the Nook is faster because it uses more recent hardware, while Kindle has been a year old in the market. I think Amazon is preparing a next gen one. Just wait and see a couple of months as rumors say the will introduce the new one. The rumor also says Kindle might have a touch screen too (some people in the internet forum wish Amazon not to arm it with a touch screen. I don't understand what's the reason behind it yet).

Overall, I guess they tie in many comparisons. Only our preferences can tell which one to buy. If I haven't had Kindle, I might buy this new Nook because it's cute (very portable and almost fit in my shirt pocket) and has some features not available on Kindle.

=-=-=-=-=
Powered by Blogilo

Thursday, June 9, 2011

Fedora 15 & GNOME 3 Crash.

Some PCs have issues when installed with Fedora 15 and GNOME 3 as its desktop manager. On my Compaq Presario R3000 labptop, I was unable to login due to crash in subsystem (gnome-shell). When I tried to login, it display a message something like "unrecovered ...".

The problem is that GNOME3 is not stable enough to be run on some machines/video cards with 3D (perhaps Nouveau driver unable to execute 100% of the required GNOME3 features?). Some people in the Internet said that by executing the following command it should fix the issue, but not in my case:

gsettings set org.gnome.desktop.session session-name gnome-fallback

After googling around, I found a good solution:

sudo rpm --nodeps -e gnome-shell 

This has fixed my GNOME problem. I could now login to the fallback mode (GNOME2-like)

Wednesday, May 25, 2011

PlayList format and translation

Sandisk Sansa mp3 player may have playlists of mp3 files. These files are stored in \PLAYLIST.
The format of playlist is actullay in UTF-16LE. In order to translate it to an ASCII (UTF-8) format, we can use a command line tool in Unix/Linux (available in Cygwin for Windows too).

Here's an example how to convert a playlist to a text format:

bash-3.2$ iconv -f UTF-16LE -t UTF-8 playlist.pla
PLP PLAYLIST
VERSION 1.20

HARP, MUSIC\James Blunt\All The Lost Souls\10_-_i_can't_hear_the_music_-_all_the_lost_souls.mp3
HARP, MUSIC\James Blunt\All The Lost Souls\09_-_annie_-_all_the_lost_souls.mp3
HARP, MUSIC\James Blunt\All The Lost Souls\04_-_same_mistake_-_all_the_lost_souls.mp3
HARP, MUSIC\James Blunt\All The Lost Souls\01_-_1973_-_all_the_lost_souls.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd1\01_-_bohemian_rhapsody_-_queen_-_greatest_hits_cd1.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd1\05_-_bicycle_race_-_queen_-_greatest_hits_cd1.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd1\16_-_we_will_rock_you_-_queen_-_greatest_hits_cd1.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd1\17_-_we_are_the_champions_-_queen_-_greatest_hits_cd1.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd2\07_-_it's_a_hard_life_-_queen_-_greatest_hits_cd2.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd2\11_-_the_miracle_-_queen_-_greatest_hits_cd2.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd2\15_-_friends_will_be_friends_-_queen_-_greatest_hits_cd2.mp3
HARP, MUSIC\Queen\Queen - Greatest Hits Cd2\16_-_the_show_must_go_on_-_queen_-_greatest_hits_cd2.mp3
HARP, MUSIC\Eric Clapton\Unplugged\07_-_layla_-_unplugged.mp3
HARP, MUSIC\Rihanna\Good Girl Gone Bad\{1]03_-_don't_stop_the_music_-_good_girl_gone_bad.mp3
HARP, MUSIC\OneRepublic\Dreaming Out Loud\{1]03_-_stop_and_stare_-_dreaming_out_loud.mp3
HARP, MUSIC\Colbie Caillat\Coco\{1]07_-_realize_-_coco.mp3
HARP, MUSIC\Timbaland\Shock Value\{1]16_-_apologize_(feat._one_republic)_-_shock_value.mp3
HARP, MUSIC\Ennio Morricone\Kill Bill Vol.2\03_-_il_tramanto_-_kill_bill_vol.2.mp3
HARP, MUSIC\Charlie Feathers\Kill Bill Vol.2\04_-_cant_hardly_stand_it_-_kill_bill_vol.2.mp3
HARP, MUSIC\Lole Y Manuel\Kill Bill Vol.2\05_-_tu_mira_(edit)_-_kill_bill_vol.2.mp3
HARP, MUSIC\Luis Bacalov\Kill Bill Vol.2\06_-_summertime_killer_-_kill_bill_vol.2.mp3
HARP, MUSIC\Alan Reeves Phil Steele And P\Kill Bill Vol.2\07_-_the_chase_-_kill_bill_vol.2.mp3
HARP, MUSIC\Ennio Morricone\Kill Bill Vol.2\09_-_l_arena_-_kill_bill_vol.2.mp3
HARP, MUSIC\Malcolm Mclaren\Kill Bill Vol.2\12_-_about_her_-_kill_bill_vol.2.mp3
HARP, MUSIC\Chingon\Kill Bill Vol.2\14_-_malaguena_salerosa_-_kill_bill_vol.2.mp3
HARP, MUSIC\Meiko Kaji\Kill Bill Vol.2\15_-_urami_bushi_-_kill_bill_vol.2.mp3
bash-3.2$

To create a playlist, we just reverse the format and redirect the output to a file (with extension pla) and then copy the generated file to Sansa's PLAYLIST folder. Just to remember, the path of each file is relative to MUSIC folder.

Tuesday, May 24, 2011

Script to find latitude and longitude

The following script utilize Yahoo geocode API to find longitude and langitude of any location.

#!/bin/sh

converter="http://api.maps.yahoo.com/ajax/geocode?appid=onestep&qt=1&id=m&qs="

addr="$(echo $1 | sed 's/ /+/g')"
values="$(curl -s $converter$addr | cut -d\" -f13,15 |sed 's/[^0-9\.\,\-]//g; s/,$//')"

lat1=$(echo $values | cut -d, -f1)
long1=$(echo $values | cut -d, -f2)

echo "Lat=$lat1"
echo "Long=$long1"

(Save the above script to file and chmod to be executable).
For example:

>latlong 1465 mcdowell blvd, petaluma ca 94954
Lat=-33.869629
Long=151.206955

>latlong jakarta, indonesia

Lat=-6.17144

Long=106.82782

Tuesday, May 3, 2011

iMac v.s. AsusTek All-in-One PC

AsusTek All-in-One PC:

Price: $1,719.26 at 2020pc.com (free shipping + no tax)

General
Type	Personal computer
Product Form Factor	All-in-one
Built-in Devices	Touch screen
Width	22.9 in
Depth	2 in
Height	19.5 in
Weight	28.7 lbs
Color	Black
Bundled with	3D glasses
Processor
Type	Intel Core i7 740QM / 1.73 GHz
Multi-Core Technology	Quad-Core
64-bit Computing	Yes
Installed Qty	1
Max Supported Qty	1
Mainboard
Chipset Type	Mobile Intel HM55 Express
RAM
Installed Size	8 GB / 8 GB (max)
Technology	DDR3 SDRAM
Memory Speed	1333 MHz
Form Factor	SO DIMM 204-pin
Configuration Features	4 x 2 GB
Storage Controller
Type	1 x Serial ATA - integrated
Controller Interface Type	Serial ATA-300
Storage
Hard Drive	1 x 1 TB - standard - Serial ATA-300 - 7200 rpm
Optical Storage
Type	DVD-Writer / BD-ROM
Card Reader
Type	Card reader
Supported Flash Memory Cards	SD Memory Card, SDXC Memory Card
Monitor
Monitor Type	LCD display - 3D Ready - TFT active matrix - Multi-Touch
Diagonal Size	23.6"
Max Resolution	1920 x 1080 ( Full HD )
Widescreen Display	Yes
Image Aspect Ratio	16:9
Graphics Controller
Type	Plug-in card
Graphics Processor / Vendor	NVIDIA GeForce GTX 460M
Video Memory	1.5 GB
Digital Video Standard	High-Definition Multimedia Interface (HDMI)
Multimedia Functionality
TV Tuner Type	Digital TV
Digital TV Reception	ATSC
Audio Output
Type	Sound card
Sound Output Mode	Stereo
Camera
Form Factor	Integrated
Sensor Resolution	1.3 Megapixel
Input Device
Type	Mouse, keyboard
Keyboard
Connectivity	Wireless
Mouse
Connectivity	Wireless
Audio Input
Type	Microphone
Networking
Networking	Network adapter
Wireless LAN Supported	Yes
Data Link Protocol	Ethernet, Fast Ethernet, Gigabit Ethernet, IEEE 802.11b, IEEE 802.11g, IEEE 802.11n, Bluetooth 3.0
Compliant Standards	IEEE 802.11b, IEEE 802.11g, IEEE 802.11n, Bluetooth 3.0
Expansion / Connectivity
Expansion Bays Total (Free)	Internal - 3.5"
Expansion Slots Total (Free)	1 ( 0 ) x processor 4 ( 0 ) x memory - SO DIMM 204-pin
Interfaces	4 x Hi-Speed USB - 4 pin USB Type A 1 x network - Ethernet 10Base-T/100Base-TX/1000Base-T - RJ-45 2 x SuperSpeed USB - 9 pin USB Type A 1 x microphone - input - mini-phone 3.5 mm 1 x headphones - output - mini-phone stereo 3.5 mm 1 x display / video - VGA input - 15 pin HD D-Sub (HD-15) 1 x audio / video - HDMI - 19 pin HDMI Type A 1 x display / video - TV-in
Miscellaneous
Included Accessories	Remote control
Features	ASUS Super Hybrid Engine, ASUS SonicMaster
Power
Device Type	Power adapter
Power Provided	230 Watt
Operating System / Software
OS Provided	Microsoft Windows 7 Home Premium 64-bit Edition
Microsoft Office Preloaded	Includes a pre-loaded image of select Microsoft Office 2010 suites. Purchase an Office 2010 Product Key Card or disc to activate preloaded software on this PC.
Environmental Standards
ENERGY STAR Qualified	Yes
Manufacturer Warranty
Service & Support	1 year warranty
Service & Support Details	Limited warranty - 1 year
Universal Product Identifiers
Brand	ASUSTeK COMPUTER
Part Number	ET2400XVT-B011E
GTIN	00610839324255

Advantage: USB-3

21.5-inch iMac

$1,899.00 at Apple Store/online (free shipping, but there's sales tax)
$100 discount for students

21.5-inch iMac

Ships: 1-3 business days
Part number: Z0M5

Configuration

2.8GHz Quad-Core Intel Core i7
8GB 1333MHz DDR3 SDRAM - 2x4GB
1TB Serial ATA Drive
AMD Radeon HD 6770M 512MB GDDR5

Apple Magic Mouse
Apple Wireless Keyboard (English) & User's Guide
Accessory Kit

Advantage: Thunderbolt connection (10 Gbps)

At the end, almost-apple-to-apple comparison (for students) is: 1799+167.11% (CA sales tax) - 1719.25 = 1966.11 - about $250 difference (that's more than the cost for 2 TB USB-3.0 external Hard Drive )

Sunday, March 27, 2011

NVIDIA Legacy 96.43.xx with Linux Kernel 2.6.37 or newer

The NVIDIA driver below proven to work with Linux kernel 2.6.37:

ftp://download.nvidia.com/XFree86/Linux-x86/96.43.19/

Just run and install the *-pkg1.run

Saturday, March 26, 2011

Binary-tree test

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <time.h>

/* 
 Helper function that allocates a new node with the given data and NULL left and right pointers. 
*/ 


typedef struct node {
 int data;
 struct node *left;
 struct node *right;
} NodeT;


NodeT* NewNode(int data);
void BTreeLog(const char *fmt, ...);

typedef int (*BTreeCompFunc)(NodeT* node, void *data);

NodeT* BTreeNewNode(int data) 
{ 
 NodeT* node = (NodeT*)malloc(sizeof(NodeT));    // "new" is like "malloc" 
 node->data = data; 
 node->left = NULL; 
 node->right = NULL;
 BTreeLog("BTreeNewNode: new node=0x%X, data=%d\n", node, data);
    return(node); 
} 
     

void BTreeLog(const char *fmt, ...)
{
#ifdef __ENABLE_LOG__  
 char buf[256];
 va_list ap;
 int n;
 
 va_start(ap, fmt);
 n = vsnprintf(buf, sizeof(buf), fmt, ap);
 printf("%s", buf);
 va_end(ap);
#endif 
}


int BTreeCompare(NodeT* node, void *data)
{
 if (*((int*)data) < node->data)
  return -1;
 if (*((int*)data) > node->data)
  return 1;
 return 0;
}  
/* 
  Give a binary search tree and a number, BTreeInserts a new node 
  with the given number in the correct place in the tree. 
  Returns the new root pointer which the caller should 
  then use (the standard trick to avoid using reference 
  parameters). 
*/ 

NodeT* BTreeInsert(NodeT* node, int data, BTreeCompFunc comp)
{ 
 // 1. If the tree is empty, return a new, single node 
 if (NULL == node) 
 { 
  BTreeLog("New Entry: %d\n", data);
  return BTreeNewNode(data); 
    } 
 else { 
  // 2. Otherwise, recur down the tree 
     if (comp(node, &data) == -1) {
   /*BTreeLog("BTreeInsert: left; data=%d, node=0x%X, left=0x%X, right=0x%X\n", 
       data, node, node->left, node->right);
   */    
   node->left = BTreeInsert(node->left, data, comp); 
  } 
  else {
   /* 
   BTreeLog("BTreeInsert: right; data=%d, node=0x%X, left=0x%X, right=0x%X\n", 
       data, node, node->left, node->right);
   */    
   node->right = BTreeInsert(node->right, data, comp);
  } 
 }
 return(node); // return the (unchanged) node pointer 
}


void BTreeDeleteAll(NodeT* pNode)
{
 if (pNode)
 {
  if (pNode->left)
  {
   BTreeDeleteAll(pNode->left);
  } 
  if (pNode->right)
  {
   BTreeDeleteAll(pNode->right);
  } 
  BTreeLog("BTreeDeleteAll: pNode=0x%X, data=%d\n", pNode, pNode->data);
  free(pNode);
  //pNode->left = NULL;
  //pNode->right = NULL;
 }
}

NodeT *BTreeSearch(NodeT* pNode, int data, BTreeCompFunc comp)
{
 int cmp; 
 if (pNode) {
  cmp = comp(pNode, &data); 
  if (cmp == 0)
   return pNode;
  else 
  if (cmp == -1)
  {
   /* data < pnode->data */
   pNode = BTreeSearch(pNode->left, data, comp); 
  }
  else {
   pNode = BTreeSearch(pNode->right, data, comp);
  } 
 }
 //BTreeLog("Comp...\n");
 return pNode;
}


int main(int argc, char *argv[])
{
 NodeT* root = NULL;
 NodeT* node;
 unsigned int n,i;
 int data1, data2;
 unsigned int count;

 srand(time(NULL));
 BTreeLog("BTree demo\n");
 n = rand() % 100;
 root = BTreeInsert(root, n, BTreeCompare);
 data2 = 4750;
 n = 10000000;
 for (i=0, count=0; i<n; i++)
 {
  data1 = rand()%n;
  /* insert unique entry */
  if (BTreeSearch(root, data1, BTreeCompare) == NULL) {
   BTreeInsert(root, data1, BTreeCompare);
   count++;
  } 
 }
 BTreeInsert(root, data2, BTreeCompare);
 printf("Just inserted %d entries into Binary-tree\n", count+1);
 node = BTreeSearch(root, data2, BTreeCompare);
 printf("\n\n\n\n");
 if (node) {
  printf("!!!!!!!!!!!!!!!!!!!!!!!!Found node=0x%X for data=%d\n", node, data2);
 }
 printf("\n\n\n\n");
 BTreeDeleteAll(root);
}

Wednesday, March 23, 2011

Linux Init

LINUX INIT
--------------
This is the mother of all other userspace's processes.

Where to find it?
In the util-linux package (to be found at ftp.*.kernel.org) for simpleinit or in the sysvinit package for SysV init.

Probably also in [sunsite|metalab].unc.edu or ftp.debian.org

Title: sysvinit and utilities
Version: 2.78
Entered-Date: 11FEB2000
Description: This is the Linux System V init.
   The source package has the debian build files included.
   This version can be compiled with glibc 2.0.6 and up.
Author: miquels@cistron.nl (Miquel van Smoorenburg)
Primary-Site: sunsite.unc.edu /pub/Linux/system/daemons/init
   109K sysvinit-2.78.tar.gz
Alternate-Site: ftp.cistron.nl /pub/people/miquels/software
   109K sysvinit-2.78.tar.gz
Alternate-Site: ftp.debian.org /debian/dists/potato/main/source/base
   108K sysvinit_2.78-X.tar.gz
Copying-Policy: GPL
Keywords: init shutdown halt reboot
End

ftp.debian.org:/debian/dists/potato/main/source/base/sysvinit_2.78-2.tar.gz

https://build.opensuse.org/package/files?package=sysvinit&project=YaST%3AWeb

Some properties:

#define VT_MASTER "/dev/tty0" /* Virtual console master */
#define CONSOLE "/dev/console" /* Logical system console */
#define SECURETTY "/etc/securetty" /* List of root terminals */
#define SDALLOW "/etc/shutdown.allow" /* Users allowed to shutdown */
#define INITTAB "/etc/inittab" /* Location of inittab */
#define INIT "/sbin/init" /* Location of init itself. */
#define NOLOGIN "/etc/nologin" /* Stop user logging in. */
#define FASTBOOT "/fastboot" /* Enable fast boot. */
#define FORCEFSCK "/forcefsck" /* Force fsck on boot */
#define SDPID "/var/run/shutdown.pid" /* PID of shutdown program */
#define SHELL "/bin/sh" /* Default shell */
#define SULOGIN "/sbin/sulogin" /* Sulogin */
#define INITSCRIPT "/etc/initscript" /* Initscript. */
#define PWRSTAT_OLD "/etc/powerstatus" /* COMPAT: SIGPWR reason (OK/BAD) */
#define PWRSTAT "/var/run/powerstatus" /* COMPAT: SIGPWR reason (OK/BAD) */

#if 0
#define INITLVL "/etc/initrunlvl" /* COMPAT: New runlevel */
#define INITLVL2 "/var/log/initrunlvl" /* COMPAT: New runlevel */
/* Note: INITLVL2 definition needs INITLVL */
#define HALTSCRIPT1 "/etc/init.d/halt" /* Called by "fast" shutdown */
#define HALTSCRIPT2 "/etc/rc.d/rc.0" /* Called by "fast" shutdown */
#define REBOOTSCRIPT1 "/etc/init.d/reboot" /* Ditto. */
#define REBOOTSCRIPT2 "/etc/rc.d/rc.6" /* Ditto. */

- It exits if UID is != 0 (root)
- It exits if PID != 1 (the first process in Kernel's userspace)
- It check command-line args:
   "single", "-s" : dfl_level is set to 'S'
   "-a", "auto" : set environment "AUTOBOOT=YES"
   "-b", "emergency" : emerg_shell = 1
   "-z" : ignore -z xxxx
   any of [0-9],[sS] : dfl_level is set accordingly to that level

- set default environment PATH to "/sbin:/usr/sbin:/bin:/usr/bin"
- say "@(#) init version 2.89 DATE 26-Mar-2010 miquels@cistron.nl booting" into syslog
- spawn/fork to emergency shell if emerg_shell == 1
- read inittab and configure setting based on the settings stored in INITTAB

init.c: main() ---> setproctitle()
   |
   |
   V
init_main() ----------------------------> read_inittab()
| | |
| | |
| | V
| | init_reboot(BMAGIC_SOFT)
| |
| |
| V
| ioctl(f, KDSIGACCEPT, SIGWINCH): tell kernel SIGACCEPT
|
+---> set a bunch of signals' flags
|
+----> console_init(), open /dev/CONSOLE (or otherwise if specified in env "CONSOLE") for O_RDONLY
|
+----> console_stty() : Set terminal settings to reasonable defaults
|
+----> set default environment PATH to "/sbin:/usr/sbin:/bin:/usr/bin"
|
loop forever by doing this stuf:
   1) boot transitions
   2) Read from the init FIFO by calling check_init_fifo():
   2.1) try to create /dev/initctl if not present.
   2.2) If /dev/initctl is open, stat the file to see if it is still the _same_ inode
   2.3) try to open /dev/initctl
   2.4) Read data from the pipe, return on EINTR
   2.5) console_init
   2.6) process requests (e.g., runlevel change request, power fail request, set env)

   3) check the 'failing' flags
   4) process any signal:
   4.1) SIGPWR event/signal
   4.2) SIGINT
   4.3) SIGWINCH
   4.4) SIGALRM
   4.5) SIGCHLD
   4.6) SIGHUP
   5) See whether we need to start up (again)

BOOT TRANSITION FSM
--------------------

   '#' (SYSINIT) --+-----> '*' (BOOT) ------> (NORMAL)
   | ^
   | |
   newlevel=='S'| | !did_boot && newlevel != 'S'
   | |
   +-----> 'S' (INIT)
   ^
   |
   |
   start here

Thursday, March 3, 2011

Interactive map of Linux kernel

Tuesday, February 15, 2011

Are We Ready with e-Magazine?

Today Apple's Steve Jobs announced the subscription service for magazine subscription is now supported. The similar service has been available in Amazon for its Kindle for sometime. But regardless the availability, Dol we really want to read magazines on an electronic gadget?

Here's my experience using different e-readers, both on PC, iPhone, iPad and Kindle. First of all, reading magazines on iPad has the most interesting experience because its bigger footprint than iPhone and interactivity thru its touch screen. For the easiness to our eyes, Kindle prevails, but with no color as its main downside. Reading on PC's monitor is also a good experience, except it's too bulky to carry notebook during travel, let alone reading on desktop.

Another aspect we need to pay attention is the cost of subscription (and yes, this is really a turnoff, at least for me). For example, I subscribe to Reader's Digest for about $2 a year, while on Amazon they charge about $2 per edition (one magazine a year, so total subscription is about $20). A paper TIME magazine subscription, through Ad subsidy, only charge me about $15/year. Amazon charges about $2 per magazine. I bet Apple will charge about the same. It's so non-sense and doesn't make sense! Both Apple, Amazon and the publishers want to rip us off and trick us to pay so much for less! Publishing an e-Magazine costs almost nothing (99.9% of the cost is from the operational costs including the editors/writers, unlike paper-based magazines where they have to print it and distribute it).

Another issue with e-Magazine is the magazines we already one are unsharable, unless they are DRM-free. With paper magazine, we can lend the magazine to friends and let them read free-of-charge and as long as we let them borrow it. Some e-book readers have this borrow-a-book feature, but it is still limited and not convenience to use. Also, format compatibility is a big issue right now, at least between Amazon's AZW and others' EPUB (iBook uses EPUB as well as Nook and other majority of e-readers). If we buy a magazine from Amazon, it cannot be read on iPad, unless we install Kindle-for-iPad/iPhone application for it.

The only benefit of subscribing to e-Magazine right now is that it reduces clutters of magazines. A Kindle can store thousands of magazines (depends on the content. If the magazine has alot of pictures, the size will be bigger), iPad can even store much more.

So, the bottom line is that we're (or at least me) not ready to migrate to read e-magazine yet. Maybe some people can take some advantages of reading an e-magazine, but for most people it is not cost-effective yet. Once it's become so ubiquitous and ads are everywhere in the e-magazines to offset the cost, perhaps it's the time we shall migrate to this environment-friendly magazine. Oh, don't forget also by reading paper e-magazine, we support many people's live too, from workers at printing facilities, paper companies, newstand guys to truck drivers!

Android vs iOS based Tablets

Many web sites do comparison between Android-based tablets and iPad, but unfortunately almost none of them mention about one important thing: upward/downward binary-compatibility.

What does that mean? OK, we now that a software or an application is actually stored in file. On desktop operating systems (Windows, Mac, Linux etc.), these files are executable on their respective O/S, but only for specific machine.

iPad (or iPhone) Applications are actually binary applications similar the ones we find on Windows or Mac in that they contain machine instructions directly instruct each step to be taken by CPU. The instruction set is specific to the CPU it is built on (for example, iPad app cannot run on Windows or Linux, unless we have an emulator to translate the machine code on-the-fly).

The mechanism of running application is Android is slightly different. Although Android O/S kernel is based on Linux, its applications run on top of a Java virtual machine called "Dalvik". It specifies its own instruction set, outside the platform it runs on (Linux). It acts as a new realm in a realm. The benefit is that we can run Android application on any machine we like (as long as we have the Android O/S compiled and run on the specific CPU). theoritically, an application built for Android running on MIPS CPU can also run on Intel CPU so on.

Why it is important? because developers are no more tied to develop an application specific to a CPU. They can just develop once and it will run on various machines.

Saturday, February 12, 2011

Query syntax in Google Spreadsheet

I was calculating my expenses related to medical for the purpose of Tax report. All my data is recorded in a spreadsheet in Google Spreadsheet. After experimenting, I am now pleased with its formula, especially the power of query syntax (similar to SQL syntax).

Assume a spreadsheet named "2010" where it contains tax-deductible data. Row 1 cells contain title. Actual data starts from row 2 to row 419 (range is A2 to J419)

Cells in column G contains expenses related to medical. Each Cell in column J contain text, where for medical-related expense it should contain "medical" etc.

Now, to calculate the sum of all medical-related expenses, we can put the following formula somewhere in empty cell down below as:

=query('2010'!$G$2:$J$419;"select sum(G) where J contains 'edical' "; 0)

contains query is not exact-matching, so the logic is still TRUE even if we have "medical" or "Medical".

The reason I omit "m" in "medical" is to avoid case-sensitive query (I might put "Medical" instead of "medical" in my data). We can also put LOWER() function for J to force case-insensitive matching so it will still match any case of the letters, for example:

=query('2010'!$G$2:$J$419;"select sum(G) where LOWER(J) contains 'medical' "; 0)

In this case, I put the formula in another spreadsheet (that's why you see prefix '2010' there to refer to spreadsheet named "2010").

To do logical NOT, the syntax is "NOT J contains 'edical". If you want to do logical AND, put AND in front of NOT, so it will be: "NOT J contains 'medical' AND NOT J contains 'dental' "

The best so far is as below:

=ArrayFormula(IFERROR(query('2010'!$G$2:$J$419;"select sum(G) where LOWER(J) contains 'medical'"), 0))

and the next row will fill with:

=iferror(CONTINUE(B2, 2, 1))

There are many more formulas we can experiment: MATCH(), FILTER() and so on.

Tuesday, January 4, 2011

Another Interview Question

This is an interview question for software engineer position at USAA:

"A train leaves San Antonio for Houston at 60 mph. Another train leaves Houston for San Antonio at 80 mph. Houston and San Antonio are 300 miles apart. If a bird leaves San Antonio at 100 mph, and turns around and flies back once it reaches the Houston train, and continues to fly between the two, how far will it have flown when they collide?"

First, we need to draw a line to analyze this:

|<------------------------- 300 ------------------------------|
SA                                                            H
 --------60------->             <--------80 ------------------|

When these two trains collide, the distance between them is d = 0, or 60*t = 300 - 80*t, solving this equation we get t = 300/140 hours = 15/7 = 2.143 hours. Meanwhile, for the bird the equation is: 100*t = 300 - 80*t, or t = 300/180 = 1.667 hours. This is the time when the bird reaches Houston train and turns around. How far it has traveled from SA? 100*1.667 = 166.7 miles. For this duration, SA train has traveled 60*1.667 = 100.02 miles toward Houston. The distance between the bird (now flying back toward SA) and SA train is = 166.7 - 100.02 = 66.68 miles. How many minutes before the bird hits the SA train? We use the similar equation:

|<------------------------- 66.68 ------------------------------|
SA                                                            H
 --------60------->             <--------100 -------------------|

Or, 60*T = 66.68 - 100*T T = 66.68/160 = 0.41675 hours. Total travel time for the bird: t + T = 1.667 + 0.41675 = 2.08375 hours (and it occurs before these two trains collide each other). Total travel distance for the bird: 100 mph * 2.08375 hours = 208.375 miles

Interesting Algorithm question in Facebook Interview

The question is:

"Given a number in range of 1 to n, what is minimum number of guesses needed to find a specific number if you're just given an answer either "higher" or "lower" for each guess you make"

It sounds tricky, but actually the answer is very simple.

Here's the illustration:

the number to be guessed
                                             |  
                                             V
|----------------------------------------------------------------------|
min                              ^                                    max
                                 |
                                 |
                             your guess

Using common method of binary searching, our guess starts from: min + (max-min)/2 or a number in the middle of the range (divide-and-conquer). If our guess is lower than the number, we're given "LOWER" and vice versa.

As the number to be guessed is random, it is possible the number falls right in the middle of the range and matches our first guess. So the answer of this question is (the key of this question is "minimum number of guesses") is 1.