cprover
Loading...
Searching...
No Matches
boolbv_add_sub.cpp
Go to the documentation of this file.
1/*******************************************************************\
2
3Module:
4
5Author: Daniel Kroening, kroening@kroening.com
6
7\*******************************************************************/
8
9#include "boolbv.h"
10
12#include <util/invariant.h>
13
15
17{
19 expr.id() == ID_plus || expr.id() == ID_minus ||
20 expr.id() == "no-overflow-plus" || expr.id() == "no-overflow-minus");
21
22 const typet &type = expr.type();
23
24 if(
25 type.id() != ID_unsignedbv && type.id() != ID_signedbv &&
26 type.id() != ID_fixedbv && type.id() != ID_floatbv &&
27 type.id() != ID_range && type.id() != ID_complex)
28 {
29 return conversion_failed(expr);
30 }
31
32 std::size_t width=boolbv_width(type);
33
34 const exprt::operandst &operands=expr.operands();
35
37 !operands.empty(),
38 "operator " + expr.id_string() + " takes at least one operand");
39
40 const exprt &op0 = to_multi_ary_expr(expr).op0();
42 op0.type() == type, "add/sub with mixed types:\n" + expr.pretty());
43
44 bvt bv = convert_bv(op0, width);
45
46 bool subtract=(expr.id()==ID_minus ||
47 expr.id()=="no-overflow-minus");
48
49 bool no_overflow=(expr.id()=="no-overflow-plus" ||
50 expr.id()=="no-overflow-minus");
51
52 typet arithmetic_type =
53 type.id() == ID_complex ? to_type_with_subtype(type).subtype() : type;
54
56 (arithmetic_type.id()==ID_signedbv ||
57 arithmetic_type.id()==ID_fixedbv)?bv_utilst::representationt::SIGNED:
59
60 for(exprt::operandst::const_iterator
61 it=operands.begin()+1;
62 it!=operands.end(); it++)
63 {
65 it->type() == type, "add/sub with mixed types:\n" + expr.pretty());
66
67 const bvt &op = convert_bv(*it, width);
68
69 if(type.id() == ID_complex)
70 {
71 std::size_t sub_width =
72 boolbv_width(to_type_with_subtype(type).subtype());
73
75 sub_width != 0, "complex elements shall have nonzero bit width");
77 width % sub_width == 0,
78 "total complex bit width shall be a multiple of the element bit width");
79
80 std::size_t size=width/sub_width;
81 bv.resize(width);
82
83 for(std::size_t i=0; i<size; i++)
84 {
85 bvt tmp_op;
86 tmp_op.resize(sub_width);
87
88 for(std::size_t j=0; j<tmp_op.size(); j++)
89 {
90 const std::size_t index = i * sub_width + j;
91 INVARIANT(index < op.size(), "bit index shall be within bounds");
92 tmp_op[j] = op[index];
93 }
94
95 bvt tmp_result;
96 tmp_result.resize(sub_width);
97
98 for(std::size_t j=0; j<tmp_result.size(); j++)
99 {
100 const std::size_t index = i * sub_width + j;
101 INVARIANT(index < bv.size(), "bit index shall be within bounds");
102 tmp_result[j] = bv[index];
103 }
104
105 if(to_type_with_subtype(type).subtype().id() == ID_floatbv)
106 {
107 // needs to change due to rounding mode
108 float_utilst float_utils(
109 prop, to_floatbv_type(to_type_with_subtype(type).subtype()));
110 tmp_result=float_utils.add_sub(tmp_result, tmp_op, subtract);
111 }
112 else
113 tmp_result=bv_utils.add_sub(tmp_result, tmp_op, subtract);
114
115 INVARIANT(
116 tmp_result.size() == sub_width,
117 "applying the add/sub operation shall not change the bitwidth");
118
119 for(std::size_t j=0; j<tmp_result.size(); j++)
120 {
121 const std::size_t index = i * sub_width + j;
122 INVARIANT(index < bv.size(), "bit index shall be within bounds");
123 bv[index] = tmp_result[j];
124 }
125 }
126 }
127 else if(type.id()==ID_floatbv)
128 {
129 // needs to change due to rounding mode
130 float_utilst float_utils(prop, to_floatbv_type(arithmetic_type));
131 bv=float_utils.add_sub(bv, op, subtract);
132 }
133 else if(no_overflow)
134 bv=bv_utils.add_sub_no_overflow(bv, op, subtract, rep);
135 else
136 bv=bv_utils.add_sub(bv, op, subtract);
137 }
138
139 return bv;
140}
141
143{
145 expr.id() == ID_saturating_minus || expr.id() == ID_saturating_plus);
146
147 const typet &type = expr.type();
148
149 if(
150 type.id() != ID_unsignedbv && type.id() != ID_signedbv &&
151 type.id() != ID_fixedbv && type.id() != ID_complex)
152 {
153 return conversion_failed(expr);
154 }
155
156 std::size_t width = boolbv_width(type);
157
159 expr.lhs().type() == type && expr.rhs().type() == type,
160 "saturating add/sub with mixed types:\n" + expr.pretty());
161
162 const bool subtract = expr.id() == ID_saturating_minus;
163
164 typet arithmetic_type =
165 type.id() == ID_complex ? to_type_with_subtype(type).subtype() : type;
166
168 (arithmetic_type.id() == ID_signedbv || arithmetic_type.id() == ID_fixedbv)
171
172 bvt bv = convert_bv(expr.lhs(), width);
173 const bvt &op = convert_bv(expr.rhs(), width);
174
175 if(type.id() != ID_complex)
176 return bv_utils.saturating_add_sub(bv, op, subtract, rep);
177
178 std::size_t sub_width = boolbv_width(to_type_with_subtype(type).subtype());
179
180 INVARIANT(sub_width != 0, "complex elements shall have nonzero bit width");
181 INVARIANT(
182 width % sub_width == 0,
183 "total complex bit width shall be a multiple of the element bit width");
184
185 std::size_t size = width / sub_width;
186
187 for(std::size_t i = 0; i < size; i++)
188 {
189 bvt tmp_op;
190 tmp_op.resize(sub_width);
191
192 for(std::size_t j = 0; j < tmp_op.size(); j++)
193 {
194 const std::size_t index = i * sub_width + j;
195 INVARIANT(index < op.size(), "bit index shall be within bounds");
196 tmp_op[j] = op[index];
197 }
198
199 bvt tmp_result;
200 tmp_result.resize(sub_width);
201
202 for(std::size_t j = 0; j < tmp_result.size(); j++)
203 {
204 const std::size_t index = i * sub_width + j;
205 INVARIANT(index < bv.size(), "bit index shall be within bounds");
206 tmp_result[j] = bv[index];
207 }
208
209 tmp_result = bv_utils.saturating_add_sub(tmp_result, tmp_op, subtract, rep);
210
211 INVARIANT(
212 tmp_result.size() == sub_width,
213 "applying the add/sub operation shall not change the bitwidth");
214
215 for(std::size_t j = 0; j < tmp_result.size(); j++)
216 {
217 const std::size_t index = i * sub_width + j;
218 INVARIANT(index < bv.size(), "bit index shall be within bounds");
219 bv[index] = tmp_result[j];
220 }
221 }
222
223 return bv;
224}
Pre-defined bitvector types.
const floatbv_typet & to_floatbv_type(const typet &type)
Cast a typet to a floatbv_typet.
A base class for binary expressions.
Definition std_expr.h:583
exprt & lhs()
Definition std_expr.h:613
exprt & rhs()
Definition std_expr.h:623
virtual bvt convert_add_sub(const exprt &expr)
virtual const bvt & convert_bv(const exprt &expr, const optionalt< std::size_t > expected_width={})
Convert expression to vector of literalts, using an internal cache to speed up conversion if availabl...
Definition boolbv.cpp:38
bv_utilst bv_utils
Definition boolbv.h:114
virtual bvt convert_saturating_add_sub(const binary_exprt &expr)
bvt conversion_failed(const exprt &expr)
Print that the expression of x has failed conversion, then return a vector of x's width.
Definition boolbv.cpp:82
virtual std::size_t boolbv_width(const typet &type) const
Definition boolbv.h:99
bvt add_sub_no_overflow(const bvt &op0, const bvt &op1, bool subtract, representationt rep)
Definition bv_utils.cpp:327
bvt add_sub(const bvt &op0, const bvt &op1, bool subtract)
Definition bv_utils.cpp:336
representationt
Definition bv_utils.h:29
bvt saturating_add_sub(const bvt &op0, const bvt &op1, bool subtract, representationt rep)
Definition bv_utils.cpp:357
Base class for all expressions.
Definition expr.h:56
std::vector< exprt > operandst
Definition expr.h:58
typet & type()
Return the type of the expression.
Definition expr.h:84
operandst & operands()
Definition expr.h:94
virtual bvt add_sub(const bvt &src1, const bvt &src2, bool subtract)
std::string pretty(unsigned indent=0, unsigned max_indent=0) const
Definition irep.cpp:490
const std::string & id_string() const
Definition irep.h:399
const irep_idt & id() const
Definition irep.h:396
exprt & op0()
Definition std_expr.h:877
const typet & subtype() const
Definition type.h:154
The type of an expression, extends irept.
Definition type.h:29
std::vector< literalt > bvt
Definition literal.h:201
#define DATA_INVARIANT(CONDITION, REASON)
This condition should be used to document that assumptions that are made on goto_functions,...
Definition invariant.h:534
#define PRECONDITION(CONDITION)
Definition invariant.h:463
#define INVARIANT(CONDITION, REASON)
This macro uses the wrapper function 'invariant_violated_string'.
Definition invariant.h:423
const multi_ary_exprt & to_multi_ary_expr(const exprt &expr)
Cast an exprt to a multi_ary_exprt.
Definition std_expr.h:932
const type_with_subtypet & to_type_with_subtype(const typet &type)
Definition type.h:175