Jeff Epler's blog

30 April 2018, 22:42 UTC

All integers 0 through 1,000,000 from short, digitless dc programs

I now have solutions for all the numbers in this range. The longest program required is 12 bytes. The final program found was for the number 966422: "BABAd*EC/C+n"

I consider the 23 characters " ~^-/*+|ABCDdEFIinOorvz", but prune all prefixes which are invalid due to stack underflow. 2312 is around 2.2×1016 or 254, but best guess my various programs have considered only around 5×1012 or 242 due to this pruning. Still, the process (including iteratively developing the search program) has taken several months!

What's next? I guess there's always the "fours puzzle", dc edition.

      4 4n
     10 In
      0 zn
     44 44n
      2 4vn
      1 4zn
      3 Ivn
    444 444n
      6 44vn
     40 4I*n

Files currently attached to this page:



23 April 2018, 2:50 UTC

Code size for bit reversing algorithms

I want to add support for "LSB first" to bitbang SPI in circuitpython. Probably the best way to do this is to optionally reverse the bits in each byte according to a flag setting.

Code space is always at a premium, so I investigated several code fragments for bit reversal to find out which was smallest on arm and xtensa. These code fragments are gathered from the internet. The loop is the smallest alternative on both architectures, but the 16-element look up table is not much bigger (on arm, the difference is bigger on xtensa) and is probably faster.

arm-none-eabi-gcc-7.2.1 -Os -mthumb

   text    data     bss     dec     hex filename
     40       0       0      40      28 bitrev_loop.o
     44       0       0      44      2c bitrev_lut16.o
     44       0       0      44      2c bitrev_shifts1.o
     44       0       0      44      2c bitrev_twiddle1.o

xtensa-lx106-elf-gcc-4.8.5 -Os

   text    data     bss     dec     hex filename
     40       0       0      40      28 bitrev_loop.o
     53       0       0      53      35 bitrev_lut16.o
     57       0       0      57      39 bitrev_shifts1.o
     52       0       0      52      34 bitrev_twiddle1.o

Files currently attached to this page:

bitrev_loop.c138 bytes
bitrev_lut16.c281 bytes
bitrev_shifts1.c193 bytes
bitrev_twiddle1.c178 bytes


26 March 2018, 23:51 UTC

Fuzz-testing CircuitPython

I've been hacking on CircuitPython lately. A lot of what I've done is fix bugs found by afl. Here's how to try it for yourself:

I recommend that you use a throwaway virtual machine for this, because at one point afl-fuzz learned how to create files in the filesystem! that was a big surprise, waking up to a directory full of filenames like "tesppppppppppppppppppppppppppppptfile"!

First, make sure you can build circuitpython's unix port. The steps are, approximately,

  1. Clone circuitpython
  2. git submodule update --init --recursive
  3. make -C ports/unix -j5 deplibs
  4. make -C ports/unix -j5
(you can review the .travis.yml file in the CircuitPython source tree for the packages they install on top of a regular Ubuntu system to get it building)

Note that the executable is ports/unix/micropython even when you have cloned circuitpython.

Next, get afl from If you can, follow the instructions in llvm_mode/README.llvm to get afl-clang-fast. Now, clean and rebuild:

  1. make -C ports/unix clean
  2. make -C ports/unix CC=/path/to/afl-clang-fast -j5 deplibs
  3. make -C ports/unix CC=/path/to/afl-clang-fast -j5
(If you couldn't use afl-clang-fast, then use CC=afl-clang or CC=afl-gcc)

Prepare the testcases directory for afl-fuzz. I used a number of tests from tests/basic:

  1. mkdir testcases
  2. cp tests/basics/*.py testcases

And start the fuzzer:

  1. /path/to/afl-fuzz -i testcases -o findings -- ports/unix/circuitpython

If you have any good findings, drop by the adafruit circuitpython discord and let us know about them! Even better if you fix them.


17 February 2018, 17:31 UTC

Watch Repairs

My friend, "Time Guy" Chris Radek has gotten back into the watch repair business! He writes:

After a 15-year break, I'm now accepting repair work again!

I do everything from routine cleaning and oiling (full disassembly and inspection, multi-stage ultrasonic cleaning, reassembly and correct oiling using appropriate modern synthetic oils, timing and adjustment as necessary) of automatic and manual-wind wrist and pocket watches to manufacture of unavailable parts for chronographs or repeaters.

I specialize in Accutron tuning fork watches and I have a large stock of parts and many years of experience working on them.

Please contact me and tell me how I can help you. If you are a collector I've previously worked for, I'd especially like to hear from you.

His work winding new coils for Accutron watches is particularly exciting; he tells me he's heard of just one other person doing this in the last 20 years. These particular watch parts are otherwise irreplacable.


10 February 2018, 2:58 UTC

Finding all numbers produced by short, digitless 'GNU dc' programs

Stream of consciousness updates: More bugs in my search program, found and excised. More, shorter numbers. Maybe all 10-character programs.

A few years ago, possibly in 2014, I saw this code golf problem, which invites you write a short program that prints "2014"—the caveat being, the program may not contain any digits in its source code.

read more…

2 January 2018, 19:48 UTC

Four years of Prius (2013) fuel efficiency

Year Miles MPG Gal
2014 7546.8 44.4 170
2015 7333.6 43.9 167
2016 9368.8 44.8 209
2017 9936.2 45.1 220

Fuel economy and total mileage both went up in 2017 compared to earlier years. However, due to taking more road trips total fuel usage went up.

This year had my best mileage on a single nontrivial trip, shown as 99.9 MPG on 58.5 miles. This drive included significant downhill portions (descending from 12,000 feet to 6000 feet, if I recall correctly).


6 August 2017, 2:26 UTC

poc: Python OCE Composer

poc is a tool in the vein of OpenSCAD for creating 3D models in a high level language with a minimum of boilerplate. It's now live at github, though I don't know how actively I'll deveop or maintain it yet.

Here you can see that the input format is fairly terse, and it has some abilities OpenSCAD doesn't, like selectively filleting certain edges:

with Difference():
    Box((-50,-50,-50), (50,50,50))
    Cylinder((-100,0,0), (100,0,0), 25)
    Cylinder((0,-100,0), (0,100,0), 25)
    Cylinder((0,0,-100), (0,0,100), 25)
Fillet(12, [e for e in Edges() if e.boundingBox().min.z > 0])


1 August 2017, 0:48 UTC

occmodel as Python alternative to openscad

I like openscad a lot, but I'm still on the lookout for alternatives.

Recently I ran across occmodel. Its biggest prerequisite, OpenCASCADE, is packaged in Debian Stretch as "liboce"; the rest are fairly lightweight (though compiled) extensions.

So I gave it a try for a small piece, little extension legs for a dish drainer. I plan to add two leg extensions to the antisinkward legs of the dish drainer, to improve its draining behavior. So one key feature is that the captured leg will end up being at an angle to the counter.

My python program has a few "configurables" near the top, inner and outer diameters, heights, and the distance between the legs. From this, I do some basic operations (difference of two cylinders, rotation of that intermediate solid to represent the required angle, then intersection between it and a large cube that represents the half-space 'above the countertop'. Then, just to show I can do something openscad can't do trivially, I fillet every edge by 1mm.

from __future__ import division
from math import *
from geotools import *
from tostl import occ_to_stl # a little homebrew module
import os


dist = 12*IN
dia = .7*IN
od = dia + .25*IN
elevation = 1*IN
engagement = 1*IN

angle = atan2(elevation, dist)

outer = Solid().createCylinder((0,0,-elevation), (0,0,elevation+engagement),od/2)
inner = Solid().createCylinder((0,0,elevation), (0,0,100),dia/2)
outer.rotate(angle, (1,0,0))
b = Solid().createBox((-100,-100,0), (100,100, 100))
with open("", "wb") as f: occ_to_stl(outer, f)
os.rename("", "drainboots.stl")

(I couldn't get a screenshot that did the part much justice)

What is the gap between here and a real OpenSCAD alternative?

First, I'm not confident of the robustness of liboce; I saw some segfaults and since they were dependent on specific numbers in the geometry I am tempted to assign blame there and not to the occmodel wrapper. (not that OpenSCAD is beyond reproach here)

Second, it needs an integrated environment like OpenSCAD has. Maybe one of the python "notebook" interfaces would be suitable for this.

Third, it needs less boilerplate.

Fourth, it needs broad buy-in by users of sites like thingiverse, because OpenSCAD has massive momentum behind it.


12 July 2017, 14:34 UTC

MP Select Mini: Heated Bed Repair

19 March 2017, 20:16 UTC

Time Reversed Cosmology

19 November 2016, 19:08 UTC

Monoprice Select Mini 3D Printer Review

All older entries
Website Copyright © 2004-2018 Jeff Epler