Examples for Mini C Compiler

Insertion Sort (First Version)

thread InsertionMaxSort {
    [10]nat x;
    nat i,j,yind,yval;
    // first create a test array in reverse order
    for(i=0..9) {
        x[i] = 10-i;
    }
    // now apply insertion sort
    for(i=0..9) {
        // compute maximum of x[0..N-1-i]
        j = 0;
        yval = x[j];
        for(j=1..9-i)
            if(x[j]>yval) {
                yval = x[j];
                yind = j;
            }
        // now yval is the maximum of x[0..N-1-i] and is swapped with x[N-1-i]
        j = 9-i;
        x[yind] = x[j];
        x[j] = yval;
    }
}

Insertion Sort (Second Version)

// -----------------------------------------------------------------------------
// This file implements the well-known insertion sort procedure. The main idea
// is to sort prefixes x[0..i-1] of the array x[0..N-1] and then store x[i] in
// a separate variable y so that all entries x[j+1..i-1] can be moved one place
// to the right and y can be stored at x[j+1].
//   Note in many textbooks the while loop has condition (j>=0 & x[j]>y) and
// no other code than x[j+1]=y is put after the loop. However, if conjunction
// is commutative (as in MiniC and Quartz unlike in C), then in case of j==0,
// the evaluation of this condition will not stop after j>=0 is seen false,
// and instead also x[j]>y is evaluated which leads to a runtime error.
// -----------------------------------------------------------------------------

thread InsertionSort {
    [10]nat x;
    nat i,j,y;
    // first create a test array in reverse order
    for(i=0..9) {
        x[i] = 10-i;
    }
    // now apply insertion sort
    for(i=1..9) {
        y = x[i];   // for element x[i], find its place in
        j = i-1;    // already sorted list x[0..i-1]
        while(j>0 & x[j]>y) {
            x[j+1] = x[j];
            j = j-1;
        }
        // now j==0 or x[j]<=y
        if(x[j]>y) {
            // note that this implies j==0
            x[j+1] = x[j];
            x[j] = y;
        } else {
            // here we have x[j]<=y, so that y must be placed at j+1
            x[j+1] = y;
        }
    }
}

Matrix Multiplication

// -----------------------------------------------------------------------------
// The version below uses order k-j-i which is very bad, since the inner loop
// will then access elements from a,b and c in different rows so that cache
// hits are  unlikely for all of these accesses.
// -----------------------------------------------------------------------------

function MatrixMultV0 ([][]nat a,[][]nat b,[][]nat c,nat d1,d2,d3) : [][]nat {
    nat i,j,k;
    for(k=0..d3-1)
        for(j=0..d2-1)
            for(i=0..d1-1)
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
    return c;
}

// -----------------------------------------------------------------------------
// This version uses loop ordering i-j-k which is usually the definition found
// in textbooks. This version is better than the previous one, since the
// accesses to a and c are done in the inner loop in the same rows, but the
// inner loop accesses in each iteration another row of b.
// -----------------------------------------------------------------------------

function MatrixMultV1 ([][]nat a,[][]nat b,[][]nat c,nat d1,d2,d3) : [][]nat {
    nat i,j,k;
    for(i=0..d1-1)
        for(j=0..d2-1)
            for(k=0..d3-1)
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
    return c;
}

// -----------------------------------------------------------------------------
// The version below is much more cache-friendly than the previous versions,
// since now the innermost loop accesses all array accesses in the same rows
// which increases the chances to have cache hits.
// -----------------------------------------------------------------------------

function MatrixMultV2 ([][]nat a,[][]nat b,[][]nat c,nat d1,d2,d3) : [][]nat {
    nat i,j,k;
    for(i=0..d1-1)
        for(k=0..d3-1)
            for(j=0..d2-1)
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
    return c;
}

// -----------------------------------------------------------------------------
// We can optimize the above version in that we factor out the array access to
// matrix a which is always the same in the innermost loop. This way the number
// of load instructions is reduced.
// -----------------------------------------------------------------------------

function MatrixMultV3 ([][]nat a,[][]nat b,[][]nat c,nat d1,d2,d3) : [][]nat {
    nat i,j,k,x;
    for(i=0..d1-1)
        for(k=0..d3-1) {
            x = a[i][k];
            for(j=0..d2-1)
                c[i][j] = c[i][j] + x * b[k][j];
        }
    return c;
}

// -----------------------------------------------------------------------------
// The main thread generates some test examples, and then calls one of versions.
// -----------------------------------------------------------------------------

thread MatrixMult {
    [4][5]nat a;
    [5][6]nat b;
    [4][6]nat c;
    nat i,j;
    // first create some test matrices a and b
    for(i=0..3)
        for(j=0..4)
            a[i][j] = i+j;
    for(i=0..4)
        for(j=0..5)
            b[i][j] = (i+1)*(j+1);
    for(i=0..3)
        for(j=0..5)
            c[i][j] = 0;
    // now call one of the above functions
    c = MatrixMultV3(a,b,c,4,5,6);
}

Fibonacci Numbers

Computing Square Roots (Heron's Iteration)

Computing Greatest Common Divisors (Euclid's Algorithm)

Computing Greatest Common Divisors (Extended Euclid's Algorithm)

Radix-B and B-Complement Addition

// -----------------------------------------------------------------------------
// NatAdd is a ripple carry adder for radix-B numbers
// -----------------------------------------------------------------------------

function NatAddSameLen([]nat x1,x2,[]nat sum,nat len) : []nat {
    nat c,g,p,s,i;
    c = 0;                          // initial carry digit
    for(i=0..len-1) {               // ripple from least to highest digit
        g,s = x1[i] + x2[i];        // g:generate carry; s:preliminary sum
        p,sum[i] = s + c;           // p:propagate carry; add previous carry
        c = (nat) ((bool) g | (bool) p);    // define next carry digit 0 or 1
    }
    sum[len] = c;                   // most significant digit is final carry
    return sum;
}

// -----------------------------------------------------------------------------
// IntAdd is a ripple carry adder for B-complement numbers
// -----------------------------------------------------------------------------

function IntAdd([8]nat x1,x2,[9]nat sum) : [9]nat {
    nat c,g,p,s,i;
    // first perform NatAdd up to the highest digits of x1 and x2
    c = 0;
    for(i=0..6) {
        g,s = x1[i] + x2[i];
        p,sum[i] = s + c;
        c = (nat) ((bool) g | (bool) p);
    }
    // rightmost digits have to be treated differently (namely as int)
    g,s = (nat)((int) x1[7] + (int) x2[7]);
    p,sum[8] = (nat)((int) s + (int) c);
    sum[9] = (nat) ((bool) g | (bool) p);
    return sum;
}

thread t2 {
    [4]nat x;
    [8]nat y;
    [9]nat sm;
    sm = NatAdd(x,y,sm,4,8);
}

Fachbereich Informatik

Embedded Systems Group (ES)