Debugging without a debugger

Another retro post, from even earlier times than the last one.

This happened during my high school years when some of my friends already owned a computer but I had none. So we used to get together after school and binge play some video games -- starting with Lord of the Rings text adventures and Laser Squad hot-seats...

...and then, rummaging through then-abundant "bootleg software shops" (a post-USSR version of Game Stop, selling bunches of floppy disks with copied games or other software and with labels hand-printed on a 9-pin dot matrix printer) I discovered Eric the Unready (which you can actually play in an online emulator here).

I loved it at first sight. A wonderful piece of interactive fiction with hilarious jokes and puns, challenging puzzles and, myself an avid English learner at that time, an invaluable learning resource.

Unfortunately, right after playing through the first chapter, we ran into something annoying: copy protection feature. One of the "Prince of Persia"-type where you would be asked a few questions and would need the original printed game manual to answer these correctly and play on.

And needless to say we didn't have the manual -- and of course, neither did the shop we bought the game from.

Well, as a disclaimer... I do understand that software piracy is, in the big picture, bad bad BAD, but hey, we were 15 years old and had no idea of the big picture - nor any clue about copyrights and licensing. To us at that time, the fact that we had software on our computer meant that we could do as we pleased with it, especially given that we did buy it at a shop (sic!).

And even if someone were to lecture us on the proper course of action... At that time in that part of the world, an equivalent of $30 would be a decent monthly salary (yes, monthly, not daily, not hourly), and there was absolutely no way an ordinary person could possibly make a payment anywhere to a foreign country, or for that matter, to pay in any tender other than cash - no credit cards, no wire transfers, no bank accounts...

...so yes, I admit we were stealing apples from somebody else's garden, but quite unknowingly, almost unavoidably, and without causing anyone any real harm.

But all these sentiments aside, we were already hooked, and needed a way to play on.

Surely we had no Internet to look up the correct answers (there was no Google, no Chrome and even hardly any Internet Explorer yet!), we had no one to ask (the game was so out of mainstream, and the level of English command needed to play it was so untypical that we might well have been the only players in years). We also had nothing to tinker with the game with -- no hiew, no disassembler, no debugger proper.

We did have Game Wizard, a utility that you would normally use to save and reload in Tetris or make yourself infinite lives in Pacman. The way you do it would be to search the memory for "3" when you have 3 lives, then for "2" when you have 2 lives, and so on; with some luck you would find the address in memory that holds the lives variable for the game. You can then set it to 99 or freeze at 3 to get infinite lives.

And we gave it a try, for lack of anything better to do for the rest of the evening. We began by alternating memory searches in the state before vs. after the first question is answered -- hoping to reveal its correct answer by noticing different variable values depending on whether we chanced to answer correctly. Instead, we got:

XXXX:YYYY 01 02 01 02 01 02

As a wild guess I just set it to 4 instead...

...and got right through. (Apparently I inadvertently found the counter of the questions loop and moved right past it.)
All it took after that was to save the game (and the evening), granting us with endless hours of fun time.

The power of one-liners

In modern software engineering where most software is written by large groups of people most of whom seem to dislike reading each other's code. As a result, most organizations have some style guidelines for their code: proper indentation, naming conventions, commenting, you name it.

And most developers will have strong opinions about how code should (and even more so, shouldn't) look like. And they will defend (and, their position permitting, enforce) their opinions with near-religious fervor. Most often, they will yell at you for writing this:

for (i=0;i<n;i++) for (j=i;j<n;j++) if (a[i]>a[j]) {double t=a[i];a[i]=a[j];a[j]=t;} // bubble sort A

and instead insist on something like this:

// Bubble sort array A

for (counter_rows = 0; counter_rows < n; counter_rows++) 
  {
    for (counter_columns = counter_rows; counter_columns < n; counter_columns++) 
      {
        if (a[counter_rows] > a[counter_columns])
          { 
            double temp_variable t = a[counter_rows];
            a[counter_rows] = a[counter_columns];
            a[counter_columns] = temp_variable;
          }
      }
  }

Yes, it looks neat and tidy. But is it really all that readable?

No, not really.

It is very hard to honestly defend a standpoint that a piece of code is easier to read if have to scroll through three screens to read it, as opposed to fitting it on one screen. "But this way it is more organized", comes the objection. Very true, but how is it organized?

It is organized by instructions.

But what for? By instruction is how the compiler looks at the code, but the compiler does not give the slightest damn about your code style. Humans are much more interested in what the code does than in how the code does it (assuming that you, a fellow developer, already have some knowledge of the "how" once you know the "what").

From this standpoint it makes much more sense to organize the code by logically distinct blocks -- important steps of your algorithm that you would put on your flowchart or pseudocode (pseudocode, after all, was invented specifically for this purpose: convey the meaning of complicated code in a simpler, readable, understandable form).

And this means that simple, elegant one-liners -- once (and if) they are self-evident in what they do -- are much more preferable than expanding them on two screens. See for yourselves:

//simple operations, e.g. sumproduct or matrix multiplication
double S=0; for (int i=0;i<N;i++) S+=a[i]*b[i];

for (int i=0;i<N;i++) for (int j=0;j<N;j++) for (int k=0;k<N;k++) c[i][j]+=a[i][k]*b[k][j];

// one-liner error checking, prep or boilerplate
if (failed || !solution_good) return false;

double param; if (!genericParam.Has_Double) throw Error; param = genericParam.Get_Double();

customVector<double> vec(vec1); int vec_n=vec.Count(); double* vec_ptr=vec.Data(); 

//getter/setter methods
double someClass::getSomeProperty() {return someProperty;}

void someClass::setSomeProperty(double arg) {someProperty=arg;}

//etc...

UPDATE: Following some discussion, I feel I need to clear up a confusion here. Any code, prettified, is more readable than the same code, minified. The idea of one-liners isn't about improving the readability of the one-liner code itself! It is about the exact opposite: the one-liner code is assumed to be trivial and therefore not worth going into any great detail about, so the idea is to minify the one-liner code so that it does not get in the way of what's really important and interesting in your code. In other words, it is about improving the readability of the code surrounding your one-liners.

As for naming conventions, they definitely make sense for anything that would be (re)used in several places through the code. If something is set up in one place and is used elsewhere, by all means make the name of the variable (class, object, ...) speak for itself.

That said, still try to keep it short. Calculations in the code are formulas, and formulas read much easier with shorter variables than with long, verbose ones; that's why they introduced variables in textbook formulas in the first place, and they do write E = mgh instead of "Potential_energy = mass * specific_gravity * distance" anywhere beyond grade two at school.

For intermediate variables such as loop counters, simply don't bother. Mathematical names such as a, x, y, i, j, k will perfectly do and they will make your calculations so much easier.

There are exceptions -- sometimes, when naming is especially prone to confusion, do add some mnemonics, such as i_row and i_col rather than i and j, lest you mess up your array indices. But in most cases, formulas in the code need not look any more verbose than they do on your scrap paper.  Sometimes, it is even advisable to assign "long" mnemonic variables to short ones, do the math, and then assign the result back to the long variables.

So -- no, I'm not saying your code should look like Toledo Picochess (see below). But  do write in your IDE as you would write on the blackboard, and do write code as you would write pseudocode.

After all, making code readable is all about making it readable for a human.

P.S. Toledo Picochess looks like this: (now THAT's truly unreadable code!)

#define F (getchar()&15)
#define v main(0,0,0,0,
#define Z while(
#define P return y=~y,
#define _ ;if(
char*l="dbcefcbddabcddcba~WAB+  +BAW~              +-48HLSU?A6J57IKJT576,";B,y,
b,I[149];main(w,c,h,e,S,s){int t,o,L,E,d,O=*l,N=-1e9,p,*m=I,q,r,x=10 _*I){y=~y;
Z--O>20){o=I[p=O]_ q=o^y,q>0){q+=(q<2)*y,t=q["51#/+++"],E=q["95+3/33"];do{r=I[p
+=t[l]-64]_!w|p==w&&q>1|t+2<E|!r){d=abs(O-p)_!r&(q>1|d%x<1)|(r^y)<-1){_(r^y)<-6
)P 1e5-443*h;O[I]=0,p[I]=q<2&(89<p|30>p)?5^y:o;L=(q>1?6-q?l[p/x-1]-l[O/x-1]-q+2
:0:(p[I]-o?846:d/8))+l[r+15]*9-288+l[p%x]-h-l[O%x];L-=s>h||s==h&L>49&1<s?main(s
>h?0:p,L,h+1,e,N,s):0 _!(B-O|h|p-b|S|L<-1e4))return 0;O[I]=o,p[I]=r _ S|h&&(L>N
||!h&L==N&&1&rand())){N=L _!h&&s)B=O,b=p _ h&&c-L<S)P N;}}}t+=q<2&t+3>E&((y?O<
80:39<O)||r);}Z!r&q>2&q<6||(p=O,++t<E));}}P N+1e9?N:0;}Z I[B]=-(21>B|98<B|2>(B+
1)%x),++B<120);Z++m<9+I)30[m]=1,90[m]=~(20[m]=*l++&7),80[m]=-2;Z p=19){Z++p<O)
putchar(p%x-9?"KQRBNP .pnbrqk"[7+p[I]]:x)_ x-(B=F)){B+=O-F*x;b=F;b+=O-F*x;Z x-F
);}else v 1,3+w);v 0,1);}}

Card tricks brute forced

(Now going from lowest-level to highest-level coding)

When I was in middle school, we used a standard 36-card playing deck (from 6 onwards) to play a bunch of games. We also used this deck to do some "loves me, loves me not" type fortune telling where "loves me" was indicated by, essentially, an occurrence of two aces in a row somewhere in the deck.

Much later on I got curious about how likely that outcome was. A short back of the envelope calculation gives

P = [P(A1)*P(A2|A1)]*N 
where 
P(A1) = probability of "there is an ace at position 1 in the deck", 1/9
P(A2|A1) = probability of "there is an ace  at position 2 n the deck if there already is an ace at position 1", 3/35 (3 aces left, out of 35 cards possible)
N = 35 -- number of different positions in the deck where two consecutive aces can occur.

Hence

P = [(1/9)*(3/35)]*35 = 1/3

This looks too high, at first sight. 
So let's write a simple brute-force proof in Wolfram Language (ex-Mathematica):

cards = "6789TJQKA";
adeck = Characters[cards<>cards<>cards<>cards];
testdeck[deck_List] := Length[StringPosition[StringJoin@@ToString/@deck,"AA"]]>0;
(*Monte-Carlo*)
n=100000;For[c=0;i=0,i<n,i++,(thedeck=RandomSample[adeck];If[testdeck[thedeck],c++])]
approx=N[c/n]

It is more or less obvious what the code does: it just tests a large number n of permutations on a deck (using RandomSample[])and then testing whether the resulting deck has at least two aces in a row (searching for "AA" in a deck converted to a string) and counting the number of decks in which this is found.

You can run the code in Wolfram Cloud and make sure the answer is indeed quite close to 0.3

(In hindsight, is it so strange, really? A "loves me, loves me not" trick will only survive among kids if it has a significantly non-negligible chance of a favorable outcome. And I do believe this is how most fortune telling works.)

Naturally you can modify the code very simply to include other card tricks.
For example, you can set cards="23456789TJQKA" for a standard 52-card deck; additionally you can append <>"XX" to cards<>cards<>cards<>cards to include jokers (or <>"AA" if you want them to be wild and count as aces).
Or you can change the testing function to test for any card sequence (like "AK" or "6789"), or indeed modify the criterion to any degree of complexity.

Finally, if you want to differentiate the suits of cards, we will need a slightly more complicated code:

cards = "6789TJQKA"; suits = "SHDC";
adeck = Outer[StringJoin, cards//Characters, suits//Characters]//Flatten;
testdeck[deck_List] := Length[StringPosition[StringJoin@@(First[Characters[#]]&)/@deck,"AA"]]>0;

Isn't it just beautiful how you can combine Map (/@) and Apply (@@) along with Mathematica's pure functions to create tests on lists without unnecessary boilerplate like loops? (And we can verify that making all aces distinct does not change the probability of two of them following each other.)

Finally, I initially planned to do a rigorous (rather than Monte-Carlo) test using Permutations[adesk], but it turns out that Mathematica won't have lists with "more than machine integer" elements. Sad but would probably work (and chances are, will be much faster than Monte-Carlo) with shorter decks.

Text pattern matching, revisited

This is more of a retro post to reflect on one of my very first code experiences.

1. Backstory

Back then, I was a student in an Eastern European city in the middle of a social paradigm change, and as a consequence, with parents struggling to make ends meet. So, even though I did receive a PC (or rather, $500 needed to assemble one) as my prom gift, that PC (with its AMD 5x86-133 processor) was very quickly out-specced by almost everyone in the class...

Long story short, when the city's telephone directory database was leaked and immediately became a very popular piece of software, I was annoyed to find out that it was slow as a snail on a system like mine. It was even more annoying to see that the database, of around 7MB in size, was quite enough to fit entirely in memory, so, given the right shell, we could potentially try to make it faster.

So I was approached by another guy with an older PC and we decided to write such a "fast shell". The first step was to reverse engineer the database, which was quite simple. Each record was 16 bytes, like so:

TT TT TT  NN NN NN  I1 I2  SS SS  SN SN SB SL AP AP 
telephone surname   inits  street  str.#/l    apt.#  

TT -- telephone number 
NN -- last name (integer key)
I1, I2 -- given name initials
SS -- street name (integer key)
SN -- street number
SB -- numeric street number suffix (for numbers like 23/1, pretty common in ex-USSR)
SL -- literal street number suffix (for numbers like 23A, less common but present)
AP -- apartment number

Note that SB and SL could be combined, resulting in a shorter 15-byte record; however the benefit was deemed small compared with having an aligned 16-byte record length, allowing the database file to be very easily browsable in a hex viewer.

The database had some 500-600k entries and was sorted by telephone number (allowing instant look-ups by phone number via binary search). The look-ups by by a specific name or street were very fast as well -- once the integer key for the name was found (again by binary searching, very fast), matching an integer through the entire database took about 1 second.

2. Problem 

What turned out a bit problematic was to look up by an approximate or patterned street name or last name, such as "find everyone whose name matches J?nes and who lives on West* street". On a platform that we had (some protected mode 32-bit Pascal or even standard Borland DPMI -- cannot remember now -- possibly with the use of Turbo Vision), even a simple string comparison for all entries in the database would run for ~30 seconds. Any conceivable pattern matching routine would take up minutes, which was prohibitively long.

To remedy this, we reverted to the assembly language and wrote this: (we assume, for simplicity, that both the pattern and the test string are null-terminated and that the length of the pattern is known in advance):

...
; preparation

mov ecx, __length     ;must be pattern length w/o trailing zero!
mov esi, __pattern    ;pattern string
mov edi, __test       ;test string
mov bh, 0x2A          ;*
mov bl, 0x3F          ;?
...

; main function

_resume:
repe cmpsb
je _pass
mov ah, [esi-1]
mov al, [edi-1]
cmp ah, bh            ;* encountered 
je _pass
cmp al, 0x00          ;test string too short
je _fail
cmp ah, bl            ;? encountered, skip char
jne _fail             ;otherwise -- failed
cmp cx, 0              
je _pass
jmp _resume
...

This routine (at the heart of which was a low-level repe cmpsb which is extremely fast) could handle "?" and the trailing "*" in the pattern (much like in MS-DOS wildcards), going through the entire DB in about 5-6 seconds. What it could not do was to handle "*" in the middle of the string, so as to be able to search for something like Wood*ck. And I wanted this functionality quite badly.

3. Solution

So the idea would be to extend the handling of "*" with the basic idea of  look what's behind "*" in the pattern; keep skipping characters in the test string until it matches or until the string runs out. Finally I came up with this: 

...
_resume:
repe cmpsb
je _pass
mov ah, [esi-1]
mov al, [edi-1]
cmp ah, bh ; * encountered
jne _cont

 inc esi
 dec cx ; skip *
 mov ah, [esi-1] ;look behind *
 cmp ah, 0x00 
 je _pass ;pass if * trailing
_keep:
 inc edi
 mov al, [edi-1]
 cmp al, 0x00 ; out of chars
 je _fail
 cmp al, ah ; next char found
 je _resume ; resume loop; keep cx intact!
 jmp _keep
  
_cont:
cmp al, 0x00 ; test runs out
je _fail
cmp ah, bl ; ? encountered
jne _fail
cmp cx, 0 ; pattern runs out
je _pass
jmp _resume

This allowed full pattern matching in less than 10 seconds, and without using any stack operations - everything is done entirely with registers and minimized memory access.
The only limitation was to disallow constructions such as "*?" (but you could use "?*" instead) and "**" (but you should use a single "*"). (Or on the flipside, this allows to search for literal "*" and "?" in the test string even though it was never practically relevant.)
You can test it out in an emulator by adding some housekeeping code for I/O (just borrowed this from their "Hello, World" example, this will be heavily platform-specific):

  _pass: ;output - pattern matched
     mov edx, 7    ;message length
     mov ecx, __pass    ;message to write
     mov ebx, 1     ;file descriptor (stdout)
     mov eax, 4     ;system call number (sys_write)
     int 0x80        ;call kernel
     mov eax, 1     ;system call number (sys_exit)
     int 0x80        ;call kernel
    
  _fail: ;output - pattern not matched
     mov edx, 11    ;message length
     mov ecx, __fail    ;message to write
     mov ebx, 1     ;file descriptor (stdout)
     mov eax, 4     ;system call number (sys_write)
     int 0x80        ;call kernel
     mov eax, 1     ;system call number (sys_exit)
     int 0x80        ;call kernel

  section .data ;input
     __pattern db 'testi*e',0,0xa 
     __test db 'testicle',0,0xa 
     __pass        db  'Matched',0xa
     __fail        db  'Not matched',0xa
     __length equ 8 ;length of pattern

One may wonder if it made any sense at all to do string matching on every DB entry, rather than generate a list of all key values for matching names or streets and then checking if the key of each entry matches that list. I would agree that the second approach would make sense under most circumstances, and even in those rare occasions where the list would have thousands of entries (like, if we only know the first letter of the name) matching can be made faster using binary search (our names list is sorted, remember?). I was, however, too lazy to write and debug such a matching routine, though.

Very simple "for-each" patterned programming trick

Quite a few times during coding there issome need for repetitive tasks. Something like, in C++:

...
ourDoubleMatrix A, B, C, u1, u2; 
double* A_ptr = A.Data(); A.Resize_Matrix(a,b); Eigen::Map<eigenmat> A_mat(A_ptr, A.Rows(), A.Columns()) ;
double* B_ptr = B.Data(); B.Resize_Matrix(a,b); Eigen::Map<eigenmat> B_mat(B_ptr, B.Rows(), B.Columns()) ;
... // you guessed it.

or, in VBA:

Function do_some_stuff(data As Variant, data1 As Variant, data2 As Variant, moredata As Variant, evenmoredata As Variant, somemoredata As Variant, andcantherebemoredata As Variant) As Variant
 ...
 Dim v_data As Variant: v_data = Application.Transpose(Application.Index(data, 0, 1)): count = data.Rows.Count: ReDim Preserve v_data(1 To (count + addcount))
 Dim v_data1 As Variant: v_data1 = Application.Transpose(Application.Index(data1, 0, 1)): count = data1.Rows.Count: ReDim Preserve v_data1(1 To (count + addcount))
 ... ' and again you guessed it

Doing this via copy-and-paste with substitution of variable names is, well, time-consuming and tedious. Much more importantly, it is very error-prone (think of what would happen if you end up writing double* u2_ptr = u1.Data() or
v_data2 = Application.Transpose(Application.Index(data1, 0, 1)) - such mistakes are very easy to make but would take hours of thankless debugging to spot).

The solution would be to have a tool that would do "for each item in this list of variables, code so-and-so".

Here's a very simple trick to do it in a few seconds, literally:

1. Code up your first line. (Make sure it is correct.) 
2. Set up an Excel (or any other free equivalent) spreadsheet:
• copy your list of variables into column A
• copy your ready line of code into cell B1
• put this formula into cell B2: =SUBSTITUTE(B$1,A$1,A2)
  
3. Then simply replicate the formula in B1 to the number of elements in the column A (the quickest way is to select B1 then double click the lower right corner of that sell), and recalculate the sheet if needed.
4. Copy-paste the resulting column B to your code.

That's it!

Of course there are subtleties, namely that you need to make sure that the substitution is done correctly -- namely that the variable name in the first line is unique enough not to match anything else in the code (choosing a is probably a bad idea :).

And of course you can easily extend this to include multiple substitutions, increments, case-dependent logic, all the way to some quite sophisticated meta-programming. Your mileage may vary - just make sure that coding the spreadsheet doesn't take significantly more time than copy-pasting it "the plain old way".

I can almost hear someone screaming that this is very poor programming style, and, well, I largely agree. Yes, a much better solution is to avoid scenarios when you need to code repetitive stuff altogether, for example by encapsulating all set-up stuff in their respective classes. And shortcuts such as this one should never promote (or be used as an excuse for) lousy coding.

However, we do not always have ownership of the code and its design, nor do we always have the liberty of going for "let's drop all other tasks and rework that code". In other words, there are occasions when you're in Rome and have to do as Romans do. So if/when the need really arises, it's better to have a quick and easy way to write repetitive code, as opposed to having a tedious and bug-spawning way.

In other words: if you have to write lousy code, better write a reliable lousy code.

After all, isn't this exactly what template programming is all about?

Arduino LED driver and button press handler / debouncer: another "Hello, World"

Long story short, I've bought an Arduino for some small home automation (specifically, imitating remote control commands for a portable air conditioner in order to operate it on schedule).

Having run a few simple examples, I realized that whatever my device might be, I'd need some sort of a rudimentary GUI with some buttons to control the device and some LEDs to diagnose the device state. After some testing I realized that I need to solve several problems:

1. The function digitalRead() only polls instantaneous button state ("is the button pressed now?"); some memory-based logic is needed for the detection of the event "the button was pressed and then released", which is a relevant GUI input. This logic should also filter out contact bounce , otherwise (as I quickly found out) a button press (and/or release) is very prone to being interpreted as several presses.
2. I wanted to led LEDs blink (so that my device would signal its status without doubling up as a night light) concurrently with doing other tasks (such as the device's main function). 
3. I wanted the routines to be general enough to scale to several LEDs and buttons concurrently and independently of one another.

Essentially I wanted to implement the two basic tutorials (Debounce and BlinkWithoutDelay) in a robust, encapsulated, scalable manner.

So, here's what I came up with, and decided to share it here in case it is useful for someone else.

Let's first define some global variables and structures:

// button names
#define B_UP 0
#define B_DN 1
#define B_SEL 2
#define B_MOD 3

//global constants
const byte nL=5;
const byte nB=4;
const byte pinL[nL]={11,10,9,6,5}; // should be PWM-enabled pins
const byte pinB[nB]={7,8,2,3};

const byte NOISE = 15; // ms to hit timed event for debouncing
const byte REP_DELAY = 400; // ms to initiate autorepeat
const byte REP_RATE = 100; // ms to regenerate autorepeat

//global variables, initialized
byte thisLED=0;
byte thisMODE=4;

For our array of LEDs we define some working data structures:

//data structures - LEDs
word quant[nL] = {125,125,125,125,125}; // time between ticks
word flash[nL] = {75,75,75,75,75}; // overrides if less than quant;
byte level[nL] = {120,140,100,80,40}; //brightness level 
byte mask[nL] = {B00000001,B00010001,B01010101,B00000011,B11001100};//bitwise mask

word next[nL]; // time of next LED handle event
word nextOff[nL]; // time of next turn-off event
byte cycle[nL] = {1,1,1,1,1}; //current bit in the mask, starting with 00000001, rotated left on every tick

The blinking pattern is defined as follows: every quant[i] milliseconds we define a "tick" for the LED number i; at each tick, we cycle the "current bit number" between 1 and 8 (using the internal variable cycle[i]), and turn the i-th LED either on or off, depending on the current bit in mask[i]. Additionally the LED is turned off on a "quench", when flash[i] milliseconds have elapsed since it was last turned on. Finally, level[i] simply defines the LED's brightness level. This can be illustrated like this:

This approach allows us to create a considerable variety of patterns ranging from simply "pulse N times per second" or "do N short blinks once in a while" to more complicated dash-dot patterns. It has its limitations (mostly related to the number of bits in the mask) but it is more than enough for the kinds of diagnostic output we aim for. Note that level and pattern are independently set for each LED.

By the same token we define some structures for the buttons:

//data structures - buttons
byte raw[nB] = {0,0,0,0}; //raw button state 
byte b_ready[nB] = {1,1,1,1}; //whether button is ready 
byte cooked[nB] = {0,0,0,0}; // filtered button state
byte autorepeat[nB] = {1,1,0,0}; //whether to autorepeat on button xx
byte event[nB] = {0,0,0,0}; //button press event, must be consumed on handle and re-generated on autorepeat

word last[nB] = {0,0,0,0}; // time last pressed

Here the only "parameter" is autorepeat[i], defining whether the button number i should auto-repeat. The rest are internal variables needed for debouncing and handling button press events.

Next we write the handler for the LEDs:

void pollLEDs()
{
  word now = (word)millis();
  for (byte i=0;i<nL;++i)
  {
    if ((int)(now-next[i])>=0) // next tick reached
    {
      nextOff[i] = next[i]+flash[i];
      next[i]+=quant[i]; // move next (and nextoff) forward
      boolean state = ((cycle[i] & mask[i])!=0); 
         // determine current state from mask
      analogWrite(pinL[i], (state)?level[i]:0); \
         // light up or quench according to state
      cycle[i]=cycle[i]<<1; if(cycle[i]==0) cycle[i]=1; 
         // cycle current bit in mask 
    }
    if ((int)(now-nextOff[i])>=0) 
    { // flash time exceeded before next tick
      nextOff[i]+=quant[i]; // just move forward
      analogWrite(pinL[i], 0); // quench
    }
  }
}

We see that it just implements the logic in the diagram above, using next[] and nextOff[] to store the timer values for the next tick and quench respectively. The only trick here is the use of bitwise arithmetic for cycle[] to enable quick comparison against mask[].

You can see that it is easy to make the time span between patterns longer than 8*quant[] without increasing the size of the mask by simply defining a separate period[nL] and then replace next[i]+=quant[i] with next[i]+=(cycle[i]!=1)?quant[i]:period[i]

Next we write the button handler:

void pollButtons()
{
 word now = (word)millis();
 for (byte i=0;i<nB;i++)
 {
   raw[i] = (digitalRead(pinB[i])==LOW)?1:0; // store to avoid repeated calls to digitalRead()
   // if button is ready and LOW recorded, record last pressed time and clear ready
   if (b_ready[i]==1 && cooked[i]==0 && raw[i]==1) {b_ready[i]=0;last[i]=now;}
   // if not ready and still LOW after tolerance, set filtered state, button press detected
   if (b_ready[i]==0 && cooked[i]==0 && raw[i]==1 && (word)(now-last[i]) > NOISE) cooked[i]=1;
   // if state is pressed and button released : clear filtered, restore b_ready, and generate event unless auto repeating
   if (b_ready[i]==0 && cooked[i]==1 && raw[i]==0 && (word)(now-last[i]) > NOISE) 
   {
     cooked[i]=0;
     b_ready[i]=1;
     if (autorepeat[i]<2) event[i]=1; else autorepeat[i]=1;
   }
   
   // handle auto repeat
   if (autorepeat[i]==1 && cooked[i]==1 && raw[i]==1 && (word)(now-last[i]) > REP_DELAY)
   { // initiate auto repeat
      autorepeat[i]=2;
      last[i] = now;
      event[i]=1;
   }
   if (autorepeat[i]==2 && cooked[i]==1 && raw[i]==1 && (word)(now-last[i]) > REP_RATE)
   { // if auto repeating, re-generate event periodically
      last[i] = now;
      event[i]=1;
   }
   
   //handle event once generated
   if (event[i]==1)
   {
     event[i]=0; //consume event
     control(i); //handle event
   }
 }
}

Note that it uses raw[i] to store the instantaneous state of the button number i, whereas ready[i] is a flag indicating whether that button is expected to receive input; it is set initially and cleared the instant the button press is detected (at which time the button timer is set via last[i]). The logic to determine whether the button has actually been pressed (so its filtered state, cooked[i], can be set) is "the button is still pressed some predetermined time after it was pressed initially"; I've used 15 ms as a ballpark and found it to work fine with my buttons. Once cooked[i] is set, the handler listens for the button release; once this happens, it generates an event (via setting event[i]) and return the button to its initial ready state.

For auto repeat support the amount of extension is minimal. We use the same timer to determine whether a certain time has elapsed since the button was pressed, and start generating events repeatedly at regular intervals until the button is released.

We can see from the code and description that this approach filters out the contact bounce both upon press and upon release. I am leaving it as an exercise for you to see why.

To test the implementation I made a "blink machine" quick breadboard circuit with five LEDs and four buttons, which would be used to control the way LEDs blink, like so:

 

The buttons functions are as follows:

• [SELECT]: Cycle through LEDs to control.
• [MODE]: Cycle through parameters to adjust:
  brightness, blink frequency, blink duration, blink pattern
• [UP]: Increase the current parameter for the current LED.
• [DOWN]: Decrease the current parameter for the current LED.

This corresponds to the following implementation of the event handler control()

void control(byte code)
{
 switch(code)
 {
   case B_SEL:
    thisLED++; if (thisLED>=nL) thisLED=0;
    notify();
   return;
   
   case B_MOD:
     thisMODE++; if (thisMODE>5) thisMODE=1;
     notify();
   return;

   case B_UP: case B_DN:
   {
    switch(thisMODE)
    {
  switch(thisMODE)
    {
      case 1: //level
       if (code==B_UP && level[thisLED]<255) level[thisLED]++ ;
       if (code==B_DN && level[thisLED]>0) level[thisLED]-- ;
       break;
      case 2: //period
       if (code==B_UP && quant[thisLED]<1000) quant[thisLED]+=20 ;
       if (code==B_DN && quant[thisLED]>40) quant[thisLED]-=20 ;
       break;
     case 3: //flash
       if (code==B_UP && flash[thisLED]<quant[thisLED]) flash[thisLED]+=10 ;
       if (code==B_DN && flash[thisLED]>20) flash[thisLED]-=10 ;
       break;
     case 4: //pattern up/down
       if (code==B_UP) mask[thisLED]++ ;
       if (code==B_DN) mask[thisLED]-- ;
       break;
     case 5: //pattern scramble/reset
       if (code==B_UP) mask[thisLED]=(byte)millis() ;
       if (code==B_DN) mask[thisLED]=1 ;
       break;
    }         
   }
   return;
 }
}

void notify() // show currently selected LED and mode
{
    analogWrite(pinL[thisLED],0);delay(100);
    for (byte i=1;i<=thisMODE;++i)
    {
      analogWrite(pinL[thisLED],255);delay(50);
      analogWrite(pinL[thisLED],0);delay(50);
    }
}

Note the fifth mode to quickly scramble and reset the bitwise mask. The auxiliary function notify() is used to visually indicate the currently selected LED and mode. Here, for simplicity and because the interface should be synchronous with user input, I do use delay() (pausing all other operations in the process). Exercise: During the operation of notify(), some of the LEDs may miss a tick. What will happen to their blinking pattern?

Finally to complete the sketch, here are its two main functions, setup() and loop(). Note that these are really short to isolate the button/LED workings from the rest of your code.

void setup() 
{
// initialize pins
  for (byte i=0;i<nL;++i) pinMode(pinL[i],OUTPUT);
  for (byte i=0;i<nB;++i) pinMode(pinB[i],INPUT_PULLUP);
  for (int j=0;j<nL;++j) {analogWrite(pinL[j],255);delay(75);analogWrite(pinL[j],0);delay(150);} // "splash screen"
  Serial.begin(9600); // optional, for debugging
// initialize LED timers
  word now = (word)millis();
  for (byte i=0;i<nL;++i)
  {
    next[i] = now+quant[i];
    nextOff[i] = next[i]+flash[i];
  }
}

void loop() 
{
    // just call the two handlers
    pollLEDs();
    pollButtons();
}

After some debugging the implementation tested fine, but the real use is that pollLEDs() and pollButtons() can be used within any sketch; of course, control() will need to be re-written. The pattern for the LEDs can be altered at runtime by changing the corresponding variables.

Some concluding thoughts:

• I designed the LED pins to be PWM pins but non-PWM pins may be used just as well; just replace analogWrite with digitalWrite, disregarding level[].
• LEDs can be any driving circuits that need timed controls. Similarly, buttons can be any form of digital input. If you use analog input, keep in mind that analogRead takes time and a much slower dead-time processing will be needed instead of debouncing.
• This is really basic, but -- don't use pins 0 and 1 if you use serial communication for debugging. I've spent a few hours debugging until I figured out my debug messages were mimicking button presses.

The saga of an old Sears Craftsman garage door opener

This isn't exactly about curiouser code; rather, it's about curiouser electronics and troubleshooting.

Prologue

We bought a house with a built-in garage with an old (very very old, pre-1997) Sears Craftsman electric garage door opener, which the old owners claimed was defunct but never bothered to replace. Rather than just go and replace it myself, I tried my luck playing with the bundle of low-voltage wires dangling from it - and found that it did work if you connect the right wires.

Better than nothing.

Next, I downloaded the manual and tried searching Amazon for a possible replacement remote. And was lucky again: after a few unsuccessful tries, this little dongle successfully paired with the opener and worked.

Much better than nothing!

However, my curiosity was aroused at this point. The manual mentioned that there was a possibility to attach a pair of optional optical-beam safety sensors to prevent the door from closing if something was in the way, or to reverse the door closing if someone crossed the beam. Since the garage is very tight and I don't want the closing door to crash into my rear bumper (or, heaven forbid, to injure someone), this was definitely a feature I wanted.

Part 1. Research

The easiest and most obvious solution -- to order the safety sensors set as an official accessory from Sears -- was quickly put to an untimely end with a "No longer available" message on the official spare parts website.

The next one to try, less obvious but still easy, would be to order a set of 3rd-party sensors on Amazon (in the same way as I did with the remote) and hope that it works. Alas, no luck this time -- everything I could see on the aftermarket was for newer models, and would not be compatible with my opener.

The real snag was that my opener was "old but not too old" -- recent enough so that optical safety sensors were offered as an optional feature, but manufactured before these sensors were made mandatory. And while this was precisely what made it possible to get it running without the safety beam at all (I might have given up trying had I not been so lucky in the beginning), this was what rendered all newer safety sensors completely incompatible.

The reason? As explained nicely in this video, all newer models are designed in such a way that unless they get a "safe" signal from working sensors, the door won't close; just so that those pesky users won't bypass their faulty (or out-of-alignment or not-having-survived-mediocre-parking) sensors with a piece of jumper wire, the "safe" signal is a pulse train (with about 150 Hz frequency and some 10% duty cycle), which the receiver generates in presence of the sensor signal.

The manner my opener functioned was quite the opposite: it would work in all cases except when the sensor terminals are shorted (presumably by the sensors detecting the beam interruption), in which case the closing would not commence or, if already closing, would reverse.

Finally, I just decided to blindly try my luck with this set hoping I might still get the old kind, but alas, sadly but unsurprisingly, they were of the "pulse train" kind, nicely confirmed with an oscilloscope

Part 2. Simulation

So my job was to somehow translate between the two protocols. Some device (labeled "???" in the diagrams below) had to listen to the sensor output, decide if there was a "safe" pulse train, and then short the opener's sensor terminals if there were no pulses.

  

At this point, many would scream Arduino or even Raspberry Pi ("and your door will be able to post its status on Facebook"), but I quickly decided this would be too difficult, and a massive overkill to boot. I didn't want my door to post on Facebook. I wanted it to stop closing when the beam was crossed. Even this sequel video using an integrated-circuit (555 timer) square wave generator as a "pretty damn complicated piece of jumper wire to bypass the sensor" seemed a bit of an overkill to me (and as it were, resulted in at least one real kill...)

On the face of it, I thought a simple transistor switch might do the trick - if I could have the transistor normally open via some pull-down resistors, and rectify the pulse train in such a way that the signal would offset the opening potential and close the transistor (opening the switch) if pulses are present, at the same time retaining some power on the sensors so that they would resume normal operation if the beam was restored... not obvious. After a few evenings spent in a circuit simulator I found that a single transistor was a bit too unreliable; however a MOSFET or a Darlington transistor pair might do the trick, like so:

 

The one on the right is what I chose to implement as a final circuit. The two terminals on the right connect to the opener in parallel to the sensors: the upper right (positive) to the "white" screw and the white wire from the sensors; the lower right (ground) to the "black" screw and the striped wire from the sensors.

Part 3. Implementation

With a few of Amazon "shipped from China / Hong Kong and arriving several months later" orders, I finally assembled the circuit on a breadboard...

I scrapped the current limiting resistor in the output circuit because the short-circuit current was measured to be about 40 mA anyways, and put two 1M resistors in parallel to achieve 500k. The rest is as shown.
The real wonder? It worked out of the box.
And works still.

Epilogue

The opener is still in operation, sensors included, with the original breadboard circuit loosely hanging off the drywall. A few times it would refuse to close because there was something left in the doorway (I guess that may have saved those items from being crushed).

It isn't seamless, however: after I insulated the door with some styrofoam (making it quite a bit heavier), the gears in the opener did kick the bucket. However I was able to replace them relatively cheaply and quickly.

I still have plans to solder the circuit into something more permanent (and even bought all the necessary supplies for this), but these remain low priority (ain't broken? won't fix it, at least for now).

I still wonder whether I can somehow reverse engineer the operation of "Lock" and "Light" features from the wall control unit. If you happen to have this one lying around, please drop me a line!

   

Parameter sweep in any Excel calculation

For the past few years I have dabbled a lot (and I mean a lot) in complex Excel-based quantitative finance. As a result, I would like to share a neat little trick that can be easily applied to any Excel spreadsheet.

Suppose you have a spreadsheet that does some sophisticated calculation for you (say, pricing an autocallable basket option using a Monte-Carlo simulation of a Black-Scholes model). And yes, it works; you change the input parameters and you observe the corresponding change in the output.

Now what you need is the parameter sweep analysis, i.e. you need to determine how your output changes as you vary one or more input parameters - for example, you may want to run a convergence test to see how your resulting price changes as you vary the number of Monte-Carlo simulation paths,

Of course you can do this manually, doing the simple routine "change input, run simulation, copy-paste results, repeat". But for anything more than 4-5 simulation runs his would be painfully slow and dangerously prone to error.

What's worse, if a single simulation run takes around several minutes, you'll be stuck between the need to just stare at your computer doing nothing else (and letting your productivity go to waste) or the temptation to attempt something different in the meantime (and inviting all sorts of multitasking-related errors like "aw, snap, looks like I've run this one twice, and heck, have I pasted this number to the right place?")

This is where a simple VBA macro comes to help. As simple as this:

Sub analysis1()

 Dim in1, out1, out2, out3, here As Object
 Set in1 = Worksheets("Calc").Range("Input1")
 Set out1 = Worksheets("Calc").Range("Output1")
 Set out2 = Worksheets("Calc").Range("Output2")
 Set out3 = Worksheets("Calc").Range("Output3")

 Set here = Worksheets("Report").Range("Out1D")

 While here <> Empty
  in1.Value = here.Value

  Worksheets("Calc").Calculate  ' (or do whatever you need to do to run simulation -- e.g. call some other macro)
  here.Offset(0, 1).Value = out1.Value
  here.Offset(0, 2).Value = out2.Value
  here.Offset(0, 3).Value = out3.Value
  Set here = here.Offset(1, 0)
 Wend
End Sub

Here we will need to define several named ranges: Input1 for the parameter that we will vary, Output1..3 for the calculation results we are interested in, and Out1D where the macro will look for values for input, and where, next to each input value, the result values will be output.

Why named ranges if we can specify cell addresses like.Range("F23") directly? Because it's much more robust coding style. If you decide to change the layout of your spreadsheet later, the named ranges are quite likely to point to correct locations, whereas your addresses will likely change (and your code may wreck some serious havoc on your spreadsheet). At worst (or if you decide to change parameters to vary/look at), all you will need is to re-point the named ranges to new locations rather than go through your code and edit addresses each time.

The added elegance of this example is that you don't need to specify how your sweeping parameter will vary anywhere in the code, nor do you need to count the number of runs. The program will do all of this for you, automatically running for all values you specify below the Out1D range until it hits an empty cell.
Another example will let you handle the dependence on two parameters:

Sub analysis2()

 Dim in1, in2, out1, here As Object
 Set in1 = Worksheets("Calc").Range("Input1")
 Set in2 = Worksheets("Calc").Range("Input2")
 Set out1 = Worksheets("Calc").Range("Output2D")
 Set here = Worksheets("Analysis").Range("Out2D")
 
 For i = 0 To 10
   here.Offset(-1, i + 1).Value = i * 0.01
 Next i

 While here <> Empty
  in1.Value = here.Value
  For i = 0 To 10
   in2.Value = i * 0.01
   Worksheets("Calc").Calculate '(or do whatever you need ...)
   here.Offset(0, i + 1).Value = out1.Value
  Next i
  Set here = here.Offset(1, 0)
 Wend
End Sub

As you can easily see, now we only have one output parameter (Output2D) and two input parameters (Input1, Input2). Similar to before, we look for values for parameter 1 and a place for output under the range Out2D. For the second parameter we have resorted to a simple for-loop (choosing 0, 0.1, 0.2 ... 1) but this is for simplicity and demonstration; arbitrary values for parameter 2 are possible with very little extension that I am leaving as an exercise.

A few words of warning:

• Macros are ignorant of your spreadsheet editions! If you hardcode an address, or otherwise rely on a specific layout of your workbook, you will need to re-exaamine your code every time you edit the layout. A partial workaround is using named ranges (at least you can freely move them around).
• Changes made by macros can't be undone! Before proceeding, make sure none of your important data gets overwritten, and do make a back-up copy before you test and debug your work. Luckily Excel will warn you that a file with macros cannot be saved as an .xlsx, prompting you to use .xlsm or .xlsb (or at least the old .xls) instead.
• Macros won't always run! Make sure you enable them in your Excel security settings, and make sure some pesky anti-virus program won't blindly remove them from your sheets (assuming you weren't actually up to writing malware).

Bonus: There is a very quick VBA way to save an accountant's butt.

Consider this delicate scenario. You are working on a complex spreadsheet prepared a while ago by someone else, and the spreadsheet just won't tie. Soon enough the reason is clear: the person who last worked on the sheet blindly pasted some numbers over formulas to to sweep some of their mistakes under the rug. So you are left with finding all these "cover-ups"... and needless to say, that person left the company on less-than-amicable terms, so there's no one to ask about the spreadsheet structure.

How to flag "all cells where values were pasted over formulas" in a huge spreadsheet?

Consider something like this:

' The conditions may vary. We are interested in finding "all cells that have a number and are not formulas";
' the two most obvious checks would be
' (i) Left(cell.Formula,1) = "=" (i.e. cell's formula begins with "=")
' (ii) cell.Formula <> cell.Value (i.e. its formula is different from its value)
' Neither is totally fool-proof but both work fine.

For Each cell in ActiveSheet.UsedRange
 'some more code may be needed to safely work around cells that contain errors.
 If IsNumeric(cell.Value) And Left(cell.Formula,1) = "=" Then

  ' if it is a formula, everything is OK, dim it
  cell.Font.Color = RGB(128,128,128) 
 Else
  ' if it is a number, make it stand out
  cell.Interior.Color = RGB(255,255,0) 
  cell.Font.Color = RGB(255,0,0) 
 End If
Next cell