1 /**CFile****************************************************************
2
3 FileName [acecMult.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [CEC for arithmetic circuits.]
8
9 Synopsis [Multiplier.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: acecMult.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "acecInt.h"
22 #include "misc/extra/extra.h"
23 #include "misc/util/utilTruth.h"
24
25 ABC_NAMESPACE_IMPL_START
26
27
28 ////////////////////////////////////////////////////////////////////////
29 /// DECLARATIONS ///
30 ////////////////////////////////////////////////////////////////////////
31
32 unsigned s_Classes4a[96] = {
33 0xD728, 0xB748, 0x9F60, 0xD278, 0xB478, 0x96F0, 0xC66C, 0x96CC, 0x9C6C, 0x96AA, 0xA66A, 0x9A6A,
34 0x28D7, 0x48B7, 0x609F, 0x2D87, 0x4B87, 0x690F, 0x3993, 0x6933, 0x6393, 0x6955, 0x5995, 0x6595,
35 0xEB14, 0xED12, 0xF906, 0xE1B4, 0xE1D2, 0xF096, 0xC99C, 0xCC96, 0xC9C6, 0xAA96, 0xA99A, 0xA9A6,
36 0x14EB, 0x12ED, 0x06F9, 0x1E4B, 0x1E2D, 0x0F69, 0x3663, 0x3369, 0x3639, 0x5569, 0x5665, 0x5659,
37 0x7D82, 0x7B84, 0x6F90, 0x78D2, 0x78B4, 0x69F0, 0x6CC6, 0x69CC, 0x6C9C, 0x69AA, 0x6AA6, 0x6A9A,
38 0x827D, 0x847B, 0x906F, 0x872D, 0x874B, 0x960F, 0x9339, 0x9633, 0x9363, 0x9655, 0x9559, 0x9565,
39 0xBE41, 0xDE21, 0xF609, 0xB4E1, 0xD2E1, 0xF069, 0x9CC9, 0xCC69, 0xC6C9, 0xAA69, 0x9AA9, 0xA6A9,
40 0x41BE, 0x21DE, 0x09F6, 0x4B1E, 0x2D1E, 0x0F96, 0x6336, 0x3396, 0x3936, 0x5596, 0x6556, 0x5956
41 };
42
43 unsigned s_Classes4b[384] = {
44 0x35C0, 0x53A0, 0x1DC0, 0x4788, 0x2788, 0x1BA0, 0x3C50, 0x5A30, 0x1CD0, 0x4878, 0x2878, 0x1AB0,
45 0x34C4, 0x606C, 0x3C44, 0x660C, 0x268C, 0x286C, 0x606A, 0x52A2, 0x486A, 0x468A, 0x660A, 0x5A22,
46 0x3AC0, 0x5CA0, 0x2EC0, 0x7488, 0x7288, 0x4EA0, 0x3CA0, 0x5AC0, 0x2CE0, 0x7848, 0x7828, 0x4AE0,
47 0x38C8, 0x6C60, 0x3C88, 0x66C0, 0x62C8, 0x6C28, 0x6A60, 0x58A8, 0x6A48, 0x64A8, 0x66A0, 0x5A88,
48 0xC530, 0xA350, 0xD10C, 0x8B44, 0x8D22, 0xB10A, 0xC350, 0xA530, 0xD01C, 0x84B4, 0x82D2, 0xB01A,
49 0xC434, 0x909C, 0xC344, 0x990C, 0x8C26, 0x82C6, 0x909A, 0xA252, 0x84A6, 0x8A46, 0x990A, 0xA522,
50 0xCA30, 0xAC50, 0xE20C, 0xB844, 0xD822, 0xE40A, 0xC3A0, 0xA5C0, 0xE02C, 0xB484, 0xD282, 0xE04A,
51 0xC838, 0x9C90, 0xC388, 0x99C0, 0xC862, 0xC682, 0x9A90, 0xA858, 0xA684, 0xA864, 0x99A0, 0xA588,
52 0x530C, 0x350A, 0x4730, 0x1D22, 0x1B44, 0x2750, 0x503C, 0x305A, 0x4370, 0x12D2, 0x14B4, 0x2570,
53 0x434C, 0x06C6, 0x443C, 0x0C66, 0x194C, 0x149C, 0x06A6, 0x252A, 0x129A, 0x192A, 0x0A66, 0x225A,
54 0xA30C, 0xC50A, 0x8B30, 0xD122, 0xB144, 0x8D50, 0xA03C, 0xC05A, 0x83B0, 0xD212, 0xB414, 0x85D0,
55 0x838C, 0xC606, 0x883C, 0xC066, 0x91C4, 0x9C14, 0xA606, 0x858A, 0x9A12, 0x91A2, 0xA066, 0x885A,
56 0x5C03, 0x3A05, 0x7403, 0x2E11, 0x4E11, 0x7205, 0x50C3, 0x30A5, 0x7043, 0x21E1, 0x41E1, 0x7025,
57 0x4C43, 0x09C9, 0x44C3, 0x0C99, 0x4C19, 0x41C9, 0x09A9, 0x2A25, 0x21A9, 0x2A19, 0x0A99, 0x22A5,
58 0xAC03, 0xCA05, 0xB803, 0xE211, 0xE411, 0xD805, 0xA0C3, 0xC0A5, 0xB083, 0xE121, 0xE141, 0xD085,
59 0x8C83, 0xC909, 0x88C3, 0xC099, 0xC491, 0xC941, 0xA909, 0x8A85, 0xA921, 0xA291, 0xA099, 0x88A5,
60 0xC035, 0xA053, 0xC01D, 0x8847, 0x8827, 0xA01B, 0xC305, 0xA503, 0xC10D, 0x8487, 0x8287, 0xA10B,
61 0xC131, 0x9093, 0xC311, 0x9903, 0x8923, 0x8293, 0x9095, 0xA151, 0x8495, 0x8945, 0x9905, 0xA511,
62 0xC03A, 0xA05C, 0xC02E, 0x8874, 0x8872, 0xA04E, 0xC30A, 0xA50C, 0xC20E, 0x8784, 0x8782, 0xA40E,
63 0xC232, 0x9390, 0xC322, 0x9930, 0x9832, 0x9382, 0x9590, 0xA454, 0x9584, 0x9854, 0x9950, 0xA544,
64 0x30C5, 0x50A3, 0x0CD1, 0x448B, 0x228D, 0x0AB1, 0x3C05, 0x5A03, 0x0DC1, 0x484B, 0x282D, 0x0BA1,
65 0x31C1, 0x6063, 0x3C11, 0x6603, 0x2389, 0x2839, 0x6065, 0x51A1, 0x4859, 0x4589, 0x6605, 0x5A11,
66 0x30CA, 0x50AC, 0x0CE2, 0x44B8, 0x22D8, 0x0AE4, 0x3C0A, 0x5A0C, 0x0EC2, 0x4B48, 0x2D28, 0x0EA4,
67 0x32C2, 0x6360, 0x3C22, 0x6630, 0x3298, 0x3928, 0x6560, 0x54A4, 0x5948, 0x5498, 0x6650, 0x5A44,
68 0x0C53, 0x0A35, 0x3047, 0x221D, 0x441B, 0x5027, 0x05C3, 0x03A5, 0x3407, 0x212D, 0x414B, 0x5207,
69 0x1C13, 0x0939, 0x11C3, 0x0399, 0x4613, 0x4163, 0x0959, 0x1A15, 0x2165, 0x2615, 0x0599, 0x11A5,
70 0x0CA3, 0x0AC5, 0x308B, 0x22D1, 0x44B1, 0x508D, 0x0AC3, 0x0CA5, 0x380B, 0x2D21, 0x4B41, 0x580D,
71 0x2C23, 0x3909, 0x22C3, 0x3099, 0x6431, 0x6341, 0x5909, 0x4A45, 0x6521, 0x6251, 0x5099, 0x44A5,
72 0x035C, 0x053A, 0x0374, 0x112E, 0x114E, 0x0572, 0x053C, 0x035A, 0x0734, 0x121E, 0x141E, 0x0752,
73 0x131C, 0x0636, 0x113C, 0x0366, 0x1346, 0x1436, 0x0656, 0x151A, 0x1256, 0x1526, 0x0566, 0x115A,
74 0x03AC, 0x05CA, 0x03B8, 0x11E2, 0x11E4, 0x05D8, 0x0A3C, 0x0C5A, 0x0B38, 0x1E12, 0x1E14, 0x0D58,
75 0x232C, 0x3606, 0x223C, 0x3066, 0x3164, 0x3614, 0x5606, 0x454A, 0x5612, 0x5162, 0x5066, 0x445A
76 };
77
78 unsigned s_Classes4c[768] = {
79 0x35C0, 0x53A0, 0x1DC0, 0x4788, 0x2788, 0x1BA0, 0x3C50, 0x5A30, 0x1CD0, 0x4878, 0x2878, 0x1AB0,
80 0x34C4, 0x606C, 0x3C44, 0x660C, 0x268C, 0x286C, 0x606A, 0x52A2, 0x486A, 0x468A, 0x660A, 0x5A22,
81 0xCA3F, 0xAC5F, 0xE23F, 0xB877, 0xD877, 0xE45F, 0xC3AF, 0xA5CF, 0xE32F, 0xB787, 0xD787, 0xE54F,
82 0xCB3B, 0x9F93, 0xC3BB, 0x99F3, 0xD973, 0xD793, 0x9F95, 0xAD5D, 0xB795, 0xB975, 0x99F5, 0xA5DD,
83 0x3AC0, 0x5CA0, 0x2EC0, 0x7488, 0x7288, 0x4EA0, 0x3CA0, 0x5AC0, 0x2CE0, 0x7848, 0x7828, 0x4AE0,
84 0x38C8, 0x6C60, 0x3C88, 0x66C0, 0x62C8, 0x6C28, 0x6A60, 0x58A8, 0x6A48, 0x64A8, 0x66A0, 0x5A88,
85 0xC53F, 0xA35F, 0xD13F, 0x8B77, 0x8D77, 0xB15F, 0xC35F, 0xA53F, 0xD31F, 0x87B7, 0x87D7, 0xB51F,
86 0xC737, 0x939F, 0xC377, 0x993F, 0x9D37, 0x93D7, 0x959F, 0xA757, 0x95B7, 0x9B57, 0x995F, 0xA577,
87 0xC530, 0xA350, 0xD10C, 0x8B44, 0x8D22, 0xB10A, 0xC350, 0xA530, 0xD01C, 0x84B4, 0x82D2, 0xB01A,
88 0xC434, 0x909C, 0xC344, 0x990C, 0x8C26, 0x82C6, 0x909A, 0xA252, 0x84A6, 0x8A46, 0x990A, 0xA522,
89 0x3ACF, 0x5CAF, 0x2EF3, 0x74BB, 0x72DD, 0x4EF5, 0x3CAF, 0x5ACF, 0x2FE3, 0x7B4B, 0x7D2D, 0x4FE5,
90 0x3BCB, 0x6F63, 0x3CBB, 0x66F3, 0x73D9, 0x7D39, 0x6F65, 0x5DAD, 0x7B59, 0x75B9, 0x66F5, 0x5ADD,
91 0xCA30, 0xAC50, 0xE20C, 0xB844, 0xD822, 0xE40A, 0xC3A0, 0xA5C0, 0xE02C, 0xB484, 0xD282, 0xE04A,
92 0xC838, 0x9C90, 0xC388, 0x99C0, 0xC862, 0xC682, 0x9A90, 0xA858, 0xA684, 0xA864, 0x99A0, 0xA588,
93 0x35CF, 0x53AF, 0x1DF3, 0x47BB, 0x27DD, 0x1BF5, 0x3C5F, 0x5A3F, 0x1FD3, 0x4B7B, 0x2D7D, 0x1FB5,
94 0x37C7, 0x636F, 0x3C77, 0x663F, 0x379D, 0x397D, 0x656F, 0x57A7, 0x597B, 0x579B, 0x665F, 0x5A77,
95 0x530C, 0x350A, 0x4730, 0x1D22, 0x1B44, 0x2750, 0x503C, 0x305A, 0x4370, 0x12D2, 0x14B4, 0x2570,
96 0x434C, 0x06C6, 0x443C, 0x0C66, 0x194C, 0x149C, 0x06A6, 0x252A, 0x129A, 0x192A, 0x0A66, 0x225A,
97 0xACF3, 0xCAF5, 0xB8CF, 0xE2DD, 0xE4BB, 0xD8AF, 0xAFC3, 0xCFA5, 0xBC8F, 0xED2D, 0xEB4B, 0xDA8F,
98 0xBCB3, 0xF939, 0xBBC3, 0xF399, 0xE6B3, 0xEB63, 0xF959, 0xDAD5, 0xED65, 0xE6D5, 0xF599, 0xDDA5,
99 0xA30C, 0xC50A, 0x8B30, 0xD122, 0xB144, 0x8D50, 0xA03C, 0xC05A, 0x83B0, 0xD212, 0xB414, 0x85D0,
100 0x838C, 0xC606, 0x883C, 0xC066, 0x91C4, 0x9C14, 0xA606, 0x858A, 0x9A12, 0x91A2, 0xA066, 0x885A,
101 0x5CF3, 0x3AF5, 0x74CF, 0x2EDD, 0x4EBB, 0x72AF, 0x5FC3, 0x3FA5, 0x7C4F, 0x2DED, 0x4BEB, 0x7A2F,
102 0x7C73, 0x39F9, 0x77C3, 0x3F99, 0x6E3B, 0x63EB, 0x59F9, 0x7A75, 0x65ED, 0x6E5D, 0x5F99, 0x77A5,
103 0x5C03, 0x3A05, 0x7403, 0x2E11, 0x4E11, 0x7205, 0x50C3, 0x30A5, 0x7043, 0x21E1, 0x41E1, 0x7025,
104 0x4C43, 0x09C9, 0x44C3, 0x0C99, 0x4C19, 0x41C9, 0x09A9, 0x2A25, 0x21A9, 0x2A19, 0x0A99, 0x22A5,
105 0xA3FC, 0xC5FA, 0x8BFC, 0xD1EE, 0xB1EE, 0x8DFA, 0xAF3C, 0xCF5A, 0x8FBC, 0xDE1E, 0xBE1E, 0x8FDA,
106 0xB3BC, 0xF636, 0xBB3C, 0xF366, 0xB3E6, 0xBE36, 0xF656, 0xD5DA, 0xDE56, 0xD5E6, 0xF566, 0xDD5A,
107 0xAC03, 0xCA05, 0xB803, 0xE211, 0xE411, 0xD805, 0xA0C3, 0xC0A5, 0xB083, 0xE121, 0xE141, 0xD085,
108 0x8C83, 0xC909, 0x88C3, 0xC099, 0xC491, 0xC941, 0xA909, 0x8A85, 0xA921, 0xA291, 0xA099, 0x88A5,
109 0x53FC, 0x35FA, 0x47FC, 0x1DEE, 0x1BEE, 0x27FA, 0x5F3C, 0x3F5A, 0x4F7C, 0x1EDE, 0x1EBE, 0x2F7A,
110 0x737C, 0x36F6, 0x773C, 0x3F66, 0x3B6E, 0x36BE, 0x56F6, 0x757A, 0x56DE, 0x5D6E, 0x5F66, 0x775A,
111 0xC035, 0xA053, 0xC01D, 0x8847, 0x8827, 0xA01B, 0xC305, 0xA503, 0xC10D, 0x8487, 0x8287, 0xA10B,
112 0xC131, 0x9093, 0xC311, 0x9903, 0x8923, 0x8293, 0x9095, 0xA151, 0x8495, 0x8945, 0x9905, 0xA511,
113 0x3FCA, 0x5FAC, 0x3FE2, 0x77B8, 0x77D8, 0x5FE4, 0x3CFA, 0x5AFC, 0x3EF2, 0x7B78, 0x7D78, 0x5EF4,
114 0x3ECE, 0x6F6C, 0x3CEE, 0x66FC, 0x76DC, 0x7D6C, 0x6F6A, 0x5EAE, 0x7B6A, 0x76BA, 0x66FA, 0x5AEE,
115 0xC03A, 0xA05C, 0xC02E, 0x8874, 0x8872, 0xA04E, 0xC30A, 0xA50C, 0xC20E, 0x8784, 0x8782, 0xA40E,
116 0xC232, 0x9390, 0xC322, 0x9930, 0x9832, 0x9382, 0x9590, 0xA454, 0x9584, 0x9854, 0x9950, 0xA544,
117 0x3FC5, 0x5FA3, 0x3FD1, 0x778B, 0x778D, 0x5FB1, 0x3CF5, 0x5AF3, 0x3DF1, 0x787B, 0x787D, 0x5BF1,
118 0x3DCD, 0x6C6F, 0x3CDD, 0x66CF, 0x67CD, 0x6C7D, 0x6A6F, 0x5BAB, 0x6A7B, 0x67AB, 0x66AF, 0x5ABB,
119 0x30C5, 0x50A3, 0x0CD1, 0x448B, 0x228D, 0x0AB1, 0x3C05, 0x5A03, 0x0DC1, 0x484B, 0x282D, 0x0BA1,
120 0x31C1, 0x6063, 0x3C11, 0x6603, 0x2389, 0x2839, 0x6065, 0x51A1, 0x4859, 0x4589, 0x6605, 0x5A11,
121 0xCF3A, 0xAF5C, 0xF32E, 0xBB74, 0xDD72, 0xF54E, 0xC3FA, 0xA5FC, 0xF23E, 0xB7B4, 0xD7D2, 0xF45E,
122 0xCE3E, 0x9F9C, 0xC3EE, 0x99FC, 0xDC76, 0xD7C6, 0x9F9A, 0xAE5E, 0xB7A6, 0xBA76, 0x99FA, 0xA5EE,
123 0x30CA, 0x50AC, 0x0CE2, 0x44B8, 0x22D8, 0x0AE4, 0x3C0A, 0x5A0C, 0x0EC2, 0x4B48, 0x2D28, 0x0EA4,
124 0x32C2, 0x6360, 0x3C22, 0x6630, 0x3298, 0x3928, 0x6560, 0x54A4, 0x5948, 0x5498, 0x6650, 0x5A44,
125 0xCF35, 0xAF53, 0xF31D, 0xBB47, 0xDD27, 0xF51B, 0xC3F5, 0xA5F3, 0xF13D, 0xB4B7, 0xD2D7, 0xF15B,
126 0xCD3D, 0x9C9F, 0xC3DD, 0x99CF, 0xCD67, 0xC6D7, 0x9A9F, 0xAB5B, 0xA6B7, 0xAB67, 0x99AF, 0xA5BB,
127 0x0C53, 0x0A35, 0x3047, 0x221D, 0x441B, 0x5027, 0x05C3, 0x03A5, 0x3407, 0x212D, 0x414B, 0x5207,
128 0x1C13, 0x0939, 0x11C3, 0x0399, 0x4613, 0x4163, 0x0959, 0x1A15, 0x2165, 0x2615, 0x0599, 0x11A5,
129 0xF3AC, 0xF5CA, 0xCFB8, 0xDDE2, 0xBBE4, 0xAFD8, 0xFA3C, 0xFC5A, 0xCBF8, 0xDED2, 0xBEB4, 0xADF8,
130 0xE3EC, 0xF6C6, 0xEE3C, 0xFC66, 0xB9EC, 0xBE9C, 0xF6A6, 0xE5EA, 0xDE9A, 0xD9EA, 0xFA66, 0xEE5A,
131 0x0CA3, 0x0AC5, 0x308B, 0x22D1, 0x44B1, 0x508D, 0x0AC3, 0x0CA5, 0x380B, 0x2D21, 0x4B41, 0x580D,
132 0x2C23, 0x3909, 0x22C3, 0x3099, 0x6431, 0x6341, 0x5909, 0x4A45, 0x6521, 0x6251, 0x5099, 0x44A5,
133 0xF35C, 0xF53A, 0xCF74, 0xDD2E, 0xBB4E, 0xAF72, 0xF53C, 0xF35A, 0xC7F4, 0xD2DE, 0xB4BE, 0xA7F2,
134 0xD3DC, 0xC6F6, 0xDD3C, 0xCF66, 0x9BCE, 0x9CBE, 0xA6F6, 0xB5BA, 0x9ADE, 0x9DAE, 0xAF66, 0xBB5A,
135 0x035C, 0x053A, 0x0374, 0x112E, 0x114E, 0x0572, 0x053C, 0x035A, 0x0734, 0x121E, 0x141E, 0x0752,
136 0x131C, 0x0636, 0x113C, 0x0366, 0x1346, 0x1436, 0x0656, 0x151A, 0x1256, 0x1526, 0x0566, 0x115A,
137 0xFCA3, 0xFAC5, 0xFC8B, 0xEED1, 0xEEB1, 0xFA8D, 0xFAC3, 0xFCA5, 0xF8CB, 0xEDE1, 0xEBE1, 0xF8AD,
138 0xECE3, 0xF9C9, 0xEEC3, 0xFC99, 0xECB9, 0xEBC9, 0xF9A9, 0xEAE5, 0xEDA9, 0xEAD9, 0xFA99, 0xEEA5,
139 0x03AC, 0x05CA, 0x03B8, 0x11E2, 0x11E4, 0x05D8, 0x0A3C, 0x0C5A, 0x0B38, 0x1E12, 0x1E14, 0x0D58,
140 0x232C, 0x3606, 0x223C, 0x3066, 0x3164, 0x3614, 0x5606, 0x454A, 0x5612, 0x5162, 0x5066, 0x445A,
141 0xFC53, 0xFA35, 0xFC47, 0xEE1D, 0xEE1B, 0xFA27, 0xF5C3, 0xF3A5, 0xF4C7, 0xE1ED, 0xE1EB, 0xF2A7,
142 0xDCD3, 0xC9F9, 0xDDC3, 0xCF99, 0xCE9B, 0xC9EB, 0xA9F9, 0xBAB5, 0xA9ED, 0xAE9D, 0xAF99, 0xBBA5
143 };
144
145 ////////////////////////////////////////////////////////////////////////
146 /// FUNCTION DEFINITIONS ///
147 ////////////////////////////////////////////////////////////////////////
148
149
150 /**Function*************************************************************
151
152 Synopsis [Computes NPN-canonical form using brute-force methods.]
153
154 Description []
155
156 SideEffects []
157
158 SeeAlso []
159
160 ***********************************************************************/
Extra_TruthCanonNPN3(word uTruth,int nVars,Vec_Wrd_t * vRes)161 word Extra_TruthCanonNPN3( word uTruth, int nVars, Vec_Wrd_t * vRes )
162 {
163 int nMints = (1 << nVars);
164 int nPerms = Extra_Factorial( nVars );
165 int * pComp = Extra_GreyCodeSchedule( nVars );
166 int * pPerm = Extra_PermSchedule( nVars );
167 word tCur, tTemp1, tTemp2;
168 word uTruthMin = ABC_CONST(0xFFFFFFFFFFFFFFFF);
169 int i, p, c;
170 Vec_WrdClear( vRes );
171 for ( i = 0; i < 2; i++ )
172 {
173 tCur = i ? ~uTruth : uTruth;
174 tTemp1 = tCur;
175 for ( p = 0; p < nPerms; p++ )
176 {
177 tTemp2 = tCur;
178 for ( c = 0; c < nMints; c++ )
179 {
180 if ( uTruthMin > tCur )
181 uTruthMin = tCur;
182 Vec_WrdPushUnique( vRes, tCur );
183 tCur = Abc_Tt6Flip( tCur, pComp[c] );
184 }
185 assert( tTemp2 == tCur );
186 tCur = Abc_Tt6SwapAdjacent( tCur, pPerm[p] );
187 }
188 assert( tTemp1 == tCur );
189 }
190 ABC_FREE( pComp );
191 ABC_FREE( pPerm );
192 return uTruthMin;
193 }
Acec_MultFuncTest6()194 void Acec_MultFuncTest6()
195 {
196 Vec_Wrd_t * vRes = Vec_WrdAlloc( 10000 );
197 int i; word Entry;
198
199 word Truth = ABC_CONST(0xfedcba9876543210);
200 word Canon = Extra_TruthCanonNPN3( Truth, 6, vRes );
201
202 Extra_PrintHex( stdout, (unsigned*)&Truth, 6 ); printf( "\n" );
203 Extra_PrintHex( stdout, (unsigned*)&Canon, 6 ); printf( "\n" );
204
205 printf( "Members = %d.\n", Vec_WrdSize(vRes) );
206 Vec_WrdForEachEntry( vRes, Entry, i )
207 {
208 Extra_PrintHex( stdout, (unsigned*)&Entry, 6 );
209 printf( ", " );
210 if ( i % 8 == 7 )
211 printf( "\n" );
212 }
213
214 Vec_WrdFree( vRes );
215 }
216
Extra_TruthCanonNPN2(unsigned uTruth,int nVars,Vec_Int_t * vRes)217 unsigned Extra_TruthCanonNPN2( unsigned uTruth, int nVars, Vec_Int_t * vRes )
218 {
219 static int nVarsOld, nPerms;
220 static char ** pPerms = NULL;
221
222 unsigned uTruthMin, uTruthC, uPhase, uPerm;
223 int nMints, k, i;
224
225 if ( pPerms == NULL )
226 {
227 nPerms = Extra_Factorial( nVars );
228 pPerms = Extra_Permutations( nVars );
229 nVarsOld = nVars;
230 }
231 else if ( nVarsOld != nVars )
232 {
233 ABC_FREE( pPerms );
234 nPerms = Extra_Factorial( nVars );
235 pPerms = Extra_Permutations( nVars );
236 nVarsOld = nVars;
237 }
238
239 nMints = (1 << nVars);
240 uTruthC = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) );
241 uTruthMin = 0xFFFFFFFF;
242 for ( i = 0; i < nMints; i++ )
243 {
244 uPhase = Extra_TruthPolarize( uTruth, i, nVars );
245 for ( k = 0; k < nPerms; k++ )
246 {
247 uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
248 if ( !(uPerm & 1) )
249 Vec_IntPushUnique( vRes, uPerm );
250 if ( uTruthMin > uPerm )
251 uTruthMin = uPerm;
252 }
253 uPhase = Extra_TruthPolarize( uTruthC, i, nVars );
254 for ( k = 0; k < nPerms; k++ )
255 {
256 uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
257 if ( !(uPerm & 1) )
258 Vec_IntPushUnique( vRes, uPerm );
259 if ( uTruthMin > uPerm )
260 uTruthMin = uPerm;
261 }
262 }
263 return uTruthMin;
264 }
265
Acec_MultFuncTest5()266 void Acec_MultFuncTest5()
267 {
268 Vec_Int_t * vRes = Vec_IntAlloc( 1000 );
269 int i, Entry;
270
271 unsigned Truth = 0xF335ACC0;
272 unsigned Canon = Extra_TruthCanonNPN2( Truth, 5, vRes );
273
274 Extra_PrintHex( stdout, (unsigned*)&Truth, 5 ); printf( "\n" );
275 Extra_PrintHex( stdout, (unsigned*)&Canon, 5 ); printf( "\n" );
276
277 printf( "Members = %d.\n", Vec_IntSize(vRes) );
278 Vec_IntForEachEntry( vRes, Entry, i )
279 {
280 Extra_PrintHex( stdout, (unsigned*)&Entry, 5 );
281 printf( ", " );
282 if ( i % 8 == 7 )
283 printf( "\n" );
284 }
285
286 Vec_IntFree( vRes );
287 }
288
Acec_MultFuncTest4()289 void Acec_MultFuncTest4()
290 {
291 Vec_Int_t * vRes = Vec_IntAlloc( 1000 );
292 int i, Entry;
293
294 unsigned Truth = 0xF3C0;
295 // unsigned Truth = 0xF335;
296 // unsigned Truth = 0xFD80;
297 //unsigned Truth = 0xD728;
298 //unsigned Truth = 0x35C0;
299 //unsigned Truth = 0xACC0;
300 unsigned Canon = Extra_TruthCanonNPN2( Truth, 4, vRes );
301
302 Extra_PrintHex( stdout, (unsigned*)&Truth, 4 ); printf( "\n" );
303 Extra_PrintHex( stdout, (unsigned*)&Canon, 4 ); printf( "\n" );
304
305 printf( "Members = %d.\n", Vec_IntSize(vRes) );
306 Vec_IntForEachEntry( vRes, Entry, i )
307 {
308 Extra_PrintHex( stdout, (unsigned*)&Entry, 4 );
309 printf( ", " );
310 if ( i % 12 == 11 )
311 printf( "\n" );
312 }
313
314 Vec_IntFree( vRes );
315 }
316
317
318 /**Function*************************************************************
319
320 Synopsis []
321
322 Description []
323
324 SideEffects []
325
326 SeeAlso []
327
328 ***********************************************************************/
Acec_MultCollectInputs(Vec_Int_t * vPairs,Vec_Int_t * vRanks,int iObj)329 Vec_Int_t * Acec_MultCollectInputs( Vec_Int_t * vPairs, Vec_Int_t * vRanks, int iObj )
330 {
331 Vec_Int_t * vItems = Vec_IntAlloc( 100 );
332 int k, iObj1, iObj2;
333 // collect all those appearing with this one
334 Vec_IntForEachEntryDouble( vPairs, iObj1, iObj2, k )
335 if ( iObj == iObj1 )
336 Vec_IntPushUnique( vItems, iObj2 );
337 else if ( iObj == iObj2 )
338 Vec_IntPushUnique( vItems, iObj1 );
339 // sort items by rank cost
340 Vec_IntSelectSortCost( Vec_IntArray(vItems), Vec_IntSize(vItems), vRanks );
341 return vItems;
342 }
Acec_MultDetectInputs1(Gia_Man_t * p,Vec_Wec_t * vLeafLits,Vec_Wec_t * vRootLits)343 Vec_Int_t * Acec_MultDetectInputs1( Gia_Man_t * p, Vec_Wec_t * vLeafLits, Vec_Wec_t * vRootLits )
344 {
345 Vec_Int_t * vInputs = Vec_IntAlloc( 100 );
346 Vec_Int_t * vCounts = Vec_IntStart( Gia_ManObjNum(p) );
347 Vec_Int_t * vRanks = Vec_IntStart( Gia_ManObjNum(p) );
348 Vec_Int_t * vPairs = Vec_IntAlloc( 100 );
349 Vec_Int_t * vItems = Vec_IntAlloc( 100 );
350 Vec_Int_t * vItems0;
351 Vec_Int_t * vItems1;
352 Vec_Int_t * vLevel;
353 int i, k, iLit, iObj, Count;
354 // count how many times each input appears
355 Vec_WecForEachLevel( vLeafLits, vLevel, i )
356 Vec_IntForEachEntry( vLevel, iLit, k )
357 {
358 iObj = Abc_Lit2Var(iLit);
359 Vec_IntAddToEntry( vCounts, Gia_ObjFaninId0(Gia_ManObj(p, iObj), iObj), 1 );
360 Vec_IntAddToEntry( vCounts, Gia_ObjFaninId1(Gia_ManObj(p, iObj), iObj), 1 );
361 /*
362 printf( "Rank %2d : Leaf = %4d : (%2d, %2d)\n", i, iObj,
363 Gia_ObjFaninId0(Gia_ManObj(p, iObj), iObj), Gia_ObjFaninId1(Gia_ManObj(p, iObj), iObj) );
364 if ( k == Vec_IntSize(vLevel) - 1 )
365 printf( "\n" );
366 */
367 }
368 // count ranks for each one
369 Vec_WecForEachLevel( vLeafLits, vLevel, i )
370 Vec_IntForEachEntry( vLevel, iLit, k )
371 {
372 iObj = Abc_Lit2Var(iLit);
373 if ( Vec_IntEntry(vCounts, Gia_ObjFaninId0(Gia_ManObj(p, iObj), iObj)) < 2 )
374 {
375 printf( "Skipping %d.\n", iObj );
376 continue;
377 }
378 if ( Vec_IntEntry(vCounts, Gia_ObjFaninId1(Gia_ManObj(p, iObj), iObj)) < 2 )
379 {
380 printf( "Skipping %d.\n", iObj );
381 continue;
382 }
383 Vec_IntAddToEntry( vRanks, Gia_ObjFaninId0(Gia_ManObj(p, iObj), iObj), i );
384 Vec_IntAddToEntry( vRanks, Gia_ObjFaninId1(Gia_ManObj(p, iObj), iObj), i );
385
386 Vec_IntPushTwo( vPairs, Gia_ObjFaninId0(Gia_ManObj(p, iObj), iObj), Gia_ObjFaninId1(Gia_ManObj(p, iObj), iObj) );
387 }
388
389 // print statistics
390 Vec_IntForEachEntry( vCounts, Count, i )
391 {
392 if ( !Count )
393 continue;
394 if ( !Vec_IntEntry(vRanks, i) )
395 continue;
396 Vec_IntPush( vItems, i );
397 printf( "Obj = %3d Occurs = %3d Ranks = %3d\n", i, Count, Vec_IntEntry(vRanks, i) );
398 }
399 // sort items by rank cost
400 Vec_IntSelectSortCost( Vec_IntArray(vItems), Vec_IntSize(vItems), vRanks );
401 // collect all those appearing with the last one
402 vItems0 = Acec_MultCollectInputs( vPairs, vRanks, Vec_IntEntryLast(vItems) );
403 Vec_IntAppend( vInputs, vItems0 );
404 // collect all those appearing with the last one
405 vItems1 = Acec_MultCollectInputs( vPairs, vRanks, Vec_IntEntryLast(vItems0) );
406 Vec_IntAppend( vInputs, vItems1 );
407
408 Vec_IntPrint( vItems0 );
409 Vec_IntPrint( vItems1 );
410
411 Vec_IntFree( vCounts );
412 Vec_IntFree( vRanks );
413 Vec_IntFree( vPairs );
414 Vec_IntFree( vItems );
415 Vec_IntFree( vItems0 );
416 Vec_IntFree( vItems1 );
417 return vInputs;
418 }
419
420 /**Function*************************************************************
421
422 Synopsis []
423
424 Description []
425
426 SideEffects []
427
428 SeeAlso []
429
430 ***********************************************************************/
Acec_MultDetectInputs(Gia_Man_t * p,Vec_Wec_t * vLeafLits,Vec_Wec_t * vRootLits)431 Vec_Int_t * Acec_MultDetectInputs( Gia_Man_t * p, Vec_Wec_t * vLeafLits, Vec_Wec_t * vRootLits )
432 {
433 Vec_Int_t * vInputs = Vec_IntAlloc( 100 );
434 Vec_Int_t * vSupp = Vec_IntAlloc( 100 );
435 Vec_Wrd_t * vTemp = Vec_WrdStart( Gia_ManObjNum(p) );
436 Vec_Int_t * vRanks = Vec_IntStart( Gia_ManObjNum(p) );
437 Vec_Int_t * vCounts = Vec_IntStart( Gia_ManObjNum(p) );
438 Vec_Int_t * vLevel;
439 int i, k, iLit, iObj, j, Entry;
440
441 ABC_FREE( p->pRefs );
442 Gia_ManCreateRefs( p );
443 Gia_ManForEachCiId( p, iObj, i )
444 printf( "%d=%d ", iObj, Gia_ObjRefNumId(p, iObj) );
445 printf( "\n" );
446 Gia_ManForEachAndId( p, iObj )
447 if ( Gia_ObjRefNumId(p, iObj) >= 4 )
448 printf( "%d=%d ", iObj, Gia_ObjRefNumId(p, iObj) );
449 printf( "\n" );
450
451 Vec_WecForEachLevel( vLeafLits, vLevel, i )
452 Vec_IntForEachEntry( vLevel, iLit, k )
453 {
454 word Truth = Gia_ObjComputeTruth6Cis( p, iLit, vSupp, vTemp );
455 if ( Vec_IntSize(vSupp) >= 0 )
456 {
457 printf( "Leaf = %4d : ", Abc_Lit2Var(iLit) );
458 printf( "Rank = %2d ", i );
459 printf( "Supp = %2d ", Vec_IntSize(vSupp) );
460 Extra_PrintHex( stdout, (unsigned*)&Truth, Vec_IntSize(vSupp) );
461 if ( Vec_IntSize(vSupp) == 4 ) printf( " " );
462 if ( Vec_IntSize(vSupp) == 3 ) printf( " " );
463 if ( Vec_IntSize(vSupp) <= 2 ) printf( " " );
464 printf( " " );
465 Vec_IntPrint( vSupp );
466 /*
467 if ( Truth == 0xF335ACC0F335ACC0 )
468 {
469 int iObj = Abc_Lit2Var(iLit);
470 Gia_Man_t * pGia0 = Gia_ManDupAndCones( p, &iObj, 1, 1 );
471 Gia_ManShow( pGia0, NULL, 0, 0, 0 );
472 Gia_ManStop( pGia0 );
473 }
474 */
475 }
476 // support rank counts
477 Vec_IntForEachEntry( vSupp, Entry, j )
478 {
479 Vec_IntAddToEntry( vRanks, Entry, i );
480 Vec_IntAddToEntry( vCounts, Entry, 1 );
481 }
482 if ( k == Vec_IntSize(vLevel)-1 )
483 printf( "\n" );
484 }
485
486 Vec_IntForEachEntry( vCounts, Entry, j )
487 if ( Entry )
488 printf( "%d=%d(%.2f) ", j, Entry, 1.0*Vec_IntEntry(vRanks, j)/Entry );
489 printf( "\n" );
490
491 Vec_IntFree( vSupp );
492 Vec_WrdFree( vTemp );
493 Vec_IntFree( vRanks );
494 Vec_IntFree( vCounts );
495 return vInputs;
496 }
497
498 /**Function*************************************************************
499
500 Synopsis [Mark nodes whose function is exactly that of a Booth PP.]
501
502 Description []
503
504 SideEffects []
505
506 SeeAlso []
507
508 ***********************************************************************/
Acec_MultMarkPPs(Gia_Man_t * p)509 Vec_Bit_t * Acec_MultMarkPPs( Gia_Man_t * p )
510 {
511 word Saved[32] = {
512 ABC_CONST(0xF335ACC0F335ACC0),
513 ABC_CONST(0x35C035C035C035C0),
514 ABC_CONST(0xD728D728D728D728),
515 ABC_CONST(0xFD80FD80FD80FD80),
516 ABC_CONST(0xACC0ACC0ACC0ACC0),
517 ABC_CONST(0x7878787878787878),
518 ABC_CONST(0x2828282828282828),
519 ABC_CONST(0xD0D0D0D0D0D0D0D0),
520 ABC_CONST(0x8080808080808080),
521 ABC_CONST(0x8888888888888888),
522 ABC_CONST(0xAAAAAAAAAAAAAAAA),
523 ABC_CONST(0x5555555555555555),
524
525 ABC_CONST(0xD5A8D5A8D5A8D5A8),
526 ABC_CONST(0x2A572A572A572A57),
527 ABC_CONST(0xF3C0F3C0F3C0F3C0),
528 ABC_CONST(0x5858585858585858),
529 ABC_CONST(0xA7A7A7A7A7A7A7A7),
530 ABC_CONST(0x2727272727272727),
531 ABC_CONST(0xD8D8D8D8D8D8D8D8)
532 };
533
534 Vec_Bit_t * vRes = Vec_BitStart( Gia_ManObjNum(p) );
535 Vec_Wrd_t * vTemp = Vec_WrdStart( Gia_ManObjNum(p) );
536 Vec_Int_t * vSupp = Vec_IntAlloc( 100 );
537 int i, iObj, nProds = 0;
538 Gia_ManCleanMark0(p);
539 Gia_ManForEachAndId( p, iObj )
540 {
541 word Truth = Gia_ObjComputeTruth6Cis( p, Abc_Var2Lit(iObj, 0), vSupp, vTemp );
542 if ( Vec_IntSize(vSupp) > 6 )
543 continue;
544 vSupp->nSize = Abc_Tt6MinBase( &Truth, vSupp->pArray, vSupp->nSize );
545 if ( Vec_IntSize(vSupp) > 5 )
546 continue;
547 for ( i = 0; i < 32 && Saved[i]; i++ )
548 {
549 if ( Truth == Saved[i] || Truth == ~Saved[i] )
550 {
551 Vec_BitWriteEntry( vRes, iObj, 1 );
552 nProds++;
553 break;
554 }
555 }
556 }
557 Gia_ManCleanMark0(p);
558 printf( "Collected %d pps.\n", nProds );
559 Vec_IntFree( vSupp );
560 Vec_WrdFree( vTemp );
561 return vRes;
562 }
563
564 /**Function*************************************************************
565
566 Synopsis []
567
568 Description []
569
570 SideEffects []
571
572 SeeAlso []
573
574 ***********************************************************************/
Acec_MultFindPPs_rec(Gia_Man_t * p,int iObj,Vec_Int_t * vBold)575 void Acec_MultFindPPs_rec( Gia_Man_t * p, int iObj, Vec_Int_t * vBold )
576 {
577 Gia_Obj_t * pObj;
578 pObj = Gia_ManObj( p, iObj );
579 if ( pObj->fMark0 )
580 return;
581 pObj->fMark0 = 1;
582 if ( !Gia_ObjIsAnd(pObj) )
583 return;
584 Acec_MultFindPPs_rec( p, Gia_ObjFaninId0(pObj, iObj), vBold );
585 Acec_MultFindPPs_rec( p, Gia_ObjFaninId1(pObj, iObj), vBold );
586 Vec_IntPush( vBold, iObj );
587 }
Acec_MultFindPPs(Gia_Man_t * p)588 Vec_Int_t * Acec_MultFindPPs( Gia_Man_t * p )
589 {
590 word Saved[32] = {
591 ABC_CONST(0xF335ACC0F335ACC0),
592 ABC_CONST(0x35C035C035C035C0),
593 ABC_CONST(0xD728D728D728D728),
594 ABC_CONST(0xFD80FD80FD80FD80),
595 ABC_CONST(0xACC0ACC0ACC0ACC0),
596 ABC_CONST(0x7878787878787878),
597 ABC_CONST(0x2828282828282828),
598 ABC_CONST(0xD0D0D0D0D0D0D0D0),
599 ABC_CONST(0x8080808080808080),
600 ABC_CONST(0x8888888888888888),
601 ABC_CONST(0xAAAAAAAAAAAAAAAA),
602 ABC_CONST(0x5555555555555555),
603
604 ABC_CONST(0xD5A8D5A8D5A8D5A8),
605 ABC_CONST(0x2A572A572A572A57),
606 ABC_CONST(0xF3C0F3C0F3C0F3C0),
607 ABC_CONST(0x5858585858585858),
608 ABC_CONST(0xA7A7A7A7A7A7A7A7),
609 ABC_CONST(0x2727272727272727),
610 ABC_CONST(0xD8D8D8D8D8D8D8D8)
611 };
612
613 Vec_Int_t * vBold = Vec_IntAlloc( 100 );
614 Vec_Int_t * vSupp = Vec_IntAlloc( 100 );
615 Vec_Wrd_t * vTemp = Vec_WrdStart( Gia_ManObjNum(p) );
616 int i, iObj, nProds = 0;
617 Gia_ManCleanMark0(p);
618 Gia_ManForEachAndId( p, iObj )
619 {
620 word Truth = Gia_ObjComputeTruth6Cis( p, Abc_Var2Lit(iObj, 0), vSupp, vTemp );
621 if ( Vec_IntSize(vSupp) > 6 )
622 continue;
623 vSupp->nSize = Abc_Tt6MinBase( &Truth, vSupp->pArray, vSupp->nSize );
624 if ( Vec_IntSize(vSupp) > 5 )
625 continue;
626 for ( i = 0; i < 32 && Saved[i]; i++ )
627 {
628 if ( Truth == Saved[i] || Truth == ~Saved[i] )
629 {
630 //printf( "*** Node %d is PP with support %d.\n", iObj, Vec_IntSize(vSupp) );
631 Acec_MultFindPPs_rec( p, iObj, vBold );
632 nProds++;
633 break;
634 }
635 }
636 /*
637 if ( Saved[i] )
638 {
639 printf( "Obj = %4d ", iObj );
640 Extra_PrintHex( stdout, (unsigned*)&Truth, Vec_IntSize(vSupp) );
641 if ( Vec_IntSize(vSupp) == 4 ) printf( " " );
642 if ( Vec_IntSize(vSupp) == 3 ) printf( " " );
643 if ( Vec_IntSize(vSupp) <= 2 ) printf( " " );
644 printf( " " );
645 Vec_IntPrint( vSupp );
646 }
647 */
648 }
649 Gia_ManCleanMark0(p);
650 printf( "Collected %d pps and %d nodes.\n", nProds, Vec_IntSize(vBold) );
651
652 Vec_IntFree( vSupp );
653 Vec_WrdFree( vTemp );
654 return vBold;
655 }
Acec_BoothFindPPG(Gia_Man_t * p)656 Vec_Bit_t * Acec_BoothFindPPG( Gia_Man_t * p )
657 {
658 Vec_Bit_t * vIgnore = Vec_BitStart( Gia_ManObjNum(p) );
659 Vec_Int_t * vMap = Acec_MultFindPPs( p );
660 int i, Entry;
661 Vec_IntForEachEntry( vMap, Entry, i )
662 Vec_BitWriteEntry( vIgnore, Entry, 1 );
663 Vec_IntFree( vMap );
664 return vIgnore;
665 }
Acec_MultFindPPsTest(Gia_Man_t * p)666 void Acec_MultFindPPsTest( Gia_Man_t * p )
667 {
668 Vec_Int_t * vBold = Acec_MultFindPPs( p );
669 Gia_ManShow( p, vBold, 1, 0, 0 );
670 Vec_IntFree( vBold );
671 }
672
673 ////////////////////////////////////////////////////////////////////////
674 /// END OF FILE ///
675 ////////////////////////////////////////////////////////////////////////
676
677
678 ABC_NAMESPACE_IMPL_END
679
680