Tag: Programming

pwgen for Windows

pwgen is a handy package that runs on Linux (among other systems). According to its description it “generates random, meaningless but pronounceable passwords. These passwords contain either only lowercase letters, or upper and lower case mixed, or digits thrown in. Uppercase letters and digits are placed in a way that eases remembering their position when memorizing only the word”. I use pwgen -1 for “one time only passwords” like when subscribing to mailing lists or web sites that require a username/password combination and I am not sure that I will stick with them. In other words, passwords that I fire and forget.

Unfortunately, it does not run under Windows, which is what I am working on some of these days. The code is pretty standard though, and with some minor tweaking, like borrowing a getopt(3) implementation and using srand(3)/rand(3) instead of /dev/urandom (Windows does have a similar capability) porting it to Windows was easy.

Having the source around is always handy! For those who do not want to do it themselves, here is a link to the (compiled with Digital Mars C++) binary: wpwgen.exe

Russ Cox on regular expressions

Thanks to Ozan S. Yigit I found out about a three-article series by Russ Cox on regular expressions:

I knew about Russ Cox and his interest in regular expressions because of this link to a pdf copy of “Programming Techniques: Regular expression search algorithm” that I had found at his site. Somehow I had missed the articles. Using Ozan’s words “russ cox, like other top-notch cs people, takes a topic and nails it shut. these three papers are more valuable to me than any RE book”.

Yes the articles are that good. However the good news do not stop here. Russ Cox implemented a fast, safe, thread-friendly alternative to backtracking regular expression engines (like those used in PCRE, Perl, and Python) written in C++, called RE2. It even comes with a POSIX (egrep) mode.

The postmaster in me quickly thought of the possibility of implementing a milter that makes use of RE2, just like milter-regex uses traditional regex(3), but my time is so limited by other more pressing projects, that I can only wish that someone else undertakes such a task.

Counting large numbers of events in small registers

“What does the logarithm do?”, asked a Professor a bunch of us back in 1990. “It is the inverse of e^{x} “, I said. “No” he replied, “I ask again, what does the logartihm do?”. A friend started to say something along the lines of the Wikipedia definition. “You tell me how it is calculated, but not what it stands for; why do we need it?”. He then proceeded asking us the value of the logarithm of some numbers:

x log_{10}(x)
1 0
10 1
100 2
1000 3
10000 4

– Do you see a pattern now?

“The length of the number is \lfloor log_{10}(x) \rfloor +1“, one of us observed.

– Exactly!

I was reminded of this discussion when stumbling on “Counting large numbers of events in small registers“ written by Robert Morris (father of the Robert T. Morris). Basically, what Morris observes in this paper is that with n bits available, one can count up to 2^{n}-1. He had 8 bit registers available only, so this limited counting up to 255 which did not suite the application he had at hand. So he began by simply having the value of a register representing v(n) = log_{2}(1+n) and reached to a generalized result of v(n) = \frac{log(1+\frac{n}{a})}{log(1+\frac{1}{a})} where a controls both the maximum count that can be held in the register and the expected error.

The maximum number is n_{v} = a((1+\frac{1}{a})^{v}-1). The expected error of n after n counts can be calculated from the formula \sigma^{2} = \frac{n(n-1)}{2a}.

This is a really nice hack if you need to count large numbers of events and where accuracy is not a must. It maybe helpful to people working with embedded systems or otherwise deprived environments.

(Triggered-By:)

Conway’s Game of Life implemented in Processing

Yesterday’s ugliness in implemented in Processing:

class Cell {
  int x;
  int y;
  int size;
  int live;

  Cell(int tx, int ty, int ts, int tl) {
    x = tx;
    y = ty;
    size = ts;
    live = tl;
  }

  void display() {
    stroke(0);
    if (live == 0) {
      fill(209);
    } else {
      fill(255);
    }
    rect(x, y, size, size);
  }

  void display(int c) {
    stroke(0);
    fill(c);
    rect(x, y, size, size);
  }
}

Cell[][] grid;
int[][] next;
int maxI;
int maxJ;
int size = 10;
int start = 0;

void setup() {
  size(900, 500);
  background(255);

  maxI = floor(width / size) - 1;
  maxJ = floor(height / size ) -1;
  grid = new Cell[maxI][maxJ];
  next = new int[maxI][maxJ];

  noLife();
}

void noLife() {
  for (int i = 0; i < maxI; i++) {
    for (int j = 0; j < maxJ; j++) {
      grid[i][j] = new Cell(i * size, j * size, size, 0);
      next[i][j] = 0;
      grid[i][j].display();
    }
  }
}

void draw() {
  if (start == 1) {
    runLife();
    delay(200);
  }
}

void mouseClicked() {
  if (start == 1) {
      noLife();
      start = 0;
  }

  if ((mouseX < maxI * size) && (mouseY < maxJ * size)) {
    int i = floor(mouseX / size);
    int j = floor(mouseY / size);
    if (grid[i][j].live == 1) {
      grid[i][j].live = 0;
    } else {
      grid[i][j].live = 1;
    }
    grid[i][j].display();
  } else {
    start = 1;
  }
}

void runLife() {
  int i0;
  int i1;
  int j0;
  int j1;
  int alive;

  for (int i = 0; i < maxI; i++) {
    for (int j = 0; j < maxJ; j++) {
      i0 = i - 1;
      i1 = i + 1;
      j0 = j - 1;
      j1 = j + 1;

      if (i0 < 0) i0 = maxI - 1;
      if (j0 < 0) j0 = maxJ - 1;
      if (i1 == maxI) i1 = 0;
      if (j1 == maxJ) j1 = 0;

      alive = 0;

      if (grid[i][j0].live == 1) alive++;
      if (grid[i1][j0].live == 1) alive++;
      if (grid[i1][j].live == 1) alive++;
      if (grid[i1][j1].live == 1) alive++;
      if (grid[i][j1].live == 1) alive++;
      if (grid[i0][j1].live == 1) alive++;
      if (grid[i0][j].live == 1) alive++;
      if (grid[i0][j0].live == 1) alive++;

      if ((grid[i][j].live == 1) && ((alive == 2) || (alive == 3))) {
        next[i][j] = 1;
      } else {
        next[i][j] = 0;
      }

      if ((grid[i][j].live == 0) && (alive == 3)) {
        next[i][j] = 1;
      }
    }
  }

  for (int i = 0; i < maxI; i++) {
    for (int j = 0; j < maxJ; j++) {
      grid[i][j].live = next[i][j];
      grid[i][j].display();
      next[i][j] = 0;
    }
  }
}

Two things that I find cool about Processing:

  • You can export your application as a Java applet.
  • Processing.js

Conway’s Game of Life implemented in SmallBasic

At work we have a new junior system administrator. Given the fact that he is junior and lacks even programming experience, I gave him the following assignment:

– Implement Conway’s Game of Life. Pick the programming language of your choice, the user interface of your choice, read anything you believe is relevant, ask anyone (including me) for advice, make the assumptions that suit you (and document them). Just someday come back with a demo.

Life’s rules are simple:

  • Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
  • Any live cell with more than three live neighbours dies, as if by overcrowding.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any dead cell with exactly three live neighbours becomes a live cell.

His language of choice is PHP (as I said he lacks programming experience and PHP is the only language he has ever written anything meaningful in). Given that a system administrator must be proficient at least in sh, awk, Perl and some Python (and VBScript or Windows PowerShell if working in a Windows environment) I expect a change of choice soon. He will see the light of C later.

Upon hearing about the assignment a colleague made an unfortunate humorous attempt to challenge me: If I am to put an assignment to the junior administrator, why don’t I implement it too? Due to the law of unintended consequences, this was an unfortunate remark that was done in front of the junior administrator (more on why this was a bad choice of timing later).

Continue reading “Conway’s Game of Life implemented in SmallBasic” →

atan2() implemented in bc

Dave Taylor thought that it would be a good idea to calculate in Perl the distance between two longitude / latitude points on the Earth. He also thought it would be awesome if the same could be implemented in bc.

I replied that one could easily transform in Perl the cost function from the TSP page. Dave Taylor pointed out that unfortunately atan2() is not available in bc and atan2() is used in the cost function.

“So what?” I thought. All one needs is the definition of atan2(). It turns out that one needs to define in bc the sign function and abs() too.

define sgn(x) {
        if (x == 0) {
                return(0);
        } else if (x < 0) {
                return(-1);
        } else if (x > 0) {
                return(1);
        }
}

define abs(x) {
        if (x < 0) {
                return(-1 * x);
        } else {
                return(x);
        }
}

define atan2(y, x) {
        auto pi, fi;

        pi = 4 * a(1);

        if (y == 0) {
                if (x > 0) {
                        return(0);
                } else if (x == 0) {
                        print "undefined\n";
                        halt;
                } else if (x < 0) {
                        return(pi);
                }
        }

        fi = a(abs(y/x));

        if (x > 0) {
                return(fi * sgn(y));
        } else if (x == 0) {
                return(pi * sgn(y) / 2);
        } else if (x < 0) {
                return((pi - fi) * sgn(y));
        }
}

Put the function definitions in a file (say atan2.bc) and call it from the command line as:

$ bc -l atan2.bc

The above code was written in less than ten minutes of time. I am sure that one can come up with better implementations (not calculating pi (== 4 * atan(1)) and then dividing it by 2 is an optimization directly observable). All in all it was a fun exercise, plus while searching I got to read about CORDIC.

Seven Principles of Software Testing

Bertrand Meyer (of Eiffel fame) writes about the “Seven Principles of Software Testing“:

  • Principle 1: Definition To test a program is to try to make it fail.
  • Principle 2: Tests versus specs Tests are no substitute for specifications.
  • Principle 3: Regression testing Any failed execution must yield a test case, to remain a permanent part of the project’s test suite.
  • Principle 4: Applying oracles Determining success or failure of tests must be an automatic process.
  • Principle 4 (variant): Contracts as oracles Oracles should be part of the program text, as contracts. Determining test success or failure should be an automatic process consisting of monitoring contract satisfaction during execution.
  • Principle 5: Manual and automatic test cases An effective testing process must include both manually and automatically produced test cases.
  • Principle 6: Empirical assessment of testing strategies Evaluate any testing strategy, however attractive in principle, through objective assessment using explicit criteria in a reproducible testing process.
  • Principle 7: Assessment criteria A testing strategy’s most important property is the number of faults it uncovers as a function of time.

Switching context to the subject of testing (computer) systems in a broader sense, I am reminded of a presentation at a workshop that I attended a few months ago (it was more of a penetration testing presentation):

Here is how you learn more things about your system:

  • You can have a committee study your system and plan testing; they will get back to you in 30 years.
  • You can plan, execute exercises and evaluate results for two years prior to putting it to production.
  • Or you can have a real life crisis and learn everything you need in two hours.

That is why you need to launch test events to the largest userbase possible.

Oh well, as Peter Viscarola pontificated from the NT Insider, people “just write some code“. Which leads to:

  • The ultimate (and sometimes only) test is final deployment.

Sigh…

Update: One year after the “Seven Principles of Software Testing”, Meyer blogged “What is the purpose of testing?“