263 lines
20 KiB
HTML
263 lines
20 KiB
HTML
<html>
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
|
|
<title>Introduction</title>
|
|
<link rel="stylesheet" href="boostbook.css" type="text/css">
|
|
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
|
|
<link rel="home" href="index.html" title="Safe Numerics">
|
|
<link rel="up" href="index.html" title="Safe Numerics">
|
|
<link rel="prev" href="index.html" title="Safe Numerics">
|
|
<link rel="next" href="tutorial.html" title="Tutorial and Motivating Examples">
|
|
</head>
|
|
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
|
|
<table cellpadding="2" width="100%"><tr>
|
|
<td valign="top"><img href="index.html" height="164px" src="pre-boost.jpg" alt="Library Documentation Index"></td>
|
|
<td><h2>Safe Numerics</h2></td>
|
|
</tr></table>
|
|
<div class="spirit-nav">
|
|
<a accesskey="p" href="index.html"><img src="images/prev.png" alt="Prev"></a><a accesskey="u" href="index.html"><img src="images/up.png" alt="Up"></a><a accesskey="h" href="index.html"><img src="images/home.png" alt="Home"></a><a accesskey="n" href="tutorial.html"><img src="images/next.png" alt="Next"></a>
|
|
</div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
|
|
<a name="safe_numerics.introduction"></a>Introduction</h2></div></div></div>
|
|
<div class="toc"><dl class="toc">
|
|
<dt><span class="section"><a href="introduction.html#safe_numerics.introduction.problem">Problem</a></span></dt>
|
|
<dt><span class="section"><a href="introduction.html#safe_numerics.introduction.solution">Solution</a></span></dt>
|
|
<dt><span class="section"><a href="introduction.html#safe_numerics.introduction.implementation">How It Works</a></span></dt>
|
|
<dt><span class="section"><a href="introduction.html#safe_numerics.introduction.additional_features">Additional Features</a></span></dt>
|
|
<dt><span class="section"><a href="introduction.html#safe_numerics.introduction.requirements">Requirements</a></span></dt>
|
|
<dt><span class="section"><a href="introduction.html#safe_numerics.introduction.scope">Scope</a></span></dt>
|
|
</dl></div>
|
|
<p>This library is intended as a drop-in replacement for all built-in
|
|
integer types in any program which must:</p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|
<li class="listitem"><p>be demonstrably and verifiably correct.</p></li>
|
|
<li class="listitem"><p>detect every user error such as input, assignment, etc.</p></li>
|
|
<li class="listitem"><p>be efficient as possible subject to the constraints above.</p></li>
|
|
</ul></div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h3 class="title">
|
|
<a name="safe_numerics.introduction.problem"></a>Problem</h3></div></div></div>
|
|
<p>Arithmetic operations in C/C++ are NOT guaranteed to yield a correct
|
|
mathematical result. This feature is inherited from the early days of C.
|
|
The behavior of <code class="computeroutput">int</code>, <code class="computeroutput">unsigned int</code> and others
|
|
were designed to map closely to the underlying hardware. Computer hardware
|
|
implements these types as a fixed number of bits. When the result of
|
|
arithmetic operations exceeds this number of bits, the result will not be
|
|
arithmetically correct. The following example illustrates just one example
|
|
where this causes problems.</p>
|
|
<pre class="programlisting"><span class="keyword">int</span> <span class="identifier">f</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">x</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">y</span><span class="special">)</span><span class="special">{</span>
|
|
<span class="comment">// this returns an invalid result for some legal values of x and y !</span>
|
|
<span class="keyword">return</span> <span class="identifier">x</span> <span class="special">+</span> <span class="identifier">y</span><span class="special">;</span>
|
|
<span class="special">}</span>
|
|
</pre>
|
|
<p>It is incumbent upon the C/C++ programmer to guarantee that this
|
|
behavior does not result in incorrect or unexpected operation of the
|
|
program. There are no language facilities which implement such a
|
|
guarantee. A programmer needs to examine each expression individually to
|
|
know that his program will not return an invalid result. There are a
|
|
number of ways to do this. In the above instance,
|
|
[<a class="citation" href="bibliography.html#seacord3"><span class="citation">INT32-C</span></a>] seems to recommend the following
|
|
approach:</p>
|
|
<pre class="programlisting"><span class="keyword">int</span> <span class="identifier">f</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">x</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">y</span><span class="special">)</span><span class="special">{</span>
|
|
<span class="keyword">if</span> <span class="special">(</span><span class="special">(</span><span class="special">(</span><span class="identifier">y</span> <span class="special">></span> <span class="number">0</span><span class="special">)</span> <span class="special">&&</span> <span class="special">(</span><span class="identifier">x</span> <span class="special">></span> <span class="special">(</span><span class="identifier">INT_MAX</span> <span class="special">-</span> <span class="identifier">y</span><span class="special">)</span><span class="special">)</span><span class="special">)</span>
|
|
<span class="special">||</span> <span class="special">(</span><span class="special">(</span><span class="identifier">y</span> <span class="special"><</span> <span class="number">0</span><span class="special">)</span> <span class="special">&&</span> <span class="special">(</span><span class="identifier">x</span> <span class="special"><</span> <span class="special">(</span><span class="identifier">INT_MIN</span> <span class="special">-</span> <span class="identifier">y</span><span class="special">)</span><span class="special">)</span><span class="special">)</span><span class="special">)</span> <span class="special">{</span>
|
|
<span class="comment">/* Handle error */</span>
|
|
<span class="special">}</span>
|
|
<span class="keyword">return</span> <span class="identifier">x</span> <span class="special">+</span> <span class="identifier">y</span><span class="special">;</span>
|
|
<span class="special">}</span>
|
|
</pre>
|
|
<p>This will indeed trap the error. However, it would be tedious and
|
|
laborious for a programmer to alter his code in this manner. Altering code
|
|
in this way for all arithmetic operations would likely render the code
|
|
unreadable and add another source of potential programming errors. This
|
|
approach is clearly not functional when the expression is even a little
|
|
more complex as is shown in the following example.</p>
|
|
<pre class="programlisting"><span class="keyword">int</span> <span class="identifier">f</span><span class="special">(</span><span class="keyword">int</span> <span class="identifier">x</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">y</span><span class="special">,</span> <span class="keyword">int</span> <span class="identifier">z</span><span class="special">)</span><span class="special">{</span>
|
|
<span class="comment">// this returns an invalid result for some legal values of x and y !</span>
|
|
<span class="keyword">return</span> <span class="identifier">x</span> <span class="special">+</span> <span class="identifier">y</span> <span class="special">*</span> <span class="identifier">z</span><span class="special">;</span>
|
|
<span class="special">}</span>
|
|
</pre>
|
|
<p>This example addresses only the problem of undefined/erroneous
|
|
behavior related to overflow of the addition operation as applied to the
|
|
type <code class="computeroutput">int</code>. Similar problems occur with other built-in integer
|
|
types such as <code class="computeroutput">unsigned</code>, <code class="computeroutput">long</code>, etc. And it also
|
|
applies to other operations such as subtraction, multiplication etc. .
|
|
C/C++ often automatically and silently converts some integer types to
|
|
others in the course of implementing binary operations. Sometimes such
|
|
conversions can silently change arithmetic values which inject errors. The
|
|
C/C++ standards designate some behavior such as right shifting a negative
|
|
number as "implementation defined behavior". These days machines usually
|
|
do what the programmer expects - but such behavior is not guaranteed.
|
|
Relying on such behavior will create a program which cannot be guaranteed
|
|
to be portable. And then there is undefined behavior. In this case,
|
|
compiler writer is under no obligation to do anything in particular.
|
|
Sometimes this will unexpectedly break the program. At the very least, the
|
|
program is rendered non-portable. Finally there is the case of behavior
|
|
that is arithmetically wrong to begin with - for example divide by zero.
|
|
Some runtime environments will just terminate the program, others may
|
|
throw some sort of exception. In any case, the execution has failed in a
|
|
manner from which there is no recovery.</p>
|
|
<p>All of the above conditions are obstacles to creation of a program
|
|
which will never fail. The Safe Numerics Library addresses all of these
|
|
conditions, at least as far as integer operations are concerned.</p>
|
|
<p>Since the problems and their solution are similar, we'll confine the
|
|
current discussion to just the one example shown above.</p>
|
|
</div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h3 class="title">
|
|
<a name="safe_numerics.introduction.solution"></a>Solution</h3></div></div></div>
|
|
<p>This library implements special versions of <code class="computeroutput">int</code>,
|
|
<code class="computeroutput">unsigned</code>, etc. which behave exactly like the original ones
|
|
<span class="bold"><strong>except</strong></span> that the results of these
|
|
operations are guaranteed to be either to be arithmetically correct or
|
|
invoke an error. Using this library, the above example would be rendered
|
|
as:</p>
|
|
<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">safe_numerics</span><span class="special">/</span><span class="identifier">safe_integer</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span>
|
|
<span class="keyword">using</span> <span class="keyword">namespace</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">numeric</span><span class="special">;</span>
|
|
<span class="identifier">safe</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">f</span><span class="special">(</span><span class="identifier">safe</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">x</span><span class="special">,</span> <span class="identifier">safe</span><span class="special"><</span><span class="keyword">int</span><span class="special">></span> <span class="identifier">y</span><span class="special">)</span><span class="special">{</span>
|
|
<span class="keyword">return</span> <span class="identifier">x</span> <span class="special">+</span> <span class="identifier">y</span><span class="special">;</span> <span class="comment">// throw exception if correct result cannot be returned</span>
|
|
<span class="special">}</span>
|
|
</pre>
|
|
<div class="note"><table border="0" summary="Note">
|
|
<tr>
|
|
<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="images/note.png"></td>
|
|
<th align="left">Note</th>
|
|
</tr>
|
|
<tr><td align="left" valign="top"><p>Library code in this document resides in the namespace
|
|
<code class="computeroutput">boost::numeric</code>. This namespace has generally been
|
|
eliminated from text, code and examples in order to improve
|
|
readability of the text.</p></td></tr>
|
|
</table></div>
|
|
<p>The addition expression is checked at runtime or (if possible) at
|
|
compile time to trap any possible errors resulting in incorrect arithmetic
|
|
behavior. Arithmetic expressions will not produce an erroneous result.
|
|
Instead, one and only one of the following is guaranteed to occur.</p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|
<li class="listitem"><p>the expression will yield the correct mathematical
|
|
result</p></li>
|
|
<li class="listitem"><p>the expression will emit a compilation error.</p></li>
|
|
<li class="listitem"><p>the expression will invoke a runtime exception.</p></li>
|
|
</ul></div>
|
|
<p>In other words, the <span class="bold"><strong>library absolutely
|
|
guarantees that no integer arithmetic expression will yield incorrect
|
|
results</strong></span>.</p>
|
|
</div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h3 class="title">
|
|
<a name="safe_numerics.introduction.implementation"></a>How It Works</h3></div></div></div>
|
|
<p>The library implements special versions of <code class="computeroutput">int</code>,
|
|
<code class="computeroutput">unsigned</code>, etc. Named <code class="computeroutput">safe<int></code>,
|
|
<code class="computeroutput">safe<unsigned int></code> etc. These behave exactly like the
|
|
underlying types <span class="bold"><strong>except</strong></span> that expressions
|
|
using these types fulfill the above guarantee. These "safe" types are
|
|
meant to be "drop-in" replacements for the built-in types of the same
|
|
name. So things which are legal - such as assignment of a
|
|
<code class="computeroutput">signed</code> to <code class="computeroutput">unsigned</code> value - are not trapped at
|
|
compile time as they are legal C/C++ code. Instead, they are checked at
|
|
runtime to trap the case where this (legal) operation would lead to an
|
|
arithmetically incorrect result.</p>
|
|
<p>Note that the library addresses arithmetical errors generated by
|
|
straightforward C/C++ expressions. Some of these arithmetic errors are
|
|
defined as conforming to the C/C++ standards while others are not. So
|
|
characterizing this library as only addressing undefined behavior of C/C++
|
|
numeric expressions would be misleading.</p>
|
|
<p>Facilities particular to C++14 are employed to minimize any runtime
|
|
overhead. In many cases there is no runtime overhead at all. In other
|
|
cases, a program using the library can be slightly altered to achieve the
|
|
above guarantee without any runtime overhead.</p>
|
|
</div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h3 class="title">
|
|
<a name="safe_numerics.introduction.additional_features"></a>Additional Features</h3></div></div></div>
|
|
<p>Operation of safe types is determined by template parameters which
|
|
specify a pair of <a class="link" href="promotion_policies.html" title="Promotion Policies">policy
|
|
classes</a> which specify the behavior for type promotion and error
|
|
handling. In addition to the usage serving as a drop-in replacement for
|
|
standard integer types, users of the library can:</p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|
<li class="listitem">
|
|
<p>Select or define an exception policy class to specify handling
|
|
of exceptions.</p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; ">
|
|
<li class="listitem"><p>Throw exception on runtime, trap at compile time if
|
|
possible.</p></li>
|
|
<li class="listitem"><p>Trap at compile time all operations which could possibly
|
|
fail at runtime.</p></li>
|
|
<li class="listitem"><p>Specify custom functions which should be called in case
|
|
errors are detected at runtime.</p></li>
|
|
</ul></div>
|
|
</li>
|
|
<li class="listitem">
|
|
<p>Select or define a promotion policy class to alter the C/C++
|
|
type promotion rules. This can be used to </p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: circle; ">
|
|
<li class="listitem"><p>Use C/C++ native type promotion rules so that, except
|
|
for throwing/trapping of exceptions on operations resulting in
|
|
incorrect arithmetic behavior, programs will operate
|
|
identically when using/not using safe types. This might be
|
|
used if safe types are only enabled during debug and
|
|
testing.</p></li>
|
|
<li class="listitem"><p>Replace C/C++ native promotion rules with ones which are
|
|
arithmetically equivalent but minimize the need for runtime
|
|
checking of arithmetic results. Such a policy will effectively
|
|
change the semantics of a C++ program. It's not really C++ any
|
|
more. The program cannot be expected to function the same as
|
|
when normal integer types are used.</p></li>
|
|
<li class="listitem"><p>Replace C/C++ native promotion rules with ones which
|
|
emulate other machine architectures. This is designed to
|
|
permit the testing of C/C++ code destined to be run on another
|
|
machine on one's development platform. Such a situation often
|
|
occurs while developing code for embedded systems.</p></li>
|
|
</ul></div>
|
|
</li>
|
|
<li class="listitem"><p>Enforce other program requirements using bounded integer
|
|
types. The library includes the types for ranges and literals.
|
|
Operations which violate these requirements will be trapped at
|
|
either compile time or runtime and not silently return invalid
|
|
values. These types can be used to improve program correctness and
|
|
performance.</p></li>
|
|
</ul></div>
|
|
</div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h3 class="title">
|
|
<a name="safe_numerics.introduction.requirements"></a>Requirements</h3></div></div></div>
|
|
<p>This library is composed entirely of C++ Headers. It requires a
|
|
compiler compatible with the C++14 standard.</p>
|
|
<p>The following Boost Libraries must be installed in order to use this
|
|
library</p>
|
|
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
|
|
<li class="listitem"><p>mp11</p></li>
|
|
<li class="listitem"><p>integer</p></li>
|
|
<li class="listitem"><p>config</p></li>
|
|
<li class="listitem"><p>tribool</p></li>
|
|
<li class="listitem"><p>enable_if</p></li>
|
|
</ul></div>
|
|
<p>The Safe Numerics library is delivered with an exhaustive
|
|
suite of test programs.</p>
|
|
</div>
|
|
<div class="section">
|
|
<div class="titlepage"><div><div><h3 class="title">
|
|
<a name="safe_numerics.introduction.scope"></a>Scope</h3></div></div></div>
|
|
<p>This library currently applies only to built-in integer types.
|
|
Analogous issues arise for floating point types but they are not currently
|
|
addressed by this version of the library. User or library defined types
|
|
such as arbitrary precision integers can also have this problem. Extension
|
|
of this library to these other types is not currently under development
|
|
but may be addressed in the future. This is one reason why the library
|
|
name is "safe numeric" rather than "safe integer" library.</p>
|
|
</div>
|
|
</div>
|
|
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
|
|
<td align="left"></td>
|
|
<td align="right"><div class="copyright-footer">Copyright © 2012-2018 Robert Ramey<p><a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">Subject to Boost
|
|
Software License</a></p>
|
|
</div></td>
|
|
</tr></table>
|
|
<hr>
|
|
<div class="spirit-nav">
|
|
<a accesskey="p" href="index.html"><img src="images/prev.png" alt="Prev"></a><a accesskey="u" href="index.html"><img src="images/up.png" alt="Up"></a><a accesskey="h" href="index.html"><img src="images/home.png" alt="Home"></a><a accesskey="n" href="tutorial.html"><img src="images/next.png" alt="Next"></a>
|
|
</div>
|
|
</body>
|
|
</html>
|