symtable.c File Reference

#include <stdlib.h>
#include <assert.h>
#include "defines.h"
#include "symtable.h"
#include "util.h"
#include "vsignal.h"
#include "link.h"
#include "sim.h"

Functions
static void	symtable_add_sym_sig (symtable *symtab, vsignal *sig, int msb, int lsb)
static void	symtable_init (symtable *symtab, int msb, int lsb)
symtable *	symtable_create ()
	Creates a new symtable structure.
void	symtable_add (const char *sym, vsignal *sig, int msb, int lsb)
	Creates a new symtable entry and adds it to the specified symbol table.
void	symtable_set_value (const char *sym, const char *value)
	Sets all matching symtable entries to specified value.
void	symtable_assign (const sim_time *time)
	Assigns stored values to all associated signals stored in specified symbol table.
void	symtable_dealloc (symtable *symtab)
	Deallocates all symtable entries for specified symbol table.
Variables
symtable *	vcd_symtab = NULL
int	vcd_symtab_size = 0
symtable **	timestep_tab = NULL
static int	postsim_size = 0

---

Detailed Description

Author:

Trevor Williams (phase1geo@gmail.com)

Date:

1/3/2002

VCD Files

A VCD (Value Change Dump) file is broken into two parts: a definition section and a value change section. The definition section may contain various information about the tool that generated the dumpfile (ignored by Covered), the date that the dumpfile was created (ignored by Covered), comments about the dumpfile (ignored by Covered), and the scope and variable definition information (only part of definition section that is used by Covered).

In the scope and variable definition section, we learn about what variables (these correspond to Covered's signals) are dumped and their corresponding VCD symbol. A VCD symbol can be any sequence of printable ASCII characters such that a sequence is unique to the variable that it represents. In some cases, more than one variable is represented by the same VCD symbol. This occurs when two differently named variables actually reference the same value (as in a Verilog port -- the name changes when moving from one module to another but it contains the same value). Because all references to variables in the simulation section of the VCD file use the VCD symbol as a lookup mechanism, we need to store this variable information (symbol name, its value width, pointer to the variable(s) being referrenced for that symbol name, etc.) in some sort of quick access lookup table. This table is referred to as a symtable in Covered.

In the simulation section of a VCD file, a number of problems can arise when parsing symbols within a timestep. First, when a symbol is encountered, it may pertain to information for several symbols. Therefore, we need to take the value change information and apply it to all variables (Covered signals) that correspond to that symbol. Secondly, the value change information for one VCD symbol may be output several times to the dumpfile. This behavior is unnecessary but some simulators do this whenever a variable changes value while others only output the last value of a VCD symbol prior to changing timesteps. Because of this, Covered will override the value change information of a VCD symbol if multiple lines are found, causing only the last value for a particular VCD symbol to be used.

The Symtable Structure

A symtable is a tree-like structure that is used to hold three pieces of information that are used during the simulation phase of the score command:

1. The name of the VCD symbol that a symtable entry represents
2. A list of pointers to signals which are represented by a VCD symbol.
3. A temporary storage facility to hold value change information for a particular VCD symbol.

The tree structure itself consists of nodes, one node per VCD symbol (with the exception of the root node -- this will be explained later) and each node contains an array of 256 pointers to other nodes. Having an array of 256 pointers allows us to use the name of the VCD symbol as the lookup index into the table. Because VCD symbols are allowed to use any combination of printable ASCII characters, the length of a VCD symbol (even for a large design) is usually between 1-4 characters. This means that finding the information for any given signal only takes between 0 and 3 node hops, making VCD symbol access during the simulation phase extremely fast.

The symtable is initially formed by creating a root node, the root node does not contain any symbol information (because the only symbol it could hold is the NULL character which is not an ASCII printable character). Once the root node has been created, parsing of the VCD definition section begins. When the first VCD symbol is encountered (let's say the character is '!'), we perform a symbol lookup by accessing the 33rd element of the root array (33 is the decimal form of the '!' symbol). In this case the element is a pointer to NULL; therefore, a new node is created. We then grab the next character in the VCD symbol name which is NULL. Because we have hit NULL, we know that the current node that we are in (the newly created node) is the node for our VCD symbol. Therefore, we initialize the new node with the VCD symbol information for our symbol (note that we do not need to store the VCD symbol string in the node because it is used as an index). This process continues until we have processed all VCD symbols in the VCD file, creating a tree structure that remains in memory until the scoring process is complete.

When the simulation section is being parsed, VCD symbols are looked up in the same way that they were stored. When we hit the NULL character in the VCD name string, we have found the node that contains the information for that symbol. We then store the new value into the node.

The Timestep Array

When a timestep is found in the VCD file, we need to perform a simulation of all signal changes made during that timestep. If the symtable structure was the only structure used to find all signals that changed during that timestep, we would need to perform a complete traversal of the tree for each timestep (i.e., we would need to check every signal in the design to see if it had changed). This is unnecessary and results in bad performance.

To make this lookup of changed signals more efficient, an array called "timestep_tab" is used. This array is an array of pointers to symtable tree nodes, one entry for each node in the symtable tree. The array is allocated after the symtable tree has been fully populated and is destroyed at the very end of the score command.

---

Function Documentation

void symtable_add	(	const char *	sym,
		vsignal *	sig,
		int	msb,
		int	lsb
	)

Creates a new symtable entry and adds it to the specified symbol table.

Using the symbol as a unique ID, creates a new symtable element for specified information and places it into the binary tree.

Parameters:

	sym	VCD symbol for the specified signal
	sig	Pointer to signal corresponding to the specified symbol
	msb	Most significant bit of variable to set
	lsb	Least significant bit of variable to set

References PROFILE, PROFILE_END, symtable_s::sig_head, symtable_add_sym_sig(), symtable_create(), symtable_init(), symtable_s::table, vsignal_s::value, and vcd_symtab_size.

Referenced by db_assign_symbol().

  { PROFILE(SYMTABLE_ADD);

  symtable*   curr;  /* Pointer to current symtable entry */
  const char* ptr;   /* Pointer to current character in sym */

  assert( vcd_symtab != NULL );
  assert( sym[0]     != '\0' );
  assert( sig->value != NULL );

  curr = vcd_symtab;
  ptr  = sym;

  while( *ptr != '\0' ) {
    if( curr->table[(int)*ptr] == NULL ) {
      curr->table[(int)*ptr] = symtable_create();
    }
    curr = curr->table[(int)*ptr];
    ptr++;
  }

  if( curr->sig_head == NULL ) {
    if( msb < lsb ) {
      symtable_init( curr, lsb, msb );
    } else {
      symtable_init( curr, msb, lsb );
    }
  }

  symtable_add_sym_sig( curr, sig, msb, lsb );

  /* 
   Finally increment the number of entries in the root table structure.
  */
  vcd_symtab_size++;

  PROFILE_END;

}

static void symtable_add_sym_sig	(	symtable *	symtab,
		vsignal *	sig,
		int	msb,
		int	lsb
	)			[static]

Parameters:

	symtab	Pointer to symbol table entry to initialize.
	sig	Pointer to signal that will be stored in the symtable list.
	msb	Most-significant bit of symbol entry.
	lsb	Least-significant bit of symbol entry.

Creates and adds the specified symtable signal structure to the sym_sig list for the specified symtab.

Parameters:

	symtab	Pointer to symbol table entry to initialize
	sig	Pointer to signal that will be stored in the symtable list
	msb	Most-significant bit of symbol entry
	lsb	Least-significant bit of symbol entry

References sym_sig_s::lsb, malloc_safe, sym_sig_s::msb, sym_sig_s::next, PROFILE, PROFILE_END, sym_sig_s::sig, symtable_s::sig_head, and symtable_s::sig_tail.

Referenced by symtable_add().

  { PROFILE(SYMTABLE_ADD_SYM_SIG);

  sym_sig* new_ss;  /* Pointer to newly created sym_sig structure */

  /* Create new sym_sig structure */
  new_ss       = (sym_sig*)malloc_safe( sizeof( sym_sig ) );
  new_ss->sig  = sig;
  new_ss->msb  = msb;
  new_ss->lsb  = lsb;
  new_ss->next = NULL;

  /* Add new structure to symtable list */
  if( symtab->sig_head == NULL ) {
    symtab->sig_head = symtab->sig_tail = new_ss;
  } else {
    symtab->sig_tail->next = new_ss;
    symtab->sig_tail       = new_ss;
  }

  PROFILE_END;

}

void symtable_assign

(

const sim_time *

time

)

Assigns stored values to all associated signals stored in specified symbol table.

Exceptions:

anonymous

vsignal_vcd_assign

Traverses simulation symentry array, assigning stored string value to the stored signal.

Parameters:

time

Pointer to current simulation time structure

References sym_sig_s::lsb, sym_sig_s::msb, sym_sig_s::next, postsim_size, PROFILE, PROFILE_END, sym_sig_s::sig, symtable_s::sig_head, symtable_s::value, and vsignal_vcd_assign().

Referenced by db_do_timestep().

  { PROFILE(SYMTABLE_ASSIGN);

  symtable* curr;  /* Pointer to current symtable entry */
  sym_sig*  sig;   /* Pointer to current sym_sig in list */
  int       i;     /* Loop iterator */

  for( i=0; i<postsim_size; i++ ) {
    curr = timestep_tab[i];
    sig = curr->sig_head;
    while( sig != NULL ) {
      vsignal_vcd_assign( sig->sig, curr->value, sig->msb, sig->lsb, time );
      sig = sig->next;
    }
    curr->value[0] = '\0';
  }
  postsim_size = 0;

  PROFILE_END;

}

symtable* symtable_create

(

)

Creates a new symtable structure.

Returns:

Returns a pointer to the newly created symbol table entry.

Creates a new symbol table entry and returns a pointer to the newly created structure.

References malloc_safe, PROFILE, PROFILE_END, symtable_s::sig_head, symtable_s::sig_tail, symtable_s::table, and symtable_s::value.

Referenced by covered_sim_calltf(), fst_parse(), lxt_parse(), symtable_add(), and vcd_parse().

                            { PROFILE(SYMTABLE_CREATE);

  symtable* symtab;  /* Pointer to new symtable entry */
  int       i;       /* Loop iterator */

  symtab           = (symtable*)malloc_safe( sizeof( symtable ) );
  symtab->sig_head = NULL;
  symtab->sig_tail = NULL;
  symtab->value    = NULL;
  for( i=0; i<256; i++ ) {
    symtab->table[i] = NULL;
  }

  PROFILE_END;

  return( symtab );

}

void symtable_dealloc

(

symtable *

symtab

)

Deallocates all symtable entries for specified symbol table.

Recursively deallocates all elements of specifies symbol table.

Parameters:

symtab

Pointer to root of symtable to clear

References free_safe, sym_sig_s::next, PROFILE, PROFILE_END, symtable_s::sig_head, symtable_s::size, symtable_dealloc(), symtable_s::table, and symtable_s::value.

Referenced by covered_end_of_sim(), fst_parse(), lxt_parse(), symtable_dealloc(), and vcd_parse().

  { PROFILE(SYMTABLE_DEALLOC);

  sym_sig* curr;  /* Pointer to current sym_sig in list */
  sym_sig* tmp;   /* Temporary pointer to sym_sig */
  int      i;     /* Loop iterator */

  if( symtab != NULL ) {

    for( i=0; i<256; i++ ) {
      symtable_dealloc( symtab->table[i] );
    }

    if( symtab->value != NULL ) {
      free_safe( symtab->value, symtab->size );
    }

    /* Remove sym_sig list */
    curr = symtab->sig_head;
    while( curr != NULL ) {
      tmp = curr->next;
      free_safe( curr, sizeof( sym_sig ) );
      curr = tmp;
    }

    free_safe( symtab, sizeof( symtable ) );

  }

  PROFILE_END;

}

static void symtable_init	(	symtable *	symtab,
		int	msb,
		int	lsb
	)			[static]

Initializes the contents of a symbol table entry.

Parameters:

	symtab	Pointer to symbol table entry to initialize
	msb	Most-significant bit of symbol entry
	lsb	Least-significant bit of symbol entry

References malloc_safe, PROFILE, PROFILE_END, symtable_s::size, and symtable_s::value.

Referenced by symtable_add().

  { PROFILE(SYMTABLE_INIT);

  /* Allocate and initialize the entry */
  symtab->size     = (msb - lsb) + 2;
  symtab->value    = (char*)malloc_safe( symtab->size );
  symtab->value[0] = '\0';

  PROFILE_END;

}

void symtable_set_value	(	const char *	sym,
		const char *	value
	)

Sets all matching symtable entries to specified value.

Performs a binary search of the specified tree to find all matching symtable entries. When the signal is found, the specified value is assigned to the symtable entry.

Parameters:

	sym	Name of symbol to find in the table
	value	Value to set symtable entry to when match found

References FALSE, postsim_size, PROFILE, PROFILE_END, symtable_s::size, symtable_s::table, TRUE, and symtable_s::value.

Referenced by db_set_symbol_char(), and db_set_symbol_string().

  { PROFILE(SYMTABLE_SET_VALUE);

  symtable*   curr;         /* Pointer to current symtable */
  const char* ptr;          /* Pointer to current character in symbol */
  bool        set = FALSE;  /* Specifies if this symtable entry has been set this timestep yet */

  assert( vcd_symtab != NULL );
  assert( sym[0] != '\0' );

  curr = vcd_symtab;
  ptr  = sym;

  while( (curr != NULL) && (*ptr != '\0') ) {
    curr = curr->table[(int)*ptr];
    ptr++;
  }

  if( (curr != NULL) && (curr->value != NULL) ) {

    if( curr->value[0] != '\0' ) {
      set = TRUE;
    }

    /* printf( "strlen( value ): %d, curr->size: %d\n", strlen( value ), curr->size ); */
    assert( strlen( value ) < curr->size );     /* Useful for debugging but not necessary */
    strcpy( curr->value, value );

    if( !set ) {

      /* Place in postsim queue */
      timestep_tab[postsim_size] = curr;
      postsim_size++;
   
    }

  }

  PROFILE_END;

}

---

Variable Documentation

int postsim_size = 0 [static]

Maintains the current number of elements in the timestep_tab array that need to be evaluated after simulation for a timestep.

Referenced by symtable_assign(), and symtable_set_value().

symtable** timestep_tab = NULL

Pointer to the current timestep table array. Please see the file description for how this structure is used.

symtable* vcd_symtab = NULL

Pointer to the VCD symbol table. Please see the file description for how this structure is used.

int vcd_symtab_size = 0

Maintains current number of nodes in the VCD symbol table. This value is used to create the appropriately sized timestep_tab array.

Referenced by covered_end_of_sim(), covered_sim_calltf(), db_check_dumpfile_scopes(), fst_parse(), lxt_parse(), symtable_add(), and vcd_parse().