Back to...

   1  --  Standalone LZ77 compression (encoding) package.
   2  ---------------------------------------------------
   3  --  This is a collection of various free LZ77 match finders and encoders.
   4  --  The differences reside in the way matches are found, or skipped.
   5  --  See body (lz77.adb) for details and credits.
   6  --
   7  --  Pure Ada 95+ code, 100% portable: OS-, CPU- and compiler- independent.
   8  
   9  --  Legal licensing note:
  10  
  11  --  Copyright (c) 2016 .. 2020 Gautier de Montmollin (maintainer of the Ada version)
  12  --  SWITZERLAND
  13  
  14  --  Permission is hereby granted, free of charge, to any person obtaining a copy
  15  --  of this software and associated documentation files (the "Software"), to deal
  16  --  in the Software without restriction, including without limitation the rights
  17  --  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  18  --  copies of the Software, and to permit persons to whom the Software is
  19  --  furnished to do so, subject to the following conditions:
  20  
  21  --  The above copyright notice and this permission notice shall be included in
  22  --  all copies or substantial portions of the Software.
  23  
  24  --  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  25  --  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  26  --  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  27  --  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  28  --  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  29  --  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  30  --  THE SOFTWARE.
  31  
  32  --  NB: this is the MIT License, as found 21-Aug-2016 on the site
  33  --  http://www.opensource.org/licenses/mit-license.php
  34  
  35  with Interfaces;
  36  
  37  package LZ77 is
  38  
  39    type Method_Type is (
  40      --  Use the LZHuf algorithm (see body for details and credits)
  41      LZHuf,
  42      --  Use the Info-Zip algorithm, levels 4-10 (see body for details and credits)
  43      IZ_4,
  44      IZ_5,
  45      IZ_6,
  46      IZ_7,
  47      IZ_8,
  48      IZ_9,
  49      IZ_10,
  50      --  Use LZMA SDK's BT4 algorithm (see body for details and credits)
  51      BT4,
  52      --  A nice simple LZ77 compressor by Rich Geldreich, Jr.
  53      Rich,
  54      --  Just send literals (plain bytes), no LZ77 compression at all.
  55      --  It is better with LZMA on some rare image formats for instance.
  56      No_LZ77,
  57      --  Read LZ77 codes from a text files (for research purposes)
  58      Read_LZ77_Codes
  59    );
  60  
  61    subtype Byte is Interfaces.Unsigned_8;
  62  
  63    subtype Distance_Type is Positive;  --  TBD: use Positive_M32
  64  
  65    type Distance_Length_Pair is record
  66      distance : Distance_Type;
  67      length   : Positive;
  68    end record;
  69  
  70    type DLP_Array is array (Positive range <>) of Distance_Length_Pair;
  71  
  72    Max_Length_any_Algo : constant := 2**9;  --  Practically it is 273 with LZMA.
  73  
  74    type Matches_Type is record
  75      count : Integer := 0;
  76      dl    : DLP_Array (1 .. Max_Length_any_Algo);
  77    end record;
  78  
  79    function Are_Matches_Sorted (m : Matches_Type) return Boolean;
  80  
  81    type Byte_Array is array (Natural range <>) of Byte;
  82  
  83    BT4_max_prefetch_positions : constant := 64;
  84  
  85    subtype Prefetch_Index_Type is Natural range 0 .. BT4_max_prefetch_positions;
  86  
  87    type Matches_Array is array (Prefetch_Index_Type range <>) of Matches_Type;
  88  
  89    generic
  90      ----- LZSS Parameters -----
  91      String_buffer_size : Integer := 2**12;  --  Default values.
  92      Look_Ahead         : Integer := 65;     --  Default values.
  93      Threshold          : Integer := 2;      --  Default values.
  94      --
  95      Method : Method_Type;
  96      --
  97      --  Input of data:
  98      with function  Read_Byte return Byte;
  99      with function  More_Bytes return Boolean;
 100      --  Output of LZ-compressed data:
 101      with procedure Write_Literal (b : Byte);
 102      with procedure Write_DL_Code (distance : Distance_Type; length : Integer);
 103      --
 104      LZMA_friendly : Boolean := True;  --  Up to 4 recent distances may be preferred
 105      --
 106      --  Scoring of potential DL code emission by the entropy encoder.
 107      --  This helps choosing between various matches at a given point.
 108      --  This function is only used by BT4.
 109      with procedure Estimate_DL_Codes (
 110        matches          : in out Matches_Array;
 111        old_match_index  : in     Natural;
 112        prefixes         : in     Byte_Array;
 113        best_score_index :    out Positive;
 114        best_score_set   :    out Prefetch_Index_Type;
 115        match_trace      :    out DLP_Array
 116      );
 117    procedure Encode;
 118  
 119  end LZ77;