#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <math.h>
#define WELCOME_MESSAGE "Demo of Hamming encoding algorithm for 2 byte word.\n"
#define NOTIFY_MESSAGE "We count digit positions from right to left, from 1 to inf.\n"
#define ASK_INPUT_MESSAGE "Plz, input 2 chars: "
#define MESSAGES_PATTERN "%50s"
#define VERBOSE
void printBinary(int a, int n);
//Makes Two-Byte-Word from 2 characters (bytes).
unsigned short int composeTwoBytes(unsigned char c1, unsigned char c2){
return (c1 << 8) + c2;
}
//0 or 1
short int getBit(int a, short int n) {
return (a&(1 << n)) ? 1 : 0;
}
//0 or 1
//n -- is control bit number, counted **FROM RIGHT** to left.
//N-th actual position is 21-N;
//It's hard to understand all that "20-smth", "21-smth", "smth-5", I agree. //TODO rework all to same style?
short int calcControlBit(int a, short int n) {
short int ret = 0;
int pow2n = pow(2, n);
int i = pow2n;
int s;
while (i <= 21) {
for (s = 0; s < pow2n; s++) {
if (i + s > 21) break;
ret += getBit(a, 21 - (i + s) );
}
i += 2 * pow2n;
}
return ret % 2;
}
//Encodes TBW to 21-bit sequence.
//Also prints control bits, if VERBOSE is defined.
unsigned int encodeByHemming(unsigned int a) {
int tmpBit;//for some VERBOSE outputs
int exta = 0; //Extended to 21 bit seq.
int i = 20;
int st = 0;
////At first, let's extend TBW with zeroes.
while (i >= 0) {
if (21-i == pow(2, st)) {
//exta |= 0; //keep 0 here -- it's position of control bit
st++;
} else {
exta |= getBit (a, i+st-5) << i;
}
i--;
}
//Now let's fill that zeroes with actual control bits.
#ifdef VERBOSE
printf(MESSAGES_PATTERN, "Control bits calculated while encoding are: ");
#endif //VERBOSE
for(st=0; st<=4; st++){
exta |= (tmpBit = calcControlBit(exta, st)) << (21 - (int) pow(2, st));
#ifdef VERBOSE
printf("%d", tmpBit);
#endif // VERBOSE
}
#ifdef VERBOSE
printf("\n");
#endif // VERBOSE
//here we go...
return exta;
}
//Prints first (from right) N bits of integer.
//Unsafe?..
void printBinary(int a, int n) {
int i;
for (i = n - 1; i >= 0; i--) {
printf("%d", getBit(a, i));
}
printf("\n");
}
//Inverts random bit of position from 1 to countBits.
//If VERBOSE is defined, prints the position, which was inverted.
unsigned int duckUpABit(unsigned int a, short int countBits){
srand(a);
short int i = rand()%countBits;
int ret = a & ~(1 << i);
ret |= (1 << i) & ~a;
#ifdef VERBOSE
printf(MESSAGES_PATTERN, "We just messed up position #");
printf("%d\n", i+1);
#endif // VERBOSE
return ret;
}
//Decodes 21-bit-sequence and tries to fix mistake, if there is any.
//Also prints control bits and broken (as decided) position, if VERBOSE is defined
unsigned int decodeByHemming(unsigned int a){
int tmpBit; //for some VERBOSE outputs
int exta = a;
int st;
//We will need recalculation of control bits. So, while non-zero control bits can mess things up
//we need to get rid of them -- turn all c-bits to zero.
for(st=0; st<=4; st++){
exta &= ~(1<<21-(int)pow(2,st));
}
//Now let's recalculate control bits, and remember, ones, which is not equal to gotten control bits.
short int isBroken=0; //boolean
int brokenPosition=0;
#ifdef VERBOSE
printf(MESSAGES_PATTERN, "Control bits calculated while decoding are: ");
#endif // VERBOSE
for(st=0; st<=4; st++){
if((tmpBit = calcControlBit(exta,st)) != getBit(a, 21 - pow(2,st))){
isBroken = 1;
brokenPosition += pow(2,st);
}
#ifdef VERBOSE
printf("%d", tmpBit);
#endif // VERBOSE
}
#ifdef VERBOSE
printf("\n");
#endif // VERBOSE
//If recalculated c-bits differ from gotten, we decide, that only 1 bit is broken, and fix it.
if(isBroken){
int a2 = 0; //tmp
brokenPosition = 21 - brokenPosition; //yup, we count positions *FROM RIGHT*, remember
#ifdef VERBOSE
printf(MESSAGES_PATTERN, "Possibly, broken position is #");
printf("%d\n", brokenPosition+1);
#endif // VERBOSE
//Looks like some magic. Is there any simplier way to do this?.. and should I care?
a2 = a & ~(1 << brokenPosition);
a2 |= (1 << brokenPosition) & ~a;
a = a2;
}
//Let's finally forget about 5 control bits, and keep just 16.
short int twoByteWord = 0;
int i = 20;
st = 0;
while (i >= 0) {
if (i == 21 - pow(2, st)) {
//We do not need control bits anymore; ignore.
st++;
} else {
twoByteWord |= getBit (a, i) << i+st-5;
}
i--;
}
return twoByteWord;
}
//Prints character representation of TBW -- it should be clear from name ~_~
void printTBWAsChars(unsigned short int twoByteWord){
printf("%c%c\n", *((char*) &twoByteWord), * ( ((char*) &twoByteWord) + 1));
}
int main(){
printf(WELCOME_MESSAGE);
printf(NOTIFY_MESSAGE);
printf(MESSAGES_PATTERN, ASK_INPUT_MESSAGE);
int twoByteWord = composeTwoBytes(getchar(), getchar());
printf(MESSAGES_PATTERN, "Let's encode following 2-byte word: ");
printBinary(twoByteWord, 16);
int encoded = encodeByHemming(twoByteWord);
printf(MESSAGES_PATTERN, "The encoded sequence is: ");
printBinary(encoded, 21);
int messed = duckUpABit(encoded, 21);
printf(MESSAGES_PATTERN, "Now we have broken one bit. Sequence becomes: ");
printBinary(messed, 21);
int decoded = decodeByHemming(messed);
printf(MESSAGES_PATTERN, "And after decoding we have: ");
printBinary (decoded, 16);
printf(MESSAGES_PATTERN, "Character representation is: ");
printTBWAsChars(decoded);
return 0;
}
