Saturday, February 16, 2013

Easy Steps to Create a Bootable Debian Installer on a USB stick.

This instructions work on Ubuntu Linux. They should be trivial to implement on other Linux distributions:

  1. Acquire a hybrid Debian installation disk image. You can use a hybrid to both run Debian off the installation medium, or install it on the machine. Download it and save it in your machine. See this page for info on accessing Debian ISOs: http://www.debian.org/CD/
  2. Insert your USB stick into the machine. Ensure that you backup all data since it will be overwritten
  3. Execute the following command in the terminal:
    $ sudo fdisk -l
  4. Note the device file for the USB stick. If you cannot understand the output, perform the above command both before and after inserting the USB stick and note the appended file in the output. On my system it is
    $ /dev/sdb1
  5. Execute the following command:
    $ cat /path/to/debian-iso.iso > /dev/sXY
I had to execute $ su first in order to carry out the command as the root. Remember to do $ exit immediately after the command terminates. Replace /path/to/debian-iso.iso above with the actual path to the ISO you downloaded. My /dev/sXY was /dev/sdb.

Once you are done, you can restart your machine and set it to boot from the USB stick.

How Disk Encryption Works

If you hold sensitive data on your laptop, work or home computer, you may need to implement some sort of disk encryption to keep it secure. This may come in handy when you lose your laptop, or if some attacker makes away with your hard drive (a case of data theft, or some government agency..).

I'll attempt to give a high-level description of disk encryption.

The whole disk is divided into equal sized blocks. A random character string called a key is generated by the system, and is passed to an encryption function, together with the contents of each block of the disk, and the output is stored on the disk. This data therefore looks like some random gibberish without meaning.

Any person who accesses this storage device cannot derive the unconcealed form of the data.

When the block data needs to be decrypted, the stored data is passed to a decryption function, together with the key that was used in the encryption process, to derive the unconcealed version. The security of the encrypted data therefore depends on the secrecy of the key.

One way of protecting the key is to store it on an external storage device, such as a flash-drive, and this is inserted into the system whenever the owner wants to boot up the computer. Another technique is to store it on an unencrypted part of the hard drive, and protect it with a passphrase, which the owner enters at boot time to retrieve the key. In UNIX-like systems, this may be in the /boot partition.

In the latter case, the owner needs to select a strong passphrase.

Once the key is available to the system, any data that is loaded to the memory is decrypted on the fly, and any data being written to the disk is similarly encrypted. Thus, if the attacker gains access to the system while it is on, disk encryption may not help.

That is, hopefully, an understandable  high-level description of disk encryption. In real sense, the actual implementation is more complex. See the document here for details.

If you understand deeply disk encryption, feel free to correct any errors or clarify any ambiguities in the blog comments.

Sunday, February 10, 2013

Some Terms in Parallel Computing

SIMD (Single Instruction, Multiple Data) - A computer with multiple processors each of which performs the same operation on different data streams simultaneously.

MIMD (Multiple Instructions, Multiple Data) - Each processor in a multiprocessor system performs a different operation on a separate data stream simultaneously.

SPMD (Single program, Multiple Data) - A more restrictive form of MIMD where each of the different operations are of the same program.

See Flynn's taxonomy for more information on the above.

Communication Bandwidth - The maximum amount of data that can be transmitted in a unit of time.

Communication Latency - The amount of time from when a piece of data is sent, to when it is received by the target.

Message Passing - A model of interaction among processors in a multiprocessor system. A message is composed by instructions on one processor and sent to another processor through the interconnecting bus(es).

Shared Memory  - A model of interaction where the the separate processors can read and write on the same memory space, and therefore access each others data values. It could be physical where only one memory is available to all the processors, or logical, in the case where each processor has its own memory, and a request to access a non-local  memory address is converted to some form of inter-processor communication.

Aggregate Function - A model of interaction where a group of processors act together. An example is barrier synchronization, where each processor outputs a data value on reaching a barrier (a particular point in the computation process) and the communication hardware returns a value to each processor that is a function of all the values received from the processors.

SMP (Symmetric Multiprocessors) - A multiprocessor system with two or more identical processors and a single shared memory, under control of a single OS. It can be thought of as MIMD with shared memory.

Processor Affinity - The OS scheduler keeps a process on the same processor in a multiprocessor system to take advantage of locally cached data.

Shared Everything - All data structures are in shared memory.

Shared Something - Only a subset of the data structures (the ones that need to be shared) are in shared memory.

Atomicity - The concept of an uninterruptible and indivisible operation (sequence of instructions) on a data object.

Cache Coherence - maintaining identical caches of shared memory. A change on one caches should be propagated to other caches.

Mutual Exclusion - utmost one processor or process is updating a given shared object at a given time.

Gang Scheduling - Only related processes or threads are running simultaneously in a multiprocessor system at a given instance. This could be processes of one program, or situation where the input of one process depends on the output of another running at the same time.



Friday, January 25, 2013

HTML and CSS Cheatsheet

HTML Elements

Block Elements

<h1>...</h1> to <h6>...</h6> - Document headings.
<div>...</div> - Container for flow content.
<p>...</p> -  Paragraph of text.
<header>...</header> - Introductory links. (HTML5)
<nav>...</nav> - Navigational links. (HTML5)
<article>...</article> - Self contained, re-usable composition. e.g. blog post (HTML5)
<section>...</section> - Generic section of a document/article. (HTML5)
<aside>...</aside> - Related content e.g. sidebar (HTML5)
<footer>...</footer> - Footer text. (HTML5)
<blockquote>...</blockquote> - Block of quotation.
<audio>...</audio> - Sound. (HTML5)
<video>...<video> - embed video. (HTML5)
<figure>...</figure> - encapsulate an image/illustration. (HTML5)
<figcaption>...</figcaption - caption associated with a figure.
<form>...</form> - contains elements for data input.

Inline Elements

<span>...</span> - inline container.
<q>...</q> - inline quotation.
<cite>...</cite> - title of some work.
<strong>...</strong> - give text strong importance.
<em>...</em> - stress emphasis.
<a>...</a> - hyperlinks.
<img /> - images.

Form Input Elements

<input /> - text input element.
<textarea>...</textarea> - multiline plain text editing.
<select><option>...</option>...</select> - present a menu of options.
<fieldset>...</fieldset> - group input elements.
<legend>...</legend> - caption for fieldset.
<label>...</label> - caption for input element.

CSS


Box Model

float - left, right; 
clear - left, right, both;
border-radius - top-left top-right bottom-left bottom-right (length values like em, pixels etc)
margin - top right bottom left (width values)
border - width style color;
padding - top right bottom left;
width - width-value;
height - height-value;

Positioning

static - default behavior, in the flow;
relative - relative parent element, original space reserved,  in the flow;
absolute - out of flow;
fixed - relative to screen, does not move.

Font properties

font-family - family-or-generic-name;
font-size - length-value;
font-style - normal, italic, oblique;
font-variant - small-caps, normal;
font-weight - normal, bold;
line-height - normal, height-value;

Text Properties

text-align - left, right, center, justify;
text-decoration - none, underline, overline, line-through, blink;
text-indent - length-value;
text-shadow - color, x-offset, y-offset;
text-transform - capitalize, uppercase, lowercase;

Background

background-color - color;
background-image - url("value")
background-repeat - repeat, repeat-x, repeat-y, no-repeat;
background-position - x-offset y-offset

List styles

list-style-type - none, circle, disc, armenian etc
list-style-position - inside, outside;

Others

display - none, inline, block;



See Excellent tutorials at:










Sunday, December 9, 2012

Object-Oriented Programming in C

As a follow up to my previous post where I demonstrated the how to create pointers to functions in C, in this post we'll look at how to implement simple object-oriented programming in C.

The basic idea in object-oriented programming is encapsulating data and operations on the data into a single structure. Since we can create pointers to functions, we can therefore create structures that contain both data variables and functions that manipulate these data variables. We shall also see a basic form of inheritance.

In the following example, we'll create a base Animal class, and from it derive a Human class and Duck class. Take the terms class, method and attribute as used below with a pinch of salt. Object-oriented programming is implemented in different ways in the major programming languages in use.

We first create the Animal class:

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

typedef struct {
  char *description;
  void (*move)(void *self, int steps);
  void (*make_sound)(void *self);
  void (*destroy)(void *self);
  int (*init)(void *self, const char *description);
} Animal;

void Animal_move(void *self, int steps)
{
  printf("Moves %d steps\n", steps);
}


void Animal_sound(void *self)
{
  printf("Makes a sound\n");
}

void Animal_destroy(void *self)
{
  Animal *this = self;
  if (this) {
    if (this->description) free(this->description);
    free(this); 
  }
}

int Animal_init(void *self, const char *description)
{
  Animal *this = self;
  this->description = strdup(description);
  return 1;
}

void *Animal_new(Animal proto, size_t size, const char *description)
{                                                                                                                 
  if (!proto.move) proto.move = Animal_move;
  if (!proto.make_sound) proto.make_sound = Animal_sound;
  if (!proto.destroy) proto.destroy = Animal_destroy;
  if (!proto.init) proto.init = Animal_init;

  Animal *animal = calloc(1, size);
  *animal = proto; 

  int initval = animal->init(animal, description);
  if (initval)
    return animal;
  else
    return NULL;
}

#define NEW(N, d) Animal_new(N##Proto, sizeof(N), d)

Lines 5-11: Animal class, with an attribute description and methods move, make_sound, destroy and init.

Lines 13-38: Function definitions for the above Animal methods.

Lines 40-55: The object creation function. Takes in an Animal prototype, assigns methods and allocates heap memory for the object.

Line 47: The memory space allocated depends on the parameter size passed to the function. This is useful if the object is a sub-class of Animal with a bigger size. More on this later.

Line 48: Copy the contents of the prototype into the allocated space.

Line 57: Macro definition to simplify object creation syntax.

We then look at the implementation of the Human class:

typedef struct {
  Animal proto;
  char* species;
} Human;

void Human_move(void *self, int steps)
{
  printf("walkes %d strides\n", steps);
}

void Human_sound(void *self)
{
  printf("Talks\n");
}

int Human_init(void *self, const char *species)
{
  Human *h = self;
  h->species = strdup(species);
  return 1;
}

Animal HumanProto = {
  .init = Human_init,
  .make_sound = Human_sound,
  .move = Human_move 
};


Lines 1-4: Human class with Animal attributes and methods (proto), and an extra attribute species.

Lines 6-25: Function definitions for Human methods move, sound and init to override the base class definitions in Animal.

Lines 23-27: Animal prototype for Human object, with overriding methods assigned. This will be passed to the object creation function.

The same implementation for the Duck class:

typedef struct {
  Animal proto;
  char *species;
} Duck;

void Duck_move(void *self, int steps)
{
  printf("wobbles %d steps\n", steps);
}

void Duck_sound(void *self)
{
  printf("Quacks");
}

int Duck_init(void *self, const char *species)
{
  Duck *d = self;
  d->species = strdup(species);
  return 1;
}

Animal DuckProto = {
  .move = Duck_move,
  .make_sound = Duck_sound,
  .init = Duck_init 
};

And finally, the main function, which creates an object for the each the three classes:

int main()
{
  Animal AnimalProto = {};
  Animal *animal = NEW(Animal, "An animal");
  Human *human = NEW(Human, "Homo sapien");
  Duck *duck = NEW(Duck, "Anas rubripes");
  printf("%s ", animal->description);
  animal->move(animal, 5);
  animal->make_sound(animal);
  printf("%s ", human->species);
  human->proto.move(human, 5);
  human->proto.make_sound(human);
  printf("%s ", duck->species);
  duck->proto.move(duck, 5);
  duck->proto.make_sound(duck);
  return 0;
}

We shall walk through creation of the Human object to get the gist of the program.

We first create an Animal prototype HumanProto  for the Human object:

Animal HumanProto = {
  .init = Human_init,
  .make_sound = Human_sound,
  .move = Human_move 
};

The prototype is initialized with the Human init, sound and move functions.

The invocation of the NEW macro

NEW(Human, "Homo sapien");

is transformed to:

Animal_new(HumanProto, sizeof(Human), "Homo sapien");

The Animal_new function is called with HumanProto which carries with it the overriding functions. However, the size passed to it is that of type Human which is bigger than that of HumanProto (type Animal).

When execution gets to the statement

Animal *animal = calloc(1, size);

in the Animal_new function, the calloc function returns a pointer to a memory space of the size of type Human.

*animal = proto;

copies the contents of the prototype of HumanProto to the allocated memory space. Since the size of allocated space is larger than the size of the prototype, a space that exactly fits the attribute species (a pointer) of the Human class  remains.

The statement:

animal->init(animal, "Homo sapien");

then initializes the Human object's species attribute with the string "Homo sapien".

Sunday, November 25, 2012

Creating pointers to functions in C

If you have used a programming language that has first-class functions, that is, supports assigning functions to variables and passing them to other functions, like Python or JavaScript, you may wonder why such flexibility does not exist in C.

It is actually possible, and easy, to implement this in C. In this post, we shall go through
the process of creating pointers to functions.

The first thing to do is to note the function signature, i.e. the function's arguments and return type, who's pointer we want to create. In this example, we want to create a pointer to a function that accepts two integers and returns an integer.

int fptr(int x, int y);

The construct begins like a declaration of the actual function. The next step is to wrap the function name with a pointer syntax.

int (*fptr)(int x, int y);

At this point, fptr can act like a pointer to a function, and will accept a function assigned to it. We probably want to create a type so that we can create several pointers to functions. We therefore prepend typedef to the declaration.

typedef int (*fptr)(int x, int y);

fptr will now act like a type for pointers to functions that accept two integers and return an integer. Declaring a pointer to such a function is now a straight forward affair.

fptr f1, f2;

The following program listing demonstrates how pointers to two different functions with the same  function signature can be created, and how they are invoked within a program.

#include <stdio.h>

typedef int (*fptr)(int a, int b); /*pointer type to a function*/

int add(int x, int y)
{
  return x + y;
}

int sub(int x, int y)
{
  return x - y;
}

int main()
{
  fptr op1, op2; /*create two pointers and assign functions to them*/
  op1 = add;  
  op2 = sub;

  /*invoke the functions*/
  printf("op1 on %d and %d returns %d\n", 6, 5, op1(6, 5)); 
  printf("op2 on %d and %d returns %d\n", 6, 5, op2(6, 5));
  return 0;
}

Stack vs Heap in Memory Management

There are two types of memory available to a program running in a computer, the stack memory and heap memory. The operating system allocates a fixed amount of stack memory to a running program, and the heap is extra memory that may be utilized by the program if required. This is especially important to know when using a low-level language like C.

The stack is a Last In First Out (LIFO) data structure. Items can only be inserted and removed from one end. The insert action is a push, and the remove action is a pop. To access an item, all other items on top of it have to be popped from the stack.

To examine this, let's consider the following C program.

#include <stdio.h>

int add(int a, int b)
{
  return a+b;
}

int main()
{
  int x = 1;
  int y = 2;
  int sum = add(x, y);
  printf("The sum of %d and %d is %d\n", x, y, sum);
  return 0;
}

The program above calls a function add to find the sum of two integers. The variables in the main function, that is x and y, are pushed onto the stack. When the add function is called, the address of the instruction after the function call is pushed onto the stack, and the execution jumps to the first instruction in add. Variables local to the add function, a and b are also pushed onto the stack.

When the function exits, all variables local to it are popped from the stack, and are replaced by its return value, which is then assigned to the variable sum. The execution is able to continue from where it left off in the main function, since the address of the instruction to execute which had been pushed onto the stack earlier is popped off and execution continues from this address. Here, we've only discussed a high level description of what happens, actual mechanics involved will be illustrated in a later post.

Since the stack size allocated to the program is of a fixed size, there is a limit to the size of variables, and the number of nested function calls that can occur in a program. When the stack becomes full, a condition known as stack overflow occurs and the program crashes. This may happen if one allocates a very large array, or implements a function that recursively calls itself too many times (deep recursion). The case for  deep recursion is illustrated by the following C program.

#include <stdio.h>
#define MAX 1000000000 /*maximum number of times to recurse*/

int recurse(int c)
{
  printf("level %d, ", c);
  if (c < MAX)
    recurse(++c);
}

int main()
{
  recurse(1);
  return 0;
}

By experimenting with the constant MAX, one can control the number of times that the function recurse calls itself.

When there's need to create a large variable, memory from the heap can be used. Stack memory management is automatically handled by the operating system, but memory from the heap has to be manually allocated and freed by the programmer. In C, the functions malloc and free from header file  stdlib.h are used for this, as the following snippet demonstrates.

#include <stdlib.h>
...
int *ptr = (int*)malloc(sizeof(int) * 1000000); /*allocate memory for 1000000 integers*/
...
free(ptr); /*free the previously allocated memory*/
...

The programmer, however, has to be careful to free all memory manually allocated by the heap to make it available to other programs. Otherwise a memory leak occurs, where available memory in the computer decreases to an insufficient level.

The deep recursion problem can be solved by devising an iterative program, i.e. using a loop construct, instead of calling a function recursively, for some repeated computation. The technique, known as recursion removal, will be discussed in a later post.