Re: [Freedos-devel] compressed FAT filesystems

2008-03-31 Thread Blair Campbell
Has Anybody looked up dmsdosfs? It is a linux filesystem driver that
can access quite a few different compressed dos filesystems like
drivespace and doublespace.  Perhaps an implementation could be
derived from its source code.

On Sat, Mar 29, 2008 at 7:20 AM, Eric Auer [EMAIL PROTECTED] wrote:

  Hi Imre,


   Well, I think that a seperate partition with a compressed file
   system and a block driver would be the best option.

  I agree about the block driver, but I believe a file would be more
  flexible than a partition. Once you compress a partition, you would
  otherwise have to shrink it to make use of the gain. This would
  need partition table modifications... Too much work for a simple
  system :-). What I had in mind was more something like: Compress
  a partition or ramdisk in-place, then copy the result to a file
  and format the partition or ramdisk again, to get an uncompressed
  filesystem again. You can store the compressed filesystem file on
  that partition or at another place then :-).


   At the time doublespace/stacker were released, people were not
   intended to have many partitions on there drive.

   But with linux requiring a multiple of partitions, it is proven
   that people would lower there standards and settle for multiple
   partitions anyway.

  Linux does not need multiple partitions. You can have everything
  on one partition and you can even use a swapfile instead of a
  swap partition. Yet I personally recently recommended a scheme
  of root, dos, swap, usr, home to a friend, because his BIOS
  could only boot from the first 8 GB of his 160 GB disk, so it
  made sense to put the first 3 partitions in that area (swap is
  useful for some hibernate schemes, possibly using the BIOS).

   This would be the fastest, most straight forward way of doing it.

  As often with computers, there are many ways, also many good ones :-).

  Eric





  -
  Check out the new SourceForge.net Marketplace.
  It's the best place to buy or sell services for
  just about anything Open Source.
  http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
  ___
  Freedos-devel mailing list
  Freedos-devel@lists.sourceforge.net
  https://lists.sourceforge.net/lists/listinfo/freedos-devel




-- 
Fall is my favorite season in Los Angeles, watching the birds change
color and fall from the trees.
 David Letterman (1947 - )

See ya

-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-29 Thread Imre Leber

 but more about efficient handling of long
file names. 

Your joking, right? 

Stored in reverse order, with the short file name after the long one, yeah 
that's realy got to make speed.

Imre



-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-29 Thread Eric Auer

 Stored in reverse order, with the short file name after the long
 one, yeah that's realy got to make speed.

Dear Imre, the MS algorithm is really a LITTLE bit more
advanced than a linear read of the directory. Try to find
and read the patents.

Eric



-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-29 Thread Eric Auer

Hi Imre,

 Well, I think that a seperate partition with a compressed file
 system and a block driver would be the best option.

I agree about the block driver, but I believe a file would be more
flexible than a partition. Once you compress a partition, you would
otherwise have to shrink it to make use of the gain. This would
need partition table modifications... Too much work for a simple
system :-). What I had in mind was more something like: Compress
a partition or ramdisk in-place, then copy the result to a file
and format the partition or ramdisk again, to get an uncompressed
filesystem again. You can store the compressed filesystem file on
that partition or at another place then :-).

 At the time doublespace/stacker were released, people were not
 intended to have many partitions on there drive.

 But with linux requiring a multiple of partitions, it is proven
 that people would lower there standards and settle for multiple
 partitions anyway.

Linux does not need multiple partitions. You can have everything
on one partition and you can even use a swapfile instead of a
swap partition. Yet I personally recently recommended a scheme
of root, dos, swap, usr, home to a friend, because his BIOS
could only boot from the first 8 GB of his 160 GB disk, so it
made sense to put the first 3 partitions in that area (swap is
useful for some hibernate schemes, possibly using the BIOS).

 This would be the fastest, most straight forward way of doing it.

As often with computers, there are many ways, also many good ones :-).

Eric



-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Antony Gordon
I've read all the posts, now lets look at what DriveSpace/DoubleSpace actually 
did...

You take a hard drive of x capacity, analyze the free space, a 'CVF' 
(Compressed Volume File) with variable cluster size, move the files on the disk 
into the newly created CVF file, compressing them in the process. once the 
files have been moved into the CVF, it is mounted as a drive letter,  and if 
the file extension is .000, the drive letter is swapped with the host drive. 
accessed through a block device that connects to a MRCI (Microsoft Realtime 
Compression Interface) server. 

When I read about CVF and MRCI in the DOS 6 Programmer's Reference (Microsoft), 
I thought that there had to be a much simpler way to implement this. Especially 
after the lawsuit between DOS 6.0 and DriveSpace's appearance in DOS 6.22. Of 
course, other things pressing I never really sat down to come up with 
something, by that time Windows 95 was on the horizon, and you could at least 
get up to an 800MB hard drive, and Disk Manager could help you use it all.

To effect the same principle in FreeDOS, a real-time compression interface 
would have to be clean room designed based on the known aspects of 
DBLSPACE/DRVSPACE integration with MS-DOS (or Stacker's integration with 
MS/PC-DOS), perhaps in the process figure out how we can improve the design,  
there is no need to be compatible, offer existing DBLSPACE/DRVSPACE users a 
reliable migrate path and go from there. 





 Date: Fri, 21 Mar 2008 14:08:34 -0430
 From: [EMAIL PROTECTED]
 To: freedos-devel@lists.sourceforge.net
 Subject: Re: [Freedos-devel] compressed FAT filesystems
 
 Would be OK something like a tar file, that includes time, date and 
 attributes for each file.
 And may be compressed if needed.
 
 +-+-+-+-+-+-+-+
 Marco A. Achury
 Tel: +58-(212)-6158777
 Cel: +58-(414)-3142282
 Fax: +58-(212)-2410828
 Skype: marcoachury
 www.geocities.com/marcoachury
 
 
 
 Imre Leber escribió:
  But then again,
 
  Do you realy need a file system if it is read only. You could just as well 
  use a table in the front that lists file names with path, and copy all data 
  after it. No need to have anything remotely like FAT and the like.
 
  Just:
 
  \temp\file1 start at 0
  \temp\file2 start at 1000
 
  0: data for \temp\file1
  1000: data for \temp\file2
 
  Not realy a file sytem, but should about the same.
 
  Imre
 

 
 
 
 -
 This SF.net email is sponsored by: Microsoft
 Defy all challenges. Microsoft(R) Visual Studio 2008.
 http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
 ___
 Freedos-devel mailing list
 Freedos-devel@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/freedos-devel

_
Watch “Cause Effect,” a show about real people making a real difference.  Learn 
more.
http://im.live.com/Messenger/IM/MTV/?source=text_watchcause-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Imre Leber

Actualy like Eric, privately, pointed out we already have a driver to treat a 
file as a volume, nl. SHSUFDRV.

However, the problem is not the driver, but what kind of file system should be 
used by such driver to make it compressed.

We might just take SHSUFDRV and, like doublespace, assume that anything that is 
on it is compressed. Then add a compressor like LZO to compress/decompress 
everything going in and out. That way the file system does not even need to be 
changed.

Imre 


- Oorspronkelijk bericht -
Van: Antony Gordon [mailto:[EMAIL PROTECTED]
Verzonden: vrijdag, maart 28, 2008 10:11 AM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems

I've read all the posts, now lets look at what DriveSpace/DoubleSpace actually 
did...

You take a hard drive of x capacity, analyze the free space, a 'CVF' 
(Compressed Volume File) with variable cluster size, move the files on the 
disk into the newly created CVF file, compressing them in the process. once 
the files have been moved into the CVF, it is mounted as a drive letter,  and 
if the file extension is .000, the drive letter is swapped with the host 
drive. accessed through a block device that connects to a MRCI (Microsoft 
Realtime Compression Interface) server. 

When I read about CVF and MRCI in the DOS 6 Programmer's Reference 
(Microsoft), I thought that there had to be a much simpler way to implement 
this. Especially after the lawsuit between DOS 6.0 and DriveSpace's appearance 
in DOS 6.22. Of course, other things pressing I never really sat down to come 
up with something, by that time Windows 95 was on the horizon, and you could 
at least get up to an 800MB hard drive, and Disk Manager could help you use it 
all.

To effect the same principle in FreeDOS, a real-time compression interface 
would have to be clean room designed based on the known aspects of 
DBLSPACE/DRVSPACE integration with MS-DOS (or Stacker's integration with 
MS/PC-DOS), perhaps in the process figure out how we can improve the design,  
there is no need to be compatible, offer existing DBLSPACE/DRVSPACE users a 
reliable migrate path and go from there. 





 Date: Fri, 21 Mar 2008 14:08:34 -0430
 From: [EMAIL PROTECTED]
 To: freedos-devel@lists.sourceforge.net
 Subject: Re: [Freedos-devel] compressed FAT filesystems
 
 Would be OK something like a tar file, that includes time, date and 
 attributes for each file.
 And may be compressed if needed.
 
 +-+-+-+-+-+-+-+
 Marco A. Achury
 Tel: +58-(212)-6158777
 Cel: +58-(414)-3142282
 Fax: +58-(212)-2410828
 Skype: marcoachury
 www.geocities.com/marcoachury
 
 
 
 Imre Leber escribió:
  But then again,
 
  Do you realy need a file system if it is read only. You could just as well 
  use a table in the front that lists file names with path, and copy all 
  data after it. No need to have anything remotely like FAT and the like.
 
  Just:
 
  \temp\file1 start at 0
  \temp\file2 start at 1000
 
  0: data for \temp\file1
  1000: data for \temp\file2
 
  Not realy a file sytem, but should about the same.
 
  Imre
 

 
 
 
 -
 This SF.net email is sponsored by: Microsoft
 Defy all challenges. Microsoft(R) Visual Studio 2008.
 http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
 ___
 Freedos-devel mailing list
 Freedos-devel@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/freedos-devel

_
Watch “Cause Effect,” a show about real people making a real difference.  
Learn more.
http://im.live.com/Messenger/IM/MTV/?source=text_watchcause



-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Imre Leber
Actually the sources seem to already contain zlib. 

So I assume we almost have a working doublespace already. But somebody ought to 
have a look at it to make it complete/fix the bugs.

Imre

- Oorspronkelijk bericht -
Van: Imre Leber [mailto:[EMAIL PROTECTED]
Verzonden: vrijdag, maart 28, 2008 01:05 PM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Actualy like Eric, privately, pointed out we already have a driver to treat a 
file as a volume, nl. SHSUFDRV.

However, the problem is not the driver, but what kind of file system should be 
used by such driver to make it compressed.

We might just take SHSUFDRV and, like doublespace, assume that anything that 
is on it is compressed. Then add a compressor like LZO to compress/decompress 
everything going in and out. That way the file system does not even need to be 
changed.

Imre 


- Oorspronkelijk bericht -
Van: Antony Gordon [mailto:[EMAIL PROTECTED]
Verzonden: vrijdag, maart 28, 2008 10:11 AM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems

I've read all the posts, now lets look at what DriveSpace/DoubleSpace 
actually did...

You take a hard drive of x capacity, analyze the free space, a 'CVF' 
(Compressed Volume File) with variable cluster size, move the files on the 
disk into the newly created CVF file, compressing them in the process. once 
the files have been moved into the CVF, it is mounted as a drive letter,  and 
if the file extension is .000, the drive letter is swapped with the host 
drive. accessed through a block device that connects to a MRCI (Microsoft 
Realtime Compression Interface) server. 

When I read about CVF and MRCI in the DOS 6 Programmer's Reference 
(Microsoft), I thought that there had to be a much simpler way to implement 
this. Especially after the lawsuit between DOS 6.0 and DriveSpace's 
appearance in DOS 6.22. Of course, other things pressing I never really sat 
down to come up with something, by that time Windows 95 was on the horizon, 
and you could at least get up to an 800MB hard drive, and Disk Manager could 
help you use it all.

To effect the same principle in FreeDOS, a real-time compression interface 
would have to be clean room designed based on the known aspects of 
DBLSPACE/DRVSPACE integration with MS-DOS (or Stacker's integration with 
MS/PC-DOS), perhaps in the process figure out how we can improve the design,  
there is no need to be compatible, offer existing DBLSPACE/DRVSPACE users a 
reliable migrate path and go from there. 





 Date: Fri, 21 Mar 2008 14:08:34 -0430
 From: [EMAIL PROTECTED]
 To: freedos-devel@lists.sourceforge.net
 Subject: Re: [Freedos-devel] compressed FAT filesystems
 
 Would be OK something like a tar file, that includes time, date and 
 attributes for each file.
 And may be compressed if needed.
 
 +-+-+-+-+-+-+-+
 Marco A. Achury
 Tel: +58-(212)-6158777
 Cel: +58-(414)-3142282
 Fax: +58-(212)-2410828
 Skype: marcoachury
 www.geocities.com/marcoachury
 
 
 
 Imre Leber escribió:
  But then again,
 
  Do you realy need a file system if it is read only. You could just as 
  well use a table in the front that lists file names with path, and copy 
  all data after it. No need to have anything remotely like FAT and the 
  like.
 
  Just:
 
  \temp\file1 start at 0
  \temp\file2 start at 1000
 
  0: data for \temp\file1
  1000: data for \temp\file2
 
  Not realy a file sytem, but should about the same.
 
  Imre
 

 
 
 
 -
 This SF.net email is sponsored by: Microsoft
 Defy all challenges. Microsoft(R) Visual Studio 2008.
 http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
 ___
 Freedos-devel mailing list
 Freedos-devel@lists.sourceforge.net
 https://lists.sourceforge.net/lists/listinfo/freedos-devel

_
Watch “Cause Effect,” a show about real people making a real difference.  
Learn more.
http://im.live.com/Messenger/IM/MTV/?source=text_watchcause



-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel





-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net

Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Antony Gordon
So the next step is file system. Well we already know FAT, like Microsoft, we 
can  bitmap the CVF allocation table, 0 meaning unused and 1 meaning used. The 
largest capacity of the BitFAT (assuming a 512MB CVF) is 128K( following MS 
standard).

Now according to the MS-DOS programmers reference, the MDFAT (or DoubleSpace 
File Allocation Table) consists of a series of 4 byte entries. They map FAT 
clusters to sectors in the sector heap. There is one entry for each cluster on 
the compressed drive. The entries specify the location of the sectors in the 
heap that contain the data for the cluster and flags to indicate status (i.e., 
in use, compressed, and the size of the cluster). MDFAT is a function of the 
max capacity of the CVF, The largest capacity is 512MB for a CVF so the largest 
MDFAT size is 256K
   
So, 384K in accounting using the Microsoft method, assuming direct 
implementation.


 From: [EMAIL PROTECTED]
 To: freedos-devel@lists.sourceforge.net
 Date: Fri, 28 Mar 2008 12:13:48 +
 Subject: Re: [Freedos-devel] compressed FAT filesystems
 
 Actually the sources seem to already contain zlib. 
 
 So I assume we almost have a working doublespace already. But somebody ought 
 to have a look at it to make it complete/fix the bugs.
 
 Imre
 
 - Oorspronkelijk bericht -
 Van: Imre Leber [mailto:[EMAIL PROTECTED]
 Verzonden: vrijdag, maart 28, 2008 01:05 PM
 Aan: freedos-devel@lists.sourceforge.net
 Onderwerp: Re: [Freedos-devel] compressed FAT filesystems
 
 
 Actualy like Eric, privately, pointed out we already have a driver to treat 
 a file as a volume, nl. SHSUFDRV.
 
 However, the problem is not the driver, but what kind of file system should 
 be used by such driver to make it compressed.
 
 We might just take SHSUFDRV and, like doublespace, assume that anything that 
 is on it is compressed. Then add a compressor like LZO to 
 compress/decompress everything going in and out. That way the file system 
 does not even need to be changed.
 
 Imre 
 
 
 - Oorspronkelijk bericht -
 Van: Antony Gordon [mailto:[EMAIL PROTECTED]
 Verzonden: vrijdag, maart 28, 2008 10:11 AM
 Aan: freedos-devel@lists.sourceforge.net
 Onderwerp: Re: [Freedos-devel] compressed FAT filesystems
 
 I've read all the posts, now lets look at what DriveSpace/DoubleSpace 
 actually did...
 
 You take a hard drive of x capacity, analyze the free space, a 'CVF' 
 (Compressed Volume File) with variable cluster size, move the files on the 
 disk into the newly created CVF file, compressing them in the process. once 
 the files have been moved into the CVF, it is mounted as a drive letter,  
 and if the file extension is .000, the drive letter is swapped with the 
 host drive. accessed through a block device that connects to a MRCI 
 (Microsoft Realtime Compression Interface) server. 
 
 When I read about CVF and MRCI in the DOS 6 Programmer's Reference 
 (Microsoft), I thought that there had to be a much simpler way to implement 
 this. Especially after the lawsuit between DOS 6.0 and DriveSpace's 
 appearance in DOS 6.22. Of course, other things pressing I never really sat 
 down to come up with something, by that time Windows 95 was on the horizon, 
 and you could at least get up to an 800MB hard drive, and Disk Manager 
 could help you use it all.
 
 To effect the same principle in FreeDOS, a real-time compression interface 
 would have to be clean room designed based on the known aspects of 
 DBLSPACE/DRVSPACE integration with MS-DOS (or Stacker's integration with 
 MS/PC-DOS), perhaps in the process figure out how we can improve the 
 design,  there is no need to be compatible, offer existing 
 DBLSPACE/DRVSPACE users a reliable migrate path and go from there. 
 
 
 
 
 
  Date: Fri, 21 Mar 2008 14:08:34 -0430
  From: [EMAIL PROTECTED]
  To: freedos-devel@lists.sourceforge.net
  Subject: Re: [Freedos-devel] compressed FAT filesystems
  
  Would be OK something like a tar file, that includes time, date and 
  attributes for each file.
  And may be compressed if needed.
  
  +-+-+-+-+-+-+-+
  Marco A. Achury
  Tel: +58-(212)-6158777
  Cel: +58-(414)-3142282
  Fax: +58-(212)-2410828
  Skype: marcoachury
  www.geocities.com/marcoachury
  
  
  
  Imre Leber escribió:
   But then again,
  
   Do you realy need a file system if it is read only. You could just as 
   well use a table in the front that lists file names with path, and copy 
   all data after it. No need to have anything remotely like FAT and the 
   like.
  
   Just:
  
   \temp\file1 start at 0
   \temp\file2 start at 1000
  
   0: data for \temp\file1
   1000: data for \temp\file2
  
   Not realy a file sytem, but should about the same.
  
   Imre
  
 
  
  
  
  -
  This SF.net email is sponsored by: Microsoft
  Defy all challenges. Microsoft(R) Visual Studio 2008.
  http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01

Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Eric Auer

Hi Antony,

for now, I would not recommend to try to clone any MS
compressed filesystem. Remember that they themselves
have had licensing issues with their own compressed
filesystem. One thing which makes doublespace and co
complex is their ability to WRITE to the filesystem
while it is mounted / in use. Let me explain my own
suggestion for a simpler system:

- replace the 2nd FAT by an array of cluster sizes (FAT16)
  or cluster offsets (FAT32). The latter has better speed
  but for the former, you can buffer some intermediate
  offsets in RAM (eg offset of every 256th cluster)

- clusters which have same size as uncompressed ones, are
  uncompressed clusters. Simple. Compressed clusters should
  be stored at offsets which are multiples of the sector
  size, to keep access times low and to simplify access...

- clusters which have size 0 are not in use. Simple.

- either you allow no writing, or if you write, you only
  allow writes for which the compressed cluster must not
  grow. If a write violates both constraints, you have to
  change the FAT to use a fresh cluster at the current end
  of the compressed filesystem. Such clusters ARE allowed
  to grow, but only if there are no used clusters at any
  later offset in the compressed filesystem.

- if you allow writing, do not actually shrink compressed
  clusters. Of course this can cause fragmentation. You
  can have a tool which collects all unused clusters of
  nonzero size and recycles the space they take, but this
  would happen while the filesystem is not active / mounted.

- you could use heuristics on initial filesystem creation /
  compression, for example to avoid compression of directories
  (this makes it easier for the directories to grow later).



I hope that such an implementation would be quite straigth-
forward and have good performance for read-only access. It
can be a FAT block device for DOS as output and can take
a file, partition or other data source as input. It would
do the following transformations:

- first FAT and boot sector stay as they are

- access to 2nd FAT is redirected to first FAT

- access to clusters is redirected by reading the table
  explained above (which is stored at the location of the
  former 2nd FAT) to find out the actual starting sector /
  offset of the cluster in the compressed filesystem, and
  then reading and decompressing that cluster and returning
  the decompressed contents. Writing will be more complex
  but is not needed for a first implementation.

- note that clusters are ALWAYS in strict linear order,
  even with the suggested method which would allow writes
  to the filesystem as described above. That avoids any
  need for extra redirections like cluster heaps :-).



You also need a tool for initial compression / creation of
such a compressed filesystem. Luckily it can operate in the
same space as the uncompressed filesystem, replacing it...

- walk through all clusters, and copy them from their normal
  version into their compressed version. As clusters never
  are bigger than in uncompressed state, this is as easy as
  successively overwriting all clusters with compressed data
  and filling the former 2nd FAT data area with the size info
  or offset info of all compressed clusters :-)

- this works for both FAT16 and FAT32, but I would not like
  the hassles to make it work for FAT12. Yet it would be
  possible. In FAT12, every entry has 1.5 bytes size, and
  every compressed size entry will have to be 1 or 1.5
  bytes as well. Actually 1 byte is enough as all sizes are
  multiples of 1 sector, as suggested above, and one cluster
  is never more than 64 or 128 sectors (of 512 bytes) big.

- note that you can, in principle, save some space by always
  storing only compressed SIZES. Yet as we have as much space
  as the 2nd FAT took, it is more efficient to store 32bit
  OFFSETS (in sector size units: up to 2 terabytes) for FAT32.
  Then you know at once where a compressed cluster startes,
  without having to sum up sizes :-).

- the input filesystem can be an actual partition on disk
  or the FAT filesystem of a RAMDISK, does not really matter

- the output can be stored on the source partition or on
  the ramdisk, but you will typically download it into a
  file when the compression is complete, as such a compressed
  filesystem image is smaller than the original filesystem.

- I suggest to use the source disk as the output target for
  the compression tool and use general tools like DISKCOPY
  to copy the compressed filesystem to a file when done...

- of course you must not write to a filesystem WHILE it is
  being processed by the compression tool :-p.

Eric :-)

PS: 16bit OFFSETS would not be so useful, as they only allow
partition sizes of up to 32 MB if the unit is sectors ;-).


-
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.

Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Antony Gordon

I would think that the information contained in the MS-DOS 6 Programmers 
reference is free of any restrictions related to that lawsuit. 

An initial clean room design would allow us to imitate the core functionality 
of DoubleSpace. This would allow us to read the compressed volume files, if for 
no other purpose than compatibility. The next step would be to improve the 
design where it is lacking. 

As far as writing to the file system, DoubleSpace allocates the BitFAT, MDFAT 
and FAT to maximum capacity. The resulting CVF file is maxxed for the drive in 
question, even though in most cases, the CVF will not be large enough to 
require the maximum capacity of these structures. This preallocation allows for 
growing and shrinking the CVF file very quickly. 

The other alternative might involve some sort of GZIP done on each file, so 
there is an 'invisible' decompression each time a file is accessed, and a 
decompression when the file is moved from a volume designated 'compressed' to a 
volume designated 'not compressed'. We can then use the reserved field in the 
BPB to designate a compressed file system or add to the list of FileSystemTypes 
at the end of the BPB (i.e., FAT12C, FAT16C, FAT32C).

I don't see how writing to the CVF would be a problem, since all the 'disk' 
writes would go through the BLOCK device driver, and since the driver is in 
effect a 'TSR' of sorts, it can take over Int 13h, portions of Int 21h, Int 
25h, and Int 26h (which comprise most of how DOS applications access the disk).

-T


 Date: Fri, 28 Mar 2008 20:27:50 +0100
 From: [EMAIL PROTECTED]
 To: freedos-devel@lists.sourceforge.net
 Subject: Re: [Freedos-devel] compressed FAT filesystems
 
 
 Hi Antony,
 
 for now, I would not recommend to try to clone any MS
 compressed filesystem. Remember that they themselves
 have had licensing issues with their own compressed
 filesystem. One thing which makes doublespace and co
 complex is their ability to WRITE to the filesystem
 while it is mounted / in use. Let me explain my own
 suggestion for a simpler system:
 
 - replace the 2nd FAT by an array of cluster sizes (FAT16)
   or cluster offsets (FAT32). The latter has better speed
   but for the former, you can buffer some intermediate
   offsets in RAM (eg offset of every 256th cluster)
 
 - clusters which have same size as uncompressed ones, are
   uncompressed clusters. Simple. Compressed clusters should
   be stored at offsets which are multiples of the sector
   size, to keep access times low and to simplify access...
 
 - clusters which have size 0 are not in use. Simple.
 
 - either you allow no writing, or if you write, you only
   allow writes for which the compressed cluster must not
   grow. If a write violates both constraints, you have to
   change the FAT to use a fresh cluster at the current end
   of the compressed filesystem. Such clusters ARE allowed
   to grow, but only if there are no used clusters at any
   later offset in the compressed filesystem.
 
 - if you allow writing, do not actually shrink compressed
   clusters. Of course this can cause fragmentation. You
   can have a tool which collects all unused clusters of
   nonzero size and recycles the space they take, but this
   would happen while the filesystem is not active / mounted.
 
 - you could use heuristics on initial filesystem creation /
   compression, for example to avoid compression of directories
   (this makes it easier for the directories to grow later).
 
 
 
 I hope that such an implementation would be quite straigth-
 forward and have good performance for read-only access. It
 can be a FAT block device for DOS as output and can take
 a file, partition or other data source as input. It would
 do the following transformations:
 
 - first FAT and boot sector stay as they are
 
 - access to 2nd FAT is redirected to first FAT
 
 - access to clusters is redirected by reading the table
   explained above (which is stored at the location of the
   former 2nd FAT) to find out the actual starting sector /
   offset of the cluster in the compressed filesystem, and
   then reading and decompressing that cluster and returning
   the decompressed contents. Writing will be more complex
   but is not needed for a first implementation.
 
 - note that clusters are ALWAYS in strict linear order,
   even with the suggested method which would allow writes
   to the filesystem as described above. That avoids any
   need for extra redirections like cluster heaps :-).
 
 
 
 You also need a tool for initial compression / creation of
 such a compressed filesystem. Luckily it can operate in the
 same space as the uncompressed filesystem, replacing it...
 
 - walk through all clusters, and copy them from their normal
   version into their compressed version. As clusters never
   are bigger than in uncompressed state, this is as easy as
   successively overwriting all clusters with compressed data
   and filling the former 2nd FAT data area with the size info

Re: [Freedos-devel] compressed FAT filesystems

2008-03-28 Thread Eric Auer

Hi Antony, (please switch from HTML to plain text mail...)

 I would think that the information contained in the MS-DOS 6
 Programmers reference is free of any restrictions related to
 that lawsuit.

(I assume you mean the one which forced MS to go DOS 6.2 to 6.22
and replace a bad license compressor with a barely ok clone...)

Unfortunately, no. Things can be well documented and can still
be copyrighted. For example Microsoft may have bought licenses
to have the permission to implement some well known but clever
and copyrighted algorithm for compressed filesystems in their
DOS 6.xx ...?   You maybe remember all those hassles about when
Microsoft tried to get paid by everybody who uses FAT systems.

It turned out that several patents had expired and some ideas
were too trivial to be patented. But some patents remained.
Those are not so much about FAT (if at all, then mostly about
FAT32 extensions) but more about efficient handling of long
file names. Luckily some old document from Microsoft explicitly
allows other general operating systems to support all aspects of
FAT, but for example makers of embedded devices like mp3 players
do have to pay license fees to Microsoft... Actually I own some
mp3 player which only shows id3 tags and ignores long file names
... because the makers did not want to pay Microsoft tax? This is
not linked to the question who and how actually programmed this.

I think even a general operating system could expect complaints
if they just use the Microsoft patented optimizations for their
long file name support. But as said, supporting long file names
at all is okay, as long as it is for a general operating system.

Please also see my footnote / PS about this whole licensing stuff!



 An initial clean room design would allow us to imitate the core
 functionality of DoubleSpace. This would allow us to read the
 compressed volume files, if for no other purpose than compatibility.

I doubt that such compressed volume files 1. still exist, 2. do
exist at a place where MS DOS no longer exists and 3. anybody
wants to keep them instead of just copying all files to an
uncompressed disk and then throw away MS DOS.

 The next step would be to improve the design where it is lacking.

Dunno. MS DOS is ancient. And there are several working, free and
open source modern compressed file systems out there. You should
assume that those have better design than Doublespace anyway :-).

 As far as writing to the file system, DoubleSpace allocates the BitFAT,
 MDFAT and FAT to maximum capacity. The resulting CVF file is maxxed for
 the drive in question, even though in most cases, the CVF will not be
 large enough to require the maximum capacity of these structures. This
 preallocation allows for growing and shrinking the CVF file very quickly.

Sorry, but I do not understand your summary. I assume you mean that all
tables are big enough to describe the state when all clusters are used,
but are not bigger than that? Then that would be a pretty normal size
for the tables :-).



 The other alternative might involve some sort of GZIP done on each file,
 so there is an 'invisible' decompression each time a file is accessed,
 and a decompression when the file is moved from a volume designated
 'compressed' to a volume designated 'not compressed'.

Actually TSRs like DIET have done that in the past. There is not much
magic about that. You can flag a file as being compressed by using
otherwise unused bits in the directory entry (attribs, second field
of the timestamp, etc) or by letting the contents start with a header.

Problem is that as soon as you switch off the driver, you can still
access everything, but of course you now get compressed files instead
of the invisibly decompressed files you would expect. As long as you
write-protect the compressed files, that problem is sort of acceptable.
The TSR driver could then grant write access by virtue of knowing that
the compressed file was only write-protected because it is compressed
and should not be written to without the driver loaded :-).

Note that you often do not want to compress ALL files because many
modern file formats already ARE compressed, so you cannot get those
files much smaller anyway, and compression attempts just add overhead.



 I don't see how writing to the CVF would be a problem, since all
 the 'disk' writes would go through the BLOCK device driver, and
 since the driver is in effect a 'TSR' of sorts, it can take over
 Int 13h, portions of Int 21h, Int 25h, and Int 26h (which comprise
 most of how DOS applications access the disk).

Uhhhm... We are not going to write a stealth virus here. We only
talk about a compressed filesystem driver. As long as DOS and your
DOS apps behave, you ONLY need a block device driver for that. No
hooks to any interrupt. Neither 13 (BIOS) nor 25/26 (DOS raw sector
access) nor 21 (DOS file access).

You can also have a compressed filesystem which is not like anything
with FAT at all. The interface for such 

Re: [Freedos-devel] compressed FAT filesystems

2008-03-21 Thread Imre Leber

But then again,

Do you realy need a file system if it is read only. You could just as well use 
a table in the front that lists file names with path, and copy all data after 
it. No need to have anything remotely like FAT and the like.

Just:

\temp\file1 start at 0
\temp\file2 start at 1000

0: data for \temp\file1
1000: data for \temp\file2

Not realy a file sytem, but should about the same.

Imre


- Oorspronkelijk bericht -
Van: Eric Auer [mailto:[EMAIL PROTECTED]
Verzonden: vrijdag, maart 21, 2008 03:16 AM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Hoi Imre,

 You did however make the very valid point that implementing a
 compressed file system is not so easy as one might think.

Luckily the task gets a lot easier if the filesystem will be
readonly (tool to create it, driver to read it). And such a
filesystem is still pretty useful :-).



 There is indeed a problem with random access in a stream.
 That is not very trivial to solve. But it shouldn't be overly
 difficult either.

Most compressed filesystems mentioned work around this
problem by compressing the data in blocks, for example
each cluster separately. The compressed blocks can start
at any offset, but offsets are typically rounded to a
multiple of, for example, the physical sector size. If
you use big blocks, you have to decompress more data
(and possibly eat more CPU and RAM) before you can get
to the decompressed data at the end of a block. But if
you use small blocks, you get worse compression rates
as you have less context to compress redundant data.

Your driver either needs to buffer a whole decompressed
block or it will have to decompress the same block more
than once whenever the operating system wants to read
a part of the block. In most OSes, the operating system
always reads whole 512 byte sectors, but some OSes will
read whole clusters and others only read those parts of
a cluster that you actually have to access at a time.



As BIOS disk drivers cannot access high memory directly
and EMS pages are a bad idea for filesystem drivers as
you might have some app which uses EMS concurrently, you
typically have to put decompression buffers into a DOS
low memory space or at least into UMB space... Because
you want to avoid double decompression CPU overhead, you
probably want to limit the compression block size based
on how much DOS RAM you want to give a filesystem driver.

Doing LZSS on chunks of 4k or 8k size would be a start :-).
For comparison, FAT16 normally uses 2k or more per cluster,
FAT12 (harddisk variant) and FAT32 (if filesystem  1/4 GB)
use 4k or more per cluster. Min/Max are always 0.5k/32k if
you want good compatibility (else 64k / even(?) 0.5-127.5k
cluster sizes, sector sizes from 32/64/128 to 512by or 2k).



 No what I mean with this is that if it is a linux driver it
 means that it is inherently linked to the internals of linux.

True. A Linux driver is more likely to be portable to SHSUCDX
style drivers than to our kernel. Still worth a try. The idea
is that SHSUCDX provides more semantic primitives (files
and directories etc) while the kernel built-in driver for
FAT operates in a more lowlevel way on FAT formatted disks
(block devices). Of course SHSUCDX itself also connects to
a kernel interface for the semantic side of a filesystem
(cdrom, network...). So we have a choice of interfaces.



 What I did not see was an overview of the structure of the OS

Well for romfs, the URL actually points to a spec for the FS.
I did not even look for an implementation of that one...

A more DOS friendly compressed filesystem would be one which
is FAT-ish with compressed data clusters, as suggested in the
post which started this thread :-). A driver for such a FAT-
ish compressed filesystem could give DOS a readonly block
device, and it would only have to implement basic knowledge
about the compression structures and the transformation into
normal FAT when DOS reads data or metadata. A DOS driver for
a FAT-ish compressed filesystem does not have to understand
anything about directory entries or FAT chains actually :-).

Eric


-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel





-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-21 Thread Marco Achury
Would be OK something like a tar file, that includes time, date and 
attributes for each file.
And may be compressed if needed.

+-+-+-+-+-+-+-+
Marco A. Achury
Tel: +58-(212)-6158777
Cel: +58-(414)-3142282
Fax: +58-(212)-2410828
Skype: marcoachury
www.geocities.com/marcoachury



Imre Leber escribió:
 But then again,

 Do you realy need a file system if it is read only. You could just as well 
 use a table in the front that lists file names with path, and copy all data 
 after it. No need to have anything remotely like FAT and the like.

 Just:

 \temp\file1 start at 0
 \temp\file2 start at 1000

 0: data for \temp\file1
 1000: data for \temp\file2

 Not realy a file sytem, but should about the same.

 Imre

   



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-20 Thread Imre Leber

Does the fact that all this runs on linux slip your mind (like in no way 
interesting for the stated purpose).

Seriously, how is any of that supposed to be running in DOS? It's mainly not 
even embedded (like a set of operating system services you can embed in a 
microcontroller application).

Imre


- Oorspronkelijk bericht -
Van: Eric Auer [mailto:[EMAIL PROTECTED]
Verzonden: donderdag, maart 20, 2008 03:33 AM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Hi Imre,

 Which free/open compressed embedded filesystems would that be?

Browsing wikipedia a bit gives me quite a few READONLY free and
open source compressed filesystems, several of which are useful
for embedded systems. For writeability, you would typically have
to alloc new space in your filesystem whenever a changed cluster
no longer fits (in compressed form) into where it was before.
Then you need the ability to have the storage locations of the
cluster contents be nonlinear, and you need some way to find
unused areas and either re-use them on the fly or defrag them
out of the filesystem with an offline (while the filesystem
is not used) tool. Luckily a readonly compressed filesystem is
very useful for various things already, so you can make people
happy with one of the simple readonly systems listed below :-).



http://en.wikipedia.org/wiki/Cramfs - for ROM, GPLed, uses zlib,
each page is compressed separately, metadata is not compressed,
max 16 MB / file, 256 MB / filesystem


http://en.wikipedia.org/wiki/SquashFS - GPLed, readonly, uses gzip,
used for several LiveCD versions of Linuxes, compresses data and
metadata in chunks of up to 1 MB each... Max 2^64 bytes per file.
Default block size 128 kB.


http://en.wikipedia.org/wiki/Zisofs - Linux, basically ISO9660
with extra flag to mark compressed files, it seems ;-). This
means that uncompressed files on Zisofs can be accessed by any
ISO9660 capable driver and operating system :-).


http://en.wikipedia.org/wiki/Cloop - Linux, simply a wrapper to
store a compressed block device image on a block device, it seems.
Compressed images contain a seek index with compressed and un-
compressed block sizes in pairs and the zlib compressed blocks.
I assume you get the offset of a compressed block by summing up
the sizes of the compressed blocks before it. Wikipedia says that
Apple DMG has a similar design.


http://logfs.org/logfs/LogFS - GPLed successor for JFFS2, for
flash devices... Seems to be work in progress


http://lxr.linux.no/linux/Documentation/filesystems/romfs.txt
A really simple filesystem: Main content is a linked list of
files, each file consisting of a header and the data of the
file, all aligned to 16 byte boundaries. Header contains:
Link, flags, size, checksum, max 15 bytes of name. You can
easily introduce a flag for compressed files. The link has
28 bit (high 28 bit of offset), leaving 36 bits for flags.

Flags are type (hardlink, dir, file, symlink, block device,
char device, socket, fifo) plus extra info. Hardlink info:
Offset pointer. Dir info: First file pointer. Device info:
The major and minor number. Symlink info: None - instead,
the file content is the symlink string. The . and ..
of directories are stored as normal directory entries, the
same idea as in FAT.



 Add a compression attribute to the inode structure in LEAN. And then
 put the compressed data into the file.

Tools have done the same for FAT: Use an unused bit or combination
of bits in the file attribute to mark a file as compressed, or use
some sort of header in the file contents...

The suggestion of my previous mail is a bit similar to CramFS
and Cloop in design, but my main idea is to have a filesystem
which stays similar to FAT and where it is easy to transform
a FAT system into a compressed one with a tool and for the
other way round make a compressed FAT system look like it was
a normal one with a driver for the other way round, making it
possible for the FreeDOS kernel to mount it easily :-).

This includes keeping metadata very FATish, adding compression
related metadata at a low profile place (eg replace the 2nd
copy of the FAT) and compress only the data clusters.

Eric :-)



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel





-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net

Re: [Freedos-devel] compressed FAT filesystems

2008-03-20 Thread Eric Auer

Hi Imre,

 Does the fact that all this runs on linux slip your mind
 (like in no way  interesting for the stated purpose).

Some of the filesystems claim to be implemented in only
4 kilobytes of code. Which is a lot smaller than the FAT
engine in the FreeDOS kernel, for example. If you made
a variant of our kernel with FAT removed and one of the
small readonly FS implemented, you could get more of
DOS into for example a flash BIOS. Of course removing
FAT would introduce all sorts of limitations so it is
only useful if not even a FAT ramdisk is expected to be
used in this boots DOS in BIOS example... In any case,
the suggested filesystems are all potentially USEFUL for
DOS even though their reference implementation is Linux.

 Seriously, how is any of that supposed to be running in DOS?
 It's mainly not even embedded (like a set of operating system
 services you can embed in a microcontroller application).

Neither LEAN nor any of the proposed compressed file systems
are implemented in any default DOS kernel. So it does not
make a difference whether you compile a FreeDOS driver or
modified FreeDOS kernel for LEAN or rather for some of the
compressed filesystems as long as the specs or the source
code for the filesystem handling are freely available.

I agree that there is no free open source compressed file
system which you can just drop in and run to install.
But you can port or implement a system of your choice...

This is still much better compared to the situation when
only proprietary / patented / closed source systems are
available, for example WinCE/Vista's exFAT.

Eric



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems (totaly OT)

2008-03-20 Thread Imre Leber
First let me state that I realy shouldn't be writin posts like this.

Altough I think that people online usualy do talk/write like this. Somebody new 
to the list may not appreciate it. So for everyone not enjoying the foklore, 
sorry.

This makes me think also about what is said about second life (and world of 
warcraft). People online talk much more direct, but people might not always 
apreciate it.

Anyway if anybody would like to build a virtual presence for FreeDOS in second 
life. That would be so cool.

Imre




- Oorspronkelijk bericht -
Van: Imre Leber [mailto:[EMAIL PROTECTED]
Verzonden: donderdag, maart 20, 2008 12:43 PM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Does the fact that all this runs on linux slip your mind (like in no way 
interesting for the stated purpose).

Seriously, how is any of that supposed to be running in DOS? It's mainly not 
even embedded (like a set of operating system services you can embed in a 
microcontroller application).

Imre


- Oorspronkelijk bericht -
Van: Eric Auer [mailto:[EMAIL PROTECTED]
Verzonden: donderdag, maart 20, 2008 03:33 AM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Hi Imre,

 Which free/open compressed embedded filesystems would that be?

Browsing wikipedia a bit gives me quite a few READONLY free and
open source compressed filesystems, several of which are useful
for embedded systems. For writeability, you would typically have
to alloc new space in your filesystem whenever a changed cluster
no longer fits (in compressed form) into where it was before.
Then you need the ability to have the storage locations of the
cluster contents be nonlinear, and you need some way to find
unused areas and either re-use them on the fly or defrag them
out of the filesystem with an offline (while the filesystem
is not used) tool. Luckily a readonly compressed filesystem is
very useful for various things already, so you can make people
happy with one of the simple readonly systems listed below :-).



http://en.wikipedia.org/wiki/Cramfs - for ROM, GPLed, uses zlib,
each page is compressed separately, metadata is not compressed,
max 16 MB / file, 256 MB / filesystem


http://en.wikipedia.org/wiki/SquashFS - GPLed, readonly, uses gzip,
used for several LiveCD versions of Linuxes, compresses data and
metadata in chunks of up to 1 MB each... Max 2^64 bytes per file.
Default block size 128 kB.


http://en.wikipedia.org/wiki/Zisofs - Linux, basically ISO9660
with extra flag to mark compressed files, it seems ;-). This
means that uncompressed files on Zisofs can be accessed by any
ISO9660 capable driver and operating system :-).


http://en.wikipedia.org/wiki/Cloop - Linux, simply a wrapper to
store a compressed block device image on a block device, it seems.
Compressed images contain a seek index with compressed and un-
compressed block sizes in pairs and the zlib compressed blocks.
I assume you get the offset of a compressed block by summing up
the sizes of the compressed blocks before it. Wikipedia says that
Apple DMG has a similar design.


http://logfs.org/logfs/LogFS - GPLed successor for JFFS2, for
flash devices... Seems to be work in progress


http://lxr.linux.no/linux/Documentation/filesystems/romfs.txt
A really simple filesystem: Main content is a linked list of
files, each file consisting of a header and the data of the
file, all aligned to 16 byte boundaries. Header contains:
Link, flags, size, checksum, max 15 bytes of name. You can
easily introduce a flag for compressed files. The link has
28 bit (high 28 bit of offset), leaving 36 bits for flags.

Flags are type (hardlink, dir, file, symlink, block device,
char device, socket, fifo) plus extra info. Hardlink info:
Offset pointer. Dir info: First file pointer. Device info:
The major and minor number. Symlink info: None - instead,
the file content is the symlink string. The . and ..
of directories are stored as normal directory entries, the
same idea as in FAT.



 Add a compression attribute to the inode structure in LEAN. And then
 put the compressed data into the file.

Tools have done the same for FAT: Use an unused bit or combination
of bits in the file attribute to mark a file as compressed, or use
some sort of header in the file contents...

The suggestion of my previous mail is a bit similar to CramFS
and Cloop in design, but my main idea is to have a filesystem
which stays similar to FAT and where it is easy to transform
a FAT system into a compressed one with a tool and for the
other way round make a compressed FAT system look like it was
a normal one with a driver for the other way round, making it
possible for the FreeDOS kernel to mount it easily :-).

This includes keeping metadata very FATish, adding compression
related metadata at a low profile place (eg replace the 2nd
copy of the FAT) and compress only the data clusters.

Eric

Re: [Freedos-devel] compressed FAT filesystems

2008-03-20 Thread Imre Leber
No what I mean with this is that if it is a linux driver it means that it is 
inherently linked to the internals of linux. I wouldn't think that this would 
be very easy to port to anything. At least not unless you would implement the 
entire virtual file system layer of linux first.

What I did not see was an overview of the structure of the operating system. 
Just claims that it does all sorts of things. But no document specification, 
like the one for LEAN.


Imre

- Oorspronkelijk bericht -
Van: Eric Auer [mailto:[EMAIL PROTECTED]
Verzonden: donderdag, maart 20, 2008 01:19 PM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Hi Imre,

 Does the fact that all this runs on linux slip your mind
 (like in no way  interesting for the stated purpose).

Some of the filesystems claim to be implemented in only
4 kilobytes of code. Which is a lot smaller than the FAT
engine in the FreeDOS kernel, for example. If you made
a variant of our kernel with FAT removed and one of the
small readonly FS implemented, you could get more of
DOS into for example a flash BIOS. Of course removing
FAT would introduce all sorts of limitations so it is
only useful if not even a FAT ramdisk is expected to be
used in this boots DOS in BIOS example... In any case,
the suggested filesystems are all potentially USEFUL for
DOS even though their reference implementation is Linux.

 Seriously, how is any of that supposed to be running in DOS?
 It's mainly not even embedded (like a set of operating system
 services you can embed in a microcontroller application).

Neither LEAN nor any of the proposed compressed file systems
are implemented in any default DOS kernel. So it does not
make a difference whether you compile a FreeDOS driver or
modified FreeDOS kernel for LEAN or rather for some of the
compressed filesystems as long as the specs or the source
code for the filesystem handling are freely available.

I agree that there is no free open source compressed file
system which you can just drop in and run to install.
But you can port or implement a system of your choice...

This is still much better compared to the situation when
only proprietary / patented / closed source systems are
available, for example WinCE/Vista's exFAT.

Eric



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel





-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-20 Thread Imre Leber
You did however make the very valid point that implementing a compressed file 
system is not so easy as one might think.

There is indeed a problem with random access in a stream. That is not very 
trivial to solve. But it shouldn't be overly difficult either.

Imre


- Oorspronkelijk bericht -
Van: Eric Auer [mailto:[EMAIL PROTECTED]
Verzonden: donderdag, maart 20, 2008 01:19 PM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems


Hi Imre,

 Does the fact that all this runs on linux slip your mind
 (like in no way  interesting for the stated purpose).

Some of the filesystems claim to be implemented in only
4 kilobytes of code. Which is a lot smaller than the FAT
engine in the FreeDOS kernel, for example. If you made
a variant of our kernel with FAT removed and one of the
small readonly FS implemented, you could get more of
DOS into for example a flash BIOS. Of course removing
FAT would introduce all sorts of limitations so it is
only useful if not even a FAT ramdisk is expected to be
used in this boots DOS in BIOS example... In any case,
the suggested filesystems are all potentially USEFUL for
DOS even though their reference implementation is Linux.

 Seriously, how is any of that supposed to be running in DOS?
 It's mainly not even embedded (like a set of operating system
 services you can embed in a microcontroller application).

Neither LEAN nor any of the proposed compressed file systems
are implemented in any default DOS kernel. So it does not
make a difference whether you compile a FreeDOS driver or
modified FreeDOS kernel for LEAN or rather for some of the
compressed filesystems as long as the specs or the source
code for the filesystem handling are freely available.

I agree that there is no free open source compressed file
system which you can just drop in and run to install.
But you can port or implement a system of your choice...

This is still much better compared to the situation when
only proprietary / patented / closed source systems are
available, for example WinCE/Vista's exFAT.

Eric



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel





-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-20 Thread Eric Auer

Hoi Imre,

 You did however make the very valid point that implementing a
 compressed file system is not so easy as one might think.

Luckily the task gets a lot easier if the filesystem will be
readonly (tool to create it, driver to read it). And such a
filesystem is still pretty useful :-).



 There is indeed a problem with random access in a stream.
 That is not very trivial to solve. But it shouldn't be overly
 difficult either.

Most compressed filesystems mentioned work around this
problem by compressing the data in blocks, for example
each cluster separately. The compressed blocks can start
at any offset, but offsets are typically rounded to a
multiple of, for example, the physical sector size. If
you use big blocks, you have to decompress more data
(and possibly eat more CPU and RAM) before you can get
to the decompressed data at the end of a block. But if
you use small blocks, you get worse compression rates
as you have less context to compress redundant data.

Your driver either needs to buffer a whole decompressed
block or it will have to decompress the same block more
than once whenever the operating system wants to read
a part of the block. In most OSes, the operating system
always reads whole 512 byte sectors, but some OSes will
read whole clusters and others only read those parts of
a cluster that you actually have to access at a time.



As BIOS disk drivers cannot access high memory directly
and EMS pages are a bad idea for filesystem drivers as
you might have some app which uses EMS concurrently, you
typically have to put decompression buffers into a DOS
low memory space or at least into UMB space... Because
you want to avoid double decompression CPU overhead, you
probably want to limit the compression block size based
on how much DOS RAM you want to give a filesystem driver.

Doing LZSS on chunks of 4k or 8k size would be a start :-).
For comparison, FAT16 normally uses 2k or more per cluster,
FAT12 (harddisk variant) and FAT32 (if filesystem  1/4 GB)
use 4k or more per cluster. Min/Max are always 0.5k/32k if
you want good compatibility (else 64k / even(?) 0.5-127.5k
cluster sizes, sector sizes from 32/64/128 to 512by or 2k).



 No what I mean with this is that if it is a linux driver it
 means that it is inherently linked to the internals of linux.

True. A Linux driver is more likely to be portable to SHSUCDX
style drivers than to our kernel. Still worth a try. The idea
is that SHSUCDX provides more semantic primitives (files
and directories etc) while the kernel built-in driver for
FAT operates in a more lowlevel way on FAT formatted disks
(block devices). Of course SHSUCDX itself also connects to
a kernel interface for the semantic side of a filesystem
(cdrom, network...). So we have a choice of interfaces.



 What I did not see was an overview of the structure of the OS

Well for romfs, the URL actually points to a spec for the FS.
I did not even look for an implementation of that one...

A more DOS friendly compressed filesystem would be one which
is FAT-ish with compressed data clusters, as suggested in the
post which started this thread :-). A driver for such a FAT-
ish compressed filesystem could give DOS a readonly block
device, and it would only have to implement basic knowledge
about the compression structures and the transformation into
normal FAT when DOS reads data or metadata. A DOS driver for
a FAT-ish compressed filesystem does not have to understand
anything about directory entries or FAT chains actually :-).

Eric


-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems (was: defrag methods)

2008-03-19 Thread Imre Leber

- Oorspronkelijk bericht -
Van: Eric Auer [mailto:[EMAIL PROTECTED]
Verzonden: dinsdag, maart 18, 2008 10:38 PM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: [Freedos-devel] compressed FAT filesystems (was: defrag methods)


Hi!

 Maybe with adding compression it could make a replacement for
 doublespace? (running it through the network redirector obviously)

Nope, doublespace compresses the actual data on your disk,
not the space which is free anyway ;-). I think it would be
nice to have a driver for one of those free / open compressed
embedded filesystems for DOS. Some ad-hoc suggestions for a
new filesystem.

Which free/open compressed embedded filesystems would that be? Serieus, the 
other day I read an entire thread on an electronics forum about there not being 
any of those. (That is why I have completed my own file system, 
FAT12/FAT16/FAT32 with LFN support, with C interface). 

Further more that is also what I intended to say. Add a compression attribute 
to the inode structure in LEAN. And then put the compressed data into the file.

Further more, the only reason one would use FAT is that it is compatible with a 
1001 number of tools. If you are going to make an incompatible system, at least 
base it on a more sensible design. That way you also don't have to care about 
microsoft patents and stuff.

Imre

Eric



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel





-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems (was: defrag methods)

2008-03-19 Thread Imre Leber

- Oorspronkelijk bericht -
Van: Aitor Santamar?a [mailto:[EMAIL PROTECTED]
Verzonden: woensdag, maart 19, 2008 01:45 AM
Aan: freedos-devel@lists.sourceforge.net
Onderwerp: Re: [Freedos-devel] compressed FAT filesystems (was: defrag methods)

One more thing: the big deal about DoubleSpace/DriveSpace is not the
compression itself, which could of course increase your free space,
but mostly comes from the variable-sector-per-cluster stuff: you get
lots of extra free space by cutting the space occupied by the many,
say, less than 1KB text files in a 8KB/cluster FAT fs.


Yes, and LEAN doesn't use clusters. So the maximum you can loose per file is 
511 bytes, not 8KB.

Imre

Just my 2c...
AItor





-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


Re: [Freedos-devel] compressed FAT filesystems

2008-03-19 Thread Eric Auer

Hi Imre,

 Which free/open compressed embedded filesystems would that be?

Browsing wikipedia a bit gives me quite a few READONLY free and
open source compressed filesystems, several of which are useful
for embedded systems. For writeability, you would typically have
to alloc new space in your filesystem whenever a changed cluster
no longer fits (in compressed form) into where it was before.
Then you need the ability to have the storage locations of the
cluster contents be nonlinear, and you need some way to find
unused areas and either re-use them on the fly or defrag them
out of the filesystem with an offline (while the filesystem
is not used) tool. Luckily a readonly compressed filesystem is
very useful for various things already, so you can make people
happy with one of the simple readonly systems listed below :-).



http://en.wikipedia.org/wiki/Cramfs - for ROM, GPLed, uses zlib,
each page is compressed separately, metadata is not compressed,
max 16 MB / file, 256 MB / filesystem


http://en.wikipedia.org/wiki/SquashFS - GPLed, readonly, uses gzip,
used for several LiveCD versions of Linuxes, compresses data and
metadata in chunks of up to 1 MB each... Max 2^64 bytes per file.
Default block size 128 kB.


http://en.wikipedia.org/wiki/Zisofs - Linux, basically ISO9660
with extra flag to mark compressed files, it seems ;-). This
means that uncompressed files on Zisofs can be accessed by any
ISO9660 capable driver and operating system :-).


http://en.wikipedia.org/wiki/Cloop - Linux, simply a wrapper to
store a compressed block device image on a block device, it seems.
Compressed images contain a seek index with compressed and un-
compressed block sizes in pairs and the zlib compressed blocks.
I assume you get the offset of a compressed block by summing up
the sizes of the compressed blocks before it. Wikipedia says that
Apple DMG has a similar design.


http://logfs.org/logfs/LogFS - GPLed successor for JFFS2, for
flash devices... Seems to be work in progress


http://lxr.linux.no/linux/Documentation/filesystems/romfs.txt
A really simple filesystem: Main content is a linked list of
files, each file consisting of a header and the data of the
file, all aligned to 16 byte boundaries. Header contains:
Link, flags, size, checksum, max 15 bytes of name. You can
easily introduce a flag for compressed files. The link has
28 bit (high 28 bit of offset), leaving 36 bits for flags.

Flags are type (hardlink, dir, file, symlink, block device,
char device, socket, fifo) plus extra info. Hardlink info:
Offset pointer. Dir info: First file pointer. Device info:
The major and minor number. Symlink info: None - instead,
the file content is the symlink string. The . and ..
of directories are stored as normal directory entries, the
same idea as in FAT.



 Add a compression attribute to the inode structure in LEAN. And then
 put the compressed data into the file.

Tools have done the same for FAT: Use an unused bit or combination
of bits in the file attribute to mark a file as compressed, or use
some sort of header in the file contents...

The suggestion of my previous mail is a bit similar to CramFS
and Cloop in design, but my main idea is to have a filesystem
which stays similar to FAT and where it is easy to transform
a FAT system into a compressed one with a tool and for the
other way round make a compressed FAT system look like it was
a normal one with a driver for the other way round, making it
possible for the FreeDOS kernel to mount it easily :-).

This includes keeping metadata very FATish, adding compression
related metadata at a low profile place (eg replace the 2nd
copy of the FAT) and compress only the data clusters.

Eric :-)



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel


[Freedos-devel] compressed FAT filesystems (was: defrag methods)

2008-03-18 Thread Eric Auer

Hi!

 Maybe with adding compression it could make a replacement for
 doublespace? (running it through the network redirector obviously)

Nope, doublespace compresses the actual data on your disk,
not the space which is free anyway ;-). I think it would be
nice to have a driver for one of those free / open compressed
embedded filesystems for DOS. Some ad-hoc suggestions for a
new filesystem:

Keep a normal FAT and boot sector and stuff, but wrap all the
access to the data clusters. For each data cluster, keep some
pointer to where it ACTUALLY starts (granularity: cluster, sector
or byte) and allow the clusters to be compressed. You would need
some offline make compressed version of this filesystem tool
and you would not be able to write to the filesystem later.
To get a relatively simple implementation, you can assume that
each cluster is separately compressed, for example with LZSS.
Then you only look at one cluster at a time for uncompressing.

Max amount of extra metadata: 32 bits per cluster. Note that
you do not store the size of the compressed cluster nor any
this cluster is not compressed flag - you can easily derive
those from the difference between this and next cluster start.

To reduce the space taken by the extra metadata, you can use
a more granular offset for the actual data location, and
you can compress the offset array by only storing the size of
each compressed cluster instead of its offset. To avoid too
much speed loss, you could still keep the offset of every Nth
cluster in some array in RAM to reduce the needed counting.
You can even store the size of each compressed cluster in a
granular way, eg by saying that each compressed cluster has
to start at a sector boundary and thereby is a multiple of a
sector size in compressed size (ignore trailing garbage).

That way, you can get by with for example 1 byte of extra
metadata per cluster. Actually the whole special tables for
compressed filesystem stuff could be stored at the space
taken by the second FAT :-). Then a compressed filesystem
can not take more space than the uncompressed version even
in the worst case of all filled with uncompressible files.

Just some inspiration for the compressed FAT FS dreamers :-D.

Eric



-
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse012070mrt/direct/01/
___
Freedos-devel mailing list
Freedos-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/freedos-devel