brainwagon

Another of my attempts to make pictures from volume data…

Well, i’ve had a couple of days to muck around with the ASUS WL-520G (hereafter revered to as “the ASUS” or “the router”) and OpenWRT. I have had a modicum of success, as well as a modicum of failure, so I thought I’d give an update.

For my beacon transmitter, it is important that the router maintain a fairly accurate clock, because WSPR beacon transmissions occur at the beginning of even number minutes. So, I thought the first thing that I should be do is to get ntp running on the router, to make sure that the clock timing was good. There is a minimal ntp client called, quite appropriately, ntpclient, which I added to the configuration. I also thought that it would be good to add a slightly more capable HTTP server, rather than the minimal one built into busybox. I recompiled and installed.

And immediately found out that ntpclient didn’t work. It set the clock initially, but the clock was immediately sliding away from synchronization. I killed ntpclient, and it was still slipping sharply, losing about 11 seconds every minute. I knew that there were limits to how big a drift that ntp could correct, so I did some careful googling.

It appears that there is some lingering problem with this particular device. Without getting too far into it, there is code in the sbmips.c file which claims that the clock rate for this box is 240Mhz, but in reality, it appears to be 200Mhz. Changing this number and recompiling results in a clock which is reasonably accurate, and which ntpclient can easily correct, but also appears to cause a problems with the flash memory “mtd” driver. I’m currently trying to work that out.

Addendum: Hmm. I shifted to the “trunk” instead of the stable 8.09 release, and this problem seems to have gone away. I still needed to patch sbmips.c, but it seems to work fine now.

People who read this blog might have noticed that I have a love of devices that have firmware that can be subverted for other purposes. I have a Canon SD1100 that runs the CHDK firmware. I have a couple of Linksys WRT54G routers. I have an old NSLU2 that I haven’t goofed around with in a while. I experimented with an old Linksys VOIP adapter. I’m kind of a nut.

During the Makers Faire, I noted this cool project, which converted an ASUS WL-520GU into a Wifi Internet Radio. I thought it was particularly interesting because the router hardware was cheap (only $35 after rebate from newegg.com) and because it included a USB port, meaning that it could conceivably be hooked to other interesting devices (the mightyohm project uses it to control a sound card).

How could I resist? I bought one!

And then, I created a custom distribution of OpenWRT. And, if you follow the next link, you’ll get served a webpage which is served on the router.

A webpage served from the ASUS WL-520GU

More developments coming soon.

At the Maker Faire this weekend, I picked up a Waveshield kit for the Arduino. It’s a cute little board with an SD card interface, an I2C DAC, and a little op amp circuit to provide an audio interface. It took me about an hour and a half to solder together (I’m slow, but careful) but it doesn’t appear to work. I’m suspecting a software, rather than a hardware issue. I downloaded the “playall” example, which simply plays all the audio files on your SD card, but it appears that it runs the setup() code properly, but resets the CPU somehow before ever running loop(). Lady Ada’s documentation suggests that I could be running out of RAM (my Arduino is one of the older NG ones, and has only 1K of ram, but still….) Probing with an oscilloscope reveals relatively few active signals on the top of the board when the program is running, which suggests that it’s not even trying to clock the audio data out. I was thinking of writing a simple program that just exercises the DAC first, to make sure that the board works (generating a square or triangle wav is pretty easier) since I think it’s the SD card that gobbles memory.

Anybody whose gotten one of these to work, I’d appreciate the help.

My idea is to use this to store prerecorded voice messages, and then use it to key a small FM transmitter and send voice telemetry for my balloon project.

Okay, before I get too excited, I’ll disclose that Cake was set to a time limit of around 1 second, which limited it to just a few ply (maybe 9 typically) and I was letting MIlhouse think a little harder (still taking less than 10 seconds typically). Still, it’s good: it means that sparring matches between milhouse and cake can be tuned to make them challenging. I need to figure out how I can build milhouse as an engine for CheckerBoard so this can be automated.

Perhaps I could use mingw to build an appropriate dll.

[Event "Morning Match"]
[Date "2009-05-04"]
[Black "Cake, 1sec per move"]
[White "Milhouse, 19 ply search"]
[Result "0-1"]
1. 9-13 23-19 2. 6-9 27-23 3. 11-15 23-18 4. 8-11 26-23 5. 4-8 30-26 6. 9-14 18x9 7. 5x14
22-18 8. 15x22 25x9 9. 11-16 9-6 10. 2x9 24-20 11. 8-11 26-22 12. 10-15 19x10 13. 7x14
29-25 14. 16-19 23x7 15. 3x10 28-24 16. 10-15 32-28 17. 14-18 24-19 18. 15x24 22x15 19.
9-14 28x19 20. 14-18 15-10 21. 12-16 19x12 22. 13-17 21x14 23. 18-22 25x18 24. 1-5 31-27
25. 5-9 14x5 0-1

I finally got around to totally ripping out the old implementation of transposition tables, and installing a new one based upon hints I read about on various web pages, mostly originating with some of the ideas for cache management that Ken Thompson implemented for his chess program Belle. The idea is to implement two caches, one of which is used to store board positions near the root of the tree, the other which contains all other nodes. The idea is that if you cache near the leaves, then you are likely to need the same values again soon, but if you cache higher up in the tree, you are more likely to save yourself long searches.

Using this, I managed to get my “two king vs. one king” endgames working, searching out 33 ply in just a few seconds.

LOADED puzzle 173: Simple Tests (harder)..
Color is set to red.
           White
        +--------+
        | R - - R|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - W |
        +--------+
           Red    

milhouse: depth 40
search depth is now 40
milhouse: playout
     1. 29-25 {10000}   1-5 {-10000}
     2. 25-21 {10000}   5-1 {-10000}
     3. 21-17 {10000}   1-5 {-10000}
     4. 17-13 {10000}   5-1 {-10000}
     5. 32-27 {10000}   1-5 {-10000}
     6. 27-23 {10000}   5-1 {-10000}
     7. 23-18 {10000}   1-5 {-10000}
     8. 18-14 {10000}   5-1 {-10000}
     9.  13-9 {10000}   1-5 {-10000}
    10.   9-6 {10000}   5-1 {-10000}
           White
        +--------+
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - R -|
        |- - - W |
        +--------+
           Red    

milhouse: playout
     1. 14-10 {10000}   1-5 {-10000}
     2.   6-1 {10000}   5-9 {-10000}
     3.   1-5 {10000}  9-13 {-10000}
     4. 10-15 {10000} 13-17 {-10000}
     5. 15-18 {10000} 17-13 {-10000}
     6. 18-22 {10000}  13-9 {-10000}
     7.  5x14 {10000}
           White
        +--------+
        | - - - -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - - -|
        |- - - - |
        +--------+
           Red    

milhouse:

I then tried to play a game against the novice level of Chinook. I ended up in this position, with Chinook playing white and Milhouse black. Chinook kept bragging that I was in “serious trouble”, but the reality is that the position is drawn, and once in a six piece drawn end game, Milhouse won’t stumble (barring bugs) so I called this a draw.

As some of you may have noticed, I occasionally like to write small programs to compute odd little mathematical curiousities. Something I hadn’t done in a long while was to use the Sieve of Eratosthenes to compute a bunch of prime numbers. I suspect that I wrote such a program very early in my exploration of computers, maybe thirty years ago. The basic algorithm is pretty straightforward, but takes O(N) space to find the primes less than N. It’s not hard to reduce the storage to N bits, and with a trivial bit of work you can reduce it to N/2 bits, and with a little more, you can reduce it to 4/15 N bits. That was fun to work out.

But last night I did something a bit different: I implemented a simple “segmented sieve”. Basically, the idea is that to generate all the primes up to N, you find all the primes up to sqrt(N), and save those. Then, you process the rest of the numbers in buffers of sqrt(N) at a time, by sieving each buffer with your saved primes. It’s a really simple idea, but makes sieving larger numbers more practical. I implemented the simplest possible version of this last night, and set it going to compute all the prime numbers up to 1E12. Here’s the log from the run:

[chessboard] % time ./bigsieve 1000000000000 > output
20580.222u 18.741s 5:43:39.10 99.9%     0+0k 0+0io 0pf+0w

And here’s the output file:

78498 primes less than 1000000
148933 primes less than 2000000
216816 primes less than 3000000
283146 primes less than 4000000
348513 primes less than 5000000
412849 primes less than 6000000
476648 primes less than 7000000
539777 primes less than 8000000
602489 primes less than 9000000
664579 primes less than 10000000
...999989 lines deleted...
37607912018 primes less than 1000000000000

The program doesn’t include any of the basic optimizations, I suspect it woudn’t be difficult to make this thing a factor of 2-4 faster without adding a ton of code. I’ll probably see if I can do that over the next few days. It’s a useless but fun project.

Well, I dusted off my checkers program source code and compiled it on my Mac. It managed to actually solve this position: a rather common one that checkers novices can’t often convert into a win. Black to move and win. My program seems to find the winning line, but only using a search significantly deeper than I think should be necessary to find it (the forced capture is 15 ply out from the start position). I’ll investigate more.

In fact, at the moment, it’s the largest known prime, with over 9.8 million digits. As part of my pi day celebration yesterday, I was trying to review how I might speed up my C code which calculates pi to large numbers of digits. Most of the fast ways rely on fast multiplication, utilizing the FFT algorithm. I wasn’t sure how that really worked.

So… I decided to write a program to learn and test my knowledge.

Rather than compute pi though, I thought I might try a somewhat different but similar task that relied on big number computation. I remembered that Fabrice Bellard had an obfuscated C code entry that used an integer Fast Fourier Transform to print out the largest (then) known prime. It’s really quite nifty. I decided to try to implement a similar thing, but rather than starting with his obfuscated code, I decided that I’d try to use the FFTW library to do the same.

It’s a tiny bit tricky: after all, we are using a floating point FFT to multiply large integers, and getting the precision issues nailed isn’t entirely obvious. My original idea was to represent the large numbers in base 100000 (giving five decimal digits per place) but for reasons which aren’t entirely clear to me, when computing the current largest prime, I seemed to run out of precision. Limiting myself to base 10000 seems to have cured the problem.

My program seems to work (at least minimally) now. I can compute Bellard’s number (2**6972593-1) in about 9.7 seconds, and the largest known prime (2**32582657-1) in about 53 seconds. Ironically, such numbers are really easy to output in base two: they are just lots of ones. But to convert them to base ten for formatting in the way us humans like is much more complicated.

The final output looks like:

 12,457,502,601,536,945,540,085,550,157,479,950,312,279,598,515,115,184
284,367,047,566,259,111,523,599,739,738,055,975,960,661,684,593,910,041
988,688,211,130,870,620,428,490,430,485,634,271,939,241,796,764,631,759
...
... 181631 lines deleted for brevity
...
826,726,604,958,937,322,582,512,072,612,621,443,114,535,641,869,584,273
577,446,330,457,465,821,333,212,445,737,104,635,692,000,092,659,011,752
880,154,053,967,871

I have double checked this against the official value on mersenne.org, and it matches precisely. I know that the program hides at least one gross inefficiency still: I suspect that I can actually compute the large prime in just about twelve seconds. But my head hurts for the moment, and I think I’ll pass for now.

It now can put out ground tracks as well as more detailed tracking information. Just a few more lines of code.

ARISS will be visible from grid CM87ux starting in 01:36:47 at 23:08:11
  23:08:11  +0.0°  210.7° ?  21.8°N 132.1°W  AOS
  23:09:00  +3.4°  207.9° ?  24.2°N 130.0°W
  23:10:00  +8.5°  202.5° ?  27.0°N 127.2°W
  23:11:00 +15.8°  192.4° ?  29.8°N 124.3°W
  23:12:00 +26.4°  170.1° ?  32.5°N 121.2°W
  23:12:51 +32.2°  132.9° ?  34.8°N 118.4°W  MAX
  23:13:00 +31.8°  125.4° ?  35.2°N 117.9°W
  23:14:00 +22.3°   88.7° ?  37.7°N 114.4°W
  23:15:00 +13.0°   72.4° ?  40.1°N 110.6°W
  23:16:00  +6.7°   64.6° ?  42.3°N 106.5°W
  23:17:00  +2.0°   60.2° ?  44.4°N 102.1°W
  23:17:31  +0.0°   58.7° ?  45.3°N  99.7°W  LOS

P.S. Sigh, wordpress is apparently working very hard to get rid of the Unicode characters I nicely output. To the right of the azimuth/elevation should appear a sequence of arrows to indicate if you should look north, south, east or west. When I run this on my terminal, I get:

I’ll have to work on deciding whether this Unicode stuff is worth the trouble. Probably not.

Well, my plan13 library has been joined with a library that decodes grid squares and the like, and another which downloads orbital elements and stores them in an sqlite3 database. The combination of all these allows you to write simple programs like the one I illustrate below, which gives predictions of the named satellites from any grid (defaulting of course to my own gridsquare). Witness:

[chessboard] % ./nextpass -v ARISS AO-27 SO-50 AO-51
ARISS [+] will be visible from CM87 in 0:54:30 at 02:51:30
        AOS: 02:51:29  -0.0°  163.2°
        MAX: 02:54:29  +4.4°  124.1°
        LOS: 02:57:27  +0.0°   86.0°
AO-27 [+] will be visible from CM87 in 7:53:15 at 09:50:15
        AOS: 09:50:11  -0.0°   46.9°
        MAX: 09:55:01  +6.2°   87.2°
        LOS: 09:59:45  +0.0°  127.0°
SO-50 [+] will be visible from CM87 in 6:16:45 at 08:13:45
        AOS: 08:13:44  -0.0°  159.7°
        MAX: 08:19:09 +12.3°  106.6°
        LOS: 08:24:47  +0.0°   53.6°
AO-51 [+] will be visible from CM87 in 0:42:30 at 02:39:30
        AOS: 02:39:23  -0.0°  146.5°
        MAX: 02:46:48 +41.0°   69.8°
        LOS: 02:54:14  +0.0°  356.3°

My old program for drawing globes made some nice postscript output, but in reexamining the source code, I can only imagine that I was doped up on cough medicine while working on it. I started a bit on a revamp of it, starting by purloining the matrix and vector library that I used in my old raytracer and swiping the outline data from xearth. A couple of hours of TV watching and coding later, and I have the basics fleshed out:

I’m not 100% satisfied with it, since the coordinate system that it currently uses is the default one that xearth uses, and which is not the same as used by the internals of the plan13 code that I will eventually interface to it. It’s not
especially critical, but I think it makes a less clear presentation. I’ll tighten it up later.

It also doesn’t do any filling of the continent outlines, which I’m not really sure is a flaw: my goal is not to present a photorealistic view of the earth, but rather to show a clear schematic of the path of satellites as they orbit the earth. Still, I’ll give it some thought.

If you’ve listened to some of my satellite audio, you’ll notice that in addition to the callsigns, people are exchanging things that sound like “Delta Mike 41″ or “Charlie Mike 87″. These are Maidenhead gridsquares: a system of rapidly transmitting your rough location. The kind most commonly heard are the ones that are 4 characters long (two alpha, followed by two digits), but it’s also not uncommon to have them be length six (two uppercase alpha, two digits, two lower case). Converting back and forth between grids and latitude and longitude is fairly simple, there are existing programs like geoid and wwl that can do it. But I decided to code up a Python library to do it. As a simple test, it takes two grid descriptors, and determines the bearing and the distance between both points. For instance, when I run python maidensquare.py CM87 BL11, I get the following:

CM87 -> BL11: bearing 251.0° distance: 2315.3 miles
BL11 -> CM87: bearing  54.0° distance: 2315.3 miles

BL11 is the gridsquare of NH7WN in Hawaii, which is, as you can see, south west of my location. You should also note that the return trip isn’t 180 degrees opposite the outgoing trip direction. That’s because these are directions on the sphere along great circle paths, and normal geometric invariants (such as the angles of a triangle adding up to 180°) simply don’t apply on the surface of a sphere.

I’m going to add this to my growing body of Python code, and will release it someday soon. Drop me an email if you’d like to try to test it out a bit more (warning: it’s mostly for programmers).

I got a pretty good recording of the NOAA17 pass today, and converted it with my software. Turned out very nice. You can see Catalina and San Clemente Island off the coast of California. One of my better ones to date.

Addendum: I didn’t use my Radio Shack scanner for this, I used my little Yaesu VX-3R instead. I’m beginning to suspect it is a good deal more sensitive than the scanner, although it’s really hard to tell.

Well, I’ve made some headway on a project that I thought would be cool to write: porting G3RUH’s Plan 13 Satellite Prediction algorithm to a more palateable language than BASIC. I chose python, and it appears to be mostly working. It reads in the TLE orbital elements (same ones I use in “predict” or “gpredict”) and then allows you to create a bunch of satellite objects, and query their positions over time.

Here’s a screendump of a simple test program that I was running this morning:

Satellites which are above the horizon are marked in bold. They are sorted by elevation. The datafields displayed are elevation, azimuth, latitude and longitude of the subsatellite point, velocity, the Doppler velocity, and the frequency of a signal Doppler shifted from 435.845Mhz (just a value I did to check, since I was using PolySat CP3 at the time, which has APRS telemetry downlinked on that frequency). The code requires some additional cleanup, and once I have it all ready to go and documented, I’ll make it available. I think it will have a lot of uses.