Good. 1. We may need CONFIG_COMPRESS_TYPE to select nrv2b or lzma..or none 2. Add one compress type before compressed bin. 00: for none. 0x11: for nrv2b or 0x22: for lzma.
YH On 5/22/06, Carl-Daniel Hailfinger <[EMAIL PROTECTED]> wrote: > Ronald G Minnich wrote: > > Carl-Daniel Hailfinger wrote: > >> yhlu wrote: > >> > >>> then how about the lines for 7z uncompress code? > >>> > >>> YH > >> > >> Working on it. 7z decompressor is really small (8 kb compiled on > >> i386) and written in ISO C (1884 lines of code), but compressor is > >> big and written in C++. > >> > >> Does it still make sense to try to use 7z? > > > > yes, this is the perfect tradeoff. Highly complex, compute-intensive > > compressor and simple, small decompressor. Exactly what we want. > > I managed to trim this down further. > 4 kb compiled code on i386, 497 lines of C code. > > >> How much RAM is the decompressor allowed to use? > > > > for the romcc section, you have about 6 32-bit words (or so). for the > > gcc section, you have all of memory more or less. > > OK, then we can call lzma decompressor only from the gcc section. > It needs to allocate some scratch space (between 5228 and 6295148 bytes, > default value is 15980 bytes) besides src and dst. The size of the > scratch space can be determined at compile time, so we can create > compressed images which only need 5228 bytes scratch space. > What is the best way to handle this? Dynamic allocation or fixed buffer? > > Size comparison for OLPC target and small kernel: > 843910 vmlinux.bin > 437684 vmlinux.bin.nrv2b > 377334 vmlinux.bin.lzma.smallscratchspace > 373445 vmlinux.bin.lzma.default > 46832 linuxbios_ram.bin > 23923 linuxbios_ram.bin.nrv2b > 21829 linuxbios_ram.bin.lzma.smallscratchspace > 21738 linuxbios_ram.bin.lzma.default > > The .lzma.smallscratchspace needs 5228 bytes scratch space, > the .lzma.default needs 15980 bytes scratch space. > > lzma decompression can be called the same way as nrv2b decompression: > static unsigned long unlzma(unsigned char * src, unsigned char * dst); > > Patch is attached. Please note that this patch doesn't change anything, > it only adds infrastructure. If you want a patch that builds most > targets (especially OLPC) with lzma, just ask. I have it sitting on > my hard drive. > > To use lzma compression, download the LZMA SDK. > > curl -O http://switch.dl.sourceforge.net/sourceforge/sevenzip/lzma442.tar.bz2 > mkdir lzma442 > cd lzma442 > tar xfj ../lzma442.tar.bz2 > cd C/7zip/Compress/LZMA_Alone/ > make -f makefile.gcc > cp -a lzma /usr/local/bin/ > > Regards, > Carl-Daniel > -- > http://www.hailfinger.org/ > > > diff -urN LinuxBIOSv2-2310/src/arch/i386/Config.lb > LinuxBIOSv2-2310-lzma/src/arch/i386/Config.lb > --- LinuxBIOSv2-2310/src/arch/i386/Config.lb 2006-05-18 19:29:27.000000000 > +0200 > +++ LinuxBIOSv2-2310-lzma/src/arch/i386/Config.lb 2006-05-23 > 03:17:08.000000000 +0200 > @@ -13,6 +13,10 @@ > action "mcopy -o linuxbios.rom a:" > end > > +makerule lzma > + action "test -f /usr/local/bin/lzma" > +end > + > makerule nrv2b > depends "$(TOP)/util/nrv2b/nrv2b.c" > action "$(HOSTCC) -O2 -DENCODE -DDECODE -DMAIN -DVERBOSE -DNDEBUG > -DBITSIZE=32 -DENDIAN=0 $< -o $@" > @@ -23,6 +27,11 @@ > action "cp $< $@" > end > > +makerule payload.lzma > + depends "$(PAYLOAD) lzma" > + action "lzma e $(PAYLOAD) $@" > +end > + > makerule payload.nrv2b > depends "$(PAYLOAD) nrv2b" > action "./nrv2b e $(PAYLOAD) $@" > diff -urN LinuxBIOSv2-2310/src/config/Config.lb > LinuxBIOSv2-2310-lzma/src/config/Config.lb > --- LinuxBIOSv2-2310/src/config/Config.lb 2006-05-18 19:29:24.000000000 > +0200 > +++ LinuxBIOSv2-2310-lzma/src/config/Config.lb 2006-05-23 03:15:20.000000000 > +0200 > @@ -53,6 +53,11 @@ > action "$(OBJCOPY) -O binary $< $@" > end > > +makerule linuxbios_ram.lzma > + depends "linuxbios_ram.bin lzma" > + action "lzma e $< $@" > +end > + > makerule linuxbios_ram.nrv2b > depends "linuxbios_ram.bin nrv2b" > action "./nrv2b e $< $@" > diff -urN LinuxBIOSv2-2310/src/lib/lzma.c LinuxBIOSv2-2310-lzma/src/lib/lzma.c > --- LinuxBIOSv2-2310/src/lib/lzma.c 1970-01-01 01:00:00.000000000 +0100 > +++ LinuxBIOSv2-2310-lzma/src/lib/lzma.c 2006-05-23 03:18:34.000000000 > +0200 > @@ -0,0 +1,32 @@ > +/* > + > +LinuxBIOS interface to memory-saving variant of LZMA decoder > +(C)opyright 2006 Carl-Daniel Hailfinger > +Released under the GNU GPL > + > +*/ > + > +#include "lzmadecode.c" > + > +static unsigned long unlzma(unsigned char * src, unsigned char * dst) > +{ > + unsigned char properties[LZMA_PROPERTIES_SIZE]; > + UInt32 outSize; > + SizeT inProcessed; > + SizeT outProcessed; > + int res; > + CLzmaDecoderState state; > + > + memcpy(properties, src, LZMA_PROPERTIES_SIZE); > + outSize = *(UInt32 *)(src + LZMA_PROPERTIES_SIZE); > + if (LzmaDecodeProperties(&state.Properties, properties, > LZMA_PROPERTIES_SIZE) != LZMA_RESULT_OK) { > + printk_warning("Incorrect stream properties\n"); > + } > + state.Probs = (CProb *)malloc(LzmaGetNumProbs(&state.Properties) * > sizeof(CProb)); > + res = LzmaDecode(&state, src + LZMA_PROPERTIES_SIZE + 8, > (SizeT)0xffffffff, &inProcessed, > + dst, outSize, &outProcessed); > + if (res != 0) { > + printk_warning("Decoding error = %d\n", res); > + } > + return outSize; > +} > diff -urN LinuxBIOSv2-2310/src/lib/lzmadecode.c > LinuxBIOSv2-2310-lzma/src/lib/lzmadecode.c > --- LinuxBIOSv2-2310/src/lib/lzmadecode.c 1970-01-01 01:00:00.000000000 > +0100 > +++ LinuxBIOSv2-2310-lzma/src/lib/lzmadecode.c 2006-05-23 03:13:01.000000000 > +0200 > @@ -0,0 +1,398 @@ > +/* > + LzmaDecode.c > + LZMA Decoder (optimized for Speed version) > + > + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) > + http://www.7-zip.org/ > + > + LZMA SDK is licensed under two licenses: > + 1) GNU Lesser General Public License (GNU LGPL) > + 2) Common Public License (CPL) > + It means that you can select one of these two licenses and > + follow rules of that license. > + > + SPECIAL EXCEPTION: > + Igor Pavlov, as the author of this Code, expressly permits you to > + statically or dynamically link your Code (or bind by name) to the > + interfaces of this file without subjecting your linked Code to the > + terms of the CPL or GNU LGPL. Any modifications or additions > + to this file, however, are subject to the LGPL or CPL terms. > +*/ > + > +#include "lzmadecode.h" > + > +#define kNumTopBits 24 > +#define kTopValue ((UInt32)1 << kNumTopBits) > + > +#define kNumBitModelTotalBits 11 > +#define kBitModelTotal (1 << kNumBitModelTotalBits) > +#define kNumMoveBits 5 > + > +#define RC_READ_BYTE (*Buffer++) > + > +#define RC_INIT2 Code = 0; Range = 0xFFFFFFFF; \ > + { int i; for(i = 0; i < 5; i++) { RC_TEST; Code = (Code << 8) | > RC_READ_BYTE; }} > + > + > +#define RC_TEST { if (Buffer == BufferLim) return LZMA_RESULT_DATA_ERROR; } > + > +#define RC_INIT(buffer, bufferSize) Buffer = buffer; BufferLim = buffer + > bufferSize; RC_INIT2 > + > + > +#define RC_NORMALIZE if (Range < kTopValue) { RC_TEST; Range <<= 8; Code = > (Code << 8) | RC_READ_BYTE; } > + > +#define IfBit0(p) RC_NORMALIZE; bound = (Range >> kNumBitModelTotalBits) * > *(p); if (Code < bound) > +#define UpdateBit0(p) Range = bound; *(p) += (kBitModelTotal - *(p)) >> > kNumMoveBits; > +#define UpdateBit1(p) Range -= bound; Code -= bound; *(p) -= (*(p)) >> > kNumMoveBits; > + > +#define RC_GET_BIT2(p, mi, A0, A1) IfBit0(p) \ > + { UpdateBit0(p); mi <<= 1; A0; } else \ > + { UpdateBit1(p); mi = (mi + mi) + 1; A1; } > + > +#define RC_GET_BIT(p, mi) RC_GET_BIT2(p, mi, ; , ;) > + > +#define RangeDecoderBitTreeDecode(probs, numLevels, res) \ > + { int i = numLevels; res = 1; \ > + do { CProb *p = probs + res; RC_GET_BIT(p, res) } while(--i != 0); \ > + res -= (1 << numLevels); } > + > + > +#define kNumPosBitsMax 4 > +#define kNumPosStatesMax (1 << kNumPosBitsMax) > + > +#define kLenNumLowBits 3 > +#define kLenNumLowSymbols (1 << kLenNumLowBits) > +#define kLenNumMidBits 3 > +#define kLenNumMidSymbols (1 << kLenNumMidBits) > +#define kLenNumHighBits 8 > +#define kLenNumHighSymbols (1 << kLenNumHighBits) > + > +#define LenChoice 0 > +#define LenChoice2 (LenChoice + 1) > +#define LenLow (LenChoice2 + 1) > +#define LenMid (LenLow + (kNumPosStatesMax << kLenNumLowBits)) > +#define LenHigh (LenMid + (kNumPosStatesMax << kLenNumMidBits)) > +#define kNumLenProbs (LenHigh + kLenNumHighSymbols) > + > + > +#define kNumStates 12 > +#define kNumLitStates 7 > + > +#define kStartPosModelIndex 4 > +#define kEndPosModelIndex 14 > +#define kNumFullDistances (1 << (kEndPosModelIndex >> 1)) > + > +#define kNumPosSlotBits 6 > +#define kNumLenToPosStates 4 > + > +#define kNumAlignBits 4 > +#define kAlignTableSize (1 << kNumAlignBits) > + > +#define kMatchMinLen 2 > + > +#define IsMatch 0 > +#define IsRep (IsMatch + (kNumStates << kNumPosBitsMax)) > +#define IsRepG0 (IsRep + kNumStates) > +#define IsRepG1 (IsRepG0 + kNumStates) > +#define IsRepG2 (IsRepG1 + kNumStates) > +#define IsRep0Long (IsRepG2 + kNumStates) > +#define PosSlot (IsRep0Long + (kNumStates << kNumPosBitsMax)) > +#define SpecPos (PosSlot + (kNumLenToPosStates << kNumPosSlotBits)) > +#define Align (SpecPos + kNumFullDistances - kEndPosModelIndex) > +#define LenCoder (Align + kAlignTableSize) > +#define RepLenCoder (LenCoder + kNumLenProbs) > +#define Literal (RepLenCoder + kNumLenProbs) > + > +#if Literal != LZMA_BASE_SIZE > +StopCompilingDueBUG > +#endif > + > +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char > *propsData, int size) > +{ > + unsigned char prop0; > + if (size < LZMA_PROPERTIES_SIZE) > + return LZMA_RESULT_DATA_ERROR; > + prop0 = propsData[0]; > + if (prop0 >= (9 * 5 * 5)) > + return LZMA_RESULT_DATA_ERROR; > + { > + for (propsRes->pb = 0; prop0 >= (9 * 5); propsRes->pb++, prop0 -= (9 * > 5)); > + for (propsRes->lp = 0; prop0 >= 9; propsRes->lp++, prop0 -= 9); > + propsRes->lc = prop0; > + /* > + unsigned char remainder = (unsigned char)(prop0 / 9); > + propsRes->lc = prop0 % 9; > + propsRes->pb = remainder / 5; > + propsRes->lp = remainder % 5; > + */ > + } > + > + return LZMA_RESULT_OK; > +} > + > +#define kLzmaStreamWasFinishedId (-1) > + > +int LzmaDecode(CLzmaDecoderState *vs, > + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, > + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed) > +{ > + CProb *p = vs->Probs; > + SizeT nowPos = 0; > + Byte previousByte = 0; > + UInt32 posStateMask = (1 << (vs->Properties.pb)) - 1; > + UInt32 literalPosMask = (1 << (vs->Properties.lp)) - 1; > + int lc = vs->Properties.lc; > + > + > + int state = 0; > + UInt32 rep0 = 1, rep1 = 1, rep2 = 1, rep3 = 1; > + int len = 0; > + const Byte *Buffer; > + const Byte *BufferLim; > + UInt32 Range; > + UInt32 Code; > + > + *inSizeProcessed = 0; > + *outSizeProcessed = 0; > + > + { > + UInt32 i; > + UInt32 numProbs = Literal + ((UInt32)LZMA_LIT_SIZE << (lc + > vs->Properties.lp)); > + for (i = 0; i < numProbs; i++) > + p[i] = kBitModelTotal >> 1; > + } > + > + RC_INIT(inStream, inSize); > + > + > + while(nowPos < outSize) > + { > + CProb *prob; > + UInt32 bound; > + int posState = (int)( > + (nowPos > + ) > + & posStateMask); > + > + prob = p + IsMatch + (state << kNumPosBitsMax) + posState; > + IfBit0(prob) > + { > + int symbol = 1; > + UpdateBit0(prob) > + prob = p + Literal + (LZMA_LIT_SIZE * > + ((( > + (nowPos > + ) > + & literalPosMask) << lc) + (previousByte >> (8 - lc)))); > + > + if (state >= kNumLitStates) > + { > + int matchByte; > + matchByte = outStream[nowPos - rep0]; > + do > + { > + int bit; > + CProb *probLit; > + matchByte <<= 1; > + bit = (matchByte & 0x100); > + probLit = prob + 0x100 + bit + symbol; > + RC_GET_BIT2(probLit, symbol, if (bit != 0) break, if (bit == 0) > break) > + } > + while (symbol < 0x100); > + } > + while (symbol < 0x100) > + { > + CProb *probLit = prob + symbol; > + RC_GET_BIT(probLit, symbol) > + } > + previousByte = (Byte)symbol; > + > + outStream[nowPos++] = previousByte; > + if (state < 4) state = 0; > + else if (state < 10) state -= 3; > + else state -= 6; > + } > + else > + { > + UpdateBit1(prob); > + prob = p + IsRep + state; > + IfBit0(prob) > + { > + UpdateBit0(prob); > + rep3 = rep2; > + rep2 = rep1; > + rep1 = rep0; > + state = state < kNumLitStates ? 0 : 3; > + prob = p + LenCoder; > + } > + else > + { > + UpdateBit1(prob); > + prob = p + IsRepG0 + state; > + IfBit0(prob) > + { > + UpdateBit0(prob); > + prob = p + IsRep0Long + (state << kNumPosBitsMax) + posState; > + IfBit0(prob) > + { > + UpdateBit0(prob); > + > + if (nowPos == 0) > + return LZMA_RESULT_DATA_ERROR; > + > + state = state < kNumLitStates ? 9 : 11; > + previousByte = outStream[nowPos - rep0]; > + outStream[nowPos++] = previousByte; > + > + continue; > + } > + else > + { > + UpdateBit1(prob); > + } > + } > + else > + { > + UInt32 distance; > + UpdateBit1(prob); > + prob = p + IsRepG1 + state; > + IfBit0(prob) > + { > + UpdateBit0(prob); > + distance = rep1; > + } > + else > + { > + UpdateBit1(prob); > + prob = p + IsRepG2 + state; > + IfBit0(prob) > + { > + UpdateBit0(prob); > + distance = rep2; > + } > + else > + { > + UpdateBit1(prob); > + distance = rep3; > + rep3 = rep2; > + } > + rep2 = rep1; > + } > + rep1 = rep0; > + rep0 = distance; > + } > + state = state < kNumLitStates ? 8 : 11; > + prob = p + RepLenCoder; > + } > + { > + int numBits, offset; > + CProb *probLen = prob + LenChoice; > + IfBit0(probLen) > + { > + UpdateBit0(probLen); > + probLen = prob + LenLow + (posState << kLenNumLowBits); > + offset = 0; > + numBits = kLenNumLowBits; > + } > + else > + { > + UpdateBit1(probLen); > + probLen = prob + LenChoice2; > + IfBit0(probLen) > + { > + UpdateBit0(probLen); > + probLen = prob + LenMid + (posState << kLenNumMidBits); > + offset = kLenNumLowSymbols; > + numBits = kLenNumMidBits; > + } > + else > + { > + UpdateBit1(probLen); > + probLen = prob + LenHigh; > + offset = kLenNumLowSymbols + kLenNumMidSymbols; > + numBits = kLenNumHighBits; > + } > + } > + RangeDecoderBitTreeDecode(probLen, numBits, len); > + len += offset; > + } > + > + if (state < 4) > + { > + int posSlot; > + state += kNumLitStates; > + prob = p + PosSlot + > + ((len < kNumLenToPosStates ? len : kNumLenToPosStates - 1) << > + kNumPosSlotBits); > + RangeDecoderBitTreeDecode(prob, kNumPosSlotBits, posSlot); > + if (posSlot >= kStartPosModelIndex) > + { > + int numDirectBits = ((posSlot >> 1) - 1); > + rep0 = (2 | ((UInt32)posSlot & 1)); > + if (posSlot < kEndPosModelIndex) > + { > + rep0 <<= numDirectBits; > + prob = p + SpecPos + rep0 - posSlot - 1; > + } > + else > + { > + numDirectBits -= kNumAlignBits; > + do > + { > + RC_NORMALIZE > + Range >>= 1; > + rep0 <<= 1; > + if (Code >= Range) > + { > + Code -= Range; > + rep0 |= 1; > + } > + } > + while (--numDirectBits != 0); > + prob = p + Align; > + rep0 <<= kNumAlignBits; > + numDirectBits = kNumAlignBits; > + } > + { > + int i = 1; > + int mi = 1; > + do > + { > + CProb *prob3 = prob + mi; > + RC_GET_BIT2(prob3, mi, ; , rep0 |= i); > + i <<= 1; > + } > + while(--numDirectBits != 0); > + } > + } > + else > + rep0 = posSlot; > + if (++rep0 == (UInt32)(0)) > + { > + /* it's for stream version */ > + len = kLzmaStreamWasFinishedId; > + break; > + } > + } > + > + len += kMatchMinLen; > + if (rep0 > nowPos) > + return LZMA_RESULT_DATA_ERROR; > + > + > + do > + { > + previousByte = outStream[nowPos - rep0]; > + len--; > + outStream[nowPos++] = previousByte; > + } > + while(len != 0 && nowPos < outSize); > + } > + } > + RC_NORMALIZE; > + > + > + *inSizeProcessed = (SizeT)(Buffer - inStream); > + *outSizeProcessed = nowPos; > + return LZMA_RESULT_OK; > +} > diff -urN LinuxBIOSv2-2310/src/lib/lzmadecode.h > LinuxBIOSv2-2310-lzma/src/lib/lzmadecode.h > --- LinuxBIOSv2-2310/src/lib/lzmadecode.h 1970-01-01 01:00:00.000000000 > +0100 > +++ LinuxBIOSv2-2310-lzma/src/lib/lzmadecode.h 2006-05-23 03:13:01.000000000 > +0200 > @@ -0,0 +1,67 @@ > +/* > + LzmaDecode.h > + LZMA Decoder interface > + > + LZMA SDK 4.40 Copyright (c) 1999-2006 Igor Pavlov (2006-05-01) > + http://www.7-zip.org/ > + > + LZMA SDK is licensed under two licenses: > + 1) GNU Lesser General Public License (GNU LGPL) > + 2) Common Public License (CPL) > + It means that you can select one of these two licenses and > + follow rules of that license. > + > + SPECIAL EXCEPTION: > + Igor Pavlov, as the author of this code, expressly permits you to > + statically or dynamically link your code (or bind by name) to the > + interfaces of this file without subjecting your linked code to the > + terms of the CPL or GNU LGPL. Any modifications or additions > + to this file, however, are subject to the LGPL or CPL terms. > +*/ > + > +#ifndef __LZMADECODE_H > +#define __LZMADECODE_H > + > +typedef unsigned char Byte; > +typedef unsigned short UInt16; > +typedef unsigned int UInt32; > +typedef UInt32 SizeT; > + > +#define CProb UInt16 > + > +#define LZMA_RESULT_OK 0 > +#define LZMA_RESULT_DATA_ERROR 1 > + > + > +#define LZMA_BASE_SIZE 1846 > +#define LZMA_LIT_SIZE 768 > + > +#define LZMA_PROPERTIES_SIZE 5 > + > +typedef struct _CLzmaProperties > +{ > + int lc; > + int lp; > + int pb; > +}CLzmaProperties; > + > +int LzmaDecodeProperties(CLzmaProperties *propsRes, const unsigned char > *propsData, int size); > + > +#define LzmaGetNumProbs(Properties) (LZMA_BASE_SIZE + (LZMA_LIT_SIZE << > ((Properties)->lc + (Properties)->lp))) > + > +#define kLzmaNeedInitId (-2) > + > +typedef struct _CLzmaDecoderState > +{ > + CLzmaProperties Properties; > + CProb *Probs; > + > + > +} CLzmaDecoderState; > + > + > +int LzmaDecode(CLzmaDecoderState *vs, > + const unsigned char *inStream, SizeT inSize, SizeT *inSizeProcessed, > + unsigned char *outStream, SizeT outSize, SizeT *outSizeProcessed); > + > +#endif > > > -- > linuxbios mailing list > [email protected] > http://www.openbios.org/mailman/listinfo/linuxbios > > -- linuxbios mailing list [email protected] http://www.openbios.org/mailman/listinfo/linuxbios
