From: oles@spectra (Shawn Oles) Subject: Re: Stacker like file system Date: Sun, 30 Aug 1992 02:49:15 GMT
In article <1992Aug28.223823.9755@uoft02.utoledo.edu> billp@jupiter.cse.utoledo.edu (Bill Parquet) writes:
>mfp+@CS.CMU.EDU (Michael Polis) writes:
>: |> Having a /usr/compressed/pics directory with on-the-fly compression would be
>: |> a dream come true.
>: How about storing them as GIF's, which are inherently compressed using
>: the LZW algorithm (the one used by compress).
>
>There's a few disadvantages to using GIF format. Most namely is the
>restriction to 256 colors.
>
>What kind of compression technique do those
>programs [stacker/doubledisk/etc] use? (Hopefully this isn't the start of
I am not sure about the other companies, but stacker is based on Stac Electronics
QIC-122 compression standard which is briefly discussed in "The Data
Compression Book" (Nelson, 91 pg 228). Basically it uses a variant of the
Ziv-Lempel Dictionary discussed in their 1978 paper and exploited by Welch
in the algorithm LZW. There are a wealth of books on data compression. Read
the FAQ in comp.compression for more detail.
>a completely unrelated discussion) ... The only thing that I think gets
>really ugly about those programs if you have a file that contians a block
>of zeros in the middle, then you have a program that fseeks to that block
>and writes a block of random data over it. The compression program has
>to deal with expansion in the physical file size.
easy. If blocks are compressed at the block level, as we have been discussing,
the new block can be re-written in the middle of the file independently of ALL
other blocks in the file; thus just the modified block, with its new size, is
written. This not as easy as a normal modify but is doable.
This does lead to a few problems, most notably, if the file system is full and
the modified block size increases, it is possible that the file system
will have to generate an "no space on device" type error message, which
might break a few programs.
One place where this worries me slightly, is what happens if
a) if the file system is full
b) and the user deletes a file, which modifies the block containing the
files directory entry
c) and the modified directory block expands (which is highly unlikely, but
possible)
if this occurs, then the user will not be able to remove the directory
entry, and might lead to a corrupted file system.
Anyway, the easy solution is just to panic("your screwed\n"); and recomend
a reformat. :) This is a highly unlikely senario, but still bothers me.
-shawn
---shawn