Wayne and Layne

Perl and CPAN

Perl is a scripting language. Some people really like it. I have my own feelings about it, but that’s for another day. Perl has a system to install add-on modules called CPAN, that competes and conflicts with the native package manager on a Linux install, but sometimes the only way to install a random package is to use CPAN. Here’s a quick little guide on how to do that. Standard disclaimers apply.


sudo perl -MCPAN -e shell
install Bundle:CPAN
(press enter a bunch of times to allow CPAN to access the web and do updates)
reload cpan
install Module::Whatever


Repeat that last line for each package the perl script requires. Takes a lot of trial-and-error to find all the packages you need to install. Good luck.

Two Generals’ Problem

In computing, the Two Generals’ Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. It is related to the more general Byzantine Generals’ Problem (though published long before that later generalization) and appears often in introductory classes about computer networking (particularly with regards to the Transmission Control Protocol), though it can also apply to other types of communication. Some authors also refer to this as the Two Army Problem or the Coordinated Attack Problem.

via Two Generals’ Problem – Wikipedia, the free encyclopedia.

Mel Kaye

In programming folklore Mel Kaye is an archetypical Real Programmer. Kaye was formerly a programmer at Royal McBee Computer Corporation. Ed Nather’s “The Story of Mel” details Mel’s prowess at programming. Although originally written in prose, Nather’s story was repeatedly distributed by email — the resulting wrapped lines were taken to be free verse, and were kept in this form at many sites.

According to the Jargon File appendix where the story may be found, Kaye is (or was) indeed a real person. In a FOLDOC document he is credited with doing the “bulk of the programming” on the Royal McBee LGP-30 computer. In Nather’s story, Kaye is portrayed as being prone to avoiding optimizing assemblers in favor of crafting code to take advantage of hardware quirks, for example taking advantage of the rotation of the LGP-30’s drum memory to avoid writing delay loops into the code. The story as written by Nather involved Kaye’s work on porting a blackjack program from the LGP-30 to a newer Royal McBee system; company sales executives had requested the installation of a cheat code allowing the customers to always win the game, a request that Kaye reluctantly acceded to, but accidentally changed the odds in favor of the dealer rather than the player. Subsequent to Kaye’s departure, Nather examined the code and found out that an apparent infinite loop had in fact been coded in such a way as to take advantage of a carry-overflow error, causing program control to shift past the loop to a jump instruction.

via Mel Kaye – Wikipedia, the free encyclopedia.

Real Programmer

The term Real Programmer is a term used in computer programmers’ folklore to describe the archetypal “hardcore” programmer. A real programmer eschews modern or graphical tools such as integrated development environments or languages other than assembly language or machine code in favor of more direct and efficient solutions – closer to the hardware.

The term is often used to describe a more bare metal way of doing something – for example: “Real Programmers don’t use IDEs, they write programs using cat > a.out” (that is, they write machine-readable binary files from beginning to end without making any mistakes). Each generation tends to slightly redefine a Real Programmer, as coding techniques change. For instance, a young Java programmer might refer to an older C programmer as being a Real Programmer. In turn, these C programmers refer to older Assembler programmers in the same way.

The archetypal Real Programmer is Mel Kaye of the Royal McBee Computer Corporation who is immortalised in “The Story of Mel“, one of the most famous pieces of hacker folklore. As the story infamously puts it, “He wrote in machine code – in raw, unadorned, inscrutable hexadecimal numbers. Directly.

via Real Programmer – Wikipedia, the free encyclopedia.

Cross-platform animation of still frames with MEncoder

Many times I’ve needed to take a series of still frames and create a video file to view them as an animation. Sometimes the images come from a simulation, and sometimes the images are from a video editing project where I had to edit individual frames. Regardless, I’ve spent a while searching for the best magic codes to provide to MEncoder to produce a universally compatible output video. I’ve tested video files created this way and they worked in QuickTime on OSX 10.6, Totem on Ubuntu Linux 9.10 (with the ubuntu-restricted-extras codec pack installed), and Windows XP with the K-Lite codec pack installed. Let me know if files produced this way don’t work for your system.

Since MEncoder’s default and preferred container format is AVI, I used that instead of MPEG. I used the default mpeg4 code, which should be a recent DivX or XviD codec, widely available on all common operating systems. I used MP3 encoding for the audio, sourced from a standalone .wav file created separately for this animation.

mencoder mf://*.png -mf fps=25:type=png -ovc lavc -lavcopts vcodec=mpeg4 -audiofile audio.wav -oac mp3lame -o output_video.avi

Build an AVR-GCC Toolchain

The main benefit of using Atmel’s line of AVR microcontrollers is the well established avr-gcc toolchain, based on the free and open source gcc compiler. There is a nicely packaged distribution for Windows, but nothing nice for Linux users. Given that a compiler toolchain is fairly important, I thought I should try building my own. Reproduced below are my notes from installing all the components of the avr-gcc toolchain.

Click through for a detailed guide on how to download, compile, and install the necessary tools to get an avr-gcc toolchain going with Linux. Also includes a link to download the completed package to save yourself the time of building the toolchain from scratch, if you want.

http://www.mbeckler.org/microcontrollers/avrgcc_build/

CORDIC

CORDIC (digit-by-digit method, Volder’s algorithm) (for COordinate Rotation DIgital Computer) is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions. It is commonly used when no hardware multiplier is available (e.g., simple microcontrollers and FPGAs) as the only operations it requires are addition, subtraction, bitshift and table lookup.

The modern CORDIC algorithm was first described in 1959 by Jack E. Volder. It was developed at the aeroelectronics department of Convair to replace the analog resolver in the B-58 bomber’s navigation computer, although it is similar to techniques published by Henry Briggs as early as 1624. John Stephen Walther at Hewlett-Packard further generalized the algorithm, allowing it to calculate hyperbolic and exponential functions, logarithms, multiplications, divisions, and square roots.

Originally, CORDIC was implemented using the binary numeral system. In the 1970s, decimal CORDIC became widely used in pocket calculators, most of which operate in binary-coded-decimal BCD rather than binary. CORDIC is particularly well-suited for handheld calculators, an application for which cost (eg, chip gate count has to be minimised) is much more important than is speed. Also the CORDIC subroutines for trigonometric and hyperbolic functions can share most of their code.

CORDIC is generally faster than other approaches when a hardware multiplier is unavailable (e.g., in a microcontroller based system), or when the number of gates required to implement the functions it supports should be minimized (e.g., in an FPGA). On the other hand, when a hardware multiplier is available (e.g., in a DSP microprocessor), table-lookup methods and power series are generally faster than CORDIC. These days, CORDIC algorithm is used extensively for various biomedical applications, especially in the FPGA domain.

via CORDIC – Wikipedia, the free encyclopedia.

Easily capture a background process’s PID

If you’ve ever worked with the dd command to move data around in bulk, you know that to keep tabs on the data transfer you need to send a signal to it’s process ID (PID). One easy way to capture the PID is to use the Bash shell’s secret code $! which is the PID of the last job sent to run in the background. This is also useful for capturing a job’s PID programatically when spawning background jobs from a script.

$ dd if=/dev/hda of=/dev/hdb &
$ pid=$!

Then, you can use the pid variable to work with that job. Here, with dd we can ask it how far the transfer is towards completion:

$ kill -USR1 $pid
1337+0 records in
1337+0 records out

Controlled Parallel Processing with Bash

OMG parallel processing! If you’re not interested in teaching yourself the glory and torture that is pthreads, but still have a lot of jobs to run, you might be interested in this. Frequently I need to do explorations of a design space by tuning different parameters and running a simulation, which makes for a lot of simulation runs. With all the multi-core machines available nowadays, it’s nice to run lots of jobs in parallel to reduce the waiting time, but you don’t want to run more jobs than available cores. This script will allow you to run as many jobs in parallel as you want, and starting the next job as soon as a running job finishes.

#!/bin/bash

# put the first character in square brackets,
# to prevent the grep command from showing up
# in the process list with the same string as the program
PROGNAME_REGEX="[m]y_prog"

# set this equal to the number of cores, or however many
# jobs you want to run concurently
MAXJOBS="4"

for i in `seq 1 10`; do
    # while we are running the max number of jobs, wait here
    while [ `ps aux | grep $PROGNAME_REGEX | wc -l` -ge $MAXJOBS ]; do
        sleep 1
    done

    # You can use the parameter $i to change the behavior or
    # settings of your executing program
    # The & at the end starts this program in the background
    ./my_prog $i &
done

This might not work as well if your program’s name is something generic like, say, a.out, or MATLAB, so you might have to be more creative in the line that check how many jobs are running. Maybe change the ps command to only include processes belonging to your username, or do something fancy with the grep line.

Python version of seq for OSX

OSX is based on BSD, so it is missing some of the standard GNU utilities we’ve come to expect on a linux-y system. The most frequently used of these missing utilities is the seq utility, which is used to define a range of numbers, very useful in quick loops from the command line:

$ seq 6 12
6
7
8
9
10
11
12

You can also use the -w flag to get zero-padded output:

$ seq -w 6 12
06
07
08
09
10
11
12

The nearest BSD equivalent is something called jot which of course has more functionality but is not compatible with good old seq. I wrote a quick and dirty python script to emulate the simple behaviors of seq, specifically the base counting behavior and the -w behavior. Put it somewhere on your path (I’d suggest ~/bin/) and you should be good to go:

#!/usr/bin/env python

import sys, math

if len(sys.argv) < 3:
    print "Usage: %s [-w] min max" % sys.argv[0]
    sys.exit(1)

try:
    if len(sys.argv) == 4:
        wide = True
        min = int(sys.argv[2])
        max = int(sys.argv[3])
    else:
        wide = False
        min = int(sys.argv[1])
        max = int(sys.argv[2])
except:
    print "Error: min and max must be integers"
    sys.exit(1)

width = int(math.ceil(math.log10(max)))

for i in range(min, max + 1):
    if wide:
        print "%0*d" % (width, i)
    else:
        print "%d" % i