/src/libfvde/libfvde/libfvde_huffman_tree.c

Source (jump to first uncovered line)
/*
 * Huffman tree functions
 *
 * Copyright (C) 2011-2024, Omar Choudary <choudary.omar@gmail.com>,
 *                          Joachim Metz <joachim.metz@gmail.com>
 *
 * Refer to AUTHORS for acknowledgements.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

#include <common.h>
#include <memory.h>
#include <types.h>

#include "libfvde_bit_stream.h"
#include "libfvde_huffman_tree.h"
#include "libfvde_libcerror.h"
#include "libfvde_libcnotify.h"

/* Creates a Huffman tree
 * Make sure the value huffman_tree is referencing, is set to NULL
 * Returns 1 if successful or -1 on error
 */
int libfvde_huffman_tree_initialize(
     libfvde_huffman_tree_t **huffman_tree,
     int number_of_symbols,
     uint8_t maximum_code_size,
     libcerror_error_t **error )
{
  static char *function = "libfvde_huffman_tree_initialize";
  size_t array_size     = 0;

  if( huffman_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid Huffman tree.",
     function );

    return( -1 );
  }
  if( *huffman_tree != NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
     "%s: invalid Huffman tree value already set.",
     function );

    return( -1 );
  }
  if( ( number_of_symbols < 0 )
   || ( number_of_symbols > 1024 ) )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid number of symbols value out of bounds.",
     function );

    return( -1 );
  }
  if( maximum_code_size > 32 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid maximum code size value out of bounds.",
     function );

    return( -1 );
  }
  *huffman_tree = memory_allocate_structure(
                   libfvde_huffman_tree_t );

  if( *huffman_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
     "%s: unable to create Huffman tree.",
     function );

    goto on_error;
  }
  if( memory_set(
       *huffman_tree,
       0,
       sizeof( libfvde_huffman_tree_t ) ) == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_SET_FAILED,
     "%s: unable to clear Huffman tree.",
     function );

    memory_free(
     *huffman_tree );

    *huffman_tree = NULL;

    return( -1 );
  }
  array_size = sizeof( uint16_t ) * number_of_symbols;

  ( *huffman_tree )->symbols = (uint16_t *) memory_allocate(
                                             array_size );

  if( ( *huffman_tree )->symbols == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
     "%s: unable to create symbols.",
     function );

    goto on_error;
  }
  if( memory_set(
       ( *huffman_tree )->symbols,
       0,
       array_size ) == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_SET_FAILED,
     "%s: unable to clear symbols.",
     function );

    goto on_error;
  }
  array_size = sizeof( int ) * ( maximum_code_size + 1 );

  ( *huffman_tree )->code_size_counts = (int *) memory_allocate(
                                                 array_size );

  if( ( *huffman_tree )->code_size_counts == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
     "%s: unable to create code size counts.",
     function );

    goto on_error;
  }
  if( memory_set(
       ( *huffman_tree )->code_size_counts,
       0,
       array_size ) == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_SET_FAILED,
     "%s: unable to clear code size counts.",
     function );

    goto on_error;
  }
  ( *huffman_tree )->maximum_code_size = maximum_code_size;

  return( 1 );

on_error:
  if( *huffman_tree != NULL )
  {
    if( ( *huffman_tree )->code_size_counts != NULL )
    {
      memory_free(
       ( *huffman_tree )->code_size_counts );
    }
    if( ( *huffman_tree )->symbols != NULL )
    {
      memory_free(
       ( *huffman_tree )->symbols );
    }
    memory_free(
     *huffman_tree );

    *huffman_tree = NULL;
  }
  return( -1 );
}

/* Frees a Huffman tree
 * Returns 1 if successful or -1 on error
 */
int libfvde_huffman_tree_free(
     libfvde_huffman_tree_t **huffman_tree,
     libcerror_error_t **error )
{
  static char *function = "libfvde_huffman_tree_free";

  if( huffman_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid Huffman tree.",
     function );

    return( -1 );
  }
  if( *huffman_tree != NULL )
  {
    if( ( *huffman_tree )->code_size_counts != NULL )
    {
      memory_free(
       ( *huffman_tree )->code_size_counts );
    }
    if( ( *huffman_tree )->symbols != NULL )
    {
      memory_free(
       ( *huffman_tree )->symbols );
    }
    memory_free(
     *huffman_tree );

    *huffman_tree = NULL;
  }
  return( 1 );
}

/* Builds the Huffman tree
 * Returns 1 on success, 0 if the tree is empty or -1 on error
 */
int libfvde_huffman_tree_build(
     libfvde_huffman_tree_t *huffman_tree,
     const uint8_t *code_sizes_array,
     int number_of_code_sizes,
     libcerror_error_t **error )
{
  int *symbol_offsets   = NULL;
  static char *function = "libfvde_huffman_tree_build";
  size_t array_size     = 0;
  uint16_t symbol       = 0;
  uint8_t bit_index     = 0;
  uint8_t code_size     = 0;
  int code_offset       = 0;
  int left_value        = 0;

  if( huffman_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid Huffman tree.",
     function );

    return( -1 );
  }
  if( code_sizes_array == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid code sizes array.",
     function );

    return( -1 );
  }
  if( ( number_of_code_sizes < 0 )
   || ( number_of_code_sizes > (int) INT16_MAX ) )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid number of code sizes value out of bounds.",
     function );

    return( -1 );
  }
  /* Determine the code size frequencies
   */
  array_size = sizeof( int ) * ( huffman_tree->maximum_code_size + 1 );

  if( memory_set(
       huffman_tree->code_size_counts,
       0,
       array_size ) == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_SET_FAILED,
     "%s: unable to clear code size counts.",
     function );

    goto on_error;
  }
  for( symbol = 0;
       symbol < (uint16_t) number_of_code_sizes;
       symbol++ )
  {
    code_size = code_sizes_array[ symbol ];

    if( code_size > huffman_tree->maximum_code_size )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
       "%s: invalid symbol: %d code size: %" PRIu8 " value out of bounds.",
       function,
       symbol,
       code_size );

      goto on_error;
    }
    huffman_tree->code_size_counts[ code_size ] += 1;
  }
  /* The tree has no codes
   */
  if( huffman_tree->code_size_counts[ 0 ] == number_of_code_sizes )
  {
    return( 0 );
  }
  /* Check if the set of code sizes is incomplete or over-subscribed
   */
  left_value = 1;

  for( bit_index = 1;
       bit_index <= huffman_tree->maximum_code_size;
       bit_index++ )
  {
    left_value <<= 1;
    left_value  -= huffman_tree->code_size_counts[ bit_index ];

    if( left_value < 0 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
       "%s: code sizes are over-subscribed.",
       function );

      goto on_error;
    }
  }
/* TODO
  if( left_value > 0 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: code sizes are incomplete.",
     function );

    goto on_error;
  }
*/
  symbol_offsets = (int *) memory_allocate(
                            array_size );

  if( symbol_offsets == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_MEMORY,
     LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
     "%s: unable to create symbol offsets.",
     function );

    goto on_error;
  }
  /* Calculate the offsets to sort the symbols per code size
   */
  symbol_offsets[ 0 ] = 0;
  symbol_offsets[ 1 ] = 0;

  for( bit_index = 1;
       bit_index < huffman_tree->maximum_code_size;
       bit_index++ )
  {
    symbol_offsets[ bit_index + 1 ] = symbol_offsets[ bit_index ] + huffman_tree->code_size_counts[ bit_index ];
  }
  /* Fill the symbols sorted by code size
   */
  for( symbol = 0;
       symbol < (uint16_t) number_of_code_sizes;
       symbol++ )
  {
    code_size = code_sizes_array[ symbol ];

    if( code_size == 0 )
    {
      continue;
    }
    code_offset = symbol_offsets[ code_size ];

    if( ( code_offset < 0 )
     || ( code_offset > number_of_code_sizes ) )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
       "%s: invalid symbol: %" PRIu16 " code offset: %d value out of bounds.",
       function,
       symbol,
       code_offset );

      goto on_error;
    }
    symbol_offsets[ code_size ] += 1;

    huffman_tree->symbols[ code_offset ] = symbol;
  }
  memory_free(
   symbol_offsets );

  return( 1 );

on_error:
  if( symbol_offsets != NULL )
  {
    memory_free(
     symbol_offsets );
  }
  return( -1 );
}

/* Retrieves a symbol based on the Huffman code read from the bit-stream
 * Returns 1 on success or -1 on error
 */
int libfvde_huffman_tree_get_symbol_from_bit_stream(
     libfvde_huffman_tree_t *huffman_tree,
     libfvde_bit_stream_t *bit_stream,
     uint16_t *symbol,
     libcerror_error_t **error )
{
  static char *function  = "libfvde_huffman_tree_get_symbol_from_bit_stream";
  uint32_t value_32bit   = 0;
  uint16_t safe_symbol   = 0;
  uint8_t bit_index      = 0;
  int code_size_count    = 0;
  int first_huffman_code = 0;
  int first_index        = 0;
  int huffman_code       = 0;
  int result             = 0;

  if( huffman_tree == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid Huffman tree.",
     function );

    return( -1 );
  }
  if( bit_stream == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid bit stream.",
     function );

    return( -1 );
  }
  if( symbol == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid symbol.",
     function );

    return( -1 );
  }
/* TODO get maximum_code_size of bits into local bit buffer */

  for( bit_index = 1;
       bit_index <= huffman_tree->maximum_code_size;
       bit_index++ )
  {
    if( libfvde_bit_stream_get_value(
         bit_stream,
         1,
         &value_32bit,
         error ) != 1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_GET_FAILED,
       "%s: unable to retrieve value from bit stream.",
       function );

      return( -1 );
    }
    huffman_code <<= 1;
    huffman_code  |= (int) value_32bit;

    code_size_count = huffman_tree->code_size_counts[ bit_index ];

    if( ( huffman_code - code_size_count ) < first_huffman_code )
    {
      safe_symbol = huffman_tree->symbols[ first_index + ( huffman_code - first_huffman_code ) ];

      result = 1;

      break;
    }
    first_huffman_code  += code_size_count;
    first_huffman_code <<= 1;
    first_index         += code_size_count;
  }
  if( result != 1 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid Huffman code: 0x%08" PRIx32 ".",
     function,
     huffman_code );

    return( -1 );
  }
  *symbol = safe_symbol;

  return( 1 );
}


Coverage Report

Created: 2025-09-05 06:58

Line	Count	Source (jump to first uncovered line)
1		/*
2		* Huffman tree functions
3		*
4		* Copyright (C) 2011-2024, Omar Choudary <choudary.omar@gmail.com>,
5		* Joachim Metz <joachim.metz@gmail.com>
6		*
7		* Refer to AUTHORS for acknowledgements.
8		*
9		* This program is free software: you can redistribute it and/or modify
10		* it under the terms of the GNU Lesser General Public License as published by
11		* the Free Software Foundation, either version 3 of the License, or
12		* (at your option) any later version.
13		*
14		* This program is distributed in the hope that it will be useful,
15		* but WITHOUT ANY WARRANTY; without even the implied warranty of
16		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17		* GNU General Public License for more details.
18		*
19		* You should have received a copy of the GNU Lesser General Public License
20		* along with this program. If not, see <https://www.gnu.org/licenses/>.
21		*/
22
23		#include <common.h>
24		#include <memory.h>
25		#include <types.h>
26
27		#include "libfvde_bit_stream.h"
28		#include "libfvde_huffman_tree.h"
29		#include "libfvde_libcerror.h"
30		#include "libfvde_libcnotify.h"
31
32		/* Creates a Huffman tree
33		* Make sure the value huffman_tree is referencing, is set to NULL
34		* Returns 1 if successful or -1 on error
35		*/
36		int libfvde_huffman_tree_initialize(
37		libfvde_huffman_tree_t **huffman_tree,
38		int number_of_symbols,
39		uint8_t maximum_code_size,
40		libcerror_error_t **error )
41	0	{
42	0	static char *function = "libfvde_huffman_tree_initialize";
43	0	size_t array_size = 0;
44
45	0	if( huffman_tree == NULL )
46	0	{
47	0	libcerror_error_set(
48	0	error,
49	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
50	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
51	0	"%s: invalid Huffman tree.",
52	0	function );
53
54	0	return( -1 );
55	0	}
56	0	if( *huffman_tree != NULL )
57	0	{
58	0	libcerror_error_set(
59	0	error,
60	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
61	0	LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
62	0	"%s: invalid Huffman tree value already set.",
63	0	function );
64
65	0	return( -1 );
66	0	}
67	0	if( ( number_of_symbols < 0 )
68	0	\|\| ( number_of_symbols > 1024 ) )
69	0	{
70	0	libcerror_error_set(
71	0	error,
72	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
73	0	LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
74	0	"%s: invalid number of symbols value out of bounds.",
75	0	function );
76
77	0	return( -1 );
78	0	}
79	0	if( maximum_code_size > 32 )
80	0	{
81	0	libcerror_error_set(
82	0	error,
83	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
84	0	LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
85	0	"%s: invalid maximum code size value out of bounds.",
86	0	function );
87
88	0	return( -1 );
89	0	}
90	0	*huffman_tree = memory_allocate_structure(
91	0	libfvde_huffman_tree_t );
92
93	0	if( *huffman_tree == NULL )
94	0	{
95	0	libcerror_error_set(
96	0	error,
97	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
98	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
99	0	"%s: unable to create Huffman tree.",
100	0	function );
101
102	0	goto on_error;
103	0	}
104	0	if( memory_set(
105	0	*huffman_tree,
106	0	0,
107	0	sizeof( libfvde_huffman_tree_t ) ) == NULL )
108	0	{
109	0	libcerror_error_set(
110	0	error,
111	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
112	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
113	0	"%s: unable to clear Huffman tree.",
114	0	function );
115
116	0	memory_free(
117	0	*huffman_tree );
118
119	0	*huffman_tree = NULL;
120
121	0	return( -1 );
122	0	}
123	0	array_size = sizeof( uint16_t ) * number_of_symbols;
124
125	0	( huffman_tree )->symbols = (uint16_t ) memory_allocate(
126	0	array_size );
127
128	0	if( ( *huffman_tree )->symbols == NULL )
129	0	{
130	0	libcerror_error_set(
131	0	error,
132	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
133	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
134	0	"%s: unable to create symbols.",
135	0	function );
136
137	0	goto on_error;
138	0	}
139	0	if( memory_set(
140	0	( *huffman_tree )->symbols,
141	0	0,
142	0	array_size ) == NULL )
143	0	{
144	0	libcerror_error_set(
145	0	error,
146	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
147	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
148	0	"%s: unable to clear symbols.",
149	0	function );
150
151	0	goto on_error;
152	0	}
153	0	array_size = sizeof( int ) * ( maximum_code_size + 1 );
154
155	0	( huffman_tree )->code_size_counts = (int ) memory_allocate(
156	0	array_size );
157
158	0	if( ( *huffman_tree )->code_size_counts == NULL )
159	0	{
160	0	libcerror_error_set(
161	0	error,
162	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
163	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
164	0	"%s: unable to create code size counts.",
165	0	function );
166
167	0	goto on_error;
168	0	}
169	0	if( memory_set(
170	0	( *huffman_tree )->code_size_counts,
171	0	0,
172	0	array_size ) == NULL )
173	0	{
174	0	libcerror_error_set(
175	0	error,
176	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
177	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
178	0	"%s: unable to clear code size counts.",
179	0	function );
180
181	0	goto on_error;
182	0	}
183	0	( *huffman_tree )->maximum_code_size = maximum_code_size;
184
185	0	return( 1 );
186
187	0	on_error:
188	0	if( *huffman_tree != NULL )
189	0	{
190	0	if( ( *huffman_tree )->code_size_counts != NULL )
191	0	{
192	0	memory_free(
193	0	( *huffman_tree )->code_size_counts );
194	0	}
195	0	if( ( *huffman_tree )->symbols != NULL )
196	0	{
197	0	memory_free(
198	0	( *huffman_tree )->symbols );
199	0	}
200	0	memory_free(
201	0	*huffman_tree );
202
203	0	*huffman_tree = NULL;
204	0	}
205	0	return( -1 );
206	0	}
207
208		/* Frees a Huffman tree
209		* Returns 1 if successful or -1 on error
210		*/
211		int libfvde_huffman_tree_free(
212		libfvde_huffman_tree_t **huffman_tree,
213		libcerror_error_t **error )
214	0	{
215	0	static char *function = "libfvde_huffman_tree_free";
216
217	0	if( huffman_tree == NULL )
218	0	{
219	0	libcerror_error_set(
220	0	error,
221	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
222	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
223	0	"%s: invalid Huffman tree.",
224	0	function );
225
226	0	return( -1 );
227	0	}
228	0	if( *huffman_tree != NULL )
229	0	{
230	0	if( ( *huffman_tree )->code_size_counts != NULL )
231	0	{
232	0	memory_free(
233	0	( *huffman_tree )->code_size_counts );
234	0	}
235	0	if( ( *huffman_tree )->symbols != NULL )
236	0	{
237	0	memory_free(
238	0	( *huffman_tree )->symbols );
239	0	}
240	0	memory_free(
241	0	*huffman_tree );
242
243	0	*huffman_tree = NULL;
244	0	}
245	0	return( 1 );
246	0	}
247
248		/* Builds the Huffman tree
249		* Returns 1 on success, 0 if the tree is empty or -1 on error
250		*/
251		int libfvde_huffman_tree_build(
252		libfvde_huffman_tree_t *huffman_tree,
253		const uint8_t *code_sizes_array,
254		int number_of_code_sizes,
255		libcerror_error_t **error )
256	0	{
257	0	int *symbol_offsets = NULL;
258	0	static char *function = "libfvde_huffman_tree_build";
259	0	size_t array_size = 0;
260	0	uint16_t symbol = 0;
261	0	uint8_t bit_index = 0;
262	0	uint8_t code_size = 0;
263	0	int code_offset = 0;
264	0	int left_value = 0;
265
266	0	if( huffman_tree == NULL )
267	0	{
268	0	libcerror_error_set(
269	0	error,
270	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
271	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
272	0	"%s: invalid Huffman tree.",
273	0	function );
274
275	0	return( -1 );
276	0	}
277	0	if( code_sizes_array == NULL )
278	0	{
279	0	libcerror_error_set(
280	0	error,
281	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
282	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
283	0	"%s: invalid code sizes array.",
284	0	function );
285
286	0	return( -1 );
287	0	}
288	0	if( ( number_of_code_sizes < 0 )
289	0	\|\| ( number_of_code_sizes > (int) INT16_MAX ) )
290	0	{
291	0	libcerror_error_set(
292	0	error,
293	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
294	0	LIBCERROR_ARGUMENT_ERROR_VALUE_OUT_OF_BOUNDS,
295	0	"%s: invalid number of code sizes value out of bounds.",
296	0	function );
297
298	0	return( -1 );
299	0	}
300		/* Determine the code size frequencies
301		*/
302	0	array_size = sizeof( int ) * ( huffman_tree->maximum_code_size + 1 );
303
304	0	if( memory_set(
305	0	huffman_tree->code_size_counts,
306	0	0,
307	0	array_size ) == NULL )
308	0	{
309	0	libcerror_error_set(
310	0	error,
311	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
312	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
313	0	"%s: unable to clear code size counts.",
314	0	function );
315
316	0	goto on_error;
317	0	}
318	0	for( symbol = 0;
319	0	symbol < (uint16_t) number_of_code_sizes;
320	0	symbol++ )
321	0	{
322	0	code_size = code_sizes_array[ symbol ];
323
324	0	if( code_size > huffman_tree->maximum_code_size )
325	0	{
326	0	libcerror_error_set(
327	0	error,
328	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
329	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
330	0	"%s: invalid symbol: %d code size: %" PRIu8 " value out of bounds.",
331	0	function,
332	0	symbol,
333	0	code_size );
334
335	0	goto on_error;
336	0	}
337	0	huffman_tree->code_size_counts[ code_size ] += 1;
338	0	}
339		/* The tree has no codes
340		*/
341	0	if( huffman_tree->code_size_counts[ 0 ] == number_of_code_sizes )
342	0	{
343	0	return( 0 );
344	0	}
345		/* Check if the set of code sizes is incomplete or over-subscribed
346		*/
347	0	left_value = 1;
348
349	0	for( bit_index = 1;
350	0	bit_index <= huffman_tree->maximum_code_size;
351	0	bit_index++ )
352	0	{
353	0	left_value <<= 1;
354	0	left_value -= huffman_tree->code_size_counts[ bit_index ];
355
356	0	if( left_value < 0 )
357	0	{
358	0	libcerror_error_set(
359	0	error,
360	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
361	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
362	0	"%s: code sizes are over-subscribed.",
363	0	function );
364
365	0	goto on_error;
366	0	}
367	0	}
368		/* TODO
369		if( left_value > 0 )
370		{
371		libcerror_error_set(
372		error,
373		LIBCERROR_ERROR_DOMAIN_RUNTIME,
374		LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
375		"%s: code sizes are incomplete.",
376		function );
377
378		goto on_error;
379		}
380		*/
381	0	symbol_offsets = (int *) memory_allocate(
382	0	array_size );
383
384	0	if( symbol_offsets == NULL )
385	0	{
386	0	libcerror_error_set(
387	0	error,
388	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
389	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
390	0	"%s: unable to create symbol offsets.",
391	0	function );
392
393	0	goto on_error;
394	0	}
395		/* Calculate the offsets to sort the symbols per code size
396		*/
397	0	symbol_offsets[ 0 ] = 0;
398	0	symbol_offsets[ 1 ] = 0;
399
400	0	for( bit_index = 1;
401	0	bit_index < huffman_tree->maximum_code_size;
402	0	bit_index++ )
403	0	{
404	0	symbol_offsets[ bit_index + 1 ] = symbol_offsets[ bit_index ] + huffman_tree->code_size_counts[ bit_index ];
405	0	}
406		/* Fill the symbols sorted by code size
407		*/
408	0	for( symbol = 0;
409	0	symbol < (uint16_t) number_of_code_sizes;
410	0	symbol++ )
411	0	{
412	0	code_size = code_sizes_array[ symbol ];
413
414	0	if( code_size == 0 )
415	0	{
416	0	continue;
417	0	}
418	0	code_offset = symbol_offsets[ code_size ];
419
420	0	if( ( code_offset < 0 )
421	0	\|\| ( code_offset > number_of_code_sizes ) )
422	0	{
423	0	libcerror_error_set(
424	0	error,
425	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
426	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
427	0	"%s: invalid symbol: %" PRIu16 " code offset: %d value out of bounds.",
428	0	function,
429	0	symbol,
430	0	code_offset );
431
432	0	goto on_error;
433	0	}
434	0	symbol_offsets[ code_size ] += 1;
435
436	0	huffman_tree->symbols[ code_offset ] = symbol;
437	0	}
438	0	memory_free(
439	0	symbol_offsets );
440
441	0	return( 1 );
442
443	0	on_error:
444	0	if( symbol_offsets != NULL )
445	0	{
446	0	memory_free(
447	0	symbol_offsets );
448	0	}
449	0	return( -1 );
450	0	}
451
452		/* Retrieves a symbol based on the Huffman code read from the bit-stream
453		* Returns 1 on success or -1 on error
454		*/
455		int libfvde_huffman_tree_get_symbol_from_bit_stream(
456		libfvde_huffman_tree_t *huffman_tree,
457		libfvde_bit_stream_t *bit_stream,
458		uint16_t *symbol,
459		libcerror_error_t **error )
460	0	{
461	0	static char *function = "libfvde_huffman_tree_get_symbol_from_bit_stream";
462	0	uint32_t value_32bit = 0;
463	0	uint16_t safe_symbol = 0;
464	0	uint8_t bit_index = 0;
465	0	int code_size_count = 0;
466	0	int first_huffman_code = 0;
467	0	int first_index = 0;
468	0	int huffman_code = 0;
469	0	int result = 0;
470
471	0	if( huffman_tree == NULL )
472	0	{
473	0	libcerror_error_set(
474	0	error,
475	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
476	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
477	0	"%s: invalid Huffman tree.",
478	0	function );
479
480	0	return( -1 );
481	0	}
482	0	if( bit_stream == NULL )
483	0	{
484	0	libcerror_error_set(
485	0	error,
486	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
487	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
488	0	"%s: invalid bit stream.",
489	0	function );
490
491	0	return( -1 );
492	0	}
493	0	if( symbol == NULL )
494	0	{
495	0	libcerror_error_set(
496	0	error,
497	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
498	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
499	0	"%s: invalid symbol.",
500	0	function );
501
502	0	return( -1 );
503	0	}
504		/* TODO get maximum_code_size of bits into local bit buffer */
505
506	0	for( bit_index = 1;
507	0	bit_index <= huffman_tree->maximum_code_size;
508	0	bit_index++ )
509	0	{
510	0	if( libfvde_bit_stream_get_value(
511	0	bit_stream,
512	0	1,
513	0	&value_32bit,
514	0	error ) != 1 )
515	0	{
516	0	libcerror_error_set(
517	0	error,
518	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
519	0	LIBCERROR_RUNTIME_ERROR_GET_FAILED,
520	0	"%s: unable to retrieve value from bit stream.",
521	0	function );
522
523	0	return( -1 );
524	0	}
525	0	huffman_code <<= 1;
526	0	huffman_code \|= (int) value_32bit;
527
528	0	code_size_count = huffman_tree->code_size_counts[ bit_index ];
529
530	0	if( ( huffman_code - code_size_count ) < first_huffman_code )
531	0	{
532	0	safe_symbol = huffman_tree->symbols[ first_index + ( huffman_code - first_huffman_code ) ];
533
534	0	result = 1;
535
536	0	break;
537	0	}
538	0	first_huffman_code += code_size_count;
539	0	first_huffman_code <<= 1;
540	0	first_index += code_size_count;
541	0	}
542	0	if( result != 1 )
543	0	{
544	0	libcerror_error_set(
545	0	error,
546	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
547	0	LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
548	0	"%s: invalid Huffman code: 0x%08" PRIx32 ".",
549	0	function,
550	0	huffman_code );
551
552	0	return( -1 );
553	0	}
554	0	*symbol = safe_symbol;
555
556	0	return( 1 );
557	0	}
558