// ************************************************************************** //
//                                                                            //
//    eses                   eses                                             //
//   eses                     eses                                            //
//  eses    eseses  esesese    eses   Embedded Systems Group                  //
//  ese    ese  ese ese         ese                                           //
//  ese    eseseses eseseses    ese   Department of Computer Science          //
//  eses   eses          ese   eses                                           //
//   eses   eseses  eseseses  eses    University of Kaiserslautern            //
//    eses                   eses                                             //
//                                                                            //
// ************************************************************************** //
// The sorting network below is currently one of the best known ones for 16   //
// inputs. It is due to Green and requires only 60 compare/exchange modules   //
// and has depth 10 (which is no longer the best).                            //
// ************************************************************************** //

import SortNet16.Swap;

macro aSize = 16;
macro iSize = 64;

module Green([aSize]nat{iSize} ?a,b, event !ready) {

    for(i=0..aSize-1)
        b[i] = a[i];

    // step 1: (8 swaps)
    Swap(b[0],b[1]);
    Swap(b[2],b[3]);
    Swap(b[4],b[5]);
    Swap(b[6],b[7]);
    Swap(b[8],b[9]);
    Swap(b[10],b[11]);
    Swap(b[12],b[13]);
    Swap(b[14],b[15]);
    pause;

    // step 2: (8 swaps)
    Swap(b[0],b[2]);
    Swap(b[1],b[3]);
    Swap(b[4],b[6]);
    Swap(b[5],b[7]);
    Swap(b[8],b[10]);
    Swap(b[9],b[11]);
    Swap(b[12],b[14]);
    Swap(b[13],b[15]);
    pause;

    // step 3: (8 swaps)
    Swap(b[0],b[4]);
    Swap(b[1],b[5]);
    Swap(b[2],b[6]);
    Swap(b[3],b[7]);
    Swap(b[8],b[12]);
    Swap(b[9],b[13]);
    Swap(b[10],b[14]);
    Swap(b[11],b[15]);
    pause;

    // step 4: (8 swaps)
    Swap(b[0],b[8]);
    Swap(b[1],b[9]);
    Swap(b[2],b[10]);
    Swap(b[3],b[11]);
    Swap(b[4],b[12]);
    Swap(b[5],b[13]);
    Swap(b[6],b[14]);
    Swap(b[7],b[15]);
    pause;

    // step 5: (7 swaps)
    Swap(b[1],b[2]);
    Swap(b[3],b[12]);
    Swap(b[4],b[8]);
    Swap(b[5],b[10]);
    Swap(b[6],b[9]);
    Swap(b[7],b[11]);
    Swap(b[13],b[14]);
    pause;

    // step 6: (4 swaps)
    Swap(b[1],b[4]);
    Swap(b[2],b[8]);
    Swap(b[7],b[13]);
    Swap(b[11],b[14]);
    pause;

    // step 7: (6 swaps)
    Swap(b[2],b[4]);
    Swap(b[3],b[8]);
    Swap(b[5],b[6]);
    Swap(b[7],b[12]);
    Swap(b[9],b[10]);
    Swap(b[11],b[13]);
    pause;

    // step 8: (4 swaps)
    Swap(b[3],b[5]);
    Swap(b[6],b[8]);
    Swap(b[7],b[9]);
    Swap(b[10],b[12]);
    pause;

    // step 9: (7 swaps)
    Swap(b[3],b[4]);
    Swap(b[5],b[6]);
    Swap(b[7],b[8]);
    Swap(b[9],b[10]);
    Swap(b[11],b[12]);
    pause;

    // step 10: (2 swaps)
    Swap(b[6],b[7]);
    Swap(b[8],b[9]);
    pause;

    emit(ready);
}
drivenby Test01 {
    for(i=0..aSize-1) a[i] = i;
    dw: await(ready);
    for(i=0..aSize-1) assert(b[i] == i);
}
drivenby Test02 {
    for(i=0..aSize-1) a[i] = aSize-1-i;
    dw: await(ready);
    for(i=0..aSize-1) assert(b[i] == i);
}
drivenby Test03 {
    for(i=0..aSize-1)
        a[i] = ((i%2==0)?i:((aSize%2==0)?aSize-i:aSize-1-i));
    dw: await(ready);
    for(i=0..aSize-1) assert(b[i] == i);
}