Without further ado… if you want code to implement this:
You can download this this zip file. Do with it what you will.
Category Archives: Computer Science
Crazy programming experiment of the evening…
I was struck by the lunatic programming muse again today. While reading my twitter feed, I encountered a description of SmoothLife, a generalization of Conway’s classic Game of Life. Instead of being implemented on a grid of discrete binary values, SmoothLife is implemented over a continuous, real valued field. What’s kind of neat is that “gliders” exist in this world, but unlike the discrete version, they can travel at any angle. I found it really intriguing. Witness!
Pretty neat organic shapes.
In reading up on how this works, I discovered that the implementation was unusual in a way I had not considered. It dawned on me that it would be possible to implement the “summation of neighbors” part of Conway’s life using a simple convolution. As a bonus, we’d get the “wrap around” for free: the indexing would be pretty simple. I hypothesized that I could write it using the fftw library in just a few hundred lines. So I did.
Here’s the code!
[sourcecode lang=”c”]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <complex.h>
#include <unistd.h>
#include <fftw3.h>
#define SIZE (512)
#define SHIFT (18)
fftw_complex *filter ;
fftw_complex *state ;
fftw_complex *tmp ;
fftw_complex *sum ;
int
main(int argc, char *argv[])
{
fftw_plan fwd, rev, flt ;
fftw_complex *ip, *jp ;
int x, y, g ;
srand48(getpid()) ;
filter = (fftw_complex *) fftw_malloc(SIZE * SIZE * sizeof(fftw_complex)) ;
state = (fftw_complex *) fftw_malloc(SIZE * SIZE * sizeof(fftw_complex)) ;
tmp = (fftw_complex *) fftw_malloc(SIZE * SIZE * sizeof(fftw_complex)) ;
sum = (fftw_complex *) fftw_malloc(SIZE * SIZE * sizeof(fftw_complex)) ;
flt = fftw_plan_dft_2d(SIZE, SIZE,
filter, filter, FFTW_FORWARD, FFTW_ESTIMATE) ;
fwd = fftw_plan_dft_2d(SIZE, SIZE,
state, tmp, FFTW_FORWARD, FFTW_ESTIMATE) ;
rev = fftw_plan_dft_2d(SIZE, SIZE,
tmp, sum, FFTW_BACKWARD, FFTW_ESTIMATE) ;
/* initialize the state */
for (y=0, ip=state; y<SIZE; y++) {
for (x=0; x<SIZE; x++, ip++) {
*ip = (fftw_complex) (lrand48() % 2) ;
}
}
/* initialize and compute the filter */
for (y=0, ip=filter; y<SIZE; y++, ip++) {
for (x=0; x<SIZE; x++) {
*ip = 0. ;
}
}
#define IDX(x, y) (((x + SIZE) % SIZE) + ((y+SIZE) % SIZE) * SIZE)
filter[IDX(-1, -1)] = 1. ;
filter[IDX( 0, -1)] = 1. ;
filter[IDX( 1, -1)] = 1. ;
filter[IDX(-1, 0)] = 1. ;
filter[IDX( 1, 0)] = 1. ;
filter[IDX(-1, 1)] = 1. ;
filter[IDX( 0, 1)] = 1. ;
filter[IDX( 1, 1)] = 1. ;
fftw_execute(flt) ;
for (g = 0; g < 1000; g++) {
fprintf(stderr, "generation %03d\r", g) ;
fftw_execute(fwd) ;
/* convolve */
for (y=0, ip=tmp, jp=filter; y<SIZE; y++) {
for (x=0; x<SIZE; x++, ip++, jp++) {
*ip *= *jp ;
}
}
/* go back to the sums */
fftw_execute(rev) ;
for (y=0, ip=state, jp=sum; y<SIZE; y++) {
for (x=0; x<SIZE; x++, ip++, jp++) {
int s = (int) round(creal(*ip)) ;
int t = ((int) round(creal(*jp))) >> SHIFT ;
if (s)
*ip = (t == 2 || t == 3) ;
else
*ip = (t == 3) ;
}
}
/* that’s it! dump the frame! */
char fname[80] ;
sprintf(fname, "frame.%04d.pgm", g) ;
FILE *fp = fopen(fname, "wb") ;
fprintf(fp, "P5\n%d %d\n%d\n", SIZE, SIZE, 255) ;
for (y=0, ip=state; y<SIZE; y++) {
for (x=0; x<SIZE; x++, ip++) {
int s = ((int) creal(*ip)) ;
fputc(255*s, fp) ;
}
}
fclose(fp) ;
}
fprintf(stderr, "\n") ;
return 0 ;
}
[/sourcecode]
Pardon the slightly odd code, but I wrote it while watching the VP debates and the last of the Game 5 between Detroit and the Athletics. (Thanks to the Athletics for a great season!)
It’s kind of a ridiculous way to implement Conway’s Life (there are more efficient and compact implementations), but it has one interesting feature that SmoothLife (or any other discrete life with larger neighborhoods) would use: the run time doesn’t increase with increasing size of neighborhood. I’ll try to work up a SmoothLife implementation soon.
It was just a bit of thought provoking fun, like my previous attempts at implementing bignum arithmetic with the FFT.
Addendum: Each frame (512×512 resolution) takes about 48ms on my MacBook. Not really competitive with more conventional implementations, but not miserable either.
Fourier Volume Rendering
Three years ago, I wrote a short post about volume rendering. I always meant to follow up, because I finally sorted out the problems with generating multiple, overlapping images. Here’s a new video generated with the improved code:
Fourier volume rendering is less flexible than raytracing, but it does have certain computational advantages, most notably in that you can generate images in less than O(n^3) time, which is the typical bound for conventional raytracing. It also has some applications in light field refocusing applications. But overall, I still thing that raytracing has a number of advantages. Perhaps that would make a good first serious Go program? I’ll ponder it more.
The Beaglebone: an $89 Time Machine…
A DEC SYSTEM 10, just like the computers of my past.
But what to do with it? Well, it boots Linux off the SD card, so I could do anything with it that I could do with a Linux machine. I’ve mused about my computing past before on this blog. So, I thought: “let’s see if I can get simh installed on it, and simulate the PDP-10/DEC 1091 of my computing past.
It’s frankly pretty trivial to do. It’s got gcc and wget installed, so all you have to do is fetch the source and compile it. You might want to get the pcap library installed so you can do simulated networking, and the machine itself is pretty slow (I discovered that when it’s powered from the USB, it runs at only 500Mhz, which seems really slow). But there is no trouble getting it installed. Then, all you need is some software to run on it.
In my previous excursion into the world of simh, I worked through installing TOPS-10 from scratch, but I didn’t feel like stumbling through that process again, so I searched the web and found a prebuilt image suitable for use. I downloaded it, unpacked it, and ran pdp10, starting it just as documented.
And… I was again hurled back through time. BASIC, COBOL and FORTRAN. 36 bit architecture. Craziness. Running on $89 worth of hardware, consuming 1W and the size of an Altoids tin.
I haven’t benchmarked it, but I suspect that it runs several times as fast as the original machine. I configured it to allow one to telnet into the server to simulate serial connections. I’m sure with a little work, I could dust off the corner of my brain that held information about this stuff, and figure out how to get ADVENTURE running.
And then I thought to myself: what if I wanted to hook real serial terminals to it? A little investigation reveals that the Beaglebone has six hardware UARTs. One is dedicated for connection via USB, but four are wired to expansion pins. I dug a little more, and uncovered this awesome project: the DECbox. The author mounted a beaglebone inside of a vintage DEC VT100. He even talks about modifying the VT100 to have serial connectors on the back so you can hook in additional terminals. Since the Beaglebone can simulate a wide variety of DEC machines, you could have a PDP-8, PDP-10 or PDP-11 all inside the same space.
Very cool. I’ll be keeping my eye out for a real VT100.
Addendum: in my spare time, I downloaded an image for the Gingerbread release of the Android OS. Because the Beaglebone doesn’t have a display, you start a VNC server which serves as a virtual graphics device, and then connect to it via a VNC client like TightVNC (for Windows) or Chicken of the VNC (for Mac OS X). I did this more for curiousity than anything else: it’s too slow to really be an adequate demo platform. But it might be of interest.
Gingerbread Android, running on the Beaglebone and viewed using Chicken of the VNC.
Addendum2. I was digging around to find power requirements for the board. It turns out that if you don’t use the onboard USB, the current is supposed to be around 170ma, which makes the power less than 1W. But using the USB raises that a lot: the peak is almost 500ma during boot, which is about 2.5W. If you are concerned about power, ditch the USB as a power source.
Russ Cox muses about Fields and Reed-Solomon codes
I’ve been pretty interested in codes of all sort, both the cryptographic codes and the codes that are used to provide error detection and correction. While I’ve played around quite a bit with convolutional codes, I haven’t really every bothered to develop more than a cursory understanding of the Reed-Solomon error correcting codes which have widely applied in many applications such as data storage (most notably for compact discs) and satellite data transmission. It’s very cool technology.
Luckily, super smart guy Russ Cox has a very nice writeup on the theory and practice of Reed Solomon codes. Previously Russ had postings about fast regular expression matching which you might have read (or should have). I really like his postings: he has a very clear, pragmatic but not dumbed-down approach to both the theory and practice of programming. This series promises to go on in future postings, I’ll be eagerly awaiting future installments.
A Tale of Two Gadgets: the TonidoPlug 2 and a Bus Pirate…
A few days ago, I mentioned that one of my servers had died. I spent some time thinking about how I would replace it. I like having a 24/7 hooked up to the Internet to serve as a file drop and a place where I can use SSH to connect to other devices on my home network, but the machine need not be hugely fast, and it would probably be better if it were fairly low power. My previous server drew about 30 watts, and I suspected that I could get something more compact and lower power to replace it.
So, I ordered a TonidoPlug 2. It’s a cute little server based upon the Sheeva Plug computer concept, but includes space to insert a 2.5″ SATA laptop drive. It has all sorts of “personal cloud” applications running on it, which I had no interest in, but doing a bit more research, I found that I could install ArchLinux on the internal hard drive, and it would boot to that automatically. Cool, think I. I ordered mine off Amazon.
It arrived yesterday. I powered it up, verified that it worked in its default configuration, then proceeded to follow the directions on the ArchLinux ARM page. Upon reboot… not good. I ended up with a flashing red LED, and the network never comes back up. So, I pulled the internal drive, and it reboots back to its default configuration.
I then start tracking through various support and Wiki links. I find that some people have had difficulty booting from the internal drives, and the Tonido support guys have been very coy, claiming that “we don’t support that”. Frown. Not good.
But in doing this research, I found that it was possible to access the boot loader and serial console. On the bottom side of the tonido is a nice little rubber cover, concealing 4 pins. Most people seem to make a small adapter to use an FTDI-serial adapter cable with it (the six pin ones like you would use for the Arduino), but I had a Bus Pirate sitting around, and I thought that it might work. And… it did!
In case anyone else (or me in the future) wants to know how to do this:
- The four pins are Vcc, Rx, Tx, and GND, starting from the power supply side and working toward the USB/Ethernet cable side.
- I just hooked up MOSI to RX, MISO to TX, and GND to GND
- To use the Bus Pirate with my Mac laptop, I like to use GNU screen. If you run “screen /dev/tty.usbserial-AH00MPIK 115200” (your tty device will likely be different), it makes a convenient terminal emulator. From there, you can access the Bus Pirate, configure it in UART mode with a baud rate of 115200 and sensible other defaults.
- You can then use the Bus Pirate as a UART bridge by invoking the “(1)” macro. You’ll then essentially be talking directly to the Tonido via the BusPirate.
- Using screen’s C-a H command, you can start a log file, which will record all the output from the serial port. Doing the command again will stop logging.
Hooking it up, I got lots of cool info from the Tonido:
__ __ _ _
| \/ | __ _ _ ____ _____| | |
| |\/| |/ _` | '__\ \ / / _ \ | |
| | | | (_| | | \ V / __/ | |
|_| |_|\__,_|_| \_/ \___|_|_|
_ _ ____ _
| | | | | __ ) ___ ___ | |_
| | | |___| _ \ / _ \ / _ \| __|
| |_| |___| |_) | (_) | (_) | |_
\___/ |____/ \___/ \___/ \__|
** MARVELL BOARD: DB-88F6282A-BP LE
U-Boot 1.1.4 (Sep 13 2011 - 13:25:05) Marvell version: 3.4.27
USISH-SMB Ver: topkick1281p2-001-008-20110913-codelathe
U-Boot code: 00600000 -> 0067FFF0 BSS: -> 006D0120
Soc: MV88F1155 Rev 1 (DDR2)
CPU running @ 800Mhz L2 running @ 400Mhz
SysClock = 400Mhz , TClock = 200Mhz
DRAM unknown CAL tRP = 8 tRAS = 20 tRCD=8
DRAM CS[0] base 0x00000000 size 512MB
DRAM Total size 512MB 16bit width
Addresses 8M - 0M are saved for the U-Boot usage.
Mem malloc Initialization (8M - 7M): Done
NAND:512 MB
Flash: 0 kB
CPU : Marvell Feroceon (Rev 1)
Streaming disabled
Write allocate disabled
USB 0: host mode
PEX 0: interface detected no Link.
Net: egiga0 [PRIME]
Hit any key to stop autoboot: 0
(Re)start USB...
USB: scanning bus for devices... 1 USB Device(s) found
Waiting for storage device(s) to settle before scanning...
0 Storage Device(s) found
** Bad partition 1 **
## Booting image at 00800000 ...
Bad Magic Number
Saving Environment to NAND...
Erasing Nand...Writing to Nand... done
Reset IDE:
Marvell Serial ATA Adapter
Integrated Sata device found
[0 0 0]: Enable DMA mode (5)
Device 0 @ 0 0:
Model: TOSHIBA MK6465GSX Firm: GJ003M Ser#: 50OAC319T
Type: Hard Disk
Supports 48-bit addressing
Capacity: 610480.3 MB = 596.1 GB (1250263728 x 512)
** Unable to read "/boot/uImage" from ide 0:1 **
## Booting image at 00800000 ...
Bad Magic Number
Saving Environment to NAND...
Erasing Nand...Writing to Nand... done
NAND read: device 0 offset 0x200000, size 0x600000
6291456 bytes read: OK
## Booting image at 01200000 ...
Image Name: Linux-2.6.31.8-topkick1281p2-001
Created: 2011-11-10 3:58:11 UTC
Image Type: ARM Linux Kernel Image (uncompressed)
Data Size: 3121408 Bytes = 3 MB
Load Address: 00008000
Entry Point: 00008000
Verifying Checksum ... OK
OK
Starting kernel ...
Uncompressing Linux................................................................................................................................................................................................... done, booting the kernel.
Linux version 2.6.31.8-topkick1281p2-001-004-20101214 (andrew@localhost.localdomain) (gcc version 3.4.4 (release) (CodeSourcery ARM 2005q3-2)) #2 Thu Nov 10 11:58:07 CST 2011
CPU: Feroceon 88FR131 [56251311] revision 1 (ARMv5TE), cr=00053977
CPU: VIVT data cache, VIVT instruction cache
Machine: Feroceon-KW
Using UBoot passing parameters structure
Memory policy: ECC disabled, Data cache writeback
Built 1 zonelists in Zone order, mobility grouping on. Total pages: 130048
Kernel command line: console=ttyS0,115200;version=topkick1281p2-001-006-20101103 mtdparts=nand_mtd:0x180000@0(u-boot),0x20000@0x180000(u-boot-env),0x600000@0x200000(uImage),0x1f800000@0x800000(rootfs) ubi.mtd=3 root=ubi0:rootfs rootfstype=ubifs rootdelay=10
PID hash table entries: 2048 (order: 11, 8192 bytes)
Dentry cache hash table entries: 65536 (order: 6, 262144 bytes)
Inode-cache hash table entries: 32768 (order: 5, 131072 bytes)
Memory: 512MB = 512MB total
Memory: 513280KB available (5612K code, 319K data, 148K init, 0K highmem)
NR_IRQS:128
Console: colour dummy device 80x30
Calibrating delay loop... 794.62 BogoMIPS (lpj=3973120)
Mount-cache hash table entries: 512
CPU: Testing write buffer coherency: ok
xor: measuring software checksum speed
arm4regs : 723.200 MB/sec
8regs : 433.600 MB/sec
32regs : 600.800 MB/sec
xor: using function: arm4regs (723.200 MB/sec)
NET: Registered protocol family 16
Feroceon L2: Enabling L2
Feroceon L2: Cache support initialised.
CPU Interface
-------------
SDRAM_CS0 ....base 00000000, size 512MB
SDRAM_CS1 ....disable
SDRAM_CS2 ....disable
SDRAM_CS3 ....disable
PEX0_MEM ....base e8000000, size 128MB
PEX0_IO ....base f2000000, size 1MB
INTER_REGS ....base f1000000, size 1MB
NFLASH_CS ....base fa000000, size 2MB
SPI_CS ....base f4000000, size 16MB
BOOT_ROM_CS ....no such
DEV_BOOTCS ....no such
CRYPT_ENG ....base f0000000, size 2MB
Marvell Development Board (LSP Version KW_LSP_5.0.3)-- DB-88F6282A-BP Soc: MV88F1155 Rev 1 LE
Detected Tclk 200000000 and SysClk 400000000
MV Buttons Device Load
Marvell USB EHCI Host controller #0: df837740
PEX0 interface detected no Link.
PCI: bus0: Fast back to back transfers enabled
bio: create slab <bio-0> at 0
SCSI subsystem initialized
usbcore: registered new interface driver usbfs
usbcore: registered new interface driver hub
usbcore: registered new device driver usb
raid6: int32x1 72 MB/s
raid6: int32x2 101 MB/s
raid6: int32x4 88 MB/s
raid6: int32x8 80 MB/s
raid6: using algorithm int32x2 (101 MB/s)
cfg80211: Calling CRDA to update world regulatory domain
NET: Registered protocol family 2
IP route cache hash table entries: 16384 (order: 4, 65536 bytes)
TCP established hash table entries: 65536 (order: 7, 524288 bytes)
TCP bind hash table entries: 65536 (order: 6, 262144 bytes)
TCP: Hash tables configured (established 65536 bind 65536)
TCP reno registered
NET: Registered protocol family 1
rtc mv_rtc: rtc core: registered kw-rtc as rtc0
RTC registered
cpufreq: Init kirkwood cpufreq driver
XOR registered 4 channels
XOR 2nd invalidate WA enabled
mvCesaInit: sessions=640, queue=64, pSram=f0000000
Warning: TS unit is powered off.
MV Buttons Driver Load
JFFS2 version 2.2. (NAND) © 2001-2006 Red Hat, Inc.
SGI XFS with security attributes, large block/inode numbers, no debug enabled
msgmni has been set to 1002
alg: No test for cipher_null (cipher_null-generic)
alg: No test for ecb(cipher_null) (ecb-cipher_null)
alg: No test for digest_null (digest_null-generic)
alg: No test for compress_null (compress_null-generic)
alg: No test for stdrng (krng)
alg: No test for hmac(digest_null) (hmac(digest_null-generic))
async_tx: api initialized (sync-only)
io scheduler noop registered
io scheduler anticipatory registered (default)
Serial: 8250/16550 driver, 4 ports, IRQ sharing disabled
serial8250.0: ttyS0 at MMIO 0xf1012000 (irq = 33) is a 16550A
console [ttyS0] enabled
Integrated Sata device found
IRQ 21/mvSata: IRQF_DISABLED is not guaranteed on shared IRQs
scsi0 : Marvell SCSI to SATA adapter
scsi1 : Marvell SCSI to SATA adapter
scsi 0:0:0:0: Direct-Access TOSHIBA MK6465GSX GJ00 PQ: 0 ANSI: 5
sd 0:0:0:0: [sda] Sector size 0 reported, assuming 512.
sd 0:0:0:0: [sda] 1250263728 512-byte logical blocks: (640 GB/596 GiB)
sd 0:0:0:0: [sda] 0-byte physical blocks
sd 0:0:0:0: [sda] Write Protect is off
sd 0:0:0:0: Attached scsi generic sg0 type 0
Loading Marvell Ethernet Driver:
o Cached descriptors in DRAM
o DRAM SW cache-coherency
o 2 Giga ports supported
o Multi RX Queue support - 4 RX queues
o Multi TX Queue support - 2 TX Queues
o TCP segmentation offload (TSO) supported
o Large Receive offload (LRO) supported
o Receive checksum offload supported
o Transmit checksum offload supported
o Network Fast Processing (Routing) supported - (Disabled)
o Network Fast Processing (NAT) supported
o Driver ERROR statistics enabled
o Driver INFO statistics enabled
o Proc tool API enabled
o SKB Reuse supported - (Disabled)
o SKB Recycle supported - (Disabled)
o Gateway support enabled
o Using Marvell Header Mode
o L2 IGMP support
o Rx descripors: q0=128 q1=128 q2=128 q3=128
o Tx descripors: q0=532 q1=532
o Loading network interface(s):
o register under mv88fx_eth platform
sd 0:0:0:0: [sda] Write cache: enabled, read cache: enabled, supports DPO and FUA
sd 0:0:0:0: [sda] Sector size 0 reported, assuming 512.
o eth0, ifindex = 2, GbE port = 0
Warning: Giga 1 is Powered Off
Warning: Giga 1 is Powered Off
mvFpRuleDb (df280000): 16384 entries, 65536 bytes
Intel(R) PRO/1000 Network Driver - version 7.3.21-k3-NAPI
Copyright (c) 1999-2006 Intel Corporation.
e1000e: Intel(R) PRO/1000 Network Driver - 1.0.2-k2
e1000e: Copyright (c) 1999-2008 Intel Corporation.
e100: Intel(R) PRO/100 Network Driver, 3.5.24-k2-NAPI
e100: Copyright(c) 1999-2006 Intel Corporation
sda:
PPP generic driver version 2.4.2
PPP Deflate Compression module registered
PPP BSD Compression module registered
PPP MPPE Compression module registered
NET: Registered protocol family 24
PPPoL2TP kernel driver, V1.0
Using Hamming 1-bit ECC for NAND device
NAND device: Manufacturer ID: 0xad, Chip ID: 0xdc (Hynix NAND 512MiB 3,3V 8-bit)
Scanning device for bad blocks
Bad eraseblock 1064 at 0x000008500000
Bad eraseblock 1065 at 0x000008520000
Bad eraseblock 1884 at 0x00000eb80000
Bad eraseblock 1885 at 0x00000eba0000
Bad eraseblock 2038 at 0x00000fec0000
Bad eraseblock 2039 at 0x00000fee0000
Bad eraseblock 2580 at 0x000014280000
Bad eraseblock 2581 at 0x0000142a0000
Bad eraseblock 2606 at 0x0000145c0000
Bad eraseblock 2844 at 0x000016380000
Bad eraseblock 3269 at 0x0000198a0000
Bad eraseblock 3547 at 0x00001bb60000
4 cmdlinepart partitions found on MTD device nand_mtd
Using command line partition definition
Creating 4 MTD partitions on "nand_mtd":
0x000000000000-0x000000180000 : "u-boot"
sda1
sd 0:0:0:0: [sda] Sector size 0 reported, assuming 512.
0x000000180000-0x0000001a0000 : "u-boot-env"
sd 0:0:0:0: [sda] Attached SCSI disk
0x000000200000-0x000000800000 : "uImage"
0x000000800000-0x000020000000 : "rootfs"
UBI: attaching mtd3 to ubi0
UBI: physical eraseblock size: 131072 bytes (128 KiB)
UBI: logical eraseblock size: 129024 bytes
UBI: smallest flash I/O unit: 2048
UBI: sub-page size: 512
UBI: VID header offset: 512 (aligned 512)
UBI: data offset: 2048
UBI: attached mtd3 to ubi0
UBI: MTD device name: "rootfs"
UBI: MTD device size: 504 MiB
UBI: number of good PEBs: 4020
UBI: number of bad PEBs: 12
UBI: max. allowed volumes: 128
UBI: wear-leveling threshold: 4096
UBI: number of internal volumes: 1
UBI: number of user volumes: 1
UBI: available PEBs: 75
UBI: total number of reserved PEBs: 3945
UBI: number of PEBs reserved for bad PEB handling: 40
UBI: max/mean erase counter: 3/1
UBI: image sequence number: 0
ehci_hcd: USB 2.0 'Enhanced' Host Controller (EHCI) Driver
ehci_marvell ehci_marvell.70059: Marvell Orion EHCI
ehci_marvell ehci_marvell.70059: new USB bus registered, assigned bus number 1
UBI: background thread "ubi_bgt0d" started, PID 480
ehci_marvell ehci_marvell.70059: irq 19, io base 0xf1050100
ehci_marvell ehci_marvell.70059: USB 2.0 started, EHCI 1.00
usb usb1: configuration #1 chosen from 1 choice
hub 1-0:1.0: USB hub found
hub 1-0:1.0: 1 port detected
ohci_hcd: USB 1.1 'Open' Host Controller (OHCI) Driver
uhci_hcd: USB Universal Host Controller Interface driver
usbcore: registered new interface driver usblp
Initializing USB Mass Storage driver...
usbcore: registered new interface driver usb-storage
USB Mass Storage support registered.
usbcore: registered new interface driver ums-datafab
usbcore: registered new interface driver ums-freecom
usbcore: registered new interface driver ums-jumpshot
usbcore: registered new interface driver ums-sddr09
usbcore: registered new interface driver ums-sddr55
usbcore: registered new interface driver ums-usbat
pwrctl: dev_t_NO. = 0xdd00000, major = 221
pwrctl: request the irq power off registered.
mice: PS/2 mouse device common for all mice
i2c /dev entries driver
Linux telephony interface: v1.00
md: linear personality registered for level -1
md: raid0 personality registered for level 0
md: raid1 personality registered for level 1
md: raid6 personality registered for level 6
md: raid5 personality registered for level 5
md: raid4 personality registered for level 4
device-mapper: ioctl: 4.15.0-ioctl (2009-04-01) initialised: dm-devel@redhat.com
sdhci: Secure Digital Host Controller Interface driver
sdhci: Copyright(c) Pierre Ossman
mmc0: mvsdio driver initialized, lacking card detect (fall back to polling)
Advanced Linux Sound Architecture Driver Version 1.0.20.
No device for DAI CS42L51
ALSA device list:
No soundcards found.
nf_conntrack version 0.5.0 (8192 buckets, 32768 max)
mvFpNatDb (df360000): 16384 entries, 65536 bytes
ip_tables: (C) 2000-2006 Netfilter Core Team
TCP cubic registered
NET: Registered protocol family 17
NFP (fdb) init 256 entries, 1024 bytes
RPC: Registered udp transport module.
RPC: Registered tcp transport module.
802.1Q VLAN Support v1.8 Ben Greear <greearb@candelatech.com>
All bugs added by David S. Miller <davem@redhat.com>
rtc mv_rtc: setting system clock to 2012-03-31 01:20:22 UTC (1333156822)
Waiting 10sec before mounting root device...
mmc0: new high speed SDIO card at address 0001
md: Waiting for all devices to be available before autodetect
md: If you don't use raid, use raid=noautodetect
md: Autodetecting RAID arrays.
md: Scanned 0 and added 0 devices.
md: autorun ...
md: ... autorun DONE.
UBIFS: mounted UBI device 0, volume 0, name "rootfs"
UBIFS: file system size: 501387264 bytes (489636 KiB, 478 MiB, 3886 LEBs)
UBIFS: journal size: 25159680 bytes (24570 KiB, 23 MiB, 195 LEBs)
UBIFS: media format: w4/r0 (latest is w4/r0)
UBIFS: default compressor: lzo
UBIFS: reserved for root: 4952683 bytes (4836 KiB)
VFS: Mounted root (ubifs filesystem) on device 0:11.
Freeing init memory: 148K
Using makefile-style concurrent boot in runlevel S.
Starting the hotplug events dispatcher: udevd.
Synthesizing the initial hotplug events...done.
Waiting for /dev to be fully populated...done.
Setting parameters of disc: (none).
Activating swap...done.
Starting early crypto disks...done.
Starting remaining crypto disks...done.
Loading kernel modules...done.
Cleaning up ifupdown....
Setting up networking....
Activating lvm and md swap...done.
Checking file systems...fsck from util-linux-ng 2.17.2
done.
Mounting local filesystems...done.
Activating swapfile swap...done.
Cleaning up temporary files....
Setting kernel variables ...done.
Configuring network interfaces...Internet Systems Consortium DHCP Client 4.1.1-P1
Copyright 2004-2010 Internet Systems Consortium.
All rights reserved.
For info, please visit https://www.isc.org/software/dhcp/
eth0: started
Listening on LPF/eth0/40:2c:f4:bc:8b:c9
Sending on LPF/eth0/40:2c:f4:bc:8b:c9
Sending on Socket/fallback
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 4
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 5
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 13
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 10
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 14
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 8
DHCPDISCOVER on eth0 to 255.255.255.255 port 67 interval 7
No DHCPOFFERS received.
No working leases in persistent database - sleeping.
done.
Cleaning up temporary files....
fuse init (API version 7.12)
Using makefile-style concurrent boot in runlevel 2.
Network Interface Plugging Daemon...start eth0...done.
Starting enhanced syslogd: rsyslogd.
Starting Samba daemons: nmbd smbdStarting periodic command scheduler: cron.
.
Starting system message bus: dbus.
Starting OpenBSD Secure Shell server: sshd.
EXT2-fs warning: mounting unchecked fs, running e2fsck is recommended
Debian GNU/Linux 6.0 TonidoPlug2 ttyS0
TonidoPlug2 login: --2012-03-30 18:21:50-- http://patch.codelathe.com/firmware/tonidoplug2/updates.list
Resolving patch.codelathe.com... failed: Name or service not known.
wget: unable to resolve host address “patch.codelathe.com”
Debian GNU/Linux 6.0 TonidoPlug2 ttyS0
TonidoPlug2 login: root
Password:
Last login: Fri Mar 30 18:16:16 PDT 2012 on ttyS0
Linux TonidoPlug2 2.6.31.8-topkick1281p2-001-004-20101214 #2 Thu Nov 10 11:58:07 CST 2011 armv5tel
The programs included with the Debian GNU/Linux system are free software;
the exact distribution terms for each program are described in the
individual files in /usr/share/doc/*/copyright.
Debian GNU/Linux comes with ABSOLUTELY NO WARRANTY, to the extent
permitted by applicable law.
root@TonidoPlug2:~#
I suspect I’ll be able to debug it a lot better tomorrow.
The Little Engine that Could…
In my home office, I have a machine called “fishtank”. I realized that I first bought it back in 2002, and since then it has been running various flavors of FreeBSD (probably beginning around 4.6 or so, currently running 7.2). At various times I’ve added or upgraded disk drives to it. While a power failure just two weeks ago reset it’s uptime, it’s had uptimes in excess of six hundred days on at least two occasions. I use it as an ssh server, file repository, and generally just a net accessible resource for generic computing tasks.
But the other day, I wanted to generate some new maps for my website using some code that I had never tried before, the Matplotlib Basemap Toolkit. There were already port files in FreeBSD, so I thought I’d try it out. So, I set it running with portmaster, and walked away.
The build failed.
Digging in, I found that it failed while building gcc (why it needed to build a new version of gcc I’m not sure, but it thinks it did). And it turns out it just flat ran out of memory.
I asked the quite natural question, “how much memory does this thing have?”
The answer: 256 megabytes. With less than 500 megabytes of swap.
I think it’s time to consider an upgrade. I could put 1G of memory in it, but that seems pretty lame. I think I’ll replace it with a small mini-desktop. I’m looking for an inexpensive, relatively low power and most importantly quiet server box. Anyone have any recommendations?
Arduino Basic
Edsger Dijkstra, Dutch computer scientist and winner of the 1972 Turing Award wrote:
It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration.
While I have respect for his great contributions to the field, in my opinion, this claim falls a bit far afield. In particular, nearly everyone who learned about computers in my generation seemed to through the path of BASIC. BASIC was the lingua franca of the microcomputer revolution, and while I now see it as rather quaint and ridiculous, it provided a step into computing for many people who found that they could indeed regenerate their brain cells in spite of their early exposure.
But does BASIC have any place in the modern world? Well, I must admit, the answer might be “maybe”. Little microcontrollers like the BASIC Stamp have been overshadowed a bit by the Arduino, but I still think that having an interactive interpreter that you can use to access a small computer makes some sense. Having a small language like Tiny BASIC, augmented by a few small additions to (say) allow you to generate sounds or control I/O pins makes a great deal of sense. Thus, without further justification, take a look at this project:
The code looks pretty nice and tidy, and should be easy to extend. It allows programs of up to 1.4K to be loaded into RAM, which sounds like a trivial amount, but it’s certainly enough to blink some leds, read and write some serial data, and generally exercise some of the capabilities of the chip. Neat project!
Microcontroller cheat sheet
I needed to know the pinouts for various AVR chips and the 6 pin ICSP cable they used. I found this cool little one page sheet that had that, and more. Saved for future reference:
More Wisdom on LEDs…
More important help for the budding young electronics designer:
https://twitter.com/#!/EMSL/status/144546376624250880
Note: this also works in computer graphics quite well. Just specify a negative intensity for the light value.
Making some wallpaper with the sum of cosines…
I was inspired by some Haskell code written by keegan, so I had to write a version of it in C. I didn’t do any animation, but I did have a lot of fun playing around with the parameters. For instance, check out the code, and how changing the value of N from 5, 7, and 19 generates interesting and cool patterns.
[sourcecode lang=”cpp”]
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
/*
* quasi.c
*
* Some code, inspired by keegan @
* http://mainisusuallyafunction.blogspot.com/2011/10/quasicrystals-as-sums-of-waves-in-plane.html
* but presented without any further explanation.
*/
#define N (19)
#define XSIZE (1280)
#define YSIZE (720)
#define SCALE (0.2)
double x[N], y[N], ph[N] ;
double image[YSIZE][XSIZE] ;
int
main()
{
int i, j, k ;
for (i=0; i<N; i++) {
x[i] = cos(2.0 * M_PI * i / (double) N) ;
y[i] = sin(2.0 * M_PI * i / (double) N) ;
ph[i] = 0.0 ;
}
for (j=0; j<YSIZE; j++) {
for (i=0; i<XSIZE; i++) {
image[j][i] = 0. ;
for (k=0; k<N; k++) {
double d = (x[k] * (i – XSIZE / 2.) + y[k] * (j – YSIZE / 2.) + ph[k]) * SCALE ;
image[j][i] += (1.0 + cos(d)) / 2. ;
}
int t = (int) floor(image[j][i]) ;
assert(t >= 0.) ;
double v = image[j][i] – t ;
if (t % 2 == 1) v = 1. – v ;
image[j][i] = v ;
}
}
printf("P5\n%d %d\n%d\n", XSIZE, YSIZE, 255) ;
for (j=0; j<YSIZE; j++)
for (i=0; i<XSIZE; i++)
putchar(255. * image[j][i]) ;
return 0 ;
}
[/sourcecode]
Cool stuff!
Can we go beyond WSPR? An idea for beacon operations on amateur radio.
I was interested in WSPR and visual MEPT oeprations for quite some time. I operated both a beacon and a QRSS aggregator on 30m for a while, but I grew a bit tired of it, and it’s been silent for a year or so. But I haven’t stopped thinking about them. In fact, I’ve had an idea percolating in the back of my head since last year, when I became aware of the work of Leemon Baird and William Bahn on Jam Resistant codes.
But I’m getting ahead of myself. Here are some of what I think could be improved with WSPR:
- WSPR requires accurate clocks both for receiving and transmitting. To be successfully decoded, transmissions must start within a window just a few seconds long surrounding even numbered minutes. This makes both sending and receiving systems complicated: they probably need to access an external reference (NTP, GPS or WWV) to operate reliably over an extended period.
- Fixed frequency operation can cause collisions. Each transmitter selects a fixed transmit frequency, and relies on multiplexing over time to avoid collisions. WSPR software itself provides no real help in selection of an appropriate free frequency.
- The choice of a convolutional code is somewhat odd. The payload is only 50 bits long, but we pad the results with 31 zeros to flush out the convolutional coder. Thus, we are actually getting the error correction of a rate 1/2 code, but we are only sending as much data as if we were sending a rate 1/3 code.
I had been pondering some of these issues, when I became aware of the work of Baird and Bahn. They are researchers for the Air Force Academy, and were particularly studying the problem of providing jam proof communications without the need for shared secrets. Briefly, you can imagine using spread spectrum to provide a measure of jam proofing: because the data is spread out among many frequencies over time, the spread spectrum signal has a good measure of jam proofing: the jammer needs to put energy over most of the frequency most of the time, where as the transmitter can put his full power on just one frequency at a time (other variants of spread spectrum are a bit different, but the principle holds). The only way a jammer can work efficiently is by knowing the sequence, which is usually a cryptographic secret.
This is where Baird, Bahn, and Collins’ work comes in: In their paper:
Baird, Leemon C. III, Bahn, William L. & Collins, Michael D. (2007) Jam-Resistant Communication Without Shared Secrets Through the Use of Concurrent Codes, Technical Report, U. S. Air Force Academy, USAFA-TR-2007-01, Feb 14.
they show a simple technique that can be used to transmit signals with high reliability and a high degree of jam resistance, without requiring any kind of shared secret or cryptography.
The idea is somewhat subtle, but reasonably straightforward. The idea is to create take the binary message (say, the same 50 bits that we use for WSPR). This message gets padded by a series of zeros (maybe lots of them, perhaps a multiple of the original message length). You then need a hash function (some details matter, but you can think of using a standard one like MD5 or one of the SHA variants if you like). Now, for each prefix of the message (bit streams of length one, then two, then three, and so on), you compute the hash of that prefix. Let’s say that you are going to transmit the message by sending short, powerful bursts of energy at particular times in particular window. (You can imagine this being the two minute window used to transmit WSPR to make it more practical). If we divide that into (say) 8192 slots, then we could take each hash, take the lower 13 bits, and use that to specify a particular time when that bit would get turned on. If we send 500 bits total (9 zero checksum bits) for every real one, we are sending about 500/8192 slots, or about 6% of the total. To mark the start and stop, let’s turn on the first and last bit. That’s pretty much the entire transmit side.
What’s cool is that you can decode the message on the remote side, and if you ignore efficiency, it isn’t even that hard. Let’s say that you located a stretch of bits 8190 long, between two on bits. That might be a message. So, how do you decode it? Well, the first bit might be a zero or a one. You basically pretend that you are transmitting, and encode both messages. That will return a location, which you check to see is on. If it isn’t, then you know that guess was wrong. If it is, then that hypothesis is good. It’s possible that none could be right. That means there is probably not a message in that span. It’s possible that one could be right, in which case you then add a zero, and then try adding an one, and seeing if the hypothesis still holds. There are times when both results will check out, but statistically it is unlikely. When you hit the “checksum bits”, you know that there is only one possibility: a zero. If the specified hash doesn’t yield a location that is turned on, you know that you are on the wrong track. (The overall algorithm reminds me somewhat of a Viterbi style decoder, although it is actually considerably simpler).
There are lots of details to make this efficient (you want a hash function which allows incremental updates as you add individual bits to the message) but it’s pretty straightforward.
Anyway, I think this could be the basis for a new highly-collision resistant beaconing protocol for amateur radio. It would enable very simple transmitters (a simple microcontroller could hold the sequence in internal EEPROM, no need for highly accurate clocks) and the system would be more highly jam resistant than the current system. We could use simple CW transmissions, or adapt to slower rates with more diverse frequency usage. And, the technology has been paid for by your tax dollars, so no pesky patent/IP issues would seem to apply.
What do people think? I’m interested in hearing some feedback from digitally minded radio amateurs.
Addendum: if my descriptionw as insufficient, try reading the papers (especially Visually Understanding Jam Resistant Communication) and/or posting some questions in the comments.
Sprites mods – CP/M on an AVR
I’ve always been fascinated by emulation and virtual machines, as well as retro-computing: resurrecting the old machines of my past. I never owned an old CP/M machine, but there are still some neat projects where people construct there own, and simulators like SIMH and YAZE-AG are good software simulators. But what I always wondered was whether a small microcontroller like an Atmel AVR could simulate an 8080 or Z80 fast enough to simulate these older machines.
And of course, today I found a link to someone who did just that. With a remarkably simple chunk of hardware. One AVR, a dynamic RAM, and an SD card to serve as a mass storage device. The combination is good enough to run Zork. I’m suitably impressed. The design and code are all GPL.
Donald Michie, Alan Turing, Martin Gardner, and Tic Tac Toe
As anyone who reads my blog with any regularity will tell you, I like to read and learn new things. The problem with being self taught and also easily distracted means that you often learn a great deal, but don’t always perceive the connections and scope of what you are learning. I found another example today while surfing.
Years ago, I remember reading one of Martin Gardner’s Mathematical Games columns (from March, 1962, in case you want to look it up) where he described an interesting machine for playing tic-tac-toe. It was made entirely out of matchboxes, each one of which had a tic tac toe position on the top. Inside was a collection of colored beads. Each color specified a possible legal move for the position on top. The idea was that you’d play a game by drawing these beads from the appropriate box, and making the appropriate move. At the end of the game, you’d remove the bead from the last box that sent you along the losing path. Eventually, all the losing moves get removed, and the machine plays perfect tic-tac-toe. Gardner showed how this same idea could be used to create a matchbox computer to play hexapawn, a simple game played with six pawns on a 3×3 board.
I really haven’t given it much thought since then. Many of you have probably read this article in one of the collections of Gardner’s columns.
But today, I was surfing through links and reread some of the details. I found that the machine was called MENACE (Matchbox Educable Naughts and Crosses Engine) and was invented in 1960 by a gentleman named Donald Michie. And it turns out that he’s a pretty interesting guy.
He was a colleague and friend of Alan Turing, and worked with him at Bletchley Park. Apparently Michie, Turing and Jack Good were all involved in the British code breaking efforts, and in the creation of Collosus, the first digital programmable computer which was used to crack the German “Tunny” teleprinter code. (Good and Michie were apparently two of the authors of the General Report on Tunny, a report on the cracking of the code which has only in recent years become declassified). None of this work could have been known by Martin Gardner at the time of this publication. Of course, this was also true of Turing’s work as well.
Turing made a huge impact in several related disciplines: in mathematical logic and computation, in his wartime efforts in code breaking, and in his role in creating some of the first digital computers. Turing also became interested in mathematics in biology, writing about the chemical foundations of morphogenesis and predicting oscillatory chemical reactions. Michie received a doctorate in biology from Oxford, but returned to have a profound and lasting influence on artificial intelligence. Oh, and that modest little paper on Tic Tac Toe? One of the first instances of reinforcement learning.
Very cool, to discover that the little bit of reading you did as a teen, which seemed like an insignificant game at the time, actually has profound threads which stretch out into lots of different areas.
Donald Michie’s Home Page
Trial and Error, the paper describing MENACE
Return Infinity – BareMetal OS
At various times, I’ve been interested in writing operating systems. I haven’t done much thinking about this recently, but it is a topic of interest. I hadn’t seen this project before: a small 64 bit kernel written in assembly. I have no idea whether it’s interesting, but I thought I’d bookmark it for future investigation.