2 * RAZF : Random Access compressed(Z) File
4 * Release Date: 2008-10-27
6 * Copyright 2008, Jue Ruan <ruanjue@gmail.com>, Heng Li <lh3@sanger.ac.uk>
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in the
17 * documentation and/or other materials provided with the distribution.
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * To compile razf.c, zlib-1.2.3(or greater) is required.
38 static inline uint32_t byte_swap_4(uint32_t v){
39 v = ((v & 0x0000FFFFU) << 16) | (v >> 16);
40 return ((v & 0x00FF00FFU) << 8) | ((v & 0xFF00FF00U) >> 8);
43 static inline uint64_t byte_swap_8(uint64_t v){
44 v = ((v & 0x00000000FFFFFFFFLLU) << 32) | (v >> 32);
45 v = ((v & 0x0000FFFF0000FFFFLLU) << 16) | ((v & 0xFFFF0000FFFF0000LLU) >> 16);
46 return ((v & 0x00FF00FF00FF00FFLLU) << 8) | ((v & 0xFF00FF00FF00FF00LLU) >> 8);
49 static inline int is_big_endian(){
52 return (c[0] != 0x01);
55 static void add_zindex(RAZF *rz, int64_t in, int64_t out){
56 if(rz->index->size == rz->index->cap){
57 rz->index->cap = rz->index->cap * 1.5 + 2;
58 rz->index->cell_offsets = realloc(rz->index->cell_offsets, sizeof(int) * rz->index->cap);
59 rz->index->bin_offsets = realloc(rz->index->bin_offsets, sizeof(int64_t) * (rz->index->cap/RZ_BIN_SIZE + 1));
61 if(rz->index->size % RZ_BIN_SIZE == 0) rz->index->bin_offsets[rz->index->size / RZ_BIN_SIZE] = out;
62 rz->index->cell_offsets[rz->index->size] = out - rz->index->bin_offsets[rz->index->size / RZ_BIN_SIZE];
66 static void save_zindex(RAZF *rz, int fd){
69 is_be = is_big_endian();
70 if(is_be) write(fd, &rz->index->size, sizeof(int));
72 v32 = byte_swap_4((uint32_t)rz->index->size);
73 write(fd, &v32, sizeof(uint32_t));
75 v32 = rz->index->size / RZ_BIN_SIZE + 1;
77 for(i=0;i<v32;i++) rz->index->bin_offsets[i] = byte_swap_8((uint64_t)rz->index->bin_offsets[i]);
78 for(i=0;i<rz->index->size;i++) rz->index->cell_offsets[i] = byte_swap_4((uint32_t)rz->index->cell_offsets[i]);
80 write(fd, rz->index->bin_offsets, sizeof(int64_t) * v32);
81 write(fd, rz->index->cell_offsets, sizeof(int32_t) * rz->index->size);
84 static void load_zindex(RAZF *rz, int fd){
87 if(!rz->load_index) return;
88 if(rz->index == NULL) rz->index = malloc(sizeof(ZBlockIndex));
89 is_be = is_big_endian();
90 read(fd, &rz->index->size, sizeof(int));
91 if(!is_be) rz->index->size = byte_swap_4((uint32_t)rz->index->size);
92 rz->index->cap = rz->index->size;
93 v32 = rz->index->size / RZ_BIN_SIZE + 1;
94 rz->index->bin_offsets = malloc(sizeof(int64_t) * v32);
95 read(fd, rz->index->bin_offsets, sizeof(int64_t) * v32);
96 rz->index->cell_offsets = malloc(sizeof(int) * rz->index->size);
97 read(fd, rz->index->cell_offsets, sizeof(int) * rz->index->size);
99 for(i=0;i<v32;i++) rz->index->bin_offsets[i] = byte_swap_8((uint64_t)rz->index->bin_offsets[i]);
100 for(i=0;i<rz->index->size;i++) rz->index->cell_offsets[i] = byte_swap_4((uint32_t)rz->index->cell_offsets[i]);
104 static RAZF* razf_open_w(int fd){
106 rz = calloc(1, sizeof(RAZF));
109 rz->stream = calloc(sizeof(z_stream), 1);
110 rz->inbuf = malloc(RZ_BUFFER_SIZE);
111 rz->outbuf = malloc(RZ_BUFFER_SIZE);
112 rz->index = calloc(sizeof(ZBlockIndex), 1);
113 deflateInit2(rz->stream, RZ_COMPRESS_LEVEL, Z_DEFLATED, WINDOW_BITS + 16, DEF_MEM_LEVEL, Z_DEFAULT_STRATEGY);
114 rz->stream->avail_out = RZ_BUFFER_SIZE;
115 rz->stream->next_out = rz->outbuf;
116 rz->header = calloc(sizeof(gz_header), 1);
117 rz->header->os = 0x03; //Unix
118 rz->header->text = 0;
119 rz->header->time = 0;
120 rz->header->extra = malloc(7);
121 strncpy((char*)rz->header->extra, "RAZF", 4);
122 rz->header->extra[4] = 1; // obsolete field
123 // block size = RZ_BLOCK_SIZE, Big-Endian
124 rz->header->extra[5] = RZ_BLOCK_SIZE >> 8;
125 rz->header->extra[6] = RZ_BLOCK_SIZE & 0xFF;
126 rz->header->extra_len = 7;
127 rz->header->name = rz->header->comment = 0;
128 rz->header->hcrc = 0;
129 deflateSetHeader(rz->stream, rz->header);
130 rz->block_pos = rz->block_off = 0;
134 static void _razf_write(RAZF* rz, const void *data, int size){
136 rz->stream->avail_in = size;
137 rz->stream->next_in = (void*)data;
139 tout = rz->stream->avail_out;
140 deflate(rz->stream, Z_NO_FLUSH);
141 rz->out += tout - rz->stream->avail_out;
142 if(rz->stream->avail_out) break;
143 write(rz->filedes, rz->outbuf, RZ_BUFFER_SIZE - rz->stream->avail_out);
144 rz->stream->avail_out = RZ_BUFFER_SIZE;
145 rz->stream->next_out = rz->outbuf;
146 if(rz->stream->avail_in == 0) break;
148 rz->in += size - rz->stream->avail_in;
149 rz->block_off += size - rz->stream->avail_in;
152 static void razf_flush(RAZF *rz){
155 _razf_write(rz, rz->inbuf, rz->buf_len);
156 rz->buf_off = rz->buf_len = 0;
158 if(rz->stream->avail_out){
159 write(rz->filedes, rz->outbuf, RZ_BUFFER_SIZE - rz->stream->avail_out);
160 rz->stream->avail_out = RZ_BUFFER_SIZE;
161 rz->stream->next_out = rz->outbuf;
164 tout = rz->stream->avail_out;
165 deflate(rz->stream, Z_FULL_FLUSH);
166 rz->out += tout - rz->stream->avail_out;
167 if(rz->stream->avail_out == 0){
168 write(rz->filedes, rz->outbuf, RZ_BUFFER_SIZE - rz->stream->avail_out);
169 rz->stream->avail_out = RZ_BUFFER_SIZE;
170 rz->stream->next_out = rz->outbuf;
173 rz->block_pos = rz->out;
177 static void razf_end_flush(RAZF *rz){
180 _razf_write(rz, rz->inbuf, rz->buf_len);
181 rz->buf_off = rz->buf_len = 0;
184 tout = rz->stream->avail_out;
185 deflate(rz->stream, Z_FINISH);
186 rz->out += tout - rz->stream->avail_out;
187 if(rz->stream->avail_out < RZ_BUFFER_SIZE){
188 write(rz->filedes, rz->outbuf, RZ_BUFFER_SIZE - rz->stream->avail_out);
189 rz->stream->avail_out = RZ_BUFFER_SIZE;
190 rz->stream->next_out = rz->outbuf;
195 static void _razf_buffered_write(RAZF *rz, const void *data, int size){
198 if(rz->buf_len == RZ_BUFFER_SIZE){
199 _razf_write(rz, rz->inbuf, rz->buf_len);
202 if(size + rz->buf_len < RZ_BUFFER_SIZE){
203 for(i=0;i<size;i++) ((char*)rz->inbuf + rz->buf_len)[i] = ((char*)data)[i];
207 n = RZ_BUFFER_SIZE - rz->buf_len;
208 for(i=0;i<n;i++) ((char*)rz->inbuf + rz->buf_len)[i] = ((char*)data)[i];
216 int razf_write(RAZF* rz, const void *data, int size){
220 next_block = ((rz->in / RZ_BLOCK_SIZE) + 1) * RZ_BLOCK_SIZE;
221 while(rz->in + rz->buf_len + size >= next_block){
222 n = next_block - rz->in - rz->buf_len;
223 _razf_buffered_write(rz, data, n);
227 add_zindex(rz, rz->in, rz->out);
228 next_block = ((rz->in / RZ_BLOCK_SIZE) + 1) * RZ_BLOCK_SIZE;
230 _razf_buffered_write(rz, data, size);
235 #define ASCII_FLAG 0x01 /* bit 0 set: file probably ascii text */
236 #define HEAD_CRC 0x02 /* bit 1 set: header CRC present */
237 #define EXTRA_FIELD 0x04 /* bit 2 set: extra field present */
238 #define ORIG_NAME 0x08 /* bit 3 set: original file name present */
239 #define COMMENT 0x10 /* bit 4 set: file comment present */
240 #define RESERVED 0xE0 /* bits 5..7: reserved */
242 static int _read_gz_header(unsigned char *data, int size, int *extra_off, int *extra_len){
243 int method, flags, n, len;
244 if(size < 2) return 0;
245 if(data[0] != 0x1f || data[1] != 0x8b) return 0;
246 if(size < 4) return 0;
249 if(method != Z_DEFLATED || (flags & RESERVED)) return 0;
250 n = 4 + 6; // Skip 6 bytes
253 if(flags & EXTRA_FIELD){
254 if(size < n + 2) return 0;
255 len = ((int)data[n + 1] << 8) | data[n];
259 if(n >= size) return 0;
263 *extra_len = n - (*extra_off);
265 if(flags & ORIG_NAME) while(n < size && data[n++]);
266 if(flags & COMMENT) while(n < size && data[n++]);
267 if(flags & HEAD_CRC){
268 if(n + 2 > size) return 0;
274 static RAZF* razf_open_r(int fd, int _load_index){
276 int ext_off, ext_len;
279 unsigned char c[] = "RAZF";
280 rz = calloc(1, sizeof(RAZF));
283 rz->stream = calloc(sizeof(z_stream), 1);
284 rz->inbuf = malloc(RZ_BUFFER_SIZE);
285 rz->outbuf = malloc(RZ_BUFFER_SIZE);
286 rz->end = rz->src_end = 0x7FFFFFFFFFFFFFFFLL;
287 n = read(rz->filedes, rz->inbuf, RZ_BUFFER_SIZE);
288 ret = _read_gz_header(rz->inbuf, n, &ext_off, &ext_len);
292 rz->file_type = FILE_TYPE_PLAIN;
293 memcpy(rz->outbuf, rz->inbuf, n);
299 rz->header_size = ret;
300 ret = inflateInit2(rz->stream, -WINDOW_BITS);
301 if(ret != Z_OK){ inflateEnd(rz->stream); goto PLAIN_FILE;}
302 rz->stream->avail_in = n - rz->header_size;
303 rz->stream->next_in = rz->inbuf + rz->header_size;
304 rz->stream->avail_out = RZ_BUFFER_SIZE;
305 rz->stream->next_out = rz->outbuf;
306 rz->file_type = FILE_TYPE_GZ;
307 rz->in = rz->header_size;
308 rz->block_pos = rz->header_size;
309 rz->next_block_pos = rz->header_size;
311 if(ext_len < 7 || memcmp(rz->inbuf + ext_off, c, 4) != 0) return rz;
312 if(((((unsigned char*)rz->inbuf)[ext_off + 5] << 8) | ((unsigned char*)rz->inbuf)[ext_off + 6]) != RZ_BLOCK_SIZE){
313 fprintf(stderr, " -- WARNING: RZ_BLOCK_SIZE is not %d, treat source as gz file. in %s -- %s:%d --\n", RZ_BLOCK_SIZE, __FUNCTION__, __FILE__, __LINE__);
316 rz->load_index = _load_index;
317 rz->file_type = FILE_TYPE_RZ;
318 if(lseek(fd, -16, SEEK_END) == -1){
322 rz->src_end = rz->end = 0x7FFFFFFFFFFFFFFFLL;
324 is_be = is_big_endian();
326 read(fd, &end, sizeof(int64_t));
327 if(!is_be) rz->src_end = (int64_t)byte_swap_8((uint64_t)end);
328 else rz->src_end = end;
329 read(fd, &end, sizeof(int64_t));
330 if(!is_be) rz->end = (int64_t)byte_swap_8((uint64_t)end);
333 rz->stream->avail_in -= n - rz->end;
336 if(rz->end > rz->src_end){
337 lseek(fd, rz->in, SEEK_SET);
340 if(lseek(fd, rz->end, SEEK_SET) != rz->end){
341 lseek(fd, rz->in, SEEK_SET);
345 lseek(fd, n, SEEK_SET);
350 RAZF* razf_dopen(int fd, const char *mode){
351 if(strcasecmp(mode, "r") == 0) return razf_open_r(fd, 1);
352 else if(strcasecmp(mode, "w") == 0) return razf_open_w(fd);
356 RAZF* razf_dopen2(int fd, const char *mode)
358 if(strcasecmp(mode, "r") == 0) return razf_open_r(fd, 0);
359 else if(strcasecmp(mode, "w") == 0) return razf_open_w(fd);
363 static inline RAZF* _razf_open(const char *filename, const char *mode, int _load_index){
366 if(strcasecmp(mode, "r") == 0){
367 fd = open(filename, O_RDONLY);
368 rz = razf_open_r(fd, _load_index);
369 } else if(strcasecmp(mode, "w") == 0){
370 fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0644);
371 rz = razf_open_w(fd);
376 RAZF* razf_open(const char *filename, const char *mode){
377 return _razf_open(filename, mode, 1);
380 RAZF* razf_open2(const char *filename, const char *mode){
381 return _razf_open(filename, mode, 0);
384 int razf_get_data_size(RAZF *rz, int64_t *u_size, int64_t *c_size){
386 if(rz->mode != 'r' && rz->mode != 'R') return 0;
387 switch(rz->file_type){
388 case FILE_TYPE_PLAIN:
389 if(rz->end == 0x7fffffffffffffffLL){
390 if((n = lseek(rz->filedes, 0, SEEK_CUR)) == -1) return 0;
391 rz->end = lseek(rz->filedes, 0, SEEK_END);
392 lseek(rz->filedes, n, SEEK_SET);
394 *u_size = *c_size = rz->end;
399 if(rz->src_end == rz->end) return 0;
400 *u_size = rz->src_end;
408 static int _razf_read(RAZF* rz, void *data, int size){
410 if(rz->z_eof || rz->z_err) return 0;
411 if (rz->file_type == FILE_TYPE_PLAIN) {
412 ret = read(rz->filedes, data, size);
413 if (ret == 0) rz->z_eof = 1;
416 rz->stream->avail_out = size;
417 rz->stream->next_out = data;
418 while(rz->stream->avail_out){
419 if(rz->stream->avail_in == 0){
420 if(rz->in >= rz->end){ rz->z_eof = 1; break; }
421 if(rz->end - rz->in < RZ_BUFFER_SIZE){
422 rz->stream->avail_in = read(rz->filedes, rz->inbuf, rz->end -rz->in);
424 rz->stream->avail_in = read(rz->filedes, rz->inbuf, RZ_BUFFER_SIZE);
426 if(rz->stream->avail_in == 0){
430 rz->stream->next_in = rz->inbuf;
432 tin = rz->stream->avail_in;
433 ret = inflate(rz->stream, Z_BLOCK);
434 rz->in += tin - rz->stream->avail_in;
435 if(ret == Z_NEED_DICT || ret == Z_MEM_ERROR || ret == Z_DATA_ERROR){
436 fprintf(stderr, "[_razf_read] inflate error: %d (at %s:%d)\n", ret, __FILE__, __LINE__);
440 if(ret == Z_STREAM_END){
444 if ((rz->stream->data_type&128) && !(rz->stream->data_type&64)){
446 rz->next_block_pos = rz->in;
450 return size - rz->stream->avail_out;
453 int razf_read(RAZF *rz, void *data, int size){
458 if(size < rz->buf_len){
459 for(i=0;i<size;i++) ((char*)data)[i] = ((char*)rz->outbuf + rz->buf_off)[i];
463 rz->block_off += size;
467 for(i=0;i<rz->buf_len;i++) ((char*)data)[i] = ((char*)rz->outbuf + rz->buf_off)[i];
470 rz->block_off += rz->buf_len;
474 rz->block_pos = rz->next_block_pos;
479 } else if(rz->buf_flush){
480 rz->block_pos = rz->next_block_pos;
484 if(rz->buf_flush) continue;
485 rz->buf_len = _razf_read(rz, rz->outbuf, RZ_BUFFER_SIZE);
486 if(rz->z_eof && rz->buf_len == 0) break;
488 rz->out += ori_size - size;
489 return ori_size - size;
492 int razf_skip(RAZF* rz, int size){
497 if(size < rz->buf_len){
500 rz->block_off += size;
507 rz->block_off += rz->buf_len;
509 rz->block_pos = rz->next_block_pos;
514 } else if(rz->buf_flush){
515 rz->block_pos = rz->next_block_pos;
519 if(rz->buf_flush) continue;
520 rz->buf_len = _razf_read(rz, rz->outbuf, RZ_BUFFER_SIZE);
523 rz->out += ori_size - size;
524 return ori_size - size;
527 static void _razf_reset_read(RAZF *rz, int64_t in, int64_t out){
528 lseek(rz->filedes, in, SEEK_SET);
532 rz->next_block_pos = in;
535 rz->z_eof = rz->z_err = 0;
536 inflateReset(rz->stream);
537 rz->stream->avail_in = 0;
538 rz->buf_off = rz->buf_len = 0;
541 int64_t razf_jump(RAZF *rz, int64_t block_start, int block_offset){
544 if(rz->file_type == FILE_TYPE_PLAIN){
545 rz->buf_off = rz->buf_len = 0;
546 pos = block_start + block_offset;
547 pos = lseek(rz->filedes, pos, SEEK_SET);
548 rz->out = rz->in = pos;
551 if(block_start == rz->block_pos && block_offset >= rz->block_off) {
552 block_offset -= rz->block_off;
553 goto SKIP; // Needn't reset inflate
555 if(block_start == 0) block_start = rz->header_size; // Automaticly revist wrong block_start
556 _razf_reset_read(rz, block_start, 0);
558 if(block_offset) razf_skip(rz, block_offset);
559 return rz->block_off;
562 int64_t razf_seek(RAZF* rz, int64_t pos, int where){
564 int64_t seek_pos, new_out;
566 if (where == SEEK_CUR) pos += rz->out;
567 else if (where == SEEK_END) pos += rz->src_end;
568 if(rz->file_type == FILE_TYPE_PLAIN){
569 seek_pos = lseek(rz->filedes, pos, SEEK_SET);
570 rz->buf_off = rz->buf_len = 0;
571 rz->out = rz->in = seek_pos;
573 } else if(rz->file_type == FILE_TYPE_GZ){
574 if(pos >= rz->out) goto SKIP;
577 if(pos == rz->out) return pos;
578 if(pos > rz->src_end) return rz->out;
579 if(!rz->seekable || !rz->load_index){
580 if(pos >= rz->out) goto SKIP;
582 idx = pos / RZ_BLOCK_SIZE - 1;
583 seek_pos = (idx < 0)? rz->header_size:(rz->index->cell_offsets[idx] + rz->index->bin_offsets[idx / RZ_BIN_SIZE]);
584 new_out = (idx + 1) * RZ_BLOCK_SIZE;
585 if(pos > rz->out && new_out <= rz->out) goto SKIP;
586 _razf_reset_read(rz, seek_pos, new_out);
588 razf_skip(rz, (int)(pos - rz->out));
592 uint64_t razf_tell2(RAZF *rz)
595 if (rz->load_index) {
596 int64_t idx, seek_pos;
597 idx = rz->out / RZ_BLOCK_SIZE - 1;
598 seek_pos = (idx < 0)? rz->header_size:(rz->index->cell_offsets[idx] + rz->index->bin_offsets[idx / RZ_BIN_SIZE]);
599 if (seek_pos != rz->block_pos || rz->out%RZ_BLOCK_SIZE != rz->block_off)
600 fprintf(stderr, "[razf_tell2] inconsistent block offset: (%lld, %lld) != (%lld, %lld)\n",
601 (long long)seek_pos, (long long)rz->out%RZ_BLOCK_SIZE, (long long)rz->block_pos, (long long) rz->block_off);
604 return (uint64_t)rz->block_pos<<16 | (rz->block_off&0xffff);
607 int64_t razf_seek2(RAZF *rz, uint64_t voffset, int where)
609 if (where != SEEK_SET) return -1;
610 return razf_jump(rz, voffset>>16, voffset&0xffff);
613 void razf_close(RAZF *rz){
617 deflateEnd(rz->stream);
618 save_zindex(rz, rz->filedes);
620 write(rz->filedes, &rz->in, sizeof(int64_t));
621 write(rz->filedes, &rz->out, sizeof(int64_t));
623 v64 = byte_swap_8((uint64_t)rz->in);
624 write(rz->filedes, &v64, sizeof(int64_t));
625 v64 = byte_swap_8((uint64_t)rz->out);
626 write(rz->filedes, &v64, sizeof(int64_t));
628 } else if(rz->mode == 'r'){
629 if(rz->stream) inflateEnd(rz->stream);
631 if(rz->inbuf) free(rz->inbuf);
632 if(rz->outbuf) free(rz->outbuf);
634 free(rz->header->extra);
635 free(rz->header->name);
636 free(rz->header->comment);
640 free(rz->index->bin_offsets);
641 free(rz->index->cell_offsets);