2 * lzms_common.c - Common code for LZMS compression and decompression
6 * Copyright (C) 2013, 2014 Eric Biggers
8 * This file is free software; you can redistribute it and/or modify it under
9 * the terms of the GNU Lesser General Public License as published by the Free
10 * Software Foundation; either version 3 of the License, or (at your option) any
13 * This file is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
15 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with this file; if not, see http://www.gnu.org/licenses/.
26 #include "wimlib/lzms_common.h"
27 #include "wimlib/unaligned.h"
29 /* Table: offset slot => offset slot base value */
30 const u32 lzms_offset_slot_base[LZMS_MAX_NUM_OFFSET_SYMS + 1] = {
31 0x00000001, 0x00000002, 0x00000003, 0x00000004,
32 0x00000005, 0x00000006, 0x00000007, 0x00000008,
33 0x00000009, 0x0000000d, 0x00000011, 0x00000015,
34 0x00000019, 0x0000001d, 0x00000021, 0x00000025,
35 0x00000029, 0x0000002d, 0x00000035, 0x0000003d,
36 0x00000045, 0x0000004d, 0x00000055, 0x0000005d,
37 0x00000065, 0x00000075, 0x00000085, 0x00000095,
38 0x000000a5, 0x000000b5, 0x000000c5, 0x000000d5,
39 0x000000e5, 0x000000f5, 0x00000105, 0x00000125,
40 0x00000145, 0x00000165, 0x00000185, 0x000001a5,
41 0x000001c5, 0x000001e5, 0x00000205, 0x00000225,
42 0x00000245, 0x00000265, 0x00000285, 0x000002a5,
43 0x000002c5, 0x000002e5, 0x00000325, 0x00000365,
44 0x000003a5, 0x000003e5, 0x00000425, 0x00000465,
45 0x000004a5, 0x000004e5, 0x00000525, 0x00000565,
46 0x000005a5, 0x000005e5, 0x00000625, 0x00000665,
47 0x000006a5, 0x00000725, 0x000007a5, 0x00000825,
48 0x000008a5, 0x00000925, 0x000009a5, 0x00000a25,
49 0x00000aa5, 0x00000b25, 0x00000ba5, 0x00000c25,
50 0x00000ca5, 0x00000d25, 0x00000da5, 0x00000e25,
51 0x00000ea5, 0x00000f25, 0x00000fa5, 0x00001025,
52 0x000010a5, 0x000011a5, 0x000012a5, 0x000013a5,
53 0x000014a5, 0x000015a5, 0x000016a5, 0x000017a5,
54 0x000018a5, 0x000019a5, 0x00001aa5, 0x00001ba5,
55 0x00001ca5, 0x00001da5, 0x00001ea5, 0x00001fa5,
56 0x000020a5, 0x000021a5, 0x000022a5, 0x000023a5,
57 0x000024a5, 0x000026a5, 0x000028a5, 0x00002aa5,
58 0x00002ca5, 0x00002ea5, 0x000030a5, 0x000032a5,
59 0x000034a5, 0x000036a5, 0x000038a5, 0x00003aa5,
60 0x00003ca5, 0x00003ea5, 0x000040a5, 0x000042a5,
61 0x000044a5, 0x000046a5, 0x000048a5, 0x00004aa5,
62 0x00004ca5, 0x00004ea5, 0x000050a5, 0x000052a5,
63 0x000054a5, 0x000056a5, 0x000058a5, 0x00005aa5,
64 0x00005ca5, 0x00005ea5, 0x000060a5, 0x000064a5,
65 0x000068a5, 0x00006ca5, 0x000070a5, 0x000074a5,
66 0x000078a5, 0x00007ca5, 0x000080a5, 0x000084a5,
67 0x000088a5, 0x00008ca5, 0x000090a5, 0x000094a5,
68 0x000098a5, 0x00009ca5, 0x0000a0a5, 0x0000a4a5,
69 0x0000a8a5, 0x0000aca5, 0x0000b0a5, 0x0000b4a5,
70 0x0000b8a5, 0x0000bca5, 0x0000c0a5, 0x0000c4a5,
71 0x0000c8a5, 0x0000cca5, 0x0000d0a5, 0x0000d4a5,
72 0x0000d8a5, 0x0000dca5, 0x0000e0a5, 0x0000e4a5,
73 0x0000eca5, 0x0000f4a5, 0x0000fca5, 0x000104a5,
74 0x00010ca5, 0x000114a5, 0x00011ca5, 0x000124a5,
75 0x00012ca5, 0x000134a5, 0x00013ca5, 0x000144a5,
76 0x00014ca5, 0x000154a5, 0x00015ca5, 0x000164a5,
77 0x00016ca5, 0x000174a5, 0x00017ca5, 0x000184a5,
78 0x00018ca5, 0x000194a5, 0x00019ca5, 0x0001a4a5,
79 0x0001aca5, 0x0001b4a5, 0x0001bca5, 0x0001c4a5,
80 0x0001cca5, 0x0001d4a5, 0x0001dca5, 0x0001e4a5,
81 0x0001eca5, 0x0001f4a5, 0x0001fca5, 0x000204a5,
82 0x00020ca5, 0x000214a5, 0x00021ca5, 0x000224a5,
83 0x000234a5, 0x000244a5, 0x000254a5, 0x000264a5,
84 0x000274a5, 0x000284a5, 0x000294a5, 0x0002a4a5,
85 0x0002b4a5, 0x0002c4a5, 0x0002d4a5, 0x0002e4a5,
86 0x0002f4a5, 0x000304a5, 0x000314a5, 0x000324a5,
87 0x000334a5, 0x000344a5, 0x000354a5, 0x000364a5,
88 0x000374a5, 0x000384a5, 0x000394a5, 0x0003a4a5,
89 0x0003b4a5, 0x0003c4a5, 0x0003d4a5, 0x0003e4a5,
90 0x0003f4a5, 0x000404a5, 0x000414a5, 0x000424a5,
91 0x000434a5, 0x000444a5, 0x000454a5, 0x000464a5,
92 0x000474a5, 0x000484a5, 0x000494a5, 0x0004a4a5,
93 0x0004b4a5, 0x0004c4a5, 0x0004e4a5, 0x000504a5,
94 0x000524a5, 0x000544a5, 0x000564a5, 0x000584a5,
95 0x0005a4a5, 0x0005c4a5, 0x0005e4a5, 0x000604a5,
96 0x000624a5, 0x000644a5, 0x000664a5, 0x000684a5,
97 0x0006a4a5, 0x0006c4a5, 0x0006e4a5, 0x000704a5,
98 0x000724a5, 0x000744a5, 0x000764a5, 0x000784a5,
99 0x0007a4a5, 0x0007c4a5, 0x0007e4a5, 0x000804a5,
100 0x000824a5, 0x000844a5, 0x000864a5, 0x000884a5,
101 0x0008a4a5, 0x0008c4a5, 0x0008e4a5, 0x000904a5,
102 0x000924a5, 0x000944a5, 0x000964a5, 0x000984a5,
103 0x0009a4a5, 0x0009c4a5, 0x0009e4a5, 0x000a04a5,
104 0x000a24a5, 0x000a44a5, 0x000a64a5, 0x000aa4a5,
105 0x000ae4a5, 0x000b24a5, 0x000b64a5, 0x000ba4a5,
106 0x000be4a5, 0x000c24a5, 0x000c64a5, 0x000ca4a5,
107 0x000ce4a5, 0x000d24a5, 0x000d64a5, 0x000da4a5,
108 0x000de4a5, 0x000e24a5, 0x000e64a5, 0x000ea4a5,
109 0x000ee4a5, 0x000f24a5, 0x000f64a5, 0x000fa4a5,
110 0x000fe4a5, 0x001024a5, 0x001064a5, 0x0010a4a5,
111 0x0010e4a5, 0x001124a5, 0x001164a5, 0x0011a4a5,
112 0x0011e4a5, 0x001224a5, 0x001264a5, 0x0012a4a5,
113 0x0012e4a5, 0x001324a5, 0x001364a5, 0x0013a4a5,
114 0x0013e4a5, 0x001424a5, 0x001464a5, 0x0014a4a5,
115 0x0014e4a5, 0x001524a5, 0x001564a5, 0x0015a4a5,
116 0x0015e4a5, 0x001624a5, 0x001664a5, 0x0016a4a5,
117 0x0016e4a5, 0x001724a5, 0x001764a5, 0x0017a4a5,
118 0x0017e4a5, 0x001824a5, 0x001864a5, 0x0018a4a5,
119 0x0018e4a5, 0x001924a5, 0x001964a5, 0x0019e4a5,
120 0x001a64a5, 0x001ae4a5, 0x001b64a5, 0x001be4a5,
121 0x001c64a5, 0x001ce4a5, 0x001d64a5, 0x001de4a5,
122 0x001e64a5, 0x001ee4a5, 0x001f64a5, 0x001fe4a5,
123 0x002064a5, 0x0020e4a5, 0x002164a5, 0x0021e4a5,
124 0x002264a5, 0x0022e4a5, 0x002364a5, 0x0023e4a5,
125 0x002464a5, 0x0024e4a5, 0x002564a5, 0x0025e4a5,
126 0x002664a5, 0x0026e4a5, 0x002764a5, 0x0027e4a5,
127 0x002864a5, 0x0028e4a5, 0x002964a5, 0x0029e4a5,
128 0x002a64a5, 0x002ae4a5, 0x002b64a5, 0x002be4a5,
129 0x002c64a5, 0x002ce4a5, 0x002d64a5, 0x002de4a5,
130 0x002e64a5, 0x002ee4a5, 0x002f64a5, 0x002fe4a5,
131 0x003064a5, 0x0030e4a5, 0x003164a5, 0x0031e4a5,
132 0x003264a5, 0x0032e4a5, 0x003364a5, 0x0033e4a5,
133 0x003464a5, 0x0034e4a5, 0x003564a5, 0x0035e4a5,
134 0x003664a5, 0x0036e4a5, 0x003764a5, 0x0037e4a5,
135 0x003864a5, 0x0038e4a5, 0x003964a5, 0x0039e4a5,
136 0x003a64a5, 0x003ae4a5, 0x003b64a5, 0x003be4a5,
137 0x003c64a5, 0x003ce4a5, 0x003d64a5, 0x003de4a5,
138 0x003ee4a5, 0x003fe4a5, 0x0040e4a5, 0x0041e4a5,
139 0x0042e4a5, 0x0043e4a5, 0x0044e4a5, 0x0045e4a5,
140 0x0046e4a5, 0x0047e4a5, 0x0048e4a5, 0x0049e4a5,
141 0x004ae4a5, 0x004be4a5, 0x004ce4a5, 0x004de4a5,
142 0x004ee4a5, 0x004fe4a5, 0x0050e4a5, 0x0051e4a5,
143 0x0052e4a5, 0x0053e4a5, 0x0054e4a5, 0x0055e4a5,
144 0x0056e4a5, 0x0057e4a5, 0x0058e4a5, 0x0059e4a5,
145 0x005ae4a5, 0x005be4a5, 0x005ce4a5, 0x005de4a5,
146 0x005ee4a5, 0x005fe4a5, 0x0060e4a5, 0x0061e4a5,
147 0x0062e4a5, 0x0063e4a5, 0x0064e4a5, 0x0065e4a5,
148 0x0066e4a5, 0x0067e4a5, 0x0068e4a5, 0x0069e4a5,
149 0x006ae4a5, 0x006be4a5, 0x006ce4a5, 0x006de4a5,
150 0x006ee4a5, 0x006fe4a5, 0x0070e4a5, 0x0071e4a5,
151 0x0072e4a5, 0x0073e4a5, 0x0074e4a5, 0x0075e4a5,
152 0x0076e4a5, 0x0077e4a5, 0x0078e4a5, 0x0079e4a5,
153 0x007ae4a5, 0x007be4a5, 0x007ce4a5, 0x007de4a5,
154 0x007ee4a5, 0x007fe4a5, 0x0080e4a5, 0x0081e4a5,
155 0x0082e4a5, 0x0083e4a5, 0x0084e4a5, 0x0085e4a5,
156 0x0086e4a5, 0x0087e4a5, 0x0088e4a5, 0x0089e4a5,
157 0x008ae4a5, 0x008be4a5, 0x008ce4a5, 0x008de4a5,
158 0x008fe4a5, 0x0091e4a5, 0x0093e4a5, 0x0095e4a5,
159 0x0097e4a5, 0x0099e4a5, 0x009be4a5, 0x009de4a5,
160 0x009fe4a5, 0x00a1e4a5, 0x00a3e4a5, 0x00a5e4a5,
161 0x00a7e4a5, 0x00a9e4a5, 0x00abe4a5, 0x00ade4a5,
162 0x00afe4a5, 0x00b1e4a5, 0x00b3e4a5, 0x00b5e4a5,
163 0x00b7e4a5, 0x00b9e4a5, 0x00bbe4a5, 0x00bde4a5,
164 0x00bfe4a5, 0x00c1e4a5, 0x00c3e4a5, 0x00c5e4a5,
165 0x00c7e4a5, 0x00c9e4a5, 0x00cbe4a5, 0x00cde4a5,
166 0x00cfe4a5, 0x00d1e4a5, 0x00d3e4a5, 0x00d5e4a5,
167 0x00d7e4a5, 0x00d9e4a5, 0x00dbe4a5, 0x00dde4a5,
168 0x00dfe4a5, 0x00e1e4a5, 0x00e3e4a5, 0x00e5e4a5,
169 0x00e7e4a5, 0x00e9e4a5, 0x00ebe4a5, 0x00ede4a5,
170 0x00efe4a5, 0x00f1e4a5, 0x00f3e4a5, 0x00f5e4a5,
171 0x00f7e4a5, 0x00f9e4a5, 0x00fbe4a5, 0x00fde4a5,
172 0x00ffe4a5, 0x0101e4a5, 0x0103e4a5, 0x0105e4a5,
173 0x0107e4a5, 0x0109e4a5, 0x010be4a5, 0x010de4a5,
174 0x010fe4a5, 0x0111e4a5, 0x0113e4a5, 0x0115e4a5,
175 0x0117e4a5, 0x0119e4a5, 0x011be4a5, 0x011de4a5,
176 0x011fe4a5, 0x0121e4a5, 0x0123e4a5, 0x0125e4a5,
177 0x0127e4a5, 0x0129e4a5, 0x012be4a5, 0x012de4a5,
178 0x012fe4a5, 0x0131e4a5, 0x0133e4a5, 0x0135e4a5,
179 0x0137e4a5, 0x013be4a5, 0x013fe4a5, 0x0143e4a5,
180 0x0147e4a5, 0x014be4a5, 0x014fe4a5, 0x0153e4a5,
181 0x0157e4a5, 0x015be4a5, 0x015fe4a5, 0x0163e4a5,
182 0x0167e4a5, 0x016be4a5, 0x016fe4a5, 0x0173e4a5,
183 0x0177e4a5, 0x017be4a5, 0x017fe4a5, 0x0183e4a5,
184 0x0187e4a5, 0x018be4a5, 0x018fe4a5, 0x0193e4a5,
185 0x0197e4a5, 0x019be4a5, 0x019fe4a5, 0x01a3e4a5,
186 0x01a7e4a5, 0x01abe4a5, 0x01afe4a5, 0x01b3e4a5,
187 0x01b7e4a5, 0x01bbe4a5, 0x01bfe4a5, 0x01c3e4a5,
188 0x01c7e4a5, 0x01cbe4a5, 0x01cfe4a5, 0x01d3e4a5,
189 0x01d7e4a5, 0x01dbe4a5, 0x01dfe4a5, 0x01e3e4a5,
190 0x01e7e4a5, 0x01ebe4a5, 0x01efe4a5, 0x01f3e4a5,
191 0x01f7e4a5, 0x01fbe4a5, 0x01ffe4a5, 0x0203e4a5,
192 0x0207e4a5, 0x020be4a5, 0x020fe4a5, 0x0213e4a5,
193 0x0217e4a5, 0x021be4a5, 0x021fe4a5, 0x0223e4a5,
194 0x0227e4a5, 0x022be4a5, 0x022fe4a5, 0x0233e4a5,
195 0x0237e4a5, 0x023be4a5, 0x023fe4a5, 0x0243e4a5,
196 0x0247e4a5, 0x024be4a5, 0x024fe4a5, 0x0253e4a5,
197 0x0257e4a5, 0x025be4a5, 0x025fe4a5, 0x0263e4a5,
198 0x0267e4a5, 0x026be4a5, 0x026fe4a5, 0x0273e4a5,
199 0x0277e4a5, 0x027be4a5, 0x027fe4a5, 0x0283e4a5,
200 0x0287e4a5, 0x028be4a5, 0x028fe4a5, 0x0293e4a5,
201 0x0297e4a5, 0x029be4a5, 0x029fe4a5, 0x02a3e4a5,
202 0x02a7e4a5, 0x02abe4a5, 0x02afe4a5, 0x02b3e4a5,
203 0x02bbe4a5, 0x02c3e4a5, 0x02cbe4a5, 0x02d3e4a5,
204 0x02dbe4a5, 0x02e3e4a5, 0x02ebe4a5, 0x02f3e4a5,
205 0x02fbe4a5, 0x0303e4a5, 0x030be4a5, 0x0313e4a5,
206 0x031be4a5, 0x0323e4a5, 0x032be4a5, 0x0333e4a5,
207 0x033be4a5, 0x0343e4a5, 0x034be4a5, 0x0353e4a5,
208 0x035be4a5, 0x0363e4a5, 0x036be4a5, 0x0373e4a5,
209 0x037be4a5, 0x0383e4a5, 0x038be4a5, 0x0393e4a5,
210 0x039be4a5, 0x03a3e4a5, 0x03abe4a5, 0x03b3e4a5,
211 0x03bbe4a5, 0x03c3e4a5, 0x03cbe4a5, 0x03d3e4a5,
212 0x03dbe4a5, 0x03e3e4a5, 0x03ebe4a5, 0x03f3e4a5,
213 0x03fbe4a5, 0x0403e4a5, 0x040be4a5, 0x0413e4a5,
214 0x041be4a5, 0x0423e4a5, 0x042be4a5, 0x0433e4a5,
215 0x043be4a5, 0x0443e4a5, 0x044be4a5, 0x0453e4a5,
216 0x045be4a5, 0x0463e4a5, 0x046be4a5, 0x0473e4a5,
217 0x047be4a5, 0x0483e4a5, 0x048be4a5, 0x0493e4a5,
218 0x049be4a5, 0x04a3e4a5, 0x04abe4a5, 0x04b3e4a5,
219 0x04bbe4a5, 0x04c3e4a5, 0x04cbe4a5, 0x04d3e4a5,
220 0x04dbe4a5, 0x04e3e4a5, 0x04ebe4a5, 0x04f3e4a5,
221 0x04fbe4a5, 0x0503e4a5, 0x050be4a5, 0x0513e4a5,
222 0x051be4a5, 0x0523e4a5, 0x052be4a5, 0x0533e4a5,
223 0x053be4a5, 0x0543e4a5, 0x054be4a5, 0x0553e4a5,
224 0x055be4a5, 0x0563e4a5, 0x056be4a5, 0x0573e4a5,
225 0x057be4a5, 0x0583e4a5, 0x058be4a5, 0x0593e4a5,
226 0x059be4a5, 0x05a3e4a5, 0x05abe4a5, 0x05b3e4a5,
227 0x05bbe4a5, 0x05c3e4a5, 0x05cbe4a5, 0x05d3e4a5,
228 0x05dbe4a5, 0x05e3e4a5, 0x05ebe4a5, 0x05f3e4a5,
229 0x05fbe4a5, 0x060be4a5, 0x061be4a5, 0x062be4a5,
230 0x063be4a5, 0x064be4a5, 0x065be4a5, 0x465be4a5,
231 /* The last entry is extra; it is equal to LZMS_MAX_MATCH_OFFSET + 1 and
232 * is here to aid binary search. */
235 /* Table: offset slot => number of extra offset bits */
236 const u8 lzms_extra_offset_bits[LZMS_MAX_NUM_OFFSET_SYMS] = {
237 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 , 2 , 2 , 2 , 2 , 2 , 2 , 2,
238 2 , 3 , 3 , 3 , 3 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 4 , 4 , 4 , 4,
239 4 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5 , 5,
240 5 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6 , 6,
241 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7 , 7,
242 7 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8,
243 8 , 8 , 8 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9,
244 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9 , 9,
245 9 , 9 , 9 , 9 , 9 , 9 , 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
246 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
247 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11,
248 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
249 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12,
250 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
251 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
252 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13,
253 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
254 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
255 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
256 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
257 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
258 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
259 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
260 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
261 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
262 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
263 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16,
264 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
265 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
266 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
267 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
268 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17,
269 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
270 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
271 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
272 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
273 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
274 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
275 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
276 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
277 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
278 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
279 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19,
280 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
281 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
282 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
283 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
284 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
285 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
286 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 30,
289 /* Table: length slot => length slot base value */
290 const u32 lzms_length_slot_base[LZMS_NUM_LENGTH_SYMS + 1] = {
291 0x00000001, 0x00000002, 0x00000003, 0x00000004,
292 0x00000005, 0x00000006, 0x00000007, 0x00000008,
293 0x00000009, 0x0000000a, 0x0000000b, 0x0000000c,
294 0x0000000d, 0x0000000e, 0x0000000f, 0x00000010,
295 0x00000011, 0x00000012, 0x00000013, 0x00000014,
296 0x00000015, 0x00000016, 0x00000017, 0x00000018,
297 0x00000019, 0x0000001a, 0x0000001b, 0x0000001d,
298 0x0000001f, 0x00000021, 0x00000023, 0x00000027,
299 0x0000002b, 0x0000002f, 0x00000033, 0x00000037,
300 0x0000003b, 0x00000043, 0x0000004b, 0x00000053,
301 0x0000005b, 0x0000006b, 0x0000007b, 0x0000008b,
302 0x0000009b, 0x000000ab, 0x000000cb, 0x000000eb,
303 0x0000012b, 0x000001ab, 0x000002ab, 0x000004ab,
304 0x000008ab, 0x000108ab, 0x400108ab,
305 /* The last entry is extra; it is equal to LZMS_MAX_MATCH_LENGTH + 1 and
306 * is here to aid binary search. */
309 /* Table: length slot => number of extra length bits */
310 const u8 lzms_extra_length_bits[LZMS_NUM_LENGTH_SYMS] = {
311 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
312 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
313 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ,
314 0 , 0 , 1 , 1 , 1 , 1 , 2 , 2 ,
315 2 , 2 , 2 , 2 , 3 , 3 , 3 , 3 ,
316 4 , 4 , 4 , 4 , 4 , 5 , 5 , 6 ,
317 7 , 8 , 9 , 10, 16, 30,
321 lzms_get_slot(u32 value, const u32 slot_base_tab[], unsigned num_slots)
324 unsigned r = num_slots - 1;
326 unsigned slot = (l + r) / 2;
327 if (value >= slot_base_tab[slot]) {
328 if (value < slot_base_tab[slot + 1])
338 /* Return the number of offset slots used when processing a buffer having the
339 * specified uncompressed size. */
341 lzms_get_num_offset_slots(size_t uncompressed_size)
343 if (uncompressed_size < 2)
345 return 1 + lzms_get_offset_slot(uncompressed_size - 1);
349 lzms_init_probability_entries(struct lzms_probability_entry *entries, size_t count)
351 for (size_t i = 0; i < count; i++) {
352 entries[i].num_recent_zero_bits = LZMS_INITIAL_PROBABILITY;
353 entries[i].recent_bits = LZMS_INITIAL_RECENT_BITS;
358 lzms_init_symbol_frequencies(u32 freqs[], unsigned num_syms)
360 for (unsigned sym = 0; sym < num_syms; sym++)
365 lzms_dilute_symbol_frequencies(u32 freqs[], unsigned num_syms)
367 for (unsigned sym = 0; sym < num_syms; sym++)
368 freqs[sym] = (freqs[sym] >> 1) + 1;
372 * Translate relative addresses embedded in x86 instructions into absolute
373 * addresses (@undo == %false), or undo this translation (@undo == %true).
375 * Absolute addresses are usually more compressible by LZ factorization.
377 * @last_target_usages must be a temporary array of length >= 65536.
380 lzms_x86_filter(u8 data[restrict], s32 size,
381 s32 last_target_usages[restrict], bool undo)
384 * Note: this filter runs unconditionally and uses a custom algorithm to
385 * detect data regions that probably contain x86 code.
387 * 'last_x86_pos' tracks the most recent position that has a good chance
388 * of being the start of an x86 instruction. When the filter detects a
389 * likely x86 instruction, it updates this variable and considers the
390 * next LZMS_X86_MAX_TRANSLATION_OFFSET bytes of data as valid for x86
393 * If part of the data does not, in fact, contain x86 machine code, then
394 * 'last_x86_pos' will, very likely, eventually fall more than
395 * LZMS_X86_MAX_TRANSLATION_OFFSET bytes behind the current position.
396 * This results in x86 translations being disabled until the next likely
397 * x86 instruction is detected.
399 * To identify "likely x86 instructions", the algorithm attempts to
400 * track the position of the most recent potential relative-addressing
401 * instruction that referenced each possible memory address. If it
402 * finds two references to the same memory address within an
403 * LZMS_X86_ID_WINDOW_SIZE-byte sized window, then the second reference
404 * is flagged as a likely x86 instruction. Since the instructions
405 * considered for translation necessarily use relative addressing, the
406 * algorithm does a tentative translation into absolute addresses. In
407 * addition, so that memory addresses can be looked up in an array of
408 * reasonable size (in this code, 'last_target_usages'), only the
409 * low-order 2 bytes of each address are considered significant.
420 for (i = 0; i < 65536; i++)
421 last_target_usages[i] = -(s32)LZMS_X86_ID_WINDOW_SIZE - 1;
424 * Optimization: only check for end-of-buffer when we already have a
425 * byte that is a potential opcode for x86 translation. To do this,
426 * overwrite one of the bytes near the end of the buffer, and restore it
427 * later. The correctness of this optimization relies on two
428 * characteristics of compressed format:
430 * 1. No translation can follow an opcode beginning in the last 16
432 * 2. A translation following an opcode starting at the last possible
433 * position (17 bytes from the end) never extends more than 7 bytes.
434 * Consequently, we can overwrite any of the bytes starting at
435 * data[(size - 16) + 7] and have no effect on the result, as long
436 * as we restore those bytes later.
438 tail_idx = size - 16;
439 saved_byte = data[tail_idx + 8];
440 data[tail_idx + 8] = 0xE8;
441 last_x86_pos = -LZMS_X86_MAX_TRANSLATION_OFFSET - 1;
443 /* Note: the very first byte must be ignored completely! */
446 s32 max_trans_offset;
451 * The following table is used to accelerate the common case
452 * where the byte has nothing to do with x86 translation and
453 * must simply be skipped. This is the fastest (at least on
454 * x86_64) of the implementations I tested. The other
455 * implementations I tested were:
456 * - Jump table with 256 entries
457 * - Switch statement with default
459 static const u8 is_potential_opcode[256] = {
460 [0x48] = 1, [0x4C] = 1, [0xE8] = 1,
461 [0xE9] = 1, [0xF0] = 1, [0xFF] = 1,
465 if (is_potential_opcode[data[++i]])
467 if (is_potential_opcode[data[++i]])
469 if (is_potential_opcode[data[++i]])
471 if (is_potential_opcode[data[++i]])
478 max_trans_offset = LZMS_X86_MAX_TRANSLATION_OFFSET;
481 if (data[i + 1] == 0x8B) {
482 if (data[i + 2] == 0x5 || data[i + 2] == 0xD) {
483 /* Load relative (x86_64) */
487 } else if (data[i + 1] == 0x8D) {
488 if ((data[i + 2] & 0x7) == 0x5) {
489 /* Load effective address relative (x86_64) */
496 if (data[i + 1] == 0x8D) {
497 if ((data[i + 2] & 0x7) == 0x5) {
498 /* Load effective address relative (x86_64) */
505 /* Call relative. Note: 'max_trans_offset' must be
506 * halved for this instruction. This means that we must
507 * be more confident that we are in a region of x86
508 * machine code before we will do a translation for this
509 * particular instruction. */
511 max_trans_offset /= 2;
518 if (data[i + 1] == 0x83 && data[i + 2] == 0x05) {
519 /* Lock add relative */
525 if (data[i + 1] == 0x15) {
537 if (i - last_x86_pos <= max_trans_offset) {
538 void *p32 = &data[i + opcode_nbytes];
539 u32 n = get_unaligned_u32_le(p32);
540 put_unaligned_u32_le(n - i, p32);
542 target16 = i + get_unaligned_u16_le(&data[i + opcode_nbytes]);
544 target16 = i + get_unaligned_u16_le(&data[i + opcode_nbytes]);
545 if (i - last_x86_pos <= max_trans_offset) {
546 void *p32 = &data[i + opcode_nbytes];
547 u32 n = get_unaligned_u32_le(p32);
548 put_unaligned_u32_le(n + i, p32);
552 i += opcode_nbytes + sizeof(le32) - 1;
554 if (i - last_target_usages[target16] <= LZMS_X86_ID_WINDOW_SIZE)
557 last_target_usages[target16] = i;
562 data[tail_idx + 8] = saved_byte;