Algorithm Notes

#include <stdio.h>

#include <zlib.h>
#include <cstdlib>
#include <vector>

using namespace std;

void compressFile(const char *fileName, const vector<char> &in) {
	//we will use GZip from zlib
	gzFile gz_file;
	//open the file for writing in binary mode
	gz_file = gzopen(fileName, "wb");

	//Get the size of the stream
	unsigned long int file_size = sizeof(char) * in.size();
	//Write the size of the stream, this is needed so that we know
	//how much to read back in later
	gzwrite(gz_file, (void*) &file_size, sizeof(file_size));
	//Write the data
	gzwrite(gz_file, (void*) in.data(), file_size);
	//close the file
	gzclose(gz_file);
}

void decompressFile(const char *fileName, vector<char> &out) {
	//open the file for reading in binary mode
	gzFile gz_file = gzopen(fileName, "rb");
	//this variable will hold the size of the file
	unsigned long int size;
	//we wrote out a unsigned long int when storing the file
	//read this back in to get the size of the uncompressed data
	gzread(gz_file, (void*) &size, sizeof(size));
	//resize the string
	out.resize(size / sizeof(char));
	//read in and uncompress the entire data set at once
	gzread(gz_file, (void*) out.data(), size);
	//close the file
	gzclose(gz_file);
}

int main(int argc, char* argv[])
{
	vector<char> in, out;

	// generate data
	for (int i = 0; i < 1920*1080; ++i) {
		int d = rand();
		for (int j = 0; j < 8; ++j) {
			char d2 = (d >> j) & 0xF;
			in.push_back(d2);
		}
	}

	compressFile("com.gz", in);
	decompressFile("com.gz", out);

	// check decompressed data
	for (int i = 0; i < (int) out.size(); ++i) {
		if ( in[i] != out[i] ) {
			printf("error\n");
		}
	}
    return 0;
}

 

最近真的是被 volatile 搞到了

一直以來 volatile 的用法，其實不只是單純的每次執行到該指令時從記憶體內重新讀取，不使用 CPU 內 cache，因為在執行階段記憶體的內容可能被 interrupt 更新，在經過 compiler 最佳化過後會產生意想不到的執行結果

一個經典 while loop 例子

volatile int loop = 1;
while ( loop ) {
    printf("I'm running.\n");
}

如果沒有 volatile 修飾，compiler 最佳化後的結果是不可能跳出 while 迴圈的，但事情恐怕不是只有取消 cache 記憶體讀取這麼簡單

考慮下面一個簡單的迴圈

for (int i = 0; i < 256; ++i) {
    *((volatile unsigned long *)(0x12345678)) = i;
}

我們對記憶體 0x12345678 重複寫入不同值，這在 firmware 操作經常用來對硬體填入一個巨大的陣列，但硬體只提供一個固定位置的 register interface

如果沒有 volatile 修飾，上面這段 code 可能被 compiler 最佳化成

*((unsigned long *)(0x12345678)) = 255;

意思是我們的表個僅填入最後一筆值，不會正確的填寫完整的陣列

但這並不代表我們應該取消 compiler 最佳化，或是瘋狂的在所有存取指令加入 volatile ，而是需要去了解 code implicit 意義