Web Stats

I just set up report magic for analog on my server. If anyone cares to see them, http://totally.surrealistic.net/weblog/index.html.

MIPS Assembly Language Template

Below is a simple template for writing programs and procedures in MIPS assembly language. The stack pointer by convention can point to either the bytes on top of the stack or at the next available free set of bytes on the stack. In this template it points to the next available location. This means you need to add data to the stack, then move the stack pointer to the next free spot when pushing to it. When you pop from the stack you will move the stack pointer to point to the last bit of data on the stack, then remove it.

#####################################################################
# Static data is defined here
#####################################################################

.data

######################################################################
# Program is defined here
#####################################################################

.text
.globl main                        # make main a global label

main:
        sw       $ra, 0($sp)      # Move the return address of caller
                                         # onto stack. Necessary in case this
                                         # code calls another procedure
 
        subu    $sp, $sp, 4    # Move stack pointer to next available
                                         # free space. Must subtract since stack
                                         # grows down.
 
#####################################################################
# Begin program
# Note: It is good practice to list the registers used and their
#       what they are used for.
##################################################################### 
# add your program code here

#####################################################################
# End Program
#####################################################################

#####################################################################
# Exit Program and return to location it was called from
#####################################################################
exit:
        addiu   $sp, $sp, 4    # Move stack pointer 4 bytes up,
                                         # Stack grows down, so adding actually
                                         # removes data from the stack
        
        lw      $ra, 0($sp)       # Move return address from stack into
                                         # reserved return address register $ra
  
        jr      $ra                   # Return

Dual Boot Fedora Core 4 & Windows XP

Will the fun never end!? Some of you guys *cough* Sandra *cough* might ask, has it started yet? My response is, just let me play with computers. It really is fun.

This weekend I started up another little project. Mainly I needed to get a PC up and running for doing homework at home, rather than in the labs at school. Below are the steps I followed to get my PC dual booting Windows XP and Fedora on a single drive.

1. First I installed windows. Before installation I partioned my 40 Gb hard drive into two partitions, roughly 20 Gb each. Then I installed windows as normal on the first partition (C:). It is important to note that certain format types traditionally are not compatible with certain operating systems, i.e. Linux and NTFS. Although there are some interesting new projects which allow NTFS to be mounted from linux.




2. Once installation is complete I restarted the computer (and made sure the BIOS were set to boot from CD first) and booted off of my Fedora Core install CD.




3. Again I had to format and partition the remaining 20Gb, so I could install linux on it. I made a minimal partition setup with only two partitions of the remaining space. One as the primary partion ( '/' ) and one as swap. Your partitioning can be much more complicated depending on your system and the number of disks, but for me, this is all I needed. For an introduction to partitioning for Linux see Linux.com's Introduction to Partitioning




4. Make sure that you choose to format and install on the part of the drive that does not have windows already installed on it. If you installed Windows to the C drive, that will be hda1. The partition you want to install on would be hda2.




5. The next step was to decided where to store the Fedora boot record. The easiest place is to store it on the master boot record (MBR). You can store it on the drive that linux installed on as well, but that may require a little more configuration to get the boot loader to work properly.




6. Having not used the windows boot loader I decided to use GRUB




7. Here is where the fun begins. I had chosen to use GRUB, so I figured the boot loader would appear after a reboot. From there I could decided which OS to boot. Nope! After a little googling I found out how to edit the GRUB config file. Belwo is an example file:




default=0
timeout=10
splashimage=(hd1,2)/grub/splash.xpm.gz
hiddenmenu
title Linux
        root (hd1,2)
        kernel /vmlinuz-2.4.18-14 ro root=LABEL=/
        initrd /initrd-2.4.18-14.img
title Windows XP
        rootnoverify (hd0,0)
        chainloader +1




8. code denotes which OS is default. timeout denotes the length of time before the default OS is loaded. title blocks start the description of each OS and how to load it. The last command of note is the hiddenmenu command. This tells the boot loader whether or not to actually display the boot loader screen ... or hide it. When installing Fedora Core 4, this was enabled, so I was never able to see the boot loader screen to choose my operating system. Once this line was removed the boot loader worked properly and I was able to choose which OS to load.



9. That's it!

I am now a happy user of Windows and Fedora.

Array Intersection

So finding the intersection of two arrays can be trivial, but it may not be so 'trivial' if it is asked to you by the recruiter of a company. Here are three algorithms to solve the problem.

The first solution is to brute force the problem by marching through the first array and then march through the second. If the value is found in the second array, then simply move to the next value in the first array. This algorithm assumes the values in the first array are unique. The runtime for this algorithm is O(N²).

for ($i = 0; $i < count($a); $i++) {
 for ($j = 0; $j < count($b); $j++) {
  if ($a[$i] == $b[$j]) {
   $intersection[] = $a[$i];
   break;
  }
 }
}

The second solution, assuming the arrays are sorted, is to proceed as before, except use a binary search while searching the second array. Hopefully you would be smart and iterate through the smaller array and use binary search on the larger. Otherwise your hardwork would be wasted. This algorithm also makes the uniqueness assumption. The runtime for this algorithm is O(N*Log(N));

$lo = 0;
$mid = floor(count($b) / 2);
$hi = count($b)-1;
for ($i = 0; $i < count($a); $i++) {
 while($lo <= $hi) {  
  if ($b[$mid] == $a[$i]) {
   $intersection[] = $a[$i];
   break;
  } else if ($a[$i] < $b[$mid]) {
   $hi = $mid - 1;
  } else if ($a[$i] > $b[$mid]) {
   $lo = $mid + 1;
  }
  $mid = floor(($hi + $lo) / 2);
 }
 $lo = 0;
 $mid = floor(count($b) / 2);
 $hi = count($b)-1;
}

Lastly, we have the efficient algorithm, but only possible with hash tables. In practice, this algorithm could be slower than the previous algorithm if N and M are small, but this post is not a proof, so simple as it may be I won't bore you with the details (use two arrays of length <= 100 to see). This algorithm simply involves 'marking' the values you have seen in each array as you iterate through them seperately. This algorithm will handle the case of each array not having unique values as well.

$temp_hash = array();
$intersection = array();
for ($i = 0; $i < count($a); $i++) {
 if (!isset($temp_hash[$a[$i]])) {
  $temp_hash[$a[$i]] = 1;
 } else {
  $intersection[] = $a[$i];
 }
}
for ($i = 0; $i < count($b); $i++) {
 if (!isset($temp_hash[$b[$i]])) {
  $temp_hash[$b[$i]] = 1;
 } else {
  $intersection[] = $b[$i];
 }
}

So, those are the three solutions. The first is pretty bad in most all cases, except for a few cases where both of the arrays are small and you may not want a binary search because of the extra memory and arithmetic commands. The best solution may be to switch between the three algorithms depending on the size of the inputs.

Reverse the words in a string!

This weekend I was talking to David, who is moving to Mountain View, CA for his new job at Google. He was telling me about some the interviews he has had recently. This conversation sparked me to start doing some more of those programming exercises, which are commonly used during interviews. I was bored today, so I wrote up a short algorithm to reverse the words in a string, but not the characters in the words. (Disclaimer: works upon brief inspection. I will not be responsible for anyone getting or not getting a job). Hehe.

#include <stdio.h>
#include <string.h>

int main(void) {
    char *str = "Hello World I Am Here";
    char new_str[strlen(str)]; // String to copy to
    char word_str[strlen(str)]; // Temp string to hold words
    char t_char;    // Temp character

    int i = 0; // str counter
    int j = 0; // word_str counter
    int k = 0; // copy word_str to new_str counter
    int m = 0; // new_str counter
 
    for (i = 0; i < strlen(str); i++) {
        t_char = str[strlen(str) - 1 - i];
  
        // Is this character a space. Yes, then copy the las
        // word saved, otherwise add the character to the word
        // we are saving
        if (t_char == ' ') {

            // Add the word to the new string, in reverse order
            for (k = 0; k < j; k++) {
                new_str[m] = word_str[j - k - 1];
                m++;
            }
   
            // Add the space
            new_str[m] = t_char; 
            m++;
 
            j = 0;
   
            } else {
                word_str[j] = t_char;   
                j++;
           }
    }
 
    // Add the last word, if any
    for (k = 0; k < j; k++) {
        new_str[m] = word_str[j - k - 1];
        m++;
    }
 
    // Print the word, done character by character, so unset
    // array indexes won't give an ugly print out
    for (i = 0; i < m; i++) {
        printf("%c", new_str[i]);
    }
 
    printf("\n"); 
    return 0;

}

Last night I also did some array intersection algorithms. I will post those this evening. These ones are written in PHP as opposed to C, since I used hash tables for one of the algorithms.

This code could probably be optimized, as I am repeatedly making calls to str_len, but this is more of a proof of concept than an optimal piece of code, so I am not going to worry about it. Feel free to comment, I can only learn from them.

XCode and the MySQL C API

This evening, see as how it was a Friday, I decided to do a little programming. Since I have worked with MySQL databases in PHP, Java, Visual Basic .NET, C# and Javascript, I thought it was only right to do some MySQL programming in C. This was a good chance for me to kill two birds with one stone since I want to do more C/C++ programming in XCode.

Everything was working well. Last night I installed MySQL and it's development libraries with fink. I edited the Active Target in XCode, so I could add the proper header and library paths, /sw/include/mysql & /sw/lib/mysql respectively. So I specified '-lmysqlclient' as an Other Linker Flag, so that the appropriate library was linked in during the compiling process. Sweet, this is similar to coding in Visual Studio. Why do I keep getting this error?

[Session started at 2005-10-08 02:39:02 -0700.]
ZeroLink: unknown symbol '_mysql_init'

MySQL has exited due to signal 6 (SIGABRT).

I guess the ZeroLink prefix is a good indicator. The problem here is that ZeroLink does not actually link the library appropriately. To solve the problem I had to change the Active Build Style to deployment. That was it, then it compiled and I could make some progress.

So to make a long story short, to use the MySQL C API with XCode, follow these steps:

1. Edit Active Target


2. Go to Build -> Search Paths


3. Set 'Header Search Paths' to the include directory of MySQL (usuall /usr/local/mysql/include)


4. Set 'Library Search Paths' to the include lib of MySQL (usuall /usr/local/mysql/lib)


5. Go to Build -> Linking


6. Set 'Other Linker Flags' to '-lmysqlclient'


7. Close this window


8. Set Project -> Set Active Build Style to 'deployment'

Next Step, assembly on my powerbook! This will take a little while to learn though.