Operating Systems Programming (Advanced) Bit Field Manipulation: A poker game in C

Problem Statement and Description:

1 Structure of the bit fields
1.1 The card bit field
As explained above only six bits are really needed to describe a playing card. However a seventh bit has been added, this is only as a matter of convenience, as you will see below it makes the card 000000002 an invalid card and thus the standard C logic tests can be used to test if a card is valid or not. As only seven bits are required you can use one byte to store the value. A C type definition of: 

typedef unsigned char card ;

would be useful to describe this new data type, as we don’t treat it as a whole but as a bit set.
The byte will have the following format, bits 0 encodes the colour, bits 1, 2, 3, & 4 encode the value and bits 5 & 6 encode the suit. Bit 7 is unused. Each of these subsections has the values as depicted in Tables 2, 3 & 4.
Following this table the Ace of Hearts would be 00000012(1) and the King of Spades would be 011110002(120). 

1.2 The pairs bit field
The second bit field is used to hold the number of pairs in a hand. It has the format that the four least significant bits (bits 0-3) contain the number of pairs contained in a hand and the four most significant bits (bits 4-7) hold the value of the card as detailed in Table 3. A C typedef of:

typedef unsigned char p a i r s ; 

will be useful here. 

2 Programming Tasks
You should begin by reading the example code carefully. It contains some hints and comments on where to fill in the blanks.
The first step will be writing a function that displays the card. You can use the various bit fields as an index to an array of strings once extracted. The arrays are:

static char ∗suits [] = {”Hearts”,”Diamonds”, ”Clubs” ,”Spades”};

static char ∗values []= {”Ace” ,”Two” ,”Three” ,”Four” , ”Five” ,”Six” ,”Seven” ,”Eight” , ”Nine” ,”Ten” ,”Jack” ,”Queen” , ”King”};

static char ∗colour []= {”Black” ,”Red”};

You should print the card as “Ace of Hearts, is Red”, with one card per line. Test your function by creating cards individually and displaying them.

Once you can display cards you should then write a function that populates a deck (array of 52) with cards. The deck should be sorted in order by suit, that is Ace to King of hearts, then diamonds etc. With some clever arithmetic you can accomplish this in one pass of the deck. Print the deck once you have populated it.

Once you have a deck, develop a method for shuffling it. As a hint investigate the C standard library functions rand() and srand(). Shuffling involves mixing the cards up so that the order is random. Print the deck a second time and check that you have actually mixed up the deck.

Now that we have a working shuffling algorithm we are ready to play cards. To keep things reasonably simple we are going to simulate a simplified version of poker. In this game 5 hands of five cards are dealt. There is no swapping of cards and the winner is determined by who has the highest pair. A pair of cards are cards that have the same value e.g. the Ace of Hearts and the Ace of Spades are a pair. The number of pairs contained in a hand, three or four of a kinds have no bearing on the result. If none of the five hands contains a pair, or two hands contain the same highest pair, the game is considered drawn.

Although traditional poker has the Ace card being a turning point, that is it can be the low card or the high card, the cards in this game have a fixed order, as described in Table 3. This means that Aces are low and can be beaten by any other pair.

You should develop a program that implements this game. Additionally you should print each of the hands sorted in order of value, print the number of pairs in each hand and if there is at least 1 pair print the value of the highest pair. Once all five hands have been printed you should indicate if there was a winner and the value of the pair that won. If there was no winner you should indicate that the game was drawn. See Figures 1 & 2 for some sample output.

Your hands should be stored in an array for ease of use and when sorting the hand you should investigate the C standard library function qsort(), which might make things easier for you. 

Now, the Solution:
While working in bit fields, first thing you need to do is figure out all the ranges, manipulation and comparisons that you are going to make. After that coding would be as smooth as knife in butter. So, lets do that.

Ranges of each deck:

(0000 0001)2  - Ace of Hearts
(0001 1001)2  - King of Hearts

(0010 0001)2  - Ace of Diamonds
(0011 1001)2  - King of Diamonds

(0100 0000)2  - Ace of Clubs
(0101 1000)2  - King of Clubs

(0110 0000)2  - Ace of Spades
(0111 1000)2  - King of Spades


Now, let us take it easy assume that deck is already populated. Let's go to printing. We need to print three things - card value (as given in array value), card suit (as given in array suit) and colour (as given in array colour).

1. How to get card value from typedef card?  -> Card value represented is represented by 1st, 2nd, 3rd and 4th byte (xxx0000x to xxx1100x). So, shift once to right, which removes the colour bit. Then bitwise & with 0x0F ( makes higher nibble zero). Now the values will be in range 0x00 to 0x0C. Take the values as index of card array. Here is how: values[ ( (card>>1) & 0x0F ) ].

2. How to get suit value from typedef card ? -> Deck value is represented by 5th and 6th byte. So, shift right by 5 bytes, then bitwise & with 0x03 (makes all other bits zero other than 0 and 1). Now the values will be 0x00 to 0x03. Use this values as index of suit array. Here is how: suits[ ( (c>>5) & 0x03 ) ]

3. How to get colour value from typedef card ? -> colour[ c & 0x01 ]

Now that we have some idea about these bitfields, lets populate the deck. Take a temporary variable 'a'. Incrementing it by one till 0x0C (0b00001100 - least significant nibble is value of king) will fill up the card values. To change the deck once 0x0C is reached, we just increment it by 3, so the result will be 0x10 (0b00010000 - the suit has been changed). o check the colour of card compare the deck values, that is bit 4 and 5 of temporary variable 'a', if value is 0x00 - Hearts, 0x10 - Diamonds. These two are colour red. So, LSB needs to be 1. So we shift 'a' left by one position and set the LSB. If the values are 0x20 - Clubs, 0x30 - Spades. These two are colour black. So we shift 'a' left by 1 position and reset LSB.

Code snippet:

char a = 0;

for (int i = 0; i<52 ; i++)

{

            if ((a & 0x30) == 0x00 || (a & 0x30) == 0x10){

                        deck[i] = (a << 1) | 0x01;

            }

            if ((a & 0x30) == 0x20 || (a & 0x30) == 0x30){

                        deck[i] = (a << 1) & 0xFE;

            }

            a++;

            if( (a & 0x0D) == 0x0D)

                        a = a+3;
}

Rest of the things: Shuffle, finding pairs, finding winning pair are pretty self explanatory. 

Here is the link of code. 

Comments are welcome. If there are any difficulties in understanding the code, comment. I will update the post. 

A dynamic password based security system

The basic block diagram of setup is as below:

So this contains two parts, one is authentication and second is security.

Here is the flow chart of how security part works.

How to detect a fast motion,  how to send an SMS in a C program are already explained in the given links.

Now, the question is how to do these things simultaneously? Well, the answer obviously is Multi-threading. There can be one main thread that continuously checks for a fast motion. There could be another thread that sends the alert text SMS, and one more which will transfer image from our machine to a central system. Threading in C can be easily understood by googling a bit. Here is the link to the source code.

Before running this code, what you will need to do is generate an ssh-key and copy it in the central machines. That way you will be allowed to scp command (copy over ssh) without typing the ssh password. Here is a link that explains it.

Second part is Authentication:

Well now, generating a passcode is like generating a random number, which explained here. Sending the generated passcode via SMS is explained here.  But, there is whole lot of other stuff here, for example starting a timer, getting the passcode “secretly”, stop getting the data after timer expires. All these processes are drawn in diagram below.

So the functions:

1.       Starting a timer, which is timer interrupt in Linux kernel, can be seen here

2.       Now, to get passcode “secretly”, you can see here

3.       To kill an application, you need to run command “kill process_id”( which is done after the timer expires)

Now all these things, are included in a git-hub project here.

Thanks for reading, comment are most welcome.

Call a User Space Application from Kernel Space Module

Hello,

Calling a user space application from kernel space is called Upcalling, and the application which is being called is termed as User Mode Helper (I dont know where to put spaces in this word..:D). Don't be afraid, it very easy. So, here is how it goes:

The first statement is an array which takes your app's name, and the command line arguments. So if you want to provide any command line arguments, replace them with NULL. Second argument is the environment that the application needs to execute (just copy paste it !!!!!). And, the third statement actually calls the app. It's a function which take the application and it's environment as arguments.

Here is a sample source code.

EDIT : Here is a full term project based on this. :)

Hope it Helped. Thanks for Reading.
Hardik Madhu

Timer Interrupt in Linux Kernel

Hello,

So, all the stuff starts with this function,

Now, all the setup is to be done in this function. First in this function, a timer is initialized by:

Here exp_timer is a variable of struct timer_list structure. This structure all the necessary information about the timer. And we are going to use the following information in our application.

If you feel confused, dont worry. Here's the explanation. The first line contains a variable named jiffies. This variable is incremented by kernel every at a definite interval given HZ. Normally HZ is 100Hz, so jiffies is incremented every 10ms. So let's I want delay of 5mins. Then just give that value to variable delay, and give that time to the structure. Now, when the timer is expired, we want a function to be called. This so we need to provide the name of function to the structure. Here, the function being do_something.

Here is a link for sample program.

EDIT : Here is a full term project based on this. :)

Hope it helped. Thanks for reading.

Hardik Madhu

A C program in Linux to send an SMS using SIM900 GSM Modem

Hello,

This is a tutorial which will show you, how you can send a Text SMS to a mobile number using a GSM Modem. Here I used GSM Modem with SIM900 inside it. If you don't know what the hell this is... then follow the link for brief description SIM900 and here is the modem which I used SIM900 GMS Modem. Sending SMS is not big deal, but it can be tricky for beginners (like it was for me when I did this).

Modems like this one works on a command list called "AT Commands". You can find a AT command list very easily by Google-ing. I will describe only those commands which are necessary to send an SMS. But, other commands (like calling, or reading SMS) are very similar so after knowing this, you will be able to do anything you want with it.

The modem as shown in ebay link has an RS232 interface. So to connect it with my computer, I used an RS232 to USB converter. Now, let's start going through the implementation.

I am a Linux user. So, to send command to GSM Modem in C (considered as Writing to a Device in Linux), you need to open it with permission to Write in it. Done by:

Okay, several things for a Linux newbie : open is a system call which opens any file in C program to read from it or write in it. The string in double quotes is not gibberish :D. When you attach any device to a Linux system, to communicate with it, Linux creates a specific file. That file is located in /dev directory. In this case, the name of file created is ttyUSB0. Now, after specifying the file to be opened, it's time to specify permissions. O_RDWR indicates that the file should be opened with Read/Write permissions. This open function returns a variable called "File Descriptor", and that will be used throughout the program to access this file.

Now, to make sure that connections are all right and devices are powered on and other stuff like that, write simple "AT" to the device. Can be done like this:

This is another system call, which writes to the already opened device, which is described by fd. Here, it first writes "AT" and then gives a carriage return, denoted by '\r'. Carriage specifies end of the command.

Here it tries to read 5 bytes from the Modem. There is something called an "Echo Mode" in modem, in this mode whatever you send in it, it will send back (and also appropriate reply to command will also be sent by the Modem). If everything is all right, it will reply with "OK". If you don't get this output, go and check things like Buad Rate, Power Levels etc.

After getting an OK signal from Modem, first thing we need to do it is set it in text mode. This is done by command "AT+CMFG=1". Done by:

Now, specify the mobile number (to which you want to send SMS).

This command will give you a prompt to write the content of SMS. In this prompt, you need to write the content and then press CTRL+Z to terminate it. At this termination entered text will be sent as SMS to the specified number. This can be done by:

'\x1A' is a backslash character which is CTRL+Z, which terminates the prompt, and sends entered text. So, our SMS is now sent. 

Here is the source code.

EDIT : Here is a full term project based on this. :)

I hope it was helpful. Thanks for reading. Leave comments.
Hardik Madhu

Generate True and Unique Random Number in a C Program

Hello,
           
Have you ever tried to generate a random number in C Program?

           
And face the problem that it gives same iterative numbers every time you run the program?

Now, let's say you need to generate a password which is different every time. How would you do it?

For example, a program like this:

would generate output like:

But there is a problem here (or the solution), to generate a "truly" random number, we need to provide unique seed to that function.

Here the question is: "What can be so unique in our world, that it will never be repeated?" And the answer is "TIME". So, current system time is provided as seed to generate truly random numbers. Code snippet:

After adding this, here is the snapshot of this program:

So, here you generated a unique random number.

Thanks for reading. Leave Comments.

EDIT : Here is a full term project based on this. :)

Hardik Madhu

Motion Detection and Speed Estimation using OpenCV

Hello Reader,

                Action Detection and Speed Estimation, this is what I wanted to do. I started making this bit in my Undergraduate final year, as a part of the curriculum. At that time I had no idea of either Computer Vision or anything related to that. I researched for quite a long time (on the Internet, of course). But all the methods that I found, were very complex and computationally very expensive. What I wanted was a very minimal system which can work "Real-Time" on very less computationally powerful devices. The device that I was targeting at that time was Raspberry Pi (a recent release at that time).

               So, finally after months of research (I had sufficient knowledge of the field, and) putting everything aside I came up with a very simple solution (and very idiotic). Estimating and tracking speed of the action was always my first goal. So keeping everything aside, I divided speed of action in two parts, "Fast" and "Not Fast".  In detecting these two things I took advantage of the capturing limit of the camera (640 * 480, 25fps). When there is a motion above some level, these kind of cameras are not able to capture and digitize it successfully.

               Considering this camera limit, lets go to the steps which I took:

1. Capture new frame and convert it to gray-scale (almost a first step everywhere)
2. Subtract previous frame from the current frame (or we can say, calculate absolute difference between previous image and current image) (yeah, this is what we do to detect motion)
3. Convert the difference image (which is gray-scale right now) to binary image using appropriate threshold (this can simplify the computation here onwards)
4. Find contours of the difference image (okay, this will help us know the boundaries of things in motion)
5. Estimate speed based on number of detected contours (you must be thinking : "HUH??")

                Okay then, let's fill in the void and try to understand the last step. Consider these sequence of images, in which the hand is moving very fast:

 

                   In the first image the hand is steady, and just about to start moving. Number of contours is 19. In second image, hand has started moving at a very fast speed. So, the camera is not able to capture it and digitize it properly. So number of contours we get is 9. Same thing is going to happen in next three images, number of contours found is 12, 10 and 9 respectively. Now, in the last image, hand has finished one cycle and has gone upwards again. Here, number of contours that we are detecting is 19.

                   These kind of events are the main base of the algorithm which estimates the speed of motion. Algorithm works this way:

1. Wait for detection of contours more than a predefined maximum contour threshold
2. Now, scan consecutive frames for number of contours
3. If number of contours is less than a minimum contour threshold, keep scanning
4. While scanning if the number of contours exceed the predefined maximum contour threshold, denote this event as a fast motion

                   Here is the source code for this application.

                   I hope you liked and enjoyed the post.

                   I am still researching for ways to detect Human Action Recognition. So all suggestions are most most most welcome.

                   Please leave comments.

EDIT : Here is a full term project based on this. :)

Thank You For Reading,
Hardik Madhu