1 | //␊ |
2 | // lzvn.c␊ |
3 | //␊ |
4 | // Based on works from Pike R. Alpha and AnV Software (Andy Vandijck).␊ |
5 | // Converted to C by MinusZwei on 9/14/14.␊ |
6 | //␊ |
7 | // No dogs allowed.␊ |
8 | //␊ |
9 | ␊ |
10 | #include <stdio.h>␊ |
11 | ␊ |
12 | #include <libkern/OSByteOrder.h>␊ |
13 | ␊ |
14 | ␊ |
15 | static short Llzvn_tableref[256] =␊ |
16 | {␊ |
17 | 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 4, 3,␊ |
18 | 1, 1, 1, 1, 1, 1, 4, 3, 1, 1, 1, 1, 1, 1, 5, 3,␊ |
19 | 1, 1, 1, 1, 1, 1, 5, 3, 1, 1, 1, 1, 1, 1, 5, 3,␊ |
20 | 1, 1, 1, 1, 1, 1, 5, 3, 1, 1, 1, 1, 1, 1, 5, 3,␊ |
21 | 1, 1, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 1, 0, 3,␊ |
22 | 1, 1, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 1, 0, 3,␊ |
23 | 1, 1, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 1, 0, 3,␊ |
24 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,␊ |
25 | 1, 1, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 1, 0, 3,␊ |
26 | 1, 1, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 1, 0, 3,␊ |
27 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,␊ |
28 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,␊ |
29 | 1, 1, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 1, 0, 3,␊ |
30 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,␊ |
31 | 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,␊ |
32 | 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10␊ |
33 | };␊ |
34 | ␊ |
35 | ␊ |
36 | // mov (%rdx),%r8␊ |
37 | // movzbq (%rdx),%r9␊ |
38 | // jmpq *(%rbx,%r9,8)␊ |
39 | ␊ |
40 | #define LABEL_JUMP \␊ |
41 | ␉do { \␊ |
42 | ␉␉r8 = *(uint64_t *)rdx; \␊ |
43 | ␉␉r9 = r8 & 0xFF; \␊ |
44 | ␉␉switch (Llzvn_tableref[r9]) { \␊ |
45 | ␉␉␉case 0: goto Llzvn_table0; break; \␊ |
46 | ␉␉␉case 1: goto Llzvn_table1; break; \␊ |
47 | ␉␉␉case 2: return rax; \␊ |
48 | ␉␉␉case 3: goto Llzvn_table3; break; \␊ |
49 | ␉␉␉case 4: goto Llzvn_table4; break; \␊ |
50 | ␉␉␉case 5: return 0; \␊ |
51 | ␉␉␉case 6: goto Llzvn_table6; break; \␊ |
52 | ␉␉␉case 7: goto Llzvn_table7; break; \␊ |
53 | ␉␉␉case 8: goto Llzvn_table8; break; \␊ |
54 | ␉␉␉case 9: goto Llzvn_table9; break; \␊ |
55 | ␉␉␉case 10: goto Llzvn_table10; break; \␊ |
56 | ␉␉} \␊ |
57 | ␉} while (0)␊ |
58 | ␊ |
59 | ␊ |
60 | size_t lzvn_decode(void *dst,␊ |
61 | ␉␉␉size_t dst_size,␊ |
62 | ␉␉␉const void *src,␊ |
63 | ␉␉␉size_t src_size)␊ |
64 | {␊ |
65 | const uint64_t rdi = (const uint64_t)dst;␊ |
66 | ␊ |
67 | size_t rax = 0;␊ |
68 | ␊ |
69 | uint64_t rsi = dst_size;␊ |
70 | uint64_t rcx = src_size;␊ |
71 | uint64_t rdx = (uint64_t)src;␊ |
72 | ␊ |
73 | uint64_t r8 = 0;␊ |
74 | uint64_t r9 = 0;␊ |
75 | uint64_t r10 = 0;␊ |
76 | uint64_t r11 = 0;␊ |
77 | uint64_t r12 = 0;␊ |
78 | ␊ |
79 | uint64_t addr = 0;␊ |
80 | unsigned char byte_data = 0;␊ |
81 | ␊ |
82 | short jmp = 0;␊ |
83 | ␊ |
84 | // lea Llzvn_tableref(%rip),%rbx␊ |
85 | //␊ |
86 | // this will load the address of the tableref label into the %rbx␊ |
87 | // register. in our code, this is the 'Llzvn_tableref' array␊ |
88 | //␊ |
89 | // for clearness, it will be used directly.␊ |
90 | ␊ |
91 | rax = 0; // xor %rax,%rax␊ |
92 | r12 = 0; // xor %r12,%r12␊ |
93 | ␊ |
94 | // sub $0x8,%rsi␊ |
95 | // jb Llzvn_exit␊ |
96 | jmp = rsi < 0x8 ? 1 : 0;␊ |
97 | rsi -= 0x8;␊ |
98 | if (jmp) {␊ |
99 | return 0;␊ |
100 | }␊ |
101 | ␊ |
102 | // lea -0x8(%rdx,%rcx,1),%rcx␊ |
103 | // cmp %rcx,%rdx␊ |
104 | ␉// ja Llzvn_exit␊ |
105 | rcx = rdx + rcx - 0x8;␊ |
106 | if (rdx > rcx) {␊ |
107 | return 0;␊ |
108 | }␊ |
109 | ␊ |
110 | LABEL_JUMP;␊ |
111 | ␊ |
112 | ␊ |
113 | ␊ |
114 | Llzvn_table0:␊ |
115 | r9 >>= 0x6; // shr $0x6,%r9␊ |
116 | rdx = rdx + r9 + 0x1; // lea 0x1(%rdx,%r9,1),%rdx␊ |
117 | ␊ |
118 | // cmp %rcx,%rdx␊ |
119 | // ja Llzvn_exit␊ |
120 | if (rdx > rcx) {␊ |
121 | return 0;␊ |
122 | }␊ |
123 | ␊ |
124 | r10 = 0x38; // mov $0x38,%r10␊ |
125 | r10 &= r8; // and %r8,%r10␊ |
126 | r8 >>= 0x8; // shr $0x8,%r8␊ |
127 | r10 >>= 0x3; // shr $0x3,%r10␊ |
128 | r10 += 0x3; // add $0x3,%r10␊ |
129 | goto Llzvn_l10; // jmp Llzvn_l10␊ |
130 | ␊ |
131 | Llzvn_table1:␊ |
132 | r9 >>= 0x6; // shr $0x6,%r9␊ |
133 | rdx = rdx + r9 + 0x2; // lea 0x2(%rdx,%r9,1),%rdx␊ |
134 | ␊ |
135 | // cmp %rcx,%rdx␊ |
136 | ␉// ja Llzvn_exit␊ |
137 | if (rdx > rcx) {␊ |
138 | return 0;␊ |
139 | }␊ |
140 | ␊ |
141 | r12 = r8; // mov %r8,%r12␊ |
142 | r12 = OSSwapInt64(r12); // bswap %r12␊ |
143 | r10 = r12; // mov %r12,%r10␊ |
144 | r12 <<= 0x5; // shl $0x5,%r12␊ |
145 | r12 >>= 0x35; // shr $0x35,%r12␊ |
146 | r10 <<= 0x2; // shl $0x2,%r10␊ |
147 | r10 >>= 0x3d; // shr $0x3d,%r10␊ |
148 | r10 += 0x3; // add $0x3,%r10␊ |
149 | r8 >>= 0x10; // shr $0x10,%r8␊ |
150 | goto Llzvn_l10;␊ |
151 | ␊ |
152 | ␊ |
153 | Llzvn_table3:␊ |
154 | r9 >>= 0x6; // shr $0x6,%r9␊ |
155 | rdx = rdx + r9 + 0x3; // lea 0x3(%rdx,%r9,1),%rdx␊ |
156 | ␊ |
157 | // cmp %rcx,%rdx␊ |
158 | // ja Llzvn_exit␊ |
159 | if (rdx > rcx) {␊ |
160 | return 0;␊ |
161 | }␊ |
162 | ␊ |
163 | r10 = 0x38; // mov $0x38,%r10␊ |
164 | r12 = 0xFFFF; // mov $0xffff,%r12␊ |
165 | r10 &= r8; // and %r8,%r10␊ |
166 | r8 >>= 0x8; // shr $0x8,%r8␊ |
167 | r10 >>= 0x3; // shr $0x3,%r10␊ |
168 | r12 &= r8; // and %r8,%r12␊ |
169 | r8 >>= 0x10; // shr $0x10,%r8␊ |
170 | r10 += 0x3; // add $0x3,%r10␊ |
171 | goto Llzvn_l10; // jmp Llzvn_l10␊ |
172 | ␊ |
173 | ␊ |
174 | Llzvn_table4:␊ |
175 | // add $0x1,%rdx␊ |
176 | // cmp %rcx,%rdx␊ |
177 | // ja Llzvn_exit␊ |
178 | rdx += 1;␊ |
179 | if (rdx > rcx) {␊ |
180 | return 0;␊ |
181 | }␊ |
182 | ␊ |
183 | LABEL_JUMP;␊ |
184 | ␊ |
185 | ␊ |
186 | Llzvn_table6:␊ |
187 | r9 >>= 0x3; // shr $0x3,%r9␊ |
188 | r9 &= 0x3; // and $0x3,%r9␊ |
189 | rdx = rdx + r9 + 0x3; // lea 0x3(%rdx,%r9,1),%rdx␊ |
190 | ␊ |
191 | // cmp %rcx,%rdx␊ |
192 | // ja Llzvn_exit␊ |
193 | if (rdx > rcx) {␊ |
194 | return 0;␊ |
195 | }␊ |
196 | ␊ |
197 | r10 = r8; // mov %r8,%r10␊ |
198 | r10 &= 0x307; // and $0x307,%r10␊ |
199 | r8 >>= 0xa; // shr $0xa,%r8␊ |
200 | ␊ |
201 | // movzbq %r10b,%r12␊ |
202 | r12 = r10 & 0xFF;␊ |
203 | ␊ |
204 | r10 >>= 0x8; // shr $0x8,%r10␊ |
205 | r12 <<= 0x2; // shl $0x2,%r12␊ |
206 | r10 |= r12; // or %r12,%r10␊ |
207 | r12 = 0x3FFF; // mov $0x3fff,%r12␊ |
208 | r10 += 0x3; // add $0x3,%r10␊ |
209 | r12 &= r8; // and %r8,%r12␊ |
210 | r8 >>= 0xE; // shr $0xe,%r8␊ |
211 | goto Llzvn_l10; // jmp Llzvn_l10␊ |
212 | ␊ |
213 | ␊ |
214 | Llzvn_table7:␊ |
215 | r8 >>= 0x8; // shr $0x8,%r8␊ |
216 | r8 &= 0xFF; // and $0xff,%r8␊ |
217 | r8 += 0x10; // add $0x10,%r8␊ |
218 | rdx = rdx + r8 + 0x2; // lea 0x2(%rdx,%r8,1),%rdx␊ |
219 | goto Llzvn_l0;␊ |
220 | ␊ |
221 | ␊ |
222 | Llzvn_table8:␊ |
223 | r8 &= 0xF; // and $0xf,%r8␊ |
224 | rdx = rdx + r8 + 0x1; // lea 0x1(%rdx,%r8,1),%rdx␊ |
225 | goto Llzvn_l0; // jmp Llzvn_l0␊ |
226 | ␊ |
227 | ␊ |
228 | Llzvn_table9:␊ |
229 | rdx += 0x2; // add $0x2,%rdx␊ |
230 | ␊ |
231 | // cmp %rcx,%rdx␊ |
232 | // ja Llzvn_exit␊ |
233 | if (rdx > rcx) {␊ |
234 | return 0;␊ |
235 | }␊ |
236 | ␊ |
237 | r10 = r8; // mov %r8,%r10␊ |
238 | r10 >>= 0x8; // shr $0x8,%r10␊ |
239 | r10 &= 0xFF; // and $0xff,%r10␊ |
240 | r10 += 0x10; // add $0x10,%r10␊ |
241 | goto Llzvn_l11;␊ |
242 | ␊ |
243 | ␊ |
244 | Llzvn_table10:␊ |
245 | rdx += 1; // add $0x1,%rdx␊ |
246 | ␊ |
247 | //cmp %rcx,%rdx␊ |
248 | ␉//ja Llzvn_exit␊ |
249 | if (rdx > rcx) {␊ |
250 | return 0;␊ |
251 | }␊ |
252 | ␊ |
253 | r10 = r8; // mov %r8,%r10␊ |
254 | r10 &= 0xF; // and $0xf,%r10␊ |
255 | goto Llzvn_l11; // jmp Llzvn_l11␊ |
256 | ␊ |
257 | ␊ |
258 | ␊ |
259 | ␊ |
260 | Llzvn_l10:␊ |
261 | r11 = rax + r9; // lea (%rax,%r9,1),%r11␊ |
262 | r11 += r10; // add %r10,%r11␊ |
263 | ␊ |
264 | // cmp %rsi,%r11␊ |
265 | ␉// jae Llzvn_l8␊ |
266 | if (r11 >= rsi) {␊ |
267 | goto Llzvn_l8;␊ |
268 | }␊ |
269 | ␊ |
270 | // mov %r8,(%rdi,%rax,1)␊ |
271 | addr = rdi + rax;␊ |
272 | *((uint64_t *)addr) = r8;␊ |
273 | ␊ |
274 | rax += r9; // add %r9,%rax␊ |
275 | r8 = rax; // mov %rax,%r8␊ |
276 | ␊ |
277 | // sub %r12,%r8␊ |
278 | ␉// jb Llzvn_exit␊ |
279 | jmp = r8 < r12 ? 1 : 0;␊ |
280 | r8 -= r12;␊ |
281 | if (jmp) {␊ |
282 | return 0;␊ |
283 | }␊ |
284 | ␊ |
285 | // cmp $0x8,%r12␊ |
286 | ␉// jb Llzvn_l4␊ |
287 | if (r12 < 0x8) {␊ |
288 | goto Llzvn_l4;␊ |
289 | }␊ |
290 | ␊ |
291 | ␊ |
292 | Llzvn_l5:␊ |
293 | do␊ |
294 | {␊ |
295 | // mov (%rdi,%r8,1),%r9␊ |
296 | addr = rdi + r8;␊ |
297 | r9 = *((uint64_t *)addr);␊ |
298 | ␊ |
299 | r8 += 0x8; // add $0x8,%r8␊ |
300 | ␊ |
301 | // mov %r9,(%rdi,%rax,1)␊ |
302 | addr = rdi + rax;␊ |
303 | *((uint64_t *)addr) = r9;␊ |
304 | ␊ |
305 | rax += 0x8; // add $0x8,%rax␊ |
306 | ␊ |
307 | // sub $0x8,%r10␊ |
308 | // ja Llzvn_l5␊ |
309 | jmp = r10 > 0x8 ? 1 : 0;␊ |
310 | r10 -= 0x8;␊ |
311 | }␊ |
312 | while (jmp);␊ |
313 | ␊ |
314 | rax += r10; // add %r10,%rax␊ |
315 | ␊ |
316 | LABEL_JUMP;␊ |
317 | ␊ |
318 | ␊ |
319 | Llzvn_l8:␊ |
320 | // test %r9,%r9␊ |
321 | ␉// je Llzvn_l7␊ |
322 | if (r9 != 0)␊ |
323 | {␊ |
324 | r11 = rsi + 0x8; // lea 0x8(%rsi),%r11␊ |
325 | ␊ |
326 | do␊ |
327 | {␊ |
328 | // mov %r8b,(%rdi,%rax,1)␊ |
329 | addr = rdi + rax;␊ |
330 | byte_data = (unsigned char)(r8 & 0xFF);␊ |
331 | *((unsigned char *)addr) = byte_data;␊ |
332 | ␊ |
333 | rax += 0x1; // add $0x1,%rax␊ |
334 | ␊ |
335 | // cmp %rax,%r11␊ |
336 | // je Llzvn_exit2␊ |
337 | if (rax == r11) {␊ |
338 | return rax;␊ |
339 | }␊ |
340 | ␊ |
341 | r8 >>= 0x8; // shr $0x8,%r8␊ |
342 | ␊ |
343 | // sub $0x1,%r9␊ |
344 | // jne Llzvn_l6␊ |
345 | jmp = r9 != 0x1 ? 1 : 0;␊ |
346 | r9 -= 1;␊ |
347 | }␊ |
348 | while (jmp);␊ |
349 | }␊ |
350 | ␊ |
351 | // mov %rax,%r8␊ |
352 | ␉r8 = rax;␊ |
353 | ␊ |
354 | // sub %r12,%r8␊ |
355 | ␉// jb Llzvn_exit␊ |
356 | jmp = r8 < r12 ? 1 : 0;␊ |
357 | r8 -= r12;␊ |
358 | if (jmp) {␊ |
359 | return 0;␊ |
360 | }␊ |
361 | ␊ |
362 | ␊ |
363 | Llzvn_l4:␊ |
364 | r11 = rsi + 0x8; // lea 0x8(%rsi),%r11␊ |
365 | ␊ |
366 | do␊ |
367 | {␊ |
368 | // movzbq (%rdi,%r8,1),%r9␊ |
369 | addr = rdi + r8;␊ |
370 | byte_data = *((unsigned char *)addr);␊ |
371 | r9 = byte_data;␊ |
372 | r9 &= 0xFF;␊ |
373 | ␊ |
374 | r8 += 0x1; // add $0x1,%r8␊ |
375 | ␊ |
376 | // mov %r9b,(%rdi,%rax,1)␊ |
377 | addr = rdi + rax;␊ |
378 | byte_data = (unsigned char)r9;␊ |
379 | *((unsigned char *)addr) = byte_data;␊ |
380 | ␊ |
381 | rax += 0x1; // add $0x1,%rax␊ |
382 | ␊ |
383 | // cmp %rax,%r11␊ |
384 | // je Llzvn_exit2␊ |
385 | if (rax == r11) {␊ |
386 | return rax;␊ |
387 | }␊ |
388 | ␊ |
389 | // sub $0x1,%r10␊ |
390 | // jne Llzvn_l9␊ |
391 | jmp = r10 != 0x1 ? 1 : 0;␊ |
392 | r10 -= 0x1;␊ |
393 | }␊ |
394 | while (jmp);␊ |
395 | ␊ |
396 | ␉LABEL_JUMP;␊ |
397 | ␊ |
398 | ␊ |
399 | Llzvn_l11:␊ |
400 | r8 = rax; // mov %rax,%r8␊ |
401 | ␉r8 -= r12; // sub %r12,%r8␊ |
402 | ␉r11 = rax + r10; // lea (%rax,%r10,1),%r11␊ |
403 | ␉␊ |
404 | // cmp %rsi,%r11␊ |
405 | ␉// jae Llzvn_l4␊ |
406 | if (r11 >= rsi) {␊ |
407 | goto Llzvn_l4;␊ |
408 | }␊ |
409 | ␊ |
410 | ␉// cmp $0x8,%r12␊ |
411 | ␉// jae Llzvn_l5␊ |
412 | if (r12 >= 0x8) {␊ |
413 | goto Llzvn_l5;␊ |
414 | }␊ |
415 | ␊ |
416 | ␉goto Llzvn_l4; // jmp Llzvn_l4␊ |
417 | ␊ |
418 | ␊ |
419 | Llzvn_l0:␊ |
420 | // cmp %rcx,%rdx␊ |
421 | ␉// ja Llzvn_exit␊ |
422 | if (rdx > rcx) {␊ |
423 | return 0;␊ |
424 | }␊ |
425 | ␊ |
426 | r11 = rax + r8; // lea (%rax,%r8,1),%r11␊ |
427 | r8 = -r8; // neg %r8␊ |
428 | ␊ |
429 | // cmp %rsi,%r11␊ |
430 | ␉// ja Llzvn_l2␊ |
431 | if (r11 <= rsi)␊ |
432 | {␊ |
433 | r11 = rdi + r11; // lea (%rdi,%r11,1),%r11␊ |
434 | ␊ |
435 | uint64_t check = 0;␊ |
436 | ␊ |
437 | do␊ |
438 | {␊ |
439 | // mov (%rdx,%r8,1),%r9␊ |
440 | addr = rdx + r8;␊ |
441 | r9 = *(uint64_t *)addr;␊ |
442 | ␊ |
443 | // mov %r9,(%r11,%r8,1)␊ |
444 | addr = r11 + r8;␊ |
445 | *(uint64_t *)addr = r9;␊ |
446 | ␊ |
447 | // add $0x8,%r8␊ |
448 | // jae Llzvn_l1␊ |
449 | ␊ |
450 | check = UINT64_MAX;␊ |
451 | check -= (uint64_t)r8;␊ |
452 | ␊ |
453 | r8 += 0x8;␊ |
454 | }␊ |
455 | while (check >= 0x8);␊ |
456 | ␊ |
457 | rax = r11; // mov %r11,%rax␊ |
458 | rax -= rdi; // sub %rdi,%rax␊ |
459 | ␊ |
460 | LABEL_JUMP;␊ |
461 | }␊ |
462 | ␊ |
463 | r11 = rsi + 0x8; // lea 0x8(%rsi),%r11␊ |
464 | ␊ |
465 | do␊ |
466 | {␊ |
467 | // movzbq (%rdx,%r8,1),%r9␊ |
468 | addr = rdx + r8;␊ |
469 | r9 = *((uint64_t *)addr);␊ |
470 | r9 &= 0xFF;␊ |
471 | ␊ |
472 | // mov %r9b,(%rdi,%rax,1)␊ |
473 | addr = rdi + rax;␊ |
474 | byte_data = (unsigned char)r9;␊ |
475 | *((unsigned char *)addr) = byte_data;␊ |
476 | ␊ |
477 | rax += 0x1; // add $0x1,%rax␊ |
478 | ␊ |
479 | // cmp %rax,%r11␊ |
480 | // je Llzvn_exit2␊ |
481 | if (r11 == rax) {␊ |
482 | return rax;␊ |
483 | }␊ |
484 | ␊ |
485 | // add $0x1,%r8␊ |
486 | // jne Llzvn_l3␊ |
487 | jmp = ((int64_t)r8 + 0x1 == 0) ? 0 : 1;␊ |
488 | r8 += 0x1;␊ |
489 | }␊ |
490 | while (jmp);␊ |
491 | ␊ |
492 | ␉LABEL_JUMP;␊ |
493 | ␊ |
494 | ␊ |
495 | // should never come here.␊ |
496 | return 0;␊ |
497 | }␊ |
498 | |