Re: [LinuxBIOS] selection of compression algorithm

[Carl-Daniel Hailfinger]

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?

How much RAM is the decompressor allowed to use?

Regards,
Carl-Daniel

[LinuxBIOS] selection of compression algorithm

[yhlu]

8k bytes is too big...

unrv2b uses about several bytes for pointers only..

YH

On 5/21/06, 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?
>
> How much RAM is the decompressor allowed to use?
>
> Regards,
> Carl-Daniel
> --
> http://www.hailfinger.org/

[LinuxBIOS] selection of compression algorithm

[Stefan Reinauer]

* yhlu  [060522 05:49]:
> 8k bytes is too big...

Its a lot smaller than the 80k you save compared to nrv2b, so the result
is still 72kb smaller.
> unrv2b uses about several bytes for pointers only..

[LinuxBIOS] selection of compression algorithm

[Ronald G Minnich]

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.
> 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.

ron

[LinuxBIOS] selection of compression algorithm

[Carl-Daniel Hailfinger]

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

[LinuxBIOS] selection of compression algorithm

[yhlu]

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  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:
> GNU Lesser General Public License (GNU LGPL)
> 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:
> GNU Lesser General Public License (GNU LGPL)
> 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] selection of compression algorithm

[Stefan Reinauer]

* yhlu  [060523 07:10]:
> Good.
> We may need CONFIG_COMPRESS_TYPE to select nrv2b or lzma..or none

Maybe it could even replace CONFIG_COMPRESS and
CONFIG_COMPRESS_ROM_STREAM?
> Add one compress type before compressed bin. 00: for none. 0x11:
>
> for nrv2b or 0x22:  for lzma.

We could do this all at compile time so we don't need any "runtime
infrastructure"

Stefan

[LinuxBIOS] selection of compression algorithm

[yhlu]

I may only want to lzma for payload if we can sqush tiny kernel and
initrd in 1M with LinuxBIOS.

I may need to use nrv2b for linuxbios_ram.rom and
linuxbios_ap_code.rom. These too can share the code in car stage. and
code in cache can not have too much space for lzma properties array.

YH

On 5/22/06, Stefan Reinauer  wrote:
> yhlu  [060523 07:10]:
> > Good.
> > We may need CONFIG_COMPRESS_TYPE to select nrv2b or lzma..or none
>
> Maybe it could even replace CONFIG_COMPRESS and
> CONFIG_COMPRESS_ROM_STREAM?
> > Add one compress type before compressed bin. 00: for none. 0x11:
> >
> > for nrv2b or 0x22:  for lzma.
>
> We could do this all at compile time so we don't need any "runtime
> infrastructure"
>
> Stefan

[LinuxBIOS] selection of compression algorithm

[Stefan Reinauer]

* yhlu  [060523 11:26]:
> I may only want to lzma for payload if we can sqush tiny kernel and
> initrd in 1M with LinuxBIOS.

Thats why we all would want to see this, yes. But using nrv2b if lzma is
so much more efficient makes not much sense in any other case either.
> I may need to use nrv2b for linuxbios_ram.rom and
> linuxbios_ap_code.rom.

* What's linuxbios_ap_code.rom?
> These too can share the code in car stage. and
> code in cache can not have too much space for lzma properties array.

When we're uncompressing, we do have memory. So cache sizes are no 
restriction at this point anymore.

[LinuxBIOS] selection of compression algorithm

[yhlu]

linuxbios_apc.rom is the code for ap. The code is in it's own cache.
So BSP is executing the code in ROM and RAM, and at the same time the
APs executing code in cache.

The AP uncompress the linuxbios_apc.rom from rom to it's cache before
jump it. At that time the RAM on BSP is ready already.

YH

On 5/23/06, Stefan Reinauer  wrote:
> yhlu  [060523 11:26]:
> > I may only want to lzma for payload if we can sqush tiny kernel and
> > initrd in 1M with LinuxBIOS.
>
> Thats why we all would want to see this, yes. But using nrv2b if lzma is
> so much more efficient makes not much sense in any other case either.
> > I may need to use nrv2b for linuxbios_ram.rom and
> > linuxbios_ap_code.rom.
> What's linuxbios_ap_code.rom?
> > These too can share the code in car stage. and
> > code in cache can not have too much space for lzma properties array.
>
> When we're uncompressing, we do have memory. So cache sizes are no
> restriction at this point anymore.

[LinuxBIOS] selection of compression algorithm

[Carl-Daniel Hailfinger]

yhlu wrote:
> linuxbios_apc.rom is the code for ap. The code is in it's own cache.
> So BSP is executing the code in ROM and RAM, and at the same time the
> APs executing code in cache.
>
> The AP uncompress the linuxbios_apc.rom from rom to it's cache before
> jump it. At that time the RAM on BSP is ready already.

Sorry, can you please explain what AP, APC and BSP are?

Regards,
Carl-Daniel

[LinuxBIOS] selection of compression algorithm

[yhlu]

AP: application processor. it mean all processor except BSP
BSP: bootstrap processor. the first cpu is running, and it will start APs.
APC:  I call the code that is running on AP only.

YH

On 5/23/06, Carl-Daniel Hailfinger  wrote:
> yhlu wrote:
> > linuxbios_apc.rom is the code for ap. The code is in it's own cache.
> > So BSP is executing the code in ROM and RAM, and at the same time the
> > APs executing code in cache.
> >
> > The AP uncompress the linuxbios_apc.rom from rom to it's cache before
> > jump it. At that time the RAM on BSP is ready already.
>
> Sorry, can you please explain what AP, APC and BSP are?
>
> Regards,
> Carl-Daniel
> --
> http://www.hailfinger.org/

[LinuxBIOS] selection of compression algorithm

[Beneo]

Hi YH,

I try to build amd/serengeti_cheetah, but I get a message like this:
    gcc -m32 -nostdlib -nostartfiles -static -o linuxbios_apc -T 
/export/1/new/src/config/linuxbios_apc.ld linuxbios_apc.o
    /usr/bin/ld: linuxbios_apc is too big
    collect2: ld returned 1 exit status
    make[1]: *** [linuxbios_apc] Error 1

The DCACHE_SIZE is set at 0x8000, linuxbios_apc.o has a size about 20K.

Do you know where I did wrong?  I have gcc 3.2.2.

Thanks

Beneo

----- Original Message ----- 
From: "yhlu" 
To: "Stefan Reinauer" 
Cc: "Carl-Daniel Hailfinger" ; 
"LinuxBIOS" 
Sent: Tuesday, May 23, 2006 12:53 PM
Subject: Re: [LinuxBIOS] selection of compression algorithm

linuxbios_apc.rom is the code for ap. The code is in it's own cache.
So BSP is executing the code in ROM and RAM, and at the same time the
APs executing code in cache.

The AP uncompress the linuxbios_apc.rom from rom to it's cache before
jump it. At that time the RAM on BSP is ready already.

YH

On 5/23/06, Stefan Reinauer  wrote:
> yhlu  [060523 11:26]:
> > I may only want to lzma for payload if we can sqush tiny kernel and
> > initrd in 1M with LinuxBIOS.
>
> Thats why we all would want to see this, yes. But using nrv2b if lzma is
> so much more efficient makes not much sense in any other case either.
> > I may need to use nrv2b for linuxbios_ram.rom and
> > linuxbios_ap_code.rom.
> What's linuxbios_ap_code.rom?
> > These too can share the code in car stage. and
> > code in cache can not have too much space for lzma properties array.
>
> When we're uncompressing, we do have memory. So cache sizes are no
> restriction at this point anymore.