ESP code rewritten in Ada

ESP code rewritten in Ada

[Ken Garlington]

[comp.lang.ada folks: My news server is down, but hopefully you will get
this...]

Jack W. Crenshaw has a "Programmer's Toolbox" column in Embedded Systems
Programming magazine. I like the column, but it suffers from having all
code examples written in C. For fun, I've decided to start coding some
of his examples in Ada. I found this month's example to be a good
example of what Ada can do for reliability; see if you agree.

First, here's the C code example for a simple filter:

/* General-purpose low-pass filter,
*inplementing a first-order lag. Call
*it with the input signal u, and a
*gain represented by the factor shift.
*Example, shift = 4 inples gain= 1/16
*
* Output is the return value, a short.
*The long integer x is for working
*storage, and should be neither read
*nor written by the user.
*/
short lag_filter(short u, short shift, long*x){
  x += u - (x>>shift);
  return (short)(x>>shift);
}

Elsewhere in the article, it notes that:
(1) "shift" should not change from call to call.
(2) "x" must be declared static and initialized to zero.
(2) If "shift" is known beforehand, it's better to use division rather
than a shift, to handle negative signals properly (although Microsoft
Visual C++ defeats this by always replacing the divide with a shift).

Here's my Ada version, which has the advantages of
(1) forcing "shift" to be constant from call to call
(2) hiding the definition of "x", and automatically initializing it
    (although it still has to be defined "statically" by the user,
    which is annoying.)
(3) Using division to fix the small error for negative signals.
    (Interestingly, one compiler I tried did substitute a
    shift for the divide, but if "x" was negative, it added (shift-1)
    to it first to make the shift correct.)
(4) Permits the use of types other than "short" (within reason)

-- General-purpose low-pass filter,
-- implementing a first-order lag.
-- Instantiate a copy for each input
-- such that copy has same lifetime
-- as input.
generic
  Shift : Positive;
  -- Gain is 2 to the negative Shift.
  -- E.g., shift => 4 implies gain = 1/16
  -- 2**Shift must fit in max precision

  type Signal is range <>;
  -- Signal should be at least Shift+1
  -- bits less than max precision

package Filter is
  function Lag (U : Signal) return Signal;
end Filter;

with System;
package body Filter is

  type Long is range
    System.Min_Int .. System.Max_Int;
  X : Long := 0;

  function Lag (U : Signal) return Signal is
    D : constant Long := Long(2**Shift);
  begin
    X := X + Long(U) - X / D;
    return Signal (X / D);
  end Lag;

end Filter;

I used the following test case:

with Filter;
package Use_Lag is
  subtype Short is Integer range -32768 .. 32767;
  A : Short := 200;
  package A_Filter is new Filter(Shift => 4, Signal => Short);
end Use_Lag;

with Use_Lag; use Use_Lag;
procedure Test is
begin
  A := A_Filter.Lag(A); -- new A should be 12
end Test;

For a 16-bit machine (MIL-STD-1750), I got decent assembly code, similar
to:

  Load R0, U
  Double-Shift Right Arithmetic R0, 16 bits  ; R0/R1 = Long(U)
  Double-Add R0, X
  Double-Load R2, X

Label1: ["fix" negative X before shifting]
  Branch Not Negative, Label2                ; skip if R2/R3 not neg.
  Exclusive-OR R4, R4                        ; R4 = 0
  Load Immediate R5,15                       ; R4/R5 = Long(15)
  Double-Add R2, R4                          ; negative X "fixed"

Label2:
  Double-Shift Right Arithmetic R2, 4        ; R2/R3 = X / D
  Double-Subtract R0, R2                     ; R0/R1 = new X
  Double-Store R0, X                         ; save X for next call

[here, the block of code at Label1 is repeated for the new X, then...]

Label3:
  Double-Shift Right Arithmetic R0, 4        ; R0/R1 = new X / D

[at this point R1 is returned to the user]

Even though using a straight division would have been fewer
instructions, division is so slow on this machine that the sequence
above is still competitive for negative signals (and much faster for
positive signals).

On a 32-bit machine (VAX), I got a much simpler code sequence, since it
used 32 bits for everything:

  Add X and U and store in R3
  Divide X by 16 and store in R2
  Subtract R2 from R3 and store in X
  Divide new X by 16 and return result

In either case, it looks pretty competitive to what a C compiler would
generate. Note that both tests had all checks off, max optimization.

-- 
LMTAS - "Our Brand Means Quality"
For more info, see http://www.lmtas.com or http://www.lmco.com

Re: ESP code rewritten in Ada

[Laurent Guerby]

>-- General-purpose low-pass filter,
>-- implementing a first-order lag.
>-- Instantiate a copy for each input
>-- such that copy has same lifetime
>-- as input.
>generic
>  Shift : Positive;
>  -- Gain is 2 to the negative Shift.
>  -- E.g., shift => 4 implies gain = 1/16
>  -- 2**Shift must fit in max precision
>
>  type Signal is range <>;
>  -- Signal should be at least Shift+1
>  -- bits less than max precision
>
>package Filter is
>  function Lag (U : Signal) return Signal;

   I would add a pragma Inline here, so the generated code may look
even more competitive ;-).

>end Filter;
>
>with System;
>package body Filter is
>
>  type Long is range
>    System.Min_Int .. System.Max_Int;

   This may drag unreasonable arithmetic on a given machine.  May be
it's better to add a "base" type to the generic formal (type Long is
range <>). Or to compute the needed range:

   type Long is range 0 .. 2 ** Shift;

   But this may damage compiler optimization.

>  X : Long := 0;
>
>  function Lag (U : Signal) return Signal is
>    D : constant Long := Long(2**Shift);
>  begin
>    X := X + Long(U) - X / D;
>    return Signal (X / D);
>  end Lag;
>
>end Filter;





-- 
Laurent Guerby <guerby@gnat.com>, Team Ada.
   "Use the Source, Luke. The Source will be with you, always (GPL)."

Re: ESP code rewritten in Ada

[whiting_ms@corning.com (Matt Whiting)]

In article <327F5B2B.47E3@lmtas.lmco.com>, Ken Garlington <garlingtonke@lmtas.lmco.com> writes:
> [comp.lang.ada folks: My news server is down, but hopefully you will get
> this...]
> 
> Jack W. Crenshaw has a "Programmer's Toolbox" column in Embedded Systems
> Programming magazine. I like the column, but it suffers from having all
> code examples written in C. For fun, I've decided to start coding some
> of his examples in Ada. I found this month's example to be a good
> example of what Ada can do for reliability; see if you agree.
> 
> {example deleted} 
> 

Interesting, Ken, as just last week I sent an email to Jack asking him to
consider using Ada in his column in the future!  I got no response ... sigh.
Embedded Systems Programming is one of my favorite magazines and Jack is my
favorite ESP writer, but I find the use of C unfortunate.  Have you considered
sending your example to Jack?

I CAN understand his choice of C as his column is really about techniques and
algorithms rather than implementation.  And C is certainly a concise way to
show a sample implementation, although, I think pseudo-code might be equally
effective, but with the drawback of no way to test the algorithm.

Matt