Expand source code
Browse git
from __future__ import annotations
import struct as _struct
from refinery.lib.decompression import (
DECODE_TABLE_LENGTH_MASK,
DECODE_TABLE_SYMBOL_SHIFT,
make_huffman_decode_table,
)
from refinery.lib.types import buf
LZMS_PROB_BITS = 6 # noqa
LZMS_PROB_DENOM = 1 << LZMS_PROB_BITS # noqa
LZMS_INITIAL_PROB = 48 # noqa
LZMS_INITIAL_BITS = 0x0000000055555555 # noqa
LZMS_NUM_LZ_REPS = 3 # noqa
LZMS_NUM_DELTA_REPS = 3 # noqa
LZMS_NUM_MAIN_PROBS = 16 # noqa
LZMS_NUM_MATCH_PROBS = 32 # noqa
LZMS_NUM_LZ_PROBS = 64 # noqa
LZMS_NUM_LZ_REP_PROBS = 64 # noqa
LZMS_NUM_DELTA_PROBS = 64 # noqa
LZMS_NUM_DELTA_REP_PROBS = 64 # noqa
LZMS_NUM_LITERAL_SYMS = 256 # noqa
LZMS_NUM_LENGTH_SYMS = 54 # noqa
LZMS_NUM_DELTA_POWER_SYMS = 8 # noqa
LZMS_MAX_NUM_OFFSET_SYMS = 799 # noqa
LZMS_MAX_CODEWORD_LENGTH = 15 # noqa
LZMS_LITERAL_REBUILD_FREQ = 1024 # noqa
LZMS_LZ_OFFSET_REBUILD_FREQ = 1024 # noqa
LZMS_LENGTH_REBUILD_FREQ = 512 # noqa
LZMS_DELTA_OFFSET_REBUILD_FREQ = 1024 # noqa
LZMS_DELTA_POWER_REBUILD_FREQ = 512 # noqa
LZMS_LITERAL_TABLEBITS = 10 # noqa
LZMS_LENGTH_TABLEBITS = 9 # noqa
LZMS_LZ_OFFSET_TABLEBITS = 11 # noqa
LZMS_DELTA_OFFSET_TABLEBITS = 11 # noqa
LZMS_DELTA_POWER_TABLEBITS = 7 # noqa
LZMS_X86_ID_WINDOW_SIZE = 65535 # noqa
LZMS_X86_MAX_TRANSLATION_OFF = 1023 # noqa
LZMS_OFFSET_SLOT_BASE = [
0x00000001, 0x00000002, 0x00000003, 0x00000004,
0x00000005, 0x00000006, 0x00000007, 0x00000008,
0x00000009, 0x0000000D, 0x00000011, 0x00000015,
0x00000019, 0x0000001D, 0x00000021, 0x00000025,
0x00000029, 0x0000002D, 0x00000035, 0x0000003D,
0x00000045, 0x0000004D, 0x00000055, 0x0000005D,
0x00000065, 0x00000075, 0x00000085, 0x00000095,
0x000000A5, 0x000000B5, 0x000000C5, 0x000000D5,
0x000000E5, 0x000000F5, 0x00000105, 0x00000125,
0x00000145, 0x00000165, 0x00000185, 0x000001A5,
0x000001C5, 0x000001E5, 0x00000205, 0x00000225,
0x00000245, 0x00000265, 0x00000285, 0x000002A5,
0x000002C5, 0x000002E5, 0x00000325, 0x00000365,
0x000003A5, 0x000003E5, 0x00000425, 0x00000465,
0x000004A5, 0x000004E5, 0x00000525, 0x00000565,
0x000005A5, 0x000005E5, 0x00000625, 0x00000665,
0x000006A5, 0x00000725, 0x000007A5, 0x00000825,
0x000008A5, 0x00000925, 0x000009A5, 0x00000A25,
0x00000AA5, 0x00000B25, 0x00000BA5, 0x00000C25,
0x00000CA5, 0x00000D25, 0x00000DA5, 0x00000E25,
0x00000EA5, 0x00000F25, 0x00000FA5, 0x00001025,
0x000010A5, 0x000011A5, 0x000012A5, 0x000013A5,
0x000014A5, 0x000015A5, 0x000016A5, 0x000017A5,
0x000018A5, 0x000019A5, 0x00001AA5, 0x00001BA5,
0x00001CA5, 0x00001DA5, 0x00001EA5, 0x00001FA5,
0x000020A5, 0x000021A5, 0x000022A5, 0x000023A5,
0x000024A5, 0x000026A5, 0x000028A5, 0x00002AA5,
0x00002CA5, 0x00002EA5, 0x000030A5, 0x000032A5,
0x000034A5, 0x000036A5, 0x000038A5, 0x00003AA5,
0x00003CA5, 0x00003EA5, 0x000040A5, 0x000042A5,
0x000044A5, 0x000046A5, 0x000048A5, 0x00004AA5,
0x00004CA5, 0x00004EA5, 0x000050A5, 0x000052A5,
0x000054A5, 0x000056A5, 0x000058A5, 0x00005AA5,
0x00005CA5, 0x00005EA5, 0x000060A5, 0x000064A5,
0x000068A5, 0x00006CA5, 0x000070A5, 0x000074A5,
0x000078A5, 0x00007CA5, 0x000080A5, 0x000084A5,
0x000088A5, 0x00008CA5, 0x000090A5, 0x000094A5,
0x000098A5, 0x00009CA5, 0x0000A0A5, 0x0000A4A5,
0x0000A8A5, 0x0000ACA5, 0x0000B0A5, 0x0000B4A5,
0x0000B8A5, 0x0000BCA5, 0x0000C0A5, 0x0000C4A5,
0x0000C8A5, 0x0000CCA5, 0x0000D0A5, 0x0000D4A5,
0x0000D8A5, 0x0000DCA5, 0x0000E0A5, 0x0000E4A5,
0x0000ECA5, 0x0000F4A5, 0x0000FCA5, 0x000104A5,
0x00010CA5, 0x000114A5, 0x00011CA5, 0x000124A5,
0x00012CA5, 0x000134A5, 0x00013CA5, 0x000144A5,
0x00014CA5, 0x000154A5, 0x00015CA5, 0x000164A5,
0x00016CA5, 0x000174A5, 0x00017CA5, 0x000184A5,
0x00018CA5, 0x000194A5, 0x00019CA5, 0x0001A4A5,
0x0001ACA5, 0x0001B4A5, 0x0001BCA5, 0x0001C4A5,
0x0001CCA5, 0x0001D4A5, 0x0001DCA5, 0x0001E4A5,
0x0001ECA5, 0x0001F4A5, 0x0001FCA5, 0x000204A5,
0x00020CA5, 0x000214A5, 0x00021CA5, 0x000224A5,
0x000234A5, 0x000244A5, 0x000254A5, 0x000264A5,
0x000274A5, 0x000284A5, 0x000294A5, 0x0002A4A5,
0x0002B4A5, 0x0002C4A5, 0x0002D4A5, 0x0002E4A5,
0x0002F4A5, 0x000304A5, 0x000314A5, 0x000324A5,
0x000334A5, 0x000344A5, 0x000354A5, 0x000364A5,
0x000374A5, 0x000384A5, 0x000394A5, 0x0003A4A5,
0x0003B4A5, 0x0003C4A5, 0x0003D4A5, 0x0003E4A5,
0x0003F4A5, 0x000404A5, 0x000414A5, 0x000424A5,
0x000434A5, 0x000444A5, 0x000454A5, 0x000464A5,
0x000474A5, 0x000484A5, 0x000494A5, 0x0004A4A5,
0x0004B4A5, 0x0004C4A5, 0x0004E4A5, 0x000504A5,
0x000524A5, 0x000544A5, 0x000564A5, 0x000584A5,
0x0005A4A5, 0x0005C4A5, 0x0005E4A5, 0x000604A5,
0x000624A5, 0x000644A5, 0x000664A5, 0x000684A5,
0x0006A4A5, 0x0006C4A5, 0x0006E4A5, 0x000704A5,
0x000724A5, 0x000744A5, 0x000764A5, 0x000784A5,
0x0007A4A5, 0x0007C4A5, 0x0007E4A5, 0x000804A5,
0x000824A5, 0x000844A5, 0x000864A5, 0x000884A5,
0x0008A4A5, 0x0008C4A5, 0x0008E4A5, 0x000904A5,
0x000924A5, 0x000944A5, 0x000964A5, 0x000984A5,
0x0009A4A5, 0x0009C4A5, 0x0009E4A5, 0x000A04A5,
0x000A24A5, 0x000A44A5, 0x000A64A5, 0x000AA4A5,
0x000AE4A5, 0x000B24A5, 0x000B64A5, 0x000BA4A5,
0x000BE4A5, 0x000C24A5, 0x000C64A5, 0x000CA4A5,
0x000CE4A5, 0x000D24A5, 0x000D64A5, 0x000DA4A5,
0x000DE4A5, 0x000E24A5, 0x000E64A5, 0x000EA4A5,
0x000EE4A5, 0x000F24A5, 0x000F64A5, 0x000FA4A5,
0x000FE4A5, 0x001024A5, 0x001064A5, 0x0010A4A5,
0x0010E4A5, 0x001124A5, 0x001164A5, 0x0011A4A5,
0x0011E4A5, 0x001224A5, 0x001264A5, 0x0012A4A5,
0x0012E4A5, 0x001324A5, 0x001364A5, 0x0013A4A5,
0x0013E4A5, 0x001424A5, 0x001464A5, 0x0014A4A5,
0x0014E4A5, 0x001524A5, 0x001564A5, 0x0015A4A5,
0x0015E4A5, 0x001624A5, 0x001664A5, 0x0016A4A5,
0x0016E4A5, 0x001724A5, 0x001764A5, 0x0017A4A5,
0x0017E4A5, 0x001824A5, 0x001864A5, 0x0018A4A5,
0x0018E4A5, 0x001924A5, 0x001964A5, 0x0019E4A5,
0x001A64A5, 0x001AE4A5, 0x001B64A5, 0x001BE4A5,
0x001C64A5, 0x001CE4A5, 0x001D64A5, 0x001DE4A5,
0x001E64A5, 0x001EE4A5, 0x001F64A5, 0x001FE4A5,
0x002064A5, 0x0020E4A5, 0x002164A5, 0x0021E4A5,
0x002264A5, 0x0022E4A5, 0x002364A5, 0x0023E4A5,
0x002464A5, 0x0024E4A5, 0x002564A5, 0x0025E4A5,
0x002664A5, 0x0026E4A5, 0x002764A5, 0x0027E4A5,
0x002864A5, 0x0028E4A5, 0x002964A5, 0x0029E4A5,
0x002A64A5, 0x002AE4A5, 0x002B64A5, 0x002BE4A5,
0x002C64A5, 0x002CE4A5, 0x002D64A5, 0x002DE4A5,
0x002E64A5, 0x002EE4A5, 0x002F64A5, 0x002FE4A5,
0x003064A5, 0x0030E4A5, 0x003164A5, 0x0031E4A5,
0x003264A5, 0x0032E4A5, 0x003364A5, 0x0033E4A5,
0x003464A5, 0x0034E4A5, 0x003564A5, 0x0035E4A5,
0x003664A5, 0x0036E4A5, 0x003764A5, 0x0037E4A5,
0x003864A5, 0x0038E4A5, 0x003964A5, 0x0039E4A5,
0x003A64A5, 0x003AE4A5, 0x003B64A5, 0x003BE4A5,
0x003C64A5, 0x003CE4A5, 0x003D64A5, 0x003DE4A5,
0x003EE4A5, 0x003FE4A5, 0x0040E4A5, 0x0041E4A5,
0x0042E4A5, 0x0043E4A5, 0x0044E4A5, 0x0045E4A5,
0x0046E4A5, 0x0047E4A5, 0x0048E4A5, 0x0049E4A5,
0x004AE4A5, 0x004BE4A5, 0x004CE4A5, 0x004DE4A5,
0x004EE4A5, 0x004FE4A5, 0x0050E4A5, 0x0051E4A5,
0x0052E4A5, 0x0053E4A5, 0x0054E4A5, 0x0055E4A5,
0x0056E4A5, 0x0057E4A5, 0x0058E4A5, 0x0059E4A5,
0x005AE4A5, 0x005BE4A5, 0x005CE4A5, 0x005DE4A5,
0x005EE4A5, 0x005FE4A5, 0x0060E4A5, 0x0061E4A5,
0x0062E4A5, 0x0063E4A5, 0x0064E4A5, 0x0065E4A5,
0x0066E4A5, 0x0067E4A5, 0x0068E4A5, 0x0069E4A5,
0x006AE4A5, 0x006BE4A5, 0x006CE4A5, 0x006DE4A5,
0x006EE4A5, 0x006FE4A5, 0x0070E4A5, 0x0071E4A5,
0x0072E4A5, 0x0073E4A5, 0x0074E4A5, 0x0075E4A5,
0x0076E4A5, 0x0077E4A5, 0x0078E4A5, 0x0079E4A5,
0x007AE4A5, 0x007BE4A5, 0x007CE4A5, 0x007DE4A5,
0x007EE4A5, 0x007FE4A5, 0x0080E4A5, 0x0081E4A5,
0x0082E4A5, 0x0083E4A5, 0x0084E4A5, 0x0085E4A5,
0x0086E4A5, 0x0087E4A5, 0x0088E4A5, 0x0089E4A5,
0x008AE4A5, 0x008BE4A5, 0x008CE4A5, 0x008DE4A5,
0x008FE4A5, 0x0091E4A5, 0x0093E4A5, 0x0095E4A5,
0x0097E4A5, 0x0099E4A5, 0x009BE4A5, 0x009DE4A5,
0x009FE4A5, 0x00A1E4A5, 0x00A3E4A5, 0x00A5E4A5,
0x00A7E4A5, 0x00A9E4A5, 0x00ABE4A5, 0x00ADE4A5,
0x00AFE4A5, 0x00B1E4A5, 0x00B3E4A5, 0x00B5E4A5,
0x00B7E4A5, 0x00B9E4A5, 0x00BBE4A5, 0x00BDE4A5,
0x00BFE4A5, 0x00C1E4A5, 0x00C3E4A5, 0x00C5E4A5,
0x00C7E4A5, 0x00C9E4A5, 0x00CBE4A5, 0x00CDE4A5,
0x00CFE4A5, 0x00D1E4A5, 0x00D3E4A5, 0x00D5E4A5,
0x00D7E4A5, 0x00D9E4A5, 0x00DBE4A5, 0x00DDE4A5,
0x00DFE4A5, 0x00E1E4A5, 0x00E3E4A5, 0x00E5E4A5,
0x00E7E4A5, 0x00E9E4A5, 0x00EBE4A5, 0x00EDE4A5,
0x00EFE4A5, 0x00F1E4A5, 0x00F3E4A5, 0x00F5E4A5,
0x00F7E4A5, 0x00F9E4A5, 0x00FBE4A5, 0x00FDE4A5,
0x00FFE4A5, 0x0101E4A5, 0x0103E4A5, 0x0105E4A5,
0x0107E4A5, 0x0109E4A5, 0x010BE4A5, 0x010DE4A5,
0x010FE4A5, 0x0111E4A5, 0x0113E4A5, 0x0115E4A5,
0x0117E4A5, 0x0119E4A5, 0x011BE4A5, 0x011DE4A5,
0x011FE4A5, 0x0121E4A5, 0x0123E4A5, 0x0125E4A5,
0x0127E4A5, 0x0129E4A5, 0x012BE4A5, 0x012DE4A5,
0x012FE4A5, 0x0131E4A5, 0x0133E4A5, 0x0135E4A5,
0x0137E4A5, 0x013BE4A5, 0x013FE4A5, 0x0143E4A5,
0x0147E4A5, 0x014BE4A5, 0x014FE4A5, 0x0153E4A5,
0x0157E4A5, 0x015BE4A5, 0x015FE4A5, 0x0163E4A5,
0x0167E4A5, 0x016BE4A5, 0x016FE4A5, 0x0173E4A5,
0x0177E4A5, 0x017BE4A5, 0x017FE4A5, 0x0183E4A5,
0x0187E4A5, 0x018BE4A5, 0x018FE4A5, 0x0193E4A5,
0x0197E4A5, 0x019BE4A5, 0x019FE4A5, 0x01A3E4A5,
0x01A7E4A5, 0x01ABE4A5, 0x01AFE4A5, 0x01B3E4A5,
0x01B7E4A5, 0x01BBE4A5, 0x01BFE4A5, 0x01C3E4A5,
0x01C7E4A5, 0x01CBE4A5, 0x01CFE4A5, 0x01D3E4A5,
0x01D7E4A5, 0x01DBE4A5, 0x01DFE4A5, 0x01E3E4A5,
0x01E7E4A5, 0x01EBE4A5, 0x01EFE4A5, 0x01F3E4A5,
0x01F7E4A5, 0x01FBE4A5, 0x01FFE4A5, 0x0203E4A5,
0x0207E4A5, 0x020BE4A5, 0x020FE4A5, 0x0213E4A5,
0x0217E4A5, 0x021BE4A5, 0x021FE4A5, 0x0223E4A5,
0x0227E4A5, 0x022BE4A5, 0x022FE4A5, 0x0233E4A5,
0x0237E4A5, 0x023BE4A5, 0x023FE4A5, 0x0243E4A5,
0x0247E4A5, 0x024BE4A5, 0x024FE4A5, 0x0253E4A5,
0x0257E4A5, 0x025BE4A5, 0x025FE4A5, 0x0263E4A5,
0x0267E4A5, 0x026BE4A5, 0x026FE4A5, 0x0273E4A5,
0x0277E4A5, 0x027BE4A5, 0x027FE4A5, 0x0283E4A5,
0x0287E4A5, 0x028BE4A5, 0x028FE4A5, 0x0293E4A5,
0x0297E4A5, 0x029BE4A5, 0x029FE4A5, 0x02A3E4A5,
0x02A7E4A5, 0x02ABE4A5, 0x02AFE4A5, 0x02B3E4A5,
0x02BBE4A5, 0x02C3E4A5, 0x02CBE4A5, 0x02D3E4A5,
0x02DBE4A5, 0x02E3E4A5, 0x02EBE4A5, 0x02F3E4A5,
0x02FBE4A5, 0x0303E4A5, 0x030BE4A5, 0x0313E4A5,
0x031BE4A5, 0x0323E4A5, 0x032BE4A5, 0x0333E4A5,
0x033BE4A5, 0x0343E4A5, 0x034BE4A5, 0x0353E4A5,
0x035BE4A5, 0x0363E4A5, 0x036BE4A5, 0x0373E4A5,
0x037BE4A5, 0x0383E4A5, 0x038BE4A5, 0x0393E4A5,
0x039BE4A5, 0x03A3E4A5, 0x03ABE4A5, 0x03B3E4A5,
0x03BBE4A5, 0x03C3E4A5, 0x03CBE4A5, 0x03D3E4A5,
0x03DBE4A5, 0x03E3E4A5, 0x03EBE4A5, 0x03F3E4A5,
0x03FBE4A5, 0x0403E4A5, 0x040BE4A5, 0x0413E4A5,
0x041BE4A5, 0x0423E4A5, 0x042BE4A5, 0x0433E4A5,
0x043BE4A5, 0x0443E4A5, 0x044BE4A5, 0x0453E4A5,
0x045BE4A5, 0x0463E4A5, 0x046BE4A5, 0x0473E4A5,
0x047BE4A5, 0x0483E4A5, 0x048BE4A5, 0x0493E4A5,
0x049BE4A5, 0x04A3E4A5, 0x04ABE4A5, 0x04B3E4A5,
0x04BBE4A5, 0x04C3E4A5, 0x04CBE4A5, 0x04D3E4A5,
0x04DBE4A5, 0x04E3E4A5, 0x04EBE4A5, 0x04F3E4A5,
0x04FBE4A5, 0x0503E4A5, 0x050BE4A5, 0x0513E4A5,
0x051BE4A5, 0x0523E4A5, 0x052BE4A5, 0x0533E4A5,
0x053BE4A5, 0x0543E4A5, 0x054BE4A5, 0x0553E4A5,
0x055BE4A5, 0x0563E4A5, 0x056BE4A5, 0x0573E4A5,
0x057BE4A5, 0x0583E4A5, 0x058BE4A5, 0x0593E4A5,
0x059BE4A5, 0x05A3E4A5, 0x05ABE4A5, 0x05B3E4A5,
0x05BBE4A5, 0x05C3E4A5, 0x05CBE4A5, 0x05D3E4A5,
0x05DBE4A5, 0x05E3E4A5, 0x05EBE4A5, 0x05F3E4A5,
0x05FBE4A5, 0x060BE4A5, 0x061BE4A5, 0x062BE4A5,
0x063BE4A5, 0x064BE4A5, 0x065BE4A5, 0x465BE4A5,
]
LZMS_EXTRA_OFFSET_BITS = [
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2,
2 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4,
4 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5,
5 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6,
7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7,
7 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8,
8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9,
9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9,
9 , 9 , 9 , 9 , 9 , 9 , 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11,
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12,
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13,
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16,
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17,
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 30,
]
LZMS_LENGTH_SLOT_BASE = [
0x00000001, 0x00000002, 0x00000003, 0x00000004,
0x00000005, 0x00000006, 0x00000007, 0x00000008,
0x00000009, 0x0000000A, 0x0000000B, 0x0000000C,
0x0000000D, 0x0000000E, 0x0000000F, 0x00000010,
0x00000011, 0x00000012, 0x00000013, 0x00000014,
0x00000015, 0x00000016, 0x00000017, 0x00000018,
0x00000019, 0x0000001A, 0x0000001B, 0x0000001D,
0x0000001F, 0x00000021, 0x00000023, 0x00000027,
0x0000002B, 0x0000002F, 0x00000033, 0x00000037,
0x0000003B, 0x00000043, 0x0000004B, 0x00000053,
0x0000005B, 0x0000006B, 0x0000007B, 0x0000008B,
0x0000009B, 0x000000AB, 0x000000CB, 0x000000EB,
0x0000012B, 0x000001AB, 0x000002AB, 0x000004AB,
0x000008AB, 0x000108AB,
]
LZMS_EXTRA_LENGTH_BITS = [
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
0 , 0 , 1 , 1 , 1 , 1 , 2 , 2 ,
2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 ,
4 , 4 , 4 , 4 , 4 , 5 , 5 , 6 ,
7 , 8 , 9 , 10, 16, 30,
]
def _lzms_get_num_offset_slots(uncompressed_size: int) -> int:
if uncompressed_size < 2:
return 0
target = uncompressed_size - 1
lo, hi = 0, LZMS_MAX_NUM_OFFSET_SYMS - 1
while True:
mid = (lo + hi) // 2
if target >= LZMS_OFFSET_SLOT_BASE[mid]:
if target < LZMS_OFFSET_SLOT_BASE[mid + 1]:
return mid + 1
lo = mid + 1
else:
hi = mid - 1
class LzmsProbEntry:
__slots__ = 'num_recent_zero_bits', 'recent_bits'
def __init__(self):
self.num_recent_zero_bits = LZMS_INITIAL_PROB
self.recent_bits = LZMS_INITIAL_BITS
def update(self, bit: int):
delta = int(self.recent_bits >> (LZMS_PROB_DENOM - 1)) - bit
self.num_recent_zero_bits += delta
self.recent_bits = ((self.recent_bits << 1) | bit) & ((1 << LZMS_PROB_DENOM) - 1)
@property
def probability(self) -> int:
p = self.num_recent_zero_bits
if p == 0:
p = 1
if p == LZMS_PROB_DENOM:
p = LZMS_PROB_DENOM - 1
return p
class LzmsInputBitStream:
__slots__ = '_data', '_pos', '_bitbuf', '_bitcount'
def __init__(self, data: buf):
self._data = data
self._pos = len(data)
self._bitbuf = 0
self._bitcount = 0
def ensure(self, n: int):
while self._bitcount < n:
if self._pos < 2:
return
self._pos -= 2
word = _struct.unpack_from('<H', self._data, self._pos)[0]
avail = 64 - self._bitcount
self._bitbuf |= word << (avail - 16)
self._bitcount += 16
def peek(self, n: int) -> int:
return (self._bitbuf >> 1) >> (63 - n)
def remove(self, n: int):
self._bitbuf <<= n
self._bitbuf &= (1 << 64) - 1
self._bitcount -= n
def read(self, n: int) -> int:
if n == 0:
return 0
self.ensure(n)
val = self.peek(n)
self.remove(n)
return val
class LzmsRangeDecoder:
__slots__ = '_data', '_pos', '_end', 'range', 'code'
def __init__(self, data: buf):
self._data = data
self._pos = 0
self._end = len(data)
hi = self._read_u16()
lo = self._read_u16()
self.range = 0xFFFFFFFF
self.code = (hi << 16) | lo
def _read_u16(self) -> int:
if self._pos + 2 > self._end:
return 0
val = _struct.unpack_from('<H', self._data, self._pos)[0]
self._pos += 2
return val
def _normalize(self):
if not (self.range & 0xFFFF0000):
self.range = (self.range << 16) & 0xFFFFFFFF
self.code = ((self.code << 16) | self._read_u16()) & 0xFFFFFFFF
def decode_bit(self, state: list, num_states: int, probs: list) -> int:
entry = probs[state[0]]
state[0] = (state[0] << 1) & (num_states - 1)
prob = entry.probability
self._normalize()
bound = (self.range >> LZMS_PROB_BITS) * prob
if self.code < bound:
self.range = bound
entry.update(0)
return 0
else:
self.range -= bound
self.code -= bound
entry.update(1)
state[0] |= 1
return 1
def _lzms_code_lengths(freqs: list[int]) -> bytearray:
"""
Compute the codeword lengths of the canonical Huffman code that LZMS derives from the given
symbol frequencies. The compressor and the decompressor have to derive the same code, so the
construction is fixed: Symbols are ordered by frequency and then by value, a leaf is merged
before an inner node of equal weight, and a node deeper than `LZMS_MAX_CODEWORD_LENGTH` takes
the longest shorter length that still has a free codeword.
"""
leaves = sorted(range(len(freqs)), key=lambda s: (freqs[s], s))
leaf_weights = [freqs[s] for s in leaves]
num_leaves = len(leaves)
num_nodes = num_leaves - 1
node_weights = [0] * num_nodes
node_parents = [0] * num_nodes
next_leaf = next_node = 0
for new in range(num_nodes):
if (
next_leaf + 1 < num_leaves
and (next_node == new or leaf_weights[next_leaf + 1] <= node_weights[next_node])
):
weight = leaf_weights[next_leaf] + leaf_weights[next_leaf + 1]
next_leaf += 2
elif (
next_node + 2 <= new
and (next_leaf >= num_leaves or node_weights[next_node + 1] < leaf_weights[next_leaf])
):
weight = node_weights[next_node] + node_weights[next_node + 1]
node_parents[next_node] = new
node_parents[next_node + 1] = new
next_node += 2
else:
weight = leaf_weights[next_leaf] + node_weights[next_node]
node_parents[next_node] = new
next_leaf += 1
next_node += 1
node_weights[new] = weight
length_counts = [0] * (LZMS_MAX_CODEWORD_LENGTH + 1)
length_counts[1] = 2
node_depths = [0] * num_nodes
for node in range(num_nodes - 2, -1, -1):
node_depths[node] = length = node_depths[node_parents[node]] + 1
if length >= LZMS_MAX_CODEWORD_LENGTH:
length = LZMS_MAX_CODEWORD_LENGTH - 1
while not length_counts[length]:
length -= 1
length_counts[length] -= 1
length_counts[length + 1] += 2
lengths = bytearray(num_leaves)
next_leaf = 0
for length in range(LZMS_MAX_CODEWORD_LENGTH, 0, -1):
for _ in range(length_counts[length]):
lengths[leaves[next_leaf]] = length
next_leaf += 1
return lengths
class LzmsHuffmanDecoder:
__slots__ = (
'_bitstream',
'_num_syms',
'_rebuild_freq',
'_freqs',
'_syms_until_rebuild',
'_decode_table',
'_table_bits',
)
def __init__(
self,
bitstream: LzmsInputBitStream,
num_syms: int,
rebuild_freq: int,
table_bits: int
):
self._bitstream = bitstream
self._num_syms = num_syms
self._rebuild_freq = rebuild_freq
self._table_bits = table_bits
self._freqs = [1] * num_syms
self._syms_until_rebuild = 0
self._decode_table = None
self._build()
def _build(self):
if self._num_syms >= 2:
self._decode_table = make_huffman_decode_table(
_lzms_code_lengths(self._freqs), self._table_bits, LZMS_MAX_CODEWORD_LENGTH)
self._syms_until_rebuild = self._rebuild_freq
def decode(self) -> int:
sym = self._read_symbol()
self._freqs[sym] += 1
self._syms_until_rebuild -= 1
if self._syms_until_rebuild == 0:
self._build()
for i in range(self._num_syms):
self._freqs[i] = (self._freqs[i] >> 1) + 1
return sym
def _read_symbol(self) -> int:
bs = self._bitstream
tb = self._table_bits
if (table := self._decode_table) is None:
raise RuntimeError(
F'LZMS: cannot decode a symbol from an alphabet of size {self._num_syms}'
)
bs.ensure(LZMS_MAX_CODEWORD_LENGTH)
idx = bs.peek(tb)
entry = table[idx]
symbol = entry >> DECODE_TABLE_SYMBOL_SHIFT
length = entry & DECODE_TABLE_LENGTH_MASK
if entry >= (1 << (tb + DECODE_TABLE_SYMBOL_SHIFT)):
bs.remove(tb)
entry = table[symbol + bs.peek(length)]
symbol = entry >> DECODE_TABLE_SYMBOL_SHIFT
length = entry & DECODE_TABLE_LENGTH_MASK
bs.remove(length)
return symbol
def lzms_x86_filter(data: bytearray, size: int):
if size <= 17:
return
_IS_OPCODE = bytearray(256)
_IS_OPCODE[0x48] = 1
_IS_OPCODE[0x4C] = 1
_IS_OPCODE[0xE8] = 1
_IS_OPCODE[0xE9] = 1
_IS_OPCODE[0xF0] = 1
_IS_OPCODE[0xFF] = 1
last_x86_pos = -LZMS_X86_MAX_TRANSLATION_OFF - 1
last_target_usages = [-LZMS_X86_ID_WINDOW_SIZE - 1] * 65536
tail = size - 16
i = 1
while i < tail:
if not _IS_OPCODE[data[i]]:
i += 1
continue
opcode = data[i]
max_trans_off = LZMS_X86_MAX_TRANSLATION_OFF
opcode_nbytes = 0
if opcode >= 0xF0:
if opcode & 0x0F:
if i + 1 < size and data[i + 1] == 0x15:
opcode_nbytes = 2
else:
if i + 2 < size and data[i + 1] == 0x83 and data[i + 2] == 0x05:
opcode_nbytes = 3
elif opcode <= 0x4C:
if i + 2 < size and (data[i + 2] & 0x07) == 0x05:
if data[i + 1] == 0x8D or (
data[i + 1] == 0x8B and not (data[i] & 0x04) and not (data[i + 2] & 0xF0)
):
opcode_nbytes = 3
else:
if opcode & 0x01:
i += 5
continue
else:
opcode_nbytes = 1
max_trans_off >>= 1
if opcode_nbytes == 0:
i += 1
continue
pos = i
i += opcode_nbytes
if i + 4 > size:
break
if pos - last_x86_pos <= max_trans_off:
n = int.from_bytes(data[i:i + 4], 'little')
n = (n - pos) & 0xFFFFFFFF
data[i:i + 4] = n.to_bytes(4, 'little')
target16 = pos + int.from_bytes(data[i:i + 2], 'little')
target16 &= 0xFFFF
check_pos = pos + opcode_nbytes + 3
if check_pos - last_target_usages[target16] <= LZMS_X86_ID_WINDOW_SIZE:
last_x86_pos = check_pos
last_target_usages[target16] = check_pos
i += 4
def lzms_decompress(src_data: buf, target: int) -> bytes:
if not src_data or len(src_data) < 4 or (len(src_data) & 1):
return B''
num_offset_slots = _lzms_get_num_offset_slots(target)
rd = LzmsRangeDecoder(src_data)
bs = LzmsInputBitStream(src_data)
literal_dec = LzmsHuffmanDecoder(bs, LZMS_NUM_LITERAL_SYMS, LZMS_LITERAL_REBUILD_FREQ, LZMS_LITERAL_TABLEBITS)
lz_offset_dec = LzmsHuffmanDecoder(bs, num_offset_slots, LZMS_LZ_OFFSET_REBUILD_FREQ, LZMS_LZ_OFFSET_TABLEBITS)
length_dec = LzmsHuffmanDecoder(bs, LZMS_NUM_LENGTH_SYMS, LZMS_LENGTH_REBUILD_FREQ, LZMS_LENGTH_TABLEBITS)
delta_power_dec = LzmsHuffmanDecoder(bs, LZMS_NUM_DELTA_POWER_SYMS, LZMS_DELTA_POWER_REBUILD_FREQ, LZMS_DELTA_POWER_TABLEBITS)
delta_offset_dec = LzmsHuffmanDecoder(bs, num_offset_slots, LZMS_DELTA_OFFSET_REBUILD_FREQ, LZMS_DELTA_OFFSET_TABLEBITS)
main_probs = [LzmsProbEntry() for _ in range(LZMS_NUM_MAIN_PROBS)]
match_probs = [LzmsProbEntry() for _ in range(LZMS_NUM_MATCH_PROBS)]
lz_probs = [LzmsProbEntry() for _ in range(LZMS_NUM_LZ_PROBS)]
delta_probs = [LzmsProbEntry() for _ in range(LZMS_NUM_DELTA_PROBS)]
lz_rep_probs = [[LzmsProbEntry() for _ in range(LZMS_NUM_LZ_REP_PROBS)] for _ in range(LZMS_NUM_LZ_REPS - 1)]
delta_rep_probs = [[LzmsProbEntry() for _ in range(LZMS_NUM_DELTA_REP_PROBS)] for _ in range(LZMS_NUM_DELTA_REPS - 1)]
main_state = [0]
match_state = [0]
lz_state = [0]
delta_state = [0]
lz_rep_states = [[0], [0]]
delta_rep_states = [[0], [0]]
recent_lz_offsets = [1, 2, 3, 4]
recent_delta_pairs = [1, 2, 3, 4]
prev_item_type = 0
output = bytearray()
def _decode_lz_offset() -> int:
slot = lz_offset_dec.decode()
return LZMS_OFFSET_SLOT_BASE[slot] + bs.read(LZMS_EXTRA_OFFSET_BITS[slot])
def _decode_length() -> int:
slot = length_dec.decode()
return LZMS_LENGTH_SLOT_BASE[slot] + bs.read(LZMS_EXTRA_LENGTH_BITS[slot])
def _decode_delta_offset() -> int:
slot = delta_offset_dec.decode()
return LZMS_OFFSET_SLOT_BASE[slot] + bs.read(LZMS_EXTRA_OFFSET_BITS[slot])
while len(output) < target:
if not rd.decode_bit(main_state, LZMS_NUM_MAIN_PROBS, main_probs):
output.append(literal_dec.decode())
prev_item_type = 0
elif not rd.decode_bit(match_state, LZMS_NUM_MATCH_PROBS, match_probs):
if not rd.decode_bit(lz_state, LZMS_NUM_LZ_PROBS, lz_probs):
offset = _decode_lz_offset()
recent_lz_offsets[3] = recent_lz_offsets[2]
recent_lz_offsets[2] = recent_lz_offsets[1]
recent_lz_offsets[1] = recent_lz_offsets[0]
else:
adj = prev_item_type & 1
if not rd.decode_bit(lz_rep_states[0], LZMS_NUM_LZ_REP_PROBS, lz_rep_probs[0]):
offset = recent_lz_offsets[0 + adj]
recent_lz_offsets[0 + adj] = recent_lz_offsets[0]
elif not rd.decode_bit(lz_rep_states[1], LZMS_NUM_LZ_REP_PROBS, lz_rep_probs[1]):
offset = recent_lz_offsets[1 + adj]
recent_lz_offsets[1 + adj] = recent_lz_offsets[1]
recent_lz_offsets[1] = recent_lz_offsets[0]
else:
offset = recent_lz_offsets[2 + adj]
recent_lz_offsets[2 + adj] = recent_lz_offsets[2]
recent_lz_offsets[2] = recent_lz_offsets[1]
recent_lz_offsets[1] = recent_lz_offsets[0]
recent_lz_offsets[0] = offset
prev_item_type = 1
length = _decode_length()
pos = len(output)
if offset > pos:
raise RuntimeError(F'LZMS: LZ offset {offset} exceeds position {pos}')
if length > target - pos:
raise RuntimeError(F'LZMS: LZ length {length} exceeds remaining {target - pos}')
for k in range(length):
output.append(output[pos - offset + k])
else:
adj = prev_item_type >> 1
if not rd.decode_bit(delta_state, LZMS_NUM_DELTA_PROBS, delta_probs):
power = delta_power_dec.decode()
raw_offset = _decode_delta_offset()
pair = (power << 32) | raw_offset
recent_delta_pairs[3] = recent_delta_pairs[2]
recent_delta_pairs[2] = recent_delta_pairs[1]
recent_delta_pairs[1] = recent_delta_pairs[0]
else:
if not rd.decode_bit(delta_rep_states[0], LZMS_NUM_DELTA_REP_PROBS, delta_rep_probs[0]):
pair = recent_delta_pairs[0 + adj]
recent_delta_pairs[0 + adj] = recent_delta_pairs[0]
elif not rd.decode_bit(delta_rep_states[1], LZMS_NUM_DELTA_REP_PROBS, delta_rep_probs[1]):
pair = recent_delta_pairs[1 + adj]
recent_delta_pairs[1 + adj] = recent_delta_pairs[1]
recent_delta_pairs[1] = recent_delta_pairs[0]
else:
pair = recent_delta_pairs[2 + adj]
recent_delta_pairs[2 + adj] = recent_delta_pairs[2]
recent_delta_pairs[2] = recent_delta_pairs[1]
recent_delta_pairs[1] = recent_delta_pairs[0]
power = pair >> 32
raw_offset = pair & 0xFFFFFFFF
recent_delta_pairs[0] = pair
prev_item_type = 2
length = _decode_length()
span = 1 << power
offset = raw_offset << power
pos = len(output)
if offset + span > pos:
raise RuntimeError('LZMS: delta offset+span exceeds position')
if length > target - pos:
raise RuntimeError(F'LZMS: delta length {length} exceeds remaining {target - pos}')
for k in range(length):
output.append(
(output[pos + k - offset] + output[pos + k - span] - output[pos + k - span - offset]) & 0xFF
)
lzms_x86_filter(output, target)
return bytes(output)