Stack Growth - Stackoverflow

Stack Growth

Another question you might get is to try to figure out which way a stack grows. As we know a stack (memory region interpreted as a stack) gets allocated for each process. The stack is used to store local variables and context local to the process. Each function call in a process gets a frame inside the stack where the variables local to the functions get stored; when the function exits the frame gets freed. The stack is also used to store the address of the caller function so that the IP (instruction pointer) can jump back after exiting a function call. i.e:

From the example below (Program:) before main() jumps off into foo(), it first pushes the current address of the IP into the stack so that when foo finishes, the IP can know where to go back to in main();

In some systems the stack is said to grow up and in others it is said to grow down. What the heck does that mean? See bellow:

Memory:
0x00000004 -- -- -- --
0x00000008 -- -- -- --
0x0000000C -- -- -- --
0x00000010 -- -- -- --
...

Program:
int foo();
main();
main()-call->foo();

In a simplistic world (don't hold me to the number it's just an example) if your main()'s frame is at 0x0000000C and foo()'s frame is pushed onto the stack at 0x00000008 then the stack is said to grow down-even though in the diagram it might appear as growing up-because the addresses decrease in that direction. If foo() were to appear at 0x00000010 then the stack would grow up, or in the direction in which the addresses increase.

Code:

#include <stdio.h>

void stackTracer(int *x)
{
 int y;
 if(&y > x)
  printf("The stack grows down\n");
 else
  printf("The stack grows up\n");
}

int main()
{
 int x;
 stackTracer(&x);
 getchar();
 return 0;
}

The code works because when stackTracer is called, the main() frame had already been created in the stack, therefore stackStracker() would be pushed onto the stack after main(). If the address of a variable declared in stackTracer() is greater that the address of a variable declared in main(), that tells you that the stack is growing up as it's growing in the direction that the addresses increase.

StackOverflow

The Stack has a size that is defined even before the process begins to run. The size of the Stack is defined by the linker and can be adjusted by changing the linker flags. But once the program has been linked with the Stack size then that will remain the size of the process' stack throughout its life time. Sometimes if you are not careful, you can grow the stack (recursion anyone?) over its allowed size; and you get a stackoverflow exception.

How can you tell the size of your stack?

This program came out of a couple of minutes of spare time when a co-worker friend of mine and myself decided to overflow the stack just for fun:

Code:

#include <stdio.h>

int counter = 0;
void crasher()
{
 double array[10];
 array[0]=1;
 counter++;
 printf("Counter is at %d", counter);
 crasher();
}
int main()
{
 crasher();
 return 0;
}

Then to calculate the size of your stack do => counter (amount of times you allocated that array) * 8 bytes (the size of a double [check your system though]) * 10 (the amount of doubles in the array). Note: this will be roughly the size of your stack, to check the exact size you can always check the default for your linker or the linker flags.

Byte swizzling

So, we have all heard about little endian and big endian concepts. We all know that in a little endian system the least significant byte gets stored first, or at the lowest address. In a big endian system the most gets stored in first, or at the lowest address.

So what happens if you are trying to read data that has been stored in a big endian system?

Say you have 0xDEADBEEF stored like so:

Memory:
a => DE
a+1 => AD
a+2 => BE
a+3 => EF

if you have a 32 bit pointer address pointing to a+3 the value read will be 0XEFBEADDE. In order to make sense of the value you will need to swizzle it. In other words; you will need to change the order of bytes.

Here is code which will swizzle a 32 bit value:

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


#define CODETOSWIZZLE 0XEFBEADDE
int main()
{
   
   unsigned int swizzledCode = \
          ((CODETOSWIZZLE & 0x000000FF)<<24)\
          +((CODETOSWIZZLE & 0x0000FF00)<<8)\
          +((CODETOSWIZZLE & 0x00FF0000)>>8)\
          +((CODETOSWIZZLE & 0xFF000000)>>24);

   printf("Swizzled %x", swizzledCode);

   getchar();
   return 0;
}

Palindrome Test

The palindrome test is very common in interviews. Here is a program that shows how to find out if a string is a palindrome.

Please note that this a simple program as in an interview not much more is expected from you. The test is not meant to commercialize your greatest palindrome rendition. We will not be buying palindrome testing software in the near future. The point of this test is to know your basic knowledge of string manipulation and algorithm generation. This program takes a string and tests whether the string is a palindrome or not. The palindrome can be one word long, or a whole sentence, and can have upper and lower case letters. Note that palindromes are not case sensitive. Also, the palindrome should ignore punctuation marks.

Please note that in my simple algorithm I am assuming that regular ASCII characters are used.

Algorithm:

1) Get string and lets call it testItem;
2) Strip all the punctuation marks, spaces, and symbols,
and store in testItemClean.
3) Reverse the testItem and store it into reverse.
4) Compare testItemClean and reverse.

To find more about palindromes please visit here .

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


int main()
{
   char testItem[] = "Was it Eliot's toilet, I saw?\0";
   int i = 0;
   int currentPointer = 0;
   int cPointerClean = 0;
   int length = (strlen(testItem))-1;
   char *reverse;
   char *testItemClean;

   reverse = (char*) malloc (length*sizeof(char));
   testItemClean = (char*) malloc (length*sizeof(char));
    
   for(i=0; i<=length; i++)
   {
      /*Reversing testItem and storing stripped 
       off symbols into *reverse*/
      
      if((testItem[length-i]>=65 && testItem[length-i]<=90) \
      ||((testItem[length-i]>=97 && testItem[length-i]<=122)))
      {
           if(testItem[length-i]>65 && testItem[length-i]<90)
                 testItem[length-i] = testItem[length-i] + 32; 
           reverse[currentPointer] = testItem[length-i];
           currentPointer++;
       } 

      /*Stripping testItem off symbols and storing into 
      testItemClean*/

      if((testItem[i]>=65 && testItem[i]<=90) \
      ||((testItem[i]>=97 && testItem[i]<=122)))
      {
           if(testItem[i]>65 && testItem[i]<90)
                 testItem[i] = testItem[i] + 32; 
           testItemClean[cPointerClean] = testItem[i];
           cPointerClean++;
      }

   }
   if(!strcmp(reverse, testItemClean))
           printf("It's a palindrome");
   getchar();
}

Bit counting (how many 1's in 5 [binary])

This code is simple and can be enhanced to work in more general cases. If you do end up changing any of the code and wish to post it, please feel free to do, but, do post a link back to this site.

Since so many of you have had problems in interviews regarding bit counting, I have decided to post this program. It counts the amount of 1's that there are in any 32 bit number.

#include <stdio.h>

#define BIT_MASK 0x1

int main()
{
  int number = 52;
  int i = 0;
  int counter=0;
  /*Looping for each bit in an int.*/
  for(i = 0; i < 32; i++)
  {
      /*
        RF1 -> Shift to the right by 1
        52 is 110100 in binary. 
        Bitwise AND 0 with 1 ---> 0 -> RF1
                    0 with 1 ---> 0 -> RF1
                    1 with 1 ---> 1 increase counter -> RF1
                    0 with 1 ---> 0 -> RF1
                    1 with 1 ---> 1 increase counter -> RF1
                    1 with 1 ---> 1 increase counter -> RF1
                    ...
                    It will continue 32 times except that 
                    in this case (52) the rest will be 0s.
      */
      if(number & BIT_MASK)
          counter++;
      number = number >> 1;
  }


  printf("The number of 1's in %d is: %d", number, counter);
  /* Visual Studio will close the output window very fast.
     This trick will keep it open.
  */
  getchar();

}

In Penang - Malaysia

So I have been in Penang - Malaysia for the last 3 weeks. I still have one more week to go. I am here on a business trip doing some embedded software development with Intel. And that's the most I am going to say about that.

I have to tell you, I am very impressed with Penang. When I arrived three weeks ago I wasn't sure about what to expect, or better yet, I expected different things. I had just returned from a business trip to Shanghai and while I loved the city and its people, I had some trouble getting used to the food. Being from Canada I am used to a different type of Chinese food. I arrived in Shanghai a month ago looking for chicken balls and sweet and sour chicken and instead found myself ordering from menus written completely in Chinese and having to pick based on pictures; and these sometimes deceive you. I learned towards the end of my trip that the taste of food I am more accustomed to is the Hong Konk style. So, while I was impressed with the explosion of modernism in high-rise, neon light, big screen Shanghai, and very thankful to the hospitality of its people, the trip left me worried about what to expect in Malaysia.

As soon as I landed in Penang I began to notice that most signs were written in English. Then, when I arrived at The Equatorial Hotel the whole 20 hours travel time began to look like it all might have just been worth it. But the Equatorial will be a subject of another post. This is just a look over Penang. I am very glad to say that most here speaks English very well. It is very easy to get around and I need not worry about getting lost. If I do, I get a cab and the driver will understand what I am saying. And the food...The food, as Robert from Everybody love's Raymond might say, "the food is unbelievable." The melting pot of cultures in Penang makes for an excellent dish. The most common restaurants are what the locals call Hawker places. These are food stands with a number of tables and chairs shared by all the stands. You walk and order the food you like from the different stands and tell them where you are sitting, they will then find you and bring you the food. In Hawker places you can find anything from Chinese, to Indian, to Italian food. As far as the food goes, I am doing very well.

Please keep tuned as I will keep writing about my Penang experiences.

Driving north

Driving north is always entertaining. It doesn't matter what the compass might be yelling; pointing the righteous finger around, if there is farmland between here and there I call it north. That is because most of the time I don't know where north is. You see, I am pretty bad at directions. I don't blame myself, really. I blame communism and the U.S. I grew up in Cuba, you see? Cuba being an underdeveloped country did not have the proper means to manufacture compasses, and the U.S-created embargo made it impossible for me to get my poor young hands on a compass. The lack of compasses at an early age -- as explained by Dr. Marc Gebrauchsanleitung in Compass in early childhood-- rendered me unable to properly find my bearings in any situation. So, when you are out with me and get frustrated by my inabilites to find a location, don't blame me, blame the guys responsible for you getting a cheap vacation on pristine beaches.

In any case, I believe I started calling farmlands, north, because on the first occasion when I took a trip outside of Toronto deep into farmlands, it was to Oro Medonte; north of Barrie. Barrie, is north of Toronto. The other day I was driving north again--it might have been west-- and came to this little town before London Ontario. The outskirts of this little town are carpeted with miles of farmlands and mansion like houses. The main roads linking all these farms and towns are usually 8o km/h but I love driving at 45km/h and just admire the view. The houses look like mansions out of a Stephen King's movie. The gigantic estates where just one person lives, and inevitable becomes hunted. It's eerie and almost morbidly inviting.

In these small towns you can almost always find antic stores. I love going into these antic stores. It feels like taking the express train down memory lane. But insomebody else's memory. You find old chairs, old scratched tables with teeth marks so small and eroded that the kid that created them might be an old man by now. What always fascinates me is finding picture albums. Why people think I would buy their old pictures is always beyond me. But it doesn't mean that I still don't like browsing through. Perhaps it's that same morbid invitation. Most of the pictures are made crisp by the sun and age. They are yellow and faded at the edges of the shapes depicted in them. There are children in long shorts wearing classic tami beret hats and suspenders. The backgrounds look almost completely faded in all of them, but sometimes you are lucky enough to see some people in the odd park. You look at those people and you know that they are all dead, that everyone who was alive in that period: the mailman, all the mailmen, the bum, all the bums, lawyers, writers, family men, prisoners, teachers, every teacher in the planet, honest men, dishonest men, are dead. Yet, you are still looking at them. It's like a time telescope, and you get to peep through. You should try it sometimes when you are bored. Just drive north and see where it takes you, if you are like me it will take you to different places every time. Search for antic store, and look at the treassure hidden in them. Even colour faded roadsigns are sometimes interesting telescopes to look through.

I will give you one advise though, if you happen to be driving behind me on one of those streets make sure that you are polite and don't flash your lights at me. If you don't I will pull over and you can pass. If you do I will reduce my speed to 20km/h and we can both enjoy the view.

Commute on a rainy day

Today I woke to a rainy, snowy day. In the west end of city where I live, the wind was blowing fiercely and even under the multitude of blankets and sleep covers, I could hear the muffled roar of the wind outside my window. I threw a tired arm out from under the blankets and manged to grasp the remote control of my zenith tv resting on my night table. I turned on channel 7, Breakfast television, and listened to Frank Ferragine describe the forecast for today. Was it 25 mm or 25 cm of rain that it was going to fall today? I don't remember. But since it referred to rain I believe it must have been 25 mm. Then, tomorrow 8 cm of snow. Awesome!

I sat up in bed, listened to some more news. Watched Jennifer on the live eye tell the news on the fashion show at George Brown college; great show. Great models. I mean professionally, stop it! Then got up, showered, got ready and went to work. As soon as I got out of the building the wet damp snow falling on my head, and face made me realize one thing, the commute would be a pain. From where I live it normally takes me about an hour and fifteen minutes to get to work downtown. Usually at eight in the morning the subway and bus routes are bearable if not half empty, which is just the way I like it. However, when it rains or snows it seems as though the city swells in population. I don't know how it happens, but I believe it's a conspiracy. Yes, I believe the city has a conspiracy to ruin my mornings. I believe everyone congregates at city hall the night before it's going to rain, and think up ways to annoy me in the morning. Let me tell you, it actually works.You might think it's the nut in me talking, but why else would so many people come outside, just when I am outside, the days when it's cold, and damp and gray, and dark?

From my bedroom window I can see the 427 South with a line of cars squeezed bumper to bumper, and I know that they will remain bumper to bumper towards the Gardener Express Way and the exit on Yonge street. So, I choose not to drive downtown when it rains. I decide instead to take the bus, and the subway. But guess what, it's also full of conspirators pushing and closing up against me. You can all tell me your reasons of why both the highways and the transit systems get packed, and I am sure they are all reasonable excuses. I know the truth though. It's a conspiracy.

Today as it was to expect the subway was overflowing with passengers. On the Bloor Street line people were elbow to elbow as cars would be bumper to bumper on the surface. The next great thing about a subway ride with these many people is the festival of smells that erupts. As soon I thought of it as a festival, the image formed in my head, and in my mind it went something like this:

Narrow wet damp streets were suddenly formed between canvas tents with blue plastic tarp roofing tide at the corners with rope. Suddenly, a cacophony of loud marketeer screams exploded.

"Cigarette butt and Channel No. 5!" A well dressed business looking woman in the tent beside me was screaming.
"Cigarette butt and Channel No. 5, here for free! Only today! Do not miss it! Just for today, because it's rainy and gray, and ugly!"

Then from another tent a little to the left of this one someone else was screaming louder. "Stale coffee and sweaty armpits. Stale coffee, and sweaty armpits everyone! Don't miss it! Only while it rains!
"Every one gather around, stale coffee and sweaty armpits!"

Meanwhile in a very small tent in front of me a blond girl with pale blue eyes and a U of T bag pack was looking up and whispering "Acqua di Parma. Acqua di Parma, " but no one could hear her.

Now, in the dynamic marketplace the cigarette butt and Channel No. 5 tent had merged with the stale coffee and sweaty armpits tent and together had made a powerful enterprise which was slowly driving every marketeer out of business.


Just then from the far right an hysteric cry silenced all others. All the other tents disapeared. There was no festival anymore. Just one person. Standing in an open road. He was wearing a suit. He was holding a briefcase. He was looking at his watch. He was annoyed. He was upset. He was late. "Baad breaaath! Baad breaaath! Baad Breaath!" Screaming in my head like a fire alarm.

Thankfully just then my stop came and I got off before I got a headache. But as I walked up the stairs of the Yonge and Bloor subway station I could still smell some of the products the festival was giving away, and I wondered if by chance they had left me with a few samples.

Experience, no experience

There is this William's Coffee Pub on Queen Street that I love going to. Of course if you knew that I have only gone there twice then you would wonder whether that's enough time for me to judge wether I like it or not. Also, if you knew me well you would know that I change my mind quite a lot and for me to go somewhere twice and still like it, it's quite an accomplishment. Good on you Williams Coffee Pub on Queen Street!
So, as I was saying, I like this place quite a lot. I like it because it has this unique feeling to it you know? It's like walking into a place with class but which it's still affordable. It's like going into a cafe' where you might find interesting people, even if you don't. It's like entering a place in Europe while you are still in Brampton. Once you walk inside it's almost impossible to miss the gigantic blackboard with the menu on it written in different colored chalk. If you are lucky and it's not crowded you might be able to get a booth along the wall where you can sit and lay back while appreciating a nice cup of coffee or a fruit smoothie, or a nice piece of cheese cake. If you are not so lucky you might still be able to find an empty table somewhere with a couple of unused chairs. It's as unique a place as any of the other dozens of Williams Coffee Pubs spread throughout the city, damn globalization! But that's a subject for another blog.

I was there the other night with my fiancée and we were having a conversation about the importance of experience in the workforce. I was having a blended coffee smoothie which I hoped would wake me up for the ride home. But turns out it didn't. With the times as they are, with people getting laidoff left and right, and resumes being done to compulsive levels; I began to think about what most dread the most. "Do I have enough experience," or from the employers' point of view "Do you have enough experience."

It seems to me that people sometimes do not realize that there is a catch in that method of thinking. I have seen for myself that there is a problem with that mentality. For an enterprise to function well, in my opinion there must be a balance. Of course you need experienced people in your staff, but it's also important that you look and hire inexperienced personnel. Experience only functions well and becomes a benefit when coupled with inexperience. If you haven't noticed, maybe you should be a little more observant, but experience in many cases means that you know a vast number of ways in which things won't work. It's fine if you don't agree with me. You think I am wrong. Just humour me for a bit. We as humans are programmed to draw parallels. If an infant tries to grab a light bulb and gets burnt, he will stay away from all types of illuminating objects while the memory lasts (do I really need to mention not to try this? ). But it also means that he might be scared to play with a safe toy which emits light.

In a strange way knowledge sometimes puts a box around us from which it can be hard to get out. The walls of the box are constructed by the parallels we draw. I remember one day I was looking for a particular book in the catalog computer at my local library. I was looking for a Chinese cooking book. I kept trying different combinations of Chinese cooking books, but I would get one hit returned along with a bunch of Italian or Spanish cooking book results.
It became noticeable perhaps through my cursing that I was struggling, and a nice Samaritan came to the rescue. I struggled not to curse as I explained the problems I was having. Finally she said, why don't you try typing China, hitting enter, and then typing cooking books. "What a moron," I thought to myself. She is trying to tell me, me, the computer scientist how a database works. If she had half a brain even if it was shrunken in pickle sauce she would still know that two different queries, that's right they are called queries, are separate entities. But to humour her, I tried it.

Lo and behold it worked!

It seems that this was a smart database which kept context, so after I keyed in China and later cooking books it returned just about every cooking book in China (there are a lot!). She didn't know how databases worked so she was open to try anything. She had no box. Me, on the other hand, well...Let's leave it at that.

If you have a bunch of people with a ton of experience trying to solve a new revolutionary problem that might require out of the box thinking, you will get a bunch of whiteboards horribly harassed and a couple of trees killed in report pages explaining why this problem can't be solved. Or, in the better cases you get solutions which cost billions of dollars, a kidney, and a squirrel. And although this is true, it doesn't mean that the experienced staff are stupid and can't figure out less expensive ways. It's just that they are blinded by previous knowledge and they have probably built a bunch of redundancies into the solution.

On the other hand if you get a bunch of people with no experience you might end up with a solution that costs twenty bucks,a squirrel, and works perfectly well on Tuesdays.

However if you combine the Chutzpa and genius that comes from the freedom of not knowing what won't work with the experience of those who know, you might end up with a product that's reasonable, cost effective, and you might spare a squirrel.
It's like this, the inexperienced people will bring the crazy ideas that range in the whole spectrum of what's possible and what isn't. That by definition must include what works. And the experienced people will bring their knowledge of what hasn't worked in the past so that mistakes are not constantly repeated, and not to reinvent the wheel.

I believe I will quit doing what I do the minute I am so experienced I can't think of anything new to do.

Now, do us all a favour and start hiring not based only on experience but on creativity and perseverance which are far greater virtues.

Almost science fiction

I was reading an article about NASA's Kepler telescope and the missions to find intelligent life in other planets and it made me think about the necessity of such misuse of resources. This is not to say that I, like many NASA critics, suggest that the space agency is a total waste of money and time. No, in fact I am a strong supporter of NASA and of scientific research. However, I have never been a great fan of extra terrestrial life exploration. I am more concerned with understanding how we function and the laws of physics which are involved in making us function in that particular way.

Searching for life in outer space is another thing, one which I don't quite support. It suffices to me to know that it is almost mathematically certain that in the billion upon billion upon billion of planets out there, there is another one just like this one and that it too, supports life. To me this is as certain as the laws of probability.

The search for life in other planets aside from being wasteful, to me lacks any visible benefit. Suppose that we were able to find another planet with intelligent life. Suppose it were close enough for us to send an expedition of scientists to explore the planet and interact with the living creatures. We now also have to suppose that we can come up with a way to communicate with them in which we won't unintentionally flash them a sign which they would interpret as the extraterrestrial equivalent of giving the middle finger, in which case our poor scientists would end up being rectally probed and shoved into an extraterrestrial state of the art Zoo. And if you believe I am talking none sense then you probably have never been prepped for a business meeting with clients of different cultures.

Looking through our history I can't say much good has come from the encounters of two civilizations. And before any of you gets sentimental and start telling me about how great the encounter of the European and the American civilization was, first try to convince native americans or try to convince me of the genocides and extermination of the many Indigenous civilizations in the Americas.

And this is just in good old Earth.