/src/libesedb/libesedb/libesedb_page_tree_key.c

Source
/*
 * Page tree key functions
 *
 * Copyright (C) 2009-2025, 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 "libesedb_definitions.h"
#include "libesedb_libcerror.h"
#include "libesedb_libcnotify.h"
#include "libesedb_libfcache.h"
#include "libesedb_libfdata.h"
#include "libesedb_page_tree_key.h"

/* Creates a page tree key
 * Make sure the value page_tree_key is referencing, is set to NULL
 * Returns 1 if successful or -1 on error
 */
int libesedb_page_tree_key_initialize(
     libesedb_page_tree_key_t **page_tree_key,
     libcerror_error_t **error )
{
  static char *function = "libesedb_page_tree_key_initialize";

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

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

    return( -1 );
  }
  *page_tree_key = memory_allocate_structure(
                    libesedb_page_tree_key_t );

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

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

    goto on_error;
  }
  return( 1 );

on_error:
  if( *page_tree_key != NULL )
  {
    memory_free(
     *page_tree_key );

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

/* Frees a page tree key
 * Returns 1 if successful or -1 on error
 */
int libesedb_page_tree_key_free(
     libesedb_page_tree_key_t **page_tree_key,
     libcerror_error_t **error )
{
  static char *function = "libesedb_page_tree_key_free";

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

    return( -1 );
  }
  if( *page_tree_key != NULL )
  {
    if( ( *page_tree_key )->data != NULL )
    {
      memory_free(
       ( *page_tree_key )->data );
    }
    memory_free(
     *page_tree_key );

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

/* Sets data
 * Returns 1 if successful or -1 on error
 */
int libesedb_page_tree_key_set_data(
     libesedb_page_tree_key_t *page_tree_key,
     const uint8_t *data,
     size_t data_size,
     libcerror_error_t **error )
{
  static char *function = "libesedb_page_tree_key_set_data";

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

    return( -1 );
  }
  if( page_tree_key->data != NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
     "%s: invalid page tree key - data already set.",
     function );

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

    return( -1 );
  }
  if( data_size > (size_t) MEMORY_MAXIMUM_ALLOCATION_SIZE )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_EXCEEDS_MAXIMUM,
     "%s: invalid data size value exceeds maximum allocation size.",
     function );

    return( -1 );
  }
  if( data_size > 0 )
  {
    page_tree_key->data = (uint8_t *) memory_allocate(
                                       sizeof( uint8_t ) * data_size );

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

      goto on_error;
    }
    if( memory_copy(
         page_tree_key->data,
         data,
         sizeof( uint8_t ) * data_size ) == NULL )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_MEMORY,
       LIBCERROR_MEMORY_ERROR_COPY_FAILED,
       "%s: unable to copy data.",
       function );

      goto on_error;
    }
    page_tree_key->data_size = data_size;
  }
  return( 1 );

on_error:
  if( page_tree_key->data != NULL )
  {
    memory_free(
     page_tree_key->data );

    page_tree_key->data = NULL;
  }
  page_tree_key->data_size = 0;

  return( -1 );
}

/* Append data
 * Returns 1 if successful or -1 on error
 */
int libesedb_page_tree_key_append_data(
     libesedb_page_tree_key_t *page_tree_key,
     const uint8_t *data,
     size_t data_size,
     libcerror_error_t **error )
{
  void *reallocation    = NULL;
  static char *function = "libesedb_page_tree_key_append_data";

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

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

    return( -1 );
  }
  if( data_size > (size_t) SSIZE_MAX )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_EXCEEDS_MAXIMUM,
     "%s: invalid data size value exceeds maximum.",
     function );

    return( -1 );
  }
  if( data_size > 0 )
  {
    reallocation = memory_reallocate(
                    page_tree_key->data,
                    sizeof( uint8_t ) * ( page_tree_key->data_size + data_size ) );

    if( reallocation == NULL )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_MEMORY,
       LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
       "%s: unable to resize data.",
       function );

      return( -1 );
    }
    page_tree_key->data = (uint8_t *) reallocation;

    if( memory_copy(
         &( page_tree_key->data[ page_tree_key->data_size ] ),
         data,
         sizeof( uint8_t ) * data_size ) == NULL )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_MEMORY,
       LIBCERROR_MEMORY_ERROR_COPY_FAILED,
       "%s: unable to copy data.",
       function );

      return( -1 );
    }
    page_tree_key->data_size += data_size;
  }
  return( 1 );
}

/* Compares two page tree keys
 * Returns LIBFDATA_COMPARE_LESS, LIBFDATA_COMPARE_EQUAL, LIBFDATA_COMPARE_GREATER,
 * LIBFDATA_COMPARE_GREATER_EQUAL if successful or -1 on error
 */
int libesedb_page_tree_key_compare(
     libesedb_page_tree_key_t *first_page_tree_key,
     libesedb_page_tree_key_t *second_page_tree_key,
     libcerror_error_t **error )
{
  static char *function                  = "libesedb_page_tree_key_compare";
  size_t compare_data_size               = 0;
  size_t first_page_tree_key_data_index  = 0;
  size_t second_page_tree_key_data_index = 0;
  int16_t compare_result                 = -1;
  uint8_t first_page_tree_key_data       = 0;
  int result                             = -1;

#if defined( HAVE_DEBUG_OUTPUT )
  uint8_t *page_tree_key_data            = NULL;
  size_t page_tree_key_data_size         = 0;
  uint8_t is_flexible_match              = 0;
#endif

  if( first_page_tree_key == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid first page tree key.",
     function );

    return( -1 );
  }
  if( first_page_tree_key->data == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
     "%s: invalid first page tree key - missing data.",
     function );

    return( -1 );
  }
  if( ( first_page_tree_key->type != LIBESEDB_KEY_TYPE_INDEX_VALUE )
   && ( first_page_tree_key->type != LIBESEDB_KEY_TYPE_LONG_VALUE )
   && ( first_page_tree_key->type != LIBESEDB_KEY_TYPE_LONG_VALUE_SEGMENT ) )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
     "%s: unsupported first page tree key type.",
     function );

    return( -1 );
  }
  if( second_page_tree_key == NULL )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
     LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
     "%s: invalid second page tree key.",
     function );

    return( -1 );
  }
  if( ( second_page_tree_key->type != LIBESEDB_KEY_TYPE_BRANCH )
   && ( second_page_tree_key->type != LIBESEDB_KEY_TYPE_LEAF ) )
  {
    libcerror_error_set(
     error,
     LIBCERROR_ERROR_DOMAIN_RUNTIME,
     LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
     "%s: unsupported second page tree key type.",
     function );

    return( -1 );
  }
#if defined( HAVE_DEBUG_OUTPUT )
  if( libcnotify_verbose != 0 )
  {
    libcnotify_printf(
     "%s: first page tree key\t\t\t: ",
     function );

    page_tree_key_data      = first_page_tree_key->data;
    page_tree_key_data_size = first_page_tree_key->data_size;

    while( page_tree_key_data_size > 0 )
    {
      if( libcnotify_verbose != 0 )
      {
        libcnotify_printf(
         "%02" PRIx8 " ",
         *page_tree_key_data );
      }
      page_tree_key_data++;
      page_tree_key_data_size--;
    }
    libcnotify_printf(
     "\n" );

    libcnotify_printf(
     "%s: first page tree key type\t\t: ",
     function );

    switch( first_page_tree_key->type )
    {
      case LIBESEDB_KEY_TYPE_INDEX_VALUE:
        libcnotify_printf(
         "index value" );
        break;

      case LIBESEDB_KEY_TYPE_LONG_VALUE:
        libcnotify_printf(
         "long value" );
        break;

      case LIBESEDB_KEY_TYPE_LONG_VALUE_SEGMENT:
        libcnotify_printf(
         "long value segment" );
        break;

      default:
        libcnotify_printf(
         "unknown" );
        break;
    }
    libcnotify_printf(
     "\n" );

    libcnotify_printf(
     "%s: second page tree key\t\t\t: ",
     function );

    page_tree_key_data      = second_page_tree_key->data;
    page_tree_key_data_size = second_page_tree_key->data_size;

    while( page_tree_key_data_size > 0 )
    {
      if( libcnotify_verbose != 0 )
      {
        libcnotify_printf(
         "%02" PRIx8 " ",
         *page_tree_key_data );
      }
      page_tree_key_data++;
      page_tree_key_data_size--;
    }
    libcnotify_printf(
     "\n" );

    libcnotify_printf(
     "%s: second page tree key type\t\t: ",
     function );

    switch( second_page_tree_key->type )
    {
      case LIBESEDB_KEY_TYPE_BRANCH:
        libcnotify_printf(
         "branch" );
        break;

      case LIBESEDB_KEY_TYPE_LEAF:
        libcnotify_printf(
         "leaf" );
        break;

      default:
        libcnotify_printf(
         "unknown" );
        break;
    }
    libcnotify_printf(
     "\n" );
  }
#endif /* defined( HAVE_DEBUG_OUTPUT ) */

  /* Check if the page tree key is empty, therefore has no upper bound
   * and thus the first page tree key will be greater than the second page tree key
   */
  if( second_page_tree_key->data_size > 0 )
  {
    if( second_page_tree_key->data == NULL )
    {
      libcerror_error_set(
       error,
       LIBCERROR_ERROR_DOMAIN_RUNTIME,
       LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
       "%s: invalid second page tree key - missing data.",
       function );

      return( -1 );
    }
    if( first_page_tree_key->data_size <= second_page_tree_key->data_size )
    {
      compare_data_size = first_page_tree_key->data_size;
    }
    else
    {
      compare_data_size = second_page_tree_key->data_size;
    }
#if defined( HAVE_DEBUG_OUTPUT )
    is_flexible_match = 0;
#endif

    /* The long value page_tree_key is stored reversed
     */
    if( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE )
    {
      first_page_tree_key_data_index = first_page_tree_key->data_size - 1;
    }
    else
    {
      first_page_tree_key_data_index = 0;
    }
    for( second_page_tree_key_data_index = 0;
         second_page_tree_key_data_index < compare_data_size;
         second_page_tree_key_data_index++ )
    {
      first_page_tree_key_data = first_page_tree_key->data[ first_page_tree_key_data_index ];

      if( ( first_page_tree_key->type == LIBESEDB_KEY_TYPE_INDEX_VALUE )
       && ( second_page_tree_key->type == LIBESEDB_KEY_TYPE_LEAF ) )
      {
/* TODO does not hold for branch page_tree_keys in Win XP search database */
        if( ( first_page_tree_key_data_index == 1 )
         && ( ( first_page_tree_key_data & 0x80 ) != 0 )
         && ( ( first_page_tree_key_data & 0x7f ) == second_page_tree_key->data[ second_page_tree_key_data_index ] ) )
        {
          first_page_tree_key_data &= 0x7f;

#if defined( HAVE_DEBUG_OUTPUT )
          is_flexible_match = 1;
#endif
        }
      }
      compare_result = (int16_t) first_page_tree_key_data - (int16_t) second_page_tree_key->data[ second_page_tree_key_data_index ];

      if( compare_result != 0 )
      {
        break;
      }
      if( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE )
      {
        first_page_tree_key_data_index--;
      }
      else
      {
        first_page_tree_key_data_index++;
      }
    }
  }
  if( compare_result > 0 )
  {
    result = LIBFDATA_COMPARE_GREATER;
  }
  else if( second_page_tree_key->type == LIBESEDB_KEY_TYPE_BRANCH )
  {
    if( first_page_tree_key->type == LIBESEDB_KEY_TYPE_INDEX_VALUE )
    {
      /* If the page_tree_key exactly matches the branch page_tree_key,
       * the leaf value is in the next branch node
       */
      if( compare_result == 0 )
      {
        result = LIBFDATA_COMPARE_GREATER;
      }
      else
      {
        result = LIBFDATA_COMPARE_EQUAL;
      }
    }
    else if( ( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE )
          || ( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE_SEGMENT ) )
    {
      /* If the page_tree_key matches the branch page_tree_key but is longer,
       * the leaf value is in the next branch node
       */
      if( ( compare_result == 0 )
       && ( first_page_tree_key->data_size > second_page_tree_key->data_size ) )
      {
        result = LIBFDATA_COMPARE_GREATER;
      }
      else
      {
        result = LIBFDATA_COMPARE_LESS_EQUAL;
      }
    }
    else
    {
/* TODO make sure this works */
      result = LIBFDATA_COMPARE_EQUAL;
    }
  }
  else if( second_page_tree_key->type == LIBESEDB_KEY_TYPE_LEAF )
  {
    if( compare_result < 0 )
    {
      result = LIBFDATA_COMPARE_LESS;
    }
    else if( first_page_tree_key->data_size < second_page_tree_key->data_size )
    {
      result = LIBFDATA_COMPARE_LESS;
    }
    else if( first_page_tree_key->data_size > second_page_tree_key->data_size )
    {
      result = LIBFDATA_COMPARE_GREATER;
    }
    else
    {
      result = LIBFDATA_COMPARE_EQUAL;
    }
  }
#if defined( HAVE_DEBUG_OUTPUT )
  if( libcnotify_verbose != 0 )
  {
    libcnotify_printf(
     "%s: result\t\t\t\t\t: ",
     function );

    switch( result )
    {
      case LIBFDATA_COMPARE_EQUAL:
        libcnotify_printf(
         "equal" );
        break;

      case LIBFDATA_COMPARE_GREATER:
        libcnotify_printf(
         "greater" );
        break;

      case LIBFDATA_COMPARE_GREATER_EQUAL:
        libcnotify_printf(
         "greater equal" );
        break;

      case LIBFDATA_COMPARE_LESS:
        libcnotify_printf(
         "less" );
        break;

      case LIBFDATA_COMPARE_LESS_EQUAL:
        libcnotify_printf(
         "less equal" );
        break;

      default:
        libcnotify_printf(
         "unknown" );
        break;
    }
    if( is_flexible_match != 0 )
    {
      libcnotify_printf(
       " (is flexible match)" );
    }
    libcnotify_printf(
     "\n" );

    libcnotify_printf(
     "\n" );
  }
#endif /* defined( HAVE_DEBUG_OUTPUT ) */

  return( result );
}


Coverage Report

Created: 2026-01-13 07:09

Line	Count	Source
1		/*
2		* Page tree key functions
3		*
4		* Copyright (C) 2009-2025, 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 "libesedb_definitions.h"
27		#include "libesedb_libcerror.h"
28		#include "libesedb_libcnotify.h"
29		#include "libesedb_libfcache.h"
30		#include "libesedb_libfdata.h"
31		#include "libesedb_page_tree_key.h"
32
33		/* Creates a page tree key
34		* Make sure the value page_tree_key is referencing, is set to NULL
35		* Returns 1 if successful or -1 on error
36		*/
37		int libesedb_page_tree_key_initialize(
38		libesedb_page_tree_key_t **page_tree_key,
39		libcerror_error_t **error )
40	0	{
41	0	static char *function = "libesedb_page_tree_key_initialize";
42
43	0	if( page_tree_key == NULL )
44	0	{
45	0	libcerror_error_set(
46	0	error,
47	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
48	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
49	0	"%s: invalid page tree key.",
50	0	function );
51
52	0	return( -1 );
53	0	}
54	0	if( *page_tree_key != NULL )
55	0	{
56	0	libcerror_error_set(
57	0	error,
58	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
59	0	LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
60	0	"%s: invalid page tree key value already set.",
61	0	function );
62
63	0	return( -1 );
64	0	}
65	0	*page_tree_key = memory_allocate_structure(
66	0	libesedb_page_tree_key_t );
67
68	0	if( *page_tree_key == NULL )
69	0	{
70	0	libcerror_error_set(
71	0	error,
72	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
73	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
74	0	"%s: unable to create page tree key.",
75	0	function );
76
77	0	goto on_error;
78	0	}
79	0	if( memory_set(
80	0	( *page_tree_key ),
81	0	0,
82	0	sizeof( libesedb_page_tree_key_t ) ) == NULL )
83	0	{
84	0	libcerror_error_set(
85	0	error,
86	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
87	0	LIBCERROR_MEMORY_ERROR_SET_FAILED,
88	0	"%s: unable to clear page tree key.",
89	0	function );
90
91	0	goto on_error;
92	0	}
93	0	return( 1 );
94
95	0	on_error:
96	0	if( *page_tree_key != NULL )
97	0	{
98	0	memory_free(
99	0	*page_tree_key );
100
101	0	*page_tree_key = NULL;
102	0	}
103	0	return( -1 );
104	0	}
105
106		/* Frees a page tree key
107		* Returns 1 if successful or -1 on error
108		*/
109		int libesedb_page_tree_key_free(
110		libesedb_page_tree_key_t **page_tree_key,
111		libcerror_error_t **error )
112	0	{
113	0	static char *function = "libesedb_page_tree_key_free";
114
115	0	if( page_tree_key == NULL )
116	0	{
117	0	libcerror_error_set(
118	0	error,
119	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
120	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
121	0	"%s: invalid page tree key.",
122	0	function );
123
124	0	return( -1 );
125	0	}
126	0	if( *page_tree_key != NULL )
127	0	{
128	0	if( ( *page_tree_key )->data != NULL )
129	0	{
130	0	memory_free(
131	0	( *page_tree_key )->data );
132	0	}
133	0	memory_free(
134	0	*page_tree_key );
135
136	0	*page_tree_key = NULL;
137	0	}
138	0	return( 1 );
139	0	}
140
141		/* Sets data
142		* Returns 1 if successful or -1 on error
143		*/
144		int libesedb_page_tree_key_set_data(
145		libesedb_page_tree_key_t *page_tree_key,
146		const uint8_t *data,
147		size_t data_size,
148		libcerror_error_t **error )
149	0	{
150	0	static char *function = "libesedb_page_tree_key_set_data";
151
152	0	if( page_tree_key == NULL )
153	0	{
154	0	libcerror_error_set(
155	0	error,
156	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
157	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
158	0	"%s: invalid page tree key.",
159	0	function );
160
161	0	return( -1 );
162	0	}
163	0	if( page_tree_key->data != NULL )
164	0	{
165	0	libcerror_error_set(
166	0	error,
167	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
168	0	LIBCERROR_RUNTIME_ERROR_VALUE_ALREADY_SET,
169	0	"%s: invalid page tree key - data already set.",
170	0	function );
171
172	0	return( -1 );
173	0	}
174	0	if( data == NULL )
175	0	{
176	0	libcerror_error_set(
177	0	error,
178	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
179	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
180	0	"%s: invalid data.",
181	0	function );
182
183	0	return( -1 );
184	0	}
185	0	if( data_size > (size_t) MEMORY_MAXIMUM_ALLOCATION_SIZE )
186	0	{
187	0	libcerror_error_set(
188	0	error,
189	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
190	0	LIBCERROR_RUNTIME_ERROR_VALUE_EXCEEDS_MAXIMUM,
191	0	"%s: invalid data size value exceeds maximum allocation size.",
192	0	function );
193
194	0	return( -1 );
195	0	}
196	0	if( data_size > 0 )
197	0	{
198	0	page_tree_key->data = (uint8_t *) memory_allocate(
199	0	sizeof( uint8_t ) * data_size );
200
201	0	if( page_tree_key->data == NULL )
202	0	{
203	0	libcerror_error_set(
204	0	error,
205	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
206	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
207	0	"%s: unable to create data.",
208	0	function );
209
210	0	goto on_error;
211	0	}
212	0	if( memory_copy(
213	0	page_tree_key->data,
214	0	data,
215	0	sizeof( uint8_t ) * data_size ) == NULL )
216	0	{
217	0	libcerror_error_set(
218	0	error,
219	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
220	0	LIBCERROR_MEMORY_ERROR_COPY_FAILED,
221	0	"%s: unable to copy data.",
222	0	function );
223
224	0	goto on_error;
225	0	}
226	0	page_tree_key->data_size = data_size;
227	0	}
228	0	return( 1 );
229
230	0	on_error:
231	0	if( page_tree_key->data != NULL )
232	0	{
233	0	memory_free(
234	0	page_tree_key->data );
235
236	0	page_tree_key->data = NULL;
237	0	}
238	0	page_tree_key->data_size = 0;
239
240	0	return( -1 );
241	0	}
242
243		/* Append data
244		* Returns 1 if successful or -1 on error
245		*/
246		int libesedb_page_tree_key_append_data(
247		libesedb_page_tree_key_t *page_tree_key,
248		const uint8_t *data,
249		size_t data_size,
250		libcerror_error_t **error )
251	0	{
252	0	void *reallocation = NULL;
253	0	static char *function = "libesedb_page_tree_key_append_data";
254
255	0	if( page_tree_key == NULL )
256	0	{
257	0	libcerror_error_set(
258	0	error,
259	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
260	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
261	0	"%s: invalid page tree key.",
262	0	function );
263
264	0	return( -1 );
265	0	}
266	0	if( data == 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 data.",
273	0	function );
274
275	0	return( -1 );
276	0	}
277	0	if( data_size > (size_t) SSIZE_MAX )
278	0	{
279	0	libcerror_error_set(
280	0	error,
281	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
282	0	LIBCERROR_RUNTIME_ERROR_VALUE_EXCEEDS_MAXIMUM,
283	0	"%s: invalid data size value exceeds maximum.",
284	0	function );
285
286	0	return( -1 );
287	0	}
288	0	if( data_size > 0 )
289	0	{
290	0	reallocation = memory_reallocate(
291	0	page_tree_key->data,
292	0	sizeof( uint8_t ) * ( page_tree_key->data_size + data_size ) );
293
294	0	if( reallocation == NULL )
295	0	{
296	0	libcerror_error_set(
297	0	error,
298	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
299	0	LIBCERROR_MEMORY_ERROR_INSUFFICIENT,
300	0	"%s: unable to resize data.",
301	0	function );
302
303	0	return( -1 );
304	0	}
305	0	page_tree_key->data = (uint8_t *) reallocation;
306
307	0	if( memory_copy(
308	0	&( page_tree_key->data[ page_tree_key->data_size ] ),
309	0	data,
310	0	sizeof( uint8_t ) * data_size ) == NULL )
311	0	{
312	0	libcerror_error_set(
313	0	error,
314	0	LIBCERROR_ERROR_DOMAIN_MEMORY,
315	0	LIBCERROR_MEMORY_ERROR_COPY_FAILED,
316	0	"%s: unable to copy data.",
317	0	function );
318
319	0	return( -1 );
320	0	}
321	0	page_tree_key->data_size += data_size;
322	0	}
323	0	return( 1 );
324	0	}
325
326		/* Compares two page tree keys
327		* Returns LIBFDATA_COMPARE_LESS, LIBFDATA_COMPARE_EQUAL, LIBFDATA_COMPARE_GREATER,
328		* LIBFDATA_COMPARE_GREATER_EQUAL if successful or -1 on error
329		*/
330		int libesedb_page_tree_key_compare(
331		libesedb_page_tree_key_t *first_page_tree_key,
332		libesedb_page_tree_key_t *second_page_tree_key,
333		libcerror_error_t **error )
334	0	{
335	0	static char *function = "libesedb_page_tree_key_compare";
336	0	size_t compare_data_size = 0;
337	0	size_t first_page_tree_key_data_index = 0;
338	0	size_t second_page_tree_key_data_index = 0;
339	0	int16_t compare_result = -1;
340	0	uint8_t first_page_tree_key_data = 0;
341	0	int result = -1;
342
343		#if defined( HAVE_DEBUG_OUTPUT )
344		uint8_t *page_tree_key_data = NULL;
345		size_t page_tree_key_data_size = 0;
346		uint8_t is_flexible_match = 0;
347		#endif
348
349	0	if( first_page_tree_key == NULL )
350	0	{
351	0	libcerror_error_set(
352	0	error,
353	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
354	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
355	0	"%s: invalid first page tree key.",
356	0	function );
357
358	0	return( -1 );
359	0	}
360	0	if( first_page_tree_key->data == NULL )
361	0	{
362	0	libcerror_error_set(
363	0	error,
364	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
365	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
366	0	"%s: invalid first page tree key - missing data.",
367	0	function );
368
369	0	return( -1 );
370	0	}
371	0	if( ( first_page_tree_key->type != LIBESEDB_KEY_TYPE_INDEX_VALUE )
372	0	&& ( first_page_tree_key->type != LIBESEDB_KEY_TYPE_LONG_VALUE )
373	0	&& ( first_page_tree_key->type != LIBESEDB_KEY_TYPE_LONG_VALUE_SEGMENT ) )
374	0	{
375	0	libcerror_error_set(
376	0	error,
377	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
378	0	LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
379	0	"%s: unsupported first page tree key type.",
380	0	function );
381
382	0	return( -1 );
383	0	}
384	0	if( second_page_tree_key == NULL )
385	0	{
386	0	libcerror_error_set(
387	0	error,
388	0	LIBCERROR_ERROR_DOMAIN_ARGUMENTS,
389	0	LIBCERROR_ARGUMENT_ERROR_INVALID_VALUE,
390	0	"%s: invalid second page tree key.",
391	0	function );
392
393	0	return( -1 );
394	0	}
395	0	if( ( second_page_tree_key->type != LIBESEDB_KEY_TYPE_BRANCH )
396	0	&& ( second_page_tree_key->type != LIBESEDB_KEY_TYPE_LEAF ) )
397	0	{
398	0	libcerror_error_set(
399	0	error,
400	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
401	0	LIBCERROR_RUNTIME_ERROR_UNSUPPORTED_VALUE,
402	0	"%s: unsupported second page tree key type.",
403	0	function );
404
405	0	return( -1 );
406	0	}
407		#if defined( HAVE_DEBUG_OUTPUT )
408		if( libcnotify_verbose != 0 )
409		{
410		libcnotify_printf(
411		"%s: first page tree key\t\t\t: ",
412		function );
413
414		page_tree_key_data = first_page_tree_key->data;
415		page_tree_key_data_size = first_page_tree_key->data_size;
416
417		while( page_tree_key_data_size > 0 )
418		{
419		if( libcnotify_verbose != 0 )
420		{
421		libcnotify_printf(
422		"%02" PRIx8 " ",
423		*page_tree_key_data );
424		}
425		page_tree_key_data++;
426		page_tree_key_data_size--;
427		}
428		libcnotify_printf(
429		"\n" );
430
431		libcnotify_printf(
432		"%s: first page tree key type\t\t: ",
433		function );
434
435		switch( first_page_tree_key->type )
436		{
437		case LIBESEDB_KEY_TYPE_INDEX_VALUE:
438		libcnotify_printf(
439		"index value" );
440		break;
441
442		case LIBESEDB_KEY_TYPE_LONG_VALUE:
443		libcnotify_printf(
444		"long value" );
445		break;
446
447		case LIBESEDB_KEY_TYPE_LONG_VALUE_SEGMENT:
448		libcnotify_printf(
449		"long value segment" );
450		break;
451
452		default:
453		libcnotify_printf(
454		"unknown" );
455		break;
456		}
457		libcnotify_printf(
458		"\n" );
459
460		libcnotify_printf(
461		"%s: second page tree key\t\t\t: ",
462		function );
463
464		page_tree_key_data = second_page_tree_key->data;
465		page_tree_key_data_size = second_page_tree_key->data_size;
466
467		while( page_tree_key_data_size > 0 )
468		{
469		if( libcnotify_verbose != 0 )
470		{
471		libcnotify_printf(
472		"%02" PRIx8 " ",
473		*page_tree_key_data );
474		}
475		page_tree_key_data++;
476		page_tree_key_data_size--;
477		}
478		libcnotify_printf(
479		"\n" );
480
481		libcnotify_printf(
482		"%s: second page tree key type\t\t: ",
483		function );
484
485		switch( second_page_tree_key->type )
486		{
487		case LIBESEDB_KEY_TYPE_BRANCH:
488		libcnotify_printf(
489		"branch" );
490		break;
491
492		case LIBESEDB_KEY_TYPE_LEAF:
493		libcnotify_printf(
494		"leaf" );
495		break;
496
497		default:
498		libcnotify_printf(
499		"unknown" );
500		break;
501		}
502		libcnotify_printf(
503		"\n" );
504		}
505		#endif /* defined( HAVE_DEBUG_OUTPUT ) */
506
507		/* Check if the page tree key is empty, therefore has no upper bound
508		* and thus the first page tree key will be greater than the second page tree key
509		*/
510	0	if( second_page_tree_key->data_size > 0 )
511	0	{
512	0	if( second_page_tree_key->data == NULL )
513	0	{
514	0	libcerror_error_set(
515	0	error,
516	0	LIBCERROR_ERROR_DOMAIN_RUNTIME,
517	0	LIBCERROR_RUNTIME_ERROR_VALUE_MISSING,
518	0	"%s: invalid second page tree key - missing data.",
519	0	function );
520
521	0	return( -1 );
522	0	}
523	0	if( first_page_tree_key->data_size <= second_page_tree_key->data_size )
524	0	{
525	0	compare_data_size = first_page_tree_key->data_size;
526	0	}
527	0	else
528	0	{
529	0	compare_data_size = second_page_tree_key->data_size;
530	0	}
531		#if defined( HAVE_DEBUG_OUTPUT )
532		is_flexible_match = 0;
533		#endif
534
535		/* The long value page_tree_key is stored reversed
536		*/
537	0	if( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE )
538	0	{
539	0	first_page_tree_key_data_index = first_page_tree_key->data_size - 1;
540	0	}
541	0	else
542	0	{
543	0	first_page_tree_key_data_index = 0;
544	0	}
545	0	for( second_page_tree_key_data_index = 0;
546	0	second_page_tree_key_data_index < compare_data_size;
547	0	second_page_tree_key_data_index++ )
548	0	{
549	0	first_page_tree_key_data = first_page_tree_key->data[ first_page_tree_key_data_index ];
550
551	0	if( ( first_page_tree_key->type == LIBESEDB_KEY_TYPE_INDEX_VALUE )
552	0	&& ( second_page_tree_key->type == LIBESEDB_KEY_TYPE_LEAF ) )
553	0	{
554		/* TODO does not hold for branch page_tree_keys in Win XP search database */
555	0	if( ( first_page_tree_key_data_index == 1 )
556	0	&& ( ( first_page_tree_key_data & 0x80 ) != 0 )
557	0	&& ( ( first_page_tree_key_data & 0x7f ) == second_page_tree_key->data[ second_page_tree_key_data_index ] ) )
558	0	{
559	0	first_page_tree_key_data &= 0x7f;
560
561		#if defined( HAVE_DEBUG_OUTPUT )
562		is_flexible_match = 1;
563		#endif
564	0	}
565	0	}
566	0	compare_result = (int16_t) first_page_tree_key_data - (int16_t) second_page_tree_key->data[ second_page_tree_key_data_index ];
567
568	0	if( compare_result != 0 )
569	0	{
570	0	break;
571	0	}
572	0	if( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE )
573	0	{
574	0	first_page_tree_key_data_index--;
575	0	}
576	0	else
577	0	{
578	0	first_page_tree_key_data_index++;
579	0	}
580	0	}
581	0	}
582	0	if( compare_result > 0 )
583	0	{
584	0	result = LIBFDATA_COMPARE_GREATER;
585	0	}
586	0	else if( second_page_tree_key->type == LIBESEDB_KEY_TYPE_BRANCH )
587	0	{
588	0	if( first_page_tree_key->type == LIBESEDB_KEY_TYPE_INDEX_VALUE )
589	0	{
590		/* If the page_tree_key exactly matches the branch page_tree_key,
591		* the leaf value is in the next branch node
592		*/
593	0	if( compare_result == 0 )
594	0	{
595	0	result = LIBFDATA_COMPARE_GREATER;
596	0	}
597	0	else
598	0	{
599	0	result = LIBFDATA_COMPARE_EQUAL;
600	0	}
601	0	}
602	0	else if( ( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE )
603	0	\|\| ( first_page_tree_key->type == LIBESEDB_KEY_TYPE_LONG_VALUE_SEGMENT ) )
604	0	{
605		/* If the page_tree_key matches the branch page_tree_key but is longer,
606		* the leaf value is in the next branch node
607		*/
608	0	if( ( compare_result == 0 )
609	0	&& ( first_page_tree_key->data_size > second_page_tree_key->data_size ) )
610	0	{
611	0	result = LIBFDATA_COMPARE_GREATER;
612	0	}
613	0	else
614	0	{
615	0	result = LIBFDATA_COMPARE_LESS_EQUAL;
616	0	}
617	0	}
618	0	else
619	0	{
620		/* TODO make sure this works */
621	0	result = LIBFDATA_COMPARE_EQUAL;
622	0	}
623	0	}
624	0	else if( second_page_tree_key->type == LIBESEDB_KEY_TYPE_LEAF )
625	0	{
626	0	if( compare_result < 0 )
627	0	{
628	0	result = LIBFDATA_COMPARE_LESS;
629	0	}
630	0	else if( first_page_tree_key->data_size < second_page_tree_key->data_size )
631	0	{
632	0	result = LIBFDATA_COMPARE_LESS;
633	0	}
634	0	else if( first_page_tree_key->data_size > second_page_tree_key->data_size )
635	0	{
636	0	result = LIBFDATA_COMPARE_GREATER;
637	0	}
638	0	else
639	0	{
640	0	result = LIBFDATA_COMPARE_EQUAL;
641	0	}
642	0	}
643		#if defined( HAVE_DEBUG_OUTPUT )
644		if( libcnotify_verbose != 0 )
645		{
646		libcnotify_printf(
647		"%s: result\t\t\t\t\t: ",
648		function );
649
650		switch( result )
651		{
652		case LIBFDATA_COMPARE_EQUAL:
653		libcnotify_printf(
654		"equal" );
655		break;
656
657		case LIBFDATA_COMPARE_GREATER:
658		libcnotify_printf(
659		"greater" );
660		break;
661
662		case LIBFDATA_COMPARE_GREATER_EQUAL:
663		libcnotify_printf(
664		"greater equal" );
665		break;
666
667		case LIBFDATA_COMPARE_LESS:
668		libcnotify_printf(
669		"less" );
670		break;
671
672		case LIBFDATA_COMPARE_LESS_EQUAL:
673		libcnotify_printf(
674		"less equal" );
675		break;
676
677		default:
678		libcnotify_printf(
679		"unknown" );
680		break;
681		}
682		if( is_flexible_match != 0 )
683		{
684		libcnotify_printf(
685		" (is flexible match)" );
686		}
687		libcnotify_printf(
688		"\n" );
689
690		libcnotify_printf(
691		"\n" );
692		}
693		#endif /* defined( HAVE_DEBUG_OUTPUT ) */
694
695	0	return( result );
696	0	}
697