Sometimes you come across a weird bug where the output seems to be completely impossible.  And it’s extremely hard to debug or search on google for, if you don’t know about this:

If your code has Undefined Behaviour, the compiler is allowed to assume it won’t happen, and can ‘optimize out’ chunks of your code.

Here’s a code snippet in a real bug I found yesterday:

#define FOO_SIZE 10
int foo2[FOO_SIZE];
...
int n=0;
do {
    p->foo[n] = foo2[n];
    n++;
} while( (foo2[n] != 0) && (n < FOO_SIZE) );
printk("n is %d\n", n);

This printed out:

   n is 165

and the system crashed.

But how can n become larger than FOO_SIZE=10 ?  Because the compiler ‘optimized’ away the check.  Here’s the asm:

} while( (foo2[n] != 0) && (n < FOO_SIZE) );
   21a14:       f813 2f01       ldrb.w  r2, [r3, #1]!
   21a18:       2a00            cmp     r2, #0
   21a1a:       d1f8            bne.n   21a0e <NV_Get+0x82>
   21a1c:       e7ca            b.n     219b4 <NV_Get+0x28>

What we are seeing here is that the “n < FOO_SIZE”  check has been completely removed by the compiler.  Why?

Because in the check, if n == FOO_SIZE, we would be checking if:  foo2[FOO_SIZE] != 0.  But this is out of bounds for foo.  The compiler knows that this is out of bounds, and so knows that this is undefined behaviour.  But the compiler is allowed to assume that undefined behaviour doesn’t happen, and so it assumes that n can NEVER be >= FOO_SIZE.  Thus it can remove the n < FOO_SIZE check.

This can be fixed by switching the order of the && like:

} while( (n < FOO_SIZE) && (foo2[n] != 0) );

Or, by checking n-1 instead  (which is slightly different behaviour, but good enough for me.  I was changing a lot of code with this bug.)

} while( (foo2[n-1] != 0) && (n < FOO_SIZE) );
   21a26:       7809            ldrb    r1, [r1, #0]
   21a28:       2900            cmp     r1, #0
   21a2a:       d0c3            beq.n   219b4 <NV_Get+0x28>
   21a2c:       429a            cmp     r2, r3
   21a2e:       d1f5            bne.n   21a1c <NV_Get+0x90>
   21a30:       e7c0            b.n     219b4 <NV_Get+0x28>

Now we see the second comparison in the asm.

It is common to want to calibrate cameras for lens distortion.

First print out a standard chequerboard image, and take some photos of it from various angles. You can print out images, for example, here:

https://calib.io/pages/camera-calibration-pattern-generator

Here I assume these photos are in camera_cal/calibration*.jpg

Even if you ultimately want to calibrate the images from c++, python, javascript etc, the calibration itself can be done separately, in a more convenient language, producing a matrix that you can use pretty much anywhere.  In my case, I calibrate in a jypter notebook, but use the matrix in c++.

%matplotlib inline

import numpy as np
import cv2
import glob
import matplotlib.pyplot as plt
#%matplotlib qt

# prepare object points, like (0,0,0), (1,0,0), (2,0,0) ....,(6,5,0)
objp = np.zeros((6*9,3), np.float32)
objp[:,:2] = np.mgrid[0:9,0:6].T.reshape(-1,2)

# Arrays to store object points and image points from all the images.
objpoints = [] # 3d points in real world space
imgpoints = [] # 2d points in image plane.

# Make a list of calibration images
images = glob.glob('camera_cal/calibration*.jpg')

# Step through the list and search for chessboard corners
for fname in images:
img = cv2.imread(fname)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)

# Find the chessboard corners
ret, corners = cv2.findChessboardCorners(gray, (9,6),None)

# If found, add object points, image points
if ret == True:
objpoints.append(objp)
imgpoints.append(corners)

# Draw and display the corners
img = cv2.drawChessboardCorners(img, (9,6), corners, ret)
plt.imshow(img)
plt.show()

ret, camera_undistort_matrix, camera_undistort_dist, rvecs, tvecs = cv2.calibrateCamera(objpoints, imgpoints, gray.shape[::-1], None, None)

fname = images[8]
img = cv2.imread(fname)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
ret, corners = cv2.findChessboardCorners(gray, (9,6),None)
print(ret)
img = cv2.drawChessboardCorners(img, (9,6), corners, ret)
dst = cv2.undistort(img, camera_undistort_matrix, camera_undistort_dist, None, camera_undistort_matrix)
img = np.concatenate((img, dst), axis=1)
plt.imshow(img)
cv2.imwrite("output_images/undistort_chessboard.png", img)
plt.show()

On the left is the original photo, and on the right is after applying the undistortion matrix warp.

import pickle
with open('camera_undistort_matrix.pkl', 'wb') as f:
pickle.dump((camera_undistort_matrix, camera_undistort_dist), f)
print(camera_undistort_matrix)

[[ 1.15777829e+03 0.00000000e+00 6.67113865e+02]
[ 0.00000000e+00 1.15282230e+03 3.86124659e+02]
[ 0.00000000e+00 0.00000000e+00 1.00000000e+00]]

img = cv2.imread("test_images/straight_lines1.jpg")
dst = cv2.undistort(img, camera_undistort_matrix, dist, None, camera_undistort_matrix)
img = np.concatenate((img,dst),axis=1)
img_rgb = cv2.cvtColor(np.asarray(img), cv2.COLOR_BGR2RGB)
plt.imshow(img_rgb)
cv2.imwrite("output_images/undistort_straight_lines1.png", img)
plt.show()

In the top left is the original image, in the top right is the undistorted image.  There is little difference to the eye, but the distortion lets us to now apply further distortions such as a perspective transform to provide an apparent “top-down view”.

It is also useful for applying other transforms key to stitching together images from multiple cameras.

Here’s the goal:

A way to make a webpage that lets you have an interactive dialogue by choosing options, like the old Interactive Fiction games.

The input file is very simple:

PRINT Hello!
WAIT ; This is a comment.  Wait for a key press or mouse click
PRINT I would like to ask you a question.
PRINTW Please don't be nervous. ; The 'W' means WAIT afterwards
PRINT Are you happy?
PRINT [0] Yes
PRINT [1] Not really...
CALL INPUTINT(0, 1)
IF RESULT == 0
    PRINTW I'M SO HAPPY THAT YOU'RE HAPPY!
ELSE
    PRINTW Then I am miserable 😦
ENDIF

The challenge is to make a webpage that could read that input, and run it, producing the interactive output shown in the video above.

Perhaps have a think if you don’t know how you would implement this. It is perhaps not so obvious.

Here is the approach that I decided to take.  Note that I only wanted to spend a weekend on this, so I took various shortcuts that I wouldn’t recommend if writing for production:

1. Read in the input file in, using javascript with a Tokenizer and Parser.
2. Output javascript using the above Parser, effectively making a transpiler from the input language to javascript.  Call outside javascript functions to ‘PRINT’ etc.
3. Use ‘eval’ to run the resulting transpiled code.  Yes, eval is evil and this is a case of don’t do what I do.
4. Use Promises, via async and await, to ‘pause’ and allow interaction.  Implement ‘WAIT’, ‘PRINTW’ ‘INPUTINT’ etc functions in javascript with Promises, so that they only resolve when the user has clicked, typed a number etc.
5. Display output by just appending to a list, and displaying that list in React.

1. Read the file in, using Javascript with a Tokenizer and Parser

I used jison.  Although the README blurb says that it is for Context Free Grammars, because it is based on BISON which is likewise, it does actually support context.  This was vital because the input file language is not actually a context free grammar.

2. Output javascript using the above Parser, effectively making a transpiler from the input language to javascript

The correct way to do this would be to create an Abstract Syntax Tree, however I didn’t want to take too long on this, and instead simply outputted javascript code as a string.

3. Use ‘eval’ to run the resulting transpiled code.

This is very frowned upon, but this was a weekend project, so….

There is one trick that I used here.  I wrap the entire program to be ‘eval’ed like:

async function() { ..... }()

This allows the program code inside to use async and await to wait for input, and the eval is returning a Promise.  One minor point – when we use eval to evaluate this, we want to catch errors that the Promise throws, to provide clear feedback to the user if there are problems.  E.g.

try {
    await eval(program);
} catch(e) { ... }

4. Use Promises, via async and await, to ‘pause’ and allow interaction.  Implement ‘WAIT’, ‘PRINTW’ ‘INPUTINT’ etc functions in javascript with Promises, so that they only resolve when the user has clicked, typed a number etc.

I used two layers of callbacks, to implement a poor-man’s publish and subscribe system.

So the transpiler turns:

PRINTW Hello!

into:

printLine("Hello!");
await wait();

And the wait() function is implemented as:

async function wait() {
  await new Promise(
    resolve => cb_setClickListener(() => resolve())
  )
}

So we subscribe to a click listener via the callback ‘cb_setClickListener’ and then resolve the promise (and thus resume running the program) when the click is published.

Inside the React page, we now listen for clicks and publish it to the callback:

<App onclick={
  () => this.state.clickListener &&
        this.state.clickListener()
}>

And likewise for keypresses.  (Note, I’ve simplified the code here a bit.  In the real code, I pass the keypressed etc, so that INPUTINT can listen to a particular key).

5. Display output by just appending to a list, and displaying that list in React.

The ‘printLine’ function was implemented like:

function printLine(str) {
  const newLine = <div>{str}</div>;
  this.setState({displayLines: [...displayLines, newLine]})
}

One extra detail – if the string starts with a number in a bracket like: “[0] Yes”, then I output a link that publishes that number like:

<div className="clickable" onClick={
    () => this.state.keyPressedListener &&
          this.state.keyPressedListener(number)
  }
>{str}</div>

This way, when presented with a choice, the user can just click a link instead.   I maintain two separate output lists, so that I can disable the links once we are done with them.

Conclusion and notes

It worked very nicely! I further extended this to support variables, entering strings, showing pictures, and so on.

The language is actually a real language, but very niche and used almost exclusively by Japanese. It hasn’t seen much acceptance or use outside of Japan.