Programming homework #3

bencode.c

#include "bencode.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <inttypes.h>
#include <math.h>

void data_dump(atom_t *root) {
    if (!root) {
        fprintf(stderr, "<<nil>>");
        return;
    }
    switch (root->type) {
        case ATOM_TYPE_STRING:
            fprintf(stderr, "'%s'", root->data.str);
            break;
        case ATOM_TYPE_LONG:
            fprintf(stderr, "%"PRIdPTR, root->data.l);
            break;
        case ATOM_TYPE_LIST:
            fprintf(stderr, "[");
            for (list_t *iter = root->data.list; iter;) {
                data_dump(iter->item);
                iter = iter->next;
                if (iter) fprintf(stderr, ", ");
            }
            fprintf(stderr, "]");
            break;
        case ATOM_TYPE_DICTIONARY:
            fprintf(stderr, "{");
            for (dict_t *iter = root->data.dict; iter;) {
                data_dump(iter->key);
                fprintf(stderr, ":");
                data_dump(iter->value);
                iter = iter->next;
                if (iter) fprintf(stderr, ", ");
            }
            fprintf(stderr, "}");
            break;
    }
}

char *bencode_atom(atom_t *atom) {
    char *out;
    size_t outlen;
    if (!atom) return strdup("i0e");
    switch (atom->type) {
        case ATOM_TYPE_LONG: {
            long val = atom->data.l;
            int digits = (int) log10(val) + 1;
            outlen = 2 + digits + 1;
            out = malloc(outlen);
            if (!out) return NULL;
            snprintf(out, outlen, "i%"PRIdPTR"e", val);
            return out;
        }
        case ATOM_TYPE_STRING: {
            char *str = atom->data.str;
            size_t len = strlen(str);
            int lenlen = (int) log10(len) + 1;
            outlen = lenlen + 1 + len + 1;
            out = malloc(outlen);
            if (!out) return NULL;
            snprintf(out, outlen, "%"PRIdPTR":%s", len, str);
            return out;
        }
        case ATOM_TYPE_LIST: {
            outlen = 2;
            out = calloc(outlen+1,1);
            if (!out) return NULL;
            out[0] = 'l';
            size_t pos = 1;
            list_t *iter = atom->data.list;
            while (iter) {
                char *atom_enc = bencode_atom(iter->item);
                size_t atom_len = strlen(atom_enc);
                
                outlen += atom_len;
                out = realloc(out, outlen+1);
                strcpy(&out[pos], atom_enc);
                pos += atom_len;
                
                free(atom_enc);
                iter = iter->next;
            }
            strcpy(&out[pos], "e");
            return out;
        }
        case ATOM_TYPE_DICTIONARY: {
            /* XXX: this is not actually spec compliant since keys are not sorted */
            outlen = 2;
            out = calloc(outlen+1,1);
            if (!out) return NULL;
            out[0] = 'd';
            size_t pos = 1;
            dict_t *iter = atom->data.dict;
            do {
                /* XXX: only strings are valid as keys */
                char *key_enc = bencode_atom(iter->key);
                char *val_enc = bencode_atom(iter->value);
                size_t key_len = strlen(key_enc), val_len = strlen(val_enc);
                
                outlen += key_len + val_len;
                out = realloc(out, outlen+1);
                
                strcpy(&out[pos], key_enc);
                pos += key_len;
                strcpy(&out[pos], val_enc);
                pos += val_len;
                
                free(key_enc);
                free(val_enc);
            } while ((iter = iter->next));
            strcpy(&out[pos], "e");
            return out;
        }
    }
    return NULL;
}

char *bencode_all(list_t *list) {
    char *out, *outpos;
    size_t outlen;
    out = bencode_atom(list->item);
    outlen = strlen(out);
    outpos = out + outlen;
    list = list->next;
    do {
        char *atom_enc = bencode_atom(list->item);
        size_t atom_len = strlen(atom_enc);
        
        outlen += atom_len;
        realloc(out, outlen+1);
        strcpy(outpos, atom_enc);
        outpos += atom_len;
        
        free(atom_enc);
    } while ((list = list->next));
    return out;
}

static atom_t *bdecode_atom_len(char *str, size_t *used_len) {
    atom_t *atom;
    char *pos = str + 1;
    
    switch (str[0]) {
        case 'i': {
            char *end;
            long i = strtol(str+1, &end, 10);
            if (*end != 'e')
                return NULL;
            
            atom = malloc(sizeof(atom_t));
            atom->type = ATOM_TYPE_LONG;
            atom->data.l = i;
            *used_len = end+1 - str;
            return atom;
            break;
        }
        case 'l': {
            *used_len = 2;
            list_t *list = 0, *iter = 0;
            while (*pos != 'e') {
                size_t subatom_used_len;
                atom_t *subatom = bdecode_atom_len(pos, &subatom_used_len);
                if (!subatom) /* invalid atom */
                    goto error_list;
                
                if (iter) {
                    iter->next = calloc(1, sizeof(list_t));
                    iter = iter->next;
                } else
                    iter = list = calloc(1, sizeof(list_t));
                
                iter->item = subatom;
                pos += subatom_used_len;
                *used_len += subatom_used_len;
                if (!*pos) /* unexpected EOF!! */
                    goto error_list;
            }
            atom_t *atom = malloc(sizeof(atom_t));
            atom->type = ATOM_TYPE_LIST;
            atom->data.list = list ? list : 0;
            return atom;

        error_list:
            /* free all of the allocated memory.
               subatom doesn't leak since it'll be in the last iter->data */
            if (list) bdecoded_free_list(list);
            *used_len = 0;
            return NULL;
            break;
        }
        case 'd': {
            *used_len = 2;
            dict_t *dict = 0, *iter = 0;
            int key = 1;
            while (*pos != 'e') {
                size_t subatom_used_len;
                atom_t *subatom = bdecode_atom_len(pos, &subatom_used_len);
                if (!subatom) /* invalid atom */
                    goto error_dict;
                
                if (key) {
                    if (iter) {
                        iter->next = calloc(1, sizeof(dict_t));
                        iter = iter->next;
                    } else
                        iter = dict = calloc(1, sizeof(dict_t));
                    
                    iter->key = subatom;
                } else {
                    iter->value = subatom;
                }
                key = !key;
                
                pos += subatom_used_len;
                *used_len += subatom_used_len;
                if (!*pos) /* unexpected EOF!! */
                    goto error_dict;
            }
            atom_t *atom = malloc(sizeof(atom_t));
            atom->type = ATOM_TYPE_DICTIONARY;
            atom->data.dict = dict ? dict : 0;
            return atom;
            
        error_dict:
            if (dict) bdecoded_free_dict(dict);
            *used_len = 0;
            return NULL;
            break;
        }
        default: {
            if (str[0] < '1' || str[0] > '9')
                return NULL;
            char *end;
            unsigned long len = strtoul(str, &end, 10);
            if (end == str || *end != ':')
                return NULL;
            
            atom = malloc(sizeof(atom_t));
            atom->type = ATOM_TYPE_STRING;
            atom->data.str = malloc(len+1);
            memcpy(atom->data.str, end+1, len);
            atom->data.str[len] = 0;
            *used_len = end+1+len - str;
            return atom;
        }
    }
}

atom_t *bdecode_atom(char *str) {
    size_t dont_care;
    return bdecode_atom_len(str, &dont_care);
}
list_t *bdecode_all(char *str) {
    char *pos = str;
    size_t len = strlen(str);
    char *end = str + len - 1;
    size_t atom_len;
    list_t *list = 0, *iter = 0;
    while (pos < end) {
        atom_t *atom = bdecode_atom_len(pos, &atom_len);
        if (!atom)
            goto error_all;
        
        if (iter) {
            iter->next = calloc(1, sizeof(list_t));
            iter = iter->next;
        } else
            iter = list = calloc(1, sizeof(list_t));
        
        iter->item = atom;
        pos += atom_len;
    }
    if (!list) return NULL;
    return list;
error_all:
    if (list) bdecoded_free_list(list);
    return NULL;
}

void bdecoded_free_atom(atom_t *atom) {
    switch (atom->type) {
        case ATOM_TYPE_LIST:
            bdecoded_free_list(atom->data.list);
            break;
        case ATOM_TYPE_DICTIONARY:
            bdecoded_free_dict(atom->data.dict);
            break;
        case ATOM_TYPE_STRING:
            free(atom->data.str);
            break;
        default:
            /* no need to free */
            break;
    }
    free(atom);
}

void bdecoded_free_list(list_t *list) {
    list_t *iter;
    for (iter = list; iter;) {
        list = iter->next;
        if (iter->item) bdecoded_free_atom(iter->item);
        free(iter);
        iter = list;
    }
}

void bdecoded_free_dict(dict_t *dict) {
    dict_t *iter;
    for (iter = dict; iter;) {
        dict = iter->next;
        if (iter->key) bdecoded_free_atom(iter->key);
        if (iter->value) bdecoded_free_atom(iter->value);
        free(iter);
        iter = dict;
    }
}

bencode.h

#ifndef ee2t2_bencode_h
#define ee2t2_bencode_h

typedef enum {
    ATOM_TYPE_LONG,
    ATOM_TYPE_STRING,
    ATOM_TYPE_LIST,
    ATOM_TYPE_DICTIONARY
} atom_type;

typedef union atom_data_u {
    long l;
    char *str;
    struct list_t *list;
    struct dict_t *dict;
} atom_data_u;

typedef struct atom_t {
    atom_type type;
    atom_data_u data;
} atom_t;

typedef struct list_t {
    atom_t *item;
    struct list_t *next;
} list_t;

typedef struct dict_t {
    atom_t *key;
    atom_t *value;
    struct dict_t *next;
} dict_t;

char *bencode_atom(atom_t *atom);
char *bencode_all(list_t *list);

atom_t *bdecode_atom(char *str);
list_t *bdecode_all(char *str);

void bdecoded_free_atom(atom_t *atom);
void bdecoded_free_list(list_t *list);
void bdecoded_free_dict(dict_t *dict);

void data_dump(atom_t *root);

#include <stdlib.h>
#include <string.h>

static inline atom_t *long_atom(long l) {
    atom_t *atom = malloc(sizeof(atom_t));
    if (!atom) return NULL;
    atom->type = ATOM_TYPE_LONG;
    atom->data.l = l;
    return atom;
}

static inline atom_t *str_atom(char *str) {
    atom_t *atom = malloc(sizeof(atom_t));
    if (!atom) return NULL;
    atom->type = ATOM_TYPE_STRING;
    atom->data.str = str;
    return atom;
}

static inline atom_t *str_atom_dup(char *str) {
    return str_atom(strdup(str));
}

static inline atom_t *list_atom(list_t *list) {
    atom_t *atom = malloc(sizeof(atom_t));
    if (!atom) return NULL;
    atom->type = ATOM_TYPE_LIST;
    atom->data.list = list;
    return atom;
}

static inline atom_t *dict_atom(dict_t *dict) {
    atom_t *atom = malloc(sizeof(atom_t));
    if (!atom) return NULL;
    atom->type = ATOM_TYPE_DICTIONARY;
    atom->data.dict = dict;
    return atom;
}

#endif

Makefile

CFLAGS = -std=c99 -Wall -Wextra

all: q1 q2

q1: q1.o bencode.o

q2: q2.o bencode.o

test: test.o bencode.o

q1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bencode.h"

#define CHOMP(val) val[strlen(val)-1] = '\0'

int main() {
    list_t *data = malloc(sizeof(list_t));
    atom_t data_atom = {
        .type = ATOM_TYPE_LIST,
        .data.list = data
    };
    
    atom_t *dic_atom;
    dict_t *dic;
    list_t *list_grades;
    int pick, i = 0, j;
    char *grnames[3] = {"Primeira", "Segunda", "Terceira"};
    
    printf("*** Modo de cadastro\n");
    while (1) {
        printf("Matricula (0 para sair): ");
        scanf("%d", &pick);
        if (!pick) break;
        
        dic = malloc(sizeof(dict_t));
        dic->key = str_atom_dup("Matricula");
        dic->value = long_atom(pick);
        dic_atom = dict_atom(dic);
        
        dic = dic->next = malloc(sizeof(dict_t));
        dic->key = str_atom_dup("Primeiro nome");
        dic->value = str_atom(malloc(50));
        fgets(dic->value->data.str, 50, stdin); // Read the leftover \n
        
        printf("Primeiro nome: ");
        fgets(dic->value->data.str, 50, stdin);
        CHOMP(dic->value->data.str); // Remove the trailing \n
        
        dic = dic->next = malloc(sizeof(dict_t));
        dic->key = str_atom_dup("Sobrenome");
        dic->value = str_atom(malloc(50));
        
        printf("Sobrenome: ");
        fgets(dic->value->data.str, 50, stdin);
        CHOMP(dic->value->data.str); // Remove the trailing \n
        
        dic = dic->next = malloc(sizeof(dict_t));
        dic->key = str_atom_dup("Notas");
        dic->value = list_atom(list_grades = malloc(sizeof(list_t)));
        dic->next = 0;
        
        float grade;
        char gr[20];
        for(j = 0; j < 3; j++) {
            if (j)
                list_grades = list_grades->next = malloc(sizeof(list_t));
            do {
                printf("%s nota: ", grnames[j]);
                scanf("%f", &grade);
            } while (grade < 0 || grade > 10);
            sprintf(&gr[0], "%.2f", grade);
            list_grades->item = str_atom(strdup(gr));
        }
        list_grades->next = 0;
        printf("\n");
        
        if (i)
            data = data->next = malloc(sizeof(list_t));
        data->item = dic_atom;
        ++i;
    }
    data->next = 0;
    
    FILE *f = fopen("matriculas.benc", "wb");
    char *encoded = bencode_atom(&data_atom);
    fprintf(f, "%s", encoded);
    fclose(f);
    
    free(encoded);
    bdecoded_free_list(data);
    
    printf("Gravadas %d matriculas\n", i);
    return 0;
}

q2.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include "bencode.h"

#define CHUNK 4096

int main() {
    FILE *f = fopen("matriculas.benc", "rb");
    if (!f) {
        printf("Erro abrindo matriculas.benc; execute q1 primeiro\n");
        return 1;
    }
    char *contents = malloc(CHUNK);
    for(int i = 0; fread(contents + (i*CHUNK), 1, CHUNK, f) == CHUNK;)
        contents = realloc(contents, (++i+1)*CHUNK);

    printf("*** Modo de relatorio\n");
    atom_t *root = bdecode_atom(contents);
    for (list_t *all_iter = root->data.list; all_iter; all_iter = all_iter->next) {
        for (dict_t *dic = all_iter->item->data.dict; dic; dic = dic->next) {
            printf("%s: ", dic->key->data.str);
            switch(dic->value->type) {
                case ATOM_TYPE_LONG:
                    printf("%"PRIdPTR"\n", dic->value->data.l);
                    break;
                case ATOM_TYPE_STRING:
                    printf("%s\n", dic->value->data.str);
                    break;
                case ATOM_TYPE_LIST: {
                    /* only happens on Notas */
                    float g[3], avg = 0;
                    
                    list_t *grades = dic->value->data.list;
                    
                    for(int i = 0; i < 3; i++) {
                        g[i] = atof(grades->item->data.str);
                        printf("%s%.2f", i ? ", " : "", g[i]);
                        avg += g[i];
                        grades = grades->next;
                    }
                    
                    avg /= 3;
                    
                    printf("\nMedia: %.2f\n", avg);
                    
                    break;
                }
                default: ;
            }
        }
        printf("\n");
    }
    
    bdecoded_free_atom(root);
    return 0;
}

test.c

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include "bencode.h"

#define VERBOSE 1

static void do_test(char *name, atom_t *atom) {
    char *encoded, *encoded2;
    atom_t *decoded;
    
#if VERBOSE
    fprintf(stderr, "Source: ");
    data_dump(atom);
    fprintf(stderr, "\n");
#endif
    
    encoded = bencode_atom(atom);
#if VERBOSE
    fprintf(stderr, "1st Encode: %s\n", encoded);
#endif
    
    decoded = bdecode_atom(encoded);
    if (!decoded) {
        printf("%s test: FAILED to decode!!\n", name);
        free(encoded);
        return;
    }
#if VERBOSE
    fprintf(stderr, "Decode: ");
    data_dump(decoded);
    fprintf(stderr, "\n");
#endif
    
    encoded2 = bencode_atom(decoded);
#if VERBOSE
    fprintf(stderr, "2nd Encode: %s\n", encoded2);
#endif
    
    fprintf(stderr, "%s test: %s\n\n", name, strcmp(encoded, encoded2) ? "FAILED" : "OK");
    
    bdecoded_free_atom(decoded);
    free(encoded);
    free(encoded2);
}

int main (int argc, const char * argv[])
{
    atom_t atom1, atom2;
    
    atom1.type = ATOM_TYPE_STRING;
    atom1.data.str = "Hello World!";
    
    do_test("String", &atom1);
    
    atom2.type = ATOM_TYPE_LONG;
    atom2.data.l = 123;
    
    do_test("Integer", &atom2);
    
    list_t item2 = {
        .item = &atom2
    };
    list_t item1 = {
        .item = &atom1,
        .next = &item2
    };
    
    atom_t lst = {
        .type = ATOM_TYPE_LIST,
        .data.list = &item1
    };
    
    do_test("Simple list", &lst);
    
    dict_t key1 = {
        .key = &atom1,
        .value = &atom2
    };
    
    atom_t dict = {
        .type = ATOM_TYPE_DICTIONARY,
        .data.dict = &key1
    };
    
    do_test("Simple dict", &dict);
    
    atom_t atom3 = {
        .type = ATOM_TYPE_STRING,
        .data.str = "List"
    };
    
    dict_t key2 = {
        .key = &atom3,
        .value = &lst
    };
    key1.next = &key2;
    
    do_test("Complex dict", &dict);

    return 0;
}