[ Content | Sidebar ]

Archives for programming

Portable high resolution timestamps from stat

April 21st, 2012

A small nugget of information that might be useful to someone:

The standard timestamps in struct stat have type time_t which only gives a resolution of seconds which is less than required in many situations. Luckily most operating systems provide a higher resolution timestamp within struct stat but the field name differs among Linux, BSD, etc. On Linux you can get at this with st_mtim.tv_nsec and on BSD it is st_mtimespec.tv_nsec (this also works for OS X).

With autoconf you can use something like:

AC_CHECK_MEMBERS([struct stat.st_mtimespec.tv_nsec])
AC_CHECK_MEMBERS([struct stat.st_mtim.tv_nsec])

And then later you can pull the nanoseconds out of the timestamp with:

#if defined HAVE_STRUCT_STAT_ST_MTIMESPEC_TV_NSEC
   ns = st.st_mtimespec.tv_nsec;
#elif defined HAVE_STRUCT_STAT_ST_MTIM_TV_NSEC
   ns = st.st_mtim.tv_nsec;
#else
   ns = 0;
#endif

This works the same way for atime and ctime as well as mtime. Make sure to handle the #else case as some systems (Cygwin?) don’t have this at all.

VHDL compiler improvements

April 15th, 2012

A while ago I posted about a VHDL compiler I’d started writing. Well I’ve been working on it a bit during the evenings and weekends and it’s acquired several new features. Probably the most significant is that it can now compile the standard IEEE std_logic_1164 and numeric_std packages as well the Synopsys std_logic_arith and std_logic_unsigned packages. If you clone the latest version from GitHub these will be built and installed for you automatically. Note that the original IEEE sources cannot be redistributed due to copyright restrictions so you’ll have to faff about downloading them from the IEEE standards website first – see lib/ieee/README for details.

NVC also now supports a wider range of concurrent statements, including selected and conditional assignments.

This means we can rewrite the counter example from before in a more normal way:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity counter is
    generic ( WIDTH : integer );
    port (
        clk   : in std_logic;
        reset : in std_logic;
        count : out unsigned(WIDTH - 1 downto 0) );
end entity;
 
architecture rtl of counter is
    signal count_r : unsigned(WIDTH - 1 downto 0);
begin
    count <= count_r;
 
    process (clk) is
    begin
        if rising_edge(clk) then
            if reset = '1' then
                count_r <= (others => '0');
            else
                count_r <= count_r + 1;
            end if;
        end if;            
    end process;
end architecture;

And similarly for the top-level test bench:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
 
entity counter_tb is end entity;
 
architecture test of counter_tb is
    constant WIDTH : integer := 16;
    signal clk     : std_logic := '0';
    signal reset   : std_logic := '1';
    signal count   : unsigned(WIDTH - 1 downto 0);
begin
    clk   <= not clk after 5 ns;
    reset <= '0' after 10 ns;
 
    uut: entity work.counter
        generic map ( WIDTH )
        port map ( clk, reset, count );    
end architecture;

Next we have to analyse and elaborate the design:

$ nvc -a counter.vhd
$ nvc -e counter_tb
/usr/lib/llvm-3.0/bin/llvm-ld -r -b /home/nick/nvc/build/work/_WORK.COUNTER_TB.final.bc /home/nick/nvc/build/work/_WORK.COUNTER_TB.elab.bc /home/nick/share/nvc/ieee/_IEEE.NUMERIC_STD-body.bc /home/nick/share/nvc/ieee/_IEEE.STD_LOGIC_1164-body.bc

The long llvm-ld line at the end is a new stage that links together the LLVM bitcode for the elaborated design with the bitcode for any referenced packages – the IEEE standard libraries in this case. This allows LLVM’s link time optimisation to optimise across package boundaries. For example, inlining trivial functions like rising_edge directly into the process.

$ nvc -r --stop-time=1ms --stats counter_tb
** Note: setup:28ms run:104ms maxrss:17872kB

LLVM JIT compilation accounts for most of the memory usage and 28ms setup time. However this overhead should be insignificant for any long-running simulation.

Just running the above simulation is fairly boring so I’ve also started adding a basic VCD dumper. This only works for a small set of data types but includes std_logic and std_logic_vector so should hopefully be quite useful in practice.

$ nvc -r --stop-time=100ns --vcd=out.vcd counter_tb

The output can then be opened in a VCD viewer such as GTKWave.

Note that writing out a VCD will slow the simulation considerably. In the future I’d like to be able to selectively dump signals and support other formats such as GHW or LXT2.

Writing a VHDL compiler

November 5th, 2011

I haven’t posted much about any of my projects for a some time. This is because I’ve spent the past few months squirrelling away on something new: a while ago I decided a good way to learn more about VHDL would be to write a parser/checker for it. I had a vague plan of using it to write a linting tool or indexer. I’ve also wanted to learn more about LLVM so I started hacking together a code generator on the back end of the linting tool that generated LLVM IR for sequential VHDL processes. After that I thought I might as well write a simulation kernel too and it snowballed into something approximating an embryonic VHDL compiler/simulator.

The tool is currently called “nvc” which might stand for “Nick’s VHDL Compiler” or perhaps “New VHDL Compiler”. You can get it from GitHub here: github.com/nickg/nvc. See the README file for instructions on how to build and run it.

The eventual goal is full IEEE 1076-1993 support, or at least as much as possible until I get bored. Currently its capabilities are very limited. In particular it doesn’t implement enough of VHDL to compile the IEEE std_logic_1164 package which makes it almost useless for any real-world designs. The following should give an example of what it can do at the moment though.

entity counter is
    port (
        clk   : in bit;
        count : out integer );
end entity;
 
architecture behav of counter is
begin
    process (clk) is
        variable count_var : integer := 0;
    begin
        if clk'event and clk = '1' then
            count_var := count_var + 1;
            count <= count_var;
        end if;
    end process;
end architecture;

This is a very simple behavioural model of a counter that increments on rising edges of clk. We can also add a top-level entity to generate the clock signal:

entity top is end entity;
 
architecture test of top is
    signal clk   : bit := '0';
    signal count : integer := 0;
begin
    clkgen: process is
    begin
        wait for 5 ns;
        clk <= not clk;
    end process;
 
    uut: entity work.counter
        port map (
            clk   => clk,
            count => count );
 
    process (count) is
    begin
        report integer'image(count);
    end process;
end architecture;

The final process will print the value of the counter every time it changes. You may normally have written the clkgen process with a concurrent assignment:

clk <= not clk after 5 ns;

Unfortunately processes and instantiations and the only sort of concurrent statements implemented in nvc at the moment. This is not as restrictive as it sounds: apart from generate statements all others can be trivially rewritten as processes. This is in fact how they are specified in the standard.

First we need to run the analysis step which parses the code into an internal format, performs type checking, and runs some simplification passes such as constant folding. With the above code in a single file counter.vhd we can run:

$ nvc -a counter.vhd
[gc: freed 425 trees; 297 allocated]

The work library now contains the serialised abstract syntax tree for each analysed design unit:

$ ls -lh work
total 24K
-rw-r--r-- 1 nick nick    8 Nov  5 13:37 _NVC_LIB
-rw-r--r-- 1 nick nick  682 Nov  5 13:37 WORK.COUNTER
-rw-r--r-- 1 nick nick 1.6K Nov  5 13:37 WORK.COUNTER-BEHAV
-rw-r--r-- 1 nick nick   33 Nov  5 13:37 WORK.TOP
-rw-r--r-- 1 nick nick 7.6K Nov  5 13:37 WORK.TOP-TEST

Next we run the elaboration step which builds the full design hierarchy starting from a top level entity. It also runs the LLVM IR code generation step to produce a bitcode file.

$ nvc -e top

(This step produces a large amount of debug output which should be ignored.) If you look inside the work library again you should see the generated LLVM bitcode and a serialised AST for the elaborated design – this is used for debugging later.

$ ls -lhtr work | tail -2
-rw-r--r-- 1 nick nick 8.2K Nov  5 13:39 WORK.TOP.elab
-rw-r--r-- 1 nick nick 1.3K Nov  5 13:39 _WORK.TOP.elab.bc

The elaboration step runs a number of simple LLVM optimisation passes over the bitcode before writing it out but you can run more if you like using the standard LLVM opt tool.

Now we can finally simulate the model! The simplest way to do this is in batch mode as follows:

$ nvc -r --stop-time=50ns top
0ms+0: Report Note: 0
5ns+2: Report Note: 1
15ns+2: Report Note: 2
25ns+2: Report Note: 3
35ns+2: Report Note: 4
45ns+2: Report Note: 5

Normally nvc will run until there are no more events scheduled but as the clkgen process will schedule events forever we have to specify an explicit stop time. The bitcode file is transparently converted into native machine code using LLVM’s JIT engine when the simulation is loaded.

Commercial simulators usually provide an interactive debugging environment as well as a batch mode and nvc tries to emulate this. Use the -c switch to the run command to enter interactive mode:

$ nvc -r -c top
%

This mode uses TCL for command processing, which is the de-facto standard for scripting in the EDA industry. If you have readline or libedit installed you’ll also get fancy line-editing capabilities. The features here are currently pretty limited but we can see the state of all the signals in the design:

% show signals
:top(test):clk                STD.STANDARD.BIT         '0'
:top(test):count              STD.STANDARD.INTEGER     0

Note that nvc has collapsed the ports in counter with the signals in top as they are identical: this might be confusing if you’re searching for a particular name. Now we can run the simulation and verify the signal values change:

% run 45 ns
% 0ms+0: Report Note: 0
5ns+2: Report Note: 1
15ns+2: Report Note: 2
25ns+2: Report Note: 3
35ns+2: Report Note: 4
45ns+2: Report Note: 5
 
% show signals
:top(test):clk                STD.STANDARD.BIT         '1'
:top(test):count              STD.STANDARD.INTEGER     5

Notice that the run command returns straight away and the print outs happen in the background: this is because the interactive mode forks off another process to run the simulation.

A legacy of the project’s origins as a linter, the error messages try to be more helpful than most VHDL compilers:

counter.vhd:33: no suitable overload for operator 
"+"(STD.STANDARD.BIT, universal integer)
            clk <= not (clk + 1);
                        ^^^^^^^

This is about the limit of what nvc can do at the moment. I’m not sure how far I’ll develop it but it’s been good fun hacking thus far. So obviously don’t start using it for real designs or reporting bugs just yet ;-).

Conky BBC weather

April 17th, 2011

I’ve written a Ruby script called bbc-weather.rb that parses the BBC weather RSS for a particular location and formats the data for conky. Here’s an example:

To use it insert the following in your .conkyrc:

${execpi 600 ruby /path/to/bbc-weather.rb 4197}

This will refresh every hour. Replace 4197 with the number of your local weather station. You can find this by looking at the BBC weather URL which is of the form weather/forecast/XXXX. You also need to define two colours for the script to use, in the options section before TEXT, like so:

color1 white
color2 grey

You might also need the following, as conky limits the about of text it will read from a sub-process:

text_buffer_size 2048

UPDATE: apparently this script no longer works with recent BBC Weather updates. Check out the comments for an improved version.

Emacs commit message mode

March 12th, 2011

Here’s a really trivial Emacs major mode for editing Git and Mercurial commit messages: commit-msg-mode.el. It works in basically the same way as the Vim mode, highlighting the summary line, help text, etc.

To use it, put it on your load-path and add the following to your .emacs:

(autoload 'commit-msg-mode "commit-msg-mode"
  "Major mode for editing commit messages." t)
(add-to-list 'auto-mode-alist '("COMMIT_EDITMSG$" . commit-msg-mode))
(add-to-list 'auto-mode-alist '("hg-editor-.*$" . commit-msg-mode))

If you’re anything like me you’ll appreciate having your commit message spell-checked which you can do with:

(add-hook 'commit-msg-mode-hook
          (lambda ()
            (flyspell-mode t)))

Cuckoo Hashes in Lisp

February 20th, 2011

I’ve been learning about cuckoo hashing this evening and to help with that I’ve written an implementation in Common Lisp that others might find useful: cuckoo.lisp. It provides a package cuckoo which exports make-cuckoo-hash, cuckoo-insert, cuckoo-lookup, and cuckoo-delete which perform the obvious hash-table operations. The key feature of cuckoo hashes, if you haven’t come across them before, is that they have constant worst-case lookup time. They are also quite amenable to implementation in hardware.

The keys are implicitly fixnums since it’s a prototype for a C/VHDL implementation, but it shouldn’t be too hard to extend to a generic key type. The insert function automatically rehashes in-place if the table becomes full. The hash function is the xor of three randomly selected universal hash functions, as recommended by the Pagh and Rodler paper.

Chicken SLIME now an Egg

January 22nd, 2011

The Chicken Scheme SWANK implementation I’ve been working on is now available from the main Egg repository. So now you don’t need to faff about with Git and can install it like any other extension using:

$ chicken-install slime

Follow the instructions on the Chicken Wiki to get it set up.

I’ll be mirroring changes in the Chicken SVN to the existing GitHub repository so you can carry on using that if you like.

Since I last posted about this Christian Kellermann has submitted some great patches which improve the SLDB support allowing you to examine lexical scopes in the call chain. For example:

Hit enter or click on a frame in the backtrace that says “more …” and you will see a list of the lexical variables in that scope.

List outgoing changesets in Git

January 8th, 2011

I normally use Git for my personal projects but at work I use Mercurial. While I prefer Git overall, Mercurial has some nice commands that are missing from Git. One particularly useful one is hg out which prints the changesets in your local repository that are missing from the remote. Here is a simple script which does approximately the same thing for Git:

#!/bin/sh
for i in $(git push -n $* 2>&1 \
    | awk '$1 ~ /[a-f0-9]+\.\.[a-f0-9]+/ { print $1; }')
do
    git log --oneline $i
done

Store it as git-out somewhere in your PATH and you can use git out just like a regular Git command.

Chicken SLIME describe and apropos

January 2nd, 2011

The latest version of swank-chicken.scm now supports describe (C-c C-d d) and apropos (C-c C-d a) commands using the chicken-doc egg. Here’s an example:

This apropos window works too: hit C-c C-d a, type a regexp, and a popup window will list the matching symbols; hit enter on the one you’re interested in and you will see the documentation.

Note for all this to work you will need to have the Chicken documentation installed – follow the instructions on the wiki.

Update to Chicken SWANK server

January 1st, 2011

I’ve made some improvements to the Chicken Scheme SWANK server I posted previously. Thank you to all the people who emailed me about it! I’ve fixed several minor bugs and implemented some new features:

The SLIME autodoc minor mode now works giving more detailed parameter hints. For example:

Autodoc is not enabled by default so you’ll need to add

(slime-setup '(slime-autodoc))

to your .emacs. It’s not perfect as it gets confused by symbols exported from Chicken modules (e.g. it does not work when the function has a module# prefix). Any suggestions on how to work around this would be appreciated :).

Several more SLIME commands are now implemented – e.g. C-x C-e and C-x C-r work as expected. Let me know if there’s a command you frequently use that doesn’t work. I’d love to have M-. supported but I can’t see a way to extract the required location information from Chicken.

Simple tab-completion of symbols now works too:

The problems with interrupts from Emacs I mentioned last time have now been fixed and you can easily break out of infinite loops using C-c C-c like this:

Follow the instructions in the last post to get started. If you’ve tried it already a git pull should be all you need. Note that the dependencies have changed slightly:

$ chicken-install fmt apropos symbol-utils

will install the required libraries.

Let me know if you have any questions or comments!