23 May
2006
23 May
'06
2:43 a.m.
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