| #include <stdio.h> |
| #include <stdlib.h> |
| #include <sys/types.h> |
| #include <sys/stat.h> |
| #include <sys/time.h> |
| |
| #define MAX_SIZE 150000 |
| |
| typedef struct linked_list_int { |
| int car; |
| void* cdr; |
| } linked_list_int; |
| |
| typedef struct linked_list_lli { |
| linked_list_int* car; |
| void* cdr; |
| } linked_list_lli; |
| |
| int pad_size(); |
| int calc_sum1(); |
| |
| linked_list_int* cons1(int hd, linked_list_int* tl) { |
| linked_list_int *res; |
| res = (linked_list_int*) malloc(sizeof(linked_list_int)); |
| res->car=hd; |
| res->cdr=tl; |
| return res; |
| } |
| |
| linked_list_lli* cons2(linked_list_int* hd, linked_list_lli* tl) { |
| linked_list_lli *res; |
| res = (linked_list_lli*) malloc(sizeof(linked_list_lli)); |
| res->car=hd; |
| res->cdr=tl; |
| return res; |
| } |
| |
| void free_list1(linked_list_int* list) { |
| linked_list_int *next; |
| while (list!=NULL) { |
| next = list->cdr; |
| free(list); |
| list = next; |
| } |
| return; |
| } |
| |
| void free_list2(linked_list_lli* list) { |
| linked_list_lli *next; |
| linked_list_int *hd; |
| while (list!=NULL) { |
| next = list->cdr; |
| hd = list->car; |
| free_list1(hd); |
| free(list); |
| list = next; |
| } |
| return; |
| } |
| /*==========================================================================*/ |
| |
| int read_x_bits(unsigned char* buf, int offset, int x) { /*1*/ |
| int byte_offset, bit_offset,present,initbits,res; /*2*/ |
| byte_offset = offset >> 3; /*3*/ |
| bit_offset = offset & 7; /*4*/ |
| initbits = 8-bit_offset; /*5*/ |
| present = (int)buf[byte_offset] & 255; /*6*/ |
| res = present & ((1 << initbits) - 1); /*7*/ |
| while (x > initbits) { /*8*/ |
| byte_offset++; /*9*/ |
| present = (int)buf[byte_offset] & 255; /*10*/ |
| res = (res << 8) | present; /*11*/ |
| initbits+=8; /*12*/ |
| } |
| return res >> (initbits-x); /*13*/ |
| } |
| |
| int read_11_bits(unsigned char* buf, int offset) { /*14*/ |
| int byte_offset, ioffset,present,initbits,res; /*15*/ |
| int b0,b1,b2; /*16*/ |
| byte_offset = offset >> 3; /*17*/ |
| ioffset = (8-(offset & 7)); /*18*/ |
| b0 = (int)buf[byte_offset] & 255; /*19*/ |
| b1 = (int)buf[byte_offset+1] & 255; /*20*/ |
| res = b0 << (11-ioffset); /*21*/ |
| if (ioffset >= 3) { /*22*/ |
| return (res | (b1 >> (ioffset-3))) & ((1 << 11) - 1); /*23*/ |
| } |
| else |
| b2 = (int)buf[byte_offset+2] & 255; /*24*/ |
| return (res | (b1 << (3-ioffset)) | b2 >> (ioffset+5)) & ((1 << 11) - 1); /*25*/ |
| } |
| |
| linked_list_lli* five11(unsigned char* inbuf) { /*26*/ |
| int offset,nof_packets, nof_channels,i,j,chan; /*27*/ |
| linked_list_int *packet=NULL; /*28*/ |
| linked_list_lli *res=NULL; /*29*/ |
| offset = 0; /*30*/ |
| nof_packets=read_x_bits(inbuf,offset,16); /*31*/ |
| offset=offset+16; /*32*/ |
| for(i=0;i<nof_packets;i++){ /*33*/ |
| nof_channels=read_x_bits(inbuf,offset,5); /*34*/ |
| offset+=5; /*35*/ |
| for(j=0;j<nof_channels;j++){ /*36*/ |
| chan=read_11_bits(inbuf,offset); /*37*/ |
| offset=offset+11; /*38*/ |
| packet = cons1(chan,packet); /*39*/ |
| } |
| offset=offset+pad_size(nof_channels); /*40*/ |
| res = cons2(packet,res); /*41*/ |
| packet=NULL; /*42*/ |
| } |
| return res; /*43*/ |
| } |
| |
| int pad_size(int nof_channels) { /*44*/ |
| int bits = 5+nof_channels*11; /*45*/ |
| return ((8 - (bits & 7)) & 7); /*46*/ |
| } |
| |
| int calc_sum2(linked_list_lli* list) { /*47*/ |
| linked_list_lli *next; /*48*/ |
| linked_list_int *hd; /*49*/ |
| int res=0; /*50*/ |
| while (list!=NULL) { /*51*/ |
| next = list->cdr; /*52*/ |
| hd = list->car; /*53*/ |
| res+=calc_sum1(hd); /*54*/ |
| list = next; /*55*/ |
| } |
| return res; |
| } |
| |
| int calc_sum1(linked_list_int* list) { /*56*/ |
| linked_list_int *next; /*57*/ |
| int hd,res=0; /*58*/ |
| while (list!=NULL) { /*59*/ |
| next = list->cdr; /*60*/ |
| hd = list->car; /*61*/ |
| res+=hd; /*62*/ |
| list = next; /*63*/ |
| } |
| return res; /*64*/ |
| } |
| |
| /*==========================================================================*/ |
| |
| static size_t read_data(FILE *in, void *buffer) |
| { |
| return fread(buffer, 1, MAX_SIZE, in); |
| } |
| |
| int main(int argc, char *argv[]) |
| { |
| FILE *in; |
| int i; |
| size_t size; |
| int outsize,time; |
| linked_list_lli *list; |
| unsigned char *inbuf, *outbuf, *temp; |
| |
| struct timeval pre,post; |
| |
| /* optional input arg */ |
| inbuf = malloc(MAX_SIZE); |
| |
| if (argc > 1) { |
| //create_test_data(argv[1]); // for testing purposes |
| if ((in = fopen(argv[1], "r")) == NULL) { |
| perror(argv[1]); |
| exit(1); |
| } |
| argv++; argc--; |
| } |
| else |
| in = stdin; |
| if (argc != 1) { |
| printf("Usage: five11 [infile]\n"); |
| exit(2); |
| } |
| size = read_data(in, inbuf); |
| gettimeofday(&pre,0); |
| #ifdef SMALL_PROBLEM_SIZE |
| for(i=0;i<500;i++){ |
| #else |
| for(i=0;i<10000;i++){ |
| #endif |
| list = five11(inbuf); |
| outsize = calc_sum2(list); |
| free_list2(list); |
| } |
| gettimeofday(&post,0); |
| printf("%d\n", outsize); |
| exit(0); |
| } |