wimboot/wimboot-2.7.3/src/huffman.h

   1 #ifndef _HUFFMAN_H
   2 #define _HUFFMAN_H
   3
   4 /*
   5  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
   6  *
   7  * This program is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License as
   9  * published by the Free Software Foundation; either version 2 of the
  10  * License, or (at your option) any later version.
  11  *
  12  * This program is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20  * 02110-1301, USA.
  21  */
  22
  23 /**
  24  * @file
  25  *
  26  * Huffman alphabets
  27  *
  28  */
  29
  30 #include <stdint.h>
  31
  32 /** Maximum length of a Huffman symbol (in bits) */
  33 #define HUFFMAN_BITS 16
  34
  35 /** Raw huffman symbol */
  36 typedef uint16_t huffman_raw_symbol_t;
  37
  38 /** Quick lookup length for a Huffman symbol (in bits)
  39  *
  40  * This is a policy decision.
  41  */
  42 #define HUFFMAN_QL_BITS 7
  43
  44 /** Quick lookup shift */
  45 #define HUFFMAN_QL_SHIFT ( HUFFMAN_BITS - HUFFMAN_QL_BITS )
  46
  47 /** A Huffman-coded set of symbols of a given length */
  48 struct huffman_symbols {
  49         /** Length of Huffman-coded symbols (in bits) */
  50         uint8_t bits;
  51         /** Shift to normalise symbols of this length to HUFFMAN_BITS bits */
  52         uint8_t shift;
  53         /** Number of Huffman-coded symbols having this length */
  54         uint16_t freq;
  55         /** First symbol of this length (normalised to HUFFMAN_BITS bits)
  56          *
  57          * Stored as a 32-bit value to allow the value
  58          * (1<<HUFFMAN_BITS ) to be used for empty sets of symbols
  59          * longer than the maximum utilised length.
  60          */
  61         uint32_t start;
  62         /** Raw symbols having this length */
  63         huffman_raw_symbol_t *raw;
  64 };
  65
  66 /** A Huffman-coded alphabet */
  67 struct huffman_alphabet {
  68         /** Huffman-coded symbol set for each length */
  69         struct huffman_symbols huf[HUFFMAN_BITS];
  70         /** Quick lookup table */
  71         uint8_t lookup[ 1 << HUFFMAN_QL_BITS ];
  72         /** Raw symbols
  73          *
  74          * Ordered by Huffman-coded symbol length, then by symbol
  75          * value.  This field has a variable length.
  76          */
  77         huffman_raw_symbol_t raw[0];
  78 };
  79
  80 /**
  81  * Get Huffman symbol length
  82  *
  83  * @v sym               Huffman symbol set
  84  * @ret len             Length (in bits)
  85  */
  86 static inline __attribute__ (( always_inline )) unsigned int
  87 huffman_len ( struct huffman_symbols *sym ) {
  88
  89         return sym->bits;
  90 }
  91
  92 /**
  93  * Get Huffman symbol value
  94  *
  95  * @v sym               Huffman symbol set
  96  * @v huf               Raw input value (normalised to HUFFMAN_BITS bits)
  97  * @ret raw             Raw symbol value
  98  */
  99 static inline __attribute__ (( always_inline )) huffman_raw_symbol_t
 100 huffman_raw ( struct huffman_symbols *sym, unsigned int huf ) {
 101
 102         return sym->raw[ huf >> sym->shift ];
 103 }
 104
 105 extern int huffman_alphabet ( struct huffman_alphabet *alphabet,
 106                               uint8_t *lengths, unsigned int count );
 107 extern struct huffman_symbols *
 108 huffman_sym ( struct huffman_alphabet *alphabet, unsigned int huf );
 109
 110 #endif /* _HUFFMAN_H */