[cifs-protocol] [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about blocks - TrackingID#2210140040006030
Douglas Bagnall
douglas.bagnall at catalyst.net.nz
Mon Nov 14 00:05:49 UTC 2022
hi Jeff,
What I have for the LZ77 phase, in pseudocode, is this:
set the block size to be the minimum of 65536 or the remaining size.
for each byte of the input up to block size - 3:
work out whether there's a match, using hashes etc
no match:
add a literal
continue from loop start
match:
add the match distance and length
is the end of the match past the block end?
no:
advance to the byte after the match
continue from loop start
yes:
is the end of the match within 40 bytes of the end of input?
no:
we've finished this block
yes:
set the block end to consume all the remaining input bytes
exit this loop
# here we start another loop that cleans up the remaining bytes,
# either because we got to block length - 3 where there's no room
# for matches, or because we extended the block to the end of input
for each byte of the input up to block size:
add a literal
But I am able to generate files that won't decompress on Windows, and I don't
know why. This, I *think*, is the only part that is still unclear to me.
In all my failing cases, there is a match that ends after the block end but
within 40 bytes of the end of the input, but there is no obvious pattern around
the offsets (like, it doesn't look like an off-by-one >= vs > confusion).
Anything you can add about how Windows compresses or decompresses in this
situation would be very helpful.
thanks
Douglas
On 10/11/22 13:16, Douglas Bagnall via cifs-protocol wrote:
>> If it ends within 40 bytes of the end of the buffer, the remaining bytes in
>> the buffer are encoded as literals.
>
> Is this the case even when the would-be-penultimate block doesn't end in an
> overly long match?
>
> That is, if the compressor began a block at the point where there were 64k + 20
> bytes remaining, would it always make the next block contain all the data, or
> would it wait to see if it ended in an overshooting match, and encode the
> remaining data in a new block if not?
>
> Also, when you say "within 40 bytes", is that "< 40" or "<= 40"?
>
> cheers,
> Douglas
>
>
> On 10/11/22 10:23, Jeff McCashland (He/him) wrote:
>> Hi Douglas,
>>
>> It appears you are correct that the current block ends at the end of the >64k
>> match. The maximum length of the match will go to the end of the input buffer.
>> If it ends within 40 bytes of the end of the buffer, the remaining bytes in
>> the buffer are encoded as literals.
>>
>> Best regards,
>> Jeff McCashland (He/him) | Senior Escalation Engineer | Microsoft Protocol
>> Open Specifications Team
>> Phone: +1 (425) 703-8300 x38300 | Hours: 9am-5pm | Time zone: (UTC-08:00)
>> Pacific Time (US and Canada)
>> Local country phone number found here:
>> http://support.microsoft.com/globalenglish | Extension 1138300
>>
>> -----Original Message-----
>> From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>> Sent: Tuesday, November 8, 2022 4:30 PM
>> To: Jeff McCashland (He/him) <jeffm at microsoft.com>;
>> cifs-protocol at lists.samba.org; Samuel Cabrero (Samba) <scabrero at samba.org>
>> Cc: Microsoft Support <supportmail at microsoft.com>
>> Subject: Re: [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about blocks -
>> TrackingID#2210140040006030
>>
>> Another question on this:
>>
>> When a block exceeds 64k, how can we know when the block ends?
>>
>> Does it always end immediately after the match pushing past 64k?
>>
>> Douglas
>>
>>
>>
>> On 9/11/22 12:44, Jeff McCashland (He/him) wrote:
>>> Hi Douglas,
>>>
>>> I've found something interesting while researching this issue that might help.
>>>
>>> In the initial LZ77 encoding phase, matches are searched for in 64k blocks,
>>> as documented. However, when determining the length of the match, Windows
>>> will keep searching as long as the match continues, even if it continues
>>> through multiple 64k blocks, up to a total of 64 MB. I created a file > 64MB
>>> with lowercase a-z repeated so that the first match actually goes to the end
>>> of the 64 MB 'super-block'. The length of the match worked out to just under
>>> 64 MB, and the next pass started with the remainder of the file after 64MB.
>>>
>>> I hope that helps to explain some of the oddities you're seeing.
>>>
>>> Best regards,
>>> Jeff McCashland (He/him) | Senior Escalation Engineer | Microsoft
>>> Protocol Open Specifications Team
>>> Phone: +1 (425) 703-8300 x38300 | Hours: 9am-5pm | Time zone:
>>> (UTC-08:00) Pacific Time (US and Canada) Local country phone number
>>> found here:
>>> https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fsuppo
>>> rt.microsoft.com%2Fglobalenglish&data=05%7C01%7Cjeffm%40microsoft.
>>> com%7C0483ab4790724d4204f608dac1e99e45%7C72f988bf86f141af91ab2d7cd011d
>>> b47%7C1%7C0%7C638035506383210907%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wL
>>> jAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&
>>> amp;sdata=dzDCD7AzjOQ4QVG%2FOJNg9LB%2BYRwnzTCoXvjad6A79wY%3D&reser
>>> ved=0 | Extension 1138300
>>>
>>> -----Original Message-----
>>> From: Jeff McCashland (He/him)
>>> Sent: Thursday, October 27, 2022 9:57 AM
>>> To: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>;
>>> cifs-protocol at lists.samba.org; Samuel Cabrero (Samba)
>>> <scabrero at samba.org>
>>> Cc: Microsoft Support <supportmail at microsoft.com>
>>> Subject: RE: [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about blocks
>>> - TrackingID#2210140040006030
>>>
>>> Hi Douglas,
>>>
>>> Thank you for the fast response. I will continue digging into this.
>>>
>>> Best regards,
>>> Jeff McCashland (He/him) | Senior Escalation Engineer | Microsoft
>>> Protocol Open Specifications Team
>>> Phone: +1 (425) 703-8300 x38300 | Hours: 9am-5pm | Time zone:
>>> (UTC-08:00) Pacific Time (US and Canada) Local country phone number
>>> found here:
>>> https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fsuppo
>>> rt.microsoft.com%2Fglobalenglish&data=05%7C01%7Cjeffm%40microsoft.
>>> com%7C0483ab4790724d4204f608dac1e99e45%7C72f988bf86f141af91ab2d7cd011d
>>> b47%7C1%7C0%7C638035506383210907%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wL
>>> jAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C&
>>> amp;sdata=dzDCD7AzjOQ4QVG%2FOJNg9LB%2BYRwnzTCoXvjad6A79wY%3D&reser
>>> ved=0 | Extension 1138300
>>>
>>> -----Original Message-----
>>> From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>>> Sent: Wednesday, October 26, 2022 2:10 PM
>>> To: Jeff McCashland (He/him) <jeffm at microsoft.com>;
>>> cifs-protocol at lists.samba.org; Samuel Cabrero (Samba)
>>> <scabrero at samba.org>
>>> Cc: Microsoft Support <supportmail at microsoft.com>
>>> Subject: Re: [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about blocks
>>> - TrackingID#2210140040006030
>>>
>>> hi Jeff,
>>>
>>> Thanks. Yes, I think you're understanding correctly, and that is a valid
>>> answer, and I *would* have happily accepted it, but in the meantime I have
>>> had the misfortune of re-reading MS-XCA again and again, and I now believe it
>>> contradicts this view.
>>>
>>> In 2.1.4.3 there is:
>>>
>>> The following pseudocode demonstrates the encoding method.
>>>
>>> Write the 256-byte table of symbol bit lengths
>>> While there are more literals or matches to encode
>>> [[write bits per the algorithm, not in question here]]
>>> WriteBits(SymbolLength[256], SymbolCode[256])
>>> FlushBits()
>>>
>>> This appears to be encoding a single block (there's one 256-byte table), and
>>> it ends with the FlushBits(), which is essentially the "ignore ghi..." in my
>>> example. However it also has a "WriteBits(SymbolLength[256],
>>> SymbolCode[256])", which I understand should only happen at the end of the
>>> last block.
>>>
>>> I think it would be accurate to say this pseudocode "demonstrates the
>>> encoding method for a message of 65536 or fewer bytes", but is unclear for
>>> multi-block messages.
>>>
>>>
>>> And in section 2.2.4 the main decompression pseudocode loop starts like:
>>>
>>> Loop until a decompression terminating condition
>>> Build the decoding table
>>> CurrentPosition = 256 // start at the end of the Huffman table
>>> NextBits = Read16Bits(InputBuffer + CurrentPosition)
>>> CurrentPosition += 2
>>> NextBits <<= 16
>>> NextBits |= Read16Bits(InputBuffer + CurrentPosition)
>>> CurrentPosition += 2
>>> ExtraBitCount = 16
>>>
>>>
>>> which suggests that the bits "ghi..." are discarded because we are told
>>> implicitly in the text that Read16bits shifts input into a 32 bit register --
>>> if we call it twice at the beginning of each block, whatever was in the
>>> register has to fall out the other end.
>>>
>>> cheers,
>>> Douglas
>>>
>>>
>>> On 27/10/22 05:48, Jeff McCashland (He/him) wrote:
>>>> Hi Douglas,
>>>>
>>>> As I understand, each 64k block is processed separately. In other words, the
>>>> first 64k block is LZ77 compressed, then the Huffman codes are constructed
>>>> based on symbol frequency in that 64k. If, in your example, DEF ends the 64k
>>>> block, then the subsequent ghi... will be processed with the second 64k
>>>> block and Huffman table, and not dropped.
>>>>
>>>> Am I understanding your question correctly?
>>>>
>>>> Best regards,
>>>> Jeff McCashland (He/him) | Senior Escalation Engineer | Microsoft
>>>> Protocol Open Specifications Team
>>>> Phone: +1 (425) 703-8300 x38300 | Hours: 9am-5pm | Time zone:
>>>> (UTC-08:00) Pacific Time (US and Canada) Local country phone number
>>>> found here:
>>>> https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fsupp
>>>> o
>>>> rt.microsoft.com%2Fglobalenglish&data=05%7C01%7Cjeffm%40microsoft.
>>>> com%7C2eed4b9f9fda44b7458d08dab79674a8%7C72f988bf86f141af91ab2d7cd011
>>>> d
>>>> b47%7C1%7C0%7C638024154089025057%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4w
>>>> L
>>>> jAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C
>>>> &
>>>> amp;sdata=gToAFtZwgAnmsIJgYkP9aVhup%2Blb5zsDN%2Bajebbzh18%3D&rese
>>>> r
>>>> ved=0 | Extension 1138300
>>>>
>>>> -----Original Message-----
>>>> From: Jeff McCashland (He/him)
>>>> Sent: Friday, October 14, 2022 1:58 PM
>>>> To: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>;
>>>> cifs-protocol at lists.samba.org; Samuel Cabrero (Samba)
>>>> <scabrero at samba.org>
>>>> Cc: Microsoft Support <supportmail at microsoft.com>
>>>> Subject: RE: [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about
>>>> blocks
>>>> - TrackingID#2210140040006030
>>>>
>>>> [Tom to BCC]
>>>>
>>>> Hi Douglas,
>>>>
>>>> I'll research this question and let you know what I learn.
>>>>
>>>> Best regards,
>>>> Jeff McCashland (He/him) | Senior Escalation Engineer | Microsoft
>>>> Protocol Open Specifications Team
>>>> Phone: +1 (425) 703-8300 x38300 | Hours: 9am-5pm | Time zone:
>>>> (UTC-08:00) Pacific Time (US and Canada) Local country phone number
>>>> found here:
>>>> https://nam06.safelinks.protection.outlook.com/?url=http%3A%2F%2Fsupp
>>>> o
>>>> rt.microsoft.com%2Fglobalenglish&data=05%7C01%7Cjeffm%40microsoft.
>>>> com%7C2eed4b9f9fda44b7458d08dab79674a8%7C72f988bf86f141af91ab2d7cd011
>>>> d
>>>> b47%7C1%7C0%7C638024154089025057%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4w
>>>> L
>>>> jAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000%7C%7C%7C
>>>> &
>>>> amp;sdata=gToAFtZwgAnmsIJgYkP9aVhup%2Blb5zsDN%2Bajebbzh18%3D&rese
>>>> r
>>>> ved=0 | Extension 1138300
>>>>
>>>> -----Original Message-----
>>>> From: Tom Jebo <tomjebo at microsoft.com>
>>>> Sent: Friday, October 14, 2022 9:45 AM
>>>> To: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>;
>>>> cifs-protocol at lists.samba.org; Samuel Cabrero (Samba)
>>>> <scabrero at samba.org>
>>>> Cc: Microsoft Support <supportmail at microsoft.com>
>>>> Subject: RE: [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about
>>>> blocks
>>>> - TrackingID#2210140040006030
>>>>
>>>> [dochelp to bcc]
>>>> [casemail cc]
>>>>
>>>> Hi Douglas,
>>>>
>>>> Thank you for your request. One of the Open Specifications team will respond
>>>> to start working with you. I have created case 2210140040006030 and added
>>>> the number to the subject of this email. Please refer to this case number in
>>>> future communications regarding this issue.
>>>>
>>>> Best regards,
>>>> Tom Jebo
>>>> Sr Escalation Engineer
>>>> Microsoft Open Specifications
>>>>
>>>> -----Original Message-----
>>>> From: Douglas Bagnall <douglas.bagnall at catalyst.net.nz>
>>>> Sent: Thursday, October 13, 2022 9:57 PM
>>>> To: Interoperability Documentation Help <dochelp at microsoft.com>;
>>>> cifs-protocol at lists.samba.org; Samuel Cabrero (Samba)
>>>> <scabrero at samba.org>
>>>> Subject: [EXTERNAL] [MS-XCA] LZ77+ Huffman: questions about blocks
>>>>
>>>> hi Dochelp,
>>>>
>>>>
>>>> Does the beginning of the second and subsequent blocks break the bitstream,
>>>> starting again at a byte boundary after the new Huffman table?
>>>>
>>>> The question is best explained by analogy to the way long lengths are
>>>> handled in matches. Suppose we have a match symbol in the middle of a
>>>> bitstream, and the match is a long one, requiring the reading of an extra byte:
>>>>
>>>> ijklmnop abcDEFgh [distance] qrs...
>>>> |
>>>> [match 1, 15]
>>>>
>>>> Here abc, ghi.. are the sequence of bits in the stream around the match DEF,
>>>> which is read in alternating bytes by little-endian rules, and the distance
>>>> is plonked in the middle of the stream as an individual byte. The stream
>>>> just flows around it, so gh-ijklmnop are interpreted after [distance].
>>>>
>>>> Now, if DEF instead ended the block:
>>>>
>>>> ijklmnop abcDEFgh [new Huffman table] qrs...
>>>> |
>>>> [ends the block (64k)]
>>>>
>>>>
>>>> would the bits gh-jklmnop be interpreted using the new Huffman table, as
>>>> part of the new block, or would those bits be dropped?
>>>>
>>>> Multi-block examples would of course be helpful.
>>>>
>>>>
>>>> Douglas
>>>>
>>>>
>>>
>>
>
>
> _______________________________________________
> cifs-protocol mailing list
> cifs-protocol at lists.samba.org
> https://lists.samba.org/mailman/listinfo/cifs-protocol
More information about the cifs-protocol
mailing list