summaryrefslogtreecommitdiff
path: root/posts/challenges-re-writeups-2.org
diff options
context:
space:
mode:
Diffstat (limited to 'posts/challenges-re-writeups-2.org')
-rw-r--r--posts/challenges-re-writeups-2.org924
1 files changed, 924 insertions, 0 deletions
diff --git a/posts/challenges-re-writeups-2.org b/posts/challenges-re-writeups-2.org
new file mode 100644
index 0000000..cb185fc
--- /dev/null
+++ b/posts/challenges-re-writeups-2.org
@@ -0,0 +1,924 @@
+#+TITLE: Writeups for Dennis Yurichev's Reverse Engineering Challenges (#12-#22)
+#+TAGS: writeup reverse-engineering x86
+#+DATE: <2019-05-28 Tue 15:18>
+
+This is the second set of solutions for my self-imposed challenge of completing
+at least fifty of the exercises on Dennis Yurichev's [[https://challenges.re][challenges.re]] by the end of
+the year. The first set is available [[http:///jakob.space/challenges-re-writeups-1.html][here]].
+
+* Challenge #12
+
+No hints are given for this challenge, but it is the first time a binary is
+available in addition to the disassembly. I didn't download the executable, I
+was able to gather from the tags that the target is amd64 Linux.
+
+If later challenges also provide executables, I may use it as an opportunity to
+explore the NSA's newly-released [[https://www.nsa.gov/resources/everyone/ghidra/][Ghidra]]. At the time of writing this, Ghidra's
+source code has yet to be released, so I'll have to pass up the opportunity this
+time around.
+
+#+BEGIN_SRC c
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <sys/types.h>
+#include <time.h>
+#include <unistd.h>
+#include <utime.h>
+
+int main(int argc, char **argv)
+{
+ // push rbx
+ // mov rbx, rsi
+ // sub rsp, 160
+ int ret;
+ struct stat sbuf;
+ struct utimbuf tbuf;
+
+ // cmp edi, 2
+ // je .L2
+ if (argc != 2) {
+ // mov edi, OFFSET FLAT:.LC0
+ // call puts
+ puts("Usage: ");
+ }
+
+ // .L2:
+ // mov rsi, QWORD PTR [rbx+8]
+ // lea rdx, [rsp+16]
+ // mov edi, 1
+ // call __xstat
+ ret = stat(argv[1], &sbuf);
+
+ // test eax, eax
+ // js .L10
+ if (ret < 0) {
+ // .L10:
+ // mov edi, OFFSET FLAT:.LC1
+ // call puts
+ // xor edi, edi
+ // call exit
+ puts("error #1!");
+ exit(0);
+ }
+
+ // mov rax, QWORD PTR [rsp+88]
+ // xor edi, edi
+ // mov QWORD PTR [rsp], rax
+ tbuf.actime = sbuf.st_atim.tv_sec;
+
+ // call time
+ /// ...
+ // mov QWORD PTR [rsp+8], rax
+ tbuf.modtime = time(NULL);
+
+ // mov rdi, QWORD PTR [rbx+8]
+ // mov rsi, rsp
+ // call utime
+ ret = utime(argv[1], &tbuf);
+
+ // test eax, eax
+ // js .L11
+ if (ret < 0) {
+ // .L11:
+ // mov edi, OFFSET FLAT:.LC2
+ // call puts
+ // xor edi, edi
+ // call exit
+ puts("error #2!");
+ exit(0);
+ }
+
+ // add rsp, 160
+ // xor eax, eax
+ // pop rbx
+ // ret
+ return 0;
+}
+#+END_SRC
+
+The first thing that may stand out in the disassembly listing is =call __xstat=.
+=__xstat= isn't part of the C standard library or POSIX. My understanding of
+functions like these is that sometimes an interface like =stat= will result in a
+call to some internal libc routine when compiled, but the only time I've seen
+this before was with =__printf_chk=. Regardless, search engines are your friend,
+and you should have no trouble arriving at the [[http://refspecs.linuxbase.org/LSB_3.0.0/LSB-PDA/LSB-PDA/baselib-xstat-1.html][relevant page]] in the Linux
+Standard Base Specification. One interesting thing of note is the comment that
+"=ver= shall be =3= or the behavior of these functions is undefined," yet the
+disassembly indicates that =ver= is =1=. I'm doubtful that this is part of the
+challenge, though.
+
+I also just guessed that =QWORD PTR [rsp+88]= was =sbuf.st_atim.tv_sec=, given the
+context that the value is used in. Going from assembly to the corresponding
+fields of a struct is a pain without a tool, which is perhaps an indication that
+I should've downloaded the binary and used Ghidra^h^h^h^h^h^hradare2 to prod at
+it.
+
+Either way, the code updates a file's modification time. It's comparable to
+=touch=, but doesn't create the file if it doesn't exist. The strings are
+intentionally vague, so here's a cleaned up version:
+
+#+BEGIN_SRC c
+#include <errno.h>
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+ struct stat sbuf;
+ struct utimbuf tbuf;
+
+ if (argc != 2) {
+ printf("Usage: %s [path]\n", argv[0]);
+ }
+
+ if (stat(argv[1], &sbuf) < 0) {
+ printf("%s: %s\n", argv[1], strerror(errno));
+ exit(0);
+ }
+
+ tbuf.actime = sbuf.st_atim.tv_sec;
+ tbuf.modtime = time(NULL);
+
+ if (utime(argv[1], &tbuf) < 0) {
+ printf("utime: %s\n", strerror(errno));
+ exit(0);
+ }
+
+ return 0;
+}
+#+END_SRC
+
+* Challenge #13
+
+The question for this exercise is, "[w]hat does this SSE code do?" Uh oh. I
+don't know anything about SSE. Not the end of the world, though. I always
+appreciate an opportunity to learn. Here are some notes I took on chapter 25 of
+Yurichev's book:
+
+_Vectorization_ is the process of taking several arrays as input and producing a
+single array as output. SIMD (Single Instruction, Multiple Data) is a way of
+optimizing vectorization by doing certain array-level operations in parallel.
+
+Intel's initial implementation of SIMD reused FPU register. SSE added 128-bit
+registers (%xmm*) that were separate from the FPU, and AVX added 256-bit
+registers that were separate from the FPU.
+
+Well, that doesn't seem too complicated, and the exercise only uses two
+instructions: =movdqu=, which loads a 16-byte value from memory into an %xmm*
+register, and =pmaxub=, which calculates the maximum values between two %xmm*
+registers.
+
+#+BEGIN_SRC c
+void f(int *dest, int *a, int *b)
+{
+ int i;
+
+ // xor rax, rax
+ // ...
+ // add rax, 16
+ // cmp rax, 1024
+ // jne .L4
+ // ...
+ // .L4:
+ for (i = 0; i < 256; i++) {
+ // movdqu xmm0, XMMWORD PTR [rsi+rax]
+ // movdqu xmm1, XMMWORD PTR [rdx+rax]
+ // pmaxub xmm0, xmm1
+ // movdqu XMMWORD PTR [rdi+rax], xmm0
+ dest[i] = a[i] > b[i] ? a[i] : b[i];
+ }
+
+ // rep ret
+ return;
+}
+#+END_SRC
+
+=f= will fill an array, =dest=, such that the element at each index contains the
+greater value between =a= and =b= for that index.
+
+* Challenge #14
+
+The challenge description explains that, "[n]ow that's easy," and gives both
+.NET and Java bytecode disassemblies. I am not familiar with either bytecode
+format, but I do know Java (unfortunately), so I went with that.
+
+#+BEGIN_SRC java
+public class Challenge14 {
+ public static boolean f(char a) {
+ // 0: iload_1
+ // 1: bipush 97
+ // 3: if_icmplt 14
+ // 6: iload_1
+ // 7: bipush 122
+ // 9: if_icmpgt 14
+ if (a < 97 || a > 122) {
+ // 14: iload_1
+ // 15: bipush 65
+ // 17: if_icmplt 28
+ // 20: iload_1
+ // 21: bipush 90
+ // 23: if_icmpgt 28
+ if (a < 65 || a > 90) {
+ // 28: iconst_0
+ // 29: ireturn
+ return false;
+ }
+
+ // 26: iconst_1
+ // 27: ireturn
+ return true;
+ }
+
+ // 12: iconst_1
+ // 13: ireturn
+ return true;
+ }
+}
+#+END_SRC
+
+I'm not particularly confident in my translation -- the above is the result of
+skimming the [[https://en.wikipedia.org/wiki/Java_bytecode][Java bytecode]] and [[https://en.wikipedia.org/wiki/Java_bytecode_instruction_listings][Java bytecode instruction listings]] pages on
+Wikipedia -- but that translation does appear to convey a meaningful operation:
+telling whether or not =a= is an ASCII letter.
+
+* Challenge #15
+
+The challenge description explains that, "[n]ow that's really easy."
+
+#+BEGIN_SRC c
+void f(char *dst)
+{
+ int i;
+
+ // xorps %xmm0, %xmm0
+ // movups %xmm0, 240(%rdi)
+ // movups %xmm0, 224(%rdi)
+ // movups %xmm0, 208(%rdi)
+ // movups %xmm0, 192(%rdi)
+ // movups %xmm0, 176(%rdi)
+ // movups %xmm0, 160(%rdi)
+ // movups %xmm0, 144(%rdi)
+ // movups %xmm0, 128(%rdi)
+ // movups %xmm0, 112(%rdi)
+ // movups %xmm0, 96(%rdi)
+ // movups %xmm0, 80(%rdi)
+ // movups %xmm0, 64(%rdi)
+ // movups %xmm0, 48(%rdi)
+ // movups %xmm0, 32(%rdi)
+ // movups %xmm0, 16(%rdi)
+ // movups %xmm0, (%rdi)
+ // ret
+ for (i = 0; i < 256; i++) {
+ dst[i] = '\0';
+ }
+}
+#+END_SRC
+
+I initially read the disassembly for this challenge as if it were Intel syntax,
+but it's AT&T. The operation is simple: =f= zeroes out a 256-byte buffer specified
+by the first parameter.
+
+* Challenge #16
+
+Only one disassembly is given for this challenge, and the description hints that
+it is from Clang: "[n]ow this is getting harder. Clang did a lot of optimization
+tricks and this code is heavily optimized for SSE2. Nevertheless, the original
+function is tiny and simple. What does it do?"
+
+In all honesty, I don't think that a translation to C is helpful. As the problem
+mentioned, there's heavy optimization for SSE2, and the assembly code only
+tangentially corresponds to what (I believe) is going on. Instead, I'll attempt
+to justify my partial conclusion that =f= sums an array of integers.
+
+Bytes from =rdi= (indexed with =rcx=) are interleaved into =xmm0= and =xmm2= with
+=pinsrw=, and continually added into =xmm3= and =xmm4=. Then, =xmm0= and =xmm2= are added,
+and =xmm1= is unpacked with =punpckhqdq xmm1, xmm1=. The pseudocode for the
+=punpckhqdq= instruction is given as:
+
+#+BEGIN_SRC c
+Destination[0..63] = Destination[64..127];
+Destination[64..127] = Source[64..127];
+#+END_SRC
+
+So it's unusual to see =xmm1= as both the "Source" and "Destination". This is
+followed by a =paddq xmm1, xmm0=.
+
+I can't really confirm any of this because of the =movdqa xmm1, xmmword ptr
+[rip + .LCPI0_0]= instruction. Some sort of mask is being used in those =pand
+xmm0, xmm1= and =pand xmm2, xmm1= instructions, and I suspect that it's one of many
+tricks coming together so the function works for an array of _integers_, but we
+aren't given =.LCPI0_0=, so I can't tell for sure.
+
+This also means that I can't assemble what's given. If anyone out there is
+experienced in SIMD and would to share some tips for making sense of this one,
+I'd really appreciate it.
+
+* Challenge #17
+
+The description explains that "[t]his is a quite esoteric piece of code, but
+nevertheless, the task it does is very mundane and well-known to anyone. The
+function has 4 32-bit arguments and returns a 32-bit one."
+
+#+BEGIN_SRC c
+int f(int a, int b, int c, int d)
+{
+ int tmp1, tmp2;
+
+ // sub edx, edi
+ c -= a;
+
+ // mov r8d, ecx
+ // ...
+ // sub r8d, esi
+ tmp1 = d - b;
+
+ // mov ecx, 63
+ d = 63;
+
+ // mov eax, edx
+ // sar eax, cl
+ // and eax, edx
+ tmp2 = (c >> (d & 0xff)) & c;
+
+ // mov edx, r8d
+ // sar edx, cl
+ // ...
+ // and edx, r8d
+ c = (tmp1 >> (d & 0xff)) & tmp1;
+
+ // add edi, eax
+ a += tmp2;
+
+ // add esi, edx
+ // sub esi, edi
+ b += c - a;
+
+ // mov eax, esi
+ // sar eax, cl
+ // and eax, esi
+ // add eax, edi
+ // ret
+ return ((b >> (d & 0xff)) & b) + a;
+}
+#+END_SRC
+
+The initial translation is quite messy, but observe that =d= has a constant value
+of =63=, and =63 & 0xff= is just =63=. Still, there are a number of snippets that look
+like =(c >> (d & 0xff)) & c=, and it isn't obvious what that does.
+
+#+BEGIN_SRC c
+int black_box(int a)
+{
+ return (a >> 63) & a;
+}
+
+int main(void)
+{
+ int i;
+
+ for (i = 0; i >= 0; i += 1) {
+ if (black_box(i) != 0) {
+ printf("black_box(%d) = %d\n", i, black_box(i));
+ }
+ }
+
+ for (i = 0; i <= 0; i -= 1) {
+ if (black_box(i) != i) {
+ printf("black_box(%d) = %d\n", i, black_box(i));
+ }
+ }
+
+
+ return 0;
+}
+#+END_SRC
+
+#+BEGIN_SRC
+re.c: In function 'black_box':
+re.c:64:13: warning: right shift count >= width of type [-Wshift-count-overflow]
+ return (a >> 63) & a;
+ ^~
+#+END_SRC
+
+I'm not sure if this is the intended behavior, but on amd64, this acts as
+\(min(x, 0)\). A first step at simplification can be made.
+
+#+BEGIN_SRC c
+#define MIN(a, b) (a < b ? a : b)
+
+int f(int a, int b, int c, int d)
+{
+ a += MIN(c - a, 0);
+ c = MIN(d - b, 0);
+ b += c - a;
+ return MIN(b, 0) + a;
+}
+#+END_SRC
+
+And this can be further cleaned up into a one-liner.
+
+#+BEGIN_SRC c
+#define MIN(a, b) (a < b ? a : b)
+
+int f(int a, int b, int c, int d)
+{
+ return a + \
+ MIN(b - a + MIN(d - b, 0) - MIN(c - a, 0), 0) + \
+ MIN(c - a, 0);
+}
+#+END_SRC
+
+And this happens to be an interesting implementation of \(min(a, b, c, d)\).
+
+* Challenge #18
+
+For challenges with more complicated control flow, I've been drawing the basic
+blocks out on a sheet of paper and drawing arrows between them to identify which
+transitions represent loops, and which transitions represent conditionals. That
+didn't work particularly well for this challenge, though. The solution instead
+came to me instead by just staring at the disassembly for some time.
+
+#+BEGIN_SRC c
+#include <ctype.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+int f3(char *a, uint64_t *b, uint64_t *c, uint64_t *d, uint64_t *e, uint64_t *f)
+{
+ int i;
+ char *cur;
+
+ if (strlen(a) != 36) {
+ return a;
+ }
+
+ cur = a;
+ i = 0;
+
+ while (i != 37) {
+ if (i == 8 || i == 13 || i == 18 || i == 23) {
+ if (*cur != '-') {
+ return (char *) -1;
+ }
+ } else {
+ if (i == 36 && *cur == '\0') {
+ break;
+ }
+
+ if (!isxdigit(*cur)) {
+ return (char *) -1;
+ }
+ }
+
+ i++;
+ cur++;
+ }
+
+ *b = strtoul(a, NULL, 16);
+ *c = strtoul(a + 9, NULL, 16);
+ *d = strtoul(a + 14, NULL, 16);
+ *e = strtoul(a + 19, NULL, 16);
+ *f = strtoull(a + 24, NULL, 16);
+ return 0;
+}
+#+END_SRC
+
+The code appears to implement a [[https://en.wikipedia.org/wiki/Universally_unique_identifier][UUID]] parser.
+
+* Challenge #19
+
+This challenge was particularly difficult. I began by translating the individual
+basic blocks to C, and connecting them with =goto=.
+
+#+BEGIN_SRC c
+#include <stdlib.h>
+#include <stdio.h>
+
+char *f2_bb(char *a, int b, int c, char *d)
+{
+ // rax <- a
+ // rbx <- a
+
+ // QWORD PTR [rsp+24] <- d
+ // QWORD PTR [rsp+16] <- b
+ // QWORD PTR [rsp+8] <- c
+
+ int i;
+ int j;
+ int k;
+ int *ret;
+
+ // f2:
+ {
+ // test rcx, rcx
+ // jne .L21
+ if (c == 0) {
+ // add rsp, 32
+ // pop rbx
+ // ret
+ return a;
+ }
+
+ goto BBL21;
+ }
+
+ // .L21:
+ {
+ BBL21:
+ // lea rdi, [4+rcx*4]
+ // ...
+ // call malloc
+ ret = malloc(c * 4 + 4);
+
+ // ...
+ // mov DWORD PTR [rax], -1
+ ret[0] = -1;
+
+ // ...
+ // mov DWORD PTR [rax+4], 0
+ ret[1] = 0;
+
+ // mov r9d, 1
+ i = 1;
+
+ // ...
+ // cmp r9, rcx
+ // je .L22
+ if (c == 1) {
+ goto BBL22;
+ }
+
+ goto BBL8;
+ }
+
+ // .L8:
+ {
+ BBL8:
+ // mov edi, DWORD PTR [rax+r9*4]
+ // lea r8d, [rdi+1]
+ // test r8d, r8d
+ // mov DWORD PTR [rax+4+r9*4], r8d
+ if ((ret[i + 1] = ret[i] + 1) <= 0) {
+ // jle .L5
+ goto BBL5;
+ }
+
+ // movzx r10d, BYTE PTR [rdx+r9]
+ // movsx r8, r8d
+ // cmp r10b, BYTE PTR [rdx-1+r8]
+ if (d[i] != d[ret[i + 1] - 1]) {
+ // jne .L7
+ goto BBL7;
+ }
+
+ // jmp .L5
+ goto BBL5;
+ }
+
+ // .L7:
+ {
+ BBL7:
+ // mov r8d, DWORD PTR [rax-4+r8*4]
+ // add r8d, 1
+ // test r8d, r8d
+ // mov DWORD PTR [rax+4+r9*4], r8d
+ if ((ret[i + 1] = ret[ret[i + 1] - 1] + 1) > 0) {
+ // jg .L23
+ goto BBL23;
+ }
+
+ goto BBL5;
+ }
+
+ // .L23:
+ {
+ BBL23:
+ // movsx r8, r8d
+ // cmp BYTE PTR [rdx-1+r8], r10b
+ if (d[ret[i + 1] - 1] == ret[i]) {
+ // je .L5
+ goto BBL5;
+ }
+
+ goto BBL7;
+ }
+
+ // .L5:
+ {
+ BBL5:
+ // add r9, 1
+ // cmp r9, rcx
+ if (++i != c) {
+ // jne .L8
+ goto BBL8;
+ }
+
+ goto BBL22;
+ }
+
+ // .L22:
+ {
+ BBL22:
+ // xor r8d, r8d
+ // xor r10d, r10d
+ // xor edi, edi
+ i = j = k = 0;
+ goto BBL9;
+ }
+
+ // .L9:
+ {
+ BBL9:
+ // cmp rdi, rsi
+ // jae .L24
+ if (j >= b) {
+ goto BBL24;
+ }
+
+ goto BBL14;
+ }
+
+ // .L14:
+ {
+ BBL14:
+ // test r8d, r8d
+ if (i < 0) {
+ // js .L10
+ goto BBL10;
+ }
+
+ // movsx r9, r8d
+ // movzx r11d, BYTE PTR [rdx+r9]
+ // cmp BYTE PTR [rbx+rdi], r11b
+ if (d[i] == a[j]) {
+ // je .L10
+ goto BBL10;
+ }
+
+ // cmp rdi, rsi
+ // mov r8d, DWORD PTR [rax+r9*4]
+ i = ret[i];
+
+ if (j < b) {
+ // jb .L14
+ goto BBL14;
+ }
+
+ goto BBL24;
+ }
+
+ // .L10:
+ {
+ BBL10:
+ // add r8d, 1
+ // add r10d, 1
+ // movsx rdi, r8d
+ j = ++i;
+ k++;
+
+ // cmp rdi, rcx
+ if (j == c) {
+ // je .L18
+ goto BBL18;
+ }
+
+ // movsx rdi, r10d
+ j = k;
+
+ // jmp .L9
+ goto BBL9;
+ }
+
+ // .L18:
+ {
+ BBL18:
+ // movsx r10, r10d
+ // sub r10, rcx
+ k -= c;
+
+ // add rbx, r10
+ a += k;
+
+ // jmp .L13
+ goto BBL13;
+ }
+
+
+ // .L24:
+ {
+ BBL24:
+ // xor ebx, ebx
+ a = NULL;
+ goto BBL13;
+ }
+
+ // .L13:
+ {
+ BBL13:
+ // mov rdi, rax
+ // call free
+ free(ret);
+
+ // add rsp, 32
+ // mov rax, rbx
+ // pop rbx
+ // ret
+ return a;
+ }
+
+}
+#+END_SRC
+
+#+BEGIN_SRC c
+char *f2(char *a, int b, int c, char *d)
+{
+ int i;
+ int j;
+ int k;
+ int *ret;
+
+ if (c == 0) {
+ return a;
+ }
+
+ ret = malloc((c + 1) * sizeof(int));
+ ret[0] = -1;
+ ret[1] = 0;
+
+ i = 1;
+
+ do {
+ if ((ret[i + 1] = ret[i] + 1) > 0
+ && d[i] != d[ret[i] - 1]) {
+ while ((ret[i + 1] = ret[ret[i + 1] - 1] + 1) > 0) {
+ if (d[ret[i + 1] - 1] == ret[i]) {
+ break;
+ }
+ }
+ }
+ } while (++i < c);
+
+ i = j = k = 0;
+
+ while (j < b) {
+ if (i < 0 || d[i] == a[j]) {
+ j = ++i;
+ k++;
+
+ if (j == c) {
+ free(ret);
+ return a + k - c;
+ }
+
+ j = k;
+ }
+ i = ret[i];
+ }
+
+ free(ret);
+ return NULL;
+}
+#+END_SRC
+
+This challenge was nightmarishly difficult. I plan to come back to it near the
+end of the year, but for now, consider this challenge incomplete. I've been
+banging my head against a wall trying to make sense of it for a number of weeks
+now, and I still don't have a good answer for what it does.
+
+* Challenge #20
+
+Another challenge described as "easy." This time, it really is.
+
+#+BEGIN_SRC c
+#include <stdlib.h>
+
+float f4()
+{
+ return rand() * ((float) 4.65661287307739257813e-10);
+}
+#+END_SRC
+
+I did defer to an ISA reference for =cvtsi2ss= and =mulss= as I'm not particularly
+familiar with x86's floating point instructions. This challenge also gave me an
+opportunity to use [[https://float.exposed/0x30000000][float.exposed]] to turn =.long 805306368= into a floating point
+constant, but \(4.65661287307739257813 \cdot 10^{-10}\) isn't any more
+comprehensible. The purpose of =f4= is clearer when observing the output.
+
+#+BEGIN_SRC prog
+...
+0.086556
+0.535690
+0.176955
+0.791683
+0.575702
+0.418118
+0.952373
+...
+#+END_SRC
+
+=f4= returns a random floating point number on the range \([0, 1]\).
+
+* Challenge #21
+
+I was able to complete the translation for this challenge in under five minutes,
+which I'm quite proud of.
+
+#+BEGIN_SRC c
+#include <string.h>
+
+int f1(char *a, char *b)
+{
+ // rbp <- a
+ // rbx <- b
+
+ int offset;
+
+ // push r12
+ // push rbp
+ // mov rbp, rdi
+ // push rbx
+ // mov rbx, rsi
+ // call strlen
+ // mov rdi, rbx
+ // mov r12, rax
+ // call strlen
+ // sub r12, rax
+ offset = strlen(a) - strlen(b);
+
+ // mov rsi, rbx
+ // lea rdi, [rbp+0+r12]
+ // call strcmp
+ // pop rbx
+ // test eax, eax
+ // pop rbp
+ // sete al
+ // pop r12
+ // ret
+ return strcmp(a + offset, b) ? 1 : 0;
+}
+#+END_SRC
+
+=f= is a simple "ends with" predicate function. It returns =1= if =a= ends with the
+substring =b=.
+
+* Challenge #22
+
+I stopped when I got to the =// ...=. I'd figured it out by then, and =-Os= made the
+assembly for this quite messy.
+
+#+BEGIN_SRC c
+int f2(int *a, int b, int *c, int d)
+{
+ // rcx <- a[b]
+ // eax <- d + 1
+ // ebp <- c[0]
+
+ int i; // r8
+ int j;
+ int *cur;
+
+ i = d + 1;
+ j = 0;
+
+ while (j < i){
+ while (c[j + 1] <= c[0] && j < d)
+ j++;
+
+ cur = &a[i - 1];
+ while (*cur-- > c[0]);
+
+ if (j < i) {
+ c[j + 1] ^= *(cur + 1);
+ *cur ^= *(cur + 1);
+ c[j + 1] ^= *cur;
+ }
+ }
+
+ c[0] ^= *(cur + 1);
+ // ...
+
+ return 0;
+}
+
+void f1(int *a, int b, int *c, int d)
+{
+ int ret;
+
+ while (b < d) {
+ ret = f2(a, b, c, d);
+ f1(a, b, c, ret - 1);
+ b = ret + 1;
+ }
+}
+#+END_SRC
+
+The hint for this challenge is that "[t]his can be tricky, but the algorithm is
+well known and heavily used almost everywhere," which gave it away once I got to
+the mess of =xor= instructions. This is the [[https://en.wikipedia.org/wiki/XOR_swap_algorithm][XOR swap algorithm]], extended so that
+it reverses the contents of =a= and =c=.
+
+#+BEGIN_EXPORT html
+<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/latest.js?config=TeX-MML-AM_CHTML"></script>
+#+END_EXPORT
generated by cgit v1.3 (git 2.53.0) at 2026-08-29 16:17:38 +0000