/* * yosys -- Yosys Open SYnthesis Suite * * Copyright (C) 2012 Clifford Wolf * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * */ // [[CITE]] Tarjan's strongly connected components algorithm // Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing 1 (2): 146-160, doi:10.1137/0201010 // http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm #include "kernel/register.h" #include "kernel/celltypes.h" #include "kernel/sigtools.h" #include "kernel/log.h" #include #include #include USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN struct SccWorker { RTLIL::Design *design; RTLIL::Module *module; SigMap sigmap; CellTypes ct; std::set workQueue; std::map> cellToNextCell; std::map cellToPrevSig, cellToNextSig; std::map> cellLabels; std::map cellDepth; std::set cellsOnStack; std::vector cellStack; int labelCounter; std::map cell2scc; std::vector> sccList; void run(RTLIL::Cell *cell, int depth, int maxDepth) { log_assert(workQueue.count(cell) > 0); workQueue.erase(cell); cellLabels[cell] = std::pair(labelCounter, labelCounter); labelCounter++; cellsOnStack.insert(cell); cellStack.push_back(cell); if (maxDepth >= 0) cellDepth[cell] = depth; for (auto nextCell : cellToNextCell[cell]) if (cellLabels.count(nextCell) == 0) { run(nextCell, depth+1, maxDepth); cellLabels[cell].second = min(cellLabels[cell].second, cellLabels[nextCell].second); } else if (cellsOnStack.count(nextCell) > 0 && (maxDepth < 0 || cellDepth[nextCell] + maxDepth > depth)) { cellLabels[cell].second = min(cellLabels[cell].second, cellLabels[nextCell].second); } if (cellLabels[cell].first == cellLabels[cell].second) { if (cellStack.back() == cell) { cellStack.pop_back(); cellsOnStack.erase(cell); } else { log("Found an SCC:"); std::set scc; while (cellsOnStack.count(cell) > 0) { RTLIL::Cell *c = cellStack.back(); cellStack.pop_back(); cellsOnStack.erase(c); log(" %s", RTLIL::id2cstr(c->name)); cell2scc[c] = sccList.size(); scc.insert(c); } sccList.push_back(scc); log("\n"); } } } SccWorker(RTLIL::Design *design, RTLIL::Module *module, bool nofeedbackMode, bool allCellTypes, int maxDepth) : design(design), module(module), sigmap(module) { if (module->processes.size() > 0) { log("Skipping module %s as it contains processes (run 'proc' pass first).\n", module->name.c_str()); return; } if (allCellTypes) { ct.setup(design); } else { ct.setup_internals(); ct.setup_stdcells(); } SigPool selectedSignals; SigSet sigToNextCells; for (auto &it : module->wires_) if (design->selected(module, it.second)) selectedSignals.add(sigmap(RTLIL::SigSpec(it.second))); for (auto &it : module->cells_) { RTLIL::Cell *cell = it.second; if (!design->selected(module, cell)) continue; if (!allCellTypes && !ct.cell_known(cell->type)) continue; workQueue.insert(cell); RTLIL::SigSpec inputSignals, outputSignals; for (auto &conn : cell->connections()) { bool isInput = true, isOutput = true; if (ct.cell_known(cell->type)) { isInput = ct.cell_input(cell->type, conn.first); isOutput = ct.cell_output(cell->type, conn.first); } RTLIL::SigSpec sig = selectedSignals.extract(sigmap(conn.second)); sig.sort_and_unify(); if (isInput) inputSignals.append(sig); if (isOutput) outputSignals.append(sig); } inputSignals.sort_and_unify(); outputSignals.sort_and_unify(); cellToPrevSig[cell] = inputSignals; cellToNextSig[cell] = outputSignals; sigToNextCells.insert(inputSignals, cell); } for (auto cell : workQueue) { cellToNextCell[cell] = sigToNextCells.find(cellToNextSig[cell]); if (!nofeedbackMode && cellToNextCell[cell].count(cell)) { log("Found an SCC:"); std::set scc; log(" %s", RTLIL::id2cstr(cell->name)); cell2scc[cell] = sccList.size(); scc.insert(cell); sccList.push_back(scc); log("\n"); } } labelCounter = 0; cellLabels.clear(); while (!workQueue.empty()) { RTLIL::Cell *cell = *workQueue.begin(); log_assert(cellStack.size() == 0); cellDepth.clear(); run(cell, 0, maxDepth); } log("Found %d SCCs in module %s.\n", int(sccList.size()), RTLIL::id2cstr(module->name)); } void select(RTLIL::Selection &sel) { for (int i = 0; i < int(sccList.size()); i++) { std::set &cells = sccList[i]; RTLIL::SigSpec prevsig, nextsig, sig; for (auto cell : cells) { sel.selected_members[module->name].insert(cell->name); prevsig.append(cellToPrevSig[cell]); nextsig.append(cellToNextSig[cell]); } prevsig.sort_and_unify(); nextsig.sort_and_unify(); sig = prevsig.extract(nextsig); for (auto &chunk : sig.chunks()) if (chunk.wire != NULL) sel.selected_members[module->name].insert(chunk.wire->name); } } }; struct SccPass : public Pass { SccPass() : Pass("scc", "detect strongly connected components (logic loops)") { } void help() YS_OVERRIDE { // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---| log("\n"); log(" scc [options] [selection]\n"); log("\n"); log("This command identifies strongly connected components (aka logic loops) in the\n"); log("design.\n"); log("\n"); log(" -expect \n"); log(" expect to find exactly SSCs. A different number of SSCs will\n"); log(" produce an error.\n"); log("\n"); log(" -max_depth \n"); log(" limit to loops not longer than the specified number of cells. This\n"); log(" can e.g. be useful in identifying small local loops in a module that\n"); log(" implements one large SCC.\n"); log("\n"); log(" -nofeedback\n"); log(" do not count cells that have their output fed back into one of their\n"); log(" inputs as single-cell scc.\n"); log("\n"); log(" -all_cell_types\n"); log(" Usually this command only considers internal non-memory cells. With\n"); log(" this option set, all cells are considered. For unknown cells all ports\n"); log(" are assumed to be bidirectional 'inout' ports.\n"); log("\n"); log(" -set_attr \n"); log(" set the specified attribute on all cells that are part of a logic\n"); log(" loop. the special token {} in the value is replaced with a unique\n"); log(" identifier for the logic loop.\n"); log("\n"); log(" -select\n"); log(" replace the current selection with a selection of all cells and wires\n"); log(" that are part of a found logic loop\n"); log("\n"); } void execute(std::vector args, RTLIL::Design *design) YS_OVERRIDE { std::map setAttr; bool allCellTypes = false; bool selectMode = false; bool nofeedbackMode = false; int maxDepth = -1; int expect = -1; log_header(design, "Executing SCC pass (detecting logic loops).\n"); size_t argidx; for (argidx = 1; argidx < args.size(); argidx++) { if (args[argidx] == "-max_depth" && argidx+1 < args.size()) { maxDepth = atoi(args[++argidx].c_str()); continue; } if (args[argidx] == "-expect" && argidx+1 < args.size()) { expect = atoi(args[++argidx].c_str()); continue; } if (args[argidx] == "-nofeedback") { nofeedbackMode = true; continue; } if (args[argidx] == "-all_cell_types") { allCellTypes = true; continue; } if (args[argidx] == "-set_attr" && argidx+2 < args.size()) { setAttr[args[argidx+1]] = args[argidx+2]; argidx += 2; continue; } if (args[argidx] == "-select") { selectMode = true;
/*
 * This file is subject to the terms of the GFX License. If a copy of
 * the license was not distributed with this file, you can obtain one at:
 *
 *              http://ugfx.org/license.html
 */

/**
 * @file    src/ginput/mouse.h
 * @brief   GINPUT GFX User Input subsystem header file for mouse and touch.
 *
 * @defgroup Mouse Mouse
 * @ingroup GINPUT
 *
 * @details GINPUT allows it to easily interface touchscreens and mices to
 *			your application.
 *
 * @pre		GFX_USE_GINPUT must be set to TRUE in your gfxconf.h
 * @pre		GINPUT_NEED_MOUSE must be set to TRUE in your gfxconf.h
 * 
 * @{
 */

#ifndef _GINPUT_MOUSE_H
#define _GINPUT_MOUSE_H

#if GINPUT_NEED_MOUSE || defined(__DOXYGEN__)

/*===========================================================================*/
/* Type definitions                                                          */
/*===========================================================================*/

/* This type definition is also used by touch */
typedef struct GEventMouse_t {
	GEventType		type;				// The type of this event (GEVENT_MOUSE or GEVENT_TOUCH)
	uint16_t		instance;			// The mouse/touch instance
	coord_t			x, y, z;			// The position of the mouse.
										//		- For touch devices, Z is the current pressure if supported (otherwise 0)
										//		- For mice, Z is the 3rd dimension if supported (otherwise 0)
	uint16_t		current_buttons;	// A bit is set if the button is down.
										//		- For touch only bit 0 is relevant
										//		- For mice the order of the buttons is (from 0 to n)  left, right, middle, any other buttons
										//		- Bit 15 being set indicates that an important mouse event has been missed.
		#define GINPUT_MOUSE_BTN_LEFT		0x0001
		#define GINPUT_MOUSE_BTN_RIGHT		0x0002
		#define GINPUT_MOUSE_BTN_MIDDLE		0x0004
		#define GINPUT_MOUSE_BTN_4			0x0008
		#define GINPUT_MISSED_MOUSE_EVENT	0x8000
		#define GINPUT_TOUCH_PRESSED		GINPUT_MOUSE_BTN_LEFT
	uint16_t		last_buttons;		// The value of current_buttons on the last event
	enum GMouseMeta_e {
		GMETA_NONE = 0,						// There is no meta event currently happening
		GMETA_MOUSE_DOWN = 1,				// Button 0 has just gone down
		GMETA_MOUSE_UP = 2,					// Button 0 has just gone up
		GMETA_MOUSE_CLICK = 4,				// Button 0 has just gone through a short down - up cycle
		GMETA_MOUSE_CXTCLICK = 8			// For mice - The right button has just been depressed
											// For touch - a long press has just occurred
		}				meta;
	GDisplay *			display;		// The display this mouse is currently associated with.
	} GEventMouse;

// Mouse/Touch Listen Flags - passed to geventAddSourceToListener()
#define GLISTEN_MOUSEMETA			0x0001			// Create events for meta events such as CLICK and CXTCLICK
#define GLISTEN_MOUSEDOWNMOVES		0x0002			// Creates mouse move events when the primary mouse button is down (touch is on the surface)
#define GLISTEN_MOUSEUPMOVES		0x0004			// Creates mouse move events when the primary mouse button is up (touch is off the surface - if the hardware allows).
#define	GLISTEN_MOUSENOFILTER		0x0008			// Don't filter out mouse moves where the position hasn't changed.
#define GLISTEN_TOUCHMETA			GLISTEN_MOUSEMETA
#define GLISTEN_TOUCHDOWNMOVES		GLISTEN_MOUSEDOWNMOVES
#define GLISTEN_TOUCHUPMOVES		GLISTEN_MOUSEUPMOVES
#define	GLISTEN_TOUCHNOFILTER		GLISTEN_MOUSENOFILTER

#define GINPUT_MOUSE_NUM_PORTS		1			// The total number of mouse/touch inputs supported

// Event types for the mouse ginput source
#define GEVENT_MOUSE		(GEVENT_GINPUT_FIRST+0)
#define GEVENT_TOUCH		(GEVENT_GINPUT_FIRST+1)

/*===========================================================================*/
/* External declarations.                                                    */
/*===========================================================================*/

#ifdef __cplusplus
extern "C" {
#endif

	/**
	 * @brief	Creates an instance of a mouse and returns the Source handler
	 * @note	HACK: if the instance is 9999, it is treated as instance 0 except
	 * 			that no calibration will be performed!
	 *
	 * @param[in] instance		The ID of the mouse input instance (from 0 to 9999)
	 *
	 * @return		The source handle of the created instance
	 */
	GSourceHandle ginputGetMouse(uint16_t instance);
	
	/**
	 * @brief	Assign the display associated with the mouse
	 * @note	This only needs to be called if the mouse is associated with a display
	 * 			other than the current default display. It must be called before
	 * 			@p ginputGetMouse() if the new display is to be used during the calibration
	 * 			process. Other than calibration the display is used for range checking,
	 * 			and may also be used to display a mouse pointer.
	 *
	 * @param[in] instance		The ID of the mouse input instance
	 * @param[in] g				The GDisplay to which this mouse belongs
	 */
	void ginputSetMouseDisplay(uint16_t instance, GDisplay *g);

	/**
	 * @brief	Get the display currently associated with the mouse
	 * @return	A pointer to the display
	 *
	 * @param[in] instance		The ID of the mouse input instance
	 */
	GDisplay *ginputGetMouseDisplay(uint16_t instance);

	/**
	 * @brief	Get the current mouse position and button status
	 * @note	Unlinke a listener event, this status cannot record meta events such as
	 *			"CLICK".
	 *
	 * @param[in] instance	The ID of the mouse input instance
	 * @param[in] pmouse	The mouse event
	 *
	 * @return	FALSE on an error (eg. invalid instance)
	 */
	bool_t ginputGetMouseStatus(uint16_t instance, GEventMouse *pmouse);

	/**
	 * @brief	Performs a calibration
	 *
	 * @param[in] instance	The ID of the mouse input instance
	 *
	 * @return	FALSE if the driver dosen't support a calibration of if the handle is invalid
	 */
	bool_t ginputCalibrateMouse(uint16_t instance);

	/* Set the routines to save and fetch calibration data.
	 * This function should be called before first calling ginputGetMouse() for a particular instance
	 *	as the gdispGetMouse() routine may attempt to fetch calibration data and perform a startup calibration if there is no way to get it.
	 *	If this is called after gdispGetMouse() has been called and the driver requires calibration storage, it will immediately save the data is has already obtained.
	 * The 'requireFree' parameter indicates if the fetch buffer must be free()'d to deallocate the buffer provided by the Fetch routine.
	 */
	typedef void (*GMouseCalibrationSaveRoutine)(uint16_t instance, const uint8_t *calbuf, size_t sz);			// Save calibration data
	typedef const char * (*GMouseCalibrationLoadRoutine)(uint16_t instance);									// Load calibration data (returns NULL if not data saved)

	/**
	 * @brief	Set the routines to store and restore calibration data
	 *
	 * @details	This function should be called before first calling ginputGetMouse() for a particular instance
	 *			as the gdispGetMouse() routine may attempt to fetch calibration data and perform a startup calibration if there is no way to get it.
	 *			If this is called after gdispGetMouse() has been called and the driver requires calibration storage, it will immediately save the
	 *			data is has already obtained.
	 *
	 * @param[in] instance		The ID of the mouse input instance
	 * @param[in] fnsave		The routine to save the data
	 * @param[in] fnload		The routine to restore the data
	 * @param[in] requireFree	TRUE if the buffer returned by the load function must be freed by the mouse code.
	 */	
	void ginputSetMouseCalibrationRoutines(uint16_t instance, GMouseCalibrationSaveRoutine fnsave, GMouseCalibrationLoadRoutine fnload, bool_t requireFree);

	/**
	 * @brief	Test if a particular mouse/touch instance requires routines to save it's alibration data
	 * @note	Not implemented yet
	 *
	 * @param[in] instance		The ID of the mouse input instance
	 *
	 * @return	TRUE if needed
	 */
	bool_t ginputRequireMouseCalibrationStorage(uint16_t instance);
	
#ifdef __cplusplus
}
#endif

#endif /* GINPUT_NEED_MOUSE */

#endif /* _GINPUT_MOUSE_H */
/** @} */