just do IT

adepends.py, utility for analysing android module dependency

2012-01-07T23:24:00.000+08:00

There are thousands of modules within android system. They form a very complicated dependency graph. When we want to learn about a particular module in android system, it's not easy to find out where modules that are dependent on by the module we mainly focus on are located. To make this task easier, I wrote adepends.py, which can be used to analysis dependency relationship between modules. It's capable of:

List modules defined within a directory
Generate a graphviz dot based diagram file to show dependency relationship

To show which modules are defined in a directory, we can use this command: "adepends.py -l DIRECTORY_NAME". For example, if we run "adepends.py -l external/protobuf/" command, we get below output:

libprotobuf-java-2.3.0-micro
libprotobuf-cpp-2.3.0-lite
host-libprotobuf-java-2.3.0-micro
libprotobuf-cpp-2.3.0-full
host-libprotobuf-java-2.3.0-lite
aprotoc
libprotobuf-java-2.3.0-lite

To generate a dependency diagram for a particular module, we can use this command: "adepends.py -o output.dot -m module_name". For example, if we're interested in the dependency diagram for charger module, we can use this command: "adepends.py -o output.dot -m charger". After the command finished, we have output.dot in current directory. Then we run "dot -Tpng -ooutput.png output.dot" to generate a png file for the diagram. And the diagram is shown below:

Each ellipse represents a module, the top line shows the module name, and the bottom line shows the directory that the module is defined. The arrowed edge represents the dependency relationship between two modules.

conditional compilation on wince

2011-12-05T20:23:00.001+08:00

While designing BSP, it's very common to enable or disable some features based on our requirements. Subsequently, we may need to change our code according to the feature's availability.
On a wince system, the status of a feature's availability is controlled via batch files, either cesysgen.bat (controls standard ce modules and functions) or {platform_name}.bat (controls platform specific settings). The status of a feature is set through environment variable in the batch file. The build system will build the image according to environment variables. For instance, the following line in a batch file instruct not to support SDMMC boot.

set BSP_NOSDMMC_BOOT=1

It may be desired to change our code based on the aforementioned setting. But the problem is the compiler (to be specific, preprocessor) can't see the value of BSP_NOSDMMC_BOOT environment variable. So, in order to pass the value to compiler, we need the help of build system. Just like gnu make, the wince build system can see the environment variable and define a macro for the compiler.
The code snippet below is extracted from a sources file, and shows how to define macro according to the BSP_NOSDMMC_BOOT's value.

!IF "$(BSP_NOSDMMC_BOOT)"=="0"
CDEFINES = $(CDEFINES) -DBSP_NOSDMMC_BOOT
!ENDIF

Then, in our code, we can use the BSP_NOSDMMC_BOOT macro to do conditional compilation.
And if we want to disable the whole module based on the environment variable's value, we can define SKIPBUILD in sources file, like this:

!if "$(BSP_NOSDMMC_BOOT)"=="1"
SKIPBUILD = 1
!endif

use protobuf on iphone app

2011-11-29T22:19:00.000+08:00

This post is a step by step tutorial showing how to use protobuf in iphone application. It shows how to:

Create a reusable static library
Create a executable project
Mix C++ code with object C code

1. Start terminal, cd to root folder of protobuf and run ./configure here to generate config.h header file and makefile.

2. Start XCode and create a new project. Select iOS - Library - Cocoa Touch Static Library project template.

3. Right click Other Sources and select add Existing Files.

4. Select the src/google directory, and add the directory recursively.

5. In the previous step, we add too much source files than actually needed. The sources files for the protoc compiler and unittest are included too. They're not needed to run ios application. To filter out unnecessary files, we can refer to the libprotobuf_lite_la_SOURCES and libprotobuf_la_SOURCES variables in src/Makefile, which list source files needed for protobuf library.

6. Now we need to add header file search path. Click Edit Project Settings under Project menu item.

7. Double click Header Search Paths.

8. Add protobuf and protobuf/src directory.

9. Now build the project.

10. In the terminal, run "make install" command to build protoc compiler and install it to default location(/usr/local/bin/protoc).

11. Go to examples directory and run "protoc addressbook.proto --cpp_out=./" to generate addressbook.pb.cc and addressbook.pb.h files.

12. Create a Window-Based Application.

13. Add reference to the static library we built. Right click Frameworks and select Add Existing Frameworks.

14. Click Add Other button.

15. Select the libprotobuf_ios.a file and click add button. Also, we need to add protobuf/src and protobuf/examples directory to Header Search Paths for this project.

16. Rename add_personAppDelegate.m to add_personAppDelegate.mm so that it'll be compiled as object C++.

17. The basic logic of add_personAppDelegate.mm is first create the addressbook.dat file in iphone's document directory. Then create a new AddressBook instance and add a person to it. Finally serialize the addressbook to the file we created. The full source is :

#import "add_personAppDelegate.h"

#include "addressbook.pb.h"
#include <fstream>

using namespace std;

@implementation add_personAppDelegate

@synthesize window;

#pragma mark -
#pragma mark Application lifecycle

- (BOOL)application:(UIApplication *)application didFinishLaunchingWithOptions:(NSDictionary *)launchOptions {
    GOOGLE_PROTOBUF_VERIFY_VERSION;

    NSArray *paths = NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES);
    NSString *documentDirectory = [paths objectAtIndex:0];
    NSString *filename = [NSString stringWithFormat:@"%@/addressbook.dat", documentDirectory];

    ifstream input([filename UTF8String], ios::in | ios::binary);

    tutorial::AddressBook address_book;
    address_book.ParseFromIstream(&input);
    int count = address_book.person_size();
    tutorial::Person *person = address_book.add_person();
    person->set_id(42);
    person->set_name("raymond");
    person->set_email("raymond@gmail.com");

    tutorial::Person_PhoneNumber *pn = person->add_phone();

    pn->set_type(tutorial::Person_PhoneType_WORK);
    pn->set_number("12345678");

    fstream output([filename UTF8String], ios::out | ios::trunc | ios::binary);
    person->SerializeToOstream(&output);

    NSHomeDirectory();
    // Override point for customization after application launch.

    [self.window makeKeyAndVisible];

    return YES;
}

- (void)applicationWillResignActive:(UIApplication *)application {
    /*
     Sent when the application is about to move from active to inactive state. This can occur for certain types of temporary interruptions (such as an incoming phone call or SMS message) or when the user quits the application and it begins the transition to the background state.
     Use this method to pause ongoing tasks, disable timers, and throttle down OpenGL ES frame rates. Games should use this method to pause the game.
     */
}

- (void)applicationDidEnterBackground:(UIApplication *)application {
    /*
     Use this method to release shared resources, save user data, invalidate timers, and store enough application state information to restore your application to its current state in case it is terminated later.
     If your application supports background execution, called instead of applicationWillTerminate: when the user quits.
     */
}

- (void)applicationWillEnterForeground:(UIApplication *)application {
    /*
     Called as part of  transition from the background to the inactive state: here you can undo many of the changes made on entering the background.
     */
}

- (void)applicationDidBecomeActive:(UIApplication *)application {
    /*
     Restart any tasks that were paused (or not yet started) while the application was inactive. If the application was previously in the background, optionally refresh the user interface.
     */
}

- (void)applicationWillTerminate:(UIApplication *)application {
    /*
     Called when the application is about to terminate.
     See also applicationDidEnterBackground:.
     */
}

#pragma mark -
#pragma mark Memory management

- (void)applicationDidReceiveMemoryWarning:(UIApplication *)application {
    /*
     Free up as much memory as possible by purging cached data objects that can be recreated (or reloaded from disk) later.
     */
}

- (void)dealloc {
    [window release];
    [super dealloc];
}

@end

18. After build and run the application in iphone emulator, we get generated addressbook.dat file in /Users/user_name/Library/

Application Support/iPhone Simulator/4.3/Applications/9AF109CF-1B33-49DA-BE73-603CC798408F/Documents/addressbook.dat

port protobuf-lite to wince

2011-11-24T22:24:00.003+08:00

protobuf is a wonderful project that helps us implement communication protocol. There are a lot of benefits to use it in practical project, including:

It has an efficient binary serialization algorithm
It runs cross platforms
It support mainstream programming languages, c++, python and java. there are also lots of porting out there for other popular languages.
It's designed to make protocols both backward and forward compatible.
It enables developers to focus on protocol design.

Currently, there is no official windows CE version for protobuf. It's not an easy task to port protobuf full version to windows CE. But the lite version, which supports less feature than full version (check the explanation for optimize_for option in this page for what's the difference), is easier to port. Here is how I port it:

Create a Win32 Smart Device Project library project, name it protobuf-lite-ce
Copy all source files from protobuf-lite project to protobuf-lite-ce project in Solution Explorer
Create a ce_port folder in the project's directory, and copy the errno.h header file from (Visual_Studio_Root)/VC/include into the folder. This is because Windows CE doesn't have this file, so we need to provide one. Actually, this errno.h can be a pure empty file.
Add "../src;.;./ce_port" to the project's Additional Include Directories.
The windef.h header file already defines OPTIONAL macro, it conflicts with Cardinality::OPTIONAL enum. So the extension_set.cc fails to compile, to solve this, add following code before enum Cardinality definition to undefine OPTIONAL:

#if defined(OPTIONAL)
#if defined(_MSC_VER)
#pragma message ("Unexpected OPTIONAL macro definition, #undefine OPTIONAL")
#else
#warning  "Unexpected OPTIONAL macro definition, #undefine OPTIONAL"
#endif
#undef OPTIONAL
#endif
namespace {

enum Cardinality {
  REPEATED,
  OPTIONAL
};

}  // namespace

Now the protobuf-lite-ce project should compiles fine.
Here is the project file for downloading. Just get everything there and place them in protobuf/vsprojects/ directory.

why can we use printf without including stdio.h

2011-10-30T21:12:00.001+08:00

I read the c programming language again to mourn Dennis Ritchie who passed away recently.

I noticed below statements in section "4.2 Functions Returning Non-integers", which explains the question, why can we use printf without including stdio.h.

The function atof must be declared and defined consistently. If atof itself and the call to it in main have inconsistent types in the same source file, the error will be detected by the compiler. But if (as is more likely) atof were compiled separately, the mismatch would not be detected, atof would return a double that main would treat as an int, and meaningless answers would result.
In the light of what we have said about how declarations must match definitions, this might seem surprising. The reason a mismatch can happen is that if there is no function prototype, a function is implicitly declared by its first appearance in an expression, such as
sum += atof(line)
If a name that has not been previously declared occurs in an expression and is followed by a left parentheses, it is declared by context to be a function name, the function is assumed to return an int, and nothing is assumed about its arguments. Furthermore, if a function declaration does not include arguments, as in
double atof();
that too is taken to mean that nothing is to be assumed about the arguments of atof; all parameter checking is turned off. This special meaning of the empty argument list is intended to permit older C programs to compile with new compilers. But it's a bad idea to use it with new C programs. If the function takes arguments, declare them; if it takes no arguments, use
void.

So, let's take a look at the hello world sample below:

1 //#include  <stdio.h>
2
3 int main(int argc, char *argv[])
4 {
5     printf("hello world!\n");
6     return 0;
7 }

When the code is compiled, the statement on line 5 implicitly declares the printf function because it's not declared explicitly. It's the same as if we declared printf as:
int printf();
And there is no assumption about its argument, so the code can pass the compile phase.

In link phase, unlike c++, only the function name (function signature doesn't matter) affects the symbol name. So the printf symbol name can be found from the standard c library which is linked automatically. As a result, the code above can compile and run successfully.

stream audio via udp on android

2011-10-23T11:30:00.001+08:00

In this post, I tried to play small audio data chunks with AudioTrack to show the feasibility of streaming audio. It's not straightforward enough. So I updated the sample code to actually transfer audio data with udp.
As the image below shows, the application is not too complicated.

The two buttons will each create a new thread to send and recv audio data respectively. And the sender will read audio data from the file /data/1.wav. Then, it sends the data to udp port 2048 on localhost. The receiver reads on 2048 port and feed data received to AudioTrack object.
Full code is available at:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/android/streaming_audio/src/rmd/media/StreamingAudio/UdpStream.java

microsoft's ifstream automatically removes carriage return

2011-10-12T21:49:00.001+08:00

By default, the ifstream class in miscrosoft's STL converts a carriage return and new line (0x0d0a or crlf) pair to a single new line (0x0a) automatically while reading a text file.

Take the following code for example:

1 #include    <cstdlib>
2 #include    <fstream>
3 #include    <iostream>
4
5 using namespace std;
6
7 int main ( int argc, char *argv[] )
8 {
9     ifstream fs("crlf.txt");
10     fs.seekg(0, ios::end);
11     int len = fs.tellg();
12     fs.seekg(0, ios::beg);
13
14     char* buf = new char[len];
15     fs.read(buf, len);
16     cout << hex;
17     // dump buf in hex format
18     for(int i = 0; i < len; ++i)
19         cout << static_cast<int>(buf[i]) << " ";
20     cout << endl << dec << buf << endl;
21     cout << "file size: " << len
22         << " actual read len: " << fs.gcount() << endl;
23     return EXIT_SUCCESS;
24 }               // ----------  end of function main  ----------

And let's suppose the content of crlf.txt is:

hello\r\n
world\r\n

If we compile the code with microsoft's vc++ compiler, and run the executable against the preceeding text file, we get below output:

68 65 6c 6c 6f a 77 6f 72 6c 64 a 0 0
hello
world

file size: 14 actual read len: 12

As we can see, the 0x0d0a has been changed to 0x0a, and the number of bytes actually read is 12, other than 14. But if we compile the code with g++ and run the test, we get different output:

68 65 6c 6c 6f d a 77 6f 72 6c 64 d a
hello
world

file size: 14 actual read len: 14

The number of bytes actually read is now the same as the text file's size. And the bytes read into memory is the same as the original file's on disk.

In very rare cases, we may appreciate the microsoft ifstream's behavior, which saves our time from making such conversion our-self. But in most cases, it has negative consequence and incurs subtle bugs that are hard to debug.
Not sure why is it, just to be alerted by this specific behavior exhibited by microsoft's STL.

ease android stacktrace examination in vim with agdb

2011-08-30T11:04:00.002+08:00

Continue the post view call stack of crashed application on android.
The agdb tool is able to convert PC register to source file information, but not convenient enough. After agdb outputs source file information, we still need to open the source file in vim and jump to the corresponding line manually.
Now agdb tool can generate a vim specific error file for the stacktrace to help us jump to source code directly.
Still consider the stacktrace below:

22 F/ASessionDescription(   33): frameworks/base/media/libstagefright/rtsp/ASessionDescription.cpp:264 CHECK_GT( end,s) failed:  vs.
23 I/DEBUG   (   30): *** *** *** *** *** *** *** *** *** *** *** *** *** *** *** ***
24 I/DEBUG   (   30): Build fingerprint: 'generic/generic/generic:2.3.1/GINGERBREAD/eng.raymond.20101222.130550:eng/test-keys'
25 I/DEBUG   (   30): pid: 33, tid: 450  >>> /system/bin/mediaserver <<<
26 I/DEBUG   (   30): signal 11 (SIGSEGV), code 1 (SEGV_MAPERR), fault addr deadbaad
27 I/DEBUG   (   30):  r0 deadbaad  r1 0000000c  r2 00000027  r3 00000000
28 I/DEBUG   (   30):  r4 00000080  r5 afd46668  r6 40806c10  r7 00000000
29 I/DEBUG   (   30):  r8 8031db1d  r9 0000fae0  10 00100000  fp 00000001
30 I/DEBUG   (   30):  ip ffffffff  sp 40806778  lr afd19375  pc afd15ef0  cpsr 00000030
31 I/DEBUG   (   30):          #00  pc 00015ef0  /system/lib/libc.so
32 I/DEBUG   (   30):          #01  pc 00001440  /system/lib/liblog.so
33 I/DEBUG   (   30):
34 I/DEBUG   (   30): code around pc:
35 I/DEBUG   (   30): afd15ed0 68241c23 d1fb2c00 68dae027 d0042a00
36 I/DEBUG   (   30): afd15ee0 20014d18 6028447d 48174790 24802227
37 I/DEBUG   (   30): afd15ef0 f7f57002 2106eb56 ec92f7f6 0563aa01
38 I/DEBUG   (   30): afd15f00 60932100 91016051 1c112006 e818f7f6
39 I/DEBUG   (   30): afd15f10 2200a905 f7f62002 f7f5e824 2106eb42
40 I/DEBUG   (   30):
41 I/DEBUG   (   30): code around lr:
42 I/DEBUG   (   30): afd19354 b0834a0d 589c447b 26009001 686768a5
43 I/DEBUG   (   30): afd19364 220ce008 2b005eab 1c28d003 47889901
44 I/DEBUG   (   30): afd19374 35544306 d5f43f01 2c006824 b003d1ee
45 I/DEBUG   (   30): afd19384 bdf01c30 000281a8 ffffff88 1c0fb5f0
46 I/DEBUG   (   30): afd19394 43551c3d a904b087 1c16ac01 604d9004
47 I/DEBUG   (   30):
48 I/DEBUG   (   30): stack:
49 ........................
92 I/DEBUG   (   30):     408067e4  6f697470
93 I/BootReceiver(   75): Copying /data/tombstones/tombstone_09 to DropBox (SYSTEM_TOMBSTONE)

We run this command to convert it to vim error file:
agdb.py -v < tombstone_01.txt > vim_error_file
# the -v argument tells agdb to generate a vim error file

Then in vim, we run :cg vim_error_file to load the error file to vim's quickfix buffer.
After the error file is loaded, we run :cw command in vim to examine the call stack. It's shown below:

1 pid: 33, tid: 450 >>> /system/bin/mediaserver <<<
2 /path_to_android_src_root/bionic/libc/unistd/abort.c:82: #00 __libc_android_abort
3 /path_to_android_src_root/system/core/liblog/logd_write.c:235: #01 __android_log_assert

Now we can focus on the line that we'd like to further investigate, and press enter. Vim will bring us the the exact line that the error corresponds to.

The idea of the feature is very simple. As we vim users know, vim is able to recognize lots of compilers' error message. The agdb tool converts the format of stacktrace to gcc compiler's error format, then vim can load the output to quickfix and associate lines with corresponding source code.

fix "bad class file error" android build error

2011-08-27T11:23:00.000+08:00

I got the error below while building android source code:

packages/apps/Calculator/src/com/android/calculator2/CalculatorDisplay.java:19: cannot access android.content.Context
bad class file: android/content/Context.class(android/content:Context.class)

The error is caused by using an incorrect version of jdk. Google recommend using sun-java6-jdkto build android source code. On my pc, besides sun jdk that installed, openjdk and fastjar are installed by default. And they're used to build android, rather than sun-jdk. To make sure that sun jdk is used, I used commands below to select sun jdk.

sudo update-alternatives --config java
sudo update-alternatives --config jar

Typical output is shown below, and android build successfully after I select sun jdk.

There are 2 choices for the alternative jar (providing /usr/bin/jar).

Selection    Path                             Priority   Status
------------------------------------------------------------
0            /usr/bin/fastjar                  100       auto mode
1            /usr/bin/fastjar                  100       manual mode
* 2            /usr/lib/jvm/java-6-sun/bin/jar   63        manual mode

access android source via https protocol

2011-08-22T20:21:00.002+08:00

Update: no need to use this trick anymore, since google has changed the default protocol to https.

repo is a good tool for android source tree management. It manages all git repositories for all android subprojects. By default, it clones these project via git: protocol, which is more efficient to work with than http. But the git: protocol accesses 9418 port, which may be blocked by firewalls, especially when we're using it within a restricted network environment. In this case, it's desired to be able to access android source tree with http: protocol.
The site kernel.org that hosts android source code supports https: protocol, so we can change the config file in .git folder for each android subproject to force using https: protocol. The bash command below does the job:
find -regex ".*.git/config" -exec sed -i s/git:/https:/ {} \;
To change it back to git protocol, exchange git: and https: in the command.

modify CE code for our platform

2011-07-31T19:57:00.001+08:00

A majority of windows CE core and drivers code is available to us, they reside in public directory of CE installation folder. Occasionally, we may want to modify that part of code, either to change some system behaviors, or add some log messages for debugging our platform's code.
It's strongly recommended not to change the original code in place. Because this part of code is shared by all platforms. All platforms will be affected by the modification. The right way is before making any change, copy the module into our own platform directory, and modify the copy there.
Let's say we want to modify public/common/oak/bootpart module's code.
1. We first copy it into platform/platform_name/src/common/bootpart
2. Exclude public/common/oak/bootpart from our build

3. Include platform/platform_name/src/common/bootpart into our build

4. The last step is to update other modules' sources file. For any module that depends our modified bootpart module, we should change its sources file so that it can find the new bootpart instead of the original bootpart shipped with CE. For instance, change $(_COMMONOAKROOT)\lib\$(_CPUINDPATH)\bootpart.lib to $(_TARGETPLATROOT)\lib\$(_CPUINDPATH)\bootpart.lib

addr2line for windows

2011-06-27T19:40:00.001+08:00

While debugging os or application crash bug on windows ce (the tool winaddr2line isn't particularly used for windows CE application, it can be used for normal windows application too.) platform, developers may not always have the luxury to debug step by step within a IDE. Most of time, the only information available to us is the output on serial port. (It's already very fortunate if we can see serial port output every time a crash happens.) What we get is something like:

Exception 'Data Abort' (4): Thread-Id=06890fba(pth=88eb8948), Proc-Id=06750f9e(pprc=88eb8828) 'test.exe', VM-active=06750f9e(pprc=88eb8828) 'test.exe'
PC=00011048(test.exe+0x00001048) RA=00011018(test.exe+0x00001018) SP=0002fb98, BVA=00000000

Unhandled exception c0000005:
Terminating thread 88eb8948

Given the PC register value, we need to figure out on while line in our code did the application crash. winaddr2line makes it an easy task as long as we have the pdb symbol file for the application. It's a attempt to port addr2line to windows world.
Let's take the preceding log for example. In order to find out the line number of the code that incurs the crash, we need following information.

In which module did the crash happen
What's the address can we use to query

For question 1, the module name is already available in the log. In our example, it's test.exe. For question 2, we can see the PC register's value is 0x00011048. So, we run "winaddr2line.exe -e test.exe 11048 -a -p -s -f" command, and get this: "0x00011048: foo::crash at test.cpp:8". Now we open test.cpp and check what's around line 8, the root cause is very obvious.

1
2 class foo
3 {
4     public:
5         void crash()
6         {
7             int *a = NULL;
8             int b = *a;
9         }
10 };
11
12 int main ( int argc, char *argv[] )
13 {
14     foo f;
15     f.crash();
16     return 0;
17 }

In order for the preceding command to work correctly, we must make sure the test.exe and its symbol file test.pdb is available in current directory of the shell that we run winaddr2line. If it's not the case, we should pass correct path to test.exe for -e argument and path to directory containing test.pdb for -y argument respectively.

In the example, we use PC register's value directly to query line number. But it's not always the case. Consider the crash log below:

Exception 'Raised Exception' (-1): Thread-Id=06891422(pth=88eb8948), Proc-Id=0675143e(pprc=88eb8828) 'test.exe', VM-active=0675143e(pprc=88eb8828) 'test.exe'
PC=4006d270(coredll.dll+0x0005d270) RA=80118a60(kernel.dll+0x00007a60) SP=0002fb8c, BVA=00000000

Unhandled exception c0000094:
Terminating thread 88eb8948

The crash occurred in coredll.dll module. We run command "winaddr2line.exe -e coredll.dll 4006d270 -a -p -s -f", but we can see it fails to find the line number. This is because we can't use the PC register's value directly here. The coredll.dll is loaded at 0x40010000 (0x4006d270-0x0005d270), which is different from its preferred ImageBase address (0x10000000, which can be examined with "dumpbin /headers coredll.dll" command). And winaddr2line can only make use of the ImageBase address contained statically in PE header of the binary. So, we must change the address to 0x1005d270 (0x10000000+0x0005d270). By using this address, we can see the crash occured at: d:\dublin2-1\private\winceos\coreos\core\dll\crtsupp.cpp:240

Source code for winaddr2line:
http://code.google.com/p/winaddr2line/

quickswitch

2011-05-31T18:58:00.001+08:00

One of the most used function on a pc is switching between tasks. We may write some code in vim, switch to firefox to search for the usage of an api. And then switch back to vim continue writing code. Most of time, we do this by using Alt+Tab key combination. But it's not an efficient way if there are many tasks running. It's not quick enough to find the target task.

The main drawback with Alt+Tab is it forces us to deal with more problems. For example, we want to switch to firefox task, the essential problem we're dealing with is finding the task using the clue "FIREFOX". After we press Alt+Tab, we get a window list in which all tasks are identified by icons. Now, we have to deal with another problem, finding out the icon that represents firefox. That's to say, our brain has to do a "context switch" from the "word processing" problem to an "image recognition" problem.

It's not intuitive at all. The idea of QuickSwitch is very similar to Spotlight on mac and FuzzyFinder on vim. We can keep concentrating on the "word processing" problem, no context switch.

QuickSwitch runs as a daemon. By using it, at any time we want to switch ao another task, press Ctrl+Alt+S key combination to bring up the QuickSwith main window, in which all tasks are listed. Then, type any part of the window title of the desired task and press enter to switch to it.

For instance, if we want to switch to firefox task. Type "firefox" in the input box. As we type, the window list is filtered. Those windows don't contain the word we typed in title are filtered out. When there is only one result left in the list, we can press enter key once to switch to it. If there are more than one one result left, we can continuing typing more characters to filter out more un-desired tasks. Or we can press enter to bring focus to the result list and use up, down keys (or Ctrl+P, Ctrl+N) to select desired task and press enter again to switch to it.

Source code:
http://code.google.com/p/quickswitch/

extend windows ce platform with oalioctl

2011-04-14T20:09:00.002+08:00

Though not being a open source platform, windows ce is designed to be flexible so that device venders can extend it easily. oalioctl is a feature that makes it possible to do things in kernel space on behalf of application.

Features
1. Extensibility
The essential feature of oalioctl is it enables us to extend windows ce kernel's functions, and new functions are directly accessible to application layer developers.
2. Separation
oalioctl is completely separated from kernel source code. From the sense of code organization, it doesn't differ from a normal device driver. The separation makes it easy to maintain and port oalioctl module.
3. Easy to use

Compared to a normal ce driver, the usage of oalioctl is easier from an application developer's perspective. In order to make use of a normal driver, application usually follows below sequence:
CreateFile -> DeviceIoControl -> CloseHandle
But the application can simply call KernelIoControl to make use of oalioctl library, which is a far more easy way.

Implementation
oalioctl is implemented as a standalone dynamic library. And it will be loaded automatically during kernel initialization (relevant code is in LoaderInit() function in X:\WINCE600\PRIVATE\WINCEOS\COREOS\NK\KERNEL\loader.c). So it's not necessary to register this module in platform.reg as other stream drivers do.
When an application calls KernelIoControl, the call stack goes like this:

IOControl //our own oalioctl.cpp
OEMIOControl // platform/common/src/common/ioctl/ioctl.c
IOControl // public/common/oak/oalioctl/oalioctl.cpp
EXTKernelIoCtl // private/winceos/coreos/nk/kernel/kwin32.c

How to implement our own oalioctl
It's a fair simple task to implement oalioctl layer for our own platform with following steps:

copy public/common/oak/oalioctl directory to platform/platform_name/src/drivers
change TARGETTYPE to DYNLINK in sources file
define our own iocontrol code with CTL_CODE macro
add a case branch for the new iocontrol code

resolve windows ce remote tool connection issue

2011-03-08T19:50:00.000+08:00

remote tools for windows ce is a set of powerful tools for debugging. I have Visual Studio 2005, Windows Embedded CE 6.0 R3 installed, but the remote tools don't work. They fail to connect to device with following error message:
The Microsoft ActiveSync reported the following error: Unable to load device side components. Please check server configuration settings.

There are two ways to resolve the connection issue.

1. Run remote tools from windows start menu (e.g., Microsoft Visual Studio 2005\Visual Studio Remote Tools\Remote Process Viewer, which is a shortcut to C:\Program Files\CE Remote Tools\5.01\bin\ccpview.exe), instead of starting from visual studio menu (e.g., Target/Remote Tools/Process Viewer, which is a shortcut to C:\Program Files\Common Files\Microsoft Shared\Windows CE Tools\Platman\bin\wce600\cepview.exe). remote tools version 5.01 work fine.

2. Copy
c:\Program Files\Common Files\Microsoft Shared\Windows CE Tools\Platman\target\wce600\armV4i\
to
c:\Program Files\Common Files\Microsoft Shared\Windows CE Tools\Platman\target\wce600\armV4\
. The lack of the second directory is a bug in remote tools version 6 that causes the connection issue.

view call stack of crashed application on android

2011-01-25T09:10:00.005+08:00

On android, when a process crashes in native code, the call stack of the process will be saved to a log file in /data/tombstomes/, and written to logcat as well. The information is helpful for debugging.
Unfortunately, the call stack doesn't show in human readable format, file name, function name. Instead, it's shown as module name (e.g., libc.so) and memory address of the instruction. We can use addr2line to translate the address to corresponding file name and function name if we have the binary of the module that contains symbol information.
To make it easier to use, this function is included in agdb tool (see here for more). We can use "agdb.py -r -e module_name address" to find out the function name of specified address within the module.

When we have a long call stack, instead of running the command above for each line in the call stack manually, we can feed the whole call stack to agdb through pipe and get the full resolved call stack. For example, use "adb logcat | agdb.py -r" command for adb logcat output with below contents:

we get:

Similarly, we copy a tombstone file to our development pc, and use "cat tombstone_01.txt | agdb.py -r" command to resolve call stack addresses in the tombstone log file.

install h.264 plugin for linphone on ubuntu

2011-01-19T16:48:00.003+08:00

h.264 plugin isn't a standard part of linphone installation on ubuntu. We must manually compile and install it.

1. Download msx264 plugin source code.
2. Run sudo apt-get install libmediastreamer-dev libx264-dev libavcodec-dev libswscale-dev libtheora-dev to meet msx264's dependency requirements.
3. Run ./configure --prefix=/usr/lib. It's mandatory to set prefix to /usr/lib, because linphone can't find the plugin if it's installed in default location, /usr/local/lib.
4. Run sudo make install.
5. Change the line 393 in src/msx264.c from

393 if (sws_scale(s->sws_ctx,(uint8_t * const*)orig->data,orig->linesize, 0,

393 if (sws_scale(s->sws_ctx,(uint8_t **)orig->data,orig->linesize, 0,

to get rid of compilation error, if you have.

6. Restart linphone, the h.264 plugin should be available now.

utility for debugging android native application

2011-01-13T10:05:00.001+08:00

agdb is a utility aims to ease the task of debugging android native application. Its working mechanism is similar to ndk-gdb. But it's intended to assist debugging native applications in android source tree, not for application created with ndk.

It does following things for us automatically:

find the binary that contains symbol data of target process
attach gdbserver to the target process on device, or start the target process under gdbserver if the process isn't already running
start gdb client and set correct symbol file search path

How to use it
prerequirements
agdb must know the root directory of android source code. We can tell it by passing --android-src-root argument or setting ANDROID_SRC_ROOT environment variable.
agdb interacts with target device through adb, so the device must be accessible through adb.
gdb client communicates gdbserver through tcp protocol (tcp port 7890 by default). If using emulator, we need to forward or redir tcp ports in advance.

usage
After all prequirements are met, we can run "agdb.py process_name" to debug desired application. For example, if we want to debug mediaserver application, simply run agdb.py mediaserver.
If we want to debug code in native part of a dalvik (java) application, we can use:
agdb.py --dalvik [package_name (for example, com.android.launcher)]

Limitation
It doesn't work on Windows.
It starts gdbserver in network communication mode, serial port isn't supported.
~~It doesn't support dalvik application.~~

Reference
http://source.android.com/porting/debugging_gdb.html

view raw yuv file with mplayer

2011-01-10T22:32:00.001+08:00

mplayer is a powerful utility that is helpful for examining the raw yuv file.
We decoded this h.264 media file (test_avc_amr.mp4) coming with android opencore to yuv format, saved as a.yuv. The command below can display the yuv file frame by frame:
mplayer -demuxer rawvideo -rawvideo w=176:h=144:format=i420 a.yuv -loop 0

The internal structure of a.yuv is a serial of yuv frames, without any header describing the size and format.

So, to make mplayer work, we should tell it the width and height of the yuv in pixel. Also, we need to specify the format of the raw video. The command below shows us all available formats:
mplayer -rawvideo format=help

References:
mplayer manual page
mplayer online documentation

another free uml tool, bouml

2010-12-24T11:01:00.000+08:00

Having tried metauml as my primary design utility recently, the experience isn't as good as I expected. At the beginning, I thought I would be more focused on the content/design while using a pure textual editing tool, but the result is very frustrating. Because I have to pay more attention on the organization and layout, rather than the design. metauml doesn't help me organizing elements at all, leave it all to me. I have to think in advance where should an element be placed, and instructed metauml to place the element explicitly, either in absolute coordinate or in relative coordinate. It seems ok for simple diagrams with very few elements. But as the number of elements increases, it's very hard to plan in advance. Once I made a mistake, the cost to change it is huge, I may have to re-organize everything, to keep the diagram clean.
I found an graphical tool, bouml, as an great replacement. It's efficient and powerful. bouml saves everything in text, so it's also possible to do version control. The best feature I noticed so far is its capability of reversing c++ code. By feeding it with source code directories, it will generate a full list of classes, methods exist in the code. It's very helpful for analyzing others' projects.

common programming and debugging tools

2010-12-21T19:22:00.000+08:00

To help me memorize commonly used programming and debugging tools on windows and linux, I created a wiki page here:
http://code.google.com/p/rxwen-blog-stuff/wiki/CommonProgrammingAndDebuggingToolsOnWinAndLinux

port exosip to android

2010-12-19T17:29:00.001+08:00

Port exosip to android platform isn't a difficult task because exosip doesn't rely on any special system calls that aren't available on android. It only requires osip to compile, which can also be easily ported.
As an example, I created two applications to run against exosip lib. One is a native application that can run in android shell, the other is an java application that interact with exosip through jni. The dependency relationship between modules is:

The diagram below depicts the organization of files. They're organized this way so that they can be compiled through android ndk build system.

exosip_root (NDK_MODULE_PATH environment variable points here)

libosip
- Android.mk
- source files
libexosip
- Android.mk
- source files
sip_exe
- jni
sip_jni
- jni
  - Android.mk
  - source files
- libs
  - armeabi
    - libosip.so
    - libexosip.so
- src
  - java source files
- AndroidManifest.xml

To comply with ndk build system's requirements, we create a directory named jni under sip_jni and sip_exe module, and place actual source file there. The Android.mk and Application.mk (optional) are placed in the jni directory as well. Keeping files this way, we can issue ndk-build command right in sip_jni or sip_exe directories to compile applications.
Note that we don't create jni directory for libosip and libexosip, their Android.mk is placed directly under libosip and libexosip directories. This is because they are dependent on by application modules. We don't need compile them directly, instead, the build system will build them automatically while building applications. In order to help build system find libosip and libexosip, we must set NDK_MODULE_PATH environment variable to the directory that directly containing libosip and libexosip. The build system will search for them based on directory name, so their names matter.

To port exosip to android, the essential task is to create the Android.mk file, which specifies source files, c flags, ld flags, dependent libraries. We define HAVE_TIME_H and HAVE_SYS_SELECT_H to compile exosip successfully. And we define ENABLE_TRACE and OSIP_MT to enable logging and multi-threading. In the last line, $(call import-module,libosip) tells the build system that exosip depends on osip, and all header files exported by osip (LOCAL_EXPORT_C_INCLUDES:=$(LOCAL_C_INCLUDES)) will be included by exosip automatically.
import-module is a feature that isn't available in the build system in android source tree. It enables us organizing our projects in arbitrary manner. For example, we can place libosip and libexosip directories in another directory. The build system can still find them as long as NDK_MODULE_PATH is set to the directory containing them. It's much more flexible than specifying dependency relationship with relative path.

Sample:
The sample for this post is available at:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/android/exosip_sample/
It shows how to:

use ndk build system
use stl in c++ code
create a very basic exosip application
call native code from java
call java code from native code

References:
ndk document
exosip user manual

tools for working with android jni

2010-12-14T23:07:00.000+08:00

When we make use of jni on android, it's a error-prone task to manually write the native function name for a given java native function. Though there are rules for us to follow, no one would like to memorize that. javah to the rescue.
For example, for the following java class with a native method.

1 package com.rmd.jni;

2

3 import android.app.Activity;

4 import android.os.Bundle;

5

6 public class Main extends Activity

7 {

8     /** Called when the activity is first created. */

9     @Override

10     public void onCreate(Bundle savedInstanceState)

11     {

12         super.onCreate(savedInstanceState);

13         setContentView(R.layout.main);

14     }

15

16     public native boolean JniMethod(int a);

17 }

We can follow steps below to generate a native header file:

cd to project root folder
Compile the project, e.g., using ant debug command
run javah -jni -classpath bin/classes -d jni com.rmd.jni.Main (this command generates a native header file in jni directory, for com.rmd.jni.Main class)

And we get a header file com_rmd_jni_Main.h with content below:

1 /* DO NOT EDIT THIS FILE - it is machine generated */

2 #include <jni.h>

3 /* Header for class com_rmd_jni_Main */

4

5 #ifndef _Included_com_rmd_jni_Main

6 #define _Included_com_rmd_jni_Main

7 #ifdef __cplusplus

8 extern "C" {

9 #endif

10 /*

11 * Class:     com_rmd_jni_Main

12 * Method:    JniMethod

13 * Signature: (I)Z

14 */

15 JNIEXPORT jboolean JNICALL Java_com_rmd_jni_Main_JniMethod

16   (JNIEnv *, jobject, jint);

17

18 #ifdef __cplusplus

19 }

20 #endif

21 #endif

There are cases that we need to provide a method signature of a java function to the GetMethodID function in native code. javap can help us.
Consider the java class below, within which exists a JniCallback method. And this method is meant to be called from native code.

After it's compiled, we can use javap -classpath bin/classes -s -p com.rmd.jni.Main command to find out the signature of JniCallback method. Shown below.

Compiled from "Main.java"
public class com.rmd.jni.Main extends android.app.Activity{
public com.rmd.jni.Main();
Signature: ()V
public void onCreate(android.os.Bundle);
Signature: (Landroid/os/Bundle;)V
public native boolean JniMethod(int);
Signature: (I)Z
}

Reference:
Java Native Interface Programming

learning opencore through unit testing

2010-12-08T22:00:00.002+08:00

Android 2.3 gingerbread was officially released. A big improvement is this version is in media framework, as stated in platform highlights:

Media Framework

New media framework fully replaces OpenCore, maintaining all previous codec/container support for encoding and decoding.
Integrated support for the VP8 open video compression format and the WebM open container format
Adds AAC encoding and AMR wideband encoding

I'm not able to find out what is the replacement for opencore yet. But before opencore is obsoleted, I still would like to share my way of learning opencore. This might be helpful for those who still have to work on legacy android platforms.

Opencore is a complicated multimedia framework. An effective way I thought a bit easier to learn it is looking at its unit testing code and debugging unit testing application. The advantages include:

The code can be compiled as x86 executable, so we can run it on our pc directly, rather than on a android device or emulator.
The application can be debugged with gdb
Unit tests demonstrate the simplest usage of opencore. It's particularly useful for a fresh learner to get started.
Test cases each have its own concentration, and is easier to follow.

So, if we use unit testing code as a means of learning opencore, instead of trying to understand the full-featured mediaserver, things will be much easier. We can find out the simplest way to initialize opencore and play a file. For any specific requirement we need to implement, we can always find a corresponding test case in the unit test guide and refer to its source code.

How to debug opencore with gdb
Before we use gdb to debug unit testing application, we need to be aware of a helpful gdb feature: show real type of a object though pointer.
In opencore framework, it always manipulate a concrete object through an interface or base pointer. So, during debugging, we often get lost about what the actual type of the object being pointed to by the pointer is. Gdb can print the real type of object if the pointer points to it has virtual table. This feature can be turned on with "set print object" command.
For example, if we break at the line returns a pointer in PVPlayerNodeRegistry::CreateNode function, we issue "p nodeInterface" command without print object turning on, we see:

$1 = (class PVMFNodeInterface *) 0x83c65c0

The type of the pinter is shown as PVMFNodeInterface, which isn't very informative because is the base type. If we trun print object on and run the command again, we see:

$2 = (PVMFMP4FFParserNode *) 0x83c65c0

The real type of the object is clearly printed. Very useful feature for debugging complex frameworks.
We can follow below steps to compile and debug unit testing application:

Compile the app by following instructions in quick_start.txt
cd to {open_core_root}/build_config/opencore_dynamic/build/pe_test. We need to start debugging here, otherwise the application may fail to find necessary libraries and media files.
export LD_LIBRARY_PATH=../installed_lib/linux
gdb ../bin/linux/pvplayer_engine_test
set desired breakpoints
run -source test.mp4 -test 1 1. The source and test case number argument can be changed accordingly.

python decorators

2010-12-05T21:10:00.002+08:00

Decorator is a very expressive language feature in python. It helps developers to write cleaner, modular code that is easier to extend and maintain. It also helps implement AOP and decorator pattern in python.

Decorator syntax
To declare a decorator function, we can define a function that takes a another function as argument and returns a function. The usage of decorator is very simple, just add a line begins with '@' symbol and the name of the decorator before the function to be decorated.

1 def decorator(func):
2     def new_func():
3         print "decorator message"
4         func()
5     return new_func
6
7 @decorator
8 def foo():
9     print "hello world"
10
11 foo()

The effect is when we call foo function, besides print "hello world" message, the message "decorator message" is also printed. That is, the decorator function extends foo function's behavior.
The code above is equivalent to:

1 def decorator(func):
2     def new_func():
3         print "decorator message"
4         func()
5     return new_func
6
7 def foo():
8     print "hello world"
9
10 foo = decorator(foo)
11 foo()

Decorators can also accept arguments, as long as it returns a decorator function that takes a function as argument.

1 def decorator_with_arg(arg):
2     def decorator(func):
3         def new_func():
4             print arg
5             func()
6         return new_func
7     return decorator
8
9 @decorator_with_arg("arg for decorator")
10 def foo():
11     print "hello world"
12
13 foo()

The example above is equivalent to :

1 def decorator_with_arg(arg):
2     def decorator(func):
3         def new_func():
4             print arg
5             func()
6         return new_func
7     return decorator
8
9 def foo():
10     print "hello world"
11
12 foo = decorator_with_arg("arg for decorator")(foo)
13 foo()

The decorator_with_arg function creates a closure, so that the arg argument can still be used after the decorator_with_arg returned. Since it's possible for a decorator to accept arguments, the decorator's behavior can changed based on the argument passed in. So it's possible to write more flexible code.

A more practical example
Here is a more practical example. We create a tracable decorator which is a debugging utility. It will keep records of the number of times that a function decorated with it is invoked.

1 trace_log = {}
2
3 def tracable(func):
4     def decorated_func(*arg, **kwarg):
5         if not trace_log.has_key(func.__name__):
6             trace_log[func.__name__] = 1
7         else:
8             trace_log[func.__name__] += 1
9         func(*arg, **kwarg)
10
11     return decorated_func
12
13 def print_trace_log():
14     for key, value in trace_log.items():
15         print "%s called %d times"%(key, value)
16
17 @tracable
18 def foo1():
19     print "foo1"
20
21 @tracable
22 def foo2(arg, kwd="keyword arg"):
23     print "foo2"
24     print arg
25     print kwd
26
27 @tracable
28 def foo3():
29     print "foo3"
30
31 foo1()
32 foo1()
33 foo1()
34 foo2(12)
35 foo2(13)
36
37 print_trace_log()

If we run the code, it will prints that foo1 function is called three times and foo2 function is called twice.
As the example showed, the code for implementing tracing is separated from business logic code contained within foo1 and foo2. The maintainability of the program is much higher than if the code for tracing is mixed with business logic code.

Summary
We got several benefits from decorator.
First, it helps achieve a better separation of business logic code and auxiliary code.
Second, it helps finding out where the auxiliary is used because decorator employs a very special syntax.
Third, we can extend or change our business logic without having to change existing code. New code can be implemented as a decorator.

References:
Charming Python: Decorators make magic easy
Decorators for Functions and Methods
PythonDecorators

install fcitx input method on ubuntu

2010-12-04T15:10:00.005+08:00

The default scim input method doesn't work well with freemind on my computer, so I'd like to switch to fcitx. The fcitx package in ubuntu repository is an old version, and to install fcitx manually isn't very straightforward, so I make this post about how I managed to get it to work.

1. Download fcitx source code and extract.
2. Make sure all dependent libraries are installed:

sudo apt-get install libpango1.0-dev libcairo2-dev xorg-dev libtool gettext intltool

3. Run configure && make && make install
4. At this time, fcitx failed to run and gave following error: fcitx: error while loading shared libraries: libfcitx-config.so.4: cannot open shared object file: No such file or directory. To fix it, create a symbol link in /usr/lib with this command:

sudo ln -s /usr/local/lib/libfcitx-config.so /usr/lib/libfcitx-config.so.4

5. Create /etc/X11/xinit/xinput.d/fcitx file with below content. Alternatively we can place them in ~/.profile.

XIM=fcitx
XIM_PROGRAM=/usr/local/bin/fcitx
XIM_ARGS=""
GTK_IM_MODULE=XIM
QT_IM_MODULE=XIM
DEPENDS="fcitx"

6. Edit /usr/lib/gtk-2.0/2.10.0/immodule-files.d/libgtk2.0-0.immodules file, change the line
"xim" "X Input Method" "gtk20" "/usr/share/locale" "ko:ja:th:zh"
to
"xim" "X Input Method" "gtk20" "/usr/share/locale" "en:ko:ja:th:zh"
7. Restart

To make fcitx more convenient to use, I run fcitx-config and change configurations below.

# Candidate Word Number
CandidateWordNumber=9
# Main Window Hide Mode
MainWindowHideMode=Auto
# Show Input Window After Trigger Input Mode
ShowInputWindowAfterTriggering=False
# Show Input Speed
ShowInputSpeed=False

Reference:
fcitx4.pdf

update to latest metauml

2010-11-26T15:20:00.001+08:00

The metauml package contained in the default texlive installation on ubuntu is the old version 0.2.3. This version doesn't support component diagram. I have to update to latest version manually. Here is how:

backup /usr/share/texmf-texlive/metapost/metauml
download metauml here
extract and copy everything under metauml/inputs to /usr/share/texmf-texlive/metapost/metauml
run "sudo texhash" to refresh texmf database, so that new version will be recognized

Now try the following diagram, it should compile fine.

1 input metauml;
2   beginfig(1);
3
4   Component.C("ComponentAAA")();
5   drawObject(C);
6
7   endfig;
8 end

draw uml with latex&metauml

2010-11-23T21:15:00.004+08:00

I've used and enjoyed the benefits of reversion control system for several years. RCS makes my life a lot easier. And it pushes me to highly prefer text format files over binary files, because text files can be managed by RCS more easily. metauml is a metapost library for creating uml diagrams, in text format.

Here are the steps to use it on ubuntu:

install texlive with: sudo apt-get install texlive
install metauml containing in metapost for tex: sudo apt-get install texlive-metapost

Texlive is also available for windows.
After all these tools have being installed, we can start our first uml diagram in latex.
Suppose we have following classes, and want to draw class diagram for them.

1 class Point
2 {
3 public:
4     int x;
5     int y;
6 };
7
8 class Shape
9 {
10     public:
11         virtual int get_circumference() = 0;
12         virtual ~shape();
13 };
14
15 class Circle : public Shape
16 {
17     private:
18         Point center;
19         int radius;
20     public:
21         int get_circumference();
22 };

We create below metapost file, save it as class_diagram.mp, and use "mpost class_diagram.mp" command to generate a postscript file, class_diagram.1.

1 input metauml;
2 beginfig(1);
3     %define classes
4     Class.Point("Point")("+x: int", "+y: int")();
5     Class.Shape("Shape")()("+get_circumference(): int");
6     Class.Circle("Circle")("-center: Point", "-radius: int")("+get_circumference(): int");
7
8     %layout classes
9     topToBottom(50)(Point, Circle);
10     leftToRight(50)(Circle, Shape);
11
12     %draw classes
13     drawObjects(Point, Shape, Circle);
14
15     %link classes
16     link(inheritance)(Circle.e -- Shape.w);
17     link(composition)(Point.s -- Circle.n);
18 endfig;
19 end
20

Then we create below tex file as a container document for the postscript. And use "pdflatex uml.tex" to generate the final pdf file.

1 \documentclass{article}
2
3 % The following is needed in order to make the code compatible
4 % with both latex/dvips and pdflatex.
5 \ifx\pdftexversion\undefined
6 \usepackage[dvips]{graphicx}
7 \else
8 \usepackage[pdftex]{graphicx}
9 \DeclareGraphicsRule{*}{mps}{*}{}
10 \fi
11
12 \title{MetaUML example}
13 \author{Raymond Wen}
14
15 \begin{document}
16
17 \maketitle
18
19 \section{Example}
20 \includegraphics{class_diagram.1}
21
22 \end{document}

A thing worth noticing is the latex document is of A4 size by default, which is not possible to contain a complex uml diagram. We can use "\paperwidth = 1024pt", "\paperheight = 1024pt", "\textheight = 800pt" command to create a document of arbitrary size. Here is more information about latex page layout.
The final diagram is shown below:

The advantages of using tex file to draw uml diagram includes:

We can concentrate on the content of the uml, rather than its layout
The diagram can be easily version controlled and compared
It's easier to make modifications
It's totally free
The output file format can be easily changed
It's possible to use/write tools to generate uml diagram automatically

avoid memory leak in osip

2010-11-15T20:17:00.000+08:00

I was debugging memory leak bugs recently. The bug was caused by incorrect usage of the osip library. It's not uncommon that we meet problems when we rely on a library or framework that we don't fully understand.

Symptom and debugging
The symptom is our application ran more and more slowly, and eventually crashed. This seemed very likely to be caused by resource leak. And after ran performance monitor against our application, it's further confirmed that memory was leaking. The virtual bytes, private bytes of the process was continuously increasing.
With the help of umdh.exe, we can find out exact lines of code that were leaking memory. It showed all stack traces of currently allocated memory blocks (including blocks that were either being used or leaked, so we must identify which blocks were in use and which were not) at the moment of dumping.

Causes
The causes of the memory leak is mainly caused by not understanding below items well.

transaction isn't destroyed automatically

Osip doesn't take full responsibility of managing life time of transactions. Though osip invokes callbacks registered with osip_set_kill_transaction_callback when a transaction is to be terminated, the transaction isn't freed automatically. This is supposed to be done by osip users.
The first thought I had is to call osip_transaction_free inside the kill_transaction callback, but it was wrong. Because the transaction is still accessed after the kill_transaction callback returned. So, a possible point to free transactions is to do it at the end of an iteration of the main loop, after all events have been handled.
I just don't get why this important point isn't mentioned in the official document.

inconsistent resource management model

In osip, there are inconsistency between APIs about how memories are managed. For example, we call osip_message_set_body to set the body of a sip message, this function internally duplicates the string we passed to it. So, we can (and need to) free the string passed to it after the function finishes. But when we want to call osip_message_set_method, be cautious! This function doesn't duplicate the string passed in, instead, it simply references the string we gave it. So, we can't free the string which is now owned by the sip message.
Such inconsistency makes it extremely easy to get confused and write code that either crashes or leaks.

blogporter v1.0.0 released

2010-10-20T21:48:00.004+08:00

The first version of blogporter is released. It's a utility for synchronizing posts between different blog service provider.
I wrote this tool because I need to maintain two blogs. It's annoying to have to copy and paste my posts to another blog. And the main reason I have two blogs is that blogger's service is not available in china mainland, due to a well-known reason. But I don't want to give up blogger's tight integration with my gmail account. So, I mainly write blogs here, and then use blog-porter to synchronize the other blog with this one.

Refer to http://code.google.com/p/blog-porter/ for more information about this utility.

The immediate usage of this tool is to sync posts from LiveSpace blog to other blog sites, because LiveSpace blog is soon to be closed. To do this, you can:

download LiveSpace blog data through http://{your_name}.spaces.live.com/Migration/Default.aspx
extract the downloaded zip file
install python, and BeatuifulSoup module
run "python blogporter.py --list-blogs" to find out supported blog provider
run "python blogporter.py --src-type=4 -p{path_to_unzipped_folder} --dst-type={number_stand_for_dst_blog_type} --dst-account={dst_blog_account} --dst-password={dst_blog_password} --startdate=2000-01-01 --enddate=2010-12-31 -v"

This tool still has limitations, mainly includes:

it doesn't sync comments
it doesn't sync category information from LiveSpace

I've tried below ways to work with LiveSpace, but failed to find a perfect solution.

metaweblog api, it's limited to retrieve 20 posts at most.
rss, it returns even less posts than metaweblog api. May be Google Reader API can helps us get more data through rss, since google cached a lot of historical rss data on their own server.
livespace backup file, it doesn't contain category information.

I finally choose livespace backup file to implement LiveSpaceProvider, hope this doesn't bother too much.

nook vs kindle 3

2010-10-16T12:53:00.003+08:00

I finally had a chance to play with kindle 3, and compared it with my nook.

Pros:

The greatest advantage I felt that kindle 3 is over nook is its speed. It's extremely fast to turn pages, at least twice faster than nook.
The second point that kindle 3 is totally over nook is its power sustainability, on which nook performs very poor. Kindle is said to be able to work for at least half a month in one charge, but my nook only can work slightly longer than half a week.
Kindle wins nook on size and weight as well. Though the screen size of them are the same, kindle is thinner and lighter than nook. Based on my feeling, kindle only weighs half nook's weight.
The display of kindle 3 is a little bit better. It's whiter. And its contrast is higher, so that the text is clearer and easier to read. But the difference is slight, you might not notice it if you don't have them on hand at the same time to compare.

Cons:

Kindle doesn't support epub format, which is a popular format with a lot of resources on the web.
Kindle doesn't handle pdf format as well as nook does. I opened the same pdf book on both devices, nook can wisely cut white margins of the pdf to make full use of its screen. Nook can also layout the content correctly when I chose to use a larger font. Kindle doesn't change the layout, it can only zoom into the page, which means I have to scroll the page rather than turning page to see more. But kindle support two viewport, landscape and portrait, this feature gains some point for it.
Nook is based on android, and you may extend its capability by installing new software. Thanks to nookdevs.

android touch event summary

2010-10-16T10:05:00.002+08:00

In "implement drag and drop on android", I wrote the rules how touch event can be passed to the touched view's parent, and how a parent can intercept the touched view's event. On a device without mouse, Click and LongClicked events are also strongly related to touch event. So, I'll summarize how they are related.

Button widget doesn't bubble event. If a button is touched, it doesn't pass the event to its parent in any case. (There should be more widgets exhibit this character.)
Touch event doesn't bubble up to parent if the widget also registers Click or LongClick event handler.
If a widget registers both Touch and Click event handler, Click event fires only when Touch event handler returns false. In other words, Click event gets fired only when touch event handler declares it's not interested in the touch event.
If a widget registers both Click and LongClick event handler, and LongClick event get fired. Click event will be fired only if LongClick event handler returns false.

Testing Code:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/android/touch_events/

repair mac login failure due to invalid home directory

2010-10-11T20:25:00.000+08:00

My macbook failed to start and gave me "the password you entered is invalid" on login. It happened after my user directory is changed.
By default, mac system saves a user's personal data in /Users/user_name directory. In order to make the system easier to maintain and keep my personal data separated from system data. I created two partitions during installation. One partition is used for system installation, and the second partition is used as my home directory.
To do this, after the mac has been successfully, I copied all data from original /Users/user_name directory to /Volumes/user/user_name directory. Then I remove /Users/user_name directory, and created a soft symbol link /Users/user_name pointing to /Volumes/user/user_name. Everything work perfectly.
The problem occurred after I considered the /Volumes/user directory a poor name and changed it to a better one, /Volumes/idiot. After I restarted the machine and found I can't log into the system. Mac simply complained about my password wasn't correct, though I'm pretty sure it's correct.
The reason is I forgot to change /Users/user_name symbol link to correct place. I guess mac stores my credential in my home directory. So if this directory isn't accessible, all my login attempts failed.
To repair this, I tried mounting the mac hard disk on a ubuntu box and changing the symbol link. But due to the file system (HFS, Hierarchical File System) is journaled, it's read-only on ubuntu.
I finally found another mac machine and changed the symbol link correctly. In case I may encounter this problem again, I used "sudo diskutil disableJournal /Volumes/user" command to turn off jorunaling on the file system so that it'll be writable under ubuntu. The cost is the mac may take much longer time to scan file system if not shutting down properly. It deserves, at least I can log into the system.

References:
Repair / Fix Mac HFS+ partition using Ubuntu CD
How to Move the Home Folder in OS X – and Why

How to Build a Nook emulator

2010-09-28T11:04:00.007+08:00

due to nookdevs isn't accessible, I make a copy of their document about how to build nook emulator here. Also, I shared my system.img for nook at the end this post as well.

Android Emulator for the Nook

It is very possible to run the Barnes and Noble Nook firmware in the Android Emulator. It is time to start developing some Google Android Apps for it.
Instructions for Unix/Linux

In order to do this, you will need to:
Download the Android SDK and install it. Install the Platform 1.5 SDK using tools/android in the Android SDK.
Grab the original 1.0.0 image from bn.com (mirrored here: multiupload).
Run dd if=signed_bravo_update.1.0.0.dat of=signed-bravo-update.1.0.0.tar.gz bs=1 skip=152 (On Windows use this tool. At the command line run gzip-extract signed-bravo-update.1.0.0.tar.gz bravo_update.dat. NOTE: gzip-extract requires the .net framework. Afterwards rename bravo_update.dat to signed-bravo-update.1.0.0.tar.gz)
Extract signed-bravo-update.1.0.0.tar.gz.
Rename bravo_update.dat to bravo_update.tar.gz and extract it.
Extract root.tgz.
Extract root/system/framework/services.jar with your favorite unzip utility.
Download and install smali. You need at least baksmali-1.1.jar and smali-1.1.jar. For your sanity, grab the wrapper scripts as well.
Run baksmali classes.dex on the classes.dex from services.jar to disassemble services.jar
Edit out/com/android/server/ServerThread.smali and remove the line if-lt v0, v1, :cond_483 This should be line 966. (In version 1.0.0)
Run smali out/ to re-assemble classes.dex with our fixes.
Rename out.dex to classes.dex and copy this classes.dex to services directory, overwriting the original classes.dex.
Delete the out directory and re-jar the services directory.
Make an Android Device (AVD entry) in the Android Emulator with target platform 1.5 and skin/screen size of 549 by 924 (real resolution is more like 600x944 but the emulator won't start at that size), name it nook (case sensitive).
If you are unable to create the AVDs (something like Error: Ignoring platform 'google_apis-3-r03': build.prop is missing. ) then install Eclipse, install the Android plugins for Eclipse and you will be able to create the AVDs from there.
grab lib/libaudioflinger.so from stock system.img supplied with Android SDK using unix utility unyaffs to extract the file
overwrite the libaudioflinger.so from the system/lib directory in the nook firmware with the stock Android SDK one.
use mkyaffs2image to make a system.img of the system/ of the nook firmware.
rename system.img in the 1.5 firmware platform folder to system.good and copy in replacement system.img file you just created (it will be bigger than the SDK Android system.img (approximately 108Mb)
Run the emulator by using command line emulator @nook -shell -show-kernel -verbose The emulator will take a few minutes to boot.
You will NOT be able to register your emulated Nook with BN.com but you can sideload epub books but placing them in system/media/guides when you create your replacement system.img file mentioned in step 17.

References:

http://denverdroid.blogspot.com/2010/05/how-to-build-nook-emulator.html (in detailed steps)

http://code.google.com/p/nookdevs/ (nookdevs project repository)

http://code.google.com/p/rxwen-blog-stuff/downloads/detail?name=nook_1.0.0_system.img.zip&can=2&q=  (image for downloading)

how to soft-root your nook

2010-09-28T10:58:00.000+08:00

I don't know for what reason, the nookdevs.com isn't accessible. So I made a copy of their document about how to soft-root nook here:

How to soft-root your Nook

Thanks to nookdevs.com for rooting the device. Guideline provided by nookdevs.com.

What is soft-rooting?
The softroot is a way to enable the ADB without disassembling nook to gain root shell access on both 3g-equipped (original) and WiFi-only nooks (thanks to muchadoaboutnoth from IRC for confirming that). If you don't know what that means, you probably DO NOT want to run this updater on your nook. As of today, the nook's adb runs over WiFi, you can enable ADB over USB however. Read more on benefits and disadvantages of rooting and why rooting matters.

WARNING
While we've taken great pains to make sure that this script won't damage your expensive new eBook reader, it comes with ABSOLUTELY NO WARRANTY. To date, it has been tested on nooks running 1.0.0, 1.1.0, 1.1.1, 1.2, 1.3 and 1.4 of the nook firmware on both the 3g-equipped (original) and WiFi-only nooks (thanks to muchadoaboutnoth from IRC for confirming that). If it breaks, you get to keep both pieces. In the unlikely event that you run this script and end up with a paperweight, please join us on #nookdevs (alternatively thru webchat) on irc.freenode.net and we'll see what we can do.

Once you run a third-party software updater on your nook, Barnes & Noble may consider your warranty null and void. It's sort of like strapping a rocket engine to your Civic -- If you hit the side of a mountain at 300mph, it's just not Honda's fault.

If you run this updater and your nook appears to have become a (very expensive) paperweight, DO NOT CALL BARNES & NOBLE. Join us on IRC and we'll do our best to help sort you out.

Barnes & Noble have built a really fantastic Android tablet for us. So far, it looks like it's going to be an amazing platform for third-party experimentation and development. To make sure that that stays true, there are some things you should keep in mind:
3G is for B&N resources only, if you truly think you spent $259 $199 for unlimited 3G for life, you're delusional. You can, however, use your own SIM-card for browsing thru 3G on a softrooted nook.
A number of nook owners have asked us about the nook's DRM. Don't steal books.

If we haven't scared you off, it's time to get your new rocket engine set up.

A word about 1.4 update
The instructions below will help you downgrade to 1.0.0 (which will wipe your nook settings clean) and then upgrade to the 1.4 update with the pre-installed softRoot + nookLauncher + nookLibrary + nookWifiLocker + Trook + VNC + busybox (update file courtesy of perfinion and poutine; the apps are by kbs, hari and hazymind). This streamlined rooted update retains the turboboot/uboot as is, so you will not have to downgrade prior to upgrading to rooted images in the future.

If you have already updated to the stock 1.4 (either manually or via OTA update), you can still softroot your nook following the same steps below (you will however lose your settings when you downgrade to 1.0.0).

If you currently have a nook with 1.1.1 B&N software or 1.2/1.3 softRoot software, you can skip the section about downgrading to 1.0 again and go directly to the How do I do it? section to upgrade to the rooted 1.4. You should not lose any settings during the update.

IMPORTANT: You will need to REBOOT after you get to the nook "home screen" on the first initial boot!

Known issues with softRooted 1.4 update:
WiFi Lock might not work
IMPORTANT: You will need to REBOOT after you get to the nook "home screen" on the first initial boot!

Pre-requisites
You need a B&N nook.
You need a 128MB-or-higher microSD card with a single, FAT32-formatted partition.
You need to download the rooted 1.4 update (do not forget to rename file to bravo_update.dat):
Full softRoot (root/ADB + apps) download(SHA1 hash: 5a62a2a3ad4ffa5ea6fe2c93ebe241ead5376cd0)
You'll also need the 1.0.0 image download(you won't need this if you have softrooted/streamlined 1.2 or 1.3 on your nook).
MD5 hash: c752fa57f7253d4c499398630c27bdab
SHA-1 hash: 84287d73b70e98da6a6af9f362b31e96d4e6eea4
SHA-256 hash: a22bbbf1cc61a81fd812abc5b75f5c713cab3471be36219897 aeb91b26405b35
You won't need any tools or a clean work surface. Unlike our initial efforts, this tool is a simple software updater. There's no need to crack your nook open.
Should you want to use older version of the nook software, you can download one of the obsolete versions.
Attention Chrome users: if instead of the bravo_update.dat and signed_bravo_update.dat you end up with bravo_update.dat.zip and signed_bravo_update.dat.zip accordingly, DO NOT UNZIP these files, you will just need to rename them to bravo_update.dat and signed_bravo_update.dat.

How do I do it?
Here is an overview of the process you'll go through. These are not step-by-step instructions. This is only an overview. Follow the instructions in the following sections.

Back up any files on your nook, as it WILL be erased during this process.
Manually install nook software 1.0.0 (downgrade)
Manually install modified nook 1.4 software (upgrade & root)
Use the Android Debug Bridge to access your nook's root shell over Wi-Fi.
If you already have softrooted 1.2 or 1.3 update on your nook, you just need to apply softrooted 1.4 update, no need to downgrade to 1.0.0 first.

Step 1: Prepping your nook (downgrade to 1.0.0)
You only need to do this if you have applied the B&N 1.2, 1.3 or 1.4 update. If you are currently running softrooted/streamlined 1.2 or 1.3 by poutine, skip this section.

Make sure your nook has sufficient battery to complete the procedure without turning off (at least 20%).
BACK UP ANY FILES ON YOUR NOOK. This bears repeating: you WILL lose your data if you do not.
Download the original nook 1.0.0 software image (see the Pre-requisites section).
Rename the file you downloaded, if necessary, to signed_bravo_update.dat.
If you haven't already, connect your nook to your computer via USB. The "nook" drive should appear—this is your nook's internal microSD card.
Copy the 'signed_bravo_update.dat' file to the "nook" drive.
Eject/unmount the "nook" drive. Remove USB cable. (Note: The B&N Home screen should show some indication that it's unpacking and checking the update after this step)
The update procedure should begin automatically—look at the lower-right corner of your nook's e-ink screen and there should be a small box that says "Preparing update" with a percent-complete indicator.
DO NOT turn off the power during this procedure. The nook will reboot itself when it is done.

Step 2: Rooting your nook (upgrade to modified 1.4)
Warning: This process requires that you are running the original bootloader (nook 1.0.0 software). Odds are that unless you followed the directions in Step 1: Prepping your nook above, you probably aren't. In order to get the original bootloader installed, downgrade to the full 1.0.0 image via sideloading as explained above before proceeding with the softroot.

Make sure your nook has sufficient battery to complete the procedure without turning off (at least 20%).
Download the rooted nook 1.4 software (see the Pre-requisites section).
If you haven't already, insert a microSD card in your nook (see Inserting extra storage in your nook if you need help with that).
Plug your nook into your computer via USB. You should see two drives appear: a "nook" drive (this is your nook's pre-installed, internal drive) and one more.
Unlike in Step 1, you are going to use the second drive, not your nook's internal drive (the one named "nook").
Copy the file you downloaded, which should be named "bravo_update.dat", to the nook's external drive identified in the previous step.
Eject/unmount both drives: the one for your external card, and the internal "nook" drive.
Unplug your nook from your computer.
Turn off your nook by holding in the sleep/power button on top until the screen turns blank.
Press and hold the upper page-flip button on the right-hand side of your nook (the one marked with a < pointing towards the middle of the e-ink screen).
While continuing to hold the page-flip button, press and release sleep/power button on top. Don't let go of the page-flip button.
Continue holding the page-flip button until the e-ink screen displays a "checking for update" message. Release the page-flip button within a couple seconds of when you see this message.
Timing is key. If your nook displays the typical "Starting Up" screen, you've missed it—wait until it starts up, then turn it off and try again.
Wait for your nook to finish running the updater (the touchscreen will show the progress).
Wait for your nook to fully start up after successful update, and then manually reboot it (hold the power button for about 5 seconds so that both screens shut down and then start your nook again).
It is very important, so I repeat again: Wait for your nook to fully start up after successful update, and then manually reboot it (hold the power button for about 5 seconds so that both screens shut down and then start your nook again). It is very important to reboot after an update!
That's it! You've rooted your nook.

You can delete the bravo_update.dat file from your nook's external card; you no longer need it.

Step 3: Getting a root shell with the Android Debug Bridge
How to use your newly-rooted nook:

Download and install the Android SDK.
Find the IP address of your nook (instructions are here: How to find nook's IP address).
In a terminal (command line) window, navigate to the "tools" directory in the Android SDK.
With the NOOK_IP being the IP address of your nook, enter the following:
adb connect NOOK_IP:5555
Nothing should appear to happen and you will be returned to your command prompt. This is normal.
You can now use the ADB tools to talk to your nook. To get a root shell on the nook, enter:
adb shell
A # should appear — you now have root access to your nook's command line interface!
You can also enable ADB over USB. Complete documentation for the Android Debug Bridge is available here.

Things you may want to do with your newly-liberated nook:

Install native Android applications. See application directory for more information. The modified 1.2 and up full softRoot updates already come with several nifty applications pre-installed.
Develop nook-optimized Android applications. Installing the nook emulator on your computer may be of great use for you then.

Have fun!

recovering GRUB bootloader on windows/ubuntu dual boot machine

2010-09-24T21:17:00.000+08:00

I installed both windows and ubuntu on my laptop. It's easy to dual boot because I installed ubuntu after windows. But for some reasons, I have to reinstall windows.
And after windows is installed, dual boot no longer work because windows installer overwrited the mbr. I didn't want to install ubuntu again, and luckily, I found this: Dual Boot Ubuntu and Windows.
In short, we can fix the grub with following steps:

Boot with ubuntu live cd
Mount the ubuntu installation file system
Reinstall grub with "grub-setup -d ubuntu_installation_path/boot/grub" command

understanding drawBitmapMesh on android

2010-09-24T20:52:00.001+08:00

The Canvas.drawBitmapMesh method on android is a like a mystery to me while I looked at the BitmapMesh sample. Though I tried to get some hints from the official document, it didn't help much. After played it with several tests, I got some ideas about how it worked.

A metaphor
The effect of drawBitmapMesh can be thought as pinching a point of an elastic canvas, and pull it to another point. The distorted image is very similar to what we shall get through drawBitmapMesh. Like the figures below show.

How the mesh affects the bitmap
The bitmap to be drawn is divided into equal size blocks. And the division is defined by the mesh, which is a float array. The array defines the lines that divide the bitmap. To have a division of W*H blocks, there needs to be (W+1)*(H+1) lines. These lines intersect at (W+1)*(H+1) points. Every two consecutive elements in the array corresponds to the x coordinate and y coordinate of an intersection. So, the mesh array comprises of 2*(W+1)*(H*1) elements. Given the bitmap's size is known, the drawing engine can find out the x and y coordinates of intersections by dividing the width or height of the image to W or H, respectively. So, if the x and y coordinates of an intersection supplied in the mesh doesn't equal to its intact values, the drawing engine will "pinch and pull" the intersection from its original location to the location we define.
Keep in mind that for a intersection that deviates its original location, only those four blocks that around it will be affected. All other blocks that are more than one blocks away from the intersection will remain intact.

avoid designing by coding

2010-08-29T13:14:00.003+08:00

I found a obvious, stupid mistake in my c++ code. The mistake itself is trivial and doesn't worth mentioning. What I'm interested in is what lead me to making such a mistake that a very fresh c++ learner can easily recognize.
The main reason is I was designing by coding (implementing). Designing and coding are very separate tasks in a programming project. The goal of designing is to find out an effective way of organizing our code (classes, modules, layers, etc.) so that the code is easy to understand, maintain and to be changed. The goal of coding is implementing required features based on design. Because designing and coding have different goals, there are different ways to do them. But I chose to do them simultaneously, that is, thought about the design and wrote code immediately, even before I had a clear idea of the whole design. In this way, I always didn't have a sole goal in mind, but had to think about multiple things. It's not natural for human brain to work this way. Especially considering the complexity of c++ language, if we can't fully focus on the implementation details, we are very likely to be bitten by it. The case might be less painful if we work with other languages like c#, python, which have much less details to concern. But it's generally wise to choose a more suitable tool to do the design other than coding, for example UML, or other diagrams. And code review is a good way to get rid of such mistakes.

looper and handler in android

2010-08-22T19:10:00.003+08:00

It's widely known that it's illegal to update UI components directly from threads other than main thread in android. This android document (Handling Expensive Operations in the UI Thread) suggests the steps to follow if we need to start a separate thread to do some expensive work and update UI after it's done. The idea is to create a Handler object associated with main thread, and post a Runnable to it at appropriate time. This Runnable will be invoked on the main thread. This mechanism is implemented with Looper and Handler classes.

The Looper class maintains a MessageQueue, which contains a list messages. An important character of Looper is that it's associated with the thread within which the Looper is created. This association is kept forever and can't be broken nor changed. Also note that a thread can't be associated with more than one Looper. In order to guarantee this association, Looper is stored in thread-local storage, and it can't be created via its constructor directly. The only way to create it is to call prepare static method on Looper. prepare method first examines ThreadLocal of current thread to make sure that there isn't already a Looper associated with the thread. After the examination, a new Looper is created and saved in ThreadLocal. Having prepared the Looper, we can call loop method on it to check for new messages and have Handler to deal with them.
As the name indicates, the Handler class is mainly responsible for handling (adding, removing, dispatching) messages of current thread's MessageQueue. A Handler instance is also bound to a thread. The binding between Handler and Thread is achieved via Looper and MessageQueue. A Handler is always bound to a Looper, and subsequently bound to the thread associated with the Looper. Unlike Looper, multiple Handler instances can be bound to the same thread. Whenever we call post or any methods alike on the Handler, a new message is added to the associated MessageQueue. The target field of the message is set to current Handler instance. When the Looper received this message, it invokes dispatchMessage on message's target field, so that the message routes back to to the Handler instance to be handled, but on the correct thread.
The relationships between Looper, Handler and MessageQueue is shown below:

This design is very similar to win32's message loop. The benefit of this design is that we no longer need to worry about concurrency issues while manipulating UI elements because they are guaranteed to be manipulated on the same thread. Without this simplicity, our code may bloat heavily because we have to lock access to UI elements whenever they are possibly accessed concurrently.

The example at the end of this post shows how to send messages to different handlers associated with main Looper (Main Looper is created via prepareMainLooper in ActivityThread.main).

Example:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/android/looper_and_handler/

implement drag and drop on android

2010-07-29T21:34:00.002+08:00

Nowadays, drag and drop is a frequently seen feature on touch screen devices. Tthis post introduces the basic idea of how to implement drag and drop on android.

On android, touch event is composed of a series events.
First, user puts his finger on an element, and the element receives a ACTION_DOWN event.
Then, while holding finger on screen, user moves his finger to a new location. The element receives a series of ACTION_MOVE events.
Finally, user raises his finger. At this point, the element receives ACTION_UP event.
Consider the figure below, the parent element has a child element inside. User can drag the child element anywhere in parent.

There are two important traits of touch event on android.
First, touch event will be propagated. That is, if a child chooses to ignore the first event (ACTION_DOWN) by returning false in its onTouchEvent handler, the parent's onTouchEvent handler will receive the event. Unless one of the ancestors agrees to handle the event or the root is reached, the event will continually be propagated.
Second, parent can intercept the touch event before its child's onTouchEvent handler is fired. This is achieved by overriding the onInterceptTouchEvent method on parent, and returning true from it. As a consequence, the child's onTouchEvent handler will be bypassed, and the parent's onTouchEvent handler will fire.
The work flow is shown in below diagram:

We need to setup the onTouchEvent handler for both child and parent. In child's handler, we save the child element as the item to be dragged, and return false so that subsequent event will be delivered to parent's handler. In parent's handler, we change the child's margin to match the position of the finger, so the child will follow our finger.

Sample code:
http://code.google.com/p/rxwen-blog-stuff/source/browse/#svn/trunk/android/drag

Reference:
http://developer.android.com/guide/topics/ui/ui-events.html

nook's battery sucks

2010-07-28T22:04:00.000+08:00

nook's battery is advertised to be able to run for around 10 days if users trun off the wifi. But my nook can only run for 4 days at maximum, even if I always turn air mode on. On average, I used it for two or three hours per day. That's to say, its battery can only support 12 hours normal usage! It seems the culprit is even in sleep mode, the nook still consumes a lot of battery. In this review for nook, it's said nook consumes battery while turned off !! Ridiculous!

why offsetof can use null pointer

2010-07-18T14:30:00.000+08:00

offsetof is a widely used means in c and c++ to find out the offset of a member variable in its struct or class. The most normal way to implement it is via following macro:

#define offsetof(st, m) ((size_t) ( (char *)&((st *)(0))->m - (char *)0 ))

The idea is very simple. We declare a target type pointer pointing at address 0, then we retrieve the address of its member variable. Because the start address is 0, the value of the pointer to member is the offset.
Everything is clear and simple. But wait, look at how we retrieve the address of the member, it's deferencing a pointer to 0. Why id doesn't give us a segmentation fault?
To understand this, let's check the c code below which retrieve the offset of member c in struct foo.

1 #include    "stdio.h"
2
3 struct foo
4 {
5     int a;
6     char b;
7     int c;
8 };
9
10 int main ( int argc, char *argv[] )
11 {
12     struct foo* fp = (struct foo*)0;
13     unsigned int offset = (unsigned int)&fp->c;
14     printf("offset of c is %u\n", offset);
15     return 0;
16 }               // ----------  end of function main  ----------

Then compile it with miscrosoft's c++ compiler, and dump the revelant assembly code generated by the compiler. We got this:

1 _main:
2   00401010: 55                 push        ebp
3   00401011: 8B EC              mov         ebp,esp
4   00401013: 83 EC 08           sub         esp,8
5   00401016: C7 45 FC 00 00 00  mov         dword ptr [ebp-4],0
6             00
7   0040101D: 8B 45 FC           mov         eax,dword ptr [ebp-4]
8   00401020: 83 C0 08           add         eax,8
9   00401023: 89 45 F8           mov         dword ptr [ebp-8],eax
10   00401026: 8B 4D F8           mov         ecx,dword ptr [ebp-8]
11   00401029: 51                 push        ecx
12   0040102A: 68 5C DC 41 00     push        41DC5Ch
13   0040102F: E8 14 00 00 00     call        _printf
14   00401034: 83 C4 08           add         esp,8
15   00401037: 33 C0              xor         eax,eax
16   00401039: 8B E5              mov         esp,ebp
17   0040103B: 5D                 pop         ebp
18   0040103C: C3                 ret

It's clear that the compiler doesn't blindly follow the null pointer to get its member variable's address. Instead, because the compiler knows the structure and layout of struct foo, it adds the offset (which is already known to the compiler) of member c to the starting address of struct foo to find out the address of c.
offset doesn't access memory pointed to by the null pointer. That's why we didn't get invalid memory access error while using a null pointer.

got nook

2010-07-17T16:17:00.002+08:00

Finally, after more than two weeks' waiting, my nook was delivered to me.

nook and accessories:

screensaver:

main menu:

viewing pdf:

micro-sd card socket:

There are two set of go to previous/next buttons on both left and right side of nook for user's convenience. But they are rather hard to press, and make tick noise upon pressing. A bit annoying if use it in a quiet environment. Then I found in nook's manual that the touch screen in the bottom can also be used for navigation. After the touch screen goes dark, I can swipe my finger on it to navigate. A quick (must be quick enough) swipe from right to left turns to next page, and the oppisite direction turns to previous page. No noise at all.
A flaw with this clever design is the direction of swiping on touch screen is different from the hard button's arrow direction. The hard previous button has a left arrow on it. But the direction for turnning to previous page is from left to right. So wierd.

performance impact of printf

2010-07-07T13:23:00.000+08:00

Logging is a widely used debugging means. As a way of implementing logging, I saw printf used in a lot of places. It's so quick and easy to use printf to examine the behavior of an application. But it also has heavy impact of the performance of the application, meanwhile, it makes our logging a mess and difficult to read without careful forethought.
The code snippet below calculates the fibonacci number. On line eight, I used printf to print some values. Very simple code. I compiled the code with different printf statement on line eight and run the application to see the performance.

1 int fib(int a)
2 {
3     int rc = 0;
4     if(a < 2)
5         rc = a;
6     else
7         rc = fib(a-1) + fib(a-2);
8     printf("rc = %d, a = %d\n", rc, a);
9     return rc;
10 }
11
12 int main(int argc, char* argv[])
13 {
14     int t1 = GetTickCount();
15     printf("before fib: %d\n", t1);
16     int result = fib(16);
17
18     int t2 = GetTickCount();
19     printf("after fib: %d   %d %d \n", t2, t2 - t1, result);
20     return 0;
21 }
22

The list below shows the time ticks spent with different printf statements, in decreasing order.

4188 (printf("rc = %d, a = %d\n", rc, a) )
3617 (printf("helloworld"))
844    (printf("a"))
858    (printf("%d\n", rc))
302    (printf("%d", rc))
2        (no printf)

It's very clear that the performance drops dramatically if the printf statement is there, and the more complex the format string is, the poorer the performance is. The performance is even 2000 times poorer if we compare the worst case and best case.
The reason is printf needs to invoke system call to output data, which incur a lot of transitions between user mode and kernel mode. And a complex format string also consumes a lot of processing time.

In order to get rid of the performance penalty, yet keep the capability of saving log. We must use a mature logging system, instead of printf directly. An ideal logging system should support switch, logging level and many output mechanisms.
While writing code, we're always enticed to use printf simply because it's easy to write. In contrast, a logging system should require us spending 10 minutes to understand and use. But, the time spent really deserves, considering the time we must spend later on organizing and cleaning printf statement and the possible performance impact of printf.

paste in vim command line

2010-07-05T20:26:00.001+08:00

To be able to paste something to vim's command line is a feature makes our life a lot easier. For instance, say we want to change a frequently used variable name in c source file from a_super_long_inproper_variable_for_caching_bank_account_balance to balance. To replace all of the variable's occurrence, we plan to use following replace command:

:%s/a_super_long_inproper_variable_for_caching_bank_account_balance/balance/g

Without paste capability, we have to type the variable name ourself, maybe several times because we doom to type the name wrong.
Luckily, vim has at least two ways to rescue us from having to type the name.
1. command-line window
command-line window is a separate window that enables us editing command just like working in a normal window. Plus, it lists command history. So, we can easily copy the variable name via yank command and paste it to command-line window. To open the command-line window, we can type q: while in normal mode. For more information about command-line window, see help q: in vim.
2. paste with Ctrl+R shortcut key combination
Instead of opening a separate command-line window, we can also paste directly in vim command line. While editing within command line, we can use Ctrl+R, Ctrl+W key combination to paste the word currently under cursor in last window to command line. Beside the forgoing shortcut key, vim features a lot of key combination that let us paste from different sources, like registers, file name, etc. Run :help c_CTRL-R to find more out its real power.

Reference:
Vim documentation: cmdline

perform profiling on windows ce

2010-07-01T20:07:00.001+08:00

Profiling is an effective way of finding out bottlenecks in an application. On windows ce platform, profiling can also be done easily.

To perform profiling for native code, we can use the /callcap compiler option to enable callcap profiling. After it's enabled, the compiler will inject method invocation to _CAP_Enter_Function and _CAP_Exit_Function upon entering and returnning from a function respectively. We can print or log current time in these method to achieve profiling.
It's notable that while compiling the source file contains _CAP_Enter_Function and _CAP_Exit_Function's definition, we must disable /callcap option, otherwise, these function will call themself recursively. In most cases, it's a wise idea to create a library project to implement these profiling hook fuction and trun /callcap off for the project. Then link the library to other applications to be profiled.
For demonstration, here is a visual studio project shows how to do profiling:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/wince/ce_profiling/

After we run the application, we get below output:

Enter function (at address 00011068) at 73875892
Enter function (at address 00011030) at 73875897
Enter function (at address 00011000) at 73875902
bar
Leaving function (at address 00011000) at 73876907
foo
Leaving function (at address 00011030) at 73879912
Leaving function (at address 00011068) at 73879916

As you can see, it's a very rough sample that only prints the address of function being called. Not convenient to analyse. We may improve it by mapping and translating the address to function name, because we, as the application developer, possess the private symbol file. This task doesn't need to be done on the windows ce box, it's much easier to save the log file then parse and analyse it on a pc.

References:
Remote call profiler
A tour of windows ce performance tools

openoffice exports better pdf than word

2010-06-25T22:28:00.002+08:00

I generated a pdf file from a word document with word 2007. But the pdf file looks very uncomfortable in my pdf viewer. So I looked it closely to see what makes me feel so. The culprit is the spacing between characters. As shown in the image blow, the spacing between characters within a word varies in the pdf file, though the original word document doesn't exhibit this.
I tried to export the pdf file with openoffice again. To my surprise, the generated file looks very smooth and comfortable. The spacing between characters is perfect, just as they are in doc file. Also, the edge of the font is much more clear.

I usually don't pay much attention to details like fonts and spacing. But the performance between word and openoffice differs so much that it's hard to not to notice them. I just don't get how word deserves its price.

debugging python script in ipython

2010-06-09T21:39:00.004+08:00

ipython doesn't work with built-in pdb debugger. While I tried to debug a python script with "run -d script.py" within ipython shell, I got bellow error:

AttributeError: Pdb instance has no attribute 'curframe'

To debug script in ipython, we need to use a different debugger, pydb, for example. There are only three steps to setup and use it.

download and install pydb.
start ipython with -pydb argument: ipython -pydb
start debugging with: run -d script.py

It's mandatory to set HOME environment variable to use pydb. On my windows box, there is no HOME environment variable set by default, and I got bellow error:

KeyError: 'HOME'

It can be solved by adding HOME environment variable.

Because pydb use the same set of commands with gdb, it's fairly straightforward to get start with it if you have done some debugging in gdb. This is one reason why I pick it as my debugger.

Reference:
Introducing the pydb Debugger
Debugging in Python

install ipython and readline on mac

2010-06-06T10:47:00.003+08:00

ipython is a powerful interactive shell for python. With it, we can tak advantage of python programming language in our daily works.
One of ipython's power is its tab-completion feature that needs readline to work. On mac system, it lacks this library due to license issue. There is a proprietary version of readline in mac, but it doesn't work with ipython.
To install them on mac system, we can simply use easy_install utility, like this:

sudo easy_install ipython readline

use ffmpeg to setup streaming server on android

2010-05-22T10:03:00.005+08:00

ffmpeg is a powerful media library. It provides ffserver tool that can be used to setup a streaming server.
Here is how to compile ffmpeg for android, using CodeSourcery's cross compiler.

1. Download and extract ffmpeg source code.
2. Use below commands to compile ffmpeg

./configure --arch=arm --cross-prefix=arm-none-linux-gnueabi- --extra-ldflags=-static --target-os=linux
make

3. Run file ffserver && readelf ffserver -d or arm-none-linux-gnueabi-objdump ffserver -x | grep NEEDED commands to make sure ffserver is statically linked
4. Transfer ffserver tool, ffserver.conf file (defines what media files will be served by ffserver) and media files to android with adb push command
5. Start streaming server with ./ffserver -f ffserver.conf on andoird shell

Below is a sample ffserver.conf file, which tells the ffserver to listen on rtsp port 7654. It defines two media files for streaming, /data/1.mp3 and /data/1.mp4, respectively. So make sure these files exist.

# Port on which the server is listening. You must select a different
# port from your standard HTTP web server if it is running on the same
# computer.
Port 8090

# Address on which the server is bound. Only useful if you have
# several network interfaces.
BindAddress 0.0.0.0

# Port on which the server is listening. You must select a different

# port from your standard HTTP web server if it is running on the same

# computer.

RTSPPort 7654

# Address on which the server is bound. Only useful if you have

# several network interfaces.

RTSPBindAddress 0.0.0.0

# Number of simultaneous requests that can be handled. Since FFServer

# is very fast, it is more likely that you will want to leave this high

# and use MaxBandwidth, below.

MaxClients 1000

# This the maximum amount of kbit/sec that you are prepared to

# consume when streaming to clients.

MaxBandwidth 1000

# Access log file (uses standard Apache log file format)
# '-' is the standard output.
CustomLog -

# Suppress that if you want to launch ffserver as a daemon.
NoDaemon

<Stream 1.mp4>
Format rtp
File "/data/1.mp4"
</Stream>

<Stream 1.mp3>
Format rtp
File "/data/1.mp3"
</Stream>

To test ffserver, we can start a media player that supports media streaming, and open the url: rtsp://{ip address of the android device}:7654/1.mp3.

invisible directshow render window

2010-05-21T21:08:00.003+08:00

A common task we may want to achieve while creating a media application is to start media playback on a new thread, as the sample below shows:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/multimedia/directshow/dbg_directshow_thread_issue/dbg_directshow_thread_issue.cpp
In the menu of the sample, there are two items. "Render File" will start playback on main thread of the application. "Render New Thread" will create a new thread to playback. Everything work fine in the first case, but in the second case, the directshow rendering window isn't visible, I can only hear sound.
Then I debugged the application with spy++. The image below shows all windows when the media is rendered on main thread. There is a VideoRenderer window exists on main thread.

In contrast, the image below shows all windows when the media is rendered on a new thread. The VideoRenderer window doesn't exist.

I added two lines of code at the end of Render method to block the new thread so it didn't exit after the media playback started. This time, the render window can be seen. All windows are shown below, in which the VideoRenderer window is there.

Actually, the issue has to do with windows working mechanism. A window's window procedure executes on the thread that creates the window. If the corresponding thread ends, the window will also end. That's why we have to keep the new thread from exiting to keep the VideoRenderer window alive.

[quotation from programming windows by Charles Petzold]
Although Windows programs can have multiple threads of execution, each thread's message queue handles messages for only the windows whose window procedures are executed in that thread. In other words, the message loop and the window procedure do not run concurrently. When a message loop retrieves a message from its message queue and calls DispatchMessage to send the message off to the window procedure, DispatchMessage does not return until the window procedure has returned control back to Windows.
However, the window procedure could call a function that sends the window procedure another message, in which case the window procedure must finish processing the second message before the function call returns, at which time the window procedure proceeds with the original message. For example, when a window procedure calls UpdateWindow, Windows calls the window procedure with a WM_PAINT message. When the window procedure finishes processing the WM_PAINT message, the UpdateWindow call will return controls back to the window procedure.
This means that window procedures must be reentrant. In most cases, this doesn't cause problems, but you should be aware of it. For example, suppose you set a static variable in the window procedure while processing a message and then you call a Windows function. Upon return from that function, can you be assured that the variable is still the same? Not necessarily—not if the particular Windows function you call generated another message and the window procedure changes the variable while processing that second message. This is one of the reasons why certain forms of compiler optimization must be turned off when compiling Windows programs.
In many cases, the window procedure must retain information it obtains in one message and use it while processing another message. This information must be saved in variables defined as static in the window procedure, or saved in global variables.
[/quotation]

When working with directshow, it's not necessary to create a new thread explicitly. It's fine to start playback on main thread because the main thread won't be blocked.

logging with osip

2010-05-20T19:56:00.002+08:00

As I posted before, logging is an important debugging means. In order to be truly useful and convenient, the logging module should at lease have two traits:

can be turned on and off globally
supports the concept of logging level

osip also comes with a mature logging system. Besides the traits I just mentioned, it also enables we to configure log output destination, which can be a plain file, syslog, or a function pointer to a custom logging function. The function pointer enables us to save the log to any possible storage we prefer, e.g., across network.
There is a tiny bug which prevents us using the function pointer mechanism on windows platform if we compile the osip as dynamic library. The author forgot export osip_trace_initialize_func in osipparser2.def file. So our application will end in unresolved external symbol error if we use this function. To get around this, I added the line at the very end of osipparser2.def:

osip_trace_initialize_func @416

To use osip logging, we need to:

Compile osip with ENABLE_TRACE macro defined
Define ENABLE_TRACE in our application
Initialize osip logging module
Write log message with: OSIP_TRACE (osip_trace(__FILE__, __LINE__, OSIP_INFO1, NULL, "log message"));

The wonderful thing is we can easily turn off logging by either undefine ENABLE_TRACE macro, or eliminate the line that initialize osip logging module. We can also trun logging message with specific logging level on and off. Very convenient.

An example is available here:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/protocol/osip_logging/osip_log.cpp

sip elements lifecycle

2010-05-17T22:02:00.001+08:00

In sip protocol, the difficult thing is the liecycle of sip elements, including dialog, transaction and message. Though defined as different layers in sip, their lifecycle usually overlaps. Message is the layer at the bottom. Transaction is the layer above message, it's comprised of a sip request message (sent by UAC) and all subsequent response messages (sent by UAS) to the request. A transaction is identified by Branch parameter in Via header. On top of the transaction layer is the dialog layer, which defines a peer-to-peer relationship between participants. Its identifier is the combination of the To tag, From tag and Call-ID.
The lifecycle of elements varies depending on the actual messages exchanged. As an example, Alice called Bob, and Bob accepted the call. During the session initialization process, they exchanged a bunch of sip messages. The lifecycle of transaction and dialog elements are shown below:
(Yellow block and blue block represent the lifecyle of a dialog, indicate Early sate and Confirmed state respectively. Green block represents the lifecycle of a transaction.)

The lifecycle of elements are different if Bob rejected Alice's call. In this case, the ack message belongs to the transaction that created by the invite message, not having its own transaction anymore.

The previous example suffices to show the complexity of sip elements' lifecycle. It's import to understand the lifecycle of elements to implement a mature sip protocol stack.

The essential idea of layered design is to hide lower layer's implementation detail. In sip protocol, though it's designed as layered protocol, the lower layer isn't completely transparent.
Suppose our application runs on top of a sip protocol stack. In an ideal world, our application should only relies on the dialog layer to run. But because dialog's lifecycle doesn't fully cover the lifecycle of transactions in lower layer, our application still has to rely on transaction layer or even message layer. The dependencies on different layers of sip protocol stack make things a lot complicated.
In order to simplify things, many sip protocol stack implementations abstract another higher level layer, "call", which is not defined in sip protocol specification. The existance of this layer successfully decouples our application from those different underlying layers.

capture network traffic on windows ce

2010-05-14T19:11:00.003+08:00

When developing network applications, it's always necessary to capture network traffic. Windows ce has built-in sniffer tool, netlog for this purpose. It captures network traffics to a file that can be examined with wireshark or network monitor.
To enable it, we need to select NDIS Packet Capturing DLL and NDIS User-mode I/O Protocol Driver in visual studio, as shown below.

Then, we can capture network traffic with following commands.

1. set capture file lacation:

netlogctl file "\Storage Card\net"

2. start capture

netlogctl start

3. perform network activities
4. stop capture

netlogctl stop

5. copy \Storage Card\net.cap[i].cap to computer and open with wireshark

NetLogctl usage:
netlogctl start - start the loggging.
netlogctl load - start the loggging.
netlogctl stop - stops the loggging.
netlogctl unload - causes networking to unload the netlog component. (may destabilize system)
netlogctl pkt_size XX - sets maximum packet size captured.
netlogctl cap_size XX - sets maximum size of half capture file.
netlogctl file XXX - sets the name of the file to log.
netlogctl usb XXX - 1 => log usb , 0 => stop logging usb.
netlogctl state - print state.
netlogctl trace - print trace message state for all modules.
netlogctl trace <module> - print trace message state for specified module.
netlogctl trace <module> <filter> - set trace message state for specified module.

use googletest on windows ce

2010-05-10T21:48:00.002+08:00

I've been trying to use googletest on windows ce platform to do unit testing. But gtest doesn't provide a windows ce project file, so I had to modify the project myself. Here is how to do so:

1. Add a new platform
I added a new windows ce based platform (Windows Mobile 5.0 Pocket PC SDK (ARMV4I), for example) in the configuration manager of the gtest project.

2. Add below preprocessor definitions
In order to compile gtest library for windows ce, I used below preprocessor definitions:
"NDEBUG;_WIN32_WCE=$(CEVER);UNDER_CE;$(PLATFORMDEFINES);WINCE;_CONSOLE;$(ARCHFAM);$(_ARCHFAM_);_UNICODE;UNICODE"

Not all of them are mandatory, but missing the bold ones may cause gtest fail to compile.

3. Create a windows ce console project
The sample project is available at:
http://code.google.com/p/rxwen-blog-stuff/source/browse/#svn/trunk/wince/ce_gtest_proj
This project expects to find gtest header file (gtest\gtest.h) and static library (gtestd.lib) in googletest folder in parent directory.

4. Run the application on emulator/device and verify output
Finally, I run the unit testing application on a windows ce device, and get below outputs in visual studio and serial port output respectively. The output shows that the test case passed successfully.

visual studio output window

device serial port output

It's not always necessary to run unit testing application on windows ce device. If we write our application with care, it's possible that the application can compile and run on both win32 and windows ce platform. Then we can do unit testing on a normal pc, which will be easier and faster.
But I still would like to run the unit testing on windows ce if our product is supposed to run on it. Any subtle differences between win32 and win ce may cause the unit testing succeed on one platform but fail on the other. It's wise to do unit testing on the platform that the application will actually run.

describe intention directly before ask a question

2010-04-26T20:29:00.001+08:00

Before asking a question, it's a good habit to describe your intention clearly. Below is a real story happened between me and a coworker.

CW: hey, do you know how to do B on windows?
ME: o, yes. You can:
1. Blah blah
2. Blah blah
3. Blah blah
But why you want to do this?
CW: hmmm, because I want to do A.
ME: Do A? Why ask B? They're not related.
CW: Why? According to concept C, A is controlled by B.
ME: No, you misunderstood concept C. It's blah blah
CW: O, i see.

If he asked how to do A at the beginning, we both can save a lot of time.
When we need to ask a question, it's a sign that we don't understand the stuff very well. Then we'd better describe our intention directly. If we ask a different topic by our own deduction, which may be a misunderstanding, we may be on the wrong track.

streaming audio on android

2010-04-25T20:12:00.011+08:00

Streaming media refers to the capability of playing media data while the data is being transferred from server. The user doesn't need to wait until full media content has been downloaded to start playing. In media streaming, media content is split into small chunks as the transport unit. After the user's player has received sufficient chunks, it starts playing.
From the developer's perspective, media streaming is comprised of two tasks, transfer data and render data. Application developers usually concentrate more on transfer data than render data, because codec and media renderer are often available already.
On android, streaming audio is somewhat easier than video for android provides a more friendly api to render audio data in small chunks. No matter what is our transfer mechanism, rtp, raw udp or raw file reading, we need to feed chunks we received to renderer. The AudioTrack.write function enables us doing so.
AudioTrack object runs in two modes, static or stream. In static mode, we write the whole audio file to audio hardware. In stream mode, audio data are written in small chunks. The static mode is more efficient because it doesn't have the overhead of copying data from java layer to native layer, but it's not suitable if the audio file is too big to fit it memory. It's important to notice that we call play at different time in two modes. In static mode, we must call write first, then call play. Otherwise, the AudioTrack raises an exception complains that AudioTrack object isn't properly initialized. In stream mode, they are called in reverse order. Under the hood, static and stream mode determine the memory model. In static mode, audio data are passed to renderer via shared memory. Thus static mode is more efficient.

From birds eye view, the architecture of an typical audio streaming application is:

Our application receives data from network. Then the data will be passed to a java layer AudioTrack object which internally calls through jni to native AudioTrack object. The native AudioTrack object in our application is a proxy that refers to the implementation AudioTrack object resides in audioflinger process, through binder ipc mechanism. The audiofinger process will interact with audio hardware.
Since our application and audioflinger are separate processes, so after our application has written data to audioflinger, the playback will not stop even if our application exits.

AudioTrack only supports PCM (a.k.a G.711) audio format. In other words, we can't stream mp3 audio directly. We have to deal with decoding ourselves, and feed decoded data to AudioTrack.

Sample
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/android/streaming_audio/
For demonstration purpose, this sample chooses a very simple transfer mechanism. It reads data from a wav file on disk in chunks, but we can consider it as if the data were delivered from a media server on network. The idea is similar.

Update: Check this post for a more concrete example.

why I prefer wireshark to network monitor

2010-04-24T22:52:00.004+08:00

Personally, I prefer wireshark to network monitor for:

Wireshark runs on many platforms including windows, linux, mac os x, etc. I need to work both on linux and windows, and I'd like to keep my toolbox as compact as possible.
Wireshark uses a widely adopted syntax for capture filters and disply filters which dare I call them de facto. The same syntax is used in windump and tcpdump. I don't need to remember additional syntax even work in a GUI-less environment.
Filters in wireshark seems to be more powerful. For example, the filter "tcp.flags.syn==1" enables me to view tcp SYN messages only. Based on my limited experience with network monitor, I'm not aware if it can filter at this granularity.

But network monitor has the advantage of being able to categorize network messages by processes. As shown in the image below:

It's a very convenient feature that helps me easily find out messages I'm interested in. Especially when I need to debug a process whose port numbers are picked at random or dynamically.

standalone windbg v6.12.0002.633

2010-04-23T20:23:00.007+08:00

I read from Tomas's post that newer version windbg can't be downloaded from microsoft directly anymore. To get newer windbg, we have to download the huge 620 mb WDK iso and extract windbg installer from it manually. The newest windbg standalone installer is version 6.11.1.404, released on March 27, 2009.
I don't know if microsoft will listen to our customer's voice and release a standalone windbg. Before they will, for the convenience for developers like me, here is extracted windbg package:

windbg 6.12.0002.633 x86   http://rxwen-blog-stuff.googlecode.com/files/windbg_6.12.0002.633_x86.zip
md5sum:   abdad1a805f7d89d461b4569b216001d
sha1sum: 3715d726363524643a6df561bf9d27e7acb49307

windbg_6.12.0002.633_64_installer    http://rxwen-blog-stuff.googlecode.com/files/windbg_6.12.0002.633_64_installer.zip
md5sum: 62fc3d313081f96fea3f69c4d06700a1
sha1sum: d79e6f40c08a95d5653c0eb0cc7d64c8bea8e391

A noticable change of this version is: ADPlus V7.0 is a total rewrite of ADPlus. ADPlus is now written in managed code which will allow us to add new features much easier. The old version is renamed to adplus_old.vbs. This page lists more changes of the new version.

Hope it helps.

Use google.com instead of google.com.hk

2010-04-21T19:18:00.003+08:00

After google moved their service from china mainland to hongkong, I can't access google.com or google.cn from mainland anymore. I always get redirected to google.com.hk. Based off my experience with google.com.hk, it shows more noise information than google.com and google.cn. Because in most cases, results in transitional chinese aren't what I'm looking for.

To force the browser using google.com, we can visit the url http://www.google.com/ncr. After it has been visited once, all subsequent requests for google.com won't be redirected to google.com.hk anymore. Hooray!

Override CheckMediaType with care

2010-04-18T21:24:00.004+08:00

A problem I encountered while developing my source filter's output pin is that inside FillBuffer method, the media type and size of the media sample is not exactly the same as the one I proposed in GetMediaType method. The strange thing is my pin has successfully negotiated with downstream renderer filter (its actual type is Video Mixing Renderer-9 filter), and its input pin has agreed to use the media type my filter proposed. So why the actual media type being used changes?

The answer lies in this document, handling format changes from the video renderer:

Video Mixing Renderer Filter
The Video Mixing Renderer filter (VMR-7 and VMR-9) will connect with any format that is supported by the graphics hardware on the system. The VMR-7 always uses DirectDraw for rendering, and allocates the underlying DirectDraw surfaces when the upstream filter connects. The VMR-9 always uses Direct3D for rendering, and allocates the underlying Direct3D surfaces when the upstream filter connects.
The graphics hardware may require a larger surface stride than the image width. In that case, the VMR requests a new format by calling QueryAccept. It reports the surface stride in the biWidth member of the BITMAPINFOHEADER in the video format. If the upstream filter does not return S_OK from QueryAccept, the VMR rejects the format and tries to connect using the next format advertised by the upstream filter. The VMR attaches the media type with the new format to the first media sample. After the first sample, the format remains constant; the VMR will not switch formats while the graph is running.

During the connecting phase, after both filters' pins have agreed on a media type, they perform allocator negotiation. And the downstream pin proposed a larger biWidth during allocator negotiation. As a result to the new proposal, our pin's QueryAccept method is called. If we don't override it, the default implementation of grandpa class CBasePin comes into play. CBasePin::QueryAccept internally calls CheckMediaType method to see if the newly proposed media type can be accepted. Because our pin's CheckMediaType method's original implementation is too sloppy without examining all fields of the new media type, so we ended in the situation I described at the beginning of the post.

So, the best practice for creating a source filter is we need to handle CheckMediaType carefully. Or we can take the alternative way of overriding the QueryAccept method to handle media type change explicitly.

References:
How to Write a Source Filter for DirectShow
Core Media Technology in Windows XP Empowers You to Create Custom Audio/Video Processing Components

Thoughts on directshow

2010-04-11T22:06:00.002+08:00

In this post, I'll summarize some features that make directshow stand out, from a developer's point of view.

The architecture of directshow is:

The core of directshow framework is the box in the center.

1. separation of concerns
Directshow divides a complex media rendering task into a bunch of smaller tasks, organized as different filters. Each filter has its own concentration, e.g., grabbing data from source media file, decoding data, rendering the data on display. It's more natural and easier for our brain to resolve complex problems in smaller steps, one by one. Another benefit of this breakdown structure is we can perform unit test on smaller component more easily.

2. mature abstraction layer
Directshow provides a mature abstraction layer on top of sub-tasks' concrete implementations (Adapter pattern). The existence of the abstraction layer makes our project easier to manage. The cost for dealing with changes can be minimized. For example, we can have one guy tries to implement a hardware based decoder filter. And before his filter is available, other guys in charge of other parts can use a software based decoder filter instead. After the hardware based filter is done, it's hopeful to replace the software based filter without requiring changes on other parts because interfaces of both filters are the same.

3. built-in multimedia functions
Besides being a sophisticated core framework, directshow also contains a lot of commonly used multimedia features like common media type decoders, some splitters, and multi-stream synchronizer. With these features built-in, we developers' life will be a lot easier.

References
MSDN: Directshow System Overview
http://en.wikipedia.org/wiki/DirectShow

directshow debugging tips

2010-04-03T14:19:00.006+08:00

1. View graph

When we render a media file, directshow uses intelligent connect to build a working graph for us. It may add some filters implicitly if necessary. From my perspective, it all happens transparently. It's user friendly and powerful. But while debugging, we need to know exactly how is the graph constructed and connected, at runtime. Directshow provided a utility method AddGraphToRot in %WINSDK%\Samples\multimedia\directshow\common\dshowutil.h. We can use it to register our graph to running object table, and then view the graph in graphedit. After the graph has been registered, we select File - Connect to Remote Graph in graphedit to bring up remote filter graph list. Then select the registered graph to view.

2. Keep log

IGraphBuilder exposes a SetLogFile method that can be used to specify a log file. Once set, all of the graph's activities will be saved to the log file, including how filter's are connected, how the graph attempted to connect pins. These information are valuable for debugging filters.

pGraph->SetLogFile((DWORD_PTR)CreateFile(TEXT("C:\\graph_builder.log"), GENERIC_WRITE, 0, NULL, CREATE_NEW, FILE_ATTRIBUTE_NORMAL, NULL));

3. Dump graph

In the log file generated by graph, components (filter and pin) are identified with their address in memory. The friendly name of the component isn't shown which make the log file harder to understand by human. Here is a small utility function that dumps all filters and their pins with corresponding memory address and name, in the format shown below.

http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/multimedia/directshow/graphdump.cpp

4. open source graphedit replacement
http://blog.monogram.sk/janos/tools/monogram-graphstudio/

Total Commander, what a weapon!

2010-03-29T22:31:00.007+08:00

I've used freecommander for years. It greatly improves my efficiency. Unfortunately, for some unkonwn reasons, my freecommander configuration file get corrupted after my machine power down unexpectedly several days before. Rather than making these configurations from scrarch again, I decided to give Total Commander a shot.

After I tried TC, I found it's far more powerful. TC is fully customizable, I can define any shortcut key combinations for TC internal commands or external commands defined by me. In FC, only Ctrl+[Number] is allowed to be set as shortcut key for external commands.

The most promising feature for TC is its plugin system. There are so many wonderful plugins that make TC so powerful. With packer plugin, I don't need a stand alone zip/tar/bzip2 applicaitons. With some creative filesystem plugins, task manager, regedit, dependency walker are not necessary any more. By using plugins, I can perform a lot of totally different tasks in a consistent manner, just manipulate some (fake) files in TC. This is very similar to abstraction in linux, where everything can be examined and manipulated like normal files. Abstract thinking should always be a popular idea among programmers, so I'm totally fascinated by TC.

Suggestions for Total Commander

1. Add global shortcut key. It's more convient to active total commander application with global shortcut key than pressing ctrl+tab sereval times. Though this can be achieved with tools like autohotkey, it's better if TC natively support global shortcut.

2. Improvement on command line. In windows console and linux shell, we can use tab key to complete file/command name. It's fabulous if TC also support this feature.

change command prompt font

2010-03-24T08:45:00.012+08:00

Having used consolas font for a period, I felt very comfortable with it. I've used it in putty, vim, visual studio. And I tried to use it in windows console (cmd.exe) by following scott's post, Using Consolas as the Windows Console Font. But consolas font didn't show in console's available font list. It seemed to have to do with my console code page setting, which is 936 chinese gbk. Consolas was shown after I changed the console's code page to 850 with chcp command. Thing was not perfect, I could not use chinese input method under this code page in console, and chinese characters are not displayed correctly.
As a matter of fact, there is another way to set consolas font for console through registry, which doesn't require us to change code page. Our preferences for default console are saved in HKCU\Console, including console's width, height and font. Subitems of this key save preperences for console with specified title. So we can modify the FaceName item to force a font get applied. As shown below.

Windows Registry Editor Version 5.00

[HKEY_CURRENT_USER\Console]
"FaceName"="Consolas"

[HKEY_CURRENT_USER\Console\%SystemRoot%_system32_cmd.exe]
"FaceName"="Consolas"

Here is a snapshot of the font comparison:

BTW, consolas font is designed specifically for ClearType. It looks extremely poor if ClearType is not enabled. We can use ClearType Tuner PowerToy to fine tune ClearType under windows xp.

References:
Necessary criteria for fonts to be available in a command window
Give Your Eyes a Treat

getting start with osip

2010-03-22T21:42:00.012+08:00

As described in rfc3261, sip is a layered protocol. Its layers are shown in the image below.

Unlike other sophisicated sip libiraies, exosip, pjsip, mjsip, which implement all layers of sip protocol, oSip library doesn't implement transport layer. oSip claims it doesn't provide high level api for controlling SIP session, it only provides api for sip message parsing, sdp message parsing and transaction handling. The api contains implementation for syntax, transaction and transaction unit layer.
So, in order to use oSip in our own application, we need to implement transport layer, and hook the transport layer with the oSip library.

Core structures of oSip
oSip library has four core structures, osip_t, osip_transaction_t, osip_event_t, osip_message_t. osip_t is the context of the sip library runs in. osip_transaction_t defines transaction which composes of a request message and all subsequent response messages related to the request. osip_event_t defines event inside transaction pending on handling. osip_message_t is the mapping from sip message syntax to c structure.

osip_t has four lists of transactions, each corresponds to a kind of transaction. For instance, if our sip application makes a call to another sip application, our application runs as uac (User Agent Client). A transaction is created and added to the osip_ict_transactions ( ict is short for invite client transaction) list. In the application being called, a transaction is also created and added to the osip_ist_transactions (ist is short for invite server transaction).
There are three members, msg_callbacks, kill_callbacks and cb_send_message in osip_t. They store callbacks to be called while handling events of transaction. They are designed as internal members. The proper way to add callbacks is using following apis: osip_set_cb_send_message, osip_set_message_callback and osip_set_kill_transaction_callback.

osip_transaction_t contains many members. Among them, the most important ones are:

transactionid, which uniquely identifis a transaction
state, which shows current state of the transaction
transactionff, a fifo containing all events belonging to this transaction

osip_event_t is used to represent an event pending on processing. It doesn't contain much information. It only has the transactionid of the owning transaction, the type of the event and a pointer to the sip_message_t correlate with the event. An event is usually constructed accompany with a sip_message_t instance. For example, upon receiving a incoming request, we can use osip_parse function to parse the received string to a osip_message_t instance, meanwhile, a osip_event_t instance will be created and returned. osip_event_t instance is only useful after it has been added to a transaction's event fifo. This can be done with osip_transaction_add_event or osip_find_transaction_and_add_event functions.

After events have been added to fifo, we need to call osip_xxx_execute functions to actually handle them. There are four osip_xxx_execute functions, each will handle all events belong to a transaction category. For example, osip_ist_execute function will iterate through all IST transactions in osip_ist_transactions list, loop through all events in each transaction's transactionff, call corresponding callback functions depending on the type of the event.

How to use oSip
To use oSip library, we usually follow below steps:

Initialize oSip and setup callback functions
Implement transport layer. In most cases, we create a socket based transport layer.
Create/add events by parsing incoming messages
Call osip_xxx_execute function to process all events

Here is a basic sample:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/protocol/basic_osip_sample/basic_osip_sample.cpp
This sample is a UAS(callee) for windows, and just show the basic steps of using oSip without error handling.

Something useful

It's strongly recommended not to run time consuming or indefinite ending tasks inside callback functions, otherwise, the osip main procedure will be blocked until the callback finishes.
oSip has provided a wrapper layer above native system apis to make it portable. In order to use its multi-thread feature (which is almost always necessary), we need to define OSIP_MT macro in our application.
In most cases, we don't need to concern about freeing of transaction & message instances. Their life time are managed by the osip runtime, through state machine.

native programming with android building system

2010-02-01T20:58:00.006+08:00

In the previous post, native programming on android, I showed how to use code sourcery toolchain to do native programming on android. But in that way, we must link c library statically into our application, which is not desirable. So, in this post, I'll show how to do native programming with the android built-in building system.

For demonstration purpose, I'll create a logtest application. The application relies on cutils lib and writes some log information that can be examined through "adb logcat" command.

1. Initialize android source tree
In later steps, I'll use $ANDROID_SRC to refer to the root of the android source tree.

2. Create a directory for your application within the source tree
One advantage of android building system is it doesn't require your application to follow a specific organization structure. Your application can be placed in any directory. I created $ANDROID_SRC/logtest folder for the application.

3. Create an Android.mk file for the application in the directory
Android.mk is a reserved file name to indicate a module. This file describes how to build the module. By defining LOCAL_MODULE variable, we can assign a name to our application.
Depending on the type of the module, we include $(BUILD_EXECUTABLE), $(BUILD_DYNAMIC_LIBRARY) and $(BUILD_STATIC_LIBRARY) respectively at the end of the Android.mk.

4. Specify source files for the application
Through LOCAL_SRC_FILES variable, we specifies which source files are necessary to compile the module. Paths to source files are represented relative to the location of the Android.mk file.

5. Specify dependencies
Through LOCAL_SHARED_LIBRARIES variable, we can specify other libraries that our module depends on.

6. Build application
Go to root of Android source tree, and type make $(LOCAL_MODULE) to build the application which will be placed at $ANDROID_SRC/out/target/product/generic/system/bin/logtest.

Tips:

1. show commands
By default, android building system disables command echoing. It's hard to find out and correct dependency relationships without seeing the actual command. To change this behavior, we can append the showcommands pseudo target.
For example:
make logtest showcommands

2. quick build
Android building system need to find and parse Android.mk files within the source tree, and analysis dependencies. It's a time consuming task. In fact, there is a quicker way to build a module.
cd $ANDROID_SRC
source build/envsetup.sh
mmm {path_to_module_to_be_built} showcommands

3. build host module
Android building system can also used to generate modules for the host machine. An example is the adb application. To build host module, we can use:
include $(BUILD_HOST_EXECUTABLE) # $(BUILD_HOST_STATIC_LIBRARY)

4. disable prelink
We may encounter the error below while compiling a shared library:
build/tools/apriori/prelinkmap.c(168): library '***.so' not in prelink map
This is because android tries to prelink shared library with apriori tool by default, but our library isn't presented in the build/core/prelink-linux-arm.map. Thus the error. To get rid of it, we can add the line below in Android.mk to disable prelink.
LOCAL_PRELINK_MODULE := false

The demo can be found at:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/android/logtest/

Reference:
Android Building System
Android build system

windbg sos.dll version issue

2010-01-20T18:50:00.005+08:00

I debugged a .net 1.1 based windows application which exits silently upon start up. The problem itself is trivial and not worth mentioning. What I want to say is there is a subtle point about sos.dll version. When I was debugging, I started the application under windbg. Then issue ".loadby sos mscorwks" command to load sos.dll extension corresponds to the running .net framework. And I entered !DumpAllExceptions command which should exist in sos.dll for .net framework 1.1, but ended in not finding this command: No export DumpAllExceptions found Finally, I had to use "!DumpHeap -type Exception" to find out all exceptions. Having done some investigation, I found there are two sos.dll files for .net 1.1. One in .net framework installation folder, and one in windbg installation folder. The latter one is a full featured extension and support DumpAllExceptions command. I tried debugging the application again with sos.dll comes with windbg by issusing: ".load windbg_installation_folder/clr10/sos.dll". This time, DumpAllExceptions was back to life and worked like a charm. BTW, an alternative way to do !DumpAllExceptions is to take advantage of .foreach command. .foreach(exception {!DumpHeap -type Exception -short}) {!do exception; .echo print exception done !!! ***************} For convenience, below are commands supported by different version sos.dll. C:\WINDOWS\Microsoft.NET\Framework\v1.1.4322\SOS.dll 0:000> !help SOS : Help COMState \| List COM state for each thread ClrStack \| Provides true managed stack trace, source and line numbers. Additional parameters: -p[arams] -l[ocals] -r[egs] -a[ll]. DumpClass \| Dump EEClass info DumpDomain [] \| List assemblies and modules in a domain DumpHeap [-stat] [-min 100] [-max 2000] [-mt 0x3000000] [-type ] [-fix] [start [end]] \| Dump GC heap contents DumpMD \| Dump MethodDesc info DumpMT [-MD] \| Dump MethodTable info DumpModule \| Dump EE Module info DumpObj \| Dump an object on GC heap DumpStack [-EE] [-smart] [top stack [bottom stack] \| -EE only shows managed stack items. DumpStackObjects [top stack [bottom stack] DumpVC \| Dump a value class object EEHeap [-gc] [-win32] [-loader] \| List GC/Loader heap info EEStack [-short] [-EE] \| List all stacks EE knows EEVersion \| List mscoree.dll version FinalizeQueue [-detail] \| Work queue for finalize thread GCInfo [] [IP] \| Dump GC encoding info for a managed method GCRoot \| Find roots on stack/handle for object IP2MD \| Find MethodDesc from IP Name2EE \| Find memory address of EE data given a class/method name ObjSize [] \| Find number of bytes that a root or all roots keep alive on GC heap. ProcInfo [-env] [-time] [-mem] \| Display the process info RWLock [-all] \| List info for a Read/Write lock SyncBlk [-all\|#] \| List syncblock ThreadPool \| Display CLR threadpool state Threads \| List managed threads Token2EE \| Find memory address of EE data for metadata token u [] [IP] \| Unassembly a managed code {windbg installation folder}\clr10\sos.dll 0:000> !help Did you know that a lot of exceptions (!dumpallexceptions) can cause memory problems. To see more tips, run !tip. ------------------------------------------------------------------------------- SOS is a debugger extension DLL designed to aid in the debugging of managed programs. Functions are listed by category, then roughly in order of importance. Shortcut names for popular functions are listed in parenthesis. Type "!help " for detailed info on that function. Object Inspection Examining code and stacks ----------------------------- ----------------------------- DumpObj (do) Threads (t) DumpAllExceptions (dae) CLRStack DumpStackObjects (dso) IP2MD DumpHeap (dh) U DumpVC DumpStack GCRoot EEStack ObjSize GCInfo FinalizeQueue COMState DumpDynamicAssemblies (dda) X DumpField (df) SearchStack TraverseHeap (th) GCRef Examining CLR data structures Diagnostic Utilities ----------------------------- ----------------------------- DumpDomain VerifyHeap (vh) EEHeap DumpLog Name2EE FindAppDomain SyncBlk SaveModule DumpASPNETCache (dac) SaveAllModules (sam) DumpMT GCHandles DumpClass GCHandleLeaks DumpMD FindDebugTrue Token2EE FindDebugModules EEVersion Bp DumpSig ProcInfo DumpModule StopOnException (soe) ThreadPool (tp) TD ConvertTicksToDate (ctd) Analysis ConvertVTDateToDate (cvtdd) Bl RWLock CheckCurrentException (cce) DumpConfig CurrentExceptionName (cen) DumpHttpRuntime ExceptionBp DumpSessionStateConfig FindTable DumpBuckets LoadCache DumpHistoryTable SaveCache DumpRequestTable ASPXPages DumpCollection (dc) DumpGCNotInProgress DumpDataTables CLRUsage GetWorkItems DumpLargeObjectSegments (dl) DumpModule DumpAssembly Other DumpMethodSig ----------------------------- DumpRuntimeTypes FAQ PrintIPAddress DumpHttpContext DumpXmlDocument (dxd) C:\WINDOWS\Microsoft.NET\Framework\v2.0.50727\SOS.dll 0:000> !help ------------------------------------------------------------------------------- SOS is a debugger extension DLL designed to aid in the debugging of managed programs. Functions are listed by category, then roughly in order of importance. Shortcut names for popular functions are listed in parenthesis. Type "!help " for detailed info on that function. Object Inspection Examining code and stacks ----------------------------- ----------------------------- DumpObj (do) Threads DumpArray (da) CLRStack DumpStackObjects (dso) IP2MD DumpHeap U DumpVC DumpStack GCRoot EEStack ObjSize GCInfo FinalizeQueue EHInfo PrintException (pe) COMState TraverseHeap BPMD Examining CLR data structures Diagnostic Utilities ----------------------------- ----------------------------- DumpDomain VerifyHeap EEHeap DumpLog Name2EE FindAppDomain SyncBlk SaveModule DumpMT GCHandles DumpClass GCHandleLeaks DumpMD VMMap Token2EE VMStat EEVersion ProcInfo DumpModule StopOnException (soe) ThreadPool MinidumpMode DumpAssembly DumpMethodSig Other DumpRuntimeTypes ----------------------------- DumpSig FAQ RCWCleanupList DumpIL

Ex 15.4-5 of introduction to algorithms

2010-01-20T12:01:00.008+08:00

Question:
Give an O(n squared)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers.

Answer:
A brute-force approach is enumerate all subsequences of the n numbers and find out a monotonically increasing one with the longest length. This algorithm has a poor exponential running time.
This problem exhibit optimal substructure and overlapping subproblems properties, and is suited for dynamic programming.

Let A denotes the array of n numbers, A[i] is the ith number of the array.
Let P{i,j} denotes problem of finding the longest monotonically increasing subsequence. So the original problem is P{1,n}.
Let S(i,j) denotes the length of longest subsequence of P{i,j}.
Let M(i,j) denotes the largest number in the longest subsequence of P{i,j}. Note for P{i,j}, there may exist several subsequence has the same longest length, M(i,j) should be the smallest one of them.

For P{1,j}, if A[j] is larger than M(1,j-1), then S(1,j) equals S(1,j-1) plus 1. Otherwise, it equals S(1,j-1).
So, we have:
S(1,j) = S(1,j-1) if A[j] <> M[1,j-1]

The complicated thing in this procedure is how to maintain M's value correctly. The idea is if A[j] is larger than M(1,j-1), M(1,j) should be A[j]. If A[j] is smaller than M(1,j-1), M(1,j) should either be M(1,j-1) or A[j] if A[j] is larger than M(1,x) where S(1,x) is less than S(1,j-1).

This equation yields a n squared running time algorithm.

Correction:

Having done some tests, the preceding algorithm failed for this case: "8 9 1 2 3 4".

The recursion can be performed another way. Let S(i) denotes the length of the longest subsequence that ended with item A(i). So, the relationship between a problem and its subproblem can be expressed as:

S(i) = max{ S(k)+1 } (k is between 0 and i -1) that all k satisfies A[k] is less than A[i]

And the final result is the largest one of array S.

Source code for this solution is here:

http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/algorithm/i2a_ex_15.4-5/ex15_4_5.cpp

google against GFW

2010-01-13T09:52:00.003+08:00

I keep using blogger.com because I was hoping it will not be banned by the GFW some day.
But, according to this, a new approach to china, it seems it's becoming less likely blogger.com will be unbanned. And things may become worse in china, more and more google services may be affected.

To some extent, I'm glad to see google can hold its motto "Don't be evil" firmly and stand out to fight against such extreme information blocking. But, it's hard to show full support to this action considering its consequence for google & chinese people. Just wait and see how chinese gov will response.

Update on March 23, 2010:
Finally, it happens: A new approach to China: an update. Applaud for you, google!

fix "no module named readline" on windows

2010-01-10T16:47:00.002+08:00

I tried to download android source code by following instructions in this article: Using Repo and Git. Because I'm working with cygwin on windows, the readline module isn't available. The repo script failed to run and compained "no module named readline".
Luckily, the Ipython project provides an alternative readline module named pyreadline that can be used on windows and mac osx.
To install it:
1. Download pyreadline for windows.
2. unzip the setup file.
3. Copy PURELIB/readline.py and PURELIB/pyreadline to $(python_installation_folder)/Lib

After it's done, the repo script can run successfully.

Update: In order not to get the python installation folder polluted, we can create a directory for all manually installed python modules. And set PYTHONPATH environment variable to this directory so that modules installed here can be loaded.

remove visual sourcesafe binding

2010-01-09T11:00:00.001+08:00

I need to change a visual stuio 2003 project's source control system from visual sourcesafe to subversion. In order to commit clean source files to svn, I first need to completely remove vss binding from the project.
There are a lot of articles about how to do this, I was following this one: Removing a Solution from Sourcesafe. But the problem is the project is comprised of two solutions, each with a bunch of projects. It's tedious to manually edit them manually. So, I managed to do this with following commands. These commands are available in cygwin on windows.

1. remove vss files
find ./ -name "*scc" | xargs rm
Explaination: this command uses find to get all files whose name end in "scc", then pipes the list to xargs. xargs will format the list in acceptable format and invoke rm to delete them.
There is a utility also named find on windows. In order to make sure the gnu find is invoked, I arranges the PATH environment variable so that the cygwin/bin folder precedes C:\windows\system32.

2. remove vss information in project files
find ./ -name "*.csproj" -exec sed -i '/Scc/ d'
Explaination: this command finds all files whose extension are ".csproj", and execute " sed -i '/Scc/ d' " on each file found. sed is a stream editor. This sed command searches for lines that have Scc and delete them. And the -i argument tells sed to edit file in place, so that the project gets updated.

3. restore file permission
find ./ -name "*.csproj" -exec chmod +rw {} ;
Explanation: after sed modifies a file, I lose all permission on that file. So I need to restore file permission with chmod. There is also a windows command line utility cacls can do this. And cacls can be a better choice here since microsoft internal tool may set file permission more properly than chmod.

android property system

2010-01-07T22:19:00.011+08:00

Property system is an important feature on android. It runs as a service and manages system configurations and status. All these configurations and status are properties. A property is a key/value pair, both of which are of string type.
From the sense of function, it's very similar to windows registry. Many android applications and libraries directly or indirectly relies on this feature to determine their runtime behavior. For example, adbd process queries property service to check if it's running in emulator. Another example is the java.io.File.pathSeparator returns the value stored in property service.

How property system works
The high level architecture of property system is shown as following.

In the figure, there are three processes, a group of persistent property files and a shared memory block. The shared memory block is the container of all property records. Only the property service process can write to the shared memory block. It'll load property records from persistent the save them in the shared memory.
The consumer process loads the shared memory in its own virtual space and access properties directly. The setter process also loads the shared memory in its virtual space, but it can't write to the memory directly. When the setter tries to add or update a property, it sends the property to property service via unix domain socket. The property service will write the property to shared memory on behalf of the setter process, as well as to the persistent file.

Property service runs inside init process. The init process first creates a shared memory region and stores a fd to the region. Then init process maps the region into its virtual space with mmap with MAP_SHARED flag, as a result, any updates to this area can be seen by all processes. This fd and region size are saved in a environment variable named "ANDROID_PROPERTY_WORKSPACE". Any other processes like consumer and setter will use this environment variable to get the fd and size, so that they can mmap this region into its own virtual space. The layout of the shared memory is shown below.

After that, init process will load properties from following files:
/default.prop
/system/build.prop
/system/default.prop
/data/local.prop

The next step is start property service. In this step, a unix domain socket server is created. This socket's pathname is "/dev/socket/property_service" which is well known to other client processes.
Finally, init process calls poll to wait for connect event on the socket.

On the consumer side, when it initializes libc(bionic/libc/bionic/libc_common.c __libc_init_common function). It will retrieve the fd and size from environment variable, and map the shared memory into its own space(bionic/libc/bionic/system_properties.c __system_properties_init function). After that, libcutils can read property just as normal memory for the consumer.

Currently, properties can't be removed. That's to say, once a property has been added, it can't be removed, neither can its key be changed.

How to get/set properties

There are three main means to get/set properies on android.

1. native code
When writing native applications, property_get and property_set APIs can be used to get/set properties. To use them, we need to include cutils/properties.h and link against libcutils.

2. java code
Android also provides System.getProperty and System.setProperty functions in java library, our java application can use them to get/set properties.

But it's important to note that although these java APIs are semantically equal to native version, java version store data in a totally different place. Actually, a hashtable is employed by dalvik VM to store properties. So, java properties are separated, it can't get or set native properties, and neither vice versa.

Update: Andrew mentioned that android.os.SystemProperties class can manipulate native properties, though it's intended for internal usage only. It calls through jni into native property library to get/set properties.

3. shell script
Android provides getprop and setprop command line tool to retrieve and update properties. They can be used in shell script. They are implemented on top of libcutils.

understanding the android media framework

2010-01-04T21:46:00.009+08:00

android media framework is built on top of a set of media libraries, including OpenCORE, vorbis and sonivox. So one of goal of android media framework is to provide a consistent interface for all services provided by underlying libraries and make them transparent to users.

The figure below shows the dependency relationships between libraries of the media framework.

In this figure, green components are media libraries, yellow components are android internal libraries, grey components are external libraries, and the light blue class is the java consumer of the media framework. Except for android.media.MediaPlayer class, all components are implemented in c or c++.

The core of the media framework is composed of libmedia, libmediaplayerservice and libmedia_jni. Their codes reside in frameworks/base/media folder.

libmedia defines the inheritance hierarchy and base interfaces. It’s the base library.

libmedia_jni is the shim between java application and native library. First, it implements the JNI specification so that it can be used by java application. Second, it implements the facade pattern for the convenience of caller.

libmediaplayerservice implements some of concrete players and the media service which will manage player instances.

The figure below shows the class hierarchy.

This is a simplified version of the class hierarchy. Only some core classes are included. Classes in blue are defined in libmedia, classes in green are defined in libmediaplayerservice, classes in light yellow are defined in binder, which implements the IPC on android. And classes in grey are defined in other libs.

Note the BpInterface and BnInterface are template classes. Any instantiation of them also inherit the template argument INTERFACE as well.

In the class hierarchy diagram, though listed as a separate module, binder is actually implemented inside libutils component whose source code locate at /frameworks/base/libs/utils folder.

An interesting thing to note is in android, the application that intends to show the media content and the player that actually renders the media content run in different process. The red line in the sequence diagram below shows the boundary of two processes.

The figure shows three most common operations, creating a new player, setting datasource and playing. The last MediaPlayerBase object is the interface that MediaPlayerService::Client object uses to refer to the concrete player instance. The concrete player can be VorbisPlayer, PVPlayer, or any other player, depending on the type of the media to be played.

When an application creates a android.media.MediaPlayer object, it’s actually holding a proxy which can be used to manipulate the concrete player resides in the mediaserver process. During the whole procedure, two process communicates with Binder IPC mechanism.

Having knowledge above, it’s not difficult to understand why MediaPlayer doesn’t provide an API to use memory stream as source. Because the memory manipulated by the stream is in the address space of the application, and it’s not directly accessible by the mediaserver process.

References:

Google I/O, Mastering the Android Media Framework

android media framework uml diagram

Ex 10.4-3 of introduction to algorithms

2009-12-24T17:04:00.001+08:00

Question:
Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.

Answer:
This isn't a difficult question. But the skill of turning a recursive algorithm to non-recursive algorithm is so important, it worths a blog post.

The data structure for tree node used in this post is defined as:
class TreeNode
{
public:
int value;
      TreeNode* left; // left child node
      TreeNode* right; // right child node
}

The simplest and cleanest algorithm for binary tree traversal is the recursion. As shown below:
void inOrderTraversalRecursive(TreeNode* node)
{
      if(Null == node)
          return;
      inOrderTraversalRecursive(node->left); // visit left sub-tree first
      visit(node); // visit current node
      inOrderTraversalRecursive(node->right); // visit right sub-tree
}

In this algorithm, each time we goes down a level to the calling stack, a new stack frame will be created for the new function call. Then the context changes to the new stack frame. And the node is kept on the previous stack frame. In current stack frame, node is the left or right child of last stack frame's node. With the help of stack, after a function call is finished, the context changes back to the previous stack frame and consequently gets back to the parent node. Because this stack is managed automatically be the compiler, this algorithm becomes so simple. But this stack isn't unlimited, if the tree's height is large enough, the stack may exhaust. In order to get over this limit, we can use a heap (whose limit is far larger.) based stack data structure and manage it ourselves.

This is done in a loop. Each iteration of the loop is regarded as a function call in recursive version. At proper point of the iteration, we must push/pop node from/to stack so that the context of the iteration can be maintained.
In recursive version, if node is not null, we need to save current node in stack (push) and change node to node->left. Otherwise, the function call returns right away, which means the node is restored (pop) to the value in last call stack frame. After the left sub-tree has been visited, we visit current node.
Then we save (push) current node again and change node to node->right to visit right sub-tree. After it's done, we need to restore (pop) node. But as we can see in the recursive version, the node isn't used at all after the right sub-tree has been visited. That's to say, it's not necessary to save context before we visit right sub-tree any more. This procedure can be omitted in this case.
The last thing to determine is the termination condition. In what situation can we terminate the loop? First, it's clear that the stack should be empty when the loop terminates. But this isn't enough, the node should be null as well to terminate the loop.

void inOrderTraversalStack(TreeNode* root)
{
      typedef std::stack<TreeNode*> TreeStack;
      TreeStack stack;
      TreeNode *node = root;
      while(NULL != node || !stack.empty())
      {
          if(NULL != node)
          {
          stack.push(node);
              node = node->left;
          }
          else
          {
          node = stack.top();
              stack.pop();
          visit(node);
              node = node->right;
          }
      }
}

Ex 9.3-8 of Introduction to algorithms

2009-12-17T08:49:00.003+08:00

Question:
Let X[1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O(lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.

Answer:
Without losing generality, suppose the median z is the smaller median (there are two medians since total number is even), it's the ith element in array X. In array X, there are i-1 numbers smaller than z and n-i numbers larger than the z. Because z is the median of all 2n elements, there should be n-i numbers in Y smaller than z and i numbers larger than z.
In order to find out z, we first compare the median of X and Y. Say they are mx and my respectively. If mx is smaller than my, we compare mx and the largest element in Y that is smaller than my, say it's my2. If mx is larger than my2, then mx is z, the median of all 2n elements. Otherwise, z must be in higher half of X or lower half of Y. So, we can perform preceding logic recursively.
This algorithm works just like binary search tree whose running time is O(lg n).

The code for the algorithm is available at:
http://code.google.com/p/rxwen-blog-stuff/source/browse/trunk/algorithm/i2a_ex_9.3-8/ex9_3_8.cpp

use memcmp to compare objects?

2009-12-11T09:13:00.006+08:00

I came across a question regarding c++, is it more efficient to use memcmp to determine equality of two objects of the same type.
This is not a question regarding efficiency at all, it's about correctness. Using memcmp to compare two objects MAY be correct sometimes, but it really depends on several factors:

Class alignment
Compiler implementation
Compiler configuration

You may get different results when work with different types, with different compilers. Even worse, you may get different results between two invocations in the same environment. Though it seems to be efficient, it's not reliable.

We know many compiler will align a class's members to word size for better performance, because it's harder to read or write memories at arbitrary location. So possibly, there are gaps (unused memories) between fields.

Those gaps are occupied by objects of the class, but are note directly managed through objects. The contents of these gaps are undefined. They may be what's left over since their last usage. Or they might be cleared/filled by a diligent compiler.
When you use memcmp to compare two objects, these gaps which has random bits are also taken into considertion. But this is undesired behavior and leads to uncertainty.

So, never do this unless you're 100% sure about the memory layout, compiler behavior, and you really don't care portability, and you really want to gain the efficiency.

The demo below shall show using memcmp doesn't work correctly with microsoft's c++ compiler v15.00.30729.01 and gcc v4.4.1.


#include "string.h"
// ==================================
//        Class:  Foo
//  Description:
// ==================================
class Foo
{
  public:
      Foo (): a(0), b(0), c(0){          
      };   // constructor
      int a;
      char b;
      int c;

}; // -----  end of class Foo  -----

void shuffle_stack()
{
  Foo f1;
  Foo f2;

  *((int*)(&f1.b)) = 0x87654321;
  *((int*)(&f2.b)) = 0x12345678;
}

int compare()
{
  Foo f1;
  Foo f2;

  return memcmp((void*)(&f1), (void*)(&f2), sizeof(Foo));
}

int main ( int argc, char *argv[] )
{
  int rc = 0;
  shuffle_stack();
  rc = compare();
  return 0;
} // ----------  end of function main  ----------

communicate with service on android

2009-12-09T08:50:00.003+08:00

While doing android programming, it's a common sense to use Activity to interact with users and use Service to perform time consuming tasks (actually, such tasks are usually performed on a new thread spawned by the service). A classic example is media player. It's composed of several Activities and a playing-back Service. Through Activities, users can pick a media file to play, or control (start, pause, fast forward, set volume, etc) the playing-back Service. And the Service is responsible for playing the media file. The service can run in background even no Activity of the player application is active. It's also possible that the Service is implemented and hosted in another application other than the one where Activities are implemented.
In order to allow Activities to control the behavior of the Service, there should be an mechanism to allow they talk to each other. And by following the Process Agnostic feature of Android platform, this communication mechanism should also be able to handle Inter-Process and Inside-Process communication consistently. Such that from the upper layer application code's point of view, it's making communications between components independent of which process these components run in.
Luckily, Android has already provided such a RPC mechanism which has been briefly introduced here: Android application fundamentails - remote procedure calls. And the document Designing a Remote Interface Using AIDL also shows a tutorial about how to perform RPC.
But the documents above don't include a complete yet simple example for us to follow, so I'd like to explore how to do Inside-Process as well as Inter-Process with an example.
This example is composed of two applications. The first application (app1) will bind to a service runs in another application (app2) when a button is clicked, thus demonstrates Inter-Process communication. app2 can bind to the service too, which demonstrates Inside-Process communication.

There are two buttons on each application's Activity. First, you need to click button titled start svc to bind to service and get a reference to Binder object. Then, you can click button titled call rpc to invoke a method in service.

It's trivial to repeat the tutorial of designing remote interface. So I'd like to just post some findings during my exploration.

The onBind method of service should return a non-null IBinder. Otherwise, the callback function onServiceConnected won't be fired.
Add two aidl interface with the same name to both projects (ISvcController.aidl in our example). And the interface can be used in both projects to manipulate the IBinder object returned by the service. These two interfaces can have different member functions, but any function to be used must have the same signature and be placed at the same place (index) in these interfaces.
When access the service in the same process, the original IBinder returned in onBind method is passed to onServiceConnected callback method. When access the service in a different process, a proxy for the IBinder is passed to onServiceConnected callback method.
It's necessary to call unbindService to avoid connection leaking. This can be done upon specific event handler such as a button click. A better choice is to unbind in one of Activity's life cycle events, for example, onStop. So that the connection will be freed no matter in which way the user leaves the Activity.

Source Code
browse code here:
http://code.google.com/p/rxwen-blog-stuff/source/browse/#svn/trunk/android/rpc-with-service
or via command:
svn co https://rxwen-blog-stuff.googlecode.com/svn/trunk/android/rpc-with-service

windows side by side assemblies

2009-12-07T08:30:00.002+08:00

There are times when I deployed an application on a box different from the developing box, the application failed to start with following message:
"This application has failed to start because the application configuration is incorrect. Reinstalling the application may fix this problem."
And run the application in windbg also ends in no avail. It simply complained error 14001 without hitting the ntdll!DbgBreakPoint. There should be something wrong with windows loading the application. After we manually copied msvcp90.dll and msvcr90.dll to the installation folder, it still failed.
Actually, the recommended way to solve this is provided in this msdn document. But to better understand this, we need to know what's side by side assemblies on windows. Simply put, side by side assemblies is invented to get rid of dll hell.

Traditionally, windows searches for dependent dlls in application's current directory and several predefined centric locations (e.g. c:\windows\system32) by dll name. If there are several applications use different versions of a library which is planed to be stored in centric location, there comes conflicts. This can be solved by placing dependent dll in the application's folder, but it also has disadvantages. For example, if an application depends on msvcr80.dll and make a copy of this dll in the application's installation folder. Later, microsoft releases a updated version for this dll with critical bug fixing. It would be difficult to apply this update to the application. The main idea of side by side assemblies is to allow different version of the same dll to coexist in centric location that is easier to manage.
On windows, side by side assemblies are stored in c:\windows\winsxs folder. Every assembly installed there has a folder whose name is composed of the dll name and a hash value, a manifest file and policy file(redirects application from using specified version assembly to another version) in manifest, policy folder respectively. Because different version should at least have different hash value, they don't conflict with each other.
Since windows xp or later, the application loader will take care of finding the correct dll to load. If an application enables side-by-side assemblies, the application loader will load the correct version as being specified by the application in manifest file.

Applications take advantage of side by side assemblies need to have a manifest file specifying dlls it depends on (Actually, windows doesn't allow you dynamically link against crt without manifest file). The manifest file can be embedded in the binary as resource or placed in the application local folder separately. For the latter case, the manifest file's naming convention is Executable_File_Name_With_Extension.manifest. Note that if a separate manifest file exists with a binary having embedded embedded manifest, which one takes precedence is windows version specific and may be different.

To diagnose such issue, here are some tools:
1. System event viewer
The system logs information about the assembly that it fails to locate in System Event. We can use it to find out what is missing.

2. Dependency Walker
It's the best tool for identifying if dependent dlls of an application is available on the system or not.

3. FileAlyzer Utility
It can extract and categorize information from PE file, including embedded manifest file.

4. sxstrace
sxs debugging utility. But only available on vista or later version windows.

References:
How to Debug 'The System cannot Execute the specified program' message
MSDN About Isolated Application and Side by Side Assemblies
Windows Side-by-Side Assemblies (WinSxS)

Ex5.1-3 of Introduction to Algorithms

2009-12-04T13:04:00.002+08:00

Question:
Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 - p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p?

Answer:
If we run BIASED-RANDOM twice, we might get of of following result: 00, 01, 10, 11. And the probabilities for getting each of them is: (1-p) square, (1-p)*p, p*(1-p), p square respectively. We can see that the probabilities for getting 01 equals 10. So, if we can constraint the output to either 01 or 10, we have a UNBIASED-RANDOM that can return 01 or 10 with probability of 1/2 each. And we can simply replace 01, 10 with 0 and 1 to get desired function. How can we constraint the result in 01 and 10? We can use the similar idea used in Ex5.1-2, that's abandoning any result that doesn't belong to 01 and 10 till we get one of them.
And there's a risk in this algorithm. If p is very close to 1 or 0, we may need to try a looooot of times to get either 01 or 10 which makes a very poor performance. To get around this, we can invoke BIASED-RANDOM more times. As we know, the probability of getting a full 0 or 1 permutation is p power the number of times invoking BIASED-RANDOM. And because p is between 0 and 1, the more we invoke BIASED-RANDOM, the less will the probability be, consequently the quicker we don't get full 0 or 1.

Code:

#include "iostream"
#include "ctime"
using namespace std;
int p = 50;

int BIASED_RANDOM ()
{
  int rc = 0;
  if((rand() % 100) >= p)
      rc = 1;
  else
      rc = 0;
  return rc;
}  // -----  end of function BIASED_RANDOM  -----

int UNBIASED_RANDOM()
{
  int rc = 0;

  int temp = 0;
  int i = 0;
  while(true)
  {
      temp = 0;
      temp = BIASED_RANDOM() * 10 + BIASED_RANDOM();
      if(temp == 10 || temp == 1)
          break;
  }

  if(temp == 10)
      rc = 1;
  else
      rc = 0;
  return rc;
}

int main ( int argc, char *argv[] )
{
  if(argc > 1)
      p = atoi(argv[1]);
  srand(time(NULL));

  int rc = 0;
  for(int i = 0; i < 100; ++i)
      rc += BIASED_RANDOM();
  cout << "BIASED SUM:" << rc << endl;
  rc = 0;
  for(int i = 0; i < 100; ++i)
      rc += UNBIASED_RANDOM();
  cout << "UNBIASED SUM:" << rc << endl;
  return 0;
}    // ----------  end of function main  ----------

main thread in android application

2009-12-04T08:48:00.000+08:00

In android sdk document, it's mentioned that all components(Activity, Service, etc) run on the main thread. The main thread is the thread where our code works on.
Conventionally, when talk about a Service, we think it this way:
void service()
{
while(isRunning)
{
// do something
}
}
In other words, a service is usually implemented as a infinite loop. If this is the case for android service, how can it run with other components on the same thread simultaneously?
And think about activity. It has to listen for incoming events like clicking a button, which also implies the pattern of an infinite loop. So, it's also not possible for activity to coexist with other components in the same thread as well.
In fact, components don't have their own loop, instead, they share the same main loop which is implemented in Looper. This also explains why google strongly recommends not do any long-running tasks in a component's life cycle events. Say, if we run a procedure for a long time in onBind function of a service, the main thread won't have any chance to deal with new message in the loop until the procedure finishes. The best idea is to spawn a new thread to do the task and let the main thread back to the main loop as soon as possible.
Looper is the starting point of an application. It acts as the role of message loop. It loops forever waiting for incoming messages and dispatch messages to corresponding components to handle. Upon receiving a message, the corresponding handler object's dispatchMethod will be invoked.
So, in android, a component is a object with a state machine and is able to handle all kinds of messages.

Ex5.1-2 of introduction to algorithms

2009-12-02T08:25:00.007+08:00

A friend asked my idea about the exercise 5.1-2 of introduction to algorithms. Here is the original question:

Question:
Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of a and b? ( RANDOM(0,1) returns either 0 or 1 with the same probability, and RANDOM(a,b) is supposed to return any number between [a,b] with the same probability.)

First Answer: [wrong]
My initial answer which is obviously wrong is like this:


RANDOM(int a, int b)
{
int rc = a;
for(int i = 0; i < b-a; ++i)
rc += _RANDOM(0,1);
return rc;
}

But thinking it more carefully, it doesn't return every number at the same probability.

Second Answer:
The question is similar to flip coins. Each time we flip a coin, we have the same probability to get either 0 or 1. If we flip the coin for several times, the probability of getting each permutation of 0 and 1 is the same. So, if we can use each permutation to represent a distinct number between a and b, we shall get the desired RANDOM function.
How to represent a number with a serials of 0 and 1s? Binary format!
So, if we run the RANDOM(0,1) for 1+lg(b-a) times and convert the final permutation to a decimal value plus a, that's the value we want. And we need to be careful since b-a might not be exact power of 2, so we need to run RANDOM(0,1) for ceiling of 1+lg(b-a) times. But a serial of 0 and 1 of this length might represent a number exceeds b-a, we can abandon the value and restart RANDOM(a,b) till the number is smaller than b-a.
And the code is:


#include    "cmath"
#include    "iostream"
#include    "ctime"

using namespace std;
int _RANDOM()
{
   int r = rand();
   return (r%2 == 0);
}

int RANDOM(int a, int b)
{
   int rc = 0;
   int i = 0;
   // compute log2(b-a) via log10(b-a)/log10(2)
   int t = ceil(log10((float)b-a)/log10((float)2) + 1);
   unsigned int one = 0x1, zero = 0xfffffffe;
   srand(time(NULL));
   while(i < t)
   {
       rc = rc << 1;
       if(_RANDOM())
           rc |= one;
       else
           rc &= zero;
       if(i ==(t - 1)&& rc > (b-a))
       {
           rc = 0;
           i = 0; //restart loop
       }
       ++i;
   }
   return rc + a;
}

int main(int argc, char** argv)
{
   int a, b;
   cin >> a >> b;

   int r = RANDOM(a, b);
   cout << r << endl;
   return 0;
}

video player demo in android

2009-11-30T08:24:00.001+08:00

In this post, I'll show some basic operations in android with a simple video player. The demo shows how to:

Use explicit intent
List video files with ListView, ContentProvider & MediaProvider
Retrieve data from another Activity with startActivityForResult
Play video file with VideoView

Basically, the demo is composed of two activities. The first activity (Main) is a video player with a button on it. When you click the button, the second activity(VideoSelector) shows and lists video files available on the device. Then, after you pick a video from the list, you return to Main activiry and it starts playing the video you selected.

1. Use explicit intent
On android, an intent can be implicit or explicit. An explicit intent clearly designates the component to start. Because explicit intent uses the name of target component, it's usually used inside an application. On contrast, implicit intent specifies desired action, and let the system to pick the best match component.
In our demo, we want to use the VideoSelector to select a video file, rather than the system built-in media selector, so we use explicit intent to start activity. To create explicit intent, we just need to pass the designated component class name to intent, as shown below.


               Intent i = new Intent();
               i.setClass(v.getContext(), VideoSelector.class);
               startActivityForResult(i, 0);

The use of startActivityForResult will be explained later.

2. List video files
Android provides a ListActivity class to list data provided by a ContentProvider. We can take advantage of it to list video files available on current device rather than start from scratch. To use it, we simply make it the base class for our activity, meanwhile, add a ListView with id "@android:id/list" in the activity's layout. And the final thing we need to do is set the datasource for the list with setListAdapter method.
Android also provides a MediaProvider that can list all video files. It's the default provider when we use ContentResolver to query MediaStore.Video.Media.EXTERNAL_CONTENT_URI.

3. Get data from another activity & play video
After we select a video from the list, information of the video such as its path should be passed to the main activity for playing. The recommended way is passing it via intent object. Previously, we start the VideoSelector with startActivityForResult in Main. Being started this way, when the VideoSelector is finished, the onActivityResult method of Main will be fired. So, we need to store the selected video's path in the intent to be passed to Main. Then retrieve it in Main. As shown below:


   @Override
   protected void onListItemClick(ListView l, View v, int position, long id)
   { // in VideoSelector.java
       String filePath = mCursor.getString(mCursor.getColumnIndex(MediaStore.Video.Media.DATA));
         mCursor.moveToPosition(position);
       Intent result = new Intent();
       result.putExtra(FILE_PATH, filePath);
       setResult(RESULT_OK, result);
       finish();
   }

   @Override
     protected void onActivityResult(int requestCode, int resultCode, Intent data) {
       // in Main.java
       super.onActivityResult(requestCode, resultCode, data);
       if (RESULT_OK == resultCode) {
             Bundle bd = data.getExtras();
           String path = bd.getString(VideoSelector.FILE_PATH);
           m_vvPlayer.setVideoPath(path);
           m_vvPlayer.start();
       }
   }

To download full source code for this demo, you can download them from this page:
http://code.google.com/p/rxwen-blog-stuff/source/browse/#svn/trunk/android/mplayer
or with following svn command:
svn co https://rxwen-blog-stuff.googlecode.com/svn/trunk/android/mplayer