đệ quy

Ví dụ về đệ quy, như thế nào là đệ quy – recursive!? Đầu tiên từ Terminal, gõ lệnh VIM để sửa file. Từ trong VIM, gõ lệnh term để mở một cái Terminal mới bên trong VIM, cái này thường cần cho lập trình viên để vừa sửa code một bên, vừa chạy kiểm tra bên kia xem code có đúng hay không, mà không cần phải thoát ra ngoài!

Nhưng vì ta cắc cớ, nên bên trong cái Terminal chạy trong VIM chạy bên trong Terminal này, gõ thêm một lệnh VIM nữa, kết quả là VIM nằm trong Terminal, nằm trong VIM, nằm trong Terminal, nằm trong VIM, nằm trong Terminal, nằm trong VIM, nằm trong Terminal… và trên nguyên tắc có thể kéo dài… vô hạn cấp!

performance

Để làm con Aquarium-PC, tôi mua cái mainboard Huananzhi X99, đây được xem là loại mainboard chạy 2 CPU… rẻ nhất trên thị trường, một sản phẩm đáng ngạc nhiên của các “pháp sư” Trung Hoa, còn CPU là 2 con Xeon Haswell E5-V3, cũng là loại cũ, và khá rẻ. Đơn giản vì đây là lần đầu mạo hiểm, mua rẻ rẻ thôi, lỡ có thất bại, cháy nổ hay hỏng hóc ở đâu đó thì cũng không quá xót tiền! Hệ thống ráp xong chấm được 23K điểm Passmark, một điểm số không hề tệ, ngang ngửa với con MacMini đời 2022! Thế nhưng đến khi chạy thực tế, các bài toán thực, thì Aquarium-PC luôn thua MacMini một chút trong mọi vấn đề, mặc dù thua không nhiều! Đúng là bách nhục, một bên là hệ thống lớn, 2 CPU to cồng kềnh, lại dùng tản nhiệt dầu, còn bên kia người ta bé có chút xíu! Nhưng nghĩ kỹ thì cũng thấy hợp lý, Xeon Haswell là công nghệ của gần mười năm trước, không thể nào so sánh công bằng được!

Nhưng cũng như tôi dự đoán, có một số lớp bài toán mà Aquarium-PC hơn MacMini, nhìn vào 2 cái ảnh dưới đây bạn sẽ hiểu vì sao! Chạy chương trình phân tích dữ liệu tự viết bằng Python, nó tạo ra đến hơn một chục process và dùng hơn 30GB bộ nhớ SWAP. RAM là điểm yếu của MacMini, chương trình chạy đến một lúc lượng SWAP quá lớn, máy nó lì ra không chịu chạy nữa, thậm chí… tự khởi động lại do quá nhiệt! Nhưng con Aquarium-PC thì chạy được, tuy năng lực xử lý thua chút xíu, nhưng có đến 64GB RAM, và chạy vô cùng mát! Không chỉ về RAM, Aquarium-PC còn hơn về thời gian xử lý với những lập trình nhiều processes! Ngày xưa để xử lý dữ liệu lớn/phức tạp, người ta chia thành nhiều bước, lưu kết quả trung gian ra file/database và quay lại xử lý nhiều lần! Ngày nay, với một số lớp bài toán, cứ tận dụng tài nguyên, bỏ hết lên RAM chạy một lần, code vừa nhanh, vừa đơn giản!

home servers


The C-Media usb board adds a cheap (~ $5) sound solution to the Debian box, sound quality is fair enough for “ad-hoc” listening (comparable to that of AC97 on-board chip, and for serious music, there’s already the home media player).

Quite a long time it takes me to finish and “stabilize” all these “home servers”… and finally here it is… On the left, you can see: #1: the 650 Watt UPS that provides about 3 hours of un – interrupted electricity for the whole system, #2: the WAP54G Access Point (hacked with OpenWRT), #3: the Comtrend ADSL router, #4: the LinkStation CHL (Debian Lenny: print server, 1T disk space for samba share, bittorrent server), #5: the LinkStation Duo (Debian Lenny: 1T of RAID-1 disk space for important data, SVN, Web, VPN servers (for remote access) and MPD music servers), #6: speakers.

All these miniature machines help streaming lossless music and HD video to the media player (LT-H90LAN – another Linux box resides in the living room). Except for the router (which is specialized hardware & firmware OEM-ed by Comtrend to FPT – the local ISP), all others devices runs Debian or another Linux variant. The total power consumption of the whole system is less than 50 Watt. Future computers would consume less than 1/10th of power compared to today’s ones… Power is the key, less power means less heat, less noise, more stable and more durable… the factors that make successful home services!

buffalo duo


My Buffalo, a 400 MHz, power-efficient ARM system (it consumes about 17W on average). The duo: two SATA disks (1TB each) running in RAID-1 configuration. The system can also act as a print server: most cheap home laser printer are not stand-alone device (lacking PostScript capability) and need to be attached to a PC in order to print, instead we can connect printer to this Buffalo box via usb and serve printing over network.

My newest toy: a Buffalo LinkStation Duo Network Attached Storage (NAS – or a poor man’s home server). Had thought about this long ago but don’t have time till now to dig a little bit low-level to get the thing to work! Basically what I want to have is a miniature general-purpose home server, which would run continuously 24/7. But you know with the temperature and electricity conditions here in HCMC, most PC would surely break down if let running continuously for a few months. The idea is to hack this NAS device to run Debian and turn it into a hybrid system: NAS (file server, torrent, UPnP…) and a home server which would handle a little more extra tasks. I took me a whole night to figure out how to do it.

1.   Boot the device via tftp, using u-boot, the universal bootloader. We need to to erase the HDD’s partition table (with something like: dd if=/dev/zero of=/dev/sd[a/b] count=1) to force the device into tftp boot.

2.   Telnet to the device and prepare the disks: using fdisk to apply a same partition structure to both two disks (/dev/sda and /dev/sdb) with the usual Linux FS: /boot, /swap, /(root), and /data). The disk structure would appear like this:

Device Boot Start End Blocks Id System
/dev/sda1 1 6 48163 fd Linux raid
/dev/sda2 7 1200 9590805 fd Linux raid
/dev/sda4 1201 60801 478745032 85 Linux extended
/dev/sda5 1201 1329 1036161 82 Linux swap
/dev/sda6 1330 60801 477708808 fd Linux raid

3.   Setup the RAID-1 (one-to-one mirror) structure, you can see that we mirror /boot (sda1, sdb1), /(root) (sda2, sdb2), and /data (sda6, sdb6), there’s no need to mirror /swap:

mdadm –create /dev/md0 –level=1 –raid-devices=2 /dev/sda1 /dev/sdb1
mdadm –create /dev/md1 –level=1 –raid-devices=2 /dev/sda2 /dev/sdb2
mdadm –create /dev/md2 –level=1 –raid-devices=2 /dev/sda6 /dev/sdb6

4.   Install Debian (Lenny) using debootstrap, a very handy tool to install Debian directly from a repository. DeBootStrap pulls the packages over network, build a new rootfs, after chroot-ing to the newly build system, pull and build the kernel from source. After that, we can use regular Debian commands to update, configure network, add softwares, etc… After rebooting, we’d got a brand new Debian with 1TB of RAID-1 disk space, which runs flawlessly and which is ready to serve my various automation tasks!

Notes: installing Debian would void the warranty and could easily brick your device, use the information at your own risk. The steps here are just summary, there’s been various try and fail to get the thing done, e.g: we need priorly to have binutils, wget, zlib and libssl binaries for debootstrap to work (download the deb files from Lenny’s repository, extract and copy over the Buffalo), after debootstrap-ing, I forgot to set the root password, and unable to login when the machine reboot, thus having to start the whole process over again. For further details, please consult the Buffalo NAS community.

UPDATE, Nov 18th, 2010

For a NAS which runs 24/7, it’s critical to monitor system status (temperature and the moving parts). I wrote this little fand script, a daemon to monitor hard disk temperature and adjust the fan’s speed accordingly. HDD’s temperature can be retrieved using smartmontools (most hard disk nowadays has S.M.A.R.T capabilities). And fan control on Buffalo LS Duo is done via the gpio module (thanks to talent hackers on the Buffalo NAS forum), something like this:

# values can be ‘off’, ‘slow’, ‘fast’ and ‘full’
$ echo ‘slow’> /proc/linkstation/gpio/fan

I’ve defined some thresholds, in a tropical country like VN, room temperature around 30° ~ 35° (Celsius) is a common thing, so if the HDD’s temperature is below 35°, we would turn off the fan. If it is between 35° ~ 40°, the fan speed would be ‘slow’, from 40° to 45°, the fan will be turned to ‘fast’, and if temperature excesses 45°, fan speed is set to ‘full’. Well, and even if 50° is reached, we would send a notification email (via sendmail) and shutdown the system. If you find it interesting, here is the fand scripts.

UPDATE, Nov 20th, 2010 (THE REAL DUO)

To pair with the Link-Station NAS is its cousin also from Buffalo, the Link-Theater LT-H90LAN. The LT-H90LAN reads media from Samba shares or DLNA server via LAN and is a 720p and 1080i HD-ready device. Although not Full-HD (1080p), that’s enough for my need (I don’t have a Full-HD TV in my house anyhow, maybe I’m waiting for 3D home video). It’s quite pleasing to enjoy good video quality and excellent audio in your living room, all streaming from a central NAS. The box also runs a variant of Linux (though hacking can be a pain, I would only left the device untouched for safe). This is one further step toward an all-Linux-devices home (thought I should buy an OpenMoko phone then).

kindle and feeds

After years in IT career facing monitors, it’s now time to care a little about your eyes, and I’m now using my Kindle for reading news, documents everyday! However web browsing on Kindle is quite inconvenient, there’s of course no touch screen (imagine how touch would look like with a 3fps responsiveness display), and the 5-ways button make web pages’ navigation a kind of clumsiness! I was thinking about some form of automation, basically we would need to convert some news-feeds into Kindle’s native format (mobi) for the ease of our reading, the steps below:

We’re going to use Calibre, the famous ebook-converting tool: sudo apt-get install calibre. Or you can install it (binary or source from) on Linux as guided here. The very nice feature of Calibre is that it can fetch news-feeds, parse and format them following a pre-defined rule-set called “recipe”, there’re hundreds of built-in recipes as well (“recipes” are actually python scripts used to parse and layout the data in html and some css). Below is how I fetch feeds from Engadget and VnExpress and convert them to .mobi, the native format that layouts very well on your Kindle:

$ ebook-convert /opt/calibre/resources/recipes/endgadget.recipe endgadget.mobi –output-profile=kindle
$ ebook-convert /opt/calibre/resources/recipes/vnexpress.recipe vnexpress.mobi –output-profile=kindle

Copy the files over your Kindle, the news feeds read out very very nice! (images on the left, click to enlarge). The next step is of course some further automation, you don’t want to do the whole thing manually everyday, do you!? All these works can be accomplished by a shell script, scheduled by crontab! Just have your home server prepare the documents and sync it to you via Dropbox, from which you can download and view on the device (Kindle naturally permits downloading .mobi documents). I’m using this way to serve myself latest news with coffee every morning!

kindle development without kdk

KDK, the Kindle’s Software Development Kit has been released for quite some times but Amazon still strictly restrict accessing to it, many many software developers (like me) have registered and received no reply. It is understandable that Amazon could be skeptical on what to put on Kindle’s app store, but it should not be that conservative toward the developing community. KDK is basically just a PBP (Personal Basic Profile) J2ME (Java Micro Edition) with Amazon’s extension, a Kindle emulator, and some tools…

Having no KDK doesn’t mean that we can not develop software for Kindle! Below are my notes on building, deploying an example application for Kindle. This would make cleared the steps needed to write applications for Kindle without the KDK. Please notes: the information is collected from many different sources, jailbreaking could be considered “illegal” according to some Term Of Use. Use the information at your own risk!

1.   Jailbreaking and usbnetwork

Download kindle-jailbreak and kindle-usbnetwork from here. Choose the files that is suitable for your device, e.g: for my Kindle 3 (wifi + 3G), it would be the jailbreak_0.4.N_k3g and usbnetwork_0.27.N_k3g. Copy the jailbreak_0.4.N_k3g file to your Kindle, then proceed to updating the system. The jailbreak exploits a hole in Busybox implementation to gain root access. Next, do the same thing with usbnetwork_0.27.N_k3g, which provides a secure shell via USB connection.

Launch the Search box on our Kindle, type ;debugOn, press enter to execute the command, then do the same thing with ~usbNetwork to start the sshd daemon. The default configuration would set Kindle to 192.168.2.2 and expect the connected PC to be 192.168.2.1. Now we’ve got root access and the entire FS (file system) in the palms of our hands. Spend some times exploring it, when done, put the Kindle back to normal use by issuing ~usbNetwork again, then ;debugOff.

2.   Key and file signing

This is the most important part! Kindle’s “kindlets” are exactly Java’s jar file with .azw2 extension, however, we can’t just simply copy and run it. The applet is linked against several system libraries located at: /opt/amazon/ebook/lib/Kindlet-1.1.jar and /opt/amazon/ebook/sdk/lib/*.jar (copy these files to your PC for local jar building in place of those provided by the KDK).

The .azw2 file must also be signed with 3 different keys located at: /var/local/java/keystore/developer.keystore and the security policy is defined at: /opt/amazon/ebook/security/. For more information on signing, please refer to this post. If you’re tweaking your Kindle and writing apps for it, I suggest that we would just use the signing key of Andrew de Quincey, the first one to figure out about this, so that free softwares can be easily shared among Kindle’s users.

Configure the usbnetwork interface and access Kindle via sshd. Image below: the command htop running on Kindle’s ssh console.

When finished with hacking, we can un – install these two exploits to restore Kindle back to original state (and receive official updates from Amazon), but that would be after the next section, when we’d been able to deploy our own software on it!

3.   KindleGoban – an example app

I’m going to deploy KindleGoban, a Go (weiqi) game viewer, as an example app. Adrian Petrescu, the man behind this open source game, is perhaps, an insider of Amazon’s KDK project. But technically he’s under a NDA (non disclosure agreement) and won’t be able to say anything except the publicly available information. However, he did indirectly provide valuable resources.

First, copy the developer_keystore (mentioned in #2) to your PC & Kindle (at /var/local/java/keystore/developer.keystore). Then download KindleGoban (and its dependency library KWT. Make some changes to the build.xml to include KWT (adding several widgets) and get rid of the KDK’s stuffs (which we don’t have). Then build, sign and deploy the .azw2 file to your Kindle. And there you are, a nice Go game viewer!

# first, build and sign the jar file
$ ant build.xml
$ jar cvfm KindleGoban.azw2 KindleGoban.mf bin/*
$ ./signkindlet developer_keystore KindleGoban.azw2
# copy the file over to your Kindle, also need
# to copy an example .sgf file for testing
$ scp KindleGoban.azw2 root@192.168.2.2:/mnt/us/documents

4.   Resources

This section gonna be regularly updated on the availability of documents, tools.. for development on Kindle. Please note most of these are from third – parties rather than Amazon, which are the results of hacking, reverse – engineering… and some other information indirectly available from the KDK. At the moment, we only have this official javadoc from Amazon which describes the KDK’s APIs.

  • Savory: a native ebook converting daemon for Kindle.
  • Kindle emulator: need to double check this.
  • KWT: Kindle Widget Toolkit.
  • Mangle: a manga viewer for Kindle.
  • Qindle: a Qt port for Kindle.

KindleGoban screenshots, this is, like most Kindle projects at the moment, is just starting, would expect more features in the time coming.

kindle 3


Can not resist to this temptation anymore. Kindle price dropped significantly lately and it’s time to pick a e-ink display book reader for myself. I’ve been curious about electronic paper display, the alternative to LCD or OLED displays widely used on hand – held. Actually there’s been various devices (phone, watch…) which make use of electronic paper, but none has the success like Kindle.

The first impression is that the display, which is 16 gray – scale colors, really looks like traditional paper, and reading on it is an actual pleasure. The screen refresh rate is quite low (maybe less then 6 fps), which means video would never be an option on Kindle. To my surprise, sound is extremely good, the external speaker produces stereo which may be far better than on my laptop. Wifi works fine and the experimental browser (which only supports JavaScript, no Flash, no Java) is enough for basic email and web surfing.

Connecting to my Linux box, the device appears as a normal USB mount to easily copy files over. I find Kindle very suitable for my needs: document reading, a bit of music, and casual web & email. Moreover, Kindle does not create the impression that it is an electronic device. The battery is advertised to last about 10 days (with wifi on, and even more with wifi off), so we don’t have to care about recharging very often. It simply boots up and runs, and displays nice pictures in screen – saver mode.

Amazon recently released Kindle’s SDK beta (Software Development Kit) with Java as the primary language (J2ME), and maybe C/C++ for system development. The machine’s GUI proposes to me a lot of interesting ideas on usabilities and UI design!

chinese rendering server

In my previous post, we can see the image – replacement technique being applied to mathematical formulas rendering. Replacing text by image can be seen in various Web’s techniques, mainly to display things that browser can’t! It’s a possibility that many Web technologies would never converge into common “form factors”: how many years have passed but SVG is still not supported on all browsers, how font technologies are still fighting stiffly with each other? Various issues would always remain unresolved and image replacement, though ugly and inconvenient, could be used as a temporary solution.

As you can see in the image above: the first line is a popular Chinese straight – stroke font that can be seen on most browsers, the next lines are nice calligraphy (brush – stroke) fonts that can hardly be seen on the web! I’m going to try using FreeType2 for a very specific problem: rendering Chinese fonts, the only reason is just simple: aesthetics! Searching around, I can’t find any simple, standalone solution: nice Chinese fonts are very big, a typical ttf file has size from 5MB to 50MB depending on the character set and quality (with that size, it’s obvious that we should use a server side solution). Packages like Pango or Cairo are too complex, and would require additional dependencies (which is unavailable on a free Linux host).

It takes me a whole day struggling with FreeType2’s reference and manual to get it work with Chinese fonts (quite different from conventional Latin fonts indeed), and finally here it is! You can access the executable at: http://tkxuyen.com/freetype2.php with the following syntax: freetype2.php ? text=… &font=… &size=… &color=… here is an example. Below are renderings with different sizes (anti – alias works really well):

text=洛阳城东桃李花飞来飞去落谁家&font=2&size=11&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=12&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=13&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=14&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=15&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=16&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=18&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=18&color=111111
text=洛阳城东桃李花飞来飞去落谁家&font=2&size=19&color=111111

and renderings with 3 different Chinese fonts (very big files, installed on server) and in different colors. Just note these fonts are a bit non-standard: they produce traditional Chinese characters as output, but only accept simplified Chinese as input:

text=洛阳城东桃李花飞来飞去落谁家&font=2&size=19&color=FF1111
text=洛阳城东桃李花飞来飞去落谁家&font=1&size=19&color=11FF11
text=洛阳城东桃李花飞来飞去落谁家&font=0&size=19&color=1111FF

Update, Jun 6th, 2021:

Due to some changes on my web-hosting, CGI is disabled for some reason. I really don’t have time to figure out why, so just temporarily remove the Chinese font rendering for now!

FreeType2 is an very handy open source library, it’s available on many flatform: Unix, Dos, Windows, Mac, Amiga, BeOS, Symbian… and it does a very good job of handling typefaces! Since FreeType2’s patent issues have expired since May, 2010, we would see an increasing application of FreeType2 in many areas.

This is my very simple C code (~250 LOC) to experiment with FreeType2: loading font, loading glyph, rendering bitmap, dealing with Unicode… To compile, just something like: gcc gifsave.c freetype2.c -o freetype2.cgi `pkg-config --cflags --libs freetype2`. I hope I can have time to extend the code into a more usable form: multi – line layout, alignment, RTF support, etc… Some restrictions are imposed to protect the server, if some text can’t be rendered (e.g: rendering dimensions are too large), an error image like this is displayed instead:

latex rendering server


Some example expressions rendered by MimeTeX (it’s good to appear to be smarter than you are!) If an expression fails to be rendered, you would see an error image like this:

Recently, the wonderful yourequations.com site (which I’ve been using to occasionally render mathematical expressions on web pages) has ceased it’s service due to heavy traffic. I was thinking about running my own LaTeX rendering server, things turned out to be pretty easy as follow, thanks to the excellent MimeTeX package, a LaTeX reduced subset. It’s also interesting to experiment the “stone age technique” of CGI, first download and compile the package:

wget http://www.forkosh.com/mimetex.zip
unzip mimetex.zip
cd mimetex
cc -DAA mimetex.c gifsave.c -lm -o latex.cgi
# test the binary, view the ‘fermat.gif’ image
./latex.cgi -i “a^2+b^2=c^2” -e fermat.gif

Uploaded to host, latex.cgi runs without any dependencies. The ugly thing with my (free) Linux host is that although it does allow CGI, it doesn’t allow CGI to return documents of type ‘image/gif’ no matter what. To work around, I wrote a small PHP script, which parses the GET input, calls CGI to generate and save image in a cache directory, then redirects request to the LaTeX image. This also helps not to expose your CGI directly on the web too!

// use ‘system’ command to execute CGI
$cmd = “$mimetex_path -e “.$full_filename;
$cmd = $cmd.” “.escapeshellarg($formula);
system($cmd,$status_code);
$text = $pictures_path.”/”.$filename;
return $text;

I’ve been always loving CGI for its simplicity, CGI, Perl, Python… old things never die! Although I have almost no experiences with them, they let you do whatever you want to given a little tweaking know – hows. Please note that MimeTeX is not as full – featured as LaTeX, it can’t render some too – complex expressions and it uses an ugly bitmap font. If your server has some LaTeX support, consider using MathTeX, a more advanced version from the same author.

Update, Jun 6th, 2021

Due to some changes on my web-hosting, CGI is disabled for some reason. I really don’t have time to figure out why, so just temporarily remove LaTeX rendering for now!

3d graphical user interface

The code is written in C++ base on Clutter 1.2.4 library. It shows basic widgets: tabbed container, scrolling container, list box, combo box, check box, edit box, button, label, radio button…

This is my personal project in which I tried to evaluate some new ideas and concepts in using 3D techniques for GUI (Graphical User Interface). It’s quite tiny indeed (about 6000 LOC – line of code), all written by myself in about a month (mostly in my free times at weekends). So please don’t blame me on some un-completed or un-polished features, they are just for testing the ideas only. I would try to examine the trend of applying 3D graphics to GUI, but first, let have a look at the video below.

1.   The first thing to consider is not 3D engines or hardwares, it is about usability. Many traditional (2D) GUI out there are already complex and obstructive. GUI is about information presentation and presentation should be really simple and clear so that even my grand mother can understand and use. I’ve been seeking, trying to explore many new ways invented to represent information in 3D (or 2.5D) space, and I could say only a very very small percent of them could make a usable value. Users have long been familiar with 2D, and yet 3D hasn’t been very much persuasive.

2.   3D hardwares can be categorized into 3 groups (as listed on the left), and the 3D engine can be configured to off-load calculations to hardware. With the 1st type of device, only bitmap operations could be off-loaded. With the 2nd type of device, many drawing operations (the path_xxx functions) can be off-loaded. The 3rd type of hardware is most valuable since we can have its finish for ourselves a lot of work.

It’s important to understand the target device our software stack would be running on. If it is an out-date machine with just some blitters, we should use paint-like (aka: bitmaps) operations, while on most modern PC, draw-like (aka: 2D vector) operations are more encouraging. While bitmaps may offer nicer and more customizable GUI, the cons is it lacks the scalable ability that vector has.

3.   The last is about software implementation. Many of the graphics concepts are first introduced in software, which then embedded to hardware, which then standardized by software (like OpenGL or DirectX) again. Thus, many elements of a graphics pipeline is the production of a long history of interactive evolution. A graphics pipleline is not a general framework, it depends on very detailed, in-depth techniques to be operational in real-world application.

Game & graphics are the domains where most formal software methods would easily failed. 3D graphics developers should have good knowledge on graphics in general (bitmap and vector drawing), geometry, linear algebra & discrete maths, deep understanding on data-structures and algorithms… are strong pluses, advanced tips & tricks in coding and optimization is a must (game & graphics programming has always been a hell of tricks from the age of dawn) and finally good understanding on 3D techniques (model, scenegraph, projecting, shading, clipping, lighting, effects…)

3d

We are building something like this, a 3D user interface. Day by day, we’re witnessing more and more diversities in computer user interface: concepts, designs, look and feel, animations, effects… While some would stick to an bare – bone, obscured text console, the others prefer some fancy, eye – candy GUI with all its bells & whistles. Things are much easier now with many 3D libraries and tools. Remind me about how I did all the 3D things: polygon, mesh, texture, sprite, shading, lighting, scene – graph, etc… with C & assembly on DOS!

vim for programmer

VIM “IDE” with symbol – browsing and auto – completion

Various utilities inside VIM: media player, calendar, file explorer…

I have been using VIM for most of my daily programming, and everyday, I’ve been discovering new things about VIM. We can tune VIM into a full-fledged and powerful IDE (Integrated Development Environment) that far surpasses every others! With ctags and taglist.vim, we can build tags database, which would then enable searching, browsing all symbols, variables, functions in a code – base. cscope enhances ctags even more with advanced search & browsing features. And I would need no external diff tool since we’d already have vimdiff to compare and merge code.

Working with different types of version – control system, we’d already had vcscommand.vim, which can help interfacing with svn, cvs or git! To interact with file system, I would use NERDTree or vimExplorer, a lot of tasks with fs is done even without leaving VIM! I’m not fool enough trying to do everything with VIM, but there are many other plug-ins that you would find useful: a.vim and c.vim would help you a lot in C/C++ programming, calendar.vim helps you viewing date, and keeping small notes (diary) for each day, musicbox.vim serves you with media playing inside VIM, and vimail helps send, receiving emails with just a few convenient keystrokes!

virtualization

MineSweeper running in DOSBox

Click the demo page below (jpcapplet.jar – 1.8 MB in size), it would take some times to load, embedded in it is a DOS image (floppy.img) of a floppy’s size (1.4 MB). In Linux, using dd to create a blank image file, launch JPC app, mount the empty image, fdisk to give it a partition structure, format to give it a bootable FAT12 file system, copy the files over, edit autoexec.bat to have the game run at startup, and voila – there you are, the classic DOS game of MineSweeper on the web!

Beside is screen-shot of my very first programming, the classic MineSweeper, an exercise I did first year at university. After getting started with Borland C++ 3.1, I began to write numerous toys like this; small games, graphics, animation, 3D… are among the things I was very fond of. We still had not had Internet in Vietnam then, lacking of information, we’d reinvented many wheels, including a package for displaying 3D objects (in form of polygon mess), a complete GUI for DOS with window, menu, toolbar, all kinds of controls: combo, list, button… But as they say: don’t reinvent the wheel, unless you plan on learning more about wheels, the reason we did all that fun stuff.

Back to my MineSweeper, it’s tiny, about 350 LOC (Line Of Code), using BGI (Borland Graphics Interface), C/C++ and some ASM. Yesterday, just want to check the old source, but didn’t have a Windows machine at hand, I needed to run the Borland C++ 3.1 compiler on my Linux box. Wine is good for many Windows applications, but it simply won’t work with pure DOS programs. Then I found DOSBox, you start it up in form of a console, mount a directory in local file system, have BC 3.1 installed and compiles flawlessly, and MineSweeper runs well on this virtual DOS on top of Linux!

That’s some layers of virtualization, say I want more, I want to show MineSweeper on the web, but don’t want to make change to the code, or even to the compiled binary. Could it be possible? The answer is: YES! You would need JPC, a pure Java IBM-PC emulator, it runs where there is Java: x86, RISC, mobile phone… On top of it, you can run a bundle of different OS: DOS, Linux, Windows… Then comes the delicate distinction between virtualization and emulation, hardwares, softwares, all can be virtualized to some great extent. Imagine you would run some games & utilities on a virtual DOS (or Linux) running inside JPC, hosted in Firefox browser, which in turn runs on Windows (or Linux)!

JPC can only bring about 20% power of the native machine, and even a tiny game like this is overkill to it, and mouse functioning is really crappy too. But that’s suffice to demonstrate the idea, JPC could be improved I believe. More games would be added to this Web DOS console later on! Anyone still remember Tetris, Croix-Zero, Snake, Mario…? So, what’s the points for JPC? Demonstrating the fractal principles in hardware, software evolution? Too much “nostalgia” for the “good old days” – DOS games? Anything else or just reinventing the wheel? The answer may be so, but I love this idea of cultivating the past, and pop out new things for the future!

math expression on www

I rarely need to write mathematics expressions on the web, but the last time I did, it took me some times to figure out just how to do. It’d turned out to be pretty easy, there’s a free LaTeX rendering server at yourequations.com. Excellent site! Just feed it with a LaTeX expression, it would render an image for you to put on your web page. This may be the best solution for now, while waiting for an workable HTML version that supports math.

There’s also a guide to embed this feature onto Blogger blogs (and also WordPress, and some PHP forums…) Just insert your LaTeX code between the pre (or code) tags as below and the jsTeXrender JavaScript would do the rest for you. This works fine for any browser with JavaScript support (mouse over the expressions and you would see the underlying LaTeX code). You may also need this LaTeX Reference Card for a list of LaTeX’s symbols.

Update, Otc 1st, 2010

Due to heavy traffic, yourequations.com has ceased the service. Please see this new post on how to run a LaTeX rendering server of your own!

fingerprint sensor & ubuntu

My right index finger scanned and correctly identified

Too much literature, too much music lately, now some technical to line up thoughts in my head. Fingerprint reader has been out for quite a long time, but has only come to my hand recently on this HP 6910p laptop. The machine has an AuthenTec AES2501 fingerprint sensor built in, and using it is quite straight – forward under Hardy Heron:

1.   Install fprint-demo, libfprint-dev, libfprint0 and libpam-fprint from the ppa.launchpad.net/madman2k repo.

2.   Use fprint_demo to enroll some fingers. Identification and verification is good for thumb and index fingers, but really bad for middle, ring and litte ones.

3.   Configure pam module to make use of fprint, add the two lines: auth sufficient pam_fprint.so & auth required pam_unix.so nullok_secure to your /etc/pam.d/common-auth file. Remember to enable still password login since fprint is quite preliminary.

Now restart your machine and enjoy! At login prompt, you would need to enter username, then enroll a finger for authentication. If enrolling fails, normal password login would then be applied. In KDE, screen-locking and gksudo work seemlessly with fprint.

I observe for a while the fingers’ scanned images, to find out how they did all the identification and verification tasks. It’s quite clear that they are using some control points (called minutiae). You can see red dots in the image on the left (binarized from raw scanned image): they are either end points or branching points (point at which vein separates into more veins). They don’t need to match all veins of fingerprints, they only need to do some pattern – matching on the set of minutiae. Given two sets of minutiae, some Cartesian measures on points’ position may be enough for matching two fingerprints.

This machine, HP 6910p, is designed for medium performance, but for advanced security: the machine has TMP chip inside, with a smart card slot, and a fingerprint sensor. That would be quite sufficient to protect your privacy.

file system encryption


The pc-link reader, could be in many forms: usb, serial, pcmcia, pinpad…

An Axalto (previously Schlumberger’s, now Gemalto) smart card, this could be an access – control card, a bank debit / credit card, health – care card, social – identification card… Some smart card types are actually tiny computers – they have an Operating System, and Java virtual machine inside. Note: many of the smart card vendors are OEM – ed from SCM Microsystems, a Germany – based company. We’d better choose hardware and firmware directly from SCM when work on open – source projects.

You have important data on your laptop, and one day the laptop is stolen. The best you can expect is that you loose all those valuable information. The worse… who know what it can be!? Since having a computer (hardware) in touch means having access to every data stored on it. How can you protect yourself from that situation?

The solution is encrypting your storage and keep your key safe from others’ access. You can encrypt your home directory or a whole data partition. (Some even encrypts /boot, /swap and /(root) – full disk encryption – so that their activities leave no traces). With Linux, every tools is at your hand, so let start making your life easier. Below is some guide lines on how to do it on Debian.

1.   Install eCryptfs: a Linux native and POSIX – compliant enterprise – class stacked cryptographic file system.

$ aptget install ecryptfsutils
$ modprobe ecryptfs
# you may have to patch your kernel in order for
# ecryptfsd (the key management daemon of eCryptfs)
# to work. in that case, you’d better grab and
# build eCryptfs from the latest source.

2.   Setup eCryptfs:

# simple setup, passphrase entered from stdin,
# eCryptfs allows overlay mounting: mount point
# and the actual storage can be the same.

$ mountt ecryptfs /encrypted/storage /mount/point
# you can now see your new fs using the command df,
# test it, go to your mount point and input some
# data, watch the output at the encrypted storage.
$ cd /mount/point
$ echo “Hello World” > hi.txt
$ cd /encrypted/storage
$ less hi.txt
# umount /mount/point and the file system
# is not accessible anymore

HOW TO PROTECT YOUR KEY?

Every security solution comes to a very dead-end that there’s must be a MASTER KEY as the main entrance for the whole system. And we have several ways to protect the master key:

+   the tricky way: store the key somewhere on the disk, e.g: at the first sector of the volume image (offset some bytes to a position only you know) so that the key is hard to find and can not be accidentally deleted. More information about the trick is here.

+   the explicit way: store on an external storage such as usb, the system could only be functional once the usb is plugged in.

+   the “smart” way: smart card is the best way to store key. Since you can write public / private key to a smart card but can only read public key back, no – one can read the private key, including you. Smart card is designed to do encryption / decryption jobs: just request the card to encrypt / decrypt some data using a specified key, and the card sends back the required output.

In an organization, the private key is stored on smart card and given to the “person in charge” without the fear of loosing the key. For personal use, I think the second solution (using usb) is quite enough.

1.   Setup smart card:

# install pcscd, the daemon to talk with
# card reader install OpenSC, the open
# source smart card project

$ aptget install pcscd
$ aptget install opensc
# in my case, I have an Axalto reader which is not
# supported by pcscd. knowing that Axalto’s
# hardwares are OEM-ed from SCM, I just download
# the firmware from SCM, flash the reader and it’s
# then recognized as a SCM SCR 331 device. You can
# play around the smart card using opensc-tool,
# you can erase, init the card’s file system,
# create some PIN, generate some keys using
# pkcs#15-init, encrypt/decrypt can be
# done using pkcs#15-crypt

2.   Working with keys:

Public and private keys are fundamental concepts of Digital Signature. In short, multiply two big prime numbers – two private keys – you have a semi-prime number – the public key. Certificate is wrapper of the public key to work with a CA (Certificate Authority), for the public to check if a public key really belongs to an organization.

# generate public and private keys in RSA 1024
# bit pem format extract the public key from this
# keys pair, encrypt/decrypt with the keys

$ openssl genrsaout private.pem 1024
$ openssl rsain private.pemout public.pemoutform PEMpubout
$ openssl rsautlencryptinkey public.pempubinin file.txtout file.ssl
$ openssl rsautldecryptinkey private.pemin file.sslout decrypted.txt
# create the smart card’s file system,
# then create a PIN

$ pkcs15initcreatepkcs15
$ pkcs15initstorepinauthid 01label “mycom”
# copy private key to smart card, to decrypt,
# we need to specify key’s usage

$ pkcs15initstoreprivatekey private.pemauthid 01id 45format pemkeyusage sign,decipher

3.   Setup the whole thing:

With your smart card properly setup (a public/private key pair has been stored), we can use the following script to: 1. create a temporary volatile file system 2. use smart card to decrypt the password and store to that file system (these files would simply disappear when the machine power down) 3. using the decrypted password to mount with eCryptfs.

# 1. create a volatile fs to temporarily store the
# decrypted passfile

$ mountt tmpfso size=10M,nr_inodes=10k,mode=0700 /tmp_fs
# 2. decrypt the password file from
# /root/passwd to /tmp_fs/passwd

$ pkcs15cryptpkcs1decipherk 45i /root/passwdo /tmp_fs/passwd
# 3. now mount our encrypted
# directories with eCryptfs

$ mountt ecryptfs /encrypted/storage /mount/pointo key=passphrase:passfile= /tmp_fs/passwd, cipher=aes, ecryptfs_key_bytes=16, passthrough=1, verbosity=0

Done! Choose a strong encryption algorithm (e.g AES 256 – bit), and in most cases, you and your data would be safe until they have quantum computer running. Be sure to keep your key secret or your efforts would be of no help. For maximum security, choose a good smart card model, increase your keys’ size, revise all procedures of your software system…

(You’re pretty safe right now, so why there’s an “in most cases” in my last paragraph? The truth of being secured is actually more complex than that, as a quite-simple technique like this could be applied to steal password of a disk-encryption system. This bases on the fact that data in DRAM is not faded right away after loosing power, it still can last for some seconds (or even minutes), and by cooling the DRAM using an air duster (to slow down the fading speed), the DRAM module could than be copied and scanned for password (assuming that password has been entered and kept in memory). Nothing is really safe, however, hardware problem like this should have a hardware solution (like this AES 256-bit encryption Fujitsu hard drives).