Help on designing new file archiver format

[Lasse Reinhold]

I want to create a real file archiver format for QuickLZ and have a few questions.

a) Is there any reason to have the header (file list, etc) in the beginning of the file archive instead of having it at the end? The first method requires backwards seeking into the file/device at compression which I want to avoid.

b) Are there any good (and fast!) alternatives to Adler32 which doesn't have that "missing wrap flaw" for small files?

c) What can I do to make it easy for 3'rd parties to support compression/decompression in their archiver tools? How is this usually handled?

Any other important considerations?

Lasse

[giorgiotani]

Hi, I hope my opinion on the subject may help:

a) there is not a wrong and right way to implement this, you can even decide to pre-scan the archive searching for header's area at the end of the archive i.e., read the last word of the archive, which contains the size of the header, then start reading header at archive size - header size, which usually will have a verry small impact on performances.
However writing the header at the beginning of the file may avoid some annoyances, i.e. if the archive is spanned on multiple volumes on removable devices you will need to ask the users to provide last volume (hoping it contains all the header, otherwise ask a previous one) and then provide the first one afret the header was read.

b) usually CRC32 is preferred to Adler32 even if the latter is simpler to implement; however a good CRC32 implementation is almost as fast as Adler32.

c) that may vary; in *x world in example there is a strong emphasis on pipelining application, so it will be preferred an application capable of running without GUI, able to accept parameters and to comminicate with other applications (see in example how tar and gz/bz2 works, or how Linux archivers support external binaries for extending archive format support).
On Windows instead it will be usually preferred a dll exposing archiving functions to be called from main program's executable.

About other considerations, IMHO you should think about what do you want from the archive format in term of additional properties and expected usage target:
What filesystem information are you going to store? That will be relevant expecially if the format is targeted also for backup purpouse; will be Unix or NT access and/or security policies saved?
Will the format need to implement cryptography?
Do you plan to allow volume spanning?
Will the archive contain recovery records for repairing attempts?
I think those are the most relevant additional topics to keep in mind designing an archive format, but certainly the list can't be exaustive.

[Bulat Ziganshin]

but certainly the list cant be exaustive.

but format can be (and should be!) extensible

a) Is there any reason to have the header (file list, etc) in the beginning of the file archive instead of having it at the end?

its a three-sided sword

a) directory at the beginning, a-la cabarc - decompression can be implemented with sequential file read, but compression requires to create temporary files

b) dir at the end, like 7zip/freearc. compression is sequential, but decompression need to lseek the archive file. its much less work, though, that creating temporary files, so its selected in our programs

c) dir entry before each file, like in TAR. allows to make both compression and decompression sequential, what is essential in unix world, but has its own obvious disadvantages

However writing the header at the beginning of the file may avoid some annoyances, i.e. if the archive is spanned on multiple volumes

there are many ways to implement volume splitting inside archiver. if we just go to split archive file into pieces with external utility, then we again should select between easiness of archive creation and extracting

c) What can I do to make it easy for 3rd parties to support compression/decompression in their archiver tools? How is this usually handled?

windows: unrar.dll and optionally unrar sources

Any other important considerations?

this depends on how much time you are ready to spend on this project. i suggest you to start with teaching existing archive formats, especially 7-zip. PeaZip is interesting for its great encryption/authentication support.

my own archive format imho is most flexible and powerful one, although it may be too complex to implement. when i developed it, ive written some notes and now i will try to translate them into English. now i know some weak sides of my current format and plan to improve it somewhere in 0.50, so you can readily start with even better one

[giorgiotani]

c) dir entry before each file, like in TAR. allows to make both compression and decompression sequential, what is must be in unix worls, but has its own obvious disadvantages

To further clarify it (btw, this is the solution I used in PEA format), the obvious shortcoming of this scheme is that the program browsing the archive will need to browse the whole archive to perform a list command, and to browse the archive until the selected object is found to extract it; that is much less efficient than other two schemes (with contiguously listed content and offset indexes for non sequential access to archives content).

there are many ways to implement volume splitting inside archiver. if we just go to split archive file into pieces with external utility, then we again should select between easiness of archive creation and extracting

Yes, I was thinking to a single pass archiving scheme which is inherently more complex to implement, and the degree of complexity is useless if volume spanning is not used which may occour most of the times.
However a two pass scheme with external utility for volume spanning will have some disvantages (i.e. requires temporary files and double disk time) unless we have the two applications able to pipeline the work like tar/gz on *x, but this requires a bit more of complexity too.

PeaZip is interesting for its great encryption/authentication support.

Thanks a lot for the appreciation!
I think in a modern archive format, if encryption is taken in account, an authenticated encryption scheme should be definitely used rather than classic encryption only schemes; otherwise I would recommend AES (Twofish and Serpent are good too, but today AES should be the first choice because more used and consequently more tested) in CTR mode: fast, efficient, well known and understood by analists, with provable security properties.

[Bulat Ziganshin]

Quoting: Bulat Ziganshin
there are many ways to implement volume splitting inside archiver. Yes, I was thinking to a single pass archiving scheme

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

[QUOTE=Bulat Ziganshin
there are many ways to implement volume splitting inside archiver. Yes, I was thinking to a single pass archiving scheme [/QUOTE]

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

[QUOTE=Bulat Ziganshin
there are many ways to implement volume splitting inside archiver. Yes, I was thinking to a single pass archiving scheme [/QUOTE]

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

[QUOTE=Bulat Ziganshin
there are many ways to implement volume splitting inside archiver. Yes, I was thinking to a single pass archiving scheme [/QUOTE]

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

[QUOTE=Bulat Ziganshin
there are many ways to implement volume splitting inside archiver. Yes, I was thinking to a single pass archiving scheme [/QUOTE]

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

[QUOTE=Bulat Ziganshin
there are many ways to implement volume splitting inside archiver. Yes, I was thinking to a single pass archiving scheme [/QUOTE]

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

there are many ways to implement such scheme. you may put directory of volume at the volume end, you may even ensure that volumes may be extracted separately, as it was done in arj format

<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.

well, we say here only about archive format. if encryption/authentication should be used, one should carefully plan which parts of archive should be encrypted/authd. in particluar, i declined from implementing auth. in fa 0.40 because i need to ensure that every part of archive are signed - its a more strict requirement than just encrypt parts that has interesting information. for example, i should resist against just appendding to the archive "false archive" which contains enemys data

<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.

well, we say here only about archive format. if encryption/authentication should be used, one should carefully plan which parts of archive should be encrypted/authd. in particluar, i declined from implementing auth. in fa 0.40 because i need to ensure that every part of archive are signed - its a more strict requirement than just encrypt parts that has interesting information. for example, i should resist against just appendding to the archive "false archive" which contains enemys data

<div class=""quoting"">Quoting: giorgiotani

dir entry before each file, like in TAR.]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.

well, we say here only about archive format. if encryption/authentication should be used, one should carefully plan which parts of archive should be encrypted/authd. in particluar, i declined from implementing auth. in fa 0.40 because i need to ensure that every part of archive are signed - its a more strict requirement than just encrypt parts that has interesting information. for example, i should resist against just appendding to the archive "false archive" which contains enemys data

<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.]<div class=""quoting"">Quoting: giorgiotani]<div class=""quoting"">Quoting: giorgiotani

PeaZip is interesting for its great encryption/authentication support.

well, we say here only about archive format. if encryption/authentication should be used, one should carefully plan which parts of archive should be encrypted/authd. in particluar, i declined from implementing auth. in fa 0.40 because i need to ensure that every part of archive are signed - its a more strict requirement than just encrypt parts that has interesting information. for example, i should resist against just appendding to the archive "false archive" which contains enemys data

<div class=""quoting"">Quoting: giorgiotani

dir entry before each file, like in TAR.

one more variant is to place before each compressed block list of files in this block. in this case, we are limited to do just one read per each, say, 8 mb of archive. we can also compress directory blocks if they contain large amounts of files. this also makes archive more robust - data and directory lies together so damages in other parts of archive dont disturb us

[nimdamsk]

CRC32 is no way as fast as Adler32. But with it's speed who cares? See http://www.cryptopp.com/benchmarks.html

[giorgiotani]

Fine tuning both algorithms Adler32 keep a good speed advantage (I thought not so big as in the example linked, probably this morning I was recalling obsolete or less optimized benchmarks, I apologize).

But with its speed who cares?

Yes, probably the performance penalty will be not noticeable in a tipical case of use for an archiving application.
As the speed of both algorithm is well beyond disk read/write speed, it would probably dont change too much for the user even in a single threaded application, and nothing in a multithreaded application since any of the two algorithms can mangle the data of one block before the next is read from the disk.
It would probably be proportionally more noticeable if the data is in the RAM, but in this case the process would probably be so fast that in any case that the user will not complain.

[nimdamsk]

Some more links FYI:
http://www.winimage.com/readfile.htm
http://www.winimage.com/misc/readfile_test.htm

[Piotr Tarsa]

CRC32 is no way as fast as Adler32. But with its speed who cares? See http://www.cryptopp.com/benchmarks.html

afair igor pavlov developed algorithm that computes crc- 32 code using 1.2 cycles per byte. search 7- zip forum for details.

[Bulat Ziganshin]

it's 7zCrcT8U.asm in http://belnet.dl.sourceforge.net/sourceforge/p7zip /p7zip_4.55_src_all.tar.bz2

[Lasse Reinhold]

Thanks alot for all the input on different aspects

Bulat - if you'll get time to translate it, post a note here.