/**CFile**************************************************************** FileName [fraigMan.c] PackageName [FRAIG: Functionally reduced AND-INV graphs.] Synopsis [Implementation of the FRAIG manager.] Author [Alan Mishchenko ] Affiliation [UC Berkeley] Date [Ver. 2.0. Started - October 1, 2004] Revision [$Id: fraigMan.c,v 1.11 2005/07/08 01:01:31 alanmi Exp $] ***********************************************************************/ #include "fraigInt.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// abctime timeSelect; abctime timeAssign; //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Sets the default parameters of the package.] Description [This set of parameters is tuned for equivalence checking.] SideEffects [] SeeAlso [] ***********************************************************************/ void Prove_ParamsSetDefault( Prove_Params_t * pParams ) { // clean the parameter structure memset( pParams, 0, sizeof(Prove_Params_t) ); // general parameters pParams->fUseFraiging = 1; // enables fraiging pParams->fUseRewriting = 1; // enables rewriting pParams->fUseBdds = 0; // enables BDD construction when other methods fail pParams->fVerbose = 0; // prints verbose stats // iterations pParams->nItersMax = 6; // the number of iterations // mitering pParams->nMiteringLimitStart = 5000; // starting mitering limit pParams->nMiteringLimitMulti = 2.0; // multiplicative coefficient to increase the limit in each iteration // rewriting (currently not used) pParams->nRewritingLimitStart = 3; // the number of rewriting iterations pParams->nRewritingLimitMulti = 1.0; // multiplicative coefficient to increase the limit in each iteration // fraiging pParams->nFraigingLimitStart = 2; // starting backtrack(conflict) limit pParams->nFraigingLimitMulti = 8.0; // multiplicative coefficient to increase the limit in each iteration // last-gasp BDD construction pParams->nBddSizeLimit = 1000000; // the number of BDD nodes when construction is aborted pParams->fBddReorder = 1; // enables dynamic BDD variable reordering // last-gasp mitering // pParams->nMiteringLimitLast = 1000000; // final mitering limit pParams->nMiteringLimitLast = 0; // final mitering limit // global SAT solver limits pParams->nTotalBacktrackLimit = 0; // global limit on the number of backtracks pParams->nTotalInspectLimit = 0; // global limit on the number of clause inspects // pParams->nTotalInspectLimit = 100000000; // global limit on the number of clause inspects } /**Function************************************************************* Synopsis [Prints out the current values of CEC engine parameters.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Prove_ParamsPrint( Prove_Params_t * pParams ) { printf( "CEC enging parameters:\n" ); printf( "Fraiging enabled: %s\n", pParams->fUseFraiging? "yes":"no" ); printf( "Rewriting enabled: %s\n", pParams->fUseRewriting? "yes":"no" ); printf( "BDD construction enabled: %s\n", pParams->fUseBdds? "yes":"no" ); printf( "Verbose output enabled: %s\n", pParams->fVerbose? "yes":"no" ); printf( "Solver iterations: %d\n", pParams->nItersMax ); printf( "Starting mitering limit: %d\n", pParams->nMiteringLimitStart ); printf( "Multiplicative coeficient for mitering: %.2f\n", pParams->nMiteringLimitMulti ); printf( "Starting number of rewriting iterations: %d\n", pParams->nRewritingLimitStart ); printf( "Multiplicative coeficient for rewriting: %.2f\n", pParams->nRewritingLimitMulti ); printf( "Starting number of conflicts in fraiging: %.2f\n", pParams->nFraigingLimitMulti ); printf( "Multiplicative coeficient for fraiging: %.2f\n", pParams->nRewritingLimitMulti ); printf( "BDD size limit for bailing out: %d\n", pParams->nBddSizeLimit ); printf( "BDD reordering enabled: %s\n", pParams->fBddReorder? "yes":"no" ); printf( "Last-gasp mitering limit: %d\n", pParams->nMiteringLimitLast ); printf( "Total conflict limit: %d\n", (int)pParams->nTotalBacktrackLimit ); printf( "Total inspection limit: %d\n", (int)pParams->nTotalInspectLimit ); printf( "Parameter dump complete.\n" ); } /**Function************************************************************* Synopsis [Sets the default parameters of the package.] Description [This set of parameters is tuned for equivalence checking.] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_ParamsSetDefault( Fraig_Params_t * pParams ) { memset( pParams, 0, sizeof(Fraig_Params_t) ); pParams->nPatsRand = FRAIG_PATTERNS_RANDOM; // the number of words of random simulation info pParams->nPatsDyna = FRAIG_PATTERNS_DYNAMIC; // the number of words of dynamic simulation info pParams->nBTLimit = 99; // the max number of backtracks to perform pParams->nSeconds = 20; // the max number of seconds to solve the miter pParams->fFuncRed = 1; // performs only one level hashing pParams->fFeedBack = 1; // enables solver feedback pParams->fDist1Pats = 1; // enables distance-1 patterns pParams->fDoSparse = 0; // performs equiv tests for sparse functions pParams->fChoicing = 0; // enables recording structural choices pParams->fTryProve = 1; // tries to solve the final miter pParams->fVerbose = 0; // the verbosiness flag pParams->fVerboseP = 0; // the verbose flag for reporting the proof pParams->fInternal = 0; // the flag indicates the internal run pParams->nConfLimit = 0; // the limit on the number of conflicts pParams->nInspLimit = 0; // the limit on the number of inspections } /**Function************************************************************* Synopsis [Sets the default parameters of the package.] Description [This set of parameters is tuned for complete FRAIGing.] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_ParamsSetDefaultFull( Fraig_Params_t * pParams ) { memset( pParams, 0, sizeof(Fraig_Params_t) ); pParams->nPatsRand = FRAIG_PATTERNS_RANDOM; // the number of words of random simulation info pParams->nPatsDyna = FRAIG_PATTERNS_DYNAMIC; // the number of words of dynamic simulation info pParams->nBTLimit = -1; // the max number of backtracks to perform pParams->nSeconds = 20; // the max number of seconds to solve the miter pParams->fFuncRed = 1; // performs only one level hashing pParams->fFeedBack = 1; // enables solver feedback pParams->fDist1Pats = 1; // enables distance-1 patterns pParams->fDoSparse = 1; // performs equiv tests for sparse functions pParams->fChoicing = 0; // enables recording structural choices pParams->fTryProve = 0; // tries to solve the final miter pParams->fVerbose = 0; // the verbosiness flag pParams->fVerboseP = 0; // the verbose flag for reporting the proof pParams->fInternal = 0; // the flag indicates the internal run pParams->nConfLimit = 0; // the limit on the number of conflicts pParams->nInspLimit = 0; // the limit on the number of inspections } /**Function************************************************************* Synopsis [Creates the new FRAIG manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Fraig_Man_t * Fraig_ManCreate( Fraig_Params_t * pParams ) { Fraig_Params_t Params; Fraig_Man_t * p; // set the random seed for simulation // srand( 0xFEEDDEAF ); // srand( 0xDEADCAFE ); Aig_ManRandom( 1 ); // set parameters for equivalence checking if ( pParams == NULL ) Fraig_ParamsSetDefault( pParams = &Params ); // adjust the amount of simulation info if ( pParams->nPatsRand < 128 ) pParams->nPatsRand = 128; if ( pParams->nPatsRand > 32768 ) pParams->nPatsRand = 32768; if ( pParams->nPatsDyna < 128 ) pParams->nPatsDyna = 128; if ( pParams->nPatsDyna > 32768 ) pParams->nPatsDyna = 32768; // if reduction is not performed, allocate minimum simulation info if ( !pParams->fFuncRed ) pParams->nPatsRand = pParams->nPatsDyna = 128; // start the manager p = ABC_ALLOC( Fraig_Man_t, 1 ); memset( p, 0, sizeof(Fraig_Man_t) ); // set the default parameters p->nWordsRand = FRAIG_NUM_WORDS( pParams->nPatsRand ); // the number of words of random simulation info p->nWordsDyna = FRAIG_NUM_WORDS( pParams->nPatsDyna ); // the number of patterns for dynamic simulation info p->nBTLimit = pParams->nBTLimit; // -1 means infinite backtrack limit p->nSeconds = pParams->nSeconds; // the timeout for the final miter p->fFuncRed = pParams->fFuncRed; // enables functional reduction (otherwise, only one-level hashing is performed) p->fFeedBack = pParams->fFeedBack; // enables solver feedback (the use of counter-examples in simulation) p->fDist1Pats = pParams->fDist1Pats; // enables solver feedback (the use of counter-examples in simulation) p->fDoSparse = pParams->fDoSparse; // performs equivalence checking for sparse functions (whose sim-info is 0) p->fChoicing = pParams->fChoicing; // disable accumulation of structural choices (keeps only the first choice) p->fTryProve = pParams->fTryProve; // disable accumulation of structural choices (keeps only the first choice) p->fVerbose = pParams->fVerbose; // disable verbose output p->fVerboseP = pParams->fVerboseP; // disable verbose output p->nInspLimit = pParams->nInspLimit; // the limit on the number of inspections // start memory managers p->mmNodes = Fraig_MemFixedStart( sizeof(Fraig_Node_t) ); p->mmSims = Fraig_MemFixedStart( sizeof(unsigned) * (p->nWordsRand + p->nWordsDyna) ); // allocate node arrays p->vInputs = Fraig_NodeVecAlloc( 1000 ); // the array of primary inputs p->vOutputs = Fraig_NodeVecAlloc( 1000 ); // the array of primary outputs p->vNodes = Fraig_NodeVecAlloc( 1000 ); // the array of internal nodes // start the tables p->pTableS = Fraig_HashTableCreate( 1000 ); // hashing by structure p->pTableF = Fraig_HashTableCreate( 1000 ); // hashing by function p->pTableF0 = Fraig_HashTableCreate( 1000 ); // hashing by function (for sparse functions) // create the constant node p->pConst1 = Fraig_NodeCreateConst( p ); // initialize SAT solver feedback data structures Fraig_FeedBackInit( p ); // initialize other variables p->vProj = Msat_IntVecAlloc( 10 ); p->nTravIds = 1; p->nTravIds2 = 1; return p; } /**Function************************************************************* Synopsis [Deallocates the mapping manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_ManFree( Fraig_Man_t * p ) { int i; if ( p->fVerbose ) { if ( p->fChoicing ) Fraig_ManReportChoices( p ); Fraig_ManPrintStats( p ); // Fraig_TablePrintStatsS( p ); // Fraig_TablePrintStatsF( p ); // Fraig_TablePrintStatsF0( p ); } for ( i = 0; i < p->vNodes->nSize; i++ ) if ( p->vNodes->pArray[i]->vFanins ) { Fraig_NodeVecFree( p->vNodes->pArray[i]->vFanins ); p->vNodes->pArray[i]->vFanins = NULL; } if ( p->vInputs ) Fraig_NodeVecFree( p->vInputs ); if ( p->vNodes ) Fraig_NodeVecFree( p->vNodes ); if ( p->vOutputs ) Fraig_NodeVecFree( p->vOutputs ); if ( p->pTableS ) Fraig_HashTableFree( p->pTableS ); if ( p->pTableF ) Fraig_HashTableFree( p->pTableF ); if ( p->pTableF0 ) Fraig_HashTableFree( p->pTableF0 ); if ( p->pSat ) Msat_SolverFree( p->pSat ); if ( p->vProj ) Msat_IntVecFree( p->vProj ); if ( p->vCones ) Fraig_NodeVecFree( p->vCones ); if ( p->vPatsReal ) Msat_IntVecFree( p->vPatsReal ); if ( p->pModel ) ABC_FREE( p->pModel ); Fraig_MemFixedStop( p->mmNodes, 0 ); Fraig_MemFixedStop( p->mmSims, 0 ); if ( p->pSuppS ) { ABC_FREE( p->pSuppS[0] ); ABC_FREE( p->pSuppS ); } if ( p->pSuppF ) { ABC_FREE( p->pSuppF[0] ); ABC_FREE( p->pSuppF ); } ABC_FREE( p->ppOutputNames ); ABC_FREE( p->ppInputNames ); ABC_FREE( p ); } /**Function************************************************************* Synopsis [Prepares the SAT solver to run on the two nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_ManCreateSolver( Fraig_Man_t * p ) { extern abctime timeSelect; extern abctime timeAssign; assert( p->pSat == NULL ); // allocate data for SAT solving p->pSat = Msat_SolverAlloc( 500, 1, 1, 1, 1, 0 ); p->vVarsInt = Msat_SolverReadConeVars( p->pSat ); p->vAdjacents = Msat_SolverReadAdjacents( p->pSat ); p->vVarsUsed = Msat_SolverReadVarsUsed( p->pSat ); timeSelect = 0; timeAssign = 0; } /**Function************************************************************* Synopsis [Deallocates the mapping manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_ManPrintStats( Fraig_Man_t * p ) { double nMemory; nMemory = ((double)(p->vInputs->nSize + p->vNodes->nSize) * (sizeof(Fraig_Node_t) + sizeof(unsigned)*(p->nWordsRand + p->nWordsDyna) /*+ p->nSuppWords*sizeof(unsigned)*/))/(1<<20); printf( "Words: Random = %d. Dynamic = %d. Used = %d. Memory = %0.2f MB.\n", p->nWordsRand, p->nWordsDyna, p->iWordPerm, nMemory ); printf( "Proof = %d. Counter-example = %d. Fail = %d. FailReal = %d. Zero = %d.\n", p->nSatProof, p->nSatCounter, p->nSatFails, p->nSatFailsReal, p->nSatZeros ); printf( "Nodes: Final = %d. Total = %d. Mux = %d. (Exor = %d.) ClaVars = %d.\n", Fraig_CountNodes(p,0), p->vNodes->nSize, Fraig_ManCountMuxes(p), Fraig_ManCountExors(p), p->nVarsClauses ); if ( p->pSat ) Msat_SolverPrintStats( p->pSat ); Fraig_PrintTime( "AIG simulation ", p->timeSims ); Fraig_PrintTime( "AIG traversal ", p->timeTrav ); Fraig_PrintTime( "Solver feedback ", p->timeFeed ); Fraig_PrintTime( "SAT solving ", p->timeSat ); Fraig_PrintTime( "Network update ", p->timeToNet ); Fraig_PrintTime( "TOTAL RUNTIME ", p->timeTotal ); if ( p->time1 > 0 ) { Fraig_PrintTime( "time1", p->time1 ); } if ( p->time2 > 0 ) { Fraig_PrintTime( "time2", p->time2 ); } if ( p->time3 > 0 ) { Fraig_PrintTime( "time3", p->time3 ); } if ( p->time4 > 0 ) { Fraig_PrintTime( "time4", p->time4 ); } // ABC_PRT( "Selection ", timeSelect ); // ABC_PRT( "Assignment", timeAssign ); fflush( stdout ); } /**Function************************************************************* Synopsis [Allocates simulation information for all nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Fraig_NodeVec_t * Fraig_UtilInfoAlloc( int nSize, int nWords, int fClean ) { Fraig_NodeVec_t * vInfo; unsigned * pUnsigned; int i; assert( nSize > 0 && nWords > 0 ); vInfo = Fraig_NodeVecAlloc( nSize ); pUnsigned = ABC_ALLOC( unsigned, nSize * nWords ); vInfo->pArray[0] = (Fraig_Node_t *)pUnsigned; if ( fClean ) memset( pUnsigned, 0, sizeof(unsigned) * nSize * nWords ); for ( i = 1; i < nSize; i++ ) vInfo->pArray[i] = (Fraig_Node_t *)(((unsigned *)vInfo->pArray[i-1]) + nWords); vInfo->nSize = nSize; return vInfo; } /**Function************************************************************* Synopsis [Returns simulation info of all nodes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Fraig_NodeVec_t * Fraig_ManGetSimInfo( Fraig_Man_t * p ) { Fraig_NodeVec_t * vInfo; Fraig_Node_t * pNode; unsigned * pUnsigned; int nRandom, nDynamic; int i, k, nWords; nRandom = Fraig_ManReadPatternNumRandom( p ); nDynamic = Fraig_ManReadPatternNumDynamic( p ); nWords = nRandom / 32 + nDynamic / 32; vInfo = Fraig_UtilInfoAlloc( p->vNodes->nSize, nWords, 0 ); for ( i = 0; i < p->vNodes->nSize; i++ ) { pNode = p->vNodes->pArray[i]; assert( i == pNode->Num ); pUnsigned = (unsigned *)vInfo->pArray[i]; for ( k = 0; k < nRandom / 32; k++ ) pUnsigned[k] = pNode->puSimR[k]; for ( k = 0; k < nDynamic / 32; k++ ) pUnsigned[nRandom / 32 + k] = pNode->puSimD[k]; } return vInfo; } /**Function************************************************************* Synopsis [Returns 1 if A v B is always true based on the siminfo.] Description [A v B is always true iff A' * B' is always false.] SideEffects [] SeeAlso [] ***********************************************************************/ int Fraig_ManCheckClauseUsingSimInfo( Fraig_Man_t * p, Fraig_Node_t * pNode1, Fraig_Node_t * pNode2 ) { int fCompl1, fCompl2, i; fCompl1 = 1 ^ Fraig_IsComplement(pNode1) ^ Fraig_Regular(pNode1)->fInv; fCompl2 = 1 ^ Fraig_IsComplement(pNode2) ^ Fraig_Regular(pNode2)->fInv; pNode1 = Fraig_Regular(pNode1); pNode2 = Fraig_Regular(pNode2); assert( pNode1 != pNode2 ); // check the simulation info if ( fCompl1 && fCompl2 ) { for ( i = 0; i < p->nWordsRand; i++ ) if ( ~pNode1->puSimR[i] & ~pNode2->puSimR[i] ) return 0; for ( i = 0; i < p->iWordStart; i++ ) if ( ~pNode1->puSimD[i] & ~pNode2->puSimD[i] ) return 0; return 1; } if ( !fCompl1 && fCompl2 ) { for ( i = 0; i < p->nWordsRand; i++ ) if ( pNode1->puSimR[i] & ~pNode2->puSimR[i] ) return 0; for ( i = 0; i < p->iWordStart; i++ ) if ( pNode1->puSimD[i] & ~pNode2->puSimD[i] ) return 0; return 1; } if ( fCompl1 && !fCompl2 ) { for ( i = 0; i < p->nWordsRand; i++ ) if ( ~pNode1->puSimR[i] & pNode2->puSimR[i] ) return 0; for ( i = 0; i < p->iWordStart; i++ ) if ( ~pNode1->puSimD[i] & pNode2->puSimD[i] ) return 0; return 1; } // if ( fCompl1 && fCompl2 ) { for ( i = 0; i < p->nWordsRand; i++ ) if ( pNode1->puSimR[i] & pNode2->puSimR[i] ) return 0; for ( i = 0; i < p->iWordStart; i++ ) if ( pNode1->puSimD[i] & pNode2->puSimD[i] ) return 0; return 1; } } /**Function************************************************************* Synopsis [Adds clauses to the solver.] Description [This procedure is used to add external clauses to the solver. The clauses are given by sets of nodes. Each node stands for one literal. If the node is complemented, the literal is negated.] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_ManAddClause( Fraig_Man_t * p, Fraig_Node_t ** ppNodes, int nNodes ) { Fraig_Node_t * pNode; int i, fComp, RetValue; if ( p->pSat == NULL ) Fraig_ManCreateSolver( p ); // create four clauses Msat_IntVecClear( p->vProj ); for ( i = 0; i < nNodes; i++ ) { pNode = Fraig_Regular(ppNodes[i]); fComp = Fraig_IsComplement(ppNodes[i]); Msat_IntVecPush( p->vProj, MSAT_VAR2LIT(pNode->Num, fComp) ); // printf( "%d(%d) ", pNode->Num, fComp ); } // printf( "\n" ); RetValue = Msat_SolverAddClause( p->pSat, p->vProj ); assert( RetValue ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 
The GNU General Public License, Version 3, 29 June 2007 (GPLv3)
===============================================================

> Copyright &copy; 2007
> Free Software Foundation, Inc.
> <<http://fsf.org/>>

Everyone is permitted to copy and distribute verbatim copies of this license
document, but changing it is not allowed.


Preamble
--------

The GNU General Public License is a free, copyleft license for software and
other kinds of works.

The licenses for most software and other practical works are designed to take
away your freedom to share and change the works. By contrast, the GNU General
Public License is intended to guarantee your freedom to share and change all
versions of a program--to make sure it remains free software for all its users.
We, the Free Software Foundation, use the GNU General Public License for most of
our software; it applies also to any other work released this way by its
authors. You can apply it to your programs, too.

When we speak of free software, we are referring to freedom, not price. Our
General Public Licenses are designed to make sure that you have the freedom to
distribute copies of free software (and charge for them if you wish), that you
receive source code or can get it if you want it, that you can change the
software or use pieces of it in new free programs, and that you know you can do
these things.

To protect your rights, we need to prevent others from denying you these rights
or asking you to surrender the rights. Therefore, you have certain
responsibilities if you distribute copies of the software, or if you modify it:
responsibilities to respect the freedom of others.

For example, if you distribute copies of such a program, whether gratis or for a
fee, you must pass on to the recipients the same freedoms that you received. You
must make sure that they, too, receive or can get the source code. And you must
show them these terms so they know their rights.

Developers that use the GNU GPL protect your rights with two steps: (1) assert
copyright on the software, and (2) offer you this License giving you legal
permission to copy, distribute and/or modify it.

For the developers' and authors' protection, the GPL clearly explains that there
is no warranty for this free software. For both users' and authors' sake, the
GPL requires that modified versions be marked as changed, so that their problems
will not be attributed erroneously to authors of previous versions.

Some devices are designed to deny users access to install or run modified
versions of the software inside them, although the manufacturer can do so. This
is fundamentally incompatible with the aim of protecting users' freedom to
change the software. The systematic pattern of such abuse occurs in the area of
products for individuals to use, which is precisely where it is most
unacceptable. Therefore, we have designed this version of the GPL to prohibit
the practice for those products. If such problems arise substantially in other
domains, we stand ready to extend this provision to those domains in future
versions of the GPL, as needed to protect the freedom of users.

Finally, every program is threatened constantly by software patents. States
should not allow patents to restrict development and use of software on
general-purpose computers, but in those that do, we wish to avoid the special
danger that patents applied to a free program could make it effectively
proprietary. To prevent this, the GPL assures that patents cannot be used to
render the program non-free.

The precise terms and conditions for copying, distribution and modification
follow.


TERMS AND CONDITIONS
--------------------


### 0. Definitions.

"This License refers to version 3 of the GNU General Public License.

"Copyright" also means copyright-like laws that apply to other kinds of works,
such as semiconductor masks.

"The Program" refers to any copyrightable work licensed under this License. Each
licensee is addressed as "you". "Licensees" and "recipients" may be individuals
or organizations.

To "modify" a work means to copy from or adapt all or part of the work in a
fashion requiring copyright permission, other than the making of an exact copy.
The resulting work is called a "modified version" of the earlier work or a work
"based on" the earlier work.

A "covered work" means either the unmodified Program or a work based on the
Program.

To "propagate" a work means to do anything with it that, without permission,
would make you directly or secondarily liable for infringement under applicable
copyright law, except executing it on a computer or modifying a private copy.
Propagation includes copying, distribution (with or without modification),
making available to the public, and in some countries other activities as well.

To "convey" a work means any kind of propagation that enables other parties to
make or receive copies. Mere interaction with a user through a computer network,
with no transfer of a copy, is not conveying.

An interactive user interface displays "Appropriate Legal Notices" to the extent
that it includes a convenient and prominently visible feature that (1) displays
an appropriate copyright notice, and (2) tells the user that there is no
warranty for the work (except to the extent that warranties are provided), that
licensees may convey the work under this License, and how to view a copy of this
License. If the interface presents a list of user commands or options, such as a
menu, a prominent item in the list meets this criterion.


### 1. Source Code.

The "source code" for a work means the preferred form of the work for making
modifications to it. "Object code" means any non-source form of a work.

A "Standard Interface" means an interface that either is an official standard
defined by a recognized standards body, or, in the case of interfaces specified
for a particular programming language, one that is widely used among developers
working in that language.

The "System Libraries" of an executable work include anything, other than the
work as a whole, that (a) is included in the normal form of packaging a Major
Component, but which is not part of that Major Component, and (b) serves only to
enable use of the work with that Major Component, or to implement a Standard
Interface for which an implementation is available to the public in source code
form. A "Major Component", in this context, means a major essential component
(kernel, window system, and so on) of the specific operating system (if any) on
which the executable work runs, or a compiler used to produce the work, or an
object code interpreter used to run it.

The "Corresponding Source" for a work in object code form means all the source
code needed to generate, install, and (for an executable work) run the object
code and to modify the work, including scripts to control those activities.
However, it does not include the work's System Libraries, or general-purpose
tools or generally available free programs which are used unmodified in
performing those activities but which are not part of the work. For example,
Corresponding Source includes interface definition files associated with source
files for the work, and the source code for shared libraries and dynamically
linked subprograms that the work is specifically designed to require, such as by
intimate data communication or control flow between those subprograms and other
parts of the work.

The Corresponding Source need not include anything that users can regenerate
automatically from other parts of the Corresponding Source.

The Corresponding Source for a work in source code form is that same work.


### 2. Basic Permissions.

All rights granted under this License are granted for the term of copyright on
the Program, and are irrevocable provided the stated conditions are met. This
License explicitly affirms your unlimited permission to run the unmodified
Program. The output from running a covered work is covered by this License only
if the output, given its content, constitutes a covered work. This License
acknowledges your rights of fair use or other equivalent, as provided by
copyright law.

You may make, run and propagate covered works that you do not convey, without
conditions so long as your license otherwise remains in force. You may convey
covered works to others for the sole purpose of having them make modifications
exclusively for you, or provide you with facilities for running those works,
provided that you comply with the terms of this License in conveying all
material for which you do not control copyright. Those thus making or running
the covered works for you must do so exclusively on your behalf, under your
direction and control, on terms that prohibit them from making any copies of
your copyrighted material outside their relationship with you.

Conveying under any other circumstances is permitted solely under the conditions
stated below. Sublicensing is not allowed; section 10 makes it unnecessary.


### 3. Protecting Users' Legal Rights From Anti-Circumvention Law.

No covered work shall be deemed part of an effective technological measure under
any applicable law fulfilling obligations under article 11 of the WIPO copyright
treaty adopted on 20 December 1996, or similar laws prohibiting or restricting
circumvention of such measures.

When you convey a covered work, you waive any legal power to forbid
circumvention of technological measures to the extent such circumvention is
effected by exercising rights under this License with respect to the covered
work, and you disclaim any intention to limit operation or modification of the
work as a means of enforcing, against the work's users, your or third parties'
legal rights to forbid circumvention of technological measures.


### 4. Conveying Verbatim Copies.

You may convey verbatim copies of the Program's source code as you receive it,
in any medium, provided that you conspicuously and appropriately publish on each
copy an appropriate copyright notice; keep intact all notices stating that this
License and any non-permissive terms added in accord with section 7 apply to the
code; keep intact all notices of the absence of any warranty; and give all
recipients a copy of this License along with the Program.

You may charge any price or no price for each copy that you convey, and you may
offer support or warranty protection for a fee.


### 5. Conveying Modified Source Versions.

You may convey a work based on the Program, or the modifications to produce it