/*

    File: godmode.c

    Copyright (C) 1998-2007 Christophe GRENIER <grenier@cgsecurity.org>
  
    This software is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 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 General Public License along
    with this program; if not, write the Free Software Foundation, Inc., 51
    Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

 */
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
 
#include <ctype.h>      /* tolower */
#ifdef HAVE_STDLIB_H
#include <stdlib.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#endif
#include "types.h"
#include "common.h"
#include "fnctdsk.h"
#include "analyse.h"
#include "lang.h"
#include "godmode.h"
#include "testdisk.h"
#include "fat.h"
#include "ext2.h"
#include "intrf.h"
#include "intrfn.h"
#include "intrface.h"
#include "md.h"
#include "adv.h"
#include "ntfs.h"
#include "next.h"
#include "log.h"

#define RO 1
#define RW 0
#define MAX_SEARCH_LOCATION 1024
extern const arch_fnct_t arch_i386;
extern const arch_fnct_t arch_mac;
extern const arch_fnct_t arch_none;
extern const arch_fnct_t arch_sun;
static void align_structure(const disk_t *disk_car, list_part_t *list_part,const unsigned int location_boundary);
static list_part_t *reduce_structure(list_part_t *list_part);
static int use_backup(disk_t *disk_car, const list_part_t *list_part, const int debug,const int dump_ind, const unsigned int expert, char**current_cmd);
static int interface_part_bad(disk_t *disk_car, list_part_t *list_part_bad, char **current_cmd);
static int interface_part_bad_log(disk_t *disk_car,list_part_t *list_part_bad);
static void warning_geometry(disk_t *disk_car, const unsigned int recommanded_heads_per_cylinder, char **current_cmd);
static void ask_mbr_order_i386(disk_t *disk_car,list_part_t *list_part);
static list_part_t *add_ext_part_i386(disk_t *disk_car, list_part_t *list_part, const int max_ext, const int align,const int debug);
static unsigned int tab_insert(uint64_t *tab, uint64_t offset, unsigned int tab_nbr);
/* Optimization */
static inline uint64_t CHS2offset_inline(const disk_t *disk_car,const CHS_t*CHS);
static list_part_t *search_part(disk_t *disk_car, const list_part_t *list_part_org, const int debug, const int dump_ind, const int fast_mode, const int interface, const int search_vista_part, char **current_cmd);
static inline void offset2CHS_inline(const disk_t *disk_car,const uint64_t offset, CHS_t*CHS);

static inline void offset2CHS_inline(const disk_t *disk_car,const uint64_t offset, CHS_t*CHS)
{
  uint64_t pos=offset/disk_car->sector_size;
  CHS->sector=(pos%disk_car->CHS.sector)+1;
  pos/=disk_car->CHS.sector;
  CHS->head=pos%(disk_car->CHS.head+1);
  CHS->cylinder=pos/(disk_car->CHS.head+1);
}

static inline uint64_t CHS2offset_inline(const disk_t *disk_car,const CHS_t*CHS)
{ return (((uint64_t)CHS->cylinder*(disk_car->CHS.head+1)+CHS->head)*disk_car->CHS.sector+CHS->sector-1)*disk_car->sector_size;
}
/* Optimization end */

static void align_structure(const disk_t *disk_car, list_part_t *list_part, const unsigned int location_boundary)
{
  list_part_t *element;
  for(element=list_part;element!=NULL;element=element->next)
  {
    uint64_t partition_end;
    partition_end=(element->part->part_offset+element->part->part_size-1+location_boundary-1)/location_boundary*location_boundary-1;
    element->part->part_size=partition_end-element->part->part_offset+1;
  }
}

void only_one_bootable( list_part_t *list_part, list_part_t *part_boot)
{
  list_part_t *element;
  if(part_boot->part->status==STATUS_PRIM_BOOT)
    for(element=list_part;element!=NULL;element=element->next)
    {
      if((element!=part_boot)&&(element->part->status==STATUS_PRIM_BOOT))
	element->part->status=STATUS_PRIM;
    }
}

static int interface_part_bad(disk_t *disk_car, list_part_t *list_part, char **current_cmd)
{
  int quit=0;
  int offset=0;
  int pos_num=0;
  uint64_t disk_size=disk_car->disk_size;
  list_part_t *pos=list_part;
  if(list_part==NULL)
    return 1;
  {
    list_part_t *parts;
    for(parts=list_part;parts!=NULL;parts=parts->next)
    {
      if(disk_size<parts->part->part_offset+parts->part->part_size-1)
	disk_size=parts->part->part_offset+parts->part->part_size-1;
    }
  }
  aff_copy(stdscr);
  wmove(stdscr,4,0);
  wdoprintf(stdscr,"%s",disk_car->description(disk_car));
  wmove(stdscr,6,0);
  {
    char buffer_disk_size[100];
    char buffer_disk_size_found[100];
    wdoprintf(stdscr,"The harddisk (%s) seems too small! (< %s)",
	size_to_unit(disk_car->disk_size,buffer_disk_size), size_to_unit(disk_size,buffer_disk_size_found));
  }
  wmove(stdscr,7,0);
  wdoprintf(stdscr,"Check the harddisk size: HD jumpers settings, BIOS detection...");
#if defined(__CYGWIN__) || defined(__MINGW32__)
  if(disk_car->disk_size<=((uint64_t)1<<(28-1)) && disk_size>=((uint64_t)1<<(28-1)))
  {
    wmove(stdscr,8,0);
    wdoprintf(stdscr,"Hint: update Windows to support LBA48 (minimum: W2K SP4 or XP SP1)");
  }
#endif
  wmove(stdscr,9,0);
  if(list_part->next==NULL)
  {
    wdoprintf(stdscr,"The following partition can't be recovered:");
  } else {
    wdoprintf(stdscr,"The following partitions can't be recovered:");
  }
  mvwaddstr(stdscr,10,0,msg_PART_HEADER);
  wmove(stdscr,22,0);
  wattrset(stdscr, A_REVERSE);
  wdoprintf(stdscr,"[ Continue ]");
  wattroff(stdscr, A_REVERSE);
  do
  {
    int i;
    int car;
    list_part_t *parts;
    for(i=0,parts=list_part;(parts!=NULL) && (i<offset);parts=parts->next,i++);
    for(i=offset;(parts!=NULL) &&((i-offset)<INTER_BAD_PART);i++,parts=parts->next)
    {
      wmove(stdscr,11+i-offset,0);
      wclrtoeol(stdscr);	/* before addstr for BSD compatibility */
      if(parts==pos)
      {
	char buffer_part_size[100];
	wattrset(stdscr, A_REVERSE);
	aff_part(stdscr,AFF_PART_NONL,disk_car,parts->part);
	wattroff(stdscr, A_REVERSE);
	wmove(stdscr,24,0);
	wclrtoeol(stdscr);	/* before addstr for BSD compatibility */
	if(parts->part->info[0]!='\0')
	{
	  wdoprintf(stdscr,"%s, ",parts->part->info);
	}
	wdoprintf(stdscr,"%s",size_to_unit(parts->part->part_size,buffer_part_size));
      } else
      {
	aff_part(stdscr,AFF_PART_NONL,disk_car,parts->part);
      }
    }
    wrefresh(stdscr);
    if(*current_cmd!=NULL)
      car='q';
    else
      car=wgetch(stdscr);
    switch(car)
    {
      case 'q':
      case '\r':
      case '\n':
      case KEY_ENTER:
#ifdef PADENTER
      case PADENTER:
#endif
      case 'M':
	quit=1;
	break;
      case KEY_UP:
	if(list_part!=NULL)
	{
	  if(pos->prev!=NULL)
	  {
	    pos=pos->prev;
	    pos_num--;
	  }
	  if(pos_num<offset)
	    offset--;
	}
	break;
      case KEY_DOWN:
	if(list_part!=NULL)
	{
	  if(pos->next!=NULL)
	  {
	    pos=pos->next;
	    pos_num++;
	  }
	  if(pos_num>=offset+INTER_BAD_PART)
	    offset++;
	}
	break;
      case KEY_PPAGE:
	if(list_part!=NULL)
	{
	  for(i=0;(i<INTER_BAD_PART) && (pos->prev!=NULL);i++)
	  {
	    pos=pos->prev;
	    pos_num--;
	    if(pos_num<offset)
	      offset--;
	  }
	}
	break;
      case KEY_NPAGE:
	if(list_part!=NULL)
	{
	  for(i=0;(i<INTER_BAD_PART) && (pos->next!=NULL);i++)
	  {
	    pos=pos->next;
	    pos_num++;
	    if(pos_num>=offset+INTER_BAD_PART)
	      offset++;
	  }
	}
	break;
      default:
	break;
    }
  } while(quit==0);
  return 0;
}

static int interface_part_bad_log(disk_t *disk_car,list_part_t *list_part)
{
  uint64_t disk_size=disk_car->disk_size;
  if(list_part==NULL)
    return 1;
  {
    list_part_t *parts;
    for(parts=list_part;parts!=NULL;parts=parts->next)
    {
      if(disk_size<parts->part->part_offset+parts->part->part_size-1)
	disk_size=parts->part->part_offset+parts->part->part_size-1;
    }
  }
  log_warning("%s\n",disk_car->description(disk_car));
  log_warning("Check the harddisk size: HD jumpers settings, BIOS detection...\n");
#if defined(__CYGWIN__) || defined(__MINGW32__)
  if(disk_car->disk_size<=((uint64_t)1<<(28-1)) && disk_size>=((uint64_t)1<<(28-1)))
  {
    log_warning("Hint: update Windows to support LBA48 (minimum: W2K SP4 or XP SP1)");
  }
#endif
  {
    char buffer_disk_size[100];
    char buffer_disk_size_found[100];
    log_warning("The harddisk (%s) seems too small! (< %s)\n",
	size_to_unit(disk_car->disk_size,buffer_disk_size), size_to_unit(disk_size,buffer_disk_size_found));
  }
  if(list_part->next==NULL)
  {
    log_warning("The following partition can't be recovered:\n");
  } else {
    log_warning("The following partitions can't be recovered:\n");
  }
  {
    list_part_t *parts;
    for(parts=list_part;parts!=NULL;parts=parts->next)
      log_partition(disk_car,parts->part);
  }
  return 0;
}

static void warning_geometry(disk_t *disk_car, const unsigned int recommanded_heads_per_cylinder, char**current_cmd)
{
  int quit=0;
  aff_copy(stdscr);
  wmove(stdscr,4,0);
  wdoprintf(stdscr,"%s",disk_car->description(disk_car));
  wmove(stdscr,6,0);
  log_warning("Warning: the current number of heads per cylinder is %u but the correct value may be %u.\n",disk_car->CHS.head+1,recommanded_heads_per_cylinder);
  wdoprintf(stdscr,"Warning: the current number of heads per cylinder is %u",disk_car->CHS.head+1);
  wmove(stdscr,7,0);
  wdoprintf(stdscr,"but the correct value may be %u.",recommanded_heads_per_cylinder);
  wmove(stdscr,8,0);
  wdoprintf(stdscr,"You can use the Geometry menu to change this value.");
  wmove(stdscr,9,0);
  wdoprintf(stdscr,"It's something to try if");
  wmove(stdscr,10,0);
  wdoprintf(stdscr,"- some partitions are not found by TestDisk");
  wmove(stdscr,11,0);
  wdoprintf(stdscr,"- or the partition table can not be written because partitions overlaps.");
  wmove(stdscr,22,0);
  wattrset(stdscr, A_REVERSE);
  wdoprintf(stdscr,"[ Continue ]");
  wattroff(stdscr, A_REVERSE);
  wrefresh(stdscr);
  if(*current_cmd!=NULL)
    return;
  do
  {
    int car;
    car=wgetch(stdscr);
    switch(car)
    {
      case 'q':
      case '\r':
      case '\n':
      case KEY_ENTER:
#ifdef PADENTER
      case PADENTER:
#endif
      case 'M':
	quit=1;
	break;
      default:
	break;
    }
  } while(quit==0);
}

static unsigned int tab_insert(uint64_t *tab, uint64_t offset, unsigned int tab_nbr)
{
  if(tab_nbr<MAX_SEARCH_LOCATION-1)
  {
    unsigned int i,j;
    for(i=0;i<tab_nbr && tab[i]<=offset;i++);
    tab_nbr++;
    for(j=tab_nbr;j>i;j--)
      tab[j]=tab[j-1];
    tab[i]=offset;
  }
  return tab_nbr;
}

/*
   Intel
   - Display CHS
   - Align: following configuration
   - MinPartOffset: 512
   - Geometry: care
   Mac
   - Display S
   - Align to 4k (not required)
   - MinPartOffset: 512
   - Geometry: don't care
   None
   - Display S
   - Align: none
   - MinPartOffset: 0
   - Geometry: don't care
   Sun
   - Display C
   - Align to C boundaries
   - MinPartOffset: 512
   - Partition need to have H=0, S=1
   - Geometry: required
   XBox
   - Display S
   - Align: none
   - MinPartOffset: 0x800
   - Geometry: don't care
*/

static list_part_t *search_part(disk_t *disk_car, const list_part_t *list_part_org, const int debug, const int dump_ind, const int fast_mode, const int interface, const int search_vista_part, char **current_cmd)
{
  unsigned char *buffer_disk;
  /* TODO use circular buffer for try_offset and try_offset_raid */
  uint64_t try_offset[MAX_SEARCH_LOCATION];
  uint64_t try_offset_raid[MAX_SEARCH_LOCATION];
  uint64_t search_location;
  unsigned int try_offset_nbr=0;
  unsigned int try_offset_raid_nbr=0;
  unsigned int old_cylinder=0;
  unsigned int location_boundary;
  int ind_stop=0;
  list_part_t *list_part=NULL;
  list_part_t *list_part_bad=NULL;
  partition_t *partition=partition_new();
  buffer_disk=(unsigned char*)MALLOC(16*DEFAULT_SECTOR_SIZE);
  {
    /* Will search for partition at current known partition location */
    const list_part_t *element;
    for(element=list_part_org;element!=NULL;element=element->next)
    {
      try_offset_nbr=tab_insert(try_offset,element->part->part_offset,try_offset_nbr);
    }
  }

  if(interface!=0)
  {
    wmove(stdscr,22,0);
    wattrset(stdscr, A_REVERSE);
    waddstr(stdscr,"  Stop  ");
    wattroff(stdscr, A_REVERSE);
  }
  aff_buffer(BUFFER_RESET,"Q");
  log_info("\nsearch_part()\n");
  log_info("%s\n",disk_car->description(disk_car));
  if(disk_car->arch==&arch_i386)
  {
      search_location=disk_car->sector_size;
      location_boundary=disk_car->sector_size;
  }
  else if(disk_car->arch==&arch_mac)
  {
      search_location=4096;
      location_boundary=4096;
  }
  else if(disk_car->arch==&arch_sun)
  {
      search_location=(disk_car->CHS.head+1) * disk_car->CHS.sector * disk_car->sector_size;
      location_boundary=(disk_car->CHS.head+1) * disk_car->CHS.sector * disk_car->sector_size;
  }
  else
  {
      search_location=0;
      location_boundary=disk_car->sector_size;
  }
  /* Not every sector will be examined */
  search_location_init(disk_car, location_boundary, fast_mode, search_vista_part);
  /* Scan the disk */
  while(ind_stop==0 && search_location<disk_car->disk_real_size)
  {
    unsigned int sector_inc=0;
    static CHS_t start;
    offset2CHS_inline(disk_car,search_location,&start);
    if(old_cylinder!=start.cylinder && interface!=0 && (disk_car->CHS.head!=0 || (start.cylinder & 0xFFF)==0))
    {
      old_cylinder=start.cylinder;
      wmove(stdscr,ANALYSE_Y,ANALYSE_X);
      wclrtoeol(stdscr);
      wdoprintf(stdscr,"Analyse cylinder %5u/%u: %02u%%",start.cylinder,disk_car->CHS.cylinder,(unsigned int)((uint64_t)start.cylinder*100/(disk_car->CHS.cylinder+1)));
      wrefresh(stdscr);
      ind_stop|=check_enter_or_s(stdscr);
    }
    {
      int test_nbr=0;
      int search_now=0;
      int search_now_raid=0;
      while(try_offset_nbr>0 && try_offset[0]<=search_location)
      {
	unsigned int j;
	if(try_offset[0]==search_location)
	  search_now=1;
	for(j=0;j<try_offset_nbr-1;j++)
	  try_offset[j]=try_offset[j+1];
	try_offset_nbr--;
      }
      /* PC x/0/1 x/1/1 x/2/1 */
      /* PC Vista 2048 sectors unit */
      if(disk_car->arch==&arch_i386)
	search_now|= (start.sector==1 && fast_mode>1) ||
	  (start.sector==1 && start.head<=2) ||
	  (search_vista_part>0 && search_location%(2048*512)==0);
      else
	search_now|= (search_location%location_boundary==0);
      while(try_offset_raid_nbr>0 && try_offset_raid[0]<=search_location)
      {
	unsigned int j;
	if(try_offset_raid[0]==search_location)
	  search_now_raid=1;
	for(j=0;j<try_offset_raid_nbr-1;j++)
	  try_offset_raid[j]=try_offset_raid[j+1];
	try_offset_raid_nbr--;
      }
      do
      {
	int res=0;
	partition->part_size=(uint64_t)0;
	partition->part_offset=search_location;
	if(res<=0 && test_nbr==0)
	{
	  if(search_now>0)
	    res=search_type_2(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(res<=0 && test_nbr==1)
	{
	  if(search_now_raid>0 || fast_mode>1)
	  { /* Search Linux software RAID */
	    if(disk_car->read(disk_car,8*DEFAULT_SECTOR_SIZE, buffer_disk, search_location)!=0)
	    {
	      res=-1;
	    }
	    else
	    {
	      if(recover_MD(disk_car,(const struct mdp_superblock_s*)buffer_disk,partition,debug,dump_ind)==0)
		res=1;
	      else
		res=0;
	    }
	  }
	  test_nbr++;
	}
	if(res<=0 && test_nbr==2)
	{
	  if(fast_mode==0)
	    test_nbr=6;
	  else
	  {
	    if((disk_car->arch==&arch_i386 &&
		  ((start.sector==7 && (start.head<=2 || fast_mode>1)) ||
		   (search_vista_part>0 && search_location%(2048*512)==(7-1)*512))) ||
		(disk_car->arch!=&arch_i386 && (search_location%location_boundary==(7-1)*512)))
	      res=search_FAT_backup(buffer_disk,disk_car,partition,debug,dump_ind);
	    test_nbr++;
	  }
	}
	if(res<=0 && test_nbr==3)
	{
	  if((disk_car->arch==&arch_i386 &&
		  ((start.sector==disk_car->CHS.sector && (start.head==disk_car->CHS.head || fast_mode>1)) ||
		   (search_vista_part>0 && search_location%(2048*512)==(2048-1)*512))) ||
		(disk_car->arch!=&arch_i386 && search_location%location_boundary==(location_boundary-512) &&
		 search_location>0))
	    res=search_NTFS_backup(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(res<=0 && test_nbr==4)
	{
	  if((disk_car->arch==&arch_i386 &&
		  ((start.sector==disk_car->CHS.sector && (start.head==disk_car->CHS.head || fast_mode>1)) ||
		   (search_vista_part>0 && search_location%(2048*512)==(2048-1)*512))) ||
		(disk_car->arch!=&arch_i386 && search_location%location_boundary==(location_boundary-512) &&
		 search_location>0))
	    res=search_HFS_backup(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(res<=0 && test_nbr==5)
	{
	  int s_log_block_size;
	  /* try backup superblock */
	  /* It must be in fast_mode>0 because it can hide otherwise other partition type */
	  /* Block size: 1024, 2048 or 4096 bytes (8192 bytes on Alpha systems) */
	  /* From e2fsprogs-1.34/lib/ext2fs/initialize.c: set_field(s_first_data_block, super->s_log_block_size ? 0 : 1); */
	  /* Assumes that TestDisk is not running under Alpha and s_blocks_per_group=8 * block size */
	  for(s_log_block_size=0;(s_log_block_size<=2)&&(res<=0);s_log_block_size++)
	  {
	    /* sparse superblock feature: The groups chosen are 0, 1 and powers of 3, 5 and 7. */
	    /* Checking group 3 */
	    const uint64_t hd_offset=3*(EXT2_MIN_BLOCK_SIZE<<s_log_block_size)*8*(EXT2_MIN_BLOCK_SIZE<<s_log_block_size)+(s_log_block_size==0?2*DEFAULT_SECTOR_SIZE:0);
	    if(search_location>=hd_offset)
	    {
	      CHS_t start_ext2;
	      offset2CHS_inline(disk_car,search_location-hd_offset,&start_ext2);
	      if((disk_car->arch==&arch_i386 && start_ext2.sector==1 &&  (start_ext2.head<=2 || fast_mode>1)) ||
		  (disk_car->arch!=&arch_i386 && search_location%location_boundary==0))
	      {
		if(disk_car->read(disk_car,1024, buffer_disk, search_location)==0)
		{
		  const struct ext2_super_block *sb=(const struct ext2_super_block*)buffer_disk;
		  if(le16(sb->s_block_group_nr)>0)
		  {
		    if(recover_EXT2(disk_car,sb,partition,debug,dump_ind)==0)
		      res=1;
		  }
		}
		else
		{
		  res=-1;
		}
	      }
	    }
	  }
	  test_nbr++;
	}
	if(res<=0 && test_nbr==6)
	{
	  if(search_now>0)
	  {
	    res=search_type_1(buffer_disk, disk_car,partition,debug,dump_ind);
	    test_nbr++;
	  }
	  else
	    test_nbr=11;
	}
	if(res<=0 && test_nbr==7)
	{
	  res=search_type_0(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(res<=0 && test_nbr==8)
	{
	  /* Try to catch disklabel before BSD FFS partition */
	  res=search_type_16(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(res<=0 && test_nbr==9)
	{
	  res=search_type_64(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(res<=0 && test_nbr==10)
	{
	  /* read to fill the cache */
	  disk_car->read(disk_car,8*DEFAULT_SECTOR_SIZE, buffer_disk, partition->part_offset+(63+16)*512);
	  /* Try to catch disklabel before BSD FFS partition */
	  res=search_type_128(buffer_disk,disk_car,partition,debug,dump_ind);
	  test_nbr++;
	}
	if(test_nbr==11)
	{
	  sector_inc=1;
	  test_nbr=0;
	}
	if(res<0)
	{
	  if(interface!=0)
	  {
	    wmove(stdscr,ANALYSE_Y+1,ANALYSE_X);
	    wclrtoeol(stdscr);
	    wdoprintf(stdscr,msg_READ_ERROR_AT, start.cylinder,start.head,start.sector,(unsigned long)(partition->part_offset/disk_car->sector_size));
	  }
	}
	else if(res>0)
	{
	  partition->status=STATUS_DELETED;
	  log_partition(disk_car,partition);
	  aff_part_buffer(AFF_PART_SHORT,disk_car,partition);
	  if(interface)
	  {
	    aff_buffer(BUFFER_SHOW,"Q");
	  }
	  if(disk_car->arch->is_part_known(partition)!=0 && partition->part_size>1 && (partition->part_offset>0 || disk_car->arch==&arch_none))
	  {
	    uint64_t pos_fin;
	    pos_fin=partition->part_offset+partition->part_size-1;
	    /* */
	    if(partition->upart_type!=UP_RAID)
	    {
	      unsigned int disk_factor;
	      unsigned int help_factor;
	      unsigned int help_factor_max;
	      const int align=2;
	      CHS_t end;
	      offset2CHS_inline(disk_car,partition->part_offset+partition->part_size-1,&end);
	      if(align>0)
	      {
		end.sector=disk_car->CHS.sector;
		if(align>1)
		  end.head=disk_car->CHS.head;
	      }
	      help_factor_max=((uint64_t)CHS2offset_inline(disk_car, &end)-partition->part_offset+disk_car->sector_size-partition->part_size)/MD_RESERVED_BYTES;
	      if(help_factor_max<3)
		help_factor_max=3;
	      help_factor_max+=MD_MAX_CHUNK_SIZE/MD_RESERVED_BYTES;
	      for(disk_factor=6;disk_factor>=1 && ind_stop==0;disk_factor--)
	      { /* disk_factor=1, detect Raid 0/1 */
		/* disk_factor>1, detect Raid 5 */
		for(help_factor=0;help_factor<=MD_MAX_CHUNK_SIZE/MD_RESERVED_BYTES+3 && ind_stop==0;help_factor++)
		{
		  uint64_t offset=(uint64_t)MD_NEW_SIZE_SECTORS((partition->part_size/disk_factor+help_factor*MD_RESERVED_BYTES-1)/MD_RESERVED_BYTES*MD_RESERVED_BYTES/512)*512;
		  try_offset_raid_nbr=tab_insert(try_offset_raid,partition->part_offset+offset,try_offset_raid_nbr);
		}
	      }
	    }
	    /* */
	    if(pos_fin<=disk_car->disk_size)
	    {
	      {
		partition_t *new_partition=partition_new();
		dup_partition_t(new_partition,partition);
		list_part=insert_new_partition(list_part,new_partition);
		/* Never use new_partition after insert_new_partition, it may have been freed */
	      }
	      {
		uint64_t next_part_offset=partition->part_offset+partition->part_size-1+1;
		uint64_t head_size=disk_car->CHS.sector*disk_car->sector_size;
		try_offset_nbr=tab_insert(try_offset,next_part_offset,try_offset_nbr);
		try_offset_nbr=tab_insert(try_offset,next_part_offset+head_size,try_offset_nbr);
		if(next_part_offset%head_size!=0)
		{
		  try_offset_nbr=tab_insert(try_offset,(next_part_offset+head_size-1)/head_size*head_size,try_offset_nbr);
		  try_offset_nbr=tab_insert(try_offset,(next_part_offset+head_size-1)/head_size*head_size+head_size,try_offset_nbr);
		}
	      }
	      if((fast_mode==0) && (partition->part_offset+partition->part_size-disk_car->sector_size > search_location))
	      {
		search_location=partition->part_offset+partition->part_size-disk_car->sector_size;
		test_nbr=0;
		sector_inc=1;
	      }
	    }
	    else
	    {
	      {
		partition_t *new_partition=partition_new();
		dup_partition_t(new_partition,partition);
		list_part_bad=insert_new_partition(list_part_bad,new_partition);
		/* Never use new_partition after insert_new_partition, it may have been freed */
	      }
	      log_warning("This partition ends after the disk limits. ");
	      if(debug>0)
	      {
		log_warning("(start=%lu, size=%lu, end=%lu, disk end=%lu)\n",
		    (unsigned long)(partition->part_offset/disk_car->sector_size),
		    (unsigned long)(partition->part_size/disk_car->sector_size),
		    (unsigned long)(pos_fin/disk_car->sector_size),
		    (unsigned long)(disk_car->disk_size/disk_car->sector_size));
	      }
	    }
	  }
	  else
	  {
	    if(debug>0)
	    {
	      log_warning("Partition not added.\n");
	    }
	  }
	  partition_reset(partition);
	}
      }
      while(sector_inc==0);
    }
    { /* Optimized "search_location+=disk_car->sector_size;" */
      uint64_t min=search_location_update(search_location);
      if(try_offset_nbr>0 && min>try_offset[0])
	min=try_offset[0];
      if(try_offset_raid_nbr>0 && min>try_offset_raid[0])
	min=try_offset_raid[0];
      if(min==(uint64_t)-1 || min<=search_location)
	search_location+=disk_car->sector_size;
      else
	search_location=min;
    }
  }
  /* Search for NTFS partition near the supposed partition beginning
     given by the NTFS backup boot sector */
  if(fast_mode>0)
  {
    const list_part_t *element;
    for(element=list_part;element!=NULL;element=element->next)
    {
      if(element->part->upart_type==UP_NTFS && element->part->boot_sector!=0)
      {
	unsigned int i;
	for(i=32;i>0;i--)
	{
	  partition->part_size=(uint64_t)0;
	  partition->part_offset=element->part->part_offset - i * disk_car->sector_size;
	  if(disk_car->read(disk_car, DEFAULT_SECTOR_SIZE, buffer_disk, partition->part_offset)==0)
	  {
	    if(recover_NTFS(disk_car,(const struct ntfs_boot_sector*)buffer_disk,partition,debug,dump_ind,0)==0)
	    {
	      partition->status=STATUS_DELETED;
	      if(disk_car->arch->is_part_known(partition)!=0 && partition->part_size>1 &&
		  (partition->part_offset>0 || disk_car->arch==&arch_none) &&
		  partition->part_offset+partition->part_size-1 <= disk_car->disk_size)
	      {
		partition_t *new_partition=partition_new();
		dup_partition_t(new_partition,partition);
		list_part=insert_new_partition(list_part,new_partition);
	      }
	      partition_reset(partition);
	    }
	  }
	}
      }
    }
  }
  free(partition);
  if(ind_stop>0)
    log_info("Search for partition aborted\n");
  if(list_part_bad!=NULL)
  {
    interface_part_bad_log(disk_car,list_part_bad);
    if(interface!=0)
      interface_part_bad(disk_car,list_part_bad,current_cmd);
  }
  delete_list_part(list_part_bad);
  free(buffer_disk);
  return list_part;
}

static void ask_mbr_order_i386(disk_t *disk_car,list_part_t *list_part)
{
  partition_t *table[4];
  partition_t *table2[4];
  int nbr_prim=0;
  int i,pos=0;
  int res;
  int car;
  int quit=0;
  list_part_t *element;
  /* Initialisation */
  aff_copy(stdscr);
  wmove(stdscr,4,0);
  wdoprintf(stdscr,"%s",disk_car->description(disk_car));
  mvwaddstr(stdscr,5,0,msg_MBR_ORDER);
  mvwaddstr(stdscr,6,0,msg_PART_HEADER_LONG);
  for(element=list_part;element!=NULL;element=element->next)
  {
    if((element->part->order>0) && (element->part->order<5))
      table[nbr_prim++]=element->part;
  }
  /* */
  log_info("\nSelect primaries partition\n");
  for(i=0;i<nbr_prim;i++)
      log_partition(disk_car,table[i]);
  /* */
  do
  {
    unsigned int order;
    /* sort table into table2 */
    int part=0;
    res=0;
    for(order=1;order<=4;order++)
    {
      int nbr=0;
      for(i=0;i<nbr_prim;i++)
	if(table[i]->order==order)
	{
	  table2[part++]=table[i];
	  nbr++;
	}
      res|=(nbr>1);
    }
    if(part!=nbr_prim)
    {
      log_critical("\nBUG part %d, nbr_prim %d\n", part, nbr_prim);
    }
    for(i=0;i<nbr_prim;i++)
    {
      wmove(stdscr,5+2+i,0);
      wclrtoeol(stdscr);
      if(i==pos)
	standout();
      aff_part(stdscr,AFF_PART_ORDER,disk_car,table2[i]);
      if(i==pos)
	standend();
    }
    wmove(stdscr,20,0);
    if(res)
      wdoprintf(stdscr,msg_MBR_ORDER_BAD);
    else
      wdoprintf(stdscr,msg_MBR_ORDER_GOOD);
    wrefresh(stdscr);
    car=wgetch(stdscr);
    quit=0;
    switch(car)
    {
      case KEY_UP:
	if(--pos<0)
	  pos=nbr_prim-1;
	break;
      case KEY_DOWN:
	if(++pos>=nbr_prim)
	  pos=0;
	break;
      case KEY_PPAGE:
	pos=0;
	break;
      case KEY_NPAGE:
	pos=nbr_prim-1;
	break;
      case '1':
      case '2':
      case '3':
      case '4':
	table2[pos]->order=car-'0';
	break;
      case KEY_RIGHT:
      case ' ':
      case '+':
	if(++table2[pos]->order>4)
	  table2[pos]->order=1;
	break;
      case KEY_LEFT:
      case '-':
	if(--table2[pos]->order<1)
	  table2[pos]->order=4;
	break;
      case 'q':
      case '\r':
      case '\n':
      case KEY_ENTER:
#ifdef PADENTER
      case PADENTER:
#endif
      case 'M':
	quit=1;
	break;
    }
    wrefresh(stdscr);
  } while(res!=0 || quit==0);
}

static list_part_t *reduce_structure(list_part_t *list_part)
{
  list_part_t *element=list_part;
  list_part_t *prev=NULL;
  while(element)
  {
    list_part_t *next=element->next;
    if(element->part->status==STATUS_DELETED)
    {
      if(prev==NULL)
	list_part=next;
      else
	prev->next=next;
      if(next!=NULL)
	next->prev=prev;
      free(element->part);
      free(element);
    }
    else
      prev=element;
    element=next;
  }
  return list_part;
}

static list_part_t *add_ext_part_i386(disk_t *disk_car, list_part_t *list_part, const int max_ext, const int align, const int debug)
{
  /* list_part need to be sorted! */
  /* All extended partitions of an P_EXTENDX are P_EXTENDED */
  list_part_t *element;
  list_part_t *deb=NULL;
  list_part_t *fin=NULL;
  int nbr_entries=0;
  CHS_t start,end;
  partition_t *new_partition;
  unsigned int order=0;
  for(element=list_part;element!=NULL;)
  {
    if(element->part->status==STATUS_EXT)
    {
      /* remove already existing extended partition */
      list_part_t *next=element->next;
      if(element->prev!=NULL)
	element->prev->next=element->next;
      if(element->next!=NULL)
	element->next->prev=element->prev;
      order=element->part->order;
      if(element==list_part)
	list_part=next;
      free(element->part);
      free(element);
      element=next;
    }
    else
    {
      if(element->part->status==STATUS_LOG)
      {
	if(deb==NULL)
	{
	  deb=element;
	  nbr_entries++;
	}
	fin=element;
      }
      else
	nbr_entries++;
      element=element->next;
    }
  }
  if(deb==NULL)
    return list_part;
  if((nbr_entries==4)||(max_ext!=0))
  {
    if(debug>1)
    {
      log_trace("add_ext_part_i386: max\n");
    }
    if(deb->prev==NULL)
    {
      offset2CHS_inline(disk_car,deb->part->part_offset-1,&start);
      if((align>0) && (start.cylinder>0||start.head>1))
      {
	start.cylinder=0;
	start.head=1;
	start.sector=1;
      }
    }
    else
    {
      start.cylinder=offset2cylinder(disk_car,deb->prev->part->part_offset+deb->prev->part->part_size-1)+1;
      start.head=0;
      start.sector=1;
      if(CHS2offset_inline(disk_car,&start)>=deb->part->part_offset)
      {
	offset2CHS_inline(disk_car,deb->prev->part->part_offset+deb->prev->part->part_size-1+1,&start);
	start.sector=1;
	start.head++;
	if(start.head>=disk_car->CHS.head)
	{
	  start.cylinder++;
	  start.head=0;
	}
	if(CHS2offset_inline(disk_car,&start)>=deb->part->part_offset)
	{
	  offset2CHS_inline(disk_car,deb->prev->part->part_offset+deb->prev->part->part_size-1+1,&start);
	}
      }
    }
    if(fin->next==NULL)
    {
      end.cylinder=disk_car->CHS.cylinder;
      end.head=disk_car->CHS.head;
      end.sector=disk_car->CHS.sector;
    }
    else
    {
      end.cylinder=offset2cylinder(disk_car,fin->next->part->part_offset)-1; /* 8 october 2002 */
      end.head=disk_car->CHS.head;
      end.sector=disk_car->CHS.sector;
      if(CHS2offset_inline(disk_car,&end)<=fin->part->part_offset+fin->part->part_size-1)
      {
	offset2CHS_inline(disk_car,fin->next->part->part_offset-1,&end);
	end.sector=disk_car->CHS.sector;
	if(end.head>0)
	  end.head--;
	else
	{
	  end.cylinder--;
	  end.head=disk_car->CHS.head;
	}
	if(CHS2offset_inline(disk_car,&end)<=fin->part->part_offset+fin->part->part_size-1)
	{
	  offset2CHS_inline(disk_car,fin->next->part->part_offset-1,&end);
	}
      }
    }
  }
  else
  {
    if(debug>1)
    {
      log_trace("add_ext_part_i386: min\n");
    }
    offset2CHS_inline(disk_car,deb->part->part_offset-1,&start);
    start.sector=1;
    if(deb->prev && CHS2offset_inline(disk_car,&start)<=deb->prev->part->part_offset+deb->prev->part->part_size-1)
    {
      offset2CHS_inline(disk_car,deb->part->part_offset-1,&start);
      start.sector=1;
      if(CHS2offset_inline(disk_car,&start)<=deb->prev->part->part_offset+deb->prev->part->part_size-1)
      {
	offset2CHS_inline(disk_car,deb->part->part_offset-1,&start);
      }
    }
    offset2CHS_inline(disk_car,fin->part->part_offset+fin->part->part_size-1,&end);
    end.head=disk_car->CHS.head;
    end.sector=disk_car->CHS.sector;
    if(fin->next && CHS2offset_inline(disk_car,&end)>=fin->next->part->part_offset)
    {
      offset2CHS_inline(disk_car,fin->part->part_offset+fin->part->part_size-1,&end);
      end.sector=disk_car->CHS.sector;
    }
    if(fin->next && CHS2offset_inline(disk_car,&end)>=fin->next->part->part_offset)
    {
      offset2CHS_inline(disk_car,fin->part->part_offset+fin->part->part_size-1,&end);
    }
  }
  new_partition=partition_new();
  new_partition->order=order;
  new_partition->part_type_i386=(end.cylinder>1023?P_EXTENDX:P_EXTENDED);
  new_partition->status=STATUS_EXT;
  new_partition->part_offset=CHS2offset_inline(disk_car,&start);
  new_partition->part_size=(uint64_t)CHS2offset_inline(disk_car,&end)-new_partition->part_offset+disk_car->sector_size;
  return insert_new_partition(list_part, new_partition);
}

static int use_backup(disk_t *disk_car, const list_part_t *list_part, const int debug,const int dump_ind, const unsigned int expert, char**current_cmd)
{
  const list_part_t *element;
  if(debug>1)
  {
    log_trace("use_backup\n");
  }
  for(element=list_part;element!=NULL;element=element->next)
  {
    if(element->part->boot_sector!=0)
    {
      switch(element->part->upart_type)
      {
	case UP_FAT32:
	  fat32_boot_sector(disk_car, element->part, debug, dump_ind, expert,current_cmd);
	  break;
	case UP_NTFS:
	  ntfs_boot_sector(disk_car, element->part, debug, dump_ind, expert, current_cmd);
	  break;
	case UP_HFS:
	case UP_HFSP:
	  HFS_HFSP_boot_sector(disk_car, element->part, debug, dump_ind, expert, current_cmd);
	  break;
	default:
	  log_warning("Need to fix\n");
	  log_partition(disk_car,element->part);
	  break;
      }
    }
  }
  return 0;
}

int interface_recovery(disk_t *disk_car, const list_part_t * list_part_org, const int debug, const int dump_ind, int align, const int ask_part_order, const unsigned int expert, const int search_vista_part, char **current_cmd)
{
  int res_interface_write;
  int fast_mode=0;
  do
  {
    list_part_t *list_part;
    const list_part_t *element;
    unsigned int menu=0;
    if(fast_mode==0)
      menu=3;	/* Search! */
    aff_copy(stdscr);
    wmove(stdscr,4,0);
    wdoprintf(stdscr,"%s",disk_car->description(disk_car));
    wmove(stdscr,5,0);
    res_interface_write=0;
    list_part=search_part(disk_car, list_part_org, debug, dump_ind, fast_mode, 1, search_vista_part, current_cmd);
    if(list_part!=NULL && (disk_car->arch==&arch_i386 || disk_car->arch==&arch_sun))
    { /* Correct disk geometry is necessary for successfull Intel and Sun partition recovery */
      unsigned int head_max;
      head_max=get_geometry_from_list_part(disk_car, list_part, debug);
      if(disk_car->CHS.head!=head_max)
	warning_geometry(disk_car,head_max+1,current_cmd);
    }
    {
      unsigned int location_boundary;
      if(disk_car->arch==&arch_i386)
      {
	unsigned int partition_vista=0;
	unsigned int partition_nonvista=0;
	for(element=list_part;element!=NULL;element=element->next)
	{
	  if(element->part->part_offset%(2048*512)==0 && element->part->part_size%(2048*512)==0)
	    partition_vista=1;
	  else
	    partition_nonvista=1;
	}
	if(partition_vista>0 && partition_nonvista==0)
	  location_boundary=2048*512;
	else
	{
	  if(partition_vista>0 && partition_nonvista>0)
	    align=0;
	  if(align==0)
	    location_boundary=disk_car->sector_size;
	  else if(align==1)
	    location_boundary=disk_car->CHS.sector * disk_car->sector_size;
	  else
	    location_boundary=(disk_car->CHS.head+1) * disk_car->CHS.sector * disk_car->sector_size;
	}
      }
      else if(disk_car->arch==&arch_mac)
      {
	location_boundary=4096;
      }
      else if(disk_car->arch==&arch_sun)
      {
	location_boundary=(disk_car->CHS.head+1) * disk_car->CHS.sector * disk_car->sector_size;
      }
      else
      {	/* arch_none, arch_xbox */
	location_boundary=disk_car->sector_size;
      }
      align_structure(disk_car,list_part,location_boundary);
    }

    disk_car->arch->init_structure(disk_car,list_part,debug);
    if(debug>0)
    {
      /* Write found partitions in the log file */
      log_info("\nResults\n");
      for(element=list_part;element!=NULL;element=element->next)
	log_partition(disk_car,element->part);
    }
    list_part=ask_structure(disk_car,list_part,debug,current_cmd);
    if(disk_car->arch->test_structure(list_part)==0)
    {
      int do_again=0;
      int max_ext=0;
      int can_ask_minmax_ext=0;
      int no_confirm=0;
      list_part=reduce_structure(list_part);
      /* Sort list_part */
      list_part=sorlist_part_t(list_part);
      /* Creer la partition etendue globale, cherche à aligner la partition */
      /* if(disk_car->arch==&arch_i386) */
      {
	list_part_t *parts;
	uint64_t partext_offset=0;
	uint64_t partext_size=0;
	list_part=add_ext_part_i386(disk_car,list_part,!max_ext,2,debug);
	for(parts=list_part;parts!=NULL;parts=parts->next)
	  if(parts->part->status==STATUS_EXT)
	  {
	    partext_offset=parts->part->part_offset;
	    partext_size=parts->part->part_size;
	  }
	if(partext_offset>0)
	{
	  list_part=add_ext_part_i386(disk_car,list_part,max_ext,2,debug);
	  for(parts=list_part;parts!=NULL;parts=parts->next)
	    if(parts->part->status==STATUS_EXT)
	    {
	      if(partext_offset!=parts->part->part_offset || partext_size!=parts->part->part_size)
		can_ask_minmax_ext=1;
	    }
	}
      }
      list_part=disk_car->arch->init_part_order(disk_car,list_part);
      if(ask_part_order!=0)
      {
	/* Demande l'ordre des entrees dans le MBR */
	ask_mbr_order_i386(disk_car,list_part);
	/* Demande l'ordre des partitions etendues */
      }
      do
      {
	do_again=0;
	res_interface_write=interface_write(disk_car,list_part,(fast_mode<1),can_ask_minmax_ext, &no_confirm, current_cmd,&menu);
	switch(res_interface_write)
	{
	  case 'W':
	    if(disk_car->arch->write_part!=NULL)
	    {
	      if(no_confirm!=0 || ask_confirmation("Write partition table, confirm ? (Y/N)")!=0)
	      {
		log_info("write!\n");
		if(disk_car->arch->write_part(disk_car,list_part,RW,debug,align))
		{
		  display_message(msg_PART_WR_ERR);
		}
		else
		{
		  use_backup(disk_car,list_part,debug,dump_ind,expert,current_cmd);
		  display_message("You will have to reboot for the change to take effect.\n");
		}
	      }
	      else
		log_info("Don't write, no confirmation\n");
	    }
	    break;
	  case 0:
	    if(disk_car->arch->write_part!=NULL)
	    {
	      log_info("simulate write!\n");
	      disk_car->arch->write_part(disk_car,list_part,RO,debug,align);
	    }
	    break;
	  case 'S':
	    if(fast_mode<2)
	      fast_mode++;
	    break;
	  case 'E':
	    max_ext=!max_ext;
	    list_part=add_ext_part_i386(disk_car,list_part,max_ext,2,debug);
	    do_again=1;
	    break;
	}
      }
      while(do_again==1);
    }
    else
    {
      display_message("Invalid partition structure.\n");
    }
    delete_list_part(list_part);
  } while(res_interface_write=='S');
  return 0;
}