/src/libfwnt/libfwnt/libfwnt_huffman_tree.c

Source
/*
 * Huffman tree functions
 *
 * Copyright (C) 2009-2026, 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 "libfwnt_bit_stream.h"
#include "libfwnt_huffman_tree.h"
#include "libfwnt_libcerror.h"
#include "libfwnt_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 libfwnt_huffman_tree_initialize(
     libfwnt_huffman_tree_t **huffman_tree,
     int number_of_symbols,
     uint8_t maximum_code_size,
     libcerror_error_t **error )
{
  static char *function = "libfwnt_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(
                   libfwnt_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( libfwnt_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( int ) * number_of_symbols;

  ( *huffman_tree )->symbols = (int *) 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 libfwnt_huffman_tree_free(
     libfwnt_huffman_tree_t **huffman_tree,
     libcerror_error_t **error )
{
  static char *function = "libfwnt_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 libfwnt_huffman_tree_build(
     libfwnt_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 = "libfwnt_huffman_tree_build";
  size_t array_size     = 0;
  uint8_t bit_index     = 0;
  uint8_t code_size     = 0;
  int code_offset       = 0;
  int left_value        = 0;
  int symbol            = 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->maximum_code_size == 0 )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_OUT_OF_BOUNDS,
     "%s: invalid Huffman tree - maximum code size value out of bounds.",
     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 )
  {
    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 < 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 < 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: %d 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 libfwnt_huffman_tree_get_symbol_from_bit_stream(
     libfwnt_huffman_tree_t *huffman_tree,
     libfwnt_bit_stream_t *bit_stream,
     uint32_t *symbol,
     libcerror_error_t **error )
{
  static char *function  = "libfwnt_huffman_tree_get_symbol_from_bit_stream";
  uint32_t safe_symbol   = 0;
  uint32_t value_32bit   = 0;
  uint8_t bit_index      = 0;
  uint8_t number_of_bits = 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 );
  }
  /* Try to fill the bit buffer with the maximum number of bits
   */
  while( bit_stream->bit_buffer_size < huffman_tree->maximum_code_size )
  {
    result = libfwnt_bit_stream_read(
              bit_stream,
              huffman_tree->maximum_code_size,
              error );

    if( result == -1 )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_IO,
       LIBCERROR_IO_ERROR_READ_FAILED,
       "%s: unable to read bits.",
       function );

      return( -1 );
    }
    else if( result == 0 )
    {
      break;
    }
  }
  if( huffman_tree->maximum_code_size < bit_stream->bit_buffer_size )
  {
    number_of_bits = huffman_tree->maximum_code_size;
  }
  else
  {
    number_of_bits = bit_stream->bit_buffer_size;
  }
  for( bit_index = 1;
       bit_index <= number_of_bits;
       bit_index++ )
  {
/* TODO get maximum_code_size of bits into local bit buffer */
    if( libfwnt_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: 2026-07-10 07:32

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