Re: [Freedos-devel] compressed FAT filesystems
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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)
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
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
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
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)
- 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)
- 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
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)
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
