What is multimap?

Multimap is your way to store mutliple values per key associations.

Keys and values are not sorted! Iterator over multimap issues all key-value pairs, keys are repeated!

key < — >> value

Simple example how to access it.

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main()
{
    multimap<int,string> mm={ {1,"yyyy"},{2,"bbb"},{3,"ccc"},{1,"zzz"},{5,"fff"},{1,"aaas"}};

	int prev=-1;
	for(auto p:mm)
	{
		if(p.first==prev) continue;
		auto ret=mm.equal_range(p.first);
		
		cout << p.first << ": ";
		for(auto j=ret.first;j!=ret.second;j++) cout << j->second << " ";
		cout << endl;
		prev=p.first;
	}
	
	return 0;
}

Screen Shot 2016-02-09 at 11.04.03 AM

 

Porting graywolf placement engine to MacOS X

Electronics Design Automation / Semiconductor community have no doubt heard of a quite capable open-source gate placement engine GrayWolf, successor of Yale Univ’s Timberwolf https://github.com/rubund/graywolf

Many of you also use modern Mac laptops with up-to date i7 processors which performance wise excel over most powerful application servers of beginning of 2010’s. Running EDA tools on Mac in your own consulting projects make a lot of sense, so here we publish Graywolf development version patch on Dec 19, 2015 to run on El Captain.

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 10e2b22..f9bffd2 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1,9 +1,22 @@
 cmake_minimum_required (VERSION 2.6)
 project (graywolf)
+SET(CMAKE_INSTALL_PREFIX $ENV{HOME}/opencad)
+
+IF(APPLE)
+ SET(CMAKE_SHARED_LIBRARY_SUFFIX ".so")
+ENDIF(APPLE)
+
+include_directories(/opt/X11/include)
+link_directories(/opt/X11/lib)
 
 INCLUDE(CheckIncludeFiles)
 
 # Include RPATH in build so that ldconfig is not necessary after install
+
+# disable flood of warning messages
+set (CMAKE_CXX_FLAGS "-Wno-return-type")
+set (CMAKE_C_FLAGS "-Wno-return-type -w")
+
 SET(CMAKE_SKIP_BUILD_RPATH FALSE)
 SET(CMAKE_BUILD_WITH_INSTALL_RPATH FALSE)
 SET(CMAKE_INSTALL_RPATH "${CMAKE_INSTALL_PREFIX}/lib")
diff --git a/src/Ylib/buster.c b/src/Ylib/buster.c
index c493041..b1b4d4a 100644
--- a/src/Ylib/buster.c
+++ b/src/Ylib/buster.c
@@ -227,7 +227,7 @@ INT xpos, ypos ;
 {
     if( xpos == ptS[cornerCountS].x && ypos == ptS[cornerCountS].y ){
     /* avoid redundant points */
-	return ;
+	return 0;
     }
     /* increase the space if necessary */
     if( ++cornerCountS >= ptAllocS ){
@@ -236,6 +236,8 @@ INT xpos, ypos ;
     }
     ptS[cornerCountS].x = xpos ;
     ptS[cornerCountS].y = ypos ;
+
+return 0;
 } /* end add_arb_pt */
 /* ***************************************************************** */
 
diff --git a/src/Ylib/okmalloc.c b/src/Ylib/okmalloc.c
index 10f7a33..cadf600 100644
--- a/src/Ylib/okmalloc.c
+++ b/src/Ylib/okmalloc.c
@@ -901,7 +901,8 @@ VOIDPTR ptr;
 VOID Ysafe_cfree(ptr)
 VOIDPTR ptr;
 {
-    cfree(ptr);
+    // Backward compatibility with SunOS, on Mac just use free -- cfree(ptr);
+	free(ptr);
     return;
 }
 
diff --git a/src/Ylib/program.c b/src/Ylib/program.c
index f2e0c00..e358eb3 100644
--- a/src/Ylib/program.c
+++ b/src/Ylib/program.c
@@ -72,6 +72,11 @@ static char programName[LRECL];
 static char progVersion[LRECL];
 static char progDate[LRECL];
 
+/** 
+Quick fix on Mac OS X, no getCompileDate() here
+*/
+#define getCompileDate() __DATE__
+
 /* ----------------------------------------------------------------- 
    Program control routines                    
    
@@ -85,8 +90,8 @@ char *YinitProgram(name,version,introTextFunction)
      char *version ;
      VOID (*introTextFunction)() ;
 {
-  char    *date ,
-  *getCompileDate() ;
+  char    *date; 
+  //*getCompileDate() ;
   
   Ytimer_start() ;   /* start the elapsed timer */
   sprintf(programName,"%s",name);
diff --git a/src/Ylib/relpath.c b/src/Ylib/relpath.c
index 676ba3a..ec05405 100644
--- a/src/Ylib/relpath.c
+++ b/src/Ylib/relpath.c
@@ -61,7 +61,7 @@ char *known_path, *rel_path ; /* known path and relative path to it */
     char known_fpath[LRECL] ; /* full path of known obj */
     char *ptr ;               /* used to replace obj with relative path */
     char *result ;            /* resulting path */
-    char *Yfixpath(), *strrchr(), *strcat() ;
+    char *Yfixpath(); //, *strrchr(), *strcat( char * destination, const char * source ) ;
     INT  up ;              /* keeps count of backtracking up dir tree */
 
     /* make a copy of path */
diff --git a/src/date/getdate.c b/src/date/getdate.c
index 1da4cb1..174ab65 100644
--- a/src/date/getdate.c
+++ b/src/date/getdate.c
@@ -52,7 +52,7 @@ static char SccsId[] = "@(#) getdate.c version 1.2 5/12/90" ;
 
 main( argc , argv )
 int argc ;
-char *argv ;
+char **argv ;
 {
 
 FILE        *fp ;
diff --git a/src/mincut/readcells_l.h b/src/mincut/readcells_l.h
index bc2cefe..6c9a889 100644
--- a/src/mincut/readcells_l.h
+++ b/src/mincut/readcells_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 FILE *yyin =(FILE *)NULL, *yyout =(FILE *)NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -541,7 +541,7 @@ yylook(){
 	int debug;
 # endif
 	char *yylastch;
-#ifdef linux
+#if	defined(linux) || defined(__APPLE__)
 	if (yyin == NULL) yyin = stdin;
 	if (yyout == NULL) yyout = stdout;
 #endif
diff --git a/src/syntax/readcells_l.h b/src/syntax/readcells_l.h
index e70c84d..1844b77 100644
--- a/src/syntax/readcells_l.h
+++ b/src/syntax/readcells_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if	defined(linux) || defined(__APPLE__)
 FILE *yyin = NULL, *yyout = NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -541,7 +541,7 @@ yylook(){
 	int debug;
 # endif
 	char *yylastch;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 	if (yyin == NULL) yyin = stdin;
 	if (yyout == NULL) yyout = stdout;
 #endif
diff --git a/src/twflow/readobjects_l.h b/src/twflow/readobjects_l.h
index 405f3f2..364d3d8 100644
--- a/src/twflow/readobjects_l.h
+++ b/src/twflow/readobjects_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 FILE *yyin =NULL, *yyout =NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -511,7 +511,7 @@ yylook(){
 	int debug;
 # endif
 	char *yylastch;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 	if (yyin == NULL) yyin = stdin;
 	if (yyout == NULL) yyout = stdout;
 #endif
diff --git a/src/twmc/readcells_l.h b/src/twmc/readcells_l.h
index 32c3c35..1edb217 100644
--- a/src/twmc/readcells_l.h
+++ b/src/twmc/readcells_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 FILE *yyin =NULL, *yyout =NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -527,7 +527,7 @@ yylook(){
 # endif
 	char *yylastch;
 	/* start off machines */
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 	if (yyin == NULL) yyin = stdin;
 	if (yyout == NULL) yyout = stdout;
 #endif
diff --git a/src/twmc/readnets_l.h b/src/twmc/readnets_l.h
index 7212ce4..4f6881b 100644
--- a/src/twmc/readnets_l.h
+++ b/src/twmc/readnets_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 FILE *yyin = NULL, *yyout = NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -526,7 +526,7 @@ yylook(){
 	int debug;
 # endif
 	char *yylastch;
-#ifdef linux
+#if defined(linux) || defined(__APPLE__)
 	if (yyin == NULL) yyin = stdin;
 	if (yyout == NULL) yyout = stdout;
 #endif
diff --git a/src/twsc/readcell_l.h b/src/twsc/readcell_l.h
index 3713661..bb50894 100644
--- a/src/twsc/readcell_l.h
+++ b/src/twsc/readcell_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if	defined(linux) || defined(__APPLE__)
 FILE *yyin = (FILE *)NULL, *yyout = (FILE *)NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -531,7 +531,7 @@ yylook(){
 # endif
 	char *yylastch;
 
-#ifdef linux
+#if	defined(linux) || defined(__APPLE__)
 	if (yyin == (FILE *)NULL) yyin = stdin;
 	if (yyout == (FILE *)NULL) yyout = stdout;
 #endif
diff --git a/src/twsc/readnets_l.h b/src/twsc/readnets_l.h
index b03441a..ef2028e 100644
--- a/src/twsc/readnets_l.h
+++ b/src/twsc/readnets_l.h
@@ -21,7 +21,7 @@ int yyleng; extern char yytext[];
 int yymorfg;
 extern char *yysptr, yysbuf[];
 int yytchar;
-#ifdef linux
+#if	defined(linux) || defined(__APPLE__)
 FILE *yyin =NULL, *yyout =NULL;
 #else
 FILE *yyin ={stdin}, *yyout ={stdout};
@@ -489,7 +489,7 @@ yylook(){
 # endif
 	char *yylastch;
 	/* start off machines */
-#ifdef linux
+#if	defined(linux) || defined(__APPLE__)
 	if (yyin == NULL) yyin = stdin;
 	if (yyout == NULL) yyout = stdout;
 #endif

Library validation project

celll We have just completed a customer project for Standard Cell library validation. Goal of the project was to read in and compare geometrical, pin, layout and logic data of standard cells across Liberty, LEF, Spice, GDS and Verilog representations.

That included custom GDS binary parser and few ASCII lex/yacc readers. boost::polygon was used for geometry operations. Software is written in C++ and collaborated to design team over private GIT repository

Convert UNITS record from Calma GDSII to C++ double

// Compile me:
// gcc 1.cpp -lstdc++ -o 1 -std=c++11 && ./1

#include <math.h>
#include <stdint.h>

#define SIGN_MASK (1ULL << 63)
#define EXP_MASK ((1ULL << 63) - (1ULL << 56))
#define EXP_SHIFT 56
#define SIG_MASK ((1ULL << 56) - 1)

double ibm2ieee(unsigned char *s) {
    unsigned char tmp;
    
    for(int i=0;i<4;i++) tmp=s[i],s[i]=s[7-i],s[7-i]=tmp;
    
    uint64_t x;
    int exp, negate;
    double absval;

    x = *(uint64_t *)s;
    negate = (x & SIGN_MASK) != 0;
    exp = (int)((x & EXP_MASK) >> EXP_SHIFT);
    absval = ldexp((double)(x & SIG_MASK), 4*exp-312);
    return negate ? 0.0-absval : absval;
    }

// GDS UNITs record
// 00000030  ** ** ** ** ** ** 00 14  03 05 3e 41 89 37 4b c6  |******....>A.7K.|
// 00000040  a7 f0 39 44 b8 2f a0 9b  5a 54 00 1c 05 02 00 72  |..9D./..ZT.....r|

// 00 14 03 05 is GDS units records marker
    
#include <iostream>

static union {
    unsigned char c1[8]={0x3e,0x41,0x89,0x37,0x4b,0xc6,0xa7,0xf0};
    double d1;
};

static union {
    unsigned char c2[8]={0x39,0x44,0xb8,0x2f,0xa0,0x9b,0x5a,0x54};
    double d2;
};

int main()
{
    
    d1=ibm2ieee(c1); 
    d2=ibm2ieee(c2);
    
    std::cout << "Size of double=" << sizeof(double) << std::endl;
    std::cout << "Bef: d1=" << d1 << "Meters d2=" << d2 << " d2/d1=" << (d2/d1) 
        << " Microns (10^-6) d2/d1=" << (1000000.*d2/d1) << std::endl;

    return 0;
}

Converting waveform files from scope to LTspice

Screen Shot 2015-04-01 at 11.18.13 AMIn everyday engineering practices, complex electronics design, reverse engineering, it is crucial to verify electronic circuit perfrmance vs circuit spice model. Modern oscilloscopes allow exporting binary waveforms or CSV comma separated files with time and voltage value, that can be used in Spice simuilation.

Here we present a C++ utility that converts RIGOL scope output into CSV format that can be directly imported into LT Spice voltage source model. Using this program helped us to prove that Spice model circuit parametrs is identical to actual physical board, we are seening same waveforms in control points. Continue reading

Revisiting Kernighan-Lin Fiduccia-Mattheyses algorithm

KLFM (aka Kernighan-Lin Fiduccia-Mattheyses) is a well known graph bipartitioning algorithm in electronics design automation, genomics, logistic automation (packing), other key industrial applications. KLFM as we know it of today, was first published back in 1989 in “A Linear-Time Heuristic for Improving Network Partitions” paper [pdf]. That work, and later  research “Fast Hypergraph Partition” [pdf] was either based on the assumption or converted the network hyper graph (each hyperedge often connecting more than two nodes) into a simplified graph with simple edges (connecting only two nodes). Surprisingly, we were not able to find a simple KLFM open source implementation, so we dared to spend few evenings and developed an opensourced one to contribute to the community. Continue reading

Justification of Tcl, PHP and C++ use in Electronics Design

Years ago, open source visionary Richard Stallman started a comp.lang.tcl theme with “Why you should not use Tcl” title. Having implemented large Tcl projects with tens of thousands of lines of Tcl source code, we should partially agree with another quote from Stallmans address “Tcl is ok for writing small programs, but when you push it beyond that, it becomes insufficient“.  Small Tcl programs are extremely effective.  We previosuly twitted on a scripting language comparison and analysis why Tcl, while being a healthy and live, became a niche applications language. Let’s paractically explore by example, where Tcl, PHP (or Perl, Python, Ruby) and C++ fit in Electronics Design Automation software development cicle. Continue reading

EDA custom language parsing with Lex and Yacc

EDA early days was in mid 1970-s, when the first commercial place and route tools were developed. Gerber ASCII format was introduced for machine plotting and exchanging PCB information. Later semiconductor industry employed specialized text languages for ASIC design exchange, with human readable formats such as LEF, DEF and so on. With number of transistors on a chip exceeding few billions on a typical nowadays SoC, and size of the data exchange files becoming enormously large, it is critically important to use high performance language parsing technology.

Please recall Backus-Naur Form, most widely used notation technique for context-free grammar. BNF language syntax description provides a set of deviation rules, as example of DEF parser. Lex and Yacc allow using similar clear and understandable concept:

ndspecs: ndspec | ndspecs ndspec
        ;

ndspec: layer
        | via
        | viarule
        | spacing
        ;

word_via: WORD
        | VIA
        | LAYER
        | WIDTH
        ;

specword: word_via
        {
                spec_stack_add($1.string);
        }
        ;

In 1975, Mike Lesk and Eric Shmidt introduced complementary lexical analyzer generator Lex and parser generator Yacc for language parsing,that allowed developers to create very efficient C parsers. Modern GNU development tools share the same concept, with Flex as a GNU alternative for Lex and Bison being equivalent of Yacc.

We’d like to demonstrate creating Lex/Yacc parser in this walk-trough. Lex and Yacc description is beautiful and simple,  very much alike BNF, while generated C parser is blazing fast and does not require lots of RAM/CPU resources. Continue reading

MCU board schematic

Publishing schematic and board layout files (v18 – SMD 1-layer version, v17 – trough hole that actually went into last production batch) on source forge.

v18-schematic 17-еуые

Board features following components:

Singal line protection circuitry. It is needed to protect MCU from very strong automotive induced voltage spikes. Opto-coupler is used

optoinput

DC-DC regulated voltage stepdown supply with resettable fuse. Device can work on both USB (programming, logic analyzer, Parking Assistant frontend mode) and standalone (intelligent parking assistant) mode. Impulse regulator can be ultra-affordable 33063 or 34063 produced by virtually any semiconductor manufacturer (we used OnSemi).

dcdc

USB and external power self-sense socket (18F4550 datasheet module is impractical):

selfsense