/* FitDisk V2.0
   Christian Stieber, Konradstraße 41, D-85055 Ingolstadt (Germany)
   stieber@informatik.tu-muenchen.de */

/* This program is PUBLIC DOMAIN */

/* Note: this program assumes that SAS/C does not access local
   variables via SP, but instead loads SP into an adress register
   at function entry, and uses that register to access the local
   variables (link / unlink) !!!!
   This is required to make the stack-switching work
*/

/* define V39 if you want to compile for V39 and above ONLY */
/* #define V39 */

#define STACK_SIZE 4096

#ifndef EXEC_EXECBASE_H
#include <exec/execbase.h>
#endif

#ifndef DOS_DOSEXTENS_H
#include <dos/dosextens.h>
#endif

#ifndef PROTO_EXEC_H
#include <proto/exec.h>
#endif

#ifndef PROTO_DOS_H
#include <proto/dos.h>
#endif

#ifndef V39
#ifndef CLIB_ALIB_PROTOS_H
APTR LibAllocPooled( APTR poolHeader, unsigned long memSize );
APTR LibCreatePool( unsigned long memFlags, unsigned long puddleSize,
	unsigned long threshSize );
void LibDeletePool( APTR poolHeader );
void LibFreePooled( APTR poolHeader, APTR memory, unsigned long memSize );
#endif   /* CLIB_ALIB_PROTOS_H */
#else /* V39 only */
#define LibAllocPooled AllocPooled
#define LibCreatePool CreatePool
#define LibDeletePool DeletePool
#define LibFreePooled FreePooled
#endif   /* V39 */

#include <string.h>

/***********************************************/

struct FileInfo   /* This structure holds information about a file */
   {
      struct FileInfo *Next;
      long Blocks;
      char Name[1];
   };

struct Arguments   /* Filled in by ReadArgs() */
   {
      long *BlocksFree;
      char *Directory;
      long OFS;
      long MSDOS;
   };

/***********************************************/

struct ExecBase *SysBase;
struct DosLibrary *DOSBase;

static struct Arguments Arguments=
   {
      NULL,
      NULL,
      FALSE,
      FALSE
   };

static long BlocksFree=1756;   /* the default number of free blocks */

static void *MemoryPool;       /* heap */

static long Files=0;                     /* number of files in list */
static struct FileInfo *FileList=NULL;   /* the directory */

static struct FileInfo ***Selected;      /* complicated... which files are selected at each level of the recursion */

static long Break=RETURN_OK;             /* set if we have to break */

static struct StackSwapStruct *Stacks;   /* an array of stacks for the recursion */

static char Version[]="$VER: FitDisk 2.1 (26.01.94)"
#ifdef V39
" (V39)"
#endif
;

/***********************************************/

static void MakeFileList(void);
static int ReadDir(void);

/***********************************************/

int __saveds main(void)

{
   int RC;
   struct RDArgs *RDArgs;

   RC=RETURN_OK;
   SysBase=*(struct ExecBase **)4;
   if (DOSBase=(struct DosLibrary *)OpenLibrary("dos.library",37))
      {
         if (MemoryPool=LibCreatePool(0,64*1024,64*1024))
            {
               if (RDArgs=ReadArgs("BLOCKS/N,DIRECTORY=DIR,OFS/S,MSDOS/S",(long *)&Arguments,NULL))
                  {
                     if (Arguments.BlocksFree)
                        {
                           BlocksFree=*Arguments.BlocksFree;
                        }
                     else if (Arguments.MSDOS)
                        {
                           BlocksFree=1426;
                        }
                     if (!(RC=ReadDir()) && Files)
                        {
                           if (Selected=LibAllocPooled(MemoryPool,(Files+1)*sizeof(struct FileInfo **)))
                              {
                                 memset(Selected,0,(Files+1)*sizeof(struct FileInfo **));
                                 if (Stacks=LibAllocPooled(MemoryPool,Files*sizeof(struct StackSwapStruct)))
                                    {
                                       memset(Stacks,0,Files*sizeof(struct StackSwapStruct));
                                       MakeFileList();
                                       RC=Break;
                                    }
                                 else
                                    {
                                       PrintFault(IoErr(),NULL);
                                       RC=RETURN_ERROR;
                                    }
                              }
                           else
                              {
                                 PrintFault(IoErr(),NULL);
                                 RC=RETURN_ERROR;
                              }
                        }
                     FreeArgs(RDArgs);
                  }
               else
                  {
                     PrintFault(IoErr(),NULL);
                     RC=RETURN_ERROR;
                  }
               LibDeletePool(MemoryPool);
            }
         else
            {
               PrintFault(IoErr(),NULL);
               RC=RETURN_ERROR;
            }
         CloseLibrary((struct Library *)DOSBase);
      }
   else
      {
         RC=100;
      }
   return RC;
}

/***********************************************/

static BOOL MakeSelected(int k)

{
   if ((Selected[k]) ||
       (Selected[k]=LibAllocPooled(MemoryPool,(k+2)*sizeof(struct FileInfo *))))
      {
         memset(Selected[k],0,(k+2)*sizeof(struct FileInfo *));
         return TRUE;
      }
   else
      {
         PrintFault(IoErr(),NULL);
         Break=RETURN_ERROR;
         return FALSE;
      }
}

/***********************************************/

static BOOL MakeStack(int k)

{
   if ((Stacks[k].stk_Lower) ||
       (Stacks[k].stk_Lower=LibAllocPooled(MemoryPool,STACK_SIZE)))
      {
         Stacks[k].stk_Upper=((ULONG)(Stacks[k].stk_Lower))+STACK_SIZE;
         Stacks[k].stk_Pointer=(APTR)(Stacks[k].stk_Upper);
      }
   else
      {
         PrintFault(IoErr(),NULL);
         Break=RETURN_ERROR;
         return FALSE;
      }
}

/***********************************************/

#define MySelected     Selected[k]
#define ParentSelected Selected[k+1]

static long Select_k_Files(int k, struct FileInfo *StartFile, long BlocksFree, int *FileCount)

{
   long MinBlocksFree;
   struct FileInfo *FirstFile;
   long t;
   int MyFileCount;

   MinBlocksFree=BlocksFree;
   *FileCount=0;

   ParentSelected[0]=(struct FileInfo *)NULL;
   if (k>=0)
      {
         FirstFile=StartFile;
         while (FirstFile && !Break)
            {
               t=BlocksFree-FirstFile->Blocks;
               if (t>=0)
                  {
                     MySelected[0]=FirstFile;
                     MyFileCount=0;
                     if (t)
                        {
                           MySelected++;
                           StackSwap(&Stacks[k]);
                           t=Select_k_Files(k-1,FirstFile->Next,t,&MyFileCount);
                           StackSwap(&Stacks[k]);
                           MySelected--;
                        }
                     if (t<MinBlocksFree)
                        {
                           MinBlocksFree=t;
                           memcpy(ParentSelected,MySelected,(k+1)*sizeof(struct FileInfo *));
                           *FileCount=MyFileCount+1;
                           if (*FileCount==k+1) t=0;
                        }
                  }
               if (t)
                  {
                     FirstFile=FirstFile->Next;
                  }
               else
                  {
                     FirstFile=NULL;
                  }
               if (CheckSignal(SIGBREAKF_CTRL_C))
                  {
                     PrintFault(ERROR_BREAK,NULL);
                     Break=RETURN_WARN;
                  }
            }
      }
   return MinBlocksFree;
}

/***********************************************/

static void MakeFileList(void)                                    

{
   int k;
   long MinBlocksFree, t;
   int i;
   int FileCount;

   MinBlocksFree=BlocksFree;
   for (k=0; k<Files && MinBlocksFree && !Break; k++)
      {
         if (MakeSelected(k) && MakeSelected(k+1) && MakeStack(k))
            {
               t=Select_k_Files(k,FileList,BlocksFree,&FileCount);
               if (!Break)
                  {
                     if (t<MinBlocksFree)
                        {
                           MinBlocksFree=t;
                           Printf("I was able to fill %ld blocks with %ld file%s:\n",BlocksFree-MinBlocksFree,FileCount,FileCount==1 ? "" : "s");
                           for (i=0; i<Files && Selected[k+1][i]; i++)
                              {
                                 Printf("%s (%ld blocks)\n",Selected[k+1][i]->Name,Selected[k+1][i]->Blocks);
                              }
                           PutStr("\n");
                        }
                  }
            }
      }
}

/***********************************************/

static long BlocksUsed(long ByteSize)

{
   if (Arguments.MSDOS)
      {
         return 2*((ByteSize+1023)/1024);
      }
   else
      {
         long DataBlocks;

         DataBlocks=Arguments.OFS ? (ByteSize+487)/488 : (ByteSize+511)/512;
         if (!DataBlocks) DataBlocks=1;
         return(DataBlocks+(DataBlocks+71)/72);
      }
}

/***********************************************/

static void InsertFile(struct FileInfo *FileInfo)

{
   struct FileInfo *PrevInfo, *CurrentInfo;

   CurrentInfo=FileList;
   PrevInfo=(struct FileInfo *)&FileList;
   while (CurrentInfo && CurrentInfo->Blocks>FileInfo->Blocks)
      {
         PrevInfo=CurrentInfo;
         CurrentInfo=CurrentInfo->Next;
      }
   PrevInfo->Next=FileInfo;
   FileInfo->Next=CurrentInfo;
}

/***********************************************/

static int ReadDir(void)

{
   static struct FileInfoBlock __aligned FileInfoBlock;
   struct FileInfo *FileInfo;
   BPTR Directory;

   if (Arguments.Directory)
      {
         Directory=Lock(Arguments.Directory,ACCESS_READ);
      }
   else
      {
         Directory=DupLock(((struct Process *)(SysBase->ThisTask))->pr_CurrentDir);
      }
   if (Directory)
      {
         if (Examine(Directory,&FileInfoBlock))
            {
               while (ExNext(Directory,&FileInfoBlock))
                  {
                     if (FileInfoBlock.fib_DirEntryType<0 && BlocksUsed(FileInfoBlock.fib_Size)<=BlocksFree)
                        {
                           if (FileInfo=LibAllocPooled(MemoryPool,sizeof(struct FileInfo)+strlen(FileInfoBlock.fib_FileName)))
                              {
                                 strcpy(FileInfo->Name,FileInfoBlock.fib_FileName);
                                 FileInfo->Blocks=BlocksUsed(FileInfoBlock.fib_Size);
                                 InsertFile(FileInfo);
                                 Files++;
                              }
                           else
                              {
                                 PrintFault(IoErr(),NULL);
                                 return RETURN_ERROR;
                              }
                        }
                  }
               if (IoErr()!=ERROR_NO_MORE_ENTRIES)
                  {
                     goto DirError;
                  }
            }
         else
            {
               goto DirError;
            }
      }
   else
      {
DirError:PrintFault(IoErr(),Arguments.Directory);
         return RETURN_ERROR;
      }
   return RETURN_OK;
}