RLE (32-Bit)

Startseite < Informatik < Algorithmen < Sortieren Komprimieren < RLE < RLE (8-Bit) RLE (16-Bit) RLE (24-Bit) [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] RLE (32-Bit) RLE (alternierend) > Huffman Lempel-Ziv > Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >

RLE (32-Bit)

Implementierung Implementierung des 32-Bit-RLE

Folgende Implementierung unter Delphi 5 ist weitgehend analog zur RLE-8Bit-Implementierung (siehe RLE (8-Bit) ), deshalb habe ich auch weitgehend die Kommentare weggelassen.

Wenn von Analogie die Rede ist, muss man auch hervorheben, wo genau der Unterschied vorhanden ist. Der wesentliche Unterschied liegt darin, dass gleiche Vorkommen von 32Bit-Zeichen komprimiert werden, gleiche Vorkommen von 8Bit-Zeichen werden dagegen nicht komprimiert. Statt den Methoden Try8BitCompress und Decode8 werden hier die Methoden Try32BitCompress und Decode32 verwendet, sonst bleibt alles beim Alten.

Es ist mir durchaus bewusst, dass die folgende Implementierung nicht sehr effizient ist. Mir kommt es hier mehr auf die Semantik bzw. Lesbarkeit an, auch wenn die Effizienz darunter leiden sollte.

Kompression und Dekompression: 32-Bit-RLE


unit URle32Bit;



interface



uses

  Classes;



procedure RLE32Compress(Source, Destination: TMemoryStream);

procedure RLE32Decompress(Source, Destination: TMemoryStream);



implementation



type

  T8Bit = Byte;

  T32Bit = Longint;



const

  CodeFlag: T8Bit = $FF; // binär: 1111 1111

  NoCode: T8Bit = $00;   // binär: 0000 0000 aus T8Bit\[1..MaxCount]

  MaxCount: T8Bit = $FE; // binär: 1111 1110









procedure RLE32Compress(Source, Destination: TMemoryStream);



  function Try32BitCompress: Boolean;

  var

    Counting: Boolean;

    Count: T8Bit;

    Try32Bit: packed array[0..1] of T32Bit; // zwei 32Bit-Zeichen

    Next32Bit: T32Bit;

  begin

    Result := FALSE;

    // Existenz von zwei 32Bit-Zeichen

    if (Source.Size - Source.Position < SizeOf(Try32Bit)) then Exit;

    // Vergleich der zwei 32Bit-Zeichen

    Source.ReadBuffer(Try32Bit, SizeOf(Try32Bit));

    Source.Position := Source.Position - SizeOf(Try32Bit);

    if (Try32Bit[0] <> Try32Bit[1]) then Exit;

    // Neuer Rückgabewert: Komprimierversuch gelingt!

    Result := TRUE;

    Source.Position := Source.Position + SizeOf(Try32Bit);

    Count := High(Try32Bit) - Low(Try32Bit) + 1; // Länge der Prüfsequenz



    if (Source.Size - Source.Position >= SizeOf(Next32Bit)) then

      repeat

        Source.ReadBuffer(Next32Bit, SizeOf(Next32Bit));

        Counting := (Try32Bit[0] = Next32Bit);

        if Counting then Inc(Count, 1)

        else Source.Position := Source.Position - SizeOf(T32Bit);

      until (not Counting) or (Count >= MaxCount) or

            (Source.Size - Source.Position < SizeOf(T32Bit));



    Destination.WriteBuffer(CodeFlag, SizeOf(CodeFlag));

    Destination.WriteBuffer(Count, SizeOf(Count));

    Destination.WriteBuffer(Try32Bit[0], SizeOf(Try32Bit[0]));

  end;



  procedure NoCompress;

  var

    Next: T8Bit;

  begin

    if (Source.Size - Source.Position < SizeOf(T8Bit)) then Exit;

    Source.ReadBuffer(Next, SizeOf(Next));

    Destination.WriteBuffer(Next, SizeOf(Next));

    if (Next = CodeFlag) then Destination.WriteBuffer(NoCode, SizeOf(NoCode));

  end;



begin

 Source.Position := 0;

 Destination.Clear;



 while (Source.Size - Source.Position >= SizeOf(T8Bit)) do

   if not Try32BitCompress then NoCompress;



 Source.Position := 0;

 Destination.Position := 0;

end;









procedure RLE32Decompress(Source, Destination: TMemoryStream);

var

  CodeCount: T8Bit;

  Next: T8Bit;



  procedure Decode32(Count: T8Bit);

  var

    i: T8Bit;

    MultiNext: T32Bit;

  begin

    Source.ReadBuffer(MultiNext, SizeOf(MultiNext));

    for i := Count downto 1 do

      Destination.WriteBuffer(MultiNext, SizeOf(MultiNext));

  end;



begin

  Source.Position := 0;

  Destination.Clear;



  while (Source.Size - Source.Position >= SizeOf(T8Bit)) do

  begin

    Source.ReadBuffer(Next, SizeOf(Next));

    if (Next = CodeFlag) then

    begin

      Source.ReadBuffer(CodeCount, SizeOf(CodeCount));

      if (CodeCount = NoCode) then Destination.WriteBuffer(Next, SizeOf(Next))

      else Decode32(CodeCount);

    end

    else Destination.WriteBuffer(Next, SizeOf(Next));

  end;



  Source.Position := 0;

  Destination.Position := 0;

end;



end.

⇑ Kompression und Dekompression: 32-Bit-RLE ⇑

Beispiele Beispiele zu 32-Bit-RLE

Text-Beispiel

Das folgende Beispiel ist eine Text-Datei.

Die Zeichenfolge '0D 0A' ist ein Zeilenumbruch.

Klartext (Text)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
00 16 32 48 64	48 61 61 61 61 61 61 61 61 61 61 61 61 6C 6C 6F 21 21 21 0D 0A 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 63 68 20 62 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6E 73 21 21 21 21	Haaaaaaaaaaaallo !!!··iiiiiiiiiii iiiiiiiiiiiiiiii ch biiiiiiiiiiii iiiiiiiiins!!!!

Komprimat (Text)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
00 16 32	48 FF 03 61 61 61 61 6C 6C 6F 21 21 21 0D 0A FF 06 69 69 69 69 69 69 69 63 68 20 62 FF 05 69 69 69 69 69 6E 73 21 21 21 21	H•·aaaallo!!!··• ·iiiiiiich b•·ii iiins!!!!

Bitmap-Beispiel

Das folgende Beispiel ist eine 16-Farben-Bitmap-Datei, die ein graues X auf schwarzem Hintergrund repräsentiert.

Klartext (Bitmap)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528 544 560 576 592 608 624	42 4D 76 02 00 00 00 00 00 00 76 00 00 00 28 00 00 00 20 00 00 00 20 00 00 00 01 00 04 00 00 00 00 00 00 02 00 00 CE 0E 00 00 CE 0E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80 00 00 80 00 00 00 80 80 00 80 00 00 00 80 00 80 00 80 80 00 00 C0 C0 C0 00 80 80 80 00 00 00 FF 00 00 FF 00 00 00 FF FF 00 FF 00 00 00 FF 00 FF 00 FF FF 00 00 FF FF FF 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00	BMv·······v···(· ·· ··· ········· ······•···•····· ············•··• ···••·•···•·•·•• ··•••·•••···•··• ···••·•···•·•·•• ··•••··········· ················ ········ww······ ··ww····ww······ ··ww···wwww····· ·wwww··wwww····· ·wwww··wwwww···· wwwww··wwwww···· wwwww···wwwww··w wwww····wwwww··w wwww·····wwwwwww www······wwwwwww www·······wwwwww ww········wwwwww ww·········wwwww w··········wwwww w··········wwwww w··········wwwww w·········wwwwww ww········wwwwww ww·······wwwwwww www······wwwwwww www·····wwwww··w wwww····wwwww··w wwww···wwwww···· wwwww··wwwww···· wwwww··wwww····· ·wwww··wwww····· ·wwww···ww······ ··ww····ww······ ··ww············ ················ ······

Komprimat (Bitmap)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528	42 4D 76 02 00 00 00 00 00 00 76 00 00 00 28 FF 02 00 00 00 20 00 00 00 01 00 04 00 00 00 00 00 00 02 FF 02 00 00 CE 0E FF 04 00 00 00 00 80 00 00 80 00 00 00 80 80 00 80 00 00 00 80 00 80 00 80 80 00 00 C0 C0 C0 00 80 80 80 00 00 00 FF 00 00 00 FF 00 00 00 00 FF 00 FF 00 00 FF 00 00 00 00 FF 00 00 FF 00 00 FF 00 FF 00 00 00 FF 00 FF 00 FF 00 FF 08 00 00 00 00 00 00 00 77 77 FF 02 00 00 00 00 77 77 00 00 00 00 77 77 FF 02 00 00 00 00 77 77 00 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 00 FF 02 77 77 77 77 77 77 00 00 00 00 00 00 FF 02 77 77 77 77 77 77 00 00 00 00 00 00 00 FF 02 77 77 77 77 FF 02 00 00 00 00 FF 02 77 77 77 77 FF 02 00 00 00 00 00 77 77 77 77 77 77 FF 02 00 00 00 00 00 00 77 77 77 77 77 77 FF 02 00 00 00 00 00 00 77 77 77 77 77 77 FF 02 00 00 00 00 00 00 77 77 77 77 77 77 FF 02 00 00 00 00 00 FF 02 77 77 77 77 FF 02 00 00 00 00 FF 02 77 77 77 77 00 00 00 00 00 00 00 FF 02 77 77 77 77 77 77 00 00 00 00 00 00 FF 02 77 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 00 77 77 FF 02 00 00 00 00 77 77 00 00 00 00 77 77 FF 02 00 00 00 00 77 77 FF 08 00 00 00 00 00 00	BMv·······v···(• ···· ··········· ··•···•·•·····•· ·•···••·•···•·•· ••··•••·•••···•· ··•····•·•··•··· ·•··•··•·•···•·• ·•·•········ww•· ····ww····ww•··· ··ww···wwww····· ·wwww··wwww····· ·wwww··wwwww···· wwwww··wwwww···· wwwww···wwwww··w wwww····wwwww··w wwww·····•·wwwww w······•·wwwwww· ······•·wwww•··· ··•·wwww•······w wwwww•·······www www•·······wwwww w•·······wwwwww• ······•·wwww•··· ··•·wwww·······• ·wwwwww······•·w wwwww·····wwwww· ·wwwww····wwwww· ·wwwww···wwwww·· ··wwwww··wwwww·· ··wwwww··wwww··· ···wwww··wwww··· ···wwww···ww•··· ··ww····ww•····· ww•·······

Unrealistisches Beispiel

Das folgende Beispiel ist eine Text-Datei mit 220 a's gefolgt von 2 Blanks gefolgt von 300 b's gefolgt von 2 Blanks gefolgt von 220 c's

Dieses Beispiel ist recht unrealistisch; derartige Dateien sind selten!

Klartext (unrealistisch)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528 544 560 576 592 608 624 640 656 672 688 704 720 736	61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 20 20 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 20 20 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63	aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaa bb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbb cccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccc

Komprimat (unrealistisch)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
00 16	FF 37 61 61 61 61 20 20 FF 4B 62 62 62 62 20 20 FF 37 63 63 63 63	•7aaaa •Kbbbb •7cccc

Startseite Sitemap Downloads Hilfe Impressum Pflichtenheft