Skip to content
GitLab
Explore
Sign in
Primary navigation
Search or go to…
Project
Alethe
Manage
Activity
Members
Labels
Plan
Issues
Issue boards
Milestones
Iterations
Code
Merge requests
Repository
Branches
Commits
Tags
Repository graph
Compare revisions
Locked files
Build
Pipelines
Jobs
Pipeline schedules
Test cases
Artifacts
Deploy
Releases
Model registry
Analyze
Model experiments
Help
Help
Support
GitLab documentation
Compare GitLab plans
Community forum
Contribute to GitLab
Provide feedback
Keyboard shortcuts
?
Snippets
Groups
Projects
Show more breadcrumbs
veriT
Alethe
Merge requests
!4
Add some bitvector rules
Code
Review changes
Check out branch
Download
Patches
Plain diff
Merged
Add some bitvector rules
devel/bb2024
into
master
Overview
0
Commits
9
Pipelines
2
Changes
1
Merged
Hans-Jörg
requested to merge
devel/bb2024
into
master
1 year ago
Overview
0
Commits
9
Pipelines
2
Changes
1
Expand
This moves
#31
forward!
Merge request reports
Viewing commit
f081142f
Prev
Next
Show latest version
1 file
+
50
−
42
Inline
Compare changes
Side-by-side
Inline
Show whitespace changes
Show one file at a time
f081142f
Bitblasting: adapt notation
· f081142f
Hans-Jörg
authored
1 year ago
spec/rule_list.tex
+
50
−
42
Options
@@ -1532,58 +1532,58 @@ form and the reordering of equalities.
\begin{RuleDescription}
{
bitblast
_
extract
}
\begin{AletheX}
$
i
$
.
&
\ctxsep
&
$
((
\
_\ \mathrm
{
extract
}
\
j
\
i
)
\
x
)
\simeq
(
\mathrm
{
bbterm
}
\
x
[
i
]
\ \ldots\
x
[
j
]
)
$
&
(
\currule
)
\\
$
i
$
.
&
\ctxsep
&
$
((
\
lsymb
{
extract
}
\
j
\
i
)
\
x
)
≈
(
\lsymb
{
bbT
}
\ \varphi
_
i
\ \ldots\
\varphi
_
j
)
$
&
(
\currule
)
\\
\end{AletheX}
Each term
$
x
[
i
]
$
corresponds to whether the
$
i
$
-th bit of
$
x
$
is true or not, which
will be represented via an application of the operator ``bit
\_
of'', i.e.,
$
((
\_\
bit
\_
of
\
i
)
\
x
)
$
, which has a Boolean return type.
%
The ``bbterm'' operator takes
$
n
$
Booleans and yields a bit-vector of size
$
n
$
where the least significant bit is 1 if the first argument 1 is true, 0
otherwise, and so on.
%
\noindent
where the formulas
$
\varphi
_
k
$
are
$
(
\lsymb
{
bitOf
}_
k
\
x
)
$
for
$
i
\leq
k
\leq
j
$
.
Alternatively, the rule may also be phrased as a ``short-circuiting'' of the
above when
$
x
$
is a
``bbterm''
application:
above when
$
x
$
is a
$
\lsymb
{
bbT
}$
application:
\medskip
\begin{AletheX}
$
i
$
.
&
\ctxsep
&
$
((
\
_\ \mathrm
{
extract
}
\
j
\
i
)
\
(
\
mathrm
{
bbterm
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
))
\simeq
(
\mathrm
{
bbterm
}
\
x
_
i
\ \ldots\
x
_
j
)
$
&
(
\currule
)
\\
$
i
$
.
&
\ctxsep
&
$
((
\
lsymb
{
extract
}
\
j
\
i
)
\
(
\
lsymb
{
bbT
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
))
≈
(
\lsymb
{
bbT
}
\
x
_
i
\ \ldots\
x
_
j
)
$
&
(
\currule
)
\\
\end{AletheX}
\noindent
This alternative is based on the validity of the equality
$$
(
\mathrm
{
bbterm
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
)[
i
]
\simeq
x
_
i
$$
for any bit-vector
$
x
$
of size
$
n
+
1
$
, where
$
0
\leq
i
\leq
n
$
.
\[
\lsymb
{
bitOf
}_
k
\
(
\lsymb
{
bbT
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
)
≈ x
_
k
\]
for any bit-vector
$
x
$
of size
$
n
+
1
$
, where
$
0
\leq
k
\leq
n
$
.
\end{RuleDescription}
\begin{RuleDescription}
{
bitblast
_
ult
}
\begin{AletheX}
$
i
$
.
&
\ctxsep
&
$
(
\
mathrm
{
bvult
}
\
x
\
y
)
\simeq
res
_{
n
-
1
}$
&
(
\currule
)
\\
$
i
$
.
&
\ctxsep
&
$
(
\
lsymb
{
bvult
}
\
x
\
y
)
≈
\mathrm
{
res
}
_{
n
-
1
}$
&
(
\currule
)
\\
\end{AletheX}
in which both
$
x
$
and
$
y
$
must have the same type
$
(
\
_\ \mathrm
{
BitVec
}
\
n
)
$
and, for
$
i
\geq
0
$
:
in which both
$
x
$
and
$
y
$
must have the same type
$
(
\
lsymb
{
BitVec
}
\
n
)
$
and, for
$
i
\geq
0
$
\[
\begin
{
array
}{
lcl
}
\mathrm
{
res
}_
0
&
=
&
\neg
x
[
0
]
\wedge
y
[
0
]
\\
\mathrm
{
res
}_{
i
+
1
}&
=
&
((
x
[
i
+
1
]
\simeq
y
[
i
+
1
])
\wedg
e
\mathrm
{
res
}_
i
)
\vee
(
\neg
x
[
i
+
1
]
\wedge
y
[
i
+
1
]
)
\mathrm
{
res
}_
0
&
=
&
\neg
(
\lsymb
{
bitOf
}_
0
\
x
)
\wedge
(
\lsymb
{
bitOf
}_
0
\
y
)
\\
\mathrm
{
res
}_{
i
+
1
}&
=
&
((
(
\lsymb
{
bitOf
}_{
i
+
1
}
\
x
)
≈
(
\lsymb
{
bitOf
}_{
i
+
1
}
\
y
))
\wedge
\mathrm
{
res
}_
i
)
\ve
e
(
\neg
(
\lsymb
{
bitOf
}_{
i
+
1
}
\
x
)
\wedge
(
\lsymb
{
bitOf
}_{
i
+
1
}
\
y
)
)
\end
{
array
}
\]
\noindent
Alternatively, the rule may also be phrased as a ``short-circuiting'' of the
above when
$
x
$
and
$
y
$
are ``
bbterm
'' applications. So given that
above when
$
x
$
and
$
y
$
are ``
$
\lsymb
{
bbT
}$
'' applications. So given that
\[
\begin
{
array
}{
lcl
}
x
&
=
&
(
\
mathrm
{
bbterm
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
)
\\
y
&
=
&
(
\
mathrm
{
bbterm
}
\
y
_
0
\ \ldots\
y
_
i
\ \ldots
\
y
_
j
\ \ldots\
y
_
n
)
\\
x
&
=
&
(
\
lsymb
{
bbT
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
)
\\
y
&
=
&
(
\
lsymb
{
bbT
}
\
y
_
0
\ \ldots\
y
_
i
\ \ldots
\
y
_
j
\ \ldots\
y
_
n
)
\\
\end
{
array
}
\]
then ``res'' can be defined, for
$
i
\geq
0
$
, as
then ``
$
\mathrm
{
res
}$
'' can be defined, for
$
i
\geq
0
$
, as
\[
\begin
{
array
}{
lcl
}
\mathrm
{
res
}_
0
&
=
&
\neg
x
_
0
\wedge
y
_
0
\\
\mathrm
{
res
}_{
i
+
1
}&
=
&
((
x
_{
i
+
1
}
\simeq
y
_{
i
+
1
}
)
\wedge
\mathrm
{
res
}_{
i
+
1
}&
=
&
((
x
_{
i
+
1
}
≈
y
_{
i
+
1
}
)
\wedge
\mathrm
{
res
}_
i
)
\vee
(
\neg
x
_{
i
+
1
}
\wedge
y
_{
i
+
1
}
)
\end
{
array
}
\]
@@ -1592,37 +1592,45 @@ then ``res'' can be defined, for $i \geq 0$, as
\begin{RuleDescription}
{
bitblast
_
add
}
\begin{AletheX}
$
i
$
.
&
\ctxsep
&
$
(
\mathrm
{
bvadd
}
\
x
\
y
)
\simeq
(
\mathrm
{
bbterm
}
\
(
x
[
0
]
\oplus
y
[
0
])
\oplus\mathrm
{
carry
}_
0
\ \ldots\
(
x
[
n
-
1
]
\oplus
y
[
n
-
1
])
\oplus\mathrm
{
carry
}_{
n
-
1
}
)
$
&
(
\currule
)
\\
$
i
$
.
&
\ctxsep
&
$
(
\lsymb
{
bvadd
}
\
x
\
y
)
≈ A
_
1
$
&
(
\currule
)
\\
\end{AletheX}
in which both
$
x
$
and
$
y
$
must have the same type
$
(
\_\ \mathrm
{
BitVec
}
\
n
)
$
and, for
$
i
\geq
0
$
:
\[
\begin
{
array
}{
lcl
}
\mathrm
{
carry
}_
0
&
=
&
\bot\\
\mathrm
{
carry
}_{
i
+
1
}&
=
&
(
x
[
i
]
\wedge
y
[
i
])
\vee
((
x
[
i
]
\oplus
y
[
i
])
\wedge
\mathrm
{
carry
}_
i
)
\end
{
array
}
\]
in which both
$
x
$
and
$
y
$
must have the same type
$
(
\lsymb
{
BitVec
}
\
n
)
$
.
The term ``
$
A
_
1
$
'' is
\begin{align*}
(
\lsymb
{
bbT
}
\;
&
(((
\lsymb
{
bitOf
}_{
0
}
\
x)
\,\lsymb
{
xor
}
\,
(
\lsymb
{
bitOf
}_{
0
}
\
y))
\,\lsymb
{
xor
}
\,\mathrm
{
carry
}_
0)
\\
&
(((
\lsymb
{
bitOf
}_{
1
}
\
x)
\,\lsymb
{
xor
}
\,
(
\lsymb
{
bitOf
}_{
1
}
\
y))
\,\lsymb
{
xor
}
\,\mathrm
{
carry
}_
1)
\\
&
\ldots
\\
&
(((
\lsymb
{
bitOf
}_{
n-1
}
\
x)
\,\lsymb
{
xor
}
\,
(
\lsymb
{
bitOf
}_{
n-1
}
\
y))
\,\lsymb
{
xor
}
\,\mathrm
{
carry
}_{
n-1
}
))
\end{align*}
and for
$
i
\geq
0
$
\[
\begin
{
array
}{
lcl
}
\mathrm
{
carry
}_
0
&
=
&
\bot\\
\mathrm
{
carry
}_{
i
+
1
}&
=
&
((
\lsymb
{
bitOf
}_{
i
}
\
x
)
\wedge
(
\lsymb
{
bitOf
}_{
i
}
\
y
))
\vee
(((
\lsymb
{
bitOf
}_{
i
}
\
x
)
\,\lsymb
{
xor
}
\,
(
\lsymb
{
bitOf
}_{
i
}
\
y
))
\wedge
\mathrm
{
carry
}_
i
)
\end
{
array
}
\]
\noindent
Alternatively, the rule may also be phrased as a ``short-circuiting'' of the
above when
$
x
$
and
$
y
$
are ``
bbterm
'' applications. So given that
above when
$
x
$
and
$
y
$
are ``
$
\lsymb
{
bbT
}$
'' applications. So given that
\[
\begin
{
array
}{
lcl
}
x
&
=
&
(
\
mathrm
{
bbterm
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
)
\\
y
&
=
&
(
\
mathrm
{
bbterm
}
\
y
_
0
\ \ldots\
y
_
i
\ \ldots
\
y
_
j
\ \ldots\
y
_
n
)
\\
x
&
=
&
(
\
lsymb
{
bbT
}
\
x
_
0
\ \ldots\
x
_
i
\ \ldots
\
x
_
j
\ \ldots\
x
_
n
)
\\
y
&
=
&
(
\
lsymb
{
bbT
}
\
y
_
0
\ \ldots\
y
_
i
\ \ldots
\
y
_
j
\ \ldots\
y
_
n
)
\\
\end
{
array
}
\]
then the rule can be alternatively phrased as
\begin{AletheX}
$
i
$
.
&
\ctxsep
&
$
(
\mathrm
{
bvadd
}
\
x
\
y
)
\simeq
(
\mathrm
{
bbterm
}
\
(
x
_
0
\oplus
y
_
0
)
\oplus\mathrm
{
carry
}_
0
\ \ldots\
(
x
_{
n
-
1
}
\oplus
y
_{
n
-
1
}
)
\oplus\mathrm
{
carry
}_{
n
-
1
}
)
$
&
(
\currule
)
\\
$
i
$
.
&
\ctxsep
&
$
(
\mathrm
{
bvadd
}
\
x
\
y
)
≈ A
_
2
$
&
(
\currule
)
\\
\end{AletheX}
with ``carry'' being defined, for
$
i
\geq
0
$
, as
with
$
A
_
2
:
=
(
\lsymb
{
bbT
}
\
(
x
_
0
\,\lsymb
{
xor
}
\,
y
_
0
)
\,\lsymb
{
xor
}
\,\mathrm
{
carry
}_
0
\ \ldots\
(
x
_{
n
-
1
}
\,\lsymb
{
xor
}
\,
y
_{
n
-
1
}
)
\,\lsymb
{
xor
}
\,\mathrm
{
carry
}_{
n
-
1
}
)
$
and
``
$
\mathrm
{
carry
}$
'' being defined, for
$
i
\geq
0
$
, as
\[
\begin
{
array
}{
lcl
}
\mathrm
{
carry
}_
0
&
=
&
\bot\\
\mathrm
{
carry
}_{
i
+
1
}&
=
&
(
x
_
i
\wedge
y
_
i
)
\vee
((
x
_
i
\
oplus
y
_
i
)
\wedge
\mathrm
{
carry
}_
i
)
\mathrm
{
carry
}_{
i
+
1
}&
=
&
(
x
_
i
\wedge
y
_
i
)
\vee
((
x
_
i
\
,\lsymb
{
xor
}
\,
y
_
i
)
\wedge
\mathrm
{
carry
}_
i
)
\end
{
array
}
\]
Loading