New archive file format (was: [omgps] collect feature requests)
jerjoz.forums at gmail.com
Wed Jul 1 23:25:14 CEST 2009
On Wed, Jul 1, 2009 at 2:20 PM, Laszlo
KREKACS<laszlo.krekacs.list at gmail.com> wrote:
>> I dont want to compress at all. The 118MB for me is perfect. I only
>> want to pack the directory into a file. But not compressing.
>> Im thinking about tar or ar.
> I have studied all the available archive and compression options.
> Most notably tar and zip file format .
> They are the most common archive types. I read also ar (dpkg
> and ipkg uses it) and cpio format. So I did my homework, and
> made some researches.
> Our requirements:
> - no compression (no wasted cpu time)
> - random access (no slow waiting time and memory issue)
> - readily available module/library for easy of integrating
> (best: no additional package is required to install on the phone)
> Tar completely fail at random access, simply it lacks the
> table of content, so accessing the last file in the archive
> requires reading the whole content before it.
> Zip support accessing each files in the archive, although
> it compress the file by default.
> There are dar and xar, which meets our random access
> criteria. However dar needs to be ported to the device, and
> xar is still in development (that means limited python support
> for example).
> So I wrote down the most dumb archive fileformat ever;)
> When I wrote the specification, I only had one goal:
> make it so simple, that everybody can implement it,
> so no need to wait for ready-made library.
> It is called KISS fileformat (keep it simple and stupid),
> the preferred extension would be filename.kiss
> You can read it here, I also included it (at the end of mail)
> for reference:
> I think it is suitable for our map tile usage.
> What do you think?
> Best regards,
> : http://en.wikipedia.org/wiki/Tar_(file_format)
> : http://www.python.org/doc/2.5.2/lib/module-tarfile.html
> : http://www.python.org/doc/2.5.2/lib/module-zipfile.html
> : http://en.wikipedia.org/wiki/Comparison_of_file_archivers
> : http://en.wikipedia.org/wiki/DAR_(Disk_Archiver)
> : http://en.wikipedia.org/wiki/Archive_formats
> : http://code.google.com/p/xar/
> KISS archive fileformat specification:
> # KISS archive format (Keep It Simple and Stupid)
> ## General properties
> - blocksize: 512 bytes
> - only store filename (and directory if any) and content
> - first file contains the filenames
> - header: start block, end block, position of last block
> ## Overall file structure
> [header][filenames][1. file][2. file][3. file]
> ## [header]
> [SB][EB][POS] [SB][EB][POS] [SB][EB][POS] etc..
> [ 4][ 4][ 2] [ 4][ 4][ 2] [ 4][ 4][ 2] etc..
> [ header ] [ filenames ] [1. file ] etc..
> SB (start block): 4 byte
> EB (end block): 4 byte
> POS (position of last block): 2 byte
> All numbers are stored big-endian. That means most significant bit first.
> 613 dec = 265 hex = \00 \00 \02 \65 (4 bytes)
> 130411 dec = 1FD6B hex = \00 \01 \FD \6B (4 bytes)
> The remaining part of the header block MUST be filled with zero bytes.
> You will always have remaining part in the block, simply each file
> takes 10 bytes. (512/10 = 51 and 2 bytes left)
> ## [filenames]
> UTF-8 text for each filename, delimited with '\n' byte.
> The directory structure is preserved too.
> [name of 1. file]['\n'][name of 2. file]['\n'][name of 3. file] etc..
> Some examples:
> this is a file.txt
> weird_dir/this\/files contains\/several\\ slashes.txt
> Special characters:
> '\n': You cant have '\n' character in the filename. It is preserved.
> (it is not supported in most filesystems anyway)
> '/': directory delimiter. To save directory structure.
> '\/': if the filename itself contains an / character
> '\\': if the filename itself contains a \ character
> ## [X. file]
> The file content as is.
> ## FAQ:
> Q: Why another archive format?
> A: Because it is the most dumb format ever;)
> Q: Why not tar, ar, zip, [name archive type here]?
> A: Short answer: widely used archive format are not suited for random access
> with no compression.
> Long answer: tar: there is no index, reading the last file of the archive
> requires reading the whole file before it.
> zip: individual files are compressed, which means: processortime
> xar: it would fit the requirements, but it is not widely
> supported, and not in every language.
> Q: I use X language does KISS supported there?
> A: The fileformat is so simple, it is intented, every programmer
> could implement it in "no time".
> Q: Does compression supported?
> A: No. But you can compress the whole file,
> just like in tar case: filename.kiss.bz2. Use it for file sharing.
> Q: Do advanced features (rights, symlinks, hardlinks, user/group/other) are
> A: No. It was not the goal of this archive. Although you can implement it, just
> write those informations in the first file. It is not recommended.
> Q: If the original file is not multiple of 512 bytes, how it will look in the
> archive, how many bytes will it take?
> A: Lets have an example. We have three files:
> 768bytes file, 1024 bytes, 2047 bytes
> First file (768 bytes) will take two blocks: 2*512 = 1024 bytes
> Second file (1024 bytes) will take two blocks too: 2*512 = 1024 bytes
> Third file (2047 bytes) will take four blocks: 4*512 = 2048 bytes
> Lets name the files:
> - "first filename.extension", (24 bytes)
> - "second try", (10 bytes)
> - "I want a sexy name.txt", (22 bytes)
> The [filenames] section:
> [24 bytes][1 byte][10 bytes][1 byte][22 bytes] = 58bytes = 1 block
> The header ([SB][EB][POS]):
> [00 00 00 00][00 00 00 00][00 31] (this is the header itself, start at the
> 0. block, ends at 0. block, and
> the header is 50 bytes long. That means
> start at the 0. byte and
> ends at the at the 49. byte.
> (0..49 = 50 bytes, which is 0x31))
> [00 00 00 01][00 00 00 01][00 39] (58 byte long, that means 0..57 bytes
> and 57 dec = 0x39 hexa)
> [00 00 00 02][00 00 00 03][00 FF] (768-512 = 256, so 0..255 bytes.
> 255dec = FF hexa)
> [00 00 00 04][00 00 00 05][01 FF] (1024 bytes = 2 blocks, the
> second is full)
> [00 00 00 06][00 00 00 09][01 FE] ( 2047-(3*512) = 511. 510dec = 1FE hexa)
> The overall filesize:
> [header][filenames][1. file][2. file][3. file]
> [ 1 ][ 1 ][ 2 ][ 2 ][ 4 ] = 10 blocks = 5120B = 5kB
> Q: How is it filled the unused part of the block (if the file is
> not multiple of 512 bytes) ?
> A: It can be random bytes. But should be zero bytes. Or checksum if there is
> enough space left (see section "An insane idea for checksums").
> ## Implementation advices
> 1. Count the files what you want to archive -> you know how much
> space is required by the header. 1-49 files requires one block for the header
> (10 bytes for the header, 10 bytes for the filenames section, x*10 bytes
> for the files itself. Maximum x is 49 for one block)
> 2. dump 0xFF for the header (look at the "tape archiving" to understand why FF)
> 3. Generate the filenames section and write the filenames section.
> 4. Attache each file to the archive, and generate the header
> on-the-fly (in memory)
> 4. Overwrite the header with valid data.
> ## An insane idea for checksums (integrity checking)
> Here is the idea, write the checksum at the remaining space, if the
> file is multiple of 512 byte, write two checksums at the next end of file,
> if there is no enough space, write it at the next file, and so on.
> If each file was multiple of 512 bytes, or there are not enough space
> at the end of each files. There will be no checksum for some of the last files
> (but it is always better then having no checksums at all).
> Which should be rare, but if you are worried about it, you can always add
> a new file with all the necessary informations.
> This section is not mandatory for the fileformat. So if you are brave enough,
> implement it! If you dont care, no worries.
> CRC32 is 4 bytes (32 bits) long.
> I think 4bytes should be safe enough;)
> A little example code in python how to calculate it:
> import binascii
> def crc2hex(crc):
> for i in range(4):
> t=crc & 0xFF
> crc >>= 8
> res='%02X%s' % (t, res)
> return res
> if __name__=='__main__':
> test='hello world! and Python too ;)'
> print 'CRC:', crc
> hex_str = crc2hex(crc)
> print 'CRC in hex:', hex_str
> print 'in byte representation: ', hex_str.decode("hex")
> MD5sum is 16bytes long.
> The CRC32 (4bytes) is recommended. It is enough to detect inconsistencies.
> ## An another insane idea for tape archiving
> Who the hell use tapes these days?;)
> So if the first block is filled with FF hexa, it means the header is at the
> end of the archive file, the tailer is more right term;)
> So when you archive the tape, you cant reverse and
> write the header at the beginning of file.
> In that case, the header (at the end of file) is in REVERSE order.
> So the last 4 bytes tells where the header begins. So no need to search for it.
> Simply read the last 4 bytes, determine where the header
> begins(reverse order!),
> and read those blocks. Reverse the byte orders, and thats way you can process
> it normally.
> Openmoko community mailing list
> community at lists.openmoko.org
More information about the community