1.1 A generic checksum algorithm The checksum algorithm that you will implement

Question

1.1 A generic checksum algorithm

The checksum algorithm that you will implement requires a key, and is illustrated in Figure 2. The

left most bit of the key is always a 1. If the length of the key is n , then the length of the checksum

string will be n-1.

To compute the checksum of a data string, given a key string, the following steps are executed.

First, the key string is aligned with the left end of the data string. If the leftmost 1 of the key string

is aligned with a 1 in the data string, we xor the key onto the data string. Otherwise, we shift the

key right until we can align its leftmost 1 with a 1 in the data string. Then, we xor again the key

onto the data string. Progressively, we eliminate the 1's from the left side of data string. We stop

when the key reaches the right end of the data string. The checksum string is made of the

n -1 rightmost remaining bits of the data string.

The checksum algorithm you are required to implement was described in Section 1.1. Recall that a

key string is a string of '0' and '1' that always starts with a '1'. The function

checksum

operates on

null terminated strings.

/**

* This function is responsible for computing

* the checksum of a string of '0' and '1' given a key string of '0' and '1'.

* The checksum is returned as a string of '0' and '1'.

*

* @param char* data_string - The null terminated data string of '0' and '1'

*

* @param char* key_string - The null terminated key string of '0' and '1'

* @param char** checksum_string - The new null terminated checksum string

* of '0' and '1' computed by this function

* @return A negative number if an error occurs (failed malloc for example)

* otherwise return 0

*/

int checksum(char* data_string, char* key_string, char** checksum_string);

Explanation / Answer

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
int checksum(char* data_string, char* key_string, char** checksum_string);
//main functiion to check the function
int main(){
   char data_string[100],key_string[100];
    cin>>data_string>>key_string;
    char* checksum_string;
   cout<<checksum(data_string,key_string,&checksum_string)<<endl;
   cout<<checksum_string<<endl;

   return 0;
}

int checksum(char* data_string, char* key_string, char** checksum_string){
   int data_size = strlen(data_string);
   int key_size = strlen(key_string);
  
   //run till right end of data_string align with key_string
   for(int i=0;i<data_size-key_size+1;i++){
       //xor would only be done when left most of key_sting align with 1 on data_string
       if(data_string[i]=='1'){
           for(int j=0,k=i;j<key_size;j++,k++)
               //xoring
               data_string[k] = ((data_string[k]-'0') ^ (key_string[j]-'0')) + '0';
       }
   }
  
   char * buffer;
   //checksum string is of size key_size-1 plus 1 for null character
   buffer = (char*) malloc (key_size);
   if(buffer==NULL) return -1;
   //copy last key_size - 1 character from data_string into checksum_string
   strcpy(buffer,data_string+data_size-key_size+1);
  
   *checksum_string = buffer;
   return 0;
}

Run:

Copy the code in file named of your choice i.e checksum.cpp
    type in terminal
        c++ checksum.cpp
        ./a.out

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.