Endianness
I found a paper about endianness while I was looking on Intel's developer documentations. I have been wondering what kind of advantages can be gained to store the data in little endian or big endian format. There are some explained advantages and disadvantages in that document. However, I haven't been enough convinced with these explanations. I think there are many others related to CPU and hardware design.
Anyway, that document well describes the endianness and the portability issues. It should be read if you have got some questions in mind.
I implemented a function which checks the endiannes of the CPU on run time. It is possible to decide the architecture by comparing one byte. However, I like to perform strict check on multi-byte data.
Here is the link of the Intel's document.
union {
char array[sizeof(int)];
int intVal;
} testUnion;
int main()
{
int i, bigEndVal = 0, littleEndVal = 0;
char c = 'a';
for(i = 0; i < sizeof(int); i++) {
testUnion.array[i] = c;
bigEndVal = (bigEndVal << 8) | c;
littleEndVal = littleEndVal | (c << 8 * i);
c++;
}
if (testUnion.intVal == bigEndVal)
printf("Big Endian\n");
else if (testUnion.intVal == littleEndVal)
printf("Little Endian\n");
else
printf("Unknown\n");
return 0;
}
C++, Functions That Return Two Values
I am going to explain the class pair that is provided to treat two values as one. The class pair is used several times in STL. The container classes map and multimap use the class pair to handle the key/value pairs. The other usage of the pair class is functions that return two values. I choose the title as 'Functions That Return Two Value' instead of 'The class pair' because it sounds much more attractive since developers used to hear functions can return one value.
The pair structure is defined in <utility> as follows;
template<class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 fist;
T2 second;
pair() : first(T1()), second(T2()) {}
pair(const T1& val1, const T2& val2) : first(val1), second(val2) {}
template<class Other1, class Other2>
pair(const pair<Other1, Other2>& p) : first(p.first), second(p.second) {}
};
}
The pair is defined as struct. Therefore, accessing the members (first and second) is possible. The definition is short and straightforward. However, the template version of the copy constructor may seen confusing. The template copy constructor is called whenever implicit conversion is needed. There are many good books about C++, STL and Templates, two of them are as follows;
1. C++ Primer, by Stanley B. Lippman, Josée LaJoie, Barbara E. Moo
2. The C++ Standard Library: A Tutorial and Reference, by Nicolai M. Josuttis
The make_pair() template function makes the life easier by creating the pair without explicit types.
template<class T1, class T2>
make_pair(const T1& val1, const T2& val2)
{
return pair<T1, T2>(val1, val2);
}
}
In conclusion, here is an example of function that returns two values, including use of the pair class and make_pair function.
#include <iostream>
#include <utility>
using namespace std;
const double PI = 3.14;
pair<double, double> areaAndCircumferenceOfCircle(double r)
{
return make_pair((PI * r * r), (2 * PI * r));
}
int main(int argc, char *argv[])
{
pair<double, double> circle;
circle = areaAndCircumferenceOfCircle(5);
cout << "Area: " << circle.first << endl;
cout << "Circumference: " << circle.second << endl;
return 0;
}
Peterson’s n-Process Protocol
Peterson's Solution is a classic software based solution to the critical-section problem. Peterson's original formulations works for 2 processes. However, it is possible to implement it for more than 2 processes.
The following code works for 2 processes and it can be found easily on the Internet.
#define TRUE 1
int turn;
int interested[2];
void enterRegion(int process)
{
int other = 1 - process;
interested[process] = TRUE;
turn = process;
while (interested[other] == TRUE && turn == process)
;
}
void leaveRegion(int process)
{
interested[process] = FALSE;
}
Unfortunately, there aren't many resources about n-Process Peterson solution. I think one of the good explanation can be found in "Operating Systems Review, January 1990 ('Proof of a Mutual Exclusion Algorithm', M Hofri)".
I just like to show the following implementation of Peterson's n-Process Protocol.
#define N 10 /* First process is indicated with 1, not 0 */
int turn[N];
int stage[N + 1];
void enterRegion(int process)
{
int i, j;
for (i = 1; i <= N - 1; i++) {
stage[process] = i;
turn[i] = process;
for (j = 1; j <= N; j++) {
if (j == process)
continue;
while (stage[j] >= i && turn[i] == process)
;
}
}
}
void leaveRegion(int process)
{
stage[process] = FALSE;
}
Note: There are N processes from 1 to N. Therefore we need a turn array with size N - 1 and we need a stage array with size N. However, I declared the turn and the stage arrays with sizes N and N + 1 respectively. It is just because I like to keep the code clean. I don't want to subtract 1 like turn[i - 1]. I ignore the first elements -turn[0] and stage[0]- and never access them.
Tower of Hanoi
The tower of Hanoi is a mathematical game invented by French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs.
The objective is to transfer entire tower A to the peg B, moving only one disk at a time and never moving a larger one onto a smaller one.
The algorithm to transfer n disks from A to B in general: We first transfer n - 1 smallest disks to peg C, then move the largest one to the peg B and finally transfer the n - 1 smallest back onto largest (peg B).
The number of necessary moves to transfer n disks can be found by
Tn = 2^n - 1
Here is the sample solution in C:
void hanoi(int n_disks, char source, char destination, char temp)
{
static n_move = 0;
if (n_disks == 1) {
printf("%d - Move disk 1 from %c to %c\n", ++n_move, source, destination);
} else {
hanoi(n_disks - 1, source, temp, destination);
printf("%d - Move disk %d from %c to %c\n", ++n_move, n_disks, source, destination);
hanoi(n_disks -1, temp, destination, source);
}
}
int main(int argc, char *argv)
{
int n_disk = 8;
char source = 'A';
char destination = 'B';
char temp = 'C';
hanoi(n_disk, source, destination, temp);
return 0;
}