Uploaded first package to hackage today

http://hackage.haskell.org/package/hashing

Finally started to use something fancy (Data.Aeson)

First time aeson user. The magic part is ToJSON/FromJSON instance. Knowing how generics works in Haskell, one could intuitively expect empty ToJSON and FromJSON instance to work as is (no need to write any specialization to serialize/de-serialize ADT) and that will be the discipline I would choose when define APIs.

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE DeriveGeneric #-}
import qualified Data.ByteString.Lazy as L
import qualified Data.Text as Text
import Data.Text(Text)

import Data.Aeson
import GHC.Generics

data Patient = Patient {
    firstName :: Text
  , lastName :: Text
  , emailAddress :: Text
  , birthDate :: Text
  , latestBloodPressureDate :: Text
  , systolic :: Int
  , diastolic :: Int
  } deriving (Generic, Show)

instance ToJSON Patient where
instance FromJSON Patient where

patients :: L.ByteString -> Maybe [Patient]
patients = decode

main = L.getContents >>= print . patients

generate all combinations of given length for [1..k]

> selections 2 4
[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]

selections :: Int -> Int -> [[Int]]
selections 1 k = fmap pure [1..k]
selections n k = liftA2 (:) [1..k] (selections (n-1) k)

total number of selections = k ^ n

Generate BST for an ordered list

It seems hard when first heard of this. However, it's way more easier they I thought:

import Data.Array
import Data.List

data BTree a = Leaf | Branch a (BTree a) (BTree a) deriving Show

-- | the type signature can be omitted, use it here for documentation
makeBST :: Ord a => [a] -> BTree a
makeBST xs = acc (listArray (1, len) (sort xs)) 1 len
  where len = length xs
        acc u i j
          | i > j = Leaf
          | i <= j = Branch (u ! k) (acc u i (pred k)) (acc u (succ k) j)
            where k = (i+j) `div` 2

The idea is extremely simple, for a (sub) list already sorted, divide it to

  [left] ++ [pivot] ++ [right]

make pivot to be the root node, then call makeBST recursively on both @left and @right, and inserted it to the root node.

I've spotted C++ implementation which made me headache, however, the Haskell version feels like a one-liner.

Guess I've found another example of my theory:

  To learn algorithm, you probably shouldn't read any code at all, not even pseudo code.

There are some outstanding books on algorithms, what I don't like is the imperative style pseudo code, and assume you have to implement the algorithm with C/C++/Java, which is really hard to understand. To me, if I tried to read into the code, I would forget the algorithm itself pretty quick, 3 month later, I forget the code altogether; Instead, tried to understand the algorithm without any code (or at least functional ones, draw graphs if necessary). It may take longer when implement some algorithms than memorizing the code, the upside is this kind of memory last really long.

match incremental input with predefined dictionary

Requirement:

1) a dictionary with many words (String) without duplicates
2) an input feed with many continuous characters (String)
3) input keep growing (append new character) if any word in the dictionary is a prefix (including equal) of the input stream, in this case the word need to be recorded, and continue 3); if none is a prefix of the input stream, then input terminate, return the result

Looks like a Trie can be used for such task, for every iteration when input grows, check if we can find input stream from the dictionary (converted to a Trie); however, it's not easy to implement efficient and pure functional Trie in Haskell. Thus here the alternative.

The idea is for every iteration, we keep reduce the candiates, if any candiates has a full match, we then could return the candiates; if there's no candidates, we then could let the caller terminate input stream.

candidate is defined as:

-- type Candidate = (String, [String])

The first part is the prefix already matched, second part is the substring of the candidates with prefix (first) removed;

result is aggregated by a Writer Monad;
return value could be either one of:

data MatchStatus = More    -- we have candidates, keep growing input stream;
                 | Done    -- No more candidate, terminate input
                   deriving Show

The monadic code makes the logic quite handy.

incr c = do
  (matched, rems) <- br="" get="">  let rems' = fmap tail . filter (\xs -> if null xs then False else if (head xs) /= c then False else True) $ rems
      matched' = c:matched
  put (matched', rems')
  when (any null rems') ( tell (Seq.singleton (reverse matched')) )
  return $! if null rems' then Done else More<- br="" get="">
<- br="" get=""><- br="" get="">
-- dict1 = ["xde", "xd", "efgh"]
-- runIdentity . runRWST (incr 'x' >> incr 'd' >> incr 'e' >> incr 'f') 0 $ ("", dict1)

--   (Done,("fedx",[]),fromList ["xd","xde"])

C interview quiz: how to reverse a string

So I heard someone was asked how to reverse a C string maybe in a coding interview. seems pretty easy? At least it's very easy come into some solution like this:

char* reverse(char* s, int n)
{
 int i;
 char ch;

 for (i = 0; i < n / 2; i++) {
   ch = s[i];
   s[i] = s[n - i -1];
   s[n -i - 1] = ch;
 }

 return s;
}

Well, this might can pass the coding test, for a serious C programmer, I don't think that's the right solution. The problem is as a low level C programmer, you need think like machines, machines do terribly when handling with bytes, but much better with words. Keep this in mind, we could find a much better solution (even it's longer):

static inline void swap64(long long* x, long long* y)
{
 long long t = *x;
 *x = *y;
 *y = t;
}

static inline void swap32(int* x, int* y)
{
 int t = *x;
 *x = *y;
 *y = t;
}

static inline void swap16(short* x, short* y)
{
 short t = *x;
 *x = *y;
 *y = t;
}

static inline void swap8(char* x, char* y)
{
 char t = *x;
 *x = *y;
 *y = t;
}

static inline char* fastrev(char* s, int i, int j)
{
 while (i + 16 <= j) {
   long long *l1 = (long long*)(s+i);
   long long *l2 = (long long*)(s+j-8);
   *l1 = bswap_64(*l1);
   *l2 = bswap_64(*l2);
   swap64(l1, l2);
   i += 8;
   j -= 8;
 }
 while(i + 8 <= j) {
   int* i1 = (int*)(s+i);
   int* i2 = (int*)(s+j-4);
   *i1 = bswap_32(*i1);
   *i2 = bswap_32(*i2);
   swap32(i1, i2);
   i += 4;
   j -= 4;
 }
 while(i + 4 <= j) {
   short* i1 = (short*)(s+i);
   short* i2 = (short*)(s+j-2);
   *i1 = bswap_16(*i1);
   *i2 = bswap_16(*i2);
   swap16(i1, i2);
   i += 2;
   j -= 2;
 }
 while (i < j) {
   char* c1 = s+i;
   char* c2 = s+j-1;
   swap8(c1, c2);
   i++;
   j--;
 }

 return s;
}

char* reverse(char* s, int n)
{
 return fastrev(s, 0, n);
}

(I didn't use swap macro with the well-known `xor` trick, because `xor` on non-words doesn't necessarily faster).

The 2nd solution is 3 times faster on my computer when revering 10^6 bytes string repeated 1000 times (have to do this, otherwise the bottle neck is I/O). Main function:

int main(int argc, char* argv[])
{
 char* line;
 size_t n;
 ssize_t k;
 int loop, loopcnt = 1000;
 int nt;

 scanf("%d\n", &nt);

 while(nt--) {
   k = getline(&line, &n, stdin);
   line[k-1] = '\0';
   loop = loopcnt;
   while(loop--) {
     reverse(line, k-1);
   }
   printf("%s\n", reverse(line, k-1));
 }

 free(line);
 return 0;
}

Timing Result:

[wangbj@nuc tmp]$ ls -l /tmp/i5.txt   
-rw-r--r-- 1 wangbj users 1000003 Mar 19 00:43 /tmp/i5.txt
[wangbj@nuc tmp]$ time cat /tmp/i5.txt | ./rev > /dev/null       

real    0m0.637s
user    0m0.621s
sys     0m0.015s
[wangbj@nuc tmp]$ time cat /tmp/i5.txt | ./rev2 > /dev/null

real    0m0.206s
user    0m0.197s
sys     0m0.015s

While there are so much big tech asking algorithm questions (problem is 90% of exactly the same questions can be found online with answers..), reverse a string might not a laughable problem at all!

Binary tree right side view with Haskell

data BTree a = Leaf | Branch a !(BTree a) !(BTree a) deriving Show

expand Leaf = return (mempty, [])
expand (Branch a l r) = return (Alt (Just a), [r, l])
rightSideView = mapM (getAlt . mconcat) . init . levels . runIdentity . unfoldTreeM_BF expand

My thoughts on design patterns

In many programming languages design pattern is a hot topic and a must do; without mastering various deisng patterns one seems barely mastered the programming language. My take is if design patterns is really essential, why it isn't built as part of the programming language, and enforce everyone to use it? After all, it's good to encourage good behaviors than bad.

In Functional Programming language, design pattern isn't frequently talked about, as it has quite different programming paradigm, For the reason I listed, the essence of design pattern (I wouldn't like to name it, the word design is much more prefered) is built into the programming languge.

I woud like to elaborate more reason behind that, however, some expert already did a much better job (Yet I'm just a beginner).

http://blog.ezyang.com/2010/05/design-patterns-in-haskel/

Why you should learn functional programming

The first time I came across functional programming is from wikipedia accidentally, for a quick sort example:

quicksort [] = []
quicksort (x:xs) = quicksort left ++ [x] ++ quicksort right
    where left = filter (<= x) xs
          right = filter (> x) xs

I was amazed (even today) by its simplicity, and come into the problem deeply without distracted by any kind of implementation details. before that I've spent quit sometime to understand quick sort, mainly by reading text book Introduction to Algorithms (It's a great book). However, it was the Haskell version helped me understand the algorithm deeply in mind.

Another example is finding /nth/ maximum element of an list, this is very similar to quicksort, except we can discard either left or right:

kth n (x:xs)
  | n <= len = kth n right
  | n == 1 + len = x
  | otherwise = kth (n - len - 1) left
    where left = filter (<= x) xs
          right = filter (> x) xs
          len = length right

Thus it requires less time complexity (average time complexity is O(n)). And I think it's more easier for understanding the problem.

Netboot EFI Linux (diskless) with qemu/ovmf/grub2

. prerequiresites:

- DHCP/TFTP, so that you can netboot with PXE;

1) create an standalone grub efi image:

  sudo grub2-mkstandalone -d /usr/lib/grub/x86_64-efi/ -O x86_64-efi --fonts="unicode" -o grub2.efi  /boot/grub/grub.cfg=/tftpboot/netgrub.cfg

netgrub.cfg is something like:

 set timeout=5

# linux (tftp)/vmlinuz
menuentry 'Linux diskless' --class gentoo --class gnu-linux --class gnu --class os {
        insmod net
        insmod efinet
        insmod tftp
        insmod http
        insmod gzio
        insmod part_gpt

        insmod efi_gop
        insmod efi_uga


        set net_default_server=192.168.1.1

        net_add_addr eno0 efinet0 192.168.1.81

        echo 'Network status: '
        net_ls_cards
        net_ls_addr
        net_ls_routes

        echo 'Loading Linux ...'
        linux (tftp)/vmlinuz root=/dev/nfs rw nfsroot=192.168.1.11:/exports/nfs/gentoo ip=on
}

and let DHCP server send grub2.efi (filename=grub2.efi) to our client (192.168.1.81).

2) build OVMF from EDK2.

3) running a recent qemu (>= 1.6.0)

  sudo qemu-system-x86_64 -enable-kvm -m 2048 -vga qxl -L . -bios OVMF.fd -device virtio-net-pci,romfile=,netdev=mynet0,mac=00:12:34:56:78:9a -netdev tap,script=/etc/qemu/qemu-ifup,id=mynet0 -vnc :30

- Because we use macaddr above, need make sure DHCP server configure macaddr from above to ip address 192.168.1.81.
- Make sure romfile is empty, which will use OVMF virtio-net-pci driver instead of iPXE virtio-net-pci driver (in my case it runs into error: failure at drivers/bus/virtio-ring.c:69)

4) vncview :30 and check status.

Note:

a) In theory this can also boot a box supports PXE into EFI mode (diskless), so that you don't have to create a EFI boot disk (I don't like this way).

dmesg from booted linux with above method:

http://pastebin.com/84xEtwMS

Install Debian testing/lenny into Qemu MIPS Malta board

Install Debian testing/lenny into Qemu MIPS Malta board

1. Install debian (testing/lenny) with qemu-system-mipsel/malta.

qemu-img create -f qcow2 debian-mipsel.img 1G
lftp -c mirror ftp://ftp.fi.debian.org/debian/dists/testing/main/installer-mipsel/current/images/malta/netboot/
cd netboot
sudo qemu-system-mipsel -kernel vmlinux-2.6.26-1-4kc-malta -initrd initrd.gz -append 'console=ttyS0' -nographic -serial stdio -net nic -net tap -hda /path/to/debian-mipsel.img

Fellow the standard debian installation process and finish install debian (standard system) to debian-mipsel.img.
Note: Qemu emulation for architecture different from the host side is very slow, be patient during the installation. this maybe take more than 1 hrs depending on the host's hardware configuration.

2. Reboot to the debian-mipsel system we installed right now, rsyncing the entire file system if neccessary (in case of nfsroot). Before that, we'd better to build our own kernel. the qemu simulates MIPS MALTA board with the following hardware:

The Malta emulation supports the following devices:

* - Core board with MIPS 24Kf CPU and Galileo system controller
* - PIIX4 PCI/USB/SMbus controller
* - The Multi-I/O chip's serial device
* - PCnet32 PCI network card
* - Malta FPGA serial device
* - Cirrus VGA graphics card

compile kernel for mips malta board:

cd linux-2.6
make ARCH=mips malta_defconfig

Tune the defconfig if needed:

make ARCH=mips menuconfig
make ARCH=mips CROSS_COMPILE=mipsel-unknown-linux-gnu- -j3

After we have own own kernel, we could use this kernel to boot with our filesystem we installed right now:

sudo qemu-system-mipsel -kernel vmlinux -append 'root=/dev/hda1 ro console=ttyS0' -nographic -serial stdio -net nic -net tap -hda /path/to/debian-mipsel.img -boot c

Login into the new system, prepare to exports our filesystem using rsync:

aptitude update
aptitude install rsync

Since the `/' filesystem contains some virtual filesystem like /dev, /proc, /sys, we must avoid syncing these directory, and the simplest way I know is:

Mount the root filesystem to other directory:

mount /dev/hda1 /mnt

Mount other directory like /boot to the new mounted root (/mnt) if neccessary.

On a other machine, assume it's IP address is 192.168.2.104:

sudo mkdir -p /exports/nfs/diskless/debian-mipsel # on 192.168.2.104, choose a directory you prefer.

On our Qemu target:

cd /mnt
rsync -av * root@192.168.2.104:/exports/nfs/diskless/debian-mipsel/ # sync the entire filesystem to the remote machine.

Note 1: We use qemu to `cheat' for a filesystem installed with debian, in a simular way we could also have a rootfs for other architecture.
Note 2: Other than Debian, gentoo stage3 is also a good choice, and you don't have to install (with qemu-system-xxx), but surely you don't want to `emerge' in a qemu simluated target system ;-)
Note 3: If you have a debian host environment, the simplest way to install a rootfs might be use debootstrap, you can also debootstrap a filesystem for other architecture, please refer to `man debootstrap' for details.

3. Using Qemu/MALTA with nfsroot. Before that we have to modify the something in the nfsroot filesystem, ie:

cd /exports/nfs/diskless/debian-mipsel

vim etc/fstab # comment stuff like /dev/hda1 etc..
vim etc/inittab # comment tty* since we don't use any tty and uncomment ttyS0 and use a proper bitrate because our terminal is on ttyS0

cd /path/to/linux-2.6
sudo qemu-system-mipsel -kernel vmlinux -append 'root=/dev/nfs rw nfsroot=192.168.2.104:/exports/nfs/diskless/debian-mipsel ip=dhcp console=ttyS0' -nographic -serial stdio -net nic -net tap

Note: to use this, make sure DHCP and NFS server is configured properly, please refer to this document: http://wangbj.blogspot.com/2009/03/using-qemu-to-simulate-armintegratorcp.html or /usr/src/linux/Documentation/filesystem/nfsroot.txt (the best).

Using Qemu to simulate ARM/IntegratorCP board

Using Qemu to simulate ARM/IntegratorCP board

1. Qemu/u-boot setup.

Get a recent copy of u-boot sources, build for integrator board.

cd u-boot-2009.01
make integratorcp_config
make ARCH=arm CROSS_COMPILE=arm-unknown-linux-gnueabi-

Now we could use qemu to run u-boot binary. ie:

qemu-system-arm -kernel u-boot -net nic -net tap -nographic -serial stdio

Note: we should have -net nic -net tap support, otherwise u-boot will not able to do network traffic.

2. Compile a kernel for IntegratorCP board.

cd linux-2.6
make ARCH=arm integrator_defconfig

tune settings to fit the IntergratorCP board, Qemu simulates this board with (from /usr/share/doc/qemu-xxx):

Use the executable 'qemu-system-arm' to simulate a ARM machine. The ARM Integrator/CP board is emulated with the following devices:

* - ARM926E, ARM1026E, ARM946E, ARM1136 or Cortex-A8 CPU
* - Two PL011 UARTs
* - SMC 91c111 Ethernet adapter
* - PL110 LCD controller
* - PL050 KMI with PS/2 keyboard and mouse.
* - PL181 MultiMedia Card Interface with SD card.

Note: ARM926E is an ARMv5te architecture.

make ARCH=arm menuconfig
make ARCH=arm CROSS_COMPILE=arm-unknown-linux-gnueabi- -j3
make ARCH=arm CROSS_COMPILE=arm-unknown-linux-gnueabi- uImage

3. Qemu, u-boot, and kernel together.

copy our uImage to tftp server, configure an tftp server first if you don't have one.

cp arch/arm/boot/uImage /tftpboot/uImage
/etc/init.d/in.tftpd start

run qemu with u-boot

qemu-system-arm -kernel ~/build/u-boot/u-boot-2009.01/u-boot -net nic -net tap -nographic -serial stdio

and then under u-boot prompt:

Integrator-CP # setenv ipaddr 10.0.0.21 # board ip address
Integrator-CP # setenv server 10.0.0.207 # tftp server ipaddress
Integrator-CP # setenv bootargs 'root=/dev/nfs rw nfsroot=10.0.0.207:/exports/nfs/diskless/gentoo-arm ip=dhcp console=ttyAMA0'
Integrator-CP # tftp 400000 uImage
Integrator-CP # bootm 400000

Note 1: I'm using nfs-root/diskless system, to use this, you have to configure a nfs server first, the corresponding /etc/exports file should be something like:

# /etc/exports: NFS file systems being exported. See exports(5).

/exports/nfs/diskless 10.0.0.0/255.255.255.0(rw,no_root_squash,no_subtree_check)

Note 2: /exports/nfs/diskless/gentoo-arm is a filesystem from gentoo/arm stage3 tarball, since we're using IP kernel level autoconfigration, so we have to tell the userspace program do not to configure ip anymore, under gentoo system, this could be done by (/etc/conf.d/net):

config_eth0=( "null" );

Change /etc/inittab so that init could start from ttyAMA0 with proper bitrate. you can also uncomment tty0-tty6 since we don't use them.

By default the init program is also trying to mount /etc/fstab entries, we could also uncomment unneccessary entries to avoid mount errors/warnings.

Note 3: The cross-toolchain is built by gentoo's crossdev by:

crossdev -S --ex-gdb -t arm-unknown-linux-gnueabi

Using kvm/qemu with virtio

Using kvm/qemu with virtio

Since kernel 2.6.25, linux kernel have virtio support, virtio is different
with full device virtualization, it doesn't have to behave as the realhardware,
the guest driver actually knows it is running under a virtual environment, thus
in theory it's should be faster and more efficient than the full virtualized
hardware.

Newer qemu (svn version, not 0.9.1) have virtio support, recent kvm also have
virtio support.

In order to utilize virtio, you will need a recent kernel (> 2.6.25) with
virtio (variants) support, and a recent qemu/kvm.

How to use Virtio

* Get kvm version >= 60 (or recent svn verstion qemu)
* Get Linux kernel with virtio drivers for the guest

Get Kernel >= 2.6.25 and activate (modules should also work, but take care of initramdisk)
+

CONFIG_VIRTIO_PCI=y (Virtualization -> PCI driver for virtio devices)
+

CONFIG_VIRTIO_BALLOON=y (Virtualization -> Virtio balloon driver)
+

CONFIG_VIRTIO_BLK=y (Device Drivers -> Block -> Virtio block driver)
+

CONFIG_VIRTIO_NET=y (Device Drivers -> Network device support -> Virtio network driver)
+ CONFIG_VIRTIO=y (automatically selected)
+ CONFIG_VIRTIO_RING=y (automatically selected)
+ you can safely disable SATA/SCSI and also all other nic drivers if you only use VIRTIO (disk/nic)

As an alternative one can use a standard guest kernel for the guest > 2.6.18 and make use sync backward compatibility option

Backport and instructions can be found in kvm-guest-drivers-linux.git
* Use model=virtio for the network devices and if=virtio for disk
Example

qemu/x86_64-softmmu/qemu-system-x86_64 -boot c -drive file=/images/xpbase.qcow2,if=virtio,boot=on -m 384 -net nic,model=virtio -net tap,script=/etc/kvm/qemu-ifup

Another Example of using virtio:

I use qemu/kvm to install a distro like arch linux, I can't use virtio at the
begining because the official arch linux kernel (archlinux 2009.2, kernel
2.6.28.5-2) can not boot via virtio devices. so:

qemu-img create -f qcow2 arch-x86.img 1G
sudo kvm -cdrom archlinux-2009.02-core-x86_64.iso -hda arch-x86.img -boot 'd' -net nic,model=e1000 -net tap

NOTE: root partition mount point in /etc/fstab should be UUID or LABEL based
because later the device interface (sda->vda) might be changed. ie:

LABEL=/arch / ext4 noatime 0 0

after finishing archlinux installation, we could use our own kernel to utilize
virtio, ie:

cd ~/linux/linux-2.6

build a kernel with VIRTIO support.

sudo kvm -kernel arch/i386/boot/bzImage -append 'root=/dev/vd1 ro console=ttyS0,115200' -drive file=~/arch-x86.img,if=virtio,boot=on -m 256 -net nic,model=virtio -net tap

refs:
http://kvm.qumranet.com/kvmwiki/Virtio
http://wiki.libvirt.org/page/Virtio

Gentoo QEMU/KVM ethernet bridging nano HOWTO

Qemu could use tun/tap to emulate bridged network, so the guest could have a real ip as host. ie:

[code]qemu -net nic -net tap[/code]

or

[code]kvm -net nic -net tap[/code]

Under gentoo, in order to use that, we have to:

* kernel requirements:

CONFIG_BRIDGE, CONFIG_TUN must be included (y/m) CONFIG_KVM_INTEL/CONFIG_KVM_AMD must be selected in order to use kvm

CONFIG_IP_PNP and CONFIG_ROOT_NFS must be included to use nfsroot/diskless mounted filesystem. Host side NIC driver must also be compiled into kernel (y).

* user space application:

bridge-utils, qemu/kvm

Networking interface layout:

br0: bridge interface, binded with real IP address for network access. eth0: interface of br0, no IP. tapX: interface of guest, no IP.

NOTE: switch interfaces don't have an IP address.

Network configuration in gentoo:

*) make sure NetworkManager/dhcdbd is not started, network interface must not be managed by NetworkManager. ie:

[code]

$ cd /etc/init.d/ $ ln -s net.lo net.eth0 $ ln -s net.lo net.br0 $ rc-update add net.eth0 default $ rc-update add net.br0 default

[/code]

*) /etc/conf.d/net configration, ie:

[code]

bridge_br0="eth0" config_br0=("dhcp") config_eth0=("null")

[/code]

You have to insert some modules if neccessary like:

[code]

$ modprobe tun kvm_amd

[/code]

Start using qemu/kvm:

[code]

$ kvm -kernel bzImage -append "root=/dev/nfs rw nfsroot=192.168.2.xxx:/home/gentoo-x86 ip=on" -net nic,model=e1000 -net tap

[/code]

Note: kvm have it's own network startup/stop scripts /etc/kvm/kvm-if{up,down} in gentoo, if you're using qemu, you have to write your own /etc/qemu-if{up,down} scripts, just copying /etc/kvm/kvm-if{up,down} it's essential.

.refs:

http://www.linuxfoundation.org/en/Net:Bridge gentoo's /etc/conf.d/net.example

1st post of my blog ;)

very happy to become a blogger ;-)