wimboot/wimboot-2.7.3/src/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 <stdint.h>
  28 #include <string.h>
  29 #include <stdio.h>
  30 #include <assert.h>
  31 #include "wimboot.h"
  32 #include "huffman.h"
  33
  34 /**
  35  * Transcribe binary value (for debugging)
  36  *
  37  * @v value             Value
  38  * @v bits              Length of value (in bits)
  39  * @ret string          Transcribed value
  40  */
  41 static const char * huffman_bin ( unsigned long value, unsigned int bits ) {
  42         static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
  43         char *out = buf;
  44
  45         /* Sanity check */
  46         assert ( bits < sizeof ( buf ) );
  47
  48         /* Transcribe value */
  49         while ( bits-- )
  50                 *(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
  51         *out = '\0';
  52
  53         return buf;
  54 }
  55
  56 /**
  57  * Dump Huffman alphabet (for debugging)
  58  *
  59  * @v alphabet          Huffman alphabet
  60  */
  61 static void __attribute__ (( unused ))
  62 huffman_dump_alphabet ( struct huffman_alphabet *alphabet ) {
  63         struct huffman_symbols *sym;
  64         unsigned int bits;
  65         unsigned int huf;
  66         unsigned int i;
  67
  68         /* Dump symbol table for each utilised length */
  69         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
  70                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
  71                 sym = &alphabet->huf[ bits - 1 ];
  72                 if ( sym->freq == 0 )
  73                         continue;
  74                 huf = ( sym->start >> sym->shift );
  75                 DBG ( "Huffman length %d start \"%s\" freq %d:", bits,
  76                       huffman_bin ( huf, sym->bits ), sym->freq );
  77                 for ( i = 0 ; i < sym->freq ; i++ ) {
  78                         DBG ( " %03x", sym->raw[ huf + i ] );
  79                 }
  80                 DBG ( "\n" );
  81         }
  82
  83         /* Dump quick lookup table */
  84         DBG ( "Huffman quick lookup:" );
  85         for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
  86                             sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
  87                 DBG ( " %d", ( alphabet->lookup[i] + 1 ) );
  88         }
  89         DBG ( "\n" );
  90 }
  91
  92 /**
  93  * Construct Huffman alphabet
  94  *
  95  * @v alphabet          Huffman alphabet
  96  * @v lengths           Symbol length table
  97  * @v count             Number of symbols
  98  * @ret rc              Return status code
  99  */
 100 int huffman_alphabet ( struct huffman_alphabet *alphabet,
 101                        uint8_t *lengths, unsigned int count ) {
 102         struct huffman_symbols *sym;
 103         unsigned int huf;
 104         unsigned int cum_freq;
 105         unsigned int bits;
 106         unsigned int raw;
 107         unsigned int adjustment;
 108         unsigned int prefix;
 109         int empty;
 110         int complete;
 111
 112         /* Clear symbol table */
 113         memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
 114
 115         /* Count number of symbols with each Huffman-coded length */
 116         empty = 1;
 117         for ( raw = 0 ; raw < count ; raw++ ) {
 118                 bits = lengths[raw];
 119                 if ( bits ) {
 120                         alphabet->huf[ bits - 1 ].freq++;
 121                         empty = 0;
 122                 }
 123         }
 124
 125         /* In the degenerate case of having no symbols (i.e. an unused
 126          * alphabet), generate a trivial alphabet with exactly two
 127          * single-bit codes.  This allows callers to avoid having to
 128          * check for this special case.
 129          */
 130         if ( empty )
 131                 alphabet->huf[0].freq = 2;
 132
 133         /* Populate Huffman-coded symbol table */
 134         huf = 0;
 135         cum_freq = 0;
 136         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 137                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 138                 sym = &alphabet->huf[ bits - 1 ];
 139                 sym->bits = bits;
 140                 sym->shift = ( HUFFMAN_BITS - bits );
 141                 sym->start = ( huf << sym->shift );
 142                 sym->raw = &alphabet->raw[cum_freq];
 143                 huf += sym->freq;
 144                 if ( huf > ( 1U << bits ) ) {
 145                         DBG ( "Huffman alphabet has too many symbols with "
 146                               "lengths <=%d\n", bits );
 147                         return -1;
 148                 }
 149                 huf <<= 1;
 150                 cum_freq += sym->freq;
 151         }
 152         complete = ( huf == ( 1U << bits ) );
 153
 154         /* Populate raw symbol table */
 155         for ( raw = 0 ; raw < count ; raw++ ) {
 156                 bits = lengths[raw];
 157                 if ( bits ) {
 158                         sym = &alphabet->huf[ bits - 1 ];
 159                         *(sym->raw++) = raw;
 160                 }
 161         }
 162
 163         /* Adjust Huffman-coded symbol table raw pointers and populate
 164          * quick lookup table.
 165          */
 166         for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
 167                                    sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
 168                 sym = &alphabet->huf[ bits - 1 ];
 169
 170                 /* Adjust raw pointer */
 171                 sym->raw -= sym->freq; /* Reset to first symbol */
 172                 adjustment = ( sym->start >> sym->shift );
 173                 sym->raw -= adjustment; /* Adjust for quick indexing */
 174
 175                 /* Populate quick lookup table */
 176                 for ( prefix = ( sym->start >> HUFFMAN_QL_SHIFT ) ;
 177                       prefix < ( 1 << HUFFMAN_QL_BITS ) ; prefix++ ) {
 178                         alphabet->lookup[prefix] = ( bits - 1 );
 179                 }
 180         }
 181
 182         /* Check that there are no invalid codes */
 183         if ( ! complete ) {
 184                 DBG ( "Huffman alphabet is incomplete\n" );
 185                 return -1;
 186         }
 187
 188         return 0;
 189 }
 190
 191 /**
 192  * Get Huffman symbol set
 193  *
 194  * @v alphabet          Huffman alphabet
 195  * @v huf               Raw input value (normalised to HUFFMAN_BITS bits)
 196  * @ret sym             Huffman symbol set
 197  */
 198 struct huffman_symbols * huffman_sym ( struct huffman_alphabet *alphabet,
 199                                        unsigned int huf ) {
 200         struct huffman_symbols *sym;
 201         unsigned int lookup_index;
 202
 203         /* Find symbol set for this length */
 204         lookup_index = ( huf >> HUFFMAN_QL_SHIFT );
 205         sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
 206         while ( huf < sym->start )
 207                 sym--;
 208         return sym;
 209 }