tag:blogger.com,1999:blog-55817705009380147482024-03-14T02:27:55.803-07:00Mad Man with a CompilerPreston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.comBlogger25125tag:blogger.com,1999:blog-5581770500938014748.post-64617691516619614002024-02-04T13:00:00.000-08:002024-02-04T13:00:12.633-08:00Lessons from Ancient File Systems<p>In my <a href="https://madcompiler.blogspot.com/2024/02/a-user-space-file-system-for-fun-and.html">previous post</a>, I mentioned that I found a number of oddities when digging through the details of various Atari 8-bit file systems. I read through the specifications I could find online, and ran the actual code in emulators to verify and discover details when the specifications were unclear or incorrect. There were some surprising finds.</p><p>I looked at:</p><p></p><ul style="text-align: left;"><li>Atari DOS 1.0</li><li>Atari DOS 2.0s</li><li>Atari DOS 2.0d</li><li>Atari DOS 2.5</li><li>MyDOS 4.5</li><li>Atari DOS 3</li><li>Atari DOS 4 (prototype, never released)</li><li>DOS XE</li><li>LiteDOS</li><li>Sparta DOS</li></ul><p></p><p>Atari DOS 1.0 started it all off back in 1979. It supported single-sided, single-density disks that consisted of 720 sectors holding 128 bytes each. It has some bugs and implementation limitations, so DOS 2.0s ('s' for single density) soon replaced it, making some key changes. Soon other DOS versions started appearing, some trying to maintain backwards compatibility, and others trying completely new approaches. I won't go into the technical details, but I do want to highlight what I think are the most interesting design decisions.</p><p>Keep in mind that DOS 1 was designed when they were planning on selling the base Atari 800 with only 8K of RAM. (The 400 would have been only 4K, but marketed with a cassette drive instead.) So the design minimized the need for additional sector buffers. Hence the strategy for files was to use the last few bytes of each sector as metadata, including the link to the next sector in the file.</p><p>Atari used 6 bits at the end of each sector to hold a file number. This was the index of the file in the directory. (The other two bits and another byte together pointed at the next sector of the file.) This was presented in documentation as being there to detect file corruption, which seemed like a waste, as that sort of file corruption almost never happened. But I'm now pretty sure that wasn't the reason the file number was there. Instead, it was to support "note" and "point" commands. Atari believed people would use files as a database, and with the sector chaining, it was impossible to jump around in a file without reading it linearly. So a program could "note" its position in a file (sector and offset) and then return there later with the point command. This is where verifying that the file number in the user-supplied sector number matched the entry used when opening the file came in. Without that number, there would be no verification that a "point" would end up in the right file.</p><p>In DOS 1, the last byte of each sector was a sector sequence number with the high bit cleared. This was a nice idea, and would have been useful if someone were writing a tool to undelete files. If the high bit were set, it was the last sector of the file, and the low bits were the number of data bytes in the sector. In DOS 2, the last byte was instead always the number of data bytes in the sector. This would seem to have made the code simpler, but actually the opposite, as DOS 2 also included compatibility code for reading DOS 1 files (as did DOS 2.5). The real reason is that allowed partially filled sectors in the middle of files, which happened when a file was opened for append, as it would start with an empty write buffer instead of filling it with the data from the last sector. (DOS 1 didn't have an append option at all.) I would have thought it would have been simpler to implement append without partial sectors and avoid needing compatibility code, but apparently not.</p><p>Several less-popular versions of DOS didn't support zero-length files. If you opened a new file for writing and closed it without first writing anything, the file was deleted. That seems crazy today, but at the time, that was not one of the quirks people complained about; mostly those DOS versions were unpopular because of incompatibility and issues like wasted space from internal fragmentation.</p><p>Only two versions of DOS supported time stamps on files, DOS XE and Sparta DOS. Nobody wanted to type in the date and time on every boot, and a battery-backed real-time clock wasn't a standard feature of any of the 8-bit computers that I'm aware of (certainly not the Atari).</p><p>Several versions of DOS supported subdirectories. This was mostly for versions that supported larger disks, like MyDOS and SpartaDOS.</p><p>One quirk of Atari DOS (1, 2, and 4) is putting the directory and free sector bitmap table on a track in the middle of the disk. The theory was that this would minimize seek time between reading the directory and reading a file. Not a horrible idea, though it was horribly mangled by an off-by-one error because sector numbers on the drive were 1-based instead of 0-based as the original coders believed, so there was a seek between the sector bitmaps and the directory. They doubled down on this in DOS 4, where the location of the directory changes depending on the disk format, so larger disks have the directory at higher sector numbers. There was a lot wrong with DOS 4; it probably would have been quite unpopular if it had made it past being a prototype without significant changes.</p><p>The biggest problem with the official Atari versions of DOS is that they never anticipated future needs. I can forgive DOS 1, as it was developed on a short time frame for an 8K computer, and that locked in DOS 2 for compatibility reasons. But DOS 3 was a disaster. Atari had a new drive that could format 130K disks as well as the old 90K disks, so they needed a new DOS that would take advantage of the new space. But they ignored other drives with 256-byte double-density sectors (180K) and the possibility of double-sided disks (360K) that were already on the market for other computers. Better engineers would have designed something to grow and meet future needs, but instead they just implemented the minimum requirements. So when Atari was later designing the 1450XLD computer which did have 360K drives, they had to have a new DOS again. While that was never released, they did develop a DOS for it, which again, only handled the specific formats that that drive supported, with no thoughts for the future.</p><p>On the other hand, the most successful DOS versions for the retro computing Atari community now are precisely the ones that could scale to any drive, namely MyDOS and SpartaDOS. MyDOS retained DOS 2 compatibility, but extended it to support upto 16MB drives and adding subdirectories. SpartaDOS dropped compatibility, but was able to support 512-byte sectors, allowing for 32MB drive support. (The Atari's I/O protocols limited the system to a 16-bit field for sector numbers.)</p><p>So the big lesson here is to always plan for the future. Listen to the requirements for the current product, but then design with the assumption that you'll be asked to expand the requirements in the future. If you don't, users may be cursing you when the code is released. But who knows? If you do it right, people may still be using your code in 40 years.</p>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-30760573477694194342024-02-04T12:47:00.000-08:002024-02-05T10:52:34.975-08:00A User-Space File System for Fun and HistoryI got my start with computers as a kid with an Atari 800 way back when. When I'm feeling nostalgic, I still enjoy pulling it out and playing with it. These days, I'm more likely to pull out an emulator than the real thing, as they're now so precise that it's very difficult to find a difference, and it eliminates all the hassles involved with disks that were slow and may have failed with age. That means I need tools for manipulating disk images.<div><br /></div><div>So there I was... I was posting at AtariAge about a tool I wrote to extract the files from a disk image, and another to create an image containing a set of files, and someone remarked that they were surprised that nobody had created a Linux kernel module to mount the disk image files as a file system. That was a dangerous comment. Writing a Linux kernel module to support Atari file systems is certainly possible, but would be a lot of work. But there's another option, which is to write a file system in user space using a package called "FUSE."</div><div><br /></div><div>I've written a file system using FUSE before, and it's far less complicated than writing one in kernel space. Besides making debugging vastly simpler, you can also just skip lots of things and the library will take care of it for you. And with Atari file systems, there are, of course, many modern features that just aren't supported. And another big advantage of FUSE is that it works on MacOS as well as Linux, so it makes the project available to a wider audience. (It also runs on the Windows Subsystem for Linux.)</div><div><br /></div><div>But note that I said Atari file system<b>s</b>, not file system. Depending on how you count, I found at least seven or perhaps ten different file systems. (Several are variations, so they can share most of the same code.) This means the first task is to detect which file system a disk image is using, if any (as many programs just read disk sectors directly and didn't use a file system at all). </div><div><br /></div><div>So the first step is to have sanity checking routines to determine if a disk image is consistent for each file system. Then implement the key file system features for each DOS version. The key functions that had to be implemented are reading a directory, getting file attributes, reading a file, and writing a file. Most other features are trivial or unsupported for most file systems, but I implemented as much as possible. For example, files could be locked, which I interpreted as the write-permission bit for the file owner. Some file systems did support time stamps on files, but for most, I just copied the time stamp on the disk image file.</div><div><br /></div><div>But once it was working, it was quite simple to add more features. So I made files like ".sector361" that would contain the raw bytes of sector 361. The file doesn't have to exist in the directory, but as long as it's supported by the get attributes, read, and possibly write functions, it will work just fine. This feature was also very helpful in debugging the file systems, as I could look at a hexdump of raw sectors when something wasn't behaving as expected, or when I had to reverse engineer a file system with incomplete specifications.</div><div><br /></div><div>Of course, every time I finished a file system or new feature, someone on AtariAge would find yet another for me to look at. That was really half the fun of it. I discovered a number of file systems used on the Atari that I hadn't encountered before, and there were some weird ones. The oddities of those file systems probably deserves <a href="https://madcompiler.blogspot.com/2024/02/lessons-from-ancient-file-systems.html">its own blog post</a>.</div><div><br /></div><div>But once I had it pretty solid, there was another wrinkle. There's a special "Atari Partition Table" format for hard disks that's used with some newer add-ons, including flash card readers that people now use with their old computers. This presented two major problems. First, the documentation for the APT images, while detailed, had points that were confusing or ambiguitiies, and included many options that aren't actually used. This required getting sample images from users, as I didn't use it myself. Second, this meant having a number of different file systems mounted in subdirectories. That required refactoring the code, including adding a middle layer to call into. Sometimes adding an extra layer of indirection lets you do magic.</div><div><br /></div><div>Unfortunately, this doesn't work for all file systems in an APT partition, as the file system code uses a memory map of the image file, and with some APT options, the disk image is no longer a straight linear stream of bytes. This has to do with fitting smaller sector sizes into 512-byte sectors when sometimes you care a lot more about efficient code than efficient space. But since I can export the image of the contents of each partition, even if the bytes have to be scrambled by the read and write functions, that image can then be opened separately by a new instance of my program, creating a new mount point. A bit awkward, but it works.</div><div><br /></div><div>So that was a fun project. While this had no commercial value, it was interesting to look at ancient file systems and see how they did things, as well as to play around with FUSE.</div><div><br /></div><div>So here is the code if you're interested:</div><div><br /></div><div>https://github.com/pcrow/atari_8bit_utils/tree/main/atrfs</div><div><br /></div><div>Now I suppose what's needed next is a wrapper to take the code for a kernel file system, and run it under FUSE. That would allow you to develop a kernel file system with all the convenience of user-space tools, but you could then build the code as a kernel module once it's working. That's a project for another day.</div>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-81842086745620435062023-10-30T19:51:00.001-07:002023-10-30T19:51:53.622-07:00Apache as a Proxy<p>I have a number of different devices and services running on my home network with web interfaces, and I would like to be able to access them all from anywhere. Some of these are smart devices, some are software packages, but it doesn't really matter. I want to be able to access them all by connecting to a web page on the server running on my firewall (or wherever port 443 is forwarded).</p>
<p>To start with, I did an inventory of all the devices and servers on my network. The tool 'nmap' is idea for this. Something like this works:</p>
<p>nmap 192.168.0.1-254</p>
<p>My network is a little more complicated, but I just run the equivalent command on each subnet. For any device showing something on port 80 or 443, I connect with a web browser and see what's there. For other ports that might be web pages, I can construct a URL by adding 'http://' or 'https://' to the front and adding ':8443' or whatever the port is. If the web browser brings up anything interesting, I note that, too.</p>
<p>For the first pass, I create a web page that simply has a link to each service of interest on my network. Of course, this will only work from inside my network, but at least I now have a page listing everything that I want to connect to. Some of these will be http, others https, often with bad certificates (like my printer). That's fine, I'll eventually deal with that using my proxy.</p>
<p>There are two categories of applications that I want to proxy.</p>
<p>The simple case is web applications that for various reasons run on different web servers (either on the same system on a different port or a different system; it doesn't matter), but are already running as a subdirectory, and I just want to forward anything going to that subdirectory on the main web server to the application.</p>
<p>The complicated case is typically a device where it assumes it's its own web server, and everything is relative to the root of the server. I want to proxy it from a subdirectory on my main server, and this means modifying all the links that are passed through. Sometimes this is easy, but sometimes it's quite difficult.</p>
<p>For the simple case, I'll use an application called "mythweb" as an example. This is running on an internal server at http://192.168.0.5/mythweb/. I've set it up in my /etc/hosts file as myth.mydomain.com, so I don't have to reference the IP number. My apache installation has my server defined in /etc/apache2/vhosts.d/mydomain.conf, and I'll be adding entries to that file. So for mythweb, it's really quite simple:</p>
<!-- HTML generated using hilite.me --><div style="background: #f8f8f8; overflow:auto;width:auto;border:solid gray;color:black;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%"> <span style="color: #008000; font-weight: bold"><Location</span> <span style="color: #BB4444">/mythweb/</span><span style="color: #008000; font-weight: bold">></span>
<span style="color: #AA22FF">ProxyPass</span> http://myth.mydomain.com/mythweb/
<span style="color: #AA22FF">ProxyPassReverse</span> http://myth.mydomain.com/mythweb/
<span style="color: #008800; font-style: italic"># mythweb sets a global cookie; change path from / to /mythweb/</span>
<span style="color: #AA22FF">ProxyPassReverseCookiePath</span> <span style="color: #BB4444">"/"</span> <span style="color: #BB4444">"/mythweb/"</span>
<span style="color: #008000; font-weight: bold"></Location></span>
</pre></div>
<!-- END HTML generated using hilite.me -->
<p>That's it. Since I'm going to be defining multiple proxies as virtual subdirectories, I'm defining each as a location. The "ProxyPass" line says where to send requests for anything in this directory. The "ProxyPassReverse" is used for rewriting any redirects that the internal server may send back to the location. The final note is that this application was setting a global cookie, so the "ProxyPassReverseCookiePath" option restricts any cookies it sets to only be for the subdirectory so they don't get seen by any other programs.</p><p>Doing a proxy for something that isn't already packaged in a subdirectory can get much more complicated, as you have to tell Apache how to modify the files being served as well as as the URLs being requested. This potentially means modifying .js, .css, and .html files, and what has to be done is different for each application.</p><p>Perhaps my simplest example is my NAS management. I'm running XigmaNAS.</p>
<!--HTML generated using hilite.me--><div style="background: rgb(248, 248, 248); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: green; font-weight: bold;"><Location</span> <span style="color: #bb4444;">/nas/</span><span style="color: green; font-weight: bold;">></span>
<span style="color: #aa22ff;">ProxyPass</span> http://nas.mydomain.com/
<span style="color: #aa22ff;">ProxyPassReverse</span> http://nas.mydomain.com/
<span style="color: #aa22ff;">ProxyPassReverse</span> /
<span style="color: #aa22ff;">ProxyHTMLEnable</span> <span style="color: #aa22ff; font-weight: bold;">On</span>
<span style="color: #aa22ff;">ProxyHTMLExtended</span> <span style="color: #aa22ff; font-weight: bold;">On</span>
<span style="color: #aa22ff;">RequestHeader</span> unset Accept-Encoding
<span style="color: #aa22ff;">ProxyHTMLURLMap</span> ^/ <span style="color: green;">/nas/</span> R
<span style="color: #aa22ff;">ProxyHTMLURLMap</span> http://[w.]*mydomain[^/]*/ <span style="color: green;">/nas/</span> R
<span style="color: green; font-weight: bold;"></Location></span>
</pre></div>
<!--END HTML generated using hilite.me-->
<p>This starts out the same, but there's a good bit more. Now we need another ProxyPassReverse line for '/' to direct to the location (/nas/). Since we're modifying file internals, we turn off the "Accept-Encoding" option to disable compression. I use ProxyHTMLURLMap to do regular expression substitutions in links in html files. The "extended" option tries to also modify Javascript and CSS within html files. The two lines for changing are switching any top-level links to the subdirectory, as well as any full links. Fortunately this program doesn't use any CSS or JS files with links in them that need to be modified.</p><p>However, there's some setup for the ProxyHTMLURLMap command to define what gets treated as a URL. I've seen some references to including "proxy_html.conf," but my Apache didn't have that file, so I put these lines in directly to my config file. Note that these are not specific to a location, so I put them before the location tags:</p>
<!--HTML generated using hilite.me--><div style="background: rgb(248, 248, 248); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: #aa22ff;">ProxyHTMLEvents</span> onclick ondblclick onmousedown onmouseup onmouseover onmousemove onmouseout onkeypress onkeydown onkeyup onfocus onblur onload onunload onsubmit onreset onselect onchange
<span style="color: #aa22ff;">ProxyHTMLLinks</span> a href
<span style="color: #aa22ff;">ProxyHTMLLinks</span> area href
<span style="color: #aa22ff;">ProxyHTMLLinks</span> link href
<span style="color: #aa22ff;">ProxyHTMLLinks</span> img src longdesc usemap
<span style="color: #aa22ff;">ProxyHTMLLinks</span> object classid codebase data usemap
<span style="color: #aa22ff;">ProxyHTMLLinks</span> q cite
<span style="color: #aa22ff;">ProxyHTMLLinks</span> blockquote cite
<span style="color: #aa22ff;">ProxyHTMLLinks</span> ins cite
<span style="color: #aa22ff;">ProxyHTMLLinks</span> del cite
<span style="color: #aa22ff;">ProxyHTMLLinks</span> form action
<span style="color: #aa22ff;">ProxyHTMLLinks</span> input src usemap
<span style="color: #aa22ff;">ProxyHTMLLinks</span> head profile
<span style="color: #aa22ff;">ProxyHTMLLinks</span> base href
<span style="color: #aa22ff;">ProxyHTMLLinks</span> <span style="color: #aa22ff; font-weight: bold;">script</span> src for
<span style="color: #aa22ff;">ProxyHTMLLinks</span> iframe src
</pre></div>
<!--END HTML generated using hilite.me-->
<p>For my managed network switch, I had to also do some additional modifications to the html files to get it to work. In the process, I double-modified some URLs, so I had to undo them:</p>
<!--HTML generated using hilite.me--><div style="background: rgb(248, 248, 248); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: #aa22ff;">AddOutputFilterByType</span> SUBSTITUTE text/html
<span style="color: #aa22ff;">Substitute</span> s|action=<span style="color: #bb4444;">"/|action="</span><span style="color: green;">/switch/</span>|n
<span style="color: #aa22ff;">Substitute</span> s|=<span style="color: #bb4444;">"/"</span>|=<span style="color: #bb4444;">"/switch/"</span>|n
<span style="color: #aa22ff;">Substitute</span> s|location.href=<span style="color: #bb4444;">"/|location.href="</span><span style="color: green;">/switch/</span>|n
<span style="color: #aa22ff;">Substitute</span> s|<span style="color: #bb4444;">"/switch/switch/|"</span><span style="color: green;">/switch/</span>|n
</pre></div>
<!--END HTML generated using hilite.me-->
<p>So how did I figure that out? It's an iterative process of loading it through the proxy and looking at what files are being requested, and figuring out how the browser got the wrong information when it wasn't translating things correctly. This isn't too hard if you open up the console (Control-Alt-I in Chrome, Control-Shift-I in Firefox). There you can see every request and response as seen by the web browser. You can compare connecting directly and through the proxy.</p><p>From here it keeps getting more complicated, but it boils down to creating substitute rules for other types. I had to watch carefully in the console, as in one application I had to modify application/javascript, while in another it was application/x-javascript.</p><p>Another issue that I've encountered is proxying an internal device that uses https with a bad certificate. I have my own legitimate certificate, and I just want to ignore the internal one, and it turns out that's easy to do. I just put the following into my config file (before the <location> tags):</p>
<!--HTML generated using hilite.me--><div style="background: rgb(248, 248, 248); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: #008800; font-style: italic;"># Enable SSL proxy and ignore local certificate errors</span>
<span style="color: #aa22ff;">SSLProxyEngine</span> <span style="color: #aa22ff; font-weight: bold;">On</span>
<span style="color: #aa22ff;">SSLProxyVerify</span> <span style="color: #aa22ff; font-weight: bold;">none</span>
<span style="color: #aa22ff;">SSLProxyCheckPeerCN</span> <span style="color: #aa22ff; font-weight: bold;">Off</span> # Ignore certificate <span style="color: #aa22ff; font-weight: bold;">error</span>
<span style="color: #aa22ff;">SSLProxyCheckPeerName</span> <span style="color: #aa22ff; font-weight: bold;">off</span>
<span style="color: #aa22ff;">SSLProxyCheckPeerExpire</span> <span style="color: #aa22ff; font-weight: bold;">off</span>
</pre></div>
<!--END HTML generated using hilite.me-->
<p>With that I can set a proxy to https:// instead of http:// and everything else just works.</p><p>What about security? Many of the things I'm proxying already have password protection, but some don't. Fortunately it's easy to add a password inside any <location> field:</p>
<!--HTML generated using hilite.me--><div style="background: rgb(248, 248, 248); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: #008800; font-style: italic;"># Authentication</span>
<span style="color: #aa22ff;">AuthType</span> Basic
<span style="color: #aa22ff;">AuthName</span> <span style="color: #bb4444;">"Password"</span>
<span style="color: #aa22ff;">AuthUserFile</span> <span style="color: green;">/var/www/localhost/accounts/webfrontend</span>
<span style="color: #aa22ff;">require</span> valid-user
</pre></div>
<!--END HTML generated using hilite.me-->
<p>That's just the same as you would do for a <directory> if you weren't doing a proxy. Note that my server only runs on https, or I wouldn't use "basic" authentication.</p><p>Another problem is doing a proxy for something that uses websockets. I hit this with my security camera, and the following does the trick:</p>
<!--HTML generated using hilite.me--><div style="background: rgb(248, 248, 248); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: #008800; font-style: italic;"># See: https://httpd.apache.org/docs/2.4/mod/mod_proxy_wstunnel.html</span>
<span style="color: #aa22ff;">RewriteEngine</span> <span style="color: #aa22ff; font-weight: bold;">on</span>
<span style="color: #aa22ff;">RewriteCond</span> %{HTTP:Upgrade} websocket [NC]
<span style="color: #aa22ff;">RewriteCond</span> %{HTTP:Connection} upgrade [NC]
<span style="color: #aa22ff;">RewriteRule</span> ^/?(.*) <span style="color: #bb4444;">"ws://camera.mydomain.com/$1"</span> [P,L]
</pre></div>
<!--END HTML generated using hilite.me-->
<p>Unfortunately I haven't succeeded in doing a proxy of everything. One device fails to load all the pages even though it appears Apache is modifying all the links correctly. What I have been able to do in that case is have Apache listen on a separate port with a new entry in /etc/apache2/vhosts.d/, and that vhost is a straight proxy for the device without any link rewriting to push it into a subdirectory. If you're having trouble getting something to work with the rewrites, that's a good first step.</p><p>The Apache proxy feature is very powerful. It's great to be able to take all my different devices and put them in a single interface and appear as if they are all on the same server. Unfortunately this can be very complicated in some cases. If developers would avoid absolute links, especially in CSS and JavaScript, it would make proxying much easier. It would also be nice if there were some community database of proxy recipes for devices and web applications. You would think there would be a wiki for this with pages for each device or application that someone had done a proxy for.</p>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-66149077712061575652023-10-30T09:56:00.000-07:002023-10-30T09:56:27.437-07:00Transparent Mode Proxies<p> I have a fairly complicated home network setup, which should come as a surprise to absolutely nobody. I recently dealt with an issue that had been bugging me for ages, but first some background. I want to be able to connect to my home systems from pretty much anywhere, and ssh is the obvious tool for that. Occasionally I've been somewhere where they've blocked outgoing connections to port 22 (the ssh port), but I can instead connect to port 443 (the https port). So if I instead run ssh on port 443, that gets around the problem. But I also want to have a web server on port 443. Fortunately there's this neat little tool called 'sslh' that can sit and listen for connections on a port, and when something connects and sends a message to the server, it determines what protocol the client is using and forwards the connection to the appropriate program. So now I have multiple services running on the one port that should never be blocked.</p><p>But there's a problem.</p><p>The server logs for ssh and apache show the source of the connections as being from the local system, which is technically correct since they are coming from sslh on my local system. I could merge the logs from sslh into the logs for apache and ssh, but that would be a pain. What I really want is to have the original source IP to show up in the logs for the applications as if there wasn't a proxy in the middle.</p><p>Wishful thinking, right? But apparently some really smart people wished for it, so they made it happen.</p><p>There are instructions for how to make this work for sslh, and if you follow them exactly, and if you're lucky, it does work. I say you have to be lucky because there are some subtle issues that you'll hit if you think you're smarter than the instructions or try to do things a little differently. Which is exactly the sort of thing I'm obviously going to do.</p><p>The way sslh works, is it accepts connections, and then sees the first message that the client sends, which it uses to determine what application to forward the connection to. Fortunately network protocols tend to expect the client to send the first message, so for things like ssh, ssl, and http, sslh will know what to do. (However, some protocols like imap have the server send the first message upon establishing a connection, so sslh can only service one such protocol by defaulting to it using a timeout.)</p><p>So my real setup is more complicated than what I described (which should come as no surprise). The issue I hit was with connections using ssl (or really tls as the newer versions have been renamed). If I am going to have multiple services using ssl encryption, then I need to decrypt the incoming connection and then use sslh to multiplex to different applications. This is done by using the program stunnel. And it also has transparent proxy support.</p><p>So an incoming connection comes in on port 443. First sslh gets it and sees what protocol it's using. If it's SSL/TLS, it sends it to stunnel, which then sends it back to sslh, which finally sends it on to apache, ssh, imap, or whatever else I have hidden behind that port.</p><p>Support for transparent proxying is included with both sslh and stunnel, so I'm good, right?</p><p>Nope.</p><p>I can get it working with one of them. I can get it working with sslh going to stunnel and on to apache. But if I have stunnel going to sslh, it breaks badly.</p><p>Why is that?</p><p>Well here's the problem. A quick search brings up instructions on how to make the transparent proxy work, but while they give you the formula, they don't explain how it actually works. And without understanding the reasoning behind the instructions, you're stuck if something goes wrong or if you want to try some creative variation on the same concept.</p><p>So I decided to figure out what's actually happening, and here's the technical meat of my post:</p><p>There are two parts of making this work. The first is the transparent proxy has to send outgoing packets that appear to be from the original host, not from itself. The second is the network layer of the operating system has to know to route the return packets back to the proxy application, even though they'll be addressed to some other system.</p><div style="text-align: left;">To send packets with the original source IP, the transparent proxy has to do two things between creating the socket and connecting to the target. First, it has to enable transparent mode, which requires either running as root or having the cap_net_raw capability. This is done with a line of code like:<br />
<!--HTML generated using hilite.me--><div style="background: rgb(255, 255, 255); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> <span style="color: #333399; font-weight: bold;">int</span> transparent<span style="color: #333333;">=</span><span style="color: #0000dd; font-weight: bold;">1</span>;
res <span style="color: #333333;">=</span> setsockopt(fd, IPPROTO_IP, IP_TRANSPARENT, <span style="color: #333333;">&</span>transparent, <span style="color: #008800; font-weight: bold;">sizeof</span>(transparent));
</pre></div>
<!--END HTML generated using hilite.me-->
<div>And then it has to say where the packet is to appear to originate from:</div>
<!--HTML generated using hilite.me--><div style="background: rgb(255, 255, 255); border-color: gray; border-image: initial; border-style: solid; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;"><pre style="line-height: 125%; margin: 0px;"> getpeername(fd_from, from.ai_addr, <span style="color: #333333;">&</span>from.ai_addrlen);
res <span style="color: #333333;">=</span> bind(fd, from.ai_addr, from.ai_addrlen);
</pre></div>
<!--END HTML generated using hilite.me-->
<div>Normally you only bind a socket to an address like that when listening for incoming connections, but that's how you tell the kernel what address you're sending from in transparent mode.</div><div><br /></div><div>The other part of this is to have the operating system route packets for your application back to you. I won't go into the details here, but there are two approaches I've seen. One is to run your proxy as a specific user, and have a firewall rule that all packets from that user are flagged by the firewall, with firewall rules that have the return packets get sent to a different routing table that tells them to go to the local machine. The other, and the one I prefer, is to connect to a local IP address other than 127.0.0.1, such as 127.255.0.1. Really, anything under 127.x.x.x works besides all zeros or all 255. (I have a separate post about localhost being 127.0.0.1/8 instead of 127.0.0.1/32, giving you a ton of addresses to use for things like this.)</div><div><br /></div><div>Note that the above assumes that the target of the transparent proxy is on the same system. It's probably possible to create firewall rules that will make this work with proxying for a separate internal server, but I haven't explored that, as I haven't needed it yet.</div><div><br /></div><div>Of course, what would be really nice is to just tell the networking layer to check all local bindings before forwarding packets, but there's no option for that. I think that would make a nasty mix of code layers in the routing code, so I can understand why the fancy firewall rules are required.</div><div><br /></div><div><br /></div><div>So now that I understand how it's supposed to work, why didn't it work for me with my complicated setup?</div><div><br /></div><div>The problem was the bind() call. That's not just binding an IP address, it's also binding a port. What does that mean? Every network port is bound to a combination of an IP address and a port. This is done explicitly for any service listening for incoming connections. For outgoing connections, it's done implicitly with the local IP and some high numbered port that is automatically assigned. But in transparent proxy mode, that outgoing connection binding is controlled directly by the program. And if you have multiple layers of transparent proxies, you get into trouble. You simply can't have two connections bound to the same IP address and port. In transparent mode, you're using the original IP and port, so a second hop doesn't work.</div><div><br /></div><div>Except it does if stunnel is the second hop. How does it do this? It gets a bind error, but then retries with a new port. This means the end application sees a different origin port number, but the IP address is right. And in most cases, that port number isn't logged or meaningful, so it doesn't matter. It does break the 'ident' protocol, but I don't think anyone uses that anymore; certainly not for connections from outside a firewall.</div><div><br /></div><div>So to make it work for me, once I understood what was really happening and why it was failing, was to put in the same retry on bind failures in sslh using a new port. And being open source, I sent my patch to the developer of the program, and my patch will be in the next release. That's the power of open source.</div></div>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-19662684239779874902021-11-02T21:11:00.000-07:002021-11-02T21:11:25.403-07:00Don't Use Modular Arithmetic With Negative Numbers<p>Most programmers are familiar with the "modulus" operator, which is the percent symbol in the language C and many other programming languages that have followed. Anyone who remembers learning division in elementary school will recall that when you divide a number, say 21 by a smaller number, say 5, you get a whole number part, 4 in this case, but there's a little left over. Later in arithmetic, you learned to continue the division and get 4.2, but when first learning, you would be told to stop at 4 and say you had a remainder of 1. This concept turns out to be incredibly useful given that computers do a lot of work with integers.</p><p>In C, when working with integer math, you will observe:</p>
<!-- HTML generated using hilite.me --><div style="background: #f8f8f8; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;color:black;"><pre style="margin: 0; line-height: 125%"> <span style="color: #666666">21</span> <span style="color: #666666">/</span> <span style="color: #666666">5</span> <span style="color: #666666">=</span> <span style="color: #666666">4</span>
</pre></div>
<!-- HTML generated using hilite.me --><div style="background: #f8f8f8; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;color:black;"><pre style="margin: 0; line-height: 125%"> <span style="color: #666666">21</span> <span style="color: #666666">%</span> <span style="color: #666666">5</span> <span style="color: #666666">=</span> <span style="color: #666666">1</span>
</pre></div>
<p>When I was a math major in college, we worked with modular arithmetic quite a bit both in my number theory class and in my modern algebra class when working with ring theory. Number theory in particular was a wonderful class for a computer scientist, as it is the mathematical basis for pretty much all integer computing, as well as the basis for cryptography.</p><p>Now in modular arithmetic, as any mathematician knows, if you're working with mod 5, you always end up with numbers from 0 through 4. Here, 4+1 is 0, and 0-1 is 4. You've just taken the number line and wrapped it into a tight circle.</p><p>In computers, this is used in many applications.</p><p>Anything needing random numbers typically calls a function that returns a random unsigned integer from zero to however large the integer is (about four billion for a 32-bit integer). If you're writing code to simulate rolling dice for Dungeons and Dragons, then you'll often want a random number from 1 through 20, so you'll take your huge random number, mod it by 20 to get a number from 0 through 19, and add one.</p><p>Another common data structure is an array. It doesn't matter here what the elements are, they could be simple integers or complex structures. What matters is that the array has a known number of elements, and you reference elements using integer indices of zero through one less than the array length. So if the array has 50 elements, they're 0 through 49. Now sometimes we have an array where we are keeping a history of events, so we save the index of the next event to write, and after writing it, we add one to move to the next element. But to avoid going past the end, we mod the index by the array length to make it wrap around at the end.</p><p>That all works great.</p><p>Now suppose we have a circular array as I described, and we want to read it backwards. We should be able to simply keep subtracting one and taking the result mod the array size so that when we go from zero to negative one it will jump back instead to the end (49 in the above example). But we have two problems here.</p><p>First, often programmers use unsigned integers, especially for array indices. When you subtract 1 from 0 with an unsigned number, it's an integer underflow, which wraps around to be the largest possible integer (that 4 billion-ish number for 32-bit integers). And unless your array size is a power of 2, that modular arithmetic will not work out right. If you think back to how modular arithmetic is like wrapping the number line into a circle, you can see this if you imagine wrapping a 72-inch tape measure into a 5-inch circle. This would work great most of the way, but since you would have that last two inches at the end, moving backwards from zero would be as if the tape connected instantly back to 72, so subtracting one would go to 71, which would be read mod 5 as 1, not 4 like a mathematician would expect.</p><p>Second, even if you're carefully using signed integers for the array indices, the modular operator doesn't follow arithmetic rules as mathematicians would expect. In fact, it's not really a modular operator at all, but really a remainder operator. But those are the same thing, right? Not really. The catch is how the division operator works.</p><p>What is -1/5 in integer arithmetic?</p><p>Is that 0 or -1?</p><p>If it's -1, then you would have a remainder of 4. That's also what you would want from a modular operator, keeping the value always in the 0 through 4 range.</p><p>If it's 0, then you would have a remainder of -1. That's not how modular arithmetic works, as you can't have a negative modular result.</p><p>In C, the answer is 0. And the so-called modular operator will tell you that -1%5 is -1.</p><p>In C, division of negative numbers rounds towards zero instead of negative infinity, which breaks true modular arithmetic.</p><p>Fortunately, it's not hard to work around this problem.</p><p>Say you're moving backwards through a circular array, and what you want to do is:</p>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;color:black;"><pre style="margin: 0; line-height: 125%"> previous_index <span style="color: #333333">=</span> ( current_index <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span> ) <span style="color: #333333">%</span> number_of_elements;
</pre></div>
<p>But since that breaks at zero, just add in the array size:</p>
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;border-width:.1em .1em .1em .8em;padding:.2em .6em;color:black;"><pre style="margin: 0; line-height: 125%"> previous_index <span style="color: #333333">=</span> ( number_of_elements <span style="color: #333333">+</span> current_index <span style="color: #333333">-</span> <span style="color: #0000DD; font-weight: bold">1</span> ) <span style="color: #333333">%</span> number_of_elements;
</pre></div>
<p>That simple change prevents the index from ever going negative, and except when wrapping around below zero, the added array size is just erased by the modular operator.</p>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-52858801364279346292019-07-30T08:48:00.004-07:002019-07-30T08:48:53.303-07:00Merge Conflicts for Non-CodersI was discussing my day at work with my family, and I had spent much of the day resolving conflicts after doing a merge of two divergent branches. Of course, neither my wife nor my son understood what I was talking about, so I came up with a very simple analogy to explain what I was doing.<br />
<br />
Imagine a teacher wrote out a plot outline for a book, and then assigned each student to write one chapter. The student writing chapter 5 decides that the heroes need to use a shovel, so he make a small change in the draft of chapter 3 so that they find a shovel at the beach. Meanwhile the student writing chapter 3 decides she doesn't like the beach scene, so she changes it so that they go for a hike in the woods instead.<br />
<br />
Eventually the students have to put all their work together. The conflicting changes demonstrate two types of conflicts:<br />
<br />
First, in adding in the shovel in chapter 3, the first student made changes to a paragraph that the other student also modified in changing the scene from the beach to the woods. When using an automated merge tool, this sort of conflict is automatically detected, and the person doing the merge is shown the conflict.<br />
<br />
Second, if in resolving the direct conflict, it's possible that the shovel is removed from chapter 3. The merge had been completed, but no automated tools will tell you that the shovel used in chapter 5 now comes out of nowhere. If this were computer code, this would either show up at compile time ("Error: Reference to undefined object "shovel" in chapter 5, paragraph 12."), or worse, would introduce a bug that only shows up when the code runs under certain circumstances. If the book merge left the shovel out, hopefully it would be found by the editor (testing by the quality assurance team for a software project), not left for readers to be confused by (a bug in the field).<br />
<br />
The right analogy can often make it much easier to explain things. If you like this one, or have questions about other aspects of software engineering that you would like me to find similar analogies for, please comment.Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com3tag:blogger.com,1999:blog-5581770500938014748.post-81941562476782302672019-02-25T12:24:00.002-08:002019-02-25T12:24:38.963-08:00Linux With a 4K Laptop DisplayI have a new laptop with a 4K display. This is double the resolution in each direction of a typical laptop, but with the same physical dimensions. That means each pixel takes up a quarter of the space of a single pixel on a traditional display. By default, many things will run using the same number of pixels as on a smaller display, resulting in text too tiny to read.<br />
<br />
Making the problem more complicated, I want to be able to connect my laptop to an external display running at a lower resolution, and be able to disconnect it, walk away, and still have things work on the built-in screen. I also want things look right if I plug in a much larger 4K display. In other words, I want everything to work based on the DPI of the screen, not the pixels.<br />
<br />
The simple solution is to run the display at a lower resolution. This quick-and-dirty hack is good enough for most people, but you lose the crispness of the 4K display, and lose the ability to play 4K video at full resolution (which I may someday care about). It also just feels like the wrong approach.<br />
<br />
So I set my goal to make everything work nicely regardless of whether I'm using an external display or not, and handle changing between external and internal displays on the fly as seamlessly as possible.<br />
<br />
Many people discussing this use the term "HiDPI" for high dots-per-inch displays, so if you're searching for solutions that I don't cover here, that's one term to search on.<br />
<br />
I'm running Gentoo Linux, so some of my comments are going to be specific to that distribution, but for the most part it's simply a matter of finding the different locations for the equivalent files in your distribution.<br />
<br />
Another good resource that I found in researching this is the Arch Linux Wiki page on the same topic: <a href="https://wiki.archlinux.org/index.php/HiDPI">https://wiki.archlinux.org/index.php/HiDPI</a><br />
<br />
<h3>
HiDPI Linux Console</h3>
<br />
First, there are two different things to worry about. Almost everything I've seen online focuses on X, but I also want to have the console working correctly. Here I have three issues to get working correctly:<br />
<br />
<ol>
<li>Setting up the Grub boot menu to look right.</li>
<li>Setting the console font to a reasonable size.</li>
<li>Changing console fonts and resolution when changing displays.</li>
</ol>
<h4>
Grub Boot Menu</h4>
After some searching, I found that I can install fonts for Grub to use. The command I used was:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">mount /boot
<span style="color: darkgoldenrod;">SIZE</span><span style="color: #666666;">=</span>48
grub-mkfont --output<span style="color: #666666;">=</span>/boot/grub/fonts/DejaVuSansMono-<span style="color: #aa22ff; font-weight: bold;">${</span><span style="color: darkgoldenrod;">SIZE</span><span style="color: #aa22ff; font-weight: bold;">}</span>.pf2 <span style="color: #bb6622; font-weight: bold;">\</span>
--size<span style="color: #666666;">=</span><span style="color: #aa22ff; font-weight: bold;">${</span><span style="color: darkgoldenrod;">SIZE</span><span style="color: #aa22ff; font-weight: bold;">}</span> /usr/share/fonts/dejavu/DejaVuSansMono.ttf
umount /boot
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
In Gentoo, you can select the font in /etc/default/grub, so when building the configuration file, it will use the selected font:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: darkgoldenrod;">GRUB_FONT</span><span style="color: #666666;">=</span>/boot/grub/fonts/DejaVuSansMono-48.pf2
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
The only problem with this font and size is the vertical lines have slight gaps. From what I've found, this is a font issue due to using the wrong vertical line character (ASCII vertical bar instead of a unicode vertical line, or the other way around). I would like to figure out what the offending character is and remove it from the character set or swap it with a good one, but I haven't figured out yet which character it's using and which character I want it to use.</div>
<div>
<br /></div>
<div>
Another problem is that while this makes the text perfectly readable on my built-in display, the text is huge if I boot with an external monitor. I looked into rewriting the grub scripts to select the font based on the screen resolution (from the 'videoinfo' command). Normally the grub.cfg is generated dynamically from a script provided as part of the grub installation, but I could write my own or have a post-processing tweak script that added my changes. Unfortunately, the grub scripting language just isn't powerful enough to do this. There is simply no mechanism to have the script behave differently based on the output of a command (like 'videoinfo'). There's no ability to pipe and grep to test for certain output or to put the output of a command into a variable. If there were, I could check the resolution of the active display and select from the installed fonts to get an appropriate size. Of course, if I could do that, I could also parse the output of a directory listing and dynamically generate the menu to select from the installed kernels, eliminating the need to update the grub config every time I install a new kernel.<br />
<br />
So for now, I'm stuck with selecting a single predetermined font for grub regardless of what screen happens to be attached at boot time. I'm sticking with the -48 font, which looks good on the laptop screen even though it is ridiculously huge on my external display, but still has room for my menu options. I submitted a feature request for grub to add dynamic font selection support (<a href="https://savannah.gnu.org/bugs/index.php?51914" target="_blank">bug 51914</a>).<br />
<br />
Also, I've noticed that interactions with grub are very slow. This is <a href="https://savannah.gnu.org/bugs/?46133" target="_blank">bug 46133</a>. It's mostly unrelated to the topic at hand, but the bug only shows up at high screen resolutions, so don't be surprised if you hit it.</div>
<br />
<h4>
Linux Console Font</h4>
For the console, I needed to find a font that looked reasonable. I use a for loop in bash to try every font in /usr/share/consolefonts, and the only one that looked right for me was latarcyrheb-sun32.psfu.gz. As a quick fix, 'setfont -C /dev/tty1 /usr/share/consolefonts/latarcyrheb-sun32.psfu.gz' worked, repeating for each console. That's still a bit small, resulting in a text console of 240x67. (Note: I've now installed the Terminus font, but the largest there is the same size; ter-i32b.psf.)<br />
<br />
For a real solution, I could use the consolefont service on Gentoo, but that still leaves the kernel boot messages too tiny to read. I found a great writeup of a solution for putting a font into the kernel: <a href="https://www.artembutusov.com/modify-linux-kernel-font/">https://www.artembutusov.com/modify-linux-kernel-font/</a> That's the real solution for booting with a good console font. I followed his instructions to install Terminus font as the kernel font, and now all the boot messages are readable.<br />
<br />
Still, I'm limited to a maximum size of a -32 font, which is readable but small on my screen, and I can't make it dynamically select the boot font based on the screen resolution. That's a fundamental limitation in Linux for now.<br />
<br />
For the Linux console, the kernel is stuck with one font as far as I can tell, but I can use the consolefont service to select the font based on the screen resolution. All I need is to set /etc/conf.d/consolefont to check the screen size and then adjust the font if needed. But what I really want is a solution that detects and adjusts the font if I switch between screens.<br />
<div>
<div>
<br /></div>
<div>
Generating a console font from a TrueType font like DejaVu Sans Mono would probably be ideal, as then a script could generate the font for exactly the right size based on the DPI. Everything I've seen online suggests that this is difficult at best. Supposedly fontforge can do this, but I haven't figured out how to use it. The grub-mkfont program shows that it can be done, but that only generates grub fonts, and I haven't found anything that converts out of that format. Some research showed that there was a ttf2bdf program with older versions of Freetype, which has been supplanted by otf2bdf. The page for this is down, but I was able to find an ebuild and the source elsewhere. The output of that can be sent to bdf2psf (a package available in Gentoo). Put this all together, and we have console fonts dynamically sized to the active display. But for some reason the resulting fonts don't work, so something is broken.<br />
<br />
The good news is that the kernel developers are aware of this problem, and one of the features of the 5.0 Linux kernel is a new console font for HiDPI displays. I look forward to trying this, especially seeing if they have a solution for changing monitors.</div>
</div>
<div>
<br /></div>
<h4>
Dynamically Changing Console Resolution</h4>
<div>
<div>
The command: 'fbset -a -xres 1980 -yres 1200' corrects the resolution (provided it's connected to a 1980x1200 monitor). The command 'hwinfo --monitor' will provide information about connected monitors, allowing this to be scripted. Now all that's needed is a trick to activate a script anytime a monitor is added or removed.</div>
<div>
<br /></div>
<div>
To detect video changes, it appears that I can't rely on any system events, which is unfortunate. You would think that connecting or disconnecting a monitor would trigger something like udev, but no such luck. My laptop uses an external USB-C dongle for most video connections, and it would probably work for detecting the connection of the dongle (since that changes the devices), but if the video cable is connected after the dongle is plugged in, that doesn't help. It also doesn't help if I use the built-in HDMI port on the laptop. I want a solution that will always work and isn't dependant on other coinciding changes.</div>
<div>
<br /></div>
<div>
What does work is monitoring changes in /sys. In particular, watch for changes to the directory /sys/class/drm and for changes in any file /sys/class/drm/*/status. Unfortunately, this is a virtual file system, so the kernel only updates the files when someone looks. If something changes in sysfs, but nobody looks, did it really change? No, it didn't. That means you can't use inotify to find out about changes.</div>
</div>
<div>
<br /></div>
<div>
So getting this to work requires a script that actively polls files in /sys to watch for resolution changes.<br />
<br />
Of course, there will be things I will want to tweak in X on monitor changes, too, so those can go in the same script. If requested in the comments, I'll post the script.</div>
<div>
<br />
<h4>
Dynamically Changing Console Fonts</h4>
The same script that changes the console resolution can also change the console fonts. After playing with this, though, I decided it was a better solution to simply leave everything at the -32 font, which is a bit small on the 4K display and a bit big on other displays, but usable everywhere.<br />
<br />
<br /></div>
<div>
<h3>
HiDPI Linux X11 Display</h3>
<div>
Running X Windows on a high DPI display is challenging because there are several different ways that applications adjust. A few settings will cover most applications, but then others either require application-specific settings or simply don't have scaling options. Also, changing DPI on the fly is difficult; most applications will need to be restarted to adjust. We're in the early days of 4K displays right now, so hopefully everything that is still actively maintained will automatically adjust within the next year or two.</div>
</div>
<div>
<br /></div>
<div>
I expect most desktop environments like KDE and Gnome have their own ways of configuring the DPI, just like they do with other configuration options. I don't run a desktop environment, so I'm not going to talk about them. Some of the settings I'll discuss are hopefully adjusted under the covers by your desktop settings, but you can fall back to setting them manually like I do if that doesn't work.</div>
<div>
<br /></div>
<div>
Before setting the DPI, I need a good way of determining what the DPI is. Fortunately, the screen dimensions are reported by the monitor's EDID information, and it's usually accurate. In some cases, the information is wrong, or you'll find that things look better with a different DPI. Until recently, a DPI of 96 was considered typical, so that's what you probably get if you don't adjust anything.</div>
<div>
<div>
<br /></div>
<div>
The command I use to determine the DPI extracts the screen size (in mm) from xrandr and converts it to inches:</div>
<div>
<br /></div>
<div>
<!-- HTML generated using hilite.me -->
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #996633;">DPI</span><span style="color: #333333;">=</span><span style="color: #008800; font-weight: bold;">$(</span>xrandr | egrep <span style="color: darkgoldenrod;">' connected .* [1-9][0-9]*mm x [1-9][0-9]*mm|[*]'</span> | \
sed -e N -e <span style="background-color: #fff0f0;">'s/\n/ /'</span> | \
sed -e <span style="background-color: #fff0f0;">'s/^[^ ]*//'</span> -e <span style="background-color: #fff0f0;">'s/([^)]*)//'</span> -e <span style="background-color: #fff0f0;">'s/^[^0-9]*[^ ]*//'</span> -e <span style="background-color: #fff0f0;">'s/[^0-9]/ /g'</span> | \
awk <span style="background-color: #fff0f0;">'{printf("%g %g\n",$3/($1 * 0.0393701),$4/($2 * 0.0393701))}'</span> | \
awk <span style="background-color: #fff0f0;">'{printf("%d\n",($1+$2+0.5)/2)}'</span> | head -n 1<span style="color: #008800; font-weight: bold;">)</span>
</pre>
</div>
<!-- END HTML generated using hilite.me -->
</div>
</div>
<br />
<h4>
General Settings</h4>
<div>
Ideally we should set some value on the X server, and then your applications will use that value, select the right fonts, and adjust the scaling of everything automatically. The good news is that since most programs use a small number of toolkits like gtk+, qt, and the like, we're in reasonably good shape. The toolkits are DPI-aware, so if you tell them what DPI to use, programs based on them will just work.</div>
<div>
<br /></div>
<div>
Much of the configuration of the X server can now be done dynamically with xrandr. This includes setting the DPI. This is the most important setting, and hopefully everything will move to use this one setting in the future:</div>
<div>
<br /></div>
<div>
<div>
xrandr --dpi ${DPI}</div>
</div>
<div>
<br /></div>
<div>
For GTK, it uses a X resource. In most systems, your ~/.Xresources file is loaded when X starts, but if you want something dynamic, the line to use is:</div>
<div>
<div>
<br /></div>
<div>
xrdb -override <<< "Xft.dpi: ${DPI}"</div>
</div>
<div>
<br /></div>
<div>
That uses a Bash "here string." It's roughly equivalent to:</div>
<div>
<br /></div>
<div>
echo "Xft.dpi: ${DPI}" | xrdb -override</div>
<div>
<br /></div>
<div>
But it doesn't create a subshell.</div>
<div>
<br /></div>
<div>
That takes care of applications like Thunderbird and emacs (for the menus if compiled with gtk).<br />
<br /></div>
<h4>
Cursors / Pointers</h4>
<div>
I've never played with modifying the cursors in X before, so I learned a lot about how they work. There's one cursor that is displayed in the root window, which defaults to a 'x'. This is the only one set by X itself, and you change it with the command xsetroot. All the other cursors are set by the programs you're running (which includes the window manager). Some programs will automatically adjust the cursor that they use based on the DPI settings they use for other scaling. The method used by other applications is to read the information from X resources.</div>
<div>
<br /></div>
<div>
In playing with setting cursors, I found that you can install a bunch of different cursor themes. I installed and tried a bunch, and rather liked the whiteglass theme, which is part of the x11-themes/xcursor-themes package in Gentoo.</div>
<div>
<div>
<div>
<br /></div>
<div>
xrdb -override <<< "Xcursor.theme: whiteglass"</div>
</div>
<div>
xrdb -override <<< "Xcursor.size: $(( DPI / 6 ))"</div>
</div>
<div>
<br /></div>
<div>
For the root window cursor, I picked a cursor from a different theme, but stuck with the default X_cursor. This is set using the full path (which may be different on your system or even with different themes). X sets this cursor as part of its startup before the resources are loaded, so it can't be controlled by the resources.</div>
<div>
<br /></div>
<div>
<div>
xsetroot -xcf /usr/share/cursors/xorg-x11/Adwaita/cursors/X_cursor $(( DPI / 6 ))</div>
</div>
<div>
<br /></div>
<div>
You can change the root cursor anytime you like, but the cursors inside applications, including those set by the window manager, require that you restart your application to pick up the changes. This means restarting your window manager when you change monitors.<br />
<br /></div>
<h4>
Application-Specific Settings</h4>
<div>
<div>
<b>Xterm:</b> I've never worried about fonts in xterm before, but it turns out to be a fairly simple problem to solve. You just select a TrueType font for xterm and set a reasonable point size. Then it will select the font size to be correct for the DPI of the display (as of the time the terminal launches). To make this work, I set two X resources:</div>
<div>
<br /></div>
<div>
XTerm*faceName: Dejavu Sans Mono Bold</div>
<div>
XTerm*faceSize: 8</div>
<div>
<br /></div>
<div>
<b>Chromium:</b> You have to specify a command-line option for a forced scale factor. Hopefully they'll fix this in the future, but you'll still want this if you don't like the default:</div>
<div>
<br /></div>
<div>
--force-device-scale-factor=$(bc <<< "scale=5;${DPI} / 96" )</div>
<div>
<br /></div>
<div>
That's a little on the large size, so use a higher base DPI than 96 if it doesn't look right to you.</div>
<div>
<br /></div>
<div>
<b>VNC viewer:</b> I've been using tightvnc viewer, but it's been pretty much abandoned, and it doesn't have any scaling option. There's a fork of the project, though, that solves this problem: ssvnc. This is mostly a set of wrappers to tunnel VNC though ssl or ssh, but I've been doing that with my own wrappers already, so I'm ignoring that. What's really useful is that ssvncviewer is command-line compatible with TightVNC's vncviewer, and it adds a scaling factor. Since I'm already using a wrapper script for ssh, I just modified it to add a scale of 2 if the DPI is over 200.</div>
<div>
<br /></div>
<div>
ssvncviewer -scale 2 ...</div>
<div>
<br /></div>
<div>
<b>twm:</b> Yes, I'm the last person on Earth still running twm, but the information here might apply elsewhere, too.<br />
<br />
First, your window manager has the job of launching programs, and some of those require special parameters based on the DPI. If you don't want to have to restart your window manager when you switch monitors, the solution is to use wrapper scripts for all of those programs. Second, you'll need some trick to have a dynamic configuration for your window manager. I use twm, but I patched it to use popen() instead of fopen() when reading the configuration file if it finds that it's executable, so my .twmrc is already generated by script. (Perhaps I'll add a blog entry on my hacks of twm.)</div>
<div>
<br /></div>
<div>
It's not surprising that twm doesn't support TTF fonts, so you can't just specify a point size and let it scale (though I've seem some references to patches, so it's not an unreasonable approach; moving to vtwm or another window manager might also make sense). Instead, the fonts are hard-coded in the .twmrc file. Since I already have that file dynamically generated, I can set the fonts based on the DPI. One simpler method would be to have two config files and have a script that detects monitor changes handle setting a symbolic link to the correct one.</div>
<div>
<br /></div>
</div>
<div>
<b>Others:</b> If you find other applications that don't just work, I would suggest finding their bug tracking system and opening a bug. Someday everything should just work.<br />
<br /></div>
<h3>
Future Work</h3>
<div>
What if you have multiple displays at different resolutions? Unfortunately, you can only set one DPI with xrandr or X resources at a time. Every time someone asks about setting per-monitor DPI, the answer seems to be to scale the higher DPI display. Making this work correctly would also require that applications supported changing DPI on the fly, so that they would adjust automatically if dragged to a different screen. For those moving from X to Wayland, apparently it's using per-monitor scaling as its solution, too.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-89969865070595760312017-08-15T10:45:00.001-07:002017-08-15T10:45:15.401-07:00A Subtle Difference between C and C++: String LiteralsFor the most part, C++ is a superset of C. You can write C code, rename the file with a .cpp extension, and the compiler will compile it in C++ mode, generating essentially the same code. In fact, the very first C++ compilers were actually C compilers with extra pre-processing. But there are some subtle differences, and I recently ran into one that has some important implications.<br />
<br />
<h3>
<b>In C, string literals are not constant, but in C++ they are.</b></h3>
<br />
For most practical purposes, string literals are constants in C. The compiler puts them into a data segment that the code can't modify. All the libc string functions take (const char *) parameters. But if you assign a (char *) pointer to the start of a string literal, the compiler won't warn you about dropping the 'const' from the type, and you can write code that modifies the string (only to have it fault at run time). In fact, the warning about dropping the 'const' is probably the reason that newer versions of C haven't changed string literals to be constant.<br />
<br />
Why does anyone care?<br />
<br />
I've found two specific instances where code works when compiled as C++, but not as C because of this.<br />
<br />
<h3>
<b>You can't use string literals as the targets of case statements.</b></h3>
<br />
This may seem obvious, as a case statement takes an integer type, not a string. But suppose you want to do a switch based on the first four characters of a string (after ensuring that it's at least four characters long). Imagine the following macro:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define STR2INT(s) ( ((s[0]) << 24) | ((s[1]) << 16) | ((s[2]) << 8) | (s[3]) )</span>
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
Now you could write code like:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> <span style="color: #aa22ff; font-weight: bold;">switch</span>(STR2INT(option)) {
<span style="color: #aa22ff; font-weight: bold;">case</span> STR2INT(<span style="color: #bb4444;">"help"</span>):
...
<span style="color: #aa22ff; font-weight: bold;">case</span> STR2INT(<span style="color: #bb4444;">"read"</span>):
...
}
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
That works in C++. But in C, the compiler complains that the case statements aren't constant expressions. To make it work in C, you have to have a much uglier version of the macro for the case statements:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define CHARS2INT(w, x, y, z) (((w) << 24) | ((x) << 16) | ((y) << 8) | (z))</span>
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
Then the code looks like:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> <span style="color: #aa22ff; font-weight: bold;">switch</span>(STR2INT(option)) {
<span style="color: #aa22ff; font-weight: bold;">case</span> CHARS2INT(<span style="color: #bb4444;">'h'</span>,<span style="color: #bb4444;">'e'</span>,<span style="color: #bb4444;">'l'</span>,<span style="color: #bb4444;">'p'</span>):
...
<span style="color: #aa22ff; font-weight: bold;">case</span> CHARS2INT(<span style="color: #bb4444;">'r'</span>,<span style="color: #bb4444;">'e'</span>,<span style="color: #bb4444;">'a'</span>,<span style="color: #bb4444;">'d'</span>):
...
}
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
That works in both C and C++, but is a pain to write. At least the STR2INT macro works fine in other situations where the compiler insists on constant values.<br />
<br />
<h3>
<b>You can't write asserts based on macro names.</b></h3>
<br />
In large software projects, it's not unusual to have sets of macros for specific purposes. These macros are by convention supposed to follow some project-specific format. There even may be a defined correlation between the name of the macro and the value. It would be nice to be able to write asserts based on the macro name to enforce those conventions.<br />
<br />
A quick aside on asserts:<br />
<br />
Both C and C++ now support compile-time asserts. It used to be that you would write code that would generate a negative shift if the expression wasn't true or something like that. When the assert failed, you would get a compile-time error that was rather confusing until you looked at the offending line. With the new mechanism, the compiler displays whatever message you tell it. You use static_assert(expression,"message"); In C, you have to include <assert.h> or use _Static_assert. This was added in C11 and C++11.<br />
<br />
So for a trivial example, suppose we have macros like:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define VAL_7B 0x7b</span>
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
Now somewhere we use those macros:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> process_value(VAL_7B);
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
Obviously real code would have other parameters, but this is enough for our purposes.<br />
<br />
To have asserts based on the macro name, what appears to be a function call must also be a macro; presumably a macro wrapper around the real function call. Consider this definition:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define process_value(v) \</span>
<span style="color: #008800;"> do { \</span>
<span style="color: #008800;"> _process_value(v); \</span>
<span style="color: #008800;"> } while(0)</span>
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
That's a basic wrapper, forcing a semicolon at the end of the do-while loop. This lets us add in asserts using the '#' preprocessor operator to stringify the input parameter:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define CHAR2HEX(c) ( (c) <= '9' ? (c) - '0' : (c) - 'A' + 10 ) </span><span style="color: #008800; font-style: italic;">// Assumes uppercase</span>
<span style="color: #008800;">#define process_value(v) \</span>
<span style="color: #008800;"> do { \</span>
<span style="color: #008800;"> static_assert( (#v)[0]=='V' && (#v)[1]=='A' && (#v)[2]=='L' && (#v)[3]=='_', "Must use a 'VAL_xx' macro here" ); \</span>
<span style="color: #008800;"> static_assert( CHAR2HEX((#v)[4]) == ((v)>>4) , "'VAL_xx' macro doesn't match defined value" ); \</span>
<span style="color: #008800;"> static_assert( CHAR2HEX((#v)[5]) == ((v)&0x0f), "'VAL_xx' macro doesn't match defined value" ); \</span>
<span style="color: #008800;"> static_assert( (#v)[06]==0, "'VAL_xx' macro format wrong" ); \</span>
<span style="color: #008800;"> _process_value(v); \</span>
<span style="color: #008800;"> } while(0)</span>
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
In C++, that works great. In C, you just can't do that.<br />
<br />
And here's something interesting: Why not change the above example to look like:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define CHAR2HEX(c) ( (c) <= '9' ? (c) - '0' : (c) - 'A' + 10 ) </span><span style="color: #008800; font-style: italic;">// Assumes uppercase</span>
<span style="color: #008800;">#define process_value(v) \</span>
<span style="color: #008800;"> do { \</span>
<span style="color: #008800;"> static_assert( (#v)[0]=='V' && (#v)[1]=='A' && (#v)[2]=='L' && (#v)[3]=='_', "Must use a 'VAL_xx' macro here" ); \</span>
<span style="color: #008800;"> static_assert( CHAR2HEX((#v)[4]) <= 0xf , "'VAL_xx' macro with bad hex value" ); \</span>
<span style="color: #008800;"> static_assert( CHAR2HEX((#v)[5]) <= 0xf , "'VAL_xx' macro with bad hex value" ); \</span>
<span style="color: #008800;"> static_assert( (#v)[06]==0, "'VAL_xx' macro format wrong" ); \</span>
<span style="color: #008800;"> _process_value( CHAR2HEX((#v)[4])<<4 | CHAR2HEX((#v)[5]) ); \</span>
<span style="color: #008800;"> } while(0)</span>
</pre>
</div>
<br />
<!-- END HTML generated using hilite.me -->
This uses the value directly out of the macro name, so you can leave the value off entirely when defining the macro, right? Yes. But it goes further than that. Since the above code only uses the stringification of the parameter, it never expands it. That means it's perfectly happy if you never define the VAL_XX macros at all, which is probably not what you want. Be sure that the wrapper macro expands the macro somewhere if you want to be sure it's actually a defined macro.<br />
<br />
<h3>
<b>Conclusion</b></h3>
<br />
So if you've followed my other writing up to this point, you're probably expecting some clever hack to make this work in C. Sorry, but not this time. It would probably be relatively simple to add a compiler option or #pragma directive to make string constants literal in C, but gcc doesn't have this, and I'm not aware of any other compiler that does. (Please comment if you know otherwise.) There are plenty of tricks you could do if you're willing to use additional tools in your build process, like an additional step between the regular preprocessor and the compiler to look for extracting characters from string literals and convert them into character constants (and you could tell the compiler to use a wrapper script to do that as the preprocessor), but that's not likely to be an acceptable option.<br />
<br />
You just can't do that in C.<br />
<div>
<br />
<h3>
Resources</h3>
This is the test file I used to be sure my above examples were correct: <a href="https://drive.google.com/open?id=0B5SLVkFB67MpMkFYVGI5cFQzVk0" target="_blank">c_vs_cpp_example.c</a></div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-65303075962701523072017-08-11T13:05:00.002-07:002018-03-19T13:14:18.092-07:00Installing Gentoo Linux on a Dell Precision 5510From time to time I realize just how slow and outdated my computer is. Usually that's long after the corporate policy says I can order a new one, and this time was no different. The engineering laptop is a Dell (no surprise if you know where I work), and the default model is the Precision 5510. New computers always come with Windows installed, so my first task is to install Linux. I figured other people with this or similar models will want to hear about what issues I encountered, so I'm documenting the process here.<br />
<br />
The first thing I did was update the BIOS. There have been some low-level security issues in the press recently, so I figured I should start with the latest base. This was easy: I booted into the installed Windows, logged in, and went go to http://dell.com/support. From there I entered my service tag, clicked on downloads, and selected the BIOS. As I expected, the installed BIOS was a few months older than the latest one. I'm glad I didn't try to install this under Linux, though I assume there is a way to do so. It was a simple process of clicking the obvious choices, and then it rebooted and completed flashing.<br />
<br />
Now the challenges began.<br />
<br />
This is my first laptop without a CD/DVD drive (unless you go back to the floppy days). So to boot Linux, I needed a bootable USB flash. I had followed some very complicated instructions to set up a flash drive, but then found that I had much better results by simply taking the Gentoo live CD and using 'dd if=source_file.iso of=/dev/sdb bs=8192k' to copy it.<br />
<br />
So it should be simple to boot from the flash drive, right? Wrong! Windows set up a "fast boot" where it bypasses most of the BIOS, including the part that watches for holding down F12 for the boot menu. After some searching, I found that you need to enter "control panel" in the Windows search thing that replaces the Start menu (this is my first time to ever run Windows 10). From there I used one of the control panels to disable fast boot. Even with that, it took several tries to get it to recognize the F12 for the boot menu--it checks it very early in the process and moves past it very quickly.<br />
<br />
So I booted the Gentoo USB, and started following the installation guide. I've done this before, so I wasn't expecting too much trouble, but I did have some surprises. First, I wiped the partition table and set it up for Gentoo. I chose to use 1GB VFAT for the EFI partition that is also used as my /boot partition. When everything is good, I'll only mount it to copy over new kernels when updating. Most of the rest of the drive is my root partition, for which I selected ext4. The last 64GB I used as a swap partition, which is excessive, but I hate running out of memory and having the OOM killer sacrifice the one thing I wanted to keep alive.<br />
<br />
At this point, I found that I had no network. This is my first modern laptop without an ethernet port. It came with three different USB-C dongles that I could use, one is just ethernet, one is ethernet, video, and USB, and one is essentially a docking port with lots of ports on it. What I quickly learned is that USB-C isn't like traditional USB. USB-C is the connector, but it can use several different protocols over that connector, including PCI, in which case the marketing name is Thunderbolt. None of that was working in Linux. More on this in a bit...<br />
<br />
So for the time being, I tried copying over stuff using a second flash stick, but that didn't get me very far. I found an old regular USB ethernet dongle, and that worked fine. Once I set up my kernel to boot from EFI, everything should have been mostly good, but of course it wasn't. I had to go back and forth between booting from USB and failing with my kernel. This was a challenge because I couldn't get the F12 menu to come up once I had wiped the Windows partition. I ended up switching back and forth between legacy and EFI booting in the BIOS; legacy for USB and EFI for my attempt at my installed kernel. This probably wasn't necessary, but it worked to get me past the problem. (I needed to go into the BIOS anyway to tell it to boot the grub loader from EFI instead of Windows.)<br />
<br />
Getting the system to boot natively was a huge pain. Part of the problem is that after the boot completes, Gentoo clears the screen for the login prompt, so you lose the boot messages. I decided to fix this by commenting out the getty command for tty1 in /etc/inittab. Now I have to switch consoles to log in, but I can always see the last screenful of the boot. I eventually got my installed kernel to work. It turned out that I had failed to configure tmpfs, and Gentoo fails the boot process miserably if it can't put a tmpfs file system on /run. This is what I get for configuring my own kernels--a bit of pain, but I always learn things.<br />
<br />
So I finally dived into the problem of the Thunderbolt devices simply not working. The main problem was again the BIOS. It was configured with security options for Thunderbolt. This is a good idea--without security, any device plugged into that port can do anything it wants with your computer. But for setting up Linux, it's not a good idea, so I turned off all the security options. I would like to turn them back on at some point, but I'll have to do some research to see if and how Linux handles Thunderbolt security.<br />
<br />
<h4>
Issues</h4>
Now I'm able to get the system up and running for the most part, but I'm still having some issues. I'll document each one here:<br />
<br />
<br />
Issue:<br />
<br />
Switching from X back to a console works, but then moving back to X doesn't<br />
<br />
Solution:<br />
<br />
Need to load firmware as mentioned in https://wiki.gentoo.org/wiki/Intel<br />
Switch acceleration from Sandybridge New Architecture (SNA) to UXA<br />
Setting 'Option "DRI" "False"' works--switching is consistent, though there's an 8-10 second black screen when switching back to X.<br />
<br />
Issue:<br />
<br />
The trackpad works fine in the console as long as you don't want to do a right or middle click. If you're used to using gpm, you can't do cut-and-paste operations or anything else requiring a middle or right mouse button.<br />
<br />
Solutions:<br />
<br />
I have not found any solution to this problem.<br />
<br />
Issue:<br />
<br />
X has no middle-click on the trackpad.<br />
<br />
Solutions:<br />
<br />
You can set the logical location of the middle button to be in the middle of the bottom of the trackpad with the synclient command. Unfortunately, this doesn't help with gpm on the console. I added the following script to my X startup script:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #888888;">#!/bin/bash</span>
<span style="color: #007020;">eval</span> <span style="color: #008800; font-weight: bold;">$(</span>synclient -l | egrep <span style="background-color: #fff0f0;">'(Left|Right)Edge|RightButtonAreaTop|MiddleButtonAreaRight'</span> | sed -e <span style="background-color: #fff0f0;">'s/ //g'</span><span style="color: #008800; font-weight: bold;">)</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">[</span> <span style="background-color: #fff0f0;">"${MiddleButtonAreaRight}"</span> !<span style="color: #333333;">=</span> 0 <span style="color: #333333;">]</span>; <span style="color: #008800; font-weight: bold;">then</span>
<span style="color: #008800; font-weight: bold;"> </span><span style="color: #007020;">echo </span>Middle mouse button already <span style="color: #007020;">set </span>up
<span style="color: #007020;">exit </span>0
<span style="color: #008800; font-weight: bold;">fi</span>
<span style="color: #888888;"># The order here is critical or it will be rejected:</span>
synclient <span style="color: #996633;">RightButtonAreaLeft</span><span style="color: #333333;">=</span><span style="color: #008800; font-weight: bold;">$((</span> RightEdge <span style="color: #333333;">-</span> <span style="color: #333333;">(</span>RightEdge <span style="color: #333333;">-</span> LeftEdge<span style="color: #333333;">)</span> <span style="color: #333333;">/</span> <span style="color: #6600ee; font-weight: bold;">3</span> <span style="color: #333333;">+</span> <span style="color: #6600ee; font-weight: bold;">1</span> <span style="color: #008800; font-weight: bold;">))</span>
synclient <span style="color: #996633;">MiddleButtonAreaRight</span><span style="color: #333333;">=</span><span style="color: #008800; font-weight: bold;">$((</span> RightEdge <span style="color: #333333;">-</span> <span style="color: #333333;">(</span>RightEdge <span style="color: #333333;">-</span> LeftEdge<span style="color: #333333;">)</span> <span style="color: #333333;">/</span> <span style="color: #6600ee; font-weight: bold;">3</span> <span style="color: #008800; font-weight: bold;">))</span>
synclient <span style="color: #996633;">MiddleButtonAreaTop</span><span style="color: #333333;">=</span><span style="color: #008800; font-weight: bold;">${</span><span style="color: #996633;">RightButtonAreaTop</span><span style="color: #008800; font-weight: bold;">}</span>
synclient <span style="color: #996633;">MiddleButtonAreaLeft</span><span style="color: #333333;">=</span><span style="color: #008800; font-weight: bold;">$((</span> LeftEdge <span style="color: #333333;">+</span> <span style="color: #333333;">(</span>RightEdge <span style="color: #333333;">-</span> LeftEdge<span style="color: #333333;">)</span> <span style="color: #333333;">/</span> <span style="color: #6600ee; font-weight: bold;">3</span> <span style="color: #008800; font-weight: bold;">))</span>
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
You can play with that to get the buttons to work however you like. I chose to have three equal buttons, and I didn't play with the other settings, but you can look at the output of 'synclient -l' to see what all you can fiddle with. Do note my comment about the order. You can't have overlapping buttons, so I had to be sure to shrink the right button before defining the middle button (the left button is implicit, so you don't have to adjust it).<br />
<br /></div>
Issue:<br />
<br />
The Thunderbolt devices work fine if they're connected when the system boots. If you unplug and replug them, the system sometimes needs a kick to rescan the PCI bus:<br />
echo 1 > /sys/bus/pci/rescan<br />
Takes care of it usually. However, after several repeated disconnect/connect cycles, the PCI scan fails, and it can't use the device.<br />
<br />
Solution:<br />
<br />
I don't do a lot of disconnecting/reconnecting, so I haven't dug any further into this.<br />
<br />
<h4>
Kernel Config</h4>
Getting the kernel config right for all the devices can be tricky. I'm old fashioned enough that I configure my kernel with support for exactly the devices I use, avoiding modules as much as possible. I'm noting here some of the drivers you'll want to be sure to include:<br />
<br />
<b>Trackpad</b>: From dmesg, I see it's a SynPS/2 Synaptics TouchPad.<br />
<br />
<b>Ethernet</b>: The dock uses a Realtek 8153 USB ethernet chip.<br />
<br />
<b>Sound</b>: The WD-15 dock uses a 0bda:4014 Realtek USB audio device<br />
<br />
<b>Touch Screen</b>: It has an Elan touchscreen. Select the "HID Multitouch panels" driver under "Special HID drivers" in the kernel configuration. It's working, but I haven't tuned it. At some point I may want to investigate, and this looks like a promising guide: https://wiki.archlinux.org/index.php/Calibrating_Touchscreen<br />
<br />
<b>WiFi</b>: It has an Intel 8260 chip, which uses the iwlwifi driver It also requires firmware. I used this guide: https://wiki.gentoo.org/wiki/Iwlwifi<br />
<br />
<b>Bluetooth</b>: It has an Intel 8087:0a2b USB Bluetooth device. I configured it so that the kernel recognizes it and is happy, but I don't have a wireless keyboard or mouse, so I may not use it anytime soon, but I'm thinking about using it for audio. The only catch was that before it would connect to my Amazon Echo, I had to tell it, "Alexa, pair with my phone." A volume control shows up with "alsamixer -D bluealsa." The guide I used is: https://wiki.gentoo.org/wiki/Bluetooth<br />
<br />
<b>Video</b>: It has both Intel and Nvidia graphics, but unlike some laptops, you can't just ignore the Intel and use the Nvidia graphics--you have to access the Nvidia through the Intel GPU. So you can't install the Nvidia drivers without first installing the Intel drivers.<br />
<br />
<b>Flash Reader</b>: It's a Realtek RTS525A PCI device. It requires the kernel to be built with CONFIG_MFD_RTSX_PCI and CONFIG_MMC_REALTEK_PCI. Unlike my old laptop, the card sticks out when inserted, so I can't leave an empty microSD adapter in the laptop.<br />
<br />
<b>WebCam</b>: I haven't looked into using the webcam.Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-58971469800661895192017-06-19T13:08:00.000-07:002017-06-19T13:09:41.193-07:00Go To Statement Considered Helpful (part 5: Fun with Switches)For my final segment on the use of gotos, let us not forget one important hidden goto. The switch statement is essentially a goto with a variable label. This means that the if(0) trick can apply here, too.<br />
<br />
Before I get into the meat, I want to point out that many of the examples in this section aren't great code. In most cases the best way is to find a more traditional solution. Unlike the previous segments I've written on using gotos, this is mostly fun hacking food for thought, not something you're likely to include in your code.<br />
<br />
You're probably vaguely familiar with Duff's Device. Typically you run across it as a loop unrolling technique that a professor mentions in some computer science class, but you then forget about it. Anyway, here's an example. Without Duff's Device, you have a standard loop as below:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">for</span>(i<span style="color: #666666;">=0</span>; i<span style="color: #666666;"><</span>n; <span style="color: #666666;">++</span>i) do_it_once();
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
With Duff's Device, the loop is unrolled manually as below:</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #00bb00; font-weight: bold;">int</span> loops <span style="color: #666666;">=</span> (n <span style="color: #666666;">+</span> <span style="color: #666666;">3</span>) <span style="color: #666666;">/</span> <span style="color: #666666;">4</span>;
<span style="color: #aa22ff; font-weight: bold;">switch</span>(n<span style="color: #666666;">%4</span>) {
<span style="color: #aa22ff; font-weight: bold;">do</span> {
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">0</span>: do_it_once();
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">3</span>: do_it_once();
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">2</span>: do_it_once();
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">1</span>: do_it_once();
} <span style="color: #aa22ff; font-weight: bold;">while</span> ( <span style="color: #666666;">--</span>loops <span style="color: #666666;">></span> <span style="color: #666666;">0</span> );
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
That takes a bit to make sense of. The trick is that first time in, the switch jumps to only do the odd cases, then it hits the do/while loop and goes through all the cases for as many times as is needed. The most common case cited for using that code is writing out a buffer to a register. If you're writing to a serial port or something like that, then that's the right way to do it, but if you're doing something more like a buffer copy, a simpler way that is easier to parse would be to pull the loop outside the switch as in the code below. To keep this example parallel to the Duff's device example, the odd instances are done first, though there's no reason for doing it one way or the other. (In fact, for a buffer copy, you might do odd bytes first and last to optimize for alignment, depending on the needs of the system.)</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">switch</span>(n<span style="color: #666666;">%4</span>){
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">3</span>: do_it_once();
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">2</span>: do_it_once();
<span style="color: #aa22ff; font-weight: bold;">case</span> <span style="color: #666666;">1</span>: do_it_once();
}
<span style="color: #aa22ff; font-weight: bold;">for</span>(i<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>n<span style="color: #666666;">/4</span>;<span style="color: #666666;">++</span>i) do_it_four_times();
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
That's rarely used, but in very specific cases it can be a big win. For example, a memory copy routine may use something very similar to use large registers for the bulk of the data while still supporting odd numbers of bytes. Duff's Device (with the do loop inside the switch statement) has the advantage of eliminating redundant code, especially when the do_it_four_times() call needs to be the same statement four times, and when a larger number is used. If you're working at this level of manual optimization, they key is to try a number of implementations and run performance testing. When combining clever code with optimizing compilers and specific hardware, there are usually more factors than you're taking into account, and you may be surprised at the results.</div>
<div>
<br /></div>
<div>
Now for what I like to call Crow's Corollary to Duff's Device. I sometimes find that I have a series of cases that handle mostly the same thing, but need a slightly different setup. Other cases have completely different code. See the example below.</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">switch</span>(var) {
<span style="color: #aa22ff; font-weight: bold;">case</span> A:
buf_to_use <span style="color: #666666;">=</span> A_BUF;
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> B:
buf_to_use <span style="color: #666666;">=</span> B_BUF;
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> C:
buf_to_use <span style="color: #666666;">=</span> C_BUF;
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> D:
<span style="color: #008800; font-style: italic;">// Completely different code from A, B, C</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
Now imagine that "use_buf()" is 15 or 20 lines of code instead of a simple function. (Yes, I'll accept that the best solution is probably to refactor those 15 to 20 lines into a simple function, but I'm having fun looking at other options.) In order to avoid repeating the code that is the same for the similar cases, you can put the case labels inside an if(0) just like with a goto! Here is the example without the repeated code.</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">switch</span>(var) {
<span style="color: #aa22ff; font-weight: bold;">case</span> A:
buf_to_use <span style="color: #666666;">=</span> A_BUF;
<span style="color: #008800; font-style: italic;">// Fall through but skip over assignment</span>
<span style="color: #aa22ff; font-weight: bold;">if</span> ( <span style="color: #666666;">0</span> ) {
<span style="color: #aa22ff; font-weight: bold;">case</span> B:
buf_to_use <span style="color: #666666;">=</span> B_BUF;
}
<span style="color: #008800; font-style: italic;">// Fall through but skip over assignment</span>
<span style="color: #aa22ff; font-weight: bold;">if</span> ( <span style="color: #666666;">0</span> ) {
<span style="color: #aa22ff; font-weight: bold;">case</span> C:
buf_to_use <span style="color: #666666;">=</span> C_BUF;
}
<span style="color: #008800; font-style: italic;">// General code for cases: A, B, C</span>
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> D:
<span style="color: #008800; font-style: italic;">// Completely different code from A, B, C</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
The importance here is the if(0) construct allows you to avoid duplicating the code that is common to several of the cases without requiring that the initial portion of the cases be identical. This could be implemented with a nested switch statement to set up A, B, and C, but programmers are lazy; I've never seen anyone implement the above example with a nested switch to avoid the use_buf() duplication, even if it's 20 lines of code instead of one. Rarely will someone create a function to factor out the duplicated code. Usually I just see the 20 lines of code duplicated. That's bad. That's what if(0) is there to solve.</div>
<div>
<br /></div>
<div>
Of course, this can be implemented more directly using goto:</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">switch</span>(var) {
<span style="color: #aa22ff; font-weight: bold;">case</span> A:
buf_to_use <span style="color: #666666;">=</span> A_BUF;
<span style="color: #aa22ff; font-weight: bold;">goto</span> use_buf;
<span style="color: #aa22ff; font-weight: bold;">case</span> B:
buf_to_use <span style="color: #666666;">=</span> B_BUF;
<span style="color: #aa22ff; font-weight: bold;">goto</span> use_buf;
<span style="color: #aa22ff; font-weight: bold;">case</span> C:
buf_to_use <span style="color: #666666;">=</span> C_BUF;
<span style="color: #aa22ff; font-weight: bold;">goto</span> use_buf;
<span style="color: #008800; font-style: italic;">// General code for cases: A, B, C</span>
<span style="color: #a0a000;">use_buf:</span>
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> D:
<span style="color: #008800; font-style: italic;">// Completely different code from A, B, C</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
The former version with if(0) blocks interleaved with the case statements is more fun, but it's certainly more confusing and hard to read than simply using a goto. The goto version is also much more friendly to your text editor's auto-indent configuration. (I'm not even sure what "proper" indention is for the interleaved if(0) construct!)</div>
<div>
<br /></div>
<div>
And here's what you would need to write if you were being pedantic about not using gotos:</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">switch</span>(var) {
<span style="color: #aa22ff; font-weight: bold;">case</span> A:
<span style="color: #aa22ff; font-weight: bold;">case</span> B:
<span style="color: #aa22ff; font-weight: bold;">case</span> C:
<span style="color: #aa22ff; font-weight: bold;">switch</span>(var) {
<span style="color: #aa22ff; font-weight: bold;">case</span> A:
buf_to_use <span style="color: #666666;">=</span> A_BUF;
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> B:
buf_to_use <span style="color: #666666;">=</span> B_BUF;
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> C:
buf_to_use <span style="color: #666666;">=</span> C_BUF;
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #a0a000;">default:</span>
flag_error(); <span style="color: #008800; font-style: italic;">// Should be impossible to reach</span>
<span style="color: #aa22ff; font-weight: bold;">break</span>; <span style="color: #008800; font-style: italic;">// avoid warning</span>
}
<span style="color: #008800; font-style: italic;">// General code for cases: A, B, C</span>
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>;
<span style="color: #aa22ff; font-weight: bold;">case</span> D:
<span style="color: #008800; font-style: italic;">// Completely different code from A, B, C</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
That's clunkier to write, harder to read, and more difficult to maintain. If you change the list of cases that use_buf() applies to, you have to modify the case statements in both switch statements, which might as well be begging for bugs. The repeated case statements in the nested switch statement still constitute duplicated code--exactly what we're trying to avoid by factoring out the use_buf() code. Keep your code clean and concise. Use the right tool for the job, and sometimes 'goto' is the right tool.</div>
<div>
<br /></div>
<div>
If you really want to write the same code without a goto or repeated cases, there is a way, but I don't recommend it. You can interleave another loop inside the switch statement so the breaks for the cases break the loop, not the switch. It may be a fun hack, but it's not good code:</div>
</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">switch</span>(var) {
<span style="color: #008800; font-style: italic;">// do loop to change where break goes</span>
<span style="color: #aa22ff; font-weight: bold;">do</span> {
<span style="color: #aa22ff; font-weight: bold;">case</span> A:
buf_to_use <span style="color: #666666;">=</span> A_BUF;
<span style="color: #aa22ff; font-weight: bold;">break</span>; <span style="color: #008800; font-style: italic;">// exits do loop, not switch</span>
<span style="color: #aa22ff; font-weight: bold;">case</span> B:
buf_to_use <span style="color: #666666;">=</span> B_BUF;
<span style="color: #aa22ff; font-weight: bold;">break</span>; <span style="color: #008800; font-style: italic;">// exits do loop, not switch</span>
<span style="color: #aa22ff; font-weight: bold;">case</span> C:
buf_to_use <span style="color: #666666;">=</span> C_BUF;
<span style="color: #aa22ff; font-weight: bold;">break</span>; <span style="color: #008800; font-style: italic;">// exits do loop, not switch</span>
} <span style="color: #aa22ff; font-weight: bold;">while</span> (<span style="color: #666666;">0</span>);
<span style="color: #008800; font-style: italic;">// General code for cases: A, B, C</span>
use_buf(buf_to_use);
<span style="color: #aa22ff; font-weight: bold;">break</span>; <span style="color: #008800; font-style: italic;">// regular switch exit</span>
<span style="color: #aa22ff; font-weight: bold;">case</span> D:
<span style="color: #008800; font-style: italic;">// Completely different code from A, B, C</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
<div>
This is the closest corollary to Duff's Device, but again, don't do that. The above example should be viewed by the compiler as being identical to the goto version. Most C programmers aren't used to mixing up switch statements with other control structures like that, which also makes it harder to understand. Unless you have some arbitrary "no gotos" rule handed down from management, the goto version is the simplest to read and understand. Use the gotos.</div>
</div>
<div>
<br /></div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-56206949413739654032017-06-19T12:58:00.002-07:002017-06-19T13:09:37.767-07:00Go To Statement Considered Helpful (part 4: Tail Recursion)One other place where goto can be useful is in implementing tail recursion. As you should recall, tail recursion is when a function returns with a call to itself. For example:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">foo(<span style="color: #00bb00; font-weight: bold;">int</span> a)
{
...
<span style="color: #aa22ff; font-weight: bold;">if</span> ( recurse )
{
<span style="color: #aa22ff; font-weight: bold;">return</span>(foo(a<span style="color: #666666;">+1</span>)); <span style="color: #008800; font-style: italic;">// tail recursion</span>
}
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
Most compilers will optimize that into a goto to the top of the function. However, in some cases the compiler will fail you, and you have a runtime fault when the stack overflows. Perhaps you turned off optimization to aid in debugging. Perhaps the compiler isn't as smart as it should be. Who knows? If you're running with a limited stack (and stacks are always limited), don't trust your compiler. Replace the recursion with a goto as below:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">foo(<span style="color: #00bb00; font-weight: bold;">int</span> a)
{
<span style="color: #a0a000;">tail_recursion:</span>
...
<span style="color: #aa22ff; font-weight: bold;">if</span> ( recurse )
{
a<span style="color: #666666;">=</span>a<span style="color: #666666;">+1</span>;
<span style="color: #aa22ff; font-weight: bold;">goto</span> tail_recursion; <span style="color: #008800; font-style: italic;">// return(foo(a)) without recursion</span>
}
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
Now you won't blow away your stack if the optimization settings change.<br />
<br />
Of course, you can implement that by putting the body of the function inside a while(1){...; break;} loop, and then replace the goto with a continue. However, doing that is just as much of a hack as a goto. It also adds an unnecessary indention level, and it is definitely harder to read than the simple goto.<br />
<br />
Unlike the previous examples, I'm not hiding the goto here in a macro. I am using a label name that should tell any experienced programmer what I'm doing. If I were to hide this in a macro, it would be less clear what's going on.<br />
<br />
Now you might object that previously I've said to trust the compiler to optimize your code and don't worry about whether it looks like you're adding a few extra instructions. I still stand by that, but this isn't a matter of trusting optimization for a few instructions. This is a matter of your program not crashing. I ran into this exact situation in real code. When the correctness of your code requires optimization, you need to force the code to always be optimized, which is exactly why we need the goto in this case.Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-78417816024853885412017-06-19T12:50:00.000-07:002017-06-19T13:09:33.053-07:00Go To Statement Considered Helpful (part 3: Finding Matches in a Loop)Another time I often find use for a goto is in a for loop that is scanning an array to find a match. If a match is found, a break terminates the loop. See the standard version of this below. It repeats the condition check for the loop to see if the loop terminated early. The other option would be to use a flag to indicate if a match was found. This requires initializing the variable and then setting it if a match is found. Both of these variations are very common.<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">for</span> (i<span style="color: #666666;">=0</span>; i<span style="color: #666666;"><</span>ARRAY_SIZE(data); <span style="color: #666666;">++</span>i)
{
<span style="color: #aa22ff; font-weight: bold;">if</span> ( data[i].key <span style="color: #666666;">==</span> value ) <span style="color: #aa22ff; font-weight: bold;">break</span>;
}
<span style="color: #aa22ff; font-weight: bold;">if</span> ( i<span style="color: #666666;"><</span>ARRAY_SIZE(data) )
{
<span style="color: #008800; font-style: italic;">// data[i].key is our match</span>
<span style="color: #a0a000;">match_found:</span>
...
}
<span style="color: #aa22ff; font-weight: bold;">else</span>
{
<span style="color: #008800; font-style: italic;">// No match was found</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
I hate repeating code; that's a source of bugs, as years later someone might need to make a change and only change one of the two copies. Adding a tracking variable is clunky. Again, goto can save the day. Consider the code below:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">for</span> (i<span style="color: #666666;">=0</span>; i<span style="color: #666666;"><</span>ARRAY_SIZE(data); <span style="color: #666666;">++</span>i)
{
<span style="color: #aa22ff; font-weight: bold;">if</span> ( data[i].key <span style="color: #666666;">==</span> value ) <span style="color: #aa22ff; font-weight: bold;">goto</span> match_found;
}
<span style="color: #aa22ff; font-weight: bold;">if</span> ( <span style="color: #666666;">0</span> )
{
<span style="color: #008800; font-style: italic;">// data[i].key is our match</span>
<span style="color: #a0a000;">match_found:</span>
...
}
<span style="color: #aa22ff; font-weight: bold;">else</span>
{
<span style="color: #008800; font-style: italic;">// No match was found</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
This eliminates the repeated comparison, so if something changes, it only has to change once. A quick reaction that many will have is that this also will be faster than the alternative, but generally compilers are very good at eliminating redundant comparisons, and processors are fast enough that it's rarely worth worrying about saving a few machine instructions; in fact, it's usually best to be willing to sacrifice machine instructions for better code.<br />
<br />
Without the goto, you can't scope the loop index to be just the loop, or you end up using an extra boolean tracking variable. Most importantly, without the goto, the code is longer and more complicated, and that's exactly what you don't want. Of course, in most cases, you'll still need the loop index to know which item matched, but sometimes you only need to know if there was a match.<br />
<br />
Once again, the C preprocessor comes to the rescue with a clever pair of macros below:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define EXIT_LOOP_WITH_MATCH(name) goto _loop_match_ ## _name;</span>
<span style="color: #008800;">#define IF_LOOP_EXITED_WITH_MATCH(_name) if(0) _loop_match_ ## _name:</span>
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
The macro works just like a regular if statement. You can use it with or without braces, and you can use a regular else condition. The only catch is that the compiler will likely complain about an unused label if you have the IF macro without a matching EXIT macro. That may well be more of a benefit than a restriction.<br />
<br />
With the macro, our previous example is nice and clean as seen below:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #aa22ff; font-weight: bold;">for</span> (i<span style="color: #666666;">=0</span>; i<span style="color: #666666;"><</span>ARRAY_SIZE(data); <span style="color: #666666;">++</span>i)
{
<span style="color: #aa22ff; font-weight: bold;">if</span> ( data[i].key <span style="color: #666666;">==</span> value ) EXIT_LOOP_WITH_MATCH(my_loop);
}
IF_LOOP_EXITED_WITH_MATCH(my_loop)
{
<span style="color: #008800; font-style: italic;">// data[i].key is our match</span>
...
}
<span style="color: #aa22ff; font-weight: bold;">else</span>
{
<span style="color: #008800; font-style: italic;">// No match was found</span>
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
Those macros may look familiar. They should. They're exactly the same as the THROW and CATCH macros I discussed previously for exception handling in C.<br />
<br />
It is interesting to note that this and the previous example for the use of goto (breaking out of a nested loop and avoiding extra code to handle exiting a loop early) are exactly the two cases cited in Kernighan and Ritchie's <i>The C Programming Language</i> book when it discusses the goto statement in section 3.8.<br />
<br />Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-26470426574857255982017-06-19T12:00:00.000-07:002017-06-19T13:16:00.470-07:00Go To Statement Considered Helpful (part 2: Nested Loops)<div>
If you're in a nested loop in C code, and you want to issue a break or continue statement, but want it to apply to the outer loop, you're going to have some awkward code.</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> <span style="color: #aa22ff; font-weight: bold;">for</span>(j<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>j_end;<span style="color: #666666;">++</span>j)
{
<span style="color: #aa22ff; font-weight: bold;">for</span>(i<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>end;<span style="color: #666666;">++</span>i)
{
...
<span style="color: #aa22ff; font-weight: bold;">if</span> (condition) next_j; <span style="color: #008800; font-style: italic;">// break then continue?</span>
...
}
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
Implementing that 'next_j' statement could be done with setting a flag, issuing a break, and then checking the flag after the inner loop terminates. What we want is a "goto continue_outer_loop." And when you do this, it can be a perfect place for one of my favorite tricks, the use of "if (0)" for live code. At the end of the outer loop, put in the block of code, "if (0) { continue_outer_loop: continue; }" and you can then use your goto to implement the feature that the language is missing. This looks like:</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> <span style="color: #aa22ff; font-weight: bold;">for</span>(j<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>j_end;<span style="color: #666666;">++</span>j)
{
<span style="color: #aa22ff; font-weight: bold;">for</span>(i<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>end;<span style="color: #666666;">++</span>i)
{
...
<span style="color: #aa22ff; font-weight: bold;">if</span> (condition) <span style="color: #aa22ff; font-weight: bold;">goto</span> continue_outter_loop;
...
}
...
<span style="color: #aa22ff; font-weight: bold;">if</span>(<span style="color: #666666;">0</span>) continue_outter_loop<span style="color: #666666;">:</span> <span style="color: #aa22ff; font-weight: bold;">continue</span>;
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
A nice thing to do would be to imagine how the language might be extended to eliminate this need for a goto. Loops could easily be named, allowing the name of the loop to be an optional parameter to a break or continue statement. What if instead of for(i=0;i<10;++i), you could write for(i=0;i<10;++i;index_loop). Then you could use "break index_loop;" inside an inner loop with no need for a goto. Good luck getting the language committees to agree to this anytime soon. On the bright side, Java recognized this shortcoming, so the language provides for named loops; in C and C++, goto lets you implement the missing feature.</div>
<div>
<br /></div>
<div>
In this case, all this can be included in macros, as shown below. The first pass at trying this can result in compiler warnings about unused labels, which is why I added the extra do-nothing gotos. With even the most minimal compiler optimizations, this should provide exactly the same execution as if the language provided for named loops natively. The only restriction is that you can't use the same name for more than one loop in the same function.</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-style: italic;">/*</span>
<span style="color: #008800; font-style: italic;"> * Named loops:</span>
<span style="color: #008800; font-style: italic;"> *</span>
<span style="color: #008800; font-style: italic;"> * Name any loop, typically the first thing after the opening brace.</span>
<span style="color: #008800; font-style: italic;"> * Then in a nested loop, break or continue from it with</span>
<span style="color: #008800; font-style: italic;"> * BREAK_LOOP/CONTINUE_LOOP.</span>
<span style="color: #008800; font-style: italic;"> *</span>
<span style="color: #008800; font-style: italic;"> * Code Copyright 2015 by Preston Crow</span>
<span style="color: #008800; font-style: italic;"> * used by permission</span>
<span style="color: #008800; font-style: italic;"> * (You have permission to use this as long as you keep</span>
<span style="color: #008800; font-style: italic;"> * this comment block intact.)</span>
<span style="color: #008800; font-style: italic;"> */</span>
<span style="color: #008800;">#define NAME_THIS_LOOP(_name) \</span>
<span style="color: #008800;">if(0) \</span>
<span style="color: #008800;">{ \</span>
<span style="color: #008800;"> goto _continue_loop_ ## _name; \</span>
<span style="color: #008800;"> _continue_loop_ ## _name : continue; \</span>
<span style="color: #008800;">} \</span>
<span style="color: #008800;">if(0) \</span>
<span style="color: #008800;">{ \</span>
<span style="color: #008800;"> goto _break_loop_ ## _name; \</span>
<span style="color: #008800;"> _break_loop_ ## _name : break; \</span>
<span style="color: #008800;">} \</span>
<span style="color: #008800;">do { ; } while (0) </span><span style="color: #008800; font-style: italic;">/* Force a semicolon */</span><span style="color: #008800;"></span>
<span style="color: #008800;">#define CONTINUE_LOOP(_name) goto _continue_loop_ ## _name</span>
<span style="color: #008800;">#define BREAK_LOOP(_name) goto _break_loop_ ## _name</span>
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
Note that the naming macro can go anywhere in the loop where a continue or break statement would work as expected. Using those macros, the code is quite readable:</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> <span style="color: #aa22ff; font-weight: bold;">for</span>(j<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>j_end;<span style="color: #666666;">++</span>j)
{
NAME_THIS_LOOP(outter_loop)
<span style="color: #aa22ff; font-weight: bold;">for</span>(i<span style="color: #666666;">=0</span>;i<span style="color: #666666;"><</span>end;<span style="color: #666666;">++</span>i)
{
...
<span style="color: #aa22ff; font-weight: bold;">if</span> (condition) CONTINUE_LOOP(outter_loop);
...
}
...
}
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
<div>
<br /></div>
<div>
I thought I was very clever the day I came up with that. I felt a little less clever when researching revealed that others have also suggested very similar macros for the same purpose. In any case, I highly recommend that you use these macros or the like in all C and C++ projects where appropriate.</div>
<div>
<br /></div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-88837224920194375242017-06-19T11:00:00.000-07:002017-06-19T13:15:37.668-07:00Go To Statement Considered Helpful (part 1: Exceptions)The most obvious use of a goto statement in C is for exception handling. Many people before have noted that this is one good use of gotos.<br />
<br />
It's not unusual to have a function with a number of checks for errors. When an error is encountered, the function must release locks and free memory acquired and allocated at the start of the function before returning an error to the caller. The simple way to do this is to have all the errors jump to a label near the end of the function where this is done. Often this is the same code that a successful exit from the function also executes. This is certainly better than repeating the same code many different times in the same function. Newer languages have recognized this and implemented this functionality in the language. In C++, you can use throw/catch. In Java, there is also the try/finally construct that can also handle many of these situations.<br />
<br />
In C, to handle exceptions, you will often see code with a goto as below:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"> buf<span style="color: #666666;">=</span>malloc(size);
<span style="color: #aa22ff; font-weight: bold;">if</span> ( <span style="color: #666666;">!</span>buf ) <span style="color: #aa22ff; font-weight: bold;">goto</span> error_exit;
...
<span style="color: #a0a000;">error_exit:</span>
printf(<span style="color: #bb4444;">"Out of memory</span><span style="color: #bb6622; font-weight: bold;">\n</span><span style="color: #bb4444;">"</span>);
...
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
This code is typical enough that many coders are happy with it like that. But what if we could implement exception handling like C++ in C using macros? Well, we can. Two language tricks make this possible. First, you can use "if (0)" to create code that can only be reached by a goto. Second, the target of an if statement can be a labeled statement or block. I'll get back to that in a bit. Here are the macros:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800;">#define THROW(_name) goto handle_exception_ ## _name;</span>
<span style="color: #008800;">#define CATCH(_name) if(0) handle_exception_ ## _name:</span>
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
Now there's no need to complain that C lacks exception handling. This works much like the C++ version, but without the parameter. Also, they are scoped for the whole function, as they aren't connected to a “try{...}” block of statements. See the example below:<br />
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #f8f8f8; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">buf<span style="color: #666666;">=</span>malloc(size);
<span style="color: #aa22ff; font-weight: bold;">if</span> ( <span style="color: #666666;">!</span>buf ) THROW(out_of_memory);
...
CATCH(out_of_memory) {
printf(<span style="color: #bb4444;">"Out of memory</span><span style="color: #bb6622; font-weight: bold;">\n</span><span style="color: #bb4444;">"</span>);
}
<span style="color: #aa22ff; font-weight: bold;">if</span> (buf) free(buf);
<span style="color: #aa22ff; font-weight: bold;">return</span>;
</pre>
</div>
<!-- END HTML generated using hilite.me -->
<br />
Wait a second. What's going on with those macros? That's some crazy code that can't be right.<br />
<br />
The first trick is to protect the target of the goto in the target of an if(0) statement. That means the target of the goto is in code that can't be reached without the goto. This trick reduces some of the spaghetti code issues normally associated with goto statements.<br />
<br />
<span style="line-height: 16px;">But what about that label after the if(0)?</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">Well, I'm taking advantage of a surprising glitch in the C language definition. When I first wrote the code, I was thinking that what I needed for my macro was to be able to write: if(0) label: { statements; } but putting the label in there certainly wouldn't be allowed. Much to my surprise, it compiled and worked! I went back and checked the language definition, and found that it is, in fact, legal code. I can't believe they intended this when defining the language, but as a lucky artifact of how they set up the parsing, it is how they defined it. (Perhaps it was because case statements in a switch work just like labels. The reason isn't particularly important here.) This allows you to macro-ize the CATCH without having any ugliness with the target and braces. You can follow the CATCH macro with a block of statements, a single statement, or just a semicolon to follow the same code that follows.</span><br />
<span style="line-height: 16px;"><br /></span>
<ait a="" an="" associated="" be="" can="" code="" crazy="" div="" first="" going="" goto.="" goto="" hat="" his="" if="" in="" is="" issues="" macros="" means="" nbsp="" normally="" of="" on="" protect="" reached="" reduces="" right.="" s="" second.="" some="" spaghetti="" statement.="" statements.="" style="line-height: 16px; margin-bottom: 0.08in; margin-top: 0.08in;" t="" target="" that="" the="" those="" to="" trick="" with="" without="">By hiding all this in the macro, I've effectively extended the C language to add a missing feature.</ait><br />
<style type="text/css">
@page { margin: 0.79in }
p { margin-bottom: 0.1in; line-height: 120% }
a:link { so-language: zxx }
</style>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-46956606494556243902017-06-19T10:00:00.000-07:002017-06-19T13:15:12.582-07:00Go To Statement Considered Harmful (revisited)<div style="margin-bottom: 0in;">
<span style="line-height: 16px;">Hopefully you've heard of the famous letter by Edsger Dykstra, "Go To Statement Considered Harmful." This was one of the most influential letters ever written in Computer Science, published in <i>Communications of the ACM</i> in March, 1968. This letter effectively defined structured programming for generations of coders. It has been taken as gospel and taught in so many programming classes that most developers take it for granted. The goto statement is just too low-level for modern programming.</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">This has been taken so far that some languages simply didn't include goto in the language. Java is a prime example. Though in that case, they were hedging their bets, as they kept a reserved word for it, and they did include it in the bytecode.</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">The letter itself is rather dry and academic. You can find it online, and it's worth the read. (I found it at https://www.cs.utexas.edu/~EWD/transcriptions/EWD02xx/EWD215.html under the original title; it was the ACM editor that selected the now-famous "harmful" title.) It has good points. In general, the use of goto results in spaghetti code that is hard to debug and harder to maintain. Clean code breaks things into functions, loops, and other well-defined control structures, with little obvious need for direct jumps.</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">I first heard of this when my world of programming consisted of Atari BASIC. The idea of not using goto was rather shocking in that context, but then most BASIC implementations of the day lacked functions, while loops, and a number of other higher-level structures that even shell scripts have today. When I moved on to Pascal and C, there seemed to be little use for the old goto, and I readily accepted the idea that it was a bad idea.</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">But the idea of avoiding direct jumps has been treated as a religious dogma instead of as a general guideline, and this has been harmful itself. There are many reasons why using an explicit goto is a good idea. In fact, no matter how nicely structured your code is, it's impossible to avoid that pesky goto. How do you think all those nice loops are implemented? At the assembly level, it's all comparisons and jumps.</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">Now you can say that that's just a technical nitpick, and you're mostly correct. Dykstra even referenced it in his original letter. Just because the good structured statements your language provides are implemented with jumps doesn't mean you should use them directly. However, what it does do is give a good consistent reason for when you should use gotos in your code.</span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;"><b>Use a goto only when you need to implement something that your language doesn't provide for.</b></span><br />
<span style="line-height: 16px;"><br /></span>
<span style="line-height: 16px;">Following this, I've written a series of examples where a goto statement provides some useful and interesting features for C programmers.</span><br />
<br />
<ul>
<li><a href="http://madcompiler.blogspot.com/2017/06/go-to-statement-considered-helpful-part.html">Go To Statement Considered Helpful (part 1: Exceptions)</a></li>
<li><a href="http://madcompiler.blogspot.com/2017/06/go-to-statement-considered-helpful-part_19.html">Go To Statement Considered Helpful (part 2: Nested Loops)</a></li>
<li><a href="http://madcompiler.blogspot.com/2017/06/go-to-statement-considered-helpful-part_57.html">Go To Statement Considered Helpful (part 3: Finding Matches in a Loop)</a></li>
<li><a href="http://madcompiler.blogspot.com/2017/06/go-to-statement-considered-helpful-part_2.html">Go To Statement Considered Helpful (part 4: Tail Recursion)</a></li>
<li><a href="http://madcompiler.blogspot.com/2017/06/go-to-statement-considered-helpful-part_61.html">Go To Statement Considered Helpful (part 5: Fun with Switches)</a></li>
</ul>
</div>
<style type="text/css">
@page { margin: 0.79in }
p { margin-bottom: 0.1in; line-height: 120% }
a:link { so-language: zxx }
</style>Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-23396359099537098062017-05-25T07:17:00.004-07:002023-10-30T09:26:22.821-07:00Nice Code Blocks in BloggerThis post is mostly for my own use, but I figure some others might like it, too. You may have noticed that I have some nice code blocks in some of my posts. I may start with something like:<br />
<br />
<span style="font-family: "courier new" , "courier" , monospace;">function(args)</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">{</span><br />
<span style="font-family: "courier new" , "courier" , monospace;"> if ( maybe ) do_something();</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">}</span><br />
<br />
(I set the font to offset the above code using the font-selector make it stand out a bit.)<br />
<br />
How to I get those nice looking blocks?<br />
<br />
To start, I use a site to format the blocks:<br />
<br />
<a href="http://hilite.me/">http://hilite.me/</a><br />
<br />
That generates HTML that I can paste into my post. When editing, normally you're in "compose" mode, but near the top left, you can hit "HTML" to get into the raw code of the page. I just paste the results from the web page. Make sure you don't put it in the middle of a <div></div> pair. I often put a lone line of text where I want to paste into the page to make it easy to find. Something like this:<br />
<br />
==========PASTE_CODE_BLOCK_HERE==========<br />
<br />
So doing that, now I have this:<br />
<!--HTML generated using hilite.me--><br />
<div style="background: rgb(255, 255, 255); border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0px;">function(args)
{
<span style="background-color: #ffaaaa; color: red;"> </span> <span style="background-color: #ffaaaa; color: red;"> </span> <span style="color: #008800; font-weight: bold;">if</span> ( maybe ) do_something();
}
</pre>
</div>
<br />
After that, I hit "preview." There I'll see that with a white background, I see lots of off-white text on white. Not good. (This is because my normal page style is light text on dark, and the highlighter page assumes you have dark text on light and doesn't override it.) At the top of the HTML block I paste in, there are some HTML style options separated by semicolons. I need to add in, "color:black;" to correct the color issue:
<!--HTML generated using hilite.me--><br />
<br />
<div style="background: rgb(255, 255, 255); border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0px;">function(args)
{
<span style="background-color: #ffaaaa; color: red;"> </span> <span style="background-color: #ffaaaa; color: red;"> </span> <span style="color: #008800; font-weight: bold;">if</span> ( maybe ) do_something();
}
</pre>
</div>
<br />
That's nice, but I don't like that it highlights spaces. This is a simple matter of removing the "<span ...> </span>" tags around the spaces. But wait, there's a reason those are there: it's based on where I'm pasting from. If I'm pasting from a web page with formatting, some of that is getting picked up by the highlighter. As a general rule, never paste into Blogger from a web page or formatted document--it will mess up all sorts of things. I have to make sure I'm posting raw ASCII text if I want a nice clean block of code. So going back to the original code, pasting it first into a text editor, and then into the highlighter, and editing the default text color:<br />
<!--HTML generated using hilite.me--><br />
<div style="background: rgb(255, 255, 255); border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0px;">function(args)
{
<span style="color: #008800; font-weight: bold;">if</span> ( maybe ) do_something();
}
</pre>
</div>
<br />
So there's just one change, but to be sure I remember it and to make it easy, I'll save a one-line command line for fixing things. I toss in stripping out stray blank lines. Since I want to buffer all the input before printing the output, I'll pipe the output to a tail command. I then add a final comment line and a blank line to keep things easier to follow when editing the page:<br />
<!-- HTML generated using hilite.me --><div style="background: #ffffff; overflow:auto;width:auto;border:solid gray;color:black;border-width:.1em .1em .1em .8em;padding:.2em .6em;"><pre style="margin: 0; line-height: 125%">sed -e <span style="background-color: #fff0f0">'s/border: *solid gray/&;color:black/'</span> <span style="color: #666666; font-weight: bold; background-color: #fff0f0">\</span>
-e <span style="background-color: #fff0f0">'s@<span[^>]*> </span>@ @g'</span>|
grep -v <span style="background-color: #fff0f0">'^$'</span> |
tail -n 10000 ; <span style="color: #666666; font-weight: bold; background-color: #fff0f0">\</span>
<span style="color: #007020">echo</span> <span style="background-color: #fff0f0">'<!-- END HTML generated using hilite.me -->'</span>; <span style="color: #666666; font-weight: bold; background-color: #fff0f0">\</span>
<span style="color: #007020">echo</span> <span style="background-color: #fff0f0">''</span>
</pre></div>
<!-- END HTML generated using hilite.me -->
<br />
One simple hint: You're free to leave blank lines in the HTML version of the page outside of the block generated by the web page. This may make it simpler to find and update the blocks as needed, but Blogger sometimes removes them. In any case, they're harmless.<br />
<br />
Another thing to watch for is that the Blogger composer sometimes gets confused as to the line breaks around code blocks. Always check the preview--there are often line breaks where the composer doesn't show them between your text and the code block.<br />
<br />
For this post I used the "colorful" style. I think I'll use "emacs" in most of my posts. Somehow that color scheme looks natural to me.Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-71270703429075979532017-05-04T07:35:00.003-07:002017-05-04T07:35:49.715-07:00Digital Rights Management (DRM) and Star WarsMany of my friends have heard me complain (OK, rant) about DRM. DRM officially stands for "digital rights management," but I prefer "digital restrictions management." The most common use of DRM is for video like Blu Ray discs and Netflix. DRM software enforces the restrictions imposed by the seller. You only get to use the media in the way they intended, no matter how much money you spent to buy it. You don't fully own that disc you just bought. Want to skip the previews? Sorry. Want to skip the copyright notice? No way.<div>
<br /></div>
<div>
Of course, DRM doesn't stop the professional copiers. People in various countries will take one legal disc and press duplicates that are completely identical, bypassing all the copy protections. DRM value: zero. Semi-professional pirates find various ways of bypassing the protection, including ripping from the HDMI output with hacks to remove the copy protection there, and then they share the videos online. DRM value: none. Regular owners who want to copy the movie to their iPad to watch in the car can't. Yes, some discs offer alternatives that may or may not work offline. DRM value: consumers annoyed.</div>
<div>
<br /></div>
<div>
But let's look at the worst impact of DRM ever: Star Wars.</div>
<div>
<br /></div>
<div>
In particular, have you ever wondered why Princess Leia had to send the Death Star plans with R2D2 instead of transmitting them to another ship? Or why they never made copies and sent them with multiple courriers? Clearly the plans were encumbered with the nastiest DRM ever invented. Want to copy them? No way. Want to transmit them without destroying the original? Nope, not allowed. Want to analyze them to find a design flaw allowing you to destroy the Death Star using small fighters too small to be considered a serious threat? No problem, but only if you watch the Imperial Secret Documents crawl first.</div>
<div>
<br /></div>
<div>
So remember, DRM isn't just about stopping those nasty consumers from watching movies they've legitimately purchased on multiple devices. DRM is also about preserving the Empire. Support DRM to help destroy the last vestiges of the Republic.</div>
<div>
<br /></div>
<div>
Happy Star Wars Day. May the Fourth be with you.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-12532787765011124842016-07-06T18:07:00.000-07:002017-05-24T11:11:58.271-07:00Writing Telnet in BashEvery so often, I find that I need to script some network connection. For interactive jobs, the standard answer is to use 'telnet' with 'expect' to achieve this. Unfortunately, expect is often a major pain to work with. The obvious modern solution would be to use Python, but I haven't learned that yet. What I do know is Bash, and wouldn't it be cool to do this entirely in Bash? So to prove that this works, I decided to write a simple telnet client entirely in Bash. If I can write telnet in Bash, I can extend it to manage the connection to do pretty much anything I want.<br />
<div>
<br /></div>
<div>
To make this work, I need to use the Bash network extensions. Built into Bash is a virtual file system for creating network sockets: /dev/tcp/host/port. Just open the file with the appropriate protocol/host/port, and you're good to go. Be aware that while this was added in Bash 2.04, it's a compile-time option, and the version of Bash included with some distributions might not support this.</div>
<div>
<br /></div>
<div>
So obviously, I was able to get this to work, or I wouldn't be writing this. Here's the script:</div>
<div>
<br /></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; color: black; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #888888;">#!/bin/bash</span>
<span style="color: #888888;">#</span>
<span style="color: #888888;"># A Bash-only telnet client</span>
<span style="color: #888888;">#</span>
<span style="color: #888888;"># Options:</span>
<span style="color: #888888;"># $1 host name</span>
<span style="color: #888888;"># $2 port (default 23)</span>
<span style="color: #888888;">#</span>
read_write_one_char<span style="color: #333333;">()</span>
<span style="color: #333333;">{</span>
<span style="color: #996633;">IFS</span><span style="color: #333333;">=</span><span style="background-color: #fff0f0;">$'\n'</span> <span style="color: #888888;"># tell read to treat all non-newline characters the same</span>
<span style="color: #008800; font-weight: bold;">while </span><span style="color: #007020;">true</span>; <span style="color: #008800; font-weight: bold;">do</span>
<span style="color: #008800; font-weight: bold;"> </span><span style="color: #007020;">read</span> -r -n 1 -t 0.01 C
<span style="color: #996633;">STATUS</span><span style="color: #333333;">=</span><span style="color: #996633;">$?</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">[</span> <span style="color: #008800; font-weight: bold;">${</span><span style="color: #996633;">STATUS</span><span style="color: #008800; font-weight: bold;">}</span> !<span style="color: #333333;">=</span> 0 <span style="color: #333333;">]</span>; <span style="color: #008800; font-weight: bold;">then</span>
<span style="color: #008800; font-weight: bold;"> if</span> <span style="color: #333333;">[</span> <span style="color: #008800; font-weight: bold;">${</span><span style="color: #996633;">STATUS</span><span style="color: #008800; font-weight: bold;">}</span> -gt 128 <span style="color: #333333;">]</span>; <span style="color: #008800; font-weight: bold;">then</span> <span style="color: #888888;"># Read returns 142 on timeout</span>
<span style="color: #008800; font-weight: bold;">return </span>0 <span style="color: #888888;"># Normal exit</span>
<span style="color: #008800; font-weight: bold;">fi</span>
<span style="color: #008800; font-weight: bold;"> return </span>1 <span style="color: #888888;"># EOF or other problem</span>
<span style="color: #008800; font-weight: bold;">fi</span>
<span style="color: #008800; font-weight: bold;"> if</span> <span style="color: #333333;">[</span> -z <span style="background-color: #fff0f0;">"${C}"</span> <span style="color: #333333;">]</span>; <span style="color: #008800; font-weight: bold;">then</span>
<span style="color: #008800; font-weight: bold;"> </span><span style="color: #007020;">echo</span> <span style="background-color: #fff0f0;">""</span>
<span style="color: #008800; font-weight: bold;">else</span>
<span style="color: #008800; font-weight: bold;"> </span><span style="color: #007020;">echo</span> -n <span style="background-color: #fff0f0;">"${C}"</span>
<span style="color: #008800; font-weight: bold;">fi</span>
<span style="color: #008800; font-weight: bold;"> done</span>
<span style="color: #333333;">}</span>
do_io<span style="color: #333333;">()</span>
<span style="color: #333333;">{</span>
<span style="color: #008800; font-weight: bold;">while </span><span style="color: #007020;">true</span>; <span style="color: #008800; font-weight: bold;">do</span>
<span style="color: #008800; font-weight: bold;"> </span>read_write_one_char 0<&3 <span style="color: #333333;">||</span> <span style="color: #007020;">break</span>
<span style="color: #007020;"> </span>read_write_one_char 1>&3 <span style="color: #333333;">||</span> <span style="color: #007020;">break</span>
<span style="color: #007020;"> </span><span style="color: #008800; font-weight: bold;">done</span>
<span style="color: #333333;">}</span>
<span style="color: #996633;">PORT</span><span style="color: #333333;">=</span><span style="background-color: #fff0f0;">"$2"</span>
<span style="color: #008800; font-weight: bold;">if</span> <span style="color: #333333;">[</span> -z <span style="background-color: #fff0f0;">"$PORT"</span> <span style="color: #333333;">]</span>; <span style="color: #008800; font-weight: bold;">then</span>
<span style="color: #008800; font-weight: bold;"> </span><span style="color: #996633;">PORT</span><span style="color: #333333;">=</span>23
<span style="color: #008800; font-weight: bold;">fi</span>
<span style="color: #007020;">exec </span>3<>/dev/tcp/<span style="color: #996633;">$1</span>/<span style="color: #008800; font-weight: bold;">${</span><span style="color: #996633;">PORT</span><span style="color: #008800; font-weight: bold;">}</span>
do_io
<span style="color: #007020;">exec </span>3>&-
</pre>
<pre style="line-height: 16.25px;"><span style="color: #007020;">exec </span>3<&-</pre>
</div>
<div>
So how does this work?
<br />
<br />
The last four lines have three uses of 'exec'. The syntax of the 'exec' command is rather counterintuitive--it's essentially overloading the command with something that doesn't exec a new binary. It's opening a socket for read and write to file descriptor 3, and then closing it when the work is done. Note that while you open the socket for read and write with a single call, you have to close read and write separately.<br />
<br />
The real work is in the function read_write_one_char(). This function uses the Bash built-in command 'read' to read one byte from stdin and copy it to stdout. Here we run into some significant limitations in Bash for handling I/O. I would like to be able to do a binary read into a string, the write it out, which is essentially what I'm doing. Unfortunately, Bash tries really hard to be working with words separated by whitespace, not binary data. The internal variable 'IFS' defines what it considers to be whitespace, so I have to override that to be just newline (using a Bash syntax for specifying non-ASCII constants).<br />
<br />
The read command returns a non-zero status if it times out that is greater than 128 (142 in my testing, but I wouldn't rely on that). If it returns any other non-zero status, the script assumes it's an end-of-file indication.<br />
<br />
When echoing the character that was read out, we are again bitten by the shell's insistence on working with words and whitespace, so the script has to undo that by treating an empty read as having read whitespace (which is only a newline, having overridden IFS as mentioned above).<br />
<br />
The read has a timeout of a hundredth of a second so that the same thread can switch between reading the console and the network. It's within a loop, however, so that if a burst of characters comes in, it will read until it times out before switching to the other input.<br />
<br />
That's it.<br />
<br />
The script works rather nicely for simple tasks. It could easily be extended to handle some things like \r\n sequences and things like that. Extending it to read more than one character at a time would improve performance. More importantly, it could easily save text read from the network for matching against patterns just like 'expect' does.<br />
<br />
One thing that is particularly cool about this script is that it's all pure Bash. Every command that it uses is built-in. There is not a single subprocess being forked. Just echo, read, test ([), and true.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-40089957886221932572016-02-16T17:36:00.001-08:002016-02-16T17:36:56.667-08:00Linux with LIRC Remote ControlsOn May 11, 2000, I ordered our first DVR. It was a ReplayTV 2020, capable of recording 20 hours of TV on its 20GB hard drive. We had previously used a VCR for recording several shows, but the DVR experience was so much better that we never even got around to watching some shows that we had previously recorded on VHS. Five years later, we replaced the ReplayTV with MythTV. I've refreshed the hardware, but the database has carried over, reporting that our first recording was on February 20, 2004 (and episode of CSI).<br />
<br />
I could go on and on about how wonderful MythTV is, though I wouldn't recommend it unless you like to tinker with all sorts of Linux oddities to keep everything working just right. One of those oddities is dealing with a remote control. While you can use a wireless keyboard (which we do), it's often much nicer to use a standard universal remote. Which brings us to the point of this post.<br />
<br />
To receive IR signals, you need an IR receiver. Today there are several USB-based solutions, including a programmable FLIRC device that remembers IR signals and converts them into the keystrokes of your choice. While I would probably get one of those if I were starting fresh today, I have an old PVR-250 card that included an IR receiver. I keep the card for digitizing VHS tapes, and take advantage of the IR receiver.<br />
<br />
All was good, until my remote control suddenly died. I tried new batteries. No luck. And of course the remote is no longer being made, as even something as standard as a universal remote has to be changed every few years, so I ended up ordering a new universal remote.<br />
<br />
Programming a universal remote for use with MythTV should be fairly simple. It doesn't really matter what codes the remote sends, as long as the computer can receive them, and as long as each button sends a different key. Making this a little trickier, the receiver I have only parses the RC-5 protocol used by Philips. So I set the remote to a code set for a Philips TV that sent signals on most of the buttons. I managed to find another universal remote, and I programmed it to a different Philips code set, then used the learning mode on the new remote to program the remaining buttons so that each button sent a different signal.<br />
<br />
To program the Linux side, there are three places to set up codes. The kernel has a mapping of codes to key codes in the input layer. LIRC has a mapping in /etc/lirc/lircd.conf, and applications have a mapping in ~/.lircrc.<br />
<br />
Fortunately, the lircd.conf mapping can be ignored once it's set up, as the key code to symbol mapping is standard regardless of the remote. While you still need the file, its purpose was to do the mapping now in the input layer for older drivers that didn't use that layer.<br />
<br />
The ~/.lircrc file is where the real magic of using LIRC comes in. If the remote worked like a keyboard, then all applications would see the same key for each button. But with LIRC, you can set up different actions for a given button for each program. For example, you can tell MythTV that the PLAY button has the action of 'P' on the keyboard, while for Xine the same PLAY button has the action of the space bar.<br />
<br />
The tricky part is setting up the initial mapping from remote codes to key symbols in the kernel. For this, there's the input-utils package. First, the 'lsinput' command told me that my remote was input 4. Knowing this, I used 'input-events 4' to watch the raw scan codes for each button on the remote. I found that a few were duplicates, so I had to use the learning mode to learn different codes for those buttons.<br />
<br />
Then it should have been a simple matter of using 'input-kbd' to program a new set of mappings. This program takes a mapping from scan codes to keyboard codes (which LIRC then passes on to the programs). I had a file that mapped the codes for my previous remote, and even the remote from before that (which we went back to using briefly, despite some buttons not working on it). I was able to add the codes for the new remote. But that's when things fell apart.<br />
<br />
Somehow, after sending the new mapping file to the kernel using input-kbd, displaying the active map would show that some buttons reverted back to a previous value. I was absolutely convinced that I was doing everything correctly, so I was going to report this as a kernel bug. In preparing to send the report, I ran input-kbd under strace so that I could cite the exact ioctls that were misbehaving, and much to my surprise, I saw that input-kbd was sending my mapping, followed by a bunch of old mappings.<br />
<br />
So it was time to look at the source for input-kbd.<br />
<br />
Since I use Gentoo Linux, I had the source already downloaded. Looking at the source, and knowing the behavior I was seeing, the bug was fairly obvious. The program was written assuming that anyone submitting a new mapping would want to remap all the same codes as the old map, so it read the old map, then overwrote it with the new map, but when sending the map back to the kernel, used the size of the original map.<br />
<br />
So I wrote a patch to fix that bug. I also took the time to allow comments in the input file (saving my init script having to strip them out with sed and grep before loading them). Again, as a Gentoo user, I was able to put the patches in /etc/portage/patches/sys-apps/input-utils/, and now the patches are automatically applied whenever I install the package.<br />
<br />
But being a responsible person, I also looked for a place to report the bug back to the developer. The project is on Git Hub, but there is no issue tracker there or anywhere else that I could find. So I resorted to emailing the developer, hoping that the published address was still valid. I'm pleased to report that the patches got through and were immediately applied (with a few tweaks). I've sent one more iteration of improvements, but hopefully when input-utils-1.2 is released, this bug will be gone.<br />
<br />
So having done all that, I decided to take the remote apart and see what was wrong with it. I pried it apart with a screwdriver. It's just one circuit board with a single chip. I couldn't see any indication of cracked solder or anything like that, so I put it back together. I put the batteries back in, and...<br />
<br />
The old remote works just fine.<br />
<br />
Well, I learned a bit about how the mapping of remotes works in Linux, and I rather like the new remote. In any case, I'll have something to switch to when the old one dies again.Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-87927865064458860822015-12-10T11:48:00.003-08:002015-12-10T11:48:49.909-08:00Portable Inline Assembly<div>
This is a fun little tidbit. Assembly language is, obviously, not portable. If you use inline assembly code in a C program, you won't expect it to run on multiple processors without special handling for each one. Well, there's an exception to that.<br />
<br />
First, the trivial exception:</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">__asm__(<span style="color: blue;">""</span>);
</pre>
</div>
<div>
<br />
That's valid code (assuming the gcc compiler, as I will throughout this discussion). But it doesn't do anything, so it's rather pointless. The magic comes in when you specify the input and output parameters. For output, I'll specify two registers, assigned to the variables 'a' and 'b'. For input, I'll use the same registers. The syntax GCC uses is that zero is the first output register, and so-forth. Note that you specify the output first.<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;">__asm__(<span style="color: blue;">""</span> \
:<span style="color: blue;">"=r"</span>(a), <span style="color: blue;">"=r"</span>(b) \
:<span style="color: blue;">"0"</span>(b),<span style="color: blue;">"1"</span>(a) );
</pre>
</div>
<div>
<br />
Now this does something! We've told it that the input is two registers with the values from variables 'b' and 'a', and the output is the same two registers which are variables 'a' and 'b'. Notice the order. We've swapped two variables. No intermediary storage. No fancy xors. No actual code. What we've done is tell the compiler to swap it's notion of where 'a' and 'b' are stored (with both being registers).<br />
<br />
We can make this into a fancy macro:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border: solid gray; color: black border-width: .1em .1em .1em .8em; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: teal;">#define SWAP_ASM(_a,_b) __asm__("" \</span>
<span style="color: teal;"> :"=r"(_a), "=r"(_b) \</span>
<span style="color: teal;"> :"0"(_b),"1"(_a) );</span>
</pre>
</div>
<div>
<br />
And demonstrate that it works:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: teal;">#include <stdio.h></span>
<span style="color: teal;">#define SWAP_ASM(_a,_b) __asm__("" \</span>
<span style="color: teal;"> :"=r"(_a), "=r"(_b) \</span>
<span style="color: teal;"> :"0"(_b),"1"(_a) );</span>
<span style="color: navy; font-weight: bold;">int</span> main(<span style="color: navy; font-weight: bold;">int</span> argc,<span style="color: navy; font-weight: bold;">char</span> *argv[])
{
<span style="color: navy; font-weight: bold;">int</span> a=<span style="color: purple;">'a'</span>, b=<span style="color: purple;">'b'</span>;
(<span style="color: navy; font-weight: bold;">void</span>)argc;(<span style="color: navy; font-weight: bold;">void</span>)argv; <span style="color: #008800; font-style: italic;">// no "unused" warning</span>
SWAP_ASM(a,b);
printf(<span style="color: blue;">"a contains '%c'\n"
"b contains '%c'\n"</span>,a,b);
<span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">0</span>;
}
</pre>
</div>
<div>
<br />
Now admittedly, this isn't very useful. If the variables aren't in registers, the compiler has to generate load and store instructions before and after the swap. Using inline assembly can mess up optimization (probably more so in older releases), so using a variable to do a swap with all your code being in C is likely a better choice. Still, a neat little hack.</div>
</div>
</div>
</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-24680731777348017162015-12-03T15:01:00.000-08:002015-12-03T15:01:07.459-08:00Scripting ssh passwordsOne of the most powerful communications tools available is ssh. Pretty much the only version on Linux is OpenSSH, and most of the versions I've come across on other platforms are derived from it. I assume you know that, and I assume you also know that the best way to use it is with pre-shared keys so that you don't have to worry about passwords. Unfortunately, that isn't always an option.<br />
<div>
<br /></div>
<div>
Recently I was working on a script that needed to use ssh to connect to an embedded system. There are no keys on the remote system, so you have to use a password. You can look the password up in a database. Asking the user to do that and type it in manually would be a pain, and in this case, would add no security.</div>
<div>
<br /></div>
<div>
Openssh does everything it can to make scripting passwords difficult, which is only reasonable from a security standpoint. But for anyone who has been around Unix systems for a while knows, there's a program called "expect" that solves the problem. Expect allocates a pseudo TTY device, spawns a target program, and controls it through the TTY. It can watch for prompts and issue responses, and it can eventually return control to the parent TTY, allowing a user to interact manually.</div>
<div>
<br /></div>
<div>
So I set up a script using expect to enter the password for ssh, and all was good. I invited everyone else in my department to use the same script. Most people loved it. Then I started getting complaints. It seems that while I would expect expect to be installed everywhere, that expectation was flawed. I could ask everyone to install expect (and I did), but it seems that everyone is managing their own Linux systems, and many developers don't really know much about doing so.</div>
<div>
<br /></div>
<div>
I needed a better solution.</div>
<div>
<br /></div>
<div>
I found a better solution.</div>
<div>
<br /></div>
<div>
Ssh has a feature where it can run a GUI program to ask for a password. That is exactly where we'll get our scripted password inserted. This requires two things: Set the environment variable SSH_ASKPASS to an executable that will write the password to stdout, and have the ssh process not be connected to a tty.</div>
<div>
<br /></div>
<div>
The first part is easy. Just create a script that echos the password:<br />
<br />
<pre> echo echo $PW > /tmp/pw.$$
chmod 700 /tmp/pw.$$</pre>
</div>
<div>
<br />
The second part is a little more tricky. Also, it means that we can't interact with ssh once it connects. Well, maybe we could with some additional trickery, but fortunately, my use of ssh didn't require interacting with it once the connection was established--I was just forwarding ports. The obvious solution of redirecting stdin from /dev/null doesn't work, and neither does outright closing stdin. The tty is part of a process state independent of the file descriptors, so we have to actually detach it. What we want here is a program called 'setsid.' This is part of the util-linux package, and it seems to be on every system I've been able to find, including the ones that didn't have expect.<br />
<br />
Now there's one problem with setsid. It immediately runs the program in the background. I wanted to check the exit status of ssh to verify that everything was good. I thought I was in luck, seeing that there's an option to do just this: --wait. Then I found that most of the other developers have older systems from before this option was added (in 2013, apparently). This required creating another temporary script and a temporary results file, with the parent script waiting in a loop for it to finish. So in /tmp/dossh.$$, I put the ssh command, followed by saving of the status ($?) in /tmp/dossh.$$.result. And to keep everything clean, the last line of the script removes the script itself from /tmp.<br />
<br />
So the parent script runs 'setsid /tmp/dossh.$$' then sits in a loop:<br />
<pre> while ! [ -f /tmp/dossh.$$.result]; do sleep .1; done</pre>
Then the parent script can grab the result, remove the remaining temporary files, and make use of the ssh tunnel. No manual password entry required.<br />
<br />
No expect required! (And that's a good thing. Expect is a pain to use, in large part due to TCL being a painful language, but also due to issues where subtle changes in software versions can break everything, such as if a prompt changes slightly.)<br />
<br />
Everything works exactly as the user would expect it to.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com1tag:blogger.com,1999:blog-5581770500938014748.post-85229430004112241262015-11-25T09:15:00.000-08:002015-11-25T09:15:33.012-08:00Solving a PuzzleEarlier this year, I was given a puzzle as a gift. It's a simple frame with Tetris-like blocks of different shapes, and the object is to get all nine blocks into the frame. Making it more difficult, there will be leftover empty squares throughout the puzzle. I played around with it for a while, and it wasn't too difficult to get to within one square of completing it, but I was probably nowhere close to actually solving it.<br />
<div>
<br /></div>
<div>
Being a programmer, I decided it would be more fun to program my computer to solve the puzzle. I spent a couple of hours on it, and came up with a nice result. I'll share the result below, along with some observations about the program and the puzzle.</div>
<div>
<br /></div>
<div>
First, here's a link to the puzzle: <a href="http://www.palmettopuzzleworks.net/#!The Infuriater/zoom/mainPage/i8m8k">http://www.palmettopuzzleworks.net/</a></div>
<div>
You can <a href="https://www.etsy.com/listing/209610592/the-infuriater-one-bad-diabolic-puzzle">buy it directly</a> through Etsy for $20.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://static.wixstatic.com/media/db7e98_6ac0607f4d5945eebb82d82c236d9065.jpg/v1/fit/w_843,h_744,q_75/db7e98_6ac0607f4d5945eebb82d82c236d9065.jpg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="282" src="https://static.wixstatic.com/media/db7e98_6ac0607f4d5945eebb82d82c236d9065.jpg/v1/fit/w_843,h_744,q_75/db7e98_6ac0607f4d5945eebb82d82c236d9065.jpg" width="320" /></a></div>
<div>
<br /></div>
<div>
Before I delve into my program, let me start by suggesting that this might make a great programming assignment. It's a very well-defined problem, but with a number of subtleties to watch out for.</div>
<div>
<br /></div>
<div>
So let me show you my solution. My intuition was that this would be a computationally complex problem, and it looked like a good fit regardless, so my language of choice was C.</div>
<div>
<br /></div>
<div>
The first thing to do is define the data structures. I've found that in the vast majority of problems, the data structures drive the code. If you have the wrong data structures, you'll never get a good solution, but with the right data structures, the code mostly flows into place.</div>
<div>
<br /></div>
<div>
As you can see in the picture, the board is an 11x11 grid with some spaces filled in. That makes the board an easy two-dimensional array. The largest piece fits in a 4x5 grid, so I created a three-dimensional array for the pieces initialized to a 1 for the spots that are filled and a 0 for the squares not occupied. Thinking ahead, I'm going to have to rotate each piece, so I need to use a square for each piece, not just a rectangle, so each piece is a 5x5 grid.</div>
<div>
<br /></div>
<!-- height:200px;color: #000000; -->
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: navy; font-weight: bold;">int</span> grid[<span style="color: blue;">11</span>][<span style="color: blue;">11</span>];
<span style="color: navy; font-weight: bold;">int</span> pieces[<span style="color: blue;">9</span>][<span style="color: blue;">5</span>][<span style="color: blue;">5</span>] =
{
<span style="color: #008800; font-style: italic;">// first four pieces are "big" and take four rows</span>
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
<span style="color: #008800; font-style: italic;">// remaining five pieces take three rows</span>
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } }
};
</pre>
</div>
<div>
<br />
Initializing the grid is pretty simple: a zero represents an open space, a number indicates a piece (1 through 9), and another constant represents the border (10). Because the border is more filled than open, the code fills the borders, then opens up the spaces where a piece can intrude.<br />
<br /></div>
<!-- height:200px;color: #000000; -->
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: teal;">#define BORDER 10</span>
<span style="color: navy; font-weight: bold;">void</span> init_border(<span style="color: navy; font-weight: bold;">void</span>)
{
<span style="color: #008800; font-style: italic;">// Set grid to zero</span>
memset(grid,<span style="color: blue;">0</span>,<span style="color: navy; font-weight: bold;">sizeof</span>(grid));
<span style="color: #008800; font-style: italic;">// Border defaults to blocked</span>
<span style="color: navy; font-weight: bold;">for</span>(<span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>;i<<span style="color: blue;">11</span>;++i)
{
grid[<span style="color: blue;">0</span>][i] = grid[i][<span style="color: blue;">0</span>] = grid[<span style="color: blue;">10</span>][i] = grid[i][<span style="color: blue;">10</span>] = BORDER;
}
<span style="color: #008800; font-style: italic;">// Clear spots</span>
grid[<span style="color: blue;">0</span>][<span style="color: blue;">2</span>] = grid[<span style="color: blue;">0</span>][<span style="color: blue;">4</span>] = grid[<span style="color: blue;">0</span>][<span style="color: blue;">8</span>] = <span style="color: blue;">0</span>;
grid[<span style="color: blue;">10</span>][<span style="color: blue;">1</span>] = grid[<span style="color: blue;">10</span>][<span style="color: blue;">4</span>] = grid[<span style="color: blue;">10</span>][<span style="color: blue;">6</span>] = grid[<span style="color: blue;">10</span>][<span style="color: blue;">8</span>] = <span style="color: blue;">0</span>;
grid[<span style="color: blue;">3</span>][<span style="color: blue;">0</span>] = grid[<span style="color: blue;">5</span>][<span style="color: blue;">0</span>] = grid[<span style="color: blue;">8</span>][<span style="color: blue;">0</span>] = <span style="color: blue;">0</span>;
grid[<span style="color: blue;">1</span>][<span style="color: blue;">10</span>] = grid[<span style="color: blue;">5</span>][<span style="color: blue;">10</span>] = grid[<span style="color: blue;">7</span>][<span style="color: blue;">10</span>] = grid[<span style="color: blue;">9</span>][<span style="color: blue;">10</span>] = <span style="color: blue;">0</span>;
}
</pre>
</div>
<div>
<br />
Now here we come to the key trick to make the whole thing work. I have to try each piece in four different rotations. If I rotate the pieces on the fly, the program will be spending most of its time doing rotations. That's not a good idea for something that is already likely to be quite computationally intensive. So why not save the work and just do it once? This raises one subtlety to the problem: The pieces all fit in a 5x5 grid, but have at least one row or column empty. The solving code will want to assume that the top row and left column are non-empty, so each rotation has to also shift to make that happen. With that explained, there's nothing particularly fancy about the code, though I'll admit that on the first run, it mangled the pieces by doing some reflections as well as rotations.<br />
<br /></div>
<!-- height:200px;color: #000000; -->
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: navy; font-weight: bold;">int</span> all_pieces[<span style="color: blue;">9</span>][<span style="color: blue;">4</span>][<span style="color: blue;">5</span>][<span style="color: blue;">5</span>];
<span style="color: navy; font-weight: bold;">void</span> init_rotations(<span style="color: navy; font-weight: bold;">void</span>)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>; piece<<span style="color: blue;">9</span>; ++piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">0</span>; rotation<<span style="color: blue;">4</span>; ++rotation )
{
<span style="color: navy; font-weight: bold;">if</span> ( rotation == <span style="color: blue;">0</span> )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][r][c] = pieces[piece][r][c];
}
}
}
<span style="color: navy; font-weight: bold;">else</span>
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][<span style="color: blue;">4</span>-c][r] = all_pieces[piece][rotation-<span style="color: blue;">1</span>][r][c];
}
}
}
}
}
<span style="color: #008800; font-style: italic;">// Now shift rotations to all be in the upper-left (no all-zero rows or all-zero columns</span>
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>; piece<<span style="color: blue;">9</span>; ++piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">1</span>; rotation<<span style="color: blue;">4</span>; ++rotation )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>; i<<span style="color: blue;">5</span>; ++i )
{
<span style="color: navy; font-weight: bold;">if</span> ( all_pieces[piece][rotation][<span style="color: blue;">0</span>][i] ) <span style="color: navy; font-weight: bold;">goto</span> next; <span style="color: #008800; font-style: italic;">// Something in the first row</span>
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">4</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r+<span style="color: blue;">1</span>][c];
}
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][<span style="color: blue;">4</span>][c] = <span style="color: blue;">0</span>;
}
--rotation; <span style="color: navy; font-weight: bold;">continue</span>;
next: ;
}
}
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>; piece<<span style="color: blue;">9</span>; ++piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">1</span>; rotation<<span style="color: blue;">4</span>; ++rotation )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>; i<<span style="color: blue;">5</span>; ++i )
{
<span style="color: navy; font-weight: bold;">if</span> ( all_pieces[piece][rotation][i][<span style="color: blue;">0</span>] ) <span style="color: navy; font-weight: bold;">goto</span> next2; <span style="color: #008800; font-style: italic;">// Something in the first column</span>
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">4</span>;++c )
{
all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r][c+<span style="color: blue;">1</span>];
}
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
all_pieces[piece][rotation][r][<span style="color: blue;">4</span>] = <span style="color: blue;">0</span>;
}
--rotation; <span style="color: navy; font-weight: bold;">continue</span>;
next2: ;
}
}
}
</pre>
</div>
<div>
<br />
Before writing the code to try all the combinations and find the solution, I need to be able to display the board. I also need to be able to display the pieces to check that I've coded and rotated them correctly. This is a place where spending a few minutes extra to have nice readable output can save a lot of time in understanding the results. Using a graphics toolkit or generating HTML would be overkill for this problem. Simple printing to the console would be fine, but tossing in some ANSI color codes to make the pieces easier to visualize would be well worth the effort. Fortunately, I have a handy set of ANSI color code defines:<br />
<br /></div>
<!-- height:200px;color: #000000; -->
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: teal;">#define _CN "\033[m" </span><span style="color: #008800; font-style: italic;">// Reset to default color and attributes</span>
<span style="color: teal;">#define _CRED "\033[1;31m" </span><span style="color: #008800; font-style: italic;">// Set text to bold red</span>
<span style="color: teal;">#define _Cred "\033[31m" </span><span style="color: #008800; font-style: italic;">// Set text to red</span>
<span style="color: teal;">#define _C_red "\033[4;31m" </span><span style="color: #008800; font-style: italic;">// Set text to underlined and red</span>
<span style="color: teal;">#define _C_RED "\033[4;1;31m" </span><span style="color: #008800; font-style: italic;">// Set text to underline and bold red</span>
<span style="color: teal;">#define _Bred "\033[41m" </span><span style="color: #008800; font-style: italic;">// Set background to red</span>
<span style="color: teal;">#define _CGRN "\033[1;32m"</span>
<span style="color: teal;">#define _Cgrn "\033[32m"</span>
<span style="color: teal;">#define _C_grn "\033[4;32m"</span>
<span style="color: teal;">#define _C_GRN "\033[4;1;32m"</span>
<span style="color: teal;">#define _Bgrn "\033[42m"</span>
<span style="color: teal;">#define _CYEL "\033[1;33m"</span>
<span style="color: teal;">#define _Cyel "\033[33m"</span>
<span style="color: teal;">#define _C_yel "\033[4;33m"</span>
<span style="color: teal;">#define _C_YEL "\033[4;1;33m"</span>
<span style="color: teal;">#define _Byel "\033[43m"</span>
<span style="color: teal;">#define _CBLU "\033[1;34m"</span>
<span style="color: teal;">#define _Cblu "\033[34m"</span>
<span style="color: teal;">#define _C_blu "\033[4;34m"</span>
<span style="color: teal;">#define _C_BLU "\033[4;1;34m"</span>
<span style="color: teal;">#define _Bblu "\033[44m"</span>
<span style="color: teal;">#define _CMAG "\033[1;35m"</span>
<span style="color: teal;">#define _Cmag "\033[35m"</span>
<span style="color: teal;">#define _C_mag "\033[4;35m"</span>
<span style="color: teal;">#define _C_MAG "\033[4;1;35m"</span>
<span style="color: teal;">#define _Bmag "\033[45m"</span>
<span style="color: teal;">#define _CCYN "\033[1;36m"</span>
<span style="color: teal;">#define _Ccyn "\033[36m"</span>
<span style="color: teal;">#define _C_cyn "\033[4;36m"</span>
<span style="color: teal;">#define _C_CYN "\033[4;1;36m"</span>
<span style="color: teal;">#define _Bcyn "\033[46m"</span>
<span style="color: teal;">#define _CWHT "\033[1;37m"</span>
<span style="color: teal;">#define _Cwht "\033[37m"</span>
<span style="color: teal;">#define _C_wht "\033[4;37m"</span>
<span style="color: teal;">#define _C_WHT "\033[4;1;37m"</span>
<span style="color: teal;">#define _Bwht "\033[47m"</span>
<span style="color: teal;">#define _CBLK "\033[1;30m"</span>
<span style="color: teal;">#define _Cblk "\033[30m"</span>
<span style="color: teal;">#define _C_blk "\033[4;30m"</span>
<span style="color: teal;">#define _C_BLK "\033[4;1;30m"</span>
<span style="color: teal;">#define _Bblk "\033[40m"</span>
<span style="color: #008800; font-style: italic;">/*</span>
<span style="color: #008800; font-style: italic;"> * ANSI attribute strings</span>
<span style="color: #008800; font-style: italic;"> */</span>
<span style="color: teal;">#define _A_BOLD "\033[1m" </span><span style="color: #008800; font-style: italic;">// Leave color and underline-status as-is, set BOLD</span>
<span style="color: teal;">#define _A_UNDER "\033[4m" </span><span style="color: #008800; font-style: italic;">// Leave color and bold-status as-is, set UNDERLINE</span>
<span style="color: teal;">#define _A_BOLD_UNDER "\033[1;4m" </span><span style="color: #008800; font-style: italic;">// Just an optimized version of _A_BOLD _A_UNDER</span>
</pre>
</div>
<div>
<br />
So using those defines to display the grid and the pieces is fairly straightforward. You'll notice that I take advantage of C's string concatenation--any two strings separated only by whitespace are treated as a single string.<br />
<br /></div>
<!-- height:200px;color: #000000; -->
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: navy; font-weight: bold;">void</span> display_grid(<span style="color: navy; font-weight: bold;">void</span>)
{
printf(_Bblk<span style="color: blue;">" "</span>_CN<span style="color: blue;">"\n"</span>);
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> row=<span style="color: blue;">0</span>;row<<span style="color: blue;">11</span>;++row)
{
printf(_Bblk<span style="color: blue;">" "</span>_CN);
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> col=<span style="color: blue;">0</span>;col<<span style="color: blue;">11</span>;++col)
{
<span style="color: navy; font-weight: bold;">char</span> c;
c = grid[row][col] + <span style="color: purple;">'0'</span>;
<span style="color: navy; font-weight: bold;">switch</span>(grid[row][col]) {
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">0</span>: c=<span style="color: purple;">' '</span>; printf(_Bwht); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">1</span>:
printf(_Bcyn); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">2</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">3</span>:
printf(_Bblu); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">4</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">5</span>:
printf(_Bmag); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">6</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">7</span>:
printf(_Byel); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">8</span>:
printf(_Bred); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">9</span>:
printf(_Bgrn); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> BORDER: c=<span style="color: purple;">' '</span>; printf(_Bblk); <span style="color: navy; font-weight: bold;">break</span>;
}
printf(<span style="color: blue;">"%c"</span>_CN,c);
}
printf(_Bblk<span style="color: blue;">" "</span>_CN<span style="color: blue;">"\n"</span>);
}
printf(_Bblk<span style="color: blue;">" "</span>_CN<span style="color: blue;">"\n"</span>);
printf(<span style="color: blue;">"\n"</span>);
}
<span style="color: navy; font-weight: bold;">void</span> display_pieces(<span style="color: navy; font-weight: bold;">void</span>)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>;piece<<span style="color: blue;">9</span>;++piece)
{
printf(<span style="color: blue;">"Piece %d rotations\n"</span>,piece+<span style="color: blue;">1</span>);
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> row=<span style="color: blue;">0</span>;row<<span style="color: blue;">5</span>;++row)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">0</span>;rotation<<span style="color: blue;">4</span>;++rotation)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> col=<span style="color: blue;">0</span>;col<<span style="color: blue;">5</span>;++col)
{
<span style="color: navy; font-weight: bold;">char</span> c;
c = all_pieces[piece][rotation][row][col] ? <span style="color: purple;">'1'</span> + piece : <span style="color: purple;">' '</span>;
<span style="color: navy; font-weight: bold;">switch</span>(all_pieces[piece][rotation][row][col] * (piece+<span style="color: blue;">1</span>)) {
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">0</span>: c=<span style="color: purple;">' '</span>; printf(_Bwht); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">1</span>:
printf(_Bcyn); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">2</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">3</span>:
printf(_Bblu); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">4</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">5</span>:
printf(_Bmag); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">6</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">7</span>:
printf(_Byel); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">8</span>:
printf(_Bred); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">9</span>:
printf(_Bgrn); <span style="color: navy; font-weight: bold;">break</span>;
default:
printf(<span style="color: blue;">"invalid"</span>); <span style="color: navy; font-weight: bold;">break</span>;
}
printf(<span style="color: blue;">"%c"</span>_CN,c);
}
printf(<span style="color: blue;">" "</span>);
}
printf(<span style="color: blue;">"\n"</span>);
}
}
}
</pre>
</div>
<div>
<br />
With the above code, I have all that is needed to display the pre-rotated pieces (which proved vital for debugging mangled rotations) and the game board with any pieces placed in it. Starting out, it looks like:<br />
<br /></div>
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; color: black; height: 200px; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="font-family: Courier New; font-size: 10pt;">Piece 1 rotations
<span style="background-color: #f0f0f0; color: black;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span> <span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span> <span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f0f0;">1</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 2 rotations
<span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">2</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 3 rotations
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span> <span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #0000f0;">3</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 4 rotations
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">4</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 5 rotations
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">5</span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f000f0;">5</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 6 rotations
<span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">6</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 7 rotations
<span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f000;">7</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 8 rotations
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f00000;">8</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Piece 9 rotations
<span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #00f000;">9</span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #00f000;">9</span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
<span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span> <span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span>
Empty board
<span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: #f0f0f0;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span><span style="background-color: black;"> </span>
<span style="background-color: black;"> </span>
</pre>
</div>
<div>
<br />
So the the code to actually go through the placements feels anticlimactic at this point. It simply marches through the puzzle, trying every possible combination in much the way I would do if I were doing an exhaustive search by hand. Here's the complete program:<br />
<br /></div>
<!-- height:200px;color: #000000; -->
<!-- HTML generated using hilite.me -->
<br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; color: black; height: 200px; overflow: auto; padding: .2em .6em; width: auto;">
<pre style="line-height: 125%; margin: 0;"><span style="color: #008800; font-style: italic;">/*</span>
<span style="color: #008800; font-style: italic;"> * Find the solution or solutions to The Infuriater</span>
<span style="color: #008800; font-style: italic;"> *</span>
<span style="color: #008800; font-style: italic;"> * By Preston Crow</span>
<span style="color: #008800; font-style: italic;"> *</span>
<span style="color: #008800; font-style: italic;"> * gcc -std=c99 -W -Wall puzzle.c -o puzzle -O3 && puzzle</span>
<span style="color: #008800; font-style: italic;"> */</span>
<span style="color: teal;">#include <stdio.h></span>
<span style="color: teal;">#include <stdlib.h></span>
<span style="color: teal;">#include <string.h></span>
<span style="color: teal;">#define _CN "\033[m" </span><span style="color: #008800; font-style: italic;">// Reset to default color and attributes</span>
<span style="color: teal;">#define _CRED "\033[1;31m" </span><span style="color: #008800; font-style: italic;">// Set text to bold red</span>
<span style="color: teal;">#define _Cred "\033[31m" </span><span style="color: #008800; font-style: italic;">// Set text to red</span>
<span style="color: teal;">#define _C_red "\033[4;31m" </span><span style="color: #008800; font-style: italic;">// Set text to underlined and red</span>
<span style="color: teal;">#define _C_RED "\033[4;1;31m" </span><span style="color: #008800; font-style: italic;">// Set text to underline and bold red</span>
<span style="color: teal;">#define _Bred "\033[41m" </span><span style="color: #008800; font-style: italic;">// Set background to red</span>
<span style="color: teal;">#define _CGRN "\033[1;32m"</span>
<span style="color: teal;">#define _Cgrn "\033[32m"</span>
<span style="color: teal;">#define _C_grn "\033[4;32m"</span>
<span style="color: teal;">#define _C_GRN "\033[4;1;32m"</span>
<span style="color: teal;">#define _Bgrn "\033[42m"</span>
<span style="color: teal;">#define _CYEL "\033[1;33m"</span>
<span style="color: teal;">#define _Cyel "\033[33m"</span>
<span style="color: teal;">#define _C_yel "\033[4;33m"</span>
<span style="color: teal;">#define _C_YEL "\033[4;1;33m"</span>
<span style="color: teal;">#define _Byel "\033[43m"</span>
<span style="color: teal;">#define _CBLU "\033[1;34m"</span>
<span style="color: teal;">#define _Cblu "\033[34m"</span>
<span style="color: teal;">#define _C_blu "\033[4;34m"</span>
<span style="color: teal;">#define _C_BLU "\033[4;1;34m"</span>
<span style="color: teal;">#define _Bblu "\033[44m"</span>
<span style="color: teal;">#define _CMAG "\033[1;35m"</span>
<span style="color: teal;">#define _Cmag "\033[35m"</span>
<span style="color: teal;">#define _C_mag "\033[4;35m"</span>
<span style="color: teal;">#define _C_MAG "\033[4;1;35m"</span>
<span style="color: teal;">#define _Bmag "\033[45m"</span>
<span style="color: teal;">#define _CCYN "\033[1;36m"</span>
<span style="color: teal;">#define _Ccyn "\033[36m"</span>
<span style="color: teal;">#define _C_cyn "\033[4;36m"</span>
<span style="color: teal;">#define _C_CYN "\033[4;1;36m"</span>
<span style="color: teal;">#define _Bcyn "\033[46m"</span>
<span style="color: teal;">#define _CWHT "\033[1;37m"</span>
<span style="color: teal;">#define _Cwht "\033[37m"</span>
<span style="color: teal;">#define _C_wht "\033[4;37m"</span>
<span style="color: teal;">#define _C_WHT "\033[4;1;37m"</span>
<span style="color: teal;">#define _Bwht "\033[47m"</span>
<span style="color: teal;">#define _CBLK "\033[1;30m"</span>
<span style="color: teal;">#define _Cblk "\033[30m"</span>
<span style="color: teal;">#define _C_blk "\033[4;30m"</span>
<span style="color: teal;">#define _C_BLK "\033[4;1;30m"</span>
<span style="color: teal;">#define _Bblk "\033[40m"</span>
<span style="color: #008800; font-style: italic;">/*</span>
<span style="color: #008800; font-style: italic;"> * ANSI attribute strings</span>
<span style="color: #008800; font-style: italic;"> */</span>
<span style="color: teal;">#define _A_BOLD "\033[1m" </span><span style="color: #008800; font-style: italic;">// Leave color and underline-status as-is, set BOLD</span>
<span style="color: teal;">#define _A_UNDER "\033[4m" </span><span style="color: #008800; font-style: italic;">// Leave color and bold-status as-is, set UNDERLINE</span>
<span style="color: teal;">#define _A_BOLD_UNDER "\033[1;4m" </span><span style="color: #008800; font-style: italic;">// Just an optimized version of _A_BOLD _A_UNDER</span>
<span style="color: navy; font-weight: bold;">int</span> grid[<span style="color: blue;">11</span>][<span style="color: blue;">11</span>];
<span style="color: navy; font-weight: bold;">int</span> pieces[<span style="color: blue;">9</span>][<span style="color: blue;">5</span>][<span style="color: blue;">5</span>] =
{
<span style="color: #008800; font-style: italic;">// first four pieces are "big" and take four rows</span>
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
<span style="color: #008800; font-style: italic;">// remaining five pieces take three rows</span>
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } },
{ { <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span> },
<span style="background-color: #e3d2d2; color: #a61717;">#</span><span style="color: navy; font-weight: bold;">if</span> <span style="color: blue;">0</span>
{ <span style="color: blue;">0</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
<span style="background-color: #e3d2d2; color: #a61717;">#</span><span style="color: navy; font-weight: bold;">else</span>
{ <span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">1</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
<span style="background-color: #e3d2d2; color: #a61717;">#</span>endif
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> },
{ <span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span>,<span style="color: blue;">0</span> } }
};
<span style="color: navy; font-weight: bold;">int</span> all_pieces[<span style="color: blue;">9</span>][<span style="color: blue;">4</span>][<span style="color: blue;">5</span>][<span style="color: blue;">5</span>];
<span style="color: navy; font-weight: bold;">int</span> place[<span style="color: blue;">9</span>][<span style="color: blue;">3</span>]; <span style="color: #008800; font-style: italic;">// rotation,row,col for the piece</span>
<span style="color: teal;">#define BORDER 10</span>
<span style="color: navy; font-weight: bold;">void</span> init_border(<span style="color: navy; font-weight: bold;">void</span>)
{
<span style="color: #008800; font-style: italic;">// Set grid to zero</span>
memset(grid,<span style="color: blue;">0</span>,<span style="color: navy; font-weight: bold;">sizeof</span>(grid));
<span style="color: #008800; font-style: italic;">// Border defaults to blocked</span>
<span style="color: navy; font-weight: bold;">for</span>(<span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>;i<<span style="color: blue;">11</span>;++i)
{
grid[<span style="color: blue;">0</span>][i] = grid[i][<span style="color: blue;">0</span>] = grid[<span style="color: blue;">10</span>][i] = grid[i][<span style="color: blue;">10</span>] = BORDER;
}
<span style="color: #008800; font-style: italic;">// Clear spots</span>
grid[<span style="color: blue;">0</span>][<span style="color: blue;">2</span>] = grid[<span style="color: blue;">0</span>][<span style="color: blue;">4</span>] = grid[<span style="color: blue;">0</span>][<span style="color: blue;">8</span>] = <span style="color: blue;">0</span>;
grid[<span style="color: blue;">10</span>][<span style="color: blue;">1</span>] = grid[<span style="color: blue;">10</span>][<span style="color: blue;">4</span>] = grid[<span style="color: blue;">10</span>][<span style="color: blue;">6</span>] = grid[<span style="color: blue;">10</span>][<span style="color: blue;">8</span>] = <span style="color: blue;">0</span>;
grid[<span style="color: blue;">3</span>][<span style="color: blue;">0</span>] = grid[<span style="color: blue;">5</span>][<span style="color: blue;">0</span>] = grid[<span style="color: blue;">8</span>][<span style="color: blue;">0</span>] = <span style="color: blue;">0</span>;
grid[<span style="color: blue;">1</span>][<span style="color: blue;">10</span>] = grid[<span style="color: blue;">5</span>][<span style="color: blue;">10</span>] = grid[<span style="color: blue;">7</span>][<span style="color: blue;">10</span>] = grid[<span style="color: blue;">9</span>][<span style="color: blue;">10</span>] = <span style="color: blue;">0</span>;
}
<span style="color: navy; font-weight: bold;">void</span> init_rotations(<span style="color: navy; font-weight: bold;">void</span>)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>; piece<<span style="color: blue;">9</span>; ++piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">0</span>; rotation<<span style="color: blue;">4</span>; ++rotation )
{
<span style="color: navy; font-weight: bold;">if</span> ( rotation == <span style="color: blue;">0</span> )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][r][c] = pieces[piece][r][c];
}
}
}
<span style="color: navy; font-weight: bold;">else</span>
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][<span style="color: blue;">4</span>-c][r] = all_pieces[piece][rotation-<span style="color: blue;">1</span>][r][c];
}
}
}
}
}
<span style="color: #008800; font-style: italic;">// Now shift rotations to all be in the upper-left (no all-zero rows or all-zero columns</span>
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>; piece<<span style="color: blue;">9</span>; ++piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">1</span>; rotation<<span style="color: blue;">4</span>; ++rotation )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>; i<<span style="color: blue;">5</span>; ++i )
{
<span style="color: navy; font-weight: bold;">if</span> ( all_pieces[piece][rotation][<span style="color: blue;">0</span>][i] ) <span style="color: navy; font-weight: bold;">goto</span> next; <span style="color: #008800; font-style: italic;">// Something in the first row</span>
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">4</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r+<span style="color: blue;">1</span>][c];
}
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">5</span>;++c )
{
all_pieces[piece][rotation][<span style="color: blue;">4</span>][c] = <span style="color: blue;">0</span>;
}
--rotation; <span style="color: navy; font-weight: bold;">continue</span>;
next: ;
}
}
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>; piece<<span style="color: blue;">9</span>; ++piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">1</span>; rotation<<span style="color: blue;">4</span>; ++rotation )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>; i<<span style="color: blue;">5</span>; ++i )
{
<span style="color: navy; font-weight: bold;">if</span> ( all_pieces[piece][rotation][i][<span style="color: blue;">0</span>] ) <span style="color: navy; font-weight: bold;">goto</span> next2; <span style="color: #008800; font-style: italic;">// Something in the first column</span>
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>;c<<span style="color: blue;">4</span>;++c )
{
all_pieces[piece][rotation][r][c] = all_pieces[piece][rotation][r][c+<span style="color: blue;">1</span>];
}
}
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>;r<<span style="color: blue;">5</span>;++r )
{
all_pieces[piece][rotation][r][<span style="color: blue;">4</span>] = <span style="color: blue;">0</span>;
}
--rotation; <span style="color: navy; font-weight: bold;">continue</span>;
next2: ;
}
}
}
<span style="color: navy; font-weight: bold;">void</span> display_grid(<span style="color: navy; font-weight: bold;">void</span>)
{
printf(_Bblk<span style="color: blue;">" "</span>_CN<span style="color: blue;">"\n"</span>);
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> row=<span style="color: blue;">0</span>;row<<span style="color: blue;">11</span>;++row)
{
printf(_Bblk<span style="color: blue;">" "</span>_CN);
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> col=<span style="color: blue;">0</span>;col<<span style="color: blue;">11</span>;++col)
{
<span style="color: navy; font-weight: bold;">char</span> c;
c = grid[row][col] + <span style="color: purple;">'0'</span>;
<span style="color: navy; font-weight: bold;">switch</span>(grid[row][col]) {
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">0</span>: c=<span style="color: purple;">' '</span>; printf(_Bwht); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">1</span>:
printf(_Bcyn); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">2</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">3</span>:
printf(_Bblu); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">4</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">5</span>:
printf(_Bmag); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">6</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">7</span>:
printf(_Byel); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">8</span>:
printf(_Bred); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">9</span>:
printf(_Bgrn); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> BORDER: c=<span style="color: purple;">' '</span>; printf(_Bblk); <span style="color: navy; font-weight: bold;">break</span>;
}
printf(<span style="color: blue;">"%c"</span>_CN,c);
}
printf(_Bblk<span style="color: blue;">" "</span>_CN<span style="color: blue;">"\n"</span>);
}
printf(_Bblk<span style="color: blue;">" "</span>_CN<span style="color: blue;">"\n"</span>);
printf(<span style="color: blue;">"\n"</span>);
}
<span style="color: navy; font-weight: bold;">void</span> display_pieces(<span style="color: navy; font-weight: bold;">void</span>)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> piece=<span style="color: blue;">0</span>;piece<<span style="color: blue;">9</span>;++piece)
{
printf(<span style="color: blue;">"Piece %d rotations\n"</span>,piece+<span style="color: blue;">1</span>);
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> row=<span style="color: blue;">0</span>;row<<span style="color: blue;">5</span>;++row)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> rotation=<span style="color: blue;">0</span>;rotation<<span style="color: blue;">4</span>;++rotation)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> col=<span style="color: blue;">0</span>;col<<span style="color: blue;">5</span>;++col)
{
<span style="color: navy; font-weight: bold;">char</span> c;
c = all_pieces[piece][rotation][row][col] ? <span style="color: purple;">'1'</span> + piece : <span style="color: purple;">' '</span>;
<span style="color: navy; font-weight: bold;">switch</span>(all_pieces[piece][rotation][row][col] * (piece+<span style="color: blue;">1</span>)) {
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">0</span>: c=<span style="color: purple;">' '</span>; printf(_Bwht); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">1</span>:
printf(_Bcyn); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">2</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">3</span>:
printf(_Bblu); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">4</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">5</span>:
printf(_Bmag); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">6</span>:
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">7</span>:
printf(_Byel); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">8</span>:
printf(_Bred); <span style="color: navy; font-weight: bold;">break</span>;
<span style="color: navy; font-weight: bold;">case</span> <span style="color: blue;">9</span>:
printf(_Bgrn); <span style="color: navy; font-weight: bold;">break</span>;
default:
printf(<span style="color: blue;">"invalid"</span>); <span style="color: navy; font-weight: bold;">break</span>;
}
printf(<span style="color: blue;">"%c"</span>_CN,c);
}
printf(<span style="color: blue;">" "</span>);
}
printf(<span style="color: blue;">"\n"</span>);
}
}
}
<span style="color: navy; font-weight: bold;">void</span> remove_piece(<span style="color: navy; font-weight: bold;">int</span> piece)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> row=<span style="color: blue;">0</span>;row<<span style="color: blue;">11</span>;++row)
{
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> col=<span style="color: blue;">0</span>;col<<span style="color: blue;">11</span>;++col)
{
<span style="color: navy; font-weight: bold;">if</span> ( grid[row][col] == piece+<span style="color: blue;">1</span> )
{
grid[row][col] = <span style="color: blue;">0</span>;
}
}
}
}
<span style="color: navy; font-weight: bold;">int</span> place_piece_here(<span style="color: navy; font-weight: bold;">int</span> piece,<span style="color: navy; font-weight: bold;">int</span> rotation,<span style="color: navy; font-weight: bold;">int</span> row,<span style="color: navy; font-weight: bold;">int</span> col)
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>; r<<span style="color: blue;">5</span>; ++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>; c<<span style="color: blue;">5</span>; ++c )
{
<span style="color: navy; font-weight: bold;">if</span> ( all_pieces[piece][rotation][r][c] )
{
<span style="color: navy; font-weight: bold;">if</span> ( r+row >= <span style="color: blue;">11</span> || c+col >=<span style="color: blue;">11</span> ) <span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">0</span>; <span style="color: #008800; font-style: italic;">// Off the grid</span>
<span style="color: navy; font-weight: bold;">if</span> ( grid[r+row][c+col] ) <span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">0</span>; <span style="color: #008800; font-style: italic;">// Spot full</span>
}
}
}
<span style="color: #008800; font-style: italic;">// Yes, it goes here; put it in the grid</span>
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> r=<span style="color: blue;">0</span>; r<<span style="color: blue;">5</span>; ++r )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> c=<span style="color: blue;">0</span>; c<<span style="color: blue;">5</span>; ++c )
{
<span style="color: navy; font-weight: bold;">if</span> ( all_pieces[piece][rotation][r][c] )
{
grid[r+row][c+col] = piece+<span style="color: blue;">1</span>;
}
}
}
<span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">1</span>;
}
<span style="color: #008800; font-style: italic;">// Place a piece if possible; return true if placed</span>
<span style="color: navy; font-weight: bold;">int</span> place_piece(<span style="color: navy; font-weight: bold;">int</span> piece)
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> rotation=place[piece][<span style="color: blue;">0</span>]; rotation<<span style="color: blue;">4</span>; ++rotation,place[piece][<span style="color: blue;">1</span>]=<span style="color: blue;">0</span>,place[piece][<span style="color: blue;">2</span>]=<span style="color: blue;">0</span> )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> row=place[piece][<span style="color: blue;">1</span>]; row<<span style="color: blue;">9</span>; ++row,place[piece][<span style="color: blue;">2</span>]=<span style="color: blue;">0</span> )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> col=place[piece][<span style="color: blue;">2</span>]; col<<span style="color: blue;">9</span>; ++col )
{
<span style="color: navy; font-weight: bold;">if</span> ( place_piece_here(piece,rotation,row,col) )
{
place[piece][<span style="color: blue;">0</span>]=rotation;
place[piece][<span style="color: blue;">1</span>]=row;
place[piece][<span style="color: blue;">2</span>]=col;
<span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">1</span>;
}
}
}
}
<span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">0</span>;
}
<span style="color: navy; font-weight: bold;">int</span> main(<span style="color: navy; font-weight: bold;">int</span> argc,<span style="color: navy; font-weight: bold;">char</span> *argv[])
{
(<span style="color: navy; font-weight: bold;">void</span>)argc;(<span style="color: navy; font-weight: bold;">void</span>)argv;
init_border();
init_rotations();
display_pieces();
printf(<span style="color: blue;">"Empty board\n"</span>);
display_grid();
<span style="color: navy; font-weight: bold;">int</span> solutions=<span style="color: blue;">0</span>;
<span style="color: navy; font-weight: bold;">for</span> (<span style="color: navy; font-weight: bold;">int</span> i=<span style="color: blue;">0</span>; i<<span style="color: blue;">9</span>; ++i )
{
<span style="color: navy; font-weight: bold;">if</span> ( place_piece(i) )
{
<span style="color: navy; font-weight: bold;">if</span> ( i == <span style="color: blue;">8</span> )
{
++solutions;
printf(<span style="color: blue;">"Solution %d found:\n"</span>,solutions);
display_grid();
remove_piece(i);
}
<span style="color: navy; font-weight: bold;">else</span>
{
<span style="color: navy; font-weight: bold;">if</span> ( i >=<span style="color: blue;">7</span> && <span style="color: blue;">0</span> ) <span style="color: #008800; font-style: italic;">// debug</span>
{
printf(<span style="color: blue;">"Placed %d pieces:\n"</span>,i+<span style="color: blue;">1</span>);
display_grid();
}
<span style="color: navy; font-weight: bold;">if</span> ( i != <span style="color: blue;">8</span> )
{
<span style="color: navy; font-weight: bold;">for</span> ( <span style="color: navy; font-weight: bold;">int</span> j=<span style="color: blue;">0</span>;j<<span style="color: blue;">3</span>; ++j)
place[i+<span style="color: blue;">1</span>][j]=<span style="color: blue;">0</span>;
}
<span style="color: navy; font-weight: bold;">continue</span>;
}
}
<span style="color: navy; font-weight: bold;">if</span> ( i == <span style="color: blue;">0</span> )
{
<span style="color: navy; font-weight: bold;">if</span> ( !solutions )
{
printf(<span style="color: blue;">"Failed to solve puzzle\n"</span>);
}
<span style="color: navy; font-weight: bold;">break</span>;
}
<span style="color: #008800; font-style: italic;">//printf("Can't place piece %d; remove piece %d\n",i+1,i);</span>
<span style="color: #008800; font-style: italic;">// Advance the previous piece</span>
--i;
remove_piece(i);
<span style="color: #008800; font-style: italic;">// printf("piece %d was at rot,row,col %d,%d,%d\n",i+1,place[i][0],place[i][1],place[i][2]);</span>
++place[i][<span style="color: blue;">2</span>];
<span style="color: #008800; font-style: italic;">// Go back one more as the loop will increment</span>
--i;
<span style="color: #008800; font-style: italic;">// printf("piece %d was at rot,row,col %d,%d,%d\n",i+1,place[i][0],place[i][1],place[i][2]);</span>
}
<span style="color: #008800; font-style: italic;">//display_grid();</span>
<span style="color: navy; font-weight: bold;">return</span> <span style="color: blue;">0</span>;
}
</pre>
</div>
<div>
<br />
Now much to my surprise, once I had debugged it, it ran quite fast. I had guessed that it might run for hours before finding the solution, but it ran to completion in under a minute. The biggest surprise was that it found not one, but eight solutions! I shared my results with the creator of the puzzle. He said he had also used a computer to verify that there was only one solution, but apparently his program had a bug. He has made a slight change to the puzzle, so if you buy it now, it will have one unique solution.<br />
<br />
In case you're interested in buying and playing with the puzzle yourself, I won't spoil it by posting the solution here. It's simple enough to run the program if you want to see them.<br />
<br />
And a note on copyright: While I hold the copyright on all my posts, including the above code, in my opinion, the ANSI color code defines are simple and obvious enough that they can hardly be considered copyrightable, so feel free to use them.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-22145976624511769952015-11-23T12:37:00.000-08:002015-11-23T12:37:41.648-08:00Don't Fix That Bug!<div style="line-height: 100%; margin-bottom: 0in;">
When writing a
program, everyone encounters bugs. Usually the first thing you will
try to do is fix the bugs. Don't do that. Fixing bugs should be the
last thing you do. Yes, you will need to fix them, but it should,
quite literally, be the last thing you do.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Fixing a bug is like
looking for your lost car keys. You always find them in the last
place you look. Why? Well, of course, because you stop looking once
you find them. Unless you then look in several other places just so
you can say it wasn't in the last place you looked.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
The problem with
fixing bugs is that bugs aren't simply a flaw in your code, they're
an opportunity. Especially the interesting bugs. The bugs that take
all day or longer to track down are great bugs. Make good use of
them.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Use your bugs to
make your code more robust. When you have a bug, especially an
interesting bug in a large complicated program, the odds are good
that you will have other similar bugs, either hidden in the code
already, or waiting to be introduced by patches in the future.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Fixing a bug is like
relying on a firewall to provide your security. Sure, a firewall is
important, but anyone who pays attention to security knows that it's
just one aspect of security. Good security has many layers of
protection, because we all know that no one layer of security will be
perfect.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
So face reality.
When you have an interesting bug, it's likely impossible to fix it.
Sure you can probably track it down and eliminate the one instance of
it that has shown up, but like a hydra, it will raise another head
and bite you again, no matter how many you cut off.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<br />
<div style="line-height: 100%; margin-bottom: 0in;">
You can never fix
the bug. So what do you do? You deploy a multi-layered strategy for
dealing with the bug.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<b>Document the
errors.</b></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
When you have an
error, grab as much useful information about what may have caused it
as you can. Put that in an error log or somewhere that you'll have
access to it. And keep in mind that you might not remember what's
going on when you look at the error several years later, so be
verbose with saving the error data. A few minutes invested now
adding a line or two of text and some color-coded formatting can save
hours down the road.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Working with
enterprise-class products, error handling is done at many levels, and
the more interesting the bug is, the more attention should be paid at
each of level.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
If the error happens
in the field, make sure you provide enough information to the
customer that the customer will know what corrective action is
appropriate. Keep in mind that the first thing many people do with
an error message is paste it in to Google to see how others have
dealt with it. With this in mind, make sure all error messages have
unique strings that facilitate searching. You can create web pages
for each error message so that the anyone hitting the bug will find
your documentation. (You can then use the web server logs as an indication of how often different errors are showing up in the field.)</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
If your product can
connect home for support, make sure that you provide documentation
for the product support engineers, so that they know how to handle
the error. In many cases, you'll want them not only to know how to
fix the particular case, but also have them collect enough
information for you to track down and fix that instance of the bug.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<b>Add debugging
tools.</b></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
When this error
happens on a live system, how difficult is it to get the information
that you need to tell what is going on? Can you spend some time now
to make it easier to get that information? There's nothing more
frustrating than having an instance of a difficult-to-recreate bug
show up, and not be able to get the data you need to find out what
caused it.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Again, you need to
have a good mechanism for saving as much information about the state
of the program at the time of the error as possible. A stack trace
is great for many errors. Knowing values of key variables is always
useful.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<b>Render the bug
harmless.</b></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Make your code more
robust so that the entire category of bug is no longer a critical
show-stopper. When this bug trips, have the program detect that
something went wrong and take corrective action.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
I encountered a
recent example of this. I was developing some code roughly analogous
to the code that an operating system uses to suspend to disk when a
laptop is put to sleep. The product needed to handle hardware
failures of the storage medium during the save. I had a memory
corruption bug that was causing writes to occasionally fail. Before
tracking down the bug, I used the random corruption as motivation to
implement the fault handling. By the time I tracked down the actual
memory corruption bug, the code was working correctly despite the
bug. It was very noisy, with lots of errors being reported, but
nothing that stopped the end result from working correctly.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
A similar example
dates back to the 1970s. IBM was putting out their first mainframe
system. They needed it to the most stable computer system ever
built. It wasn't. It crashed all the time. Their solution was to
create a fault-handling system that could catch most of the crashes
and recover them. The result was perhaps the most successful system
ever launched.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<b>If it's the last
thing you do, fix the bug.</b></div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
</div>
<div style="line-height: 100%; margin-bottom: 0in;">
Once you've done
everything to deal with the bug outside of fixing it, fix it. But
don't be surprised if months or years later, you get reports of the
same bug. You only fixed the one instance that triggered. But if
you did things right, it won't be a critical customer issue. No need
to rush a patch out to the field. Just a bit of noise to correct in
the next release.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0tag:blogger.com,1999:blog-5581770500938014748.post-5362447928161054662015-11-14T18:25:00.000-08:002015-11-14T18:25:26.618-08:00Why loopback is 127.0.0.0/8If you've played with networking at all, you should be familiar with 127.0.0.1 being localhost. If you look closely at the network settings, you'll see that this is on a loopback device, and it's configured as a /8 network, not just that one IP address. That means any IP address in the range of 127.0.0.0 through 127.255.255.255 goes to the loopback device. Typically your hosts file only uses one of those addresses, namely the aforementioned localhost.<br />
<br />
So what's the point of having 24-bits of local IP addressing? Isn't that just a waste? Not entirely. It turns out there is at least one very clever trick you can use this for.<br />
<br />
Suppose you have a service running that uses a given port, say port 2159. Now suppose you have that service running on several systems, and you want to use that service locally. Now suppose there's a firewall on those boxes that blocks remote access to port 2159. The obvious solution is to use ssh to forward that port back to the local system. But if you have the same service in use locally, you have to use a different port number. Or if you want to work with more than one remote system at a time, you have to use a different port. This may break your client software that also insists on using port 2159. You can fix this by inserting iptables rules that direct anything going to port 2159 at the remote IP address to instead go to whatever port number you picked locally. That works great, except you have to have root access to set iptables rules, and you need to have your kernel configured with the right iptables options, and you have to clean up all the entries when you close your ssh tunnel (which gets tricky someone just kills the process). This is not a solution that you can deploy as a script for lots of people to use.<br />
<br />
Fortunately, you can use port 2159 locally. The trick is to bind it to a different local IP address. Since we have millions to choose from, not just one, this is easy. Say we wanted to use 10.4.5.6:2159. We set up a ssh tunnel to make that port appear locally on 127.4.5.6:2159. We can do the same for lots of other systems at the same time. No need for root access or any other magic hacks (unless the port number is below 1024).<br />
<br />
So to implement the above example: <br />
<pre> ssh -L 127.4.5.6:2159:127.0.0.1:2159 -o ExitOnForwardFailure=yes \</pre>
<pre> -f -N user@10.4.5.6</pre>
<br />
Now we just tell our program to connect to 127.4.5.6, and it works just like 10.4.5.6 would, only without being blocked by the firewall.<br />
<br />
Interestingly, the designers of IPv6 apparently thought using a /8 for loopback was a waste, so you only get the one IP address there. I haven't worked much with IPv6, though, so there be similar tricks available. In any case, you can still use the local IPv4 space even if the real network is IPv6-only.<br />
<br />
Oh, and in case you're curious, 2159 is the remote GDB debugging port, so I figured it was a good example. I've been using this trick at work with a bunch of similar ports for debugging, much of it using internally developed software that doesn't provide an option for using an alternative port number. While you can make a good argument that all software should allow alternative port numbers (and I would tend to agree), reality is that this is not the case, and this one way of dealing with that.Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com1tag:blogger.com,1999:blog-5581770500938014748.post-43910100366030263352015-11-14T13:05:00.003-08:002015-11-14T13:05:49.520-08:00Introduction<div style="line-height: 100%; margin-bottom: 0in;">
I've been developing
software for over three decades. Half of that professionally. The
rest as a student or as a hobby. Over the years, I've noticed many
things that have been quite valuable for my career, but generally not
things taught as part of a standard curriculum. The purpose of this
blog is to collect various bits of wisdom that will hopefully be of
value to others in the same field, whether professionally or as a
hobby.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
Most of my professional programming has been in C, which a touch of assembly, but I often need to write tools using Bash with heavy lifting from awk and sed to automate things. I'm fairly religious about using Unix (mostly Linux), because it lets me control exactly what I'm doing with my computer.</div>
<div style="line-height: 100%; margin-bottom: 0in;">
<br /></div>
<div style="line-height: 100%; margin-bottom: 0in;">
So I expect this blog will be mostly a mix of C programming, Bash scripting, and Linux tweaking.</div>
Preston Crowhttp://www.blogger.com/profile/12946901695663413109noreply@blogger.com0