Tag Archives: c

Luxeed LED Keyboard Driver for Linux


Hardware Review

This is a really cool keyboard, except that the ESC and function keys do not light up and are strangely located and difficult to press. I also don’t understand why the spacebar does not light up; seems like it’s the most important key. The construction is not very good and the feel is a bit mushy. However, this keyboard is fun for hacking and could be really great for user training.

Device Driver and Source Code

After much troubleshooting, I have created a simple C driver library for the Luxeed deTA 100/200 keyboard using libusb. This driver allows the LEDs under each key to be set from C from most Unix-like operating systems. This is my first attempt at reverse-engineering the protocol of a USB device.

Source is located here: http://github.com/kstephens/luxeed/tree/master

Overview

There is a user-space single-threaded, non-blocking I/O daemon using libevent that accepts multiple TCP connections on port 12345 to execute pixel update commands. I’ve been able to get time between frames down to 0.025 seconds.

Commands

Commands sent from clients via TCP to the server:

set <RED> <GREEN> <BLUE> <KEY>...
update
wait <SECONDS>
get <KEY>

Keys can be specified using names (e.g.: “TAB”, “LSHIFT”, “A”), key IDs (e.g. “#20” same as “Y”) or positions relative to the top-left corner (e.g.: “2@1” same as “W”). The “get” command returns the current color of a key. The key colors are atomically uploaded to the keyboard with “update” command.

Building and Running the Server

 > cd luxeed/src
 > make install-prereqs
 > make
 > sudo ./luxeed --server & # start the server

Basic Commands

Make the number keys light up blue:

 > netcat localhost 12345
set 00 00 ff 1 2 3 4 5 6 7 8 9 0 
update
^D

Simple client that flashes keys:

 > sudo ./luxeed --server & # start the server
 > cat flash_keys 
#!/bin/bash

t=0.5
c="ff ff ff"
c2="00 00 00"
while [ $# -gt 0 ]
do
  case "$1"
  in
    -t)
      t="$2"; shift 2
    ;;
    -c)
      c="$2"; shift 2
    ;;
    -c2)
      c2="$2"; shift 2
    ;;
    *)
      break
    ;;
  esac
done
keys="$*"

while true
do
  netcat localhost 12345 <<END
set $c $keys
update 
wait $t
set $c2 $keys
update 
wait $t
END
done 
 > ./flash_keys ENTER # flash the ENTER key

Since the server can service multiple clients, we can flash multiple keys at different rates and colors using multiple clients:

  > ./flash_keys -t 0.2 -c 'ff 00 00' TAB &
  > ./flash_keys ENTER &

Maybe it’s time for a demo video.

Things left:

  • Pausing updates to the keyboard for a short time period after any keypress would allow animations but not let them interfere with the typist. The keyboard I/O channel is too slow to handle typing and animations (~10 frame/sec) at the same time.
  • A bulk update command that maps a PNM image representing the keyboard would be helpful.
  • udev rules to prevent the need for running the server as root.
  • Debian packaging.

There are some I/O throttling issues; sometimes the keyboard disconnects (or requires a power cycle) if data is sent to it too quickly. The only message I could decipher is a bulk keyboard update message of 5 65-byte blocks with an embedded checksum. Maybe there is a smaller differential update payload that will only update specific keys which would be more useful for faster animation. There may be a response message that needs to be read.

If you have this keyboard, give it a try!

Ruby Internals: Why RUBY_FIXNUM_FLAG should be 0x00

Type tags in MRI Ruby VALUE

Internally, values in MRI Ruby are 32-bit (at least for 32-bit processors). Some of the least-significant bits are used to store type information. See the VALUE definition in include/ruby/ruby.h. Using type tag bits avoids allocating additional memory for commonly-used immutable values, like integers.

Ruby uses a single-bit tag of 0x01 as the Fixnum type tag. The remaining bits, are used to store the Fixnum’s signed value. This is an immediate value; it doesn’t require storage for the Fixnum value to be allocated, unlike the heap space that would be required for a String. Other types will use different tag bits.

Since Ruby uses 31 bits to store the Fixnum’s value, all the other types use 0 for least-significant bit; Ruby uses dynamic length tags:

 3         2         1
10987654321098765432109876543210 bit index 
--------------------------------
sxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1 Fixnum
00000000000000000000000000000000 false
00000000000000000000000000000010 true
00000000000000000000000000000100 nil
00000000000000000000000000000110 undef
xxxxxxxxxxxxxxxxxxxxxxxx00001110 Symbol
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0x0 All other types

A non-zero Fixnum type tag requires that the tag must be masked or shifted away on Fixnum operands before numeric operations. In a running program, Fixnum is probably the most common numeric type and quite possibly the most common type of all; it makes sense to make the most common operations on Fixnum: +, -, *, / as fast and as simple as possible. It’s also likely that addition is the most common operation applied to Fixnum.

Imagine the following bit of Ruby code:

x = 1
y = 3
puts x + y

Internally, INT2FIX(X) is used to create a Ruby value from a C int X:

#define INT2FIX(X) (((X) << 1) | RUBY_FIXNUM_FLAG)
#define FIX2INT(X) ((X) >> 1)

Thus:

INT2FIX(1) => 3
INT2FIX(3) => 7

FIX2INT(X) shifts one bit down which removes the tag and returns the original integer.

To compute x + y, Ruby internally, in numeric.c: fix_plus(), does the following:

x + y                             =>
INT2FIX(FIX2INT(x) + FIX2INT(y))  =>
((3 >> 1) + (7 >> 1)) << 1 | 1    =>
9

FIX2INT(9)                        => 
(9 >> 1)                          =>
4

If a type-tag of 0x00 was used for Fixnums, there is no tag to remove and addition or subtraction on Fixnums requires no tag manipulations. Assume:

#define INT2FIX(X) ((X) << 1)
#define FIX2INT(X) ((X) >> 1)

The Ruby expression x + y would simply be x + y in C code, assuming no underflow or overflow into Bignum.

Multiplication with zero Fixnum tags is very simple: only one of the operands needs to be shifted down:

#define FIXMUL(X, Y)((X) >> 1) * (Y))

Fixnum division: the result of the division is shifted up:

#define FIXDIV(X, Y) (((X) / (Y)) << 1)

Two-bit type tags on 32-bit architectures

Oaklisp and LL (http://kurtstephens.com/pub/ll/) use 2-bit tags for all values. LL uses the following tag scheme:

 3         2         1
10987654321098765432109876543210 bit index 
--------------------------------
sxxxxxxxxxxxxxxxxxxxxxxxxxxxxx00 <fixnum>
pppppppppppppppppppppppppppppp01 <locative>
seeeeeeeemmmmmmmmmmmmmmmmmmmmm10 <flonum>
pppppppppppppppppppppppppppppp11 All other types

Floating-point (<flonum>) values are C floats which sacrifice the 2 least-significant mantissa bits for the type tag. Locatives are safe pointers to other values. Oaklisp stores floating-point values as allocated objects and uses a tag for other common immediate values: characters, etc.

The rationale for choosing a fixed-size lower 2-bit type tag, opposed to a dynamic-length type tag, as in Ruby, or high-bit tags, like some older Lisp implementations, is as follows:

C compilers and dynamic memory allocators will align allocations to word boundaries for performance reasons, so there cannot not be a pointer to an object that would require some of the lower bits of a pointer, except for sub-word access, e.g.: char *. 32-bit words are 4 bytes long; the lower 2 bits of any object pointer will always be zero, and are free to be used for type tagging.

If references to allocated objects are encoded using a 0x03 type tag, tag removal could be:

  #define RBASIC(X) ((struct RBasic*)((X) - 3))

Assuming that most of the time the interpreter is referencing structure members of the object, and does not need the actual address of the object:

  struct RBasic {
      VALUE flags; /* struct offset: + 0 */
      VALUE klass; /* struct offset: + 4 */
  };

  RBASIC(X)->klass =>
  ((struct RBasic*)((X) - 3))->klass

C compilers convert the pointer->member expression into an offset from an address. For 32-bit VALUEs:

  RBASIC(X)->flags => *(VALUE*)((X) - 3 + 0)
  RBASIC(X)->klass => *(VALUE*)((X) - 3 + 4)

Using subtraction as the tag removal operation, instead of (X & ~3),
allows the C compiler to constant fold the tag removal and the structure offset:

  RBASIC(X)->flags => *(VALUE*)((X) - 3)
  RBASIC(X)->klass => *(VALUE*)((X) + 1)

Therefore, there is no additional tag removal cost to reference structure members with non-zero offsets. One could reorder the members depending on which is “hotter”.

Research shows that tag manipulation is a heavy cost, esp. for numerics; any tagging scheme should be as simple and consistent as possible.

For example, determining the class of a VALUE could be inlined:

  #define CLASS_OF(v) ((v) & 3) ? RBASIC(v)->klass : rb_cFixnum)

Two-bit tags naturally align with word boundaries on 32-bit processors. Thus, zero tags for integers on 32-bit processors allows pointer arithmetic on VALUE*, as in the Array#[] method, to require no tag manipulation or multiplication to offset into the allocated Array’s elements.

Thanks to Gary Wright for inspiring me to write about this.