1 /**CFile****************************************************************
2
3 FileName [vecMem.h]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Resizable arrays.]
8
9 Synopsis [Resizable array of memory pieces.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - July 20, 2012.]
16
17 Revision [$Id: vecMem.h,v 1.00 2012/07/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #ifndef ABC__misc__vec__vecMem_h
22 #define ABC__misc__vec__vecMem_h
23
24
25 ////////////////////////////////////////////////////////////////////////
26 /// INCLUDES ///
27 ////////////////////////////////////////////////////////////////////////
28
29 #include <stdio.h>
30
31 ABC_NAMESPACE_HEADER_START
32
33 /*
34 This vector stores pieces of memory of the given size.
35 It is useful for representing truth tables and any other objects
36 of the fixed size. It is better that Extra_MmFixed because the
37 entry IDs can be used as handles to retrieve memory pieces without
38 the need for an array of pointers from entry IDs into memory pieces
39 (this can save 8(4) bytes per object on a 64(32)-bit platform).
40 */
41
42 ////////////////////////////////////////////////////////////////////////
43 /// PARAMETERS ///
44 ////////////////////////////////////////////////////////////////////////
45
46 ////////////////////////////////////////////////////////////////////////
47 /// BASIC TYPES ///
48 ////////////////////////////////////////////////////////////////////////
49
50 typedef struct Vec_Mem_t_ Vec_Mem_t;
51 struct Vec_Mem_t_
52 {
53 int nEntrySize; // entry size (in terms of 8-byte words)
54 int nEntries; // number of entries currently used
55 int LogPageSze; // log2 of page size (in terms of entries)
56 int PageMask; // page mask
57 int nPageAlloc; // number of pages currently allocated
58 int iPage; // the number of a page currently used
59 word ** ppPages; // memory pages
60 Vec_Int_t * vTable; // hash table
61 Vec_Int_t * vNexts; // next pointers
62 };
63
64 ////////////////////////////////////////////////////////////////////////
65 /// MACRO DEFINITIONS ///
66 ////////////////////////////////////////////////////////////////////////
67
68 #define Vec_MemForEachEntry( p, pEntry, i ) \
69 for ( i = 0; (i < Vec_MemEntryNum(p)) && ((pEntry) = Vec_MemReadEntry(p, i)); i++ )
70
71 ////////////////////////////////////////////////////////////////////////
72 /// FUNCTION DEFINITIONS ///
73 ////////////////////////////////////////////////////////////////////////
74
75 /**Function*************************************************************
76
77 Synopsis [Allocates a memory vector.]
78
79 Description [Entry size is in terms of 8-byte words. Page size is log2
80 of the number of entries on one page.]
81
82 SideEffects []
83
84 SeeAlso []
85
86 ***********************************************************************/
Vec_MemAlloc_(Vec_Mem_t * p,int nEntrySize,int LogPageSze)87 static inline void Vec_MemAlloc_( Vec_Mem_t * p, int nEntrySize, int LogPageSze )
88 {
89 memset( p, 0, sizeof(Vec_Mem_t) );
90 p->nEntrySize = nEntrySize;
91 p->LogPageSze = LogPageSze;
92 p->PageMask = (1 << p->LogPageSze) - 1;
93 p->iPage = -1;
94 }
Vec_MemAlloc(int nEntrySize,int LogPageSze)95 static inline Vec_Mem_t * Vec_MemAlloc( int nEntrySize, int LogPageSze )
96 {
97 Vec_Mem_t * p;
98 p = ABC_CALLOC( Vec_Mem_t, 1 );
99 p->nEntrySize = nEntrySize;
100 p->LogPageSze = LogPageSze;
101 p->PageMask = (1 << p->LogPageSze) - 1;
102 p->iPage = -1;
103 return p;
104 }
Vec_MemFree(Vec_Mem_t * p)105 static inline void Vec_MemFree( Vec_Mem_t * p )
106 {
107 int i;
108 for ( i = 0; i <= p->iPage; i++ )
109 ABC_FREE( p->ppPages[i] );
110 ABC_FREE( p->ppPages );
111 ABC_FREE( p );
112 }
Vec_MemFreeP(Vec_Mem_t ** p)113 static inline void Vec_MemFreeP( Vec_Mem_t ** p )
114 {
115 if ( *p == NULL )
116 return;
117 Vec_MemFree( *p );
118 *p = NULL;
119 }
Vec_MemDup(Vec_Mem_t * pVec)120 static inline Vec_Mem_t * Vec_MemDup( Vec_Mem_t * pVec )
121 {
122 Vec_Mem_t * p = NULL;
123 return p;
124 }
125
126 /**Function*************************************************************
127
128 Synopsis [Duplicates the integer array.]
129
130 Description []
131
132 SideEffects []
133
134 SeeAlso []
135
136 ***********************************************************************/
Vec_MemFill(Vec_Mem_t * pVec,int nEntries)137 static inline void Vec_MemFill( Vec_Mem_t * pVec, int nEntries )
138 {
139 }
Vec_MemClean(Vec_Mem_t * pVec,int nEntries)140 static inline void Vec_MemClean( Vec_Mem_t * pVec, int nEntries )
141 {
142 }
143
144 /**Function*************************************************************
145
146 Synopsis []
147
148 Description []
149
150 SideEffects []
151
152 SeeAlso []
153
154 ***********************************************************************/
Vec_MemEntrySize(Vec_Mem_t * p)155 static inline int Vec_MemEntrySize( Vec_Mem_t * p )
156 {
157 return p->nEntrySize;
158 }
Vec_MemEntryNum(Vec_Mem_t * p)159 static inline int Vec_MemEntryNum( Vec_Mem_t * p )
160 {
161 return p->nEntries;
162 }
Vec_MemPageSize(Vec_Mem_t * p)163 static inline int Vec_MemPageSize( Vec_Mem_t * p )
164 {
165 return p->LogPageSze;
166 }
Vec_MemPageNum(Vec_Mem_t * p)167 static inline int Vec_MemPageNum( Vec_Mem_t * p )
168 {
169 return p->iPage+1;
170 }
171
172 /**Function*************************************************************
173
174 Synopsis []
175
176 Description []
177
178 SideEffects []
179
180 SeeAlso []
181
182 ***********************************************************************/
Vec_MemMemory(Vec_Mem_t * p)183 static inline double Vec_MemMemory( Vec_Mem_t * p )
184 {
185 return (double)sizeof(word) * p->nEntrySize * (1 << p->LogPageSze) * (p->iPage + 1) + (double)sizeof(word *) * p->nPageAlloc + (double)sizeof(Vec_Mem_t);
186 }
187
188 /**Function*************************************************************
189
190 Synopsis []
191
192 Description []
193
194 SideEffects []
195
196 SeeAlso []
197
198 ***********************************************************************/
Vec_MemReadEntry(Vec_Mem_t * p,int i)199 static inline word * Vec_MemReadEntry( Vec_Mem_t * p, int i )
200 {
201 assert( i >= 0 && i < p->nEntries );
202 return p->ppPages[i >> p->LogPageSze] + p->nEntrySize * (i & p->PageMask);
203 }
Vec_MemReadEntryLast(Vec_Mem_t * p)204 static inline word * Vec_MemReadEntryLast( Vec_Mem_t * p )
205 {
206 assert( p->nEntries > 0 );
207 return Vec_MemReadEntry( p, p->nEntries-1 );
208 }
Vec_MemWriteEntry(Vec_Mem_t * p,int i,word * pEntry)209 static inline void Vec_MemWriteEntry( Vec_Mem_t * p, int i, word * pEntry )
210 {
211 word * pPlace = Vec_MemReadEntry( p, i );
212 memmove( pPlace, pEntry, sizeof(word) * p->nEntrySize );
213 }
Vec_MemGetEntry(Vec_Mem_t * p,int i)214 static inline word * Vec_MemGetEntry( Vec_Mem_t * p, int i )
215 {
216 assert( i >= 0 );
217 if ( i >= p->nEntries )
218 {
219 int k, iPageNew = (i >> p->LogPageSze);
220 if ( p->iPage < iPageNew )
221 {
222 // realloc page pointers if needed
223 if ( iPageNew >= p->nPageAlloc )
224 p->ppPages = ABC_REALLOC( word *, p->ppPages, (p->nPageAlloc = p->nPageAlloc ? 2 * p->nPageAlloc : iPageNew + 32) );
225 // allocate new pages if needed
226 for ( k = p->iPage + 1; k <= iPageNew; k++ )
227 p->ppPages[k] = ABC_ALLOC( word, p->nEntrySize * (1 << p->LogPageSze) );
228 // update page counter
229 p->iPage = iPageNew;
230 }
231 // update entry counter
232 p->nEntries = i + 1;
233 }
234 return Vec_MemReadEntry( p, i );
235 }
Vec_MemSetEntry(Vec_Mem_t * p,int i,word * pEntry)236 static inline void Vec_MemSetEntry( Vec_Mem_t * p, int i, word * pEntry )
237 {
238 word * pPlace = Vec_MemGetEntry( p, i );
239 memmove( pPlace, pEntry, sizeof(word) * (size_t)p->nEntrySize );
240 }
Vec_MemPush(Vec_Mem_t * p,word * pEntry)241 static inline void Vec_MemPush( Vec_Mem_t * p, word * pEntry )
242 {
243 word * pPlace = Vec_MemGetEntry( p, p->nEntries );
244 memmove( pPlace, pEntry, sizeof(word) * (size_t)p->nEntrySize );
245 }
246
247 /**Function*************************************************************
248
249 Synopsis []
250
251 Description []
252
253 SideEffects []
254
255 SeeAlso []
256
257 ***********************************************************************/
Vec_MemShrink(Vec_Mem_t * p,int nEntriesNew)258 static inline void Vec_MemShrink( Vec_Mem_t * p, int nEntriesNew )
259 {
260 int i, iPageOld = p->iPage;
261 assert( nEntriesNew <= p->nEntries );
262 p->nEntries = nEntriesNew;
263 p->iPage = (nEntriesNew >> p->LogPageSze);
264 for ( i = p->iPage + 1; i <= iPageOld; i++ )
265 ABC_FREE( p->ppPages[i] );
266 }
267
268 /**Function*************************************************************
269
270 Synopsis []
271
272 Description []
273
274 SideEffects []
275
276 SeeAlso []
277
278 ***********************************************************************/
Vec_MemDumpDigit(FILE * pFile,int HexDigit)279 static inline void Vec_MemDumpDigit( FILE * pFile, int HexDigit )
280 {
281 assert( HexDigit >= 0 && HexDigit < 16 );
282 if ( HexDigit < 10 )
283 fprintf( pFile, "%d", HexDigit );
284 else
285 fprintf( pFile, "%c", 'A' + HexDigit-10 );
286 }
Vec_MemDump(FILE * pFile,Vec_Mem_t * pVec)287 static inline void Vec_MemDump( FILE * pFile, Vec_Mem_t * pVec )
288 {
289 word * pEntry;
290 int i, w, d;
291 if ( pFile == stdout )
292 printf( "Memory vector has %d entries: \n", Vec_MemEntryNum(pVec) );
293 Vec_MemForEachEntry( pVec, pEntry, i )
294 {
295 for ( w = pVec->nEntrySize - 1; w >= 0; w-- )
296 for ( d = 15; d >= 0; d-- )
297 Vec_MemDumpDigit( pFile, (int)(pEntry[w] >> (d<<2)) & 15 );
298 fprintf( pFile, "\n" );
299 }
300 }
301
302 /**Function*************************************************************
303
304 Synopsis [Hashing entries in the memory vector.]
305
306 Description []
307
308 SideEffects []
309
310 SeeAlso []
311
312 ***********************************************************************/
Vec_MemHashAlloc(Vec_Mem_t * p,int nTableSize)313 static inline void Vec_MemHashAlloc( Vec_Mem_t * p, int nTableSize )
314 {
315 assert( p->vTable == NULL && p->vNexts == NULL );
316 p->vTable = Vec_IntStartFull( Abc_PrimeCudd(nTableSize) );
317 p->vNexts = Vec_IntAlloc( nTableSize );
318 }
Vec_MemHashFree(Vec_Mem_t * p)319 static inline void Vec_MemHashFree( Vec_Mem_t * p )
320 {
321 if ( p == NULL )
322 return;
323 Vec_IntFreeP( &p->vTable );
324 Vec_IntFreeP( &p->vNexts );
325 }
Vec_MemHashKey(Vec_Mem_t * p,word * pEntry)326 static inline unsigned Vec_MemHashKey( Vec_Mem_t * p, word * pEntry )
327 {
328 static int s_Primes[8] = { 1699, 4177, 5147, 5647, 6343, 7103, 7873, 8147 };
329 int i, nData = 2 * p->nEntrySize;
330 unsigned * pData = (unsigned *)pEntry;
331 unsigned uHash = 0;
332 for ( i = 0; i < nData; i++ )
333 uHash += pData[i] * s_Primes[i & 0x7];
334 return uHash % Vec_IntSize(p->vTable);
335 }
Vec_MemHashLookup(Vec_Mem_t * p,word * pEntry)336 static int * Vec_MemHashLookup( Vec_Mem_t * p, word * pEntry )
337 {
338 int * pSpot = Vec_IntEntryP( p->vTable, Vec_MemHashKey(p, pEntry) );
339 for ( ; *pSpot != -1; pSpot = Vec_IntEntryP(p->vNexts, *pSpot) )
340 if ( !memcmp( Vec_MemReadEntry(p, *pSpot), pEntry, sizeof(word) * p->nEntrySize ) ) // equal
341 return pSpot;
342 return pSpot;
343 }
Vec_MemHashProfile(Vec_Mem_t * p)344 static void Vec_MemHashProfile( Vec_Mem_t * p )
345 {
346 int e;
347 for ( e = 0; e < 1000; e++ )
348 {
349 int Count = 0;
350 int * pSpot = Vec_IntEntryP( p->vTable, e );
351 for ( ; *pSpot != -1; pSpot = Vec_IntEntryP(p->vNexts, *pSpot) )
352 Count++;
353 printf( "%d ", Count );
354 }
355 printf( "\n" );
356 }
Vec_MemHashResize(Vec_Mem_t * p)357 static void Vec_MemHashResize( Vec_Mem_t * p )
358 {
359 word * pEntry;
360 int i, * pSpot;
361 //Vec_MemHashProfile( p );
362 Vec_IntFill( p->vTable, Abc_PrimeCudd(2 * Vec_IntSize(p->vTable)), -1 );
363 Vec_IntClear( p->vNexts );
364 Vec_MemForEachEntry( p, pEntry, i )
365 {
366 pSpot = Vec_MemHashLookup( p, pEntry );
367 assert( *pSpot == -1 );
368 *pSpot = Vec_IntSize(p->vNexts);
369 Vec_IntPush( p->vNexts, -1 );
370 }
371 assert( p->nEntries == Vec_IntSize(p->vNexts) );
372 }
Vec_MemHashInsert(Vec_Mem_t * p,word * pEntry)373 static int Vec_MemHashInsert( Vec_Mem_t * p, word * pEntry )
374 {
375 int * pSpot;
376 if ( p->nEntries > Vec_IntSize(p->vTable) )
377 Vec_MemHashResize( p );
378 pSpot = Vec_MemHashLookup( p, pEntry );
379 if ( *pSpot != -1 )
380 return *pSpot;
381 *pSpot = Vec_IntSize(p->vNexts);
382 Vec_IntPush( p->vNexts, -1 );
383 Vec_MemPush( p, pEntry );
384 assert( p->nEntries == Vec_IntSize(p->vNexts) );
385 return Vec_IntSize(p->vNexts) - 1;
386 }
387
388
389 /**Function*************************************************************
390
391 Synopsis [Allocates memory vector for storing truth tables.]
392
393 Description []
394
395 SideEffects []
396
397 SeeAlso []
398
399 ***********************************************************************/
Vec_MemAllocForTTSimple(int nVars)400 static inline Vec_Mem_t * Vec_MemAllocForTTSimple( int nVars )
401 {
402 int nWords = (nVars <= 6 ? 1 : (1 << (nVars - 6)));
403 Vec_Mem_t * vTtMem = Vec_MemAlloc( nWords, 12 );
404 Vec_MemHashAlloc( vTtMem, 10000 );
405 return vTtMem;
406 }
Vec_MemAllocForTT(int nVars,int fCompl)407 static inline Vec_Mem_t * Vec_MemAllocForTT( int nVars, int fCompl )
408 {
409 int Value, nWords = (nVars <= 6 ? 1 : (1 << (nVars - 6)));
410 word * uTruth = ABC_ALLOC( word, nWords );
411 Vec_Mem_t * vTtMem = Vec_MemAlloc( nWords, 12 );
412 Vec_MemHashAlloc( vTtMem, 10000 );
413 memset( uTruth, 0x00, sizeof(word) * nWords );
414 Value = Vec_MemHashInsert( vTtMem, uTruth ); assert( Value == 0 );
415 if ( fCompl )
416 memset( uTruth, 0x55, sizeof(word) * nWords );
417 else
418 memset( uTruth, 0xAA, sizeof(word) * nWords );
419 Value = Vec_MemHashInsert( vTtMem, uTruth ); assert( Value == 1 );
420 ABC_FREE( uTruth );
421 return vTtMem;
422 }
Vec_MemAddMuxTT(Vec_Mem_t * p,int nVars)423 static inline void Vec_MemAddMuxTT( Vec_Mem_t * p, int nVars )
424 {
425 int Value, nWords = (nVars <= 6 ? 1 : (1 << (nVars - 6)));
426 word * uTruth = ABC_ALLOC( word, nWords );
427 memset( uTruth, 0xCA, sizeof(word) * nWords );
428 Value = Vec_MemHashInsert( p, uTruth ); assert( Value == 2 );
429 ABC_FREE( uTruth );
430 }
Vec_MemDumpTruthTables(Vec_Mem_t * p,char * pName,int nLutSize)431 static inline void Vec_MemDumpTruthTables( Vec_Mem_t * p, char * pName, int nLutSize )
432 {
433 FILE * pFile;
434 char pFileName[1000];
435 sprintf( pFileName, "tt_%s_%02d.txt", pName ? pName : NULL, nLutSize );
436 pFile = pName ? fopen( pFileName, "wb" ) : stdout;
437 Vec_MemDump( pFile, p );
438 if ( pFile != stdout )
439 fclose( pFile );
440 printf( "Dumped %d %d-var truth tables into file \"%s\" (%.2f MB).\n",
441 Vec_MemEntryNum(p), nLutSize, pName ? pFileName : "stdout",
442 8.0 * Vec_MemEntryNum(p) * Vec_MemEntrySize(p) / (1 << 20) );
443 }
444
445 ABC_NAMESPACE_HEADER_END
446
447 #endif
448
449 ////////////////////////////////////////////////////////////////////////
450 /// END OF FILE ///
451 ////////////////////////////////////////////////////////////////////////
452
453