CSC209 Assignment 2

crc16.c

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

#include "data.h"

// based on code from:
// http://stackoverflow.com/questions/111928/is-there-a-printf-converter-to-print-in-binary-format?rq=1

const char *to_binary(int x) {
    static char bits[17];
    bits[0] = '\0';
    int z;
    for (z = 1 << 15; z > 0; z >>= 1) {
        strcat(bits, ((x & z) == z) ? "1" : "0");
    }
    return bits;
}


/*
 Process one bit of the message.
 reg: register (modified by this function)
 key: CRC16 key being used
 next_bit: next bit of message
 */

void crc_bit(unsigned short *reg, unsigned int key, unsigned int next_bit) {
    int sig_bit = *reg >> 15;
    *reg = (*reg << 1) | next_bit;
    if (sig_bit)
        *reg ^= key;
}

/*
 Process one byte of the message.
 reg: register (modified by this function)
 key: CRC16 key being used
 next_byte: next byte of message
 */

void crc_byte(unsigned short *reg, unsigned int key, unsigned char next_byte) {
    int i;
    for (i = 8 * sizeof(next_byte) - 1; i >= 0; i--) {
        // Iterate in reverse to start with the most significant bit
        unsigned int next_bit = (next_byte >> i) & 1;
        crc_bit(reg, key, next_bit);
    }
}


/*
 Process an entire message using CRC16 and return the CRC.
 key: CRC16 key being used
 message: message for which we are calculating the CRC.
 num_bytes: size of the message in bytes.
 */

unsigned short crc_message(unsigned int key, unsigned char *message, unsigned int num_bytes) {
    unsigned short reg = 0;
    int i;
    for (i = 0; i < num_bytes; i++)
        crc_byte(&reg, key, message[i]);
    for (i = 0; i < 16; i++)
        crc_bit(&reg, key, 0);
    return reg;
}


/*testing code*/

//int main(void) {
//    unsigned short reg = 0;
//    crc_byte(&reg, XMODEM_KEY, 0x64);
//    // Expecting *reg == 0x2c22 == 11298
//    
//    unsigned short crc16 = crc_message(XMODEM_KEY, "d", 1);
//    printf("%s\n", to_binary(crc16));
//    
//    return 0;
//}

data.h

/* Functions and type declarations for the CRC code */
#define XMODEM_KEY 0x1021

unsigned short crc_message(unsigned int key, unsigned char *message, unsigned int num_bytes);


/* Function and type declarations for packets */

#define MAXSIZE 256
struct packet {
    unsigned short block_num;
    unsigned short block_size;
    unsigned short crc;
    unsigned char *payload;
};

/* Packet function declarations */

unsigned char *create_block();
struct packet *create_empty_packet();
struct packet *create_packet(unsigned short block_num, unsigned short block_size, unsigned short crc, unsigned char *payload);


/* Function and type declaration for list of packets */

struct list {
	struct packet p;
	struct list *next;
};

/* List function declarations */

void print_list(struct list *head);
struct list *create_node(struct packet *packet);
struct list *create_block_node(unsigned short block_size, unsigned short crc, unsigned char *payload);
struct list *add_packet(struct list *node, struct packet *packet);
struct list *add_block(struct list *node, unsigned short block_size, unsigned short crc, unsigned char *payload);
struct list *insert_packet_in_order(struct list **head, struct packet *packet);

void free_node(struct list *node);
void free_list(struct list *head);


/* Log messages */

#define INSERTED 0
#define CRC_MATCH 1
#define CRC_NO_MATCH 2
#define DUPLICATE 3

/* logfp is a global variable because it is used inside other functions.
 * We could pass it in as a parameter to the functions that call log_message
 * but since it is nice to see the logging happen in the background, it seems
 * reasonable to make the file pointer a global variable.
 */
extern FILE *logfp;
void log_message(struct packet *p, int message_no, FILE *logfp);

list.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "data.h"


char *messages[] = {
	"inserted packet",
	"CRC code matches",
	"CRC code does not match",
	"duplicate block"
};

void log_message(struct packet *p, int message_no, FILE *logfp) {
    if (logfp != NULL)
        fprintf(logfp, "%hu\t%hu\t%s\n", p->block_num, p->block_size, messages[message_no]);
}

/*
 * Print the packet and payload contained in the specified node to stdout.
 */
void print_node(struct list *node) {
    printf("%.*s", node->p.block_size, node->p.payload);
}

/*
 * Print each node in the linked list with the specified head.
 */
void print_list(struct list *head) {
    struct list *current = head;
    unsigned int previous_block_num = 0;
    while (current != NULL) {
        // Print "###" for each missing packet
        int i;
        for (i = previous_block_num; i < current->p.block_num; i++)
            printf("###");
        
        // Print the current node
        print_node(current);
        
        // Advance to the next node
        previous_block_num = current->p.block_num;
        current = current->next;
    }
}

/*
 * Allocate memory for a payload block and return it.
 */
unsigned char *create_block() {
    unsigned char *block = malloc(MAXSIZE);
    if (block == NULL) {
        perror("malloc: failed to allocate block");
        exit(1);
    }
    return block;
}

/*
 * Allocate memory for a new packet and return it.
 */
struct packet *create_empty_packet() {
    struct packet *packet = malloc(sizeof(struct packet));
    if (packet == NULL) {
        perror("malloc: failed to allocate packet");
        exit(1);
    }
    return packet;
}

/*
 * Allocate memory for a new packet, set its properties, and return it.
 */
struct packet *create_packet(unsigned short block_num,
                             unsigned short block_size,
                             unsigned short crc,
                             unsigned char *payload) {
    struct packet *packet = create_empty_packet();
    packet->block_num = block_num;
    packet->block_size = block_size;
    packet->crc = crc;
    packet->payload = payload;
    return packet;
}

/*
 * Create and return a new node with the specified packet
 */
struct list *create_node(struct packet *packet) {
    struct list *node = malloc(sizeof(struct list));
    if (node == NULL) {
        perror("malloc: failed to allocate node");
        exit(1);
    }
    node->p = *packet;
    node->next = NULL;
    return node;
}

/*
 * Create and return a new node with a packet created from the specified block parameters.
 */
struct list *create_block_node(unsigned short block_size, unsigned short crc, unsigned char *payload) {
    struct packet *packet = create_packet(0, block_size, crc, payload);
    struct list *node = create_node(packet);
    free(packet);
    return node;
}

/*
 * Add the specified packet as a new node after the specified node and return the newly-created node.
 */
struct list *add_packet(struct list *node, struct packet *packet) {
    return (node->next = create_node(packet));
}

/*
 * Construct a packet from the specified parameters,
 * add it as the next node to the specified node and return the newly-created node.
 */
struct list *add_block(struct list *node, unsigned short block_size, unsigned short crc, unsigned char *payload) {
    struct packet *packet = create_packet(node->p.block_num + 1, block_size, crc, payload);
    struct list *new_node = add_packet(node, packet);
    free(packet);
    return new_node;
}

/*
 * Insert the specified packet into the linked list with the specified head, in order of block_num.
 * Return the newly-inserted node.
 */
struct list *insert_packet_in_order(struct list **head, struct packet *packet) {
    struct list *current = *head;
    struct list *previous = NULL;
    while (current != NULL) {
        if (current->p.block_num == packet->block_num) {
            // Duplicate block found; log message
            log_message(packet, 3, logfp);
            
            // Create new node to replace the current node
            struct list *node = create_node(packet);
            node->next = current->next;
            if (previous != NULL) {
                // Insert the packet between the previous node and the current node
                previous->next = node;
            } else {
                // Insert the packet at the head of the list
                *head = node;
            }
            
            // Free the lost node
            free_node(current);
            
            // Done inserting this packet
            return node;
        } else if (current->p.block_num > packet->block_num) {
            // Current node's block_num > packet->block_num
            struct list *node = create_node(packet);
            node->next = current;
            if (previous != NULL) {
                // Insert the packet between the previous node and the current node
                previous->next = node;
            } else {
                // Insert the packet at the head of the list
                *head = node;
            }

            return node;
        } else {
            // Current node has block_num < packet->block_num;
            if (current->next != NULL) {
                // Advance to next node
                previous = current;
                current = current->next;
            } else {
                // All existing nodes have block_num < packet->block_num; insert at end of list
                return (current->next = create_node(packet));
            }
        }
    }
    return NULL;
}

/*
 * Frees dynamically-allocated memory used by the specified node.
 */
void free_node(struct list *node) {
    free(node->p.payload);
    free(node);
}

/*
 * Frees all dynamically-allocated memory used by the linked list with the specified head node.
 */
void free_list(struct list *head) {
    struct list *current = head;
    while (current != NULL) {
        struct list *next = current->next;
        free_node(current);
        current = next;
    }
}

Makefile

# The first rule is what is executed when you run make with no arguments
# In this case it will build two programs.
all : packetize readstream

# The executable program depends on the .o files.
# The compile line links all the .o files together to create the executable.
packetize : packetize.o crc16.o list.o
	gcc -Wall -g -o packetize packetize.o list.o crc16.o

readstream : readstream.o crc16.o list.o
	gcc -Wall -g -o readstream readstream.o list.o crc16.o


# Each individual source file depends on itself plus the header file
# Each source file can be separately compiled to produce a .o file
# that will be linked together to create the executable.
crc16.o : crc16.c data.h
	gcc -Wall -g -c crc16.c

list.o : list.c data.h
	gcc -Wall -g -c list.c

packetize.o : packetize.c data.h
	gcc -Wall -g -c packetize.c

readstream.o : readstream.c data.h
	gcc -Wall -g -c readstream.c

clean :
	rm *.o packetize readstream

packetize.c

#include <stdio.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <unistd.h>

#include "data.h"

FILE *logfp = NULL;

/*
 * Create a linked list of packets from raw bytes in file infp and return the head of the list.
 */
struct list *create_packet_list(FILE *infp) {
    struct list *packets = NULL;
    struct list *current = NULL;
    
    // Allocate an extra byte for the null character
    unsigned char *block = create_block();
    unsigned short block_size;
    
    while ((block_size = fread(block, sizeof(unsigned char), MAXSIZE, infp)) != 0) {
        if (ferror(infp)) {
            perror("fread: error reading block from file");
            exit(1);
        }
        
        unsigned short crc = crc_message(XMODEM_KEY, block, (unsigned int) block_size);
        if (packets == NULL) {
            packets = create_block_node(block_size, crc, (unsigned char *) block);
            current = packets;
        } else {
            // Add the block as a new node current->next
            add_block(current, block_size, crc, (unsigned char *) block);
            current = current->next;
        }
        block = create_block();
    }
    
    // Done creating list; free last block
    free(block);
    
    return packets;
}

/*
 * Write each packet and payload in the specified linked list to the file outfp
 */
void write_packet_list(FILE *outfp, struct list *packets) {
    struct list *current = packets;
    while (current != NULL) {
        // Write the struct packet
        fwrite(&(current->p), sizeof(struct packet), 1, outfp);
        if (ferror(outfp)) {
            perror("fread: error writing packet struct");
            exit(1);
        }
        
        // Write the payload
        fwrite(current->p.payload, sizeof(unsigned char), current->p.block_size, outfp);
        if (ferror(outfp)) {
            perror("fread: error writing payload");
            exit(1);
        }
        
        current = current->next;
    }
}


/* Read a file, break it into packets. */

/*
 * Notes: getopt is a useful library function to make it easier to read in
 * command line arguments, especially those with options. Read the man page
 * (man 3 getopt) for more information.
 */

int main(int argc, char *argv[]) {
    FILE *infp = stdin;
    FILE *outfp = NULL;
    char opt;
    extern int optind;
    extern char *optarg;
    
    while ((opt = getopt(argc, argv, "f:")) != -1) {
        switch (opt) {
            case 'f':
                infp = fopen(optarg, "r");
                if(!infp) {
                    perror("fopen");
                    exit(1);
                }
                break;
            default: /* '?' */
                fprintf(stderr, "Usage: %s [-f inputfile ] outputfile\n", argv[0]);
                exit(1);
        }
    }
    
    if (optind >= argc) {
        fprintf(stderr, "Expected outputfile name\n");
        exit(1);
    }
    
    if (!(outfp = fopen(argv[optind], "w"))){
        perror("fopen");
        exit(1);
    }
    
    // Read blocks from file and construct a linked list
    struct list *packets = create_packet_list(infp);
    
    // Write the linked list to file
    write_packet_list(outfp, packets);
    
    // Free memory used by the list
    free_list(packets);
    
    // Close files
    if (fclose(infp)) {
        perror("fclose: could not close infp");
        exit(1);
    };
    if (fclose(outfp)) {
        perror("fclose: could not close outfp");
        exit(1);
    };

    return 0;
}

readstream.c

#include <stdio.h>
#include <sys/stat.h>
#include <stdlib.h>
#include <unistd.h>

#include "data.h"

FILE *logfp = NULL;

/*
 * Create a linked list of packets from bytes in file infp previously written by packetize,
 * and return the head of the list.
 */
struct list *create_packet_list(FILE *infp) {
    struct list *packets = NULL;
    struct packet *packet = create_empty_packet();
    
    // Read one packet at a time
    while (fread(packet, sizeof(struct packet), 1, infp) != 0) {
        if (ferror(infp)) {
            perror("fread: error reading packet from file");
            exit(1);
        }
        
        // Allocate and read the payload
        packet->payload = malloc(packet->block_size);
        if (packet->payload == NULL) {
            perror("malloc: failed to allocate payload");
            exit(1);
        }
        fread(packet->payload, packet->block_size, 1, infp);
        if (ferror(infp)) {
            perror("fread: error reading payload from file");
            exit(1);
        }
        
        if (packet->crc != crc_message(XMODEM_KEY, packet->payload, packet->block_size)) {
            // CRC mismatch; payload is corrupted; log message
            log_message(packet, 2, logfp);
            
            // Free memory for corrupt packet
            free(packet->payload);
            free(packet);
        } else {
            // Report that the CRC matches
            log_message(packet, 1, logfp);
            
            // Add the valid packet to the list
            if (packets == NULL) {
                packets = create_node(packet);
            } else {
                // Insert the packet in the list in order of block_num, overwriting duplicates if necessary
                insert_packet_in_order(&packets, packet);
            }
            
            // Report that the packet was inserted
            log_message(packet, 0, logfp);
            
            // Only a reference to the payload was stored in the list; block_num, block_size, crc were copied by value
            // Therefore, we're done with the temporary packet struct
            free(packet);
        }
        packet = create_empty_packet();
    }
    
    // Done creating list; free last packet
    free(packet);
    
    return packets;
}


/* Read a packet file, and coalesce packets */

/*
 * Print to stdout the reconstructed data.  If a packet is missing, insert
 * ### into the output
 */

int main(int argc, char *argv[]) {
    FILE *infp;
    char opt;
    extern int optind;
    extern char *optarg;
    
    while ((opt = getopt(argc, argv, "l:")) != -1) {
        switch (opt) {
            case 'l':
                logfp = fopen(optarg, "w");
                if(!logfp) {
                    perror("fopen");
                    exit(1);
                }
                break;
            default: /* '?' */
                fprintf(stderr, "Usage: %s [-l logfile ] inputfile\n", argv[0]);
                exit(1);
        }
    }
    if (optind >= argc) {
        fprintf(stderr, "Expected inputfile name\n");
        exit(1);
    }
    
    if (argc != 2 && argc != 4) {
        fprintf(stderr, "Usage: %s [-l logfile ] inputfile\n", argv[0]);
        exit(1);
    }
    
    if ((infp = fopen(argv[optind], "r")) == NULL) {
        perror("fopen");
        exit(1);
    }
    
    // Read packets from file and construct a linked list
    struct list *packets = create_packet_list(infp);
    
    // Print the list to stdout
    print_list(packets);
    
    // Free memory used by the list
    free_list(packets);
    
    // Close files
    if (fclose(infp)) {
        perror("fclose: could not close infp");
        exit(1);
    };
    if (logfp != NULL && fclose(logfp)) {
        perror("fclose: could not close logfp");
        exit(1);
    }
    
    return 0;
}