环境：Win10 (x64) 编译器：VS2019 (x64)
encode输入图像文件 gray.bmp 生成文件file.dat 和 code.dat
decode输入文件file.dat 和 code.dat 生成图像gary.bmp
encode:
#include"HXLBMPFILE.h"
#include<algorithm>
#include<cstring>
#include<fstream>
#include<vector>
using namespace std;
class HuffmanNode
{
public:
unsigned char symbol;
unsigned int freq;
unsigned int codeword;
unsigned short codewordLen;
HuffmanNode* left, * right;
HuffmanNode()
{
left = right = 0;
}
HuffmanNode(unsigned char s, unsigned int f, HuffmanNode* lf = 0, HuffmanNode* rt = 0)
{
symbol = s;
freq = f;
left = lf, right = rt;
}
};
class ListNode
{
public:
HuffmanNode* tree;
ListNode* prev, * next;
ListNode()
{
next = prev = 0;
}
ListNode(ListNode* p, ListNode* n)
{
prev = p, next = n;
}
};
class DataRec
{
public:
unsigned char symbol;
unsigned int freq;
DataRec()
{
}
bool operator == (const DataRec& dr) const
{
return symbol == dr.symbol;
}
bool operator < (const DataRec& dr)const
{
return freq < dr.freq;
}
};
class HuffmanCoding
{
public:
const unsigned int ASCII;
const unsigned int bits;
const unsigned short mask = 0xff;
HuffmanNode* HuffmanTree, ** chars;
unsigned short dataCnt;
unsigned int bitsCnt;
vector<DataRec> data;
HuffmanCoding(): ASCII(256), bits(8)
{
chars = new HuffmanNode * [ASCII + 1];
for (int i = 0; i < ASCII; i++)
chars[i] = 0;
}
void encode(HXLBMPFILE*, const char*, const char*);
void input(HXLBMPFILE*);
void writebytes(ofstream&, unsigned int, int);
void createHuffmanTree();
void createCodewords(HuffmanNode*, unsigned int, unsigned short);
void transformTree2Lists(HuffmanNode*);
void outputHeader(HXLBMPFILE*, const char*);
void outputData(HXLBMPFILE*, const char*);
void saveCode(const char*);
};
void HuffmanCoding::encode(HXLBMPFILE* bmpfile, const char* FileName1, const char* FileName2)
{
input(bmpfile);
createHuffmanTree();
createCodewords(HuffmanTree, 0, 0);
transformTree2Lists(HuffmanTree);
outputHeader(bmpfile, FileName1);
outputData(bmpfile, FileName1);
saveCode(FileName2);
}
void HuffmanCoding::writebytes(ofstream& fout, unsigned int pack, int bytes)
{
unsigned char* s = new unsigned char[bytes];
for (int i = bytes - 1; i >= 0; i--)
{
s[i] = pack & mask;
pack >>= bits;
}
for (int i = 0; i < bytes; i++)
fout.put(s[i]);
}
void HuffmanCoding::input(HXLBMPFILE* bmpfile)
{
unsigned char ch;
DataRec r;
vector<DataRec>::iterator iter;
r.freq = 1;
for (int i = 0; i < (*bmpfile).imageh; i++)
for (int j = 1; j < (*bmpfile).imagew; j++)
{
ch = (*bmpfile).pDataAt(i)[j];
r.symbol = ch;
iter = find(data.begin(), data.end(), r);
if (iter == data.end())
data.push_back(r);
else
iter->freq++;
}
sort(data.begin(), data.end());
dataCnt = data.size();
}
void HuffmanCoding::createHuffmanTree()
{
ListNode* head, * tail;
unsigned int newFreq;
head = tail = new ListNode;
head->tree = new HuffmanNode(data[0].symbol, data[0].freq);
for (int i = 1; i < data.size(); i++)
{
tail->next = new ListNode(tail, 0);
tail = tail->next;
tail->tree = new HuffmanNode(data[i].symbol, data[i].freq);
}
while (head != tail)
{
newFreq = head->tree->freq + head->next->tree->freq;
ListNode* p, * newNode;
for (p = tail; p != 0 && p->tree->freq > newFreq; p = p->prev)
;
newNode = new ListNode(p, p->next);
p->next = newNode;
if (p == tail)
tail = newNode;
else
newNode->next->prev = newNode;
newNode->tree = new HuffmanNode('\0', newFreq, head->tree, head->next->tree);
head = head->next->next;
delete head->prev->prev;
delete head->prev;
head->prev = 0;
}
HuffmanTree = head->tree;
delete head;
}
void HuffmanCoding::createCodewords(HuffmanNode* p, unsigned int codeword, unsigned short codewordLen)
{
if (p->left == 0 && p->right == 0)
{
p->codeword = codeword;
p->codewordLen = codewordLen;
}
else
{
createCodewords(p->left, codeword << 1, codewordLen + 1);
createCodewords(p->right, codeword << 1 | 1, codewordLen + 1);
}
}
void HuffmanCoding::transformTree2Lists(HuffmanNode* p)
{
if (p->left == 0 && p->right == 0)
{
p->right = 0;
p->left = 0;
chars[unsigned char(p->symbol)] = p;
}
else
{
transformTree2Lists(p->left);
transformTree2Lists(p->right);
}
}
void HuffmanCoding::outputHeader(HXLBMPFILE* bmpfile, const char* FileName)
{
FILE* f;
f = fopen(FileName, "w+b");
BITMAPFILEHEADER fh;
BITMAPINFOHEADER ih;
memset(&ih, 0, sizeof(BITMAPINFOHEADER));
fh.bfType = 0x4d42;
fh.bfReserved1 = fh.bfReserved2 = 0;
fh.bfOffBits = sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + (((*bmpfile).iYRGBnum == 1) ? 256 * sizeof(RGBQUAD) : 0);
ih.biSize = 40; ih.biPlanes = 1;
ih.biWidth = (*bmpfile).imagew;
ih.biHeight = (*bmpfile).imageh;
ih.biBitCount = 8 * (*bmpfile).iYRGBnum;
int w4b = ((*bmpfile).imagew * (*bmpfile).iYRGBnum + 3) / 4 * 4;
ih.biSizeImage = ih.biHeight * w4b;
fh.bfSize = fh.bfOffBits + ih.biSizeImage;
fwrite(&fh, sizeof(BITMAPFILEHEADER), 1, f);
fwrite(&ih, sizeof(BITMAPINFOHEADER), 1, f);
fwrite((*bmpfile).palette, sizeof(RGBQUAD), ASCII, f);
fclose(f);
}
void HuffmanCoding::outputData(HXLBMPFILE* bmpfile, const char* FileName)
{
ofstream fout;
fout.open(FileName, ios::app | ios::out | ios::binary);
const int bytes = 3;
unsigned int packCnt = 0, maxPack = bytes * bits, pack = 0;
unsigned int nowcodeword = 0, nowcodewordLen = 0;
unsigned int bitsLeft = 0, hold = 0;
unsigned char ch;
bitsCnt = 0;
for (int i = (*bmpfile).imageh - 1; i >= 0; i--)
{
for (int j = 0; j < (*bmpfile).imagew; j++)
{
nowcodeword = chars[(*bmpfile).pDataAt(i)[j]]->codeword;
nowcodewordLen = chars[(*bmpfile).pDataAt(i)[j]]->codewordLen;
if (nowcodewordLen < maxPack - packCnt)
{
pack = (pack << nowcodewordLen) | nowcodeword;
packCnt += nowcodewordLen;
}
else
{
bitsLeft = maxPack - packCnt;
pack <<= bitsLeft;
if (bitsLeft != nowcodewordLen)
{
hold = nowcodeword;
hold >>= nowcodewordLen - bitsLeft;
pack |= hold;
}
else
pack |= nowcodeword;
writebytes(fout, pack, bytes);
bitsCnt += bytes * bits;
if (bitsLeft != nowcodewordLen)
{
pack = nowcodeword;
packCnt = nowcodewordLen - bitsLeft;
pack &= (1 << packCnt) - 1;
}
else
{
pack = 0;
packCnt = 0;
}
}
}
}
if (packCnt != 0)
{
pack <<= maxPack - packCnt;
writebytes(fout, pack, bytes);
bitsCnt += packCnt;
}
fout.close();
}
void HuffmanCoding::saveCode(const char* FileName)
{
ofstream fout;
fout.open(FileName, ios::out | ios::binary);
char ch, ch2;
unsigned long long totalLen = 0;
unsigned long long totalFreq = 0;
writebytes(fout, dataCnt, 1);
writebytes(fout, bitsCnt, 3);
for (int i = data.size() - 1; i >= 0; i--)
{
fout.put(data[i].symbol);
writebytes(fout, chars[data[i].symbol]->codeword, 3);
fout.put(unsigned char(chars[data[i].symbol]->codewordLen));
totalLen += unsigned long long(chars[data[i].symbol]->codewordLen) * chars[data[i].symbol]->freq;
totalFreq += unsigned long long(chars[data[i].symbol]->freq);
}
printf("bpp: %lf \n", totalLen * 1.0 / totalFreq);
fout.close();
}
调用：
#include"HuffmanCoding.h"
#include"HXLBMPFILE.h"
using namespace std;
int main()
{
HXLBMPFILE originalfile;
HXLBMPFILE source;
HuffmanCoding Huffman;
if (!originalfile.LoadBMPFILE("gray.bmp"))
exit(1);
source.imagew = originalfile.imagew;
source.imageh = originalfile.imageh;
source.iYRGBnum = originalfile.iYRGBnum;
*source.palette = *originalfile.palette;
if (!source.AllocateMem())
exit(1);
for (int i = 0; i < originalfile.imageh; i++)
for (int j = 0; j < originalfile.imagew; j++)
source.pDataAt(i)[j] = originalfile.pDataAt(i)[j];
Huffman.encode(&source, "file.dat", "code.dat");
return 0;
}
decode：
#pragma once
#include"HXLBMPFILE.h"
#include<algorithm>
#include<cstring>
#include<fstream>
#include<vector>
using namespace std;
class HuffmanNode
{
public:
unsigned char symbol;
unsigned int codeword;
unsigned short codewordLen;
HuffmanNode* left, * right;
HuffmanNode()
{
left = right = 0;
}
HuffmanNode(unsigned char s, HuffmanNode* lf = 0, HuffmanNode* rt = 0)
{
symbol = s;
left = lf, right = rt;
}
};
class ListNode
{
public:
HuffmanNode* tree;
ListNode* prev, * next;
ListNode()
{
next = prev = 0;
}
ListNode(ListNode* p, ListNode* n)
{
prev = p, next = n;
}
};
class HuffmanCoding
{
public:
const unsigned int ASCII;
const unsigned int bits;
const unsigned short mask = 0xffff;
HuffmanNode* HuffmanTree, ** chars;
unsigned short dataCnt;
unsigned int bitsCnt;
HuffmanCoding() : ASCII(256), bits(8)
{
chars = new HuffmanNode * [ASCII + 1];
for (int i = 0; i < ASCII; i++)
chars[i] = 0;
}
void decode(HXLBMPFILE*, const char*, const char*);
void loadCode(const char*);
unsigned int readbytes(ifstream&, int);
void rebuildHuffmanNode(unsigned char, HuffmanNode*, unsigned int, unsigned short);
void rebuildHuffmanTree();
void inputHeader(HXLBMPFILE*, const char*);
void inputData(HXLBMPFILE*, const char*);
};
void HuffmanCoding::decode(HXLBMPFILE* bmpfile, const char* FileName1, const char* FileName2)
{
loadCode(FileName2);
rebuildHuffmanTree();
inputHeader(bmpfile, FileName1);
inputData(bmpfile, FileName1);
}
unsigned int HuffmanCoding::readbytes(ifstream& fin, int bytes)
{
unsigned int num;
num = unsigned int(fin.get());
for (int i = 1; i < bytes; i++)
{
num <<= bits;
num |= unsigned int(fin.get());
}
return num;
}
void HuffmanCoding::loadCode(const char* FileName)
{
ifstream fin;
fin.open(FileName, ios::in | ios::binary);
unsigned char ch;
if (!fin)
exit(1);
dataCnt = readbytes(fin, 1);
bitsCnt = readbytes(fin, 3);
for (int i = 0; i < dataCnt; i++)
{
ch = unsigned char(readbytes(fin, 1));
chars[ch] = new HuffmanNode(ch);
chars[ch]->codeword = readbytes(fin, 3);
chars[ch]->codewordLen = readbytes(fin, 1);
}
}
void HuffmanCoding::rebuildHuffmanNode(unsigned char ch, HuffmanNode* p, unsigned int codeword, unsigned short codewordLen)
{
if (codewordLen == 0)
{
p->codeword = chars[ch]->codeword;
p->codewordLen = chars[ch]->codewordLen;
p->right = p->left = 0;
p->symbol = ch;
}
else
{
if ((codeword >> (codewordLen - 1)) & 1)
{
if (p->right == NULL)
p->right = new HuffmanNode('\0');
rebuildHuffmanNode(ch, p->right, codeword, codewordLen - 1);
}
else
{
if (p->left == NULL)
p->left = new HuffmanNode('\0');
rebuildHuffmanNode(ch, p->left, codeword, codewordLen - 1);
}
}
}
void HuffmanCoding::rebuildHuffmanTree()
{
ListNode* head;
head = new ListNode;
head->tree = new HuffmanNode;
for (int ch = 0; ch < ASCII; ch++)
{
if (chars[unsigned char(ch)] != NULL)
{
rebuildHuffmanNode(ch, head->tree, chars[ch]->codeword, chars[ch]->codewordLen);
}
}
HuffmanTree = head->tree;
}
void HuffmanCoding::inputHeader(HXLBMPFILE* bmpfile, const char* FileName)
{
FILE* f;
f = fopen(FileName, "r+b");
BITMAPFILEHEADER fh;
BITMAPINFOHEADER ih;
fread(&fh, sizeof(BITMAPFILEHEADER), 1, f);
if (fh.bfType != 0x4d42)
{
fclose(f);
return;
}
fread(&ih, sizeof(BITMAPINFOHEADER), 1, f);
if ((ih.biBitCount != 8) && (ih.biBitCount != 24))
{
fclose(f);
return;
}
(*bmpfile).iYRGBnum = ih.biBitCount / 8;
(*bmpfile).imagew = ih.biWidth;
(*bmpfile).imageh = ih.biHeight;
if (!(*bmpfile).AllocateMem())
{
fclose(f);
return;
}
if ((*bmpfile).iYRGBnum == 1)
fread((*bmpfile).palette, sizeof(RGBQUAD), 256, f);
fseek(f, fh.bfOffBits, SEEK_SET);
fclose(f);
}
void HuffmanCoding::inputData(HXLBMPFILE* bmpfile, const char* FileName)
{
ifstream fin;
fin.open(FileName, ios::in | ios::binary);
unsigned char ch = 0;
unsigned long long nowbits = 0, nowbitsCnt = 0;
int i = (*bmpfile).imageh - 1, j = 0;
int mask = 1 << (bits - 1);
if (!fin)
exit(1);
fin.seekg(sizeof(BITMAPFILEHEADER) + sizeof(BITMAPINFOHEADER) + (((*bmpfile).iYRGBnum == 1) ? 256 * sizeof(RGBQUAD) : 0), ios::beg);
ch = fin.get();
while (nowbitsCnt < bitsCnt && i >= 0)
{
for (HuffmanNode* p = HuffmanTree; ;)
{
if (p->left == 0 && p->right == 0)
{
(*bmpfile).pDataAt(i)[j] = p->symbol;
if (++j == (*bmpfile).imagew)
j = 0, i--;
nowbitsCnt += p->codewordLen;
break;
}
else if ((ch & mask) == 0)
p = p->left;
else
p = p->right;
if (++nowbits == bits)
{
ch = fin.get();
nowbits = 0;
}
else
ch <<= 1;
}
}
fin.close();
}
调用：
#include"HuffmanCoding.h"
#include"HXLBMPFILE.h"
using namespace std;
int main()
{
HXLBMPFILE target;
HuffmanCoding Huffman;
const char* FileName = "gray.bmp";
Huffman.decode(&target, "file.dat", "code.dat");
target.SaveBMPFILE(FileName);
}
Processed:
0.010, SQL:
9
