RLE算法

鼯鼠

找到两篇介绍RLE算法的文章，结合着看，理解了这个算法的目的是压缩重复的字节。大量应用在图形压缩上的原因，是因为图片中通常有很多相同颜色的区域(比如一片全黑的背景)。

RLE的基本思路是，把数据分两种情况对待：
A1.一些连续的重复字节
A2.一些连续的，不相重复的字节

RLE压缩最常见的一种算法思路：

将全部的数据分成很多块，这些块的长度各不一样:
all data = [block] + [block] + ... + [block]
每一块由两部分顺序组成:
a block = [header] + [data]
其中header部分占2字节16位，这16位中的最高位，标志了这个block的属性，是属于上面的A1还是A2。对应于A1和A2，剩下的15位以及后面的Data部分的意义又分为两种：
A1: block的剩下15位记录重复的次数，取值范围[0,32767]；data段仅含一个字节，即重复的那个字节
A2: block的剩下15位记录data段有多少个字节；data段则是一系列不相重复的字节。

举例：(来自《汉化基础教程——压缩篇》)
文本字符串：A A A A A B C D E F F F。编码后得到：85 A 4 B C D E 83 F（85H= 10000101B、4H= 00000100B、83H= 10000011B）

参考:
《汉化基础教程——压缩篇》by 全球通 PGCG汉化组（该文还介绍了两外两种RLE算法，以及与GBA、汉化有关的其它压缩算法）
http://www.tgbus.com/htm/GBA/edu/cnedu/20041215215029-1.html
《Run Length Encoding compressor program, 16 bit header version》by Shaun Case
http://www.gamedev.net/reference/articles/article290.asp

字符串的加密与解密的各种方法（RLE算法）[转帖]

CRLECompressioin rle;
char src[] = "11122233333336666666666666666666666666666666666666666666";
char dest[100];
char dest1[100];
memset(dest, 0, 100);
memset(dest1, 0, 100);
int len = strlen(src);
int rc = rle.Compress((unsigned char*)src, len, (unsigned char*)dest);
int rc1 = rle.Decompress((unsigned char*)dest, rc, (unsigned char*)dest1);
/////////////////////////////////////////////////////////////////////////////

class CRLECompressioin
{
public:
CRLECompressioin();
virtual ~CRLECompressioin();

int Compress(unsigned char* src, int len, unsigned char* dest);
int Decompress(unsigned char* src, int len, unsigned char* dest);
};

// RLECompressioin.cpp: implementation of the CRLECompressioin class.
//
//////////////////////////////////////////////////////////////////////

#include "Compress.h"

const unsigned char DELIM = (char)0xFF;
const unsigned char MAX = (char)0xFE;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CRLECompressioin::CRLECompressioin()
{

}

CRLECompressioin::~CRLECompressioin()
{

}

int CRLECompressioin:: Compress(unsigned char* src, int len, unsigned char* dest)
{
unsigned char current_char;
int char_count = 0;

int iCompressedLen = 0;

for(int iLoop = 0; iLoop < len; iLoop++)
{
if((src[iLoop] == src[iLoop + 1]) && (src[iLoop] == src[iLoop + 2]))
{
current_char = src[iLoop];
char_count = 0x00;
bool hit_end = false;
for(int iLoop2 = 0; iLoop2 < 0xFE; iLoop2++)
{
if(src[iLoop + iLoop2] == current_char)
{
char_count++;
}
else
{
iLoop += (char_count - 1);
dest[iCompressedLen++] = DELIM;
dest[iCompressedLen++] = char_count;
dest[iCompressedLen++] = current_char;
iLoop2 = 0xFE;
hit_end = true;
}
}
if(!hit_end)
{
iLoop += 0xFD;
dest[iCompressedLen++] = DELIM;
dest[iCompressedLen++] = MAX;
dest[iCompressedLen++] = current_char;
}
}
else
{
if(src[iLoop] == DELIM)
{
dest[iCompressedLen++] = DELIM;
dest[iCompressedLen++] = DELIM;
}
else
{
dest[iCompressedLen++] = src[iLoop];
}
}
}

return iCompressedLen;

}

int CRLECompressioin:ecompress(unsigned char* src, int len, unsigned char* dest)
{

int iDecompressedLen = 0;

for(int iLoop = 0; iLoop < len; iLoop++)
{
if(src[iLoop] == DELIM)
{
if(src[iLoop + 1] == DELIM)
{
dest[iDecompressedLen++] = src[iLoop];
iLoop++;
}
else
{
int iBufSize = (int)src[iLoop + 1];
for(int iLoop2 = 0; iLoop2 < iBufSize; iLoop2++)
{
dest[iDecompressedLen++] = src[iLoop+2];
}
iLoop += 2;
}
}
else
{
dest[iDecompressedLen++] = src[iLoop];
}
}

return iDecompressedLen;
}

[此贴子已经被作者于2006-3-25 16:23:23编辑过]

cgj888

老鼠在线吗

鼯鼠

RLE算法
　　这种压缩编码是一种变长的编码，RLE根据文本不同的具体情况会有不同的压缩编码变体与之相适应，以产生更大的压缩比率。

　　变体1：重复次数+字符
文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。

　　变体2：特殊字符+重复次数+字符
文本字符串：A A A A A B C C C C B C C C，编码后得到：B B 5 A B B 4 C B B 3 C。编码串的最开始说明特殊字符B，以后B后面跟着的数字就表示出重复的次数。

　　变体3：把文本每个字节分组成块，每个字符最多重复 127 次。每个块以一个特殊字节开头。那个特殊字节的第 7 位如果被置位，那么剩下的7位数值就是后面的字符的重复次数。如果第 7 位没有被置位，那么剩下 7 位就是后面没有被压缩的字符的数量。例如：文本字符串：A A A A A B C D E F F F。编码后得到：85 A 4 B C D E 83 F（85H= 10000101B、4H= 00000100B、83H= 10000011B）

　　以上3种不RLE变体是最常用的几种，其他还有很多很多变体算法，这些算法在Winzip Winrar这些软件中也是经常用到的。

-------------------------------------------------------------------

RLE压缩及优化

简单的说RLE压缩就是将一串连续的相同数据转化为特定的格式达到压缩的目的。

下面都对byte流压缩。
如输入数据
LPBTE pByte={1,1,1,1,1,1};
压缩的数据为6,1
压缩了4个字符。

但是在数据流里面不能直接这么替换，而应该使用特殊的控制字符，否则无法解压。

比如pByte={6,1,0,1,1,1,1,1,1};

这样有两个6,1无法判断是原有的6,1还是{1,1,1,1,1,1}压缩后的代码。

所以应该有控制字符。
(1)
为了达到最大压缩率，可以先扫描源数据流，使用最少出现的字符做控制字符。

如 pByte={6,1,0,1,1,1,1,1,1,...};
扫描后发现0为最少出现的字符。

我们使用0作为压缩的控制，其他字符代表他本身。源数据里面的0,用0,0来表示。
那么pByte压缩后为
6,1,0,0,0,6,1 ......

解压时 BYTE a,b,c;

a=依次扫描压缩数据，如果输入字符为非控制字符，则直接输出到解压流。

如果为控制字符，b=其下一字符是否也为控制字符，如果是，在输出流输出控制字符的代码。

如果不是c=读压缩流，然后输出b个c到输出流。

注意:该处对于>Ctrlcode 的编码需要自己计算偏移.

如ctrl=2.那么n=3时应该修正为2.

刚才介绍的方法是最大压缩率的，但是因为对每个输入字符需要检查，速度不算快。

(2)
为了增加解压速度，可以采用其他的编码方式。
主要方法是不对每个输入字符进行检查，只检查较少次就达到几乎相同的压缩率。

来看看这个改进的方法。

仔细观察，其实对不重复的字符也可以用控制n+数据的方式表示。这里的n带表n个未压缩数据。


还是刚才的数据。
pByte={6,1,0,1,1,1,1,1,1}
不用扫描选择0为控制

压缩为3,{6,1,0,}　0,　 6, 1
　　　n　　　　　 ctrl n　m

解压就非常方便了

扫描数据读一个字符，
{
n=read;
if(n)
　　　　　　　　　 {　　
字符拷贝n个
　　　　　　　　　 }
else
{
n=read();
m=read;
write (n个m);
}

}

(3)优化

对(1)的优化。
观察得知，1,1,1这样的数据压缩率为0,
所以当n<=3时不用压缩。
而直接写为1,1,1样的格式。

另外如果有多个控制字符连续。也可以压缩。
观察ctrl=0;
0,0,0,0
如果用控制编码为8个0
而压缩编码为0,4,0 所以控制字符连续两个即可压缩。

对(2)：

只对压缩编码优化。
例
1,2,3,4,1,1
如果死套公式，为
4,1,2,3,4,0,2,1
反倒增加2个字节。
如果用
6,1,2,3,4,1,1只增加一个字节。

[此贴子已经被作者于2006-3-25 18:21:31编辑过]

鼯鼠

在阿～～

cgj888

有QQ吗

联系下在论坛里说不清楚啊

关于DX9.0的

蚊子

我还没见过论坛上说不清的呢～～呵呵

鼯鼠

我的QQ324007255  不过最好在论坛上留言  我不太用QQ

cgj888

就是我的程序写起来后,那画面会隔点时间闪烁

cgj888

主程序代码这样的

#include "stdafx.h"
#include "myd3d.h"
#include "tianjie.h"

#define MAX_LOADSTRING 100

// 全局变量:
HINSTANCE hInst; // 当前实例
TCHAR szTitle[MAX_LOADSTRING]; // 标题栏文本
TCHAR szWindowClass[MAX_LOADSTRING]; // 主窗口类名
void Render();
d3dTexture a_Bk ;

// 此代码模块中包含的函数声明:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
int APIENTRY _tWinMain(HINSTANCE hInstance,
HINSTANCE hPrevInstance,
LPTSTR lpCmdLine,
int nCmdShow)

{
// TODO: 在此放置代码。
MSG msg;
HACCEL hAccelTable;

// 初始化全局字符串
LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
LoadString(hInstance, IDC_TIANJIE, szWindowClass, MAX_LOADSTRING);
MyRegisterClass(hInstance);

// 执行应用程序初始化:
if (!InitInstance (hInstance, nCmdShow))
{
return FALSE;
}

hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_TIANJIE);

// 主消息循环:
while (GetMessage(&msg, NULL, 0, 0))
{
if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
{
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}

return (int) msg.wParam;
}

//
// 函数: MyRegisterClass()
//
// 目的: 注册窗口类。
//
// 注释:
//
// 仅当希望在已添加到 Windows 95 的
// “RegisterClassEx”函数之前此代码与 Win32 系统兼容时，
// 才需要此函数及其用法。调用此函数
// 十分重要，这样应用程序就可以获得关联的
// “格式正确的”小图标。
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
WNDCLASSEX wcex;
wcex.cbSize = sizeof(WNDCLASSEX);
wcex.style = CS_HREDRAW | CS_VREDRAW; //窗口类型
wcex.lpfnWndProc = (WNDPROC)WndProc; //窗口的消息处理函数
wcex.cbClsExtra = 0;
wcex.cbWndExtra = 0;
wcex.hInstance = hInstance; //程序的实例句柄
wcex.hIcon = NULL; //设置窗口的图标
wcex.hCursor = LoadCursor(NULL, IDC_ARROW);//设置鼠标光标形状
wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);//设置窗口背景颜色
wcex.lpszMenuName = NULL; //设置窗口菜单，由于此例程不使用菜单所以设置为NULL
wcex.lpszClassName = szWindowClass; //定义窗口类的名称
wcex.hIconSm = NULL;

return RegisterClassEx(&wcex);
}

//
// 函数: InitInstance(HANDLE, int)
//
// 目的: 保存实例句柄并创建主窗口
//
// 注释:
//
// 在此函数中，我们在全局变量中保存实例句柄并
// 创建和显示主程序窗口。
//
// 在这个函数里，将按照前面所定义的窗口类别来建立并显示实际的程序窗口
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
HWND hWnd;
hInst = hInstance; // 将实例句柄存储在全局变量中

hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);
//以上是设置窗口类的名称
//窗口的标题
//WS_OVERLAPPEDWINDOW, 窗口的风格
//CW_USEDEFAULT, 窗口的坐标X
//CW_USEDEFAULT,窗口的坐标y
//CW_USEDEFAULT, 窗口的宽度
//CW_USEDEFAULT,窗口的高度
//NULL, 父窗口句柄
//NULL, 窗口的菜单句柄
//hInstance, 窗口的句柄
//NULL 参数指针

if (!hWnd)
{
return FALSE;
}
//下面是创建完成窗口后Windows并没有将其显示到显示器上
//只是在内存中保存了这个窗口的全部信息，要显示这个窗口
//需要使用 ShowWindow(hwnd,iCmdShow) 函数
//这个函数有两个参数 第一个参数是用CreateWindow()函数创建窗口的时候返回的窗口句柄
//第二个参数是WinMain()函数的第三个参数
//为了保证窗口能够正常的显示到显示器上我们还要调用UpdateWindow(hwnd) 函数

MoveWindow(hWnd,0,0,1024,768,true);// 设置窗口的位置以及大小
ShowWindow(hWnd, nCmdShow);
UpdateWindow(hWnd);

Render();

return TRUE;
}

//
// 函数: WndProc(HWND, unsigned, WORD, LONG)
//
// 目的: 处理主窗口的消息。
//
// WM_COMMAND - 处理应用程序菜单
// WM_PAINT - 绘制主窗口
// WM_DESTROY - 发送退出消息并返回
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
//下面其中以"WM"开头的标识符是消息参数
//在WINUSER.H文件中定义
//WM_CREATE是窗口过程收到的第一个消息
//当调用CreateWindow()函数来建立窗口的时候
//窗口过程函数收到这个消息第二个消息WM_PAINT是十分重要的消息
//他负责向窗体上画东西，我们要通过它来在窗口的中央显示"HELLO"字符串
//当第一次建立窗体和需要刷新窗体的时候Windows会发送WM_PAINT消息．

switch (message)
{
case WM_CREATE :
if( !d3dCreate( hWnd,1024,768,true ))
PostMessage(hWnd,WM_CLOSE,0,0);
a_Bk.Create( "2005.bmp" );
break;
case WM_PAINT: // 设置窗口的重绘消息
Render();
break;
case WM_DESTROY :
d3dRelease();
break;;
default: // 其他消息
return DefWindowProc(hWnd, message, wParam, lParam);
}
return 0;
}

void Render()
{
// d3dTexture bk ;

//睲?
d3dClear(D3DCOLOR_XRGB(255,255,255));
//秨﹍酶籹
d3dHdc hdc ;
d3d_Device->BeginScene();
a_Bk.BltFast( 0 , 0,1024,768 );
hdc.Release();
d3d_Device->EndScene();
//Θ?
d3d_Device->resent( NULL , NULL , NULL , NULL );

}

cgj888

还有我也碰到

http://forum.exceedu.com/forum/dispbbs.asp?boardID=46&ID=5680&page=3

这个问题可我按照这个解决办法后

那图片的尺寸变窄了

D3DXCreateTextureFromFileEx( d3d_Device ,
file , D3DX_DEFAULT , D3DX_DEFAULT ,
0 , 0 , D3DFMT_UNKNOWN , D3DPOOL_MANAGED ,
D3DX_FILTER_NONE ,
D3DX_FILTER_NONE , 0 , &in , NULL , &m_Texture );

我是这样写的

如果不用D3DX_FILTER_NONE图片就是有点糊涂

cgj888

[em02][em02][em02][em02]没人回答了