[libre-riscv-dev] [Bug 312] New: Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[libre-riscv-dev] [Bug 312] New: Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[bugzilla-daemon]

https://bugs.libre-soc.org/show_bug.cgi?id=312

            Bug ID: 312
           Summary: Formal Correctness Proof for CountZero needed
                    (basically PriorityEncoder)
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: PC
                OS: Mac OS
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Formal Verification
          Assignee: lkcl@lkcl.net
          Reporter: lkcl@lkcl.net
                CC: libre-riscv-dev@lists.libre-riscv.org
   NLnet milestone: ---

a formal correctness proof is needed for POWER countzero.py
the majority of that is actually a proof for PriorityEncoder,
with the rest taking care of niggles surrounding starting the
count from the MSB rather than the LSB, and 64/32 bit mode

the basis of the proof is a for-loop:

for i in range(64) - or 32
    with m.If(result == i):
        Assert(input[i] == 1)  -- assert that the bit in the input is a 1
        Assert(input & (1<<(i-1)-1) == 0   -- all bits below must be zero

this is basically the count done in a different way, however the important bit
about the proof is that it operates "inverted" from the actual computation.  it
starts from the *result* condition - result == i - and based on that result,
analyses (performs Assertions) on the *input*.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

[libre-riscv-dev] [Bug 312] Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[bugzilla-daemon]

https://bugs.libre-soc.org/show_bug.cgi?id=312

Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
    NLnet milestone|---                         |NLNet.2019.10.Formal
           See Also|                            |https://bugs.libre-soc.org/
                   |                            |show_bug.cgi?id=311

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

[libre-riscv-dev] [Bug 312] Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[bugzilla-daemon]

https://bugs.libre-soc.org/show_bug.cgi?id=312

Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
    parent task for|                            |198
  budget allocation|                            |

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

[libre-riscv-dev] [Bug 312] Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[bugzilla-daemon]

https://bugs.libre-soc.org/show_bug.cgi?id=312

Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 total budget (EUR)|0                           |150
  for completion of|                            |
       task and all|                            |
           subtasks|                            |

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

[libre-riscv-dev] [Bug 312] Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[bugzilla-daemon]

https://bugs.libre-soc.org/show_bug.cgi?id=312

--- Comment #1 from Luke Kenneth Casson Leighton <lkcl@lkcl.net> ---
this is now definitely a formal proof for PriorityEncoder because countzero.py
is not used, replaced by use of nmutil.clz.  however, nmutil.clz *is*
PriorityEncoder.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev

[libre-riscv-dev] [Bug 312] Formal Correctness Proof for CountZero needed (basically PriorityEncoder)

[bugzilla-daemon]

https://bugs.libre-soc.org/show_bug.cgi?id=312

Luke Kenneth Casson Leighton <lkcl@lkcl.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://bugs.libre-soc.org/
                   |                            |show_bug.cgi?id=326

-- 
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
libre-riscv-dev mailing list
libre-riscv-dev@lists.libre-riscv.org
http://lists.libre-riscv.org/mailman/listinfo/libre-riscv-dev