关于 RLE 压缩方法是不是这样定义的???这是我网上搜到的。 ( 积分: 0 )

  • 主题发起人 主题发起人 QSmile
  • 开始时间 开始时间
Q

QSmile

Unregistered / Unconfirmed
GUEST, unregistred user!
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段则是一系列不相重复的字节。

-------------------
但这与网上很多说的,有点小差异,我认为这个是正确的,完整些的
关于那个 Header。最高位为 1 时表示重复字节,还是不重重字节呢?
 
unit RLELite;

interface

uses
Windows;

function RLELength(pInput:Pointer;dwCount:DWORD):DWORD;

function RLEEncode(pInput :Pointer;dwCount:DWORD;pOutput:Pointer):DWORD;
function RLEDecode(pInput:Pointer;pOutput:Pointer):DWORD;

implementation

// Global Variables
var
dwCodeLength :DWORD = 19;

// Return the Run Length Encoded Size
function RLELength(pInput:Pointer;dwCount:DWORD):DWORD;
label
_LoadByte, _CompareBytes, _Finished, _BuildCode, _CheckShift,_ShiftData,
_Continue, _Exit, _Done;
var
dwNewCount, dwMaxRun,dwUnusedByte :DWORD;
fOutput:Boolean;
begin
// Compressed Count
dwNewCount := 4;

// Max Run Length

// Variables Used for Code Shifting
dwUnusedByte := 0;
fOutput := FALSE;

asm
pushad;
// Calculate the Maximum Run Length
MOV EDX,1;
MOV ECX,dwCodeLength;
SUB ECX,9;
SHL EDX,CL;
SUB EDX,1;
MOV dwMaxRun,EDX;

// Load the Count of Bytes to Encode
MOV EDX,dwCount;

// Initialize the Output Bits
XOR EDI,EDI;

// Initialize the Storage DWORD
XOR ESI,ESI;

// Load the Byte to Compare
_LoadByte:

// Save the Storage DWORD
PUSH ESI;

// Load a Byte
MOV ESI,pInput;
MOV AL,[ESI];

// Initialize the Run Length Count to 1
MOV ECX,DWORD PTR 1;

// Compare the Bytes
_CompareBytes:

// Check for EOD
CMP EDX,0;
JZ _Finished;

// Compare to the Max Length for an Encode
CMP ECX,dwMaxRun;
JA _Finished;

// Compare the Bytes
CMP AL,[ESI + ECX];

// Increment the Run Length
LEA ECX,[ECX + 1];

// Decrement the Bytes Processed
LEA EDX,[EDX - 1];

// Branch for the Comparison
JE _CompareBytes;

// Finished Encoding
_Finished:

// Decrement the Run Length for Encoding
DEC ECX;

// Increment the Pointer to the Source Data
ADD ESI,ECX;
MOV pInput,ESI;

// Restore the Storage DWORD
POP ESI;

// Check for a 1:1 Character Copy
CMP ECX,1;
JNZ _BuildCode;

// Move in the Character
XOR EBX,EBX;
MOV BH,1;
MOV BL,AL;

// Set the Code Length
MOV ECX,9;

// Jump to Checking the Bit Shifting
JMP _CheckShift;

// Build the Compression Code
_BuildCode:
MOV EBX,ECX;
SHL EBX,8;
MOV BL,AL;

// Set the Code Length
MOV ECX,dwCodeLength;

// See How Many Bits Can be Shifted to the Output DWORD
_CheckShift:
ADD EDI,ECX;
CMP EDI,32;
JLE _ShiftData;

// See How Many Bits of the Last Code Can't Be Used
SUB EDI,32;

// Adjust ECX to Handle only the Bits that Can Be Used
SUB ECX,EDI;

// Save the Code
MOV dwUnusedByte,EBX;

// Shift the Input Symbol to the Right
PUSH ECX;
MOV ECX,EDI;
SHR EBX,CL;
POP ECX;

// Set the Output Flag
MOV fOutput,TRUE;

// Shift the Output Data
_ShiftData:

// Shift the Output Symbol to Handle a New Symbol
SHL ESI,CL;

// OR the Output Symbol with New Symbol
OR ESI,EBX;

// Check for Outputting a full DWORD
CMP fOutput,FALSE;
JE _Continue;

// Increment the Compression Count
ADD dwNewCount,4;

// Remove the Bits we Used
MOV EAX,32;
SUB EAX,EDI;
MOV ECX,EAX ;

// Restore the Unused Portion of the Code
MOV EAX,dwUnusedByte;
SHL EAX,CL;
SHR EAX,CL;

// Update the Code to Have the Left Over Bits
MOV ESI,EAX;

// Initialize the Left Over Bits
MOV dwUnusedByte,0;

// Reset the Output Flag
MOV fOutput,FALSE;

// Compare for More Data
_Continue:
CMP EDX,0;
JZ _Exit;

// Go Back for More Bytes
JMP _LoadByte;

// Finished Encoding
_Exit:

// Update Any Remaining Compression data in the Buffer
CMP EDI,0;
JE _Done;

// Left Shift the Remaining Bits
MOV EAX,32;
SUB EAX,EDI;
MOV ECX,EAX;
SHL ESI,CL;

// Increment the Compression Count
ADD dwNewCount,4;

// Done Encoding
_Done:
popad;
end;

// Return the Compressed Count
Result := dwNewCount;
end;

// Run Length Encode the Input Data to the Output Data
function RLEEncode(pInput :Pointer;dwCount:DWORD;pOutput:Pointer):DWORD;
label
_LoadByte, _CompareBytes ,_Finished, _BuildCode, _CheckShift, _ShiftData,
_Continue, _Exit, _Done;
var
dwNewCount :DWORD;
dwUnusedByte: DWORD;
fOutput: Boolean;
dwMaxRun:DWORD;
begin

// Compressed Count
dwNewCount := 4;

// Variables Used for Code Shifting
dwUnusedByte := 0;
fOutput := FALSE;

// Max Run Length


asm
// Calculate the Maximum Run Length
pushad;

MOV EDX,1
MOV ECX,dwCodeLength
SUB ECX,9
SHL EDX,CL
SUB EDX,1
MOV dwMaxRun,EDX

// Point to the Input Byte
MOV EDI,pOutput

// Load the Count of Bytes to Encode
MOV EDX,dwCount

// Store the Original Length in the Compressed Data
MOV [EDI],EDX

// Increment the Input Data Pointer
ADD EDI,4
MOV pOutput,EDI

// Initialize the Output Bits
XOR EDI,EDI

// Initialize the Storage DWORD
XOR ESI,ESI

// Load the Byte to Compare
_LoadByte:

// Save the Storage DWORD
PUSH ESI

// Load a Byte
MOV ESI,pInput
MOV AL,[ESI]

// Initialize the Run Length Count to 1
MOV ECX,DWORD PTR 1

// Compare the Bytes
_CompareBytes:

// Check for EOD
CMP EDX,0
JZ _Finished

// Compare to the Max Length for an Encode
CMP ECX,dwMaxRun
JA _Finished

// Compare the Bytes
CMP AL,[ESI + ECX]

// Increment the Run Length
LEA ECX,[ECX + 1]

// Decrement the Bytes Processed
LEA EDX,[EDX - 1]

// Branch for the Comparison
JE _CompareBytes

// Finished Encoding
_Finished:

// Decrement the Run Length for Encoding
DEC ECX

// Increment the Pointer to the Source Data
ADD ESI,ECX
MOV pInput,ESI

// Restore the Storage DWORD
POP ESI

// Check for a 1:1 Character Copy
CMP ECX,1
JNZ _BuildCode

// Move in the Character
XOR EBX,EBX
MOV BH,1
MOV BL,AL

// Set the Code Length
MOV ECX,9

// Jump to Checking the Bit Shifting
JMP _CheckShift

// Build the Compression Code
_BuildCode:
MOV EBX,ECX
SHL EBX,8
MOV BL,AL

// Set the Code Length
MOV ECX,dwCodeLength

// See How Many Bits Can be Shifted to the Output DWORD
_CheckShift:
ADD EDI,ECX
CMP EDI,32
JLE _ShiftData

// See How Many Bits of the Last Code Can't Be Used
SUB EDI,32

// Adjust ECX to Handle only the Bits that Can Be Used
SUB ECX,EDI

// Save the Code
MOV dwUnusedByte,EBX

// Shift the Input Symbol to the Right
PUSH ECX
MOV ECX,EDI
SHR EBX,CL
POP ECX

// Set the Output Flag
MOV fOutput,TRUE

// Shift the Output Data
_ShiftData:

// Shift the Output Symbol to Handle a New Symbol
SHL ESI,CL

// OR the Output Symbol with New Symbol
OR ESI,EBX

// Check for Outputting a full DWORD
CMP fOutput,FALSE
JE _Continue

// Output an Encoded Symbol
MOV EAX,ESI
PUSH EDI
MOV EDI,pOutput
MOV [EDI],EAX
ADD EDI,4
MOV pOutput,EDI
POP EDI

// Increment the Compression Count
ADD dwNewCount,4

// Remove the Bits we Used
MOV EAX,32
SUB EAX,EDI
MOV ECX,EAX

// Restore the Unused Portion of the Code
MOV EAX,dwUnusedByte
SHL EAX,CL
SHR EAX,CL

// Update the Code to Have the Left Over Bits
MOV ESI,EAX

// Initialize the Left Over Bits
MOV dwUnusedByte,0

// Reset the Output Flag
MOV fOutput,FALSE

// Compare for More Data
_Continue:
CMP EDX,0
JZ _Exit

// Go Back for More Bytes
JMP _LoadByte

// Finished Encoding
_Exit:

// Update Any Remaining Compression data in the Buffer
CMP EDI,0
JE _Done

// Left Shift the Remaining Bits
MOV EAX,32
SUB EAX,EDI
MOV ECX,EAX
SHL ESI,CL

// Output the Final Encoded Symbol
MOV EAX,ESI
MOV EDI,pOutput
MOV [EDI],EAX

// Increment the Compression Count
ADD dwNewCount,4

// Done Encoding
_Done:
popad;
end;

// Return the Compressed Count
Result := dwNewCount;
end;

// Run Length Decode the Input Data to the Output Data
function RLEDecode(pInput:Pointer;pOutput:Pointer):DWORD;
label
_LoopInput, _LeftShift, _Output,_CheckBits, _Exit ;
var
dwCount:DWORD;
dwCompCount:DWORD;
dwCodeLength2:DWORD;
begin
// Compressed Count

asm
pushad;
// Get the CodeLength - 1 for Checking a 1:1 Compression
MOV EAX,dwCodeLength
DEC EAX
MOV dwCodeLength2,EAX

// Point to the Input Byte
MOV ESI,pInput

// Point to the Output Byte
MOV EDI,pOutput

// Load the Count of Bytes Encoded
LODSD

// Save the New Input Location
MOV pInput,ESI

// Save the Count of the UnCompressed Data
MOV dwCompCount,EAX

// Initialize the Count of Bytes Decoded
MOV dwCount,EAX

// Initialize Number of Bits for Current Symbol to Process
MOV ESI,dwCodeLength

// Initialize the Decode Storage
XOR EDX,EDX

// Main Loop for Reading Input
_LoopInput:

// Save the Number of Bits for the Current Symbol
PUSH ESI

// Point to the Input Data
MOV ESI,pInput

// Read an Encoded DWORD
LODSD

// Save the Pointer to the Input Data
MOV pInput,ESI

// Restore the Number of Bits for the Current Symbol
POP ESI

// Initialize Number of Bits to Process
MOV EBX,32

// Shift in an Encoded Symbol, 1 bit at a time
_LeftShift:

// Shift 1 Bit of the Input Code to the Output
SHLD EDX,EAX,1

// Shift the Input Code 1 Bit to the Left
SHL EAX,1

// Decrement the Number of Bits Processed
DEC ESI

// Check for a Fully Encoded Symbol
JZ _Output

// Compare the High Bit for RLE or Character Encode
CMP ESI,dwCodeLength2
JNZ _CheckBits

// Compare the High Bit, 0 = RLE, 1 = 1:1 Character Encode
CMP EDX,0
JZ _CheckBits

// Update the Bits Left to 8
MOV ESI,8

// Check for More Bits to Process
_CheckBits:

// Decrement the Number of Bits Processed in the Input DWORD
DEC EBX

// Continue Shifting More Bits
JNZ _LeftShift

// Read Another DWORD of Data
JMP _LoopInput

// Output the Run Length Amount of the Code
_Output:

// Get the Run Length
MOV ECX,EDX
SHR ECX,8

// Get the Code
AND EDX,255

// Save the Input DWORD
PUSH EAX

// Copy the Code
MOV EAX,EDX

// Save the Run Length
PUSH ECX

// Output the Run Length Amount of the Code
REP STOSB

// Restore the Run Length
POP ECX

// Restore the Input DWORD
POP EAX

// Check for More Data to Decode
SUB dwCompCount,ECX
JZ _Exit

// Initialize the Decode Storage
XOR EDX,EDX

// Initialize Number of Bits for Current Symbol to Process
MOV ESI,dwCodeLength

// Check for More Bits to Process
JMP _CheckBits

// Finished
_Exit:
popad;
end;

// Return the Count of Uncompressed Data
Result := dwCount;
end;

end.
 
送分沒人要?
 
送给我吧,这贴应该作为笔记~~
 
接受答案了.
 

Similar threads

S
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
1K
SUNSTONE的Delphi笔记
S
S
回复
0
查看
900
SUNSTONE的Delphi笔记
S
后退
顶部