<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Hard Mode - Medium]]></title>
        <description><![CDATA[coding and video games - Medium]]></description>
        <link>https://medium.com/hard-mode?source=rss----f0c797c030df---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Hard Mode - Medium</title>
            <link>https://medium.com/hard-mode?source=rss----f0c797c030df---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sat, 21 Nov 2026 21:06:39 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/hard-mode" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[NES Emulator - Writing a Disassembler and Memory Viewer]]></title>
            <link>https://medium.com/hard-mode/nes-emulator-writing-a-disassembler-and-memory-viewer-4727e76de57?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/4727e76de57</guid>
            <category><![CDATA[gaming]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[emulator]]></category>
            <category><![CDATA[videogames]]></category>
            <category><![CDATA[c]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Tue, 25 Apr 2023 05:31:06 GMT</pubDate>
            <atom:updated>2023-04-26T23:14:24.030Z</atom:updated>
            <content:encoded><![CDATA[<p>Over the previous weekend (April 14–16 2023) the <a href="https://handmade.network/">Handmade Network</a> held a programming jam called <a href="https://handmade.network/jam/visibility-2023/">Visibility Jam</a>. The goal was to spend a weekend building something that helps bring visibility to things that are obscured or hidden in computing. My previous personal project was a <a href="https://github.com/bitwitch/nes-emulator">NES emulator</a>, and I thought it would be cool to use the <a href="https://handmade.network/jam">Visibility Jam</a> to program some features that provide visibility into the system. I was able to complete a few of the ideas I originally had:</p><ul><li>Visualizing the pattern table memory on a cartridge (basically showing the sprites used in the game)</li><li>Writing a disassembler and displaying 6502 assembly you can step through as the game runs</li><li>Memory viewer</li></ul><p>I had a lot of fun and I would like to share what I worked on.</p><p>If you’re the type that just wants to read the code, you can find it <a href="https://github.com/bitwitch/nes-emulator">here</a>.</p><h3>Visualizing the Pattern Table Memory</h3><p>I want to first briefly describe how graphics are represented in the NES. The graphics data for a particular game are stored in a chip on the cartridge called CHR memory. The image below is my copy of Double Dragon III; you can see the CHR memory is the large chip on the right.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*WCRlA4DmCMbqY8xKIwPowQ.jpeg" /><figcaption>Cartridge board for Double Dragon III</figcaption></figure><p>The chip responsible for drawing these graphics to the screen — or more precisely for generating a composite video signal — is called the picture processing unit (PPU). The PPU fetches graphics data from the cartridge using an 8 KB region of the PPU address space from 0x0000–0x1FFF known as the <strong>pattern table</strong>. The pattern table is divided into two sections of 256 tiles each. These sections are often referred to as pattern table 0 and pattern table 1.</p><p>Each tile is 8x8 pixels and is represented by 16 bytes that are split into two bit-planes. For each pixel in the tile, one bit from each plane combine together to encode a palette index for that pixel. Which palette to use and the colors in each palette can be changed dynamically to change the colors of tiles.</p><p>That should give you a rough understanding of how graphics are represented, but if you are interested in learning more specific details I recommend checking out the fantastic <a href="https://www.nesdev.org/wiki/Nesdev_Wiki">NESdev Wiki</a>, where I learned basically everything I know about the NES.</p><p>Okay, so to refocus on the task at hand, in order to visualize these pattern tables I needed to read through the pattern table region of the PPU address space (0x0000–0x1FFF), decode a palette index for each pixel, and get the corresponding color for the index in the currently selected palette. Each of these colors is then stored in a pixel buffer that is 128x128 pixels. To make this process more concrete, here is the code from my emulator:</p><pre>// for each pattern table<br>for (int table=0; table&lt;2; ++table)<br>// for each tile in the pattern table<br>for (int tile_row=0; tile_row&lt;16; ++tile_row)<br>for (int tile_col=0; tile_col&lt;16; ++tile_col) {<br>    int pixel_start = (tile_row*pitch+tile_col)*8;<br>    uint16_t tile_start = table*0x1000 + tile_row*0x100 + tile_col*0x10;<br>    // for each row in the tile<br>    for (int tile_y=0; tile_y&lt;8; ++tile_y) {<br>        uint8_t plane0 = ppu_bus_read(tile_start+tile_y);<br>        uint8_t plane1 = ppu_bus_read(tile_start+tile_y+8);<br>        // for each col in the tile<br>        for (int tile_x=0; tile_x&lt;8; ++tile_x) {<br>            int i = pixel_start + tile_y*pitch + (7-tile_x);<br>            int pal_index = (plane0 &amp; 1) | ((plane1 &amp; 1) &lt;&lt; 1);<br>            uint32_t color = get_color_from_palette(selected_palette, pal_index);<br>            pattern_tables[table].pixels[i] = color;<br>            plane0 &gt;&gt;= 1; plane1 &gt;&gt;= 1;<br>        }<br>    }<br>}</pre><p>Now for the fun part! We can pop in some game cartridges and see what the pattern tables look like!</p><p>(BTW: “popping in a game cartridge” is way more satisfying on a real NES: grabbing that chunky plastic cartridge, sliding it into the slot, pressing it in and feeling the teeth at the back grip the cartridge, and pressing the whole slot down vertically, locking it into place with a satisfying click!)</p><p>Here are some screenshots of pattern tables from some of my favorite games as a kid. Oh the nostalgia! The pattern table on the left is what the PPU reads from 0x0000–0x0FFF, and the right one is from 0x1000–0x1FFF.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*nRZcb94z2upLbzB8yqithw.png" /></figure><h3>Disassembler</h3><p>My next goal with the debug window was to display the CPU state and the game’s code, and let the user step through the code as the game runs. To understand how this works requires a little bit more explanation about the CPU and game cartridges.</p><p>The CPU used in the NES was an 8-bit microprocessor designed by MOS Technologies called the 6502. This was the same CPU used in some of the influential 8-bit home computers like the Apple II and Commodore 64. The actual chip used in the NES was a custom 6502 manufactured by Ricoh that had both the 6502 CPU and the audio processing unit (APU) on the same chip. There is some curious lore surrounding this chip, how Ricoh cloned the 6502, and whether it was licensed by MOS Technologies or not. If you are interested in investigating further you can start <a href="https://www.copetti.org/writings/consoles/nes/#a-bit-of-context">here</a>.</p><p>Similar to the PPU discussed in the previous section, the CPU communicates with other devices on the NES over a bus by simply reading from or writing to addresses. It has a 64 KB address space in which the game cartridge is accessible from 0x4020–0xFFFF. There is a special register inside the CPU called the program counter or instruction pointer that always holds the address of the next instruction for the CPU to execute. So to fetch an instruction from the cartridge the CPU looks at the address in the program counter, reads an instruction from that address, and advances the program counter.</p><p>Remember that the goal is to visualize this process in the debug window, so we need to display the instruction corresponding to the CPU’s program counter and ideally some instructions surrounding it for context. In order to display an instruction in human readable assembly form, we need to decode the raw bytes — aka machine code — stored in memory on the cartridge. This process is called <strong>disassembling</strong>.</p><p>For example if we are given the byte stream <strong>AD 10 30</strong>, we need to disassemble that into the instruction<strong> LDA $3010</strong> (which means load register A with the value at memory address 0x3010). The 6502 has variable length instructions; they can be either one, two, or three bytes long. The length of the instruction depends on the addressing mode. In the example<strong> LDA $3010</strong>, the addressing mode is called absolute addressing and requires two additional bytes after the opcode to encode the memory address. To disassemble an arbitrary instruction, we start by reading the first byte of the instruction which is the opcode. The opcode encodes both the kind of operation (add, subtract, load, store, etc.) and the addressing mode. The strategy I used was to create a table of instructions indexed by opcode. You can lookup the instruction in the table to determine the addressing mode, which tells you how many more bytes to read for this instruction. After reading all the necessary instruction bytes, we perform a straightforward translation of the opcode to its assembly mnemonic and the addressing mode into assembly syntax.</p><p>As you can see, the procedure for disassembling an instruction is relatively simple. The bulk of the work involved in facilitating disassembly is just creating the instruction table. There are a number of 6502 datasheets that were published, from <a href="http://archive.6502.org/datasheets/mos_6500_mpu_nov_1985.pdf">MOS</a> and <a href="http://archive.6502.org/datasheets/rockwell_r650x_r651x.pdf">Rockwell</a> for example, that contain instruction tables that can more or less be directly translated. My favorite resource for referencing the 6502 instruction set, however, is <a href="https://masswerk.at/6502/6502_instruction_set.html">this wonderful website</a>. In my case, I had already written the instruction table since I had to in order to emulate the 6502 CPU in the first place.</p><p>Okay so now that we understand how to disassemble instructions, your first thought might be to just disassemble all the code on the cartridge a single time when the emulator boots up, starting at 0x4020 and stopping at 0xFFFF. However, there is an important piece of the puzzle which we have not discussed yet that makes this approach inviable: <strong>mappers</strong>.</p><h4>Mappers</h4><p>The address space that the CPU uses to access the cartridge is fixed to the range 0x4020–0xFFFF. If the code on a cartridge is directly mapped into this address space then the maximum amount of code that particular game can contain is just under 48 KB. In fact there are many NES games that do just that. However, if a game wants to use more than 48 KB of code then it has to map different chunks of its code into and out of the CPU’s address space continually as the game runs. This remapping of addresses is what a <strong>mapper </strong>does. If we revisit the image of the Double Dragon III board, you can see the mapper chip in the bottom left.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*0rWBGwPgKZOBe4Xw8J7EnA.jpeg" /><figcaption>Cartridge board for Double Dragon III</figcaption></figure><p>Mappers can extend not only the code capacity of a cartridge, but also the graphics capacity since a mapper could also map different chunks of graphics data into and out of the PPU address space. This leads to the larger point that game developers could hypothetically manufacture mapper chips that do any arbitrary thing they want. This is part of what makes the job of a NES emulator developer difficult, you have to emulate the mapper chip for every game that you want your emulator to support. Fortunately, there are some common ones that a lot of games used and you can get a lot of mileage out of emulating just a handful of mappers.</p><p>Back to the problem of disassembling, the reason you cannot just disassemble all the code in a game once at startup is because any address can potentially be remapped to a different location by the mapper as the game is running. This suggests that some form of dynamic disassembly must be employed. As the game runs, we need to continually disassemble how ever many instructions we want to display. You can think of this as a moving window in the address space. I wanted to show the current instruction highlighted in the middle, a few of the previously executed instructions displayed above it, and a few of the following instructions displayed below it.</p><p>Disassembling previously executed instructions presents a problem: since the 6502 has variable length instructions, given the current address in the program counter you don’t know how far back to go to reach the start of a previous instruction. You might consider stepping back by one byte at a time and testing for opcodes, but it is entirely possible for a byte that represents a memory address to also be a valid opcode and there is no way to differentiate the two. My solution to this problem was to just cache a certain number of instruction addresses. The program counter could be cached before each instruction that the CPU executes, replacing the oldest address in cache. Here is the API for storing and retrieving cached instruction addresses in my emulator:</p><pre>uint16_t cached_ins_addrs[MAX_CACHED_INS];<br>int cached_ins_index;<br><br>void cache_ins_addr(uint16_t addr) {<br>    cached_ins_addrs[cached_ins_index] = addr;<br>    cached_ins_index = (cached_ins_index+1) % MAX_CACHED_INS;<br>}<br><br>uint16_t get_cached_ins_addr_at(int num_prev_ins) {<br>    assert(num_prev_ins &lt; MAX_CACHED_INS);<br>    int index = cached_ins_index - num_prev_ins;<br>    if (index &lt; 0) index += MAX_CACHED_INS;<br>    return cached_ins_addrs[index];<br>}</pre><p><strong>cached_ins_addrs</strong> is a ring buffer of addresses. When you cache an address, a cursor is incremented and wraps around to zero once it reaches the end of the buffer. When you want to get the address of the instruction that was executed say five instructions ago, you call <strong>get_cached_ins_addr_at(5)</strong>. This simple system enables disassembling n previously executed instructions, where n is the size of the ring buffer.</p><p>Disassembling future instructions is straightforward. Since an opcode tells you how many bytes an instruction contains, the address where the next instruction begins is unambiguous.</p><p>Now we have the full picture for disassembling. Say we want to display 14 instructions in the debug window: we use the cached instruction addresses to disassemble 6 previous instructions, then we disassemble the current instruction in the program counter, and finally we disassemble 7 instructions following that. If we also include a print out of the current state of all the CPU registers then we finally have our completed debug window!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/506/1*UqOwWpNMyi__bNC-LLyhlA.gif" /><figcaption>Visualizing CPU state and stepping through disassembled instructions</figcaption></figure><p>You can see the current instruction is highlighted pink. As you step through instructions, the CPU executes each one and you can see the registers update accordingly.</p><p>The last piece that is interesting to talk about with respect to disassembling is the memory management strategy. Since we are continually disassembling different chunks of memory, we have to generate new assembly strings for each frame that the emulator renders. The naïve strategy in C would be to just malloc and free all of the strings we generate. Another more efficient but less flexible strategy could be to just have a hardcoded number of static buffers and write the assembly strings into these. I found that I could get the best of both worlds by using an arena allocator. A big chunk of memory is allocated at program startup that acts as a stack. In the main loop for each frame to be rendered, all the strings are pushed onto the stack when they are generated and then rendered to the screen. At the end of each frame the position in the memory stack is restored to its position before the frame, essentially popping all the memory from the stack. If this is your first time encountering an arena allocator and you want to learn more, I can point you to <a href="https://youtu.be/YvoyKQYNy20?t=3513">this video</a> by Per Vognsen (where I learned) and <a href="https://www.rfleury.com/p/untangling-lifetimes-the-arena-allocator">this article</a> by Ryan Fleury.</p><h3>Memory Viewer</h3><p>The final feature that I was able to implement during the jam was a memory viewer. I started by just displaying a small fixed range of the address space. This is very straightforward: we iterate over the address range, use <strong>bus_read(addr)</strong> to read each byte, and render them in hexadecimal format. <strong>bus_read(addr)</strong> just dispatches to whichever device occupies the address space that <strong>addr </strong>falls in. In the case of the cartridge, the mapper can perform any mapping logic that it needs to, but from an outside perspective we don’t have to think about any of that we just get a byte returned. Each display line starts with a memory address followed by sixteen bytes that represent the data in memory starting at that address. I also display the ASCII representation of bytes that land within the ASCII range. This is not particularly useful for a NES emulator, but it is interesting and taught me that some games store their name (like CONTRA and ZELDA) in a few bytes at around 0xFFEA.</p><p>The next step was to allow the full 64 KB memory space to be explored. This required two things: the ability to scroll around the memory space and “clipping” the address space that is read, formatted, and rendered to only what will be visible in the memory window. To start, I introduced a <strong>scroll_y</strong> variable that is incremented or decremented depending on the direction that the user scrolls the mouse wheel. The starting address of the memory range visible in the viewer is then calculated based on the <strong>scroll_y</strong> value. The ending address is calculated based on the start address and the number of display lines visible on screen, which in turn depends on both the font height and the window height. Some care must be taken to ensure that the start and end addresses are 16 byte aligned and also to prevent scrolling below 0 or above 0xFFFF. That can be difficult to mentally put together from a description in prose, so here is the code from my emulator that renders the memory contents:</p><pre>void render_memory(void) {<br>    char buffer[MAX_LINE_LEN];<br>    int num_visible_lines = (memory_window.height / TEXT_LINE_HEIGHT) - 1;<br>    int line_num          = 0;<br>    uint16_t start        = 16 * (uint16_t)(memory_window.scroll_y / TEXT_LINE_HEIGHT);<br>    start                 = MIN(start, 0xFFF0 - 16*num_visible_lines);<br>    uint16_t end          = start + 16*num_visible_lines;<br><br>    for (uint16_t addr = start; addr &gt;= start &amp;&amp; addr &lt;= end; addr += 16) {<br>        uint8_t bytes[16];<br>        char ascii[17];<br>        for (int i=0; i&lt;16; ++i) {<br>            bytes[i] = bus_read(addr+i);<br>            ascii[i] = isprint(bytes[i]) ? bytes[i] : &#39;.&#39;;<br>        }<br>        ascii[16] = 0;<br><br>        snprintf(buffer, MAX_LINE_LEN, <br>            &quot;%04X: %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X %02X |%s|&quot;,<br>            addr, bytes[0], bytes[1], bytes[2], bytes[3],<br>            bytes[4], bytes[5], bytes[6], bytes[7],<br>            bytes[8], bytes[9], bytes[10], bytes[11],<br>            bytes[12], bytes[13], bytes[14], bytes[15],<br>            ascii);<br>            <br>        int pad = 15;<br>        render_text(<br>            &amp;memory_window,                                // window<br>            buffer,                                        // text<br>            pad,                                           // x position<br>            line_num*TEXT_LINE_HEIGHT + TEXT_LINE_HEIGHT); // y position<br>        ++line_num;<br>    }<br>}</pre><p>And here is what scrolling the memory viewer with the mouse wheel looks like in action:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/812/1*m01pQ0wEwsxQSypDkxJ7jA.gif" /><figcaption>memory viewer scrolling with mouse wheel</figcaption></figure><h4>Goto Address Command Window</h4><p>With a 64 KB address space, it could take a painfully long time to manually scroll to a specific address. So I added a little popup command window that allows the user to type in an address and jump directly to it in the memory viewer.</p><p>The algorithm is essentially:</p><ul><li>If the user presses the g key, open the goto address command window</li><li>If the command window is open, record user input into a buffer only allowing valid hex digits</li><li>If the user presses enter, calculate the scroll offset needed to jump to the desired address and set <strong>scroll_y</strong></li></ul><p>The scroll offset calculation is pretty simple: we align the user supplied address down to 16 bytes to get the address at the start of the line, divide by 16 to get the line number, and multiply by the height of a text line to get the scroll offset. Now we can easily jump around to any location in the address space!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/810/1*1Gwg7biOTA_K9-OQC8I_bw.gif" /><figcaption>memory viewer goto address command window</figcaption></figure><h3>Demonstration</h3><p>With these three new features, we have gained a much better view into the system and can visualize what is going on in the NES. The pattern table viewer shows us how some games swap palettes to achieve blinking lights or swap tiles to achieve more interesting character animations. The disassembler lets us see exactly what instructions the CPU is executing and view the state of all the CPU registers. The memory viewer lets us explore the entire memory space, and combined with the debug window allows us to see how the CPU interacts with all the devices connected to the bus. Here is video demonstrating the use of all of the features implemented during the jam.</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2Fvq9G2pxeRp8&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3Dvq9G2pxeRp8&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/14d53d56cee4ff05ef2523012dbda4aa/href">https://medium.com/media/14d53d56cee4ff05ef2523012dbda4aa/href</a></iframe><h3>Closing Thoughts</h3><p>I had a really fun weekend hacking on my emulator, and I think I was able to achieve some interesting results. Jams are really effective at showing you how much you can get done when you consciously set aside a chunk of time to intensely focus and work hard. It was also cool to see people posting updates, screenshots, and clips of their projects in the Handmade Network discord. Here are just a few of my favorite projects submitted that you should also check out: <a href="https://handmade.network/p/369/rede/">REDE</a>, <a href="https://handmade.network/p/377/y-no-server/">y no server</a>, and <a href="https://handmade.network/p/386/png-chunk-explorer/">PNG Chunk Explorer</a>. See all the Visibility Jam projects <a href="https://handmade.network/jam/visibility-2023/">here</a>.</p><p>Thanks for reading!</p><h4>Shout Outs</h4><p>The visual layout for the debug window I copied from <a href="https://www.youtube.com/javidx9">javidx9</a>’s emulator. Check out his youtube channel, he is great.</p><p>Reading through the source code of <a href="https://bisqwit.iki.fi/jutut/kuvat/programming_examples/nesemu1/">bisqwit’s emulator</a> gave me some ideas for my own.</p><p>I am a huge fan of <a href="https://github.com/nothings/stb">Sean Barrett’s single-header libraries</a>, and he has one for true type font rasterizing, <a href="https://github.com/nothings/stb/blob/master/stb_truetype.h">stb_truetype</a>. I had never used it before the jam but it got me up and running with text rendering in no time. Thanks Sean.</p><p>I highly recommend <a href="https://www.copetti.org/writings/consoles/nes">Rodrigo Copetti’s article</a> as an overview of the NES architecture.</p><p>The <a href="https://www.nesdev.org/wiki/Nesdev_Wiki">NESdev Wiki</a> is absolutely indispensable for learning about the NES and how to emulate it. I am so grateful to the amazing community that put in an enormous amount of work to reverse engineer and document the system. In particular, a huge thank you to Blargg and Disch (RIP). I found your resources and forum posts monumentally helpful and I would not have been able to write my emulator without them.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4727e76de57" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/nes-emulator-writing-a-disassembler-and-memory-viewer-4727e76de57">NES Emulator - Writing a Disassembler and Memory Viewer</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A simple circular slider]]></title>
            <link>https://medium.com/hard-mode/a-simple-circular-slider-78bb75ed442?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/78bb75ed442</guid>
            <category><![CDATA[code]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[slider]]></category>
            <category><![CDATA[circle]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Mon, 30 Mar 2020 17:16:27 GMT</pubDate>
            <atom:updated>2020-04-29T16:14:12.466Z</atom:updated>
            <content:encoded><![CDATA[<p>I do web programming for my day job. Recently I needed to create a circular<br>slider, and I find the result rather satisfying.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/420/1*Lqt_HcT2DpdbevCYnwS0uA.gif" /></figure><p>The essential idea is that there are a a few layers: a circle with a thin border and the control button, a circle with a thick border that represents the “fill”, and a layer of rectangular overlays that mask the thick border. The circle with the thick border is the bottom layer (furthest from the viewer’s eye), then the overlay layer, and finally the thin circle layer.</p><h3>Building the slider</h3><p>The first step was to create a circle with a button that can be clicked and dragged along the circumference of the circle. To draw the circle, I used a div with a border-radius set to 50%. The control button is the same, but smaller and with a background color. The concept for the control button is to make it follow the mouse, but restrict its movement to the circumference of the circle. This can be done with basic trigonometry.</p><p>The idea is to get the angle between the mouse and the horizontal axis that passes through the circle’s center. To do this, I first obtain the mouse<br>position and the circle center in window coordinates. Then I calculate the mouse position relative to the center of the circle, in order to construct a right triangle with the hypotenuse connecting the circle center and the mouse position. From this triangle, the tangent of the desired angle (theta) can be obtained from the mouse’s relative position:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*i11lgAXjP3C8Mci__HVSxA.jpeg" /></figure><pre>tan(theta) = mouseRelY / mouseRelX<br>theta = arctan(mouseRelY / mouseRelX)</pre><p>Now if you remember from your high school math class, when referring to the unit circle centered at the origin the tangent is positive in quadrants 1 and 3, but negative in quadrants 2 and 4. The effect is that our calculated angle will be skewed in all quadrants but 1. What we want is an angle that increases from 0 to 2π. So to account for the tangent skew, we can add π to our calculated angle if the angle occurs in quadrant 2 or 3, and add 2π if the angle occurs in quadrant 4. The sign (not sin) of the mouse relative x and y positions can be used to determine the quadrant that the angle occurs in.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Hs4YWK1GdG-PaBeAlEka6w.jpeg" /><figcaption>Tangent sign in unit circle quadrants</figcaption></figure><pre>// quadrant 2<br>if (mouseRelX &lt; 0 &amp;&amp; mouseRelY &gt; 0) {<br>    theta += Math.PI</pre><pre>// quadrant 3<br>} else if (mouseRelX &lt; 0 &amp;&amp; mouseRelY &lt;= 0) {<br>    theta += Math.PI</pre><pre>// quadrant 4<br>} else if (mouseRelX &gt; 0 &amp;&amp; mouseRelY &lt;= 0) {<br>    theta += 2 * Math.PI<br>}</pre><p>Now that we have obtained the angle along the circle where the control should be, we need to place it along the circumference of the circle. Since we know the radius of the circle and the angle along the circle, the position can be calculated as follows:</p><pre>controlX = R * cos(theta)<br>controlY = R * sin(theta)</pre><p>To position the control, I set its css-attribute ‘position’ to absolute and the<br>circle’s position to ‘relative’. I also define a translation transform (-50%, -50%) on the control to position it relative to its center rather than the top-leftmost pixel. Then I continuously update its ‘top’ and ‘left’ attributes as follows:</p><pre>left = circleRadius + controlX<br>top = circleRadius — controlY</pre><p>The way I update is dead simple, there are event listeners for mousedown,<br>mouseup, and mousemove events that each call respective event handlers. The mousedown handler sets a controlHeld variable to true, the mouseup handler sets controlHeld to false, and the mousemove handler does all calculations and updates the control’s position if the control is currently being held.</p><p>The next step is to interpret the slider’s position as something useful. Here I will interpret it as a percentage value (0–100). For my use case, the designer wanted 0 to be at the top center of the circle and values to increase as the slider is pulled clockwise around the circle.</p><p>We can obtain such a percentage value by transforming the previously calculated angle. Recall that in the canonical representation of the unit circle, angles start at 0, with the point on the circle being at the center right, and angles increase counter-clockwise. Angles have values between 0 and 2π. So the transformation is calculated as:</p><pre>newPercent = 100 — ((100 * theta) / (2 * PI)) + 25</pre><p>We map the angle that goes from 0–2π to a value from 0–100, subtract it<br>from 100 to flip the direction, and add 25 to shift the starting point to the<br>top of the circle.</p><p>We have one problem left. Since we added 25, the values now range from 25–125. So to correct the values that occur in the first quadrant, we just subtract 100.</p><pre>if (newPercent &gt; 100) newPercent -= 100</pre><h3>Fill Visualization</h3><p>We now have a circular slider that can be interpreted as a value between 0 and 100. The last step is to add some visualization of the “fill” percentage. By this I mean drawing the fill as an arc from 0 (the top center of the circle) to the control’s current position. The approach I took was to create a circle with a thick border that sits directly beneath the thin circle, and to mask the thick circle with rectangular overlays that rotate to reveal portions of the thick border as the control is dragged.</p><p>Practical considerations require two separate rectangles. A single rectangle can only reveal one half of the circle. Each rectangle is placed inside of a wrapper div with overflow set to hidden. The rectangles are rotated about the circle center such that when one rectangle is rotated and spills over into the opposite half of the circle, it is cut off by the wrapper element since its overflow is hidden. The gif below will be much easier to understand than a text description.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*qxS7rbNW3uYim-SNrUPtOA.gif" /></figure><p>The rotation of each rectangle is calculated as follows:</p><pre>overlayRotation1 = 2 * PI * newPercent / 100<br>overlayRotation2 = overlayRotation1 + PI</pre><p>The rotations are restricted to their respective semicircles:</p><pre>if (newPercent &gt; 50) {<br> overlayRotation1 = PI<br>} else {<br> overlayRotation2 = 0<br>}</pre><p>Within the mousemove handler, I apply each rotation to its respective rectangle. In the previous gif, the rectangles are green and orange so they are easier to understand. In practice these rectangles would have a white background (or whatever the page background is) to effectively be invisible.</p><p>If you need the background to be something other than a solid color it is possible to tweak the code to achieve this, but I will leave that as an exercise for the reader. Here is an <a href="http://reflect.jbl.com/">example</a> of the circular slider with a changing gradient background that was used in production for a pair of solar headphones.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*Yt3c6R8LxE5tM_VUiuOSng.gif" /></figure><p>Thanks for reading. Go outside now.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=78bb75ed442" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/a-simple-circular-slider-78bb75ed442">A simple circular slider</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Exapunking]]></title>
            <link>https://medium.com/hard-mode/exapunking-ff8cc3b2c082?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/ff8cc3b2c082</guid>
            <category><![CDATA[assembly-language]]></category>
            <category><![CDATA[exapunks]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[zachtronic]]></category>
            <category><![CDATA[games]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Tue, 25 Sep 2018 22:38:18 GMT</pubDate>
            <atom:updated>2022-01-11T21:46:46.744Z</atom:updated>
            <content:encoded><![CDATA[<h4>Making a game for the TEC Redshift</h4><p>EXAPUNKS is the latest programming game from <a href="http://www.zachtronics.com/">Zachtronics</a>. Read zines, write viruses, hack everything. Life doesn’t get any better. If you haven’t played it yet then stop reading this right now, go <a href="http://www.zachtronics.com/exapunks/">buy</a> it, and come back in a couple days when you have the hang of things.</p><p>For those of you who have no interest in playing the game (wtf is wrong with you?!) but still want to grok the rest of this article, here is a bit of context. In EXAPUNKS you program EXAs. EXA stands for EXecution Agent — a small program that can move in and out of networks and execute code. Every EXA has registers and code, can hold a single file, and can communicate with other EXAs inside a network over a global register. You program EXAs in an assembly style language with a very limited set of instructions. EXAs can be uploaded into pretty much any network, regardless of what the underlying hardware is making them extremely versatile. In this article, I will describe how to program EXAs to make a video game for the in-game console called the TEC Redshift.</p><p>If you read on, there are some mild <strong>spoilers</strong>.</p><p>Right, now let’s get to hacking. So Ghast has given us a handheld gaming console called the Redshift (much like a Gameboy in this universe) and the second issue of his underground computer magazine Trash World News. It’s up to us to figure out how to program a game for it. I wanted to make something simple for my first Redshift game, so I decided to make a Space Invaders / Galaga style arcade shooter. My game uses three EXAs: one controls the player, one controls the enemies or invaders, and one controls the player’s bullets.</p><h3>EXA 1 — The Player</h3><p>The player has a sprite, can move in four directions, and can fire bullets. In order to draw the sprite, we first create a file that contains the data describing which pixels should be toggled on and off. We use the DATA instruction followed by a series of space separated integers to create the file. Each integer is a three digit number: the hundreds place represents whether the pixel is on or off, the tens place represents the x position of the pixel, and the ones place represents the y position of the pixel. A sprite is 10x10 pixels.</p><pre>DATA 000 010 020 130 140<br>DATA 150 160 070 080 090</pre><pre>DATA 001 011 121 131 141<br>DATA 151 161 171 081 091</pre><pre>DATA 002 012 122 132 142<br>DATA 152 162 172 082 092</pre><pre>DATA 003 013 023 033 143<br>DATA 153 063 073 083 093</pre><pre>DATA 004 014 024 034 144<br>DATA 154 064 074 084 094</pre><pre>DATA 005 015 025 135 145<br>DATA 155 165 075 085 095</pre><pre>DATA 006 116 126 136 146<br>DATA 156 166 176 186 096</pre><pre>DATA 107 117 027 037 147<br>DATA 157 067 077 187 197</pre><pre>DATA 108 018 028 138 048<br>DATA 058 168 078 088 198</pre><pre>DATA 109 019 029 139 049<br>DATA 059 169 079 089 199</pre><p>Next, we initialize the collision output register of the EXA so that other EXA’s can identify this one on a collision. We also position the sprite at the bottom center of the Redshift screen and seek to the beginning of the EXA’s held file.</p><pre>MARK INIT<br>COPY 1 CO<br>COPY 55 GX<br>COPY 90 GY<br>SEEK -9999</pre><p>Then, we read each consecutive value from the file into the GP register of the EXA to draw the sprite. After each copy, we test to see if we have reached the end of the file and if not, jump back to the SPRITE label.</p><pre>MARK SPRITE <br>COPY F GP <br>TEST EOF<br>FJMP SPRITE</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/536/1*8J9t1ufQH6NnWZoTfpsvAQ.gif" /><figcaption>reading the file into the GP register</figcaption></figure><h4>Main Loop</h4><p>Once the sprite is drawn, we are ready to start the main loop. We first check for user input by reading from the Redshift’s hardware registers. If input is detected, we jump to the corresponding label to handle either movement or shooting. We also check for collision with an enemy. I will describe how we handle a collision later. For movement, we simply increment or decrement the sprite’s position by writing to the GX or GY register. Vertical movement is pretty useless for this particular game, but I still included it. To shoot a bullet we copy the sprite’s x and y positions to the global M register. Another EXA is <em>listening </em>for values on this register and will handle firing the bullet. I will describe this in detail in one of the following sections. We copy the sprite’s position so that the EXA that handles the bullet knows where to fire the bullet from. After handling all possible user input, collisions, and updating position, we use the WAIT instruction to pause execution until the next frame synchronization (30 times per second) and finally jump to the INPUT label continuing the game loop.</p><pre>MARK INPUT<br>LINK 800<br>NOTE SHOOTING<br>SWIZ #PADB 1 X<br>TEST X = 1<br>TJMP SHOOT<br>NOTE COLLISION<br>TEST CI = 2<br>TJMP GAMEOVER<br>NOTE HORIZONTAL<br>TEST #PADX = -1<br>TJMP MOVL<br>TEST #PADX = 1<br>TJMP MOVR<br>NOTE VERTICAL<br>TEST #PADY = -1<br>TJMP MOVU<br>TEST #PADY = 1<br>TJMP MOVD<br>JUMP SYNC</pre><pre>MARK MOVL<br>SUBI GX 1 GX<br>JUMP SYNC</pre><pre>MARK MOVR<br>ADDI GX 1 GX<br>JUMP SYNC</pre><pre>MARK MOVU<br>SUBI GY 1 GY<br>JUMP SYNC</pre><pre>MARK MOVD<br>ADDI GY 1 GY<br>JUMP SYNC</pre><pre>MARK SHOOT<br>COPY GX M<br>COPY GY M<br>JUMP SYNC</pre><pre>MARK SYNC<br>LINK -1<br>WAIT<br>JUMP INPUT</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/342/1*1sWsVXxuO9J1XFyH0577JQ.gif" /><figcaption>player movement</figcaption></figure><h4>Collision</h4><p>In the case of a collision with an invader, we jump to the GAMEOVER label. This code moves the player sprite off screen and writes the text ‘GAME OVER’. In order to do this we replicate the EXA 8 times, one for each letter in ‘GAME OVER’. The REPL instruction creates a copy of the EXA and jumps to the specified label in the replicant EXA. Each EXA renders its letter and then loops, doing nothing until the user presses the X button to restart the game. The original EXA jumps to the RESET label, listening for the user to press the X button to restart the game. When the user presses X, the EXA writes a value to the global M register to notify the invader EXA that the game has restarted.</p><pre>MARK GAMEOVER<br>COPY 35 GY<br>REPL G<br>REPL A<br>REPL M<br>REPL E1<br>REPL O<br>REPL V<br>REPL E2 <br>REPL R<br>COPY -99 GY<br>JUMP RESET</pre><pre>MARK G<br>COPY 10 GX<br>COPY 307 GP<br>JUMP END</pre><pre>MARK A<br>COPY 20 GX<br>COPY 301 GP<br>JUMP END</pre><pre>MARK M<br>COPY 30 GX<br>COPY 313 GP<br>JUMP END</pre><pre>MARK E1<br>COPY 40 GX<br>COPY 305 GP<br>JUMP END</pre><pre>MARK O<br>COPY 60 GX<br>COPY 327 GP<br>JUMP END</pre><pre>MARK V<br>COPY 70 GX<br>COPY 322 GP <br>JUMP END</pre><pre>MARK E2<br>COPY 80 GX<br>COPY 305 GP<br>JUMP END</pre><pre>MARK R<br>COPY 90 GX<br>COPY 318 GP</pre><pre>MARK END<br>TEST #PADB = 0<br>TJMP END<br>HALT</pre><pre>MARK RESET<br>TEST #PADB = 0<br>FJMP NEWGAME<br>JUMP RESET</pre><pre>MARK NEWGAME<br>COPY 1 M<br>LINK -1<br>JUMP INIT</pre><p>Thats it for the player EXA. Here is the complete code before we move on to the code for the invaders.</p><pre>DATA 000 010 020 130 140<br>DATA 150 160 070 080 090</pre><pre>DATA 001 011 121 131 141<br>DATA 151 161 171 081 091</pre><pre>DATA 002 012 122 132 142<br>DATA 152 162 172 082 092</pre><pre>DATA 003 013 023 033 143<br>DATA 153 063 073 083 093</pre><pre>DATA 004 014 024 034 144<br>DATA 154 064 074 084 094</pre><pre>DATA 005 015 025 135 145<br>DATA 155 165 075 085 095</pre><pre>DATA 006 116 126 136 146<br>DATA 156 166 176 186 096</pre><pre>DATA 107 117 027 037 147<br>DATA 157 067 077 187 197</pre><pre>DATA 108 018 028 138 048<br>DATA 058 168 078 088 198</pre><pre>DATA 109 019 029 139 049<br>DATA 059 169 079 089 199</pre><pre>MARK INIT<br>COPY 1 CO<br>COPY 55 GX<br>COPY 90 GY<br>SEEK -9999</pre><pre>MARK SPRITE <br>COPY F GP <br>TEST EOF<br>FJMP SPRITE</pre><pre>MARK INPUT<br>LINK 800<br>NOTE SHOOT<br>SWIZ #PADB 1 X<br>TEST X = 1<br>TJMP SHOOT<br>NOTE COLLISION<br>TEST CI = 2<br>TJMP GAMEOVER<br>NOTE HORIZONTAL<br>TEST #PADX = -1<br>TJMP MOVL<br>TEST #PADX = 1<br>TJMP MOVR<br>NOTE VERTICAL<br>TEST #PADY = -1<br>TJMP MOVU<br>TEST #PADY = 1<br>TJMP MOVD<br>JUMP SYNC</pre><pre>MARK MOVL<br>SUBI GX 1 GX<br>JUMP SYNC</pre><pre>MARK MOVR<br>ADDI GX 1 GX<br>JUMP SYNC</pre><pre>MARK MOVU<br>SUBI GY 1 GY<br>JUMP SYNC</pre><pre>MARK MOVD<br>ADDI GY 1 GY<br>JUMP SYNC</pre><pre>MARK SHOOT<br>COPY GX M<br>COPY GY M<br>JUMP SYNC</pre><pre>MARK SYNC<br>LINK -1<br>WAIT<br>JUMP INPUT</pre><pre>MARK GAMEOVER<br>COPY 35 GY<br>REPL G<br>REPL A<br>REPL M<br>REPL E1<br>REPL O<br>REPL V<br>REPL E2 <br>REPL R<br>COPY -99 GY<br>JUMP RESET</pre><pre>MARK G<br>COPY 10 GX<br>COPY 307 GP<br>JUMP END</pre><pre>MARK A<br>COPY 20 GX<br>COPY 301 GP<br>JUMP END<br>MARK M<br>COPY 30 GX<br>COPY 313 GP<br>JUMP END<br>MARK E1<br>COPY 40 GX<br>COPY 305 GP<br>JUMP END<br>MARK O<br>COPY 60 GX<br>COPY 327 GP<br>JUMP END<br>MARK V<br>COPY 70 GX<br>COPY 322 GP <br>JUMP END<br>MARK E2<br>COPY 80 GX<br>COPY 305 GP<br>JUMP END<br>MARK R<br>COPY 90 GX<br>COPY 318 GP<br>MARK END<br>TEST #PADB = 0<br>TJMP END<br>HALT</pre><pre>MARK RESET<br>TEST #PADB = 0<br>FJMP NEWGAME<br>JUMP RESET</pre><pre>MARK NEWGAME<br>COPY 1 M<br>LINK -1<br>JUMP INIT</pre><h3>EXA 2 — The Invaders</h3><p>The invaders have a UFO-like sprite and endlessly spawn at the top of the screen, diving down towards the player. Just like the player EXA, the enemy EXA first creates a file that defines the sprite, initializes the collision output register, and loops through the file writing values to the GP register to draw the sprite.</p><pre>DATA 000 010 020 130 140<br>DATA 150 160 070 080 090</pre><pre>DATA 001 011 121 131 141<br>DATA 151 161 171 081 091</pre><pre>DATA 002 012 122 132 142<br>DATA 152 162 172 082 092</pre><pre>DATA 003 013 023 133 143<br>DATA 153 163 073 083 093</pre><pre>NOTE INIT<br>COPY 2 CO<br>LINK 800</pre><pre>MARK SPRITE <br>COPY F GP <br>TEST EOF<br>FJMP SPRITE</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/516/1*eRf6FcfT1j_S2f5sQyo1dA.gif" /></figure><h4>Main Loop</h4><p>Once the sprite is drawn, we begin the invasion. There are actually two loops that control the invader behavior. The outer loop spawns a new invader, and the inner loop moves the invader and tests for collisions. For the outer loop, we use the RAND instruction to generate a random value between 0 and 110 (the Redshift’s screen is 120x100 pixels) and write this value to the GX register to spawn an invader at a random x position at the top of the screen. For the inner loop, we move the invader down the screen by incrementing the GY register. Then, we test for collisions with the player or with a bullet. If there is a player collision, we jump to the KILLPLAYER label to handle this case. If there is a bullet collision, we simply jump to the INVADE label to spawn a new invader. Finally, we test if the invader is offscreen. If it is, we jump to the INVADE label to spawn a new invader, otherwise we jump to the MOVE label to continue the inner loop.</p><pre>MARK INVADE<br>RAND 0 110 GX<br>COPY 0 GY<br>MARK MOVE<br>ADDI GY 1 GY<br>NOTE TEST COLLISION<br>TEST CI = 1<br>TJMP KILLPLAYER<br>TEST CI = 3<br>TJMP INVADE<br>NOTE TEST OFFSCREEN<br>TEST GY &gt; 99<br>TJMP INVADE<br>WAIT<br>JUMP MOVE</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/346/1*G1xFtJmJeHHmKEOvObQBpw.gif" /><figcaption>invaders spawning</figcaption></figure><h4>Player Collision</h4><p>In the case of a player collision, we hide the invader sprite by writing an offscreen value to the GX register, then listen on the global M register for a message from the player EXA to signal that the game has been restarted. We use the statement TEST MRD to test if the EXA can read from the global M register without pausing / blocking. If there is a value in the M register, we discard the value so that the sender can continue executing its code and jump to the INVADE instruction to restart the main loop.</p><pre>MARK KILLPLAYER<br>NOOP<br>NOOP<br>NOOP<br>NOOP<br>NOOP<br>COPY -77 GX<br>TEST MRD<br>TJMP RESET<br>JUMP KILLPLAYER</pre><pre>MARK RESET<br>VOID M <br>JUMP INVADE</pre><p>*NOTE — the NOOP instructions are there to deal with a race condition. When there is a collision with the player and an invader, the invader receives the message first. The NOOP instructions pause the invader so that the player has time to catch up and receive the collision message before the invader is positioned offscreen. This is maybe a bit hacky but were EXAPUNKING here, hacking by definition.</p><h3>EXA 3 — The Bullets</h3><p>The EXA that controls bullets follows the same initialization pattern as the other two EXAs. It draws a 2x2 square sprite and defines the collision output value as 3.</p><pre>DATA 140 150 141 151</pre><pre>COPY 3 CO<br>MARK SPRITE <br>COPY F GP <br>TEST EOF<br>FJMP SPRITE</pre><p>Like the invader EXA, the bullet EXA also has two loops: the outer loop waits for a message from the Player to shoot a bullet and the inner loop moves the bullet and tests for a collision with an invader. We also test if the player tries to shoot more than one bullet at a time, in which case we simply ignore the message to fire a bullet by discarding the value from the M register and jumping back to the MOVE label.</p><pre>MARK WAIT4SHOOT<br>COPY -99 GX<br>COPY -99 GY<br>COPY M GX<br>COPY M GY<br>MARK MOVE<br>NOTE IGNORE MORE THAN 1<br>TEST MRD<br>TJMP IGNORE<br>SUBI GY 1 GY<br>NOTE TEST COLLISION<br>TEST CI = 2<br>TJMP WAIT4SHOOT<br>NOTE TEST OFFSCREEN<br>TEST GY &lt; 1 <br>TJMP WAIT4SHOOT<br>WAIT <br>JUMP MOVE</pre><pre>MARK IGNORE<br>VOID M<br>JUMP MOVE</pre><h3>GG</h3><p>And that, my friends, is how you properly EXAPUNK.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/342/1*p4AaIjj10aWT0DV2QORpGg.gif" /><figcaption>EXAPUNKING</figcaption></figure><p>Thanks for reading! I hope you found it interesting or helpful. If you’re playing EXAPUNKS find me on steam (bitwitch) and we can go head to head in a hacker battle!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ff8cc3b2c082" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/exapunking-ff8cc3b2c082">Exapunking</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A fast iterative process for multiplication in Scheme]]></title>
            <link>https://medium.com/hard-mode/a-fast-iterative-process-for-multiplication-in-scheme-668e1726ab17?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/668e1726ab17</guid>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[mathematics]]></category>
            <category><![CDATA[scheme]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[coding]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Mon, 05 Feb 2018 02:33:17 GMT</pubDate>
            <atom:updated>2018-02-05T05:25:54.542Z</atom:updated>
            <content:encoded><![CDATA[<p>I have been studying the book <a href="https://www.amazon.com/Structure-Interpretation-Computer-Programs-Engineering/dp/0262510871"><em>Structure and Interpretation of Computer Programs</em></a><em> </em>in my free time. The book uses the Scheme programming language to explain and explore concepts in programming and computer science. It is a great book with a lot of depth and I highly recommend it to anyone interested in either of these areas of study.</p><p>One of the exercises in the book is to design a procedure that can multiply two numbers (without using multiplication or division) <strong>in O(log n) time </strong>and using <strong>O(1) space</strong>. The solution is really cool! The way in which the procedure manipulates numbers is both clever and elegant. Let’s take a look at how it works.</p><h3>The Problem Statement</h3><p>It is assumed that our language can only add and subtract, not multiply and divide. In such a language, integer multiplication can be performed by means of repeated addition. The following procedure demonstrates this and has a time complexity that is linear in b (O(n) time complexity).</p><pre>(define (* a b)<br>  (if (= b 0)<br>      0<br>      (+ a (* a (- b 1)))))</pre><p>Given this example, the exercise in the book is then presented to the reader as follows:</p><blockquote>Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.</blockquote><p>By analogous to fast-expt , a previous exercise in the book, the authors simply mean that the procedure must evolve an iterative process that takes O(1) space and must also take a logarithmic number of steps.</p><p>Here is the solution that I wrote:</p><pre>(define (* a b)<br>  (if (or (= a 0) (= b 0)) <br>    0<br>    (fast-mult-iter a b 0)))</pre><pre>(define (fast-mult-iter a b sum)<br>  (cond <br>    ((= b 0) sum)<br>    ((even? b) <br>      (fast-mult-iter (double a) (halve b) sum))<br>  (else <br>    (fast-mult-iter a (- b 1) (+ a sum)))))</pre><pre>#|<br>It is assumed that double and halve are implemented <br>by the language. The following procedures are<br>meant to simulate such implementations. <br>|#</pre><pre>(define (double n)<br>  (+ n n))</pre><pre>(define (halve n)<br>  (/ n 2))</pre><h4>TL;DR</h4><p>The procedure alternates between two patterns: halving b and doubling a until b is odd; then subtracting 1 from b and incrementing sum by a.</p><h3>How It Works</h3><p>Basically, the procedure works by halving b and doubling a until b is an odd number. This is possible because of the associative and commutative properties of multiplication. Then, it pulls out one a and adds it to a state variable sum by subtracting 1 from b . Now b will be even again and the procedure can continue this pattern: halving b and doubling a until b is odd, then subtracting 1 from b and incrementing sum by a. This pattern continues until b is zero, at which point the procedure returns the sum.</p><p>Let’s look at this more closely with an example. Suppose we apply the * procedure to 10 and 12. That is to say a is 10 and b is 12. The following diagram illustrates this example. Starting from the top row and reading the diagram row by row demonstrates how the variables a, b, and sum change throughout the lifecycle of the procedure call.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/535/1*YHx3Tmv13hzPaO-uqzFjPQ.jpeg" /></figure><p>We will halve b and double a until b is no longer even. So a becomes 20 and b becomes 6. Then a becomes 40 and b becomes 3. The multiplication has been transformed to 40 x 3 which can be represented as 40 + 40 + 40. If we pull out one 40 and move it to sum , we are left with 40 + 40 or 40 * 2, and b is once again even. Now we continue the pattern of halving and doubling such that a becomes 80 and b becomes 1. Since b is now odd we can pull out one 80 and move it to sum so that we are left with a of 80, b of 0, and sum of 80 + 40 = 120. Now in the last iteration of the procedure since b is zero, the sum of 120 is returned.</p><p>This is a relatively simple procedure, but I really like the way that it manipulates the numbers with two interwoven patterns. The challenge of designing the algorithm was the restriction of having a time complexity of O(log n) and a space complexity of O(1). I thought it was a cool example and I wanted to share it with you all. I hope that you find it interesting as well. Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=668e1726ab17" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/a-fast-iterative-process-for-multiplication-in-scheme-668e1726ab17">A fast iterative process for multiplication in Scheme</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Shaker Maker: Part II]]></title>
            <link>https://medium.com/hard-mode/shaker-maker-part-ii-2d3dc7282305?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/2d3dc7282305</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[redux]]></category>
            <category><![CDATA[react]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Sun, 21 Jan 2018 20:41:32 GMT</pubDate>
            <atom:updated>2018-01-21T20:41:48.687Z</atom:updated>
            <content:encoded><![CDATA[<h4>Animated Playback</h4><p>Welcome to Part II of the Shaker Maker series. Shaker Maker is a web app that I built that allows users to create choreography, play music, sync their choreography to the exact tempo of any song and playback their choreography with it. In <a href="https://medium.com/hard-mode/shaker-maker-part-i-462ceb4bb577">Part I</a>, I showed you how I built a posable figure so that users can click-and-drag the figure into poses and create a choreography. In Part II, I want to show you how I implemented an animated playback feature so that users can watch the choreography that they created.</p><p>You can see a full demo video of Shaker Maker <a href="https://youtu.be/2r7YqN45YeA">here</a>, and if you’re a Tinashe fan there is an extra choreography demo for you <a href="https://youtu.be/9yJ3-h11lEk">here</a>.</p><h3>The Concept</h3><p>Users create choreography by dragging the joints of a posable figure into a series of poses. The posable figure is shown below and the button to add a pose is located on the speaker to the left of the figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/658/1*FhzjsqeNc6e1rhx2-y7Yjg.png" /><figcaption>posable figure, <strong>Add Pose</strong> button shown in green</figcaption></figure><p>When a user clicks the <em>Add Pose</em> button, the figure’s current pose is added to the choreography as a new frame. The choreography is represented as a list of poses that are displayed below the posable figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/650/1*ooUSfR-AtlJZ-vylFXCQgA.png" /><figcaption>a choreography is represented as a list of poses</figcaption></figure><p>The playback feature is displayed as a TV screen with a play/pause button, a stop button, and a slider to adjust playback speed. When a user clicks the play button, the playback feature cycles through each pose in the current choreography<em>. </em>A user can adjust the slider bar to change the playback speed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*BImEsspAzX08rEjTcu-ogw.gif" /></figure><p>Conceptually, that is how the playback feature works. Technically, I implemented animated playback in JavaScript using React, Redux, and Konva.</p><h3>How It Works</h3><p>First, a user creates a choreography. All of the poses that make up a choreography are stored in state using Redux. Each pose is represented as an array of lines where each line is both a Konva object and React component. Once a user has created a choreography, they can use the playback feature to watch their choreography. The playback feature lives within a React component called PlaybackContainer . This component is connected to the Redux store, but it also has a local state with the following shape.</p><pre>state = {<br>  frames: [],<br>  frameCounter: 0,<br>  playing: false,<br>  playbackSpeed: 75<br>}</pre><p>frames points to the array of poses that the animated playback feature will cycle through, frameCounter points to the current frame being displayed, playing points to a boolean representing whether the choreography is currently playing or not, and playbackSpeed points to the current value of the slider bar controlling how fast the choreography plays.</p><h3>Frames</h3><p>The poses stored in Redux need to be resized before they can be played back. In the componentWillReceiveProps() lifecycle method, these poses are mapped to a new array of resized poses and are stored in local state as frames .</p><pre>componentWillReceiveProps(nextProps) {<br>  const frames = nextProps.poses.list.map(pose =&gt; {<br>    return this.resizePose(pose.lines) <br>  })</pre><pre>  this.setState({<br>    frames<br>  })<br>}</pre><p>The resizePose() function is responsible for resizing each line of a pose, representing the figure’s body parts, as well as an ellipse that represents the figure’s head. For my purposes, the length of each line is doubled and the thickness is increased. For the head, the x and y positions of the center of the ellipse are doubled and the line thickness is increased. The function returns a resized pose which is an array of lines that are simultaneously Konva objects and React components as I am using the react-konva library.</p><pre>resizePose = (lines) =&gt; {<br>  let i = 0<br>  return lines.map(line =&gt; {<br>    if (line.type === &#39;Ellipse&#39;) {<br>      const newCenterX = line.props.x * 2<br>      const newCenterY = line.props.y * 2 <br>      return (<br>        &lt;Ellipse <br>          key={++i} <br>          x={newCenterX} <br>          y={newCenterY} <br>          radius={{x: 10, y: 14}} <br>          stroke=&#39;#000&#39; <br>          strokeWidth={4}<br>        /&gt;<br>      )<br>    } else {<br>      const newPoints = line.props.points.map(point =&gt; point*2)<br>      return (<br>        &lt;Line <br>          key={++i} <br>          points={newPoints} <br>          stroke=&#39;#000&#39; <br>          strokeWidth={4} <br>        /&gt;<br>      )<br>    }<br>  })<br>}</pre><p>Once the poses are resized, they are stored in local state as frames .</p><h3>Animating</h3><p>Animation for Shaker Maker basically consists of: a canvas to display the animation, buttons to control starting and stoping playback, a function to control cycling through the poses, and a slider bar to control the playback speed.</p><p>There are a number of event handlers controlling animated playback: handlePlay() , handlePause() , handleStop() , andhandlePlaybackSpeed() . The play, pause, and stop handlers are attached to the buttons that correspond with their name. The playback speed handler is attached to the slider and updates the playbackSpeed in local state whenever the slider bar is adjusted.</p><p>The most important element of the animated playback feature is the playbackTimer() . This function is responsible for the actual animation by cycling through each of the poses in a choreography. The playbackTimer() is a recursive function that calculates the required timeInterval between frames based on the selected playbackSpeed , updates the frameCounter , and calls itself using setTimeout() with the delay equal to the calculated timeInterval .</p><pre>playbackTimer = () =&gt; {<br>  if (!this.state.playing) return false<br>  const timeInterval = (100 - this.state.playbackSpeed) * 10<br>    <br>  let newFrameCount<br>  if (counter &gt;= this.state.frames.length - 1) {<br>    newFrameCount = 0<br>  } else<br>    newFrameCount = this.state.frameCounter + 1<br>  }</pre><pre>  this.setState({frameCounter: newFrameCount})<br>  this.timeout = setTimeout(this.playbackTimer, timeInterval)<br>}</pre><p>The timeInterval is calculated by subtracting 100 from the current playbackSpeed (the value represented by the slider) and multiplying the result by 10. The choice of 10 as a multiplier was somewhat arbitrary, it just controls the range of possible playback speeds. The time interval is in milliseconds and ranges from one frame per 1000 milliseconds (one per second) up to one frame per 10 milliseconds*. This corresponds to a tempo range of 60 BPM (beats per minute) to a wildly impractical 6000 BPM !</p><p><em>* The actual max playback speed is as fast as </em><em>setTimeout can run with a delay of 0, but the maximum calculable playback speed is when the slider is at 99 yielding one frame per 10 milliseconds.</em></p><p>The playbackTimer() is initially called by handlePlay() . When a user clicks the play button, handlePlay() is invoked setting playing to true and then calling the playbackTimer().</p><pre>handlePlay = () =&gt; {<br>  if (this.state.frames.length === 0 || this.state.playing) <br>    return false <br>    <br>  this.setState({<br>    playing: true<br>  }, this.playbackTimer)<br>}</pre><h3>The Result</h3><p>Stick figures WEEERKING it!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*ShLeBz7kOPq7-oUXaKcOkA.gif" /></figure><p>Thanks for reading Part II ! If you enjoyed it, check out Part III (coming soon) on how I made an in app music player and a beat matcher to sync choreography to a user’s music.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2d3dc7282305" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/shaker-maker-part-ii-2d3dc7282305">Shaker Maker: Part II</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Shaker Maker: Part I]]></title>
            <link>https://medium.com/hard-mode/shaker-maker-part-i-462ceb4bb577?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/462ceb4bb577</guid>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[react]]></category>
            <category><![CDATA[redux]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Fri, 29 Dec 2017 00:31:38 GMT</pubDate>
            <atom:updated>2018-01-21T20:43:41.664Z</atom:updated>
            <content:encoded><![CDATA[<h4>Building a posable figure in JavaScript</h4><p>I love to dance. When I’m dancing I have this feeling of joy and freedom that flows through my body. What’s more, when you are dancing with other people you feel connected and share that feeling of joy and freedom. This feeling inspired me to build a tool that allows people to create, explore, and experience dance.</p><p>I built a web application, Shaker Maker, that allows users to create choreography, sync their choreography to any music that they choose, listen to their music, and watch their choreography in action. You can see a full demo video of Shaker Maker <a href="https://youtu.be/2r7YqN45YeA">here</a>. I built Shaker Maker with a Ruby on Rails backend and a JavaScript frontend utilizing React and Redux. I’d like to take you back through the application’s development and describe my thought process, how I approached problems, challenges that I encountered, and my solutions to challenges. Hopefully you learn something along the way. This will be part of a series of posts about the making of Shaker Maker. Part I will focus on building the posable figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*8wSfVZz0sfhBOB5AXUeXJg.png" /></figure><h3>The Idea</h3><p>In its infancy, the idea for Shaker Maker was: a posable figure, a button to save an image of the figure’s current pose, and a list of all the images saved. This series of images would effectively make up a choreography. These three features were my minimum viable product, but I had goals for quite a few other features as well: a playback feature that would allow a user to watch their choreography, an in-app music player, and a way to sync the playback of the choreography to the music so that they perfectly match. However, the first step was to build a posable figure so that users could start to sketch out a choreography.</p><h3>Posable Figure</h3><p>The first feature that I needed to build was the posable figure. I knew that I wanted to use canvas for the figure, and I had used a library called Konva in a previous project (<a href="https://www.youtube.com/watch?v=23q97PkciH0&amp;t=2s">a game called Code Caverns</a>), so I wanted to use this library again. Konva provides a layer of abstraction on top of canvas and it has a nice React wrapper, react-konva, which allows you to make React components out of Konva objects (the documentation for Konva can be found <a href="https://konvajs.github.io/docs/index.html">here</a>).</p><p>The essential idea for the posable figure is a stick figure with draggable joints (elbows, shoulders, hips, knees, etc.). A user is able to pose the figure into a dance move by clicking and dragging its joints. The joints are connected by lines which form all of the body parts except for the head which is an ellipse.</p><p>The figure is made up of two container components: a JointLayer and a LineLayer. The JointLayer component renders all of the joints as circles on the canvas. The position of each joint is stored in the Redux store and is updated every time a joint is moved. Then there is a LineLayer that renders all of the body parts connecting the joints. This layer is re-rendered every time a joint is moved so that the body parts move with the joints.</p><p>Perhaps the hardest part about coding the posable figure was getting the joints to move together. For example, if a user drags the knee joint, the foot needs to move with it, otherwise the leg would deform. Similarly, when a shoulder is dragged, both the elbow and hand need to move with the shoulder to maintain the proportions of the figure. More generally, if a user drags a joint, all of the <em>children</em> of that joint need to move with it. Most of the relationships between parent and child joints are intuitive, the only two that might need defining are the pelvis and neck joints. The pelvis is essentially the root node — every other joint is a child of the pelvis — so moving the pelvis moves the entire figure. The neck is the parent node of the entire upper body and pivots about the pelvis. Moving the neck joint will rotate the upper body about the pelvis.</p><h3>JointLayer</h3><p>Drag movement bubbling down to children and all other aspects of joint movement are controlled by callback functions which are methods of the JointLayer component. These callbacks are passed down to each joint as props. The four main callback functions that control joint movement are: onDragStart(), onDragMove(), onDragEnd(), and dragBound().</p><h4>onDragStart()</h4><p>This function is called once every time a user initializes a click and drag. It calculates the initial distances between the joint that the user clicked on and all of its child joints. These distances are stored in the local state of the JointLayer component. They are used to maintain the distance between each joint and its children as the figure is being posed.</p><pre>onDragStart = (e) =&gt; {<br>  const { name, x, y } = e.target.attrs<br>  const newState = {}</pre><pre>  jointChildren[name].forEach (child =&gt; {<br>    const distX = this.props.joints[child].x - x<br>    const distY = this.props.joints[child].y - y<br>    newState[child] = {x: distX, y: distY} <br>   })</pre><pre>   this.setState({<br>     dragStartDist: newState<br>   })<br>}  </pre><p>jointChildren is an object that maps each parent joint to an array of its child joints.</p><h4>onDragMove()</h4><p>This function is called every time the position of a joint changes during a click and drag. It iterates through the children of the joint that is being dragged and updates their positions such that the distance between each child and the joint being dragged is the same as the distance right before the joint started being dragged (i.e. the distance that was stored in state by the onDragStart function). The position of each joint is updated by dispatching an action to the Redux store by calling moveJoint().</p><pre>onDragMove = (e) =&gt; {<br>  const {name, x, y} = e.target.attrs<br>  const dist = this.state.dragStartDist</pre><pre>  jointChildren[name].forEach(child =&gt; {<br>    this.props.moveJoint(<br>      child, <br>      dist[child].x + this.props.joints[name].x, <br>      dist[child].y + this.props.joints[name].y<br>    )<br>  })</pre><pre>  this.props.moveJoint(name, x, y)<br>}</pre><h4>onDragEnd()</h4><p>onDragEnd() simply clears out the distances that were stored in local state by onDragStart().</p><pre>onDragEnd = () =&gt; {<br>  this.setState({<br>    dragStartDist: {}<br>  })<br>}</pre><h4>dragBound()</h4><p>The dragBound function defines the conditions for which a joint is allowed to be dragged. The main condition is that the distance between a joint and its pivot point must remain constant. For example, the pivot point of the elbow is the shoulder, so when dragging the elbow the distance between the elbow and the shoulder must not change. This effectively means that a joint can only move in a circle around its pivot point. The dragBound function calls findPivot() in order to get the pivot joint of the joint being dragged. Then, it calculates the current scale of the body part — the limb that connects the joint being dragged and its pivot joint — which represents how much it would be stretched or squashed due to the joint movement. Finally, it corrects for the stretch or squash such that the scale is always equal to 1 and the length of the body part remains constant.</p><pre>dragBound = function(pos) {<br>  const pivot = this.attrs.findPivot(this.attrs.name)<br>  const stretch = Math.sqrt(Math.pow(pos.x - pivot.x, 2) + <br>    Math.pow(pos.y - pivot.y, 2))<br>  const scale = pivot.radius / stretch</pre><pre>  if(scale !== 1 &amp;&amp; this.attrs.name !== &#39;pelvis&#39;) {<br>    return {<br>      y: Math.round((pos.y - pivot.y) * scale + pivot.y),<br>      x: Math.round((pos.x - pivot.x) * scale + pivot.x)<br>    }<br>  } else {<br>    return {x: pos.x, y: pos.y}<br>  }<br>}</pre><h3>LineLayer</h3><p>All of the figure’s body parts are rendered in the LineLayer. Basically, a line is constructed that connects each joint to its parent and an ellipse is drawn for the head.There is one method of the LineLayer component that handles rendering, drawLines() .</p><h4>drawLines()</h4><p>This function is called every time the LineLayer renders and a re-render is triggered every time a joint is moved. The function iterates through each body part and constructs a Konva line connecting each joint to its parent. It constructs an ellipse for the head with its center at the midpoint between the joint at the top of the head and the joint at the bottom of the head.</p><pre>const drawLines = () =&gt; {<br>  const joints = props.joints<br>  const lines = []<br>  let i = 0</pre><pre>  for(let part in bodyMap) {<br>    const {start, stop} = bodyMap[part]</pre><pre>    if (part === &#39;head&#39;) {<br>      const centerX = (joints[stop].x + joints[start].x) / 2<br>      const centerY = (joints[stop].y + joints[start].y) / 2<br>      <br>      lines.push(<br>        &lt;Ellipse <br>          key={++i} <br>          x={centerX} <br>          y={centerY} <br>          radius={{x: 10, y: 13}} <br>          stroke=&#39;#000&#39; <br>          strokeWidth={4}<br>        /&gt;<br>      )</pre><pre>    } else {<br>      const points = [<br>        joints[start].x, <br>        joints[start].y, <br>        joints[stop].x, <br>        joints[stop].y<br>      ]<br>      lines.push(<br>        &lt;Line <br>          key={++i} <br>          points={points} <br>          stroke=&#39;#000&#39; <br>          strokeWidth={4} <br>        /&gt;<br>      )<br>    }<br>  }</pre><pre>  props.setCurrentPose(lines)<br>  return lines<br>}</pre><h3>The Result</h3><p>Behold an interactive posable figure!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*GBubkelR3YR3sK3bQN4lsQ.gif" /></figure><p>To recap: the posable figure essentially consists of two container components, a JointLayer and a LineLayer. The JointLayer has methods that control the movement of the joints that it passes down as props to each joint component. The LineLayer has a single method that renders each line component and an ellipse component for the head every time a joint is moved.</p><p>That’s it for Part I. I hope you find it interesting and/or useful. Check out <a href="https://medium.com/hard-mode/shaker-maker-part-ii-2d3dc7282305">Part II</a> to see how I created the animated playback feature and Part III (coming soon) to see how I implemented an in-app music player. Thanks for reading!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=462ceb4bb577" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/shaker-maker-part-i-462ceb4bb577">Shaker Maker: Part I</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Continuations]]></title>
            <link>https://medium.com/hard-mode/continuations-d6e90619dfa8?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/d6e90619dfa8</guid>
            <category><![CDATA[continuation]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[code]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[scheme]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Tue, 31 Oct 2017 23:59:09 GMT</pubDate>
            <atom:updated>2017-10-31T23:58:59.790Z</atom:updated>
            <content:encoded><![CDATA[<p>Continuations give the programmer a way to control the flow of a program. While the concept itself exists in any programming language, continuations are most powerful in languages that treat them as first-class citizens and that include tail-call optimization. This post is an introduction to continuations and will not go into continuation passing style (CPS) or delimited continuations, but if you are interested in learning more these are two areas that you can explore.</p><h3>What is a continuation?</h3><p>A continuation can be thought of as the <strong>rest</strong> of a computation. This statement makes little sense on its own; it is best understood by example.</p><p>Take for example the following computation:</p><pre>5 + (6 * 3) - 12</pre><p>The <strong>current</strong> computation is (6 * 3) . The continuation at this moment is the rest of the computation, meaning all of the computation excluding the current computation, i.e. “add five and subtract twelve.” This can be represented as 5 + _ — 12, where _ is a <em>hole</em> in the continuation that will be filled by the result of the current computation. The continuation will change throughout the computation cycle. Once (6 * 3) is computed, the computation effectively becomes 5 + 18 — 12 . The current computation at this moment becomes (5 + 18) and the continuation becomes _ — 12 . Then, the current computation becomes 23 — 12 and the continuation at this moment is empty, as there is no computation to be executed after the current computation returns a value.</p><p>Another way to think about continuations is that they provide a way to refer to the state of a program at an arbitrary point in its execution. I especially like the description provided in an <a href="https://groups.google.com/forum/#!msg/perl.perl6.language/-KFNPaLL2yE/_RzO8Fenz7AJ">email</a> log from Perl programming pro Luke Palmer:</p><blockquote>People say continuations are like time<br>traveling; I like to put it this way:</blockquote><blockquote>Say you’re in the kitchen in front of the refrigerator, thinking about a<br>sandwitch (sic). You take a continuation right there and stick it in your<br>pocket. Then you get some turkey and bread out of the refrigerator and<br>make yourself a sandwitch, which is now sitting on the counter. You<br>invoke the continuation in your pocket, and you find yourself standing<br>in front of the refrigerator again, thinking about a sandwitch (sic). But<br>fortunately, there’s a sandwitch (sic) on the counter, and all the materials<br>used to make it are gone. So you eat it. :-)</blockquote><blockquote>A continuation doesn’t save data. It’s just a closure that closes over<br>the execution stack (and any lexicals associated with it; thus the “I<br>want a sandwitch” (sic) thought). If things change between the taking and<br>invoking of the continuation, those things remain changed after<br>invoking.</blockquote><h3>Why are continuations useful?</h3><p>One of the major use-cases of continuations is in nondeterministic programming. Continuations provide a way for a program to make a branching decision at runtime, based on criteria not directly specified by the programmer. The programmer may specify a number of alternatives, and the program chooses at runtime which branch to follow. One example of a method of choice in such a scenario, is backtracking. A backtracking algorithm will incrementally build the solution to a problem, abandoning a potential solution branch if it fails at any point in the branch and backtracking to a previous point in the program to seek a new potential solution branch. Continuations provide a way to return to a previous state in the program; however the things that changed before the application/invocation of the continuation remain changed (i.e. the branch that is known to be a failing branch is cut from potential solutions). Continuations can also be a powerful way to control program flow in web applications. The Seaside web framework makes extensive use of continuations for example.</p><h3>Getting started with continuations in Scheme</h3><p>Here is a functional representation of the first continuation in the example from the introduction, written in scheme. (the current computation being (6 * 3) and the current continuation being 5 + _ — 12 .</p><pre>((lambda (v)<br>  (- (+ 5 v) 12)) <br> (* 6 3))</pre><p>The lambda expression is a representation of the continuation. The lambda expression is applied to the multiplication of 6 and 3 which is a representation of the current computation.</p><p>Scheme however, allows you to “grab” the current continuation using a procedure call-with-current-continuation or call/cc .</p><pre>(- (+ 5 (call/cc <br>         (lambda (k) <br>           (begin<br>             (set! *k* k)<br>             (k (* 6 3))))))<br> 12)</pre><p>In scheme continuations are first-class citizens, meaning that we can <em>set bang</em> a variable, *k*, to capture the current continuation. In this way, we can apply the captured continuation to any arbitrary value outside of the context in which it was captured (ex. (*k* (* 3 4)) evaluates to 5 ). While this is a simple example, the technique opens the door to some very interesting and powerful programming paradigms.</p><p>Another example of using call/cc can be found in <a href="https://www.scheme.com/tspl4/further.html#g63">chapter 3</a> of The Scheme Programming Language by Kent Dybvig.</p><pre>(define product<br>  (lambda (ls)<br>    (call/cc<br>      (lambda (break)<br>        (let f ([ls ls])<br>          (cond<br>            [(null? ls) 1]<br>            [(= (car ls) 0) (break 0)]<br>            [else (* (car ls) (f (cdr ls)))]))))))</pre><pre>;(product &#39;(1 2 3 4 5)) =&gt; 120<br>;(product &#39;(7 3 8 0 1 9 5)) =&gt; 0</pre><p>This example demonstrates a nonlocal exit from a recursion. This program recursively multiplies the numbers in a list, but will immediately return zero if a zero is detected within the list, without performing any of the pending multiplications. In this example, the current continuation is stored in break . If a zero is the car of the list at the current recursive call, the current continuation is applied to zero. Since the current continuation is the lambda expression within the definition of product, the entire procedure applied to the list immediately evaluates to zero.</p><p>Once you start to get the hang of continuations, you can look into delimited continuations, which allow you to implement essentially any control structure in programming. I would point you to the work of Kenichi Asai, a programmer and professor at Ochanomizu University in Japan.</p><p><strong>NOTE: Most of the ideas in this post were taken from William Byrd. I highly recommend looking into his talks, videos, google hangouts, and books. This post is based largely off of his google hangouts </strong><a href="https://www.youtube.com/watch?v=2GfFlfToBCo"><strong>video</strong></a><strong> on continuations. It is my intent to share these ideas with you, and reflect on the concepts that I have learned.</strong></p><h3>Other Sources:</h3><blockquote><a href="http://matt.might.net/articles/by-example-continuation-passing-style/">http://matt.might.net/articles/by-example-continuation-passing-style/</a><br><a href="https://www.youtube.com/watch?v=2GfFlfToBCo">https://www.youtube.com/watch?v=2GfFlfToBCo</a><br><a href="http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/">http://matt.might.net/articles/programming-with-continuations--exceptions-backtracking-search-threads-generators-coroutines/</a><br><a href="https://www.scheme.com/tspl4/further.html#g63">https://www.scheme.com/tspl4/further.html#g63</a><br><a href="https://www.youtube.com/watch?v=QNM-njddhIw">https://www.youtube.com/watch?v=QNM-njddhIw</a><br><a href="https://marijnhaverbeke.nl/cps/">https://marijnhaverbeke.nl/cps/</a><br><a href="http://www.cs.toronto.edu/~david/courses/csc324_w15/extra/choice.html">http://www.cs.toronto.edu/~david/courses/csc324_w15/extra/choice.html</a><br><a href="https://groups.google.com/forum/#!msg/perl.perl6.language/-KFNPaLL2yE/_RzO8Fenz7AJ">https://groups.google.com/forum/#!msg/perl.perl6.language/-KFNPaLL2yE/_RzO8Fenz7AJ</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d6e90619dfa8" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/continuations-d6e90619dfa8">Continuations</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Programming Poetry: Duff’s Device]]></title>
            <link>https://medium.com/hard-mode/programming-poetry-duffs-device-a8b2da177284?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/a8b2da177284</guid>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[code]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[c-programming]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Wed, 11 Oct 2017 01:15:05 GMT</pubDate>
            <atom:updated>2017-10-11T01:14:52.767Z</atom:updated>
            <content:encoded><![CDATA[<p>Duff’s Device is a really clever implementation of dynamic loop unrolling. Tom Duff wrote the code in 1983 while working at Lucasfilm. Duff invented his particular implementation of loop unrolling in order to optimize a routine that copied an array of shorts into the Programmed IO data register of an Evans &amp; Sutherland Picture System II. Let’s check out the code first, and then take a look at some background information which will help to understand it.</p><pre>send(to, from, count)<br>	register short *to, *from;<br>	register count;<br>	{<br>		register n=(count+7)/8;<br>		switch(count%8){<br>		case 0:	do{	*to = *from++;<br>		case 7:		*to = *from++;<br>		case 6:		*to = *from++;<br>		case 5:		*to = *from++;<br>		case 4:		*to = *from++;<br>		case 3:		*to = *from++;<br>		case 2:		*to = *from++;<br>		case 1:		*to = *from++;<br>			}while(--n&gt;0);<br>		}<br>	}</pre><p>Magic. Now let’s back up and try to understand it.</p><h3>The Evans &amp; Sutherland Picture System</h3><p>The code was written for The Evans &amp; Sutherland Picture System II. Check out this front page of a pamphlet on the Picture System I from 1974. It’s a blast from the past!</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cbIZFTHsAbXusQEgT03YVQ.jpeg" /><figcaption>a pamphlet on the Picture System 1 from 1974</figcaption></figure><p>Duff wrote his code for the Picture System II, but one can safely assume that it was quite similar to version I. The machine was used to visualize and manipulate 3D models in real time. It included a tablet and pen that together served as the standard graphic input device. The images below should give you an idea of how The Picture System was used.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*vEgd_hPpvT1FQBKson8CfQ.png" /></figure><h3>The Impetus</h3><p>Here is an example of a routine from a program that Duff was working on for the Picture System.</p><pre>send(to, from, count)<br>	register short *to, *from;<br>	register count;<br>	{<br>		do<br>			*to = *from++;<br>		while(--count&gt;0);<br>	}</pre><p>In an <a href="http://www.lysator.liu.se/c/duffs-device.html">email</a> from 1983, where Duff formally introduced his device, he also described the impetus for writing it. He included the routine above and noted the following:</p><blockquote>As it turns out, this loop was the bottleneck in a real-time animation playback program which ran too slowly by about 50%.</blockquote><p>The typical solution, as he states in the email, is loop unrolling. In order to understand Duff’s Device, we must first understand the concept of loop unrolling.</p><h3>Loop Unrolling</h3><p>Loop unrolling is an optimization technique that trades program size for speed. The binary size of the program is increased, but execution speed is gained. The technique works by transforming a loop in order to eliminate assembly instructions that control the loop. In the case of the VAX C compiler that The Picture System II used, the do-while loop in question would be compiled into two instructions: <strong>movw</strong> and <strong>subleq</strong>. The <strong>movw</strong> instruction makes a copy of one register pair into another register pair, and the <strong>subleq</strong> instruction specifies “SUbtract and Branch if Less than or EQual to zero”. Let’s consider the do-while loop of interest and examine the assembly instructions.</p><pre>{<br>       	do<br>		*to = *from++;        // compiles to a movw<br>	while(--count&gt;0);             // compiles to a subleq<br>}</pre><p>If count were say, 20, then the loop above would compile down to 20 movw instructions and 20 subleq instructions. Now, let us consider <em>unrolling</em> the loop in order to decrease the number of subleq instructions run by the computer.</p><pre>int n = count / 5;                // if count is 20, n is 4<br>{<br>       	do<br>	       *to = *from++;     // 5 copies will be executed<br>               *to = *from++;     // each iteration of the <br>               *to = *from++;     // loop<br>               *to = *from++;<br>               *to = *from++; <br>	while(--n&gt;0);             // the loop will run 4 times <br>}                                 // for the same total of 20 copies</pre><p>By duplicating the body of the loop, it has been unrolled 5 times. The resulting compiled C code includes the same 20 movw instructions as the original loop, but the unrolled loop includes only 4 subleq instructions. You might be asking yourself: what happens if count is not evenly divisible by 5? In this case, programmers often implement a post-processing loop or a switch statement to handle the remainder. A switch implementation might look something like this:</p><pre>int remainder = count % 5;<br>switch (remainder)                <br>{<br>        case 4 : *to = *from++;      <br>        case 3 : *to = *from++;<br>        case 2 : *to = *from++;<br>        case 1 : *to = *from++;<br>        case 0 : ;<br>}</pre><p>This code will execute the remaining number of register copies not completed in the unrolled loop. This code compiles down to a number of movw instructions equal to remainder (plus the instructions required for the switch calculation and branching to the correct case label). It is important to understand that in C, switch statements do not break automatically before each case label. This means that once code execution begins at the calculated case label, it <em>falls through</em> the remaining case labels executing each line of code in succession. This property of C is instrumental in Duff’s implementation of loop unrolling.</p><p>Since movw instructions are executed faster than subleq instructions, the unrolled loop coupled with a switch statement accomplishes the same task as the original loop and runs significantly faster. Now that we understand loop unrolling, let’s take a look at Duff’s clever implementation.</p><h3>Duff’s Device</h3><p>Duff essentially wove together a loop unroll and a switch statement to poetically express the same idea that the two code blocks express separately. It is surprising to many, that it is in fact legal C code.</p><p>Here it is, Duff’s Device, in all its beauty:</p><pre>send(to, from, count)<br>	register short *to, *from;<br>	register count;<br>	{<br>		register n=(count+7)/8;<br>		switch(count%8){<br>		case 0:	do{	*to = *from++;<br>		case 7:		*to = *from++;<br>		case 6:		*to = *from++;<br>		case 5:		*to = *from++;<br>		case 4:		*to = *from++;<br>		case 3:		*to = *from++;<br>		case 2:		*to = *from++;<br>		case 1:		*to = *from++;<br>			}while(--n&gt;0);<br>		}<br>	}</pre><p><em>note: There is no post increment on the </em><em>to pointer, because the device was meant to copy values serially into an IO register. The device could be used for general memory copy if the postfix ++ were to be included.</em></p><h3>How it works</h3><p>Duff’s Device includes a loop unwound 8 times. The loop is embedded in a switch statement such that the switch calculates the remainder of register copies to carry out before the loop is entered. Execution jumps into the loop at the calculated case label, falls through the remaining case labels, and then hits the while keyword which will jump to the beginning of the do-while loop and execute cycles of 8 register copies until n reaches 0.</p><h4>Disadvantages</h4><p>This speed increase is not without consequences, however. The static code size is increased, which may be undesirable or excessive and can in turn cause an increase in instruction cache misses. In order to determine whether it is worth manually unrolling a loop, the cost of increased static code size and cache misses must be weighed against the gain in program execution speed. It is worth noting that nowadays it is increasingly rare that a programmer needs to manually unroll a loop since most modern compilers are very good at optimization and will already unroll loops where they deem appropriate.</p><h3>Sources</h3><blockquote><a href="https://stackoverflow.com/questions/514118/how-does-duffs-device-work">https://stackoverflow.com/questions/514118/how-does-duffs-device-work</a><br><a href="http://www.lysator.liu.se/c/duffs-device.html">http://www.lysator.liu.se/c/duffs-device.html</a><br><a href="http://www.drdobbs.com/a-reusable-duff-device/184406208">http://www.drdobbs.com/a-reusable-duff-device/184406208</a><br><a href="https://en.wikipedia.org/wiki/Duff%27s_device#Performance">https://en.wikipedia.org/wiki/Duff%27s_device#Performance</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a8b2da177284" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/programming-poetry-duffs-device-a8b2da177284">Programming Poetry: Duff’s Device</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Thief: Milkmaid Heist]]></title>
            <link>https://medium.com/hard-mode/thief-milkmaid-heist-b5de140c9db?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/b5de140c9db</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[games]]></category>
            <category><![CDATA[ruby]]></category>
            <category><![CDATA[code]]></category>
            <category><![CDATA[videogames]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Mon, 02 Oct 2017 01:39:53 GMT</pubDate>
            <atom:updated>2018-04-03T03:24:31.835Z</atom:updated>
            <content:encoded><![CDATA[<p>A couple weeks ago, I built a CLI game in Ruby with a friend and peer at Flatiron School, Cole Shapiro, called <strong><em>Thief: Milkmaid Heist. </em></strong>TMH<strong><em> </em></strong>is a text-based adventure game where you play as the international art thief, Vince Peruggi, breaking into the Rijskmuseum in Amsterdam to steal valuable works of art. We built the game in three days; it turned out to be an interesting project.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*p_4ANQ_3ELljpc-MYcePlw.gif" /><figcaption>opening screen</figcaption></figure><h3>The Story</h3><p>The game takes place in Amsterdam in 2005 during a large renovation of the Rijksmuseum. The renovation provides the perfect opportunity to break in and steal priceless works of art. The player gets to choose gadgets to take with them on the heist to help them overcome obstacles in the museum such as laser sensors, noise alarms, and security guards. Familiar text-based adventure game elements like open ended user input are present, as well as some pretty cool colorized ascii art representing the works on display at the museum. The player breaks into the museum, navigates the corridors to discover art that they may steal, and encounters obstacles along the way that they must overcome using their gadgets.</p><h3>Gameplay</h3><p>The goal of the game is to steal as much art as possible from the Rijksmuseum, and to ultimately steal the famous Vermeer painting, <em>The Milkmaid.</em> The game begins at the thief’s hideout. The player must select 5 gadgets to bring with them on the heist. As the heist begins, the player finds themself outside of the Rijksmuseum, where they must choose their entry point into the museum. Once inside, the player encounters obstacles that are randomly generated by the game engine. For example, the player may notice laser emitters on the walls suggesting that the corridor is rigged with a labyrinth of laser sensors. If the player has selected their gadgets wisely, then they will be able to use a gadget to overcome the obstacle. It is also possible for the player to attempt to rely on their base skills as a thief to overcome an obstacle. However, this will drain the player’s stats, lowering the probability of being able to overcome an obstacle in the same manner in the future.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*kzXfibTYIf3t1FQLYDxKWQ.gif" /></figure><p>After every obstacle that the player successfully overcomes, they reach a new corridor of the museum with art available for them to steal. Every time they attempt to steal a work of art, there is a random chance that they will trip an alarm. If the player can disable the alarm, then they can steal the artwork and continue the heist. If the player avoids all obstacles and is able to reach the grand hall containing “The Milkmaid,” then they can steal it and escape the museum.</p><h3>Connecting to the Rijskmuseum API</h3><p>We pulled all of the data pertaining to the artworks in the game, including images of the art, from the Rijksmuseum API. We parsed the JSON data into artwork attributes which we stored in a database. Then, we used Active Record to instantiate Ruby objects with corresponding attributes from the database. As a player explores new corridors in the Rijksmuseum, we randomly generate artworks from the database (and render an image in ascii art form) that the player can encounter and attempt to steal.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*GPjn2dGuwS2sURXHETSZuQ.gif" /></figure><h3>Incorporating Randomness</h3><p>One of our goals was to incorporate randomness and attempt to encourage emergent behavior in the game. We wanted to avoid a completely linear and obviously scripted experience. We implemented a number of design choices in order to achieve an interesting and unique game experience for each playthrough.</p><ul><li>The obstacles that a player encounters are randomly chosen.</li><li>The player gets to choose which gadgets to take with them on the heist at the beginning of each playthrough.</li><li>Each gadget and obstacle has unique stats including: technical complexity, physical demand, and willpower required.</li><li>Gadgets can be used in a variety of unique ways to overcome obstacles.</li><li>The artworks that are generated in each playthrough are randomly chosen.</li><li>When a player attempts to steal an artwork, there is a random chance that they will trip an alarm and have to disarm it.</li></ul><h3>Ascii Art</h3><p>The images of the works of art on display at the Rijskmuseum were converted into ascii art using the Ruby gem ‘asciiart’ and a program called Image Magick. Another Ruby gem ‘rainbow’ enabled the images to be converted into colored ascii art.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/826/1*VXA-8TmZyV_PV9b1AXCgSA.png" /><figcaption>Portraits of Giuliano and Francesco Giamberti da Sangallo, Piero di Cosimo, 1482</figcaption></figure><p>I had a lot of fun building <em>Thief: Milkmaid Heist</em> with Cole and I am happy with what we created in such a short period of time. If you are interested, feel free to check out the github repository: <a href="https://github.com/xxDOOMbox/THIEF-cli"><em>https://github.com/bitwitch/THIEF-cli</em></a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b5de140c9db" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/thief-milkmaid-heist-b5de140c9db">Thief: Milkmaid Heist</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[The Legendary Fast Inverse Square Root]]></title>
            <link>https://medium.com/hard-mode/the-legendary-fast-inverse-square-root-e51fee3b49d9?source=rss----f0c797c030df---4</link>
            <guid isPermaLink="false">https://medium.com/p/e51fee3b49d9</guid>
            <category><![CDATA[videogames]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[c-programming]]></category>
            <category><![CDATA[coding]]></category>
            <category><![CDATA[code]]></category>
            <dc:creator><![CDATA[Shaw]]></dc:creator>
            <pubDate>Mon, 18 Sep 2017 15:33:29 GMT</pubDate>
            <atom:updated>2020-05-07T21:32:06.348Z</atom:updated>
            <content:encoded><![CDATA[<p>In the 90s, 3D video games were in their infancy, and the ability to render 3D graphics was constrained by hardware. This led programmers to devise creative ways to get around hardware limitations. One such innovation, known as the Fast Inverse Square Root function, was introduced in id Software’s First Person Shooter from 1999, Quake III Arena.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/460/1*vBFusX31Iwr5LYULQGolpQ.gif" /><figcaption>gameplay from Quake III Arena</figcaption></figure><h3>Why inverse square roots?</h3><p>Inverse square roots are useful in video game graphics and particularly in 3D game engines. Pathfinding, lighting, reflections, and many other game programming techniques require vector normalization, which involves an inverse square root operation. Inverse square roots, which rely on floating point division, are expensive for processors. In a fast paced, graphically intense game like Quake III Arena, these calculations are made millions of times every second, so even a minor improvement in the performance of such a calculation could significantly improve graphics computation speed and ultimately the game’s frame rate. So how did programmers of the <em>id Tech 3</em> engine get around the expensive inverse square root function? They implemented a very accurate, very fast approximation.</p><h3>Source Code</h3><p>Here it is, in all it’s glory: the fast inverse square root source code from Quake III Arena! The preprocessor directives have been removed, but the code and comments are as they appeared in the Quake engine.</p><pre>float Q_rsqrt( float number )<br>{<br>    long i;<br>    float x2, y;<br>    <strong>const</strong> float threehalfs = 1.5F;<br><br>    x2 = number * 0.5F;<br>    y  = number;<br>    i  = * ( long * ) &amp;y;    <em>// evil floating point bit level hacking</em><br>    i  = 0x5f3759df - ( i &gt;&gt; 1 );               <em>// what the fuck? </em><br>    y  = * ( float * ) &amp;i;<br>    y  = y * ( threehalfs - ( x2 * y * y ) );   <em>// 1st iteration</em><br><em>//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration,<br>                                              // this can be removed</em><br><br>    <strong>return</strong> y;<br>}</pre><p>Okay… so that’s ridiculous. Nothing short of voodoo black magic, but let me try to explain. The overall idea of this approximation is essentially a Newton-Raphson iteration. The Newton-Raphson root finding method works like this: given an approximation of a numbers root, c, a better approximation is found using y = c/2 * (3 — xc²) . The fast inverse square root function implements a single Newton-Raphson iteration starting with a really clever first guess.</p><p>Let’s take a closer look at how it works:</p><h3>1. Get the bits of the floating point number</h3><p>y = number;<br>In C, a single-precision float is stored in memory as a 32 bit number. Bit 31 represents the sign, bits 30 - 23 represent an 8 bit exponent, and bits 22 - 0 represent a 23 bit mantissa — a binary number with the decimal point to the left.</p><h3>2. Reinterpret the number as an integer</h3><p>i = * ( long * ) &amp;y;<br>The same 32 bit number can also be interpreted as an integer, where the most significant bit stores the sign.</p><h3>3. Bitwise shift the 32 bit number to the right by one</h3><p>( i &gt;&gt; 1 );<br>A single bit shift to the right inserts a 0 as the most significant bit and drops the least significant bit of a number. This effectively divides the integer interpretation of the number by 2. However if the same number were to be interpreted as a float, the change is much more drastic than division by 2. The bitwise shift negates the exponent and divides it by 2, shifts a bit from the exponent into the mantissa, and drops the least significant bit of the mantissa.</p><h3>3. Subtract the bit-shifted number from 0x5f3759df</h3><p>i = 0x5f3759df — ( i &gt;&gt; 1 );<br>Chris Lomont explains in his <a href="http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf">paper</a> that the initial guess used in Quake III Arena’s fast inverse square “is piecewise linear, and the function being approximated is not the same in all cases.” When shifting the number’s bits to the right by one, there are two possible cases: either the number’s exponent is even or it is odd. The magic hex number, 0x5f3759df, was chosen such that it minimizes the error between the two cases. Thus, whether the bit-shifted number has an odd or even exponent, subtracting the number from the magic number yields an accurate approximation of the inverse square root of the original number (once the result, i , has been reinterpreted as a float).</p><h3>4. Reinterpret the result as a float</h3><p>y = * ( float * ) &amp;i;<br>At this point, i is stored in memory as an integer. The function reinterprets i and stores the result in memory as a floating point number. This number is a relatively accurate initial guess of the inverse square root of the input value.</p><h3>5. Perform a Newton-Raphson iteration</h3><p>y = y * ( threehalfs — ( x2 * y * y ) );<br>A single Newton-Raphson iteration is performed to calculate a more accurate approximation of the inverse square root of the input. The result of the Newton-Raphson iteration is the return value of the function. The result is extremely accurate with a maximum error of 0.175%.</p><p>The real genius of this code, is the line:</p><pre>i  = 0x5f3759df - ( i &gt;&gt; 1 );</pre><p>As I said before, voodoo black magic. Where did it come from? Who on Earth conjured such sorcery?</p><h3>Origin of the Fast Inverse Square Root</h3><p>The Fast Inverse Square Root has an interesting history. The original author was not revealed until 2006, 7 years after the game’s release, and around 20 years after the code was originally written. Rys Sommerfeldt, Senior Manager of the European Game Engineering Team at AMD RTG, launched an <a href="https://www.beyond3d.com/content/articles/8/">investigation</a> into the function’s origins in 2004. He began his search with John Carmack, lead programmer of Quake III, who denied authorship and suggested Terje Mathisen, a master of x86 assembly programming who helped with optimization on the Quake III engine.</p><p>Sommerfeldt reached out to Mathisen, who replied that he had, in fact, written an inverse square root function some 5+ years earlier, but that the Quake fast inverse square root function was <em>not</em> the one that he wrote. He suggested that it looked like something that might have come from MIT’s HAKMEM documents.</p><p>More investigative work from Sommerfeldt led him to a contact at NVIDIA who suggested he ask Gary Tarolli, an employee at NVIDIA and a founding member of 3dfx. Sommerfeldt emailed Gary, who responded that the function definitely passed by his keyboard many times. Gary said that he had simulated different hex constants in his work on the IRIS Indigo workstation computer, but that he was <strong>not </strong>the original author. With no other leads, the investigation lay dormant for about a year.</p><p>As the article that Sommerfeldt wrote gained publicity, it finally reached the eyes of the original author of the Fast Inverse Square Root function, Greg Walsh! *<em>thunderous applause</em>* Greg Walsh is a monument in the world of computing. He helped engineer the first WYSIWYG (“what you see is what you get”) word processor at Xerox PARC and helped found Ardent Computer. Greg worked closely with Cleve Moler, author of Matlab, while at Ardent and it was Cleve who Greg called the inspiration for the Fast Inverse Square Root function.</p><p>The Fast Inverse Square Root function is a beautiful bit of code. I am both inspired and mesmerized by it. The world has Greg Walsh, the artist, and Cleve Moler, the muse, to thank for bringing such a brilliant work of art to creation.</p><h3>Sources:</h3><blockquote><a href="https://www.beyond3d.com/content/articles/8/">https://www.beyond3d.com/content/articles/8/</a><br><a href="https://www.beyond3d.com/content/articles/15/">https://www.beyond3d.com/content/articles/15/</a><br><a href="http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf">http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf</a><br><a href="https://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/">https://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/</a><br><a href="https://en.wikipedia.org/wiki/Fast_inverse_square_root">https://en.wikipedia.org/wiki/Fast_inverse_square_root</a></blockquote><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e51fee3b49d9" width="1" height="1" alt=""><hr><p><a href="https://medium.com/hard-mode/the-legendary-fast-inverse-square-root-e51fee3b49d9">The Legendary Fast Inverse Square Root</a> was originally published in <a href="https://medium.com/hard-mode">Hard Mode</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>