My own archive format

[noeska]

Fragmentation cannot be avoided.

My idea is to keep a list of unused blocks. And reuse them asap. This gets you fragmention in the end. But for the moment i do not care.

Analyzing if you have fragmented files will be easy. Defragmenting it won't be as you said.

During the day i will upload what i have this far. Just wrote some new code on writing data using tvirtualfilestream into a tvirualfilesystem. But i still need to test that. Writing and reading a complete stream at once already works.

[Brainer]

My idea is to create something very similar to NTFS' LCN and, just like your idea was, store a list of removed blocks so that I know where I can store data. A block would be 1 kB in size.

If I want to store a file, I just calculate how many blocks I'd need, look up the list for removed blocks, seek there and write a 1 kB of data. And so on until the the list of removed blocks is empty, then I'd just write the rest of the file at the end of the archive.

The allocation tree would be placed just after the header and the list of removed blocks. Maybe I'll post some more detailed specification later, I'd really like to have look at your code, noeska, just to make sure I haven't copied much from you.

[noeska]

Here it is: http://www.noeska.net/downloads/VirtualFileSystem.zip MPL license

Be aware the the TVirtualFileStream is broken for writing. And it only supports one file. Because it have not yet written the directory part as i need TVirtualFileStream to work for that. I also need that one to keep the list of deleted blocks (yes blocks not files). So it is not realy useable yet.

In the example try the following
bNew
bFilleMemo
bSaveMemo
Close the application
bOpen
bLoadMemo

everything else may lead to exceptions :-)

Fixed TVirtualFileStream: Here it is: http://www.noeska.net/downloads/Virt...ystemFixed.zip MPL license
Not tested fully yet.
Small files e.g. < 1block seem to be broken now

[Brainer]

So you make the virtual file system have a fixed size?

Also looking at:
TBrainVFSBlock = packed record
Size: Word; // rozmiar bloku danych (domyœlnie: 512)
// data block size (default: 512)
Offset: Int64; // offset bloku w pliku. Int64 to m&#185;dry wyb??r
// block's offset in archive. Int64 is a wide choice here
Flag: Byte; // flaga opisuj&#185;ca blok:
// (0 - wolny blok, 7 - blok u&#191;ywany, 23 - blok usuni&#234;ty)
// flag describing the block:
// (0 - free block, 7 - dirty block, 23 - block deleted)
end;

Makes me wonder why store size and offset? The idea for fat/ntsf or virtualfilesystem is that all blocks are equal size.
In you case you can number your blocks 1,2,3 etc. The offset can be calculated as: header+(blockid*blocksize).
Thus giving:
TBrainVFSBlock = packed record
BlockId: Int64;
Flag: Byte; //could also be boolean?
end;
Or to go haywire. Only put deleted blocks in FBlocks :-) and assume other blocks are used.
Or are you not planning on splitting up larger files over multiple blocks. I do not see code for that yet in your code.
Be aware on what block together make a file and in what order.

Referring to your mail, no. Every block has the same size, I just store the info in the record for convenience.

About splitting files, yes. My idea is to split large files into several blocks, but I haven't implemented it yet. I sent you the code just to let you know what my idea actually is.

To everyone, here's the code I've got so far:
[pascal]
//************************************************** ****************************
//
// BrainVirtualFileSystem - Wirtualny system plik??w / Virtual file system.
// Copyright &#169; 2008 Patryk Nusbaum.
// Wszystkie prawa zastrze¬øone. / All rights reserved.
//
// Data modyfikacji / Last modified: 10.11.2008
// Mail: patrick.nusbaum@gmail.com
// WWW: www.pateman.net76.net
//
// Licencja / License
// -------------------
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// * Neither the name of Patryk Nusbaum nor the names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//************************************************** ****************************
unit BrainVirtualFileSystem;
// TODO 5 -o Patryk Nusbaum: Doda?¶ obs¬?ug?™ wyj¬±tk??w. / Add exception handling.
// TODO 4 -o Patryk Nusbaum: Doda?¶ obs¬?ug?™ klasy dziennika. / Add logging support.
// DONE 5 -o Patryk Nusbaum: Opracowa?¶ list?™ przechowuj¬±c¬± wolne bloki. / Make a list storing free blocks.

// prosz?™ si?™ zg¬?osi?¶ do mnie, gdy kto¬? odgadnie znaczenie warto¬?ci
// "BrainVFSProtectionFlag" i flag blok??w.
// hit me up when you guess the meaning of "BrainVFSProtectionFlag"
// and the block flags' values.

interface

{$DEFINE DEBUG}

uses
Windows, Classes, {$IFDEF DEBUG}SysUtils, Dialogs,{$ENDIF}
// --
BrainIntegerList;

const
// sta¬?e
// constants
BrainVFSSignature = 'BRAINVFS';
BrainVFSVersion = 10;
BrainVFSProtectionFlag = 92;
BrainVFSBlockSize = 512;
BrainVFSDiskSize = 1024;
BrainVFSMaxStringLength = 128;

type
// 128-bitowy ¬?a?±cuch tekstu
// a 128-byte string
TBrainVFSString = String[BrainVFSMaxStringLength];

// rekord nag¬wka pliku archiwum
// archive file's header record
{ .: TBrainVFSHeader :. }
TBrainVFSHeader = packed record
VFSSignature: array[0..7] of Char; // sygnatura pliku (domy¬?lnie: "BRAINVFS")
// file signature (default: "BRAINVFS")
VFSVersion: Byte; // wersja pliku (domy¬?lnie "10", czyli 1.0)
// file version (default: "10", means 1.0)
VFSProtectionFlag: Byte; // flaga ochrony pliku:
// (0 - brak ochrony, 92 - ochrona w¬?¬±czona)
// file protection flag:
// (0 - no protection, 92 - protection on)
VFSTreeOffset: Int64; // offset drzewa alokacji plik??w
// offset of the file allocation tree
end;

// rekord reprezentuj±cy pojedynczy blok danych
// record representing a single data block
{ .: TBrainVFSBlock :. }
TBrainVFSBlock = packed record
Size: Word; // rozmiar bloku danych (domy¬?lnie: 512)
// data block size (default: 512)
Offset: Int64; // offset bloku w pliku. Int64 to m±dry wyb??r
// block's offset in archive. Int64 is a wide choice here
Flag: Byte; // flaga opisuj±ca blok:
// (0 - wolny blok, 7 - blok u¬øywany, 23 - blok usuni?™ty)
// flag describing the block:
// (0 - free block, 7 - dirty block, 23 - block deleted)
end;

// klasa obs¬?uguj¬±ca dzia¬?anie wirtualnego dysku
// class working as a virtual disk
{ .: TBrainVFSDisk :. }
TBrainVFSDisk = class sealed(TObject)
private
{ Private declarations }
FBlocks: array of TBrainVFSBlock;
FFreeBlocks: TBrainIntegerList;
// --
FBlockCount: Word;
FBlockSize: Word;
FDiskSize: Word;
FStream: TStream;
// funkcja sprawdza, czy podany blok istnieje
// this function checks if "ABlockIndex" is a valid block index
function IsValidBlock(const ABlockIndex: Word): Boolean;
public
{ Public declarations }
constructor Create(const S: TStream = nil; const ABlockSize: Word = BrainVFSBlockSize;
const ADiskSize: Word = BrainVFSDiskSize);
destructor Destroy(); override;

// procedura dokonuje formatowania dysku
// this procedure formats a disk
procedure FormatDisk();

// funkcja zwraca pierwszy wolny blok danych
// this function returns a free block's index
function GetFreeBlock(): Word;
// funkcja zwraca "True", gdy flaga bloku wynosi "0"
// this function returns "True" when a block's flag is "0"
function IsBlockEmpty(const ABlockIndex: Word): Boolean;
// funkcja zwraca "True", gdy flaga bloku wynosi "23"
// this function returns "True" when a block's flag is "23"
function IsBlockRemoved(const ABlockIndex: Word): Boolean;
// funkcja zwraca "True", gdy flaga bloku wynosi "7"
// this function returns "True" when a block's flag is "7"
function IsBlockDirty(const ABlockIndex: Word): Boolean;
// funkcja zwraca offset bloku
// this function returns a block's offset
function GetBlockOffset(const ABlockIndex: Word): Int64;

// procedura odczytuje zawarto¬??¶ danego bloku do strumienia
// this procedure reads block's contents to a stream
procedure ReadBlock(const ABlockIndex: Word; out S: TStream);
// procedura zapisuje zawarto¬??¶ strumienia do bloku
// this procedure saves stream's contents to a block
procedure WriteBlock(const ABlockIndex: Word; const S: TStream);
// procedura ustawia flag?™ bloku na "23"
// this procedure sets a block's flag to "23"
procedure MarkBlockRemoved(const ABlockIndex: Word);
// procedura ustawia flag?™ bloku na "7"
// this procedure sets a block's flag to "7"
procedure MarkBlockDirty(const ABlockIndex: Word);

{$IFDEF DEBUG}
procedure DisplayFreeBlocks();
{$ENDIF}

property BlockCount: Word read FBlockCount;
property DiskSize: Word read FDiskSize;
property BlockSize: Word read FBlockSize;
end;

// klasa imituj¬±ca dzia¬?anie systemu dyskowego
// class behaving like a disk system
{ .: TBrainVFSDiskSystem :. }
TBrainVFSDiskSystem = class sealed(TObject)
private
{ Private declarations }
FDisk: TBrainVFSDisk;
public
{ Public declarations }
constructor Create(const ADisk: TBrainVFSDisk = nil);
destructor Destroy(); override;

(*
// procedura zapisuje plik do naszego wirtualnego dysku
// this procedure stores a file inside our virtual disk
procedure WriteFile(const AFileName: String);
*)

property Disk: TBrainVFSDisk read FDisk;
end;

implementation

{ TBrainVFSDisk }

constructor TBrainVFSDisk.Create(const S: TStream; const ABlockSize, ADiskSize: Word);
begin
inherited Create();

if (ABlockSize = 0) then
FBlockSize := BrainVFSBlockSize
else
FBlockSize := ABlockSize;
if (ADiskSize = 0) then
FDiskSize := BrainVFSDiskSize
else
FDiskSize := ADiskSize;

FStream := S;
FBlockCount := (FDiskSize div FBlockSize);

FFreeBlocks := TBrainIntegerList.Create();
FFreeBlocks.Duplicates := dupIgnore;
FFreeBlocks.Sorted := True;

SetLength(FBlocks, FBlockCount);
FormatDisk();
end;

destructor TBrainVFSDisk.Destroy;
begin
FStream := nil;
FBlocks := nil;
FFreeBlocks.Free();

inherited Destroy();
end;

procedure TBrainVFSDisk.DisplayFreeBlocks;
var
S: String;
I: Integer;
begin
S := 'FREE BLOCKS' + #13#10;
for I := 0 to FFreeBlocks.Count -1 do
S := S + IntToStr(FFreeBlocks.Integers[I]) + #13#10;
ShowMessage(S);
end;

procedure TBrainVFSDisk.FormatDisk();
const
AByte: Byte = 0;
var
I, J: Integer;
begin
FFreeBlocks.Clear();
FStream.Seek(SizeOf(TBrainVFSHeader), soFromBeginning);

for I := 0 to FBlockCount -1 do
with FBlocks[I] do
begin
Size := FBlockSize;
Offset := SizeOf(TBrainVFSHeader) + I * SizeOf(TBrainVFSBlock);
Flag := 0; // blok wolny / free block

FFreeBlocks.Add(I);

for J := 0 to FBlockSize -1 do
FStream.Write(AByte, SizeOf(Byte));
end;
end;

function TBrainVFSDisk.GetBlockOffset(const ABlockIndex: Word): Int64;
begin
if IsValidBlock(ABlockIndex) then
Result := FBlocks[ABlockIndex].Offset
else
Result := -1;
end;

function TBrainVFSDisk.GetFreeBlock: Word;
begin
Result := FFreeBlocks.First();
end;

function TBrainVFSDisk.IsBlockDirty(const ABlockIndex: Word): Boolean;
begin
if IsValidBlock(ABlockIndex) then
Result := (FBlocks[ABlockIndex].Flag = 7)
else
Result := False;
end;

function TBrainVFSDisk.IsBlockEmpty(const ABlockIndex: Word): Boolean;
begin
if IsValidBlock(ABlockIndex) then
Result := (FBlocks[ABlockIndex].Flag = 0)
else
Result := False;
end;

function TBrainVFSDisk.IsBlockRemoved(const ABlockIndex: Word): Boolean;
begin
if IsValidBlock(ABlockIndex) then
Result := (FBlocks[ABlockIndex].Flag = 23)
else
Result := False;
end;

function TBrainVFSDisk.IsValidBlock(const ABlockIndex: Word): Boolean;
begin
Result := (ABlockIndex < FDiskSize);
end;

procedure TBrainVFSDisk.MarkBlockDirty(const ABlockIndex: Word);
begin
if IsValidBlock(ABlockIndex) then
begin
FBlocks[ABlockIndex].Flag := 7;
FFreeBlocks.Remove(ABlockIndex);
end;
end;

procedure TBrainVFSDisk.MarkBlockRemoved(const ABlockIndex: Word);
begin
if IsValidBlock(ABlockIndex) then
begin
FBlocks[ABlockIndex].Flag := 23;
FFreeBlocks.Add(ABlockIndex);
end;
end;

procedure TBrainVFSDisk.ReadBlock(const ABlockIndex: Word; out S: TStream);
begin
if IsValidBlock(ABlockIndex) and Assigned(S) then
begin
FStream.Seek(FBlocks[ABlockIndex].Offset, soFromBeginning);
S.CopyFrom(FStream, FBlockSize);
end;
end;

procedure TBrainVFSDisk.WriteBlock(const ABlockIndex: Word; const S: TStream);
begin
if IsValidBlock(ABlockIndex) and Assigned(S) then
begin
FStream.Seek(FBlocks[ABlockIndex].Offset, soFromBeginning);
FStream.CopyFrom(S, FBlockSize);

// to samo, co MarkBlockDirty
// the same as MarkBlockDirty
FBlocks[ABlockIndex].Flag := 7;
FFreeBlocks.Remove(ABlockIndex);
end;
end;

{ TBrainVFSDiskSystem }

constructor TBrainVFSDiskSystem.Create(const ADisk: TBrainVFSDisk);
begin
inherited Create();

FDisk := ADisk;
end;

destructor TBrainVFSDiskSystem.Destroy;
begin
FDisk := nil;

inherited Destroy();
end;

end.
[/pascal]

I'll keep you posted.

[noeska]

for now i have an interesting problem.

start situation:
directory is at block 1.

next i save a file so as nextfreeblock i get 2.
next i write an entry in the directory (file is not yet written)
unfortunately the dir entry is to large to fit into block 1 together with the previous entry so it request a nextfreeblock to use and that gets 2 also
now i write the file now on writing it i do another nextfreeblock and get 3.
now i have wrong directory entry for the file as that now states 2 and not 3 as it should be.

hmm how to solve that:
1) update the directory entry after writing the file
2) write the file entry only after writing the file

Download: http://www.noeska.net/download/Virtu...temDirTest.zip MPL license

[Brainer]

Ooops, now I realised I made I mistake putting all the code here, next time I'll provide a link.

Noeska, do you have to store the file structure as a block? Can't you just use XML or a B-tree and just store it in the file archive?

[noeska]

Noeska, do you have to store the file structure as a block? Can't you just use XML or a B-tree and just store it in the file archive?

What file stucture are you refering to? If you mean a directory entry then yes. See what i do with fdir. Essentialy that is a tfilestream inside a tfilestream (the virtual filesystem).

[Brainer]

Yip, I meant the directory structure. My plan is to store it as a tree, at the end of the file. Also, I'm not sure if you noticed, I set a limit to the maximum size of a disk. It's 4 gigabytes (65536 bytes/block * 65536 blocks). 4 gigs is enough for now, I don't plan on making such big archives yet, but who knows?

I haven't checked your demo yet, will do soon. Why do you use a TStream-descendant class, btw? I saw it multiple times in other projects, couldn't understand it at all.

[noeska]

My plan is to store it as a tree, at the end of the file. Also, I'm not sure if you noticed, I set a limit to the maximum size of a disk.

Is not that a waste of disk space.? E.g. if you plan on using 2gb at the max and store the tree at the end you make a 2gb empty file first?

Why do you use a TStream-descendant class, btw? I saw it multiple times in other projects, couldn't understand it at all.

Yes it is not easy and i encountered lots of bugs while writing it :-)
But in general streams are an easy to use. E.g. lots of components in delphi provide easy ways of using them. E.g. Memo1.Lines.SaveToStream(MyStream);

[Brainer]

Is not that a waste of disk space.? E.g. if you plan on using 2gb at the max and store the tree at the end you make a 2gb empty file first?

No, you can always choose the size of the disk. All the blocks are written at once, that's the fault of my idea. So if you create a 2 GB disk, all the blocks will be immediately written. I have to find a way round it...

EDIT
Actually, I've found a way. Will introduce it later once I make some progress. Stay tuned. :lol: