Lines Matching +full:len +full:- +full:or +full:- +full:limit
20 the Burrows-Wheeler transformation. Much of that time is delay
25 non-profit hospice organization in the name of the woman I loved, who
32 Lafayette, LA 70503-3240
34 Phone (337) 232-1234 or 1-800-738-2226
35 Fax (337) 232-1297
70 #define RETVAL_LAST_BLOCK (-1)
71 #define RETVAL_NOT_BZIP_DATA (-2)
72 #define RETVAL_UNEXPECTED_INPUT_EOF (-3)
73 #define RETVAL_UNEXPECTED_OUTPUT_EOF (-4)
74 #define RETVAL_DATA_ERROR (-5)
75 #define RETVAL_OUT_OF_MEMORY (-6)
76 #define RETVAL_OBSOLETE_INPUT (-7)
83 /* We have an extra slot at the end of limit[] for a sentinel value. */
84 int limit[MAX_HUFCODE_BITS+1]; member
108 int io_error; /* non-zero if we have IO error */
123 while (bd->inbufBitCount < bits_wanted) { in get_bits()
126 if (bd->inbufPos == bd->inbufCount) { in get_bits()
127 if (bd->io_error) in get_bits()
129 bd->inbufCount = bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE); in get_bits()
130 if (bd->inbufCount <= 0) { in get_bits()
131 bd->io_error = RETVAL_UNEXPECTED_INPUT_EOF; in get_bits()
134 bd->inbufPos = 0; in get_bits()
136 /* Avoid 32-bit overflow (dump bit buffer to top of output) */ in get_bits()
137 if (bd->inbufBitCount >= 24) { in get_bits()
138 bits = bd->inbufBits&((1 << bd->inbufBitCount)-1); in get_bits()
139 bits_wanted -= bd->inbufBitCount; in get_bits()
141 bd->inbufBitCount = 0; in get_bits()
144 bd->inbufBits = (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++]; in get_bits()
145 bd->inbufBitCount += 8; in get_bits()
148 bd->inbufBitCount -= bits_wanted; in get_bits()
149 bits |= (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-1); in get_bits()
154 /* Unpacks the next block and sets up for the inverse burrows-wheeler step. */
160 int *limit = NULL; in get_next_block() local
166 dbuf = bd->dbuf; in get_next_block()
167 dbufSize = bd->dbufSize; in get_next_block()
168 selectors = bd->selectors; in get_next_block()
169 byteCount = bd->byteCount; in get_next_block()
170 symToByte = bd->symToByte; in get_next_block()
171 mtfSymbol = bd->mtfSymbol; in get_next_block()
177 bd->headerCRC = get_bits(bd, 32); in get_next_block()
183 There was some code for this in busybox 1.0.0-pre3, but nobody ever in get_next_block()
198 if (t&(1 << (15-i))) { in get_next_block()
201 if (k&(1 << (15-j))) in get_next_block()
226 for (; j; j--) in get_next_block()
227 mtfSymbol[j] = mtfSymbol[j-1]; in get_next_block()
247 t = get_bits(bd, 5)-1; in get_next_block()
250 if (((unsigned)t) > (MAX_HUFCODE_BITS-1)) in get_next_block()
255 increment or decrement the value. in get_next_block()
261 bd->inbufBitCount++; in get_next_block()
266 t += (((k+1)&2)-1); in get_next_block()
268 /* Correct for the initial -1, to get the in get_next_block()
282 /* Calculate permute[], base[], and limit[] tables from in get_next_block()
291 * limit[] indicates the largest numerical value a in get_next_block()
294 * code with a value > limit[length] needs another in get_next_block()
297 hufGroup = bd->groups+j; in get_next_block()
298 hufGroup->minLen = minLen; in get_next_block()
299 hufGroup->maxLen = maxLen; in get_next_block()
301 adjust the base and limit array pointers so we're in get_next_block()
304 base = hufGroup->base-1; in get_next_block()
305 limit = hufGroup->limit-1; in get_next_block()
307 * temp[] and limit[]. */ in get_next_block()
310 temp[i] = limit[i] = 0; in get_next_block()
313 hufGroup->permute[pp++] = t; in get_next_block()
318 /* Calculate limit[] (the largest symbol-coding value in get_next_block()
319 *at each bit length, which is (previous limit << in get_next_block()
321 *symbols to ignore at each bit length, which is limit in get_next_block()
334 to-be-ignored bits to 1 so they don't in get_next_block()
335 affect the value > limit[length] in get_next_block()
337 limit[i] = (pp << (maxLen - i)) - 1; in get_next_block()
339 base[i+1] = pp-(t += temp[i]); in get_next_block()
341 limit[maxLen+1] = INT_MAX; /* Sentinel value for in get_next_block()
343 limit[maxLen] = pp+temp[maxLen]-1; in get_next_block()
361 if (!(symCount--)) { in get_next_block()
362 symCount = GROUP_SIZE-1; in get_next_block()
365 hufGroup = bd->groups+selectors[selector++]; in get_next_block()
366 base = hufGroup->base-1; in get_next_block()
367 limit = hufGroup->limit-1; in get_next_block()
369 /* Read next Huffman-coded symbol. */ in get_next_block()
379 equivalent to j = get_bits(bd, hufGroup->maxLen); in get_next_block()
381 while (bd->inbufBitCount < hufGroup->maxLen) { in get_next_block()
382 if (bd->inbufPos == bd->inbufCount) { in get_next_block()
383 j = get_bits(bd, hufGroup->maxLen); in get_next_block()
386 bd->inbufBits = in get_next_block()
387 (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++]; in get_next_block()
388 bd->inbufBitCount += 8; in get_next_block()
390 bd->inbufBitCount -= hufGroup->maxLen; in get_next_block()
391 j = (bd->inbufBits >> bd->inbufBitCount)& in get_next_block()
392 ((1 << hufGroup->maxLen)-1); in get_next_block()
396 i = hufGroup->minLen; in get_next_block()
397 while (j > limit[i]) in get_next_block()
399 bd->inbufBitCount += (hufGroup->maxLen - i); in get_next_block()
401 if ((i > hufGroup->maxLen) in get_next_block()
402 || (((unsigned)(j = (j>>(hufGroup->maxLen-i))-base[i])) in get_next_block()
405 nextSym = hufGroup->permute[j]; in get_next_block()
407 either a new literal byte, or a repeated run of the in get_next_block()
411 if (((unsigned)nextSym) <= SYMBOL_RUNB) { /* RUNA or RUNB */ in get_next_block()
419 or-ing 0 or 1 at each bit position, add 1 in get_next_block()
420 or 2 instead. For example, 1011 is 1 << 0 in get_next_block()
424 or 0/1 method (except all bits 0, which in get_next_block()
434 /* When we hit the first non-run symbol after a run, in get_next_block()
447 while (t--) in get_next_block()
456 found. (Note that the result can't be -1 or 0, in get_next_block()
461 non-literal nextSym values equals -1.) */ in get_next_block()
464 i = nextSym - 1; in get_next_block()
472 mtfSymbol[i] = mtfSymbol[i-1]; in get_next_block()
473 } while (--i); in get_next_block()
480 /* At this point, we've read all the Huffman-coded symbols in get_next_block()
484 Burrows-Wheeler transform on dbuf. See in get_next_block()
487 /* Turn byteCount into cumulative occurrence counts of 0 to n-1. */ in get_next_block()
507 bd->writePos = dbuf[origPtr]; in get_next_block()
508 bd->writeCurrent = (unsigned char)(bd->writePos&0xff); in get_next_block()
509 bd->writePos >>= 8; in get_next_block()
510 bd->writeRunCountdown = 5; in get_next_block()
512 bd->writeCount = dbufCount; in get_next_block()
517 /* Undo burrows-wheeler transform on intermediate buffer to produce output.
518 If start_bunzip was initialized with out_fd =-1, then up to len bytes of
519 data are written to outbuf. Return value is number of bytes written or
520 error (all errors are negative numbers). If out_fd!=-1, outbuf and len
521 are ignored, data is written to out_fd and return is RETVAL_OK or error.
524 static int INIT read_bunzip(struct bunzip_data *bd, char *outbuf, int len) in read_bunzip() argument
530 if (bd->writeCount < 0) in read_bunzip()
531 return bd->writeCount; in read_bunzip()
534 dbuf = bd->dbuf; in read_bunzip()
535 pos = bd->writePos; in read_bunzip()
536 xcurrent = bd->writeCurrent; in read_bunzip()
540 Huffman-decoded a block into the intermediate buffer yet). */ in read_bunzip()
542 if (bd->writeCopies) { in read_bunzip()
544 --bd->writeCopies; in read_bunzip()
549 if (gotcount >= len) { in read_bunzip()
550 bd->writePos = pos; in read_bunzip()
551 bd->writeCurrent = xcurrent; in read_bunzip()
552 bd->writeCopies++; in read_bunzip()
553 return len; in read_bunzip()
557 bd->writeCRC = (((bd->writeCRC) << 8) in read_bunzip()
558 ^bd->crc32Table[((bd->writeCRC) >> 24) in read_bunzip()
562 if (bd->writeCopies) { in read_bunzip()
563 --bd->writeCopies; in read_bunzip()
567 if (!bd->writeCount--) in read_bunzip()
570 * Burrows-Wheeler transform */ in read_bunzip()
578 testing for non-zero is faster */ in read_bunzip()
579 if (--bd->writeRunCountdown) { in read_bunzip()
581 bd->writeRunCountdown = 4; in read_bunzip()
585 bd->writeCopies = xcurrent; in read_bunzip()
587 bd->writeRunCountdown = 5; in read_bunzip()
590 if (!bd->writeCopies) in read_bunzip()
594 --bd->writeCopies; in read_bunzip()
598 bd->writeCRC = ~bd->writeCRC; in read_bunzip()
599 bd->totalCRC = ((bd->totalCRC << 1) | in read_bunzip()
600 (bd->totalCRC >> 31)) ^ bd->writeCRC; in read_bunzip()
602 if (bd->writeCRC != bd->headerCRC) { in read_bunzip()
603 bd->totalCRC = bd->headerCRC+1; in read_bunzip()
608 /* Refill the intermediate buffer by Huffman-decoding next in read_bunzip()
613 bd->writeCount = previous; in read_bunzip()
616 bd->writeCRC = 0xffffffffUL; in read_bunzip()
617 pos = bd->writePos; in read_bunzip()
618 xcurrent = bd->writeCurrent; in read_bunzip()
622 static long INIT nofill(void *buf, unsigned long len) in nofill() argument
624 return -1; in nofill()
627 /* Allocate the structure, read file header. If in_fd ==-1, inbuf must contain
628 a complete bunzip file (len bytes long). If in_fd!=-1, inbuf and len are
630 static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, long len, in start_bunzip() argument
648 bd->inbuf = inbuf; in start_bunzip()
649 bd->inbufCount = len; in start_bunzip()
651 bd->fill = fill; in start_bunzip()
653 bd->fill = nofill; in start_bunzip()
658 for (j = 8; j; j--) in start_bunzip()
660 bd->crc32Table[i] = c; in start_bunzip()
663 /* Ensure that file starts with "BZh['1'-'9']." */ in start_bunzip()
665 if (((unsigned int)(i-BZh0-1)) >= 9) in start_bunzip()
668 /* Fourth byte (ascii '1'-'9'), indicates block size in units of 100k of in start_bunzip()
670 bd->dbufSize = 100000*(i-BZh0); in start_bunzip()
672 bd->dbuf = large_malloc(bd->dbufSize * sizeof(int)); in start_bunzip()
673 if (!bd->dbuf) in start_bunzip()
680 STATIC int INIT bunzip2(unsigned char *buf, long len, in bunzip2() argument
688 int i = -1; in bunzip2()
707 i = start_bunzip(&bd, inbuf, len, fill); in bunzip2()
724 if (bd->headerCRC != bd->totalCRC) in bunzip2()
733 if (bd->dbuf) in bunzip2()
734 large_free(bd->dbuf); in bunzip2()
736 *pos = bd->inbufPos; in bunzip2()
748 STATIC int INIT __decompress(unsigned char *buf, long len, in __decompress() argument
755 return bunzip2(buf, len - 4, fill, flush, outbuf, pos, error); in __decompress()