brainwagon "There is much pleasure in useless knowledge." — Bertrand Russell

26Jun/161

Hooded Oriole at my hummingbird feeder…

Last year, I bodged together a motion detecting camera to photograph hummingbirds at my hummingbird feeder. But it was always a temporary hack. We had some difficulty with the ants that discovered the feeder, and we discontinued the experiment.

I had a post that I could hang some feeders from, and decided to fill a planter with cement and embed the post so I could move it around and hose it down easily. It's working pretty well: last weekend we finished it, and have already had to refill the feeder. I think I've identified at least three to four hummingbirds who are feeding there, although they seem quite territorial, and one of the larger ones often scares off the smaller ones.

But he doesn't seem to bother this guy:

yellow

I'm not much of a bird watcher, but a little googling suggests to me that he's a Hooded Oriole. They seem to like the sugar water from hummingbird feeders, and slurp up a fair amount of this stuff when they land. I've seen a female of the species as well, who is a bit paler and lacks the black markings surrounding the eye.

I'll try to get the motion detecting camera up sometime in the next few weeks.

25May/160

Shower (or should I say “cow-er”) Thought of the Day…

I just recently found out about the /r/showerthoughts subreddit, where people vote on pithy sayings. I thought this might be a fun thing to have to replace the aging and relatively static "fortune" file that I use. I used the Python "PRAW" library to fetch the top entry for the day, and then optionally pass it to the terrific "cowsay" program for formatting.

Here's the tiny, nearly trivial code, whose code includes an example of the output of "./shower --cow"

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# a program for fetching texts from Reddit's /r/showerthoughts reddit.
#  _________________________________________
# / The guy who said “Look! Up in the sky!  \
# | It’s a bird!” in the Superman intro was |
# \ strangely excited to see a bird...      /
#  -----------------------------------------
# \   ^__^
#  \  (oo)\_______
#     (__)\       )\/\
#         ||----w |
#         ||     ||

# Written by Mark VandeWettering, no rights reserved.

import sys
import subprocess
import argparse
import textwrap
import praw

parser = argparse.ArgumentParser(description = 'Fetch shower thoughts from reddit.')
parser.add_argument('--cow', action='store_true',
                help='pipe output through cowsay')
parser.add_argument('--cowstyle', dest='cowstyle', nargs=1, default=['default'],
                help='style passed to cowsay')
args = parser.parse_args()

r = praw.Reddit('shower')
s = r.get_subreddit('showerthoughts')

submissions = s.get_top_from_day(limit = 1)


for submission in submissions:
        if args.cow:
            ps = subprocess.Popen(['cowsay', '-f', args.cowstyle[0]], shell=False, stdin=subprocess.PIPE)
            ps.stdin.write(submission.title.encode('utf-8'))
            ps.stdin.close()
            ps.wait()
        else:
            for l in textwrap.wrap(submission.title, 60):
                print ("\t%s" % l).encode('utf-8')
Filed under: My Projects No Comments
21May/160

Some random pictures from the Maker Faire…

Filed under: My Projects No Comments
17May/160

Code for generating a random Latin square…

The other day I mentioned that generating random Latin squares was a bit more complicated than I thought, and that an algorithm by Jacobson and Matthews was the way that people typically did it. I worked up this implementation based on a couple of different descriptions of the algorithm (the original paper was behind a paywall). The code below simply generates a random DIMxDIM Latin square using their algorithm. I haven't done extensive testing, but it appears to mostly work. I did run a test where I generated one million 4x4 matrices, and found that it generated all 576 different matrices in approximately the same propertion, so it appears to at least be roughly operational. I'll eventually merge the code with my nascent KenKen generator.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

/*
 * rls.c
 *
 * A straightforward implementation of the algorithm by Jacobson and 
 * Matthews, _Generating uniformly distributed random Latin square_,
 * Journal of Combinatorial Design, 1996.
 *
 * I actually couldn't find the original paper, so this is an implementation
 * based upon other descriptions of the algorithm.
 *
 * Written by Mark VandeWettering.
 *
 */


#define DIM (6)

typedef struct t_incidence_cube {
    int s[DIM][DIM][DIM] ;
} IncidenceCube ;


void
InitIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    /* First, zero the cube */
    for (i=0; i<DIM; i++)
        for (j=0; j<DIM; j++)
            for (k=0; k<DIM; k++)
                c->s[i][j][k] = 0 ;

    /* And then dump ones in the right place... */
    for (i=0; i<DIM; i++)
        for (j=0; j<DIM; j++)
            c->s[i][j][(i+j)%DIM] = 1 ;
}

void
PrintIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    for (i=0; i<DIM; i++) {
        for (j=0; j<DIM; j++) {
            for (k=0; k<DIM; k++) {
                if (c->s[i][j][k]) {
                    printf("%2d ", k+1) ;
                    break ;
                }
            }
        }
        printf("\n") ;
    }
    printf("\n") ;
}

void
CompactPrintIncidenceCube(IncidenceCube *c)
{
    int i, j, k ;

    for (i=0; i<DIM; i++) {
        for (j=0; j<DIM; j++) {
            for (k=0; k<DIM; k++) {
                if (c->s[i][j][k]) {
                    printf("%01d", k+1) ;
                    break ;
                }
            }
        }
    }
    printf("\n") ;
}

void
ShuffleIncidenceCube(IncidenceCube *c)
{
    int i, j ;

    for (i=0; i<DIM*DIM*DIM; i++) {
        
        // Assume we have a "proper" matrix...
       
        // Pick a random zero from the incidence cube... 
        int rx, ry, rz ;
        do {
            rx = lrand48() % DIM ;
            ry = lrand48() % DIM ;
            rz = lrand48() % DIM ;
        } while (c->s[rx][ry][rz]) ;

        int ox, oy, oz ;

        for (j=0; j<DIM; j++) {
            if (c->s[j][ry][rz] == 1)
                ox = j ;
            if (c->s[rx][j][rz] == 1)
                oy = j ;
            if (c->s[rx][ry][j] == 1)
                oz = j ;
        }

        // do the +/- 1 move...  
        // These are all square with zeros in them...
        c->s[rx][ry][rz] ++ ;
        c->s[rx][oy][oz] ++ ;
        c->s[ox][ry][oz] ++ ;
        c->s[ox][oy][rz] ++ ;

        // These all have ones, except for maybe the last one...
        c->s[rx][ry][oz] -- ;
        c->s[rx][oy][rz] -- ;
        c->s[ox][ry][rz] -- ;
        c->s[ox][oy][oz] -- ;

        while (c->s[ox][oy][oz] < 0) {

            rx = ox ;
            ry = oy ;
            rz = oz ;

            // Pick one of the two 1's that are in conflict
            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[j][ry][rz] == 1) {
                        ox = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[j][ry][rz] == 1) {
                        ox = j ;
                    }
                }
            }

            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[rx][j][rz] == 1) {
                        oy = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[rx][j][rz] == 1) {
                        oy = j ;
                    }
                }
            }

            if (drand48() < 0.5) {
                for (j=0; j<DIM; j++) {
                    if (c->s[rx][ry][j] == 1) {
                        oz = j ;
                    }
                }
            } else {
                for (j=DIM-1; j>=0; j--)  {
                    if (c->s[rx][ry][j] == 1) {
                        oz = j ;
                    }
                }
            }
          
            // do the +/- 1 move...  
            // These are all square with zeros in them...
            c->s[rx][ry][rz] ++ ;
            c->s[rx][oy][oz] ++ ;
            c->s[ox][ry][oz] ++ ;
            c->s[ox][oy][rz] ++ ;

            // These all have ones, except for maybe the last one...
            c->s[rx][ry][oz] -- ;
            c->s[rx][oy][rz] -- ;
            c->s[ox][ry][rz] -- ;
            c->s[ox][oy][oz] -- ;
        }

    }
}

int
main()
{
    IncidenceCube c ;
    int i ;

    srand48(getpid()) ;
    InitIncidenceCube(&c) ;
    ShuffleIncidenceCube(&c) ;
    PrintIncidenceCube(&c) ;
    return 1 ;
}
12May/161

KenKen puzzle solver…

Lately, my lunch hours have been spent working on the NYT Crossword with my lunch companion Tom. While I find that the Thursday crosswords are often beyond my ability to do in the allotted time, between the two of us, more often than not we manage to plow through them. Slowly over time, we've begun to solve them slightly quicker, so I've branched out to doing the KenKen puzzles.

For those of you who haven't seen these before, you can learn about them on their official website here. The 4x4 ones are usually pretty easy, but the last couple days have done some 6x6 puzzles have been shockingly hard. So much so, that today I got to this state on today's puzzle:

IMG_1128

Yes, I was using pen. And I made a mistake, although I can't see what I was thinking when I did. And because I made a mistake, I couldn't spot it, and I was hung up. The "4" in first column was wrong. I knew it could not be a 6 or 1, or a 3, or a 4, but for some reason I thought that the final column couldn't be 4 and 3, but..

Never mind, it doesn't matter what the mistake was.

By the end up twenty minutes I was annoyed, knew I had made a mistake, but decided to give into the urge to write a program to solve it. How long could it take?

Well, the answer was about 27 minutes.

This program doesn't have any interface or flexibility, everything is hard coded. Basically it uses backtracking and fills in each square in order from bottom left to top right, and as the top most, right most square of each outlined area is finished, it checks to make sure that the sums/differences/whatever for the filled in region sum to the right values. I didn't know how I was going to encode those constraints, so I just ended up writing a function that computes the proper constraint. This is not really the right way to do it: it's error prone and requires recompilation of the code to change the puzzle. But it does work fairly well, once you type the expressions in correctly.

Once I got those straightened out, it blats out the solution in less than 1 millisecond on my desktop.

+---+---+---+---+---+---+
| 6 | 1 | 5 | 2 | 4 | 3 |
+---+---+---+---+---+---+
| 2 | 6 | 1 | 3 | 5 | 4 |
+---+---+---+---+---+---+
| 1 | 4 | 6 | 5 | 3 | 2 |
+---+---+---+---+---+---+
| 3 | 2 | 4 | 6 | 1 | 5 |
+---+---+---+---+---+---+
| 5 | 3 | 2 | 4 | 6 | 1 |
+---+---+---+---+---+---+
| 4 | 5 | 3 | 1 | 2 | 6 |
+---+---+---+---+---+---+

1 solutions found

It points out that the 4 should have been a 2 (IDIOT!) and then it all works out.

The code is 178 lines long, but is not particularly pretty/short/adaptable. Some day, I'll have to tidy it up and make a better version.

But in case people find this stuff interesting, here it is. Remember: 27 minutes to write.

include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * kenken.c
 *
 * A program inspired by a particular tough 6x6 puzzle that appeared
 * on Thursday, May 11, 2016, which Tom Duff and I could not appear to
 * get the answer to during our lunch hour.  I thought that it was possible
 * that I could write a program to solve the puzzle in less than an hour.
 *
 * Hence, this code.
 *
 */

int total = 0 ;

#define DIM     (6)

typedef struct t_puzzle_state {
    int sq[DIM][DIM] ;
    int r[DIM] ;            // bitflag for values left in rows...
    int c[DIM] ;            // bitflag for values available in columns
} PuzzleState ;


void
PrintPuzzleState(PuzzleState *p)
{
    int i, j ;

    printf("+") ;
    for(j=0; j<DIM; j++)
        printf("---+") ;
    printf("\n") ;

    for (i=0; i<DIM; i++) {
        printf("|") ;
        for (j=0; j<DIM; j++) {

            if (p->sq[DIM-1-i][j])
                printf(" %1d |", p->sq[DIM-1-i][j]) ;
            else
                printf("   |") ;
        }
        printf("\n+") ;
        for(j=0; j<DIM; j++)
            printf("---+") ;
        printf("\n") ;
    }
    printf("\n") ;
}

void
InitializePuzzleState(PuzzleState *p)
{
    int i, j ;

    memset((void *) p, 0, sizeof(*p)) ;

    for (i=0; i<DIM; i++) {
        for (j=1; j<=DIM; j++) {
            p->r[i] |= (1<<j) ;
            p->c[i] |= (1<<j) ;
        }
    }
}

void
HardcodePuzzleState(PuzzleState *p, int r, int c, int val)
{
    p->sq[r] = val ;
    p->r[r] &= ~(1<<val) ;
    p->c &= ~(1<<val) ;
}

#define SQUARE(i, j)    ((i)*DIM+(j))
#define ABS(x)          ((x)<0?(-(x)):(x))

int
ConstraintSatisfied(PuzzleState *p, int i, int j)
{
    switch (SQUARE(i,j)) {
    case SQUARE(0,1):
        return ABS(p->sq[0][0] - p->sq[0][1]) == 1 ;
    case SQUARE(0,2):
        return p->sq[0][2] == 3 ;
    case SQUARE(1, 3):
        return (p->sq[0][3]+p->sq[1][3]) == 5 ;
    case SQUARE(1, 4):
        return (p->sq[0][4] * p->sq[0][5] * p->sq[1][4]) == 72 ;
    case SQUARE(2, 2):
        if (p->sq[2][2] == 2 * p->sq[1][2])
            return 1 ;
        if (p->sq[1][2] == 2 * p->sq[2][2])
            return 1 ;
        return 0 ;
    case SQUARE(2, 4):
        return ABS(p->sq[2][4] - p->sq[2][3]) == 5 ;
    case SQUARE(3, 1):
        if (p->sq[3][1] == 2 * p->sq[2][1])
           return 1 ;
        if (p->sq[2][1] == 2 * p->sq[3][1])
           return 1 ;
        return 0 ;
    case SQUARE(3, 5):
        return (p->sq[3][5]+p->sq[2][5]+p->sq[1][5]) == 8 ;
    case SQUARE(4, 2):
        return ABS(p->sq[4][2] - p->sq[4][1]) == 5 ;
    case SQUARE(4, 3):
        return p->sq[4][3] == 3 ;
    case SQUARE(4, 4):
        return (p->sq[4][4]+p->sq[3][2]+p->sq[3][3]+p->sq[3][4]) == 19 ;
    case SQUARE(5, 1):
        return (p->sq[4][0]*p->sq[5][0]*p->sq[5][1]) == 12 ;
    case SQUARE(5, 4):
        return (p->sq[5][2]+p->sq[5][3]+p->sq[5][4]) == 11 ;
    case SQUARE(5, 5):
        return (p->sq[5][5]+p->sq[4][5]) == 7 ;
    default:
        return 1 ;
    }

    return 1 ;
}

void
SolvePuzzleState(PuzzleState *p, int i, int j)
{
    int v ;

    if (i >= DIM) {
        PrintPuzzleState(p) ;
        total ++ ;
        return ;
    }
        
    int pval = p->r[i] & p->c[j] ;

    for (v=1; v<=DIM; v++) {
        if ((pval & (1<<v)) == 0)
            continue ;
        // Try to place v in sq[i][j] ;
        p->sq[i][j] = v ;

        if (ConstraintSatisfied(p, i, j)) {
            p->r[i] &= ~(1<<v) ;
            p->c[j] &= ~(1<<v) ;

            int ni, nj ;
            nj = j + 1 ;
            if (nj < DIM) {
                ni = i ;
            } else {
                ni = i + 1 ;
                nj = 0 ;
            }

            SolvePuzzleState(p, ni, nj) ;

            p->r[i] |= (1<<v) ;
            p->c[j] |= (1<<v) ;
        } 
    }
    p->sq[i][j] = 0 ;
}

main()
{
    PuzzleState p ;
    InitializePuzzleState(&p) ;
    // HardcodePuzzleState(&p, 0, 2, 3) ;
    // HardcodePuzzleState(&p, 4, 3, 3) ;

    SolvePuzzleState(&p, 0, 0) ;
    fprintf(stderr, "%d solutions found\n", total) ;
}
4May/161

Solving the N queens problem, again…

Backtracking is a better technique, obviously. The version from earlier today was actually not very clever, and took half an hour to find the 73,712 solutions to the 13x13 checkerboard. This version is less code (just 91 lines, compared to 107 for yesterdays) and finds all the 13x13 solutions in just 2.5 seconds (a speed up of around 720x).

#include <stdio.h>
#include <stdlib.h>

#define MAX_N   (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
    int i, j ;

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n") ;

    for (i=0; i<n; i++) {
        printf("|") ;
        for (j=0; j<n; j++) {
            if (j == board[i])
                printf("O") ;
            else
                printf(" ") ;
            if (j < n-1)
                printf("|") ;
        }
        printf("?\n") ;
        if (i < n-1) {
            printf("+") ;
            for (j=0; j<n; j++) {
                printf("-") ;   
                if (j < n-1) 
                    printf("+") ;       
            }
            printf("+\n") ;
        }
    }

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))


void
place(int r, int n)
{
    int i, j ;
    if (r == n) {
        // We filled in all rows...
        total++ ;
        print(board, n) ;
    } else {
        for (i=0; i<n; i++) {
           board[r] = i ;
           for (j = 0; j<r; j++) {
                if (board[j] == board[r])
                    goto skipit ;
                if (abs(board[j]-board[r]) == abs(j-r))
                    goto skipit ;
           }
           place(r+1, n) ;
skipit:
           continue ;
        }
    }
}

int
main(int argc, char *argv[])
{
    int n = atoi(argv[1]) ;
    place(0, n) ;
    if (total == 0)
        fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
    else
        fprintf(stderr, "There is %d solution%s for the %dx%d board.\n", 
                total, total > 1 ? "s" : "", n, n) ;
    return 0 ;
}

Fun.

Filed under: My Projects 1 Comment
4May/160

Solving the N Queens Problem…

A question on Quora set me thinking about solving the N Queens problem, which is to list all ways that N queens can be positioned on an NxN checkerboard such that no queen can attack the other. I seemed to have misplaced my implementation of this that I did in Python, so I decided to do one in C while watching Agents of Shield. The code in general shows the lack of attention, but it does work. It can find all 92 solutions for the 8x8 checkerboard in under one second, but slows down rapidly after that, taking nearly half an hour to find all 73,712 solutions for the 13x13 board.

This program isn't completely unclever (in fact, I think it is too clever in a way) but it should be properly described as a brute force search, since it generates all N! ways of positioning N queens in different rows, and tests them for diagonals. Thus, it's runtime is O(N!), which isn't great. It doesn't even do backtracking, which would undoubtedly help a great deal.

One good page I found googling this morning is this one by Jeff Somer. His program is much more clever than mine. My estimate is that my program would take well over 100,000 years to count all the positions for a 21x21 board, Jeff's does it in about a week.

Another cool page is this one, which introduces the idea of "super-queens", which also capture with the same moves as a knight. Only one unique solution for N=10 exists, which is pretty cool. For higher N, more solutions become possible.

Code is archived here.

#include <stdio.h>
#include <stdlib.h>

#define MAX_N   (15)

int board[MAX_N] ;
int total = 0 ;

void
print(int board[MAX_N], int n)
{
    int i, j ;

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n") ;

    for (i=0; i<n; i++) {
        printf("|") ;
        for (j=0; j<n; j++) {
            if (j == board[i])
                printf("O") ;
            else
                printf(" ") ;
            if (j < n-1)
                printf("|") ;
        }
        printf("?\n") ;
        if (i < n-1) {
            printf("+") ;
            for (j=0; j<n; j++) {
                printf("-") ;   
                if (j < n-1) 
                    printf("+") ;       
            }
            printf("+\n") ;
        }
    }

    printf("+") ;
    for (i=0; i<n; i++) {
        printf("-") ;
        if (i < n-1)
            printf("+") ;
    }
    printf("+\n\n") ;
}

#define abs(n) ((n)<(0)?(-(n)):(n))

void
check(int board[MAX_N], int n)
{
    int col[MAX_N] ;
    int i, j ;

    for (i=n-1; i>=0; i--) {
        col[i] = board[i] ;
        for (j=i+1; j<n; j++) {
            if (col[i] <= col[j]) 
                col[j]++ ;
        }
    }

    // now, check for diagonals.. 
    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
            if (abs(col[i]-col[j]) == abs(j-i))
                return ;

    // we have a winner...
    total++ ;
    print(col, n) ;
}

void
place(int i, int n)
{
    if (i == n) {
        // check board 
        check(board, n) ;
    } else {
        int which ;
        for (which=0; which < n-i; which++) {
            board[i] = which ;
            // recurse...
            place(i+1, n) ;
        }
    }
}

int
main(int argc, char *argv[])
{
    int n = atoi(argv[1]) ;
    place(0, n) ;
    if (total == 0)
        fprintf(stderr, "There are no solutions for the %dx%d board..\n", n, n) ;
    else
        fprintf(stderr, "There is %d solution%s for the %dx%d board.\n", 
                total, total > 1 ? "s" : "", n, n) ;
    return 0 ;
}
Filed under: My Projects No Comments
26Apr/160

Streaming to twitch.tv with ffmpeg…

I was trying to figure out how to screencast to twitch.tv using ffmpeg. A couple of hours of tinkering resulted in the following command line which does a bunch of stuff.

  • It captures the X desktop at 15 fps and 1920x1080 resolution.
  • It grabs frames from my webcam (a Logitech Pro 9000) at 320x240 resolution.
  • It then combines the two into a 1024x576 image, with the video overlayed at the top right and a banner at the bottom that displays a couple of lines of text.
  • It then ships it to the twitch.tv server.  If you grab this code, you need to add your own streaming URL for your own channel.
#!/bin/bash

/home/markv/bin/ffmpeg 	\
	-y -thread_queue_size 64 -f x11grab -s 1920x1080 -framerate 15 -i :0.0+0,0 \
	-thread_queue_size 64 -f v4l2 -input_format mjpeg -framerate 5 -video_size 320x240 -i /dev/video0 \
	-filter_complex \
	"[0:v] scale=1024:576, setpts=PTS-STARTPTS  [bg]; \
	 [1:v] setpts=PTS-STARTPTS [fg]; \
	 color=0x336699cc:1024x64, drawtext=textfile=twitch.txt:fontfile=/usr/share/fonts/truetype/dejavu/DejaVuSansMono-Bold.ttf:x=10:y=16:fontsize=16:fontcolor=white [bottom] ; \
	 [bg][fg] overlay=W-w-16:16 [out2]; \
	 [out2][bottom] overlay=0:H-64, format=yuv420p [out]" \
	-map "[out]" \
	-vsync 1 \
	-c:v libx264 -b:v 500k -maxrate 500k -bufsize 1000k -framerate 15 -g 30 -crf 30 -preset fast -pix_fmt yuv420p -tune zerolatency \
	-f flv rtmp://live.twitch.tv/app/live_XXXXXXXX_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

A few additional notes:

  • The default DNS server for my ISP don't serve DNS requests for the live.twitch.tv server.   I fixed this by adding the Google DNS servers to my router (8.8.8.8 and 8.8.4.4).
  • The script appears to work pretty well, but sometimes has difficulty starting up.  And, when the script crashes, the remote clients don't time out for a considerable time.
  • I haven't tested this extensively.

Buyer beware, but I hope it is useful.

 

Filed under: My Projects No Comments
14Apr/165

Recommendations for tech to create a virtual hacker space?

Most of my hacking occurs in a vacuum: where I sit in my living room or in my home office and toil away silently on projects which occasionally get documented here, but which all too often are just my way of passing the time. On the way to work, I was asking myself what I could do to boost my own excitement about these projects, and provide some incentive to do more, and on a more regular basis.

So, I had an idea which is almost certainly not new: the idea of a virtual hackerspace.

For years, I used to donate my Friday evenings to the Chabot Amateur Telescope Makers workshop. I'd go down and spend three or four hours showing up, seeing who needed help on a telescope project, or I'd bring my own and work on that. I want to create a more generic "workshop network", where people can meet regularly for a kind of hackerspace parallel play using video conferencing technology.

In some sense, it's just an extension of Google Hangouts. The idea would be that each participant would have a webcam/microphone setup, and at the appointed time, we could all just open our cameras and mics, say "hi" to one another and then go about our business, potentially sharing our projects or asking questions of the group at large. I've mostly used Hangouts for simple one-to-one conversations, and have little experience with larger groups, and didn't really find any obvious links about how to manage larger groups. Does anyone have any recommendations on how to setup such a network? I am not really interested in creating a "show", but really more of a set of spaces which encourage mutual collaboration and interest.

I'm willing to entertain other technologies as well, if people have better suggestions.

And, if you would be interested in joining in this kind of "network", drop me a note here or on twitter (@brainwagon). I'll try to do an update of what I learn.

26Mar/162

More on Caxton Foster’s Blue Architecture…

Okay, it's been a long time since I wrote anything here. Not really a lot dramatic going on in life, I just have been spending my free time writing for Quora rather than my own blog. But I still am nerding out from time to time. Last night I dusted off an old project of mine and carried it a bit further...

I had written a short post before about a simulator I wrote for Caxton Foster's "Blue" computer architecture described in his book Computer Architecture. I have the third edition published in 1985. The "Blue" architecture is ridiculously simple: only sixteen instructions, 4096 words of memory, and only one addressing mode. If you click back to my previous post, you'll see a complete behavioral simulator for it, written in less than an hour.

Somehow this came back up, and I was suddenly intrigued by the idea of trying to write a simple program for it, just to test my ideas about how awful such a machine would be. Ultimately, my goal is to write a simple program that can compute the value of pi to around 100 decimal places. Such a program seems doable, but it's not a complete cakewalk. But to achieve this, I thought it might be fun to write a simple assembler.

So, I shook the cobwebs that have covered the bits of my brain that understood yacc/lex/bison/flex and wrote a simple assembler for the architecture. It totals only about 250 lines of code, but can handle symbolic labels and all the instructions. It took me about two hours of wall clock time, with my attention split between programming and watching the latest episode of Grimm.

I doubt the assembler is of any real interest, but eventually I'll get the code onto github.

I then sat down this morning, and wrote this simple program to take the signed value at the memory location VALUE and print it as a signed decimal number. It prints the sign then five digits, with leading zeros if necessary. I didn't bother to comment
the code, but here it is...

PRINTVALUE:
	LDA VALUE
	JMA NEG
	LDA PLUS
	OUT
POS:
	LDA S0
	STA TMP0
	SRJ DODIGIT
	LDA S1
	STA TMP0
	SRJ DODIGIT
	LDA S2
	STA TMP0
	SRJ DODIGIT
	LDA S3
	STA TMP0
	SRJ DODIGIT
	LDA S4
	STA TMP0
	SRJ DODIGIT
	HLT

DODIGIT:
	IOR JMPBIT
	STA RETURN
	LDA ZERO
	STA DIGIT
LOOP:	LDA VALUE
	ADD TMP0
	JMA DONE
	STA VALUE
	LDA DIGIT
	ADD ONE
	STA DIGIT
	JMP LOOP
DONE:
	LDA DIGIT
	ADD FE
	OUT
RETURN:
	JMP 0

NEG:
	LDA MINUS
	OUT
	LDA VALUE
	XOR ONES
	ADD ONE
	STA VALUE
	JMP POS

VALUE:	.WORD 12323
TMP0:	.WORD 0
DIGIT:	.WORD 0
S0:	.WORD -10000
S1:	.WORD -1000
S2:	.WORD -100
S3:	.WORD -10
S4:	.WORD -1
ZERO:	.WORD 0
ONE:	.WORD 1
ONES:	.WORD $FFFF
JMPBIT:	.WORD $A000
MINUS:	.STRING "-"
PLUS:	.STRING "+"
FE:	.WORD 48

The assembler spits out a series of 16 bit words which can be loaded into my
simulator...

0x602B, 0x9024, 0x6038, 0xC000, 0x602E, 0x702C, 0x8014, 0x602F, 
0x702C, 0x8014, 0x6030, 0x702C, 0x8014, 0x6031, 0x702C, 0x8014, 
0x6032, 0x702C, 0x8014, 0x0000, 0x4036, 0x7023, 0x6033, 0x702D, 
0x602B, 0x102C, 0x9020, 0x702B, 0x602D, 0x1034, 0x702D, 0xA018, 
0x602D, 0x1039, 0xC000, 0xA000, 0x6037, 0xC000, 0x602B, 0x2035, 
0x1034, 0x702B, 0xA004, 0x3023, 0x0000, 0x0000, 0xD8F0, 0xFC18, 
0xFF9C, 0xFFF6, 0xFFFF, 0x0000, 0x0001, 0xFFFF, 0xA000, 0x002D, 
0x002B, 0x0030, 

The data above gets simply compiled into my simulator and runs.

Screen Shot 2016-03-26 at 10.57.16 AM

Okay, so what's fun to note about this?

There is only a single register, the accumulator. You spend a LOT of time loading things, modifying the value, and storing them back into main memory. There is no "immediate mode", so you have to create memory locations to store common values like "1" and "0". DODIGIT is a subroutine, which is called by the SRJ instruction. SRJ puts the PC into the accumulator, and then jumps to the specified address. To "return", you OR in the bits to the accumulator to form a JMP instruction, and then store that at the end of your subroutine. There is no call stack. Although not demonstrated particularly here, the processor does not implement indexing or indirection. There is also no real condition registers such as CARRY or OVERFLOW, so implementing multi-precision arithmetic might be a challenge.

Foster's book also details additions to this architecture, eventually becoming INDIGO, an architecture which is rather similar to a PDP-8.

Sure, if you are going to really learn computer archtictures, Patterson and Hennessy is probably a better path, but there is something like of pleasing in this archaic trip down memory lane. My pi computing program will percolate in my brain for a bit, and will find implementation on some other evening.

Addendum: Hackaday recently posted about Al Williams' FPGA implementation of an architecture which is based upon Foster's Blue machine. I believe he made a number of changes that make it more practical, but it might be worth looking at. He wrote a monitor, which seems to use opcodes which aren't compatible with mine.

Addendum2: Pondering it some more throughout the day, it seems difficult to implement my idea of a pi computing program for this virtual machine. All of the algorithms that I can think of require 32 bit numbers, and the Blue architecture simply lacks the capabilities needed to implement it. It also is pretty weak on conditional statements: the only condition that you can branch on is the sign bit of the accumulator.

25Jan/160

Quadcopter Survey with my DJI Phantom 2/GoPro

I hadn't been flying my DJI Phantom 2 since last year (before I herniated two disks in my neck) but I've been meaning to take it out and get it in the the air. This week, two different things happened which provided some incentives to get it in the air, for reasons which weren't entirely frivolous:

  • My new next door neighbor mentioned that there was debris in the drainage ditches up on the hill that drain from his yard to my yard. I thought that it had been cleaned out, so I wanted to be sure, but frankly, hiking up there when the ground is wet is asking for a new herniated disk.
  • I had a small roof leak which caused a call to my roofers to come out and have a peek. They mentioned that I had a fair number of busted tiles on my roof (annoying, perhaps broken by our contractors during last years remodel?).

I hadn't flown in a while, so I decided that rather than flying over my house, I'd begin by just getting the view of the drainage ditches. I got the copter charged up again, reviewed my checklists, and took it out into the backyard.

Oddly, I heard a familiar droning: one of my neighbors had a quadcopter up doing a high pass over the neighborhood. By the time I was ready though, it had sailed back off to the south. I got it up in the air and tried to get my coordination back. It was a beautiful day for flying.

Here's a nice high view to the north east from my house, fairly high up.

vlcsnap-2016-01-24-16h43m07s108

But that wasn't what I was after: I aimed the GoPro down and flew fairly low over my hill to get these pictures. This is the view of the lower of the two drainage ditches. It's got a little silt in it, but is pretty clear. It might be worthwhile to do a concrete patch of the seam. You can also see a fair number of gopher holes up on the hill.

vlcsnap-2016-01-24-16h42m37s703

The other ditch is at the top of the hill. It actually gets a lot less water, so the silt settles out pretty well up there, and I've got some grass growing it. It could definitely use some work to clear it.

vlcsnap-2016-01-24-16h42m21s229

Very nice! Perhaps next weekend I'll do a flight over the house and see if I can identify broken roof tiles. I'm pretty glad I didn't have to hike up there to check it out. Kind of wish I had an FPV setup. Perhaps I'll get that going in the not-too-distant future.

21Sep/151

On calculators, Space Invaders and Binary Coded Decimal Arithmetic…

A couple days ago, one of my Twitter or Facebook friends (sadly, I forgot who, comment if it was you, and I'll give you credit) pointed out this awesome page:

Reversing Sinclair's amazing 1974 calculator hack - half the ROM of the HP-35

It documented an interesting calculator made by Sinclair in the 1970s. It is an awesome hack that was used to create a full scientific calculator with logarithms and trigonometric functions out of an inexpensive chip from TI which could (only barely) do add, subtract, multiply and divide. The page's author, Ken Shirriff, wrote a nifty little simulator for the calculator that runs in the browser. Very cute. It got me thinking about the bizarre little chip that was at the center of this device.

I'm kind of back in an emulator kick. I recently had dusted off my code that I had started for emulating the 8080 processor. I had originally wanted to implement a version of CP/M, but I remembered that the 1978 game Space Invaders was also based upon the 8080. It wasn't hard to find a ROM file for it, and with a little bit of hacking, research and debugging, I had my own version of Space Invaders written in C and using SDL2, running on my Mac laptop.

Screen Shot 2015-09-16 at 12.46.01 PM

Fun stuff.  The sound is a little crude: most of the sound in the original game was generated by a series of discrete circuits which you can find on this page archived via the Wayback Machine. I briefly played around with simulating some of the sounds using LTSpice based upon these circuits (it appears to work fairly well), but I haven't got that fully integrated into my simulator yet. For now, it just queues up some recorded sounds and plays them at the appropriate time. Everything is currently working except for the classic "thump... thump..." of their marching. I'll get that working sometime soon.

Anyway, back to calculators. One thing on Ken's page kind of made me think: he mentioned that the HP-35 had taken two years, twenty engineers, and a million dollars to develop. Mind you, the HP-35 was pretty revolutionary for its time. But I thought to myself "isn't a calculator an easy hobby project now?"

After all, I had assembled a KIM-Uno, Oscar's awesome little $10 board that emulates the KIM-1 microcomputer:

In fact, the KIM-Uno implements a floating point calculator as well. It's brains are just an ordinary Arduino Pro Mini wired on the back. Arduino Pro Minis can be had for less than $3 from China. Could I make a fun little calculator using that as the basis?

My mind is obviously skipping around a lot at this point.

Of course, a bit more googling revealed that someone had done something very similar using the MSP430 chips from (appropriately enough, also manufactured by Texas Instruments). Check out the build thread here.. It's pretty nifty, and uses a coin cell to drive it, as well as some very classic looking "bubble LED displays", which you can get from Sparkfun. Pretty cool.

Anyway...

For fun, I thought it might be fun to write some routines to do binary coded decimal arithmetic. My last real experience with it was on the 6502 decades ago, and I had never done anything very sophisticated with it. I understood the basic ideas, but I needed some refresher, and was wondering what kind of bit twiddling hacks could be used to implement the basic operations. Luckily, I stumbled onto Douglas Jones' page on implementing BCD arithmetic, which is just what the doctor ordered. He pointed out some cool tricks and wrinkles associated with various bits of padding and the like. I thought I'd code up a simple set of routines that stored 8 BCD digits in a standard 32 bit integer. His page didn't include multiplication or division. Multiplication was simple enough to do (at least in this slightly crazy "repeated addition" way) but I'll have to work a bit harder to make division work. I'm not sure I really know the proper way to handle overflow and the sign bits (my multiplication currently multiplies two 8 digit numbers, and only returns the low 8 digits of the result). But.. it seems to work.

And since I haven't been posting stuff to my blog lately, this is an attempt to get back to it.

Without further ado, here is some code:

/*
 * A simple implementation of the ideas/algorithms in 
 * http://homepage.cs.uiowa.edu/~jones/bcd/bcd.html
 *
 * Written with the idea of potentially doing a simple calculator that
 * uses BCD arithmetic.
 */

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

typedef uint32_t bcd8 ;         /* 8 digits packed bcd */

int
valid(bcd8 a)
{
    bcd8 t1, t2, t3, t4 ;
    t1 = a + 0x06666666 ;
    t2 = a ^ 0x06666666 ;
    t3 = t1 ^ t2 ;
    t4 = t3 & 0x111111110 ;
    return t4 ? 0 : 1 ;
}

bcd8
add(bcd8 a, bcd8 b)
{
    bcd8 t1, t2, t3, t4, t5, t6 ;

    t1 = a + 0x06666666 ;
    t2 = t1 + b ;
    t3 = t1 ^ b ;
    t4 = t2 ^ t3 ;
    t5 = ~t4 & 0x11111110 ;
    t6 = (t5 >> 2) | (t5 >> 3) ;
    return t2 - t6 ;
}

bcd8
tencomp(bcd8 a)
{
    bcd8 t1 ;

    t1 = 0xF9999999 - a ;
    return add(t1, 0x00000001) ;
}

bcd8
sub(bcd8 a, bcd8 b)
{
    return add(a, tencomp(b)) ;
}

bcd8
mult(bcd8 a, bcd8 b)
{
    bcd8 result = 0 ;
    bcd8 tmp = a ;
    bcd8 digit ;
    int i, j ;

    for (i=0; i<8; i++) {

        digit = b & 0xF ;
        b >>= 4 ;

        for (j=0; j<digit; j++)
            result = add(result, tmp) ;

        tmp <<= 4 ;
    }
    return result ;
}

int 
main(int argc, char *argv[])
{
    bcd8 t = 0x00009134 ;
    bcd8 u = 0x00005147 ;
    bcd8 r ;

    r = mult(t, u) ;
    printf("%X * %X = %X\n", t, u, r) ;
}

I'll have to play around with this some more. It shouldn't be hard to move code like this to run on the Arduino Pro Mini, and drive 3 bubble displays (yielding 11 digits plus a sign bit) of precision. And I may not use this 8 digits packed into 32 bit format: since I want 12 digits, maybe packing only 4 digits into a 32 bit word would work out better.

Anyway, it's all kind of fun to think about the clanking clockwork that lived inside these primitive machines.

I'll try to post more often soon.

4Jul/150

The Kim-Uno — a Kim-1 simulator

Ken Boak had mentioned on twitter that someone was creating a blinken-lights front end for the simh simulator of the PDP-8, called the PiDP-8, since you can power the entire thing from a Raspberry Pi. Very cool, but not quite available yet. What was available from Oscar is the Kim-Uno, a simulator for the old KIM-1 computer, a single board computer based upon the MOS6502 with a simple LED display and a whopping 1K of memory, first shipped in 1977 or so for about $245. The simulator is incredibly simple: a board, buttons, leds, and an Arduino Micro to drive it all. I went ahead and ordered one, just for kicks.

But you don't actually need the hardware to play with this: you can get the code running on an ordinary Arduino Uno. So I did. It's setup to run Microchess out of the box. Microchess is cool because it can play chess in less than 1K of code, and probably was the first commercial game software produced for hobbyist computers.

The Kim-Uno sketch is a little bit odd though. I've begun tinkering with it, and cleaning it up a bit. First of all, I thought it was confusing the way it tried to include the 6502 core emulation (written by Mike Chambers). It is written in C, and to merge it into the sketch required a bit of chicanery using 'extern "C"' directives. Bleh, I renamed cpu.c to cpu.cpp, and cleaned that up. I fixed some forward declarations. I uncovered a couple of bugs by paying attention to compiler warnings. It won't even come close to compiling on non-Arduino platforms, so I deleted lots of conditional definitions. And I generally just tidied things up. Along the way, I checked out the code that Oscar put in to scan the six digit display, which took a lot of pins. As is happens, I had an 8 digit display which used the 74HC595, which I had gotten working before using an interrupt driven display driver. I merged that code in, and now I had a hardware display like the Kim wired to my Uno. Probably refreshes more often than the original, but looks great!

When I get my code tidied up more, you'll be able to download it on github. Stay tuned.

1Jun/153

Driving an 8 digit, 7 segment display based upon the 74HC595…

A few weeks ago, I was scanning the Deal Extreme website, and ordered a few different LED displays, not because of any pressing need, but because I wanted to have some display options available if I needed some for a project. I was especially interested in cheap LED displays. One of the ones I ordered was this 8 digit, 7 segment display, which seemed to have a five pin interface. Without thinking about it too much, I went ahead and ordered it.

Today, they arrived. Like a lot of things that come from dealextreme, this one had been shipped somewhat haphazardly: the right angle header pins were significantly bent, but a little gentle prodding moved them back into place. I then spent a few minutes trying to decide what the module actually needed.

Unlike the modules I've had previously based upon the TM1637/TM1638/TM1640, these modules did not have a controller onboard that could latch all the segments and hold values. Instead, this board has 2 8 bit shift registers (namely, the 74HC595). Basically, one shift register controls which of the 8 digits are powered up (a high value in the 8 bit word indicates that the corresponding digit has a power on its cathode (which is common to all the segments of the LED) and the other 8 bit word tells it which segment is turned on (actually, it's inverted: a 1 indicates the corresponding segment is off).

But here lies the rub: you only have 8+8 control lines, but you have to control 56 (actually 64 if you include the decimal points) segments. The way you get around this is to display a single digit at a time, but only do it for a short period of time. If you flip between digits fast enough, your persistence of vision will merge them into a consistent display.

The usual way to do this with an Arduino would be to use the shiftOut statement to clock the data out on some serial pins, and then call delay (or delayMicrosecond) to wait a bit, then shift the data out for the next digit, etc... But that makes the loop() difficult to write: you have to interleave both the display and all the other work that you have to do, with careful attention to timing.

There is a better way: interrupts. In particular, I used the TimerOne library (available on the Teensy as well as the Arduino libraries) to setup a timer interrupt. The idea is to contain a display buffer of 8 bytes, one byte per digit, which specifies which of the 8 segments is on. When the interrupt occurs, it clocks out the cathode and then the segments for the specified digit as quickly as it can, and then increments the display digit by one, wrapping around if necessary. Because this happens in an interrupt, it means that display happens without any real use intervention. When you want to change what is displayed on the display, you just change the contents of the segment buffer and then the interrupt fires next time, the appropriate digit will
be displayed.

The basic code worked the first time I typed it in (modulo plugging jumpers into the wrong pins on the Teensy, and with the digits occurring in the reverse order than I desired). A moments tweaking yielded this nice, steady display:

I've decided that rather than posting code fragments embedded here, I will instead post links to a github repository that holds the necessary code. As I extend and make improvements, you'll be able to get updated code there.

28May/153

A 4 digit, 7 segment display board based upon the TM1637 chipset…

Yesterday, I got a small 4 digit, 7 segment LED display board in the mail from dx.com. Cost was around $3 shipped, and the module uses a 4 pin interface (power, ground, clock and data). Originally, I thought it was I2C, but like other modules I have received based upon chipsets made by Titan Micro (using the TM1638 and TM1640) it looks superficially like I2C, but doesn't use the open collector bus and addressing scheme of I2C. You end up clocking commands to the board using two dedicated pins.

The driver that I'm using comes from here. It is based upon the driver from avishorp, but includes support for the colon that separates the two pairs of digits on this display, which I wanted to allow blinking to help indicate that the clock was running. This was my example sketch, which is completely unremarkable. It doesn't set the time from a real source, I just hard coded it to set the time to a specific constant near when I compiled it.

#include <Time.h>
#include <TM1637Display.h>

#define CLK 2
#define DIO 3

TM1637Display display(CLK, DIO);

void setup() {
  Serial.begin(9600);
  // put your setup code here, to run once:
  setTime(1432823831UL);
  display.setBrightness(0xF);

}

boolean colon = true ;

void loop() {
  
  // put your main code here, to run repeatedly:
  int t = hour() * 100 + minute() ;
  display.setColon(colon);
  colon = !colon ;
  display.showNumberDec(t, true);
  delay(1000) ;
}

It works reasonably well.


Addendum: I received this tweet:


Not a bad little trick to archive. Instead of using the Time library, you need to use the RTClib library. I modified my program above to do it. Here's the new version:

#include <Wire.h>
#include <RTClib.h>
#include <TM1637Display.h>

RTC_Millis rtc;

#define CLK 2
#define DIO 3

TM1637Display display(CLK, DIO);

void setup() {
  Serial.begin(9600);
  display.setBrightness(0xF);
  rtc.begin(DateTime(F(__DATE__), F(__TIME__))) ;
}

boolean colon = true ;

void loop() {
  DateTime now = rtc.now() ;
  int t = now.hour() * 100 + now.minute() ;
  ;
  display.setColon(colon);
  colon = !colon ;
  display.showNumberDec(t, true);
  delay(1000) ;
}

Note: the time gets set to the time when the code is compiled. If you compile and install it, it will likely be a couple of seconds off. And when the Arduino gets reset, it will get reset to that same time. This is most useful in setting the time on an external time keeping module.