How Does Call Stack Work?

From Stanford CS Ed Library: Pointers and Memory

The exact details of the implementation are language and compiler specific. However, the basic structure below is approximates the method used by many different systems and languages...

To call a function such as foo(6, x+1)...

1. Evaluate the actual parameter expressions, such as the x+1, in the caller's context.

2. Allocate memory for foo()'s locals by pushing a suitable "local block" of memory onto a runtime "call stack" dedicated to this purpose. For parameters but not local variables, store the values from step (1) into the appropriate slot in foo()'s local block.

3. Store the caller's current address of execution (its "return address") and switch execution to foo().

4. foo() executes with its local block conveniently available at the end of the call stack.

5. When foo() is finished, it exits by popping its locals off the stack and "returns" to the caller using the previously stored return address. Now the caller's locals are on the end of the stack and it can resume executing.

Algorithms - Sorting

From Wikipedia Sorting Algorithm.

Bubble sort

Bubble sort is a straightforward and simplistic method of sorting data that is used in computer science education. The algorithm starts at the beginning of the data set. It compares the first two elements, and if the first is greater than the second, then it swaps them. It continues doing this for each pair of adjacent elements to the end of the data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. This algorithm is highly inefficient, and is rarely used^, except as a simplistic example.
Bubble sort average case and worst case are both O(n²).

ResultCode BubbleSort(int a[], int nSize)
{
    ResultCode res = SORT_FAILED;
    int i, j = 0;
    bool bSwap = true;
    int tmp;
    if (a)
    {
        while (bSwap)
        {
            bSwap = false;
            j++;
            for (i = 0; i < (nSize - j); i++)
            {
                if (a[i] > a[i + 1])
                {
                    tmp = a[i];
                    a[i] = a[i + 1];
                    a[i + 1] = tmp;
                    bSwap = true;
                }
            }
        }
        res = SORT_OK;
    }
    return res;
}

Selection sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

ResultCode SelectionSort(int numbers[], int array_size)
{
    int i, j;
    int min, temp;
    ResultCode res = SORT_FAILED;
    if (numbers)
    {
        // for each number, find the min from the list of i to the end
        // and then swap the min with i;
        for (i = 0; i < array_size-1; i++)
        {
            // set min to i
            min = i;
            // check each one from i + 1 to the end of the array
            // to find the minimum number from the list of numbers
            // from i+1 to the end
            for (j = i+1; j < array_size; j++)
            {
                // if any number is less than the min, set min to the new index
                if (numbers[j] < numbers[min])
                {
                    min = j;
                }
            }
            // swap the minimum with i
            temp = numbers[i];
            numbers[i] = numbers[min];
            numbers[min] = temp;
        }
         res = SORT_OK;
    }
    return res;
}

Insertion sort

Main article: Insertion sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists, and often is used as part of more sophisticated algorithms. It works by taking elements from the list one by one and inserting them in their correct position into a new sorted list. In arrays, the new list and the remaining elements can share the array's space, but insertion is expensive, requiring shifting all following elements over by one. Shell sort (see below) is a variant of insertion sort that is more efficient for larger lists.

ResultCode InsertionSort(int arr[], int length)
{
    int i, j, tmp;
    ResultCode res = SORT_FAILED;
    if (arr)
    {
        for (i = 1; i < length; i++)
        {
            j = i;
            while (j > 0 && arr[j - 1] > arr[j])
            {
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;
                j--;
            }

        }
        res = SORT_OK;
    }
    return res;
}

Shell sort

Main article: Shell sort

Shell sort was invented by Donald Shell in 1959. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time. One implementation can be described as arranging the data sequence in a two-dimensional array and then sorting the columns of the array using insertion sort.

ResultCode ShellSort(int num[], int length)
{
    int i, temp, flag = 1;
    int d = length;
    ResultCode res = SORT_FAILED;
    if (num)
    {
        while(flag || (d > 1))
        {
            flag = 0;                     
            d = (d + 1) / 2; // use (d + 1)/2 as the gap
            // starting from positon 0 to length - d - 1, comparing num[i] 
            //and num[i+d]
            for (i = 0; i < (length - d); i++)  
            {
                if (num[i + d] > num[i])
                {
                    // swap positions i+d and i
                    temp = num[i + d];         
                    num[i + d] = num[i];
                    num[i] = temp;
                    // tells swap has occurred
                    flag = 1;                                   }
            }
        }
        res = SORT_OK;
    }
    return res;
}

Binary tree sort

typedef struct tree_el {
   int val;
   struct tree_el * right, * left;
} node;

void BinaryTreeSort(node **tree, node *item)
{
   if(!(*tree)) {
      *tree = item;
      return;
   }
   if(item->val <= (*tree)->val)
      BinaryTreeSort(&(*tree)->left, item);
   else if(item->val>(*tree)->val)
      BinaryTreeSort(&(*tree)->right, item);
}

void printout(node * tree) {
   if(tree->left) printout(tree->left);
   printf("%d\n",tree->val);
   if(tree->right) printout(tree->right);
}

Merge sort

Main article: Merge sort

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n). Merge sort has seen a relatively recent surge in popularity for practical implementations, being used for the standard sort routine in the programming languages Perl^[5], Python (as timsort^[6]), and Java (also uses timsort as of JDK7^[7]), among others. Merge sort has been used in Java at least since 2000 in JDK1.3.^[8][9]

void Merge(int a[], int low, int high, int mid)
{
    int i, j, k, c[high - low];
    i = low;
    j = mid + 1;
    k = 0;

    while((i <= mid) && (j <= high))
    {
        if (a[i] < a[j])
        {
            c[k] = a[i];
            k++;
            i++;
        }
        else
        {
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while (i <= mid)
    {
        c[k] = a[i];
        k++;
        i++;
    }
    while(j <= high)
    {
        c[k] = a[j];
        k++;
        j++;
    }
    for(i = low; i < (high + 1); i++)
    {
        a[i] = c[i - low];
    }
}


ResultCode MergeSort(int a[], int low, int high)
{
    ResultCode res = SORT_FAILED;
    int mid;

    if (a)
    {
        if (low < high)
        {
            mid = (low + high) / 2;
            MergeSort (a, low, mid);
            MergeSort(a, mid + 1, high);
            Merge(a, low, high, mid);
        }
        res = SORT_OK;
    }
    return res;
}

Heapsort

Main article: Heapsort

Heapsort is a much more efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree. Once the data list has been made into a heap, the root node is guaranteed to be the largest(or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log n) time, instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time, and this is also the worst case complexity.

// node index starts at 0
#define left(i) 2*i+1
#define right(i) 2*i+2

// In computer science, a heap is a specialized tree-based data structure
// that satisfies the heap property: if B is a child node of A, then
// key(A) = key(B). This implies that an element with the greatest key is
// always in the root node, and so such a heap is sometimes called a max-heap.
void max_heapify(int a[],int i,int size)
{
    int l,r,largest,temp;
    l=left(i);
    r=right(i);
    if(l<=size-1 && a[l]>a[i])
        largest = l;
    else largest = i;
    if(r<=size-1 && a[r]>a[largest])
        largest = r;
    if(largest != i)
    {
        temp = a[i];
        a[i]=a[largest];
        a[largest]=temp;
        // since we change the value of the "largest" (index) node,
        // we have to make sure there is still a max heap below that.
        max_heapify(a,largest,size);
    }
}
void build_max_heap(int a[],int size)
{
    int i;
    // starting from rightmost parent going upward.
    for(i=size/2 - 1 ;i>=0;i--)
        max_heapify(a,i,size);
}
ResultCode HeapSort(int a[],int size)
{
    int i,temp;
    ResultCode res = SORT_FAILED;
    if (a)
    {

        build_max_heap(a,size);
        for(i=size-1;i>0;i--)
        {
            // swap the root (largest value) and the end
            temp=a[i];
            a[i]=a[0];
            a[0]=temp;
            size=size - 1;
            max_heapify(a,0,size);
        }
        res = SORT_OK;
    }
    return res;
}

Quicksort

Main article: Quicksort

Quicksort is a divide and conquer algorithm which relies on a partition operation: to partition an array, we choose an element, called a pivot, move all smaller elements before the pivot, and move all greater elements after it. This can be done efficiently in linear time and in-place. We then recursively sort the lesser and greater sublists. Efficient implementations of quicksort (with in-place partitioning) are typically unstable sorts and somewhat complex, but are among the fastest sorting algorithms in practice. Together with its modest O(log n) space usage, this makes quicksort one of the most popular sorting algorithms, available in many standard libraries. The most complex issue in quicksort is choosing a good pivot element; consistently poor choices of pivots can result in drastically slower O(n²) performance, but if at each step we choose the median as the pivot then it works in O(n log n). Finding the median, however, is an O(n) operation on unsorted lists, and therefore exacts its own penalty.

ResultCode QuickSort(int arr[], int left, int right)
{

    int i = left, j = right;
    int tmp;
    ResultCode res = SORT_FAILED;
    if (arr)
    {
        int pivot = arr[(left + right) / 2];
        /* partition */
        while (i <= j)
        {
            while (arr[i] < pivot)
            {
                i++;
            }
            while (arr[j] > pivot)
            {
                j--;
            }
            if (i <= j)
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        };
        /* recursion */
        if (left < j)
        {
            QuickSort(arr, left, j);
        }
        if (i < right)
        {
            QuickSort(arr, i, right);
        }
        res = SORT_OK;
    }
    return res;
}

Counting Sort

Main article: Counting sort

Counting sort is applicable when each input is known to belong to a particular set, S, of possibilities. The algorithm runs in O(|S| + n) time and O(|S|) memory where n is the length of the input. It works by creating an integer array of size |S| and using the ith bin to count the occurrences of the ith member of S in the input. Each input is then counted by incrementing the value of its corresponding bin. Afterward, the counting array is looped through to arrange all of the inputs in order. This sorting algorithm cannot often be used because S needs to be reasonably small for it to be efficient, but the algorithm is extremely fast and demonstrates great asymptotic behavior as n increases. It also can be modified to provide stable behavior.

ResultCode CountingSort (int array[], int size)
{
    int i, min, max;
    ResultCode res = SORT_FAILED;
    if (array)
    {
        min = max = array[0];
        for(i = 1; i < size; i++)
        {
            if (array[i] < min)
                min = array[i];
            else if (array[i] > max)
                max = array[i];
        }
        // under the assumption of range being smaller than size, or it's 
        // not worth it.
        int range = max - min + 1;
        int *count = (int *)malloc(range * sizeof(int));

        for(i = 0; i < range; i++)
        {
            count[i] = 0;
        }
        // count index + 2 is the value,
        // counting freqency of that value.
        for(i = 0; i < size; i++)
        {
            count[ array[i] - min ]++;
        }
        int j, z = 0;
        for(i = min; i <= max; i++)
        {
            for(j = 0; j < count[ i - min ]; j++)
            {
                array[z++] = i;
            }
        }
        free(count);
        res = SORT_OK;
    }
    return res;
}

Bucket sort

Main article: Bucket sort

Bucket sort is a divide and conquer sorting algorithm that generalizes Counting sort by partitioning an array into a finite number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. Thus this is most effective on data whose values are limited (e.g. a sort of a million integers ranging from 1 to 1000). A variation of this method called the single buffered count sort is faster than quicksort and takes about the same time to run on any set of data.

// Here array is the array to be sorted and n is the number of buckets to 
// use. The function msbits(x,k) returns the k most significant bits of x 
// (msbits = floor(x/2^(size(x)-k)), floor function returns the largest 
// integral value not greater than x.)
// uucket sort assumes that the input is generated by a random process 
// that distributes elements uniformly over the interval [0, 1), in this 
// code, the range is [0, 999]
ResultCode BucketSort(int *a,int n)
{
    vector bucket[10];
    int i, j;
    int idx = 0;

    ResultCode res = SORT_FAILED;
    if (a)
    {
        for (i = 0; i < n; i++)
        {
            bucket[(a[i]/100)].push_back(a[i]);
        }
        for (i = 0; i < 10; i++)
        {
            // creating a new array.
            int arr[bucket[i].size()];

            // copy the vector data to array because our InsertionSort 
            // accepts array.
            for (j = 0; j < bucket[i].size(); j++)
            {
                arr[j] = bucket[i][j];
            }

            InsertionSort(arr, bucket[i].size());
            // put the sorted bucket to the original array.
            for (j = 0; j < bucket[i].size(); j++)
            {
                a[idx++] = arr[j];
            }
        }
        res = SORT_OK;
    }
    return res;
}

Radix sort

Main article: Radix sort

Radix sort is an algorithm that sorts a list of fixed-size numbers of length k in O(n · k) time by treating them as bit strings. We first sort the list by the least significant bit while preserving their relative order using a stable sort. Then we sort them by the next bit, and so on from right to left, and the list will end up sorted. Most often, the counting sort algorithm is used to accomplish the bitwise sorting, since the number of values a bit can have is minimal - only '1' or '0'.

ResultCode RadixSort(int *a,int n)
{
    int i;
    int b[n], m=0, exp=1;
    ResultCode res = SORT_FAILED;

    if (a)
    {
        // Find the maximum number
        for (i=0;i m)
            {
                m = a[i];
            }
        }

        // starting from the last digit
        while ((m/exp) > 0)
        {
            int bucket[10]={0};

            // put each number in the bucket according to the value in the 
            // inspected digit
            for(i = 0; i < n; i++)
            {
                bucket[(a[i]/exp) % 10]++;
            }

            // accumulate the values to the buckets
            for(i = 1;i < 10; i++)
            {
                bucket[i] += bucket[i-1];
            }

            // smart!
            // use the bucket value - 1 (because it's the sequence!) to 
            // for indices of the new array.
            for(i = n-1;i >= 0; i--)
            {
                b[--bucket[a[i]/exp%10]] = a[i];
            }
            for(i = 0;i < n;i++)
            {
                a[i] = b[i];
            }
            exp*=10;
        }
        res = SORT_OK;

    }

    return res;
}

Name	Average	Worst	Memory	Stable	Method	Notes
Bubble Sort	n2	n2	1	Yes	Exchanging	Tiny code
Selection Sort	n2	n2	1	Depends	Selection	Its stability depends on the implementation. Used to sort this table in Safari or other Webkit web browser
Insertion Sort	n2	n2	1	Yes	Insertion	Average case is also O(n + d), where d is the number of inversions
Shell Sort	-	nlog2n	1	No	Insertion
Binary Tree Sort	nlogn	nlogn	n	Yes	Insertion	When using a self-balancing binary search tree
Merge Sort	nlogn	nlogn	n	Yes	Merging	Used to sort this table in Firefox
Heapsort	nlogn	nlogn	1	No	Selection
Quicksort	nlogn	n2	logn	Depends	Partitioning	Can be implemented as a stable sort depending on how the pivot is handled. Naïve variants use O(n) space

The following table describes sorting algorithms that are not comparison sorts. As such, they are not limited by a O(nlogn) lower bound. Complexities below are in terms of n, the number of items to be sorted, k, the size of each key, and s, the chunk size used by the implementation. Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that n << 2^k, where << means "much less than."

Name	Average	Worst	Memory	Stable	n << 2k	Notes
Bucket Sort	n * k	n2 * k	n * k	Yes	No	Assumes uniform distribution of elements from the domain in the array.
Counting Sort	n + k	n + k	n + 2k	Yes	Yes	If k = O(n) then RT = O(n)
LSD Radix Sort	n * k/s	n * k/s	n	Yes	No

Installing and building your C++ programs in Cygwin on Windows Vista

Installation:

1. Run or download setup.exe from this link: http://www.cygwin.com/setup.exe.
2. Select "Install from Internet" & "Direct Connection" if that's your Internet setting.
3. Keep the recommended Root Directory and "Install for" if you don't feel like changing them.
4. Select your Internet connection
5. On Select Packages window, Open "Devel" to select gdb & open "Editor" to select vim if you want vi (I know, I'm old-fashioned...)

On Windows Vista, browse to "C:\ProgramData\Microsoft\Windows\Start Menu\Programs\Cygwin" directory, press right mouse button on Cygwin Bash Shell file, selection Properties->Advanced. Check "Run as administrator"

Run Cygwin Bash Shell from Programs list.


Building your first C++ program
$ g++ yourprog.cpp

If you see the following error:
“This application has requested the Runtime to terminate it in an unusual way”

Add the following:
export TEMP=/tmp to your ~/.bashrc file

Close and restart your Cygwin Bash Shell.

Create an FTP only account in Solaris

The FTP-only username is ftpuser in the following instructions.
   
1. su to root

2. # cat /etc/passwd|cut -f 1 -d: > /etc/ftpusers

3. # echo 'echo "FTP user"' > /bin/ftpuser
# chmod a+x /bin/ftpuser

4. If /etc/shell exists, add 

/bin/ftpuser 

to the last line. 

If not

# ls /bin/*sh > /etc/shells
 
Then add /bin/ftpuser to the last line

5. # useradd -c "FTP User" -d /export/home/ftpuser -m -s /bin/ftpuser -g staff ftpuser
6. # passwd ftpuser


Source: http://www.tek-tips.com/faqs.cfm?fid=2315 + my modifications.
  
Added on 6/9/2010: I just found that my full access account couldn't ftp any more after this. Only ftpuser can ftp. For some strange reason, my username got added to /etc/ftpusers which lists the users that can NOT ftp... Very very weird. After removing my username, the ftp works again.

gconf problem

Yesterday for some reason my CentOS 5.3's gnome session couldn't start any more. It kept showing this kind of messages:

"An error occurred while loading or saving configuration information for gnome-session. Some of your configuration settings may not work properly.


An error occurred while loading or saving configuration information for Nautilus. Some of your configuration settings may not work properly.


An error occurred while loading or saving configuration information for Power Manager. Some of your configuration settings may not work properly.
.
.
."

Clicking on "Details" showed:
"GConf error: Failed to contact configuration server; some possible causes are that you need to enable TCP/IP networking for ORBit, or you have stale NFS locks due to a system crash. See http://www.gnome.org/projects/gconf/ for information. (Details - 1: Could not send message to gconf daemon: Message did not receive a reply (timeout by message bus))"

This morning I spent hours trying to figure out what's going on here. Reinstalling is the last resort. Creating a new user and copy all the files under it is a workaround.

Finally from one of the numerous posts I read, I found "messages" file under /var/log could give you some clues if the system encounters problems during the process of starting up.

The last part of my messages file showed:
Jun  4 04:08:18 mboot-dell gconfd (root-10001): starting (version 2.14.0), pid 10001 user 'root'
Jun  4 04:08:18 mboot-dell gconfd (root-10001): Bad permissions 777 on directory /tmp/gconfd-root
Jun  4 04:08:18 mboot-dell gconfd (root-10001): Failed to get lock for daemon, exiting: Directory /tmp/gconfd-root has a problem, gconfd can't use it

It turned out that the directory /tmp/gconf-xxxx has to have permission 700 instead of 777 where xxxx is the user name. I must have changed it to 777 while doing one of my scribed tests.

Can you believe that? The success of starting the GNOME session depends on the permission of the directory in /tmp directory! This is really hard to conceive. /tmp should be used as /tmp not as a place to save anything mission critical. Don't you think so?

Handbrake hangs at 100%

I wanted to convert one of my exercise DVD discs (VIDEO_TS folder) to mp4 but for some reason, Handbrakes always hung at 100% and the file kept growing. The activity window showed the following:

[14:12:47] sync: adding 252 ms of silence to audio 0 start 15879500, next 15856782
[14:12:47] sync: adding 307 ms of silence to audio 0 start 16039772, next 16012100
[14:12:47] sync: audio 0 time went backwards 0 ms, dropped 25 frames (next 16040900, current 16040900)
[14:12:53] sync: adding 70 ms of silence to audio 0 start 19398884, next 19392572
[14:12:58] sync: adding 70 ms of silence to audio 0 start 22515044, next 22508732
[14:13:03] sync: adding 70 ms of silence to audio 0 start 25631204, next 25624892

After using Ctrl+C to kill the process, the resulting file only has the first two chapters, the rest of it consisted the repeats of a couple of frames.

I used Magic DVD copier to cut down the DVD content to only the title with the chapters I want. But Handbrake still hung at 100%.

Finally I concatenated the VOBs (there are three, copy /b file1+file2+file3 big_file) in the folder and converted it. Finally, it was a success.

Looks like the problem is something to do with the wrong Chaptering and sync. Handbrake just couldn't handle it. And it can do it if it's pure vob files. Still a mystery to me...

TDSS Toolkit Infection Fix

Finally I got rid of this crazy Google search result redirecting virus. I'm pretty certain that I got it (and others which are easier to remove) from one of free games for Nokia phone sites. I struggled with it for more than a week. What a shame. This really taught me a huge lesson about nothing is free...

Symptoms:
1. Fake Windows XP Security Center showed up and it said I should turn on some security thing.

2. Some kind of virus doctor window showed up and started scanning.

3. Task Manager button was grayed out when Alt+Ctrl+Del were pressed.

4. regedit, regedt32 were disabled.

5. Windows update site was blocked.

6. Google search results got redirected.

7. Tab completion is disabled in command line.

8. Does not recognize .exe file

Fix:
1. Download ComboFix from bleepingcomputer and run it. This program takes a long time to run but it's worth it.

2. Download TDSSKiller.zip from kaspersky and run it. If TDSSKiller says your atapi.sys or tskXX.tmp (XX is a number, it's different for each system. Mine is tsk21.tmp) is infected and wants you to reboot to fix it. Don't do it yet.

3. If the problem is with atapi.sys, find a clean XP machine with the same SP level, copy its atapi.sys in c:\windows\system32\drivers to a floppy or flash drive. Boot the infected system to Safe Mode (F8 during system startup) with Networking, replace the infected atapi.sys with the clean one. Do step 4 although TDSSKiller doesn't report tskXX.tmp is infected.

4. If tskXX.tmp is infected, run regedit (To re-enable it if it's disabled by virus, run
gpedit.msc->User configuration -> Administrative Templates -> System.
Choose "Prevent access to registry editing", set it to disable and then set it back to Not Configured.). Search the specific tskXX.tmp in the registry and replace it with atapi.sys.

5. Delete tskXX.tmp in C:\windows\system32\drivers

6. Reboot

7. Clean up and prevention

a. Re-enable Alt+Ctrl+Del: Run gpedit.msc->User Configuration->Administrative Templates-> System->Ctrl+Alt+Del Options. Choose "Remove Task Manger", set it to disable and then set it back to Not Configured.

b. If you're using Firefox, I suggest installing the following Add-Ons to prevent future infections.

NoScript
Verify Redirect

Hope this fixes your problem. It was such a painful process to figure this out...