Subject: Re: [linux-audio-dev] LAAGA - how are we doing ?
From: Jim Peters (jim_AT_aguazul.demon.co.uk)
Date: Sat May 05 2001 - 18:09:01 EEST
Paul Davis wrote:
> OTOH, there are several reasons to consider the intermediate buffer
> step, and its something I am definitely thinking about.
Okay, it seems to me that the approach we take to all of this depends
on what is going to be happening more - one-to-one connections (no
mixing required) or many-to-one connections.
Taking the case of mostly one-to-one connections, there is a quite
different approach we could take. This would be to pass the plugin a
list of buffer pointers - both buffers to read and buffers to write
(all using floats as you confirmed). The plugin now has a choice of
whether to copy and modify data, or whether to simply copy the pointer
itself over, and return one of the input buffers as output, in place
of the output buffer it was offered. So, the choice is to either
copy+modify the data, or to just copy the pointer.
This means that when data is passed straight through components, there
is no copying, which would optimise your situation with ardour. Using
this method, however, mixing would always have to be handled by
another step - there is no possibility of a run_adding() kind of
optimisation. This mixing step could be inserted automatically by the
server if it sees two or more connections to the same destination.
Note that this method could be used independently of whether we are
using the `bus' model or the `graph' model of interconnections,
although the approach is more obvious from the `graph' perspective.
Also, the buffers we are moving around could even be pointing to data
in shared memory segments - so even data that's come in from outside
could end up being written straight into the output hardware buffer
without any intermediate copying.
As I say, the downside of all of this is an additional step when
mixing has to take place.
> The "mixing in 16 bit" is precisely what I meant by "if you send to a
> physical channel and the normalized sum exceeds 1, then you clip".
To me the downside of mixing in 16-bit is that errors can accumulate -
for instance adding four floats and then converting to short gives a
+/-0.5 LSB error range, but converting to short first and then adding
gives a total error range of +/-2.0 LSB.
> it would be crazy having the internal objects working directly on the
> (physical) channels, because they could not be (efficiently) portable
> among different audio h/w with differing sample widths, interleave
> status, etc. thats precisely what the engine is for.
Absolutely agreed here - we have to stick to one format internally.
> Yes. Each relay through a bus will cause a "frames_per_cycle" delay. I
> am working on some ideas on how to fix this. Its non-trivial. The
> solution is something like ...
I believe it is possible to convert any `bus' setup into an equivalent
`graph' setup, in which case every feedback loop has a delay of only
one "frames_per_cycle" period.
I've spent most of today putting together a perl-script to test this
and to make sure my ideas are sound, and I'm attaching it at the
bottom of this E-mail (it's only 12K, but I'll stick it on a
web-server next time if people object to attachments like this). I
wrote this because I'm cautious about making suggestions that might
turn out to lead to unexpected difficulties.
This script allows you to load imaginary plugins and connect them up,
and it then generates a suitable run-list, noting any feedback loops
that require a temporary buffer between cycles. There are a couple of
small example networks available by typing `ex 1' and `ex 2'. The
hardware ports are represented by ports HW_I-[1234] for input and
HW_O-[1234] for output. There is no visualisation tool, so you're
just going to have to use pen and paper if you want to see the
networks ! Any bugs in this that anyone finds, please let me know.
The code is not too efficient, but it works (as far as I've tested
it). Erik was talking about some kind of back-tracking method for
evaluating flow graphs in GStreamer, but I can see no need for this -
you can work out the run-list beforehand to avoid this. The run-list
only needs to be recomputed when connections are changed.
However my code doesn't do anything like the caching optimisations he
describes (gain-EQ-pan/gain-EQ-pan/gain-EQ-pan/gain-EQ-pan versus
gain-gain-gain-gain/EQ-EQ-EQ-EQ/pan-pan-pan-pan).
I will volunteer to convert this Perl code to efficient C when the
time comes if no-one else fancies it.
I appreciate the "show us the code" attitude that Kai mentioned,
because working on my own, I do have a tendency to design a bit too
far ahead without always testing my ideas. So - here's the code.
...
I think we are going to have to talk about how applications are going
to get connected together once they have loaded their plugin into the
server. Paul mentioned some idea about each application providing the
means to select the channels or busses it uses. I put forward the
patchbay model. There is also the signal flow graph model which
others have mentioned.
The model used to manage the connections from the outside can be
independent of the model used on the inside to manage how the plugins
are actually executed. So, we could present a `bus' model to the
user, and internally optimise it as a flow-graph using something like
the code in the script.
We need to talk about the connection model used from the outside
because it will make a big difference to how easy all of this is to
use. If it's easy to use, people will see the light right away, but
if we make them struggle, only the few with the faith to go on with
make it through.
Jim
--
Jim Peters / __ | \ Aguazul
/ /| /| )| /| / )|| \
jim_AT_aguazul. \ (_|(_|(_|(_| )(_|I / www.aguazul.
demon.co.uk \ ._) _/ / demon.co.uk
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#!/usr/bin/perl -w
#
# This is just to illustrate that the run-list generating code
# is not impossibly difficult to implement. Almost everything
# here would have to be implemented differently in C.
#
# Jim Peters <jim_AT_aguazul.demon.co.uk>
#
use Term::ReadLine;
my $term= new Term::ReadLine 'demo';
$term->ornaments(0);
#
# Maps each plugin name to a hash of ports, each of which maps
# each port-name in the form "plugin-portname" to a flag
# indicating plugin input (0) or output (1).
#
%plugin= ();
#
# List of input and output ports for all plugins - generated
# from %plugin.
#
@input= ();
@output= ();
#
# List of connections between ports. Values are in the form
# "plugin-port:plugin-port", output port first then input.
#
@conn= ();
#
# Routines
#
sub help {
print <<'END';
help Show this help
load <plugin-name> Load up a plugin with the given name
unload <plugin-name> Unload the given plugin and drop connections
r Generate a run-list for this network
l List all input and output ports
lc List all active connections
c <port-num> <port-num> Connect two ports
d <port-num> <port-num> Disconnect two ports
aip <plugin-port> Add an input port to an already-loaded plugin
aop <plugin-port> Add an output port to an already-loaded plugin
dp <plugin-port> Delete a port from an already-loaded plugin
ex <n> Load up example network `n'
END
}
sub regen_in_out {
my @in= ();
my @out= ();
for my $pl (keys %plugin) {
for my $port (keys %{$plugin{$pl}}) {
if ($plugin{$pl}->{$port}) {
push @out, $port;
} else {
push @in, $port;
}
}
}
@input= sort @in;
@output= sort @out;
}
sub load {
my $nam= shift;
die "Name $nam already in use\n" if (exists($plugin{$nam}));
die "Can't use '-' or ':'\n" if ($nam =~ /-/);
my $lin= shift;
$lin= $term->readline("Enter space-separated list of input port names\nIN> ")
unless (defined $lin);
my @inp= split(' ', $lin);
$lin= shift;
$lin= $term->readline("Enter space-separated list of output port names\nOUT> ")
unless (defined $lin);
my @out= split(' ', $lin);
my %hash= ();
for (@inp) { $hash{"$nam-$_"}= 0; }
for (@out) { $hash{"$nam-$_"}= 1; }
$plugin{$nam}= \%hash;
regen_in_out();
}
sub unload {
my $nam= shift;
# Strip out connections to this
@conn= grep { !/^$nam-/ && !/:$nam-/; } @conn;
delete $plugin{$nam};
regen_in_out();
}
sub list_ports {
my $cnt= @input;
$cnt= @output if ($cnt < @output);
print "Plugin outputs: Plugin inputs:\n";
for (0..$cnt-1) {
my $txt= '';
$txt= sprintf("%2d: ", $_) . $output[$_]
if ($_ < @output);
$txt= substr($txt . " "x40, 0, 40);
$txt .= sprintf("%2d: ", $_) . $input[$_]
if ($_ < @input);
print " $txt\n";
}
}
sub list_conn {
print "Connections:\n";
for (sort @conn) {
/([^:]+):([^:]+)/;
print " $1 -> $2\n";
}
}
sub conn {
die "Expecting two arguments\n" unless @_ == 2;
my $cc= $output[$_[0]] . ":" . $input[$_[1]];
die "Bad args\n" unless $cc !~ /^:/ && $cc !~ /:$/;
for (@conn) {
die "Already connected\n"
if ($_ eq $cc);
}
push @conn, $cc;
}
sub disconn {
die "Expecting two arguments\n" unless @_ == 2;
my $cc= $output[$_[0]] . ":" . $input[$_[1]];
die "Bad args\n" unless $cc !~ /^:/ && $cc !~ /:$/;
@conn= grep { $_ ne $cc; } @conn;
}
sub add_port {
my $typ= shift;
my $nam= shift;
die "Expecting plugin-port name" unless $nam =~ /^([^-]+)-([^-]+)$/;
my $pnam= $1;
die "Plugin doesn't exist" unless exists $plugin{$pnam};
my $pl= $plugin{$pnam};
$pl->{$nam}= $typ;
regen_in_out();
}
sub del_port {
my $nam= shift;
die "Expecting plugin-port name" unless $nam =~ /^([^-]+)-([^-]+)$/;
my $pnam= $1;
die "Plugin doesn't exist" unless exists $plugin{$pnam};
my $pl= $plugin{$pnam};
die "Port doesn't exist" unless exists $pl->{$nam};
delete $pl->{$nam};
regen_in_out();
# Strip out connections
@conn= grep { !/^$nam:/ && !/:$nam$/; } @conn;
}
sub reorder_conn {
# For feedback loops there is a choice as to where the
# cycle-period delay is inserted. The worst choice is to put it
# somewhere in the main path from HW inputs to HW outputs, which
# is where process() might put it without any help. Since
# process() hooks up connections strictly in the order that they
# appear in the list, we need to get the most important
# connections high in the list. This is what this routine does.
# It gives a rating to each plugin according to how far away it is
# from the hardware in each direction. It then considers each
# connection, judging it on the shortest path it is a part of from
# hardware inputs to hardware outputs. The connections taking
# part in the shortest paths go to the top of the list.
# This works because a feedback loop back-tracks in the flow
# graph, so it should always be part of a longer path than the
# more direct route.
# Afterthought: I'm extending this idea to count any plugin that
# has no outputs as a final sink, and any plugin that has no
# inputs as a source. So, I'm measuring distances to the nearest
# source or sink instead of exclusively to the hardware. I think
# this should cover all types of flow-graph now.
my %dist_to_out= ();
my %dist_from_in= ();
for my $pl (keys %plugin) {
$dist_to_out{$pl}= 999999;
$dist_from_in{$pl}= 999999;
}
# Roll forwards from sources (including hardware inputs)
do {
my @list= ();
for my $pl (keys %plugin) {
my $ok= 1;
for (values %{$plugin{$pl}}) { $ok &&= $_; }
next unless $ok;
push @list, $pl;
$dist_from_in{$pl}= 0;
}
my @temp= @conn;
my $lev= 0;
my $togo= @temp;
while ($togo > 0 && @list) {
my @newlist= ();
$lev++;
for my $cc (@temp) {
next if ($cc eq '');
die "Badly formatted connection: $cc"
unless $cc =~ /^([^-]+)-([^:]+):([^-]+)-([^:]+)$/;
my $psrc= $1;
my $pdst= $3;
for my $pl (@list) {
if ($pl eq $psrc) {
$dist_from_in{$pdst}= $lev
if ($lev < $dist_from_in{$pdst});
$cc= ''; # Don't want to process this connection again
$togo--;
push @newlist, $pdst;
}
}
}
@list= @newlist;
}
};
# Roll backwards from sinks (including hardware outputs)
do {
my @list= ();
for my $pl (keys %plugin) {
my $ok= 1;
for (values %{$plugin{$pl}}) { $ok &&= !$_; }
next unless $ok;
push @list, $pl;
$dist_to_out{$pl}= 0;
}
my @temp= @conn;
my $lev= 0;
my $togo= @temp;
while ($togo > 0 && @list) {
my @newlist= ();
$lev++;
for my $cc (@temp) {
next if ($cc eq '');
die "Badly formatted connection: $cc"
unless $cc =~ /^([^-]+)-([^:]+):([^-]+)-([^:]+)$/;
my $psrc= $1;
my $pdst= $3;
for my $pl (@list) {
if ($pl eq $pdst) {
$dist_to_out{$psrc}= $lev
if ($lev < $dist_to_out{$psrc});
$cc= ''; # Don't want to process this connection again
$togo--;
push @newlist, $psrc;
}
}
}
@list= @newlist;
}
};
# Okay, now for each plugin we know the shortest distance to the
# nearest source or sink, with a value of 999999 if there is no
# connection (which indicates an endless loop without any eventual
# source or sink).
# Now we just sort the connections in order of total distance
# before and after a connection - i.e. the shortest path it is
# involved in.
my %temp= ();
for my $cc (@conn) {
die "Badly formatted connection: $cc"
unless $cc =~ /^([^-]+)-([^:]+):([^-]+)-([^:]+)$/;
my $dist= $dist_from_in{$1} + $dist_to_out{$3};
$temp{$cc}= $dist;
}
@conn= sort { $temp{$a} <=> $temp{$b}; } @conn;
return \%dist_from_in, \%dist_to_out;
}
sub process {
# Build up a list of constraints for each plugin as we scan the
# connection list. %order contains one entry for each ordering
# constraint between two plugins, taking the form:
# "plugin1-plugin2" indicating that plugin1 must be before
# plugin2. %active contain a value 1 for each active plugin.
my %order= ();
my %active= ();
my @feedback= ();
# Get better results by optimising the connection order
my ($dist_from_in, $dist_to_out)= reorder_conn();
for $cc (@conn) {
die "Corrupted connection list\n"
unless $cc =~ /^([^-]+)-([^:]+):([^-]+)-([^-]+)$/;
my $psrc= $1;
my $src= "$1-$2";
my $pdst= $3;
my $dst= "$3-$4";
$active{$psrc}= 1;
$active{$pdst}= 1;
if (exists $order{"$pdst-$psrc"}) {
# Feedback loop. This connection must be delayed by one
# cycle-period
push @feedback, $cc;
next;
}
$order{"$psrc-$pdst"}= 1;
# Apply constraints from $pdst to $psrc
for (keys %order) {
$order{"$psrc-$1"}= 1
if (/^$pdst-(.*)$/);
}
# Apply constraints from $psrc to $pdst
for (keys %order) {
$order{"$1-$pdst"}= 1
if (/^(.*)-$psrc$/);
}
}
#DEBUG for (sort keys %order) { print "### $_\n"; }
# Now use the ordering constraints to generate a run-list
my @run_list= ();
my @temp= keys %active;
push @run_list, shift @temp;
while (@temp) {
my $pl= shift @temp;
my $min= 0;
my $max= @run_list;
for (0.._AT_run_list-1) {
my $pl2= $run_list[$_];
$max= $_ if ($max > $_ && exists $order{"$pl-$pl2"});
$min= $_+1 if (exists $order{"$pl2-$pl"});
}
die "Impossible: $min > $max" if ($min > $max);
#DEBUG print "### $pl: $min .. $max\n";
splice @run_list, $min, 0, $pl;
}
print "Execute plugins in this order:\n";
for (@run_list) {
print(" ", substr($_ . " "x32, 0, 32),
"($dist_from_in->{$_}/$dist_to_out->{$_} steps from nearest source/sink)\n");
}
if (@feedback) {
print "\nFeedback buffers required for the following connections:\n";
for (@feedback) {
my $val= $_; $val =~ s/:/ -> /;
print " $val\n";
}
}
}
sub zap_all {
%plugin= ();
@conn= ();
load("HW_I", "", "1 2 3 4");
load("HW_O", "1 2 3 4", "");
}
sub example {
my $ex= shift;
my $max= 2;
die "Give me a number 1 to $max\n"
if ($ex < 1 || $ex > $max);
zap_all();
if ($ex == 1) {
load("AAA", "I", "O");
load("BBB", "I", "O1 O2");
load("CCC", "I1 I2", "O");
load("DDD", "I", "O");
push @conn, "HW_I-1:AAA-I";
push @conn, "HW_I-2:BBB-I";
push @conn, "AAA-O:CCC-I1";
push @conn, "BBB-O1:CCC-I2";
push @conn, "BBB-O2:DDD-I";
push @conn, "CCC-O:HW_O-1";
push @conn, "DDD-O:HW_O-2";
}
if ($ex == 2) {
load("AAA", "I1 I2", "O");
load("BBB", "I1 I2", "O1 O2");
load("CCC", "I", "O1 O2");
push @conn, "HW_I-1:AAA-I1";
push @conn, "BBB-O2:AAA-I2";
push @conn, "AAA-O:BBB-I2";
push @conn, "CCC-O1:BBB-I1";
push @conn, "BBB-O1:CCC-I";
push @conn, "CCC-O2:HW_O-1";
}
}
#
# Main loop
#
zap_all();
help();
while (defined ($_= $term->readline(">> "))) {
my @cmd= split;
next unless @cmd;
my $cmd= shift @cmd;
eval {
if ($cmd eq 'help') { help(); }
elsif ($cmd eq 'load') { load(@cmd); }
elsif ($cmd eq 'unload') { unload(@cmd); }
elsif ($cmd eq 'l') { list_ports(); }
elsif ($cmd eq 'lc') { list_conn(); }
elsif ($cmd eq 'c') { conn(@cmd); }
elsif ($cmd eq 'd') { disconn(@cmd); }
elsif ($cmd eq 'r') { process(); }
elsif ($cmd eq 'aip') { add_port(0, @cmd); }
elsif ($cmd eq 'aop') { add_port(1, @cmd); }
elsif ($cmd eq 'dp') { del_port(@cmd); }
elsif ($cmd eq 'ex') { example(@cmd); }
else { die "`$cmd' not known\n"; }
};
print "$@\n" if ($@);
}
## END ##
This archive was generated by hypermail 2b28 : Sat May 05 2001 - 19:02:44 EEST