GRUB2/MOD_SRC/grub-2.04/grub-core/ventoy/huffman.c

   1 /*
   2  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  */
  19
  20 /**
  21  * @file
  22  *
  23  * Huffman alphabets
  24  *
  25  */
  26
  27 #include "wimboot.h"
  28 #include "huffman.h"
  29
  30 /**
  31  * Transcribe binary value (for debugging)
  32  *
  33  * @v value             Value
  34  * @v bits              Length of value (in bits)
  35  * @ret string          Transcribed value
  36  */
  37 const char * huffman_bin ( unsigned long value, unsigned int bits ) {
  38         static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
  39         char *out = buf;
  40
  41         /* Sanity check */
  42         assert ( bits < sizeof ( buf ) );
  43
  44         /* Transcribe value */
  45         while ( bits-- )
  46                 *(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
  47         *out = '\0';
  48
  49         return buf;
  50 }
  51
  52 /**
  53  * Dump Huffman alphabet (for debugging)
  54  *
  55  * @v alphabet          Huffman alphabet
  56  */
  57 static void __attribute__ (( unused ))
  58 huffman_dump_alphabet ( struct huffman_alphabet *alphabet ) {
  59         struct huffman_symbols *sym;
  60         unsigned int bits;
  61         unsigned int huf;
  62         unsigned int i;
  63
  64     (void)huf;
  65
  66         /* Dump symbol table for each utilised length */
  67         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
  68                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
  69                 sym = &alphabet->huf[ bits - 1 ];
  70                 if ( sym->freq == 0 )
  71                         continue;
  72                 huf = ( sym->start >> sym->shift );
  73                 DBG ( "Huffman length %d start \"%s\" freq %d:", bits,
  74                       huffman_bin ( huf, sym->bits ), sym->freq );
  75                 for ( i = 0 ; i < sym->freq ; i++ ) {
  76                         DBG ( " %03x", sym->raw[ huf + i ] );
  77                 }
  78                 DBG ( "\n" );
  79         }
  80
  81         /* Dump quick lookup table */
  82         DBG ( "Huffman quick lookup:" );
  83         for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
  84                             sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
  85                 DBG ( " %d", ( alphabet->lookup[i] + 1 ) );
  86         }
  87         DBG ( "\n" );
  88 }
  89
  90 /**
  91  * Construct Huffman alphabet
  92  *
  93  * @v alphabet          Huffman alphabet
  94  * @v lengths           Symbol length table
  95  * @v count             Number of symbols
  96  * @ret rc              Return status code
  97  */
  98 int huffman_alphabet ( struct huffman_alphabet *alphabet,
  99                        uint8_t *lengths, unsigned int count ) {
 100         struct huffman_symbols *sym;
 101         unsigned int huf;
 102         unsigned int cum_freq;
 103         unsigned int bits;
 104         unsigned int raw;
 105         unsigned int adjustment;
 106         unsigned int prefix;
 107         int empty;
 108         int complete;
 109
 110         /* Clear symbol table */
 111         memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
 112
 113         /* Count number of symbols with each Huffman-coded length */
 114         empty = 1;
 115         for ( raw = 0 ; raw < count ; raw++ ) {
 116                 bits = lengths[raw];
 117                 if ( bits ) {
 118                         alphabet->huf[ bits - 1 ].freq++;
 119                         empty = 0;
 120                 }
 121         }
 122
 123         /* In the degenerate case of having no symbols (i.e. an unused
 124          * alphabet), generate a trivial alphabet with exactly two
 125          * single-bit codes.  This allows callers to avoid having to
 126          * check for this special case.
 127          */
 128         if ( empty )
 129                 alphabet->huf[0].freq = 2;
 130
 131         /* Populate Huffman-coded symbol table */
 132         huf = 0;
 133         cum_freq = 0;
 134         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 135                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 136                 sym = &alphabet->huf[ bits - 1 ];
 137                 sym->bits = bits;
 138                 sym->shift = ( HUFFMAN_BITS - bits );
 139                 sym->start = ( huf << sym->shift );
 140                 sym->raw = &alphabet->raw[cum_freq];
 141                 huf += sym->freq;
 142                 if ( huf > ( 1U << bits ) ) {
 143                         DBG ( "Huffman alphabet has too many symbols with "
 144                               "lengths <=%d\n", bits );
 145                         return -1;
 146                 }
 147                 huf <<= 1;
 148                 cum_freq += sym->freq;
 149         }
 150         complete = ( huf == ( 1U << bits ) );
 151
 152         /* Populate raw symbol table */
 153         for ( raw = 0 ; raw < count ; raw++ ) {
 154                 bits = lengths[raw];
 155                 if ( bits ) {
 156                         sym = &alphabet->huf[ bits - 1 ];
 157                         *(sym->raw++) = raw;
 158                 }
 159         }
 160
 161         /* Adjust Huffman-coded symbol table raw pointers and populate
 162          * quick lookup table.
 163          */
 164         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 165                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 166                 sym = &alphabet->huf[ bits - 1 ];
 167
 168                 /* Adjust raw pointer */
 169                 sym->raw -= sym->freq; /* Reset to first symbol */
 170                 adjustment = ( sym->start >> sym->shift );
 171                 sym->raw -= adjustment; /* Adjust for quick indexing */
 172
 173                 /* Populate quick lookup table */
 174                 for ( prefix = ( sym->start >> HUFFMAN_QL_SHIFT ) ;
 175                       prefix < ( 1 << HUFFMAN_QL_BITS ) ; prefix++ ) {
 176                         alphabet->lookup[prefix] = ( bits - 1 );
 177                 }
 178         }
 179
 180         /* Check that there are no invalid codes */
 181         if ( ! complete ) {
 182                 DBG ( "Huffman alphabet is incomplete\n" );
 183                 return -1;
 184         }
 185
 186         return 0;
 187 }
 188
 189 /**
 190  * Get Huffman symbol set
 191  *
 192  * @v alphabet          Huffman alphabet
 193  * @v huf               Raw input value (normalised to HUFFMAN_BITS bits)
 194  * @ret sym             Huffman symbol set
 195  */
 196 struct huffman_symbols * huffman_sym ( struct huffman_alphabet *alphabet,
 197                                        unsigned int huf ) {
 198         struct huffman_symbols *sym;
 199         unsigned int lookup_index;
 200
 201         /* Find symbol set for this length */
 202         lookup_index = ( huf >> HUFFMAN_QL_SHIFT );
 203         sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
 204         while ( huf < sym->start )
 205                 sym--;
 206         return sym;
 207 }