[LinuxBIOS] selection of compression algorithm
yhlu
yinghailu at gmail.com
Tue May 23 07:10:39 CEST 2006
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 <c-d.hailfinger.devel.2006 at gmx.net> 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
> linuxbios at linuxbios.org
> http://www.openbios.org/mailman/listinfo/linuxbios
>
>
More information about the coreboot
mailing list