Modifying Sets during iteration in ECMAScript 6

I discovered something pleasantly weird while playing with new Javascript features in ES6: You can mutate sets while iterating over their elements.

Sets come with any decent standard library and are useful for quickly keeping track of objects you've seen, holding event handlers, and stripping duplicates from collections (to name a few use cases). Sets are container objects which differ from arrays two ways: 1) They don't store items in any particular order, and 2) They may only contain a given item once.

Because sets are theoretically unordered and usually don't expose their internal data structures, one must use an iterator to list their elements. Most implementations also don't like it when a set changes while iterating over it.

Here is an example in Python:

s = set([1,2, 4,5])
for x in s:
    print x
    if x == 2:
        s.add(3)

It fails with the following message:

user@hostname /tmp $ python test.py 
1
2
Traceback (most recent call last):
  File "test.py", line 2, in 
    for x in s:
RuntimeError: Set changed size during iteration

Here's an equivalent program in Java:

import java.util.*;

public class test {
    public static void main (String[] args) {
        Set s = new HashSet(
            Arrays.asList(1, 2, 4, 5)
        );
        
        for (Integer x : s) {
            System.out.println(x);
            if (x == 2) {
                s.add(3);
            }
        }
    }
}

user@hostname /tmp $ javac test.java && java test
1
2
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
 at java.util.HashMap$KeyIterator.next(HashMap.java:1453)
 at test.main(test.java:9)

Now, let's look at the same code in Javascript:

'use strict';

const s = new Set([1,2, 4,5]);
for (let x of s) {
    console.log(x);
    if (x == 2) {
        s.add(3);
    }
}

karl@charmander /tmp $ node --version
v4.2.2
karl@charmander /tmp $ node test.js
1
2
4
5
3

Not only does the Set iterator not complain, it also iterates over the new element!

I wonder if this is in the Javascript spec, a brilliant piece of engineering on Google's part, or some sort of laziness. Does the Set keep an internal list of all the elements that have been added since iteration began? Or is it lazy, keeping an internal array of its elements and scanning the list in O(n) time as new elements are added?

A Lego/Arduino Game Controller

For my first project on this blog, I present a functioning game controller I built out of Legos.

It all started a few weeks ago when I discovered that someone posted instructions for making an Arduino Uno R3 emulate USB HID devices such as keyboards and mice. I'd been itching to use my Arduino for this kind of thing for awhile now, but while newer model Arduinos like the Leonardo have built-in USB support, I have an older Uno R3. I suppose I could have gone out and bought the newer model, but I'm cheap and like to use what I already have.

Hardware

For the body of the controller, I used Lego because it was convenient, seeing as I don't have access to a shop and I'm not that handy to begin with. (Come soon, ubiquitous 3D printing!)

For grips, I used boat-hull-shaped pieces because they were the most contoured pieces I could find. The breadboard is stuck to a panel of smooth-top plates and held in place with sticky tack (a.k.a. blu-tack). As for the Arduino itself, I discovered that since the PCB slides perfectly between the grooves of 1x2 grate plates, I could basically rack-mount the board without adhesives.

The gamepad buttons are tactile switches that you can find inside many electronic devices. I bought mine from a store, but if I were to do it again I'd buy them in bulk online -- DigiKey sells them for 10 cents apiece. I also tried harvesting buttons from broken electronics. The two black buttons on top are de-soldered from an old Microsoft Mouse. The two bumper buttons have been sitting around in my electronics box for years, but I saw similar ones on DigiKey for around $1 each. I'm sure one can find more appropriate switches for the bumpers.

The wires are held in place with more sticky/blu-tack where appropriate. I tried to keep things as neat as possible by harvesting ribbon cable from and old floppy drive. Unfortunately, the ribbon cable is a thin enough guage that it has trouble making contact with the headers on the Arduino, so I'd recommend anyone using ribbon cables to jam a second wire in along side it to improve the connection.

Warning: technical details ahead

Electrically, each button is hooked up between a pin on the Arduino and ground. The Arduino pins are configured in INPUT_PULLUP mode, meaning that an internal resistor is pulling it to +5V.

For those of you unfamiliar with electronics, the digital I/O pins on an Arduino are capable of either putting out a voltage of +5 volts or 0 volts (commonly refered to as "ground"), or not asserting a voltage and reading the current voltage back in. Whether the voltage is +5V or 0V is interpreted as a logical 0 or 1. Here, I put the Arduino in a hybrid mode where it weakly tries to get the voltage up to +5V, but pressing the button pulls it down to ground, which the Arduino can sense by reading the voltage of the pin. This method is a lot easier than using a two-way switch that sends +5V in one position and 0V in the other.

Software

Software-wise, the computer doesn't think the controller is a controller -- it sees a USB keyboard. This was intentional. Each button corresponds to a key such as WASD, the arrow keys, enter/esc/shift, etc. Emulating a keyboard rather than a USB joystick doesn't lose out on functionality; I use a PC for what little gaming I do, and PC games almost universally support keyboard controls. Not only can I still use the controller for games, I retain the flexibility to use it for other things that support keyboard controls, such as browsing Imgur.

Actually emulating a USB keyboard is pretty tricky to do. It would be easy if I was using an Arduino Leonardo, but I'm not. Whereas the Leonardo uses a single processor to handle USB communication and driving the I/O pins, the Uno's primary processor only communicates in serial; a second processor (an ATmega16U2 or ATmega8U2) translates its serial I/O to USB. Whereas the Leonardo can natively decide how to communicate over USB, the Uno's chip needs to be programmed seperately with a firmware to change its behavior.

Mitchtech's tutorial explains the firmware-updating process but I'll repeat some of the details here in case anything happens to the original post. The second chip is programmed using Device Firmware Update mode, a method of re-programming chips over USB. It can be used by installing the following packages on a Ubuntu/Debian-based Linux distribution:

sudo apt-get install dfu-programmer dfu-utils

Next, one needs the firmware to flash to the Arduino. You actually need two firmwares -- the keyboard emulation firmware and the original stock firmware for programming the Arduino. Due to size limitations of the ATmega16/8U2 chip, the Arduino can't reprogram the main AVR processor and emulate a keyboard at the same time. If you want that, go with the Leonardo. You'll be switching back and forth between the two firmwares a lot.

• Keyboard firmware: Mitchtech's Dropbox link | Google Drive mirror
• Stock firmware: Mitchtech's Dropbox link | Google Drive mirror

Since the Arduino has to be reprogrammed twice every time I want to test the program, I wrote a short script. I put the following in my project folder next to the firmware files:

#!/bin/bash

# Script for flashing the firmware on an arduino uno r3's USB chip (the atmega16u2)
# between emulating a USB serial device and emulating a keyboard.
#
# Usage:
#   ./flashfirmware serial
#       Uploads the usbserial firmware to the Arduino
#
#   ./flashfirmware keyboard
#       Uploads the keyboard emulation firmware to the Arduino
#
# Instructions:
#   Before uploading, make sure that the device /dev/ttyACM0 on your system is
#   set to writable (with "sudo chmod a+w /dev/ttyACM0") and put the Arduino into
#   DFU mode by shorting the two pins closes to the reset button.
#
# Sources:
#
# http://bartruffle.blogspot.com/2013/09/dfu-programming-atmega16u2-on-arduino.html
#   Workaround for an Arduino Uno R3 specifically: You need to connect the two bare
#   pins nearest the reset button momentarily to put the chip into DFU (Device
#   Firmware Update) mode to accept the new firmware.
#
# http://mitchtech.net/arduino-usb-hid-keyboard/
#   Instructions for flashing the Arduino with the new firmware and the download
#   link for the firmware files

set -e

# This is what device the arduino is assigned on my system.
ARDUINO=/dev/ttyACM0

# Paths to the firmware files
SERIAL_FIRMWARE=`dirname $0`/Arduino-usbserial-uno.hex
KEYBOARD_FIRMWARE=`dirname $0`/Arduino-keyboard-0.3.hex

function flash() {
    
    # Sanity check: Verify that the firmware file exists
    if ( cat ${ARDUINO} > /dev/null 2>/dev/null ); then
        echo "!!! ERROR: Cannot read firmware file $1. Aborting."
        return 1
    else
        echo "Going to flash firmware image $1"
    fi
    
    # Check that the Arduino is ready to accept the new firmware
    while [[ true ]]; do
        if ( stat ${ARDUINO} > /dev/null 2>/dev/null ); then
            echo
            echo "The arduino is connected, but the chip is not in DFU mode."
            echo "Please short the two bare pins closest to the reset button"
            echo "and press any key to continue."
            read -n 1
        else
            break
        fi
    done

    # Flash it!
    echo "sudo dfu-programmer atmega16u2 erase"
    sudo dfu-programmer atmega16u2 erase
    echo "sudo dfu-programmer atmega16u2 flash --debug 1 $1"
    sudo dfu-programmer atmega16u2 flash --debug 1 $1
    echo "sudo dfu-programmer atmega16u2 reset"
    sudo dfu-programmer atmega16u2 reset

    echo "Flash succeeded. Please plug-cycle (unplug and plug it back in again)"
    echo "the arduino."

    return 0
}

case $1 in
    serial)
        flash ${SERIAL_FIRMWARE}
        ;;
    keyboard)
        flash ${KEYBOARD_FIRMWARE}
        ;;
    *)
        echo "Usage:"
        echo "    $0 serial"
        echo "        Flashes an arduino with the usbserial firmware."
        echo "        (Needed to reprogram the arduino)"
        echo "    $0 keyboard"
        echo "        Flashes an arduino with the keyboard emulation firmware."
esac

There's one trick about DFU on the R3 -- you need to sort two pins before uploading the firmware. Bart Ruffle's blog explains how to do it -- go look at his diagram.

Anyway, here's the actual program I used:

#define BUTTON_PRESSED  LOW
#define BUTTON_RELEASED HIGH

#define DELTA (4 - 'a')

struct button {
  byte pin;
  byte keycode;
  byte state;
  char name[16];
} buttons[] = {
  { A0, 'q' + DELTA, BUTTON_RELEASED, "left-trigger" }, 
  { A1, 'e' + DELTA, BUTTON_RELEASED, "right-trigger" },
  { A2, 'z' + DELTA, BUTTON_RELEASED, "left-auxiliary" }, 
  { A3, 'c' + DELTA, BUTTON_RELEASED, "right-auxiliary" },
  {  5, 'w' + DELTA, BUTTON_RELEASED, "left-left" },
  {  4, 'a' + DELTA, BUTTON_RELEASED, "left-up" },
  {  3, 's' + DELTA, BUTTON_RELEASED, "left-down" },
  {  2, 'd' + DELTA, BUTTON_RELEASED, "left-right" },
  {  6, 41 /* esc */, BUTTON_RELEASED, "select" },
  {  7, 40 /* ret */, BUTTON_RELEASED, "start" },
  { 11, 80 /* <-- */, BUTTON_RELEASED, "right-left" },
  { 10, 82 /* ^^^ */, BUTTON_RELEASED, "right-up" }, 
  {  9, 81 /* vvv */, BUTTON_RELEASED, "right-down" }, 
  {  8, 79 /* --> */, BUTTON_RELEASED, "right-right" },
};

byte NUMBER_OF_BUTTONS = sizeof(buttons)/sizeof(button);

void getButtonStates()
{
  for(uint8_t i = 0; i < NUMBER_OF_BUTTONS; i++)
  {
    buttons[i].state = digitalRead(buttons[i].pin);
  }
}

void reportKeys()
{
  // Keyboard report buffer - see:
  // - http://mitchtech.net/arduino-usb-hid-keyboard/
  // - http://www.circuitsathome.com/mcu/lightweight-usb-host-part-6-hid << actual explanation
  // - https://github.com/felis/lightweight-usb-host/blob/master/HID.h
  uint8_t buf[8] = {0};
  
  // USB can report the status of up to six keys simultaneously.
  // Their keycodes are stored in bytes 2-7 of the report buffer.
  uint8_t slot = 2;
  uint8_t maxSlot = 8;
  
  for(uint8_t i = 0; i < NUMBER_OF_BUTTONS; i++)
  {
    if(buttons[i].state == BUTTON_PRESSED)
    {
      buf[slot] = buttons[i].keycode;
      
      // Don't report any more key codes if the buffer's filled up
      slot++;
      if(slot >= maxSlot)
      {
        break;
      }
    }
  }
  
  Serial.write(buf, sizeof(buf));
}

void setup()
{
  for(uint8_t i = 0; i < NUMBER_OF_BUTTONS; i++)
  {
    pinMode(buttons[i].pin, INPUT_PULLUP);
  }
  Serial.begin(9600);
}

void loop()
{
  getButtonStates();
  reportKeys();
}

Key presses are sent to the Serial-to-USB chip in buffer specific to the firmware. In the case of the keyboard firmware, an 8-byte buffer is used where the first two bytes are a bitfield for the modifier keys and the remaining six bytes are keycodes as specified in the USB HID usage tables (the keyboard table starts on page 53). It seems that USB keyboards are limited to reporting only six simultaneous keypresses -- it would explain why many mechanical keyboards come with PS/2 adapters to support "N-key rollover" as opposed to "6-key rollover". (I should do more reading on this some time.) Since only six keys are supported, the arduino only reports the first six that it polls. If I ever make this emulate a joystick instead, this issue should go away since joysticks use a separate bit for each button.

Conclusions

I've tried this controller out with Portal 1 and 2, Garry's Mod, Minecraft, and VisualBoy Advance, and my conclusion is that it still needs work. Playing Pokemon feels natural due to the GameBoy exclusively using digital buttons, but anything close to an FPS give me trouble for several reasons

1. Digital buttons don't give enough precision for camera panning. In Portal, I frequently overshot anything I was trying to aim the oculus at; a simple matter of placing a portal in the appropriate spot on the wall took ten seconds because I'd be too high, then too low, and then too high again. I was usually better off just walking and strafing to fine-tune my aim than simply pointing the camera at my target.

2. There simply aren't enough buttons. My controller has 14 buttons on it, counting the two I harvested from the mouse. That's fine for a GameBoy game, but when movement and strafing tie up 6 of those buttons and two are dedicated to bringing up and dismissing the game menu, four buttons just doesn't cut it.

   Even if I had enough buttons, I'm starting to run up against the Arduino's physical limited number of pins. The Arduino has 13 digital I/O pins and 6 additional analog pins which may be used for digital I/O, but pins 0 and 1 are already used for communicating with the computer and pin 13's hard-wired LED messes with INPUT_PULLUP mode. Working around pin 13's limitations, that means I can only put 3 more buttons on my controller.

3. Portal and Garry's mod have terrible keyboard support for camera control. You can turn right and left just fine, but the Source engine requires you to disable mouse looking in order for looking up and down to work. Worse, while I could get Portal 2 to work the older games, Portal and GMod, refused to listen to the game pad. Seems like a dumb decision in the first place.

Despite its faults, I'm glad with how it turned out. The controller is completely customizable; the grips can be switched out at will and the buttons can be remapped to anything I want. I learned more about both electronics and microcontrollers in the process, and I found an excuse to pull out a soldering iron for only the second time in my life.

Besides, I find it addicting to just sit there and push buttons on the controller, even if they're not connected to anything!

Future work

It's obvious that if I want to use this controller for anything other than GameBoy games, I need to add analog sticks. I've already ordered and received a pair of joystick potentiometers, and once I figure out how to integrate them into the controller I'll try and write another post. Joysticks use fewer I/O pins than buttons since each axis is represented by a single, variable voltage rather than a pair of buttons. They also contain built-in buttons that may be activated by pushing the joystick.

The other thing I'll need to do is use a gamepad firmware instead of emulating a keyboard so I can send the state of the thumb sticks -- keyboards don't report analog values! I'll lose the ability to use it to lazily browse Imgur, but I could always install a utility that maps gamepads to mouse and keyboard movements.

What is this?

I guess I should write some sort of introduction as a first post. I don't want to write a long one, though, so I'll keep it short.

This blog is simply a place to write-up the various projects I work on in my free time. There are a couple reasons why I'm choosing to post them on the Internet rather than a couple Word docs on my PC, though:

1. Writing about my projects online lets me describe them in more detail than can fit in a post on a social networking site like Facebook; if I want to show friends and family what I'm doing, I can just link them here.

2. Things in the Cloud are less likely to be lost from hard drive failures. (That said, they're more likely to be lost from services closing down. *Shrugs* It's a gamble.)

3. I've learned a lot from reading other people's posts on various websites. Starting a blog is an opportunity to give back.

So, without further adieu, my project log blog.