#include "hop.h"
Go to the source code of this file.
Functions | |
void | Hop_ManIncrementTravId (Hop_Man_t *p) |
void | Hop_ManCleanData (Hop_Man_t *p) |
void | Hop_ObjCleanData_rec (Hop_Obj_t *pObj) |
void | Hop_ObjCollectMulti_rec (Hop_Obj_t *pRoot, Hop_Obj_t *pObj, Vec_Ptr_t *vSuper) |
void | Hop_ObjCollectMulti (Hop_Obj_t *pRoot, Vec_Ptr_t *vSuper) |
int | Hop_ObjIsMuxType (Hop_Obj_t *pNode) |
int | Hop_ObjRecognizeExor (Hop_Obj_t *pObj, Hop_Obj_t **ppFan0, Hop_Obj_t **ppFan1) |
Hop_Obj_t * | Hop_ObjRecognizeMux (Hop_Obj_t *pNode, Hop_Obj_t **ppNodeT, Hop_Obj_t **ppNodeE) |
void | Hop_ObjPrintEqn (FILE *pFile, Hop_Obj_t *pObj, Vec_Vec_t *vLevels, int Level) |
void | Hop_ObjPrintVerilog (FILE *pFile, Hop_Obj_t *pObj, Vec_Vec_t *vLevels, int Level) |
void | Hop_ObjPrintVerbose (Hop_Obj_t *pObj, int fHaig) |
void | Hop_ManPrintVerbose (Hop_Man_t *p, int fHaig) |
void | Hop_ManDumpBlif (Hop_Man_t *p, char *pFileName) |
void Hop_ManCleanData | ( | Hop_Man_t * | p | ) |
Function*************************************************************
Synopsis [Cleans the data pointers for the nodes.]
Description []
SideEffects []
SeeAlso []
Definition at line 60 of file hopUtil.c.
00061 { 00062 Hop_Obj_t * pObj; 00063 int i; 00064 p->nTravIds = 1; 00065 Hop_ManConst1(p)->pData = NULL; 00066 Hop_ManForEachPi( p, pObj, i ) 00067 pObj->pData = NULL; 00068 Hop_ManForEachPo( p, pObj, i ) 00069 pObj->pData = NULL; 00070 Hop_ManForEachNode( p, pObj, i ) 00071 pObj->pData = NULL; 00072 }
void Hop_ManDumpBlif | ( | Hop_Man_t * | p, | |
char * | pFileName | |||
) |
Function*************************************************************
Synopsis [Writes the AIG into the BLIF file.]
Description []
SideEffects []
SeeAlso []
Definition at line 505 of file hopUtil.c.
00506 { 00507 FILE * pFile; 00508 Vec_Ptr_t * vNodes; 00509 Hop_Obj_t * pObj, * pConst1 = NULL; 00510 int i, nDigits, Counter = 0; 00511 if ( Hop_ManPoNum(p) == 0 ) 00512 { 00513 printf( "Hop_ManDumpBlif(): AIG manager does not have POs.\n" ); 00514 return; 00515 } 00516 // collect nodes in the DFS order 00517 vNodes = Hop_ManDfs( p ); 00518 // assign IDs to objects 00519 Hop_ManConst1(p)->pData = (void *)Counter++; 00520 Hop_ManForEachPi( p, pObj, i ) 00521 pObj->pData = (void *)Counter++; 00522 Hop_ManForEachPo( p, pObj, i ) 00523 pObj->pData = (void *)Counter++; 00524 Vec_PtrForEachEntry( vNodes, pObj, i ) 00525 pObj->pData = (void *)Counter++; 00526 nDigits = Hop_Base10Log( Counter ); 00527 // write the file 00528 pFile = fopen( pFileName, "w" ); 00529 fprintf( pFile, "# BLIF file written by procedure Hop_ManDumpBlif() in ABC\n" ); 00530 fprintf( pFile, "# http://www.eecs.berkeley.edu/~alanmi/abc/\n" ); 00531 fprintf( pFile, ".model test\n" ); 00532 // write PIs 00533 fprintf( pFile, ".inputs" ); 00534 Hop_ManForEachPi( p, pObj, i ) 00535 fprintf( pFile, " n%0*d", nDigits, (int)pObj->pData ); 00536 fprintf( pFile, "\n" ); 00537 // write POs 00538 fprintf( pFile, ".outputs" ); 00539 Hop_ManForEachPo( p, pObj, i ) 00540 fprintf( pFile, " n%0*d", nDigits, (int)pObj->pData ); 00541 fprintf( pFile, "\n" ); 00542 // write nodes 00543 Vec_PtrForEachEntry( vNodes, pObj, i ) 00544 { 00545 fprintf( pFile, ".names n%0*d n%0*d n%0*d\n", 00546 nDigits, (int)Hop_ObjFanin0(pObj)->pData, 00547 nDigits, (int)Hop_ObjFanin1(pObj)->pData, 00548 nDigits, (int)pObj->pData ); 00549 fprintf( pFile, "%d%d 1\n", !Hop_ObjFaninC0(pObj), !Hop_ObjFaninC1(pObj) ); 00550 } 00551 // write POs 00552 Hop_ManForEachPo( p, pObj, i ) 00553 { 00554 fprintf( pFile, ".names n%0*d n%0*d\n", 00555 nDigits, (int)Hop_ObjFanin0(pObj)->pData, 00556 nDigits, (int)pObj->pData ); 00557 fprintf( pFile, "%d 1\n", !Hop_ObjFaninC0(pObj) ); 00558 if ( Hop_ObjIsConst1(Hop_ObjFanin0(pObj)) ) 00559 pConst1 = Hop_ManConst1(p); 00560 } 00561 if ( pConst1 ) 00562 fprintf( pFile, ".names n%0*d\n 1\n", nDigits, (int)pConst1->pData ); 00563 fprintf( pFile, ".end\n\n" ); 00564 fclose( pFile ); 00565 Vec_PtrFree( vNodes ); 00566 }
void Hop_ManIncrementTravId | ( | Hop_Man_t * | p | ) |
CFile****************************************************************
FileName [hopUtil.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [And-Inverter Graph package.]
Synopsis [Various procedures.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - May 11, 2006.]
Revision [
] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************
Synopsis [Increments the current traversal ID of the network.]
Description []
SideEffects []
SeeAlso []
Definition at line 42 of file hopUtil.c.
00043 { 00044 if ( p->nTravIds >= (1<<30)-1 ) 00045 Hop_ManCleanData( p ); 00046 p->nTravIds++; 00047 }
void Hop_ManPrintVerbose | ( | Hop_Man_t * | p, | |
int | fHaig | |||
) |
Function*************************************************************
Synopsis [Prints node in HAIG.]
Description []
SideEffects []
SeeAlso []
Definition at line 479 of file hopUtil.c.
00480 { 00481 Vec_Ptr_t * vNodes; 00482 Hop_Obj_t * pObj; 00483 int i; 00484 printf( "PIs: " ); 00485 Hop_ManForEachPi( p, pObj, i ) 00486 printf( " %p", pObj ); 00487 printf( "\n" ); 00488 vNodes = Hop_ManDfs( p ); 00489 Vec_PtrForEachEntry( vNodes, pObj, i ) 00490 Hop_ObjPrintVerbose( pObj, fHaig ), printf( "\n" ); 00491 printf( "\n" ); 00492 }
void Hop_ObjCleanData_rec | ( | Hop_Obj_t * | pObj | ) |
Function*************************************************************
Synopsis [Recursively cleans the data pointers in the cone of the node.]
Description [Applicable to small AIGs only because no caching is performed.]
SideEffects []
SeeAlso []
Definition at line 85 of file hopUtil.c.
00086 { 00087 assert( !Hop_IsComplement(pObj) ); 00088 assert( !Hop_ObjIsPo(pObj) ); 00089 if ( Hop_ObjIsAnd(pObj) ) 00090 { 00091 Hop_ObjCleanData_rec( Hop_ObjFanin0(pObj) ); 00092 Hop_ObjCleanData_rec( Hop_ObjFanin1(pObj) ); 00093 } 00094 pObj->pData = NULL; 00095 }
Function*************************************************************
Synopsis [Detects multi-input gate rooted at this node.]
Description []
SideEffects []
SeeAlso []
Definition at line 130 of file hopUtil.c.
00131 { 00132 assert( !Hop_IsComplement(pRoot) ); 00133 Vec_PtrClear( vSuper ); 00134 Hop_ObjCollectMulti_rec( pRoot, pRoot, vSuper ); 00135 }
Function*************************************************************
Synopsis [Detects multi-input gate rooted at this node.]
Description []
SideEffects []
SeeAlso []
Definition at line 108 of file hopUtil.c.
00109 { 00110 if ( pRoot != pObj && (Hop_IsComplement(pObj) || Hop_ObjIsPi(pObj) || Hop_ObjType(pRoot) != Hop_ObjType(pObj)) ) 00111 { 00112 Vec_PtrPushUnique(vSuper, pObj); 00113 return; 00114 } 00115 Hop_ObjCollectMulti_rec( pRoot, Hop_ObjChild0(pObj), vSuper ); 00116 Hop_ObjCollectMulti_rec( pRoot, Hop_ObjChild1(pObj), vSuper ); 00117 }
int Hop_ObjIsMuxType | ( | Hop_Obj_t * | pNode | ) |
Function*************************************************************
Synopsis [Returns 1 if the node is the root of MUX or EXOR/NEXOR.]
Description []
SideEffects []
SeeAlso []
Definition at line 148 of file hopUtil.c.
00149 { 00150 Hop_Obj_t * pNode0, * pNode1; 00151 // check that the node is regular 00152 assert( !Hop_IsComplement(pNode) ); 00153 // if the node is not AND, this is not MUX 00154 if ( !Hop_ObjIsAnd(pNode) ) 00155 return 0; 00156 // if the children are not complemented, this is not MUX 00157 if ( !Hop_ObjFaninC0(pNode) || !Hop_ObjFaninC1(pNode) ) 00158 return 0; 00159 // get children 00160 pNode0 = Hop_ObjFanin0(pNode); 00161 pNode1 = Hop_ObjFanin1(pNode); 00162 // if the children are not ANDs, this is not MUX 00163 if ( !Hop_ObjIsAnd(pNode0) || !Hop_ObjIsAnd(pNode1) ) 00164 return 0; 00165 // otherwise the node is MUX iff it has a pair of equal grandchildren 00166 return (Hop_ObjFanin0(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC0(pNode1))) || 00167 (Hop_ObjFanin0(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC1(pNode1))) || 00168 (Hop_ObjFanin1(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC0(pNode1))) || 00169 (Hop_ObjFanin1(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC1(pNode1))); 00170 }
Function*************************************************************
Synopsis [Prints Eqn formula for the AIG rooted at this node.]
Description [The formula is in terms of PIs, which should have their names assigned in pObj->pData fields.]
SideEffects []
SeeAlso []
Definition at line 319 of file hopUtil.c.
00320 { 00321 Vec_Ptr_t * vSuper; 00322 Hop_Obj_t * pFanin; 00323 int fCompl, i; 00324 // store the complemented attribute 00325 fCompl = Hop_IsComplement(pObj); 00326 pObj = Hop_Regular(pObj); 00327 // constant case 00328 if ( Hop_ObjIsConst1(pObj) ) 00329 { 00330 fprintf( pFile, "%d", !fCompl ); 00331 return; 00332 } 00333 // PI case 00334 if ( Hop_ObjIsPi(pObj) ) 00335 { 00336 fprintf( pFile, "%s%s", fCompl? "!" : "", pObj->pData ); 00337 return; 00338 } 00339 // AND case 00340 Vec_VecExpand( vLevels, Level ); 00341 vSuper = Vec_VecEntry(vLevels, Level); 00342 Hop_ObjCollectMulti( pObj, vSuper ); 00343 fprintf( pFile, "%s", (Level==0? "" : "(") ); 00344 Vec_PtrForEachEntry( vSuper, pFanin, i ) 00345 { 00346 Hop_ObjPrintEqn( pFile, Hop_NotCond(pFanin, fCompl), vLevels, Level+1 ); 00347 if ( i < Vec_PtrSize(vSuper) - 1 ) 00348 fprintf( pFile, " %s ", fCompl? "+" : "*" ); 00349 } 00350 fprintf( pFile, "%s", (Level==0? "" : ")") ); 00351 return; 00352 }
void Hop_ObjPrintVerbose | ( | Hop_Obj_t * | pObj, | |
int | fHaig | |||
) |
Function*************************************************************
Synopsis [Prints node in HAIG.]
Description []
SideEffects []
SeeAlso []
Definition at line 453 of file hopUtil.c.
00454 { 00455 assert( !Hop_IsComplement(pObj) ); 00456 printf( "Node %p : ", pObj ); 00457 if ( Hop_ObjIsConst1(pObj) ) 00458 printf( "constant 1" ); 00459 else if ( Hop_ObjIsPi(pObj) ) 00460 printf( "PI" ); 00461 else 00462 printf( "AND( %p%s, %p%s )", 00463 Hop_ObjFanin0(pObj), (Hop_ObjFaninC0(pObj)? "\'" : " "), 00464 Hop_ObjFanin1(pObj), (Hop_ObjFaninC1(pObj)? "\'" : " ") ); 00465 printf( " (refs = %3d)", Hop_ObjRefs(pObj) ); 00466 }
Function*************************************************************
Synopsis [Prints Verilog formula for the AIG rooted at this node.]
Description [The formula is in terms of PIs, which should have their names assigned in pObj->pData fields.]
SideEffects []
SeeAlso []
Definition at line 366 of file hopUtil.c.
00367 { 00368 Vec_Ptr_t * vSuper; 00369 Hop_Obj_t * pFanin, * pFanin0, * pFanin1, * pFaninC; 00370 int fCompl, i; 00371 // store the complemented attribute 00372 fCompl = Hop_IsComplement(pObj); 00373 pObj = Hop_Regular(pObj); 00374 // constant case 00375 if ( Hop_ObjIsConst1(pObj) ) 00376 { 00377 fprintf( pFile, "1\'b%d", !fCompl ); 00378 return; 00379 } 00380 // PI case 00381 if ( Hop_ObjIsPi(pObj) ) 00382 { 00383 fprintf( pFile, "%s%s", fCompl? "~" : "", pObj->pData ); 00384 return; 00385 } 00386 // EXOR case 00387 if ( Hop_ObjIsExor(pObj) ) 00388 { 00389 Vec_VecExpand( vLevels, Level ); 00390 vSuper = Vec_VecEntry( vLevels, Level ); 00391 Hop_ObjCollectMulti( pObj, vSuper ); 00392 fprintf( pFile, "%s", (Level==0? "" : "(") ); 00393 Vec_PtrForEachEntry( vSuper, pFanin, i ) 00394 { 00395 Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin, (fCompl && i==0)), vLevels, Level+1 ); 00396 if ( i < Vec_PtrSize(vSuper) - 1 ) 00397 fprintf( pFile, " ^ " ); 00398 } 00399 fprintf( pFile, "%s", (Level==0? "" : ")") ); 00400 return; 00401 } 00402 // MUX case 00403 if ( Hop_ObjIsMuxType(pObj) ) 00404 { 00405 if ( Hop_ObjRecognizeExor( pObj, &pFanin0, &pFanin1 ) ) 00406 { 00407 fprintf( pFile, "%s", (Level==0? "" : "(") ); 00408 Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin0, fCompl), vLevels, Level+1 ); 00409 fprintf( pFile, " ^ " ); 00410 Hop_ObjPrintVerilog( pFile, pFanin1, vLevels, Level+1 ); 00411 fprintf( pFile, "%s", (Level==0? "" : ")") ); 00412 } 00413 else 00414 { 00415 pFaninC = Hop_ObjRecognizeMux( pObj, &pFanin1, &pFanin0 ); 00416 fprintf( pFile, "%s", (Level==0? "" : "(") ); 00417 Hop_ObjPrintVerilog( pFile, pFaninC, vLevels, Level+1 ); 00418 fprintf( pFile, " ? " ); 00419 Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin1, fCompl), vLevels, Level+1 ); 00420 fprintf( pFile, " : " ); 00421 Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin0, fCompl), vLevels, Level+1 ); 00422 fprintf( pFile, "%s", (Level==0? "" : ")") ); 00423 } 00424 return; 00425 } 00426 // AND case 00427 Vec_VecExpand( vLevels, Level ); 00428 vSuper = Vec_VecEntry(vLevels, Level); 00429 Hop_ObjCollectMulti( pObj, vSuper ); 00430 fprintf( pFile, "%s", (Level==0? "" : "(") ); 00431 Vec_PtrForEachEntry( vSuper, pFanin, i ) 00432 { 00433 Hop_ObjPrintVerilog( pFile, Hop_NotCond(pFanin, fCompl), vLevels, Level+1 ); 00434 if ( i < Vec_PtrSize(vSuper) - 1 ) 00435 fprintf( pFile, " %s ", fCompl? "|" : "&" ); 00436 } 00437 fprintf( pFile, "%s", (Level==0? "" : ")") ); 00438 return; 00439 }
Function*************************************************************
Synopsis [Recognizes what nodes are inputs of the EXOR.]
Description []
SideEffects []
SeeAlso []
Definition at line 184 of file hopUtil.c.
00185 { 00186 Hop_Obj_t * p0, * p1; 00187 assert( !Hop_IsComplement(pObj) ); 00188 if ( !Hop_ObjIsNode(pObj) ) 00189 return 0; 00190 if ( Hop_ObjIsExor(pObj) ) 00191 { 00192 *ppFan0 = Hop_ObjChild0(pObj); 00193 *ppFan1 = Hop_ObjChild1(pObj); 00194 return 1; 00195 } 00196 assert( Hop_ObjIsAnd(pObj) ); 00197 p0 = Hop_ObjChild0(pObj); 00198 p1 = Hop_ObjChild1(pObj); 00199 if ( !Hop_IsComplement(p0) || !Hop_IsComplement(p1) ) 00200 return 0; 00201 p0 = Hop_Regular(p0); 00202 p1 = Hop_Regular(p1); 00203 if ( !Hop_ObjIsAnd(p0) || !Hop_ObjIsAnd(p1) ) 00204 return 0; 00205 if ( Hop_ObjFanin0(p0) != Hop_ObjFanin0(p1) || Hop_ObjFanin1(p0) != Hop_ObjFanin1(p1) ) 00206 return 0; 00207 if ( Hop_ObjFaninC0(p0) == Hop_ObjFaninC0(p1) || Hop_ObjFaninC1(p0) == Hop_ObjFaninC1(p1) ) 00208 return 0; 00209 *ppFan0 = Hop_ObjChild0(p0); 00210 *ppFan1 = Hop_ObjChild1(p0); 00211 return 1; 00212 }
Function*************************************************************
Synopsis [Recognizes what nodes are control and data inputs of a MUX.]
Description [If the node is a MUX, returns the control variable C. Assigns nodes T and E to be the then and else variables of the MUX. Node C is never complemented. Nodes T and E can be complemented. This function also recognizes EXOR/NEXOR gates as MUXes.]
SideEffects []
SeeAlso []
Definition at line 228 of file hopUtil.c.
00229 { 00230 Hop_Obj_t * pNode0, * pNode1; 00231 assert( !Hop_IsComplement(pNode) ); 00232 assert( Hop_ObjIsMuxType(pNode) ); 00233 // get children 00234 pNode0 = Hop_ObjFanin0(pNode); 00235 pNode1 = Hop_ObjFanin1(pNode); 00236 00237 // find the control variable 00238 if ( Hop_ObjFanin1(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC1(pNode1)) ) 00239 { 00240 // if ( Fraig_IsComplement(pNode1->p2) ) 00241 if ( Hop_ObjFaninC1(pNode0) ) 00242 { // pNode2->p2 is positive phase of C 00243 *ppNodeT = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1); 00244 *ppNodeE = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1); 00245 return Hop_ObjChild1(pNode1);//pNode2->p2; 00246 } 00247 else 00248 { // pNode1->p2 is positive phase of C 00249 *ppNodeT = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1); 00250 *ppNodeE = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1); 00251 return Hop_ObjChild1(pNode0);//pNode1->p2; 00252 } 00253 } 00254 else if ( Hop_ObjFanin0(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC0(pNode1)) ) 00255 { 00256 // if ( Fraig_IsComplement(pNode1->p1) ) 00257 if ( Hop_ObjFaninC0(pNode0) ) 00258 { // pNode2->p1 is positive phase of C 00259 *ppNodeT = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2); 00260 *ppNodeE = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2); 00261 return Hop_ObjChild0(pNode1);//pNode2->p1; 00262 } 00263 else 00264 { // pNode1->p1 is positive phase of C 00265 *ppNodeT = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2); 00266 *ppNodeE = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2); 00267 return Hop_ObjChild0(pNode0);//pNode1->p1; 00268 } 00269 } 00270 else if ( Hop_ObjFanin0(pNode0) == Hop_ObjFanin1(pNode1) && (Hop_ObjFaninC0(pNode0) ^ Hop_ObjFaninC1(pNode1)) ) 00271 { 00272 // if ( Fraig_IsComplement(pNode1->p1) ) 00273 if ( Hop_ObjFaninC0(pNode0) ) 00274 { // pNode2->p2 is positive phase of C 00275 *ppNodeT = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1); 00276 *ppNodeE = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2); 00277 return Hop_ObjChild1(pNode1);//pNode2->p2; 00278 } 00279 else 00280 { // pNode1->p1 is positive phase of C 00281 *ppNodeT = Hop_Not(Hop_ObjChild1(pNode0));//pNode1->p2); 00282 *ppNodeE = Hop_Not(Hop_ObjChild0(pNode1));//pNode2->p1); 00283 return Hop_ObjChild0(pNode0);//pNode1->p1; 00284 } 00285 } 00286 else if ( Hop_ObjFanin1(pNode0) == Hop_ObjFanin0(pNode1) && (Hop_ObjFaninC1(pNode0) ^ Hop_ObjFaninC0(pNode1)) ) 00287 { 00288 // if ( Fraig_IsComplement(pNode1->p2) ) 00289 if ( Hop_ObjFaninC1(pNode0) ) 00290 { // pNode2->p1 is positive phase of C 00291 *ppNodeT = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2); 00292 *ppNodeE = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1); 00293 return Hop_ObjChild0(pNode1);//pNode2->p1; 00294 } 00295 else 00296 { // pNode1->p2 is positive phase of C 00297 *ppNodeT = Hop_Not(Hop_ObjChild0(pNode0));//pNode1->p1); 00298 *ppNodeE = Hop_Not(Hop_ObjChild1(pNode1));//pNode2->p2); 00299 return Hop_ObjChild1(pNode0);//pNode1->p2; 00300 } 00301 } 00302 assert( 0 ); // this is not MUX 00303 return NULL; 00304 }