Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-pascal / 2010-01

LZMA Algorithm fails on 64bit

16 messages · 4 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Matthias Klumpp

Hello!
I use the LZMA-SDK for Pascal to compress files. ( http://www.birtles.org.uk/programming/ )
I can compress files on 64bit and 32bit architecture. But if I try to decompress LZMA-Compressed files on AMD64, it fails. I use code [-1-] to decompress files. The action works perfectly on i386, but if I compile it for AMD64 usi9ng FPC 2.4.0 it fails throwing the exception 'Error in data stream'. It fails at code [-2-] in TLZMADecoder.Code because pos0 is greater than nowPos64. I'am trying now for about half a week to solve this problem, but I don't have any idea now, why this happens on AMD64. The code does not use any pointers which could be wrong, but maybe a type conversion from Int64 to Int32...
Does anyone know why the code fails to work? Is this a bug in FPC? Kind regards
Matthias Klumpp

################################################### ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
CodeSequence [-1-]:
-----

var inStream:TBufferedFS;
    outStream:TBufferedFS;
    decoder: TLZMADecoder;
    properties:array[0..4] of byte;
    filesize,outSize:Int64;
    i: Integer;
    v: byte;
const propertiessize=5;
begin
 if not FileExists(ipkfile) then Exception.Create('IPK file does not
exists!');
 try
  inStream:=TBufferedFS.Create(ipkfile, fmOpenRead or fmShareDenyNone);
 try
  outStream:=TBufferedFS.Create(workdir+'ipktar.tar', fmCreate);
  decoder:=TLZMADecoder.Create;
  inStream.position:=0;
    with decoder do
    begin
      if inStream.read(properties, propertiesSize)  propertiesSize then
       raise Exception.Create('input .lzma file is too short');
      if not SetDecoderProperties(properties) then
       raise Exception.Create('Incorrect stream properties');
      outSize := 0;
      for i := 0 to 7 do
      begin
       v := inStream.ReadByte;
       if v < 0 then
        raise Exception.Create('Can''t read stream size');
       outSize := outSize or v shl (8 * i);
      end;
      if not Code(inStream, outStream, outSize) then
       raise Exception.Create('Error in data stream');
     end;
     decoder.Free;
 finally
  outStream.Free;
 end;
 finally
  inStream.Free;
 end;
end;

################################################### ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
CodeSequence [-2-]:
-----

if (rep0 >= nowPos64) or (rep0 >= m_DictionarySizeCheck) then
      begin
         m_OutWindow.Flush();
         result:=false;
         exit;
      end;

###################################################

Reply by email

Jonas Maebe
to Matthias Klumpp
Does anyone know why the code fails to work?

Not really, but at least the following is will be evaluated differently on 32 and 64 bit platforms:

Show quoted text 39 lines
################################################### ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ CodeSequence [-1-]: ----- var inStream:TBufferedFS; outStream:TBufferedFS; decoder: TLZMADecoder; properties:array[0..4] of byte; filesize,outSize:Int64; i: Integer; v: byte; const propertiessize=5; begin if not FileExists(ipkfile) then Exception.Create('IPK file does not exists!'); try inStream:=TBufferedFS.Create(ipkfile, fmOpenRead or fmShareDenyNone); try outStream:=TBufferedFS.Create(workdir+'ipktar.tar', fmCreate); decoder:=TLZMADecoder.Create; inStream.position:=0; with decoder do begin if inStream.read(properties, propertiesSize) propertiesSize then raise Exception.Create('input .lzma file is too short'); if not SetDecoderProperties(properties) then raise Exception.Create('Incorrect stream properties'); outSize := 0; for i := 0 to 7 do begin v := inStream.ReadByte; if v < 0 then raise Exception.Create('Can''t read stream size'); outSize := outSize or v shl (8 * i);

v is a byte, i is a longint (integer in Delphi mode). Outsize is an int64.

On a 32 bit platform, "v shl (8 * i)" will be evaluated as 32 bit. This means that the upper 32 bits of the result of that expression will be discarded before the "or" operation is performed. On a 64 bit platform, that entire expression will be evaluated using 64 bit arithmetic.

Jonas

Reply by email

Matthias Klumpp
to Jonas Maebe
Jonas Maebe wrote
> Does anyone know why the code fails to work? Not really, but at least the following is will be evaluated differently

on

32 and 64 bit platforms: [...] v is a byte, i is a longint (integer in Delphi mode). Outsize is an

int64.

Show quoted text 6 lines
On a 32 bit platform, "v shl (8 * i)" will be evaluated as 32 bit. This means that the upper 32 bits of the result of that expression will be discarded before the "or" operation is performed. On a 64 bit platform, that entire expression will be evaluated using 64 bit arithmetic.

Hi!
Maybe the is the reason why it fails, cause the compression does not do operations like this. How do I have to change the expression to make it work on 32bit and 64bit?
Thanks!
Matthias

Reply by email

Jonas Maebe
to Matthias Klumpp
Matthias Klumpp wrote 20 lines
On Sat, 23 Jan 2010 14:19:23 +0100, Jonas Maebe wrote: >> Does anyone know why the code fails to work? > > Not really, but at least the following is will be evaluated differently > on 32 and 64 bit platforms: > > [...] > v is a byte, i is a longint (integer in Delphi mode). Outsize is an > int64. > > On a 32 bit platform, "v shl (8 * i)" will be evaluated as 32 bit. This > means that the upper 32 bits of the result of that expression will be > discarded before the "or" operation is performed. On a 64 bit platform, > that entire expression will be evaluated using 64 bit arithmetic. > Hi! Maybe the is the reason why it fails, cause the compression does not do operations like this. How do I have to change the expression to make it work on 32bit and 64bit?

I think the code there is currently actually only correct on 64 bit platforms and wrong on 32 bit platforms: it seems that it should read an int64 in little endian format and converts it on-the-fly to the native endianess, but that currently only happens correctly on 64 bit platforms. I was also wrong about what it does on 32 bit platforms, because that depends on the used architecture. On PowerPC, it will indeed throw away the upper 32 bits as I described above. On i386, it will however result in something like "v shl ((8 *i) and 31)".

I don't think there is a quick fix. Someone who knows what is going on has to go through it and properly fix it. Hacking the code you posted will only result in hiding a bug, and you will probably still get more errors elsewhere.

Jonas

Reply by email

Matthias Klumpp
to Jonas Maebe
I think the code there is currently actually only correct on 64 bit platforms and wrong on 32 bit platforms: it seems that it should read an int64 in little endian format and converts it on-the-fly to the native endianess, but that currently only happens correctly on 64 bit platforms.

I

was also wrong about what it does on 32 bit platforms, because that

depends

on the used architecture. On PowerPC, it will indeed throw away the upper 32 bits as I described above. On i386, it will however result in

something

like "v shl ((8 *i) and 31)".

I checked it: The old version and your code produce exactly the same value on 64bit and 32bit. There is no difference between both results.

I don't think there is a quick fix. Someone who knows what is going on

has

to go through it and properly fix it. Hacking the code you posted will

only

result in hiding a bug, and you will probably still get more errors elsewhere.

The problem is that no Pascal developer knows this code. It was translated from Java code.
Can you imagine another difference between 64bit and 32bit which may cause those error? The bitshifts result in the same value on 32bit and 64bit... Kind regards
Matthias Klumpp

Reply by email

JoshyFun
to Matthias Klumpp

Hello FPC-Pascal,

Monday, January 25, 2010, 1:29:48 PM, you wrote:

MK> The problem is that no Pascal developer knows this code. It was translated MK> from Java code.
MK> Can you imagine another difference between 64bit and 32bit which may cause MK> those error? The bitshifts result in the same value on 32bit and 64bit... MK> Kind regards
MK> Matthias Klumpp

The stream is compressed with 32 bits version ? Or are the 64 bits compressed files the ones that fail to be decompressed in 64 bits also ?

So the question a 32 bits compressed LZMA can be decompressed with 32 bits "decode", and the same stream decompressed with the 64 bits version ?

Best regards, JoshyFun

Reply by email

Jonas Maebe
to Matthias Klumpp: I depends something I checked it: The old version and your code produce exactly the same…
Matthias Klumpp wrote 14 lines
> I think the code there is currently actually only correct on 64 bit > platforms and wrong on 32 bit platforms: it seems that it should read an > int64 in little endian format and converts it on-the-fly to the native > endianess, but that currently only happens correctly on 64 bit platforms. > I > was also wrong about what it does on 32 bit platforms, because that > depends > on the used architecture. On PowerPC, it will indeed throw away the upper > 32 bits as I described above. On i386, it will however result in > something > like "v shl ((8 *i) and 31)". I checked it: The old version and your code produce exactly the same value on 64bit and 32bit. There is no difference between both results.

Strange, apparently shl/shr are not automatically changed to 64 bit when compiling for a 64 bit platform. I don't know why that is the case.

You can force a 64 bit shift by typecasting v to int64.

Show quoted text 8 lines
> I don't think there is a quick fix. Someone who knows what is going on > has > to go through it and properly fix it. Hacking the code you posted will > only > result in hiding a bug, and you will probably still get more errors > elsewhere. The problem is that no Pascal developer knows this code. It was translated from Java code.

At least the person who translated it supposedly knows it. Otherwise, you have to go back to the Java code and look how it does things.

Can you imagine another difference between 64bit and 32bit which may cause those error? The bitshifts result in the same value on 32bit and 64bit...

There are probably other places where an automatic upcast to 64 bit does take place (it happens for all add/sub/div/mod operations at least).

Jonas

Reply by email

Matthias Klumpp
to JoshyFun: MK> The problem is that no Pascal developer knows this code. It was translated MK> from…
The stream is compressed with 32 bits version ? Or are the 64 bits compressed files the ones that fail to be decompressed in 64 bits also ?

I cpmpressed a stream with the 64bits version. I can uncompress it successfully on 32bit, but not on 64bit.
I haven't tried to decompress 32bit compressed files under 64bit, but decompressing files compressed under 64bit does not work under 64bit, but on 32bit.

So the question a 32 bits compressed LZMA can be decompressed with 32 bits "decode", and the same stream decompressed with the 64 bits version ?

I'll try, but I think it won't work.

I included the Decoder function at the end of this file...

##################################################

function TLZMADecoder.Code(const
inStream,outStream:TStream;outSize:int64):boolean;
var state,rep0,rep1,rep2,rep3:Int64;
    nowPos64:Int64;
    prevByte:byte;
    posState:int64;
    decoder2:TLZMADecoder2;
    len,distance,posSlot,numDirectBits:Int64;
    lpos:int64;
    progint:int64;
begin
DoProgress(LPAMax,outSize);
m_RangeDecoder.SetStream(inStream);
m_OutWindow.SetStream(outStream);
self.Init;
state := ULZMABase.StateInit;
rep0 := 0; rep1 := 0; rep2 := 0; rep3 := 0;
nowPos64 := 0;
prevByte := 0;
progint:=outsize div CodeProgressInterval;
lpos:=progint;
while (outSize < 0) or (nowPos64 < outSize) do
begin
      if (nowPos64 >=lpos) then begin
         DoProgress(LPAPos,nowPos64);
         lpos:=lpos+progint;
         end;
      posState := nowPos64 and m_PosStateMask;
      if (m_RangeDecoder.DecodeBit(m_IsMatchDecoders, (state shl
ULZMABase.kNumPosStatesBitsMax) + posState) = 0) then
      begin
         decoder2 := m_LiteralDecoder.GetDecoder(nowPos64, prevByte);
         if not ULZMABase.StateIsCharState(state) then
            prevByte := decoder2.DecodeWithMatchByte(m_RangeDecoder,
m_OutWindow.GetByte(rep0))
            else prevByte := decoder2.DecodeNormal(m_RangeDecoder);
         m_OutWindow.PutByte(prevByte);
         state := ULZMABase.StateUpdateChar(state);
         inc(nowPos64);
         end else
         begin
             if (m_RangeDecoder.DecodeBit(m_IsRepDecoders, state) = 1) then
begin
                len := 0;
                if (m_RangeDecoder.DecodeBit(m_IsRepG0Decoders, state) = 0)
then begin
                   if (m_RangeDecoder.DecodeBit(m_IsRep0LongDecoders,
(state shl ULZMABase.kNumPosStatesBitsMax) + posState) = 0) then
                   begin
                      state := ULZMABase.StateUpdateShortRep(state);
                      len := 1;
                   end;
                   end else
                   begin
                       if m_RangeDecoder.DecodeBit(m_IsRepG1Decoders,
state) = 0 then
                          distance := rep1
                       else
                       begin
                            if (m_RangeDecoder.DecodeBit(m_IsRepG2Decoders,
state) = 0) then
                               distance := rep2
                            else
                            begin
                                 distance := rep3;
                                 rep3 := rep2;
                            end;
                            rep2 := rep1;
                       end;
                       rep1 := rep0;
                       rep0 := distance;
                       end;
                if len = 0 then begin
                   len := m_RepLenDecoder.Decode(m_RangeDecoder, posState)
+ ULZMABase.kMatchMinLen;
                   state := ULZMABase.StateUpdateRep(state);
                   end;
                end else begin
                    rep3 := rep2;
                    rep2 := rep1;
                    rep1 := rep0;
                    len := ULZMABase.kMatchMinLen +
m_LenDecoder.Decode(m_RangeDecoder, posState);
                    state := ULZMABase.StateUpdateMatch(state);
                    posSlot :=
m_PosSlotDecoder[ULZMABase.GetLenToPosState(len)].Decode(m_RangeDecoder);
                    if posSlot >= ULZMABase.kStartPosModelIndex then begin
                       numDirectBits := (posSlot shr 1) - 1;
                       rep0 := ((2 or (posSlot and 1)) shl numDirectBits);
                       if posSlot < ULZMABase.kEndPosModelIndex then
                          rep0 := rep0 +
UBitTreeDecoder.ReverseDecode(m_PosDecoders,
                                   rep0 - posSlot - 1, m_RangeDecoder,
numDirectBits)
                          else
                          begin
                               rep0 := rep0 +
(m_RangeDecoder.DecodeDirectBits(
                                        numDirectBits -
ULZMABase.kNumAlignBits) shl ULZMABase.kNumAlignBits);
                               rep0 := rep0 +
m_PosAlignDecoder.ReverseDecode(m_RangeDecoder);
                               if rep0 < 0 then
                               begin
                                  if rep0 = -1 then
                                     break;
                                  result:=false;
                                  exit;
                               end;
                          end;
                       end else rep0 := posSlot;
                    end;
      if (rep0 >= nowPos64) or (rep0 >= m_DictionarySizeCheck) then
      begin
         m_OutWindow.Flush();
         result:=false;
         exit;
      end;
      m_OutWindow.CopyBlock(rep0, len);
      nowPos64 := nowPos64 + len;
      prevByte := m_OutWindow.GetByte(0);
      end;
end;
m_OutWindow.Flush();
m_OutWindow.ReleaseStream();
m_RangeDecoder.ReleaseStream();
DoProgress(LPAPos,nowPos64);
result:=true;
end;

Reply by email

Matthias Klumpp
to Jonas Maebe: Strange, apparently shl/shr are not automatically changed to 64 bit when compiling for a…
Show quoted text 7 lines
Strange, apparently shl/shr are not automatically changed to 64 bit when compiling for a 64 bit platform. I don't know why that is the case. You can force a 64 bit shift by typecasting v to int64. At least the person who translated it supposedly knows it. Otherwise, you have to go back to the Java code and look how it does things.

I already talked to him, but he doesn't know it either. So I have to fix it if I want it working... I already translated a lot of Java code, but it is nearly exactly the same as the Pascal code already was and the Decompress keeps failing.
I will compile the Java code now, maybe it fails too. (but I don't think so)

Reply by email

JoshyFun
to Matthias Klumpp: I cpmpressed a stream with the 64bits version. I can uncompress it successfully on 32bit,…

Hello FPC-Pascal,

Monday, January 25, 2010, 2:27:00 PM, you wrote:

MK> I cpmpressed a stream with the 64bits version. I can uncompress it MK> successfully on 32bit, but not on 64bit.
MK> I haven't tried to decompress 32bit compressed files under 64bit, but MK> decompressing files compressed under 64bit does not work under 64bit, but MK> on 32bit.

Well, so the compression routine seems to be fine and 64 aware. I asked because in the encode routine I found 2 points that could be problematic or not, but I can not test 64 bit right now.

In 32->64 bits conversion I had found some problems when using "trivial" compares against constants, but none of them appear to be present in the decoder.

> So the question a 32 bits compressed LZMA can be decompressed with 32 > bits "decode", and the same stream decompressed with the 64 bits > version ?

MK> I'll try, but I think it won't work.

I hope to have some spare time this afternoon to test it, as I also need LZMA decompress in 64 bit.

Best regards, JoshyFun

Reply by email

Matthias Klumpp
to JoshyFun
Show quoted text 7 lines
>> So the question a 32 bits compressed LZMA can be decompressed with 32 >> bits "decode", and the same stream decompressed with the 64 bits >> version ? MK> I'll try, but I think it won't work. I hope to have some spare time this afternoon to test it, as I also need LZMA decompress in 64 bit.

I checked it: Decompressing files on 64bit-machines which were compressed on 32bit-linux does not work. Which means:
32bit-compressed -> 32bit-decompression ==> Works! 64bit-compressed -> 64bit-decompression ==> Does not work 64bit-compressed -> 32bit-decompression ==> Works! 32bit-compressed -> 64bit-decompression ==> Does not work.

Reply by email

JoshyFun
to Matthias Klumpp

Hello FPC-Pascal,

you wrote
> I hope to have some spare time this afternoon to test it, as I also > need LZMA decompress in 64 bit.

MK> I checked it: Decompressing files on 64bit-machines which were compressed MK> on 32bit-linux does not work. Which means:
MK> 32bit-compressed -> 32bit-decompression ==> Works! MK> 64bit-compressed -> 64bit-decompression ==> Does not work MK> 64bit-compressed -> 32bit-decompression ==> Works! MK> 32bit-compressed -> 64bit-decompression ==> Does not work.

Found the bug in URangeDecoder.pas

function TRangeDecoder.DecodeDirectBits(const numTotalBits:integer):integer;
var i,t:integer;
begin
result:=0;
for i := numTotalBits downto 1 do begin
    range:=range shr 1;
    //Old Code:
    //t := ((Code - Range) shr 31);
    //New one:
    t := (DWORD(Code - Range) shr 31);
    Code := Code - Range and (t - 1);
    result := (result shl 1) or (1 - t);
    if ((Range and kTopMask) = 0) then begin
       Code := (Code shl 8) or ReadByte(stream);
       Range := Range shl 8;
       end;
    end;
end;

DWORD fixes the problem, as:

32 bits: ($80000001 - 1) shr 31 = 1
64 bits: ($80000001 - 1) shr 31 = -1
64 bits: DWORD($80000001 - 1) shr 31 = -1

It looks like a problem in 64 bit versions :-? I think this topic appears in the past about 32<->64 bits shift operations over signed variables.

Best regards, JoshyFun

Reply by email

Graeme Geldenhuys
to JoshyFun
JoshyFun wrote
Found the bug in URangeDecoder.pas

I am planning on using LZMA in the future (no timeframe available yet), but could you guys make the fixed code available somewhere in a repository or as a sub-project of Lazarus CCR?

Otherwise others developers downloading the LZMA SDK from the original author will have to go through the same debug process as you guys have.

Regards,
- Graeme -

fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal http://opensoft.homeip.net/fpgui/

Reply by email

JoshyFun
to Graeme Geldenhuys

Hello FPC-Pascal,

Tuesday, January 26, 2010, 7:52:08 AM, you wrote:

GG> I am planning on using LZMA in the future (no timeframe available yet), but GG> could you guys make the fixed code available somewhere in a repository or GG> as a sub-project of Lazarus CCR?

More tests should be applied as I only tested it against one single small file. Once done I think it can be added to CCR.

GG> Otherwise others developers downloading the LZMA SDK from the original GG> author will have to go through the same debug process as you guys have.

Yes and the hunting was not easy :( fortunatly the code is quite small.

Best regards, JoshyFun

Reply by email

Matthias Klumpp
to JoshyFun
JoshyFun wrote 5 lines
Hello FPC-Pascal, Tuesday, January 26, 2010, 7:52:08 AM, you wrote: GG> I am planning on using LZMA in the future (no timeframe available

yet),

but GG> could you guys make the fixed code available somewhere in a

repository

Show quoted text 7 lines
or GG> as a sub-project of Lazarus CCR? More tests should be applied as I only tested it against one single small file. Once done I think it can be added to CCR. GG> Otherwise others developers downloading the LZMA SDK from the

original

GG> author will have to go through the same debug process as you guys

have.

Yes and the hunting was not easy :( fortunatly the code is quite small.

Cool! Many thanks for that fix! I was reviewing the code for nearly two days without any usable result.
I did a lot of testing, and the fixed version performs quite well. I now pushed it to the repository of my project which uses the SDK. If there are problems, I'll notify you, if everything works for a longer time, I can say the code has been well-tested for Lazarus-CCR.
Thanks!
Matthias Klumpp

Reply by email

JoshyFun
to Matthias Klumpp

Hello FPC-Pascal,

you wrote
> Yes and the hunting was not easy :( fortunatly the code is quite > small.

MK> Cool! Many thanks for that fix! I was reviewing the code for nearly two MK> days without any usable result.

Well I use a quite simple approach a lot of "writeln" after each variable assignement in the main loop using:

writeln({$I %LINE%},variable);

Run the same program in both 32 and 64 bits and apply a diff between both outputs, this reveals the wrong assigned variable in main loop. Then take the function that produces that value and do the same inside. I spend most time rebooting the machine from 32 to 64 bits :) I think I must install a virtual 32 bits machine in my 64 bit OS :)

MK> I did a lot of testing, and the fixed version performs quite well. I now MK> pushed it to the repository of my project which uses the SDK. If there are MK> problems, I'll notify you, if everything works for a longer time, I can say MK> the code has been well-tested for Lazarus-CCR.

Fine!. But simply decompressing a large chunch of data should reveal any possible hidden bug as decompression is almost all the same the same operation over and over again.

PS: Can anybody comment if this is expected ?

32 bits: ($80000001 - 1) shr 31 = 1
64 bits: ($80000001 - 1) shr 31 = -1
64 bits: DWORD($80000001 - 1) shr 31 = 1

Best regards, JoshyFun

Reply by email