/**CFile****************************************************************
FileName [aigIso.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [AIG package.]
Synopsis [Graph isomorphism package.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - April 28, 2007.]
Revision [$Id: aigIso.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
***********************************************************************/
#include "saig.h"
ABC_NAMESPACE_IMPL_START
/*
#define ISO_MASK 0x3FF
static int s_1kPrimes[ISO_MASK+1] =
{
901403,984877,908741,966307,924437,965639,918787,931067,982621,917669,981473,936407,990487,926077,922897,970861,
942317,961747,979717,978947,940157,987821,981221,917713,983083,992231,928253,961187,991817,927643,923129,934291,
998071,967567,961087,988661,910031,930481,904489,974167,941351,959911,963811,921463,900161,934489,905629,930653,
901819,909457,939871,924083,915113,937969,928457,946291,973787,912869,994093,959279,905803,995219,949903,911011,
986707,995053,930583,955511,928307,930889,968729,911507,949043,939359,961679,918041,937681,909091,963913,923539,
929587,953347,917573,913037,995387,976483,986239,946949,922489,917887,957553,931529,929813,949567,941683,905161,
928819,932417,900089,935903,926587,914467,967361,944833,945881,941741,915949,903407,904157,971863,993893,963607,
918943,912463,980957,962963,968089,904513,963763,907363,904097,904093,991343,918347,986983,986659,935819,903569,
929171,913933,999749,923123,961531,935861,915053,994853,943511,969923,927191,968333,949391,950959,968311,991409,
911681,987101,904027,975259,907399,946223,907259,900409,957221,901063,974657,912337,979001,970147,982301,968213,
923959,964219,935443,950161,989251,936127,985679,958159,930077,971899,944857,956083,914293,941981,909481,909047,
960527,958183,970687,914827,949051,928159,933551,964423,914041,915869,929953,901367,914219,975551,912391,917809,
991499,904781,949153,959887,961957,970943,947741,941263,984541,951437,984301,947423,905761,964913,971357,927709,
916441,941933,956993,988243,921197,905453,922081,950813,946331,998561,929023,937421,956231,907651,977897,905491,
960173,931837,955217,911951,990643,971021,949439,988453,996781,951497,906011,944309,911293,917123,983803,928097,
977747,928703,949957,919189,925513,923953,904997,986351,930689,902009,912007,906757,955793,926803,906809,962743,
911917,909329,949021,974651,959083,945367,905137,948377,931757,945409,920279,915007,960121,920609,946163,946391,
928903,932951,944329,901529,959809,918469,978643,911159,982573,965411,962233,911269,953273,974437,907589,992269,
929399,980431,905693,968267,970481,911089,950557,913799,920407,974489,909863,918529,975277,929323,971549,969181,
972787,964267,939971,943763,940483,971501,921637,945341,955211,920701,978349,969041,929861,904103,908539,995369,
995567,917471,908879,993821,947783,954599,978463,914519,942869,947263,988343,914657,956987,903641,943343,991063,
985403,926327,982829,958439,942017,960353,944987,934793,948971,999331,990767,915199,912211,946459,997019,965059,
924907,983233,943273,945359,919613,933883,928927,942763,994087,996211,918971,924871,938491,957139,918839,914629,
974329,900577,952823,941641,900461,946997,983123,935149,923693,908419,995651,912871,987067,920201,913921,929209,
962509,974599,972001,920273,922099,951781,958549,909971,975133,937207,929941,961397,980677,923579,980081,942199,
940319,942979,912349,942691,986989,947711,972343,932663,937877,940369,919571,927187,981439,932353,952313,915947,
915851,974041,989381,921029,997013,999199,914801,918751,997327,992843,982133,932051,964861,903979,937463,916781,
944389,986719,958369,961451,917767,954367,949853,934939,958807,975797,949699,957097,980773,969989,934907,909281,
904679,909833,991741,946769,908381,932447,957889,981697,905701,919033,999023,993541,912953,911719,934603,925019,
989341,912269,917789,981049,959149,989909,960521,952183,922627,936253,910957,972047,945037,940399,928313,928471,
962459,959947,927541,917333,926899,911837,985631,955127,922729,911171,900511,926251,918209,943477,955277,959773,
971039,917353,955313,930301,990799,957731,917519,938507,988111,911657,999721,968917,934537,903073,921703,966227,
904661,998213,954307,931309,909331,933643,910099,958627,914533,902903,950149,972721,915157,969037,988219,944137,
976411,952873,964787,970927,968963,920741,975187,966817,982909,975281,931907,959267,980711,924617,975691,962309,
976307,932209,989921,907969,947927,932207,945397,948929,904903,938563,961691,977671,963173,927149,951061,966547,
937661,983597,948139,948041,982759,941093,993703,910097,902347,990307,978217,996763,904919,924641,902299,929549,
977323,975071,932917,996293,925579,925843,915487,917443,999541,943043,919109,959879,912173,986339,939193,939599,
927077,977183,966521,959471,991943,985951,942187,932557,904297,972337,931751,964097,942341,966221,929113,960131,
906427,970133,996511,925637,971651,983443,981703,933613,939749,929029,958043,961511,957241,901079,950479,975493,
985799,909401,945601,911077,978359,948151,950333,968879,978727,961151,957823,950393,960293,915683,971513,915659,
943841,902477,916837,911161,958487,963691,949607,935707,987607,901613,972557,938947,931949,919021,982217,914737,
913753,971279,981683,915631,907807,970421,983173,916099,984587,912049,981391,947747,966233,932101,991733,969757,
904283,996601,979807,974419,964693,931537,917251,967961,910093,989321,988129,997307,963427,999221,962447,991171,
993137,914339,964973,908617,968567,920497,980719,949649,912239,907367,995623,906779,914327,918131,983113,962993,
977849,914941,932681,905713,932579,923977,965507,916469,984119,931981,998423,984407,993841,901273,910799,939847,
997153,971429,994927,912631,931657,968377,927833,920149,978041,947449,993233,927743,939737,975017,961861,984539,
938857,977437,950921,963659,923917,932983,922331,982393,983579,935537,914357,973051,904531,962077,990281,989231,
910643,948281,961141,911839,947413,923653,982801,903883,931943,930617,928679,962119,969977,926921,999773,954181,
963019,973411,918139,959719,918823,941471,931883,925273,918173,949453,946993,945457,959561,968857,935603,978283,
978269,947389,931267,902599,961189,947621,920039,964049,947603,913259,997811,943843,978277,972119,929431,918257,
991663,954043,910883,948797,929197,985057,990023,960961,967139,923227,923371,963499,961601,971591,976501,989959,
908731,951331,989887,925307,909299,949159,913447,969797,959449,976957,906617,901213,922667,953731,960199,960049,
985447,942061,955613,965443,947417,988271,945887,976369,919823,971353,962537,929963,920473,974177,903649,955777,
963877,973537,929627,994013,940801,985709,995341,936319,904681,945817,996617,953191,952859,934889,949513,965407,
988357,946801,970391,953521,905413,976187,968419,940669,908591,976439,915731,945473,948517,939181,935183,978067,
907663,967511,968111,981599,913907,933761,994933,980557,952073,906557,935621,914351,967903,949129,957917,971821,
925937,926179,955729,966871,960737,968521,949997,956999,961273,962683,990377,908851,932231,929749,932149,966971,
922079,978149,938453,958313,995381,906259,969503,922321,918947,972443,916411,935021,944429,928643,952199,918157,
917783,998497,944777,917771,936731,999953,975157,908471,989557,914189,933787,933157,938953,922931,986569,964363,
906473,963419,941467,946079,973561,957431,952429,965267,978473,924109,979529,991901,988583,918259,961991,978037,
938033,949967,986071,986333,974143,986131,963163,940553,950933,936587,923407,950357,926741,959099,914891,976231,
949387,949441,943213,915353,983153,975739,934243,969359,926557,969863,961097,934463,957547,916501,904901,928231,
903673,974359,932219,916933,996019,934399,955813,938089,907693,918223,969421,940903,940703,913027,959323,940993,
937823,906691,930841,923701,933259,911959,915601,960251,985399,914359,930827,950251,975379,903037,905783,971237
};
*/
/*
#define ISO_MASK 0x7F
static int s_1kPrimes[ISO_MASK+1] = {
1009, 1049, 1093, 1151, 1201, 1249, 1297, 1361, 1427, 1459,
1499, 1559, 1607, 1657, 1709, 1759, 1823, 1877, 1933, 1997,
2039, 2089, 2141, 2213, 2269, 2311, 2371, 2411, 2467, 2543,
2609, 2663, 2699, 2741, 2797, 2851, 2909, 2969, 3037, 3089,
3169, 3221, 3299, 3331, 3389, 3461, 3517, 3557, 3613, 3671,
3719, 3779, 3847, 3907, 3943, 4013, 4073, 4129, 4201, 4243,
4289, 4363, 4441, 4493, 4549, 4621, 4663, 4729, 4793, 4871,
4933, 4973, 5021, 5087, 5153, 5227, 5281, 5351, 5417, 5471,
5519, 5573, 5651, 5693, 5749, 5821, 5861, 5923, 6011, 6073,
6131, 6199, 6257, 6301, 6353, 6397, 6481, 6563, 6619, 6689,
6737, 6803, 6863, 6917, 6977, 7027, 7109, 7187, 7237, 7309,
7393, 7477, 7523, 7561, 7607, 7681, 7727, 7817, 7877, 7933,
8011, 8039, 8059, 8081, 8093, 8111, 8123, 8147
};
*/
/*
#define ISO_MASK 0x7
static int s_1kPrimes[ISO_MASK+1] = {
12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741
};
*/
#define ISO_MASK 0x3FF
static unsigned int s_1kPrimes[ISO_MASK+1] =
//#define ISO_MASK 0xFF
//static int s_1kPrimes[0x3FF+1] =
{
0x38c19891,0xde37b0ed,0xdebcd025,0xe19b7bbe,0x7e7ebd0e,0xaeed03a1,0x811230dc,0x10bfece0,
0xb3b23fb1,0x74176098,0xc34ec7c5,0x6bef8939,0xc40be5e3,0x2ab51a09,0xafc17cea,0x0dccc7a2,
0xdf7db34d,0x1009c96f,0x93fd7494,0x54385b33,0x6f36eed8,0xa1953f82,0xfbd1144a,0xde533a46,
0x23aa1cad,0x9a18943c,0xb65000d8,0x867e9974,0xe7880035,0xf9931ad4,0xcfca1e45,0x6b5aec96,
0xe9c1a119,0xfa4968c5,0x94cf93da,0xe8c9eac4,0x95884242,0x1bba52c7,0x9232c321,0x9cec8658,
0x984b6ad9,0x18a6eed3,0x950353e2,0x6222f6eb,0xdfbedd47,0xef0f9023,0xac932a26,0x590eaf55,
0x97d0a034,0xdc36cd2e,0x22736b37,0xdc9066b0,0x2eb2f98b,0x5d9c7baf,0x85747c9e,0x8aca1055,
0x50d66b74,0x2f01ae9e,0xa1a80123,0x3e1ce2dc,0xebedbc57,0x4e68bc34,0x855ee0cf,0x17275120,
0x2ae7f2df,0xf71039eb,0x7c283eec,0x70cd1137,0x7cf651f3,0xa87bfa7a,0x14d87f02,0xe82e197d,
0x8d8a5ebe,0x1e6a15dc,0x197d49db,0x5bab9c89,0x4b55dea7,0x55dede49,0x9a6a8080,0xe5e51035,
0xe148d658,0x8a17eb3b,0xe22e4b38,0xe5be2a9a,0xbe938cbb,0x3b981069,0x7f9c0c8e,0xf756df10,
0x8fa783f7,0x252062ce,0x3dc46b4b,0xf70f6432,0x3f378276,0x44b137a1,0x2bf74b77,0x04892ed6,
0xfd318de1,0xd58c235e,0x94c6d25b,0x7aa5f218,0x35c9e921,0x5732fbbb,0x06026481,0xf584a44f,
0x946e1b5f,0x8463d5b2,0x4ebca7b2,0x54887b15,0x08d1e804,0x5b22067d,0x794580f6,0xb351ea43,
0xbce555b9,0x19ae2194,0xd32f1396,0x6fc1a7f1,0x1fd8a867,0x3a89fdb0,0xea49c61c,0x25f8a879,
0xde1e6437,0x7c74afca,0x8ba63e50,0xb1572074,0xe4655092,0xdb6f8b1c,0xc2955f3c,0x327f85ba,
0x60a17021,0x95bd261d,0xdea94f28,0x04528b65,0xbe0109cc,0x26dd5688,0x6ab2729d,0xc4f029ce,
0xacf7a0be,0x4c912f55,0x34c06e65,0x4fbb938e,0x1533fb5f,0x03da06bd,0x48262889,0xc2523d7d,
0x28a71d57,0x89f9713a,0xf574c551,0x7a99deb5,0x52834d91,0x5a6f4484,0xc67ba946,0x13ae698f,
0x3e390f34,0x34fc9593,0x894c7932,0x6cf414a3,0xdb7928ab,0x13a3b8a3,0x4b381c1d,0xa10b54cb,
0x55359d9d,0x35a3422a,0x58d1b551,0x0fd4de20,0x199eb3f4,0x167e09e2,0x3ee6a956,0x5371a7fa,
0xd424efda,0x74f521c5,0xcb899ff6,0x4a42e4f4,0x747917b6,0x4b08df0b,0x090c7a39,0x11e909e4,
0x258e2e32,0xd9fad92d,0x48fe5f69,0x0545cde6,0x55937b37,0x9b4ae4e4,0x1332b40e,0xc3792351,
0xaff982ef,0x4dba132a,0x38b81ef1,0x28e641bf,0x227208c1,0xec4bbe37,0xc4e1821c,0x512c9d09,
0xdaef1257,0xb63e7784,0x043e04d7,0x9c2cea47,0x45a0e59a,0x281315ca,0x849f0aac,0xa4071ed3,
0x0ef707b3,0xfe8dac02,0x12173864,0x471f6d46,0x24a53c0a,0x35ab9265,0xbbf77406,0xa2144e79,
0xb39a884a,0x0baf5b6d,0xcccee3dd,0x12c77584,0x2907325b,0xfd1adcd2,0xd16ee972,0x345ad6c1,
0x315ebe66,0xc7ad2b8d,0x99e82c8d,0xe52da8c8,0xba50f1d3,0x66689cd8,0x2e8e9138,0x43e15e74,
0xf1ced14d,0x188ec52a,0xe0ef3cbb,0xa958aedc,0x4107a1bc,0x5a9e7a3e,0x3bde939f,0xb5b28d5a,
0x596fe848,0xe85ad00c,0x0b6b3aae,0x44503086,0x25b5695c,0xc0c31dcd,0x5ee617f0,0x74d40c3a,
0xd2cb2b9f,0x1e19f5fa,0x81e24faf,0xa01ed68f,0xcee172fc,0x7fdf2e4d,0x002f4774,0x664f82dd,
0xc569c39a,0xa2d4dcbe,0xaadea306,0xa4c947bf,0xa413e4e3,0x81fb5486,0x8a404970,0x752c980c,
0x98d1d881,0x5c932c1e,0xeee65dfb,0x37592cdd,0x0fd4e65b,0xad1d383f,0x62a1452f,0x8872f68d,
0xb58c919b,0x345c8ee3,0xb583a6d6,0x43d72cb3,0x77aaa0aa,0xeb508242,0xf2db64f8,0x86294328,
0x82211731,0x1239a9d5,0x673ba5de,0xaf4af007,0x44203b19,0x2399d955,0xa175cd12,0x595928a7,
0x6918928b,0xde3126bb,0x6c99835c,0x63ba1fa2,0xdebbdff0,0x3d02e541,0xd6f7aac6,0xe80b4cd0,
0xd0fa29f1,0x804cac5e,0x2c226798,0x462f624c,0xad05b377,0x22924fcd,0xfbea205c,0x1b47586d,
0x214d04ab,0xe093e487,0x10607ada,0x42b261cc,0x1a85e0f6,0xb851bfc3,0x77d5591c,0xda13f344,
0xc39c4c00,0xe60d75fc,0x7edae36a,0x3e4ac3ec,0x8bc38db4,0xe848dce9,0xb2407d4d,0x0d79c61e,
0x1e6c293a,0x7bc30986,0xdf18cb8f,0x23003172,0x6948e3fa,0x9b7e4f09,0x14b3b339,0x9c8078c2,
0x9a47c29f,0x85bb45ec,0x9ca35a93,0xd7db5227,0x1d9b0a10,0xb7fbbfe9,0x05b72426,0x6f30b2fa,
0x9fb44078,0xedffd3f8,0x1b02b7bc,0x43e3cfd3,0x0d44293e,0x25c8d552,0xedd3f85d,0x6f921c8c,
0x953cca0c,0x9c975b70,0xc6bd0b53,0x4f204f3e,0xa3cc69cc,0xceec390b,0x34905626,0x82ad5d41,
0xe46589a5,0x7989841d,0x045d7d9f,0xe49b7b2f,0x46baf101,0x996f92de,0x427566c8,0x918a1ee1,
0xf4baa589,0x6bdff7c7,0x3c6936ea,0xe85bfb70,0x5d96ea26,0x6d5a8991,0x7f0a528d,0x852f0634,
0x2ec04501,0x5ca15c35,0xd8695e7a,0x456876c7,0x52e97b83,0x34b4c5ed,0x54d73fbb,0x44a6be01,
0xf8019155,0x33d55a31,0x3fe51c99,0xe1cb94fd,0x8c39cd60,0xd585efba,0x2765579b,0xb8f7ed12,
0xbb04b2cd,0xd8859981,0xd966988d,0xa68bfeda,0x73110705,0x38d6aec0,0x613bc275,0xc7283c2d,
0xe051d0b1,0x32b8c2ee,0x0e73fb9e,0x7ab05c25,0x6ff652b9,0x45aeabc6,0x6be1a891,0x5b43531b,
0xcd711248,0x2b777d40,0x46956d16,0x474355a8,0xe872d6c6,0xe4158d96,0xabe03036,0x5b4fd9a4,
0xeceba1db,0xaac9713f,0xe953153b,0xf44a9229,0x460cba72,0xfd13fdf6,0x8bbf82ae,0xaf55778f,
0xa447a5b2,0x98b647b3,0x5f351c57,0x69d0bb71,0xf14d2706,0x78b1a3af,0x7206c73f,0x3f5cd4a6,
0x5c0e4515,0xdb46a663,0x10c3a9b0,0x8eda7748,0x52bb44c9,0x3df62689,0xc83e2732,0xf36c99af,
0x7ec7a94c,0x5c823718,0x6586e58e,0x4b726e75,0xcfe03a05,0x34eb2f4b,0xf4eec9cf,0xb38d6d73,
0x71fafa9e,0x0371a29a,0xc405f83b,0x889f49c2,0xd1443000,0x469665bf,0x609ed65d,0x67c8f9ba,
0x9d2f6055,0xb91b8eb1,0x96c809fe,0x2d6ab0f5,0xc16d4f04,0x590171ab,0x73d67526,0xf724e44c,
0x6aef02b7,0x6489a325,0x4458401e,0x22d94ad7,0x05e5be57,0x5634fad8,0x951fcf70,0x4baad7f0,
0x40c1090d,0xedc28abd,0x343cc6e4,0x4ff7c030,0x0734a641,0x2635a90e,0x2e000c84,0x4b617a70,
0x872e9c9e,0x3dceeb42,0xd0fcc398,0x9cc9b9c8,0x2de02f0c,0xaf0e2614,0xa60253aa,0xe0517492,
0xa7bde4b4,0x3bb66d7d,0x7f215e82,0xf259de66,0xe17380fe,0xdbc718b4,0x66abcc29,0xf0826e1f,
0x08f60995,0xce81b933,0xa832c0e9,0x37aed7d4,0x8a75c261,0x916627b4,0xd486a04b,0x64fd0fde,
0x1261328a,0xe037772f,0xb5b71117,0x55d04bd8,0x8f6c1c7b,0xb9f5fcdd,0x5918f756,0x25c90099,
0x2e8787db,0x58e14e38,0x0d397852,0x32c8e33b,0x5ae2b795,0x3a7b3ff7,0x5eebf893,0x1aeee816,
0xc2ef31d0,0x1d86e615,0x183f1de3,0xb89d46c4,0x525ebbf6,0xfe0198ca,0x4986cc4a,0x2a75701e,
0x382158b1,0x192ee88f,0x3e512912,0xcd571c3d,0xdf694fe8,0xec8ead1d,0x83719ac3,0x3f654079,
0xf6a623c5,0x33e1fc6e,0xe7f7c426,0x5bff0f6c,0x698a9bb1,0xec2a29ba,0x75358b45,0x40c6ffef,
0x6605bb55,0x53a8c97a,0x7bba1569,0x499bc51b,0x5849c89a,0xe6ddb267,0x8659c719,0x14a05548,
0xeec648a9,0x618af87a,0x62214521,0x7f36e610,0x152efeeb,0xc2b0f0ed,0x1d657588,0xa5fcec4b,
0xf872f109,0x46903038,0x04b57b97,0xe5d51b14,0x06c264ec,0x68aa8d14,0xa4e1bed8,0xdae169c2,
0xeb90debd,0xe8c11a7a,0xcafce013,0x63820cee,0x948c23e5,0xc1d42ea3,0x8256c951,0x9b587773,
0x2fa8380c,0x30255e09,0x1a809cdc,0xe1446068,0x2714621d,0xb3347d64,0x1f4cbf3d,0xd068bc26,
0x2c422740,0x06c4a3ad,0x5dc9d63c,0x4724bf48,0x28e34add,0x27d5221d,0xe349c7e2,0x6119e0a5,
0x4ae7d29f,0x53a7912d,0xfc5db779,0x7d28d357,0xfd80036d,0x06bcc597,0x36d70a8a,0x37738cb7,
0xf11e6272,0xfdd5d153,0x5dc666dc,0x6b5a415d,0x1073b415,0x36f30d9a,0x807daf7b,0x387f6823,
0x8970fe00,0xee560be5,0xea8c0bad,0xfac2b422,0xc845861d,0xa181a2ee,0x29c4dffd,0x4d441bb2,
0x7a64cf93,0x0c33e6ac,0x0a35d034,0x1067d26d,0x8c7da0cc,0x2d6e2d5a,0x9932c25a,0x5fca4e2c,
0x2c82fd71,0x41730b70,0x244bdbb9,0x96514307,0xc6a32a6b,0xc4c256a7,0x38517fd8,0x541aa859,
0x0752afe3,0x741e22f9,0xa2565483,0x7588b0b9,0xdd404e42,0x4d86c49d,0x6fa93fc1,0x163bd200,
0x745d0d31,0x8d3dd20e,0xebdc64db,0x9315c149,0x39db3299,0xb0c22004,0xa4c0295b,0x8b3573eb,
0xd92a40a3,0x73d6c379,0x67673309,0xdaff1d7f,0x42fcfeb8,0xd57c11a4,0x402066ef,0x9d1134e0,
0x9f417081,0x10f49e00,0x7e7ee855,0x314e6d25,0x602bdbe6,0xa4be4045,0xac511dc4,0x33d6bda8,
0x2f2bc412,0x4b9c0b6c,0x98aaab06,0x7f0a5801,0xfbf1f16d,0x058f54ae,0x4fd97724,0x348cb50b,
0xef6f659f,0x0cd8b184,0x1d71a666,0xae3c87dd,0x7bd56793,0xe0f8f6a8,0x90429c55,0x8a3cc4d0,
0x49957b70,0x3baf3912,0x755efebb,0xa5eca17f,0x486065a1,0x1dffcefb,0xd914b3a0,0x1ced93c1,
0xa4262dcd,0xc12a4adc,0x08f6de4e,0x4c204faf,0xca1815de,0xa4af836f,0x91d5e44d,0xd2a7caa4,
0x68a9a3fe,0x844f8dac,0x3fc36c67,0x8be23937,0x69879d94,0x5d0dbecb,0x1f0f59a4,0x94721142,
0xfca6064a,0x6d28aa48,0x804cd04e,0x4a3906de,0x8e352509,0x302326d9,0xed4937ed,0x4a570e63,
0xcaa57efb,0x64bd4878,0x3419334a,0x712e5f6b,0x9fa9d687,0x06f8645f,0x620ca96f,0xdc5d6cce,
0x392f3257,0x52140f06,0xc4b3bda4,0xe8c7eba7,0x066bd754,0xc5941f26,0xe6dfd573,0x328dd14d,
0xb1cb4ba7,0x1d37a9b8,0x96a195a5,0x970e535a,0x290351b8,0x570000f6,0xe14ae341,0x35ede6a6,
0x9a02f032,0xaf2ebb58,0x146be492,0x670b3e4b,0x72fa6cfd,0xa243af97,0xbbd5fc21,0xcb8852a2,
0x5d5b4a42,0xeefff0ac,0xa59ad1b6,0x3ec55544,0x48d64f69,0x9065d3d0,0xdd09485b,0xdd63bd09,
0x605e811d,0xc4b4ed7d,0xb0b58558,0x0644400b,0x12222346,0x086f146a,0xad6dee36,0x5488d1a3,
0x0c93bc0c,0x18555d92,0x9f4427bf,0xa590a66a,0x3a630fda,0xf1681c2e,0x948a16fb,0x16fe3338,
0xc9832357,0xd1e8e6b5,0xd9cfe034,0x05b22f26,0x27233c6e,0x355890e1,0xfbe6eaf3,0x0dcd8e8f,
0x00b5df46,0xd97730ac,0xc6dfd8ff,0x0cb1840a,0x41e9d249,0xbb471b4e,0x480b8f63,0x1ffe8871,
0x17b11821,0x1709e440,0xcefb3668,0xa4954ddd,0xf03ef8b5,0x6b3e633c,0xe5813096,0x3697c9a6,
0x7800f52f,0x73a7aa39,0x59ac23b7,0xb4663166,0x9ca9d6f8,0x2d441072,0x38cef3d3,0x39a3faf6,
0x89299fb9,0xd558295f,0xcf79c633,0x232dd96e,0xadb2955b,0xe962cbb9,0xab7c0061,0x1027c329,
0xb4b43e07,0x25240a7a,0x98ea4825,0xdbf2edbd,0x8be15d26,0x879f3cd9,0xa4138089,0xa32dcb06,
0x602af961,0x4b13f451,0x1c87d0d5,0xc3bb141b,0x9ebf55a1,0xef030a9a,0x8d199b93,0xdabcbb56,
0xf412f80f,0x302e90ad,0xc4d9878b,0xc392f650,0x4fd3a614,0x0a96ddc4,0xcd1878c7,0x9ddd3ae1,
0xdaf46458,0xba7c8656,0xf667948f,0xc37e3c23,0x04a577c6,0xbe615f1e,0xcc97406c,0xd497f16f,
0x79586586,0xd2057d14,0x1bb92028,0xab888e5e,0x26bef100,0xf46b3671,0xf21f1acc,0x67f288c8,
0x39c722df,0x61d21eaf,0x9c5853a0,0x63b693c7,0x1ea53c0a,0x95bc0a85,0xa7372f2d,0x3ef6a6b3,
0x82c9c4ac,0x4dea10ee,0xdfcb543d,0xd412f427,0x53e27f2c,0x875d8422,0x5367a7d8,0x41acf3fa,
0xbce47234,0x8056fb9a,0x4e9a4c48,0xe4a45945,0x2cfee3ae,0xb4554b10,0x5e37a915,0x591b1963,
0x4fa255c1,0xe01c897b,0x504e6208,0x7c7368eb,0x13808fd7,0x02ac0816,0x30305d2c,0x6c4bbdb7,
0xa48a9599,0x57466059,0x4c6ebfc7,0x8587ccdf,0x6ff0abf0,0x5b6b63fe,0x31d9ec64,0x63458abd,
0x21245905,0xccdb28fc,0xac828acb,0xe5e82bea,0xa7d76141,0xa699038e,0xcaba7e06,0x2710253f,
0x2ff9c94d,0x26e48a2c,0xd713ec5e,0x869f2ed4,0x25bcd712,0xcb3e918f,0x615c3a5a,0x9fb43903,
0x37900eb9,0x4f682db0,0x35a80dc6,0x4eb27c65,0x502735ab,0xb163b4c8,0x604649a8,0xb23a6cd3,
0x9f715091,0x2e6fbb51,0x2ec9144b,0x272cbe65,0x90a0a453,0x420e1503,0x2d00d338,0x4aa96675,
0xd025b61c,0xab02d9d7,0x2afe2a37,0xf8129b9b,0x4db04c54,0x654a5c06,0x3213ff51,0x4e09d0b1,
0x333369a3,0xae27310a,0x91d076d0,0xa96ebcd0,0xefde54f4,0x021c309a,0xd506f53d,0xa5635251,
0x2f23916e,0x1fe86bb1,0xcbc62160,0x2147c8cc,0xdeb3e47c,0x028e3987,0x8061de42,0x39be931b,
0x2b7e54c5,0xe64d2f96,0x4069522d,0x4aa66857,0x83b62634,0x4ba72095,0x9aade2a9,0xf1223cd9,
0x91cbddf0,0xec5d237f,0x593f3280,0x0b924439,0x446f4063,0xc66f8d8c,0x8b7128ba,0xb597f451,
0xc8925236,0x1720f235,0x7cd2e9a0,0x4c130339,0x8a665a52,0x5bef2733,0xba35d9bc,0x6d26644c,
0x385cdce1,0x509e4280,0x12aa9ed7,0xf5314d21,0xbe249d4a,0xf32e9753,0x91821cf9,0x01d63491,
0x49afa237,0x80e0bc27,0x844d796b,0xeff5ccb7,0x46303091,0x743484b4,0x77de1ab7,0x5ab00bea,
0x6316cd81,0x8ded07f4,0x3845a3a5,0x206625c4,0x8c123c6f,0xc80a971e,0xd4d4fa3f,0x5eba911d,
0xee168406,0x61cdcbad,0x981a44cd,0x718d030f,0xf653e92e,0xd5b77859,0x11e9e5d9,0xf6fe6ff3,
0x5239f010,0xe289b21b,0x0b52832b,0xca700c62,0xee7a5e15,0x8543ce2c,0x94a703cc,0x0b844d34,
0xf70638e5,0xfa286206,0xf8778906,0x1419e883,0xdb0fc46b,0xbeb74261,0xc6957b62,0x8352d2a8,
0x460586ce,0x90b28336,0xc9107ea8,0x3590403b,0x259a4279,0x6a1a7bbe,0x0f3b76e1,0x4872a716,
0xa5bfff13,0x8b30be72,0xe5a68957,0x17dbbc52,0x33a40187,0x7074220c,0xd8221b92,0x40ec7448,
0x7dbbcdfc,0xd5a9bb83,0xb4c0d25c,0xa0040390,0x6fb429dc,0xb8cede12,0x87d193bd,0x55c6e004
};
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
#define ISO_NUM_INTS 3
typedef struct Iso_Obj_t_ Iso_Obj_t;
struct Iso_Obj_t_
{
// hashing entries (related to the parameter ISO_NUM_INTS!)
unsigned Level : 30;
unsigned nFinNeg : 2;
unsigned FaninSig;
unsigned FanoutSig;
// other data
int iNext; // hash table entry
int iClass; // next one in class
int Id; // unique ID
};
typedef struct Iso_Man_t_ Iso_Man_t;
struct Iso_Man_t_
{
Aig_Man_t * pAig; // user's AIG manager
Iso_Obj_t * pObjs; // isomorphism objects
int nObjIds; // counter of object IDs
int nClasses; // total number of classes
int nEntries; // total number of entries
int nSingles; // total number of singletons
int nObjs; // total objects
int nBins; // hash table size
int * pBins; // hash table
Vec_Ptr_t * vSingles; // singletons
Vec_Ptr_t * vClasses; // other classes
Vec_Ptr_t * vTemp1; // other classes
Vec_Ptr_t * vTemp2; // other classes
abctime timeHash;
abctime timeFout;
abctime timeSort;
abctime timeOther;
abctime timeTotal;
};
static inline Iso_Obj_t * Iso_ManObj( Iso_Man_t * p, int i ) { assert( i >= 0 && i < p->nObjs ); return i ? p->pObjs + i : NULL; }
static inline int Iso_ObjId( Iso_Man_t * p, Iso_Obj_t * pObj ) { assert( pObj > p->pObjs && pObj < p->pObjs + p->nObjs ); return pObj - p->pObjs; }
static inline Aig_Obj_t * Iso_AigObj( Iso_Man_t * p, Iso_Obj_t * q ) { return Aig_ManObj( p->pAig, Iso_ObjId(p, q) ); }
#define Iso_ManForEachObj( p, pObj, i ) \
for ( i = 1; (i < p->nObjs) && ((pObj) = Iso_ManObj(p, i)); i++ ) if ( pIso->Level == -1 ) {} else
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
//extern void Iso_ReadPrimes( char * pFileName );
//Iso_ReadPrimes( "primes.txt" );
/**Function*************************************************************
Synopsis [Read primes from file.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ReadPrimes( char * pFileName )
{
FILE * pFile;
int Nums[10000];
int i, j, Temp, nSize = 0;
// read the numbers
pFile = fopen( pFileName, "rb" );
while ( fscanf( pFile, "%d", Nums + nSize++ ) == 1 );
fclose( pFile );
assert( nSize >= (1<<10) );
// randomly permute
srand( 111 );
for ( i = 0; i < nSize; i++ )
{
j = rand() % nSize;
Temp = Nums[i];
Nums[i] = Nums[j];
Nums[j] = Temp;
}
// write out
for ( i = 0; i < 64; i++ )
{
printf( " " );
for ( j = 0; j < 16; j++ )
printf( "%d,", Nums[i*16+j] );
printf( "\n" );
}
}
/**Function*************************************************************
Synopsis [Read primes from file.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_FindNumbers()
{
unsigned Nums[1024];
unsigned char * pNums = (unsigned char *)Nums;
int i, j;
srand( 111 );
for ( i = 0; i < 1024 * 4; i++ )
pNums[i] = (unsigned char)rand();
// write out
for ( i = 0; i < 128; i++ )
{
printf( " " );
for ( j = 0; j < 8; j++ )
printf( "0x%08x,", Nums[i*8+j] );
printf( "\n" );
}
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManObjCount_rec( Aig_Man_t * p, Aig_Obj_t * pObj, int * pnNodes, int * pnEdges )
{
if ( Aig_ObjIsCi(pObj) )
return;
if ( Aig_ObjIsTravIdCurrent(p, pObj) )
return;
Aig_ObjSetTravIdCurrent(p, pObj);
Iso_ManObjCount_rec( p, Aig_ObjFanin0(pObj), pnNodes, pnEdges );
Iso_ManObjCount_rec( p, Aig_ObjFanin1(pObj), pnNodes, pnEdges );
(*pnEdges) += Aig_ObjFaninC0(pObj) + Aig_ObjFaninC1(pObj);
(*pnNodes)++;
}
void Iso_ManObjCount( Aig_Man_t * p, Aig_Obj_t * pObj, int * pnNodes, int * pnEdges )
{
assert( Aig_ObjIsNode(pObj) );
*pnNodes = *pnEdges = 0;
Aig_ManIncrementTravId( p );
Iso_ManObjCount_rec( p, pObj, pnNodes, pnEdges );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Iso_Man_t * Iso_ManStart( Aig_Man_t * pAig )
{
Iso_Man_t * p;
p = ABC_CALLOC( Iso_Man_t, 1 );
p->pAig = pAig;
p->nObjs = Aig_ManObjNumMax( pAig );
p->pObjs = ABC_CALLOC( Iso_Obj_t, p->nObjs );
p->nBins = Abc_PrimeCudd( p->nObjs );
p->pBins = ABC_CALLOC( int, p->nBins );
p->vSingles = Vec_PtrAlloc( 1000 );
p->vClasses = Vec_PtrAlloc( 1000 );
p->vTemp1 = Vec_PtrAlloc( 1000 );
p->vTemp2 = Vec_PtrAlloc( 1000 );
p->nObjIds = 1;
return p;
}
void Iso_ManStop( Iso_Man_t * p, int fVerbose )
{
if ( fVerbose )
{
p->timeOther = p->timeTotal - p->timeHash - p->timeFout;
ABC_PRTP( "Building ", p->timeFout, p->timeTotal );
ABC_PRTP( "Hashing ", p->timeHash-p->timeSort, p->timeTotal );
ABC_PRTP( "Sorting ", p->timeSort, p->timeTotal );
ABC_PRTP( "Other ", p->timeOther, p->timeTotal );
ABC_PRTP( "TOTAL ", p->timeTotal, p->timeTotal );
}
Vec_PtrFree( p->vTemp1 );
Vec_PtrFree( p->vTemp2 );
Vec_PtrFree( p->vClasses );
Vec_PtrFree( p->vSingles );
ABC_FREE( p->pBins );
ABC_FREE( p->pObjs );
ABC_FREE( p );
}
/**Function*************************************************************
Synopsis [Compares two objects by their signature.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Iso_ObjCompare( Iso_Obj_t ** pp1, Iso_Obj_t ** pp2 )
{
return -memcmp( *pp1, *pp2, sizeof(int) * ISO_NUM_INTS );
}
/**Function*************************************************************
Synopsis [Compares two objects by their ID.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Iso_ObjCompareByData( Aig_Obj_t ** pp1, Aig_Obj_t ** pp2 )
{
Aig_Obj_t * pIso1 = *pp1;
Aig_Obj_t * pIso2 = *pp2;
assert( Aig_ObjIsCi(pIso1) || Aig_ObjIsCo(pIso1) );
assert( Aig_ObjIsCi(pIso2) || Aig_ObjIsCo(pIso2) );
return pIso1->iData - pIso2->iData;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Iso_ObjHash( Iso_Obj_t * pIso, int nBins )
{
static unsigned BigPrimes[8] = {12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
unsigned * pArray = (unsigned *)pIso;
unsigned i, Value = 0;
assert( ISO_NUM_INTS < 8 );
for ( i = 0; i < ISO_NUM_INTS; i++ )
Value ^= BigPrimes[i] * pArray[i];
return Value % nBins;
}
static inline int Iso_ObjHashAdd( Iso_Man_t * p, Iso_Obj_t * pIso )
{
Iso_Obj_t * pThis;
int * pPlace = p->pBins + Iso_ObjHash( pIso, p->nBins );
p->nEntries++;
for ( pThis = Iso_ManObj(p, *pPlace);
pThis; pPlace = &pThis->iNext,
pThis = Iso_ManObj(p, *pPlace) )
if ( Iso_ObjCompare( &pThis, &pIso ) == 0 ) // equal signatures
{
if ( pThis->iClass == 0 )
{
p->nClasses++;
p->nSingles--;
}
// add to the list
pIso->iClass = pThis->iClass;
pThis->iClass = Iso_ObjId( p, pIso );
return 1;
}
// create new list
*pPlace = Iso_ObjId( p, pIso );
p->nSingles++;
return 0;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManCollectClasses( Iso_Man_t * p )
{
Iso_Obj_t * pIso;
int i;
abctime clk = Abc_Clock();
Vec_PtrClear( p->vSingles );
Vec_PtrClear( p->vClasses );
for ( i = 0; i < p->nBins; i++ )
{
for ( pIso = Iso_ManObj(p, p->pBins[i]); pIso; pIso = Iso_ManObj(p, pIso->iNext) )
{
assert( pIso->Id == 0 );
if ( pIso->iClass )
Vec_PtrPush( p->vClasses, pIso );
else
Vec_PtrPush( p->vSingles, pIso );
}
}
clk = Abc_Clock();
Vec_PtrSort( p->vSingles, (int (*)(void))Iso_ObjCompare );
Vec_PtrSort( p->vClasses, (int (*)(void))Iso_ObjCompare );
p->timeSort += Abc_Clock() - clk;
assert( Vec_PtrSize(p->vSingles) == p->nSingles );
assert( Vec_PtrSize(p->vClasses) == p->nClasses );
// assign IDs to singletons
Vec_PtrForEachEntry( Iso_Obj_t *, p->vSingles, pIso, i )
if ( pIso->Id == 0 )
pIso->Id = p->nObjIds++;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Iso_Man_t * Iso_ManCreate( Aig_Man_t * pAig )
{
int fUseXor = 0;
Iso_Man_t * p;
Iso_Obj_t * pIso, * pIsoF;
Aig_Obj_t * pObj, * pObjLi;
int i;
p = Iso_ManStart( pAig );
// create TFI signatures
Aig_ManForEachObj( pAig, pObj, i )
{
if ( Aig_ObjIsCo(pObj) )
continue;
pIso = p->pObjs + i;
pIso->Level = pObj->Level;
// pIso->nFinNeg = Aig_ObjFaninC0(pObj) + Aig_ObjFaninC1(pObj);
assert( pIso->FaninSig == 0 );
assert( pIso->FanoutSig == 0 );
if ( fUseXor )
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIso->FaninSig ^= pIsoF->FaninSig;
pIso->FaninSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIso->FaninSig ^= pIsoF->FaninSig;
pIso->FaninSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
}
else
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIso->FaninSig += pIsoF->FaninSig;
pIso->FaninSig += pIso->Level * s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIso->FaninSig += pIsoF->FaninSig;
pIso->FaninSig += pIso->Level * s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
}
}
// create TFO signatures
Aig_ManForEachObjReverse( pAig, pObj, i )
{
if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
continue;
pIso = p->pObjs + i;
if ( fUseXor )
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig ^= pIso->FanoutSig;
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIsoF->FanoutSig ^= pIso->FanoutSig;
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
else if ( Aig_ObjIsCo(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig ^= pIso->FanoutSig;
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC0(pObj)) & ISO_MASK];
}
}
else
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig += pIso->FanoutSig;
pIsoF->FanoutSig += pIso->Level * s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIsoF->FanoutSig += pIso->FanoutSig;
pIsoF->FanoutSig += pIso->Level * s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
else if ( Aig_ObjIsCo(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig += pIso->FanoutSig;
pIsoF->FanoutSig += pIso->Level * s_1kPrimes[Abc_Var2Lit(pIso->Level, Aig_ObjFaninC0(pObj)) & ISO_MASK];
}
}
}
// consider flops
Aig_ManForEachLiLoSeq( p->pAig, pObjLi, pObj, i )
{
if ( Aig_ObjFaninId0(pObjLi) == 0 ) // ignore constant!
continue;
pIso = Iso_ManObj( p, Aig_ObjId(pObj) );
pIsoF = Iso_ManObj( p, Aig_ObjFaninId0(pObjLi) );
assert( pIso->FaninSig == 0 );
pIso->FaninSig = pIsoF->FaninSig;
// assert( pIsoF->FanoutSig == 0 );
pIsoF->FanoutSig += pIso->FanoutSig;
}
/*
Aig_ManForEachObj( pAig, pObj, i )
{
pIso = p->pObjs + i;
Aig_ObjPrint( pAig, pObj );
printf( "Lev = %4d. Pos = %4d. FaninSig = %10d. FanoutSig = %10d.\n",
pIso->Level, pIso->nFinNeg, pIso->FaninSig, pIso->FanoutSig );
}
*/
// add to the hash table
Aig_ManForEachObj( pAig, pObj, i )
{
if ( !Aig_ObjIsCi(pObj) && !Aig_ObjIsNode(pObj) )
continue;
pIso = p->pObjs + i;
Iso_ObjHashAdd( p, pIso );
}
// derive classes for the first time
Iso_ManCollectClasses( p );
return p;
}
/**Function*************************************************************
Synopsis [Creates adjacency lists.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManAssignAdjacency( Iso_Man_t * p )
{
int fUseXor = 0;
Iso_Obj_t * pIso, * pIsoF;
Aig_Obj_t * pObj, * pObjLi;
int i;
// create TFI signatures
Aig_ManForEachObj( p->pAig, pObj, i )
{
pIso = p->pObjs + i;
pIso->FaninSig = 0;
pIso->FanoutSig = 0;
if ( Aig_ObjIsCo(pObj) )
continue;
if ( fUseXor )
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIso->FaninSig ^= pIsoF->FaninSig;
if ( pIsoF->Id )
pIso->FaninSig ^= s_1kPrimes[Abc_Var2Lit(pIsoF->Id, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIso->FaninSig ^= pIsoF->FaninSig;
if ( pIsoF->Id )
pIso->FaninSig ^= s_1kPrimes[Abc_Var2Lit(pIsoF->Id, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
}
else
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIso->FaninSig += pIsoF->FaninSig;
if ( pIsoF->Id )
pIso->FaninSig += pIsoF->Id * s_1kPrimes[Abc_Var2Lit(pIsoF->Id, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIso->FaninSig += pIsoF->FaninSig;
if ( pIsoF->Id )
pIso->FaninSig += pIsoF->Id * s_1kPrimes[Abc_Var2Lit(pIsoF->Id, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
}
}
// create TFO signatures
Aig_ManForEachObjReverse( p->pAig, pObj, i )
{
if ( Aig_ObjIsCi(pObj) || Aig_ObjIsConst1(pObj) )
continue;
pIso = p->pObjs + i;
assert( !Aig_ObjIsCo(pObj) || pIso->Id == 0 );
if ( fUseXor )
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig ^= pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIsoF->FanoutSig ^= pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
else if ( Aig_ObjIsCo(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig ^= pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC0(pObj)) & ISO_MASK];
}
}
else
{
if ( Aig_ObjIsNode(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig += pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig += pIso->Id * s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC0(pObj)) & ISO_MASK];
pIsoF = p->pObjs + Aig_ObjFaninId1(pObj);
pIsoF->FanoutSig += pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig += pIso->Id * s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC1(pObj)) & ISO_MASK];
}
else if ( Aig_ObjIsCo(pObj) )
{
pIsoF = p->pObjs + Aig_ObjFaninId0(pObj);
pIsoF->FanoutSig += pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig += pIso->Id * s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC0(pObj)) & ISO_MASK];
}
}
}
// consider flops
Aig_ManForEachLiLoSeq( p->pAig, pObjLi, pObj, i )
{
if ( Aig_ObjFaninId0(pObjLi) == 0 ) // ignore constant!
continue;
pIso = Iso_ManObj( p, Aig_ObjId(pObj) );
pIsoF = Iso_ManObj( p, Aig_ObjFaninId0(pObjLi) );
assert( pIso->FaninSig == 0 );
// assert( pIsoF->FanoutSig == 0 );
if ( fUseXor )
{
pIso->FaninSig = pIsoF->FaninSig;
if ( pIsoF->Id )
pIso->FaninSig ^= s_1kPrimes[Abc_Var2Lit(pIsoF->Id, Aig_ObjFaninC0(pObjLi)) & ISO_MASK];
pIsoF->FanoutSig += pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig ^= s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC0(pObjLi)) & ISO_MASK];
}
else
{
pIso->FaninSig = pIsoF->FaninSig;
if ( pIsoF->Id )
pIso->FaninSig += pIsoF->Id * s_1kPrimes[Abc_Var2Lit(pIsoF->Id, Aig_ObjFaninC0(pObjLi)) & ISO_MASK];
pIsoF->FanoutSig += pIso->FanoutSig;
if ( pIso->Id )
pIsoF->FanoutSig += pIso->Id * s_1kPrimes[Abc_Var2Lit(pIso->Id, Aig_ObjFaninC0(pObjLi)) & ISO_MASK];
}
}
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManPrintClasseSizes( Iso_Man_t * p )
{
Iso_Obj_t * pIso, * pTemp;
int i, Counter;
Vec_PtrForEachEntry( Iso_Obj_t *, p->vClasses, pIso, i )
{
Counter = 0;
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
Counter++;
printf( "%d ", Counter );
}
printf( "\n" );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManPrintClasses( Iso_Man_t * p, int fVerbose, int fVeryVerbose )
{
int fOnlyCis = 0;
Iso_Obj_t * pIso, * pTemp;
int i;
// count unique objects
if ( fVerbose )
printf( "Total objects =%7d. Entries =%7d. Classes =%7d. Singles =%7d.\n",
p->nObjs, p->nEntries, p->nClasses, p->nSingles );
if ( !fVeryVerbose )
return;
printf( "Non-trivial classes:\n" );
Vec_PtrForEachEntry( Iso_Obj_t *, p->vClasses, pIso, i )
{
if ( fOnlyCis && pIso->Level > 0 )
continue;
printf( "%5d : {", i );
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
{
if ( fOnlyCis )
printf( " %d", Aig_ObjCioId( Iso_AigObj(p, pTemp) ) );
else
{
Aig_Obj_t * pObj = Iso_AigObj(p, pTemp);
if ( Aig_ObjIsNode(pObj) )
printf( " %d{%s%d(%d),%s%d(%d)}", Iso_ObjId(p, pTemp),
Aig_ObjFaninC0(pObj)? "-": "+", Aig_ObjFaninId0(pObj), Aig_ObjLevel(Aig_ObjFanin0(pObj)),
Aig_ObjFaninC1(pObj)? "-": "+", Aig_ObjFaninId1(pObj), Aig_ObjLevel(Aig_ObjFanin1(pObj)) );
else
printf( " %d", Iso_ObjId(p, pTemp) );
}
printf( "(%d)", pTemp->Level );
}
printf( " }\n" );
}
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManRehashClassNodes( Iso_Man_t * p )
{
Iso_Obj_t * pIso, * pTemp;
int i;
// collect nodes
Vec_PtrClear( p->vTemp1 );
Vec_PtrClear( p->vTemp2 );
Vec_PtrForEachEntry( Iso_Obj_t *, p->vClasses, pIso, i )
{
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
if ( pTemp->Id == 0 )
Vec_PtrPush( p->vTemp1, pTemp );
else
Vec_PtrPush( p->vTemp2, pTemp );
}
// clean and add nodes
p->nClasses = 0; // total number of classes
p->nEntries = 0; // total number of entries
p->nSingles = 0; // total number of singletons
memset( p->pBins, 0, sizeof(int) * p->nBins );
Vec_PtrForEachEntry( Iso_Obj_t *, p->vTemp1, pTemp, i )
{
assert( pTemp->Id == 0 );
pTemp->iClass = pTemp->iNext = 0;
Iso_ObjHashAdd( p, pTemp );
}
Vec_PtrForEachEntry( Iso_Obj_t *, p->vTemp2, pTemp, i )
{
assert( pTemp->Id != 0 );
pTemp->iClass = pTemp->iNext = 0;
}
// collect new classes
Iso_ManCollectClasses( p );
}
/**Function*************************************************************
Synopsis [Find nodes with the min number of edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Iso_Obj_t * Iso_ManFindBestObj( Iso_Man_t * p, Iso_Obj_t * pIso )
{
Iso_Obj_t * pTemp, * pBest = NULL;
int nNodesBest = -1, nNodes;
int nEdgesBest = -1, nEdges;
assert( pIso->Id == 0 );
if ( pIso->Level == 0 )
return pIso;
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
{
assert( pTemp->Id == 0 );
Iso_ManObjCount( p->pAig, Iso_AigObj(p, pTemp), &nNodes, &nEdges );
// printf( "%d,%d ", nNodes, nEdges );
if ( nNodesBest < nNodes || (nNodesBest == nNodes && nEdgesBest < nEdges) )
{
nNodesBest = nNodes;
nEdgesBest = nEdges;
pBest = pTemp;
}
}
// printf( "\n" );
return pBest;
}
/**Function*************************************************************
Synopsis [Find nodes with the min number of edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManBreakTies( Iso_Man_t * p, int fVerbose )
{
int fUseOneBest = 0;
Iso_Obj_t * pIso, * pTemp;
int i, LevelStart = 0;
pIso = (Iso_Obj_t *)Vec_PtrEntry( p->vClasses, 0 );
LevelStart = pIso->Level;
if ( fVerbose )
printf( "Best level %d\n", LevelStart );
Vec_PtrForEachEntry( Iso_Obj_t *, p->vClasses, pIso, i )
{
if ( (int)pIso->Level < LevelStart )
break;
if ( !fUseOneBest )
{
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
{
assert( pTemp->Id == 0 );
pTemp->Id = p->nObjIds++;
}
continue;
}
if ( pIso->Level == 0 )//&& pIso->nFoutPos + pIso->nFoutNeg == 0 )
{
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
pTemp->Id = p->nObjIds++;
continue;
}
pIso = Iso_ManFindBestObj( p, pIso );
pIso->Id = p->nObjIds++;
}
}
/**Function*************************************************************
Synopsis [Finalizes unification of combinational outputs.]
Description [Assigns IDs to the unclassified CIs in the order of obj IDs.]
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Iso_ManFinalize( Iso_Man_t * p )
{
Vec_Int_t * vRes;
Aig_Obj_t * pObj;
int i;
assert( p->nClasses == 0 );
assert( Vec_PtrSize(p->vClasses) == 0 );
// set canonical numbers
Aig_ManForEachObj( p->pAig, pObj, i )
{
if ( !Aig_ObjIsCi(pObj) && !Aig_ObjIsNode(pObj) )
{
pObj->iData = -1;
continue;
}
pObj->iData = Iso_ManObj(p, Aig_ObjId(pObj))->Id;
assert( pObj->iData > 0 );
}
Aig_ManConst1(p->pAig)->iData = 0;
// assign unique IDs to the CIs
Vec_PtrClear( p->vTemp1 );
Vec_PtrClear( p->vTemp2 );
Aig_ManForEachCi( p->pAig, pObj, i )
{
assert( pObj->iData > 0 );
if ( Aig_ObjCioId(pObj) >= Aig_ManCiNum(p->pAig) - Aig_ManRegNum(p->pAig) ) // flop
Vec_PtrPush( p->vTemp2, pObj );
else // PI
Vec_PtrPush( p->vTemp1, pObj );
}
// sort CIs by their IDs
Vec_PtrSort( p->vTemp1, (int (*)(void))Iso_ObjCompareByData );
Vec_PtrSort( p->vTemp2, (int (*)(void))Iso_ObjCompareByData );
// create the result
vRes = Vec_IntAlloc( Aig_ManCiNum(p->pAig) );
Vec_PtrForEachEntry( Aig_Obj_t *, p->vTemp1, pObj, i )
Vec_IntPush( vRes, Aig_ObjCioId(pObj) );
Vec_PtrForEachEntry( Aig_Obj_t *, p->vTemp2, pObj, i )
Vec_IntPush( vRes, Aig_ObjCioId(pObj) );
return vRes;
}
/**Function*************************************************************
Synopsis [Find nodes with the min number of edges.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Iso_ManDumpOneClass( Iso_Man_t * p )
{
Vec_Ptr_t * vNodes = Vec_PtrAlloc( 100 );
Iso_Obj_t * pIso, * pTemp;
Aig_Man_t * pNew = NULL;
assert( p->nClasses > 0 );
pIso = (Iso_Obj_t *)Vec_PtrEntry( p->vClasses, 0 );
assert( pIso->Id == 0 );
for ( pTemp = pIso; pTemp; pTemp = Iso_ManObj(p, pTemp->iClass) )
{
assert( pTemp->Id == 0 );
Vec_PtrPush( vNodes, Iso_AigObj(p, pTemp) );
}
pNew = Aig_ManDupNodes( p->pAig, vNodes );
Vec_PtrFree( vNodes );
Aig_ManShow( pNew, 0, NULL );
Aig_ManStopP( &pNew );
}
/**Function*************************************************************
Synopsis [Finds canonical permutation of CIs and assigns unique IDs.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Vec_Int_t * Saig_ManFindIsoPerm( Aig_Man_t * pAig, int fVerbose )
{
int fVeryVerbose = 0;
Vec_Int_t * vRes;
Iso_Man_t * p;
abctime clk = Abc_Clock(), clk2 = Abc_Clock();
p = Iso_ManCreate( pAig );
p->timeFout += Abc_Clock() - clk;
Iso_ManPrintClasses( p, fVerbose, fVeryVerbose );
while ( p->nClasses )
{
// assign adjacency to classes
clk = Abc_Clock();
Iso_ManAssignAdjacency( p );
p->timeFout += Abc_Clock() - clk;
// rehash the class nodes
clk = Abc_Clock();
Iso_ManRehashClassNodes( p );
p->timeHash += Abc_Clock() - clk;
Iso_ManPrintClasses( p, fVerbose, fVeryVerbose );
// force refinement
while ( p->nSingles == 0 && p->nClasses )
{
// Iso_ManPrintClasseSizes( p );
// assign IDs to the topmost level of classes
Iso_ManBreakTies( p, fVerbose );
// assign adjacency to classes
clk = Abc_Clock();
Iso_ManAssignAdjacency( p );
p->timeFout += Abc_Clock() - clk;
// rehash the class nodes
clk = Abc_Clock();
Iso_ManRehashClassNodes( p );
p->timeHash += Abc_Clock() - clk;
Iso_ManPrintClasses( p, fVerbose, fVeryVerbose );
}
}
p->timeTotal = Abc_Clock() - clk2;
// printf( "IDs assigned = %d. Objects = %d.\n", p->nObjIds, 1+Aig_ManCiNum(p->pAig)+Aig_ManNodeNum(p->pAig) );
assert( p->nObjIds == 1+Aig_ManCiNum(p->pAig)+Aig_ManNodeNum(p->pAig) );
// if ( p->nClasses )
// Iso_ManDumpOneClass( p );
vRes = Iso_ManFinalize( p );
Iso_ManStop( p, fVerbose );
return vRes;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END