GRUB2/MOD_SRC/grub-2.04/grub-core/ventoy/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 /** Maximum length of a Huffman symbol (in bits) */
  31 #define HUFFMAN_BITS 16
  32
  33 /** Raw huffman symbol */
  34 typedef uint16_t huffman_raw_symbol_t;
  35
  36 /** Quick lookup length for a Huffman symbol (in bits)
  37  *
  38  * This is a policy decision.
  39  */
  40 #define HUFFMAN_QL_BITS 7
  41
  42 /** Quick lookup shift */
  43 #define HUFFMAN_QL_SHIFT ( HUFFMAN_BITS - HUFFMAN_QL_BITS )
  44
  45 /** A Huffman-coded set of symbols of a given length */
  46 struct huffman_symbols {
  47         /** Length of Huffman-coded symbols (in bits) */
  48         uint8_t bits;
  49         /** Shift to normalise symbols of this length to HUFFMAN_BITS bits */
  50         uint8_t shift;
  51         /** Number of Huffman-coded symbols having this length */
  52         uint16_t freq;
  53         /** First symbol of this length (normalised to HUFFMAN_BITS bits)
  54          *
  55          * Stored as a 32-bit value to allow the value
  56          * (1<<HUFFMAN_BITS ) to be used for empty sets of symbols
  57          * longer than the maximum utilised length.
  58          */
  59         uint32_t start;
  60         /** Raw symbols having this length */
  61         huffman_raw_symbol_t *raw;
  62 };
  63
  64 /** A Huffman-coded alphabet */
  65 struct huffman_alphabet {
  66         /** Huffman-coded symbol set for each length */
  67         struct huffman_symbols huf[HUFFMAN_BITS];
  68         /** Quick lookup table */
  69         uint8_t lookup[ 1 << HUFFMAN_QL_BITS ];
  70         /** Raw symbols
  71          *
  72          * Ordered by Huffman-coded symbol length, then by symbol
  73          * value.  This field has a variable length.
  74          */
  75         huffman_raw_symbol_t raw[0];
  76 };
  77
  78 /**
  79  * Get Huffman symbol length
  80  *
  81  * @v sym               Huffman symbol set
  82  * @ret len             Length (in bits)
  83  */
  84 static inline __attribute__ (( always_inline )) unsigned int
  85 huffman_len ( struct huffman_symbols *sym ) {
  86
  87         return sym->bits;
  88 }
  89
  90 /**
  91  * Get Huffman symbol value
  92  *
  93  * @v sym               Huffman symbol set
  94  * @v huf               Raw input value (normalised to HUFFMAN_BITS bits)
  95  * @ret raw             Raw symbol value
  96  */
  97 static inline __attribute__ (( always_inline )) huffman_raw_symbol_t
  98 huffman_raw ( struct huffman_symbols *sym, unsigned int huf ) {
  99
 100         return sym->raw[ huf >> sym->shift ];
 101 }
 102
 103 extern int huffman_alphabet ( struct huffman_alphabet *alphabet,
 104                               uint8_t *lengths, unsigned int count );
 105 extern struct huffman_symbols *
 106 huffman_sym ( struct huffman_alphabet *alphabet, unsigned int huf );
 107
 108 #endif /* _HUFFMAN_H */