¬2Ì2 33L3l3 Ì3ì3ü3,4L4l4|4Œ4¬4¼4Ì4Ü4ü4 55,5<5L5l5Œ5¼5ì5 6,6<6<6l6|6 Ì6ì6 7,7L7\7|7|7Œ7¬7¬7¬7¬7¼7Ü7 8,8\8Œ8¼8ì8,9\9Œ9Ì9Ü9ì9ü9<:\:|:œ:¬:¼:Ü: ;;<;L;L;L;\;|;|;œ;œ;œ;¼;ü;<<<\<l<Œ<¼<¼<Ì<Ü< =,=L=\=\=Œ=¬=¼=¼=Ü=ì=>,>L>|>¼>Ü>ü> ?? #include "alloc.h" #include "error.h" #define ALIGNMENT 16 /* XXX: assuming that this alignment is enough */ #define SPACE 4096 /* must be multiple of ALIGNMENT */ typedef union { char irrelevant[ALIGNMENT]; double d; } aligned; static aligned realspace[SPACE / ALIGNMENT]; #define space ((char *) realspace) static unsigned int avail = SPACE; /* multiple of ALIGNMENT; 0<=avail<=SPACE */ /*@null@*//*@out@*/char *alloc(unsigned int n) { char *x; n = (n + ALIGNMENT - 1) & ~(ALIGNMENT - 1); /* XXX: could overflow */ if (n <= avail) { avail -= n; return space + avail; } x = malloc(n); if (!x) errno = error_nomem; return x; } void alloc_free(void *x) { if ((char *)x >= space) if ((char *)x < space + SPACE) return; /* XXX: assuming that pointers are flat */ free(x); } Hbun-0.1b2/trydevino.c3_ºD3#include #include int main(void) { int r; struct stat statbuf; unsigned char *p; p = &statbuf.st_dev; r = *p; p = &statbuf.st_ino; r += *p; return r; } Hbun-0.1b2/stat.h4_ŸD4#include "haslstat.h" #if HASlstat enum { haslstat = 1 }; #else enum { haslstat = 0 }; #include "assert.h" #define lstat(n, b) (assert(0), 0) #define S_ISLNK(x) (assert(0), 0) #define readlink(a, b, c) (assert(0), 0) #endif #include "hasst_xtimespec.h" #if HASst_xtimespec #define ST_ACCESS_NANO(x) (x.st_atimespec.tv_nsec) #define ST_MODIFY_NANO(x) (x.st_mtimespec.tv_nsec) #endif #include "hasst_xtim.h" #if HASst_xtim #define ST_ACCESS_NANO(x) (x.st_atim.tv_nsec) #define ST_MODIFY_NANO(x) (x.st_mtim.tv_nsec) #endif /* Undocumented feature of Tru64 Unix: there are three "spare" fields in struct stat, which hold microsecond values for atime, mtime, and ctime. */ #include "hasst_spare123.h" #if HASst_spare123 #define ST_ACCESS_NANO(x) (x.st_spare1 * 1000UL) #define ST_MODIFY_NANO(x) (x.st_spare2 * 1000UL) #endif #ifndef ST_ACCESS_NANO #define ST_ACCESS_NANO(x) 0 #define ST_MODIFY_NANO(x) 0 #endif Hbun-0.1b2/subgetopt.h5_ D5#ifndef SUBGETOPT_H #define SUBGETOPT_H #ifndef SUBGETOPTNOSHORT #define sgopt subgetopt #define sgoptarg subgetoptarg #define sgoptind subgetoptind #define sgoptpos subgetoptpos #define sgoptproblem subgetoptproblem #define sgoptprogname subgetoptprogname #define sgoptdone subgetoptdone #endif #define SUBGETOPTDONE -1 extern int subgetopt(int,char **,const char *); extern char *subgetoptarg; extern int subgetoptind; extern int subgetoptpos; extern int subgetoptproblem; extern char *subgetoptprogname; extern int subgetoptdone; #endif Hbun-0.1b2/strerr_die.c6_WD6#include "buffer.h" #include "exit.h" #include "strerr.h" void strerr_warn(const char *x1,const char *x2,const char *x3,const char *x4,const char *x5,const char *x6,const struct strerr *se) { strerr_sysinit(); if (x1) buffer_puts(buffer_2,x1); if (x2) buffer_puts(buffer_2,x2); if (x3) buffer_puts(buffer_2,x3); if (x4) buffer_puts(buffer_2,x4); if (x5) buffer_puts(buffer_2,x5); if (x6) buffer_puts(buffer_2,x6); while(se) { if (se->x) buffer_puts(buffer_2,se->x); if (se->y) buffer_puts(buffer_2,se->y); if (se->z) buffer_puts(buffer_2,se->z); se = se->who; } buffer_puts(buffer_2,"\n"); buffer_flush(buffer_2); } void strerr_die(const int e,const char *x1,const char *x2,const char *x3,const char *x4,const char *x5,const char *x6,const struct strerr *se) { strerr_warn(x1,x2,x3,x4,x5,x6,se); _exit(e); } Hbun-0.1b2/bun_cdb_make.h7_.D7#include "buffer.h" #include "cdb_make.h" extern int bun_cdb_add_bzip2(struct cdb_make *, char *, uint32, int, unsigned long *); extern int bun_cdb_add_file(struct cdb_make *, char *, uint32, int, unsigned long); extern int bun_cdb_add_stream(struct cdb_make *, char *, uint32, int, unsigned long *); Hbun-0.1b2/tryst_spare123.c8_œD8#include int main(void) { int x; struct stat statbuf; x = statbuf.st_spare1; x = statbuf.st_spare2; x = statbuf.st_spare3; return 0; } Hbun-0.1b2/out_mem.c9_zD9/* Public domain. */ #include #include "error.h" #include "out.h" int out_mem(int out, unsigned char *p, size_t size) { ssize_t chunk; chunk = out_MEM_CHUNK; while (size) { ssize_t nw; if (chunk > size) chunk = size; if ((nw = write(out, p, chunk)) < 0) { if (errno == error_intr) continue; return -1; } size -= nw; p += nw; } return 0; } Hbun-0.1b2/caltime_fmt.c10_D10#include "caldate.h" #include "caltime.h" unsigned int caltime_fmt(char *s, struct caltime *ct) { unsigned int result; long x; result = caldate_fmt(s,&ct->date); if (s) { s += result; x = ct->hour; s[0] = ' '; s[2] = '0' + (x % 10); x /= 10; s[1] = '0' + (x % 10); s += 3; x = ct->minute; s[0] = ':'; s[2] = '0' + (x % 10); x /= 10; s[1] = '0' + (x % 10); s += 3; x = ct->second; s[0] = ':'; s[2] = '0' + (x % 10); x /= 10; s[1] = '0' + (x % 10); s += 3; s[0] = ' '; x = ct->offset; if (x < 0) { s[1] = '-'; x = -x; } else s[1] = '+'; s[5] = '0' + (x % 10); x /= 10; s[4] = '0' + (x % 6); x /= 6; s[3] = '0' + (x % 10); x /= 10; s[2] = '0' + (x % 10); } return result + 15; } Hbun-0.1b2/decompress.c11_œSD11 /*-------------------------------------------------------------*/ /*--- Decompression machinery ---*/ /*--- decompress.c ---*/ /*-------------------------------------------------------------*/ /*-- This file is a part of bzip2 and/or libbzip2, a program and library for lossless, block-sorting data compression. Copyright (C) 1996-2002 Julian R Seward. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 3. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 4. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Julian Seward, Cambridge, UK. jseward@acm.org bzip2/libbzip2 version 1.0 of 21 March 2000 This program is based on (at least) the work of: Mike Burrows David Wheeler Peter Fenwick Alistair Moffat Radford Neal Ian H. Witten Robert Sedgewick Jon L. Bentley For more information on these sources, see the manual. --*/ #include "bzlib_private.h" /*---------------------------------------------------*/ static void makeMaps_d ( DState* s ) { Int32 i; s->nInUse = 0; for (i = 0; i < 256; i++) if (s->inUse[i]) { s->seqToUnseq[s->nInUse] = i; s->nInUse++; } } /*---------------------------------------------------*/ #define RETURN(rrr) \ { retVal = rrr; goto save_state_and_return; }; #define GET_BITS(lll,vvv,nnn) \ case lll: s->state = lll; \ while (True) { \ if (s->bsLive >= nnn) { \ UInt32 v; \ v = (s->bsBuff >> \ (s->bsLive-nnn)) & ((1 << nnn)-1); \ s->bsLive -= nnn; \ vvv = v; \ break; \ } \ if (s->strm->avail_in == 0) RETURN(BZ_OK); \ s->bsBuff \ = (s->bsBuff << 8) | \ ((UInt32) \ (*((UChar*)(s->strm->next_in)))); \ s->bsLive += 8; \ s->strm->next_in++; \ s->strm->avail_in--; \ s->strm->total_in_lo32++; \ if (s->strm->total_in_lo32 == 0) \ s->strm->total_in_hi32++; \ } #define GET_UCHAR(lll,uuu) \ GET_BITS(lll,uuu,8) #define GET_BIT(lll,uuu) \ GET_BITS(lll,uuu,1) /*---------------------------------------------------*/ #define GET_MTF_VAL(label1,label2,lval) \ { \ if (groupPos == 0) { \ groupNo++; \ if (groupNo >= nSelectors) \ RETURN(BZ_DATA_ERROR); \ groupPos = BZ_G_SIZE; \ gSel = s->selector[groupNo]; \ gMinlen = s->minLens[gSel]; \ gLimit = &(s->limit[gSel][0]); \ gPerm = &(s->perm[gSel][0]); \ gBase = &(s->base[gSel][0]); \ } \ groupPos--; \ zn = gMinlen; \ GET_BITS(label1, zvec, zn); \ while (1) { \ if (zn > 20 /* the longest code */) \ RETURN(BZ_DATA_ERROR); \ if (zvec <= gLimit[zn]) break; \ zn++; \ GET_BIT(label2, zj); \ zvec = (zvec << 1) | zj; \ }; \ if (zvec - gBase[zn] < 0 \ || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE) \ RETURN(BZ_DATA_ERROR); \ lval = gPerm[zvec - gBase[zn]]; \ } /*---------------------------------------------------*/ Int32 BZ2_decompress ( DState* s ) { UChar uc; Int32 retVal; Int32 minLen, maxLen; bz_stream* strm = s->strm; /* stuff that needs to be saved/restored */ Int32 i; Int32 j; Int32 t; Int32 alphaSize; Int32 nGroups; Int32 nSelectors; Int32 EOB; Int32 groupNo; Int32 groupPos; Int32 nextSym; Int32 nblockMAX; Int32 nblock; Int32 es; Int32 N; Int32 curr; Int32 zt; Int32 zn; Int32 zvec; Int32 zj; Int32 gSel; Int32 gMinlen; Int32* gLimit; Int32* gBase; Int32* gPerm; if (s->state == BZ_X_MAGIC_1) { /*initialise the save area*/ s->save_i = 0; s->save_j = 0; s->save_t = 0; s->save_alphaSize = 0; s->save_nGroups = 0; s->save_nSelectors = 0; s->save_EOB = 0; s->save_groupNo = 0; s->save_groupPos = 0; s->save_nextSym = 0; s->save_nblockMAX = 0; s->save_nblock = 0; s->save_es = 0; s->save_N = 0; s->save_curr = 0; s->save_zt = 0; s->save_zn = 0; s->save_zvec = 0; s->save_zj = 0; s->save_gSel = 0; s->save_gMinlen = 0; s->save_gLimit = NULL; s->save_gBase = NULL; s->save_gPerm = NULL; } /*restore from the save area*/ i = s->save_i; j = s->save_j; t = s->save_t; alphaSize = s->save_alphaSize; nGroups = s->save_nGroups; nSelectors = s->save_nSelectors; EOB = s->save_EOB; groupNo = s->save_groupNo; groupPos = s->save_groupPos; nextSym = s->save_nextSym; nblockMAX = s->save_nblockMAX; nblock = s->save_nblock; es = s->save_es; N = s->save_N; curr = s->save_curr; zt = s->save_zt; zn = s->save_zn; zvec = s->save_zvec; zj = s->save_zj; gSel = s->save_gSel; gMinlen = s->save_gMinlen; gLimit = s->save_gLimit; gBase = s->save_gBase; gPerm = s->save_gPerm; retVal = BZ_OK; switch (s->state) { GET_UCHAR(BZ_X_MAGIC_1, uc); if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC); GET_UCHAR(BZ_X_MAGIC_2, uc); if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC); GET_UCHAR(BZ_X_MAGIC_3, uc) if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC); GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8) if (s->blockSize100k < (BZ_HDR_0 + 1) || s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC); s->blockSize100k -= BZ_HDR_0; if (s->smallDecompress) { s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) ); s->ll4 = BZALLOC( ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar) ); if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR); } else { s->tt = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) ); if (s->tt == NULL) RETURN(BZ_MEM_ERROR); } GET_UCHAR(BZ_X_BLKHDR_1, uc); if (uc == 0x17) goto endhdr_2; if (uc != 0x31) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_BLKHDR_2, uc); if (uc != 0x41) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_BLKHDR_3, uc); if (uc != 0x59) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_BLKHDR_4, uc); if (uc != 0x26) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_BLKHDR_5, uc); if (uc != 0x53) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_BLKHDR_6, uc); if (uc != 0x59) RETURN(BZ_DATA_ERROR); s->currBlockNo++; if (s->verbosity >= 2) VPrintf1 ( "\n [%d: huff+mtf ", s->currBlockNo ); s->storedBlockCRC = 0; GET_UCHAR(BZ_X_BCRC_1, uc); s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); GET_UCHAR(BZ_X_BCRC_2, uc); s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); GET_UCHAR(BZ_X_BCRC_3, uc); s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); GET_UCHAR(BZ_X_BCRC_4, uc); s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc); GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1); s->origPtr = 0; GET_UCHAR(BZ_X_ORIGPTR_1, uc); s->origPtr = (s->origPtr << 8) | ((Int32)uc); GET_UCHAR(BZ_X_ORIGPTR_2, uc); s->origPtr = (s->origPtr << 8) | ((Int32)uc); GET_UCHAR(BZ_X_ORIGPTR_3, uc); s->origPtr = (s->origPtr << 8) | ((Int32)uc); if (s->origPtr < 0) RETURN(BZ_DATA_ERROR); if (s->origPtr > 10 + 100000*s->blockSize100k) RETURN(BZ_DATA_ERROR); /*--- Receive the mapping table ---*/ for (i = 0; i < 16; i++) { GET_BIT(BZ_X_MAPPING_1, uc); if (uc == 1) s->inUse16[i] = True; else s->inUse16[i] = False; } for (i = 0; i < 256; i++) s->inUse[i] = False; for (i = 0; i < 16; i++) if (s->inUse16[i]) for (j = 0; j < 16; j++) { GET_BIT(BZ_X_MAPPING_2, uc); if (uc == 1) s->inUse[i * 16 + j] = True; } makeMaps_d ( s ); if (s->nInUse == 0) RETURN(BZ_DATA_ERROR); alphaSize = s->nInUse+2; /*--- Now the selectors ---*/ GET_BITS(BZ_X_SELECTOR_1, nGroups, 3); if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR); GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15); if (nSelectors < 1) RETURN(BZ_DATA_ERROR); for (i = 0; i < nSelectors; i++) { j = 0; while (True) { GET_BIT(BZ_X_SELECTOR_3, uc); if (uc == 0) break; j++; if (j >= nGroups) RETURN(BZ_DATA_ERROR); } s->selectorMtf[i] = j; } /*--- Undo the MTF values for the selectors. ---*/ { UChar pos[BZ_N_GROUPS], tmp, v; for (v = 0; v < nGroups; v++) pos[v] = v; for (i = 0; i < nSelectors; i++) { v = s->selectorMtf[i]; tmp = pos[v]; while (v > 0) { pos[v] = pos[v-1]; v--; } pos[0] = tmp; s->selector[i] = tmp; } } /*--- Now the coding tables ---*/ for (t = 0; t < nGroups; t++) { GET_BITS(BZ_X_CODING_1, curr, 5); for (i = 0; i < alphaSize; i++) { while (True) { if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR); GET_BIT(BZ_X_CODING_2, uc); if (uc == 0) break; GET_BIT(BZ_X_CODING_3, uc); if (uc == 0) curr++; else curr--; } s->len[t][i] = curr; } } /*--- Create the Huffman decoding tables ---*/ for (t = 0; t < nGroups; t++) { minLen = 32; maxLen = 0; for (i = 0; i < alphaSize; i++) { if (s->len[t][i] > maxLen) maxLen = s->len[t][i]; if (s->len[t][i] < minLen) minLen = s->len[t][i]; } BZ2_hbCreateDecodeTables ( &(s->limit[t][0]), &(s->base[t][0]), &(s->perm[t][0]), &(s->len[t][0]), minLen, maxLen, alphaSize ); s->minLens[t] = minLen; } /*--- Now the MTF values ---*/ EOB = s->nInUse+1; nblockMAX = 100000 * s->blockSize100k; groupNo = -1; groupPos = 0; for (i = 0; i <= 255; i++) s->unzftab[i] = 0; /*-- MTF init --*/ { Int32 ii, jj, kk; kk = MTFA_SIZE-1; for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) { for (jj = MTFL_SIZE-1; jj >= 0; jj--) { s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj); kk--; } s->mtfbase[ii] = kk + 1; } } /*-- end MTF init --*/ nblock = 0; GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym); while (True) { if (nextSym == EOB) break; if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) { es = -1; N = 1; do { if (nextSym == BZ_RUNA) es = es + (0+1) * N; else if (nextSym == BZ_RUNB) es = es + (1+1) * N; N = N * 2; GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym); } while (nextSym == BZ_RUNA || nextSym == BZ_RUNB); es++; uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ]; s->unzftab[uc] += es; if (s->smallDecompress) while (es > 0) { if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); s->ll16[nblock] = (UInt16)uc; nblock++; es--; } else while (es > 0) { if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); s->tt[nblock] = (UInt32)uc; nblock++; es--; }; continue; } else { if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR); /*-- uc = MTF ( nextSym-1 ) --*/ { Int32 ii, jj, kk, pp, lno, off; UInt32 nn; nn = (UInt32)(nextSym - 1); if (nn < MTFL_SIZE) { /* avoid general-case expense */ pp = s->mtfbase[0]; uc = s->mtfa[pp+nn]; while (nn > 3) { Int32 z = pp+nn; s->mtfa[(z) ] = s->mtfa[(z)-1]; s->mtfa[(z)-1] = s->mtfa[(z)-2]; s->mtfa[(z)-2] = s->mtfa[(z)-3]; s->mtfa[(z)-3] = s->mtfa[(z)-4]; nn -= 4; } while (nn > 0) { s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--; }; s->mtfa[pp] = uc; } else { /* general case */ lno = nn / MTFL_SIZE; off = nn % MTFL_SIZE; pp = s->mtfbase[lno] + off; uc = s->mtfa[pp]; while (pp > s->mtfbase[lno]) { s->mtfa[pp] = s->mtfa[pp-1]; pp--; }; s->mtfbase[lno]++; while (lno > 0) { s->mtfbase[lno]--; s->mtfa[s->mtfbase[lno]] = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1]; lno--; } s->mtfbase[0]--; s->mtfa[s->mtfbase[0]] = uc; if (s->mtfbase[0] == 0) { kk = MTFA_SIZE-1; for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) { for (jj = MTFL_SIZE-1; jj >= 0; jj--) { s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj]; kk--; } s->mtfbase[ii] = kk + 1; } } } } /*-- end uc = MTF ( nextSym-1 ) --*/ s->unzftab[s->seqToUnseq[uc]]++; if (s->smallDecompress) s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else s->tt[nblock] = (UInt32)(s->seqToUnseq[uc]); nblock++; GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym); continue; } } /* Now we know what nblock is, we can do a better sanity check on s->origPtr. */ if (s->origPtr < 0 || s->origPtr >= nblock) RETURN(BZ_DATA_ERROR); s->state_out_len = 0; s->state_out_ch = 0; BZ_INITIALISE_CRC ( s->calculatedBlockCRC ); s->state = BZ_X_OUTPUT; if (s->verbosity >= 2) VPrintf0 ( "rt+rld" ); /*-- Set up cftab to facilitate generation of T^(-1) --*/ s->cftab[0] = 0; for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1]; for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1]; if (s->smallDecompress) { /*-- Make a copy of cftab, used in generation of T --*/ for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i]; /*-- compute the T vector --*/ for (i = 0; i < nblock; i++) { uc = (UChar)(s->ll16[i]); SET_LL(i, s->cftabCopy[uc]); s->cftabCopy[uc]++; } /*-- Compute T^(-1) by pointer reversal on T --*/ i = s->origPtr; j = GET_LL(i); do { Int32 tmp = GET_LL(j); SET_LL(j, i); i = j; j = tmp; } while (i != s->origPtr); s->tPos = s->origPtr; s->nblock_used = 0; if (s->blockRandomised) { BZ_RAND_INIT_MASK; BZ_GET_SMALL(s->k0); s->nblock_used++; BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; } else { BZ_GET_SMALL(s->k0); s->nblock_used++; } } else { /*-- compute the T^(-1) vector --*/ for (i = 0; i < nblock; i++) { uc = (UChar)(s->tt[i] & 0xff); s->tt[s->cftab[uc]] |= (i << 8); s->cftab[uc]++; } s->tPos = s->tt[s->origPtr] >> 8; s->nblock_used = 0; if (s->blockRandomised) { BZ_RAND_INIT_MASK; BZ_GET_FAST(s->k0); s->nblock_used++; BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; } else { BZ_GET_FAST(s->k0); s->nblock_used++; } } RETURN(BZ_OK); endhdr_2: GET_UCHAR(BZ_X_ENDHDR_2, uc); if (uc != 0x72) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_ENDHDR_3, uc); if (uc != 0x45) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_ENDHDR_4, uc); if (uc != 0x38) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_ENDHDR_5, uc); if (uc != 0x50) RETURN(BZ_DATA_ERROR); GET_UCHAR(BZ_X_ENDHDR_6, uc); if (uc != 0x90) RETURN(BZ_DATA_ERROR); s->storedCombinedCRC = 0; GET_UCHAR(BZ_X_CCRC_1, uc); s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); GET_UCHAR(BZ_X_CCRC_2, uc); s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); GET_UCHAR(BZ_X_CCRC_3, uc); s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); GET_UCHAR(BZ_X_CCRC_4, uc); s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc); s->state = BZ_X_IDLE; RETURN(BZ_STREAM_END); default: AssertH ( False, 4001 ); } AssertH ( False, 4002 ); save_state_and_return: s->save_i = i; s->save_j = j; s->save_t = t; s->save_alphaSize = alphaSize; s->save_nGroups = nGroups; s->save_nSelectors = nSelectors; s->save_EOB = EOB; s->save_groupNo = groupNo; s->save_groupPos = groupPos; s->save_nextSym = nextSym; s->save_nblockMAX = nblockMAX; s->save_nblock = nblock; s->save_es = es; s->save_N = N; s->save_curr = curr; s->save_zt = zt; s->save_zn = zn; s->save_zvec = zvec; s->save_zj = zj; s->save_gSel = gSel; s->save_gMinlen = gMinlen; s->save_gLimit = gLimit; s->save_gBase = gBase; s->save_gPerm = gPerm; return retVal; } /*-------------------------------------------------------------*/ /*--- end decompress.c ---*/ /*-------------------------------------------------------------*/ Hbun-0.1b2/bzlib.c12_•¶D12 /*-------------------------------------------------------------*/ /*--- Library top-level functions. ---*/ /*--- bzlib.c ---*/ /*-------------------------------------------------------------*/ /*-- This file is a part of bzip2 and/or libbzip2, a program and library for lossless, block-sorting data compression. Copyright (C) 1996-2002 Julian R Seward. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 3. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 4. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Julian Seward, Cambridge, UK. jseward@acm.org bzip2/libbzip2 version 1.0 of 21 March 2000 This program is based on (at least) the work of: Mike Burrows David Wheeler Peter Fenwick Alistair Moffat Radford Neal Ian H. Witten Robert Sedgewick Jon L. Bentley For more information on these sources, see the manual. --*/ /*-- CHANGES ~~~~~~~ 0.9.0 -- original version. 0.9.0a/b -- no changes in this file. 0.9.0c * made zero-length BZ_FLUSH work correctly in bzCompress(). * fixed bzWrite/bzRead to ignore zero-length requests. * fixed bzread to correctly handle read requests after EOF. * wrong parameter order in call to bzDecompressInit in bzBuffToBuffDecompress. Fixed. --*/ #include "bzlib_private.h" /*---------------------------------------------------*/ /*--- Compression stuff ---*/ /*---------------------------------------------------*/ /*---------------------------------------------------*/ #ifndef BZ_NO_STDIO void BZ2_bz__AssertH__fail ( int errcode ) { fprintf(stderr, "\n\nbzip2/libbzip2: internal error number %d.\n" "This is a bug in bzip2/libbzip2, %s.\n" "Please report it to me at: jseward@acm.org. If this happened\n" "when you were using some program which uses libbzip2 as a\n" "component, you should also report this bug to the author(s)\n" "of that program. Please make an effort to report this bug;\n" "timely and accurate bug reports eventually lead to higher\n" "quality software. Thanks. Julian Seward, 30 December 2001.\n\n", errcode, BZ2_bzlibVersion() ); if (errcode == 1007) { fprintf(stderr, "\n*** A special note about internal error number 1007 ***\n" "\n" "Experience suggests that a common cause of i.e. 1007\n" "is unreliable memory or other hardware. The 1007 assertion\n" "just happens to cross-check the results of huge numbers of\n" "memory reads/writes, and so acts (unintendedly) as a stress\n" "test of your memory system.\n" "\n" "I suggest the following: try compressing the file again,\n" "possibly monitoring progress in detail with the -vv flag.\n" "\n" "* If the error cannot be reproduced, and/or happens at different\n" " points in compression, you may have a flaky memory system.\n" " Try a memory-test program. I have used Memtest86\n" " (www.memtest86.com). At the time of writing it is free (GPLd).\n" " Memtest86 tests memory much more thorougly than your BIOSs\n" " power-on test, and may find failures that the BIOS doesn't.\n" "\n" "* If the error can be repeatably reproduced, this is a bug in\n" " bzip2, and I would very much like to hear about it. Please\n" " let me know, and, ideally, save a copy of the file causing the\n" " problem -- without which I will be unable to investigate it.\n" "\n" ); } exit(3); } #endif /*---------------------------------------------------*/ static int bz_config_ok ( void ) { if (sizeof(int) != 4) return 0; if (sizeof(short) != 2) return 0; if (sizeof(char) != 1) return 0; return 1; } /*---------------------------------------------------*/ static void* default_bzalloc ( void* opaque, Int32 items, Int32 size ) { void* v = malloc ( items * size ); return v; } static void default_bzfree ( void* opaque, void* addr ) { if (addr != NULL) free ( addr ); } /*---------------------------------------------------*/ static void prepare_new_block ( EState* s ) { Int32 i; s->nblock = 0; s->numZ = 0; s->state_out_pos = 0; BZ_INITIALISE_CRC ( s->blockCRC ); for (i = 0; i < 256; i++) s->inUse[i] = False; s->blockNo++; } /*---------------------------------------------------*/ static void init_RL ( EState* s ) { s->state_in_ch = 256; s->state_in_len = 0; } static Bool isempty_RL ( EState* s ) { if (s->state_in_ch < 256 && s->state_in_len > 0) return False; else return True; } /*---------------------------------------------------*/ int BZ_API(BZ2_bzCompressInit) ( bz_stream* strm, int blockSize100k, int verbosity, int workFactor ) { Int32 n; EState* s; if (!bz_config_ok()) return BZ_CONFIG_ERROR; if (strm == NULL || blockSize100k < 1 || blockSize100k > 9 || workFactor < 0 || workFactor > 250) return BZ_PARAM_ERROR; if (workFactor == 0) workFactor = 30; if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc; if (strm->bzfree == NULL) strm->bzfree = default_bzfree; s = BZALLOC( sizeof(EState) ); if (s == NULL) return BZ_MEM_ERROR; s->strm = strm; s->arr1 = NULL; s->arr2 = NULL; s->ftab = NULL; n = 100000 * blockSize100k; s->arr1 = BZALLOC( n * sizeof(UInt32) ); s->arr2 = BZALLOC( (n+BZ_N_OVERSHOOT) * sizeof(UInt32) ); s->ftab = BZALLOC( 65537 * sizeof(UInt32) ); if (s->arr1 == NULL || s->arr2 == NULL || s->ftab == NULL) { if (s->arr1 != NULL) BZFREE(s->arr1); if (s->arr2 != NULL) BZFREE(s->arr2); if (s->ftab != NULL) BZFREE(s->ftab); if (s != NULL) BZFREE(s); return BZ_MEM_ERROR; } s->blockNo = 0; s->state = BZ_S_INPUT; s->mode = BZ_M_RUNNING; s->combinedCRC = 0; s->blockSize100k = blockSize100k; s->nblockMAX = 100000 * blockSize100k - 19; s->verbosity = verbosity; s->workFactor = workFactor; s->block = (UChar*)s->arr2; s->mtfv = (UInt16*)s->arr1; s->zbits = NULL; s->ptr = (UInt32*)s->arr1; strm->state = s; strm->total_in_lo32 = 0; strm->total_in_hi32 = 0; strm->total_out_lo32 = 0; strm->total_out_hi32 = 0; init_RL ( s ); prepare_new_block ( s ); return BZ_OK; } /*---------------------------------------------------*/ static void add_pair_to_block ( EState* s ) { Int32 i; UChar ch = (UChar)(s->state_in_ch); for (i = 0; i < s->state_in_len; i++) { BZ_UPDATE_CRC( s->blockCRC, ch ); } s->inUse[s->state_in_ch] = True; switch (s->state_in_len) { case 1: s->block[s->nblock] = (UChar)ch; s->nblock++; break; case 2: s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = (UChar)ch; s->nblock++; break; case 3: s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = (UChar)ch; s->nblock++; break; default: s->inUse[s->state_in_len-4] = True; s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = (UChar)ch; s->nblock++; s->block[s->nblock] = ((UChar)(s->state_in_len-4)); s->nblock++; break; } } /*---------------------------------------------------*/ static void flush_RL ( EState* s ) { if (s->state_in_ch < 256) add_pair_to_block ( s ); init_RL ( s ); } /*---------------------------------------------------*/ #define ADD_CHAR_TO_BLOCK(zs,zchh0) \ { \ UInt32 zchh = (UInt32)(zchh0); \ /*-- fast track the common case --*/ \ if (zchh != zs->state_in_ch && \ zs->state_in_len == 1) { \ UChar ch = (UChar)(zs->state_in_ch); \ BZ_UPDATE_CRC( zs->blockCRC, ch ); \ zs->inUse[zs->state_in_ch] = True; \ zs->block[zs->nblock] = (UChar)ch; \ zs->nblock++; \ zs->state_in_ch = zchh; \ } \ else \ /*-- general, uncommon cases --*/ \ if (zchh != zs->state_in_ch || \ zs->state_in_len == 255) { \ if (zs->state_in_ch < 256) \ add_pair_to_block ( zs ); \ zs->state_in_ch = zchh; \ zs->state_in_len = 1; \ } else { \ zs->state_in_len++; \ } \ } /*---------------------------------------------------*/ static Bool copy_input_until_stop ( EState* s ) { Bool progress_in = False; if (s->mode == BZ_M_RUNNING) { /*-- fast track the common case --*/ while (True) { /*-- block full? --*/ if (s->nblock >= s->nblockMAX) break; /*-- no input? --*/ if (s->strm->avail_in == 0) break; progress_in = True; ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) ); s->strm->next_in++; s->strm->avail_in--; s->strm->total_in_lo32++; if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++; } } else { /*-- general, uncommon case --*/ while (True) { /*-- block full? --*/ if (s->nblock >= s->nblockMAX) break; /*-- no input? --*/ if (s->strm->avail_in == 0) break; /*-- flush/finish end? --*/ if (s->avail_in_expect == 0) break; progress_in = True; ADD_CHAR_TO_BLOCK ( s, (UInt32)(*((UChar*)(s->strm->next_in))) ); s->strm->next_in++; s->strm->avail_in--; s->strm->total_in_lo32++; if (s->strm->total_in_lo32 == 0) s->strm->total_in_hi32++; s->avail_in_expect--; } } return progress_in; } /*---------------------------------------------------*/ static Bool copy_output_until_stop ( EState* s ) { Bool progress_out = False; while (True) { /*-- no output space? --*/ if (s->strm->avail_out == 0) break; /*-- block done? --*/ if (s->state_out_pos >= s->numZ) break; progress_out = True; *(s->strm->next_out) = s->zbits[s->state_out_pos]; s->state_out_pos++; s->strm->avail_out--; s->strm->next_out++; s->strm->total_out_lo32++; if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; } return progress_out; } /*---------------------------------------------------*/ static Bool handle_compress ( bz_stream* strm ) { Bool progress_in = False; Bool progress_out = False; EState* s = strm->state; while (True) { if (s->state == BZ_S_OUTPUT) { progress_out |= copy_output_until_stop ( s ); if (s->state_out_pos < s->numZ) break; if (s->mode == BZ_M_FINISHING && s->avail_in_expect == 0 && isempty_RL(s)) break; prepare_new_block ( s ); s->state = BZ_S_INPUT; if (s->mode == BZ_M_FLUSHING && s->avail_in_expect == 0 && isempty_RL(s)) break; } if (s->state == BZ_S_INPUT) { progress_in |= copy_input_until_stop ( s ); if (s->mode != BZ_M_RUNNING && s->avail_in_expect == 0) { flush_RL ( s ); BZ2_compressBlock ( s, (Bool)(s->mode == BZ_M_FINISHING) ); s->state = BZ_S_OUTPUT; } else if (s->nblock >= s->nblockMAX) { BZ2_compressBlock ( s, False ); s->state = BZ_S_OUTPUT; } else if (s->strm->avail_in == 0) { break; } } } return progress_in || progress_out; } /*---------------------------------------------------*/ int BZ_API(BZ2_bzCompress) ( bz_stream *strm, int action ) { Bool progress; EState* s; if (strm == NULL) return BZ_PARAM_ERROR; s = strm->state; if (s == NULL) return BZ_PARAM_ERROR; if (s->strm != strm) return BZ_PARAM_ERROR; preswitch: switch (s->mode) { case BZ_M_IDLE: return BZ_SEQUENCE_ERROR; case BZ_M_RUNNING: if (action == BZ_RUN) { progress = handle_compress ( strm ); return progress ? BZ_RUN_OK : BZ_PARAM_ERROR; } else if (action == BZ_FLUSH) { s->avail_in_expect = strm->avail_in; s->mode = BZ_M_FLUSHING; goto preswitch; } else if (action == BZ_FINISH) { s->avail_in_expect = strm->avail_in; s->mode = BZ_M_FINISHING; goto preswitch; } else return BZ_PARAM_ERROR; case BZ_M_FLUSHING: if (action != BZ_FLUSH) return BZ_SEQUENCE_ERROR; if (s->avail_in_expect != s->strm->avail_in) return BZ_SEQUENCE_ERROR; progress = handle_compress ( strm ); if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ) return BZ_FLUSH_OK; s->mode = BZ_M_RUNNING; return BZ_RUN_OK; case BZ_M_FINISHING: if (action != BZ_FINISH) return BZ_SEQUENCE_ERROR; if (s->avail_in_expect != s->strm->avail_in) return BZ_SEQUENCE_ERROR; progress = handle_compress ( strm ); if (!progress) return BZ_SEQUENCE_ERROR; if (s->avail_in_expect > 0 || !isempty_RL(s) || s->state_out_pos < s->numZ) return BZ_FINISH_OK; s->mode = BZ_M_IDLE; return BZ_STREAM_END; } return BZ_OK; /*--not reached--*/ } /*---------------------------------------------------*/ int BZ_API(BZ2_bzCompressEnd) ( bz_stream *strm ) { EState* s; if (strm == NULL) return BZ_PARAM_ERROR; s = strm->state; if (s == NULL) return BZ_PARAM_ERROR; if (s->strm != strm) return BZ_PARAM_ERROR; if (s->arr1 != NULL) BZFREE(s->arr1); if (s->arr2 != NULL) BZFREE(s->arr2); if (s->ftab != NULL) BZFREE(s->ftab); BZFREE(strm->state); strm->state = NULL; return BZ_OK; } /*---------------------------------------------------*/ /*--- Decompression stuff ---*/ /*---------------------------------------------------*/ /*---------------------------------------------------*/ int BZ_API(BZ2_bzDecompressInit) ( bz_stream* strm, int verbosity, int small ) { DState* s; if (!bz_config_ok()) return BZ_CONFIG_ERROR; if (strm == NULL) return BZ_PARAM_ERROR; if (small != 0 && small != 1) return BZ_PARAM_ERROR; if (verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR; if (strm->bzalloc == NULL) strm->bzalloc = default_bzalloc; if (strm->bzfree == NULL) strm->bzfree = default_bzfree; s = BZALLOC( sizeof(DState) ); if (s == NULL) return BZ_MEM_ERROR; s->strm = strm; strm->state = s; s->state = BZ_X_MAGIC_1; s->bsLive = 0; s->bsBuff = 0; s->calculatedCombinedCRC = 0; strm->total_in_lo32 = 0; strm->total_in_hi32 = 0; strm->total_out_lo32 = 0; strm->total_out_hi32 = 0; s->smallDecompress = (Bool)small; s->ll4 = NULL; s->ll16 = NULL; s->tt = NULL; s->currBlockNo = 0; s->verbosity = verbosity; return BZ_OK; } /*---------------------------------------------------*/ static void unRLE_obuf_to_output_FAST ( DState* s ) { UChar k1; if (s->blockRandomised) { while (True) { /* try to finish existing run */ while (True) { if (s->strm->avail_out == 0) return; if (s->state_out_len == 0) break; *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); s->state_out_len--; s->strm->next_out++; s->strm->avail_out--; s->strm->total_out_lo32++; if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; } /* can a new run be started? */ if (s->nblock_used == s->save_nblock+1) return; s->state_out_len = 1; s->state_out_ch = s->k0; BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; s->state_out_len = 2; BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; s->state_out_len = 3; BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; BZ_GET_FAST(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; s->state_out_len = ((Int32)k1) + 4; BZ_GET_FAST(s->k0); BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; s->nblock_used++; } } else { /* restore */ UInt32 c_calculatedBlockCRC = s->calculatedBlockCRC; UChar c_state_out_ch = s->state_out_ch; Int32 c_state_out_len = s->state_out_len; Int32 c_nblock_used = s->nblock_used; Int32 c_k0 = s->k0; UInt32* c_tt = s->tt; UInt32 c_tPos = s->tPos; char* cs_next_out = s->strm->next_out; unsigned int cs_avail_out = s->strm->avail_out; /* end restore */ UInt32 avail_out_INIT = cs_avail_out; Int32 s_save_nblockPP = s->save_nblock+1; unsigned int total_out_lo32_old; while (True) { /* try to finish existing run */ if (c_state_out_len > 0) { while (True) { if (cs_avail_out == 0) goto return_notr; if (c_state_out_len == 1) break; *( (UChar*)(cs_next_out) ) = c_state_out_ch; BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch ); c_state_out_len--; cs_next_out++; cs_avail_out--; } s_state_out_len_eq_one: { if (cs_avail_out == 0) { c_state_out_len = 1; goto return_notr; }; *( (UChar*)(cs_next_out) ) = c_state_out_ch; BZ_UPDATE_CRC ( c_calculatedBlockCRC, c_state_out_ch ); cs_next_out++; cs_avail_out--; } } /* can a new run be started? */ if (c_nblock_used == s_save_nblockPP) { c_state_out_len = 0; goto return_notr; }; c_state_out_ch = c_k0; BZ_GET_FAST_C(k1); c_nblock_used++; if (k1 != c_k0) { c_k0 = k1; goto s_state_out_len_eq_one; }; if (c_nblock_used == s_save_nblockPP) goto s_state_out_len_eq_one; c_state_out_len = 2; BZ_GET_FAST_C(k1); c_nblock_used++; if (c_nblock_used == s_save_nblockPP) continue; if (k1 != c_k0) { c_k0 = k1; continue; }; c_state_out_len = 3; BZ_GET_FAST_C(k1); c_nblock_used++; if (c_nblock_used == s_save_nblockPP) continue; if (k1 != c_k0) { c_k0 = k1; continue; }; BZ_GET_FAST_C(k1); c_nblock_used++; c_state_out_len = ((Int32)k1) + 4; BZ_GET_FAST_C(c_k0); c_nblock_used++; } return_notr: total_out_lo32_old = s->strm->total_out_lo32; s->strm->total_out_lo32 += (avail_out_INIT - cs_avail_out); if (s->strm->total_out_lo32 < total_out_lo32_old) s->strm->total_out_hi32++; /* save */ s->calculatedBlockCRC = c_calculatedBlockCRC; s->state_out_ch = c_state_out_ch; s->state_out_len = c_state_out_len; s->nblock_used = c_nblock_used; s->k0 = c_k0; s->tt = c_tt; s->tPos = c_tPos; s->strm->next_out = cs_next_out; s->strm->avail_out = cs_avail_out; /* end save */ } } /*---------------------------------------------------*/ __inline__ Int32 BZ2_indexIntoF ( Int32 indx, Int32 *cftab ) { Int32 nb, na, mid; nb = 0; na = 256; do { mid = (nb + na) >> 1; if (indx >= cftab[mid]) nb = mid; else na = mid; } while (na - nb != 1); return nb; } /*---------------------------------------------------*/ static void unRLE_obuf_to_output_SMALL ( DState* s ) { UChar k1; if (s->blockRandomised) { while (True) { /* try to finish existing run */ while (True) { if (s->strm->avail_out == 0) return; if (s->state_out_len == 0) break; *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); s->state_out_len--; s->strm->next_out++; s->strm->avail_out--; s->strm->total_out_lo32++; if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; } /* can a new run be started? */ if (s->nblock_used == s->save_nblock+1) return; s->state_out_len = 1; s->state_out_ch = s->k0; BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; s->state_out_len = 2; BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; s->state_out_len = 3; BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; BZ_GET_SMALL(k1); BZ_RAND_UPD_MASK; k1 ^= BZ_RAND_MASK; s->nblock_used++; s->state_out_len = ((Int32)k1) + 4; BZ_GET_SMALL(s->k0); BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK; s->nblock_used++; } } else { while (True) { /* try to finish existing run */ while (True) { if (s->strm->avail_out == 0) return; if (s->state_out_len == 0) break; *( (UChar*)(s->strm->next_out) ) = s->state_out_ch; BZ_UPDATE_CRC ( s->calculatedBlockCRC, s->state_out_ch ); s->state_out_len--; s->strm->next_out++; s->strm->avail_out--; s->strm->total_out_lo32++; if (s->strm->total_out_lo32 == 0) s->strm->total_out_hi32++; } /* can a new run be started? */ if (s->nblock_used == s->save_nblock+1) return; s->state_out_len = 1; s->state_out_ch = s->k0; BZ_GET_SMALL(k1); s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; s->state_out_len = 2; BZ_GET_SMALL(k1); s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; s->state_out_len = 3; BZ_GET_SMALL(k1); s->nblock_used++; if (s->nblock_used == s->save_nblock+1) continue; if (k1 != s->k0) { s->k0 = k1; continue; }; BZ_GET_SMALL(k1); s->nblock_used++; s->state_out_len = ((Int32)k1) + 4; BZ_GET_SMALL(s->k0); s->nblock_used++; } } } /*---------------------------------------------------*/ int BZ_API(BZ2_bzDecompress) ( bz_stream *strm ) { DState* s; if (strm == NULL) return BZ_PARAM_ERROR; s = strm->state; if (s == NULL) return BZ_PARAM_ERROR; if (s->strm != strm) return BZ_PARAM_ERROR; while (True) { if (s->state == BZ_X_IDLE) return BZ_SEQUENCE_ERROR; if (s->state == BZ_X_OUTPUT) { if (s->smallDecompress) unRLE_obuf_to_output_SMALL ( s ); else unRLE_obuf_to_output_FAST ( s ); if (s->nblock_used == s->save_nblock+1 && s->state_out_len == 0) { BZ_FINALISE_CRC ( s->calculatedBlockCRC ); if (s->verbosity >= 3) VPrintf2 ( " {0x%x, 0x%x}", s->storedBlockCRC, s->calculatedBlockCRC ); if (s->verbosity >= 2) VPrintf0 ( "]" ); if (s->calculatedBlockCRC != s->storedBlockCRC) return BZ_DATA_ERROR; s->calculatedCombinedCRC = (s->calculatedCombinedCRC << 1) | (s->calculatedCombinedCRC >> 31); s->calculatedCombinedCRC ^= s->calculatedBlockCRC; s->state = BZ_X_BLKHDR_1; } else { return BZ_OK; } } if (s->state >= BZ_X_MAGIC_1) { Int32 r = BZ2_decompress ( s ); if (r == BZ_STREAM_END) { if (s->verbosity >= 3) VPrintf2 ( "\n combined CRCs: stored = 0x%x, computed = 0x%x", s->storedCombinedCRC, s->calculatedCombinedCRC ); if (s->calculatedCombinedCRC != s->storedCombinedCRC) return BZ_DATA_ERROR; return r; } if (s->state != BZ_X_OUTPUT) return r; } } AssertH ( 0, 6001 ); return 0; /*NOTREACHED*/ } /*---------------------------------------------------*/ int BZ_API(BZ2_bzDecompressEnd) ( bz_stream *strm ) { DState* s; if (strm == NULL) return BZ_PARAM_ERROR; s = strm->state; if (s == NULL) return BZ_PARAM_ERROR; if (s->strm != strm) return BZ_PARAM_ERROR; if (s->tt != NULL) BZFREE(s->tt); if (s->ll16 != NULL) BZFREE(s->ll16); if (s->ll4 != NULL) BZFREE(s->ll4); BZFREE(strm->state); strm->state = NULL; return BZ_OK; } #ifndef BZ_NO_STDIO /*---------------------------------------------------*/ /*--- File I/O stuff ---*/ /*---------------------------------------------------*/ #define BZ_SETERR(eee) \ { \ if (bzerror != NULL) *bzerror = eee; \ if (bzf != NULL) bzf->lastErr = eee; \ } typedef struct { FILE* handle; Char buf[BZ_MAX_UNUSED]; Int32 bufN; Bool writing; bz_stream strm; Int32 lastErr; Bool initialisedOk; } bzFile; /*---------------------------------------------*/ static Bool myfeof ( FILE* f ) { Int32 c = fgetc ( f ); if (c == EOF) return True; ungetc ( c, f ); return False; } /*---------------------------------------------------*/ BZFILE* BZ_API(BZ2_bzWriteOpen) ( int* bzerror, FILE* f, int blockSize100k, int verbosity, int workFactor ) { Int32 ret; bzFile* bzf = NULL; BZ_SETERR(BZ_OK); if (f == NULL || (blockSize100k < 1 || blockSize100k > 9) || (workFactor < 0 || workFactor > 250) || (verbosity < 0 || verbosity > 4)) { BZ_SETERR(BZ_PARAM_ERROR); return NULL; }; if (ferror(f)) { BZ_SETERR(BZ_IO_ERROR); return NULL; }; bzf = malloc ( sizeof(bzFile) ); if (bzf == NULL) { BZ_SETERR(BZ_MEM_ERROR); return NULL; }; BZ_SETERR(BZ_OK); bzf->initialisedOk = False; bzf->bufN = 0; bzf->handle = f; bzf->writing = True; bzf->strm.bzalloc = NULL; bzf->strm.bzfree = NULL; bzf->strm.opaque = NULL; if (workFactor == 0) workFactor = 30; ret = BZ2_bzCompressInit ( &(bzf->strm), blockSize100k, verbosity, workFactor ); if (ret != BZ_OK) { BZ_SETERR(ret); free(bzf); return NULL; }; bzf->strm.avail_in = 0; bzf->initialisedOk = True; return bzf; } /*---------------------------------------------------*/ void BZ_API(BZ2_bzWrite) ( int* bzerror, BZFILE* b, void* buf, int len ) { Int32 n, n2, ret; bzFile* bzf = (bzFile*)b; BZ_SETERR(BZ_OK); if (bzf == NULL || buf == NULL || len < 0) { BZ_SETERR(BZ_PARAM_ERROR); return; }; if (!(bzf->writing)) { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; if (ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return; }; if (len == 0) { BZ_SETERR(BZ_OK); return; }; bzf->strm.avail_in = len; bzf->strm.next_in = buf; while (True) { bzf->strm.avail_out = BZ_MAX_UNUSED; bzf->strm.next_out = bzf->buf; ret = BZ2_bzCompress ( &(bzf->strm), BZ_RUN ); if (ret != BZ_RUN_OK) { BZ_SETERR(ret); return; }; if (bzf->strm.avail_out < BZ_MAX_UNUSED) { n = BZ_MAX_UNUSED - bzf->strm.avail_out; n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar), n, bzf->handle ); if (n != n2 || ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return; }; } if (bzf->strm.avail_in == 0) { BZ_SETERR(BZ_OK); return; }; } } /*---------------------------------------------------*/ void BZ_API(BZ2_bzWriteClose) ( int* bzerror, BZFILE* b, int abandon, unsigned int* nbytes_in, unsigned int* nbytes_out ) { BZ2_bzWriteClose64 ( bzerror, b, abandon, nbytes_in, NULL, nbytes_out, NULL ); } void BZ_API(BZ2_bzWriteClose64) ( int* bzerror, BZFILE* b, int abandon, unsigned int* nbytes_in_lo32, unsigned int* nbytes_in_hi32, unsigned int* nbytes_out_lo32, unsigned int* nbytes_out_hi32 ) { Int32 n, n2, ret; bzFile* bzf = (bzFile*)b; if (bzf == NULL) { BZ_SETERR(BZ_OK); return; }; if (!(bzf->writing)) { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; if (ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return; }; if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = 0; if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = 0; if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = 0; if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = 0; if ((!abandon) && bzf->lastErr == BZ_OK) { while (True) { bzf->strm.avail_out = BZ_MAX_UNUSED; bzf->strm.next_out = bzf->buf; ret = BZ2_bzCompress ( &(bzf->strm), BZ_FINISH ); if (ret != BZ_FINISH_OK && ret != BZ_STREAM_END) { BZ_SETERR(ret); return; }; if (bzf->strm.avail_out < BZ_MAX_UNUSED) { n = BZ_MAX_UNUSED - bzf->strm.avail_out; n2 = fwrite ( (void*)(bzf->buf), sizeof(UChar), n, bzf->handle ); if (n != n2 || ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return; }; } if (ret == BZ_STREAM_END) break; } } if ( !abandon && !ferror ( bzf->handle ) ) { fflush ( bzf->handle ); if (ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return; }; } if (nbytes_in_lo32 != NULL) *nbytes_in_lo32 = bzf->strm.total_in_lo32; if (nbytes_in_hi32 != NULL) *nbytes_in_hi32 = bzf->strm.total_in_hi32; if (nbytes_out_lo32 != NULL) *nbytes_out_lo32 = bzf->strm.total_out_lo32; if (nbytes_out_hi32 != NULL) *nbytes_out_hi32 = bzf->strm.total_out_hi32; BZ_SETERR(BZ_OK); BZ2_bzCompressEnd ( &(bzf->strm) ); free ( bzf ); } /*---------------------------------------------------*/ BZFILE* BZ_API(BZ2_bzReadOpen) ( int* bzerror, FILE* f, int verbosity, int small, void* unused, int nUnused ) { bzFile* bzf = NULL; int ret; BZ_SETERR(BZ_OK); if (f == NULL || (small != 0 && small != 1) || (verbosity < 0 || verbosity > 4) || (unused == NULL && nUnused != 0) || (unused != NULL && (nUnused < 0 || nUnused > BZ_MAX_UNUSED))) { BZ_SETERR(BZ_PARAM_ERROR); return NULL; }; if (ferror(f)) { BZ_SETERR(BZ_IO_ERROR); return NULL; }; bzf = malloc ( sizeof(bzFile) ); if (bzf == NULL) { BZ_SETERR(BZ_MEM_ERROR); return NULL; }; BZ_SETERR(BZ_OK); bzf->initialisedOk = False; bzf->handle = f; bzf->bufN = 0; bzf->writing = False; bzf->strm.bzalloc = NULL; bzf->strm.bzfree = NULL; bzf->strm.opaque = NULL; while (nUnused > 0) { bzf->buf[bzf->bufN] = *((UChar*)(unused)); bzf->bufN++; unused = ((void*)( 1 + ((UChar*)(unused)) )); nUnused--; } ret = BZ2_bzDecompressInit ( &(bzf->strm), verbosity, small ); if (ret != BZ_OK) { BZ_SETERR(ret); free(bzf); return NULL; }; bzf->strm.avail_in = bzf->bufN; bzf->strm.next_in = bzf->buf; bzf->initialisedOk = True; return bzf; } /*---------------------------------------------------*/ void BZ_API(BZ2_bzReadClose) ( int *bzerror, BZFILE *b ) { bzFile* bzf = (bzFile*)b; BZ_SETERR(BZ_OK); if (bzf == NULL) { BZ_SETERR(BZ_OK); return; }; if (bzf->writing) { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; if (bzf->initialisedOk) (void)BZ2_bzDecompressEnd ( &(bzf->strm) ); free ( bzf ); } /*---------------------------------------------------*/ int BZ_API(BZ2_bzRead) ( int* bzerror, BZFILE* b, void* buf, int len ) { Int32 n, ret; bzFile* bzf = (bzFile*)b; BZ_SETERR(BZ_OK); if (bzf == NULL || buf == NULL || len < 0) { BZ_SETERR(BZ_PARAM_ERROR); return 0; }; if (bzf->writing) { BZ_SETERR(BZ_SEQUENCE_ERROR); return 0; }; if (len == 0) { BZ_SETERR(BZ_OK); return 0; }; bzf->strm.avail_out = len; bzf->strm.next_out = buf; while (True) { if (ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return 0; }; if (bzf->strm.avail_in == 0 && !myfeof(bzf->handle)) { n = fread ( bzf->buf, sizeof(UChar), BZ_MAX_UNUSED, bzf->handle ); if (ferror(bzf->handle)) { BZ_SETERR(BZ_IO_ERROR); return 0; }; bzf->bufN = n; bzf->strm.avail_in = bzf->bufN; bzf->strm.next_in = bzf->buf; } ret = BZ2_bzDecompress ( &(bzf->strm) ); if (ret != BZ_OK && ret != BZ_STREAM_END) { BZ_SETERR(ret); return 0; }; if (ret == BZ_OK && myfeof(bzf->handle) && bzf->strm.avail_in == 0 && bzf->strm.avail_out > 0) { BZ_SETERR(BZ_UNEXPECTED_EOF); return 0; }; if (ret == BZ_STREAM_END) { BZ_SETERR(BZ_STREAM_END); return len - bzf->strm.avail_out; }; if (bzf->strm.avail_out == 0) { BZ_SETERR(BZ_OK); return len; }; } return 0; /*not reached*/ } /*---------------------------------------------------*/ void BZ_API(BZ2_bzReadGetUnused) ( int* bzerror, BZFILE* b, void** unused, int* nUnused ) { bzFile* bzf = (bzFile*)b; if (bzf == NULL) { BZ_SETERR(BZ_PARAM_ERROR); return; }; if (bzf->lastErr != BZ_STREAM_END) { BZ_SETERR(BZ_SEQUENCE_ERROR); return; }; if (unused == NULL || nUnused == NULL) { BZ_SETERR(BZ_PARAM_ERROR); return; }; BZ_SETERR(BZ_OK); *nUnused = bzf->strm.avail_in; *unused = bzf->strm.next_in; } #endif /*---------------------------------------------------*/ /*--- Misc convenience stuff ---*/ /*---------------------------------------------------*/ /*---------------------------------------------------*/ int BZ_API(BZ2_bzBuffToBuffCompress) ( char* dest, unsigned int* destLen, char* source, unsigned int sourceLen, int blockSize100k, int verbosity, int workFactor ) { bz_stream strm; int ret; if (dest == NULL || destLen == NULL || source == NULL || blockSize100k < 1 || blockSize100k > 9 || verbosity < 0 || verbosity > 4 || workFactor < 0 || workFactor > 250) return BZ_PARAM_ERROR; if (workFactor == 0) workFactor = 30; strm.bzalloc = NULL; strm.bzfree = NULL; strm.opaque = NULL; ret = BZ2_bzCompressInit ( &strm, blockSize100k, verbosity, workFactor ); if (ret != BZ_OK) return ret; strm.next_in = source; strm.next_out = dest; strm.avail_in = sourceLen; strm.avail_out = *destLen; ret = BZ2_bzCompress ( &strm, BZ_FINISH ); if (ret == BZ_FINISH_OK) goto output_overflow; if (ret != BZ_STREAM_END) goto errhandler; /* normal termination */ *destLen -= strm.avail_out; BZ2_bzCompressEnd ( &strm ); return BZ_OK; output_overflow: BZ2_bzCompressEnd ( &strm ); return BZ_OUTBUFF_FULL; errhandler: BZ2_bzCompressEnd ( &strm ); return ret; } /*---------------------------------------------------*/ int BZ_API(BZ2_bzBuffToBuffDecompress) ( char* dest, unsigned int* destLen, char* source, unsigned int sourceLen, int small, int verbosity ) { bz_stream strm; int ret; if (dest == NULL || destLen == NULL || source == NULL || (small != 0 && small != 1) || verbosity < 0 || verbosity > 4) return BZ_PARAM_ERROR; strm.bzalloc = NULL; strm.bzfree = NULL; strm.opaque = NULL; ret = BZ2_bzDecompressInit ( &strm, verbosity, small ); if (ret != BZ_OK) return ret; strm.next_in = source; strm.next_out = dest; strm.avail_in = sourceLen; strm.avail_out = *destLen; ret = BZ2_bzDecompress ( &strm ); if (ret == BZ_OK) goto output_overflow_or_eof; if (ret != BZ_STREAM_END) goto errhandler; /* normal termination */ *destLen -= strm.avail_out; BZ2_bzDecompressEnd ( &strm ); return BZ_OK; output_overflow_or_eof: if (strm.avail_out > 0) { BZ2_bzDecompressEnd ( &strm ); return BZ_UNEXPECTED_EOF; } else { BZ2_bzDecompressEnd ( &strm ); return BZ_OUTBUFF_FULL; }; errhandler: BZ2_bzDecompressEnd ( &strm ); return ret; } /*---------------------------------------------------*/ /*-- Code contributed by Yoshioka Tsuneo (QWF00133@niftyserve.or.jp/tsuneo-y@is.aist-nara.ac.jp), to support better zlib compatibility. This code is not _officially_ part of libbzip2 (yet); I haven't tested it, documented it, or considered the threading-safeness of it. If this code breaks, please contact both Yoshioka and me. --*/ /*---------------------------------------------------*/ /*---------------------------------------------------*/ /*-- return version like "0.9.0c". --*/ const char * BZ_API(BZ2_bzlibVersion)(void) { return BZ_VERSION; } #ifndef BZ_NO_STDIO /*---------------------------------------------------*/ #if defined(_WIN32) || defined(OS2) || defined(MSDOS) # include # include # define SET_BINARY_MODE(file) setmode(fileno(file),O_BINARY) #else # define SET_BINARY_MODE(file) #endif static BZFILE * bzopen_or_bzdopen ( const char *path, /* no use when bzdopen */ int fd, /* no use when bzdopen */ const char *mode, int open_mode) /* bzopen: 0, bzdopen:1 */ { int bzerr; char unused[BZ_MAX_UNUSED]; int blockSize100k = 9; int writing = 0; char mode2[10] = ""; FILE *fp = NULL; BZFILE *bzfp = NULL; int verbosity = 0; int workFactor = 30; int smallMode = 0; int nUnused = 0; if (mode == NULL) return NULL; while (*mode) { switch (*mode) { case 'r': writing = 0; break; case 'w': writing = 1; break; case 's': smallMode = 1; break; default: if (isdigit((int)(*mode))) { blockSize100k = *mode-BZ_HDR_0; } } mode++; } strcat(mode2, writing ? "w" : "r" ); strcat(mode2,"b"); /* binary mode */ if (open_mode==0) { if (path==NULL || strcmp(path,"")==0) { fp = (writing ? stdout : stdin); SET_BINARY_MODE(fp); } else { fp = fopen(path,mode2); } } else { #ifdef BZ_STRICT_ANSI fp = NULL; #else fp = fdopen(fd,mode2); #endif } if (fp == NULL) return NULL; if (writing) { /* Guard against total chaos and anarchy -- JRS */ if (blockSize100k < 1) blockSize100k = 1; if (blockSize100k > 9) blockSize100k = 9; bzfp = BZ2_bzWriteOpen(&bzerr,fp,blockSize100k, verbosity,workFactor); } else { bzfp = BZ2_bzReadOpen(&bzerr,fp,verbosity,smallMode, unused,nUnused); } if (bzfp == NULL) { if (fp != stdin && fp != stdout) fclose(fp); return NULL; } return bzfp; } /*---------------------------------------------------*/ /*-- open file for read or write. ex) bzopen("file","w9") case path="" or NULL => use stdin or stdout. --*/ BZFILE * BZ_API(BZ2_bzopen) ( const char *path, const char *mode ) { return bzopen_or_bzdopen(path,-1,mode,/*bzopen*/0); } /*---------------------------------------------------*/ BZFILE * BZ_API(BZ2_bzdopen) ( int fd, const char *mode ) { return bzopen_or_bzdopen(NULL,fd,mode,/*bzdopen*/1); } /*---------------------------------------------------*/ int BZ_API(BZ2_bzread) (BZFILE* b, void* buf, int len ) { int bzerr, nread; if (((bzFile*)b)->lastErr == BZ_STREAM_END) return 0; nread = BZ2_bzRead(&bzerr,b,buf,len); if (bzerr == BZ_OK || bzerr == BZ_STREAM_END) { return nread; } else { return -1; } } /*---------------------------------------------------*/ int BZ_API(BZ2_bzwrite) (BZFILE* b, void* buf, int len ) { int bzerr; BZ2_bzWrite(&bzerr,b,buf,len); if(bzerr == BZ_OK){ return len; }else{ return -1; } } /*---------------------------------------------------*/ int BZ_API(BZ2_bzflush) (BZFILE *b) { /* do nothing now... */ return 0; } /*---------------------------------------------------*/ void BZ_API(BZ2_bzclose) (BZFILE* b) { int bzerr; FILE *fp = ((bzFile *)b)->handle; if (b==NULL) {return;} if(((bzFile*)b)->writing){ BZ2_bzWriteClose(&bzerr,b,0,NULL,NULL); if(bzerr != BZ_OK){ BZ2_bzWriteClose(NULL,b,1,NULL,NULL); } }else{ BZ2_bzReadClose(&bzerr,b); } if(fp!=stdin && fp!=stdout){ fclose(fp); } } /*---------------------------------------------------*/ /*-- return last error code --*/ static char *bzerrorstrings[] = { "OK" ,"SEQUENCE_ERROR" ,"PARAM_ERROR" ,"MEM_ERROR" ,"DATA_ERROR" ,"DATA_ERROR_MAGIC" ,"IO_ERROR" ,"UNEXPECTED_EOF" ,"OUTBUFF_FULL" ,"CONFIG_ERROR" ,"???" /* for future */ ,"???" /* for future */ ,"???" /* for future */ ,"???" /* for future */ ,"???" /* for future */ ,"???" /* for future */ }; const char * BZ_API(BZ2_bzerror) (BZFILE *b, int *errnum) { int err = ((bzFile *)b)->lastErr; if(err>0) err = 0; *errnum = err; return bzerrorstrings[err*-1]; } #endif /*-------------------------------------------------------------*/ /*--- end bzlib.c ---*/ /*-------------------------------------------------------------*/ Hbun-0.1b2/msg.h13_ÉD13#include "strerr.h" extern void missingattr(const char *, const char *); extern void notcreated(const char *); extern void unknownmeta(const char *, const char *); extern void badbundle(const char *, const char *); extern void badextract(const char *, struct strerr *); extern void badinsert(const char *, struct strerr *); extern void badlookup(const char *, struct strerr *); extern void badexec(const char *); extern void badopenin(const char *); extern void badopenout(const char *); extern void badread(const char *); extern void badrename(const char *, const char *); extern void badseek(const char *); extern void badunlink(const char *); extern void badwrite(const char *); extern void badwritestd(void); extern void badarg(const char *, const char *); extern void badbzip2(const char *); extern void badsys(const char *); extern void badzip(void); extern void nomem(void); extern void usage(const char *); extern void help(void); extern void version(void); Hbun-0.1b2/env.c14_$D14#include "str.h" #include "env.h" extern /*@null@*/char *env_get(const char *s) { int i; unsigned int len; if (!s) return 0; len = str_len(s); for (i = 0;environ[i];++i) if (str_start(environ[i],s) && (environ[i][len] == '=')) return environ[i] + len + 1; return 0; } Hbun-0.1b2/bun.5.html15_˜D15 bun - bun file format

NAME

bun - bun file format

DESCRIPTION

A bun file is a cdb file. cdb provides indexed and sequential access methods to records; refer to the cdb documentation for details of how the database is organized on disk.

The bun file format assumes ASCII throughout.

Index record

A valid bun file contains an index record with a null key (the key of length 0). The data associated with the index is the concatenation of each pathname that appears in the bun file, in netstring format.

Here is an example of a complete index, in cdbmake format. 

    +0,19:->3:foo,3:bar,4:quux,

This index contains three pathnames: foo, bar, and quux.

Head records

A valid bun file contains a head record for each pathname. The head key is H (the capital letter aitch), followed by the pathname. The head data is the concatenation of:

  • a reference number, expressed in decimal, which is unique within this bun file;
  • a file type character;
  • and a string of metadata characters.

The file type character is one of the following.

_ (underscore)
regular file
/
directory
=
(hard) link
@
symbolic link
|
pipe
B
block device
C
character device

Here are some example head records. 

    +4,2:Hfoo->0_
    +4,2:Hbar->1_GZ
    +5,6:Hquux->2/AMOP

The first says that foo is a regular file; its reference number is 0, and there are no metadata records associated with it. bar is also a regular file, its reference number is 1, and it has two metadata records associated with it. quux is a directory; its reference number is 2, and there are four metadata records associated with it.

Content records

All file types, except directory and pipe, require a content record. The content key is D (the capital letter dee), followed by the relevant reference number.

For a file, the content data is the (possibly compressed) contents of the file.

For a link or symbolic link, the content data is the name of the file linked to.

For a device, whether character or block, the content data is the value of st_rdev stored as 8 bytes, big-endian.

Here is a trivial content record; the item with reference number 0 (the regular file foo in this example) contains the words bar and baz on separate lines. 

    +2,8:D0->bar
    baz

Metadata records

Each head record contains a (possibly empty) string of metadata characters. For each character, there is a corresponding metadata record: the key is the metadata character followed by the reference number.

The following metadata characters are defined.

A
Time of the item's last access, in external TAI64NA format.
G
Global file permissions: file permission codes to use in default of specific permissions.
M
Time of the item's last modification, in external TAI64NA format.
O (capital letter oh)
File ownership: concatenation, in netstring format, of the names or IDs of all the owners of the file, and any names that have permissions associated with them. Each begins with a letter showing what sort of name it is: U is a user name; u a numeric user ID; G is a group name; g a numeric group ID; and O is other users.
P
File permissions: concatenation of the file permission codes for each owner in netstring format.
X
Reserved.
Z
Uncompression algorithm.

Here are some example metadata records. 

    +2,6:Z1->gunzip
    +2,18:O2->4:Utjg,4:g312,1:O,
    +2,16:P2->3:RWS,2:RS,2:RS,

These say that file bar can be uncompressed with gunzip; directory quux is owned by tjg, has a numeric group ID of 312, and the permissions are rwxr-xr-x.

File permission codes

The following file permission codes are defined for use in G and P metadata records.

B
G only; directory only. BSD group semantics apply. Corresponds to the meaning in Unix of the setgid bit on a directory.
I
P only, and meaningless unless X is also set. When executed, the process acquires the owner's credentials. Corresponds to the usual meaning of Unix's setuid (for a U or u owner) and setgid (for a G or g owner) bits.
M
G only. Mandatory file locking applies.
P
G only; directory only. Restricted write permission: users may only rename and delete files they own within this directory. Corresponds to the meaning of Unix's directory sticky bit.
R
Read access.
S
Directory only. Search access.
T
G only, and meaningless unless X is also set. The program's text segment should remain in VM. Corresponds to the usual meaning of Unix's sticky bit.
W
Write access.
X
Execute access.

AUTHOR

Tim Goodwin; cdb by Dan Bernstein.

Hbun-0.1b2/bun.116_ZMD16.TH BUN 1 2001\-06\-11 "Public Domain Documentation" "Unix Software \- Commands" .SH "NAME" .PP bun \- bundle many files into a single file .SH "SYNOPSIS" .PP \fBbun\fR \fIcommand\fR [ \fB\-\fR\fIflag\fR ... ] \fIbundle\fR [ \fIpathname\fR ... ] .PP \fBbun \-h\fR .PP \fBbun \-v\fR .SH "DESCRIPTION" .PP The \fBbun\fR program is used to bundle many files, directories, symbolic links, etc. into a single \fIbundle\fR file. \fBbun\fR can also be used to extract items from a previously created \fIbundle\fR. .PP \fBbun \-h\fR writes a usage summary to standard output and exits; \fBbun \-v\fR reports the version number of \fBbun\fR to standard output, and exits. Otherwise, \fBbun\fR must be invoked with at least two command line arguments: the \fIcommand\fR specifies which operation to perform (creation, extraction, or table of contents), and the \fIbundle\fR names the file which is to operated on. \fIbundle\fR must be a seekable file (a normal file in the file system; not a pipe, tape device, etc.). .SS Commands .PP The following \fIcommand\fRs are available. .IP "\fB\fBc\fR\fR" create \fIbundle\fR. If one or more \fIpathname\fRs are specified, they are each added to \fIbundle\fR. If no \fIpathname\fRs are specified, \fBbun\fR reads them from standard input, terminated by newlines. .IP "\fB\fBx\fR\fR" extract items from \fIbundle\fR. If one or more \fIpathname\fRs are specified, they are each extracted from \fIbundle\fR. If no \fIpathname\fRs are specified, every item contained in \fIbundle\fR is extracted. .PP In addition to the items stored in \fIbundle\fR, \fBbun\fR creates directories as needed. .IP "\fB\fBt\fR\fR" table of contents. As for the \fBx\fR command, if one or more \fIpathname\fRs are specified, they are each printed to standard output, followed by a newline. If no \fIpathname\fRs are specified, every pathname contained in \fIbundle\fR is printed. .IP "\fB\fBz\fR\fR" create compressed. The \fBz\fR command is equivalent to the \fBc\fR command, except that each regular file is a candidate for compression. .SS Flags .PP Command line \fIflag\fRs may be concatenated with the \fIcommand\fR, or they may appear as separate arguments introduced by \fB\-\fR (a hyphen). A hyphen is also permitted before the \fIcommand\fR. Thus, the following are equivalent. .ft CW .nf bun clv mybun.bun bun \-c \-l \-v mybun.bun bun c \-lv mybun.bun .ft R .fi .PP The argument \fB\-\fR\fB\-\fR (two hyphens) indicates the end of flag processing. It is only necessary if \fIbundle\fR begins, or may begin, with a hyphen. .ft CW .nf bun x \-\- "$BUN" .ft R .fi .PP Two flags specify which meta\-information is to be stored or retrieved. .IP "\fBd\fR" date: file modification and access times. A \fIbundle\fR is capable of storing timestamps with attosecond precision. \fIbun\fR uses as much precision as the underlying filesystem offers: normally nanosecond, microsecond, or second precision. .IP "\fBu\fR" user: file ownership and permission information (including group ownership). .PP These flags both work in the same way. If the flag is specified for \fIbundle\fR creation (that is, with the \fBc\fR or \fBz\fR commands), that meta\-information is stored in the \fIbundle\fR. .PP During extraction, \fBbun\fR by default retrieves all meta\-information present in \fIbundle\fR. However, if the \fBd\fR or \fBu\fR flag is specified on the command line, the corresponding meta\-information will be ignored. (It is not an error to ignore meta\-information that is not present!) .PP Likewise, when listing the verbose table of contents (the \fBtv\fR command), specifying \fBd\fR or \fBu\fR suppresses the corresponding meta\-information. .PP Although a little unusual, this scheme reflects common usage. Most \fIbundle\fRs do not need to store date meta\-information: the default is not to store it. But if a \fIbundle\fR includes date meta\-information, it must be there for a reason: the default is to use it. .PP Other flags which can be specified when creating a \fIbundle\fR are as follows. .IP "\fBf\fR" flat mode. By default, when a pathname (either mentioned on the command line, or read from standard input) names a directory, the directory and its contents are stored in \fIbundle\fR, recursively. If the \fBf\fR flag is in effect, just the directory is stored. .IP "\fBi\fR (lower case letter aye)" use numeric identifiers for user information. This flag only makes sense in combination with \fBu\fR; it instructs \fBbun\fR to store owner information using your system's numeric identifiers, instead of names. .IP "\fBl\fR (lower case letter ell)" look for hard links. By default, \fBbun\fR doesn't make the extra effort to detect hard links when creating \fIbundle\fR. If the \fBl\fR flag is in effect, hard links will be detected: the contents of a multiply\-linked file will only be stored once in \fIbundle\fR; each subsequent occurrence will be stored as a link. When extracting from a \fIbundle\fR containing hard links, \fBbun\fR always re\-creates the links. .IP "\fBs\fR" follow symbolic links. By default, \fBbun\fR stores symbolic links as such in \fIbundle\fR. If the \fBs\fR flag is in effect, the target of the link is stored instead. If this flag is present, and the part of the file system being stored contains a loop (a symbolic link pointing to one of its own parent directories), \fBbun\fR will loop till it exhausts some system resource (usually the limit on open file descriptors). .PP Other flags which can be specified when extracting are as follows. .IP "\fBa\fR" use absolute pathnames. During \fIbundle\fR creation, \fBbun\fR always stores pathnames exactly as they were specified. By default, \fBbun\fR removes a leading \fI/\fR from absolute pathnames during extraction: this provides flexibility, and some degree of protection from mistakes. If the \fBa\fR flag is present, all files will be extracted to the stored pathnames, even if they are absolute. .IP "\fBo\fR (lower case letter oh)" copy regular files to standard output; anything which is not a regular file is silently skipped. .PP Flags which can be specified for any operation are as follows. .IP "\fBn\fR" write \fIpathname\fRs to standard output after they are added to, or extracted from, the \fIbundle\fR. .IP "\fBq\fR" quicker, but safe only for quiescent trees. By default, \fBbun x\fR extracts files (everything except directories) to a temporary name, synchronizes the file (that is, ensures that the file is physically on the disk), then atomically renames the new file. If the \fBq\fR flag is present, files are extracted in place (overwritten) and not synchronized. This is considerably faster, but voids \fBbun\fR's reliability guarantee. .PP Similarly, \fBbun c\fR creates \fIbundle\fR with a temporary name, and, if there are no errors, synchronizes it and renames it into place. \fBbun cq\fR writes \fIbundle\fR in place, which is slightly quicker (the difference is not as significant as when extracting). Additionally, if a \fIpathname\fR cannot be inserted (perhaps because it is unreadable), \fBbun cq\fR will create \fIbundle\fR regardless; \fBbun c\fR will not. .PP \fBbun tq\fR is permitted, but the \fBq\fR flag has no effect. .IP "\fBv\fR" write verbose information about each file to standard output; see below for details. .IP "\fB0\fR (digit zero)" use NUL terminated pathnames. When reading pathnames from standard input, or writing them to standard output, by default they are terminated by the LF character. If the \fB0\fR flag is in effect, they are terminated by NUL instead, permitting pathnames which contain LF to appear in \fIbundle\fR. Note that in the command \fBbun cn0 foo.bun\fR (with no \fIpathname\fRs specified on the command line), the \fB0\fR flag causes both the input and the output to be NUL terminated. .SS Verbose table of contents .PP When the \fBv\fR flag is present, verbose information about each file is written to standard output. For example: .ft CW .nf $ bun zudv bar.bun /bin/su /bin/su file 14124 G:RWX M:1999\-08\-18T02:31:25.000Z A:2000\-07\-11T03:05:37.000Z P:Uroot(IRWX),Gsystem(RX),O(RX) Z:gunzip .ft R .fi .PP Each line of output has at least the following fields, separated by spaces. .IP "Name" The pathname of the item, as stored in the bundle. .IP "Type" One of \fBfile\fR, \fBdirectory\fR, \fBpipe\fR, \fBblock\-special\fR, or \fBcharacter\-special\fR. .IP "Size" The size of the data associated with this item, in bytes. This will be 0 for directories, and pipes. For compressed files, it is the size of the compressed data. .PP These may be followed by several optionals fields, each of which is introduced by a capital letter followed by a colon. .IP "A" The access time of the item. Times are expressed in UTC, to milli\-second precision. .IP "G" Global permissions; see below. .IP "M" The modification time of the item. .IP "P" Specific owners and permissions associated with the item; see below. .IP "Z" The uncompression algorithm, if the item is compressed. .SS Compression .PP With the \fBz\fR command, each regular file encountered is a candidate for compression. Compression is controlled by three environment variables. .IP "\fBBUN_ZIP\fR (default gzip)" The command to use for compression: it must be found in \fBPATH\fR (or be an absolute pathname); it must read from standard input and write compressed data to standard output. .PP If \fBBUN_ZIP\fR is set, \fBBUN_UNZIP\fR must be set, too. .IP "\fBBUN_UNZIP\fR (default gunzip)" The name of the uncompression algorithm. This is stored in \fIbundle\fR; during extraction, it is interpreted as the filter command to run. It should be an unadorned name: recommended values are gunzip or bunzip2. .IP "\fBBUN_ZIP_MIN\fR (default 188)" The minimum file size to compress. Files smaller than this will not be compressed. .PP Note that all these variables, including \fBBUN_UNZIP\fR, are only relevant during \fIbundle\fR creation. The uncompression command to use is stored in \fIbundle\fR itself; changing \fBBUN_UNZIP\fR has no effect on extraction. .SS File permissions .PP \fBbun \-cu\fR stores user information as names, not numeric UIDs, GIDs, etc. If the \fBv\fR flag is in effect, user and permission information is introduced by \fBP:\fR, which is followed by a comma separated list. Each element of the list consists of a letter indicating what sort of user this is, an optional name, and a parenthesized list (possibly empty) of the permissions associated with that user. .IP "U" The user that owns the item. .IP "u" The numeric ID of the user that owns the item. .IP "G" The group that owns the item. .IP "g" The numeric ID of the group that owns the item. .IP "O" Other, which must have an empty name: the permissions granted to all users not otherwise named. .PP In addition to the full ownership and permissions information which is stored with \fBbun \-cu\fR, \fBbun\fR also stores \fIglobal permissions\fR information, whether the \fBu\fR flag was specified or not. If the \fBv\fR flag is in effect, \fIglobal permissions\fR are introduced by \fBG:\fR. The \fIglobal permissions\fR are the union of all the specific read, write, search, and execute permissions: if some user can execute a file, it will have e\fBX\fRecute global permissions. To save some space, the most common \fIglobal permissions\fR are not stored: \fBRWS\fR is the default for a directory; \fBRW\fR for any other type. .PP During \fIbundle\fR extraction, the \fIglobal permissions\fR are used if there is no other permissions data, or if the \fBu\fR flag is in effect. \fIGlobal permissions\fR are modified by the process's \fIumask\fR before being applied. .PP The following permission codes may be reported if the \fBv\fR flag is in effect. .IP "R" Read access. .IP "S" Directory only. Search access. .IP "W" Write access. .IP "X" Execute access. .IP "B" \fBG\fR only; directory only. BSD group semantics apply. Corresponds to the meaning in Unix of the setgid bit on a directory. .IP "I" \fBP\fR only, and meaningless unless \fBX\fR is also set. When executed, the process acquires the owner's credentials. Corresponds to the usual meaning of Unix's setuid bit (if this is a \fBU\fR owner) or setgid bit (if this is a \fBG\fR owner). .IP "M" \fBG\fR only. Mandatory file locking applies. .IP "P" \fBG\fR only; directory only. Restricted write permission: users may only rename and delete files they own within this directory. Corresponds to the meaning of Unix's directory sticky bit. .IP "T" \fBG\fR only, and meaningless unless \fBX\fR is also set. The program's text segment should remain in VM. Corresponds to the usual meaning of Unix's sticky bit. .SH "EXAMPLES" .SS Specifying pathnames for creation .PP These two examples are equivalent: they demonstrate the two ways of supplying \fIpathname\fRs to the \fBc\fRreate command. .ft CW .nf bun c foo.bun foo1.c foo2.c { echo foo1.c; echo foo2.c; } | bun c foo.bun .ft R .fi .PP There is little point in using the second form with a fixed list of \fIpathname\fRs; it is intended to be combined with tools such as \fBfind\fR(1). .ft CW .nf find foo \-name '*.c' | bun c foo.bun .ft R .fi .SS Specifying pathnames for table of contents .PP Specifying a \fIpathname\fR in combination with the \fBt\fR command is a quick way to check if a \fIbundle\fR contains that \fIpathname\fR. .ft CW .nf $ bun t foo.bun foo1.c foo3.c foo1.c bun: cannot look up `foo3.c': head record missing .ft R .fi .PP The exit status of \fBbun\fR will be zero only if every \fIpathname\fR specified was found in \fIbundle\fR. .SS Date and user meta\-information .PP This command creates a \fIbundle\fR that includes date meta\-information for each file. .ft CW .nf bun cd mybun.bun * .ft R .fi .PP The usual command will extract all files from \fImybun.bun\fR, and (attempt to) set each file's date meta\-information to the stored values. .ft CW .nf bun x mybun.bun .ft R .fi .PP But if the \fBd\fR flag is specified during extraction, .ft CW .nf bun xd mybun.bun .ft R .fi .PP the date meta\-information will be ignored, just as if the \fBd\fR flag had not been specified for the creation of \fImybun.bun\fR. .SS Users and permissions .PP Here is a motley collection of (empty) files, showing a variety of owners and permissions. .ft CW .nf $ ls \-l total 0 \-r\-xr\-xr\-t 1 ftp adm 0 Jul 11 11:33 01555 \-rwxrwsr\-x 1 bin mem 0 Jul 11 11:33 02775 \-r\-\-\-\-\-\-\-\- 1 tjg xra 0 Jul 11 11:32 0400 \-r\-\-r\-\-rw\- 1 nobody nobody 0 Jul 11 11:32 0446 \-rwsr\-xr\-x 1 root system 0 Jul 11 11:32 04755 \-rwxr\-xr\-x 1 qmailq qmail 0 Jul 11 11:32 0755 $ bun cuv bar.bun * 01555 file 0 G:RTX P:Uftp(RX),Gadm(RX),O(RX) 02775 file 0 G:RWX P:Ubin(RWX),Gmem(IRWX),O(RX) 0400 file 0 G:R P:Utjg(R),Gxra(),O() 0446 file 0 P:Unobody(R),Gnobody(R),O(RW) 04755 file 0 G:RWX P:Uroot(IRWX),Gsystem(RX),O(RX) 0755 file 0 G:RWX P:Uqmailq(RWX),Gqmail(RX),O(RX) .ft R .fi .SS Global permissions .PP Here is the \fBbun tv\fR listing for a particular \fIbundle\fR. Each file's name is descriptive of its permissions. .ft CW .nf read\-execute file 4 G:RX read\-only file 4 G:R read\-search directory 0 G:RS read\-write file 4 read\-write\-search directory 0 write\-execute file 4 G:RWX .ft R .fi .PP Each file's name is descriptive of its permissions. \fBbun\fR has not stored any global permissions for the file \fIread\-write\fR, nor the directory \fIread\-write\-search\fR, as these are the default. .PP If a \fIumask\fR of \fB027\fR were in effect, unpacking the above \fIbundle\fR would produce the following file permissions. .ft CW .nf \-r\-xr\-x\-\-\- [...] read\-execute \-r\-\-r\-\-\-\-\- [...] read\-only dr\-xr\-x\-\-\- [...] read\-search \-rw\-r\-\-\-\-\- [...] read\-write drwxr\-x\-\-\- [...] read\-write\-search \-rwxr\-x\-\-\- [...] write\-execute .ft R .fi .SS The 0 flag .PP The \fB0\fR flag works well in combination with a \fBfind\fR(1) that supports \fB\-print0\fR, and \fBxargs\fR(1) that supports \fB\-0\fR. .ft CW .nf find foo \-type f \-print0 | bun c0 foo.bun bun t0 foo.bun | xargs \-0 rm \-f .ft R .fi .PP It is only necessary if you expect \fIpathname\fRs which may contain the LF character: since \fBbun\fR does not split input at any other character, it can handle \fIpathname\fRs that contain spaces even without the \fB0\fR flag. .SS The f flag .PP The \fBf\fR flag is particularly useful when using \fBfind\fR(1) to select files for inclusion in \fIbundle\fR. .ft CW .nf find foo \-name RCS \-prune \-o \-print | bun cf foo.bun .ft R .fi .SS The o flag .PP The \fBo\fR flag is a quick way to examine a file in a \fIbundle\fR, without having to extract anything. .ft CW .nf bun xo pkg\-1.1.bun pkg\-1.1/README | more .ft R .fi .PP It can be combined with bun \-t to loop over every file in a \fIbundle\fR. .ft CW .nf for i in `bun t foo.bun`; do echo $i bun xo foo.bun $i | wc done .ft R .fi .SS The i flag .PP The \fBi\fR flag is useful if you need to bundle up a tree which contains user or group IDs that cannot be looked up; for example, if they belong to an account which has been deleted. .ft CW .nf $ bun cu gone.bun /export/home/gone bun: cannot insert `/export/home/gone': cannot find name for uid `123': file does not exist bun: warning: `bar.bun' not created due to earlier errors $ bun cuiv gone.bun /export/home/gone /export/home/gone directory 0 P:u123(RSW),g123(RS),O(RS) .ft R .fi .PP .ps -2 A side note: if you're wondering what ``file does not exist'' means here, that is the error reported by the \fBgetpwuid\fR(3) call. \fBbun\fR reports this error back to you, even though most flavours of Unix don't return sensible error information from \fBgetpwuid\fR(3) and friends. .ps +2 .SH "RETURN VALUE" .PP \fBbun\fR exits with status 0 if it was able to do everything it was asked to. If not, suitable diagnostics are printed, and the exit status is 1. .SH "RELIABILITY GUARANTEE" .PP The \fBbun\fR reliability guarantee is a design goal, and depends on both \fBbun\fR and your operating system being free of bugs. No legal warranty is expressed or implied. .PP \fBbun\fR promises that, at all times, the files it creates will either i) not exist with their final names; or ii) be complete. The promise applies even if the operating system halts in the middle of a \fBbun\fR operation. The promise applies both to the single \fIbundle\fR created with \fBbun c\fR, and the (potentially) many files created with \fBbun x\fR. .PP The reliability guarantee does not apply if the \fBq\fR flag is present: the \fBq\fR flag should only be used for quiescent trees. .PP For example, if you are unpacking the source of a package which is distributed as a \fIbundle\fR, you are presumably creating a completely new directory tree, and using the \fBq\fR flag is perfectly sensible. If you are unpacking a \fIbundle\fR which contains \fI/etc/passwd\fR, you definitely want the default, reliable mode of operation. .SH "SEE ALSO" .PP \fBbun\fR(5). .SH "BUGS" .PP There should be a way of specifying flags (particularly \fBd\fR, \fBu\fR, and \fBz\fR) on a per\-\fIpathname\fR basis. .SH "RESTRICTIONS" .PP A \fIbundle\fR cannot exceed 4GB. .PP It is theoretically possible to confuse \fBbun\fR's detection of hard links (the \fBl\fR flag), by deleting and creating files within the file tree being bundled. .PP It is not meaningful to attempt to store a (Unix domain) socket. .PP Files of type block\-special and character\-special are inherently unportable. .SH "AUTHOR" .PP Tim Goodwin; library code from Dan Bernstein. Hbun-0.1b2/tryst_xtimespec.c17_±D17#include int main(void) { struct timespec x; struct stat statbuf; x = statbuf.st_atimespec; x = statbuf.st_mtimespec; x = statbuf.st_ctimespec; return 0; } Hbun-0.1b2/netstr.h18_‚D18#include "cdb.h" #include "list.h" #include "stralloc.h" extern int netstr_cat(stralloc *, stralloc *); extern int netstr_catb(stralloc *, char *, unsigned int); extern int netstr_cats(stralloc *, char *); extern int netstr_get(stralloc *, struct cdb *, unsigned long *); extern int netstr_from_list(struct list *, stralloc *); extern int netstr_to_list(struct cdb *, struct list *); Hbun-0.1b2/trylstat.c19_wD19#include #include int main(void) { struct stat statbuf; lstat("/", &statbuf); return 0; } Hbun-0.1b2/stralloc_pend.c20_™D20#include "alloc.h" #include "stralloc.h" #include "gen_allocdefs.h" GEN_ALLOC_append(stralloc,char,s,len,a,i,n,x,30,stralloc_readyplus,stralloc_append) Hbun-0.1b2/conf-ld21_ÖD21gcc -O2 -Wall -Wshadow -Wpointer-arith -Wbad-function-cast -Wmissing-declarations -Wnested-externs -Wcast-qual -Wcast-align -Wwrite-strings The above command will be used to link object files into an executable. Hbun-0.1b2/stralloc_catb.c22_>D22#include "stralloc.h" #include "byte.h" int stralloc_catb(stralloc *sa, const char *s, unsigned int n) { if (!sa->s) return stralloc_copyb(sa,s,n); if (!stralloc_readyplus(sa,n + 1)) return 0; byte_copy(sa->s + sa->len,n,s); sa->len += n; sa->s[sa->len] = 'Z'; /* ``offensive programming'' */ return 1; } Hbun-0.1b2/extract.c23_ÓD23/* Public domain. */ #include #include #include #include #include #include "alloc.h" #include "assert.h" #include "buffer.h" #include "bun.h" #include "bun_attr.h" #include "bun_cdb.h" #include "bunny.h" #include "byte.h" #include "cdb.h" #include "error.h" #include "filter.h" #include "info.h" #include "msg.h" #include "pathexec.h" #include "stat.h" #include "str.h" #include "stralloc.h" #include "strerr.h" #include "taia.h" #include "unix.h" static int make_path(stralloc *name) { char *end; stralloc dir = { 0 }; struct stat st; /* Find the end of the name. */ end = name->s + name->len - 1; assert(*end == '\0'); /* Strip off last path component. */ while (end > name->s && *end != '/') --end; if (end == name->s) return 1; if (!stralloc_copyb(&dir, name->s, end - name->s)) nomem(); if (!stralloc_0(&dir)) nomem(); if (stat(dir.s, &st) < 0) { if (errno != error_noent) STRERR_SYS3(0, bun_err, "cannot stat `", dir.s, "': "); /* XXX dir.s never freed */ if (make_path(&dir)) if (mkdir(dir.s, 0777) < 0) STRERR_SYS3(0, bun_err, "cannot make directory `", dir.s, "': "); /* XXX dir.s never freed */ } alloc_free(dir.s); return 1; } static int extract_dir(struct bunny *item) { if (unix_mkdir(item->name.s, item->global_attr) < 0) { if (errno == error_exist) return 1; STRERR_SYS3(0, bun_err, "cannot make directory `", item->name.s, "': "); } return 1; } static int extract_file(struct bunny *item) { int fd; item->code.s[0] = 'D'; if (!bun_cdb_seekn(item, item->code.s, item->code.len)) STRERR(0, bun_err, "data missing"); if (flag_out) fd = 1; else { fd = unix_open_trunc(item->tname.s, item->global_attr); if (fd < 0) STRERR_SYS3(0, bun_err, "cannot open `", item->tname.s, "' for output: "); } item->fd = fd; if (item->iscompressed) { if (str_equal(item->unzip, "bunzip2")) { if (bun_cdb_blast_bunzip2(&item->cdb.r, fd) < 0) STRERR_SYS(0, bun_err, "cannot copy from bundle to file: "); } else { const char *arg[2]; arg[0] = item->unzip; arg[1] = 0; fd = filter_out(fd, arg); if (bun_cdb_blast(&item->cdb.r, fd) < 0) { STRERR_SYS(0, bun_err, "cannot copy from bundle to file: "); } } } else { if (bun_cdb_blast(&item->cdb.r, fd) < 0) { STRERR_SYS(0, bun_err, "cannot copy from bundle to file: "); } } if (item->iscompressed && !str_equal(item->unzip, "bunzip2")) { int status; status = filter_end(fd); if (!WIFEXITED(status) || WEXITSTATUS(status) != 0) STRERR(0, bun_err, "unzip command failed"); } return 1; } static int do_link(struct bunny *item, int (*fn)(const char *, const char *), const char *errstr) { item->code.s[0] = 'D'; if (!bun_cdb_fetchn(item, item->code.s, item->code.len, &item->link)) STRERR(0, bun_err, "data missing"); if (!stralloc_0(&item->link)) nomem(); if ((*fn)(item->link.s, item->tname.s) < 0) STRERR_SYS3(0, bun_err, errstr, item->link.s, "': "); return 1; } static int extract_link(struct bunny *item) { return do_link(item, &link, "cannot link to `"); } static int extract_slink(struct bunny *item) { if (!haslstat) STRERR(0, bun_err, "symbolic links not supported"); return do_link(item, &symlink, "cannot symlink to `"); } static int extract_pipe(struct bunny *item) { if (unix_make_pipe(item->tname.s, item->global_attr) < 0) STRERR_SYS3(0, bun_err, "cannot make pipe `", item->tname.s, "': "); return 1; } static int do_special(struct bunny *item, int (*fn)(char *, bun_attr_t, unsigned long), const char *errstr) { int i; static stralloc str_rdev; unsigned long rdev; item->code.s[0] = 'D'; if (!bun_cdb_fetchn(item, item->code.s, item->code.len, &str_rdev)) STRERR(0, bun_err, "data missing"); rdev = 0; for (i = 0; i < bun_rdev_size; ++i) { rdev <<= 8; rdev |= str_rdev.s[i]; } if ((*fn)(item->tname.s, item->global_attr, rdev) < 0) STRERR_SYS3(0, bun_err, errstr, item->tname.s, "': "); return 1; } static int extract_chars(struct bunny *item) { return do_special(item, &unix_make_chars, "cannot make character special `"); } static int extract_blocks(struct bunny *item) { return do_special(item, &unix_make_blocks, "cannot make block special `"); } static int (*extractors[])(struct bunny *) = { extract_file, extract_dir, extract_link, extract_slink, extract_pipe, extract_chars, extract_blocks, 0 }; int extract(struct bunny *item) { assert(extractors[bun_file] == extract_file); assert(extractors[bun_dir] == extract_dir); assert(extractors[bun_link] == extract_link); assert(extractors[bun_slink] == extract_slink); assert(extractors[bun_pipe] == extract_pipe); assert(extractors[bun_chars] == extract_chars); assert(extractors[bun_blocks] == extract_blocks); assert(extractors[bun_unknown] == 0); if (!bunny_in(item)) { badextract(item->name.s, &bun_err); return 0; } if (flag_out) { if (item->type != bun_file) return 1; } else { if (!flag_abs) while (item->name.s[0] == '/') { --item->name.len; byte_copy(item->name.s, item->name.len, item->name.s + 1); } if (!make_path(&item->name)) { badextract(item->name.s, &bun_err); return 0; } assert(item->name.s[item->name.len - 1] == '\0'); if (!flag_quick && item->type != bun_dir) { if (!unix_tmp_name(&item->tname, item->name.s)) nomem(); } else { if (!stralloc_copy(&item->tname, &item->name)) nomem(); } } assert(extractors[item->type] != 0); if (!(*extractors[item->type])(item) || (!flag_out && !bun2unix(item))) { assert(item->name.s[item->name.len - 1] == '\0'); badextract(item->name.s, &bun_err); if (!flag_quick && item->type != bun_dir) (void)unlink(item->tname.s); return 0; } if (flag_name) { (void)info(item); if (buffer_flush(buffer_1) == -1) badwritestd(); } return 1; } Hbun-0.1b2/cdb_make.h24_jD24/* Public domain. */ #ifndef CDB_MAKE_H #define CDB_MAKE_H #include "buffer.h" #include "uint32.h" #define CDB_HPLIST 1000 struct cdb_hp { uint32 h; uint32 p; } ; struct cdb_hplist { struct cdb_hp hp[CDB_HPLIST]; struct cdb_hplist *next; int num; } ; struct cdb_make { char bspace[8192]; char final[2048]; uint32 count[256]; uint32 start[256]; struct cdb_hplist *head; struct cdb_hp *split; /* includes space for hash */ struct cdb_hp *hash; uint32 numentries; buffer b; uint32 pos; int fd; } ; extern int cdb_make_start(struct cdb_make *,int); extern int cdb_make_addbegin(struct cdb_make *,unsigned int,unsigned int); extern int cdb_make_addend(struct cdb_make *,unsigned int,unsigned int,uint32); extern int cdb_make_add(struct cdb_make *,char *,unsigned int,char *,unsigned int); extern int cdb_make_finish(struct cdb_make *); #endif Hbun-0.1b2/library-sgetopt25_D25sgetopt.o subgetopt.o Hbun-0.1b2/bun_hash.h26_ÝD26#include "stralloc.h" struct hash_table { struct hash_item **hashes; unsigned int n; }; int hash_init(struct hash_table *, unsigned int); int hash_insert_once(struct hash_table *, stralloc *, stralloc *, stralloc *); Hbun-0.1b2/error.h27_=D27#ifndef ERROR_H #define ERROR_H #include extern int error_intr; extern int error_nomem; extern int error_noent; extern int error_txtbsy; extern int error_io; extern int error_exist; extern int error_timeout; extern int error_inprogress; extern int error_wouldblock; extern int error_again; extern int error_pipe; extern int error_perm; extern int error_acces; extern int error_nodevice; extern int error_proto; extern int error_isdir; extern int error_connrefused; extern int error_range; extern const char *error_str(int); extern int error_temp(int); #endif Hbun-0.1b2/Manifest28_ÑD28bun.1 bun.1.html bun.5 bun.5.html configure gcc-flags xhtml2man.lhs CHANGES INSTALL README Manifest+ Manifest Makefile default-prefix configure conf-cc conf-ld conf-libs conf-prefix default-prefix package warn-auto.sh target-bun bun.1 bun.5 helper-araucaria helper-statdiff library-alloc library-buffer library-byte library-bz2 library-env library-err library-libbz2 library-libcdb library-libtai library-list library-netstr library-out library-scan library-sgetopt library-str library-stralloc library-unix Makefile+ bun_attr.c bun_cdb_make.c bun_cdb.c bun_hash.c bun.c bunny.c extract.c filter.c info.c insert.c msg.c unix.c araucaria.c statdiff.c alloc.c alloc_re.c buffer.c buffer_0.c buffer_1.c buffer_1s.c buffer_2.c buffer_copy.c buffer_get.c buffer_put.c buffer_read.c buffer_write.c byte_copy.c byte_cr.c byte_diff.c uint32_pack.c uint32_unpack.c blocksort.c bzlib.c compress.c crctable.c decompress.c huffman.c randtable.c env.c error.c error_str.c str_len.c strerr_die.c strerr_sys.c cdb.c cdb_hash.c cdb_make.c caldate_fmjd.c caldate_fmt.c caltime_fmt.c caltime_utc.c leapsecs_init.c leapsecs_read.c leapsecs_sub.c taia_pack.c taia_unpack.c tai_pack.c tai_unpack.c list.c netstr_cat.c netstr_catb.c netstr_cats.c netstr_get.c netstr_list.c out_file.c out_mem.c out_stream.c out_filter_mem.c out_bzip2.c out_bunzip2.c scan_ulong.c sgetopt.c subgetopt.c str_chr.c str_cpy.c str_diff.c str_diffn.c str_start.c stralloc_cat.c stralloc_catb.c stralloc_cats.c stralloc_copy.c stralloc_eady.c stralloc_num.c stralloc_num8.c stralloc_opyb.c stralloc_opys.c stralloc_pend.c open_read.c open_trunc.c pathexec_env.c pathexec_run.c seek_cur.c seek_set.c bun_attr.h bun.h bun_cdb_make.h cdb_make.h error.h mmap.h out.h seek.h stralloc.h buffer.h bun_cdb.h cdb.h msg.h uint32.h alloc.h assert.h bun_hash.h byte.h info.h netstr.h open.h stat.h str.h strerr.h bunny.h filter.h pathexec.h taia.h unix.h caltime.h defaults.h env.h package.h devino.h lchown.h list.h scan.h tai.h utimes.h sgetopt.h readwrite.h bzlib_private.h exit.h caldate.h leapsecs.h gen_allocdefs.h bzlib.h subgetopt.h gen_alloc.h uint64.h features-compile tryst_spare123.c tryst_xtim.c tryst_xtimespec.c features-load trydevino.c trylstat.c tryutimes.c features-run trylchown.c tryulong32.c Hbun-0.1b2/str_cpy.c29_KD29#include "str.h" unsigned int str_copy(register char *s, register const char *t) { register int len; len = 0; for (;;) { if (!(*s = *t)) return len; ++s; ++t; ++len; if (!(*s = *t)) return len; ++s; ++t; ++len; if (!(*s = *t)) return len; ++s; ++t; ++len; if (!(*s = *t)) return len; ++s; ++t; ++len; } } Hbun-0.1b2/tai.h30_»D30#ifndef TAI_H #define TAI_H #include "uint64.h" struct tai { uint64 x; } ; extern void tai_now(struct tai *); #define tai_approx(t) ((double) ((t)->x)) extern void tai_add(struct tai *, struct tai *, struct tai *); extern void tai_sub(struct tai *, struct tai *, struct tai *); #define tai_less(t,u) ((t)->x < (u)->x) #define TAI_PACK 8 extern void tai_pack(char *, struct tai *); extern void tai_unpack(char *, struct tai *); #endif Hbun-0.1b2/stralloc_copy.c31_›D31#include "byte.h" #include "stralloc.h" int stralloc_copy(stralloc *sato,const stralloc *safrom) { return stralloc_copyb(sato,safrom->s,safrom->len); } Hbun-0.1b2/pathexec_env.c32_ýD32#include "stralloc.h" #include "alloc.h" #include "str.h" #include "byte.h" #include "env.h" #include "pathexec.h" static stralloc plus; static stralloc tmp; int pathexec_env(const char *s,const char *t) { if (!s) return 1; if (!stralloc_copys(&tmp,s)) return 0; if (t) { if (!stralloc_cats(&tmp,"=")) return 0; if (!stralloc_cats(&tmp,t)) return 0; } if (!stralloc_0(&tmp)) return 0; return stralloc_cat(&plus,&tmp); } void pathexec(char **argv) { char **e; unsigned int elen; unsigned int i; unsigned int j; unsigned int split; unsigned int t; if (!stralloc_cats(&plus,"")) return; elen = 0; for (i = 0;environ[i];++i) ++elen; for (i = 0;i < plus.len;++i) if (!plus.s[i]) ++elen; e = (char **) alloc((elen + 1) * sizeof(char *)); if (!e) return; elen = 0; for (i = 0;environ[i];++i) e[elen++] = environ[i]; j = 0; for (i = 0;i < plus.len;++i) if (!plus.s[i]) { split = str_chr(plus.s + j,'='); for (t = 0;t < elen;++t) if (byte_equal(plus.s + j,split,e[t])) if (e[t][split] == '=') { --elen; e[t] = e[elen]; break; } if (plus.s[j + split]) e[elen++] = plus.s + j; j = i + 1; } e[elen] = 0; pathexec_run(*argv,argv,e); alloc_free(e); } Hbun-0.1b2/alloc.h33_¸D33#ifndef ALLOC_H #define ALLOC_H extern /*@null@*//*@out@*/char *alloc(unsigned int); extern void alloc_free(void *); extern int alloc_re(void **, unsigned int, unsigned int); #endif Hbun-0.1b2/byte_diff.c34_ÁD34#include "byte.h" int byte_diff(register const char *s, unsigned int n, register const char *t) { for (;;) { if (!n) return 0; if (*s != *t) break; ++s; ++t; --n; if (!n) return 0; if (*s != *t) break; ++s; ++t; --n; if (!n) return 0; if (*s != *t) break; ++s; ++t; --n; if (!n) return 0; if (*s != *t) break; ++s; ++t; --n; } return ((int)(unsigned int)(unsigned char) *s) - ((int)(unsigned int)(unsigned char) *t); } Hbun-0.1b2/leapsecs_init.c35_«D35#include "leapsecs.h" static int flaginit = 0; int leapsecs_init(void) { if (flaginit) return 0; if (leapsecs_read() == -1) return -1; flaginit = 1; return 0; } Hbun-0.1b2/caltime_utc.c36_;D36#include "tai.h" #include "leapsecs.h" #include "caldate.h" #include "caltime.h" /* XXX: breaks tai encapsulation */ void caltime_utc(struct caltime *ct, struct tai *t, int *pwday, int *pyday) { struct tai t2 = *t; uint64 u; int leap; long s; /* XXX: check for overfow? */ leap = leapsecs_sub(&t2); u = t2.x; u += 58486; s = u % 86400ULL; ct->second = (s % 60) + leap; s /= 60; ct->minute = s % 60; s /= 60; ct->hour = s; u /= 86400ULL; caldate_frommjd(&ct->date,/*XXX*/(long) (u - 53375995543064ULL),pwday,pyday); ct->offset = 0; } Hbun-0.1b2/conf-libs37_5D37 The above libraries will be included when linking. Hbun-0.1b2/library-byte38_@D38byte_copy.o byte_cr.o byte_diff.o uint32_pack.o uint32_unpack.o Hbun-0.1b2/out_filter_mem.c39_ID39/* Public domain. */ #include #include "error.h" #include "out.h" #include "pathexec.h" int out_filter_mem(int out, const char *f, unsigned char *p, size_t size) { const char *arg[2]; int pip[2]; if (pipe(pip) < 0) return -1; switch (fork()) { case -1: return -1; case 0: close(pip[1]); close(0); if (dup(pip[0]) != 0) return -1; close (pip[0]); if (out != 1) { close(1); if (dup(out) != 1) return -1; close(out); } arg[0] = f; arg[1] = 0; pathexec(arg); return -1; default: close(pip[0]); return out_mem(pip[1], p, size); } } Hbun-0.1b2/sgetopt.h40_¿D40#ifndef SGETOPT_H #define SGETOPT_H #ifndef SGETOPTNOSHORT #define getopt sgetoptmine #define optarg subgetoptarg #define optind subgetoptind #define optpos subgetoptpos #define opterr sgetopterr #define optproblem subgetoptproblem #define optprogname sgetoptprogname #define opteof subgetoptdone #endif #include "subgetopt.h" extern int sgetoptmine(int,char **,const char *); extern int sgetopterr; extern const char *sgetoptprogname; #endif Hbun-0.1b2/conf-cc41_ÈD41gcc -O2 -Wall -Wshadow -Wpointer-arith -Wbad-function-cast -Wmissing-declarations -Wnested-externs -Wcast-qual -Wcast-align -Wwrite-strings The above command will be used to compile C source files. Hbun-0.1b2/strerr_sys.c42_ÄD42#include "error.h" #include "strerr.h" struct strerr strerr_sys; void strerr_sysinit(void) { strerr_sys.who = 0; strerr_sys.x = error_str(errno); strerr_sys.y = ""; strerr_sys.z = ""; } Hbun-0.1b2/warn-auto.sh43_=D43#! /bin/sh # WARNING! Automatically generated; do not edit. Hbun-0.1b2/blocksort.c44_QD44 /*-------------------------------------------------------------*/ /*--- Block sorting machinery ---*/ /*--- blocksort.c ---*/ /*-------------------------------------------------------------*/ /*-- This file is a part of bzip2 and/or libbzip2, a program and library for lossless, block-sorting data compression. Copyright (C) 1996-2002 Julian R Seward. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 3. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 4. The name of the author may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. Julian Seward, Cambridge, UK. jseward@acm.org bzip2/libbzip2 version 1.0 of 21 March 2000 This program is based on (at least) the work of: Mike Burrows David Wheeler Peter Fenwick Alistair Moffat Radford Neal Ian H. Witten Robert Sedgewick Jon L. Bentley For more information on these sources, see the manual. To get some idea how the block sorting algorithms in this file work, read my paper On the Performance of BWT Sorting Algorithms in Proceedings of the IEEE Data Compression Conference 2000, Snowbird, Utah, USA, 27-30 March 2000. The main sort in this file implements the algorithm called cache in the paper. --*/ #include "bzlib_private.h" /*---------------------------------------------*/ /*--- Fallback O(N log(N)^2) sorting ---*/ /*--- algorithm, for repetitive blocks ---*/ /*---------------------------------------------*/ /*---------------------------------------------*/ static __inline__ void fallbackSimpleSort ( UInt32* fmap, UInt32* eclass, Int32 lo, Int32 hi ) { Int32 i, j, tmp; UInt32 ec_tmp; if (lo == hi) return; if (hi - lo > 3) { for ( i = hi-4; i >= lo; i-- ) { tmp = fmap[i]; ec_tmp = eclass[tmp]; for ( j = i+4; j <= hi && ec_tmp > eclass[fmap[j]]; j += 4 ) fmap[j-4] = fmap[j]; fmap[j-4] = tmp; } } for ( i = hi-1; i >= lo; i-- ) { tmp = fmap[i]; ec_tmp = eclass[tmp]; for ( j = i+1; j <= hi && ec_tmp > eclass[fmap[j]]; j++ ) fmap[j-1] = fmap[j]; fmap[j-1] = tmp; } } /*---------------------------------------------*/ #define fswap(zz1, zz2) \ { Int32 zztmp = zz1; zz1 = zz2; zz2 = zztmp; } #define fvswap(zzp1, zzp2, zzn) \ { \ Int32 yyp1 = (zzp1); \ Int32 yyp2 = (zzp2); \ Int32 yyn = (zzn); \ while (yyn > 0) { \ fswap(fmap[yyp1], fmap[yyp2]); \ yyp1++; yyp2++; yyn--; \ } \ } #define fmin(a,b) ((a) < (b)) ? (a) : (b) #define fpush(lz,hz) { stackLo[sp] = lz; \ stackHi[sp] = hz; \ sp++; } #define fpop(lz,hz) { sp--; \ lz = stackLo[sp]; \ hz = stackHi[sp]; } #define FALLBACK_QSORT_SMALL_THRESH 10 #define FALLBACK_QSORT_STACK_SIZE 100 static void fallbackQSort3 ( UInt32* fmap, UInt32* eclass, Int32 loSt, Int32 hiSt ) { Int32 unLo, unHi, ltLo, gtHi, n, m; Int32 sp, lo, hi; UInt32 med, r, r3; Int32 stackLo[FALLBACK_QSORT_STACK_SIZE]; Int32 stackHi[FALLBACK_QSORT_STACK_SIZE]; r = 0; sp = 0; fpush ( loSt, hiSt ); while (sp > 0) { AssertH ( sp < FALLBACK_QSORT_STACK_SIZE, 1004 ); fpop ( lo, hi ); if (hi - lo < FALLBACK_QSORT_SMALL_THRESH) { fallbackSimpleSort ( fmap, eclass, lo, hi ); continue; } /* Random partitioning. Median of 3 sometimes fails to avoid bad cases. Median of 9 seems to help but looks rather expensive. This too seems to work but is cheaper. Guidance for the magic constants 7621 and 32768 is taken from Sedgewick's algorithms book, chapter 35. */ r = ((r * 7621) + 1) % 32768; r3 = r % 3; if (r3 == 0) med = eclass[fmap[lo]]; else if (r3 == 1) med = eclass[fmap[(lo+hi)>>1]]; else med = eclass[fmap[hi]]; unLo = ltLo = lo; unHi = gtHi = hi; while (1) { while (1) { if (unLo > unHi) break; n = (Int32)eclass[fmap[unLo]] - (Int32)med; if (n == 0) { fswap(fmap[unLo], fmap[ltLo]); ltLo++; unLo++; continue; }; if (n > 0) break; unLo++; } while (1) { if (unLo > unHi) break; n = (Int32)eclass[fmap[unHi]] - (Int32)med; if (n == 0) { fswap(fmap[unHi], fmap[gtHi]); gtHi--; unHi--; continue; }; if (n < 0) break; unHi--; } if (unLo > unHi) break; fswap(fmap[unLo], fmap[unHi]); unLo++; unHi--; } AssertD ( unHi == unLo-1, "fallbackQSort3(2)" ); if (gtHi < ltLo) continue; n = fmin(ltLo-lo, unLo-ltLo); fvswap(lo, unLo-n, n); m = fmin(hi-gtHi, gtHi-unHi); fvswap(unLo, hi-m+1, m); n = lo + unLo - ltLo - 1; m = hi - (gtHi - unHi) + 1; if (n - lo > hi - m) { fpush ( lo, n ); fpush ( m, hi ); } else { fpush ( m, hi ); fpush ( lo, n ); } } } #undef fmin #undef fpush #undef fpop #undef fswap #undef fvswap #undef FALLBACK_QSORT_SMALL_THRESH #undef FALLBACK_QSORT_STACK_SIZE /*---------------------------------------------*/ /* Pre: nblock > 0 eclass exists for [0 .. nblock-1] ((UChar*)eclass) [0 .. nblock-1] holds block ptr exists for [0 .. nblock-1] Post: ((UChar*)eclass) [0 .. nblock-1] holds block All other areas of eclass destroyed fmap [0 .. nblock-1] holds sorted order bhtab [ 0 .. 2+(nblock/32) ] destroyed */ #define SET_BH(zz) bhtab[(zz) >> 5] |= (1 << ((zz) & 31)) #define CLEAR_BH(zz) bhtab[(zz) >> 5] &= ~(1 << ((zz) & 31)) #define ISSET_BH(zz) (bhtab[(zz) >> 5] & (1 << ((zz) & 31))) #define WORD_BH(zz) bhtab[(zz) >> 5] #define UNALIGNED_BH(zz) ((zz) & 0x01f) static void fallbackSort ( UInt32* fmap, UInt32* eclass, UInt32* bhtab, Int32 nblock, Int32 verb ) { Int32 ftab[257]; Int32 ftabCopy[256]; Int32 H, i, j, k, l, r, cc, cc1; Int32 nNotDone; Int32 nBhtab; UChar* eclass8 = (UChar*)eclass; /*-- Initial 1-char radix sort to generate initial fmap and initial BH bits. --*/ if (verb >= 4) VPrintf0 ( " bucket sorting ...\n" ); for (i = 0; i < 257; i++) ftab[i] = 0; for (i = 0; i < nblock; i++) ftab[eclass8[i]]++; for (i = 0; i < 256; i++) ftabCopy[i] = ftab[i]; for (i = 1; i < 257; i++) ftab[i] += ftab[i-1]; for (i = 0; i < nblock; i++) { j = eclass8[i]; k = ftab[j] - 1; ftab[j] = k; fmap[k] = i; } nBhtab = 2 + (nblock / 32); for (i = 0; i < nBhtab; i++) bhtab[i] = 0; for (i = 0; i < 256; i++) SET_BH(ftab[i]); /*-- Inductively refine the buckets. Kind-of an "exponential radix sort" (!), inspired by the Manber-Myers suffix array construction algorithm. --*/ /*-- set sentinel bits for block-end detection --*/ for (i = 0; i < 32; i++) { SET_BH(nblock + 2*i); CLEAR_BH(nblock + 2*i + 1); } /*-- the log(N) loop --*/ H = 1; while (1) { if (verb >= 4) VPrintf1 ( " depth %6d has ", H ); j = 0; for (i =