BitInputStream.h

  1. #pragma once
  3. #include <vector>
  4. #include <string>
  5. #include "Common.h"
  7. class BitInputStream
  8. {
  9. private:
  10.     typedef unsigned char byte;
  12.     FILE* file;
  13.     byte* buffer;
  14.     int bufferMaxSize;
  15.     int maxBitSize;
  16.     int pos;
  18. public:
  19.     BitInputStream(const std::string &inputFileName, int bufferSize) {
  20.         file = fopen(inputFileName.c_str(), "rb");
  21.         if (file == nullptr) {
  22.             throw std::exception("input file not found");
  23.         }
  24.         buffer = new byte[bufferSize];
  25.         this->bufferMaxSize = bufferSize;
  26.         fill();
  27.         pos = 0;
  28.     }
  30.     ~BitInputStream() {
  31.         close();
  32.     }
  34. public:
  35.     bool readBit() {
  36.         int bytePos = pos / 8;
  37.         int bitPos = pos % 8;
  38.         bool ret = (buffer[bytePos] >> bitPos) & 1;
  39.         pos += 1;
  40.         if (pos >= maxBitSize) fill();
  41.         return ret;
  42.     }
  44.     byte readByte() {
  45.         byte num = 0;
  46.         for (int i = 0; i < 8; i++) {
  47.             bool val = readBit();
  48.             if (val) {
  49.                 num |= (1 << i);
  50.             }
  51.         }
  52.         return num;
  53.     }
  55.     int readInt32() {
  56.         int num = 0;
  57.         for (int i = 0; i < 32; i++) {
  58.             bool val = readBit();
  59.             if (val) {
  60.                 num |= (1 << i);
  61.             }
  62.         }
  63.         return num;
  64.     }
  66.     __int64 readInt64() {
  67.         __int64 num = 0;
  68.         for (int i = 0; i < 64; i++) {
  69.             bool val = readBit();
  70.             if (val) {
  71.                 num |= ((__int64)1 << i);
  72.             }
  73.         }
  74.         return num;
  75.     }
  77.     void close() {
  78.         delete buffer;
  79.         fclose(file);
  80.     }
  82. private:
  83.     //从文件中读入数据到缓冲区
  84.     void fill() {
  85.         int cnt = fread(buffer, 1, bufferMaxSize, file);
  86.         maxBitSize = cnt * 8;
  87.         pos = 0;
  88.     }
  89. };

BitOutputStream.h

  1. #pragma once
  3. #include <string>
  5. class BitOutputStream
  6. {
  7. private:
  8.     typedef unsigned char byte;
  10.     FILE* file;
  11.     byte* buffer;
  12.     int BUFFER_SIZE;
  13.     int bitsize;
  15. public:
  16.     BitOutputStream(const std::string &outputFileName, int bufferSize) {
  17.         file = fopen(outputFileName.c_str(), "wb");
  18.         if (file == nullptr) {
  19.             throw std::exception("dst file not found");
  20.         }
  21.         buffer = new byte[bufferSize];
  22.         memset(buffer, 0, bufferSize);
  23.         this->BUFFER_SIZE = bufferSize;
  24.         bitsize = 0;
  25.     }
  27.     ~BitOutputStream() {
  28.         if (file != nullptr) {
  29.             close();
  30.         }
  31.     }
  33.     void close() {
  34.         flush();
  35.         fclose(file);
  36.         file = nullptr;
  37.         delete[] buffer;
  38.         buffer = nullptr;
  39.     }
  41.     void writeBit(bool val) {
  42.         //static int cnt = 0;
  43.         //putchar(val ? '1' : '0');
  44.         //cnt += 1;
  45.         //if (cnt == 8) {
  46.         //    putchar(' ');
  47.         //    cnt = 0;
  48.         //}
  50.         if (val == true) {
  51.             int bytePos = bitsize / 8;
  52.             int bitPos = bitsize % 8;
  53.             buffer[bytePos] |= 1 << bitPos;
  54.         }
  55.         bitsize += 1;
  56.         if (bitsize == BUFFER_SIZE * 8) {
  57.             flush();
  58.         }
  59.     }
  61.     void writeByte(byte num) {
  62.         for (int i = 0; i < 8; i++) {
  63.             writeBit(num & 1);
  64.             num = num >> 1;
  65.         }
  66.     }
  68.     void writeInt32(int num) {
  69.         for (int i = 0; i < 32; i++) {
  70.             writeBit(num & 1);
  71.             num = num >> 1;
  72.         }
  73.     }
  75.     void writeInt64(__int64 num) {
  76.         for (int i = 0; i < 64; i++) {
  77.             writeBit(num & 1);
  78.             num = num >> 1;
  79.         }
  80.     }
  82. private:
  83.     //将缓冲区中的数据写入到文件中
  84.     void flush() {
  85.         int byteSize = bitsize % 8 == 0 ? bitsize / 8 : bitsize / 8 + 1;
  86.         fwrite(buffer, 1, byteSize, file);
  87.         memset(buffer, 0, BUFFER_SIZE);    //将buffer中所有元素重置为0
  88.         bitsize = 0;
  89.     }
  91. };

Common.h

  1. #pragma once
  3. typedef unsigned char byte;
  4. const int N = 256;
  6. struct HufNode {
  7.     byte ch;
  8.     size_t freq;
  9.     HufNode *lchild, *rchild;
  11.     HufNode() :ch(0), freq(0), lchild(nullptr), rchild(nullptr) {}
  12.     HufNode(byte ch) :ch(ch), freq(0), lchild(nullptr), rchild(nullptr) {}
  13.     HufNode(byte ch, size_t freq) :ch(ch), freq(freq), lchild(nullptr), rchild(nullptr) {}
  15.     bool isLeaf() {
  16.         return lchild == nullptr && rchild == nullptr;
  17.     }
  18. };

FileCompress.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <queue>
  5. #include <vector>
  6. #include <functional>
  8. #include "BitOutputStream.h"
  9. #include "Common.h"
  10. using namespace std;
  12. class FileCompress {
  13. private:
  14.     size_t byteFrequence[N] = { 0 };    //统计每个字符出现的频次
  15.     vector<bool> codeTable[N];    //每个字符的编码表
  16.     BitOutputStream* bos;
  18.     void countFrequence(const char* src) {
  19.         FILE* f = fopen(src, "rb");
  20.         if (f == NULL) {
  21.             perror("open src file error");
  22.             exit(0);
  23.         }
  25.         byte data;
  26.         while (true) {
  27.             int size = fread(&data, sizeof(byte), 1, f);
  28.             if (size == 0) break;
  29.             byteFrequence[data] += 1;
  30.         }
  31.         fclose(f);
  32.     }
  34.     void writeContent(const char* src) {
  35.         FILE* f = fopen(src, "rb");
  36.         if (f == NULL) {
  37.             perror("open src file error");
  38.             exit(0);
  39.         }
  41.         byte data;
  42.         while (!feof(f)) {
  43.             int size = fread(&data, 1, 1, f);
  44.             if (size == 0) break;
  45.             for (bool b : codeTable[data]) {
  46.                 bos->writeBit(b);
  47.             }
  48.         }
  49.         fclose(f);
  50.     }
  52.     struct cmp {
  53.         bool operator() (HufNode* n1, HufNode* n2) {
  54.             return n1->freq > n2->freq;
  55.         }
  56.     };
  58.     HufNode* createHufTree() {
  59.         priority_queue<HufNode*, vector<HufNode*>, cmp> pq;
  60.         for (int i = 0; i < N; i++) {
  61.             if (byteFrequence[i] == 0) continue;
  62.             HufNode* temp = new HufNode(i, byteFrequence[i]);
  63.             pq.push(temp);
  64.         }
  65.         while (pq.size() > 1) {
  66.             HufNode* node1 = pq.top(); pq.pop();
  67.             HufNode* node2 = pq.top(); pq.pop();
  68.             HufNode* partent = new HufNode(0, node1->freq + node2->freq);
  69.             partent->lchild = node1;
  70.             partent->rchild = node2;
  71.             pq.push(partent);
  72.         }
  73.         return pq.top();
  74.     }
  76.     void writeHufTree(HufNode* root) {
  77.         if (root->isLeaf()) {
  78.             bos->writeBit(true);
  79.             bos->writeByte(root->ch);
  80.             return;
  81.         }
  82.         bos->writeBit(false);
  83.         writeHufTree(root->lchild);
  84.         writeHufTree(root->rchild);
  85.     }
  87.     void dfs(HufNode* root, vector<bool> &path) {
  88.         if (root == NULL) return;
  89.         if (root->isLeaf()) {
  90.             codeTable[root->ch] = path;
  91.         }
  92.         else {
  93.             path.push_back(false);
  94.             dfs(root->lchild, path);
  95.             path.pop_back();
  97.             path.push_back(true);
  98.             dfs(root->rchild, path);
  99.             path.pop_back();
  100.         }
  101.     }
  103.     void generateCodeTable(HufNode* root) {
  104.         vector<bool> path;
  105.         dfs(root, path);
  106.     }
  108.     __int64 calcTotalBits() {
  109.         __int64 cnt = 0;
  110.         for (int i = 0; i < N; i++) {
  111.             cnt += (__int64)byteFrequence[i] * codeTable[i].size();
  112.         }
  113.         return cnt;
  114.     }
  116. public:
  118.     void compress(const char* inputFilePath, const char* outputFilePath) {
  119.         countFrequence(inputFilePath);
  120.         HufNode* root = createHufTree();
  121.         generateCodeTable(root);
  122.         bos = new BitOutputStream(outputFilePath, 1024 * 1024 * 8);
  124.         writeHufTree(root);
  125.         __int64 cnt = calcTotalBits();
  126.         bos->writeInt64(cnt);
  127.         writeContent(inputFilePath);
  128.         bos->close();
  129.     }
  130. };

FileDecompress.h

  1. #pragma once
  3. #include "BitInputStream.h"
  4. #include "Common.h"
  6. class FileDecompress {
  7. private:
  8.     BitInputStream* bis;
  10.     HufNode* createHufTree() {
  11.         bool val = bis->readBit();
  12.         if (val) {    // 1表示叶节点
  13.             byte ch = bis->readByte();
  14.             return new HufNode(ch);
  15.         }
  16.         else {    // 0 表示非叶节点，且一定有两个孩子
  17.             HufNode* root = new HufNode();
  18.             root->lchild = createHufTree();
  19.             root->rchild = createHufTree();
  20.             return root;
  21.         }
  22.     }
  24. public:
  25.     void decompress(const char* inputFilePath, const char* outputFilePath) {
  26.         bis = new BitInputStream(inputFilePath, 1024 * 1024 * 8);
  27.         HufNode* root = createHufTree();
  28.         __int64 totalBitCnt = bis->readInt64();
  30.         FILE* output = fopen(outputFilePath, "wb");
  31.         if (output == nullptr) {
  32.             perror("");
  33.             exit(0);
  34.         }
  36.         HufNode* p = root;
  37.         for (__int64 i = 0; i < totalBitCnt; i++) {
  38.             bool b = bis->readBit();
  39.             if (b == false) {
  40.                 p = p->lchild;
  41.             }
  42.             else {
  43.                 p = p->rchild;
  44.             }
  45.             if (p->isLeaf()) {
  46.                 byte data = p->ch;
  47.                 fwrite(&data, sizeof(byte), 1, output);
  48.                 p = root;
  49.             }
  50.         }
  51.         fclose(output);
  52.         bis->close();
  53.     }
  54. };

main.cpp

  1. #include <iostream>
  3. #include "FileCompress.h"
  4. #include "FileDecompress.h"
  5. using namespace std;
  7. int main(int argc, char* argv[]) {
  8.     if (argc != 4) {
  9.         cout << "参数个数错误！" << endl;
  10.         cout << "使用方法。。。。" << endl;
  11.         exit(0);
  12.     }
  14.     if (strcmp(argv[1], "zip") == 0) {
  15.         FileCompress f;
  16.         f.compress(argv[2], argv[3]);
  17.     }
  18.     else if (strcmp(argv[1], "unzip") == 0) {
  19.         FileDecompress f;
  20.         f.decompress(argv[2], argv[3]);
  21.     }
  22.     else {
  23.         cout << "unknown command" << endl;
  24.     }
  26.     //FileCompress f;
  27.     //f.compress("D:/1.exe", "D:/temp.dat");
  29.     //FileDecompress f2;
  30.     //f2.decompress("D:/temp.dat", "D:/2.exe");
  32.     return 0;
  33. }