minilut.h 11.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
/**CFile****************************************************************

  FileName    [minilut.h]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Minimalistic representation of LUT mapped network.]

  Synopsis    [External declarations.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - September 29, 2012.]

  Revision    [$Id: minilut.h,v 1.00 2012/09/29 00:00:00 alanmi Exp $]

***********************************************************************/
 
#ifndef MINI_LUT__mini_lut_h
#define MINI_LUT__mini_lut_h

////////////////////////////////////////////////////////////////////////
///                          INCLUDES                                ///
////////////////////////////////////////////////////////////////////////

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

ABC_NAMESPACE_HEADER_START

////////////////////////////////////////////////////////////////////////
///                         PARAMETERS                               ///
////////////////////////////////////////////////////////////////////////

#define MINI_LUT_NULL       (0x7FFFFFFF)
#define MINI_LUT_NULL2      (0x7FFFFFFE)
#define MINI_LUT_START_SIZE (0x000000FF)

////////////////////////////////////////////////////////////////////////
///                         BASIC TYPES                              ///
////////////////////////////////////////////////////////////////////////

typedef struct Mini_Lut_t_       Mini_Lut_t;
struct Mini_Lut_t_ 
{
    int           nCap;
    int           nSize;
    int           nRegs;
    int           LutSize;
    int *         pArray;
    unsigned *    pTruths;
};

////////////////////////////////////////////////////////////////////////
///                      MACRO DEFINITIONS                           ///
////////////////////////////////////////////////////////////////////////

// memory management
#define MINI_LUT_ALLOC(type, num)     ((type *) malloc(sizeof(type) * (num)))
#define MINI_LUT_CALLOC(type, num)    ((type *) calloc((num), sizeof(type)))
#define MINI_LUT_FALLOC(type, num)    ((type *) memset(malloc(sizeof(type) * (num)), 0xff, sizeof(type) * (num)))
#define MINI_LUT_FREE(obj)            ((obj) ? (free((char *) (obj)), (obj) = 0) : 0)
#define MINI_LUT_REALLOC(type, obj, num) \
        ((obj) ? ((type *) realloc((char *)(obj), sizeof(type) * (num))) : \
         ((type *) malloc(sizeof(type) * (num))))

// compute truth table size measured in unsigned's
static int  Mini_LutWordNum( int LutSize ) 
{
    return LutSize > 5 ? 1 << (LutSize-5) : 1;
}

// internal procedures
static void Mini_LutGrow( Mini_Lut_t * p, int nCapMin )
{
    if ( p->nCap >= nCapMin )
        return;
    p->pArray  = MINI_LUT_REALLOC( int,      p->pArray,  nCapMin * p->LutSize ); 
    p->pTruths = MINI_LUT_REALLOC( unsigned, p->pTruths, nCapMin * Mini_LutWordNum(p->LutSize) ); 
    p->nCap   = nCapMin;
    assert( p->pArray );
    assert( p->pTruths );
}
static void Mini_LutPush( Mini_Lut_t * p, int nVars, int * pVars, unsigned * pTruth )
{
    int i, nWords = Mini_LutWordNum(p->LutSize);
    if ( p->nSize == p->nCap )
    {
        assert( p->LutSize*p->nSize < MINI_LUT_NULL/2 );
        if ( p->nCap < MINI_LUT_START_SIZE )
            Mini_LutGrow( p, MINI_LUT_START_SIZE );
        else
            Mini_LutGrow( p, 2 * p->nCap );
    }
    for ( i = 0; i < nVars; i++ )
100 101
        assert( pVars[i] >= 0 && pVars[i] < p->nSize );
    for ( i = 0; i < nVars; i++ )
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
        p->pArray[p->LutSize * p->nSize + i] = pVars[i];
    for ( ; i < p->LutSize; i++ )
        p->pArray[p->LutSize * p->nSize + i] = MINI_LUT_NULL;
    for ( i = 0; i < nWords; i++ )
        p->pTruths[nWords * p->nSize + i] = pTruth? pTruth[i] : 0;
    p->nSize++;
}

// accessing fanins
static int Mini_LutNodeFanin( Mini_Lut_t * p, int Id, int k )
{
    assert( Id >= 0 && Id < p->nSize );
    return p->pArray[p->LutSize*Id+k];
}
static unsigned * Mini_LutNodeTruth( Mini_Lut_t * p, int Id )    
{ 
    assert( Id >= 0 && Id < p->nSize ); 
    return p->pTruths + Id * Mini_LutWordNum(p->LutSize);
}

// working with LUTs
static int      Mini_LutNodeConst0()                           { return 0;                    }
static int      Mini_LutNodeConst1()                           { return 1;                    }

static int      Mini_LutNodeNum( Mini_Lut_t * p )              { return p->nSize;             }
static int      Mini_LutNodeIsConst( Mini_Lut_t * p, int Id )  { assert( Id >= 0 ); return Id == 0 || Id == 1; }
128 129 130
static int      Mini_LutNodeIsPi( Mini_Lut_t * p, int Id )     { assert( Id >= 0 ); return Id > 1 && Mini_LutNodeFanin( p, Id, 0 ) == MINI_LUT_NULL; }
static int      Mini_LutNodeIsPo( Mini_Lut_t * p, int Id )     { assert( Id >= 0 ); return Id > 1 && Mini_LutNodeFanin( p, Id, 0 ) != MINI_LUT_NULL && Mini_LutNodeFanin( p, Id, 1 ) == MINI_LUT_NULL2; }
static int      Mini_LutNodeIsNode( Mini_Lut_t * p, int Id )   { assert( Id >= 0 ); return Id > 1 && Mini_LutNodeFanin( p, Id, 0 ) != MINI_LUT_NULL && Mini_LutNodeFanin( p, Id, 1 ) != MINI_LUT_NULL2; }
131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181

static int      Mini_LutSize( Mini_Lut_t * p )                 { return p->LutSize;           }

// working with sequential AIGs
static int      Mini_LutRegNum( Mini_Lut_t * p )               { return p->nRegs;             }
static void     Mini_LutSetRegNum( Mini_Lut_t * p, int n )     { p->nRegs = n;                }

// iterators through objects
#define Mini_LutForEachPi( p, i )    for (i = 2; i < Mini_LutNodeNum(p); i++) if ( !Mini_LutNodeIsPi(p, i) )   {} else 
#define Mini_LutForEachPo( p, i )    for (i = 2; i < Mini_LutNodeNum(p); i++) if ( !Mini_LutNodeIsPo(p, i) )   {} else 
#define Mini_LutForEachNode( p, i )  for (i = 2; i < Mini_LutNodeNum(p); i++) if ( !Mini_LutNodeIsNode(p, i) ) {} else

// iterator through fanins
#define Mini_LutForEachFanin( p, i, Fan, k ) for (k = 0; (k < p->LutSize) && (Fan = Mini_LutNodeFanin(p, i, k)) < MINI_LUT_NULL2; k++) 

// constructor/destructor
static Mini_Lut_t * Mini_LutStart( int LutSize )
{
    Mini_Lut_t * p; int i;
    assert( LutSize >= 2 && LutSize <= 16 );
    p = MINI_LUT_CALLOC( Mini_Lut_t, 1 );
    p->LutSize = LutSize;
    p->nCap    = MINI_LUT_START_SIZE;
    p->pArray  = MINI_LUT_ALLOC( int,      p->nCap * p->LutSize );
    p->pTruths = MINI_LUT_ALLOC( unsigned, p->nCap * Mini_LutWordNum(p->LutSize) );
    Mini_LutPush( p, 0, NULL, NULL ); // const0
    Mini_LutPush( p, 0, NULL, NULL ); // const1
    for ( i = 0; i < Mini_LutWordNum(p->LutSize); i++ )
        p->pTruths[i] = 0;
    for ( i = 0; i < Mini_LutWordNum(p->LutSize); i++ )
        p->pTruths[Mini_LutWordNum(p->LutSize) + i] = ~0;
    return p;
}
static void Mini_LutStop( Mini_Lut_t * p )
{
    MINI_LUT_FREE( p->pArray );
    MINI_LUT_FREE( p->pTruths );
    MINI_LUT_FREE( p );
}
static void Mini_LutPrintStats( Mini_Lut_t * p )
{
    int i, nPis, nPos, nNodes;
    nPis = 0;
    Mini_LutForEachPi( p, i )
        nPis++;
    nPos = 0;
    Mini_LutForEachPo( p, i )
        nPos++;
    nNodes = 0;
    Mini_LutForEachNode( p, i )
        nNodes++;
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
    printf( "PI = %d. PO = %d. LUT = %d. FF = %d.\n", nPis, nPos, nNodes, p->nRegs );
}
static void Mini_LutPrint( Mini_Lut_t * p )
{
    int i, k, Fan;
    printf( "MiniLUT statistics: " );
    Mini_LutPrintStats( p );
    printf( "Printout of nodes:\n" );
    for ( i = 0; i < p->nSize; i++ )
    {
        printf( "%6d : ", i );
        if ( Mini_LutNodeIsConst(p, i) )
            printf( "Const%d", i );
        else if ( Mini_LutNodeIsPi(p, i) )
            printf( "PI" );
        else if ( Mini_LutNodeIsPo(p, i) )
            printf( "PO" );
        else if ( Mini_LutNodeIsNode(p, i) )
        {
            printf( "LUT%d  Fanins:", p->LutSize );
            Mini_LutForEachFanin( p, i, Fan, k )
                printf( " %6d", Fan );
            while ( k++ < p->LutSize )
                printf( "       " );
            printf( "   Function: " );
            for ( k = 31; k >= 0; k-- )
                printf( "%c", '0' + ((p->pTruths[i] >> k) & 1) );
        }
        printf( "\n" );
    }
    printf( "End of printout.\n" );
213 214 215 216 217 218 219 220 221 222 223 224 225
}

// serialization
static void Mini_LutDump( Mini_Lut_t * p, char * pFileName )
{
    FILE * pFile;
    int RetValue;
    pFile = fopen( pFileName, "wb" );
    if ( pFile == NULL )
    {
        printf( "Cannot open file for writing \"%s\".\n", pFileName );
        return;
    }
Alan Mishchenko committed
226 227 228 229 230
    RetValue = (int)fwrite( &p->nSize,   sizeof(int), 1, pFile );
    RetValue = (int)fwrite( &p->nRegs,   sizeof(int), 1, pFile );
    RetValue = (int)fwrite( &p->LutSize, sizeof(int), 1, pFile );
    RetValue = (int)fwrite( p->pArray,   sizeof(int), p->nSize * p->LutSize, pFile );
    RetValue = (int)fwrite( p->pTruths,  sizeof(int), p->nSize * Mini_LutWordNum(p->LutSize), pFile );
231 232 233 234 235 236 237 238 239 240 241 242 243
    fclose( pFile );
}
static Mini_Lut_t * Mini_LutLoad( char * pFileName )
{
    Mini_Lut_t * p;
    FILE * pFile;
    int RetValue, nSize;
    pFile = fopen( pFileName, "rb" );
    if ( pFile == NULL )
    {
        printf( "Cannot open file for reading \"%s\".\n", pFileName );
        return NULL;
    }
Alan Mishchenko committed
244
    RetValue = (int)fread( &nSize, sizeof(int), 1, pFile );
245 246
    p = MINI_LUT_CALLOC( Mini_Lut_t, 1 );
    p->nSize   = p->nCap = nSize;
Alan Mishchenko committed
247 248
    RetValue = (int)fread( &p->nRegs,   sizeof(int), 1, pFile );
    RetValue = (int)fread( &p->LutSize, sizeof(int), 1, pFile );
Alan Mishchenko committed
249 250
    p->pArray  = MINI_LUT_ALLOC( int,      p->nCap * p->LutSize );
    p->pTruths = MINI_LUT_ALLOC( unsigned, p->nCap * Mini_LutWordNum(p->LutSize) );
Alan Mishchenko committed
251 252
    RetValue = (int)fread( p->pArray,   sizeof(int), p->nCap * p->LutSize, pFile );
    RetValue = (int)fread( p->pTruths,  sizeof(int), p->nCap * Mini_LutWordNum(p->LutSize), pFile );
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
    fclose( pFile );
    return p;
}


// creating nodes 
// (constant nodes are created when LUT manager is created)
static int Mini_LutCreatePi( Mini_Lut_t * p )
{
    Mini_LutPush( p, 0, NULL, NULL );
    return p->nSize - 1;
}
static int Mini_LutCreatePo( Mini_Lut_t * p, int Var0 )
{
    assert( Var0 >= 0 && Var0 < p->nSize );
    Mini_LutPush( p, 1, &Var0, NULL );
    // mark PO by setting its 2nd fanin to the special number
    p->pArray[p->LutSize*(p->nSize - 1)+1] = MINI_LUT_NULL2;
    return p->nSize - 1;
}

// create LUT
static int Mini_LutCreateNode( Mini_Lut_t * p, int nVars, int * pVars, unsigned * pTruth )
{
    assert( nVars >= 0 && nVars <= p->LutSize );
    Mini_LutPush( p, nVars, pVars, pTruth );
    return p->nSize - 1;
}

// procedure to check the topological order during AIG construction
static int Mini_LutCheck( Mini_Lut_t * p )
{
    int status = 1;
    int i, k, iFaninVar;
    Mini_LutForEachNode( p, i )
    {
        for ( k = 0; k < p->LutSize; k++ )
        {
            iFaninVar = Mini_LutNodeFanin( p, i, k );
            if ( iFaninVar == MINI_LUT_NULL )
                continue;
            if ( iFaninVar >= p->LutSize * i )
                printf( "Fanin %d of LUT node %d is not in a topological order.\n", k, i ), status = 0;
        }
    }
    Mini_LutForEachPo( p, i )
    {
        iFaninVar = Mini_LutNodeFanin( p, i, 0 );
        if ( iFaninVar >= p->LutSize * i )
            printf( "Fanin %d of PO node %d is not in a topological order.\n", k, i ), status = 0;
    }
    return status;
}



////////////////////////////////////////////////////////////////////////
///                    FUNCTION DECLARATIONS                         ///
////////////////////////////////////////////////////////////////////////

ABC_NAMESPACE_HEADER_END

#endif

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////