[SOLVED] C CSE123 Discussion

CSE123 Discussion
Updated from Alexs excellent note

Example of CRC 8
Polynomial is x8+x2+x1+1
Expressed as 100000111
Lets say we want to know 1111100000 divided by our polynomial
___________ 100000111 | 1111100000
100000111 XOR
11101001
Pseudocode
Is the most significant bit in what remains 0?
If yes, shift what remains left until the leading bit is a 1.
If not, XOR the divisor with what remains.
Repeat until we have a remainder (number <= k bits long)shift left by 1 100000111 XOR111101110shift left by 1stop since we are left with 8 bits CRC 8 Computation// Function returns the remainder from a CRC calculation on a char* array of length byte_lenchar crc8(char* array, int array_len){// The most significant bit of the polynomial can be discarded in the computation, because: // (1) it is always 1// (2) it aligns with the next ‘1’ of the dividend; the XOR result for this bit is always 0char poly =0x07; //00000111char crc = array[0];int i, j;for(i = 1; i < array_len; i++){char next_byte = ith byte of array;for(j = 7; j >= 0; j){ // Start at most significant bit of next byte and work our way down
if(crcs most significant bit is 0){
left shift crc by 1;
crc = crc OR get_bit(next_byte, j); // get_bit(next_byte, j) returns the a bit in position j from next_byte
} else{ // crcs most significant bit is 1 left shift crc by 1;
crc = crc OR get_bit(next_byte, j); crc = crc XOR poly;
} }
}
return crc; }

Getting Started
You can use any common CRC polynomials
Create crc.h and crc.c. Youll need to implement:
char get_bit (char byte, int pos); // return a char with a value of 0 or 1 depending on whether the bit in the pos is 0 or 1
char crc8 (char* array, int byte_len); // or crc16, crc32 etc.
void append_crc (char* array, int array_len); // append crc remainder to the char array
int is_corrupted (char* array, int array_len); // return 1 if a frame is corrupted, otherwise return 0

Bitwise operators in C
X AND Y -> X&Y
X OR Y -> X|Y
X XOR Y -> X^Y
NOT X -> ~X
Shift X by Y bits to the left -> X< X>>Y
Bitwise operators have lower priority than comparison operators E.g. to see whether the most significant bit of a byte is 0
Wrong: if (byte & 0x80==0)
Correct: if ((byte & 0x80)==0)

Notes for Discussion 3 1. ThestructtimevalobjectinC
Struct timeval{
time_t tv_sec; //sec suseconds_t tv_usec; //microsec
}
When sending a frame, get the time and add 0.1s to it. The result records when the frame times out. Put this information into the sender queue along with the frame.
void calculate_timeout(struct timeval * timeout){ gettimeofday(timeout,NULL);//use this to get the current time timeout->tv_usec+=100000;//0.1s
if (timeout->tv_usec>=1000000){
timeout->tv_usec-=1000000;//1s
timeout->tv_sec+=1; }
}
Use time_val_usecdiff (already defined in util.c) to compute the difference for two timeval objects.

2. Sequence/acknumberwraparound
The sequence/ack number in project 1 is 8 bits (unsigned char). When its value reaches 255, it should wrap back around to 0.
For sender:
For receiver:

3. Framing
If the size of the input message is greater than that of a frame payload, you should split the message into multiple pieces.
A skeleton code to do framing:
void ll_split_head (LLnode ** head_ptr, int payload_size){ if (head_ptr == NULL || *head_ptr == NULL){
return; }
//get the message from the head of the linked list
LLnode* head = *head_ptr;
Cmd* head_cmd = (Cmd*) head -> value; char* msg = head_cmd -> message;
//do not need to split
if(strlen(msg) < payload_size){return; }int i;LLnode* curr;LLnode* next;Cmd* next_cmd;curr = head;for(i = payload_size; i < strlen(msg); i += payload_size){//TODO: malloc herechar* cmd_msg = (char*) malloc((cut_size + 1) * sizeof(char)); // One extra byte for NULL character memset(cmd_msg, 0, (payload_size + 1) * sizeof(char)); strncpy(cmd_msg, msg + i, payload_size);//TODO: fill the next_cmd//TODO: fill the next node and add it to the linked list}msg[payload_size] = ‘’;//cut the original msg }