From: "Jan Beulich" Subject: [PATCH] x86/dom0: support bzip2 and lzma compressed bzImage payloads Date: Thu, 05 Nov 2009 14:24:54 +0000 Message-ID: <4AF2EE46020000780001DCDF@vpn.id2.novell.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=__Part163DA326.0__=" Return-path: List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xensource.com Errors-To: xen-devel-bounces@lists.xensource.com To: xen-devel@lists.xensource.com List-Id: xen-devel@lists.xenproject.org This is a MIME message. If you are reading this text, you may want to consider changing to a mail reader or gateway that understands how to properly handle MIME multipart messages. --=__Part163DA326.0__= Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable Content-Disposition: inline This matches functionality in the tools already supporting the same for DomU-s. Code taken from Linux 2.6.32-rc and adjusted as little as possible to be usable in Xen. The question is whether, particularly for non-Linux Dom0-s, plain ELF images compressed by bzip2 or lzma should also be supported. Signed-off-by: Jan Beulich --- 2009-10-27.orig/xen/arch/x86/bzimage.c 2009-10-07 13:31:36.0000000= 00 +0200 +++ 2009-10-27/xen/arch/x86/bzimage.c 2009-11-05 12:23:05.000000000 = +0100 @@ -4,6 +4,7 @@ #include #include #include +#include #include =20 #define HEAPORDER 3 @@ -93,28 +94,38 @@ static __init void flush_window(void) outcnt =3D 0; } =20 -static __init int gzip_length(char *image, unsigned long image_len) +static __init unsigned long output_length(char *image, unsigned long = image_len) { return *(uint32_t *)&image[image_len - 4]; } =20 -static __init int perform_gunzip(char *output, char **_image_start, = unsigned long *image_len) +static __init int gzip_check(char *image, unsigned long image_len) { - char *image =3D *_image_start; - int rc; - unsigned char magic0 =3D (unsigned char)image[0]; - unsigned char magic1 =3D (unsigned char)image[1]; + unsigned char magic0, magic1; =20 - if ( magic0 !=3D 0x1f || ( (magic1 !=3D 0x8b) && (magic1 !=3D 0x9e) ) = ) + if ( image_len < 2 ) return 0; =20 + magic0 =3D (unsigned char)image[0]; + magic1 =3D (unsigned char)image[1]; + + return (magic0 =3D=3D 0x1f) && ((magic1 =3D=3D 0x8b) || (magic1 = =3D=3D 0x9e)); +} + +static __init int perform_gunzip(char *output, char *image, unsigned long = image_len) +{ + int rc; + + if ( !gzip_check(image, image_len) ) + return 1; + window =3D (unsigned char *)output; =20 free_mem_ptr =3D (unsigned long)alloc_xenheap_pages(HEAPORDER, 0); free_mem_end_ptr =3D free_mem_ptr + (PAGE_SIZE << HEAPORDER); =20 inbuf =3D (unsigned char *)image; - insize =3D *image_len; + insize =3D image_len; inptr =3D 0; =20 makecrc(); @@ -125,8 +136,6 @@ static __init int perform_gunzip(char * } else { - *_image_start =3D (char *)window; - *image_len =3D gzip_length(image, *image_len); rc =3D 0; } =20 @@ -203,9 +212,12 @@ int __init bzimage_headroom(char *image_ img =3D image_start + (hdr->setup_sects+1) * 512; img +=3D hdr->payload_offset; =20 - headroom =3D gzip_length(img, hdr->payload_length); - headroom +=3D headroom >> 12; /* Add 8 bytes for every 32K input = block */ - headroom +=3D (32768 + 18); /* Add 32K + 18 bytes of extra headroom = */ + headroom =3D output_length(img, hdr->payload_length); + if (gzip_check(img, hdr->payload_length)) { + headroom +=3D headroom >> 12; /* Add 8 bytes for every 32K input = block */ + headroom +=3D (32768 + 18); /* Add 32K + 18 bytes of extra = headroom */ + } else + headroom +=3D hdr->payload_length; headroom =3D (headroom + 4095) & ~4095; =20 return headroom; @@ -215,6 +227,7 @@ int __init bzimage_parse(char *image_bas { struct setup_header *hdr =3D (struct setup_header *)(*image_start); int err =3D bzimage_check(hdr, *image_len); + unsigned long output_len; =20 if (err < 1) return err; @@ -224,11 +237,18 @@ int __init bzimage_parse(char *image_bas *image_start +=3D (hdr->setup_sects+1) * 512; *image_start +=3D hdr->payload_offset; *image_len =3D hdr->payload_length; + output_len =3D output_length(*image_start, *image_len); =20 - if ( (err =3D perform_gunzip(image_base, image_start, image_len)) < 0 = ) - return err; + if ( (err =3D perform_gunzip(image_base, *image_start, *image_len)) > = 0 ) + err =3D decompress(*image_start, *image_len, image_base); + + if ( !err ) + { + *image_start =3D image_base; + *image_len =3D output_len; + } =20 - return 0; + return err > 0 ? 0 : err; } =20 /* --- 2009-10-27.orig/xen/common/Makefile 2009-05-27 13:54:07.000000000 = +0200 +++ 2009-10-27/xen/common/Makefile 2009-11-05 12:26:53.000000000 = +0100 @@ -35,6 +35,8 @@ obj-y +=3D radix-tree.o obj-y +=3D rbtree.o obj-y +=3D lzo.o =20 +obj-$(CONFIG_X86) +=3D decompress.o bunzip2.o unlzma.o + obj-$(perfc) +=3D perfc.o obj-$(crash_debug) +=3D gdbstub.o obj-$(xenoprof) +=3D xenoprof.o --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ 2009-10-27/xen/common/bunzip2.c 2009-11-05 12:44:51.000000000 = +0100 @@ -0,0 +1,726 @@ +/* vi: set sw =3D 4 ts =3D 4: */ +/* Small bzip2 deflate implementation, by Rob Landley (rob@landley.net= ). + + Based on bzip2 decompression code by Julian R Seward (jseward@acm.o= rg), + which also acknowledges contributions by Mike Burrows, David = Wheeler, + Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten, + Robert Sedgewick, and Jon L. Bentley. + + This code is licensed under the LGPLv2: + LGPL (http://www.gnu.org/copyleft/lgpl.html=20 +*/ + +/* + Size and speed optimizations by Manuel Novoa III (mjn3@codepoet.or= g). + + More efficient reading of Huffman codes, a streamlined read_bunzip(= ) + function, and various other tweaks. In (limited) tests, approximat= ely + 20% faster than bzcat on x86 and about 10% faster on arm. + + Note that about 2/3 of the time is spent in read_unzip() reversing + the Burrows-Wheeler transformation. Much of that time is delay + resulting from cache misses. + + I would ask that anyone benefiting from this work, especially = those + using it in commercial products, consider making a donation to my = local + non-profit hospice organization in the name of the woman I loved, = who + passed away Feb. 12, 2003. + + In memory of Toni W. Hagan + + Hospice of Acadiana, Inc. + 2600 Johnston St., Suite 200 + Lafayette, LA 70503-3240 + + Phone (337) 232-1234 or 1-800-738-2226 + Fax (337) 232-1297 + + http://www.hospiceacadiana.com/=20 + + Manuel + */ + +/* + Made it fit for running in Linux Kernel by Alain Knaff (alain@knaff= .lu) +*/ + +#include "decompress.h" + +#ifndef INT_MAX +#define INT_MAX 0x7fffffff +#endif + +/* Constants for Huffman coding */ +#define MAX_GROUPS 6 +#define GROUP_SIZE 50 /* 64 would have been more = efficient */ +#define MAX_HUFCODE_BITS 20 /* Longest Huffman code allowed */ +#define MAX_SYMBOLS 258 /* 256 literals + RUNA + RUNB */ +#define SYMBOL_RUNA 0 +#define SYMBOL_RUNB 1 + +/* Status return values */ +#define RETVAL_OK 0 +#define RETVAL_LAST_BLOCK (-1) +#define RETVAL_NOT_BZIP_DATA (-2) +#define RETVAL_UNEXPECTED_INPUT_EOF (-3) +#define RETVAL_UNEXPECTED_OUTPUT_EOF (-4) +#define RETVAL_DATA_ERROR (-5) +#define RETVAL_OUT_OF_MEMORY (-6) +#define RETVAL_OBSOLETE_INPUT (-7) + +/* Other housekeeping constants */ +#define BZIP2_IOBUF_SIZE 4096 + +/* This is what we know about each Huffman coding group */ +struct group_data { + /* We have an extra slot at the end of limit[] for a sentinal = value. */ + int limit[MAX_HUFCODE_BITS+1]; + int base[MAX_HUFCODE_BITS]; + int permute[MAX_SYMBOLS]; + int minLen, maxLen; +}; + +/* Structure holding all the housekeeping data, including IO buffers and + memory that persists between calls to bunzip */ +struct bunzip_data { + /* State for interrupting output loop */ + int writeCopies, writePos, writeRunCountdown, writeCount, = writeCurrent; + /* I/O tracking data (file handles, buffers, positions, etc.) */ + int (*fill)(void*, unsigned int); + int inbufCount, inbufPos /*, outbufPos*/; + unsigned char *inbuf /*,*outbuf*/; + unsigned int inbufBitCount, inbufBits; + /* The CRC values stored in the block header and calculated from = the + data */ + unsigned int crc32Table[256], headerCRC, totalCRC, writeCRC; + /* Intermediate buffer and its size (in bytes) */ + unsigned int *dbuf, dbufSize; + /* These things are a bit too big to go on the stack */ + unsigned char selectors[32768]; /* nSelectors =3D 15 bits = */ + struct group_data groups[MAX_GROUPS]; /* Huffman coding tables = */ + int io_error; /* non-zero if we have IO error */ +}; + + +/* Return the next nnn bits of input. All reads from the compressed = input + are done through this function. All reads are big endian */ +static unsigned int INIT get_bits(struct bunzip_data *bd, char bits_wanted= ) +{ + unsigned int bits =3D 0; + + /* If we need to get more data from the byte buffer, do so. + (Loop getting one byte at a time to enforce endianness and = avoid + unaligned access.) */ + while (bd->inbufBitCount < bits_wanted) { + /* If we need to read more data from file into byte = buffer, do + so */ + if (bd->inbufPos =3D=3D bd->inbufCount) { + if (bd->io_error) + return 0; + bd->inbufCount =3D bd->fill(bd->inbuf, BZIP2_IOBUF_= SIZE); + if (bd->inbufCount <=3D 0) { + bd->io_error =3D RETVAL_UNEXPECTED_INPUT_EO= F; + return 0; + } + bd->inbufPos =3D 0; + } + /* Avoid 32-bit overflow (dump bit buffer to top of = output) */ + if (bd->inbufBitCount >=3D 24) { + bits =3D bd->inbufBits&((1 << bd->inbufBitCount)-1)= ; + bits_wanted -=3D bd->inbufBitCount; + bits <<=3D bits_wanted; + bd->inbufBitCount =3D 0; + } + /* Grab next 8 bits of input from buffer. */ + bd->inbufBits =3D (bd->inbufBits << 8)|bd->inbuf[bd->inbufP= os++]; + bd->inbufBitCount +=3D 8; + } + /* Calculate result */ + bd->inbufBitCount -=3D bits_wanted; + bits |=3D (bd->inbufBits >> bd->inbufBitCount)&((1 << bits_wanted)-= 1); + + return bits; +} + +/* Unpacks the next block and sets up for the inverse burrows-wheeler = step. */ + +static int INIT get_next_block(struct bunzip_data *bd) +{ + struct group_data *hufGroup =3D NULL; + int *base =3D NULL; + int *limit =3D NULL; + int dbufCount, nextSym, dbufSize, groupCount, selector, + i, j, k, t, runPos, symCount, symTotal, nSelectors, + byteCount[256]; + unsigned char uc, symToByte[256], mtfSymbol[256], *selectors; + unsigned int *dbuf, origPtr; + + dbuf =3D bd->dbuf; + dbufSize =3D bd->dbufSize; + selectors =3D bd->selectors; + + /* Read in header signature and CRC, then validate signature. + (last block signature means CRC is for whole file, return now) = */ + i =3D get_bits(bd, 24); + j =3D get_bits(bd, 24); + bd->headerCRC =3D get_bits(bd, 32); + if ((i =3D=3D 0x177245) && (j =3D=3D 0x385090)) + return RETVAL_LAST_BLOCK; + if ((i !=3D 0x314159) || (j !=3D 0x265359)) + return RETVAL_NOT_BZIP_DATA; + /* We can add support for blockRandomised if anybody complains. + There was some code for this in busybox 1.0.0-pre3, but nobody = ever + noticed that it didn't actually work. */ + if (get_bits(bd, 1)) + return RETVAL_OBSOLETE_INPUT; + origPtr =3D get_bits(bd, 24); + if (origPtr > dbufSize) + return RETVAL_DATA_ERROR; + /* mapping table: if some byte values are never used (encoding = things + like ascii text), the compression code removes the gaps to have = fewer + symbols to deal with, and writes a sparse bitfield indicating = which + values were present. We make a translation table to convert = the + symbols back to the corresponding bytes. */ + t =3D get_bits(bd, 16); + symTotal =3D 0; + for (i =3D 0; i < 16; i++) { + if (t&(1 << (15-i))) { + k =3D get_bits(bd, 16); + for (j =3D 0; j < 16; j++) + if (k&(1 << (15-j))) + symToByte[symTotal++] =3D = (16*i)+j; + } + } + /* How many different Huffman coding groups does this block use? = */ + groupCount =3D get_bits(bd, 3); + if (groupCount < 2 || groupCount > MAX_GROUPS) + return RETVAL_DATA_ERROR; + /* nSelectors: Every GROUP_SIZE many symbols we select a new + Huffman coding group. Read in the group selector list, + which is stored as MTF encoded bit runs. (MTF =3D Move To + Front, as each value is used it's moved to the start of the + list.) */ + nSelectors =3D get_bits(bd, 15); + if (!nSelectors) + return RETVAL_DATA_ERROR; + for (i =3D 0; i < groupCount; i++) + mtfSymbol[i] =3D i; + for (i =3D 0; i < nSelectors; i++) { + /* Get next value */ + for (j =3D 0; get_bits(bd, 1); j++) + if (j >=3D groupCount) + return RETVAL_DATA_ERROR; + /* Decode MTF to get the next selector */ + uc =3D mtfSymbol[j]; + for (; j; j--) + mtfSymbol[j] =3D mtfSymbol[j-1]; + mtfSymbol[0] =3D selectors[i] =3D uc; + } + /* Read the Huffman coding tables for each group, which code + for symTotal literal symbols, plus two run symbols (RUNA, + RUNB) */ + symCount =3D symTotal+2; + for (j =3D 0; j < groupCount; j++) { + unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1]= ; + int minLen, maxLen, pp; + /* Read Huffman code lengths for each symbol. They're + stored in a way similar to mtf; record a starting + value for the first symbol, and an offset from the + previous value for everys symbol after that. + (Subtracting 1 before the loop and then adding it + back at the end is an optimization that makes the + test inside the loop simpler: symbol length 0 + becomes negative, so an unsigned inequality catches + it.) */ + t =3D get_bits(bd, 5)-1; + for (i =3D 0; i < symCount; i++) { + for (;;) { + if (((unsigned)t) > (MAX_HUFCODE_BITS-1)) + return RETVAL_DATA_ERROR; + + /* If first bit is 0, stop. Else + second bit indicates whether to + increment or decrement the value. + Optimization: grab 2 bits and unget + the second if the first was 0. */ + + k =3D get_bits(bd, 2); + if (k < 2) { + bd->inbufBitCount++; + break; + } + /* Add one if second bit 1, else + * subtract 1. Avoids if/else */ + t +=3D (((k+1)&2)-1); + } + /* Correct for the initial -1, to get the + * final symbol length */ + length[i] =3D t+1; + } + /* Find largest and smallest lengths in this group */ + minLen =3D maxLen =3D length[0]; + + for (i =3D 1; i < symCount; i++) { + if (length[i] > maxLen) + maxLen =3D length[i]; + else if (length[i] < minLen) + minLen =3D length[i]; + } + + /* Calculate permute[], base[], and limit[] tables from + * length[]. + * + * permute[] is the lookup table for converting + * Huffman coded symbols into decoded symbols. base[] + * is the amount to subtract from the value of a + * Huffman symbol of a given length when using + * permute[]. + * + * limit[] indicates the largest numerical value a + * symbol with a given number of bits can have. This + * is how the Huffman codes can vary in length: each + * code with a value > limit[length] needs another + * bit. + */ + hufGroup =3D bd->groups+j; + hufGroup->minLen =3D minLen; + hufGroup->maxLen =3D maxLen; + /* Note that minLen can't be smaller than 1, so we + adjust the base and limit array pointers so we're + not always wasting the first entry. We do this + again when using them (during symbol decoding).*/ + base =3D hufGroup->base-1; + limit =3D hufGroup->limit-1; + /* Calculate permute[]. Concurently, initialize + * temp[] and limit[]. */ + pp =3D 0; + for (i =3D minLen; i <=3D maxLen; i++) { + temp[i] =3D limit[i] =3D 0; + for (t =3D 0; t < symCount; t++) + if (length[t] =3D=3D i) + hufGroup->permute[pp++] =3D t; + } + /* Count symbols coded for at each bit length */ + for (i =3D 0; i < symCount; i++) + temp[length[i]]++; + /* Calculate limit[] (the largest symbol-coding value + *at each bit length, which is (previous limit << + *1)+symbols at this level), and base[] (number of + *symbols to ignore at each bit length, which is limit + *minus the cumulative count of symbols coded for + *already). */ + pp =3D t =3D 0; + for (i =3D minLen; i < maxLen; i++) { + pp +=3D temp[i]; + /* We read the largest possible symbol size + and then unget bits after determining how + many we need, and those extra bits could be + set to anything. (They're noise from + future symbols.) At each level we're + really only interested in the first few + bits, so here we set all the trailing + to-be-ignored bits to 1 so they don't + affect the value > limit[length] + comparison. */ + limit[i] =3D (pp << (maxLen - i)) - 1; + pp <<=3D 1; + base[i+1] =3D pp-(t +=3D temp[i]); + } + limit[maxLen+1] =3D INT_MAX; /* Sentinal value for + * reading next sym. */ + limit[maxLen] =3D pp+temp[maxLen]-1; + base[minLen] =3D 0; + } + /* We've finished reading and digesting the block header. Now + read this block's Huffman coded symbols from the file and + undo the Huffman coding and run length encoding, saving the + result into dbuf[dbufCount++] =3D uc */ + + /* Initialize symbol occurrence counters and symbol Move To + * Front table */ + for (i =3D 0; i < 256; i++) { + byteCount[i] =3D 0; + mtfSymbol[i] =3D (unsigned char)i; + } + /* Loop through compressed symbols. */ + runPos =3D dbufCount =3D symCount =3D selector =3D 0; + for (;;) { + /* Determine which Huffman coding group to use. */ + if (!(symCount--)) { + symCount =3D GROUP_SIZE-1; + if (selector >=3D nSelectors) + return RETVAL_DATA_ERROR; + hufGroup =3D bd->groups+selectors[selector++]; + base =3D hufGroup->base-1; + limit =3D hufGroup->limit-1; + } + /* Read next Huffman-coded symbol. */ + /* Note: It is far cheaper to read maxLen bits and + back up than it is to read minLen bits and then an + additional bit at a time, testing as we go. + Because there is a trailing last block (with file + CRC), there is no danger of the overread causing an + unexpected EOF for a valid compressed file. As a + further optimization, we do the read inline + (falling back to a call to get_bits if the buffer + runs dry). The following (up to got_huff_bits:) is + equivalent to j =3D get_bits(bd, hufGroup->maxLen); + */ + while (bd->inbufBitCount < hufGroup->maxLen) { + if (bd->inbufPos =3D=3D bd->inbufCount) { + j =3D get_bits(bd, hufGroup->maxLen); + goto got_huff_bits; + } + bd->inbufBits =3D + (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos= ++]; + bd->inbufBitCount +=3D 8; + }; + bd->inbufBitCount -=3D hufGroup->maxLen; + j =3D (bd->inbufBits >> bd->inbufBitCount)& + ((1 << hufGroup->maxLen)-1); +got_huff_bits: + /* Figure how how many bits are in next symbol and + * unget extras */ + i =3D hufGroup->minLen; + while (j > limit[i]) + ++i; + bd->inbufBitCount +=3D (hufGroup->maxLen - i); + /* Huffman decode value to get nextSym (with bounds = checking) */ + if ((i > hufGroup->maxLen) + || (((unsigned)(j =3D (j>>(hufGroup->maxLen-i))-bas= e[i])) + >=3D MAX_SYMBOLS)) + return RETVAL_DATA_ERROR; + nextSym =3D hufGroup->permute[j]; + /* We have now decoded the symbol, which indicates + either a new literal byte, or a repeated run of the + most recent literal byte. First, check if nextSym + indicates a repeated run, and if so loop collecting + how many times to repeat the last literal. */ + if (((unsigned)nextSym) <=3D SYMBOL_RUNB) { /* RUNA or = RUNB */ + /* If this is the start of a new run, zero out + * counter */ + if (!runPos) { + runPos =3D 1; + t =3D 0; + } + /* Neat trick that saves 1 symbol: instead of + or-ing 0 or 1 at each bit position, add 1 + or 2 instead. For example, 1011 is 1 << 0 + + 1 << 1 + 2 << 2. 1010 is 2 << 0 + 2 << 1 + + 1 << 2. You can make any bit pattern + that way using 1 less symbol than the basic + or 0/1 method (except all bits 0, which + would use no symbols, but a run of length 0 + doesn't mean anything in this context). + Thus space is saved. */ + t +=3D (runPos << nextSym); + /* +runPos if RUNA; +2*runPos if RUNB */ + + runPos <<=3D 1; + continue; + } + /* When we hit the first non-run symbol after a run, + we now know how many times to repeat the last + literal, so append that many copies to our buffer + of decoded symbols (dbuf) now. (The last literal + used is the one at the head of the mtfSymbol + array.) */ + if (runPos) { + runPos =3D 0; + if (dbufCount+t >=3D dbufSize) + return RETVAL_DATA_ERROR; + + uc =3D symToByte[mtfSymbol[0]]; + byteCount[uc] +=3D t; + while (t--) + dbuf[dbufCount++] =3D uc; + } + /* Is this the terminating symbol? */ + if (nextSym > symTotal) + break; + /* At this point, nextSym indicates a new literal + character. Subtract one to get the position in the + MTF array at which this literal is currently to be + found. (Note that the result can't be -1 or 0, + because 0 and 1 are RUNA and RUNB. But another + instance of the first symbol in the mtf array, + position 0, would have been handled as part of a + run above. Therefore 1 unused mtf position minus 2 + non-literal nextSym values equals -1.) */ + if (dbufCount >=3D dbufSize) + return RETVAL_DATA_ERROR; + i =3D nextSym - 1; + uc =3D mtfSymbol[i]; + /* Adjust the MTF array. Since we typically expect to + *move only a small number of symbols, and are bound + *by 256 in any case, using memmove here would + *typically be bigger and slower due to function call + *overhead and other assorted setup costs. */ + do { + mtfSymbol[i] =3D mtfSymbol[i-1]; + } while (--i); + mtfSymbol[0] =3D uc; + uc =3D symToByte[uc]; + /* We have our literal byte. Save it into dbuf. */ + byteCount[uc]++; + dbuf[dbufCount++] =3D (unsigned int)uc; + } + /* At this point, we've read all the Huffman-coded symbols + (and repeated runs) for this block from the input stream, + and decoded them into the intermediate buffer. There are + dbufCount many decoded bytes in dbuf[]. Now undo the + Burrows-Wheeler transform on dbuf. See + http://dogma.net/markn/articles/bwt/bwt.htm=20 + */ + /* Turn byteCount into cumulative occurrence counts of 0 to n-1. = */ + j =3D 0; + for (i =3D 0; i < 256; i++) { + k =3D j+byteCount[i]; + byteCount[i] =3D j; + j =3D k; + } + /* Figure out what order dbuf would be in if we sorted it. */ + for (i =3D 0; i < dbufCount; i++) { + uc =3D (unsigned char)(dbuf[i] & 0xff); + dbuf[byteCount[uc]] |=3D (i << 8); + byteCount[uc]++; + } + /* Decode first byte by hand to initialize "previous" byte. + Note that it doesn't get output, and if the first three + characters are identical it doesn't qualify as a run (hence + writeRunCountdown =3D 5). */ + if (dbufCount) { + if (origPtr >=3D dbufCount) + return RETVAL_DATA_ERROR; + bd->writePos =3D dbuf[origPtr]; + bd->writeCurrent =3D (unsigned char)(bd->writePos&0xff); + bd->writePos >>=3D 8; + bd->writeRunCountdown =3D 5; + } + bd->writeCount =3D dbufCount; + + return RETVAL_OK; +} + +/* Undo burrows-wheeler transform on intermediate buffer to produce = output. + If start_bunzip was initialized with out_fd =3D-1, then up to len = bytes of + data are written to outbuf. Return value is number of bytes written = or + error (all errors are negative numbers). If out_fd!=3D-1, outbuf and = len + are ignored, data is written to out_fd and return is RETVAL_OK or = error. +*/ + +static int INIT read_bunzip(struct bunzip_data *bd, unsigned char = *outbuf, int len) +{ + const unsigned int *dbuf; + int pos, xcurrent, previous, gotcount; + + /* If last read was short due to end of file, return last block = now */ + if (bd->writeCount < 0) + return bd->writeCount; + + gotcount =3D 0; + dbuf =3D bd->dbuf; + pos =3D bd->writePos; + xcurrent =3D bd->writeCurrent; + + /* We will always have pending decoded data to write into the = output + buffer unless this is the very first call (in which case we = haven't + Huffman-decoded a block into the intermediate buffer yet). */ + + if (bd->writeCopies) { + /* Inside the loop, writeCopies means extra copies (beyond = 1) */ + --bd->writeCopies; + /* Loop outputting bytes */ + for (;;) { + /* If the output buffer is full, snapshot + * state and return */ + if (gotcount >=3D len) { + bd->writePos =3D pos; + bd->writeCurrent =3D xcurrent; + bd->writeCopies++; + return len; + } + /* Write next byte into output buffer, updating = CRC */ + outbuf[gotcount++] =3D xcurrent; + bd->writeCRC =3D (((bd->writeCRC) << 8) + ^bd->crc32Table[((bd->writeCRC) >> 24) + ^xcurrent]); + /* Loop now if we're outputting multiple + * copies of this byte */ + if (bd->writeCopies) { + --bd->writeCopies; + continue; + } +decode_next_byte: + if (!bd->writeCount--) + break; + /* Follow sequence vector to undo + * Burrows-Wheeler transform */ + previous =3D xcurrent; + pos =3D dbuf[pos]; + xcurrent =3D pos&0xff; + pos >>=3D 8; + /* After 3 consecutive copies of the same + byte, the 4th is a repeat count. We count + down from 4 instead *of counting up because + testing for non-zero is faster */ + if (--bd->writeRunCountdown) { + if (xcurrent !=3D previous) + bd->writeRunCountdown =3D 4; + } else { + /* We have a repeated run, this byte + * indicates the count */ + bd->writeCopies =3D xcurrent; + xcurrent =3D previous; + bd->writeRunCountdown =3D 5; + /* Sometimes there are just 3 bytes + * (run length 0) */ + if (!bd->writeCopies) + goto decode_next_byte; + /* Subtract the 1 copy we'd output + * anyway to get extras */ + --bd->writeCopies; + } + } + /* Decompression of this block completed successfully */ + bd->writeCRC =3D ~bd->writeCRC; + bd->totalCRC =3D ((bd->totalCRC << 1) | + (bd->totalCRC >> 31)) ^ bd->writeCRC; + /* If this block had a CRC error, force file level CRC = error. */ + if (bd->writeCRC !=3D bd->headerCRC) { + bd->totalCRC =3D bd->headerCRC+1; + return RETVAL_LAST_BLOCK; + } + } + + /* Refill the intermediate buffer by Huffman-decoding next + * block of input */ + /* (previous is just a convenient unused temp variable here) */ + previous =3D get_next_block(bd); + if (previous) { + bd->writeCount =3D previous; + return (previous !=3D RETVAL_LAST_BLOCK) ? previous : = gotcount; + } + bd->writeCRC =3D 0xffffffffUL; + pos =3D bd->writePos; + xcurrent =3D bd->writeCurrent; + goto decode_next_byte; +} + +static int INIT nofill(void *buf, unsigned int len) +{ + return -1; +} + +/* Allocate the structure, read file header. If in_fd =3D=3D-1, inbuf = must contain + a complete bunzip file (len bytes long). If in_fd!=3D-1, inbuf and = len are + ignored, and data is read from file handle into temporary buffer. */ +static int INIT start_bunzip(struct bunzip_data **bdp, void *inbuf, int = len, + int (*fill)(void*, unsigned int)) +{ + struct bunzip_data *bd; + unsigned int i, j, c; + const unsigned int BZh0 =3D + (((unsigned int)'B') << 24)+(((unsigned int)'Z') << 16) + +(((unsigned int)'h') << 8)+(unsigned int)'0'; + + /* Figure out how much data to allocate */ + i =3D sizeof(struct bunzip_data); + + /* Allocate bunzip_data. Most fields initialize to zero. */ + bd =3D *bdp =3D malloc(i); + memset(bd, 0, sizeof(struct bunzip_data)); + /* Setup input buffer */ + bd->inbuf =3D inbuf; + bd->inbufCount =3D len; + if (fill !=3D NULL) + bd->fill =3D fill; + else + bd->fill =3D nofill; + + /* Init the CRC32 table (big endian) */ + for (i =3D 0; i < 256; i++) { + c =3D i << 24; + for (j =3D 8; j; j--) + c =3D c&0x80000000 ? (c << 1)^0x04c11db7 : (c << = 1); + bd->crc32Table[i] =3D c; + } + + /* Ensure that file starts with "BZh['1'-'9']." */ + i =3D get_bits(bd, 32); + if (((unsigned int)(i-BZh0-1)) >=3D 9) + return RETVAL_NOT_BZIP_DATA; + + /* Fourth byte (ascii '1'-'9'), indicates block size in units of = 100k of + uncompressed data. Allocate intermediate buffer for block. */ + bd->dbufSize =3D 100000*(i-BZh0); + + bd->dbuf =3D large_malloc(bd->dbufSize * sizeof(int)); + return RETVAL_OK; +} + +/* Example usage: decompress src_fd to dst_fd. (Stops at end of bzip2 = data, + not end of file.) */ +STATIC int INIT bunzip2(unsigned char *buf, unsigned int len, + int(*fill)(void*, unsigned int), + int(*flush)(void*, unsigned int), + unsigned char *outbuf, + unsigned int *pos, + void(*error_fn)(const char *x)) +{ + struct bunzip_data *bd; + int i =3D -1; + unsigned char *inbuf; + + set_error_fn(error_fn); + if (flush) + outbuf =3D malloc(BZIP2_IOBUF_SIZE); + + if (!outbuf) { + error("Could not allocate output bufer"); + return -1; + } + if (buf) + inbuf =3D buf; + else + inbuf =3D malloc(BZIP2_IOBUF_SIZE); + if (!inbuf) { + error("Could not allocate input bufer"); + goto exit_0; + } + i =3D start_bunzip(&bd, inbuf, len, fill); + if (!i) { + for (;;) { + i =3D read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE); + if (i <=3D 0) + break; + if (!flush) + outbuf +=3D i; + else + if (i !=3D flush(outbuf, i)) { + i =3D RETVAL_UNEXPECTED_OUTPUT_EOF;= + break; + } + } + } + /* Check CRC and release memory */ + if (i =3D=3D RETVAL_LAST_BLOCK) { + if (bd->headerCRC !=3D bd->totalCRC) + error("Data integrity error when decompressing."); + else + i =3D RETVAL_OK; + } else if (i =3D=3D RETVAL_UNEXPECTED_OUTPUT_EOF) { + error("Compressed file ends unexpectedly"); + } + if (bd->dbuf) + large_free(bd->dbuf); + if (pos) + *pos =3D bd->inbufPos; + free(bd); + if (!buf) + free(inbuf); +exit_0: + if (flush) + free(outbuf); + return i; +} --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ 2009-10-27/xen/common/decompress.c 2009-11-05 12:27:10.000000000 = +0100 @@ -0,0 +1,27 @@ +#include +#include +#include +#include +#include + +static void __init error(const char *msg) +{ + printk("%s\n", msg); +} + +int __init decompress(void *inbuf, unsigned int len, void *outbuf) +{ +#if 0 /* Not needed here yet. */ + if ( len >=3D 2 && + (!memcmp(inbuf, "\037\213", 2) || !memcmp(inbuf, "\037\236", 2)) = ) + return gunzip(inbuf, len, NULL, NULL, outbuf, NULL, error); +#endif + + if ( len >=3D 3 && !memcmp(inbuf, "\x42\x5a\x68", 3) ) + return bunzip2(inbuf, len, NULL, NULL, outbuf, NULL, error); + + if ( len >=3D 2 && !memcmp(inbuf, "\135\000", 2) ) + return unlzma(inbuf, len, NULL, NULL, outbuf, NULL, error); + + return 1; +} --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ 2009-10-27/xen/common/decompress.h 2009-11-05 15:21:52.000000000 = +0100 @@ -0,0 +1,19 @@ +#include +#include +#include +#include +#include +#include +#include + +#define STATIC +#define INIT __init + +static void(*__initdata error)(const char *); +#define set_error_fn(x) error =3D x; + +#define malloc xmalloc_bytes +#define free xfree + +#define large_malloc xmalloc_bytes +#define large_free xfree --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ 2009-10-27/xen/common/unlzma.c 2009-11-05 12:45:37.000000000 = +0100 @@ -0,0 +1,647 @@ +/* Lzma decompressor for Linux kernel. Shamelessly snarfed + * from busybox 1.1.1 + * + * Linux kernel adaptation + * Copyright (C) 2006 Alain < alain@knaff.lu > + * + * Based on small lzma deflate implementation/Small range coder + * implementation for lzma. + * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org > + * + * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) + * Copyright (C) 1999-2005 Igor Pavlov + * + * Copyrights of the parts, see headers below. + * + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 = USA + */ + +#include "decompress.h" + +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) + +static long long INIT read_int(unsigned char *ptr, int size) +{ + int i; + long long ret =3D 0; + + for (i =3D 0; i < size; i++) + ret =3D (ret << 8) | ptr[size-i-1]; + return ret; +} + +#define ENDIAN_CONVERT(x) \ + x =3D (typeof(x))read_int((unsigned char *)&x, sizeof(x)) + + +/* Small range coder implementation for lzma. + * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org > + * + * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) + * Copyright (c) 1999-2005 Igor Pavlov + */ + +#include + +#define LZMA_IOBUF_SIZE 0x10000 + +struct rc { + int (*fill)(void*, unsigned int); + uint8_t *ptr; + uint8_t *buffer; + uint8_t *buffer_end; + int buffer_size; + uint32_t code; + uint32_t range; + uint32_t bound; +}; + + +#define RC_TOP_BITS 24 +#define RC_MOVE_BITS 5 +#define RC_MODEL_TOTAL_BITS 11 + + +static int nofill(void *buffer, unsigned int len) +{ + return -1; +} + +/* Called twice: once at startup and once in rc_normalize() */ +static void INIT rc_read(struct rc *rc) +{ + rc->buffer_size =3D rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE); + if (rc->buffer_size <=3D 0) + error("unexpected EOF"); + rc->ptr =3D rc->buffer; + rc->buffer_end =3D rc->buffer + rc->buffer_size; +} + +/* Called once */ +static inline void INIT rc_init(struct rc *rc, + int (*fill)(void*, unsigned int), + unsigned char *buffer, int = buffer_size) +{ + if (fill) + rc->fill =3D fill; + else + rc->fill =3D nofill; + rc->buffer =3D (uint8_t *)buffer; + rc->buffer_size =3D buffer_size; + rc->buffer_end =3D rc->buffer + rc->buffer_size; + rc->ptr =3D rc->buffer; + + rc->code =3D 0; + rc->range =3D 0xFFFFFFFF; +} + +static inline void INIT rc_init_code(struct rc *rc) +{ + int i; + + for (i =3D 0; i < 5; i++) { + if (rc->ptr >=3D rc->buffer_end) + rc_read(rc); + rc->code =3D (rc->code << 8) | *rc->ptr++; + } +} + + +/* Called once. TODO: bb_maybe_free() */ +static inline void INIT rc_free(struct rc *rc) +{ + free(rc->buffer); +} + +/* Called twice, but one callsite is in inline'd rc_is_bit_0_helper() */ +static void INIT rc_do_normalize(struct rc *rc) +{ + if (rc->ptr >=3D rc->buffer_end) + rc_read(rc); + rc->range <<=3D 8; + rc->code =3D (rc->code << 8) | *rc->ptr++; +} +static inline void INIT rc_normalize(struct rc *rc) +{ + if (rc->range < (1 << RC_TOP_BITS)) + rc_do_normalize(rc); +} + +/* Called 9 times */ +/* Why rc_is_bit_0_helper exists? + *Because we want to always expose (rc->code < rc->bound) to optimizer + */ +static inline uint32_t INIT rc_is_bit_0_helper(struct rc *rc, uint16_t = *p) +{ + rc_normalize(rc); + rc->bound =3D *p * (rc->range >> RC_MODEL_TOTAL_BITS); + return rc->bound; +} +static inline int INIT rc_is_bit_0(struct rc *rc, uint16_t *p) +{ + uint32_t t =3D rc_is_bit_0_helper(rc, p); + return rc->code < t; +} + +/* Called ~10 times, but very small, thus inlined */ +static inline void INIT rc_update_bit_0(struct rc *rc, uint16_t *p) +{ + rc->range =3D rc->bound; + *p +=3D ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS; +} +static inline void rc_update_bit_1(struct rc *rc, uint16_t *p) +{ + rc->range -=3D rc->bound; + rc->code -=3D rc->bound; + *p -=3D *p >> RC_MOVE_BITS; +} + +/* Called 4 times in unlzma loop */ +static int INIT rc_get_bit(struct rc *rc, uint16_t *p, int *symbol) +{ + if (rc_is_bit_0(rc, p)) { + rc_update_bit_0(rc, p); + *symbol *=3D 2; + return 0; + } else { + rc_update_bit_1(rc, p); + *symbol =3D *symbol * 2 + 1; + return 1; + } +} + +/* Called once */ +static inline int INIT rc_direct_bit(struct rc *rc) +{ + rc_normalize(rc); + rc->range >>=3D 1; + if (rc->code >=3D rc->range) { + rc->code -=3D rc->range; + return 1; + } + return 0; +} + +/* Called twice */ +static inline void INIT +rc_bit_tree_decode(struct rc *rc, uint16_t *p, int num_levels, int = *symbol) +{ + int i =3D num_levels; + + *symbol =3D 1; + while (i--) + rc_get_bit(rc, p + *symbol, symbol); + *symbol -=3D 1 << num_levels; +} + + +/* + * Small lzma deflate implementation. + * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org > + * + * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/) + * Copyright (C) 1999-2005 Igor Pavlov + */ + + +struct lzma_header { + uint8_t pos; + uint32_t dict_size; + uint64_t dst_size; +} __attribute__ ((packed)) ; + + +#define LZMA_BASE_SIZE 1846 +#define LZMA_LIT_SIZE 768 + +#define LZMA_NUM_POS_BITS_MAX 4 + +#define LZMA_LEN_NUM_LOW_BITS 3 +#define LZMA_LEN_NUM_MID_BITS 3 +#define LZMA_LEN_NUM_HIGH_BITS 8 + +#define LZMA_LEN_CHOICE 0 +#define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1) +#define LZMA_LEN_LOW (LZMA_LEN_CHOICE_2 + 1) +#define LZMA_LEN_MID (LZMA_LEN_LOW \ + + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BIT= S))) +#define LZMA_LEN_HIGH (LZMA_LEN_MID \ + +(1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_MID_BIT= S))) +#define LZMA_NUM_LEN_PROBS (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))= + +#define LZMA_NUM_STATES 12 +#define LZMA_NUM_LIT_STATES 7 + +#define LZMA_START_POS_MODEL_INDEX 4 +#define LZMA_END_POS_MODEL_INDEX 14 +#define LZMA_NUM_FULL_DISTANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1)) + +#define LZMA_NUM_POS_SLOT_BITS 6 +#define LZMA_NUM_LEN_TO_POS_STATES 4 + +#define LZMA_NUM_ALIGN_BITS 4 + +#define LZMA_MATCH_MIN_LEN 2 + +#define LZMA_IS_MATCH 0 +#define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS= _MAX)) +#define LZMA_IS_REP_G0 (LZMA_IS_REP + LZMA_NUM_STATES) +#define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATES) +#define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES) +#define LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES) +#define LZMA_POS_SLOT (LZMA_IS_REP_0_LONG \ + + (LZMA_NUM_STATES << LZMA_NUM_POS_BITS_MAX)) +#define LZMA_SPEC_POS (LZMA_POS_SLOT \ + +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BI= TS)) +#define LZMA_ALIGN (LZMA_SPEC_POS \ + + LZMA_NUM_FULL_DISTANCES - LZMA_END_POS_MODEL_INDEX) +#define LZMA_LEN_CODER (LZMA_ALIGN + (1 << LZMA_NUM_ALIGN_BITS)) +#define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + LZMA_NUM_LEN_PROBS) +#define LZMA_LITERAL (LZMA_REP_LEN_CODER + LZMA_NUM_LEN_PROBS) + + +struct writer { + uint8_t *buffer; + uint8_t previous_byte; + size_t buffer_pos; + int bufsize; + size_t global_pos; + int(*flush)(void*, unsigned int); + struct lzma_header *header; +}; + +struct cstate { + int state; + uint32_t rep0, rep1, rep2, rep3; +}; + +static inline size_t INIT get_pos(struct writer *wr) +{ + return + wr->global_pos + wr->buffer_pos; +} + +static inline uint8_t INIT peek_old_byte(struct writer *wr, + uint32_t offs) +{ + if (!wr->flush) { + int32_t pos; + while (offs > wr->header->dict_size) + offs -=3D wr->header->dict_size; + pos =3D wr->buffer_pos - offs; + return wr->buffer[pos]; + } else { + uint32_t pos =3D wr->buffer_pos - offs; + while (pos >=3D wr->header->dict_size) + pos +=3D wr->header->dict_size; + return wr->buffer[pos]; + } + +} + +static inline void INIT write_byte(struct writer *wr, uint8_t byte) +{ + wr->buffer[wr->buffer_pos++] =3D wr->previous_byte =3D byte; + if (wr->flush && wr->buffer_pos =3D=3D wr->header->dict_size) { + wr->buffer_pos =3D 0; + wr->global_pos +=3D wr->header->dict_size; + wr->flush((char *)wr->buffer, wr->header->dict_size); + } +} + + +static inline void INIT copy_byte(struct writer *wr, uint32_t offs) +{ + write_byte(wr, peek_old_byte(wr, offs)); +} + +static inline void INIT copy_bytes(struct writer *wr, + uint32_t rep0, int len) +{ + do { + copy_byte(wr, rep0); + len--; + } while (len !=3D 0 && wr->buffer_pos < wr->header->dst_size); +} + +static inline void INIT process_bit0(struct writer *wr, struct rc *rc, + struct cstate *cst, uint16_t *p, + int pos_state, uint16_t *prob, + int lc, uint32_t literal_pos_mask) { + int mi =3D 1; + rc_update_bit_0(rc, prob); + prob =3D (p + LZMA_LITERAL + + (LZMA_LIT_SIZE + * (((get_pos(wr) & literal_pos_mask) << lc) + + (wr->previous_byte >> (8 - lc)))) + ); + + if (cst->state >=3D LZMA_NUM_LIT_STATES) { + int match_byte =3D peek_old_byte(wr, cst->rep0); + do { + int bit; + uint16_t *prob_lit; + + match_byte <<=3D 1; + bit =3D match_byte & 0x100; + prob_lit =3D prob + 0x100 + bit + mi; + if (rc_get_bit(rc, prob_lit, &mi)) { + if (!bit) + break; + } else { + if (bit) + break; + } + } while (mi < 0x100); + } + while (mi < 0x100) { + uint16_t *prob_lit =3D prob + mi; + rc_get_bit(rc, prob_lit, &mi); + } + write_byte(wr, mi); + if (cst->state < 4) + cst->state =3D 0; + else if (cst->state < 10) + cst->state -=3D 3; + else + cst->state -=3D 6; +} + +static inline void INIT process_bit1(struct writer *wr, struct rc *rc, + struct cstate *cst, uint16_t = *p, + int pos_state, uint16_t *prob) = { + int offset; + uint16_t *prob_len; + int num_bits; + int len; + + rc_update_bit_1(rc, prob); + prob =3D p + LZMA_IS_REP + cst->state; + if (rc_is_bit_0(rc, prob)) { + rc_update_bit_0(rc, prob); + cst->rep3 =3D cst->rep2; + cst->rep2 =3D cst->rep1; + cst->rep1 =3D cst->rep0; + cst->state =3D cst->state < LZMA_NUM_LIT_STATES ? 0 : 3; + prob =3D p + LZMA_LEN_CODER; + } else { + rc_update_bit_1(rc, prob); + prob =3D p + LZMA_IS_REP_G0 + cst->state; + if (rc_is_bit_0(rc, prob)) { + rc_update_bit_0(rc, prob); + prob =3D (p + LZMA_IS_REP_0_LONG + + (cst->state << + LZMA_NUM_POS_BITS_MAX) + + pos_state); + if (rc_is_bit_0(rc, prob)) { + rc_update_bit_0(rc, prob); + + cst->state =3D cst->state < LZMA_NUM_LIT_ST= ATES ? + 9 : 11; + copy_byte(wr, cst->rep0); + return; + } else { + rc_update_bit_1(rc, prob); + } + } else { + uint32_t distance; + + rc_update_bit_1(rc, prob); + prob =3D p + LZMA_IS_REP_G1 + cst->state; + if (rc_is_bit_0(rc, prob)) { + rc_update_bit_0(rc, prob); + distance =3D cst->rep1; + } else { + rc_update_bit_1(rc, prob); + prob =3D p + LZMA_IS_REP_G2 + cst->state; + if (rc_is_bit_0(rc, prob)) { + rc_update_bit_0(rc, prob); + distance =3D cst->rep2; + } else { + rc_update_bit_1(rc, prob); + distance =3D cst->rep3; + cst->rep3 =3D cst->rep2; + } + cst->rep2 =3D cst->rep1; + } + cst->rep1 =3D cst->rep0; + cst->rep0 =3D distance; + } + cst->state =3D cst->state < LZMA_NUM_LIT_STATES ? 8 : 11; + prob =3D p + LZMA_REP_LEN_CODER; + } + + prob_len =3D prob + LZMA_LEN_CHOICE; + if (rc_is_bit_0(rc, prob_len)) { + rc_update_bit_0(rc, prob_len); + prob_len =3D (prob + LZMA_LEN_LOW + + (pos_state << + LZMA_LEN_NUM_LOW_BITS)); + offset =3D 0; + num_bits =3D LZMA_LEN_NUM_LOW_BITS; + } else { + rc_update_bit_1(rc, prob_len); + prob_len =3D prob + LZMA_LEN_CHOICE_2; + if (rc_is_bit_0(rc, prob_len)) { + rc_update_bit_0(rc, prob_len); + prob_len =3D (prob + LZMA_LEN_MID + + (pos_state << + LZMA_LEN_NUM_MID_BITS)); + offset =3D 1 << LZMA_LEN_NUM_LOW_BITS; + num_bits =3D LZMA_LEN_NUM_MID_BITS; + } else { + rc_update_bit_1(rc, prob_len); + prob_len =3D prob + LZMA_LEN_HIGH; + offset =3D ((1 << LZMA_LEN_NUM_LOW_BITS) + + (1 << LZMA_LEN_NUM_MID_BITS)); + num_bits =3D LZMA_LEN_NUM_HIGH_BITS; + } + } + + rc_bit_tree_decode(rc, prob_len, num_bits, &len); + len +=3D offset; + + if (cst->state < 4) { + int pos_slot; + + cst->state +=3D LZMA_NUM_LIT_STATES; + prob =3D + p + LZMA_POS_SLOT + + ((len < + LZMA_NUM_LEN_TO_POS_STATES ? len : + LZMA_NUM_LEN_TO_POS_STATES - 1) + << LZMA_NUM_POS_SLOT_BITS); + rc_bit_tree_decode(rc, prob, + LZMA_NUM_POS_SLOT_BITS, + &pos_slot); + if (pos_slot >=3D LZMA_START_POS_MODEL_INDEX) { + int i, mi; + num_bits =3D (pos_slot >> 1) - 1; + cst->rep0 =3D 2 | (pos_slot & 1); + if (pos_slot < LZMA_END_POS_MODEL_INDEX) { + cst->rep0 <<=3D num_bits; + prob =3D p + LZMA_SPEC_POS + + cst->rep0 - pos_slot - 1; + } else { + num_bits -=3D LZMA_NUM_ALIGN_BITS; + while (num_bits--) + cst->rep0 =3D (cst->rep0 << 1) | + rc_direct_bit(rc); + prob =3D p + LZMA_ALIGN; + cst->rep0 <<=3D LZMA_NUM_ALIGN_BITS; + num_bits =3D LZMA_NUM_ALIGN_BITS; + } + i =3D 1; + mi =3D 1; + while (num_bits--) { + if (rc_get_bit(rc, prob + mi, &mi)) + cst->rep0 |=3D i; + i <<=3D 1; + } + } else + cst->rep0 =3D pos_slot; + if (++(cst->rep0) =3D=3D 0) + return; + } + + len +=3D LZMA_MATCH_MIN_LEN; + + copy_bytes(wr, cst->rep0, len); +} + + + +STATIC inline int INIT unlzma(unsigned char *buf, unsigned int in_len, + int(*fill)(void*, unsigned int), + int(*flush)(void*, unsigned int), + unsigned char *output, + unsigned int *posp, + void(*error_fn)(const char *x) + ) +{ + struct lzma_header header; + int lc, pb, lp; + uint32_t pos_state_mask; + uint32_t literal_pos_mask; + uint16_t *p; + int num_probs; + struct rc rc; + int i, mi; + struct writer wr; + struct cstate cst; + unsigned char *inbuf; + int ret =3D -1; + + set_error_fn(error_fn); + + if (buf) + inbuf =3D buf; + else + inbuf =3D malloc(LZMA_IOBUF_SIZE); + if (!inbuf) { + error("Could not allocate input bufer"); + goto exit_0; + } + + cst.state =3D 0; + cst.rep0 =3D cst.rep1 =3D cst.rep2 =3D cst.rep3 =3D 1; + + wr.header =3D &header; + wr.flush =3D flush; + wr.global_pos =3D 0; + wr.previous_byte =3D 0; + wr.buffer_pos =3D 0; + + rc_init(&rc, fill, inbuf, in_len); + + for (i =3D 0; i < sizeof(header); i++) { + if (rc.ptr >=3D rc.buffer_end) + rc_read(&rc); + ((unsigned char *)&header)[i] =3D *rc.ptr++; + } + + if (header.pos >=3D (9 * 5 * 5)) + error("bad header"); + + mi =3D 0; + lc =3D header.pos; + while (lc >=3D 9) { + mi++; + lc -=3D 9; + } + pb =3D 0; + lp =3D mi; + while (lp >=3D 5) { + pb++; + lp -=3D 5; + } + pos_state_mask =3D (1 << pb) - 1; + literal_pos_mask =3D (1 << lp) - 1; + + ENDIAN_CONVERT(header.dict_size); + ENDIAN_CONVERT(header.dst_size); + + if (header.dict_size =3D=3D 0) + header.dict_size =3D 1; + + if (output) + wr.buffer =3D output; + else { + wr.bufsize =3D MIN(header.dst_size, header.dict_size); + wr.buffer =3D large_malloc(wr.bufsize); + } + if (wr.buffer =3D=3D NULL) + goto exit_1; + + num_probs =3D LZMA_BASE_SIZE + (LZMA_LIT_SIZE << (lc + lp)); + p =3D (uint16_t *) large_malloc(num_probs * sizeof(*p)); + if (p =3D=3D 0) + goto exit_2; + num_probs =3D LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp)); + for (i =3D 0; i < num_probs; i++) + p[i] =3D (1 << RC_MODEL_TOTAL_BITS) >> 1; + + rc_init_code(&rc); + + while (get_pos(&wr) < header.dst_size) { + int pos_state =3D get_pos(&wr) & pos_state_mask; + uint16_t *prob =3D p + LZMA_IS_MATCH + + (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state; + if (rc_is_bit_0(&rc, prob)) + process_bit0(&wr, &rc, &cst, p, pos_state, prob, + lc, literal_pos_mask); + else { + process_bit1(&wr, &rc, &cst, p, pos_state, prob); + if (cst.rep0 =3D=3D 0) + break; + } + } + + if (posp) + *posp =3D rc.ptr-rc.buffer; + if (wr.flush) + wr.flush(wr.buffer, wr.buffer_pos); + ret =3D 0; + large_free(p); +exit_2: + if (!output) + large_free(wr.buffer); +exit_1: + if (!buf) + free(inbuf); +exit_0: + return ret; +} --- /dev/null 1970-01-01 00:00:00.000000000 +0000 +++ 2009-10-27/xen/include/xen/decompress.h 2009-11-05 12:27:44.0000000= 00 +0100 @@ -0,0 +1,38 @@ +#ifndef __XEN_GENERIC_H +#define __XEN_GENERIC_H + +typedef int decompress_fn(unsigned char *inbuf, unsigned int len, + int (*fill)(void*, unsigned int), + int (*flush)(void*, unsigned int), + unsigned char *outbuf, unsigned int *posp, + void (*error)(const char *x)); + +/* inbuf - input buffer + * len - len of pre-read data in inbuf + * fill - function to fill inbuf when empty + * flush - function to write out outbuf + * outbuf - output buffer + * posp - if non-null, input position (number of bytes read) will be + * returned here + * error - error reporting function + * + * If len !=3D 0, inbuf should contain all the necessary input data, and = fill + * should be NULL + * If len =3D 0, inbuf can be NULL, in which case the decompressor will = allocate + * the input buffer. If inbuf !=3D NULL it must be at least XXX_IOBUF_SIZ= E bytes. + * fill will be called (repeatedly...) to read data, at most XXX_IOBUF_SIZ= E + * bytes should be read per call. Replace XXX with the appropriate = decompressor + * name, i.e. LZMA_IOBUF_SIZE. + * + * If flush =3D NULL, outbuf must be large enough to buffer all the = expected + * output. If flush !=3D NULL, the output buffer will be allocated by = the + * decompressor (outbuf =3D NULL), and the flush function will be called = to + * flush the output buffer at the appropriate time (decompressor and = stream + * dependent). + */ + +decompress_fn bunzip2, unlzma; + +int decompress(void *inbuf, unsigned int len, void *outbuf); + +#endif --=__Part163DA326.0__= Content-Type: text/plain; name="xen-x86-advanced-decompress.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="xen-x86-advanced-decompress.patch" This matches functionality in the tools already supporting the same = for=0ADomU-s.=0A=0ACode taken from Linux 2.6.32-rc and adjusted as little = as possible to=0Abe usable in Xen.=0A=0AThe question is whether, particular= ly for non-Linux Dom0-s, plain ELF=0Aimages compressed by bzip2 or lzma = should also be supported.=0A=0ASigned-off-by: Jan Beulich =0A=0A--- 2009-10-27.orig/xen/arch/x86/bzimage.c 2009-10-07 = 13:31:36.000000000 +0200=0A+++ 2009-10-27/xen/arch/x86/bzimage.c = 2009-11-05 12:23:05.000000000 +0100=0A@@ -4,6 +4,7 @@=0A #include = =0A #include =0A #include =0A+#include= =0A #include =0A =0A #define HEAPORDER = 3=0A@@ -93,28 +94,38 @@ static __init void flush_window(void)=0A = outcnt =3D 0;=0A }=0A =0A-static __init int gzip_length(char *image, = unsigned long image_len)=0A+static __init unsigned long output_length(char = *image, unsigned long image_len)=0A {=0A return *(uint32_t *)&image[ima= ge_len - 4];=0A }=0A =0A-static __init int perform_gunzip(char *output, = char **_image_start, unsigned long *image_len)=0A+static __init int = gzip_check(char *image, unsigned long image_len)=0A {=0A- char *image = =3D *_image_start;=0A- int rc;=0A- unsigned char magic0 =3D = (unsigned char)image[0];=0A- unsigned char magic1 =3D (unsigned = char)image[1];=0A+ unsigned char magic0, magic1;=0A =0A- if ( magic0 = !=3D 0x1f || ( (magic1 !=3D 0x8b) && (magic1 !=3D 0x9e) ) )=0A+ if ( = image_len < 2 )=0A return 0;=0A =0A+ magic0 =3D (unsigned = char)image[0];=0A+ magic1 =3D (unsigned char)image[1];=0A+=0A+ = return (magic0 =3D=3D 0x1f) && ((magic1 =3D=3D 0x8b) || (magic1 =3D=3D = 0x9e));=0A+}=0A+=0A+static __init int perform_gunzip(char *output, char = *image, unsigned long image_len)=0A+{=0A+ int rc;=0A+=0A+ if ( = !gzip_check(image, image_len) )=0A+ return 1;=0A+=0A window =3D = (unsigned char *)output;=0A =0A free_mem_ptr =3D (unsigned long)alloc_x= enheap_pages(HEAPORDER, 0);=0A free_mem_end_ptr =3D free_mem_ptr + = (PAGE_SIZE << HEAPORDER);=0A =0A inbuf =3D (unsigned char *)image;=0A- = insize =3D *image_len;=0A+ insize =3D image_len;=0A inptr =3D = 0;=0A =0A makecrc();=0A@@ -125,8 +136,6 @@ static __init int = perform_gunzip(char *=0A }=0A else=0A {=0A- *_image_star= t =3D (char *)window;=0A- *image_len =3D gzip_length(image, = *image_len);=0A rc =3D 0;=0A }=0A =0A@@ -203,9 +212,12 @@ int = __init bzimage_headroom(char *image_=0A img =3D image_start + = (hdr->setup_sects+1) * 512;=0A img +=3D hdr->payload_offset;=0A =0A- = headroom =3D gzip_length(img, hdr->payload_length);=0A- headroom +=3D = headroom >> 12; /* Add 8 bytes for every 32K input block */=0A- = headroom +=3D (32768 + 18); /* Add 32K + 18 bytes of extra headroom */=0A+ = headroom =3D output_length(img, hdr->payload_length);=0A+ if = (gzip_check(img, hdr->payload_length)) {=0A+ headroom +=3D headroom = >> 12; /* Add 8 bytes for every 32K input block */=0A+ headroom = +=3D (32768 + 18); /* Add 32K + 18 bytes of extra headroom */=0A+ } = else=0A+ headroom +=3D hdr->payload_length;=0A headroom =3D = (headroom + 4095) & ~4095;=0A =0A return headroom;=0A@@ -215,6 +227,7 = @@ int __init bzimage_parse(char *image_bas=0A {=0A struct setup_header= *hdr =3D (struct setup_header *)(*image_start);=0A int err =3D = bzimage_check(hdr, *image_len);=0A+ unsigned long output_len;=0A =0A = if (err < 1)=0A return err;=0A@@ -224,11 +237,18 @@ int __init = bzimage_parse(char *image_bas=0A *image_start +=3D (hdr->setup_sects+1)= * 512;=0A *image_start +=3D hdr->payload_offset;=0A *image_len = =3D hdr->payload_length;=0A+ output_len =3D output_length(*image_start, = *image_len);=0A =0A- if ( (err =3D perform_gunzip(image_base, image_star= t, image_len)) < 0 )=0A- return err;=0A+ if ( (err =3D perform_gu= nzip(image_base, *image_start, *image_len)) > 0 )=0A+ err =3D = decompress(*image_start, *image_len, image_base);=0A+=0A+ if ( !err = )=0A+ {=0A+ *image_start =3D image_base;=0A+ *image_len = =3D output_len;=0A+ }=0A =0A- return 0;=0A+ return err > 0 ? 0 : = err;=0A }=0A =0A /*=0A--- 2009-10-27.orig/xen/common/Makefile 2009-05-27 = 13:54:07.000000000 +0200=0A+++ 2009-10-27/xen/common/Makefile 2009-11-05 = 12:26:53.000000000 +0100=0A@@ -35,6 +35,8 @@ obj-y +=3D radix-tree.o=0A = obj-y +=3D rbtree.o=0A obj-y +=3D lzo.o=0A =0A+obj-$(CONFIG_X86) +=3D = decompress.o bunzip2.o unlzma.o=0A+=0A obj-$(perfc) +=3D perfc.o=0A = obj-$(crash_debug) +=3D gdbstub.o=0A obj-$(xenoprof) +=3D xenoprof.o=0A-= -- /dev/null 1970-01-01 00:00:00.000000000 +0000=0A+++ 2009-10-27/xen/co= mmon/bunzip2.c 2009-11-05 12:44:51.000000000 +0100=0A@@ -0,0 +1,726 = @@=0A+/* vi: set sw =3D 4 ts =3D 4: */=0A+/* Small bzip2 deflate = implementation, by Rob Landley (rob@landley.net).=0A+=0A+ Based on = bzip2 decompression code by Julian R Seward (jseward@acm.org),=0A+ = which also acknowledges contributions by Mike Burrows, David Wheeler,=0A+ = Peter Fenwick, Alistair Moffat, Radford Neal, Ian H. Witten,=0A+ = Robert Sedgewick, and Jon L. Bentley.=0A+=0A+ This code is licensed = under the LGPLv2:=0A+ LGPL (http://www.gnu.org/copyleft/lgpl.html= =0A+*/=0A+=0A+/*=0A+ Size and speed optimizations by Manuel Novoa III = (mjn3@codepoet.org).=0A+=0A+ More efficient reading of Huffman codes, a = streamlined read_bunzip()=0A+ function, and various other tweaks. In = (limited) tests, approximately=0A+ 20% faster than bzcat on x86 and = about 10% faster on arm.=0A+=0A+ Note that about 2/3 of the time is = spent in read_unzip() reversing=0A+ the Burrows-Wheeler transformation.= Much of that time is delay=0A+ resulting from cache misses.=0A+=0A= + I would ask that anyone benefiting from this work, especially = those=0A+ using it in commercial products, consider making a = donation to my local=0A+ non-profit hospice organization in the = name of the woman I loved, who=0A+ passed away Feb. 12, 2003.=0A+=0A+ = In memory of Toni W. Hagan=0A+=0A+ Hospice of = Acadiana, Inc.=0A+ 2600 Johnston St., Suite 200=0A+ = Lafayette, LA 70503-3240=0A+=0A+ Phone (337) 232-1234 or = 1-800-738-2226=0A+ Fax (337) 232-1297=0A+=0A+ = http://www.hospiceacadiana.com/=0A+=0A+ Manuel=0A+ */=0A+=0A+/*=0A+ = Made it fit for running in Linux Kernel by Alain Knaff (alain@knaff.lu)=0A+= */=0A+=0A+#include "decompress.h"=0A+=0A+#ifndef INT_MAX=0A+#define = INT_MAX 0x7fffffff=0A+#endif=0A+=0A+/* Constants for Huffman coding = */=0A+#define MAX_GROUPS 6=0A+#define GROUP_SIZE = 50 /* 64 would have been more efficient */=0A+#define MAX_HUFCODE_BITS= 20 /* Longest Huffman code allowed */=0A+#define MAX_SYMBOLS = 258 /* 256 literals + RUNA + RUNB */=0A+#define SYMBOL_RUNA = 0=0A+#define SYMBOL_RUNB 1=0A+=0A+/* Status return values = */=0A+#define RETVAL_OK 0=0A+#define RETVAL_LAST_BLOCK = (-1)=0A+#define RETVAL_NOT_BZIP_DATA (-2)=0A+#define RETVAL_UNEX= PECTED_INPUT_EOF (-3)=0A+#define RETVAL_UNEXPECTED_OUTPUT_EOF = (-4)=0A+#define RETVAL_DATA_ERROR (-5)=0A+#define RETVAL_OUT_= OF_MEMORY (-6)=0A+#define RETVAL_OBSOLETE_INPUT = (-7)=0A+=0A+/* Other housekeeping constants */=0A+#define BZIP2_IOBUF_SIZE = 4096=0A+=0A+/* This is what we know about each Huffman coding = group */=0A+struct group_data {=0A+ /* We have an extra slot at the = end of limit[] for a sentinal value. */=0A+ int limit[MAX_HUFCODE_BITS+= 1];=0A+ int base[MAX_HUFCODE_BITS];=0A+ int permute[MAX_SYMBOLS];=0A+ = int minLen, maxLen;=0A+};=0A+=0A+/* Structure holding all the housekeeping = data, including IO buffers and=0A+ memory that persists between calls to = bunzip */=0A+struct bunzip_data {=0A+ /* State for interrupting output = loop */=0A+ int writeCopies, writePos, writeRunCountdown, writeCount, = writeCurrent;=0A+ /* I/O tracking data (file handles, buffers, = positions, etc.) */=0A+ int (*fill)(void*, unsigned int);=0A+ int = inbufCount, inbufPos /*, outbufPos*/;=0A+ unsigned char *inbuf = /*,*outbuf*/;=0A+ unsigned int inbufBitCount, inbufBits;=0A+ /* = The CRC values stored in the block header and calculated from the=0A+ = data */=0A+ unsigned int crc32Table[256], headerCRC, totalCRC, = writeCRC;=0A+ /* Intermediate buffer and its size (in bytes) */=0A+ = unsigned int *dbuf, dbufSize;=0A+ /* These things are a bit too big = to go on the stack */=0A+ unsigned char selectors[32768]; /* = nSelectors =3D 15 bits */=0A+ struct group_data groups[MAX_GROUPS]; /* = Huffman coding tables */=0A+ int io_error; /* = non-zero if we have IO error */=0A+};=0A+=0A+=0A+/* Return the next nnn = bits of input. All reads from the compressed input=0A+ are done through = this function. All reads are big endian */=0A+static unsigned int INIT = get_bits(struct bunzip_data *bd, char bits_wanted)=0A+{=0A+ unsigned = int bits =3D 0;=0A+=0A+ /* If we need to get more data from the byte = buffer, do so.=0A+ (Loop getting one byte at a time to enforce = endianness and avoid=0A+ unaligned access.) */=0A+ while = (bd->inbufBitCount < bits_wanted) {=0A+ /* If we need to read more = data from file into byte buffer, do=0A+ so */=0A+ if = (bd->inbufPos =3D=3D bd->inbufCount) {=0A+ if = (bd->io_error)=0A+ return 0;=0A+ = bd->inbufCount =3D bd->fill(bd->inbuf, BZIP2_IOBUF_SIZE);=0A+ = if (bd->inbufCount <=3D 0) {=0A+ bd->io_erro= r =3D RETVAL_UNEXPECTED_INPUT_EOF;=0A+ return = 0;=0A+ }=0A+ bd->inbufPos =3D 0;=0A+ = }=0A+ /* Avoid 32-bit overflow (dump bit buffer to top of = output) */=0A+ if (bd->inbufBitCount >=3D 24) {=0A+ = bits =3D bd->inbufBits&((1 << bd->inbufBitCount)-1);=0A+ = bits_wanted -=3D bd->inbufBitCount;=0A+ bits <<=3D = bits_wanted;=0A+ bd->inbufBitCount =3D 0;=0A+ = }=0A+ /* Grab next 8 bits of input from buffer. */=0A+ = bd->inbufBits =3D (bd->inbufBits << 8)|bd->inbuf[bd->inbufPos++];=0A+ = bd->inbufBitCount +=3D 8;=0A+ }=0A+ /* Calculate result */=0A+ = bd->inbufBitCount -=3D bits_wanted;=0A+ bits |=3D (bd->inbufBits >> = bd->inbufBitCount)&((1 << bits_wanted)-1);=0A+=0A+ return bits;=0A+}= =0A+=0A+/* Unpacks the next block and sets up for the inverse burrows-wheel= er step. */=0A+=0A+static int INIT get_next_block(struct bunzip_data = *bd)=0A+{=0A+ struct group_data *hufGroup =3D NULL;=0A+ int *base = =3D NULL;=0A+ int *limit =3D NULL;=0A+ int dbufCount, nextSym, = dbufSize, groupCount, selector,=0A+ i, j, k, t, runPos, = symCount, symTotal, nSelectors,=0A+ byteCount[256];=0A+ = unsigned char uc, symToByte[256], mtfSymbol[256], *selectors;=0A+ = unsigned int *dbuf, origPtr;=0A+=0A+ dbuf =3D bd->dbuf;=0A+ dbufSize = =3D bd->dbufSize;=0A+ selectors =3D bd->selectors;=0A+=0A+ /* Read in = header signature and CRC, then validate signature.=0A+ (last block = signature means CRC is for whole file, return now) */=0A+ i =3D = get_bits(bd, 24);=0A+ j =3D get_bits(bd, 24);=0A+ bd->headerCRC =3D = get_bits(bd, 32);=0A+ if ((i =3D=3D 0x177245) && (j =3D=3D 0x385090))=0A+= return RETVAL_LAST_BLOCK;=0A+ if ((i !=3D 0x314159) || = (j !=3D 0x265359))=0A+ return RETVAL_NOT_BZIP_DATA;=0A+ /* = We can add support for blockRandomised if anybody complains.=0A+ = There was some code for this in busybox 1.0.0-pre3, but nobody ever=0A+ = noticed that it didn't actually work. */=0A+ if (get_bits(bd, 1))=0A+ = return RETVAL_OBSOLETE_INPUT;=0A+ origPtr =3D get_bits(bd, = 24);=0A+ if (origPtr > dbufSize)=0A+ return RETVAL_DATA_= ERROR;=0A+ /* mapping table: if some byte values are never used = (encoding things=0A+ like ascii text), the compression code removes = the gaps to have fewer=0A+ symbols to deal with, and writes a = sparse bitfield indicating which=0A+ values were present. We make a = translation table to convert the=0A+ symbols back to the correspondin= g bytes. */=0A+ t =3D get_bits(bd, 16);=0A+ symTotal =3D 0;=0A+ = for (i =3D 0; i < 16; i++) {=0A+ if (t&(1 << (15-i))) {=0A+ = k =3D get_bits(bd, 16);=0A+ for (j =3D = 0; j < 16; j++)=0A+ if (k&(1 << (15-j)))=0A+ = symToByte[symTotal++] =3D (16*i)+j;=0A+ = }=0A+ }=0A+ /* How many different Huffman coding groups does this = block use? */=0A+ groupCount =3D get_bits(bd, 3);=0A+ if = (groupCount < 2 || groupCount > MAX_GROUPS)=0A+ return RETVAL_DATA_= ERROR;=0A+ /* nSelectors: Every GROUP_SIZE many symbols we select a = new=0A+ Huffman coding group. Read in the group selector list,=0A+ = which is stored as MTF encoded bit runs. (MTF =3D Move To=0A+ Front, = as each value is used it's moved to the start of the=0A+ list.) = */=0A+ nSelectors =3D get_bits(bd, 15);=0A+ if (!nSelectors)=0A+ = return RETVAL_DATA_ERROR;=0A+ for (i =3D 0; i < groupCount; i++)=0A+ = mtfSymbol[i] =3D i;=0A+ for (i =3D 0; i < nSelectors; i++) {=0A+ = /* Get next value */=0A+ for (j =3D 0; get_bits(bd, 1); = j++)=0A+ if (j >=3D groupCount)=0A+ = return RETVAL_DATA_ERROR;=0A+ /* Decode MTF to get the = next selector */=0A+ uc =3D mtfSymbol[j];=0A+ = for (; j; j--)=0A+ mtfSymbol[j] =3D mtfSymbol[j-1];=0A= + mtfSymbol[0] =3D selectors[i] =3D uc;=0A+ }=0A+ /* = Read the Huffman coding tables for each group, which code=0A+ for = symTotal literal symbols, plus two run symbols (RUNA,=0A+ RUNB) = */=0A+ symCount =3D symTotal+2;=0A+ for (j =3D 0; j < groupCount; j++) = {=0A+ unsigned char length[MAX_SYMBOLS], temp[MAX_HUFCODE_BITS+1]= ;=0A+ int minLen, maxLen, pp;=0A+ /* Read Huffman = code lengths for each symbol. They're=0A+ stored in a way = similar to mtf; record a starting=0A+ value for the first = symbol, and an offset from the=0A+ previous value for = everys symbol after that.=0A+ (Subtracting 1 before the loop = and then adding it=0A+ back at the end is an optimization that = makes the=0A+ test inside the loop simpler: symbol length = 0=0A+ becomes negative, so an unsigned inequality catches=0A+ = it.) */=0A+ t =3D get_bits(bd, 5)-1;=0A+ = for (i =3D 0; i < symCount; i++) {=0A+ for (;;) {=0A+ = if (((unsigned)t) > (MAX_HUFCODE_BITS-1))=0A+ = return RETVAL_DATA_ERROR;=0A+=0A+ = /* If first bit is 0, stop. Else=0A+ second = bit indicates whether to=0A+ increment or = decrement the value.=0A+ Optimization: = grab 2 bits and unget=0A+ the second if = the first was 0. */=0A+=0A+ k =3D get_bits(bd, = 2);=0A+ if (k < 2) {=0A+ = bd->inbufBitCount++;=0A+ = break;=0A+ }=0A+ /* = Add one if second bit 1, else=0A+ * = subtract 1. Avoids if/else */=0A+ t +=3D = (((k+1)&2)-1);=0A+ }=0A+ /* Correct = for the initial -1, to get the=0A+ * final symbol = length */=0A+ length[i] =3D t+1;=0A+ }=0A+ = /* Find largest and smallest lengths in this group */=0A+ = minLen =3D maxLen =3D length[0];=0A+=0A+ for (i =3D 1; i < = symCount; i++) {=0A+ if (length[i] > maxLen)=0A+ = maxLen =3D length[i];=0A+ else if = (length[i] < minLen)=0A+ minLen =3D = length[i];=0A+ }=0A+=0A+ /* Calculate permute[], = base[], and limit[] tables from=0A+ * length[].=0A+ = *=0A+ * permute[] is the lookup table for converting=0A+ = * Huffman coded symbols into decoded symbols. base[]=0A+ * = is the amount to subtract from the value of a=0A+ * Huffman = symbol of a given length when using=0A+ * permute[].=0A+ = *=0A+ * limit[] indicates the largest numerical value a=0A+ = * symbol with a given number of bits can have. This=0A+ * = is how the Huffman codes can vary in length: each=0A+ * code = with a value > limit[length] needs another=0A+ * bit.=0A+ = */=0A+ hufGroup =3D bd->groups+j;=0A+ hufGroup->minLen = =3D minLen;=0A+ hufGroup->maxLen =3D maxLen;=0A+ /* = Note that minLen can't be smaller than 1, so we=0A+ adjust = the base and limit array pointers so we're=0A+ not always = wasting the first entry. We do this=0A+ again when = using them (during symbol decoding).*/=0A+ base =3D hufGroup->= base-1;=0A+ limit =3D hufGroup->limit-1;=0A+ /* = Calculate permute[]. Concurently, initialize=0A+ * temp[] = and limit[]. */=0A+ pp =3D 0;=0A+ for (i =3D minLen; = i <=3D maxLen; i++) {=0A+ temp[i] =3D limit[i] =3D = 0;=0A+ for (t =3D 0; t < symCount; t++)=0A+ = if (length[t] =3D=3D i)=0A+ = hufGroup->permute[pp++] =3D t;=0A+ }=0A+ /* Count = symbols coded for at each bit length */=0A+ for (i =3D 0; i < = symCount; i++)=0A+ temp[length[i]]++;=0A+ /* = Calculate limit[] (the largest symbol-coding value=0A+ *at each = bit length, which is (previous limit <<=0A+ *1)+symbols at = this level), and base[] (number of=0A+ *symbols to ignore at = each bit length, which is limit=0A+ *minus the cumulative = count of symbols coded for=0A+ *already). */=0A+ pp = =3D t =3D 0;=0A+ for (i =3D minLen; i < maxLen; i++) {=0A+ = pp +=3D temp[i];=0A+ /* We read the = largest possible symbol size=0A+ and then unget = bits after determining how=0A+ many we need, and those = extra bits could be=0A+ set to anything. (They're = noise from=0A+ future symbols.) At each level = we're=0A+ really only interested in the first = few=0A+ bits, so here we set all the trailing=0A+ = to-be-ignored bits to 1 so they don't=0A+ = affect the value > limit[length]=0A+ comparison. = */=0A+ limit[i] =3D (pp << (maxLen - i)) - 1;=0A+ = pp <<=3D 1;=0A+ base[i+1] =3D pp-(t +=3D = temp[i]);=0A+ }=0A+ limit[maxLen+1] =3D INT_MAX; /* = Sentinal value for=0A+ * reading next = sym. */=0A+ limit[maxLen] =3D pp+temp[maxLen]-1;=0A+ = base[minLen] =3D 0;=0A+ }=0A+ /* We've finished reading and digesting = the block header. Now=0A+ read this block's Huffman coded symbols = from the file and=0A+ undo the Huffman coding and run length = encoding, saving the=0A+ result into dbuf[dbufCount++] =3D uc = */=0A+=0A+ /* Initialize symbol occurrence counters and symbol Move = To=0A+ * Front table */=0A+ for (i =3D 0; i < 256; i++) {=0A+ = byteCount[i] =3D 0;=0A+ mtfSymbol[i] =3D (unsigned char)i;=0A+ = }=0A+ /* Loop through compressed symbols. */=0A+ runPos =3D = dbufCount =3D symCount =3D selector =3D 0;=0A+ for (;;) {=0A+ /* = Determine which Huffman coding group to use. */=0A+ if = (!(symCount--)) {=0A+ symCount =3D GROUP_SIZE-1;=0A+ = if (selector >=3D nSelectors)=0A+ = return RETVAL_DATA_ERROR;=0A+ hufGroup =3D bd->groups+sel= ectors[selector++];=0A+ base =3D hufGroup->base-1;=0A+ = limit =3D hufGroup->limit-1;=0A+ }=0A+ /* = Read next Huffman-coded symbol. */=0A+ /* Note: It is far cheaper = to read maxLen bits and=0A+ back up than it is to read = minLen bits and then an=0A+ additional bit at a time, = testing as we go.=0A+ Because there is a trailing last block = (with file=0A+ CRC), there is no danger of the overread = causing an=0A+ unexpected EOF for a valid compressed file. As = a=0A+ further optimization, we do the read inline=0A+ = (falling back to a call to get_bits if the buffer=0A+ = runs dry). The following (up to got_huff_bits:) is=0A+ = equivalent to j =3D get_bits(bd, hufGroup->maxLen);=0A+ */=0A+ = while (bd->inbufBitCount < hufGroup->maxLen) {=0A+ if = (bd->inbufPos =3D=3D bd->inbufCount) {=0A+ j = =3D get_bits(bd, hufGroup->maxLen);=0A+ goto = got_huff_bits;=0A+ }=0A+ bd->inbufBi= ts =3D=0A+ (bd->inbufBits << 8)|bd->inbuf[bd->= inbufPos++];=0A+ bd->inbufBitCount +=3D 8;=0A+ = };=0A+ bd->inbufBitCount -=3D hufGroup->maxLen;=0A+ j = =3D (bd->inbufBits >> bd->inbufBitCount)&=0A+ ((1 << = hufGroup->maxLen)-1);=0A+got_huff_bits:=0A+ /* Figure how how = many bits are in next symbol and=0A+ * unget extras */=0A+ = i =3D hufGroup->minLen;=0A+ while (j > limit[i])=0A+ = ++i;=0A+ bd->inbufBitCount +=3D (hufGroup->maxLen - = i);=0A+ /* Huffman decode value to get nextSym (with bounds = checking) */=0A+ if ((i > hufGroup->maxLen)=0A+ = || (((unsigned)(j =3D (j>>(hufGroup->maxLen-i))-base[i]))=0A+ = >=3D MAX_SYMBOLS))=0A+ return RETVAL_DATA_ERROR;= =0A+ nextSym =3D hufGroup->permute[j];=0A+ /* We have = now decoded the symbol, which indicates=0A+ either a new = literal byte, or a repeated run of the=0A+ most recent = literal byte. First, check if nextSym=0A+ indicates a = repeated run, and if so loop collecting=0A+ how many times = to repeat the last literal. */=0A+ if (((unsigned)nextSym) = <=3D SYMBOL_RUNB) { /* RUNA or RUNB */=0A+ /* If this = is the start of a new run, zero out=0A+ * counter */=0A+ = if (!runPos) {=0A+ runPos =3D = 1;=0A+ t =3D 0;=0A+ }=0A+ = /* Neat trick that saves 1 symbol: instead of=0A+ = or-ing 0 or 1 at each bit position, add 1=0A+ = or 2 instead. For example, 1011 is 1 << 0=0A+ + 1 << = 1 + 2 << 2. 1010 is 2 << 0 + 2 << 1=0A+ + 1 << = 2. You can make any bit pattern=0A+ that way using = 1 less symbol than the basic=0A+ or 0/1 method = (except all bits 0, which=0A+ would use no symbols, = but a run of length 0=0A+ doesn't mean anything = in this context).=0A+ Thus space is saved. */=0A+ = t +=3D (runPos << nextSym);=0A+ /* +runPos if = RUNA; +2*runPos if RUNB */=0A+=0A+ runPos <<=3D = 1;=0A+ continue;=0A+ }=0A+ /* When we = hit the first non-run symbol after a run,=0A+ we now know how = many times to repeat the last=0A+ literal, so append that = many copies to our buffer=0A+ of decoded symbols (dbuf) now. = (The last literal=0A+ used is the one at the head of the = mtfSymbol=0A+ array.) */=0A+ if (runPos) {=0A+ = runPos =3D 0;=0A+ if (dbufCount+t = >=3D dbufSize)=0A+ return RETVAL_DATA_ERROR;= =0A+=0A+ uc =3D symToByte[mtfSymbol[0]];=0A+ = byteCount[uc] +=3D t;=0A+ while (t--)=0A+ = dbuf[dbufCount++] =3D uc;=0A+ }=0A+ /* = Is this the terminating symbol? */=0A+ if (nextSym > symTotal)=0A+= break;=0A+ /* At this point, nextSym = indicates a new literal=0A+ character. Subtract one to get = the position in the=0A+ MTF array at which this literal is = currently to be=0A+ found. (Note that the result can't be = -1 or 0,=0A+ because 0 and 1 are RUNA and RUNB. But = another=0A+ instance of the first symbol in the mtf = array,=0A+ position 0, would have been handled as part of = a=0A+ run above. Therefore 1 unused mtf position minus 2=0A+ = non-literal nextSym values equals -1.) */=0A+ if = (dbufCount >=3D dbufSize)=0A+ return RETVAL_DATA_ERROR;= =0A+ i =3D nextSym - 1;=0A+ uc =3D mtfSymbol[i];=0A+ = /* Adjust the MTF array. Since we typically expect to=0A+ = *move only a small number of symbols, and are bound=0A+ = *by 256 in any case, using memmove here would=0A+ *typically= be bigger and slower due to function call=0A+ *overhead and = other assorted setup costs. */=0A+ do {=0A+ = mtfSymbol[i] =3D mtfSymbol[i-1];=0A+ } while (--i);=0A+ = mtfSymbol[0] =3D uc;=0A+ uc =3D symToByte[uc];=0A+ = /* We have our literal byte. Save it into dbuf. */=0A+ byteCount[u= c]++;=0A+ dbuf[dbufCount++] =3D (unsigned int)uc;=0A+ = }=0A+ /* At this point, we've read all the Huffman-coded symbols=0A+ = (and repeated runs) for this block from the input stream,=0A+ and = decoded them into the intermediate buffer. There are=0A+ = dbufCount many decoded bytes in dbuf[]. Now undo the=0A+ = Burrows-Wheeler transform on dbuf. See=0A+ http://dogma.net/markn/a= rticles/bwt/bwt.htm=0A+ */=0A+ /* Turn byteCount into cumulative = occurrence counts of 0 to n-1. */=0A+ j =3D 0;=0A+ for (i =3D 0; i < = 256; i++) {=0A+ k =3D j+byteCount[i];=0A+ byteCount[i= ] =3D j;=0A+ j =3D k;=0A+ }=0A+ /* Figure out what order = dbuf would be in if we sorted it. */=0A+ for (i =3D 0; i < = dbufCount; i++) {=0A+ uc =3D (unsigned char)(dbuf[i] & 0xff);=0A+= dbuf[byteCount[uc]] |=3D (i << 8);=0A+ byteCount[u= c]++;=0A+ }=0A+ /* Decode first byte by hand to initialize = "previous" byte.=0A+ Note that it doesn't get output, and if the = first three=0A+ characters are identical it doesn't qualify as a run = (hence=0A+ writeRunCountdown =3D 5). */=0A+ if (dbufCount) = {=0A+ if (origPtr >=3D dbufCount)=0A+ return = RETVAL_DATA_ERROR;=0A+ bd->writePos =3D dbuf[origPtr];=0A+ = bd->writeCurrent =3D (unsigned char)(bd->writePos&0xff);=0A+ = bd->writePos >>=3D 8;=0A+ bd->writeRunCountdown =3D 5;=0A+ = }=0A+ bd->writeCount =3D dbufCount;=0A+=0A+ return RETVAL_OK;=0A+}=0A+= =0A+/* Undo burrows-wheeler transform on intermediate buffer to produce = output.=0A+ If start_bunzip was initialized with out_fd =3D-1, then up = to len bytes of=0A+ data are written to outbuf. Return value is number = of bytes written or=0A+ error (all errors are negative numbers). If = out_fd!=3D-1, outbuf and len=0A+ are ignored, data is written to out_fd = and return is RETVAL_OK or error.=0A+*/=0A+=0A+static int INIT read_bunzip(= struct bunzip_data *bd, unsigned char *outbuf, int len)=0A+{=0A+ = const unsigned int *dbuf;=0A+ int pos, xcurrent, previous, gotcount;=0A+= =0A+ /* If last read was short due to end of file, return last block = now */=0A+ if (bd->writeCount < 0)=0A+ return bd->writeCou= nt;=0A+=0A+ gotcount =3D 0;=0A+ dbuf =3D bd->dbuf;=0A+ pos =3D = bd->writePos;=0A+ xcurrent =3D bd->writeCurrent;=0A+=0A+ /* We will = always have pending decoded data to write into the output=0A+ buffer = unless this is the very first call (in which case we haven't=0A+ = Huffman-decoded a block into the intermediate buffer yet). */=0A+=0A+ if = (bd->writeCopies) {=0A+ /* Inside the loop, writeCopies means = extra copies (beyond 1) */=0A+ --bd->writeCopies;=0A+ /* = Loop outputting bytes */=0A+ for (;;) {=0A+ /* = If the output buffer is full, snapshot=0A+ * state = and return */=0A+ if (gotcount >=3D len) {=0A+ = bd->writePos =3D pos;=0A+ = bd->writeCurrent =3D xcurrent;=0A+ bd->writeCo= pies++;=0A+ return len;=0A+ = }=0A+ /* Write next byte into output buffer, updating = CRC */=0A+ outbuf[gotcount++] =3D xcurrent;=0A+ = bd->writeCRC =3D (((bd->writeCRC) << 8)=0A+ = ^bd->crc32Table[((bd->writeCRC) >> 24)=0A+ = ^xcurrent]);=0A+ /* Loop now if we're outputting = multiple=0A+ * copies of this byte */=0A+ = if (bd->writeCopies) {=0A+ --bd->writeCopies;= =0A+ continue;=0A+ }=0A+decode= _next_byte:=0A+ if (!bd->writeCount--)=0A+ = break;=0A+ /* Follow sequence vector to = undo=0A+ * Burrows-Wheeler transform */=0A+ = previous =3D xcurrent;=0A+ pos =3D dbuf[pos];= =0A+ xcurrent =3D pos&0xff;=0A+ = pos >>=3D 8;=0A+ /* After 3 consecutive copies of = the same=0A+ byte, the 4th is a repeat count. We = count=0A+ down from 4 instead *of counting up = because=0A+ testing for non-zero is faster */=0A+ = if (--bd->writeRunCountdown) {=0A+ = if (xcurrent !=3D previous)=0A+ bd->writeRu= nCountdown =3D 4;=0A+ } else {=0A+ = /* We have a repeated run, this byte=0A+ * = indicates the count */=0A+ bd->writeCopies = =3D xcurrent;=0A+ xcurrent =3D previous;=0A+ = bd->writeRunCountdown =3D 5;=0A+ = /* Sometimes there are just 3 bytes=0A+ * = (run length 0) */=0A+ if (!bd->writeCopies)=0A+ = goto decode_next_byte;=0A+ = /* Subtract the 1 copy we'd output=0A+ * = anyway to get extras */=0A+ --bd->writeCopies;= =0A+ }=0A+ }=0A+ /* Decompression = of this block completed successfully */=0A+ bd->writeCRC =3D = ~bd->writeCRC;=0A+ bd->totalCRC =3D ((bd->totalCRC << 1) = |=0A+ (bd->totalCRC >> 31)) ^ bd->writeCRC;=0A+ = /* If this block had a CRC error, force file level CRC error. = */=0A+ if (bd->writeCRC !=3D bd->headerCRC) {=0A+ = bd->totalCRC =3D bd->headerCRC+1;=0A+ return RETVAL_LAST_= BLOCK;=0A+ }=0A+ }=0A+=0A+ /* Refill the intermediate = buffer by Huffman-decoding next=0A+ * block of input */=0A+ /* = (previous is just a convenient unused temp variable here) */=0A+ = previous =3D get_next_block(bd);=0A+ if (previous) {=0A+ = bd->writeCount =3D previous;=0A+ return (previous !=3D = RETVAL_LAST_BLOCK) ? previous : gotcount;=0A+ }=0A+ bd->writeCRC =3D = 0xffffffffUL;=0A+ pos =3D bd->writePos;=0A+ xcurrent =3D = bd->writeCurrent;=0A+ goto decode_next_byte;=0A+}=0A+=0A+static int INIT = nofill(void *buf, unsigned int len)=0A+{=0A+ return -1;=0A+}=0A+=0A+/* = Allocate the structure, read file header. If in_fd =3D=3D-1, inbuf must = contain=0A+ a complete bunzip file (len bytes long). If in_fd!=3D-1, = inbuf and len are=0A+ ignored, and data is read from file handle into = temporary buffer. */=0A+static int INIT start_bunzip(struct bunzip_data = **bdp, void *inbuf, int len,=0A+ int (*fill)(vo= id*, unsigned int))=0A+{=0A+ struct bunzip_data *bd;=0A+ unsigned = int i, j, c;=0A+ const unsigned int BZh0 =3D=0A+ (((unsigned= int)'B') << 24)+(((unsigned int)'Z') << 16)=0A+ +(((unsigne= d int)'h') << 8)+(unsigned int)'0';=0A+=0A+ /* Figure out how much = data to allocate */=0A+ i =3D sizeof(struct bunzip_data);=0A+=0A+ /* = Allocate bunzip_data. Most fields initialize to zero. */=0A+ bd =3D = *bdp =3D malloc(i);=0A+ memset(bd, 0, sizeof(struct bunzip_data));=0A+ /* = Setup input buffer */=0A+ bd->inbuf =3D inbuf;=0A+ bd->inbufCo= unt =3D len;=0A+ if (fill !=3D NULL)=0A+ bd->fill =3D = fill;=0A+ else=0A+ bd->fill =3D nofill;=0A+=0A+ /* = Init the CRC32 table (big endian) */=0A+ for (i =3D 0; i < 256; = i++) {=0A+ c =3D i << 24;=0A+ for (j =3D 8; j; = j--)=0A+ c =3D c&0x80000000 ? (c << 1)^0x04c11db7 : = (c << 1);=0A+ bd->crc32Table[i] =3D c;=0A+ }=0A+=0A+ /* = Ensure that file starts with "BZh['1'-'9']." */=0A+ i =3D get_bits(bd, = 32);=0A+ if (((unsigned int)(i-BZh0-1)) >=3D 9)=0A+ = return RETVAL_NOT_BZIP_DATA;=0A+=0A+ /* Fourth byte (ascii '1'-'9'), = indicates block size in units of 100k of=0A+ uncompressed data. = Allocate intermediate buffer for block. */=0A+ bd->dbufSize =3D 100000*(i-= BZh0);=0A+=0A+ bd->dbuf =3D large_malloc(bd->dbufSize * sizeof(int));=0A+ = return RETVAL_OK;=0A+}=0A+=0A+/* Example usage: decompress src_fd to = dst_fd. (Stops at end of bzip2 data,=0A+ not end of file.) */=0A+STATIC = int INIT bunzip2(unsigned char *buf, unsigned int len,=0A+ = int(*fill)(void*, unsigned int),=0A+ int(*flush)(void*, = unsigned int),=0A+ unsigned char *outbuf,=0A+ = unsigned int *pos,=0A+ void(*error_fn)(const char = *x))=0A+{=0A+ struct bunzip_data *bd;=0A+ int i =3D -1;=0A+ = unsigned char *inbuf;=0A+=0A+ set_error_fn(error_fn);=0A+ if = (flush)=0A+ outbuf =3D malloc(BZIP2_IOBUF_SIZE);=0A+=0A+ if = (!outbuf) {=0A+ error("Could not allocate output bufer");=0A+ = return -1;=0A+ }=0A+ if (buf)=0A+ inbuf =3D buf;=0A+ = else=0A+ inbuf =3D malloc(BZIP2_IOBUF_SIZE);=0A+ if = (!inbuf) {=0A+ error("Could not allocate input bufer");=0A+ = goto exit_0;=0A+ }=0A+ i =3D start_bunzip(&bd, inbuf, len, = fill);=0A+ if (!i) {=0A+ for (;;) {=0A+ i = =3D read_bunzip(bd, outbuf, BZIP2_IOBUF_SIZE);=0A+ if = (i <=3D 0)=0A+ break;=0A+ if = (!flush)=0A+ outbuf +=3D i;=0A+ = else=0A+ if (i !=3D flush(outbuf, i)) {=0A+ = i =3D RETVAL_UNEXPECTED_OUTPUT_EOF;=0A+ = break;=0A+ }=0A+ = }=0A+ }=0A+ /* Check CRC and release memory */=0A+ if (i =3D=3D = RETVAL_LAST_BLOCK) {=0A+ if (bd->headerCRC !=3D bd->totalCRC= )=0A+ error("Data integrity error when decompressing.");= =0A+ else=0A+ i =3D RETVAL_OK;=0A+ } = else if (i =3D=3D RETVAL_UNEXPECTED_OUTPUT_EOF) {=0A+ error("Comp= ressed file ends unexpectedly");=0A+ }=0A+ if (bd->dbuf)=0A+ = large_free(bd->dbuf);=0A+ if (pos)=0A+ *pos =3D bd->inbufP= os;=0A+ free(bd);=0A+ if (!buf)=0A+ free(inbuf);=0A+exit_0:=0A+= if (flush)=0A+ free(outbuf);=0A+ return i;=0A+}=0A--= - /dev/null 1970-01-01 00:00:00.000000000 +0000=0A+++ 2009-10-27/xen/co= mmon/decompress.c 2009-11-05 12:27:10.000000000 +0100=0A@@ -0,0 = +1,27 @@=0A+#include =0A+#include =0A+#include = =0A+#include =0A+#include =0A+= =0A+static void __init error(const char *msg)=0A+{=0A+ printk("%s\n", = msg);=0A+}=0A+=0A+int __init decompress(void *inbuf, unsigned int len, = void *outbuf)=0A+{=0A+#if 0 /* Not needed here yet. */=0A+ if ( len = >=3D 2 &&=0A+ (!memcmp(inbuf, "\037\213", 2) || !memcmp(inbuf, = "\037\236", 2)) )=0A+ return gunzip(inbuf, len, NULL, NULL, outbuf, = NULL, error);=0A+#endif=0A+=0A+ if ( len >=3D 3 && !memcmp(inbuf, = "\x42\x5a\x68", 3) )=0A+ return bunzip2(inbuf, len, NULL, NULL, = outbuf, NULL, error);=0A+=0A+ if ( len >=3D 2 && !memcmp(inbuf, = "\135\000", 2) )=0A+ return unlzma(inbuf, len, NULL, NULL, outbuf, = NULL, error);=0A+=0A+ return 1;=0A+}=0A--- /dev/null 1970-01-01 = 00:00:00.000000000 +0000=0A+++ 2009-10-27/xen/common/decompress.h = 2009-11-05 15:21:52.000000000 +0100=0A@@ -0,0 +1,19 @@=0A+#include = =0A+#include =0A+#include =0A+= #include =0A+#include =0A+#include = =0A+#include =0A+=0A+#define STATIC=0A+#define INIT = __init=0A+=0A+static void(*__initdata error)(const char *);=0A+#define = set_error_fn(x) error =3D x;=0A+=0A+#define malloc xmalloc_bytes=0A+#define= free xfree=0A+=0A+#define large_malloc xmalloc_bytes=0A+#define large_free= xfree=0A--- /dev/null 1970-01-01 00:00:00.000000000 +0000=0A+++ = 2009-10-27/xen/common/unlzma.c 2009-11-05 12:45:37.000000000 +0100=0A@@ = -0,0 +1,647 @@=0A+/* Lzma decompressor for Linux kernel. Shamelessly = snarfed=0A+ * from busybox 1.1.1=0A+ *=0A+ * Linux kernel adaptation=0A+ * = Copyright (C) 2006 Alain < alain@knaff.lu >=0A+ *=0A+ * Based on small = lzma deflate implementation/Small range coder=0A+ * implementation for = lzma.=0A+ * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >=0A+ = *=0A+ * Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/= )=0A+ * Copyright (C) 1999-2005 Igor Pavlov=0A+ *=0A+ * Copyrights of the = parts, see headers below.=0A+ *=0A+ *=0A+ * This program is free software; = you can redistribute it and/or=0A+ * modify it under the terms of the GNU = Lesser General Public=0A+ * License as published by the Free Software = Foundation; either=0A+ * version 2.1 of the License, or (at your option) = any later version.=0A+ *=0A+ * This program is distributed in the hope = that it will be useful,=0A+ * but WITHOUT ANY WARRANTY; without even the = implied warranty of=0A+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR = PURPOSE. See the GNU=0A+ * Lesser General Public License for more = details.=0A+ *=0A+ * You should have received a copy of the GNU Lesser = General Public=0A+ * License along with this library; if not, write to the = Free Software=0A+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, = MA 02110-1301 USA=0A+ */=0A+=0A+#include "decompress.h"=0A+=0A+#define = MIN(a, b) (((a) < (b)) ? (a) : (b))=0A+=0A+static long long INIT read_int(u= nsigned char *ptr, int size)=0A+{=0A+ int i;=0A+ long long ret =3D = 0;=0A+=0A+ for (i =3D 0; i < size; i++)=0A+ ret =3D = (ret << 8) | ptr[size-i-1];=0A+ return ret;=0A+}=0A+=0A+#define ENDIAN_CONV= ERT(x) \=0A+ x =3D (typeof(x))read_int((unsigned char *)&x, sizeof(x))=0A+= =0A+=0A+/* Small range coder implementation for lzma.=0A+ * Copyright (C) = 2006 Aurelien Jacobs < aurel@gnuage.org >=0A+ *=0A+ * Based on LzmaDecode.= c from the LZMA SDK 4.22 (http://www.7-zip.org/)=0A+ * Copyright (c) = 1999-2005 Igor Pavlov=0A+ */=0A+=0A+#include =0A+=0A+#defi= ne LZMA_IOBUF_SIZE 0x10000=0A+=0A+struct rc {=0A+ int (*fill)(void*, = unsigned int);=0A+ uint8_t *ptr;=0A+ uint8_t *buffer;=0A+ = uint8_t *buffer_end;=0A+ int buffer_size;=0A+ uint32_t code;=0A+ = uint32_t range;=0A+ uint32_t bound;=0A+};=0A+=0A+=0A+#define RC_TOP_BIT= S 24=0A+#define RC_MOVE_BITS 5=0A+#define RC_MODEL_TOTAL_BITS 11=0A+=0A+=0A= +static int nofill(void *buffer, unsigned int len)=0A+{=0A+ return = -1;=0A+}=0A+=0A+/* Called twice: once at startup and once in rc_normalize()= */=0A+static void INIT rc_read(struct rc *rc)=0A+{=0A+ rc->buffer_size = =3D rc->fill((char *)rc->buffer, LZMA_IOBUF_SIZE);=0A+ if (rc->buffer_size= <=3D 0)=0A+ error("unexpected EOF");=0A+ rc->ptr =3D = rc->buffer;=0A+ rc->buffer_end =3D rc->buffer + rc->buffer_size;=0A+}=0A+= =0A+/* Called once */=0A+static inline void INIT rc_init(struct rc = *rc,=0A+ int (*fill)(void*, unsigned = int),=0A+ unsigned char *buffer, int = buffer_size)=0A+{=0A+ if (fill)=0A+ rc->fill =3D fill;=0A+ = else=0A+ rc->fill =3D nofill;=0A+ rc->buffer =3D = (uint8_t *)buffer;=0A+ rc->buffer_size =3D buffer_size;=0A+ rc->buffer_= end =3D rc->buffer + rc->buffer_size;=0A+ rc->ptr =3D rc->buffer;=0A+= =0A+ rc->code =3D 0;=0A+ rc->range =3D 0xFFFFFFFF;=0A+}=0A+=0A+stati= c inline void INIT rc_init_code(struct rc *rc)=0A+{=0A+ int i;=0A+=0A+ = for (i =3D 0; i < 5; i++) {=0A+ if (rc->ptr >=3D rc->buffer_end)=0A= + rc_read(rc);=0A+ rc->code =3D = (rc->code << 8) | *rc->ptr++;=0A+ }=0A+}=0A+=0A+=0A+/* Called once. = TODO: bb_maybe_free() */=0A+static inline void INIT rc_free(struct rc = *rc)=0A+{=0A+ free(rc->buffer);=0A+}=0A+=0A+/* Called twice, but one = callsite is in inline'd rc_is_bit_0_helper() */=0A+static void INIT = rc_do_normalize(struct rc *rc)=0A+{=0A+ if (rc->ptr >=3D rc->buffer_end)=0A= + rc_read(rc);=0A+ rc->range <<=3D 8;=0A+ rc->code = =3D (rc->code << 8) | *rc->ptr++;=0A+}=0A+static inline void INIT = rc_normalize(struct rc *rc)=0A+{=0A+ if (rc->range < (1 << RC_TOP_BITS))= =0A+ rc_do_normalize(rc);=0A+}=0A+=0A+/* Called 9 times = */=0A+/* Why rc_is_bit_0_helper exists?=0A+ *Because we want to always = expose (rc->code < rc->bound) to optimizer=0A+ */=0A+static inline = uint32_t INIT rc_is_bit_0_helper(struct rc *rc, uint16_t *p)=0A+{=0A+ = rc_normalize(rc);=0A+ rc->bound =3D *p * (rc->range >> RC_MODEL_TOTAL_BIT= S);=0A+ return rc->bound;=0A+}=0A+static inline int INIT rc_is_bit_0(struct= rc *rc, uint16_t *p)=0A+{=0A+ uint32_t t =3D rc_is_bit_0_helper(rc, = p);=0A+ return rc->code < t;=0A+}=0A+=0A+/* Called ~10 times, but very = small, thus inlined */=0A+static inline void INIT rc_update_bit_0(struct = rc *rc, uint16_t *p)=0A+{=0A+ rc->range =3D rc->bound;=0A+ *p +=3D = ((1 << RC_MODEL_TOTAL_BITS) - *p) >> RC_MOVE_BITS;=0A+}=0A+static inline = void rc_update_bit_1(struct rc *rc, uint16_t *p)=0A+{=0A+ rc->range = -=3D rc->bound;=0A+ rc->code -=3D rc->bound;=0A+ *p -=3D *p >> = RC_MOVE_BITS;=0A+}=0A+=0A+/* Called 4 times in unlzma loop */=0A+static = int INIT rc_get_bit(struct rc *rc, uint16_t *p, int *symbol)=0A+{=0A+ if = (rc_is_bit_0(rc, p)) {=0A+ rc_update_bit_0(rc, p);=0A+ = *symbol *=3D 2;=0A+ return 0;=0A+ } else {=0A+ = rc_update_bit_1(rc, p);=0A+ *symbol =3D *symbol * 2 + 1;=0A+ = return 1;=0A+ }=0A+}=0A+=0A+/* Called once */=0A+static inline = int INIT rc_direct_bit(struct rc *rc)=0A+{=0A+ rc_normalize(rc);=0A+ = rc->range >>=3D 1;=0A+ if (rc->code >=3D rc->range) {=0A+ = rc->code -=3D rc->range;=0A+ return 1;=0A+ }=0A+ return = 0;=0A+}=0A+=0A+/* Called twice */=0A+static inline void INIT=0A+rc_bit_tree= _decode(struct rc *rc, uint16_t *p, int num_levels, int *symbol)=0A+{=0A+ = int i =3D num_levels;=0A+=0A+ *symbol =3D 1;=0A+ while (i--)=0A+ = rc_get_bit(rc, p + *symbol, symbol);=0A+ *symbol -=3D 1 << = num_levels;=0A+}=0A+=0A+=0A+/*=0A+ * Small lzma deflate implementation.=0A+= * Copyright (C) 2006 Aurelien Jacobs < aurel@gnuage.org >=0A+ *=0A+ * = Based on LzmaDecode.c from the LZMA SDK 4.22 (http://www.7-zip.org/)=0A+ * = Copyright (C) 1999-2005 Igor Pavlov=0A+ */=0A+=0A+=0A+struct lzma_header = {=0A+ uint8_t pos;=0A+ uint32_t dict_size;=0A+ uint64_t = dst_size;=0A+} __attribute__ ((packed)) ;=0A+=0A+=0A+#define LZMA_BASE_SIZE= 1846=0A+#define LZMA_LIT_SIZE 768=0A+=0A+#define LZMA_NUM_POS_BITS_MAX = 4=0A+=0A+#define LZMA_LEN_NUM_LOW_BITS 3=0A+#define LZMA_LEN_NUM_MID_BITS = 3=0A+#define LZMA_LEN_NUM_HIGH_BITS 8=0A+=0A+#define LZMA_LEN_CHOICE = 0=0A+#define LZMA_LEN_CHOICE_2 (LZMA_LEN_CHOICE + 1)=0A+#define LZMA_LEN_LO= W (LZMA_LEN_CHOICE_2 + 1)=0A+#define LZMA_LEN_MID (LZMA_LEN_LOW \=0A+ = + (1 << (LZMA_NUM_POS_BITS_MAX + LZMA_LEN_NUM_LOW_BITS)))=0A+#define = LZMA_LEN_HIGH (LZMA_LEN_MID \=0A+ +(1 << (LZMA_NUM_POS= _BITS_MAX + LZMA_LEN_NUM_MID_BITS)))=0A+#define LZMA_NUM_LEN_PROBS = (LZMA_LEN_HIGH + (1 << LZMA_LEN_NUM_HIGH_BITS))=0A+=0A+#define LZMA_NUM_STA= TES 12=0A+#define LZMA_NUM_LIT_STATES 7=0A+=0A+#define LZMA_START_POS_MODEL= _INDEX 4=0A+#define LZMA_END_POS_MODEL_INDEX 14=0A+#define LZMA_NUM_FULL_DI= STANCES (1 << (LZMA_END_POS_MODEL_INDEX >> 1))=0A+=0A+#define LZMA_NUM_POS_= SLOT_BITS 6=0A+#define LZMA_NUM_LEN_TO_POS_STATES 4=0A+=0A+#define = LZMA_NUM_ALIGN_BITS 4=0A+=0A+#define LZMA_MATCH_MIN_LEN 2=0A+=0A+#define = LZMA_IS_MATCH 0=0A+#define LZMA_IS_REP (LZMA_IS_MATCH + (LZMA_NUM_STATES = << LZMA_NUM_POS_BITS_MAX))=0A+#define LZMA_IS_REP_G0 (LZMA_IS_REP + = LZMA_NUM_STATES)=0A+#define LZMA_IS_REP_G1 (LZMA_IS_REP_G0 + LZMA_NUM_STATE= S)=0A+#define LZMA_IS_REP_G2 (LZMA_IS_REP_G1 + LZMA_NUM_STATES)=0A+#define = LZMA_IS_REP_0_LONG (LZMA_IS_REP_G2 + LZMA_NUM_STATES)=0A+#define LZMA_POS_S= LOT (LZMA_IS_REP_0_LONG \=0A+ + (LZMA_NUM_STATES << = LZMA_NUM_POS_BITS_MAX))=0A+#define LZMA_SPEC_POS (LZMA_POS_SLOT \=0A+ = +(LZMA_NUM_LEN_TO_POS_STATES << LZMA_NUM_POS_SLOT_BITS))=0A+#define = LZMA_ALIGN (LZMA_SPEC_POS \=0A+ + LZMA_NUM_FULL_DISTANCES - = LZMA_END_POS_MODEL_INDEX)=0A+#define LZMA_LEN_CODER (LZMA_ALIGN + (1 << = LZMA_NUM_ALIGN_BITS))=0A+#define LZMA_REP_LEN_CODER (LZMA_LEN_CODER + = LZMA_NUM_LEN_PROBS)=0A+#define LZMA_LITERAL (LZMA_REP_LEN_CODER + = LZMA_NUM_LEN_PROBS)=0A+=0A+=0A+struct writer {=0A+ uint8_t *buffer;=0A= + uint8_t previous_byte;=0A+ size_t buffer_pos;=0A+ int = bufsize;=0A+ size_t global_pos;=0A+ int(*flush)(void*, unsigned = int);=0A+ struct lzma_header *header;=0A+};=0A+=0A+struct cstate = {=0A+ int state;=0A+ uint32_t rep0, rep1, rep2, rep3;=0A+};=0A+=0A+stati= c inline size_t INIT get_pos(struct writer *wr)=0A+{=0A+ return=0A+ = wr->global_pos + wr->buffer_pos;=0A+}=0A+=0A+static inline uint8_t = INIT peek_old_byte(struct writer *wr,=0A+ = uint32_t offs)=0A+{=0A+ if (!wr->flush) {=0A+ int32_t = pos;=0A+ while (offs > wr->header->dict_size)=0A+ = offs -=3D wr->header->dict_size;=0A+ pos =3D wr->buffer_= pos - offs;=0A+ return wr->buffer[pos];=0A+ } else {=0A+ = uint32_t pos =3D wr->buffer_pos - offs;=0A+ while (pos >=3D = wr->header->dict_size)=0A+ pos +=3D wr->header->dict_s= ize;=0A+ return wr->buffer[pos];=0A+ }=0A+=0A+}=0A+=0A+s= tatic inline void INIT write_byte(struct writer *wr, uint8_t byte)=0A+{=0A+= wr->buffer[wr->buffer_pos++] =3D wr->previous_byte =3D byte;=0A+ = if (wr->flush && wr->buffer_pos =3D=3D wr->header->dict_size) {=0A+ = wr->buffer_pos =3D 0;=0A+ wr->global_pos +=3D wr->header->dic= t_size;=0A+ wr->flush((char *)wr->buffer, wr->header->dict_size= );=0A+ }=0A+}=0A+=0A+=0A+static inline void INIT copy_byte(struct writer = *wr, uint32_t offs)=0A+{=0A+ write_byte(wr, peek_old_byte(wr, offs));=0A= +}=0A+=0A+static inline void INIT copy_bytes(struct writer *wr,=0A+ = uint32_t rep0, int len)=0A+{=0A+ do {=0A+ = copy_byte(wr, rep0);=0A+ len--;=0A+ } while = (len !=3D 0 && wr->buffer_pos < wr->header->dst_size);=0A+}=0A+=0A+static = inline void INIT process_bit0(struct writer *wr, struct rc *rc,=0A+ = struct cstate *cst, uint16_t *p,=0A+ = int pos_state, uint16_t *prob,=0A+ = int lc, uint32_t literal_pos_mask) {=0A+ int mi =3D 1;=0A+ = rc_update_bit_0(rc, prob);=0A+ prob =3D (p + LZMA_LITERAL +=0A+ = (LZMA_LIT_SIZE=0A+ * (((get_pos(wr) & literal_pos_mask) << = lc)=0A+ + (wr->previous_byte >> (8 - lc))))=0A+ = );=0A+=0A+ if (cst->state >=3D LZMA_NUM_LIT_STATES) {=0A+ = int match_byte =3D peek_old_byte(wr, cst->rep0);=0A+ do {=0A+ = int bit;=0A+ uint16_t *prob_lit;=0A+=0A+= match_byte <<=3D 1;=0A+ bit =3D = match_byte & 0x100;=0A+ prob_lit =3D prob + 0x100 + bit + = mi;=0A+ if (rc_get_bit(rc, prob_lit, &mi)) {=0A+ = if (!bit)=0A+ break;=0A+ = } else {=0A+ if (bit)=0A+ = break;=0A+ }=0A+ } = while (mi < 0x100);=0A+ }=0A+ while (mi < 0x100) {=0A+ = uint16_t *prob_lit =3D prob + mi;=0A+ rc_get_bit(rc, prob_lit, = &mi);=0A+ }=0A+ write_byte(wr, mi);=0A+ if (cst->state < 4)=0A+ = cst->state =3D 0;=0A+ else if (cst->state < 10)=0A+ cst->state = -=3D 3;=0A+ else=0A+ cst->state -=3D 6;=0A+}=0A+=0A+stat= ic inline void INIT process_bit1(struct writer *wr, struct rc *rc,=0A+ = struct cstate *cst, uint16_t *p,=0A+ = int pos_state, uint16_t *prob) {=0A+ int = offset;=0A+ uint16_t *prob_len;=0A+ int num_bits;=0A+ int = len;=0A+=0A+ rc_update_bit_1(rc, prob);=0A+ prob =3D p + LZMA_IS_REP + = cst->state;=0A+ if (rc_is_bit_0(rc, prob)) {=0A+ rc_update_b= it_0(rc, prob);=0A+ cst->rep3 =3D cst->rep2;=0A+ = cst->rep2 =3D cst->rep1;=0A+ cst->rep1 =3D cst->rep0;=0A+ = cst->state =3D cst->state < LZMA_NUM_LIT_STATES ? 0 : 3;=0A+ = prob =3D p + LZMA_LEN_CODER;=0A+ } else {=0A+ rc_update_b= it_1(rc, prob);=0A+ prob =3D p + LZMA_IS_REP_G0 + cst->state;= =0A+ if (rc_is_bit_0(rc, prob)) {=0A+ = rc_update_bit_0(rc, prob);=0A+ prob =3D (p + LZMA_IS_REP_0= _LONG=0A+ + (cst->state <<=0A+ = LZMA_NUM_POS_BITS_MAX) +=0A+ pos_state);= =0A+ if (rc_is_bit_0(rc, prob)) {=0A+ = rc_update_bit_0(rc, prob);=0A+=0A+ = cst->state =3D cst->state < LZMA_NUM_LIT_STATES ?=0A+ = 9 : 11;=0A+ copy_byte(wr, cst->rep0);= =0A+ return;=0A+ } else = {=0A+ rc_update_bit_1(rc, prob);=0A+ = }=0A+ } else {=0A+ uint32_t distance;=0A+=0A+ = rc_update_bit_1(rc, prob);=0A+ prob =3D p = + LZMA_IS_REP_G1 + cst->state;=0A+ if (rc_is_bit_0(rc,= prob)) {=0A+ rc_update_bit_0(rc, prob);=0A+ = distance =3D cst->rep1;=0A+ } else = {=0A+ rc_update_bit_1(rc, prob);=0A+ = prob =3D p + LZMA_IS_REP_G2 + cst->state;=0A+ = if (rc_is_bit_0(rc, prob)) {=0A+ = rc_update_bit_0(rc, prob);=0A+ distance = =3D cst->rep2;=0A+ } else {=0A+ = rc_update_bit_1(rc, prob);=0A+ = distance =3D cst->rep3;=0A+ cst->rep3 = =3D cst->rep2;=0A+ }=0A+ = cst->rep2 =3D cst->rep1;=0A+ }=0A+ = cst->rep1 =3D cst->rep0;=0A+ cst->rep0 =3D distance;=0A+= }=0A+ cst->state =3D cst->state < LZMA_NUM_LIT_ST= ATES ? 8 : 11;=0A+ prob =3D p + LZMA_REP_LEN_CODER;=0A+ = }=0A+=0A+ prob_len =3D prob + LZMA_LEN_CHOICE;=0A+ if = (rc_is_bit_0(rc, prob_len)) {=0A+ rc_update_bit_0(rc, = prob_len);=0A+ prob_len =3D (prob + LZMA_LEN_LOW=0A+ = + (pos_state <<=0A+ LZMA_LEN_NUM_LOW_BITS));=0A+= offset =3D 0;=0A+ num_bits =3D LZMA_LEN_NUM_L= OW_BITS;=0A+ } else {=0A+ rc_update_bit_1(rc, prob_len);=0A+ = prob_len =3D prob + LZMA_LEN_CHOICE_2;=0A+ if = (rc_is_bit_0(rc, prob_len)) {=0A+ rc_update_bit_0(rc,= prob_len);=0A+ prob_len =3D (prob + LZMA_LEN_MID=0A+ = + (pos_state <<=0A+ = LZMA_LEN_NUM_MID_BITS));=0A+ offset =3D 1 << LZMA_LEN_NU= M_LOW_BITS;=0A+ num_bits =3D LZMA_LEN_NUM_MID_BITS;=0A+ = } else {=0A+ rc_update_bit_1(rc, prob_len);=0A+ = prob_len =3D prob + LZMA_LEN_HIGH;=0A+ offset =3D = ((1 << LZMA_LEN_NUM_LOW_BITS)=0A+ + (1 << = LZMA_LEN_NUM_MID_BITS));=0A+ num_bits =3D LZMA_LEN_NUM_H= IGH_BITS;=0A+ }=0A+ }=0A+=0A+ rc_bit_tree_decode(rc, = prob_len, num_bits, &len);=0A+ len +=3D offset;=0A+=0A+ if = (cst->state < 4) {=0A+ int pos_slot;=0A+=0A+ cst->state = +=3D LZMA_NUM_LIT_STATES;=0A+ prob =3D=0A+ p = + LZMA_POS_SLOT +=0A+ ((len <=0A+ = LZMA_NUM_LEN_TO_POS_STATES ? len :=0A+ LZMA_NUM_LEN_TO_P= OS_STATES - 1)=0A+ << LZMA_NUM_POS_SLOT_BITS);=0A+ = rc_bit_tree_decode(rc, prob,=0A+ = LZMA_NUM_POS_SLOT_BITS,=0A+ &pos_slot);=0A+ = if (pos_slot >=3D LZMA_START_POS_MODEL_INDEX) {=0A+ = int i, mi;=0A+ num_bits =3D (pos_slot >> 1) - 1;=0A+ = cst->rep0 =3D 2 | (pos_slot & 1);=0A+ if = (pos_slot < LZMA_END_POS_MODEL_INDEX) {=0A+ = cst->rep0 <<=3D num_bits;=0A+ prob =3D p + = LZMA_SPEC_POS +=0A+ cst->rep0 - = pos_slot - 1;=0A+ } else {=0A+ = num_bits -=3D LZMA_NUM_ALIGN_BITS;=0A+ while = (num_bits--)=0A+ cst->rep0 =3D = (cst->rep0 << 1) |=0A+ rc_direct_b= it(rc);=0A+ prob =3D p + LZMA_ALIGN;=0A+ = cst->rep0 <<=3D LZMA_NUM_ALIGN_BITS;=0A+ = num_bits =3D LZMA_NUM_ALIGN_BITS;=0A+ }=0A+ = i =3D 1;=0A+ mi =3D 1;=0A+ = while (num_bits--) {=0A+ if (rc_get_bit(rc, = prob + mi, &mi))=0A+ cst->rep0 |=3D = i;=0A+ i <<=3D 1;=0A+ }=0A+ = } else=0A+ cst->rep0 =3D pos_slot;=0A+ if = (++(cst->rep0) =3D=3D 0)=0A+ return;=0A+ }=0A+=0A+ = len +=3D LZMA_MATCH_MIN_LEN;=0A+=0A+ copy_bytes(wr, cst->rep0, = len);=0A+}=0A+=0A+=0A+=0A+STATIC inline int INIT unlzma(unsigned char = *buf, unsigned int in_len,=0A+ int(*fill)(void*, = unsigned int),=0A+ int(*flush)(void*, unsigned = int),=0A+ unsigned char *output,=0A+ = unsigned int *posp,=0A+ void(*error_f= n)(const char *x)=0A+ )=0A+{=0A+ struct lzma_header header;=0A+ = int lc, pb, lp;=0A+ uint32_t pos_state_mask;=0A+ uint32_t literal_po= s_mask;=0A+ uint16_t *p;=0A+ int num_probs;=0A+ struct rc = rc;=0A+ int i, mi;=0A+ struct writer wr;=0A+ struct cstate cst;=0A+ = unsigned char *inbuf;=0A+ int ret =3D -1;=0A+=0A+ set_error_fn(error_= fn);=0A+=0A+ if (buf)=0A+ inbuf =3D buf;=0A+ else=0A+ = inbuf =3D malloc(LZMA_IOBUF_SIZE);=0A+ if (!inbuf) {=0A+ = error("Could not allocate input bufer");=0A+ goto exit_0;=0A+ = }=0A+=0A+ cst.state =3D 0;=0A+ cst.rep0 =3D cst.rep1 =3D cst.rep2 = =3D cst.rep3 =3D 1;=0A+=0A+ wr.header =3D &header;=0A+ wr.flush = =3D flush;=0A+ wr.global_pos =3D 0;=0A+ wr.previous_byte =3D = 0;=0A+ wr.buffer_pos =3D 0;=0A+=0A+ rc_init(&rc, fill, inbuf, = in_len);=0A+=0A+ for (i =3D 0; i < sizeof(header); i++) {=0A+ = if (rc.ptr >=3D rc.buffer_end)=0A+ rc_read(&rc);=0A+ = ((unsigned char *)&header)[i] =3D *rc.ptr++;=0A+ }=0A+=0A+ = if (header.pos >=3D (9 * 5 * 5))=0A+ error("bad header");=0A+=0A= + mi =3D 0;=0A+ lc =3D header.pos;=0A+ while (lc >=3D 9) {=0A+ = mi++;=0A+ lc -=3D 9;=0A+ }=0A+ pb =3D 0;=0A+ lp =3D = mi;=0A+ while (lp >=3D 5) {=0A+ pb++;=0A+ lp -=3D = 5;=0A+ }=0A+ pos_state_mask =3D (1 << pb) - 1;=0A+ literal_pos_mask = =3D (1 << lp) - 1;=0A+=0A+ ENDIAN_CONVERT(header.dict_size);=0A+ = ENDIAN_CONVERT(header.dst_size);=0A+=0A+ if (header.dict_size = =3D=3D 0)=0A+ header.dict_size =3D 1;=0A+=0A+ if (output)=0A+ = wr.buffer =3D output;=0A+ else {=0A+ wr.bufsize =3D = MIN(header.dst_size, header.dict_size);=0A+ wr.buffer =3D = large_malloc(wr.bufsize);=0A+ }=0A+ if (wr.buffer =3D=3D NULL)=0A+ = goto exit_1;=0A+=0A+ num_probs =3D LZMA_BASE_SIZE + (LZMA_LIT_SIZE << = (lc + lp));=0A+ p =3D (uint16_t *) large_malloc(num_probs * sizeof(*p));=0A= + if (p =3D=3D 0)=0A+ goto exit_2;=0A+ num_probs = =3D LZMA_LITERAL + (LZMA_LIT_SIZE << (lc + lp));=0A+ for (i =3D 0; i < = num_probs; i++)=0A+ p[i] =3D (1 << RC_MODEL_TOTAL_BITS) >> = 1;=0A+=0A+ rc_init_code(&rc);=0A+=0A+ while (get_pos(&wr) < = header.dst_size) {=0A+ int pos_state =3D get_pos(&wr) & = pos_state_mask;=0A+ uint16_t *prob =3D p + LZMA_IS_MATCH +=0A+ = (cst.state << LZMA_NUM_POS_BITS_MAX) + pos_state;=0A+ = if (rc_is_bit_0(&rc, prob))=0A+ process_bit0(&wr, &rc, = &cst, p, pos_state, prob,=0A+ lc, literal_po= s_mask);=0A+ else {=0A+ process_bit1(&wr, = &rc, &cst, p, pos_state, prob);=0A+ if (cst.rep0 = =3D=3D 0)=0A+ break;=0A+ }=0A+ = }=0A+=0A+ if (posp)=0A+ *posp =3D rc.ptr-rc.buffer;=0A+ if = (wr.flush)=0A+ wr.flush(wr.buffer, wr.buffer_pos);=0A+ ret =3D = 0;=0A+ large_free(p);=0A+exit_2:=0A+ if (!output)=0A+ = large_free(wr.buffer);=0A+exit_1:=0A+ if (!buf)=0A+ free(inbuf)= ;=0A+exit_0:=0A+ return ret;=0A+}=0A--- /dev/null 1970-01-01 = 00:00:00.000000000 +0000=0A+++ 2009-10-27/xen/include/xen/decompress.h = 2009-11-05 12:27:44.000000000 +0100=0A@@ -0,0 +1,38 @@=0A+#ifndef = __XEN_GENERIC_H=0A+#define __XEN_GENERIC_H=0A+=0A+typedef int decompress_fn= (unsigned char *inbuf, unsigned int len,=0A+ int = (*fill)(void*, unsigned int),=0A+ int (*flush)(voi= d*, unsigned int),=0A+ unsigned char *outbuf, = unsigned int *posp,=0A+ void (*error)(const char = *x));=0A+=0A+/* inbuf - input buffer=0A+ * len - len of pre-read = data in inbuf=0A+ * fill - function to fill inbuf when empty=0A+ * = flush - function to write out outbuf=0A+ * outbuf - output buffer=0A+ * = posp - if non-null, input position (number of bytes read) will be=0A+ * = returned here=0A+ * error - error reporting function=0A+ *=0A+ = * If len !=3D 0, inbuf should contain all the necessary input data, and = fill=0A+ * should be NULL=0A+ * If len =3D 0, inbuf can be NULL, in which = case the decompressor will allocate=0A+ * the input buffer. If inbuf !=3D = NULL it must be at least XXX_IOBUF_SIZE bytes.=0A+ * fill will be called = (repeatedly...) to read data, at most XXX_IOBUF_SIZE=0A+ * bytes should be = read per call. Replace XXX with the appropriate decompressor=0A+ * name, = i.e. LZMA_IOBUF_SIZE.=0A+ *=0A+ * If flush =3D NULL, outbuf must be large = enough to buffer all the expected=0A+ * output. If flush !=3D NULL, the = output buffer will be allocated by the=0A+ * decompressor (outbuf =3D = NULL), and the flush function will be called to=0A+ * flush the output = buffer at the appropriate time (decompressor and stream=0A+ * dependent).= =0A+ */=0A+=0A+decompress_fn bunzip2, unlzma;=0A+=0A+int decompress(void = *inbuf, unsigned int len, void *outbuf);=0A+=0A+#endif=0A --=__Part163DA326.0__= Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel --=__Part163DA326.0__=--