LZW编码解码 C++

为了给单片机的一些常量数据压缩下，找到了简单的lzw压缩算法

网上找了一个源码，发现没达到最优的压缩，又改了下，

主要是bit数据的存放统一用16位，太浪费，变为动态调整

测试代码如下

    uint8_t org[]={
        //'q','q','q','q','q','q','q','w','c'
        //'O','n','e','d','a','y'
		//'X','y','m','y','m','o','t'
		'A','B','R','A','C','A','D','A','B','R','A','B','R','A','B','R','A'
        ,0x00
        };
    //为方便测试，这里只测试了字母，用0x00结尾。
    //其实可以是任意16进制数，数据结尾自定义
    uint8_t* c=org;
	int orgSize=0;
	while(*c){
		orgSize++;
		c++;
	}
	printf("orgSize:%drn",orgSize);

    //把org[]编码压缩到endatas[]中
    uint8_t endatas[300];
    Biter bitPuter(endatas);

    LzwCode lzwCode(200);
    lzwCode.Encode(org,orgSize,&bitPuter);
    
    Serial.printf("encode data:rn");
    for(int i=0;i 
源文件如下：
 
编解码代码 lzw.h lzw.cpp
 
#ifndef _MY_LZW_H
#define _MY_LZW_H

#include 
#include "Biter.h"

class DictItem {
  public:
    //0x00-0xff为【基本元素】，不超过8位
    uint8_t suffix;

    int parent;
    int firstchild;
    int nextsibling;
  private:
};

class LzwCode {
  public:
    LzwCode(uint16_t dsize0);
    ~LzwCode();

    void Init(uint16_t dsize0);
    void Dispose();

    void Encode(uint8_t* fp,int size, Biter *bf);
    int Decode(Biter *bf,uint8_t *fp);

    void PrintDictionary();

  private:
    DictItem* dictionary=0;
    uint16_t dictSize;
    //下一个字典的编码
    uint16_t next_code;

    uint8_t bitw;//读取、写入的bit位数
    uint32_t bitm;//掩码

    void InitDictionary();
    int DecodeString(int start, int code,uint8_t* list);
    int InDictionary(int character, int string_code);
    void AddToDictionary(int character, int string_code,uint8_t decode=0);
};

#endif
 
#include "lzw.h"

LzwCode::LzwCode(uint16_t dsize0){
    Init(dsize0);
}

LzwCode::~LzwCode(){
    Dispose();
}


void LzwCode::Init(uint16_t dsize0){
    Dispose();

	dictSize=dsize0+256;
    dictionary=new DictItem[dictSize];
}

void LzwCode::Dispose(){
    if(dictionary){
        delete[] dictionary;
        dictionary=0;
    }
}


void LzwCode::InitDictionary(){
    //以0x00-0xff为【基本元素】，所以有256个元素
	for(int i=0; i<256; i++){
		dictionary[i].suffix = i;
		dictionary[i].parent = -1;
		dictionary[i].firstchild = -1;
		dictionary[i].nextsibling = i+1;
	}
	dictionary[255].nextsibling = -1;

	next_code = 256;
}


void LzwCode::PrintDictionary(){
	int n;
	int count;
	//存放扩展元素（每个是基本元素），
	//单个扩展元素包含的基本元素不超过50个
	uint8_t list[50];

	Serial.printf("dict:rn");
	for(n=256; n", n);
		count = DecodeString(0, n, list);
		while(count-- > 0)
			Serial.printf("%c", (char)(list[count]));
		Serial.printf( "rn");
	}
}


int LzwCode::DecodeString(int start, int code,uint8_t* list){
	int index = start;

	while(code>=0){
		list[index] = dictionary[code].suffix;
		code = dictionary[code].parent;
		index++;
	}
	return index;
}


int LzwCode::InDictionary(int character, int string_code){
	int sibling;//下一个
	if(string_code<0)
        return character;

	sibling = dictionary[string_code].firstchild;
	while(sibling>-1){
		if(character == dictionary[sibling].suffix)
            return sibling;
		sibling = dictionary[sibling].nextsibling;
	}
	return -1;
}


void LzwCode::AddToDictionary(int character, int string_code,uint8_t decode){
	int firstsibling, nextsibling;

	if(decode){
		if((next_code&bitm)!=0){
			bitm<<=1;
			bitw++;
			Serial.printf("bitw %drn", bitw);
		}
	}

	if(0>string_code)
        return;

	if(next_code>=dictSize){
		Serial.printf("Dictionary overflow!!!!rn");
		return;
	}

	dictionary[next_code].suffix = character;
	dictionary[next_code].parent = string_code;
	dictionary[next_code].nextsibling = -1;
	dictionary[next_code].firstchild = -1;
	firstsibling = dictionary[string_code].firstchild;
	if(-1Put(dsize,3*8);
	
	InitDictionary();

	string_code = -1;
	while(nPut(string_code,bitw);

            AddToDictionary(character, string_code);
			
			string_code = character;
		}
	}
    bp->Put(string_code,bitw);
	bp->Flush();
}


int LzwCode::Decode(Biter *bf,uint8_t *fp){
	int character;
	int new_code, last_code;
	int phrase_length;

	//存放扩展元素（每个是基本元素），
	//单个扩展元素包含的基本元素不超过50个
	uint8_t list[50];
	
	int n=0;
	bitw=8;
	bitm=1<<8;

	int size=bf->Get(3*8);
	int orgsize=size;
	Serial.printf("size:%drn", size);
	
	InitDictionary();
	last_code = -1;
	while (size>0) {
		new_code = (int)bf->Get(bitw);
		if (new_code >= next_code) { // this is the case CSCSC( not in dict)
			list[0] = character;
			phrase_length = DecodeString(1, last_code,list);
		} else {
			phrase_length = DecodeString(0, new_code,list);
		}
		character = list[phrase_length - 1];
		while (0 < phrase_length) {
			phrase_length--;
			fp[n++]=list[phrase_length];
			size--;
		}

        AddToDictionary(character, last_code,1);
            
		last_code = new_code;
	}

	return orgsize;
}
 
比特操作代码  Biter.h Biter.cpp
 
#ifndef _MY_BITER_H
#define _MY_BITER_H

#include 

class Biter {
  public:
    Biter(uint8_t* datas0,uint32_t datasize0=0);
    void Init(uint8_t* datas0,uint32_t datasize0=0);

    uint32_t Get(int bitWidth);
    void Put(uint32_t data, int bitWidth);
    void Flush();
    int Size();

  private:
    uint8_t* datas;
	  uint32_t datasize;

    uint32_t index;//datas的存放位置
    uint8_t mask;//当前bit存放的位置

    uint8_t cache;//写入的缓存，满8位存入datas、或一次读取8位
    
    uint8_t GetBit();
    void PutBit(uint8_t bit);
};

#endif
 
#include "Biter.h"

Biter::Biter(uint8_t *datas0, uint32_t datasize0)
{
	Init(datas0, datasize0);
}

void Biter::Init(uint8_t *datas0, uint32_t datasize0)
{
	this->datas = datas0;
	this->datasize = datasize0;
	this->index = 0;
	this->mask = 0x80;
	this->cache = 0;
}




uint8_t Biter::GetBit()
{
	if (this->mask == 0x80)
	{
		if (this->index == this->datasize)
		{
			return 0;
		}
		this->cache = this->datas[this->index++];
	}

	uint8_t value = this->mask & this->cache;

	if (this->mask == 0x01)
		this->mask = 0x80;
	else
		this->mask >>= 1;

	return value ? 1 : 0;
}


uint32_t Biter::Get(int bitWidth)
{
	uint32_t maskv;
	uint32_t value;

	maskv = 1L << (bitWidth - 1);
	value = 0L;
	while (maskv != 0)
	{
		if (GetBit())
			value |= maskv;
		maskv >>= 1;
	}

	return value;
}




void Biter::PutBit(uint8_t bit)
{
	// 1则写入，0不变
	if (bit != 0)
		this->cache |= this->mask;

	this->mask >>= 1;
	if (this->mask == 0)
	{
		// 满8位存入
		this->datas[this->index++] = this->cache;
		this->cache = 0;
		this->mask = 0x80;
	}
}


void Biter::Put(uint32_t data, int bitWidth)
{
	uint32_t maskv;

	maskv = 1L << (bitWidth - 1);
	while (maskv != 0)
	{
		PutBit((data & maskv) ? 1 : 0);

		maskv >>= 1;
	}
}

void Biter::Flush()
{
	// 如果填充没完成，把剩余的放入数据
	if (this->mask == 0x80)
	{
		this->datas[this->index++] = this->cache;
	}
}


int Biter::Size()
{
	return this->index;
}