#include<stdio.h>
#include<stdlib.h>

/*
   Simple DES
   I am implimenting what is called simple DES ( 10 bit DES or S-DES )
   It uses a 10 bit key, and encrypts data 8 bits at a time.

   The symbol DEBUG changes the behaviour
   If it is not set, it tests the entire range with little output.
   If it is set it only tests one input, but is verbose.
   By default it is NOT set, compile with -DDEBUG to set it.

   This code was written for gcc

   John W. Clark
 */

typedef unsigned short uval;    // 16 bit unsigned numbers
// rather than have 8 bit and 10 bit numbers I just used uval 
// hopefully this makes it easier not harder

// create the s-boxes
static const uval S0[4][4] =
{
    { 1, 0, 3, 2 },
    { 3, 2, 1, 0 },
    { 0, 2, 1, 3 },
    { 3, 1, 0, 3 }
};
static const uval S1[4][4] =
{
    { 0, 1, 2, 3 },
    { 2, 0, 1, 3 },
    { 3, 0, 1, 0 },
    { 2, 1, 0, 3 }
};

/*
   I am using macros for two reasons :
   1. they avoid the overhead of a function call
   2. they are more fun that a barrel of IS students
   If you want to see how macros expand use : gcc -E
 */

// bit x of y, evaluate to 1 or 0 ( true/false )
#define B(x,y) ( ((y) >> (x)) & 0x01)

/*
   bit reordering permutations and expansions
   the bit remapping is prior to each
   these are all defined as macros
 */

// p10  9876543210 -> 7583609124
#define p10(x) ( B(7,x) << 9 | B(5,x) << 8 | B(8,x) << 7 | B(3,x) << 6 | \
        B(6,x) << 5 | B(0,x) << 4 | B(9,x) << 3 | B(1,x) << 2 | \
        B(2,x) << 1 | B(4,x) )

    //p8   9876543210 -> 47362501
#define p8(x) ( B(4,x) << 7 | B(7,x) << 6 | B(3,x) << 5 | B(6,x) << 4 | \
        B(2,x) << 3 | B(5,x) << 2 | B(0,x) << 1 | B(1,x) )

    //p4   3210 -> 2013
#define p4(x) ( B(2,x) << 3 | B(0,x) << 2 | B(1,x) << 1 | B(3,x) )

    //ip   76543210 -> 62574031
#define ip(x) ( B(6,x) << 7 | B(2,x) << 6 | B(5,x) << 5 | B(7,x) << 4 | \
        B(4,x) << 3 | B(0,x) << 2 | B(3,x) << 1 | B(1,x) )

    //ip_inv 76543210 -> 47531602
#define ip_inv(x) ( B(4,x) << 7 | B(7,x) << 6 | B(5,x) << 5 | B(3,x) << 4 | \
        B(1,x) << 3 | B(6,x) << 2 | B(0,x) << 1 | B(2,x) )

    //ep   3210 -> 03212103
#define ep(x) ( B(0,x) << 7 | B(3,x) << 6 | B(2,x) << 5 | B(1,x) << 4 | \
        B(2,x) << 3 | B(1,x) << 2 | B(0,x) << 1 | B(3,x) )

    //sw   76543210 -> 32107654
#define sw(x) ( B(3,x) << 7 | B(2,x) << 6 | B(1,x) << 5 | B(0,x) << 4 | \
        B(7,x) << 3 | B(6,x) << 2 | B(5,x) << 1 | B(4,x) )

    // actually used these
    // rotate x left y bits, total size is 5 bits
#define ROT_L5(x,y) ((( (x) << (y) ) | ( (x) >> (5-y) )) & 0x1F )
    // get the right 5 bits of x
#define RIGHT5(x) ( (x) & 0x1F )
    // get the left 5 bits of x
#define LEFT5(x) ( ( (x) >> 5 ) & 0x1F )
    // get the right 4 bits of x
#define RIGHT4(x) ( (x) & 0x0F )
    // get the left 4 bits of x
#define LEFT4(x) ( ( (x) >> 4 ) & 0x0F )



    // print x as a 10 bit value
void p_bits( uval x )
{
    char arr[13] = "00 0000 0000";
    int i, j;
    for( i = 9, j = 0 ; i >= 0 ; --i, ++j )
    {
        // leave 2 and 7 as spaces for readability
        if ( ( j == 2 ) || ( j == 7 ) )
        {
            ++j;
        }
        if( B(i,x ) )
        {
            arr[ j ] = '1';
        }
    }
    printf ( "%s\n", arr );
}

#ifdef DEBUG
// clean up the debugging stuff
void debugf( char * s, uval x )
{
    printf( "%s", s );
    p_bits( x );
}
#else
// make it an empty statement
#define debugf(s,x) ;
#endif

// real des functions
void subkeys( uval k, uval * k1, uval * k2 )
{
    uval n = p10( k );
    // split it into two 5 bit halves
    uval l = LEFT5( n );
    uval r = RIGHT5( n );
    uval tmp;
    debugf( "ep(k) = ", n );
    // rotate each half left by one
    l = ROT_L5( l, 1 );
    r = ROT_L5( r, 1 );
    tmp = ( l << 5 ) | r;   // join them
    debugf( "ls-1 =  ", tmp );
    *k1 = p8( tmp );
    debugf( "k1 =    ", *k1 );
    // rotate each half left by two
    l = ROT_L5( l, 2 );
    r = ROT_L5( r, 2 );
    tmp = ( l << 5 ) | r;   // join them
    debugf( "ls-2 =  ", tmp );
    *k2 = p8( tmp );
    debugf( "k2 =    ", *k2 );
}

uval F( uval x, uval k )
{
    uval row,col;
    uval rval;
    uval a = ep(x) ^ k; // expand and add key
    uval l = LEFT4( a );
    uval r = RIGHT4( a );
    // row bits 30 , col bits 21
    // lookup left 4 in S0
    row = ( B(3, l ) << 1 ) | B(0, l );
    col = ( B(2, l ) << 1 ) | B(1, l );
    rval = S0[row][col] << 2;   // the left 2 bits
    // lookup right 4 in S1
    row = ( B(3, r ) << 1 ) | B(0, r );
    col = ( B(2, r ) << 1 ) | B(1, r );
    rval |= S1[row][col];       // the right 2 bits
    rval = p4(rval);
    return rval;
}

// fk(L,R,SK) = ( L ^ F(R,SK),R )
uval f_k( uval x, uval k )
{
    uval l = LEFT4( x );
    uval r = RIGHT4( x );
    uval y = l ^ F( r, k );         // "add" them, really xor
    uval rval = ( y << 4 ) | r;     // join them
    return rval;
}

uval encrypt( uval in, uval k1, uval k2 )
{
    uval x = ip( in );
    debugf( "after ip     ", x );
    x = f_k( x , k1 );
    debugf( "after f_k    ", x );
    x = sw( x );
    debugf( "after sw     ", x );
    x = f_k( x , k2 );
    debugf( "after f_k    ", x );
    x = ip_inv( x );
    debugf( "after ip_inv ", x );
    return x;
}

int main()
{
    uval input,output;      // test variables
    uval key,key1,key2;     // key and subkeys
    uval tmp;

    // uval must be 10 bits, so I look for < 2 bytes
    if ( sizeof( uval ) < 2 )
    {
        printf("Houston, we have a problem!\n");
        printf("sizeof(uval) = %d\n", sizeof( uval ) );
        printf("redefine uval to something bigger!\n");
        exit(1);
    }

    // test case
    input = 0xA5;  //   1010 0101
    key = 0x097;   //00 1001 0111 

    printf( "key =    " ); p_bits( key );
    subkeys( key, &key1, &key2 );
    printf( "key1 =   " ); p_bits( key1 );
    printf( "key2 =   " ); p_bits( key2 );

    printf( "input =  " ); p_bits( input );
    output = encrypt( input, key1, key2 );
    printf( "output = " ); p_bits( output );    // 0011 0110 = 36

    // reverse the subkeys to decrypt
    tmp = encrypt( output, key2, key1 );
    printf( "tmp =    " ); p_bits( tmp );
    // tmp == input , the encryption has symmetry
    if ( tmp != input )
    {
        printf("Houston, we have a problem!\n");
        printf("it is not symmetric!\n");
        exit(2);
    }

#ifndef DEBUG
    {   // new subscope so I can declare variables here
        uval x,y,z;
        // verify for entire data range 0...255
        for ( x = 0 ; x < 256 ; ++x )
        {
            y = encrypt( x, key1, key2 );
            z = encrypt( y, key2, key1 );
            if ( x != z )
            {
                printf( "error at %X\n", x );
            }
        }
    }
#endif

    return 0;
}