Back to...

   1  --  Huffman.Encoding.Length_Limited_Coding
   2  ------------------------------------------
   3  --    This algorithm builds optimal Huffman codes for a given alphabet
   4  --    and occurrence counts (frequencies) of this alphabet. These occurrences
   5  --    are supposed to have been counted in a message to be sent in a
   6  --    compressed form using the Huffman codes. As output, only the bit lengths
   7  --    of the Huffman codes are given; the Huffman codes themselves are built
   8  --    with these bit lengths when the message actually needs to be sent.
   9  --
  10  --  Pure Ada 95+ code, 100% portable: OS-, CPU- and compiler- independent.
  11  
  12  --  Legal licensing note:
  13  
  14  --  Copyright (c) 2016 .. 2024 Gautier de Montmollin (maintainer of the Ada version)
  15  --  SWITZERLAND
  16  --
  17  --  The copyright holder is only the maintainer of the Ada version;
  18  --  authors of the C code and those of the algorithm are cited below.
  19  
  20  --  Permission is hereby granted, free of charge, to any person obtaining a copy
  21  --  of this software and associated documentation files (the "Software"), to deal
  22  --  in the Software without restriction, including without limitation the rights
  23  --  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  24  --  copies of the Software, and to permit persons to whom the Software is
  25  --  furnished to do so, subject to the following conditions:
  26  
  27  --  The above copyright notice and this permission notice shall be included in
  28  --  all copies or substantial portions of the Software.
  29  
  30  --  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  31  --  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  32  --  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  33  --  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  34  --  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  35  --  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  36  --  THE SOFTWARE.
  37  
  38  --  NB: this is the MIT License, as found 21-Aug-2016 on the site
  39  --  http://www.opensource.org/licenses/mit-license.php
  40  
  41  --  Author: lode.vandevenne [*] gmail [*] com (Lode Vandevenne)
  42  --  Author: jyrki.alakuijala [*] gmail [*] com (Jyrki Alakuijala)
  43  
  44  --  Bounded package merge algorithm, based on the paper
  45  --    "A Fast and Space-Economical Algorithm for Length-Limited Coding
  46  --    Jyrki Katajainen, Alistair Moffat, Andrew Turpin".
  47  
  48  --  Translated by G. de Montmollin to Ada from katajainen.c (Zopfli project), 7-Feb-2016
  49  --  Translation notes in procedure's body.
  50  
  51  generic
  52    type Alphabet is (<>);  --  Any discrete type
  53    --  Count_Type is an integer type large enough for counting
  54    --  and indexing. See body for actual bounds.
  55    type Count_Type is range <>;
  56    type Count_Array is array (Alphabet) of Count_Type;
  57    type Length_Array is array (Alphabet) of Natural;
  58    max_bits : Positive;  --  Length limit in Huffman codes
  59  
  60  procedure Huffman.Encoding.Length_Limited_Coding
  61    (frequencies : in     Count_Array;
  62     bit_lengths :    out Length_Array);