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).