Subversion Repositories cryptosorter

/*

 * MEMOCODE Hardware/Software CoDesign Contest 2008

 *

 * Everyone is granted permission to copy, modify and redistribute

 * this tool set under the following conditions:

 *

 *    This source code is distributed for non-commercial use only.

 *    Please contact the maintainer for restrictions applying to

 *    commercial use.

 *

 *    Permission is granted to anyone to make or distribute copies

 *    of this source code, either as received or modified, in any

 *    medium, provided that all copyright notices, permission and

 *    nonwarranty notices are preserved, and that the distributor

 *    grants the recipient permission for further redistribution as

 *    permitted by this document.

 *

 *    Permission is granted to distribute this file in compiled

 *    or executable form under the same conditions that apply for

 *    source code, provided that either:

 *

 *    A. it is accompanied by the corresponding machine-readable

 *       source code,

 *    B. it is accompanied by a written offer, with no time limit,

 *       to give anyone a machine-readable copy of the corresponding

 *       source code in return for reimbursement of the cost of

 *       distribution.  This written offer must permit verbatim

 *       duplication by anyone, or

 *    C. it is distributed by someone who received only the

 *       executable form, and is accompanied by a copy of the

 *       written offer of source code that they received concurrently.

 *

 * In other words, you are welcome to use, share and improve this

 * source file.  You are forbidden to forbid anyone else to use, share

 * and improve what you give them.

 *

 * THE SOFTWARE IS PROVIDED "AS-IS" WITHOUT ANY WARRANTY OF ANY KIND, EITHER

 * EXPRESS, IMPLIED OR STATUTORY, INCLUDING BUT NOT LIMITED TO ANY WARRANTY

 * THAT THE SOFTWARE WILL CONFORM TO SPECIFICATIONS OR BE ERROR-FREE AND ANY

 * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,

 * TITLE, OR NON-INFRINGEMENT.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY

 * BE LIABLE FOR ANY DAMAGES, INCLUDING BUT NOT LIMITED TO DIRECT, INDIRECT,

 * SPECIAL OR CONSEQUENTIAL DAMAGES, ARISING OUT OF, RESULTING FROM, OR IN

 * ANY WAY CONNECTED WITH THIS SOFTWARE (WHETHER OR NOT BASED UPON WARRANTY,

 * CONTRACT, TORT OR OTHERWISE).

 *

 */

#include "recordio.h"

#include "aes_core.h"

#include <assert.h>

#include <stdio.h>

RECORD  db[MAXRECORD];

static AES_KEY  db_encrypt_key;

static unsigned db_chk;

FILE* sortedplain;

unsigned nextrng(unsigned rng) {

  return (rng >> 1) ^ (-(signed int)(rng & 1) & 0xd0000001u);

}

void getkey(unsigned idx, unsigned *f) {

  unsigned char plaindata[16] = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0,

                                 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0};

  unsigned char cryptdata[16];

  int i;

  PUTU32(plaindata+12, idx);

  AES_encrypt(plaindata, cryptdata, &db_encrypt_key);

  for (i=0; i<4; i++)

    f[i] = GETU32(cryptdata + 4*i);

}

void initializedb(const unsigned char *gkey) {

  unsigned rng = RNGSEED;

  unsigned i;

  unsigned record_key[4];

  assert(sortedplain = fopen("sortedplain.hex","w"));

  static int n = MAXRECORD;

  assert(gkey != 0);

  AES_set_encrypt_key(gkey, 128, &db_encrypt_key);

  db_chk = 0; // reference checksum for non-encrypted data

  for (i=0; i<MAXRECORD; i++) {

    getkey(i, record_key);

    db[i].f1 = n^ record_key[0];

    db[i].f2 = 0^ record_key[1];

    db[i].f3 = 0^ record_key[2];

    db[i].f4 = 0^ record_key[3];

    n--;

    /*rng = nextrng(rng);

    if (rng < 0x80000000)

           db[i].f1 = record_key[0];

    else {

      db[i].f1  = rng ^ record_key[0];

      db_chk   += rng;

    }

    rng = nextrng(rng);

    if (rng < 0x40000000)

      db[i].f2 = record_key[1];

    else {

      db[i].f2  = rng ^ record_key[1];

      db_chk   += rng;

    }

    rng = nextrng(rng);

    if (rng < 0x20000000)

      db[i].f3 = record_key[2];

    else {

      db[i].f3  = rng ^ record_key[2];

      db_chk   += rng;

         }

    rng = nextrng(rng);

    db[i].f4  = rng ^ record_key[3];

    db_chk   += rng;*/

    }

}

void readrecord(RECORD *r, unsigned idx) {

  unsigned record_key[4];

  assert(r != 0);

  assert(idx < MAXRECORD);

  getkey(idx, record_key);

  r->f1 = db[idx].f1 ^ record_key[0];

  r->f2 = db[idx].f2 ^ record_key[1];

  r->f3 = db[idx].f3 ^ record_key[2];

  r->f4 = db[idx].f4 ^ record_key[3];

}

void writerecord(RECORD *r, unsigned idx) {

  unsigned record_key[4];

  assert(r != 0);

  assert(idx < MAXRECORD);

  getkey(idx, record_key);

  db[idx].f1 = r->f1 ^ record_key[0];

  db[idx].f2 = r->f2 ^ record_key[1];

  db[idx].f3 = r->f3 ^ record_key[2];

  db[idx].f4 = r->f4 ^ record_key[3];

}

int comparerecord(unsigned idx1, unsigned idx2) {

  RECORD r1, r2;

  unsigned r;

  readrecord(&r1, idx1);

  readrecord(&r2, idx2);

  if ( (r1.f1) >  (r2.f1)) r = 0;

  else if (((r1.f1) == (r2.f1)) &&

           ((r1.f2)  > (r2.f2))) r = 0;

  else if (((r1.f1) == (r2.f1)) &&

           ((r1.f2) == (r2.f2)) &&

                          ((r1.f3)  > (r2.f3))) r = 0;

  else if (((r1.f1) == (r2.f1)) &&

           ((r1.f2) == (r2.f2)) &&

                          ((r1.f3) == (r2.f3)) &&

                          ((r1.f4)  > (r2.f4))) r = 0;

  else r = 1;

  return r;

}

void swaprecord(unsigned idx1, unsigned idx2) {

  RECORD r1, r2;

  readrecord(&r1, idx1);

  readrecord(&r2, idx2);

  writerecord(&r2, idx1);

  writerecord(&r1, idx2);

}

int verifydb() {

  unsigned i;

  unsigned ok = 1;

  unsigned chk;

  RECORD   R;

  // verify if the ordering is correct

  for (i=0; i<MAXRECORD-1; i++){

    readrecord(&R, i);

    fprintf(sortedplain,"%08x%08x%08x%08x\n", R.f1,  R.f2,  R.f3,  R.f4);

    ok = ok & (comparerecord(i+1, i) == 0);

  }

  // evaluate checksum

  chk = 0;

  for (i=0; i<MAXRECORD; i++) {

    readrecord(&R, i);

    chk += R.f1;

    chk += R.f2;

    chk += R.f3;

    chk += R.f4;

  }

  return ok & (chk == db_chk);

}

void sortrecord() {

  unsigned i, swapped = 1, gap;

  gap = MAXRECORD * 10 / 13;

  while ((gap > 1) || (swapped)) {

    swapped = 0;

    if (gap > 1) {

      gap = gap * 10 / 13;

      gap = (gap == 10) ? 11 : gap;

      gap = (gap ==  9) ? 11 : gap;

    }

    for (i=0; (i + gap) <= MAXRECORD-1; i++)

      if (comparerecord(i+gap, i)) {

        swaprecord(i,i+gap);

        swapped = 1;

      }

  }

}

void showdb() {

  unsigned i;

  unsigned record_key[4];

  for (i=0; i<MAXRECORD; i++) {

    printf("%3x ", i);

    printf("%8x ",db[i].f1);

    printf("%8x ",db[i].f2);

    printf("%8x ",db[i].f3);

    printf("%8x ",db[i].f4);

    getkey(i, record_key);

    printf("%8x ",(db[i].f1 ^ record_key[0]));

    printf("%8x ",(db[i].f2 ^ record_key[1]));

    printf("%8x ",(db[i].f3 ^ record_key[2]));

    printf("%8x\n",(db[i].f4 ^ record_key[3]));

  }

}