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