codebytez

Prime algorithm in assembler

2011-10-16T21:36:00.000-04:00

One of the greatest strengths of assembly language is the extreme compactness of code. Digging though my old files I found this gem that prints all prime numbers under 2^32. The COM file size is 165 bytes. That's right! You could memorize the bytes if you wanted to and hand assemble it.

The algorithm is not sieve (which would create 2^31 locations and strike off multiples of primes). Rather this is a space optimized algorithm that repeatedly divides each number n from 2 to sqrt(n) to determine if a number is prime. This algorithm uses no additional storage than the 165 bytes to hold the code.

.model tiny
.code
.386
org 100h
start:
main proc
xor eax,eax
mov al,3
@@m2:
call isprime
jnc @@m1
call printdword
call printcrlf
@@m1:
inc eax
jnz @@m2

mov ax,4c00h
int 21h
main endp

isprime proc
pushad
mov esi,eax ; save number
xor ecx,ecx
mov ebx,ecx
mov edx,ecx ; edx = 0
call sqrt
mov cx,ax ; save sqrt
mov bl,2 ; ebx = 2 (divisor)
@@i2:
mov eax,esi ; restore number
cmp ecx,ebx ; is sqrt < divisor?
jl @@i4 ; yes, no need to divide any more
div ebx
or edx,edx
jz @@i1
xor edx,edx
inc ebx
jnz @@i2
@@i4:
stc
jmp @@i3
@@i1:
clc
@@i3:
popad
ret
isprime endp

sqrt proc
push ebx
push ecx

xor ecx,ecx
mov ebx,ecx
@@s2:
inc ebx
sub eax,ebx
jl @@s1
inc cx
inc ebx
jmp @@s2
@@s1:
mov ax,cx

pop ecx
pop ebx
ret
sqrt endp

printdword proc
pushad
xor ebx,ebx
mov cx,bx
mov bl,10
@@p1:
xor edx,edx
div ebx
push dx
inc cx
or eax,eax
jnz @@p1
@@p2:
pop ax
add al,'0'
mov dl,al
mov ah,02
int 21h
loop @@p2

popad
ret
printdword endp

printcrlf proc

pusha

mov dl,13

mov ah,02

int 21h

mov dl,10

mov ah,2

int 21h

popa

ret

printcrlf endp

end start

Fix for NFS v4 inverse squashing

2011-08-16T23:06:00.000-04:00

Due to an NFS Bug, when ZFS is shared over NFS4 on the client side all files will appear owned by nobody:nogroup. If idmapd is not set it will be 4294967294: 4294967294.

The client can still read and write and the files will appear normally on the server. Chown will fail, which means you cannot run VM images off this share.

Mounting this with nfs option vers=3 in /etc/fstab is the only workaround until the bug is fixed.

Native (non-FUSE) ZFS on linux

2011-08-16T19:22:00.001-04:00

Thanks to Darik Horn, we can have native ZFS on linux. Instructions here. Works on natty, but may have issues on Lucid.

Note:

Preemptible kernels not supported. This should be OK for servers.
The ppa does not actually cover all dependencies. I had to figure out zlib1g-dev and uuid-dev


sudo add-apt-repository ppa:dajhorn/zfs
sudo apt-get update
sudo apt-get install zlib1g-dev uuid-dev ubuntu-zfs

If you get the following error, the build is unsuccessful:


Failed to load ZFS module stack.
Load the module manually by running 'insmod /zfs.ko' as root.

To determine missing dependencies:


cd /var/lib/dkms/zfs/*/build
./configure. # Error message will tell you what dependencies are missing

make

make install

Repeat or other directories under dkms if they had errors. If you get any error regarding unknown symbol or module format, you have booted the wrong kernel.

Migrating running VMs using virsh

2011-07-27T20:39:00.004-04:00

Prerequisites:

All VM images are mounted on a shared location, for example: /vmimages. If any images are qcow2 images with a backing file, those files also need to be present on shared locations.
kvm-pxe needs to be installed. If not, the migration occurs, but the VM is suspended at the destination.
Optional: If you want to be able to do this from scripts, setup ssh keys so you don't need to enter passwords

Migrate with the following command as root on the source host:


virsh migrate --live vmname qemu+ssh://destination.host/system

or if you are not on source, you can first connect to the source host


virsh --connect qemu://source.host/system migrate --live vmname \
      qemu+ssh://destination.host/system

Read only root on VMs

2011-07-03T11:52:00.001-04:00

Follow the instructions from here: https://help.ubuntu.com/community/aufsRootFileSystemOnUsbFlash

disable app-armor on dhclient (otherwise networking will fail)

sudo aa-complain /etc/apparmor.d/sbin.dhclient

edit /etc/grub.d/00_header to not show menu on unclean close:


# if [ "\${recordfail}" = 1 ]
# then
set timeout=-1
#else
set timeout=${2}
#fi

Optionally, you can choose to not unmount NFS paritions, etc in /etc/rc0.d/S35networking and S40unmountfs

Exporting ZFS filesystem over NFS

2011-06-30T20:24:00.010-04:00

First you need to install nfs-kernel-server. You also need a later kernel: 2.6.35 or better

Install zfs native (or zfs-fuse):

sudo add-apt-repository ppa:dajhorn/zfs
sudo apt-get update
sudo apt-get install ubuntu-zfs

By default NFS sharing is off. To export a zfs filesystem, say zfs/home:

#Setup shared FS
zfs create -o compression=on -o atime=off -o sharesmb=on zfs/home

#export RO
zfs set sharenfs=ro zfs/home

#stop exporting. Also for next command to take effect
zfs set sharenfs=off zfs/home  

# export RW, fsid needs to be unique per filesystem
zfs set \
 sharenfs=10.1.1.0/24:rw,fsid=100,no_subtree_check,async,no_root_squash zfs/home

# add this to /etc/rc.local
zfs share -a

#To mount from OSX use the following command. -P option is for secure (<1024) ports
mount_nfs -P 10.1.1.1:/zfs/home/${USER} /mnt/home

Later invocations override earlier, so to export RW to only one host and RO to others:

zfs set sharenfs=off zfs/backup
zfs set sharenfs=10.0.0.0/8:ro,no_subtree_check,async,no_root_squash zfs/backup
zfs set sharenfs=10.1.1.1:rw,no_subtree_check,async,no_root_squash zfs/backup

The host writing the backup is 10.1.1.1 and will get read/write access. The rest will get read only access.

Note: Setting the mountpoint property of a ZFS dataset to anything other than the default pool/dataset will cause it to be exported with all_squash. Do not change the mountpoint if you want to NFS share a dataset

If you are getting a lot of stale NFS handles, the IO requests are timing out before they can be serviced due to heavy IO load. Mount your NFS shares using these options (example fstab entry):


server:/zfs/dataset    /mnt       nfs     defaults,timeo=20,retrans=5,rsize=8192,wsize=8192,intr    0       0

The timeo to 2 seconds from default of 0.7 seconds is the most important attribute.

Minimal graphical Ubuntu install

2011-06-03T22:57:00.003-04:00

#!/bin/sh
# Minimal Ubuntu Graphical install
sudo apt-get install gnome-panel gdm gnome-terminal network-manager-gnome \
network-manager gnome-power-manager chromium-browser \
ubuntu-artwork libaudiofile0 flashplugin-installer

Time machine on a network drive

2011-05-18T11:52:00.002-04:00

A very good explanation of how to use a network drive for time machine. However, there is no need to reboot your OS X once you change the setting. I also make a shell script to create a time machine compatible network drive using all the above steps automatically. Enjoy!

#!/bin/sh
# Create a time machine compatible network drive 
# (c) codebytez.blogspot.com
NETLOC=$1
if [ -z "$1" ]
then
        echo Usage: $0 /Volumes/network_volume \[size\]
        exit 1
fi

if [ -z "$2" ]
then
        SIZE=100g
else
        SIZE=$2
fi

defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1
MAC=`ifconfig en0 | grep ether | perl -lne 'print @f if (@f = /[0-9a-f]{2}/g)'`
HOST=`echo $HOSTNAME | perl -F'\.' -lane 'print $F[0]'`
VOL=${HOST}_${MAC}.sparsebundle
hdiutil create -size $SIZE -fs HFS+J -volname "Time Machine" $VOL
rsync -aE $VOL $NETLOC
rm -rf $VOL
echo Created $NETLOC/$VOL
echo Select as backup disk in Time Machine Preferences

Gates' Law

2005-08-22T20:35:00.000-04:00

"The speed of processors doubles every 18 months" -- Moore's law

"The speed of software halves every 18 months" -- Gates' law

I'm uncertain if Gates' Law was meant as a joke, but I did notice that Lotus 123 ran at about the same speed on an old 80286 as excel runs on your modern PC.

Some of it is certainly because newer hardware makes more things possible, such as the graphical interface and tooltips. Newer software does try to be sexier by doing flashy things such as the talking paperclip. This causes a tendency for the software to bloat to the point of saturation, i.e. until it performs at barely acceptable speeds.

But application programming seems to get worse with faster processors. Even with more memory, faster disks and multiple CPUs, your average web application runs slower. Is it possible that the faster hardware has made us worse programmers?

In the old days, to set a register to the value 1, even an average assembly programmer would do something like this:


xor ax,ax
inc ax

rather than:mov ax,1 The reason was simple. The programmer knew the latter alternative required access to memory, which is generally ten times slower than accessing registers. Modern programming languages hide details like this from the programmer, so he does not know the real cost of bad programming.

With garbage collection now part of many languages, we see many applications having to deal with memory problems. Why? Because the average programmer does not know the cost of object creation since he does not have to deal with cleanup.

For example in C++ you would do this:


// case 1: allocate on stack
int a = 1;
// other code
DirEnt de;


// case 2: allocate on heap
int *a = new int;
// other code
DirEnt *de = new DirEnt;

In the first case, the variable is allocated on the stack and disappears when execution moves outside the scope. The compiler calculates the required space at compile time and generates a simple instruction such as:


sub bp, 2+248        ; int is 2 bytes, dirent is 248 bytes

In the second case, the variable is allocated on the heap, which is a comparatively slow operation. First, a check is made for sufficient free memory. The heap is then searched for contiguous free memory of the desired size and then initialized. The region is marked "in-use" and a pointer to the memory is returned. If there is no contiguous memory, the system may choose to compact/defragment memory.

Two characteristics of the heap vs stack in the above example are that the memory allocation routine would need to be called twice, since the compiler has no way of knowing if the allocations can be combined given there is other code between the two allocations. Also while each thread has its own stack, multiple threads compete for the same heap allocator (except a small portion of thread local heap, which is not really a factor in large memory footprints).

In languages such as Java you cannot really allocate anything except primitives on the stack even if you don't intend to use them beyond the immediate scope. This represents a big load on the memory management system. Objects that properly belong on the stack now crowd the heap, putting a strain on the entire system.

"But how slow can memory allocation be? Isn't memory accessible in nanoseconds?"

In most operating systems, for practically all applications, the memory allocated is virtual memory from the theoretical address space rather than actual physical memory. This implies that you need huge amounts of memory to never have a page fault. Page faults generally work at the speed of storage, which is measured in milliseconds unless you have a solid state disk.

With fragmented memory and a large memory footprint, we end up dealing with multiple page faults, causing the system to thrash. This is especially apparent in multi-threaded programming where the locality of reference principle does not save you from multiple simultaneous page faults.

Unfortunately, even a programmer who is aware of these issues is helpless if the language itself is restrictive. What java could have done is allocate objects on the stack if they are not passed to other methods.


// new translates to alloc on stack
DirEnt e = new DirEnt(".");
e.list();


// passed to other class, alloc on heap
DirEnt e = new DirEnt("..");
stack.add(e);

Theoretically, the java compiler could follow the object in the call tree and see if anyone retains a reference to it, but that would render the compiler prohibitively slow and perhaps incorrect if reflection is used.

It is therefore up to the programmer to not trust the much touted features of any language (or any technology) without sufficient experience. Failing which, your programs end up testifying for Gates' Law.

The problem with DTDs and schemas

2005-08-08T06:10:00.000-04:00

Many would agree with me that XML is too bulky for its intended purposes. But would you say the same about HTML? probably not.

And why should that be? Isnt XML a glorified, genericized HTML? Despite what the historians say about both being children of SGML, the fact of the matter is that XML only came into being after the spectacular success of HTML and if you remember the original marketing hype, it was all about how web documents would be XML in the future and how they would be rendered or used differently by other consumers.

One of the important factors for the failure of XML is the reliance on DTDs and schemas. HTML succeeded simply because there was no predefined format for any given web page. Browsers ignored what they did not understand, and did the best with what they could. HTML was a language that browsers and servers spoke. There was a syntax, but no schema. The schema came later, long after HTML was refined through multi-year, multi-user testing.

Your typical enterprise application does not have that luxury.

Consider this snippet of XML:


<orders>
<date>Dec-24</date>
 <order>
  <customer>Joe Schlubbs</customer>
  <customer-address>10 drowning st</customer-address>
  <customer-city>London</customer-city>
  <order-line>
     <quantity>100</quantity>
     <item-number>J-350</item-number>
     <item-name>extra large onions</item-name>
     <price-per-item>12.35</price-per-item>
     <!-- other fields -->
  </order-line>
 </order>
 <order>
   <customer>Joe Schlubbs</customer>
   <customer-address>10 drowning st</customer-address>
   <customer-city>London</customer-city>
   <order-line>
      <quantity>100</quantity>
      <item-number>J-007</item-number>
      <item-name>extra large bullets</item-name>
      <price-per-item>1.99</price-per-item>
   </order-line>
  </order>
</orders>

Lets assume we are writing an application that needs a list of all customers who spent more than a thousand bucks in the last month so we could mail them some coupons.

An SQL programmer would simply do a SELECT customer, sum(price*qty) group by customer having sum(price*qty) > 1000. The typical XML programmer on the other hand, has to get all orders for the last month and skim through large amounts of text to produce the necessary results. Depending on the number of tags, close to 90 percent of the input will be useless to the application.

Could the server simply omit the unnecessary data? Probably not, because the tags are not optional. Thats because when they designed the XML, they could not forsee that business would be so good that they would send out coupons.

It is simply impossible to forsee all possible future needs, so to really future-proof your schema, you would need to make nearly every tag optional. This pretty much void the purpose of a schema.

A schema where every tag is optional could still useful, to describe what tags go where and what they mean -- sort of like HTML.

Or you could just deal with the bulk.

Semaphores in assembler and java

2005-08-04T20:00:00.000-04:00

How do you implement a semaphore in assembler taking into account the fact that you may have multiple CPUs with each CPU possibly executing multiple threads of code at any time? We use the xchg instruction, which performs atomic exchange of its arguments.


;acquire semaphore
    xor     ax, ax      ; set AX to zero
L1:
    xchg    ax, sema    ; atomic test and set. sema = 0, ax = sema
    or      ax, ax      ; is the value we obtained from sema 0?
    jz      L1          ; yes, wait for someone to release semaphore
    dec     ax          ; no, we got the semaphore.
    xchg    ax, sema    ; decrease by one and store

;process stuff

; release semaphore
    xchg    ax, sema    ; sema value may have been changed by other threads
    inc     ax          ; bump to notify we have released it
    xchg    ax, sema    ; atomic store

This is why there is an atomic exchange instruction in many processors. An atomic test and set instruction is indispensable for a variety of systems programming, semaphores being one of them. On systems with multiple processors, you probably want to lock the bus before executing the xchg. The code becomes:


    lock xchg  ax, sema

In case you have forgotten, the lock instruction locks the memory bus for the duration of the next instruction, which ensures that another processor does not read or write to sema when we are writing to it. The sequence of instructions


L1:
    xchg    ax, sema
    or      ax, ax
    jz      L1

form an anti-pattern called "busy-waiting" and burns up CPU resources when waiting to acquire the semaphore. In real life systems programming, it is often replaced by a spin lock, (which is a "design pattern") A spin lock busy waits for a few instruction cycles and then goes to sleep. The idea behind this is that context switches are expensive, and for many operations, semaphores are held briefly enough that the majority of the time, the waiting thread acquires the semaphore without the added cost of a context switch.


;acquire semaphore
L0:
    mov     cx, 0800h    ; spin the test loop so many times ...
    xor     ax, ax       ; ... choose 1/2 cost of context switch and tweak
L1:
    xchg    ax, sema
    or      ax, ax
    jnz     L2           ; got the semaphore, go to update
    loop    L1           ; repeat till cx is zero
    call    monitor_wait ; context switch
    jmp     L0           ; need to retest after notify
L2:
    dec     ax
    xchg    ax, sema

As you can see this implementation is very efficient and wastes very few cycles. A semaphore variable needs to be initialized with the number of simultaneous threads that can access it. For a mutex (equivalent to java's synchronized) we set the value to 1. The Linux kernel approaches the problem in a similar manner (albeit in C). The java equivalent looks like this:


synchronized(lock) // sema is an invisible variable inside object lock
{                  // sema acquired if you get here
    // process
}                  // release sema

Given that mutexes are nothing but special case of semaphores which have been in use in systems programming since antiquity and the relative simplicity of the machine code to implement them, its surprising that the monitorenter and monitorexit instructions were prohibitively expensive in early JVM implementations.

SEXML

2005-08-03T20:01:00.000-04:00

XML has the unfortunate side effect of being bulky. While bulk is good for the large intestine, its pretty much useless in computing. Which is why I devised SEXML. That's Simple Elemental XML. This is how it was derived: First, we get rid of attributes. What good are attributes for? They can easily be replaced by elements:

<order qty="12" price="13.5" brokerage="15%">
<order-type>buy</order-type>
<effective-time>market-close</effective-time>
</order>

can be rewritten as:

<order>
<qty>12</qty>
<price>13.5</price>
<brokerage>15%</brokerage>
<order-type>buy</order-type>
<effective-time>market-close</effective-time>
</order>

Next, we get rid of the irritating double tags. We accomplish this by turning <qty>12</qty> into qty<12>. The XML above becomes:

order<
qty<12>
price<13.5>
brokerage<15%>
order-type<buy>
effective-time<market-close>
>

To avoid confusion between XML and SEXML, and to enable embedding one in the other, lets replace <> with something else, say {} and while we are at it, put them on just one line:

order{qty{12}price{13.5}brokerage{15%}order-type{buy}effective-time{market-close}}

Perhaps we should separate the items with a comma, in case there are empty elements:

order{qty{12},price{13.5},brokerage{15%},order-type{buy},effective-time{market-close}}

There we go. If we had used parantheses, it would look too much like lisp and scare people off. Of course, you would put everything on one line only for use in URLs and the like.

The above has the same informational content of the XML above, but is much more compact and simpler to parse.

"But wait!" I hear screams. "What about schemas? What about the XML header? Character encoding? Entities?"

Nothing prevents you from using a schema. After all, it only describes structure and type information, not whether you use braces or angle brackets. Your schema just wont mention any attributes. As an exercise, try writing a schema for the above in SEXML.

As for the header, I dont see why you cant SEXML it up.

sexml {
 version{1.0}, encoding{utf-8},
 order{
     qty{12},price{13.5},brokerage{15%},order-type{buy},effective-time{market-close}
 }
}

Entities such as < can live as is.

I believe CDATA is quite unnecessary for SEXML and in fact, seems to be rarely used in XML. If you believe otherwise, please enlighten me.

/*
Since the original reason the comment in xml became the unweildy  to maintain compatibility with HTML, we can break it here to use C++ style comments. (Do you really need 4 chars to start a comment?)
*/

Lets see what it looks like with parantheses:

sexml (
 version(1.0), encoding(utf-8),
 order (
     qty(12),price(13.5),brokerage(15%),order-type(buy),effective-time(market-close)
 )
)

Guess the Lisp folks were right. Everything is a list of lists.

Assembling a home theatre PC

2005-02-01T01:09:00.000-05:00

I've wanted to build an AMD-64 for some time and I finally got started with the following parts. All items were located on Pricewatch. For some items, I did not automatically choose the cheapest vendor if the vendor had less than best ratings.

The general plan is to have a media box such as this.

Item	Price (w/. shipping)	Qty	Amount
AMD Athlon 64 939 3500+	$262.70	1	$262.70
Asus A8N SLI skt939	$194.00	1	$194.00
Ahanix D4	$229.58	1	$229.58
Zalman CNPS7000B-CU Cooler	$52.00	1	$52.00
Samsung PC3200 512MB	$82.00	2	$164.00
HITACHI 250GB SATA	$120.00	2	$240.00
Hauppage WinPVR-250	$128.00	1	$128.00
PCI express eVGA 6600 256MB	$129.00	1	$129.00
Arctic Silver 5	$6.00	1	$6.00

In addition, I bought some Everclear 95% grain alcohol from a liquor store for cleaning the computer parts. (Never use anything other than pure grain alcohol!)

In general, stores where shipping is free tend to ship via snail mail, so when looking at the price, factor that in.

Most items were packed perfectly. I was impressed with the packing of the hard drives and the Ahanix case. Other items were packaged adequately. The only exception was the Zalman cooler, which had some copper cooling blades bent because they did not seal the box. Copper is a soft metal and bends easily. the fan also looked very slightly scuffed. I straightened out the fins of the Zalman carefully. Then I verified that the fan ran silently and decided not to ask for an exchange.

First impressions:

The Ahanix D4 case looks like a stereo component device. The front metal face is about a quarter inch thick and feels luxurious. A hinged door that covers the 5.25 inch bays is held together by magnets and impresses quality. The entire case is aluminum and is very well constructed. The included power supply is silent and the case is designed to be kept cool. I wont review the case fully here since its been reviewed elsewhere, but suffice to say this is the best case you can get that holds a full ATX board and worth every penny. The D5 is cooler looking, but does not seem to have front USB/firewire ports and has an infra-red remote control sensor that is plugged to the USB port. I was not sure how it would work with lirc, so I did not buy it. The only negetive about this box is that smudges can be easily seen when you touch it.

The AMD Athlon 64 CPU looked like it had some extremely thin layer of gunk on it (returned item?) but I washed it with alcohol and it evaporated.

The Zalman CNPS7700-Cu cooler is a thing of beauty. It looks like a copper flower. The fan is large and silent. It comes with a fan control device, some thermal grease and various brackets. I cleaned its bottom with alcohol too.

The Asus A8N SLI deluxe motherboard truly deserves the Deluxe tag. It comes with every imaginable cable and fixture including a SATA fixture that allows you to plug in SATA drives at the back. The chipset fan is reasonably silent. The optical SPDIF out makes this board attractive to Home Theater projects. The 8 SATA RAID interfaces don't hurt either. The most important feature however, is Nvidia chipset, which has good Linux support from the vendor.

The Arctic silver 5 compound comes in a tiny syringe with a rubber dome top.

The Hitachi SATA hard drives run great, but are not as silent as their IBM counterparts (before IBM sold their hard drive division to Hitachi). It could be because I have 2 SATA drives in raid config (more on that later) and they make the seek sound simultaneously. I need to investigate into silencing the drives a bit more.

The eVGA GeForce 6600 with 256MB seems to be the fastest card at the price. This card comes with a shrouded fan. If you are a serious gamer (I'm not), its a good idea to go with the 6800 GT and get the Arctic cooler for it.

The RAM looked like ... RAM. The DIMMS had Copper heat spreaders on them and the word RAMSES printed. I complained to the vendor that he had sent me Ramses brand when I had requested Micron. He told me that the heat spreader was Ramses and the RAM was actually Samsung, which was allegedly better than Micron. I decided to keep the RAM if it ran stable. Fortunately, it did.

I had an old Plextor 712A DVD Writer, which I plugged into the system.

Hardware installation:

First, I removed the motherboard backplate provided by Ahanix. The items simply did not match my motherboard. I replaced it with one included by ASUS. The motherboard comes with a bracket and baseplate for the stock CPU cooler which I removed and then attached the baseplate that came with the Zalman cooler (using the nipples provided). I placed the motherboard on a flat surface and lifted the ZIF socket's lever and then aligned the CPU's golden triangle with the triangular mark on the ZIF socket. It fell into place easily. Placing the CPU on the ZIF socket and pushing the lever back to horizontal position is about the easiest thing to do.

Next, I took the Arctic silver 5 syringe and punctured the top with a pin and then squeezed about 1 and a half rice grain lengths on the CPU. I then gently lowered the Zalman cooler and aligned the screw holes with the nipples. Once the cooler sits on the CPU, a suction prevents you from easily picking up the cooler. but you can turn it slightly. I then screwed in the cooler tight alternating each screw.

I then lifted the motherboard with the CPU and cooler into the case and screwed it to the base. (Some folks prefer to attach the board first and then install the CPU and heatsink, but given that Arctic silver is slightly capacitative, I needed to be absolutely sure that not a single particle would fall onto the motherboard.)

Next, I installed the Samsung 512MBx2 PC3200 RAM which had copper heat spreaders on them into the appropriate banks (A1 and B1) to make best use of DDR feature.

Next, I installed the Hitachi SATA hard drives. You only get access to one side of the bay, so I screwed them in.

Next, I installed the PCI-Express eVGA card into the blue PCIe slot (as recommended if using a single slot)

Last, I connected all the case connections such as the power and hard drive LEDs

Linux Installation: Most folks would do well to just install the KnoppMyth distribution, but I'm a gentoo fanatic, so I downloaded the AMD64 ISO and installed gentoo and installed from stage3. Standard procedure with some hints for raid.

The only things I need to tell you are: For the sound card, I chose snd-intel8x0 (alsa driver) and for the net I chose forcedeth. Although I got nvidia's nvsound and nvnet to work after applying patches, I saw no advantage over standard kernel provided drivers. For the video, I emerge nvidia-kernel and added nvidia to modules.autoload. I managed to setup SPDIF using instructions here. I see that my SPDIF is properly setup:

# cat /proc/asound/pcm
00-00: Intel ICH : NVidia CK804 : playback 1 : capture 1
00-01: Intel ICH - MIC ADC : NVidia CK804 - MIC ADC : capture 1
00-02: Intel ICH - IEC958 : NVidia CK804 - IEC958 : playback 1

So I should be able to play it like this:

# mplayer -ao alsa:device=hw=0.2 mozart.mp3

But either my receiver has no support for it or I need to do something like this or this. So I went back to analog sound output.

The video was tricky. I finally managed to get the right xorg.conf file but I had two serious problems. The first, the cursor was a transparent square area with a cluster of black dots and second, the icons and text would disappear if the mouse went over them (or sometimes just by themselves). Fortunately, I found a patch on the internet for xorg and recompiled with it. All I did was emerge it, when it said 'Source unpacked' I pressed control+Z, applied the patch and resumed the job. I really should do something like this (go to bottom), but I'm guessing that they will have the bugfix in the next version anyway.

Its important to autoload the nvidia module or you get a "failure to load nvidia" error when you start X.

I struggled to setup the RAID, until I realized that the onboard RAID controllers are nothing more than a place in the BIOS to store your settings. Linux still sees the physical hard drives. Grub probes the BIOS, so it sees the real drives. You cannot install GRUB with fakeraid. The best option was to use mdadm and Linux software raid, which is just as fast if not faster. The utility mdadm was part of the installation cd, so I used it to setup the raid. The trick of course, is to set your boot partition as RAID-1, so that grub will load off it. Install grub in both partitions as shown here. I could probably have used the hardware using instructions here.

I got the Vacuum Fluorescent Display (part of the D4 case) working using these instructions. The VFD displays y with umlaut when the it tries to display a filled square for which I found a patch here

Wealth of info here

Noise

In general, I can constantly hear the constant whoosh of the fans at the back (I've disconnected one). The motherboard chip fan was the noisiest and I noticed that it was running at 8000+ RPM. I fixed the fan speed regulator that came with the CPU cooler and attached it to the motherboard chip fan and turned it fully down. The fan now runs at 4000+ RPM, but has almost negligible sound. The hard disks are silent unless there is activity, which I figure is the sound echoing off the case. The activity is occaisional even when compiling the kernel due to the 8MB caches.

Infrared

I purchased the parts off Radio Shack and soldered my own infra red receiver. I attached the IR sensor off a long wire, so I could squeeze it into the space provided by the D4 case (just above the HDD light left of the VFD).

Heat

In general, the CPU runs at 35C with the case open and 43C with the case closed at idle. On heavy load, it goes upto 55C. The motherboard temp and the case ambient temperature is generally about 5C and 15C below the CPU temperature.

Conclusion

All in all, I'm happy with the power and performance of this machine. I aim to install the arctic cooler for my VGA card and I also need to figure out how to reduce the noise of the fans and the hard disks.

Historical: Typewriter

2005-01-24T22:52:00.000-05:00

When I was a kid, I wrote this assembly program that would play with the VGA fonts (I wrote a whole bunch of programs that messed with the VGA fonts) One particular program that comes to mind is one that shifts the lines on the VGA font one scan line upward, making it look like it was typed on a typewriter with an errant key.



SCANLINES	equ	16
SHIFT		equ	 2

.model small
.code
	org	100h
main	proc
	mov	ax,1130h	; read char vector
	mov	bh,06		; 8*16 vga/mcga
	int	10h

	mov	ah,0		; read char
	int	16h
	cbw
	push	ax
	
		
	mov	cl,4		; map of offending char
	shl	ax,cl
	add	bp,ax
	add	bp,SHIFT	
	
	mov	cx,SCANLINES-SHIFT	; save char bitmap
	push	ds
	push	es		
	pop	ds
	pop	es
	mov	si,bp		; ds:si->original map
	lea	di,charmap	; es:di->our buf
	cld
	rep	movsb	
			
	mov	ax,1100h	; set char
	mov	cx,1
	pop	dx
	mov	bh,10h		; 8*16 vga/mcga
	lea	bp,charmap
	int	10h

	mov	ax,4c00h
	int	21h
main	endp

charmap	db SCANLINES dup(0)	; init to 0 as last lines must be blank
	end	main

History: Executing a program in DOS

2005-01-24T21:51:00.000-05:00

A common trick in the old days was to execute an application from within another. Here is some code example of how that was normally done:


.model tiny
.code

ExecBlk	Struc
	Psp	dw	?
	Cmdline	dw	?
	CmdSeg	dw	?
	FCB1	dw	?
	FCB1seg	dw	?
	FCB2	dw	?
	FCB2seg	dw	?
ExecBlk	ends

	org	100h

main	proc
	lea	bx,pspblk
	mov	sp,bx
	call	resize	

	mov	execb.psp,0		; copy our environment
	mov	execb.cmdline,80h	; pass command line as is
	mov	execb.FCB1,5ch
	mov	execb.FCB2,6ch
	mov	execb.cmdseg,cs
	mov	execb.FCB1seg,cs
	mov	execb.FCB2seg,cs
	lea	dx,execf
	push	ds
	pop	es
	lea	bx,execb
	mov	ax,4b00h
	int	21h
merr:
	mov	ax,4c00h
	int	21h
main	endp

resize	proc
	add	bx,15
	mov	cl,4
	shr	bx,cl
	mov	ax,cs
	add	bx,ax
	mov	ah,4ah
	int	21h
	jc	merr
	ret
resize	endp


execf	db	"PAT.COM",0		; ASCIIZ pathname of file to be execd
execb	ExecBlk	<>
_stack	dw	1000h dup(?)

pspblk	label	byte

	end	main

Is BASIC good for anything?

2004-12-31T14:51:00.000-05:00

Has BASIC become the red haired stepchild that nobody wants?

Some folks look down upon BASIC programmers; in fact they even avoid thier company. I'm not trying to say that all programmers are equal in the eyes of the CPU or anything, but remember that Bill Gates is basically a BASIC programmer and that BASIC was once the language of choice for many music related application in the 80's. BASIC's PLAY keyword makes it simple to program musical notes and I'm sure the language has a couple of other redeeming features as well (I just can't remember what they are at the moment).

BASIC's lack of the need for formal structure such as class declarations or include statements plus its interpreted nature makes it a popular language to learn programming even in places like India where everyone is allegedly born partially a programmer.

Speaking of India, here is a song written entirely in BASIC.

10 '+------------------------------------------------------------------------+
20 '|                      The Indian National Anthem                        |
90 '+------------------------------------------------------------------------+
110  PLAY "L8C#D#FFFFFFL4FL8FFD#FL4F#"  '| Jana gana mana adhinayaka jaya hai|
120  PLAY "L4FL8FFL4D#L8D#D#CD#L2C#"    '| Bharatha bhagya vidhatha          |
130  PLAY "L4D#G#L8G#L4G#L5G#"          '| Punjaba Sinda                     |
140  PLAY "L8G#L4G#L8G#G#G#L8A#L4G#"    '| Gujaratha maratha                 |
150  PLAY "L4F#L8F#F#L4FL8FFD#F#L1F"    '| Dravida uthkala vanga             |
160  PLAY "L4FL8FFl4Fl8fd#g#g#l4g#f#f#" '| Vindhya Himachala Yamuna Ganga    |
170  PLAY "L4fl8ffd#d#d#l8cl4d#l1c#"    '| Uthkala jaladi taranga            |
180  PLAY "L8ffffl4fl4fl8d#fl1f#"       '| Tava shubha name jage             |
190  PLAY "L8ff#g#g#l4g#l8f#fd#l8f#l1f" '| Tava shubha ashisa mage           |
200  PLAY "l4ffl8d#d#d#d#cd#l1c#"       '| Gahe Tava jaya gatha              |
210  PLAY "l8g#g#g#g#l4g#l8g#g#"        '| Jana gana mangala                 |
220  PLAY "l4g#l8g#g#g#l8a#l4g#"        '| Dayaka jaya hai                   |
230  PLAY "l4f#l8f#f#l4fl8ffl8d#f#l1f"  '| Bharatha bhagya vidhata           |
240  PLAY "o5l8ccl1c#l8co4a#l1o5c"      '| Jaya hai jaya hai                 |
250  PLAY "l8o4g#g#o5l1o4a#"            '| Jaya hai                          |
260  PLAY "l8c#d#fff#f#d#fl1f#"         '| Jaya jaya jaya jaya hai           |
270  END                                '+-----------------------------------+

Choosing the best suited language

2004-12-31T14:24:00.000-05:00

But its got to be done in Jaavaa! (or .NET or VB or whatever)

No, Dr. Dre, you need to choose what's the most suitable language to solve the problem. Believe it or not, the complexity of the application changes dramatically with a language that thinks differently from the problem class at hand.

For example, consider a simple app that converts strips non-ASCII characters by converting them to their ASCII counterparts.

Lets say your manager loves BASIC and writes it as below


OPEN "unstripped" FOR INPUT AS #1
OPEN "stripped" FOR OUTPUT AS #2
WHILE NOT EOF(1)
     a$ = INPUT$(1, 1)
     n = ASC(a$)
     IF n > 127 THEN
           PRINT #2, CHR$(ASC(a$) - 128);
     ELSE
           PRINT #2, a$;
     END IF
WEND
CLOSE
END

That is quite reasonable, isn't it? You could probably write something equivalent in C, Java or related languages.
Yes, but look how much simpler it would be if Perl was chosen as the language of choice.


perl -pe 'y/\x80-\xff/\x00-\x7f/'

Its a one liner you type on the command line. For text processing, Perl tends to beat any other language.

Writing good hashcodes and equals

2004-12-07T13:56:00.000-05:00

How would one write a good hashcode? Here is one I've seen in real life:


class Thing
{
    List itemlist;

    public int hashCode()
    {
        return toString().hashCode();
    }

    public boolean equals(Object o)
    {
        return o.toString().equals(toString());
    }

    public String toString()
    {
        return "Items = " + itemlist.toString() ;
    }
}

For reasons of brevity, I've drastically reduced the size of the original toString() function, but suffice to say, it printed the all elements of the entire complex Object with appropriate keywords. And the member itemlist was one that could grow indefinitely long. It was obvious that the dude who wrote it does not know what a hashcode is at all. A hashcode serves as a value for quick comparison between Objects. It is essentially used to quickly locate which bucket the item is stored in HashMaps and other data structures that provide near constant access time. If the hashCode computation takes longer than the equals comparison, then you need to brush up on your fundamentals. What could be done differently? A simple way to define a good hashCode is given below:

class A
{
    Integer a, b;
    String c;
    Set d;

    public int hashCode()
    {
        // Sum of (prime number * hashcode) for selected members
        return 7 * a.hashCode() + 11 * b.hashCode();
    }

    public boolean equals(Object o)
    {
        if(o == null || !getClass().equals(o.getClass()) || o.hashCode() != hashCode())
            return false;
        A other = (A)o;
        return other.a == a && other.b == b
            && c.equals(other.c) && d.equals(other.d);
    }
}

As you can see, while equal Objects imply equal hashCodes, the converse is not necessarily true. Most of the time, the check for class and hashCode will eliminate most matches. Among the few that do match, you just need to compare the itemlists without converting them to String first. This has the added benefit that the comparison can terminate early for example if the lengths are different. If you do not have any other members or you believe that they do not sufficiently provide a proper distribution of the hashcodes, you can define the functions as below:

class Thing
{
  private List itemlist;

    public int hashCode()
    {
        if( itemlist != null && itemlist.size() > 0 )
            return itemlist.size() * 7 + itemlist.get(0).hashCode();
        else
            return 0;
    }

    public boolean equals(Object o)
    {
        if (o == null || !getClass().equals(o.getClass()) || o.hashCode() != hashCode())
            return false;
        Thing thing = (Thing)o;
        return thing.itemlist == null && itemlist == null ||
            thing.itemlist.equals(itemlist);
    }

    public String toString()
    {
        return "Items = " + itemlist.toString() ;
    }
}

Of course, you have to ask yourself what business you have in returning toString() of classes that can be very large. If unavoidable, you should at least cache the results of toString() and hashCode() and update them on changes. This may need synchronization, so generally keeping hashcodes and toString functions simple is the better choice.

Does Java pass Objects by reference?

2004-09-16T22:07:00.000-04:00

You often hear that Java passes primitives by value and Objects by reference. Unfortunately, this is misleading. A reference has a specific meaning in programming terminology. A reference is the variable itself. Its not a pointer, its not a copy, its the actual variable. This means that if a variable is passed by reference to a function and the function assigns another value to it, the changes are visible outside the function. C++ implements references faithful to the original meaning while Java does not. #include <iostream.h> class Ref { public: int one(int& it) { it = 1; } // Reassign variable void two(int& it) { it++; } // Change variable }; int main() { Ref ref; int item = 0; ref.one(item); cout << "Item is " << item << endl; ref.two(item); cout << "Item is " << item << endl; int* i = new int(0); ref.one(*i); cout << "I is " << *i << endl; } Prints: Item is 1 Item is 2 I is 1 Java on the other hand, passes a copy of the reference. This means that any changes to the variable are preserved, but you cannot reassign the variable to point to something else within the traditional meaning of "reference." import java.util.Date; public class Ref { public void one(Date item) { item = new Date(); } public void two(Date item) { item.setTime(365*24*60*60*1000L); } public static void main(String[] args) { Date item = new Date(); item.setTime(0); Ref ref = new Ref(); ref.one(item); // Change not reflected here System.out.println("Item is "+item); ref.two(item); // Change is reflected here System.out.println("Item is "+item); } } Prints: Item is Wed Dec 31 19:00:00 EST 1969 Item is Thu Dec 31 19:00:00 EST 1970 The net effect of this is that a Java function can change the Object passed to it, but any reassignment to something else is lost. Many argue that this is indeed safer and C++ funtionality can be achieved by having the function return the new value and let the caller assign it to the actual variable. It also protects the programmer from having to overload the = operator when calling outside code to ensure that the reference is not reassigned. Click here for good reference on References

Tricks with Comments

2004-07-31T18:39:00.000-04:00

Trick one: The code switch Sometimes it is essential to switch between two blocks of code. On systems that support C style comments, you could use the following construct: //* Two slashes for version A, one slash for version B int main() // version A { printf("Version A\n"); } /*/ int main() // version B { printf("Version B\n"); } //*/ Works on C/C++/Java/C#. For SQL: --/* SELECT * FROM A /*/ SELECT * FROM B --*/ Remove the -- on the first line to switch to the second block. Now, if anyone knows how to do it in other languages...

Trick two: Nested comments Some compilers support nested comments (actually, only Borland!). This piece of code helps you detect if the compiler supports nested comments:

#define NESTED /* /* /*/ 0 */*/*/1

main()
{
   puts(NESTED ? "Supported" : "Unsupported");
}

Bad algorithms and caching

2004-07-29T21:21:00.000-04:00

The fibonacci function is traditionally defined recursively:

fib(n) = fib(n-1) + fib(n-2); fib(1) = fib(0) = 1

This would typically be implemented in the venerable C language as:

unsigned long long fib(int n)
{
        return n == 0 || n == 1 ? 1 : fib(n-1) + fib(n-2);
}

The problem with this implementation is that the performance is atrocious. $ time ./fib -r 40 165580141 real 0m18.263s user 0m18.262s sys 0m0.002s The reason is that each higher number needs geometrically increasing number of recursive invocations:

 
 fib(0) = 1 call
 fib(1) = 1 call
 fib(2) = 3 calls
 fib(3) = 5 calls
 fib(4) = 9 calls
 fib(5) = 15 calls
 fib(6) = 25 calls
 fib(7) = 41 calls
 fib(8) = 67 calls
 fib(9) = 109 calls
 fib(10)=177 calls
 ....
 fib(40) = 331160281 calls

Curiously, the number of calls for fib(n) can be defined as:

 fib_calls(n) = 1 + fib_calls(n-1) + fib_calls(n-2); fib_calls(1) = fib_calls(0) = 1

The performance problem is addressed by rewriting the function to work iteratively: unsigned long long iterative_fib(int n) { register unsigned long long n1 = 0, n2 = 1, tmp; int i = 0; for(i = 0 ; i < n; i++) { tmp = n2; n2 = n2 + n1; n1 = tmp; } return n2; } This gives a remarkable boost in performance: $ time ./fib -i 40 165580141 real 0m0.003s user 0m0.001s sys 0m0.002s Another way to get around the performance problem is to use caching with the recursive algorithm: static unsigned long long cache[100]; unsigned long long cached_fib(int n) { if(cache[n]) return cache[n]; return n == 0 || n == 1 ? 1 : (cache[n] = cached_fib(n-1)+cached_fib(n-2)); } Performance is similar to that of the iterative version: $ time ./fib -c 40 165580141 real 0m0.003s user 0m0.000s sys 0m0.003s However, in a program that calls the fibonacci function numerous times, the cached recursive version would work on an average, faster than the iterative verion. The flip side is that caching uses up memory. After a certain threshold, the system starts swapping to disk and performance degrades rapidly. So you really want to select good algorithms wherever possible and save caching for operations that simply have to be cached such as those involving disk or network IO.

Click here to download the complete source

Simplicity, the first principle

2004-02-19T23:59:00.000-05:00

Simple programs evolve, complex programs die. 99 percent of features are under utilized in any program. Simplicity and elegance is way more successful than feature load. So is adherence to existing standards.