summaryrefslogtreecommitdiff
path: root/Build/source/libs/zziplib/zziplib-0.13.62/docs/zzip-parse.htm
blob: a3c49dcba76d76d436ec813df7a855757fcb71d8 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
<section> <date> 17. December 2002 </date>
<h2> ZIP Format </h2>        About Zip Parsing Internals...

<!--border-->

<section>
<h3> ZIP Trailer Block </h3>

<P>
  The general ZIP file format is written sequentially - each file
  being added gets a local file header and its inflated data. When
  all files are written then a central directory is written - and
  this central directory may even span multiple disks. And each
  disk gets a descriptor block that contains a pointer to the start
  of the central directory. This descriptor is always written last
  and therefore we call it the "ZIP File Trailer Block".
</P>
<P>
  Okay, so we know that this ZIP Trailer is always at the end of a zip
  file and that is has a fixed length, and a magic four-byte value at
  its block start. That should make it easy to detect zip files but in
  the real world it is not that easy - it is allowed to add a zip
  archive comment text <em>after</em> the Trailer block. It's rarely
  used these days but it turns out that a zip reader must be ready
  to search for the Trailer block starting at the end of the file
  and looking upwards for the Trailer magic (it's "PK\5\6" btw).
</P>
<P>
  Now that's what the internal function __zip_find_disk_trailer is
  used for. It's somewhat optimized as we try to use mmap features
  of the underlying operating system. The returned structure is 
  called zzip_disk_trailer in the library source code, and we only
  need two values actually: u_rootseek and u_rootsize. The first of
  these can be used to lseek to the place of the central directory
  and the second value tells us the byte size of the central directory.
</P>

</section><section>
<h3> ZIP Central Directory </h3>

<P>
  So here we are at the central directory. The disk trailer did also
  tell us how many entries are there but it is not that easy to read
  them. Each directory entry (zzip_root_dirent type) has again a
  magic value up front followed by a few items but they all have some
  dos format - consider the timestamps, and atleast size/seek values 
  are in intel byteorder. So we might want to parse them into a format
  that is easier to handle in internal code.
</P>
<P>
  That is also needed for another reason - there are three items in that 
  directory entry being size values of three variadic fields following
  right after the directory. That's right, three of these. The first
  variadic field is the filename of this directory entry. In other
  words, the root directory entry does not contain a seek value of
  where the filename starts off, the start of the filename is 
  implicitly given with the end address of the directory entry.
</P>
<P>
  The size value for the filename does simply say how long the
  filename is - however, and more importantly, it allows us to 
  compute the start of the next variadic field, called the extra
  info field. Well, we do not need any value from that extra info
  block (it has unix filemode bits when packed under unix) but we
  can be quite sure that this field is not null either. And that
  was the second variadic field.
</P>
<P>
  There is a third variadic field however - it's the comment field.
  That was pretty heavily used in the good old DOS days. We are not
  used to it anymore since filenames are generally self-descriptive
  today but in the DOS days a filename was 8+3 chars maximum - and
  it was in the comment field that told users what's in there. It
  turned out that many software archives used zip format for just
  that purpose as their primary distribution format - for being 
  able to attach a comment line with each entry.
</P>
<P>
  Now, these three variadic fields have each an entry in the 
  directory entry header telling of their size. And after these
  three variadic fields the next directory entry follows right in.
  Yes, again there is no seek value here - we have to take the sum
  of the three field sizes and add that to the end address of the
  directory entry - just to be able to get to the next entry.
</P>

</section><section>
<h3> Internal Directory </h3>

<P>
  Now, the external ZIP format is too complicated. We cut it down
  to the bare minimum we actually need. The fields in the entry
  are parsed into a format directly usable, and from the variadic
  fields we only keep the filename. Oh, and we ensure that the
  filename gets a trailing null byte, so it can surely be passed
  down into libc routines.
</P>
<P>
  There is another trick by the way - we use the u_rootsize value
  to malloc a block for the internal directory. That ensures the
  internal root directory entries are in nearby locations, and
  including the filenames themselves which we put in between the
  dirent entries. That's not only similar to the external directory
  format, but when calling readdir and looking for a matching
  filename of an zzip_open call, this will ensure the memory is
  fetched in a linear fashion. Modern cpu architectures are able
  to burst through it.
</P>
<P>
  One might think to use a more complicated internal directory
  format - like hash tables or something. However, they all suffer
  from the fact that memory access patterns will be somewhat random
  which eats a lot of speed. It is hardly predictable under what
  circumstances it gets us a benefit, but the problem is certainly
  not off-world: there are zzip archives with 13k+ entries. In a real
  filesystem people will not put 13k files into one directory, of 
  course - but for the zip central directory all entries are listed
  in parallel with their subdirectory paths attached. So, if the
  original subtree had a number of directories, they'll end up in
  parallel in the zip's central directory.
</P>

</section><section>
<h3> File Entry </h3>

<P>
  The zip directory entry has one value that is called z_off in the
  zziplib sources - it's the seek value to the start of the actual
  file data, or more correctly it points to the "local file header".
  Each file data block is preceded/followed with a little frame.
  There is not much interesting information in these framing blocks, 
  the values are duplicates of the ones found in the zip central
  directory - however, we must skip the local file header (and a
  possible duplicate of filename and extrainfo) to arrive at the
  actual file data.
</P>
<P>
  When the start of the actual file data, we can finally read data.
  The zziplib library does only know about two choices defined by 
  the value in the z_compr field - a value of "0" means "stored"
  and data has been stored in uncompresed format, so that we can
  just copy it out of the file to the application buffer.
</P>
<P>
  A value of "8" means "deflated", and here we initialize the zlib
  and every file data is decompressed before copying it to the
  application buffer. Care must be taken here since zlib input data
  and decompressed data may differ significantly. The zlib compression
  will not even obey byte boundaries - a single bit may expand to
  hundreds of bytes. That's why each ZZIP_FILE has a decompression
  buffer attached.
</P>
<P>
  All the other z_compr values are only of historical meaning,
  the infozip unix tools will only create deflated content, and
  the same applies to pkzip 2.x tools. If there would be any other
  value than "0" or "8" then zziplib can not decompress it, simple
  as that.
</P>

</section><section>
<h3> ZZIP_DIR / ZZIP_FILE </h3>

<P>
  The ZZIP_DIR internal structures stores a posix handle to the
  zip file, and a pointer to the parsed central directory block.
  One can use readdir/rewinddir to walk each entry in the central
  directory and compare with the filenames attached. And that's
  what will be done at a zzip_open call to find the file entry.
</P>
<P>
  There are a few more fields in the ZZIP_DIR structure, where 
  most of these are related to the use of this struct as a
  shared recource. You can use zzip_file_open to walk the 
  preparsed central directory and return a new ZZIP_FILE handle
  for that entry.
</P>
<P>
  That ZZIP_FILE handle contains a back pointer its ZZIP_DIR
  that it was made from - and the back pointer also serves as flag
  that the ZZIP_FILE handle points to a file within a ZIP file as
  opposed to wrapping a real file in the real directory tree.
  Each ZZIP_FILE will increment a shared counter, so that the
  next dir_close will be deferred until all ZZIP_FILE have been
  destroyed.
</P>
<P>
  Another optmization is the cache-pointer in the ZZIP_DIR. It is
  quite common to read data entries sequentially, as that the
  zip directory is scanned for files matching a specific pattern,
  and when a match is seen, that file is openened. However, each
  ZZIP_FILE needs a decompression buffer, and we keep a cache of
  the last one freed so that it can be picked up right away for the
  next zzip_file_open.
</P>
<P>
  Note that using multiple zzip_open() directly, each will open
  and parse a zip directory of its own. That's bloat both in
  terms of memory consumption and execution speed. One should try
  to take advantage of the feature that multiple ZZIP_FILE's can
  share a common ZZIP_DIR with a common preparsed copy of the
  zip's central directory. That can be done directly with using
  zzip_file_open to use a ZZIP_DIR as a factory for ZZIP_FILE,
  but also zzip_freopen can be used to reuse the old internal
  central directory, instead of parsing it again.
</P>
<P>
  And while zzip_freopen would release the old ZZIP_FILE handle
  only resuing the ZZIP_DIR attached, one can use another routine
  directly called zzip_open_shared that will create a ZZIP_FILE
  from an existing ZZIP_FILE. Oh, and not need to worry about 
  problems when a filepath given to zzip_freopen() happens to
  be in another place, another directory, another zip archive.
  In that case, the old zzip's internal directory is freed and
  the others directory read - the preparsed central directory
  is only used if that is actually possible.
</P>

</section></section>