Friday, February 24, 2012

Caesar Cipher Algorithms in C

The Caesar cipher is one of the simplest and most widely known encryption techniques. The method consists in replacing each letter with another letter who is s positions to the right, where s is a number who was fixed before.

If you want to read more about the Caesar cipher (especially the history behind it), you should probably see this.

For the C implementation we shall consider the following macrodefinitions, enumerations and libraries:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define SHIFT_MAX      26
#define NUMBER_OF_LETTERS    26
#define NUMBER_OF_DIGITS    10
#define CAESAR_CIPHER_SPECIAL_CHARS  " .!?,;:'()[]{}`"

typedef enum
{
 OPERATION_SUCCESS = 1U,
 OPERATION_FAILED  = 0U
}OPERATION_STATUS;
1. The Encryption Algorithm
We shall consider E as the encrypted ASCII string and O as the "original" ASCII string. E is calculated using the formulas displayed below:
Caesar cipher encryption formulas
  • Oi - the element at  the i-th position in the original string.
  • Ei -  the element at  the i-th position in the encrypted string.
  • M - a predefined set of elements who will not be encrypted (this set will be contained in CAESAR_CIPHER_SPECIAL_CHARS).
  • s - how many positions a letter or a digit will be shifted
  • The "magic numbers" 97, 65 and 48 represent the ASCII codes of 'a', 'A' and '0', while 26 and 10 represent the number of letters of the English alphabet respectively the number of digits. 
Example (s=3) :
The original string    : I AM CAESAR
The encrypted string: L DP FDHVDU

The C implementation:
OPERATION_STATUS CaesarCipher_Encrypt(const char* originalMessage,
                                      char* codedMessage,
                                      short shift)
{
 unsigned int size = strlen(originalMessage);
 unsigned int i = 0;
 for(i=0; i<size; i++)
 {
  if(islower(originalMessage[i]))
  {
   codedMessage[i] = (((short)(originalMessage[i]-'a') + shift)
                      %NUMBER_OF_LETTERS) + 'a';
  }
  else if(isupper(originalMessage[i]))
  {
   codedMessage[i] = (((short)(originalMessage[i]-'A') + shift)
                      %NUMBER_OF_LETTERS) + 'A';
  }
  else if(isdigit(originalMessage[i]))
  {
   codedMessage[i] = ((short)(originalMessage[i]-'0') + shift)
                      %NUMBER_OF_DIGITS + '0';
  }
  else if(strchr(CAESAR_CIPHER_SPECIAL_CHARS, originalMessage[i])!=NULL)
  {
   codedMessage[i] = originalMessage[i];
  }
  else
  {
   return OPERATION_FAILED;
  }
 }
 codedMessage[size] = '\0';
 return OPERATION_SUCCESS;
}
2. The Decryption Algorithm
We shall consider E as the encrypted string and O as the decrypted string. O is calculated using the formulas displayed below:

  • Oi - the element at  the i-th position in the decrypted string.
  • Ei - the element at  the i-th position in the encrypted string.
  • M - a predefined set of elements who will not be encypted (this set will be contained in CAESAR_CIPHER_SPECIAL_CHARS).
  • s - how many positions a letter or a digit was shifted
  • The "magic numbers" 97, 65 and 48 represent the ASCII codes of 'a', 'A' and '0', while 26 and 10 represent the number of letters of the English alphabet respectively the number of digits. 
Example (s=3) :
The encrypted string: L DP FDHVDU
The decrypted string: I AM CAESAR

The C implementation:
OPERATION_STATUS CaesarCipher_Decrypt(const char* codedMessage,
                                      char* originalMessage,
                                      short shift)
{
 unsigned int size = strlen(codedMessage);
 unsigned int i = 0;
 for(i=0; i<size; i++)
 {
  if(islower(codedMessage[i]))
  {
   originalMessage[i] = (abs((short)(codedMessage[i]-'a') - shift)
                        %NUMBER_OF_LETTERS) + 'a';
  }
  else if(isupper(codedMessage[i]))
  {
   originalMessage[i] = (abs((short)(codedMessage[i]-'A') - shift)
                        %NUMBER_OF_LETTERS) + 'A';
  }
  else if(isdigit(codedMessage[i]))
  {
   originalMessage[i] = (abs((short)(codedMessage[i]-'0') - shift))
                        %NUMBER_OF_DIGITS + '0';
  }
  else if(strchr(CAESAR_CIPHER_SPECIAL_CHARS, codedMessage[i])!=NULL)
  {
   originalMessage[i] = codedMessage[i];
  }
  else
  {
   return OPERATION_FAILED;
  }
 }
 originalMessage[size] = '\0';
 return OPERATION_SUCCESS;
}
3. Breaking the Caesar's Cipher 
Breaking Caesar's Cipher is not very complicated. For an encrypted string you have NUMBER_OF_LETTERS (normally 26) possible decrypted strings. Using the functions described above it will not be very complicated or time-consuming to generate all strings and figure out the shift value.
char coded[30] = "L dp FDHVDU 5345!!!";
char message[30];
unsigned int i = 0;
for(i=0; i<26;i++)
{
 CaesarCipher_Decrypt(coded,message,i);
 printf("%s with shift value %d\n",message,i);
}
//Output
//L dp FDHVDU 5345!!! with shift value 0
//K co ECGUCT 4234!!! with shift value 1
//J bn DBFTBS 3123!!! with shift value 2
//I am CAESAR 2012!!! with shift value 3
//H bl BBDRBQ 1101!!! with shift value 4
//G ck ACCQCP 0210!!! with shift value 5
//F dj BDBPDO 1321!!! with shift value 6
//E ei CEAOEN 2432!!! with shift value 7
//D fh DFBNFM 3543!!! with shift value 8
//C gg EGCMGL 4654!!! with shift value 9
//B hf FHDLHK 5765!!! with shift value 10
//A ie GIEKIJ 6876!!! with shift value 11
//B jd HJFJJI 7987!!! with shift value 12
//C kc IKGIKH 8098!!! with shift value 13
//D lb JLHHLG 9109!!! with shift value 14
//E ma KMIGMF 0210!!! with shift value 15
//F nb LNJFNE 1321!!! with shift value 16
//G oc MOKEOD 2432!!! with shift value 17
//H pd NPLDPC 3543!!! with shift value 18
//I qe OQMCQB 4654!!! with shift value 19
//J rf PRNBRA 5765!!! with shift value 20
//K sg QSOASB 6876!!! with shift value 21
//L th RTPBTC 7987!!! with shift value 22
//M ui SUQCUD 8098!!! with shift value 23
//N vj TVRDVE 9109!!! with shift value 24
//O wk UWSEWF 0210!!! with shift value 25
By studying the output and using your common sense, you can easily observe that the only sentence that makes sense is the one where the shift value is equal to 3.

Download source here

Sunday, February 19, 2012

HSI - RGB Conversion Algorithms in C

In order to understand this article you should probably read this article first:

If you are curious about the theory behind the HSI and RGB color spaces, you can read this articles:

1.RGB to HSI Conversion

This function will create a HSI model from a RGB model. The algorithm behind the conversion is described by the formulas below:
RGB to HSI conversion formulas
The meaning of the variables:
M - the RGB component with the greatest value
m - the RGB component with the smalles value
c - chroma
rf,gf,bf - the components of the RGB model (red, green, blue)
h,s,i - the components of HSL model (hue, saturation, intensity)

The components of the RGB model (r,g,b), saturation (S)  and intensity (I) should have values in the range [0,1], while the hue (h) should have values in the range [0,360].

The prototype of the function is:
/* Description:
 *  Creates a HsiColor structure from RGB components
 * Parameters:
 *  r,g,b - the components of an RGB model expressed
 *          as real numbers
 * Returns:
 *  A pointer to the HsiColor is the parameters are
 * correct. Otherwise returns NULL.
 */
HsiColor* Hsi_CreateFromRgbF(double r, double g, double b);
The function can be implemented as:
HsiColor* Hsi_CreateFromRgbF(double r, double g, double b)
{
    HsiColor* color = NULL;
    double m = Double_GetMinimum(r,g,b);
    double M = Double_GetMaximum(r,g,b);
    double c = M-m;
    if(RgbF_IsValid(r,g,b)==true)
    {
        color = (HsiColor*)malloc(sizeof(HsiColor));
        color->I = (1.0/3.0)*(r+g+b);
        if(c==0)
        {
            color->H = 0.0;
            color->S = 0.0;
        }
        else
        {
            if(M==r)
            {
                color->H = fmod(((g-b)/c), 6.0);
            }
            else if(M==g)
            {
                color->H = (b-r)/c + 2.0;
            }
            else if(M==b)
            {
                color->H = (r-g)/c + 4.0;
            }
            color->H *=60.0;
            color->S = 1.0 - (m/color->I);
        }
    }
    return color;
}
2.HSI to RGB Conversion 
This function will create a RGB model from a HSI model. The algorithm behind the conversion is described by the formulas below:
HSI to RGB conversion formulas
The meaning of the variables:
h, s, i - the components of the HSI model (hue, saturation, intensity)
hr - the hue component expressed in radians
k - the correcting coefficient for hr
x,y,z - intermediary values
x',y',z' - intensity-compensated intermediary values
Rf, Gf, Bf - the components of the RGB model (red, green blue)

The components of the RGB model (r,g,b), saturation (S) and intensity (I) should have values in the range [0,1], while the hue (h) should have values in the range [0,360].

The prototype of the function is:
/*
 * Description:
 *  Creates a RgbFColor structure from HSI components
 * Parameters:
 *  h,s,i - the components of an HSI model expressed
 *          as real numbers
 * Returns:
 *  A pointer to the RgbFColor is the parameters are
 * correct. Otherwise returns NULL.
 */
RgbFColor* RgbF_CreateFromHsi(double h, double s, double i);
The function can be implemented as:
RgbFColor* RgbF_CreateFromHsi(double h, double s, double i)
{
    RgbFColor* color = NULL;
    if(Hsi_IsValid(h,s,i)==true)
    {
        color = RgbF_Create(0.0,0.0,0.0);
        if(h>=0.0 && h<=(HUE_UPPER_LIMIT/3.0))
        {
            color->B = (1.0/3.0)*(1.0-s);
            color->R = (1.0/3.0)*((s*cos(h))/cos(60.0-h));
            color->G = 1.0-(color->B + color->R);
        }
        else if(h>(HUE_UPPER_LIMIT/3.0) && h<=(2.0*HUE_UPPER_LIMIT/3.0))
        {
            h-=(HUE_UPPER_LIMIT/3.0);
            color->R = (1.0/3.0)*(1.0-s);
            color->G = (1.0/3.0)*((s*cos(h))/cos(60.0-h));
            color->B = 1.0-(color->G + color->R);

        }
        else /* h>240 h<360 */
        {
            h-=(2.0*HUE_UPPER_LIMIT/3.0);
            color->G = (1.0/3.0)*(1.0-s);
            color->B = (1.0/3.0)*((s*cos(h))/cos(60.0-h));
            color->R = 1.0-(color->G + color->B);
        }
    }
    return color;
}
3. Example
#include<stdio.h>
#include"colorspace.h"

int main(int argc, char** argv)
{
    HsiColor* hsi = NULL;
    RgbFColor* rgbF = NULL;
    RgbIColor* rgbI = NULL;

    /*HSI to RGB*/
    hsi = Hsi_Create(30.0, 0.3, 0.2);
    rgbF = RgbF_CreateFromHsi(hsi->H, hsi->S, hsi->I);
    rgbI = RgbI_CreateFromRealForm(rgbF->R, rgbF->G, rgbF->B);
    printf("\nHSI : %f %f %f", hsi->H, hsi->S, hsi->I);
    printf("\nRGBf : %f %f %f", rgbF->R, rgbF->G, rgbF->B);
    printf("\nRGBi : %d %d %d", rgbI->R, rgbI->G, rgbI->B);

    /*Frees the resources*/
    free(hsi);
    free(rgbF);
    free(rgbI);

    /*RGB to HSI*/
    rgbI = RgbI_Create(34U, 50U, 98U);
    rgbF = RgbF_CreateFromIntegerForm(rgbI->R, rgbI->G, rgbI->B);
    hsi = Hsi_CreateFromRgbF(rgbF->R, rgbF->G, rgbF->B);
    printf("\nHSI : %f %f %f", hsi->H, hsi->S, hsi->I);
    printf("\nRGBf : %f %f %f", rgbF->R, rgbF->G, rgbF->B);
    printf("\nRGBi : %d %d %d", rgbI->R, rgbI->G, rgbI->B);
    return 0;
}
/*
 HSI : 30.000000 0.300000 0.200000
 RGBf : 0.100000 0.666667 0.233333
 RGBi : 26 170 60
 HSI : 225.000000 0.439560 0.237909
 RGBf : 0.133333 0.196078 0.384314
 RGBi : 34 50 98
 */

The Colorspace Conversions Library

The purpose of this library is to provide functions and data structures for color space conversion operations.

In order operate more easily with the components of the color spaces we shall define every color space as a structure.
Color space Structure Members
RGB RgbFColor double R,G,B
RGB RgbIColor uint8_t R,G,B
HSI HsiColor double H,S,I
HSL HslColor double H,S,L
HSV HsvColor double H,S,V
YIQ YiqColor double Y,I,Q
YUV YuvColor double Y,U,V

The RgbIColor is associated with the RGB color space model and it will contain the R,G,B components expressed as natural numbers in the range [0,255].

The RbgFColor is associated with the RGB color space model and it will contain the R,G,B components expressed as real numbers in the range [0.0, 1.0].

The HslColor is associated with the HSL color space model and it will contain the H,S,L components expressed as real numbers where H is in the range [0.0, 360.0] and S and L are in the range [0.0, 1.0].

The HsvColor is associated with the HSV color space model and it will contain the H,S,V components expressed as real numbers where H is in the range [0.0, 360.0] and S and V are in the range [0.0, 1.0].

The HsiColor is associated with the HSI color space model and it will contain the H,S,I components expressed as real numbers where H is in the range [0.0, 360.0] and S and I are in the range [0.0, 1.0].

The YiqColor is associated with the YIQ color space model and it will contain the Y,I,Q components expressed as real numbers where Y is in the range [0.0, 1.0], I is in the range [-0.5957, 0.5957], Q is in the range [-0.5226, 0.5226].

The YuvColor is associated with the YUV color space model and it will contain the Y,U,V components expressed as real numbers where Y is in the range [0.0, 1.0], U is in the range [-0.436, 0.436], Q is in the range [-0.615, 0.615].

We shall also define the following functions which will be used for the conversion algorithms:
/*
 * Description:
 *  Checks if a value is within a specified interval
 * Parameters:
 *  value - the value who is checked
 *  lowerLimit - the lower limit of the interval
 *  upperLimit - the upper limit of the interval
 * Returns:
 *  true if the value is within the interval
 *  false if the value is not within the interval
 */
bool RealIsWithinBounds(double value, double lowerLimit, double upperLimit);
/*
 * Description:
 *  Checks if a value is within a specified interval
 * Parameters:
 *  value - the value who is checked
 *  lowerLimit - the lower limit of the interval
 *  upperLimit - the upper limit of the interval
 * Returns:
 *  true if the value is within the interval
 *  false if the value is not within the interval
 */
bool IntegerIsWithinBounds(uint8_t value, uint8_t lowerLimit, uint8_t upperLimit);
/*
 * Description:
 *  Returns the smallest of the three parameters
 * Parameters
 *  r,g,b - 3 real numbers
 * Returns
 *  The smallest real number from the set {r,g,b}
 */
double Double_GetMinimum(double r, double g, double b);
/*
 * Description:
 *  Returns the largest of the three parameters
 * Parameters
 *  r,g,b - 3 real numbers
 * Returns
 *  The largest real number from the set {r,g,b}
 */
double Double_GetMaximum(double r, double g, double b);

/*
 * Description:
 *  Checks if the RGB components are valid
 * Parameters:
 *  r,g,b - the components of an RGB model expressed
 *          as real numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool RgbF_IsValid(double r, double g, double b);
/*
 * Description:
 *  Checks if the HSI components are valid
 * Parameters:
 *  h,s,i - the components of an HSI model expressed
 *          as real numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool Hsi_IsValid(double h, double s, double i);
/*
 * Description:
 *  Checks if the RGB components are valid
 * Parameters:
 *  r,g,b - the components of an RGB model expressed
 *          as natural numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool RgbI_IsValid(uint8_t r, uint8_t g, uint8_t b);
/*
 * Description:
 *  Checks if the HSL components are valid
 * Parameters:
 *  h,s,l - the components of an HSL model expressed
 *          as real numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool Hsl_IsValid(double h, double s, double l);
/*
 * Description:
 *  Checks if the HSV components are valid
 * Parameters:
 *  h,s,v - the components of an HSV model expressed
 *          as real numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool Hsv_IsValid(double h, double s, double v);
/*
 * Description:
 *  Checks if the YIQ components are valid
 * Parameters:
 *  y,i,q - the components of an YIQ model expressed
 *          as real numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool Yiq_IsValid(double y, double i, double q);
/*
 * Description:
 *  Checks if the YUV components are valid
 * Parameters:
 *  y,u,v - the components of an YUV model expressed
 *          as real numbers
 * Returns:
 *  true if the values are correct
 *  false if the values are incorrect
 */
bool Yuv_IsValid(double y, double u, double v);
If you want to view the implementation of these functions, see the links below:

Saturday, February 4, 2012

PCM A-law and u-law Companding Algorithms in ANSI C

The Pulse Code Modulation (PCM), also known as G.711, is a very commonly used waveform codec, especially for audio companding in telephony. PCM is based on an non-uniform 8 bits quantization who is used for representing each sample took from an continuous (analog) signal.

Currently, there two slightly different versions of G.711:
  • µ-Law (used in North America and Japan)
    • Advantage: Provides a larger range for signals
    • Disadvantage: It's not as a good as the A-Law when it comes to low-amplitude signals 
  • A-Law (used in Europe and the rest of the world)
    • Advantage: It's good for low-amplitude signals
    • Disadvantage : It has a significantly smaller range than the µ-Law
The term companding was formed from the words compressing and expanding, and it refers to the process in which a signal is compressed (the range of the signal is reduced) and then expanded (the signal returns to a form similar to form before he was compressed).

If you want to know more about G.711 and the mathematics behind it, you should read:

1. A-Law implementation

1.1. A-Law Compression (Encoding) Algorithm
int8_t ALaw_Encode(int16_t number)
{
   const uint16_t ALAW_MAX = 0xFFF;
   uint16_t mask = 0x800;
   uint8_t sign = 0;
   uint8_t position = 11;
   uint8_t lsb = 0;
   if (number < 0)
   {
      number = -number;
      sign = 0x80;
   }
   if (number > ALAW_MAX)
   {
      number = ALAW_MAX;
   }
   for (; ((number & mask) != mask && position >= 5); mask >>= 1, position--);
   lsb = (number >> ((position == 4) ? (1) : (position - 4))) & 0x0f;
   return (sign | ((position - 4) << 4) | lsb) ^ 0x55;
}
First, the number is verified is its negative. If the number is negative he will be made positive and the sign  variable (by default 0) will contain the value 0x80 (so when it's OR-ed to the coded result it will determine it's sign).

Since the A-Law algorithm considers numbers in the range 0x000 - 0xFFF (without considering the sign bit), if a number is bigger than 0xFFF, it will automatically made equal to 0xFFF in order to avoid further problems.

The first step in determining the coded value is finding the position of the first bit who has a 1 value (excluding the sign bit). The search is started from position 11 and is continued until a bit with the value 1 is find or until a position smaller than 5 is met.

If the position is smaller than 5 (there was no 1 bit found on the positions 11-5),  the least significant byte of the coded number is made equal the the bits 5,4,3,2 of the original number. Otherwise the least significant bit of the coded number is equal to the first four bits who come after the first 1 bit encountered.

In the end, the most significant byte of the coded number is computed according to the position of the first 1 bit (if not such this was found, then the position is considered).

Also, before returning the result, the even bits of the result will be complemented (by XOR-ing with 0x55).

1.2.A-Law Expanding (Decoding) Algorithm
/*
 * Description:
 *  Decodes an 8-bit unsigned integer using the A-Law.
 * Parameters:
 *  number - the number who will be decoded
 * Returns:
 *  The decoded number
 */
int16_t ALaw_Decode(int8_t number)
{
   uint8_t sign = 0x00;
   uint8_t position = 0;
   int16_t decoded = 0;
   number^=0x55;
   if(number&0x80)
   {
      number&=~(1<<7);
      sign = -1;
   }
   position = ((number & 0xF0) >>4) + 4;
   if(position!=4)
   {
      decoded = ((1<<position)|((number&0x0F)<<(position-4))
                |(1<<(position-5)));
   }
   else
   {
      decoded = (number<<1)|1;
   }
   return (sign==0)?(decoded):(-decoded);
}
The first thing the decoding algorithm does is to complement the even bits of the coded number (since they were complemented in the coding part, complementing them again would "bring them to normal").

The next step is to verify if the number is negative by checking if the 8th bit is set (if it's set, the number is negative). If the number is negative, the variable named sign (who is used like a flag/boolean) is set to -1 and the number is made positive by clearing the 8th bit.

As you probably observed, I used a more complicated algorithm for checking the negativity of the number - I had to do this because my compiler had (and perhaps your would've had) problems with 8 bit variables and a statement like number=-number raises some problems.

The next thing we need in order to decode the number is to determine the position we calculated in encoding algorithm. The position is calculated as the sum between the value represented by the most significant byte of the coded number and 4.

The final step consists in actually decoding the number. The number will have its first 1 bit at the position determined before, the next four bits will be equal to the least significant byte of the coded number and the next bit following them will be automatically set to 1. If the position determined is smaller than 5, the position bit will not be set automatically (but the last 1 bit will).

Before returning the number, if the number is negative he will have it sign added.

2.µ-Law Implementation

2.1. µ-Law Compression (Encoding) Algorithm
int8_t MuLaw_Encode(int16_t number)
{
   const uint16_t MULAW_MAX = 0x1FFF;
   const uint16_t MULAW_BIAS = 33;
   uint16_t mask = 0x1000;
   uint8_t sign = 0;
   uint8_t position = 12;
   uint8_t lsb = 0;
   if (number < 0)
   {
      number = -number;
      sign = 0x80;
   }
   number += MULAW_BIAS;
   if (number > MULAW_MAX)
   {
      number = MULAW_MAX;
   }
   for (; ((number & mask) != mask && position >= 5); mask >>= 1, position--)
        ;
   lsb = (number >> (position - 4)) & 0x0f;
   return (~(sign | ((position - 5) << 4) | lsb));
}
The µ-Law compression algorithm is very similar to the A-Law compression algorithm.The main difference is that the µ-Law uses 13 bits instead of 12 bits, so the position variable will be initialized with 12 instead of 11. In order to make sure that there will be no number without a 1 bit in the first 12-5 positions, a bias value is added to the number (in this case 33). So, since there is no special case (numbers who do not have a 1 bit in the first 12-5 positions), this makes the algorithm less complex by eliminating some condtions.

Also in the end all bits are complemented, not just the even ones.

2.1. µ-Law Expanding (Decoding) Algorithm
int16_t MuLaw_Decode(int8_t number)
{
   const uint16_t MULAW_BIAS = 33;
   uint8_t sign = 0, position = 0;
   int16_t decoded = 0;
   number = ~number;
   if (number & 0x80)
   {
      number &= ~(1 << 7);
      sign = -1;
   }
   position = ((number & 0xF0) >> 4) + 5;
   decoded = ((1 << position) | ((number & 0x0F) << (position - 4))
             | (1 << (position - 5))) - MULAW_BIAS;
   return (sign == 0) ? (decoded) : (-(decoded));
}

As well as the compression algorithm, the expanding algorithm is also very similar to the A-Law expanding algorithm. The differences are that in the beginning all bits are complemented (not only the even ones) and the position is calculated as the value of the coded number most significant byte plus 5 instead of 4 (since the µ-Law uses 13 bits). Also, before the number is returned, the bias is subtracted.

Related Posts Plugin for WordPress, Blogger...