kitPerm.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "kit.h"

Go to the source code of this file.

Macros
#define	inline   __inline
#define	NFUNCS   (1<<20)

Typedefs
typedef unsigned __int64	word
	DECLARATIONS ///. More...
typedef unsigned short	shot
typedef unsigned char	byte

Functions
void	Kit_PermCreateS ()
	FUNCTION DEFINITIONS ///. More...
void	Kit_PermCreateP ()
static void	Kit_PermCycleOne (shot *s, byte *b, int v)
static void	Kit_PermCycleMany (shot *s, byte *b, int V, int v)
void	Kit_PermCompute (word *o, word *i, int V)
void	Kit_PermComputeNaive (word *F, int nVars)
word	M (word f1, word f2, int n)
word	Tf (word f, int n)
void	Kit_PermComputeTest ()
void	Kit_PermComputeTest_ ()

Variables
static shot	S [256]
static byte	P [256]

Macro Definition Documentation

#define inline   __inline

CFile****************************************************************

FileName [kitPerm.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Computation kit.]

Synopsis [Procedures for permuting truth tables.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Oct 26, 2011.]

Revision [

Id:

kitPerm.c,v 1.00 2011/11/26 00:00:00 alanmi Exp

]

Definition at line 28 of file kitPerm.c.

#define NFUNCS   (1<<20)

Definition at line 265 of file kitPerm.c.

Typedef Documentation

typedef unsigned char byte

Definition at line 38 of file kitPerm.c.

typedef unsigned short shot

Definition at line 37 of file kitPerm.c.

typedef unsigned __int64 word

DECLARATIONS ///.

Definition at line 36 of file kitPerm.c.

Function Documentation

void Kit_PermCompute	(	word *	o,
		word *	i,
		int	V
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 199 of file kitPerm.c.

{
    word * t;
    int v, n = (1 << (V-3));
    assert( V >= 6 && V <= 16 );
    for ( v = 0; v < n; v++ )
        ((byte *)i)[v] = P[((byte *)i)[v]];
    for ( v = 3; v < V; v++ )
    {
        Kit_PermCycleMany( (shot *)o, (byte *)i, V, v );
        t = i; i = o; o = t;
    }
    if ( V & 1 )
    {
        n = (1 << (V-6));
        for ( v = 0; v < n; v++ )
            o[v] = i[v];
    }
}

void Kit_PermComputeNaive	(	word *	F,
		int	nVars
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file kitPerm.c.

{
    extern void If_CluReverseOrder( word * pF, int nVars, int * V2P, int * P2V, int iVarStart );
    int i, V2P[16], P2V[16];
    for ( i = 0; i < nVars; i++ )
        V2P[i] = P2V[i] = i;
    If_CluReverseOrder( F, nVars, V2P, P2V, 0 );
}

void Kit_PermComputeTest

(

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 278 of file kitPerm.c.

{
    word * T = (word *)malloc( 8 * NFUNCS );
    word i, o, w = 0;
    int k, b;
    abctime clk;

    srand( 0 );

    clk = Abc_Clock();
    for ( k = 0; k < NFUNCS; k++ )
        for ( b = 0; b < 8; b++ )
            ((byte *)(T + k))[b] = (byte)(rand() & 0xFF);
    ABC_PRT( "Assign", Abc_Clock() - clk );

//    T[0] = 0xacaccacaaccaacca;
//    Kit_DsdPrintFromTruth( T, 6 );

    // perform measurements
    clk = Abc_Clock();
    for ( k = 0; k < NFUNCS; k++ )
    {
        i = T[k];
//        Kit_PermComputeNaive( &i, 6 );
        Tf( i, 6 );
    }
    ABC_PRT( "Perm1 ", Abc_Clock() - clk );

    // perform measurements
    clk = Abc_Clock();
    for ( k = 0; k < NFUNCS; k++ )
    {
        i = T[k];
        Kit_PermCompute( &o, &i, 6 );

//        w = T[k];
//        Kit_PermComputeNaive( &w, 6 );
//        assert( w == o );
    }
    ABC_PRT( "Perm2 ", Abc_Clock() - clk );

    assert( w == 0 );
    free( T );
}

void Kit_PermComputeTest_

(

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso [] `

Definition at line 334 of file kitPerm.c.

{
    word t, s;
    t = 0xacaccacaaccaacca;
//    Kit_DsdPrintFromTruth( &t, 6 ); printf( "\n" );
    s = Tf( t, 6 );
//    Kit_PermComputeNaive( &t, 6 );
//    Kit_DsdPrintFromTruth( &s, 6 ); printf( "\n" );
}

void Kit_PermCreateP

(

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 135 of file kitPerm.c.

{
    int i, s1, s2, r;
    for ( i = 0; i < 256; i++ )
    {
        if ( i % 16 == 0 )
            printf( "\n" );
        s1 = i & 0x0A;
        s2 = i & 0x50;
        r = i ^ s1 ^ s2 ^ (s1 << 3) ^ (s2 >> 3);
        assert( r < 256 );
        printf( "0x%02x, ", r );
    }
}

void Kit_PermCreateS

(

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 111 of file kitPerm.c.

{
    int i, n, r;
    for ( i = 0; i < 256; i++ )
    {
        if ( i % 8 == 0 )
            printf( "\n" );
        for ( r = n = 0; n < 8; n++ )
            r |= ((i & (1 << n)) << n);
        printf( "0x%04x, ", r );
    }
}

static void Kit_PermCycleMany ( shot *  s, byte *  b, int  V, int  v  )

inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 180 of file kitPerm.c.

{
    int i, n = (1 << (V - 1 - v)), m = (1 << (v-2));
    assert( v > 2 && v < V );
    for ( i = 0; i < n; i++, s += (m >> 1), b += m )
        Kit_PermCycleOne( s, b, v );   
}

static void Kit_PermCycleOne ( shot *  s, byte *  b, int  v  )

inlinestatic

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 161 of file kitPerm.c.

{
    int i, n = (1 << (v-3));
    assert( v > 2 && v < 16 );
    for ( i = 0; i < n; i++ )
        s[i] = S[b[i]] | (S[b[i+n]] << 1);
}

word M	(	word	f1,
		word	f2,
		int	n
	)

Definition at line 240 of file kitPerm.c.

{
    word temp = 0;
    word a = 1;
    int i;
    for(  i = 0; i < n; i++)
        temp = temp + (((f1>>i)&a) << (2*i) ) + (((f2>>i)&a) << (2*i+1));
    return temp;
}

word Tf	(	word	f,
		int	n
	)

Definition at line 250 of file kitPerm.c.

{
    if(n==1)
        return f;
    else
    {
//        int x = (int)pow(2,n-1);
        int x;
        x = (1 << (n-1));
        return (  M (Tf( (f << x) >> x, n-1), Tf( (f >> x), n-1), x) );     //def. of M just below the function
     }
}

Variable Documentation

byte P[256]

static

Initial value:

=
{
    0x00, 0x01, 0x10, 0x11, 0x04, 0x05, 0x14, 0x15, 0x40, 0x41, 0x50, 0x51, 0x44, 0x45, 0x54, 0x55,
    0x02, 0x03, 0x12, 0x13, 0x06, 0x07, 0x16, 0x17, 0x42, 0x43, 0x52, 0x53, 0x46, 0x47, 0x56, 0x57,
    0x20, 0x21, 0x30, 0x31, 0x24, 0x25, 0x34, 0x35, 0x60, 0x61, 0x70, 0x71, 0x64, 0x65, 0x74, 0x75,
    0x22, 0x23, 0x32, 0x33, 0x26, 0x27, 0x36, 0x37, 0x62, 0x63, 0x72, 0x73, 0x66, 0x67, 0x76, 0x77,
    0x08, 0x09, 0x18, 0x19, 0x0c, 0x0d, 0x1c, 0x1d, 0x48, 0x49, 0x58, 0x59, 0x4c, 0x4d, 0x5c, 0x5d,
    0x0a, 0x0b, 0x1a, 0x1b, 0x0e, 0x0f, 0x1e, 0x1f, 0x4a, 0x4b, 0x5a, 0x5b, 0x4e, 0x4f, 0x5e, 0x5f,
    0x28, 0x29, 0x38, 0x39, 0x2c, 0x2d, 0x3c, 0x3d, 0x68, 0x69, 0x78, 0x79, 0x6c, 0x6d, 0x7c, 0x7d,
    0x2a, 0x2b, 0x3a, 0x3b, 0x2e, 0x2f, 0x3e, 0x3f, 0x6a, 0x6b, 0x7a, 0x7b, 0x6e, 0x6f, 0x7e, 0x7f,
    0x80, 0x81, 0x90, 0x91, 0x84, 0x85, 0x94, 0x95, 0xc0, 0xc1, 0xd0, 0xd1, 0xc4, 0xc5, 0xd4, 0xd5,
    0x82, 0x83, 0x92, 0x93, 0x86, 0x87, 0x96, 0x97, 0xc2, 0xc3, 0xd2, 0xd3, 0xc6, 0xc7, 0xd6, 0xd7,
    0xa0, 0xa1, 0xb0, 0xb1, 0xa4, 0xa5, 0xb4, 0xb5, 0xe0, 0xe1, 0xf0, 0xf1, 0xe4, 0xe5, 0xf4, 0xf5,
    0xa2, 0xa3, 0xb2, 0xb3, 0xa6, 0xa7, 0xb6, 0xb7, 0xe2, 0xe3, 0xf2, 0xf3, 0xe6, 0xe7, 0xf6, 0xf7,
    0x88, 0x89, 0x98, 0x99, 0x8c, 0x8d, 0x9c, 0x9d, 0xc8, 0xc9, 0xd8, 0xd9, 0xcc, 0xcd, 0xdc, 0xdd,
    0x8a, 0x8b, 0x9a, 0x9b, 0x8e, 0x8f, 0x9e, 0x9f, 0xca, 0xcb, 0xda, 0xdb, 0xce, 0xcf, 0xde, 0xdf,
    0xa8, 0xa9, 0xb8, 0xb9, 0xac, 0xad, 0xbc, 0xbd, 0xe8, 0xe9, 0xf8, 0xf9, 0xec, 0xed, 0xfc, 0xfd,
    0xaa, 0xab, 0xba, 0xbb, 0xae, 0xaf, 0xbe, 0xbf, 0xea, 0xeb, 0xfa, 0xfb, 0xee, 0xef, 0xfe, 0xff
}

Definition at line 76 of file kitPerm.c.

shot S[256]

static

Definition at line 40 of file kitPerm.c.