Sanity check on a weird bit of math and std_logic_unsigned

[M. Norton]

Hello folks,

I'm having to do surgery on something a contractor left us. One small problem was that he took a file with numeric_std already defined and used and then for his own additions added std_logic_unsigned (thanks SO much.) Anyhow, I am having to carefully evaluate what he's doing so that I don't unnecessarily break something that is already working. Not especially well commented either, so I'm having to infer intent from the code as well.

So, I run into a bit of code where he's putting in a little filter and I amhaving trouble trying to figure out what the hell he was getting at, because as far as I can tell, there's code that will never get executed due to the way the math works.

[code snippet, encapsulated in ye olde clocked process]
if (pulse_event_true = '1') then
if ((X"08000000" + count - (X"0000 & count(31 downto 16))) < X"08000000") then
count <= (the above equation);
else
count <= X"08000000";
end if;
else
count <= count - (X"0000 & count(31 downto 16));
end if;
[/code]

Okay, so when there's a pulse, he adds a constant to the count, and otherwise it decays slowly. No trouble there. The problem I've got is that he does that bounds check at the beginning to make sure he doesn't exceed 0x08000000 before he does the addition, otherwise he just caps out at 0x08000000.

The part I don't get is that the saturation limit is exactly the same as the constant he's adding. By my reasoning, the count value could never exceed 0x08000000 except as a starting condition, and then we might have something large enough that it would wrap around 0xfffffffff and then trigger the top clause. This is covered by the fact that the count has an asynchronousreset to 0, and has a synchronous reset to 0 (software controlled elsewhere). Thus as far as I can tell, this count is going to stay at 0 until a pulse comes along, get set to 0x08000000, decay awhile until the next pulse. When another pulse comes along, there's no mathematical way the current count plus 0x08000000 will ever NOT be greater than or equal to 0x08000000 and thus just gets pegged back to the count.

It seems to be working adequately by all reports, but it kind of bugs me. And I'm taking out the std_logic_unsigned crap, so I can pretty easily convert the math to x <= x - shift_right(x,8), but there's that damned as-far-as-I-can-tell-non-executing-code that I have to decide whether to keep or just simplify to what is happening.

Any ideas folks? Am I missing a case whereby C + f(t) is ever < C for all f(t) being non-negative?

Thanks for any responses.

Mark

 

[KJ]

Hello folks,

I'm having to do surgery on something a contractor left us.  One small problem was that he took a file with numeric_std already defined and used and then for his own additions added std_logic_unsigned (thanks SO much.)  Anyhow, I am having to carefully evaluate what he's doing so that I don't unnecessarily break something that is already working.  Not especially well commented either, so I'm having to infer intent from the code as well.

While not on the point of your post, let me suggest that a good
general check that you haven't broken something is to create a
testbench that instances both the original code and your new code,
drives all of the inputs to both identically and then add assertions
to check that the outputs of both are always the same. You're
dependent on the quality of the testbench to make sure that you cover
as much of the cases as possible, but that will always be the case
anyway.

So, I run into a bit of code where he's putting in a little filter and I am having trouble trying to figure out what the hell he was getting at, because as far as I can tell, there's code that will never get executed due tothe way the math works.

Okay, so when there's a pulse, he adds a constant to the count, and otherwise it decays slowly.  No trouble there.  The problem I've got is thathe does that bounds check at the beginning to make sure he doesn't exceed 0x08000000 before he does the addition, otherwise he just caps out at 0x08000000.

The part I don't get is that the saturation limit is exactly the same as the constant he's adding.  By my reasoning, the count value could never exceed 0x08000000 except as a starting condition, and then we might have something large enough that it would wrap around 0xfffffffff and then trigger the top clause.  This is covered by the fact that the count has an asynchronous reset to 0, and has a synchronous reset to 0 (software controlled elsewhere).  Thus as far as I can tell, this count is going to stay at 0 until a pulse comes along, get set to 0x08000000, decay awhile until the nextpulse.  When another pulse comes along, there's no mathematical way the current count plus 0x08000000 will ever NOT be greater than or equal to 0x08000000 and thus just gets pegged back to the count.

I'm not sure what the function of pulse_event_true is supposed to
represent, but it is operating as a synchronous reset; when
pulse_event_true is '1' then count is set to X"08000000". At first, I
didn't exhaustively test the 2^28 different possible starting
conditions for count, but I did test four of them (including all bits
set to 'U') and in all cases, pulse_event_true set to '1' caused count
to be set to X"08000000".

Next I synthesized it with Quartus. If the innermost loop is
logically useless than it might synthesize away completely and a build
with the code 'as is' and one without the innermost 'if' statement
ideally should produce the exact same output. If it did then it would
prove that the innermost check is useless. Alas, such was not the
case. Your original code synthesized to 100+ Altera ALUTs, the code
with the 'if' statement removed synthesized to 33 ALUTs. While the
same output file would be sufficient to prove the innermost loop
useless, getting different results does not prove anything.

The next thought was '2^28 isn't *that* big of a number (268+ million)
so create a testbench that initializes count to a value, set
pulse_event_true to 1 and see if count goes to X"08000000" at the next
clock. Repeat for all possible values of count. The code to do all
of this is posted below. It looks like it will take ~2 hours to
complete. So far it is ~1/3 of the way through and has not hit an
assertion. Assuming that it really does complete that will show that
the innermost 'if' statement really is useless and can be
removed...and based on the synthesis information you will save some
logic by getting rid of it.

My guess is that the entire inner 'if' statement used to be quite
different and evolved into the present form over time. If the
contractor archived any earlier builds you might peruse those to see
the evolution of that block of code to satisfy your curiousity. At
some point though that code took a poor mutation (in fact, it might
have only been one mutation that occurred several weeks after not
having looked at the code in a while). So now would be a good time
for natural selection to takes its turn and wipe out that code.

It seems to be working adequately by all reports, but it kind of bugs me. And I'm taking out the std_logic_unsigned crap, so I can pretty easily convert the math to x <= x - shift_right(x,8), but there's that damned as-far-as-I-can-tell-non-executing-code that I have to decide whether to keepor just simplify to what is happening.

Any ideas folks?  Am I missing a case whereby C + f(t) is ever < C for all f(t) being non-negative?

Unless there is something about using the non-standard libraries that
makes it function differently (but I doubt it) than I would say you
should be able to remove it. However, before doing that surgery you
should probably run my testbench with the original code modified only
with my 'kj_*' input additions and run that sim but I'm confident that
it should pass sim as well. In any case, now you have a testbench
that exhaustively tests this code snippet which will either run to
completion indicating the code is safe to remove or it will stop
indicating the precise condition that really does trigger the 'if'
statement. And, assuming you archive the bench, you'll have the proof
necessary to show that the code was not needed in case there is ever a
question about why the code was removed.

Kevin Jennings

[Start of code]
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
entity count_saturate is
port (
kj_rst: in std_ulogic;
kj_cnt: in unsigned(31 downto 0);
clock: in std_ulogic := '0';
pulse_event_true: in std_ulogic := '0';
count: buffer unsigned(31 downto 0));
end count_saturate;
architecture rtl of count_saturate is
begin
process(clock)
begin
if rising_edge(clock) then
if (kj_rst = '1') then
count <= kj_cnt;
else
if (pulse_event_true = '1') then
if ((X"08000000" + count - (X"0000" & count(31 downto 16)))
< X"08000000") then
count <= (X"08000000" + count - (X"0000" & count(31
downto 16)));
else
count <= X"08000000";
end if;
else
count <= count - (X"0000" & count(31 downto 16));
end if;
end if;
end if;
end process;
end rtl;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity tb_count_saturate is
end tb_count_saturate;
architecture rtl of tb_count_saturate is
signal clock: std_ulogic := '0';
signal pulse_event_true: std_ulogic := '0';
signal count: unsigned(31 downto 0);
signal sim_complete: std_ulogic := '0';
signal kj_rst: std_ulogic;
signal kj_cnt: unsigned(31 downto 0);

begin
clock <= not(clock) and not(sim_complete) after 5 ns;
MAIN : process
begin
for i in 0 to 16#08000000# loop
kj_rst <= '1';
kj_cnt <= to_unsigned(i, kj_cnt'length);
pulse_event_true <= '0';
wait until falling_edge(clock);
assert (count = to_unsigned(i, kj_cnt'length)) report "OOPS!
Incorrect value for count" severity ERROR;
kj_rst <= '0';
pulse_event_true <= '1';
wait until falling_edge(clock);
assert (count = X"08000000") report "OOPS! Incorrect value for
count" severity ERROR;
if i mod 256 = 0 then
report "Loop #" & integer'image(i);
end if;
end loop;
sim_complete <= '1';
wait;
end process MAIN;

DUT : entity work.count_saturate port map(
kj_rst => kj_rst,
kj_cnt => kj_cnt,
clock => clock,
pulse_event_true => pulse_event_true,
count => count);
end rtl;
[End of code]

 

[JimLewis]

Hi Mark,
I think the key here is to put "_" in the literals to make them
readable.
It is X"0800_0000" and not X"8000_0000".

So if we ignore the decay temporarily. The count has to be greater
than or equal to X"F800_0000" to cause a roll over and for the if
statement to be false.

The following assignment looks odd to me since it is huge decay rather
than a saturation:
count <= X"0800_0000";

The shift is a by 16: x <= x - shift_right(x,16),

Best,
Jim

I'm having to do surgery on something a contractor left us.  One small problem was that he took a file with numeric_std already defined and used and then for his own additions added std_logic_unsigned (thanks SO much.)  Anyhow, I am having to carefully evaluate what he's doing so that I don't unnecessarily break something that is already working.  Not especially well commented either, so I'm having to infer intent from the code as well.

So, I run into a bit of code where he's putting in a little filter and I am having trouble trying to figure out what the hell he was getting at, because as far as I can tell, there's code that will never get executed due tothe way the math works.

[code snippet, encapsulated in ye olde clocked process]
if (pulse_event_true = '1') then
   if ((X"08000000" + count - (X"0000 & count(31 downto 16))) < X"08000000") then
       count <= (the above equation);
   else
       count <= X"08000000";
   end if;
else
   count <= count - (X"0000 & count(31 downto 16));
end if;
[/code]

Okay, so when there's a pulse, he adds a constant to the count, and otherwise it decays slowly.  No trouble there.  The problem I've got is thathe does that bounds check at the beginning to make sure he doesn't exceed 0x08000000 before he does the addition, otherwise he just caps out at 0x08000000.

The part I don't get is that the saturation limit is exactly the same as the constant he's adding.  By my reasoning, the count value could never exceed 0x08000000 except as a starting condition, and then we might have something large enough that it would wrap around 0xfffffffff and then trigger the top clause.  This is covered by the fact that the count has an asynchronous reset to 0, and has a synchronous reset to 0 (software controlled elsewhere).  Thus as far as I can tell, this count is going to stay at 0 until a pulse comes along, get set to 0x08000000, decay awhile until the nextpulse.  When another pulse comes along, there's no mathematical way the current count plus 0x08000000 will ever NOT be greater than or equal to 0x08000000 and thus just gets pegged back to the count.

It seems to be working adequately by all reports, but it kind of bugs me. And I'm taking out the std_logic_unsigned crap, so I can pretty easily convert the math to x <= x - shift_right(x,8), but there's that damned as-far-as-I-can-tell-non-executing-code that I have to decide whether to keepor just simplify to what is happening.

Any ideas folks?  Am I missing a case whereby C + f(t) is ever < C for all f(t) being non-negative?

Thanks for any responses.

Mark