This question regards the C implementation of the python code posted in this other question of mine, hence the explanation of the task at hand will be the same:
The problem
I need to process the data contained in a (relatively) large binary file.
The file has the following structure:
40 bytes of initialization,
4 bytes, 1 byte,
4 bytes, 1 byte,
...
lots of such 5-byte blocks
...
The number of 5-byte blocks (to which I'll refer to as 'timetags' in the following) may vary, but the total size of the file can be in the order of ~100 MBs.
In each 5-byte block the first 4 bytes encode a uint32_t (unsigned integer) 'timestamp', and the fifth byte is a number encoding a 'channel'.
My task is to find out whether there are contiguous sequences of 4 timetags, such that the corresponding timestamps are within a certain time window from each other, and if that is the case store the corresponding channels.
For example, if there is a sequence of timetags whose decoded data is
100, 2
300, 4
310, 5
340, 8,
369, 6,
413, 8
and my time window is 100, then I store the list [4,5,8,6].
In general the number of such fourfold coincidences will be extremely small with respect to the total number of timetags (e.g. for a ~100MB file I have ~10 such coincidences). Also, the timestamps are generally in increasing order, but sometimes there is a sudden jump (when the timestamps becomes too big for the 4 bytes to encode) and the count starts over, and this has to be taken into account (see below for an example file).
The question
I initially solved this problem with Python, but didn't manage to find a solution efficient enough. You can see the python code, and related discussions, on this codereview.SE question.
Here follows my solution implemented in C. This turned out to be much faster than the python solution. However, being me not an expert of C, I wonder if there is still room for improvements.
In particular, I'm wondering if it is better to read the whole file at once, which is what I've done in the code posted here, or to repeatedly read just a few bytes. In the linked question about the python implementation, switching from a read-all-at-once to a read-at-chunks solution gave a 2x improvement in speed. Doing the same thing with the C code, however, seems to significantly reduce the efficiency of the algorithm (though it can possibly be because of my poor way of implementing that).
Any tips/suggestions are welcome.
The code
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <sys/stat.h>
// #include <time.h>
off_t fsize(const char*);
int write_results_to_file(const char*, uint8_t(*)[4], uint16_t);
off_t fsize(const char* filename)
{
struct stat st;
if(stat(filename, &st) == 0)
return st.st_size;
return -1;
}
int write_results_to_file( const char* file_name,\
uint8_t (*results)[4], \
uint16_t number_of_elements
)
{
FILE *file;
file = fopen(file_name, "a");
for(int i = 0; i < number_of_elements; i++)
{
printf("fourfold coincidence: ");
for(int j = 0; j < 3; j++)
printf("%d,", results[i][j]/32 + 1);
printf("%d\n", results[i][3]/32 + 1);
fprintf(file, "%d,%d,%d,%d\n",\
results[i][0]/32 + 1,\
results[i][1]/32 + 1,\
results[i][2]/32 + 1,\
results[i][3]/32 + 1
);
}
fclose(file);
return 0;
}
int main() {
// clock_t begin_time;
// begin_time = clock();
const char FILE_NAME[] = "timetags.bin";
const char OUTPUT_FILE_NAME[] = "processed_timetags.txt";
const uint8_t WINDOW_SIZE = 100;
// we use arrays with 4 elements, being interested only in fourfold coincidences.
uint32_t timestamps[4];
uint8_t channels[4];
// assuming that there are no more than 1000 coincidences
uint8_t quadruples[1000][4];
uint16_t quadruples_pos = 0;
// curr_byte and curr_timestamp will be used in the for loop
uint32_t curr_byte;
uint32_t curr_timestamp;
// Initialize array of chars able to contain all the bytes.
// The first 40 bytes are to be ignored.
// If the number of bytes is not a multiple of 5, the exceeding bytes are
// not read.
// In this way, file_size effectively equals 5 times the number of 5-byte blocks
size_t file_size = fsize(FILE_NAME) - 40;
file_size = file_size - file_size % 5;
uint8_t* data = malloc(sizeof(uint8_t) * file_size);
// open file in binary read mode
FILE *file;
file = fopen(FILE_NAME, "rb");
if( file == NULL )
{
perror(FILE_NAME);
return(-1);
}
// ignore the first 40 bytes
fseek(file, 40, SEEK_SET);
// the rest of the file is stored in data
fread(data, file_size, 1, file);
// We start by reading the first 5 bytes stored in data.
// This is achieved reinterpreting the first 4 bytes in data as a single
// 4-byte unsigned integer number.
// The fifth byte encodes the channel.
timestamps[0] = *(uint32_t*) &data[0];
channels[0] = data[4];
uint8_t timestamps_pos = 1;
// Loop through data, at blocks of 5 bytes (remembering that we already
// processed the first 5 bytes)
for (int timetag_index = 1;
timetag_index < file_size/5;
timetag_index++
)
{
// curr_byte points to the first byte of the 5-byte block that is
// being processed
curr_byte = timetag_index * 5;
curr_timestamp = *(uint32_t*) &data[curr_byte];
if( curr_timestamp - timestamps[0] <= WINDOW_SIZE &&
curr_timestamp > timestamps[0]
)
{
timestamps[timestamps_pos] = curr_timestamp;
channels[timestamps_pos] = data[curr_byte + 4];
timestamps_pos++;
}
else // we reinitialize the arrays and start a new window
{
// first the quadruple is stored, if we have one
if(timestamps_pos == 4)
{
// quadruples[quadruples_pos++] = channels;
// printf("found quadruple: ");
// for(int i = 0; i<4; i++)
// printf("%d,\t",channels[i]);
// printf("\t\tat timetag nr %d", timetag_index);
// printf("\n");
memcpy(&quadruples[quadruples_pos++], channels, sizeof(channels));
}
// then a new window is opened
timestamps_pos = 1;
timestamps[0] = curr_timestamp;
channels[0] = data[curr_byte + 4];
}
}
fclose(file);
free(data);
// printf("Time required: %f\n", (double) (clock()-begin_time) / CLOCKS_PER_SEC);
write_results_to_file(OUTPUT_FILE_NAME, quadruples, quadruples_pos);
return 0;
}
