my huffman encoding

[matlex]

This my first try for huffman encoding!

bitreader.h

#ifndef BIT_H
#define BIT_H

#include <fstream>
typedef unsigned char byte;

class bitwriter {
	byte _byBuffer;
	int _iNumBits;
	std::fstream& _file;
public:
	bitwriter(std::fstream& file) : _file(file), _iNumBits(0) {}

	~bitwriter() {
		flush();
	}

	// Scrive un bit sullo stream
	bool bitwrite(unsigned bit) {
		_byBuffer = _byBuffer << 1;
		_byBuffer = _byBuffer + (bit & 1);
		_iNumBits++;
		if (_iNumBits == 8) {
			_file.write((char *)&_byBuffer, 1);
			_iNumBits = 0;
			if (_file.fail())
				return false;
		}
		return true;
	}

	// Scrive gli n bit meno significativi di un intero sullo stream
	bool write(unsigned u, int n) {
		while (n>0)
			bitwrite(u >> --n);
		return _file.fail();
	}

	// Svuota il buffer su file
	bool flush() {
		while (_iNumBits>0)
			bitwrite(0);
		return _file.fail();
	}
};

class bitreader {
	byte _byBuffer;
	int _iNumBits;
	std::fstream& _file;

	bool fill() {
		_file.read((char *)&_byBuffer, 1);
		_iNumBits = 8;
		return _file.fail();
	}
public:
	bitreader(std::fstream& file) : _file(file), _iNumBits(0) {}

	// Legge un bit dallo stream
	bool bitread(unsigned &bit) {
		if (_iNumBits == 0)
			fill();
		_iNumBits--;
		bit = (_byBuffer >> _iNumBits) & 1;
		return true;
	}

	// Legge n bit dallo stream
	bool read(unsigned &u, int n) {
		u = 0;
		while (n>0) {
			unsigned bit;
			bitread(bit);
			u |= bit << --n;
		}
		return _file.fail();
	}
};

#endif // BIT_H 

elias.h

#ifndef ELIAS_H
#define ELIAS_H

#include <string>
#include <fstream>
#include <sstream>

#include "image.h"
#include "bit.h"

typedef unsigned char byte;

using namespace std;

unsigned NumBits(unsigned u) {
	unsigned n = 0;
	while (u) {
		n++;
		u >>= 1;
	}
	return n;
}

unsigned EliasCodeLength(unsigned u) {
	return NumBits(u) * 2 - 1;
}

unsigned Mapping(int i) {
	if (i>0)
		return unsigned(i * 2);
	else
		return unsigned(-i * 2 + 1);
}

int InverseMapping(unsigned u) {
	if (u % 2)
		return -(int(u) - 1) / 2;
	else
		return int(u) / 2;
}

void SaveElias(const string &sFileName, const image<byte>& imm) {
	fstream file(sFileName.c_str(), fstream::binary | fstream::out);
	bitwriter bw(file);
	// Header
	bw.write(imm.width(), 24);
	bw.write(imm.height(), 24);
	// Scrivo i pixel
	for (unsigned y = 0; y<imm.height(); ++y) {
		// Il primo pixel viene scritto così
		bw.write(imm(0, y), 8);
		for (unsigned x = 1; x<imm.width(); ++x) {
			int iDiff = imm(x, y) - imm(x - 1, y);
			unsigned uMap = Mapping(iDiff);
			unsigned uLen = EliasCodeLength(uMap);
			bw.write(uMap, uLen);
		}
	}
}

bool LoadElias(const string &sFileName, image<byte> &imm) {
	fstream file(sFileName.c_str(), fstream::binary | fstream::in);
	if (!file)
		return false;
	bitreader br(file);

	// Leggo l'Header
	unsigned uWidth, uHeight;
	br.read(uWidth, 24);
	br.read(uHeight, 24);

	// Ridimensiono l'immagine
	imm.setsize(uWidth, uHeight);

	unsigned u;
	for (unsigned y = 0; y<imm.height(); ++y) {
		// Il primo pixel viene scritto così
		br.read(u, 8);
		imm(0, y) = byte(u);
		for (unsigned x = 1; x<imm.width(); ++x) {
			// Leggo il codice di Elias
			int iLen = 0;
			do {
				br.bitread(u);
				if (u == 0)
					iLen++;
			} while (u == 0);

			unsigned uCode = 1;
			while (iLen>0) {
				br.bitread(u);
				uCode = (uCode << 1) | u;
				iLen--;
			}

			// Effettuo il mapping inverso
			int iDiff = InverseMapping(uCode);
			// Ricostruisco l'immagine
			imm(x, y) = iDiff + imm(x - 1, y);
		}
	}
	return true;
}


#endif // ELIAS_H

image.h

#ifndef IMAGE_H
#define IMAGE_H

#include <vector>

template <typename _T>
class image {
	unsigned _w, _h;
	std::vector<_T> _pix;
public:
	image(unsigned w = 0, unsigned h = 0) : _w(w), _h(h), _pix(w*h) {}

	void setsize(unsigned w, unsigned h) {
		_w = w;
		_h = h;
		_pix.resize(_w*_h);
	}
	void setsize(const image& rhs) {
		setsize(rhs._w, rhs._h);
	}

	_T& operator() (unsigned x, unsigned y) {
		return _pix[y*_w + x];
	}
	const _T& operator() (unsigned x, unsigned y) const {
		return _pix[y*_w + x];
	}

	unsigned width() const { return _w; }
	unsigned height() const { return _h; }

	typedef typename std::vector<_T>::iterator iterator;
	iterator begin() {
		return _pix.begin();
	}
	iterator end() {
		return _pix.end();
	}
};

#endif // IMAGE_H 

pgm.h

#ifndef PGM_H
#define PGM_H

#include <string>

#include "image.h"
#include <fstream>
#include <sstream>


typedef unsigned char byte;

using namespace std;

void SavePGM_bin(const string &sFileName, const image<byte>& imm) {
	fstream file(sFileName.c_str(), fstream::binary | fstream::out);
	// Header
	file << "P5" << endl;
	// Larghezza e Altezza
	file << imm.width() << " " << imm.height() << endl;
	// Massimo livello di grigio
	file << "255" << endl;
	// Scrivo i byte
	for (unsigned y = 0; y<imm.height(); ++y) {
		for (unsigned x = 0; x<imm.width(); ++x) {
			file.write((const char *)&imm(x, y), 1);
		}
	}
}

string LoadPGM_getstring(fstream &file) {
	string s;
	char buf;
	do {
		file.get(buf);
		if (file.eof() || buf == '\n' || buf == ' ' || buf == '\t')
			break;
		s.append(1, buf);
	} while (true);
	return s;
}
string LoadPGM_getstring(fstream &file, char chDelim) {
	string s;
	char buf;
	do {
		file.get(buf);
		if (file.eof() || buf == chDelim)
			break;
		s.append(1, buf);
	} while (true);
	return s;
}
int LoadPGM_getint_skipcomments(fstream &file) {
	string s;
	do {
		s = LoadPGM_getstring(file);
		if (s[0] == '#')
			LoadPGM_getstring(file, '\n');
	} while (s[0] == '#');
	stringstream stream(s);
	int i;
	stream >> i;
	return i;
}

bool LoadPGM_bin(const string &sFileName, image<byte> &imm) {
	fstream file(sFileName.c_str(), fstream::binary | fstream::in);
	if (!file)
		return false;

	string sHeader = LoadPGM_getstring(file);
	if (sHeader != "P5")
		return false;
	int iWidth = LoadPGM_getint_skipcomments(file);
	int iHeight = LoadPGM_getint_skipcomments(file);
	int iMaxDepth = LoadPGM_getint_skipcomments(file);

	// Ridimensiono l'immagine
	imm.setsize(iWidth, iHeight);

	// Leggo i byte
	for (unsigned y = 0; y<imm.height(); ++y) {
		for (unsigned x = 0; x<imm.width(); ++x) {
			file.read((char *)&imm(x, y), 1);
		}
	}
	return true;
}

#endif // PGM_H 

[matlex]

ops i forgot the
main.cpp

#include <algorithm>
#include <numeric>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <functional>
#include <list>
#include <map>
using namespace std;

#include "pgm.h"
#include "elias.h"
#include "bit.h"

byte diff2imm(short sh) {
	return sh / 2 + 127;
}

struct incrementer {
	vector<unsigned>& _ist;
	int _base;

	incrementer(vector<unsigned>& ist, int base = 0) : _ist(ist), _base(base) {}

	void operator() (int i) {
		_ist[i + _base]++;
	}
};


struct symbol {
	int _sym;
	double _prob;
	symbol *_left;
	symbol *_right;

	unsigned _code, _length;

	symbol(int sym = 0, double prob = 0, symbol *left = 0, symbol *right = 0) :
		_sym(sym), _prob(prob), _left(left), _right(right), _code(0), _length(0) {}

	bool operator< (const symbol& rhs) const {
		return _prob<rhs._prob;
	}
};

template <typename T>
struct pointer_less_than {
	const bool operator()(const T *a, const T * b) const {
		if (!a || !b)
			return false;
		else
			return *a < *b;
	}
};

void print_huffmantree(const symbol *s, string& str) {
	if (!s->_left)
		cout << s->_sym << "\t"
		<< setiosflags(ios::fixed) << setprecision(6)
		<< s->_prob << "\t" << str << "\n";
	else {
		str += "0";
		print_huffmantree(s->_left, str);
		str.erase(str.length() - 1);

		str += "1";
		print_huffmantree(s->_right, str);
		str.erase(str.length() - 1);
	}
}

void CreateHuffmanCodes(symbol *s, unsigned code, unsigned length, map<int, symbol>& mapHuff) {
	if (!s->_left) { //non capisco cosa significa la condizione
		s->_code = code;
		s->_length = length;

		mapHuff.insert(pair<int, symbol>(s->_sym, *s));

		cout << s->_sym << "\t"
			<< setiosflags(ios::fixed) << setprecision(6)
			<< s->_prob << "\t" << code << "\t" << length << "\n";
	}
	else {
		CreateHuffmanCodes(s->_left, code << 1, length + 1, mapHuff);
		CreateHuffmanCodes(s->_right, (code << 1) + 1, length + 1, mapHuff);
	}
}

void pair_print(pair<unsigned, unsigned>& p) {
	cout << p.first << "\t" << p.second << "\n";
}

void main() {
	/*
	image<byte> imm;
	// Carico l'immagine
	if (!LoadPGM_bin("rana_bin.pgm",imm))
	return;

	// Creo la mappa di differenze
	image<short> diff(imm.width(),imm.height());
	for (unsigned y=0;y<imm.height();++y) {
	diff(0,y) = imm(0,y);
	for (unsigned x=1;x<imm.width();++x) {
	diff(x,y) = imm(x,y)-imm(x-1,y);
	}
	}

	// Creo l'immagine per visualizzare le differenze
	image<byte> immDiff(diff.width(),diff.height());
	transform (diff.begin(),diff.end(),immDiff.begin(),diff2imm);
	SavePGM_bin ("rana_diff.pgm",immDiff);

	// Creo l'istogramma delle differenze
	vector<unsigned> ist_diff(511);
	fill (ist_diff.begin(),ist_diff.end(),0);
	for_each (diff.begin(),diff.end(),incrementer(ist_diff,255));

	// Salvo l'istogramma delle differenze
	fstream fileIst("ist_diff.txt", fstream::out);
	for (unsigned i=0;i<ist_diff.size();++i)
	fileIst << int(i)-255 << "\t" << ist_diff[i] << "\n";

	// Dato un istogramma costruisco un vettore di simboli (con la probabilità)
	vector<symbol> symbols;
	double dTotal = accumulate (ist_diff.begin(),ist_diff.end(),0.0);
	for (unsigned i=0;i<ist_diff.size();++i)
	if (ist_diff[i]>0)
	symbols.push_back (symbol(short(i)-255,ist_diff[i]/dTotal));
	*/

	// Carico un file di interi
	fstream file("esempio.txt", fstream::in);
	vector<int> data; // dichiaro un vettore di interi, di nome data
	//copio i valori presenti nel file e li vado ad inserire in data
	copy(istream_iterator<int>(file), istream_iterator<int>(), back_inserter(data));
	// Stampo il vettore
	copy(data.begin(), data.end(), ostream_iterator<int>(cout, "\n"));
	cout << "\n";

	// Estraggo i valori unici
	vector<int> values; // dichiarazione di un vettore di interi di nome values
	unique_copy(data.begin(), data.end(), back_inserter(values)); // funzione che mi permette di estrarre i 
	// valori unici presenti nel vettore
	// Stampo il vettore
	// uso la funzione copy per copiare in uscita i valori del vettore 
	copy(values.begin(), values.end(), ostream_iterator<int>(cout, "\n"));
	cout << "\n";

	// Per ogni valore unico conto le occorrenze e creo dei simboli
	// creazione di una lista di simboli
	list<symbol*> symbols;

	for (vector<int>::iterator it = values.begin(); it != values.end(); ++it) {
		// salvo in una variabile occorrenze di tipo double i valori
		double dOccorrenze = count_if(data.begin(), data.end(), bind2nd(equal_to<int>(), *it));
		symbols.push_back(new symbol(*it, dOccorrenze / data.size()));
	}

	// Ordino i simboli
	symbols.sort(pointer_less_than<symbol>());

	// Stampo
	for (list<symbol*>::iterator it = symbols.begin(); it != symbols.end(); ++it) {
		cout << (**it)._sym << "\t" << (**it)._prob << "\n";
	}
	cout << "\n";

	// Applico l'algoritmo di Huffman
	while (symbols.size()>1) {
		// Prendo i due simboli meno probabili della lista
		// posso fare così perchè prima li ho ordinati, quindi sono già quali sono i meno probabili
		symbol *s1 = symbols.front();
		symbols.pop_front();
		symbol *s2 = symbols.front();
		symbols.pop_front();
		// Creo un nuovo simbolo che combini i due estratti
		symbol *s = new symbol(0, s1->_prob + s2->_prob, s1, s2);
		// Inserisco il simbolo nella lista alla posizione corretta
		// vado praticamente ad inserire la somma nell'ordine corretto
		list<symbol*>::iterator it = symbols.begin();
		while (it != symbols.end() && **it<*s)
			++it;
		symbols.insert(it, s);

		// Stampo
		for (list<symbol*>::iterator it = symbols.begin(); it != symbols.end(); ++it) {
			cout << (**it)._sym << "\t" << (**it)._prob << "\n";
		}

	}
	symbol *root = symbols.front();
	symbols.pop_front();

	// Ho costruito l'albero, adesso lo visualizzo
	print_huffmantree(root, string());
	cout << "\n";

	// Memorizzo codici e lunghezze e metto tutto in una map
	map<int, symbol> mapHuff;	//mapHuff ti tipo map, costituito da interi e simboli
	CreateHuffmanCodes(root, 0, 0, mapHuff);
	cout << "\n";

	// Elenco tutte le lunghezze
	typedef pair<unsigned, unsigned> pairuu; //definizione e creazione di un tipo pair con 2 unsigned di nome pairuu
	typedef vector<pairuu> vpairuu; // definizione di una vettore con oggetti dello stesso tipo
	vpairuu vecLunghezze; // vettore di tipo vpairuu di nome vecLunghezze
	for (map<int, symbol>::iterator it = mapHuff.begin(); it != mapHuff.end(); ++it) {
		vecLunghezze.push_back(pairuu(it->second._length, it->first));
	}

	for_each(vecLunghezze.begin(), vecLunghezze.end(), pair_print);
	cout << "\n";

	sort(vecLunghezze.begin(), vecLunghezze.end());

	for_each(vecLunghezze.begin(), vecLunghezze.end(), pair_print);
	cout << "\n";

	// Genero i codici canonici
	unsigned code = 0;
	unsigned length = 0;
	for (vpairuu::iterator it = vecLunghezze.begin(); it != vecLunghezze.end(); ++it) {
		while (it->first>length) {
			length++;
			code <<= 1;
		}
		mapHuff[it->second]._code = code;
		code++;
	}

	for (map<int, symbol>::iterator it = mapHuff.begin(); it != mapHuff.end(); ++it) {
		cout << it->second._sym << "\t"
			<< setiosflags(ios::fixed) << setprecision(6)
			<< it->second._prob << "\t" << it->second._code << "\t" << it->second._length << "\n";
	}

	// Salvo il file utilizzando i codici di Huffman
	fstream fileOut("esempio.huf", fstream::out | fstream::binary);
	bitwriter bw(fileOut);
	// Prima scrivo il numero di elementi della tabella
	bw.write(vecLunghezze.size(), 32);
	// Poi scrivo la tabella con lunghezza e valore
	for (vpairuu::iterator it = vecLunghezze.begin(); it != vecLunghezze.end(); ++it) {
		bw.write(it->first, 32);
		bw.write(it->second, 32);
	}
	// Poi scrivo i dati codificati
	for (vector<int>::iterator it = data.begin(); it != data.end(); ++it) {
		symbol& s = mapHuff[*it];
		bw.write(s._code, s._length);
	}
	system("PAUSE");
}

[bellerofonte]

thanks works great!