Komprimer og dekomprimere enheten ved hjelp LZ77 algoritme for Borland (Turbo) Pascal versjon 7.0
bidragsyter: ANDREW EIGUS
Unit LZSSUnit; {LZSSUNIT - Komprimer og dekomprimere enheten ved hjelp LZ77 algoritme for Borland (Turbo) Pascal versjon 7.0
assembler Programmerer: Andy Tam, Pascal Konvertering: Douglas Webb, Unit Conversion og dynamisk minnetildeling: Andrew Eigus
Public Domain versjon.. 1,02, sist endret 30.11.94. Målplattformer:. DOS, DPMI, Windows
Skrevet av Andrew Eigus (aka: Mr. Byte) av: Fidonet: 2: 5100/33, Internett: [email protected], [email protected] .lv. }
Interface product: {# Z +} {Denne enheten er klar til bruk med Dj. Murdochs ScanHelp verktøyet som vil gjøre en Borland .TPH fil for det. } {# Z-}
konst LZRWBufSize = 8192; {Les buffer størrelse} product: {# Z +} N = 4096; {Bigger N - > Bedre komprimering på store filer. } F = 18; Terskel = 2; Nul = N * 2; InBufPtr: Ordet = LZRWBufSize; InBufSize: Ordet = LZRWBufSize; OutBufPtr: Ordet = 0; {# Z-}
typen {#X TWriteProc} {# X LZSquash} {# X LZUnsquash}
TReadProc = funksjon (var ReadBuf; Var NumRead: ord): ord; {Dette er erklæring for tilpasset lesefunksjon. Den bør leses # LZRWBufSize # bytes fra ReadBuf. Returverdien blir ignorert. } Product: {#X TReadProc} {# X LZSquash} {# X LZUnsquash} TWriteProc = funksjon (var WriteBuf, Count: ord; Var NumWritten: ord): ord; {Dette er erklæring for tilpasset skrivefunksjon. Det bør skrive Count bytes inn WriteBuf og returnere antall faktiske bytes skrevet inn NumWritten variabel. Returverdien blir ignorert. } Product: {# Z +} PLZRWBuffer = ^ TLZRWBuffer; TLZRWBuffer = array [0..LZRWBufSize - 1] av Byte; {file buffere}
PLZTextBuf = ^ TLZTextBuf; TLZTextBuf = array [0..n + F - 2] av Byte;
PLeftMomTree = ^ TLeftMomTree; TLeftMomTree = array [0..n] av Word; PRightTree = ^ TRightTree; TRightTree = array [0..n + 256] av Word,
konst LZSSMemRequired = sizeof (TLZRWBuffer) * 2 + sizeof (TLZTextBuf) + sizeof (TLeftMomTree) * 2 + sizeof (TRightTree); {# Z-}
funksjon LZInit: boolean; {Denne funksjonen bør kalles før noen andre kompresjonsrutiner fra denne enheten - det tildeler minne og initialiserer alle interne variabler som kreves av kompresjonsrutiner. Dersom tildeling mislykkes, returnerer LZInit False, betyr dette at det ikke er nok minne for kompresjon eller dekompresjon prosessen. Den returnerer True hvis initialisering var vellykket. } {#X LZDone} {# X LZSquash} {# X LZUnsquash}
prosedyre LZSquash (ReadProc: TReadProc; WriteProc: TWriteProc); {Denne fremgangsmåten blir brukt for komprimering. ReadProc spesifiserer tilpasset lesefunksjon som leser data, og WriteProc angir tilpasset skrivefunksjon som skriver komprimerte data. } {#X LZUnsquash} {# X LZInit} {# X LZDone}
prosedyre LZUnSquash (ReadProc: TReadProc; WriteProc: TWriteProc); {Denne fremgangsmåten brukes for dekompresjon. ReadProc spesifiserer tilpasset lesefunksjon som leser komprimerte data, og WriteProc angir tilpasset skrivefunksjon som skriver dekomprimeres data. } {#X LZSquash} {# X LZInit} {# X LZDone}
prosedyre LZDone; {Denne prosedyren bør kalles etter at du har fullført kompresjon eller dekompresjon. Det deallokerer (frigjør) alt minne er tildelt av LZInit. Merk: Du bør alltid ringe LZDone etter at du ferdig med å bruke kompresjonsrutiner fra denne enheten. } {#X LZInit} {# X LZSquash} {# X LZUnsquash}
implementering
Var Høyde, MatchPos, MatchLen, LastLen: ord; TextBufP: PLZTextBuf; LeftP, MomP: PLeftMomTree; RightP: PRightTree; CodeBuf: array [0..16] av Byte; LZReadProc: TReadProc; LZWriteProc: TWriteProc; InBufP, OutBufP: PLZRWBuffer; Bytes: ord; Initialisert: boolean;
Funksjon LZSS_Read: ord; {Returnerer # bytes som leses} Begynn LZReadProc (InBufP ^, Bytes); LZSS_Read: = Bytes; Slutt; {LZSS_Read}
Funksjon LZSS_Write: ord; {Returns # bytes skrevet} Begynn LZWriteProc (OutBufP ^, OutBufPtr, Bytes); LZSS_Write: = Bytes End; {LZSS_Write}
Prosedyre getc; assembler; Asm {getc: returnere en karakter fra buffer RETURN: AL = input røye Carry satt når EOF} presse bx mov bx, inBufPtr cmp bx, inBufSize jb @ getc1 trykk cx trykk dx presse di presse si samtale LZSS_Read pop si pop di pop dx pop cx mov inBufSize, øks eller øks, øks JZ @ getc2 {; EOF} xor bx, bx @ getc1: PUSH DI LES DI, [InBufP] MOV AL, BYTE PTR [ES: DI + BX] POP ​​DI økes bx mov inBufPtr, bx pop bx clc {; tømme bære flagget} JMPend @ getc2: pop bx stc {; sett bære å indikere EOF}end: End; {Getc}
Prosedyre Putc; assembler; {Putc: sette en karakter i utgangsbufferen Entry: AL = utgang røye} Asm presse bx mov bx, outBufPtr PUSH DI LES DI, [OutBufP] MOV BYTE PTR [ES: DI + BX], AL POP DI inc bx cmp bx , LZRWBufSize jb @ putc1 mov OutBufPtr, LZRWBufSize {Bare så flush vil fungere. } Presse cx trykk dx presse di presse si samtale LZSS_Write pop si pop di pop dx pop cx XOR bx, bx @ putc1: mov outBufPtr, bx pop bx End; {Putc}
Prosedyre InitTree; assembler; {InitTree: stille alle binære søketrær. Det er 256 BST-tallet, en for alle strenger startet med en spesiell karakter. Den av foreldrene er tre K er node N + K + 1, og det har bare en rett barnet} Asm cld push-ds pop es LES DI, [RightP] {mov di, utlignet rett} legge di, (N + 1) * 2 mov cx, 256 mov ax, NUL rep stosw LES dI, [MomP] {mov di, offset mamma} mov cx, N rep stosw End; {InitTree}
Prosedyre spriker; assembler; {Spriker: bruk spriker tre operasjoner for å flytte noden til "toppen" av treet. Legg merke til at det ikke vil faktisk bli roten av treet på grunn roten av hvert tre er en spesiell node. I stedet vil det bli riktig barn av denne spesielle noden
ENTRY. Di = noden som skal roteres} Asm @ Splay1: PUSH BX LES BX, [MomP] MOV SI, [ES: BX + DI] POP ​​BX {mov si, [Offset mamma + di]} cmp si, NUL {; exit hvis foreldrene er en spesiell node} ja @ Splay4 PUSH DI LES DI, [MomP] ADD DI, SI MOV BX, [ES: DI] {mov bx, [Offset mamma + si]} POP DI cmp bx, NUL {; sjekke om sin besteforelder er spesiell} JBE @ Splay5 {; hvis ikke så hopp} PUSH BX LES BX, [LeftP] CMP DI, [ES: BX + SI] POP ​​BX {cmp di, [Offset Venstre + si]} {; er den aktuelle noden er en venstre barn? } JNE @ Splay2 PUSH BX LES BX, [RightP] MOV DX, [ES: BX + DI] {mov dx, [Offset Høyre + di]} {; utføre en venstre sikk operasjon} LES BX, [LeftP] MOV [ES: BX + SI], DX {mov [Offset Venstre + si], dx} LES BX, [RightP] MOV [ES: BX + DI], SI POP BX {mov [Offset Høyre + di], si} JMP @ Splay3 @ Splay2: PUSH BX LES BX, [LeftP] MOV DX, [ES: BX + dI] {mov dx, [Offset Venstre + di]} {; utføre en riktig sikk} LES BX, [RightP] MOV [ES: BX + SI], DX {mov [Offset Høyre + si], dx} LES BX, [LeftP] MOV [ES: BX + DI], SI POP BX {mov [Offset Venstre + di], si} @ Splay3: PUSH SI LES SI, [RightP] MOV [ES: SI + BX], dI POP SI {mov [Offset Høyre + bx], di} xchg bx, dx PUSH AX MOV AX, BX LES BX, [MomP] ADD BX, AX MOV [ES: BX], SI LES BX, [MomP] MOV [ES: BX + SI], DI LES BX, [MomP] MOV [ES: BX + dI], DX MOV BX, AX POP AX {mov [Offset mamma + bx], si mov [Offset mamma + si], di mov [Offset mamma + di], dx} @ Splay4: JMPend @ Splay5: PUSH DI LES DI, [MomP] MOV CX, [ES: DI + BX] POP ​​DI {mov cx, [Offset mamma + bx]} PUSH BX LES BX, [LeftP] CMP DI, [ES: BX + SI] POP ​​BX {CMP di, [Offset Venstre + si]} JNE @ Splay7 PUSH dI LES dI, [LeftP] CMP SI, [ES: dI + BX] POP ​​dI {cmp si, [Offset Venstre + bx]} JNE @ Splay6 PUSH AX MOV AX, DI LES DI, [RightP] ADD DI, SI MOV DX, [ES: DI] {mov dx, [Offset Høyre + si]} {; utføre venstre sikk-sikk drift} LES DI, [LeftP] MOV [ES: DI + BX], DX {mov [Offset Venstre + bx] dx} xchg bx, dx LES DI, [MomP] MOV [ES: DI + BX], DX {mov [Offset mamma + bx] dx} LES dI, [RightP] ADD dI, AX MOV BX, [ES: dI] {mov bx, [Offset Høyre + di]} LES dI, [LeftP ] ADD DI, SI MOV [ES: DI], BX LES DI, [MomP] MOV [ES: DI + BX], SI {mov [Offset Venstre + si], bx mov [Offset mamma + bx], si} mov bx, dx LES DI, [RightP] ADD DI, SI MOV [ES: DI], BX LES DI, [RightP] ADD DI, AX MOV [ES: DI], SI {mov [Offset Høyre + si], bx mov [Offset Høyre + di], si} LES dI, [MomP] MOV [ES: dI + BX], SI LES dI, [MomP] ADD dI, SI STOSW MOV dI, AX POP AX {mov [Offset mamma + bx] , si mov [Offset mamma + si], di} JMP @ Splay9 @ Splay6: PUSH AX MOV AX, SI LES SI, [LeftP] ADD SI, dI MOV DX, [ES: SI] {mov dx, [Offset Venstre + di]} {; utføre venstre sikk-sakk drift} LES SI, [RightP] MOV [ES: SI + BX], DX {mov [Offset Høyre + bx] dx} xchg bx, dx LES SI, [MomP] MOV [ES: SI + BX], DX {mov [Offset mamma + bx] dx} LES SI, [RightP] ADD SI, dI MOV BX, [ES: SI] {mov bx, [Offset Høyre + di]} LES SI, [LeftP ] ADD SI, AX MOV [ES: SI], BX {mov [Offset Venstre + si], bx} LES SI, [MomP] MOV [ES: SI + BX], AX {mov [Offset mamma + bx], si } mov bx, dx LES SI, [LeftP] ADD SI, dI MOV [ES: SI], BX {mov [Offset Venstre + di], bx} LES SI, [RightP] ADD SI, dI MOV [ES: SI] , AX {mov [Offset Høyre + di], si} LES SI, [MomP] ADD SI, AX MOV [ES: SI], dI {mov [Offset mamma + si], di} LES SI, [MomP] MOV [ ,,,0],ES: SI + BX], dI MOV SI, AX POP AX {mov [Offset mamma + bx], di} JMP @ Splay9 @ Splay7: PUSH dI LES dI, [RightP] CMP SI, [ES: dI + BX] POP DI {CMP si, [Offset Høyre + bx]} JNE @ Splay8 PUSH AX MOV AX, SI LES SI, [LeftP] ADD SI, AX MOV DX, [ES: SI] {mov dx, [Offset Venstre + si]} {; utføre en riktig sikk-sikk} LES SI, [RightP] MOV [ES: SI + BX], DX {mov [Offset Høyre + bx] dx} xchg bx, dx LES SI, [MomP] MOV [ES: SI + BX], DX {mov [Offset mamma + bx] dx} LES SI, [LeftP] ADD SI, dI MOV BX, [ES: SI] {mov bx, [Offset Venstre + di]} LES SI, [RightP] ADD SI, AX MOV [ES: SI], BX {mov [Offset Høyre + si], bx} LES SI, [MomP] MOV [ES: SI + BX], AX {mov [Offset mamma + bx], si} mov bx, dx LES SI, [LeftP] ADD SI, AX MOV [ES: SI], BX {mov [Offset Venstre + si], bx} LES SI, [LeftP] ADD SI, DI MOV [ES: SI] AX {mov [Offset Venstre + di], si} LES SI, [MomP] MOV [ES: SI + BX], AX {mov [Offset mamma + bx], si} LES SI, [MomP] ADD SI, AX MOV [ES: SI], dI {mov [Offset mamma + si], di} MOV SI, AX POP AX JMP @ Splay9 @ Splay8: PUSH AX MOV AX, SI LES SI, [RightP] ADD SI, dI MOV DX, [ ,,,0],ES: SI] {mov dx, [Offset Høyre + di]} {; utføre en riktig sikk-sakk} LES SI, [LeftP] MOV [ES: SI + BX], DX {mov [Offset Venstre + bx] dx} xchg bx, dx LES SI, [MomP] MOV [ES: SI + BX], DX {mov [Offset mamma + bx] dx} LES SI, [LeftP] ADD SI, dI MOV BX, [ES: SI] {mov bx, [Offset Venstre + di]} LES SI, [RightP] ADD SI, AX MOV [ES: SI], BX {mov [Offset Høyre + si], bx} LES SI, [MomP] MOV [ES: SI + BX], AX {mov [Offset mamma + bx], si} mov bx, dx LES SI, [RightP] ADD SI, dI MOV [ES: SI], BX {mov [Offset Høyre + di], bx} LES SI, [LeftP] ADD SI, dI MOV [ES: SI] AX {mov [Offset Venstre + di], si} LES SI, [MomP] ADD SI, AX MOV [ES: SI], dI LES SI, [MomP] MOV [ES: SI + BX], dI {mov [Offset mamma + si], di mov [Offset mamma + bx], di} MOV SI, AX POP AX @ Splay9: mov si, CX cmp si, NUL ja @ Splay10 PUSH dI LES dI, [LeftP] ADD dI, SI CMP BX [ES: DI] POP ​​DI {cmp bx, [Offset Venstre + si]} JNE @ Splay10 PUSH BX LES BX, [LeftP] MOV [ES: BX + SI], DI POP BX {mov [Offset Venstre + si] , di} JMP @ Splay11 @ Splay10: PUSH BX LES BX, [RightP] MOV [ES: BX + SI], dI POP BX {mov [Offset Høyre + si], di} @ Splay11: PUSH BX LES BX, [MomP ] MOV [ES: BX + dI], SI POP BX {mov [Offset mamma + di], si} JMP @ Splay1end: End; {Spriker}
Prosedyre InsertNode; assembler; {InsertNode: Sett den nye noden til tilsvarende tre. Legg merke til at plasseringen av en streng i buffer også tjente som nodenummer. ENTRY: di = posisjon i buffer} Asm presse si trykk dx trykk cx trykk bx mov dx, en xor øks, øks mov matchLen, øks mov høyde, øks LES SI, [TextBufP] ADD SI, DI MOV AL, BYTE PTR [ ,,,0],ES: SI] {mov al, byte ptr [Offset TextBuf + di]} SHL di, en add øks, N + 1 SHL øks, en mov si, øks mov ax, NUL PUSH BX LES BX, [RightP] MOV WORD PTR [ES: BX + dI], AX {mov ordet ptr [Offset Høyre + di], øks} LES BX, [LeftP] MOV WORD PTR [ES: BX + dI], AX POP BX {mov ordet ptr [Offset Venstre + di], øks} @ Ins1: inc høyde CMP dx, 0 jl @ Ins3 PUSH dI LES dI, [RightP] ADD dI, SI MOV AX, WORD PTR [ES: dI] POP ​​dI {mov ax, ordet ptr [Offset Høyre + si]} cmp øks, NUL je @ Ins2 mov si, øks JMP @ Ins5 @ Ins2: PUSH BX LES BX, [RightP] MOV WORD PTR [ES: BX + SI], DI {mov ordet ptr [Offset Høyre + si ], di} LES BX, [MomP] MOV WORD PTR [ES: BX + dI], SI POP BX {mov ordet ptr [Offset mamma + di], si} JMP @ Ins11 @ Ins3: PUSH BX LES BX, [LeftP ] ADD BX, SI MOV AX, WORD PTR [ES: BX] POP ​​BX {mov ax, ordet ptr [Offset Venstre + si]} cmp øks, NUL je @ Ins4 mov si, øks JMP @ Ins5 @ Ins4: PUSH BX LES BX, [LeftP] ADD BX, SI MOV WORD PTR [ES: BX], dI {mov ordet ptr [Offset Venstre + si], di} LES BX, [MomP] ADD BX, dI MOV WORD PTR [ES: BX] , SI POP BX {mov ordet ptr [Offset mamma + di], si} JMP @ Ins11 @ Ins5: mov bx, en SHR si, en SHR di, en xor lm, lm xor dh, dh @ Ins6: PUSH SI LES SI [TextBufP] ADD SI, DI MOV DL, BYTE PTR [ES: SI + BX] POP ​​SI PUSH DI LES DI, [TextBufP] ADD DI, SI MOV CL, BYTE PTR [ES: DI + BX] POP ​​DI {mov dl, byte ptr [Offset Textbuf + di + bx] mov cl, byte ptr [Offset TextBuf + si + bx]} sub dx, CX JNZ @ Ins7 inc bx cmp bx, F jb @ Ins6 @ Ins7: SHL si, en SHL di, en cmp bx, matchLen JBE @ Ins1 mov ax, si SHR øks, 1 mov matchPos, øks mov matchLen, bx cmp bx, F jb @ Ins1 @ Ins8: PUSH CX LES BX, [MomP] MOV AX, WORD PTR [ ,,,0],ES: BX + SI] {mov ax, ordet ptr [Offset mamma + si]} LES BX, [MomP] MOV WORD PTR [ES: BX + dI], AX {mov ordet ptr [Offset mamma + di], øks} LES BX, [LeftP] MOV CX, WORD PTR [ES: BX + SI] {mov bx, ordet ptr [Offset Venstre + si]} LES BX, [LeftP] MOV WORD PTR [ES: BX + DI], CX { mov ordet ptr [Offset Venstre + di], bx} LES BX, [MomP] ADD BX, CX MOV WORD PTR [ES: BX], dI {mov ordet ptr [Offset mamma + bx], di} LES BX, [RightP ] MOV CX, WORD PTR [ES: BX + SI] {mov bx, ordet ptr [Offset Høyre + si]} LES BX, [RightP] MOV WORD PTR [ES: BX + DI], CX {mov ordet ptr [Offset høyre + di], bx} LES BX, [MomP] ADD BX, CX MOV WORD PTR [ES: BX], dI {mov ordet ptr [Offset mamma + bx], di} LES BX, [MomP] MOV CX, WORD PTR [ES: BX + SI] {mov bx, ordet ptr [Offset mamma + si]} MOV BX, CX POP CX PUSH DI LES DI, [RightP] CMP SI, WORD PTR [ES: DI + BX] POP ​​DI { CMP si, ordet ptr [Offset Høyre + bx]} JNE @ Ins9 PUSH SI LES SI, [RightP] MOV WORD PTR [ES: SI + BX], dI POP SI {mov ordet ptr [Offset Høyre + bx], di} JMP @ Ins10 @ Ins9: PUSH SI LES SI, [LeftP] MOV WORD PTR [ES: SI + BX], dI POP SI {mov ordet ptr [Offset Venstre + bx], di} @ Ins10: PUSH dI LES dI, [ ,,,0],MomP] ADD DI, SI MOV WORD PTR [ES: DI], NUL pOP DI {mov ordet ptr [Offset mamma + si], NUL} @ Ins11: CMP høyde, 30 jb @ Ins12 samtale spriker @ Ins12: pop bx pop cx pop dx pop si shr di, en End; {InsertNode}
Prosedyre DeleteNode; assembler; {DeleteNode: slette noden fra treet
ENTRY: SI = posisjon i buffer} Asm presse di presse bx SHL si, en PUSH DI LES DI, [MomP] ADD DI, SI CMP WORD PTR [ES: DI] , NUL POP DI {cmp ordet ptr [Offset mamma + si], NUL} {; hvis den ikke har noen foreldre da exit} je @ del7 PUSH DI LES DI, [RightP] ADD DI, SI CMP WORD PTR [ES: DI], NUL POP DI {cmp ordet ptr [Offset Høyre + si], NUL} {; har den rett barnet? } Je @ del8 PUSH BX LES BX, [LeftP] MOV DI, WORD PTR [ES: BX + SI] POP ​​BX {mov di, ordet ptr [Offset Venstre + si]} {; betyr det har forlatt barnet? } CMP di, NUL je @ del9 PUSH SI LES SI, [RightP] ADD SI, DI MOV AX, WORD PTR [ES: SI] POP ​​SI {mov ax, ordet ptr [Offset Høyre + di]} {; har den riktige barnebarn? } CMP øks, NUL je @ Del2 {;