Benchmark
non-incremental/QF_ABV/brummayerbiere2/countbitstableuninit0128.smt2
Count bits pop(x) algorithm, table lookup method, buggy version
From the book "Hacker's delight" by Henry S. Warren, Jr., page 71
The algorithm precomputes pop(x) for x in range 0 to 255 and stores it
into a lookup table. However, one precomputed value is uninitialized.
We try to cross-check it with the obvious method of counting bits:
for (s = i = 0; i < BW; i++)
if (x & (1 << i))
s++;
Contributed by Robert Brummayer (robert.brummayer@gmail.com)
| Benchmark |
|---|
| Size | 33184 |
| Compressed Size | 2292 |
| License |
Creative Commons Attribution 4.0 International
(CC-BY-4.0)
|
| Category | crafted |
| First Occurrence | 2008-07-07 |
| Generated By | — |
| Generated On | — |
| Generator | — |
| Dolmen OK | 1 |
| strict Dolmen OK | 1 |
| check-sat calls | 1 |
| Status | sat |
| Inferred Status | sat |
| Size | 33176 |
| Compressed Size | 2308 |
| Max. Term Depth | 259 |
| Asserts | 1 |
| Declared Functions | 0 |
| Declared Constants | 2 |
| Declared Sorts | 0 |
| Defined Functions | 0 |
| Defined Recursive Functions | 0 |
| Defined Sorts | 0 |
| Constants | 0 |
| Declared Datatypes | 0 |
Symbols
ite | 257 |
not | 1 |
= | 258 |
let | 141 |
concat | 16 |
extract | 16 |
bvnot | 129 |
bvand | 128 |
bvadd | 143 |
bvshl | 128 |
bvlshr | 15 |
zero_extend | 128 |
select | 16 |
store | 255 |
| | | |
Evaluations
| Evaluation |
Rating |
Solver |
Variant |
Result |
Wallclock |
CPU Time |
|
SMT-COMP 2010
|
|
Boolector |
Boolector 1.2 |
sat ✅
|
14.70000
|
—
|
| |
CVC3 |
CVC3 2.3 |
sat ✅
|
76.50000
|
—
|
|
SMT Evaluation 2013
|
|
Boolector |
Boolector-1.5.118-SMT-EVAL-2013 default |
sat ✅
|
1.59343
|
—
|
| |
|
Boolector-SMT-COMP-2011 default |
sat ✅
|
30.82210
|
—
|
| |
|
Boolector-SMT-COMP-2012 default |
sat ✅
|
4.11752
|
—
|
| |
CVC3 |
CVC3-SMT-COMP-2010 default |
sat ✅
|
49.70430
|
—
|
| |
|
CVC3-SMT-COMP-2011 default |
sat ✅
|
50.06510
|
—
|
| |
|
CVC3-SMT-COMP-2012 default |
sat ✅
|
51.19010
|
—
|
| |
CVC4 |
CVC4-SMT-COMP-2012-Resubmission default |
sat ✅
|
663.58500
|
—
|
| |
|
CVC4-SMT-EVAL-2013 default |
sat ✅
|
370.26700
|
—
|
| |
MathSAT |
MathSAT5-5.2.6-SMT-EVAL-2013 default |
sat ✅
|
15.58220
|
—
|
| |
|
MathSAT5-SMT-COMP-2011 default |
sat ✅
|
668.36600
|
—
|
| |
|
MathSAT5-SMT-COMP-2012 default |
sat ✅
|
319.78300
|
—
|
| |
SONOLAR |
SONOLAR-2013-05-15-SMT-EVAL-2013 default |
sat ✅
|
1.52516
|
—
|
| |
|
SONOLAR-SMT-COMP-2011 default |
sat ✅
|
11.23310
|
—
|
| |
|
SONOLAR-SMT-COMP-2012 default |
sat ✅
|
23.92580
|
—
|
| |
Tiffany de Wintermonte |
TdW-SMT-COMP-2012 default |
sat ✅
|
1.52574
|
—
|
| |
Z3 |
Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-EVAL-2013 default |
sat ✅
|
484.08200
|
—
|
| |
|
Z3-SMT-COMP-2011 default |
unknown ❌
|
—
|
—
|
|
SMT-COMP 2014
|
0.14 (6/7) |
Boolector |
Boolector boolectord |
sat ✅
|
1.13188
|
1.12183
|
| |
|
Boolector boolectorj |
sat ✅
|
1.08152
|
1.07883
|
| |
CVC4 |
CVC4 f7118b2 default |
sat ✅
|
135.55700
|
135.53700
|
| |
Kleaver |
Kleaver-indie-more-typed kleaver_indie_1 |
unknown ❌
|
0.02109
|
0.02000
|
| |
|
Kleaver-indie-more-typed kleaver_portfolio |
unknown ❌
|
0.04457
|
0.03499
|
| |
MathSAT |
MathSAT-5.2.12-Main default |
sat ✅
|
17.79630
|
17.79130
|
| |
SONOLAR |
sonolar_smtcomp-2014 default |
sat ✅
|
5.80261
|
5.79012
|
| |
Yices2 |
Yices-2.2.1-smtcomp2014 default |
sat ✅
|
1.71117
|
1.70274
|
| |
Z3 |
Z3-4.3.2.a054b099c1d6-x64-debian-6.0.6-SMT-COMP-2014 default |
sat ✅
|
212.52800
|
212.57800
|
|
SMT-COMP 2015
|
|
Boolector |
Boolector SMT15 QF_AUFBV final boolector_qf_aufbv |
sat ✅
|
4.53952
|
4.54031
|
| |
CVC4 |
CVC4-master-2015-06-15-9b32405-main default |
sat ✅
|
1185.02000
|
1185.39000
|
| |
|
CVC4-experimental-2015-06-15-ff5745a-main default |
sat ✅
|
65.55190
|
65.56600
|
| |
MathSAT |
MathSat 5.3.6 main smtcomp2015_main |
sat ✅
|
21.70370
|
21.71270
|
| |
Yices2 |
Yices default |
sat ✅
|
1.15992
|
1.15882
|
| |
Z3 |
z3 4.4.0 default |
sat ✅
|
40.67660
|
40.69380
|
|
SMT-COMP 2016
|
|
Boolector |
Boolector boolector |
sat ✅
|
2.30042
|
2.30200
|
| |
CVC4 |
CVC4-master-2016-05-27-cfef263-main default |
sat ✅
|
70.47760
|
69.19940
|
| |
MathSAT |
mathsat-5.3.11-linux-x86_64-Main default |
sat ✅
|
45.75370
|
45.78130
|
| |
Yices2 |
Yices-2.4.2 default |
sat ✅
|
1.14854
|
1.14926
|
| |
Z3 |
z3-4.4.1 default |
sat ✅
|
0.54312
|
0.54471
|
|
SMT-COMP 2017
|
|
Boolector |
Boolector SMT17 final boolector |
sat ✅
|
1.64768
|
1.64703
|
| |
CVC4 |
CVC4-smtcomp2017-main default |
sat ✅
|
10.01360
|
10.01240
|
| |
MathSAT |
mathsat-5.4.1-linux-x86_64-Main default |
sat ✅
|
24.28150
|
24.28250
|
| |
Yices2 |
Yices2-Main default |
sat ✅
|
1.11544
|
1.11482
|
| |
Z3 |
z3-4.5.0 default |
sat ✅
|
38.75090
|
38.72860
|
|
SMT-COMP 2018
|
0.20 (4/5) |
Boolector |
Boolector_default |
sat ✅
|
3.01394
|
3.01380
|
| |
CVC4 |
master-2018-06-10-b19c840-competition-default_default |
sat ✅
|
5.87591
|
5.87548
|
| |
MathSAT |
mathsat-5.5.2-linux-x86_64-Main_default |
unknown ❌
|
81.35890
|
81.35790
|
| |
Yices2 |
Yices 2.6.0_default |
sat ✅
|
6.02168
|
6.02090
|
| |
Z3 |
z3-4.7.1_default |
sat ✅
|
794.67600
|
794.60500
|
|
SMT-COMP 2024
|
0.25 (3/4) |
Bitwuzla |
Bitwuzla |
sat ✅
|
4.36875
|
4.26386
|
| |
cvc5 |
cvc5 |
sat ✅
|
14.67641
|
14.55661
|
| |
SMTInterpol |
SMTInterpol |
unknown ❌
|
1201.76490
|
1323.86857
|
| |
Yices2 |
Yices2 |
sat ✅
|
2.63911
|
2.53965
|