My Little Notebook

Using regular expression with Perl

2012-02-08T21:05:00.001-05:00

A very good tutorial:
Perl 5 - Regular Expressions

How Kinect works

2011-12-09T15:56:00.001-05:00

How does Kinect work? from Wired.com

And another one:
How does Kinect really work?

Copy constructor & Assignment constructor

2011-05-12T10:32:00.000-04:00

Default copy

Every struct and class have a default copy constructor and assignment operator method. e.g.

1: struct Foo { int f, o; }; 2: Foo f1 = {1, 10}; 3: Foo f2(f1); 4: Foo f3; f3 = f1;

Line 2 invokes the default copy constructor; Line 3 invokes the default assignment operator. The difference of the two is that the copy constructor is invoked when the target (f2) is constructed, passing the source object into the new one; the assignment constructor is invoked when the target object (f3) already exists.

When to implement your own copy?

The default copy only make a shallow copy. Thus, if one of the members is a pointer, a shallow copy will not allocate memory but create another pointer pointing to the same address. When one of them free the memory, the other one is still pointing to that piece of memory.

In this case, explicit copy and assignment constructor are required.

The difference between the bodies of the two constructors is that the copy constructor can allocate new memory and assign value to the pointer assuming that no member has been set yet (since the object is just being constructed); however, the assignment constructor must handle the case where members may already have been initialized and thus have to delete the contents of the pointer before assigning new value.

class Foobar { int fo; char* name; public: Foobar(const char* str, int n) { name = new char[strlen(str)+1]; strcpy(name, str); age = n; } Foobar(const Foobar& rf) { name = new char[strlen(rf.name)+1]; strcpy(name, rf.name); age = rf.age; } Foobar& Foobar(const Foobar& rf) { char* temp = new char[strlen(rf.name)+1]; delete[] name; name = temp; strcpy(name, rf.name); age = rf.age; return *this; } ~Foobar() { delete[] name; } };

Notice that

why temp is used and why not delete[] name; name = new char ...The reason is that the new may throw an exception and leave the object in a bad state. By finishing all operations that could fail and then replacing the fields, the code is safe.
the assignment operator returns a reference to the object so that f1 = f2 = f3 will work.

Avoid copy or assignment constructors

In some cases, it may not be proper to make a copy of some class fields. To prevent the default implicit copy and assignment constructors, a private copy constructor and assignment operator should be provided. No need to implement the methods. Simply prototyping is enough.

private: Foobar(const Foobar& rf); Foobar& Foobar(const Foobar& rf);

By doing this, if a piece of code attempts to copy the object, there will be an error message saying that the copy constructor and assignment operator cannot be accessed.

Ref: Copy Constructors and Assignment Operators

Mac OS X Memory Management: terms in Activity Monitor

2011-04-23T19:48:00.002-04:00

Last week, I was suffered by the super slow start of VMware Fashion. From the status bar, I can see the usage of CPU is low and the problem seems from memory usage. I opened Activity Monitor to see the detailed memory usage and was surprised to find out that there are only 100MB (or even less!) "free memory". Btw, I am using Macbook with 2G memory.

This forced me to do more research about the memory management in Mac OS. It turned out that the low amount free memory may not be a bad thing (cf. in Windows, it definitely sucks!).

Let's start from some general terms here.

You might noticed that, in Activity Monitor, there are: Free, Wired, Active, and Inactive memory. The sum of all these four will be equal to the total amount of RAM (in my case, 2GB).

Free memory: as named, it is the not-yet-used memory.
Wired memory: here, "wired" = always-in. These data will never be moved to the disk and will always stay in RAM. It could be owned by some core system processes or stand-by processes even after you close the application (main process).
Active memory: These data is currently in RAM and has been recently used.
Inactive memory: here is the tricky part. These data is not actively being used but has recently used. What does it mean? It means that each time when you quit an app, their data will stay in the memory as inactive memory until the app is reopened and access the same data again, OR they are replaced by other apps' data just like free memory. What's the benefit? Think about "memory frequency"!

Mac OS uses a different memory management methodology from what Windows does. It will crawl as more as possible free memory to catch up disk data so that when these data come into use, the access time will be reduced. When the memory usage hits some threshold, it will release some inactive memory; If it is still not enough, it will swap some data from RAM to disk. In Activity Monitor, you can see the cumulative statistics of Page-ins and Page-outs.

Check out this for more details about memory management and virtual memory.

求二进制数中1的个数

2011-03-15T09:52:00.001-04:00

比较常见的就是移位计数和快速法了，这篇帖子里列的相当全。

GNU Screen

2011-03-11T12:27:00.000-05:00

If you are a UNIX user, you maybe familiar with workspaces, featured in UNIX where you can have different workspaces: one for reading email, one for working, one for Internet surfing, and one for composing documents, blablabla.

Now you can start one terminal and run screen in it. Bang! Problem solved.

Refer to GNU Screen: an introduction and beginner's tutorial || kuro5hin.org for more details.

Here are some commands most used:

typing screen will start a screen session for you;
Ctrl-a and then type c to create a new session;
Ctrl-a n to switch to the next or previous session;
Ctrl-a d to detach from screen sessions and screen -r [session number] to resume the session you detached. Note that after you detached, all of the screen windows are still running. You can close the terminal, leave your office, go back home, open a terminal on your home machine and resume your work at home!

How to run .py file？

2011-02-27T14:33:00.003-05:00

Suppose Python is installed in /usr/bin/python.

In the .py file, add the following line as the first line to tell shell which interpreter you are using:
#!/usr/bin/python
Close the file, set it as an executable file
chmod a+x [filename]
Now you can type ./[filename] to execute it!

What if we need some input parameters? We will use command-line arguments and here is how:

In the .py file, add import sys, and then grab the arguments from sys.argv[1:].

Note 1: sys.argv[0] is the script name.
Note 2: sys.argv read in arguments as strings, so if you want integer or float use int() or float() to convert them.

Python - list

2011-02-25T16:43:00.007-05:00

List is a very useful and powerful data structure in Python. Here are something about it.

Copy a list in a right way

First we need to understand how Python manages objects. Remember pointers in C++? Keep it in mind since you gonna see its bro soon.

In Python, a = [1, 2, 3] means that a POINTs to the list [1, 2, 3]. a itself is NOT the list.
So, if we do b = a, we didn't copy the list from a to b. We just created a new "pointer" (or, more pythonic, say "tag") b which points to the same object as a does.
Thus, to copy the list referenced by a, we need to create a new list and attach b to it.

There are two ways:

Slicing. i.e. b = a[:]
[:] returns a slice of the specified portion of the list. It creates a new list, and copy the portion of the original list into the new one. By omitting the first and second index, the slice starts at the beginning and stops at the end of the list.
Constructor. i.e. b = list(a)
Here, list() is the constructor of list. It will construct a new list based on the passed parameter.
Plus, this makes the code more readable and more OO styled!

Refer [1] for more details.

More stuffs about [start:stop]

Basically, you can get any continuous portion from the original list by using the operator [:].

But, what if we want to extract odd or even items?

The straightforward way is even = [lst[i] for i in range(len(lst)) if i % 2 == 0].

Wait! Try this.

>>> l = [1, 2, 3, 4, 5]
>>> l
[1, 2, 3, 4, 5]
>>> l[::2]
[1, 3, 5]
>>> l[1::2]
[2, 4]

See, it is simple! The secret is: the third arg is a step value.

Remove duplicates from a list

[2] lists many ways to do it and their benchmarks. I pick some of them:

list(set(lst)) # No order preserving
{}.fromkeys(lst).keys() # No order preserving (faster than 1)
seen = set() # Order preserving
[x for x in lst if x not in seen and not seen.add(x)]

Ref: [1] Python: copying a list the right way

[2] Fastest way to uniqify a list in Python

How to "re-import" an updated module in Python Interpreter

2011-02-25T16:18:00.004-05:00

It is common to write a module and debug and test it in the Python interpreter on-the-fly. Then, after fixing some bugs, we want the interpreter test on the updated module.

Just typing "import" again will not help since it would only give you the existing copy of the module from sys.modules. Thus, a straightforward but brutal (and annoying :) way is exiting-and-reentering the interpreter.

Or, we can use "reload(module)" to update sys.modules and get a new copy of that module.

reload is a build-in function in Python. When reload(module) is executed:

Python modules’ code is recompiled and the module-level code reexecuted, defining a new set of objects which are bound to names in the module’s dictionary. The init function of extension modules is not called a second time.
As with all other objects in Python the old objects are only reclaimed after their reference counts drop to zero.
The names in the module namespace are updated to point to any new or changed objects.
Other references to the old objects (such as names external to the module) are NOT rebound to refer to the new objects and must be updated in each namespace where they occur if that is desired.

Did you see it? It is very tricky to get it right! If, if any other modules have a reference to the original module or any object from the original module, they will keep their old references and very confusing things will happen.

So, if you are using a self-contained module, reload will be perfect for you to save you from exiting-reentering cycles; but if you got two modules depending on each other, or if you got a module passing references to its objects to system module, unfortunately, exiting-reentering would be the only choice for you.

Vi/Vim: Insert text at the beginning of a multi-line selection

2011-02-24T00:45:00.004-05:00

Sometimes, we would like to indent or comment out a block of code. Here are some solutions:

Solution 1:

Use Ctrl+v to select the first column of text in the lines you want to comment.
Then hit 'I' and type the text you want to insert.
Then hit Esc, wait 1 second and the inserted text will appear on every line.

Solution 2:

This replaces the beginning of each line with "//":
:%s!^!//!
This replaces the beginning of each selected line (use visual mode to select) with "//":
:'<,'>s!^!//!;
And removing the text goes as follows:
:'<,'>s!^//!!
If you want to reuse it, put this in your .vimrc:
vmap \c :s!^!//! vmap \u :s!^//!!
Then, whenever in visual mode, you can hit \c to comment the block and \u to uncomment it. Of course, you can change those shortcut keystrokes to whatever.

Solution 3:

place the cursor on the first line and type the following to insert "//" at the beginning of that line:
I//
Press Esc and use the digraph:
j.j.
Here, j is a motion command and . repeats the last editing command you made (in this case I//).

Think before you do, ALWAYS

2011-02-14T20:34:00.005-05:00

Given a to-do list with 20 or 30 things like "write down your name", "draw a star", "write down numbers", etc. Now read it and see how far you can go in one minute. What will you do?

A. Work on the steps one by one immediately and as fast as possible.
B. Read through the whole list very quickly and then decide what to do next.

If you are an A-type person, you will only get about 10 or less steps down in one minute, since you need to read and write;
If you are a B-type person, congratulations! You will find that at the end (the last one or the one before the last) there is one step saying "skip step 1 through this one". Bingo!

This is to tell you: NEVER START UNTIL YOU KNOW WHAT YOU NEED TO DO.

For example, as a programmer, when you get a new project, don't sit down and coding immediately. INSTEAD, think about how to do it, think about algorithms, think about the best language you should use, think until you have a clear idea in your mind and then start coding. It sounds taking more time by thinking first, right? But, actually, no, it saves your time from fix unexpected bugs and from re-codings.

Wait, one more thing: How could I know the list will have that tricky step in advance?

Remember the instruction? "READ the list"! Yes, literally, read the whole list first!

Re-enable Java 1.5 and 1.4 on Mac OS X 10.6

2011-02-12T13:31:00.003-05:00

Apple disabled Java 1.4 and 1.5 from OS X 10.6 (the default is Java 1.6 there). Unfortunately, sometimes you will find some softwares still rely on the older versions.

Here are two articles talking about how to restore Java 1.4 and 1.5 with a hand-on instruction:

Using Java 1.5 and Java 1.4 on Snow Leopard
Snow Leopard Java problems (and fix)

Basically, to install Java 1.5 (1.4 would be the same, just replace 1.5.0 with 1.4.2)

Get Java 1.5 from Internet, e.g. http://tedwise.com/files/java.1.5.0-leopard.tar.gz
and expand it using tar -zxvf java.1.5.0-leopard.tar.gz
Move it to the default Java directory (password required)
sudo mv 1.5.0 /System/Library/Frameworks/JavaVM.framework/Versions/1.5.0-leopard
Finally, set up links
cd /System/Library/Frameworks/JavaVM.framework/Versions/ sudo rm 1.5.0 sudo ln -s 1.5.0-leopard 1.5.0 sudo rm 1.5 sudo ln -s 1.5.0 1.5
You can change the default Java version in Java Preference (located in /Applications/Utilities)

One more thing needed to be mentioned: After installing these older versions, some Java applications might crash, especially GUI applications. But command-line applications and using Java SDK to compile seems work very well.

You decide.

Install QualNet on Mac OS X

2011-02-09T20:55:00.003-05:00

Install QualNet

Download the installation package from the QualNet download page or load it from the installation CD.
Go to the home directory, and extract QualNet using the following command:
tar xvfz qualnet-4.5.1-university-wireless-mme.tar.gz
QualNet will be installed in ~/snt/qualnet/4.5.
Copy the license file into [qualnet_installed_dir]\license_dir
Set the QualNet environment variables.
QUALNET_HOME=[qualnet_installed_dir]/5.0 export QUALNET_HOME

Compile and Test

Go to QUALNET_HOME\main directory using the cd command to change directories.
Make a copy of the original Makefile for the version of gcc installed on your system.
cp Makefile-darwin-x86-gcc-4.0 Makefile
Use gcc -v to check the version of gcc (gcc 4.0 is required).
Important: Add these lines after the line "include Makefile-unix-common"
CXX = g++-4.0 GCC = gcc-4.0 CFLAGS += -m32 CXXFLAGS += -m32
Qualnet does not like 64 bit on the Mac...
Compile QualNet (it takes several minutes for QualNet to compile).
make
This creates the QualNet executable qualnet in the QUALNET_HOME/bin directory.
To recompile QualNet, run make again. However, it is sometimes useful to delete all object files before recompiling.
make clean make
Test the QualNet installation after compiling.
cd $QUALNET_HOME/bin/scenarios/default ./qualnet default.config
Test the QualNet GUI.
cd $QUALNET_HOME/gui/netbeans/bin ./runide.sh

2010-09-07T16:43:00.001-04:00

List of important publications in computer science

The Collection of Computer Science Bibliographies

svn: locate older versions

2010-07-23T21:19:00.002-04:00

To locate some older file via svn, we first need to figure out the version number.
svn log [filename] will list out all of the previous subversions of that file with comments that we checked in using svn commit -m "[comments]". The result would look like as follows:

------------------------------------------------------------------------ [ver no.] | [author] | [commit date & time] | [number of comment lines] [comments] ------------------------------------------------------------------------ and so on...

Then, after we find the version number that we are looking for, instead of checking it out, we can use svn cat -r [ver no.] [filename] to read the content of the file.

Basic Work Cycle on SVN

2010-07-14T16:41:00.004-04:00

I tried ZigVersion first on my Macbook. It is convenient to use, especially for a beginner. It provides license for non-commercial users. But, unfortunately, the website is not available any more.

So I turned back to SVN. Mac OS has already installed svn for developers. :)

The typical work cycle looks like this [1]:

1. Update your working copy.
• svn update
2. Make changes.
• svn add • svn delete • svn copy • svn move
3. Examine your changes.
• svn status • svn diff
4. Possibly undo some changes.
• svn revert
5. Resolve conflicts (merge others' changes).
• svn update • svn resolve
6. Commit your changes.
• svn commit

Ref: [1] Version Control with Subversion for svn1.5

Layout Management in Qt

2010-06-15T00:05:00.004-04:00

Layout management is to give an appropriate size and position for each widget on a form [1].

Instead of using manually (=lots of calculation and coding work :[ ) layout management, Qt provides several classes:

QHBoxLayout,
QVBoxLayout,
and QGridLayout.

These classes can be used conveniently through Qt Designer or directly in source code. They ensure that widgets adapt automatically to different fonts, languages, and platforms. That is, if the user changes the system's font settings, or he translate the application's UI to other languages, the layout classes will resize themselves to avoid text truncation. Plus, if we add or remove, hide or show , and change a widget from a layout, the layout will automatically adapt to the new situation.

QHBoxLayout and QVBoxLayout are quite straightforward: lay out side by side or in a top-bottom fashion, respectively.

QGridLayout allows a row by column layout, i.e. a two-dimensional grid.

addLayout and addWidget add layouts or widgets to a layout;
setContentsMargins and setSpacing change the margin around the dialog and the spacing between child widgets.
Or, modify the form setting from Form menu and select Form Setting... [2].

Ref: [1] More detailed example can be found in Chapter 6, [C++ GUI Programming with Qt4].2nd.Edt
[2] Qt4.6: Customizing Qt Designer Forms

zz 高效的Timer实现 - Daly的游戏人生 - C 博客

2010-06-04T17:23:00.001-04:00

原帖：高效的Timer实现 - Daly的游戏人生 - C 博客

很多程序都需要处理一系列定时事件，一个Timer程序就是实现定时事件集合的管理。
每个timer事件项一般包括超时值(delay), 标识(key)和回调函数，Timer程序的作用就是实现插入，删除，更新和调用。

方法1. 链表
最简单的实现是有序链表。list_head保存到当前时间的剩余时间remain_time，后一节点保存与前一节点的超时时间的差(而不是到当前时间的差)。
更新：每次tick update时，只需要更新链表头节点remain_time，如果remain_time <= 0, 调用函数，删除该头节点，然后更新后一个节点的remain_time,如此类推直到头结点remain_time > 0或链表为空. O(1)
插入：相当于插入排序。有序插入到适当位置，更新后一个节点的remain_time.
删除：遍历链表搜索，删除节点，更新后一个节点的remain_time.
例子：live555流媒体服务器

方法2. 最小堆(优先队列)
方法与链表类似，插入/删除效率从O(n)变为O(lgN)
libevent中有min-heap实现一个优先队列，根节点是最先触发的超时时间, 与方法1一样，只需更新根节点。根节点超时后，调整堆即可

方法3. Hash或分级
根据超时值的范围(比如CPU的流逝ticks)进行hash，hash后每个bucket实现方法1所示的链表. 较方法1减少了搜索次数
例子：MudOS定时器

方法4. 分级hash
这是linux内核timer的实现方法，值得参考。见文献[1]
方法：假设定时值以tick为单位，每tick更新timer一次。
定时值范围为0 ~ 2^32个tick(32个bit), 则把他分成4级，每级做一个hash, 每个则有256个bucket (刚好8bit)
000000000 00000000 00000000 00000000
--------- -------- -------- --------
A B C D
插入：算出 tick_trig = delay + 当前tick， mask = tick_trig & 0xFF000000，
如果mask不等于0，在A hash表插入timer项, 否则进入下一级，mask = tick_trig & 0x00FF0000, 插入B hash表，如此类推。
更新：每次tick++, 先检查D hash表(最低8位的与操作)有无timer项，如果有，执行函数并删除。
如果tick满255进位，则检查C hash表中对应位置有否timer项，如果有，重新插入(此处的timer项必定会插入D hash表中)，如此类推
这样，插入，更新，删除都做到O(1)了
疑惑：这个方法用于内核级程序。对于用户级程序，每次update的间隔不恒定（即每次tick不一定是+1），这时需要扫描tick之前的几个bucket了

Getting Started with Qt4

2010-05-15T17:36:00.007-04:00

Create a hello.cpp file in hello directory with the following code:

#include <QApplication> #include <QPushButton> int main (int argc, char *argv[]) { QApplication app(argc, argv); QPushButton *button = new QPushButton("Quit"); QObject::connect(button, SIGNAL(clicked()), &app, SLOT(quit())); button->show(); return app.exec(); }

Enter the hello directory, type qmake -project to platform-independent project file (.pro file), and then type qmake -spec macx-g++ hello.pro to create a platform-specific makefile from the project file (in this case, we use g++).
Type make to build the program.
Run it by typing ./hello on Unix, and open hello.app on Mac OS X.

In Qt, a widget is "a visible element in a user interface". It includes buttons, menus, scroll bars, dialogs, and main windows. Usually, most applications use a dialog or main window as its application window. But Qt allows any widget to be an application window (in this example, a button).

A Qt widget uses signals (no, not THE signal in UNIX =) to indicate that a user action or a change of state has occurred. In this example, a button's clicked() signal is connected to the application object's quit() slot (i.e. function).

Ref: [1] [C++ GUI Programming with Qt4].2nd.Edt
[2] Qt Assistant (== MSDN for VC)

extern keyword

2010-05-11T18:20:00.004-04:00

The extern keyword explicitly declares a variable or function and specifies that it has external linkage (i.e. visible from files other than the one in which it's defined).

Declare vs. Define [1]
To define a variable, the compiler will allocate memory and might also to initialize it to some value;
To declare a variable, the compiler "knows" that a variable by that name and type exists, and it will not allocate memory since it has been done somewhere else.
A variable must be defined once and only once but it can be declared many times.

An external variable may also be declared inside a function. Otherwise the compiler will consider it a definition of a local variable with a different scope, lifetime and initial value. This declaration will only be visible inside the function.

extern vs. include guards [2]

Include guards:
#ifndef _SOMENAME_H #define _SOMENAME_H ... (body of the header) ... #endif //_SOMENAME_H
Include guards are useful only when a.cpp includes a.h and b.h, both of which include c.h. In this case, c.h will be parsed only once.

Consider a header file, header.h, which has a global variable declaration without extern keyword.
int x;
Now suppose two source files, a.cpp and b.cpp, both of which include header.h. And we compile a.cpp and b.cpp separately.
g++ a.cpp -o a.o g++ b.cpp -o b.o
When a.cpp is compiled, the compiler reads header.h and instantiates an integer variable named x as part of the object file a.o. Then b.cpp gets compiled. The compiler doesn't remember that a.cpp already read hearder.h, and it will read header.h (again!) and instantiates another integer variable named x as part of b.o!
When a.o and b.o are linked into the final executable, there are two separate instantiations of the same variable, x! Hence, a linked error. :(

The extern applied to a function prototype makes no difference since functions are assumed to be external. But, when used with a string, it can specify that the linkage conventions of another language are being used for the declarator(s).

extern string-literal declarator
extern string-literal { declarator-list }

Mixed-language Programming and external linkage [3]

A C++ programmer may use a standard C library and it works coz C implementation takes care of the language for us. But when we use our own libraries witten in C from a C++ program, we need extern "C" for our functions.
Consider a C library containing
%cat greet.h extern char *greet(); // notice that there is no string-literal "C"!
Now our C++ code call the C function and is linked with the dynamic library that holds the implementation for the function.
%cat mixcode.cpp #include "greet.h" int main() { greet(); return (0); } %CC -lgreet mixcode.cpp
The linking will be failed with undefined symbol error! Why?
The reason is that a typical C++ compiler mangles function names to support function overloading! So, the symbol greet is changed to something else (depends on the algorithm implemented in the compiler during the name mangling process). Hence the object file dose not have the symbol greet anywhere in the symbol table!
The solution is to use extern "C" instead of extern.
%cat greet.h #if defined __cplusplus // use this to avoid an error from a C compiler extern "C" { // since C compiler doesn't recognize "C" protion #endif char *greet(); #if defined __cplusplus } #endifThe function name greet was not mangled by the C++ compiler, and hence the linker could find the symbol in the object file and was able to build the executable.

Note: Standard C99 does NOT support function overloading but it may mangle some names.

Ref: [1] External variable (wiki)
[2] Header inclusions (C++ forums)
[3] Mixed-language Programming and external linkage

Install libQGLViewer on Mac OS X 10.6.3 (Snow Leopard) [1]

2010-05-02T14:18:00.006-04:00

Pre-requirement: Qt
The easiest way to develop Qt applications on a Mac is to download Xcode from the apple web site and then to install a Qt package from the nokia web site.

Note -- Qt for Mac OS X requirement

Performing a new install of the Qt 4.6 beta on Snow Leopard triggers a bug in the installer that causes the install to fail. Updating an existing Qt installation works fine.
There are two workarounds, either disable spotlight for the target drive during the install, or do a custom install where you deselect documentation and examples. Run the installer again as a full install to get the documentation and examples installed.

Using make
The general procedure is

tar -xzf libQGLViewer-2.3.5.tar.gz
cd libQGLViewer-2.3.5/QGLViewer
qmake
make
make install

The default install paths are system directories. It could be customized by qmake parameters, e.g. qmake PREFIX=$HOME

Possible Errors and Solutions

bash-3.2$ qmake -spec macx-g++
bash-3.2$ make
make: *** No rule to  make target `qglviewer.icns', needed by `/Library/Frameworks/QGLViewer.framework/Versions/2/Headers/qglviewer.icns'.   Stop.

Solu 1: Remove every mention of qglviewer.icns in all .pro files.
Solu 2: Create an empty file with the same name to "cheat" make.

touch qglviewer.icns
make

```
bash-3.2$ qmake -spec darwin-g++
bash-3.2$ make
Undefined symbols:
"QWidget::x11Event(_XEvent*)", referenced from:
vtable for VRenderInterfacein saveSnapshot.o
vtable for ImageInterfacein saveSnapshot.o
vtable for QGLViewerin moc_qglviewer.o
ld: symbol(s) not found
collect2: ld returned 1 exit status
make: *** [/Library/Frameworks/QGLViewer.framework/QGLViewer] Error 1
```
darwin-g++ requires X11. Supposedly, x11Event thing is only switched on when Q_WS_X11 is defined [2].

A solu: try compile and run the following program [3] with gcc -I/Developer/qt/include -o test test.c and see what it says. If it says Q_WS_X11 then that's the problem. Find a version of gcc and Qt so that Q_WS_X11 will not be spited out. An alternative is to include -lX11 at link time to force feed (a bad dog...).

Using Xcode

qmake -spec macx-xcode

Then open and build the resulting Xcode project. Run make install to install the documentation in /Developer/Documentation/QGLViewer.

Note
Both Xcode and make generate a Framework by default.

Ref: [1] libQGLViewer installation on Mac
[2] Bugs: can't make mysql on Mac
[3]

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

#include <qglobal.h>

int main(int argc, char **argv) {

#if defined(__APPLE__) && defined(__GNUC__)
fprintf(stderr, "__APPLE__ && __GNUC__\n");
#endif

#ifdef __MACOSX__
fprintf(stderr, "__MACOSX__\n");
#endif

#ifdef __DARWIN_X11__
fprintf(stderr, "__DARWIN_X11__\n");
#endif

#ifdef Q_OS_UNIX
fprintf(stderr, "Q_OS_UNIX\n");
#endif

#ifdef Q_WS_MACX
fprintf(stderr, "Q_WS_MACX\n");
#endif

#ifdef Q_WS_X11
fprintf(stderr, "Q_WS_X11\n");
#endif
}

It should say:

__APPLE__ && __GNUC__
Q_OS_UNIX
Q_WS_MACX

Uninstall DevTools

2010-04-29T23:15:00.002-04:00

Uninstall XCode:

Type the following command from a terminal window.
%% sudo /Developer/Library/uninstall-devtools --mode=all
Easy enough, just make sure this is what you really intend to do as once it’s gone, it’s gone.
IMPORTANT: If you are going to install a previous version of the Developer Tools, be sure to restart the machine after installing.

Uninstall MacPort: [1]

First uninstall all the installed ports by running this command in the Terminal.
%% sudo port -f uninstall installed
To remove all remaining traces of MacPorts, run the following command in the Terminal.
%% sudo rm -rf \
/opt/local \
/Applications/DarwinPorts \
/Applications/MacPorts \
/Library/LaunchDaemons/org.macports.* \
/Library/Receipts/DarwinPorts*.pkg \
/Library/Receipts/MacPorts*.pkg \
/Library/StartupItems/DarwinPortsStartup \
/Library/Tcl/darwinports1.0 \
/Library/Tcl/macports1.0 \
~/.macports

Polymorphism, Inheritance -- virtual functions

2010-04-27T19:05:00.008-04:00

A virtual function allows derived classes to over-ridden the implementation provided by the base class so that derived classes could have different functionality from the base class.

cf. Function Overloading: Declare the same function (same name, same return type) with different number of parameters or different types of parameters.

cf. non-virtual member functions: The non-virtual functions are resolved at compile time (aka static binding); whereas the virtual functions are resolved during run-time (aka dynamic binding).

If a function is NOT declared as virtual, then the base class function would have been called all the times; But if the function is declared virtual, the derived class function is being invoked.
Whenever a program has a C++ virtual function declared, a v-table is constructed for the class. The v-table consists of addresses to the virtual functions for classes and pointers to the functions from each of the objects of the derived class. Whenever there is a function call made to the c++ virtual function, the v-table is used to resolve to the function address. This is how the Dynamic binding happens during a virtual function call.

vs. Java: In Java, all non-static methods are by default virtual functions unless they are marked with the keyword final.

A pure virtual functions is declared using a special syntax [ = 0 ] and all classes that contain at least one pure virtual function are abstract base classes.
Because in abstract base classes at least one of its members lacks implementation, we can NOT create instances (objects) of it. But we can create pointers to it and take advantage of all its polymorphic abilities.

class Abstract {
public:
virtual void pure_virtual() = 0;
};

Abstract abs; // illegal
Abstract* pAbs; // perfectly valid

It is important for a C++ base class to have a virtual destructor to ensure that the destructor from the most derived class will always be called.

Here is a full example:

#include <iostream>
#include <string>

using namespace std;

//There are N types of amphibians: frogs and toads.

class Amphibian{
public:
Amphibian() {
cout << "Constructing " << name() << endl;
}
virtual ~Amphibian() {
cout << "Destructing " << name() << endl;
}
public:
void jump(){ // non-virtual function
cout << "I'm jumping now." << endl;
}
virtual string name() {
return "Amphibian";
}

// not a pure virtural function but a declaration
// will produce error during link-time
//virtual void speak();

virtual void speak() {
cout << "Error." << endl;
}
};

class Frog: public Amphibian{
public:
~Frog() {
cout << "Destructing " << endl;
}
public:
string name() {
return "Frog";
}
void speak() {
cout << "Ribbet." << endl;
}
};

class Toad: public Amphibian{
public:
Toad() {
cout << "Contructing " << endl;
}
public:
string name() {
return "Toad";
}
void speak() {
cout << "Croak!" << endl;
}
};

int main(){

Amphibian * ap1 = new Amphibian();
ap1->jump();
ap1->speak();
cout << endl;
Frog * fp1 = new Frog();
fp1->jump();
fp1->speak();
cout << endl;
Toad * tp1 = new Toad();
tp1->jump();
tp1->speak();
cout << endl;

Amphibian * list[10];
list[0] = ap1;
list[1] = fp1;
list[2] = tp1;

for (int i = 0; i <>
list[i]->speak(); //ah!

delete ap1;
cout << endl;
delete fp1;
cout << endl;
delete tp1;

return 0;
}

g++ output:

Constructing Amphibian
I'm jumping now.
Error.

Constructing Amphibian
I'm jumping now.
Ribbet.

Constructing Amphibian
Contructing Toad
I'm jumping now.
Croak!

Error.
Ribbet.
Croak!

Destructing Amphibian

Destructing Frog
Destructing Amphibian

Destructing Amphibian

Ref: [1] wiki - virtual function
[2] C++ FAQ Lite - virtual function

CMake -- Cross-Platform Make System

2010-04-27T17:43:00.003-04:00

CMake itself is not a build system, since it USES native build system to build files.
It generates native build environments and it supports most modern systems, such as Make on UNIX/Linux, VS on Windows and XCode on Apple. That's how it can be used as a Cross-Platform make system.

Using CMake to build a project is extremely easy.

First, create a CMakeLists.txt which contains the project parameters and describes the build process in simple CMake language.

Then, take UNIX as an example, enter the directory which contains CMakeLists.txt and type in:

cmake path
make

The CMake step reads the CMakeLists.txt file from the source directory and generates appropriate Makefiles for the system, in the current directory. CMake also maintains a list of all header files that objects depend on, so dependency checking can be assured. If you need to add more source files, simply add them to the list. Once Makefiles are generated, you do not have to run CMake any more, because the dependency to CMakeLists.txt also are in the generated Makefiles. If you want to make sure that dependencies are regenerated, you can always run make depend.

Similarly, on Mac OS X, run

cmake -G Xcode

CMake will generate an XCode project for you. Just open the XXX.xcodeproj in XCode and you are done. =]

Ref: [1] CMake Wiki
[2] CMake + Qt4 + XCode on OSX

Default install location for MacPorts

2010-04-20T18:11:00.003-04:00

Default: /opt/local

Reason: to avoid stomping on other installations; /usr/local is not a viable (practicable/feasible) choice due to:

Some software (especially tools from GNU) look in /usr/local as a default location, which means MacPorts can't be isolated when needed
/usr/local is usually reserved for the host system's admin to install items local to that system, so it would be a bad choice to be taken over by a non-system port system
GCC considers /usr/local to be a standard system directory, thus, (at least) the include directory is UNable to appear early in the list of include directories, and hence, MacPorts-installed items would be difficult to use properly for items which need them (where another version is installed elsewhere, like /usr/X11R6)

Ref: FAQ - MacPorts

Install libQGLViewer on Mac using MacPorts

2010-04-20T17:45:00.003-04:00

Well, I felt so lucky to have MacPorts to install these open-source libraries... So many dependencies...

bash-3.2$ port deps libQGLViewer
Full Name: libQGLViewer @2.3.5
Build Dependencies: libicns
Library Dependencies: qt4-mac

bash-3.2$ sudo port install libqglviewer
Password:
---> Computing dependencies for libQGLViewer
---> Fetching jpeg
...
---> Fetching jasper
...
---> Fetching libpng
...
---> Fetching libicns
...
---> Fetching perl5.8
...
---> Fetching perl5
...
---> Fetching p5-locale-gettext
...
---> Fetching help2man
...
---> Fetching m4
...
---> Fetching autoconf
...
---> Fetching automake
...
---> Fetching libtool
...
---> Fetching pkgconfig
...
---> Fetching dbus
...
---> Activating dbus @1.2.16_1
###############################################################
# Startup items have been generated that will aid in
# starting dbus with launchd. They are disabled
# by default. Execute the following command to start them,
# and to cause it to launch at startup:
#
# sudo launchctl load -w /Library/LaunchDaemons/org.freedesktop.dbus-system.plist
# launchctl load -w /Library/LaunchAgents/org.freedesktop.dbus-session.plist
###############################################################
---> Cleaning dbus
---> Fetching tiff
...
---> Fetching lcms
...
---> Fetching libmng
...
---> Fetching readline
...
---> Fetching sqlite3
...
---> Fetching qt4-mac
...

It was stuck when "Building qt4-mac". Used Ctrl+C to break the procedure and tried to re-install by calling "sudo port install libqglviewer" but didn't work. From the manual, it is said that a port can not be uninstalled if it was installed as a dependency. Thus, called "port clean qt4-mac" and re-install libqglviewer. It worked!

---> Fetching libqglviewer
...

Install CGAL on Mac using MacPorts

2010-04-20T17:22:00.003-04:00

For a general introduction about MacPorts and its commands, you can find in the prior post.

bash-3.2$ port deps cgal
Full Name: cgal @3.5.1
Library Dependencies: cmake,
boost,
mpfr

bash-3.2$ port install cgal
MacPorts running without privileges. You may be unable to complete certain actio
ns (eg install).
---> Computing dependencies for cgal
...
Error: Target org.macports.install returned: MacPorts requires root privileges f
or this action
Error: The following dependencies failed to build: cmake libidn gettext libiconv
gperf ncurses ncursesw openssl mpfr gmp
Error: Status 1 encountered during processing.
Before reporting a bug, first run the command again with the -d flag to get comp
lete output.

bash-3.2$ sudo port install cgal
Password:
---> Computing dependencies for cgal
---> Fetching gperf
...
---> Fetching libiconv
...
---> Fetching ncursesw
...
---> Fetching ncurses
...
---> Fetching gettext
...
---> Fetching libidn
...
---> Fetching openssl
...
---> Fetching cmake
...
---> Fetching gmp
...
---> Fetching mpfr
...
---> Fetching cgal
---> Attempting to fetch CGAL-3.5.1.tar.gz from http://lil.fr.distfiles.macports.org/cgal
---> Verifying checksum(s) for cgal
---> Extracting cgal
---> Configuring cgal
---> Building cgal
---> Staging cgal into destroot
---> Installing cgal @3.5.1_0
---> Activating cgal @3.5.1_0
---> Cleaning cgal

bash-3.2$ port livecheck cgal
cgal seems to have been updated (port version: 3.5.1, new version: 3.5)

Install Boost on Mac (Snow Leopard) using MacPorts

2010-04-20T15:13:00.005-04:00

The MacPorts is an easy-to-use system for compiling, installing, and upgrading open-source software on the Mac OS X operating system.

Pre-requirement:

Apple's Xcode Developer Tools
Ensure that the optional components for command line development are installed ("Unix Development" in the Xcode 3.x installer).
The X11 windowing environment (aka "X11 User")
The "X11 User" package is included by default on Snow Leopard.
You can use the xorg-server port instead of Apple's X11.app if you wish.

Install MacPorts:

The easiest way is to download the dmg for Snow Leopard and run the system's package installer (.pkg). This procedure will place a default MacPorts installation on your host system. Your shell configuration files (.profile) might be adapted by the installer. The installer will also run "selfupdate" to ensure the latest available release.
To keep your MacPorts system current, you should run the following step manually:
sudo port -v selfupdate

MacPorts also provides Source install and SVN install. You can find a detailed instruction here or Installing section in manual.

Install Boost using MacPorts:

bash-3.2$ port deps boost
Full Name: boost @1.42.0
Build Dependencies: boost-jam
Library Dependencies: zlib,
expat,
bzip2

Then in the installing procedure, it installs dependencies first and then boost.

bash-3.2$ sudo port install boost
Password:
---> Computing dependencies for boost
---> Fetching boost-jam
---> Attempting to fetch boost-jam-3.1.17.tgz from http://voxel.dl.sourceforge.net/boost
---> Verifying checksum(s) for boost-jam
---> Extracting boost-jam
---> Applying patches to boost-jam
---> Configuring boost-jam
---> Building boost-jam
---> Staging boost-jam into destroot
---> Installing boost-jam @3.1.17_0
---> Activating boost-jam @3.1.17_0
---> Cleaning boost-jam
---> Fetching bzip2
...
---> Fetching expat
...
---> Fetching zlib
...
---> Fetching boost
---> Attempting to fetch boost_1_42_0.tar.bz2 from http://voxel.dl.sourceforge.
net/boost
---> Verifying checksum(s) for boost
---> Extracting boost
---> Applying patches to boost
---> Configuring boost
---> Building boost

---> Staging boost into destroot
---> Installing boost @1.42.0_0
---> Activating boost @1.42.0_0
---> Cleaning boost

Port Commands [manual]:

selfupdate
sudo port selfupdate
or use the debug flag for verbose output: sudo port -d selfupdate
list
port list is used to get a list of all available ports. (The list is very long, so use search if you know part of it.)
port installed is used to get a list of all installed ports in your host system.
search
port search xxx is used to find port names by partial matches.
get information
port info xxx is to get information about a port: description, maintainer, etc.
port deps xxx shows the dependencies of a port.
port variants xxx allows you to check what variations of a port are available.
install
sudo port install xxx
clean
port clean --all xxx deletes all intermediate files that MacPorts creates while building a port.
uninstall
port uninstall xxx will uninstall an installed port.
A port will not be uninstalled if it was installed as a dependency of another port. You can use -f (force) uninstall port -f uninstall xxx but be careful!
upgrade
port upgrade xxx upgrades installed ports and their dependencies when a Portfile in the repository has been updated after the port was installed.
port -n upgrade xxx will not upgrade a port's dependencies.
port upgrade outdated upgrades all outdated ports.

Self learning

2010-03-31T17:20:00.000-04:00

Several useful websits for programmer: -- those who want to learn sth awesome by themselves (not only in class, definitely).

O'Reilly Answers
http://answers.oreilly.com/

Webmonkey
http://www.webmonkey.com/

Google Code University
http://code.google.com/edu/languages/

Rectilinear Mininimum Spanning Trees & Steiner Trees

2010-03-30T15:32:00.005-04:00

Given a set of points in a plane, a Rectilinear Minimum Spanning Tree (RMST) is a set of edges which connects all of the points with minimum rectilinear distance. Rectilinear distance (also called "Manhattan Distance") is the sum of the horizontal and vertical distance between two points. It is used instead of Euclidean distance in VLSI CAD applications because VLSI processes support only horizontal and vertical wires.

The RMST can be used as an estimate of the length of a net that connects together multiple terminals.

The RMST Problem is a special case of the Minimum Spanning Tree problem studied in Computer Science Algorithms textbooks in that the distances between the points imply a complete graph

Ref: [1] A. Kahng and I. Mandoiu, "GSRC Bookshelf RMST-Pack: Rectilinear Minimum Spanning Tree Algorithms", June 2001.
[2] RMST Applet

About Steiner Trees

Given a set of terminal points in a plane, a Minimum Steiner Rectilinear Tree (MSRT) is a set of edges which connects all the terminals along with a set of added "Steiner points" such that the rectilinear distance is minimized. F. Hwang [4] proved that the length of a Steiner tree can be up to 3/2 times shorter than a Rectilinear Minimum Spanning Tree on the same set of terminals.

M. Hanan [3] proved that a Minimum RST can be constructed using points on a grid defined by the x and y coordinates of the terminal points (now known as the Hanan Grid).

The Minimum Steiner Rectilinear tree problem is be NP-Hard [2].

Ref: [1] MSRT Applet
[2] M. Garey and D. Johnson, "The rectilinear Steiner tree problem is NP-complete", SIAM Journal on Applied Mathematics, Vol. 32 pp. 826-834, 1977.
[3] M. Hanan, "On Steiner's Problem with Rectilinear Distance", SIAM Journal of Applied Math, Vol. 14, No. 2, March 1966, pp. 255-265.
[4] F. Hwang, "On Steiner Minimal Trees with Rectilinear Distance", SIAM Journal of Applied Mathematics, Vol. 30, No. 1, January 1976, pp. 104-114.
[5] F. Hwang, D. Richards, and P. Winter, The Steiner Tree Problem, North-Holland, 1992.

Flash memory vs. DRAM

2010-02-24T11:14:00.003-05:00

Flash memory is a non-volatile computer storage that can be electrically erased and reprogrammed. Now it can be erased and programmed in large blocks instead of the entire chip in earlier age.
Flash memory is non-volatile, meaning that no power is needed to maintain the information stored in the chip. Beyond that, flash memory offers fast read access times (although not as fast as DRAM) and better kinetic shock resistance than hard disks. These characteristics determine the popularity of flash memory in portable devices. Plus, it is extremely durable, in terms of intense pressure, extremes of temperature, and even immersion in water.
Flash memory is a type of EEPROM but old-style EEPROM is only erasable in small blocks (typically bytes) and thus slowly. Being able to erase in large blocks gives flash memory a significant speed advantage over old-style EEPROM.

DRAM (Dynamic Random Access Memory) is a type of random access memory. Its structure is simpler than SRAM, which allows DRAM to reach very high density. But, unlike flash memory, it is volatile memory (it loses its data when the power supply is removed.

Nucleus RTOS

2010-02-23T23:29:00.003-05:00

Nucleus OS is an efficient real-time operating system (RTOS) created by the Embedded Software Division of Mentor Graphics.

It is ideal for resource-constrained devices (in terms of frequency and memory) and for environments where squeezing out every cycle per watt is paramount. It is designed for embedded applications such as consumer electronics, set-top boxes, cell phones, and other portable and hand-held devices.

Core Services: Dynamic task creation and deletion; Application Timers; Counting Semaphores; Event Flags; Static and dynamic memory allocation.
Inter-task Communications Synchronization via: Semaphores; Fixed and variable queues; Mailboxes; Pipes; UNIX-like Signals.
Real-Time MMU (Memory Management Unit): Deterministic flat memory model; Graceful handling of errors in the field.

Possible uses of Wireless Sensor Networks

2010-02-17T20:37:00.002-05:00

Just record them here and will check them our with more details later when writing my thesis. ^^

Environmental and weather monitoring
home automation and air conditioning
monitoring soil in agriculture
tracking goods in commerce and industry
monitoring machines in manufacturing plants
health care and medical diagnostics
CodeBlue by Harvard Univ.
smart clothing for firefighter protection
sensor mote, dynamically select header sensor of the cluster (one cluster per person)
[Huantian Cao, Dept. of Fashion and Apparel Studies@UDel]
intrusion detection and other security systems
military applications

Taxicab Geometry

2010-02-17T10:47:00.005-05:00

The taxicab metric, also known as rectilinear distance, city block distance, Manhattan distance, is another metric of Euclidean geometry in which the distance between two points is the sum of the (absolute) differences of their coordinates. Manhattan distance comes from the grid layout of most streets on the island of Manhattan where the shortest path a car could take between two points in the city is as long as their distance in taxicab geometry.

Given two points p(p_1, p_2, ..., p_n) and q(q_1, q_2, ..., q_n), their taxicab distance is

dist(p, q) = Sum(|p_i - q_i|), i = 1, 2, ..., n

e.g. in 2D plane, the taxicab distance between (p_1, p_2) and (q_1, q_2) is |p_1 - q_1| + |p_2 - q_2|.

cf. The Euclidean distance is the length of the straight line segment between two points.
As shown in the picture (from wiki), the green line is Euclidean distance; The red, blue, and yellow lines are Manhattan distance and they have the same length.

In chess, the distance between squares on the chessboard is measured in Manhattan distance.

Interestingly, the shape of circles in taxicab geometry changes -- taxicab circles are squares with sides oriented at a 45° angle to the coordinate axes.

0-1 Integer Programming

2010-02-08T15:20:00.003-05:00

Linear Programming (LP) is a mathematical method to achieve an optimal outcome (such as maximum profit or lowest cost) in a given mathematical model with a list of requirements represented as linear equations. It can be expressed in the following form:

Maximum c^Tx
Subject to Ax ≤ b

where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients and A is a (known) matrix of coefficients.

If the unknown variables are all required to be integers, then the problem is called an Integer Programming (IP) or Integer Linear Programming (ILP) problem. 0-1 IP or Binary Integer Programming (BIP) is the special case of IP where variables are required to be 0 or 1 (rather than arbitrary integers). In contrast to LP, which can be solved efficiently in the worst case, this problem is classified as NP-hard. If only some of the unknown variables are required to be integers, then it is Mixed Integer Programming (MIP) problem. They are also NP-hard.
Advanced algorithms for solving ILP includes:

Branch and Bound
(Ref: http://mat.gsia.cmu.edu/orclass/integer/node13.html)

Solve the linear relaxation of the problem. If the solution is integer, then we are done. Otherwise create two new subproblems by branching on a fractional variable.
A subproblem is not active when any of the following occurs:
1. You used the subproblem to branch on,
2. All variables in the solution are integer,
3. The subproblem is infeasible,
4. You can fathom the subproblem by a bounding argument.
Choose an active subproblem and branch on a fractional variable. Repeat until there are no active subproblems.

b. Cutting Plane method
The fundamental idea behind cutting planes is to add constraints (called cuts) to a linear program until the optimal basic feasible solution takes on integer values.

What do U and I learn from PhD?

2010-02-07T09:47:00.003-05:00

It is generally believed that Ph.D. graduates are ONLY suitable candidates for academia and research. However, it is NOT just that!

What do you learn from PhD study? How do you prepare for work? (or, I should say, what/how should you?!)

Conducting Research
A major difference between a undergrad life and a graduate life is the emphasis on research.
Undergrad education focuses more on understanding fundamental concepts, evaluated through homework assignments and exams; While graduate education emphasizes on broad research through publication reviews, class projects, faculty-student group research, and the dissertation.
At the beginning, preliminary research provides an look into a variety of disciplines within the major area and allows students to develop and determine their interest.
At the ending, students focus on specific problem-solving tasks to complete their dissertations and thus gradation.
Not only the successes but failures of the research help develop the practical skills necessary for career success.
Communicating effectively
The skills and good habits of technical writing are further developed in graduate school, which is desired by most employers. Also, presenting one's ideas individually in a technical session builds student confidence and alleviates presentation anxiety. Students become familiar with visual aids and learn how to delivery their ideas better according to their audience.
Teaching
Through teaching experiences, students learn how to express their knowledge, get better teamwork, develop critical multitasking skills on time management, and may even improve supervisor/employee relationships.

Ref: "Putting transferable Ph.D. skills to work", Maryclaire Peterson, IEEE Potentials 2009.

MU-MIMO systems

2010-02-06T22:55:00.002-05:00

Keep this in mind just in case it might be of help someday...

Multiple User Multiple Input Multiple Output system: the future of wireless communication systems. MIMO have already been employed in 802.11n and 802.16e standards. Now, it might be extended to multi-user scenarios in the context of high data rates envisioned for future cellular standards after 3G.

GPU vs. CPU

2010-02-06T14:45:00.002-05:00

GPU, a Graphics Processing Unit, is a specialized processor designed for high performance 3D rendering. Their born highly parallel structure make them more effective and efficient than general-purpose CPUs.

Due to the relentless demands for graphics performance, GPUs provide parallel design for vector operations and also increase their precision in programmablity, from 8-bit integer (as most CPUs do), to 24-bit floating point, then to 32-bit floating point, and soon to 64-bit double-precision floating point!

Now, since GPUs are programmable, they are considered to be used for some more general computation for complex algorithms. GPUs exceed the complexity of modern CPUs in terms of absolute transistor count but they are designed for solving almost completely unrelated problems. At least, GPUs may be used as a new form of stream processors in the context of parallel processing and floating point calculations.

PS. I'm not a graphics gal and I might interpret GPUs in a wrong way... If so, hope someone could point it out...

A little worry...

2010-02-05T19:42:00.000-05:00

When I was reading an article for sensor battery, "forever" battery using some nanotechnology. Then I was a little, just a little bit, worried about my current research topic.
I'm designing algorithms to prolong the battery lifetime in the context of topology control.
What if, at some point, sensors would have forever battery using solar or nano batteries?! Would then my research make any sense any more??? :-(

Living in the Cloud?!

2010-01-21T22:02:00.003-05:00

<Winners & Losers>, a special report of IEEE Spectrum for the past 2009, predict Google's Chrome OS as one of the winners.

It IS pretty cool:
-- 7 SECONDs from a shut-down computer to your emails and docs;
-- No more various plug-ins (thanks to HTML5 and hope all websites would like HTML5 sooner...);
-- Say goodbye to hard drives and L2 caches and walk in the cloud w/o even realize you are there.

It would be an amazing change not only to an OS but to the entire architecture of computers.
Hmm, if all of these would be implement in the future few years, what would happen?
No other software companies! The world will be a realm of Google + Internet.

Now, everything will be in the cloud. And, it is FREE! -- Chrome OS and browser are both free and open-source (Well, you still need to buy a netbook… But it is just $300+, a similar price for a smart phone!).
But, is it really free?
Actually, sorry but NO. You need to pay for your "steps" in the cloud: pay for the Internet. And sometimes, you would be "kick out" from the Cloud to the "ground" even you would like to pay. Yes, just think about being on a flight w/ your brick netbook.
Technically, we have internet access everywhere. But if you rely all your life on the Cloud, you will definitely find that it is just a fairytale.
So, maybe Google would figure out a way to offer free wifi all over the world…

Another issue is security, also the kink of the Cloud.
Is it Safe? Is it safe for sensitive documents?
"It's worth pointing out the many companies store sensitive documents in the cloud right now, and some of them use the enterprise version of Google Apps." ["Chrome the Conqueror", Jan 2010 IEEE Spectrum.]
So, Chrome should also provide a way to "jump" from one Cloud to another (login might be able to do that) and make sure any information in the private Cloud would not be leak to the public.

It would be revolution -- to "googleize" the real world!

Poor Richard's advice

2009-10-27T15:06:00.001-04:00

Poor Richard's advice: "If you would not be forgotten, as soon as you are dead and rotten, either write things worth reading, or do things worth writing."

-- Benjamin Franklin

Six Sources of Influence -- By Jo Miller@GHC09

2009-09-30T17:55:00.005-04:00

Our behavior teaches others how to treat us!

Grace Hopper Celebration of Women in Computing 2009 is awesome!
Firstly, it IS amazing to see thousands of "Technical Women" in one single conference. Secondly, it is great to talk with other students or researchers -- you can always get something new and your mind might get refreshed. I'm still feel shy and sometime awkward to talk with strangers, BUT, but, I also can feel my change! Starting a conversation seems not that difficult for me now! Well, in some cases... :P

Jo Miller is actually the very example to show "a person of influence". I want to make my notes public instead of sharing with my laptop. So, here you go!

Miller said that if you want to become a person of influence, you need to make the impression that you ARE someone that has something to say and should be listened to. As an example, she says that at meetings you should arrive early, be prepared with talking points and sit near the main group. Your behaviour teaches people how to treat you.
She also listed out 6 sources of influence:

6. Positional Influence

It comes from your job title and role. Yes, your title does matter to others!
Beyond that, you also need to be prepared with a 30-sec commercial talk including the following contents and speak it out loudly and confidently.

Name
Job title
I'm responsible for ... a, b, c
Come directly to me when you ...

5. Expertise Influence

It comes from your background, qualifications, experiences and expertise.
Ways to build it:
Don't wait for an invitation to speak up on your topics of expertise; Don't downplay yourself;
Do promote your accomplishments;
Present in meetings and lunch & learns; Write articles or papers or a blog; Speak on panels and at conferences.

4. Resources Influence

Having access to the resources you need to do your job well. Best use what you have.
Ways to build it:
Become a strong negotiator; Learn matrixed management; Cross train others in your area; Prioritize your workload, communicate bandwidth constraints; Gain visibility for the importance of your work and the effort it takes; Suggest special projects as developmental opportunities for others.

3. Informational Influence

Being an informational powerhouse who keeps a "finger on the pulse" of business, personnel and organizational issues.
Ways to built it:
Strive to keep a 'finger on the pulse' of the business; Stay current on personnel and organizational issues; Know who other 'informational powerhouses' are; Filter out useful information from gossip or noise; Seek out information about changes before they occur.
Why? This will help you make BETTER decisions and be able to change directions SOONER when necessary.

2. Direct Influence

Be firm, professional and direct when someone's behavior is detrimental to the team or the organization.
Ways to effectively use it:
Be firm, fair and professional; Be direct and concise while delivering tough news; Explain what was unacceptable and why; Focus on a positive vision for the future.
BUT do this for ONLY 1% of the case! Do it in private! Be direct and give the individual specific examples and/or a positive vision for how things will change FOR THEM if they change their behavior.

1. Relationship Influence

Knowing who the KEY people are in your organization, profession, and industry, and building an influential network.
Your network aka your "sphere of influence".

Ref: A full version of the presentation can be found here.

Cognitive Ad Hoc Networks

2009-09-24T11:21:00.003-04:00

A cognitive network is a network with a cognitive process that can perceive current network conditions and then plan, decide, and act on those conditions. The network can learn from these adaptations and use them to make future decisions, all while taking into account end-to-end goals [1].

Ref: [1] Thomas R. W., DaSilva L. A., Mackenzie A. B.; Cognitive Networks. Proc. IEEE DySPAN 2005, Nov 2005, pp 352-360.

.MPKG File Extension

2009-07-30T15:34:00.003-04:00

Meta PacKaGe File on Mac OS X or Linux

Macintosh installer package that contains all the necessary installation files in a single Mac OS X package. It is typically found on *NIX-type (inc. UNIX, LINUX, etc.) systems.

.DMG File Extension

2009-07-30T14:43:00.005-04:00

Disk iMaGe File on Macintosh OS X (corresponding to .ISO or .IMG file on Windows)

Usually, it is used for software installment downloaded from the Internet. When clicking the image file, it is automatically mounted as a virtual disk on the desktop. It could also be opened using Apple Disk Utility just like a real disk.

In most cases, a DMG file is not recognizable on Windows. It may be opened in Daemon Tools as some virtual drive. There are several software that can convert DMG file to a more standard format that can be recognized by Windows. (For further info, search for 'DMG2IMG' or 'DMG2ISO'.)

Wi-Fi on the go

2009-07-29T10:55:00.003-04:00

To get online, of course, you can go to a library, a cafe shop, or some restaurant. The key thing is: you have to sit in the range of an access point / hot spot. What if you want Internet while you are on the move?

An old fashion option is to use cellular modem (cellular PC-card) and plug the card into your laptop. Then you can use your laptop to surf on the Internet.
You can get such a modem from a cellular carrier like Verizon, Sprint, AT&T or T-mobile. The card provides the Internet connection, courtesy of those companies' 3G ("third generation") high-speed cellular data networks. Well, the speed may not be the same as a cable-modem speed, but it is close enough.
In addition, you can use a mobile router that translates the cellular connection into a Wi-Fi one. By doing this, you can share your Internet signal.
Notice that, here, at least one laptop is required (to activate the PC-card).

Now you can have an alternative way which provide you a personal Wi-Fi bubble, a private hot spot, that followed you everywhere you go!
Novatel MiFi 2200, available from Verizon starting in mid-May.
It IS pocket-able -- just triple thick as a credit card. It does provide a personal, portable, powerful, password-protected wireless hot spot. And yes, it still gets its Internet signal the same way those cellular modems do — in this case, converting Verizon’s 3G (high-speed) cellular signal into a Wi-Fi cloud. But, now, you don't need to carry your big laptop. What you need to do is simply put this tiny thing into your pocket!

Well, there is another way: find free Wi-Fi using an easy Wi-Fi radar. It may not work all the time (depends on whether there are any free access points nearby) but it is FREE!
Free access points can be found in a cafe house, a hotel, an airport, an local library, a book store, and maybe some national parks. Plus, there are several cities covered entirely by free wifi-access, like San Francisco, Mountain View, or Chicago. The good news is that Municipal WiFi is popping up in cities across the nation which is free, government sponsored wireless internet in certain areas of a city where people are likely to congregate.

One day in the near future, we would have Internet everywhere just as water, electricity facilities. :-)

Bluetooth

2009-07-06T10:51:00.003-04:00

Name: Bluetooth (name after the tenth-century king Harald I of Denmark, who united dissonant Danish tribes into a single kingdom -- Bluetooth units communications protocols into one universal standard)

Parents: Bluetooth Special Interest Group (SIG)[1][2] & IEEE 802.15 Task group 1, divorced at 2005 and now living with Bluetooth SIG.

Contributions: exchanging data over short distances (10m/50m) from fixed and mobile devices, creating personal area networks (PANs); a wireless alternative to RS232 data cables.

Potential Diseases:
Bluejacking is the sending of unsolicited messages to Bluetooth-enabled devices, essentially harmless (exploit others' Bluetooth connections without their knowledge but no exposure of any data in the victim's handset);
Bluesnarfing is the unauthorized access of information from a wireless device through a Bluetooth connection (exploit others' Bluetooth connections without their knowledge and copy information from the victim's Bluetooth device);

Community Participation:
Pairing; Bluesniping; Piconet Topology

Ref: Bluetooth@wiki

Mobility Models

2009-05-18T13:58:00.004-04:00

Random Waypoint Model (RWP)

Each node chooses uniformly at random a destination point (the 'waypoint') within the deployment region R, and moves toward it along a straight line. Node Velocity is chosen uniformly at random in the interval [v_min, v_max], where v_min and v_max are the minimum and maximum node velocities. When the node arrives at destination, it remains stationary for a predefined pause time, and then starts moving again according to the same pattern.
Individual movement (each node moves independently)
Obstacle-free (move in any subregion of R)
Intentional Movement
Border effect (the long-term node spatial distribution in concentrated in the center of R)
Ref: - Johnson D, Maltz D, Hu Y, Jetcheva J; The Dynamic Source Routing Protocol for Mobile ad hoc Networks (dsr). Internet Draft draft-ietf-manet-dsr-7.txt, 2002, Mobile Ad Hoc Networking Working Group.
- Blough D, Resta G, Santi P; A statistical analysis of the long-run node spatial distribution in mobile ad hoc network. 2004, Wireless Networks 10, pp 543-554.
- Bettstetter C, Resta G, Santi P; The node distribution of the random waypoint mobility model for wireless ad hoc networks. 2003, IEEE Trans. on Mobile Computing 2(3), pp 257-269.

Random Direction Model

Each node chooses a direction uniformly at random in the interval [0, 2PI], and a random velocity in the interval [v_min, v_max]. Then, it starts moving in the selected direction with the chosen velocity. When the node reaches the boundary of R, it chooses a new direction and velocity (or 'bounced back'), and so on.
Individual movement (each node moves independently)
Obstacle-free (move in any subregion of R)
Intentional Movement
Avoid the 'border effect' of RWP -- maintain a uniform node spatial distribution during the simulation time
Ref: - Royer E, Melliar-Smith P, Moser L; An analysis of the optimum node density for ad hoc mobile networks. 2001, IEEE International Conf. on Communications, Helsinki, pp 857-861.
- Pearlman M, Haas Z, Sholander P, Tabrizi S; On the impact of alternate path routing for load balancing in mobile ad hoc networks. 2000, Proc. ACM MobiHoc, Boston, MA, pp 3-10.

Brownian-like Motion Model (Drunkard-like Model)

The position of a node at a given time step depends (in a certain, probabilistic, way) on the node position at the previous step. No explicit modeling of movement direction and velocity is used in this model.
Individual movement (each node moves independently)
Obstacle-free (move in any subregion of R)
Nonintentional Movement
Ref: - Santi P, Blough D; The critical transmitting range for connectivity in sparse wireless ad hoc networks. 2003, IEEE Trans. on Mobile Computing 2(1), pp 25-39.

Map-based Mobility Models

Freeway Mobility Model -- Freeway scenario
Several freeways, located in the deployment region, composed of a varying number of lanes in both directions; Nodes, located on a freeway, moving with a random velocity (temporally dependent on its previous velocity); Safety distance; etc.
Ref: - Bai F, Sadagopan N, Helmy A; Important: a framework to systematically analyze the impact of mobility on performance of routing protocols for ad hoc networks. 2003, Proc. IEEE Infocom, SF, CA, pp 825-835.
Manhattan Mobility Model -- Urban scenario
Horizontal and vertical streets; Nodes, moving along the streets in both directions; when arriving at an intersection, randomly chooses whether to continue moving along the same direction, or to take a left/right turn; Velocity of a node depends on that at the previous time step; etc.
Ref: - Bai F, Sadagopan N, Helmy A; Important: a framework to systematically analyze the impact of mobility on performance of routing protocols for ad hoc networks. 2003, Proc. IEEE Infocom, SF, CA, pp 825-835.
Obstacle Mobility Model -- Building & Pathways scenario
Obstacles (Buildings) in the environment; Pathways, connecting defferent buildings; Nodes, moving along the pathways; radio signal is obstructed by those obstacles; etc.
Ref: - Jordosh A, Belding-Royer E, Almeroth K, Suri S; Towards realistic mobility models for mobile ad hoc networks. 2003, Proc. ACM Mobicom, pp 217-229.

Group-based Mobility Model

Nodes are randomly assigned to one of the Group Leaders, thus forming groups. The leaders are randomly distributed in R and its group members are randomly located in its neighborhood. Then the group leader moves according to some mobility model and its group members 'follow' the leader with a speed and direction that are a random perturbation of those of its leader. When two groups cross, any group member can leave its group and join the other with a certain probability.
Ref: - Hong X, Gerla M, Pei G, Chiang C; A group mobility model for ad hoc wireless networks. 1999, Proc. ACM MSWiM, Seattle, WA, pp 53-60.
- Wang K, Li B; Group mobility and partition prediction in wireless ad hoc networks. 2002, Proc. IEEE International Conf. on Communications, NY, pp 1017-1021.

Ref: Santi P; Topology Control in Wireless Ad Hoc and Sensor Networks (Section 2.4). 2006

Conformal Geometry (保形几何)

2009-05-14T11:12:00.002-04:00

In Mathematics, Conformal Geometry is the study of the set of angle-preserving ("conformal") transformations on a Riemannian manifold or pseudo-Riemannian manifold. [wiki]

The main invariant in conformal geometry is the angle between two directions. This definition of conformal geometry is valid for Euclidean spaces of arbitrary dimension. [1]

[1] G.V.Bushmanova; Conformal Geometry, in Hazewinkel, Michiel, 2001, Kluwer Academic Publishers.

An n-dimensional space with notions of distance and angle that obey the Euclidean relationships is called an n-dimensional Euclidean space. An essential property of a Euclidean space is its flatness. An example of such a relationship is that the sum of the angles in a triangle is always 180 degrees. [wiki]

Point Graph

2009-05-13T13:43:00.005-04:00

The main weakness of the point graph model is the assumption of perfectly regular radio coverage. Such an assumption is quite realistic in open air, flat environments. While, ad hoc and sensor networks are likely to be used in very different situations, such as indoor or urban scenarios (ad hoc), or under harsh conditions (sensor).
However, the point graph model is still widely used in the study of ad hoc network properties since including all those interference or influence of walls or ... would make the network model too complex and scenario dependent. The results obtained using the point graph model are useful to some extent, but become less and less significant from a practical point of view as the actural radio coverage area is more and more irregular.

Continuum Percolation Graphs

A Unit Disk Graph (UDG) is a graph in which every two nodes are connected with an edge iff they are at distance at most 1.
UDGs corresponds to network models with homogeneous rage assignment, i.e. all the nodes have the same transmitting range.

Geometric Random Graphs (GRG)

A set of points is distributed according to some probability distribution in a certain region. Points are then connected according to some rule (e.g. connect to all the points within distance r, or connect to the k closest nodes, etc.), generating a geometric random graph.
Notes: traditional random graph theory is not very useful in the theoretical analysis of fundamental ad hoc network properties coz a fundamental assumption in this model is that the probabilities of edge occurrence in the graph are independent, which is not the case in the context of wireless ad hoc networks.
Several asymptotic properties can be studied in a GRG model, including:
min & max node degree; longest nearest neighbor link; length of the shortest path; total edge length; number of connected components; critical neighbor number of the k-neighbors graph; total edge length of DT; length of the longest edge of MST; total edge length of MST; etc.

Ref: Santi, P.; Topology Control in Wireless Ad Hoc and Sensor Networks (Section 2.2 + Appendix B), 2006

Proximity Graphs

2009-04-28T11:57:00.005-04:00

Proximity Graphs are a class of graphs introduced in the theory of Computational Geometry that are based on proximity relationships between nodes. A proximity graph is simply a graph in which two vertices are connected by an edge if and only if the vertices satisfy particular geometric requirements.
It represents neighbor relationships between geometric points in the Euclidean plane. That is, given a set of points in the plane, put edges between points that satisfy a particular neighbor relationship with each other to form a graph.

Ref: - Lecture Notes from Math @ SFSU

K-neighbors Graph

Given a set N of points in the d-dimensional space (d=1, 2, 3), and an integer k>=1, the k-neighbors graph is the directed graph where an edge (u, v) is presented iff v is one of the k closest neighbors of node u.

Delaunay Triangulation (DT)

Given a set N of points in the plane, DT of N is the unique triangulation of N such that the circumcircle of every triangle contains no points of N in its interior.
Notes: A Triangulation of N is a maximal planar subdivision whose node set is N. A Maximal Planar Subdivision of N is a planar graph s.t. no edge connecting two nodes in N can be added without compromising graph planarity.

Relative Neighborhood Graph (RNG)

A graph that has an edge between u and w if there is no node v such that
max{uv, wv} <= uw. [wiki] i.e. there is an edge between u and w iff there is
no node v in Lune(u, w), where Lune(u, w) is the intersection of the circle about u
with a radius of |uw| and the circle about w with a radius of |uw|.
Ref: - Jaromczyk, J.W.; Toussaint, G.T.; Relative neighborhood graphs and their relatives, (1992)
Supowit, K.J.; The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees, (1983)

Gabriel Graph (GG)

A graph with vertex set V in which any points P and Q in V are adjacent
precisely if they are distinct and the closed disc of which line segment PQ is a
diameter contains no other elements of V. i.e. there is an edge between P and Q
in GG iff the disk obtained using PQ as its diameter does not contain any vertex
from V. [wiki]
GG is a subgraph of DT. It can be found in linear time if the Delaunay triangulation is given. GG contains as a subgraph the Euclidean MST and the nearest neighbor graph.
EMST ≤ RNG ≤ GG ≤ DT
Ref: - Matula, D. W.; Sokal, R. R. Properties of Gabriel graphs relevant to geographic variation research and clustering of points in the plane, Geogr. Anal. 12: 205-222 (1980).
- Lecture Notes from CS @ JHU

Yao Graphs (YG)

The basic idea underlying the Yao graphs is to cut the space around each node into sectors of equal angle and to connect each node to the nearest neighbor in each of its sectors.
At each node u in V, any k equally seperated rays originated at u define k equal sectors. In each sector, choose the shortest directed edge (u, w) in G, if any, and add the correspondent directed edge in YG_k.
Ref: - Lecture Notes from CS @ JHU.
- Yao graphs and MST, J. Caceres et al.

Ref: - Santi, P.; Topology Control in Wireless Ad Hoc and Sensor Networks (Appendix A), 2006

Spanner

2009-04-28T11:38:00.004-04:00

A geometric spanner or a k-spanner graph or a k-spanner is a weighted graph over a set of points as its vertices which for every pair of vertices has a path between them of weight at most k times the spatial distance between these points for a fixed k. The parameter k is called the stretch factor or dilation factor of the spanner.

It was proven that the problem of finding a spanner in the Euclidean plane with minimal dilation over n points with at most m edges in NP-hard.[wiki]

Ref: - David Eppstein, Spanning Trees and Spanners, Tech. Report (1996)
- Giri Narasimhan, Michiel Smid, Geometric Spanner Networks, Cambridge University Press (2007) ISBN 0521815134

sort in STL

2009-03-08T17:00:00.003-04:00

sort is a function in STL that takes two random-access iterators, the start and the end, as arguments and performs a comparison sort on the range of elements between the two iterators, front-inclusive and end-exclusive. The underlying algorithm is (usually) introsort, which is a combination of quicksort quicksort and heapsort (the implementation details are not mandated). Whatever the implementation, the complexity is guaranteed to be O(nlogn) comparisons in the worst case.

SGI STL specification of sort() function

Note that elements in the map container are sorted from lower to higher key value internally on construction. Thus, by taking advantage of such a feature, given an array of elements, we can insert each element and its corresponding index into a map container, and then use an iterator to read them out in order.
multimap is a map container that allows different elements to have the same key value. An example of multimap can be found here.

Authorship

2009-02-25T17:30:00.000-05:00

Hmm, it's quite interesting to hear that different departments did has different policy for authorship.

Some departments may publish a paper with a loooong author list, while some may have one with only one or two authors.

Some departments think the most important author (major) should be the first one, and the second would be the second important, and so on. While some may take the first (and the last) as major author(s) and 'ignore' the one in the middle... :-)

Dr. L told me that, in our area, theoretical computer science, first author would be major author if he did most of the job, OR alphabetical order would be use if everyone did part of the job. He would like to put student name prior to his.
Plus, in his view, when judging tenure for an assistant professor, the number of first-author papers are not quite important since one can comment on what is done by him and who is under his advise. The grant he got plays a significant role in some universities... (hmm, this is quite similar to Chinese...)

HTTP/1.1 vs HTTP/1.0

2008-12-14T17:53:00.006-05:00

HTTP Persistent Connection in /1.1

(Also called HTTP keep-alive, or HTTP connection reuse)
i.e. using the same TCP connection to send and receive multiple HTTP requests/responses, as opposed to opening a new one for every single request/response pair.

Using persistent connections is very important for improving HTTP performance. There are several advantages, including:

Network friendly. Less network traffic due to fewer setting up and tearing down of TCP connections.

Reduced latency on subsequent request. Due to avoidance of initial TCP handshake

React to congestion appropriately. Long lasting connections allowing TCP sufficient time to determine the congestion state of the network. Note that each new connection will always start from slow start and may not have enough time to enter congestion avoidance if it is open only for a short while.

The advantages are even more obvious with HTTPS or HTTP over SSL/TLS. There, persistent connections may reduce the number of costly SSL/TLS handshake to establish security associations, in addition to the initial TCP connection set up.

In HTTP/1.1, persistent connections are the default behavior of any connection.

Pipelining in 1.1

Normally, HTTP requests are issued sequentially, with the next request being issued only after the response to the current request has been completely received.

Allow multiple HTTP requests to be written out to a socket together without waiting for the corresponding responses. The requester then waits for the responses to arrive in the order in which they were requested. --> reduce the page response time, especially over high latency connections

Possible to pack several HTTP requests into one TCP/IP packet. --> reduce the number of TCP/IP packets, which naturally reduces the burden on IP routers and networks and benefits the whole internet

Pipelining can only be done when reusing an existing keep-alive connection.

Comparison of VoIP software

2008-12-09T22:34:00.001-05:00

Voice over Internet Protocol

Comparison of software

NASA Tests First Deep-Space Internet

2008-11-22T09:22:00.005-05:00

News from NASA JPL lab

NASA has successfully tested the first deep space communications network modeled on the Internet, using DTN. They called "Disruption-Tolerant Networking", which should be same to "Delay-Tolerant Networking", I believe...

P.S. In the mean time, Xuan told me that British Government exploded bunch of files documenting UFO related stuffs.
Here is a link from Google-Video.
British UFO Files
... This film is based on Government files documenting EYE witness accounts of unexplained events that have occurred in the skies of Britain during the last 60 years...

Omg, “during the last 60 years", that means, UFO first appeared in 1940's!!
Sounds interesting... Is there any relationship between these two issues?! I'm wondering...

FXP -- File eXchange Protocol

2008-11-21T12:55:00.006-05:00

File eXchange Protocol (FXP) allows you to copy files from one FTP server to another FTP server (two remote hosts) using an FXP client.

FXP removes the middle step of transferring files from one FTP server to your local machine then to the second FTP server. The data transfer rate is also independent of your own internet connection speed as it is based on the connection speed between the two hosts, which is usually faster than a user's own Internet connection. Since FXP provides a direct connection between the two hosts, users are unable to see standard FTP information in their client software such as transfer progress and connection speed. Usually you will see only a successful or failed transfer message.

To use FXP, the remote servers must support PASV mode and allow PORT commands to foreign hosts.

User-PI - Server A (Dest)     User-PI - Server B (Source)
------------------            ------------------
C->A : Connect                C->B : Connect
C->A : PASV
A->C : 227 Entering Passive Mode. A1,A2,A3,a1,a2
                             C->B : PORT A1,A2,A3,a1,a2
                             B->C : 200 Okay
C->A : STOR                   C->B : RETR

TFTP - Trivial File Transfer Protocol

2008-11-19T10:22:00.005-05:00

Simple, designed for quickly file transfer, requires only basic IP and UDP on port 69.
Good for bootstrap time on a diskless workstation.
No security for TFTP.

UDP provide no connection establishment and termination.
Thus, in TFTP, RRQ/WRQ, ACK/ERROR messages are used to establish connection for the blocks of data belonging to the same file.
No special message for termination. Termination is accomplished by sending the last block of data which is < 512 bytes.

UDP does not have any mechanism for flow and error control.
In TFTP, flow control is achieved by numbering the data blocks and waiting for an ACK before the next data block is sent.
The TFTP error-control mechanism is symmetric, which means that sender and receiver both use time-outs, i.e. time-out for not only data messages byt also for ack messages.
Receiver uses UDP checksum to detect data corruption and discards the block if damaged. No negative ack in TFTP. Sender will retransmit the block after time-out period.

Sorcerer's Apprentice Bug
Happens if ACK message is not lost but dealyed. Then, every succeeding block is sent twice and every succeeding ack is received twice.

TFTP uses the well-known port 69 for the initial connection and an ephemetal port for the remaining communication. The reason is that communication between a client and a server can be quite lengthy (even minutes). If a server uses the well-known port number to communicate with a single client, no other clients can use these services during that time!

FTP - File Transfer Protocol

2008-11-19T09:46:00.005-05:00

FTP is in Application layer and each time it opens 2 TCP connections: one for control and one for data.

In control connection, server issues a passive open on port 21 and wait for a client. This connection will be persistent over the whole session.
FTP uses NVT ASCII character set instead of command code, i.e. each command or response is one short line ended by CR and LF. It is sort of wasting network resource but it makes programming and debugging to be easier.

In data connection, client issues a passive open, sends its ephemeral port number to server using PORT via control connection and server then issues an active open use port 20. An alternative method is using PASV command: client asks server to choose a port number, server does a passive open and sends the port number in response, and client issues an active open using that port number.
Such a connection will be open and closed upon each file transfer.
Notice that in the first method, server does NOT open the connection upon receiving PORT w/ the port number of client but prepares itself for issuing an active open. Server will open the data connection when receiving a request via control connection and close the data connection when finishing the whole list/file.
Before sending a file, 3 attributes (file type, data structure and transmission mode) need to be defined through the control connection.

Limit on total number of TCP connections in OS

2008-11-06T12:05:00.002-05:00

By using non-persistent parallel connection, a HTTP application could be faster coz it creates multiple TCP connections for a web page and embedded objects in that page. But why there exists a limit on the total number of TCP connections in OS level?

Think about congestion control.
Suppose there are 40 TCP connections between a pair of client and server. One packet is lost. Then what happens?
Only one connection will be slow down according to congestion control. All the others still keep sending in a higher speed!

There is a term called "TCP friendly". It designed for applications to vary their sending rate in response to congestion.

TCP-Friendly Rate Control (TFRC) is a congestion control mechanism designed for unicase flows operating in an Internet environment and competing with TCP traffic. It is designed for applications that use a fixed packet size, and vary their sending rate in packets per second in response to congestion. TFRC is a receiver-based mechanism, with the calculation of the congestion control information (i.e., the loss event rate) in the daat receiver rather in the data sender. This is well-suited to an application where the sender is a large server handling many concurrent connections, and the receiver has more memory and CPU cycles available for computation. [Adapted from RFC 3448 - TCP Friendly Rate Control (TFRC): Protocol Specification]

Another related web page is here.

Murphy's law

2008-11-05T10:24:00.002-05:00

Murphy's law is an adage in Western culture that broadly states, "if anything can go wrong, it will." It is also cited as: "If there's more than one possible outcome of a job or task, and one of those outcomes will result in disaster or an undesirable consequence, then somebody will do it that way"; "Anything that can go wrong, will," the similar "Whatever can go wrong, will go wrong," or, "Whatever can go wrong will go wrong, and at the worst possible time, in the worst possible way." In a less dramatic fashion, the law can be expressed as "Anything that has a probability of happening greater than 0 can and will happen. No exceptions."

It IS a funny law but the point is that its spirit embodies the principle of defensive design (sometimes referred to as a "Murphy-proofing" procedure) -- anticipating the mistakes the end-user is likely to make.

P2P or P2SP?

2008-11-02T12:30:00.004-05:00

点对点技术（peer-to-peer，简称P2P）又称对等互联网络技术，是一种网络新技术，依赖网络中参与者的计算能力和带宽，而不是把依赖都聚集在较少的几台服务器上。P2P网络通常用于通过Ad Hoc连接来连接节点。这类网络可以用于多种用途，各种文件共享软件已经得到了广泛的使用。P2P技术也被使用在类似VoIP等实时媒体业务的数据通信中。

纯点对点网络没有客户端或服务器的概念，只有平等的同级节点，同时对网络上的其它节点充当客户端和服务器。这种网络设计模型不同于客户端-服务器模型，在客户端-服务器模型中通信通常来往于一个中央服务器。

P2S（Peer to Sever），即点对服务器技术，是最经典的一种下载协议。“点”(Peer)即网络节点或终端，通常可以理解为用户计算机。P2S协议又分HTTP（Hyper Text Transportation Protocol，译为超文本传输协议）与FTP（File Transportation Protocol，文件传输协议）两种类型。IE自带的下载软件采用的是P2S技术。

P2SP（Peer to Sever&Peer），即点对服务器和点技术，是一种下载协议。“点”(Peer)即网络节点或终端，通常可以理解为用户计算机。P2SP整合了P2P与P2S技术。在稳定性和速度方面，P2SP协议比传统的P2P或P2S有了较大的提高。

迅雷采用一种类似P2P的方式来结合和取代传统下载方式，透过后台上传服务器及客户端电脑上通过迅雷下载的资料（用户可进行限制），使得传统HTTP/FTP等协议下的资料以P2P模式传输，能够获得较高的下载速度。
用户使用迅雷打开一个，例如URL等待下载地址时，迅雷会将目标档案资料发送至服务器进行比对检索，并在短时间内返回大量拥有该档案的目标电脑。这些目标电脑可以是提供该档案的传统 HTTP/FTP服务器，亦可能是仅仅储存有该档案而安装了迅雷的普通电脑。随后，迅雷建立大量连接从这些目标电脑上下载目标档案，形成了P2P的下载方式，故此不积压于服务器的负荷能力。

Linearity of Expectation

2008-10-26T12:07:00.002-04:00

The expectation of the sum of two random variables is the sum of their expectations, that is,

E[X+Y] = E[X] + E[Y]

whenever E[X] and E[Y] are defined. We call this property linearity of expectation, and it holds even if X and Y are NOT independent. It also extends to finite and absolutely convergent summations of expectations. Linearity of expectation is the key property that enables us to perform probabilistic analyses by using indicator random variable.

c.f. When two random variables X and Y are independent and each has a defined expectation,

E[XY] = E[X]E[Y]

A (discrete) random variable X is a function from a finite or countably infinite sample space S to the real numbers. It associates a real number with each possible outcome of an experiment, which allows us to work with the probability distribution induced on the resulting set of numbers. Random variables can also be defined for uncountably infinite sample spaces, but they raise technical issues that are unnecessary to address for our purposes. Henceforth, we shall assume that random variables are discrete.
The expected value (or, synonymously, expectation or mean) of a discrete random variable X is
E[X] = \sum_{x}{x Pr[X=x]}
which is well defined if the sum is finite or converges absolutely.

Good for your eyes ^^

2008-10-25T14:32:00.002-04:00

保护视力色

FAFBE6 杏仁黄 250,251,230
FFF2E2 秋叶褐 255,242,226
FDE6E0 胭脂红 253,230,224
F3FFE1 芥末绿 243,255,225
DAFAFE 天蓝 218,250,254
E9EBFE 雪青 233,235,254
EAEAEF 灰 234,234,239
FFFFFF 银河白 255.255.255

改变窗口颜色

第一步，在桌面上点击鼠标右键，依次点击“属性(properties)”、“外观(appearance)”、“高级(advanced)”按钮。
第二步，在打开的“高级(advanced)”对话框中，在“项目(items)”下拉列表里选择“窗口(windows)”。
第三步，再打开右边对应的“颜色(color)”列表，选择其中的“其他(others)”一项，在打开的对话框里，把“色调(Hue)”的参数设置为85，把“饱和度(Sat)”参数设置为90，把“亮度(Lum)”参数设置为205，单击“添加到自定义颜色(Add tocustom colors)”，点击“确定”退出设置。

IE的网页背景

打开IE，点击“工具(TOOLS)”，点“INTERNET选项(INTERNET OPTIONS)”，点右下角的“辅助功能 (Assessibility)”，然后勾选“不使用网页中指定的颜色(ignore colors specifiedon web pages)”，然后点“确定”退出。

PDF格式背景

点击编辑 ->首选项->辅助工具
选中“替换文档颜色”和“自定义颜色”，将背景颜色改成你想要的背景颜色

1st Congestion Collapse

2008-10-21T14:56:00.001-04:00

1986 - first congestion collapse Observed!

-- Omg, I was just entering my primary school at that time...

P2P File Sharing: BT, eMule...

2007-11-12T17:23:00.000-05:00

Yesterday, when I use bt and emule to download , some questions jumped out -- "How to locate content in other peers using these software" and "What is the difference between BT and eMule". Well, first, let me read Network text for some hints.

--Partly cited from Charper 2: Application Layer

P2P file sharing is a compelling content distribution paradigm because all content is transferred directly between ordinary peers without passing through third-party server. It still relies on the client-server paradigm. All peers must be capable of running both the client and server sides of the file transfer protocol.

In a P2P file-sharing system, there is typically a large number of connected peers, with each peer having objects to share. If peer X is interested in obtaining a particular object, then it must have a way of determining the IP addresses of the connected peers that have copies of the desired object. Now, there are mainly three architectures for locating content.

1. Centralized Directory

Representative application: Napster.

In this manner, there is a large server (or server farm) to provide the directory service, that is, it collects information about available content to share in each active peer and thereby creating a centralized, dynamic database that maps each object name to a set of IP addresses. When an active peer obtains a new object, or removes an object, it informs the directory server so that server can update its database. Also, server must periodically ping to make sure a child peer is still alive.

Drawback: the salient one is that the P2P application is only partially decentralized. The file transfer between peers is decentralized, but the process of locating content is highly centralized, which will be the performance bottleneck of the whole system.

2. Query Flooding

Representative application: Gnutella.

In Gnutella, peers send Gnutella Query message to neighboring peers in the overlay network over the pre-existing TCP connections. All neighbors check whether the keyword matches any of the files available for sharing, and if there is a match, it sends back a QueryHit message. In the meantime, they forward the message to all of their neighbors, which in turn check the match and forward the message to all of their neighbors, and so on. This process is referred to as Query Flooding. In practice, to reduce the query traffic that is dumped into the Internet, Gnutella uses Limited Scope Query Flooding, which localize the flooding to a region of the overlay network. To solve Bootstrap problem (peer must first find some other peer that is already in the overlay network), client maintains a list of peers that are often up in the Gnutella network or contacts with a Gnutella site that maintains such a list.

Drawback: it uses a full distributed architecture, but only locates content in nearby peers in the overlay network, where "nearby" means within a small number of hops.

3. Exploiting Heterogeneity

Representative application: KaZaA.

KaZaA borrows ideas from both Napster and Gnutella. It resembles Gnutella in the sense that it does not use a dedicated directory server. However, unlike Gnutella, the peers in KaZaA are not equal -- the peers with high bandwidth connections and high Internet connectivity are designed as group leaders and maintain a database that includes the identifiers of all the files its children are sharing. In contrast with Nepster, a group leader is not a dedicate server, instead, it is an ordinary peer. When receiving a Query message, each group leader not only tracks the content of its children, but also forwards the query to other group leaders to which it is connected. By this means, the group leaders create a network that resembles a Gnutella network, and KaZaA shares content information among the various groups.

KaZaA also employs a number of features to improve its performance. These techniques include: Queue Management at Server and Client (Frequent uploaders can get priority in server queue), Parallel Downloading (Downloading portions of the file from different peers in parallel), Content Hash.

Now, come back to my previous question. How are BT and eMule doing?

The two application can do better than KaZaA when downloading large files. The salient difference from KaZaA is that the two both cut a large file into pieces and use DHT to locate it.

DHT introduce a hash function to map the object being searched for to a unique identifier, distributing the range of the hash function among all nodes in the network. Thus, each node must "know about" at least one copy of each object that hashes within its range (when one exists). For each object, nodes whose ranges cover that object must be reachable via a "short" path by the arbitrarily chosen querier nodes and by nodes that have copies of the object. Note that DHT mechanism should be fully distributed s.t. no centralized point that bottlenecks throughput or can act as single point of failure.

In BitTorrent, file.torrent is a descriptor of objects, which includes file name, file length, hash identifier and URL of tracker. Client first gets file.torrent, then uses the URL of tracker to access the tracker to get the list of peers, and downloads the file from these peers in parallel.

In eMule, each client must be connected to a server to enter the network. When connecting your client to a server, the server will assigns your client a High-ID or Low-ID according to whether other clients can freely connect to your client. Once connected to the network, the client can search for keywords in filenames. A search can either be local search (searches only the server you are connected to - quicker but fewer matches) or global search (searches all the servers within the network - slower but more results). Recent version of eMule uses Kademlia to solve the Bootstrap problem, a network independent to classic servers based eD2k and improve scalability.

References:

More information about eMule

A P2P Systems Tutorial (PPT file)

Basic Terms of Graphs

2007-05-20T17:14:00.001-04:00

Basicly, what is a graph?

A graph G = (V, E) consists of two types of elements, where V is the set of vertices or nodes and E is the set of pairs of distinct vertices, called edges or lines.[Wiki]

The vertices belonging to an edge are called the ends, endpoints, or endvertices of the edge. Two vertices u and v are considered adjacent if an edge exists between them; these two vertices are said to be incident to that edge, or, equivalently, that edge incident to those two vertices.

Normally, we use n to denote the number of vertices |V|, namely the order of a graph, and use e to denote the number of edges |E|, namely the size of a graph. The degree of a vertex is the number of other vertices connected to it by edges. The distance dG(u, v) between two (not necessary distinct) vertices u and v in a graph G is the length of a shortest path between them.

A graph is k-connected if and only if it contains k internally disjoint paths between any two vertices. That is, the minimum number of vertices needed to be removed to disconnect G is k. A component is a maximally connected subgraph; and a biconnected component is a maximal set of edges in which any two members lie on a common simple cycle.

A dominating set of a graph is a vertex subset whose closed neighborhood includes all vertices of the graph. A vertex v dominates another vertex u if there is an edge from v to u. A vertex subset V dominates another vertex subset U if every vertex in U is adjacent to some vertex in V. The minimum size of a dominating set is the domination number.

An isolated vertex is a vertex not incident to any edges. An independent set, or stable set or staset, is a set of isolated vertices, i.e., no pair of vertices is adjacent. The graph induced by any independent set is an empty graph. The independence number α(G) of a graph G is the size of a largest independent set of G.

A matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex. A maximum matching is a matching that contains the largest possible number of edges. There may be many maximum matchings. The matching number of a graph is the size of a maximum matching. A perfect matching is a matching which covers all vertices of the graph.

The complement of a graph G is a graph with the same vertex set as G but with an edge set such that xy is an edge in if and only if xy is not an edge in G.

Two graphs G and H are said to be isomorphic, denoted by G ~ H, if there is a one-to-one correspondence, called an isomorphism, between the vertices of the graph such that two vertices are adjacent in G if and only if their corresponding vertices are adjacent in H. Likewise, a graph G is said to be homomorphic to a graph H if there is a mapping, called a homomorphism, from V(G) to V(H) such that if two vertices are adjacent in G then their corresponding vertices are adjacent in H.

Walk, Path, Cycle

A walk is an alternating sequence of vertices and edges, beginning and ending with a vertex, in which each vertex is incident to the two edges that precede and follow it in the sequence, and the vertices that precede and follow an edge are the endvertices of that edge. A walk is closed if its first and last vertices are the same, and open if they are different. A trail is a walk in which all the edges are distinct.

A path is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. The first vertex is called the start vertex and the last vertex is called the end vertex. Both of them are called end or terminal vertices of the path. The other vertices in the path are internal vertices.

A cycle is a path such that the start vertex and end vertex are the same. Notice however that unlike paths, any vertex of a cycle can be chosen as the start, so the start is often not specified.

Traditionally, a path referred to an open walk; while a cycle is equivalent to a closed walk.

A path with no repeated vertices is called a simple path, and cycle with no repeated vertices aside from the start/end vertex is a simple cycle.
Two paths are independent (alternatively, internally vertex-disjoint) if they do not have any internal vertex in common.

The length of a walk is the number of edges that the path uses, counting multiple edges multiple times. For an open walk, l = n–1, where n is the number of vertices visited (a vertex is counted each time it is visited). For a closed walk, l = n (the start/end vertex is listed twice, but is NOT counted twice).

A loop is a cycle of length 1, i.e. an edge whose endvertices are the same vertex, e.g. (u, u).
A cycle of length 2 is a pair of digons (multiple edges).
A cycle of length 3 is called a triangle.
An edge is multiple if there is another edge with the same endvertices, e.g. (u, v) and (v, u); otherwise it is simple.

A path or cycle is Hamiltonian (or spanning) if it uses all vertices exactly once. A graph that contains a Hamiltonian path is traceable.
A trail or cycle is Eulerian if it uses all edges precisely once. A graph that contains an Eulerian trail is traversable.

Two paths are internally disjoint (some people call it independent) if they do not have any vertex in common, except the first and last ones.

Subgraphs

A subgraph of a graph G is a graph whose vertex and edge sets are subsets of those of G. In the other direction, a supergraph of a graph G is a graph that contains G as a subgraph.

A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G.

A subgraph H of a graph G is said to be induced if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has the most edges that appear in G over the same vertex set. If H is chosen based on a vertex subset S of V(G), then H can be written as G[S] and is said to be induced by S.

Tree

A tree is a connected acyclic simple graph. A vertex of degree 1 is called a leaf. A subtree of the tree T is a connected subgraph of T. A forest is an acyclic simple graph. A subforest of the forest F is a subgraph of F.

A spanning tree is a spanning subgraph that is a tree. Every graph has a spanning forest. But only a connected graph has a spanning tree.

A special kind of tree called a star is $K_{1,k}$. An induced star with 3 edges is a claw.

A k-ary tree is a rooted tree in which every internal vertex has k children. An 1-ary tree is just a path. A 2-ary tree is also called a binary tree.

Cliques

A complete graph of order n is a simple graph with n vertices in which every vertex is adjacent to every other. A clique is a complete subgraph in a graph. A k-clique is a clique of order k. A maximal clique is a clique that is not a subset of any other clique.

The clique number of a graph G is the order of a largest clique in G.

Important graphs

Undirected / Directed Graph
edges are unordered or ordered pairs of vertices respectively
In a directed graph, an arc e=(u, v) is considered to be directed from u to v.
Weighted Graph
each edge is associated with some value, variously called its cost, weight, length or other term depending on the application
Acyclic / Unicyclic / Pancyclic Graph
A graph is acyclic if it contains no cycles; unicyclic if it contains exactly one cycle; and pancyclic if it contains cycles of every possible length (from 3 to the order of the graph).
Directed Acyclic Graph (dag / DAG)
a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v
Every directed acyclic graph corresponds to a partial order on its vertices.
A simple directed acyclic graph:
DAGs can be considered to be a generalization of trees in which certain subtrees can be shared by different parts of the tree.
Simple / Multigraph / Pseudograph Graph
A graph is a simple graph if it has no multiple edges or loops, a multigraph if it has multiple edges, but no loops, and a multigraph or pseudograph if it contains both multiple edges and loops (the literature is highly inconsistent).
When stated without any qualification, a graph is almost always assumed to be simple.
Complete Graph
each pair of vertices is joined by an edge, that is, the graph contains all possible edges
Bipartite Graph
the vertices can be divided into two sets, W and X, so that every edge has one vertex in each of the two sets
Complete Bipartite Graph
the vertex set is the union of two disjoint subsets, W and X, so that every vertex in W is adjacent to every vertex in X but there are no edges within W or X
The complete bipartite graph with partitions of size |W| = m and |X| = n is denoted Km,n.
Planar Graph
a graph that can be drawn in a plane with no crossing edges (i.e., embedded in a plane)
A tree is necessarily a planar graph.
Unit Disk Graph
A graph formed from a collection of points in the Euclidean plane, in which two points are connected if their distance is below a fixed threshold.
Unit disk graphs have been used in computer science to model the topology of ad-hoc wireless communication networks.
It is NP-hard to determine whether a graph, given without geometry, can be represented as a unit disk graph.
Unit Distance Graph
A graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one.
Unlike planar graphs, edges of unit distance graphs are allowed to cross each other.
Every unit distance graph is a unit disk graph, but the converse is not true.

Create a Research Poster

2007-04-03T11:59:00.001-04:00

Suggestions on how to propose/create a research poster

Minimum vs Minimal

2007-03-30T14:57:00.000-04:00

[Comments from Dr.Lloyd]

We need to be careful with this word.
Recall that Minimal can often mean a local minimum whereas Minimum is more of a global concept.
To avoid confusion, it is almost always best to use minimum unless you are really sure that minimal is what is needed.

Context Switch

2007-03-09T16:57:00.000-05:00

Context Switch

A context switch is storing and restoring the state (context) of a process such that multiple processes can share a single CPU resource. The context switch is an essential feature of a multitasking operating system. [Wiki]

The state of the process includes all the registers that the process may be using in future. Specifically, they are: the value of the Program Counter (PC), Stack Pointer (SP) and Frame Pointer (FP) or it might involve resetting the MMU to make a different set of memory pages available. Often, all the data that is necessary for state is stored in one data structure, called a Process Control Block (PCB). [Dict]

In order to switch processes, OS saves the state of the first process in its PCB. After that, OS now loads another process, restores its context (in doing so, the PC of the new process is loaded), and thus execution can continue in the new process.

Program Counter (PC)

A register contains the address of the next instruction to be executed. The PC is automatically incremented after each instruction is fetched to point to the following instruction.

Stack Pointer (SP)

A register or variable pointing to the top of a stack. If the stack is a "full" stack the SP points to the most recently pushed item, else if it is an "empty" stack, the PS points to the first empty location, where the next item will be pushed.

Memory Management Unit (MMU)

A hardware device or circuit that supports virtual memory and paging by translating virtual addresses (the range of addresses used by the processor) into physical addresses.

setjmp / longjmp [Linux man page]

NAME

setjmp, sigsetjmp -- save stack context for non-local goto
longjmp, siglongjmp -- non-local jump to a saved stack context

SYNOPSIS

#include <setjmp.h>

DESCRIPTION

setjmp() and longjmp() are useful for dealing with errors and interrupts encountered in a low-level subroutine of a program.

setjmp() saves the stack context/environment in env for later use by longjmp(). The stack context will be invalidated if the function which called setjmp() returns. sigsetjmp() is similar to setjmp(). If savesigs is non-zero, the set of blocked signals is saved in env and will be restored if a siglongjmp() is later performed with this env.

--Why? Because what we saved is the SP and FP of the calling procedure. If that procedure returns, then when you restore the SP and FP, the stack might be in a different state than before. For example:

main() routine is first called. The stack is initialized, so do SP, FP and PC.
main() calls a(). It first pushes the arguments on the stack in reverse order, and then pushes the return PC on the stack, and the old FP. The FP and SP then are changed to make an empty stack frame for a().
The first thing that a() does is allocate room for its local variables. Then it calls setjmp(), which saves the current state of the registers. In other words, it saves the current values of SP, FP, and PC.
Now a() returns to main(). The stack looks as the very start, except that env is initialized to the state of the machine when a() was called.
Then main() calls b(). In b(), longjmp() is called. The registers are restored to their values when a() called setjmp(), and the PC returns from setjmp() in a().

--Did you see the problem? Yes. The stack is in a bad state. When we try to use the pointer to the arguments of a(), it points to the arguments of b() actually, which dumps core.

longjmp() restores the environment saved by the last call of setjmp() with the corresponding env argument. After longjmp() is completed, program execution continues as if the corresponding call of setjmp() had just returned the value val. longjmp() cannot cause 0 to be returned. If longjmp is invoked with a second argument of 0, 1 will be returned instead. siglongjmp() is similar to longjmp() except for the type of its env argument. If the sigsetjmp() call that set this env used a non-zero savesigs flag, siglongjmp() also restores the set of blocked signals.

RETURN VALUE

setjmp() and sigsetjmp() return 0 if returning directly, and non-zero when returning from longjmp() using the saved context.

longjmp() and siglongjmp() never return.

NOTES

POSIX does not specify whether setjmp()/longjmp() will save/restore the signal context. If you want to save and restore signal masks, use sigsetjmp()/siglongjmp(). setjmp() and sigsetjmp() / longjmp() and siglongjmp() make programs hard to understand and maintain. If possible an alternative should be used.

--I DO agree with that!!

setcontext / getcontext, makecontext / swapcontext [Linux man page]

--They are much safer and easier to use than setjmp/longjmp do.

NAME

getcontext, setcontext -- get and set current user context
makecontext, swapcontext -- manipulate user context

SYNOPSIS

#include <ucontext.h>

DESCRIPTION

In a System V-like environment, one has the type ucontext_t defined in <ucontext.h> and the four functions getcontext(), setcontext(), makecontext() and swapcontext() that allow user-level context switching between multiple threads of control within a process.

getcontext() gets the current context of the calling process, storing it in the ucontext struct pointed to by ucp. The ucontext_t type that ucp points to defines the user context and includes the contents of the calling thread's machine registers, the signal mask, and the current execution stack.

setcontext() sets the context of the calling process to the state stored in the ucontext struct pointed to by ucp. A successful call to setcontext() shall not return; program execution resumes at the point specified by the ucp argument passed to setcontext(). The ucp argument should be created either by a prior call to getcontext() or makecontext(), or by being passed as an argument to a signal handler. If the ucp argument was created with getcontext(), program execution continues as if the corresponding call of getcontext() had just returned. If the ucp argument was created with makecontext(), program execution continues with the function passed to makecontext().

The makecontext() function modifies the context pointed to by ucp (which was obtained from a call to getcontext()). Before invoking makecontext(), the caller must allocate a new stack for this context and assign its address to ucp->uc_stack, and define a successor context and assign its address to ucp->uc_link. When this context is later activated (using setcontext() or swapcontext()) the function func is called, and passed the series of integer (int) arguments that follow argc; the caller must specify the number of these arguments in argc. When this function returns, the successor context is activated. If the successor context pointer is NULL, the thread exits.

The swapcontext() function saves the current context in the structure pointed to by oucp, and then activates the context pointed to by ucp.

RETURN VALUE

Upon successful completion, setcontext() shall not return and getcontext() shall return 0; otherwise, a value of -1 shall be returned.

When successful, swapcontext() does not return. (But we may return later, in case oucp is activated, in which case it looks like swapcontext() returns 0.) On error, swapcontext() returns -1 and sets errno appropriately.

APPLICATION USAGE
When a signal handler is executed, the current user context is saved and a new context is created. If the thread leaves the signal handler via longjmp(), then it is unspecified whether the context at the time of the corresponding setjmp() call is restored and thus whether future calls to getcontext() provide an accurate representation of the current context, since the context restored by longjmp() does not necessarily contain all the information that setcontext() requires. Signal handlers should use siglongjmp() or setcontext() instead.

Static variables & Static functions

2007-03-07T20:46:00.000-05:00

Static variables in C

Here, we need give a brief introduction of "C storage classes" first.

"storage classes" is a concept of C which are used to define the scope (visibility) and life time of variables and/or functions.
There are several storage classes available.

AUTO
auto is the default storage class for local varialbes. auto can only be used within functions, i.e. local variables which can only be visible in the function.
REGISTER
register is used to define local variables that should be stored in a register instead of RAM. This means that the variable has a maximum size equal to the register size (usually one word) and can't have the unary '&' operator applied to it (as it does not have a memory location).
Register should only be used for variables that require quick access - such as counters. Note that defining 'register' goes not mean that the variable will be stored in a register. It means that it MIGHT be stored in a register - depending on hardware and implimentation restrictions.
STATIC
We will discuss it later. :)
EXTERN
extern defines a global variable that is visable to ALL object modules.
For instance, when you define a variable in file 1 and 'extern' it, you can read and change its value. Note that if file 1 changes the value of the variable, file 2 will see the new value.

Well, go back to our topic.

static is the default storage class for global variables. That is to say, the two variables defined as below both have a static storage class.

static int count;
int road;
main()

static variable can also be defined within a function.
In this case, the variable is permanent. It can only be initalised once and only one copy of the variable exists. Recursive calls use the same variable. It is initialized at the compilation time and retains its value between calls to the function. Since it is initialized at compilation time, the initial value must be a constant.

Static variables in C++

It is same as in C when defined a static variable as a global variable or inside a function.

When defined a class member variable as static, only one copy of it exists. It can be accessed without instantiation of the class. All instances of the object use the same variable (memory location).

Static Functions in C

static functions can only visible to other functions in the same file, so providing function hiding.

It is a good trick which could improve the program performance. Declaring local functions as static tells the compiler that the function need not service any calls from unrelated modules. If the function is small enough, it may be inlined without having to maintain an external copy. If the function's address is never taken, the compiler can try to simplify and rearrange usage of it within other function.

Static Functions in C++

The differences between a static member function and non-static member functions are as follows.

A static member function can access only static member data, static member functions and data and functions outside the class. A non-static member function can access all of the above including the static data member.
A static member function can be called, even when a class is not instantiated, a non-static member function can be called only after instantiating the class as an object.
A static member function cannot be declared virtual, whereas a non-static member functions can be declared as virtual
A static member function cannot have access to the 'this' pointer of the class.

The static member functions are not used very frequently in programs. But nevertheless, they become useful whenever we need to have functions which are accessible even when the class is not instantiated.?

Concurrency VS Parallelism

2007-03-02T12:02:00.000-05:00

Parallelism is a subset of Concurrency.
Parallelism implies simultaneous running of code (which is impossible on uniprecessor machines);
Concurrency implies that many tasks can run in any order and POSSIBLY in parallel.

Camera

2007-02-19T11:50:00.000-05:00

Basically, we define the lens of camera as follow:

Lens Focal Length	Terminology	Typical Photography
Less than 21 mm	Extreme Wide Angle	Architecture
21-35 mm	Wide Angle	Landscape
35-70?mm	Normal	Street & Documentary
70-135 mm	Medium Telephoto	Portraiture
135-300+ mm	Telephoto	Sports, Bird & Wildlife

Understanding Camera Lenses

"... This tutorial aims to improve understanding by providing an introductory overview of concepts relating to image quality, focal length, perspective, prime vs. zoom lenses and aperture or f-number..."

C VS C++

2007-02-09T12:31:00.001-05:00

Sorting in C++ VS C
By Amit Patel, Jan. 4th, 2000 (a long time ago)

"... When I programmed in C, I always had to choose between library routines and hand-written code..."
"... In C++, I choose (STL) library routines whenever possible. It's refreshing to finally be able to use library routines without expecting any performance penalties..."

Another C VS C++ page
By Jakob Ostergaard, Feb. 24th, 2004

"... I firmly believe that C++ is a superior general purpose programming language..."

Process VS Thread

2007-01-19T12:01:00.000-05:00

Process VS Thread: An Introduction (CHN)

--Cited by Sophie Che, Jan. 2007

An introduction of some basic conception about Multi-Process & Multi-Thread (in Chinese).

Programming Optimization

2007-01-03T12:30:00.001-05:00

--Cited by Sophie Che, Jan. 2007

"... This is a page about the elusive subject of program performance optimization. ... Optimization is but one of many desirable goals in software engineering, and is often antagonistic to other important goals such as stability, maintainability, and portability. ... Be cautious and wary of the cost of optimizing your code."

Paper Writing

2006-12-16T11:54:00.001-05:00

How to Write an A+ Research Paper

Outlines the logical steps to writing a good research paper. Like the Olympic athlete aiming for the gold medal, you must have a positive attitude and the belief that you have the ability to achieve it. This is just the start to writing an research paper. More...

How to do Research At the MIT AI Lab
By a whole bunch of current, former, and honorary MIT AI Lab graduate students
Editor: David Chapman. Sep. 1988.
Copyright 1987~1988 by the authors

Explain how to do research