Subversion Repositories aemb

/* $Id: literate.hh,v 1.1 2008-04-11 15:31:47 sybreon Exp $

**

** AEMB Function Verification C++ Testbench

** Copyright (C) 2004-2008 Shawn Tan 

**

** This file is part of AEMB.

**

** AEMB is free software: you can redistribute it and/or modify it

** under the terms of the GNU General Public License as published by

** the Free Software Foundation, either version 3 of the License, or

** (at your option) any later version.

**

** AEMB is distributed in the hope that it will be useful, but WITHOUT

** ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

** or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public

** License for more details.

**

** You should have received a copy of the GNU General Public License

** along with AEMB.  If not, see .

*/

/**

  AEMB Software Verification

  @file literate.hh

  Algorithms listed here are extracted from literateprograms.org and

  modified for AEMB testing.

*/

#include 

#ifndef LITERATE_HH

#define LITERATE_HH

/*

FIBONACCI TEST

http://en.literateprograms.org/Fibonacci_numbers_(C)

  This tests for the following:

  - Recursion & Iteration

  - 32/16/8-bit data handling

*/

unsigned int fibSlow(unsigned int n)

{

  return n < 2 ? n : fibSlow(n-1) + fibSlow(n-2);

}

unsigned int fibFast(unsigned int n)

{

  unsigned int a[3];

  unsigned int *p=a;

  unsigned int i;

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

    if(i<2) *p=i;

    else {

      if(p==a) *p=*(a+1)+*(a+2);

      else if(p==a+1) *p=*a+*(a+2);

      else *p=*a+*(a+1);

    }

    if(++p>a+2) p=a;

  }

  return p==a?*(p+2):*(p-1);

}

int fibonacciTest(int max) {

  unsigned int n;

  unsigned int fast, slow;

  // 32-bit LUT

  unsigned int fib_lut32[] = {

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

  };

  // 16-bit LUT

  unsigned short fib_lut16[] = {

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

  };

  // 8-bit LUT

  unsigned char fib_lut8[] = {

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

  };

  for (n=0;n

    slow = fibSlow(n);

    fast = fibFast(n);

    if ((slow != fast) ||

        (fast != fib_lut32[n]) ||

        (fast != fib_lut16[n]) ||

        (fast != fib_lut8[n])) {

      return EXIT_FAILURE;

    }

  }

  return EXIT_SUCCESS;

}

/*

   EUCLIDEAN TEST

   http://en.literateprograms.org/Euclidean_algorithm_(C)

   This tests for the following:

   - Modulo arithmetic

   - Goto

*/

int euclidGCD(int a, int b) {

  if (b > a) goto b_larger;

  while (1) {

    a = a % b;

    if (a == 0) return b;

  b_larger:

    b = b % a;

    if (b == 0) return a;

  }

}

int euclideanTest(int max)

{

  int n;

  int euclid;

  // Random Numbers

  int euclid_a[] = {

    1804289383, 1681692777, 1957747793, 719885386, 596516649,

    1025202362, 783368690, 2044897763, 1365180540, 304089172,

    35005211, 294702567, 336465782, 278722862

  };

  int euclid_b[] = {

    846930886, 1714636915, 424238335, 1649760492, 1189641421,

    1350490027, 1102520059, 1967513926, 1540383426, 1303455736,

    521595368, 1726956429, 861021530, 233665123

  };

  // GCD

  int euclid_lut[] = {

    1, 1, 1, 2, 1, 1, 1, 1, 6, 4, 1, 3, 2, 1

  };

  for (n=0;n

    euclid = euclidGCD(euclid_a[n],euclid_b[n]);

    if (euclid != euclid_lut[n]) {

      return EXIT_FAILURE;

    }

  }

  return EXIT_SUCCESS;

}

/**

   NEWTON-RHAPSON

   http://en.literateprograms.org/Newton-Raphson's_method_for_root_finding_(C)

   This tests for the following:

   - Multiplication & Division

   - Floating point arithmetic

   - Integer to Float conversion

*/

float newtonSqrt(float n)

{

  float x = 0.0;

  float xn = 0.0;

  int iters = 0;

  int i;

  for (i = 0; i <= (int)n; ++i)

    {

      float val = i*i-n;

      if (val == 0.0)

        return i;

      if (val > 0.0)

        {

          xn = (i+(i-1))/2.0;

          break;

        }

    }

  while (!(iters++ >= 100

           || x == xn))

    {

      x = xn;

      xn = x - (x * x - n) / (2 * x);

    }

  return xn;

}

int newtonTest (int max) {

  int n;

  float newt;

  // 32-bit LUT

  float newt_lut[] = {

    0.000000000000000000000000,

    1.000000000000000000000000,

    1.414213538169860839843750,

    1.732050776481628417968750,

    2.000000000000000000000000,

    2.236068010330200195312500,

    2.449489831924438476562500,

    2.645751237869262695312500,

    2.828427076339721679687500,

    3.000000000000000000000000,

    3.162277698516845703125000,

    3.316624879837036132812500,

    3.464101552963256835937500,

    3.605551242828369140625000,

    3.741657495498657226562500

  };

  for (n=0;n

    newt = newtonSqrt(n);

    if (newt != newt_lut[n]) {

      return EXIT_FAILURE;

    }

  }

  return EXIT_SUCCESS;

}

#endif

/*

$log$

*/